Proposal: defer rule listener calls until after traversal is complete

[not-an-aardvark]

For a long time, rules have had a slight usability issue where the parent property of a node is only present after a node is traversed and its listeners have been invoked. This can lead to confusing issues (e.g. #9101) where a function call on a node can change behavior depending on whether the node has been traversed.

Previously, there has been discussion about adding the parent property during the scope analysis traversal (eslint/eslint-scope#27). However, I realized there's a much easier solution: We can just defer all rule listener calls until after traversal is complete.

The current traversal logic looks roughly like this (pseudocode):

for each node in the AST in traversal order:
    node.parent = parentNode
    for each rule listener that matches the node:
        invoke the listener on the node

We could change it to this:

for each node in the AST in traversal order:
    node.parent = parentNode
    for each rule listener that matches the node:
        push (listener, node) into a FIFO queue

for each (listener, node) pair in the queue:
    invoke the listener on the node

The effect is that all parent properties would be present for all rule listeners.

We would need to evaluate the performance effects of doing this. I suspect that most of the time spent traversing the AST is a result of enumerating the children of a node, so after all the nodes have already been enumerated in order, I don't think invoking a function on a small fraction of the nodes will create a big performance problem. (Actually, this might allow us to move scope analysis into the same traversal too, since rules wouldn't be able to observe the scope until the traversal is complete.)

Note that rules can observe the AST before traversal starts, so they would still be able to observe nodes without a parent property. (edit: actually, this can be avoided.)

[not-an-aardvark]

TSC Summary: This issue proposes updating traversal logic to call rule listeners after all nodes have a parent property. This is intended to prevent rules from having confusing issues where only some nodes have a parent property. There is no compatibility impact, and based on an implementation locally, there is no noticeable performance impact.
TSC Question: Should we accept this proposal?

[platinumazure]

How does memory consumption look with your local implementation?

[not-an-aardvark]

I'm unsure of the best way to measure memory consumption precisely, but if you tell me a good way then I can try it out. Alternatively, I pushed up my implementation in 92bedb8, so feel free to test that out if you'd like.

My guess is that memory consumption is not affected very much (we create an additional array with length equal to twice the number of nodes in the AST, but that's fairly small in comparison to e.g. the token arrays that we already use).

[not-an-aardvark]

This was accepted in today's TSC meeting.

[not-an-aardvark]

Reopening because this change was reverted to fix #9331.

[not-an-aardvark]

TSC Summary: This issue proposes updating traversal logic to call rule listeners after all nodes have a parent property. The issue was previously accepted by the TSC, but it was reverted because there was some compatibility impact (a plugin was relying on the fact that the AST is non-circular, and another plugin was relying on the parent property not existing in some cases).

TSC Question: Should we schedule this as a breaking change in v5.0.0?

[not-an-aardvark]

In today's TSC meeting, the TSC decided to accept this as a breaking change for 5.0.