regex_anre/

object.rs

// Copyright (c) 2025 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::transition::Transition;

pub const MAIN_ROUTE_INDEX: usize = 0;

// The `Map` structure:
//
// ```diagram
// Map
// |
// |-- Main route --\
// |                |-- node 0 --\
// |                |            |- path --> points to the next node
// |                |            |- path --> points to the next node
// |                |            |- ...
// |                |            \- path --> points to the next node
// |                |-- node 1
// |                |-- ...
// |                |-- node N
// |
// |-- Sub route (generated by lookaround assertions)
// |-- Sub route (generated by lookaround assertions)
// ```

// The `Map` represents the result of compilation.
//
// One regular expression generates one map.
#[derive(Debug)]
pub struct Map {
    // Generally, one regular expression consists of a series of nodes, which forming a "route."
    // However, "lookahead assertions" and "lookbehind assertions" in the regular expression
    // generate sub-routes. Therefore, one map may contains multiple routes,
    // in which the first route is the main route, and others are sub-routes.
    pub routes: Vec<Route>,

    // The capture groups with optional names.
    //
    // All capture groups have a unique index, and some of them may have a name.
    // This vector is used to store the names of capture groups, where
    // the index of the name corresponds to the capture group index.
    pub capture_groups: Vec<Option<String>>,

    pub repetition_counter_count: usize,
}

// A `Route` represents a series of nodes.
#[derive(Debug)]
pub struct Route {
    // A route consists of multiple nodes.
    // Each node contains multiple transitions (or character patterns),
    // which are conceptually similar to functions in programming languages.
    pub nodes: Vec<Node>,

    // The index of the entry node in the node list.
    pub entry_node_index: usize,

    // The index of the exit node in the node list.
    pub exit_node_index: usize,

    // True if the expression starts with the line begin boundary assertion `^`,
    // meaning that if a route match fails,
    // the process will not move the beginning point forward (one character) and try matching again.
    // This is also true for "lookahead assertions" and "lookbehind assertions" sub-routes,
    // thus the lookbehind assertion can only match a fixed number of characters in ANRE.
    pub is_fixed_cursor_begin_position: bool,
}

// A route consists of multiple nodes.
// Each node has one or more paths to the next node,
// except for the `exit node`, which is the end of the route and has no path.
#[derive(Debug)]
pub struct Node {
    pub path: Vec<Path>,
}

// Represents a transition item and the index of the next node to go to when the transition executes successfully.
#[derive(Debug)]
pub struct Path {
    // The transition object.
    // A transition represents a condition to be satisfied for the route to continue to the next node.
    // It is similar to the condition in an `if` statement in programming languages.
    pub transition: Transition,

    // The index of the next node to go to when the transition executes successfully.
    pub target_node_index: usize,
}

impl Map {
    pub fn new() -> Self {
        Map {
            routes: vec![],
            capture_groups: vec![],
            repetition_counter_count: 0,
        }
    }

    // Creates a route object and returns its index.
    pub fn create_route(&mut self) -> usize {
        let route = Route {
            nodes: vec![],
            entry_node_index: 0,
            exit_node_index: 0,
            is_fixed_cursor_begin_position: false,
        };

        let idx = self.routes.len();
        self.routes.push(route);
        idx
    }

    // Creates a capture group object and returns its index.
    pub fn create_capture_group(&mut self, name: Option<String>) -> usize {
        let idx = self.capture_groups.len();
        self.capture_groups.push(name);
        idx
    }

    pub fn create_repetition_counter(&mut self) -> usize {
        let idx = self.repetition_counter_count;
        self.repetition_counter_count += 1;
        idx
    }

    // Retrieves the index of a capture group by its name.
    //
    // Returns `None` if there is no capture group with the specified name.
    pub fn get_capture_group_index_by_name(&self, name: &str) -> Option<usize> {
        self.capture_groups.iter().position(|item| match item {
            Some(n) => n == name,
            None => false,
        })
    }

    // Retrieves the name of a capture group by its index.
    //
    // Returns `None` if there is no capture group name with the specified index.
    pub fn get_capture_group_name_by_index(&self, index: usize) -> Option<&str> {
        let opt_name = &self.capture_groups[index];
        if let Some(name) = opt_name {
            Some(name.as_str())
        } else {
            None
        }
    }

