uv_installer/

plan.rs

use std::fmt;
use std::path::PathBuf;
use std::sync::Arc;

use anyhow::{Result, bail};
use owo_colors::OwoColorize;
use tracing::{debug, warn};

use uv_cache::{Cache, CacheBucket, WheelCache};
use uv_cache_info::Timestamp;
use uv_configuration::{BuildOptions, Reinstall};
use uv_distribution::{
    BuiltWheelIndex, HttpArchivePointer, PathArchivePointer, RegistryWheelIndex,
};
use uv_distribution_filename::WheelFilename;
use uv_distribution_types::{
    BuiltDist, CachedDirectUrlDist, CachedDist, ConfigSettings, Dist, Error, ExtraBuildRequires,
    ExtraBuildVariables, Hashed, IndexLocations, InstalledDist, Name, PackageConfigSettings,
    RequirementSource, Resolution, ResolvedDist, SourceDist,
};
use uv_fs::Simplified;
use uv_normalize::PackageName;
use uv_platform_tags::{AbiTag, IncompatibleTag, LanguageTag, PlatformTag, TagCompatibility, Tags};
use uv_pypi_types::VerbatimParsedUrl;
use uv_python::PythonEnvironment;
use uv_redacted::DisplaySafeUrl;
use uv_types::HashStrategy;

use crate::satisfies::RequirementSatisfaction;
use crate::{InstallationStrategy, SitePackages};

/// A wheel dependency is incompatible with the current platform.
#[derive(Debug)]
pub struct IncompatibleWheelError {
    /// The dependency source (URL or path, with location).
    kind: IncompatibleWheelKind,
    /// Optional compatibility hint generated from wheel tags.
    compatibility_hint: Option<IncompatibleWheelHint>,
}

#[derive(Debug)]
enum IncompatibleWheelKind {
    Url(DisplaySafeUrl),
    Path(PathBuf),
}

impl fmt::Display for IncompatibleWheelKind {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Url(url) => write!(f, "URL ({url})"),
            Self::Path(path) => write!(f, "path ({})", path.user_display()),
        }
    }
}

/// A hint describing why a wheel is incompatible.
#[derive(Debug)]
enum IncompatibleWheelHint {
    /// The wheel targets a different Python version than the current interpreter.
    Python {
        wheel_tags: Vec<LanguageTag>,
        current: Option<LanguageTag>,
    },
    /// The wheel targets a different ABI than the current interpreter.
    Abi {
        wheel_tags: Vec<AbiTag>,
        current: Option<AbiTag>,
    },
    /// The wheel targets a GIL-enabled interpreter, but the current one is free-threaded.
    FreethreadedAbi {
        wheel_tags: Vec<AbiTag>,
        current: Option<AbiTag>,
    },
    /// The wheel targets a different platform than the current one.
    Platform {
        wheel_tags: Vec<PlatformTag>,
        current: Option<PlatformTag>,
    },
}

impl fmt::Display for IncompatibleWheelHint {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Python {
                wheel_tags,
                current,
            } => {
                if let Some(current) = current {
                    write!(
                        f,
                        "The wheel is compatible with {}, but you're using {}",
                        format_language_tags(wheel_tags),
                        format_language_tag(*current),
                    )
                } else {
                    write!(f, "The wheel requires {}", format_language_tags(wheel_tags))
                }
            }
            Self::Abi {
                wheel_tags,
                current,
            } => {
                if let Some(current) = current {
                    write!(
                        f,
                        "The wheel is compatible with {}, but you're using {}",
                        format_abi_tags(wheel_tags),
                        format_abi_tag(*current),
                    )
                } else {
                    write!(f, "The wheel requires {}", format_abi_tags(wheel_tags))
                }
            }
            Self::FreethreadedAbi {
                wheel_tags,
                current,
            } => {
                let current_display = if let Some(current) = current {
                    format_abi_tag(*current)
                } else {
                    "free-threaded Python".to_string()
                };
                let wheel_display = wheel_tags
                    .iter()
                    .map(|tag| match tag {
                        AbiTag::Abi3 => format!("the stable ABI (`{}`)", tag.cyan()),
                        _ => {
                            if let Some(pretty) = tag.pretty() {
                                format!("the {} ABI (`{}`)", pretty.cyan(), tag.cyan())
                            } else {
                                format!("`{}`", tag.cyan())
                            }
                        }
                    })
                    .collect::<Vec<_>>()
                    .join(", ");
                write!(
                    f,
                    "You're using {current_display}, but the wheel was built for {wheel_display}, which requires a GIL-enabled interpreter"
                )
            }
            Self::Platform {
                wheel_tags,
                current,
            } => {
                if let Some(current) = current {
                    write!(
                        f,
                        "The wheel is compatible with {}, but you're on {}",
                        format_platform_tags(wheel_tags),
                        format_platform_tag(current),
                    )
                } else {
                    write!(f, "The wheel requires {}", format_platform_tags(wheel_tags))
                }
            }
        }
    }
}

