miden_rowan/green/
node.rs

1use alloc::{
2    borrow::{Cow, ToOwned},
3    vec::Vec,
4};
5use core::{
6    borrow::Borrow,
7    fmt,
8    iter::{self, FusedIterator},
9    mem::{self, ManuallyDrop},
10    ops, ptr, slice,
11};
12
13use crate::{
14    GreenToken, NodeOrToken, TextRange, TextSize,
15    arc::{Arc, HeaderSlice, ThinArc},
16    countme::Count,
17    green::{GreenElement, GreenElementRef, SyntaxKind},
18};
19
20#[derive(Debug, Clone, PartialEq, Eq, Hash)]
21pub(super) struct GreenNodeHead {
22    kind: SyntaxKind,
23    text_len: TextSize,
24    _c: Count<GreenNode>,
25}
26
27#[derive(Debug, Clone, PartialEq, Eq, Hash)]
28#[repr(u8)]
29pub(crate) enum GreenChild {
30    Node { rel_offset: TextSize, node: GreenNode },
31    Token { rel_offset: TextSize, token: GreenToken },
32}
33
34type Repr = HeaderSlice<GreenNodeHead, [GreenChild]>;
35type ReprThin = HeaderSlice<GreenNodeHead, [GreenChild; 0]>;
36#[repr(transparent)]
37pub struct GreenNodeData {
38    data: ReprThin,
39}
40
41impl PartialEq for GreenNodeData {
42    fn eq(&self, other: &Self) -> bool {
43        self.header() == other.header() && self.slice() == other.slice()
44    }
45}
46
47/// Internal node in the immutable tree.
48/// It has other nodes and tokens as children.
49#[derive(Clone, PartialEq, Eq, Hash)]
50#[repr(transparent)]
51pub struct GreenNode {
52    ptr: ThinArc<GreenNodeHead, GreenChild>,
53}
54
55impl ToOwned for GreenNodeData {
56    type Owned = GreenNode;
57
58    #[inline]
59    fn to_owned(&self) -> GreenNode {
60        let green = unsafe { GreenNode::from_raw(ptr::NonNull::from(self)) };
61        let green = ManuallyDrop::new(green);
62        GreenNode::clone(&green)
63    }
64}
65
66impl Borrow<GreenNodeData> for GreenNode {
67    #[inline]
68    fn borrow(&self) -> &GreenNodeData {
69        self
70    }
71}
72
73impl From<Cow<'_, GreenNodeData>> for GreenNode {
74    #[inline]
75    fn from(cow: Cow<'_, GreenNodeData>) -> Self {
76        cow.into_owned()
77    }
78}
79
80impl fmt::Debug for GreenNodeData {
81    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
82        f.debug_struct("GreenNode")
83            .field("kind", &self.kind())
84            .field("text_len", &self.text_len())
85            .field("n_children", &self.children().len())
86            .finish()
87    }
88}
89
90impl fmt::Debug for GreenNode {
91    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
92        let data: &GreenNodeData = self;
93        fmt::Debug::fmt(data, f)
94    }
95}
96
97impl fmt::Display for GreenNode {
98    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
99        let data: &GreenNodeData = self;
100        fmt::Display::fmt(data, f)
101    }
102}
103
104impl fmt::Display for GreenNodeData {
105    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
106        for child in self.children() {
107            write!(f, "{}", child)?;
108        }
109        Ok(())
110    }
111}
112
113impl GreenNodeData {
114    #[inline]
115    fn header(&self) -> &GreenNodeHead {
116        &self.data.header
117    }
118
119    #[inline]
120    fn slice(&self) -> &[GreenChild] {
121        self.data.slice()
122    }
123
124    /// Kind of this node.
125    #[inline]
126    pub fn kind(&self) -> SyntaxKind {
127        self.header().kind
128    }
129
130    /// Returns the length of the text covered by this node.
131    #[inline]
132    pub fn text_len(&self) -> TextSize {
133        self.header().text_len
134    }
135
136    /// Children of this node.
137    #[inline]
138    pub fn children(&self) -> Children<'_> {
139        Children { raw: self.slice().iter() }
140    }
141
142    pub(crate) fn child_at_range(
143        &self,
144        rel_range: TextRange,
145    ) -> Option<(usize, TextSize, GreenElementRef<'_>)> {
146        let idx = self
147            .slice()
148            .binary_search_by(|it| {
149                let child_range = it.rel_range();
150                TextRange::ordering(child_range, rel_range)
151            })
152            // XXX: this handles empty ranges
153            .unwrap_or_else(|it| it.saturating_sub(1));
154        let child = &self.slice().get(idx).filter(|it| it.rel_range().contains_range(rel_range))?;
155        Some((idx, child.rel_offset(), child.as_ref()))
156    }
157
158    #[must_use]
159    pub fn replace_child(&self, index: usize, new_child: GreenElement) -> GreenNode {
160        let mut replacement = Some(new_child);
161        let children = self.children().enumerate().map(|(i, child)| {
162            if i == index { replacement.take().unwrap() } else { child.to_owned() }
163        });
164        GreenNode::new(self.kind(), children)
165    }
166    #[must_use]
167    pub fn insert_child(&self, index: usize, new_child: GreenElement) -> GreenNode {
168        // https://github.com/rust-lang/rust/issues/34433
169        self.splice_children(index..index, iter::once(new_child))
170    }
171    #[must_use]
172    pub fn remove_child(&self, index: usize) -> GreenNode {
173        self.splice_children(index..=index, iter::empty())
174    }
175    #[must_use]
176    pub fn splice_children<R, I>(&self, range: R, replace_with: I) -> GreenNode
177    where
178        R: ops::RangeBounds<usize>,
179        I: IntoIterator<Item = GreenElement>,
180    {
181        let mut children: Vec<_> = self.children().map(|it| it.to_owned()).collect();
182        children.splice(range, replace_with);
183        GreenNode::new(self.kind(), children)
184    }
185}
186
187impl ops::Deref for GreenNode {
188    type Target = GreenNodeData;
189
190    #[inline]
191    fn deref(&self) -> &GreenNodeData {
192        let repr: &Repr = &self.ptr;
193        unsafe {
194            let repr: &ReprThin = &*(repr as *const Repr as *const ReprThin);
195            mem::transmute::<&ReprThin, &GreenNodeData>(repr)
196        }
197    }
198}
199
200impl GreenNode {
201    /// Creates new Node.
202    #[inline]
203    pub fn new<I>(kind: SyntaxKind, children: I) -> GreenNode
204    where
205        I: IntoIterator<Item = GreenElement>,
206        I::IntoIter: ExactSizeIterator,
207    {
208        let mut text_len: TextSize = 0.into();
209        let children = children.into_iter().map(|el| {
210            let rel_offset = text_len;
211            text_len += el.text_len();
212            match el {
213                NodeOrToken::Node(node) => GreenChild::Node { rel_offset, node },
214                NodeOrToken::Token(token) => GreenChild::Token { rel_offset, token },
215            }
216        });
217
218        let data = ThinArc::from_header_and_iter(
219            GreenNodeHead { kind, text_len: 0.into(), _c: Count::new() },
220            children,
221        );
222
223        // XXX: fixup `text_len` after construction, because we can't iterate
224        // `children` twice.
225        let data = {
226            let mut data = Arc::from_thin(data);
227            Arc::get_mut(&mut data).unwrap().header.text_len = text_len;
228            Arc::into_thin(data)
229        };
230
231        GreenNode { ptr: data }
232    }
233
234    #[inline]
235    pub(crate) fn into_raw(this: GreenNode) -> ptr::NonNull<GreenNodeData> {
236        let green = ManuallyDrop::new(this);
237        let green: &GreenNodeData = &green;
238        ptr::NonNull::from(green)
239    }
240
241    #[inline]
242    pub(crate) unsafe fn from_raw(ptr: ptr::NonNull<GreenNodeData>) -> GreenNode {
243        unsafe {
244            let arc = Arc::from_raw(&ptr.as_ref().data as *const ReprThin);
245            let arc = mem::transmute::<Arc<ReprThin>, ThinArc<GreenNodeHead, GreenChild>>(arc);
246            GreenNode { ptr: arc }
247        }
248    }
249}
250
251impl GreenChild {
252    #[inline]
253    pub(crate) fn as_ref(&self) -> GreenElementRef<'_> {
254        match self {
255            GreenChild::Node { node, .. } => NodeOrToken::Node(node),
256            GreenChild::Token { token, .. } => NodeOrToken::Token(token),
257        }
258    }
259    #[inline]
260    pub(crate) fn rel_offset(&self) -> TextSize {
261        match self {
262            GreenChild::Node { rel_offset, .. } | GreenChild::Token { rel_offset, .. } => {
263                *rel_offset
264            }
265        }
266    }
267    #[inline]
268    fn rel_range(&self) -> TextRange {
269        let len = self.as_ref().text_len();
270        TextRange::at(self.rel_offset(), len)
271    }
272}
273
274#[derive(Debug, Clone)]
275pub struct Children<'a> {
276    pub(crate) raw: slice::Iter<'a, GreenChild>,
277}
278
279// NB: forward everything stable that iter::Slice specializes as of Rust 1.39.0
280impl ExactSizeIterator for Children<'_> {
281    #[inline(always)]
282    fn len(&self) -> usize {
283        self.raw.len()
284    }
285}
286
287impl<'a> Iterator for Children<'a> {
288    type Item = GreenElementRef<'a>;
289
290    #[inline]
291    fn next(&mut self) -> Option<GreenElementRef<'a>> {
292        self.raw.next().map(GreenChild::as_ref)
293    }
294
295    #[inline]
296    fn size_hint(&self) -> (usize, Option<usize>) {
297        self.raw.size_hint()
298    }
299
300    #[inline]
301    fn count(self) -> usize
302    where
303        Self: Sized,
304    {
305        self.raw.count()
306    }
307
308    #[inline]
309    fn nth(&mut self, n: usize) -> Option<Self::Item> {
310        self.raw.nth(n).map(GreenChild::as_ref)
311    }
312
313    #[inline]
314    fn last(mut self) -> Option<Self::Item>
315    where
316        Self: Sized,
317    {
318        self.next_back()
319    }
320
321    #[inline]
322    fn fold<Acc, Fold>(self, init: Acc, mut f: Fold) -> Acc
323    where
324        Fold: FnMut(Acc, Self::Item) -> Acc,
325    {
326        let mut accum = init;
327        for x in self {
328            accum = f(accum, x);
329        }
330        accum
331    }
332}
333
334impl DoubleEndedIterator for Children<'_> {
335    #[inline]
336    fn next_back(&mut self) -> Option<Self::Item> {
337        self.raw.next_back().map(GreenChild::as_ref)
338    }
339
340    #[inline]
341    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
342        self.raw.nth_back(n).map(GreenChild::as_ref)
343    }
344
345    #[inline]
346    fn rfold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc
347    where
348        Fold: FnMut(Acc, Self::Item) -> Acc,
349    {
350        let mut accum = init;
351        while let Some(x) = self.next_back() {
352            accum = f(accum, x);
353        }
354        accum
355    }
356}
357
358impl FusedIterator for Children<'_> {}
359
360#[cfg(test)]
361mod test {
362
363    #[test]
364    #[cfg(target_pointer_width = "64")]
365    fn check_green_child_size() {
366        use super::GreenChild;
367        use core::mem;
368
369        assert_eq!(mem::size_of::<GreenChild>(), mem::size_of::<usize>() * 2);
370    }
371}
miden_rowan/green/node.rs

miden_rowan/green/
node.rs
