//! This module specifies the input to rust-analyzer. In some sense, this is
//! **the** most important module, because all other fancy stuff is strictly
//! derived from this input.
//!
//! Note that neither this module, nor any other part of the analyzer's core do
//! actual IO. See `vfs` and `project_model` in the `rust-analyzer` crate for how
//! actual IO is done and lowered to input.

use std::error::Error;
use std::hash::BuildHasherDefault;
use std::{fmt, mem, ops};

use cfg::{CfgOptions, HashableCfgOptions};
use dashmap::DashMap;
use dashmap::mapref::entry::Entry;
use intern::Symbol;
use la_arena::{Arena, Idx, RawIdx};
use rustc_hash::{FxBuildHasher, FxHashMap, FxHashSet, FxHasher};
use salsa::{Durability, Setter};
use span::Edition;
use triomphe::Arc;
use vfs::{AbsPathBuf, AnchoredPath, FileId, VfsPath, file_set::FileSet};

use crate::{CrateWorkspaceData, EditionedFileId, FxIndexSet, RootQueryDb};

pub type ProcMacroPaths =
    FxHashMap<CrateBuilderId, Result<(String, AbsPathBuf), ProcMacroLoadingError>>;

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum ProcMacroLoadingError {
    Disabled,
    FailedToBuild,
    ExpectedProcMacroArtifact,
    MissingDylibPath,
    NotYetBuilt,
    NoProcMacros,
    ProcMacroSrvError(Box<str>),
}
impl ProcMacroLoadingError {
    pub fn is_hard_error(&self) -> bool {
        match self {
            ProcMacroLoadingError::Disabled | ProcMacroLoadingError::NotYetBuilt => false,
            ProcMacroLoadingError::ExpectedProcMacroArtifact
            | ProcMacroLoadingError::FailedToBuild
            | ProcMacroLoadingError::MissingDylibPath
            | ProcMacroLoadingError::NoProcMacros
            | ProcMacroLoadingError::ProcMacroSrvError(_) => true,
        }
    }
}

impl Error for ProcMacroLoadingError {}
impl fmt::Display for ProcMacroLoadingError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            ProcMacroLoadingError::ExpectedProcMacroArtifact => {
                write!(f, "proc-macro crate did not build proc-macro artifact")
            }
            ProcMacroLoadingError::Disabled => write!(f, "proc-macro expansion is disabled"),
            ProcMacroLoadingError::FailedToBuild => write!(f, "proc-macro failed to build"),
            ProcMacroLoadingError::MissingDylibPath => {
                write!(
                    f,
                    "proc-macro crate built but the dylib path is missing, this indicates a problem with your build system."
                )
            }
            ProcMacroLoadingError::NotYetBuilt => write!(f, "proc-macro not yet built"),
            ProcMacroLoadingError::NoProcMacros => {
                write!(f, "proc macro library has no proc macros")
            }
            ProcMacroLoadingError::ProcMacroSrvError(msg) => {
                write!(f, "proc macro server error: {msg}")
            }
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct SourceRootId(pub u32);

/// Files are grouped into source roots. A source root is a directory on the
/// file systems which is watched for changes. Typically it corresponds to a
/// Rust crate. Source roots *might* be nested: in this case, a file belongs to
/// the nearest enclosing source root. Paths to files are always relative to a
/// source root, and the analyzer does not know the root path of the source root at
/// all. So, a file from one source root can't refer to a file in another source
/// root by path.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SourceRoot {
    /// Sysroot or crates.io library.
    ///
    /// Libraries are considered mostly immutable, this assumption is used to
    /// optimize salsa's query structure
    pub is_library: bool,
    file_set: FileSet,
}

impl SourceRoot {
    pub fn new_local(file_set: FileSet) -> SourceRoot {
        SourceRoot { is_library: false, file_set }
    }

    pub fn new_library(file_set: FileSet) -> SourceRoot {
        SourceRoot { is_library: true, file_set }
    }

    pub fn path_for_file(&self, file: &FileId) -> Option<&VfsPath> {
        self.file_set.path_for_file(file)
    }

    pub fn file_for_path(&self, path: &VfsPath) -> Option<&FileId> {
        self.file_set.file_for_path(path)
    }

    pub fn resolve_path(&self, path: AnchoredPath<'_>) -> Option<FileId> {
        self.file_set.resolve_path(path)
    }

    pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
        self.file_set.iter()
    }
}

