Make the compiler use a Packed AST (PAST) internally

[Araq]

See the code in compiler/past.nim and compiler/bitabs.nim for a rather precise outline of the structure. The plan is to use NimTree throughout the compiler which is a linearized representation of the AST that only supports in-place mutation in strategic places. In order to support Nim's VM / macro system there will be two operations:

proc fromTree(t: NimTree): PNode
proc toTree(n: PNode): NimTree

Instead of mutating an AST, you create a fresh one. The number of allocations is very low because a full tree is essentially stored as a single string/blob in memory.

[disruptek]

Are these files in a branch somewhere?

[disruptek]

Oh, I'm an idiot. 😆

[timotheecour]

I like #6 a lot because it goes in the right direction, has clear benefits and the complexity is worth the cost; but I don't think that's the case here.

IMO this is a case of premature optimization that not only will add a lot of complexity + bugs (eg code that needs mutation) but, in the end, may end up being slower (when you're forced to copy a subtree instead of mutating an inner node). Analogy with packedjson falls short (lots of mutations/transformations happen during compilation) and I can think of other ways to optimize performance that are less disruptive.

In any case, it'd need some POC with profiling.

[Araq]

I can think of other ways to optimize performance that are less disruptive.
In any case, it'd need some POC with profiling.

Maybe, but the idea is also to have a cleaner API so that we can change the representation easily. Then the representation can be picked that gives us the most performance. The Packed AST design enforces an API that supports packed ASTs, usually abstract APIs not written with this structure in mind don't support it at all.