commit e665229aefa465755b17d605f20610d6cf4bd52e
parent 8aa842d5dfa4e091671abf3ac05d9f90e3974271
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Wed, 10 Jun 2026 22:50:57 -0700
perf(lex): redesign scanner on a splice-folded buffer
The lexer wove translation phase 2 (backslash-newline line splicing) into every
byte access: peek(off) re-walked off+1 bytes from the cursor re-testing for a
splice each step, bump() ran skip_splices, and identifier/number/string scans
plus intern all paid the per-byte splice test — though splices are vanishingly
rare in real source. lex_next/peek were among the hottest functions on every
compile.
Restructure phase 2 into a single up-front pass (lex_fold_splices): fold every
\<newline> out of the input once, so the scanner walks clean logical bytes with
plain direct indexing. Splice-free input (the overwhelming common case) is
borrowed verbatim, zero-copy; otherwise a folded heap copy plus a small sorted
array of fold offsets keeps line/col exact (lex_sync_splices advances the line
as the cursor passes each removed newline). peek() becomes a bounds-checked
index, bump() drops skip_splices, and intern/number scanning read straight from
the folded buffer — the per-token splice pre-scan and reusable splice scratch
are gone entirely.
vs the pre-lexer state: body-size -7%, type-decl -9%, pp-macro -E -6%, fn-count
-4.5%. Object output, -E output, -g line tables, and diagnostics all
byte-identical — including a splice battery (mid-token / mid-string / leading /
trailing / consecutive line continuations) where an error across a splice still
reports the correct physical line. Verified: test-pp/parse/toy/debug/dwarf/
smoke-x64/smoke-rv64 + 21 rt/ sources byte-identical.
Diffstat:
| M | lang/cpp/lex/lex.c | | | 207 | ++++++++++++++++++++++++++++++++++++------------------------------------------- |
1 file changed, 95 insertions(+), 112 deletions(-)
diff --git a/lang/cpp/lex/lex.c b/lang/cpp/lex/lex.c
@@ -20,6 +20,10 @@ struct Lexer {
Compiler* c;
Pool* pool;
Heap* heap;
+ /* `src`/`len` are the post-phase-2 (line-splice-folded) logical bytes the
+ * scanner walks with plain direct indexing — no per-byte splice test. When
+ * the input contains no `\<newline>` (the common case) this borrows the input
+ * verbatim (owns_src = 0, zero-copy); otherwise it is a folded heap copy. */
const char* src;
size_t len;
size_t pos;
@@ -32,62 +36,92 @@ struct Lexer {
* 0 = none, 1 = saw pp-hash, 2 = saw `#include`/etc and the next
* token may be a header-name. */
u8 dstate;
- /* Grow-once scratch reused for per-token splice removal: a (rare) token
- * containing a `\<newline>` packs its bytes here instead of a fresh heap
- * block, so capacity sticks at the high-water mark and steady-state lexing
- * never allocates per token. Contents are transient -- valid only until the
- * next token. */
- char* scratch;
- size_t scratch_cap;
+ u8 owns_src; /* src is a heap-allocated folded copy to free at close */
+ /* Sorted logical offsets at which a `\<newline>` splice was folded out, so
+ * line/col tracking can still advance the physical line as the cursor passes
+ * each. Empty (and NULL) for splice-free input. */
+ u32* splices;
+ u32 nsplices;
+ u32 next_splice;
};
-/* At least `need` bytes of reusable scratch (see Lexer.scratch), growing
- * geometrically and retaining capacity. NULL only on OOM. */
-static char* lex_scratch(Lexer* l, size_t need) {
- if (need > l->scratch_cap) {
- size_t cap = l->scratch_cap ? l->scratch_cap : 64;
- char* p;
- while (cap < need) cap *= 2;
- p = (char*)l->heap->realloc(l->heap, l->scratch, l->scratch_cap, cap, 1);
- if (!p) return NULL;
- l->scratch = p;
- l->scratch_cap = cap;
+/* §5.1.1.2 translation phase 2: fold every `\<newline>` line splice out of the
+ * input once, up front, so the scanner never tests for splices per byte. The
+ * common (splice-free) input is borrowed verbatim; otherwise a heap copy holds
+ * the folded text and `splices[]` records each fold point (a logical offset) so
+ * line numbering still advances across the removed physical newline. */
+static void lex_fold_splices(Lexer* l, const char* src, size_t len) {
+ size_t i;
+ size_t nspl = 0;
+ char* buf;
+ u32* spl;
+ size_t w, s, wcap;
+ l->next_splice = 0;
+ for (i = 0; i + 1 < len; ++i)
+ if (src[i] == '\\' && src[i + 1] == '\n') ++nspl;
+ if (nspl == 0) {
+ l->src = src;
+ l->len = len;
+ l->owns_src = 0;
+ l->splices = NULL;
+ l->nsplices = 0;
+ return;
+ }
+ /* Each folded splice removes exactly 2 bytes, so the folded length is known
+ * up front; allocate it exactly so the close-time free size matches. */
+ wcap = len - 2u * nspl;
+ spl = (u32*)l->heap->alloc(l->heap, nspl * sizeof(u32), _Alignof(u32));
+ buf = wcap ? (char*)l->heap->alloc(l->heap, wcap, 1) : NULL;
+ if (!spl || (wcap && !buf)) {
+ /* OOM: fall back to the raw input. The (rare) splice then survives into a
+ * token spelling, but lexing stays memory-safe. */
+ if (buf) l->heap->free(l->heap, buf, wcap);
+ if (spl) l->heap->free(l->heap, spl, nspl * sizeof(u32));
+ l->src = src;
+ l->len = len;
+ l->owns_src = 0;
+ l->splices = NULL;
+ l->nsplices = 0;
+ return;
+ }
+ w = 0;
+ s = 0;
+ for (i = 0; i < len;) {
+ if (i + 1 < len && src[i] == '\\' && src[i + 1] == '\n') {
+ spl[s++] = (u32)w; /* fold point = logical offset of the next byte */
+ i += 2;
+ continue;
+ }
+ buf[w++] = src[i++];
}
- return l->scratch;
+ l->src = wcap ? buf : "";
+ l->len = w; /* == wcap */
+ l->owns_src = wcap ? 1u : 0u;
+ l->splices = spl;
+ l->nsplices = (u32)s;
}
-/* §5.1.1.2 translation phase 2: splice physical lines joined by
- * backslash-newline. Advance past any splice sequence at l->pos so the
- * cursor never rests on the leading backslash of a splice. */
-static void skip_splices(Lexer* l) {
- while (l->pos + 1 < l->len && l->src[l->pos] == '\\' &&
- l->src[l->pos + 1] == '\n') {
- l->pos += 2;
+/* Advance the line counter for any fold points at the current logical position
+ * (a `\<newline>` removed here was a physical line break). Called after every
+ * cursor advance and once at open for a leading splice. */
+static inline void lex_sync_splices(Lexer* l) {
+ while (l->next_splice < l->nsplices && l->splices[l->next_splice] == l->pos) {
l->line++;
l->col = 1;
+ l->next_splice++;
}
}
-/* Logical peek: returns the off-th post-splice byte starting at l->pos,
- * or -1 at end of input. Does not mutate l->pos. */
+/* The off-th logical byte at the cursor, or -1 at end of input. Splices were
+ * folded out at open, so this is a plain bounds-checked index — no per-byte
+ * splice walk. */
static int peek(const Lexer* l, size_t off) {
- size_t pos = l->pos;
- size_t k = 0;
- while (pos < l->len) {
- if (pos + 1 < l->len && l->src[pos] == '\\' && l->src[pos + 1] == '\n') {
- pos += 2;
- continue;
- }
- if (k == off) return (unsigned char)l->src[pos];
- ++pos;
- ++k;
- }
- return -1;
+ size_t p = l->pos + off;
+ return p < l->len ? (unsigned char)l->src[p] : -1;
}
static int bump(Lexer* l) {
int ch;
- skip_splices(l);
if (l->pos >= l->len) return -1;
ch = (unsigned char)l->src[l->pos++];
if (ch == '\n') {
@@ -96,6 +130,7 @@ static int bump(Lexer* l) {
} else {
l->col++;
}
+ lex_sync_splices(l);
return ch;
}
@@ -156,13 +191,13 @@ Lexer* lex_open_mem(Compiler* c, const char* name, const char* src,
return NULL;
}
l->heap = h;
- l->src = src ? src : "";
- l->len = src ? len : 0;
+ lex_fold_splices(l, src ? src : "", src ? len : 0);
l->pos = 0;
l->file_id = 0;
(void)kit_source_add_memory(c, kit_slice_cstr(name), &l->file_id);
l->line = 1;
l->col = 1;
+ lex_sync_splices(l); /* a splice folded at offset 0 advances to line 2 */
l->at_bol = 1;
l->had_space = 0;
return l;
@@ -170,7 +205,9 @@ Lexer* lex_open_mem(Compiler* c, const char* name, const char* src,
void lex_close(Lexer* l) {
if (!l) return;
- if (l->scratch) l->heap->free(l->heap, l->scratch, l->scratch_cap);
+ if (l->owns_src) l->heap->free(l->heap, (char*)l->src, l->len);
+ if (l->splices)
+ l->heap->free(l->heap, l->splices, l->nsplices * sizeof(u32));
c_pool_free(l->pool);
l->heap->free(l->heap, l, sizeof(*l));
}
@@ -193,35 +230,11 @@ void lex_skip_shebang(Lexer* l) {
SrcLoc lex_loc(const Lexer* l) { return lex_here(l); }
u32 lex_file_id(const Lexer* l) { return l->file_id; }
-/* Intern bytes [start, end) with line splices (\<newline>) removed, so token
- * spellings reflect post-phase-2 logical text. */
-static Sym intern_spliced(Lexer* l, size_t start, size_t end) {
- size_t i;
- int has_splice = 0;
- char* buf;
- size_t k;
-
- for (i = start; i + 1 < end; ++i) {
- if (l->src[i] == '\\' && l->src[i + 1] == '\n') {
- has_splice = 1;
- break;
- }
- }
- if (!has_splice)
- return kit_sym_intern(l->pool->c,
- (KitSlice){.s = l->src + start, .len = end - start});
-
- buf = lex_scratch(l, end - start);
- if (!buf) return 0;
- k = 0;
- for (i = start; i < end;) {
- if (i + 1 < end && l->src[i] == '\\' && l->src[i + 1] == '\n') {
- i += 2;
- continue;
- }
- buf[k++] = l->src[i++];
- }
- return kit_sym_intern(l->pool->c, (KitSlice){.s = buf, .len = k});
+/* Intern a token's spelling [start, end) straight from the folded buffer (it is
+ * already post-phase-2 logical text — splices were removed at open). */
+static Sym lex_intern(Lexer* l, size_t start, size_t end) {
+ return kit_sym_intern(l->pool->c,
+ (KitSlice){.s = l->src + start, .len = end - start});
}
/* §6.4.7 header-name lookahead: in include-directive context, a `<` or `"`
@@ -350,7 +363,6 @@ Tok lex_next(Lexer* l) {
* subsequent content tokens for the line that follows. */
for (;;) {
skip_ws_and_comments(l);
- skip_splices(l);
if (l->pos >= l->len) {
t.kind = TOK_EOF;
t.loc = lex_here(l);
@@ -396,7 +408,7 @@ Tok lex_next(Lexer* l) {
bump(l);
}
t.kind = TOK_HEADER;
- t.spelling = intern_spliced(l, start, l->pos);
+ t.spelling = lex_intern(l, start, l->pos);
t.v.str = t.spelling;
l->dstate = 0;
return t;
@@ -452,7 +464,7 @@ Tok lex_next(Lexer* l) {
if (scan_quoted(l, is_char ? '\'' : '"')) t.flags |= TF_LITERAL_BAD;
t.kind = (u16)(is_char ? TOK_CHR : TOK_STR);
t.flags |= encf;
- t.spelling = intern_spliced(l, start, l->pos);
+ t.spelling = lex_intern(l, start, l->pos);
t.v.str = t.spelling;
l->dstate = 0;
return t;
@@ -485,7 +497,7 @@ Tok lex_next(Lexer* l) {
}
}
t.kind = TOK_IDENT;
- t.spelling = intern_spliced(l, start, l->pos);
+ t.spelling = lex_intern(l, start, l->pos);
t.v.ident = t.spelling;
if (l->dstate == 1) {
KitSlice s = kit_sym_str(l->pool->c, t.spelling);
@@ -499,42 +511,13 @@ Tok lex_next(Lexer* l) {
/* pp-number (§6.4.8), then classified to TOK_NUM / TOK_FLT. */
if (is_digit(ch) || (ch == '.' && is_digit(peek(l, 1)))) {
- size_t plen;
const char* text;
- size_t i, k;
- int has_splice = 0;
+ size_t k;
scan_pp_number(l);
- plen = l->pos - start;
- /* The interned spelling is the post-splice text. The common case has no
- * `\<newline>` inside the number, so its bytes are already contiguous in
- * the source -- classify and intern straight from there with no copy. A
- * splice packs into the lexer's reused scratch, never a per-token alloc. */
- for (i = start; i + 1 < l->pos; ++i) {
- if (l->src[i] == '\\' && l->src[i + 1] == '\n') {
- has_splice = 1;
- break;
- }
- }
- if (!has_splice) {
- text = l->src + start;
- k = plen;
- } else {
- char* sb = lex_scratch(l, plen ? plen : 1);
- if (sb) {
- k = 0;
- for (i = start; i < l->pos;) {
- if (i + 1 < l->pos && l->src[i] == '\\' && l->src[i + 1] == '\n') {
- i += 2;
- continue;
- }
- sb[k++] = l->src[i++];
- }
- text = sb;
- } else {
- text = l->src + start; /* OOM: fall back to the raw source bytes */
- k = plen;
- }
- }
+ /* The spelling is contiguous logical text in the folded buffer (splices
+ * were removed at open), so classify and intern straight from there. */
+ text = l->src + start;
+ k = l->pos - start;
t.kind = (u16)(pp_number_is_float(text, k) ? TOK_FLT : TOK_NUM);
/* Suffix flags for §6.4.4.1 / §6.4.4.2. The parser dispatches on
* TF_INT_U/L/LL and TF_FLT_F/L to pick a TY_* tag for the literal,
@@ -806,7 +789,7 @@ Tok lex_next(Lexer* l) {
for (i = 0; i < adv; ++i) bump(l);
t.kind = kind;
t.v.punct = punct;
- t.spelling = intern_spliced(l, start, l->pos);
+ t.spelling = lex_intern(l, start, l->pos);
if (kind == TOK_PP_HASH)
l->dstate = 1;
else