/// Format a single language tag with optional pretty name and cyan coloring.
fn format_language_tag(tag: LanguageTag) -> String {
    if let Some(pretty) = tag.pretty() {
        format!("{} (`{}`)", pretty.cyan(), tag.cyan())
    } else {
        format!("`{}`", tag.cyan())
    }
}

/// Format a list of language tags as a comma-separated string.
fn format_language_tags(tags: &[LanguageTag]) -> String {
    tags.iter()
        .map(|tag| format_language_tag(*tag))
        .collect::<Vec<_>>()
        .join(", ")
}

/// Format a single ABI tag with optional pretty name and cyan coloring.
fn format_abi_tag(tag: AbiTag) -> String {
    if let Some(pretty) = tag.pretty() {
        format!("{} (`{}`)", pretty.cyan(), tag.cyan())
    } else {
        format!("`{}`", tag.cyan())
    }
}

/// Format a list of ABI tags as a comma-separated string.
fn format_abi_tags(tags: &[AbiTag]) -> String {
    tags.iter()
        .map(|tag| format_abi_tag(*tag))
        .collect::<Vec<_>>()
        .join(", ")
}

/// Format a single platform tag with optional pretty name and cyan coloring.
fn format_platform_tag(tag: &PlatformTag) -> String {
    if let Some(pretty) = tag.pretty() {
        format!("{} (`{}`)", pretty.cyan(), tag.cyan())
    } else {
        format!("`{}`", tag.cyan())
    }
}

/// Format a list of platform tags as a comma-separated string.
fn format_platform_tags(tags: &[PlatformTag]) -> String {
    tags.iter()
        .map(format_platform_tag)
        .collect::<Vec<_>>()
        .join(", ")
}

impl fmt::Display for IncompatibleWheelError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "A {} dependency is incompatible with the current platform",
            self.kind,
        )
    }
}

impl std::error::Error for IncompatibleWheelError {}

impl uv_errors::Hint for IncompatibleWheelError {
    fn hints(&self) -> uv_errors::Hints<'_> {
        if let Some(hint) = &self.compatibility_hint {
            uv_errors::Hints::from(hint.to_string())
        } else {
            uv_errors::Hints::none()
        }
    }
}

/// A planner to generate an [`Plan`] based on a set of requirements.
#[derive(Debug)]
pub struct Planner<'a> {
    resolution: &'a Resolution,
}

impl<'a> Planner<'a> {
    /// Set the requirements use in the [`Plan`].
    pub fn new(resolution: &'a Resolution) -> Self {
        Self { resolution }
    }

