kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

Lexer and preprocessor API: a lean token boundary for the C frontend

Goal. Redesign the lexer -> preprocessor -> parser boundary so a wholesale lexer/preprocessor rewrite can be high-performance without fusing the frontend layers. The lexer, preprocessor, and parser remain separately reusable modules: cpp / cc -E still use the preprocessor as a standalone component, and the C parser still consumes a preprocessed token stream. What changes is the data and the handoff contract.

This is a design note for the new API and boundary types. It is not yet an implementation plan for the scanner algorithm itself.

1. Current boundary

Today the frontend has a simple but heavy token contract.

1.1 C compile path

lang/c/c.c wires the C frontend as:

source bytes
  -> lex_open_mem / lex_skip_shebang
  -> pp_new / pp_push_input
  -> parse_c
  -> pcg adapter
  -> KitCg
  -> CgTarget / NativeDirectTarget
  -> NativeTarget
  -> MC emit

The current parser-feed path sets pp_set_suppress_lexer_newlines(pp, 1) before the primary lexer is pushed. Include lexers inherit the same policy. This avoids materializing non-directive newline tokens for the parser, while still surfacing directive-terminating newlines so directive reading works.

1.2 Lexer input

lex_open_mem takes:

Opening a lexer also registers a fresh compiler source file id. The lexer owns phase-2 line-splice folding. If a file contains no backslash-newline splices, it borrows the original bytes. If splices exist, it builds a folded copy and records fold points for physical line accounting.

That means the true lexer input boundary is not just (char*, len). It is:

1.3 Lexer output

The lexer returns Tok by value:

typedef struct Tok {
  u16 kind;
  u16 flags;
  SrcLoc loc;
  Sym spelling;
  union {
    Sym ident;
    Sym str;
    u32 punct;
  } v;
} Tok;

Important properties:

1.4 PP internal source stack

PP reads from a stack of token sources:

SRC_BUF is used for macro bodies, argument prescan, pushback, #pragma forwarding, and synthetic token sequences. Hidesets are internal to PP and are carried either as a per-token side array or as one uniform hideset id for a whole replay buffer.

Current macro bodies store full Tok arrays. A no-## body can be pointer replayed with per-invocation loc/first-flag overrides; bodies with paste still copy/substitute/paste through scratch buffers.

1.5 PP output to parser

pp_next() returns a macro-expanded Tok by value. The parser wraps it with:

The parser should not see non-directive newlines or directives. It does still see forwarded non-pragma # tokens in invalid cases, and it explicitly swallows forwarded pragmas.

There are already out-pointer paths inside PP (pp_next_raw_into, pp_next_into) because returning a 24-byte Tok by value costs a hidden sret copy. The public boundary has not caught up to that shape.

2. Design decision

Use a lean token as the canonical internal token for the C preprocessor lane:

This does not require control-flow fusion. The scanner can be rewritten as a tcc-class high-throughput scanner, the PP can keep a source stack and macro engine, and the parser can remain recursive descent. The boundary becomes cheap enough that keeping the layers separate is not itself the hot cost.

3. Proposed core types

The names here are provisional. The point is the contract.

3.1 Source input

typedef uint32_t CppSourceId;

typedef enum CppSourceFlag {
  CPP_SRC_PRIMARY = 1u << 0,      /* allow shebang skip */
  CPP_SRC_SYSTEM = 1u << 1,       /* diagnostics/deps source property */
  CPP_SRC_PARSER_FEED = 1u << 2,  /* suppress non-directive newlines */
  CPP_SRC_NO_SPLICES = 1u << 3,   /* caller proves no backslash-newline */
} CppSourceFlag;

typedef struct CppSourceSpec {
  KitSlice name;
  const char* bytes;
  uint32_t len;
  uint32_t flags;
} CppSourceSpec;

The lexer open API should make source identity explicit. It should return, or store in the lexer, the compiler file id registered for this source. Include resolution remains PP-owned; the lexer should not do filesystem work.

CPP_SRC_NO_SPLICES is the safe version of today's paste fast path. It is only valid for synthetic buffers whose construction proves no line splice can exist. Normal source files and command-line definitions stay on the safe splice scan.

3.2 Location reference

typedef struct CppLocRef {
  uint32_t file_id;
  uint32_t byte_off;
} CppLocRef;

The hot token carries a byte offset in the logical source stream, not an eager line/col pair. The source registry or lexer source object must have enough line-map data to turn (file_id, byte_off) into KitSrcLoc on demand.

#line complicates this. The PP should keep the current file/line overlay on the source stack, as it does today, and provide a helper:

KitSrcLoc cpp_pp_materialize_loc(CppPP* pp, CppLocRef loc);

Dynamic __LINE__ expansion should use the overlay-aware helper. Diagnostics from parser/PP should also route through it. The parser should not know the details of #line state.

3.3 Text reference

typedef enum CppTextKind {
  CPP_TEXT_NONE = 0,
  CPP_TEXT_SOURCE = 1,
  CPP_TEXT_SYM = 2,
} CppTextKind;

