/*
regex2 0.9.6 beta (VM Edition) - Performance Optimized

Copyright (c) 2026 Dario Deledda. All rights reserved.
Use of this source code is governed by an MIT license
that can be found in the LICENSE file.

This file contains a regex module based on a Virtual Machine approach.

Features:
 - **Non-recursive VM**: Safe execution without stack overflow on complex patterns.
 - UTF8 support with Fast ASCII path.
 - Literal characters, '.', '*', '{m,n}'.
 - Short quantifiers: '?', '+'.
 - Non-greedy quantifiers: '*?', '+?', '??'.
 - Nested groups: '()'.
 - Named groups: '(?P<name>...)'.
 - Non-capturing groups: '(?:...)'.
 - Character classes: \w, \W, \d, \D, \s, \S, \a, \A.
 - Hex escapes: \xHH, \XHHHH.
 - Alternation: '|'.
 - Character classes: [abc], [^abc], [a-z].
 - Anchors: '^' (start of string), '$' (end of string).
 - Word boundaries: '\b' (word boundary), '\B' (non-word boundary).
 - Inline Flags:
   - '(?i)' Case insensitive.
   - '(?m)' Multiline (anchors match newlines).
   - '(?s)' Dot-all (dot matches newline).

Configuration:
 - `max_stack_depth`: Controls the dynamic growth limit of the backtracking stack.
    Default is 2048. Increase this value if you encounter complex patterns failing
    on deep recursions/backtracking, or decrease it to limit memory usage.

Functions:
 - `compile(pattern) !Regex` -> Compiles a pattern into a Regex object.
 - `(r Regex) find(text) ?Match` -> Finds the first match in a string.
 - `(r Regex) find_all(text) []Match` -> Finds all non-overlapping matches.
 - `(r Regex) find_from(text, start_index) ?Match` -> Finds the first match starting from a specific index.
 - `(r Regex) replace(text, repl) string` -> Finds and replaces the first match.
 - `(r Regex) fullmatch(text string) ?Match` -> Match exact strings.
 - `(r Regex) group_by_name(m Match, name string) string` -> Get text of a named group.

Key Architectural Features and Optimizations:
 - **Pre-allocated Machine workspace**: All search operations are zero-allocation.
 - **Raw pointer access**: Bypasses bounds checking for string and instruction access.
 - **Fast ASCII Path**: Characters < 128 bypass heavy UTF-8 decoding.
 - **Instruction merging**: Consecutive character matches are merged into string blocks.
 - **Bitmap lookups**: ASCII character classes use a 128-bit bitset for O(1) matching.
 - **NFA Virtual Machine**: Executes bytecode instructions to simulate pattern matching.
 - **Dynamic Stack Growth**: Automatically expands the backtracking stack to prevent false negatives.
 - **Zero-Allocation Search**: Reuses a pre-allocated Machine workspace for search operations.
 - **Anchored Optimization**: Patterns starting with '^' skip the scanning loop.
 - **Prefix Skipping**: Uses Boyer-Moore-like skipping for literal prefixes.

*/

module pcre

import strconv
import strings

/******************************************************************************
*
* VM Instruction Definition
*
******************************************************************************/

// InstType defines the operation codes for the Virtual Machine.
enum InstType as u8 {
    match             // Halt and signal a successful match.
    char              // Match a single UTF-8 rune.
    string            // Match a sequence of ASCII characters (merged optimization).
    any               // Match any character (dot).
    class             // Match a character class (e.g., [a-z] or \d).
    split             // Branch execution: target_x (primary), target_y (backtrack).
    jmp               // Unconditional jump to target_x.
    save              // Save current string position into a capture group index.
    assert_start      // Assert current position is start of string.
    assert_end        // Assert current position is end of string.
    assert_line_start // Assert current position is start of a line (multiline mode).
    assert_line_end   // Assert current position is end of a line (multiline mode).
    assert_bound      // Assert word boundary (\b).
    assert_nbound     // Assert non-word boundary (\B).
}

// Inst represents a single bytecode instruction.
// Packed for memory locality.
struct Inst {
mut:
    typ         InstType
    val         rune   // Used by .char
    val_str     string // Used by .string
    val_len     int    // Byte length of val_str
    target_x    int    // Primary jump/split target
    target_y    int    // Backtrack target for .split
    group_idx   int    // Capture group index for .save
    char_class  []rune // Literal runes for character classes
    bitmap      [4]u32 // 128-bit bitset for ASCII character classes
    inverted    bool   // Negation flag for classes
    ignore_case bool   // Case-insensitive flag
    dot_all     bool   // Whether '.' matches '\n'
}

// Machine provides a workspace for VM execution.
// To ensure thread safety, this is created per top-level API call.
pub struct Machine {
mut:
    stack    []int // Backtracking stack stores: [capture_states..., string_ptr, next_pc]
    captures []int // Flat array of [start, end] byte indices for groups
}