    /// Partition a set of requirements into those that should be linked from the cache, those that
    /// need to be downloaded, and those that should be removed.
    ///
    /// The install plan will respect cache [`Freshness`]. Specifically, if refresh is enabled, the
    /// plan will respect cache entries created after the current time (as per the [`Refresh`]
    /// policy). Otherwise, entries will be ignored. The downstream distribution database may still
    /// read those entries from the cache after revalidating them.
    ///
    /// The install plan will also respect the required hashes, such that it will never return a
    /// cached distribution that does not match the required hash. Like pip, though, it _will_
    /// return an _installed_ distribution that does not match the required hash.
    pub fn build(
        self,
        mut site_packages: SitePackages,
        installation: InstallationStrategy,
        reinstall: &Reinstall,
        build_options: &BuildOptions,
        hasher: &HashStrategy,
        index_locations: &IndexLocations,
        config_settings: &ConfigSettings,
        config_settings_package: &PackageConfigSettings,
        extra_build_requires: &ExtraBuildRequires,
        extra_build_variables: &ExtraBuildVariables,
        cache: &Cache,
        venv: &PythonEnvironment,
        tags: &Tags,
    ) -> Result<Plan> {
        // Index all the already-downloaded wheels in the cache.
        let mut registry_index = RegistryWheelIndex::new(
            cache,
            tags,
            index_locations,
            hasher,
            config_settings,
            config_settings_package,
            extra_build_requires,
            extra_build_variables,
        );
        let built_index = BuiltWheelIndex::new(
            cache,
            tags,
            hasher,
            config_settings,
            config_settings_package,
            extra_build_requires,
            extra_build_variables,
        );

        let mut cached = vec![];
        let mut remote = vec![];
        let mut reinstalls = vec![];
        let mut extraneous = vec![];

        // TODO(charlie): There are a few assumptions here that are hard to spot:
        //
        // 1. Apparently, we never return direct URL distributions as [`ResolvedDist::Installed`].
        //    If you trace the resolver, we only ever return [`ResolvedDist::Installed`] if you go
        //    through the [`CandidateSelector`], and we only go through the [`CandidateSelector`]
        //    for registry distributions.
        //
        // 2. We expect any distribution returned as [`ResolvedDist::Installed`] to hit the
        //    "Requirement already installed" path (hence the `unreachable!`) a few lines below it.
        //    So, e.g., if a package is marked as `--reinstall`, we _expect_ that it's not passed in
        //    as [`ResolvedDist::Installed`] here.
        for dist in self.resolution.distributions() {
            // Check if the package should be reinstalled.
            let reinstall = reinstall.contains_package(dist.name())
                || dist
                    .source_tree()
                    .is_some_and(|source_tree| reinstall.contains_path(source_tree));

            // Check if installation of a binary version of the package should be allowed.
            let no_binary = build_options.no_binary_package(dist.name());
            let no_build = build_options.no_build_package(dist.name());

            // Determine whether the distribution is already installed.
            let installed_dists = site_packages.remove_packages(dist.name());
            if reinstall {
                reinstalls.extend(installed_dists);
            } else {
                match installed_dists.as_slice() {
                    [] => {}
                    [installed] => {
                        let source = RequirementSource::from(dist);
                        match RequirementSatisfaction::check(
                            dist.name(),
                            installed,
                            &source,
                            dist.version(),
                            installation,
                            tags,
                            config_settings,
                            config_settings_package,
                            extra_build_requires,
                            extra_build_variables,
                        ) {
                            RequirementSatisfaction::Mismatch => {
                                debug!(
                                    "Requirement installed, but mismatched:\n  Installed: {installed:?}\n  Requested: {source:?}"
                                );
                            }
                            RequirementSatisfaction::Satisfied => {
                                debug!("Requirement already installed: {installed}");
                                continue;
                            }
                            RequirementSatisfaction::OutOfDate => {
                                debug!("Requirement installed, but not fresh: {installed}");

                                // If we made it here, something went wrong in the resolver, because it returned an
                                // already-installed distribution that we "shouldn't" use. Typically, this means the
                                // distribution was considered out-of-date, but in a way that the resolver didn't
                                // detect, and is indicative of drift between the resolver's candidate selector and
                                // the install plan. For example, at present, the resolver doesn't check that an
                                // installed distribution was built with the expected build settings. Treat it as
                                // up-to-date for now; it's just means we may not rebuild a package when we otherwise
                                // should. This is a known issue, but should only affect the `uv pip` CLI, as the
                                // project APIs never return installed distributions during resolution (i.e., the
                                // resolver is stateless).
                                // TODO(charlie): Incorporate these checks into the resolver.
                                if matches!(dist, ResolvedDist::Installed { .. }) {
                                    warn!(
                                        "Installed distribution was considered out-of-date, but returned by the resolver: {dist}"
                                    );
                                    continue;
                                }
                            }
                            RequirementSatisfaction::CacheInvalid => {
                                // Already logged
                            }
                        }
                        reinstalls.push(installed.clone());
                    }
                    // We reinstall installed distributions with multiple versions because
                    // we do not want to keep multiple incompatible versions but removing
                    // one version is likely to break another.
                    _ => reinstalls.extend(installed_dists),
                }
            }

            let ResolvedDist::Installable { dist, .. } = dist else {
                unreachable!("Installed distribution could not be found in site-packages: {dist}");
            };

            if cache.must_revalidate_package(dist.name())
                || dist
                    .source_tree()
                    .is_some_and(|source_tree| cache.must_revalidate_path(source_tree))
            {
                debug!("Must revalidate requirement: {}", dist.name());
                remote.push(dist.clone());
                continue;
            }

            // Identify any cached distributions that satisfy the requirement.
            match dist.as_ref() {
                Dist::Built(BuiltDist::Registry(wheel)) => {
                    if let Some(distribution) = registry_index.wheel(wheel, no_build, no_binary) {
                        debug!("Registry requirement already cached: {distribution}");
                        cached.push(CachedDist::Registry(distribution.clone()));
                        continue;
                    }
                }
                Dist::Built(BuiltDist::DirectUrl(wheel)) => {
                    if !wheel.filename.is_compatible(tags) {
                        return Err(IncompatibleWheelError {
                            kind: IncompatibleWheelKind::Url(wheel.url.to_url()),
                            compatibility_hint: generate_wheel_compatibility_hint(
                                &wheel.filename,
                                tags,
                            ),
                        }
                        .into());
                    }

                    if no_binary {
                        bail!(
                            "A URL dependency points to a wheel which conflicts with `--no-binary`: {}",
                            wheel.url
                        );
                    }

                    // Find the exact wheel from the cache, since we know the filename in
                    // advance.
                    let cache_entry = cache
                        .shard(
                            CacheBucket::Wheels,
                            WheelCache::Url(&wheel.url).wheel_dir(wheel.name().as_ref()),
                        )
                        .entry(format!("{}.http", wheel.filename.cache_key()));

                    // Read the HTTP pointer.
                    match HttpArchivePointer::read_from(&cache_entry) {
                        Ok(Some(pointer)) => {
                            let cache_info = pointer.to_cache_info();
                            let build_info = pointer.to_build_info();
                            let archive = pointer.into_archive();
                            if archive.satisfies(hasher.get(dist.as_ref())) {
                                let cached_dist = CachedDirectUrlDist {
                                    filename: wheel.filename.clone(),
                                    url: VerbatimParsedUrl {
                                        parsed_url: wheel.to_parsed_url(),
                                        verbatim: wheel.url.clone(),
                                    },
                                    hashes: archive.hashes,
                                    cache_info,
                                    build_info,
                                    path: cache.archive(&archive.id).into_boxed_path(),
                                };

                                debug!("URL wheel requirement already cached: {cached_dist}");
                                cached.push(CachedDist::Url(cached_dist));
                                continue;
                            }
                            debug!(
                                "Cached URL wheel requirement does not match expected hash policy for: {wheel}"
                            );
                        }
                        Ok(None) => {}
                        Err(err) => {
                            debug!(
                                "Failed to deserialize cached URL wheel requirement for: {wheel} ({err})"
                            );
                        }
                    }
                }
                Dist::Built(BuiltDist::Path(wheel)) => {
                    // Validate that the path exists.
                    if !wheel.install_path.exists() {
                        return Err(Error::NotFound(wheel.url.to_url()).into());
                    }

                    if !wheel.filename.is_compatible(tags) {
                        return Err(IncompatibleWheelError {
                            kind: IncompatibleWheelKind::Path(wheel.install_path.to_path_buf()),
                            compatibility_hint: generate_wheel_compatibility_hint(
                                &wheel.filename,
                                tags,
                            ),
                        }
                        .into());
                    }

                    if no_binary {
                        bail!(
                            "A path dependency points to a wheel which conflicts with `--no-binary`: {}",
                            wheel.url
                        );
                    }

                    // Find the exact wheel from the cache, since we know the filename in
                    // advance.
                    let cache_entry = cache
                        .shard(
                            CacheBucket::Wheels,
                            WheelCache::Url(&wheel.url).wheel_dir(wheel.name().as_ref()),
                        )
                        .entry(format!("{}.rev", wheel.filename.cache_key()));

                    match PathArchivePointer::read_from(&cache_entry) {
                        Ok(Some(pointer)) => match Timestamp::from_path(&wheel.install_path) {
                            Ok(timestamp) => {
                                if pointer.is_up_to_date(timestamp) {
                                    let cache_info = pointer.to_cache_info();
                                    let build_info = pointer.to_build_info();
                                    let archive = pointer.into_archive();
                                    if archive.satisfies(hasher.get(dist.as_ref())) {
                                        let cached_dist = CachedDirectUrlDist {
                                            filename: wheel.filename.clone(),
                                            url: VerbatimParsedUrl {
                                                parsed_url: wheel.to_parsed_url(),
                                                verbatim: wheel.url.clone(),
                                            },
                                            hashes: archive.hashes,
                                            cache_info,
                                            build_info,
                                            path: cache.archive(&archive.id).into_boxed_path(),
                                        };
                                        debug!(
                                            "Path wheel requirement already cached: {cached_dist}"
                                        );
                                        cached.push(CachedDist::Url(cached_dist));
                                        continue;
                                    }
                                    debug!(
                                        "Cached path wheel requirement does not match expected hash policy for: {wheel}"
                                    );
                                }
                            }
                            Err(err) => {
                                debug!("Failed to get timestamp for wheel {wheel} ({err})");
                            }
                        },
                        Ok(None) => {}
                        Err(err) => {
                            debug!(
                                "Failed to deserialize cached path wheel requirement for: {wheel} ({err})"
                            );
                        }
                    }
                }
                Dist::Built(BuiltDist::GitPath(wheel)) => {
                    if !wheel.filename.is_compatible(tags) {
                        bail!(
                            "A Git path dependency is incompatible with the current platform: {}",
                            wheel.install_path.user_display()
                        );
                    }

                    if no_binary {
                        bail!(
                            "A Git path dependency points to a wheel which conflicts with `--no-binary`: {}",
                            wheel.url
                        );
                    }

                    if let Some(git_sha) = wheel.git.precise() {
                        // Find the exact wheel from the cache, since we know the filename in
                        // advance.
                        let cache_entry = cache
                            .shard(
                                CacheBucket::Wheels,
                                WheelCache::Git(&wheel.url, git_sha.as_short_str()).root(),
                            )
                            .entry(format!("{}.rev", wheel.filename.cache_key()));

                        if let Some(pointer) = PathArchivePointer::read_from(&cache_entry)? {
                            let cache_info = pointer.to_cache_info();
                            let build_info = pointer.to_build_info();
                            let archive = pointer.into_archive();
                            if archive.satisfies(hasher.get(dist.as_ref())) {
                                let cached_dist = CachedDirectUrlDist {
                                    filename: wheel.filename.clone(),
                                    url: VerbatimParsedUrl {
                                        parsed_url: wheel.to_parsed_url(),
                                        verbatim: wheel.url.clone(),
                                    },
                                    hashes: archive.hashes,
                                    cache_info,
                                    build_info,
                                    path: cache.archive(&archive.id).into_boxed_path(),
                                };

                                debug!("Git wheel requirement already cached: {cached_dist}");
                                cached.push(CachedDist::Url(cached_dist));
                                continue;
                            }
                        }
                    }
                }
                Dist::Source(SourceDist::Registry(sdist)) => {
                    if let Some(distribution) = registry_index.source(sdist, no_build, no_binary) {
                        debug!("Registry requirement already cached: {distribution}");
                        cached.push(CachedDist::Registry(distribution.clone()));
                        continue;
                    }
                }
                Dist::Source(SourceDist::DirectUrl(sdist)) => {
                    // Find the most-compatible wheel from the cache, since we don't know
                    // the filename in advance.
                    match built_index.url(sdist) {
                        Ok(Some(wheel)) => {
                            if wheel.filename().name == sdist.name {
                                let cached_dist = wheel.into_url_dist(VerbatimParsedUrl {
                                    parsed_url: sdist.to_parsed_url(),
                                    verbatim: sdist.url.clone(),
                                });
                                debug!("URL source requirement already cached: {cached_dist}");
                                cached.push(CachedDist::Url(cached_dist));
                                continue;
                            }

                            warn!(
                                "Cached wheel filename does not match requested distribution for: `{}` (found: `{}`)",
                                sdist,
                                wheel.filename()
                            );
                        }
                        Ok(None) => {}
                        Err(err) => {
                            debug!(
                                "Failed to deserialize cached wheel filename for: {sdist} ({err})"
                            );
                        }
                    }
                }
                Dist::Source(SourceDist::GitPath(sdist)) => {
                    // Find the most-compatible wheel from the cache, since we don't know
                    // the filename in advance.
                    if let Some(wheel) = built_index.git_path(sdist)? {
                        if wheel.filename().name == sdist.name {
                            let cached_dist = wheel.into_url_dist(VerbatimParsedUrl {
                                parsed_url: sdist.to_parsed_url(),
                                verbatim: sdist.url.clone(),
                            });
                            debug!("Git source requirement already cached: {cached_dist}");
                            cached.push(CachedDist::Url(cached_dist));
                            continue;
                        }

                        warn!(
                            "Cached wheel filename does not match requested distribution for: `{}` (found: `{}`)",
                            sdist,
                            wheel.filename()
                        );
                    }
                }
                Dist::Source(SourceDist::GitDirectory(sdist)) => {
                    // Find the most-compatible wheel from the cache, since we don't know
                    // the filename in advance.
                    if let Some(wheel) = built_index.git_directory(sdist) {
                        if wheel.filename().name == sdist.name {
                            let cached_dist = wheel.into_url_dist(VerbatimParsedUrl {
                                parsed_url: sdist.to_parsed_url(),
                                verbatim: sdist.url.clone(),
                            });
                            debug!("Git source requirement already cached: {cached_dist}");
                            cached.push(CachedDist::Url(cached_dist));
                            continue;
                        }

                        warn!(
                            "Cached wheel filename does not match requested distribution for: `{}` (found: `{}`)",
                            sdist,
                            wheel.filename()
                        );
                    }
                }
                Dist::Source(SourceDist::Path(sdist)) => {
                    // Validate that the path exists.
                    if !sdist.install_path.exists() {
                        return Err(Error::NotFound(sdist.url.to_url()).into());
                    }

                    // Find the most-compatible wheel from the cache, since we don't know
                    // the filename in advance.
                    match built_index.path(sdist) {
                        Ok(Some(wheel)) => {
                            if wheel.filename().name == sdist.name {
                                let cached_dist = wheel.into_url_dist(VerbatimParsedUrl {
                                    parsed_url: sdist.to_parsed_url(),
                                    verbatim: sdist.url.clone(),
                                });
                                debug!("Path source requirement already cached: {cached_dist}");
                                cached.push(CachedDist::Url(cached_dist));
                                continue;
                            }

                            warn!(
                                "Cached wheel filename does not match requested distribution for: `{}` (found: `{}`)",
                                sdist,
                                wheel.filename()
                            );
                        }
                        Ok(None) => {}
                        Err(err) => {
                            debug!(
                                "Failed to deserialize cached wheel filename for: {sdist} ({err})"
                            );
                        }
                    }
                }
                Dist::Source(SourceDist::Directory(sdist)) => {
                    // Validate that the path exists.
                    if !sdist.install_path.exists() {
                        return Err(Error::NotFound(sdist.url.to_url()).into());
                    }

                    // Find the most-compatible wheel from the cache, since we don't know
                    // the filename in advance.
                    match built_index.directory(sdist) {
                        Ok(Some(wheel)) => {
                            if wheel.filename().name == sdist.name {
                                let cached_dist = wheel.into_url_dist(VerbatimParsedUrl {
                                    parsed_url: sdist.to_parsed_url(),
                                    verbatim: sdist.url.clone(),
                                });
                                debug!(
                                    "Directory source requirement already cached: {cached_dist}"
                                );
                                cached.push(CachedDist::Url(cached_dist));
                                continue;
                            }

                            warn!(
                                "Cached wheel filename does not match requested distribution for: `{}` (found: `{}`)",
                                sdist,
                                wheel.filename()
                            );
                        }
                        Ok(None) => {}
                        Err(err) => {
                            debug!(
                                "Failed to deserialize cached wheel filename for: {sdist} ({err})"
                            );
                        }
                    }
                }
            }

            debug!("Identified uncached distribution: {dist}");
            remote.push(dist.clone());
        }

        // Remove any unnecessary packages.
        if site_packages.any() {
            // Retain seed packages unless: (1) the virtual environment was created by uv and
            // (2) the `--seed` argument was not passed to `uv venv`.
            let seed_packages = !venv.cfg().is_ok_and(|cfg| cfg.is_uv() && !cfg.is_seed());
            for dist_info in site_packages {
                if seed_packages && is_seed_package(&dist_info, venv) {
                    debug!("Preserving seed package: {dist_info}");
                    continue;
                }

                debug!("Unnecessary package: {dist_info}");
                extraneous.push(dist_info);
            }
        }

        Ok(Plan {
            cached,
            remote,
            reinstalls,
            extraneous,
        })
    }
}

