"\nThe diff parser is trying to be a faster version of the normal parser by trying\nto reuse the nodes of a previous pass over the same file. This is also called\nincremental parsing in parser literature. The difference is mostly that with\nincremental parsing you get a range that needs to be reparsed. Here we\ncalculate that range ourselves by using difflib. After that it's essentially\nincremental parsing.\n\nThe biggest issue of this approach is that we reuse nodes in a mutable way. The\nintial design and idea is quite problematic for this parser, but it is also\npretty fast. Measurements showed that just copying nodes in Python is simply\nquite a bit slower (especially for big files >3 kLOC). Therefore we did not\nwant to get rid of the mutable nodes, since this is usually not an issue.\n\nThis is by far the hardest software I ever wrote, exactly because the initial\ndesign is crappy. When you have to account for a lot of mutable state, it\ncreates a ton of issues that you would otherwise not have. This file took\nprobably 3-6 months to write, which is insane for a parser.\n\nThere is a fuzzer in that helps test this whole thing. Please use it if you\nmake changes here. If you run the fuzzer like::\n\n    test/fuzz_diff_parser.py random -n 100000\n\nyou can be pretty sure that everything is still fine. I sometimes run the\nfuzzer up to 24h to make sure everything is still ok.\n"
_R='file_input'
_Q='funcdef'
_P='classdef'
_O='ERROR_DEDENT'
_N='async_funcdef'
_M='decorated'
_L='newline'
_K='endmarker'
_J='DEDENT'
_I='error_node'
_H='async_stmt'
_G='\r'
_F='suite'
_E='\n'
_D='error_leaf'
_C=None
_B=False
_A=True
import re,difflib
from collections import namedtuple
import logging
from parso.utils import split_lines
from parso.python.parser import Parser
from parso.python.tree import EndMarker
from parso.python.tokenize import PythonToken,BOM_UTF8_STRING
from parso.python.token import PythonTokenTypes
LOG=logging.getLogger(__name__)
DEBUG_DIFF_PARSER=_B
_INDENTATION_TOKENS='INDENT',_O,_J
NEWLINE=PythonTokenTypes.NEWLINE
DEDENT=PythonTokenTypes.DEDENT
NAME=PythonTokenTypes.NAME
ERROR_DEDENT=PythonTokenTypes.ERROR_DEDENT
ENDMARKER=PythonTokenTypes.ENDMARKER
def _is_indentation_error_leaf(node):return node.type==_D and node.token_type in _INDENTATION_TOKENS
def _get_previous_leaf_if_indentation(leaf):
	A=leaf
	while A and _is_indentation_error_leaf(A):A=A.get_previous_leaf()
	return A
def _get_next_leaf_if_indentation(leaf):
	A=leaf
	while A and _is_indentation_error_leaf(A):A=A.get_next_leaf()
	return A
def _get_suite_indentation(tree_node):return _get_indentation(tree_node.children[1])
def _get_indentation(tree_node):return tree_node.start_pos[1]
def _assert_valid_graph(node):
	'\n    Checks if the parent/children relationship is correct.\n\n    This is a check that only runs during debugging/testing.\n    ';A=node
	try:H=A.children
	except AttributeError:
		if A.type==_D and A.token_type in _INDENTATION_TOKENS:assert not A.value;assert not A.prefix;return
		D=_get_previous_leaf_if_indentation(A.get_previous_leaf())
		if D is _C:B=A.prefix;E=1,0
		else:assert D.end_pos<=A.start_pos,(D,A);B=D.value+A.prefix;E=D.start_pos
		if _E in B or _G in B:G=split_lines(B);I=E[0]+len(G)-1;C=I,len(G[-1])
		else:
			C=E[0],E[1]+len(B)
			if B.startswith(BOM_UTF8_STRING)and A.get_start_pos_of_prefix()==(1,0):C=C[0],C[1]-1
		assert A.start_pos==C,(A.start_pos,C)
	else:
		for F in H:assert F.parent==A,(A,F);_assert_valid_graph(F)
