





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       = 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       = 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 				_lowerCamelCase :



      """simple docstring"""






      UpperCAmelCase_						:      int       =None
      UpperCAmelCase_						:      Union[str, Any]       =()
      UpperCAmelCase_						:      List[str]       =()
      UpperCAmelCase_						:      Optional[Any]       =True
      UpperCAmelCase_						:      Optional[Any]       =True
      UpperCAmelCase_						:      Any       =True
      UpperCAmelCase_						:      int       =False







      def 						UpperCAmelCase		( self				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase=False   )       ->   dict:






        '''simple docstring'''






        __snake_case   :				Any        =       copy.deepcopy(UpperCAmelCase   )

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

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







      @slow
      def 						UpperCAmelCase		( self   )       ->   Any:






        '''simple docstring'''






        __snake_case    ,   __snake_case   :				List[str]        =       self.model_tester.prepare_config_and_inputs_for_common()
        for model_class in self.all_model_classes[:2]:
          __snake_case   :				str        =       self._prepare_for_class(UpperCAmelCase				,						UpperCAmelCase   )
          __snake_case   :				List[str]        =       model_class(UpperCAmelCase   )

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

          __snake_case   :				int        =       run_in_graph_mode()
          self.assertIsNotNone(UpperCAmelCase   )







      @slow
      def 						UpperCAmelCase		( self   )       ->   int:






        '''simple docstring'''






        __snake_case    ,   __snake_case   :				List[str]        =       self.model_tester.prepare_config_and_inputs_for_common()
        for model_class in self.all_model_classes[:2]:
          __snake_case   :				str        =       self._prepare_for_class(UpperCAmelCase				,						UpperCAmelCase   )
          __snake_case   :				Union[str, Any]        =       model_class(UpperCAmelCase   )

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

          __snake_case   :				int        =       run_in_graph_mode()
          self.assertIsNotNone(UpperCAmelCase   )







      @slow
      def 						UpperCAmelCase		( self   )       ->   List[Any]:






        '''simple docstring'''






        __snake_case    ,   __snake_case   :				Optional[int]        =       self.model_tester.prepare_config_and_inputs_for_common()
        for model_class in self.all_model_classes[:2]:
          __snake_case   :				List[Any]        =       model_class(UpperCAmelCase   )
          if getattr(UpperCAmelCase				,						"hf_compute_loss"				,						UpperCAmelCase   ):
            # Test that model correctly compute the loss with kwargs
            __snake_case   :				List[Any]        =       self._prepare_for_class(inputs_dict.copy()				,						UpperCAmelCase				,						return_labels=UpperCAmelCase   )
            # Is there a better way to remove these decoder inputs?
            __snake_case   :				int        =       {
                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")
            }

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

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

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

            __snake_case   :				str        =       history.history["loss"][0]
            self.assertTrue(not isnan(UpperCAmelCase   )   )
            __snake_case   :				List[Any]        =       history.history["val_loss"][0]
            self.assertTrue(not isnan(UpperCAmelCase   )   )







      @slow
      def 						UpperCAmelCase		( self   )       ->   Any:






        '''simple docstring'''






        __snake_case    ,   __snake_case   :				Union[str, Any]        =       self.model_tester.prepare_config_and_inputs_for_common()
        __snake_case   :				Dict        =       True
        __snake_case   :				Any        =       True

        if hasattr(UpperCAmelCase				,						"use_cache"   ):
          __snake_case   :				Any        =       True

        __snake_case   :				int        =       getattr(self.model_tester				,						"encoder_seq_length"				,						self.model_tester.seq_length   )
        __snake_case   :				Tuple        =       getattr(self.model_tester				,						"key_length"				,						UpperCAmelCase   )

        for model_class in self.all_model_classes[:2]:
          __snake_case   :				Dict        =       self._prepare_for_class(UpperCAmelCase				,						UpperCAmelCase   )
          __snake_case   :				int        =       model_class(UpperCAmelCase   )
          model.build()
          __snake_case   :				str        =       len(model(UpperCAmelCase   )   )

          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:
              __snake_case   :				List[str]        =       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(UpperCAmelCase				,						saved_model=UpperCAmelCase   )
            __snake_case   :				str        =       os.path.join(UpperCAmelCase				,						"saved_model"				,						"1"   )
            __snake_case   :				Tuple        =       tf.keras.models.load_model(UpperCAmelCase   )
            __snake_case   :				Tuple        =       model(UpperCAmelCase   )

            if self.is_encoder_decoder:
              __snake_case   :				int        =       outputs["encoder_hidden_states"]
              __snake_case   :				str        =       outputs["encoder_attentions"]
            else:
              __snake_case   :				int        =       outputs["hidden_states"]
              __snake_case   :				Optional[Any]        =       outputs["attentions"]

            self.assertEqual(len(UpperCAmelCase   )				,						UpperCAmelCase   )

            __snake_case   :				int        =       getattr(
                self.model_tester				,						"expected_num_hidden_layers"				,						self.model_tester.num_hidden_layers + 1   )

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

            self.assertEqual(len(UpperCAmelCase   )				,						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 						UpperCAmelCase		( self   )       ->   Union[str, Any]:






        '''simple docstring'''






        tf.keras.mixed_precision.set_global_policy("mixed_float16"   )

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

            self.assertIsNotNone(UpperCAmelCase   )
        finally:
          tf.keras.mixed_precision.set_global_policy("float32"   )







      @slow
      def 						UpperCAmelCase		( self   )       ->   Union[str, Any]:






        '''simple docstring'''






        __snake_case    ,   __snake_case   :				Dict        =       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"]
        __snake_case   :				str        =       {
            module_member
            for model_class in self.all_model_classes
            for module in (import_module(model_class.__module__   ),)
            for module_member_name in dir(UpperCAmelCase   )
            if module_member_name.endswith("MainLayer"   )
            for module_member in (getattr(UpperCAmelCase				,						UpperCAmelCase   ),)
            if isinstance(UpperCAmelCase				,						UpperCAmelCase   )
            and tf.keras.layers.Layer in module_member.__bases__
            and getattr(UpperCAmelCase				,						"_keras_serializable"				,						UpperCAmelCase   )
        }

        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
            __snake_case   :				Tuple        =       TFSharedEmbeddings(self.model_tester.vocab_size				,						self.model_tester.hidden_size				,						name="shared"   )
            __snake_case   :				List[str]        =       False
            __snake_case   :				List[Any]        =       main_layer_class(UpperCAmelCase				,						embed_tokens=UpperCAmelCase   )
          else:
            __snake_case   :				Any        =       main_layer_class(UpperCAmelCase   )

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

          if hasattr(self.model_tester				,						"num_labels"   ):
            __snake_case   :				List[Any]        =       self.model_tester.num_labels
          else:
            __snake_case   :				Tuple        =       2

          __snake_case   :				List[str]        =       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   )

          __snake_case   :				Any        =       main_layer(UpperCAmelCase   )[0]
          __snake_case   :				str        =       tf.keras.layers.Dense(UpperCAmelCase				,						activation="softmax"				,						name="outputs"   )(UpperCAmelCase   )
          __snake_case   :				str        =       tf.keras.models.Model(inputs=UpperCAmelCase				,						outputs=[outputs]   )

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

          with tempfile.TemporaryDirectory() as tmpdirname:
            __snake_case   :				Any        =       os.path.join(UpperCAmelCase				,						"keras_model.h5"   )
            model.save(UpperCAmelCase   )
            if "T5" in main_layer_class.__name__:
              __snake_case   :				Optional[Any]        =       tf.keras.models.load_model(
                  UpperCAmelCase				,						custom_objects={
                      main_layer_class.__name__: main_layer_class,
                      "TFSharedEmbeddings": TFSharedEmbeddings,
                  }				,						)
            else:
              __snake_case   :				Dict        =       tf.keras.models.load_model(
                  UpperCAmelCase				,						custom_objects={main_layer_class.__name__: main_layer_class}   )
            assert isinstance(UpperCAmelCase				,						tf.keras.Model   )
            model(UpperCAmelCase   )







      @slow
      def 						UpperCAmelCase		( self   )       ->   int:






        '''simple docstring'''






        __snake_case    ,   __snake_case   :				int        =       self.model_tester.prepare_config_and_inputs_for_common()

        for model_class in self.all_model_classes[:2]:
          __snake_case   :				Dict        =       model_class(UpperCAmelCase   )

          __snake_case   :				str        =       copy.deepcopy(UpperCAmelCase   )

          if not self.is_encoder_decoder:
            __snake_case   :				int        =       inputs["input_ids"]
            del inputs["input_ids"]
          else:
            __snake_case   :				Dict        =       inputs["input_ids"]
            __snake_case   :				Any        =       inputs.get("decoder_input_ids"				,						UpperCAmelCase   )
            del inputs["input_ids"]
            inputs.pop("decoder_input_ids"				,						UpperCAmelCase   )

          if not self.is_encoder_decoder:
            __snake_case   :				List[str]        =       model.get_input_embeddings()(UpperCAmelCase   )
          else:
            __snake_case   :				Optional[int]        =       model.get_input_embeddings()(UpperCAmelCase   )
            __snake_case   :				str        =       model.get_input_embeddings()(UpperCAmelCase   )

          __snake_case   :				Dict        =       self._prepare_for_class(UpperCAmelCase				,						UpperCAmelCase   )

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

          __snake_case   :				int        =       run_in_graph_mode()
          self.assertIsNotNone(UpperCAmelCase   )







      def 						UpperCAmelCase		( self				,						UpperCAmelCase				,						UpperCAmelCase   )       ->   Any:






        '''simple docstring'''






        __snake_case   :				int        =       []
        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
        __snake_case   :				Optional[Any]        =       []
        while len(UpperCAmelCase   ) < num_bad_tokens:
          __snake_case   :				Any        =       tf.squeeze(ids_tensor((1, 1)				,						self.model_tester.vocab_size   )				,						0   ).numpy()[0]
          if token not in special_tokens:
            bad_tokens.append(UpperCAmelCase   )
        return bad_tokens







      def 						UpperCAmelCase		( self				,						UpperCAmelCase   )       ->   Any:






        '''simple docstring'''






        for token_id in output_ids[0].numpy().tolist():
          self.assertGreaterEqual(UpperCAmelCase				,						0   )
          self.assertLess(UpperCAmelCase				,						self.model_tester.vocab_size   )







      def 						UpperCAmelCase		( self				,						UpperCAmelCase				,						UpperCAmelCase   )       ->   List[str]:






        '''simple docstring'''






        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(UpperCAmelCase   )				,						len(UpperCAmelCase   )   ):
              # if tokens match
              if generated_ids_slice[i - len(UpperCAmelCase   ) : i] == bad_word_ids:
                return True
        return False








