libsnobol4 1.0.2
High-performance SNOBOL4-style pattern matching library
Loading...
Searching...
No Matches
search.h
Go to the documentation of this file.
1#pragma once
2
3#ifdef __cplusplus
4extern "C" {
5#endif
6
7
8#include <stdio.h>
9
54
55#include "snobol/snobol_attrs.h"
56#include "snobol/vm.h"
57#include <stdbool.h>
58#include <stddef.h>
59#include <stdint.h>
60
61struct snobol_pattern; /* forward decl — only used as an opaque pointer */
62
63/* ---------------------------------------------------------------------------
64 * Search candidate metadata
65 *
66 * Derived once from compiled bytecode; stored alongside patterns for fast
67 * retrieval on each search invocation. Allows the search loop to skip
68 * unpromising candidate positions before invoking the general VM matcher.
69 * ---------------------------------------------------------------------------
70 */
71
73#define SNOBOL_SEARCH_MAX_PREFIX 16
74
77
78/* ---------------------------------------------------------------------------
79 * Tier constants for single-dispatch routing
80 *
81 * Each tier corresponds to a matching strategy in snobol_search_exec().
82 * The tier is computed at compile time and stored in snobol_search_meta_t.tier.
83 * ---------------------------------------------------------------------------
84 */
100
101/* ---------------------------------------------------------------------------
102 * Metadata flag bit constants
103 *
104 * Packed into snobol_search_meta_t.flags for single-word access.
105 * ---------------------------------------------------------------------------
106 */
107#define META_HAS_LITERAL_PREFIX (1u << 0)
108#define META_HAS_FIRST_BYTE (1u << 1)
109#define META_HAS_CANDIDATE_BITMAP (1u << 2)
110#define META_MAY_MATCH_EMPTY (1u << 3)
111#define META_ALWAYS_CONSUMES (1u << 4)
112#define META_IS_SINGLE_CHAR_ALT (1u << 5)
113#define META_IS_BREAK_FAMILY (1u << 6)
114#define META_IS_SPAN_FAMILY (1u << 7)
115#define META_IS_BREAKX (1u << 8)
116#define META_ASCII_CLASS_ONLY (1u << 9)
117#define META_HAS_START_BITMAP (1u << 10)
118#define META_AUTOMATON_ELIGIBLE (1u << 11)
119#define META_IS_ALT_LITERALS (1u << 12)
120#define META_HAS_BMH_SKIP (1u << 13)
121#define META_IS_LITERAL_ONLY (1u << 14)
122#define META_SEARCH_VM_ELIGIBLE (1u << 15)
123#define META_SIMD_ELIGIBLE (1u << 16)
124#define META_IS_ALT_LITERALS_FLAT (1u << 17)
125#define META_HAS_REQUIRED_LIT (1u << 18)
126#define META_FUSION_ELIGIBLE (1u << 19)
127
128/* ---------------------------------------------------------------------------
129 * Automaton (DFA) types
130 *
131 * Constructed from search-VM-eligible bytecode via powerset construction.
132 * Enables O(n) single-pass matching over the subject.
133 * ---------------------------------------------------------------------------
134 */
135
137#define SNOBOL_DFA_DEAD UINT16_MAX
138
140enum { SNOBOL_DFA_MAX_STATES = 4096 };
141
148typedef struct {
149 uint16_t *trans;
150 uint32_t num_states;
151 uint8_t *
153 uint16_t start_state;
154 uint32_t state_cap;
156
165
168
169/* ---------------------------------------------------------------------------
170 * Pattern fusion types
171 *
172 * The fusion engine compiles concat chains of compatible ops (LIT, SPAN,
173 * ANY, NOTANY, BREAK) into a flat segment list. exec_fusion() walks the
174 * segment list directly — no VM, no bytecode dispatch, no choice stack.
175 * ---------------------------------------------------------------------------
176 */
177
178enum { FUSION_LIT = 0 };
179enum { FUSION_RUN = 1 };
180enum { FUSION_CHAR = 2 };
181enum { FUSION_ALT = 3 };
182
184enum { MAX_FUSION_ALT = 8 };
185
187 uint8_t type;
188 union {
189 struct {
190 const uint8_t *data;
191 uint32_t len;
193 struct {
194 uint8_t bitmap[32];
195 uint32_t min;
197 struct {
198 uint8_t bitmap[32];
200 struct {
203 uint32_t alt_count;
205 };
207
212
217 const struct snobol_pattern *pattern);
218
219typedef struct {
220 /* Packed flags and tier index ------------------------------------------ */
221 uint32_t flags;
222 uint8_t tier;
223
227
228 /* First-byte candidate ------------------------------------------------- */
229 /* When has_first_byte is true, every match MUST start with first_byte.
230 * Enables memchr-based position skipping when prefix_len >= 1. */
232 uint8_t first_byte;
233
234 /* Candidate-set bitmap ------------------------------------------------- */
235 /* Each set bit i means a match MAY start with byte i (0-127).
236 * Used for alternation-of-single-chars and similar patterns. */
238 uint64_t candidate_bitmap[2]; /* 128-bit ASCII bitmap */
239
240 /* Empty-match flag ----------------------------------------------------- */
241 /* When true, the pattern can succeed while consuming zero bytes;
242 * the search loop must advance unconditionally after an empty match. */
244
245 /* Always-consuming flag ------------------------------------------------ */
246 /* When true, the pattern consumes at least one byte on success.
247 * The search loop may advance by (match_end - match_start) safely. */
249
250 /* Single-char alternation ---------------------------------------------- */
251 /* True if the root pattern is a pure alternation of single-character
252 * literals; these can be collapsed to a candidate-set for one-pass scan. */
255 size_t alt_count;
256
257 /* BREAK / SPAN / BREAKX classification --------------------------------- */
258 /* True if the first effective opcode is BREAK, BREAKX, or SPAN. */
263 uint64_t class_bitmap[2];
264
265 /* Start-byte bitmap ---------------------------------------------------- */
266 /* 256-bit bitmap: bit i is set when the pattern can match starting with
267 * byte value i. Computed by derive_meta for ALL patterns.
268 * Allows the search loop to reject candidate positions whose subject byte
269 * is not in the bitmap (inspired by PCRE2's start_bits). */
271 uint8_t start_bitmap[32];
272
273 /* Minimum match length (in bytes) -------------------------------------- */
274 /* Lower bound on the number of subject bytes consumed by a successful
275 * match. Zero when unknown. Inspired by PCRE2's find_minlength. */
276 uint32_t minlength;
277
278 /* Automaton eligibility ------------------------------------------------ */
279 /* True if the pattern is eligible for the lightweight automaton path:
280 * ASCII-only, side-effect free (no EVAL/ASSIGN/EMIT ops), and structurally
281 * local (no DYNAMIC). */
283
284 /* Alternation-of-literals detection ----------------------------------- */
285 /* True when the pattern is a flat alternation of literal strings
286 * (e.g. "abc" | "def" | "ghi"). Enables trie-based multi-string matching
287 * (Tier 3a) which replaces the general VM loop for these patterns. */
289
290 /* True when the alt-literals trie is "flat": the alternatives share no
291 * common prefix, so the trie provides no benefit over the general VM.
292 * Detected at derive_meta time; flat alt-literals are routed to
293 * TIER_GENERAL instead of TIER_ALT_LIT (fixes the 125x regression). */
295
296 /* Boyer-Moore-Horspool skip table -------------------------------------- */
297 /* When has_bmh_skip is true, bmh_skip[byte] gives the distance to advance
298 * the search position after a VM failure at the current candidate. The
299 * table is computed from the literal prefix (bmh_skip_len) and allows the
300 * search loop to skip more than one byte at a time for literal-leading
301 * patterns that fall through to the general VM or automaton paths.
302 *
303 * The skip value is computed for the byte at subject[pos + bmh_skip_len - 1]
304 * and is valid as long as pos + bmh_skip_len <= subject_len.
305 * bmh_skip_len is identical to literal_prefix_len when has_bmh_skip is set. */
307 uint8_t *bmh_skip;
309
310 /* Literal-only detection ------------------------------------------------ */
311 /* True when the pattern is a single literal followed by ACCEPT (optionally
312 * with zero-width assertions like POS/RPOS/ANCHOR between). Enables a
313 * fast memmem/memcmp path that bypasses the VM entirely. */
315
316 /* Search-VM eligibility ------------------------------------------------- */
317 /* True when the pattern contains only opcodes from the safe set supported
318 * by the lightweight search-VM (search_vm_exec). The safe set includes
319 * LIT, LEN, ANY, NOTANY, SPAN, BREAK, JMP, SPLIT, POS, RPOS, TAB, RTAB,
320 * ANCHOR, FENCE, NOP, REPEAT_INIT, REPEAT_STEP, ACCEPT, FAIL, ABORT,
321 * SUCCEED. Patterns with EVAL, ASSIGN, CAP_START, CAP_END, EMIT_*,
322 * DYNAMIC, TABLE_*, ARRAY_*, GOTO, GOTO_F, LABEL, BAL, REM, BREAKX are
323 * NOT eligible. */
325
326 /* Required-byte pre-filter ----------------------------------------------- */
327 /* The longest literal that MUST appear in the subject for a match to exist.
328 * When required_lit_len > 0, dispatch_search_impl runs a memchr/memmem
329 * scan before any tier and returns false (with prefilter_skip=true) when
330 * the literal is absent. Derived from the rightmost literal(s) before
331 * ACCEPT/SUCCEED along all paths. */
335
336 /* Capture presence ------------------------------------------------------- */
337 /* True when the bytecode contains any OP_CAP_START / OP_CAP_END (or
338 * OP_EMIT_CAPTURE). Only TIER_SEARCH_VM (6) and TIER_GENERAL (8) can record
339 * captures; all other tiers silently drop them. derive_meta uses this to
340 * gate the non-capturing eligibility flags off so captured patterns are
341 * never routed to a tier that would lose the capture. */
343
344 /* Register-state usage (D3) ------------------------------------------------
345 * Fine-grained liveness for the register arrays a search-VM execution can
346 * touch. has_assign is set when OP_ASSIGN can write variable registers;
347 * has_counter when REPEAT_INIT/REPEAT_STEP can touch loop counters. The
348 * restart loop zeroes only the register classes the pattern provably uses
349 * (captures implied by has_capture). Conservative derivation: an op the
350 * walker cannot classify marks every class used. */
353
354 /* SIMD NFA eligibility -------------------------------------------------- */
355 /* True when the pattern is eligible for the SIMD-accelerated NFA path:
356 * ASCII-only character-class operations (SPAN, BREAK, ANY, NOTANY) with
357 * no side effects, captures, or complex control flow. Patterns that pass
358 * are routed to Tier 9 (TIER_SIMD_NFA). */
360
361 /* Fusion eligibility --------------------------------------------------- */
362 /* True when the pattern is a concat of fusible ops (LIT, SPAN, ANY,
363 * NOTANY, BREAK) with no captures, EVAL, or side effects. When true,
364 * `fusion` points to the compiled segment list and `tier` is set to
365 * TIER_FUSED_AUTOMATON. */
369
370/* ---------------------------------------------------------------------------
371 * Metadata flag accessor macros
372 *
373 * Type-safe bitfield access for snobol_search_meta_t.flags.
374 * Each macro tests exactly one bit; arguments are evaluated once.
375 * ---------------------------------------------------------------------------
376 */
377#define snobol_meta_has_literal_prefix(m) \
378 (!!((m)->flags & META_HAS_LITERAL_PREFIX))
379#define snobol_meta_has_first_byte(m) (!!((m)->flags & META_HAS_FIRST_BYTE))
380#define snobol_meta_has_candidate_bitmap(m) \
381 (!!((m)->flags & META_HAS_CANDIDATE_BITMAP))
382#define snobol_meta_may_match_empty(m) (!!((m)->flags & META_MAY_MATCH_EMPTY))
383#define snobol_meta_always_consumes(m) (!!((m)->flags & META_ALWAYS_CONSUMES))
384#define snobol_meta_is_single_char_alt(m) \
385 (!!((m)->flags & META_IS_SINGLE_CHAR_ALT))
386#define snobol_meta_is_break_family(m) (!!((m)->flags & META_IS_BREAK_FAMILY))
387#define snobol_meta_is_span_family(m) (!!((m)->flags & META_IS_SPAN_FAMILY))
388#define snobol_meta_is_breakx(m) (!!((m)->flags & META_IS_BREAKX))
389#define snobol_meta_ascii_class_only(m) (!!((m)->flags & META_ASCII_CLASS_ONLY))
390#define snobol_meta_has_start_bitmap(m) (!!((m)->flags & META_HAS_START_BITMAP))
391#define snobol_meta_automaton_eligible(m) \
392 (!!((m)->flags & META_AUTOMATON_ELIGIBLE))
393#define snobol_meta_is_alt_literals(m) (!!((m)->flags & META_IS_ALT_LITERALS))
394#define snobol_meta_alt_literals_flat(m) \
395 (!!((m)->flags & META_IS_ALT_LITERALS_FLAT))
396#define snobol_meta_has_bmh_skip(m) (!!((m)->flags & META_HAS_BMH_SKIP))
397#define snobol_meta_is_literal_only(m) (!!((m)->flags & META_IS_LITERAL_ONLY))
398#define snobol_meta_search_vm_eligible(m) \
399 (!!((m)->flags & META_SEARCH_VM_ELIGIBLE))
400#define snobol_meta_simd_eligible(m) (!!((m)->flags & META_SIMD_ELIGIBLE))
401#define snobol_meta_has_required_lit(m) (!!((m)->flags & META_HAS_REQUIRED_LIT))
402#define snobol_meta_fusion_eligible(m) (!!((m)->flags & META_FUSION_ELIGIBLE))
403
412/* Verify tier field is within the first cache line (64 bytes)
413 * so that dispatch decisions don't pull in the full metadata struct. */
414static_assert(
415 offsetof(snobol_search_meta_t, tier) < 64,
416 "tier field must be within first 64 bytes of snobol_search_meta_t");
417
418static inline void snobol_meta_set_flag(snobol_search_meta_t *m,
419 uint32_t flag) {
420 m->flags |= flag;
421}
422
423/* ---------------------------------------------------------------------------
424 * Search execution result
425 * ---------------------------------------------------------------------------
426 */
445
446/* ---------------------------------------------------------------------------
447 * Search-mode skip/bailout reason codes
448 *
449 * Used in diagnostics to distinguish expected candidate rejection from
450 * unsupported control flow or safety fallbacks.
451 * ---------------------------------------------------------------------------
452 */
472
473/* ---------------------------------------------------------------------------
474 * Per-search-invocation diagnostics
475 *
476 * Populated by snobol_search_exec() when a non-NULL pointer is passed.
477 * ---------------------------------------------------------------------------
478 */
487
488/* ---------------------------------------------------------------------------
489 * API
490 * ---------------------------------------------------------------------------
491 */
492
504void snobol_search_derive_meta(const uint8_t *bc, size_t bc_len,
506
517
528
540
568SNOBOL_NODISCARD bool snobol_search_exec(
569 VM *vm, const char *subject, size_t subject_len, size_t start_offset,
570 const snobol_search_meta_t *meta, const snobol_dfa_t *dfa,
572
592SNOBOL_NODISCARD bool snobol_search_exec_anchored(
593 VM *vm, const char *subject, size_t subject_len,
594 const snobol_search_meta_t *meta, const snobol_dfa_t *dfa,
596
617 const snobol_search_meta_t *meta, bool dfa_available, size_t subject_len,
618 bool anchored);
619
625snobol_dfa_t *build_dfa(const uint8_t *bc, size_t bc_len, const VM *vm);
626
627/* Forward declaration — complete type in snobol/snobol.h */
628struct snobol_pattern;
629
641bool check_simd_eligible(const uint8_t *bc, size_t bc_len);
642
661bool tier_simd_nfa(VM *vm, const char *subject, size_t subject_len,
662 size_t start_offset, const snobol_search_meta_t *meta,
663 const snobol_dfa_t *dfa, snobol_search_result_t *out_result,
664 snobol_search_diag_t *diag, bool anchored);
665
675snobol_auto_trie_t *snobol_build_alt_trie(const uint8_t *bc, size_t bc_len);
676
682
688bool snobol_pattern_automaton_available(const struct snobol_pattern *pattern);
689
695
703bool tier_fusion(VM *vm, const char *subject, size_t subject_len,
704 size_t start_offset, const snobol_search_meta_t *meta,
705 const snobol_dfa_t *dfa, snobol_search_result_t *out_result,
706 snobol_search_diag_t *diag, bool anchored);
707
708#ifdef __cplusplus
709}
710#endif
@ FUSION_CHAR
Definition search.h:180
@ MAX_FUSION_SEGMENTS
Definition search.h:183
bool snobol_search_exec(VM *vm, const char *subject, size_t subject_len, size_t start_offset, const snobol_search_meta_t *meta, const snobol_dfa_t *dfa, snobol_search_result_t *out_result, snobol_search_diag_t *diag)
struct snobol_auto_trie_t snobol_auto_trie_t
Opaque pre-allocated trie used by the Tier-5 alternation matcher.
Definition search.h:164
bool check_simd_eligible(const uint8_t *bc, size_t bc_len)
snobol_search_tier_t snobol_search_executed_tier(const snobol_search_meta_t *meta, bool dfa_available, size_t subject_len, bool anchored)
void snobol_dfa_free(snobol_dfa_t *dfa)
void snobol_search_meta_free(snobol_search_meta_t *meta)
@ MAX_FUSION_ALT
Definition search.h:184
bool snobol_search_exec_anchored(VM *vm, const char *subject, size_t subject_len, const snobol_search_meta_t *meta, const snobol_dfa_t *dfa, snobol_search_result_t *out_result, snobol_search_diag_t *diag)
bool tier_simd_nfa(VM *vm, const char *subject, size_t subject_len, size_t start_offset, const snobol_search_meta_t *meta, const snobol_dfa_t *dfa, snobol_search_result_t *out_result, snobol_search_diag_t *diag, bool anchored)
void snobol_auto_trie_free(snobol_auto_trie_t *trie)
snobol_dfa_t * build_dfa(const uint8_t *bc, size_t bc_len, const VM *vm)
bool snobol_pattern_automaton_available(const struct snobol_pattern *pattern)
@ FUSION_RUN
Definition search.h:179
void snobol_search_dump_cost_model(FILE *out)
Print the cost-model tier coefficients used by select_tier_by_cost().
@ SNOBOL_DFA_MAX_STATES
Definition search.h:140
snobol_search_skip_reason_t
Definition search.h:453
@ SNOBOL_SEARCH_SKIP_LITERAL
Definition search.h:455
@ SNOBOL_SEARCH_SKIP_NONE
Definition search.h:454
@ SNOBOL_SEARCH_SKIP_BREAK_SCAN
Definition search.h:459
@ SNOBOL_SEARCH_SKIP_JIT_EXIT_RATE
Definition search.h:464
@ SNOBOL_SEARCH_BAILOUT_UNSUPPORTED
Definition search.h:465
@ SNOBOL_SEARCH_SKIP_JIT_BUDGET
Definition search.h:463
@ SNOBOL_SEARCH_SKIP_BITMAP
Definition search.h:458
@ SNOBOL_SEARCH_SKIP_JIT_COLD
Definition search.h:461
@ SNOBOL_SEARCH_SKIP_FIRST_BYTE
Definition search.h:457
@ SNOBOL_SEARCH_SKIP_SPAN_SCAN
Definition search.h:460
@ SNOBOL_SEARCH_BAILOUT_CANDIDATE
Definition search.h:469
@ SNOBOL_SEARCH_BAILOUT_SAFETY
Definition search.h:467
snobol_search_tier_t
Definition search.h:85
@ TIER_BREAK_SCAN
Definition search.h:86
@ TIER_LITERAL
Definition search.h:88
@ TIER_ALT_LIT
Definition search.h:91
@ TIER_BITMAP
Definition search.h:90
@ TIER_GENERAL
Definition search.h:94
@ TIER_SIMD_NFA
Definition search.h:95
@ TIER_FUSED_AUTOMATON
Definition search.h:97
@ TIER_SEARCH_VM
Definition search.h:92
@ TIER_PREFIX
Definition search.h:89
@ TIER_AUTOMATON
Definition search.h:93
@ TIER_SPAN_SCAN
Definition search.h:87
@ TIER_COUNT
Definition search.h:98
void snobol_search_derive_meta(const uint8_t *bc, size_t bc_len, snobol_search_meta_t *out)
@ FUSION_LIT
Definition search.h:178
void snobol_search_vm_cleanup(VM *vm)
#define SNOBOL_SEARCH_MAX_PREFIX
Definition search.h:73
snobol_auto_trie_t * snobol_pattern_get_trie_cache(const struct snobol_pattern *pattern)
Return the pattern's cached Tier-5 alternation trie, or NULL if it has not been built yet....
@ SNOBOL_SEARCH_MAX_ALT
Definition search.h:76
void snobol_fusion_free(snobol_fusion_t *fusion)
bool tier_fusion(VM *vm, const char *subject, size_t subject_len, size_t start_offset, const snobol_search_meta_t *meta, const snobol_dfa_t *dfa, snobol_search_result_t *out_result, snobol_search_diag_t *diag, bool anchored)
@ FUSION_ALT
Definition search.h:181
snobol_auto_trie_t * snobol_build_alt_trie(const uint8_t *bc, size_t bc_len)
Portable function-attribute macros for SNOBOL4.
VM state: all mutable state for a single pattern execution.
Definition vm.h:450
uint32_t state_cap
Definition search.h:154
uint8_t * accepting
Definition search.h:152
uint16_t * trans
Definition search.h:149
uint32_t num_states
Definition search.h:150
uint16_t start_state
Definition search.h:153
struct snobol_fusion_segment_t::@236033107013075262003164050113201127364051355164::@075213112345222035105263074331127142012342106343 alt
struct snobol_fusion_segment_t::@236033107013075262003164050113201127364051355164::@267177212254254225124202022136303141037107315366 lit
struct snobol_fusion_segment_t::@236033107013075262003164050113201127364051355164::@015262335013162170013205374336275101310027212037 run
uint8_t bitmap[32]
Definition search.h:194
const uint8_t * data
Definition search.h:190
struct snobol_fusion_segment_t * alts[MAX_FUSION_ALT]
Definition search.h:201
struct snobol_fusion_segment_t::@236033107013075262003164050113201127364051355164::@040141274147077071306120076365311033220246344375 chr
uint32_t alt_lens[MAX_FUSION_ALT]
Definition search.h:202
snobol_fusion_segment_t segs[MAX_FUSION_SEGMENTS]
Definition search.h:210
uint32_t count
Definition search.h:209
uint64_t automaton_tests
Definition search.h:482
uint64_t candidates_tested
Definition search.h:480
uint64_t candidates_skipped
Definition search.h:481
snobol_search_skip_reason_t last_skip_reason
Definition search.h:485
uint64_t search_vm_tests
Definition search.h:483
uint8_t * bmh_skip
Definition search.h:307
uint8_t alt_bytes[SNOBOL_SEARCH_MAX_ALT]
Definition search.h:254
uint8_t required_lit[SNOBOL_SEARCH_MAX_PREFIX]
Definition search.h:333
uint8_t literal_prefix[SNOBOL_SEARCH_MAX_PREFIX]
Definition search.h:225
uint64_t class_bitmap[2]
Definition search.h:263
uint8_t start_bitmap[32]
Definition search.h:271
uint64_t candidate_bitmap[2]
Definition search.h:238
size_t required_lit_len
Definition search.h:334
snobol_fusion_t * fusion
Definition search.h:367
bool has_candidate_bitmap
Definition search.h:237
uint32_t minlength
Definition search.h:276
bool is_alt_literals_flat
Definition search.h:294
size_t literal_prefix_len
Definition search.h:226
Virtual machine types, opcodes, and execution API for libsnobol4.