#[derive(Default, Clone)]
pub struct CrateGraphBuilder {
    arena: Arena<CrateBuilder>,
}

pub type CrateBuilderId = Idx<CrateBuilder>;

impl ops::Index<CrateBuilderId> for CrateGraphBuilder {
    type Output = CrateBuilder;

    fn index(&self, index: CrateBuilderId) -> &Self::Output {
        &self.arena[index]
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CrateBuilder {
    pub basic: CrateDataBuilder,
    pub extra: ExtraCrateData,
    pub cfg_options: CfgOptions,
    pub env: Env,
    ws_data: Arc<CrateWorkspaceData>,
}

impl fmt::Debug for CrateGraphBuilder {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_map()
            .entries(self.arena.iter().map(|(id, data)| (u32::from(id.into_raw()), data)))
            .finish()
    }
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct CrateName(Symbol);

impl CrateName {
    /// Creates a crate name, checking for dashes in the string provided.
    /// Dashes are not allowed in the crate names,
    /// hence the input string is returned as `Err` for those cases.
    pub fn new(name: &str) -> Result<CrateName, &str> {
        if name.contains('-') { Err(name) } else { Ok(Self(Symbol::intern(name))) }
    }

    /// Creates a crate name, unconditionally replacing the dashes with underscores.
    pub fn normalize_dashes(name: &str) -> CrateName {
        Self(Symbol::intern(&name.replace('-', "_")))
    }

    pub fn symbol(&self) -> &Symbol {
        &self.0
    }
}

impl fmt::Display for CrateName {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.0.fmt(f)
    }
}

impl ops::Deref for CrateName {
    type Target = Symbol;
    fn deref(&self) -> &Symbol {
        &self.0
    }
}

/// Origin of the crates.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum CrateOrigin {
    /// Crates that are from the rustc workspace.
    Rustc { name: Symbol },
    /// Crates that are workspace members.
    Local { repo: Option<String>, name: Option<Symbol> },
    /// Crates that are non member libraries.
    Library { repo: Option<String>, name: Symbol },
    /// Crates that are provided by the language, like std, core, proc-macro, ...
    Lang(LangCrateOrigin),
}

impl CrateOrigin {
    pub fn is_local(&self) -> bool {
        matches!(self, CrateOrigin::Local { .. })
    }

    pub fn is_lib(&self) -> bool {
        matches!(self, CrateOrigin::Library { .. })
    }

    pub fn is_lang(&self) -> bool {
        matches!(self, CrateOrigin::Lang { .. })
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum LangCrateOrigin {
    Alloc,
    Core,
    ProcMacro,
    Std,
    Test,
    Other,
}

impl From<&str> for LangCrateOrigin {
    fn from(s: &str) -> Self {
        match s {
            "alloc" => LangCrateOrigin::Alloc,
            "core" => LangCrateOrigin::Core,
            "proc-macro" | "proc_macro" => LangCrateOrigin::ProcMacro,
            "std" => LangCrateOrigin::Std,
            "test" => LangCrateOrigin::Test,
            _ => LangCrateOrigin::Other,
        }
    }
}

impl fmt::Display for LangCrateOrigin {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let text = match self {
            LangCrateOrigin::Alloc => "alloc",
            LangCrateOrigin::Core => "core",
            LangCrateOrigin::ProcMacro => "proc_macro",
            LangCrateOrigin::Std => "std",
            LangCrateOrigin::Test => "test",
            LangCrateOrigin::Other => "other",
        };
        f.write_str(text)
    }
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct CrateDisplayName {
    // The name we use to display various paths (with `_`).
    crate_name: CrateName,
    // The name as specified in Cargo.toml (with `-`).
    canonical_name: Symbol,
}

impl CrateDisplayName {
    pub fn canonical_name(&self) -> &Symbol {
        &self.canonical_name
    }
    pub fn crate_name(&self) -> &CrateName {
        &self.crate_name
    }
}

impl From<CrateName> for CrateDisplayName {
    fn from(crate_name: CrateName) -> CrateDisplayName {
        let canonical_name = crate_name.0.clone();
        CrateDisplayName { crate_name, canonical_name }
    }
}

impl fmt::Display for CrateDisplayName {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.crate_name.fmt(f)
    }
}

impl ops::Deref for CrateDisplayName {
    type Target = Symbol;
    fn deref(&self) -> &Symbol {
        &self.crate_name
    }
}

impl CrateDisplayName {
    pub fn from_canonical_name(canonical_name: &str) -> CrateDisplayName {
        let crate_name = CrateName::normalize_dashes(canonical_name);
        CrateDisplayName { crate_name, canonical_name: Symbol::intern(canonical_name) }
    }
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum ReleaseChannel {
    Stable,
    Beta,
    Nightly,
}

impl ReleaseChannel {
    pub fn as_str(self) -> &'static str {
        match self {
            ReleaseChannel::Stable => "stable",
            ReleaseChannel::Beta => "beta",
            ReleaseChannel::Nightly => "nightly",
        }
    }