// Regex is the compiled regular expression object.
pub struct Regex {
pub:
    pattern      string         // The original regex string
    prog         []Inst         // Compiled bytecode
    total_groups int            // Number of capture groups defined in pattern
    group_map    map[string]int // Mapping of names to indices for (?P<name>...)
    prefix_lit   string         // Pre-calculated literal prefix for fast-skip optimization
    has_prefix   bool           // Whether a literal prefix exists
    anchored     bool           // True if pattern starts with '^' (optimization hint)
pub mut:
    max_stack_depth int // User-defined stack limit hint
}

// Match contains the results of a successful regex match.
pub struct Match {
pub:
    text   string   // The full text of the match
    start  int      // Starting byte index in the source string
    end    int      // Ending byte index in the source string
    groups []string // Sub-strings captured by groups
}

// Internal structures for Compilation
struct Quantifier {
mut:
    min    int
    max    int // -1 for infinity
    greedy bool
}

struct Flags {
mut:
    ignore_case bool
    multiline   bool
    dot_all     bool
}

enum NodeType {
    chr
    any_char
    group
    alternation
    char_class
    start_of_string
    end_of_string
    word_boundary
    non_word_boundary
    word_char
    non_word_char
    digit
    non_digit
    whitespace
    non_whitespace
    lowercase_char
    uppercase_char
}

struct Node {
mut:
    typ                 NodeType
    chr                 rune
    quant               Quantifier
    nodes               []Node
    alternatives        [][]Node
    group_capture_index int = -1
    char_set            []rune
    inverted            bool
    ignore_case         bool
    multiline           bool
    dot_all             bool
}

/******************************************************************************
*
* Internal Utilities (Inlined for Speed)
*
******************************************************************************/

// read_rune_at decodes a UTF-8 rune from a byte pointer safely.
// Marked inline to be embedded directly into the VM loop.
@[inline]
fn read_rune_at(str &u8, len int, index int) (rune, int) {
    unsafe {
        if index >= len {
            return 0, 0
        }
        b0 := u32(str[index])
        if b0 < 0x80 {
            return rune(b0), 1
        }
        if (b0 & 0xE0) == 0xC0 && index + 1 < len {
            return rune(((b0 & 0x1F) << 6) | (u32(str[index + 1]) & 0x3F)), 2
        }
        if (b0 & 0xF0) == 0xE0 && index + 2 < len {
            return rune(((b0 & 0x0F) << 12) | ((u32(str[index + 1]) & 0x3F) << 6) | (u32(str[
                index + 2]) & 0x3F)), 3
        }
        if (b0 & 0xF8) == 0xF0 && index + 3 < len {
            return rune(((b0 & 0x07) << 18) | ((u32(str[index + 1]) & 0x3F) << 12) | ((u32(str[
                index + 2]) & 0x3F) << 6) | (u32(str[index + 3]) & 0x3F)), 4
        }
    }
    return 0, 0
}

// is_word_char returns true for alphanumeric ASCII characters and underscore.
@[inline]
fn is_word_char(r u8) bool {
    return (r >= `a` && r <= `z`) || (r >= `A` && r <= `Z`) || (r >= `0` && r <= `9`) || r == `_`
}

// set_bitmap sets a specific bit in a 128-bit bitset for ASCII matching.
@[inline]
fn set_bitmap(mut bitmap [4]u32, r rune) {
    if r >= 0 && r < 128 {
        idx := u32(r) >> 5
        bit := u32(r) & 31
        bitmap[idx] |= (u32(1) << bit)
    }
}

/******************************************************************************
*
* Compiler Logic
*
******************************************************************************/

// compile transforms a regex pattern string into a Regex object.
pub fn compile(pattern string) !Regex {
    mut group_map := map[string]int{}
    initial_flags := Flags{false, false, false}

    // Phase 1: AST Parsing
    nodes, _, final_group_count := parse_nodes(pattern, 0, `\0`, 0, initial_flags, mut group_map)!

    root := Node{
        typ:   .group
        nodes: nodes
        quant: Quantifier{1, 1, true}
    }

    // Phase 2: Bytecode Emission
    mut compiler := Compiler{
        prog: []Inst{cap: 128}
    }
    compiler.emit_node(root)
    compiler.emit(Inst{ typ: .match })

    // Phase 3: Optimization
    optimized_prog := compiler.optimize()

    // Detect Prefix and Anchor optimizations
    mut prefix := ''
    mut has_prefix := false
    mut anchored := false

    if optimized_prog.len > 0 {
        first := optimized_prog[0]
        if first.typ == .string {
            prefix = first.val_str
            has_prefix = true
        } else if first.typ == .char && !first.ignore_case && first.val < 128 {
            prefix = unsafe { u8(first.val).ascii_str() }
            has_prefix = true
        } else if first.typ == .assert_start {
            anchored = true
        }
    }

    return Regex{
        max_stack_depth: 2048
        pattern:         pattern
        prog:            optimized_prog
        total_groups:    final_group_count
        group_map:       group_map
        prefix_lit:      prefix
        has_prefix:      has_prefix
        anchored:        anchored
    }
}

