"""A bottom-up tree matching algorithm implementation meant to speed

[0] Fix | Delete

up 2to3's matching process. After the tree patterns are reduced to

[1] Fix | Delete

their rarest linear path, a linear Aho-Corasick automaton is

[2] Fix | Delete

created. The linear automaton traverses the linear paths from the

[3] Fix | Delete

leaves to the root of the AST and returns a set of nodes for further

[4] Fix | Delete

matching. This reduces significantly the number of candidate nodes."""

[5] Fix | Delete

[6] Fix | Delete

__author__ = "George Boutsioukis <gboutsioukis@gmail.com>"

[7] Fix | Delete

[8] Fix | Delete

import logging

[9] Fix | Delete

import itertools

[10] Fix | Delete

from collections import defaultdict

[11] Fix | Delete

[12] Fix | Delete

from . import pytree

[13] Fix | Delete

from .btm_utils import reduce_tree

[14] Fix | Delete

[15] Fix | Delete

class BMNode(object):

[16] Fix | Delete

"""Class for a node of the Aho-Corasick automaton used in matching"""

[17] Fix | Delete

count = itertools.count()

[18] Fix | Delete

def __init__(self):

[19] Fix | Delete

self.transition_table = {}

[20] Fix | Delete

self.fixers = []

[21] Fix | Delete

self.id = next(BMNode.count)

[22] Fix | Delete

self.content = ''

[23] Fix | Delete

[24] Fix | Delete

class BottomMatcher(object):

[25] Fix | Delete

"""The main matcher class. After instantiating the patterns should

[26] Fix | Delete

be added using the add_fixer method"""

[27] Fix | Delete

[28] Fix | Delete

def __init__(self):

[29] Fix | Delete

self.match = set()

[30] Fix | Delete

self.root = BMNode()

[31] Fix | Delete

self.nodes = [self.root]

[32] Fix | Delete

self.fixers = []

[33] Fix | Delete

self.logger = logging.getLogger("RefactoringTool")

[34] Fix | Delete

[35] Fix | Delete

def add_fixer(self, fixer):

[36] Fix | Delete

"""Reduces a fixer's pattern tree to a linear path and adds it

[37] Fix | Delete

to the matcher(a common Aho-Corasick automaton). The fixer is

[38] Fix | Delete

appended on the matching states and called when they are

[39] Fix | Delete

reached"""

[40] Fix | Delete

self.fixers.append(fixer)

[41] Fix | Delete

tree = reduce_tree(fixer.pattern_tree)

[42] Fix | Delete

linear = tree.get_linear_subpattern()

[43] Fix | Delete

match_nodes = self.add(linear, start=self.root)

[44] Fix | Delete

for match_node in match_nodes:

[45] Fix | Delete

match_node.fixers.append(fixer)

[46] Fix | Delete

[47] Fix | Delete

def add(self, pattern, start):

[48] Fix | Delete

"Recursively adds a linear pattern to the AC automaton"

[49] Fix | Delete

#print("adding pattern", pattern, "to", start)

[50] Fix | Delete

if not pattern:

[51] Fix | Delete

#print("empty pattern")

[52] Fix | Delete

return [start]

[53] Fix | Delete

if isinstance(pattern[0], tuple):

[54] Fix | Delete

#alternatives

[55] Fix | Delete

#print("alternatives")

[56] Fix | Delete

match_nodes = []

[57] Fix | Delete

for alternative in pattern[0]:

[58] Fix | Delete

#add all alternatives, and add the rest of the pattern

[59] Fix | Delete

#to each end node

[60] Fix | Delete

end_nodes = self.add(alternative, start=start)

[61] Fix | Delete

for end in end_nodes:

[62] Fix | Delete

match_nodes.extend(self.add(pattern[1:], end))

[63] Fix | Delete

return match_nodes

[64] Fix | Delete

else:

[65] Fix | Delete

#single token

[66] Fix | Delete

#not last

[67] Fix | Delete

if pattern[0] not in start.transition_table:

[68] Fix | Delete

#transition did not exist, create new

[69] Fix | Delete

next_node = BMNode()

[70] Fix | Delete

start.transition_table[pattern[0]] = next_node

[71] Fix | Delete

else:

[72] Fix | Delete

#transition exists already, follow

[73] Fix | Delete

next_node = start.transition_table[pattern[0]]

[74] Fix | Delete

[75] Fix | Delete

if pattern[1:]:

[76] Fix | Delete

end_nodes = self.add(pattern[1:], start=next_node)

[77] Fix | Delete

else:

[78] Fix | Delete

end_nodes = [next_node]

[79] Fix | Delete

return end_nodes

[80] Fix | Delete

[81] Fix | Delete

def run(self, leaves):

[82] Fix | Delete