    #[allow(clippy::should_implement_trait)]
    pub fn from_str(str: &str) -> Option<Self> {
        Some(match str {
            "" | "stable" => ReleaseChannel::Stable,
            "nightly" => ReleaseChannel::Nightly,
            _ if str.starts_with("beta") => ReleaseChannel::Beta,
            _ => return None,
        })
    }
}

/// The crate data from which we derive the `Crate`.
///
/// We want this to contain as little data as possible, because if it contains dependencies and
/// something changes, this crate and all of its dependencies ids are invalidated, which causes
/// pretty much everything to be recomputed. If the crate id is not invalidated, only this crate's
/// information needs to be recomputed.
///
/// *Most* different crates have different root files (actually, pretty much all of them).
/// Still, it is possible to have crates distinguished by other factors (e.g. dependencies).
/// So we store only the root file - unless we find that this crate has the same root file as
/// another crate, in which case we store all data for one of them (if one is a dependency of
/// the other, we store for it, because it has more dependencies to be invalidated).
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct UniqueCrateData {
    root_file_id: FileId,
    disambiguator: Option<Box<(BuiltCrateData, HashableCfgOptions)>>,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct CrateData<Id> {
    pub root_file_id: FileId,
    pub edition: Edition,
    /// The dependencies of this crate.
    ///
    /// Note that this may contain more dependencies than the crate actually uses.
    /// A common example is the test crate which is included but only actually is active when
    /// declared in source via `extern crate test`.
    pub dependencies: Vec<Dependency<Id>>,
    pub origin: CrateOrigin,
    pub is_proc_macro: bool,
    /// The working directory to run proc-macros in invoked in the context of this crate.
    /// This is the workspace root of the cargo workspace for workspace members, the crate manifest
    /// dir otherwise.
    // FIXME: This ought to be a `VfsPath` or something opaque.
    pub proc_macro_cwd: Arc<AbsPathBuf>,
}

pub type CrateDataBuilder = CrateData<CrateBuilderId>;
pub type BuiltCrateData = CrateData<Crate>;

/// Crate data unrelated to analysis.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ExtraCrateData {
    pub version: Option<String>,
    /// A name used in the package's project declaration: for Cargo projects,
    /// its `[package].name` can be different for other project types or even
    /// absent (a dummy crate for the code snippet, for example).
    ///
    /// For purposes of analysis, crates are anonymous (only names in
    /// `Dependency` matters), this name should only be used for UI.
    pub display_name: Option<CrateDisplayName>,
    /// The cfg options that could be used by the crate
    pub potential_cfg_options: Option<CfgOptions>,
}

#[derive(Default, Clone, PartialEq, Eq)]
pub struct Env {
    entries: FxHashMap<String, String>,
}

impl fmt::Debug for Env {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        struct EnvDebug<'s>(Vec<(&'s String, &'s String)>);

        impl fmt::Debug for EnvDebug<'_> {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                f.debug_map().entries(self.0.iter().copied()).finish()
            }
        }
        f.debug_struct("Env")
            .field("entries", &{
                let mut entries: Vec<_> = self.entries.iter().collect();
                entries.sort();
                EnvDebug(entries)
            })
            .finish()
    }
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Dependency<Id> {
    pub crate_id: Id,
    pub name: CrateName,
    prelude: bool,
    sysroot: bool,
}

pub type DependencyBuilder = Dependency<CrateBuilderId>;
pub type BuiltDependency = Dependency<Crate>;

impl DependencyBuilder {
    pub fn new(name: CrateName, crate_id: CrateBuilderId) -> Self {
        Self { name, crate_id, prelude: true, sysroot: false }
    }

    pub fn with_prelude(
        name: CrateName,
        crate_id: CrateBuilderId,
        prelude: bool,
        sysroot: bool,
    ) -> Self {
        Self { name, crate_id, prelude, sysroot }
    }
}

