3 files changed, 51 insertions, 35 deletions

diff --git a/crates/ra_db/src/fixture.rs b/crates/ra_db/src/fixture.rs
index 4f4fb4494..2aafb9965 100644
--- a/crates/ra_db/src/fixture.rs
+++ b/crates/ra_db/src/fixture.rs
@@ -149,15 +149,17 @@ fn with_files(
             let crate_id = crate_graph.add_crate_root(
                 file_id,
                 meta.edition,
-                Some(CrateName::new(&krate).unwrap()),
+                Some(krate.clone()),
                 meta.cfg,
                 meta.env,
                 Default::default(),
             );
-            let prev = crates.insert(krate.clone(), crate_id);
+            let crate_name = CrateName::new(&krate).unwrap();
+            let prev = crates.insert(crate_name.clone(), crate_id);
             assert!(prev.is_none());
             for dep in meta.deps {
-                crate_deps.push((krate.clone(), dep))
+                let dep = CrateName::new(&dep).unwrap();
+                crate_deps.push((crate_name.clone(), dep))
             }
         } else if meta.path == "/main.rs" || meta.path == "/lib.rs" {
             assert!(default_crate_root.is_none());
@@ -220,7 +222,7 @@ impl From<Fixture> for FileMeta {
                 .edition
                 .as_ref()
                 .map_or(Edition::Edition2018, |v| Edition::from_str(&v).unwrap()),
-            env: Env::from(f.env.iter()),
+            env: f.env.into_iter().collect(),
         }
     }
 }
diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs
index 7f3660118..6f2e5cfc7 100644
--- a/crates/ra_db/src/input.rs
+++ b/crates/ra_db/src/input.rs
@@ -6,7 +6,7 @@
 //! actual IO. See `vfs` and `project_model` in the `rust-analyzer` crate for how
 //! actual IO is done and lowered to input.
 
-use std::{fmt, ops, str::FromStr, sync::Arc};
+use std::{fmt, iter::FromIterator, ops, str::FromStr, sync::Arc};
 
 use ra_cfg::CfgOptions;
 use ra_syntax::SmolStr;