// new_machine allocates a new VM state machine.
// This isolates the runtime memory (stack/captures) from the compiled regex, allowing thread-safe usage.
pub fn (r &Regex) new_machine() Machine {
    // Pre-allocate enough space for stack and captures to avoid re-allocation in hot path
    return Machine{
        stack:    []int{len: r.max_stack_depth}
        captures: []int{len: r.total_groups * 2}
    }
}

// Compiler holds the state for generating the bytecode instructions.
struct Compiler {
mut:
    prog []Inst
}

// emit appends an instruction to the program and returns its index.
fn (mut c Compiler) emit(i Inst) int {
    c.prog << i
    return c.prog.len - 1
}

// optimize merges consecutive literal characters into single string instructions
// and resolves jump targets to absolute indices.
fn (mut c Compiler) optimize() []Inst {
    mut targets := map[int]bool{}
    for inst in c.prog {
        if inst.typ == .split || inst.typ == .jmp {
            targets[inst.target_x] = true
            targets[inst.target_y] = true
        }
    }

    mut new_prog := []Inst{cap: c.prog.len}
    mut idx_map := map[int]int{}

    mut i := 0
    for i < c.prog.len {
        inst := c.prog[i]
        idx_map[i] = new_prog.len

        // Optimization: Merge consecutive chars
        if inst.typ == .char && !inst.ignore_case && inst.val < 128 {
            mut s_val := unsafe { u8(inst.val).ascii_str() }
            mut j := i + 1
            for j < c.prog.len && !targets[j] {
                next := c.prog[j]
                if next.typ == .char && !next.ignore_case && next.val < 128 {
                    s_val += unsafe { u8(next.val).ascii_str() }
                    j++
                } else {
                    break
                }
            }
            if j > i + 1 {
                new_prog << Inst{
                    typ:     .string
                    val_str: s_val
                    val_len: s_val.len
                }
                for k := i + 1; k < j; k++ {
                    idx_map[k] = new_prog.len
                }
                i = j
                continue
            }
        }
        new_prog << inst
        i++
    }
    idx_map[c.prog.len] = new_prog.len

    // Fix jump offsets
    for mut inst in new_prog {
        if inst.typ == .split || inst.typ == .jmp {
            inst.target_x = idx_map[inst.target_x] or { inst.target_x }
            inst.target_y = idx_map[inst.target_y] or { inst.target_y }
        }
    }
    return new_prog
}

// emit_class generates the instructions for a character class node.
// It populates the bitmap for O(1) ASCII matching and the slice for Unicode.
fn (mut c Compiler) emit_class(node Node) {
    mut bitmap := [4]u32{}
    mut char_class := node.char_set.clone()
    mut inverted := node.inverted

    // Pre-compile common classes into the bitmap for O(1) lookups
    match node.typ {
        .word_char {
            for r := `0`; r <= `9`; r++ {
                set_bitmap(mut bitmap, r)
            }
            for r := `a`; r <= `z`; r++ {
                set_bitmap(mut bitmap, r)
            }
            for r := `A`; r <= `Z`; r++ {
                set_bitmap(mut bitmap, r)
            }
            set_bitmap(mut bitmap, `_`)
        }
        .non_word_char {
            inverted = true
            for r := `0`; r <= `9`; r++ {
                set_bitmap(mut bitmap, r)
            }
            for r := `a`; r <= `z`; r++ {
                set_bitmap(mut bitmap, r)
            }
            for r := `A`; r <= `Z`; r++ {
                set_bitmap(mut bitmap, r)
            }
            set_bitmap(mut bitmap, `_`)
        }
        .digit {
            for r := `0`; r <= `9`; r++ {
                set_bitmap(mut bitmap, r)
            }
        }
        .non_digit {
            inverted = true
            for r := `0`; r <= `9`; r++ {
                set_bitmap(mut bitmap, r)
            }
        }
        .whitespace {
            for r in [` `, `\t`, `\n`, `\r`, `\v`, `\f`] {
                set_bitmap(mut bitmap, r)
            }
        }
        .non_whitespace {
            inverted = true
            for r in [` `, `\t`, `\n`, `\r`, `\v`, `\f`] {
                set_bitmap(mut bitmap, r)
            }
        }
        .lowercase_char {
            for r := `a`; r <= `z`; r++ {
                set_bitmap(mut bitmap, r)
            }
        }
        .uppercase_char {
            for r := `A`; r <= `Z`; r++ {
                set_bitmap(mut bitmap, r)
            }
        }
        .char_class {
            for r in node.char_set {
                set_bitmap(mut bitmap, r)
                if node.ignore_case {
                    if r >= `a` && r <= `z` {
                        set_bitmap(mut bitmap, r - 32)
                    } else if r >= `A` && r <= `Z` {
                        set_bitmap(mut bitmap, r + 32)
                    }
                }
            }
        }
        else {}
    }

    c.emit(Inst{
        typ:         .class
        char_class:  char_class
        bitmap:      bitmap
        inverted:    inverted
        ignore_case: node.ignore_case
    })
}

