kit

lex_runtime.c (43857B)

---

 /* gramlex.c - shared borrowed-input DFA driver for gramgen-generated lexers. */
 #include <string.h>
 
 #include <kit/support/gram_lex_tables.h>
 #include <kit/gram_unicode.h>
 
 static const uint64_t KW_FNV_OFFSET = 0xcbf29ce484222325ull;
 static const uint64_t KW_FNV_PRIME = 0x100000001b3ull;
 static const uint64_t KW_MIX1 = 0x9e3779b97f4a7c15ull;
 static const uint64_t KW_MIX2 = 0xff51afd7ed558ccdull;
 static const uint64_t KW_MIX3 = 0xc4ceb9fe1a85ec53ull;
 
 typedef struct {
   KitGramLexInputSpan* span;
   size_t off;
 } span_pos;
 
 typedef struct {
   uint32_t line, col;
   KitGramUnicodePos upos;
 } lex_pos;
 
 typedef struct {
   const KitGramLexGrammar* g;
 } kit_gram_matcher_impl;
 _Static_assert(sizeof(kit_gram_matcher_impl) <= KIT_GRAM_MATCHER_SIZE,
                "KitGramMatcher too small");
 static kit_gram_matcher_impl* matcher_impl(KitGramMatcher* m) {
   return (kit_gram_matcher_impl*)m;
 }
 
 typedef struct {
   const KitGramLexGrammar* g;
   KitGramLexInput* in;
   size_t from;
   bool multiline;
 } kit_gram_match_iter_impl;
 _Static_assert(sizeof(kit_gram_match_iter_impl) <= KIT_GRAM_MATCH_ITER_SIZE,
                "KitGramMatchIter too small");
 static kit_gram_match_iter_impl* iter_impl(KitGramMatchIter* it) {
   return (kit_gram_match_iter_impl*)it;
 }
 
 typedef struct kit_gram_lex_input_impl {
   KitGramLexInputConfig cfg;
   KitGramLexInputSpan* head;
   KitGramLexInputSpan* tail;
   size_t off;
 
   bool finished;
   bool failed;
   bool mode_set;
   KitGramLexInputMode mode;
 
   uint32_t line, col;
   KitGramUnicodePos upos;
   KitGramLexError error;
 
   size_t pending_len;
   lex_pos pending_pos;
   bool token_valid;
   span_pos token_start;
   size_t token_len;
   const unsigned char* token_lexeme;
 } kit_gram_lex_input_impl;
 
 typedef struct kit_gram_lexer_impl {
   const KitGramLexGrammar* g;
   KitGramLexInput* input_mem;
   kit_gram_lex_input_impl* in;
   KitGramLexConfig cfg;
 } kit_gram_lexer_impl;
 
 typedef struct kit_gram_lex_lexeme_impl {
   kit_gram_lex_input_impl* in;
   KitGramLexInputSpan* span;
   size_t off;
   size_t remaining;
   const unsigned char* single;
   size_t single_len;
   bool yielded_single;
 } kit_gram_lex_lexeme_impl;
 
 _Static_assert(sizeof(kit_gram_lex_input_impl) <= sizeof(KitGramLexInput),
                "KitGramLexInput storage too small - raise KIT_GRAM_LEX_INPUT_SIZE "
                "in gramlex.h");
 _Static_assert(_Alignof(kit_gram_lex_input_impl) <= _Alignof(KitGramLexInput),
                "KitGramLexInput storage under-aligned");
 _Static_assert(
     sizeof(kit_gram_lexer_impl) <= sizeof(KitGramLexer),
     "KitGramLexer storage too small - raise KIT_GRAM_LEXER_SIZE in gramlex.h");
 _Static_assert(_Alignof(kit_gram_lexer_impl) <= _Alignof(KitGramLexer),
                "KitGramLexer storage under-aligned");
 _Static_assert(sizeof(kit_gram_lex_lexeme_impl) <= sizeof(KitGramLexLexeme),
                "KitGramLexLexeme storage too small - raise KIT_GRAM_LEX_LEXEME_SIZE "
                "in gramlex.h");
 _Static_assert(_Alignof(kit_gram_lex_lexeme_impl) <= _Alignof(KitGramLexLexeme),
                "KitGramLexLexeme storage under-aligned");
 
 static kit_gram_lex_input_impl* in_impl(KitGramLexInput* in) {
   return (kit_gram_lex_input_impl*)in;
 }
 static const kit_gram_lex_input_impl* cin_impl(const KitGramLexInput* in) {
   return (const kit_gram_lex_input_impl*)in;
 }
 static kit_gram_lexer_impl* lx_impl(KitGramLexer* lx) { return (kit_gram_lexer_impl*)lx; }
 static kit_gram_lex_lexeme_impl* it_impl(KitGramLexLexeme* it) {
   return (kit_gram_lex_lexeme_impl*)it;
 }
 
 static uint32_t add_u32_wrap(uint32_t a, size_t b) { return a + (uint32_t)b; }
 
 static uint32_t cur_line(const kit_gram_lex_input_impl* in) {
   return in->mode_set && in->mode == KIT_GRAM_LEX_INPUT_UTF8 ? in->upos.line
                                                          : in->line;
 }
 
 static uint32_t cur_col(const kit_gram_lex_input_impl* in) {
   return in->mode_set && in->mode == KIT_GRAM_LEX_INPUT_UTF8 ? in->upos.col
                                                          : in->col;
 }
 
 static unsigned char current_byte(const kit_gram_lex_input_impl* in) {
   return in->head && in->off < in->head->len ? in->head->bytes[in->off] : 0;
 }
 
 static lex_pos current_pos(const kit_gram_lex_input_impl* in) {
   return (lex_pos){.line = in->line, .col = in->col, .upos = in->upos};
 }
 
 static void set_pos(kit_gram_lex_input_impl* in, const lex_pos* pos) {
   if (in->mode_set && in->mode == KIT_GRAM_LEX_INPUT_UTF8) {
     in->upos = pos->upos;
   } else {
     in->line = pos->line;
     in->col = pos->col;
   }
 }
 
 typedef struct {
   lex_pos pos;
   uint32_t cp;
   uint8_t need;
 } scan_pos;
 
 static void scan_pos_init(scan_pos* sp, const kit_gram_lex_input_impl* in) {
   *sp = (scan_pos){.pos = current_pos(in)};
 }
 
 static void scan_pos_advance(scan_pos* sp, KitGramLexInputMode mode,
                              unsigned char b) {
   if (mode != KIT_GRAM_LEX_INPUT_UTF8) {
     if (b == '\n') {
       sp->pos.line++;
       sp->pos.col = 1;
     } else {
       sp->pos.col = add_u32_wrap(sp->pos.col, 1);
     }
     return;
   }
 
   if (!sp->need) {
     if (b < 0x80u) {
       kit_gram_unicode_pos_advance(&sp->pos.upos, b);
     } else if (b >= 0xC2u && b <= 0xDFu) {
       sp->cp = (uint32_t)(b & 0x1Fu);
       sp->need = 1;
     } else if (b >= 0xE0u && b <= 0xEFu) {
       sp->cp = (uint32_t)(b & 0x0Fu);
       sp->need = 2;
     } else if (b >= 0xF0u && b <= 0xF4u) {
       sp->cp = (uint32_t)(b & 0x07u);
       sp->need = 3;
     }
     return;
   }
 
   if (!kit_gram_utf8_is_cont(b)) {
     sp->need = 0;
     return;
   }
   sp->cp = (sp->cp << 6) | (uint32_t)(b & 0x3Fu);
   if (--sp->need == 0) kit_gram_unicode_pos_advance(&sp->pos.upos, sp->cp);
 }
 
 static void release_span(KitGramLexInputSpan* span) {
   if (span->on_consumed) span->on_consumed(span->ud, span->bytes, span->len);
   span->next = NULL;
 }
 
 static void release_consumed_front(kit_gram_lex_input_impl* in) {
   while (in->head && in->off >= in->head->len) {
     KitGramLexInputSpan* span = in->head;
     in->head = span->next;
     if (in->tail == span) in->tail = NULL;
     in->off = 0;
     release_span(span);
   }
 }
 
 static void release_all(kit_gram_lex_input_impl* in) {
   KitGramLexInputSpan* span = in->head;
   while (span) {
     KitGramLexInputSpan* next = span->next;
     release_span(span);
     span = next;
   }
   in->head = NULL;
   in->tail = NULL;
   in->off = 0;
 }
 
 static void set_error(kit_gram_lex_input_impl* in, uint32_t line, uint32_t col,
                       unsigned char byte, const char* message) {
   if (!in || in->failed) return;
   in->failed = true;
   in->pending_len = 0;
   in->token_valid = false;
   in->error = (KitGramLexError){
       .line = line, .col = col, .byte = byte, .message = message};
   release_all(in);
 }
 
 static void set_current_error(kit_gram_lex_input_impl* in, unsigned char byte,
                               const char* message) {
   set_error(in, cur_line(in), cur_col(in), byte, message);
 }
 
 static void set_hook_error(kit_gram_lex_input_impl* in, const KitGramToken* tok,
                            const KitGramLexError* err, const char* fallback) {
   uint32_t line = err && err->line ? err->line : tok->line;
   uint32_t col = err && err->col ? err->col : tok->col;
   unsigned char byte = err ? err->byte : 0;
   const char* message = err && err->message ? err->message : fallback;
   set_error(in, line, col, byte, message);
 }
 
 static size_t gather_from(span_pos pos, unsigned char* out, size_t cap) {
   size_t n = 0;
   KitGramLexInputSpan* span = pos.span;
   size_t off = pos.off;
   while (span && n < cap) {
     while (off < span->len && n < cap) out[n++] = span->bytes[off++];
     span = span->next;
     off = 0;
   }
   return n;
 }
 
 static bool diagnose_utf8_at_current(const kit_gram_lex_input_impl* in,
                                      const char** message) {
   if (!in->mode_set || in->mode != KIT_GRAM_LEX_INPUT_UTF8 || !in->head ||
       in->off >= in->head->len)
     return false;
   unsigned char tmp[4];
   uint32_t cp = 0;
   size_t nbytes = 0;
   size_t n = gather_from((span_pos){in->head, in->off}, tmp, sizeof tmp);
   KitGramUtf8Status st = kit_gram_utf8_decode_one(tmp, n, &cp, &nbytes);
   (void)cp;
   (void)nbytes;
   if (st == KIT_GRAM_UTF8_INVALID) {
     *message = "invalid UTF-8";
     return true;
   }
   if (st == KIT_GRAM_UTF8_NEED_MORE && in->finished) {
     *message = "incomplete UTF-8";
     return true;
   }
   return false;
 }
 
 static bool advance_cursor_raw(kit_gram_lex_input_impl* in, size_t n) {
   if (!n) return true;
   if (in->head && in->off + n <= in->head->len) {
     in->off += n;
     release_consumed_front(in);
     return true;
   }
   size_t remaining = n;
   while (remaining && in->head) {
     size_t avail = in->head->len - in->off;
     size_t take = remaining < avail ? remaining : avail;
     in->off += take;
     remaining -= take;
     release_consumed_front(in);
   }
   if (remaining) {
     set_current_error(in, 0, "input cursor out of range");
     return false;
   }
   return true;
 }
 
 static bool consume_committed(kit_gram_lex_input_impl* in, size_t n,
                               const lex_pos* pos) {
   if (!advance_cursor_raw(in, n)) return false;
   set_pos(in, pos);
   return true;
 }
 
 static void commit_pending(kit_gram_lex_input_impl* in) {
   if (!in || !in->pending_len || in->failed) return;
   size_t n = in->pending_len;
   in->pending_len = 0;
   in->token_valid = false;
   (void)consume_committed(in, n, &in->pending_pos);
 }
 
 /* ---- Tier-1 edge anchors (zero-width DFA transitions) --------------------
  * Edge anchors are baked into the DFA: start anchors (\A/^) select an alternate
  * start state, and end anchors (\z/$) surface as the per-state end-context
  * accept tables. The driver picks the start state from the start-of-match
  * context and, at each scanned length, the highest-priority accept whose end
  * context holds. Both the tokenizer and the match API share these two helpers.
  */
 
 /* Pick the start DFA state for a scan beginning at a position that is (or is
  * not) the start of text / a line. start_text/start_line are 0 when the grammar
  * has no start anchors, so state 0 serves every context. */
 static uint16_t lex_start_state(const KitGramLexGrammar* g, bool multiline,
                                 bool text_start, bool line_start) {
   if (text_start) return g->start_text;
   if (multiline && line_start) return g->start_line;
   return 0;
 }
 
 /* Priority-winning accept at `state` for a match whose end is at_text_end
  * and/or before a line break. Plain accepts are always eligible; \z (text)
  * accepts at text end; $ (line) accepts at text end or, under multiline, before
  * a break. Lower accept id = higher source priority; KIT_GRAM_LEX_ACCEPT_NONE =
  * none.
  */
 static uint16_t lex_pick_accept(const KitGramLexGrammar* g, uint16_t state,
                                 bool at_text_end, bool before_break,
                                 bool multiline) {
   uint16_t best = g->accept[state];
   if (at_text_end && g->accept_text) {
     uint16_t a = g->accept_text[state];
     if (a < best) best = a;
   }
   if (g->accept_line && (at_text_end || (multiline && before_break))) {
     uint16_t a = g->accept_line[state];
     if (a < best) best = a;
   }
   return best;
 }
 
 /* End-of-match context at the lookahead position (span,off): whether it is the
  * end of text, and whether a line break begins there. `determined` is false
  * when the deciding bytes are not yet available and the input is not finished
  * (the tokenizer then reports NEED_MORE). `want_break` is false when no line
  * ($) end anchor is in play, so the break scalar need not be decoded. */
 typedef struct {
   bool determined;
   bool at_text_end;
   bool before_break;
 } scan_end_ctx;
 
 static scan_end_ctx scan_end_context(const kit_gram_lex_input_impl* in,
                                      KitGramLexInputSpan* span, size_t off,
                                      bool want_break) {
   while (span && off >= span->len) {
     off -= span->len;
     span = span->next;
   }
   if (!span) {
     if (in->finished) return (scan_end_ctx){true, true, false};
     return (scan_end_ctx){false, false, false};
   }
   if (!want_break) return (scan_end_ctx){true, false, false};
   bool brk;
   if (in->mode == KIT_GRAM_LEX_INPUT_UTF8) {
     unsigned char tmp[4];
     size_t n = gather_from((span_pos){span, off}, tmp, sizeof tmp);
     uint32_t cp = 0;
     size_t nbytes = 0;
     KitGramUtf8Status st = kit_gram_utf8_decode_one(tmp, n, &cp, &nbytes);
     if (st == KIT_GRAM_UTF8_NEED_MORE && !in->finished)
       return (scan_end_ctx){false, false, false};
     brk = st == KIT_GRAM_UTF8_OK && kit_gram_unicode_is_line_break(cp);
   } else {
     brk = span->bytes[off] == '\n';
   }
   return (scan_end_ctx){true, false, brk};
 }
 
 static bool state_has_outgoing(const KitGramLexGrammar* g, uint16_t state) {
   if (!g || state >= g->nstates) return false;
   uint16_t stride = g->class_stride ? g->class_stride : g->nclasses;
   const uint16_t* row = &g->trans[(size_t)state * stride];
   for (uint16_t i = 0; i < g->nclasses; i++)
     if (row[i] != KIT_GRAM_LEX_DEAD) return true;
   return false;
 }
 
 typedef enum {
   SCAN_ACCEPT,
   SCAN_NEED_MORE,
   SCAN_ERROR,
 } scan_status;
 
 static scan_status scan_one(kit_gram_lexer_impl* lx, uint16_t* accept_out,
                             size_t* len_out, lex_pos* pos_out) {
   kit_gram_lex_input_impl* in = lx->in;
   const KitGramLexGrammar* g = lx->g;
   const uint8_t* class_of = g->class_of;
   const uint16_t* trans = g->trans;
   const uint16_t stride = g->class_stride ? g->class_stride : g->nclasses;
   const bool ml = g->multiline;
   const bool has_end = g->accept_text || g->accept_line;
   const KitGramLexInputMode mode = g->input;
 
   uint16_t state = 0;
   if (g->start_text || g->start_line) {
     bool ts = cur_line(in) == 1 && cur_col(in) == 1;
     bool ls = cur_col(in) == 1; /* text start or just after a line break */
     state = lex_start_state(g, ml, ts, ls);
   }
   uint16_t best_accept = KIT_GRAM_LEX_ACCEPT_NONE;
   size_t best_len = 0;
   lex_pos best_pos = current_pos(in);
   /* scan_pos drives UTF-8 scalar position folding; the byte fast path tracks
    * position arithmetically and never touches it, so initialize it lazily only
    * in the branches that use it. */
   scan_pos sp;
   size_t seen = 0;
   KitGramLexInputSpan* span = in->head;
   size_t off = in->off;
 
   if (!has_end) {
     /* Fast path: no end anchors, so accepts need no end-context lookahead.
      * The per-byte loop is specialized on input mode (loop unswitching). In
      * byte mode the column advances exactly one per byte and resets only
      * across the rare embedded newline, so the winning end position is
      * arithmetic — avoiding both the per-accept 20-byte position-struct copy
      * (whose bulk, upos, is unused in byte mode) and the per-byte runtime
      * mode branch inside scan_pos_advance. UTF-8 mode keeps the folded
      * scan_pos scalar decode. */
     const uint16_t* accept_tbl = g->accept;
     bool dead = false;
     if (mode != KIT_GRAM_LEX_INPUT_UTF8) {
       const uint32_t start_col = in->col;
       uint32_t line = in->line;
       size_t last_nl = 0; /* seen index just past the last '\n'; 0 = none */
       while (span) {
         const unsigned char* buf = span->bytes;
         size_t len = span->len;
         while (off < len) {
           unsigned char b = buf[off];
           uint16_t next = trans[(size_t)state * stride + class_of[b]];
           if (next == KIT_GRAM_LEX_DEAD) {
             dead = true;
             goto fast_done;
           }
           state = next;
           off++;
           seen++;
           if (b == '\n') {
             line++;
             last_nl = seen;
           }
           uint16_t accept = accept_tbl[state];
           if (accept != KIT_GRAM_LEX_ACCEPT_NONE) {
             best_accept = accept;
             best_len = seen;
             best_pos.line = line;
             best_pos.col = last_nl ? (uint32_t)(1u + (seen - last_nl))
                                    : add_u32_wrap(start_col, seen);
           }
         }
         span = span->next;
         off = 0;
       }
     } else {
       scan_pos_init(&sp, in);
       while (span) {
         const unsigned char* buf = span->bytes;
         size_t len = span->len;
         while (off < len) {
           unsigned char b = buf[off];
           uint16_t next = trans[(size_t)state * stride + class_of[b]];
           if (next == KIT_GRAM_LEX_DEAD) {
             dead = true;
             goto fast_done;
           }
           state = next;
           off++;
           seen++;
           scan_pos_advance(&sp, KIT_GRAM_LEX_INPUT_UTF8, b);
           uint16_t accept = accept_tbl[state];
           if (accept != KIT_GRAM_LEX_ACCEPT_NONE) {
             best_accept = accept;
             best_len = seen;
             best_pos = sp.pos;
           }
         }
         span = span->next;
         off = 0;
       }
     }
   fast_done:
     if (dead) {
       if (best_accept != KIT_GRAM_LEX_ACCEPT_NONE) {
         *accept_out = best_accept;
         *len_out = best_len;
         *pos_out = best_pos;
         return SCAN_ACCEPT;
       }
       const char* message = "invalid token";
       diagnose_utf8_at_current(in, &message);
       set_current_error(in, current_byte(in), message);
       return SCAN_ERROR;
     }
 
     if (best_accept != KIT_GRAM_LEX_ACCEPT_NONE) {
       if (in->finished || !state_has_outgoing(g, state)) {
         *accept_out = best_accept;
         *len_out = best_len;
         *pos_out = best_pos;
         return SCAN_ACCEPT;
       }
     } else if (in->finished) {
       const char* message = "incomplete token";
       diagnose_utf8_at_current(in, &message);
       set_current_error(in, current_byte(in), message);
       return SCAN_ERROR;
     } else if (!state_has_outgoing(g, state)) {
       const char* message = "invalid token";
       diagnose_utf8_at_current(in, &message);
       set_current_error(in, current_byte(in), message);
       return SCAN_ERROR;
     }
     return SCAN_NEED_MORE;
   }
 
   /* End-anchored grammar: evaluate the full candidate (plain plus the eligible
    * end-context accepts) at each scanned length. This needs one position of
    * lookahead for the end context, so it can report NEED_MORE mid-token. */
   const bool want_break = g->accept_line && ml;
   bool dead = false;
   scan_pos_init(&sp, in);
   for (;;) {
     while (span && off >= span->len) {
       span = span->next;
       off = 0;
     }
     scan_end_ctx ec = scan_end_context(in, span, off, want_break);
     if (!ec.determined) {
       /* End context unresolved (more bytes may arrive). Record the
        * context-free plain accept; wait unless nothing more can change the
        * outcome (no extension and no pending end accept at this state). */
       uint16_t plain = g->accept[state];
       if (plain != KIT_GRAM_LEX_ACCEPT_NONE) {
         best_accept = plain;
         best_len = seen;
         best_pos = sp.pos;
       }
       bool end_pending =
           (g->accept_text && g->accept_text[state] != KIT_GRAM_LEX_ACCEPT_NONE) ||
           (g->accept_line && g->accept_line[state] != KIT_GRAM_LEX_ACCEPT_NONE);
       if (state_has_outgoing(g, state) || end_pending) return SCAN_NEED_MORE;
       break;
     }
     uint16_t cand =
         lex_pick_accept(g, state, ec.at_text_end, ec.before_break, ml);
     if (cand != KIT_GRAM_LEX_ACCEPT_NONE) {
       best_accept = cand;
       best_len = seen;
       best_pos = sp.pos;
     }
     if (!span) break; /* end of text (input finished) */
     unsigned char b = span->bytes[off];
     uint16_t next = trans[(size_t)state * stride + class_of[b]];
     if (next == KIT_GRAM_LEX_DEAD) {
       dead = true;
       break;
     }
     state = next;
     off++;
     seen++;
     scan_pos_advance(&sp, mode, b);
   }
 
   if (best_accept != KIT_GRAM_LEX_ACCEPT_NONE) {
     *accept_out = best_accept;
     *len_out = best_len;
     *pos_out = best_pos;
     return SCAN_ACCEPT;
   }
   const char* message = dead ? "invalid token" : "incomplete token";
   diagnose_utf8_at_current(in, &message);
   set_current_error(in, current_byte(in), message);
   return SCAN_ERROR;
 }
 
 static const unsigned char* prepare_lexeme(kit_gram_lex_input_impl* in,
                                            size_t len) {
   in->token_start = (span_pos){in->head, in->off};
   in->token_len = len;
   in->token_valid = true;
 
   if (!len) {
     in->token_lexeme = (const unsigned char*)"";
     return in->token_lexeme;
   }
   if (in->head && in->off + len <= in->head->len) {
     in->token_lexeme = in->head->bytes + in->off;
     return in->token_lexeme;
   }
   if (in->cfg.carry && len <= in->cfg.carry_cap) {
     size_t copied = 0;
     KitGramLexInputSpan* span = in->head;
     size_t off = in->off;
     while (span && copied < len) {
       size_t avail = span->len - off;
       size_t take = len - copied < avail ? len - copied : avail;
       memcpy(in->cfg.carry + copied, span->bytes + off, take);
       copied += take;
       span = span->next;
       off = 0;
     }
     in->token_lexeme = in->cfg.carry;
     return in->token_lexeme;
   }
   in->token_lexeme = NULL;
   return NULL;
 }
 
 /* ---- Extracted-keyword lookup (shared) -----------------------------------
  * A literal token shadowed by a more general host recognizer is moved out of
  * the DFA into a sorted (lexeme -> kind) table keyed by the host kind. After
  * the DFA picks a token whose kind is a host, the runtime binary-searches the
  * matched lexeme and rewrites the kind on an exact hit. The two callers (the
  * tokenizer and the match API) read the matched bytes differently, so they pass
  * a byte accessor; the table is sorted in the same memcmp order the comparator
  * uses. */
 static const KitGramLexKeywordTable* keyword_table_for(
     const KitGramLexGrammar* g, KitGramTokenKind host) {
   for (uint16_t i = 0; i < g->nkeyword_tables; i++)
     if (g->keyword_tables[i].host == host) return &g->keyword_tables[i];
   return NULL;
 }
 
 typedef unsigned char (*kw_byte_fn)(void* ud, size_t i);
 
 static uint64_t kw_fnv_bytes(const unsigned char* s, size_t len) {
   uint64_t h = KW_FNV_OFFSET;
   for (size_t i = 0; i < len; i++) h = (h ^ s[i]) * KW_FNV_PRIME;
   return h;
 }
 
 static uint64_t kw_fnv_indirect(kw_byte_fn at, void* ud, size_t len) {
   uint64_t h = KW_FNV_OFFSET;
   for (size_t i = 0; i < len; i++) h = (h ^ at(ud, i)) * KW_FNV_PRIME;
   return h;
 }
 
 /* Finish a seed-independent FNV byte hash the same way kit_gram_lex_kw_hash64 does
  * after its byte loop. This lets lookup hash the lexeme bytes once, then derive
  * both the CHD bucket and displaced slot from the same accumulator. */
 static uint64_t kw_hash_finish(uint64_t h, uint32_t seed) {
   h ^= (uint64_t)seed * KW_MIX1;
   h ^= h >> 33;
   h *= KW_MIX2;
   h ^= h >> 33;
   h *= KW_MIX3;
   h ^= h >> 33;
   return h;
 }
 
 static bool kw_eq_indirect(kw_byte_fn at, void* ud, size_t len,
                            const KitGramLexKeyword* kw) {
   if (len != kw->len) return false;
   for (size_t i = 0; i < len; i++)
     if (at(ud, i) != (unsigned char)kw->lexeme[i]) return false;
   return true;
 }
 
 static bool kw_eq_bytes(const unsigned char* s, size_t len,
                         const KitGramLexKeyword* kw) {
   return len == kw->len && memcmp(s, kw->lexeme, len) == 0;
 }
 
 /* Minimal perfect hash (CHD): bucket via seed 0, displace via the bucket's
  * seed, then one byte compare confirms the lexeme. nseeds and nkeywords are
  * powers of two (the generator rounds up, padding the slot array with empty
  * entries), so both indices are a mask rather than a per-token modulo. */
 static bool kw_lookup_hashed(const KitGramLexKeywordTable* t,
                              uint64_t byte_hash, const unsigned char* bytes,
                              kw_byte_fn at, void* ud, size_t len,
                              KitGramTokenKind* out) {
   if (!t->nseeds || !t->nkeywords) return false;
   if ((t->min_len || t->max_len) && (len < t->min_len || len > t->max_len))
     return false;
   uint32_t bucket =
       (uint32_t)(kw_hash_finish(byte_hash, 0) & (uint64_t)(t->nseeds - 1u));
   uint32_t slot = (uint32_t)(kw_hash_finish(byte_hash, t->seeds[bucket]) &
                              (uint64_t)(t->nkeywords - 1u));
   const KitGramLexKeyword* kw = &t->keywords[slot];
   if (!kw->lexeme) return false;
   if (bytes) {
     if (!kw_eq_bytes(bytes, len, kw)) return false;
   } else if (!kw_eq_indirect(at, ud, len, kw)) {
     return false;
   }
   *out = kw->kind;
   return true;
 }
 
 static bool kw_lookup_bytes(const KitGramLexKeywordTable* t,
                             const unsigned char* bytes, size_t len,
                             KitGramTokenKind* out) {
   if (!bytes) return false;
   if ((t->min_len || t->max_len) && (len < t->min_len || len > t->max_len))
     return false;
   return kw_lookup_hashed(t, kw_fnv_bytes(bytes, len), bytes, NULL, NULL, len,
                           out);
 }
 
 static bool kw_lookup_indirect(const KitGramLexKeywordTable* t, kw_byte_fn at,
                                void* ud, size_t len, KitGramTokenKind* out) {
   if ((t->min_len || t->max_len) && (len < t->min_len || len > t->max_len))
     return false;
   return kw_lookup_hashed(t, kw_fnv_indirect(at, ud, len), NULL, at, ud, len,
                           out);
 }
 
 KitGramTokenKind kit_gram_lex_keyword_rewrite(const KitGramLexGrammar* g,
                                        KitGramTokenKind kind,
                                        const unsigned char* bytes, size_t len) {
   const KitGramLexKeywordTable* t = keyword_table_for(g, kind);
   if (!t) return kind;
   KitGramTokenKind out;
   if (kw_lookup_bytes(t, bytes, len, &out)) return out;
   return kind;
 }
 
 /* Byte i of a token starting at a span_pos, walking the span list. */
 static unsigned char tok_kw_byte(void* ud, size_t i) {
   span_pos p = *(const span_pos*)ud;
   KitGramLexInputSpan* span = p.span;
   size_t off = p.off + i;
   while (span && off >= span->len) {
     off -= span->len;
     span = span->next;
   }
   return span ? span->bytes[off] : 0;
 }
 
 void kit_gram_lex_input_init(KitGramLexInput* mem,
                          const KitGramLexInputConfig* cfg) {
   if (!mem) return;
   kit_gram_lex_input_impl* in = in_impl(mem);
   *in = (kit_gram_lex_input_impl){
       .cfg = cfg ? *cfg : (KitGramLexInputConfig){0}, .line = 1, .col = 1};
   kit_gram_unicode_pos_init(&in->upos);
   if (in->cfg.carry_cap && !in->cfg.carry)
     set_error(in, 1, 1, 0, "invalid lexer input configuration");
 }
 
 void kit_gram_lex_input_push(KitGramLexInput* mem, KitGramLexInputSpan* span) {
   if (!mem || !span) return;
   kit_gram_lex_input_impl* in = in_impl(mem);
   if (in->failed) return;
   commit_pending(in);
   if (in->failed) return;
   if (in->finished) {
     set_current_error(in, 0, "cannot push after lexer input finish");
     return;
   }
   if (span->len && !span->bytes) {
     set_current_error(in, 0, "invalid lexer input span");
     return;
   }
   span->next = NULL;
   if (in->tail)
     in->tail->next = span;
   else
     in->head = span;
   in->tail = span;
   release_consumed_front(in);
 }
 
 void kit_gram_lex_input_finish(KitGramLexInput* mem) {
   if (!mem) return;
   kit_gram_lex_input_impl* in = in_impl(mem);
   if (in->failed) return;
   commit_pending(in);
   if (!in->failed) {
     in->finished = true;
     release_consumed_front(in);
   }
 }
 
 const KitGramLexError* kit_gram_lex_input_error(const KitGramLexInput* in) {
   static const KitGramLexError null_error = {
       .line = 1, .col = 1, .message = "null lexer input"};
   return in ? &cin_impl(in)->error : &null_error;
 }
 
 void kit_gram_lexer_init(KitGramLexer* mem, const KitGramLexGrammar* g,
                      KitGramLexInput* input, const KitGramLexConfig* cfg) {
   if (!mem) return;
   kit_gram_lexer_impl* lx = lx_impl(mem);
   *lx = (kit_gram_lexer_impl){.g = g,
                           .input_mem = input,
                           .in = input ? in_impl(input) : NULL,
                           .cfg = cfg ? *cfg : (KitGramLexConfig){0}};
   if (!input) return;
   kit_gram_lex_input_impl* in = lx->in;
   if (in->failed) return;
   if (!g || !g->trans || !g->accept || !g->accepts || g->nclasses == 0 ||
       g->nstates == 0 || (g->class_stride && g->class_stride < g->nclasses)) {
     set_error(in, cur_line(in), cur_col(in), 0, "invalid lexer configuration");
     return;
   }
   if (!in->mode_set) {
     in->mode = g->input;
     in->mode_set = true;
   } else if (in->mode != g->input) {
     set_error(in, cur_line(in), cur_col(in), 0, "lexer input mode mismatch");
   }
 }
 
 KitGramLexStatus kit_gram_lexer_next(KitGramLexer* mem, KitGramToken* out) {
   kit_gram_lexer_impl* lx = lx_impl(mem);
   kit_gram_lex_input_impl* in = lx->in;
   if (!in || !lx->g) return KIT_GRAM_LEX_ERROR;
   if (in->failed) return KIT_GRAM_LEX_ERROR;
   if (!out) {
     set_error(in, cur_line(in), cur_col(in), 0, "null token output");
     return KIT_GRAM_LEX_ERROR;
   }
 
   commit_pending(in);
   if (in->failed) return KIT_GRAM_LEX_ERROR;
 
   for (;;) {
     release_consumed_front(in);
     if (!in->head) return in->finished ? KIT_GRAM_LEX_EOF : KIT_GRAM_LEX_NEED_MORE;
 
     uint16_t accept = KIT_GRAM_LEX_ACCEPT_NONE;
     size_t tok_len = 0;
     lex_pos tok_end = current_pos(in);
     scan_status st = scan_one(lx, &accept, &tok_len, &tok_end);
     if (st == SCAN_NEED_MORE) return KIT_GRAM_LEX_NEED_MORE;
     if (st == SCAN_ERROR) return KIT_GRAM_LEX_ERROR;
     if (accept >= lx->g->naccepts) {
       set_error(in, cur_line(in), cur_col(in), 0, "invalid lexer accept table");
       return KIT_GRAM_LEX_ERROR;
     }
 
     const KitGramLexAccept* a = &lx->g->accepts[accept];
     /* Edge anchors are already resolved inside scan_one (start-state choice
      * plus end-context accept selection), so the accepted token is final. */
 
     if (a->skip) {
       if (!consume_committed(in, tok_len, &tok_end)) return KIT_GRAM_LEX_ERROR;
       continue;
     }
 
     const unsigned char* lexeme = prepare_lexeme(in, tok_len);
     KitGramToken tok = {
         .kind = a->tok,
         .lexeme = (const char*)lexeme,
         .len = tok_len,
         .line = cur_line(in),
         .col = cur_col(in),
     };
     in->pending_len = tok_len;
     in->pending_pos = tok_end;
 
     /* Rewrite an extracted keyword's kind on the whole lexeme, before the
      * hook, so the hook sees final kinds (as with the in-DFA representation).
      */
     if (lx->g->nkeyword_tables) {
       const KitGramLexKeywordTable* kt = keyword_table_for(lx->g, a->tok);
       KitGramTokenKind kw_kind;
       if (kt) {
         if (lexeme) {
           if (kw_lookup_bytes(kt, lexeme, tok_len, &kw_kind))
             tok.kind = kw_kind;
         } else {
           span_pos sp = in->token_start;
           if (kw_lookup_indirect(kt, tok_kw_byte, &sp, tok_len, &kw_kind))
             tok.kind = kw_kind;
         }
       }
     }
 
     if (lx->cfg.token_hook) {
       KitGramLexError hook_err = {.line = tok.line, .col = tok.col};
       KitGramLexHookResult hr =
           lx->cfg.token_hook(mem, lx->cfg.hook_ud, &tok, &hook_err);
       switch (hr) {
         case KIT_GRAM_LEX_HOOK_KEEP:
           break;
         case KIT_GRAM_LEX_HOOK_SKIP:
           commit_pending(in);
           if (in->failed) return KIT_GRAM_LEX_ERROR;
           continue;
         case KIT_GRAM_LEX_HOOK_ERROR:
           set_hook_error(in, &tok, &hook_err, "lexer token hook failed");
           return KIT_GRAM_LEX_ERROR;
         default:
           set_hook_error(in, &tok, &hook_err,
                          "invalid lexer token hook result");
           return KIT_GRAM_LEX_ERROR;
       }
     }
 
     *out = tok;
     return KIT_GRAM_LEX_TOKEN;
   }
 }
 
 void kit_gram_lexer_lexeme(KitGramLexer* mem, KitGramLexLexeme* it_mem) {
   if (!it_mem) return;
   kit_gram_lex_lexeme_impl* it = it_impl(it_mem);
   *it = (kit_gram_lex_lexeme_impl){0};
   if (!mem) return;
   kit_gram_lexer_impl* lx = lx_impl(mem);
   kit_gram_lex_input_impl* in = lx->in;
   if (!in || !in->token_valid) return;
   it->in = in;
   it->remaining = in->token_len;
   if (in->token_lexeme) {
     it->single = in->token_lexeme;
     it->single_len = in->token_len;
   } else {
     it->span = in->token_start.span;
     it->off = in->token_start.off;
   }
 }
 
 bool kit_gram_lex_lexeme_next(KitGramLexLexeme* it_mem, KitGramLexSegment* seg) {
   if (!it_mem || !seg) return false;
   kit_gram_lex_lexeme_impl* it = it_impl(it_mem);
   if (it->single) {
     if (it->yielded_single) return false;
     it->yielded_single = true;
     *seg = (KitGramLexSegment){.bytes = it->single, .len = it->single_len};
     return true;
   }
   while (it->span && it->remaining) {
     if (it->off >= it->span->len) {
       it->span = it->span->next;
       it->off = 0;
       continue;
     }
     size_t avail = it->span->len - it->off;
     size_t take = it->remaining < avail ? it->remaining : avail;
     *seg = (KitGramLexSegment){.bytes = it->span->bytes + it->off, .len = take};
     it->off += take;
     it->remaining -= take;
     return true;
   }
   return false;
 }
 
 /* ---- Match API (re2::Set, winner-only) -----------------------------------
  *
  * A read-only view over the input's current span list. Logical offset 0 is the
  * first unconsumed byte (in->head at in->off). The view never mutates or
  * consumes the input, so the same input may be matched repeatedly. */
 typedef struct {
   KitGramLexInputSpan* head;
   size_t head_off;
   size_t total;
   KitGramLexInputMode mode;
 } match_view;
 
 /* Locate the span/offset holding logical position pos. Returns false if pos is
  * at or beyond the end of available bytes. */
 static bool view_locate(const match_view* v, size_t pos,
                         KitGramLexInputSpan** span_out, size_t* off_out) {
   KitGramLexInputSpan* s = v->head;
   size_t off = v->head_off;
   size_t remaining = pos;
   while (s) {
     size_t avail = s->len - off;
     if (remaining < avail) {
       *span_out = s;
       *off_out = off + remaining;
       return true;
     }
     remaining -= avail;
     s = s->next;
     off = 0;
   }
   return false;
 }
 
 static bool view_byte(const match_view* v, size_t pos, unsigned char* out) {
   KitGramLexInputSpan* s;
   size_t off;
   if (!view_locate(v, pos, &s, &off)) return false;
   *out = s->bytes[off];
   return true;
 }
 
 static size_t view_gather(const match_view* v, size_t pos, unsigned char* out,
                           size_t cap) {
   KitGramLexInputSpan* s;
   size_t off;
   if (!view_locate(v, pos, &s, &off)) return 0;
   return gather_from((span_pos){s, off}, out, cap);
 }
 
 /* True iff a line-break scalar begins exactly at logical position pos. */
 static bool view_break_at(const match_view* v, size_t pos) {
   if (v->mode == KIT_GRAM_LEX_INPUT_UTF8) {
     unsigned char tmp[4];
     size_t n = view_gather(v, pos, tmp, sizeof tmp);
     uint32_t cp = 0;
     size_t nbytes = 0;
     if (kit_gram_utf8_decode_one(tmp, n, &cp, &nbytes) != KIT_GRAM_UTF8_OK)
       return false;
     return kit_gram_unicode_is_line_break(cp);
   }
   unsigned char b = 0;
   return view_byte(v, pos, &b) && b == '\n';
 }
 
 /* True iff a line-break scalar ends exactly at logical position pos (pos > 0),
  * i.e. pos is immediately after a newline. */
 static bool view_break_before(const match_view* v, size_t pos) {
   if (pos == 0) return false;
   if (v->mode != KIT_GRAM_LEX_INPUT_UTF8) {
     unsigned char b = 0;
     return view_byte(v, pos - 1, &b) && b == '\n';
   }
   /* Walk back over UTF-8 continuation bytes to the lead byte, then decode
    * forward and require the scalar to end exactly at pos. */
   size_t start = pos - 1;
   unsigned char b = 0;
   while (start > 0) {
     if (!view_byte(v, start, &b)) return false;
     if ((b & 0xC0u) != 0x80u) break; /* not a continuation byte */
     if (pos - start >= 4) return false;
     start--;
   }
   unsigned char tmp[4];
   size_t n = view_gather(v, start, tmp, sizeof tmp);
   uint32_t cp = 0;
   size_t nbytes = 0;
   if (kit_gram_utf8_decode_one(tmp, n, &cp, &nbytes) != KIT_GRAM_UTF8_OK) return false;
   return start + nbytes == pos && kit_gram_unicode_is_line_break(cp);
 }
 
 /* Longest-match DFA scan from logical position `start`, honoring edge anchors
  * structurally: the start-of-match context picks the start state, and at each
  * length the highest-priority accept whose end context holds wins. Mirrors
  * scan_one over a resident view — running out of bytes is simply end of text,
  * so there is no NEED_MORE. */
 static bool match_scan(const KitGramLexGrammar* g, const match_view* v,
                        size_t start, bool multiline, uint16_t* accept_out,
                        size_t* len_out) {
   KitGramLexInputSpan* span;
   size_t off;
   if (!view_locate(v, start, &span, &off)) return false;
 
   const uint8_t* class_of = g->class_of;
   const uint16_t* trans = g->trans;
   const uint16_t stride = g->class_stride ? g->class_stride : g->nclasses;
   const bool has_end = g->accept_text || g->accept_line;
 
   uint16_t state = 0;
   if (g->start_text || g->start_line) {
     bool ts = start == 0;
     bool ls = ts || view_break_before(v, start);
     state = lex_start_state(g, multiline, ts, ls);
   }
   uint16_t best_accept = KIT_GRAM_LEX_ACCEPT_NONE;
   size_t best_len = 0, seen = 0;
 
   if (!has_end) {
     const uint16_t* accept_tbl = g->accept;
     while (span) {
       const unsigned char* buf = span->bytes;
       size_t len = span->len;
       while (off < len) {
         uint16_t next = trans[(size_t)state * stride + class_of[buf[off]]];
         if (next == KIT_GRAM_LEX_DEAD) goto done;
         state = next;
         off++;
         seen++;
         uint16_t acc = accept_tbl[state];
         if (acc != KIT_GRAM_LEX_ACCEPT_NONE) {
           best_accept = acc;
           best_len = seen;
         }
       }
       span = span->next;
       off = 0;
     }
   done:
     if (best_accept == KIT_GRAM_LEX_ACCEPT_NONE) return false;
     *accept_out = best_accept;
     *len_out = best_len;
     return true;
   }
 
   const bool want_break = g->accept_line && multiline;
   for (;;) {
     bool at_text_end = start + seen == v->total;
     bool before_break =
         !at_text_end && want_break && view_break_at(v, start + seen);
     uint16_t cand =
         lex_pick_accept(g, state, at_text_end, before_break, multiline);
     if (cand != KIT_GRAM_LEX_ACCEPT_NONE) {
       best_accept = cand;
       best_len = seen;
     }
     while (span && off >= span->len) {
       span = span->next;
       off = 0;
     }
     if (!span) break;
     uint16_t next = trans[(size_t)state * stride + class_of[span->bytes[off]]];
     if (next == KIT_GRAM_LEX_DEAD) break;
     state = next;
     off++;
     seen++;
   }
   if (best_accept == KIT_GRAM_LEX_ACCEPT_NONE) return false;
   *accept_out = best_accept;
   *len_out = best_len;
   return true;
 }
 
 static bool match_valid(const KitGramLexGrammar* g, const KitGramLexInput* in) {
   return g && in && g->trans && g->accept && g->accepts && g->nclasses &&
          g->nstates && (!g->class_stride || g->class_stride >= g->nclasses) &&
          !cin_impl(in)->failed;
 }
 
 /* Byte i of a match at logical offset `base` of the view (in range by
  * construction, since the match length came from the same span list). */
 typedef struct {
   const match_view* v;
   size_t base;
 } view_kw_ud;
 static unsigned char view_kw_byte(void* ud, size_t i) {
   const view_kw_ud* u = ud;
   unsigned char b = 0;
   view_byte(u->v, u->base + i, &b);
   return b;
 }
 
 static const unsigned char* view_contiguous(const match_view* v, size_t base,
                                             size_t len) {
   KitGramLexInputSpan* s;
   size_t off;
   if (!view_locate(v, base, &s, &off))
     return len ? NULL : (const unsigned char*)"";
   return off + len <= s->len ? s->bytes + off : NULL;
 }
 
 /* Longest match at exactly logical position `from`, honoring in-pattern
  * anchors. Writes [from, from+len) and kind on success. Extracted keywords are
  * rewritten the same way the tokenizer does, so a Set match reports the same
  * winning kind whether or not the literal was pulled out of the DFA. */
 static bool match_one_at(const KitGramLexGrammar* g, const match_view* v,
                          bool multiline, size_t from, KitGramMatch* out) {
   uint16_t accept = KIT_GRAM_LEX_ACCEPT_NONE;
   size_t len = 0;
   if (!match_scan(g, v, from, multiline, &accept, &len)) return false;
   if (accept >= g->naccepts) return false;
   const KitGramLexAccept* a = &g->accepts[accept];
   KitGramTokenKind kind = a->tok;
   if (g->nkeyword_tables) {
     const KitGramLexKeywordTable* kt = keyword_table_for(g, a->tok);
     KitGramTokenKind kw_kind;
     if (kt) {
       const unsigned char* bytes = view_contiguous(v, from, len);
       if (bytes) {
         if (kw_lookup_bytes(kt, bytes, len, &kw_kind)) kind = kw_kind;
       } else {
         view_kw_ud ud = {v, from};
         if (kw_lookup_indirect(kt, view_kw_byte, &ud, len, &kw_kind))
           kind = kw_kind;
       }
     }
   }
   out->start = from;
   out->end = from + len;
   out->kind = kind;
   return true;
 }
 
 static match_view view_of(const KitGramLexInput* in) {
   const kit_gram_lex_input_impl* imp = cin_impl(in);
   match_view v = {imp->head, imp->off, 0,
                   imp->mode_set ? imp->mode : KIT_GRAM_LEX_INPUT_BYTES};
   for (KitGramLexInputSpan* s = imp->head; s; s = s->next) {
     size_t base = s == imp->head ? imp->off : 0;
     if (s->len > base) v.total += s->len - base;
   }
   return v;
 }
 
 void kit_gram_matcher_bind(KitGramMatcher* m, const KitGramLexGrammar* g) {
   matcher_impl(m)->g = g;
 }
 
 bool kit_gram_match_anchored(KitGramMatcher* m, KitGramLexInput* in,
                          const KitGramMatchOpts* opts, KitGramMatch* out) {
   const KitGramLexGrammar* g = matcher_impl(m)->g;
   if (!out || !match_valid(g, in)) return false;
   bool multiline = opts && opts->multiline;
   match_view v = view_of(in);
   v.mode = g->input; /* the grammar defines byte vs utf8 newline semantics */
   return match_one_at(g, &v, multiline, 0, out);
 }
 
 bool kit_gram_match_full(KitGramMatcher* m, KitGramLexInput* in,
                      const KitGramMatchOpts* opts, KitGramMatch* out) {
   const KitGramLexGrammar* g = matcher_impl(m)->g;
   if (!out || !match_valid(g, in)) return false;
   bool multiline = opts && opts->multiline;
   match_view v = view_of(in);
   v.mode = g->input; /* the grammar defines byte vs utf8 newline semantics */
   KitGramMatch m2;
   if (!match_one_at(g, &v, multiline, 0, &m2)) return false;
   if (m2.end != v.total) return false; /* the whole input must be one match */
   *out = m2;
   return true;
 }
 
 static bool match_find_from(const KitGramLexGrammar* g, const match_view* v,
                             bool multiline, size_t from, KitGramMatch* out) {
   for (size_t p = from; p < v->total; p++)
     if (match_one_at(g, v, multiline, p, out)) return true;
   return false;
 }
 
 bool kit_gram_match_find(KitGramMatcher* m, KitGramLexInput* in,
                      const KitGramMatchOpts* opts, KitGramMatch* out) {
   const KitGramLexGrammar* g = matcher_impl(m)->g;
   if (!out || !match_valid(g, in)) return false;
   bool multiline = opts && opts->multiline;
   match_view v = view_of(in);
   v.mode = g->input; /* the grammar defines byte vs utf8 newline semantics */
   return match_find_from(g, &v, multiline, 0, out);
 }
 
 void kit_gram_match_iter_init(KitGramMatchIter* it, KitGramMatcher* m,
                           KitGramLexInput* in, const KitGramMatchOpts* opts) {
   if (!it) return;
   const KitGramLexGrammar* g = matcher_impl(m)->g;
   iter_impl(it)->g = g;
   iter_impl(it)->in = in;
   iter_impl(it)->from = 0;
   iter_impl(it)->multiline = opts && opts->multiline;
 }
 
 bool kit_gram_match_iter_next(KitGramMatchIter* it, KitGramMatch* out) {
   if (!it || !out || !match_valid(iter_impl(it)->g, iter_impl(it)->in))
     return false;
   match_view v = view_of(iter_impl(it)->in);
   v.mode =
       iter_impl(it)
           ->g->input; /* the grammar defines byte vs utf8 newline semantics */
   KitGramMatch m;
   if (!match_find_from(iter_impl(it)->g, &v, iter_impl(it)->multiline,
                        iter_impl(it)->from, &m))
     return false;
   *out = m;
   iter_impl(it)->from =
       m.end > iter_impl(it)->from
           ? m.end
           : iter_impl(it)->from + 1; /* non-overlap, progress */
   return true;
 }