1 //! This module specifies the input to rust-analyzer. In some sense, this is
2 //! **the** most important module, because all other fancy stuff is strictly
3 //! derived from this input.
5 //! Note that neither this module, nor any other part of the analyzer's core do
6 //! actual IO. See `vfs` and `project_model` in the `rust-analyzer` crate for how
7 //! actual IO is done and lowered to input.
9 use std::{fmt, iter::FromIterator, ops, str::FromStr, sync::Arc};
12 use rustc_hash::{FxHashMap, FxHashSet};
14 use tt::TokenExpander;
15 use vfs::{file_set::FileSet, VfsPath};
19 /// Files are grouped into source roots. A source root is a directory on the
20 /// file systems which is watched for changes. Typically it corresponds to a
21 /// Rust crate. Source roots *might* be nested: in this case, a file belongs to
22 /// the nearest enclosing source root. Paths to files are always relative to a
23 /// source root, and the analyzer does not know the root path of the source root at
24 /// all. So, a file from one source root can't refer to a file in another source
26 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
27 pub struct SourceRootId(pub u32);
29 #[derive(Clone, Debug, PartialEq, Eq)]
30 pub struct SourceRoot {
31 /// Sysroot or crates.io library.
33 /// Libraries are considered mostly immutable, this assumption is used to
34 /// optimize salsa's query structure
36 pub(crate) file_set: FileSet,
40 pub fn new_local(file_set: FileSet) -> SourceRoot {
41 SourceRoot { is_library: false, file_set }
43 pub fn new_library(file_set: FileSet) -> SourceRoot {
44 SourceRoot { is_library: true, file_set }
46 pub fn path_for_file(&self, file: &FileId) -> Option<&VfsPath> {
47 self.file_set.path_for_file(file)
49 pub fn file_for_path(&self, path: &VfsPath) -> Option<&FileId> {
50 self.file_set.file_for_path(path)
52 pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
57 /// `CrateGraph` is a bit of information which turns a set of text files into a
58 /// number of Rust crates. Each crate is defined by the `FileId` of its root module,
59 /// the set of cfg flags (not yet implemented) and the set of dependencies. Note
60 /// that, due to cfg's, there might be several crates for a single `FileId`! As
61 /// in the rust-lang proper, a crate does not have a name. Instead, names are
62 /// specified on dependency edges. That is, a crate might be known under
63 /// different names in different dependent crates.
65 /// Note that `CrateGraph` is build-system agnostic: it's a concept of the Rust
66 /// language proper, not a concept of the build system. In practice, we get
67 /// `CrateGraph` by lowering `cargo metadata` output.
68 #[derive(Debug, Clone, Default, PartialEq, Eq)]
69 pub struct CrateGraph {
70 arena: FxHashMap<CrateId, CrateData>,
73 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
74 pub struct CrateId(pub u32);
76 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
77 pub struct CrateName(SmolStr);
80 /// Creates a crate name, checking for dashes in the string provided.
81 /// Dashes are not allowed in the crate names,
82 /// hence the input string is returned as `Err` for those cases.
83 pub fn new(name: &str) -> Result<CrateName, &str> {
84 if name.contains('-') {
87 Ok(Self(SmolStr::new(name)))
91 /// Creates a crate name, unconditionally replacing the dashes with underscores.
92 pub fn normalize_dashes(name: &str) -> CrateName {
93 Self(SmolStr::new(name.replace('-', "_")))
97 impl fmt::Display for CrateName {
98 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
99 write!(f, "{}", self.0)
103 impl ops::Deref for CrateName {
105 fn deref(&self) -> &Self::Target {
110 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
111 pub struct ProcMacroId(pub u32);
113 #[derive(Debug, Clone)]
114 pub struct ProcMacro {
116 pub expander: Arc<dyn TokenExpander>,
119 impl Eq for ProcMacro {}
120 impl PartialEq for ProcMacro {
121 fn eq(&self, other: &ProcMacro) -> bool {
122 self.name == other.name && Arc::ptr_eq(&self.expander, &other.expander)
126 #[derive(Debug, Clone, PartialEq, Eq)]
127 pub struct CrateData {
128 pub root_file_id: FileId,
129 pub edition: Edition,
130 /// The name to display to the end user.
131 /// This actual crate name can be different in a particular dependent crate
132 /// or may even be missing for some cases, such as a dummy crate for the code snippet.
133 pub display_name: Option<String>,
134 pub cfg_options: CfgOptions,
136 pub dependencies: Vec<Dependency>,
137 pub proc_macro: Vec<ProcMacro>,
140 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
146 #[derive(Default, Debug, Clone, PartialEq, Eq)]
148 entries: FxHashMap<String, String>,
151 #[derive(Debug, Clone, PartialEq, Eq)]
152 pub struct Dependency {
153 pub crate_id: CrateId,
158 pub fn add_crate_root(
162 display_name: Option<String>,
163 cfg_options: CfgOptions,
165 proc_macro: Vec<(SmolStr, Arc<dyn tt::TokenExpander>)>,
168 proc_macro.into_iter().map(|(name, it)| ProcMacro { name, expander: it }).collect();
170 let data = CrateData {
171 root_file_id: file_id,
177 dependencies: Vec::new(),
179 let crate_id = CrateId(self.arena.len() as u32);
180 let prev = self.arena.insert(crate_id, data);
181 assert!(prev.is_none());
190 ) -> Result<(), CyclicDependenciesError> {
191 if self.dfs_find(from, to, &mut FxHashSet::default()) {
192 return Err(CyclicDependenciesError);
194 self.arena.get_mut(&from).unwrap().add_dep(name, to);
198 pub fn is_empty(&self) -> bool {
199 self.arena.is_empty()
202 pub fn iter(&self) -> impl Iterator<Item = CrateId> + '_ {
203 self.arena.keys().copied()
206 /// Returns an iterator over all transitive dependencies of the given crate.
207 pub fn transitive_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> + '_ {
208 let mut worklist = vec![of];
209 let mut deps = FxHashSet::default();
211 while let Some(krate) = worklist.pop() {
212 if !deps.insert(krate) {
216 worklist.extend(self[krate].dependencies.iter().map(|dep| dep.crate_id));
223 // FIXME: this only finds one crate with the given root; we could have multiple
224 pub fn crate_id_for_crate_root(&self, file_id: FileId) -> Option<CrateId> {
226 self.arena.iter().find(|(_crate_id, data)| data.root_file_id == file_id)?;
230 /// Extends this crate graph by adding a complete disjoint second crate
233 /// The ids of the crates in the `other` graph are shifted by the return
235 pub fn extend(&mut self, other: CrateGraph) -> u32 {
236 let start = self.arena.len() as u32;
237 self.arena.extend(other.arena.into_iter().map(|(id, mut data)| {
238 let new_id = id.shift(start);
239 for dep in &mut data.dependencies {
240 dep.crate_id = dep.crate_id.shift(start);
247 fn dfs_find(&self, target: CrateId, from: CrateId, visited: &mut FxHashSet<CrateId>) -> bool {
248 if !visited.insert(from) {
256 for dep in &self[from].dependencies {
257 let crate_id = dep.crate_id;
258 if self.dfs_find(target, crate_id, visited) {
266 impl ops::Index<CrateId> for CrateGraph {
267 type Output = CrateData;
268 fn index(&self, crate_id: CrateId) -> &CrateData {
269 &self.arena[&crate_id]
274 pub fn shift(self, amount: u32) -> CrateId {
275 CrateId(self.0 + amount)
280 fn add_dep(&mut self, name: CrateName, crate_id: CrateId) {
281 self.dependencies.push(Dependency { name, crate_id })
285 impl FromStr for Edition {
286 type Err = ParseEditionError;
288 fn from_str(s: &str) -> Result<Self, Self::Err> {
290 "2015" => Edition::Edition2015,
291 "2018" => Edition::Edition2018,
292 _ => return Err(ParseEditionError { invalid_input: s.to_string() }),
298 impl fmt::Display for Edition {
299 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
300 f.write_str(match self {
301 Edition::Edition2015 => "2015",
302 Edition::Edition2018 => "2018",
307 impl FromIterator<(String, String)> for Env {
308 fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
309 Env { entries: FromIterator::from_iter(iter) }
314 pub fn set(&mut self, env: &str, value: String) {
315 self.entries.insert(env.to_owned(), value);
318 pub fn get(&self, env: &str) -> Option<String> {
319 self.entries.get(env).cloned()
324 pub struct ParseEditionError {
325 invalid_input: String,
328 impl fmt::Display for ParseEditionError {
329 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
330 write!(f, "invalid edition: {:?}", self.invalid_input)
334 impl std::error::Error for ParseEditionError {}
337 pub struct CyclicDependenciesError;
341 use super::{CfgOptions, CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
344 fn detect_cyclic_dependency_indirect() {
345 let mut graph = CrateGraph::default();
346 let crate1 = graph.add_crate_root(
350 CfgOptions::default(),
354 let crate2 = graph.add_crate_root(
358 CfgOptions::default(),
362 let crate3 = graph.add_crate_root(
366 CfgOptions::default(),
370 assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
371 assert!(graph.add_dep(crate2, CrateName::new("crate3").unwrap(), crate3).is_ok());
372 assert!(graph.add_dep(crate3, CrateName::new("crate1").unwrap(), crate1).is_err());
376 fn detect_cyclic_dependency_direct() {
377 let mut graph = CrateGraph::default();
378 let crate1 = graph.add_crate_root(
382 CfgOptions::default(),
386 let crate2 = graph.add_crate_root(
390 CfgOptions::default(),
394 assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
395 assert!(graph.add_dep(crate2, CrateName::new("crate2").unwrap(), crate2).is_err());
400 let mut graph = CrateGraph::default();
401 let crate1 = graph.add_crate_root(
405 CfgOptions::default(),
409 let crate2 = graph.add_crate_root(
413 CfgOptions::default(),
417 let crate3 = graph.add_crate_root(
421 CfgOptions::default(),
425 assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
426 assert!(graph.add_dep(crate2, CrateName::new("crate3").unwrap(), crate3).is_ok());
430 fn dashes_are_normalized() {
431 let mut graph = CrateGraph::default();
432 let crate1 = graph.add_crate_root(
436 CfgOptions::default(),
440 let crate2 = graph.add_crate_root(
444 CfgOptions::default(),
449 .add_dep(crate1, CrateName::normalize_dashes("crate-name-with-dashes"), crate2)
452 graph[crate1].dependencies,
455 name: CrateName::new("crate_name_with_dashes").unwrap()