






import os
from pickle import UnpicklingError
from typing import Dict, Tuple

import jax
import jax.numpy as jnp
import numpy as np
from flax.serialization import from_bytes
from flax.traverse_util import flatten_dict, unflatten_dict

import transformers

from .utils import logging


__UpperCamelCase					:		Union[str, Any]	  =						logging.get_logger(__name__)
def      a_ (      _A      ,   _A      ,   _A      ,   _A=False  )			->			str:







				"""simple docstring"""
				try:
								import torch  # noqa: F401
				except ImportError:
								logger.error(
								    'Loading a PyTorch model in Flax, requires both PyTorch and Flax to be installed. Please see'
								    ' https://pytorch.org/ and https://flax.readthedocs.io/en/latest/installation.html for installation'
								    ' instructions.'  )
								raise

				if not is_sharded:
								snake_case__									=     os.path.abspath(_A  )
								logger.info(f'''Loading PyTorch weights from {pt_path}'''  )

								snake_case__									=     torch.load(_A      ,   map_location='cpu'  )
								logger.info(f'''PyTorch checkpoint contains {sum(t.numel() for t in pt_state_dict.values()  ):,} parameters.'''  )

								snake_case__									=     convert_pytorch_state_dict_to_flax(_A      ,   _A  )
				else:
								# model is sharded and pytorch_checkpoint_path already contains the list of .pt shard files
								snake_case__									=     convert_pytorch_sharded_state_dict_to_flax(_A      ,   _A  )
				return flax_state_dict
def      a_ (      _A      ,   _A      ,   _A      ,   _A      ,   )			->			(Tuple[str], np.ndarray):







				"""simple docstring"""

				def is_key_or_prefix_key_in_dict(_A  ) -> bool:
								return len(set(_A  ) & {key, (model_prefix,) + key}  ) > 0

				# layer norm
				snake_case__									=     pt_tuple_key[:-1] + ('scale',)
				if pt_tuple_key[-1] in ["weight", "gamma"] and is_key_or_prefix_key_in_dict(_A  ):
								return renamed_pt_tuple_key, pt_tensor

				# batch norm layer mean
				snake_case__									=     pt_tuple_key[:-1] + ('mean',)
				if pt_tuple_key[-1] == "running_mean" and not is_key_or_prefix_key_in_dict(_A  ):
								return renamed_pt_tuple_key, pt_tensor

				# batch norm layer var
				snake_case__									=     pt_tuple_key[:-1] + ('var',)
				if pt_tuple_key[-1] == "running_var" and not is_key_or_prefix_key_in_dict(_A  ):
								return renamed_pt_tuple_key, pt_tensor

				# embedding
				snake_case__									=     pt_tuple_key[:-1] + ('embedding',)
				if pt_tuple_key[-1] == "weight" and is_key_or_prefix_key_in_dict(_A  ):
								return renamed_pt_tuple_key, pt_tensor

				# conv layer
				snake_case__									=     pt_tuple_key[:-1] + ('kernel',)
				if pt_tuple_key[-1] == "weight" and pt_tensor.ndim == 4 and not is_key_or_prefix_key_in_dict(_A  ):
								snake_case__									=     pt_tensor.transpose(2      ,   3      ,   1      ,   0  )
								return renamed_pt_tuple_key, pt_tensor

				# linear layer
				snake_case__									=     pt_tuple_key[:-1] + ('kernel',)
				if pt_tuple_key[-1] == "weight" and not is_key_or_prefix_key_in_dict(_A  ):
								snake_case__									=     pt_tensor.T
								return renamed_pt_tuple_key, pt_tensor

				# old PyTorch layer norm weight
				snake_case__									=     pt_tuple_key[:-1] + ('weight',)
				if pt_tuple_key[-1] == "gamma":
								return renamed_pt_tuple_key, pt_tensor

				# old PyTorch layer norm bias
				snake_case__									=     pt_tuple_key[:-1] + ('bias',)
				if pt_tuple_key[-1] == "beta":
								return renamed_pt_tuple_key, pt_tensor

				# New `weight_norm` from https://github.com/huggingface/transformers/pull/24030
				snake_case__									=     None
				if pt_tuple_key[-3::2] == ("parametrizations", "original0"):
								snake_case__									=     pt_tuple_key[-2] + '_g'
				elif pt_tuple_key[-3::2] == ("parametrizations", "original1"):
								snake_case__									=     pt_tuple_key[-2] + '_v'
				if name is not None:
								snake_case__									=     pt_tuple_key[:-3] + (name,)
								return renamed_pt_tuple_key, pt_tensor

				return pt_tuple_key, pt_tensor
