Allow overriding context

[ardera]

Some languages require more extensive context to parse correctly. For example in C, this example should produce different AST depending on whether a is a type or a variable:

void something() {
    a * b;
}

If a is a type, this is a variable declaration of variable b with type a*. If a is a variable name, this is an expression that multiplies a with b.

How should this kind of context be tracked? My idea would be to implement a custom Context that tracks declared variables and types, i.e.:

class CContext implements Context {
  const CContext(
    this.buffer,
    this.position, {
    required this.typeNames,
    required this.variableNames,
  });

  const CContext.empty(
    this.buffer,
    this.position
  ) : typeNames = const [],
      variableNames = const [];

  final List<String> typeNames;
  final List<String> variableNames;

  @override
  final String buffer;

  @override
  final int position;

  @override
  CFailure<R> failure<R>(String message, [int? position]) {
    return CFailure(
      buffer,
      position ?? this.position,
      message,
      typeNames: typeNames,
      variableNames: variableNames,
    );
  }

  @override
  CSuccess<R> success<R>(R result, [int? position]) {
    return CSuccess(
      buffer,
      position ?? this.position,
      result,
      typeNames,
      variableNames,
    );
  }

  CContext defineType(String name) {
    return CContext(
      buffer, position,
      typeNames: List.unmodifiable(typeNames.followedBy([name])),
      variableNames: variableNames
    );
  }

  CContext defineVariable(String name) {
    return CContext(
      buffer, position,
      typeNames: typeNames,
      variableNames: List.unmodifiable(variableNames.followedBy([name]))
    );
  }

  @override
  String toPositionString() => Token.positionString(buffer, position);

  @override
  String toString() => 'FileContext[${toPositionString()}]';
}

abstract class CResult<R> extends Context implements Result<R> {
 // ...
}

class CSuccess<R> extends CResult<R> implements Success<R> {
  // ...
}

class CFailure<R> extends CResult<R> implements Failure<R> {
  // ...
}

and then instead parse like this:

class MyCParserDefinition extends GrammarDefinition {
  // ... other rules here
  
  // A typedef statement
  // Will add the typedef to the context on success
  Parser typedef() => typedefToken() & typeName().callCC((continuation, context) {
    final result = continuation(context);
    if (result case CSuccess<String>(:final value, :final position) {
      return result.defineType(value).success(value, position);
    } else {
      return result;
    }
  });
}

final definition = MyCParserDefinition();
final parser = definition.buildFrom(definition.start());
final result = parser.parseOn(CContext.empty(source, 0));

However, it seems like that doesn't work, as there's multiple places where a parser will just create a new Context from scratch reintroduce that into the parsing:

1. fastParseOn will apparently always create a new context from scratch:

   dart-petitparser/lib/src/core/parser.dart

   Lines 32 to 35 in 235fd02

   	int fastParseOn(String buffer, int position) {
   	final result = parseOn(Context(buffer, position));
   	return result.isSuccess ? result.position : -1;
   	}

2. MatchesIterator.parseOn:

   dart-petitparser/lib/src/matcher/matches/matches_iterator.dart

   Lines 17 to 33 in 235fd02

   	bool moveNext() {
   	while (start <= input.length) {
   	final end = parser.fastParseOn(input, start);
   	if (end < 0) {
   	start++;
   	} else {
   	current = parser.parseOn(Context(input, start)).value;
   	if (overlapping || start == end) {
   	start++;
   	} else {
   	start = end;
   	}
   	return true;
   	}
   	}
   	return false;
   	}

3. TrimmingParser will create a new context from scratch:

   dart-petitparser/lib/src/parser/action/trimming.dart

   Lines 38 to 50 in 235fd02

   	Result<R> parseOn(Context context) {
   	final buffer = context.buffer;
   	final before = _trim(left, buffer, context.position);
   	if (before != context.position) {
   	context = Context(buffer, before);
   	}
   	final result = delegate.parseOn(context);
   	if (result.isFailure) return result;
   	final after = _trim(right, buffer, result.position);
   	return after == result.position
   	? result
   	: result.success(result.value, after);
   	}

Is this even the right way to use the Context? Should I do it completely differently for context-aware parsing? Should I just try to avoid fastParseOn and MatchesIterator & TrimmingParser? (I don't even know when fastParseOn will be called instead of parseOn)

[renggli]

I don't think passing typeNames and variableNames in the context will work, or you will also somehow need to maintain it correctly through backtracking. I think the easiest is if you build the AST using multiplications (or a special other node), and then after parsing / during type analysis you convert to the final form.

[ardera]

Thanks! I see. It's not just this specific case though, there's many variants like this where the concrete AST depends on type info:

a * (*b) (c, d, f);

(either a variable declaration, a multiplication of a with a comma operator expression casted to b*, or a multiplication of a with function *b called with args c, d, f)

I don't know how many other special cases there are, probably more. Basically this means you have to fall back to emitting tokens as soon as you see a *, until you see a ;, and then build a separate parser that constructs AST from tokens instead of strings.

Is there really no way to get that context method to work? Idk it seems to me that would be the cleaner solution (if there even is a clean way to parse C)

Btw I really appreciate your work on this package. I think it's really useful and well designed.

[renggli]

A possible workaround is to introduce side-effects, like the indent parser does on line 42:

dart-petitparser/lib/src/indent/indent.dart

Lines 38 to 44 in 235fd02

	late Parser<String> increase = parser
	.plusString(message)
	.where((value) => value.length > current.length)
	.map((value) {
	stack.add(current);
	return current = value;
	}, hasSideEffects: true).and();

In your example you would have the fields typeNames and variableNames in MyCParserDefinition, and maintain their state in .map((value) => ..., hasSideEffects: true) mapping functions. Setting hasSideEffects is important, as otherwise the execution of the callback is skipped if the result is not used.

It will be tricky to get everything right and a bit ugly to loose the functional properties of the parser. For example, you need to somehow manage the scope of your variables. However, this might be easier than rewriting the AST in your case?

[ardera]

Right, yeah that's a good solution.

Another idea I came up with (just for completeness) is just producing both AST nodes, one for the case where a is a type and one where a is a variable, and then deciding which one to use once you have the type information. Though that's basically twice as much parsing work