4 files changed, 172 insertions, 256 deletions

diff --git a/crates/ra_db/Cargo.toml b/crates/ra_db/Cargo.toml
index 8ab409158..5f334d04f 100644
--- a/crates/ra_db/Cargo.toml
+++ b/crates/ra_db/Cargo.toml
@@ -3,13 +3,13 @@ edition = "2018"
 name = "ra_db"
 version = "0.1.0"
 authors = ["rust-analyzer developers"]
+license = "MIT OR Apache-2.0"
 
 [lib]
 doctest = false
 
 [dependencies]
-salsa = "0.14.1"
-relative-path = "1.0.0"
+salsa = "0.15.0"
 rustc-hash = "1.1.0"
 
 ra_syntax = { path = "../ra_syntax" }
@@ -17,3 +17,5 @@ ra_cfg = { path = "../ra_cfg" }
 ra_prof = { path = "../ra_prof" }
 ra_tt = { path = "../ra_tt" }
 test_utils = { path = "../test_utils" }
+vfs = { path = "../vfs" }
+stdx = { path = "../stdx" }
diff --git a/crates/ra_db/src/fixture.rs b/crates/ra_db/src/fixture.rs
index 482a2f3e6..209713987 100644
--- a/crates/ra_db/src/fixture.rs
+++ b/crates/ra_db/src/fixture.rs
@@ -57,17 +57,16 @@
 //! fn insert_source_code_here() {}
 //! "
 //! ```
-
-use std::str::FromStr;
-use std::sync::Arc;
+use std::{str::FromStr, sync::Arc};
 
 use ra_cfg::CfgOptions;
 use rustc_hash::FxHashMap;
-use test_utils::{extract_offset, parse_fixture, parse_single_fixture, FixtureMeta, CURSOR_MARKER};
+use test_utils::{extract_range_or_offset, Fixture, RangeOrOffset, CURSOR_MARKER};
+use vfs::{file_set::FileSet, VfsPath};
 
 use crate::{
-    input::CrateName, CrateGraph, CrateId, Edition, Env, FileId, FilePosition, RelativePathBuf,
-    SourceDatabaseExt, SourceRoot, SourceRootId,
+    input::CrateName, CrateGraph, CrateId, Edition, Env, FileId, FilePosition, SourceDatabaseExt,
+    SourceRoot, SourceRootId,
 };
 
 pub const WORKSPACE: SourceRootId = SourceRootId(0);
