cargo 0.100.0

use std::fmt;
use std::fmt::Write as _;
use std::path::{Path, PathBuf};

use crate::sources::IndexSummary;
use crate::sources::path::RecursivePathSource;
use crate::sources::source::QueryKind;
use crate::util::edit_distance::{closest, edit_distance};
use crate::util::errors::CargoResult;
use crate::util::{GlobalContext, OptVersionReq, VersionExt};
use crate::workspace::{Dependency, PackageId, Registry, Summary};
use anyhow::Error;

use super::VersionPreferences;
use super::context::ResolverContext;
use super::types::{ConflictMap, ConflictReason};

/// Error during resolution providing a path of `PackageId`s.
pub struct ResolveError {
    cause: Error,
    package_path: Vec<PackageId>,
}

impl ResolveError {
    pub fn new<E: Into<Error>>(cause: E, package_path: Vec<PackageId>) -> Self {
        Self {
            cause: cause.into(),
            package_path,
        }
    }

    /// Returns a path of packages from the package whose requirements could not be resolved up to
    /// the root.
    pub fn package_path(&self) -> &[PackageId] {
        &self.package_path
    }
}

impl std::error::Error for ResolveError {
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        self.cause.source()
    }
}

impl fmt::Debug for ResolveError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.cause.fmt(f)
    }
}

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

pub type ActivateResult<T> = Result<T, ActivateError>;

#[derive(Debug)]
pub enum ActivateError {
    Fatal(anyhow::Error),
    Conflict(PackageId, ConflictReason),
}

impl From<::anyhow::Error> for ActivateError {
    fn from(t: ::anyhow::Error) -> Self {
        ActivateError::Fatal(t)
    }
}

impl From<(PackageId, ConflictReason)> for ActivateError {
    fn from(t: (PackageId, ConflictReason)) -> Self {
        ActivateError::Conflict(t.0, t.1)
    }
}

