A preview of the fixer automaton and current progress

I hoped to have a prototype ready by this weekend, but school got in the way and I couldn't find the time to complete it. The automaton can currently add constant(without wildcards) subpatterns to itself and run on a tree. I'm currently working on a function that converts a compiled pattern tree to its subpatterns in order to test more fixers, which turned out to be much harder than I thought since Base/Node/WildcardPattern objects were not really made for this. But I'm close. Anyway, I've made a graph of the current automaton for the raw_input fixer in order to make the process more clear:

The pattern was power< name='raw_input' trailer< '(' [any] ')' > any* > . The pattern was reduced(by hand) to it's minimum subpatterns:



{ '('->trailer->power, raw_input->power, ')'->trailer->power }



from which the above automaton was built. Now consider adding the very similar pattern for the buffer fixer. The resulting automaton would look like this:

The automaton begins for each leaf, and when each subpattern is matched the current node is marked with its id. When all subpatterns match on a single node for a fixer, the whole fixer matches. The patterns for other fixers will be added on the same automaton. There are some subtleties here: wildcard subpatterns need to be split at the wildcard positions and added as new subpatterns on all nodes starting with the next token, plus once on the root; alternatives must have their destination nodes combined on a single subpattern; repeaters with constant numbers need to be multiply matched etc. But overall, I believe that each issue can be handled without restricting the current fixer syntax.

Progress Report

Exams start tomorrow and I've spent most of this week studying. But I've had the chance to start coding a prototype of the matching algorithm I proposed. It is completed to the point where it simulates the raw_input fixer pattern. Profiling results look promising; for example for this one fixer it took about 0.087 CPU seconds on a single file(preprocessing aside).

Of course running this single fixer with the current algorithm took about 0.018 seconds. But the new algorithm should behave much better when more fixer patterns are added, with processing time remaining close to the current level, so all in all I find this promising.

Let me explain. In theory, bottom-up tree traversal takes number_of_leaves*tree_height steps. Say b is the maximum number of children in a node and h is the height then this becomes (b^h)*h. h is about logn so the the traversal is in the O(n*logn) class. Of course the constant numbers depend on the characteristics of each tree. So, since the automaton runs in constant time on each step the number of comparisons is still O(n*logn).

The current version of the algorithm runs in O(n*pattern_nodes). Since pattern_nodes can be considered a constant number compared to n, this is O(n). Repeaters can add an overhead here when backtracking, depending on their position on the pattern_tree. But let's also consider this a constant factor, just for simplicity(I believe they add a b^h*h factor too; I have no time to check this).

The important thing to note is that the algorithm depends on the sizes of the patterns, which means that matching takes longer each time a pattern is added. The proposed algorithm is independent of the pattern sizes(except for the preprocessing part), so this is why I expect this number to stay close to the current level.

While writing this prototype I came to the realization that it is unnecessary to store the leaf-to-root strings; we can simply keep a set of the tree leaves and traverse them by asking each one for its parent. When a fixer transforms the tree, it currently marks the nodes that it changed. This can be extended to propagate the "changed" label to its node's children, and we can use this information to recheck only their descendant leaves.

A couple of other realizations I came to: patterns with wildcards need to be split up, then the subpatterns are added to the automaton skipping x states, where x is the subpattern's position. I'm working on the details of the implementation. Second, there is a great potential for threading on this algorithm, each thread can simulate the automaton on a different leaf in parallel so this will be something to consider in the future.

Some benchmarking results, and an implementation plan

Well I'm still not able to run profile for building django-3k and I'm not sure what it is that I'm doing wrong. But anyway, at least I got it to work for a single file. I used feedgenerator.py from the the django-3k codebase and here is the result, using gprof2dot:

No surprises here, the program spends most of its in the pattern matching functions, as it was already known(the green boxes down-left). Since a significant overhead in python is function calls, I'm still confident that a more iterative pattern matching algorithm that will avoid the number of recursions will be able to speed things up. Anyway, as a first reference here are the results of time:

Command being timed: "/usr/local/bin/python3 /home/giorgos/dev/gsoc/django-3k/setup.py build"
User time (seconds): 386.96
System time (seconds): 0.87
Percent of CPU this job got: 97%
Elapsed (wall clock) time (h:mm:ss or m:ss): 6:37.14
....

Note that I've built python with threads disabled, because they often mess up the profiler. But it shouldn't matter, results are always relative and threads are not used internally in 2to3.

Now, analyzing the algorithm I came up with, I'm pretty sure that theoretically it should offer no benefit compared to the existing one, i.e. I believe it runs the same number of comparisons. Of course preprocessing a few parts may help overall, but still. On the other hand, as I mentioned above I think a major issue in the existing algorithm is its recursive nature; the algorithm I propose may benefit from being a bit more "linear".

Anyway, running a few tests it seems to me that the most (practically) computationally intensive part is obtaining the bottom-up strings, and doing so every time the tree is altered. Profiling showed that it can take up to 0.5 secs to obtain the full set; that's quite a lot, and usually 1-2 fixers are applied per file so multiply that by 2. That's not so bad, but I'll see in the future if there is a faster way to obtain it.

