libsnobol4 1.0.2
High-performance SNOBOL4-style pattern matching library
Loading...
Searching...
No Matches
search.h File Reference

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>
Include dependency graph for search.h:
This graph shows which files directly or indirectly include this file:

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

Macros

#define SNOBOL_SEARCH_MAX_PREFIX   16
#define META_HAS_LITERAL_PREFIX   (1u << 0)
#define META_HAS_FIRST_BYTE   (1u << 1)
#define META_HAS_CANDIDATE_BITMAP   (1u << 2)
#define META_MAY_MATCH_EMPTY   (1u << 3)
#define META_ALWAYS_CONSUMES   (1u << 4)
#define META_IS_SINGLE_CHAR_ALT   (1u << 5)
#define META_IS_BREAK_FAMILY   (1u << 6)
#define META_IS_SPAN_FAMILY   (1u << 7)
#define META_IS_BREAKX   (1u << 8)
#define META_ASCII_CLASS_ONLY   (1u << 9)
#define META_HAS_START_BITMAP   (1u << 10)
#define META_AUTOMATON_ELIGIBLE   (1u << 11)
#define META_IS_ALT_LITERALS   (1u << 12)
#define META_HAS_BMH_SKIP   (1u << 13)
#define META_IS_LITERAL_ONLY   (1u << 14)
#define META_SEARCH_VM_ELIGIBLE   (1u << 15)
#define META_SIMD_ELIGIBLE   (1u << 16)
#define META_IS_ALT_LITERALS_FLAT   (1u << 17)
#define META_HAS_REQUIRED_LIT   (1u << 18)
#define META_FUSION_ELIGIBLE   (1u << 19)
#define SNOBOL_DFA_DEAD   UINT16_MAX
#define snobol_meta_has_literal_prefix(m)
#define snobol_meta_has_first_byte(m)
#define snobol_meta_has_candidate_bitmap(m)
#define snobol_meta_may_match_empty(m)
#define snobol_meta_always_consumes(m)
#define snobol_meta_is_single_char_alt(m)
#define snobol_meta_is_break_family(m)
#define snobol_meta_is_span_family(m)
#define snobol_meta_is_breakx(m)
#define snobol_meta_ascii_class_only(m)
#define snobol_meta_has_start_bitmap(m)
#define snobol_meta_automaton_eligible(m)
#define snobol_meta_is_alt_literals(m)
#define snobol_meta_alt_literals_flat(m)
#define snobol_meta_has_bmh_skip(m)
#define snobol_meta_is_literal_only(m)
#define snobol_meta_search_vm_eligible(m)
#define snobol_meta_simd_eligible(m)
#define snobol_meta_has_required_lit(m)
#define snobol_meta_fusion_eligible(m)

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)

Detailed Description

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.

Tier Dispatch

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)

search_vm_t

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.

Metadata Bitfield Flags

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.

Macro Definition Documentation

◆ META_ALWAYS_CONSUMES

#define META_ALWAYS_CONSUMES   (1u << 4)

Definition at line 111 of file search.h.

◆ META_ASCII_CLASS_ONLY

#define META_ASCII_CLASS_ONLY   (1u << 9)

Definition at line 116 of file search.h.

◆ META_AUTOMATON_ELIGIBLE

#define META_AUTOMATON_ELIGIBLE   (1u << 11)

Definition at line 118 of file search.h.

◆ META_FUSION_ELIGIBLE

#define META_FUSION_ELIGIBLE   (1u << 19)

Definition at line 126 of file search.h.

◆ META_HAS_BMH_SKIP

#define META_HAS_BMH_SKIP   (1u << 13)

Definition at line 120 of file search.h.

◆ META_HAS_CANDIDATE_BITMAP

#define META_HAS_CANDIDATE_BITMAP   (1u << 2)

Definition at line 109 of file search.h.

◆ META_HAS_FIRST_BYTE

#define META_HAS_FIRST_BYTE   (1u << 1)

Definition at line 108 of file search.h.

◆ META_HAS_LITERAL_PREFIX

#define META_HAS_LITERAL_PREFIX   (1u << 0)

Definition at line 107 of file search.h.

◆ META_HAS_REQUIRED_LIT

#define META_HAS_REQUIRED_LIT   (1u << 18)

Definition at line 125 of file search.h.

◆ META_HAS_START_BITMAP

#define META_HAS_START_BITMAP   (1u << 10)

Definition at line 117 of file search.h.

◆ META_IS_ALT_LITERALS

#define META_IS_ALT_LITERALS   (1u << 12)

