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
depthfirst 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 shortcircuit) by
returning notaNone 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 subelements, 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.





visit_Seq(self,
adt)
Deconstructs sequences 
source code




result


Inherited from object :
__delattr__ ,
__format__ ,
__getattribute__ ,
__hash__ ,
__init__ ,
__new__ ,
__reduce__ ,
__reduce_ex__ ,
__repr__ ,
__setattr__ ,
__sizeof__ ,
__str__ ,
__subclasshook__

Inherited from object :
__class__

Default visitor.
This method will be called for those data types that has no specific
visitors. It will recursively descent into all ADT values.
