Merge #774

774: Batch crate & command r=matklad a=flodiebold

This adds a new crate, `ra_batch`, which is intended for scenarios where you're loading a workspace once and then running some analyses using the HIR API. Also, it adds a command to `ra_cli` which uses that to type-check all crates in a workspace and print some statistics:

E.g. in rust-analyzer:
```
> $ time target/release/ra_cli analysis-stats
Database loaded, 21 roots
Crates in this dir: 28
Total modules found: 231
Total declarations: 3694
Total functions: 2408
Total expressions: 47017
Expressions of unknown type: 19826 (42%)
Expressions of partially unknown type: 4482 (9%)
target/release/ra_cli analysis-stats  3,23s user 0,60s system 100% cpu 3,821 total
```

Or in rust-lang/rust:
```
> $ time ../opensource/rust-analyzer/target/release/ra_cli analysis-stats
Database loaded, 77 roots
Crates in this dir: 130
Total modules found: 1820
Total declarations: 35038
Total functions: 25914
Total expressions: 753678
Expressions of unknown type: 337975 (44%)
Expressions of partially unknown type: 92314 (12%)
../opensource/rust-analyzer/target/release/ra_cli analysis-stats  13,45s user 2,08s system 100% cpu 15,477 total
```

~This still needs a test. Type-checking all of rust-analyzer sadly takes almost a minute when compiled in debug mode :sweat_smile: So I'll need to add something simpler (maybe just looking at a few modules).~

Co-authored-by: Florian Diebold <[email protected]>

12 files changed, 429 insertions, 6 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 0009cdaab..0a5bec2bf 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -487,6 +487,18 @@ version = "1.0.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "indicatif"
+version = "0.11.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "console 0.7.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "lazy_static 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "number_prefix 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)",
+ "parking_lot 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "regex 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "inotify"
 version = "0.6.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -781,6 +793,14 @@ dependencies = [
 ]
 
 [[package]]
+name = "number_prefix"
+version = "0.2.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "owning_ref"
 version = "0.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -910,12 +930,32 @@ dependencies = [
 ]
 
 [[package]]
