regex-anre 2.1.2

// Copyright (c) 2026 Hemashushu <hippospark@gmail.com>, All rights reserved.
//
// This Source Code Form is subject to the terms of
// the Mozilla Public License version 2.0 and additional exceptions.
// For more details, see the LICENSE, LICENSE.additional, and CONTRIBUTING files.

use crate::{
    context::{Context, MatchRange, Routine},
    object::{MAIN_ROUTE_INDEX, Map},
    transition::{CharSetItem, RepetitionType, Transition},
    utf8_codepoint_reader::{next_codepoint, previous_codepoint},
};

/// Start a new process.
///
/// A process represents a single matching operation.
/// The first time matching is started from the position 0 of the source text,
/// and it is the (`last position of matching` + `matching length`) for subsequent matchings.
pub fn start_process(context: &mut Context, object: &Map, start_position: usize) -> bool {
    // The end position is the length of the source text.
    let end = context.bytes.len();

    // Start the main routine for matching.
    start_routine(context, object, MAIN_ROUTE_INDEX, start_position, end)
}

/// Start a routine.
///
/// A routine corresponds to a route, thus
/// sub-routines (generated by lookaround assertions) also invoke this function.
/// The `route_index`, `start_position`, and `end_position` parameters specify the route index
/// and the text range for the routine.
/// The `context.routines` stack is used to record sub-routines.
pub fn start_routine(
    context: &mut Context,
    map: &Map,
    route_index: usize,
    start_position: usize, // Start position (inclusive, in bytes) of the searching text range .
    end_position: usize,   // End position (exclusive, in bytes) of the searching text range.
) -> bool {
    let mut result = false;
    let mut cursor = start_position;

    // Add a routine for the route to the context.
    let routine = Routine::new(start_position, end_position, route_index);
    context.routines.push(routine);

    // Continue moving the start position forward and retry matching
    // until a match is successful or the end of the searching range is reached.
    while cursor < end_position {
        if execute_transitions(context, map, cursor) {
            result = true;
            break;
        }

        // If the expression starts with "^...", there is no need to try remaining characters.
        if map.routes[route_index].is_fixed_cursor_begin_position {
            break;
        }

        // Move forward by one character and try again.
        let (_, byte_length) = next_codepoint(context.bytes, cursor);
        cursor += byte_length;
    }

    // Remove the routine for the route from the context.
    context.routines.pop();
    result
}

/// Execute transitions for a route starting from a specified position.
/// Returns `true` if all transitions succeed, otherwise `false`.
fn execute_transitions(context: &mut Context, map: &Map, cursor: usize) -> bool {
    let (route_index, entry_node_index, exit_node_index) = {
        let routine = context.get_current_routine_ref();
        let route_index = routine.route_index;
        let route = &map.routes[route_index];
        (route_index, route.entry_node_index, route.exit_node_index)
    };

    // Add transitions of the entry node.
    context.push_transitions_of_node(map, entry_node_index, cursor, 0);

    // Transitions are similar to functions in programming languages.
    // `transition_stack` is similar to a call stack.
    //
    // In detail, a route consists of multiple nodes, when a routine is running,
    // it traverses nodes one by one based on transitions. Each node contains one or more transitions,
    // these transitions are pushed onto this stack for backtracking purposes.
    //
    // When a transition is executed, it is popped from the stack:
    // - On failure: The next transition is popped and tried. If the stack is empty,
    //   it indicates that the route matching has failed.
    // - On success: The routine moves to the next node pointed to by the transition
    //   and pushes all transitions of the new node onto the stack. If the node is the
    //   last node (which is called the exit node) of the route, it means the route matching has succeeded.
    while let Some(frame) = context.pop_transition_stack_item() {
        let route = &map.routes[route_index];
        let node = &route.nodes[frame.current_node_index];
        let transition_item = &node.path[frame.transition_index];

        let last_cursor = frame.cursor;
        let last_repetition_count = frame.repetition_count;
        let transition = &transition_item.transition;
        let target_node_index = transition_item.target_node_index;

        let execute_result = transition.execute(context, map, last_cursor, last_repetition_count);

        match execute_result {
            ExecuteResult::Success(move_forward_in_bytes, current_repetition_count) => {
                if target_node_index == exit_node_index {
                    // Reached the exit node of the route, meaning the route matching succeeded.
                    return true;
                }

                // Add transitions of the target node.
                context.push_transitions_of_node(
                    map,
                    target_node_index,
                    last_cursor + move_forward_in_bytes,
                    current_repetition_count,
                );
            }
            ExecuteResult::Failure => {
                // Check the next transition.
            }
        }
    }

    // All transitions failed, meaning the route matching failed.
    false
}

