5 files changed, 438 insertions, 0 deletions

diff --git a/crates/libsyntax2/src/yellow/builder.rs b/crates/libsyntax2/src/yellow/builder.rs
new file mode 100644
index 000000000..5e94e5055
--- /dev/null
+++ b/crates/libsyntax2/src/yellow/builder.rs
@@ -0,0 +1,65 @@
+use {
+    parser_impl::Sink,
+    yellow::{GreenNode, SyntaxError, SyntaxNode, SyntaxRoot},
+    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 = SyntaxNode;
+
+    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) -> SyntaxNode {
+        assert_eq!(self.children.len(), 1);
+        let root = self.children.pop().unwrap();
+        let root = SyntaxRoot::new(root, self.errors);
+        SyntaxNode::new_owned(root)
+    }
+}
diff --git a/crates/libsyntax2/src/yellow/green.rs b/crates/libsyntax2/src/yellow/green.rs
new file mode 100644
index 000000000..f505b26d7
--- /dev/null
+++ b/crates/libsyntax2/src/yellow/green.rs
@@ -0,0 +1,95 @@
+use std::sync::Arc;
+use {
+    SyntaxKind, TextUnit,
+    smol_str::SmolStr,
+};
+
+#[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::of_str(text.as_str()),
+            GreenNode::Branch(b) => b.text_len(),
+        }
+    }
+
+    pub fn children(&self) -> &[GreenNode] {
+        match self {
+            GreenNode::Leaf { .. } => &[],
+            GreenNode::Branch(b) => b.children(),
+        }
+    }
+
+    pub fn text(&self) -> String {
+        let mut buff = String::new();
+        go(self, &mut buff);
+        return buff;
+        fn go(node: &GreenNode, buff: &mut String) {
+            match node {
+                GreenNode::Leaf { text, .. } => buff.push_str(text.as_str()),
+                GreenNode::Branch(b) => b.children().iter().for_each(|child| go(child, buff)),
+            }
+        }
+    }
+}
+
+#[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/libsyntax2/src/yellow/mod.rs b/crates/libsyntax2/src/yellow/mod.rs
new file mode 100644
index 000000000..ff3bb221b
--- /dev/null
+++ b/crates/libsyntax2/src/yellow/mod.rs
@@ -0,0 +1,62 @@
+mod builder;
+mod green;
+mod red;
+mod syntax;
+
+use std::{
+    ops::Deref,
+    sync::Arc,
+    ptr,
+};
+pub use self::syntax::{SyntaxNode, SyntaxNodeRef, SyntaxError};
+pub(crate) use self::{
+    builder::GreenBuilder,
+    green::GreenNode,
+    red::RedNode,
+};
+
+pub trait TreeRoot: Deref<Target=SyntaxRoot> + Clone + Send + Sync {}
+
+#[derive(Debug)]
+pub struct SyntaxRoot {
+    red: RedNode,
+    pub(crate) errors: Vec<SyntaxError>,
+}
+
+impl TreeRoot for Arc<SyntaxRoot> {}
+
+impl<'a> TreeRoot for &'a SyntaxRoot {}
+
+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)]
+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 impl TreeRoot) -> &'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/libsyntax2/src/yellow/red.rs b/crates/libsyntax2/src/yellow/red.rs
new file mode 100644
index 000000000..13ad44c65
--- /dev/null
+++ b/crates/libsyntax2/src/yellow/red.rs
@@ -0,0 +1,94 @@
+use parking_lot::RwLock;
+use {yellow::{GreenNode, RedPtr}, TextUnit};
+
+#[derive(Debug)]
+pub(crate) struct RedNode {
+    green: GreenNode,
+    parent: Option<ParentData>,
+    children: RwLock<Box<[Option<RedNode>]>>,
+}
+
+#[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 n_children = green.children().len();
+        let children = (0..n_children)
+            .map(|_| None)
+            .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;
+        }
+        match &self.children.read()[idx] {
+            Some(child) => return Some(RedPtr::new(child)),
+            None => (),
+        };
+        let green_children = self.green.children();
+        let start_offset = self.start_offset()
+            + green_children[..idx]
+            .iter()
+            .map(|x| x.text_len())
+            .sum::<TextUnit>();
+        let child =
+            RedNode::new_child(green_children[idx].clone(), RedPtr::new(self), start_offset, idx);
+        let mut children = self.children.write();
+        if children[idx].is_none() {
+            children[idx] = Some(child)
+        }
+        Some(RedPtr::new(children[idx].as_ref().unwrap()))
+    }
+
+    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/libsyntax2/src/yellow/syntax.rs b/crates/libsyntax2/src/yellow/syntax.rs
new file mode 100644
index 000000000..6e33310f1
--- /dev/null
+++ b/crates/libsyntax2/src/yellow/syntax.rs
@@ -0,0 +1,122 @@
+use std::{fmt, sync::Arc};
+
+use {
+    yellow::{RedNode, TreeRoot, SyntaxRoot, RedPtr},
+    SyntaxKind::{self, *},
+    TextRange, TextUnit,
+};
+
+
+#[derive(Clone, Copy)]
+pub struct SyntaxNode<R: TreeRoot = Arc<SyntaxRoot>> {
+    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> {}
+
+pub type SyntaxNodeRef<'a> = SyntaxNode<&'a SyntaxRoot>;
+
+#[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
+pub struct SyntaxError {
+    pub msg: String,
+    pub offset: TextUnit,
+}
+
+impl SyntaxNode<Arc<SyntaxRoot>> {
+    pub(crate) fn new_owned(root: SyntaxRoot) -> Self {
+        let root = Arc::new(root);
+        let red = RedPtr::new(&root.red);
+        SyntaxNode { root, red }
+    }
+}
+
+impl<R: TreeRoot> SyntaxNode<R> {
+    pub fn as_ref<'a>(&'a self) -> SyntaxNode<&'a SyntaxRoot> {
+        SyntaxNode {
+            root: &*self.root,
+            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) -> String {
+        self.red().green().text()
+    }
+
+    pub fn children<'a>(&'a self) -> impl Iterator<Item = SyntaxNode<R>> + 'a {
+        let red = self.red();
+        let n_children = red.n_children();
+        (0..n_children).map(move |i| SyntaxNode {
+            root: self.root.clone(),
+            red: red.get_child(i).unwrap(),
+        })
+    }
+
+    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>> {
+        self.children().next()
+    }
+
+    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 is_leaf(&self) -> bool {
+        self.first_child().is_none()
+    }
+
+    fn red(&self) -> &RedNode {
+        unsafe { self.red.get(&self.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(())
+    }
+}
+
+fn has_short_text(kind: SyntaxKind) -> bool {
+    match kind {
+        IDENT | LIFETIME | INT_NUMBER | FLOAT_NUMBER => true,
+        _ => false,
+    }
+}