1//! Implementation of the cursors -- API for convenient access to syntax trees.
2//!
3//! Functional programmers will recognize that this module implements a zipper
4//! for a purely functional (green) tree.
5//!
6//! A cursor node (`SyntaxNode`) points to a `GreenNode` and a parent
7//! `SyntaxNode`. This allows cursor to provide iteration over both ancestors
8//! and descendants, as well as a cheep access to absolute offset of the node in
9//! file.
10//!
11//! By default `SyntaxNode`s are immutable, but you can get a mutable copy of
12//! the tree by calling `clone_for_update`. Mutation is based on interior
13//! mutability and doesn't need `&mut`. You can have two `SyntaxNode`s pointing
14//! at different parts of the same tree; mutations via the first node will be
15//! reflected in the other.
16
17// Implementation notes:
18//
19// The implementation is utterly and horribly unsafe. This whole module is an
20// unsafety boundary. It is believed that the API here is, in principle, sound,
21// but the implementation might have bugs.
22//
23// The core type is `NodeData` -- a heap-allocated reference counted object,
24// which points to a green node or a green token, and to the parent `NodeData`.
25// Publicly-exposed `SyntaxNode` and `SyntaxToken` own a reference to
26// `NodeData`.
27//
28// `NodeData`s are transient, and are created and destroyed during tree
29// traversals. In general, only currently referenced nodes and their ancestors
30// are alive at any given moment.
31//
32// More specifically, `NodeData`'s ref count is equal to the number of
33// outstanding `SyntaxNode` and `SyntaxToken` plus the number of children with
34// non-zero ref counts. For example, if the user has only a single `SyntaxNode`
35// pointing somewhere in the middle of the tree, then all `NodeData` on the path
36// from that point towards the root have ref count equal to one.
37//
38// `NodeData` which doesn't have a parent (is a root) owns the corresponding
39// green node or token, and is responsible for freeing it.
40//
41// That's mostly it for the immutable subset of the API. Mutation is fun though,
42// you'll like it!
43//
44// Mutability is a run-time property of a tree of `NodeData`. The whole tree is
45// either mutable or immutable. `clone_for_update` clones the whole tree of
46// `NodeData`s, making it mutable (note that the green tree is re-used).
47//
48// If the tree is mutable, then all live `NodeData` are additionally liked to
49// each other via intrusive liked lists. Specifically, there are two pointers to
50// siblings, as well as a pointer to the first child. Note that only live nodes
51// are considered. If the user only has `SyntaxNode`s for the first and last
52// children of some particular node, then their `NodeData` will point at each
53// other.
54//
55// The links are used to propagate mutations across the tree. Specifically, each
56// `NodeData` remembers it's index in parent. When the node is detached from or
57// attached to the tree, we need to adjust the indices of all subsequent
58// siblings. That's what makes the `for c in node.children() { c.detach() }`
59// pattern work despite the apparent iterator invalidation.
60//
61// This code is encapsulated into the sorted linked list (`sll`) module.
62//
63// The actual mutation consist of functionally "mutating" (creating a
64// structurally shared copy) the green node, and then re-spinning the tree. This
65// is a delicate process: `NodeData` point directly to the green nodes, so we
66// must make sure that those nodes don't move. Additionally, during mutation a
67// node might become or might stop being a root, so we must take care to not
68// double free / leak its green node.
69//
70// Because we can change green nodes using only shared references, handing out
71// references into green nodes in the public API would be unsound. We don't do
72// that, but we do use such references internally a lot. Additionally, for
73// tokens the underlying green token actually is immutable, so we can, and do
74// return `&str`.
75//
76// Invariants [must not leak outside of the module]:
77// - Mutability is the property of the whole tree. Intermixing elements that
78// differ in mutability is not allowed.
79// - Mutability property is persistent.
80// - References to the green elements' data are not exposed into public API
81// when the tree is mutable.
82// - TBD
83
84use std::{
85 borrow::Cow,
86 cell::Cell,
87 fmt,
88 hash::{Hash, Hasher},
89 iter,
90 mem::{self, ManuallyDrop},
91 ops::Range,
92 ptr, slice,
93};
94
95use countme::Count;
96
97use crate::{
98 green::{GreenChild, GreenElementRef, GreenNodeData, GreenTokenData, SyntaxKind},
99 sll,
100 utility_types::Delta,
101 Direction, GreenNode, GreenToken, NodeOrToken, SyntaxText, TextRange, TextSize, TokenAtOffset,
102 WalkEvent,
103};
104
105enum Green {
106 Node { ptr: Cell<ptr::NonNull<GreenNodeData>> },
107 Token { ptr: ptr::NonNull<GreenTokenData> },
108}
109
110struct _SyntaxElement;
111
112struct NodeData {
113 _c: Count<_SyntaxElement>,
114
115 rc: Cell<u32>,
116 parent: Cell<Option<ptr::NonNull<NodeData>>>,
117 index: Cell<u32>,
118 green: Green,
119
120 /// Invariant: never changes after NodeData is created.
121 mutable: bool,
122 /// Absolute offset for immutable nodes, unused for mutable nodes.
123 offset: TextSize,
124 // The following links only have meaning when `mutable` is true.
125 first: Cell<*const NodeData>,
126 /// Invariant: never null if mutable.
127 next: Cell<*const NodeData>,
128 /// Invariant: never null if mutable.
129 prev: Cell<*const NodeData>,
130}
131
132unsafe impl sll::Elem for NodeData {
133 fn prev(&self) -> &Cell<*const Self> {
134 &self.prev
135 }
136 fn next(&self) -> &Cell<*const Self> {
137 &self.next
138 }
139 fn key(&self) -> &Cell<u32> {
140 &self.index
141 }
142}
143
144pub type SyntaxElement = NodeOrToken<SyntaxNode, SyntaxToken>;
145
146pub struct SyntaxNode {
147 ptr: ptr::NonNull<NodeData>,
148}
149
150impl Clone for SyntaxNode {
151 #[inline]
152 fn clone(&self) -> Self {
153 self.data().inc_rc();
154 SyntaxNode { ptr: self.ptr }
155 }
156}
157
158impl Drop for SyntaxNode {
159 #[inline]
160 fn drop(&mut self) {
161 if self.data().dec_rc() {
162 unsafe { free(self.ptr) }
163 }
164 }
165}
166
167#[derive(Debug)]
168pub struct SyntaxToken {
169 ptr: ptr::NonNull<NodeData>,
170}
171
172impl Clone for SyntaxToken {
173 #[inline]
174 fn clone(&self) -> Self {
175 self.data().inc_rc();
176 SyntaxToken { ptr: self.ptr }
177 }
178}
179
180impl Drop for SyntaxToken {
181 #[inline]
182 fn drop(&mut self) {
183 if self.data().dec_rc() {
184 unsafe { free(self.ptr) }
185 }
186 }
187}
188
189#[inline(never)]
190unsafe fn free(mut data: ptr::NonNull<NodeData>) {
191 loop {
192 debug_assert_eq!(data.as_ref().rc.get(), 0);
193 debug_assert!(data.as_ref().first.get().is_null());
194 let node = Box::from_raw(data.as_ptr());
195 match node.parent.take() {
196 Some(parent) => {
197 debug_assert!(parent.as_ref().rc.get() > 0);
198 if node.mutable {
199 sll::unlink(&parent.as_ref().first, &*node)
200 }
201 if parent.as_ref().dec_rc() {
202 data = parent;
203 } else {
204 break;
205 }
206 }
207 None => {
208 match &node.green {
209 Green::Node { ptr } => {
210 let _ = GreenNode::from_raw(ptr.get());
211 }
212 Green::Token { ptr } => {
213 let _ = GreenToken::from_raw(*ptr);
214 }
215 }
216 break;
217 }
218 }
219 }
220}
221
222impl NodeData {
223 #[inline]
224 fn new(
225 parent: Option<SyntaxNode>,
226 index: u32,
227 offset: TextSize,
228 green: Green,
229 mutable: bool,
230 ) -> ptr::NonNull<NodeData> {
231 let parent = ManuallyDrop::new(parent);
232 let res = NodeData {
233 _c: Count::new(),
234 rc: Cell::new(1),
235 parent: Cell::new(parent.as_ref().map(|it| it.ptr)),
236 index: Cell::new(index),
237 green,
238
239 mutable,
240 offset,
241 first: Cell::new(ptr::null()),
242 next: Cell::new(ptr::null()),
243 prev: Cell::new(ptr::null()),
244 };
245 unsafe {
246 if mutable {
247 let res_ptr: *const NodeData = &res;
248 match sll::init((*res_ptr).parent().map(|it| &it.first), res_ptr.as_ref().unwrap())
249 {
250 sll::AddToSllResult::AlreadyInSll(node) => {
251 if cfg!(debug_assertions) {
252 assert_eq!((*node).index(), (*res_ptr).index());
253 match ((*node).green(), (*res_ptr).green()) {
254 (NodeOrToken::Node(lhs), NodeOrToken::Node(rhs)) => {
255 assert!(ptr::eq(lhs, rhs))
256 }
257 (NodeOrToken::Token(lhs), NodeOrToken::Token(rhs)) => {
258 assert!(ptr::eq(lhs, rhs))
259 }
260 it => {
261 panic!("node/token confusion: {:?}", it)
262 }
263 }
264 }
265
266 ManuallyDrop::into_inner(parent);
267 let res = node as *mut NodeData;
268 (*res).inc_rc();
269 return ptr::NonNull::new_unchecked(res);
270 }
271 it => {
272 let res = Box::into_raw(Box::new(res));
273 it.add_to_sll(res);
274 return ptr::NonNull::new_unchecked(res);
275 }
276 }
277 }
278 ptr::NonNull::new_unchecked(Box::into_raw(Box::new(res)))
279 }
280 }
281
282 #[inline]
283 fn inc_rc(&self) {
284 let rc = match self.rc.get().checked_add(1) {
285 Some(it) => it,
286 None => std::process::abort(),
287 };
288 self.rc.set(rc)
289 }
290
291 #[inline]
292 fn dec_rc(&self) -> bool {
293 let rc = self.rc.get() - 1;
294 self.rc.set(rc);
295 rc == 0
296 }
297
298 #[inline]
299 fn key(&self) -> (ptr::NonNull<()>, TextSize) {
300 let ptr = match &self.green {
301 Green::Node { ptr } => ptr.get().cast(),
302 Green::Token { ptr } => ptr.cast(),
303 };
304 (ptr, self.offset())
305 }
306
307 #[inline]
308 fn parent_node(&self) -> Option<SyntaxNode> {
309 let parent = self.parent()?;
310 debug_assert!(matches!(parent.green, Green::Node { .. }));
311 parent.inc_rc();
312 Some(SyntaxNode { ptr: ptr::NonNull::from(parent) })
313 }
314
315 #[inline]
316 fn parent(&self) -> Option<&NodeData> {
317 self.parent.get().map(|it| unsafe { &*it.as_ptr() })
318 }
319
320 #[inline]
321 fn green(&self) -> GreenElementRef<'_> {
322 match &self.green {
323 Green::Node { ptr } => GreenElementRef::Node(unsafe { &*ptr.get().as_ptr() }),
324 Green::Token { ptr } => GreenElementRef::Token(unsafe { &*ptr.as_ref() }),
325 }
326 }
327 #[inline]
328 fn green_siblings(&self) -> slice::Iter<GreenChild> {
329 match &self.parent().map(|it| &it.green) {
330 Some(Green::Node { ptr }) => unsafe { &*ptr.get().as_ptr() }.children().raw,
331 Some(Green::Token { .. }) => {
332 debug_assert!(false);
333 [].iter()
334 }
335 None => [].iter(),
336 }
337 }
338 #[inline]
339 fn index(&self) -> u32 {
340 self.index.get()
341 }
342
343 #[inline]
344 fn offset(&self) -> TextSize {
345 if self.mutable {
346 self.offset_mut()
347 } else {
348 self.offset
349 }
350 }
351
352 #[cold]
353 fn offset_mut(&self) -> TextSize {
354 let mut res = TextSize::from(0);
355
356 let mut node = self;
357 while let Some(parent) = node.parent() {
358 let green = parent.green().into_node().unwrap();
359 res += green.children().raw.nth(node.index() as usize).unwrap().rel_offset();
360 node = parent;
361 }
362
363 res
364 }
365
366 #[inline]
367 fn text_range(&self) -> TextRange {
368 let offset = self.offset();
369 let len = self.green().text_len();
370 TextRange::at(offset, len)
371 }
372
373 #[inline]
374 fn kind(&self) -> SyntaxKind {
375 self.green().kind()
376 }
377
378 fn next_sibling(&self) -> Option<SyntaxNode> {
379 let siblings = self.green_siblings().enumerate();
380 let index = self.index() as usize;
381
382 siblings.skip(index + 1).find_map(|(index, child)| {
383 child.as_ref().into_node().and_then(|green| {
384 let parent = self.parent_node()?;
385 let offset = parent.offset() + child.rel_offset();
386 Some(SyntaxNode::new_child(green, parent, index as u32, offset))
387 })
388 })
389 }
390
391 fn next_sibling_by_kind(&self, matcher: &impl Fn(SyntaxKind) -> bool) -> Option<SyntaxNode> {
392 let siblings = self.green_siblings().enumerate();
393 let index = self.index() as usize;
394
395 siblings.skip(index + 1).find_map(|(index, child)| {
396 if !matcher(child.as_ref().kind()) {
397 return None;
398 }
399 child.as_ref().into_node().and_then(|green| {
400 let parent = self.parent_node()?;
401 let offset = parent.offset() + child.rel_offset();
402 Some(SyntaxNode::new_child(green, parent, index as u32, offset))
403 })
404 })
405 }
406
407 fn prev_sibling(&self) -> Option<SyntaxNode> {
408 let rev_siblings = self.green_siblings().enumerate().rev();
409 let index = rev_siblings.len().checked_sub(self.index() as usize)?;
410
411 rev_siblings.skip(index).find_map(|(index, child)| {
412 child.as_ref().into_node().and_then(|green| {
413 let parent = self.parent_node()?;
414 let offset = parent.offset() + child.rel_offset();
415 Some(SyntaxNode::new_child(green, parent, index as u32, offset))
416 })
417 })
418 }
419
420 fn next_sibling_or_token(&self) -> Option<SyntaxElement> {
421 let mut siblings = self.green_siblings().enumerate();
422 let index = self.index() as usize + 1;
423
424 siblings.nth(index).and_then(|(index, child)| {
425 let parent = self.parent_node()?;
426 let offset = parent.offset() + child.rel_offset();
427 Some(SyntaxElement::new(child.as_ref(), parent, index as u32, offset))
428 })
429 }
430
431 fn next_sibling_or_token_by_kind(
432 &self,
433 matcher: &impl Fn(SyntaxKind) -> bool,
434 ) -> Option<SyntaxElement> {
435 let siblings = self.green_siblings().enumerate();
436 let index = self.index() as usize;
437
438 siblings.skip(index + 1).find_map(|(index, child)| {
439 if !matcher(child.as_ref().kind()) {
440 return None;
441 }
442 let parent = self.parent_node()?;
443 let offset = parent.offset() + child.rel_offset();
444 Some(SyntaxElement::new(child.as_ref(), parent, index as u32, offset))
445 })
446 }
447
448 fn prev_sibling_or_token(&self) -> Option<SyntaxElement> {
449 let mut siblings = self.green_siblings().enumerate();
450 let index = self.index().checked_sub(1)? as usize;
451
452 siblings.nth(index).and_then(|(index, child)| {
453 let parent = self.parent_node()?;
454 let offset = parent.offset() + child.rel_offset();
455 Some(SyntaxElement::new(child.as_ref(), parent, index as u32, offset))
456 })
457 }
458
459 fn detach(&self) {
460 assert!(self.mutable);
461 assert!(self.rc.get() > 0);
462 let parent_ptr = match self.parent.take() {
463 Some(parent) => parent,
464 None => return,
465 };
466
467 sll::adjust(self, self.index() + 1, Delta::Sub(1));
468 let parent = unsafe { parent_ptr.as_ref() };
469 sll::unlink(&parent.first, self);
470
471 // Add strong ref to green
472 match self.green().to_owned() {
473 NodeOrToken::Node(it) => {
474 GreenNode::into_raw(it);
475 }
476 NodeOrToken::Token(it) => {
477 GreenToken::into_raw(it);
478 }
479 }
480
481 match parent.green() {
482 NodeOrToken::Node(green) => {
483 let green = green.remove_child(self.index() as usize);
484 unsafe { parent.respine(green) }
485 }
486 NodeOrToken::Token(_) => unreachable!(),
487 }
488
489 if parent.dec_rc() {
490 unsafe { free(parent_ptr) }
491 }
492 }
493 fn attach_child(&self, index: usize, child: &NodeData) {
494 assert!(self.mutable && child.mutable && child.parent().is_none());
495 assert!(self.rc.get() > 0 && child.rc.get() > 0);
496
497 child.index.set(index as u32);
498 child.parent.set(Some(self.into()));
499 self.inc_rc();
500
501 if !self.first.get().is_null() {
502 sll::adjust(unsafe { &*self.first.get() }, index as u32, Delta::Add(1));
503 }
504
505 match sll::link(&self.first, child) {
506 sll::AddToSllResult::AlreadyInSll(_) => {
507 panic!("Child already in sorted linked list")
508 }
509 it => it.add_to_sll(child),
510 }
511
512 match self.green() {
513 NodeOrToken::Node(green) => {
514 // Child is root, so it owns the green node. Steal it!
515 let child_green = match &child.green {
516 Green::Node { ptr } => unsafe { GreenNode::from_raw(ptr.get()).into() },
517 Green::Token { ptr } => unsafe { GreenToken::from_raw(*ptr).into() },
518 };
519
520 let green = green.insert_child(index, child_green);
521 unsafe { self.respine(green) };
522 }
523 NodeOrToken::Token(_) => unreachable!(),
524 }
525 }
526 unsafe fn respine(&self, mut new_green: GreenNode) {
527 let mut node = self;
528 loop {
529 let old_green = match &node.green {
530 Green::Node { ptr } => ptr.replace(ptr::NonNull::from(&*new_green)),
531 Green::Token { .. } => unreachable!(),
532 };
533 match node.parent() {
534 Some(parent) => match parent.green() {
535 NodeOrToken::Node(parent_green) => {
536 new_green =
537 parent_green.replace_child(node.index() as usize, new_green.into());
538 node = parent;
539 }
540 _ => unreachable!(),
541 },
542 None => {
543 mem::forget(new_green);
544 let _ = GreenNode::from_raw(old_green);
545 break;
546 }
547 }
548 }
549 }
550}
551
552impl SyntaxNode {
553 pub fn new_root(green: GreenNode) -> SyntaxNode {
554 let green = GreenNode::into_raw(green);
555 let green = Green::Node { ptr: Cell::new(green) };
556 SyntaxNode { ptr: NodeData::new(None, 0, 0.into(), green, false) }
557 }
558
559 pub fn new_root_mut(green: GreenNode) -> SyntaxNode {
560 let green = GreenNode::into_raw(green);
561 let green = Green::Node { ptr: Cell::new(green) };
562 SyntaxNode { ptr: NodeData::new(None, 0, 0.into(), green, true) }
563 }
564
565 fn new_child(
566 green: &GreenNodeData,
567 parent: SyntaxNode,
568 index: u32,
569 offset: TextSize,
570 ) -> SyntaxNode {
571 let mutable = parent.data().mutable;
572 let green = Green::Node { ptr: Cell::new(green.into()) };
573 SyntaxNode { ptr: NodeData::new(Some(parent), index, offset, green, mutable) }
574 }
575
576 pub fn is_mutable(&self) -> bool {
577 self.data().mutable
578 }
579
580 pub fn clone_for_update(&self) -> SyntaxNode {
581 assert!(!self.data().mutable);
582 match self.parent() {
583 Some(parent) => {
584 let parent = parent.clone_for_update();
585 SyntaxNode::new_child(self.green_ref(), parent, self.data().index(), self.offset())
586 }
587 None => SyntaxNode::new_root_mut(self.green_ref().to_owned()),
588 }
589 }
590
591 pub fn clone_subtree(&self) -> SyntaxNode {
592 SyntaxNode::new_root(self.green().into())
593 }
594
595 #[inline]
596 fn data(&self) -> &NodeData {
597 unsafe { self.ptr.as_ref() }
598 }
599
600 #[inline]
601 fn can_take_ptr(&self) -> bool {
602 self.data().rc.get() == 1 && !self.data().mutable
603 }
604
605 #[inline]
606 fn take_ptr(self) -> ptr::NonNull<NodeData> {
607 assert!(self.can_take_ptr());
608 let ret = self.ptr;
609 // don't change the refcount when self gets dropped
610 std::mem::forget(self);
611 ret
612 }
613
614 pub fn replace_with(&self, replacement: GreenNode) -> GreenNode {
615 assert_eq!(self.kind(), replacement.kind());
616 match &self.parent() {
617 None => replacement,
618 Some(parent) => {
619 let new_parent = parent
620 .green_ref()
621 .replace_child(self.data().index() as usize, replacement.into());
622 parent.replace_with(new_parent)
623 }
624 }
625 }
626
627 #[inline]
628 pub fn kind(&self) -> SyntaxKind {
629 self.data().kind()
630 }
631
632 #[inline]
633 fn offset(&self) -> TextSize {
634 self.data().offset()
635 }
636
637 #[inline]
638 pub fn text_range(&self) -> TextRange {
639 self.data().text_range()
640 }
641
642 #[inline]
643 pub fn index(&self) -> usize {
644 self.data().index() as usize
645 }
646
647 #[inline]
648 pub fn text(&self) -> SyntaxText {
649 SyntaxText::new(self.clone())
650 }
651
652 #[inline]
653 pub fn green(&self) -> Cow<'_, GreenNodeData> {
654 let green_ref = self.green_ref();
655 match self.data().mutable {
656 false => Cow::Borrowed(green_ref),
657 true => Cow::Owned(green_ref.to_owned()),
658 }
659 }
660 #[inline]
661 fn green_ref(&self) -> &GreenNodeData {
662 self.data().green().into_node().unwrap()
663 }
664
665 #[inline]
666 pub fn parent(&self) -> Option<SyntaxNode> {
667 self.data().parent_node()
668 }
669
670 #[inline]
671 pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode> {
672 iter::successors(Some(self.clone()), SyntaxNode::parent)
673 }
674
675 #[inline]
676 pub fn children(&self) -> SyntaxNodeChildren {
677 SyntaxNodeChildren::new(self.clone())
678 }
679
680 #[inline]
681 pub fn children_with_tokens(&self) -> SyntaxElementChildren {
682 SyntaxElementChildren::new(self.clone())
683 }
684
685 pub fn first_child(&self) -> Option<SyntaxNode> {
686 self.green_ref().children().raw.enumerate().find_map(|(index, child)| {
687 child.as_ref().into_node().map(|green| {
688 SyntaxNode::new_child(
689 green,
690 self.clone(),
691 index as u32,
692 self.offset() + child.rel_offset(),
693 )
694 })
695 })
696 }
697
698 pub fn first_child_by_kind(&self, matcher: &impl Fn(SyntaxKind) -> bool) -> Option<SyntaxNode> {
699 self.green_ref().children().raw.enumerate().find_map(|(index, child)| {
700 if !matcher(child.as_ref().kind()) {
701 return None;
702 }
703 child.as_ref().into_node().map(|green| {
704 SyntaxNode::new_child(
705 green,
706 self.clone(),
707 index as u32,
708 self.offset() + child.rel_offset(),
709 )
710 })
711 })
712 }
713
714 pub fn last_child(&self) -> Option<SyntaxNode> {
715 self.green_ref().children().raw.enumerate().rev().find_map(|(index, child)| {
716 child.as_ref().into_node().map(|green| {
717 SyntaxNode::new_child(
718 green,
719 self.clone(),
720 index as u32,
721 self.offset() + child.rel_offset(),
722 )
723 })
724 })
725 }
726
727 pub fn first_child_or_token(&self) -> Option<SyntaxElement> {
728 self.green_ref().children().raw.next().map(|child| {
729 SyntaxElement::new(child.as_ref(), self.clone(), 0, self.offset() + child.rel_offset())
730 })
731 }
732
733 pub fn first_child_or_token_by_kind(
734 &self,
735 matcher: &impl Fn(SyntaxKind) -> bool,
736 ) -> Option<SyntaxElement> {
737 self.green_ref().children().raw.enumerate().find_map(|(index, child)| {
738 if !matcher(child.as_ref().kind()) {
739 return None;
740 }
741 Some(SyntaxElement::new(
742 child.as_ref(),
743 self.clone(),
744 index as u32,
745 self.offset() + child.rel_offset(),
746 ))
747 })
748 }
749
750 pub fn last_child_or_token(&self) -> Option<SyntaxElement> {
751 self.green_ref().children().raw.enumerate().next_back().map(|(index, child)| {
752 SyntaxElement::new(
753 child.as_ref(),
754 self.clone(),
755 index as u32,
756 self.offset() + child.rel_offset(),
757 )
758 })
759 }
760
761 // if possible (i.e. unshared), consume self and advance it to point to the next sibling
762 // this way, we can reuse the previously allocated buffer
763 pub fn to_next_sibling(self) -> Option<SyntaxNode> {
764 if !self.can_take_ptr() {
765 // cannot mutate in-place
766 return self.next_sibling();
767 }
768
769 let mut ptr = self.take_ptr();
770 let data = unsafe { ptr.as_mut() };
771 assert!(data.rc.get() == 1);
772
773 let parent = data.parent_node()?;
774 let parent_offset = parent.offset();
775 let siblings = parent.green_ref().children().raw.enumerate();
776 let index = data.index() as usize;
777
778 siblings
779 .skip(index + 1)
780 .find_map(|(index, child)| {
781 child
782 .as_ref()
783 .into_node()
784 .and_then(|green| Some((green, index as u32, child.rel_offset())))
785 })
786 .and_then(|(green, index, rel_offset)| {
787 data.index.set(index);
788 data.offset = parent_offset + rel_offset;
789 data.green = Green::Node { ptr: Cell::new(green.into()) };
790 Some(SyntaxNode { ptr })
791 })
792 .or_else(|| {
793 data.dec_rc();
794 unsafe { free(ptr) };
795 None
796 })
797 }
798
799 pub fn next_sibling(&self) -> Option<SyntaxNode> {
800 self.data().next_sibling()
801 }
802
803 pub fn next_sibling_by_kind(
804 &self,
805 matcher: &impl Fn(SyntaxKind) -> bool,
806 ) -> Option<SyntaxNode> {
807 self.data().next_sibling_by_kind(matcher)
808 }
809
810 pub fn prev_sibling(&self) -> Option<SyntaxNode> {
811 self.data().prev_sibling()
812 }
813
814 pub fn next_sibling_or_token(&self) -> Option<SyntaxElement> {
815 self.data().next_sibling_or_token()
816 }
817
818 pub fn next_sibling_or_token_by_kind(
819 &self,
820 matcher: &impl Fn(SyntaxKind) -> bool,
821 ) -> Option<SyntaxElement> {
822 self.data().next_sibling_or_token_by_kind(matcher)
823 }
824
825 pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement> {
826 self.data().prev_sibling_or_token()
827 }
828
829 pub fn first_token(&self) -> Option<SyntaxToken> {
830 self.first_child_or_token()?.first_token()
831 }
832 pub fn last_token(&self) -> Option<SyntaxToken> {
833 self.last_child_or_token()?.last_token()
834 }
835
836 #[inline]
837 pub fn siblings(&self, direction: Direction) -> impl Iterator<Item = SyntaxNode> {
838 iter::successors(Some(self.clone()), move |node| match direction {
839 Direction::Next => node.next_sibling(),
840 Direction::Prev => node.prev_sibling(),
841 })
842 }
843
844 #[inline]
845 pub fn siblings_with_tokens(
846 &self,
847 direction: Direction,
848 ) -> impl Iterator<Item = SyntaxElement> {
849 let me: SyntaxElement = self.clone().into();
850 iter::successors(Some(me), move |el| match direction {
851 Direction::Next => el.next_sibling_or_token(),
852 Direction::Prev => el.prev_sibling_or_token(),
853 })
854 }
855
856 #[inline]
857 pub fn descendants(&self) -> impl Iterator<Item = SyntaxNode> {
858 self.preorder().filter_map(|event| match event {
859 WalkEvent::Enter(node) => Some(node),
860 WalkEvent::Leave(_) => None,
861 })
862 }
863
864 #[inline]
865 pub fn descendants_with_tokens(&self) -> impl Iterator<Item = SyntaxElement> {
866 self.preorder_with_tokens().filter_map(|event| match event {
867 WalkEvent::Enter(it) => Some(it),
868 WalkEvent::Leave(_) => None,
869 })
870 }
871
872 #[inline]
873 pub fn preorder(&self) -> Preorder {
874 Preorder::new(self.clone())
875 }
876
877 #[inline]
878 pub fn preorder_with_tokens(&self) -> PreorderWithTokens {
879 PreorderWithTokens::new(self.clone())
880 }
881
882 pub fn token_at_offset(&self, offset: TextSize) -> TokenAtOffset<SyntaxToken> {
883 // TODO: this could be faster if we first drill-down to node, and only
884 // then switch to token search. We should also replace explicit
885 // recursion with a loop.
886 let range = self.text_range();
887 assert!(
888 range.start() <= offset && offset <= range.end(),
889 "Bad offset: range {:?} offset {:?}",
890 range,
891 offset
892 );
893 if range.is_empty() {
894 return TokenAtOffset::None;
895 }
896
897 let mut children = self.children_with_tokens().filter(|child| {
898 let child_range = child.text_range();
899 !child_range.is_empty()
900 && (child_range.start() <= offset && offset <= child_range.end())
901 });
902
903 let left = children.next().unwrap();
904 let right = children.next();
905 assert!(children.next().is_none());
906
907 if let Some(right) = right {
908 match (left.token_at_offset(offset), right.token_at_offset(offset)) {
909 (TokenAtOffset::Single(left), TokenAtOffset::Single(right)) => {
910 TokenAtOffset::Between(left, right)
911 }
912 _ => unreachable!(),
913 }
914 } else {
915 left.token_at_offset(offset)
916 }
917 }
918
919 pub fn covering_element(&self, range: TextRange) -> SyntaxElement {
920 let mut res: SyntaxElement = self.clone().into();
921 loop {
922 assert!(
923 res.text_range().contains_range(range),
924 "Bad range: node range {:?}, range {:?}",
925 res.text_range(),
926 range,
927 );
928 res = match &res {
929 NodeOrToken::Token(_) => return res,
930 NodeOrToken::Node(node) => match node.child_or_token_at_range(range) {
931 Some(it) => it,
932 None => return res,
933 },
934 };
935 }
936 }
937
938 pub fn child_or_token_at_range(&self, range: TextRange) -> Option<SyntaxElement> {
939 let rel_range = range - self.offset();
940 self.green_ref().child_at_range(rel_range).map(|(index, rel_offset, green)| {
941 SyntaxElement::new(green, self.clone(), index as u32, self.offset() + rel_offset)
942 })
943 }
944
945 pub fn splice_children<I: IntoIterator<Item = SyntaxElement>>(
946 &self,
947 to_delete: Range<usize>,
948 to_insert: I,
949 ) {
950 assert!(self.data().mutable, "immutable tree: {}", self);
951 for (i, child) in self.children_with_tokens().enumerate() {
952 if to_delete.contains(&i) {
953 child.detach();
954 }
955 }
956 let mut index = to_delete.start;
957 for child in to_insert {
958 self.attach_child(index, child);
959 index += 1;
960 }
961 }
962
963 pub fn detach(&self) {
964 assert!(self.data().mutable, "immutable tree: {}", self);
965 self.data().detach()
966 }
967
968 fn attach_child(&self, index: usize, child: SyntaxElement) {
969 assert!(self.data().mutable, "immutable tree: {}", self);
970 child.detach();
971 let data = match &child {
972 NodeOrToken::Node(it) => it.data(),
973 NodeOrToken::Token(it) => it.data(),
974 };
975 self.data().attach_child(index, data)
976 }
977}
978
979impl SyntaxToken {
980 fn new(
981 green: &GreenTokenData,
982 parent: SyntaxNode,
983 index: u32,
984 offset: TextSize,
985 ) -> SyntaxToken {
986 let mutable = parent.data().mutable;
987 let green = Green::Token { ptr: green.into() };
988 SyntaxToken { ptr: NodeData::new(Some(parent), index, offset, green, mutable) }
989 }
990
991 #[inline]
992 fn data(&self) -> &NodeData {
993 unsafe { self.ptr.as_ref() }
994 }
995
996 #[inline]
997 fn can_take_ptr(&self) -> bool {
998 self.data().rc.get() == 1 && !self.data().mutable
999 }
1000
1001 #[inline]
1002 fn take_ptr(self) -> ptr::NonNull<NodeData> {
1003 assert!(self.can_take_ptr());
1004 let ret = self.ptr;
1005 // don't change the refcount when self gets dropped
1006 std::mem::forget(self);
1007 ret
1008 }
1009
1010 pub fn replace_with(&self, replacement: GreenToken) -> GreenNode {
1011 assert_eq!(self.kind(), replacement.kind());
1012 let parent = self.parent().unwrap();
1013 let me: u32 = self.data().index();
1014
1015 let new_parent = parent.green_ref().replace_child(me as usize, replacement.into());
1016 parent.replace_with(new_parent)
1017 }
1018
1019 #[inline]
1020 pub fn kind(&self) -> SyntaxKind {
1021 self.data().kind()
1022 }
1023
1024 #[inline]
1025 pub fn text_range(&self) -> TextRange {
1026 self.data().text_range()
1027 }
1028
1029 #[inline]
1030 pub fn index(&self) -> usize {
1031 self.data().index() as usize
1032 }
1033
1034 #[inline]
1035 pub fn text(&self) -> &str {
1036 match self.data().green().as_token() {
1037 Some(it) => it.text(),
1038 None => {
1039 debug_assert!(
1040 false,
1041 "corrupted tree: a node thinks it is a token: {:?}",
1042 self.data().green().as_node().unwrap().to_string()
1043 );
1044 ""
1045 }
1046 }
1047 }
1048
1049 #[inline]
1050 pub fn green(&self) -> &GreenTokenData {
1051 self.data().green().into_token().unwrap()
1052 }
1053
1054 #[inline]
1055 pub fn parent(&self) -> Option<SyntaxNode> {
1056 self.data().parent_node()
1057 }
1058
1059 #[inline]
1060 pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode> {
1061 std::iter::successors(self.parent(), SyntaxNode::parent)
1062 }
1063
1064 pub fn next_sibling_or_token(&self) -> Option<SyntaxElement> {
1065 self.data().next_sibling_or_token()
1066 }
1067
1068 pub fn next_sibling_or_token_by_kind(
1069 &self,
1070 matcher: &impl Fn(SyntaxKind) -> bool,
1071 ) -> Option<SyntaxElement> {
1072 self.data().next_sibling_or_token_by_kind(matcher)
1073 }
1074
1075 pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement> {
1076 self.data().prev_sibling_or_token()
1077 }
1078
1079 #[inline]
1080 pub fn siblings_with_tokens(
1081 &self,
1082 direction: Direction,
1083 ) -> impl Iterator<Item = SyntaxElement> {
1084 let me: SyntaxElement = self.clone().into();
1085 iter::successors(Some(me), move |el| match direction {
1086 Direction::Next => el.next_sibling_or_token(),
1087 Direction::Prev => el.prev_sibling_or_token(),
1088 })
1089 }
1090
1091 pub fn next_token(&self) -> Option<SyntaxToken> {
1092 match self.next_sibling_or_token() {
1093 Some(element) => element.first_token(),
1094 None => self
1095 .ancestors()
1096 .find_map(|it| it.next_sibling_or_token())
1097 .and_then(|element| element.first_token()),
1098 }
1099 }
1100 pub fn prev_token(&self) -> Option<SyntaxToken> {
1101 match self.prev_sibling_or_token() {
1102 Some(element) => element.last_token(),
1103 None => self
1104 .ancestors()
1105 .find_map(|it| it.prev_sibling_or_token())
1106 .and_then(|element| element.last_token()),
1107 }
1108 }
1109
1110 pub fn detach(&self) {
1111 assert!(self.data().mutable, "immutable tree: {}", self);
1112 self.data().detach()
1113 }
1114}
1115
1116impl SyntaxElement {
1117 fn new(
1118 element: GreenElementRef<'_>,
1119 parent: SyntaxNode,
1120 index: u32,
1121 offset: TextSize,
1122 ) -> SyntaxElement {
1123 match element {
1124 NodeOrToken::Node(node) => {
1125 SyntaxNode::new_child(node, parent, index as u32, offset).into()
1126 }
1127 NodeOrToken::Token(token) => {
1128 SyntaxToken::new(token, parent, index as u32, offset).into()
1129 }
1130 }
1131 }
1132
1133 #[inline]
1134 pub fn text_range(&self) -> TextRange {
1135 match self {
1136 NodeOrToken::Node(it) => it.text_range(),
1137 NodeOrToken::Token(it) => it.text_range(),
1138 }
1139 }
1140
1141 #[inline]
1142 pub fn index(&self) -> usize {
1143 match self {
1144 NodeOrToken::Node(it) => it.index(),
1145 NodeOrToken::Token(it) => it.index(),
1146 }
1147 }
1148
1149 #[inline]
1150 pub fn kind(&self) -> SyntaxKind {
1151 match self {
1152 NodeOrToken::Node(it) => it.kind(),
1153 NodeOrToken::Token(it) => it.kind(),
1154 }
1155 }
1156
1157 #[inline]
1158 pub fn parent(&self) -> Option<SyntaxNode> {
1159 match self {
1160 NodeOrToken::Node(it) => it.parent(),
1161 NodeOrToken::Token(it) => it.parent(),
1162 }
1163 }
1164
1165 #[inline]
1166 pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode> {
1167 let first = match self {
1168 NodeOrToken::Node(it) => Some(it.clone()),
1169 NodeOrToken::Token(it) => it.parent(),
1170 };
1171 iter::successors(first, SyntaxNode::parent)
1172 }
1173
1174 pub fn first_token(&self) -> Option<SyntaxToken> {
1175 match self {
1176 NodeOrToken::Node(it) => it.first_token(),
1177 NodeOrToken::Token(it) => Some(it.clone()),
1178 }
1179 }
1180 pub fn last_token(&self) -> Option<SyntaxToken> {
1181 match self {
1182 NodeOrToken::Node(it) => it.last_token(),
1183 NodeOrToken::Token(it) => Some(it.clone()),
1184 }
1185 }
1186
1187 pub fn next_sibling_or_token(&self) -> Option<SyntaxElement> {
1188 match self {
1189 NodeOrToken::Node(it) => it.next_sibling_or_token(),
1190 NodeOrToken::Token(it) => it.next_sibling_or_token(),
1191 }
1192 }
1193
1194 fn can_take_ptr(&self) -> bool {
1195 match self {
1196 NodeOrToken::Node(it) => it.can_take_ptr(),
1197 NodeOrToken::Token(it) => it.can_take_ptr(),
1198 }
1199 }
1200
1201 fn take_ptr(self) -> ptr::NonNull<NodeData> {
1202 match self {
1203 NodeOrToken::Node(it) => it.take_ptr(),
1204 NodeOrToken::Token(it) => it.take_ptr(),
1205 }
1206 }
1207
1208 // if possible (i.e. unshared), consume self and advance it to point to the next sibling
1209 // this way, we can reuse the previously allocated buffer
1210 pub fn to_next_sibling_or_token(self) -> Option<SyntaxElement> {
1211 if !self.can_take_ptr() {
1212 // cannot mutate in-place
1213 return self.next_sibling_or_token();
1214 }
1215
1216 let mut ptr = self.take_ptr();
1217 let data = unsafe { ptr.as_mut() };
1218
1219 let parent = data.parent_node()?;
1220 let parent_offset = parent.offset();
1221 let siblings = parent.green_ref().children().raw.enumerate();
1222 let index = data.index() as usize;
1223
1224 siblings
1225 .skip(index + 1)
1226 .find_map(|(index, green)| {
1227 data.index.set(index as u32);
1228 data.offset = parent_offset + green.rel_offset();
1229
1230 match green.as_ref() {
1231 NodeOrToken::Node(node) => {
1232 data.green = Green::Node { ptr: Cell::new(node.into()) };
1233 Some(SyntaxElement::Node(SyntaxNode { ptr }))
1234 }
1235 NodeOrToken::Token(token) => {
1236 data.green = Green::Token { ptr: token.into() };
1237 Some(SyntaxElement::Token(SyntaxToken { ptr }))
1238 }
1239 }
1240 })
1241 .or_else(|| {
1242 data.dec_rc();
1243 unsafe { free(ptr) };
1244 None
1245 })
1246 }
1247
1248 pub fn next_sibling_or_token_by_kind(
1249 &self,
1250 matcher: &impl Fn(SyntaxKind) -> bool,
1251 ) -> Option<SyntaxElement> {
1252 match self {
1253 NodeOrToken::Node(it) => it.next_sibling_or_token_by_kind(matcher),
1254 NodeOrToken::Token(it) => it.next_sibling_or_token_by_kind(matcher),
1255 }
1256 }
1257
1258 pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement> {
1259 match self {
1260 NodeOrToken::Node(it) => it.prev_sibling_or_token(),
1261 NodeOrToken::Token(it) => it.prev_sibling_or_token(),
1262 }
1263 }
1264
1265 fn token_at_offset(&self, offset: TextSize) -> TokenAtOffset<SyntaxToken> {
1266 assert!(self.text_range().start() <= offset && offset <= self.text_range().end());
1267 match self {
1268 NodeOrToken::Token(token) => TokenAtOffset::Single(token.clone()),
1269 NodeOrToken::Node(node) => node.token_at_offset(offset),
1270 }
1271 }
1272
1273 pub fn detach(&self) {
1274 match self {
1275 NodeOrToken::Node(it) => it.detach(),
1276 NodeOrToken::Token(it) => it.detach(),
1277 }
1278 }
1279}
1280
1281// region: impls
1282
1283// Identity semantics for hash & eq
1284impl PartialEq for SyntaxNode {
1285 #[inline]
1286 fn eq(&self, other: &SyntaxNode) -> bool {
1287 self.data().key() == other.data().key()
1288 }
1289}
1290
1291impl Eq for SyntaxNode {}
1292
1293impl Hash for SyntaxNode {
1294 #[inline]
1295 fn hash<H: Hasher>(&self, state: &mut H) {
1296 self.data().key().hash(state);
1297 }
1298}
1299
1300impl fmt::Debug for SyntaxNode {
1301 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1302 f&mut DebugStruct<'_, '_>.debug_struct("SyntaxNode")
1303 .field("kind", &self.kind())
1304 .field(name:"text_range", &self.text_range())
1305 .finish()
1306 }
1307}
1308
1309impl fmt::Display for SyntaxNode {
1310 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1311 self.preorder_with_tokens()
1312 .filter_map(|event: WalkEvent>| match event {
1313 WalkEvent::Enter(NodeOrToken::Token(token: SyntaxToken)) => Some(token),
1314 _ => None,
1315 })
1316 .try_for_each(|it: SyntaxToken| fmt::Display::fmt(&it, f))
1317 }
1318}
1319
1320// Identity semantics for hash & eq
1321impl PartialEq for SyntaxToken {
1322 #[inline]
1323 fn eq(&self, other: &SyntaxToken) -> bool {
1324 self.data().key() == other.data().key()
1325 }
1326}
1327
1328impl Eq for SyntaxToken {}
1329
1330impl Hash for SyntaxToken {
1331 #[inline]
1332 fn hash<H: Hasher>(&self, state: &mut H) {
1333 self.data().key().hash(state);
1334 }
1335}
1336
1337impl fmt::Display for SyntaxToken {
1338 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1339 fmt::Display::fmt(self.text(), f)
1340 }
1341}
1342
1343impl From<SyntaxNode> for SyntaxElement {
1344 #[inline]
1345 fn from(node: SyntaxNode) -> SyntaxElement {
1346 NodeOrToken::Node(node)
1347 }
1348}
1349
1350impl From<SyntaxToken> for SyntaxElement {
1351 #[inline]
1352 fn from(token: SyntaxToken) -> SyntaxElement {
1353 NodeOrToken::Token(token)
1354 }
1355}
1356
1357// endregion
1358
1359// region: iterators
1360
1361#[derive(Clone, Debug)]
1362pub struct SyntaxNodeChildren {
1363 parent: SyntaxNode,
1364 next: Option<SyntaxNode>,
1365 next_initialized: bool,
1366}
1367
1368impl SyntaxNodeChildren {
1369 fn new(parent: SyntaxNode) -> SyntaxNodeChildren {
1370 SyntaxNodeChildren { parent, next: None, next_initialized: false }
1371 }
1372
1373 pub fn by_kind<F: Fn(SyntaxKind) -> bool>(self, matcher: F) -> SyntaxNodeChildrenByKind<F> {
1374 if !self.next_initialized {
1375 SyntaxNodeChildrenByKind { next: self.parent.first_child_by_kind(&matcher), matcher }
1376 } else {
1377 SyntaxNodeChildrenByKind {
1378 next: self.next.and_then(|node: SyntaxNode| {
1379 if matcher(node.kind()) {
1380 Some(node)
1381 } else {
1382 node.next_sibling_by_kind(&matcher)
1383 }
1384 }),
1385 matcher,
1386 }
1387 }
1388 }
1389}
1390
1391impl Iterator for SyntaxNodeChildren {
1392 type Item = SyntaxNode;
1393 fn next(&mut self) -> Option<SyntaxNode> {
1394 if !self.next_initialized {
1395 self.next = self.parent.first_child();
1396 self.next_initialized = true;
1397 } else {
1398 self.next = self.next.take().and_then(|next: SyntaxNode| next.to_next_sibling());
1399 }
1400
1401 self.next.clone()
1402 }
1403}
1404
1405#[derive(Clone, Debug)]
1406pub struct SyntaxNodeChildrenByKind<F: Fn(SyntaxKind) -> bool> {
1407 next: Option<SyntaxNode>,
1408 matcher: F,
1409}
1410
1411impl<F: Fn(SyntaxKind) -> bool> Iterator for SyntaxNodeChildrenByKind<F> {
1412 type Item = SyntaxNode;
1413 fn next(&mut self) -> Option<SyntaxNode> {
1414 self.next.take().map(|next: SyntaxNode| {
1415 self.next = next.next_sibling_by_kind(&self.matcher);
1416 next
1417 })
1418 }
1419}
1420
1421#[derive(Clone, Debug)]
1422pub struct SyntaxElementChildren {
1423 parent: SyntaxNode,
1424 next: Option<SyntaxElement>,
1425 next_initialized: bool,
1426}
1427
1428impl SyntaxElementChildren {
1429 fn new(parent: SyntaxNode) -> SyntaxElementChildren {
1430 SyntaxElementChildren { parent, next: None, next_initialized: false }
1431 }
1432
1433 pub fn by_kind<F: Fn(SyntaxKind) -> bool>(self, matcher: F) -> SyntaxElementChildrenByKind<F> {
1434 if !self.next_initialized {
1435 SyntaxElementChildrenByKind {
1436 next: self.parent.first_child_or_token_by_kind(&matcher),
1437 matcher,
1438 }
1439 } else {
1440 SyntaxElementChildrenByKind {
1441 next: self.next.and_then(|node| {
1442 if matcher(node.kind()) {
1443 Some(node)
1444 } else {
1445 node.next_sibling_or_token_by_kind(&matcher)
1446 }
1447 }),
1448 matcher,
1449 }
1450 }
1451 }
1452}
1453
1454impl Iterator for SyntaxElementChildren {
1455 type Item = SyntaxElement;
1456 fn next(&mut self) -> Option<SyntaxElement> {
1457 if !self.next_initialized {
1458 self.next = self.parent.first_child_or_token();
1459 self.next_initialized = true;
1460 } else {
1461 self.next = self.next.take().and_then(|next: NodeOrToken| next.to_next_sibling_or_token());
1462 }
1463
1464 self.next.clone()
1465 }
1466}
1467
1468#[derive(Clone, Debug)]
1469pub struct SyntaxElementChildrenByKind<F: Fn(SyntaxKind) -> bool> {
1470 next: Option<SyntaxElement>,
1471 matcher: F,
1472}
1473
1474impl<F: Fn(SyntaxKind) -> bool> Iterator for SyntaxElementChildrenByKind<F> {
1475 type Item = SyntaxElement;
1476 fn next(&mut self) -> Option<SyntaxElement> {
1477 self.next.take().map(|next: NodeOrToken| {
1478 self.next = next.next_sibling_or_token_by_kind(&self.matcher);
1479 next
1480 })
1481 }
1482}
1483
1484pub struct Preorder {
1485 start: SyntaxNode,
1486 next: Option<WalkEvent<SyntaxNode>>,
1487 skip_subtree: bool,
1488}
1489
1490impl Preorder {
1491 fn new(start: SyntaxNode) -> Preorder {
1492 let next: Option> = Some(WalkEvent::Enter(start.clone()));
1493 Preorder { start, next, skip_subtree: false }
1494 }
1495
1496 pub fn skip_subtree(&mut self) {
1497 self.skip_subtree = true;
1498 }
1499
1500 #[cold]
1501 fn do_skip(&mut self) {
1502 self.next = self.next.take().map(|next: WalkEvent| match next {
1503 WalkEvent::Enter(first_child: SyntaxNode) => WalkEvent::Leave(first_child.parent().unwrap()),
1504 WalkEvent::Leave(parent: SyntaxNode) => WalkEvent::Leave(parent),
1505 })
1506 }
1507}
1508
1509impl Iterator for Preorder {
1510 type Item = WalkEvent<SyntaxNode>;
1511
1512 fn next(&mut self) -> Option<WalkEvent<SyntaxNode>> {
1513 if self.skip_subtree {
1514 self.do_skip();
1515 self.skip_subtree = false;
1516 }
1517 let next = self.next.take();
1518 self.next = next.as_ref().and_then(|next| {
1519 Some(match next {
1520 WalkEvent::Enter(node) => match node.first_child() {
1521 Some(child) => WalkEvent::Enter(child),
1522 None => WalkEvent::Leave(node.clone()),
1523 },
1524 WalkEvent::Leave(node) => {
1525 if node == &self.start {
1526 return None;
1527 }
1528 match node.next_sibling() {
1529 Some(sibling) => WalkEvent::Enter(sibling),
1530 None => WalkEvent::Leave(node.parent()?),
1531 }
1532 }
1533 })
1534 });
1535 next
1536 }
1537}
1538
1539pub struct PreorderWithTokens {
1540 start: SyntaxElement,
1541 next: Option<WalkEvent<SyntaxElement>>,
1542 skip_subtree: bool,
1543}
1544
1545impl PreorderWithTokens {
1546 fn new(start: SyntaxNode) -> PreorderWithTokens {
1547 let next: Option>> = Some(WalkEvent::Enter(start.clone().into()));
1548 PreorderWithTokens { start: start.into(), next, skip_subtree: false }
1549 }
1550
1551 pub fn skip_subtree(&mut self) {
1552 self.skip_subtree = true;
1553 }
1554
1555 #[cold]
1556 fn do_skip(&mut self) {
1557 self.next = self.next.take().map(|next: WalkEvent>| match next {
1558 WalkEvent::Enter(first_child: NodeOrToken) => WalkEvent::Leave(first_child.parent().unwrap().into()),
1559 WalkEvent::Leave(parent: NodeOrToken) => WalkEvent::Leave(parent),
1560 })
1561 }
1562}
1563
1564impl Iterator for PreorderWithTokens {
1565 type Item = WalkEvent<SyntaxElement>;
1566
1567 fn next(&mut self) -> Option<WalkEvent<SyntaxElement>> {
1568 if self.skip_subtree {
1569 self.do_skip();
1570 self.skip_subtree = false;
1571 }
1572 let next = self.next.take();
1573 self.next = next.as_ref().and_then(|next| {
1574 Some(match next {
1575 WalkEvent::Enter(el) => match el {
1576 NodeOrToken::Node(node) => match node.first_child_or_token() {
1577 Some(child) => WalkEvent::Enter(child),
1578 None => WalkEvent::Leave(node.clone().into()),
1579 },
1580 NodeOrToken::Token(token) => WalkEvent::Leave(token.clone().into()),
1581 },
1582 WalkEvent::Leave(el) if el == &self.start => return None,
1583 WalkEvent::Leave(el) => match el.next_sibling_or_token() {
1584 Some(sibling) => WalkEvent::Enter(sibling),
1585 None => WalkEvent::Leave(el.parent()?.into()),
1586 },
1587 })
1588 });
1589 next
1590 }
1591}
1592// endregion
1593