11 files changed, 775 insertions, 0 deletions

diff --git a/src/parser/grammar/attributes.rs b/src/parser/grammar/attributes.rs
new file mode 100644
index 000000000..8bf04afce
--- /dev/null
+++ b/src/parser/grammar/attributes.rs
@@ -0,0 +1,79 @@
+use super::*;
+
+pub(super) fn inner_attributes(p: &mut Parser) {
+    while p.at([POUND, EXCL]) {
+        attribute(p, true)
+    }
+}
+
+pub(super) fn outer_attributes(p: &mut Parser) {
+    while p.at(POUND) {
+        attribute(p, false)
+    }
+}
+
+fn attribute(p: &mut Parser, inner: bool) {
+    let attr = p.start();
+    assert!(p.at(POUND));
+    p.bump();
+
+    if inner {
+        assert!(p.at(EXCL));
+        p.bump();
+    }
+
+    if p.expect(L_BRACK) {
+        meta_item(p);
+        p.expect(R_BRACK);
+    }
+    attr.complete(p, ATTR);
+}
+
+fn meta_item(p: &mut Parser) {
+    if p.at(IDENT) {
+        let meta_item = p.start();
+        p.bump();
+        match p.current() {
+            EQ => {
+                p.bump();
+                if !expressions::literal(p) {
+                    p.error().message("expected literal").emit();
+                }
+            }
+            L_PAREN => meta_item_arg_list(p),
+            _ => (),
+        }
+        meta_item.complete(p, META_ITEM);
+    } else {
+        p.error().message("expected attribute value").emit()
+    }
+}
+
+fn meta_item_arg_list(p: &mut Parser) {
+    assert!(p.at(L_PAREN));
+    p.bump();
+    loop {
+        match p.current() {
+            EOF | R_PAREN => break,
+            IDENT => meta_item(p),
+            c => if !expressions::literal(p) {
+                let message = "expected attribute";
+
+                if items::ITEM_FIRST.contains(c) {
+                    p.error().message(message).emit();
+                    return;
+                }
+
+                let err = p.start();
+                p.error().message(message).emit();
+                p.bump();
+                err.complete(p, ERROR);
+                continue;
+            },
+        }
+        if !p.at(R_PAREN) {
+            p.expect(COMMA);
+        }
+    }
+    p.expect(R_PAREN);
+}
diff --git a/src/parser/grammar/expressions.rs b/src/parser/grammar/expressions.rs
new file mode 100644
index 000000000..8caaf3553
--- /dev/null
+++ b/src/parser/grammar/expressions.rs
@@ -0,0 +1,20 @@
+use super::*;
+
+pub(super) fn literal(p: &mut Parser) -> bool {
+    match p.current() {
+        TRUE_KW | FALSE_KW | INT_NUMBER | FLOAT_NUMBER | BYTE | CHAR | STRING | RAW_STRING
+        | BYTE_STRING | RAW_BYTE_STRING => {
+            let lit = p.start();
+            p.bump();
+            lit.complete(p, LITERAL);
+            true
+        }
+        _ => false,
+    }
+}
+
+pub(super) fn expr(p: &mut Parser) {
+    if !literal(p) {
+        p.error().message("expected expression").emit();
+    }
+}
diff --git a/src/parser/grammar/items/consts.rs b/src/parser/grammar/items/consts.rs
new file mode 100644
index 000000000..c9881d681
--- /dev/null
+++ b/src/parser/grammar/items/consts.rs
@@ -0,0 +1,21 @@
+use super::*;
+
+pub(super) fn static_item(p: &mut Parser) {
+    const_or_static(p, STATIC_KW)
+}
+
+pub(super) fn const_item(p: &mut Parser) {
+    const_or_static(p, CONST_KW)
+}
+
+fn const_or_static(p: &mut Parser, kw: SyntaxKind) {
+    assert!(p.at(kw));
+    p.bump();
+    p.eat(MUT_KW); // TODO: validator to forbid const mut
+    p.expect(IDENT);
+    p.expect(COLON);
+    types::type_ref(p);
+    p.expect(EQ);
+    expressions::expr(p);
+    p.expect(SEMI);
+}
diff --git a/src/parser/grammar/items/mod.rs b/src/parser/grammar/items/mod.rs
new file mode 100644
index 000000000..3612802e1
--- /dev/null
+++ b/src/parser/grammar/items/mod.rs
@@ -0,0 +1,196 @@
+use super::*;
+
+mod structs;
+mod use_item;
+mod consts;
+mod traits;
+
+pub(super) fn mod_contents(p: &mut Parser, stop_on_r_curly: bool) {
+    attributes::inner_attributes(p);
+    while !p.at(EOF) && !(stop_on_r_curly && p.at(R_CURLY)) {
+        item(p);
+    }
+}
+
+pub(super) const ITEM_FIRST: TokenSet = token_set![
+    EXTERN_KW, MOD_KW, USE_KW, STRUCT_KW, ENUM_KW, FN_KW, PUB_KW, POUND
+];
+
+fn item(p: &mut Parser) {
+    let item = p.start();
+    attributes::outer_attributes(p);
+    visibility(p);
+    let la = p.nth(1);
+    let item_kind = match p.current() {
+        USE_KW => {
+            use_item::use_item(p);
+            USE_ITEM
+        }
+        // test extern_crate
+        // extern crate foo;
+        EXTERN_KW if la == CRATE_KW => {
+            extern_crate_item(p);
+            EXTERN_CRATE_ITEM
+        }
+        EXTERN_KW => {
+            abi(p);
+            match p.current() {
+                // test extern_fn
+                // extern fn foo() {}
+                FN_KW => {
+                    fn_item(p);
+                    FN_ITEM
+                }
+                // test extern_block
+                // extern {}
+                L_CURLY => {
+                    extern_block(p);
+                    EXTERN_BLOCK
+                }
+                // test extern_struct
+                // extern struct Foo;
+                _ => {
+                    item.abandon(p);
+                    p.error().message("expected `fn` or `{`").emit();
+                    return;
+                }
+            }
+        }
+        STATIC_KW => {
+            consts::static_item(p);
+            STATIC_ITEM
+        }
+        CONST_KW => match p.nth(1) {
+            // test const_fn
+            // const fn foo() {}
+            FN_KW => {
+                p.bump();
+                fn_item(p);
+                FN_ITEM
+            }
+            // test const_unsafe_fn
+            // const unsafe fn foo() {}
+            UNSAFE_KW if p.nth(2) == FN_KW => {
+                p.bump();
+                p.bump();
+                fn_item(p);
+                FN_ITEM
+            }
+            _ => {
+                consts::const_item(p);
+                CONST_ITEM
+            }
+        },
+        // TODO: auto trait
+        // test unsafe_trait
+        // unsafe trait T {}
+        UNSAFE_KW if la == TRAIT_KW => {
+            p.bump();
+            traits::trait_item(p);
+            TRAIT_ITEM
+        }
+        // TODO: default impl
+        // test unsafe_impl
+        // unsafe impl Foo {}
+        UNSAFE_KW if la == IMPL_KW => {
+            p.bump();
+            traits::impl_item(p);
+            IMPL_ITEM
+        }
+        MOD_KW => {
+            mod_item(p);
+            MOD_ITEM
+        }
+        STRUCT_KW => {
+            structs::struct_item(p);
+            STRUCT_ITEM
+        }
+        ENUM_KW => {
+            structs::enum_item(p);
+            ENUM_ITEM
+        }
+        FN_KW => {
+            fn_item(p);
+            FN_ITEM
+        }
+        L_CURLY => {
+            item.abandon(p);
+            error_block(p, "expected item");
+            return;
+        }
+        err_token => {
+            item.abandon(p);
+            let message = if err_token == SEMI {
+                //TODO: if the item is incomplete, this message is misleading
+                "expected item, found `;`\n\
+                 consider removing this semicolon"
+            } else {
+                "expected item"
+            };
+            p.err_and_bump(message);
+            return;
+        }
+    };
+    item.complete(p, item_kind);
+}
+
+fn extern_crate_item(p: &mut Parser) {
+    assert!(p.at(EXTERN_KW));
+    p.bump();
+    assert!(p.at(CRATE_KW));
+    p.bump();
+
+    p.expect(IDENT) && alias(p) && p.expect(SEMI);
+}
+
+fn extern_block(p: &mut Parser) {
+    assert!(p.at(L_CURLY));
+    p.bump();
+    p.expect(R_CURLY);
+}
+
+fn mod_item(p: &mut Parser) {
+    assert!(p.at(MOD_KW));
+    p.bump();
+
+    if p.expect(IDENT) && !p.eat(SEMI) {
+        if p.expect(L_CURLY) {
+            mod_contents(p, true);
+            p.expect(R_CURLY);
+        }
+    }
+}
+
+fn abi(p: &mut Parser) {
+    assert!(p.at(EXTERN_KW));
+    let abi = p.start();
+    p.bump();
+    match p.current() {
+        STRING | RAW_STRING => p.bump(),
+        _ => (),
+    }
+    abi.complete(p, ABI);
+}
+
+fn fn_item(p: &mut Parser) {
+    assert!(p.at(FN_KW));
+    p.bump();
+
+    p.expect(IDENT);
+    if p.at(L_PAREN) {
+        fn_value_parameters(p);
+    } else {
+        p.error().message("expected function arguments").emit();
+    }
+
+    if p.at(L_CURLY) {
+        p.expect(L_CURLY);
+        p.expect(R_CURLY);
+    }
+
+    fn fn_value_parameters(p: &mut Parser) {
+        assert!(p.at(L_PAREN));
+        p.bump();
+        p.expect(R_PAREN);
+    }
+}
diff --git a/src/parser/grammar/items/structs.rs b/src/parser/grammar/items/structs.rs
new file mode 100644
index 000000000..69d95c698
--- /dev/null
+++ b/src/parser/grammar/items/structs.rs
@@ -0,0 +1,117 @@
+use super::*;
+
+pub(super) fn struct_item(p: &mut Parser) {
+    assert!(p.at(STRUCT_KW));
+    p.bump();
+
+    if !p.expect(IDENT) {
+        return;
+    }
+    type_params::list(p);
+    match p.current() {
+        WHERE_KW => {
+            type_params::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 => {
+            pos_fields(p);
+            p.expect(SEMI);
+        }
+        _ => {
+            p.error().message("expected `;`, `{`, or `(`").emit();
+            return;
+        }
+    }
+}
+
+pub(super) fn enum_item(p: &mut Parser) {
+    assert!(p.at(ENUM_KW));
+    p.bump();
+    p.expect(IDENT);
+    type_params::list(p);
+    type_params::where_clause(p);
+    if p.expect(L_CURLY) {
+        while !p.at(EOF) && !p.at(R_CURLY) {
+            let var = p.start();
+            attributes::outer_attributes(p);
+            if p.at(IDENT) {
+                p.bump();
+                match p.current() {
+                    L_CURLY => named_fields(p),
+                    L_PAREN => pos_fields(p),
+                    EQ => {
+                        p.bump();
+                        expressions::expr(p);
+                    }
+                    _ => (),
+                }
+                var.complete(p, ENUM_VARIANT);
+            } else {
+                var.abandon(p);
+                p.err_and_bump("expected enum variant");
+            }
+            if !p.at(R_CURLY) {
+                p.expect(COMMA);
+            }
+        }
+        p.expect(R_CURLY);
+    }
+}
+
+fn named_fields(p: &mut Parser) {
+    assert!(p.at(L_CURLY));
+    p.bump();
+    while !p.at(R_CURLY) && !p.at(EOF) {
+        named_field(p);
+        if !p.at(R_CURLY) {
+            p.expect(COMMA);
+        }
+    }
+    p.expect(R_CURLY);
+
+    fn named_field(p: &mut Parser) {
+        let field = p.start();
+        visibility(p);
+        if p.expect(IDENT) {
+            p.expect(COLON);
+            types::type_ref(p);
+            field.complete(p, NAMED_FIELD);
+        } else {
+            field.abandon(p);
+            p.err_and_bump("expected field declaration");
+        }
+    }
+}
+
+fn pos_fields(p: &mut Parser) {
+    if !p.expect(L_PAREN) {
+        return;
+    }
+    while !p.at(R_PAREN) && !p.at(EOF) {
+        let pos_field = p.start();
+        visibility(p);
+        types::type_ref(p);
+        pos_field.complete(p, POS_FIELD);
+
+        if !p.at(R_PAREN) {
+            p.expect(COMMA);
+        }
+    }
+    p.expect(R_PAREN);
+}
diff --git a/src/parser/grammar/items/traits.rs b/src/parser/grammar/items/traits.rs
new file mode 100644
index 000000000..3bef9639f
--- /dev/null
+++ b/src/parser/grammar/items/traits.rs
@@ -0,0 +1,17 @@
+use super::*;
+
+pub(super) fn trait_item(p: &mut Parser) {
+    assert!(p.at(TRAIT_KW));
+    p.bump();
+    p.expect(IDENT);
+    p.expect(L_CURLY);
+    p.expect(R_CURLY);
+}
+
+pub(super) fn impl_item(p: &mut Parser) {
+    assert!(p.at(IMPL_KW));
+    p.bump();
+    p.expect(IDENT);
+    p.expect(L_CURLY);
+    p.expect(R_CURLY);
+}
diff --git a/src/parser/grammar/items/use_item.rs b/src/parser/grammar/items/use_item.rs
new file mode 100644
index 000000000..38e7b3f8a
--- /dev/null
+++ b/src/parser/grammar/items/use_item.rs
@@ -0,0 +1,66 @@
+use super::*;
+
+pub(super) fn use_item(p: &mut Parser) {
+    assert!(p.at(USE_KW));
+    p.bump();
+    use_tree(p);
+    p.expect(SEMI);
+}
+
+fn use_tree(p: &mut Parser) {
+    let la = p.nth(1);
+    let m = p.start();
+    match (p.current(), la) {
+        (STAR, _) => p.bump(),
+        (COLONCOLON, STAR) => {
+            p.bump();
+            p.bump();
+        }
+        (L_CURLY, _) | (COLONCOLON, L_CURLY) => {
+            if p.at(COLONCOLON) {
+                p.bump();
+            }
+            nested_trees(p);
+        }
+        _ if paths::is_path_start(p) => {
+            paths::use_path(p);
+            match p.current() {
+                AS_KW => {
+                    alias(p);
+                }
+                COLONCOLON => {
+                    p.bump();
+                    match p.current() {
+                        STAR => {
+                            p.bump();
+                        }
+                        L_CURLY => nested_trees(p),
+                        _ => {
+                            // is this unreachable?
+                            p.error().message("expected `{` or `*`").emit();
+                        }
+                    }
+                }
+                _ => (),
+            }
+        }
+        _ => {
+            m.abandon(p);
+            p.err_and_bump("expected one of `*`, `::`, `{`, `self`, `super`, `indent`");
+            return;
+        }
+    }
+    m.complete(p, USE_TREE);
+}
+
+fn nested_trees(p: &mut Parser) {
+    assert!(p.at(L_CURLY));
+    p.bump();
+    while !p.at(EOF) && !p.at(R_CURLY) {
+        use_tree(p);
+        if !p.at(R_CURLY) {
+            p.expect(COMMA);
+        }
+    }
+    p.expect(R_CURLY);
+}
diff --git a/src/parser/grammar/mod.rs b/src/parser/grammar/mod.rs
new file mode 100644
index 000000000..afce308d0
--- /dev/null
+++ b/src/parser/grammar/mod.rs
@@ -0,0 +1,130 @@
+use super::parser::{Parser, TokenSet};
+use SyntaxKind;
+use syntax_kinds::*;
+
+mod items;
+mod attributes;
+mod expressions;
+mod types;
+mod paths;
+mod type_params;
+
+pub(crate) fn file(p: &mut Parser) {
+    let file = p.start();
+    p.eat(SHEBANG);
+    items::mod_contents(p, false);
+    file.complete(p, FILE);
+}
+
+fn visibility(p: &mut Parser) {
+    if p.at(PUB_KW) {
+        let vis = p.start();
+        p.bump();
+        if p.at(L_PAREN) {
+            match p.nth(1) {
+                CRATE_KW | SELF_KW | SUPER_KW => {
+                    p.bump();
+                    p.bump();
+                    p.expect(R_PAREN);
+                }
+                IN_KW => {
+                    p.bump();
+                    p.bump();
+                    paths::use_path(p);
+                    p.expect(R_PAREN);
+                }
+                _ => (),
+            }
+        }
+        vis.complete(p, VISIBILITY);
+    }
+}
+
+fn alias(p: &mut Parser) -> bool {
+    if p.at(AS_KW) {
+        let alias = p.start();
+        p.bump();
+        p.expect(IDENT);
+        alias.complete(p, ALIAS);
+    }
+    true //FIXME: return false if three are errors
+}
+
+fn error_block(p: &mut Parser, message: &str) {
+    assert!(p.at(L_CURLY));
+    let err = p.start();
+    p.error().message(message).emit();
+    p.bump();
+    let mut level: u32 = 1;
+    while level > 0 && !p.at(EOF) {
+        match p.current() {
+            L_CURLY => level += 1,
+            R_CURLY => level -= 1,
+            _ => (),
+        }
+        p.bump();
+    }
+    err.complete(p, ERROR);
+}
+
+impl<'p> Parser<'p> {
+    fn at<L: Lookahead>(&self, l: L) -> bool {
+        l.is_ahead(self)
+    }
+
+    fn err_and_bump(&mut self, message: &str) {
+        let err = self.start();
+        self.error().message(message).emit();
+        self.bump();
+        err.complete(self, ERROR);
+    }
+
+    fn expect(&mut self, kind: SyntaxKind) -> bool {
+        if self.at(kind) {
+            self.bump();
+            true
+        } else {
+            self.error().message(format!("expected {:?}", kind)).emit();
+            false
+        }
+    }
+
+    fn eat(&mut self, kind: SyntaxKind) -> bool {
+        self.current() == kind && {
+            self.bump();
+            true
+        }
+    }
+}
+
+trait Lookahead: Copy {
+    fn is_ahead(self, p: &Parser) -> bool;
+}
+
+impl Lookahead for SyntaxKind {
+    fn is_ahead(self, p: &Parser) -> bool {
+        p.current() == self
+    }
+}
+
+impl Lookahead for [SyntaxKind; 2] {
+    fn is_ahead(self, p: &Parser) -> bool {
+        p.current() == self[0] && p.nth(1) == self[1]
+    }
+}
+
+impl Lookahead for [SyntaxKind; 3] {
+    fn is_ahead(self, p: &Parser) -> bool {
+        p.current() == self[0] && p.nth(1) == self[1] && p.nth(2) == self[2]
+    }
+}
+
+#[derive(Clone, Copy)]
+struct AnyOf<'a>(&'a [SyntaxKind]);
+
+impl<'a> Lookahead for AnyOf<'a> {
+    fn is_ahead(self, p: &Parser) -> bool {
+        let curr = p.current();
+        self.0.iter().any(|&k| k == curr)
+    }
+}
diff --git a/src/parser/grammar/paths.rs b/src/parser/grammar/paths.rs
new file mode 100644
index 000000000..6efac2610
--- /dev/null
+++ b/src/parser/grammar/paths.rs
@@ -0,0 +1,49 @@
+use super::*;
+
+pub(super) fn is_path_start(p: &Parser) -> bool {
+    AnyOf(&[IDENT, SELF_KW, SUPER_KW, COLONCOLON]).is_ahead(p)
+}
+
+pub(super) fn use_path(p: &mut Parser) {
+    path(p)
+}
+
+pub(super) fn type_path(p: &mut Parser) {
+    path(p)
+}
+
+fn path(p: &mut Parser) {
+    if !is_path_start(p) {
+        return;
+    }
+    let path = p.start();
+    path_segment(p, true);
+    let mut qual = path.complete(p, PATH);
+    loop {
+        let use_tree = match p.nth(1) {
+            STAR | L_CURLY => true,
+            _ => false,
+        };
+        if p.at(COLONCOLON) && !use_tree {
+            let path = qual.precede(p);
+            p.bump();
+            path_segment(p, false);
+            let path = path.complete(p, PATH);
+            qual = path;
+        } else {
+            break;
+        }
+    }
+}
+
+fn path_segment(p: &mut Parser, first: bool) {
+    let segment = p.start();
+    if first {
+        p.eat(COLONCOLON);
+    }
+    match p.current() {
+        IDENT | SELF_KW | SUPER_KW => p.bump(),
+        _ => p.error().message("expected identifier").emit(),
+    };
+    segment.complete(p, PATH_SEGMENT);
+}
diff --git a/src/parser/grammar/type_params.rs b/src/parser/grammar/type_params.rs
new file mode 100644
index 000000000..12c9a5362
--- /dev/null
+++ b/src/parser/grammar/type_params.rs
@@ -0,0 +1,75 @@
+use super::*;
+
+pub(super) fn list(p: &mut Parser) {
+    if !p.at(L_ANGLE) {
+        return;
+    }
+    let m = p.start();
+    p.bump();
+
+    while !p.at(EOF) && !p.at(R_ANGLE) {
+        match p.current() {
+            LIFETIME => lifetime_param(p),
+            IDENT => type_param(p),
+            _ => p.err_and_bump("expected type parameter"),
+        }
+        if !p.at(R_ANGLE) && !p.expect(COMMA) {
+            break;
+        }
+    }
+    p.expect(R_ANGLE);
+    m.complete(p, TYPE_PARAM_LIST);
+
+    fn lifetime_param(p: &mut Parser) {
+        assert!(p.at(LIFETIME));
+        let m = p.start();
+        p.bump();
+        if p.eat(COLON) {
+            while p.at(LIFETIME) {
+                p.bump();
+                if !p.eat(PLUS) {
+                    break;
+                }
+            }
+        }
+        m.complete(p, LIFETIME_PARAM);
+    }
+
+    fn type_param(p: &mut Parser) {
+        assert!(p.at(IDENT));
+        let m = p.start();
+        p.bump();
+        if p.eat(COLON) {
+            loop {
+                let has_paren = p.eat(L_PAREN);
+                p.eat(QUESTION);
+                if p.at(FOR_KW) {
+                    //TODO
+                }
+                if p.at(LIFETIME) {
+                    p.bump();
+                } else if paths::is_path_start(p) {
+                    paths::type_path(p);
+                } else {
+                    break;
+                }
+                if has_paren {
+                    p.expect(R_PAREN);
+                }
+                if !p.eat(PLUS) {
+                    break;
+                }
+            }
+        }
+        if p.at(EQ) {
+            types::type_ref(p)
+        }
+        m.complete(p, TYPE_PARAM);
+    }
+}
+
+pub(super) fn where_clause(p: &mut Parser) {
+    if p.at(WHERE_KW) {
+        p.bump();
+    }
+}
diff --git a/src/parser/grammar/types.rs b/src/parser/grammar/types.rs
new file mode 100644
index 000000000..1a3d44a0a
--- /dev/null
+++ b/src/parser/grammar/types.rs
@@ -0,0 +1,5 @@
+use super::*;
+
+pub(super) fn type_ref(p: &mut Parser) {
+    p.expect(IDENT);
+}