Notes on the new internal HILTI Spicy AST structure

AST type resolving

• All types are stored as explicit nodes inside the AST, and always returned as references to these nodes through accessors.
  • Shortcut: If an type corresponds directly to the type of a sub-node, the accessor can return the result of the corresponding sub-node's accessor. This must be done only if no further computation on the type to be returned is necessary (because our accessor has to return a reference to the type, and the current node will be const so that it can’t store any new nodes).
• If a type is unknown at first and to be computed by the Resolver, then the node will start out as type::auto_. type::isResolved() considers type::auto_ as unresolved.
  • If a type is definitely not resolvable to anything else, it’ll be set to type::unknown (which itself does count as a resolved type through type::isResolved(), so that we don’t loop).
• If an AST slot for a type is needed only sometimes, set it to node::none when unused.
• Finding type::unknown in the final AST is not necessarily an error. The validator needs to catch it where it is considered illegal.
• Finding a type::auto_ left in the final AST, is always an error. It means something was supposed to be resolved, but wasn’t.

Managing AST Cycles

• When walking the AST, we must avoid getting into cycles, because we then wouldn’t terminate the traversal. We do this as follows:
  • Generally we break cycles by storing a NodeRef to an existing Node instead of creating a new one. For example, expression::ResolvedID stores a reference to the expression that the ID lookup has returned.
  • For types this unfortunately often doesn’t work well because they are inherently cyclic so that essentially any non-atomic type would need to store references to its children. Then, however, we wouldn’t have a place to store the actual nodes anywhere. Therefore, we handle types differently: We allow to “prune” AST walking at types for which we don’t want (or can’t) traverse in depth. This works by calling type::pruneWalk(t) on a type T. The effect of that is that AST walking, when going down into the type, will stop there if that type also has a type ID associated with it (it's those that create the cycles). Note that we don’t just generally stop looking at all children because some visitors actually still need to see those types without type IDs (like the Spicy codegen swapping out units for structs). (AST debug dumps mark nodes that will not be traversed further with (prune).)

AST Meta Data

• All Declaration nodes receive a canonical ID that’s globally unique and stably across runs. This is assigned by the Normalizer pass.
• Global function declarations that implement struct methods will have their parent type set to that struct type.