noyalib/cst/green.rs
1// SPDX-License-Identifier: MIT OR Apache-2.0
2// Copyright (c) 2026 Noyalib. All rights reserved.
3
4//! Immutable green-node primitive with relative-length leaves.
5//!
6//! A `GreenNode` is purely structural — it stores `SyntaxKind` plus
7//! children, and tracks `text_len` (the sum of its descendants'
8//! byte lengths). Token leaves carry only their `len`, not an
9//! absolute byte range. The actual source text lives once, on the
10//! [`crate::cst::Document`] that owns the tree; every text-bearing
11//! API takes a `source` argument.
12//!
13//! This shape is what makes incremental edits cheap: a splice only
14//! rewrites the path from the root down to the spliced node's
15//! parent. Pre- and post-splice subtrees are reused via cheap
16//! `Arc<[GreenChild]>` clones — no per-leaf range arithmetic. To
17//! recover an absolute byte position, walk the tree from the root
18//! accumulating offsets — see the doctest on
19//! [`GreenChild::token_text`].
20
21use crate::cst::syntax::SyntaxKind;
22use crate::prelude::*;
23
24/// A leaf-or-node child of a [`GreenNode`].
25///
26/// Token leaves carry only their byte length within their parent.
27/// To materialise text, walk the tree from the root and pass the
28/// running offset down (see [`GreenChild::token_text`]).
29///
30/// # Examples
31///
32/// ```
33/// use noyalib::cst::{parse_document, GreenChild, SyntaxKind};
34///
35/// let doc = parse_document("a: 1\n").unwrap();
36/// let src = doc.source();
37/// // Walk children, tracking byte offset, to materialise leaf text.
38/// let mut offset = 0;
39/// for child in doc.syntax().children() {
40/// if let GreenChild::Token { kind, len } = child {
41/// // `len` is `u32` — cast to `usize` for slice arithmetic.
42/// let text = &src[offset..offset + *len as usize];
43/// assert_eq!(text.is_empty(), false);
44/// let _ = (kind, text);
45/// }
46/// offset += child.text_len();
47/// }
48/// ```
49#[derive(Debug, Clone)]
50pub enum GreenChild {
51 /// A nested node.
52 Node(GreenNode),
53 /// A leaf token. `len` is its byte length in the source — its
54 /// absolute position depends on the running offset accumulated
55 /// while walking from the root.
56 ///
57 /// `len` is `u32` (not `usize`) — YAML documents are bounded
58 /// at 4 GiB by the parser's `max_document_length` cap, and
59 /// the narrower field halves the size of every leaf in the
60 /// CST. On a 64-bit target this drops `GreenChild::Token`
61 /// from 24 bytes to 8 bytes and meaningfully improves L1/L2
62 /// cache locality on tree traversals. Cast to `usize` at
63 /// arithmetic call sites: `&source[offset..offset + len as usize]`.
64 Token {
65 /// Classification of this leaf.
66 kind: SyntaxKind,
67 /// Byte length of this leaf in the source.
68 len: u32,
69 },
70}
71
72impl GreenChild {
73 /// Total byte length of this child's contribution to its
74 /// parent's text. For nodes this is `text_len()`; for tokens
75 /// it is `len`.
76 ///
77 /// Returns `usize` for ergonomic arithmetic at call sites; the
78 /// underlying `u32` storage is widened at this boundary.
79 #[must_use]
80 pub fn text_len(&self) -> usize {
81 match self {
82 Self::Node(n) => n.text_len(),
83 Self::Token { len, .. } => *len as usize,
84 }
85 }
86
87 /// Borrow the source text of this leaf, given `source` (the
88 /// document's source) and `offset` (the running byte position
89 /// at which this child begins). Returns `None` for `Node`
90 /// variants — recurse into them with `offset + 0` as the new
91 /// base for their children.
92 ///
93 /// # Examples
94 ///
95 /// ```
96 /// use noyalib::cst::{parse_document, GreenChild, GreenNode};
97 ///
98 /// fn first_leaf_text<'a>(node: &GreenNode, src: &'a str, base: usize) -> Option<&'a str> {
99 /// let mut offset = base;
100 /// for c in node.children() {
101 /// match c {
102 /// GreenChild::Token { .. } => return c.token_text(src, offset),
103 /// GreenChild::Node(n) => {
104 /// if let Some(t) = first_leaf_text(n, src, offset) {
105 /// return Some(t);
106 /// }
107 /// }
108 /// }
109 /// offset += c.text_len();
110 /// }
111 /// None
112 /// }
113 ///
114 /// let doc = parse_document("a: 1\n").unwrap();
115 /// assert_eq!(first_leaf_text(doc.syntax(), doc.source(), 0), Some("a"));
116 /// ```
117 #[must_use]
118 pub fn token_text<'s>(&self, source: &'s str, offset: usize) -> Option<&'s str> {
119 match self {
120 Self::Token { len, .. } => Some(&source[offset..offset + *len as usize]),
121 Self::Node(_) => None,
122 }
123 }
124
125 /// Append this child's text into `out`. The caller passes the
126 /// document source and the running byte offset at which this
127 /// child begins. Returns the offset past the child's last byte.
128 pub(crate) fn write_text(&self, out: &mut String, source: &str, offset: usize) -> usize {
129 match self {
130 Self::Node(n) => n.write_text(out, source, offset),
131 Self::Token { len, .. } => {
132 let l = *len as usize;
133 out.push_str(&source[offset..offset + l]);
134 offset + l
135 }
136 }
137 }
138}
139
140/// An immutable, byte-faithful syntax-tree node.
141///
142/// A `GreenNode` is purely structural — it carries `kind`,
143/// `text_len`, and an `Arc<[GreenChild]>` of children. The actual
144/// source text lives elsewhere (on the owning [`crate::cst::Document`]),
145/// and every text-bearing API takes the source as an argument.
146///
147/// Cloning a `GreenNode` is `O(1)` — three `Arc` increments at most.
148///
149/// The text of a node is the concatenation, in document order, of
150/// the text of every descendant leaf. For an unmodified parse this
151/// equals the input.
152///
153/// # Examples
154///
155/// ```
156/// use noyalib::cst::parse_document;
157///
158/// let src = "key: value\n";
159/// let doc = parse_document(src).unwrap();
160/// assert_eq!(doc.syntax().text_len(), src.len());
161/// assert_eq!(doc.syntax().text(src), src);
162/// ```
163#[derive(Debug, Clone)]
164pub struct GreenNode {
165 kind: SyntaxKind,
166 /// Sum of every descendant leaf's byte length, narrowed to
167 /// `u32`. YAML documents are bounded at 4 GiB by the parser's
168 /// `max_document_length` cap, so a `u32` is sufficient. The
169 /// narrower field meaningfully improves cache locality on
170 /// tree traversals.
171 text_len: u32,
172 children: Arc<[GreenChild]>,
173}
174
175impl GreenNode {
176 /// Build a green node from its kind and children. The total
177 /// `text_len` is summed from the children — callers do not need
178 /// to compute it separately.
179 ///
180 /// # Panics
181 ///
182 /// Panics if the children's total length exceeds `u32::MAX`
183 /// bytes. The crate's own builders use the fallible form and
184 /// return an error instead.
185 #[must_use]
186 pub fn new(kind: SyntaxKind, children: Vec<GreenChild>) -> Self {
187 Self::try_new(kind, children)
188 .expect("YAML document exceeds 4 GiB — parser cap should have rejected this earlier")
189 }
190
191 /// Fallible [`Self::new`]: `None` when the children's total
192 /// length does not fit the `u32` length field.
193 pub(crate) fn try_new(kind: SyntaxKind, children: Vec<GreenChild>) -> Option<Self> {
194 let mut total: usize = 0;
195 for child in &children {
196 total = total.checked_add(child.text_len())?;
197 }
198 let text_len = u32::try_from(total).ok()?;
199 Some(Self {
200 kind,
201 text_len,
202 children: Arc::from(children),
203 })
204 }
205
206 /// Classification of this node.
207 #[must_use]
208 pub fn kind(&self) -> SyntaxKind {
209 self.kind
210 }
211
212 /// Total byte length of this node's text.
213 ///
214 /// Returns `usize` for ergonomic arithmetic at call sites; the
215 /// underlying `u32` storage is widened at this boundary.
216 #[must_use]
217 pub fn text_len(&self) -> usize {
218 self.text_len as usize
219 }
220
221 /// Iterate immediate children of this node.
222 pub fn children(&self) -> impl Iterator<Item = &GreenChild> {
223 self.children.iter()
224 }
225
226 /// Concatenation of every descendant leaf's text in document
227 /// order, given the source string the leaves index into. For
228 /// an unmodified parse this is identical to the input. For a
229 /// post-edit document call this with [`crate::cst::Document::source`].
230 #[must_use]
231 pub fn text(&self, source: &str) -> String {
232 let mut out = String::with_capacity(self.text_len as usize);
233 let _ = self.write_text(&mut out, source, 0);
234 out
235 }
236
237 /// Append the descendant text into `out`. Used by
238 /// [`Self::text`] and by the document-level `Display` impl.
239 pub(crate) fn write_text(&self, out: &mut String, source: &str, offset: usize) -> usize {
240 let mut pos = offset;
241 for child in self.children.iter() {
242 pos = child.write_text(out, source, pos);
243 }
244 pos
245 }
246}
247
248impl Drop for GreenNode {
249 /// Release the subtree without recursion.
250 ///
251 /// The derived drop would recurse once per nesting level, so a
252 /// deep enough tree would exhaust the stack while it is being
253 /// freed. Each uniquely owned child list is detached and pushed on
254 /// a heap stack instead, so every node is dropped with an empty
255 /// child list. Shared lists (still referenced by another tree after
256 /// an edit) only lose a reference count.
257 fn drop(&mut self) {
258 if !has_node_child(&self.children) {
259 return;
260 }
261 let mut pending = vec![core::mem::replace(&mut self.children, empty_children())];
262 while let Some(mut list) = pending.pop() {
263 let Some(children) = Arc::get_mut(&mut list) else {
264 continue;
265 };
266 for child in children.iter_mut() {
267 if let GreenChild::Node(node) = child
268 && has_node_child(&node.children)
269 {
270 pending.push(core::mem::replace(&mut node.children, empty_children()));
271 }
272 }
273 }
274 }
275}
276
277fn has_node_child(children: &[GreenChild]) -> bool {
278 children.iter().any(|c| matches!(c, GreenChild::Node(_)))
279}
280
281fn empty_children() -> Arc<[GreenChild]> {
282 Arc::from(Vec::new())
283}