Truffle Node replacement problem caused by recursion

[Wei Zhang]

Hi guys,

I came across a problem with Truffle node replacement when I was
trying to apply Python level inlining to binarytrees.py (one of the
shootout benchmarks). I thought it is worth sharing it with all of you
that are using Truffle.

Basically, recursion might cause inconsistencies in a Truffle AST.
That is a node's parent's children don't include itself.

We all know binarytrees. This is the simplified AST that is enough to
show the problem:

RootNodeOfFoo
    Statement0
    Statement1
    BinaryOp
        Call(foo)
        Constant(1)

When the function foo starts execution, BinaryOp node is specializing
itself from the Uninitialized state by executing its two operands
before it replaces itself with a specialized version. Because one of
its operand is a recursive call, the deepest recursive invocation will
specialized BinaryOp first. When it returns to an earlier active
BinaryOp.executeAndSpecialize0(), the node replacement will fail. At
that point, the children of BinaryOp have already adopted by the
lastly created BinaryOpSpecialized. We end up with a situation where
Call(foo)'s parent is not a child of RootNodeOfFoo.

So when I try to replace the recursive call(foo) node with a inlined
version, I cannot do a simple node replacement. I have to lookup the
real parent that is reachable from the RootNodeOfFoo.

Maybe it's not a bad idea to have some kind of failure detection of
node replacement...
Thanks,
--------------------------
Wei Zhang
Personal: NdrZmansN at Gmail.com