typedef struct CppTextRef {
  uint32_t kind;
  uint32_t source_id;
  uint32_t off;
  uint32_t len_or_sym;
} CppTextRef;

For source tokens, CPP_TEXT_SOURCE names a byte span in the source's logical post-splice buffer. For synthetic tokens, CPP_TEXT_SYM carries an interned symbol id in len_or_sym.

Helpers:

KitSlice cpp_text_slice(CppPP* pp, CppTextRef text);
Sym cpp_text_intern(CppPP* pp, CppTextRef text);
int cpp_text_eq_cstr(CppPP* pp, CppTextRef text, const char* s);

This keeps exact spelling available for -E, diagnostics, stringize, paste, literal decode, and macro identity checks without forcing every punctuator and literal spelling through the global symbol table on first lex.

3.4 Token

typedef struct CppTok {
  uint16_t kind;
  uint16_t flags;
  uint32_t aux;
  CppLocRef loc;
  CppTextRef text;
} CppTok;

Field meaning:

For identifiers, aux is the interned Sym. text may also be present as the exact spelling span, but normal identifier equality and macro lookup use aux.

For punctuators, aux is the Punct code. text is optional for common canonical punctuators on the parser-feed path. The -E, stringize, and paste paths can still recover spelling by either source span or canonical punctuator table. Digraphs need an exact source span.

For literals, text is the source or synthetic spelling. Numeric and string decoding should read via cpp_text_slice and only intern if a later operation requires a Sym.

4. New API shape

4.1 Lexer

typedef struct CppLexer CppLexer;

int cpp_lex_open(CppLexer* lx, KitCompiler* c, const CppSourceSpec* src);
void cpp_lex_reset(CppLexer* lx, const CppSourceSpec* src);
void cpp_lex_close(CppLexer* lx);

void cpp_lex_set_mode(CppLexer* lx, uint32_t flags);
void cpp_lex_next(CppLexer* lx, CppTok* out);

uint32_t cpp_lex_file_id(const CppLexer* lx);
KitSrcLoc cpp_lex_materialize_loc(const CppLexer* lx, CppLocRef loc);
KitSlice cpp_lex_text_slice(const CppLexer* lx, CppTextRef text);

The lexer should fill a caller-provided token slot. It should not return token structs by value.

The lexer should not track include keyword state as a hidden state machine. Instead PP should request header-name lexing while reading an include/embed directive. That can be a mode bit scoped to the next token, or an explicit entry point:

void cpp_lex_next_header_name(CppLexer* lx, CppTok* out);

This removes #include knowledge from the normal scanner hot path.

4.2 Preprocessor

typedef struct CppPP CppPP;

int cpp_pp_open(CppPP* pp, KitCompiler* c, const KitPreprocessOptions* opts);
void cpp_pp_close(CppPP* pp);

int cpp_pp_push_source(CppPP* pp, const CppSourceSpec* src);
void cpp_pp_add_include_dir(CppPP* pp, const char* dir, int system);
void cpp_pp_define(CppPP* pp, const char* name, const char* body);
void cpp_pp_undef(CppPP* pp, const char* name);

void cpp_pp_next_raw(CppPP* pp, CppTok* out);
void cpp_pp_next_parse(CppPP* pp, CppTok* out);
void cpp_pp_emit_text(CppPP* pp, KitWriter* out);

KitSrcLoc cpp_pp_materialize_loc(CppPP* pp, CppLocRef loc);
KitSlice cpp_pp_text_slice(CppPP* pp, CppTextRef text);
Sym cpp_pp_text_intern(CppPP* pp, CppTextRef text);

cpp_pp_next_raw is the -E stream: macro-expanded, directives consumed, newlines preserved as needed for text reconstruction.

cpp_pp_next_parse is the parser stream: macro-expanded, directives consumed, non-directive newlines absent, forwarded pragmas swallowed or represented by a parser-ignored event.

Both write into caller-owned slots.

4.3 Parser

The parser should own a small token cursor:

typedef struct CTokenCursor {
  CppPP* pp;
  CppTok cur;
  CppTok next;
  CppTok pending;
  uint8_t has_next;
  uint8_t has_pending;
} CTokenCursor;

The parser's advance, peek1, pending string-literal fusion, and braced-block replay stay local to the parser. The difference is that they copy CppTok, not the old eager-interned Tok, and they ask PP/text helpers only when a spelling or materialized location is actually needed.

5. Layer responsibilities

5.1 Lexer owns

5.2 PP owns

5.3 Parser owns

Hidesets must not cross into the parser. Include state must not cross into the lexer. C semantic keyword/type state must not cross into PP.

