Bug 16571 – JSC needs a NodeWalker class to walk the AST tree

• Status: RESOLVED
• Resolution: INVALID
• Component: JavaScriptCore

[Eric Seidel (no email)]

JSC needs a NodeWalker class to walk the AST tree

I'm writing this out in a bug, so I make sure to cover most/all of the foreseeable uses with my implementation.

Uses I know of:
1.  Syntax checking -- needs to walk all StatementNodes (which may be buried under FuncExprNodes), and needs eachNode and leavingNode callbacks (entering to push labels & check syntax and after to pop labels)
2.  optimizeVariableAccess -- needs to walk all StatementNodes (not necessarily including those buried in FuncExprNodes), needs an eachNode callback
3.  enable/disable debugging -- needs to walk all StatementNodes (including those buried under FuncExprNodes), needs eachNode callback

If there are more uses which we can think of now, we should list them in this bug so I can design for them.

Current thoughts I've had include:

1.  Having an "add your kids to this stack" method, keeping a kid stack and a parent stack, all nodes get pushed onto the parent stack and the kid stack, then the "add your kids method" is called, during advance() the top kid node is compared with the top parent node, if they match, the "leaving" callback is called, and then both stacks are popped, this repeats until either the stacks are empty or the kid stack does not agree with the parent stack in which case that's the next node.

2.  Similar to above, but instead keeping a single stack of node* + state variable.  Push yourself onto the stack with a "leaving" state, then call the "push your kids" method, each gets pushed with an "entering" state.  When poping nodes of the stack, check state and call the leaving callback for each with a leaving state, until you reach one with an "entering" state which is the next node.

3.  Add childNodes() virtual accessor function and possibly as "hasChildNodes()" virtual function.  You still need a stack with states, or two stacks, but you avoid pushing leaf nodes with a "leaving" state only to then immediately pop them.  Instead you end up having to copy the returned child node pointers onto the stack. :(

None of these methods are perfect yet.  I'm sure there is a good solution here.  Perhaps a bit of algorithms research is what's in order. :)

[Eric Seidel (no email)]

As a further optimization, we could actually let the beginCallback return some sort of information as to if the endCallback is needed or not.  Still pondering...

[Geoffrey Garen]

I'm not convinced that an abstract NodeWalker is the best direction right now, for two reasons:

1. Making tree traversal specific to the operation at hand (e.g., declaration gathering doesn't visit as many nodes as variable access optimization) was a substantial performance win, at least when it was first implemented.

2. The upcoming move to byte code will substantially change our AST needs in unpredictable ways.

[Eric Seidel (no email)]

The big win is that it's non-recursive.  Meaning when we move to byte-code, we can support much much deeper AST trees.

[Eric Seidel (no email)]

Adding ggaren so he'll see my comment.

[Geoffrey Garen]

AST traversal is already non-recursive.

[Eric Seidel (no email)]

yes, you're right.  I'm OK leaving the NodeWalker patch in bug 16547 out of the tree.

[Gavin Barraclough]

I don't think this bug is still relevant.