def      a_ (      _A      ,   _A  )			->			Dict:







				"""simple docstring"""
				snake_case__									=     {k: v.numpy() for k, v in pt_state_dict.items()}

				snake_case__									=     flax_model.base_model_prefix

				# use params dict if the model contains batch norm layers
				if "params" in flax_model.params:
								snake_case__									=     flax_model.params['params']
				else:
								snake_case__									=     flax_model.params
				snake_case__									=     flatten_dict(_A  )

				# add batch_stats keys,values to dict
				if "batch_stats" in flax_model.params:
								snake_case__									=     flatten_dict(flax_model.params['batch_stats']  )
								random_flax_state_dict.update(_A  )

				snake_case__									=     {}

				snake_case__									=     (model_prefix not in flax_model_params) and (
				    model_prefix in {k.split('.'  )[0] for k in pt_state_dict.keys()}
				)
				snake_case__									=     (model_prefix in flax_model_params) and (
				    model_prefix not in {k.split('.'  )[0] for k in pt_state_dict.keys()}
				)

				# Need to change some parameters name to match Flax names
				for pt_key, pt_tensor in pt_state_dict.items():
								snake_case__									=     tuple(pt_key.split('.'  )  )

								# remove base model prefix if necessary
								snake_case__									=     pt_tuple_key[0] == model_prefix
								if load_model_with_head_into_base_model and has_base_model_prefix:
												snake_case__									=     pt_tuple_key[1:]

								# Correctly rename weight parameters
								snake_case__							,						snake_case__									=     rename_key_and_reshape_tensor(
								    _A      ,   _A      ,   _A      ,   _A  )

								# add model prefix if necessary
								snake_case__									=     (model_prefix,) + flax_key in random_flax_state_dict
								if load_base_model_into_model_with_head and require_base_model_prefix:
												snake_case__									=     (model_prefix,) + flax_key

								if flax_key in random_flax_state_dict:
												if flax_tensor.shape != random_flax_state_dict[flax_key].shape:
																raise ValueError(
																    f'''PyTorch checkpoint seems to be incorrect. Weight {pt_key} was expected to be of shape '''
																    f'''{random_flax_state_dict[flax_key].shape}, but is {flax_tensor.shape}.'''  )

        # add batch stats if the model contains batchnorm layers
								if "batch_stats" in flax_model.params:
												if "mean" in flax_key[-1] or "var" in flax_key[-1]:
																snake_case__									=     jnp.asarray(_A  )
																continue
												# remove num_batches_tracked key
												if "num_batches_tracked" in flax_key[-1]:
																flax_state_dict.pop(_A      ,   _A  )
																continue

												# also add unexpected weight so that warning is thrown
												snake_case__									=     jnp.asarray(_A  )

								else:
												# also add unexpected weight so that warning is thrown
												snake_case__									=     jnp.asarray(_A  )

				return unflatten_dict(_A  )
