Repository: rust-analyzer/rust-analyzer
Pull request #3933 (2020-04-10 19:16:16)

Fix accidently quadratic behavior when processing include!
This fixes the immediate problem behind #3927. It doesn't yet fix the deeper problem with `to_node` being quadratic (hence the test is ignored), but it is a good start anyway.

bors r+


Patch:
diff --git a/Cargo.lock b/Cargo.lock
index 34c5351623..20e7e745be 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -594,9 +594,9 @@ checksum = "ae91b68aebc4ddb91978b11a1b02ddd8602a05ec19002801c5666000e05e0f83"
 
 [[package]]
 name = "lock_api"
-version = "0.3.4"
+version = "0.3.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "c4da24a77a3d8a6d4862d95f72e6fdb9c09a643ecdb402d754004a557f2bec75"
+checksum = "79b2de95ecb4691949fea4716ca53cdbcfccb2c612e19644a8bad05edcf9f47b"
 dependencies = [
  "scopeguard",
 ]
@@ -759,9 +759,9 @@ checksum = "a86ed3f5f244b372d6b1a00b72ef7f8876d0bc6a78a4c9985c53614041512063"
 
 [[package]]
 name = "parking_lot"
-version = "0.10.1"
+version = "0.10.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "6fdfcb5f20930a79e326f7ec992a9fdb5b7bd809254b1e735bdd5a99f78bee0d"
+checksum = "92e98c49ab0b7ce5b222f2cc9193fc4efe11c6d0bd4f648e374684a6857b1cfc"
 dependencies = [
  "lock_api",
  "parking_lot_core",
@@ -769,9 +769,9 @@ dependencies = [
 
 [[package]]
 name = "parking_lot_core"
-version = "0.7.1"
+version = "0.7.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "0e136c1904604defe99ce5fd71a28d473fa60a12255d511aa78a9ddf11237aeb"
+checksum = "7582838484df45743c8434fbff785e8edf260c28748353d44bc0da32e0ceabf1"
 dependencies = [
  "cfg-if",
  "cloudabi",
@@ -1481,9 +1481,9 @@ checksum = "c111b5bd5695e56cffe5129854aa230b39c93a305372fdbb2668ca2394eea9f8"
 
 [[package]]
 name = "smallvec"
-version = "1.3.0"
+version = "1.2.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "05720e22615919e4734f6a99ceae50d00226c3c5aca406e102ebc33298214e0a"
+checksum = "5c2fb2ec9bcd216a5b0d0ccf31ab17b5ed1d627960edff65bbe95d3ce221cefc"
 
 [[package]]
 name = "smol_str"
@@ -1531,9 +1531,9 @@ dependencies = [
 
 [[package]]
 name = "termios"
-version = "0.3.2"
+version = "0.3.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "6f0fcee7b24a25675de40d5bb4de6e41b0df07bc9856295e7e2b3a3600c400c2"
+checksum = "72b620c5ea021d75a735c943269bb07d30c9b77d6ac6b236bc8b5c496ef05625"
 dependencies = [
  "libc",
 ]
diff --git a/crates/ra_mbe/src/syntax_bridge.rs b/crates/ra_mbe/src/syntax_bridge.rs
index 8e8ae2b294..9fb5cb0583 100644
--- a/crates/ra_mbe/src/syntax_bridge.rs
+++ b/crates/ra_mbe/src/syntax_bridge.rs
@@ -137,21 +137,23 @@ impl TokenMap {
         token_id: tt::TokenId,
         open_relative_range: TextRange,
         close_relative_range: TextRange,
-    ) {
+    ) -> usize {
+        let res = self.entries.len();
         self.entries
             .push((token_id, TokenTextRange::Delimiter(open_relative_range, close_relative_range)));
+        res
     }
 
-    fn update_close_delim(&mut self, token_id: tt::TokenId, close_relative_range: TextRange) {
-        if let Some(entry) = self.entries.iter_mut().find(|(tid, _)| *tid == token_id) {
-            if let TokenTextRange::Delimiter(dim, _) = entry.1 {
-                entry.1 = TokenTextRange::Delimiter(dim, close_relative_range);
-            }
+    fn update_close_delim(&mut self, idx: usize, close_relative_range: TextRange) {
+        let (_, token_text_range) = &mut self.entries[idx];
+        if let TokenTextRange::Delimiter(dim, _) = token_text_range {
+            *token_text_range = TokenTextRange::Delimiter(*dim, close_relative_range);
         }
     }
 
-    fn remove_delim(&mut self, token_id: tt::TokenId) {
-        self.entries.retain(|(tid, _)| *tid != token_id);
+    fn remove_delim(&mut self, idx: usize) {
+        // FIXME: This could be accidently quadratic
+        self.entries.remove(idx);
     }
 }
 
@@ -238,24 +240,24 @@ impl TokenIdAlloc {
         token_id
     }
 
-    fn open_delim(&mut self, open_abs_range: TextRange) -> tt::TokenId {
+    fn open_delim(&mut self, open_abs_range: TextRange) -> (tt::TokenId, usize) {
         let token_id = tt::TokenId(self.next_id);
         self.next_id += 1;
-        self.map.insert_delim(
+        let idx = self.map.insert_delim(
             token_id,
             open_abs_range - self.global_offset,
             open_abs_range - self.global_offset,
         );
-        token_id
+        (token_id, idx)
     }
 
-    fn close_delim(&mut self, id: tt::TokenId, close_abs_range: Option<TextRange>) {
+    fn close_delim(&mut self, idx: usize, close_abs_range: Option<TextRange>) {
         match close_abs_range {
             None => {
-                self.map.remove_delim(id);
+                self.map.remove_delim(idx);
             }
             Some(close) => {
-                self.map.update_close_delim(id, close - self.global_offset);
+                self.map.update_close_delim(idx, close - self.global_offset);
             }
         }
     }
@@ -322,7 +324,7 @@ trait TokenConvertor {
 
             if let Some((kind, closed)) = delim {
                 let mut subtree = tt::Subtree::default();
-                let id = self.id_alloc().open_delim(range);
+                let (id, idx) = self.id_alloc().open_delim(range);
                 subtree.delimiter = Some(tt::Delimiter { kind, id });
 
                 while self.peek().map(|it| it.kind() != closed).unwrap_or(false) {
@@ -331,7 +333,7 @@ trait TokenConvertor {
                 let last_range = match self.bump() {
                     None => {
                         // For error resilience, we insert an char punct for the opening delim here
-                        self.id_alloc().close_delim(id, None);
+                        self.id_alloc().close_delim(idx, None);
                         let leaf: tt::Leaf = tt::Punct {
                             id: self.id_alloc().alloc(range),
                             char: token.to_char().unwrap(),
@@ -344,7 +346,7 @@ trait TokenConvertor {
                     }
                     Some(it) => it.1,
                 };
-                self.id_alloc().close_delim(id, Some(last_range));
+                self.id_alloc().close_delim(idx, Some(last_range));
                 subtree.into()
             } else {
                 let spacing = match self.peek() {
diff --git a/crates/ra_prof/src/lib.rs b/crates/ra_prof/src/lib.rs
index 00ea3a9b06..2d4f68f5e0 100644
--- a/crates/ra_prof/src/lib.rs
+++ b/crates/ra_prof/src/lib.rs
@@ -113,21 +113,6 @@ pub fn profile(label: Label) -> Profiler {
     })
 }
 
-pub fn print_time(label: Label) -> impl Drop {
-    struct Guard {
-        label: Label,
-        start: Instant,
-    }
-
-    impl Drop for Guard {
-        fn drop(&mut self) {
-            eprintln!("{}: {:?}", self.label, self.start.elapsed())
-        }
-    }
-
-    Guard { label, start: Instant::now() }
-}
-
 pub struct Profiler {
     label: Option<Label>,
     detail: Option<String>,
diff --git a/crates/stdx/src/lib.rs b/crates/stdx/src/lib.rs
index 401a568bd5..01cdf452c2 100644
--- a/crates/stdx/src/lib.rs
+++ b/crates/stdx/src/lib.rs
@@ -1,6 +1,6 @@
 //! Missing batteries for standard libraries.
 
-use std::{cell::Cell, fmt};
+use std::{cell::Cell, fmt, time::Instant};
 
 #[inline(always)]
 pub fn is_ci() -> bool {
@@ -88,3 +88,17 @@ where
         Ok(())
     }
 }
+pub fn timeit(label: &'static str) -> impl Drop {
+    struct Guard {
+        label: &'static str,
+        start: Instant,
+    }
+
+    impl Drop for Guard {
+        fn drop(&mut self) {
+            eprintln!("{}: {:?}", self.label, self.start.elapsed())
+        }
+    }
+
+    Guard { label, start: Instant::now() }
+}


Test patch:
diff --git a/crates/ra_hir_ty/src/tests/macros.rs b/crates/ra_hir_ty/src/tests/macros.rs
index ff4599b712..f2a9b1c408 100644
--- a/crates/ra_hir_ty/src/tests/macros.rs
+++ b/crates/ra_hir_ty/src/tests/macros.rs
@@ -1,10 +1,13 @@
+use std::fs;
+
 use insta::assert_snapshot;
 use ra_db::fixture::WithFixture;
-
-use super::{infer, type_at, type_at_pos};
+use test_utils::project_dir;
 
 use crate::test_db::TestDB;
 
+use super::{infer, type_at, type_at_pos};
+
 #[test]
 fn cfg_impl_def() {
     let (db, pos) = TestDB::with_position(
@@ -481,6 +484,30 @@ fn bar() -> u32 {0}
     assert_eq!("u32", type_at_pos(&db, pos));
 }
 
+#[test]
+#[ignore]
+fn include_accidentally_quadratic() {
+    let file = project_dir().join("crates/ra_syntax/test_data/accidentally_quadratic");
+    let big_file = fs::read_to_string(file).unwrap();
+    let big_file = vec![big_file; 10].join("\n");
+
+    let fixture = r#"
+//- /main.rs
+#[rustc_builtin_macro]
+macro_rules! include {() => {}}
+
+include!("foo.rs");
+
+fn main() {
+    RegisterBlock { }<|>;
+}
+    "#;
+    let fixture = format!("{}\n//- /foo.rs\n{}", fixture, big_file);
+
+    let (db, pos) = TestDB::with_position(&fixture);
+    assert_eq!("RegisterBlock", type_at_pos(&db, pos));
+}
+
 #[test]
 fn infer_builtin_macros_include_concat() {
     let (db, pos) = TestDB::with_position(