"""The main interface with the bottom matcher. The tree is

[83] Fix | Delete

traversed from the bottom using the constructed

[84] Fix | Delete

automaton. Nodes are only checked once as the tree is

[85] Fix | Delete

retraversed. When the automaton fails, we give it one more

[86] Fix | Delete

shot(in case the above tree matches as a whole with the

[87] Fix | Delete

rejected leaf), then we break for the next leaf. There is the

[88] Fix | Delete

special case of multiple arguments(see code comments) where we

[89] Fix | Delete

recheck the nodes

[90] Fix | Delete

[91] Fix | Delete

Args:

[92] Fix | Delete

The leaves of the AST tree to be matched

[93] Fix | Delete

[94] Fix | Delete

Returns:

[95] Fix | Delete

A dictionary of node matches with fixers as the keys

[96] Fix | Delete

"""

[97] Fix | Delete

current_ac_node = self.root

[98] Fix | Delete

results = defaultdict(list)

[99] Fix | Delete

for leaf in leaves:

[100] Fix | Delete

current_ast_node = leaf

[101] Fix | Delete

while current_ast_node:

[102] Fix | Delete

current_ast_node.was_checked = True

[103] Fix | Delete

for child in current_ast_node.children:

[104] Fix | Delete

# multiple statements, recheck

[105] Fix | Delete

if isinstance(child, pytree.Leaf) and child.value == u";":

[106] Fix | Delete

current_ast_node.was_checked = False

[107] Fix | Delete

break

[108] Fix | Delete

if current_ast_node.type == 1:

[109] Fix | Delete

#name

[110] Fix | Delete

node_token = current_ast_node.value

[111] Fix | Delete

else:

[112] Fix | Delete

node_token = current_ast_node.type

[113] Fix | Delete

[114] Fix | Delete

if node_token in current_ac_node.transition_table:

[115] Fix | Delete

#token matches

[116] Fix | Delete

current_ac_node = current_ac_node.transition_table[node_token]

[117] Fix | Delete

for fixer in current_ac_node.fixers:

[118] Fix | Delete

if not fixer in results:

[119] Fix | Delete

results[fixer] = []

[120] Fix | Delete

results[fixer].append(current_ast_node)

[121] Fix | Delete

[122] Fix | Delete

else:

[123] Fix | Delete

#matching failed, reset automaton

[124] Fix | Delete

current_ac_node = self.root

[125] Fix | Delete

if (current_ast_node.parent is not None

[126] Fix | Delete

and current_ast_node.parent.was_checked):

[127] Fix | Delete

#the rest of the tree upwards has been checked, next leaf

[128] Fix | Delete

break

[129] Fix | Delete

[130] Fix | Delete

#recheck the rejected node once from the root

[131] Fix | Delete

if node_token in current_ac_node.transition_table:

[132] Fix | Delete

#token matches

[133] Fix | Delete

current_ac_node = current_ac_node.transition_table[node_token]

[134] Fix | Delete

for fixer in current_ac_node.fixers:

[135] Fix | Delete

if not fixer in results.keys():

[136] Fix | Delete

results[fixer] = []

[137] Fix | Delete

results[fixer].append(current_ast_node)

[138] Fix | Delete

[139] Fix | Delete

current_ast_node = current_ast_node.parent

[140] Fix | Delete

return results

[141] Fix | Delete

[142] Fix | Delete

def print_ac(self):

[143] Fix | Delete

"Prints a graphviz diagram of the BM automaton(for debugging)"

[144] Fix | Delete

print("digraph g{")

[145] Fix | Delete

def print_node(node):

[146] Fix | Delete

for subnode_key in node.transition_table.keys():

[147] Fix | Delete

subnode = node.transition_table[subnode_key]

[148] Fix | Delete

print("%d -> %d [label=%s] //%s" %

[149] Fix | Delete

(node.id, subnode.id, type_repr(subnode_key), str(subnode.fixers)))

[150] Fix | Delete

if subnode_key == 1:

[151] Fix | Delete

print(subnode.content)

[152] Fix | Delete

print_node(subnode)

[153] Fix | Delete

print_node(self.root)

[154] Fix | Delete

print("}")

[155] Fix | Delete

[156] Fix | Delete

# taken from pytree.py for debugging; only used by print_ac

[157] Fix | Delete

_type_reprs = {}

[158] Fix | Delete

def type_repr(type_num):

[159] Fix | Delete

global _type_reprs

[160] Fix | Delete

if not _type_reprs:

[161] Fix | Delete

from .pygram import python_symbols

[162] Fix | Delete

# printing tokens is possible but not as useful

[163] Fix | Delete

# from .pgen2 import token // token.__dict__.items():

[164] Fix | Delete

for name, val in python_symbols.__dict__.items():

[165] Fix | Delete

if type(val) == int: _type_reprs[val] = name

[166] Fix | Delete

return _type_reprs.setdefault(type_num, type_num)

[167] Fix | Delete

[168] Fix | Delete