impl BuiltDependency {
    /// Whether this dependency is to be added to the depending crate's extern prelude.
    pub fn is_prelude(&self) -> bool {
        self.prelude
    }

    /// Whether this dependency is a sysroot injected one.
    pub fn is_sysroot(&self) -> bool {
        self.sysroot
    }
}

pub type CratesIdMap = FxHashMap<CrateBuilderId, Crate>;

#[salsa_macros::input]
#[derive(Debug, PartialOrd, Ord)]
pub struct Crate {
    #[returns(ref)]
    pub data: BuiltCrateData,
    /// Crate data that is not needed for analysis.
    ///
    /// This is split into a separate field to increase incrementality.
    #[returns(ref)]
    pub extra_data: ExtraCrateData,
    // This is in `Arc` because it is shared for all crates in a workspace.
    #[returns(ref)]
    pub workspace_data: Arc<CrateWorkspaceData>,
    #[returns(ref)]
    pub cfg_options: CfgOptions,
    #[returns(ref)]
    pub env: Env,
}

impl Crate {
    /// Returns an iterator over all transitive dependencies of the given crate,
    /// including the crate itself.
    ///
    /// **Warning**: do not use this query in `hir-*` crates! It kills incrementality across crate metadata modifications.
    pub fn transitive_deps(self, db: &dyn salsa::Database) -> Box<[Crate]> {
        // There is a bit of duplication here and in `CrateGraphBuilder` in the same method, but it's not terrible
        // and removing that is a bit difficult.
        let mut worklist = vec![self];
        let mut deps_seen = FxHashSet::default();
        let mut deps = Vec::new();

        while let Some(krate) = worklist.pop() {
            if !deps_seen.insert(krate) {
                continue;
            }
            deps.push(krate);

            worklist.extend(krate.data(db).dependencies.iter().map(|dep| dep.crate_id));
        }
        deps.into_boxed_slice()
    }

    /// Returns all transitive reverse dependencies of the given crate,
    /// including the crate itself.
    ///
    /// **Warning**: do not use this query in `hir-*` crates! It kills incrementality across crate metadata modifications.
    pub fn transitive_rev_deps(self, db: &dyn RootQueryDb) -> Box<[Crate]> {
        let mut worklist = vec![self];
        let mut rev_deps = FxHashSet::default();
        rev_deps.insert(self);

        let mut inverted_graph = FxHashMap::<_, Vec<_>>::default();
        db.all_crates().iter().for_each(|&krate| {
            krate
                .data(db)
                .dependencies
                .iter()
                .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate))
        });

        while let Some(krate) = worklist.pop() {
            if let Some(crate_rev_deps) = inverted_graph.get(&krate) {
                crate_rev_deps
                    .iter()
                    .copied()
                    .filter(|&rev_dep| rev_deps.insert(rev_dep))
                    .for_each(|rev_dep| worklist.push(rev_dep));
            }
        }

        rev_deps.into_iter().collect::<Box<_>>()
    }
}

/// The mapping from [`UniqueCrateData`] to their [`Crate`] input.
#[derive(Debug, Default)]
pub struct CratesMap(DashMap<UniqueCrateData, Crate, BuildHasherDefault<FxHasher>>);

impl CrateGraphBuilder {
    pub fn add_crate_root(
        &mut self,
        root_file_id: FileId,
        edition: Edition,
        display_name: Option<CrateDisplayName>,
        version: Option<String>,
        mut cfg_options: CfgOptions,
        mut potential_cfg_options: Option<CfgOptions>,
        mut env: Env,
        origin: CrateOrigin,
        is_proc_macro: bool,
        proc_macro_cwd: Arc<AbsPathBuf>,
        ws_data: Arc<CrateWorkspaceData>,
    ) -> CrateBuilderId {
        env.entries.shrink_to_fit();
        cfg_options.shrink_to_fit();
        if let Some(potential_cfg_options) = &mut potential_cfg_options {
            potential_cfg_options.shrink_to_fit();
        }
        self.arena.alloc(CrateBuilder {
            basic: CrateData {
                root_file_id,
                edition,
                dependencies: Vec::new(),
                origin,
                is_proc_macro,
                proc_macro_cwd,
            },
            extra: ExtraCrateData { version, display_name, potential_cfg_options },
            cfg_options,
            env,
            ws_data,
        })
    }

