





from __future__ import annotations

from typing import Any






def 					SCREAMING_SNAKE_CASE__				(							UpperCamelCase__:				list[Any]     ):
		create_state_space_tree(UpperCamelCase__       , []       , 0     )






def 					SCREAMING_SNAKE_CASE__				(							UpperCamelCase__:				list[Any]       , UpperCamelCase__:				list[Any]       , UpperCamelCase__:				int     ):

		if index == len(UpperCamelCase__     ):
				print(UpperCamelCase__     )
				return

		create_state_space_tree(UpperCamelCase__       , UpperCamelCase__       , index + 1     )
		current_subsequence.append(sequence[index]     )
		create_state_space_tree(UpperCamelCase__       , UpperCamelCase__       , index + 1     )
		current_subsequence.pop()


if __name__ == "__main__":
	_lowerCamelCase 					=      [3, 1, 2, 4]
	generate_all_subsequences(seq)

	seq.clear()
	seq.extend(['A', 'B', 'C'])
	generate_all_subsequences(seq)
import tempfile
import unittest

from transformers import TaConfig, is_torch_available
from transformers.testing_utils import (
    require_sentencepiece,
    require_tokenizers,
    require_torch,
    slow,
    torch_device,
)

from ...generation.test_utils import GenerationTesterMixin
from ...test_modeling_common import ModelTesterMixin, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
				import torch

				from transformers import AutoTokenizer, UMTaForConditionalGeneration, UMTaForQuestionAnswering, UMTaModel



