
import unittest

import numpy as np
import timeout_decorator  # noqa

from transformers import BlenderbotSmallConfig, is_flax_available
from transformers.testing_utils import require_flax, slow

from ...generation.test_flax_utils import FlaxGenerationTesterMixin
from ...test_modeling_flax_common import FlaxModelTesterMixin, ids_tensor


if is_flax_available():
    import os

    # The slow tests are often failing with OOM error on GPU
    # This makes JAX allocate exactly what is needed on demand, and deallocate memory that is no longer needed
    # but will be slower as stated here https://jax.readthedocs.io/en/latest/gpu_memory_allocation.html
    lowerCamelCase  ="platform"

    import jax
    import jax.numpy as jnp

    from transformers.models.blenderbot_small.modeling_flax_blenderbot_small import (
        FlaxBlenderbotSmallForConditionalGeneration,
        FlaxBlenderbotSmallModel,
        shift_tokens_right,
    )


def 				SCREAMING_SNAKE_CASE_   (      UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__=None			,		UpperCamelCase__=None			,		UpperCamelCase__=None			,		UpperCamelCase__=None			,		UpperCamelCase__=None			,		UpperCamelCase__=None			,		):
      if attention_mask is None:
            UpperCamelCase__     : List[Any]											=					np.where(input_ids != config.pad_token_id			,		1			,		0		)
      if decoder_attention_mask is None:
            UpperCamelCase__     : Any											=					np.where(decoder_input_ids != config.pad_token_id			,		1			,		0		)
      if head_mask is None:
            UpperCamelCase__     : Union[str, Any]											=					np.ones((config.encoder_layers, config.encoder_attention_heads)		)
      if decoder_head_mask is None:
            UpperCamelCase__     : List[str]											=					np.ones((config.decoder_layers, config.decoder_attention_heads)		)
      if cross_attn_head_mask is None:
            UpperCamelCase__     : Optional[Any]											=					np.ones((config.decoder_layers, config.decoder_attention_heads)		)
      return {
          "input_ids": input_ids,
          "decoder_input_ids": decoder_input_ids,
          "attention_mask": attention_mask,
          "decoder_attention_mask": attention_mask,
      }




