



import collections
import importlib.util
import os
import re
from pathlib import Path


UpperCAmelCase__       =	'src/transformers'


# Matches is_xxx_available()
UpperCAmelCase__       =	re.compile(r"is\_([a-z_]*)_available()")
# Catches a one-line _import_struct = {xxx}
UpperCAmelCase__       =	re.compile(r"^_import_structure\s+=\s+\{([^\}]+)\}")
# Catches a line with a key-values pattern: "bla": ["foo", "bar"]
UpperCAmelCase__       =	re.compile(r"\s+\"\S*\":\s+\[([^\]]*)\]")
# Catches a line if not is_foo_available
UpperCAmelCase__       =	re.compile(r"^\s*if\s+not\s+is\_[a-z_]*\_available\(\)")
# Catches a line _import_struct["bla"].append("foo")
UpperCAmelCase__       =	re.compile(r"^\s*_import_structure\[\"\S*\"\]\.append\(\"(\S*)\"\)")
# Catches a line _import_struct["bla"].extend(["foo", "bar"]) or _import_struct["bla"] = ["foo", "bar"]
UpperCAmelCase__       =	re.compile(r"^\s*_import_structure\[\S*\](?:\.extend\(|\s*=\s+)\[([^\]]*)\]")
# Catches a line with an object between quotes and a comma:     "MyModel",
UpperCAmelCase__       =	re.compile("^\s+\"([^\"]+)\",")
# Catches a line with objects between brackets only:    ["foo", "bar"],
UpperCAmelCase__       =	re.compile("^\s+\[([^\]]+)\]")
# Catches a line with from foo import bar, bla, boo
UpperCAmelCase__       =	re.compile(r"\s+from\s+\S*\s+import\s+([^\(\s].*)\n")
# Catches a line with try:
UpperCAmelCase__       =	re.compile(r"^\s*try:")
# Catches a line with else:
UpperCAmelCase__       =	re.compile(r"^\s*else:")





def 							A     (					_UpperCAmelCase    :       List[str]   )    ->			List[str]:







   '''simple docstring'''
   if _re_test_backend.search(a__   ) is None:
      return None
   _UpperCAmelCase			=       [b[0] for b in _re_backend.findall(a__   )]
   backends.sort()
   return "_and_".join(a__   )





