9 files changed, 606 insertions, 12 deletions

diff --git a/src/lib.rs b/src/lib.rs
index b90b70c05..cf2e97024 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -12,7 +12,8 @@
 //!   [RFC.md]: <https://github.com/matklad/libsyntax2/blob/master/docs/RFC.md>
 
 #![forbid(missing_debug_implementations, unconditional_recursion, future_incompatible)]
-#![deny(bad_style, unsafe_code, missing_docs)]
+#![deny(bad_style, missing_docs)]
+#![allow(missing_docs)]
 //#![warn(unreachable_pub)] // rust-lang/rust#47816
 
 extern crate unicode_xid;
@@ -21,19 +22,24 @@ extern crate text_unit;
 mod tree;
 mod lexer;
 mod parser;
+mod yellow;
 
 pub mod syntax_kinds;
 pub use text_unit::{TextRange, TextUnit};
 pub use tree::{File, Node, SyntaxKind, Token};
-pub(crate) use tree::{ErrorMsg, FileBuilder, Sink};
+pub(crate) use tree::{ErrorMsg, FileBuilder, Sink, GreenBuilder};
 pub use lexer::{next_token, tokenize};
-pub use parser::parse;
+pub use yellow::SyntaxNode;
+pub(crate) use yellow::SError;
+pub use parser::{parse, parse_green};
 
 /// Utilities for simple uses of the parser.
 pub mod utils {
     use std::fmt::Write;
 
-    use {File, Node};
+    use {File, Node, SyntaxNode};
+    use std::collections::BTreeSet;
+    use SError;
 
     /// Parse a file and create a string representation of the resulting parse tree.
     pub fn dump_tree(file: &File) -> String {
@@ -65,4 +71,42 @@ pub mod utils {
             }
         }
     }
+
+    /// Parse a file and create a string representation of the resulting parse tree.
+    pub fn dump_tree_green(syntax: &SyntaxNode) -> String {
+        let mut errors: BTreeSet<_> = syntax.root.errors.iter().cloned().collect();
+        let mut result = String::new();
+        go(syntax, &mut result, 0, &mut errors);
+        return result;
+
+        fn go(node: &SyntaxNode, buff: &mut String, level: usize, errors: &mut BTreeSet<SError>) {
+            buff.push_str(&String::from("  ").repeat(level));
+            write!(buff, "{:?}\n", node).unwrap();
+//            let my_errors = node.errors().filter(|e| e.after_child().is_none());
+//            let parent_errors = node.parent()
+//                .into_iter()
+//                .flat_map(|n| n.errors())
+//                .filter(|e| e.after_child() == Some(node));
+//
+            let my_errors: Vec<_> = errors.iter().filter(|e| e.offset == node.range().start())
+                .cloned().collect();
+            for err in my_errors {
+                errors.remove(&err);
+                buff.push_str(&String::from("  ").repeat(level));
+                write!(buff, "err: `{}`\n", err.message).unwrap();
+            }
+
+            for child in node.children().iter() {
+                go(child, buff, level + 1, errors)
+            }
+
+            let my_errors: Vec<_> = errors.iter().filter(|e| e.offset == node.range().end())
+                .cloned().collect();
+            for err in my_errors {
+                errors.remove(&err);
+                buff.push_str(&String::from("  ").repeat(level));
+                write!(buff, "err: `{}`\n", err.message).unwrap();
+            }
+        }
+    }
 }
diff --git a/src/parser/event.rs b/src/parser/event.rs
index ac8a55de9..0fbfaeb9f 100644
--- a/src/parser/event.rs
+++ b/src/parser/event.rs
@@ -1,5 +1,5 @@
 use {
-    ErrorMsg, File, FileBuilder, Sink, SyntaxKind, Token,
+    ErrorMsg, File, FileBuilder, Sink, SyntaxKind, Token, GreenBuilder,
     syntax_kinds::TOMBSTONE,
 };
 use super::is_insignificant;
@@ -69,6 +69,11 @@ pub(crate) enum Event {
 
 pub(super) fn to_file(text: String, tokens: &[Token], events: Vec<Event>) -> File {
     let mut builder = FileBuilder::new(text);
+    process(&mut builder, tokens, events);
+    builder.finish()
+}
+
+pub(super) fn process(builder: &mut Sink, tokens: &[Token], events: Vec<Event>) {
     let mut idx = 0;
 
     let mut holes = Vec::new();
@@ -145,5 +150,4 @@ pub(super) fn to_file(text: String, tokens: &[Token], events: Vec<Event>) -> Fil
             &Event::Error { ref msg } => builder.error(ErrorMsg { msg: msg.clone() }),
         }
     }
-    builder.finish()
 }
diff --git a/src/parser/mod.rs b/src/parser/mod.rs
index 3814837e1..26fbb6e3d 100644
--- a/src/parser/mod.rs
+++ b/src/parser/mod.rs
@@ -1,7 +1,3 @@
-use {File, SyntaxKind, Token};
-
-use syntax_kinds::*;
-
 #[macro_use]
 mod token_set;
 mod parser;
