Support tree rebalancing

5 files changed, 86 insertions, 29 deletions

diff --git a/src/parser/event_parser/grammar/items.rs b/src/parser/event_parser/grammar/items.rs
index 522986ed0..725f04d1e 100644
--- a/src/parser/event_parser/grammar/items.rs
+++ b/src/parser/event_parser/grammar/items.rs
@@ -32,6 +32,7 @@ fn mod_contents_item(p: &mut Parser) {
 }
 
 fn item(p: &mut Parser) -> bool {
+    let attrs_start = p.mark();
     attributes::outer_attributes(p);
     visibility(p);
     //    node_if(p, USE_KW, USE_ITEM, use_item)
@@ -41,11 +42,17 @@ fn item(p: &mut Parser) -> bool {
     // || unsafe trait, impl
     // || node_if(p, FN_KW, FN_ITEM, fn_item)
     // || node_if(p, TYPE_KW, TYPE_ITEM, type_item)
-    node_if(p, [EXTERN_KW, CRATE_KW], EXTERN_CRATE_ITEM, extern_crate_item)
+    let item_start = p.mark();
+    let item_parsed = node_if(p, [EXTERN_KW, CRATE_KW], EXTERN_CRATE_ITEM, extern_crate_item)
         || node_if(p, MOD_KW, MOD_ITEM, mod_item)
         || node_if(p, USE_KW, USE_ITEM, use_item)
         || node_if(p, STRUCT_KW, STRUCT_ITEM, struct_item)
-        || node_if(p, FN_KW, FN_ITEM, fn_item)
+        || node_if(p, FN_KW, FN_ITEM, fn_item);
+
+    if item_parsed && attrs_start != item_start {
+        p.forward_parent(attrs_start, item_start);
+    }
+    item_parsed
 }
 
 fn struct_item(p: &mut Parser) {
diff --git a/src/parser/event_parser/mod.rs b/src/parser/event_parser/mod.rs
index 87b317c84..c89a3ebe7 100644
--- a/src/parser/event_parser/mod.rs
+++ b/src/parser/event_parser/mod.rs
@@ -5,7 +5,10 @@ mod parser;
 
 #[derive(Debug)]
 pub(crate) enum Event {
-    Start { kind: SyntaxKind },
+    Start {
+        kind: SyntaxKind,
+        forward_parent: Option<u32>,
+    },
     Finish,
     Token {
         kind: SyntaxKind,
diff --git a/src/parser/event_parser/parser.rs b/src/parser/event_parser/parser.rs
index 8bc382b12..14c0efe2d 100644
--- a/src/parser/event_parser/parser.rs
+++ b/src/parser/event_parser/parser.rs
@@ -22,6 +22,9 @@ pub(crate) struct Parser<'t> {
 #[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();
@@ -47,6 +50,21 @@ 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) {
+        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)
     }
@@ -71,7 +89,7 @@ impl<'t> Parser<'t> {
     }
 
     pub(crate) fn start(&mut self, kind: SyntaxKind) {
-        self.event(Event::Start { kind });
+        self.event(Event::Start { kind, forward_parent: None });
     }
 
     pub(crate) fn finish(&mut self) {
diff --git a/src/parser/mod.rs b/src/parser/mod.rs
index 742755142..c08d32d08 100644
--- a/src/parser/mod.rs
+++ b/src/parser/mod.rs
@@ -18,10 +18,39 @@ fn from_events_to_file(
 ) -> File {
     let mut builder = FileBuilder::new(text);
     let mut idx = 0;
-    for event in events {
+
+    let mut holes = Vec::new();
+    let mut forward_parents = Vec::new();
+
+    for (i, event) in events.iter().enumerate() {
+        if holes.last() == Some(&i) {
+            holes.pop();
+            continue
+        }
+
         match event {
-            Event::Start { kind } => builder.start_internal(kind),
-            Event::Finish => {
+            &Event::Start { kind, forward_parent } => {
+                forward_parents.clear();
+                let mut idx = i;
+                loop {
+                    let (kind, fwd) = match events[idx] {
+                        Event::Start { kind, forward_parent } => (kind, forward_parent),
+                        _ => unreachable!(),
+                    };
+                    forward_parents.push((idx, kind));
+                    if let Some(fwd) = fwd {
+                        idx += fwd as usize;
+                    } else {
+                        break;
+                    }
+                }
+                for &(idx, kind) in forward_parents.iter().into_iter().rev() {
+                    builder.start_internal(kind);
+                    holes.push(idx);
+                }
+                holes.pop();
+            }
+            &Event::Finish => {
                 while idx < tokens.len() {
                     let token = tokens[idx];
                     if is_insignificant(token.kind) {
@@ -33,7 +62,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;
@@ -44,8 +73,8 @@ fn from_events_to_file(
                     break;
                 }
             },
-            Event::Error { message } => builder.error().message(message).emit(),
-
+            &Event::Error { ref message } =>
+                builder.error().message(message.clone()).emit(),
         }
     }
     builder.finish()
diff --git a/tests/data/parser/ok/0011_outer_attribute.txt b/tests/data/parser/ok/0011_outer_attribute.txt
index a790f4095..0f69b1f66 100644
--- a/tests/data/parser/ok/0011_outer_attribute.txt
+++ b/tests/data/parser/ok/0011_outer_attribute.txt
@@ -1,23 +1,23 @@
 FILE@[0; 35)
-  ATTR@[0; 13)
-    POUND@[0; 1)
-    L_BRACK@[1; 2)
-    META_ITEM@[2; 11)
-      IDENT@[2; 5)
-      L_PAREN@[5; 6)
-      META_ITEM@[6; 10)
-        IDENT@[6; 10)
-      R_PAREN@[10; 11)
-    R_BRACK@[11; 12)
-    WHITESPACE@[12; 13)
-  ATTR@[13; 23)
-    POUND@[13; 14)
-    L_BRACK@[14; 15)
-    META_ITEM@[15; 21)
-      IDENT@[15; 21)
-    R_BRACK@[21; 22)
-    WHITESPACE@[22; 23)
-  FN_ITEM@[23; 35)
+  FN_ITEM@[0; 35)
+    ATTR@[0; 13)
+      POUND@[0; 1)
+      L_BRACK@[1; 2)
+      META_ITEM@[2; 11)
+        IDENT@[2; 5)
+        L_PAREN@[5; 6)
+        META_ITEM@[6; 10)
+          IDENT@[6; 10)
+        R_PAREN@[10; 11)
+      R_BRACK@[11; 12)
+      WHITESPACE@[12; 13)
+    ATTR@[13; 23)
+      POUND@[13; 14)
+      L_BRACK@[14; 15)
+      META_ITEM@[15; 21)
+        IDENT@[15; 21)
+      R_BRACK@[21; 22)
+      WHITESPACE@[22; 23)
     FN_KW@[23; 25)
     WHITESPACE@[25; 26)
     IDENT@[26; 29)