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//! where green nodes are immutable and don't contain position information,
5//! making them cacheable and shareable across different parse trees.
6
7use triomphe::Arc;
8
9/// A green tree element - either a node or a leaf kind.
10///
11/// Green trees represent the immutable structure of kind trees without
12/// position information. They are designed to be cacheable and shareable
13/// across different parse trees and incremental updates.
14#[derive(Debug, Clone)]
15pub enum GreenTree<K: Copy> {
16    /// A green node with child elements
17    Node(Arc<GreenNode<K>>),
18    /// A green leaf kind
19    Leaf(GreenLeaf<K>),
20}
21
22impl<K: Copy> GreenTree<K> {
23    /// Returns the total byte length of this green tree element.
24    ///
25    /// # Returns
26    ///
27    /// The byte length of the element, either from the node's total length
28    /// or the leaf's text length
29    #[inline]
30    pub fn len(&self) -> usize {
31        match self {
32            GreenTree::Node(n) => n.length,
33            GreenTree::Leaf(t) => t.length,
34        }
35    }
36}
37
38/// A green leaf kind that stores only kind and length.
39///
40/// Green leaves represent individual tokens (keywords, identifiers, literals, etc.)
41/// without storing the actual text content. They only store the kind kind and
42/// length, avoiding text duplication and enabling efficient sharing.
43#[derive(Debug, Clone, Copy, PartialEq, Eq)]
44pub struct GreenLeaf<K: Copy> {
45    /// The kind kind/category (e.g., keyword, identifier, literal)
46    pub kind: K,
47    /// The byte length of the kind text
48    pub length: usize,
49}
50
51impl<K: Copy> GreenLeaf<K> {
52    /// Creates a new green leaf kind.
53    ///
54    /// # Arguments
55    ///
56    /// * `kind` - The kind kind/category
57    /// * `len` - The byte length of the kind text
58    ///
59    /// # Returns
60    ///
61    /// A new [`GreenLeaf`] with the given kind and length
62    #[inline]
63    pub fn new(kind: K, len: usize) -> Self {
64        Self { kind, length: len }
65    }
66}
67
68/// A green node that contains child elements without parent pointers.
69///
70/// Green nodes represent kind tree nodes with their structural information
71/// but without position data or parent references. This design makes them
72/// immutable and shareable across different parse trees.
73#[derive(Debug, Clone)]
74pub struct GreenNode<K: Copy> {
75    /// The node kind/category (e.g., expression, statement, declaration)
76    pub kind: K,
77    /// The child elements of this node
78    pub children: Vec<GreenTree<K>>,
79    /// The total byte length of this node and all its children
80    pub length: usize,
81}
82
83impl<K: Copy> GreenNode<K> {
84    /// Creates a new green node from kind and children.
85    ///
86    /// # Arguments
87    ///
88    /// * `kind` - The node kind/category
89    /// * `children` - The child elements of this node
90    ///
91    /// # Returns
92    ///
93    /// A reference-counted [`GreenNode`] with computed total length
94    pub fn new(kind: K, children: Vec<GreenTree<K>>) -> Arc<Self> {
95        let len = children.iter().map(|c| c.len()).sum();
96        Arc::new(Self { kind, children, length: len })
97    }
98}
99
100impl<K: Copy> GreenNode<K> {
101    /// Replaces a range of child elements with new children.
102    ///
103    /// This method is essential for incremental parsing, allowing efficient
104    /// updates to kind trees by replacing only the changed portions.
105    ///
106    /// # Arguments
107    ///
108    /// * `replace_start` - The starting index of the range to replace (inclusive)
109    /// * `replace_end` - The ending index of the range to replace (exclusive)
110    /// * `new_children` - The new child elements to insert
111    ///
112    /// # Returns
113    ///
114    /// A new [`Arc<GreenNode<K>>`] with the specified children replaced
115    ///
116    /// # Panics
117    ///
118    /// Panics if the indices are out of bounds or if `replace_start > replace_end`
119    pub fn replace_range(&self, replace_start: usize, replace_end: usize, new_children: Vec<GreenTree<K>>) -> Arc<Self> {
120        assert!(replace_start <= replace_end && replace_end <= self.children.len());
121        let mut children = Vec::with_capacity(self.children.len() - (replace_end - replace_start) + new_children.len());
122        children.extend_from_slice(&self.children[..replace_start]);
123        children.extend(new_children.into_iter());
124        children.extend_from_slice(&self.children[replace_end..]);
125        GreenNode::new(self.kind, children)
126    }
127}
oak_core/tree/green_tree.rs

oak_core/tree/
green_tree.rs