/// Returns `true` if the given distribution is a seed package.
fn is_seed_package(dist_info: &InstalledDist, venv: &PythonEnvironment) -> bool {
    if venv.interpreter().python_tuple() >= (3, 12) {
        matches!(dist_info.name().as_ref(), "uv" | "pip")
    } else {
        // Include `setuptools` and `wheel` on Python <3.12.
        matches!(
            dist_info.name().as_ref(),
            "pip" | "setuptools" | "wheel" | "uv"
        )
    }
}

/// Generate a hint for explaining wheel compatibility issues.
fn generate_wheel_compatibility_hint(
    filename: &WheelFilename,
    tags: &Tags,
) -> Option<IncompatibleWheelHint> {
    let TagCompatibility::Incompatible(incompatible_tag) = filename.compatibility(tags) else {
        return None;
    };

    match incompatible_tag {
        IncompatibleTag::Python => Some(IncompatibleWheelHint::Python {
            wheel_tags: filename.python_tags().to_vec(),
            current: tags.python_tag(),
        }),
        IncompatibleTag::FreethreadedAbi => Some(IncompatibleWheelHint::FreethreadedAbi {
            wheel_tags: filename.abi_tags().to_vec(),
            current: tags.abi_tag(),
        }),
        IncompatibleTag::Abi => Some(IncompatibleWheelHint::Abi {
            wheel_tags: filename.abi_tags().to_vec(),
            current: tags.abi_tag(),
        }),
        IncompatibleTag::Platform => Some(IncompatibleWheelHint::Platform {
            wheel_tags: filename.platform_tags().to_vec(),
            current: tags.platform_tag().cloned(),
        }),
        _ => None,
    }
}

