10 files changed, 189 insertions, 145 deletions

diff --git a/src/parser/event_parser/grammar/attributes.rs b/src/parser/event_parser/grammar/attributes.rs
index 8b5e5bcfe..2d04a1a41 100644
--- a/src/parser/event_parser/grammar/attributes.rs
+++ b/src/parser/event_parser/grammar/attributes.rs
@@ -19,13 +19,13 @@ fn attribute(p: &mut Parser, kind: AttrKind) -> bool {
         if kind == AttrKind::Inner && p.raw_lookahead(1) != EXCL {
             return false;
         }
-        p.start(ATTR);
+        let attr = p.start();
         p.bump();
         if kind == AttrKind::Inner {
             p.bump();
         }
         p.expect(L_BRACK) && meta_item(p) && p.expect(R_BRACK);
-        p.finish();
+        attr.complete(p, ATTR);
         true
     } else {
         false
@@ -34,7 +34,7 @@ fn attribute(p: &mut Parser, kind: AttrKind) -> bool {
 
 fn meta_item(p: &mut Parser) -> bool {
     if p.at(IDENT) {
-        p.start(META_ITEM);
+        let meta_item = p.start();
         p.bump();
         if p.eat(EQ) {
             if !expressions::literal(p) {
@@ -46,7 +46,7 @@ fn meta_item(p: &mut Parser) -> bool {
             comma_list(p, R_PAREN, meta_item_inner);
             p.expect(R_PAREN);
         }
-        p.finish();
+        meta_item.complete(p, META_ITEM);
         true
     } else {
         false
diff --git a/src/parser/event_parser/grammar/expressions.rs b/src/parser/event_parser/grammar/expressions.rs
index 0f65193c9..a943b8c81 100644
--- a/src/parser/event_parser/grammar/expressions.rs
+++ b/src/parser/event_parser/grammar/expressions.rs
@@ -6,9 +6,9 @@ pub(super) fn literal(p: &mut Parser) -> bool {
         INT_NUMBER | FLOAT_NUMBER |
         BYTE | CHAR |
         STRING | RAW_STRING | BYTE_STRING | RAW_BYTE_STRING => {
-            p.start(LITERAL);
+            let lit = p.start();
             p.bump();
-            p.finish();
+            lit.complete(p, LITERAL);
             true
         }
         _ => false
diff --git a/src/parser/event_parser/grammar/items.rs b/src/parser/event_parser/grammar/items.rs
index 4514f0dab..c9a890553 100644
--- a/src/parser/event_parser/grammar/items.rs
+++ b/src/parser/event_parser/grammar/items.rs
@@ -8,19 +8,34 @@ pub(super) fn mod_contents(p: &mut Parser) {
 }
 
 fn item(p: &mut Parser) {
-    let attrs_start = p.mark();
+    let item = p.start();
     attributes::outer_attributes(p);
     visibility(p);
     let la = p.raw_lookahead(1);
-    let item_start = p.mark();
-    match p.current() {
-        EXTERN_KW if la == CRATE_KW => extern_crate_item(p),
-        MOD_KW => mod_item(p),
-        USE_KW => use_item(p),
-        STRUCT_KW => struct_item(p),
-        FN_KW => fn_item(p),
+    let item_kind = match p.current() {
+        EXTERN_KW if la == CRATE_KW => {
+            extern_crate_item(p);
+            EXTERN_CRATE_ITEM
+        }
+        MOD_KW => {
+            mod_item(p);
+            MOD_ITEM
+        }
+        USE_KW => {
+            use_item(p);
+            USE_ITEM
+        }
+        STRUCT_KW => {
+            struct_item(p);
+            STRUCT_ITEM
+        }
+        FN_KW => {
+            fn_item(p);
+            FN_ITEM
+        }
         err_token => {
-            p.start(ERROR);
+            item.abandon(p);
+            let err = p.start();
             let message = if err_token == SEMI {
                 //TODO: if the item is incomplete, this message is misleading
                 "expected item, found `;`\n\
@@ -32,60 +47,52 @@ fn item(p: &mut Parser) {
                 .message(message)
                 .emit();
             p.bump();
-            p.finish();
+            err.complete(p, ERROR);
             return;
         }
     };
-    p.forward_parent(attrs_start, item_start);
+    item.complete(p, item_kind);
 }
 
 fn struct_item(p: &mut Parser) {
-    p.start(STRUCT_ITEM);
-
     assert!(p.at(STRUCT_KW));
     p.bump();
 
-    struct_inner(p);
-    p.finish();
-
-    fn struct_inner(p: &mut Parser) {
-        if !p.expect(IDENT) {
-            p.finish();
-            return;
-        }
-        generic_parameters(p);
-        match p.current() {
-            WHERE_KW => {
-                where_clause(p);
-                match p.current() {
-                    SEMI => {
-                        p.bump();
-                        return;
-                    }
-                    L_CURLY => named_fields(p),
-                    _ => { //TODO: special case `(` error message
-                        p.error()
-                            .message("expected `;` or `{`")
-                            .emit();
-                        return;
-                    }
+    if !p.expect(IDENT) {
+        return;
+    }
+    generic_parameters(p);
+    match p.current() {
+        WHERE_KW => {
+            where_clause(p);
+            match p.current() {
+                SEMI => {
+                    p.bump();
+                    return;
+                }
+                L_CURLY => named_fields(p),
+                _ => { //TODO: special case `(` error message
+                    p.error()
+                        .message("expected `;` or `{`")
+                        .emit();
+                    return;
                 }
             }
-            SEMI => {
-                p.bump();
-                return;
-            }
-            L_CURLY => named_fields(p),
-            L_PAREN => {
-                tuple_fields(p);
-                p.expect(SEMI);
-            }
-            _ => {
-                p.error()
-                    .message("expected `;`, `{`, or `(`")
-                    .emit();
-                return;
-            }
+        }
+        SEMI => {
+            p.bump();
+            return;
+        }
+        L_CURLY => named_fields(p),
+        L_PAREN => {
+            pos_fields(p);
+            p.expect(SEMI);
+        }
+        _ => {
+            p.error()
+                .message("expected `;`, `{`, or `(`")
+                .emit();
+            return;
         }
     }
 }
@@ -97,30 +104,30 @@ fn named_fields(p: &mut Parser) {
     }));
 
     fn named_field(p: &mut Parser) {
-        p.start(NAMED_FIELD);
+        let field = p.start();
         visibility(p);
         if p.expect(IDENT) && p.expect(COLON) {
             types::type_ref(p);
         };
-        p.finish()
+        field.complete(p, NAMED_FIELD);
     }
 }
 
-fn tuple_fields(p: &mut Parser) {
+fn pos_fields(p: &mut Parser) {
     if !p.expect(L_PAREN) {
         return;
     }
     comma_list(p, R_PAREN, |p| {
-        tuple_field(p);
+        pos_field(p);
         true
     });
     p.expect(R_PAREN);
 
-    fn tuple_field(p: &mut Parser) {
-        p.start(POS_FIELD);
+    fn pos_field(p: &mut Parser) {
+        let pos_field = p.start();
         visibility(p);
         types::type_ref(p);
-        p.finish();
+        pos_field.complete(p, POS_FIELD);
     }
 }
 
@@ -129,28 +136,21 @@ fn generic_parameters(_: &mut Parser) {}
 fn where_clause(_: &mut Parser) {}
 
 fn extern_crate_item(p: &mut Parser) {
-    p.start(EXTERN_CRATE_ITEM);
-
     assert!(p.at(EXTERN_KW));
     p.bump();
-
     assert!(p.at(CRATE_KW));
     p.bump();
 
     p.expect(IDENT) && alias(p) && p.expect(SEMI);
-    p.finish();
 }
 
 fn mod_item(p: &mut Parser) {
-    p.start(MOD_ITEM);
-
     assert!(p.at(MOD_KW));
     p.bump();
 
     if p.expect(IDENT) && !p.eat(SEMI) {
         p.curly_block(mod_contents);
     }
-    p.finish()
 }
 
 pub(super) fn is_use_tree_start(kind: SyntaxKind) -> bool {
@@ -158,28 +158,24 @@ pub(super) fn is_use_tree_start(kind: SyntaxKind) -> bool {
 }
 
 fn use_item(p: &mut Parser) {
-    p.start(USE_ITEM);
-
     assert!(p.at(USE_KW));
     p.bump();
+
     use_tree(p);
     p.expect(SEMI);
-    p.finish();
 
     fn use_tree(p: &mut Parser) -> bool {
         let la = p.raw_lookahead(1);
+        let m = p.start();
         match (p.current(), la) {
             (STAR, _) => {
-                p.start(USE_TREE);
                 p.bump();
             }
             (COLONCOLON, STAR) => {
-                p.start(USE_TREE);
                 p.bump();
                 p.bump();
             }
             (L_CURLY, _) | (COLONCOLON, L_CURLY) => {
-                p.start(USE_TREE);
                 if p.at(COLONCOLON) {
                     p.bump();
                 }
@@ -188,7 +184,6 @@ fn use_item(p: &mut Parser) {
                 });
             }
             _ if paths::is_path_start(p) => {
-                p.start(USE_TREE);
                 paths::use_path(p);
                 match p.current() {
                     AS_KW => {
@@ -216,23 +211,23 @@ fn use_item(p: &mut Parser) {
                     _ => (),
                 }
             }
-            _ => return false,
+            _ => {
+                m.abandon(p);
+                return false
+            },
         }
-        p.finish();
+        m.complete(p, USE_TREE);
         return true;
     }
 }
 
 
 fn fn_item(p: &mut Parser) {
-    p.start(FN_ITEM);
-
     assert!(p.at(FN_KW));
     p.bump();
 
     p.expect(IDENT) && p.expect(L_PAREN) && p.expect(R_PAREN)
         && p.curly_block(|_| ());
-    p.finish();
 }
 
 
diff --git a/src/parser/event_parser/grammar/mod.rs b/src/parser/event_parser/grammar/mod.rs
index c3d0c8c10..d3b63c4c1 100644
--- a/src/parser/event_parser/grammar/mod.rs
+++ b/src/parser/event_parser/grammar/mod.rs
@@ -10,15 +10,15 @@ mod types;
 mod paths;
 
 pub(crate) fn file(p: &mut Parser) {
-    p.start(FILE);
+    let file = p.start();
     p.eat(SHEBANG);
     items::mod_contents(p);
-    p.finish()
+    file.complete(p, FILE);
 }
 
 fn visibility(p: &mut Parser) {
     if p.at(PUB_KW) {
-        p.start(VISIBILITY);
+        let vis = p.start();
         p.bump();
         if p.at(L_PAREN) {
             match p.raw_lookahead(1) {
@@ -32,16 +32,16 @@ fn visibility(p: &mut Parser) {
                 _ => ()
             }
         }
-        p.finish();
+        vis.complete(p, VISIBILITY);
     }
 }
 
 fn alias(p: &mut Parser) -> bool {
     if p.at(AS_KW) {
-        p.start(ALIAS);
+        let alias = p.start();
         p.bump();
         p.expect(IDENT);
-        p.finish();
+        alias.complete(p, ALIAS);
     }
     true //FIXME: return false if three are errors
 }
diff --git a/src/parser/event_parser/grammar/paths.rs b/src/parser/event_parser/grammar/paths.rs
index f5124cfce..b58c59aef 100644
--- a/src/parser/event_parser/grammar/paths.rs
+++ b/src/parser/event_parser/grammar/paths.rs
@@ -8,19 +8,16 @@ pub(crate) fn use_path(p: &mut Parser) {
     if !is_path_start(p) {
         return;
     }
-    let mut prev = p.mark();
-    p.start(PATH);
+    let path = p.start();
     path_segment(p, true);
-    p.finish();
+    let mut qual = path.complete(p, PATH);
     loop {
-        let curr = p.mark();
         if p.at(COLONCOLON) && !items::is_use_tree_start(p.raw_lookahead(1)) {
-            p.start(PATH);
+            let path = qual.precede(p);
             p.bump();
             path_segment(p, false);
-            p.forward_parent(prev, curr);
-            prev = curr;
-            p.finish();
+            let path = path.complete(p, PATH);
+            qual = path;
         } else {
             break;
         }
@@ -28,7 +25,7 @@ pub(crate) fn use_path(p: &mut Parser) {
 }
 
 fn path_segment(p: &mut Parser, first: bool) {
-    p.start(PATH_SEGMENT);
+    let segment = p.start();
     if first {
         p.eat(COLONCOLON);
     }
@@ -42,5 +39,5 @@ fn path_segment(p: &mut Parser, first: bool) {
                 .emit();
         }
     };
-    p.finish();
+    segment.complete(p, PATH_SEGMENT);
 }
diff --git a/src/parser/event_parser/mod.rs b/src/parser/event_parser/mod.rs
index c89a3ebe7..7c81182e3 100644
--- a/src/parser/event_parser/mod.rs
+++ b/src/parser/event_parser/mod.rs
@@ -23,4 +23,4 @@ pub(crate) fn parse<'t>(text: &'t str, raw_tokens: &'t [Token]) -> Vec<Event> {
     let mut parser = parser::Parser::new(text, raw_tokens);
     grammar::file(&mut parser);
     parser.into_events()
-}
\ No newline at end of file
+}
diff --git a/src/parser/event_parser/parser.rs b/src/parser/event_parser/parser.rs
index 6171b3579..2bc9dd34f 100644
--- a/src/parser/event_parser/parser.rs
+++ b/src/parser/event_parser/parser.rs
@@ -1,8 +1,71 @@
 use {Token, SyntaxKind, TextUnit};
-use super::{Event};
+use super::Event;
 use super::super::is_insignificant;
 use syntax_kinds::{L_CURLY, R_CURLY, ERROR};
-use tree::EOF;
+use tree::{EOF, TOMBSTONE};
+
+pub(crate) struct Marker {
+    pos: u32
+}
+
+impl Marker {
+    pub fn complete(self, p: &mut Parser, kind: SyntaxKind) -> CompleteMarker {
+        match self.event(p) {
+            &mut Event::Start { kind: ref mut slot, ..} => {
+                *slot = kind;
+            }
+            _ => unreachable!(),
+        }
+        p.event(Event::Finish);
+        let result = CompleteMarker { pos: self.pos };
+        ::std::mem::forget(self);
+        result
+    }
+
+    pub fn abandon(self, p: &mut Parser) {
+        let idx = self.pos as usize;
+        if idx == p.events.len() - 1 {
+            match p.events.pop() {
+                Some(Event::Start { kind: TOMBSTONE, forward_parent: None }) => (),
+                _ => unreachable!()
+            }
+        }
+        ::std::mem::forget(self);
+    }
+
+    fn event<'p>(&self, p: &'p mut Parser) -> &'p mut Event {
+        &mut p.events[self.idx()]
+    }
+
+    fn idx(&self) -> usize {
+        self.pos as usize
+    }
+}
+
+impl Drop for Marker {
+    fn drop(&mut self) {
+        if !::std::thread::panicking() {
+            panic!("Each marker should be eithe completed or abandoned");
+        }
+    }
+}
+
+pub(crate) struct CompleteMarker {
+    pos: u32
+}
+
+impl CompleteMarker {
+    pub(crate) fn precede(self, p: &mut Parser) -> Marker {
+        let m = p.start();
+        match p.events[self.pos as usize] {
+            Event::Start { ref mut forward_parent, ..} => {
+                *forward_parent = Some(m.pos - self.pos);
+            }
+            _ => unreachable!(),
+        }
+        m
+    }
+}
 
 
 pub(crate) struct Parser<'t> {
@@ -19,12 +82,9 @@ pub(crate) struct Parser<'t> {
     curly_limit: Option<i32>,
 }
 
-#[derive(Debug, Clone, Copy,PartialEq, Eq)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
 pub(crate) struct Pos(u32);
 
-#[derive(Debug, Clone, Copy,PartialEq, Eq)]
-pub(crate) struct Mark(u32);
-
 impl<'t> Parser<'t> {
     pub(crate) fn new(text: &'t str, raw_tokens: &'t [Token]) -> Parser<'t> {
         let mut tokens = Vec::new();
@@ -50,31 +110,13 @@ impl<'t> Parser<'t> {
         }
     }
 
-    pub(crate) fn mark(&self) -> Mark {
-        Mark(self.events.len() as u32)
-    }
-
-    pub(crate) fn forward_parent(&mut self, child: Mark, parent: Mark) {
-        if child == parent || parent == self.mark() {
-            return
-        }
-        assert!(child.0 < parent.0);
-        let diff = parent.0 - child.0;
-        match self.events[child.0 as usize] {
-            Event::Start { ref mut forward_parent, .. } => {
-                *forward_parent = Some(diff);
-            }
-            _ => unreachable!()
-        }
-    }
-
     pub(crate) fn pos(&self) -> Pos {
         Pos(self.pos as u32)
     }
 
     pub(crate) fn into_events(self) -> Vec<Event> {
         assert!(self.curly_limit.is_none());
-        assert!(self.current() == EOF);
+        assert_eq!(self.current(), EOF);
         self.events
     }
 
@@ -85,18 +127,16 @@ impl<'t> Parser<'t> {
         let token = self.tokens[self.pos];
         if let Some(limit) = self.curly_limit {
             if limit == self.curly_level && token.kind == R_CURLY {
-                return EOF
+                return EOF;
             }
         }
         token.kind
     }
 
-    pub(crate) fn start(&mut self, kind: SyntaxKind) {
-        self.event(Event::Start { kind, forward_parent: None });
-    }
-
-    pub(crate) fn finish(&mut self) {
-        self.event(Event::Finish);
+    pub(crate) fn start(&mut self) -> Marker {
+        let m = Marker { pos: self.events.len() as u32 };
+        self.event(Event::Start { kind: TOMBSTONE, forward_parent: None });
+        m
     }
 
     pub(crate) fn error<'p>(&'p mut self) -> ErrorBuilder<'p, 't> {
@@ -124,20 +164,20 @@ impl<'t> Parser<'t> {
         let old_level = self.curly_level;
         let old_limit = self.curly_limit;
         if !self.expect(L_CURLY) {
-            return false
+            return false;
         }
         self.curly_limit = Some(self.curly_level);
         f(self);
         assert!(self.curly_level > old_level);
         self.curly_limit = old_limit;
         if !self.expect(R_CURLY) {
-            self.start(ERROR);
+            let err = self.start();
             while self.curly_level > old_level {
                 if self.bump() == EOF {
                     break;
                 }
             }
-            self.finish();
+            err.complete(self, ERROR);
         }
         true
     }
@@ -149,7 +189,7 @@ impl<'t> Parser<'t> {
 
 pub(crate) struct ErrorBuilder<'p, 't: 'p> {
     message: Option<String>,
-    parser: &'p mut Parser<'t>
+    parser: &'p mut Parser<'t>,
 }
 
 impl<'t, 'p> ErrorBuilder<'p, 't> {
diff --git a/src/parser/mod.rs b/src/parser/mod.rs
index 0c29442f9..5ec4b8e93 100644
--- a/src/parser/mod.rs
+++ b/src/parser/mod.rs
@@ -1,6 +1,7 @@
 use {Token, File, FileBuilder, Sink, SyntaxKind};
 
 use syntax_kinds::*;
+use tree::TOMBSTONE;
 
 mod event_parser;
 use self::event_parser::Event;
@@ -29,6 +30,8 @@ fn from_events_to_file(
         }
 
         match event {
+            &Event::Start { kind: TOMBSTONE, .. } => (),
+
             &Event::Start { .. } => {
                 forward_parents.clear();
                 let mut idx = i;
@@ -62,7 +65,7 @@ fn from_events_to_file(
                 }
                 builder.finish_internal()
             },
-            &Event::Token { kind, mut n_raw_tokens } => loop {
+            &Event::Token { kind: _, mut n_raw_tokens } => loop {
                 let token = tokens[idx];
                 if !is_insignificant(token.kind) {
                     n_raw_tokens -= 1;
diff --git a/src/tree/file_builder.rs b/src/tree/file_builder.rs
index 37bd5b2c8..35702ddd7 100644
--- a/src/tree/file_builder.rs
+++ b/src/tree/file_builder.rs
@@ -48,7 +48,9 @@ impl Sink for FileBuilder {
     }
 
     fn finish_internal(&mut self) {
-        let (id, _) = self.in_progress.pop().unwrap();
+        let (id, _) = self.in_progress.pop().expect(
+            "trying to complete a node, but there are no in-progress nodes"
+        );
         if !self.in_progress.is_empty() {
             self.add_len(id);
         }
@@ -77,8 +79,8 @@ impl FileBuilder {
             self.in_progress.iter().map(|&(idx, _)| self.nodes[idx].kind)
                 .collect::<Vec<_>>()
         );
-        assert!(
-            self.pos == (self.text.len() as u32).into(),
+        assert_eq!(
+            self.pos, (self.text.len() as u32).into(),
             "nodes in FileBuilder do not cover the whole file"
         );
         File {
diff --git a/src/tree/mod.rs b/src/tree/mod.rs
index d8f843737..3315b926e 100644
--- a/src/tree/mod.rs
+++ b/src/tree/mod.rs
@@ -10,17 +10,24 @@ pub use self::file_builder::{FileBuilder, Sink};
 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct SyntaxKind(pub(crate) u32);
 
-pub(crate) const EOF: SyntaxKind = SyntaxKind(10000);
+pub(crate) const EOF: SyntaxKind = SyntaxKind(!0);
 pub(crate) const EOF_INFO: SyntaxInfo = SyntaxInfo {
     name: "EOF"
 };
 
+pub(crate) const TOMBSTONE: SyntaxKind = SyntaxKind(!0 - 1);
+pub(crate) const TOMBSTONE_INFO: SyntaxInfo = SyntaxInfo {
+    name: "TOMBSTONE"
+};
+
+
 impl SyntaxKind {
     fn info(self) -> &'static SyntaxInfo {
-        if self == EOF {
-            return &EOF_INFO;
+        match self {
+            EOF => &EOF_INFO,
+            TOMBSTONE => &TOMBSTONE_INFO,
+            _ => syntax_info(self),
         }
-        syntax_info(self)
     }
 }