Error tolerant ASTs in Kolasu 1.6

[ftomassetti]

When creating an AST we would like to support two use-cases that are difficult to reconcile:

• We would like to have type-checking ensuring that the AST is well-formed
• We would like to be able to work with partially incorrect ASTs

For example, we would like ASTs to be strictly defined:

class AdditionExpr(val left: Expr, val right: Expr) : Expr()

When writing an interpreter we want to be sure that left and right are present in each AdditionExpr, so that we can write code such as:

fun AdditionExpr.evaluta(symbolTable: SymbolTable) : Value = left.evaluate(symbolTable).add(right.evaluate(symbolTable))

On the other hand when parsing an incorrect piece of code we do not want to completely fail but to build a partial AST, which is still useful to support editors, to perform code analysis, etc. This would typically be done by making classes less strict:

class AdditionExpr(val left: Expr?, val right: Expr?) : Expr()

Which in turn requires to use nullability checks in all the places.

And what about assigning a left value to indicate that some Expr could ot be recognized? How could we represent that?

For this problem we looked into various alternatives, discussed today in the Tech Meeting:

• GenericErrorNodes, as implemented currently in Kolasu 1.5 by @alessiostalla
• Use Either from the Arrow library, as suggested by @loradd
• Use a compiler plugin to produce error classes to represented errors, as suggested by @ftomassetti
• Use DynamicNodes and fall back to them when one error is present in the AST, as suggested by @alessiostalla

Below the authors will illustrate their ideas so that we can discuss them and pick one solution

[ftomassetti]

I would consider solve this problem through a compiler plugin.

The rationale is that in Kolasu 1.6 we plan to use a compiler plugin for several features (observability of features, auto-setting parents, and possibly generating languages and concepts).

The idea is that, for each AST class we would create a corresponding Error class:

class ErrorAdditionExpr(message: String) : AdditionExpr(), Error(message)
   val left: Expr
       get() = throw InvalidASTException()
   val right: Expr
       get() = throw InvalidASTException()

We would be able to use the ErrorAdditionExpr whereever an AdditionExpr was present.

The advantage is that:

• When AST is correct, nothing would change for the user
• When some errors are present, we still get type-checking

The problem is that, if the AST is used without checking for errors we could get the InvalidASTException exception inadvertently.
However, when getting the AST, we could check if it contains any error:

fun Node.hasErrors() = myAst.walk<Error>.toList().isNotEmpty()

And based on that fact it has errors or not we could decide not to process the AST further with components that full expect a correct AST (for example an interpreter).

[loradd]

I like this approach! 👍

A couple of thoughts:

• How would this work with nodes defined as data classes (hence final) as we often do right now?

• Would these error nodes be available for the users to insert? For example, during a transformation to verify and possibly detect semantic issues on ASTs, could it be a good idea to allow users to instantiate such nodes? Or is this approach planned to cover syntactic issues only?

• Would the issues list continue to be part of the parsing result? Are these nodes going to replace it?

[ftomassetti]

Good questions.

For data classes:

• If the compiler plugin can anyway extend the class, ignoring the fact that data classes should not be extended, then we will do that
• Otherwise we either force users not to use data classes (we will generate a compiler error), but we will still generate hashcode and equals methods for them through the compiler plugin, as if they were data classes, just not final

For the error nodes, yes, users would be able to insert them, but they should be used to represent catastophic errors that prevent a piece of the AST to exist. When we can build an AST despite the errors we can still build it and add issues as needed. So these error nodes would complement issues and not replace them.