So a portion the algorithm in pseudocode currently is something like this:

get_bottom-strings:
#Bottom strings will be lists of the format[(NodeId, TOKENTYPE), ...].
  for leave in leaves:
    return leave.type + parent.bottom_string() #recursively obtain bottom-up strings

get_pattern_dict:
  for fixer in fixers:
    reduce_repeaters(fixer.pattern_tree) # reduce repeaters to obtain a constant tree
        -> WildcardPattern is reduced to its MIN; this may actually create nodes
    for leave in pattern_tree.leaves:
      obtain bottom-up string
    return pattern_dict

Then we use the pattern_dictionaries to build the AC automaton. Now simulating the AC automaton in python may be too slow for our purposes here, so perhaps a C version could be considered in the future if that's an option. The automaton is constructed by adding each string at a time as detailed in the Aho-Corasick paper, and nodes will be represented by a ACNode type with a dictionary as a transition table. On each final node callbacks will be added to mark the position of the match. Finally a match dictionary with nodeId as the key will be used to check whether at any point a fixer has been matched.

So that pretty much covers it. I'm at the stage of planning how to fit all these in the existing code. I hope I'll have some time this week(my term exams start on Monday) to push this further.

A bottom-up tree matching algorithm

Seeing a tree from the bottom up is a bit like 'unfolding' it. The tree structure is converted into a series of linear paths starting from leaf to root.

So the first step in the algorithm is to create those leaf-to-root strings, by keeping a record of all leaves and propagating up the tree. In a common python file there are typically a few thousand leaves with an average height of 50-60 nodes. The process can have a significant overhead since it must be run once for every file but the final result may be worth it.

Now the main idea behind this algorithm is reducing the search space. We can extract from each complex pattern a "minimum" set of constant pattern paths that that we can use to mark candidate nodes. Say for example we have the same pattern tree for the print stmt:



The minimum constant path in this case is simple_stmt->print_stmt, which we obtain by reducing the wildcard patterns to their minimum sufficient pattern(in this case none). After reducing the repeater patterns we can obtain the path dictionary as in Algorithm D only this time we'll be writing them backwards.

For simplicity lets consider only the above pattern and the single path {print_stmt->simple_stmt}. We proceed by combining the constant patterns into a single Aho-Corasick automaton that resembles the one in Algorithm D. This part of the algorithm can be preprocessed and updated only when the fixer patterns change, and the resulting automaton can be pickled.

The resulting automaton is run on each leaf-to-root string and the nodes are marked when each constant path is matched. When the set of sufficient pattern paths is matched we run the existing matching algorithm on this node; this step is necessary because wildcard patterns have to still be matched exactly in order to return the correct content for each variable.

Is this process worth it? I haven't analyzed it yet. Traversing a tree from the bottom is inefficient since we run into the same nodes again and again. On the other checking linear patterns requires less time than tree patterns. Furthermore storing the strings as real immutable strings we can take advantage of the optimizations the interpreter provides, unlike running recursive calls to traverse the tree. Plus preprocessing the fixer patterns into an automaton can save some time.

The next step will be to formally analyze the algorithm and obtain some preliminary profiling results.

Why Algorithm D won't work

When I was hastily making my proposal for GSOC, I came upon Hoffman & O'Donnell's paper "Pattern Matching in Trees". The paper's subject seemed to fit perfectly 2to3's matching problem and I assumed that the algorithm they proposed, Algorithm D, could be somehow extended to include repeaters like * and +. After further research, I realized I was wrong; their algorithm depends on pattern tree nodes having a fixed arity, i.e. no repeaters.

To explain this a bit further, Algorithm D works like this: The pattern tree is converted into a trie, then a dictionary of paths is formed from the trie and an Aho-Corasick automaton is created from the dictionary. The final states of the automaton define the matching state; when all path-states have been reached the pattern has been matched.

Here's a demonstration to make this clear:

This is a pattern tree and the resulting trie. The pattern will match any print_stmt that follows any other statement(any is a wildcard).

The path dictionary would be {simple_stmt1, simple_stmt2print_stmt}. The resulting automaton is easily constructed from the trie and it would look like this(fail transitions are omitted):

The numbers correspond to a fixed position in the tree, that is starting from root we follow transition 1 when we encounter the first child, transition 2 for the second and so on.
But how could this pattern, that matches a print_stmt in any position, be converted into an automaton?

I was confident that the problem could be somehow worked around and extend the automata to include repeaters. No matter how much I tried I admit that I'm out of wits here. Even more, I have started to think that the top-down automaton is not capable of matching repeaters, because it somehow resembles counting; think about it, if the tree was in linear form and had deep paths left and right, say

simple_stmt( ((((....)))), print_stmt, ((((...)))) )

then you'd have to keep a count of the left&right parentheses: the classic case that exceeds the capabilities of finite automata.

Not all hope is lost however; I have thought of a different algorihm that will still use the Aho Corasick automaton but in a bottom-up manner. More details will follow in the next article