class 					_lowerCamelCase			:





     """simple docstring"""







     def __init__(				self    ,    __SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE=1_3    ,    __SCREAMING_SNAKE_CASE=7    ,    __SCREAMING_SNAKE_CASE=True    ,    __SCREAMING_SNAKE_CASE=False    ,    __SCREAMING_SNAKE_CASE=9_9    ,    __SCREAMING_SNAKE_CASE=1_6    ,    __SCREAMING_SNAKE_CASE=2    ,    __SCREAMING_SNAKE_CASE=4    ,    __SCREAMING_SNAKE_CASE=4    ,    __SCREAMING_SNAKE_CASE="gelu"    ,    __SCREAMING_SNAKE_CASE=0.1    ,    __SCREAMING_SNAKE_CASE=0.1    ,    __SCREAMING_SNAKE_CASE=3_2    ,    __SCREAMING_SNAKE_CASE=2    ,    __SCREAMING_SNAKE_CASE=1    ,    __SCREAMING_SNAKE_CASE=0    ,    __SCREAMING_SNAKE_CASE=0.02    ,    )	-> int:




           """simple docstring"""







           UpperCamelCase__     : Tuple											=					parent
           UpperCamelCase__     : List[Any]											=					batch_size
           UpperCamelCase__     : str											=					seq_length
           UpperCamelCase__     : Optional[Any]											=					is_training
           UpperCamelCase__     : List[str]											=					use_labels
           UpperCamelCase__     : Optional[int]											=					vocab_size
           UpperCamelCase__     : List[Any]											=					hidden_size
           UpperCamelCase__     : Tuple											=					num_hidden_layers
           UpperCamelCase__     : Optional[Any]											=					num_attention_heads
           UpperCamelCase__     : Tuple											=					intermediate_size
           UpperCamelCase__     : List[Any]											=					hidden_act
           UpperCamelCase__     : Dict											=					hidden_dropout_prob
           UpperCamelCase__     : Union[str, Any]											=					attention_probs_dropout_prob
           UpperCamelCase__     : Optional[Any]											=					max_position_embeddings
           UpperCamelCase__     : Tuple											=					eos_token_id
           UpperCamelCase__     : Union[str, Any]											=					pad_token_id
           UpperCamelCase__     : List[str]											=					bos_token_id
           UpperCamelCase__     : List[str]											=					initializer_range






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> List[str]:




           """simple docstring"""







           UpperCamelCase__     : Union[str, Any]											=					np.clip(ids_tensor([self.batch_size, self.seq_length - 1]    ,    self.vocab_size	)    ,    3    ,    self.vocab_size	)
           UpperCamelCase__     : str											=					np.concatenate((input_ids, 2 * np.ones((self.batch_size, 1)    ,    dtype=np.intaa	))    ,    -1	)

           UpperCamelCase__     : List[Any]											=					shift_tokens_right(__SCREAMING_SNAKE_CASE    ,    1    ,    2	)

           UpperCamelCase__     : str											=					BlenderbotSmallConfig(
               vocab_size=self.vocab_size    ,    d_model=self.hidden_size    ,    encoder_layers=self.num_hidden_layers    ,    decoder_layers=self.num_hidden_layers    ,    encoder_attention_heads=self.num_attention_heads    ,    decoder_attention_heads=self.num_attention_heads    ,    encoder_ffn_dim=self.intermediate_size    ,    decoder_ffn_dim=self.intermediate_size    ,    dropout=self.hidden_dropout_prob    ,    attention_dropout=self.attention_probs_dropout_prob    ,    max_position_embeddings=self.max_position_embeddings    ,    eos_token_id=self.eos_token_id    ,    bos_token_id=self.bos_token_id    ,    pad_token_id=self.pad_token_id    ,    initializer_range=self.initializer_range    ,    use_cache=__SCREAMING_SNAKE_CASE    ,    )
           UpperCamelCase__     : Optional[Any]											=					prepare_blenderbot_inputs_dict(__SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	)
           return config, inputs_dict






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> Union[str, Any]:




           """simple docstring"""







           UpperCamelCase__					,UpperCamelCase__     : List[Any]											=					self.prepare_config_and_inputs()
           return config, inputs_dict






     def  __SCREAMING_SNAKE_CASE      (				self    ,    __SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	)	-> str:




           """simple docstring"""







           UpperCamelCase__     : Optional[Any]											=					2_0
           UpperCamelCase__     : int											=					model_class_name(__SCREAMING_SNAKE_CASE	)

           UpperCamelCase__     : List[str]											=					model.encode(inputs_dict['''input_ids''']	)

           UpperCamelCase__					,UpperCamelCase__     : Optional[Any]											=					(
               inputs_dict['''decoder_input_ids'''],
               inputs_dict['''decoder_attention_mask'''],
           )

           UpperCamelCase__     : Any											=					model.init_cache(decoder_input_ids.shape[0]    ,    __SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	)
           UpperCamelCase__     : Union[str, Any]											=					jnp.ones((decoder_input_ids.shape[0], max_decoder_length)    ,    dtype='''i4'''	)

           UpperCamelCase__     : Tuple											=					jnp.broadcast_to(
               jnp.arange(decoder_input_ids.shape[-1] - 1	)[None, :]    ,    (decoder_input_ids.shape[0], decoder_input_ids.shape[-1] - 1)    ,    )
           UpperCamelCase__     : List[Any]											=					model.decode(
               decoder_input_ids[:, :-1]    ,    __SCREAMING_SNAKE_CASE    ,    decoder_attention_mask=__SCREAMING_SNAKE_CASE    ,    past_key_values=__SCREAMING_SNAKE_CASE    ,    decoder_position_ids=__SCREAMING_SNAKE_CASE    ,    )

           UpperCamelCase__     : Union[str, Any]											=					jnp.array(decoder_input_ids.shape[0] * [[decoder_input_ids.shape[-1] - 1]]    ,    dtype='''i4'''	)
           UpperCamelCase__     : Dict											=					model.decode(
               decoder_input_ids[:, -1:]    ,    __SCREAMING_SNAKE_CASE    ,    decoder_attention_mask=__SCREAMING_SNAKE_CASE    ,    past_key_values=outputs_cache.past_key_values    ,    decoder_position_ids=__SCREAMING_SNAKE_CASE    ,    )

           UpperCamelCase__     : int											=					model.decode(__SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	)

           UpperCamelCase__     : Dict											=					np.max(np.abs((outputs_cache_next[0][:, -1, :5] - outputs[0][:, -1, :5])	)	)
           self.parent.assertTrue(diff < 1e-3    ,    msg=F'''Max diff is {diff}'''	)






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




           """simple docstring"""







           UpperCamelCase__     : List[Any]											=					2_0
           UpperCamelCase__     : str											=					model_class_name(__SCREAMING_SNAKE_CASE	)

           UpperCamelCase__     : Tuple											=					model.encode(inputs_dict['''input_ids''']	)

           UpperCamelCase__					,UpperCamelCase__     : Union[str, Any]											=					(
               inputs_dict['''decoder_input_ids'''],
               inputs_dict['''decoder_attention_mask'''],
           )

           UpperCamelCase__     : Union[str, Any]											=					jnp.concatenate(
               [
                   decoder_attention_mask,
                   jnp.zeros((decoder_attention_mask.shape[0], max_decoder_length - decoder_attention_mask.shape[1])	),
               ]    ,    axis=-1    ,    )

           UpperCamelCase__     : int											=					model.init_cache(decoder_input_ids.shape[0]    ,    __SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	)
           UpperCamelCase__     : str											=					jnp.broadcast_to(
               jnp.arange(decoder_input_ids.shape[-1] - 1	)[None, :]    ,    (decoder_input_ids.shape[0], decoder_input_ids.shape[-1] - 1)    ,    )

           UpperCamelCase__     : Tuple											=					model.decode(
               decoder_input_ids[:, :-1]    ,    __SCREAMING_SNAKE_CASE    ,    decoder_attention_mask=__SCREAMING_SNAKE_CASE    ,    past_key_values=__SCREAMING_SNAKE_CASE    ,    decoder_position_ids=__SCREAMING_SNAKE_CASE    ,    )
           UpperCamelCase__     : List[str]											=					jnp.array(decoder_input_ids.shape[0] * [[decoder_input_ids.shape[-1] - 1]]    ,    dtype='''i4'''	)
           UpperCamelCase__     : Any											=					model.decode(
               decoder_input_ids[:, -1:]    ,    __SCREAMING_SNAKE_CASE    ,    past_key_values=outputs_cache.past_key_values    ,    decoder_attention_mask=__SCREAMING_SNAKE_CASE    ,    decoder_position_ids=__SCREAMING_SNAKE_CASE    ,    )

           UpperCamelCase__     : int											=					model.decode(__SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE    ,    decoder_attention_mask=__SCREAMING_SNAKE_CASE	)

           UpperCamelCase__     : Union[str, Any]											=					np.max(np.abs((outputs_cache_next[0][:, -1, :5] - outputs[0][:, -1, :5])	)	)
           self.parent.assertTrue(diff < 1e-3    ,    msg=F'''Max diff is {diff}'''	)




