]> git.lizzy.rs Git - rust.git/blob - crates/base_db/src/input.rs
Fix standard library doclinks not going to the correct page
[rust.git] / crates / base_db / src / 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
9 use std::{fmt, iter::FromIterator, ops, panic::RefUnwindSafe, str::FromStr, sync::Arc};
10
11 use cfg::CfgOptions;
12 use rustc_hash::{FxHashMap, FxHashSet};
13 use syntax::SmolStr;
14 use tt::Subtree;
15 use vfs::{file_set::FileSet, FileId, VfsPath};
16
17 /// Files are grouped into source roots. A source root is a directory on the
18 /// file systems which is watched for changes. Typically it corresponds to a
19 /// Rust crate. Source roots *might* be nested: in this case, a file belongs to
20 /// the nearest enclosing source root. Paths to files are always relative to a
21 /// source root, and the analyzer does not know the root path of the source root at
22 /// all. So, a file from one source root can't refer to a file in another source
23 /// root by path.
24 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
25 pub struct SourceRootId(pub u32);
26
27 #[derive(Clone, Debug, PartialEq, Eq)]
28 pub struct SourceRoot {
29     /// Sysroot or crates.io library.
30     ///
31     /// Libraries are considered mostly immutable, this assumption is used to
32     /// optimize salsa's query structure
33     pub is_library: bool,
34     pub(crate) file_set: FileSet,
35 }
36
37 impl SourceRoot {
38     pub fn new_local(file_set: FileSet) -> SourceRoot {
39         SourceRoot { is_library: false, file_set }
40     }
41     pub fn new_library(file_set: FileSet) -> SourceRoot {
42         SourceRoot { is_library: true, file_set }
43     }
44     pub fn path_for_file(&self, file: &FileId) -> Option<&VfsPath> {
45         self.file_set.path_for_file(file)
46     }
47     pub fn file_for_path(&self, path: &VfsPath) -> Option<&FileId> {
48         self.file_set.file_for_path(path)
49     }
50     pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
51         self.file_set.iter()
52     }
53 }
54
55 /// `CrateGraph` is a bit of information which turns a set of text files into a
56 /// number of Rust crates.
57 ///
58 /// Each crate is defined by the `FileId` of its root module, the set of enabled
59 /// `cfg` flags and the set of dependencies.
60 ///
61 /// Note that, due to cfg's, there might be several crates for a single `FileId`!
62 ///
63 /// For the purposes of analysis, a crate does not have a name. Instead, names
64 /// are specified on dependency edges. That is, a crate might be known under
65 /// different names in different dependent crates.
66 ///
67 /// Note that `CrateGraph` is build-system agnostic: it's a concept of the Rust
68 /// language proper, not a concept of the build system. In practice, we get
69 /// `CrateGraph` by lowering `cargo metadata` output.
70 ///
71 /// `CrateGraph` is `!Serialize` by design, see
72 /// <https://github.com/rust-analyzer/rust-analyzer/blob/master/docs/dev/architecture.md#serialization>
73 #[derive(Debug, Clone, Default /* Serialize, Deserialize */)]
74 pub struct CrateGraph {
75     arena: FxHashMap<CrateId, CrateData>,
76 }
77
78 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
79 pub struct CrateId(pub u32);
80
81 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
82 pub struct CrateName(SmolStr);
83
84 impl CrateName {
85     /// Creates a crate name, checking for dashes in the string provided.
86     /// Dashes are not allowed in the crate names,
87     /// hence the input string is returned as `Err` for those cases.
88     pub fn new(name: &str) -> Result<CrateName, &str> {
89         if name.contains('-') {
90             Err(name)
91         } else {
92             Ok(Self(SmolStr::new(name)))
93         }
94     }
95
96     /// Creates a crate name, unconditionally replacing the dashes with underscores.
97     pub fn normalize_dashes(name: &str) -> CrateName {
98         Self(SmolStr::new(name.replace('-', "_")))
99     }
100 }
101
102 impl fmt::Display for CrateName {
103     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
104         write!(f, "{}", self.0)
105     }
106 }
107
108 impl ops::Deref for CrateName {
109     type Target = str;
110     fn deref(&self) -> &str {
111         &*self.0
112     }
113 }
114
115 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
116 pub struct CrateDisplayName {
117     // The name we use to display various paths (with `_`).
118     crate_name: CrateName,
119     // The name as specified in Cargo.toml (with `-`).
120     canonical_name: String,
121 }
122
123 impl CrateDisplayName {
124     pub fn canonical_name(&self) -> &str {
125         &self.canonical_name
126     }
127     pub fn crate_name(&self) -> &CrateName {
128         &self.crate_name
129     }
130 }
131
132 impl From<CrateName> for CrateDisplayName {
133     fn from(crate_name: CrateName) -> CrateDisplayName {
134         let canonical_name = crate_name.to_string();
135         CrateDisplayName { crate_name, canonical_name }
136     }
137 }
138
139 impl fmt::Display for CrateDisplayName {
140     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
141         write!(f, "{}", self.crate_name)
142     }
143 }
144
145 impl ops::Deref for CrateDisplayName {
146     type Target = str;
147     fn deref(&self) -> &str {
148         &*self.crate_name
149     }
150 }
151
152 impl CrateDisplayName {
153     pub fn from_canonical_name(canonical_name: String) -> CrateDisplayName {
154         let crate_name = CrateName::normalize_dashes(&canonical_name);
155         CrateDisplayName { crate_name, canonical_name }
156     }
157 }
158
159 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
160 pub struct ProcMacroId(pub u32);
161
162 #[derive(Copy, Clone, Eq, PartialEq, Debug, Hash)]
163 pub enum ProcMacroKind {
164     CustomDerive,
165     FuncLike,
166     Attr,
167 }
168
169 pub trait ProcMacroExpander: fmt::Debug + Send + Sync + RefUnwindSafe {
170     fn expand(
171         &self,
172         subtree: &Subtree,
173         attrs: Option<&Subtree>,
174         env: &Env,
175     ) -> Result<Subtree, ProcMacroExpansionError>;
176 }
177
178 pub enum ProcMacroExpansionError {
179     Panic(String),
180     /// Things like "proc macro server was killed by OOM".
181     System(String),
182 }
183
184 #[derive(Debug, Clone)]
185 pub struct ProcMacro {
186     pub name: SmolStr,
187     pub kind: ProcMacroKind,
188     pub expander: Arc<dyn ProcMacroExpander>,
189 }
190
191 #[derive(Debug, Clone)]
192 pub struct CrateData {
193     pub root_file_id: FileId,
194     pub edition: Edition,
195     /// A name used in the package's project declaration: for Cargo projects,
196     /// its `[package].name` can be different for other project types or even
197     /// absent (a dummy crate for the code snippet, for example).
198     ///
199     /// For purposes of analysis, crates are anonymous (only names in
200     /// `Dependency` matters), this name should only be used for UI.
201     pub display_name: Option<CrateDisplayName>,
202     pub cfg_options: CfgOptions,
203     pub potential_cfg_options: CfgOptions,
204     pub env: Env,
205     pub dependencies: Vec<Dependency>,
206     pub proc_macro: Vec<ProcMacro>,
207 }
208
209 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
210 pub enum Edition {
211     Edition2015,
212     Edition2018,
213     Edition2021,
214 }
215
216 impl Edition {
217     pub const CURRENT: Edition = Edition::Edition2018;
218 }
219
220 #[derive(Default, Debug, Clone, PartialEq, Eq)]
221 pub struct Env {
222     entries: FxHashMap<String, String>,
223 }
224
225 #[derive(Debug, Clone, PartialEq, Eq)]
226 pub struct Dependency {
227     pub crate_id: CrateId,
228     pub name: CrateName,
229     prelude: bool,
230 }
231
232 impl Dependency {
233     pub fn new(name: CrateName, crate_id: CrateId) -> Self {
234         Self { name, crate_id, prelude: true }
235     }
236
237     pub fn with_prelude(name: CrateName, crate_id: CrateId, prelude: bool) -> Self {
238         Self { name, crate_id, prelude }
239     }
240
241     /// Whether this dependency is to be added to the depending crate's extern prelude.
242     pub fn is_prelude(&self) -> bool {
243         self.prelude
244     }
245 }
246
247 impl CrateGraph {
248     pub fn add_crate_root(
249         &mut self,
250         file_id: FileId,
251         edition: Edition,
252         display_name: Option<CrateDisplayName>,
253         cfg_options: CfgOptions,
254         potential_cfg_options: CfgOptions,
255         env: Env,
256         proc_macro: Vec<ProcMacro>,
257     ) -> CrateId {
258         let data = CrateData {
259             root_file_id: file_id,
260             edition,
261             display_name,
262             cfg_options,
263             potential_cfg_options,
264             env,
265             proc_macro,
266             dependencies: Vec::new(),
267         };
268         let crate_id = CrateId(self.arena.len() as u32);
269         let prev = self.arena.insert(crate_id, data);
270         assert!(prev.is_none());
271         crate_id
272     }
273
274     pub fn add_dep(
275         &mut self,
276         from: CrateId,
277         dep: Dependency,
278     ) -> Result<(), CyclicDependenciesError> {
279         let _p = profile::span("add_dep");
280
281         // Check if adding a dep from `from` to `to` creates a cycle. To figure
282         // that out, look for a  path in the *opposite* direction, from `to` to
283         // `from`.
284         if let Some(path) = self.find_path(&mut FxHashSet::default(), dep.crate_id, from) {
285             let path = path.into_iter().map(|it| (it, self[it].display_name.clone())).collect();
286             let err = CyclicDependenciesError { path };
287             assert!(err.from().0 == from && err.to().0 == dep.crate_id);
288             return Err(err);
289         }
290
291         self.arena.get_mut(&from).unwrap().add_dep(dep);
292         Ok(())
293     }
294
295     pub fn is_empty(&self) -> bool {
296         self.arena.is_empty()
297     }
298
299     pub fn iter(&self) -> impl Iterator<Item = CrateId> + '_ {
300         self.arena.keys().copied()
301     }
302
303     /// Returns an iterator over all transitive dependencies of the given crate,
304     /// including the crate itself.
305     pub fn transitive_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> + '_ {
306         let mut worklist = vec![of];
307         let mut deps = FxHashSet::default();
308
309         while let Some(krate) = worklist.pop() {
310             if !deps.insert(krate) {
311                 continue;
312             }
313
314             worklist.extend(self[krate].dependencies.iter().map(|dep| dep.crate_id));
315         }
316
317         deps.into_iter()
318     }
319
320     /// Returns all transitive reverse dependencies of the given crate,
321     /// including the crate itself.
322     pub fn transitive_rev_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> + '_ {
323         let mut worklist = vec![of];
324         let mut rev_deps = FxHashSet::default();
325         rev_deps.insert(of);
326
327         let mut inverted_graph = FxHashMap::<_, Vec<_>>::default();
328         self.arena.iter().for_each(|(&krate, data)| {
329             data.dependencies
330                 .iter()
331                 .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate))
332         });
333
334         while let Some(krate) = worklist.pop() {
335             if let Some(krate_rev_deps) = inverted_graph.get(&krate) {
336                 krate_rev_deps
337                     .iter()
338                     .copied()
339                     .filter(|&rev_dep| rev_deps.insert(rev_dep))
340                     .for_each(|rev_dep| worklist.push(rev_dep));
341             }
342         }
343
344         rev_deps.into_iter()
345     }
346
347     /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
348     /// come before the crate itself).
349     pub fn crates_in_topological_order(&self) -> Vec<CrateId> {
350         let mut res = Vec::new();
351         let mut visited = FxHashSet::default();
352
353         for krate in self.arena.keys().copied() {
354             go(self, &mut visited, &mut res, krate);
355         }
356
357         return res;
358
359         fn go(
360             graph: &CrateGraph,
361             visited: &mut FxHashSet<CrateId>,
362             res: &mut Vec<CrateId>,
363             source: CrateId,
364         ) {
365             if !visited.insert(source) {
366                 return;
367             }
368             for dep in graph[source].dependencies.iter() {
369                 go(graph, visited, res, dep.crate_id)
370             }
371             res.push(source)
372         }
373     }
374
375     // FIXME: this only finds one crate with the given root; we could have multiple
376     pub fn crate_id_for_crate_root(&self, file_id: FileId) -> Option<CrateId> {
377         let (&crate_id, _) =
378             self.arena.iter().find(|(_crate_id, data)| data.root_file_id == file_id)?;
379         Some(crate_id)
380     }
381
382     /// Extends this crate graph by adding a complete disjoint second crate
383     /// graph.
384     ///
385     /// The ids of the crates in the `other` graph are shifted by the return
386     /// amount.
387     pub fn extend(&mut self, other: CrateGraph) -> u32 {
388         let start = self.arena.len() as u32;
389         self.arena.extend(other.arena.into_iter().map(|(id, mut data)| {
390             let new_id = id.shift(start);
391             for dep in &mut data.dependencies {
392                 dep.crate_id = dep.crate_id.shift(start);
393             }
394             (new_id, data)
395         }));
396         start
397     }
398
399     fn find_path(
400         &self,
401         visited: &mut FxHashSet<CrateId>,
402         from: CrateId,
403         to: CrateId,
404     ) -> Option<Vec<CrateId>> {
405         if !visited.insert(from) {
406             return None;
407         }
408
409         if from == to {
410             return Some(vec![to]);
411         }
412
413         for dep in &self[from].dependencies {
414             let crate_id = dep.crate_id;
415             if let Some(mut path) = self.find_path(visited, crate_id, to) {
416                 path.push(from);
417                 return Some(path);
418             }
419         }
420
421         None
422     }
423
424     // Work around for https://github.com/rust-analyzer/rust-analyzer/issues/6038.
425     // As hacky as it gets.
426     pub fn patch_cfg_if(&mut self) -> bool {
427         let cfg_if = self.hacky_find_crate("cfg_if");
428         let std = self.hacky_find_crate("std");
429         match (cfg_if, std) {
430             (Some(cfg_if), Some(std)) => {
431                 self.arena.get_mut(&cfg_if).unwrap().dependencies.clear();
432                 self.arena
433                     .get_mut(&std)
434                     .unwrap()
435                     .dependencies
436                     .push(Dependency::new(CrateName::new("cfg_if").unwrap(), cfg_if));
437                 true
438             }
439             _ => false,
440         }
441     }
442
443     fn hacky_find_crate(&self, display_name: &str) -> Option<CrateId> {
444         self.iter().find(|it| self[*it].display_name.as_deref() == Some(display_name))
445     }
446 }
447
448 impl ops::Index<CrateId> for CrateGraph {
449     type Output = CrateData;
450     fn index(&self, crate_id: CrateId) -> &CrateData {
451         &self.arena[&crate_id]
452     }
453 }
454
455 impl CrateId {
456     fn shift(self, amount: u32) -> CrateId {
457         CrateId(self.0 + amount)
458     }
459 }
460
461 impl CrateData {
462     fn add_dep(&mut self, dep: Dependency) {
463         self.dependencies.push(dep)
464     }
465 }
466
467 impl FromStr for Edition {
468     type Err = ParseEditionError;
469
470     fn from_str(s: &str) -> Result<Self, Self::Err> {
471         let res = match s {
472             "2015" => Edition::Edition2015,
473             "2018" => Edition::Edition2018,
474             "2021" => Edition::Edition2021,
475             _ => return Err(ParseEditionError { invalid_input: s.to_string() }),
476         };
477         Ok(res)
478     }
479 }
480
481 impl fmt::Display for Edition {
482     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
483         f.write_str(match self {
484             Edition::Edition2015 => "2015",
485             Edition::Edition2018 => "2018",
486             Edition::Edition2021 => "2021",
487         })
488     }
489 }
490
491 impl FromIterator<(String, String)> for Env {
492     fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
493         Env { entries: FromIterator::from_iter(iter) }
494     }
495 }
496
497 impl Env {
498     pub fn set(&mut self, env: &str, value: String) {
499         self.entries.insert(env.to_owned(), value);
500     }
501
502     pub fn get(&self, env: &str) -> Option<String> {
503         self.entries.get(env).cloned()
504     }
505
506     pub fn iter(&self) -> impl Iterator<Item = (&str, &str)> {
507         self.entries.iter().map(|(k, v)| (k.as_str(), v.as_str()))
508     }
509 }
510
511 #[derive(Debug)]
512 pub struct ParseEditionError {
513     invalid_input: String,
514 }
515
516 impl fmt::Display for ParseEditionError {
517     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
518         write!(f, "invalid edition: {:?}", self.invalid_input)
519     }
520 }
521
522 impl std::error::Error for ParseEditionError {}
523
524 #[derive(Debug)]
525 pub struct CyclicDependenciesError {
526     path: Vec<(CrateId, Option<CrateDisplayName>)>,
527 }
528
529 impl CyclicDependenciesError {
530     fn from(&self) -> &(CrateId, Option<CrateDisplayName>) {
531         self.path.first().unwrap()
532     }
533     fn to(&self) -> &(CrateId, Option<CrateDisplayName>) {
534         self.path.last().unwrap()
535     }
536 }
537
538 impl fmt::Display for CyclicDependenciesError {
539     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
540         let render = |(id, name): &(CrateId, Option<CrateDisplayName>)| match name {
541             Some(it) => format!("{}({:?})", it, id),
542             None => format!("{:?}", id),
543         };
544         let path = self.path.iter().rev().map(render).collect::<Vec<String>>().join(" -> ");
545         write!(
546             f,
547             "cyclic deps: {} -> {}, alternative path: {}",
548             render(self.from()),
549             render(self.to()),
550             path
551         )
552     }
553 }
554
555 #[cfg(test)]
556 mod tests {
557     use super::{CfgOptions, CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
558
559     #[test]
560     fn detect_cyclic_dependency_indirect() {
561         let mut graph = CrateGraph::default();
562         let crate1 = graph.add_crate_root(
563             FileId(1u32),
564             Edition2018,
565             None,
566             CfgOptions::default(),
567             CfgOptions::default(),
568             Env::default(),
569             Default::default(),
570         );
571         let crate2 = graph.add_crate_root(
572             FileId(2u32),
573             Edition2018,
574             None,
575             CfgOptions::default(),
576             CfgOptions::default(),
577             Env::default(),
578             Default::default(),
579         );
580         let crate3 = graph.add_crate_root(
581             FileId(3u32),
582             Edition2018,
583             None,
584             CfgOptions::default(),
585             CfgOptions::default(),
586             Env::default(),
587             Default::default(),
588         );
589         assert!(graph
590             .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
591             .is_ok());
592         assert!(graph
593             .add_dep(crate2, Dependency::new(CrateName::new("crate3").unwrap(), crate3))
594             .is_ok());
595         assert!(graph
596             .add_dep(crate3, Dependency::new(CrateName::new("crate1").unwrap(), crate1))
597             .is_err());
598     }
599
600     #[test]
601     fn detect_cyclic_dependency_direct() {
602         let mut graph = CrateGraph::default();
603         let crate1 = graph.add_crate_root(
604             FileId(1u32),
605             Edition2018,
606             None,
607             CfgOptions::default(),
608             CfgOptions::default(),
609             Env::default(),
610             Default::default(),
611         );
612         let crate2 = graph.add_crate_root(
613             FileId(2u32),
614             Edition2018,
615             None,
616             CfgOptions::default(),
617             CfgOptions::default(),
618             Env::default(),
619             Default::default(),
620         );
621         assert!(graph
622             .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
623             .is_ok());
624         assert!(graph
625             .add_dep(crate2, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
626             .is_err());
627     }
628
629     #[test]
630     fn it_works() {
631         let mut graph = CrateGraph::default();
632         let crate1 = graph.add_crate_root(
633             FileId(1u32),
634             Edition2018,
635             None,
636             CfgOptions::default(),
637             CfgOptions::default(),
638             Env::default(),
639             Default::default(),
640         );
641         let crate2 = graph.add_crate_root(
642             FileId(2u32),
643             Edition2018,
644             None,
645             CfgOptions::default(),
646             CfgOptions::default(),
647             Env::default(),
648             Default::default(),
649         );
650         let crate3 = graph.add_crate_root(
651             FileId(3u32),
652             Edition2018,
653             None,
654             CfgOptions::default(),
655             CfgOptions::default(),
656             Env::default(),
657             Default::default(),
658         );
659         assert!(graph
660             .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
661             .is_ok());
662         assert!(graph
663             .add_dep(crate2, Dependency::new(CrateName::new("crate3").unwrap(), crate3))
664             .is_ok());
665     }
666
667     #[test]
668     fn dashes_are_normalized() {
669         let mut graph = CrateGraph::default();
670         let crate1 = graph.add_crate_root(
671             FileId(1u32),
672             Edition2018,
673             None,
674             CfgOptions::default(),
675             CfgOptions::default(),
676             Env::default(),
677             Default::default(),
678         );
679         let crate2 = graph.add_crate_root(
680             FileId(2u32),
681             Edition2018,
682             None,
683             CfgOptions::default(),
684             CfgOptions::default(),
685             Env::default(),
686             Default::default(),
687         );
688         assert!(graph
689             .add_dep(
690                 crate1,
691                 Dependency::new(CrateName::normalize_dashes("crate-name-with-dashes"), crate2)
692             )
693             .is_ok());
694         assert_eq!(
695             graph[crate1].dependencies,
696             vec![Dependency::new(CrateName::new("crate_name_with_dashes").unwrap(), crate2)]
697         );
698     }
699 }