"Except" does not work correctly with shared prefixes in nonterminals, leading to ambiguity

rodinaarssen commented 4 months ago

Describe the bug When nonterminals share prefixes, "except" does not work correctly.

To Reproduce

lexical S
    = A!c
    | C
    ;
lexical A
    = b: C B
    | c: C
    ;
lexical B = "b";
lexical C = "c";

rascal>parse(#S, "c")
Reloading module lang::visualfx::A
|TODO:///|: Ambiguity(
  |unknown:///|(0,1,<1,0>,<1,1>),
  "S",
  "c")
ok

Expected behavior There should be no ambiguity here. Adding () at the start of either constructor of A makes the problem go away, e.g.:

lexical A
    = b: C B
    | c: () C
    ;

Desktop (please complete the following information):

Context: VS Code
Rascal Version: 0.34.1

jurgenvinju commented 4 months ago

@arnoldlankamp this looks to be a prefix-sharing issue:

In the breaking grammar, the prefixes are equal, but only if you ignore the conditions on the first non-terminal C.
In the non-breaking grammar, the prefix sharing is broken due to the additional () in one of the alternatives.

Perhaps you could have a look; but if you don't have the time no worries. Groetjes!

arnoldlankamp commented 4 months ago

Interesting 🤔, I don't immediately see a way in which prefix-sharing and completion filters would be able to interact in this specific case, since the completion filter is not on any of the prefix-shared nodes, but on an indirectly related non-terminal, which is processed independently.

The cleanest way to check if this issue is indeed related to prefix-sharing is to disable this feature. Which can be done by changing this flag from true to false: https://github.com/usethesource/rascal/blob/8e0f7b2753dcde63b31c79d704d75d0e0eaa37b8/src/org/rascalmpl/parser/gtd/preprocessing/ExpectBuilder.java#L67 By adding a dummy symbol you're also effectively disabling prefix-sharing for a certain alternative, but also a introduce a potentially significant change to the order in which symbols are evaluated by the parser, which may lead to false positive test results. I'm not trying to imply this is what's going on right now, but it is something to consider.

If changing the above flag turns out to resolve the issue, you could even consider using it as a temporary patch and live with the associated performance hit until a proper fix arrives.

In any case, I'll have a look at the root cause of this issue when I have some time.

arnoldlankamp commented 4 months ago

I just wrote a test case and found out I misunderstood the problem and was testing the wrong thing 🤦‍♂️ .

This has something to do with labeled alternatives not being rejected. So the origin of this problem is somewhere in the ExpectBuilder, which handles the prefix merging.

I guess it's not correctly considering nesting restrictions in all cases.

At least I know where to look now 😅 .

arnoldlankamp commented 4 months ago

By the way if anyone could supply me with the generated parser for the given grammar (the Java file) that would save me some time, since I don't have Rascal installed on my laptop.

arnoldlankamp commented 4 months ago

The ExpectBuilder relies on the nesting restrictions implicitly, by assuming the ParserGenerator assigns stack nodes identifiers that take sharing permissibility into account (e.g.: that they are unique for alternatives with the same priority and partially overlapping prefixes).

This should be working as intended, for as far as I can see 🤔 . To say more I'll need to have a look at the generated parser code.

jurgenvinju commented 4 months ago

I'll post it here in a few minutes. Installing Rascal is easy from the VScode extensions view. Just search for Rascal and pick install.

jurgenvinju commented 4 months ago

package example;

import java.io.IOException;
import java.io.StringReader;

import io.usethesource.vallang.type.TypeFactory;
import io.usethesource.vallang.IConstructor;
import io.usethesource.vallang.ISourceLocation;
import io.usethesource.vallang.IValue;
import io.usethesource.vallang.IValueFactory;
import io.usethesource.vallang.exceptions.FactTypeUseException;
import io.usethesource.vallang.io.StandardTextReader;
import org.rascalmpl.parser.gtd.stack.*;
import org.rascalmpl.parser.gtd.stack.filter.*;
import org.rascalmpl.parser.gtd.stack.filter.follow.*;
import org.rascalmpl.parser.gtd.stack.filter.match.*;
import org.rascalmpl.parser.gtd.stack.filter.precede.*;
import org.rascalmpl.parser.gtd.preprocessing.ExpectBuilder;
import org.rascalmpl.parser.gtd.util.IntegerKeyedHashMap;
import org.rascalmpl.parser.gtd.util.IntegerList;
import org.rascalmpl.parser.gtd.util.IntegerMap;
import org.rascalmpl.values.ValueFactoryFactory;
import org.rascalmpl.values.RascalValueFactory;
import org.rascalmpl.values.parsetrees.ITree;

