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