def 							A     (					_UpperCAmelCase    :       Any   )    ->			int:







   '''simple docstring'''
   with open(a__							,       'r'							,       encoding='utf-8'							,       newline='\n'   ) as f:
      _UpperCAmelCase			=       f.readlines()

   _UpperCAmelCase			=       0
   while line_index < len(a__   ) and not lines[line_index].startswith('_import_structure = {'   ):
      line_index += 1

   # If this is a traditional init, just return.
   if line_index >= len(a__   ):
      return None

   # First grab the objects without a specific backend in _import_structure
   _UpperCAmelCase			=       []
   while not lines[line_index].startswith('if TYPE_CHECKING'   ) and find_backend(lines[line_index]   ) is None:
      _UpperCAmelCase			=       lines[line_index]
      # If we have everything on a single line, let's deal with it.
      if _re_one_line_import_struct.search(a__   ):
         _UpperCAmelCase			=       _re_one_line_import_struct.search(a__   ).groups()[0]
         _UpperCAmelCase			=       re.findall('\[([^\]]+)\]'							,       a__   )
         for imp in imports:
            objects.extend([obj[1:-1] for obj in imp.split(', '   )]   )
         line_index += 1
         continue
      _UpperCAmelCase			=       _re_import_struct_key_value.search(a__   )
      if single_line_import_search is not None:
         _UpperCAmelCase			=       [obj[1:-1] for obj in single_line_import_search.groups()[0].split(', '   ) if len(a__   ) > 0]
         objects.extend(a__   )
      elif line.startswith(' ' * 8 + '"'   ):
         objects.append(line[9:-3]   )
      line_index += 1

   _UpperCAmelCase			=       {'none': objects}
   # Let's continue with backend-specific objects in _import_structure
   while not lines[line_index].startswith('if TYPE_CHECKING'   ):
      # If the line is an if not is_backend_available, we grab all objects associated.
      _UpperCAmelCase			=       find_backend(lines[line_index]   )
      # Check if the backend declaration is inside a try block:
      if _re_try.search(lines[line_index - 1]   ) is None:
         _UpperCAmelCase			=       None

      if backend is not None:
         line_index += 1

         # Scroll until we hit the else block of try-except-else
         while _re_else.search(lines[line_index]   ) is None:
            line_index += 1

         line_index += 1

         _UpperCAmelCase			=       []
         # Until we unindent, add backend objects to the list
         while len(lines[line_index]   ) <= 1 or lines[line_index].startswith(' ' * 4   ):
            _UpperCAmelCase			=       lines[line_index]
            if _re_import_struct_add_one.search(a__   ) is not None:
               objects.append(_re_import_struct_add_one.search(a__   ).groups()[0]   )
            elif _re_import_struct_add_many.search(a__   ) is not None:
               _UpperCAmelCase			=       _re_import_struct_add_many.search(a__   ).groups()[0].split(', '   )
               _UpperCAmelCase			=       [obj[1:-1] for obj in imports if len(a__   ) > 0]
               objects.extend(a__   )
            elif _re_between_brackets.search(a__   ) is not None:
               _UpperCAmelCase			=       _re_between_brackets.search(a__   ).groups()[0].split(', '   )
               _UpperCAmelCase			=       [obj[1:-1] for obj in imports if len(a__   ) > 0]
               objects.extend(a__   )
            elif _re_quote_object.search(a__   ) is not None:
               objects.append(_re_quote_object.search(a__   ).groups()[0]   )
            elif line.startswith(' ' * 8 + '"'   ):
               objects.append(line[9:-3]   )
            elif line.startswith(' ' * 12 + '"'   ):
               objects.append(line[13:-3]   )
            line_index += 1

         _UpperCAmelCase			=       objects
      else:
         line_index += 1

    # At this stage we are in the TYPE_CHECKING part, first grab the objects without a specific backend
   _UpperCAmelCase			=       []
   while (
       line_index < len(a__   )
       and find_backend(lines[line_index]   ) is None
       and not lines[line_index].startswith('else'   )
   ):
      _UpperCAmelCase			=       lines[line_index]
      _UpperCAmelCase			=       _re_import.search(a__   )
      if single_line_import_search is not None:
         objects.extend(single_line_import_search.groups()[0].split(', '   )   )
      elif line.startswith(' ' * 8   ):
         objects.append(line[8:-2]   )
      line_index += 1

   _UpperCAmelCase			=       {'none': objects}
   # Let's continue with backend-specific objects
   while line_index < len(a__   ):
      # If the line is an if is_backend_available, we grab all objects associated.
      _UpperCAmelCase			=       find_backend(lines[line_index]   )
      # Check if the backend declaration is inside a try block:
      if _re_try.search(lines[line_index - 1]   ) is None:
         _UpperCAmelCase			=       None

      if backend is not None:
         line_index += 1

         # Scroll until we hit the else block of try-except-else
         while _re_else.search(lines[line_index]   ) is None:
            line_index += 1

         line_index += 1

         _UpperCAmelCase			=       []
         # Until we unindent, add backend objects to the list
         while len(lines[line_index]   ) <= 1 or lines[line_index].startswith(' ' * 8   ):
            _UpperCAmelCase			=       lines[line_index]
            _UpperCAmelCase			=       _re_import.search(a__   )
            if single_line_import_search is not None:
               objects.extend(single_line_import_search.groups()[0].split(', '   )   )
            elif line.startswith(' ' * 12   ):
               objects.append(line[12:-2]   )
            line_index += 1

         _UpperCAmelCase			=       objects
      else:
         line_index += 1

   return import_dict_objects, type_hint_objects





def 							A     (					_UpperCAmelCase    :       List[Any]							,       _UpperCAmelCase    :       str   )    ->			Optional[Any]:







   '''simple docstring'''

   def find_duplicates(_UpperCAmelCase    :       Dict   ):
      return [k for k, v in collections.Counter(a__   ).items() if v > 1]

   if list(import_dict_objects.keys()   ) != list(type_hint_objects.keys()   ):
      return ["Both sides of the init do not have the same backends!"]

   _UpperCAmelCase			=       []
   for key in import_dict_objects.keys():
      _UpperCAmelCase			=       find_duplicates(import_dict_objects[key]   )
      if duplicate_imports:
         errors.append(F"Duplicate _import_structure definitions for: {duplicate_imports}"   )
      _UpperCAmelCase			=       find_duplicates(type_hint_objects[key]   )
      if duplicate_type_hints:
         errors.append(F"Duplicate TYPE_CHECKING objects for: {duplicate_type_hints}"   )

      if sorted(set(import_dict_objects[key]   )   ) != sorted(set(type_hint_objects[key]   )   ):
         _UpperCAmelCase			=       'base imports' if key == 'none' else F"{key} backend"
         errors.append(F"Differences for {name}:"   )
         for a in type_hint_objects[key]:
            if a not in import_dict_objects[key]:
               errors.append(F"  {a} in TYPE_HINT but not in _import_structure."   )
         for a in import_dict_objects[key]:
            if a not in type_hint_objects[key]:
               errors.append(F"  {a} in _import_structure but not in TYPE_HINT."   )
   return errors





def 							A     (					)    ->			List[str]:







   '''simple docstring'''
   _UpperCAmelCase			=       []
   for root, _, files in os.walk(a__   ):
      if "__init__.py" in files:
         _UpperCAmelCase			=       os.path.join(a__							,       '__init__.py'   )
         _UpperCAmelCase			=       parse_init(a__   )
         if objects is not None:
            _UpperCAmelCase			=       analyze_results(*a__   )
            if len(a__   ) > 0:
               _UpperCAmelCase			=       F"Problem in {fname}, both halves do not define the same objects.\n{errors[0]}"
               failures.append('\n'.join(a__   )   )
   if len(a__   ) > 0:
      raise ValueError('\n\n'.join(a__   )   )





