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 mut siblings = self.green_siblings().enumerate();
380 let index = self.index() as usize;
381
382 siblings.nth(index);
383 siblings.find_map(|(index, child)| {
384 child.as_ref().into_node().and_then(|green| {
385 let parent = self.parent_node()?;
386 let offset = parent.offset() + child.rel_offset();
387 Some(SyntaxNode::new_child(green, parent, index as u32, offset))
388 })
389 })
390 }
391 fn prev_sibling(&self) -> Option<SyntaxNode> {
392 let mut rev_siblings = self.green_siblings().enumerate().rev();
393 let index = rev_siblings.len().checked_sub(self.index() as usize + 1)?;
394
395 rev_siblings.nth(index);
396 rev_siblings.find_map(|(index, child)| {
397 child.as_ref().into_node().and_then(|green| {
398 let parent = self.parent_node()?;
399 let offset = parent.offset() + child.rel_offset();
400 Some(SyntaxNode::new_child(green, parent, index as u32, offset))
401 })
402 })
403 }
404
405 fn next_sibling_or_token(&self) -> Option<SyntaxElement> {
406 let mut siblings = self.green_siblings().enumerate();
407 let index = self.index() as usize + 1;
408
409 siblings.nth(index).and_then(|(index, child)| {
410 let parent = self.parent_node()?;
411 let offset = parent.offset() + child.rel_offset();
412 Some(SyntaxElement::new(child.as_ref(), parent, index as u32, offset))
413 })
414 }
415 fn prev_sibling_or_token(&self) -> Option<SyntaxElement> {
416 let mut siblings = self.green_siblings().enumerate();
417 let index = self.index().checked_sub(1)? as usize;
418
419 siblings.nth(index).and_then(|(index, child)| {
420 let parent = self.parent_node()?;
421 let offset = parent.offset() + child.rel_offset();
422 Some(SyntaxElement::new(child.as_ref(), parent, index as u32, offset))
423 })
424 }
425
426 fn detach(&self) {
427 assert!(self.mutable);
428 assert!(self.rc.get() > 0);
429 let parent_ptr = match self.parent.take() {
430 Some(parent) => parent,
431 None => return,
432 };
433
434 unsafe {
435 sll::adjust(self, self.index() + 1, Delta::Sub(1));
436 let parent = parent_ptr.as_ref();
437 sll::unlink(&parent.first, self);
438
439 // Add strong ref to green
440 match self.green().to_owned() {
441 NodeOrToken::Node(it) => {
442 GreenNode::into_raw(it);
443 }
444 NodeOrToken::Token(it) => {
445 GreenToken::into_raw(it);
446 }
447 }
448
449 match parent.green() {
450 NodeOrToken::Node(green) => {
451 let green = green.remove_child(self.index() as usize);
452 parent.respine(green)
453 }
454 NodeOrToken::Token(_) => unreachable!(),
455 }
456
457 if parent.dec_rc() {
458 free(parent_ptr)
459 }
460 }
461 }
462 fn attach_child(&self, index: usize, child: &NodeData) {
463 assert!(self.mutable && child.mutable && child.parent().is_none());
464 assert!(self.rc.get() > 0 && child.rc.get() > 0);
465
466 unsafe {
467 child.index.set(index as u32);
468 child.parent.set(Some(self.into()));
469 self.inc_rc();
470
471 if !self.first.get().is_null() {
472 sll::adjust(&*self.first.get(), index as u32, Delta::Add(1));
473 }
474
475 match sll::link(&self.first, child) {
476 sll::AddToSllResult::AlreadyInSll(_) => {
477 panic!("Child already in sorted linked list")
478 }
479 it => it.add_to_sll(child),
480 }
481
482 match self.green() {
483 NodeOrToken::Node(green) => {
484 // Child is root, so it ownes the green node. Steal it!
485 let child_green = match &child.green {
486 Green::Node { ptr } => GreenNode::from_raw(ptr.get()).into(),
487 Green::Token { ptr } => GreenToken::from_raw(*ptr).into(),
488 };
489
490 let green = green.insert_child(index, child_green);
491 self.respine(green);
492 }
493 NodeOrToken::Token(_) => unreachable!(),
494 }
495 }
496 }
497 unsafe fn respine(&self, mut new_green: GreenNode) {
498 let mut node = self;
499 loop {
500 let old_green = match &node.green {
501 Green::Node { ptr } => ptr.replace(ptr::NonNull::from(&*new_green)),
502 Green::Token { .. } => unreachable!(),
503 };
504 match node.parent() {
505 Some(parent) => match parent.green() {
506 NodeOrToken::Node(parent_green) => {
507 new_green =
508 parent_green.replace_child(node.index() as usize, new_green.into());
509 node = parent;
510 }
511 _ => unreachable!(),
512 },
513 None => {
514 mem::forget(new_green);
515 let _ = GreenNode::from_raw(old_green);
516 break;
517 }
518 }
519 }
520 }
521}
522
523impl SyntaxNode {
524 pub fn new_root(green: GreenNode) -> SyntaxNode {
525 let green = GreenNode::into_raw(green);
526 let green = Green::Node { ptr: Cell::new(green) };
527 SyntaxNode { ptr: NodeData::new(None, 0, 0.into(), green, false) }
528 }
529
530 pub fn new_root_mut(green: GreenNode) -> SyntaxNode {
531 let green = GreenNode::into_raw(green);
532 let green = Green::Node { ptr: Cell::new(green) };
533 SyntaxNode { ptr: NodeData::new(None, 0, 0.into(), green, true) }
534 }
535
536 fn new_child(
537 green: &GreenNodeData,
538 parent: SyntaxNode,
539 index: u32,
540 offset: TextSize,
541 ) -> SyntaxNode {
542 let mutable = parent.data().mutable;
543 let green = Green::Node { ptr: Cell::new(green.into()) };
544 SyntaxNode { ptr: NodeData::new(Some(parent), index, offset, green, mutable) }
545 }
546
547 pub fn clone_for_update(&self) -> SyntaxNode {
548 assert!(!self.data().mutable);
549 match self.parent() {
550 Some(parent) => {
551 let parent = parent.clone_for_update();
552 SyntaxNode::new_child(self.green_ref(), parent, self.data().index(), self.offset())
553 }
554 None => SyntaxNode::new_root_mut(self.green_ref().to_owned()),
555 }
556 }
557
558 pub fn clone_subtree(&self) -> SyntaxNode {
559 SyntaxNode::new_root(self.green().into())
560 }
561
562 #[inline]
563 fn data(&self) -> &NodeData {
564 unsafe { self.ptr.as_ref() }
565 }
566
567 pub fn replace_with(&self, replacement: GreenNode) -> GreenNode {
568 assert_eq!(self.kind(), replacement.kind());
569 match &self.parent() {
570 None => replacement,
571 Some(parent) => {
572 let new_parent = parent
573 .green_ref()
574 .replace_child(self.data().index() as usize, replacement.into());
575 parent.replace_with(new_parent)
576 }
577 }
578 }
579
580 #[inline]
581 pub fn kind(&self) -> SyntaxKind {
582 self.data().kind()
583 }
584
585 #[inline]
586 fn offset(&self) -> TextSize {
587 self.data().offset()
588 }
589
590 #[inline]
591 pub fn text_range(&self) -> TextRange {
592 self.data().text_range()
593 }
594
595 #[inline]
596 pub fn index(&self) -> usize {
597 self.data().index() as usize
598 }
599
600 #[inline]
601 pub fn text(&self) -> SyntaxText {
602 SyntaxText::new(self.clone())
603 }
604
605 #[inline]
606 pub fn green(&self) -> Cow<'_, GreenNodeData> {
607 let green_ref = self.green_ref();
608 match self.data().mutable {
609 false => Cow::Borrowed(green_ref),
610 true => Cow::Owned(green_ref.to_owned()),
611 }
612 }
613 #[inline]
614 fn green_ref(&self) -> &GreenNodeData {
615 self.data().green().into_node().unwrap()
616 }
617
618 #[inline]
619 pub fn parent(&self) -> Option<SyntaxNode> {
620 self.data().parent_node()
621 }
622
623 #[inline]
624 pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode> {
625 iter::successors(Some(self.clone()), SyntaxNode::parent)
626 }
627
628 #[inline]
629 pub fn children(&self) -> SyntaxNodeChildren {
630 SyntaxNodeChildren::new(self.clone())
631 }
632
633 #[inline]
634 pub fn children_with_tokens(&self) -> SyntaxElementChildren {
635 SyntaxElementChildren::new(self.clone())
636 }
637
638 pub fn first_child(&self) -> Option<SyntaxNode> {
639 self.green_ref().children().raw.enumerate().find_map(|(index, child)| {
640 child.as_ref().into_node().map(|green| {
641 SyntaxNode::new_child(
642 green,
643 self.clone(),
644 index as u32,
645 self.offset() + child.rel_offset(),
646 )
647 })
648 })
649 }
650 pub fn last_child(&self) -> Option<SyntaxNode> {
651 self.green_ref().children().raw.enumerate().rev().find_map(|(index, child)| {
652 child.as_ref().into_node().map(|green| {
653 SyntaxNode::new_child(
654 green,
655 self.clone(),
656 index as u32,
657 self.offset() + child.rel_offset(),
658 )
659 })
660 })
661 }
662
663 pub fn first_child_or_token(&self) -> Option<SyntaxElement> {
664 self.green_ref().children().raw.next().map(|child| {
665 SyntaxElement::new(child.as_ref(), self.clone(), 0, self.offset() + child.rel_offset())
666 })
667 }
668 pub fn last_child_or_token(&self) -> Option<SyntaxElement> {
669 self.green_ref().children().raw.enumerate().next_back().map(|(index, child)| {
670 SyntaxElement::new(
671 child.as_ref(),
672 self.clone(),
673 index as u32,
674 self.offset() + child.rel_offset(),
675 )
676 })
677 }
678
679 pub fn next_sibling(&self) -> Option<SyntaxNode> {
680 self.data().next_sibling()
681 }
682 pub fn prev_sibling(&self) -> Option<SyntaxNode> {
683 self.data().prev_sibling()
684 }
685
686 pub fn next_sibling_or_token(&self) -> Option<SyntaxElement> {
687 self.data().next_sibling_or_token()
688 }
689 pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement> {
690 self.data().prev_sibling_or_token()
691 }
692
693 pub fn first_token(&self) -> Option<SyntaxToken> {
694 self.first_child_or_token()?.first_token()
695 }
696 pub fn last_token(&self) -> Option<SyntaxToken> {
697 self.last_child_or_token()?.last_token()
698 }
699
700 #[inline]
701 pub fn siblings(&self, direction: Direction) -> impl Iterator<Item = SyntaxNode> {
702 iter::successors(Some(self.clone()), move |node| match direction {
703 Direction::Next => node.next_sibling(),
704 Direction::Prev => node.prev_sibling(),
705 })
706 }
707
708 #[inline]
709 pub fn siblings_with_tokens(
710 &self,
711 direction: Direction,
712 ) -> impl Iterator<Item = SyntaxElement> {
713 let me: SyntaxElement = self.clone().into();
714 iter::successors(Some(me), move |el| match direction {
715 Direction::Next => el.next_sibling_or_token(),
716 Direction::Prev => el.prev_sibling_or_token(),
717 })
718 }
719
720 #[inline]
721 pub fn descendants(&self) -> impl Iterator<Item = SyntaxNode> {
722 self.preorder().filter_map(|event| match event {
723 WalkEvent::Enter(node) => Some(node),
724 WalkEvent::Leave(_) => None,
725 })
726 }
727
728 #[inline]
729 pub fn descendants_with_tokens(&self) -> impl Iterator<Item = SyntaxElement> {
730 self.preorder_with_tokens().filter_map(|event| match event {
731 WalkEvent::Enter(it) => Some(it),
732 WalkEvent::Leave(_) => None,
733 })
734 }
735
736 #[inline]
737 pub fn preorder(&self) -> Preorder {
738 Preorder::new(self.clone())
739 }
740
741 #[inline]
742 pub fn preorder_with_tokens(&self) -> PreorderWithTokens {
743 PreorderWithTokens::new(self.clone())
744 }
745
746 pub fn token_at_offset(&self, offset: TextSize) -> TokenAtOffset<SyntaxToken> {
747 // TODO: this could be faster if we first drill-down to node, and only
748 // then switch to token search. We should also replace explicit
749 // recursion with a loop.
750 let range = self.text_range();
751 assert!(
752 range.start() <= offset && offset <= range.end(),
753 "Bad offset: range {:?} offset {:?}",
754 range,
755 offset
756 );
757 if range.is_empty() {
758 return TokenAtOffset::None;
759 }
760
761 let mut children = self.children_with_tokens().filter(|child| {
762 let child_range = child.text_range();
763 !child_range.is_empty()
764 && (child_range.start() <= offset && offset <= child_range.end())
765 });
766
767 let left = children.next().unwrap();
768 let right = children.next();
769 assert!(children.next().is_none());
770
771 if let Some(right) = right {
772 match (left.token_at_offset(offset), right.token_at_offset(offset)) {
773 (TokenAtOffset::Single(left), TokenAtOffset::Single(right)) => {
774 TokenAtOffset::Between(left, right)
775 }
776 _ => unreachable!(),
777 }
778 } else {
779 left.token_at_offset(offset)
780 }
781 }
782
783 pub fn covering_element(&self, range: TextRange) -> SyntaxElement {
784 let mut res: SyntaxElement = self.clone().into();
785 loop {
786 assert!(
787 res.text_range().contains_range(range),
788 "Bad range: node range {:?}, range {:?}",
789 res.text_range(),
790 range,
791 );
792 res = match &res {
793 NodeOrToken::Token(_) => return res,
794 NodeOrToken::Node(node) => match node.child_or_token_at_range(range) {
795 Some(it) => it,
796 None => return res,
797 },
798 };
799 }
800 }
801
802 pub fn child_or_token_at_range(&self, range: TextRange) -> Option<SyntaxElement> {
803 let rel_range = range - self.offset();
804 self.green_ref().child_at_range(rel_range).map(|(index, rel_offset, green)| {
805 SyntaxElement::new(green, self.clone(), index as u32, self.offset() + rel_offset)
806 })
807 }
808
809 pub fn splice_children(&self, to_delete: Range<usize>, to_insert: Vec<SyntaxElement>) {
810 assert!(self.data().mutable, "immutable tree: {}", self);
811 for (i, child) in self.children_with_tokens().enumerate() {
812 if to_delete.contains(&i) {
813 child.detach();
814 }
815 }
816 let mut index = to_delete.start;
817 for child in to_insert {
818 self.attach_child(index, child);
819 index += 1;
820 }
821 }
822
823 pub fn detach(&self) {
824 assert!(self.data().mutable, "immutable tree: {}", self);
825 self.data().detach()
826 }
827
828 fn attach_child(&self, index: usize, child: SyntaxElement) {
829 assert!(self.data().mutable, "immutable tree: {}", self);
830 child.detach();
831 let data = match &child {
832 NodeOrToken::Node(it) => it.data(),
833 NodeOrToken::Token(it) => it.data(),
834 };
835 self.data().attach_child(index, data)
836 }
837}
838
839impl SyntaxToken {
840 fn new(
841 green: &GreenTokenData,
842 parent: SyntaxNode,
843 index: u32,
844 offset: TextSize,
845 ) -> SyntaxToken {
846 let mutable = parent.data().mutable;
847 let green = Green::Token { ptr: green.into() };
848 SyntaxToken { ptr: NodeData::new(Some(parent), index, offset, green, mutable) }
849 }
850
851 #[inline]
852 fn data(&self) -> &NodeData {
853 unsafe { self.ptr.as_ref() }
854 }
855
856 pub fn replace_with(&self, replacement: GreenToken) -> GreenNode {
857 assert_eq!(self.kind(), replacement.kind());
858 let parent = self.parent().unwrap();
859 let me: u32 = self.data().index();
860
861 let new_parent = parent.green_ref().replace_child(me as usize, replacement.into());
862 parent.replace_with(new_parent)
863 }
864
865 #[inline]
866 pub fn kind(&self) -> SyntaxKind {
867 self.data().kind()
868 }
869
870 #[inline]
871 pub fn text_range(&self) -> TextRange {
872 self.data().text_range()
873 }
874
875 #[inline]
876 pub fn index(&self) -> usize {
877 self.data().index() as usize
878 }
879
880 #[inline]
881 pub fn text(&self) -> &str {
882 match self.data().green().as_token() {
883 Some(it) => it.text(),
884 None => {
885 debug_assert!(
886 false,
887 "corrupted tree: a node thinks it is a token: {:?}",
888 self.data().green().as_node().unwrap().to_string()
889 );
890 ""
891 }
892 }
893 }
894
895 #[inline]
896 pub fn green(&self) -> &GreenTokenData {
897 self.data().green().into_token().unwrap()
898 }
899
900 #[inline]
901 pub fn parent(&self) -> Option<SyntaxNode> {
902 self.data().parent_node()
903 }
904
905 #[inline]
906 pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode> {
907 std::iter::successors(self.parent(), SyntaxNode::parent)
908 }
909
910 pub fn next_sibling_or_token(&self) -> Option<SyntaxElement> {
911 self.data().next_sibling_or_token()
912 }
913 pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement> {
914 self.data().prev_sibling_or_token()
915 }
916
917 #[inline]
918 pub fn siblings_with_tokens(
919 &self,
920 direction: Direction,
921 ) -> impl Iterator<Item = SyntaxElement> {
922 let me: SyntaxElement = self.clone().into();
923 iter::successors(Some(me), move |el| match direction {
924 Direction::Next => el.next_sibling_or_token(),
925 Direction::Prev => el.prev_sibling_or_token(),
926 })
927 }
928
929 pub fn next_token(&self) -> Option<SyntaxToken> {
930 match self.next_sibling_or_token() {
931 Some(element) => element.first_token(),
932 None => self
933 .ancestors()
934 .find_map(|it| it.next_sibling_or_token())
935 .and_then(|element| element.first_token()),
936 }
937 }
938 pub fn prev_token(&self) -> Option<SyntaxToken> {
939 match self.prev_sibling_or_token() {
940 Some(element) => element.last_token(),
941 None => self
942 .ancestors()
943 .find_map(|it| it.prev_sibling_or_token())
944 .and_then(|element| element.last_token()),
945 }
946 }
947
948 pub fn detach(&self) {
949 assert!(self.data().mutable, "immutable tree: {}", self);
950 self.data().detach()
951 }
952}
953
954impl SyntaxElement {
955 fn new(
956 element: GreenElementRef<'_>,
957 parent: SyntaxNode,
958 index: u32,
959 offset: TextSize,
960 ) -> SyntaxElement {
961 match element {
962 NodeOrToken::Node(node) => {
963 SyntaxNode::new_child(node, parent, index as u32, offset).into()
964 }
965 NodeOrToken::Token(token) => {
966 SyntaxToken::new(token, parent, index as u32, offset).into()
967 }
968 }
969 }
970
971 #[inline]
972 pub fn text_range(&self) -> TextRange {
973 match self {
974 NodeOrToken::Node(it) => it.text_range(),
975 NodeOrToken::Token(it) => it.text_range(),
976 }
977 }
978
979 #[inline]
980 pub fn index(&self) -> usize {
981 match self {
982 NodeOrToken::Node(it) => it.index(),
983 NodeOrToken::Token(it) => it.index(),
984 }
985 }
986
987 #[inline]
988 pub fn kind(&self) -> SyntaxKind {
989 match self {
990 NodeOrToken::Node(it) => it.kind(),
991 NodeOrToken::Token(it) => it.kind(),
992 }
993 }
994
995 #[inline]
996 pub fn parent(&self) -> Option<SyntaxNode> {
997 match self {
998 NodeOrToken::Node(it) => it.parent(),
999 NodeOrToken::Token(it) => it.parent(),
1000 }
1001 }
1002
1003 #[inline]
1004 pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode> {
1005 let first = match self {
1006 NodeOrToken::Node(it) => Some(it.clone()),
1007 NodeOrToken::Token(it) => it.parent(),
1008 };
1009 iter::successors(first, SyntaxNode::parent)
1010 }
1011
1012 pub fn first_token(&self) -> Option<SyntaxToken> {
1013 match self {
1014 NodeOrToken::Node(it) => it.first_token(),
1015 NodeOrToken::Token(it) => Some(it.clone()),
1016 }
1017 }
1018 pub fn last_token(&self) -> Option<SyntaxToken> {
1019 match self {
1020 NodeOrToken::Node(it) => it.last_token(),
1021 NodeOrToken::Token(it) => Some(it.clone()),
1022 }
1023 }
1024
1025 pub fn next_sibling_or_token(&self) -> Option<SyntaxElement> {
1026 match self {
1027 NodeOrToken::Node(it) => it.next_sibling_or_token(),
1028 NodeOrToken::Token(it) => it.next_sibling_or_token(),
1029 }
1030 }
1031 pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement> {
1032 match self {
1033 NodeOrToken::Node(it) => it.prev_sibling_or_token(),
1034 NodeOrToken::Token(it) => it.prev_sibling_or_token(),
1035 }
1036 }
1037
1038 fn token_at_offset(&self, offset: TextSize) -> TokenAtOffset<SyntaxToken> {
1039 assert!(self.text_range().start() <= offset && offset <= self.text_range().end());
1040 match self {
1041 NodeOrToken::Token(token) => TokenAtOffset::Single(token.clone()),
1042 NodeOrToken::Node(node) => node.token_at_offset(offset),
1043 }
1044 }
1045
1046 pub fn detach(&self) {
1047 match self {
1048 NodeOrToken::Node(it) => it.detach(),
1049 NodeOrToken::Token(it) => it.detach(),
1050 }
1051 }
1052}
1053
1054// region: impls
1055
1056// Identity semantics for hash & eq
1057impl PartialEq for SyntaxNode {
1058 #[inline]
1059 fn eq(&self, other: &SyntaxNode) -> bool {
1060 self.data().key() == other.data().key()
1061 }
1062}
1063
1064impl Eq for SyntaxNode {}
1065
1066impl Hash for SyntaxNode {
1067 #[inline]
1068 fn hash<H: Hasher>(&self, state: &mut H) {
1069 self.data().key().hash(state);
1070 }
1071}
1072
1073impl fmt::Debug for SyntaxNode {
1074 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1075 f&mut DebugStruct<'_, '_>.debug_struct("SyntaxNode")
1076 .field("kind", &self.kind())
1077 .field(name:"text_range", &self.text_range())
1078 .finish()
1079 }
1080}
1081
1082impl fmt::Display for SyntaxNode {
1083 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1084 self.preorder_with_tokens()
1085 .filter_map(|event: WalkEvent>| match event {
1086 WalkEvent::Enter(NodeOrToken::Token(token: SyntaxToken)) => Some(token),
1087 _ => None,
1088 })
1089 .try_for_each(|it: SyntaxToken| fmt::Display::fmt(&it, f))
1090 }
1091}
1092
1093// Identity semantics for hash & eq
1094impl PartialEq for SyntaxToken {
1095 #[inline]
1096 fn eq(&self, other: &SyntaxToken) -> bool {
1097 self.data().key() == other.data().key()
1098 }
1099}
1100
1101impl Eq for SyntaxToken {}
1102
1103impl Hash for SyntaxToken {
1104 #[inline]
1105 fn hash<H: Hasher>(&self, state: &mut H) {
1106 self.data().key().hash(state);
1107 }
1108}
1109
1110impl fmt::Display for SyntaxToken {
1111 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1112 fmt::Display::fmt(self.text(), f)
1113 }
1114}
1115
1116impl From<SyntaxNode> for SyntaxElement {
1117 #[inline]
1118 fn from(node: SyntaxNode) -> SyntaxElement {
1119 NodeOrToken::Node(node)
1120 }
1121}
1122
1123impl From<SyntaxToken> for SyntaxElement {
1124 #[inline]
1125 fn from(token: SyntaxToken) -> SyntaxElement {
1126 NodeOrToken::Token(token)
1127 }
1128}
1129
1130// endregion
1131
1132// region: iterators
1133
1134#[derive(Clone, Debug)]
1135pub struct SyntaxNodeChildren {
1136 next: Option<SyntaxNode>,
1137}
1138
1139impl SyntaxNodeChildren {
1140 fn new(parent: SyntaxNode) -> SyntaxNodeChildren {
1141 SyntaxNodeChildren { next: parent.first_child() }
1142 }
1143}
1144
1145impl Iterator for SyntaxNodeChildren {
1146 type Item = SyntaxNode;
1147 fn next(&mut self) -> Option<SyntaxNode> {
1148 self.next.take().map(|next: SyntaxNode| {
1149 self.next = next.next_sibling();
1150 next
1151 })
1152 }
1153}
1154
1155#[derive(Clone, Debug)]
1156pub struct SyntaxElementChildren {
1157 next: Option<SyntaxElement>,
1158}
1159
1160impl SyntaxElementChildren {
1161 fn new(parent: SyntaxNode) -> SyntaxElementChildren {
1162 SyntaxElementChildren { next: parent.first_child_or_token() }
1163 }
1164}
1165
1166impl Iterator for SyntaxElementChildren {
1167 type Item = SyntaxElement;
1168 fn next(&mut self) -> Option<SyntaxElement> {
1169 self.next.take().map(|next: NodeOrToken| {
1170 self.next = next.next_sibling_or_token();
1171 next
1172 })
1173 }
1174}
1175
1176pub struct Preorder {
1177 start: SyntaxNode,
1178 next: Option<WalkEvent<SyntaxNode>>,
1179 skip_subtree: bool,
1180}
1181
1182impl Preorder {
1183 fn new(start: SyntaxNode) -> Preorder {
1184 let next: Option> = Some(WalkEvent::Enter(start.clone()));
1185 Preorder { start, next, skip_subtree: false }
1186 }
1187
1188 pub fn skip_subtree(&mut self) {
1189 self.skip_subtree = true;
1190 }
1191
1192 #[cold]
1193 fn do_skip(&mut self) {
1194 self.next = self.next.take().map(|next: WalkEvent| match next {
1195 WalkEvent::Enter(first_child: SyntaxNode) => WalkEvent::Leave(first_child.parent().unwrap()),
1196 WalkEvent::Leave(parent: SyntaxNode) => WalkEvent::Leave(parent),
1197 })
1198 }
1199}
1200
1201impl Iterator for Preorder {
1202 type Item = WalkEvent<SyntaxNode>;
1203
1204 fn next(&mut self) -> Option<WalkEvent<SyntaxNode>> {
1205 if self.skip_subtree {
1206 self.do_skip();
1207 self.skip_subtree = false;
1208 }
1209 let next = self.next.take();
1210 self.next = next.as_ref().and_then(|next| {
1211 Some(match next {
1212 WalkEvent::Enter(node) => match node.first_child() {
1213 Some(child) => WalkEvent::Enter(child),
1214 None => WalkEvent::Leave(node.clone()),
1215 },
1216 WalkEvent::Leave(node) => {
1217 if node == &self.start {
1218 return None;
1219 }
1220 match node.next_sibling() {
1221 Some(sibling) => WalkEvent::Enter(sibling),
1222 None => WalkEvent::Leave(node.parent()?),
1223 }
1224 }
1225 })
1226 });
1227 next
1228 }
1229}
1230
1231pub struct PreorderWithTokens {
1232 start: SyntaxElement,
1233 next: Option<WalkEvent<SyntaxElement>>,
1234 skip_subtree: bool,
1235}
1236
1237impl PreorderWithTokens {
1238 fn new(start: SyntaxNode) -> PreorderWithTokens {
1239 let next: Option>> = Some(WalkEvent::Enter(start.clone().into()));
1240 PreorderWithTokens { start: start.into(), next, skip_subtree: false }
1241 }
1242
1243 pub fn skip_subtree(&mut self) {
1244 self.skip_subtree = true;
1245 }
1246
1247 #[cold]
1248 fn do_skip(&mut self) {
1249 self.next = self.next.take().map(|next: WalkEvent>| match next {
1250 WalkEvent::Enter(first_child: NodeOrToken) => WalkEvent::Leave(first_child.parent().unwrap().into()),
1251 WalkEvent::Leave(parent: NodeOrToken) => WalkEvent::Leave(parent),
1252 })
1253 }
1254}
1255
1256impl Iterator for PreorderWithTokens {
1257 type Item = WalkEvent<SyntaxElement>;
1258
1259 fn next(&mut self) -> Option<WalkEvent<SyntaxElement>> {
1260 if self.skip_subtree {
1261 self.do_skip();
1262 self.skip_subtree = false;
1263 }
1264 let next = self.next.take();
1265 self.next = next.as_ref().and_then(|next| {
1266 Some(match next {
1267 WalkEvent::Enter(el) => match el {
1268 NodeOrToken::Node(node) => match node.first_child_or_token() {
1269 Some(child) => WalkEvent::Enter(child),
1270 None => WalkEvent::Leave(node.clone().into()),
1271 },
1272 NodeOrToken::Token(token) => WalkEvent::Leave(token.clone().into()),
1273 },
1274 WalkEvent::Leave(el) if el == &self.start => return None,
1275 WalkEvent::Leave(el) => match el.next_sibling_or_token() {
1276 Some(sibling) => WalkEvent::Enter(sibling),
1277 None => WalkEvent::Leave(el.parent()?.into()),
1278 },
1279 })
1280 });
1281 next
1282 }
1283}
1284// endregion
1285