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
298#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
299pub enum ReleaseChannel {
300    Stable,
301    Beta,
302    Nightly,
303}
304
305impl ReleaseChannel {
306    pub fn as_str(self) -> &'static str {
307        match self {
308            ReleaseChannel::Stable => "stable",
309            ReleaseChannel::Beta => "beta",
310            ReleaseChannel::Nightly => "nightly",
311        }
312    }
313
314    #[allow(clippy::should_implement_trait)]
315    pub fn from_str(str: &str) -> Option<Self> {
316        Some(match str {
317            "" | "stable" => ReleaseChannel::Stable,
318            "nightly" => ReleaseChannel::Nightly,
319            _ if str.starts_with("beta") => ReleaseChannel::Beta,
320            _ => return None,
321        })
322    }
323}
324
325/// The crate data from which we derive the `Crate`.
326///
327/// We want this to contain as little data as possible, because if it contains dependencies and
328/// something changes, this crate and all of its dependencies ids are invalidated, which causes
329/// pretty much everything to be recomputed. If the crate id is not invalidated, only this crate's
330/// information needs to be recomputed.
331///
332/// *Most* different crates have different root files (actually, pretty much all of them).
333/// Still, it is possible to have crates distinguished by other factors (e.g. dependencies).
334/// So we store only the root file - unless we find that this crate has the same root file as
335/// another crate, in which case we store all data for one of them (if one is a dependency of
336/// the other, we store for it, because it has more dependencies to be invalidated).
337#[derive(Debug, Clone, PartialEq, Eq, Hash)]
338pub struct UniqueCrateData {
339    root_file_id: FileId,
340    disambiguator: Option<Box<(BuiltCrateData, HashableCfgOptions)>>,
341}
342
343#[derive(Debug, Clone, PartialEq, Eq, Hash)]
344pub struct CrateData<Id> {
345    pub root_file_id: FileId,
346    pub edition: Edition,
347    /// The dependencies of this crate.
348    ///
349    /// Note that this may contain more dependencies than the crate actually uses.
350    /// A common example is the test crate which is included but only actually is active when
351    /// declared in source via `extern crate test`.
352    pub dependencies: Vec<Dependency<Id>>,
353    pub origin: CrateOrigin,
354    pub is_proc_macro: bool,
355    /// The working directory to run proc-macros in invoked in the context of this crate.
356    /// This is the workspace root of the cargo workspace for workspace members, the crate manifest
357    /// dir otherwise.
358    // FIXME: This ought to be a `VfsPath` or something opaque.
359    pub proc_macro_cwd: Arc<AbsPathBuf>,
360}
361
362pub type CrateDataBuilder = CrateData<CrateBuilderId>;
363pub type BuiltCrateData = CrateData<Crate>;
364
365/// Crate data unrelated to analysis.
366#[derive(Debug, Clone, PartialEq, Eq)]
367pub struct ExtraCrateData {
368    pub version: Option<String>,
369    /// A name used in the package's project declaration: for Cargo projects,
370    /// its `[package].name` can be different for other project types or even
371    /// absent (a dummy crate for the code snippet, for example).
372    ///
373    /// For purposes of analysis, crates are anonymous (only names in
374    /// `Dependency` matters), this name should only be used for UI.
375    pub display_name: Option<CrateDisplayName>,
376    /// The cfg options that could be used by the crate
377    pub potential_cfg_options: Option<CfgOptions>,
378}
379
380#[derive(Default, Clone, PartialEq, Eq)]
381pub struct Env {
382    entries: FxHashMap<String, String>,
383}
384
385impl fmt::Debug for Env {
386    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
387        struct EnvDebug<'s>(Vec<(&'s String, &'s String)>);
388
389        impl fmt::Debug for EnvDebug<'_> {
390            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
391                f.debug_map().entries(self.0.iter().copied()).finish()
392            }
393        }
394        f.debug_struct("Env")
395            .field("entries", &{
396                let mut entries: Vec<_> = self.entries.iter().collect();
397                entries.sort();
398                EnvDebug(entries)
399            })
400            .finish()
401    }
402}
403
404#[derive(Debug, Clone, PartialEq, Eq, Hash)]
405pub struct Dependency<Id> {
406    pub crate_id: Id,
407    pub name: CrateName,
408    prelude: bool,
409    sysroot: bool,
410}
411
412pub type DependencyBuilder = Dependency<CrateBuilderId>;
413pub type BuiltDependency = Dependency<Crate>;
414
415impl DependencyBuilder {
416    pub fn new(name: CrateName, crate_id: CrateBuilderId) -> Self {
417        Self { name, crate_id, prelude: true, sysroot: false }
418    }
419
420    pub fn with_prelude(
421        name: CrateName,
422        crate_id: CrateBuilderId,
423        prelude: bool,
424        sysroot: bool,
425    ) -> Self {
426        Self { name, crate_id, prelude, sysroot }
427    }
428}
429
430impl BuiltDependency {
431    /// Whether this dependency is to be added to the depending crate's extern prelude.
432    pub fn is_prelude(&self) -> bool {
433        self.prelude
434    }
435
436    /// Whether this dependency is a sysroot injected one.
437    pub fn is_sysroot(&self) -> bool {
438        self.sysroot
439    }
440}
441
442pub type CratesIdMap = FxHashMap<CrateBuilderId, Crate>;
443
444#[salsa_macros::input]
445#[derive(Debug, PartialOrd, Ord)]
446pub struct Crate {
447    #[returns(ref)]
448    pub data: BuiltCrateData,
449    /// Crate data that is not needed for analysis.
450    ///
451    /// This is split into a separate field to increase incrementality.
452    #[returns(ref)]
453    pub extra_data: ExtraCrateData,
454    // This is in `Arc` because it is shared for all crates in a workspace.
455    #[returns(ref)]
456    pub workspace_data: Arc<CrateWorkspaceData>,
457    #[returns(ref)]
458    pub cfg_options: CfgOptions,
459    #[returns(ref)]
460    pub env: Env,
461}
462
463impl Crate {
464    /// Returns an iterator over all transitive dependencies of the given crate,
465    /// including the crate itself.
466    ///
467    /// **Warning**: do not use this query in `hir-*` crates! It kills incrementality across crate metadata modifications.
468    pub fn transitive_deps(self, db: &dyn salsa::Database) -> Vec<Crate> {
469        // There is a bit of duplication here and in `CrateGraphBuilder` in the same method, but it's not terrible
470        // and removing that is a bit difficult.
471        let mut worklist = vec![self];
472        let mut deps_seen = FxHashSet::default();
473        let mut deps = Vec::new();
474
475        while let Some(krate) = worklist.pop() {
476            if !deps_seen.insert(krate) {
477                continue;
478            }
479            deps.push(krate);
480
481            worklist.extend(krate.data(db).dependencies.iter().map(|dep| dep.crate_id));
482        }
483        deps
484    }
485
486    /// Returns all transitive reverse dependencies of the given crate,
487    /// including the crate itself.
488    ///
489    /// **Warning**: do not use this query in `hir-*` crates! It kills incrementality across crate metadata modifications.
490    pub fn transitive_rev_deps(self, db: &dyn RootQueryDb) -> Box<[Crate]> {
491        let mut worklist = vec![self];
492        let mut rev_deps = FxHashSet::default();
493        rev_deps.insert(self);
494
495        let mut inverted_graph = FxHashMap::<_, Vec<_>>::default();
496        db.all_crates().iter().for_each(|&krate| {
497            krate
498                .data(db)
499                .dependencies
500                .iter()
501                .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate))
502        });
503
504        while let Some(krate) = worklist.pop() {
505            if let Some(crate_rev_deps) = inverted_graph.get(&krate) {
506                crate_rev_deps
507                    .iter()
508                    .copied()
509                    .filter(|&rev_dep| rev_deps.insert(rev_dep))
510                    .for_each(|rev_dep| worklist.push(rev_dep));
511            }
512        }
513
514        rev_deps.into_iter().collect::<Box<_>>()
515    }
516}
517
518/// The mapping from [`UniqueCrateData`] to their [`Crate`] input.
519#[derive(Debug, Default)]
520pub struct CratesMap(DashMap<UniqueCrateData, Crate, BuildHasherDefault<FxHasher>>);
521
522impl CrateGraphBuilder {
523    pub fn add_crate_root(
524        &mut self,
525        root_file_id: FileId,
526        edition: Edition,
527        display_name: Option<CrateDisplayName>,
528        version: Option<String>,
529        mut cfg_options: CfgOptions,
530        mut potential_cfg_options: Option<CfgOptions>,
531        mut env: Env,
532        origin: CrateOrigin,
533        is_proc_macro: bool,
534        proc_macro_cwd: Arc<AbsPathBuf>,
535        ws_data: Arc<CrateWorkspaceData>,
536    ) -> CrateBuilderId {
537        env.entries.shrink_to_fit();
538        cfg_options.shrink_to_fit();
539        if let Some(potential_cfg_options) = &mut potential_cfg_options {
540            potential_cfg_options.shrink_to_fit();
541        }
542        self.arena.alloc(CrateBuilder {
543            basic: CrateData {
544                root_file_id,
545                edition,
546                dependencies: Vec::new(),
547                origin,
548                is_proc_macro,
549                proc_macro_cwd,
550            },
551            extra: ExtraCrateData { version, display_name, potential_cfg_options },
552            cfg_options,
553            env,
554            ws_data,
555        })
556    }
557
558    pub fn add_dep(
559        &mut self,
560        from: CrateBuilderId,
561        dep: DependencyBuilder,
562    ) -> Result<(), CyclicDependenciesError> {
563        let _p = tracing::info_span!("add_dep").entered();
564
565        // Check if adding a dep from `from` to `to` creates a cycle. To figure
566        // that out, look for a  path in the *opposite* direction, from `to` to
567        // `from`.
568        if let Some(path) = self.find_path(&mut FxHashSet::default(), dep.crate_id, from) {
569            let path =
570                path.into_iter().map(|it| (it, self[it].extra.display_name.clone())).collect();
571            let err = CyclicDependenciesError { path };
572            assert!(err.from().0 == from && err.to().0 == dep.crate_id);
573            return Err(err);
574        }
575
576        self.arena[from].basic.dependencies.push(dep);
577        Ok(())
578    }
579
580    pub fn set_in_db(self, db: &mut dyn RootQueryDb) -> CratesIdMap {
581        // For some reason in some repositories we have duplicate crates, so we use a set and not `Vec`.
582        // We use an `IndexSet` because the list needs to be topologically sorted.
583        let mut all_crates = FxIndexSet::with_capacity_and_hasher(self.arena.len(), FxBuildHasher);
584        let mut visited = FxHashMap::default();
585        let mut visited_root_files = FxHashSet::default();
586
587        let old_all_crates = db.all_crates();
588
589        let crates_map = db.crates_map();
590        // 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.
591        for krate in self.iter() {
592            go(
593                &self,
594                db,
595                &crates_map,
596                &mut visited,
597                &mut visited_root_files,
598                &mut all_crates,
599                krate,
600            );
601        }
602
603        if old_all_crates.len() != all_crates.len()
604            || old_all_crates.iter().any(|&krate| !all_crates.contains(&krate))
605        {
606            db.set_all_crates_with_durability(
607                Arc::new(Vec::from_iter(all_crates).into_boxed_slice()),
608                Durability::MEDIUM,
609            );
610        }
611
612        return visited;
613
614        fn go(
615            graph: &CrateGraphBuilder,
616            db: &mut dyn RootQueryDb,
617            crates_map: &CratesMap,
618            visited: &mut FxHashMap<CrateBuilderId, Crate>,
619            visited_root_files: &mut FxHashSet<FileId>,
620            all_crates: &mut FxIndexSet<Crate>,
621            source: CrateBuilderId,
622        ) -> Crate {
623            if let Some(&crate_id) = visited.get(&source) {
624                return crate_id;
625            }
626            let krate = &graph[source];
627            let dependencies = krate
628                .basic
629                .dependencies
630                .iter()
631                .map(|dep| BuiltDependency {
632                    crate_id: go(
633                        graph,
634                        db,
635                        crates_map,
636                        visited,
637                        visited_root_files,
638                        all_crates,
639                        dep.crate_id,
640                    ),
641                    name: dep.name.clone(),
642                    prelude: dep.prelude,
643                    sysroot: dep.sysroot,
644                })
645                .collect::<Vec<_>>();
646            let crate_data = BuiltCrateData {
647                dependencies,
648                edition: krate.basic.edition,
649                is_proc_macro: krate.basic.is_proc_macro,
650                origin: krate.basic.origin.clone(),
651                root_file_id: krate.basic.root_file_id,
652                proc_macro_cwd: krate.basic.proc_macro_cwd.clone(),
653            };
654            let disambiguator = if visited_root_files.insert(krate.basic.root_file_id) {
655                None
656            } else {
657                Some(Box::new((crate_data.clone(), krate.cfg_options.to_hashable())))
658            };
659
660            let unique_crate_data =
661                UniqueCrateData { root_file_id: krate.basic.root_file_id, disambiguator };
662            let crate_input = match crates_map.0.entry(unique_crate_data) {
663                Entry::Occupied(entry) => {
664                    let old_crate = *entry.get();
665                    if crate_data != *old_crate.data(db) {
666                        old_crate.set_data(db).with_durability(Durability::MEDIUM).to(crate_data);
667                    }
668                    if krate.extra != *old_crate.extra_data(db) {
669                        old_crate
670                            .set_extra_data(db)
671                            .with_durability(Durability::MEDIUM)
672                            .to(krate.extra.clone());
673                    }
674                    if krate.cfg_options != *old_crate.cfg_options(db) {
675                        old_crate
676                            .set_cfg_options(db)
677                            .with_durability(Durability::MEDIUM)
678                            .to(krate.cfg_options.clone());
679                    }
680                    if krate.env != *old_crate.env(db) {
681                        old_crate
682                            .set_env(db)
683                            .with_durability(Durability::MEDIUM)
684                            .to(krate.env.clone());
685                    }
686                    if krate.ws_data != *old_crate.workspace_data(db) {
687                        old_crate
688                            .set_workspace_data(db)
689                            .with_durability(Durability::MEDIUM)
690                            .to(krate.ws_data.clone());
691                    }
692                    old_crate
693                }
694                Entry::Vacant(entry) => {
695                    let input = Crate::builder(
696                        crate_data,
697                        krate.extra.clone(),
698                        krate.ws_data.clone(),
699                        krate.cfg_options.clone(),
700                        krate.env.clone(),
701                    )
702                    .durability(Durability::MEDIUM)
703                    .new(db);
704                    entry.insert(input);
705                    input
706                }
707            };
708            all_crates.insert(crate_input);
709            visited.insert(source, crate_input);
710            crate_input
711        }
712    }
713
714    pub fn iter(&self) -> impl Iterator<Item = CrateBuilderId> + '_ {
715        self.arena.iter().map(|(idx, _)| idx)
716    }
717
718    /// Returns an iterator over all transitive dependencies of the given crate,
719    /// including the crate itself.
720    pub fn transitive_deps(&self, of: CrateBuilderId) -> impl Iterator<Item = CrateBuilderId> {
721        let mut worklist = vec![of];
722        let mut deps = FxHashSet::default();
723
724        while let Some(krate) = worklist.pop() {
725            if !deps.insert(krate) {
726                continue;
727            }
728
729            worklist.extend(self[krate].basic.dependencies.iter().map(|dep| dep.crate_id));
730        }
731
732        deps.into_iter()
733    }
734
735    /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
736    /// come before the crate itself).
737    fn crates_in_topological_order(&self) -> Vec<CrateBuilderId> {
738        let mut res = Vec::new();
739        let mut visited = FxHashSet::default();
740
741        for krate in self.iter() {
742            go(self, &mut visited, &mut res, krate);
743        }
744
745        return res;
746
747        fn go(
748            graph: &CrateGraphBuilder,
749            visited: &mut FxHashSet<CrateBuilderId>,
750            res: &mut Vec<CrateBuilderId>,
751            source: CrateBuilderId,
752        ) {
753            if !visited.insert(source) {
754                return;
755            }
756            for dep in graph[source].basic.dependencies.iter() {
757                go(graph, visited, res, dep.crate_id)
758            }
759            res.push(source)
760        }
761    }
762
763    /// Extends this crate graph by adding a complete second crate
764    /// graph and adjust the ids in the [`ProcMacroPaths`] accordingly.
765    ///
766    /// This will deduplicate the crates of the graph where possible.
767    /// Furthermore dependencies are sorted by crate id to make deduplication easier.
768    ///
769    /// Returns a map mapping `other`'s IDs to the new IDs in `self`.
770    pub fn extend(
771        &mut self,
772        mut other: CrateGraphBuilder,
773        proc_macros: &mut ProcMacroPaths,
774    ) -> FxHashMap<CrateBuilderId, CrateBuilderId> {
775        // Sorting here is a bit pointless because the input is likely already sorted.
776        // However, the overhead is small and it makes the `extend` method harder to misuse.
777        self.arena
778            .iter_mut()
779            .for_each(|(_, data)| data.basic.dependencies.sort_by_key(|dep| dep.crate_id));
780
781        let m = self.arena.len();
782        let topo = other.crates_in_topological_order();
783        let mut id_map: FxHashMap<CrateBuilderId, CrateBuilderId> = FxHashMap::default();
784        for topo in topo {
785            let crate_data = &mut other.arena[topo];
786
787            crate_data
788                .basic
789                .dependencies
790                .iter_mut()
791                .for_each(|dep| dep.crate_id = id_map[&dep.crate_id]);
792            crate_data.basic.dependencies.sort_by_key(|dep| dep.crate_id);
793
794            let find = self.arena.iter().take(m).find_map(|(k, v)| (v == crate_data).then_some(k));
795            let new_id = find.unwrap_or_else(|| self.arena.alloc(crate_data.clone()));
796            id_map.insert(topo, new_id);
797        }
798
799        *proc_macros =
800            mem::take(proc_macros).into_iter().map(|(id, macros)| (id_map[&id], macros)).collect();
801        id_map
802    }
803
804    fn find_path(
805        &self,
806        visited: &mut FxHashSet<CrateBuilderId>,
807        from: CrateBuilderId,
808        to: CrateBuilderId,
809    ) -> Option<Vec<CrateBuilderId>> {
810        if !visited.insert(from) {
811            return None;
812        }
813
814        if from == to {
815            return Some(vec![to]);
816        }
817
818        for dep in &self[from].basic.dependencies {
819            let crate_id = dep.crate_id;
820            if let Some(mut path) = self.find_path(visited, crate_id, to) {
821                path.push(from);
822                return Some(path);
823            }
824        }
825
826        None
827    }
828
829    /// Removes all crates from this crate graph except for the ones in `to_keep` and fixes up the dependencies.
830    /// Returns a mapping from old crate ids to new crate ids.
831    pub fn remove_crates_except(
832        &mut self,
833        to_keep: &[CrateBuilderId],
834    ) -> Vec<Option<CrateBuilderId>> {
835        let mut id_map = vec![None; self.arena.len()];
836        self.arena = std::mem::take(&mut self.arena)
837            .into_iter()
838            .filter_map(|(id, data)| if to_keep.contains(&id) { Some((id, data)) } else { None })
839            .enumerate()
840            .map(|(new_id, (id, data))| {
841                id_map[id.into_raw().into_u32() as usize] =
842                    Some(CrateBuilderId::from_raw(RawIdx::from_u32(new_id as u32)));
843                data
844            })
845            .collect();
846        for (_, data) in self.arena.iter_mut() {
847            data.basic.dependencies.iter_mut().for_each(|dep| {
848                dep.crate_id =
849                    id_map[dep.crate_id.into_raw().into_u32() as usize].expect("crate was filtered")
850            });
851        }
852        id_map
853    }
854
855    pub fn shrink_to_fit(&mut self) {
856        self.arena.shrink_to_fit();
857    }
858}
859
860impl Crate {
861    pub fn root_file_id(self, db: &dyn salsa::Database) -> EditionedFileId {
862        let data = self.data(db);
863        EditionedFileId::new(db, data.root_file_id, data.edition, self)
864    }
865}
866
867impl Extend<(String, String)> for Env {
868    fn extend<T: IntoIterator<Item = (String, String)>>(&mut self, iter: T) {
869        self.entries.extend(iter);
870    }
871}
872
873impl FromIterator<(String, String)> for Env {
874    fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
875        Env { entries: FromIterator::from_iter(iter) }
876    }
877}
878
879impl Env {
880    pub fn set(&mut self, env: &str, value: impl Into<String>) {
881        self.entries.insert(env.to_owned(), value.into());
882    }
883
884    pub fn get(&self, env: &str) -> Option<String> {
885        self.entries.get(env).cloned()
886    }
887
888    pub fn extend_from_other(&mut self, other: &Env) {
889        self.entries.extend(other.entries.iter().map(|(x, y)| (x.to_owned(), y.to_owned())));
890    }
891
892    pub fn is_empty(&self) -> bool {
893        self.entries.is_empty()
894    }
895
896    pub fn insert(&mut self, k: impl Into<String>, v: impl Into<String>) -> Option<String> {
897        self.entries.insert(k.into(), v.into())
898    }
899
900    pub fn contains_key(&self, arg: &str) -> bool {
901        self.entries.contains_key(arg)
902    }
903}
904
905impl From<Env> for Vec<(String, String)> {
906    fn from(env: Env) -> Vec<(String, String)> {
907        let mut entries: Vec<_> = env.entries.into_iter().collect();
908        entries.sort();
909        entries
910    }
911}
912
913impl<'a> IntoIterator for &'a Env {
914    type Item = (&'a String, &'a String);
915    type IntoIter = std::collections::hash_map::Iter<'a, String, String>;
916
917    fn into_iter(self) -> Self::IntoIter {
918        self.entries.iter()
919    }
920}
921
922#[derive(Debug)]
923pub struct CyclicDependenciesError {
924    path: Vec<(CrateBuilderId, Option<CrateDisplayName>)>,
925}
926
927impl CyclicDependenciesError {
928    fn from(&self) -> &(CrateBuilderId, Option<CrateDisplayName>) {
929        self.path.first().unwrap()
930    }
931    fn to(&self) -> &(CrateBuilderId, Option<CrateDisplayName>) {
932        self.path.last().unwrap()
933    }
934}
935
936impl fmt::Display for CyclicDependenciesError {
937    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
938        let render = |(id, name): &(CrateBuilderId, Option<CrateDisplayName>)| match name {
939            Some(it) => format!("{it}({id:?})"),
940            None => format!("{id:?}"),
941        };
942        let path = self.path.iter().rev().map(render).collect::<Vec<String>>().join(" -> ");
943        write!(
944            f,
945            "cyclic deps: {} -> {}, alternative path: {}",
946            render(self.from()),
947            render(self.to()),
948            path
949        )
950    }
951}
952
953#[cfg(test)]
954mod tests {
955    use triomphe::Arc;
956    use vfs::AbsPathBuf;
957
958    use crate::{CrateWorkspaceData, DependencyBuilder};
959
960    use super::{CrateGraphBuilder, CrateName, CrateOrigin, Edition::Edition2018, Env, FileId};
961
962    fn empty_ws_data() -> Arc<CrateWorkspaceData> {
963        Arc::new(CrateWorkspaceData { target: Err("".into()), toolchain: None })
964    }
965
966    #[test]
967    fn detect_cyclic_dependency_indirect() {
968        let mut graph = CrateGraphBuilder::default();
969        let crate1 = graph.add_crate_root(
970            FileId::from_raw(1u32),
971            Edition2018,
972            None,
973            None,
974            Default::default(),
975            Default::default(),
976            Env::default(),
977            CrateOrigin::Local { repo: None, name: None },
978            false,
979            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
980            empty_ws_data(),
981        );
982        let crate2 = graph.add_crate_root(
983            FileId::from_raw(2u32),
984            Edition2018,
985            None,
986            None,
987            Default::default(),
988            Default::default(),
989            Env::default(),
990            CrateOrigin::Local { repo: None, name: None },
991            false,
992            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
993            empty_ws_data(),
994        );
995        let crate3 = graph.add_crate_root(
996            FileId::from_raw(3u32),
997            Edition2018,
998            None,
999            None,
1000            Default::default(),
1001            Default::default(),
1002            Env::default(),
1003            CrateOrigin::Local { repo: None, name: None },
1004            false,
1005            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1006            empty_ws_data(),
1007        );
1008        assert!(
1009            graph
1010                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
1011                .is_ok()
1012        );
1013        assert!(
1014            graph
1015                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate3").unwrap(), crate3,))
1016                .is_ok()
1017        );
1018        assert!(
1019            graph
1020                .add_dep(crate3, DependencyBuilder::new(CrateName::new("crate1").unwrap(), crate1,))
1021                .is_err()
1022        );
1023    }
1024
1025    #[test]
1026    fn detect_cyclic_dependency_direct() {
1027        let mut graph = CrateGraphBuilder::default();
1028        let crate1 = graph.add_crate_root(
1029            FileId::from_raw(1u32),
1030            Edition2018,
1031            None,
1032            None,
1033            Default::default(),
1034            Default::default(),
1035            Env::default(),
1036            CrateOrigin::Local { repo: None, name: None },
1037            false,
1038            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1039            empty_ws_data(),
1040        );
1041        let crate2 = graph.add_crate_root(
1042            FileId::from_raw(2u32),
1043            Edition2018,
1044            None,
1045            None,
1046            Default::default(),
1047            Default::default(),
1048            Env::default(),
1049            CrateOrigin::Local { repo: None, name: None },
1050            false,
1051            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1052            empty_ws_data(),
1053        );
1054        assert!(
1055            graph
1056                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
1057                .is_ok()
1058        );
1059        assert!(
1060            graph
1061                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
1062                .is_err()
1063        );
1064    }
1065
1066    #[test]
1067    fn it_works() {
1068        let mut graph = CrateGraphBuilder::default();
1069        let crate1 = graph.add_crate_root(
1070            FileId::from_raw(1u32),
1071            Edition2018,
1072            None,
1073            None,
1074            Default::default(),
1075            Default::default(),
1076            Env::default(),
1077            CrateOrigin::Local { repo: None, name: None },
1078            false,
1079            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1080            empty_ws_data(),
1081        );
1082        let crate2 = graph.add_crate_root(
1083            FileId::from_raw(2u32),
1084            Edition2018,
1085            None,
1086            None,
1087            Default::default(),
1088            Default::default(),
1089            Env::default(),
1090            CrateOrigin::Local { repo: None, name: None },
1091            false,
1092            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1093            empty_ws_data(),
1094        );
1095        let crate3 = graph.add_crate_root(
1096            FileId::from_raw(3u32),
1097            Edition2018,
1098            None,
1099            None,
1100            Default::default(),
1101            Default::default(),
1102            Env::default(),
1103            CrateOrigin::Local { repo: None, name: None },
1104            false,
1105            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1106            empty_ws_data(),
1107        );
1108        assert!(
1109            graph
1110                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
1111                .is_ok()
1112        );
1113        assert!(
1114            graph
1115                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate3").unwrap(), crate3,))
1116                .is_ok()
1117        );
1118    }
1119
1120    #[test]
1121    fn dashes_are_normalized() {
1122        let mut graph = CrateGraphBuilder::default();
1123        let crate1 = graph.add_crate_root(
1124            FileId::from_raw(1u32),
1125            Edition2018,
1126            None,
1127            None,
1128            Default::default(),
1129            Default::default(),
1130            Env::default(),
1131            CrateOrigin::Local { repo: None, name: None },
1132            false,
1133            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1134            empty_ws_data(),
1135        );
1136        let crate2 = graph.add_crate_root(
1137            FileId::from_raw(2u32),
1138            Edition2018,
1139            None,
1140            None,
1141            Default::default(),
1142            Default::default(),
1143            Env::default(),
1144            CrateOrigin::Local { repo: None, name: None },
1145            false,
1146            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1147            empty_ws_data(),
1148        );
1149        assert!(
1150            graph
1151                .add_dep(
1152                    crate1,
1153                    DependencyBuilder::new(
1154                        CrateName::normalize_dashes("crate-name-with-dashes"),
1155                        crate2,
1156                    )
1157                )
1158                .is_ok()
1159        );
1160        assert_eq!(
1161            graph.arena[crate1].basic.dependencies,
1162            vec![
1163                DependencyBuilder::new(CrateName::new("crate_name_with_dashes").unwrap(), crate2,)
1164            ]
1165        );
1166    }
1167}
base_db/input.rs

base_db/
input.rs
