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