





"""simple docstring"""


import functools
from math import sqrt
from time import time





def 				a__      (	_UpperCAmelCase						,  *_UpperCAmelCase						,  **_UpperCAmelCase						)     ->	Union[str, Any]:

 '''simple docstring'''






 snake_case__     				=					time()
 snake_case__     				=					func(*_UpperCAmelCase						,  **_UpperCAmelCase						)
 snake_case__     				=					time()
 if int(end - start						) > 0:
  print(f"{func.__name__} runtime: {(end - start):0.4f} s"						)
 else:
  print(f"{func.__name__} runtime: {(end - start) * 1_0_0_0:0.4f} ms"						)
 return output





def 				a__      (	_UpperCAmelCase						)     ->	list[int]:

 '''simple docstring'''






 if n < 0:
  raise Exception("n is negative"						)
 if n == 0:
  return [0]
 snake_case__     				=					[0, 1]
 for _ in range(n - 1						):
  fib.append(fib[-1] + fib[-2]						)
 return fib





def 				a__      (	_UpperCAmelCase						)     ->	list[int]:

 '''simple docstring'''






 def fib_recursive_term(_UpperCAmelCase						) -> int:
  if i < 0:
   raise Exception("n is negative"						)
  if i < 2:
   return i
  return fib_recursive_term(i - 1						) + fib_recursive_term(i - 2						)

 if n < 0:
  raise Exception("n is negative"						)
 return [fib_recursive_term(_UpperCAmelCase						) for i in range(n + 1						)]





def 				a__      (	_UpperCAmelCase						)     ->	list[int]:

 '''simple docstring'''






 @functools.cache
 def fib_recursive_term(_UpperCAmelCase						) -> int:
  if i < 0:
   raise Exception("n is negative"						)
  if i < 2:
   return i
  return fib_recursive_term(i - 1						) + fib_recursive_term(i - 2						)

 if n < 0:
  raise Exception("n is negative"						)
 return [fib_recursive_term(_UpperCAmelCase						) for i in range(n + 1						)]





def 				a__      (	_UpperCAmelCase						)     ->	list[int]:

 '''simple docstring'''






 if n < 0:
  raise Exception("n is negative"						)
 # Cache must be outside recursuive function
 # other it will reset every time it calls itself.
 snake_case__     				=					{0: 0, 1: 1, 2: 1}  # Prefilled cache

 def rec_fn_memoized(_UpperCAmelCase						) -> int:
  if num in cache:
   return cache[num]

  snake_case__     				=					rec_fn_memoized(num - 1						) + rec_fn_memoized(num - 2						)
  snake_case__     				=					value
  return value

 return [rec_fn_memoized(_UpperCAmelCase						) for i in range(n + 1						)]





def 				a__      (	_UpperCAmelCase						)     ->	list[int]:

 '''simple docstring'''






 if n < 0:
  raise Exception("n is negative"						)
 if n >= 1_4_7_5:
  raise Exception("n is too large"						)
 snake_case__     				=					sqrt(5						)
 snake_case__     				=					(1 + sqrt_a) / 2
 return [round(phi**i / sqrt_a						) for i in range(n + 1						)]


if __name__ == "__main__":
   a__       :  List[Any]       		=					3_0
   time_func(fib_iterative, num)
   time_func(fib_recursive, num)  # Around 3s runtime
   time_func(fib_recursive_cached, num)  # Around 0ms runtime
   time_func(fib_memoization, num)
   time_func(fib_binet, num)






"""simple docstring"""




from __future__ import annotations

import copy
import os
import tempfile
from importlib import import_module
from math import isnan

from transformers import is_tf_available
from transformers.models.auto import get_values
from transformers.testing_utils import _tf_gpu_memory_limit, require_tf, slow

from ..test_modeling_tf_common import ids_tensor