// emit_node handles quantifiers and loops, delegating the actual logic to emit_logic.
fn (mut c Compiler) emit_node(node Node) {
    for _ in 0 .. node.quant.min {
        c.emit_logic(node)
    }

    if node.quant.max == -1 {
        split_idx := c.emit(Inst{ typ: .split })
        start_pc := c.prog.len
        c.emit_logic(node)
        c.emit(Inst{ typ: .jmp, target_x: split_idx })
        if node.quant.greedy {
            c.prog[split_idx].target_x = start_pc
            c.prog[split_idx].target_y = c.prog.len
        } else {
            c.prog[split_idx].target_x = c.prog.len
            c.prog[split_idx].target_y = start_pc
        }
    } else if node.quant.max > node.quant.min {
        rem := node.quant.max - node.quant.min
        mut splits := []int{}
        for _ in 0 .. rem {
            idx := c.emit(Inst{ typ: .split })
            match_pc := c.prog.len
            if node.quant.greedy {
                c.prog[idx].target_x = match_pc
            } else {
                c.prog[idx].target_y = match_pc
            }
            c.emit_logic(node)
            splits << idx
        }
        end_pc := c.prog.len
        for idx in splits {
            if node.quant.greedy {
                c.prog[idx].target_y = end_pc
            } else {
                c.prog[idx].target_x = end_pc
            }
        }
    }
}

// emit_logic generates instructions for specific node types (char, group, alternation).
fn (mut c Compiler) emit_logic(node Node) {
    match node.typ {
        .chr {
            c.emit(Inst{ typ: .char, val: node.chr, ignore_case: node.ignore_case })
        }
        .any_char {
            c.emit(Inst{ typ: .any, dot_all: node.dot_all })
        }
        .group {
            if node.group_capture_index != -1 {
                c.emit(Inst{ typ: .save, group_idx: node.group_capture_index * 2 })
            }
            for child in node.nodes {
                c.emit_node(child)
            }
            if node.group_capture_index != -1 {
                c.emit(Inst{ typ: .save, group_idx: node.group_capture_index * 2 + 1 })
            }
        }
        .alternation {
            if node.alternatives.len == 0 {
                return
            }
            mut end_jumps := []int{}
            for i := 0; i < node.alternatives.len - 1; i++ {
                split_idx := c.emit(Inst{ typ: .split })
                c.prog[split_idx].target_x = c.prog.len
                for child in node.alternatives[i] {
                    c.emit_node(child)
                }
                end_jumps << c.emit(Inst{ typ: .jmp })
                c.prog[split_idx].target_y = c.prog.len
            }
            for child in node.alternatives.last() {
                c.emit_node(child)
            }
            for idx in end_jumps {
                c.prog[idx].target_x = c.prog.len
            }
        }
        .start_of_string {
            c.emit(Inst{
                typ: if node.multiline { InstType.assert_line_start } else { InstType.assert_start }
            })
        }
        .end_of_string {
            c.emit(Inst{
                typ: if node.multiline { InstType.assert_line_end } else { InstType.assert_end }
            })
        }
        .word_boundary {
            c.emit(Inst{ typ: .assert_bound })
        }
        .non_word_boundary {
            c.emit(Inst{ typ: .assert_nbound })
        }
        else {
            c.emit_class(node)
        }
    }
}

