Type.match and Type.instantiate for NonTerminalType

[jurgenvinju]

Trying to implement Type.match and Type.instantiate for NonTerminalType such that pattern matching works for types like {&T &E}* and &O?

• If that works, then generic library functions like sort, size, zip and reverse can be written for syntax lists
• Generally some things become simpler for concrete syntax analysis which are now "given" for abstract syntax and abstract lists.
• It's a big step towards finishing the concrete syntax features.
• Most complex code written for this works both for the interpreter and the compiled run-time as it is a part of the run-time type system of Rascal parse trees.

[jurgenvinju]

Currently "everything" is implemented but I managed to break the parser generator. In particular the code that uses abstract patterns to match against concrete trees is now broken.

[jurgenvinju]

The current milestones for this branch are:

• [x] do not break existing code
• [x] make this work: int size({&Elem &Sep}* l) = (0 | it + 1 | _ <- l);

[codecov[bot]]

Codecov Report

Merging #1844 (47fb001) into main (22a2833) will decrease coverage by 1%. The diff coverage is 19%.

@@           Coverage Diff            @@
##              main   #1844    +/-   ##
========================================
- Coverage       49%     48%    -1%     
- Complexity    6091    6138    +47     
========================================
  Files          670     670            
  Lines        58698   58881   +183     
  Branches      8544    8603    +59     
========================================
+ Hits         28792   28825    +33     
- Misses       27729   27828    +99     
- Partials      2177    2228    +51     

Impacted Files	Coverage Δ
src/org/rascalmpl/types/RascalType.java	20% <ø> (ø)
...org/rascalmpl/values/parsetrees/SymbolAdapter.java	25% <17%> (-3%)	:arrow_down:
src/org/rascalmpl/types/NonTerminalType.java	52% <62%> (+<1%)	:arrow_up:

... and 9 files with indirect coverage changes

[jurgenvinju]

Next steps before this can be merged:

• [ ] write some tests
• [ ] add several useful generic syntax list functions to List: size, zip, reverse, unzip

[jurgenvinju]

#1835 is now needed to finish this work correctly. Consider:

syntax X = A*;
lexical B = A*;
lexical A = "a"
layout W = [ ]*;

Now we have two A* types in the grammar, one of which becomes a separated list: {A W}* and the other remains A*.

Then:

A* f(A* x) is ambiguous. It could either be the lexical or the syntax list!

• it can't be both because of Liskov's substitution principle; by accepting both, either could come out again, which would be type-incorrect.
• We need to know which it is.

In #1835 we propose to have syntax[...] and lexical[...] "syntax role modifiers" which would be exactly right in this case. We would leave the default on syntax and then we'd write:

A* f(A* l) = ... ; // for the syntax case, which will match on the separated layout list
lex[A*] f(lex[A*] l) = ... // for the lexical case

More importantly, generic functions can that also be disambiguated:

int size(&T* l) = ...
int size(lex[&T*] l) = ...
int reverse(lex[{&Elem &Sep}+]) = ...

Albeit a bit of a mouthful, I don't see another way. We need to specify which syntax role lists and generic lists have if we want some level of type correctness.

[jurgenvinju]

@PaulKlint I will try and finish this in the coming days. I don't think it's relevant for you (except if I break things) in the short run, but it would be good if you read along with this in order to predict necessary fixes for the checker or compiler later. This is used to be a blind spot in our typing rules: i.e. what about {&T &U}* ?

This stuff is necessary to make the code around concrete syntax for external parsers work smoothly. Otherwise, we'll have to write a lot more code in Java, which I'm trying to avoid.