Definition at line 119 of file search.h.

◆ META_IS_ALT_LITERALS_FLAT

#define META_IS_ALT_LITERALS_FLAT   (1u << 17)

Definition at line 124 of file search.h.

◆ META_IS_BREAK_FAMILY

#define META_IS_BREAK_FAMILY   (1u << 6)

Definition at line 113 of file search.h.

◆ META_IS_BREAKX

#define META_IS_BREAKX   (1u << 8)

Definition at line 115 of file search.h.

◆ META_IS_LITERAL_ONLY

#define META_IS_LITERAL_ONLY   (1u << 14)

Definition at line 121 of file search.h.

◆ META_IS_SINGLE_CHAR_ALT

#define META_IS_SINGLE_CHAR_ALT   (1u << 5)

Definition at line 112 of file search.h.

◆ META_IS_SPAN_FAMILY

#define META_IS_SPAN_FAMILY   (1u << 7)

Definition at line 114 of file search.h.

◆ META_MAY_MATCH_EMPTY

#define META_MAY_MATCH_EMPTY   (1u << 3)

Definition at line 110 of file search.h.

◆ META_SEARCH_VM_ELIGIBLE

#define META_SEARCH_VM_ELIGIBLE   (1u << 15)

Definition at line 122 of file search.h.

◆ META_SIMD_ELIGIBLE

#define META_SIMD_ELIGIBLE   (1u << 16)

Definition at line 123 of file search.h.

◆ SNOBOL_DFA_DEAD

#define SNOBOL_DFA_DEAD   UINT16_MAX

Sentinel: no transition / DEAD state.

Definition at line 137 of file search.h.

◆ snobol_meta_alt_literals_flat

#define snobol_meta_alt_literals_flat ( m)
Value:
(!!((m)->flags & META_IS_ALT_LITERALS_FLAT))
#define META_IS_ALT_LITERALS_FLAT
Definition search.h:124

Definition at line 394 of file search.h.

◆ snobol_meta_always_consumes

#define snobol_meta_always_consumes ( m)
Value:
(!!((m)->flags & META_ALWAYS_CONSUMES))
#define META_ALWAYS_CONSUMES
Definition search.h:111

Definition at line 383 of file search.h.

◆ snobol_meta_ascii_class_only

#define snobol_meta_ascii_class_only ( m)
Value:
(!!((m)->flags & META_ASCII_CLASS_ONLY))
#define META_ASCII_CLASS_ONLY
Definition search.h:116

Definition at line 389 of file search.h.

◆ snobol_meta_automaton_eligible

#define snobol_meta_automaton_eligible ( m)
Value:
(!!((m)->flags & META_AUTOMATON_ELIGIBLE))
#define META_AUTOMATON_ELIGIBLE
Definition search.h:118

Definition at line 391 of file search.h.

◆ snobol_meta_fusion_eligible

#define snobol_meta_fusion_eligible ( m)
Value:
(!!((m)->flags & META_FUSION_ELIGIBLE))
#define META_FUSION_ELIGIBLE
Definition search.h:126

Definition at line 402 of file search.h.

◆ snobol_meta_has_bmh_skip

#define snobol_meta_has_bmh_skip ( m)
Value:
(!!((m)->flags & META_HAS_BMH_SKIP))
#define META_HAS_BMH_SKIP
Definition search.h:120

Definition at line 396 of file search.h.

◆ snobol_meta_has_candidate_bitmap

#define snobol_meta_has_candidate_bitmap ( m)
Value:
(!!((m)->flags & META_HAS_CANDIDATE_BITMAP))
#define META_HAS_CANDIDATE_BITMAP
Definition search.h:109

Definition at line 380 of file search.h.

◆ snobol_meta_has_first_byte

#define snobol_meta_has_first_byte ( m)
Value:
(!!((m)->flags & META_HAS_FIRST_BYTE))
#define META_HAS_FIRST_BYTE
Definition search.h:108

Definition at line 379 of file search.h.

◆ snobol_meta_has_literal_prefix

#define snobol_meta_has_literal_prefix ( m)
Value:
(!!((m)->flags & META_HAS_LITERAL_PREFIX))
#define META_HAS_LITERAL_PREFIX
Definition search.h:107

Definition at line 377 of file search.h.

◆ snobol_meta_has_required_lit

#define snobol_meta_has_required_lit ( m)
Value:
(!!((m)->flags & META_HAS_REQUIRED_LIT))
#define META_HAS_REQUIRED_LIT
Definition search.h:125

Definition at line 401 of file search.h.