pub(super) fn activation_error(
    resolver_ctx: &ResolverContext,
    registry: &impl Registry,
    version_prefs: &VersionPreferences,
    parent: &Summary,
    dep: &Dependency,
    conflicting_activations: &ConflictMap,
    candidates: &[Summary],
    gctx: &GlobalContext,
) -> ResolveError {
    let to_resolve_err = |err| {
        ResolveError::new(
            err,
            resolver_ctx
                .parents
                .path_to_bottom(&parent.package_id())
                .into_iter()
                .map(|(node, _)| node)
                .cloned()
                .collect(),
        )
    };

    if !candidates.is_empty() {
        let mut msg = format!("failed to select a version for `{}`.", dep.package_name());
        msg.push_str("\n    ... required by ");
        msg.push_str(&describe_path_in_context(
            resolver_ctx,
            &parent.package_id(),
        ));

        msg.push_str("\nversions that meet the requirements `");
        msg.push_str(&dep.version_req().to_string());
        msg.push_str("` ");

        if let Some(v) = dep.version_req().locked_version() {
            msg.push_str("(locked to ");
            msg.push_str(&v.to_string());
            msg.push_str(") ");
        }

        msg.push_str("are: ");
        msg.push_str(
            &candidates
                .iter()
                .map(|v| v.version())
                .map(|v| v.to_string())
                .collect::<Vec<_>>()
                .join(", "),
        );

        let mut conflicting_activations: Vec<_> = conflicting_activations.iter().collect();
        conflicting_activations.sort_unstable();
        // This is reversed to show the newest versions first. I don't know if there is
        // a strong reason to do this, but that is how the code previously worked
        // (see https://github.com/rust-lang/cargo/pull/5037) and I don't feel like changing it.
        conflicting_activations.reverse();
        // Flag used for grouping all semver errors together.
        let mut has_semver = false;

        for (p, r) in &conflicting_activations {
            match r {
                ConflictReason::Semver => {
                    has_semver = true;
                }
                ConflictReason::Links(link) => {
                    msg.push_str("\n\npackage `");
                    msg.push_str(&*dep.package_name());
                    msg.push_str("` links to the native library `");
                    msg.push_str(link);
                    msg.push_str("`, but it conflicts with a previous package which links to `");
                    msg.push_str(link);
                    msg.push_str("` as well:\n");
                    msg.push_str(&describe_path_in_context(resolver_ctx, p));
                    msg.push_str("\nnote: only one package in the dependency graph may specify the same links value to ensure that only one copy of a native library is linked in the final binary");
                    msg.push_str("\nfor more information, see https://doc.rust-lang.org/cargo/reference/resolver.html#links");
                    msg.push_str("\nhelp: try to adjust your dependencies so that only one package uses the `links = \"");
                    msg.push_str(link);
                    msg.push_str("\"` value");
                }
                ConflictReason::MissingFeature(feature) => {
                    msg.push_str("\n\npackage `");
                    msg.push_str(&*p.name());
                    msg.push_str("` depends on `");
                    msg.push_str(&*dep.package_name());
                    msg.push_str("` with feature `");
                    msg.push_str(feature);
                    msg.push_str("` but `");
                    msg.push_str(&*dep.package_name());
                    msg.push_str("` does not have that feature.\n");
                    let latest = candidates.last().expect("in the non-empty branch");
                    if let Some(closest) = closest(feature, latest.features().keys(), |k| k) {
                        msg.push_str("help: there is a feature `");
                        msg.push_str(closest);
                        msg.push_str("` with a similar name\n");
                    } else if !latest.features().is_empty() {
                        let mut features: Vec<_> =
                            latest.features().keys().map(|f| f.as_str()).collect();
                        features.sort();
                        msg.push_str("help: available features: ");
                        msg.push_str(&features.join(", "));
                        msg.push_str("\n");
                    }
                    // p == parent so the full path is redundant.
                }
                ConflictReason::RequiredDependencyAsFeature(feature) => {
                    msg.push_str("\n\npackage `");
                    msg.push_str(&*p.name());
                    msg.push_str("` depends on `");
                    msg.push_str(&*dep.package_name());
                    msg.push_str("` with feature `");
                    msg.push_str(feature);
                    msg.push_str("` but `");
                    msg.push_str(&*dep.package_name());
                    msg.push_str("` does not have that feature.\n");
                    msg.push_str(
                        "note: a required dependency with that name exists, \
                         but only optional dependencies can be used as features.\n",
                    );
                    // p == parent so the full path is redundant.
                }
                ConflictReason::NonImplicitDependencyAsFeature(feature) => {
                    msg.push_str("\n\npackage `");
                    msg.push_str(&*p.name());
                    msg.push_str("` depends on `");
                    msg.push_str(&*dep.package_name());
                    msg.push_str("` with feature `");
                    msg.push_str(feature);
                    msg.push_str("` but `");
                    msg.push_str(&*dep.package_name());
                    msg.push_str("` does not have that feature.\n");
                    msg.push_str(
                        "note: an optional dependency with that name exists, \
                         but that dependency uses the \"dep:\" \
                         syntax in the features table, so it does not have an \
                         implicit feature with that name.\n",
                    );
                    // p == parent so the full path is redundant.
                }
            }
        }

        if has_semver {
            // Group these errors together.
            msg.push_str("\n\nall possible versions conflict with previously selected packages");
            for (p, r) in &conflicting_activations {
                if let ConflictReason::Semver = r {
                    msg.push_str("\n\n  previously selected ");
                    msg.push_str(&describe_path_in_context(resolver_ctx, p));
                }
            }
        }

        msg.push_str("\n\nfailed to select a version for `");
        msg.push_str(&*dep.package_name());
        msg.push_str("` which could resolve this conflict");

        return to_resolve_err(anyhow::format_err!("{}", msg));
    }

    // We didn't actually find any candidates, so we need to
    // give an error message that nothing was found.
    let mut msg = String::new();
    let mut hints = String::new();
    // Whether any candidate was rejected for being newer than `min-publish-age`,
    let mut has_too_new = false;
    if let Some(version_candidates) = rejected_versions(registry, dep) {
        let version_candidates = match version_candidates {
            Ok(c) => c,
            Err(e) => return to_resolve_err(e),
        };

        let locked_version = dep
            .version_req()
            .locked_version()
            .map(|v| format!(" (locked to {})", v))
            .unwrap_or_default();
        let _ = writeln!(
            &mut msg,
            "failed to select a version for the requirement `{} = \"{}\"`{}",
            dep.package_name(),
            dep.version_req(),
            locked_version
        );
        for candidate in version_candidates {
            match candidate {
                IndexSummary::Candidate(summary) => {
                    if let Some(violation) = version_prefs.too_new(&summary) {
                        has_too_new = true;
                        let note = violation.note();
                        let _ = writeln!(
                            &mut msg,
                            "  version {} is too new ({note})",
                            summary.version(),
                        );
                    } else {
                        // HACK: If this was a real candidate, we wouldn't hit this case.
                        // so it must be a patch which get normalized to being a candidate
                        let _ =
                            writeln!(&mut msg, "  version {} is unavailable", summary.version());
                    }
                }
                IndexSummary::Yanked(summary) => {
                    let _ = writeln!(&mut msg, "  version {} is yanked", summary.version());
                }
                IndexSummary::Offline(summary) => {
                    let _ = writeln!(&mut msg, "  version {} is not cached", summary.version());
                }
                IndexSummary::Unsupported(summary, schema_version) => {
                    if let Some(rust_version) = summary.rust_version() {
                        // HACK: technically its unsupported and we shouldn't make assumptions
                        // about the entry but this is limited and for diagnostics purposes
                        let _ = writeln!(
                            &mut msg,
                            "  version {} requires cargo {}",
                            summary.version(),
                            rust_version
                        );
                    } else {
                        let _ = writeln!(
                            &mut msg,
                            "  version {} requires a Cargo version that supports index version {}",
                            summary.version(),
                            schema_version
                        );
                    }
                }
                IndexSummary::Invalid(summary) => {
                    let _ = writeln!(
                        &mut msg,
                        "  version {}'s index entry is invalid",
                        summary.version()
                    );
                }
            }
        }
    } else if let Some(candidates) = alt_versions(registry, dep) {
        let candidates = match candidates {
            Ok(c) => c,
            Err(e) => return to_resolve_err(e),
        };
        let versions = {
            let mut versions = candidates
                .iter()
                .take(3)
                .map(|cand| cand.version().to_string())
                .collect::<Vec<_>>();

            if candidates.len() > 3 {
                versions.push("...".into());
            }

            versions.join(", ")
        };

        let locked_version = dep
            .version_req()
            .locked_version()
            .map(|v| format!(" (locked to {})", v))
            .unwrap_or_default();

        let _ = writeln!(
            &mut msg,
            "failed to select a version for the requirement `{} = \"{}\"`{}",
            dep.package_name(),
            dep.version_req(),
            locked_version,
        );
        let _ = writeln!(
            &mut msg,
            "candidate versions found which didn't match: {versions}",
        );

        // If we have a pre-release candidate, then that may be what our user is looking for
        if let Some(pre) = candidates.iter().find(|c| c.version().is_prerelease()) {
            let _ = write!(
                &mut hints,
                "\nhelp: if you are looking for the prerelease package it needs to be specified explicitly"
            );
            let _ = write!(
                &mut hints,
                "\n    {} = {{ version = \"{}\" }}",
                pre.name(),
                pre.version()
            );
        }

        // If we have a path dependency with a locked version, then this may
        // indicate that we updated a sub-package and forgot to run `cargo
        // update`. In this case try to print a helpful error!
        if dep.source_id().is_path() && dep.version_req().is_locked() {
            let _ = write!(
                &mut hints,
                "\nhelp: to update a path dependency's locked version, run `cargo update`",
            );
        }

        if registry.is_replaced(dep.source_id()) {
            let _ = write!(
                &mut hints,
                "\nnote: perhaps a crate was updated and forgotten to be re-vendored?"
            );
        }
    } else if let Some(packages) = alt_paths(dep, gctx) {
        let path = dep.source_id().url().to_file_path().unwrap();
        let _ = writeln!(
            &mut msg,
            "no matching package named `{}` found",
            dep.package_name()
        );

        let mut exact_match: Option<PathBuf> = None;
        let mut found_dir: Option<String> = None;
        let mut names_found: Vec<(String, PathBuf)> = vec![];

        for pkg in &packages {
            let manifest_dir = pkg.manifest_path().parent().unwrap();
            let p_name = pkg.name().as_str();
            if p_name == dep.package_name().as_str() {
                exact_match = Some(manifest_dir.to_path_buf());
                break;
            } else if manifest_dir == path {
                found_dir = Some(p_name.to_string());
            } else {
                names_found.push((p_name.to_string(), manifest_dir.to_path_buf()));
            }
        }

        let mut add_hint = |name: &str, p: &Path| {
            let _ = writeln!(&mut hints);
            let _ = write!(
                &mut hints,
                "help: package `{}` exists at `{}`",
                name,
                p.display()
            );
        };

        if let Some(dir) = exact_match {
            add_hint(dep.package_name().as_str(), &dir);
        } else if let Some(dir_pkg) = found_dir {
            add_hint(&dir_pkg, &path);
        } else {
            names_found.sort_by(|a, b| a.0.cmp(&b.0));
            for (name, p) in names_found.iter() {
                add_hint(name, p);
            }
        }
    } else if let Some(name_candidates) = alt_names(registry, dep) {
        let name_candidates = match name_candidates {
            Ok(c) => c,
            Err(e) => return to_resolve_err(e),
        };
        let _ = writeln!(
            &mut msg,
            "no matching package named `{}` found",
            dep.package_name()
        );

        let mut names = name_candidates
            .iter()
            .take(3)
            .map(|c| c.1.name().as_str())
            .collect::<Vec<_>>();
        if name_candidates.len() > 3 {
            names.push("...");
        }
        let suggestions =
            names
                .iter()
                .enumerate()
                .fold(String::default(), |acc, (i, el)| match i {
                    0 => acc + el,
                    i if names.len() - 1 == i && name_candidates.len() <= 3 => acc + " or " + el,
                    _ => acc + ", " + el,
                });
        let _ = writeln!(
            &mut hints,
            "\nhelp: packages with similar names: {suggestions}"
        );
    } else {
        let _ = writeln!(
            &mut msg,
            "no matching package named `{}` found",
            dep.package_name()
        );
    }

    let mut location_searched_msg = registry.describe_source(dep.source_id());
    if location_searched_msg.is_empty() {
        location_searched_msg = format!("{}", dep.source_id());
    }
    let _ = writeln!(&mut msg, "location searched: {}", location_searched_msg);
    let _ = write!(
        &mut msg,
        "required by {}",
        describe_path_in_context(resolver_ctx, &parent.package_id()),
    );

    if has_too_new {
        let downgrade_to =
            alt_versions(registry, dep)
                .and_then(|r| r.ok())
                .and_then(|candidates| {
                    candidates
                        .into_iter()
                        .find(|s| version_prefs.too_new(s).is_none())
                });
        if let Some(summary) = downgrade_to {
            let _ = write!(
                &mut hints,
                "\nhelp: to preserve the min-publish-age, \
                 downgrade the requirement to \"{}\"",
                summary.version(),
            );
        }
        let _ = write!(
            &mut hints,
            "\nhelp: to use too-new packages anyways, \
             re-resolve with `CARGO_RESOLVER_INCOMPATIBLE_PUBLISH_AGE=allow`",
        );
    }

    if let Some(offline_flag) = gctx.offline_flag() {
        let _ = write!(
            &mut hints,
            "\nnote: offline mode (via `{offline_flag}`) \
             can sometimes cause surprising resolution failures\
             \nhelp: if this error is too confusing you may wish to retry \
             without `{offline_flag}`",
        );
    }

    to_resolve_err(anyhow::format_err!("{msg}{hints}"))
}

