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