@require_flax
class 					_lowerCamelCase			(   unittest.TestCase			):





     """simple docstring"""







     SCREAMING_SNAKE_CASE_		 =	99






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> List[str]:




           """simple docstring"""







           UpperCamelCase__     : int											=					np.array(
               [
                   [7_1, 8_2, 1_8, 3_3, 4_6, 9_1, 2],
                   [6_8, 3_4, 2_6, 5_8, 3_0, 8_2, 2],
                   [5, 9_7, 1_7, 3_9, 9_4, 4_0, 2],
                   [7_6, 8_3, 9_4, 2_5, 7_0, 7_8, 2],
                   [8_7, 5_9, 4_1, 3_5, 4_8, 6_6, 2],
                   [5_5, 1_3, 1_6, 5_8, 5, 2, 1],  # note padding
                   [6_4, 2_7, 3_1, 5_1, 1_2, 7_5, 2],
                   [5_2, 6_4, 8_6, 1_7, 8_3, 3_9, 2],
                   [4_8, 6_1, 9, 2_4, 7_1, 8_2, 2],
                   [2_6, 1, 6_0, 4_8, 2_2, 1_3, 2],
                   [2_1, 5, 6_2, 2_8, 1_4, 7_6, 2],
                   [4_5, 9_8, 3_7, 8_6, 5_9, 4_8, 2],
                   [7_0, 7_0, 5_0, 9, 2_8, 0, 2],
               ]    ,    dtype=np.intaa    ,    )

           UpperCamelCase__     : List[str]											=					input_ids.shape[0]
           UpperCamelCase__     : Any											=					BlenderbotSmallConfig(
               vocab_size=self.vocab_size    ,    d_model=2_4    ,    encoder_layers=2    ,    decoder_layers=2    ,    encoder_attention_heads=2    ,    decoder_attention_heads=2    ,    encoder_ffn_dim=3_2    ,    decoder_ffn_dim=3_2    ,    max_position_embeddings=4_8    ,    eos_token_id=2    ,    pad_token_id=1    ,    bos_token_id=0    ,    )
           return config, input_ids, batch_size






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> Dict:




           """simple docstring"""







           UpperCamelCase__					,UpperCamelCase__					,UpperCamelCase__     : Optional[int]											=					self._get_config_and_data()
           UpperCamelCase__     : Dict											=					FlaxBlenderbotSmallForConditionalGeneration(__SCREAMING_SNAKE_CASE	)
           UpperCamelCase__     : Union[str, Any]											=					lm_model(input_ids=__SCREAMING_SNAKE_CASE	)
           UpperCamelCase__     : Optional[Any]											=					(batch_size, input_ids.shape[1], config.vocab_size)
           self.assertEqual(outputs['''logits'''].shape    ,    __SCREAMING_SNAKE_CASE	)






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> List[str]:




           """simple docstring"""







           UpperCamelCase__     : int											=					BlenderbotSmallConfig(
               vocab_size=self.vocab_size    ,    d_model=1_4    ,    encoder_layers=2    ,    decoder_layers=2    ,    encoder_attention_heads=2    ,    decoder_attention_heads=2    ,    encoder_ffn_dim=8    ,    decoder_ffn_dim=8    ,    max_position_embeddings=4_8    ,    )
           UpperCamelCase__     : int											=					FlaxBlenderbotSmallForConditionalGeneration(__SCREAMING_SNAKE_CASE	)
           UpperCamelCase__     : Any											=					np.array([[7_1, 8_2, 1_8, 3_3, 4_6, 9_1, 2], [6_8, 3_4, 2_6, 5_8, 3_0, 2, 1]]    ,    dtype=np.intaa	)
           UpperCamelCase__     : Tuple											=					np.array([[8_2, 7_1, 8_2, 1_8, 2], [5_8, 6_8, 2, 1, 1]]    ,    dtype=np.intaa	)
           UpperCamelCase__     : Tuple											=					lm_model(input_ids=__SCREAMING_SNAKE_CASE    ,    decoder_input_ids=__SCREAMING_SNAKE_CASE	)
           UpperCamelCase__     : List[str]											=					(*summary.shape, config.vocab_size)
           self.assertEqual(outputs['''logits'''].shape    ,    __SCREAMING_SNAKE_CASE	)






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> Optional[int]:




           """simple docstring"""







           UpperCamelCase__     : Any											=					np.array([[7_1, 8_2, 1_8, 3_3, 2, 1, 1], [6_8, 3_4, 2_6, 5_8, 3_0, 8_2, 2]]    ,    dtype=np.intaa	)
           UpperCamelCase__     : str											=					shift_tokens_right(__SCREAMING_SNAKE_CASE    ,    1    ,    2	)
           UpperCamelCase__     : List[str]											=					np.equal(__SCREAMING_SNAKE_CASE    ,    1	).astype(np.floataa	).sum()
           UpperCamelCase__     : Union[str, Any]											=					np.equal(__SCREAMING_SNAKE_CASE    ,    1	).astype(np.floataa	).sum()
           self.assertEqual(shifted.shape    ,    input_ids.shape	)
           self.assertEqual(__SCREAMING_SNAKE_CASE    ,    n_pad_before - 1	)
           self.assertTrue(np.equal(shifted[:, 0]    ,    2	).all()	)




