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
463/// The mapping from [`UniqueCrateData`] to their [`Crate`] input.
464#[derive(Debug, Default)]
465pub struct CratesMap(DashMap<UniqueCrateData, Crate, BuildHasherDefault<FxHasher>>);
466
467impl CrateGraphBuilder {
468    pub fn add_crate_root(
469        &mut self,
470        root_file_id: FileId,
471        edition: Edition,
472        display_name: Option<CrateDisplayName>,
473        version: Option<String>,
474        mut cfg_options: CfgOptions,
475        mut potential_cfg_options: Option<CfgOptions>,
476        mut env: Env,
477        origin: CrateOrigin,
478        is_proc_macro: bool,
479        proc_macro_cwd: Arc<AbsPathBuf>,
480        ws_data: Arc<CrateWorkspaceData>,
481    ) -> CrateBuilderId {
482        env.entries.shrink_to_fit();
483        cfg_options.shrink_to_fit();
484        if let Some(potential_cfg_options) = &mut potential_cfg_options {
485            potential_cfg_options.shrink_to_fit();
486        }
487        self.arena.alloc(CrateBuilder {
488            basic: CrateData {
489                root_file_id,
490                edition,
491                dependencies: Vec::new(),
492                origin,
493                is_proc_macro,
494                proc_macro_cwd,
495            },
496            extra: ExtraCrateData { version, display_name, potential_cfg_options },
497            cfg_options,
498            env,
499            ws_data,
500        })
501    }
502
503    pub fn add_dep(
504        &mut self,
505        from: CrateBuilderId,
506        dep: DependencyBuilder,
507    ) -> Result<(), CyclicDependenciesError> {
508        let _p = tracing::info_span!("add_dep").entered();
509
510        // Check if adding a dep from `from` to `to` creates a cycle. To figure
511        // that out, look for a  path in the *opposite* direction, from `to` to
512        // `from`.
513        if let Some(path) = self.find_path(&mut FxHashSet::default(), dep.crate_id, from) {
514            let path =
515                path.into_iter().map(|it| (it, self[it].extra.display_name.clone())).collect();
516            let err = CyclicDependenciesError { path };
517            assert!(err.from().0 == from && err.to().0 == dep.crate_id);
518            return Err(err);
519        }
520
521        self.arena[from].basic.dependencies.push(dep);
522        Ok(())
523    }
524
525    pub fn set_in_db(self, db: &mut dyn RootQueryDb) -> CratesIdMap {
526        // For some reason in some repositories we have duplicate crates, so we use a set and not `Vec`.
527        // We use an `IndexSet` because the list needs to be topologically sorted.
528        let mut all_crates = FxIndexSet::with_capacity_and_hasher(self.arena.len(), FxBuildHasher);
529        let mut visited = FxHashMap::default();
530        let mut visited_root_files = FxHashSet::default();
531
532        let old_all_crates = db.all_crates();
533
534        let crates_map = db.crates_map();
535        // 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.
536        for krate in self.iter() {
537            go(
538                &self,
539                db,
540                &crates_map,
541                &mut visited,
542                &mut visited_root_files,
543                &mut all_crates,
544                krate,
545            );
546        }
547
548        if old_all_crates.len() != all_crates.len()
549            || old_all_crates.iter().any(|&krate| !all_crates.contains(&krate))
550        {
551            db.set_all_crates_with_durability(
552                Arc::new(Vec::from_iter(all_crates).into_boxed_slice()),
553                Durability::MEDIUM,
554            );
555        }
556
557        return visited;
558
559        fn go(
560            graph: &CrateGraphBuilder,
561            db: &mut dyn RootQueryDb,
562            crates_map: &CratesMap,
563            visited: &mut FxHashMap<CrateBuilderId, Crate>,
564            visited_root_files: &mut FxHashSet<FileId>,
565            all_crates: &mut FxIndexSet<Crate>,
566            source: CrateBuilderId,
567        ) -> Crate {
568            if let Some(&crate_id) = visited.get(&source) {
569                return crate_id;
570            }
571            let krate = &graph[source];
572            let dependencies = krate
573                .basic
574                .dependencies
575                .iter()
576                .map(|dep| BuiltDependency {
577                    crate_id: go(
578                        graph,
579                        db,
580                        crates_map,
581                        visited,
582                        visited_root_files,
583                        all_crates,
584                        dep.crate_id,
585                    ),
586                    name: dep.name.clone(),
587                    prelude: dep.prelude,
588                    sysroot: dep.sysroot,
589                })
590                .collect::<Vec<_>>();
591            let crate_data = BuiltCrateData {
592                dependencies,
593                edition: krate.basic.edition,
594                is_proc_macro: krate.basic.is_proc_macro,
595                origin: krate.basic.origin.clone(),
596                root_file_id: krate.basic.root_file_id,
597                proc_macro_cwd: krate.basic.proc_macro_cwd.clone(),
598            };
599            let disambiguator = if visited_root_files.insert(krate.basic.root_file_id) {
600                None
601            } else {
602                Some(Box::new((crate_data.clone(), krate.cfg_options.to_hashable())))
603            };
604
605            let unique_crate_data =
606                UniqueCrateData { root_file_id: krate.basic.root_file_id, disambiguator };
607            let crate_input = match crates_map.0.entry(unique_crate_data) {
608                Entry::Occupied(entry) => {
609                    let old_crate = *entry.get();
610                    if crate_data != *old_crate.data(db) {
611                        old_crate.set_data(db).with_durability(Durability::MEDIUM).to(crate_data);
612                    }
613                    if krate.extra != *old_crate.extra_data(db) {
614                        old_crate
615                            .set_extra_data(db)
616                            .with_durability(Durability::MEDIUM)
617                            .to(krate.extra.clone());
618                    }
619                    if krate.cfg_options != *old_crate.cfg_options(db) {
620                        old_crate
621                            .set_cfg_options(db)
622                            .with_durability(Durability::MEDIUM)
623                            .to(krate.cfg_options.clone());
624                    }
625                    if krate.env != *old_crate.env(db) {
626                        old_crate
627                            .set_env(db)
628                            .with_durability(Durability::MEDIUM)
629                            .to(krate.env.clone());
630                    }
631                    if krate.ws_data != *old_crate.workspace_data(db) {
632                        old_crate
633                            .set_workspace_data(db)
634                            .with_durability(Durability::MEDIUM)
635                            .to(krate.ws_data.clone());
636                    }
637                    old_crate
638                }
639                Entry::Vacant(entry) => {
640                    let input = Crate::builder(
641                        crate_data,
642                        krate.extra.clone(),
643                        krate.ws_data.clone(),
644                        krate.cfg_options.clone(),
645                        krate.env.clone(),
646                    )
647                    .durability(Durability::MEDIUM)
648                    .new(db);
649                    entry.insert(input);
650                    input
651                }
652            };
653            all_crates.insert(crate_input);
654            visited.insert(source, crate_input);
655            crate_input
656        }
657    }
658
659    pub fn iter(&self) -> impl Iterator<Item = CrateBuilderId> + '_ {
660        self.arena.iter().map(|(idx, _)| idx)
661    }
662
663    /// Returns an iterator over all transitive dependencies of the given crate,
664    /// including the crate itself.
665    pub fn transitive_deps(&self, of: CrateBuilderId) -> impl Iterator<Item = CrateBuilderId> {
666        let mut worklist = vec![of];
667        let mut deps = FxHashSet::default();
668
669        while let Some(krate) = worklist.pop() {
670            if !deps.insert(krate) {
671                continue;
672            }
673
674            worklist.extend(self[krate].basic.dependencies.iter().map(|dep| dep.crate_id));
675        }
676
677        deps.into_iter()
678    }
679
680    /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
681    /// come before the crate itself).
682    fn crates_in_topological_order(&self) -> Vec<CrateBuilderId> {
683        let mut res = Vec::new();
684        let mut visited = FxHashSet::default();
685
686        for krate in self.iter() {
687            go(self, &mut visited, &mut res, krate);
688        }
689
690        return res;
691
692        fn go(
693            graph: &CrateGraphBuilder,
694            visited: &mut FxHashSet<CrateBuilderId>,
695            res: &mut Vec<CrateBuilderId>,
696            source: CrateBuilderId,
697        ) {
698            if !visited.insert(source) {
699                return;
700            }
701            for dep in graph[source].basic.dependencies.iter() {
702                go(graph, visited, res, dep.crate_id)
703            }
704            res.push(source)
705        }
706    }
707
708    /// Extends this crate graph by adding a complete second crate
709    /// graph and adjust the ids in the [`ProcMacroPaths`] accordingly.
710    ///
711    /// This will deduplicate the crates of the graph where possible.
712    /// Furthermore dependencies are sorted by crate id to make deduplication easier.
713    ///
714    /// Returns a map mapping `other`'s IDs to the new IDs in `self`.
715    pub fn extend(
716        &mut self,
717        mut other: CrateGraphBuilder,
718        proc_macros: &mut ProcMacroPaths,
719    ) -> FxHashMap<CrateBuilderId, CrateBuilderId> {
720        // Sorting here is a bit pointless because the input is likely already sorted.
721        // However, the overhead is small and it makes the `extend` method harder to misuse.
722        self.arena
723            .iter_mut()
724            .for_each(|(_, data)| data.basic.dependencies.sort_by_key(|dep| dep.crate_id));
725
726        let m = self.arena.len();
727        let topo = other.crates_in_topological_order();
728        let mut id_map: FxHashMap<CrateBuilderId, CrateBuilderId> = FxHashMap::default();
729        for topo in topo {
730            let crate_data = &mut other.arena[topo];
731
732            crate_data
733                .basic
734                .dependencies
735                .iter_mut()
736                .for_each(|dep| dep.crate_id = id_map[&dep.crate_id]);
737            crate_data.basic.dependencies.sort_by_key(|dep| dep.crate_id);
738
739            let find = self.arena.iter().take(m).find_map(|(k, v)| (v == crate_data).then_some(k));
740            let new_id = find.unwrap_or_else(|| self.arena.alloc(crate_data.clone()));
741            id_map.insert(topo, new_id);
742        }
743
744        *proc_macros =
745            mem::take(proc_macros).into_iter().map(|(id, macros)| (id_map[&id], macros)).collect();
746        id_map
747    }
748
749    fn find_path(
750        &self,
751        visited: &mut FxHashSet<CrateBuilderId>,
752        from: CrateBuilderId,
753        to: CrateBuilderId,
754    ) -> Option<Vec<CrateBuilderId>> {
755        if !visited.insert(from) {
756            return None;
757        }
758
759        if from == to {
760            return Some(vec![to]);
761        }
762
763        for dep in &self[from].basic.dependencies {
764            let crate_id = dep.crate_id;
765            if let Some(mut path) = self.find_path(visited, crate_id, to) {
766                path.push(from);
767                return Some(path);
768            }
769        }
770
771        None
772    }
773
774    /// Removes all crates from this crate graph except for the ones in `to_keep` and fixes up the dependencies.
775    /// Returns a mapping from old crate ids to new crate ids.
776    pub fn remove_crates_except(
777        &mut self,
778        to_keep: &[CrateBuilderId],
779    ) -> Vec<Option<CrateBuilderId>> {
780        let mut id_map = vec![None; self.arena.len()];
781        self.arena = std::mem::take(&mut self.arena)
782            .into_iter()
783            .filter_map(|(id, data)| if to_keep.contains(&id) { Some((id, data)) } else { None })
784            .enumerate()
785            .map(|(new_id, (id, data))| {
786                id_map[id.into_raw().into_u32() as usize] =
787                    Some(CrateBuilderId::from_raw(RawIdx::from_u32(new_id as u32)));
788                data
789            })
790            .collect();
791        for (_, data) in self.arena.iter_mut() {
792            data.basic.dependencies.iter_mut().for_each(|dep| {
793                dep.crate_id =
794                    id_map[dep.crate_id.into_raw().into_u32() as usize].expect("crate was filtered")
795            });
796        }
797        id_map
798    }
799
800    pub fn shrink_to_fit(&mut self) {
801        self.arena.shrink_to_fit();
802    }
803}
804
805pub(crate) fn transitive_rev_deps(db: &dyn RootQueryDb, of: Crate) -> FxHashSet<Crate> {
806    let mut worklist = vec![of];
807    let mut rev_deps = FxHashSet::default();
808    rev_deps.insert(of);
809
810    let mut inverted_graph = FxHashMap::<_, Vec<_>>::default();
811    db.all_crates().iter().for_each(|&krate| {
812        krate
813            .data(db)
814            .dependencies
815            .iter()
816            .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate))
817    });
818
819    while let Some(krate) = worklist.pop() {
820        if let Some(crate_rev_deps) = inverted_graph.get(&krate) {
821            crate_rev_deps
822                .iter()
823                .copied()
824                .filter(|&rev_dep| rev_deps.insert(rev_dep))
825                .for_each(|rev_dep| worklist.push(rev_dep));
826        }
827    }
828
829    rev_deps
830}
831
832impl BuiltCrateData {
833    pub fn root_file_id(&self, db: &dyn salsa::Database) -> EditionedFileId {
834        EditionedFileId::new(db, self.root_file_id, self.edition)
835    }
836}
837
838impl Extend<(String, String)> for Env {
839    fn extend<T: IntoIterator<Item = (String, String)>>(&mut self, iter: T) {
840        self.entries.extend(iter);
841    }
842}
843
844impl FromIterator<(String, String)> for Env {
845    fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
846        Env { entries: FromIterator::from_iter(iter) }
847    }
848}
849
850impl Env {
851    pub fn set(&mut self, env: &str, value: impl Into<String>) {
852        self.entries.insert(env.to_owned(), value.into());
853    }
854
855    pub fn get(&self, env: &str) -> Option<String> {
856        self.entries.get(env).cloned()
857    }
858
859    pub fn extend_from_other(&mut self, other: &Env) {
860        self.entries.extend(other.entries.iter().map(|(x, y)| (x.to_owned(), y.to_owned())));
861    }
862
863    pub fn is_empty(&self) -> bool {
864        self.entries.is_empty()
865    }
866
867    pub fn insert(&mut self, k: impl Into<String>, v: impl Into<String>) -> Option<String> {
868        self.entries.insert(k.into(), v.into())
869    }
870}
871
872impl From<Env> for Vec<(String, String)> {
873    fn from(env: Env) -> Vec<(String, String)> {
874        let mut entries: Vec<_> = env.entries.into_iter().collect();
875        entries.sort();
876        entries
877    }
878}
879
880impl<'a> IntoIterator for &'a Env {
881    type Item = (&'a String, &'a String);
882    type IntoIter = std::collections::hash_map::Iter<'a, String, String>;
883
884    fn into_iter(self) -> Self::IntoIter {
885        self.entries.iter()
886    }
887}
888
889#[derive(Debug)]
890pub struct CyclicDependenciesError {
891    path: Vec<(CrateBuilderId, Option<CrateDisplayName>)>,
892}
893
894impl CyclicDependenciesError {
895    fn from(&self) -> &(CrateBuilderId, Option<CrateDisplayName>) {
896        self.path.first().unwrap()
897    }
898    fn to(&self) -> &(CrateBuilderId, Option<CrateDisplayName>) {
899        self.path.last().unwrap()
900    }
901}
902
903impl fmt::Display for CyclicDependenciesError {
904    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
905        let render = |(id, name): &(CrateBuilderId, Option<CrateDisplayName>)| match name {
906            Some(it) => format!("{it}({id:?})"),
907            None => format!("{id:?}"),
908        };
909        let path = self.path.iter().rev().map(render).collect::<Vec<String>>().join(" -> ");
910        write!(
911            f,
912            "cyclic deps: {} -> {}, alternative path: {}",
913            render(self.from()),
914            render(self.to()),
915            path
916        )
917    }
918}
919
920#[cfg(test)]
921mod tests {
922    use triomphe::Arc;
923    use vfs::AbsPathBuf;
924
925    use crate::{CrateWorkspaceData, DependencyBuilder};
926
927    use super::{CrateGraphBuilder, CrateName, CrateOrigin, Edition::Edition2018, Env, FileId};
928
929    fn empty_ws_data() -> Arc<CrateWorkspaceData> {
930        Arc::new(CrateWorkspaceData { target: Err("".into()), toolchain: None })
931    }
932
933    #[test]
934    fn detect_cyclic_dependency_indirect() {
935        let mut graph = CrateGraphBuilder::default();
936        let crate1 = graph.add_crate_root(
937            FileId::from_raw(1u32),
938            Edition2018,
939            None,
940            None,
941            Default::default(),
942            Default::default(),
943            Env::default(),
944            CrateOrigin::Local { repo: None, name: None },
945            false,
946            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
947            empty_ws_data(),
948        );
949        let crate2 = graph.add_crate_root(
950            FileId::from_raw(2u32),
951            Edition2018,
952            None,
953            None,
954            Default::default(),
955            Default::default(),
956            Env::default(),
957            CrateOrigin::Local { repo: None, name: None },
958            false,
959            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
960            empty_ws_data(),
961        );
962        let crate3 = graph.add_crate_root(
963            FileId::from_raw(3u32),
964            Edition2018,
965            None,
966            None,
967            Default::default(),
968            Default::default(),
969            Env::default(),
970            CrateOrigin::Local { repo: None, name: None },
971            false,
972            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
973            empty_ws_data(),
974        );
975        assert!(
976            graph
977                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
978                .is_ok()
979        );
980        assert!(
981            graph
982                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate3").unwrap(), crate3,))
983                .is_ok()
984        );
985        assert!(
986            graph
987                .add_dep(crate3, DependencyBuilder::new(CrateName::new("crate1").unwrap(), crate1,))
988                .is_err()
989        );
990    }
991
992    #[test]
993    fn detect_cyclic_dependency_direct() {
994        let mut graph = CrateGraphBuilder::default();
995        let crate1 = graph.add_crate_root(
996            FileId::from_raw(1u32),
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        let crate2 = graph.add_crate_root(
1009            FileId::from_raw(2u32),
1010            Edition2018,
1011            None,
1012            None,
1013            Default::default(),
1014            Default::default(),
1015            Env::default(),
1016            CrateOrigin::Local { repo: None, name: None },
1017            false,
1018            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1019            empty_ws_data(),
1020        );
1021        assert!(
1022            graph
1023                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
1024                .is_ok()
1025        );
1026        assert!(
1027            graph
1028                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
1029                .is_err()
1030        );
1031    }
1032
1033    #[test]
1034    fn it_works() {
1035        let mut graph = CrateGraphBuilder::default();
1036        let crate1 = graph.add_crate_root(
1037            FileId::from_raw(1u32),
1038            Edition2018,
1039            None,
1040            None,
1041            Default::default(),
1042            Default::default(),
1043            Env::default(),
1044            CrateOrigin::Local { repo: None, name: None },
1045            false,
1046            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1047            empty_ws_data(),
1048        );
1049        let crate2 = graph.add_crate_root(
1050            FileId::from_raw(2u32),
1051            Edition2018,
1052            None,
1053            None,
1054            Default::default(),
1055            Default::default(),
1056            Env::default(),
1057            CrateOrigin::Local { repo: None, name: None },
1058            false,
1059            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1060            empty_ws_data(),
1061        );
1062        let crate3 = graph.add_crate_root(
1063            FileId::from_raw(3u32),
1064            Edition2018,
1065            None,
1066            None,
1067            Default::default(),
1068            Default::default(),
1069            Env::default(),
1070            CrateOrigin::Local { repo: None, name: None },
1071            false,
1072            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1073            empty_ws_data(),
1074        );
1075        assert!(
1076            graph
1077                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
1078                .is_ok()
1079        );
1080        assert!(
1081            graph
1082                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate3").unwrap(), crate3,))
1083                .is_ok()
1084        );
1085    }
1086
1087    #[test]
1088    fn dashes_are_normalized() {
1089        let mut graph = CrateGraphBuilder::default();
1090        let crate1 = graph.add_crate_root(
1091            FileId::from_raw(1u32),
1092            Edition2018,
1093            None,
1094            None,
1095            Default::default(),
1096            Default::default(),
1097            Env::default(),
1098            CrateOrigin::Local { repo: None, name: None },
1099            false,
1100            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1101            empty_ws_data(),
1102        );
1103        let crate2 = graph.add_crate_root(
1104            FileId::from_raw(2u32),
1105            Edition2018,
1106            None,
1107            None,
1108            Default::default(),
1109            Default::default(),
1110            Env::default(),
1111            CrateOrigin::Local { repo: None, name: None },
1112            false,
1113            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
1114            empty_ws_data(),
1115        );
1116        assert!(
1117            graph
1118                .add_dep(
1119                    crate1,
1120                    DependencyBuilder::new(
1121                        CrateName::normalize_dashes("crate-name-with-dashes"),
1122                        crate2,
1123                    )
1124                )
1125                .is_ok()
1126        );
1127        assert_eq!(
1128            graph.arena[crate1].basic.dependencies,
1129            vec![
1130                DependencyBuilder::new(CrateName::new("crate_name_with_dashes").unwrap(), crate2,)
1131            ]
1132        );
1133    }
1134}
base_db/input.rs

base_db/
input.rs
