Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

5 files changed, 1524 insertions, 0 deletions

diff --git a/src/tools/rust-analyzer/crates/base-db/Cargo.toml b/src/tools/rust-analyzer/crates/base-db/Cargo.toml
new file mode 100644
index 000000000..f02a51ab6
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/base-db/Cargo.toml
@@ -0,0 +1,22 @@
+[package]
+name = "base-db"
+version = "0.0.0"
+description = "TBD"
+license = "MIT OR Apache-2.0"
+edition = "2021"
+rust-version = "1.57"
+
+[lib]
+doctest = false
+
+[dependencies]
+salsa = "0.17.0-pre.2"
+rustc-hash = "1.1.0"
+
+syntax = { path = "../syntax", version = "0.0.0" }
+stdx = { path = "../stdx", version = "0.0.0" }
+cfg = { path = "../cfg", version = "0.0.0" }
+profile = { path = "../profile", version = "0.0.0" }
+tt = { path = "../tt", version = "0.0.0" }
+test-utils = { path = "../test-utils", version = "0.0.0" }
+vfs = { path = "../vfs", version = "0.0.0" }
diff --git a/src/tools/rust-analyzer/crates/base-db/src/change.rs b/src/tools/rust-analyzer/crates/base-db/src/change.rs
new file mode 100644
index 000000000..b57f23457
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/base-db/src/change.rs
@@ -0,0 +1,85 @@
+//! Defines a unit of change that can applied to the database to get the next
+//! state. Changes are transactional.
+
+use std::{fmt, sync::Arc};
+
+use salsa::Durability;
+use vfs::FileId;
+
+use crate::{CrateGraph, SourceDatabaseExt, SourceRoot, SourceRootId};
+
+/// Encapsulate a bunch of raw `.set` calls on the database.
+#[derive(Default)]
+pub struct Change {
+    pub roots: Option<Vec<SourceRoot>>,
+    pub files_changed: Vec<(FileId, Option<Arc<String>>)>,
+    pub crate_graph: Option<CrateGraph>,
+}
+
+impl fmt::Debug for Change {
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let mut d = fmt.debug_struct("Change");
+        if let Some(roots) = &self.roots {
+            d.field("roots", roots);
+        }
+        if !self.files_changed.is_empty() {
+            d.field("files_changed", &self.files_changed.len());
+        }
+        if self.crate_graph.is_some() {
+            d.field("crate_graph", &self.crate_graph);
+        }
+        d.finish()
+    }
+}
+
+impl Change {
+    pub fn new() -> Change {
+        Change::default()
+    }
+
+    pub fn set_roots(&mut self, roots: Vec<SourceRoot>) {
+        self.roots = Some(roots);
+    }
+
+    pub fn change_file(&mut self, file_id: FileId, new_text: Option<Arc<String>>) {
+        self.files_changed.push((file_id, new_text))
+    }
+
+    pub fn set_crate_graph(&mut self, graph: CrateGraph) {
+        self.crate_graph = Some(graph);
+    }
+
+    pub fn apply(self, db: &mut dyn SourceDatabaseExt) {
+        let _p = profile::span("RootDatabase::apply_change");
+        if let Some(roots) = self.roots {
+            for (idx, root) in roots.into_iter().enumerate() {
+                let root_id = SourceRootId(idx as u32);
+                let durability = durability(&root);
+                for file_id in root.iter() {
+                    db.set_file_source_root_with_durability(file_id, root_id, durability);
+                }
+                db.set_source_root_with_durability(root_id, Arc::new(root), durability);
+            }
+        }
+
+        for (file_id, text) in self.files_changed {
+            let source_root_id = db.file_source_root(file_id);
+            let source_root = db.source_root(source_root_id);
+            let durability = durability(&source_root);
+            // XXX: can't actually remove the file, just reset the text
+            let text = text.unwrap_or_default();
+            db.set_file_text_with_durability(file_id, text, durability)
+        }
+        if let Some(crate_graph) = self.crate_graph {
+            db.set_crate_graph_with_durability(Arc::new(crate_graph), Durability::HIGH)
+        }
+    }
+}
+
+fn durability(source_root: &SourceRoot) -> Durability {
+    if source_root.is_library {
+        Durability::HIGH
+    } else {
+        Durability::LOW
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/base-db/src/fixture.rs b/src/tools/rust-analyzer/crates/base-db/src/fixture.rs
new file mode 100644
index 000000000..8e6e6a11a
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/base-db/src/fixture.rs
@@ -0,0 +1,494 @@
+//! A set of high-level utility fixture methods to use in tests.
+use std::{mem, str::FromStr, sync::Arc};
+
+use cfg::CfgOptions;
+use rustc_hash::FxHashMap;
+use test_utils::{
+    extract_range_or_offset, Fixture, RangeOrOffset, CURSOR_MARKER, ESCAPED_CURSOR_MARKER,
+};
+use tt::Subtree;
+use vfs::{file_set::FileSet, VfsPath};
+
+use crate::{
+    input::{CrateName, CrateOrigin, LangCrateOrigin},
+    Change, CrateDisplayName, CrateGraph, CrateId, Dependency, Edition, Env, FileId, FilePosition,
+    FileRange, ProcMacro, ProcMacroExpander, ProcMacroExpansionError, SourceDatabaseExt,
+    SourceRoot, SourceRootId,
+};
+
+pub const WORKSPACE: SourceRootId = SourceRootId(0);
+
+pub trait WithFixture: Default + SourceDatabaseExt + 'static {
+    fn with_single_file(ra_fixture: &str) -> (Self, FileId) {
+        let fixture = ChangeFixture::parse(ra_fixture);
+        let mut db = Self::default();
+        fixture.change.apply(&mut db);
+        assert_eq!(fixture.files.len(), 1);
+        (db, fixture.files[0])
+    }
+
+    fn with_many_files(ra_fixture: &str) -> (Self, Vec<FileId>) {
+        let fixture = ChangeFixture::parse(ra_fixture);
+        let mut db = Self::default();
+        fixture.change.apply(&mut db);
+        assert!(fixture.file_position.is_none());
+        (db, fixture.files)
+    }
+
+    fn with_files(ra_fixture: &str) -> Self {
+        let fixture = ChangeFixture::parse(ra_fixture);
+        let mut db = Self::default();
+        fixture.change.apply(&mut db);
+        assert!(fixture.file_position.is_none());
+        db
+    }
+
+    fn with_files_extra_proc_macros(
+        ra_fixture: &str,
+        proc_macros: Vec<(String, ProcMacro)>,
+    ) -> Self {
+        let fixture = ChangeFixture::parse_with_proc_macros(ra_fixture, proc_macros);
+        let mut db = Self::default();
+        fixture.change.apply(&mut db);
+        assert!(fixture.file_position.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 = range_or_offset.expect_offset();
+        (db, FilePosition { file_id, offset })
+    }
+
+    fn with_range(ra_fixture: &str) -> (Self, FileRange) {
+        let (db, file_id, range_or_offset) = Self::with_range_or_offset(ra_fixture);
+        let range = range_or_offset.expect_range();
+        (db, FileRange { file_id, range })
+    }
+
+    fn with_range_or_offset(ra_fixture: &str) -> (Self, FileId, RangeOrOffset) {
+        let fixture = ChangeFixture::parse(ra_fixture);
+        let mut db = Self::default();
+        fixture.change.apply(&mut db);
+        let (file_id, range_or_offset) = fixture
+            .file_position
+            .expect("Could not find file position in fixture. Did you forget to add an `$0`?");
+        (db, file_id, range_or_offset)
+    }
+
+    fn test_crate(&self) -> CrateId {
+        let crate_graph = self.crate_graph();
+        let mut it = crate_graph.iter();
+        let res = it.next().unwrap();
+        assert!(it.next().is_none());
+        res
+    }
+}
+
+impl<DB: SourceDatabaseExt + Default + 'static> WithFixture for DB {}
+
+pub struct ChangeFixture {
+    pub file_position: Option<(FileId, RangeOrOffset)>,
+    pub files: Vec<FileId>,
+    pub change: Change,
+}
+
+impl ChangeFixture {
+    pub fn parse(ra_fixture: &str) -> ChangeFixture {
+        Self::parse_with_proc_macros(ra_fixture, Vec::new())
+    }
+
+    pub fn parse_with_proc_macros(
+        ra_fixture: &str,
+        mut proc_macros: Vec<(String, ProcMacro)>,
+    ) -> ChangeFixture {
+        let (mini_core, proc_macro_names, fixture) = Fixture::parse(ra_fixture);
+        let mut change = Change::new();
+
+        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 default_cfg = CfgOptions::default();
+
+        let mut file_set = FileSet::default();
+        let mut current_source_root_kind = SourceRootKind::Local;
+        let source_root_prefix = "/".to_string();
+        let mut file_id = FileId(0);
+        let mut roots = Vec::new();
+
+        let mut file_position = None;
+
+        for entry in fixture {
+            let text = if entry.text.contains(CURSOR_MARKER) {
+                if entry.text.contains(ESCAPED_CURSOR_MARKER) {
+                    entry.text.replace(ESCAPED_CURSOR_MARKER, CURSOR_MARKER)
+                } else {
+                    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
+                }
+            } else {
+                entry.text.clone()
+            };
+
+            let meta = FileMeta::from(entry);
+            assert!(meta.path.starts_with(&source_root_prefix));
+            if !meta.deps.is_empty() {
+                assert!(meta.krate.is_some(), "can't specify deps without naming the crate")
+            }
+
+            if let Some(kind) = &meta.introduce_new_source_root {
+                let root = match current_source_root_kind {
+                    SourceRootKind::Local => SourceRoot::new_local(mem::take(&mut file_set)),
+                    SourceRootKind::Library => SourceRoot::new_library(mem::take(&mut file_set)),
+                };
+                roots.push(root);
+                current_source_root_kind = *kind;
+            }
+
+            if let Some((krate, origin, version)) = meta.krate {
+                let crate_name = CrateName::normalize_dashes(&krate);
+                let crate_id = crate_graph.add_crate_root(
+                    file_id,
+                    meta.edition,
+                    Some(crate_name.clone().into()),
+                    version,
+                    meta.cfg.clone(),
+                    meta.cfg,
+                    meta.env,
+                    Ok(Vec::new()),
+                    false,
+                    origin,
+                );
+                let prev = crates.insert(crate_name.clone(), crate_id);
+                assert!(prev.is_none());
+                for dep in meta.deps {
+                    let prelude = meta.extern_prelude.contains(&dep);
+                    let dep = CrateName::normalize_dashes(&dep);
+                    crate_deps.push((crate_name.clone(), dep, prelude))
+                }
+            } else if meta.path == "/main.rs" || meta.path == "/lib.rs" {
+                assert!(default_crate_root.is_none());
+                default_crate_root = Some(file_id);
+                default_cfg = meta.cfg;
+            }
+
+            change.change_file(file_id, Some(Arc::new(text)));
+            let path = VfsPath::new_virtual_path(meta.path);
+            file_set.insert(file_id, path);
+            files.push(file_id);
+            file_id.0 += 1;
+        }
+
+        if crates.is_empty() {
+            let crate_root = default_crate_root
+                .expect("missing default crate root, specify a main.rs or lib.rs");
+            crate_graph.add_crate_root(
+                crate_root,
+                Edition::CURRENT,
+                Some(CrateName::new("test").unwrap().into()),
+                None,
+                default_cfg.clone(),
+                default_cfg,
+                Env::default(),
+                Ok(Vec::new()),
+                false,
+                CrateOrigin::CratesIo { repo: None },
+            );
+        } else {
+            for (from, to, prelude) in crate_deps {
+                let from_id = crates[&from];
+                let to_id = crates[&to];
+                crate_graph
+                    .add_dep(
+                        from_id,
+                        Dependency::with_prelude(CrateName::new(&to).unwrap(), to_id, prelude),
+                    )
+                    .unwrap();
+            }
+        }
+
+        if let Some(mini_core) = mini_core {
+            let core_file = file_id;
+            file_id.0 += 1;
+
+            let mut fs = FileSet::default();
+            fs.insert(core_file, VfsPath::new_virtual_path("/sysroot/core/lib.rs".to_string()));
+            roots.push(SourceRoot::new_library(fs));
+
+            change.change_file(core_file, Some(Arc::new(mini_core.source_code())));
+
+            let all_crates = crate_graph.crates_in_topological_order();
+
+            let core_crate = crate_graph.add_crate_root(
+                core_file,
+                Edition::Edition2021,
+                Some(CrateDisplayName::from_canonical_name("core".to_string())),
+                None,
+                CfgOptions::default(),
+                CfgOptions::default(),
+                Env::default(),
+                Ok(Vec::new()),
+                false,
+                CrateOrigin::Lang(LangCrateOrigin::Core),
+            );
+
+            for krate in all_crates {
+                crate_graph
+                    .add_dep(krate, Dependency::new(CrateName::new("core").unwrap(), core_crate))
+                    .unwrap();
+            }
+        }
+
+        if !proc_macro_names.is_empty() {
+            let proc_lib_file = file_id;
+            file_id.0 += 1;
+
+            proc_macros.extend(default_test_proc_macros());
+            let (proc_macro, source) = filter_test_proc_macros(&proc_macro_names, proc_macros);
+            let mut fs = FileSet::default();
+            fs.insert(
+                proc_lib_file,
+                VfsPath::new_virtual_path("/sysroot/proc_macros/lib.rs".to_string()),
+            );
+            roots.push(SourceRoot::new_library(fs));
+
+            change.change_file(proc_lib_file, Some(Arc::new(source)));
+
+            let all_crates = crate_graph.crates_in_topological_order();
+
+            let proc_macros_crate = crate_graph.add_crate_root(
+                proc_lib_file,
+                Edition::Edition2021,
+                Some(CrateDisplayName::from_canonical_name("proc_macros".to_string())),
+                None,
+                CfgOptions::default(),
+                CfgOptions::default(),
+                Env::default(),
+                Ok(proc_macro),
+                true,
+                CrateOrigin::CratesIo { repo: None },
+            );
+
+            for krate in all_crates {
+                crate_graph
+                    .add_dep(
+                        krate,
+                        Dependency::new(CrateName::new("proc_macros").unwrap(), proc_macros_crate),
+                    )
+                    .unwrap();
+            }
+        }
+
+        let root = match current_source_root_kind {
+            SourceRootKind::Local => SourceRoot::new_local(mem::take(&mut file_set)),
+            SourceRootKind::Library => SourceRoot::new_library(mem::take(&mut file_set)),
+        };
+        roots.push(root);
+        change.set_roots(roots);
+        change.set_crate_graph(crate_graph);
+
+        ChangeFixture { file_position, files, change }
+    }
+}
+
+fn default_test_proc_macros() -> [(String, ProcMacro); 4] {
+    [
+        (
+            r#"
+#[proc_macro_attribute]
+pub fn identity(_attr: TokenStream, item: TokenStream) -> TokenStream {
+    item
+}
+"#
+            .into(),
+            ProcMacro {
+                name: "identity".into(),
+                kind: crate::ProcMacroKind::Attr,
+                expander: Arc::new(IdentityProcMacroExpander),
+            },
+        ),
+        (
+            r#"
+#[proc_macro_derive(DeriveIdentity)]
+pub fn derive_identity(item: TokenStream) -> TokenStream {
+    item
+}
+"#
+            .into(),
+            ProcMacro {
+                name: "DeriveIdentity".into(),
+                kind: crate::ProcMacroKind::CustomDerive,
+                expander: Arc::new(IdentityProcMacroExpander),
+            },
+        ),
+        (
+            r#"
+#[proc_macro_attribute]
+pub fn input_replace(attr: TokenStream, _item: TokenStream) -> TokenStream {
+    attr
+}
+"#
+            .into(),
+            ProcMacro {
+                name: "input_replace".into(),
+                kind: crate::ProcMacroKind::Attr,
+                expander: Arc::new(AttributeInputReplaceProcMacroExpander),
+            },
+        ),
+        (
+            r#"
+#[proc_macro]
+pub fn mirror(input: TokenStream) -> TokenStream {
+    input
+}
+"#
+            .into(),
+            ProcMacro {
+                name: "mirror".into(),
+                kind: crate::ProcMacroKind::FuncLike,
+                expander: Arc::new(MirrorProcMacroExpander),
+            },
+        ),
+    ]
+}
+
+fn filter_test_proc_macros(
+    proc_macro_names: &[String],
+    proc_macro_defs: Vec<(String, ProcMacro)>,
+) -> (Vec<ProcMacro>, String) {
+    // The source here is only required so that paths to the macros exist and are resolvable.
+    let mut source = String::new();
+    let mut proc_macros = Vec::new();
+
+    for (c, p) in proc_macro_defs {
+        if !proc_macro_names.iter().any(|name| name == &stdx::to_lower_snake_case(&p.name)) {
+            continue;
+        }
+        proc_macros.push(p);
+        source += &c;
+    }
+
+    (proc_macros, source)
+}
+
+#[derive(Debug, Clone, Copy)]
+enum SourceRootKind {
+    Local,
+    Library,
+}
+
+#[derive(Debug)]
+struct FileMeta {
+    path: String,
+    krate: Option<(String, CrateOrigin, Option<String>)>,
+    deps: Vec<String>,
+    extern_prelude: Vec<String>,
+    cfg: CfgOptions,
+    edition: Edition,
+    env: Env,
+    introduce_new_source_root: Option<SourceRootKind>,
+}
+
+fn parse_crate(crate_str: String) -> (String, CrateOrigin, Option<String>) {
+    if let Some((a, b)) = crate_str.split_once('@') {
+        let (version, origin) = match b.split_once(':') {
+            Some(("CratesIo", data)) => match data.split_once(',') {
+                Some((version, url)) => {
+                    (version, CrateOrigin::CratesIo { repo: Some(url.to_owned()) })
+                }
+                _ => panic!("Bad crates.io parameter: {}", data),
+            },
+            _ => panic!("Bad string for crate origin: {}", b),
+        };
+        (a.to_owned(), origin, Some(version.to_string()))
+    } else {
+        let crate_origin = match &*crate_str {
+            "std" => CrateOrigin::Lang(LangCrateOrigin::Std),
+            "core" => CrateOrigin::Lang(LangCrateOrigin::Core),
+            _ => CrateOrigin::CratesIo { repo: None },
+        };
+        (crate_str, crate_origin, None)
+    }
+}
+
+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()));
+        let deps = f.deps;
+        FileMeta {
+            path: f.path,
+            krate: f.krate.map(parse_crate),
+            extern_prelude: f.extern_prelude.unwrap_or_else(|| deps.clone()),
+            deps,
+            cfg,
+            edition: f.edition.as_ref().map_or(Edition::CURRENT, |v| Edition::from_str(v).unwrap()),
+            env: f.env.into_iter().collect(),
+            introduce_new_source_root: f.introduce_new_source_root.map(|kind| match &*kind {
+                "local" => SourceRootKind::Local,
+                "library" => SourceRootKind::Library,
+                invalid => panic!("invalid source root kind '{}'", invalid),
+            }),
+        }
+    }
+}
+
+// Identity mapping
+#[derive(Debug)]
+struct IdentityProcMacroExpander;
+impl ProcMacroExpander for IdentityProcMacroExpander {
+    fn expand(
+        &self,
+        subtree: &Subtree,
+        _: Option<&Subtree>,
+        _: &Env,
+    ) -> Result<Subtree, ProcMacroExpansionError> {
+        Ok(subtree.clone())
+    }
+}
+
+// Pastes the attribute input as its output
+#[derive(Debug)]
+struct AttributeInputReplaceProcMacroExpander;
+impl ProcMacroExpander for AttributeInputReplaceProcMacroExpander {
+    fn expand(
+        &self,
+        _: &Subtree,
+        attrs: Option<&Subtree>,
+        _: &Env,
+    ) -> Result<Subtree, ProcMacroExpansionError> {
+        attrs
+            .cloned()
+            .ok_or_else(|| ProcMacroExpansionError::Panic("Expected attribute input".into()))
+    }
+}
+
+#[derive(Debug)]
+struct MirrorProcMacroExpander;
+impl ProcMacroExpander for MirrorProcMacroExpander {
+    fn expand(
+        &self,
+        input: &Subtree,
+        _: Option<&Subtree>,
+        _: &Env,
+    ) -> Result<Subtree, ProcMacroExpansionError> {
+        fn traverse(input: &Subtree) -> Subtree {
+            let mut res = Subtree::default();
+            res.delimiter = input.delimiter;
+            for tt in input.token_trees.iter().rev() {
+                let tt = match tt {
+                    tt::TokenTree::Leaf(leaf) => tt::TokenTree::Leaf(leaf.clone()),
+                    tt::TokenTree::Subtree(sub) => tt::TokenTree::Subtree(traverse(sub)),
+                };
+                res.token_trees.push(tt);
+            }
+            res
+        }
+        Ok(traverse(input))
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/base-db/src/input.rs b/src/tools/rust-analyzer/crates/base-db/src/input.rs
new file mode 100644
index 000000000..9b5a10acf
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/base-db/src/input.rs
@@ -0,0 +1,792 @@
+//! This module specifies the input to rust-analyzer. In some sense, this is
+//! **the** most important module, because all other fancy stuff is strictly
+//! derived from this input.
+//!
+//! Note that neither this module, nor any other part of the analyzer's core do
+//! 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, iter::FromIterator, ops, panic::RefUnwindSafe, str::FromStr, sync::Arc};
+
+use cfg::CfgOptions;
+use rustc_hash::{FxHashMap, FxHashSet};
+use syntax::SmolStr;
+use tt::Subtree;
+use vfs::{file_set::FileSet, FileId, VfsPath};
+
+/// 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
+/// Rust crate. Source roots *might* be nested: in this case, a file belongs to
+/// the nearest enclosing source root. Paths to files are always relative to a
+/// source root, and the analyzer does not know the root path of the source root at
+/// all. So, a file from one source root can't refer to a file in another source
+/// root by path.
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
+pub struct SourceRootId(pub u32);
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct SourceRoot {
+    /// Sysroot or crates.io library.
+    ///
+    /// Libraries are considered mostly immutable, this assumption is used to
+    /// optimize salsa's query structure
+    pub is_library: bool,
+    pub(crate) file_set: FileSet,
+}
+
+impl SourceRoot {
+    pub fn new_local(file_set: FileSet) -> SourceRoot {
+        SourceRoot { is_library: false, file_set }
+    }
+    pub fn new_library(file_set: FileSet) -> SourceRoot {
+        SourceRoot { is_library: true, file_set }
+    }
+    pub fn path_for_file(&self, file: &FileId) -> Option<&VfsPath> {
+        self.file_set.path_for_file(file)
+    }
+    pub fn file_for_path(&self, path: &VfsPath) -> Option<&FileId> {
+        self.file_set.file_for_path(path)
+    }
+    pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
+        self.file_set.iter()
+    }
+}
+
+/// `CrateGraph` is a bit of information which turns a set of text files into a
+/// number of Rust crates.
+///
+/// Each crate is defined by the `FileId` of its root module, the set of enabled
+/// `cfg` flags and the set of dependencies.
+///
+/// Note that, due to cfg's, there might be several crates for a single `FileId`!
+///
+/// For the purposes of analysis, a crate does not have a name. Instead, names
+/// are specified on dependency edges. That is, a crate might be known under
+/// different names in different dependent crates.
+///
+/// Note that `CrateGraph` is build-system agnostic: it's a concept of the Rust
+/// language proper, not a concept of the build system. In practice, we get
+/// `CrateGraph` by lowering `cargo metadata` output.
+///
+/// `CrateGraph` is `!Serialize` by design, see
+/// <https://github.com/rust-lang/rust-analyzer/blob/master/docs/dev/architecture.md#serialization>
+#[derive(Debug, Clone, Default /* Serialize, Deserialize */)]
+pub struct CrateGraph {
+    arena: FxHashMap<CrateId, CrateData>,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct CrateId(pub u32);
+
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub struct CrateName(SmolStr);
+
+impl CrateName {
+    /// Creates a crate name, checking for dashes in the string provided.
+    /// Dashes are not allowed in the crate names,
+    /// hence the input string is returned as `Err` for those cases.
+    pub fn new(name: &str) -> Result<CrateName, &str> {
+        if name.contains('-') {
+            Err(name)
+        } else {
+            Ok(Self(SmolStr::new(name)))
+        }
+    }
+
+    /// Creates a crate name, unconditionally replacing the dashes with underscores.
+    pub fn normalize_dashes(name: &str) -> CrateName {
+        Self(SmolStr::new(name.replace('-', "_")))
+    }
+
+    pub fn as_smol_str(&self) -> &SmolStr {
+        &self.0
+    }
+}
+
+impl fmt::Display for CrateName {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+impl ops::Deref for CrateName {
+    type Target = str;
+    fn deref(&self) -> &str {
+        &*self.0
+    }
+}
+
+/// Origin of the crates. It is used in emitting monikers.
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub enum CrateOrigin {
+    /// Crates that are from crates.io official registry,
+    CratesIo { repo: Option<String> },
+    /// Crates that are provided by the language, like std, core, proc-macro, ...
+    Lang(LangCrateOrigin),
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub enum LangCrateOrigin {
+    Alloc,
+    Core,
+    ProcMacro,
+    Std,
+    Test,
+    Other,
+}
+
+impl From<&str> for LangCrateOrigin {
+    fn from(s: &str) -> Self {
+        match s {
+            "alloc" => LangCrateOrigin::Alloc,
+            "core" => LangCrateOrigin::Core,
+            "proc-macro" => LangCrateOrigin::ProcMacro,
+            "std" => LangCrateOrigin::Std,
+            "test" => LangCrateOrigin::Test,
+            _ => LangCrateOrigin::Other,
+        }
+    }
+}
+
+impl fmt::Display for LangCrateOrigin {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let text = match self {
+            LangCrateOrigin::Alloc => "alloc",
+            LangCrateOrigin::Core => "core",
+            LangCrateOrigin::ProcMacro => "proc_macro",
+            LangCrateOrigin::Std => "std",
+            LangCrateOrigin::Test => "test",
+            LangCrateOrigin::Other => "other",
+        };
+        f.write_str(text)
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub struct CrateDisplayName {
+    // The name we use to display various paths (with `_`).
+    crate_name: CrateName,
+    // The name as specified in Cargo.toml (with `-`).
+    canonical_name: String,
+}
+
+impl CrateDisplayName {
+    pub fn canonical_name(&self) -> &str {
+        &self.canonical_name
+    }
+    pub fn crate_name(&self) -> &CrateName {
+        &self.crate_name
+    }
+}
+
+impl From<CrateName> for CrateDisplayName {
+    fn from(crate_name: CrateName) -> CrateDisplayName {
+        let canonical_name = crate_name.to_string();
+        CrateDisplayName { crate_name, canonical_name }
+    }
+}
+
+impl fmt::Display for CrateDisplayName {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.crate_name.fmt(f)
+    }
+}
+
+impl ops::Deref for CrateDisplayName {
+    type Target = str;
+    fn deref(&self) -> &str {
+        &*self.crate_name
+    }
+}
+
+impl CrateDisplayName {
+    pub fn from_canonical_name(canonical_name: String) -> CrateDisplayName {
+        let crate_name = CrateName::normalize_dashes(&canonical_name);
+        CrateDisplayName { crate_name, canonical_name }
+    }
+}
+
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+pub struct ProcMacroId(pub u32);
+
+#[derive(Copy, Clone, Eq, PartialEq, Debug, Hash)]
+pub enum ProcMacroKind {
+    CustomDerive,
+    FuncLike,
+    Attr,
+}
+
+pub trait ProcMacroExpander: fmt::Debug + Send + Sync + RefUnwindSafe {
+    fn expand(
+        &self,
+        subtree: &Subtree,
+        attrs: Option<&Subtree>,
+        env: &Env,
+    ) -> Result<Subtree, ProcMacroExpansionError>;
+}
+
+pub enum ProcMacroExpansionError {
+    Panic(String),
+    /// Things like "proc macro server was killed by OOM".
+    System(String),
+}
+
+pub type ProcMacroLoadResult = Result<Vec<ProcMacro>, String>;
+
+#[derive(Debug, Clone)]
+pub struct ProcMacro {
+    pub name: SmolStr,
+    pub kind: ProcMacroKind,
+    pub expander: Arc<dyn ProcMacroExpander>,
+}
+
+#[derive(Debug, Clone)]
+pub struct CrateData {
+    pub root_file_id: FileId,
+    pub edition: Edition,
+    pub version: Option<String>,
+    /// A name used in the package's project declaration: for Cargo projects,
+    /// its `[package].name` can be different for other project types or even
+    /// absent (a dummy crate for the code snippet, for example).
+    ///
+    /// For purposes of analysis, crates are anonymous (only names in
+    /// `Dependency` matters), this name should only be used for UI.
+    pub display_name: Option<CrateDisplayName>,
+    pub cfg_options: CfgOptions,
+    pub potential_cfg_options: CfgOptions,
+    pub env: Env,
+    pub dependencies: Vec<Dependency>,
+    pub proc_macro: ProcMacroLoadResult,
+    pub origin: CrateOrigin,
+    pub is_proc_macro: bool,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub enum Edition {
+    Edition2015,
+    Edition2018,
+    Edition2021,
+}
+
+impl Edition {
+    pub const CURRENT: Edition = Edition::Edition2018;
+}
+
+#[derive(Default, Debug, Clone, PartialEq, Eq)]
+pub struct Env {
+    entries: FxHashMap<String, String>,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct Dependency {
+    pub crate_id: CrateId,
+    pub name: CrateName,
+    prelude: bool,
+}
+
+impl Dependency {
+    pub fn new(name: CrateName, crate_id: CrateId) -> Self {
+        Self { name, crate_id, prelude: true }
+    }
+
+    pub fn with_prelude(name: CrateName, crate_id: CrateId, prelude: bool) -> Self {
+        Self { name, crate_id, prelude }
+    }
+
+    /// Whether this dependency is to be added to the depending crate's extern prelude.
+    pub fn is_prelude(&self) -> bool {
+        self.prelude
+    }
+}
+
+impl CrateGraph {
+    pub fn add_crate_root(
+        &mut self,
+        root_file_id: FileId,
+        edition: Edition,
+        display_name: Option<CrateDisplayName>,
+        version: Option<String>,
+        cfg_options: CfgOptions,
+        potential_cfg_options: CfgOptions,
+        env: Env,
+        proc_macro: ProcMacroLoadResult,
+        is_proc_macro: bool,
+        origin: CrateOrigin,
+    ) -> CrateId {
+        let data = CrateData {
+            root_file_id,
+            edition,
+            version,
+            display_name,
+            cfg_options,
+            potential_cfg_options,
+            env,
+            proc_macro,
+            dependencies: Vec::new(),
+            origin,
+            is_proc_macro,
+        };
+        let crate_id = CrateId(self.arena.len() as u32);
+        let prev = self.arena.insert(crate_id, data);
+        assert!(prev.is_none());
+        crate_id
+    }
+
+    pub fn add_dep(
+        &mut self,
+        from: CrateId,
+        dep: Dependency,
+    ) -> Result<(), CyclicDependenciesError> {
+        let _p = profile::span("add_dep");
+
+        // Check if adding a dep from `from` to `to` creates a cycle. To figure
+        // that out, look for a  path in the *opposite* direction, from `to` to
+        // `from`.
+        if let Some(path) = self.find_path(&mut FxHashSet::default(), dep.crate_id, from) {
+            let path = path.into_iter().map(|it| (it, self[it].display_name.clone())).collect();
+            let err = CyclicDependenciesError { path };
+            assert!(err.from().0 == from && err.to().0 == dep.crate_id);
+            return Err(err);
+        }
+
+        self.arena.get_mut(&from).unwrap().add_dep(dep);
+        Ok(())
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.arena.is_empty()
+    }
+
+    pub fn iter(&self) -> impl Iterator<Item = CrateId> + '_ {
+        self.arena.keys().copied()
+    }
+
+    /// Returns an iterator over all transitive dependencies of the given crate,
+    /// including the crate itself.
+    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.into_iter()
+    }
+
+    /// Returns all transitive reverse dependencies of the given crate,
+    /// including the crate itself.
+    pub fn transitive_rev_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> {
+        let mut worklist = vec![of];
+        let mut rev_deps = FxHashSet::default();
+        rev_deps.insert(of);
+
+        let mut inverted_graph = FxHashMap::<_, Vec<_>>::default();
+        self.arena.iter().for_each(|(&krate, data)| {
+            data.dependencies
+                .iter()
+                .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate))
+        });
+
+        while let Some(krate) = worklist.pop() {
+            if let Some(krate_rev_deps) = inverted_graph.get(&krate) {
+                krate_rev_deps
+                    .iter()
+                    .copied()
+                    .filter(|&rev_dep| rev_deps.insert(rev_dep))
+                    .for_each(|rev_dep| worklist.push(rev_dep));
+            }
+        }
+
+        rev_deps.into_iter()
+    }
+
+    /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
+    /// come before the crate itself).
+    pub fn crates_in_topological_order(&self) -> Vec<CrateId> {
+        let mut res = Vec::new();
+        let mut visited = FxHashSet::default();
+
+        for krate in self.arena.keys().copied() {
+            go(self, &mut visited, &mut res, krate);
+        }
+
+        return res;
+
+        fn go(
+            graph: &CrateGraph,
+            visited: &mut FxHashSet<CrateId>,
+            res: &mut Vec<CrateId>,
+            source: CrateId,
+        ) {
+            if !visited.insert(source) {
+                return;
+            }
+            for dep in graph[source].dependencies.iter() {
+                go(graph, visited, res, dep.crate_id)
+            }
+            res.push(source)
+        }
+    }
+
+    // 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, _) =
+            self.arena.iter().find(|(_crate_id, data)| data.root_file_id == file_id)?;
+        Some(crate_id)
+    }
+
+    /// Extends this crate graph by adding a complete disjoint second crate
+    /// graph.
+    ///
+    /// The ids of the crates in the `other` graph are shifted by the return
+    /// amount.
+    pub fn extend(&mut self, other: CrateGraph) -> u32 {
+        let start = self.arena.len() as u32;
+        self.arena.extend(other.arena.into_iter().map(|(id, mut data)| {
+            let new_id = id.shift(start);
+            for dep in &mut data.dependencies {
+                dep.crate_id = dep.crate_id.shift(start);
+            }
+            (new_id, data)
+        }));
+        start
+    }
+
+    fn find_path(
+        &self,
+        visited: &mut FxHashSet<CrateId>,
+        from: CrateId,
+        to: CrateId,
+    ) -> Option<Vec<CrateId>> {
+        if !visited.insert(from) {
+            return None;
+        }
+
+        if from == to {
+            return Some(vec![to]);
+        }
+
+        for dep in &self[from].dependencies {
+            let crate_id = dep.crate_id;
+            if let Some(mut path) = self.find_path(visited, crate_id, to) {
+                path.push(from);
+                return Some(path);
+            }
+        }
+
+        None
+    }
+
+    // Work around for https://github.com/rust-lang/rust-analyzer/issues/6038.
+    // As hacky as it gets.
+    pub fn patch_cfg_if(&mut self) -> bool {
+        let cfg_if = self.hacky_find_crate("cfg_if");
+        let std = self.hacky_find_crate("std");
+        match (cfg_if, std) {
+            (Some(cfg_if), Some(std)) => {
+                self.arena.get_mut(&cfg_if).unwrap().dependencies.clear();
+                self.arena
+                    .get_mut(&std)
+                    .unwrap()
+                    .dependencies
+                    .push(Dependency::new(CrateName::new("cfg_if").unwrap(), cfg_if));
+                true
+            }
+            _ => false,
+        }
+    }
+
+    fn hacky_find_crate(&self, display_name: &str) -> Option<CrateId> {
+        self.iter().find(|it| self[*it].display_name.as_deref() == Some(display_name))
+    }
+}
+
+impl ops::Index<CrateId> for CrateGraph {
+    type Output = CrateData;
+    fn index(&self, crate_id: CrateId) -> &CrateData {
+        &self.arena[&crate_id]
+    }
+}
+
+impl CrateId {
+    fn shift(self, amount: u32) -> CrateId {
+        CrateId(self.0 + amount)
+    }
+}
+
+impl CrateData {
+    fn add_dep(&mut self, dep: Dependency) {
+        self.dependencies.push(dep)
+    }
+}
+
+impl FromStr for Edition {
+    type Err = ParseEditionError;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        let res = match s {
+            "2015" => Edition::Edition2015,
+            "2018" => Edition::Edition2018,
+            "2021" => Edition::Edition2021,
+            _ => return Err(ParseEditionError { invalid_input: s.to_string() }),
+        };
+        Ok(res)
+    }
+}
+
+impl fmt::Display for Edition {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.write_str(match self {
+            Edition::Edition2015 => "2015",
+            Edition::Edition2018 => "2018",
+            Edition::Edition2021 => "2021",
+        })
+    }
+}
+
+impl FromIterator<(String, String)> for Env {
+    fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
+        Env { entries: FromIterator::from_iter(iter) }
+    }
+}
+
+impl Env {
+    pub fn set(&mut self, env: &str, value: String) {
+        self.entries.insert(env.to_owned(), value);
+    }
+
+    pub fn get(&self, env: &str) -> Option<String> {
+        self.entries.get(env).cloned()
+    }
+
+    pub fn iter(&self) -> impl Iterator<Item = (&str, &str)> {
+        self.entries.iter().map(|(k, v)| (k.as_str(), v.as_str()))
+    }
+}
+
+#[derive(Debug)]
+pub struct ParseEditionError {
+    invalid_input: String,
+}
+
+impl fmt::Display for ParseEditionError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "invalid edition: {:?}", self.invalid_input)
+    }
+}
+
+impl std::error::Error for ParseEditionError {}
+
+#[derive(Debug)]
+pub struct CyclicDependenciesError {
+    path: Vec<(CrateId, Option<CrateDisplayName>)>,
+}
+
+impl CyclicDependenciesError {
+    fn from(&self) -> &(CrateId, Option<CrateDisplayName>) {
+        self.path.first().unwrap()
+    }
+    fn to(&self) -> &(CrateId, Option<CrateDisplayName>) {
+        self.path.last().unwrap()
+    }
+}
+
+impl fmt::Display for CyclicDependenciesError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let render = |(id, name): &(CrateId, Option<CrateDisplayName>)| match name {
+            Some(it) => format!("{}({:?})", it, id),
+            None => format!("{:?}", id),
+        };
+        let path = self.path.iter().rev().map(render).collect::<Vec<String>>().join(" -> ");
+        write!(
+            f,
+            "cyclic deps: {} -> {}, alternative path: {}",
+            render(self.from()),
+            render(self.to()),
+            path
+        )
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::CrateOrigin;
+
+    use super::{CfgOptions, CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
+
+    #[test]
+    fn detect_cyclic_dependency_indirect() {
+        let mut graph = CrateGraph::default();
+        let crate1 = graph.add_crate_root(
+            FileId(1u32),
+            Edition2018,
+            None,
+            None,
+            CfgOptions::default(),
+            CfgOptions::default(),
+            Env::default(),
+            Ok(Vec::new()),
+            false,
+            CrateOrigin::CratesIo { repo: None },
+        );
+        let crate2 = graph.add_crate_root(
+            FileId(2u32),
+            Edition2018,
+            None,
+            None,
+            CfgOptions::default(),
+            CfgOptions::default(),
+            Env::default(),
+            Ok(Vec::new()),
+            false,
+            CrateOrigin::CratesIo { repo: None },
+        );
+        let crate3 = graph.add_crate_root(
+            FileId(3u32),
+            Edition2018,
+            None,
+            None,
+            CfgOptions::default(),
+            CfgOptions::default(),
+            Env::default(),
+            Ok(Vec::new()),
+            false,
+            CrateOrigin::CratesIo { repo: None },
+        );
+        assert!(graph
+            .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
+            .is_ok());
+        assert!(graph
+            .add_dep(crate2, Dependency::new(CrateName::new("crate3").unwrap(), crate3))
+            .is_ok());
+        assert!(graph
+            .add_dep(crate3, Dependency::new(CrateName::new("crate1").unwrap(), crate1))
+            .is_err());
+    }
+
+    #[test]
+    fn detect_cyclic_dependency_direct() {
+        let mut graph = CrateGraph::default();
+        let crate1 = graph.add_crate_root(
+            FileId(1u32),
+            Edition2018,
+            None,
+            None,
+            CfgOptions::default(),
+            CfgOptions::default(),
+            Env::default(),
+            Ok(Vec::new()),
+            false,
+            CrateOrigin::CratesIo { repo: None },
+        );
+        let crate2 = graph.add_crate_root(
+            FileId(2u32),
+            Edition2018,
+            None,
+            None,
+            CfgOptions::default(),
+            CfgOptions::default(),
+            Env::default(),
+            Ok(Vec::new()),
+            false,
+            CrateOrigin::CratesIo { repo: None },
+        );
+        assert!(graph
+            .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
+            .is_ok());
+        assert!(graph
+            .add_dep(crate2, Dependency::new(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,
+            None,
+            CfgOptions::default(),
+            CfgOptions::default(),
+            Env::default(),
+            Ok(Vec::new()),
+            false,
+            CrateOrigin::CratesIo { repo: None },
+        );
+        let crate2 = graph.add_crate_root(
+            FileId(2u32),
+            Edition2018,
+            None,
+            None,
+            CfgOptions::default(),
+            CfgOptions::default(),
+            Env::default(),
+            Ok(Vec::new()),
+            false,
+            CrateOrigin::CratesIo { repo: None },
+        );
+        let crate3 = graph.add_crate_root(
+            FileId(3u32),
+            Edition2018,
+            None,
+            None,
+            CfgOptions::default(),
+            CfgOptions::default(),
+            Env::default(),
+            Ok(Vec::new()),
+            false,
+            CrateOrigin::CratesIo { repo: None },
+        );
+        assert!(graph
+            .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
+            .is_ok());
+        assert!(graph
+            .add_dep(crate2, Dependency::new(CrateName::new("crate3").unwrap(), crate3))
+            .is_ok());
+    }
+
+    #[test]
+    fn dashes_are_normalized() {
+        let mut graph = CrateGraph::default();
+        let crate1 = graph.add_crate_root(
+            FileId(1u32),
+            Edition2018,
+            None,
+            None,
+            CfgOptions::default(),
+            CfgOptions::default(),
+            Env::default(),
+            Ok(Vec::new()),
+            false,
+            CrateOrigin::CratesIo { repo: None },
+        );
+        let crate2 = graph.add_crate_root(
+            FileId(2u32),
+            Edition2018,
+            None,
+            None,
+            CfgOptions::default(),
+            CfgOptions::default(),
+            Env::default(),
+            Ok(Vec::new()),
+            false,
+            CrateOrigin::CratesIo { repo: None },
+        );
+        assert!(graph
+            .add_dep(
+                crate1,
+                Dependency::new(CrateName::normalize_dashes("crate-name-with-dashes"), crate2)
+            )
+            .is_ok());
+        assert_eq!(
+            graph[crate1].dependencies,
+            vec![Dependency::new(CrateName::new("crate_name_with_dashes").unwrap(), crate2)]
+        );
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/base-db/src/lib.rs b/src/tools/rust-analyzer/crates/base-db/src/lib.rs
new file mode 100644
index 000000000..2d0a95b09
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/base-db/src/lib.rs
@@ -0,0 +1,131 @@
+//! base_db defines basic database traits. The concrete DB is defined by ide.
+
+#![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)]
+
+mod input;
+mod change;
+pub mod fixture;
+
+use std::{panic, sync::Arc};
+
+use rustc_hash::FxHashSet;
+use syntax::{ast, Parse, SourceFile, TextRange, TextSize};
+
+pub use crate::{
+    change::Change,
+    input::{
+        CrateData, CrateDisplayName, CrateGraph, CrateId, CrateName, CrateOrigin, Dependency,
+        Edition, Env, LangCrateOrigin, ProcMacro, ProcMacroExpander, ProcMacroExpansionError,
+        ProcMacroId, ProcMacroKind, ProcMacroLoadResult, SourceRoot, SourceRootId,
+    },
+};
+pub use salsa::{self, Cancelled};
+pub use vfs::{file_set::FileSet, AnchoredPath, AnchoredPathBuf, FileId, VfsPath};
+
+#[macro_export]
+macro_rules! impl_intern_key {
+    ($name:ident) => {
+        impl $crate::salsa::InternKey for $name {
+            fn from_intern_id(v: $crate::salsa::InternId) -> Self {
+                $name(v)
+            }
+            fn as_intern_id(&self) -> $crate::salsa::InternId {
+                self.0
+            }
+        }
+    };
+}
+
+pub trait Upcast<T: ?Sized> {
+    fn upcast(&self) -> &T;
+}
+
+#[derive(Clone, Copy, Debug)]
+pub struct FilePosition {
+    pub file_id: FileId,
+    pub offset: TextSize,
+}
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
+pub struct FileRange {
+    pub file_id: FileId,
+    pub range: TextRange,
+}
+
+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_path(&self, path: AnchoredPath<'_>) -> Option<FileId>;
+    fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>>;
+}
+
+/// Database which stores all significant input facts: source code and project
+/// model. Everything else in rust-analyzer is derived from these queries.
+#[salsa::query_group(SourceDatabaseStorage)]
+pub trait SourceDatabase: FileLoader + std::fmt::Debug {
+    // Parses the file into the syntax tree.
+    #[salsa::invoke(parse_query)]
+    fn parse(&self, file_id: FileId) -> Parse<ast::SourceFile>;
+
+    /// The crate graph.
+    #[salsa::input]
+    fn crate_graph(&self) -> Arc<CrateGraph>;
+}
+
+fn parse_query(db: &dyn SourceDatabase, file_id: FileId) -> Parse<ast::SourceFile> {
+    let _p = profile::span("parse_query").detail(|| format!("{:?}", file_id));
+    let text = db.file_text(file_id);
+    SourceFile::parse(&*text)
+}
+
+/// We don't want to give HIR knowledge of source roots, hence we extract these
+/// methods into a separate DB.
+#[salsa::query_group(SourceDatabaseExtStorage)]
+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.
+    /// Source root of the file.
+    #[salsa::input]
+    fn file_source_root(&self, file_id: FileId) -> SourceRootId;
+    /// Contents of the source root.
+    #[salsa::input]
+    fn source_root(&self, id: SourceRootId) -> Arc<SourceRoot>;
+
+    fn source_root_crates(&self, 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()
+        .filter(|&krate| {
+            let root_file = graph[krate].root_file_id;
+            db.file_source_root(root_file) == id
+        })
+        .collect();
+    Arc::new(res)
+}
+
+/// Silly workaround for cyclic deps between the traits
+pub struct FileLoaderDelegate<T>(pub T);
+
+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_path(&self, path: AnchoredPath<'_>) -> Option<FileId> {
+        // FIXME: this *somehow* should be platform agnostic...
+        let source_root = self.0.file_source_root(path.anchor);
+        let source_root = self.0.source_root(source_root);
+        source_root.file_set.resolve_path(path)
+    }
+
+    fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>> {
+        let _p = profile::span("relevant_crates");
+        let source_root = self.0.file_source_root(file_id);
+        self.0.source_root_crates(source_root)
+    }
+}