// parse_nodes implements a recursive descent parser to construct the AST from the pattern string.
fn parse_nodes(pattern string, pos_start int, terminator rune, group_counter_start int, passed_flags Flags, mut group_map map[string]int) !([]Node, int, int) {
    mut pos := pos_start
    mut group_counter := group_counter_start
    mut current_flags := passed_flags
    mut alternatives := [][]Node{}
    mut current_sequence := []Node{}

    for pos < pattern.len {
        chr, char_len := read_rune_at(pattern.str, pattern.len, pos)
        if chr == terminator {
            pos += char_len
            if alternatives.len > 0 {
                alternatives << current_sequence
                return [
                    Node{
                        typ:          .alternation
                        alternatives: alternatives
                        quant:        Quantifier{1, 1, true}
                    },
                ], pos, group_counter
            }
            return current_sequence, pos, group_counter
        }
        if chr == `|` {
            pos += char_len
            if current_sequence.len == 0 {
                return error('Empty alternative')
            }
            alternatives << current_sequence
            current_sequence = []Node{}
            continue
        }

        mut parsed_nodes := []Node{}
        match chr {
            `^` {
                pos += char_len
                parsed_nodes << Node{
                    typ:       .start_of_string
                    multiline: current_flags.multiline
                }
            }
            `$` {
                pos += char_len
                parsed_nodes << Node{
                    typ:       .end_of_string
                    multiline: current_flags.multiline
                }
            }
            `.` {
                pos += char_len
                parsed_nodes << Node{
                    typ:     .any_char
                    dot_all: current_flags.dot_all
                }
            }
            `*`, `+`, `?`, `{` {
                return error('Quantifier must follow a token')
            }
            `(` {
                pos += char_len
                mut idx := -1
                mut cap := true
                if pos < pattern.len && pattern[pos] == `?` {
                    pos++
                    if pos < pattern.len && pattern[pos] in [`i`, `m`, `s`] {
                        for pos < pattern.len && pattern[pos] != `)` {
                            match pattern[pos] {
                                `i` { current_flags.ignore_case = true }
                                `m` { current_flags.multiline = true }
                                `s` { current_flags.dot_all = true }
                                else {}
                            }

                            pos++
                        }
                        if pos < pattern.len {
                            pos++
                        }
                        continue
                    } else if pos < pattern.len && pattern[pos] == `:` {
                        cap = false
                        pos++
                    } else if pos < pattern.len && pattern[pos] == `P` {
                        pos++
                        if pos >= pattern.len || pattern[pos] != `<` {
                            return error('Invalid named group syntax')
                        }
                        pos++
                        end := pattern.index_after('>', pos) or { -1 }
                        if end == -1 {
                            return error('Unclosed named group')
                        }
                        name := pattern[pos..end]
                        if name in group_map {
                            return error('Duplicate named group: ${name}')
                        }
                        idx = group_counter
                        group_map[name] = idx
                        pos = end + 1
                    }
                }
                if cap {
                    if idx == -1 {
                        idx = group_counter
                    }
                    group_counter++
                }
                sub, new_p, new_c := parse_nodes(pattern, pos, `)`, group_counter, current_flags, mut
                    group_map)!
                pos = new_p
                group_counter = new_c
                parsed_nodes << Node{
                    typ:                 .group
                    nodes:               sub
                    group_capture_index: idx
                }
            }
            `[` {
                pos += char_len
                end := pattern.index_after(']', pos) or { -1 }
                if end == -1 {
                    return error('Unclosed character class')
                }
                content := pattern[pos..end]
                pos = end + 1
                inv := content.len > 0 && content[0] == `^`
                mut set := []rune{}
                mut i := if inv { 1 } else { 0 }
                for i < content.len {
                    c, l := read_rune_at(content.str, content.len, i)
                    if i + l + 1 < content.len && content[i + l] == `-` {
                        ec, el := read_rune_at(content.str, content.len, i + l + 1)
                        for r := c; r <= ec; r++ {
                            set << r
                        }
                        i += l + 1 + el
                    } else {
                        set << c
                        i += l
                    }
                }
                parsed_nodes << Node{
                    typ:         .char_class
                    char_set:    set
                    inverted:    inv
                    ignore_case: current_flags.ignore_case
                }
            }
            `\\` {
                pos += char_len
                if pos >= pattern.len {
                    return error('Trailing backslash')
                }
                esc, el := read_rune_at(pattern.str, pattern.len, pos)
                pos += el
                match esc {
                    `w` {
                        parsed_nodes << Node{
                            typ: .word_char
                        }
                    }
                    `W` {
                        parsed_nodes << Node{
                            typ: .non_word_char
                        }
                    }
                    `d` {
                        parsed_nodes << Node{
                            typ: .digit
                        }
                    }
                    `D` {
                        parsed_nodes << Node{
                            typ: .non_digit
                        }
                    }
                    `s` {
                        parsed_nodes << Node{
                            typ: .whitespace
                        }
                    }
                    `S` {
                        parsed_nodes << Node{
                            typ: .non_whitespace
                        }
                    }
                    `b` {
                        parsed_nodes << Node{
                            typ: .word_boundary
                        }
                    }
                    `B` {
                        parsed_nodes << Node{
                            typ: .non_word_boundary
                        }
                    }
                    `a` {
                        parsed_nodes << Node{
                            typ: .lowercase_char
                        }
                    }
                    `A` {
                        parsed_nodes << Node{
                            typ: .uppercase_char
                        }
                    }
                    `x` {
                        // \xHH - two hex digits decode to a character
                        if pos + 2 > pattern.len {
                            return error('\\x requires exactly 2 hex digits')
                        }
                        hex_str := pattern[pos..pos + 2]
                        val := strconv.parse_uint(hex_str, 16, 32) or {
                            return error('Invalid hex escape \\x${hex_str}')
                        }
                        pos += 2
                        parsed_nodes << Node{
                            typ:         .chr
                            chr:         rune(val)
                            ignore_case: current_flags.ignore_case
                        }
                    }
                    `X` {
                        // \XHHHH - four hex digits decode to a Unicode codepoint
                        if pos + 4 > pattern.len {
                            return error('\\X requires exactly 4 hex digits')
                        }
                        hex_str := pattern[pos..pos + 4]
                        val := strconv.parse_uint(hex_str, 16, 32) or {
                            return error('Invalid hex escape \\X${hex_str}')
                        }
                        pos += 4
                        parsed_nodes << Node{
                            typ:         .chr
                            chr:         rune(val)
                            ignore_case: current_flags.ignore_case
                        }
                    }
                    else {
                        parsed_nodes << Node{
                            typ:         .chr
                            chr:         esc
                            ignore_case: current_flags.ignore_case
                        }
                    }
                }
            }
            else {
                pos += char_len
                parsed_nodes << Node{
                    typ:         .chr
                    chr:         chr
                    ignore_case: current_flags.ignore_case
                }
            }
        }

        if parsed_nodes.len > 0 {
            mut q := Quantifier{1, 1, true}
            if pos < pattern.len {
                peek := pattern[pos]
                match peek {
                    `*` {
                        q = Quantifier{0, -1, true}
                        pos++
                    }
                    `+` {
                        q = Quantifier{1, -1, true}
                        pos++
                    }
                    `?` {
                        q = Quantifier{0, 1, true}
                        pos++
                    }
                    `{` {
                        end := pattern.index_after('}', pos) or { -1 }
                        if end == -1 {
                            return error('Unclosed quantifier')
                        }
                        parts := pattern[pos + 1..end].split(',')
                        min := parts[0].int()
                        max := if parts.len > 1 {
                            if parts[1] == '' { -1 } else { parts[1].int() }
                        } else {
                            min
                        }
                        if min < 0 || (max != -1 && max < min) {
                            return error('Invalid quantifier range {${min},${max}}')
                        }
                        q = Quantifier{min, max, true}
                        pos = end + 1
                    }
                    else {}
                }

                if pos < pattern.len && pattern[pos] == `?` {
                    q.greedy = false
                    pos++
                }
            }
            parsed_nodes.last().quant = q
        }
        current_sequence << parsed_nodes
    }

    if alternatives.len > 0 {
        if current_sequence.len == 0 {
            return error('Empty alternative at end of pattern')
        }
        alternatives << current_sequence
        return [
            Node{
                typ:          .alternation
                alternatives: alternatives
                quant:        Quantifier{1, 1, true}
            },
        ], pos, group_counter
    }
    return current_sequence, pos, group_counter
}