def 							A     (					)    ->			str:







   '''simple docstring'''
   _UpperCAmelCase			=       []
   for path, directories, files in os.walk(a__   ):
      for folder in directories:
         # Ignore private modules
         if folder.startswith('_'   ):
            directories.remove(a__   )
            continue
         # Ignore leftovers from branches (empty folders apart from pycache)
         if len(list((Path(a__   ) / folder).glob('*.py'   )   )   ) == 0:
            continue
         _UpperCAmelCase			=       str((Path(a__   ) / folder).relative_to(a__   )   )
         _UpperCAmelCase			=       short_path.replace(os.path.sep							,       '.'   )
         submodules.append(a__   )
      for fname in files:
         if fname == "__init__.py":
            continue
         _UpperCAmelCase			=       str((Path(a__   ) / fname).relative_to(a__   )   )
         _UpperCAmelCase			=       short_path.replace('.py'							,       ''   ).replace(os.path.sep							,       '.'   )
         if len(submodule.split('.'   )   ) == 1:
            submodules.append(a__   )
   return submodules


UpperCAmelCase__       =	[
    'convert_pytorch_checkpoint_to_tf2',
    'modeling_flax_pytorch_utils',
]





def 							A     (					)    ->			Tuple:







   '''simple docstring'''
   # This is to make sure the transformers module imported is the one in the repo.
   _UpperCAmelCase			=       importlib.util.spec_from_file_location(
       'transformers'							,       os.path.join(a__							,       '__init__.py'   )							,       submodule_search_locations=[PATH_TO_TRANSFORMERS]							,       )
   _UpperCAmelCase			=       spec.loader.load_module()

   _UpperCAmelCase			=       [
       module
       for module in get_transformers_submodules()
       if module not in IGNORE_SUBMODULES and module not in transformers._import_structure.keys()
   ]
   if len(a__   ) > 0:
      _UpperCAmelCase			=       '\n'.join(F"- {module}" for module in module_not_registered   )
      raise ValueError(
          'The following submodules are not properly registered in the main init of Transformers:\n'
          F"{list_of_modules}\n"
          'Make sure they appear somewhere in the keys of `_import_structure` with an empty list as value.'   )


if __name__ == "__main__":
       check_all_inits()
       check_submodules()





from __future__ import annotations

from itertools import permutations
from random import randint
from timeit import repeat





def 							A     (					)    ->			tuple[list[int], int]:







			'''simple docstring'''
			_UpperCAmelCase			=       [randint(-1_000							,       1_000   ) for i in range(10   )]
			_UpperCAmelCase			=       randint(-5_000							,       5_000   )
			return (arr, r)


UpperCAmelCase__       =	make_dataset()





def 							A     (					_UpperCAmelCase    :       list[int]							,       _UpperCAmelCase    :       int   )    ->			tuple[int, ...]:







			'''simple docstring'''
			for triplet in permutations(_UpperCAmelCase							,       3   ):
						if sum(_UpperCAmelCase   ) == target:
									return tuple(sorted(_UpperCAmelCase   )   )
			return (0, 0, 0)





def 							A     (					_UpperCAmelCase    :       list[int]							,       _UpperCAmelCase    :       int   )    ->			tuple[int, int, int]:







			'''simple docstring'''
			arr.sort()
			_UpperCAmelCase			=       len(_UpperCAmelCase   )
			for i in range(n - 1   ):
						_UpperCAmelCase	,					_UpperCAmelCase			=       i + 1, n - 1
						while left < right:
									if arr[i] + arr[left] + arr[right] == target:
												return (arr[i], arr[left], arr[right])
									elif arr[i] + arr[left] + arr[right] < target:
												left += 1
									elif arr[i] + arr[left] + arr[right] > target:
												right -= 1
			return (0, 0, 0)





def 							A     (					)    ->			tuple[float, float]:







			'''simple docstring'''
			_UpperCAmelCase			=       '\nfrom __main__ import dataset, triplet_sum1, triplet_sum2\n'
			_UpperCAmelCase			=       '\ntriplet_sum1(*dataset)\n'
			_UpperCAmelCase			=       '\ntriplet_sum2(*dataset)\n'
			_UpperCAmelCase			=       repeat(setup=_UpperCAmelCase							,       stmt=_UpperCAmelCase							,       repeat=5							,       number=10_000   )
			_UpperCAmelCase			=       repeat(setup=_UpperCAmelCase							,       stmt=_UpperCAmelCase							,       repeat=5							,       number=10_000   )
			return (min(_UpperCAmelCase   ), min(_UpperCAmelCase   ))


if __name__ == "__main__":
							from doctest import testmod

							testmod()
							UpperCAmelCase__       =	solution_times()
							print(f"""The time for naive implementation is {times[0]}.""")
							print(f"""The time for optimized implementation is {times[1]}.""")
