Skip to main content

RAP 18 Improved Ambiguous Tree Support

rascal-0.43.3
RAP18
TitleImproved Ambiguous Tree Support
AuthorDavy Landman, Jurgen Vinju, Pieter Olivier
StatusDraft
TypeRuntime System

Abstract​

The topic of RAP 16 (Error Tree Support) was how handle regular code that tries to access parts of error trees that are not present ("beyond the dot"). This RAP builds on this by adding support for better handling of ambiguous trees.

Motivation​

For a "real world" issue and caused by lack of support for ambiguous trees and discussion see: https://github.com/usethesource/rascal/issues/2579

Currently when code tries to access part of a tree but the tree is ambiguous, the interpreter throws a static error as if the error was caused by a compile time error, for example:

import ParseTree;
import vis::Text;
import IO;

syntax S = altA: O? A a | A a | altB: "b";
syntax A = "a";
syntax O = "o"?;
...
S s = parse(#S, "a", allowAmbiguity=true);
rascal>println(prettyTree(s));
❖
├─ S = A a
│ └─ A = "a"
└─ S = O? A a
├─ ❖
│ ├─ O?
│ └─ O?
│ └─ O = "o"?
│ └─ "o"?
└─ A = "a"

ok
rascal>println("a: <s.a>");
|prompt:///|(13,1,<1,13>,<1,14>): Undeclared field: a for Tree
Advice: |https://www.rascal-mpl.org/docs/Rascal/Errors/CompileTimeErrors/UndeclaredField|

But the underlying cause is actually a dynamic error: the tree happens to be an ambiguous tree so accessing a field does not make sense. Because static errors cannot be caught, there is no way for a developer to handle this situation without explicitly checking beforehand if a tree is an ambigous tree.

How to handle attempts at accessing subtrees of ambiguous trees​

There are a limited number of ways code can try to access or analyze subtrees of parse trees.

  • Checking if a field exists (tree has name, tree.name?)
  • Checking if a tree is generated by a certain labeled production (tree is label)
  • Named field access (tree.field)
  • Named field access with alternative (tree.name?alt)
  • Named field assignment (tree.field=subtree)
  • Indexed field access (tree[index])
  • Indexed field assignment (tree[index] = subtree)
  • Matching using concrete syntax ((Stat)\if \<Expr e> then \<StatList s>`)`

Not that tree level access (using /amb(_) matching for instance) is fully supported and often the only way to reliably deal with ambiguous trees currently.

Checking for field existence​

Field existance checks on an ambiguous tree should always return false. This is already the current behavior in the interpreter.

Checking if a tree is generated by a labeled production​

This should also return false when performed on an ambigous tree: the children of an ambiguous tree can be of different productions so there is no one labeled production. This is already the current behavior of the interpreter.

Named field access​

There is no sensible way to implement this so throwing an exception is the only solution. Currently the interpreter throws an static UndeclaredField error in this case.

We already solved an almost identical problem (access to non-existing subtrees) when working with error trees in RAP16. In that case the top-level node would be an error node and access could fail if a subtree "after the dot" was accessed. In that case a special ParseErrorRecovery exception was thrown when such an access was attempted. This allows the programmer to catch such exceptions at the level of abstraction where they can be handled instead of having to sprinkle the code with checks for error trees.

We propose to use the same approach here: throw a Ambiguity exception (analogous to the ParseErrorRecovery exception) when access to a field of a parse tree fails because the parse tree is ambiguous but it does not contain error trees.

Named field assignment​

This should also generate a Ambiguity exception. Currently it generates a NoSuchField exception in the interpreter, which is a dynamic exception so it can be caught. For consistency this should be turned into a Ambiguity exception.

Named field access with alternative​

When applied on an ambigous tree the alternative should be returned. This already works in the interpreter.

Indexed field access​

Indexed field access on an ambiguous tree should generate a Ambiguity exception.

This currently causes an internal error in the interpreter (caused by a Java UnsupportedOperationException).

Indexed field assignment​

Indexed field assignment on an ambiguous tree should generate an Ambiguity exception.

Indexed field assignment does not currently work in the interpreter at all.

Matching using concrete syntax​

Matching should fail on ambiguous trees but typed holes can match ambiguous trees. This already works in the interpreter. We do not have a way to explicitly match ambiguous trees.

Conclusions​

For the interpreter the following changes are needed:

  • tree.field should throw a Ambiguity exception instead of a static UndeclaredField error.
  • tree.field=subtree should throw a Ambiguity exception instead of a NoSuchField exception.
  • Named field access on ambiguous trees should throw a Ambiguity exception.
  • Named field assignment on ambiguous trees should throw a Ambiguity exception.
  • Indexed field access on ambiguous trees should throw a Ambiguity exception.
  • Indexed field assignment on ambiguous trees should throw a Ambiguity exception. This should probably wait until proper support for indexed field assignment in the interpreter is implemented.

Handle faulty access to ambiguous trees in backtracking contexts and generators​

Analogous to what whas discussed in RAP16, Ambiguity exceptions caused by ambiguous tree access should be propagated normally during backtracking and in generators.

Compatibility​

This proposal is backwards compatible in the sense that if code used to work without throwing static errors, it will continue to function but now throws a dynamic error. Try/catch blocks that happen to catch all exceptions will now also catch Ambiguity exceptions caused by access to an ambiguous tree.

Implementation​

We can follow exactly the same implementation path we did for the error recovery case. Start by writing tests and then add support to both the interpreter and compiler. Note that the implementation should be simpler for ambiguous trees than for error trees: for ambiguous trees all field access should result in an Ambiguity exception while for error trees only access to fields "after the dot" should fail with an ParseErrorRecovery exception.

Special handling of ambiguities on similar trees​

What if all alternatives do have a particular field? We could let field checks succeed in that case as that seems sound. But in practice we foresee this would cause confusion, because although all alternatives have a particular field, it is unclear which one to return on access so field access would still throw an exception. The same goes for ambiguities where all alternatives are generated by the same (labeled) production. Letting tree is label succeed will cause trouble later.

Use of the same exception for failures caused by ambiguous trees and error trees​

Error recovery often causes ambiguities even when the syntax does not normally allow ambigous trees. It might even be argued that ambiguous trees are a also produced by a specialized form of error recovery.

In practice we expect language designers to be interested in either error recovery trees or in the presence of 'true' ambiguities, so we opted to use different exceptions for these cases.