G: use trees

13 files changed, 319 insertions, 93 deletions

diff --git a/grammar.ron b/grammar.ron
index ca6299f23..fe0ec8406 100644
--- a/grammar.ron
+++ b/grammar.ron
@@ -80,6 +80,7 @@ Grammar(
         "META_ITEM",
         "MOD_ITEM",
         "USE_ITEM",
+        "USE_TREE",
         "PATH",
         "PATH_SEGMENT",
         "LITERAL",
diff --git a/src/parser/event_parser/grammar/items.rs b/src/parser/event_parser/grammar/items.rs
index f7310c09a..2f64111ab 100644
--- a/src/parser/event_parser/grammar/items.rs
+++ b/src/parser/event_parser/grammar/items.rs
@@ -74,9 +74,63 @@ fn mod_item(p: &mut Parser) {
     p.curly_block(mod_contents);
 }
 
+pub(super) fn is_use_tree_start(kind: SyntaxKind) -> bool {
+    kind == STAR || kind == L_CURLY
+}
+
 fn use_item(p: &mut Parser) {
-    paths::use_path(p);
+    use_tree(p);
     p.expect(SEMI);
+
+    fn use_tree(p: &mut Parser) -> bool{
+        if node_if(p, STAR, USE_TREE, |_| ()) {
+            return true
+        }
+        if node_if(p, [COLONCOLON, STAR], USE_TREE, |_| ()) {
+           return true
+        }
+        if [COLONCOLON, L_CURLY].is_ahead(p) || L_CURLY.is_ahead(p) {
+            node(p, USE_TREE, |p| {
+                p.eat(COLONCOLON);
+                p.curly_block(|p| {
+                    comma_list(p, EOF, use_tree);
+                });
+            });
+            return true;
+        }
+        if paths::is_path_start(p) {
+            node(p, USE_TREE, |p| {
+                paths::use_path(p);
+                match p.current() {
+                    AS_KW => {
+                        alias(p);
+                    }
+                    COLONCOLON => {
+                        p.bump();
+                        match p.current() {
+                            STAR => {
+                                p.bump();
+                            }
+                            L_CURLY => {
+                                p.curly_block(|p| {
+                                    comma_list(p, EOF, use_tree);
+                                });
+                            }
+                            _ => {
+                                // is this unreachable?
+                                p.error()
+                                    .message("expected `{` or `*`")
+                                    .emit();
+                            }
+                        }
+                    }
+                    _ => (),
+                }
+            });
+            return true;
+        }
+        false
+    }
 }
 
 fn struct_field(p: &mut Parser) -> bool {
diff --git a/src/parser/event_parser/grammar/paths.rs b/src/parser/event_parser/grammar/paths.rs
index d6887a9ba..62d1a3bb2 100644
--- a/src/parser/event_parser/grammar/paths.rs
+++ b/src/parser/event_parser/grammar/paths.rs
@@ -1,7 +1,11 @@
 use super::*;
 
+pub (crate) fn is_path_start(p: &Parser) -> bool {
+    AnyOf(&[IDENT, SELF_KW, SUPER_KW, COLONCOLON]).is_ahead(p)
+}
+
 pub(crate) fn use_path(p: &mut Parser) {
-    if !AnyOf(&[IDENT, SELF_KW, SUPER_KW, COLONCOLON]).is_ahead(p) {
+    if !is_path_start(p) {
         return;
     }
     let mut prev = p.mark();
@@ -10,11 +14,17 @@ pub(crate) fn use_path(p: &mut Parser) {
     });
     many(p, |p| {
         let curr = p.mark();
-        node_if(p, COLONCOLON, PATH, |p| {
-            path_segment(p, false);
-            p.forward_parent(prev, curr);
-            prev = curr;
-        })
+        if p.current() == COLONCOLON && !items::is_use_tree_start(p.raw_lookahead(1)) {
+            node(p, PATH, |p| {
+                p.bump();
+                path_segment(p, false);
+                p.forward_parent(prev, curr);
+                prev = curr;
+            });
+            true
+        } else {
+            false
+        }
     });
 }
 
diff --git a/src/parser/mod.rs b/src/parser/mod.rs
index c08d32d08..0c29442f9 100644
--- a/src/parser/mod.rs
+++ b/src/parser/mod.rs
@@ -29,7 +29,7 @@ fn from_events_to_file(
         }
 
         match event {
-            &Event::Start { kind, forward_parent } => {
+            &Event::Start { .. } => {
                 forward_parents.clear();
                 let mut idx = i;
                 loop {
diff --git a/src/syntax_kinds.rs b/src/syntax_kinds.rs
index 48f55fa97..8bc63a210 100644
--- a/src/syntax_kinds.rs
+++ b/src/syntax_kinds.rs
@@ -77,13 +77,14 @@ pub const ATTR: SyntaxKind = SyntaxKind(72);
 pub const META_ITEM: SyntaxKind = SyntaxKind(73);
 pub const MOD_ITEM: SyntaxKind = SyntaxKind(74);
 pub const USE_ITEM: SyntaxKind = SyntaxKind(75);
-pub const PATH: SyntaxKind = SyntaxKind(76);
-pub const PATH_SEGMENT: SyntaxKind = SyntaxKind(77);
-pub const LITERAL: SyntaxKind = SyntaxKind(78);
-pub const ALIAS: SyntaxKind = SyntaxKind(79);
-pub const VISIBILITY: SyntaxKind = SyntaxKind(80);
+pub const USE_TREE: SyntaxKind = SyntaxKind(76);
+pub const PATH: SyntaxKind = SyntaxKind(77);
+pub const PATH_SEGMENT: SyntaxKind = SyntaxKind(78);
+pub const LITERAL: SyntaxKind = SyntaxKind(79);
+pub const ALIAS: SyntaxKind = SyntaxKind(80);
+pub const VISIBILITY: SyntaxKind = SyntaxKind(81);
 
-static INFOS: [SyntaxInfo; 81] = [
+static INFOS: [SyntaxInfo; 82] = [
     SyntaxInfo { name: "USE_KW" },
     SyntaxInfo { name: "FN_KW" },
     SyntaxInfo { name: "STRUCT_KW" },
@@ -160,6 +161,7 @@ static INFOS: [SyntaxInfo; 81] = [
     SyntaxInfo { name: "META_ITEM" },
     SyntaxInfo { name: "MOD_ITEM" },
     SyntaxInfo { name: "USE_ITEM" },
+    SyntaxInfo { name: "USE_TREE" },
     SyntaxInfo { name: "PATH" },
     SyntaxInfo { name: "PATH_SEGMENT" },
     SyntaxInfo { name: "LITERAL" },
diff --git a/tests/data/parser/err/0004_use_path_bad_segment.txt b/tests/data/parser/err/0004_use_path_bad_segment.txt
index 241ee8562..cd7e86d68 100644
--- a/tests/data/parser/err/0004_use_path_bad_segment.txt
+++ b/tests/data/parser/err/0004_use_path_bad_segment.txt
@@ -1,14 +1,15 @@
 FILE@[0; 12)
   USE_ITEM@[0; 9)
     USE_KW@[0; 3)
-    PATH@[3; 9)
-      PATH@[3; 7)
-        PATH_SEGMENT@[3; 7)
-          WHITESPACE@[3; 4)
-          IDENT@[4; 7)
-      COLONCOLON@[7; 9)
-      PATH_SEGMENT@[9; 9)
-      err: `expected identifier`
+    USE_TREE@[3; 9)
+      PATH@[3; 9)
+        PATH@[3; 7)
+          PATH_SEGMENT@[3; 7)
+            WHITESPACE@[3; 4)
+            IDENT@[4; 7)
+        COLONCOLON@[7; 9)
+        PATH_SEGMENT@[9; 9)
+        err: `expected identifier`
     err: `expected SEMI`
   ERROR@[9; 12)
   err: `expected item`
diff --git a/tests/data/parser/ok/0009_use_item.txt b/tests/data/parser/ok/0009_use_item.txt
index f15c30940..63274125d 100644
--- a/tests/data/parser/ok/0009_use_item.txt
+++ b/tests/data/parser/ok/0009_use_item.txt
@@ -1,17 +1,19 @@
 FILE@[0; 19)
   USE_ITEM@[0; 9)
     USE_KW@[0; 3)
-    PATH@[3; 7)
-      PATH_SEGMENT@[3; 7)
-        WHITESPACE@[3; 4)
-        IDENT@[4; 7)
+    USE_TREE@[3; 7)
+      PATH@[3; 7)
+        PATH_SEGMENT@[3; 7)
+          WHITESPACE@[3; 4)
+          IDENT@[4; 7)
     SEMI@[7; 8)
     WHITESPACE@[8; 9)
   USE_ITEM@[9; 19)
     USE_KW@[9; 12)
-    PATH@[12; 18)
-      PATH_SEGMENT@[12; 18)
-        WHITESPACE@[12; 13)
-        COLONCOLON@[13; 15)
-        IDENT@[15; 18)
+    USE_TREE@[12; 18)
+      PATH@[12; 18)
+        PATH_SEGMENT@[12; 18)
+          WHITESPACE@[12; 13)
+          COLONCOLON@[13; 15)
+          IDENT@[15; 18)
     SEMI@[18; 19)
diff --git a/tests/data/parser/ok/0010_use_path_segments.txt b/tests/data/parser/ok/0010_use_path_segments.txt
index a407be826..d0f2033ce 100644
--- a/tests/data/parser/ok/0010_use_path_segments.txt
+++ b/tests/data/parser/ok/0010_use_path_segments.txt
@@ -1,34 +1,36 @@
 FILE@[0; 40)
   USE_ITEM@[0; 21)
     USE_KW@[0; 3)
-    PATH@[3; 19)
-      PATH@[3; 14)
-        PATH@[3; 9)
-          PATH_SEGMENT@[3; 9)
-            WHITESPACE@[3; 4)
-            COLONCOLON@[4; 6)
-            IDENT@[6; 9)
-        COLONCOLON@[9; 11)
-        PATH_SEGMENT@[11; 14)
-          IDENT@[11; 14)
-      COLONCOLON@[14; 16)
-      PATH_SEGMENT@[16; 19)
-        IDENT@[16; 19)
+    USE_TREE@[3; 19)
+      PATH@[3; 19)
+        PATH@[3; 14)
+          PATH@[3; 9)
+            PATH_SEGMENT@[3; 9)
+              WHITESPACE@[3; 4)
+              COLONCOLON@[4; 6)
+              IDENT@[6; 9)
+          COLONCOLON@[9; 11)
+          PATH_SEGMENT@[11; 14)
+            IDENT@[11; 14)
+        COLONCOLON@[14; 16)
+        PATH_SEGMENT@[16; 19)
+          IDENT@[16; 19)
     SEMI@[19; 20)
     WHITESPACE@[20; 21)
   USE_ITEM@[21; 40)
     USE_KW@[21; 24)
-    PATH@[24; 38)
-      PATH@[24; 33)
-        PATH@[24; 28)
-          PATH_SEGMENT@[24; 28)
-            WHITESPACE@[24; 25)
-            IDENT@[25; 28)
-        COLONCOLON@[28; 30)
-        PATH_SEGMENT@[30; 33)
-          IDENT@[30; 33)
-      COLONCOLON@[33; 35)
-      PATH_SEGMENT@[35; 38)
-        IDENT@[35; 38)
+    USE_TREE@[24; 38)
+      PATH@[24; 38)
+        PATH@[24; 33)
+          PATH@[24; 28)
+            PATH_SEGMENT@[24; 28)
+              WHITESPACE@[24; 25)
+              IDENT@[25; 28)
+          COLONCOLON@[28; 30)
+          PATH_SEGMENT@[30; 33)
+            IDENT@[30; 33)
+        COLONCOLON@[33; 35)
+        PATH_SEGMENT@[35; 38)
+          IDENT@[35; 38)
     SEMI@[38; 39)
     WHITESPACE@[39; 40)
diff --git a/tests/data/parser/ok/0013_use_path_self_super.txt b/tests/data/parser/ok/0013_use_path_self_super.txt
index 90bbb9b2d..2b0934e97 100644
--- a/tests/data/parser/ok/0013_use_path_self_super.txt
+++ b/tests/data/parser/ok/0013_use_path_self_super.txt
@@ -1,50 +1,53 @@
 FILE@[0; 65)
   USE_ITEM@[0; 15)
     USE_KW@[0; 3)
-    PATH@[3; 13)
-      PATH@[3; 8)
-        PATH_SEGMENT@[3; 8)
-          WHITESPACE@[3; 4)
-          SELF_KW@[4; 8)
-      COLONCOLON@[8; 10)
-      PATH_SEGMENT@[10; 13)
-        IDENT@[10; 13)
+    USE_TREE@[3; 13)
+      PATH@[3; 13)
+        PATH@[3; 8)
+          PATH_SEGMENT@[3; 8)
+            WHITESPACE@[3; 4)
+            SELF_KW@[4; 8)
+        COLONCOLON@[8; 10)
+        PATH_SEGMENT@[10; 13)
+          IDENT@[10; 13)
     SEMI@[13; 14)
     WHITESPACE@[14; 15)
   USE_ITEM@[15; 38)
     USE_KW@[15; 18)
-    PATH@[18; 36)
-      PATH@[18; 31)
-        PATH@[18; 24)
-          PATH_SEGMENT@[18; 24)
-            WHITESPACE@[18; 19)
-            SUPER_KW@[19; 24)
-        COLONCOLON@[24; 26)
-        PATH_SEGMENT@[26; 31)
-          SUPER_KW@[26; 31)
-      COLONCOLON@[31; 33)
-      PATH_SEGMENT@[33; 36)
-        IDENT@[33; 36)
+    USE_TREE@[18; 36)
+      PATH@[18; 36)
+        PATH@[18; 31)
+          PATH@[18; 24)
+            PATH_SEGMENT@[18; 24)
+              WHITESPACE@[18; 19)
+              SUPER_KW@[19; 24)
+          COLONCOLON@[24; 26)
+          PATH_SEGMENT@[26; 31)
+            SUPER_KW@[26; 31)
+        COLONCOLON@[31; 33)
+        PATH_SEGMENT@[33; 36)
+          IDENT@[33; 36)
     SEMI@[36; 37)
     WHITESPACE@[37; 38)
   USE_ITEM@[38; 65)
     USE_KW@[38; 41)
-    PATH@[41; 63)
-      PATH@[41; 58)
-        PATH@[41; 51)
-          PATH@[41; 48)
-            PATH_SEGMENT@[41; 48)
-              WHITESPACE@[41; 42)
-              COLONCOLON@[42; 44)
-              SELF_KW@[44; 48)
-          COLONCOLON@[48; 50)
-          PATH_SEGMENT@[50; 51)
-            IDENT@[50; 51)
-        COLONCOLON@[51; 53)
-        PATH_SEGMENT@[53; 58)
-          SUPER_KW@[53; 58)
-      COLONCOLON@[58; 60)
-      PATH_SEGMENT@[60; 63)
-        IDENT@[60; 63)
+    USE_TREE@[41; 63)
+      PATH@[41; 63)
+        PATH@[41; 58)
+          PATH@[41; 51)
+            PATH@[41; 48)
+              PATH_SEGMENT@[41; 48)
+                WHITESPACE@[41; 42)
+                COLONCOLON@[42; 44)
+                SELF_KW@[44; 48)
+            COLONCOLON@[48; 50)
+            PATH_SEGMENT@[50; 51)
+              IDENT@[50; 51)
+          COLONCOLON@[51; 53)
+          PATH_SEGMENT@[53; 58)
+            SUPER_KW@[53; 58)
+        COLONCOLON@[58; 60)
+        PATH_SEGMENT@[60; 63)
+          IDENT@[60; 63)
     SEMI@[63; 64)
     WHITESPACE@[64; 65)
diff --git a/tests/data/parser/ok/0014_use_tree.rs b/tests/data/parser/ok/0014_use_tree.rs
new file mode 100644
index 000000000..5e4aa3a33
--- /dev/null
+++ b/tests/data/parser/ok/0014_use_tree.rs
@@ -0,0 +1,7 @@
+use *;
+use ::*;
+use ::{};
+use {};
+use foo::*;
+use foo::{};
+use ::foo::{a, b, c};
diff --git a/tests/data/parser/ok/0014_use_tree.txt b/tests/data/parser/ok/0014_use_tree.txt
new file mode 100644
index 000000000..ca91e63e1
--- /dev/null
+++ b/tests/data/parser/ok/0014_use_tree.txt
@@ -0,0 +1,85 @@
+FILE@[0; 81)
+  USE_ITEM@[0; 7)
+    USE_KW@[0; 3)
+    USE_TREE@[3; 5)
+      WHITESPACE@[3; 4)
+      STAR@[4; 5)
+    SEMI@[5; 6)
+    WHITESPACE@[6; 7)
+  USE_ITEM@[7; 16)
+    USE_KW@[7; 10)
+    USE_TREE@[10; 14)
+      WHITESPACE@[10; 11)
+      COLONCOLON@[11; 13)
+      STAR@[13; 14)
+    SEMI@[14; 15)
+    WHITESPACE@[15; 16)
+  USE_ITEM@[16; 26)
+    USE_KW@[16; 19)
+    USE_TREE@[19; 24)
+      WHITESPACE@[19; 20)
+      COLONCOLON@[20; 22)
+      L_CURLY@[22; 23)
+      R_CURLY@[23; 24)
+    SEMI@[24; 25)
+    WHITESPACE@[25; 26)
+  USE_ITEM@[26; 34)
+    USE_KW@[26; 29)
+    USE_TREE@[29; 32)
+      WHITESPACE@[29; 30)
+      L_CURLY@[30; 31)
+      R_CURLY@[31; 32)
+    SEMI@[32; 33)
+    WHITESPACE@[33; 34)
+  USE_ITEM@[34; 46)
+    USE_KW@[34; 37)
+    USE_TREE@[37; 44)
+      PATH@[37; 41)
+        PATH_SEGMENT@[37; 41)
+          WHITESPACE@[37; 38)
+          IDENT@[38; 41)
+      COLONCOLON@[41; 43)
+      STAR@[43; 44)
+    SEMI@[44; 45)
+    WHITESPACE@[45; 46)
+  USE_ITEM@[46; 59)
+    USE_KW@[46; 49)
+    USE_TREE@[49; 57)
+      PATH@[49; 53)
+        PATH_SEGMENT@[49; 53)
+          WHITESPACE@[49; 50)
+          IDENT@[50; 53)
+      COLONCOLON@[53; 55)
+      L_CURLY@[55; 56)
+      R_CURLY@[56; 57)
+    SEMI@[57; 58)
+    WHITESPACE@[58; 59)
+  USE_ITEM@[59; 81)
+    USE_KW@[59; 62)
+    USE_TREE@[62; 79)
+      PATH@[62; 68)
+        PATH_SEGMENT@[62; 68)
+          WHITESPACE@[62; 63)
+          COLONCOLON@[63; 65)
+          IDENT@[65; 68)
+      COLONCOLON@[68; 70)
+      L_CURLY@[70; 71)
+      USE_TREE@[71; 72)
+        PATH@[71; 72)
+          PATH_SEGMENT@[71; 72)
+            IDENT@[71; 72)
+      COMMA@[72; 73)
+      USE_TREE@[73; 75)
+        PATH@[73; 75)
+          PATH_SEGMENT@[73; 75)
+            WHITESPACE@[73; 74)
+            IDENT@[74; 75)
+      COMMA@[75; 76)
+      USE_TREE@[76; 78)
+        PATH@[76; 78)
+          PATH_SEGMENT@[76; 78)
+            WHITESPACE@[76; 77)
+            IDENT@[77; 78)
+      R_CURLY@[78; 79)
+    SEMI@[79; 80)
+    WHITESPACE@[80; 81)
diff --git a/tests/data/parser/ok/0015_use_tree.rs b/tests/data/parser/ok/0015_use_tree.rs
new file mode 100644
index 000000000..46a0783a2
--- /dev/null
+++ b/tests/data/parser/ok/0015_use_tree.rs
@@ -0,0 +1,2 @@
+use foo as bar;
+use foo::{a as b, *, ::*, ::foo as x};
diff --git a/tests/data/parser/ok/0015_use_tree.txt b/tests/data/parser/ok/0015_use_tree.txt
new file mode 100644
index 000000000..c1975f6cb
--- /dev/null
+++ b/tests/data/parser/ok/0015_use_tree.txt
@@ -0,0 +1,57 @@
+FILE@[0; 55)
+  USE_ITEM@[0; 16)
+    USE_KW@[0; 3)
+    USE_TREE@[3; 14)
+      PATH@[3; 8)
+        PATH_SEGMENT@[3; 8)
+          WHITESPACE@[3; 4)
+          IDENT@[4; 7)
+          WHITESPACE@[7; 8)
+      ALIAS@[8; 14)
+        AS_KW@[8; 10)
+        WHITESPACE@[10; 11)
+        IDENT@[11; 14)
+    SEMI@[14; 15)
+    WHITESPACE@[15; 16)
+  USE_ITEM@[16; 55)
+    USE_KW@[16; 19)
+    USE_TREE@[19; 53)
+      PATH@[19; 23)
+        PATH_SEGMENT@[19; 23)
+          WHITESPACE@[19; 20)
+          IDENT@[20; 23)
+      COLONCOLON@[23; 25)
+      L_CURLY@[25; 26)
+      USE_TREE@[26; 32)
+        PATH@[26; 28)
+          PATH_SEGMENT@[26; 28)
+            IDENT@[26; 27)
+            WHITESPACE@[27; 28)
+        ALIAS@[28; 32)
+          AS_KW@[28; 30)
+          WHITESPACE@[30; 31)
+          IDENT@[31; 32)
+      COMMA@[32; 33)
+      USE_TREE@[33; 35)
+        WHITESPACE@[33; 34)
+        STAR@[34; 35)
+      COMMA@[35; 36)
+      USE_TREE@[36; 40)
+        WHITESPACE@[36; 37)
+        COLONCOLON@[37; 39)
+        STAR@[39; 40)
+      COMMA@[40; 41)
+      USE_TREE@[41; 52)
+        PATH@[41; 48)
+          PATH_SEGMENT@[41; 48)
+            WHITESPACE@[41; 42)
+            COLONCOLON@[42; 44)
+            IDENT@[44; 47)
+            WHITESPACE@[47; 48)
+        ALIAS@[48; 52)
+          AS_KW@[48; 50)
+          WHITESPACE@[50; 51)
+          IDENT@[51; 52)
+      R_CURLY@[52; 53)
+    SEMI@[53; 54)
+    WHITESPACE@[54; 55)