@@ -75,21 +74,32 @@ pub const WORKSPACE: SourceRootId = SourceRootId(0);
 pub trait WithFixture: Default + SourceDatabaseExt + 'static {
     fn with_single_file(text: &str) -> (Self, FileId) {
         let mut db = Self::default();
-        let file_id = with_single_file(&mut db, text);
-        (db, file_id)
+        let (_, files) = with_files(&mut db, text);
+        assert_eq!(files.len(), 1);
+        (db, files[0])
     }
 
     fn with_files(ra_fixture: &str) -> Self {
         let mut db = Self::default();
-        let pos = with_files(&mut db, ra_fixture);
+        let (pos, _) = with_files(&mut db, ra_fixture);
         assert!(pos.is_none());
         db
     }
 
     fn with_position(ra_fixture: &str) -> (Self, FilePosition) {
+        let (db, file_id, range_or_offset) = Self::with_range_or_offset(ra_fixture);
+        let offset = match range_or_offset {
+            RangeOrOffset::Range(_) => panic!(),
+            RangeOrOffset::Offset(it) => it,
+        };
+        (db, FilePosition { file_id, offset })
+    }
+
+    fn with_range_or_offset(ra_fixture: &str) -> (Self, FileId, RangeOrOffset) {
         let mut db = Self::default();
-        let pos = with_files(&mut db, ra_fixture);
-        (db, pos.unwrap())
+        let (pos, _) = with_files(&mut db, ra_fixture);
+        let (file_id, range_or_offset) = pos.unwrap();
+        (db, file_id, range_or_offset)
     }
 
     fn test_crate(&self) -> CrateId {
@@ -103,119 +113,64 @@ pub trait WithFixture: Default + SourceDatabaseExt + 'static {
 
 impl<DB: SourceDatabaseExt + Default + 'static> WithFixture for DB {}
 
-fn with_single_file(db: &mut dyn SourceDatabaseExt, ra_fixture: &str) -> FileId {
-    let file_id = FileId(0);
-    let rel_path: RelativePathBuf = "/main.rs".into();
-
-    let mut source_root = SourceRoot::new_local();
-    source_root.insert_file(rel_path.clone(), file_id);
-
-    let fixture = parse_single_fixture(ra_fixture);
-
-    let crate_graph = if let Some(entry) = fixture {
-        let meta = match ParsedMeta::from(&entry.meta) {
-            ParsedMeta::File(it) => it,
-            _ => panic!("with_single_file only support file meta"),
-        };
-
-        let mut crate_graph = CrateGraph::default();
-        crate_graph.add_crate_root(
-            file_id,
-            meta.edition,
-            meta.krate.map(|name| {
-                CrateName::new(&name).expect("Fixture crate name should not contain dashes")
-            }),
-            meta.cfg,
-            meta.env,
-            Default::default(),
-            Default::default(),
-        );
-        crate_graph
-    } else {
-        let mut crate_graph = CrateGraph::default();
-        crate_graph.add_crate_root(
-            file_id,
-            Edition::Edition2018,
-            None,
-            CfgOptions::default(),
-            Env::default(),
-            Default::default(),
-            Default::default(),
-        );
-        crate_graph
-    };
-
-    db.set_file_text(file_id, Arc::new(ra_fixture.to_string()));
-    db.set_file_relative_path(file_id, rel_path);
-    db.set_file_source_root(file_id, WORKSPACE);
-    db.set_source_root(WORKSPACE, Arc::new(source_root));
-    db.set_crate_graph(Arc::new(crate_graph));
-
-    file_id
-}
-
-fn with_files(db: &mut dyn SourceDatabaseExt, fixture: &str) -> Option<FilePosition> {
-    let fixture = parse_fixture(fixture);
+fn with_files(
+    db: &mut dyn SourceDatabaseExt,
+    fixture: &str,
+) -> (Option<(FileId, RangeOrOffset)>, Vec<FileId>) {
+    let fixture = Fixture::parse(fixture);
 
+    let mut files = Vec::new();
     let mut crate_graph = CrateGraph::default();
     let mut crates = FxHashMap::default();
     let mut crate_deps = Vec::new();
     let mut default_crate_root: Option<FileId> = None;
 
-    let mut source_root = SourceRoot::new_local();
-    let mut source_root_id = WORKSPACE;
-    let mut source_root_prefix: RelativePathBuf = "/".into();
+    let mut file_set = FileSet::default();
+    let source_root_id = WORKSPACE;
+    let source_root_prefix = "/".to_string();
     let mut file_id = FileId(0);
 
     let mut file_position = None;
 
-    for entry in fixture.iter() {
-        let meta = match ParsedMeta::from(&entry.meta) {
-            ParsedMeta::Root { path } => {
-                let source_root = std::mem::replace(&mut source_root, SourceRoot::new_local());
-                db.set_source_root(source_root_id, Arc::new(source_root));
-                source_root_id.0 += 1;
-                source_root_prefix = path;
-                continue;
-            }
-            ParsedMeta::File(it) => it,
+    for entry in fixture {
+        let text = if entry.text.contains(CURSOR_MARKER) {
+            let (range_or_offset, text) = extract_range_or_offset(&entry.text);
+            assert!(file_position.is_none());
+            file_position = Some((file_id, range_or_offset));
+            text.to_string()
+        } else {
+            entry.text.clone()
         };
+
+        let meta = FileMeta::from(entry);
         assert!(meta.path.starts_with(&source_root_prefix));
 
         if let Some(krate) = meta.krate {
             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(),
-                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());
             default_crate_root = Some(file_id);
         }
 
-        let text = if entry.text.contains(CURSOR_MARKER) {
-            let (offset, text) = extract_offset(&entry.text);
-            assert!(file_position.is_none());
-            file_position = Some(FilePosition { file_id, offset });
-            text.to_string()
-        } else {
-            entry.text.to_string()
-        };
-
         db.set_file_text(file_id, Arc::new(text));
-        db.set_file_relative_path(file_id, meta.path.clone());
         db.set_file_source_root(file_id, source_root_id);
-        source_root.insert_file(meta.path, file_id);
-
+        let path = VfsPath::new_virtual_path(meta.path);
+        file_set.insert(file_id, path.into());
+        files.push(file_id);
         file_id.0 += 1;
     }
 
@@ -228,7 +183,6 @@ fn with_files(db: &mut dyn SourceDatabaseExt, fixture: &str) -> Option<FilePosit
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
     } else {
         for (from, to) in crate_deps {
@@ -238,19 +192,14 @@ fn with_files(db: &mut dyn SourceDatabaseExt, fixture: &str) -> Option<FilePosit
         }
     }
 
-    db.set_source_root(source_root_id, Arc::new(source_root));
+    db.set_source_root(source_root_id, Arc::new(SourceRoot::new_local(file_set)));
     db.set_crate_graph(Arc::new(crate_graph));
 
-    file_position
-}
-
-enum ParsedMeta {
-    Root { path: RelativePathBuf },
-    File(FileMeta),
+    (file_position, files)
 }
 
 struct FileMeta {
-    path: RelativePathBuf,
+    path: String,
     krate: Option<String>,
     deps: Vec<String>,
     cfg: CfgOptions,
@@ -258,25 +207,22 @@ struct FileMeta {
     env: Env,
 }
 
-impl From<&FixtureMeta> for ParsedMeta {
-    fn from(meta: &FixtureMeta) -> Self {
-        match meta {
-            FixtureMeta::Root { path } => {
-                // `Self::Root` causes a false warning: 'variant is never constructed: `Root` '
-                // see https://github.com/rust-lang/rust/issues/69018
-                ParsedMeta::Root { path: path.to_owned() }
-            }
-            FixtureMeta::File(f) => Self::File(FileMeta {
-                path: f.path.to_owned(),
-                krate: f.crate_name.to_owned(),
-                deps: f.deps.to_owned(),
-                cfg: f.cfg.to_owned(),
-                edition: f
-                    .edition
-                    .as_ref()
-                    .map_or(Edition::Edition2018, |v| Edition::from_str(&v).unwrap()),
-                env: Env::from(f.env.iter()),
-            }),
+impl From<Fixture> for FileMeta {
+    fn from(f: Fixture) -> FileMeta {
+        let mut cfg = CfgOptions::default();
+        f.cfg_atoms.iter().for_each(|it| cfg.insert_atom(it.into()));
+        f.cfg_key_values.iter().for_each(|(k, v)| cfg.insert_key_value(k.into(), v.into()));
+
+        FileMeta {
+            path: f.path,
+            krate: f.krate,
+            deps: f.deps,
+            cfg,
+            edition: f
+                .edition
+                .as_ref()
+                .map_or(Edition::Edition2018, |v| Edition::from_str(&v).unwrap()),
+            env: Env::from(f.env.iter()),
         }
     }
 }
diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs
index 4d2d3b48a..aaa492759 100644
--- a/crates/ra_db/src/input.rs
+++ b/crates/ra_db/src/input.rs
@@ -6,29 +6,15 @@
 //! 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,
-    path::{Path, PathBuf},
-    str::FromStr,
-    sync::Arc,
-};
+use std::{fmt, ops, str::FromStr, sync::Arc};
 
 use ra_cfg::CfgOptions;
 use ra_syntax::SmolStr;
-use rustc_hash::FxHashMap;
-use rustc_hash::FxHashSet;
-
-use crate::{RelativePath, RelativePathBuf};
-use fmt::Display;
 use ra_tt::TokenExpander;
+use rustc_hash::{FxHashMap, FxHashSet};
+use vfs::file_set::FileSet;
 
-/// `FileId` is an integer which uniquely identifies a file. File paths are
-/// messy and system-dependent, so most of the code should work directly with
-/// `FileId`, without inspecting the path. The mapping between `FileId` and path
-/// and `SourceRoot` is constant. A file rename is represented as a pair of
-/// deletion/creation.
-#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
-pub struct FileId(pub u32);
+pub use vfs::FileId;
 
 /// Files are grouped into source roots. A source root is a directory on the
 /// file systems which is watched for changes. Typically it corresponds to a
@@ -47,27 +33,18 @@ pub struct SourceRoot {
     /// Libraries are considered mostly immutable, this assumption is used to
     /// optimize salsa's query structure
     pub is_library: bool,
-    files: FxHashMap<RelativePathBuf, FileId>,
+    pub(crate) file_set: FileSet,
 }
 
 impl SourceRoot {
-    pub fn new_local() -> SourceRoot {
-        SourceRoot { is_library: false, files: Default::default() }
-    }
-    pub fn new_library() -> SourceRoot {
-        SourceRoot { is_library: true, files: Default::default() }
-    }
-    pub fn insert_file(&mut self, path: RelativePathBuf, file_id: FileId) {
-        self.files.insert(path, file_id);
+    pub fn new_local(file_set: FileSet) -> SourceRoot {
+        SourceRoot { is_library: false, file_set }
     }
-    pub fn remove_file(&mut self, path: &RelativePath) {
-        self.files.remove(path);
+    pub fn new_library(file_set: FileSet) -> SourceRoot {
+        SourceRoot { is_library: true, file_set }
     }
-    pub fn walk(&self) -> impl Iterator<Item = FileId> + '_ {
-        self.files.values().copied()
-    }
-    pub fn file_by_relative_path(&self, path: &RelativePath) -> Option<FileId> {
-        self.files.get(path).copied()
+    pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
+        self.file_set.iter()
     }
 }
 
@@ -90,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 {
@@ -111,12 +88,19 @@ impl CrateName {
     }
 }
 
-impl Display for CrateName {
+impl fmt::Display for CrateName {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "{}", self.0)
     }
 }
 
+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);
 
@@ -140,10 +124,9 @@ 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 extern_source: ExternSource,
     pub dependencies: Vec<Dependency>,
     pub proc_macro: Vec<ProcMacro>,
 }
@@ -154,26 +137,15 @@ pub enum Edition {
     Edition2015,
 }
 
-#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
-pub struct ExternSourceId(pub u32);
-
 #[derive(Default, Debug, Clone, PartialEq, Eq)]
 pub struct Env {
     entries: FxHashMap<String, String>,
 }
 
-// FIXME: Redesign vfs for solve the following limitation ?
-// Note: Some env variables (e.g. OUT_DIR) are located outside of the
-// crate. We store a map to allow remap it to ExternSourceId
-#[derive(Default, Debug, Clone, PartialEq, Eq)]
-pub struct ExternSource {
-    extern_paths: FxHashMap<PathBuf, ExternSourceId>,
-}
-
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct Dependency {
     pub crate_id: CrateId,
-    pub name: SmolStr,
+    pub name: CrateName,
 }
 
 impl CrateGraph {
@@ -181,10 +153,9 @@ impl CrateGraph {
         &mut self,
         file_id: FileId,
         edition: Edition,
-        display_name: Option<CrateName>,
+        display_name: Option<String>,
         cfg_options: CfgOptions,
         env: Env,
-        extern_source: ExternSource,
         proc_macro: Vec<(SmolStr, Arc<dyn ra_tt::TokenExpander>)>,
     ) -> CrateId {
         let proc_macro =
@@ -196,7 +167,6 @@ impl CrateGraph {
             display_name,
             cfg_options,
             env,
-            extern_source,
             proc_macro,
             dependencies: Vec::new(),
         };
@@ -215,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(())
     }
 
@@ -227,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, _) =
@@ -256,12 +243,12 @@ impl CrateGraph {
             return false;
         }
 
+        if target == from {
+            return true;
+        }
+
         for dep in &self[from].dependencies {
             let crate_id = dep.crate_id;
-            if crate_id == target {
-                return true;
-            }
-
             if self.dfs_find(target, crate_id, visited) {
                 return true;
             }
@@ -284,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 })
     }
 }