    pub fn add_dep(
        &mut self,
        from: CrateBuilderId,
        dep: DependencyBuilder,
    ) -> Result<(), CyclicDependenciesError> {
        let _p = tracing::info_span!("add_dep").entered();

        // Check if adding a dep from `from` to `to` creates a cycle. To figure
        // that out, look for a  path in the *opposite* direction, from `to` to
        // `from`.
        if let Some(path) = self.find_path(&mut FxHashSet::default(), dep.crate_id, from) {
            let path =
                path.into_iter().map(|it| (it, self[it].extra.display_name.clone())).collect();
            let err = CyclicDependenciesError { path };
            assert!(err.from().0 == from && err.to().0 == dep.crate_id);
            return Err(err);
        }

        self.arena[from].basic.dependencies.push(dep);
        Ok(())
    }

    pub fn set_in_db(self, db: &mut dyn RootQueryDb) -> CratesIdMap {
        // For some reason in some repositories we have duplicate crates, so we use a set and not `Vec`.
        // We use an `IndexSet` because the list needs to be topologically sorted.
        let mut all_crates = FxIndexSet::with_capacity_and_hasher(self.arena.len(), FxBuildHasher);
        let mut visited = FxHashMap::default();
        let mut visited_root_files = FxHashSet::default();

        let old_all_crates = db.all_crates();

        let crates_map = db.crates_map();
        // salsa doesn't compare new input to old input to see if they are the same, so here we are doing all the work ourselves.
        for krate in self.iter() {
            go(
                &self,
                db,
                &crates_map,
                &mut visited,
                &mut visited_root_files,
                &mut all_crates,
                krate,
            );
        }

        if old_all_crates.len() != all_crates.len()
            || old_all_crates.iter().any(|&krate| !all_crates.contains(&krate))
        {
            db.set_all_crates_with_durability(
                Arc::new(Vec::from_iter(all_crates).into_boxed_slice()),
                Durability::MEDIUM,
            );
        }

        return visited;

        fn go(
            graph: &CrateGraphBuilder,
            db: &mut dyn RootQueryDb,
            crates_map: &CratesMap,
            visited: &mut FxHashMap<CrateBuilderId, Crate>,
            visited_root_files: &mut FxHashSet<FileId>,
            all_crates: &mut FxIndexSet<Crate>,
            source: CrateBuilderId,
        ) -> Crate {
            if let Some(&crate_id) = visited.get(&source) {
                return crate_id;
            }
            let krate = &graph[source];
            let dependencies = krate
                .basic
                .dependencies
                .iter()
                .map(|dep| BuiltDependency {
                    crate_id: go(
                        graph,
                        db,
                        crates_map,
                        visited,
                        visited_root_files,
                        all_crates,
                        dep.crate_id,
                    ),
                    name: dep.name.clone(),
                    prelude: dep.prelude,
                    sysroot: dep.sysroot,
                })
                .collect::<Vec<_>>();
            let crate_data = BuiltCrateData {
                dependencies,
                edition: krate.basic.edition,
                is_proc_macro: krate.basic.is_proc_macro,
                origin: krate.basic.origin.clone(),
                root_file_id: krate.basic.root_file_id,
                proc_macro_cwd: krate.basic.proc_macro_cwd.clone(),
            };
            let disambiguator = if visited_root_files.insert(krate.basic.root_file_id) {
                None
            } else {
                Some(Box::new((crate_data.clone(), krate.cfg_options.to_hashable())))
            };

            let unique_crate_data =
                UniqueCrateData { root_file_id: krate.basic.root_file_id, disambiguator };
            let crate_input = match crates_map.0.entry(unique_crate_data) {
                Entry::Occupied(entry) => {
                    let old_crate = *entry.get();
                    if crate_data != *old_crate.data(db) {
                        old_crate.set_data(db).with_durability(Durability::MEDIUM).to(crate_data);
                    }
                    if krate.extra != *old_crate.extra_data(db) {
                        old_crate
                            .set_extra_data(db)
                            .with_durability(Durability::MEDIUM)
                            .to(krate.extra.clone());
                    }
                    if krate.cfg_options != *old_crate.cfg_options(db) {
                        old_crate
                            .set_cfg_options(db)
                            .with_durability(Durability::MEDIUM)
                            .to(krate.cfg_options.clone());
                    }
                    if krate.env != *old_crate.env(db) {
                        old_crate
                            .set_env(db)
                            .with_durability(Durability::MEDIUM)
                            .to(krate.env.clone());
                    }
                    if krate.ws_data != *old_crate.workspace_data(db) {
                        old_crate
                            .set_workspace_data(db)
                            .with_durability(Durability::MEDIUM)
                            .to(krate.ws_data.clone());
                    }
                    old_crate
                }
                Entry::Vacant(entry) => {
                    let input = Crate::builder(
                        crate_data,
                        krate.extra.clone(),
                        krate.ws_data.clone(),
                        krate.cfg_options.clone(),
                        krate.env.clone(),
                    )
                    .durability(Durability::MEDIUM)
                    .new(db);
                    entry.insert(input);
                    input
                }
            };
            all_crates.insert(crate_input);
            visited.insert(source, crate_input);
            crate_input
        }
    }