/******************************************************************************
*
* Virtual Machine Execution Engine (Highly Optimized)
*
******************************************************************************/

// vm_match executes the bytecode against the input string using the provided Machine state.
// OPTIMIZATION: Uses raw pointers for instruction and stack access to bypass bounds checking.
@[direct_array_access]
fn (r &Regex) vm_match(text string, start_pos int, mut m Machine) ?Match {
    unsafe {
        // Optimization: Cast voidptr to typed pointer for direct indexing
        mut cap_ptr := &int(m.captures.data)
        cap_len := m.captures.len

        // Fast clear of captures using pointer arithmetic (memset-like)
        for i := 0; i < cap_len; i++ {
            cap_ptr[i] = -1
        }

        mut sp := start_pos // String Pointer Index
        mut stack_ptr := 0 // Stack Pointer Offset

        cap_size := r.total_groups * 2
        frame_size := cap_size + 2 // [captures..., saved_sp, saved_pc]

        // Raw pointers for hot path access
        prog_start := &Inst(r.prog.data)
        mut inst_ptr := prog_start // PC as a pointer

        str_ptr := text.str
        str_len := text.len

        // Cache stack data pointer (cast to typed pointer)
        mut stack_data := &int(m.stack.data)
        mut stack_max := m.stack.len

        for {
            // Check if we walked off the program (should be caught by match inst)
            // Using pointer arithmetic: offset = (inst_ptr - prog_start)

            match inst_ptr.typ {
                .match {
                    // Only allocate result strings on successful match
                    mut s_groups := []string{cap: r.total_groups}
                    for i := 0; i < r.total_groups; i++ {
                        s, e := cap_ptr[i * 2], cap_ptr[i * 2 + 1]
                        s_groups << if s != -1 && e >= s { text[s..e] } else { '' }
                    }
                    return Match{
                        text:   text[start_pos..sp]
                        start:  start_pos
                        end:    sp
                        groups: s_groups
                    }
                }
                .char {
                    if sp >= str_len {
                        goto backtrack
                    }
                    curr_byte := str_ptr[sp]

                    // Fast ASCII path
                    if curr_byte < 128 && inst_ptr.val < 128 {
                        mut c1, mut c2 := curr_byte, u8(inst_ptr.val)
                        if inst_ptr.ignore_case {
                            if c1 >= `a` && c1 <= `z` {
                                c1 -= 32
                            }
                            if c2 >= `a` && c2 <= `z` {
                                c2 -= 32
                            }
                        }
                        if c1 == c2 {
                            sp++
                            inst_ptr++
                            continue
                        }
                        goto backtrack
                    }

                    // UTF-8 Path
                    rn, l := read_rune_at(str_ptr, str_len, sp)
                    if l == 0 {
                        goto backtrack
                    }

                    mut match_ok := false
                    if inst_ptr.ignore_case {
                        r1 := if rn >= `a` && rn <= `z` { rn - 32 } else { rn }
                        r2 := if inst_ptr.val >= `a` && inst_ptr.val <= `z` {
                            inst_ptr.val - 32
                        } else {
                            inst_ptr.val
                        }
                        if r1 == r2 {
                            match_ok = true
                        }
                    } else if rn == inst_ptr.val {
                        match_ok = true
                    }

                    if match_ok {
                        sp += l
                        inst_ptr++
                    } else {
                        goto backtrack
                    }
                }
                .string {
                    if sp + inst_ptr.val_len > str_len {
                        goto backtrack
                    }
                    // Inline memcmp
                    v_str := inst_ptr.val_str.str
                    for i in 0 .. inst_ptr.val_len {
                        if str_ptr[sp + i] != v_str[i] {
                            goto backtrack
                        }
                    }
                    sp += inst_ptr.val_len
                    inst_ptr++
                }
                .class {
                    if sp >= str_len {
                        goto backtrack
                    }
                    c_byte := str_ptr[sp]
                    mut matched := false
                    mut cl := 1

                    // Optimization: Bitmap lookup for ASCII
                    if c_byte < 128 {
                        if (inst_ptr.bitmap[c_byte >> 5] & (u32(1) << (c_byte & 31))) != 0 {
                            matched = true
                        }
                    } else {
                        rn, l := read_rune_at(str_ptr, str_len, sp)
                        cl = l
                        for cr in inst_ptr.char_class {
                            if cr == rn {
                                matched = true
                                break
                            }
                        }
                    }

                    if matched != inst_ptr.inverted {
                        sp += cl
                        inst_ptr++
                    } else {
                        goto backtrack
                    }
                }
                .any {
                    if sp >= str_len {
                        goto backtrack
                    }
                    if inst_ptr.dot_all || str_ptr[sp] != `\n` {
                        _, cl := read_rune_at(str_ptr, str_len, sp)
                        sp += cl
                        inst_ptr++
                    } else {
                        goto backtrack
                    }
                }
                .save {
                    cap_ptr[inst_ptr.group_idx] = sp
                    inst_ptr++
                }
                .split {
                    if stack_ptr + frame_size >= stack_max {
                        new_size := stack_max * 2
                        if new_size > r.max_stack_depth {
                            goto backtrack
                        }
                        m.stack.grow_len(new_size)
                        stack_data = &int(m.stack.data) // Pointer might change on realloc
                        stack_max = new_size
                    }

                    // Optimization: Unrolled stack push
                    stack_offset := stack_ptr
                    for i in 0 .. cap_size {
                        stack_data[stack_offset + i] = cap_ptr[i]
                    }
                    stack_data[stack_offset + cap_size] = sp
                    // Save backtrack target PC index
                    stack_data[stack_offset + cap_size + 1] = inst_ptr.target_y

                    stack_ptr += frame_size
                    // Jump to primary target (convert index to pointer)
                    // FIX: Use pointer indexing instead of addition to avoid type mismatch
                    inst_ptr = &prog_start[inst_ptr.target_x]
                }
                .jmp {
                    inst_ptr = &prog_start[inst_ptr.target_x]
                }
                .assert_start {
                    if sp == 0 {
                        inst_ptr++
                    } else {
                        goto backtrack
                    }
                }
                .assert_end {
                    if sp == str_len {
                        inst_ptr++
                    } else {
                        goto backtrack
                    }
                }
                .assert_line_start {
                    if sp == 0 || (sp > 0 && str_ptr[sp - 1] == `\n`) {
                        inst_ptr++
                    } else {
                        goto backtrack
                    }
                }
                .assert_line_end {
                    if sp == str_len || str_ptr[sp] == `\n` {
                        inst_ptr++
                    } else {
                        goto backtrack
                    }
                }
                .assert_bound, .assert_nbound {
                    l := if sp > 0 { is_word_char(str_ptr[sp - 1]) } else { false }
                    r_ := if sp < str_len { is_word_char(str_ptr[sp]) } else { false }
                    if (inst_ptr.typ == .assert_bound && l != r_)
                        || (inst_ptr.typ == .assert_nbound && l == r_) {
                        inst_ptr++
                    } else {
                        goto backtrack
                    }
                }
            }

            continue

            backtrack:
            if stack_ptr <= 0 {
                return none
            }

            stack_ptr -= frame_size
            stack_offset := stack_ptr

            // Restore captures
            for i in 0 .. cap_size {
                cap_ptr[i] = stack_data[stack_offset + i]
            }
            sp = stack_data[stack_offset + cap_size]
            // Restore PC from index (explicit cast for pointer arithmetic)
            // FIX: Use pointer indexing instead of addition
            inst_ptr = &prog_start[stack_data[stack_offset + cap_size + 1]]
        }
    }
    return none
}