◆ snobol_meta_has_start_bitmap

#define snobol_meta_has_start_bitmap ( m)
Value:
(!!((m)->flags & META_HAS_START_BITMAP))
#define META_HAS_START_BITMAP
Definition search.h:117

Definition at line 390 of file search.h.

◆ snobol_meta_is_alt_literals

#define snobol_meta_is_alt_literals ( m)
Value:
(!!((m)->flags & META_IS_ALT_LITERALS))
#define META_IS_ALT_LITERALS
Definition search.h:119

Definition at line 393 of file search.h.

◆ snobol_meta_is_break_family

#define snobol_meta_is_break_family ( m)
Value:
(!!((m)->flags & META_IS_BREAK_FAMILY))
#define META_IS_BREAK_FAMILY
Definition search.h:113

Definition at line 386 of file search.h.

◆ snobol_meta_is_breakx

#define snobol_meta_is_breakx ( m)
Value:
(!!((m)->flags & META_IS_BREAKX))
#define META_IS_BREAKX
Definition search.h:115

Definition at line 388 of file search.h.

◆ snobol_meta_is_literal_only

#define snobol_meta_is_literal_only ( m)
Value:
(!!((m)->flags & META_IS_LITERAL_ONLY))
#define META_IS_LITERAL_ONLY
Definition search.h:121

Definition at line 397 of file search.h.

◆ snobol_meta_is_single_char_alt

#define snobol_meta_is_single_char_alt ( m)
Value:
(!!((m)->flags & META_IS_SINGLE_CHAR_ALT))
#define META_IS_SINGLE_CHAR_ALT
Definition search.h:112

Definition at line 384 of file search.h.

◆ snobol_meta_is_span_family

#define snobol_meta_is_span_family ( m)
Value:
(!!((m)->flags & META_IS_SPAN_FAMILY))
#define META_IS_SPAN_FAMILY
Definition search.h:114

Definition at line 387 of file search.h.

◆ snobol_meta_may_match_empty

#define snobol_meta_may_match_empty ( m)
Value:
(!!((m)->flags & META_MAY_MATCH_EMPTY))
#define META_MAY_MATCH_EMPTY
Definition search.h:110

Definition at line 382 of file search.h.

◆ snobol_meta_search_vm_eligible

#define snobol_meta_search_vm_eligible ( m)
Value:
(!!((m)->flags & META_SEARCH_VM_ELIGIBLE))
#define META_SEARCH_VM_ELIGIBLE
Definition search.h:122

Definition at line 398 of file search.h.

◆ snobol_meta_simd_eligible

#define snobol_meta_simd_eligible ( m)
Value:
(!!((m)->flags & META_SIMD_ELIGIBLE))
#define META_SIMD_ELIGIBLE
Definition search.h:123

Definition at line 400 of file search.h.

◆ SNOBOL_SEARCH_MAX_PREFIX

#define SNOBOL_SEARCH_MAX_PREFIX   16

Maximum literal prefix bytes retained for candidate skipping.

Definition at line 73 of file search.h.

Typedef Documentation

◆ 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.

Definition at line 164 of file search.h.

◆ snobol_fusion_segment_t

typedef struct snobol_fusion_segment_t snobol_fusion_segment_t

Enumeration Type Documentation

◆ anonymous enum

anonymous enum
Enumerator
FUSION_CHAR 

Definition at line 180 of file search.h.

◆ anonymous enum

anonymous enum
Enumerator
FUSION_LIT 

Definition at line 178 of file search.h.

◆ anonymous enum

anonymous enum
Enumerator
FUSION_ALT 

Definition at line 181 of file search.h.

◆ anonymous enum

anonymous enum
Enumerator
FUSION_RUN 

Definition at line 179 of file search.h.

◆ anonymous enum

anonymous enum
Enumerator
MAX_FUSION_SEGMENTS 

Definition at line 183 of file search.h.

◆ anonymous enum

anonymous enum

Maximum DFA states before we give up and fall back to the search-VM.

Enumerator
SNOBOL_DFA_MAX_STATES 

Definition at line 140 of file search.h.

◆ anonymous enum

anonymous enum

Maximum single-char alternation bytes tracked.

Enumerator
SNOBOL_SEARCH_MAX_ALT 

Definition at line 76 of file search.h.

◆ anonymous enum

anonymous enum
Enumerator
MAX_FUSION_ALT 

Definition at line 184 of file search.h.

◆ snobol_search_skip_reason_t

Enumerator
SNOBOL_SEARCH_SKIP_NONE 