impl Transition {
    /// Executes the transition and returns the result.
    ///
    /// Note that the `cursor` and `repetition_count` should be passed as parameters
    /// instead of being stored in the context because they are specific to the transition being executed
    /// and may change during backtracking.
    pub fn execute(
        &self,
        context: &mut Context,
        map: &Map,

        // the current position.
        //
        // position is a cursor in the source text.
        cursor: usize,

        // the current repetition number.
        //
        // it is used by:
        // - `Transition::RepetitionForward`
        // - `Transition::RepetitionBack`
        repetition_count: usize,
    ) -> ExecuteResult {
        match self {
            Transition::Jump(_) => {
                // jumping transition always success,
                //
                // jumping transition has no character movement (no source bytes are consumed).
                ExecuteResult::Success(0, 0)
            }
            Transition::Char(transition) => {
                let routine = context.get_current_routine_ref();

                if cursor >= routine.range_end {
                    ExecuteResult::Failure
                } else {
                    let (cp, _) = next_codepoint(context.bytes, cursor);
                    if cp == transition.codepoint {
                        ExecuteResult::Success(transition.byte_length, 0)
                    } else {
                        ExecuteResult::Failure
                    }
                }
            }
            Transition::AnyChar(_) => {
                let routine = context.get_current_routine_ref();

                if cursor >= routine.range_end {
                    ExecuteResult::Failure
                } else {
                    let (current_char, byte_length) = get_char(context.bytes, cursor);

                    // "char_any" does not include new-line characters.
                    // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_expressions/Character_classes
                    if current_char != '\n' as u32 && current_char != '\r' as u32 {
                        ExecuteResult::Success(byte_length, 0)
                    } else {
                        ExecuteResult::Failure
                    }
                }
            }
            Transition::String(transition) => {
                let routine = context.get_current_routine_ref();

                if cursor + transition.byte_length > routine.range_end {
                    ExecuteResult::Failure
                } else {
                    let mut all_code_point_matched = true;
                    let mut current_position: usize = cursor;

                    for expected_codepoint in &transition.codepoints {
                        let (actual_code_point, length) =
                            next_codepoint(context.bytes, current_position);
                        if *expected_codepoint != actual_code_point {
                            all_code_point_matched = false;
                            break;
                        }
                        current_position += length;
                    }

                    if all_code_point_matched {
                        ExecuteResult::Success(transition.byte_length, 0)
                    } else {
                        ExecuteResult::Failure
                    }
                }
            }
            Transition::CharSet(transition) => {
                let routine = context.get_current_routine_ref();

                if cursor >= routine.range_end {
                    return ExecuteResult::Failure;
                }

                let (current_char, byte_length) = get_char(context.bytes, cursor);
                let mut found_any: bool = false;

                for item in &transition.items {
                    found_any = match item {
                        CharSetItem::Char(c) => current_char == *c,
                        CharSetItem::Range(r) => {
                            current_char >= r.start && current_char <= r.end_inclusive
                        }
                    };

                    if found_any {
                        break;
                    }
                }

                if found_any ^ transition.negative {
                    ExecuteResult::Success(byte_length, 0)
                } else {
                    ExecuteResult::Failure
                }
            }
            Transition::BackReference(transition) => {
                let MatchRange { start, end } =
                    &context.matched_slots[transition.capture_group_index];

                let bytes = &context.bytes[*start..*end];
                let length_in_byte = end - start;

                let routine = context.get_current_routine_ref();

                if cursor + length_in_byte > routine.range_end {
                    ExecuteResult::Failure
                } else {
                    let mut all_byte_matched = true;

                    for (idx, actual_byte) in bytes.iter().enumerate() {
                        if actual_byte != &context.bytes[idx + cursor] {
                            all_byte_matched = false;
                            break;
                        }
                    }

                    if all_byte_matched {
                        ExecuteResult::Success(length_in_byte, 0)
                    } else {
                        ExecuteResult::Failure
                    }
                }
            }
            Transition::LineBoundaryAssertion(transition) => {
                let bytes = context.bytes;
                let success = if transition.is_end {
                    is_end(bytes, cursor)
                } else {
                    is_first_char(cursor)
                };

                if success {
                    ExecuteResult::Success(0, 0)
                } else {
                    ExecuteResult::Failure
                }
            }
            Transition::WordBoundaryAssertion(transition) => {
                let bytes = context.bytes;
                let success = if transition.is_negative {
                    !is_word_bound(bytes, cursor)
                } else {
                    is_word_bound(bytes, cursor)
                };

                if success {
                    ExecuteResult::Success(0, 0)
                } else {
                    ExecuteResult::Failure
                }
            }
            Transition::CaptureStart(transition) => {
                context.matched_slots[transition.capture_group_index].start = cursor;
                context.matched_slots[transition.capture_group_index].end = cursor;
                ExecuteResult::Success(0, 0)
            }
            Transition::CaptureEnd(transition) => {
                context.matched_slots[transition.capture_group_index].end = cursor;
                ExecuteResult::Success(0, 0)
            }
            Transition::CounterReset(transition) => {
                let counter_index = transition.counter_index;
                context.counter_slots[counter_index] = 0;
                ExecuteResult::Success(0, 0)
            }
            Transition::CounterIncrement(transition) => {
                let counter_index = transition.counter_index;
                let new_count = context.counter_slots[counter_index] + 1;
                context.counter_slots[counter_index] = new_count;
                ExecuteResult::Success(0, new_count)
            }
            Transition::RepetitionForward(transition) => {
                let can_forward = match transition.repetition_type {
                    RepetitionType::Repeat(m) => repetition_count == m,
                    RepetitionType::RepeatFrom(from) => repetition_count >= from,
                    RepetitionType::RepeatRange(from, to) => {
                        repetition_count >= from && repetition_count <= to
                    }
                };
                if can_forward {
                    ExecuteResult::Success(0, repetition_count)
                } else {
                    ExecuteResult::Failure
                }
            }
            Transition::RepetitionBack(transition) => {
                let can_backward = match transition.repetition_type {
                    RepetitionType::Repeat(n) => repetition_count < n,
                    RepetitionType::RepeatFrom(_) => true,
                    RepetitionType::RepeatRange(_, to) => repetition_count < to,
                };
                if can_backward {
                    ExecuteResult::Success(0, repetition_count)
                } else {
                    ExecuteResult::Failure
                }
            }
            Transition::LookAheadAssertion(transition) => {
                let route_index = transition.route_index;
                let routine_result =
                    start_routine(context, map, route_index, cursor, context.bytes.len());

                let result = routine_result ^ transition.is_negative;
                if result {
                    // assertion should not move the position of parent thread
                    const NO_FORWARD: usize = 0;
                    ExecuteResult::Success(NO_FORWARD, 0)
                } else {
                    ExecuteResult::Failure
                }
            }
            Transition::LookBehindAssertion(transition) => {
                let route_index = transition.route_index;
                let routine_result = if let Ok(start) = get_position_by_chars_backward(
                    context.bytes,
                    cursor,
                    transition.match_length_in_char,
                ) {
                    // the child thread should start at position `current_position - backward_count_in_bytes`.
                    start_routine(context, map, route_index, start, context.bytes.len())
                } else {
                    false
                };

                let result = routine_result ^ transition.is_negative;
                if result {
                    // assertion should not move the position of parent thread
                    const NO_FORWARD: usize = 0;
                    ExecuteResult::Success(NO_FORWARD, 0)
                } else {
                    ExecuteResult::Failure
                }
            }
        }
    }
}