@SuppressWarnings("all")
public class S extends org.rascalmpl.parser.gtd.SGTDBF<IConstructor, ITree, ISourceLocation> {
  protected final static IValueFactory VF = ValueFactoryFactory.getValueFactory();

  protected static IValue _read(java.lang.String s, io.usethesource.vallang.type.Type type) {
    try {
      return new StandardTextReader().read(VF, org.rascalmpl.values.RascalValueFactory.uptr, type, new StringReader(s));
    }
    catch (FactTypeUseException e) {
      throw new RuntimeException("unexpected exception in generated parser", e);  
    } catch (IOException e) {
      throw new RuntimeException("unexpected exception in generated parser", e);  
    }
  }

  protected static java.lang.String _concat(java.lang.String ...args) {
    int length = 0;
    for (java.lang.String s :args) {
      length += s.length();
    }
    java.lang.StringBuilder b = new java.lang.StringBuilder(length);
    for (java.lang.String s : args) {
      b.append(s);
    }
    return b.toString();
  }
  protected static final TypeFactory _tf = TypeFactory.getInstance();

  private static final IntegerMap _resultStoreIdMappings;
  private static final IntegerKeyedHashMap<IntegerList> _dontNest;

  protected static void _putDontNest(IntegerKeyedHashMap<IntegerList> result, int parentId, int childId) {
    IntegerList donts = result.get(childId);
    if (donts == null) {
      donts = new IntegerList();
      result.put(childId, donts);
    }
    donts.add(parentId);
  }

  protected int getResultStoreId(int parentId) {
    return _resultStoreIdMappings.get(parentId);
  }

  protected static IntegerKeyedHashMap<IntegerList> _initDontNest() {
    IntegerKeyedHashMap<IntegerList> result = new IntegerKeyedHashMap<IntegerList>(); 

    _putDontNest(result, 100, 27);
   return result;
  }

  protected static IntegerMap _initDontNestGroups() {
    IntegerMap result = new IntegerMap();
    int resultStoreId = result.size();

    ++resultStoreId;

    result.putUnsafe(100, resultStoreId);

    return result;
  }

  protected boolean hasNestingRestrictions(java.lang.String name){
        return (_dontNest.size() != 0); // TODO Make more specific.
  }

  protected IntegerList getFilteredParents(int childId) {
        return _dontNest.get(childId);
  }

  // initialize priorities     
  static {
    _dontNest = _initDontNest();
    _resultStoreIdMappings = _initDontNestGroups();
  }

  // Production declarations

