lang::parser::position
lang/src/parser/position.mo
Position tracking utilities for the self-hosted parser Extracted from parser.mo as part of Phase C
pub struct LineColScan {
newlines : I64,
/// Characters since the last newline -- or, if there is no newline at
/// all, the character count of the whole string.
trailing : I64,
}pub def resolve_offsets_in_file (source : String) (offsets : List I64) : List (Pair I64 Location)Resolve offsets (ascending, absolute byte offsets) against source.
Offsets at or past end-of-file resolve to the file's final position
rather than being dropped: end-of-input is a real position, and a
dropped entry would leave a term with no location for no visible
reason.
The single-pass walk consumes pending from the head and never goes
back, so it REQUIRES ascending input. This used to check is_ascending
and fall back to a per-offset rescan of the whole file when it failed --
"the correct-but-quadratic path. Slow beats wrong." Correct, and a trap:
the fallback is silent, and callers do not in fact deliver ascending
offsets.
build_loc_table (lang/parser.mo) collects spans in pre-order and
argued that pre-order IS ascending. It is not, and the counterexample is
every infix expression in the language: a + b parses to
app (app (+) a) b, so a pre-order walk visits the operator node --
whose span starts at the + -- BEFORE the operand a that precedes it
in the source. Measured with bench/parser_located.mo:
init/id.mo 675 bytes, 30 spans ascending YES 27ms -> 36ms lang/types.mo 73000 bytes, 1469 spans ascending NO 1753ms -> 287766ms
164x, with the first inversion at span index 244. That fallback is what
made a --verbose self-compile WITHOUT --release take 28035824ms
(7h48m) against 275424ms with it, ~99.4% of it in with_located_decls.
Debug info is on by default, so that was the default monad compile.
So sort, and make the invariant hold rather than detecting that it does
not. is_ascending is kept as the cheap skip for input that already is
(the small-file case above) and as the executable statement of what the
walk needs. The quadratic fallback is gone: an unreachable-by-hope slow
path that nothing exercises is how this hid for as long as it did.
Sorting changes the ORDER of the returned pairs, not their content. The
only consumer (build_loc_table -> rekey_by_rem) folds them into a
HashMap keyed by offset, and this file's own tests look results up by
offset via lookup_resolved, so no caller observes the order.
Offsets at or past end-of-file resolve to the file's final position rather than being dropped: end-of-input is a real position, and a dropped entry would leave a term with no location for no visible reason.
pub def is_ascending (offsets : List I64) : Bool