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, panic::RefUnwindSafe, str::FromStr, sync::Arc};
12 use rustc_hash::{FxHashMap, FxHashSet};
15 use vfs::{file_set::FileSet, FileId, VfsPath};
17 /// Files are grouped into source roots. A source root is a directory on the
18 /// file systems which is watched for changes. Typically it corresponds to a
19 /// Rust crate. Source roots *might* be nested: in this case, a file belongs to
20 /// the nearest enclosing source root. Paths to files are always relative to a
21 /// source root, and the analyzer does not know the root path of the source root at
22 /// all. So, a file from one source root can't refer to a file in another source
24 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
25 pub struct SourceRootId(pub u32);
27 #[derive(Clone, Debug, PartialEq, Eq)]
28 pub struct SourceRoot {
29 /// Sysroot or crates.io library.
31 /// Libraries are considered mostly immutable, this assumption is used to
32 /// optimize salsa's query structure
34 pub(crate) file_set: FileSet,
38 pub fn new_local(file_set: FileSet) -> SourceRoot {
39 SourceRoot { is_library: false, file_set }
41 pub fn new_library(file_set: FileSet) -> SourceRoot {
42 SourceRoot { is_library: true, file_set }
44 pub fn path_for_file(&self, file: &FileId) -> Option<&VfsPath> {
45 self.file_set.path_for_file(file)
47 pub fn file_for_path(&self, path: &VfsPath) -> Option<&FileId> {
48 self.file_set.file_for_path(path)
50 pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
55 /// `CrateGraph` is a bit of information which turns a set of text files into a
56 /// number of Rust crates.
58 /// Each crate is defined by the `FileId` of its root module, the set of enabled
59 /// `cfg` flags and the set of dependencies.
61 /// Note that, due to cfg's, there might be several crates for a single `FileId`!
63 /// For the purposes of analysis, a crate does not have a name. Instead, names
64 /// are specified on dependency edges. That is, a crate might be known under
65 /// different names in different dependent crates.
67 /// Note that `CrateGraph` is build-system agnostic: it's a concept of the Rust
68 /// language proper, not a concept of the build system. In practice, we get
69 /// `CrateGraph` by lowering `cargo metadata` output.
71 /// `CrateGraph` is `!Serialize` by design, see
72 /// <https://github.com/rust-analyzer/rust-analyzer/blob/master/docs/dev/architecture.md#serialization>
73 #[derive(Debug, Clone, Default /* Serialize, Deserialize */)]
74 pub struct CrateGraph {
75 arena: FxHashMap<CrateId, CrateData>,
78 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
79 pub struct CrateId(pub u32);
81 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
82 pub struct CrateName(SmolStr);
85 /// Creates a crate name, checking for dashes in the string provided.
86 /// Dashes are not allowed in the crate names,
87 /// hence the input string is returned as `Err` for those cases.
88 pub fn new(name: &str) -> Result<CrateName, &str> {
89 if name.contains('-') {
92 Ok(Self(SmolStr::new(name)))
96 /// Creates a crate name, unconditionally replacing the dashes with underscores.
97 pub fn normalize_dashes(name: &str) -> CrateName {
98 Self(SmolStr::new(name.replace('-', "_")))
102 impl fmt::Display for CrateName {
103 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
104 write!(f, "{}", self.0)
108 impl ops::Deref for CrateName {
110 fn deref(&self) -> &str {
115 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
116 pub struct CrateDisplayName {
117 // The name we use to display various paths (with `_`).
118 crate_name: CrateName,
119 // The name as specified in Cargo.toml (with `-`).
120 canonical_name: String,
123 impl CrateDisplayName {
124 pub fn canonical_name(&self) -> &str {
127 pub fn crate_name(&self) -> &CrateName {
132 impl From<CrateName> for CrateDisplayName {
133 fn from(crate_name: CrateName) -> CrateDisplayName {
134 let canonical_name = crate_name.to_string();
135 CrateDisplayName { crate_name, canonical_name }
139 impl fmt::Display for CrateDisplayName {
140 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
141 write!(f, "{}", self.crate_name)
145 impl ops::Deref for CrateDisplayName {
147 fn deref(&self) -> &str {
152 impl CrateDisplayName {
153 pub fn from_canonical_name(canonical_name: String) -> CrateDisplayName {
154 let crate_name = CrateName::normalize_dashes(&canonical_name);
155 CrateDisplayName { crate_name, canonical_name }
159 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
160 pub struct ProcMacroId(pub u32);
162 #[derive(Copy, Clone, Eq, PartialEq, Debug, Hash)]
163 pub enum ProcMacroKind {
169 pub trait ProcMacroExpander: fmt::Debug + Send + Sync + RefUnwindSafe {
173 attrs: Option<&Subtree>,
175 ) -> Result<Subtree, ProcMacroExpansionError>;
178 pub enum ProcMacroExpansionError {
180 /// Things like "proc macro server was killed by OOM".
184 #[derive(Debug, Clone)]
185 pub struct ProcMacro {
187 pub kind: ProcMacroKind,
188 pub expander: Arc<dyn ProcMacroExpander>,
191 #[derive(Debug, Clone)]
192 pub struct CrateData {
193 pub root_file_id: FileId,
194 pub edition: Edition,
195 /// A name used in the package's project declaration: for Cargo projects,
196 /// its `[package].name` can be different for other project types or even
197 /// absent (a dummy crate for the code snippet, for example).
199 /// For purposes of analysis, crates are anonymous (only names in
200 /// `Dependency` matters), this name should only be used for UI.
201 pub display_name: Option<CrateDisplayName>,
202 pub cfg_options: CfgOptions,
203 pub potential_cfg_options: CfgOptions,
205 pub dependencies: Vec<Dependency>,
206 pub proc_macro: Vec<ProcMacro>,
209 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
217 pub const CURRENT: Edition = Edition::Edition2018;
220 #[derive(Default, Debug, Clone, PartialEq, Eq)]
222 entries: FxHashMap<String, String>,
225 #[derive(Debug, Clone, PartialEq, Eq)]
226 pub struct Dependency {
227 pub crate_id: CrateId,
233 pub fn new(name: CrateName, crate_id: CrateId) -> Self {
234 Self { name, crate_id, prelude: true }
237 pub fn with_prelude(name: CrateName, crate_id: CrateId, prelude: bool) -> Self {
238 Self { name, crate_id, prelude }
241 /// Whether this dependency is to be added to the depending crate's extern prelude.
242 pub fn is_prelude(&self) -> bool {
248 pub fn add_crate_root(
252 display_name: Option<CrateDisplayName>,
253 cfg_options: CfgOptions,
254 potential_cfg_options: CfgOptions,
256 proc_macro: Vec<ProcMacro>,
258 let data = CrateData {
259 root_file_id: file_id,
263 potential_cfg_options,
266 dependencies: Vec::new(),
268 let crate_id = CrateId(self.arena.len() as u32);
269 let prev = self.arena.insert(crate_id, data);
270 assert!(prev.is_none());
278 ) -> Result<(), CyclicDependenciesError> {
279 let _p = profile::span("add_dep");
281 // Check if adding a dep from `from` to `to` creates a cycle. To figure
282 // that out, look for a path in the *opposite* direction, from `to` to
284 if let Some(path) = self.find_path(&mut FxHashSet::default(), dep.crate_id, from) {
285 let path = path.into_iter().map(|it| (it, self[it].display_name.clone())).collect();
286 let err = CyclicDependenciesError { path };
287 assert!(err.from().0 == from && err.to().0 == dep.crate_id);
291 self.arena.get_mut(&from).unwrap().add_dep(dep);
295 pub fn is_empty(&self) -> bool {
296 self.arena.is_empty()
299 pub fn iter(&self) -> impl Iterator<Item = CrateId> + '_ {
300 self.arena.keys().copied()
303 /// Returns an iterator over all transitive dependencies of the given crate,
304 /// including the crate itself.
305 pub fn transitive_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> + '_ {
306 let mut worklist = vec![of];
307 let mut deps = FxHashSet::default();
309 while let Some(krate) = worklist.pop() {
310 if !deps.insert(krate) {
314 worklist.extend(self[krate].dependencies.iter().map(|dep| dep.crate_id));
320 /// Returns all transitive reverse dependencies of the given crate,
321 /// including the crate itself.
322 pub fn transitive_rev_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> + '_ {
323 let mut worklist = vec![of];
324 let mut rev_deps = FxHashSet::default();
327 let mut inverted_graph = FxHashMap::<_, Vec<_>>::default();
328 self.arena.iter().for_each(|(&krate, data)| {
331 .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate))
334 while let Some(krate) = worklist.pop() {
335 if let Some(krate_rev_deps) = inverted_graph.get(&krate) {
339 .filter(|&rev_dep| rev_deps.insert(rev_dep))
340 .for_each(|rev_dep| worklist.push(rev_dep));
347 /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
348 /// come before the crate itself).
349 pub fn crates_in_topological_order(&self) -> Vec<CrateId> {
350 let mut res = Vec::new();
351 let mut visited = FxHashSet::default();
353 for krate in self.arena.keys().copied() {
354 go(self, &mut visited, &mut res, krate);
361 visited: &mut FxHashSet<CrateId>,
362 res: &mut Vec<CrateId>,
365 if !visited.insert(source) {
368 for dep in graph[source].dependencies.iter() {
369 go(graph, visited, res, dep.crate_id)
375 // FIXME: this only finds one crate with the given root; we could have multiple
376 pub fn crate_id_for_crate_root(&self, file_id: FileId) -> Option<CrateId> {
378 self.arena.iter().find(|(_crate_id, data)| data.root_file_id == file_id)?;
382 /// Extends this crate graph by adding a complete disjoint second crate
385 /// The ids of the crates in the `other` graph are shifted by the return
387 pub fn extend(&mut self, other: CrateGraph) -> u32 {
388 let start = self.arena.len() as u32;
389 self.arena.extend(other.arena.into_iter().map(|(id, mut data)| {
390 let new_id = id.shift(start);
391 for dep in &mut data.dependencies {
392 dep.crate_id = dep.crate_id.shift(start);
401 visited: &mut FxHashSet<CrateId>,
404 ) -> Option<Vec<CrateId>> {
405 if !visited.insert(from) {
410 return Some(vec![to]);
413 for dep in &self[from].dependencies {
414 let crate_id = dep.crate_id;
415 if let Some(mut path) = self.find_path(visited, crate_id, to) {
424 // Work around for https://github.com/rust-analyzer/rust-analyzer/issues/6038.
425 // As hacky as it gets.
426 pub fn patch_cfg_if(&mut self) -> bool {
427 let cfg_if = self.hacky_find_crate("cfg_if");
428 let std = self.hacky_find_crate("std");
429 match (cfg_if, std) {
430 (Some(cfg_if), Some(std)) => {
431 self.arena.get_mut(&cfg_if).unwrap().dependencies.clear();
436 .push(Dependency::new(CrateName::new("cfg_if").unwrap(), cfg_if));
443 fn hacky_find_crate(&self, display_name: &str) -> Option<CrateId> {
444 self.iter().find(|it| self[*it].display_name.as_deref() == Some(display_name))
448 impl ops::Index<CrateId> for CrateGraph {
449 type Output = CrateData;
450 fn index(&self, crate_id: CrateId) -> &CrateData {
451 &self.arena[&crate_id]
456 fn shift(self, amount: u32) -> CrateId {
457 CrateId(self.0 + amount)
462 fn add_dep(&mut self, dep: Dependency) {
463 self.dependencies.push(dep)
467 impl FromStr for Edition {
468 type Err = ParseEditionError;
470 fn from_str(s: &str) -> Result<Self, Self::Err> {
472 "2015" => Edition::Edition2015,
473 "2018" => Edition::Edition2018,
474 "2021" => Edition::Edition2021,
475 _ => return Err(ParseEditionError { invalid_input: s.to_string() }),
481 impl fmt::Display for Edition {
482 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
483 f.write_str(match self {
484 Edition::Edition2015 => "2015",
485 Edition::Edition2018 => "2018",
486 Edition::Edition2021 => "2021",
491 impl FromIterator<(String, String)> for Env {
492 fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
493 Env { entries: FromIterator::from_iter(iter) }
498 pub fn set(&mut self, env: &str, value: String) {
499 self.entries.insert(env.to_owned(), value);
502 pub fn get(&self, env: &str) -> Option<String> {
503 self.entries.get(env).cloned()
506 pub fn iter(&self) -> impl Iterator<Item = (&str, &str)> {
507 self.entries.iter().map(|(k, v)| (k.as_str(), v.as_str()))
512 pub struct ParseEditionError {
513 invalid_input: String,
516 impl fmt::Display for ParseEditionError {
517 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
518 write!(f, "invalid edition: {:?}", self.invalid_input)
522 impl std::error::Error for ParseEditionError {}
525 pub struct CyclicDependenciesError {
526 path: Vec<(CrateId, Option<CrateDisplayName>)>,
529 impl CyclicDependenciesError {
530 fn from(&self) -> &(CrateId, Option<CrateDisplayName>) {
531 self.path.first().unwrap()
533 fn to(&self) -> &(CrateId, Option<CrateDisplayName>) {
534 self.path.last().unwrap()
538 impl fmt::Display for CyclicDependenciesError {
539 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
540 let render = |(id, name): &(CrateId, Option<CrateDisplayName>)| match name {
541 Some(it) => format!("{}({:?})", it, id),
542 None => format!("{:?}", id),
544 let path = self.path.iter().rev().map(render).collect::<Vec<String>>().join(" -> ");
547 "cyclic deps: {} -> {}, alternative path: {}",
557 use super::{CfgOptions, CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
560 fn detect_cyclic_dependency_indirect() {
561 let mut graph = CrateGraph::default();
562 let crate1 = graph.add_crate_root(
566 CfgOptions::default(),
567 CfgOptions::default(),
571 let crate2 = graph.add_crate_root(
575 CfgOptions::default(),
576 CfgOptions::default(),
580 let crate3 = graph.add_crate_root(
584 CfgOptions::default(),
585 CfgOptions::default(),
590 .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
593 .add_dep(crate2, Dependency::new(CrateName::new("crate3").unwrap(), crate3))
596 .add_dep(crate3, Dependency::new(CrateName::new("crate1").unwrap(), crate1))
601 fn detect_cyclic_dependency_direct() {
602 let mut graph = CrateGraph::default();
603 let crate1 = graph.add_crate_root(
607 CfgOptions::default(),
608 CfgOptions::default(),
612 let crate2 = graph.add_crate_root(
616 CfgOptions::default(),
617 CfgOptions::default(),
622 .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
625 .add_dep(crate2, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
631 let mut graph = CrateGraph::default();
632 let crate1 = graph.add_crate_root(
636 CfgOptions::default(),
637 CfgOptions::default(),
641 let crate2 = graph.add_crate_root(
645 CfgOptions::default(),
646 CfgOptions::default(),
650 let crate3 = graph.add_crate_root(
654 CfgOptions::default(),
655 CfgOptions::default(),
660 .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
663 .add_dep(crate2, Dependency::new(CrateName::new("crate3").unwrap(), crate3))
668 fn dashes_are_normalized() {
669 let mut graph = CrateGraph::default();
670 let crate1 = graph.add_crate_root(
674 CfgOptions::default(),
675 CfgOptions::default(),
679 let crate2 = graph.add_crate_root(
683 CfgOptions::default(),
684 CfgOptions::default(),
691 Dependency::new(CrateName::normalize_dashes("crate-name-with-dashes"), crate2)
695 graph[crate1].dependencies,
696 vec![Dependency::new(CrateName::new("crate_name_with_dashes").unwrap(), crate2)]