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

oak_core/tree/
green_tree.rs
