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 #[must_use]
180 pub fn new(kind: SyntaxKind, children: Vec<GreenChild>) -> Self {
181 let text_len: usize = children.iter().map(GreenChild::text_len).sum();
182 let text_len = u32::try_from(text_len)
183 .expect("YAML document exceeds 4 GiB — parser cap should have rejected this earlier");
184 Self {
185 kind,
186 text_len,
187 children: Arc::from(children),
188 }
189 }
190
191 /// Classification of this node.
192 #[must_use]
193 pub fn kind(&self) -> SyntaxKind {
194 self.kind
195 }
196
197 /// Total byte length of this node's text.
198 ///
199 /// Returns `usize` for ergonomic arithmetic at call sites; the
200 /// underlying `u32` storage is widened at this boundary.
201 #[must_use]
202 pub fn text_len(&self) -> usize {
203 self.text_len as usize
204 }
205
206 /// Iterate immediate children of this node.
207 pub fn children(&self) -> impl Iterator<Item = &GreenChild> {
208 self.children.iter()
209 }
210
211 /// Concatenation of every descendant leaf's text in document
212 /// order, given the source string the leaves index into. For
213 /// an unmodified parse this is identical to the input. For a
214 /// post-edit document call this with [`crate::cst::Document::source`].
215 #[must_use]
216 pub fn text(&self, source: &str) -> String {
217 let mut out = String::with_capacity(self.text_len as usize);
218 let _ = self.write_text(&mut out, source, 0);
219 out
220 }
221
222 /// Append the descendant text into `out`. Used by
223 /// [`Self::text`] and by the document-level `Display` impl.
224 pub(crate) fn write_text(&self, out: &mut String, source: &str, offset: usize) -> usize {
225 let mut pos = offset;
226 for child in self.children.iter() {
227 pos = child.write_text(out, source, pos);
228 }
229 pos
230 }
231}