// Maybe the user mistyped the ver_req? Like `dep="2"` when `dep="0.2"`
// was meant. So we re-query the registry with `dep="*"` so we can
// list a few versions that were actually found.
fn alt_versions(registry: &impl Registry, dep: &Dependency) -> Option<CargoResult<Vec<Summary>>> {
    let mut wild_dep = dep.clone();
    wild_dep.set_version_req(OptVersionReq::Any);

    let candidates = match crate::util::block_on(registry.query_vec(&wild_dep, QueryKind::Exact)) {
        Ok(candidates) => candidates,
        Err(e) => return Some(Err(e)),
    };
    let mut candidates: Vec<_> = candidates
        .into_iter()
        .filter_map(|s| match s {
            IndexSummary::Candidate(s) => Some(s),
            _ => None,
        })
        .collect();
    candidates.sort_unstable_by(|a, b| b.version().cmp(a.version()));
    if candidates.is_empty() {
        None
    } else {
        Some(Ok(candidates))
    }
}

/// Maybe something is wrong with the available versions
fn rejected_versions(
    registry: &impl Registry,
    dep: &Dependency,
) -> Option<CargoResult<Vec<IndexSummary>>> {
    let mut version_candidates =
        match crate::util::block_on(registry.query_vec(&dep, QueryKind::RejectedVersions)) {
            Ok(candidates) => candidates,
            Err(e) => return Some(Err(e)),
        };
    version_candidates.sort_unstable_by_key(|a| a.package_id().version().clone());
    if version_candidates.is_empty() {
        None
    } else {
        Some(Ok(version_candidates))
    }
}