def _assert_nodes_are_equal(node1,node2):
	B=node1;A=node2
	try:C=B.children
	except AttributeError:assert not hasattr(A,'children'),(B,A);assert B.value==A.value,(B,A);assert B.type==A.type,(B,A);assert B.prefix==A.prefix,(B,A);assert B.start_pos==A.start_pos,(B,A);return
	else:
		try:D=A.children
		except AttributeError:assert _B,(B,A)
	for(E,F)in zip(C,D):_assert_nodes_are_equal(E,F)
	assert len(C)==len(D),_E+repr(C)+_E+repr(D)
def _get_debug_error_message(module,old_lines,new_lines):A=new_lines;B=split_lines(module.get_code(),keepends=_A);C=difflib.unified_diff(A,B);D=difflib.unified_diff(old_lines,A);import parso;return"There's an issue with the diff parser. Please report (parso v%s) - Old/New:\n%s\nActual Diff (May be empty):\n%s"%(parso.__version__,''.join(D),''.join(C))
def _get_last_line(node_or_leaf):
	A=node_or_leaf.get_last_leaf()
	if _ends_with_newline(A):return A.start_pos[0]
	else:
		B=A.get_next_leaf()
		if B.type==_K and _E in B.prefix:return A.end_pos[0]+1
		return A.end_pos[0]
def _skip_dedent_error_leaves(leaf):
	A=leaf
	while A is not _C and A.type==_D and A.token_type==_J:A=A.get_previous_leaf()
	return A
def _ends_with_newline(leaf,suffix=''):
	B=suffix;A=leaf;A=_skip_dedent_error_leaves(A)
	if A.type==_D:C=A.token_type.lower()
	else:C=A.type
	return C==_L or B.endswith(_E)or B.endswith(_G)
def _flows_finished(pgen_grammar,stack):
	'\n    if, while, for and try might not be finished, because another part might\n    still be parsed.\n    '
	for A in stack:
		if A.nonterminal in('if_stmt','while_stmt','for_stmt','try_stmt'):return _B
	return _A
def _func_or_class_has_suite(node):
	A=node
	if A.type==_M:A=A.children[-1]
	if A.type in(_N,_H):A=A.children[-1]
	return A.type in(_P,_Q)and A.children[-1].type==_F
def _suite_or_file_input_is_valid(pgen_grammar,stack):
	B=stack
	if not _flows_finished(pgen_grammar,B):return _B
	for A in reversed(B):
		if A.nonterminal=='decorator':return _B
		if A.nonterminal==_F:return len(A.nodes)>1
	return _A
def _is_flow_node(node):
	A=node
	if A.type==_H:A=A.children[1]
	try:B=A.children[0].value
	except AttributeError:return _B
	return B in('if','for','while','try','with')
class _PositionUpdatingFinished(Exception):0
def _update_positions(nodes,line_offset,last_leaf):
	B=last_leaf;C=line_offset
	for A in nodes:
		try:D=A.children
		except AttributeError:
			A.line+=C
			if A is B:raise _PositionUpdatingFinished
		else:_update_positions(D,C,B)