@require_flax
class 					_lowerCamelCase			(   UpperCamelCase_						,				unittest.TestCase						,				UpperCamelCase_			):





     """simple docstring"""







     SCREAMING_SNAKE_CASE_		 =	True
     SCREAMING_SNAKE_CASE_		 =	(
         (
             FlaxBlenderbotSmallModel,
             FlaxBlenderbotSmallForConditionalGeneration,
         )
         if is_flax_available()
         else ()
     )
     SCREAMING_SNAKE_CASE_		 =	(FlaxBlenderbotSmallForConditionalGeneration,) if is_flax_available() else ()






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> int:




           """simple docstring"""







           UpperCamelCase__     : Any											=					FlaxBlenderbotSmallModelTester(self	)






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> str:




           """simple docstring"""







           UpperCamelCase__					,UpperCamelCase__     : Optional[Any]											=					self.model_tester.prepare_config_and_inputs()
           for model_class in self.all_model_classes:
                 self.model_tester.check_use_cache_forward(__SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	)






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> List[Any]:




           """simple docstring"""







           UpperCamelCase__					,UpperCamelCase__     : Dict											=					self.model_tester.prepare_config_and_inputs()
           for model_class in self.all_model_classes:
                 self.model_tester.check_use_cache_forward_with_attn_mask(__SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	)






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> List[str]:




           """simple docstring"""







           UpperCamelCase__					,UpperCamelCase__     : Union[str, Any]											=					self.model_tester.prepare_config_and_inputs_for_common()

           for model_class in self.all_model_classes:
                 with self.subTest(model_class.__name__	):
                       UpperCamelCase__     : List[Any]											=					self._prepare_for_class(__SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	)
                       UpperCamelCase__     : str											=					model_class(__SCREAMING_SNAKE_CASE	)

                       @jax.jit
                       def encode_jitted(__SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE=None    ,    **__SCREAMING_SNAKE_CASE	):
                             return model.encode(input_ids=__SCREAMING_SNAKE_CASE    ,    attention_mask=__SCREAMING_SNAKE_CASE	)

                       with self.subTest('''JIT Enabled'''	):
                             UpperCamelCase__     : Optional[Any]											=					encode_jitted(**__SCREAMING_SNAKE_CASE	).to_tuple()

                       with self.subTest('''JIT Disabled'''	):
                             with jax.disable_jit():
                                   UpperCamelCase__     : Any											=					encode_jitted(**__SCREAMING_SNAKE_CASE	).to_tuple()

                       self.assertEqual(len(__SCREAMING_SNAKE_CASE	)    ,    len(__SCREAMING_SNAKE_CASE	)	)
                       for jitted_output, output in zip(__SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	):
                             self.assertEqual(jitted_output.shape    ,    output.shape	)






     def  __SCREAMING_SNAKE_CASE      (				self	)	-> Optional[Any]:




           """simple docstring"""







           UpperCamelCase__					,UpperCamelCase__     : Any											=					self.model_tester.prepare_config_and_inputs_for_common()

           for model_class in self.all_model_classes:
                 with self.subTest(model_class.__name__	):
                       UpperCamelCase__     : List[str]											=					model_class(__SCREAMING_SNAKE_CASE	)
                       UpperCamelCase__     : List[str]											=					model.encode(inputs_dict['''input_ids''']    ,    inputs_dict['''attention_mask''']	)

                       UpperCamelCase__     : Any											=					{
                           '''decoder_input_ids''': inputs_dict['''decoder_input_ids'''],
                           '''decoder_attention_mask''': inputs_dict['''decoder_attention_mask'''],
                           '''encoder_outputs''': encoder_outputs,
                       }

                       @jax.jit
                       def decode_jitted(__SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	):
                             return model.decode(
                                 decoder_input_ids=__SCREAMING_SNAKE_CASE    ,    decoder_attention_mask=__SCREAMING_SNAKE_CASE    ,    encoder_outputs=__SCREAMING_SNAKE_CASE    ,    )

                       with self.subTest('''JIT Enabled'''	):
                             UpperCamelCase__     : List[Any]											=					decode_jitted(**__SCREAMING_SNAKE_CASE	).to_tuple()

                       with self.subTest('''JIT Disabled'''	):
                             with jax.disable_jit():
                                   UpperCamelCase__     : List[Any]											=					decode_jitted(**__SCREAMING_SNAKE_CASE	).to_tuple()

                       self.assertEqual(len(__SCREAMING_SNAKE_CASE	)    ,    len(__SCREAMING_SNAKE_CASE	)	)
                       for jitted_output, output in zip(__SCREAMING_SNAKE_CASE    ,    __SCREAMING_SNAKE_CASE	):
                             self.assertEqual(jitted_output.shape    ,    output.shape	)






     @slow
     def  __SCREAMING_SNAKE_CASE      (				self	)	-> List[str]:




           """simple docstring"""







           for model_class_name in self.all_model_classes:
                 UpperCamelCase__     : Optional[int]											=					model_class_name.from_pretrained('''facebook/blenderbot_small-90M'''	)
                 # FlaxBlenderbotForSequenceClassification expects eos token in input_ids
                 UpperCamelCase__     : List[str]											=					np.ones((1, 1)	) * model.config.eos_token_id
                 UpperCamelCase__     : Optional[Any]											=					model(__SCREAMING_SNAKE_CASE	)
                 self.assertIsNotNone(__SCREAMING_SNAKE_CASE	)




