Designing a maintainable class hierarchy for representation of ASTs

Question

I need to design an AST-like class hierarchy for the introspection of code (like the Java Element API used during annotation processing). But I'm unsure how to make it maintainable and easy to use.

My instinct is to model the language as closely as possible and take full advantage of the type system. In order to do this, I would use inheritance to model the intuitive "is a"-relationship between syntax elements to get exhaustion checks in switch-expressions. I.e. MethodElements and ConstructorElements are ExecutableElements, TypeAliasElements, ClassElements and InterfaceElements are TypeElements and so on. This leads to quite a deep class hierarchy.

However, shared behaviour doesn't respect this hierarchy. For example: PackageElements, ClassElements and InterfaceElements can enclose other elements. But PackageElements only ever enclose other PackageElements or TypeElements and only ClassElements ever enclose ConstructorElements. Mixin-interfaces in combination with delegates for the implementation can be used to share behaviour between the classes. Still, it gets complex very quickly with deep class hierarchies and many mixin interfaces. Should there be a single interface for elements that are able to enclose other elements? Or an interface for being able to enclose packages, another interface for being able to enclose types, another one for enclosing functions etc. Should there be separate properties for visibility and modality or simply one that contains all applicable modifiers?

The opposite approach (the one chosen by the Java Element API) is to make the hierarchy flat with less specific interfaces: All classes implement the getEnclosedElements: List<Element> function, with those elements that don't enclose anything simply returning an empty list. Similarly there aren't different types for classes and interfaces. They are just grouped together under TypeElement with an enum property that specifies which kind it really is. Of course that makes everything much simpler for me, but it's not obvious to the user from the interface alone which classes may enclose which kinds of other elements, so users have to read API documentation much more often and their code is less safe.

Which approach is preferable here? I'm afraid that the deep class hierarchies will make the API undiscoverable, hard to maintain (because so many mixins are necessary to share behaviour between similar classes) and annoying to use. For example: The user may want to write a function to print all the members of a ClassElement or InterfacElement. They can not use the EnclosesElements interface because a PackageElement also encloses elements and also can not use the TypeElement base class because that includes TypeAliasElement which never encloses members. There is no interface or base class that includes just InterfaceElement and ClassElement.

Answer 1

Its about balance.

Encoding more of the Client Language in the Type Model of the Host Language will enforce Host Code to play nice with the Client Languages. It will also be a source of complexity as the Host Code must be tested and extended compatibly with the Client Language.

Encoding less information about the Client Language in the Host Language will open up opportunities for the Host Code to misuse the Client Language. It will also make implementing multiple client languages, including any proprietary extensions easier. It will allow a more modular design, improve reuse, and reduce duplication.

My question would be how are you using this AST? Is it aimed at:

• providing a DSL within the Host Language - then prefer the complex type information as the code is written in the Host Language. It is compiled alongside the Host Code and can be broadly presumed to be fixed at this point. Getting compilation errors, and providing stack traceability is the best approach for debugging, and long-term maintenance.
• providing a Host scripting feature to allow after-compilation behaviour modifications. In this case lean on the type system to make it easy to incorporate data and functions written within the Host language to be used by the script, and conversely provide types that easily adapt Client languages functions and data for use by the Host Language. A few common types and function signatures should be sufficient, but see what works. You won't be able to avoid run-time checking and errors entirely, particularly where the Host and Client language have different semantics.
• providing a compiler or interpreter. Prefer simpler, generic implementations. In this case the Host Language does not care to integrate with the Client language, so keeping it simpler makes it both quicker, and more flexible. These solutions also don't tend to stop with an AST but further optimise, simplify, and compile the Client code. So having a complicated AST has dubious benefits, and definitive costs. You would do better to provide services such as interactive debugging, JIT, and trans-piling.