if is_tf_available():
     import numpy as np
     import tensorflow as tf

     from transformers import (
         TF_MODEL_FOR_CAUSAL_LM_MAPPING,
         TF_MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING,
         TF_MODEL_FOR_MASKED_LM_MAPPING,
         TF_MODEL_FOR_MULTIPLE_CHOICE_MAPPING,
         TF_MODEL_FOR_NEXT_SENTENCE_PREDICTION_MAPPING,
         TF_MODEL_FOR_PRETRAINING_MAPPING,
         TF_MODEL_FOR_QUESTION_ANSWERING_MAPPING,
         TF_MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING,
         TF_MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
         TF_MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING,
         TFSharedEmbeddings,
     )

     if _tf_gpu_memory_limit is not None:
          _UpperCamelCase:					Optional[int]     				=	tf.config.list_physical_devices('GPU')
          for gpu in gpus:
               # Restrict TensorFlow to only allocate x GB of memory on the GPUs
               try:
                    tf.config.set_logical_device_configuration(
                        gpu, [tf.config.LogicalDeviceConfiguration(memory_limit=_tf_gpu_memory_limit)]
                    )
                    _UpperCamelCase:					List[str]     				=	tf.config.list_logical_devices('GPU')
                    print('Logical GPUs', logical_gpus)
               except RuntimeError as e:
                    # Virtual devices must be set before GPUs have been initialized
                    print(e)