/******************************************************************************
*
* Public API
*
******************************************************************************/

// find returns the first match of the regex in text.
pub fn (r &Regex) find(text string) ?Match {
    return r.find_from(text, 0)
}

// find_from returns the first match starting from start_index.
// Optimized with fast prefix skipping and anchor checks.
pub fn (r &Regex) find_from(text string, start_index int) ?Match {
    if start_index < 0 || start_index > text.len {
        return none
    }
    mut m := r.new_machine()

    // Optimization: Anchored pattern (^) only checks the start
    if r.anchored {
        if start_index == 0 {
            return r.vm_match(text, 0, mut m)
        }
        // If multiline mode is NOT enabled, ^ only matches index 0.
        // If multiline is enabled, we need to check every newline, handled by logic below.
        // Note: The compiler sets anchored=true only for ^ at start.
        // If multiline flag is set dynamically inside pattern, strict anchoring logic might differ,
        // but standard ^ usage benefits here.
    }

    // Optimization: Boyer-Moore-like literal prefix skip
    if r.has_prefix {
        mut i := text.index_after(r.prefix_lit, start_index) or { -1 }
        for i != -1 {
            if res := r.vm_match(text, i, mut m) {
                return res
            }
            i = text.index_after(r.prefix_lit, i + 1) or { -1 }
        }
        return none
    }

    for i := start_index; i <= text.len; i++ {
        // Skip UTF-8 continuation bytes to ensure we only match at rune boundaries
        // 0xC0 (11000000) is the start of a multi-byte sequence, 0x80 (10000000) is a continuation
        if i > 0 && i < text.len && (text[i] & 0xC0) == 0x80 {
            continue
        }
        if res := r.vm_match(text, i, mut m) {
            return res
        }
    }
    return none
}

