|
libsnobol4 1.0.2
High-performance SNOBOL4-style pattern matching library
|
Core search runtime API for libsnobol4. More...
#include <stdio.h>#include "snobol/snobol_attrs.h"#include "snobol/vm.h"#include <stdbool.h>#include <stddef.h>#include <stdint.h>

Go to the source code of this file.
Classes | |
| struct | snobol_dfa_t |
| struct | snobol_fusion_segment_t |
| struct | snobol_fusion_t |
| struct | snobol_search_meta_t |
| struct | snobol_search_result_t |
| struct | snobol_search_diag_t |
Typedefs | |
| typedef struct snobol_auto_trie_t | snobol_auto_trie_t |
| Opaque pre-allocated trie used by the Tier-5 alternation matcher. | |
| typedef struct snobol_fusion_segment_t | snobol_fusion_segment_t |
Enumerations | |
| enum | { SNOBOL_SEARCH_MAX_ALT = 32 } |
| enum | snobol_search_tier_t { TIER_BREAK_SCAN = 0 , TIER_SPAN_SCAN = 1 , TIER_LITERAL = 2 , TIER_PREFIX = 3 , TIER_BITMAP = 4 , TIER_ALT_LIT = 5 , TIER_SEARCH_VM = 6 , TIER_AUTOMATON = 7 , TIER_GENERAL = 8 , TIER_SIMD_NFA , TIER_FUSED_AUTOMATON = 10 , TIER_COUNT = 11 } |
| enum | { SNOBOL_DFA_MAX_STATES = 4096 } |
| enum | { FUSION_LIT = 0 } |
| enum | { FUSION_RUN = 1 } |
| enum | { FUSION_CHAR = 2 } |
| enum | { FUSION_ALT = 3 } |
| enum | { MAX_FUSION_SEGMENTS = 32 } |
| enum | { MAX_FUSION_ALT = 8 } |
| enum | snobol_search_skip_reason_t { SNOBOL_SEARCH_SKIP_NONE = 0 , SNOBOL_SEARCH_SKIP_LITERAL , SNOBOL_SEARCH_SKIP_FIRST_BYTE = 2 , SNOBOL_SEARCH_SKIP_BITMAP = 3 , SNOBOL_SEARCH_SKIP_BREAK_SCAN = 4 , SNOBOL_SEARCH_SKIP_SPAN_SCAN = 5 , SNOBOL_SEARCH_SKIP_JIT_COLD , SNOBOL_SEARCH_SKIP_JIT_BUDGET = 7 , SNOBOL_SEARCH_SKIP_JIT_EXIT_RATE = 8 , SNOBOL_SEARCH_BAILOUT_UNSUPPORTED , SNOBOL_SEARCH_BAILOUT_SAFETY , SNOBOL_SEARCH_BAILOUT_CANDIDATE } |
Functions | |
| void | snobol_auto_trie_free (snobol_auto_trie_t *trie) |
| 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. Read-only accessor intended for diagnostics and tests; the cache is populated lazily on the first Tier-5 search. | |
| void | snobol_search_derive_meta (const uint8_t *bc, size_t bc_len, snobol_search_meta_t *out) |
| void | snobol_search_meta_free (snobol_search_meta_t *meta) |
| void | snobol_search_vm_cleanup (VM *vm) |
| void | snobol_search_dump_cost_model (FILE *out) |
| Print the cost-model tier coefficients used by select_tier_by_cost(). | |
| 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) |
| 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) |
| snobol_search_tier_t | snobol_search_executed_tier (const snobol_search_meta_t *meta, bool dfa_available, size_t subject_len, bool anchored) |
| snobol_dfa_t * | build_dfa (const uint8_t *bc, size_t bc_len, const VM *vm) |
| bool | check_simd_eligible (const uint8_t *bc, size_t bc_len) |
| 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) |
| snobol_auto_trie_t * | snobol_build_alt_trie (const uint8_t *bc, size_t bc_len) |
| void | snobol_dfa_free (snobol_dfa_t *dfa) |
| bool | snobol_pattern_automaton_available (const struct snobol_pattern *pattern) |
| 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) |
Core search runtime API for libsnobol4.
Provides search-from-offset, find-next-match, split-over-subject, and replace-over-subject execution paths that operate within one native C control loop, avoiding PHP-level offset iteration.
The search runtime is language-agnostic: it depends only on the compiled bytecode, the VM structure, and standard C library primitives.
Search execution is dispatched through a function pointer table indexed by meta->tier (snobol_search_tier_t). Each tier represents a matching strategy with different performance characteristics:
Tier 0: BREAK/BREAKX ASCII bitmap scan Tier 1: SPAN ASCII bitmap scan Tier 2: Literal-only fast path (no VM) Tier 3: Literal prefix (memmem/memchr) Tier 4: Candidate-set bitmap for single-char alternation Tier 5: Alternation-of-literals (trie-based) Tier 6: Search-VM (lightweight backtracking NFA) Tier 7: DFA automaton (O(n) linear scan) Tier 8: General VM fallback (full SNOBOL4 VM) Tier 9: SIMD Thompson NFA (AVX2/NEON-accelerated byte-parallel NFA) Tier 10: Fused concat-pattern automaton (no VM)
Lightweight VM state (~1.6 KB) for Tier 6-7 execution. Contains bytecode pointer, subject pointer, instruction/position pointers, range metadata, choice stack, loop counters, and (for Tier 6 capture-aware) capture and variable registers. Lower tiers use only bc/ip/pos; the extra fields are ignored.
snobol_search_meta_t.flags packs 16 boolean flags into a uint32_t for single-word access. Each flag corresponds to a META_* constant defined below. The tier field (uint8_t) stores the pre-computed tier index for single-dispatch routing via tier_table[meta->tier].
Definition in file search.h.
| #define SNOBOL_DFA_DEAD UINT16_MAX |
| #define snobol_meta_alt_literals_flat | ( | m | ) |
| #define snobol_meta_always_consumes | ( | m | ) |
| #define snobol_meta_ascii_class_only | ( | m | ) |
| #define snobol_meta_automaton_eligible | ( | m | ) |
| #define snobol_meta_fusion_eligible | ( | m | ) |
| #define snobol_meta_has_bmh_skip | ( | m | ) |
| #define snobol_meta_has_candidate_bitmap | ( | m | ) |
| #define snobol_meta_has_first_byte | ( | m | ) |
| #define snobol_meta_has_literal_prefix | ( | m | ) |
| #define snobol_meta_has_required_lit | ( | m | ) |
| #define snobol_meta_has_start_bitmap | ( | m | ) |
| #define snobol_meta_is_alt_literals | ( | m | ) |
| #define snobol_meta_is_break_family | ( | m | ) |
| #define snobol_meta_is_breakx | ( | m | ) |
| #define snobol_meta_is_literal_only | ( | m | ) |
| #define snobol_meta_is_single_char_alt | ( | m | ) |
| #define snobol_meta_is_span_family | ( | m | ) |
| #define snobol_meta_may_match_empty | ( | m | ) |
| #define snobol_meta_search_vm_eligible | ( | m | ) |
| #define snobol_meta_simd_eligible | ( | m | ) |
| #define SNOBOL_SEARCH_MAX_PREFIX 16 |
| typedef struct snobol_auto_trie_t snobol_auto_trie_t |
Opaque pre-allocated trie used by the Tier-5 alternation matcher.
The full definition lives in search.c (it is a ~7 KB fixed pool). Callers (e.g. snobol_pattern_t) only ever hold a pointer, so the struct body is intentionally not exposed here.
| typedef struct snobol_fusion_segment_t snobol_fusion_segment_t |
| anonymous enum |
| anonymous enum |
| enum snobol_search_tier_t |
| Enumerator | |
|---|---|
| TIER_BREAK_SCAN | BREAK/BREAKX with ASCII bitmap scan |
| TIER_SPAN_SCAN | SPAN with ASCII bitmap scan |
| TIER_LITERAL | Literal-only fast path (no VM) |
| TIER_PREFIX | Literal prefix (memmem / memchr) |
| TIER_BITMAP | Candidate-set bitmap for single-char alt |
| TIER_ALT_LIT | Alternation-of-literals (trie-based) |
| TIER_SEARCH_VM | Search-VM for eligible patterns |
| TIER_AUTOMATON | DFA automaton for eligible patterns |
| TIER_GENERAL | General VM fallback with start-byte bitmap |
| TIER_SIMD_NFA | SIMD-accelerated Thompson NFA for charclass patterns |
| TIER_FUSED_AUTOMATON | Fused concat-pattern automaton (no VM) |
| TIER_COUNT | Number of tiers (sentinel) |
| snobol_dfa_t * build_dfa | ( | const uint8_t * | bc, |
| size_t | bc_len, | ||
| const VM * | vm ) |
Build a DFA from search-VM-eligible bytecode via powerset construction. Returns NULL on allocation failure or state explosion (>4096 states). The caller owns the returned DFA (free with snobol_dfa_free()).
| bool check_simd_eligible | ( | const uint8_t * | bc, |
| size_t | bc_len ) |
Check whether a pattern is eligible for SIMD NFA execution.
Returns true when the bytecode contains only character-class ops (SPAN, BREAK, ANY, NOTANY) with no side effects, captures, or complex control flow. All character classes must be ASCII-only.
| bc | Compiled bytecode buffer |
| bc_len | Bytecode length |
| void snobol_auto_trie_free | ( | snobol_auto_trie_t * | trie | ) |
Free a cached trie previously built by the Tier-5 matcher. Safe on NULL.
| snobol_auto_trie_t * snobol_build_alt_trie | ( | const uint8_t * | bc, |
| size_t | bc_len ) |
Build an alt-literals trie from SPLIT/LIT bytecode.
Walks the bytecode starting at offset 0, following SPLIT branches and collecting OP_LIT leaves into a trie (stack-allocated ~7 KB pool). Returns NULL on allocation failure or if the bytecode is not a valid alt-literals SPLIT tree. The caller owns the returned trie and must free it with snobol_auto_trie_free().
| void snobol_dfa_free | ( | snobol_dfa_t * | dfa | ) |
Free a DFA allocated by build_dfa(). Called from snobol_pattern_free() in api.c.
| void snobol_fusion_free | ( | snobol_fusion_t * | fusion | ) |
Free heap-allocated fusion struct and its ALT sub-lists. Safe on NULL.
| bool snobol_pattern_automaton_available | ( | const struct snobol_pattern * | pattern | ) |
Check whether a pattern has a usable DFA automaton. Returns true when the DFA is constructed and its state count is under the SNOBOL_DFA_MAX_STATES cap (i.e. construction did not abort).
| 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. Read-only accessor intended for diagnostics and tests; the cache is populated lazily on the first Tier-5 search.
| void snobol_search_derive_meta | ( | const uint8_t * | bc, |
| size_t | bc_len, | ||
| snobol_search_meta_t * | out ) |
Derive search candidate metadata from compiled pattern bytecode.
Call once after compilation; store alongside the compiled pattern for fast retrieval on each search invocation. The function always writes to *out (all fields default to false/0 when the pattern has no analyzable structure).
| bc | Compiled bytecode buffer (read-only) |
| bc_len | Bytecode length in bytes |
| out | Output metadata struct (caller-allocated) |
| void snobol_search_dump_cost_model | ( | FILE * | out | ) |
Print the cost-model tier coefficients used by select_tier_by_cost().
Diagnostic aid for recalibrating the per-tier setup/throughput costs from bench_probe output. The authoritative values live in core/src/search.c (k_tier_cost); this prints them so the probe and other diagnostics share a single source of truth.
| out | Stream to write to (NULL is treated as stdout). |
| 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 ) |
Execute a single search over [subject, subject+subject_len) from start_offset, returning the first non-overlapping match using one native C control loop.
The caller must populate vm->bc and vm->bc_len with the match pattern bytecode and may set vm->eval_fn, vm->emit_fn, and related callback fields before calling. The function manages vm->s, vm->len, vm->pos, and vm->ip internally for each candidate position.
After a successful return, vm->var_start, vm->var_end, and vm->var_count reflect the captures from the winning match.
| vm | Partially-initialised VM (bc/bc_len + callbacks set) |
| subject | Full subject string pointer |
| subject_len | Subject length in bytes |
| start_offset | Byte offset to start searching from (0 = beginning) |
| meta | Optional pre-derived metadata for acceleration (NULL = derive inline) |
| dfa | Optional pre-built DFA for the automaton tier (NULL = none) |
| out_result | Output: match position (always written; success=false on no match) |
| diag | Optional diagnostics output (may be NULL) |
| 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 ) |
Anchored (SNOBOL-style) match entry point used by Pattern::match().
Equivalent to snobol_search_exec() with start_offset = 0 and the anchored flag set: the match must begin exactly at offset 0. The cost-model tier selection excludes scanning tiers (BREAK/SPAN/PREFIX) and any match that does not start at the anchor is rejected. This routes anchored matching through the cheaper cost-model tiers instead of forcing the full VM.
| vm | Partially-initialised VM (bc/bc_len + callbacks set) |
| subject | Full subject string pointer |
| subject_len | Subject length in bytes |
| meta | Optional pre-derived metadata (NULL = derive inline) |
| dfa | Optional DFA for automaton acceleration (NULL = none) |
| out_result | Output: match position (always written; success=false on no match) |
| diag | Optional diagnostics output (may be NULL) |
| snobol_search_tier_t snobol_search_executed_tier | ( | const snobol_search_meta_t * | meta, |
| bool | dfa_available, | ||
| size_t | subject_len, | ||
| bool | anchored ) |
Diagnostic readout: return the executed dispatch tier that dispatch_search_impl() would select for the given metadata and subject, distinct from the structural tier reported by snobol_pattern_get_meta() -> meta.tier.
The cost model (select_tier_by_cost) may promote a structurally SEARCH_VM pattern to the AUTOMATON tier when a DFA is available, so benchmarks that label scenarios by meta->tier mislabel the real path. This function lets the probe (and external callers) measure the tier actually executed.
| meta | Pre-derived search metadata (e.g. from snobol_pattern_get_meta()). |
| dfa_available | True when the caller would supply a DFA (enables the Tier-7 automaton override); false otherwise. |
| subject_len | Subject length in bytes. |
| anchored | True for anchored (Pattern::match) matching. |
| void snobol_search_meta_free | ( | snobol_search_meta_t * | meta | ) |
Free heap-allocated fields in a metadata struct.
Must be called when a metadata struct is no longer needed and was populated by snobol_search_derive_meta(). Currently frees the bmh_skip table if allocated.
| meta | Metadata struct to clean up (NULL is safe). |
| void snobol_search_vm_cleanup | ( | VM * | vm | ) |
Free heap-allocated fields in a VM used by the search runtime.
Releases the Pike thread/defer buffers and choice arena that may have been allocated during snobol_search_exec() or snobol_search_exec_anchored(). Safe to call on a zero-initialised or already-cleaned VM (fields are NULL).
| vm | VM struct to clean up (NULL is safe). |
| 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 ) |
Tier 10: Fused concat-pattern execution entry point.
Executes fusible concat patterns (LIT/SPAN/ANY/NOTANY/BREAK chains) via a dedicated lightweight engine — no VM, no bytecode dispatch, no choice stack.
| 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 ) |
Tier 9: SIMD-accelerated Thompson NFA entry point.
Processes eligible character-class patterns (SPAN, BREAK, ANY, NOTANY with ASCII-only ranges) using SIMD instructions when available, falling back to a scalar reference implementation for short subjects and non-SIMD platforms.
| vm | VM with bc/bc_len set for the pattern |
| subject | Subject string |
| subject_len | Subject length |
| start_offset | Search start offset |
| meta | Pre-derived metadata (unused, must be non-NULL) |
| dfa | Unused (must be NULL) |
| out_result | Match result |
| diag | Diagnostics (may be NULL) |
| anchored | Whether the match must begin exactly at start_offset |