  private static final IConstructor cHJvZChsaXQoInNvcnQoXCJDXCIpIiksW1xjaGFyLWNsYXNzKFtyYW5nZSgxMTUsMTE1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTEsMTExKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTQsMTE0KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTYsMTE2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSg0MCw0MCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoMzQsMzQpXSksXGNoYXItY2xhc3MoW3JhbmdlKDY3LDY3KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgzNCwzNCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoNDEsNDEpXSldLHt9KQ0000 = (IConstructor) _read("prod(lit(\"sort(\\\"C\\\")\"),[\\char-class([range(115,115)]),\\char-class([range(111,111)]),\\char-class([range(114,114)]),\\char-class([range(116,116)]),\\char-class([range(40,40)]),\\char-class([range(34,34)]),\\char-class([range(67,67)]),\\char-class([range(34,34)]),\\char-class([range(41,41)])],{})", RascalValueFactory.Production);
  private static final IConstructor cmVndWxhcihpdGVyKFxjaGFyLWNsYXNzKFtyYW5nZSg0OCw1NyldKSkp = (IConstructor) _read("regular(iter(\\char-class([range(48,57)])))", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsaXQoIjoiKSxbXGNoYXItY2xhc3MoW3JhbmdlKDU4LDU4KV0pXSx7fSk00 = (IConstructor) _read("prod(lit(\":\"),[\\char-class([range(58,58)])],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChlbXB0eSgpLFtdLHt9KQ0000 = (IConstructor) _read("prod(empty(),[],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsYWJlbCgiYyIsbGV4KCJBIikpLFtsZXgoIkMiKV0se30p = (IConstructor) _read("prod(label(\"c\",lex(\"A\")),[lex(\"C\")],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsaXQoImMiKSxbXGNoYXItY2xhc3MoW3JhbmdlKDk5LDk5KV0pXSx7fSk00 = (IConstructor) _read("prod(lit(\"c\"),[\\char-class([range(99,99)])],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsYWJlbCgiYiIsbGV4KCJBIikpLFtsZXgoIkMiKSxsZXgoIkIiKV0se30p = (IConstructor) _read("prod(label(\"b\",lex(\"A\")),[lex(\"C\"),lex(\"B\")],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkMiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQ1wiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJDIikpKX0p = (IConstructor) _read("prod(label(\"$MetaHole\",lex(\"C\")),[\\char-class([range(0,0)]),lit(\"sort(\\\"C\\\")\"),lit(\":\"),iter(\\char-class([range(48,57)])),\\char-class([range(0,0)])],{tag(\"holeType\"(lex(\"C\")))})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkEiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQVwiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJBIikpKX0p = (IConstructor) _read("prod(label(\"$MetaHole\",lex(\"A\")),[\\char-class([range(0,0)]),lit(\"sort(\\\"A\\\")\"),lit(\":\"),iter(\\char-class([range(48,57)])),\\char-class([range(0,0)])],{tag(\"holeType\"(lex(\"A\")))})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsYXlvdXRzKCIkZGVmYXVsdCQiKSxbXSx7fSk00 = (IConstructor) _read("prod(layouts(\"$default$\"),[],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIlMiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiU1wiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJTIikpKX0p = (IConstructor) _read("prod(label(\"$MetaHole\",lex(\"S\")),[\\char-class([range(0,0)]),lit(\"sort(\\\"S\\\")\"),lit(\":\"),iter(\\char-class([range(48,57)])),\\char-class([range(0,0)])],{tag(\"holeType\"(lex(\"S\")))})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsaXQoInNvcnQoXCJCXCIpIiksW1xjaGFyLWNsYXNzKFtyYW5nZSgxMTUsMTE1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTEsMTExKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTQsMTE0KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTYsMTE2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSg0MCw0MCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoMzQsMzQpXSksXGNoYXItY2xhc3MoW3JhbmdlKDY2LDY2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgzNCwzNCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoNDEsNDEpXSldLHt9KQ0000 = (IConstructor) _read("prod(lit(\"sort(\\\"B\\\")\"),[\\char-class([range(115,115)]),\\char-class([range(111,111)]),\\char-class([range(114,114)]),\\char-class([range(116,116)]),\\char-class([range(40,40)]),\\char-class([range(34,34)]),\\char-class([range(66,66)]),\\char-class([range(34,34)]),\\char-class([range(41,41)])],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsaXQoImIiKSxbXGNoYXItY2xhc3MoW3JhbmdlKDk4LDk4KV0pXSx7fSk00 = (IConstructor) _read("prod(lit(\"b\"),[\\char-class([range(98,98)])],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsZXgoIlMiKSxbY29uZGl0aW9uYWwobGV4KCJBIikse2V4Y2VwdCgiYyIpfSldLHt9KQ0000 = (IConstructor) _read("prod(lex(\"S\"),[conditional(lex(\"A\"),{except(\"c\")})],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsaXQoInNvcnQoXCJBXCIpIiksW1xjaGFyLWNsYXNzKFtyYW5nZSgxMTUsMTE1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTEsMTExKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTQsMTE0KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTYsMTE2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSg0MCw0MCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoMzQsMzQpXSksXGNoYXItY2xhc3MoW3JhbmdlKDY1LDY1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgzNCwzNCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoNDEsNDEpXSldLHt9KQ0000 = (IConstructor) _read("prod(lit(\"sort(\\\"A\\\")\"),[\\char-class([range(115,115)]),\\char-class([range(111,111)]),\\char-class([range(114,114)]),\\char-class([range(116,116)]),\\char-class([range(40,40)]),\\char-class([range(34,34)]),\\char-class([range(65,65)]),\\char-class([range(34,34)]),\\char-class([range(41,41)])],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsaXQoInNvcnQoXCJTXCIpIiksW1xjaGFyLWNsYXNzKFtyYW5nZSgxMTUsMTE1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTEsMTExKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTQsMTE0KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTYsMTE2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSg0MCw0MCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoMzQsMzQpXSksXGNoYXItY2xhc3MoW3JhbmdlKDgzLDgzKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgzNCwzNCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoNDEsNDEpXSldLHt9KQ0000 = (IConstructor) _read("prod(lit(\"sort(\\\"S\\\")\"),[\\char-class([range(115,115)]),\\char-class([range(111,111)]),\\char-class([range(114,114)]),\\char-class([range(116,116)]),\\char-class([range(40,40)]),\\char-class([range(34,34)]),\\char-class([range(83,83)]),\\char-class([range(34,34)]),\\char-class([range(41,41)])],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsZXgoIkIiKSxbbGl0KCJiIildLHt9KQ0000 = (IConstructor) _read("prod(lex(\"B\"),[lit(\"b\")],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkIiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQlwiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJCIikpKX0p = (IConstructor) _read("prod(label(\"$MetaHole\",lex(\"B\")),[\\char-class([range(0,0)]),lit(\"sort(\\\"B\\\")\"),lit(\":\"),iter(\\char-class([range(48,57)])),\\char-class([range(0,0)])],{tag(\"holeType\"(lex(\"B\")))})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsZXgoIkMiKSxbbGl0KCJjIildLHt9KQ0000 = (IConstructor) _read("prod(lex(\"C\"),[lit(\"c\")],{})", RascalValueFactory.Production);
  private static final IConstructor cHJvZChsZXgoIlMiKSxbbGV4KCJDIildLHt9KQ0000 = (IConstructor) _read("prod(lex(\"S\"),[lex(\"C\")],{})", RascalValueFactory.Production);

  // Item declarations

  protected static class layouts_$default$ {
    public final static AbstractStackNode<IConstructor>[] EXPECTS;
    static{
      ExpectBuilder<IConstructor> builder = new ExpectBuilder<IConstructor>(_resultStoreIdMappings);
      init(builder);
      EXPECTS = builder.buildExpectArray();
    }

    protected static final void _init_cHJvZChsYXlvdXRzKCIkZGVmYXVsdCQiKSxbXSx7fSk00(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[1];

      tmp[0] = new EpsilonStackNode<IConstructor>(3, 0);
      builder.addAlternative(S.cHJvZChsYXlvdXRzKCIkZGVmYXVsdCQiKSxbXSx7fSk00, tmp);
    }
    public static void init(ExpectBuilder<IConstructor> builder){

        _init_cHJvZChsYXlvdXRzKCIkZGVmYXVsdCQiKSxbXSx7fSk00(builder);

    }
  }

  protected static class A {
    public final static AbstractStackNode<IConstructor>[] EXPECTS;
    static{
      ExpectBuilder<IConstructor> builder = new ExpectBuilder<IConstructor>(_resultStoreIdMappings);
      init(builder);
      EXPECTS = builder.buildExpectArray();
    }

    protected static final void _init_cHJvZChsYWJlbCgiYiIsbGV4KCJBIikpLFtsZXgoIkMiKSxsZXgoIkIiKV0se30p(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[2];

      tmp[1] = new NonTerminalStackNode<IConstructor>(15, 1, "B", null, null);
      tmp[0] = new NonTerminalStackNode<IConstructor>(14, 0, "C", null, null);
      builder.addAlternative(S.cHJvZChsYWJlbCgiYiIsbGV4KCJBIikpLFtsZXgoIkMiKSxsZXgoIkIiKV0se30p, tmp);
    }
    protected static final void _init_cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkEiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQVwiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJBIikpKX0p(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[5];

      tmp[3] = new ListStackNode<IConstructor>(22, 3, cmVndWxhcihpdGVyKFxjaGFyLWNsYXNzKFtyYW5nZSg0OCw1NyldKSkp, new CharStackNode<IConstructor>(21, 0, new int[][]{{48,57}}, null, null), true, null, null);
      tmp[1] = new LiteralStackNode<IConstructor>(19, 1, cHJvZChsaXQoInNvcnQoXCJBXCIpIiksW1xjaGFyLWNsYXNzKFtyYW5nZSgxMTUsMTE1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTEsMTExKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTQsMTE0KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTYsMTE2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSg0MCw0MCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoMzQsMzQpXSksXGNoYXItY2xhc3MoW3JhbmdlKDY1LDY1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgzNCwzNCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoNDEsNDEpXSldLHt9KQ0000, new int[] {115,111,114,116,40,34,65,34,41}, null, null);
      tmp[0] = new CharStackNode<IConstructor>(18, 0, new int[][]{{0,0}}, null, null);
      tmp[4] = new CharStackNode<IConstructor>(23, 4, new int[][]{{0,0}}, null, null);
      tmp[2] = new LiteralStackNode<IConstructor>(20, 2, cHJvZChsaXQoIjoiKSxbXGNoYXItY2xhc3MoW3JhbmdlKDU4LDU4KV0pXSx7fSk00, new int[] {58}, null, null);
      builder.addAlternative(S.cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkEiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQVwiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJBIikpKX0p, tmp);
    }
    protected static final void _init_cHJvZChsYWJlbCgiYyIsbGV4KCJBIikpLFtsZXgoIkMiKV0se30p(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[1];

      tmp[0] = new NonTerminalStackNode<IConstructor>(27, 0, "C", null, null);
      builder.addAlternative(S.cHJvZChsYWJlbCgiYyIsbGV4KCJBIikpLFtsZXgoIkMiKV0se30p, tmp);
    }
    public static void init(ExpectBuilder<IConstructor> builder){

        _init_cHJvZChsYWJlbCgiYiIsbGV4KCJBIikpLFtsZXgoIkMiKSxsZXgoIkIiKV0se30p(builder);

        _init_cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkEiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQVwiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJBIikpKX0p(builder);

        _init_cHJvZChsYWJlbCgiYyIsbGV4KCJBIikpLFtsZXgoIkMiKV0se30p(builder);

    }
  }

  protected static class C {
    public final static AbstractStackNode<IConstructor>[] EXPECTS;
    static{
      ExpectBuilder<IConstructor> builder = new ExpectBuilder<IConstructor>(_resultStoreIdMappings);
      init(builder);
      EXPECTS = builder.buildExpectArray();
    }

    protected static final void _init_cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkMiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQ1wiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJDIikpKX0p(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[5];

      tmp[3] = new ListStackNode<IConstructor>(35, 3, cmVndWxhcihpdGVyKFxjaGFyLWNsYXNzKFtyYW5nZSg0OCw1NyldKSkp, new CharStackNode<IConstructor>(34, 0, new int[][]{{48,57}}, null, null), true, null, null);
      tmp[1] = new LiteralStackNode<IConstructor>(32, 1, cHJvZChsaXQoInNvcnQoXCJDXCIpIiksW1xjaGFyLWNsYXNzKFtyYW5nZSgxMTUsMTE1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTEsMTExKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTQsMTE0KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTYsMTE2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSg0MCw0MCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoMzQsMzQpXSksXGNoYXItY2xhc3MoW3JhbmdlKDY3LDY3KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgzNCwzNCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoNDEsNDEpXSldLHt9KQ0000, new int[] {115,111,114,116,40,34,67,34,41}, null, null);
      tmp[0] = new CharStackNode<IConstructor>(31, 0, new int[][]{{0,0}}, null, null);
      tmp[4] = new CharStackNode<IConstructor>(36, 4, new int[][]{{0,0}}, null, null);
      tmp[2] = new LiteralStackNode<IConstructor>(33, 2, cHJvZChsaXQoIjoiKSxbXGNoYXItY2xhc3MoW3JhbmdlKDU4LDU4KV0pXSx7fSk00, new int[] {58}, null, null);
      builder.addAlternative(S.cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkMiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQ1wiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJDIikpKX0p, tmp);
    }
    protected static final void _init_cHJvZChsZXgoIkMiKSxbbGl0KCJjIildLHt9KQ0000(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[1];

      tmp[0] = new LiteralStackNode<IConstructor>(39, 0, cHJvZChsaXQoImMiKSxbXGNoYXItY2xhc3MoW3JhbmdlKDk5LDk5KV0pXSx7fSk00, new int[] {99}, null, null);
      builder.addAlternative(S.cHJvZChsZXgoIkMiKSxbbGl0KCJjIildLHt9KQ0000, tmp);
    }
    public static void init(ExpectBuilder<IConstructor> builder){

        _init_cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkMiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQ1wiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJDIikpKX0p(builder);

        _init_cHJvZChsZXgoIkMiKSxbbGl0KCJjIildLHt9KQ0000(builder);

    }
  }

  protected static class B {
    public final static AbstractStackNode<IConstructor>[] EXPECTS;
    static{
      ExpectBuilder<IConstructor> builder = new ExpectBuilder<IConstructor>(_resultStoreIdMappings);
      init(builder);
      EXPECTS = builder.buildExpectArray();
    }

    protected static final void _init_cHJvZChsZXgoIkIiKSxbbGl0KCJiIildLHt9KQ0000(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[1];

      tmp[0] = new LiteralStackNode<IConstructor>(42, 0, cHJvZChsaXQoImIiKSxbXGNoYXItY2xhc3MoW3JhbmdlKDk4LDk4KV0pXSx7fSk00, new int[] {98}, null, null);
      builder.addAlternative(S.cHJvZChsZXgoIkIiKSxbbGl0KCJiIildLHt9KQ0000, tmp);
    }
    protected static final void _init_cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkIiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQlwiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJCIikpKX0p(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[5];

      tmp[4] = new CharStackNode<IConstructor>(50, 4, new int[][]{{0,0}}, null, null);
      tmp[2] = new LiteralStackNode<IConstructor>(47, 2, cHJvZChsaXQoIjoiKSxbXGNoYXItY2xhc3MoW3JhbmdlKDU4LDU4KV0pXSx7fSk00, new int[] {58}, null, null);
      tmp[3] = new ListStackNode<IConstructor>(49, 3, cmVndWxhcihpdGVyKFxjaGFyLWNsYXNzKFtyYW5nZSg0OCw1NyldKSkp, new CharStackNode<IConstructor>(48, 0, new int[][]{{48,57}}, null, null), true, null, null);
      tmp[1] = new LiteralStackNode<IConstructor>(46, 1, cHJvZChsaXQoInNvcnQoXCJCXCIpIiksW1xjaGFyLWNsYXNzKFtyYW5nZSgxMTUsMTE1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTEsMTExKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTQsMTE0KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTYsMTE2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSg0MCw0MCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoMzQsMzQpXSksXGNoYXItY2xhc3MoW3JhbmdlKDY2LDY2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgzNCwzNCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoNDEsNDEpXSldLHt9KQ0000, new int[] {115,111,114,116,40,34,66,34,41}, null, null);
      tmp[0] = new CharStackNode<IConstructor>(45, 0, new int[][]{{0,0}}, null, null);
      builder.addAlternative(S.cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkIiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQlwiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJCIikpKX0p, tmp);
    }
    public static void init(ExpectBuilder<IConstructor> builder){

        _init_cHJvZChsZXgoIkIiKSxbbGl0KCJiIildLHt9KQ0000(builder);

        _init_cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIkIiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiQlwiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJCIikpKX0p(builder);

    }
  }

  protected static class S {
    public final static AbstractStackNode<IConstructor>[] EXPECTS;
    static{
      ExpectBuilder<IConstructor> builder = new ExpectBuilder<IConstructor>(_resultStoreIdMappings);
      init(builder);
      EXPECTS = builder.buildExpectArray();
    }

    protected static final void _init_cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIlMiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiU1wiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJTIikpKX0p(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[5];

      tmp[2] = new LiteralStackNode<IConstructor>(93, 2, cHJvZChsaXQoIjoiKSxbXGNoYXItY2xhc3MoW3JhbmdlKDU4LDU4KV0pXSx7fSk00, new int[] {58}, null, null);
      tmp[4] = new CharStackNode<IConstructor>(96, 4, new int[][]{{0,0}}, null, null);
      tmp[0] = new CharStackNode<IConstructor>(91, 0, new int[][]{{0,0}}, null, null);
      tmp[1] = new LiteralStackNode<IConstructor>(92, 1, cHJvZChsaXQoInNvcnQoXCJTXCIpIiksW1xjaGFyLWNsYXNzKFtyYW5nZSgxMTUsMTE1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTEsMTExKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTQsMTE0KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTYsMTE2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSg0MCw0MCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoMzQsMzQpXSksXGNoYXItY2xhc3MoW3JhbmdlKDgzLDgzKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgzNCwzNCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoNDEsNDEpXSldLHt9KQ0000, new int[] {115,111,114,116,40,34,83,34,41}, null, null);
      tmp[3] = new ListStackNode<IConstructor>(95, 3, cmVndWxhcihpdGVyKFxjaGFyLWNsYXNzKFtyYW5nZSg0OCw1NyldKSkp, new CharStackNode<IConstructor>(94, 0, new int[][]{{48,57}}, null, null), true, null, null);
      builder.addAlternative(S.cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIlMiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiU1wiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJTIikpKX0p, tmp);
    }
    protected static final void _init_cHJvZChsZXgoIlMiKSxbY29uZGl0aW9uYWwobGV4KCJBIikse2V4Y2VwdCgiYyIpfSldLHt9KQ0000(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[1];

      tmp[0] = new NonTerminalStackNode<IConstructor>(100, 0, "A", null, null);
      builder.addAlternative(S.cHJvZChsZXgoIlMiKSxbY29uZGl0aW9uYWwobGV4KCJBIikse2V4Y2VwdCgiYyIpfSldLHt9KQ0000, tmp);
    }
    protected static final void _init_cHJvZChsZXgoIlMiKSxbbGV4KCJDIildLHt9KQ0000(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[1];

      tmp[0] = new NonTerminalStackNode<IConstructor>(102, 0, "C", null, null);
      builder.addAlternative(S.cHJvZChsZXgoIlMiKSxbbGV4KCJDIildLHt9KQ0000, tmp);
    }
    public static void init(ExpectBuilder<IConstructor> builder){

        _init_cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIlMiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiU1wiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJTIikpKX0p(builder);

        _init_cHJvZChsZXgoIlMiKSxbY29uZGl0aW9uYWwobGV4KCJBIikse2V4Y2VwdCgiYyIpfSldLHt9KQ0000(builder);

        _init_cHJvZChsZXgoIlMiKSxbbGV4KCJDIildLHt9KQ0000(builder);

    }
  }

  // Parse methods    

  public AbstractStackNode<IConstructor>[] layouts_$default$() {
    return layouts_$default$.EXPECTS;
  }
  public AbstractStackNode<IConstructor>[] A() {
    return A.EXPECTS;
  }
  public AbstractStackNode<IConstructor>[] C() {
    return C.EXPECTS;
  }
  public AbstractStackNode<IConstructor>[] B() {
    return B.EXPECTS;
  }
  public AbstractStackNode<IConstructor>[] S() {
    return S.EXPECTS;
  }
}

This was generated using:

import lang::rascal::grammar::ParserGenerator;
import Grammar;
import IO;
writeFile(|home:///S.java|, newGenerate("example", "S", grammar(#S)));

jurgenvinju commented 4 months ago

Note to self and Arnold: this disambiguation filter is handled by the NoNesting relation and not by the enter and completion filters. Next to the forbidden nestings generated by the associativity and priority relations (which transitively closed), these ! annotations add single tuples to the NoNest relation.

We have _putDontNest(result, 100, 27); as the only tuple in this grammar.

100 is the A in this one prod(lex(\"S\"),[conditional(lex(\"A\"),{except(\"c\")})],{}) which is lexical S = A!c;
27 is the C in "prod(label(\"c\",lex(\"A\")),[lex(\"C\")],{})" which is lexical A = c:C;

The final symbol of each rule is always used to identify the rule:

rel[int,int] computeDontNests(Items items, Grammar grammar, Grammar uniqueGrammar) {
  // first we compute a map from productions to their last items (which identify each production)
  prodItems = (p:items[getType(rhs)][item(p,size(lhs)-1)].itemId | /Production p:prod(Symbol rhs,list[Symbol] lhs, _) := grammar);

It's unclear to me what happens with an epsilon rule that must be rejected.

arnoldlankamp commented 4 months ago

Thanks for the generated parser's code 👍 .

As far as I can see everything seems to be correctly generated. The ExpectBuilder definitely seems to most likely source of this bug. Probably because it's merging stack nodes without taking properly taking the nesting restrictions into account.

If so there are two possible ways of fixing this:

Prevent merging stack nodes that have nesting restrictions associated with them (only the last node of an alternative can have a nesting restriction associated with them, so any potential performance impact of such a change is limited). What is interesting about this is that I recall letting the last stack node of every alternative 'dangle' was actually part of the original prefix-sharing design to prevent problems like this 🤔 .
Update the set of nesting restrictions after merging a stack node with nesting restrictions associated with it. This is a bit more work to implement and would not always correctly resolve the hypothetical case where you have identical alternatives with different nesting restrictions (which could be considered user error, but we may as well prevent undefined outcomes, even in cases where users provide unexpected, but ultimately valid, input).

So I guess I'll go with the first option.

I'll let you know as soon as I've had some time to implement a solution.

jurgenvinju commented 4 months ago

Yes, let's go for the first. Of course, we still are working under hypotheses, but if that fixes it the hypotheses are confirmed :-) I'm happy we have good regression tests. Let's add this case to the manually written cases? Thanks for looking into this Arnold; you can do it 100x faster than I could.

arnoldlankamp commented 4 months ago

I already started writing a new test case on a branch a few days ago, since I need it to debug the issue anyway.

However it may be a few days until I get around to spending more time on this issue. I'll let you know when it's done.

jurgenvinju commented 4 months ago

Excellent!

arnoldlankamp commented 3 months ago

I just finished writing a new test case on a branch, which reproduces the issue.

I've also pinned down the problem to somewhere around here: https://github.com/usethesource/rascal/blob/52703208f6e58579efdb6d6a5ea32d8298408a1c/src/org/rascalmpl/parser/gtd/preprocessing/ExpectBuilder.java#L112-L113

It looks to be taking nesting restrictions into account while merging alternatives, but it's apparently missing one or more cases.

I'll try to find some time to have a better look at it next week. I know what the problem is and know what needs to be done to rectify it, but I don't want to rush out a fix today and potentially break something else in the process.

Until then, disabling prefix-sharing by setting: https://github.com/usethesource/rascal/blob/52703208f6e58579efdb6d6a5ea32d8298408a1c/src/org/rascalmpl/parser/gtd/preprocessing/ExpectBuilder.java#L67 to false, is still available as temporary workaround.

arnoldlankamp commented 3 months ago

@jurgenvinju By the way, I noticed these alternatives in the generated parser code you posted:

protected static final void _init_cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIlMiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiU1wiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJTIikpKX0p(ExpectBuilder<IConstructor> builder) {
      AbstractStackNode<IConstructor>[] tmp = (AbstractStackNode<IConstructor>[]) new AbstractStackNode[5];

      tmp[2] = new LiteralStackNode<IConstructor>(93, 2, cHJvZChsaXQoIjoiKSxbXGNoYXItY2xhc3MoW3JhbmdlKDU4LDU4KV0pXSx7fSk00, new int[] {58}, null, null);
      tmp[4] = new CharStackNode<IConstructor>(96, 4, new int[][]{{0,0}}, null, null);
      tmp[0] = new CharStackNode<IConstructor>(91, 0, new int[][]{{0,0}}, null, null);
      tmp[1] = new LiteralStackNode<IConstructor>(92, 1, cHJvZChsaXQoInNvcnQoXCJTXCIpIiksW1xjaGFyLWNsYXNzKFtyYW5nZSgxMTUsMTE1KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTEsMTExKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTQsMTE0KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgxMTYsMTE2KV0pLFxjaGFyLWNsYXNzKFtyYW5nZSg0MCw0MCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoMzQsMzQpXSksXGNoYXItY2xhc3MoW3JhbmdlKDgzLDgzKV0pLFxjaGFyLWNsYXNzKFtyYW5nZSgzNCwzNCldKSxcY2hhci1jbGFzcyhbcmFuZ2UoNDEsNDEpXSldLHt9KQ0000, new int[] {115,111,114,116,40,34,83,34,41}, null, null);
      tmp[3] = new ListStackNode<IConstructor>(95, 3, cmVndWxhcihpdGVyKFxjaGFyLWNsYXNzKFtyYW5nZSg0OCw1NyldKSkp, new CharStackNode<IConstructor>(94, 0, new int[][]{{48,57}}, null, null), true, null, null);
      builder.addAlternative(S.cHJvZChsYWJlbCgiJE1ldGFIb2xlIixsZXgoIlMiKSksW1xjaGFyLWNsYXNzKFtyYW5nZSgwLDApXSksbGl0KCJzb3J0KFwiU1wiKSIpLGxpdCgiOiIpLGl0ZXIoXGNoYXItY2xhc3MoW3JhbmdlKDQ4LDU3KV0pKSxcY2hhci1jbGFzcyhbcmFuZ2UoMCwwKV0pXSx7dGFnKCJob2xlVHlwZSIobGV4KCJTIikpKX0p, tmp);
  }

It looks like each sort has an extra alternative that looks like: [\0]sort{"S"}:[0-9]+[\0], where "S" is the name of the respective sort. These are unlikely to ever match anything, because they are delimited by null characters, so it doesn't look like something that should be there. Does this serve any purpose? This strikes me as old left over debugging code or something similar.

usethesource / rascal

"Except" does not work correctly with shared prefixes in nonterminals, leading to ambiguity #1915