    // For debugging: generates a textual representation of the map.
    pub fn get_debug_text(&self) -> String {
        let mut buffer = vec![];

        // Routes
        if self.routes.len() == 1 {
            buffer.push(self.routes[0].get_debug_text());
        } else {
            for (route_index, route) in self.routes.iter().enumerate() {
                buffer.push(format!("= route: ${}", route_index));
                buffer.push(route.get_debug_text());
                buffer.push("".to_string());
            }
        }

        // Capture groups
        for (capture_group_index, opt_capture_group_name) in self.capture_groups.iter().enumerate()
        {
            let s = if let Some(name) = &opt_capture_group_name {
                format!("# capture: {{{}}}, name: {}", capture_group_index, name)
            } else {
                format!("# capture: {{{}}}", capture_group_index)
            };
            buffer.push(s);
        }

        buffer.join("\n")
    }
}

impl Default for Map {
    fn default() -> Self {
        Self::new()
    }
}

impl Route {
    // Creates a node object and returns its index.
    pub fn create_node(&mut self) -> usize {
        let node = Node { path: vec![] };
        let idx = self.nodes.len();
        self.nodes.push(node);

        idx
    }

    // Creates a path object and returns its index.
    pub fn create_path(
        &mut self,
        source_node_index: usize,
        target_node_index: usize,
        transition: Transition,
    ) -> usize {
        let transition_item = Path {
            transition,
            target_node_index,
        };

        let idx = self.nodes[source_node_index].path.len();

        self.nodes[source_node_index].path.push(transition_item);

        idx
    }

    // For debugging: generates a textual representation of the route.
    pub fn get_debug_text(&self) -> String {
        let mut buffer = vec![];

        for (node_index, node) in self.nodes.iter().enumerate() {
            // Node
            if node_index == self.entry_node_index {
                buffer.push(format!("* node: {} (in)", node_index));
            } else if node_index == self.exit_node_index {
                buffer.push(format!("* node: {} (out)", node_index));
            } else {
                buffer.push(format!("* node: {}", node_index));
            }

            // Transition items
            for transition_item in &node.path {
                let s = format!(
                    "  - {} -> {}",
                    transition_item.transition, transition_item.target_node_index
                );
                buffer.push(s);
            }
        }

        buffer.join("\n")
    }
}

// Component is a logical concept in the compiler, it is used to wrap the nodes and transitions generated by an expression,
// and provide a unified interface (an "in port" and an "out port") for connecting with other components.
//
// In the code views, a component is just a pair of `Node` objects.
//
// The following diagram illustrates the simplest case of a component, which is
// a component that contains a single literal transition.
//
// ```diagram
//   /-----------------------------\
//   |          literal            |
//   |        | transition         |
//   |        v                    |
// =====o==-------------------==o=====
//   | in node            out node |
//   |                             |
//   \----- literal component -----/
// ```
//
// Component can be nested, for example a group component can contain another group component.
//
// The following diagram illustrates a group component that wraps components
// and connects them with jump transitions.
//
// ```diagram
//   /-------------------------------------------------------------\
//   |                    jump                  other components   |
//   |                  | transition          | and transitions    |
//   |                  |                     |                    |
//   |  /-----------\   |     /-----------\   |     /-----------\  |
// =====o in    out o==-----==o in    out o==.....==o in    out o=====
//   |  \-----------/         \-----------/         \-----------/  |
//   |    component             component             component    |
//   |                                                             |
//   \----------------------- group component ---------------------/
// ```
//
// A regular expression is compiled into
// nodes and transitions, but in the program views, they are wrapped into components, at the
// root level, a program is a single component, and the "in port" of the component is the
// entry point of the program, and the "out port" of the component is the exit point of the program.
//
// The following diagram illustrates a program component that wraps a root expression component
// with indexed capturing transitions.
//
// ```diagram
//   /---------------------------------------------------------\
//   |                                                         |
//   |  capture start |                     capture end |      |
//   |     transition |                      transition |      |
//   |                V    /-------------\              v      |
// =====o==-------------===o in      out o===-------------==o=====
//   |  in                 \-------------/                 out |
//   |  node               root expression                node |
//   |                        component                        |
//   |                                                         |
//   \------------------- program component--------------------/
// ```
pub struct Component {
    pub in_node_index: usize,
    pub out_node_index: usize,
}