def      a_ (      _A      ,   _A  )			->			int:







				"""simple docstring"""
				import torch

				# Load the index
				snake_case__									=     {}
				for shard_file in shard_filenames:
								# load using msgpack utils
								snake_case__									=     torch.load(_A  )
								snake_case__									=     {k: v.numpy() for k, v in pt_state_dict.items()}

								snake_case__									=     flax_model.base_model_prefix

								# use params dict if the model contains batch norm layers and then add batch_stats keys,values to dict
								if "batch_stats" in flax_model.params:
												snake_case__									=     flax_model.params['params']

												snake_case__									=     flatten_dict(_A  )
												random_flax_state_dict.update(flatten_dict(flax_model.params['batch_stats']  )  )
								else:
												snake_case__									=     flax_model.params
												snake_case__									=     flatten_dict(_A  )

								snake_case__									=     (model_prefix not in flax_model_params) and (
								    model_prefix in {k.split('.'  )[0] for k in pt_state_dict.keys()}
								)
								snake_case__									=     (model_prefix in flax_model_params) and (
								    model_prefix not in {k.split('.'  )[0] for k in pt_state_dict.keys()}
								)
								# Need to change some parameters name to match Flax names
								for pt_key, pt_tensor in pt_state_dict.items():
												snake_case__									=     tuple(pt_key.split('.'  )  )

												# remove base model prefix if necessary
												snake_case__									=     pt_tuple_key[0] == model_prefix
												if load_model_with_head_into_base_model and has_base_model_prefix:
																snake_case__									=     pt_tuple_key[1:]

												# Correctly rename weight parameters
												snake_case__							,						snake_case__									=     rename_key_and_reshape_tensor(
												    _A      ,   _A      ,   _A      ,   _A  )
												# add model prefix if necessary
												snake_case__									=     (model_prefix,) + flax_key in random_flax_state_dict
												if load_base_model_into_model_with_head and require_base_model_prefix:
																snake_case__									=     (model_prefix,) + flax_key

												if flax_key in random_flax_state_dict:
																if flax_tensor.shape != random_flax_state_dict[flax_key].shape:
																				raise ValueError(
																				    f'''PyTorch checkpoint seems to be incorrect. Weight {pt_key} was expected to be of shape '''
																				    f'''{random_flax_state_dict[flax_key].shape}, but is {flax_tensor.shape}.'''  )

            # add batch stats if the model contains batchnorm layers
												if "batch_stats" in flax_model.params:
																if "mean" in flax_key[-1]:
																				snake_case__									=     jnp.asarray(_A  )
																				continue
																if "var" in flax_key[-1]:
																				snake_case__									=     jnp.asarray(_A  )
																				continue
																# remove num_batches_tracked key
																if "num_batches_tracked" in flax_key[-1]:
																				flax_state_dict.pop(_A      ,   _A  )
																				continue

																# also add unexpected weight so that warning is thrown
																snake_case__									=     jnp.asarray(_A  )

												else:
																# also add unexpected weight so that warning is thrown
																snake_case__									=     jnp.asarray(_A  )
				return unflatten_dict(_A  )
def      a_ (      _A      ,   _A  )			->			Dict:







				"""simple docstring"""
				snake_case__									=     os.path.abspath(_A  )
				logger.info(f'''Loading Flax weights from {flax_checkpoint_path}'''  )

				# import correct flax class
				snake_case__									=     getattr(_A      ,   'Flax' + model.__class__.__name__  )

				# load flax weight dict
				with open(_A      ,   'rb'  ) as state_f:
								try:
												snake_case__									=     from_bytes(_A      ,   state_f.read()  )
								except UnpicklingError:
												raise EnvironmentError(f'''Unable to convert {flax_checkpoint_path} to Flax deserializable object. '''  )

				return load_flax_weights_in_pytorch_model(_A      ,   _A  )


