aboutsummaryrefslogtreecommitdiff
path: root/crates/libsyntax2/src/algo
diff options
context:
space:
mode:
Diffstat (limited to 'crates/libsyntax2/src/algo')
-rw-r--r--crates/libsyntax2/src/algo/mod.rs129
-rw-r--r--crates/libsyntax2/src/algo/visit.rs110
-rw-r--r--crates/libsyntax2/src/algo/walk.rs38
3 files changed, 0 insertions, 277 deletions
diff --git a/crates/libsyntax2/src/algo/mod.rs b/crates/libsyntax2/src/algo/mod.rs
deleted file mode 100644
index 7287f5bb2..000000000
--- a/crates/libsyntax2/src/algo/mod.rs
+++ /dev/null
@@ -1,129 +0,0 @@
1pub mod walk;
2pub mod visit;
3
4use {
5 SyntaxNodeRef, TextUnit, TextRange,
6 text_utils::{contains_offset_nonstrict, is_subrange},
7};
8
9pub fn find_leaf_at_offset(node: SyntaxNodeRef, offset: TextUnit) -> LeafAtOffset {
10 let range = node.range();
11 assert!(
12 contains_offset_nonstrict(range, offset),
13 "Bad offset: range {:?} offset {:?}", range, offset
14 );
15 if range.is_empty() {
16 return LeafAtOffset::None;
17 }
18
19 if node.is_leaf() {
20 return LeafAtOffset::Single(node);
21 }
22
23 let mut children = node.children()
24 .filter(|child| {
25 let child_range = child.range();
26 !child_range.is_empty() && contains_offset_nonstrict(child_range, offset)
27 });
28
29 let left = children.next().unwrap();
30 let right = children.next();
31 assert!(children.next().is_none());
32 return if let Some(right) = right {
33 match (find_leaf_at_offset(left, offset), find_leaf_at_offset(right, offset)) {
34 (LeafAtOffset::Single(left), LeafAtOffset::Single(right)) =>
35 LeafAtOffset::Between(left, right),
36 _ => unreachable!()
37 }
38 } else {
39 find_leaf_at_offset(left, offset)
40 };
41}
42
43#[derive(Clone, Copy, Debug)]
44pub enum LeafAtOffset<'a> {
45 None,
46 Single(SyntaxNodeRef<'a>),
47 Between(SyntaxNodeRef<'a>, SyntaxNodeRef<'a>)
48}
49
50impl<'a> LeafAtOffset<'a> {
51 pub fn right_biased(self) -> Option<SyntaxNodeRef<'a>> {
52 match self {
53 LeafAtOffset::None => None,
54 LeafAtOffset::Single(node) => Some(node),
55 LeafAtOffset::Between(_, right) => Some(right)
56 }
57 }
58
59 pub fn left_biased(self) -> Option<SyntaxNodeRef<'a>> {
60 match self {
61 LeafAtOffset::None => None,
62 LeafAtOffset::Single(node) => Some(node),
63 LeafAtOffset::Between(left, _) => Some(left)
64 }
65 }
66}
67
68impl<'f> Iterator for LeafAtOffset<'f> {
69 type Item = SyntaxNodeRef<'f>;
70
71 fn next(&mut self) -> Option<SyntaxNodeRef<'f>> {
72 match *self {
73 LeafAtOffset::None => None,
74 LeafAtOffset::Single(node) => { *self = LeafAtOffset::None; Some(node) }
75 LeafAtOffset::Between(left, right) => { *self = LeafAtOffset::Single(right); Some(left) }
76 }
77 }
78}
79
80pub fn find_covering_node(root: SyntaxNodeRef, range: TextRange) -> SyntaxNodeRef {
81 assert!(is_subrange(root.range(), range));
82 let (left, right) = match (
83 find_leaf_at_offset(root, range.start()).right_biased(),
84 find_leaf_at_offset(root, range.end()).left_biased()
85 ) {
86 (Some(l), Some(r)) => (l, r),
87 _ => return root
88 };
89
90 common_ancestor(left, right)
91}
92
93pub fn ancestors<'a>(node: SyntaxNodeRef<'a>) -> impl Iterator<Item=SyntaxNodeRef<'a>> {
94 generate(Some(node), |&node| node.parent())
95}
96
97#[derive(Debug)]
98pub enum Direction {
99 Forward,
100 Backward,
101}
102
103pub fn siblings<'a>(
104 node: SyntaxNodeRef<'a>,
105 direction: Direction
106) -> impl Iterator<Item=SyntaxNodeRef<'a>> {
107 generate(Some(node), move |&node| match direction {
108 Direction::Forward => node.next_sibling(),
109 Direction::Backward => node.prev_sibling(),
110 })
111}
112
113fn common_ancestor<'a>(n1: SyntaxNodeRef<'a>, n2: SyntaxNodeRef<'a>) -> SyntaxNodeRef<'a> {
114 for p in ancestors(n1) {
115 if ancestors(n2).any(|a| a == p) {
116 return p;
117 }
118 }
119 panic!("Can't find common ancestor of {:?} and {:?}", n1, n2)
120}
121
122pub fn generate<T>(seed: Option<T>, step: impl Fn(&T) -> Option<T>) -> impl Iterator<Item=T> {
123 ::itertools::unfold(seed, move |slot| {
124 slot.take().map(|curr| {
125 *slot = step(&curr);
126 curr
127 })
128 })
129}
diff --git a/crates/libsyntax2/src/algo/visit.rs b/crates/libsyntax2/src/algo/visit.rs
deleted file mode 100644
index 9f1c127c7..000000000
--- a/crates/libsyntax2/src/algo/visit.rs
+++ /dev/null
@@ -1,110 +0,0 @@
1use std::marker::PhantomData;
2use {SyntaxNodeRef, AstNode};
3
4
5pub fn visitor<'a, T>() -> impl Visitor<'a, Output=T> {
6 EmptyVisitor { ph: PhantomData }
7}
8
9pub fn visitor_ctx<'a, T, C>(ctx: C) -> impl VisitorCtx<'a, Output=T, Ctx=C> {
10 EmptyVisitorCtx { ph: PhantomData, ctx }
11}
12
13pub trait Visitor<'a>: Sized {
14 type Output;
15 fn accept(self, node: SyntaxNodeRef<'a>) -> Option<Self::Output>;
16 fn visit<N, F>(self, f: F) -> Vis<Self, N, F>
17 where N: AstNode<'a>,
18 F: FnOnce(N) -> Self::Output,
19 {
20 Vis { inner: self, f, ph: PhantomData }
21 }
22}
23
24pub trait VisitorCtx<'a>: Sized {
25 type Output;
26 type Ctx;
27 fn accept(self, node: SyntaxNodeRef<'a>) -> Result<Self::Output, Self::Ctx>;
28 fn visit<N, F>(self, f: F) -> VisCtx<Self, N, F>
29 where N: AstNode<'a>,
30 F: FnOnce(N, Self::Ctx) -> Self::Output,
31 {
32 VisCtx { inner: self, f, ph: PhantomData }
33 }
34}
35
36#[derive(Debug)]
37struct EmptyVisitor<T> {
38 ph: PhantomData<fn() -> T>
39}
40
41impl<'a, T> Visitor<'a> for EmptyVisitor<T> {
42 type Output = T;
43
44 fn accept(self, _node: SyntaxNodeRef<'a>) -> Option<T> {
45 None
46 }
47}
48
49#[derive(Debug)]
50struct EmptyVisitorCtx<T, C> {
51 ctx: C,
52 ph: PhantomData<fn() -> T>,
53}
54
55impl<'a, T, C> VisitorCtx<'a> for EmptyVisitorCtx<T, C> {
56 type Output = T;
57 type Ctx = C;
58
59 fn accept(self, _node: SyntaxNodeRef<'a>) -> Result<T, C> {
60 Err(self.ctx)
61 }
62}
63
64#[derive(Debug)]
65pub struct Vis<V, N, F> {
66 inner: V,
67 f: F,
68 ph: PhantomData<fn(N)>,
69}
70
71impl<'a, V, N, F> Visitor<'a> for Vis<V, N, F>
72 where
73 V: Visitor<'a>,
74 N: AstNode<'a>,
75 F: FnOnce(N) -> <V as Visitor<'a>>::Output,
76{
77 type Output = <V as Visitor<'a>>::Output;
78
79 fn accept(self, node: SyntaxNodeRef<'a>) -> Option<Self::Output> {
80 let Vis { inner, f, .. } = self;
81 inner.accept(node).or_else(|| N::cast(node).map(f))
82 }
83}
84
85#[derive(Debug)]
86pub struct VisCtx<V, N, F> {
87 inner: V,
88 f: F,
89 ph: PhantomData<fn(N)>,
90}
91
92impl<'a, V, N, F> VisitorCtx<'a> for VisCtx<V, N, F>
93 where
94 V: VisitorCtx<'a>,
95 N: AstNode<'a>,
96 F: FnOnce(N, <V as VisitorCtx<'a>>::Ctx) -> <V as VisitorCtx<'a>>::Output,
97{
98 type Output = <V as VisitorCtx<'a>>::Output;
99 type Ctx = <V as VisitorCtx<'a>>::Ctx;
100
101 fn accept(self, node: SyntaxNodeRef<'a>) -> Result<Self::Output, Self::Ctx> {
102 let VisCtx { inner, f, .. } = self;
103 inner.accept(node).or_else(|ctx|
104 match N::cast(node) {
105 None => Err(ctx),
106 Some(node) => Ok(f(node, ctx))
107 }
108 )
109 }
110}
diff --git a/crates/libsyntax2/src/algo/walk.rs b/crates/libsyntax2/src/algo/walk.rs
deleted file mode 100644
index 536ee705f..000000000
--- a/crates/libsyntax2/src/algo/walk.rs
+++ /dev/null
@@ -1,38 +0,0 @@
1use {
2 SyntaxNodeRef,
3 algo::generate,
4};
5
6pub fn preorder<'a>(root: SyntaxNodeRef<'a>) -> impl Iterator<Item = SyntaxNodeRef<'a>> {
7 walk(root).filter_map(|event| match event {
8 WalkEvent::Enter(node) => Some(node),
9 WalkEvent::Exit(_) => None,
10 })
11}
12
13#[derive(Debug, Copy, Clone)]
14pub enum WalkEvent<'a> {
15 Enter(SyntaxNodeRef<'a>),
16 Exit(SyntaxNodeRef<'a>),
17}
18
19pub fn walk<'a>(root: SyntaxNodeRef<'a>) -> impl Iterator<Item = WalkEvent<'a>> {
20 generate(Some(WalkEvent::Enter(root)), move |pos| {
21 let next = match *pos {
22 WalkEvent::Enter(node) => match node.first_child() {
23 Some(child) => WalkEvent::Enter(child),
24 None => WalkEvent::Exit(node),
25 },
26 WalkEvent::Exit(node) => {
27 if node == root {
28 return None;
29 }
30 match node.next_sibling() {
31 Some(sibling) => WalkEvent::Enter(sibling),
32 None => WalkEvent::Exit(node.parent().unwrap()),
33 }
34 }
35 };
36 Some(next)
37 })
38}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-16 10:30:41 +0100