From b5021411a84822cb3f1e3aeffad9550dd15bdeb6 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Sun, 16 Sep 2018 12:54:24 +0300 Subject: rename all things --- crates/ra_syntax/src/algo/mod.rs | 129 +++++++++++++++++++++++++++++++++++++ crates/ra_syntax/src/algo/visit.rs | 110 +++++++++++++++++++++++++++++++ crates/ra_syntax/src/algo/walk.rs | 38 +++++++++++ 3 files changed, 277 insertions(+) create mode 100644 crates/ra_syntax/src/algo/mod.rs create mode 100644 crates/ra_syntax/src/algo/visit.rs create mode 100644 crates/ra_syntax/src/algo/walk.rs (limited to 'crates/ra_syntax/src/algo') diff --git a/crates/ra_syntax/src/algo/mod.rs b/crates/ra_syntax/src/algo/mod.rs new file mode 100644 index 000000000..7287f5bb2 --- /dev/null +++ b/crates/ra_syntax/src/algo/mod.rs @@ -0,0 +1,129 @@ +pub mod walk; +pub mod visit; + +use { + SyntaxNodeRef, TextUnit, TextRange, + text_utils::{contains_offset_nonstrict, is_subrange}, +}; + +pub fn find_leaf_at_offset(node: SyntaxNodeRef, offset: TextUnit) -> LeafAtOffset { + let range = node.range(); + assert!( + contains_offset_nonstrict(range, offset), + "Bad offset: range {:?} offset {:?}", range, offset + ); + if range.is_empty() { + return LeafAtOffset::None; + } + + if node.is_leaf() { + return LeafAtOffset::Single(node); + } + + let mut children = node.children() + .filter(|child| { + let child_range = child.range(); + !child_range.is_empty() && contains_offset_nonstrict(child_range, offset) + }); + + let left = children.next().unwrap(); + let right = children.next(); + assert!(children.next().is_none()); + return if let Some(right) = right { + match (find_leaf_at_offset(left, offset), find_leaf_at_offset(right, offset)) { + (LeafAtOffset::Single(left), LeafAtOffset::Single(right)) => + LeafAtOffset::Between(left, right), + _ => unreachable!() + } + } else { + find_leaf_at_offset(left, offset) + }; +} + +#[derive(Clone, Copy, Debug)] +pub enum LeafAtOffset<'a> { + None, + Single(SyntaxNodeRef<'a>), + Between(SyntaxNodeRef<'a>, SyntaxNodeRef<'a>) +} + +impl<'a> LeafAtOffset<'a> { + pub fn right_biased(self) -> Option> { + match self { + LeafAtOffset::None => None, + LeafAtOffset::Single(node) => Some(node), + LeafAtOffset::Between(_, right) => Some(right) + } + } + + pub fn left_biased(self) -> Option> { + match self { + LeafAtOffset::None => None, + LeafAtOffset::Single(node) => Some(node), + LeafAtOffset::Between(left, _) => Some(left) + } + } +} + +impl<'f> Iterator for LeafAtOffset<'f> { + type Item = SyntaxNodeRef<'f>; + + fn next(&mut self) -> Option> { + match *self { + LeafAtOffset::None => None, + LeafAtOffset::Single(node) => { *self = LeafAtOffset::None; Some(node) } + LeafAtOffset::Between(left, right) => { *self = LeafAtOffset::Single(right); Some(left) } + } + } +} + +pub fn find_covering_node(root: SyntaxNodeRef, range: TextRange) -> SyntaxNodeRef { + assert!(is_subrange(root.range(), range)); + let (left, right) = match ( + find_leaf_at_offset(root, range.start()).right_biased(), + find_leaf_at_offset(root, range.end()).left_biased() + ) { + (Some(l), Some(r)) => (l, r), + _ => return root + }; + + common_ancestor(left, right) +} + +pub fn ancestors<'a>(node: SyntaxNodeRef<'a>) -> impl Iterator> { + generate(Some(node), |&node| node.parent()) +} + +#[derive(Debug)] +pub enum Direction { + Forward, + Backward, +} + +pub fn siblings<'a>( + node: SyntaxNodeRef<'a>, + direction: Direction +) -> impl Iterator> { + generate(Some(node), move |&node| match direction { + Direction::Forward => node.next_sibling(), + Direction::Backward => node.prev_sibling(), + }) +} + +fn common_ancestor<'a>(n1: SyntaxNodeRef<'a>, n2: SyntaxNodeRef<'a>) -> SyntaxNodeRef<'a> { + for p in ancestors(n1) { + if ancestors(n2).any(|a| a == p) { + return p; + } + } + panic!("Can't find common ancestor of {:?} and {:?}", n1, n2) +} + +pub fn generate(seed: Option, step: impl Fn(&T) -> Option) -> impl Iterator { + ::itertools::unfold(seed, move |slot| { + slot.take().map(|curr| { + *slot = step(&curr); + curr + }) + }) +} diff --git a/crates/ra_syntax/src/algo/visit.rs b/crates/ra_syntax/src/algo/visit.rs new file mode 100644 index 000000000..9f1c127c7 --- /dev/null +++ b/crates/ra_syntax/src/algo/visit.rs @@ -0,0 +1,110 @@ +use std::marker::PhantomData; +use {SyntaxNodeRef, AstNode}; + + +pub fn visitor<'a, T>() -> impl Visitor<'a, Output=T> { + EmptyVisitor { ph: PhantomData } +} + +pub fn visitor_ctx<'a, T, C>(ctx: C) -> impl VisitorCtx<'a, Output=T, Ctx=C> { + EmptyVisitorCtx { ph: PhantomData, ctx } +} + +pub trait Visitor<'a>: Sized { + type Output; + fn accept(self, node: SyntaxNodeRef<'a>) -> Option; + fn visit(self, f: F) -> Vis + where N: AstNode<'a>, + F: FnOnce(N) -> Self::Output, + { + Vis { inner: self, f, ph: PhantomData } + } +} + +pub trait VisitorCtx<'a>: Sized { + type Output; + type Ctx; + fn accept(self, node: SyntaxNodeRef<'a>) -> Result; + fn visit(self, f: F) -> VisCtx + where N: AstNode<'a>, + F: FnOnce(N, Self::Ctx) -> Self::Output, + { + VisCtx { inner: self, f, ph: PhantomData } + } +} + +#[derive(Debug)] +struct EmptyVisitor { + ph: PhantomData T> +} + +impl<'a, T> Visitor<'a> for EmptyVisitor { + type Output = T; + + fn accept(self, _node: SyntaxNodeRef<'a>) -> Option { + None + } +} + +#[derive(Debug)] +struct EmptyVisitorCtx { + ctx: C, + ph: PhantomData T>, +} + +impl<'a, T, C> VisitorCtx<'a> for EmptyVisitorCtx { + type Output = T; + type Ctx = C; + + fn accept(self, _node: SyntaxNodeRef<'a>) -> Result { + Err(self.ctx) + } +} + +#[derive(Debug)] +pub struct Vis { + inner: V, + f: F, + ph: PhantomData, +} + +impl<'a, V, N, F> Visitor<'a> for Vis + where + V: Visitor<'a>, + N: AstNode<'a>, + F: FnOnce(N) -> >::Output, +{ + type Output = >::Output; + + fn accept(self, node: SyntaxNodeRef<'a>) -> Option { + let Vis { inner, f, .. } = self; + inner.accept(node).or_else(|| N::cast(node).map(f)) + } +} + +#[derive(Debug)] +pub struct VisCtx { + inner: V, + f: F, + ph: PhantomData, +} + +impl<'a, V, N, F> VisitorCtx<'a> for VisCtx + where + V: VisitorCtx<'a>, + N: AstNode<'a>, + F: FnOnce(N, >::Ctx) -> >::Output, +{ + type Output = >::Output; + type Ctx = >::Ctx; + + fn accept(self, node: SyntaxNodeRef<'a>) -> Result { + let VisCtx { inner, f, .. } = self; + inner.accept(node).or_else(|ctx| + match N::cast(node) { + None => Err(ctx), + Some(node) => Ok(f(node, ctx)) + } + ) + } +} diff --git a/crates/ra_syntax/src/algo/walk.rs b/crates/ra_syntax/src/algo/walk.rs new file mode 100644 index 000000000..536ee705f --- /dev/null +++ b/crates/ra_syntax/src/algo/walk.rs @@ -0,0 +1,38 @@ +use { + SyntaxNodeRef, + algo::generate, +}; + +pub fn preorder<'a>(root: SyntaxNodeRef<'a>) -> impl Iterator> { + walk(root).filter_map(|event| match event { + WalkEvent::Enter(node) => Some(node), + WalkEvent::Exit(_) => None, + }) +} + +#[derive(Debug, Copy, Clone)] +pub enum WalkEvent<'a> { + Enter(SyntaxNodeRef<'a>), + Exit(SyntaxNodeRef<'a>), +} + +pub fn walk<'a>(root: SyntaxNodeRef<'a>) -> impl Iterator> { + generate(Some(WalkEvent::Enter(root)), move |pos| { + let next = match *pos { + WalkEvent::Enter(node) => match node.first_child() { + Some(child) => WalkEvent::Enter(child), + None => WalkEvent::Exit(node), + }, + WalkEvent::Exit(node) => { + if node == root { + return None; + } + match node.next_sibling() { + Some(sibling) => WalkEvent::Enter(sibling), + None => WalkEvent::Exit(node.parent().unwrap()), + } + } + }; + Some(next) + }) +} -- cgit v1.2.3