@require_tf
class 	a__		:
   _lowerCamelCase       				=					None
   _lowerCamelCase       				=					()
   _lowerCamelCase       				=					()
   _lowerCamelCase       				=					True
   _lowerCamelCase       				=					True
   _lowerCamelCase       				=					True
   _lowerCamelCase       				=					False


   def 							lowercase					(				self   :				Dict,  lowerCAmelCase   :				Dict,  lowerCAmelCase   :				Optional[Any],  lowerCAmelCase   :				Optional[int]=False      )     ->							dict:
         lowercase	:   Tuple											= copy.deepcopy(lowerCAmelCase      )

         if model_class in get_values(lowerCAmelCase      ):
               lowercase	:   Union[str, Any]											= {
                   k: tf.tile(tf.expand_dims(lowerCAmelCase,  1      ),  (1, self.model_tester.num_choices) + (1,) * (v.ndim - 1)      )
                   if isinstance(lowerCAmelCase,  tf.Tensor      ) and v.ndim > 0
                   else v
                   for k, v in inputs_dict.items()
               }

         if return_labels:
               if model_class in get_values(lowerCAmelCase      ):
                     lowercase	:   List[str]											= tf.ones(self.model_tester.batch_size,  dtype=tf.intaa      )
               elif model_class in get_values(lowerCAmelCase      ):
                     lowercase	:   Optional[Any]											= tf.zeros(self.model_tester.batch_size,  dtype=tf.intaa      )
                     lowercase	:   Union[str, Any]											= tf.zeros(self.model_tester.batch_size,  dtype=tf.intaa      )
               elif model_class in [
                   *get_values(lowerCAmelCase      ),
                   *get_values(lowerCAmelCase      ),
               ]:
                     lowercase	:   str											= tf.zeros(self.model_tester.batch_size,  dtype=tf.intaa      )
               elif model_class in get_values(lowerCAmelCase      ):
                     lowercase	:   str											= tf.zeros(self.model_tester.batch_size,  dtype=tf.intaa      )
               elif model_class in [
                   *get_values(lowerCAmelCase      ),
                   *get_values(lowerCAmelCase      ),
                   *get_values(lowerCAmelCase      ),
                   *get_values(lowerCAmelCase      ),
                   *get_values(lowerCAmelCase      ),
               ]:
                     lowercase	:   Tuple											= tf.zeros(
                         (self.model_tester.batch_size, self.model_tester.seq_length),  dtype=tf.intaa      )
         return inputs_dict


   @slow
   def 							lowercase					(				self   :				int      )     ->							Union[str, Any]:
         lowercase						,     lowercase	:   Optional[int]											= self.model_tester.prepare_config_and_inputs_for_common()
         for model_class in self.all_model_classes[:2]:
               lowercase	:   List[str]											= self._prepare_for_class(lowerCAmelCase,  lowerCAmelCase      )
               lowercase	:   List[Any]											= model_class(lowerCAmelCase      )

               @tf.function
               def run_in_graph_mode():
                     return model(lowerCAmelCase      )

               lowercase	:   Optional[Any]											= run_in_graph_mode()
               self.assertIsNotNone(lowerCAmelCase      )


   @slow
   def 							lowercase					(				self   :				List[str]      )     ->							Optional[int]:
         lowercase						,     lowercase	:   Tuple											= self.model_tester.prepare_config_and_inputs_for_common()
         for model_class in self.all_model_classes[:2]:
               lowercase	:   Optional[Any]											= self._prepare_for_class(lowerCAmelCase,  lowerCAmelCase      )
               lowercase	:   int											= model_class(lowerCAmelCase      )

               @tf.function(experimental_compile=lowerCAmelCase      )
               def run_in_graph_mode():
                     return model(lowerCAmelCase      )

               lowercase	:   int											= run_in_graph_mode()
               self.assertIsNotNone(lowerCAmelCase      )


   @slow
   def 							lowercase					(				self   :				List[Any]      )     ->							Any:
         # This is a copy of the test_keras_fit method, but we use XLA compilation instead of eager
         lowercase						,     lowercase	:   Tuple											= self.model_tester.prepare_config_and_inputs_for_common()
         for model_class in self.all_model_classes[:2]:
               lowercase	:   Optional[Any]											= model_class(lowerCAmelCase      )
               if getattr(lowerCAmelCase,  'hf_compute_loss',  lowerCAmelCase      ):
                     # Test that model correctly compute the loss with kwargs
                     lowercase	:   int											= self._prepare_for_class(inputs_dict.copy(),  lowerCAmelCase,  return_labels=lowerCAmelCase      )
                     # Is there a better way to remove these decoder inputs?
                     lowercase	:   Dict											= {
                         key: val
                         for key, val in prepared_for_class.items()
                         if key not in ('head_mask', 'decoder_head_mask', 'cross_attn_head_mask', 'decoder_input_ids')
                     }

                     lowercase	:   int											= {
                         'labels',
                         'label',
                         'label_ids',
                         'start_positions',
                         'start_position',
                         'end_positions',
                         'end_position',
                         'next_sentence_label',
                     }
                     lowercase	:   int											= possible_label_cols.intersection(set(lowerCAmelCase      )      )
                     self.assertGreater(len(lowerCAmelCase      ),  0,  msg='No matching label names found!'      )
                     lowercase	:   Union[str, Any]											= {key: val for key, val in prepared_for_class.items() if key in label_names}
                     lowercase	:   Tuple											= {key: val for key, val in prepared_for_class.items() if key not in label_names}
                     self.assertGreater(len(lowerCAmelCase      ),  0      )

                     # Make sure it works with XLA!
                     model.compile(optimizer=tf.keras.optimizers.SGD(0.0      ),  jit_compile=lowerCAmelCase      )
                     # Make sure the model fits without crashing regardless of where we pass the labels
                     lowercase	:   str											= model.fit(
                         lowerCAmelCase,  validation_data=lowerCAmelCase,  steps_per_epoch=1,  validation_steps=1,  shuffle=lowerCAmelCase,  verbose=0,  )
                     lowercase	:   Dict											= history.history['loss'][0]
                     self.assertTrue(not isnan(lowerCAmelCase      )      )
                     lowercase	:   List[str]											= history.history['val_loss'][0]
                     self.assertTrue(not isnan(lowerCAmelCase      )      )

                     # Now test it with separate labels, to make sure that path works in XLA too.
                     lowercase	:   int											= model_class(lowerCAmelCase      )
                     model.compile(optimizer=tf.keras.optimizers.SGD(0.0      ),  jit_compile=lowerCAmelCase      )
                     lowercase	:   Optional[Any]											= model.fit(
                         lowerCAmelCase,  lowerCAmelCase,  validation_data=(inputs_minus_labels, labels),  steps_per_epoch=1,  validation_steps=1,  shuffle=lowerCAmelCase,  verbose=0,  )

                     lowercase	:   str											= history.history['loss'][0]
                     self.assertTrue(not isnan(lowerCAmelCase      )      )
                     lowercase	:   Optional[int]											= history.history['val_loss'][0]
                     self.assertTrue(not isnan(lowerCAmelCase      )      )


   @slow
   def 							lowercase					(				self   :				Optional[Any]      )     ->							Tuple:
         lowercase						,     lowercase	:   int											= self.model_tester.prepare_config_and_inputs_for_common()
         lowercase	:   List[str]											= True
         lowercase	:   Dict											= True

         if hasattr(lowerCAmelCase,  'use_cache'      ):
               lowercase	:   Optional[int]											= True

         lowercase	:   Tuple											= getattr(self.model_tester,  'encoder_seq_length',  self.model_tester.seq_length      )
         lowercase	:   Tuple											= getattr(self.model_tester,  'key_length',  lowerCAmelCase      )

         for model_class in self.all_model_classes[:2]:
               lowercase	:   Any											= self._prepare_for_class(lowerCAmelCase,  lowerCAmelCase      )
               lowercase	:   Optional[int]											= model_class(lowerCAmelCase      )
               model.build()
               lowercase	:   Dict											= len(model(lowerCAmelCase      )      )

               for key in list(class_inputs_dict.keys()      ):
                     # Remove keys not in the serving signature, as the SavedModel will not be compiled to deal with them
                     if key not in model.input_signature:
                           del class_inputs_dict[key]
                     # Check it's a tensor, in case the inputs dict has some bools in it too
                     elif isinstance(class_inputs_dict[key],  tf.Tensor      ) and class_inputs_dict[key].dtype.is_integer:
                           lowercase	:   Tuple											= tf.cast(class_inputs_dict[key],  tf.intaa      )

               if set(class_inputs_dict.keys()      ) != set(model.input_signature.keys()      ):
                     continue  # Some models have inputs that the preparation functions don't create, we skip those

               with tempfile.TemporaryDirectory() as tmpdirname:
                     model.save_pretrained(lowerCAmelCase,  saved_model=lowerCAmelCase      )
                     lowercase	:   Any											= os.path.join(lowerCAmelCase,  'saved_model',  '1'      )
                     lowercase	:   List[Any]											= tf.keras.models.load_model(lowerCAmelCase      )
                     lowercase	:   Dict											= model(lowerCAmelCase      )

                     if self.is_encoder_decoder:
                           lowercase	:   List[str]											= outputs['encoder_hidden_states']
                           lowercase	:   Union[str, Any]											= outputs['encoder_attentions']
                     else:
                           lowercase	:   Any											= outputs['hidden_states']
                           lowercase	:   Optional[Any]											= outputs['attentions']

                     self.assertEqual(len(lowerCAmelCase      ),  lowerCAmelCase      )

                     lowercase	:   Optional[Any]											= getattr(
                         self.model_tester,  'expected_num_hidden_layers',  self.model_tester.num_hidden_layers + 1      )

                     self.assertEqual(len(lowerCAmelCase      ),  lowerCAmelCase      )
                     self.assertListEqual(
                         list(output_hidden_states[0].shape[-2:]      ),  [self.model_tester.seq_length, self.model_tester.hidden_size],  )

                     self.assertEqual(len(lowerCAmelCase      ),  self.model_tester.num_hidden_layers      )
                     self.assertListEqual(
                         list(output_attentions[0].shape[-3:]      ),  [self.model_tester.num_attention_heads, encoder_seq_length, encoder_key_length],  )


   @slow
   def 							lowercase					(				self   :				Dict      )     ->							Union[str, Any]:
         tf.keras.mixed_precision.set_global_policy('mixed_float16'      )

         # try/finally block to ensure subsequent tests run in float32
         try:
               lowercase						,     lowercase	:   List[str]											= self.model_tester.prepare_config_and_inputs_for_common()
               for model_class in self.all_model_classes[:2]:
                     lowercase	:   str											= self._prepare_for_class(lowerCAmelCase,  lowerCAmelCase      )
                     lowercase	:   Tuple											= model_class(lowerCAmelCase      )
                     lowercase	:   int											= model(lowerCAmelCase      )

                     self.assertIsNotNone(lowerCAmelCase      )
         finally:
               tf.keras.mixed_precision.set_global_policy('float32'      )


   @slow
   def 							lowercase					(				self   :				Dict      )     ->							List[str]:
         lowercase						,     lowercase	:   int											= self.model_tester.prepare_config_and_inputs_for_common()
         # head_mask and decoder_head_mask has different shapes than other input args
         if "head_mask" in inputs_dict:
               del inputs_dict["head_mask"]
         if "decoder_head_mask" in inputs_dict:
               del inputs_dict["decoder_head_mask"]
         if "cross_attn_head_mask" in inputs_dict:
               del inputs_dict["cross_attn_head_mask"]
         lowercase	:   Dict											= {
             module_member
             for model_class in self.all_model_classes
             for module in (import_module(model_class.__module__      ),)
             for module_member_name in dir(lowerCAmelCase      )
             if module_member_name.endswith('MainLayer'      )
             for module_member in (getattr(lowerCAmelCase,  lowerCAmelCase      ),)
             if isinstance(lowerCAmelCase,  lowerCAmelCase      )
             and tf.keras.layers.Layer in module_member.__bases__
             and getattr(lowerCAmelCase,  '_keras_serializable',  lowerCAmelCase      )
         }

         for main_layer_class in tf_main_layer_classes:
               # T5MainLayer needs an embed_tokens parameter when called without the inputs_embeds parameter
               if "T5" in main_layer_class.__name__:
                     # Take the same values than in TFT5ModelTester for this shared layer
                     lowercase	:   List[Any]											= TFSharedEmbeddings(self.model_tester.vocab_size,  self.model_tester.hidden_size,  name='shared'      )
                     lowercase	:   str											= False
                     lowercase	:   Any											= main_layer_class(lowerCAmelCase,  embed_tokens=lowerCAmelCase      )
               else:
                     lowercase	:   Tuple											= main_layer_class(lowerCAmelCase      )

               lowercase	:   Optional[int]											= {
                   name: tf.keras.Input(tensor.shape[1:],  dtype=tensor.dtype      ) for name, tensor in inputs_dict.items()
               }

               if hasattr(self.model_tester,  'num_labels'      ):
                     lowercase	:   int											= self.model_tester.num_labels
               else:
                     lowercase	:   Optional[int]											= 2

               lowercase	:   Any											= tf.data.Dataset.from_tensor_slices(
                   (inputs_dict, np.ones((self.model_tester.batch_size, self.model_tester.seq_length, num_labels, 1)      ))      ).batch(1      )

               lowercase	:   str											= main_layer(lowerCAmelCase      )[0]
               lowercase	:   List[Any]											= tf.keras.layers.Dense(lowerCAmelCase,  activation='softmax',  name='outputs'      )(lowerCAmelCase      )
               lowercase	:   Optional[Any]											= tf.keras.models.Model(inputs=lowerCAmelCase,  outputs=[outputs]      )

               model.compile(loss='binary_crossentropy',  optimizer='adam',  metrics=['binary_accuracy']      )
               model.fit(lowerCAmelCase,  epochs=1      )

               with tempfile.TemporaryDirectory() as tmpdirname:
                     lowercase	:   Dict											= os.path.join(lowerCAmelCase,  'keras_model.h5'      )
                     model.save(lowerCAmelCase      )
                     if "T5" in main_layer_class.__name__:
                           lowercase	:   Tuple											= tf.keras.models.load_model(
                               lowerCAmelCase,  custom_objects={
                                   main_layer_class.__name__: main_layer_class,
                                   'TFSharedEmbeddings': TFSharedEmbeddings,
                               },  )
                     else:
                           lowercase	:   str											= tf.keras.models.load_model(
                               lowerCAmelCase,  custom_objects={main_layer_class.__name__: main_layer_class}      )
                     assert isinstance(lowerCAmelCase,  tf.keras.Model      )
                     model(lowerCAmelCase      )


   @slow
   def 							lowercase					(				self   :				Tuple      )     ->							List[str]:
         lowercase						,     lowercase	:   Any											= self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes[:2]:
               lowercase	:   Any											= model_class(lowerCAmelCase      )

               lowercase	:   List[str]											= copy.deepcopy(lowerCAmelCase      )

               if not self.is_encoder_decoder:
                     lowercase	:   List[Any]											= inputs['input_ids']
                     del inputs["input_ids"]
               else:
                     lowercase	:   Optional[Any]											= inputs['input_ids']
                     lowercase	:   Union[str, Any]											= inputs.get('decoder_input_ids',  lowerCAmelCase      )
                     del inputs["input_ids"]
                     inputs.pop('decoder_input_ids',  lowerCAmelCase      )

               if not self.is_encoder_decoder:
                     lowercase	:   Union[str, Any]											= model.get_input_embeddings()(lowerCAmelCase      )
               else:
                     lowercase	:   Dict											= model.get_input_embeddings()(lowerCAmelCase      )
                     lowercase	:   Any											= model.get_input_embeddings()(lowerCAmelCase      )

               lowercase	:   Union[str, Any]											= self._prepare_for_class(lowerCAmelCase,  lowerCAmelCase      )

               @tf.function
               def run_in_graph_mode():
                     return model(lowerCAmelCase      )

               lowercase	:   int											= run_in_graph_mode()
               self.assertIsNotNone(lowerCAmelCase      )


   def 							lowercase					(				self   :				str,  lowerCAmelCase   :				List[Any],  lowerCAmelCase   :				int      )     ->							Dict:
         # special tokens cannot be bad tokens
         lowercase	:   List[Any]											= []
         if model.config.bos_token_id is not None:
               special_tokens.append(model.config.bos_token_id      )
         if model.config.pad_token_id is not None:
               special_tokens.append(model.config.pad_token_id      )
         if model.config.eos_token_id is not None:
               special_tokens.append(model.config.eos_token_id      )

         # create random bad tokens that are not special tokens
         lowercase	:   List[Any]											= []
         while len(lowerCAmelCase      ) < num_bad_tokens:
               lowercase	:   str											= tf.squeeze(ids_tensor((1, 1),  self.model_tester.vocab_size      ),  0      ).numpy()[0]
               if token not in special_tokens:
                     bad_tokens.append(lowerCAmelCase      )
         return bad_tokens


   def 							lowercase					(				self   :				List[str],  lowerCAmelCase   :				Any      )     ->							str:
         for token_id in output_ids[0].numpy().tolist():
               self.assertGreaterEqual(lowerCAmelCase,  0      )
               self.assertLess(lowerCAmelCase,  self.model_tester.vocab_size      )






   def 							lowercase					(				self   :				str,  lowerCAmelCase   :				Any,  lowerCAmelCase   :				str      )     ->							Any:
         # for all bad word tokens
         for bad_word_ids in bad_words_ids:
               # for all slices in batch
               for generated_ids_slice in generated_ids:
                     # for all word idx
                     for i in range(len(lowerCAmelCase      ),  len(lowerCAmelCase      )      ):
                           # if tokens match
                           if generated_ids_slice[i - len(lowerCAmelCase      ) : i] == bad_word_ids:
                                 return True
         return False
