oak_core/tree/
cursor.rs

1//! efficient Cursor for GreenNode traversal
2//!
3//! This module provides a cursor implementation for traversing GreenTrees
4//! in an Arena-based memory model. It tracks absolute offsets and allows
5//! efficient navigation (up, down, next sibling) without recursion.
6
7use crate::{
8    Language,
9    tree::{GreenNode, GreenTree},
10};
11
12/// A cursor for traversing a GreenTree.
13///
14/// It maintains a path from the root to the current node, allowing for
15/// `parent()` navigation and offset tracking.
16#[derive(Debug, Clone)]
17pub struct Cursor<'a, L: Language> {
18    /// The current element (Node or Leaf).
19    current: GreenTree<'a, L>,
20    /// The absolute start offset of the current element.
21    offset: usize,
22    /// The stack of parent nodes and the index of the current node within them.
23    /// Format: (Parent Node, Index in Parent, Parent Start Offset)
24    stack: Vec<(&'a GreenNode<'a, L>, usize, usize)>,
25}
26
27impl<'a, L: Language> Cursor<'a, L> {
28    /// Creates a new cursor starting at the given root node.
29    pub fn new(root: &'a GreenNode<'a, L>) -> Self {
30        Self { current: GreenTree::Node(root), offset: 0, stack: Vec::with_capacity(16) }
31    }
32
33    /// Returns the current element.
34    #[inline]
35    pub fn current(&self) -> GreenTree<'a, L> {
36        self.current
37    }
38
39    /// Returns the current element as a node, if it is one.
40    #[inline]
41    pub fn as_node(&self) -> Option<&'a GreenNode<'a, L>> {
42        match self.current {
43            GreenTree::Node(n) => Some(n),
44            GreenTree::Leaf(_) => None,
45        }
46    }
47
48    /// Returns the absolute start offset of the current element.
49    #[inline]
50    pub fn offset(&self) -> usize {
51        self.offset
52    }
53
54    /// Returns the text length of the current element.
55    #[inline]
56    pub fn len(&self) -> usize {
57        self.current.len() as usize
58    }
59
60    /// Returns the absolute end offset of the current element.
61    #[inline]
62    pub fn end_offset(&self) -> usize {
63        self.offset + self.len()
64    }
65
66    /// Tries to move to the first child of the current node.
67    /// Returns true if successful (current was a node with children).
68    pub fn step_into(&mut self) -> bool {
69        match self.current {
70            GreenTree::Node(node) => {
71                if let Some(first_child) = node.children.first() {
72                    self.stack.push((node, 0, self.offset));
73                    self.current = *first_child;
74                    // offset remains the same for the first child
75                    true
76                }
77                else {
78                    false
79                }
80            }
81            GreenTree::Leaf(_) => false,
82        }
83    }
84
85    /// Tries to move to the next sibling.
86    /// Returns true if successful.
87    pub fn step_over(&mut self) -> bool {
88        if let Some((parent, idx, _parent_offset)) = self.stack.last() {
89            let next_idx = idx + 1;
90            if let Some(sibling) = parent.children.get(next_idx) {
91                // Update offset: current offset + current len
92                self.offset += self.current.len() as usize;
93
94                // Update stack top
95                let last = self.stack.last_mut().unwrap();
96                last.1 = next_idx;
97
98                self.current = *sibling;
99                true
100            }
101            else {
102                false
103            }
104        }
105        else {
106            false
107        }
108    }
109
110    /// Tries to move to the parent node.
111    /// Returns true if successful (not at root).
112    pub fn step_out(&mut self) -> bool {
113        if let Some((parent, _, parent_offset)) = self.stack.pop() {
114            self.current = GreenTree::Node(parent);
115            self.offset = parent_offset;
116            true
117        }
118        else {
119            false
120        }
121    }
122
123    /// Pre-order traversal step: try into, then over, then out + over.
124    /// Returns true if moved to a new node, false if finished traversal.
125    pub fn step(&mut self) -> bool {
126        if self.step_into() {
127            return true;
128        }
129        if self.step_over() {
130            return true;
131        }
132        while self.step_out() {
133            if self.step_over() {
134                return true;
135            }
136        }
137        false
138    }
139
140    /// Skips the current subtree (like step_over), but if that fails, goes up and over.
141    /// Effectively "next node in post-order" or "next node not in this subtree".
142    pub fn step_next(&mut self) -> bool {
143        if self.step_over() {
144            true
145        }
146        else {
147            while self.step_out() {
148                if self.step_over() {
149                    return true;
150                }
151            }
152            false
153        }
154    }
155}
oak_core/tree/cursor.rs

oak_core/tree/
cursor.rs