#[derive(Debug, Default)]
pub struct Plan {
    /// The distributions that are not already installed in the current environment, but are
    /// available in the local cache.
    pub cached: Vec<CachedDist>,

    /// The distributions that are not already installed in the current environment, and are
    /// not available in the local cache.
    pub remote: Vec<Arc<Dist>>,

    /// Any distributions that are already installed in the current environment, but will be
    /// re-installed (including upgraded) to satisfy the requirements.
    pub reinstalls: Vec<InstalledDist>,

    /// Any distributions that are already installed in the current environment, and are
    /// _not_ necessary to satisfy the requirements.
    pub extraneous: Vec<InstalledDist>,
}

impl Plan {
    /// Returns `true` if the plan is empty.
    pub fn is_empty(&self) -> bool {
        self.cached.is_empty()
            && self.remote.is_empty()
            && self.reinstalls.is_empty()
            && self.extraneous.is_empty()
    }

    /// Partition the remote distributions based on a predicate function.
    ///
    /// Returns a tuple of plans, where the first plan contains the remote distributions that match
    /// the predicate, and the second plan contains those that do not.
    ///
    /// Any extraneous and cached distributions will be returned in the first plan, while the second
    /// plan will contain any `false` matches from the remote distributions, along with any
    /// reinstalls for those distributions.
    pub fn partition<F>(self, mut f: F) -> (Self, Self)
    where
        F: FnMut(&PackageName) -> bool,
    {
        let Self {
            cached,
            remote,
            reinstalls,
            extraneous,
        } = self;

        // Partition the remote distributions based on the predicate function.
        let (left_remote, right_remote) = remote
            .into_iter()
            .partition::<Vec<_>, _>(|dist| f(dist.name()));

        // If any remote distributions are not matched, but are already installed, ensure that
        // they're uninstalled as part of the right plan. (Uninstalling them as part of the left
        // plan risks uninstalling them from the environment _prior_ to the replacement being built.)
        let (left_reinstalls, right_reinstalls) = reinstalls
            .into_iter()
            .partition::<Vec<_>, _>(|dist| !right_remote.iter().any(|d| d.name() == dist.name()));

        // If the right plan is non-empty, then remove extraneous distributions as part of the
        // right plan, so they're present until the very end. Otherwise, we risk removing extraneous
        // packages that are actually build dependencies.
        let (left_extraneous, right_extraneous) = if right_remote.is_empty() {
            (extraneous, vec![])
        } else {
            (vec![], extraneous)
        };

        // Always include the cached distributions in the left plan.
        let (left_cached, right_cached) = (cached, vec![]);

        // Include all cached and extraneous distributions in the left plan.
        let left_plan = Self {
            cached: left_cached,
            remote: left_remote,
            reinstalls: left_reinstalls,
            extraneous: left_extraneous,
        };

        // The right plan will only contain the remote distributions that did not match the predicate,
        // along with any reinstalls for those distributions.
        let right_plan = Self {
            cached: right_cached,
            remote: right_remote,
            reinstalls: right_reinstalls,
            extraneous: right_extraneous,
        };

        (left_plan, right_plan)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::str::FromStr;
    use uv_platform_tags::{Arch, Os, Platform, TagsOptions};

    #[test]
    fn test_abi3_on_free_threaded_python_hint() {
        // Create a Tags object for free-threaded Python 3.14
        let platform = Platform::new(
            Os::Manylinux {
                major: 2,
                minor: 28,
            },
            Arch::X86_64,
        );
        let tags = Tags::from_env(
            platform,
            (3, 14),   // python_version
            "cpython", // implementation_name
            (3, 14),   // implementation_version
            TagsOptions {
                manylinux_compatible: true,
                gil_disabled: true,
                debug_enabled: false,
                is_cross: false,
            },
        )
        .unwrap();

        // Create a wheel filename with abi3 tag
        let filename =
            WheelFilename::from_str("foo-1.0-cp37-abi3-manylinux_2_17_x86_64.whl").unwrap();

        // Generate the hint
        let hint = generate_wheel_compatibility_hint(&filename, &tags).unwrap();

        let hint = hint.to_string();
        let hint = anstream::adapter::strip_str(&hint);
        insta::assert_snapshot!(hint, @"You're using free-threaded CPython 3.14 (`cp314t`), but the wheel was built for the stable ABI (`abi3`), which requires a GIL-enabled interpreter");
    }

    #[test]
    fn test_gil_enabled_cpython_on_free_threaded_python_hint() {
        // Create a Tags object for free-threaded Python 3.14
        let platform = Platform::new(
            Os::Manylinux {
                major: 2,
                minor: 28,
            },
            Arch::X86_64,
        );
        let tags = Tags::from_env(
            platform,
            (3, 14),   // python_version
            "cpython", // implementation_name
            (3, 14),   // implementation_version
            TagsOptions {
                manylinux_compatible: true,
                gil_disabled: true,
                debug_enabled: false,
                is_cross: false,
            },
        )
        .unwrap();

        // Create a wheel filename with cp314 ABI tag (same version, GIL-enabled)
        let filename =
            WheelFilename::from_str("foo-1.0-cp314-cp314-manylinux_2_17_x86_64.whl").unwrap();

        // Generate the hint
        let hint = generate_wheel_compatibility_hint(&filename, &tags).unwrap();

        let hint = hint.to_string();
        let hint = anstream::adapter::strip_str(&hint);
        insta::assert_snapshot!(hint, @"You're using free-threaded CPython 3.14 (`cp314t`), but the wheel was built for the CPython 3.14 ABI (`cp314`), which requires a GIL-enabled interpreter");
    }

    #[test]
    fn test_abi3_on_regular_python_no_special_hint() {
        // Create a Tags object for regular (non-free-threaded) Python 3.14
        let platform = Platform::new(
            Os::Manylinux {
                major: 2,
                minor: 28,
            },
            Arch::X86_64,
        );
        let tags = Tags::from_env(
            platform,
            (3, 14),   // python_version
            "cpython", // implementation_name
            (3, 14),   // implementation_version
            TagsOptions {
                manylinux_compatible: true,
                gil_disabled: false,
                debug_enabled: false,
                is_cross: false,
            },
        )
        .unwrap();

        // Create a wheel filename with abi3 tag
        let filename =
            WheelFilename::from_str("foo-1.0-cp37-abi3-manylinux_2_17_x86_64.whl").unwrap();

        // The wheel should be compatible (abi3 works on regular Python)
        let hint = generate_wheel_compatibility_hint(&filename, &tags);

        // No hint should be generated because the wheel is compatible
        assert!(
            hint.is_none(),
            "Expected no hint (wheel should be compatible), got: {hint:?}"
        );
    }
}