    pub fn iter(&self) -> impl Iterator<Item = CrateBuilderId> + '_ {
        self.arena.iter().map(|(idx, _)| idx)
    }

    /// Returns an iterator over all transitive dependencies of the given crate,
    /// including the crate itself.
    pub fn transitive_deps(&self, of: CrateBuilderId) -> impl Iterator<Item = CrateBuilderId> {
        let mut worklist = vec![of];
        let mut deps = FxHashSet::default();

        while let Some(krate) = worklist.pop() {
            if !deps.insert(krate) {
                continue;
            }

            worklist.extend(self[krate].basic.dependencies.iter().map(|dep| dep.crate_id));
        }

        deps.into_iter()
    }

    /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
    /// come before the crate itself).
    fn crates_in_topological_order(&self) -> Vec<CrateBuilderId> {
        let mut res = Vec::new();
        let mut visited = FxHashSet::default();

        for krate in self.iter() {
            go(self, &mut visited, &mut res, krate);
        }

        return res;

        fn go(
            graph: &CrateGraphBuilder,
            visited: &mut FxHashSet<CrateBuilderId>,
            res: &mut Vec<CrateBuilderId>,
            source: CrateBuilderId,
        ) {
            if !visited.insert(source) {
                return;
            }
            for dep in graph[source].basic.dependencies.iter() {
                go(graph, visited, res, dep.crate_id)
            }
            res.push(source)
        }
    }

    /// Extends this crate graph by adding a complete second crate
    /// graph and adjust the ids in the [`ProcMacroPaths`] accordingly.
    ///
    /// This will deduplicate the crates of the graph where possible.
    /// Furthermore dependencies are sorted by crate id to make deduplication easier.
    ///
    /// Returns a map mapping `other`'s IDs to the new IDs in `self`.
    pub fn extend(
        &mut self,
        mut other: CrateGraphBuilder,
        proc_macros: &mut ProcMacroPaths,
    ) -> FxHashMap<CrateBuilderId, CrateBuilderId> {
        // Sorting here is a bit pointless because the input is likely already sorted.
        // However, the overhead is small and it makes the `extend` method harder to misuse.
        self.arena
            .iter_mut()
            .for_each(|(_, data)| data.basic.dependencies.sort_by_key(|dep| dep.crate_id));

        let m = self.arena.len();
        let topo = other.crates_in_topological_order();
        let mut id_map: FxHashMap<CrateBuilderId, CrateBuilderId> = FxHashMap::default();
        for topo in topo {
            let crate_data = &mut other.arena[topo];

            crate_data
                .basic
                .dependencies
                .iter_mut()
                .for_each(|dep| dep.crate_id = id_map[&dep.crate_id]);
            crate_data.basic.dependencies.sort_by_key(|dep| dep.crate_id);

            let find = self.arena.iter().take(m).find_map(|(k, v)| (v == crate_data).then_some(k));
            let new_id = find.unwrap_or_else(|| self.arena.alloc(crate_data.clone()));
            id_map.insert(topo, new_id);
        }

        *proc_macros =
            mem::take(proc_macros).into_iter().map(|(id, macros)| (id_map[&id], macros)).collect();
        id_map
    }

    fn find_path(
        &self,
        visited: &mut FxHashSet<CrateBuilderId>,
        from: CrateBuilderId,
        to: CrateBuilderId,
    ) -> Option<Vec<CrateBuilderId>> {
        if !visited.insert(from) {
            return None;
        }

        if from == to {
            return Some(vec![to]);
        }

        for dep in &self[from].basic.dependencies {
            let crate_id = dep.crate_id;
            if let Some(mut path) = self.find_path(visited, crate_id, to) {
                path.push(from);
                return Some(path);
            }
        }

        None
    }

    /// Removes all crates from this crate graph except for the ones in `to_keep` and fixes up the dependencies.
    /// Returns a mapping from old crate ids to new crate ids.
    pub fn remove_crates_except(
        &mut self,
        to_keep: &[CrateBuilderId],
    ) -> Vec<Option<CrateBuilderId>> {
        let mut id_map = vec![None; self.arena.len()];
        self.arena = std::mem::take(&mut self.arena)
            .into_iter()
            .filter_map(|(id, data)| if to_keep.contains(&id) { Some((id, data)) } else { None })
            .enumerate()
            .map(|(new_id, (id, data))| {
                id_map[id.into_raw().into_u32() as usize] =
                    Some(CrateBuilderId::from_raw(RawIdx::from_u32(new_id as u32)));
                data
            })
            .collect();
        for (_, data) in self.arena.iter_mut() {
            data.basic.dependencies.iter_mut().for_each(|dep| {
                dep.crate_id =
                    id_map[dep.crate_id.into_raw().into_u32() as usize].expect("crate was filtered")
            });
        }
        id_map
    }

    pub fn shrink_to_fit(&mut self) {
        self.arena.shrink_to_fit();
    }
}

