Introduce red-green syntax tree

4 files changed, 455 insertions, 0 deletions

diff --git a/src/yellow/green.rs b/src/yellow/green.rs
new file mode 100644
index 000000000..ede23b719
--- /dev/null
+++ b/src/yellow/green.rs
@@ -0,0 +1,194 @@
+use std::sync::Arc;
+use text_unit::TextUnit;
+use SyntaxKind;
+
+type TokenText = String;
+
+#[derive(Debug)]
+pub(crate) struct GreenNode {
+    kind: SyntaxKind,
+    data: GreenNodeData,
+}
+
+impl GreenNode {
+    pub(crate) fn new_leaf(kind: SyntaxKind, text: TokenText) -> GreenNode {
+        GreenNode {
+            kind,
+            data: GreenNodeData::Leaf(GreenLeaf { text }),
+        }
+    }
+
+    pub(crate) fn new_branch(
+        kind: SyntaxKind,
+    ) -> GreenNode {
+        let branch = GreenBranch {
+            text_len: 0.into(),
+            leading_trivia: Trivias::default(),
+            children: Vec::new(),
+        };
+        GreenNode {
+            kind,
+            data: GreenNodeData::Branch(branch),
+        }
+    }
+
+    pub(crate) fn push_trivia(&mut self, kind: SyntaxKind, text: TokenText) {
+        let branch = match &mut self.data {
+            GreenNodeData::Branch(branch) => branch,
+            _ => panic!()
+        };
+        branch.text_len += TextUnit::of_str(&text);
+        let leading = &mut branch.leading_trivia;
+        branch.children.last_mut().map(|(_, t)| t).unwrap_or(leading)
+            .push(Arc::new(GreenTrivia { kind, text }));
+    }
+
+    pub(crate) fn push_child(&mut self, node: Arc<GreenNode>) {
+        let branch = match &mut self.data {
+            GreenNodeData::Branch(branch) => branch,
+            _ => panic!()
+        };
+        branch.text_len += node.text_len();
+        branch.children.push((node, Trivias::default()));
+    }
+
+    pub(crate) fn kind(&self) -> SyntaxKind {
+        self.kind
+    }
+
+    pub(crate) fn text_len(&self) -> TextUnit {
+        match &self.data {
+            GreenNodeData::Leaf(l) => l.text_len(),
+            GreenNodeData::Branch(b) => b.text_len(),
+        }
+    }
+
+    pub(crate) fn text(&self) -> String {
+        let mut buff = String::new();
+        go(self, &mut buff);
+        return buff;
+        fn go(node: &GreenNode, buff: &mut String) {
+            match &node.data {
+                GreenNodeData::Leaf(l) => buff.push_str(&l.text),
+                GreenNodeData::Branch(branch) => {
+                    add_trivia(&branch.leading_trivia, buff);
+                    branch.children.iter().for_each(|(child, trivias)| {
+                        go(child, buff);
+                        add_trivia(trivias, buff);
+                    })
+                }
+            }
+        }
+
+        fn add_trivia(trivias: &Trivias, buff: &mut String) {
+            trivias.iter().for_each(|t| buff.push_str(&t.text))
+        }
+    }
+
+    pub(crate) fn n_children(&self) -> usize {
+        match &self.data {
+            GreenNodeData::Leaf(_) => 0,
+            GreenNodeData::Branch(branch) => branch.children.len(),
+        }
+    }
+
+    pub(crate) fn nth_child(&self, idx: usize) -> &Arc<GreenNode> {
+        match &self.data {
+            GreenNodeData::Leaf(_) => panic!("leaf nodes have no children"),
+            GreenNodeData::Branch(branch) => &branch.children[idx].0,
+        }
+    }
+
+    pub(crate) fn nth_trivias(&self, idx: usize) -> &Trivias {
+        match &self.data {
+            GreenNodeData::Leaf(_) => panic!("leaf nodes have no children"),
+            GreenNodeData::Branch(branch) => if idx == 0 {
+                &branch.leading_trivia
+            } else {
+                &branch.children[idx - 1].1
+            },
+        }
+    }
+
+    pub(crate) fn is_leaf(&self) -> bool {
+        match self.data {
+            GreenNodeData::Leaf(_) => true,
+            GreenNodeData::Branch(_) => false
+        }
+    }
+
+    pub(crate) fn leaf_text(&self) -> &str {
+        match &self.data {
+            GreenNodeData::Leaf(l) => l.text.as_str(),
+            GreenNodeData::Branch(_) => panic!("not a leaf")
+        }
+    }
+}
+
+#[derive(Debug)]
+enum GreenNodeData {
+    Leaf(GreenLeaf),
+    Branch(GreenBranch),
+}
+
+#[derive(Debug)]
+struct GreenLeaf {
+    text: TokenText
+}
+
+#[derive(Debug)]
+struct GreenBranch {
+    text_len: TextUnit,
+    leading_trivia: Trivias,
+    children: Vec<(Arc<GreenNode>, Trivias)>,
+}
+
+#[derive(Debug)]
+pub(crate) struct GreenTrivia {
+    pub(crate) kind: SyntaxKind,
+    pub(crate) text: TokenText,
+}
+
+type Trivias = Vec<Arc<GreenTrivia>>;
+
+
+pub(crate) trait TextLen {
+    fn text_len(&self) -> TextUnit;
+}
+
+impl TextLen for GreenTrivia {
+    fn text_len(&self) -> TextUnit {
+        TextUnit::of_str(&self.text)
+    }
+}
+
+impl<T: TextLen> TextLen for Arc<T> {
+    fn text_len(&self) -> TextUnit {
+        let this: &T = self;
+        this.text_len()
+    }
+}
+
+impl TextLen for GreenNode {
+    fn text_len(&self) -> TextUnit {
+        self.text_len()
+    }
+}
+
+impl TextLen for GreenLeaf {
+    fn text_len(&self) -> TextUnit {
+        TextUnit::of_str(&self.text)
+    }
+}
+
+impl TextLen for GreenBranch {
+    fn text_len(&self) -> TextUnit {
+        self.text_len
+    }
+}
+
+impl<T: TextLen> TextLen for [T] {
+    fn text_len(&self) -> TextUnit {
+        self.iter().map(TextLen::text_len).sum()
+    }
+}
diff --git a/src/yellow/mod.rs b/src/yellow/mod.rs
new file mode 100644
index 000000000..236328a7f
--- /dev/null
+++ b/src/yellow/mod.rs
@@ -0,0 +1,42 @@
+mod green;
+mod red;
+mod syntax;
+
+use std::{
+    sync::{Arc, Weak},
+    ops::Deref,
+    mem
+};
+pub(crate) use self::{
+    green::{GreenNode, TextLen},
+    red::RedNode,
+    syntax::SError,
+};
+pub use self::syntax::SyntaxNode;
+
+// This could be just `*const T`, but we use `Weak` for additional checks
+#[derive(Debug)]
+pub(crate) struct Ptr<T>(Weak<T>);
+
+impl<T> Clone for Ptr<T> {
+    fn clone(&self) -> Self {
+        Ptr(self.0.clone())
+    }
+}
+
+impl<T> Ptr<T> {
+    fn clone(self_: &Ptr<T>) -> Ptr<T> {
+        Ptr(Weak::clone(&self_.0))
+    }
+
+    fn new(arc: &Arc<T>) -> Ptr<T> {
+        Ptr(Arc::downgrade(arc))
+    }
+
+    unsafe fn get(&self) -> &T {
+        let t = self.0.upgrade()
+            .expect("caller must guarantee that Ptr is not null");
+        let t: &T = &*t;
+        mem::transmute(t)
+    }
+}
diff --git a/src/yellow/red.rs b/src/yellow/red.rs
new file mode 100644
index 000000000..feba99faa
--- /dev/null
+++ b/src/yellow/red.rs
@@ -0,0 +1,87 @@
+use std::sync::{Arc, Weak, RwLock};
+use {
+    TextUnit, SyntaxKind, TextRange,
+    yellow::{Ptr, GreenNode, TextLen}
+};
+
+#[derive(Debug)]
+pub(crate) struct RedNode {
+    green: Arc<GreenNode>,
+    parent: Option<ParentData>,
+    children: RwLock<Vec<Option<Arc<RedNode>>>>,
+}
+
+#[derive(Debug)]
+struct ParentData {
+    parent: Ptr<RedNode>,
+    start_offset: TextUnit,
+    index_in_parent: usize,
+}
+
+impl RedNode {
+    pub fn new_root(
+        green: Arc<GreenNode>,
+    ) -> RedNode {
+        RedNode::new(green, None)
+    }
+
+    fn new_child(
+        green: Arc<GreenNode>,
+        parent: Ptr<RedNode>,
+        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: Arc<GreenNode>,
+        parent: Option<ParentData>,
+    ) -> RedNode {
+        let children = vec![None; green.n_children()];
+        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.n_children()
+    }
+
+    pub(crate) fn nth_child(&self, me: Ptr<RedNode>, n: usize) -> Arc<RedNode> {
+        match &self.children.read().unwrap()[n] {
+            Some(child) => return child.clone(),
+            None => (),
+        }
+        let mut children = self.children.write().unwrap();
+        if children[n].is_none() {
+            let start_offset = {
+                let mut acc = self.start_offset();
+                for i in 0..n {
+                    acc += self.green.nth_trivias(i).text_len();
+                    acc += self.green.nth_child(i).text_len();
+                }
+                acc += self.green.nth_trivias(n).text_len();
+                acc
+            };
+            let green = self.green.nth_child(n).clone();
+            let child = RedNode::new_child(green, me, start_offset, n);
+            children[n] = Some(Arc::new(child))
+        }
+        children[n].as_ref().unwrap().clone()
+    }
+}
diff --git a/src/yellow/syntax.rs b/src/yellow/syntax.rs
new file mode 100644
index 000000000..0c9ffeb14
--- /dev/null
+++ b/src/yellow/syntax.rs
@@ -0,0 +1,132 @@
+use std::{
+    fmt,
+    sync::Arc,
+};
+
+use {
+    TextRange, TextUnit, SyntaxKind,
+    yellow::{Ptr, RedNode, GreenNode, TextLen},
+};
+use yellow::green::GreenTrivia;
+
+#[derive(Clone)]
+pub struct SyntaxNode {
+    pub(crate) root: SyntaxRoot,
+    red: Ptr<RedNode>,
+    trivia_pos: Option<(usize, usize)>,
+}
+
+#[derive(Clone)]
+pub struct SyntaxRoot {
+    red: Arc<RedNode>,
+    pub(crate) errors: Arc<Vec<SError>>,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
+pub(crate) struct SError {
+    pub(crate) message: String,
+    pub(crate) offset: TextUnit,
+}
+
+impl SyntaxNode {
+    pub(crate) fn new(root: Arc<GreenNode>, errors: Vec<SError>) -> SyntaxNode {
+        let root = Arc::new(RedNode::new_root(root));
+        let red = Ptr::new(&root);
+        let root = SyntaxRoot { red: root, errors: Arc::new(errors) };
+        SyntaxNode { root, red, trivia_pos: None }
+    }
+
+    pub fn kind(&self) -> SyntaxKind {
+        let green = self.red().green();
+        match self.trivia_pos {
+            None => green.kind(),
+            Some((i, j)) => green.nth_trivias(i)[j].kind
+        }
+    }
+
+    pub fn range(&self) -> TextRange {
+        let red = self.red();
+        let green = red.green();
+        match self.trivia_pos {
+            None => TextRange::offset_len(red.start_offset(), red.green().text_len()),
+            Some((i, j)) => {
+                let trivias = green.nth_trivias(i);
+                let offset = if i == 0 {
+                    red.start_offset()
+                } else {
+                    let prev_child = red.nth_child(Ptr::clone(&self.red), i - 1);
+                    let mut offset = prev_child.start_offset() + prev_child.green().text_len();
+                    for k in 0..j {
+                        offset += &trivias[k].text_len();
+                    }
+                    offset
+                };
+                TextRange::offset_len(offset, trivias[j].text_len())
+            }
+        }
+    }
+
+    pub fn text(&self) -> String {
+        let green = self.red().green();
+        match self.trivia_pos {
+            None => green.text(),
+            Some((i, j)) => green.nth_trivias(i)[j].text.clone()
+        }
+    }
+
+    pub fn children(&self) -> Vec<SyntaxNode> {
+        let mut res = Vec::new();
+        let red = self.red();
+        let green = red.green();
+        if green.is_leaf() || self.trivia_pos.is_some() {
+            return Vec::new();
+        }
+        for (j, _) in green.nth_trivias(0).iter().enumerate() {
+            res.push(SyntaxNode {
+                root: self.root.clone(),
+                red: Ptr::clone(&self.red),
+                trivia_pos: Some((0, j)),
+            })
+        }
+
+        let n_children = red.n_children();
+        for i in 0..n_children {
+            res.push(SyntaxNode {
+                root: self.root.clone(),
+                red: Ptr::new(&red.nth_child(Ptr::clone(&self.red), i)),
+                trivia_pos: None,
+            });
+            for (j, _) in green.nth_trivias(i + 1).iter().enumerate() {
+                res.push(SyntaxNode {
+                    root: self.root.clone(),
+                    red: self.red.clone(),
+                    trivia_pos: Some((i + 1, j)),
+                })
+            }
+        }
+        res
+    }
+
+    fn red(&self) -> &RedNode {
+        // Safe b/c root ptr keeps red alive
+        unsafe { self.red.get() }
+    }
+}
+
+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(())
+    }
+}
+
+fn has_short_text(kind: SyntaxKind) -> bool {
+    use syntax_kinds::*;
+    match kind {
+        IDENT | LIFETIME => true,
+        _ => false,
+    }
+}