From a261a1836ba02a1c091c5165795dc165ca399a87 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Tue, 2 Oct 2018 17:07:12 +0300 Subject: Move to rowan for syntax tree impl --- crates/ra_syntax/src/yellow/builder.rs | 32 ++--- crates/ra_syntax/src/yellow/green.rs | 90 ------------ crates/ra_syntax/src/yellow/mod.rs | 174 ++++++++++++++--------- crates/ra_syntax/src/yellow/red.rs | 113 --------------- crates/ra_syntax/src/yellow/syntax.rs | 215 ----------------------------- crates/ra_syntax/src/yellow/syntax_text.rs | 2 +- 6 files changed, 119 insertions(+), 507 deletions(-) delete mode 100644 crates/ra_syntax/src/yellow/green.rs delete mode 100644 crates/ra_syntax/src/yellow/red.rs delete mode 100644 crates/ra_syntax/src/yellow/syntax.rs (limited to 'crates/ra_syntax/src/yellow') diff --git a/crates/ra_syntax/src/yellow/builder.rs b/crates/ra_syntax/src/yellow/builder.rs index e4ab37899..35dbaec05 100644 --- a/crates/ra_syntax/src/yellow/builder.rs +++ b/crates/ra_syntax/src/yellow/builder.rs @@ -1,15 +1,15 @@ +use rowan::GreenNodeBuilder; use { parser_impl::Sink, - yellow::{GreenNode, SyntaxError}, + yellow::{GreenNode, SyntaxError, RaTypes}, SyntaxKind, TextRange, TextUnit, }; pub(crate) struct GreenBuilder<'a> { text: &'a str, - parents: Vec<(SyntaxKind, usize)>, - children: Vec, pos: TextUnit, errors: Vec, + inner: GreenNodeBuilder, } impl<'a> Sink<'a> for GreenBuilder<'a> { @@ -18,35 +18,25 @@ impl<'a> Sink<'a> for GreenBuilder<'a> { fn new(text: &'a str) -> Self { GreenBuilder { text, - parents: Vec::new(), - children: Vec::new(), pos: 0.into(), errors: Vec::new(), + inner: GreenNodeBuilder::new(), } } fn leaf(&mut self, kind: SyntaxKind, len: TextUnit) { let range = TextRange::offset_len(self.pos, len); self.pos += len; - let text = &self.text[range]; - self.children.push( - GreenNode::new_leaf(kind, text) - ); + let text = self.text[range].into(); + self.inner.leaf(kind, text); } fn start_internal(&mut self, kind: SyntaxKind) { - let len = self.children.len(); - self.parents.push((kind, len)); + self.inner.start_internal(kind) } fn finish_internal(&mut self) { - let (kind, first_child) = self.parents.pop().unwrap(); - let children: Vec<_> = self.children - .drain(first_child..) - .collect(); - self.children.push( - GreenNode::new_branch(kind, children.into_boxed_slice()) - ); + self.inner.finish_internal(); } fn error(&mut self, message: String) { @@ -56,9 +46,7 @@ impl<'a> Sink<'a> for GreenBuilder<'a> { }) } - fn finish(mut self) -> (GreenNode, Vec) { - assert_eq!(self.children.len(), 1); - let root = self.children.pop().unwrap(); - (root, self.errors) + fn finish(self) -> (GreenNode, Vec) { + (self.inner.finish(), self.errors) } } diff --git a/crates/ra_syntax/src/yellow/green.rs b/crates/ra_syntax/src/yellow/green.rs deleted file mode 100644 index 8fb691643..000000000 --- a/crates/ra_syntax/src/yellow/green.rs +++ /dev/null @@ -1,90 +0,0 @@ -use std::sync::Arc; - -use smol_str::SmolStr; - -use {SyntaxKind, TextUnit}; - -#[derive(Clone, Debug)] -pub(crate) enum GreenNode { - Leaf { - kind: SyntaxKind, - text: SmolStr, - }, - Branch(Arc), -} - -impl GreenNode { - pub(crate) fn new_leaf(kind: SyntaxKind, text: &str) -> GreenNode { - GreenNode::Leaf { kind, text: SmolStr::new(text) } - } - - pub(crate) fn new_branch(kind: SyntaxKind, children: Box<[GreenNode]>) -> GreenNode { - GreenNode::Branch(Arc::new(GreenBranch::new(kind, children))) - } - - pub fn kind(&self) -> SyntaxKind { - match self { - GreenNode::Leaf { kind, .. } => *kind, - GreenNode::Branch(b) => b.kind(), - } - } - - pub fn text_len(&self) -> TextUnit { - match self { - GreenNode::Leaf { text, .. } => TextUnit::from(text.len() as u32), - GreenNode::Branch(b) => b.text_len(), - } - } - - pub fn children(&self) -> &[GreenNode] { - match self { - GreenNode::Leaf { .. } => &[], - GreenNode::Branch(b) => b.children(), - } - } - - pub fn leaf_text_ref(&self) -> Option<&SmolStr> { - match self { - GreenNode::Leaf { text, .. } => Some(text), - GreenNode::Branch(_) => None, - } - } -} - -#[derive(Clone, Debug)] -pub(crate) struct GreenBranch { - text_len: TextUnit, - kind: SyntaxKind, - children: Box<[GreenNode]>, -} - -impl GreenBranch { - fn new(kind: SyntaxKind, children: Box<[GreenNode]>) -> GreenBranch { - let text_len = children.iter().map(|x| x.text_len()).sum::(); - GreenBranch { - text_len, - kind, - children, - } - } - - pub fn kind(&self) -> SyntaxKind { - self.kind - } - - pub fn text_len(&self) -> TextUnit { - self.text_len - } - - pub fn children(&self) -> &[GreenNode] { - &*self.children - } -} - -#[test] -fn test_sizes() { - use std::mem::size_of; - println!("GreenBranch = {}", size_of::()); - println!("GreenNode = {}", size_of::()); - println!("SmolStr = {}", size_of::()); -} diff --git a/crates/ra_syntax/src/yellow/mod.rs b/crates/ra_syntax/src/yellow/mod.rs index 0596e702f..c621b1d6a 100644 --- a/crates/ra_syntax/src/yellow/mod.rs +++ b/crates/ra_syntax/src/yellow/mod.rs @@ -1,100 +1,142 @@ mod builder; -mod green; -mod red; -mod syntax; mod syntax_text; use std::{ - sync::Arc, - ptr, -}; -pub use self::syntax::{SyntaxNode, SyntaxNodeRef, SyntaxError, SyntaxNodeChildren}; -pub(crate) use self::{ - builder::GreenBuilder, - green::GreenNode, - red::RedNode, - syntax_text::SyntaxText, + fmt, + hash::{Hash, Hasher}, }; +use rowan::Types; +use {SyntaxKind, TextUnit, TextRange, SmolStr}; +use self::syntax_text::SyntaxText; -#[derive(Debug)] -pub struct SyntaxRoot { - red: RedNode, - pub(crate) errors: Vec, +pub use rowan::{TreeRoot}; +pub(crate) use self::builder::GreenBuilder; + +#[derive(Debug, Clone, Copy)] +pub enum RaTypes {} +impl Types for RaTypes { + type Kind = SyntaxKind; + type RootData = Vec; } -pub trait TreeRoot: Clone + Send + Sync { - fn borrowed(&self) -> RefRoot; - fn owned(&self) -> OwnedRoot; +pub type OwnedRoot = ::rowan::OwnedRoot; +pub type RefRoot<'a> = ::rowan::RefRoot<'a, RaTypes>; + +pub type GreenNode = ::rowan::GreenNode; - #[doc(hidden)] - fn syntax_root(&self) -> &SyntaxRoot; +#[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)] +pub struct SyntaxError { + pub msg: String, + pub offset: TextUnit, } -#[derive(Clone, Debug)] -pub struct OwnedRoot(Arc); -#[derive(Clone, Copy, Debug)] -pub struct RefRoot<'a>(&'a OwnedRoot); // TODO: shared_from_this instead of double indirection -impl<'a> RefRoot<'a> { - fn syntax_root(&self) -> &'a SyntaxRoot { - self.0.syntax_root() +#[derive(Clone, Copy)] +pub struct SyntaxNode = OwnedRoot>( + ::rowan::SyntaxNode, +); +pub type SyntaxNodeRef<'a> = SyntaxNode>; + +impl PartialEq> for SyntaxNode +where + R1: TreeRoot, + R2: TreeRoot, +{ + fn eq(&self, other: &SyntaxNode) -> bool { + self.0 == other.0 } } -impl TreeRoot for OwnedRoot { - fn borrowed(&self) -> RefRoot { - RefRoot(&self) - } - fn owned(&self) -> OwnedRoot { - self.clone() +impl> Eq for SyntaxNode {} +impl> Hash for SyntaxNode { + fn hash(&self, state: &mut H) { + self.0.hash(state) } +} - fn syntax_root(&self) -> &SyntaxRoot { - &*self.0 +impl SyntaxNode { + pub(crate) fn new(green: GreenNode, errors: Vec) -> SyntaxNode { + SyntaxNode(::rowan::SyntaxNode::new(green, errors)) + } +} +impl<'a> SyntaxNode> { + pub fn leaf_text(self) -> Option<&'a SmolStr> { + self.0.leaf_text() } } -impl<'a> TreeRoot for RefRoot<'a> { - fn borrowed(&self) -> RefRoot { - *self +impl> SyntaxNode { + pub(crate) fn root_data(&self) -> &Vec { + self.0.root_data() + } + pub(crate) fn replace_with(&self, replacement: GreenNode) -> GreenNode { + self.0.replace_with(replacement) + } + pub fn borrowed<'a>(&'a self) -> SyntaxNode> { + SyntaxNode(self.0.borrowed()) + } + pub fn owned(&self) -> SyntaxNode { + SyntaxNode(self.0.owned()) + } + pub fn kind(&self) -> SyntaxKind { + self.0.kind() } - fn owned(&self) -> OwnedRoot { - self.0.clone() + pub fn range(&self) -> TextRange { + self.0.range() } - fn syntax_root(&self) -> &SyntaxRoot { - self.0.syntax_root() + pub fn text(&self) -> SyntaxText { + SyntaxText::new(self.borrowed()) + } + pub fn is_leaf(&self) -> bool { + self.0.is_leaf() + } + pub fn parent(&self) -> Option> { + self.0.parent().map(SyntaxNode) + } + pub fn first_child(&self) -> Option> { + self.0.first_child().map(SyntaxNode) + } + pub fn last_child(&self) -> Option> { + self.0.last_child().map(SyntaxNode) + } + pub fn next_sibling(&self) -> Option> { + self.0.next_sibling().map(SyntaxNode) + } + pub fn prev_sibling(&self) -> Option> { + self.0.prev_sibling().map(SyntaxNode) + } + pub fn children(&self) -> SyntaxNodeChildren { + SyntaxNodeChildren(self.0.children()) } } -impl SyntaxRoot { - pub(crate) fn new(green: GreenNode, errors: Vec) -> SyntaxRoot { - SyntaxRoot { - red: RedNode::new_root(green), - errors, +impl> fmt::Debug for SyntaxNode { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + write!(fmt, "{:?}@{:?}", self.kind(), self.range())?; + if has_short_text(self.kind()) { + write!(fmt, " \"{}\"", self.text())?; } + Ok(()) } } -#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)] -pub(crate) struct RedPtr(ptr::NonNull); - -unsafe impl Send for RedPtr {} - -unsafe impl Sync for RedPtr {} +#[derive(Debug)] +pub struct SyntaxNodeChildren>( + ::rowan::SyntaxNodeChildren +); -impl RedPtr { - fn new(red: &RedNode) -> RedPtr { - RedPtr(red.into()) - } +impl> Iterator for SyntaxNodeChildren { + type Item = SyntaxNode; - unsafe fn get<'a>(self, _root: &'a SyntaxRoot) -> &'a RedNode { - &*self.0.as_ptr() + fn next(&mut self) -> Option> { + self.0.next().map(SyntaxNode) } } -#[test] -fn assert_send_sync() { - fn f() {} - f::(); - f::(); - f::(); + +fn has_short_text(kind: SyntaxKind) -> bool { + use SyntaxKind::*; + match kind { + IDENT | LIFETIME | INT_NUMBER | FLOAT_NUMBER => true, + _ => false, + } } diff --git a/crates/ra_syntax/src/yellow/red.rs b/crates/ra_syntax/src/yellow/red.rs deleted file mode 100644 index 84cfe4fba..000000000 --- a/crates/ra_syntax/src/yellow/red.rs +++ /dev/null @@ -1,113 +0,0 @@ -use parking_lot::RwLock; -use {yellow::{GreenNode, RedPtr}, TextUnit}; - -#[derive(Debug)] -pub(crate) struct RedNode { - green: GreenNode, - parent: Option, - children: RwLock>, -} - -#[derive(Debug)] -enum RedChild { - Zigot(TextUnit), - Child(RedNode) -} - -impl RedChild { - fn set(&mut self, node: RedNode) -> &RedNode { - match self { - RedChild::Child(node) => return node, - RedChild::Zigot(_) => { - *self = RedChild::Child(node); - match self { - RedChild::Child(node) => return node, - RedChild::Zigot(_) => unreachable!() - } - } - } - } -} - -#[derive(Debug)] -struct ParentData { - parent: RedPtr, - start_offset: TextUnit, - index_in_parent: usize, -} - -impl RedNode { - pub fn new_root(green: GreenNode) -> RedNode { - RedNode::new(green, None) - } - - fn new_child( - green: GreenNode, - parent: RedPtr, - start_offset: TextUnit, - index_in_parent: usize, - ) -> RedNode { - let parent_data = ParentData { - parent, - start_offset, - index_in_parent, - }; - RedNode::new(green, Some(parent_data)) - } - - fn new(green: GreenNode, parent: Option) -> RedNode { - let mut start_offset = parent.as_ref().map(|it| it.start_offset).unwrap_or(0.into()); - let children = green.children() - .iter() - .map(|child| { - let off = start_offset; - start_offset += child.text_len(); - RedChild::Zigot(off) - }) - .collect::>() - .into_boxed_slice(); - RedNode { - green, - parent, - children: RwLock::new(children), - } - } - - pub(crate) fn green(&self) -> &GreenNode { - &self.green - } - - pub(crate) fn start_offset(&self) -> TextUnit { - match &self.parent { - None => 0.into(), - Some(p) => p.start_offset, - } - } - - pub(crate) fn n_children(&self) -> usize { - self.green.children().len() - } - - pub(crate) fn get_child(&self, idx: usize) -> Option { - if idx >= self.n_children() { - return None; - } - let start_offset = match &self.children.read()[idx] { - RedChild::Child(child) => return Some(RedPtr::new(child)), - RedChild::Zigot(start_offset) => *start_offset, - }; - let green_children = self.green.children(); - let child = - RedNode::new_child(green_children[idx].clone(), RedPtr::new(self), start_offset, idx); - let mut children = self.children.write(); - let child = children[idx].set(child); - Some(RedPtr::new(child)) - } - - pub(crate) fn parent(&self) -> Option { - Some(self.parent.as_ref()?.parent) - } - pub(crate) fn index_in_parent(&self) -> Option { - Some(self.parent.as_ref()?.index_in_parent) - } -} diff --git a/crates/ra_syntax/src/yellow/syntax.rs b/crates/ra_syntax/src/yellow/syntax.rs deleted file mode 100644 index 1d99cab4a..000000000 --- a/crates/ra_syntax/src/yellow/syntax.rs +++ /dev/null @@ -1,215 +0,0 @@ -use std::{ - fmt, sync::Arc, - hash::{Hasher, Hash}, - ops::Range, -}; - -use smol_str::SmolStr; - -use { - yellow::{GreenNode, RedNode, TreeRoot, SyntaxRoot, RedPtr, RefRoot, OwnedRoot, SyntaxText}, - SyntaxKind::{self, *}, - TextRange, TextUnit, -}; - - -#[derive(Clone, Copy)] -pub struct SyntaxNode { - pub(crate) root: R, - // Guaranteed to not dangle, because `root` holds a - // strong reference to red's ancestor - red: RedPtr, -} - -unsafe impl Send for SyntaxNode {} -unsafe impl Sync for SyntaxNode {} - -impl PartialEq> for SyntaxNode { - fn eq(&self, other: &SyntaxNode) -> bool { - self.red == other.red - } -} - -impl Eq for SyntaxNode {} -impl Hash for SyntaxNode { - fn hash(&self, state: &mut H) { - self.red.hash(state) - } -} - -pub type SyntaxNodeRef<'a> = SyntaxNode>; - -#[test] -fn syntax_node_ref_is_copy() { - fn assert_copy(){} - assert_copy::() -} - -#[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)] -pub struct SyntaxError { - pub msg: String, - pub offset: TextUnit, -} - -impl SyntaxNode { - pub(crate) fn new_owned(root: SyntaxRoot) -> Self { - let root = OwnedRoot(Arc::new(root)); - let red = RedPtr::new(&root.syntax_root().red); - SyntaxNode { root, red } - } -} - -impl<'a> SyntaxNode> { - pub(crate) fn leaf_text_ref(self) -> Option<&'a SmolStr> { - let red = unsafe { self.red.get(self.root.syntax_root()) }; - red.green().leaf_text_ref() - } -} - -impl SyntaxNode { - pub fn borrowed<'a>(&'a self) -> SyntaxNodeRef<'a> { - SyntaxNode { - root: self.root.borrowed(), - red: self.red, - } - } - - pub fn owned(&self) -> SyntaxNode { - SyntaxNode { - root: self.root.owned(), - red: self.red, - } - } - - pub fn kind(&self) -> SyntaxKind { - self.red().green().kind() - } - - pub fn range(&self) -> TextRange { - let red = self.red(); - TextRange::offset_len(red.start_offset(), red.green().text_len()) - } - - pub fn text(&self) -> SyntaxText { - SyntaxText::new(self.borrowed()) - } - - pub fn children(&self) -> SyntaxNodeChildren { - SyntaxNodeChildren { - parent: self.clone(), - iter: (0..self.red().n_children()) - } - } - - pub fn parent(&self) -> Option> { - let parent = self.red().parent()?; - Some(SyntaxNode { - root: self.root.clone(), - red: parent, - }) - } - - pub fn first_child(&self) -> Option> { - let red = self.red().get_child(0)?; - Some(SyntaxNode { root: self.root.clone(), red }) - } - - pub fn last_child(&self) -> Option> { - let n = self.red().n_children(); - let n = n.checked_sub(1)?; - let red = self.red().get_child(n)?; - Some(SyntaxNode { root: self.root.clone(), red }) - } - - pub fn next_sibling(&self) -> Option> { - let red = self.red(); - let parent = self.parent()?; - let next_sibling_idx = red.index_in_parent()? + 1; - let sibling_red = parent.red().get_child(next_sibling_idx)?; - Some(SyntaxNode { - root: self.root.clone(), - red: sibling_red, - }) - } - - pub fn prev_sibling(&self) -> Option> { - let red = self.red(); - let parent = self.parent()?; - let prev_sibling_idx = red.index_in_parent()?.checked_sub(1)?; - let sibling_red = parent.red().get_child(prev_sibling_idx)?; - Some(SyntaxNode { - root: self.root.clone(), - red: sibling_red, - }) - } - - pub fn is_leaf(&self) -> bool { - self.first_child().is_none() - } - - pub fn leaf_text(&self) -> Option { - self.borrowed().leaf_text_ref().map(|it| it.clone()) - } - - pub(crate) fn replace_with(&self, green: GreenNode) -> GreenNode { - assert_eq!(self.kind(), green.kind()); - match self.parent() { - None => green, - Some(parent) => { - let children: Vec<_> = parent.children().map(|child| { - if child == *self { - green.clone() - } else { - child.red().green().clone() - } - }).collect(); - let new_parent = GreenNode::new_branch( - parent.kind(), - children.into_boxed_slice(), - ); - parent.replace_with(new_parent) - }, - } - } - - fn red(&self) -> &RedNode { - unsafe { self.red.get(self.root.syntax_root()) } - } -} - -impl fmt::Debug for SyntaxNode { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - write!(fmt, "{:?}@{:?}", self.kind(), self.range())?; - if has_short_text(self.kind()) { - write!(fmt, " \"{}\"", self.text())?; - } - Ok(()) - } -} - -#[derive(Debug)] -pub struct SyntaxNodeChildren { - parent: SyntaxNode, - iter: Range, -} - -impl Iterator for SyntaxNodeChildren { - type Item = SyntaxNode; - - fn next(&mut self) -> Option> { - self.iter.next().map(|i| { - let red = self.parent.red(); - SyntaxNode { - root: self.parent.root.clone(), - red: red.get_child(i).unwrap(), - } - }) - } -} - -fn has_short_text(kind: SyntaxKind) -> bool { - match kind { - IDENT | LIFETIME | INT_NUMBER | FLOAT_NUMBER => true, - _ => false, - } -} diff --git a/crates/ra_syntax/src/yellow/syntax_text.rs b/crates/ra_syntax/src/yellow/syntax_text.rs index 280bedd78..affd7f9c7 100644 --- a/crates/ra_syntax/src/yellow/syntax_text.rs +++ b/crates/ra_syntax/src/yellow/syntax_text.rs @@ -25,7 +25,7 @@ impl<'a> SyntaxText<'a> { let range = self.range; preorder(self.node) .filter_map(move |node| { - let text = node.leaf_text_ref()?; + let text = node.leaf_text()?; let range = intersect(range, node.range())?; let range = range - node.range().start(); Some(&text[range]) -- cgit v1.2.3