impl Component {
    pub fn new(in_node_index: usize, out_node_index: usize) -> Self {
        Component {
            in_node_index,
            out_node_index,
        }
    }
}

#[cfg(test)]
mod tests {
    use pretty_assertions::{assert_eq, assert_str_eq};

    use crate::{
        object::Map,
        transition::{CharTransition, Transition},
    };

    #[test]
    fn test_object_file_create_route() {
        let mut object = Map::new();

        // Create a route
        {
            let route_index = object.create_route();
            let route = &mut object.routes[route_index];

            // Create a node
            let _idx0 = route.create_node();

            assert_str_eq!(
                route.get_debug_text(),
                "\
* node: 0 (in)"
            );

            // Create other nodes
            let idx1 = route.create_node();
            let _idx2 = route.create_node();
            let idx3 = route.create_node();

            route.entry_node_index = idx1;
            route.exit_node_index = idx3;

            assert_str_eq!(
                route.get_debug_text(),
                "\
* node: 0
* node: 1 (in)
* node: 2
* node: 3 (out)"
            );
        }

        // Create another route
        {
            let route_index = object.create_route();
            let route = &mut object.routes[route_index];

            // Create a node
            let _idx0 = route.create_node();

            assert_str_eq!(
                object.get_debug_text(),
                "\
= route: $0
* node: 0
* node: 1 (in)
* node: 2
* node: 3 (out)

= route: $1
* node: 0 (in)
"
            );
        }
    }

    #[test]
    fn test_object_file_create_capture_group() {
        let mut object = Map::new();
        let route_index = object.create_route();
        let route = &mut object.routes[route_index];

        route.create_node();
        route.create_node();

        object.create_capture_group(None);
        object.create_capture_group(Some("foo".to_string()));
        object.create_capture_group(None);

        assert_str_eq!(
            object.get_debug_text(),
            "\
* node: 0 (in)
* node: 1
# capture: {0}
# capture: {1}, name: foo
# capture: {2}"
        );

        assert_eq!(object.get_capture_group_index_by_name("foo"), Some(1));
        assert!(object.get_capture_group_index_by_name("bar").is_none());
    }

    #[test]
    fn test_object_file_create_path() {
        let mut object = Map::new();
        let route_index = object.create_route();
        let route = &mut object.routes[route_index];

        let node_idx0 = route.create_node();
        let node_idx1 = route.create_node();
        let node_idx2 = route.create_node();
        let node_idx3 = route.create_node();

        let trans_idx0 = route.create_path(
            node_idx0,
            node_idx1,
            Transition::Char(CharTransition::new('a')),
        );

        assert_str_eq!(
            route.get_debug_text(),
            "\
* node: 0 (in)
  - Char 'a' -> 1
* node: 1
* node: 2
* node: 3"
        );

        assert_eq!(trans_idx0, 0);

        let trans_idx1 = route.create_path(
            node_idx0,
            node_idx2,
            Transition::Char(CharTransition::new('b')),
        );

        let trans_idx2 = route.create_path(
            node_idx0,
            node_idx3,
            Transition::Char(CharTransition::new('c')),
        );

        assert_str_eq!(
            route.get_debug_text(),
            "\
* node: 0 (in)
  - Char 'a' -> 1
  - Char 'b' -> 2
  - Char 'c' -> 3
* node: 1
* node: 2
* node: 3"
        );

        assert_eq!(trans_idx1, 1);
        assert_eq!(trans_idx2, 2);

        let trans_idx3 = route.create_path(
            node_idx1,
            node_idx2,
            Transition::Char(CharTransition::new('x')),
        );

        assert_str_eq!(
            route.get_debug_text(),
            "\
* node: 0 (in)
  - Char 'a' -> 1
  - Char 'b' -> 2
  - Char 'c' -> 3
* node: 1
  - Char 'x' -> 2
* node: 2
* node: 3"
        );

        assert_eq!(trans_idx3, 0);
    }
}