class DiffParser:
	'\n    An advanced form of parsing a file faster. Unfortunately comes with huge\n    side effects. It changes the given module.\n    '
	def __init__(A,pgen_grammar,tokenizer,module):A._pgen_grammar=pgen_grammar;A._tokenizer=tokenizer;A._module=module
	def _reset(A):A._copy_count=0;A._parser_count=0;A._nodes_tree=_NodesTree(A._module)
	def update(A,old_lines,new_lines):
		'\n        The algorithm works as follows:\n\n        Equal:\n            - Assure that the start is a newline, otherwise parse until we get\n              one.\n            - Copy from parsed_until_line + 1 to max(i2 + 1)\n            - Make sure that the indentation is correct (e.g. add DEDENT)\n            - Add old and change positions\n        Insert:\n            - Parse from parsed_until_line + 1 to min(j2 + 1), hopefully not\n              much more.\n\n        Returns the new module node.\n        ';E=old_lines;B=new_lines;LOG.debug('diff parser start');A._module._used_names=_C;A._parser_lines_new=B;A._reset();F=len(B);K=difflib.SequenceMatcher(_C,E,A._parser_lines_new);L=K.get_opcodes();LOG.debug('line_lengths old: %s; new: %s'%(len(E),F))
		for(D,G,H,I,C)in L:
			LOG.debug('-> code[%s] old[%s:%s] new[%s:%s]',D,G+1,H,I+1,C)
			if C==F and B[-1]=='':C-=1
			if D=='equal':M=I-G;A._copy_from_old_parser(M,G+1,H,C)
			elif D=='replace':A._parse(until_line=C)
			elif D=='insert':A._parse(until_line=C)
			else:assert D=='delete'
		A._nodes_tree.close()
		if DEBUG_DIFF_PARSER:
			try:N=''.join(B);assert A._module.get_code()==N;_assert_valid_graph(A._module);O=Parser(A._pgen_grammar,error_recovery=_A).parse(A._tokenizer(B));_assert_nodes_are_equal(A._module,O)
			except AssertionError:print(_get_debug_error_message(A._module,E,B));raise
		J=A._module.end_pos[0]
		if J!=F:raise Exception('(%s != %s) '%(J,F)+_get_debug_error_message(A._module,E,B))
		LOG.debug('diff parser end');return A._module
	def _enabled_debugging(B,old_lines,lines_new):
		A=lines_new
		if B._module.get_code()!=''.join(A):LOG.warning('parser issue:\n%s\n%s',''.join(old_lines),''.join(A))
	def _copy_from_old_parser(A,line_offset,start_line_old,until_line_old,until_line_new):
		F=line_offset;C=-1
		while until_line_new>A._nodes_tree.parsed_until_line:
			G=A._nodes_tree.parsed_until_line-F;D=A._get_old_line_stmt(G+1)
			if D is _C:A._parse(A._nodes_tree.parsed_until_line+1)
			else:
				E=D.parent.children;H=E.index(D)
				if start_line_old==1 and E[0].get_first_leaf().prefix.startswith(BOM_UTF8_STRING):B=[]
				else:I=A._nodes_tree.parsed_until_line+1;B=A._nodes_tree.copy_nodes(E[H:],until_line_old,F)
				if B:A._copy_count+=1;J=A._nodes_tree.parsed_until_line;LOG.debug('copy old[%s:%s] new[%s:%s]',B[0].start_pos[0],B[-1].end_pos[0]-1,I,J)
				else:A._parse(A._nodes_tree.parsed_until_line+1)
			assert C!=A._nodes_tree.parsed_until_line,C;C=A._nodes_tree.parsed_until_line
	def _get_old_line_stmt(D,old_line):
		C=old_line;A=D._module.get_leaf_for_position((C,0),include_prefixes=_A)
		if _ends_with_newline(A):A=A.get_next_leaf()
		if A.get_start_pos_of_prefix()[0]==C:
			B=A
			while B.parent.type not in(_R,_F):B=B.parent
			if B.start_pos[0]>=C:return B
	def _parse(A,until_line):
		'\n        Parses at least until the given line, but might just parse more until a\n        valid state is reached.\n        ';C=until_line;B=0
		while C>A._nodes_tree.parsed_until_line:
			D=A._try_parse_part(C);E=D.children;A._nodes_tree.add_parsed_nodes(E,A._keyword_token_indents)
			if A._replace_tos_indent is not _C:A._nodes_tree.indents[-1]=A._replace_tos_indent
			LOG.debug('parse_part from %s to %s (to %s in part parser)',E[0].get_start_pos_of_prefix()[0],A._nodes_tree.parsed_until_line,D.end_pos[0]-1);assert B!=A._nodes_tree.parsed_until_line,B;B=A._nodes_tree.parsed_until_line
	def _try_parse_part(A,until_line):"\n        Sets up a normal parser that uses a spezialized tokenizer to only parse\n        until a certain position (or a bit longer if the statement hasn't\n        ended.\n        ";A._parser_count+=1;B=A._nodes_tree.parsed_until_line;C=A._parser_lines_new[B:];D=A._diff_tokenize(C,until_line,line_offset=B);A._active_parser=Parser(A._pgen_grammar,error_recovery=_A);return A._active_parser.parse(tokens=D)
	def _diff_tokenize(B,lines,until_line,line_offset=0):
		H=line_offset;G=_B;E=B._nodes_tree.indents;I=len(E);J=B._tokenizer(lines,start_pos=(H+1,0),indents=E,is_first_token=H==0);K=B._active_parser.stack;B._replace_tos_indent=_C;B._keyword_token_indents={}
		for C in J:
			D=C.type
			if D==DEDENT:
				if len(E)<I:
					while _A:
						D,L,F,A=C=next(J)
						if D in(DEDENT,ERROR_DEDENT):
							if D==ERROR_DEDENT:B._replace_tos_indent=F[1]+1
						else:break
					if _E in A or _G in A:A=re.sub('[^\\n\\r]+\\Z','',A)
					else:
						assert F[1]>=len(A),repr(A)
						if F[1]-len(A)==0:A=''
					yield PythonToken(ENDMARKER,'',F,A);break
			elif D==NEWLINE and C.start_pos[0]>=until_line:G=_A
			elif G:
				G=_B
				if len(E)==I:
					if _suite_or_file_input_is_valid(B._pgen_grammar,K):yield PythonToken(ENDMARKER,'',C.start_pos,'');break
			if D==NAME and C.string in('class','def'):B._keyword_token_indents[C.start_pos]=list(E)
			yield C
