Class Visitor

source code

object --+
         |
        Visitor

ADT Visitor.
This class helps to perform iterations over arbitrary ADTs.


When visitor runs, it will visit each constituent of an ADT.
When an ADT instance is visited, the visitor will first look
for method named `enter_C` for each class `C` in the MRO of
the ADT instance. All found methods will be invoked.

Then it will look for a method called `enter_C` for each class `C`
in the MRO sequence of the ADT class. If one is found,
then it will be called, other classes in the MRO sequence will not
be considered.

Finally, the visitor will look for a method called `leave_C` using
the same algorithm as described for the `enter_C` method.

The algorithm, described above, actually implements the
depth-first traversal. Methods starting with the prefix `enter`
are called right before the corresponding subtree is visited
(preorder).  Methods starting with the `leave` are called just
after the subtree is visited. Methods starting with `visit`
actually perform the visiting. If it is not overridden, then
`visit_ADT` method is invoked, that will continue traversal to the
subtree. If `visit_C` method is overridden (where `C` is name of
class in the MRO of the ADT instance), then it is responsibility
of the `visit_C` method to call `run` method to continue
traversal. If `run` is not called, then the traversal will not
continue. It is possible to change the order of traversal, by
overriding `visit` methods. Usually, it is better to keep away
from the `visit` methods, and use `enter` (the preorder traversal)
if possible. However, if it is needed to inject some code between
the traversal of two subtrees of a tree, or if an order should be
changed, then the visit method is a way to go.

By default, every element of an ADT is traversed. It is possible
to terminate the traversal abnormally (to short-circuit) by
returning not-a-None value from any of the methods. The returned
value will be a result of the `run` method.


Example
-------

Suppose we have a small expression language with defined as
follows:

>>> class Exp(ADT)   : pass
>>> class Binop(Exp) : pass
>>> class Unop(Exp)  : pass
>>> class Value(Exp) : pass
>>> class Add(Binop) : pass
>>> class Mul(Binop) : pass
>>> class Neg(Unop)  : pass
>>> class Var(Value) : pass
>>> class Int(Value) : pass


We will write an abstract interpreter that will calculate a sign
of expression. In our abstraction, we now a sign of constants,
signs of variables are unknown. The negation operation negates the
sign of expression, and any binary operation preserves the sign,
if both operands have the same sign, otherwise the sign is
undefined. We will use the following lattice to represent our
abstraction:


                      True  False
                        |     |
                        +--+--+
                           |
                          None

The same expressed in Python:


>>> class Sign(Visitor) :
        def __init__(self):
            self.neg = None

        def visit_Binop(self,exp):
            self.run(exp.arg[0])
            lhs = self.neg
            self.run(exp.arg[1])
            rhs = self.neg
            if lhs != rhs:
                self.neg = None

        def leave_Neg(self,exp):
            if self.neg is not None:
                self.neg = not self.neg

        def enter_Var(self,var):
            self.neg = None

        def enter_Int(self,n):
            self.neg = n < Int(0)

We overrode method ``visit_Binop`` that will be invoked for both,
addition and subtraction, since in our abstraction they behave the
same. We chose to override the ``visit`` stage instead of the
``enter`` or leave, because we wanted to inject our code between
visiting left and right branch of the expression. We overrode
`leave_Neg` to switch the sign _after_ the enclosed expression is
visited. Since variable can have arbitrary sign, we're must stop
the sign analysis as soon as we have a variable. Finally, for constants
we just look at their sign.


To test our sign analysis let's write a simple expression,

>>> exp = Add((Neg(Neg(Int(1)))), Mul(Int(2), Neg(Neg(Int(3)))))

It is easy to see that it is positive (in fact it is not).  In the
infix notation, the expression corresponds to


>>> -(-1) + 2 * -(-3)
7

So, let's run the analysis:

>>> exp = Add((Neg(Neg(Int(1)))), Mul(Int(2), Neg(Neg(Int(3)))))
>>> ai = Sign()
>>> ai.run(exp)
>>> print("exp {0} is {1}".format(exp,
                                  "negative" if ai.neg else
                                  "unknown"  if ai.neg is None else
                                  "positive"))

For an ADT of type C the method `visit_C` is looked up in the
visitors methods dictionary. If it doesn't exist, then `visit_B` is
looked up, where `B` is the base class of `C`. The process continues,
until the method is found. This is guaranteed to terminate,
since visit_ADT method is defined.

Note: Non ADTs will be silently ignored.

Once the method is found it is called. It is the method's responsiblity
to recurse into sub-elements, e.g., call run method.

For example, suppose that we want to count negative values in
some BIL expression:

class CountNegatives(Visitor):
    def __init__(self):
        self.neg = False
        self.count = 0

    def visit_Int(self, int):
        if int.arg < 0 and not self.neg               or int.arg > 0 and self.neg:
            self.count += 1

    def visit_NEG(self, op):
        was = self.neg
        self.neg = not was
        self.run(op.arg)
        self.neg = was

We need to keep track on the unary negation operator, and, of
course, we need to look for immediates, so we override two methods:
visit_Int for Int constructor and visit_NEG for counting unary minuses.
(Actually we should count for bitwise NOT operation also, since it will
change the sign bit also, but lets forget about it for the matter of the
exercise (and it can be easily fixed just by matching visit_UnOp)).

When we hit visit_NEG we toggle current sign, storing its previous value
and recurse into the operand. After we return from the recursion, we restore
the sign.