aboutsummaryrefslogtreecommitdiff
path: root/crates/base_db/src/input.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/base_db/src/input.rs')
-rw-r--r--crates/base_db/src/input.rs453
1 files changed, 453 insertions, 0 deletions
diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs
new file mode 100644
index 000000000..f3d65cdf0
--- /dev/null
+++ b/crates/base_db/src/input.rs
@@ -0,0 +1,453 @@
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::{fmt, iter::FromIterator, ops, str::FromStr, sync::Arc};
10
11use cfg::CfgOptions;
12use rustc_hash::{FxHashMap, FxHashSet};
13use syntax::SmolStr;
14use tt::TokenExpander;
15use vfs::file_set::FileSet;
16
17pub use vfs::FileId;
18
19/// Files are grouped into source roots. A source root is a directory on the
20/// file systems which is watched for changes. Typically it corresponds to a
21/// Rust crate. Source roots *might* be nested: in this case, a file belongs to
22/// the nearest enclosing source root. Paths to files are always relative to a
23/// source root, and the analyzer does not know the root path of the source root at
24/// all. So, a file from one source root can't refer to a file in another source
25/// root by path.
26#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
27pub struct SourceRootId(pub u32);
28
29#[derive(Clone, Debug, PartialEq, Eq)]
30pub struct SourceRoot {
31 /// Sysroot or crates.io library.
32 ///
33 /// Libraries are considered mostly immutable, this assumption is used to
34 /// optimize salsa's query structure
35 pub is_library: bool,
36 pub(crate) file_set: FileSet,
37}
38
39impl SourceRoot {
40 pub fn new_local(file_set: FileSet) -> SourceRoot {
41 SourceRoot { is_library: false, file_set }
42 }
43 pub fn new_library(file_set: FileSet) -> SourceRoot {
44 SourceRoot { is_library: true, file_set }
45 }
46 pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
47 self.file_set.iter()
48 }
49}
50
51/// `CrateGraph` is a bit of information which turns a set of text files into a
52/// number of Rust crates. Each crate is defined by the `FileId` of its root module,
53/// the set of cfg flags (not yet implemented) and the set of dependencies. Note
54/// that, due to cfg's, there might be several crates for a single `FileId`! As
55/// in the rust-lang proper, a crate does not have a name. Instead, names are
56/// specified on dependency edges. That is, a crate might be known under
57/// different names in different dependent crates.
58///
59/// Note that `CrateGraph` is build-system agnostic: it's a concept of the Rust
60/// language proper, not a concept of the build system. In practice, we get
61/// `CrateGraph` by lowering `cargo metadata` output.
62#[derive(Debug, Clone, Default, PartialEq, Eq)]
63pub struct CrateGraph {
64 arena: FxHashMap<CrateId, CrateData>,
65}
66
67#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
68pub struct CrateId(pub u32);
69
70#[derive(Debug, Clone, PartialEq, Eq, Hash)]
71pub struct CrateName(SmolStr);
72
73impl CrateName {
74 /// Creates a crate name, checking for dashes in the string provided.
75 /// Dashes are not allowed in the crate names,
76 /// hence the input string is returned as `Err` for those cases.
77 pub fn new(name: &str) -> Result<CrateName, &str> {
78 if name.contains('-') {
79 Err(name)
80 } else {
81 Ok(Self(SmolStr::new(name)))
82 }
83 }
84
85 /// Creates a crate name, unconditionally replacing the dashes with underscores.
86 pub fn normalize_dashes(name: &str) -> CrateName {
87 Self(SmolStr::new(name.replace('-', "_")))
88 }
89}
90
91impl fmt::Display for CrateName {
92 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
93 write!(f, "{}", self.0)
94 }
95}
96
97impl ops::Deref for CrateName {
98 type Target = str;
99 fn deref(&self) -> &Self::Target {
100 &*self.0
101 }
102}
103
104#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
105pub struct ProcMacroId(pub u32);
106
107#[derive(Debug, Clone)]
108pub struct ProcMacro {
109 pub name: SmolStr,
110 pub expander: Arc<dyn TokenExpander>,
111}
112
113impl Eq for ProcMacro {}
114impl PartialEq for ProcMacro {
115 fn eq(&self, other: &ProcMacro) -> bool {
116 self.name == other.name && Arc::ptr_eq(&self.expander, &other.expander)
117 }
118}
119
120#[derive(Debug, Clone, PartialEq, Eq)]
121pub struct CrateData {
122 pub root_file_id: FileId,
123 pub edition: Edition,
124 /// The name to display to the end user.
125 /// This actual crate name can be different in a particular dependent crate
126 /// or may even be missing for some cases, such as a dummy crate for the code snippet.
127 pub display_name: Option<String>,
128 pub cfg_options: CfgOptions,
129 pub env: Env,
130 pub dependencies: Vec<Dependency>,
131 pub proc_macro: Vec<ProcMacro>,
132}
133
134#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
135pub enum Edition {
136 Edition2018,
137 Edition2015,
138}
139
140#[derive(Default, Debug, Clone, PartialEq, Eq)]
141pub struct Env {
142 entries: FxHashMap<String, String>,
143}
144
145#[derive(Debug, Clone, PartialEq, Eq)]
146pub struct Dependency {
147 pub crate_id: CrateId,
148 pub name: CrateName,
149}
150
151impl CrateGraph {
152 pub fn add_crate_root(
153 &mut self,
154 file_id: FileId,
155 edition: Edition,
156 display_name: Option<String>,
157 cfg_options: CfgOptions,
158 env: Env,
159 proc_macro: Vec<(SmolStr, Arc<dyn tt::TokenExpander>)>,
160 ) -> CrateId {
161 let proc_macro =
162 proc_macro.into_iter().map(|(name, it)| ProcMacro { name, expander: it }).collect();
163
164 let data = CrateData {
165 root_file_id: file_id,
166 edition,
167 display_name,
168 cfg_options,
169 env,
170 proc_macro,
171 dependencies: Vec::new(),
172 };
173 let crate_id = CrateId(self.arena.len() as u32);
174 let prev = self.arena.insert(crate_id, data);
175 assert!(prev.is_none());
176 crate_id
177 }
178
179 pub fn add_dep(
180 &mut self,
181 from: CrateId,
182 name: CrateName,
183 to: CrateId,
184 ) -> Result<(), CyclicDependenciesError> {
185 if self.dfs_find(from, to, &mut FxHashSet::default()) {
186 return Err(CyclicDependenciesError);
187 }
188 self.arena.get_mut(&from).unwrap().add_dep(name, to);
189 Ok(())
190 }
191
192 pub fn is_empty(&self) -> bool {
193 self.arena.is_empty()
194 }
195
196 pub fn iter(&self) -> impl Iterator<Item = CrateId> + '_ {
197 self.arena.keys().copied()
198 }
199
200 /// Returns an iterator over all transitive dependencies of the given crate.
201 pub fn transitive_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> + '_ {
202 let mut worklist = vec![of];
203 let mut deps = FxHashSet::default();
204
205 while let Some(krate) = worklist.pop() {
206 if !deps.insert(krate) {
207 continue;
208 }
209
210 worklist.extend(self[krate].dependencies.iter().map(|dep| dep.crate_id));
211 }
212
213 deps.remove(&of);
214 deps.into_iter()
215 }
216
217 // FIXME: this only finds one crate with the given root; we could have multiple
218 pub fn crate_id_for_crate_root(&self, file_id: FileId) -> Option<CrateId> {
219 let (&crate_id, _) =
220 self.arena.iter().find(|(_crate_id, data)| data.root_file_id == file_id)?;
221 Some(crate_id)
222 }
223
224 /// Extends this crate graph by adding a complete disjoint second crate
225 /// graph.
226 ///
227 /// The ids of the crates in the `other` graph are shifted by the return
228 /// amount.
229 pub fn extend(&mut self, other: CrateGraph) -> u32 {
230 let start = self.arena.len() as u32;
231 self.arena.extend(other.arena.into_iter().map(|(id, mut data)| {
232 let new_id = id.shift(start);
233 for dep in &mut data.dependencies {
234 dep.crate_id = dep.crate_id.shift(start);
235 }
236 (new_id, data)
237 }));
238 start
239 }
240
241 fn dfs_find(&self, target: CrateId, from: CrateId, visited: &mut FxHashSet<CrateId>) -> bool {
242 if !visited.insert(from) {
243 return false;
244 }
245
246 if target == from {
247 return true;
248 }
249
250 for dep in &self[from].dependencies {
251 let crate_id = dep.crate_id;
252 if self.dfs_find(target, crate_id, visited) {
253 return true;
254 }
255 }
256 false
257 }
258}
259
260impl ops::Index<CrateId> for CrateGraph {
261 type Output = CrateData;
262 fn index(&self, crate_id: CrateId) -> &CrateData {
263 &self.arena[&crate_id]
264 }
265}
266
267impl CrateId {
268 pub fn shift(self, amount: u32) -> CrateId {
269 CrateId(self.0 + amount)
270 }
271}
272
273impl CrateData {
274 fn add_dep(&mut self, name: CrateName, crate_id: CrateId) {
275 self.dependencies.push(Dependency { name, crate_id })
276 }
277}
278
279impl FromStr for Edition {
280 type Err = ParseEditionError;
281
282 fn from_str(s: &str) -> Result<Self, Self::Err> {
283 let res = match s {
284 "2015" => Edition::Edition2015,
285 "2018" => Edition::Edition2018,
286 _ => return Err(ParseEditionError { invalid_input: s.to_string() }),
287 };
288 Ok(res)
289 }
290}
291
292impl fmt::Display for Edition {
293 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
294 f.write_str(match self {
295 Edition::Edition2015 => "2015",
296 Edition::Edition2018 => "2018",
297 })
298 }
299}
300
301impl FromIterator<(String, String)> for Env {
302 fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
303 Env { entries: FromIterator::from_iter(iter) }
304 }
305}
306
307impl Env {
308 pub fn set(&mut self, env: &str, value: String) {
309 self.entries.insert(env.to_owned(), value);
310 }
311
312 pub fn get(&self, env: &str) -> Option<String> {
313 self.entries.get(env).cloned()
314 }
315}
316
317#[derive(Debug)]
318pub struct ParseEditionError {
319 invalid_input: String,
320}
321
322impl fmt::Display for ParseEditionError {
323 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
324 write!(f, "invalid edition: {:?}", self.invalid_input)
325 }
326}
327
328impl std::error::Error for ParseEditionError {}
329
330#[derive(Debug)]
331pub struct CyclicDependenciesError;
332
333#[cfg(test)]
334mod tests {
335 use super::{CfgOptions, CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
336
337 #[test]
338 fn detect_cyclic_dependency_indirect() {
339 let mut graph = CrateGraph::default();
340 let crate1 = graph.add_crate_root(
341 FileId(1u32),
342 Edition2018,
343 None,
344 CfgOptions::default(),
345 Env::default(),
346 Default::default(),
347 );
348 let crate2 = graph.add_crate_root(
349 FileId(2u32),
350 Edition2018,
351 None,
352 CfgOptions::default(),
353 Env::default(),
354 Default::default(),
355 );
356 let crate3 = graph.add_crate_root(
357 FileId(3u32),
358 Edition2018,
359 None,
360 CfgOptions::default(),
361 Env::default(),
362 Default::default(),
363 );
364 assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
365 assert!(graph.add_dep(crate2, CrateName::new("crate3").unwrap(), crate3).is_ok());
366 assert!(graph.add_dep(crate3, CrateName::new("crate1").unwrap(), crate1).is_err());
367 }
368
369 #[test]
370 fn detect_cyclic_dependency_direct() {
371 let mut graph = CrateGraph::default();
372 let crate1 = graph.add_crate_root(
373 FileId(1u32),
374 Edition2018,
375 None,
376 CfgOptions::default(),
377 Env::default(),
378 Default::default(),
379 );
380 let crate2 = graph.add_crate_root(
381 FileId(2u32),
382 Edition2018,
383 None,
384 CfgOptions::default(),
385 Env::default(),
386 Default::default(),
387 );
388 assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
389 assert!(graph.add_dep(crate2, CrateName::new("crate2").unwrap(), crate2).is_err());
390 }
391
392 #[test]
393 fn it_works() {
394 let mut graph = CrateGraph::default();
395 let crate1 = graph.add_crate_root(
396 FileId(1u32),
397 Edition2018,
398 None,
399 CfgOptions::default(),
400 Env::default(),
401 Default::default(),
402 );
403 let crate2 = graph.add_crate_root(
404 FileId(2u32),
405 Edition2018,
406 None,
407 CfgOptions::default(),
408 Env::default(),
409 Default::default(),
410 );
411 let crate3 = graph.add_crate_root(
412 FileId(3u32),
413 Edition2018,
414 None,
415 CfgOptions::default(),
416 Env::default(),
417 Default::default(),
418 );
419 assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
420 assert!(graph.add_dep(crate2, CrateName::new("crate3").unwrap(), crate3).is_ok());
421 }
422
423 #[test]
424 fn dashes_are_normalized() {
425 let mut graph = CrateGraph::default();
426 let crate1 = graph.add_crate_root(
427 FileId(1u32),
428 Edition2018,
429 None,
430 CfgOptions::default(),
431 Env::default(),
432 Default::default(),
433 );
434 let crate2 = graph.add_crate_root(
435 FileId(2u32),
436 Edition2018,
437 None,
438 CfgOptions::default(),
439 Env::default(),
440 Default::default(),
441 );
442 assert!(graph
443 .add_dep(crate1, CrateName::normalize_dashes("crate-name-with-dashes"), crate2)
444 .is_ok());
445 assert_eq!(
446 graph[crate1].dependencies,
447 vec![Dependency {
448 crate_id: crate2,
449 name: CrateName::new("crate_name_with_dashes").unwrap()
450 }]
451 );
452 }
453}