class _NodesTreeNode:
	_ChildrenGroup=namedtuple('_ChildrenGroup','prefix children line_offset last_line_offset_leaf')
	def __init__(A,tree_node,parent=_C,indentation=0):A.tree_node=tree_node;A._children_groups=[];A.parent=parent;A._node_children=[];A.indentation=indentation
	def finish(A):
		B=[]
		for(F,C,D,G)in A._children_groups:
			E=_get_next_leaf_if_indentation(C[0].get_first_leaf());E.prefix=F+E.prefix
			if D!=0:
				try:_update_positions(C,D,G)
				except _PositionUpdatingFinished:pass
			B+=C
		A.tree_node.children=B
		for H in B:H.parent=A.tree_node
		for I in A._node_children:I.finish()
	def add_child_node(A,child_node):A._node_children.append(child_node)
	def add_tree_nodes(B,prefix,children,line_offset=0,last_line_offset_leaf=_C):
		C=children;A=last_line_offset_leaf
		if A is _C:A=C[-1].get_last_leaf()
		D=B._ChildrenGroup(prefix,C,line_offset,A);B._children_groups.append(D)
	def get_last_line(C,suffix):
		A=suffix;B=0
		if C._children_groups:
			D=C._children_groups[-1];E=_get_previous_leaf_if_indentation(D.last_line_offset_leaf);B=E.end_pos[0]+D.line_offset
			if _ends_with_newline(E,A):B-=1
		B+=len(split_lines(A))-1
		if A and not A.endswith(_E)and not A.endswith(_G):B+=1
		if C._node_children:return max(B,C._node_children[-1].get_last_line(A))
		return B
	def __repr__(A):return'<%s: %s>'%(A.__class__.__name__,A.tree_node)