// Return `Err` if the position it less than 0
#[inline]
fn get_position_by_chars_backward(
    bytes: &[u8],
    mut current_position: usize,
    backward_chars: usize,
) -> Result<usize, ()> {
    for _ in 0..backward_chars {
        if current_position == 0 {
            return Err(());
        }

        let (_, char_length_in_byte) = previous_codepoint(bytes, current_position);
        current_position -= char_length_in_byte;
    }

    Ok(current_position)
}

#[inline]
fn get_char(bytes: &[u8], position: usize) -> (u32, usize) {
    next_codepoint(bytes, position)
}

#[inline]
fn is_first_char(position: usize) -> bool {
    position == 0
}

#[inline]
fn is_end(bytes: &[u8], position: usize) -> bool {
    let total_byte_length = bytes.len();
    position >= total_byte_length
}

#[inline]
fn is_word_bound(bytes: &[u8], position: usize) -> bool {
    if bytes.is_empty() {
        false
    } else if position == 0 {
        let (current_char, _) = get_char(bytes, position);
        is_word_char(current_char)
    } else if position >= bytes.len() {
        // Because the "mactching" operation moves forward one character,
        // so only the previous character is needed to be checked.
        let (previous_char, _) = get_char(bytes, position - 1);
        is_word_char(previous_char)
    } else {
        // Because the "mactching" operation moves forward one character,
        // so only the previous character is needed to be checked.
        let (current_char, _) = get_char(bytes, position);
        let (previous_char, _) = get_char(bytes, position - 1);

        if is_word_char(current_char) {
            !is_word_char(previous_char)
        } else {
            is_word_char(previous_char)
        }
    }
}

#[inline]
fn is_word_char(c: u32) -> bool {
    (c >= 'a' as u32 && c <= 'z' as u32)
        || (c >= 'A' as u32 && c <= 'Z' as u32)
        || (c >= '0' as u32 && c <= '9' as u32)
        || (c == '_' as u32)
}

/// Represents the result of executing a transition.
pub enum ExecuteResult {
    Success(
        usize, // Number of bytes to move forward
        usize, // The latest repetition count
    ),
    Failure, // Indicates that the transition failed
}