Bug 16571 - JSC needs a NodeWalker class to walk the AST tree
Summary: JSC needs a NodeWalker class to walk the AST tree
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Macintosh OS X 10.4
: P2 Normal
Assignee: Nobody
Depends on:
Blocks: 16547
  Show dependency treegraph
Reported: 2007-12-21 22:02 PST by Eric Seidel (no email)
Modified: 2012-09-07 12:24 PDT (History)
3 users (show)

See Also:


Note You need to log in before you can comment on or make changes to this bug.
Description Eric Seidel (no email) 2007-12-21 22:02:52 PST
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. :)
Comment 1 Eric Seidel (no email) 2007-12-21 22:39:09 PST
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...
Comment 2 Geoffrey Garen 2008-01-01 11:15:11 PST
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.
Comment 3 Eric Seidel (no email) 2008-01-01 11:43:04 PST
The big win is that it's non-recursive.  Meaning when we move to byte-code, we can support much much deeper AST trees.
Comment 4 Eric Seidel (no email) 2008-01-01 11:43:21 PST
Adding ggaren so he'll see my comment.
Comment 5 Geoffrey Garen 2008-01-01 12:44:39 PST
AST traversal is already non-recursive.
Comment 6 Eric Seidel (no email) 2008-01-01 14:36:16 PST
yes, you're right.  I'm OK leaving the NodeWalker patch in bug 16547 out of the tree.
Comment 7 Gavin Barraclough 2012-09-07 12:24:52 PDT
I don't think this bug is still relevant.