oak_core/tree/
green_tree.rs

1//! Green tree implementation for immutable kind tree representation.
2//!
3//! This module provides the "green" side of the red-green tree architecture.
4//! In this high-performance implementation, green nodes are allocated in a
5//! `SyntaxArena` and do not use reference counting.
6
7use crate::Language;
8use std::{
9    fmt,
10    hash::{Hash, Hasher},
11};
12
13/// A green tree element - either a node or a leaf kind.
14///
15/// Green trees represent the immutable structure of kind trees without
16/// position information.
17pub enum GreenTree<'a, L: Language> {
18    /// A green node with child elements
19    Node(&'a GreenNode<'a, L>),
20    /// A green leaf kind
21    Leaf(GreenLeaf<L>),
22}
23
24// Manually implement Clone/Copy to avoid L: Copy bound
25impl<'a, L: Language> Clone for GreenTree<'a, L> {
26    fn clone(&self) -> Self {
27        *self
28    }
29}
30
31impl<'a, L: Language> Copy for GreenTree<'a, L> {}
32
33impl<'a, L: Language> fmt::Debug for GreenTree<'a, L> {
34    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
35        match self {
36            Self::Node(node) => fmt::Debug::fmt(node, f),
37            Self::Leaf(leaf) => fmt::Debug::fmt(leaf, f),
38        }
39    }
40}
41
42impl<'a, L: Language> PartialEq for GreenTree<'a, L> {
43    fn eq(&self, other: &Self) -> bool {
44        match (self, other) {
45            (Self::Node(l0), Self::Node(r0)) => l0 == r0,
46            (Self::Leaf(l0), Self::Leaf(r0)) => l0 == r0,
47            _ => false,
48        }
49    }
50}
51
52impl<'a, L: Language> Eq for GreenTree<'a, L> {}
53
54impl<'a, L: Language> Hash for GreenTree<'a, L> {
55    fn hash<H: Hasher>(&self, state: &mut H) {
56        match self {
57            Self::Node(node) => node.hash(state),
58            Self::Leaf(leaf) => leaf.hash(state),
59        }
60    }
61}
62
63impl<'a, L: Language> GreenTree<'a, L> {
64    /// Returns the total byte length of this green tree element.
65    ///
66    /// For nodes, this is the sum of all children's lengths.
67    /// For leaves, this is the length of the token.
68    #[inline]
69    pub fn len(&self) -> u32 {
70        match self {
71            GreenTree::Node(n) => n.text_len,
72            GreenTree::Leaf(t) => t.length,
73        }
74    }
75
76    /// Checks if this green tree element is a node.
77    #[inline]
78    pub fn is_node(&self) -> bool {
79        matches!(self, Self::Node(_))
80    }
81
82    /// Checks if this green tree element is a leaf.
83    #[inline]
84    pub fn is_leaf(&self) -> bool {
85        matches!(self, Self::Leaf(_))
86    }
87
88    /// Returns the element as a node if it is one.
89    #[inline]
90    pub fn as_node(&self) -> Option<&'a GreenNode<'a, L>> {
91        match self {
92            Self::Node(n) => Some(n),
93            _ => None,
94        }
95    }
96
97    /// Returns the element as a leaf if it is one.
98    #[inline]
99    pub fn as_leaf(&self) -> Option<GreenLeaf<L>> {
100        match self {
101            Self::Leaf(l) => Some(*l),
102            _ => None,
103        }
104    }
105}
106
107/// A green leaf kind that stores only kind and length.
108///
109/// Leaves are the terminal elements of the green tree, representing
110/// individual tokens in the source code.
111pub struct GreenLeaf<L: Language> {
112    /// The token kind/category.
113    pub kind: L::TokenType,
114    /// The byte length of the token text.
115    pub length: u32,
116    /// Optional index into the metadata store for provenance information.
117    ///
118    /// This is used to track where a token came from in complex
119    /// transformations or multi-file sources.
120    pub metadata: Option<std::num::NonZeroU32>,
121}
122
123impl<L: Language> fmt::Debug for GreenLeaf<L> {
124    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
125        f.debug_struct("GreenLeaf").field("kind", &self.kind).field("length", &self.length).field("metadata", &self.metadata).finish()
126    }
127}
128
129impl<L: Language> Hash for GreenLeaf<L> {
130    fn hash<H: Hasher>(&self, state: &mut H) {
131        self.kind.hash(state);
132        self.length.hash(state);
133        self.metadata.hash(state)
134    }
135}
136
137// Manually implement Clone/Copy to avoid L: Copy bound
138impl<L: Language> Clone for GreenLeaf<L> {
139    fn clone(&self) -> Self {
140        *self
141    }
142}
143
144impl<L: Language> Copy for GreenLeaf<L> {}
145
146impl<L: Language> PartialEq for GreenLeaf<L> {
147    fn eq(&self, other: &Self) -> bool {
148        self.kind == other.kind && self.length == other.length && self.metadata == other.metadata
149    }
150}
151
152impl<L: Language> Eq for GreenLeaf<L> {}
153
154impl<L: Language> GreenLeaf<L> {
155    /// Creates a new green leaf kind.
156    ///
157    /// # Arguments
158    ///
159    /// * `kind` - The token type.
160    /// * `len` - The length of the token in bytes.
161    #[inline]
162    pub fn new(kind: L::TokenType, len: u32) -> Self {
163        Self { kind, length: len, metadata: None }
164    }
165
166    /// Creates a new green leaf kind with provenance metadata.
167    ///
168    /// # Arguments
169    ///
170    /// * `kind` - The token type.
171    /// * `len` - The length of the token in bytes.
172    /// * `metadata` - The metadata index.
173    #[inline]
174    pub fn with_metadata(kind: L::TokenType, len: u32, metadata: Option<std::num::NonZeroU32>) -> Self {
175        Self { kind, length: len, metadata }
176    }
177
178    /// Returns the kind of this leaf.
179    #[inline]
180    pub fn kind(&self) -> L::TokenType {
181        self.kind
182    }
183
184    /// Returns the length of this leaf in bytes.
185    #[inline]
186    pub fn length(&self) -> u32 {
187        self.length
188    }
189}
190
191/// A green node that contains child elements.
192///
193/// Green nodes are allocated in a `SyntaxArena` and hold a slice reference
194/// to their children. They are POD (Plain Old Data) and strictly immutable.
195///
196/// Unlike red nodes, green nodes do not know their absolute position in the
197/// source code, which makes them highly reusable for incremental parsing.
198pub struct GreenNode<'a, L: Language> {
199    /// The element type (kind) of this node.
200    pub kind: L::ElementType,
201    /// The total text length of this node (sum of children's lengths) in bytes.
202    pub text_len: u32,
203    /// The children of this node, which can be other nodes or leaf tokens.
204    pub children: &'a [GreenTree<'a, L>],
205}
206
207// Manually implement Clone to avoid L: Clone bound (though L usually is Clone)
208impl<'a, L: Language> Clone for GreenNode<'a, L> {
209    fn clone(&self) -> Self {
210        Self { kind: self.kind, text_len: self.text_len, children: self.children }
211    }
212}
213
214impl<'a, L: Language> PartialEq for GreenNode<'a, L> {
215    fn eq(&self, other: &Self) -> bool {
216        self.kind == other.kind && self.text_len == other.text_len && self.children == other.children
217    }
218}
219
220impl<'a, L: Language> Eq for GreenNode<'a, L> {}
221
222impl<'a, L: Language> fmt::Debug for GreenNode<'a, L> {
223    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
224        f.debug_struct("GreenNode").field("kind", &self.kind).field("children", &self.children).field("length", &self.text_len).finish()
225    }
226}
227
228impl<'a, L: Language> Hash for GreenNode<'a, L> {
229    fn hash<H: Hasher>(&self, state: &mut H) {
230        self.kind.hash(state);
231        self.children.hash(state)
232    }
233}
234
235impl<'a, L: Language> GreenNode<'a, L> {
236    /// Creates a new green node from child elements.
237    ///
238    /// This function assumes the children slice is already allocated in the arena.
239    /// It automatically calculates the total `text_len` by summing child lengths.
240    ///
241    /// # Arguments
242    ///
243    /// * `kind` - The node type.
244    /// * `children` - The slice of child elements.
245    pub fn new(kind: L::ElementType, children: &'a [GreenTree<'a, L>]) -> Self {
246        let len: u32 = children.iter().map(|c| c.len()).sum();
247        Self { kind, text_len: len, children }
248    }
249
250    /// Returns the kind of this node.
251    #[inline]
252    pub fn kind(&self) -> L::ElementType {
253        self.kind
254    }
255
256    /// Returns the total text length of this node in bytes.
257    #[inline]
258    pub fn text_len(&self) -> u32 {
259        self.text_len
260    }
261
262    /// Returns the children of this node.
263    #[inline]
264    pub fn children(&self) -> &'a [GreenTree<'a, L>] {
265        self.children
266    }
267
268    /// Returns a specific child at index.
269    ///
270    /// Returns `None` if the index is out of bounds.
271    #[inline]
272    pub fn child_at(&self, index: usize) -> Option<&'a GreenTree<'a, L>> {
273        self.children.get(index)
274    }
275
276    /// Checks if this node has any children.
277    #[inline]
278    pub fn has_children(&self) -> bool {
279        !self.children.is_empty()
280    }
281
282    /// Returns the number of children in this node.
283    #[inline]
284    pub fn children_count(&self) -> usize {
285        self.children.len()
286    }
287}
oak_core/tree/green_tree.rs

oak_core/tree/
green_tree.rs
