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