|
libsnobol4 1.0.2
High-performance SNOBOL4-style pattern matching library
|
Virtual machine types, opcodes, and execution API for libsnobol4. More...


Go to the source code of this file.
Classes | |
| struct | cp_range |
| Unicode codepoint range [start, end] (both inclusive). More... | |
| struct | snobol_range_meta_t |
| Cached range metadata for a single charclass set. More... | |
| struct | snobol_buf |
| Generic growable byte buffer used for VM output accumulation. More... | |
| struct | WriteLogEntry |
| Write-log entry recording a single capture register modification. More... | |
| struct | UndoRecord |
| A single trail undo record. More... | |
| struct | CompactChoiceHeader |
| Header for a compact choice stack record (trail-based). More... | |
| struct | choice |
| Legacy full-snapshot choice stack entry. More... | |
| struct | ChoiceArenaPage |
| struct | ChoiceArena |
| struct | VM |
| VM state: all mutable state for a single pattern execution. More... | |
| struct | search_vm_t |
| Lightweight VM state for search-mode execution (Tier 1-7). More... | |
Macros | |
| #define | SNOBOL_DYNAMIC_PATTERN 1 |
| Enable dynamic pattern and table support. | |
Typedefs | |
| typedef struct cp_range | CpRange |
| Unicode codepoint range [start, end] (both inclusive). | |
| typedef void(* | emit_cb) (const char *data, size_t len, void *udata) |
Callback invoked by OP_EMIT_* instructions to stream output. | |
| typedef struct ChoiceArenaPage | ChoiceArenaPage |
| typedef struct ChoiceArena | ChoiceArena |
Functions | |
| ChoiceArena * | vm_arena_create (void) |
| void | vm_arena_destroy (ChoiceArena *arena) |
| void | vm_arena_reset (ChoiceArena *arena) |
| uint8_t * | vm_arena_alloc (ChoiceArena *arena, size_t n) |
| void | vm_arena_pop_last (ChoiceArena *arena) |
| const uint8_t * | get_ranges_ptr (const VM *vm, uint16_t set_id, uint16_t *out_count, uint16_t *out_case) |
| Retrieve charclass range data for a set ID. | |
| void | snobol_build_range_meta (const uint8_t *bc, size_t bc_len, snobol_range_meta_t **out_table, size_t *out_count) |
| Build a range metadata table from bytecode for O(1) set_id lookup. | |
| bool | ranges_to_ascii_bitmap (const uint8_t *ranges_ptr, size_t count, uint64_t map[2]) |
| Build a 128-bit ASCII bitmap from range data; returns false if any range exceeds 127. | |
| bool | ranges_to_full_bitmap (const uint8_t *ranges_ptr, size_t count, uint64_t map[4]) |
| Build a 256-bit byte-level bitmap from range data; supports the full 0-255 byte range (UTF-8 safe). | |
| bool | range_contains (const uint8_t *ranges_ptr, size_t count, uint32_t cp) |
| Test whether a codepoint is contained in a packed range array. | |
| bool | vm_exec (VM *vm) |
| Execute a single pass of VM bytecode (used internally by vm_run). | |
| bool | vm_run (VM *vm) |
| Run the VM, re-executing on backtrack until accept or exhausted. | |
| void | vm_init_labels (VM *vm) |
| Allocate label offset table; call before vm_run(). | |
| void | vm_free_labels (VM *vm) |
| Free label offset table. | |
| bool | vm_register_label (VM *vm, uint16_t label_id, uint32_t offset) |
| Register a label at a given bytecode offset. | |
| uint32_t | vm_get_label_offset (VM *vm, uint16_t label_id) |
| Retrieve the bytecode offset for a label; returns UINT32_MAX if not found. | |
| void | vm_init_tables (VM *vm) |
| Initialise the VM's table registry. | |
| void | vm_free_tables (VM *vm) |
| Free the VM's table registry. | |
| bool | vm_register_table (VM *vm, snobol_table_t *table, uint16_t *out_id) |
Register a table and return its runtime ID via out_id. | |
| snobol_table_t * | vm_get_table (VM *vm, uint16_t table_id) |
| Look up a table by runtime ID; returns NULL if not found. | |
| void | vm_init_arrays (VM *vm) |
| Initialise the VM's array registry. | |
| void | vm_free_arrays (VM *vm) |
| Free the VM's array registry. | |
| bool | vm_register_array (VM *vm, snobol_array_t *array, uint16_t *out_id) |
Register an array and return its runtime ID via out_id. | |
| snobol_array_t * | vm_get_array (VM *vm, uint16_t array_id) |
| Look up an array by runtime ID; returns NULL if not found. | |
| void | snobol_buf_init (snobol_buf *b) |
| Initialise a snobol_buf to empty state (no allocation). | |
| void | snobol_buf_append (snobol_buf *b, const char *data, size_t len) |
Append len bytes from data to the buffer, growing as needed. | |
| void | snobol_buf_clear (snobol_buf *b) |
| Reset buffer length to 0 (keeps allocation). | |
| void | snobol_buf_free (snobol_buf *b) |
| Free buffer memory and reset to empty state. | |
| void | vm_push_choice (VM *vm, size_t ip, size_t pos) |
| Push a backtracking choice point onto the VM's choice stack. | |
| bool | vm_pop_choice (VM *vm) |
| Pop the most recent choice point; return false if stack is empty. | |
| void | snobol_vm_reset (VM *vm) |
| Reset VM state between match attempts while keeping choice/allocation. Clears captures, counters, and rewinds the choice stack. The caller is responsible for setting ip/pos to appropriate values. | |
| void | vm_write_log_init (VM *vm) |
| Allocate write-log circular buffer. | |
| void | vm_write_log_free (VM *vm) |
| Free write-log buffer. | |
| void | vm_write_log_clear (VM *vm) |
| Clear all write-log entries without freeing memory. | |
| void | vm_write_log_track_cap_start (VM *vm, uint8_t cap, size_t old_start) |
Track an old cap_start value before overwriting register cap. | |
| void | vm_write_log_track_cap_end (VM *vm, uint8_t cap, size_t old_end) |
Track an old cap_end value before overwriting register cap. | |
| size_t | vm_write_log_count_entries (const VM *vm) |
| Return the current number of valid write-log entries. | |
| void | vm_write_log_copy_entries (const VM *vm, WriteLogEntry *dst, size_t dst_cap) |
| Copy write-log entries into a caller-provided buffer. | |
| size_t | vm_compact_choice_record_size (const CompactChoiceHeader *hdr) |
| Return the total size in bytes of a compact choice record. | |
| void | vm_trail_init (VM *vm) |
| Allocate the undo trail buffer. | |
| void | vm_trail_free (VM *vm) |
| Free the undo trail buffer. | |
| void | vm_trail_clear (VM *vm) |
| Reset trail depth to zero without freeing memory. | |
| void | vm_trail_push (VM *vm, UndoRecord rec) |
| Push a record onto the trail, growing the buffer as needed. | |
| void | vm_trail_counter_inc (VM *vm, uint8_t loop_id, uint32_t prior_count, size_t prior_last_pos) |
| Record a counter increment (OP_REPEAT_STEP) for undo on backtrack. | |
| void | vm_trail_cap_write (VM *vm, uint8_t cap, uint8_t sub, size_t prior_start, size_t prior_end) |
Record a capture-register write (OP_CAP_START/OP_CAP_END) for undo. sub is 0 to restore only prior_start, 1 to restore only prior_end, and 2 to restore both. | |
| void | vm_trail_var_write (VM *vm, uint8_t var, size_t prior_start, size_t prior_end) |
| Record a named-variable write (OP_ASSIGN) for undo on backtrack. | |
| void | vm_trail_replay (VM *vm, size_t base) |
| Replay trail entries [base, top) in reverse, restoring prior state. | |
| size_t | vm_trail_depth (const VM *vm) |
| Return the current number of live trail records. | |
| size_t | vm_choice_stack_memory_usage (VM *vm) |
| Return the current bytes used by the choice stack. | |
| size_t | vm_choice_record_average_size (VM *vm) |
| Return the average choice record size in bytes (computed from accumulated stats). | |
| size_t | vm_choice_stack_depth (VM *vm) |
| Return the current number of live choice points on the stack. | |
Virtual machine types, opcodes, and execution API for libsnobol4.
Defines the bytecode instruction set, VM state structure, and all functions for executing compiled SNOBOL4 patterns. This is an internal API used by the language bindings and the public snobol.h wrapper.
Definition in file vm.h.
| #define SNOBOL_DYNAMIC_PATTERN 1 |
| typedef struct ChoiceArena ChoiceArena |
| typedef struct ChoiceArenaPage ChoiceArenaPage |
Unicode codepoint range [start, end] (both inclusive).
Used to represent character class ranges in the bytecode charclass tables.
| typedef void(* emit_cb) (const char *data, size_t len, void *udata) |
| anonymous enum |
| anonymous enum |
| anonymous enum |
Sentinel table_id written by compile_template_to_bytecode() for any table reference that has not yet been bound to a runtime ID. Call snobol_template_bind_tables() to resolve these to real IDs.
| Enumerator | |
|---|---|
| SNBL_TABLE_ID_UNBOUND | |
| anonymous enum |
| enum OpCode |
Bytecode opcodes for the SNOBOL4 VM.
Each opcode is followed by zero or more operand bytes as documented in the inline comments. Operands are big-endian.
| Enumerator | |
|---|---|
| OP_ACCEPT | Pattern succeeds; no operands |
| OP_FAIL | Pattern fails unconditionally; no operands |
| OP_JMP | Unconditional jump; target: u32 |
| OP_SPLIT | Non-deterministic branch; target_a: u32, target_b: u32 |
| OP_LIT | Match literal bytes; offset: u32, len: u32 |
| OP_ANY | Match char in class; charclass id: u16 |
| OP_NOTANY | Match char NOT in class; charclass id: u16 |
| OP_SPAN | Match 1+ chars in class; charclass id: u16 |
| OP_BREAK | Consume until char in set (0 or more); charclass id: u16 |
| OP_CAP_START | Begin capture region; reg: u8 |
| OP_CAP_END | End capture region; reg: u8 |
| OP_ASSIGN | Assign capture register to variable; var: u16, reg: u8 |
| OP_LEN | Match exactly n codepoints; n: u32 |
| OP_EVAL | Call back to host; fn: u16, reg: u8 |
| OP_ANCHOR | Position anchor; type: u8 (0=start, 1=end) |
| OP_REPEAT_INIT | Begin bounded repetition; loop_id: u8, min: u32, max: u32, skip_target: u32 |
| OP_REPEAT_STEP | Step bounded repetition; loop_id: u8, jmp_target: u32 |
| OP_EMIT_LITERAL | Append literal to output; offset: u32, len: u32 |
| OP_EMIT_CAPTURE | Append capture register to output; reg: u8 |
| OP_EMIT_EXPR | LEGACY: emit with expression; reg: u8, expr_type: u8 — use OP_EMIT_FORMAT in new code |
| OP_EMIT_TABLE | Table-backed lookup emit; see vm.h inline encoding doc |
| OP_EMIT_FORMAT | Formatted capture emit; reg: u8, format_type: u8 (see SNBL_FMT_*) |
| OP_LABEL | Define label target; label_id: u16 |
| OP_GOTO | Unconditional label jump; label_id: u16 |
| OP_GOTO_F | Jump to label if last match failed; label_id: u16 |
| OP_TABLE_GET | Match a bound table value; table_id: u16, key_kind: u8, key payload, flags: u8, name_len: u8, name: bytes[name_len]. key_kind 0 = register (u8), 1 = inline literal (len u16 + bytes); a register key is a capture-derived subject range, a literal key is data. flags bit 0 = case-insensitive value matching. The stored value is matched against the subject and consumed; a missing key fails. Variable-length instruction. |
| OP_TABLE_SET | Update: table[key] = value_reg; table_id: u16, key_kind: u8, key payload (same encoding as OP_TABLE_GET), value_reg: u8, name_len: u8, name: bytes[name_len]. The value register must hold a capture range (an empty range stores an empty value); the key is data and is not consumed. Variable-length. |
| OP_ARRAY_GET | Lookup: dest_reg = array[key_reg]; array_id: u16, key_reg: u8, dest_reg: u8, name_len: u8, name: bytes[name_len] |
| OP_ARRAY_SET | Update: array[key_reg] = value_reg; array_id: u16, key_reg: u8, value_reg: u8, name_len: u8, name: bytes[name_len] |
| OP_DYNAMIC | Evaluate dynamic pattern from pending definition; no operands |
| OP_DYNAMIC_DEF | Define inline dynamic pattern block; len: u32, bytecode... |
| OP_BREAKX | BREAK with retry choice for O(n) tokenization; charclass id: u16 |
| OP_BAL | Match balanced delimiter pair; open_cp: u32, close_cp: u32 |
| OP_FENCE | Cut choice stack (no backtrack past this point); no operands |
| OP_REM | Match remainder of subject to end; no operands |
| OP_RPOS | Succeed when cursor is n codepoints from end; n: u32 |
| OP_RTAB | Advance cursor to n codepoints from end; n: u32 |
| OP_POS | Succeed when cursor is exactly n codepoints from start; n: u32 |
| OP_TAB | Advance cursor to n codepoints from start; n: u32 |
| OP_ABORT | Terminate entire match immediately; no operands |
| OP_SUCCEED | Force immediate match success at current position; no operands |
| OP_NOP | No-op — skip one byte (emitted by fusion pass) |
| enum snobol_builtin_fn_t |
Built-in function dispatch IDs for direct C dispatch via OP_EVAL.
IDs start at 1; ID 0 (SNOBOL_FN_NONE) means "host callback". All IDs < SNOBOL_FN_MAX are recognised built-ins.
| Enumerator | |
|---|---|
| SNOBOL_FN_NONE | Not a built-in: use eval_fn host callback |
| SNOBOL_FN_SIZE |
|
| SNOBOL_FN_TRIM |
|
| SNOBOL_FN_DUPL |
|
| SNOBOL_FN_REVERSE |
|
| SNOBOL_FN_SUBSTR |
|
| SNOBOL_FN_REPLACE |
|
| SNOBOL_FN_REPLACE_CHAR |
|
| SNOBOL_FN_LPAD |
|
| SNOBOL_FN_RPAD |
|
| SNOBOL_FN_CHAR |
|
| SNOBOL_FN_ORD |
|
| SNOBOL_FN_UPPER |
|
| SNOBOL_FN_LOWER |
|
| SNOBOL_FN_IDENT |
|
| SNOBOL_FN_DIFFER |
|
| SNOBOL_FN_LEXEQ |
|
| SNOBOL_FN_LEXLT |
|
| SNOBOL_FN_LEXGT |
|
| SNOBOL_FN_INTEGER |
|
| SNOBOL_FN_REAL |
|
| SNOBOL_FN_NUMERIC |
|
| SNOBOL_FN_EQ |
|
| SNOBOL_FN_NE |
|
| SNOBOL_FN_LT |
|
| SNOBOL_FN_GT |
|
| SNOBOL_FN_LE |
|
| SNOBOL_FN_GE |
|
| SNOBOL_FN_MAX | Sentinel: all IDs < SNOBOL_FN_MAX are known built-ins |
| enum UndoKind |
Undo-record op kinds for the per-thread backtracking trail.
The trail records only the mutations a thread makes to live VM state (counters, captures, named variables) since the last choice point. On a choice pop, the records belonging to the abandoned thread are replayed in reverse to restore pre-choice state — replacing the full memcpy snapshot.
| const uint8_t * get_ranges_ptr | ( | const VM * | vm, |
| uint16_t | set_id, | ||
| uint16_t * | out_count, | ||
| uint16_t * | out_case ) |
Retrieve charclass range data for a set ID.
| [in] | vm | VM instance (for bytecode range table). |
| [in] | set_id | Charclass set ID from the bytecode. |
| [out] | out_count | Number of ranges returned. |
| [out] | out_case | Non-zero if set is case-insensitive. |
| bool range_contains | ( | const uint8_t * | ranges_ptr, |
| size_t | count, | ||
| uint32_t | cp ) |
Test whether a codepoint is contained in a packed range array.
| [in] | ranges_ptr | Range data from get_ranges_ptr(). |
| [in] | count | Number of ranges. |
| [in] | cp | Codepoint to test. |
cp falls within any range. | bool ranges_to_ascii_bitmap | ( | const uint8_t * | ranges_ptr, |
| size_t | count, | ||
| uint64_t | map[2] ) |
Build a 128-bit ASCII bitmap from range data; returns false if any range exceeds 127.
| [in] | ranges_ptr | Range data from get_ranges_ptr(). |
| [in] | count | Number of ranges. |
| [out] | map | Output 2×uint64 bitmap, one bit per ASCII code. |
| bool ranges_to_full_bitmap | ( | const uint8_t * | ranges_ptr, |
| size_t | count, | ||
| uint64_t | map[4] ) |
Build a 256-bit byte-level bitmap from range data; supports the full 0-255 byte range (UTF-8 safe).
Each bit position corresponds to a byte value (bit 0 → byte 0x00, bit 255 → byte 0xFF). Returns false if any range exceeds 255.
| [in] | ranges_ptr | Range data from get_ranges_ptr(). |
| [in] | count | Number of ranges. |
| [out] | map | Output 4×uint64 bitmap (256 bits). |
| void snobol_buf_append | ( | snobol_buf * | b, |
| const char * | data, | ||
| size_t | len ) |
Append len bytes from data to the buffer, growing as needed.
| void snobol_buf_clear | ( | snobol_buf * | b | ) |
Reset buffer length to 0 (keeps allocation).
| void snobol_buf_free | ( | snobol_buf * | b | ) |
Free buffer memory and reset to empty state.
| void snobol_buf_init | ( | snobol_buf * | b | ) |
Initialise a snobol_buf to empty state (no allocation).
| void snobol_build_range_meta | ( | const uint8_t * | bc, |
| size_t | bc_len, | ||
| snobol_range_meta_t ** | out_table, | ||
| size_t * | out_count ) |
Build a range metadata table from bytecode for O(1) set_id lookup.
Scans the bytecode for the charclass trailer, resolves each set_id via get_ranges_ptr() (fallback path), and stores the results in a table indexed by (set_id - 1). The caller owns the returned table and must free it with snobol_free().
| [in] | bc | Bytecode buffer. |
| [in] | bc_len | Bytecode length. |
| [out] | out_table | Receives pointer to allocated table (or NULL). |
| [out] | out_count | Receives number of table entries (0 if none). |
| void snobol_vm_reset | ( | VM * | vm | ) |
Reset VM state between match attempts while keeping choice/allocation. Clears captures, counters, and rewinds the choice stack. The caller is responsible for setting ip/pos to appropriate values.
| uint8_t * vm_arena_alloc | ( | ChoiceArena * | arena, |
| size_t | n ) |
| ChoiceArena * vm_arena_create | ( | void | ) |
| void vm_arena_destroy | ( | ChoiceArena * | arena | ) |
| void vm_arena_pop_last | ( | ChoiceArena * | arena | ) |
| void vm_arena_reset | ( | ChoiceArena * | arena | ) |
| size_t vm_choice_record_average_size | ( | VM * | vm | ) |
Return the average choice record size in bytes (computed from accumulated stats).
| size_t vm_choice_stack_depth | ( | VM * | vm | ) |
Return the current number of live choice points on the stack.
| size_t vm_choice_stack_memory_usage | ( | VM * | vm | ) |
Return the current bytes used by the choice stack.
| size_t vm_compact_choice_record_size | ( | const CompactChoiceHeader * | hdr | ) |
Return the total size in bytes of a compact choice record.
| bool vm_exec | ( | VM * | vm | ) |
| void vm_free_labels | ( | VM * | vm | ) |
Free label offset table.
| snobol_array_t * vm_get_array | ( | VM * | vm, |
| uint16_t | array_id ) |
Look up an array by runtime ID; returns NULL if not found.
| uint32_t vm_get_label_offset | ( | VM * | vm, |
| uint16_t | label_id ) |
Retrieve the bytecode offset for a label; returns UINT32_MAX if not found.
| snobol_table_t * vm_get_table | ( | VM * | vm, |
| uint16_t | table_id ) |
Look up a table by runtime ID; returns NULL if not found.
| bool vm_pop_choice | ( | VM * | vm | ) |
Pop the most recent choice point; return false if stack is empty.
| void vm_push_choice | ( | VM * | vm, |
| size_t | ip, | ||
| size_t | pos ) |
Push a backtracking choice point onto the VM's choice stack.
| bool vm_register_array | ( | VM * | vm, |
| snobol_array_t * | array, | ||
| uint16_t * | out_id ) |
Register an array and return its runtime ID via out_id.
| bool vm_register_label | ( | VM * | vm, |
| uint16_t | label_id, | ||
| uint32_t | offset ) |
Register a label at a given bytecode offset.
| bool vm_register_table | ( | VM * | vm, |
| snobol_table_t * | table, | ||
| uint16_t * | out_id ) |
Register a table and return its runtime ID via out_id.
| bool vm_run | ( | VM * | vm | ) |
| void vm_trail_cap_write | ( | VM * | vm, |
| uint8_t | cap, | ||
| uint8_t | sub, | ||
| size_t | prior_start, | ||
| size_t | prior_end ) |
Record a capture-register write (OP_CAP_START/OP_CAP_END) for undo. sub is 0 to restore only prior_start, 1 to restore only prior_end, and 2 to restore both.
| void vm_trail_clear | ( | VM * | vm | ) |
Reset trail depth to zero without freeing memory.
| void vm_trail_counter_inc | ( | VM * | vm, |
| uint8_t | loop_id, | ||
| uint32_t | prior_count, | ||
| size_t | prior_last_pos ) |
Record a counter increment (OP_REPEAT_STEP) for undo on backtrack.
| size_t vm_trail_depth | ( | const VM * | vm | ) |
Return the current number of live trail records.
| void vm_trail_free | ( | VM * | vm | ) |
Free the undo trail buffer.
| void vm_trail_init | ( | VM * | vm | ) |
Allocate the undo trail buffer.
| void vm_trail_push | ( | VM * | vm, |
| UndoRecord | rec ) |
Push a record onto the trail, growing the buffer as needed.
| void vm_trail_replay | ( | VM * | vm, |
| size_t | base ) |
Replay trail entries [base, top) in reverse, restoring prior state.
| void vm_trail_var_write | ( | VM * | vm, |
| uint8_t | var, | ||
| size_t | prior_start, | ||
| size_t | prior_end ) |
Record a named-variable write (OP_ASSIGN) for undo on backtrack.
| void vm_write_log_clear | ( | VM * | vm | ) |
Clear all write-log entries without freeing memory.
| void vm_write_log_copy_entries | ( | const VM * | vm, |
| WriteLogEntry * | dst, | ||
| size_t | dst_cap ) |
Copy write-log entries into a caller-provided buffer.
| size_t vm_write_log_count_entries | ( | const VM * | vm | ) |
Return the current number of valid write-log entries.
| void vm_write_log_free | ( | VM * | vm | ) |
Free write-log buffer.
| void vm_write_log_init | ( | VM * | vm | ) |
Allocate write-log circular buffer.
| void vm_write_log_track_cap_end | ( | VM * | vm, |
| uint8_t | cap, | ||
| size_t | old_end ) |
Track an old cap_end value before overwriting register cap.
| void vm_write_log_track_cap_start | ( | VM * | vm, |
| uint8_t | cap, | ||
| size_t | old_start ) |
Track an old cap_start value before overwriting register cap.