from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

_UpperCamelCase       = TypeVar('''T''')
_UpperCamelCase       = TypeVar('''U''')




class 				_lowerCamelCase (    Generic[T, U]    ):



      """simple docstring"""






      def __init__( self				,						UpperCAmelCase				,						UpperCAmelCase   )       ->   Dict:






        '''simple docstring'''






        __snake_case   :				Any        =       key
        __snake_case   :				Tuple        =       val
        __snake_case   :				int        =       0
        __snake_case   :				DoubleLinkedListNode[T, U] | None        =       None
        __snake_case   :				DoubleLinkedListNode[T, U] | None        =       None







      def __repr__( self   )       ->   str:






        '''simple docstring'''






        return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
            self.key				,						self.val				,						self.freq				,						self.next is not None				,						self.prev is not None   )




class 				_lowerCamelCase (    Generic[T, U]    ):



      """simple docstring"""






      def __init__( self   )       ->   None:






        '''simple docstring'''






        __snake_case   :				DoubleLinkedListNode[T, U]        =       DoubleLinkedListNode(UpperCAmelCase				,						UpperCAmelCase   )
        __snake_case   :				DoubleLinkedListNode[T, U]        =       DoubleLinkedListNode(UpperCAmelCase				,						UpperCAmelCase   )
        __snake_case    ,   __snake_case   :				Any        =       self.rear, self.head







      def __repr__( self   )       ->   str:






        '''simple docstring'''






        __snake_case   :				Union[str, Any]        =       ["DoubleLinkedList"]
        __snake_case   :				List[Any]        =       self.head
        while node.next is not None:
          rep.append(str(UpperCAmelCase   )   )
          __snake_case   :				List[Any]        =       node.next
        rep.append(str(self.rear   )   )
        return ",\n    ".join(UpperCAmelCase   )







      def 						UpperCAmelCase		( self				,						UpperCAmelCase   )       ->   None:






        '''simple docstring'''






        __snake_case   :				Dict        =       self.rear.prev

        # All nodes other than self.head are guaranteed to have non-None previous
        assert previous is not None

        __snake_case   :				int        =       node
        __snake_case   :				List[str]        =       previous
        __snake_case   :				Optional[int]        =       node
        __snake_case   :				int        =       self.rear
        node.freq += 1
        self._position_node(UpperCAmelCase   )







      def 						UpperCAmelCase		( self				,						UpperCAmelCase   )       ->   None:






        '''simple docstring'''






        while node.prev is not None and node.prev.freq > node.freq:
          # swap node with previous node
          __snake_case   :				List[Any]        =       node.prev

          __snake_case   :				Dict        =       previous_node.prev
          __snake_case   :				Union[str, Any]        =       node.prev
          __snake_case   :				Union[str, Any]        =       previous_node
          __snake_case   :				int        =       node







      def 						UpperCAmelCase		( self				,						UpperCAmelCase   )       ->   DoubleLinkedListNode[T, U] | None:






        '''simple docstring'''






        if node.prev is None or node.next is None:
          return None

        __snake_case   :				Optional[int]        =       node.next
        __snake_case   :				Optional[Any]        =       node.prev
        __snake_case   :				Optional[int]        =       None
        __snake_case   :				Any        =       None
        return node