impl BuiltCrateData {
    pub fn root_file_id(&self, db: &dyn salsa::Database) -> EditionedFileId {
        EditionedFileId::new(db, self.root_file_id, self.edition)
    }
}

impl Extend<(String, String)> for Env {
    fn extend<T: IntoIterator<Item = (String, String)>>(&mut self, iter: T) {
        self.entries.extend(iter);
    }
}

impl FromIterator<(String, String)> for Env {
    fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
        Env { entries: FromIterator::from_iter(iter) }
    }
}

impl Env {
    pub fn set(&mut self, env: &str, value: impl Into<String>) {
        self.entries.insert(env.to_owned(), value.into());
    }

    pub fn get(&self, env: &str) -> Option<String> {
        self.entries.get(env).cloned()
    }

    pub fn extend_from_other(&mut self, other: &Env) {
        self.entries.extend(other.entries.iter().map(|(x, y)| (x.to_owned(), y.to_owned())));
    }

    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }

    pub fn insert(&mut self, k: impl Into<String>, v: impl Into<String>) -> Option<String> {
        self.entries.insert(k.into(), v.into())
    }

    pub fn contains_key(&self, arg: &str) -> bool {
        self.entries.contains_key(arg)
    }
}

impl From<Env> for Vec<(String, String)> {
    fn from(env: Env) -> Vec<(String, String)> {
        let mut entries: Vec<_> = env.entries.into_iter().collect();
        entries.sort();
        entries
    }
}

impl<'a> IntoIterator for &'a Env {
    type Item = (&'a String, &'a String);
    type IntoIter = std::collections::hash_map::Iter<'a, String, String>;

    fn into_iter(self) -> Self::IntoIter {
        self.entries.iter()
    }
}

#[derive(Debug)]
pub struct CyclicDependenciesError {
    path: Vec<(CrateBuilderId, Option<CrateDisplayName>)>,
}

impl CyclicDependenciesError {
    fn from(&self) -> &(CrateBuilderId, Option<CrateDisplayName>) {
        self.path.first().unwrap()
    }
    fn to(&self) -> &(CrateBuilderId, Option<CrateDisplayName>) {
        self.path.last().unwrap()
    }
}

impl fmt::Display for CyclicDependenciesError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let render = |(id, name): &(CrateBuilderId, Option<CrateDisplayName>)| match name {
            Some(it) => format!("{it}({id:?})"),
            None => format!("{id:?}"),
        };
        let path = self.path.iter().rev().map(render).collect::<Vec<String>>().join(" -> ");
        write!(
            f,
            "cyclic deps: {} -> {}, alternative path: {}",
            render(self.from()),
            render(self.to()),
            path
        )
    }
}

#[cfg(test)]
mod tests {
    use triomphe::Arc;
    use vfs::AbsPathBuf;

    use crate::{CrateWorkspaceData, DependencyBuilder};

    use super::{CrateGraphBuilder, CrateName, CrateOrigin, Edition::Edition2018, Env, FileId};

    fn empty_ws_data() -> Arc<CrateWorkspaceData> {
        Arc::new(CrateWorkspaceData { target: Err("".into()), toolchain: None })
    }

