Module earley 

2026-09-26: Earley parser for grammar matching. EarleyParser holds the Earley items, advances them one byte at a time (advance), expands rule references (predict, predict_fsm), completes finished rules (complete), reports the acceptable next bytes (accept), and pushes or rolls back steps for the matcher.

Owner: grammar. Invariants: completable, is_completed and scanable_history hold one entry per step. new, an accepted advance, push_state_and_expand and push_one_state_to_check add one to each; pop_last_states(count) removes count from each and panics rather than remove the first step; reset clears all three.

Structs

EarleyParser

The Earley parser. Drives grammar matching: it keeps the set of Earley items, advances them byte-by-byte, and supports push/rollback of parser state for the matcher’s token rollback.

ParserState

An Earley item: a position inside a rule’s body, paired with the input position the rule was predicted at.

ProcessQueue

Below this many distinct states the C++ RepeatDetector scans a small vector; above it, it switches to a hash set. We always use a hash set — AHashSet makes the small-N case cheap enough that the dual representation is not worth the complexity. Behavior (which states are reported visited) is identical.

Constants

NO_PREV_INPUT_POS

A rule_start_pos of this value marks an item as a root of the parsing stack (no preceding input position).

UNEXPANDED_RULE_START_SEQUENCE_ID

A sequence_id of this value means the rule has not been expanded yet (used for the initial state pushed into the parser).

Functions

cache_key

The C++ uses two equality notions; we model the parsing one as PartialEq (all fields). The cache notion ignores rule_start_pos and repeat_count — see cache_key.

Type Aliases

CompletableEntry

One (referenced_rule_id, parent_state) entry of the completable-states table. The C++ stores Compact2DArray<pair<int32_t, ParserState>>; the Rust port now uses the ported Compact2DArray (CSR) layout, matching it exactly.