/// Maybe the user mistyped the name? Like `dep-thing` when `Dep_Thing`
/// was meant. So we try asking the registry for a `fuzzy` search for suggestions.
fn alt_names(
    registry: &impl Registry,
    dep: &Dependency,
) -> Option<CargoResult<Vec<(usize, Summary)>>> {
    let mut wild_dep = dep.clone();
    wild_dep.set_version_req(OptVersionReq::Any);

    let name_candidates =
        match crate::util::block_on(registry.query_vec(&wild_dep, QueryKind::AlternativeNames)) {
            Ok(candidates) => candidates,
            Err(e) => return Some(Err(e)),
        };
    let mut name_candidates: Vec<_> = name_candidates
        .into_iter()
        .map(|s| match s {
            IndexSummary::Candidate(sum)
            | IndexSummary::Yanked(sum)
            | IndexSummary::Offline(sum)
            | IndexSummary::Unsupported(sum, _)
            | IndexSummary::Invalid(sum) => sum,
        })
        .collect();
    name_candidates.sort_unstable_by_key(|a| a.name());
    name_candidates.dedup_by(|a, b| a.name() == b.name());
    let mut name_candidates: Vec<_> = name_candidates
        .into_iter()
        .filter_map(|n| Some((edit_distance(&*wild_dep.package_name(), &*n.name(), 3)?, n)))
        .collect();
    name_candidates.sort_by_key(|o| o.0);

    if name_candidates.is_empty() {
        None
    } else {
        Some(Ok(name_candidates))
    }
}

