


"""simple docstring"""
import collections
import os
import re
from pathlib import Path


__SCREAMING_SNAKE_CASE							:    Union[str, Any]		=    'src/transformers'


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







def 						_a				(      _SCREAMING_SNAKE_CASE				)    ->				Optional[int]:
							if _re_test_backend.search(_SCREAMING_SNAKE_CASE				) is None:
														return None
							snake_case_           =		[b[0] for b in _re_backend.findall(_SCREAMING_SNAKE_CASE				)]
							backends.sort()
							return "_and_".join(_SCREAMING_SNAKE_CASE				)







def 						_a				(      _SCREAMING_SNAKE_CASE				)    ->				Optional[int]:
							with open(_SCREAMING_SNAKE_CASE				, """r"""				, encoding="""utf-8"""				, newline="""\n"""				) as f:
														snake_case_           =		f.readlines()

							snake_case_           =		0
							while line_index < len(_SCREAMING_SNAKE_CASE				) and not lines[line_index].startswith("""_import_structure = {"""				):
														line_index += 1

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

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

							snake_case_           =		{"""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.
														snake_case_           =		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:
																					snake_case_           =		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

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

																					snake_case_           =		objects
														else:
																					line_index += 1

    # At this stage we are in the TYPE_CHECKING part, first grab the objects without a specific backend
							snake_case_           =		[]
							while (
							    line_index < len(_SCREAMING_SNAKE_CASE				)
							    and find_backend(lines[line_index]				) is None
							    and not lines[line_index].startswith("""else"""				)
							):
														snake_case_           =		lines[line_index]
														snake_case_           =		_re_import.search(_SCREAMING_SNAKE_CASE				)
														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

							snake_case_           =		{"""none""": objects}
							# Let's continue with backend-specific objects
							while line_index < len(_SCREAMING_SNAKE_CASE				):
														# If the line is an if is_backend_available, we grab all objects associated.
														snake_case_           =		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:
																					snake_case_           =		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

																					snake_case_           =		[]
																					# Until we unindent, add backend objects to the list
																					while len(lines[line_index]				) <= 1 or lines[line_index].startswith(""" """ * 8				):
																												snake_case_           =		lines[line_index]
																												snake_case_           =		_re_import.search(_SCREAMING_SNAKE_CASE				)
																												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

																					snake_case_           =		objects
														else:
																					line_index += 1

							return import_dict_objects, type_hint_objects







def 						_a				(      _SCREAMING_SNAKE_CASE				, _SCREAMING_SNAKE_CASE				)    ->				Tuple:

							def find_duplicates(_SCREAMING_SNAKE_CASE				):
														return [k for k, v in collections.Counter(_SCREAMING_SNAKE_CASE				).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!"]

							snake_case_           =		[]
							for key in import_dict_objects.keys():
														snake_case_           =		find_duplicates(import_dict_objects[key]				)
														if duplicate_imports:
																					errors.append(f"""Duplicate _import_structure definitions for: {duplicate_imports}"""				)
														snake_case_           =		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]				)				):
																					snake_case_           =		"""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				(      )    ->				str:
							snake_case_           =		[]
							for root, _, files in os.walk(_SCREAMING_SNAKE_CASE				):
														if "__init__.py" in files:
																					snake_case_           =		os.path.join(_SCREAMING_SNAKE_CASE				, """__init__.py"""				)
																					snake_case_           =		parse_init(_SCREAMING_SNAKE_CASE				)
																					if objects is not None:
																												snake_case_           =		analyze_results(*_SCREAMING_SNAKE_CASE				)
																												if len(_SCREAMING_SNAKE_CASE				) > 0:
																																			snake_case_           =		f"""Problem in {fname}, both halves do not define the same objects.\n{errors[0]}"""
																																			failures.append("""\n""".join(_SCREAMING_SNAKE_CASE				)				)
							if len(_SCREAMING_SNAKE_CASE				) > 0:
														raise ValueError("""\n\n""".join(_SCREAMING_SNAKE_CASE				)				)







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


__SCREAMING_SNAKE_CASE							:    Dict		=    [
    'convert_pytorch_checkpoint_to_tf2',
    'modeling_flax_pytorch_utils',
    'models.esm.openfold_utils',
]







def 						_a				(      )    ->				Tuple:
							# This is to make sure the transformers module imported is the one in the repo.
							from transformers.utils import direct_transformers_import

							snake_case_           =		direct_transformers_import(_SCREAMING_SNAKE_CASE				)

							snake_case_           =		set(transformers._import_structure.keys()				)
							# This contains all the base keys of the _import_structure object defined in the init, but if the user is missing
							# some optional dependencies, they may not have all of them. Thus we read the init to read all additions and
							# (potentiall re-) add them.
							with open(os.path.join(_SCREAMING_SNAKE_CASE				, """__init__.py"""				)				, """r"""				) as f:
														snake_case_           =		f.read()
							import_structure_keys.update(set(re.findall(r"""import_structure\[\"([^\"]*)\"\]"""				, _SCREAMING_SNAKE_CASE				)				)				)

							snake_case_           =		[
							    module
							    for module in get_transformers_submodules()
							    if module not in IGNORE_SUBMODULES and module not in import_structure_keys
							]

							if len(_SCREAMING_SNAKE_CASE				) > 0:
														snake_case_           =		"""\n""".join(f"""- {module}""" for module in module_not_registered				)
														raise ValueError(
														    """The following submodules are not properly registed 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()







"""simple docstring"""
from __future__ import annotations

from collections import deque





class      __A     :





							'''simple docstring'''

							def __init__(				self							:      List[Any]		,       UpperCAmelCase_							:      list[str]       )					->List[Any]:



														"""simple docstring"""



														snake_case_           =		[]
														self.adlist.append(
														    {"""value""": """""", """next_states""": [], """fail_state""": 0, """output""": []}       )

														for keyword in keywords:
																					self.add_keyword(UpperCAmelCase_       )
														self.set_fail_transitions()



							def 		lowerCAmelCase       (				self							:      int		,       UpperCAmelCase_							:      int		,       UpperCAmelCase_							:      str       )					->int | None:



														"""simple docstring"""



														for state in self.adlist[current_state]["next_states"]:
																					if char == self.adlist[state]["value"]:
																												return state
														return None



							def 		lowerCAmelCase       (				self							:      int		,       UpperCAmelCase_							:      str       )					->None:



														"""simple docstring"""



														snake_case_           =		0
														for character in keyword:
																					snake_case_           =		self.find_next_state(UpperCAmelCase_		,       UpperCAmelCase_       )
																					if next_state is None:
																												self.adlist.append(
																												    {
																												        """value""": character,
																												        """next_states""": [],
																												        """fail_state""": 0,
																												        """output""": [],
																												    }       )
																												self.adlist[current_state]["next_states"].append(len(self.adlist       ) - 1       )
																												snake_case_           =		len(self.adlist       ) - 1
																					else:
																												snake_case_           =		next_state
														self.adlist[current_state]["output"].append(UpperCAmelCase_       )



							def 		lowerCAmelCase       (				self							:      Optional[Any]       )					->None:



														"""simple docstring"""



														snake_case_           =		deque()
														for node in self.adlist[0]["next_states"]:
																					q.append(UpperCAmelCase_       )
																					snake_case_           =		0
														while q:
																					snake_case_           =		q.popleft()
																					for child in self.adlist[r]["next_states"]:
																												q.append(UpperCAmelCase_       )
																												snake_case_           =		self.adlist[r]["""fail_state"""]
																												while (
																												    self.find_next_state(UpperCAmelCase_		,       self.adlist[child]["""value"""]       ) is None
																												    and state != 0
																												):
																																			snake_case_           =		self.adlist[state]["""fail_state"""]
																												snake_case_           =		self.find_next_state(
																												    UpperCAmelCase_		,       self.adlist[child]["""value"""]       )
																												if self.adlist[child]["fail_state"] is None:
																																			snake_case_           =		0
																												snake_case_           =		(
																												    self.adlist[child]["""output"""]
																												    + self.adlist[self.adlist[child]["""fail_state"""]]["""output"""]
																												)



							def 		lowerCAmelCase       (				self							:      Union[str, Any]		,       UpperCAmelCase_							:      str       )					->dict[str, list[int]]:



														"""simple docstring"""



														snake_case_           =		{}  # returns a dict with keywords and list of its occurrences
														snake_case_           =		0
														for i in range(len(UpperCAmelCase_       )       ):
																					while (
																					    self.find_next_state(UpperCAmelCase_		,       string[i]       ) is None
																					    and current_state != 0
																					):
																												snake_case_           =		self.adlist[current_state]["""fail_state"""]
																					snake_case_           =		self.find_next_state(UpperCAmelCase_		,       string[i]       )
																					if next_state is None:
																												snake_case_           =		0
																					else:
																												snake_case_           =		next_state
																												for key in self.adlist[current_state]["output"]:
																																			if key not in result:
																																										snake_case_           =		[]
																																			result[key].append(i - len(UpperCAmelCase_       ) + 1       )
														return result


if __name__ == "__main__":
				import doctest

				doctest.testmod()