class _NodesTree:
	def __init__(A,module):B=module;A._base_node=_NodesTreeNode(B);A._working_stack=[A._base_node];A._module=B;A._prefix_remainder='';A.prefix='';A.indents=[0]
	@property
	def parsed_until_line(self):return self._working_stack[-1].get_last_line(self.prefix)
	def _update_insertion_node(A,indentation):
		for B in reversed(list(A._working_stack)):
			if B.indentation<indentation or B is A._working_stack[0]:return B
			A._working_stack.pop()
	def add_parsed_nodes(B,tree_nodes,keyword_token_indents):
		A=tree_nodes;C=B.prefix;A=B._remove_endmarker(A)
		if not A:B.prefix=C+B.prefix;return
		assert A[0].type!=_L;D=B._update_insertion_node(A[0].start_pos[1]);assert D.tree_node.type in(_F,_R);D.add_tree_nodes(C,A);B._update_parsed_node_tos(A[-1],keyword_token_indents)
	def _update_parsed_node_tos(B,tree_node,keyword_token_indents):
		C=keyword_token_indents;A=tree_node
		if A.type==_F:E=A.parent.children[0];D=_NodesTreeNode(A,indentation=C[E.start_pos][-1]);D.add_tree_nodes('',list(A.children));B._working_stack[-1].add_child_node(D);B._working_stack.append(D);B._update_parsed_node_tos(A.children[-1],C)
		elif _func_or_class_has_suite(A):B._update_parsed_node_tos(A.children[-1],C)
	def _remove_endmarker(B,tree_nodes):
		'\n        Helps cleaning up the tree nodes that get inserted.\n        ';C=tree_nodes;A=C[-1].get_last_leaf();E=A.type==_K;B._prefix_remainder=''
		if E:
			F=A.prefix;D=max(F.rfind(_E),F.rfind(_G))
			if D>-1:A.prefix,B._prefix_remainder=A.prefix[:D+1],A.prefix[D+1:]
		B.prefix=''
		if E:B.prefix=A.prefix;C=C[:-1]
		return C
	def _get_matching_indent_nodes(F,tree_nodes,is_new_suite):
		B=is_new_suite;A=iter(tree_nodes)
		if B:yield next(A)
		C=next(A);D=_get_indentation(C)
		if not B and D not in F.indents:return
		yield C
		for E in A:
			if _get_indentation(E)!=D:return
			yield E
	def copy_nodes(A,tree_nodes,until_line,line_offset):
		'\n        Copies tree nodes from the old parser tree.\n\n        Returns the number of tree nodes that were copied.\n        ';B=tree_nodes
		if B[0].type in(_D,_I):return[]
		C=_get_indentation(B[0]);E=list(A._working_stack);F=A.prefix;G=A.indents;A.indents=[A for A in A.indents if A<=C];A._update_insertion_node(C);D,A._working_stack,A.prefix,H=A._copy_nodes(list(A._working_stack),B,until_line,line_offset,A.prefix)
		if D:A.indents+=H
		else:A._working_stack=E;A.prefix=F;A.indents=G
		return D
	def _copy_nodes(K,working_stack,nodes,until_line,line_offset,prefix='',is_nested=_B):
		P=line_offset;L=until_line;M=nodes;I=prefix;G=working_stack;A=[];J=[];M=list(K._get_matching_indent_nodes(M,is_new_suite=is_nested));H=''
		for B in M:
			if B.start_pos[0]>L:break
			if B.type==_K:break
			if B.type==_D and B.token_type in(_J,_O):break
			if _get_last_line(B)>L:
				if _func_or_class_has_suite(B):A.append(B)
				break
			try:T=B.children
			except AttributeError:pass
			else:
				C=B
				if C.type==_M:C=C.children[-1]
				if C.type in(_N,_H):C=C.children[-1]
				if C.type in(_P,_Q):Q=C.children[-1]
				else:Q=T[-1]
				if Q.type in(_D,_I):break
			A.append(B)
		if A:
			while A:
				D=A[-1]
				if D.type in(_D,_I)or _is_flow_node(A[-1]):
					H='';A.pop()
					while A:
						D=A[-1]
						if D.get_last_leaf().type==_L:break
						A.pop()
					continue
				if len(A)>1 and A[-2].type==_I:A.pop();continue
				break
		if not A:return[],G,I,J
		R=G[-1];D=A[-1];N=_B
		if _func_or_class_has_suite(D):
			F=D
			while F.type!=_F:F=F.children[-1]
			U=_get_suite_indentation(F);J.append(U);S=_NodesTreeNode(F,indentation=_get_indentation(D));V,W,H,X=K._copy_nodes(G+[S],F.children,L,P,is_nested=_A);J+=X
			if len(V)<2:A.pop();H=''
			else:assert A;R.add_child_node(S);G=W;N=_A
		if A:
			if not _ends_with_newline(A[-1].get_last_leaf())and not N:Y=A[-1].get_next_leaf().prefix;H=split_lines(Y,keepends=_A)[0]
			if N:
				E=A[-1]
				if E.type==_M:E=E.children[-1]
				if E.type in(_N,_H):E=E.children[-1]
				O=E.children[-2].get_last_leaf();assert O==':'
			else:O=A[-1].get_last_leaf()
			R.add_tree_nodes(I,A,P,O);I=H;K._prefix_remainder=''
		return A,G,I,J
	def close(A):
		A._base_node.finish()
		try:D=A._module.get_last_leaf()
		except IndexError:B=[1,0]
		else:D=_skip_dedent_error_leaves(D);B=list(D.end_pos)
		C=split_lines(A.prefix);assert len(C)>0
		if len(C)==1:
			if C[0].startswith(BOM_UTF8_STRING)and B==[1,0]:B[1]-=1
			B[1]+=len(C[0])
		else:B[0]+=len(C)-1;B[1]=len(C[-1])
		E=EndMarker('',tuple(B),A.prefix+A._prefix_remainder);E.parent=A._module;A._module.children.append(E)