4 files changed, 109 insertions, 213 deletions

diff --git a/crates/ra_db/Cargo.toml b/crates/ra_db/Cargo.toml
index 8ab409158..372fb242b 100644
--- a/crates/ra_db/Cargo.toml
+++ b/crates/ra_db/Cargo.toml
@@ -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..4f4fb4494 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,83 +113,36 @@ 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 {
@@ -190,7 +153,6 @@ fn with_files(db: &mut dyn SourceDatabaseExt, fixture: &str) -> Option<FilePosit
                 meta.cfg,
                 meta.env,
                 Default::default(),
-                Default::default(),
             );
             let prev = crates.insert(krate.clone(), crate_id);
             assert!(prev.is_none());
@@ -202,20 +164,11 @@ fn with_files(db: &mut dyn SourceDatabaseExt, fixture: &str) -> Option<FilePosit
             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 +181,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 +190,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 +205,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 bf26048f2..7f3660118 100644
--- a/crates/ra_db/src/input.rs
+++ b/crates/ra_db/src/input.rs
@@ -6,27 +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 ra_tt::TokenExpander;
 use rustc_hash::{FxHashMap, FxHashSet};
+use vfs::file_set::FileSet;
 
-use crate::{RelativePath, RelativePathBuf};
-
-/// `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
@@ -45,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()
     }
 }
 
@@ -141,7 +120,6 @@ pub struct CrateData {
     pub display_name: Option<CrateName>,
     pub cfg_options: CfgOptions,
     pub env: Env,
-    pub extern_source: ExternSource,
     pub dependencies: Vec<Dependency>,
     pub proc_macro: Vec<ProcMacro>,
 }
@@ -152,22 +130,11 @@ 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,
@@ -182,7 +149,6 @@ impl CrateGraph {
         display_name: Option<CrateName>,
         cfg_options: CfgOptions,
         env: Env,
-        extern_source: ExternSource,
         proc_macro: Vec<(SmolStr, Arc<dyn ra_tt::TokenExpander>)>,
     ) -> CrateId {
         let proc_macro =
@@ -194,7 +160,6 @@ impl CrateGraph {
             display_name,
             cfg_options,
             env,
-            extern_source,
             proc_macro,
             dependencies: Vec::new(),
         };
@@ -254,12 +219,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;
             }
@@ -334,20 +299,6 @@ impl Env {
     }
 }
 
-impl ExternSource {
-    pub fn extern_path(&self, path: &Path) -> Option<(ExternSourceId, RelativePathBuf)> {
-        self.extern_paths.iter().find_map(|(root_path, id)| {
-            let rel_path = path.strip_prefix(root_path).ok()?;
-            let rel_path = RelativePathBuf::from_path(rel_path).ok()?;
-            Some((*id, rel_path))
-        })
-    }
-
-    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,
@@ -369,7 +320,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),
@@ -378,7 +329,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         let crate2 = graph.add_crate_root(
             FileId(2u32),
@@ -387,7 +337,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         let crate3 = graph.add_crate_root(
             FileId(3u32),
@@ -396,7 +345,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());
@@ -404,7 +352,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),
@@ -413,7 +361,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         let crate2 = graph.add_crate_root(
             FileId(2u32),
@@ -422,6 +369,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(
@@ -431,7 +400,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());
@@ -447,7 +415,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         let crate2 = graph.add_crate_root(
             FileId(2u32),
@@ -456,7 +423,6 @@ mod tests {
             CfgOptions::default(),
             Env::default(),
             Default::default(),
-            Default::default(),
         );
         assert!(graph
             .add_dep(crate1, CrateName::normalize_dashes("crate-name-with-dashes"), crate2)
diff --git a/crates/ra_db/src/lib.rs b/crates/ra_db/src/lib.rs
index 80ddb6058..4a3ba57da 100644
--- a/crates/ra_db/src/lib.rs
+++ b/crates/ra_db/src/lib.rs
@@ -12,12 +12,13 @@ use rustc_hash::FxHashSet;
 pub use crate::{
     cancellation::Canceled,
     input::{
-        CrateData, 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, AbsPathBuf, VfsPath};
 
 #[macro_export]
 macro_rules! impl_intern_key {
@@ -113,7 +114,7 @@ pub trait SourceDatabase: CheckCanceled + FileLoader + std::fmt::Debug {
 }
 
 fn parse_query(db: &impl SourceDatabase, file_id: FileId) -> Parse<ast::SourceFile> {
-    let _p = profile("parse_query");
+    let _p = profile("parse_query").detail(|| format!("{:?}", file_id));
     let text = db.file_text(file_id);
     SourceFile::parse(&*text)
 }
@@ -125,8 +126,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;
@@ -161,24 +160,9 @@ impl<T: SourceDatabaseExt> FileLoader for FileLoaderDelegate<&'_ T> {
     }
     fn resolve_path(&self, anchor: FileId, path: &str) -> Option<FileId> {
         // FIXME: this *somehow* should be platform agnostic...
-        if std::path::Path::new(path).is_absolute() {
-            let krate = *self.relevant_crates(anchor).iter().next()?;
-            let (extern_source_id, relative_file) =
-                self.0.crate_graph()[krate].extern_source.extern_path(path.as_ref())?;
-
-            let source_root = self.0.source_root(SourceRootId(extern_source_id.0));
-            source_root.file_by_relative_path(&relative_file)
-        } else {
-            let rel_path = {
-                let mut rel_path = self.0.file_relative_path(anchor);
-                assert!(rel_path.pop());
-                rel_path.push(path);
-                rel_path.normalize()
-            };
-            let source_root = self.0.file_source_root(anchor);
-            let source_root = self.0.source_root(source_root);
-            source_root.file_by_relative_path(&rel_path)
-        }
+        let source_root = self.0.file_source_root(anchor);
+        let source_root = self.0.source_root(source_root);
+        source_root.file_set.resolve_path(anchor, path)
     }
 
     fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>> {