Ts-morph: Change descendant traversal order

[dsherret]

Given the following tree:

SourceFile
  FunctionDec1
    Identifier1
    Block1
      FunctionDec2
        Identifier2
        Block2
      FunctionDec3
        Identifier3
        Block3
  EndOfFileToken

The current traversal order for methods like forEachDescendant and .getDescendants() is FunctionDec1, Identifier1, Block1, FunctionDec2, Identifier2, Block2, FunctionDec3, Identifier3, Block3, EndOfFileToken.

The problem with this traversal order is that when you remove say FunctionDec2 during the iteration (Identifier2 and Block2 are now forgotten), then you have to be sure to check node.wasForgotten() for every node to ensure you don't use a now forgotten node.

New Traversal Order

Instead of yielding the current node and then yielding the children, it would be the opposite: Identifier1, Identifier2, Block2, FunctionDec2, Identifier3, Block3, FunctionDec3, Block1, FunctionDec1, EndOfFileToken

With this order people won't have to bother checking .wasForgotten() and so there shouldn't be many surprises. Plus, this is the same order I go through the tree when implementing a custom transformer in the compiler api.

This affects all .forEachDescendant and .getDescendants()-like methods. Also ForEachDescendantTraversalControl#skip() would be removed.

[lazarljubenovic]

So changing it to post-order (children, then self), right?

I'm afraid for performance implications when iterating. Pre-order (self, then children) traversal is still very handy when examining the tree I think, especially with control methods like skip. I find it unnatural to search through a tree in a bottom-up fashion.

That said of course, I get the reasoning behind this. Indeed, when manipulating the tree you usually do it bottom-up.

So seems to me like both are still valid use cases; what do you think about keeping them both?

[dsherret]

@lazarljubenovic thanks for the feedback! Yes, exactly (preorder to postorder). I was so focused in to my transformation scenario that I didn't spend enough time thinking about analysis. Yes, definitely agree that we need both!

How about the following?

enum TreeOrder {
    Pre = "pre",
    Post = "post"
}

node.forEachDescendant((node, traversal) => {
    console.log(node.getText());
}, TreeOrder.Post);

node.getDescendantsOfKind(SyntaxKind.ClassDeclaration, TreeOrder.Post);

Pre

• Pros: Probably what people would expect by default. Not a breaking change.
• Cons: Leads to an error if someone manipulates a node.

Post

• Pros: Won't have a forgotten node error due to manipulation.
• Cons: Might be confusing because I feel like people would expect pre when analyzing. That could lead to a silent problem. Breaking change.

I'm thinking probably Pre should be the default to prevent a silent problem and if it ever throws due to a forgotten node when using forEachDescendant, it could recommend to people to supply Post.

Does that sound good? What do you think?

[dsherret]

I'll probably close this and implement #513 instead.

[lazarljubenovic]

I like the straight-forwardness of just telling the lib how to traverse the tree. Declarative and powerful, the best combination IMO :+1:

I'm wondering if it would be worth the trouble to overload the signature and do a run-time check of the argument type (because we can't have default parameter as first arg) in order to move the traversal ordering as the first argument.

node.forEachDescendant(TreeOrder.Post, (node, traversal) => {
    console.log(node.getText())
})

I just don't like how the lambda goes before the pre/post option. It kinda disappears next to the closing }). :thinking:

[dsherret]

Agree! Thanks, I updated the other issue.

Yeah, it's better for people to think about what kind of traversal they're going to be doing right at the start and when reading, to read that before they read the body.

Edit: Implementing #513 instead.