base_db/
input.rs

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.
4//!
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.
8
9use std::error::Error;
10use std::hash::BuildHasherDefault;
11use std::{fmt, mem, ops};
12
13use cfg::{CfgOptions, HashableCfgOptions};
14use dashmap::DashMap;
15use dashmap::mapref::entry::Entry;
16use intern::Symbol;
17use la_arena::{Arena, Idx, RawIdx};
18use rustc_hash::{FxBuildHasher, FxHashMap, FxHashSet, FxHasher};
19use salsa::{Durability, Setter};
20use span::Edition;
21use triomphe::Arc;
22use vfs::{AbsPathBuf, AnchoredPath, FileId, VfsPath, file_set::FileSet};
23
24use crate::{CrateWorkspaceData, EditionedFileId, FxIndexSet, RootQueryDb};
25
26pub type ProcMacroPaths =
27    FxHashMap<CrateBuilderId, Result<(String, AbsPathBuf), ProcMacroLoadingError>>;
28
29#[derive(Debug, Clone, PartialEq, Eq, Hash)]
30pub enum ProcMacroLoadingError {
31    Disabled,
32    FailedToBuild,
33    ExpectedProcMacroArtifact,
34    MissingDylibPath,
35    NotYetBuilt,
36    NoProcMacros,
37    ProcMacroSrvError(Box<str>),
38}
39impl ProcMacroLoadingError {
40    pub fn is_hard_error(&self) -> bool {
41        match self {
42            ProcMacroLoadingError::Disabled | ProcMacroLoadingError::NotYetBuilt => false,
43            ProcMacroLoadingError::ExpectedProcMacroArtifact
44            | ProcMacroLoadingError::FailedToBuild
45            | ProcMacroLoadingError::MissingDylibPath
46            | ProcMacroLoadingError::NoProcMacros
47            | ProcMacroLoadingError::ProcMacroSrvError(_) => true,
48        }
49    }
50}
51
52impl Error for ProcMacroLoadingError {}
53impl fmt::Display for ProcMacroLoadingError {
54    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
55        match self {
56            ProcMacroLoadingError::ExpectedProcMacroArtifact => {
57                write!(f, "proc-macro crate did not build proc-macro artifact")
58            }
59            ProcMacroLoadingError::Disabled => write!(f, "proc-macro expansion is disabled"),
60            ProcMacroLoadingError::FailedToBuild => write!(f, "proc-macro failed to build"),
61            ProcMacroLoadingError::MissingDylibPath => {
62                write!(
63                    f,
64                    "proc-macro crate built but the dylib path is missing, this indicates a problem with your build system."
65                )
66            }
67            ProcMacroLoadingError::NotYetBuilt => write!(f, "proc-macro not yet built"),
68            ProcMacroLoadingError::NoProcMacros => {
69                write!(f, "proc macro library has no proc macros")
70            }
71            ProcMacroLoadingError::ProcMacroSrvError(msg) => {
72                write!(f, "proc macro server error: {msg}")
73            }
74        }
75    }
76}
77
78#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
79pub struct SourceRootId(pub u32);
80
81/// Files are grouped into source roots. A source root is a directory on the
82/// file systems which is watched for changes. Typically it corresponds to a
83/// Rust crate. Source roots *might* be nested: in this case, a file belongs to
84/// the nearest enclosing source root. Paths to files are always relative to a
85/// source root, and the analyzer does not know the root path of the source root at
86/// all. So, a file from one source root can't refer to a file in another source
87/// root by path.
88#[derive(Clone, Debug, PartialEq, Eq)]
89pub struct SourceRoot {
90    /// Sysroot or crates.io library.
91    ///
92    /// Libraries are considered mostly immutable, this assumption is used to
93    /// optimize salsa's query structure
94    pub is_library: bool,
95    file_set: FileSet,
96}
97
98impl SourceRoot {
99    pub fn new_local(file_set: FileSet) -> SourceRoot {
100        SourceRoot { is_library: false, file_set }
101    }
102
103    pub fn new_library(file_set: FileSet) -> SourceRoot {
104        SourceRoot { is_library: true, file_set }
105    }
106
107    pub fn path_for_file(&self, file: &FileId) -> Option<&VfsPath> {
108        self.file_set.path_for_file(file)
109    }
110
111    pub fn file_for_path(&self, path: &VfsPath) -> Option<&FileId> {
112        self.file_set.file_for_path(path)
113    }
114
115    pub fn resolve_path(&self, path: AnchoredPath<'_>) -> Option<FileId> {
116        self.file_set.resolve_path(path)
117    }
118
119    pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
120        self.file_set.iter()
121    }
122}
123
124#[derive(Default, Clone)]
125pub struct CrateGraphBuilder {
126    arena: Arena<CrateBuilder>,
127}
128
129pub type CrateBuilderId = Idx<CrateBuilder>;
130
131impl ops::Index<CrateBuilderId> for CrateGraphBuilder {
132    type Output = CrateBuilder;
133
134    fn index(&self, index: CrateBuilderId) -> &Self::Output {
135        &self.arena[index]
136    }
137}
138
139#[derive(Debug, Clone, PartialEq, Eq)]
140pub struct CrateBuilder {
141    pub basic: CrateDataBuilder,
142    pub extra: ExtraCrateData,
143    pub cfg_options: CfgOptions,
144    pub env: Env,
145    ws_data: Arc<CrateWorkspaceData>,
146}
147
148impl fmt::Debug for CrateGraphBuilder {
149    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
150        f.debug_map()
151            .entries(self.arena.iter().map(|(id, data)| (u32::from(id.into_raw()), data)))
152            .finish()
153    }
154}
155
156#[derive(Debug, Clone, PartialEq, Eq, Hash)]
157pub struct CrateName(Symbol);
158
159impl CrateName {
160    /// Creates a crate name, checking for dashes in the string provided.
161    /// Dashes are not allowed in the crate names,
162    /// hence the input string is returned as `Err` for those cases.
163    pub fn new(name: &str) -> Result<CrateName, &str> {
164        if name.contains('-') { Err(name) } else { Ok(Self(Symbol::intern(name))) }
165    }
166
167    /// Creates a crate name, unconditionally replacing the dashes with underscores.
168    pub fn normalize_dashes(name: &str) -> CrateName {
169        Self(Symbol::intern(&name.replace('-', "_")))
170    }
171
172    pub fn symbol(&self) -> &Symbol {
173        &self.0
174    }
175}
176
177impl fmt::Display for CrateName {
178    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
179        self.0.fmt(f)
180    }
181}
182
183impl ops::Deref for CrateName {
184    type Target = Symbol;
185    fn deref(&self) -> &Symbol {
186        &self.0
187    }
188}
189
190/// Origin of the crates.
191#[derive(Debug, Clone, PartialEq, Eq, Hash)]
192pub enum CrateOrigin {
193    /// Crates that are from the rustc workspace.
194    Rustc { name: Symbol },
195    /// Crates that are workspace members.
196    Local { repo: Option<String>, name: Option<Symbol> },
197    /// Crates that are non member libraries.
198    Library { repo: Option<String>, name: Symbol },
199    /// Crates that are provided by the language, like std, core, proc-macro, ...
200    Lang(LangCrateOrigin),
201}
202
203impl CrateOrigin {
204    pub fn is_local(&self) -> bool {
205        matches!(self, CrateOrigin::Local { .. })
206    }
207
208    pub fn is_lib(&self) -> bool {
209        matches!(self, CrateOrigin::Library { .. })
210    }
211
212    pub fn is_lang(&self) -> bool {
213        matches!(self, CrateOrigin::Lang { .. })
214    }
215}
216
217#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
218pub enum LangCrateOrigin {
219    Alloc,
220    Core,
221    ProcMacro,
222    Std,
223    Test,
224    Other,
225}
226
227impl From<&str> for LangCrateOrigin {
228    fn from(s: &str) -> Self {
229        match s {
230            "alloc" => LangCrateOrigin::Alloc,
231            "core" => LangCrateOrigin::Core,
232            "proc-macro" | "proc_macro" => LangCrateOrigin::ProcMacro,
233            "std" => LangCrateOrigin::Std,
234            "test" => LangCrateOrigin::Test,
235            _ => LangCrateOrigin::Other,
236        }
237    }
238}
239
240impl fmt::Display for LangCrateOrigin {
241    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
242        let text = match self {
243            LangCrateOrigin::Alloc => "alloc",
244            LangCrateOrigin::Core => "core",
245            LangCrateOrigin::ProcMacro => "proc_macro",
246            LangCrateOrigin::Std => "std",
247            LangCrateOrigin::Test => "test",
248            LangCrateOrigin::Other => "other",
249        };
250        f.write_str(text)
251    }
252}
253
254#[derive(Debug, Clone, PartialEq, Eq, Hash)]
255pub struct CrateDisplayName {
256    // The name we use to display various paths (with `_`).
257    crate_name: CrateName,
258    // The name as specified in Cargo.toml (with `-`).
259    canonical_name: Symbol,
260}
261
262impl CrateDisplayName {
263    pub fn canonical_name(&self) -> &Symbol {
264        &self.canonical_name
265    }
266    pub fn crate_name(&self) -> &CrateName {
267        &self.crate_name
268    }
269}
270
271impl From<CrateName> for CrateDisplayName {
272    fn from(crate_name: CrateName) -> CrateDisplayName {
273        let canonical_name = crate_name.0.clone();
274        CrateDisplayName { crate_name, canonical_name }
275    }
276}
277
278impl fmt::Display for CrateDisplayName {
279    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
280        self.crate_name.fmt(f)
281    }
282}
283
284impl ops::Deref for CrateDisplayName {
285    type Target = Symbol;
286    fn deref(&self) -> &Symbol {
287        &self.crate_name
288    }
289}
290
291impl CrateDisplayName {
292    pub fn from_canonical_name(canonical_name: &str) -> CrateDisplayName {
293        let crate_name = CrateName::normalize_dashes(canonical_name);
294        CrateDisplayName { crate_name, canonical_name: Symbol::intern(canonical_name) }
295    }
296}
297
298pub type TargetLayoutLoadResult = Result<Arc<str>, Arc<str>>;
299
300#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
301pub enum ReleaseChannel {
302    Stable,
303    Beta,
304    Nightly,
305}
306
307impl ReleaseChannel {
308    pub fn as_str(self) -> &'static str {
309        match self {
310            ReleaseChannel::Stable => "stable",
311            ReleaseChannel::Beta => "beta",
312            ReleaseChannel::Nightly => "nightly",
313        }
314    }
315
316    #[allow(clippy::should_implement_trait)]
317    pub fn from_str(str: &str) -> Option<Self> {
318        Some(match str {
319            "" | "stable" => ReleaseChannel::Stable,
320            "nightly" => ReleaseChannel::Nightly,
321            _ if str.starts_with("beta") => ReleaseChannel::Beta,
322            _ => return None,
323        })
324    }
325}
326
327/// The crate data from which we derive the `Crate`.
328///
329/// We want this to contain as little data as possible, because if it contains dependencies and
330/// something changes, this crate and all of its dependencies ids are invalidated, which causes
331/// pretty much everything to be recomputed. If the crate id is not invalidated, only this crate's
332/// information needs to be recomputed.
333///
334/// *Most* different crates have different root files (actually, pretty much all of them).
335/// Still, it is possible to have crates distinguished by other factors (e.g. dependencies).
336/// So we store only the root file - unless we find that this crate has the same root file as
337/// another crate, in which case we store all data for one of them (if one is a dependency of
338/// the other, we store for it, because it has more dependencies to be invalidated).
339#[derive(Debug, Clone, PartialEq, Eq, Hash)]
340pub struct UniqueCrateData {
341    root_file_id: FileId,
342    disambiguator: Option<Box<(BuiltCrateData, HashableCfgOptions)>>,
343}
344
345#[derive(Debug, Clone, PartialEq, Eq, Hash)]
346pub struct CrateData<Id> {
347    pub root_file_id: FileId,
348    pub edition: Edition,
349    /// The dependencies of this crate.
350    ///
351    /// Note that this may contain more dependencies than the crate actually uses.
352    /// A common example is the test crate which is included but only actually is active when
353    /// declared in source via `extern crate test`.
354    pub dependencies: Vec<Dependency<Id>>,
355    pub origin: CrateOrigin,
356    pub is_proc_macro: bool,
357    /// The working directory to run proc-macros in invoked in the context of this crate.
358    /// This is the workspace root of the cargo workspace for workspace members, the crate manifest
359    /// dir otherwise.
360    // FIXME: This ought to be a `VfsPath` or something opaque.
361    pub proc_macro_cwd: Arc<AbsPathBuf>,
362}
363
364pub type CrateDataBuilder = CrateData<CrateBuilderId>;
365pub type BuiltCrateData = CrateData<Crate>;
366
367/// Crate data unrelated to analysis.
368#[derive(Debug, Clone, PartialEq, Eq)]
369pub struct ExtraCrateData {
370    pub version: Option<String>,
371    /// A name used in the package's project declaration: for Cargo projects,
372    /// its `[package].name` can be different for other project types or even
373    /// absent (a dummy crate for the code snippet, for example).
374    ///
375    /// For purposes of analysis, crates are anonymous (only names in
376    /// `Dependency` matters), this name should only be used for UI.
377    pub display_name: Option<CrateDisplayName>,
378    /// The cfg options that could be used by the crate
379    pub potential_cfg_options: Option<CfgOptions>,
380}
381
382#[derive(Default, Clone, PartialEq, Eq)]
383pub struct Env {
384    entries: FxHashMap<String, String>,
385}
386
387impl fmt::Debug for Env {
388    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
389        struct EnvDebug<'s>(Vec<(&'s String, &'s String)>);
390
391        impl fmt::Debug for EnvDebug<'_> {
392            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
393                f.debug_map().entries(self.0.iter().copied()).finish()
394            }
395        }
396        f.debug_struct("Env")
397            .field("entries", &{
398                let mut entries: Vec<_> = self.entries.iter().collect();
399                entries.sort();
400                EnvDebug(entries)
401            })
402            .finish()
403    }
404}
405
406#[derive(Debug, Clone, PartialEq, Eq, Hash)]
407pub struct Dependency<Id> {
408    pub crate_id: Id,
409    pub name: CrateName,
410    prelude: bool,
411    sysroot: bool,
412}
413
414pub type DependencyBuilder = Dependency<CrateBuilderId>;
415pub type BuiltDependency = Dependency<Crate>;
416
417impl DependencyBuilder {
418    pub fn new(name: CrateName, crate_id: CrateBuilderId) -> Self {
419        Self { name, crate_id, prelude: true, sysroot: false }
420    }
421
422    pub fn with_prelude(
423        name: CrateName,
424        crate_id: CrateBuilderId,
425        prelude: bool,
426        sysroot: bool,
427    ) -> Self {
428        Self { name, crate_id, prelude, sysroot }
429    }
430}
431
432impl BuiltDependency {
433    /// Whether this dependency is to be added to the depending crate's extern prelude.
434    pub fn is_prelude(&self) -> bool {
435        self.prelude
436    }
437
438    /// Whether this dependency is a sysroot injected one.
439    pub fn is_sysroot(&self) -> bool {
440        self.sysroot
441    }
442}
443
444pub type CratesIdMap = FxHashMap<CrateBuilderId, Crate>;
445
446#[salsa_macros::input]
447#[derive(Debug, PartialOrd, Ord)]
448pub struct Crate {
449    #[returns(ref)]
450    pub data: BuiltCrateData,
451    /// Crate data that is not needed for analysis.
452    ///
453    /// This is split into a separate field to increase incrementality.
454    #[returns(ref)]
455    pub extra_data: ExtraCrateData,
456    // This is in `Arc` because it is shared for all crates in a workspace.
457    #[returns(ref)]
458    pub workspace_data: Arc<CrateWorkspaceData>,
459    #[returns(ref)]
460    pub cfg_options: CfgOptions,
461    #[returns(ref)]
462    pub env: Env,
463}
464
465/// The mapping from [`UniqueCrateData`] to their [`Crate`] input.
466#[derive(Debug, Default)]
467pub struct CratesMap(DashMap<UniqueCrateData, Crate, BuildHasherDefault<FxHasher>>);
468
469impl CrateGraphBuilder {
470    pub fn add_crate_root(
471        &mut self,
472        root_file_id: FileId,
473        edition: Edition,
474        display_name: Option<CrateDisplayName>,
475        version: Option<String>,
476        mut cfg_options: CfgOptions,
477        mut potential_cfg_options: Option<CfgOptions>,
478        mut env: Env,
479        origin: CrateOrigin,
480        is_proc_macro: bool,
481        proc_macro_cwd: Arc<AbsPathBuf>,
482        ws_data: Arc<CrateWorkspaceData>,
483    ) -> CrateBuilderId {
484        env.entries.shrink_to_fit();
485        cfg_options.shrink_to_fit();
486        if let Some(potential_cfg_options) = &mut potential_cfg_options {
487            potential_cfg_options.shrink_to_fit();
488        }
489        self.arena.alloc(CrateBuilder {
490            basic: CrateData {
491                root_file_id,
492                edition,
493                dependencies: Vec::new(),
494                origin,
495                is_proc_macro,
496                proc_macro_cwd,
497            },
498            extra: ExtraCrateData { version, display_name, potential_cfg_options },
499            cfg_options,
500            env,
501            ws_data,
502        })
503    }
504
505    pub fn add_dep(
506        &mut self,
507        from: CrateBuilderId,
508        dep: DependencyBuilder,
509    ) -> Result<(), CyclicDependenciesError> {
510        let _p = tracing::info_span!("add_dep").entered();
511
512        // Check if adding a dep from `from` to `to` creates a cycle. To figure
513        // that out, look for a  path in the *opposite* direction, from `to` to
514        // `from`.
515        if let Some(path) = self.find_path(&mut FxHashSet::default(), dep.crate_id, from) {
516            let path =
517                path.into_iter().map(|it| (it, self[it].extra.display_name.clone())).collect();
518            let err = CyclicDependenciesError { path };
519            assert!(err.from().0 == from && err.to().0 == dep.crate_id);
520            return Err(err);
521        }
522
523        self.arena[from].basic.dependencies.push(dep);
524        Ok(())
525    }
526
527    pub fn set_in_db(self, db: &mut dyn RootQueryDb) -> CratesIdMap {
528        // For some reason in some repositories we have duplicate crates, so we use a set and not `Vec`.
529        // We use an `IndexSet` because the list needs to be topologically sorted.
530        let mut all_crates = FxIndexSet::with_capacity_and_hasher(self.arena.len(), FxBuildHasher);
531        let mut visited = FxHashMap::default();
532        let mut visited_root_files = FxHashSet::default();
533
534        let old_all_crates = db.all_crates();
535
536        let crates_map = db.crates_map();
537        // salsa doesn't compare new input to old input to see if they are the same, so here we are doing all the work ourselves.
538        for krate in self.iter() {
539            go(
540                &self,
541                db,
542                &crates_map,
543                &mut visited,
544                &mut visited_root_files,
545                &mut all_crates,
546                krate,
547            );
548        }
549
550        if old_all_crates.len() != all_crates.len()
551            || old_all_crates.iter().any(|&krate| !all_crates.contains(&krate))
552        {
553            db.set_all_crates_with_durability(
554                Arc::new(Vec::from_iter(all_crates).into_boxed_slice()),
555                Durability::MEDIUM,
556            );
557        }
558
559        return visited;
560
561        fn go(
562            graph: &CrateGraphBuilder,
563            db: &mut dyn RootQueryDb,
564            crates_map: &CratesMap,
565            visited: &mut FxHashMap<CrateBuilderId, Crate>,
566            visited_root_files: &mut FxHashSet<FileId>,
567            all_crates: &mut FxIndexSet<Crate>,
568            source: CrateBuilderId,
569        ) -> Crate {
570            if let Some(&crate_id) = visited.get(&source) {
571                return crate_id;
572            }
573            let krate = &graph[source];
574            let dependencies = krate
575                .basic
576                .dependencies
577                .iter()
578                .map(|dep| BuiltDependency {
579                    crate_id: go(
580                        graph,
581                        db,
582                        crates_map,
583                        visited,
584                        visited_root_files,
585                        all_crates,
586                        dep.crate_id,
587                    ),
588                    name: dep.name.clone(),
589                    prelude: dep.prelude,
590                    sysroot: dep.sysroot,
591                })
592                .collect::<Vec<_>>();
593            let crate_data = BuiltCrateData {
594                dependencies,
595                edition: krate.basic.edition,
596                is_proc_macro: krate.basic.is_proc_macro,
597                origin: krate.basic.origin.clone(),
598                root_file_id: krate.basic.root_file_id,
599                proc_macro_cwd: krate.basic.proc_macro_cwd.clone(),
600            };
601            let disambiguator = if visited_root_files.insert(krate.basic.root_file_id) {
602                None
603            } else {
604                Some(Box::new((crate_data.clone(), krate.cfg_options.to_hashable())))
605            };
606
607            let unique_crate_data =
608                UniqueCrateData { root_file_id: krate.basic.root_file_id, disambiguator };
609            let crate_input = match crates_map.0.entry(unique_crate_data) {
610                Entry::Occupied(entry) => {
611                    let old_crate = *entry.get();
612                    if crate_data != *old_crate.data(db) {
613                        old_crate.set_data(db).with_durability(Durability::MEDIUM).to(crate_data);
614                    }
615                    if krate.extra != *old_crate.extra_data(db) {
616                        old_crate
617                            .set_extra_data(db)
618                            .with_durability(Durability::MEDIUM)
619                            .to(krate.extra.clone());
620                    }
621                    if krate.cfg_options != *old_crate.cfg_options(db) {
622                        old_crate
623                            .set_cfg_options(db)
624                            .with_durability(Durability::MEDIUM)
625                            .to(krate.cfg_options.clone());
626                    }
627                    if krate.env != *old_crate.env(db) {
628                        old_crate
629                            .set_env(db)
630                            .with_durability(Durability::MEDIUM)
631                            .to(krate.env.clone());
632                    }
633                    if krate.ws_data != *old_crate.workspace_data(db) {
634                        old_crate
635                            .set_workspace_data(db)
636                            .with_durability(Durability::MEDIUM)
637                            .to(krate.ws_data.clone());
638                    }
639                    old_crate
640                }
641                Entry::Vacant(entry) => {
642                    let input = Crate::builder(
643                        crate_data,
644                        krate.extra.clone(),
645                        krate.ws_data.clone(),
646                        krate.cfg_options.clone(),
647                        krate.env.clone(),
648                    )
649                    .durability(Durability::MEDIUM)
650                    .new(db);
651                    entry.insert(input);
652                    input
653                }
654            };
655            all_crates.insert(crate_input);
656            visited.insert(source, crate_input);
657            crate_input
658        }
659    }
660
661    pub fn iter(&self) -> impl Iterator<Item = CrateBuilderId> + '_ {
662        self.arena.iter().map(|(idx, _)| idx)
663    }
664
665    /// Returns an iterator over all transitive dependencies of the given crate,
666    /// including the crate itself.
667    pub fn transitive_deps(&self, of: CrateBuilderId) -> impl Iterator<Item = CrateBuilderId> {
668        let mut worklist = vec![of];
669        let mut deps = FxHashSet::default();
670
671        while let Some(krate) = worklist.pop() {
672            if !deps.insert(krate) {
673                continue;
674            }
675
676            worklist.extend(self[krate].basic.dependencies.iter().map(|dep| dep.crate_id));
677        }
678
679        deps.into_iter()
680    }
681
682    /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
683    /// come before the crate itself).
684    fn crates_in_topological_order(&self) -> Vec<CrateBuilderId> {
685        let mut res = Vec::new();
686        let mut visited = FxHashSet::default();
687
688        for krate in self.iter() {
689            go(self, &mut visited, &mut res, krate);
690        }
691
692        return res;
693
694        fn go(
695            graph: &CrateGraphBuilder,
696            visited: &mut FxHashSet<CrateBuilderId>,
697            res: &mut Vec<CrateBuilderId>,
698            source: CrateBuilderId,
699        ) {
700            if !visited.insert(source) {
701                return;
702            }
703            for dep in graph[source].basic.dependencies.iter() {
704                go(graph, visited, res, dep.crate_id)
705            }
706            res.push(source)
707        }
708    }
709
710    /// Extends this crate graph by adding a complete second crate
711    /// graph and adjust the ids in the [`ProcMacroPaths`] accordingly.
712    ///
713    /// This will deduplicate the crates of the graph where possible.
714    /// Furthermore dependencies are sorted by crate id to make deduplication easier.
715    ///
716    /// Returns a map mapping `other`'s IDs to the new IDs in `self`.
717    pub fn extend(
718        &mut self,
719        mut other: CrateGraphBuilder,
720        proc_macros: &mut ProcMacroPaths,
721    ) -> FxHashMap<CrateBuilderId, CrateBuilderId> {
722        // Sorting here is a bit pointless because the input is likely already sorted.
723        // However, the overhead is small and it makes the `extend` method harder to misuse.
724        self.arena
725            .iter_mut()
726            .for_each(|(_, data)| data.basic.dependencies.sort_by_key(|dep| dep.crate_id));
727
728        let m = self.arena.len();
729        let topo = other.crates_in_topological_order();
730        let mut id_map: FxHashMap<CrateBuilderId, CrateBuilderId> = FxHashMap::default();
731        for topo in topo {
732            let crate_data = &mut other.arena[topo];
733
734            crate_data
735                .basic
736                .dependencies
737                .iter_mut()
738                .for_each(|dep| dep.crate_id = id_map[&dep.crate_id]);
739            crate_data.basic.dependencies.sort_by_key(|dep| dep.crate_id);
740
741            let find = self.arena.iter().take(m).find_map(|(k, v)| (v == crate_data).then_some(k));
742            let new_id = find.unwrap_or_else(|| self.arena.alloc(crate_data.clone()));
743            id_map.insert(topo, new_id);
744        }
745
746        *proc_macros =
747            mem::take(proc_macros).into_iter().map(|(id, macros)| (id_map[&id], macros)).collect();
748        id_map
749    }
750
751    fn find_path(
752        &self,
753        visited: &mut FxHashSet<CrateBuilderId>,
754        from: CrateBuilderId,
755        to: CrateBuilderId,
756    ) -> Option<Vec<CrateBuilderId>> {
757        if !visited.insert(from) {
758            return None;
759        }
760
761        if from == to {
762            return Some(vec![to]);
763        }
764
765        for dep in &self[from].basic.dependencies {
766            let crate_id = dep.crate_id;
767            if let Some(mut path) = self.find_path(visited, crate_id, to) {
768                path.push(from);
769                return Some(path);
770            }
771        }
772
773        None
774    }
775
776    /// Removes all crates from this crate graph except for the ones in `to_keep` and fixes up the dependencies.
777    /// Returns a mapping from old crate ids to new crate ids.
778    pub fn remove_crates_except(
779        &mut self,
780        to_keep: &[CrateBuilderId],
781    ) -> Vec<Option<CrateBuilderId>> {
782        let mut id_map = vec![None; self.arena.len()];
783        self.arena = std::mem::take(&mut self.arena)
784            .into_iter()
785            .filter_map(|(id, data)| if to_keep.contains(&id) { Some((id, data)) } else { None })
786            .enumerate()
787            .map(|(new_id, (id, data))| {
788                id_map[id.into_raw().into_u32() as usize] =
789                    Some(CrateBuilderId::from_raw(RawIdx::from_u32(new_id as u32)));
790                data
791            })
792            .collect();
793        for (_, data) in self.arena.iter_mut() {
794            data.basic.dependencies.iter_mut().for_each(|dep| {
795                dep.crate_id =
796                    id_map[dep.crate_id.into_raw().into_u32() as usize].expect("crate was filtered")
797            });
798        }
799        id_map
800    }
801
802    pub fn shrink_to_fit(&mut self) {
803        self.arena.shrink_to_fit();
804    }
805}
806
807pub(crate) fn transitive_rev_deps(db: &dyn RootQueryDb, of: Crate) -> FxHashSet<Crate> {
808    let mut worklist = vec![of];
809    let mut rev_deps = FxHashSet::default();
810    rev_deps.insert(of);
811
812    let mut inverted_graph = FxHashMap::<_, Vec<_>>::default();
813    db.all_crates().iter().for_each(|&krate| {
814        krate
815            .data(db)
816            .dependencies
817            .iter()
818            .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate))
819    });
820
821    while let Some(krate) = worklist.pop() {
822        if let Some(crate_rev_deps) = inverted_graph.get(&krate) {
823            crate_rev_deps
824                .iter()
825                .copied()
826                .filter(|&rev_dep| rev_deps.insert(rev_dep))
827                .for_each(|rev_dep| worklist.push(rev_dep));
828        }
829    }
830
831    rev_deps
832}
833
834impl BuiltCrateData {
835    pub fn root_file_id(&self, db: &dyn salsa::Database) -> EditionedFileId {
836        EditionedFileId::new(db, self.root_file_id, self.edition)
837    }
838}
839
840impl Extend<(String, String)> for Env {
841    fn extend<T: IntoIterator<Item = (String, String)>>(&mut self, iter: T) {
842        self.entries.extend(iter);
843    }
844}
845
846impl FromIterator<(String, String)> for Env {
847    fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
848        Env { entries: FromIterator::from_iter(iter) }
849    }
850}
851
852impl Env {
853    pub fn set(&mut self, env: &str, value: impl Into<String>) {
854        self.entries.insert(env.to_owned(), value.into());
855    }
856
857    pub fn get(&self, env: &str) -> Option<String> {
858        self.entries.get(env).cloned()
859    }
860
861    pub fn extend_from_other(&mut self, other: &Env) {
862        self.entries.extend(other.entries.iter().map(|(x, y)| (x.to_owned(), y.to_owned())));
863    }
864
865    pub fn is_empty(&self) -> bool {
866        self.entries.is_empty()
867    }
868
869    pub fn insert(&mut self, k: impl Into<String>, v: impl Into<String>) -> Option<String> {
870        self.entries.insert(k.into(), v.into())
871    }
872}
873
874impl From<Env> for Vec<(String, String)> {
875    fn from(env: Env) -> Vec<(String, String)> {
876        let mut entries: Vec<_> = env.entries.into_iter().collect();
877        entries.sort();
878        entries
879    }
880}
881
882impl<'a> IntoIterator for &'a Env {
883    type Item = (&'a String, &'a String);
884    type IntoIter = std::collections::hash_map::Iter<'a, String, String>;
885
886    fn into_iter(self) -> Self::IntoIter {
887        self.entries.iter()
888    }
889}
890
891#[derive(Debug)]
892pub struct CyclicDependenciesError {
893    path: Vec<(CrateBuilderId, Option<CrateDisplayName>)>,
894}
895
896impl CyclicDependenciesError {
897    fn from(&self) -> &(CrateBuilderId, Option<CrateDisplayName>) {
898        self.path.first().unwrap()
899    }
900    fn to(&self) -> &(CrateBuilderId, Option<CrateDisplayName>) {
901        self.path.last().unwrap()
902    }
903}
904
905impl fmt::Display for CyclicDependenciesError {
906    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
907        let render = |(id, name): &(CrateBuilderId, Option<CrateDisplayName>)| match name {
908            Some(it) => format!("{it}({id:?})"),
909            None => format!("{id:?}"),
910        };
911        let path = self.path.iter().rev().map(render).collect::<Vec<String>>().join(" -> ");
912        write!(
913            f,
914            "cyclic deps: {} -> {}, alternative path: {}",
915            render(self.from()),
916            render(self.to()),
917            path
918        )
919    }
920}
921
922#[cfg(test)]
923mod tests {
924    use triomphe::Arc;
925    use vfs::AbsPathBuf;
926
927    use crate::{CrateWorkspaceData, DependencyBuilder};
928
929    use super::{CrateGraphBuilder, CrateName, CrateOrigin, Edition::Edition2018, Env, FileId};
930
931    fn empty_ws_data() -> Arc<CrateWorkspaceData> {
932        Arc::new(CrateWorkspaceData { data_layout: Err("".into()), toolchain: None })
933    }
934
935    #[test]
936    fn detect_cyclic_dependency_indirect() {
937        let mut graph = CrateGraphBuilder::default();
938        let crate1 = graph.add_crate_root(
939            FileId::from_raw(1u32),
940            Edition2018,
941            None,
942            None,
943            Default::default(),
944            Default::default(),
945            Env::default(),
946            CrateOrigin::Local { repo: None, name: None },
947            false,
948            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
949            empty_ws_data(),
950        );
951        let crate2 = graph.add_crate_root(
952            FileId::from_raw(2u32),
953            Edition2018,
954            None,
955            None,
956            Default::default(),
957            Default::default(),
958            Env::default(),
959            CrateOrigin::Local { repo: None, name: None },
960            false,
961            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
962            empty_ws_data(),
963        );
964        let crate3 = graph.add_crate_root(
965            FileId::from_raw(3u32),
966            Edition2018,
967            None,
968            None,
969            Default::default(),
970            Default::default(),
971            Env::default(),
972            CrateOrigin::Local { repo: None, name: None },
973            false,
974            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
975            empty_ws_data(),
976        );
977        assert!(
978            graph
979                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
980                .is_ok()
981        );
982        assert!(
983            graph
984                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate3").unwrap(), crate3,))
985                .is_ok()
986        );
987        assert!(
988            graph
989                .add_dep(crate3, DependencyBuilder::new(CrateName::new("crate1").unwrap(), crate1,))
990                .is_err()
991        );
992    }
993
994    #[test]
995    fn detect_cyclic_dependency_direct() {
996        let mut graph = CrateGraphBuilder::default();
997        let crate1 = graph.add_crate_root(
998            FileId::from_raw(1u32),
999            Edition2018,
1000            None,
1001            None,
1002            Default::default(),
1003            Default::default(),
1004            Env::default(),
1005            CrateOrigin::Local { repo: None, name: None },
1006            false,
1007            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1008            empty_ws_data(),
1009        );
1010        let crate2 = graph.add_crate_root(
1011            FileId::from_raw(2u32),
1012            Edition2018,
1013            None,
1014            None,
1015            Default::default(),
1016            Default::default(),
1017            Env::default(),
1018            CrateOrigin::Local { repo: None, name: None },
1019            false,
1020            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1021            empty_ws_data(),
1022        );
1023        assert!(
1024            graph
1025                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
1026                .is_ok()
1027        );
1028        assert!(
1029            graph
1030                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
1031                .is_err()
1032        );
1033    }
1034
1035    #[test]
1036    fn it_works() {
1037        let mut graph = CrateGraphBuilder::default();
1038        let crate1 = graph.add_crate_root(
1039            FileId::from_raw(1u32),
1040            Edition2018,
1041            None,
1042            None,
1043            Default::default(),
1044            Default::default(),
1045            Env::default(),
1046            CrateOrigin::Local { repo: None, name: None },
1047            false,
1048            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1049            empty_ws_data(),
1050        );
1051        let crate2 = graph.add_crate_root(
1052            FileId::from_raw(2u32),
1053            Edition2018,
1054            None,
1055            None,
1056            Default::default(),
1057            Default::default(),
1058            Env::default(),
1059            CrateOrigin::Local { repo: None, name: None },
1060            false,
1061            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1062            empty_ws_data(),
1063        );
1064        let crate3 = graph.add_crate_root(
1065            FileId::from_raw(3u32),
1066            Edition2018,
1067            None,
1068            None,
1069            Default::default(),
1070            Default::default(),
1071            Env::default(),
1072            CrateOrigin::Local { repo: None, name: None },
1073            false,
1074            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1075            empty_ws_data(),
1076        );
1077        assert!(
1078            graph
1079                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
1080                .is_ok()
1081        );
1082        assert!(
1083            graph
1084                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate3").unwrap(), crate3,))
1085                .is_ok()
1086        );
1087    }
1088
1089    #[test]
1090    fn dashes_are_normalized() {
1091        let mut graph = CrateGraphBuilder::default();
1092        let crate1 = graph.add_crate_root(
1093            FileId::from_raw(1u32),
1094            Edition2018,
1095            None,
1096            None,
1097            Default::default(),
1098            Default::default(),
1099            Env::default(),
1100            CrateOrigin::Local { repo: None, name: None },
1101            false,
1102            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1103            empty_ws_data(),
1104        );
1105        let crate2 = graph.add_crate_root(
1106            FileId::from_raw(2u32),
1107            Edition2018,
1108            None,
1109            None,
1110            Default::default(),
1111            Default::default(),
1112            Env::default(),
1113            CrateOrigin::Local { repo: None, name: None },
1114            false,
1115            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1116            empty_ws_data(),
1117        );
1118        assert!(
1119            graph
1120                .add_dep(
1121                    crate1,
1122                    DependencyBuilder::new(
1123                        CrateName::normalize_dashes("crate-name-with-dashes"),
1124                        crate2,
1125                    )
1126                )
1127                .is_ok()
1128        );
1129        assert_eq!(
1130            graph.arena[crate1].basic.dependencies,
1131            vec![
1132                DependencyBuilder::new(CrateName::new("crate_name_with_dashes").unwrap(), crate2,)
1133            ]
1134        );
1135    }
1136}
base_db/input.rs

base_db/
input.rs
