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    #[inline]
66    pub fn len(&self) -> u32 {
67        match self {
68            GreenTree::Node(n) => n.text_len,
69            GreenTree::Leaf(t) => t.length,
70        }
71    }
72}
73
74/// A green leaf kind that stores only kind and length.
75pub struct GreenLeaf<L: Language> {
76    /// The kind kind/category
77    pub kind: L::TokenType,
78    /// The byte length of the kind text
79    pub length: u32,
80}
81
82// Manually implement Clone/Copy to avoid L: Copy bound
83impl<L: Language> Clone for GreenLeaf<L> {
84    fn clone(&self) -> Self {
85        *self
86    }
87}
88
89impl<L: Language> Copy for GreenLeaf<L> {}
90
91impl<L: Language> PartialEq for GreenLeaf<L> {
92    fn eq(&self, other: &Self) -> bool {
93        self.kind == other.kind && self.length == other.length
94    }
95}
96
97impl<L: Language> Eq for GreenLeaf<L> {}
98
99impl<L: Language> Hash for GreenLeaf<L> {
100    fn hash<H: Hasher>(&self, state: &mut H) {
101        self.kind.hash(state);
102        self.length.hash(state);
103    }
104}
105
106impl<L: Language> fmt::Debug for GreenLeaf<L> {
107    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
108        f.debug_struct("GreenLeaf").field("kind", &self.kind).field("length", &self.length).finish()
109    }
110}
111
112impl<L: Language> GreenLeaf<L> {
113    /// Creates a new green leaf kind.
114    #[inline]
115    pub fn new(kind: L::TokenType, len: u32) -> Self {
116        Self { kind, length: len }
117    }
118}
119
120/// A green node that contains child elements.
121///
122/// Green nodes are allocated in a `SyntaxArena` and hold a slice reference
123/// to their children. They are POD (Plain Old Data) and strictly immutable.
124pub struct GreenNode<'a, L: Language> {
125    /// The element type (kind) of this node.
126    pub kind: L::ElementType,
127    /// The total text length of this node (sum of children's lengths).
128    pub text_len: u32,
129    /// The children of this node.
130    pub children: &'a [GreenTree<'a, L>],
131}
132
133// Manually implement Clone to avoid L: Clone bound (though L usually is Clone)
134impl<'a, L: Language> Clone for GreenNode<'a, L> {
135    fn clone(&self) -> Self {
136        Self { kind: self.kind, text_len: self.text_len, children: self.children }
137    }
138}
139
140impl<'a, L: Language> PartialEq for GreenNode<'a, L> {
141    fn eq(&self, other: &Self) -> bool {
142        self.kind == other.kind && self.text_len == other.text_len && self.children == other.children
143    }
144}
145
146impl<'a, L: Language> Eq for GreenNode<'a, L> {}
147
148impl<'a, L: Language> fmt::Debug for GreenNode<'a, L> {
149    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
150        f.debug_struct("GreenNode").field("kind", &self.kind).field("children", &self.children).field("length", &self.text_len).finish()
151    }
152}
153
154impl<'a, L: Language> Hash for GreenNode<'a, L> {
155    fn hash<H: Hasher>(&self, state: &mut H) {
156        self.kind.hash(state);
157        self.children.hash(state);
158    }
159}
160
161impl<'a, L: Language> GreenNode<'a, L> {
162    /// Creates a new green node from child elements.
163    ///
164    /// This function assumes the children slice is already allocated in the arena.
165    pub fn new(kind: L::ElementType, children: &'a [GreenTree<'a, L>]) -> Self {
166        let len: u32 = children.iter().map(|c| c.len()).sum();
167        Self { kind, text_len: len, children }
168    }
169
170    /// Returns the kind of this node.
171    #[inline]
172    pub fn kind(&self) -> L::ElementType {
173        self.kind
174    }
175
176    /// Returns the total text length of this node.
177    #[inline]
178    pub fn text_len(&self) -> u32 {
179        self.text_len
180    }
181
182    /// Returns the children of this node.
183    #[inline]
184    pub fn children(&self) -> &'a [GreenTree<'a, L>] {
185        self.children
186    }
187
188    /// Returns a specific child at index.
189    #[inline]
190    pub fn child_at(&self, index: usize) -> Option<&'a GreenTree<'a, L>> {
191        self.children.get(index)
192    }
193}
oak_core/tree/green_tree.rs

oak_core/tree/
green_tree.rs