+name = "ra_batch"
+version = "0.1.0"
+dependencies = [
+ "failure 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
+ "ra_db 0.1.0",
+ "ra_hir 0.1.0",
+ "ra_project_model 0.1.0",
+ "ra_syntax 0.1.0",
+ "ra_vfs 0.1.0",
+ "rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "test_utils 0.1.0",
+]
+
+[[package]]
 name = "ra_cli"
 version = "0.1.0"
 dependencies = [
  "clap 2.32.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "failure 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "flexi_logger 0.10.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "indicatif 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "join_to_string 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)",
+ "ra_batch 0.1.0",
+ "ra_db 0.1.0",
+ "ra_hir 0.1.0",
  "ra_ide_api_light 0.1.0",
  "ra_syntax 0.1.0",
  "tools 0.1.0",
@@ -1934,6 +1974,7 @@ dependencies = [
 "checksum idna 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "38f09e0f0b1fb55fdee1f17470ad800da77af5186a1a76c026b679358b7e844e"
 "checksum im 12.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "0627d417829c1d763d602687634869f254fc79f7e22dea6c824dab993db857e4"
 "checksum indexmap 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7e81a7c05f79578dbc15793d8b619db9ba32b4577003ef3af1a91c416798c58d"
+"checksum indicatif 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "2c60da1c9abea75996b70a931bba6c750730399005b61ccd853cee50ef3d0d0c"
 "checksum inotify 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)" = "40b54539f3910d6f84fbf9a643efd6e3aa6e4f001426c0329576128255994718"
 "checksum inotify-sys 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "e74a1aa87c59aeff6ef2cc2fa62d41bc43f54952f55652656b18a02fd5e356c0"
 "checksum insta 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)" = "bcdfb5ab565a1fc5c397722d5a9503f2095696ef07ef1a222d85a0fd6666c6aa"
@@ -1967,6 +2008,7 @@ dependencies = [
 "checksum num-integer 0.1.39 (registry+https://github.com/rust-lang/crates.io-index)" = "e83d528d2677f0518c570baf2b7abdcf0cd2d248860b68507bdcb3e91d4c0cea"
 "checksum num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)" = "0b3a5d7cc97d6d30d8b9bc8fa19bf45349ffe46241e8816f50f62f6d6aaabee1"
 "checksum num_cpus 1.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5a69d464bdc213aaaff628444e99578ede64e9c854025aa43b9796530afa9238"
+"checksum number_prefix 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)" = "dbf9993e59c894e3c08aa1c2712914e9e6bf1fcbfc6bef283e2183df345a4fee"
 "checksum owning_ref 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "49a4b8ea2179e6a2e27411d3bca09ca6dd630821cf6894c6c7c8467a8ee7ef13"
 "checksum parking_lot 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ab41b4aed082705d1056416ae4468b6ea99d52599ecf3169b00088d43113e337"
 "checksum parking_lot_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "94c8c7923936b28d546dfd14d4472eaf34c99b14e1c973a32b3e6d4eb04298c9"
diff --git a/crates/ra_batch/Cargo.toml b/crates/ra_batch/Cargo.toml
new file mode 100644
index 000000000..30a0749c7
--- /dev/null
+++ b/crates/ra_batch/Cargo.toml
@@ -0,0 +1,20 @@
+[package]
+edition = "2018"
+name = "ra_batch"
+version = "0.1.0"
+authors = ["Aleksey Kladov <[email protected]>"]
+
+[dependencies]
+log = "0.4.5"
+rustc-hash = "1.0"
+
+failure = "0.1.4"
+
+ra_syntax = { path = "../ra_syntax" }
+ra_db = { path = "../ra_db" }
+ra_hir = { path = "../ra_hir" }
+ra_vfs = { path = "../ra_vfs" }
+ra_project_model = { path = "../ra_project_model" }
+
+[dev-dependencies]
+test_utils = { path = "../test_utils" }
diff --git a/crates/ra_batch/src/lib.rs b/crates/ra_batch/src/lib.rs
new file mode 100644
index 000000000..837fff4dc
--- /dev/null
+++ b/crates/ra_batch/src/lib.rs
@@ -0,0 +1,151 @@
+use std::sync::Arc;
+use std::path::Path;
+use std::collections::HashSet;
+
+use rustc_hash::FxHashMap;
+
+use ra_db::{
+    CrateGraph, FileId, SourceRoot, SourceRootId, SourceDatabase, salsa,
+};
+use ra_hir::{db, HirInterner};
+use ra_project_model::ProjectWorkspace;
+use ra_vfs::{Vfs, VfsChange};
+
+type Result<T> = std::result::Result<T, failure::Error>;
+
+#[salsa::database(
+    ra_db::SourceDatabaseStorage,
+    db::HirDatabaseStorage,
+    db::PersistentHirDatabaseStorage
+)]
+#[derive(Debug)]
+pub struct BatchDatabase {
+    runtime: salsa::Runtime<BatchDatabase>,
+    interner: Arc<HirInterner>,
+}
+
+impl salsa::Database for BatchDatabase {
+    fn salsa_runtime(&self) -> &salsa::Runtime<BatchDatabase> {
+        &self.runtime
+    }
+}
+
+impl AsRef<HirInterner> for BatchDatabase {
+    fn as_ref(&self) -> &HirInterner {
+        &self.interner
+    }
+}
+
+fn vfs_file_to_id(f: ra_vfs::VfsFile) -> FileId {
+    FileId(f.0.into())
+}
+fn vfs_root_to_id(r: ra_vfs::VfsRoot) -> SourceRootId {
+    SourceRootId(r.0.into())
+}
+
+impl BatchDatabase {
+    pub fn load(crate_graph: CrateGraph, vfs: &mut Vfs) -> BatchDatabase {
+        let mut db =
+            BatchDatabase { runtime: salsa::Runtime::default(), interner: Default::default() };
+        db.set_crate_graph(Arc::new(crate_graph));
+
+        // wait until Vfs has loaded all roots
+        let receiver = vfs.task_receiver().clone();
+        let mut roots_loaded = HashSet::new();
+        for task in receiver {
+            vfs.handle_task(task);
+            let mut done = false;
+            for change in vfs.commit_changes() {
+                match change {
+                    VfsChange::AddRoot { root, files } => {
+                        let source_root_id = vfs_root_to_id(root);
+                        log::debug!(
+                            "loaded source root {:?} with path {:?}",
+                            source_root_id,
+                            vfs.root2path(root)
+                        );
+                        let mut file_map = FxHashMap::default();
+                        for (vfs_file, path, text) in files {
+                            let file_id = vfs_file_to_id(vfs_file);
+                            db.set_file_text(file_id, text);
+                            db.set_file_relative_path(file_id, path.clone());
+                            db.set_file_source_root(file_id, source_root_id);
+                            file_map.insert(path, file_id);
+                        }
+                        let source_root = SourceRoot { files: file_map };
+                        db.set_source_root(source_root_id, Arc::new(source_root));
+                        roots_loaded.insert(source_root_id);
+                        if roots_loaded.len() == vfs.num_roots() {
+                            done = true;
+                        }
+                    }
+                    VfsChange::AddFile { .. }
+                    | VfsChange::RemoveFile { .. }
+                    | VfsChange::ChangeFile { .. } => {
+                        // We just need the first scan, so just ignore these
+                    }
+                }
+            }
+            if done {
+                break;
+            }
+        }
+
+        db
+    }
+
+    pub fn load_cargo(root: impl AsRef<Path>) -> Result<(BatchDatabase, Vec<SourceRootId>)> {
+        let root = root.as_ref().canonicalize()?;
+        let ws = ProjectWorkspace::discover(root.as_ref())?;
+        let mut roots = Vec::new();
+        roots.push(root.clone());
+        for pkg in ws.cargo.packages() {
+            roots.push(pkg.root(&ws.cargo).to_path_buf());
+        }
+        for krate in ws.sysroot.crates() {
+            roots.push(krate.root_dir(&ws.sysroot).to_path_buf())
+        }
+        let (mut vfs, roots) = Vfs::new(roots);
+        let mut load = |path: &Path| {
+            let vfs_file = vfs.load(path);
+            log::debug!("vfs file {:?} -> {:?}", path, vfs_file);
+            vfs_file.map(vfs_file_to_id)
+        };
+        let crate_graph = ws.to_crate_graph(&mut load);
+        log::debug!("crate graph: {:?}", crate_graph);
+
+        let local_roots = roots
+            .into_iter()
+            .filter(|r| vfs.root2path(*r).starts_with(&root))
+            .map(vfs_root_to_id)
+            .collect();
+
+        let db = BatchDatabase::load(crate_graph, &mut vfs);
+        let _ = vfs.shutdown();
+        Ok((db, local_roots))
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use ra_hir::Crate;
+    use super::*;
+
+    #[test]
+    fn test_loading_rust_analyzer() {
+        let mut path = std::env::current_exe().unwrap();
+        while !path.join("Cargo.toml").is_file() {
+            path = path.parent().unwrap().to_owned();
+        }
+        let (db, roots) = BatchDatabase::load_cargo(path).unwrap();
+        let mut num_crates = 0;
+        for root in roots {
+            for _krate in Crate::source_root_crates(&db, root) {
+                num_crates += 1;
+            }
+        }
+
+        // RA has quite a few crates, but the exact count doesn't matter
+        assert!(num_crates > 20);
+    }
+}
diff --git a/crates/ra_cli/Cargo.toml b/crates/ra_cli/Cargo.toml
index eb1722d5e..641ac5cbd 100644
--- a/crates/ra_cli/Cargo.toml
+++ b/crates/ra_cli/Cargo.toml
@@ -9,6 +9,12 @@ publish = false
 clap = "2.32.0"
 failure = "0.1.4"
 join_to_string = "0.1.1"
+flexi_logger = "0.10.0"
+indicatif = "0.11.0"
+
 ra_syntax = { path = "../ra_syntax" }
 ra_ide_api_light = { path = "../ra_ide_api_light" }
 tools = { path = "../tools" }
+ra_batch = { path = "../ra_batch" }
+ra_hir = { path = "../ra_hir" }
+ra_db = { path = "../ra_db" }
diff --git a/crates/ra_cli/src/analysis_stats.rs b/crates/ra_cli/src/analysis_stats.rs
new file mode 100644
index 000000000..a46ac974d
--- /dev/null
+++ b/crates/ra_cli/src/analysis_stats.rs
@@ -0,0 +1,100 @@
+use std::collections::HashSet;
+
+use ra_db::SourceDatabase;
+use ra_batch::BatchDatabase;
+use ra_hir::{Crate, ModuleDef, Ty, ImplItem};
+use ra_syntax::AstNode;
+
+use crate::Result;
+
+pub fn run(verbose: bool) -> Result<()> {
+    let (db, roots) = BatchDatabase::load_cargo(".")?;
+    println!("Database loaded, {} roots", roots.len());
+    let mut num_crates = 0;
+    let mut visited_modules = HashSet::new();
+    let mut visit_queue = Vec::new();
+    for root in roots {
+        for krate in Crate::source_root_crates(&db, root) {
+            num_crates += 1;
+            let module = krate.root_module(&db).expect("crate in source root without root module");
+            visit_queue.push(module);
+        }
+    }
+    println!("Crates in this dir: {}", num_crates);
+    let mut num_decls = 0;
+    let mut funcs = Vec::new();
+    while let Some(module) = visit_queue.pop() {
+        if visited_modules.insert(module) {
+            visit_queue.extend(module.children(&db));
+
+            for decl in module.declarations(&db) {
+                num_decls += 1;
+                match decl {
+                    ModuleDef::Function(f) => funcs.push(f),
+                    _ => {}
+                }
+            }
+
+            for impl_block in module.impl_blocks(&db) {
+                for item in impl_block.items() {
+                    num_decls += 1;
+                    match item {
+                        ImplItem::Method(f) => funcs.push(*f),
+                        _ => {}
+                    }
+                }
+            }
+        }
+    }
+    println!("Total modules found: {}", visited_modules.len());
+    println!("Total declarations: {}", num_decls);
+    println!("Total functions: {}", funcs.len());
+    let bar = indicatif::ProgressBar::new(funcs.len() as u64);
+    bar.tick();
+    let mut num_exprs = 0;
+    let mut num_exprs_unknown = 0;
+    let mut num_exprs_partially_unknown = 0;
+    for f in funcs {
+        if verbose {
+            let (file_id, source) = f.source(&db);
+            let original_file = file_id.original_file(&db);
+            let path = db.file_relative_path(original_file);
+            let syntax_range = source.syntax().range();
+            let name = f.name(&db);
+            println!("{} ({:?} {})", name, path, syntax_range);
+        }
+        let body = f.body(&db);
+        let inference_result = f.infer(&db);
+        for (expr_id, _) in body.exprs() {
+            let ty = &inference_result[expr_id];
+            num_exprs += 1;
+            if let Ty::Unknown = ty {
+                num_exprs_unknown += 1;
+            } else {
+                let mut is_partially_unknown = false;
+                ty.walk(&mut |ty| {
+                    if let Ty::Unknown = ty {
+                        is_partially_unknown = true;
+                    }
+                });
+                if is_partially_unknown {
+                    num_exprs_partially_unknown += 1;
+                }
+            }
+        }
+        bar.inc(1);
+    }
+    bar.finish_and_clear();
+    println!("Total expressions: {}", num_exprs);
+    println!(
+        "Expressions of unknown type: {} ({}%)",
+        num_exprs_unknown,
+        (num_exprs_unknown * 100 / num_exprs)
+    );
+    println!(
+        "Expressions of partially unknown type: {} ({}%)",
+        num_exprs_partially_unknown,
+        (num_exprs_partially_unknown * 100 / num_exprs)
+    );
+    Ok(())
+}
diff --git a/crates/ra_cli/src/main.rs b/crates/ra_cli/src/main.rs
index a4debeb48..72e6ae4d5 100644
--- a/crates/ra_cli/src/main.rs
+++ b/crates/ra_cli/src/main.rs
@@ -1,3 +1,5 @@
+mod analysis_stats;
+
 use std::{fs, io::Read, path::Path, time::Instant};
 
 use clap::{App, Arg, SubCommand};
@@ -5,10 +7,12 @@ use join_to_string::join;
 use ra_ide_api_light::{extend_selection, file_structure, syntax_tree};
 use ra_syntax::{SourceFile, TextRange, TreeArc, AstNode};
 use tools::collect_tests;
+use flexi_logger::Logger;
 
 type Result<T> = ::std::result::Result<T, failure::Error>;
 
 fn main() -> Result<()> {
+    Logger::with_env().start()?;
     let matches = App::new("ra-cli")
         .setting(clap::AppSettings::SubcommandRequiredElseHelp)
         .subcommand(
@@ -23,6 +27,9 @@ fn main() -> Result<()> {
                 .arg(Arg::with_name("start"))
                 .arg(Arg::with_name("end")),
         )
+        .subcommand(
+            SubCommand::with_name("analysis-stats").arg(Arg::with_name("verbose").short("v")),
+        )
         .get_matches();
     match matches.subcommand() {
         ("parse", Some(matches)) => {
@@ -56,6 +63,10 @@ fn main() -> Result<()> {
             let sels = selections(&file, start, end);
             println!("{}", sels)
         }
+        ("analysis-stats", Some(matches)) => {
+            let verbose = matches.is_present("verbose");
+            analysis_stats::run(verbose)?;
+        }
         _ => unreachable!(),
     }
     Ok(())
diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs
index 405634fe0..8decc65c5 100644
--- a/crates/ra_db/src/input.rs
+++ b/crates/ra_db/src/input.rs
@@ -112,6 +112,7 @@ impl CrateGraph {
         self.arena[&crate_id].file_id
     }
 
+    // TODO: this only finds one crate with the given root; we could have multiple
     pub fn crate_id_for_crate_root(&self, file_id: FileId) -> Option<CrateId> {
         let (&crate_id, _) = self.arena.iter().find(|(_crate_id, data)| data.file_id == file_id)?;
         Some(crate_id)
diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index cafc5279d..19f103855 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -1,7 +1,7 @@
 use std::sync::Arc;
 
 use relative_path::RelativePathBuf;
-use ra_db::{CrateId, FileId};
+use ra_db::{CrateId, FileId, SourceRootId};
 use ra_syntax::{ast::self, TreeArc, SyntaxNode};
 
 use crate::{
@@ -16,7 +16,7 @@ use crate::{
     docs::{Documentation, Docs, docs_from_ast},
     module_tree::ModuleId,
     ids::{FunctionId, StructId, EnumId, AstItemDef, ConstId, StaticId, TraitId, TypeId},
-    impl_block::ImplId,
+    impl_block::{ImplId, ImplBlock},
     resolve::Resolver,
 };
 
@@ -44,6 +44,15 @@ impl Crate {
     pub fn root_module(&self, db: &impl PersistentHirDatabase) -> Option<Module> {
         self.root_module_impl(db)
     }
+
+    // TODO: should this be in source_binder?
+    pub fn source_root_crates(
+        db: &impl PersistentHirDatabase,
+        source_root: SourceRootId,
+    ) -> Vec<Crate> {
+        let crate_ids = db.source_root_crates(source_root);
+        crate_ids.iter().map(|&crate_id| Crate { crate_id }).collect()
+    }
 }
 
 #[derive(Debug)]
@@ -168,6 +177,27 @@ impl Module {
         let item_map = db.item_map(self.krate);
         Resolver::default().push_module_scope(item_map, *self)
     }
+
+    pub fn declarations(self, db: &impl HirDatabase) -> Vec<ModuleDef> {
+        let (lowered_module, _) = db.lower_module(self);
+        lowered_module
+            .declarations
+            .values()
+            .cloned()
+            .flat_map(|per_ns| {
+                per_ns.take_types().into_iter().chain(per_ns.take_values().into_iter())
+            })
+            .collect()
+    }
+
+    pub fn impl_blocks(self, db: &impl HirDatabase) -> Vec<ImplBlock> {
+        let module_impl_blocks = db.impls_in_module(self);
+        module_impl_blocks
+            .impls
+            .iter()
+            .map(|(impl_id, _)| ImplBlock::from_id(module_impl_blocks.clone(), impl_id))
+            .collect()
+    }
 }
 
 impl Docs for Module {
diff --git a/crates/ra_hir/src/expr.rs b/crates/ra_hir/src/expr.rs
index b30e11abb..4e73590d0 100644
--- a/crates/ra_hir/src/expr.rs
+++ b/crates/ra_hir/src/expr.rs
@@ -70,6 +70,14 @@ impl Body {
         self.owner
     }
 
+    pub fn exprs(&self) -> impl Iterator<Item = (ExprId, &Expr)> {
+        self.exprs.iter()
+    }
+
+    pub fn pats(&self) -> impl Iterator<Item = (PatId, &Pat)> {
+        self.pats.iter()
+    }
+
     pub fn syntax_mapping(&self, db: &impl HirDatabase) -> Arc<BodySyntaxMapping> {
         db.body_syntax_mapping(self.owner)
     }
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 7203a8a10..2dc1de41a 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -449,6 +449,49 @@ impl Ty {
         Ty::Tuple(Arc::new([]))
     }
 
+    pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        f(self);
+        match self {
+            Ty::Slice(t) | Ty::Array(t) => t.walk(f),
+            Ty::RawPtr(t, _) => t.walk(f),
+            Ty::Ref(t, _) => t.walk(f),
+            Ty::Tuple(ts) => {
+                for t in ts.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::FnPtr(sig) => {
+                for input in &sig.input {
+                    input.walk(f);
+                }
+                sig.output.walk(f);
+            }
+            Ty::FnDef { substs, sig, .. } => {
+                for input in &sig.input {
+                    input.walk(f);
+                }
+                sig.output.walk(f);
+                for t in substs.0.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::Adt { substs, .. } => {
+                for t in substs.0.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::Bool
+            | Ty::Char
+            | Ty::Int(_)
+            | Ty::Float(_)
+            | Ty::Str
+            | Ty::Never
+            | Ty::Param { .. }
+            | Ty::Infer(_)
+            | Ty::Unknown => {}
+        }
+    }
+
     fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
         f(self);
         match self {
@@ -491,7 +534,15 @@ impl Ty {
                 }
                 substs.0 = v.into();
             }
-            _ => {}
+            Ty::Bool
+            | Ty::Char
+            | Ty::Int(_)
+            | Ty::Float(_)
+            | Ty::Str
+            | Ty::Never
+            | Ty::Param { .. }
+            | Ty::Infer(_)
+            | Ty::Unknown => {}
         }
     }
 
diff --git a/crates/ra_lsp_server/src/server_world.rs b/crates/ra_lsp_server/src/server_world.rs
index f97d240fa..4a68c019f 100644
--- a/crates/ra_lsp_server/src/server_world.rs
+++ b/crates/ra_lsp_server/src/server_world.rs
@@ -47,10 +47,8 @@ impl ServerWorldState {
                 roots.push(krate.root_dir(&ws.sysroot).to_path_buf())
             }
         }
-        roots.sort();
-        roots.dedup();
-        let roots_to_scan = roots.len();
         let (mut vfs, roots) = Vfs::new(roots);
+        let roots_to_scan = roots.len();
         for r in roots {
             let is_local = vfs.root2path(r).starts_with(&root);
             change.add_root(SourceRootId(r.0.into()), is_local);
diff --git a/crates/ra_vfs/src/lib.rs b/crates/ra_vfs/src/lib.rs
index 6b4eb6842..3805be570 100644
--- a/crates/ra_vfs/src/lib.rs
+++ b/crates/ra_vfs/src/lib.rs
@@ -94,6 +94,7 @@ impl Roots {
         let mut roots = Arena::default();
         // A hack to make nesting work.
         paths.sort_by_key(|it| Reverse(it.as_os_str().len()));
+        paths.dedup();
         for (i, path) in paths.iter().enumerate() {
             let nested_roots = paths[..i]
                 .iter()
@@ -181,6 +182,10 @@ impl Vfs {
         None
     }
 
+    pub fn num_roots(&self) -> usize {
+        self.roots.len()
+    }
+
     pub fn load(&mut self, path: &Path) -> Option<VfsFile> {
         if let Some((root, rel_path, file)) = self.find_root(path) {
             return if let Some(file) = file {