class_docstr: [`BeamScorer`] implementing constrained beam search decoding.
  
  
  Args:
      batch_size (`int`):
          Batch Size of `input_ids` for which standard beam search decoding is run in parallel.
      num_beams (`int`):
          Number of beams for beam search.
      constraints (`List[Constraint]`):
          A list of positive constraints represented as `Constraint` objects that must be fulfilled in the generation
          output. For more information, the documentation of [`Constraint`] should be read.
      device (`torch.device`):
          Defines the device type (*e.g.*, `"cpu"` or `"cuda"`) on which this instance of `BeamSearchScorer` will be
          allocated.
      length_penalty (`float`, *optional*, defaults to 1.0):
          Exponential penalty to the length that is used with beam-based generation. It is applied as an exponent to
          the sequence length, which in turn is used to divide the score of the sequence. Since the score is the log
          likelihood of the sequence (i.e. negative), `length_penalty` > 0.0 promotes longer sequences, while
          `length_penalty` < 0.0 encourages shorter sequences.
      do_early_stopping (`bool` or `str`, *optional*, defaults to `False`):
          Controls the stopping condition for beam-based methods, like beam-search. It accepts the following values:
          `True`, where the generation stops as soon as there are `num_beams` complete candidates; `False`, where an
          heuristic is applied and the generation stops when is it very unlikely to find better candidates;
          `"never"`, where the beam search procedure only stops when there cannot be better candidates (canonical
          beam search algorithm).
      num_beam_hyps_to_keep (`int`, *optional*, defaults to 1):
          The number of beam hypotheses that shall be returned upon calling
          [`~transformers.BeamSearchScorer.finalize`].
      num_beam_groups (`int`, *optional*, defaults to 1):
          Number of groups to divide `num_beams` into in order to ensure diversity among different groups of beams.
          See [this paper](https://arxiv.org/pdf/1610.02424.pdf) for more details.
      max_length (`int`, *optional*):
          The maximum length of the sequence to be generated.
class_docstr_tok: ["[","`","BeamScorer","`","]","implementing","constrained","beam","search","decoding",".","Args",":","batch_size","(","`","int","`",")",":","Batch","Size","of","`","input_ids","`","for","which","standard","beam","search","decoding","is","run","in","parallel",".","num_beams","(","`","int","`",")",":","Number","of","beams","for","beam","search",".","constraints","(","`","List","[","Constraint","]","`",")",":","A","list","of","positive","constraints","represented","as","`","Constraint","`","objects","that","must","be","fulfilled","in","the","generation","output",".","For","more","information",",","the","documentation","of","[","`","Constraint","`","]","should","be","read",".","device","(","`","torch.device","`",")",":","Defines","the","device","type","(","*","e.g",".","*",",","`","``","cpu","''","`","or","`","``","cuda","''","`",")","on","which","this","instance","of","`","BeamSearchScorer","`","will","be","allocated",".","length_penalty","(","`","float","`",",","*","optional","*",",","defaults","to","1.0",")",":","Exponential","penalty","to","the","length","that","is","used","with","beam-based","generation",".","It","is","applied","as","an","exponent","to","the","sequence","length",",","which","in","turn","is","used","to","divide","the","score","of","the","sequence",".","Since","the","score","is","the","log","likelihood","of","the","sequence","(","i.e",".","negative",")",",","`","length_penalty","`",">","0.0","promotes","longer","sequences",",","while","`","length_penalty","`","<","0.0","encourages","shorter","sequences",".","do_early_stopping","(","`","bool","`","or","`","str","`",",","*","optional","*",",","defaults","to","`","False","`",")",":","Controls","the","stopping","condition","for","beam-based","methods",",","like","beam-search",".","It","accepts","the","following","values",":","`","True","`",",","where","the","generation","stops","as","soon","as","there","are","`","num_beams","`","complete","candidates",";","`","False","`",",","where","an","heuristic","is","applied","and","the","generation","stops","when","is","it","very","unlikely","to","find","better","candidates",";","`","``","never","''","`",",","where","the","beam","search","procedure","only","stops","when","there","can","not","be","better","candidates","(","canonical","beam","search","algorithm",")",".","num_beam_hyps_to_keep","(","`","int","`",",","*","optional","*",",","defaults","to","1",")",":","The","number","of","beam","hypotheses","that","shall","be","returned","upon","calling","[","`","~transformers.BeamSearchScorer.finalize","`","]",".","num_beam_groups","(","`","int","`",",","*","optional","*",",","defaults","to","1",")",":","Number","of","groups","to","divide","`","num_beams","`","into","in","order","to","ensure","diversity","among","different","groups","of","beams",".","See","[","this","paper","]","(","https",":","\/\/arxiv.org\/pdf\/1610.02424.pdf",")","for","more","details",".","max_length","(","`","int","`",",","*","optional","*",")",":","The","maximum","length","of","the","sequence","to","be","generated","."]
code: def step_sentence_constraint(
      self,
      batch_idx: int,
      input_ids: torch.LongTensor,
      vocab_scores: torch.FloatTensor,
      sent_beam_scores: torch.FloatTensor,
      sent_beam_tokens: torch.LongTensor,
      sent_beam_indices: torch.LongTensor,
      push_progress: bool = False,
  ):
      # sent_beam_tokens are the next {num_beams} number of tokens that are under consideration for this beam
      # (candidate next tokens)
  
      # 1. Adding "advance_tokens"
      #     using ConstraintStateList.advance(), we propose new tokens to be added into this "candidate list" that will
      #     advance us in fulfilling the constraints.
  
      # 2. Selecting best candidates such that we end up with highest probable candidates
      #     that fulfill our constraints.
  
      orig_len = sent_beam_indices.size(0)
      device = sent_beam_indices.device
  
      # initialize states
      topk_contraint_states = self.make_constraint_states(orig_len)
      advance_constraint_states = self.make_constraint_states(orig_len)
  
      sidx, eidx = batch_idx * orig_len, (batch_idx + 1) * orig_len
      this_batch_input_ids = input_ids[sidx:eidx]
      this_batch_token_scores = vocab_scores[sidx:eidx]
      full_hypotheses = torch.cat(
          (
              input_ids[sent_beam_indices],
              sent_beam_tokens.unsqueeze(-1),
          ),
          dim=-1,
      )
  
      # need to make new hypothesis that advance the constraints
      track_new = {
          "new_seqs": full_hypotheses.tolist(),
          "new_states": [],
          "new_indices": [],
          "new_tokens": [],
          "new_scores": [],
      }
      for seq_idx, pre_seq in enumerate(this_batch_input_ids):
          # pre_seq = ith sequence generated before this step.
  
          # input_ids -> (topk) generic beam search best model next tokens
          #           -> (advance) constraints forcing the next token
          # either way, we need to sort them into "banks" later, so store a "ConstraintListState" for all types of
          # hypotheses.
  
          topk_state = topk_contraint_states[seq_idx]
          topk_state.reset(full_hypotheses[seq_idx].cpu().tolist())
  
          advance_state = advance_constraint_states[seq_idx]
          advance_state.reset(pre_seq.cpu().tolist())
  
          if not advance_state.completed:
              advance_tokens = torch.LongTensor(
                  advance_state.advance()
              ).to(device)
              for advance_token in advance_tokens:
                  # since adding each `advance_token` leads to a different hypothesis, create new state instance.
                  new_state = advance_state.copy(stateful=True)
                  new_state.add(advance_token.cpu().tolist())
  
                  advance_seq = (
                      torch.cat(
                          (pre_seq, advance_token.unsqueeze(0)), -1
                      )
                      .cpu()
                      .tolist()
                  )
                  if advance_seq not in track_new["new_seqs"]:
                      # prevent duplicates, which are basically bound to happen in this process.
                      track_new["new_seqs"].append(advance_seq)
                      track_new["new_indices"].append(
                          sidx + seq_idx
                      )  # idx -> global idx across all the batches
                      track_new["new_tokens"].append(advance_token)
                      track_new["new_scores"].append(
                          this_batch_token_scores[seq_idx].take(
                              advance_token
                          )
                      )
                      track_new["new_states"].append(new_state)
          elif push_progress:
              # Basically, `sent_beam_indices` often chooses very little among `input_ids` the generated sequences that
              # actually fulfill our constraints. For example, let constraints == ["loves pies"] and
  
              #     pre_seq_1 = "The child loves pies and" pre_seq_2 = "The child plays in the playground and"
  
              # Without this step, if `sent_beam_indices` is something like [1,1], then
              #     1. `pre_seq_1` won't be added to the list of (topk) hypothesis since it's not in the indices and
              #     2.  it won't be added to the list of (advance) hypothesis since it's completed already. (this is
              #         the else part of `if constraints_completed[seq_idx]`)
              #     3. it ends up simply getting removed from consideration.
  
              # #3 might be fine and actually desired, since it's likely that it's a low-probability output anyways,
              # especially if it's not in the list of `sent_beam_indices`. But this often leads to lengthened beam
              # search times, since completed sequences keep getting removed after all this effort for constrained
              # generation.
  
              # Here, we basically take `pre_seq_1` and to "push" it into the considered list of hypotheses, by simply
              # appending the next likely token in the vocabulary and adding it to the list of hypotheses.
  
              new_score, new_token = torch.max(
                  this_batch_token_scores[seq_idx], 0
              )  # some next probable token
              advance_seq = torch.cat(
                  (pre_seq, new_token.unsqueeze(0)), -1
              )
  
              advance_state = advance_constraint_states[seq_idx]
  
              advance_seq = advance_seq.cpu().tolist()
  
              advance_state.reset(advance_seq)
              if advance_seq not in track_new["new_seqs"]:
                  # but still don't want to have duplicates
                  track_new["new_seqs"].append(advance_seq)
                  track_new["new_indices"].append(seq_idx)
                  track_new["new_tokens"].append(new_token)
                  track_new["new_scores"].append(new_score)
                  track_new["new_states"].append(advance_state)
  
      if len(track_new["new_indices"]) > 0:
          new_indices = torch.tensor(track_new["new_indices"]).to(
              device
          )
          new_tokens = torch.stack(track_new["new_tokens"]).to(device)
          new_scores = torch.stack(track_new["new_scores"]).to(device)
  
          all_states = topk_contraint_states + track_new["new_states"]
          all_tokens = torch.cat((sent_beam_tokens, new_tokens), -1)
          all_scores = torch.cat((sent_beam_scores, new_scores), -1)
          all_banks = torch.tensor(
              [one.get_bank() for one in all_states]
          ).to(device)
  
          zipped = all_banks * 100 + all_scores
          indices = zipped.sort(descending=True).indices
          sorted_banks = all_banks[indices]
  
          # Then we end up with {sorted among bank C}, {sorted among bank C-1}, ..., {sorted among bank 0}
  
          counter = -1
          cur_bank = sorted_banks[0]
          increments = []
          for bank in sorted_banks:
              if bank == cur_bank:
                  counter += 1
              else:
                  counter = 0
                  cur_bank = bank
              increments.append(counter)
          rearrangers = torch.tensor(
              np.argsort(increments, kind="mergesort")
          )
  
          indices = indices[rearrangers][:orig_len]
  
          sent_beam_scores = all_scores[indices]
          sent_beam_tokens = all_tokens[indices]
          sent_beam_indices = torch.cat(
              (sent_beam_indices, new_indices)
          )[indices]
  
      return sent_beam_scores, sent_beam_tokens, sent_beam_indices
  
imports: from abc import ABC, abstractmethod
  from collections import UserDict
  from typing import Dict, List, Optional, Tuple, Union
  import numpy
  import torch
  from ..utils import add_start_docstrings
  from .beam_constraints import Constraint, ConstraintListState
label_desc: Use image node_id 6 for calling the ConstrainedBeamSearchScorer obj's underlying member method code with example usage: obj.step_sentence_constraint(batch_idx, input_ids, vocab_scores, sent_beam_scores, sent_beam_tokens, sent_beam_indices, push_progress) and returns: sent_beam_scores,  sent_beam_tokens,  sent_beam_indices