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, str::FromStr, sync::Arc};
  10
  11 use cfg::CfgOptions;
  12 use rustc_hash::{FxHashMap, FxHashSet};
  13 use syntax::SmolStr;
  14 use tt::TokenExpander;
  15 use vfs::file_set::FileSet;
  16
  17 pub 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)]
  27 pub struct SourceRootId(pub u32);
  28
  29 #[derive(Clone, Debug, PartialEq, Eq)]
  30 pub 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
  39 impl 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)]
  63 pub struct CrateGraph {
  64     arena: FxHashMap<CrateId, CrateData>,
  65 }
  66
  67 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
  68 pub struct CrateId(pub u32);
  69
  70 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
  71 pub struct CrateName(SmolStr);
  72
  73 impl 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
  91 impl fmt::Display for CrateName {
  92     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  93         write!(f, "{}", self.0)
  94     }
  95 }
  96
  97 impl 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)]
 105 pub struct ProcMacroId(pub u32);
 106
 107 #[derive(Debug, Clone)]
 108 pub struct ProcMacro {
 109     pub name: SmolStr,
 110     pub expander: Arc<dyn TokenExpander>,
 111 }
 112
 113 impl Eq for ProcMacro {}
 114 impl 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)]
 121 pub 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)]
 135 pub enum Edition {
 136     Edition2018,
 137     Edition2015,
 138 }
 139
 140 #[derive(Default, Debug, Clone, PartialEq, Eq)]
 141 pub struct Env {
 142     entries: FxHashMap<String, String>,
 143 }
 144
 145 #[derive(Debug, Clone, PartialEq, Eq)]
 146 pub struct Dependency {
 147     pub crate_id: CrateId,
 148     pub name: CrateName,
 149 }
 150
 151 impl 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
 260 impl 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
 267 impl CrateId {
 268     pub fn shift(self, amount: u32) -> CrateId {
 269         CrateId(self.0 + amount)
 270     }
 271 }
 272
 273 impl CrateData {
 274     fn add_dep(&mut self, name: CrateName, crate_id: CrateId) {
 275         self.dependencies.push(Dependency { name, crate_id })
 276     }
 277 }
 278
 279 impl 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
 292 impl 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
 301 impl 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
 307 impl 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)]
 318 pub struct ParseEditionError {
 319     invalid_input: String,
 320 }
 321
 322 impl 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
 328 impl std::error::Error for ParseEditionError {}
 329
 330 #[derive(Debug)]
 331 pub struct CyclicDependenciesError;
 332
 333 #[cfg(test)]
 334 mod 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 }