def 				SCREAMING_SNAKE_CASE_   (      UpperCamelCase__			,		UpperCamelCase__		):

      def get_matched_characters(UpperCamelCase__			,		UpperCamelCase__		) -> str:
            UpperCamelCase__     : Union[str, Any]											=					[]
            UpperCamelCase__     : Union[str, Any]											=					min(len(_stra		)			,		len(_stra		)		) // 2
            for i, l in enumerate(_stra		):
                  UpperCamelCase__     : Optional[int]											=					int(max(0			,		i - limit		)		)
                  UpperCamelCase__     : List[str]											=					int(min(i + limit + 1			,		len(_stra		)		)		)
                  if l in _stra[left:right]:
                        matched.append(UpperCamelCase__		)
                        UpperCamelCase__     : List[str]											=					f'''{_stra[0:_stra.index(UpperCamelCase__		)]} {_stra[_stra.index(UpperCamelCase__		) + 1:]}'''

            return "".join(UpperCamelCase__		)

      # matching characters
      UpperCamelCase__     : Any											=					get_matched_characters(UpperCamelCase__			,		UpperCamelCase__		)
      UpperCamelCase__     : Union[str, Any]											=					get_matched_characters(UpperCamelCase__			,		UpperCamelCase__		)
      UpperCamelCase__     : List[Any]											=					len(UpperCamelCase__		)

      # transposition
      UpperCamelCase__     : str											=					(
          len([(ca, ca) for ca, ca in zip(UpperCamelCase__			,		UpperCamelCase__		) if ca != ca]		) // 2
      )

      if not match_count:
            UpperCamelCase__     : Union[str, Any]											=					0.0
      else:
            UpperCamelCase__     : Optional[int]											=					(
                1
                / 3
                * (
                    match_count / len(UpperCamelCase__		)
                    + match_count / len(UpperCamelCase__		)
                    + (match_count - transpositions) / match_count
                )
            )

      # common prefix up to 4 characters
      UpperCamelCase__     : Dict											=					0
      for ca, ca in zip(stra[:4]			,		stra[:4]		):
            if ca == ca:
                  prefix_len += 1
            else:
                  break

      return jaro + 0.1 * prefix_len * (1 - jaro)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    print(jaro_winkler("hello", "world"))