class 				_lowerCamelCase (    Generic[T, U]    ):



      """simple docstring"""






      UpperCAmelCase_						:      dict[Callable[[T], U], LFUCache[T, U]]       ={}







      def __init__( self				,						UpperCAmelCase   )       ->   Tuple:






        '''simple docstring'''






        __snake_case   :				DoubleLinkedList[T, U]        =       DoubleLinkedList()
        __snake_case   :				str        =       capacity
        __snake_case   :				str        =       0
        __snake_case   :				Optional[int]        =       0
        __snake_case   :				Any        =       0
        __snake_case   :				dict[T, DoubleLinkedListNode[T, U]]        =       {}







      def __repr__( self   )       ->   str:






        '''simple docstring'''






        return (
            F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
            F"""capacity={self.capacity}, current_size={self.num_keys})"""
        )







      def __contains__( self				,						UpperCAmelCase   )       ->   bool:






        '''simple docstring'''






        return key in self.cache







      def 						UpperCAmelCase		( self				,						UpperCAmelCase   )       ->   U | None:






        '''simple docstring'''






        if key in self.cache:
          self.hits += 1
          __snake_case   :				DoubleLinkedListNode[T, U]        =       self.cache[key]
          __snake_case   :				Union[str, Any]        =       self.list.remove(self.cache[key]   )
          assert node == value_node

          # node is guaranteed not None because it is in self.cache
          assert node is not None
          self.list.add(UpperCAmelCase   )
          return node.val
        self.miss += 1
        return None







      def 						UpperCAmelCase		( self				,						UpperCAmelCase				,						UpperCAmelCase   )       ->   None:






        '''simple docstring'''






        if key not in self.cache:
          if self.num_keys >= self.capacity:
            # delete first node when over capacity
            __snake_case   :				Optional[Any]        =       self.list.head.next

            # guaranteed to have a non-None first node when num_keys > 0
            # explain to type checker via assertions
            assert first_node is not None
            assert first_node.key is not None
            assert self.list.remove(UpperCAmelCase   ) is not None
            # first_node guaranteed to be in list

            del self.cache[first_node.key]
            self.num_keys -= 1
          __snake_case   :				Union[str, Any]        =       DoubleLinkedListNode(UpperCAmelCase				,						UpperCAmelCase   )
          self.list.add(self.cache[key]   )
          self.num_keys += 1

        else:
          __snake_case   :				Union[str, Any]        =       self.list.remove(self.cache[key]   )
          assert node is not None  # node guaranteed to be in list
          __snake_case   :				Optional[Any]        =       value
          self.list.add(UpperCAmelCase   )







      @classmethod
      def 						UpperCAmelCase		( cls				,						UpperCAmelCase = 128   )       ->   Callable[[Callable[[T], U]], Callable[..., U]]:






        '''simple docstring'''






        def cache_decorator_inner(UpperCAmelCase   ) -> Callable[..., U]:
          def cache_decorator_wrapper(*UpperCAmelCase   ) -> U:
            if func not in cls.decorator_function_to_instance_map:
              __snake_case   :				str        =       LFUCache(UpperCAmelCase   )

            __snake_case   :				Dict        =       cls.decorator_function_to_instance_map[func].get(args[0]   )
            if result is None:
              __snake_case   :				Optional[int]        =       func(*UpperCAmelCase   )
              cls.decorator_function_to_instance_map[func].put(args[0]				,						UpperCAmelCase   )
            return result

          def cache_info() -> LFUCache[T, U]:
            return cls.decorator_function_to_instance_map[func]

          setattr(UpperCAmelCase				,						"cache_info"				,						UpperCAmelCase   )  # noqa: B010

          return cache_decorator_wrapper

        return cache_decorator_inner


if __name__ == "__main__":
     import doctest

     doctest.testmod()