// find_all returns all non-overlapping matches in text.
pub fn (r &Regex) find_all(text string) []Match {
    mut matches := []Match{}
    mut m := r.new_machine()
    mut i := 0
    for i <= text.len {
        if i > 0 && i < text.len && (text[i] & 0xC0) == 0x80 {
            i++
            continue
        }
        if res := r.vm_match(text, i, mut m) {
            matches << res
            if res.end > i {
                i = res.end
            } else {
                // Empty match: advance by one full rune to avoid infinite loop
                _, rune_len := read_rune_at(text.str, text.len, i)
                i += if rune_len > 0 { rune_len } else { 1 }
            }
        } else {
            i++
        }
    }
    return matches
}

// replace finds the first match and replaces it using repl. Supports $1, $2 backreferences.
pub fn (r &Regex) replace(text string, repl string) string {
    res := r.find(text) or { return text }
    mut sb := strings.new_builder(text.len + repl.len)
    sb.write_string(text[0..res.start])
    mut i := 0
    for i < repl.len {
        if repl[i] == `$` && i + 1 < repl.len {
            next_char := repl[i + 1]
            if next_char >= `0` && next_char <= `9` {
                d := next_char - `0` - 1
                if d >= 0 && d < res.groups.len {
                    sb.write_string(res.groups[d])
                }
                i += 2
                continue
            }
        }
        sb.write_u8(repl[i])
        i++
    }
    sb.write_string(text[res.end..])
    return sb.str()
}

// fullmatch returns a Match only if the pattern matches the entire text.
pub fn (r &Regex) fullmatch(text string) ?Match {
    mut m := r.new_machine()
    if res := r.vm_match(text, 0, mut m) {
        if res.end == text.len {
            return res
        }
    }
    return none
}

// group_by_name retrieves text captured by a named group.
pub fn (r &Regex) group_by_name(m Match, name string) string {
    idx := r.group_map[name] or { return '' }
    return if idx < m.groups.len { m.groups[idx] } else { '' }
}

/******************************************************************************
*
* Compatibility Layer
*
******************************************************************************/

// new_regex is a helper wrapper to compile a regex pattern.
pub fn new_regex(pattern string, _ int) !Regex {
    return compile(pattern)
}

// match_str is a compatibility alias for find_from.
pub fn (r &Regex) match_str(text string, start_index int, _ int) ?Match {
    return r.find_from(text, start_index)
}

// get returns the matched text for a specific group index.
// Index 0 returns the full match, 1..n returns capture groups.
pub fn (m Match) get(idx int) ?string {
    if idx == 0 {
        return m.text
    }
    if idx > 0 && idx <= m.groups.len {
        return m.groups[idx - 1]
    }
    return none
}

// get_all returns a list of all captured strings, starting with the full match at index 0.
pub fn (m Match) get_all() []string {
    mut res := [m.text]
    res << m.groups
    return res
}