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: GreenNode = unsafe { GreenNode::from_raw(ptr:ptr::NonNull::from(self)) };
60 let green: ManuallyDrop = 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&mut DebugStruct<'_, '_>.debug_struct("GreenNode")
82 .field("kind", &self.kind())
83 .field("text_len", &self.text_len())
84 .field(name:"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(self: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(self:data, f)
100 }
101}
102
103impl fmt::Display for GreenNodeData {
104 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
105 for child: NodeOrToken<&GreenNodeData, …> 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>(src: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: &GreenNode, .. } => NodeOrToken::Node(node),
257 GreenChild::Token { token: &GreenToken, .. } => NodeOrToken::Token(token),
258 }
259 }
260 #[inline]
261 pub(crate) fn rel_offset(&self) -> TextSize {
262 match self {
263 GreenChild::Node { rel_offset: &TextSize, .. } | GreenChild::Token { rel_offset: &TextSize, .. } => {
264 *rel_offset
265 }
266 }
267 }
268 #[inline]
269 fn rel_range(&self) -> TextRange {
270 let len: TextSize = 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: Acc = init;
352 while let Some(x: NodeOrToken<&'a GreenNodeData, …>) = self.next_back() {
353 accum = f(accum, x);
354 }
355 accum
356 }
357}
358
359impl FusedIterator for Children<'_> {}
360