class        lowerCamelCase__				:





			def __init__(       self	:	Union[str, Any]  ,  lowercase__	:	List[Any]  ,  lowercase__	:	Dict=99  ,  lowercase__	:	List[Any]=13  ,  lowercase__	:	Union[str, Any]=7  ,  lowercase__	:	int=9  ,  lowercase__	:	List[str]=True  ,  lowercase__	:	str=True  ,  lowercase__	:	Any=False  ,  lowercase__	:	int=32  ,  lowercase__	:	Any=5  ,  lowercase__	:	int=4  ,  lowercase__	:	int=37  ,  lowercase__	:	List[str]=8  ,  lowercase__	:	Optional[int]=0.1  ,  lowercase__	:	List[Any]=0.0_0_2  ,  lowercase__	:	str=1  ,  lowercase__	:	List[str]=0  ,  lowercase__	:	Optional[int]=0  ,  lowercase__	:	List[str]=None  ,  lowercase__	:	Any=None  ,  ):
										_lowerCAmelCase							=							parent
										_lowerCAmelCase							=							batch_size
										_lowerCAmelCase							=							encoder_seq_length
										_lowerCAmelCase							=							decoder_seq_length
										# For common tests
										_lowerCAmelCase							=							self.decoder_seq_length
										_lowerCAmelCase							=							is_training
										_lowerCAmelCase							=							use_attention_mask
										_lowerCAmelCase							=							use_labels
										_lowerCAmelCase							=							vocab_size
										_lowerCAmelCase							=							hidden_size
										_lowerCAmelCase							=							num_hidden_layers
										_lowerCAmelCase							=							num_attention_heads
										_lowerCAmelCase							=							d_ff
										_lowerCAmelCase							=							relative_attention_num_buckets
										_lowerCAmelCase							=							dropout_rate
										_lowerCAmelCase							=							initializer_factor
										_lowerCAmelCase							=							eos_token_id
										_lowerCAmelCase							=							pad_token_id
										_lowerCAmelCase							=							decoder_start_token_id
										_lowerCAmelCase							=							None
										_lowerCAmelCase							=							decoder_layers





			def   SCREAMING_SNAKE_CASE__     (       self	:	str						):
										return TaConfig.from_pretrained('google/umt5-base'						)





			def   SCREAMING_SNAKE_CASE__     (       self	:	int  ,  lowercase__	:	List[str]  ,  lowercase__	:	Any  ,  lowercase__	:	int  ,  lowercase__	:	int=None  ,  lowercase__	:	str=None  ,  lowercase__	:	int=None  ,  lowercase__	:	Optional[int]=None  ,  lowercase__	:	List[Any]=None  ,  ):
										if attention_mask is None:
																	_lowerCAmelCase							=							input_ids.ne(config.pad_token_id						)
										if decoder_attention_mask is None:
																	_lowerCAmelCase							=							decoder_input_ids.ne(config.pad_token_id						)
										if head_mask is None:
																	_lowerCAmelCase							=							torch.ones(config.num_hidden_layers  ,  config.num_attention_heads  ,  device=lowercase__						)
										if decoder_head_mask is None:
																	_lowerCAmelCase							=							torch.ones(config.num_decoder_layers  ,  config.num_attention_heads  ,  device=lowercase__						)
										if cross_attn_head_mask is None:
																	_lowerCAmelCase							=							torch.ones(
																	    config.num_decoder_layers  ,  config.num_attention_heads  ,  device=lowercase__						)
										return {
										    "input_ids": input_ids,
										    "decoder_input_ids": decoder_input_ids,
										    "attention_mask": attention_mask,
										    "decoder_attention_mask": decoder_attention_mask,
										    "head_mask": head_mask,
										    "decoder_head_mask": decoder_head_mask,
										    "cross_attn_head_mask": cross_attn_head_mask,
										}





			def   SCREAMING_SNAKE_CASE__     (       self	:	List[Any]						):
										_lowerCAmelCase							=							ids_tensor([self.batch_size, self.encoder_seq_length]  ,  self.vocab_size						)
										_lowerCAmelCase							=							ids_tensor([self.batch_size, self.decoder_seq_length]  ,  self.vocab_size						)

										# we need to clamp the input ids here to avoid having pad token in between
										# this is because for NllbMoe the position_ids are prepared such that
										# all pad tokens have pos id = 2 and rest are between 2..seq_length
										# and the seq_length here is seq_length - num_pad_tokens
										# but when using past, there is no way of knowing if the past input ids had
										# pad tokens in them, which results in incorrect seq_lenth and which in turn results in
										# position_ids being off by num_pad_tokens in past input
										_lowerCAmelCase							=							input_ids.clamp(self.pad_token_id + 1						)
										_lowerCAmelCase							=							decoder_input_ids.clamp(self.pad_token_id + 1						)

										_lowerCAmelCase							=							self.get_config()
										_lowerCAmelCase							=							config.num_attention_heads
										_lowerCAmelCase							=							self.prepare_inputs_dict(lowercase__  ,  lowercase__  ,  lowercase__						)
										return config, input_dict





			def   SCREAMING_SNAKE_CASE__     (       self	:	Dict						):
										_lowerCAmelCase			,		_lowerCAmelCase							=							self.prepare_config_and_inputs()
										return config, inputs_dict





			def   SCREAMING_SNAKE_CASE__     (       self	:	Tuple						):
										return TaConfig(
										    vocab_size=1_66  ,  d_model=self.hidden_size  ,  d_ff=self.d_ff  ,  d_kv=self.hidden_size // self.num_attention_heads  ,  num_layers=self.num_hidden_layers  ,  num_decoder_layers=self.decoder_layers  ,  num_heads=self.num_attention_heads  ,  relative_attention_num_buckets=self.relative_attention_num_buckets  ,  dropout_rate=self.dropout_rate  ,  initializer_factor=self.initializer_factor  ,  eos_token_id=self.eos_token_id  ,  bos_token_id=self.pad_token_id  ,  pad_token_id=self.pad_token_id  ,  decoder_start_token_id=self.decoder_start_token_id  ,  )





			def   SCREAMING_SNAKE_CASE__     (       self	:	Optional[Any]						):
										return TaConfig(
										    vocab_size=self.vocab_size  ,  d_model=self.hidden_size  ,  d_ff=self.d_ff  ,  d_kv=self.hidden_size // self.num_attention_heads  ,  num_layers=self.num_hidden_layers  ,  num_decoder_layers=self.decoder_layers  ,  num_heads=self.num_attention_heads  ,  relative_attention_num_buckets=self.relative_attention_num_buckets  ,  dropout_rate=self.dropout_rate  ,  initializer_factor=self.initializer_factor  ,  eos_token_id=self.eos_token_id  ,  bos_token_id=self.pad_token_id  ,  pad_token_id=self.pad_token_id  ,  decoder_start_token_id=self.decoder_start_token_id  ,  )





			def   SCREAMING_SNAKE_CASE__     (       self	:	Dict  ,  lowercase__	:	List[str]  ,  lowercase__	:	str  ,  lowercase__	:	Any  ,  lowercase__	:	Optional[int]  ,  lowercase__	:	Tuple  ,  lowercase__	:	Dict  ,  ):
										_lowerCAmelCase							=							UMTaModel(config=lowercase__						)
										model.to(lowercase__						)
										model.eval()
										_lowerCAmelCase							=							model(
										    input_ids=lowercase__  ,  decoder_input_ids=lowercase__  ,  attention_mask=lowercase__  ,  decoder_attention_mask=lowercase__  ,  )
										_lowerCAmelCase							=							model(input_ids=lowercase__  ,  decoder_input_ids=lowercase__						)
										_lowerCAmelCase							=							result.last_hidden_state
										_lowerCAmelCase							=							result.past_key_values
										_lowerCAmelCase							=							result.encoder_last_hidden_state

										self.parent.assertEqual(encoder_output.size()  ,  (self.batch_size, self.encoder_seq_length, self.hidden_size)						)
										self.parent.assertEqual(decoder_output.size()  ,  (self.batch_size, self.decoder_seq_length, self.hidden_size)						)
										# There should be `num_layers` key value embeddings stored in decoder_past
										self.parent.assertEqual(len(lowercase__						)  ,  config.num_layers						)
										# There should be a self attn key, a self attn value, a cross attn key and a cross attn value stored in each decoder_past tuple
										self.parent.assertEqual(len(decoder_past[0]						)  ,  4						)





			def   SCREAMING_SNAKE_CASE__     (       self	:	Any  ,  lowercase__	:	Tuple  ,  lowercase__	:	Tuple  ,  lowercase__	:	List[Any]  ,  lowercase__	:	Dict  ,  lowercase__	:	str  ,  lowercase__	:	List[Any]  ,  ):
										_lowerCAmelCase							=							UMTaModel(config=lowercase__						).get_decoder().to(lowercase__						).eval()
										# first forward pass
										_lowerCAmelCase							=							model(lowercase__  ,  use_cache=lowercase__						)
										_lowerCAmelCase							=							model(lowercase__						)
										_lowerCAmelCase							=							model(lowercase__  ,  use_cache=lowercase__						)

										self.parent.assertTrue(len(lowercase__						) == len(lowercase__						)						)
										self.parent.assertTrue(len(lowercase__						) == len(lowercase__						) + 1						)

										_lowerCAmelCase			,		_lowerCAmelCase							=							outputs.to_tuple()

										# create hypothetical next token and extent to next_input_ids
										_lowerCAmelCase							=							ids_tensor((self.batch_size, 1)  ,  config.vocab_size						)

										# append to next input_ids and
										_lowerCAmelCase							=							torch.cat([input_ids, next_tokens]  ,  dim=-1						)

										_lowerCAmelCase							=							model(lowercase__						)['last_hidden_state']
										_lowerCAmelCase							=							model(lowercase__  ,  past_key_values=lowercase__						)['last_hidden_state']

										# select random slice
										_lowerCAmelCase							=							ids_tensor((1,)  ,  output_from_past.shape[-1]						).item()
										_lowerCAmelCase							=							output_from_no_past[:, -1, random_slice_idx].detach()
										_lowerCAmelCase							=							output_from_past[:, 0, random_slice_idx].detach()

										# test that outputs are equal for slice
										self.parent.assertTrue(torch.allclose(lowercase__  ,  lowercase__  ,  atol=1e-3						)						)





			def   SCREAMING_SNAKE_CASE__     (       self	:	Optional[int]  ,  lowercase__	:	Tuple  ,  lowercase__	:	Dict  ,  ):
										_lowerCAmelCase							=							UMTaModel(config=lowercase__						).to(lowercase__						).half().eval()
										_lowerCAmelCase							=							model(**lowercase__						)['last_hidden_state']
										self.parent.assertFalse(torch.isnan(lowercase__						).any().item()						)







@require_torch
class        lowerCamelCase__				(   UpperCAmelCase       ,UpperCAmelCase       ,UpperCAmelCase       ,unittest.TestCase				):
			UpperCamelCase__    							=(
			    (UMTaModel, UMTaForConditionalGeneration, UMTaForQuestionAnswering) if is_torch_available() else ()
			)
			UpperCamelCase__    							=(UMTaForConditionalGeneration,) if is_torch_available() else ()
			UpperCamelCase__    							=(
			    {
			        "conversational": UMTaForConditionalGeneration,
			        "feature-extraction": UMTaModel,
			        "summarization": UMTaForConditionalGeneration,
			        "text2text-generation": UMTaForConditionalGeneration,
			        "translation": UMTaForConditionalGeneration,
			        "question-answering": UMTaForQuestionAnswering,
			    }
			    if is_torch_available()
			    else {}
			)
			UpperCamelCase__    							=True
			UpperCamelCase__    							=False
			UpperCamelCase__    							=False
			UpperCamelCase__    							=True
			UpperCamelCase__    							=True
			# The small UMT5 model needs higher percentages for CPU/MP tests
			UpperCamelCase__    							=[0.8, 0.9]





			def   SCREAMING_SNAKE_CASE__     (       self	:	List[str]						):
										_lowerCAmelCase							=							UMTaModelTester(self						)





			@unittest.skip('Test has a segmentation fault on torch 1.8.0'						)
			def   SCREAMING_SNAKE_CASE__     (       self	:	str						):
										_lowerCAmelCase							=							self.model_tester.prepare_config_and_inputs()
										_lowerCAmelCase							=							UMTaModel(config_and_inputs[0]						).to(lowercase__						)
										with tempfile.TemporaryDirectory() as tmpdirname:
																	torch.onnx.export(
																	    lowercase__  ,  (config_and_inputs[1], config_and_inputs[3], config_and_inputs[2])  ,  f'{tmpdirname}/t5_test.onnx'  ,  export_params=lowercase__  ,  opset_version=9  ,  input_names=['input_ids', 'decoder_input_ids']  ,  )





			@unittest.skipIf(torch_device == 'cpu'  ,  'Cant do half precision'						)
			def   SCREAMING_SNAKE_CASE__     (       self	:	Optional[int]						):
										_lowerCAmelCase							=							self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_model_fpaa_forward(*lowercase__						)





			def   SCREAMING_SNAKE_CASE__     (       self	:	str						):
										_lowerCAmelCase							=							['encoder_attentions', 'decoder_attentions', 'cross_attentions']
										_lowerCAmelCase							=							self.model_tester.prepare_config_and_inputs()
										_lowerCAmelCase							=							config_and_inputs[0]
										_lowerCAmelCase							=							UMTaForConditionalGeneration(lowercase__						).eval()
										model.to(lowercase__						)

										_lowerCAmelCase							=							{
										    'head_mask': torch.zeros(config.num_layers  ,  config.num_heads  ,  device=lowercase__						),
										    'decoder_head_mask': torch.zeros(config.num_decoder_layers  ,  config.num_heads  ,  device=lowercase__						),
										    'cross_attn_head_mask': torch.zeros(config.num_decoder_layers  ,  config.num_heads  ,  device=lowercase__						),
										}

										for attn_name, (name, mask) in zip(lowercase__  ,  head_masking.items()						):
																	_lowerCAmelCase							=							{name: mask}
																	# Explicitly pass decoder_head_mask as it is required from T5 model when head_mask specified
																	if name == "head_mask":
																								_lowerCAmelCase							=							torch.ones(
																								    config.num_decoder_layers  ,  config.num_heads  ,  device=lowercase__						)

																	_lowerCAmelCase							=							model.generate(
																	    config_and_inputs[1]['input_ids']  ,  num_beams=1  ,  max_length=3  ,  output_attentions=lowercase__  ,  return_dict_in_generate=lowercase__  ,  **lowercase__  ,  )
																	# We check the state of decoder_attentions and cross_attentions just from the last step
																	_lowerCAmelCase							=							out[attn_name] if attn_name == attention_names[0] else out[attn_name][-1]
																	self.assertEqual(sum([w.sum().item() for w in attn_weights]						)  ,  0.0						)





			@unittest.skip('Does not work on the tiny model as we keep hitting edge cases.'						)
			def   SCREAMING_SNAKE_CASE__     (       self	:	Any						):
										pass







@require_torch
@require_sentencepiece
@require_tokenizers
class        lowerCamelCase__				(   unittest.TestCase				):





			@slow
			@unittest.skip(
			    'Unless we stop stripping left and right by default for all special tokens, the expected ids obtained here will not match the original ones. Wait for https://github.com/huggingface/transformers/pull/23909 to be merged'						)
			def   SCREAMING_SNAKE_CASE__     (       self	:	str						):
										_lowerCAmelCase							=							UMTaForConditionalGeneration.from_pretrained('google/umt5-small'  ,  return_dict=lowercase__						).to(lowercase__						)
										_lowerCAmelCase							=							AutoTokenizer.from_pretrained('google/umt5-small'  ,  use_fast=lowercase__  ,  legacy=lowercase__						)
										_lowerCAmelCase							=							[
										    'Bonjour monsieur <extra_id_0> bien <extra_id_1>.',
										    'No se como puedo <extra_id_0>.',
										    'This is the reason why we <extra_id_0> them.',
										    'The <extra_id_0> walks in <extra_id_1>, seats',
										    'A <extra_id_0> walks into a bar and orders a <extra_id_1> with <extra_id_2> pinch of <extra_id_3>.',
										]
										_lowerCAmelCase							=							tokenizer(lowercase__  ,  return_tensors='pt'  ,  padding=lowercase__						).input_ids
										# fmt: off
										_lowerCAmelCase							=							torch.tensor(
										    [
										        [ 3_85_30, 21_07_03, 25_62_99, 14_10, 25_62_98, 2_74, 1, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0],
										        [   8_26, 3_21, 6_71, 2_59_22, 25_62_99, 2_74, 1, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0],
										        [  14_60, 3_39, 3_12, 1_90_14, 1_06_20, 7_58, 25_62_99, 23_55,2_74, 1, 0, 0, 0, 0, 0, 0,0, 0],
										        [   5_17, 25_62_99, 1_48_69, 2_81, 3_01, 25_62_98, 2_75, 11_99_83,1, 0, 0, 0, 0, 0, 0, 0,0, 0],
										        [   3_20, 25_62_99, 1_48_69, 2_81, 22_34, 2_89, 22_75, 3_33,6_13_91, 2_89, 25_62_98, 5_43, 25_62_97, 16_87_14, 3_29, 25_62_96,2_74, 1],
										    ]						)
										# fmt: on
										torch.testing.assert_allclose(lowercase__  ,  lowercase__						)

										_lowerCAmelCase							=							model.generate(input_ids.to(lowercase__						)						)
										_lowerCAmelCase							=							[
										    '<pad><extra_id_0> et<extra_id_1> [eod] <extra_id_2><extra_id_55>.. [eod] 💐 💐 💐 💐 💐 💐 💐 💐 💐 💐 💐 <extra_id_56>ajšietosto<extra_id_56>lleux<extra_id_19><extra_id_6>ajšie</s>',
										    '<pad><extra_id_0>.<extra_id_1>.,<0x0A>...spech <0x0A><extra_id_20> <extra_id_21></s><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad>',
										    '<pad><extra_id_0> are not going to be a part of the world. We are not going to be a part of<extra_id_1> and<extra_id_2><0x0A><extra_id_48>.<extra_id_48></s><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad>',
										    '<pad><extra_id_0> door<extra_id_1>, the door<extra_id_2> 피해[/</s><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad>',
										    '<pad><extra_id_0>nyone who<extra_id_1> drink<extra_id_2> a<extra_id_3> alcohol<extra_id_4> A<extra_id_5> A. This<extra_id_6> I<extra_id_7><extra_id_52><extra_id_53></s><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad>',
										]
										_lowerCAmelCase							=							tokenizer.batch_decode(lowercase__						)
										self.assertEqual(lowercase__  ,  lowercase__						)






