6 files changed, 704 insertions, 0 deletions

diff --git a/crates/ra_syntax/src/yellow/builder.rs b/crates/ra_syntax/src/yellow/builder.rs
new file mode 100644
index 000000000..e4ab37899
--- /dev/null
+++ b/crates/ra_syntax/src/yellow/builder.rs
@@ -0,0 +1,64 @@
+use {
+    parser_impl::Sink,
+    yellow::{GreenNode, SyntaxError},
+    SyntaxKind, TextRange, TextUnit,
+};
+
+pub(crate) struct GreenBuilder<'a> {
+    text: &'a str,
+    parents: Vec<(SyntaxKind, usize)>,
+    children: Vec<GreenNode>,
+    pos: TextUnit,
+    errors: Vec<SyntaxError>,
+}
+
+impl<'a> Sink<'a> for GreenBuilder<'a> {
+    type Tree = (GreenNode, Vec<SyntaxError>);
+
+    fn new(text: &'a str) -> Self {
+        GreenBuilder {
+            text,
+            parents: Vec::new(),
+            children: Vec::new(),
+            pos: 0.into(),
+            errors: Vec::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)
+        );
+    }
+
+    fn start_internal(&mut self, kind: SyntaxKind) {
+        let len = self.children.len();
+        self.parents.push((kind, len));
+    }
+
+    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())
+        );
+    }
+
+    fn error(&mut self, message: String) {
+        self.errors.push(SyntaxError {
+            msg: message,
+            offset: self.pos,
+        })
+    }
+
+    fn finish(mut self) -> (GreenNode, Vec<SyntaxError>) {
+        assert_eq!(self.children.len(), 1);
+        let root = self.children.pop().unwrap();
+        (root, self.errors)
+    }
+}
diff --git a/crates/ra_syntax/src/yellow/green.rs b/crates/ra_syntax/src/yellow/green.rs
new file mode 100644
index 000000000..8fb691643
--- /dev/null
+++ b/crates/ra_syntax/src/yellow/green.rs
@@ -0,0 +1,90 @@
+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<GreenBranch>),
+}
+
+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::<TextUnit>();
+        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::<GreenBranch>());
+    println!("GreenNode   = {}", size_of::<GreenNode>());
+    println!("SmolStr     = {}", size_of::<SmolStr>());
+}
diff --git a/crates/ra_syntax/src/yellow/mod.rs b/crates/ra_syntax/src/yellow/mod.rs
new file mode 100644
index 000000000..0596e702f
--- /dev/null
+++ b/crates/ra_syntax/src/yellow/mod.rs
@@ -0,0 +1,100 @@
+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,
+};
+
+#[derive(Debug)]
+pub struct SyntaxRoot {
+    red: RedNode,
+    pub(crate) errors: Vec<SyntaxError>,
+}
+
+pub trait TreeRoot: Clone + Send + Sync {
+    fn borrowed(&self) -> RefRoot;
+    fn owned(&self) -> OwnedRoot;
+
+    #[doc(hidden)]
+    fn syntax_root(&self) -> &SyntaxRoot;
+}
+#[derive(Clone, Debug)]
+pub struct OwnedRoot(Arc<SyntaxRoot>);
+#[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()
+    }
+}
+
+impl TreeRoot for OwnedRoot {
+    fn borrowed(&self) -> RefRoot {
+        RefRoot(&self)
+    }
+    fn owned(&self) -> OwnedRoot {
+        self.clone()
+    }
+
+    fn syntax_root(&self) -> &SyntaxRoot {
+        &*self.0
+    }
+}
+
+impl<'a> TreeRoot for RefRoot<'a> {
+    fn borrowed(&self) -> RefRoot {
+        *self
+    }
+    fn owned(&self) -> OwnedRoot {
+        self.0.clone()
+    }
+    fn syntax_root(&self) -> &SyntaxRoot {
+        self.0.syntax_root()
+    }
+}
+
+impl SyntaxRoot {
+    pub(crate) fn new(green: GreenNode, errors: Vec<SyntaxError>) -> SyntaxRoot {
+        SyntaxRoot {
+            red: RedNode::new_root(green),
+            errors,
+        }
+    }
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
+pub(crate) struct RedPtr(ptr::NonNull<RedNode>);
+
+unsafe impl Send for RedPtr {}
+
+unsafe impl Sync for RedPtr {}
+
+impl RedPtr {
+    fn new(red: &RedNode) -> RedPtr {
+        RedPtr(red.into())
+    }
+
+    unsafe fn get<'a>(self, _root: &'a SyntaxRoot) -> &'a RedNode {
+        &*self.0.as_ptr()
+    }
+}
+
+#[test]
+fn assert_send_sync() {
+    fn f<T: Send + Sync>() {}
+    f::<GreenNode>();
+    f::<RedNode>();
+    f::<SyntaxNode>();
+}
diff --git a/crates/ra_syntax/src/yellow/red.rs b/crates/ra_syntax/src/yellow/red.rs
new file mode 100644
index 000000000..84cfe4fba
--- /dev/null
+++ b/crates/ra_syntax/src/yellow/red.rs
@@ -0,0 +1,113 @@
+use parking_lot::RwLock;
+use {yellow::{GreenNode, RedPtr}, TextUnit};
+
+#[derive(Debug)]
+pub(crate) struct RedNode {
+    green: GreenNode,
+    parent: Option<ParentData>,
+    children: RwLock<Box<[RedChild]>>,
+}
+
+#[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<ParentData>) -> 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::<Vec<_>>()
+            .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<RedPtr> {
+        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<RedPtr> {
+        Some(self.parent.as_ref()?.parent)
+    }
+    pub(crate) fn index_in_parent(&self) -> Option<usize> {
+        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
new file mode 100644
index 000000000..1d99cab4a
--- /dev/null
+++ b/crates/ra_syntax/src/yellow/syntax.rs
@@ -0,0 +1,215 @@
+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<R: TreeRoot = OwnedRoot> {
+    pub(crate) root: R,
+    // Guaranteed to not dangle, because `root` holds a
+    // strong reference to red's ancestor
+    red: RedPtr,
+}
+
+unsafe impl<R: TreeRoot> Send for SyntaxNode<R> {}
+unsafe impl<R: TreeRoot> Sync for SyntaxNode<R> {}
+
+impl<R1: TreeRoot, R2: TreeRoot> PartialEq<SyntaxNode<R1>> for SyntaxNode<R2> {
+    fn eq(&self, other: &SyntaxNode<R1>) -> bool {
+        self.red == other.red
+    }
+}
+
+impl<R: TreeRoot> Eq for SyntaxNode<R> {}
+impl<R: TreeRoot> Hash for SyntaxNode<R> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.red.hash(state)
+    }
+}
+
+pub type SyntaxNodeRef<'a> = SyntaxNode<RefRoot<'a>>;
+
+#[test]
+fn syntax_node_ref_is_copy() {
+    fn assert_copy<T: Copy>(){}
+    assert_copy::<SyntaxNodeRef>()
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
+pub struct SyntaxError {
+    pub msg: String,
+    pub offset: TextUnit,
+}
+
+impl SyntaxNode<OwnedRoot> {
+    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<RefRoot<'a>> {
+    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<R: TreeRoot> SyntaxNode<R> {
+    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<R> {
+        SyntaxNodeChildren {
+            parent: self.clone(),
+            iter: (0..self.red().n_children())
+        }
+    }
+
+    pub fn parent(&self) -> Option<SyntaxNode<R>> {
+        let parent = self.red().parent()?;
+        Some(SyntaxNode {
+            root: self.root.clone(),
+            red: parent,
+        })
+    }
+
+    pub fn first_child(&self) -> Option<SyntaxNode<R>> {
+        let red = self.red().get_child(0)?;
+        Some(SyntaxNode { root: self.root.clone(), red })
+    }
+
+    pub fn last_child(&self) -> Option<SyntaxNode<R>> {
+        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<SyntaxNode<R>> {
+        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<SyntaxNode<R>> {
+        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<SmolStr> {
+        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<R: TreeRoot> fmt::Debug for SyntaxNode<R> {
+    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<R: TreeRoot> {
+    parent: SyntaxNode<R>,
+    iter: Range<usize>,
+}
+
+impl<R: TreeRoot> Iterator for SyntaxNodeChildren<R> {
+    type Item = SyntaxNode<R>;
+
+    fn next(&mut self) -> Option<SyntaxNode<R>> {
+        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
new file mode 100644
index 000000000..280bedd78
--- /dev/null
+++ b/crates/ra_syntax/src/yellow/syntax_text.rs
@@ -0,0 +1,122 @@
+use std::{
+    fmt, ops,
+};
+
+use {
+    SyntaxNodeRef, TextRange, TextUnit,
+    algo::walk::preorder,
+    text_utils::{intersect, contains_offset_nonstrict},
+};
+
+#[derive(Clone)]
+pub struct SyntaxText<'a> {
+    node: SyntaxNodeRef<'a>,
+    range: TextRange,
+}
+
+impl<'a> SyntaxText<'a> {
+    pub(crate) fn new(node: SyntaxNodeRef<'a>) -> SyntaxText<'a> {
+        SyntaxText {
+            node,
+            range: node.range()
+        }
+    }
+    pub fn chunks(&self) -> impl Iterator<Item=&'a str> {
+        let range = self.range;
+        preorder(self.node)
+            .filter_map(move |node| {
+                let text = node.leaf_text_ref()?;
+                let range = intersect(range, node.range())?;
+                let range = range - node.range().start();
+                Some(&text[range])
+            })
+    }
+    pub fn push_to(&self, buf: &mut String) {
+        self.chunks().for_each(|it| buf.push_str(it));
+    }
+    pub fn to_string(&self) -> String {
+        self.chunks().collect()
+    }
+    pub fn contains(&self, c: char) -> bool {
+        self.chunks().any(|it| it.contains(c))
+    }
+    pub fn find(&self, c: char) -> Option<TextUnit> {
+        let mut acc: TextUnit = 0.into();
+        for chunk in self.chunks() {
+            if let Some(pos) = chunk.find(c) {
+                let pos: TextUnit = (pos as u32).into();
+                return Some(acc + pos);
+            }
+            acc += TextUnit::of_str(chunk);
+        }
+        None
+    }
+    pub fn len(&self) -> TextUnit {
+        self.range.len()
+    }
+    pub fn slice(&self, range: impl SyntaxTextSlice) -> SyntaxText<'a> {
+        let range = range.restrict(self.range)
+            .unwrap_or_else(|| {
+                panic!("invalid slice, range: {:?}, slice: {:?}", self.range, range)
+            });
+        SyntaxText { node: self.node, range }
+    }
+    pub fn char_at(&self, offset: TextUnit) -> Option<char> {
+        let mut start: TextUnit = 0.into();
+        for chunk in self.chunks() {
+            let end = start + TextUnit::of_str(chunk);
+            if start <= offset && offset < end {
+                let off: usize = u32::from(offset - start) as usize;
+                return Some(chunk[off..].chars().next().unwrap());
+            }
+            start = end;
+        }
+        None
+    }
+}
+
+impl<'a> fmt::Debug for SyntaxText<'a> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        fmt::Debug::fmt(&self.to_string(), f)
+    }
+}
+
+impl<'a> fmt::Display for SyntaxText<'a> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        fmt::Display::fmt(&self.to_string(), f)
+    }
+}
+
+pub trait SyntaxTextSlice: fmt::Debug {
+    fn restrict(&self, range: TextRange) -> Option<TextRange>;
+}
+
+impl SyntaxTextSlice for TextRange {
+    fn restrict(&self, range: TextRange) -> Option<TextRange> {
+        intersect(*self, range)
+    }
+}
+
+impl SyntaxTextSlice for ops::RangeTo<TextUnit> {
+    fn restrict(&self, range: TextRange) -> Option<TextRange> {
+        if !contains_offset_nonstrict(range, self.end) {
+            return None;
+        }
+        Some(TextRange::from_to(range.start(), self.end))
+    }
+}
+
+impl SyntaxTextSlice for ops::RangeFrom<TextUnit> {
+    fn restrict(&self, range: TextRange) -> Option<TextRange> {
+        if !contains_offset_nonstrict(range, self.start) {
+            return None;
+        }
+        Some(TextRange::from_to(self.start, range.end()))
+    }
+}
+
+impl SyntaxTextSlice for ops::Range<TextUnit> {
+    fn restrict(&self, range: TextRange) -> Option<TextRange> {
+        TextRange::from_to(self.start, self.end).restrict(range)
+    }
+}