@@ -9,6 +5,16 @@ mod input;
 mod event;
 mod grammar;
 
+use std::sync::Arc;
+use {
+    File, SyntaxKind, Token,
+    yellow::SyntaxNode,
+    syntax_kinds::*
+};
+use GreenBuilder;
+use parser::event::process;
+
+
 /// Parse a sequence of tokens into the representative node tree
 pub fn parse(text: String, tokens: &[Token]) -> File {
     let events = {
@@ -21,6 +27,21 @@ pub fn parse(text: String, tokens: &[Token]) -> File {
     event::to_file(text, tokens, events)
 }
 
+/// Parse a sequence of tokens into the representative node tree
+pub fn parse_green(text: String, tokens: &[Token]) -> SyntaxNode {
+    let events = {
+        let input = input::ParserInput::new(&text, tokens);
+        let parser_impl = parser::imp::ParserImpl::new(&input);
+        let mut parser = parser::Parser(parser_impl);
+        grammar::file(&mut parser);
+        parser.0.into_events()
+    };
+    let mut builder = GreenBuilder::new(text);
+    process(&mut builder, tokens, events);
+    let (green, errors) = builder.finish();
+    SyntaxNode::new(Arc::new(green), errors)
+}
+
 fn is_insignificant(kind: SyntaxKind) -> bool {
     match kind {
         WHITESPACE | COMMENT => true,
diff --git a/src/tree/file_builder.rs b/src/tree/file_builder.rs
index 712602168..4983006cd 100644
--- a/src/tree/file_builder.rs
+++ b/src/tree/file_builder.rs
@@ -7,8 +7,13 @@
 //! tree builder: the parser produces a stream of events like
 //! `start node`, `finish node`, and `FileBuilder` converts
 //! this stream to a real tree.
-use {SyntaxKind, TextRange, TextUnit};
+use std::sync::Arc;
+use {
+    SyntaxKind, TextRange, TextUnit,
+    yellow::GreenNode
+};
 use super::{File, NodeData, NodeIdx, SyntaxErrorData};
+use SError;
 
 pub(crate) trait Sink {
     fn leaf(&mut self, kind: SyntaxKind, len: TextUnit);
@@ -159,3 +164,68 @@ fn grow(left: &mut TextRange, right: TextRange) {
 pub(crate) struct ErrorMsg {
     pub(crate) msg: String,
 }
+
+pub(crate) struct GreenBuilder {
+    text: String,
+    stack: Vec<GreenNode>,
+    pos: TextUnit,
+    root: Option<GreenNode>,
+    errors: Vec<SError>,
+}
+
+impl GreenBuilder {
+    pub(crate) fn new(text: String) -> GreenBuilder {
+        GreenBuilder {
+            text,
+            stack: Vec::new(),
+            pos: 0.into(),
+            root: None,
+            errors: Vec::new(),
+        }
+    }
+
+    pub(crate) fn finish(self) -> (GreenNode, Vec<SError>) {
+        (self.root.unwrap(), self.errors)
+    }
+}
+
+impl Sink for GreenBuilder {
+    fn leaf(&mut self, kind: SyntaxKind, len: TextUnit) {
+        let range = TextRange::offset_len(self.pos, len);
+        self.pos += len;
+        let text = self.text[range].to_owned();
+        let parent = self.stack.last_mut().unwrap();
+        if kind.is_trivia() {
+            parent.push_trivia(kind, text);
+        } else {
+            let node = GreenNode::new_leaf(kind, text);
+            parent.push_child(Arc::new(node));
+        }
+    }
+
+    fn start_internal(&mut self, kind: SyntaxKind) {
+        self.stack.push(GreenNode::new_branch(kind))
+    }
+
+    fn finish_internal(&mut self) {
+        let node = self.stack.pop().unwrap();
+        if let Some(parent) = self.stack.last_mut() {
+            parent.push_child(Arc::new(node))
+        } else {
+            self.root = Some(node);
+        }
+    }
+
+    fn error(&mut self, err: ErrorMsg) {
+        self.errors.push(SError { message: err.msg, offset: self.pos })
+    }
+}
+impl SyntaxKind {
+    fn is_trivia(self) -> bool {
+        match self {
+            SyntaxKind::WHITESPACE | SyntaxKind::DOC_COMMENT | SyntaxKind::COMMENT => true,
+            _ => false
+        }
+    }
+}
+
diff --git a/src/tree/mod.rs b/src/tree/mod.rs
index f7b16d7b5..7abe17592 100644
--- a/src/tree/mod.rs
+++ b/src/tree/mod.rs
@@ -2,7 +2,7 @@ mod file_builder;
 
 use ::{TextRange, TextUnit};
 use std::{fmt, cmp};
-pub(crate) use self::file_builder::{ErrorMsg, FileBuilder, Sink};
+pub(crate) use self::file_builder::{ErrorMsg, FileBuilder, Sink, GreenBuilder};
 
 pub use syntax_kinds::SyntaxKind;
 
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,
+    }
+}