@@ -336,24 +323,6 @@ impl Env {
     }
 }
 
-impl ExternSource {
-    pub fn extern_path(&self, path: impl AsRef<Path>) -> Option<(ExternSourceId, RelativePathBuf)> {
-        let path = path.as_ref();
-        self.extern_paths.iter().find_map(|(root_path, id)| {
-            if let Ok(rel_path) = path.strip_prefix(root_path) {
-                let rel_path = RelativePathBuf::from_path(rel_path).ok()?;
-                Some((*id, rel_path))
-            } else {
-                None
-            }
-        })
-    }
-
-    pub fn set_extern_path(&mut self, root_path: &Path, root: ExternSourceId) {
-        self.extern_paths.insert(root_path.to_path_buf(), root);
-    }
-}
-
 #[derive(Debug)]
 pub struct ParseEditionError {
     invalid_input: String,
@@ -375,7 +344,7 @@ mod tests {
     use super::{CfgOptions, CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
 
     #[test]
-    fn it_should_panic_because_of_cycle_dependencies() {
+    fn detect_cyclic_dependency_indirect() {
         let mut graph = CrateGraph::default();
         let crate1 = graph.add_crate_root(
             FileId(1u32),
@@ -384,7 +353,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         let crate2 = graph.add_crate_root(
             FileId(2u32),
@@ -393,7 +361,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         let crate3 = graph.add_crate_root(
             FileId(3u32),
@@ -402,7 +369,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
         assert!(graph.add_dep(crate2, CrateName::new("crate3").unwrap(), crate3).is_ok());
@@ -410,7 +376,7 @@ mod tests {
     }
 
     #[test]
-    fn it_works() {
+    fn detect_cyclic_dependency_direct() {
         let mut graph = CrateGraph::default();
         let crate1 = graph.add_crate_root(
             FileId(1u32),
@@ -419,7 +385,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         let crate2 = graph.add_crate_root(
             FileId(2u32),
@@ -428,6 +393,28 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
+        );
+        assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
+        assert!(graph.add_dep(crate2, CrateName::new("crate2").unwrap(), crate2).is_err());
+    }
+
+    #[test]
+    fn it_works() {
+        let mut graph = CrateGraph::default();
+        let crate1 = graph.add_crate_root(
+            FileId(1u32),
+            Edition2018,
+            None,
+            CfgOptions::default(),
+            Env::default(),
+            Default::default(),
+        );
+        let crate2 = graph.add_crate_root(
+            FileId(2u32),
+            Edition2018,
+            None,
+            CfgOptions::default(),
+            Env::default(),
             Default::default(),
         );
         let crate3 = graph.add_crate_root(
@@ -437,7 +424,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
         assert!(graph.add_dep(crate2, CrateName::new("crate3").unwrap(), crate3).is_ok());
@@ -453,7 +439,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         let crate2 = graph.add_crate_root(
             FileId(2u32),
@@ -462,14 +447,16 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         assert!(graph
             .add_dep(crate1, CrateName::normalize_dashes("crate-name-with-dashes"), crate2)
             .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 fd4280de2..f25be24fe 100644
--- a/crates/ra_db/src/lib.rs
+++ b/crates/ra_db/src/lib.rs
@@ -7,16 +7,17 @@ use std::{panic, sync::Arc};
 
 use ra_prof::profile;
 use ra_syntax::{ast, Parse, SourceFile, TextRange, TextSize};
+use rustc_hash::FxHashSet;
 
 pub use crate::{
     cancellation::Canceled,
     input::{
-        CrateGraph, CrateId, CrateName, Dependency, Edition, Env, ExternSource, ExternSourceId,
-        FileId, ProcMacroId, SourceRoot, SourceRootId,
+        CrateData, CrateGraph, CrateId, CrateName, Dependency, Edition, Env, FileId, ProcMacroId,
+        SourceRoot, SourceRootId,
     },
 };
-pub use relative_path::{RelativePath, RelativePathBuf};
 pub use salsa;
+pub use vfs::{file_set::FileSet, VfsPath};
 
 #[macro_export]
 macro_rules! impl_intern_key {
@@ -78,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,
@@ -89,15 +90,13 @@ pub const DEFAULT_LRU_CAP: usize = 128;
 pub trait FileLoader {
     /// Text of the file.
     fn file_text(&self, file_id: FileId) -> Arc<String>;
-    fn resolve_relative_path(&self, anchor: FileId, relative_path: &RelativePath)
-        -> Option<FileId>;
-    fn relevant_crates(&self, file_id: FileId) -> Arc<Vec<CrateId>>;
-
-    fn resolve_extern_path(
-        &self,
-        extern_id: ExternSourceId,
-        relative_path: &RelativePath,
-    ) -> Option<FileId>;
+    /// 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. 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>>;
 }
 
 /// Database which stores all significant input facts: source code and project
@@ -113,8 +112,8 @@ 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> {
-    let _p = profile("parse_query");
+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)
 }
@@ -126,8 +125,6 @@ pub trait SourceDatabaseExt: SourceDatabase {
     #[salsa::input]
     fn file_text(&self, file_id: FileId) -> Arc<String>;
     /// Path to a file, relative to the root of its source root.
-    #[salsa::input]
-    fn file_relative_path(&self, file_id: FileId) -> RelativePathBuf;
     /// Source root of the file.
     #[salsa::input]
     fn file_source_root(&self, file_id: FileId) -> SourceRootId;
@@ -135,16 +132,18 @@ pub trait SourceDatabaseExt: SourceDatabase {
     #[salsa::input]
     fn source_root(&self, id: SourceRootId) -> Arc<SourceRoot>;
 
-    fn source_root_crates(&self, id: SourceRootId) -> Arc<Vec<CrateId>>;
+    fn source_root_crates(&self, id: SourceRootId) -> Arc<FxHashSet<CrateId>>;
 }
 
-fn source_root_crates(
-    db: &(impl SourceDatabaseExt + SourceDatabase),
-    id: SourceRootId,
-) -> Arc<Vec<CrateId>> {
-    let root = db.source_root(id);
+fn source_root_crates(db: &dyn SourceDatabaseExt, id: SourceRootId) -> Arc<FxHashSet<CrateId>> {
     let graph = db.crate_graph();
-    let res = root.walk().filter_map(|it| graph.crate_id_for_crate_root(it)).collect::<Vec<_>>();
+    let res = graph
+        .iter()
+        .filter(|&krate| {
+            let root_file = graph[krate].root_file_id;
+            db.file_source_root(root_file) == id
+        })
+        .collect::<FxHashSet<_>>();
     Arc::new(res)
 }
 
@@ -155,33 +154,15 @@ impl<T: SourceDatabaseExt> FileLoader for FileLoaderDelegate<&'_ T> {
     fn file_text(&self, file_id: FileId) -> Arc<String> {
         SourceDatabaseExt::file_text(self.0, file_id)
     }
-    fn resolve_relative_path(
-        &self,
-        anchor: FileId,
-        relative_path: &RelativePath,
-    ) -> Option<FileId> {
-        let path = {
-            let mut path = self.0.file_relative_path(anchor);
-            assert!(path.pop());
-            path.push(relative_path);
-            path.normalize()
-        };
+    fn resolve_path(&self, anchor: FileId, path: &str) -> Option<FileId> {
+        // FIXME: this *somehow* should be platform agnostic...
         let source_root = self.0.file_source_root(anchor);
         let source_root = self.0.source_root(source_root);
-        source_root.file_by_relative_path(&path)
+        source_root.file_set.resolve_path(anchor, path)
     }
 
-    fn relevant_crates(&self, file_id: FileId) -> Arc<Vec<CrateId>> {
+    fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>> {
         let source_root = self.0.file_source_root(file_id);
         self.0.source_root_crates(source_root)
     }
-
-    fn resolve_extern_path(
-        &self,
-        extern_id: ExternSourceId,
-        relative_path: &RelativePath,
-    ) -> Option<FileId> {
-        let source_root = self.0.source_root(SourceRootId(extern_id.0));
-        source_root.file_by_relative_path(&relative_path)
-    }
 }