Investigate Roslyn's Red-Green trees.

[eddyb]

https://github.com/KirillOsenkov/Bliki/wiki/Roslyn-Immutable-Trees

Incidentally, the children in our SPPF are encoded like a green tree (i.e. relative splits within the parent), it's just the "identity" of the nodes that includes their absolute range.

We could be allocating SPPF "green" nodes sequentially, and even deduplicate them after parsing (online deduplication seems... hard?), although that might be trickier after #9.

But for #12 (incremental reparsing) we'd still have to renumber the SPPF absolute ranges themselves, as we don't have a bottom-up parser, so we wouldn't gain anything from the indirection.
(And I'm not even sure we need any sort of "identity")

[brendanzab]

Also worth checking out:

• https://github.com/apple/swift/tree/master/lib/Syntax
• https://github.com/rust-analyzer/rowan