From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- src/tools/rust-analyzer/crates/base-db/Cargo.toml | 22 + .../rust-analyzer/crates/base-db/src/change.rs | 85 +++ .../rust-analyzer/crates/base-db/src/fixture.rs | 494 +++++++++++++ .../rust-analyzer/crates/base-db/src/input.rs | 792 +++++++++++++++++++++ src/tools/rust-analyzer/crates/base-db/src/lib.rs | 131 ++++ 5 files changed, 1524 insertions(+) create mode 100644 src/tools/rust-analyzer/crates/base-db/Cargo.toml create mode 100644 src/tools/rust-analyzer/crates/base-db/src/change.rs create mode 100644 src/tools/rust-analyzer/crates/base-db/src/fixture.rs create mode 100644 src/tools/rust-analyzer/crates/base-db/src/input.rs create mode 100644 src/tools/rust-analyzer/crates/base-db/src/lib.rs (limited to 'src/tools/rust-analyzer/crates/base-db') 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>, + pub files_changed: Vec<(FileId, Option>)>, + pub crate_graph: Option, +} + +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) { + self.roots = Some(roots); + } + + pub fn change_file(&mut self, file_id: FileId, new_text: Option>) { + 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) { + 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 WithFixture for DB {} + +pub struct ChangeFixture { + pub file_position: Option<(FileId, RangeOrOffset)>, + pub files: Vec, + 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 = 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, 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)>, + deps: Vec, + extern_prelude: Vec, + cfg: CfgOptions, + edition: Edition, + env: Env, + introduce_new_source_root: Option, +} + +fn parse_crate(crate_str: String) -> (String, CrateOrigin, Option) { + 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 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 { + 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 { + 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 { + 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 + '_ { + 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 +/// +#[derive(Debug, Clone, Default /* Serialize, Deserialize */)] +pub struct CrateGraph { + arena: FxHashMap, +} + +#[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 { + 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 }, + /// 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 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; +} + +pub enum ProcMacroExpansionError { + Panic(String), + /// Things like "proc macro server was killed by OOM". + System(String), +} + +pub type ProcMacroLoadResult = Result, String>; + +#[derive(Debug, Clone)] +pub struct ProcMacro { + pub name: SmolStr, + pub kind: ProcMacroKind, + pub expander: Arc, +} + +#[derive(Debug, Clone)] +pub struct CrateData { + pub root_file_id: FileId, + pub edition: Edition, + pub version: Option, + /// 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, + pub cfg_options: CfgOptions, + pub potential_cfg_options: CfgOptions, + pub env: Env, + pub dependencies: Vec, + 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, +} + +#[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, + version: Option, + 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 + '_ { + 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 { + 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 { + 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 { + 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, + res: &mut Vec, + 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 { + 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, + from: CrateId, + to: CrateId, + ) -> Option> { + 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 { + self.iter().find(|it| self[*it].display_name.as_deref() == Some(display_name)) + } +} + +impl ops::Index 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 { + 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>(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 { + self.entries.get(env).cloned() + } + + pub fn iter(&self) -> impl Iterator { + 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)>, +} + +impl CyclicDependenciesError { + fn from(&self) -> &(CrateId, Option) { + self.path.first().unwrap() + } + fn to(&self) -> &(CrateId, Option) { + self.path.last().unwrap() + } +} + +impl fmt::Display for CyclicDependenciesError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let render = |(id, name): &(CrateId, Option)| match name { + Some(it) => format!("{}({:?})", it, id), + None => format!("{:?}", id), + }; + let path = self.path.iter().rev().map(render).collect::>().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 { + 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; + fn resolve_path(&self, path: AnchoredPath<'_>) -> Option; + fn relevant_crates(&self, file_id: FileId) -> Arc>; +} + +/// 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; + + /// The crate graph. + #[salsa::input] + fn crate_graph(&self) -> Arc; +} + +fn parse_query(db: &dyn SourceDatabase, file_id: FileId) -> Parse { + 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; + /// 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; + + fn source_root_crates(&self, id: SourceRootId) -> Arc>; +} + +fn source_root_crates(db: &dyn SourceDatabaseExt, id: SourceRootId) -> Arc> { + 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(pub T); + +impl FileLoader for FileLoaderDelegate<&'_ T> { + fn file_text(&self, file_id: FileId) -> Arc { + SourceDatabaseExt::file_text(self.0, file_id) + } + fn resolve_path(&self, path: AnchoredPath<'_>) -> Option { + // 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> { + let _p = profile::span("relevant_crates"); + let source_root = self.0.file_source_root(file_id); + self.0.source_root_crates(source_root) + } +} -- cgit v1.2.3