6. Important invariants

  1. Exact spelling remains available. #, ##, -E, diagnostics, literal decode, macro redefinition checks, and header parsing all require exact spelling. The change is lazy access, not lossy tokens.

  2. Parser-feed tokens do not require newline materialization. The parser stream should never allocate or return non-directive newline tokens. Directive termination remains an internal PP/lexer concern.

  3. Identifier lookup stays Sym-based. Macro lookup and parser binding/keyword lookup should be one indexed or table lookup on an interned identifier.

  4. Punctuator spelling is not a hot-path symbol-table operation. Punctuators are roughly half the stream on large C files. The parser needs the punctuator code, not a symbol table entry. Exact text is only needed for -E, stringize, paste, and diagnostics.

  5. Line/column is lazy. Hot tokens should not pay column arithmetic and SrcLoc construction unless a consumer needs a materialized location.

  6. Synthetic tokens have stable text. Macro expansions, dynamic predefined macros, paste output, stringize output, and command-line definitions must have text refs with lifetime at least until the returned token is consumed or until the owning PP arena is reset.

  7. Macro replay can remain pointer-based. Macro bodies should store CppTok[] plus compact metadata. Object-like no-paste bodies can still be pointer-replayed with loc/first-flag override.

  8. The public compatibility API can exist during migration. Old Tok pp_next(Pp*) can be implemented as an adapter while parser code is converted. This allows byte-identical gates at each step.

7. Migration plan

Step 1: introduce the types and adapters

Add CppTok, CppTextRef, CppLocRef, and text/location helper APIs next to the current Tok. Keep old Tok as the public compatibility type.

Build adapter helpers:

void cpp_tok_to_old_tok(CppPP* pp, const CppTok* in, Tok* out);
void old_tok_to_cpp_tok(CppPP* pp, const Tok* in, CppTok* out);

The old adapter will eagerly intern text and materialize locations. That is acceptable as a temporary compatibility layer.

Step 2: make PP public pull slot-based

Add slot-based public APIs over the existing implementation:

void pp_next_into_public(Pp* pp, Tok* out);
void pp_next_raw_into_public(Pp* pp, Tok* out);

Convert parser fetch to use the slot API before changing representation. This is a low-risk cleanup because PP already has internal out-pointer machinery.

Step 3: rewrite lexer behind a compatibility adapter

Implement the new scanner to fill CppTok. Convert to old Tok at the lexer or PP boundary. Gate on:

At this stage performance will understate the final win because the adapter still eagerly interns/materializes.

Step 4: convert PP macro storage and source stack to CppTok

Move macro bodies, replay buffers, argument vectors, and directive lines to CppTok. Keep pp_next() compatibility at the outside edge.

This is where lazy spelling starts to matter: macro expansion should carry source text refs until a PP operation demands interned text.

Step 5: convert parser cursor to CppTok

Replace parser Tok slots with CppTok slots. Parser helpers should use:

After this step, the old Tok adapter is no longer on the compile hot path.

Step 6: delete or narrow the old token contract

Keep an old-style token only where external API compatibility requires it, or delete it if no public API promises it. The C frontend hot path should be CppTok end to end through lexer, PP, and parser.

8. Open questions

  1. Line-map owner. Should line maps live in the compiler source registry, the lexer source object, or PP's source cache? The answer affects how parser diagnostics materialize CppLocRef after the lexer for an include has been popped.

  2. Text lifetime for folded source. If a source needed splice folding, CppTextRef must point at the folded logical buffer, not the original bytes. That folded buffer must live long enough for any token text refs in macro bodies that outlive the source file.

  3. Macro body text retention. A macro body defined in an include may survive after that include source is popped. Either macro-body tokens must intern/copy their text at definition time, or source buffers referenced by macro bodies must be retained until pp_free.

  4. Canonical punctuator text. For canonical punctuators, can CppTextRef be omitted and reconstructed from the punctuator code? That is attractive for parser-feed and most PP paths, but -E must preserve digraph spelling where relevant.

  5. Header-name mode. The current lexer has directive state to emit TOK_HEADER. The new design should move this to PP, but the exact API should be chosen when directive reading is rewritten.

  6. Token-paste validation. Paste currently concatenates spellings and re-lexes a tiny buffer. The new scanner should preserve that validation path but route it through CPP_SRC_NO_SPLICES and a reusable lexer object.

  7. Diagnostics parity. Lazy location must preserve user-visible line/column behavior, including #line, includes, splices, comments, and shebang handling.

  8. Public names. The final names should probably not expose Cpp if this becomes the common C-family preprocessor substrate. The design uses Cpp* only to avoid colliding with current Tok/Pp names.

9. Initial right-sized target

The first useful deliverable is not the full PP rewrite. It is a measured compatibility lane:

  1. New source spec, loc ref, text ref, and token definitions.
  2. Slot-based public PP pull API over the current code.
  3. New scanner filling the lean token.
  4. Adapter to old Tok.
  5. Head-to-head sqlite measurement:
    • raw lex instructions per byte
    • compile -c instructions
    • -E byte identity
    • object byte identity

If the adapter lane cannot produce a scanner win in isolation, the scanner algorithm is not yet good enough. If it does win in isolation but not through compile, the next bottleneck is PP token storage/replay and parser conversion.