    #[test]
    fn detect_cyclic_dependency_indirect() {
        let mut graph = CrateGraphBuilder::default();
        let crate1 = graph.add_crate_root(
            FileId::from_raw(1u32),
            Edition2018,
            None,
            None,
            Default::default(),
            Default::default(),
            Env::default(),
            CrateOrigin::Local { repo: None, name: None },
            false,
            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
            empty_ws_data(),
        );
        let crate2 = graph.add_crate_root(
            FileId::from_raw(2u32),
            Edition2018,
            None,
            None,
            Default::default(),
            Default::default(),
            Env::default(),
            CrateOrigin::Local { repo: None, name: None },
            false,
            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
            empty_ws_data(),
        );
        let crate3 = graph.add_crate_root(
            FileId::from_raw(3u32),
            Edition2018,
            None,
            None,
            Default::default(),
            Default::default(),
            Env::default(),
            CrateOrigin::Local { repo: None, name: None },
            false,
            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
            empty_ws_data(),
        );
        assert!(
            graph
                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
                .is_ok()
        );
        assert!(
            graph
                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate3").unwrap(), crate3,))
                .is_ok()
        );
        assert!(
            graph
                .add_dep(crate3, DependencyBuilder::new(CrateName::new("crate1").unwrap(), crate1,))
                .is_err()
        );
    }

    #[test]
    fn detect_cyclic_dependency_direct() {
        let mut graph = CrateGraphBuilder::default();
        let crate1 = graph.add_crate_root(
            FileId::from_raw(1u32),
            Edition2018,
            None,
            None,
            Default::default(),
            Default::default(),
            Env::default(),
            CrateOrigin::Local { repo: None, name: None },
            false,
            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
            empty_ws_data(),
        );
        let crate2 = graph.add_crate_root(
            FileId::from_raw(2u32),
            Edition2018,
            None,
            None,
            Default::default(),
            Default::default(),
            Env::default(),
            CrateOrigin::Local { repo: None, name: None },
            false,
            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
            empty_ws_data(),
        );
        assert!(
            graph
                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
                .is_ok()
        );
        assert!(
            graph
                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
                .is_err()
        );
    }

    #[test]
    fn it_works() {
        let mut graph = CrateGraphBuilder::default();
        let crate1 = graph.add_crate_root(
            FileId::from_raw(1u32),
            Edition2018,
            None,
            None,
            Default::default(),
            Default::default(),
            Env::default(),
            CrateOrigin::Local { repo: None, name: None },
            false,
            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
            empty_ws_data(),
        );
        let crate2 = graph.add_crate_root(
            FileId::from_raw(2u32),
            Edition2018,
            None,
            None,
            Default::default(),
            Default::default(),
            Env::default(),
            CrateOrigin::Local { repo: None, name: None },
            false,
            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
            empty_ws_data(),
        );
        let crate3 = graph.add_crate_root(
            FileId::from_raw(3u32),
            Edition2018,
            None,
            None,
            Default::default(),
            Default::default(),
            Env::default(),
            CrateOrigin::Local { repo: None, name: None },
            false,
            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
            empty_ws_data(),
        );
        assert!(
            graph
                .add_dep(crate1, DependencyBuilder::new(CrateName::new("crate2").unwrap(), crate2,))
                .is_ok()
        );
        assert!(
            graph
                .add_dep(crate2, DependencyBuilder::new(CrateName::new("crate3").unwrap(), crate3,))
                .is_ok()
        );
    }

    #[test]
    fn dashes_are_normalized() {
        let mut graph = CrateGraphBuilder::default();
        let crate1 = graph.add_crate_root(
            FileId::from_raw(1u32),
            Edition2018,
            None,
            None,
            Default::default(),
            Default::default(),
            Env::default(),
            CrateOrigin::Local { repo: None, name: None },
            false,
            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
            empty_ws_data(),
        );
        let crate2 = graph.add_crate_root(
            FileId::from_raw(2u32),
            Edition2018,
            None,
            None,
            Default::default(),
            Default::default(),
            Env::default(),
            CrateOrigin::Local { repo: None, name: None },
            false,
            Arc::new(AbsPathBuf::assert_utf8(std::env::current_dir().unwrap())),
            empty_ws_data(),
        );
        assert!(
            graph
                .add_dep(
                    crate1,
                    DependencyBuilder::new(
                        CrateName::normalize_dashes("crate-name-with-dashes"),
                        crate2,
                    )
                )
                .is_ok()
        );
        assert_eq!(
            graph.arena[crate1].basic.dependencies,
            vec![
                DependencyBuilder::new(CrateName::new("crate_name_with_dashes").unwrap(), crate2,)
            ]
        );
    }
}