jashkenas/coffee-script — pull request #3042 by marchaefner (2013-06-21 02:41:19+00:00)
Title: Avoid excessive AST traversal in `updateLocationDataIfMissing`.

Fixes #2844 by not searching for missing `locationData` on nodes that (provably) have it already set.

The effect (on my humble computing machine):

$ cake bench $ cake bench
Lex 426 ms (28534 tokens) Lex 418 ms (28534 tokens)
Rewrite 775 ms (31761 tokens) ___\ Rewrite 644 ms (31761 tokens)
Parse 4946 ms / Parse 629 ms
Compile 717 ms (177853 chars) Compile 723 ms (177853 chars)
total 6864 ms total 2414 ms

Because the relevant code is somewhat complex, here's a lengthy discussion as to how everything works, what goes wrong and how this PR fixes it:

### `locationData` on AST nodes - Theory of Operation

AST nodes are constructed by:

* parser actions
* node constructors
* `If.addElse` via `@ensureBlock`
* compilation-methods of nodes

The `locationData` on AST nodes is set (solely) by the `updateLocationDataIfMissing` method which in turn is (only) invoked by the `addLocationDataFn` helper. The helper is used in parser actions implicitly for each action result or explicitly by `LOC`.

`updateLocationDataIfMissing` sets the `locationData` on a node and then recursively traverses down its child nodes. The latter ensures that all child nodes have their `locationData` set, allowing for simpler parser actions (not littered with `LOC` invocations).

### The speed bump

While the behaviour described above might seem innocuous, it means that for almost every production all subjacent AST fragments are wholly traversed, in search of a missing `locationData` attribute.

### Fixing it

This PR fixes one issue (see below) to ensure that for all nodes that have `locationData`, all of their child nodes do too. Thus `updateLocationDataIfMissing` only needs to operate on "location-less" nodes.

This is fairly simple: We don't need to care about nodes constructed during compilation at all (as they are not involved in any of this).

Almost all nodes constructed in parser actions and subsequently in constructors are (part of) the return value and will be processed by `LOC`/`addLocationDataFn`.

The only exception is the second `if` of `IfBlock ELSE IF ...` which is added to `IfBlock` via `If::addElse` which returns the (first) `IfBlock` (that already has a `locationData`). This is fixed by explicitly calling `LOC`.

`If::addElse` does also construct a `Block` node. Its `locationData` is now set to that of the wrapped `elseBody`. This is just for completeness sake, so that all AST nodes always have `locationData`.