Add lookahead operators (lookAhead / notFollowedBy)

[ogregoire]

Proposal

Add two zero-width operators that match against the upcoming input without consuming it:

public static Parser<Void>.OrEmpty lookAhead(Parser<?> inner);
public static Parser<Void>.OrEmpty notFollowedBy(Parser<?> inner);

Both return OrEmpty so they inherit dot-parse's existing zero-width safety: composing them in repetitions (atLeastOnce, zeroOrMore) or self-references (Parser.Rule) is a compile error, exactly as it is for optional() / orElse().

Why

Some grammar rules genuinely depend on what follows the current position. Example: a verb's meaning differs based on whether a particular continuation comes after it. The natural expression is:

phrase("verb").then(BODY).followedBy(lookAhead(phrase(". If")))
        .map(MeaningA::new)

Today, with no lookahead, authors must approximate the rule by filtering on the parsed value:

phrase("verb").then(BODY.suchThat(MEANING_A_FILTER, "meaning-A shape"))
        .map(MeaningA::new)

suchThat only sees the parser's output, not the input that follows, so the filter encodes a heuristic rather than the actual rule. The two correlate but aren't equivalent — silent correctness gaps appear when ambiguous shapes occur in continuations they shouldn't, or when unambiguous shapes occur without the expected continuation.

The same gap shows up when disambiguating overlapping vocabularies: today, dispatch order plus result-shape filters substitute for a "this arm requires X to follow" assertion, which scales poorly and forces every contributor to learn an implicit ordering invariant.

Compatibility with the no-zero-width philosophy

dot-parse's safety contract is "no zero-width parsers in unsafe positions," enforced by the OrEmpty type system. Lookahead is inherently zero-width, so naïve composition would introduce the same pathology already guarded against:

lookAhead(p).atLeastOnce()                       // would loop
expr.definedAs(lookAhead(expr).then(body))       // would recurse without progress

The fix is the same fix dot-parse already uses: lookAhead and notFollowedBy return Parser.OrEmpty<Void>, inheriting every existing restriction. The compiler rejects unsafe composition exactly as it does for optional().atLeastOnce() today. No new class of pathology is introduced — a new operator slots into the existing safety machinery.

Why not suchThat or flatMap workarounds

• suchThat(predicate, name): operates on the parsed value, not on what follows. Cannot express continuation-dependent rules without re-encoding them as heuristics.
• Manual position-tracking via flatMap: requires first-class position handles and rewind primitives that dot-parse doesn't expose, and would smuggle backtracking into a library that deliberately avoids it.
• Phrase-template inflections (phrase("verb(s)")): work for one-token suffixes only.

API references

Lookahead is a baseline feature in essentially every parser-combinator library: PEG (&p, !p), Megaparsec / parsec (lookAhead, notFollowedBy), scala-parser-combinators (&, not), nom (peek, not).

---

Note: this was flagged by my agent as the 2nd most important friction it has when writing parsers. The first being sequence(OrEmpty,Parser).

[fluentfuture]

Note that we already have .notFollowedBy(String) and .notFollowedBy(Parser).

The way it remains compatible with the current must-consume invariant is such that it's attached to an existing Parser.

There is not a positive lookahead yet as I haven't run into a need myself. I can imagine positive lookahead being useful but a real use case can help guide us in naming it not very academic (i.e. notFollowedBy() instead of negativeLookahead()).

A confusion point we need to carefully work around is that there is already .followedBy(), which isn't a lookahead. So how do we name it so that it doesn't make .followedBy() look weird?

Thanks for giving an example. Can you go into a bit more contexts about this use case? I still don't quite understand it.

[ogregoire]

Note that there is .notFollowedBy(String) and .notFollowedBy(Parser).

Yeah, those have been super useful — I use them a lot. The negative version handles maybe 80% of what I need.

A confusion point we need to carefully work around is that there is already .followedBy(), which isn't a lookahead. So how do we name it so that it doesn't make .followedBy() look weird?

Honestly, the simplest thing might be to skip the attached form entirely and just add a static lookAhead(p):

public static Parser<Void>.OrEmpty lookAhead(Parser<?> inner);

Then nothing about .followedBy() changes, and you'd just write:

parser.followedBy(lookAhead(p))
lookAhead(p).then(parser)

If you ever want an attached version later, something like .requireFollowing(p) or .expecting(p) would read clearly different from the consuming .followedBy(p). But I think you can punt on that until someone actually needs it.

Can you go into a bit more contexts about this use case?