Position not skipped

SNOBOL_SEARCH_SKIP_LITERAL 

Skipped by literal prefix scan (memmem)

SNOBOL_SEARCH_SKIP_FIRST_BYTE 

Skipped by first-byte memchr

SNOBOL_SEARCH_SKIP_BITMAP 

Skipped by candidate bitmap scan

SNOBOL_SEARCH_SKIP_BREAK_SCAN 

Skipped by BREAK/BREAKX bitmap scan

SNOBOL_SEARCH_SKIP_SPAN_SCAN 

Skipped by SPAN bitmap scan

SNOBOL_SEARCH_SKIP_JIT_COLD 

JIT skip: below search-mode hotness threshold

SNOBOL_SEARCH_SKIP_JIT_BUDGET 

JIT skip: compile budget exhausted

SNOBOL_SEARCH_SKIP_JIT_EXIT_RATE 

JIT skip: exit rate exceeded

SNOBOL_SEARCH_BAILOUT_UNSUPPORTED 

JIT bailout: unsupported control flow

SNOBOL_SEARCH_BAILOUT_SAFETY 

JIT bailout: safety fallback triggered

SNOBOL_SEARCH_BAILOUT_CANDIDATE 

JIT bailout: expected candidate rejection

Definition at line 453 of file search.h.

◆ 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)

Definition at line 85 of file search.h.

Function Documentation

◆ build_dfa()

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()).

◆ check_simd_eligible()

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.

Parameters
bcCompiled bytecode buffer
bc_lenBytecode length
Returns
true if the pattern is SIMD-eligible

◆ snobol_auto_trie_free()

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_build_alt_trie()

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().

◆ snobol_dfa_free()

void snobol_dfa_free ( snobol_dfa_t * dfa)

Free a DFA allocated by build_dfa(). Called from snobol_pattern_free() in api.c.

◆ snobol_fusion_free()

void snobol_fusion_free ( snobol_fusion_t * fusion)

Free heap-allocated fusion struct and its ALT sub-lists. Safe on NULL.

◆ snobol_pattern_automaton_available()

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_pattern_get_trie_cache()

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.

◆ snobol_search_derive_meta()

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).

Parameters
bcCompiled bytecode buffer (read-only)
bc_lenBytecode length in bytes
outOutput metadata struct (caller-allocated)

◆ snobol_search_dump_cost_model()

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.

Parameters
outStream to write to (NULL is treated as stdout).

◆ snobol_search_exec()

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.

Parameters
vmPartially-initialised VM (bc/bc_len + callbacks set)
subjectFull subject string pointer
subject_lenSubject length in bytes
start_offsetByte offset to start searching from (0 = beginning)
metaOptional pre-derived metadata for acceleration (NULL = derive inline)
dfaOptional pre-built DFA for the automaton tier (NULL = none)
out_resultOutput: match position (always written; success=false on no match)
diagOptional diagnostics output (may be NULL)
Returns
true if a match was found; false if no match in [start_offset, subject_len]

◆ snobol_search_exec_anchored()

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.

Parameters
vmPartially-initialised VM (bc/bc_len + callbacks set)
subjectFull subject string pointer
subject_lenSubject length in bytes
metaOptional pre-derived metadata (NULL = derive inline)
dfaOptional DFA for automaton acceleration (NULL = none)
out_resultOutput: match position (always written; success=false on no match)
diagOptional diagnostics output (may be NULL)
Returns
true if a match was found starting at offset 0; false otherwise

◆ snobol_search_executed_tier()

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.

Parameters
metaPre-derived search metadata (e.g. from snobol_pattern_get_meta()).
dfa_availableTrue when the caller would supply a DFA (enables the Tier-7 automaton override); false otherwise.
subject_lenSubject length in bytes.
anchoredTrue for anchored (Pattern::match) matching.
Returns
The snobol_search_tier_t that would be dispatched.

◆ snobol_search_meta_free()

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.

Parameters
metaMetadata struct to clean up (NULL is safe).

◆ snobol_search_vm_cleanup()

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).

Parameters
vmVM struct to clean up (NULL is safe).

◆ tier_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 )

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.

◆ tier_simd_nfa()

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.

Parameters
vmVM with bc/bc_len set for the pattern
subjectSubject string
subject_lenSubject length
start_offsetSearch start offset
metaPre-derived metadata (unused, must be non-NULL)
dfaUnused (must be NULL)
out_resultMatch result
diagDiagnostics (may be NULL)
anchoredWhether the match must begin exactly at start_offset
Returns
true when a match is found