Truffle Node replacement problem caused by recursion

[Andreas Woess]

Hi Wei, Stefan, et al,

I've pushed a fix about a week ago that solves this problem including an
assertion that should trigger if you do anything wrong. Please update
and let me know whether everything works as expected now.

- andreas

On 19.10.2013 01:44, Wei Zhang wrote:
> 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
>