/// For path dependencies, scan the dependency directory for any packages
/// that exist in subdirectories. This helps when the user points to a
/// directory without a Cargo.toml or with the wrong package name.
fn alt_paths(dep: &Dependency, gctx: &GlobalContext) -> Option<Vec<crate::workspace::Package>> {
    if !dep.source_id().is_path() {
        return None;
    }
    let path = dep.source_id().url().to_file_path().ok()?;
    if !path.is_dir() {
        return None;
    }
    let source_id = dep.source_id();
    let source = RecursivePathSource::new(&path, source_id, gctx);
    let packages = source.read_packages().ok()?;
    if packages.is_empty() {
        None
    } else {
        Some(packages)
    }
}

/// Returns String representation of dependency chain for a particular `pkgid`
/// within given context.
pub(super) fn describe_path_in_context(cx: &ResolverContext, id: &PackageId) -> String {
    let iter = cx
        .parents
        .path_to_bottom(id)
        .into_iter()
        .map(|(p, d)| (p, d.and_then(|d| d.iter().next())));
    describe_path(iter)
}

/// Returns String representation of dependency chain for a particular `pkgid`.
///
/// Note that all elements of `path` iterator should have `Some` dependency
/// except the first one. It would look like:
///
/// (pkg0, None)
/// -> (pkg1, dep from pkg1 satisfied by pkg0)
/// -> (pkg2, dep from pkg2 satisfied by pkg1)
/// -> ...
pub(crate) fn describe_path<'a>(
    mut path: impl Iterator<Item = (&'a PackageId, Option<&'a Dependency>)>,
) -> String {
    use std::fmt::Write;

    if let Some(p) = path.next() {
        let mut dep_path_desc = format!("package `{}`", p.0);
        for (pkg, dep) in path {
            let dep = dep.unwrap();
            let source_kind = if dep.source_id().is_path() {
                "path "
            } else if dep.source_id().is_git() {
                "git "
            } else {
                ""
            };
            let requirement = if source_kind.is_empty() {
                format!("{} = \"{}\"", dep.name_in_toml(), dep.version_req())
            } else {
                dep.name_in_toml().to_string()
            };
            let locked_version = dep
                .version_req()
                .locked_version()
                .map(|v| format!("(locked to {}) ", v))
                .unwrap_or_default();

            write!(
                dep_path_desc,
                "\n    ... which satisfies {}dependency `{}` {}of package `{}`",
                source_kind, requirement, locked_version, pkg
            )
            .unwrap();
        }

        return dep_path_desc;
    }

    String::new()
}