def      a_ (      _A      ,   _A  )			->			List[str]:







				"""simple docstring"""

				try:
								import torch  # noqa: F401
				except ImportError:
								logger.error(
								    'Loading a Flax weights in PyTorch, requires both PyTorch and Flax to be installed. Please see'
								    ' https://pytorch.org/ and https://flax.readthedocs.io/en/latest/installation.html for installation'
								    ' instructions.'  )
								raise

				# check if we have bf16 weights
				snake_case__									=     flatten_dict(jax.tree_util.tree_map(lambda _A  : x.dtype == jnp.bfloataa      ,   _A  )  ).values()
				if any(_A  ):
								# convert all weights to fp32 if the are bf16 since torch.from_numpy can-not handle bf16
								# and bf16 is not fully supported in PT yet.
								logger.warning(
								    'Found ``bfloat16`` weights in Flax model. Casting all ``bfloat16`` weights to ``float32`` '
								    'before loading those in PyTorch model.'  )
								snake_case__									=     jax.tree_util.tree_map(
								    lambda _A  : params.astype(np.floataa  ) if params.dtype == jnp.bfloataa else params      ,   _A  )

				snake_case__									=     flatten_dict(_A  )
				snake_case__									=     pt_model.state_dict()

				snake_case__									=     (pt_model.base_model_prefix in flax_state) and (
				    pt_model.base_model_prefix not in {k.split('.'  )[0] for k in pt_model_dict.keys()}
				)
				snake_case__									=     (pt_model.base_model_prefix not in flax_state) and (
				    pt_model.base_model_prefix in {k.split('.'  )[0] for k in pt_model_dict.keys()}
				)

				# keep track of unexpected & missing keys
				snake_case__									=     []
				snake_case__									=     set(pt_model_dict.keys()  )

				for flax_key_tuple, flax_tensor in flax_state_dict.items():
								snake_case__									=     flax_key_tuple[0] == pt_model.base_model_prefix
								snake_case__									=     '.'.join((pt_model.base_model_prefix,) + flax_key_tuple  ) in pt_model_dict

								# adapt flax_key to prepare for loading from/to base model only
								if load_model_with_head_into_base_model and has_base_model_prefix:
												snake_case__									=     flax_key_tuple[1:]
								elif load_base_model_into_model_with_head and require_base_model_prefix:
												snake_case__									=     (pt_model.base_model_prefix,) + flax_key_tuple

								# rename flax weights to PyTorch format
								if flax_key_tuple[-1] == "kernel" and flax_tensor.ndim == 4 and ".".join(_A  ) not in pt_model_dict:
												# conv layer
												snake_case__									=     flax_key_tuple[:-1] + ('weight',)
												snake_case__									=     jnp.transpose(_A      ,   (3, 2, 0, 1)  )
								elif flax_key_tuple[-1] == "kernel" and ".".join(_A  ) not in pt_model_dict:
												# linear layer
												snake_case__									=     flax_key_tuple[:-1] + ('weight',)
												snake_case__									=     flax_tensor.T
								elif flax_key_tuple[-1] in ["scale", "embedding"]:
												snake_case__									=     flax_key_tuple[:-1] + ('weight',)

								# adding batch stats from flax batch norm to pt
								elif "mean" in flax_key_tuple[-1]:
												snake_case__									=     flax_key_tuple[:-1] + ('running_mean',)
								elif "var" in flax_key_tuple[-1]:
												snake_case__									=     flax_key_tuple[:-1] + ('running_var',)

								if "batch_stats" in flax_state:
												snake_case__									=     '.'.join(flax_key_tuple[1:]  )  # Remove the params/batch_stats header
								else:
												snake_case__									=     '.'.join(_A  )

								# We also need to look at `pt_model_dict` and see if there are keys requiring further transformation.
								snake_case__									=     {}
								# New `weight_norm` from https://github.com/huggingface/transformers/pull/24030
								for key in pt_model_dict:
												snake_case__									=     key.split('.'  )
												snake_case__									=     None
												if key_components[-3::2] == ["parametrizations", "original0"]:
																snake_case__									=     key_components[-2] + '_g'
												elif key_components[-3::2] == ["parametrizations", "original1"]:
																snake_case__									=     key_components[-2] + '_v'
												if name is not None:
																snake_case__									=     key_components[:-3] + [name]
																snake_case__									=     '.'.join(_A  )
																snake_case__									=     key

								if flax_key in special_pt_names:
												snake_case__									=     special_pt_names[flax_key]

								if flax_key in pt_model_dict:
												if flax_tensor.shape != pt_model_dict[flax_key].shape:
																raise ValueError(
																    f'''Flax checkpoint seems to be incorrect. Weight {flax_key_tuple} was expected '''
																    f'''to be of shape {pt_model_dict[flax_key].shape}, but is {flax_tensor.shape}.'''  )
												else:
																# add weight to pytorch dict
																snake_case__									=     np.asarray(_A  ) if not isinstance(_A      ,   np.ndarray  ) else flax_tensor
																snake_case__									=     torch.from_numpy(_A  )
																# remove from missing keys
																missing_keys.remove(_A  )
								else:
												# weight is not expected by PyTorch model
												unexpected_keys.append(_A  )

				pt_model.load_state_dict(_A  )

				# re-transform missing_keys to list
				snake_case__									=     list(_A  )

				if len(_A  ) > 0:
								logger.warning(
								    'Some weights of the Flax model were not used when initializing the PyTorch model'
								    f''' {pt_model.__class__.__name__}: {unexpected_keys}\n- This IS expected if you are initializing'''
								    f''' {pt_model.__class__.__name__} from a Flax model trained on another task or with another architecture'''
								    ' (e.g. initializing a BertForSequenceClassification model from a FlaxBertForPreTraining model).\n- This'
								    f''' IS NOT expected if you are initializing {pt_model.__class__.__name__} from a Flax model that you expect'''
								    ' to be exactly identical (e.g. initializing a BertForSequenceClassification model from a'
								    ' FlaxBertForSequenceClassification model).'  )
				else:
								logger.warning(f'''All Flax model weights were used when initializing {pt_model.__class__.__name__}.\n'''  )
				if len(_A  ) > 0:
								logger.warning(
								    f'''Some weights of {pt_model.__class__.__name__} were not initialized from the Flax model and are newly'''
								    f''' initialized: {missing_keys}\nYou should probably TRAIN this model on a down-stream task to be able to'''
								    ' use it for predictions and inference.'  )
				else:
								logger.warning(
								    f'''All the weights of {pt_model.__class__.__name__} were initialized from the Flax model.\n'''
								    'If your task is similar to the task the model of the checkpoint was trained on, '
								    f'''you can already use {pt_model.__class__.__name__} for predictions without further training.'''  )

				return pt_model