Sure — let me try with a really simple example.

Say I'm parsing little English-ish sentences:

I eat an apple.
I eat an apple, then I drink water.

The first is just a bare action. The second is "an action, plus a continuation rider that says what I do next." When the parser sees "I eat an apple," I want to attach the ", then I drink water" as a rider on the first action — but only if it's actually there. If the input is just "I eat an apple." with nothing after, the action stands alone.

Now here's the catch: ", then I drink water" is also a perfectly valid free-standing sentence somewhere else in the grammar (it's just another action). So the action parser can't always grab the "then" — sometimes it belongs to whatever's parsing the list of sentences at the outer level.

What I want to write is basically: "parse the action, and if a , then follows, also grab the rider — but don't consume the , then if no rider is going to come."

// What I want:
ACTION.optionallyFollowedBy(
    lookAhead(string(", then")).then(RIDER),
    Action::withRider)

Without lookahead I end up doing one of:

1. Parse the action, then try to parse the rider, and if it fails, backtrack — except dot-parse doesn't really do backtracking, so this gets awkward.
2. Always parse "action [+ optional rider]" greedily, and then hope the outer list parser figures it out. This breaks because the outer parser was counting on the "then" being there for it.
3. Parse everything flat and figure out the structure afterward in a second pass. Works, but now the parse tree doesn't match the grammar I'm trying to express.

Same kind of thing comes up with: "I eat an apple" vs "I eat an apple if I'm hungry" — where "if I'm hungry" attaches to the eating, but "If I'm hungry, I eat an apple" is also a valid sentence with the if clause at the front. The action parser needs to know whether if is coming up before deciding whether to grab it.

That's pretty much it. Just "let me peek without eating" so I can decide whether the next bit belongs to me or to the parser one level up.

[fluentfuture]

About that code example:

ACTION.optionallyFollowedBy(
    lookAhead(string(", then")).then(RIDER),
    Action::withRider)

I'd just use:

ACTION.optionallyFollowedBy(
    string(", then").then(RIDER),
    Action::withRider)

What doesn't work in this no-lookahead version?

EDIT: perhaps the RIDER parser needs to see the ", then" prefix?

But if so, why not just:

ACTION.optionallyFollowedBy(RIDER, Action::withRider)

?

[fluentfuture]

Honestly, the simplest thing might be to skip the attached form entirely and just add a static lookAhead(p):

I want to reply to this because it actually touches on one of the most fundamental design philosophy differences in Dot Parse compared to other combinator frameworks.

In Dot Parse, there is no standalone zero-width lookahead combinators, not even as OrEmpty type. And it's the key invariant that enables left recursion detectability at parser definition time.

That is, before a Rule can be chained up recursively through the define() or definedAs(target) methods, it performs a dry-run using target.matches(""). If target is left recursive (say, it's defined directly as sequence(me, foo), or indirectly as sequence(fooThatMayBeEmpty, me)), matches("") must throw an IllegalStateException before Dot-Parse allows the recursive parser to be created.

Critically, this check must be unconditional. That is, even if left recursion only happens with a particular input, ISE must be thrown during dry run to make sure there is no surprise in production.

Direct left recursion (sequence(me, foo)) is easy, as soon as me is evaluated, reentry at index 0 is a reliable signal for left recursion.

Indirect left recursion (define(me -> sequence(foo, me))) otoh is more difficult: if foo can ever match empty at all, we need to ensure that foo must succeed during dry run in order for me to be evaluated (and then throw).

If foo is a Parser, it always consumes, so me will not be evaluated, and it correctly proves that there's no left recursion.

If foo is an OrEmpty, by knowing that all OrEmpty will always succeed on empty, me will be evaluated and thus throw.

Had Dot Parse allowed for example Parser.notEof() as a standalone conditional OrEmpty, you'd have been able to write sequence(notEof(), me), and it will defeat the match("") dry run because notEof() would fail to match and thus me will be shortcircuited -> the dry run does nothing. Later in production, when you feed it non-empty input, boom, left recursion causes StackOverflowError.

In all the combinator frameworks that allow these flexible standalone lookaheads, few protects against infinite loop, and none can detect left recursion at parser definition time, as far as I know.

For example Scala has Fast Parse, it doesn't have either infinite loop safety or left recursion safety; Cats Parse offers infinite loop safety (using a similar type dichotomy of Parser<T> vs. Parser0<T>), but it still falls short of left recursion protection: you got only useless StackOverflowError at runtime.