From 7c67612b8a894187fa3b64725531a5459f9211bf Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Fri, 10 Aug 2018 22:33:29 +0300 Subject: organizize --- crates/libsyntax2/src/algo/mod.rs | 123 +++++++++++++++++++++++++++++++ crates/libsyntax2/src/algo/search.rs | 136 +++++++++++++++++++++++++++++++++++ crates/libsyntax2/src/algo/walk.rs | 45 ++++++++++++ 3 files changed, 304 insertions(+) create mode 100644 crates/libsyntax2/src/algo/mod.rs create mode 100644 crates/libsyntax2/src/algo/search.rs create mode 100644 crates/libsyntax2/src/algo/walk.rs (limited to 'crates/libsyntax2/src/algo') diff --git a/crates/libsyntax2/src/algo/mod.rs b/crates/libsyntax2/src/algo/mod.rs new file mode 100644 index 000000000..d2de70fd4 --- /dev/null +++ b/crates/libsyntax2/src/algo/mod.rs @@ -0,0 +1,123 @@ +pub mod walk; + +use {SyntaxNodeRef, TextUnit, TextRange}; + +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) +} + +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 ancestors<'a>(node: SyntaxNodeRef<'a>) -> impl Iterator> { + Ancestors(Some(node)) +} + +#[derive(Debug)] +struct Ancestors<'a>(Option>); + +impl<'a> Iterator for Ancestors<'a> { + type Item = SyntaxNodeRef<'a>; + + fn next(&mut self) -> Option { + self.0.take().map(|n| { + self.0 = n.parent(); + n + }) + } +} + +fn contains_offset_nonstrict(range: TextRange, offset: TextUnit) -> bool { + range.start() <= offset && offset <= range.end() +} + +fn is_subrange(range: TextRange, subrange: TextRange) -> bool { + range.start() <= subrange.start() && subrange.end() <= range.end() +} diff --git a/crates/libsyntax2/src/algo/search.rs b/crates/libsyntax2/src/algo/search.rs new file mode 100644 index 000000000..46404f537 --- /dev/null +++ b/crates/libsyntax2/src/algo/search.rs @@ -0,0 +1,136 @@ +use {Node, NodeType, TextUnit, TextRange}; +use ::visitor::{visitor, process_subtree_bottom_up}; + +pub fn child_of_type(node: Node, ty: NodeType) -> Option { + node.children().find(|n| n.ty() == ty) +} + +pub fn children_of_type<'f>(node: Node<'f>, ty: NodeType) -> Box> + 'f> { + Box::new(node.children().filter(move |n| n.ty() == ty)) +} + +pub fn subtree<'f>(node: Node<'f>) -> Box> + 'f> { + Box::new(node.children().flat_map(subtree).chain(::std::iter::once(node))) +} + +pub fn descendants_of_type<'f>(node: Node<'f>, ty: NodeType) -> Vec> { + process_subtree_bottom_up( + node, + visitor(Vec::new()) + .visit_nodes(&[ty], |node, nodes| nodes.push(node)) + ) +} + +pub fn child_of_type_exn(node: Node, ty: NodeType) -> Node { + child_of_type(node, ty).unwrap_or_else(|| { + panic!("No child of type {:?} for {:?}\ + ----\ + {}\ + ----", ty, node.ty(), node.text()) + }) +} + + +pub fn ancestors(node: Node) -> Ancestors { + Ancestors(Some(node)) +} + +pub struct Ancestors<'f>(Option>); + +impl<'f> Iterator for Ancestors<'f> { + type Item = Node<'f>; + + fn next(&mut self) -> Option { + let current = self.0; + self.0 = current.and_then(|n| n.parent()); + current + } +} + +pub fn is_leaf(node: Node) -> bool { + node.children().next().is_none() && !node.range().is_empty() +} + + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)] +pub enum Direction { + Left, Right +} + +pub fn sibling(node: Node, dir: Direction) -> Option { + let (parent, idx) = child_position(node)?; + let idx = match dir { + Direction::Left => idx.checked_sub(1)?, + Direction::Right => idx + 1, + }; + parent.children().nth(idx) +} + +pub mod ast { + use {Node, AstNode, TextUnit, AstChildren}; + use visitor::{visitor, process_subtree_bottom_up}; + use super::{ancestors, find_leaf_at_offset, LeafAtOffset}; + + pub fn ancestor<'f, T: AstNode<'f>>(node: Node<'f>) -> Option { + ancestors(node) + .filter_map(T::wrap) + .next() + } + + pub fn ancestor_exn<'f, T: AstNode<'f>>(node: Node<'f>) -> T { + ancestor(node).unwrap() + } + + pub fn children_of_type<'f, N: AstNode<'f>>(node: Node<'f>) -> AstChildren { + AstChildren::new(node.children()) + } + + pub fn descendants_of_type<'f, N: AstNode<'f>>(node: Node<'f>) -> Vec { + process_subtree_bottom_up( + node, + visitor(Vec::new()) + .visit::(|node, acc| acc.push(node)) + ) + } + + pub fn node_at_offset<'f, T: AstNode<'f>>(node: Node<'f>, offset: TextUnit) -> Option { + match find_leaf_at_offset(node, offset) { + LeafAtOffset::None => None, + LeafAtOffset::Single(node) => ancestor(node), + LeafAtOffset::Between(left, right) => ancestor(left).or_else(|| ancestor(right)), + } + } +} + +pub mod traversal { + use {Node}; + + pub fn bottom_up<'f, F: FnMut(Node<'f>)>(node: Node<'f>, mut f: F) + { + go(node, &mut f); + + fn go<'f, F: FnMut(Node<'f>)>(node: Node<'f>, f: &mut F) { + for child in node.children() { + go(child, f) + } + f(node); + } + } +} + +fn child_position(child: Node) -> Option<(Node, usize)> { + child.parent() + .map(|parent| { + (parent, parent.children().position(|n| n == child).unwrap()) + }) +} + +fn common_ancestor<'f>(n1: Node<'f>, n2: Node<'f>) -> Node<'f> { + for p in ancestors(n1) { + if ancestors(n2).any(|a| a == p) { + return p; + } + } + panic!("Can't find common ancestor of {:?} and {:?}", n1, n2) +} + diff --git a/crates/libsyntax2/src/algo/walk.rs b/crates/libsyntax2/src/algo/walk.rs new file mode 100644 index 000000000..a50ec2a09 --- /dev/null +++ b/crates/libsyntax2/src/algo/walk.rs @@ -0,0 +1,45 @@ +use SyntaxNodeRef; + +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> { + let mut done = false; + ::itertools::unfold(WalkEvent::Enter(root), move |pos| { + if done { + return None; + } + let res = *pos; + *pos = match *pos { + WalkEvent::Enter(node) => match node.first_child() { + Some(child) => WalkEvent::Enter(child), + None => WalkEvent::Exit(node), + }, + WalkEvent::Exit(node) => { + if node == root { + done = true; + WalkEvent::Exit(node) + } else { + match node.next_sibling() { + Some(sibling) => WalkEvent::Enter(sibling), + None => match node.parent() { + Some(node) => WalkEvent::Exit(node), + None => WalkEvent::Exit(node), + }, + } + } + } + }; + Some(res) + }) +} -- cgit v1.2.3