__UpperCamelCase					:		List[str]	  =						256
# Modulus to hash a string
__UpperCamelCase					:		int	  =						1000003
def      a_ (      _A      ,   _A  )			->			bool:







				"""simple docstring"""
				snake_case__									=     len(_A  )
				snake_case__									=     len(_A  )
				if p_len > t_len:
								return False

				snake_case__									=     0
				snake_case__									=     0
				snake_case__									=     1

				# Calculating the hash of pattern and substring of text
				for i in range(_A  ):
								snake_case__									=     (ord(pattern[i]  ) + p_hash * alphabet_size) % modulus
								snake_case__									=     (ord(text[i]  ) + text_hash * alphabet_size) % modulus
								if i == p_len - 1:
												continue
								snake_case__									=     (modulus_power * alphabet_size) % modulus

				for i in range(0      ,   t_len - p_len + 1  ):
								if text_hash == p_hash and text[i : i + p_len] == pattern:
												return True
								if i == t_len - p_len:
												continue
								# Calculate the https://en.wikipedia.org/wiki/Rolling_hash
								snake_case__									=     (
								    (text_hash - ord(text[i]  ) * modulus_power) * alphabet_size
								    + ord(text[i + p_len]  )
								) % modulus
				return False
def      a_ (      )			->			None:







				"""simple docstring"""
				snake_case__									=     'abc1abc12'
				snake_case__									=     'alskfjaldsabc1abc1abc12k23adsfabcabc'
				snake_case__									=     'alskfjaldsk23adsfabcabc'
				assert rabin_karp(_A      ,   _A  ) and not rabin_karp(_A      ,   _A  )

				# Test 2)
				snake_case__									=     'ABABX'
				snake_case__									=     'ABABZABABYABABX'
				assert rabin_karp(_A      ,   _A  )

				# Test 3)
				snake_case__									=     'AAAB'
				snake_case__									=     'ABAAAAAB'
				assert rabin_karp(_A      ,   _A  )

				# Test 4)
				snake_case__									=     'abcdabcy'
				snake_case__									=     'abcxabcdabxabcdabcdabcy'
				assert rabin_karp(_A      ,   _A  )

				# Test 5)
				snake_case__									=     'Lü'
				snake_case__									=     'Lüsai'
				assert rabin_karp(_A      ,   _A  )
				snake_case__									=     'Lue'
				assert not rabin_karp(_A      ,   _A  )
				print('Success.'  )


if __name__ == "__main__":
							test_rabin_karp()