@@ -67,7 +67,7 @@ pub struct CrateGraph {
 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct CrateId(pub u32);
 
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct CrateName(SmolStr);
 
 impl CrateName {
@@ -94,6 +94,13 @@ impl fmt::Display for CrateName {
     }
 }
 
+impl ops::Deref for CrateName {
+    type Target = str;
+    fn deref(&self) -> &Self::Target {
+        &*self.0
+    }
+}
+
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub struct ProcMacroId(pub u32);
 
@@ -117,7 +124,7 @@ pub struct CrateData {
     /// The name to display to the end user.
     /// This actual crate name can be different in a particular dependent crate
     /// or may even be missing for some cases, such as a dummy crate for the code snippet.
-    pub display_name: Option<CrateName>,
+    pub display_name: Option<String>,
     pub cfg_options: CfgOptions,
     pub env: Env,
     pub dependencies: Vec<Dependency>,
@@ -138,7 +145,7 @@ pub struct Env {
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct Dependency {
     pub crate_id: CrateId,
-    pub name: SmolStr,
+    pub name: CrateName,
 }
 
 impl CrateGraph {
@@ -146,7 +153,7 @@ impl CrateGraph {
         &mut self,
         file_id: FileId,
         edition: Edition,
-        display_name: Option<CrateName>,
+        display_name: Option<String>,
         cfg_options: CfgOptions,
         env: Env,
         proc_macro: Vec<(SmolStr, Arc<dyn ra_tt::TokenExpander>)>,
@@ -178,7 +185,7 @@ impl CrateGraph {
         if self.dfs_find(from, to, &mut FxHashSet::default()) {
             return Err(CyclicDependenciesError);
         }
-        self.arena.get_mut(&from).unwrap().add_dep(name.0, to);
+        self.arena.get_mut(&from).unwrap().add_dep(name, to);
         Ok(())
     }
 
@@ -190,6 +197,23 @@ impl CrateGraph {
         self.arena.keys().copied()
     }
 
+    /// Returns an iterator over all transitive dependencies of the given crate.
+    pub fn transitive_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> + '_ {
+        let mut worklist = vec![of];
+        let mut deps = FxHashSet::default();
+
+        while let Some(krate) = worklist.pop() {
+            if !deps.insert(krate) {
+                continue;
+            }
+
+            worklist.extend(self[krate].dependencies.iter().map(|dep| dep.crate_id));
+        }
+
+        deps.remove(&of);
+        deps.into_iter()
+    }
+
     // FIXME: 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, _) =
@@ -247,7 +271,7 @@ impl CrateId {
 }
 
 impl CrateData {
-    fn add_dep(&mut self, name: SmolStr, crate_id: CrateId) {
+    fn add_dep(&mut self, name: CrateName, crate_id: CrateId) {
         self.dependencies.push(Dependency { name, crate_id })
     }
 }
@@ -274,18 +298,9 @@ impl fmt::Display for Edition {
     }
 }
 
-impl<'a, T> From<T> for Env
-where
-    T: Iterator<Item = (&'a String, &'a String)>,
-{
-    fn from(iter: T) -> Self {
-        let mut result = Self::default();
-
-        for (k, v) in iter {
-            result.entries.insert(k.to_owned(), v.to_owned());
-        }
-
-        result
+impl FromIterator<(String, String)> for Env {
+    fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
+        Env { entries: FromIterator::from_iter(iter) }
     }
 }
 
@@ -429,7 +444,10 @@ mod tests {
             .is_ok());
         assert_eq!(
             graph[crate1].dependencies,
-            vec![Dependency { crate_id: crate2, name: "crate_name_with_dashes".into() }]
+            vec![Dependency {
+                crate_id: crate2,
+                name: CrateName::new("crate_name_with_dashes").unwrap()
+            }]
         );
     }
 }
diff --git a/crates/ra_db/src/lib.rs b/crates/ra_db/src/lib.rs
index 4a3ba57da..f25be24fe 100644
--- a/crates/ra_db/src/lib.rs
+++ b/crates/ra_db/src/lib.rs
@@ -16,9 +16,8 @@ pub use crate::{
         SourceRoot, SourceRootId,
     },
 };
-pub use relative_path::{RelativePath, RelativePathBuf};
 pub use salsa;
-pub use vfs::{file_set::FileSet, AbsPathBuf, VfsPath};
+pub use vfs::{file_set::FileSet, VfsPath};
 
 #[macro_export]
 macro_rules! impl_intern_key {
@@ -80,7 +79,7 @@ pub struct FilePosition {
     pub offset: TextSize,
 }
 
-#[derive(Clone, Copy, Debug)]
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
 pub struct FileRange {
     pub file_id: FileId,
     pub range: TextRange,
@@ -93,9 +92,9 @@ pub trait FileLoader {
     fn file_text(&self, file_id: FileId) -> Arc<String>;
     /// Note that we intentionally accept a `&str` and not a `&Path` here. This
     /// method exists to handle `#[path = "/some/path.rs"] mod foo;` and such,
-    /// so the input is guaranteed to be utf-8 string. We might introduce
-    /// `struct StrPath(str)` for clarity some day, but it's a bit messy, so we
-    /// get by with a `&str` for the time being.
+    /// so the input is guaranteed to be utf-8 string. One might be tempted to
+    /// introduce some kind of "utf-8 path with / separators", but that's a bad idea. Behold
+    /// `#[path = "C://no/way"]`
     fn resolve_path(&self, anchor: FileId, path: &str) -> Option<FileId>;
     fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>>;
 }
@@ -113,7 +112,7 @@ pub trait SourceDatabase: CheckCanceled + FileLoader + std::fmt::Debug {
     fn crate_graph(&self) -> Arc<CrateGraph>;
 }
 
-fn parse_query(db: &impl SourceDatabase, file_id: FileId) -> Parse<ast::SourceFile> {
+fn parse_query(db: &dyn SourceDatabase, file_id: FileId) -> Parse<ast::SourceFile> {
     let _p = profile("parse_query").detail(|| format!("{:?}", file_id));
     let text = db.file_text(file_id);
     SourceFile::parse(&*text)
@@ -136,10 +135,7 @@ pub trait SourceDatabaseExt: SourceDatabase {
     fn source_root_crates(&self, id: SourceRootId) -> Arc<FxHashSet<CrateId>>;
 }
 
-fn source_root_crates(
-    db: &(impl SourceDatabaseExt + SourceDatabase),
-    id: SourceRootId,
-) -> Arc<FxHashSet<CrateId>> {
+fn source_root_crates(db: &dyn SourceDatabaseExt, id: SourceRootId) -> Arc<FxHashSet<CrateId>> {
     let graph = db.crate_graph();
     let res = graph
         .iter()