A re-organization and hopefully optimization of TotalRewriter

[GoogleCodeExporter]

The original combination of ExhaustiveRewriter and RewriteOnce did something 
like the following:

while there are no changes
    for each rewriter R in list
        for each sub-expression E (in depth-first)
            if R(E) != E then replace E by R(E), end both "for each" loops

This had the effect of extending the context for each sub-expression all over 
again for each rewriter in the list. TotalRewriter has been introduced, in my 
understanding, to minimize this contextual expansion while doing exhaustive 
rewriting, in the following way:

while there are no changes
    for each sub-expression E (in depth-first)
        for each rewriter R in list
            if R(E) != E then replace E by R(E), end both "for each" loops

That is, there was an inversion of the two inner loops, essentially. This is 
better as the outside loop on sub-expressions is the more expensive one.

However note that we still end both loops when there is a replacement.
** When there is a replacement, we go all the way back to the root and start 
over **.
This seems inefficient as it seems like we should exploit changes locally 
before starting all over from the root.

The following pseudo-code expresses the idea of being done with 
sub-expressions, then processing the parent, before going back up the tree.:

function newTotalRewriter(E, Rewriters) :    // using a name now for recursion
    previous = E
    while E == previous
        replace each *immediate* sub-expression E' of E by newTotalRewriter(E', Rewriters) (under extended context, of course)
        E = R(E) for R in Rewriters the first such that R(E) != E.

This has the effect of getting "inside" a sub-expression and only leaving it 
once it's completely reduced. Only then will its parent be processed. The 
parent will then be repeatedly processed until it is not changing anymore 
either. After all that, we leave the function and go back to the parent's 
parent.

Note that it might seem like we are re-processing the sub-expressions of the 
parent repeatedly because we may have multiple iterations of the while loop. 
However that will not happen to pre-existing sub-expressions, due to caching. 
It's only potentially *new* sub-expressions of E (some rewriters will modify E 
such that it will have newly created sub-expressions, although I think that is 
rare) that will be processed (and then, of course, for the first time).

Note that this has one potentially major disadvantage: we process the 
sub-expressions before even looking at the parent. If the parent has some 
obvious short-circuiting (it is a multiplication by zero or an if then else 
with a condition equal to "true"), we will reduce all sub-expressions before 
solving that easy short-circuit. A better version is therefore:

function newTotalRewriter(E, Rewriters) :    // using a name now for recursion
    previous = E
    while E == previous
        E = R(E) for R in Rewriters the first such that R(E) != E.
        replace each *immediate* sub-expression E' of E by newTotalRewriter(E', Rewriters) (under extended context, of course)

that is, we apply the rewriters to the parent only first, before looking at 
sub-expressions. If any sub-expression is replaced, then the E == previous 
condition will fail and we will again run the E = R(E)... line which will have 
a chance of using whatever helpful results from the sub-expression evaluations.

In conclusion, this issue is about trying out this latest version and see if it 
does better than TotalRewriter.

(may be a good idea to insert this explanation in the comments, either the 
public javadoc or at least privately to developers).

Original issue reported on code.google.com by [email protected] on 7 Feb 2014 at 1:30