rowan/green/
node.rs

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

rowan/green/
node.rs
