pubsat 0.1.0

//! Semantic versioning logic and constraint evaluation
//!
//! This module provides comprehensive support for parsing and evaluating
//! npm-style semantic version constraints (^1.2.3, ~1.0.0, >=1.5.0, etc.)

use std::fmt;
use std::str::FromStr;

use semver::Version;
use thiserror::Error;

/// Comprehensive version set specification
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum VersionSet {
    /// Any version (*)
    Any,

    /// Exact version match (=1.2.3)
    Exact(Version),

    /// Version range with optional bounds
    Range {
        /// Minimum version (inclusive or exclusive)
        min: Option<VersionBound>,
        /// Maximum version (inclusive or exclusive)
        max: Option<VersionBound>,
    },

    /// Caret constraint (^1.2.3)
    /// Compatible within same major version
    Caret(Version),

    /// Tilde constraint (~1.2.3)
    /// Compatible within same major.minor version
    Tilde(Version),

    /// Union of multiple version sets (for complex constraints)
    Union(Vec<VersionSet>),

    /// Intersection of multiple version sets
    Intersection(Vec<VersionSet>),

    /// Pre-release versions only
    PreRelease(String),
}

/// Version bound with inclusive/exclusive specification
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct VersionBound {
    pub version: Version,
    pub inclusive: bool,
}

impl VersionBound {
    /// Create an inclusive bound (>=version or <=version)
    pub fn inclusive(version: Version) -> Self {
        Self {
            version,
            inclusive: true,
        }
    }

    /// Create an exclusive bound (>version or <version)
    pub fn exclusive(version: Version) -> Self {
        Self {
            version,
            inclusive: false,
        }
    }

    /// Check if this bound is satisfied by a version (for minimum bounds)
    pub fn satisfies_min(&self, version: &Version) -> bool {
        if self.inclusive {
            version >= &self.version
        } else {
            version > &self.version
        }
    }

    /// Check if this bound is satisfied by a version (for maximum bounds)
    pub fn satisfies_max(&self, version: &Version) -> bool {
        if self.inclusive {
            version <= &self.version
        } else {
            version < &self.version
        }
    }
}

/// Errors that can occur during version constraint parsing
#[derive(Debug, Error)]
pub enum VersionError {
    #[error("Invalid version format: {input}")]
    InvalidVersion { input: String },

    #[error("Invalid version constraint: {constraint}")]
    InvalidConstraint { constraint: String },

    #[error("Unsupported constraint operator: {operator}")]
    UnsupportedOperator { operator: String },

    #[error("Empty constraint")]
    EmptyConstraint,
}

impl VersionSet {
    /// Create an "any" version set (matches all versions)
    pub fn any() -> Self {
        Self::Any
    }

    /// Create an exact version constraint
    pub fn exact(version: Version) -> Self {
        Self::Exact(version)
    }

    /// Create a caret constraint (^1.2.3)
    pub fn caret(version: Version) -> Self {
        Self::Caret(version)
    }

    /// Create a tilde constraint (~1.2.3)
    pub fn tilde(version: Version) -> Self {
        Self::Tilde(version)
    }

    /// Create a range constraint
    pub fn range(min: Option<VersionBound>, max: Option<VersionBound>) -> Self {
        Self::Range { min, max }
    }

    /// Parse an npm-style version constraint string
    pub fn parse(constraint: &str) -> Result<Self, VersionError> {
        let constraint = constraint.trim();

        if constraint.is_empty() {
            return Err(VersionError::EmptyConstraint);
        }

        // Handle special cases. Dist-tags (latest, next, beta, …) are
        // resolved at the registry; here we just accept them as "any" so
        // the parser doesn't reject a constraint that the registry will
        // later narrow down.
        match constraint {
            "*" | "" => return Ok(Self::Any),
            tag if is_dist_tag(tag) => return Ok(Self::Any),
            _ => {}
        }

        // Handle union constraints (||) - check this first since || contains spaces
        if constraint.contains("||") {
            return Self::parse_union(constraint);
        }

        // Hyphen ranges: "1.2.3 - 2.3.4"  ⇒  ">=1.2.3 <=2.3.4". Detect with
        // surrounding spaces so we don't mistake a prerelease tag like
        // "1.0.0-beta" for a hyphen range.
        if let Some((lo, hi)) = split_hyphen_range(constraint) {
            return Self::parse_hyphen_range(lo.trim(), hi.trim());
        }

        // Tolerate spaces between an operator and its version: "<=  2.0.0"
        // is what the safer-buffer / many other npm packages publish, even
        // though it's outside the strict node-semver grammar.
        let normalized = normalize_operator_spaces(constraint);

        // Handle compound constraints (space-separated)
        if normalized.contains(' ') {
            return Self::parse_compound(&normalized);
        }

        // Parse single constraint
        Self::parse_single(&normalized)
    }

    /// Parse a hyphen range `"<lo> - <hi>"` into `>=lo <=hi`.
    fn parse_hyphen_range(lo: &str, hi: &str) -> Result<Self, VersionError> {
        let lo_version = parse_partial_version(lo)?;
        // Hyphen high bound: a partial version uses the "next minor/patch"
        // semantics in node-semver. e.g. "1.2 - 2.3" → "<2.4.0", "1 - 2" → "<3.0.0".
        let hi_max = partial_upper_bound(hi)?;
        Ok(match hi_max {
            // Closed upper bound (full X.Y.Z given): use <= hi
            PartialUpper::Closed(v) => Self::Range {
                min: Some(VersionBound::inclusive(lo_version)),
                max: Some(VersionBound::inclusive(v)),
            },
            // Open upper bound (partial given): use < computed-ceiling
            PartialUpper::Open(v) => Self::Range {
                min: Some(VersionBound::inclusive(lo_version)),
                max: Some(VersionBound::exclusive(v)),
            },
        })
    }

    /// Parse a compound constraint like ">=1.0.0 <2.0.0"
    fn parse_compound(constraint: &str) -> Result<Self, VersionError> {
        let parts: Vec<&str> = constraint.split_whitespace().collect();
        let mut constraints = Vec::new();

        for part in parts {
            constraints.push(Self::parse_single(part)?);
        }

        Ok(Self::Intersection(constraints))
    }

    /// Parse a union constraint like "1.x || 2.x"
    fn parse_union(constraint: &str) -> Result<Self, VersionError> {
        let parts: Vec<&str> = constraint
            .split("||")
            .map(|s| s.trim())
            .filter(|s| !s.is_empty())
            .collect();
        let mut constraints = Vec::new();

        for part in parts {
            constraints.push(Self::parse(part)?);
        }

        if constraints.is_empty() {
            return Err(VersionError::InvalidConstraint {
                constraint: constraint.to_string(),
            });
        }

        if constraints.len() == 1 {
            return Ok(constraints.into_iter().next().unwrap());
        }

        Ok(Self::Union(constraints))
    }

    /// Parse a single constraint like "^1.2.3" or ">=1.0.0"
    fn parse_single(constraint: &str) -> Result<Self, VersionError> {
        let constraint = constraint.trim();

        // Caret constraints: ^1.2.3
        if let Some(version_str) = constraint.strip_prefix('^') {
            return Self::caret_from_partial(version_str);
        }

        // Tilde constraints: ~1.2.3
        if let Some(version_str) = constraint.strip_prefix('~') {
            return Self::tilde_from_partial(version_str);
        }

        // Range constraints: >=1.0.0, <2.0.0, etc.
        if let Some(version_str) = constraint.strip_prefix(">=") {
            return Ok(Self::Range {
                min: Some(VersionBound::inclusive(parse_partial_version(version_str)?)),
                max: None,
            });
        }

        if let Some(version_str) = constraint.strip_prefix('>') {
            return Ok(Self::Range {
                min: Some(VersionBound::exclusive(parse_partial_version(version_str)?)),
                max: None,
            });
        }

        if let Some(version_str) = constraint.strip_prefix("<=") {
            return Ok(Self::Range {
                min: None,
                max: Some(VersionBound::inclusive(parse_partial_version(version_str)?)),
            });
        }

        if let Some(version_str) = constraint.strip_prefix('<') {
            return Ok(Self::Range {
                min: None,
                max: Some(VersionBound::exclusive(parse_partial_version(version_str)?)),
            });
        }

        // Exact version (with optional = prefix)
        let version_str = constraint.strip_prefix('=').unwrap_or(constraint);

        // Handle x-ranges like 1.x, 1.2.x, 1.*, *
        if is_x_range(version_str) {
            return Self::parse_x_range(version_str);
        }

        // A bare partial like "1.2" is treated as an x-range: "1.2" ⇒ "1.2.x".
        // A bare full version like "1.2.3" is exact (npm convention).
        if Version::parse(version_str).is_ok() {
            let version = Version::parse(version_str).unwrap();
            return Ok(Self::Exact(version));
        }
        // Fall back to partial: "1" ⇒ "1.x.x", "1.2" ⇒ "1.2.x"
        Self::parse_x_range_from_partial(version_str)
    }

    /// Build a Caret constraint from a partial version like "^1", "^1.2",
    /// or "^1.2.3". Partial forms are completed to "X.0.0" / "X.Y.0".
    fn caret_from_partial(s: &str) -> Result<Self, VersionError> {
        let version = parse_partial_version(s)?;
        Ok(Self::Caret(version))
    }

    /// Build a Tilde constraint from a partial version. Partials follow the
    /// node-semver convention: "~1" → "~1.0.0", "~1.2" → "~1.2.0".
    fn tilde_from_partial(s: &str) -> Result<Self, VersionError> {
        let version = parse_partial_version(s)?;
        Ok(Self::Tilde(version))
    }

    /// Parse a partial version (1, 1.2) as an x-range.
    fn parse_x_range_from_partial(s: &str) -> Result<Self, VersionError> {
        // Treat missing components as x: "1" → "1.x.x", "1.2" → "1.2.x".
        let parts: Vec<&str> = s.split('.').collect();
        match parts.len() {
            1 => {
                let major: u64 = parts[0].parse().map_err(|_| VersionError::InvalidVersion {
                    input: s.to_string(),
                })?;
                Ok(Self::Range {
                    min: Some(VersionBound::inclusive(Version::new(major, 0, 0))),
                    max: Some(VersionBound::exclusive(Version::new(major + 1, 0, 0))),
                })
            }
            2 => {
                let major: u64 = parts[0].parse().map_err(|_| VersionError::InvalidVersion {
                    input: s.to_string(),
                })?;
                let minor: u64 = parts[1].parse().map_err(|_| VersionError::InvalidVersion {
                    input: s.to_string(),
                })?;
                Ok(Self::Range {
                    min: Some(VersionBound::inclusive(Version::new(major, minor, 0))),
                    max: Some(VersionBound::exclusive(Version::new(major, minor + 1, 0))),
                })
            }
            _ => Err(VersionError::InvalidVersion {
                input: s.to_string(),
            }),
        }
    }

    /// Parse X-range constraints like "1.x" or "1.2.x"
    fn parse_x_range(version_str: &str) -> Result<Self, VersionError> {
        let parts: Vec<&str> = version_str.split('.').collect();

        match parts.len() {
            1 if parts[0].to_lowercase() == "x" => {
                // "x" - any version
                Ok(Self::Any)
            }
            2 if parts[1].to_lowercase() == "x" => {
                // "1.x" - any version in major 1
                let major: u64 = parts[0].parse().map_err(|_| VersionError::InvalidVersion {
                    input: version_str.to_string(),
                })?;
                Ok(Self::Range {
                    min: Some(VersionBound::inclusive(Version::new(major, 0, 0))),
                    max: Some(VersionBound::exclusive(Version::new(major + 1, 0, 0))),
                })
            }
            3 if parts[2].to_lowercase() == "x" => {
                // "1.2.x" - any version in major.minor 1.2
                let major: u64 = parts[0].parse().map_err(|_| VersionError::InvalidVersion {
                    input: version_str.to_string(),
                })?;
                let minor: u64 = parts[1].parse().map_err(|_| VersionError::InvalidVersion {
                    input: version_str.to_string(),
                })?;
                Ok(Self::Range {
                    min: Some(VersionBound::inclusive(Version::new(major, minor, 0))),
                    max: Some(VersionBound::exclusive(Version::new(major, minor + 1, 0))),
                })
            }
            _ => Err(VersionError::InvalidVersion {
                input: version_str.to_string(),
            }),
        }
    }

    /// Check if a version satisfies this constraint (alias for satisfies)
    pub fn contains(&self, version: &Version) -> bool {
        self.satisfies(version)
    }

    /// Check if a version satisfies this constraint
    pub fn satisfies(&self, version: &Version) -> bool {
        match self {
            Self::Any => true,

            Self::Exact(v) => version == v,

            Self::Range { min, max } => {
                if let Some(min_bound) = min {
                    if !min_bound.satisfies_min(version) {
                        return false;
                    }
                }
                if let Some(max_bound) = max {
                    if !max_bound.satisfies_max(version) {
                        return false;
                    }
                }
                true
            }

            Self::Caret(base) => {
                // node-semver caret rules:
                //   ^1.2.3   := >=1.2.3 <2.0.0    (allow minor + patch)
                //   ^0.2.3   := >=0.2.3 <0.3.0    (0.x: allow only patch)
                //   ^0.0.3   := >=0.0.3 <0.0.4    (0.0.x: exact patch)
                if version < base {
                    return false;
                }
                if base.major > 0 {
                    version.major == base.major
                } else if base.minor > 0 {
                    version.major == 0 && version.minor == base.minor
                } else {
                    version.major == 0 && version.minor == 0 && version.patch == base.patch
                }
            }

            Self::Tilde(base) => {
                // ~1.2.3 := >=1.2.3 <1.3.0 (compatible within same major.minor)
                version >= base && version.major == base.major && version.minor == base.minor
            }

            Self::Union(sets) => sets.iter().any(|set| set.satisfies(version)),

            Self::Intersection(sets) => sets.iter().all(|set| set.satisfies(version)),

            Self::PreRelease(tag) => version.pre.as_str() == tag,
        }
    }

    /// Get all versions from a list that satisfy this constraint
    pub fn filter_versions<'a>(&self, versions: &'a [Version]) -> Vec<&'a Version> {
        versions.iter().filter(|&v| self.satisfies(v)).collect()
    }

    /// Get the best (highest) version that satisfies this constraint
    pub fn select_best<'a>(&self, versions: &'a [Version]) -> Option<&'a Version> {
        self.filter_versions(versions).into_iter().max()
    }

    /// Check if this version set intersects with another (has common versions)
    pub fn intersects(&self, other: &VersionSet) -> bool {
        match (self, other) {
            // Any constraint intersects with everything
            (Self::Any, _) | (_, Self::Any) => true,

            // Exact version constraints
            (Self::Exact(a), Self::Exact(b)) => a == b,
            (Self::Exact(v), constraint) | (constraint, Self::Exact(v)) => constraint.satisfies(v),

            // Range constraints
            (
                Self::Range {
                    min: min1,
                    max: max1,
                },
                Self::Range {
                    min: min2,
                    max: max2,
                },
            ) => self.ranges_intersect(min1, max1, min2, max2),
            (Self::Range { min, max }, constraint) | (constraint, Self::Range { min, max }) => {
                self.range_intersects_constraint(min, max, constraint)
            }

            // Caret constraints (^1.2.3 means >=1.2.3 <2.0.0)
            (Self::Caret(v1), Self::Caret(v2)) => v1.major == v2.major && (v1 <= v2 || v2 <= v1),
            (Self::Caret(base), constraint) | (constraint, Self::Caret(base)) => {
                let caret_range = Self::Range {
                    min: Some(VersionBound::inclusive(base.clone())),
                    max: Some(VersionBound::exclusive(Version::new(base.major + 1, 0, 0))),
                };
                caret_range.intersects(constraint)
            }

            // Tilde constraints (~1.2.3 means >=1.2.3 <1.3.0)
            (Self::Tilde(v1), Self::Tilde(v2)) => {
                v1.major == v2.major && v1.minor == v2.minor && (v1 <= v2 || v2 <= v1)
            }
            (Self::Tilde(base), constraint) | (constraint, Self::Tilde(base)) => {
                let tilde_range = Self::Range {
                    min: Some(VersionBound::inclusive(base.clone())),
                    max: Some(VersionBound::exclusive(Version::new(
                        base.major,
                        base.minor + 1,
                        0,
                    ))),
                };
                tilde_range.intersects(constraint)
            }

            // Union constraints - intersect if any component intersects
            (Self::Union(sets), other) | (other, Self::Union(sets)) => {
                sets.iter().any(|set| set.intersects(other))
            }

            // Intersection constraints - intersect if all components intersect
            (Self::Intersection(sets), other) | (other, Self::Intersection(sets)) => {
                sets.iter().all(|set| set.intersects(other))
            }

            // PreRelease constraints - specific case first to avoid unreachable pattern
            (Self::PreRelease(tag1), Self::PreRelease(tag2)) => tag1 == tag2,
        }
    }

    /// Helper method to check if two ranges intersect
    fn ranges_intersect(
        &self,
        min1: &Option<VersionBound>,
        max1: &Option<VersionBound>,
        min2: &Option<VersionBound>,
        max2: &Option<VersionBound>,
    ) -> bool {
        // Check if the ranges overlap
        let start1 = min1.as_ref().map(|b| &b.version);
        let end1 = max1.as_ref().map(|b| &b.version);
        let start2 = min2.as_ref().map(|b| &b.version);
        let end2 = max2.as_ref().map(|b| &b.version);

        match (start1, end1, start2, end2) {
            // If either range is unbounded, they likely intersect
            (None, None, ..) | (_, _, None, None) => true,

            // Compare the bounds
            (Some(s1), Some(e1), Some(s2), Some(e2)) => {
                // Range 1: [s1, e1], Range 2: [s2, e2]
                // They intersect if max(s1, s2) <= min(e1, e2)
                let max_start = if s1 >= s2 { s1 } else { s2 };
                let min_end = if e1 <= e2 { e1 } else { e2 };
                max_start <= min_end
            }

            // Handle cases with one bound
            (Some(s1), None, Some(_s2), Some(e2)) => s1 <= e2,
            (Some(_s1), Some(e1), Some(s2), None) => s2 <= e1,
            (None, Some(e1), Some(s2), Some(_e2)) => s2 <= e1,
            (Some(s1), Some(_e1), None, Some(e2)) => s1 <= e2,

            // Handle cases with ranges unbounded on both sides
            (None, Some(e1), Some(s2), None) => s2 <= e1,
            (Some(s1), None, None, Some(e2)) => s1 <= e2,

            // Other combinations - be conservative
            _ => true,
        }
    }

    /// Helper method to check if a range intersects with another constraint
    fn range_intersects_constraint(
        &self,
        min: &Option<VersionBound>,
        max: &Option<VersionBound>,
        constraint: &VersionSet,
    ) -> bool {
        // For now, use a simple heuristic - check if any "typical" versions in the
        // range satisfy the constraint
        match constraint {
            Self::Any => true,
            Self::Exact(v) => {
                // Check if the exact version falls within the range
                if let Some(min_bound) = min {
                    if !min_bound.satisfies_min(v) {
                        return false;
                    }
                }
                if let Some(max_bound) = max {
                    if !max_bound.satisfies_max(v) {
                        return false;
                    }
                }
                true
            }
            _ => true, // Conservative approach for complex constraints
        }
    }

    /// Combine this version set with another using intersection (AND)
    pub fn intersect(self, other: VersionSet) -> VersionSet {
        match (self, other) {
            (Self::Any, other) | (other, Self::Any) => other,
            (Self::Intersection(mut a), Self::Intersection(b)) => {
                a.extend(b);
                Self::Intersection(a)
            }
            (Self::Intersection(mut sets), other) | (other, Self::Intersection(mut sets)) => {
                sets.push(other);
                Self::Intersection(sets)
            }
            (a, b) => Self::Intersection(vec![a, b]),
        }
    }

    /// Combine this version set with another using union (OR)
    pub fn union(self, other: VersionSet) -> VersionSet {
        match (self, other) {
            (Self::Any, _) | (_, Self::Any) => Self::Any,
            (Self::Union(mut a), Self::Union(b)) => {
                a.extend(b);
                Self::Union(a)
            }
            (Self::Union(mut sets), other) | (other, Self::Union(mut sets)) => {
                sets.push(other);
                Self::Union(sets)
            }
            (a, b) => Self::Union(vec![a, b]),
        }
    }

    /// Simplify the version set by removing redundant constraints
    pub fn simplify(self) -> VersionSet {
        match self {
            Self::Intersection(sets) if sets.is_empty() => Self::Any,
            Self::Intersection(sets) if sets.len() == 1 => {
                sets.into_iter().next().unwrap().simplify()
            }
            Self::Union(sets) if sets.is_empty() => Self::Any, // No valid versions
            Self::Union(sets) if sets.len() == 1 => sets.into_iter().next().unwrap().simplify(),
            Self::Union(sets) => {
                let simplified: Vec<_> = sets.into_iter().map(|s| s.simplify()).collect();
                Self::Any.simplify_union(simplified) // Use a dummy instance to
                // call the method
            }
            Self::Intersection(sets) => {
                let simplified: Vec<_> = sets.into_iter().map(|s| s.simplify()).collect();
                Self::Any.simplify_intersection(simplified) // Use a dummy
                // instance to call
                // the method
            }
            other => other,
        }
    }

    /// Simplify a union by removing redundant and subsumed constraints
    fn simplify_union(self, mut sets: Vec<VersionSet>) -> VersionSet {
        // Remove Any constraints (they make the whole union Any)
        if sets.iter().any(|s| matches!(s, Self::Any)) {
            return Self::Any;
        }

        // Remove duplicates
        sets.sort_by_key(|a| self.constraint_sort_key(a));
        sets.dedup();

        // Remove constraints that are subsumed by others
        let mut i = 0;
        while i < sets.len() {
            let mut j = i + 1;
            while j < sets.len() {
                if self.constraint_subsumes(&sets[i], &sets[j]) {
                    // sets[i] subsumes sets[j], remove sets[j]
                    sets.remove(j);
                } else if self.constraint_subsumes(&sets[j], &sets[i]) {
                    // sets[j] subsumes sets[i], remove sets[i] and restart
                    sets.remove(i);
                    i = i.saturating_sub(1);
                    break;
                } else {
                    j += 1;
                }
            }
            if j == sets.len() {
                // No changes were made in the inner loop
                i += 1;
            }
        }

        // Merge overlapping range constraints where possible
        sets = self.merge_union_ranges(sets);

        match sets.len() {
            0 => Self::Any, // This shouldn't happen, but handle it gracefully
            1 => sets.into_iter().next().unwrap(),
            _ => Self::Union(sets),
        }
    }

    /// Simplify an intersection by removing redundant constraints and detecting
    /// contradictions
    fn simplify_intersection(self, mut sets: Vec<VersionSet>) -> VersionSet {
        // Check for contradictions and Any constraints
        sets.retain(|s| !matches!(s, Self::Any));

        // Remove duplicates
        sets.sort_by_key(|a| self.constraint_sort_key(a));
        sets.dedup();

        // Check for direct contradictions (exact versions that don't match)
        let exact_versions: Vec<_> = sets
            .iter()
            .filter_map(|s| match s {
                Self::Exact(v) => Some(v.clone()),
                _ => None,
            })
            .collect();

        if exact_versions.len() > 1 {
            // Multiple exact versions = contradiction = no solutions
            return self.create_contradiction();
        }

        // Remove constraints that are subsumed by others in intersection
        let mut i = 0;
        while i < sets.len() {
            let mut j = i + 1;
            while j < sets.len() {
                if self.constraint_subsumes(&sets[i], &sets[j]) {
                    // sets[i] subsumes sets[j] in intersection, keep the more restrictive sets[j]
                    sets.remove(i);
                    i = i.saturating_sub(1);
                    break;
                } else if self.constraint_subsumes(&sets[j], &sets[i]) {
                    // sets[j] subsumes sets[i], keep the more restrictive sets[i]
                    sets.remove(j);
                } else if !sets[i].intersects(&sets[j]) {
                    // No intersection = contradiction
                    return self.create_contradiction();
                } else {
                    j += 1;
                }
            }
            if j == sets.len() {
                i += 1;
            }
        }

        // Try to merge compatible range constraints
        sets = self.merge_intersection_ranges(sets);

        match sets.len() {
            0 => Self::Any,
            1 => sets.into_iter().next().unwrap(),
            _ => Self::Intersection(sets),
        }
    }

    /// Check if constraint `a` subsumes constraint `b` (a is less restrictive
    /// than b)
    fn constraint_subsumes(&self, a: &VersionSet, b: &VersionSet) -> bool {
        match (a, b) {
            (Self::Any, _) => true,  // Any subsumes everything
            (_, Self::Any) => false, // Nothing subsumes Any except Any itself

            // Exact versions
            (Self::Exact(v1), Self::Exact(v2)) => v1 == v2,
            (constraint, Self::Exact(v)) => constraint.satisfies(v), /* If constraint accepts v,
                                                                       * it subsumes exact v */

            // Range constraints
            (
                Self::Range {
                    min: min1,
                    max: max1,
                },
                Self::Range {
                    min: min2,
                    max: max2,
                },
            ) => self.range_subsumes(min1, max1, min2, max2),

            // Caret constraints
            (Self::Caret(v1), Self::Caret(v2)) => {
                // ^1.2.0 subsumes ^1.3.0 if they're in the same major version
                v1.major == v2.major && v1 <= v2
            }

            // Tilde constraints
            (Self::Tilde(v1), Self::Tilde(v2)) => {
                // ~1.2.0 subsumes ~1.2.3 if they're in the same major.minor
                v1.major == v2.major && v1.minor == v2.minor && v1 <= v2
            }

            // Mixed constraint types - use intersection logic
            (constraint, other) => {
                // This is a simple heuristic - could be more sophisticated
                constraint.intersects(other) && self.is_less_restrictive(constraint, other)
            }
        }
    }

    /// Check if one range subsumes another
    fn range_subsumes(
        &self,
        min1: &Option<VersionBound>,
        max1: &Option<VersionBound>,
        min2: &Option<VersionBound>,
        max2: &Option<VersionBound>,
    ) -> bool {
        // Range 1 subsumes Range 2 if Range 1 is less restrictive (covers more
        // versions)
        let min1_less_restrictive = match (min1, min2) {
            (None, _) => true,        // No minimum is less restrictive than any minimum
            (Some(_), None) => false, // Having a minimum is more restrictive than no minimum
            (Some(b1), Some(b2)) => {
                b1.version < b2.version
                    || (b1.version == b2.version && b1.inclusive && !b2.inclusive)
            }
        };

        let max1_less_restrictive = match (max1, max2) {
            (None, _) => true,        // No maximum is less restrictive than any maximum
            (Some(_), None) => false, // Having a maximum is more restrictive than no maximum
            (Some(b1), Some(b2)) => {
                b1.version > b2.version
                    || (b1.version == b2.version && b1.inclusive && !b2.inclusive)
            }
        };

        min1_less_restrictive && max1_less_restrictive
    }

    /// Simple heuristic to determine if one constraint is less restrictive than
    /// another
    fn is_less_restrictive(&self, a: &VersionSet, b: &VersionSet) -> bool {
        // This is a simple heuristic - a more complete implementation would
        // need to check specific version ranges
        match (a, b) {
            (Self::Any, _) => true,
            (_, Self::Any) => false,
            (Self::Caret(_), Self::Exact(_)) => true,
            (Self::Tilde(_), Self::Exact(_)) => true,
            (Self::Range { .. }, Self::Exact(_)) => true,
            _ => false, // Conservative for other cases
        }
    }

    /// Merge overlapping or adjacent range constraints in a union
    fn merge_union_ranges(&self, sets: Vec<VersionSet>) -> Vec<VersionSet> {
        let mut ranges: Vec<(Option<VersionBound>, Option<VersionBound>)> = Vec::new();
        let mut non_ranges = Vec::new();

        // Separate ranges from other constraints
        for set in sets {
            match set {
                Self::Range { min, max } => ranges.push((min, max)),
                other => non_ranges.push(other),
            }
        }

        if ranges.len() <= 1 {
            // No merging needed
            non_ranges.extend(
                ranges
                    .into_iter()
                    .map(|(min, max)| Self::Range { min, max }),
            );
            return non_ranges;
        }

        // Sort ranges by their start points
        ranges.sort_by(|a, b| match (&a.0, &b.0) {
            (None, None) => std::cmp::Ordering::Equal,
            (None, Some(_)) => std::cmp::Ordering::Less,
            (Some(_), None) => std::cmp::Ordering::Greater,
            (Some(min1), Some(min2)) => min1.version.cmp(&min2.version),
        });

        // Merge overlapping ranges
        let mut merged = Vec::new();
        let mut current = ranges[0].clone();

        for (min, max) in ranges.into_iter().skip(1) {
            if self.ranges_can_merge(&current.0, &current.1, &min, &max) {
                current = self.merge_two_ranges(current.0, current.1, min, max);
            } else {
                merged.push(Self::Range {
                    min: current.0,
                    max: current.1,
                });
                current = (min, max);
            }
        }
        merged.push(Self::Range {
            min: current.0,
            max: current.1,
        });

        non_ranges.extend(merged);
        non_ranges
    }

    /// Merge compatible range constraints in an intersection
    fn merge_intersection_ranges(&self, sets: Vec<VersionSet>) -> Vec<VersionSet> {
        let mut ranges: Vec<(Option<VersionBound>, Option<VersionBound>)> = Vec::new();
        let mut non_ranges = Vec::new();

        // Separate ranges from other constraints
        for set in sets {
            match set {
                Self::Range { min, max } => ranges.push((min, max)),
                other => non_ranges.push(other),
            }
        }

        if ranges.len() <= 1 {
            non_ranges.extend(
                ranges
                    .into_iter()
                    .map(|(min, max)| Self::Range { min, max }),
            );
            return non_ranges;
        }

        // For intersection, we need to find the most restrictive bounds
        let mut merged_min: Option<VersionBound> = None;
        let mut merged_max: Option<VersionBound> = None;

        for (min, max) in ranges {
            // For intersection, take the most restrictive minimum (highest)
            merged_min = match (merged_min, min) {
                (None, min) => min,
                (merged_min, None) => merged_min,
                (Some(m), Some(n)) => Some(
                    if m.version > n.version
                        || (m.version == n.version && !m.inclusive && n.inclusive)
                    {
                        m
                    } else {
                        n
                    },
                ),
            };

            // For intersection, take the most restrictive maximum (lowest)
            merged_max = match (merged_max, max) {
                (None, max) => max,
                (merged_max, None) => merged_max,
                (Some(m), Some(n)) => Some(
                    if m.version < n.version
                        || (m.version == n.version && !m.inclusive && n.inclusive)
                    {
                        m
                    } else {
                        n
                    },
                ),
            };
        }

        // Check if the merged range is valid (min <= max)
        let valid_range = match (&merged_min, &merged_max) {
            (Some(min_bound), Some(max_bound)) => {
                min_bound.version < max_bound.version
                    || (min_bound.version == max_bound.version
                        && min_bound.inclusive
                        && max_bound.inclusive)
            }
            _ => true, // If unbounded on one side, it's valid
        };

        if valid_range {
            non_ranges.push(Self::Range {
                min: merged_min,
                max: merged_max,
            });
        } else {
            // Invalid range = contradiction
            return vec![self.create_contradiction()];
        }

        non_ranges
    }

    /// Check if two ranges can be merged in a union
    fn ranges_can_merge(
        &self,
        min1: &Option<VersionBound>,
        max1: &Option<VersionBound>,
        min2: &Option<VersionBound>,
        max2: &Option<VersionBound>,
    ) -> bool {
        // Ranges can be merged if they overlap or are adjacent
        self.ranges_intersect(min1, max1, min2, max2)
            || self.ranges_adjacent(min1, max1, min2, max2)
    }

    /// Check if two ranges are adjacent (one ends where the other begins)
    fn ranges_adjacent(
        &self,
        min1: &Option<VersionBound>,
        max1: &Option<VersionBound>,
        min2: &Option<VersionBound>,
        max2: &Option<VersionBound>,
    ) -> bool {
        let first_check = match (max1, min2) {
            (Some(end1), Some(start2)) => {
                end1.version == start2.version && (end1.inclusive || start2.inclusive)
            }
            _ => false,
        };

        let second_check = match (max2, min1) {
            (Some(end2), Some(start1)) => {
                end2.version == start1.version && (end2.inclusive || start1.inclusive)
            }
            _ => false,
        };

        first_check || second_check
    }

    /// Merge two ranges into a single range
    fn merge_two_ranges(
        &self,
        min1: Option<VersionBound>,
        max1: Option<VersionBound>,
        min2: Option<VersionBound>,
        max2: Option<VersionBound>,
    ) -> (Option<VersionBound>, Option<VersionBound>) {
        let merged_min = match (min1, min2) {
            (None, _) | (_, None) => None, // No bound if either is unbounded
            (Some(b1), Some(b2)) => Some(
                if b1.version < b2.version
                    || (b1.version == b2.version && b1.inclusive && !b2.inclusive)
                {
                    b1
                } else {
                    b2
                },
            ),
        };

        let merged_max = match (max1, max2) {
            (None, _) | (_, None) => None, // No bound if either is unbounded
            (Some(b1), Some(b2)) => Some(
                if b1.version > b2.version
                    || (b1.version == b2.version && b1.inclusive && !b2.inclusive)
                {
                    b1
                } else {
                    b2
                },
            ),
        };

        (merged_min, merged_max)
    }

    /// Create a constraint that represents a contradiction (no valid versions)
    fn create_contradiction(&self) -> VersionSet {
        // Create an impossible range constraint
        Self::Range {
            min: Some(VersionBound::exclusive(Version::new(u64::MAX, 0, 0))),
            max: Some(VersionBound::exclusive(Version::new(0, 0, 0))),
        }
    }

    /// Helper function to create a sort key for constraints (for deduplication)
    fn constraint_sort_key(&self, constraint: &VersionSet) -> String {
        match constraint {
            Self::Any => "0_any".to_string(),
            Self::Exact(v) => format!("1_exact_{}", v),
            Self::Caret(v) => format!("2_caret_{}", v),
            Self::Tilde(v) => format!("3_tilde_{}", v),
            Self::Range { min, max } => {
                format!(
                    "4_range_{}_{}",
                    min.as_ref().map_or("none".to_string(), |b| format!(
                        "{}{}",
                        if b.inclusive { "i" } else { "e" },
                        b.version
                    )),
                    max.as_ref().map_or("none".to_string(), |b| format!(
                        "{}{}",
                        if b.inclusive { "i" } else { "e" },
                        b.version
                    ))
                )
            }
            Self::Union(_) => "5_union".to_string(),
            Self::Intersection(_) => "6_intersection".to_string(),
            Self::PreRelease(tag) => format!("7_prerelease_{}", tag),
        }
    }
}

/// Tags that npm registries accept in place of a version. We don't try to
/// resolve them here — the registry will pick the actual version.
fn is_dist_tag(s: &str) -> bool {
    matches!(s, "latest" | "next" | "beta" | "alpha" | "rc" | "canary")
}

/// Collapse whitespace between an operator and its version so the rest of the
/// parser can split cleanly on whitespace. Example:
///   ">= 2.1.2 < 3.0.0"  →  ">=2.1.2 <3.0.0"
fn normalize_operator_spaces(s: &str) -> String {
    let mut out = String::with_capacity(s.len());
    let chars: Vec<char> = s.chars().collect();
    let mut i = 0;
    while i < chars.len() {
        let c = chars[i];
        let op_len = match (c, chars.get(i + 1)) {
            ('>', Some('=')) | ('<', Some('=')) => 2,
            ('>' | '<' | '=' | '^' | '~', _) => 1,
            _ => 0,
        };
        if op_len > 0 {
            for k in 0..op_len {
                out.push(chars[i + k]);
            }
            i += op_len;
            // Eat any spaces / tabs immediately after the operator.
            while i < chars.len() && (chars[i] == ' ' || chars[i] == '\t') {
                i += 1;
            }
        } else {
            out.push(c);
            i += 1;
        }
    }
    out
}

/// Detect `"<lo> - <hi>"` hyphen ranges. Requires whitespace on both sides of
/// the dash so we don't mistake a prerelease like "1.0.0-beta" for one.
fn split_hyphen_range(s: &str) -> Option<(&str, &str)> {
    // Look for " - " as a token boundary. The string must not be a logical-or.
    let bytes = s.as_bytes();
    for i in 1..bytes.len().saturating_sub(1) {
        if bytes[i] == b'-' && bytes[i - 1] == b' ' && bytes[i + 1] == b' ' {
            // Only treat as a hyphen range if there are no other range
            // operators after the split — i.e. both sides parse as bare
            // partial versions (no leading >, <, =, ^, ~).
            let lo = s[..i].trim_end();
            let hi = s[i + 1..].trim_start();
            if !starts_with_operator(lo) && !starts_with_operator(hi) {
                return Some((lo, hi));
            }
        }
    }
    None
}

fn starts_with_operator(s: &str) -> bool {
    let s = s.trim_start();
    s.starts_with(">=")
        || s.starts_with("<=")
        || s.starts_with('>')
        || s.starts_with('<')
        || s.starts_with('=')
        || s.starts_with('^')
        || s.starts_with('~')
}

/// Whether the given string is an x-range (uses x/X/* as a component).
fn is_x_range(s: &str) -> bool {
    s == "*"
        || s.split('.')
            .any(|p| p.eq_ignore_ascii_case("x") || p == "*")
}

/// Parse a possibly-partial version. Accepts "1", "1.2", "1.2.3", and
/// completes missing components with zeros. Pre-release / build metadata
/// must include all three numeric components (it's an error otherwise),
/// matching what semver allows.
fn parse_partial_version(s: &str) -> Result<Version, VersionError> {
    let s = s.trim();
    if s.is_empty() {
        return Err(VersionError::EmptyConstraint);
    }
    // Try a strict parse first; this preserves prerelease/build metadata.
    if let Ok(v) = Version::parse(s) {
        return Ok(v);
    }
    // Fall back to a partial: "1" → "1.0.0", "1.2" → "1.2.0".
    let parts: Vec<&str> = s.split('.').collect();
    match parts.len() {
        1 => {
            let major: u64 = parts[0].parse().map_err(|_| VersionError::InvalidVersion {
                input: s.to_string(),
            })?;
            Ok(Version::new(major, 0, 0))
        }
        2 => {
            let major: u64 = parts[0].parse().map_err(|_| VersionError::InvalidVersion {
                input: s.to_string(),
            })?;
            let minor: u64 = parts[1].parse().map_err(|_| VersionError::InvalidVersion {
                input: s.to_string(),
            })?;
            Ok(Version::new(major, minor, 0))
        }
        _ => Err(VersionError::InvalidVersion {
            input: s.to_string(),
        }),
    }
}

/// Result of computing a hyphen-range upper bound from a partial.
enum PartialUpper {
    /// Full X.Y.Z given — closed interval (`<= v`).
    Closed(Version),
    /// Partial — open interval up to the next minor / major (`< v`).
    Open(Version),
}

/// Compute the upper bound for a hyphen range from a partial version.
/// "1.2.3" stays closed; "1.2" → < 1.3.0; "1" → < 2.0.0.
fn partial_upper_bound(s: &str) -> Result<PartialUpper, VersionError> {
    let s = s.trim();
    if Version::parse(s).is_ok() {
        return Ok(PartialUpper::Closed(Version::parse(s).unwrap()));
    }
    let parts: Vec<&str> = s.split('.').collect();
    match parts.len() {
        1 => {
            let major: u64 = parts[0].parse().map_err(|_| VersionError::InvalidVersion {
                input: s.to_string(),
            })?;
            Ok(PartialUpper::Open(Version::new(major + 1, 0, 0)))
        }
        2 => {
            let major: u64 = parts[0].parse().map_err(|_| VersionError::InvalidVersion {
                input: s.to_string(),
            })?;
            let minor: u64 = parts[1].parse().map_err(|_| VersionError::InvalidVersion {
                input: s.to_string(),
            })?;
            Ok(PartialUpper::Open(Version::new(major, minor + 1, 0)))
        }
        _ => Err(VersionError::InvalidVersion {
            input: s.to_string(),
        }),
    }
}

impl fmt::Display for VersionSet {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Any => write!(f, "*"),
            Self::Exact(v) => write!(f, "={}", v),
            Self::Caret(v) => write!(f, "^{}", v),
            Self::Tilde(v) => write!(f, "~{}", v),
            Self::Range { min, max } => match (min, max) {
                (Some(min), Some(max)) => {
                    write!(
                        f,
                        "{}{} {}{}",
                        if min.inclusive { ">=" } else { ">" },
                        min.version,
                        if max.inclusive { "<=" } else { "<" },
                        max.version
                    )
                }
                (Some(min), None) => {
                    write!(
                        f,
                        "{}{}",
                        if min.inclusive { ">=" } else { ">" },
                        min.version
                    )
                }
                (None, Some(max)) => {
                    write!(
                        f,
                        "{}{}",
                        if max.inclusive { "<=" } else { "<" },
                        max.version
                    )
                }
                (None, None) => write!(f, "*"),
            },
            Self::Union(sets) => {
                let parts: Vec<String> = sets.iter().map(|s| s.to_string()).collect();
                write!(f, "{}", parts.join(" || "))
            }
            Self::Intersection(sets) => {
                let parts: Vec<String> = sets.iter().map(|s| s.to_string()).collect();
                write!(f, "{}", parts.join(" "))
            }
            Self::PreRelease(tag) => write!(f, "pre:{}", tag),
        }
    }
}

impl FromStr for VersionSet {
    type Err = VersionError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        Self::parse(s)
    }
}

/// Helper function to create common version sets
pub mod version_sets {
    use super::*;

    /// Create a caret constraint (^version)
    pub fn caret(major: u64, minor: u64, patch: u64) -> VersionSet {
        VersionSet::caret(Version::new(major, minor, patch))
    }

    /// Create a tilde constraint (~version)
    pub fn tilde(major: u64, minor: u64, patch: u64) -> VersionSet {
        VersionSet::tilde(Version::new(major, minor, patch))
    }

    /// Create an exact constraint (=version)
    pub fn exact(major: u64, minor: u64, patch: u64) -> VersionSet {
        VersionSet::exact(Version::new(major, minor, patch))
    }

    /// Create a minimum version constraint (>=version)
    pub fn at_least(major: u64, minor: u64, patch: u64) -> VersionSet {
        VersionSet::range(
            Some(VersionBound::inclusive(Version::new(major, minor, patch))),
            None,
        )
    }

    /// Create a maximum version constraint (<version)
    pub fn below(major: u64, minor: u64, patch: u64) -> VersionSet {
        VersionSet::range(
            None,
            Some(VersionBound::exclusive(Version::new(major, minor, patch))),
        )
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_version_set_parsing() {
        // Any version
        assert_eq!(VersionSet::parse("*").unwrap(), VersionSet::Any);

        // Empty string should return error
        assert!(matches!(
            VersionSet::parse(""),
            Err(VersionError::EmptyConstraint)
        ));

        // Exact versions
        assert_eq!(
            VersionSet::parse("1.2.3").unwrap(),
            VersionSet::Exact(Version::new(1, 2, 3))
        );
        assert_eq!(
            VersionSet::parse("=1.2.3").unwrap(),
            VersionSet::Exact(Version::new(1, 2, 3))
        );

        // Caret constraints
        assert_eq!(
            VersionSet::parse("^1.2.3").unwrap(),
            VersionSet::Caret(Version::new(1, 2, 3))
        );

        // Tilde constraints
        assert_eq!(
            VersionSet::parse("~1.2.3").unwrap(),
            VersionSet::Tilde(Version::new(1, 2, 3))
        );

        // Range constraints
        assert_eq!(
            VersionSet::parse(">=1.0.0").unwrap(),
            VersionSet::Range {
                min: Some(VersionBound::inclusive(Version::new(1, 0, 0))),
                max: None
            }
        );
        assert_eq!(
            VersionSet::parse("<2.0.0").unwrap(),
            VersionSet::Range {
                min: None,
                max: Some(VersionBound::exclusive(Version::new(2, 0, 0)))
            }
        );
    }

    #[test]
    fn test_caret_constraint() {
        let constraint = VersionSet::parse("^1.2.3").unwrap();

        // Should satisfy versions >= 1.2.3 and < 2.0.0
        assert!(constraint.satisfies(&Version::new(1, 2, 3)));
        assert!(constraint.satisfies(&Version::new(1, 2, 4)));
        assert!(constraint.satisfies(&Version::new(1, 3, 0)));
        assert!(constraint.satisfies(&Version::new(1, 9, 9)));

        // Should not satisfy versions < 1.2.3 or >= 2.0.0
        assert!(!constraint.satisfies(&Version::new(1, 2, 2)));
        assert!(!constraint.satisfies(&Version::new(1, 1, 9)));
        assert!(!constraint.satisfies(&Version::new(2, 0, 0)));
        assert!(!constraint.satisfies(&Version::new(3, 0, 0)));
    }

    #[test]
    fn test_tilde_constraint() {
        let constraint = VersionSet::parse("~1.2.3").unwrap();

        // Should satisfy versions >= 1.2.3 and < 1.3.0
        assert!(constraint.satisfies(&Version::new(1, 2, 3)));
        assert!(constraint.satisfies(&Version::new(1, 2, 4)));
        assert!(constraint.satisfies(&Version::new(1, 2, 9)));

        // Should not satisfy versions < 1.2.3 or >= 1.3.0
        assert!(!constraint.satisfies(&Version::new(1, 2, 2)));
        assert!(!constraint.satisfies(&Version::new(1, 1, 9)));
        assert!(!constraint.satisfies(&Version::new(1, 3, 0)));
        assert!(!constraint.satisfies(&Version::new(2, 0, 0)));
    }

    #[test]
    fn test_compound_constraints() {
        let constraint = VersionSet::parse(">=1.0.0 <2.0.0").unwrap();

        match &constraint {
            VersionSet::Intersection(sets) => {
                assert_eq!(sets.len(), 2);
            }
            _ => panic!("Expected intersection constraint"),
        }

        // Should satisfy versions >= 1.0.0 and < 2.0.0
        assert!(constraint.satisfies(&Version::new(1, 0, 0)));
        assert!(constraint.satisfies(&Version::new(1, 5, 3)));
        assert!(constraint.satisfies(&Version::new(1, 9, 9)));

        // Should not satisfy versions < 1.0.0 or >= 2.0.0
        assert!(!constraint.satisfies(&Version::new(0, 9, 9)));
        assert!(!constraint.satisfies(&Version::new(2, 0, 0)));
    }

    #[test]
    fn test_union_constraints() {
        let constraint = VersionSet::parse("1.x || 2.x").unwrap();

        match &constraint {
            VersionSet::Union(sets) => {
                assert_eq!(sets.len(), 2);
            }
            _ => panic!("Expected union constraint"),
        }

        // Should satisfy versions in 1.x or 2.x
        assert!(constraint.satisfies(&Version::new(1, 0, 0)));
        assert!(constraint.satisfies(&Version::new(1, 5, 3)));
        assert!(constraint.satisfies(&Version::new(2, 0, 0)));
        assert!(constraint.satisfies(&Version::new(2, 9, 9)));

        // Should not satisfy versions outside 1.x and 2.x
        assert!(!constraint.satisfies(&Version::new(0, 9, 9)));
        assert!(!constraint.satisfies(&Version::new(3, 0, 0)));
    }

    #[test]
    fn test_x_ranges() {
        // Test 1.x constraint
        let constraint = VersionSet::parse("1.x").unwrap();
        assert!(constraint.satisfies(&Version::new(1, 0, 0)));
        assert!(constraint.satisfies(&Version::new(1, 9, 9)));
        assert!(!constraint.satisfies(&Version::new(2, 0, 0)));
        assert!(!constraint.satisfies(&Version::new(0, 9, 9)));

        // Test 1.2.x constraint
        let constraint = VersionSet::parse("1.2.x").unwrap();
        assert!(constraint.satisfies(&Version::new(1, 2, 0)));
        assert!(constraint.satisfies(&Version::new(1, 2, 9)));
        assert!(!constraint.satisfies(&Version::new(1, 3, 0)));
        assert!(!constraint.satisfies(&Version::new(2, 2, 0)));
    }

    #[test]
    fn test_version_filtering() {
        let versions = vec![
            Version::new(1, 0, 0),
            Version::new(1, 2, 3),
            Version::new(1, 5, 0),
            Version::new(2, 0, 0),
            Version::new(2, 1, 0),
        ];

        let constraint = VersionSet::parse("^1.2.0").unwrap();
        let filtered = constraint.filter_versions(&versions);

        assert_eq!(filtered.len(), 2);
        assert!(filtered.contains(&&Version::new(1, 2, 3)));
        assert!(filtered.contains(&&Version::new(1, 5, 0)));
    }

    #[test]
    fn test_best_version_selection() {
        let versions = vec![
            Version::new(1, 0, 0),
            Version::new(1, 2, 3),
            Version::new(1, 5, 0),
            Version::new(2, 0, 0),
        ];

        let constraint = VersionSet::parse("^1.0.0").unwrap();
        let best = constraint.select_best(&versions);

        assert_eq!(best, Some(&Version::new(1, 5, 0)));
    }

    #[test]
    fn test_version_set_display() {
        assert_eq!(VersionSet::Any.to_string(), "*");
        assert_eq!(
            VersionSet::exact(Version::new(1, 2, 3)).to_string(),
            "=1.2.3"
        );
        assert_eq!(
            VersionSet::caret(Version::new(1, 2, 3)).to_string(),
            "^1.2.3"
        );
        assert_eq!(
            VersionSet::tilde(Version::new(1, 2, 3)).to_string(),
            "~1.2.3"
        );
    }

    #[test]
    fn test_version_set_operations() {
        let a = VersionSet::parse(">=1.0.0").unwrap();
        let b = VersionSet::parse("<2.0.0").unwrap();

        let intersection = a.intersect(b);
        assert!(intersection.satisfies(&Version::new(1, 5, 0)));
        assert!(!intersection.satisfies(&Version::new(2, 0, 0)));
        assert!(!intersection.satisfies(&Version::new(0, 9, 0)));

        let c = VersionSet::parse("3.x").unwrap();
        let union = intersection.union(c);
        assert!(union.satisfies(&Version::new(1, 5, 0)));
        assert!(union.satisfies(&Version::new(3, 0, 0)));
        assert!(!union.satisfies(&Version::new(2, 0, 0)));
    }

    #[test]
    fn test_constraint_simplification_union() {
        // Test that Any in a union makes the whole thing Any
        let constraint = VersionSet::Union(vec![
            VersionSet::parse("^1.0.0").unwrap(),
            VersionSet::Any,
            VersionSet::parse("2.x").unwrap(),
        ])
        .simplify();
        assert_eq!(constraint, VersionSet::Any);

        // Test removing duplicates in union
        let constraint = VersionSet::Union(vec![
            VersionSet::parse("^1.2.0").unwrap(),
            VersionSet::parse("^1.2.0").unwrap(),
            VersionSet::parse("2.x").unwrap(),
        ])
        .simplify();

        match constraint {
            VersionSet::Union(sets) => {
                assert_eq!(sets.len(), 2); // Duplicates removed
            }
            _ => panic!("Expected simplified union"),
        }

        // Test subsumption in union (^1.0.0 subsumes ^1.2.0)
        let constraint = VersionSet::Union(vec![
            VersionSet::parse("^1.0.0").unwrap(),
            VersionSet::parse("^1.2.0").unwrap(),
        ])
        .simplify();

        // Should be simplified to just ^1.0.0 since it subsumes ^1.2.0
        assert_eq!(constraint, VersionSet::parse("^1.0.0").unwrap());
    }

    #[test]
    fn test_constraint_simplification_intersection() {
        // Test that Any constraints are removed in intersection
        let constraint = VersionSet::Intersection(vec![
            VersionSet::parse("^1.0.0").unwrap(),
            VersionSet::Any,
            VersionSet::parse("<2.0.0").unwrap(),
        ])
        .simplify();

        match constraint {
            VersionSet::Intersection(sets) => {
                assert_eq!(sets.len(), 2); // Any constraint removed
            }
            _ => panic!("Expected simplified intersection"),
        }

        // Test contradiction detection (multiple exact versions)
        let constraint = VersionSet::Intersection(vec![
            VersionSet::exact(Version::new(1, 2, 3)),
            VersionSet::exact(Version::new(1, 2, 4)),
        ])
        .simplify();

        // Should be a contradiction
        match constraint {
            VersionSet::Range {
                min: Some(min),
                max: Some(max),
            } => {
                // Should be an impossible range
                assert!(min.version > max.version);
            }
            _ => panic!("Expected contradiction constraint"),
        }

        // Test single constraint simplification
        let constraint =
            VersionSet::Intersection(vec![VersionSet::parse("^1.0.0").unwrap()]).simplify();

        assert_eq!(constraint, VersionSet::parse("^1.0.0").unwrap());
    }

    #[test]
    fn test_range_merging_union() {
        // Test merging overlapping ranges in union
        let constraint = VersionSet::Union(vec![
            VersionSet::parse(">=1.0.0").unwrap(),
            VersionSet::parse(">1.5.0").unwrap(),
        ])
        .simplify();

        // Should be simplified to just >=1.0.0 (less restrictive)
        assert_eq!(constraint, VersionSet::parse(">=1.0.0").unwrap());

        // Test merging adjacent ranges
        let range1 = VersionSet::Range {
            min: Some(VersionBound::inclusive(Version::new(1, 0, 0))),
            max: Some(VersionBound::exclusive(Version::new(2, 0, 0))),
        };
        let range2 = VersionSet::Range {
            min: Some(VersionBound::inclusive(Version::new(2, 0, 0))),
            max: Some(VersionBound::exclusive(Version::new(3, 0, 0))),
        };

        let constraint = VersionSet::Union(vec![range1, range2]).simplify();

        // Should be merged into a single range [1.0.0, 3.0.0)
        match constraint {
            VersionSet::Range {
                min: Some(min),
                max: Some(max),
            } => {
                assert_eq!(min.version, Version::new(1, 0, 0));
                assert!(min.inclusive);
                assert_eq!(max.version, Version::new(3, 0, 0));
                assert!(!max.inclusive);
            }
            _ => panic!("Expected merged range constraint"),
        }
    }

    #[test]
    fn test_range_merging_intersection() {
        // Test merging ranges in intersection (taking most restrictive bounds)
        let constraint = VersionSet::Intersection(vec![
            VersionSet::parse(">=1.0.0").unwrap(),
            VersionSet::parse(">1.5.0").unwrap(),
            VersionSet::parse("<3.0.0").unwrap(),
        ])
        .simplify();

        // Should be merged into >1.5.0 <3.0.0
        match constraint {
            VersionSet::Range {
                min: Some(min),
                max: Some(max),
            } => {
                assert_eq!(min.version, Version::new(1, 5, 0));
                assert!(!min.inclusive); // Most restrictive minimum
                assert_eq!(max.version, Version::new(3, 0, 0));
                assert!(!max.inclusive);
            }
            _ => panic!("Expected merged range constraint"),
        }

        // Test contradiction detection in range merging
        let constraint = VersionSet::Intersection(vec![
            VersionSet::parse(">2.0.0").unwrap(),
            VersionSet::parse("<1.0.0").unwrap(),
        ])
        .simplify();

        // Should detect contradiction (>2.0.0 AND <1.0.0 is impossible)
        match constraint {
            VersionSet::Range {
                min: Some(min),
                max: Some(max),
            } => {
                assert!(min.version > max.version); // Contradiction
            }
            _ => panic!("Expected contradiction constraint"),
        }
    }

    #[test]
    fn test_constraint_subsumption() {
        let any = VersionSet::Any;
        let caret = VersionSet::parse("^1.0.0").unwrap();
        let exact = VersionSet::parse("1.2.3").unwrap();
        let range = VersionSet::parse(">=1.0.0").unwrap();

        // Any subsumes everything
        assert!(any.constraint_subsumes(&any, &caret));
        assert!(any.constraint_subsumes(&any, &exact));
        assert!(any.constraint_subsumes(&any, &range));

        // Nothing (except Any) subsumes Any
        assert!(!caret.constraint_subsumes(&caret, &any));
        assert!(!exact.constraint_subsumes(&exact, &any));

        // Broader constraints subsume narrower ones
        assert!(range.constraint_subsumes(&range, &exact)); // >=1.0.0 subsumes exact 1.2.3
        assert!(caret.constraint_subsumes(&caret, &exact)); // ^1.0.0 subsumes exact 1.2.3 if compatible

        // Test caret subsumption
        let caret1 = VersionSet::parse("^1.0.0").unwrap();
        let caret2 = VersionSet::parse("^1.2.0").unwrap();
        assert!(caret1.constraint_subsumes(&caret1, &caret2)); // ^1.0.0 subsumes ^1.2.0

        // Test tilde subsumption
        let tilde1 = VersionSet::parse("~1.2.0").unwrap();
        let tilde2 = VersionSet::parse("~1.2.3").unwrap();
        assert!(tilde1.constraint_subsumes(&tilde1, &tilde2)); // ~1.2.0 subsumes ~1.2.3
    }

    #[test]
    fn test_enhanced_intersection_logic() {
        // Test caret constraint intersections
        let caret1 = VersionSet::parse("^1.2.0").unwrap();
        let caret2 = VersionSet::parse("^1.3.0").unwrap();
        assert!(caret1.intersects(&caret2)); // Same major version

        let caret3 = VersionSet::parse("^2.0.0").unwrap();
        assert!(!caret1.intersects(&caret3)); // Different major versions

        // Test tilde constraint intersections
        let tilde1 = VersionSet::parse("~1.2.3").unwrap();
        let tilde2 = VersionSet::parse("~1.2.5").unwrap();
        assert!(tilde1.intersects(&tilde2)); // Same major.minor

        let tilde3 = VersionSet::parse("~1.3.0").unwrap();
        assert!(!tilde1.intersects(&tilde3)); // Different minor versions

        // Test range intersections
        let range1 = VersionSet::parse(">=1.0.0").unwrap();
        let range2 = VersionSet::parse("<2.0.0").unwrap();
        assert!(range1.intersects(&range2)); // Overlapping ranges

        let range3 = VersionSet::parse(">=3.0.0").unwrap();
        assert!(!range2.intersects(&range3)); // Non-overlapping ranges

        // Test exact version intersections
        let exact1 = VersionSet::exact(Version::new(1, 2, 3));
        let exact2 = VersionSet::exact(Version::new(1, 2, 3));
        let exact3 = VersionSet::exact(Version::new(1, 2, 4));

        assert!(exact1.intersects(&exact2)); // Same exact version
        assert!(!exact1.intersects(&exact3)); // Different exact versions

        assert!(range1.intersects(&exact1)); // Range contains exact version
        assert!(caret1.intersects(&exact1)); // Caret constraint contains exact
        // version
    }

    #[test]
    fn test_operator_with_spaces() {
        // The case that broke express install: safer-buffer publishes
        // ">= 2.1.2 < 3.0.0" with spaces between operators and versions.
        let c = VersionSet::parse(">= 2.1.2 < 3.0.0").unwrap();
        assert!(c.satisfies(&Version::new(2, 1, 2)));
        assert!(c.satisfies(&Version::new(2, 5, 0)));
        assert!(!c.satisfies(&Version::new(2, 1, 1)));
        assert!(!c.satisfies(&Version::new(3, 0, 0)));

        // Tabs and multi-space are equivalent.
        let c = VersionSet::parse(">=  2.0.0  <   3.0.0").unwrap();
        assert!(c.satisfies(&Version::new(2, 0, 0)));
        assert!(!c.satisfies(&Version::new(3, 0, 0)));

        // Operator-only space tolerance also applies to ^ and ~.
        assert_eq!(
            VersionSet::parse("^ 1.2.3").unwrap(),
            VersionSet::parse("^1.2.3").unwrap()
        );
        assert_eq!(
            VersionSet::parse("~ 1.2.3").unwrap(),
            VersionSet::parse("~1.2.3").unwrap()
        );
    }

    #[test]
    fn test_hyphen_range() {
        // Full versions on both sides → closed interval.
        let c = VersionSet::parse("1.2.3 - 2.3.4").unwrap();
        assert!(c.satisfies(&Version::new(1, 2, 3)));
        assert!(c.satisfies(&Version::new(2, 0, 0)));
        assert!(c.satisfies(&Version::new(2, 3, 4)));
        assert!(!c.satisfies(&Version::new(1, 2, 2)));
        assert!(!c.satisfies(&Version::new(2, 3, 5)));

        // Partial high bound: "1.2 - 2.3" → ">=1.2.0 <2.4.0"
        let c = VersionSet::parse("1.2 - 2.3").unwrap();
        assert!(c.satisfies(&Version::new(1, 2, 0)));
        assert!(c.satisfies(&Version::new(2, 3, 99)));
        assert!(!c.satisfies(&Version::new(2, 4, 0)));

        // Major-only: "1 - 2" → ">=1.0.0 <3.0.0"
        let c = VersionSet::parse("1 - 2").unwrap();
        assert!(c.satisfies(&Version::new(1, 0, 0)));
        assert!(c.satisfies(&Version::new(2, 99, 99)));
        assert!(!c.satisfies(&Version::new(3, 0, 0)));

        // A bare prerelease should NOT be parsed as a hyphen range.
        let v = VersionSet::parse("1.0.0-beta.1").unwrap();
        assert!(matches!(v, VersionSet::Exact(_)));
    }

    #[test]
    fn test_partial_version_constraints() {
        // ^1 → ^1.0.0 → >=1.0.0 <2.0.0
        let c = VersionSet::parse("^1").unwrap();
        assert!(c.satisfies(&Version::new(1, 0, 0)));
        assert!(c.satisfies(&Version::new(1, 9, 9)));
        assert!(!c.satisfies(&Version::new(2, 0, 0)));

        // ~1.2 → ~1.2.0 → >=1.2.0 <1.3.0
        let c = VersionSet::parse("~1.2").unwrap();
        assert!(c.satisfies(&Version::new(1, 2, 0)));
        assert!(c.satisfies(&Version::new(1, 2, 9)));
        assert!(!c.satisfies(&Version::new(1, 3, 0)));

        // Bare partial "1.2" treated as x-range "1.2.x".
        let c = VersionSet::parse("1.2").unwrap();
        assert!(c.satisfies(&Version::new(1, 2, 0)));
        assert!(c.satisfies(&Version::new(1, 2, 9)));
        assert!(!c.satisfies(&Version::new(1, 3, 0)));

        // Bare "1" → 1.x.x
        let c = VersionSet::parse("1").unwrap();
        assert!(c.satisfies(&Version::new(1, 0, 0)));
        assert!(c.satisfies(&Version::new(1, 99, 99)));
        assert!(!c.satisfies(&Version::new(2, 0, 0)));

        // >=1 means >=1.0.0.
        let c = VersionSet::parse(">=1").unwrap();
        assert!(c.satisfies(&Version::new(1, 0, 0)));
        assert!(c.satisfies(&Version::new(99, 0, 0)));
        assert!(!c.satisfies(&Version::new(0, 99, 99)));
    }

    #[test]
    fn test_caret_zero_x_semantics() {
        // ^0.2.3 → >=0.2.3 <0.3.0 (npm semantics for 0.x)
        let c = VersionSet::parse("^0.2.3").unwrap();
        assert!(c.satisfies(&Version::new(0, 2, 3)));
        assert!(c.satisfies(&Version::new(0, 2, 9)));
        assert!(
            !c.satisfies(&Version::new(0, 3, 0)),
            "^0.2.3 must reject 0.3.0 (a minor bump); was a real bug pre-fix"
        );
        assert!(!c.satisfies(&Version::new(0, 2, 2)));

        // ^0.0.3 → exact 0.0.3 (npm semantics for 0.0.x)
        let c = VersionSet::parse("^0.0.3").unwrap();
        assert!(c.satisfies(&Version::new(0, 0, 3)));
        assert!(
            !c.satisfies(&Version::new(0, 0, 4)),
            "^0.0.3 must reject 0.0.4 (a patch bump); was a real bug pre-fix"
        );
        assert!(!c.satisfies(&Version::new(0, 0, 2)));

        // ^1.2.3 retains the original semantics.
        let c = VersionSet::parse("^1.2.3").unwrap();
        assert!(c.satisfies(&Version::new(1, 9, 9)));
        assert!(!c.satisfies(&Version::new(2, 0, 0)));
    }

    #[test]
    fn test_dist_tags_accepted() {
        for tag in ["latest", "next", "beta", "alpha", "rc", "canary"] {
            let c = VersionSet::parse(tag).unwrap();
            // We accept dist tags as Any; the registry resolves the real version.
            assert_eq!(c, VersionSet::Any, "tag {} should parse", tag);
        }
    }

    #[test]
    fn test_complex_simplification_scenarios() {
        // Test complex union simplification
        let complex_union = VersionSet::Union(vec![
            VersionSet::parse("^1.0.0").unwrap(),
            VersionSet::parse("^1.2.0").unwrap(), // Should be subsumed by ^1.0.0
            VersionSet::parse(">=2.0.0").unwrap(),
            VersionSet::parse("2.x").unwrap(), // Should be subsumed by >=2.0.0
            VersionSet::exact(Version::new(3, 0, 0)),
        ])
        .simplify();

        match complex_union {
            VersionSet::Union(sets) => {
                // Should have reduced redundant constraints
                assert!(sets.len() <= 3); // At most ^1.0.0, >=2.0.0, =3.0.0
                println!("Simplified union has {} constraints", sets.len());
                for set in &sets {
                    println!("  - {}", set);
                }
            }
            _ => panic!("Expected union constraint"),
        }

        // Test complex intersection simplification
        let complex_intersection = VersionSet::Intersection(vec![
            VersionSet::parse(">=1.0.0").unwrap(),
            VersionSet::parse(">1.5.0").unwrap(), // More restrictive
            VersionSet::parse("<3.0.0").unwrap(),
            VersionSet::parse("<=2.5.0").unwrap(), // More restrictive
            VersionSet::Any,                       // Should be removed
        ])
        .simplify();

        // Should be simplified to >1.5.0 <=2.5.0
        match complex_intersection {
            VersionSet::Range {
                min: Some(min),
                max: Some(max),
            } => {
                assert_eq!(min.version, Version::new(1, 5, 0));
                assert!(!min.inclusive); // >1.5.0
                assert_eq!(max.version, Version::new(2, 5, 0));
                assert!(max.inclusive); // <=2.5.0
            }
            _ => {
                panic!(
                    "Expected single merged range constraint, got: {:?}",
                    complex_intersection
                );
            }
        }
    }
}

#[cfg(test)]
mod proptests {
    //! Property-based tests for [`VersionSet`] semantics.
    //!
    //! Versions are generated with small numeric components (0..10
    //! per field) so the satisfaction-profile checks below cover a
    //! tractable sample of the value space.

    use super::*;
    use proptest::prelude::*;

    /// Generate a "small" semver-style Version. Major/minor/patch
    /// each in 0..10 — large enough to exercise the three caret
    /// regimes for `^0.x.y`, small enough that `prop_assert!` loops
    /// over a "sample of versions" stay tractable per case.
    fn small_version() -> impl Strategy<Value = Version> {
        (0u64..10, 0u64..10, 0u64..10).prop_map(|(a, b, c)| Version::new(a, b, c))
    }

    /// A non-recursive `VersionSet` leaf. Excludes `Union` /
    /// `Intersection` so the higher-level properties can wrap these
    /// without explosion.
    fn leaf_set() -> impl Strategy<Value = VersionSet> {
        prop_oneof![
            Just(VersionSet::Any),
            small_version().prop_map(VersionSet::Exact),
            small_version().prop_map(VersionSet::Caret),
            small_version().prop_map(VersionSet::Tilde),
            (
                small_version(),
                small_version(),
                any::<bool>(),
                any::<bool>()
            )
                .prop_map(|(lo, hi, lo_inclusive, hi_inclusive)| {
                    // Order the bounds so min <= max; ranges with min > max
                    // are technically representable but uninteresting (no
                    // version satisfies them) and would clutter shrinks.
                    let (lo, hi) = if lo <= hi { (lo, hi) } else { (hi, lo) };
                    VersionSet::Range {
                        min: Some(VersionBound {
                            version: lo,
                            inclusive: lo_inclusive,
                        }),
                        max: Some(VersionBound {
                            version: hi,
                            inclusive: hi_inclusive,
                        }),
                    }
                },),
        ]
    }

    /// A small "probe set" of versions used to compare satisfaction
    /// profiles of two `VersionSet`s. Includes 0.0.0, edge cases at
    /// each axis, and a sprinkle of mid-range values.
    fn probe_versions() -> Vec<Version> {
        let mut out = Vec::with_capacity(40);
        for major in [0u64, 1, 2, 5, 9] {
            for minor in [0u64, 1, 5, 9] {
                for patch in [0u64, 5, 9] {
                    out.push(Version::new(major, minor, patch));
                }
            }
        }
        out
    }

    proptest! {
        /// `Any` accepts every version, no matter what.
        #[test]
        fn any_satisfies_everything(v in small_version()) {
            prop_assert!(VersionSet::Any.satisfies(&v));
        }

        /// `Exact(v).satisfies(w) ⟺ v == w`.
        #[test]
        fn exact_iff_equal(v in small_version(), w in small_version()) {
            prop_assert_eq!(VersionSet::Exact(v.clone()).satisfies(&w), v == w);
        }

        /// Caret semantics by regime:
        ///   `^X.Y.Z` with X>0 ⇒ `>=X.Y.Z <(X+1).0.0`
        ///   `^0.Y.Z` with Y>0 ⇒ `>=0.Y.Z <0.(Y+1).0`
        ///   `^0.0.Z`          ⇒ exact 0.0.Z
        ///
        /// All three regimes are easy to break in a naïve refactor;
        /// this property checks each one against the spec.
        #[test]
        fn caret_three_regimes(base in small_version(), probe in small_version()) {
            let set = VersionSet::Caret(base.clone());
            let actual = set.satisfies(&probe);
            let expected = if base.major > 0 {
                probe >= base
                    && probe < Version::new(base.major + 1, 0, 0)
            } else if base.minor > 0 {
                probe >= base
                    && probe < Version::new(0, base.minor + 1, 0)
            } else {
                probe == base
            };
            prop_assert_eq!(actual, expected, "caret({}) vs {}", base, probe);
        }

        /// Tilde semantics: `~X.Y.Z` ⇒ `>=X.Y.Z <X.(Y+1).0`.
        #[test]
        fn tilde_one_regime(base in small_version(), probe in small_version()) {
            let set = VersionSet::Tilde(base.clone());
            let actual = set.satisfies(&probe);
            let expected =
                probe >= base && probe < Version::new(base.major, base.minor + 1, 0);
            prop_assert_eq!(actual, expected);
        }

        /// `Union([a, b]).satisfies(v) ≡ a.satisfies(v) || b.satisfies(v)`.
        /// The satisfaction-profile-comparison form: across a probe
        /// set of versions, the two predicates agree pointwise.
        #[test]
        fn union_distributes_over_satisfies(a in leaf_set(), b in leaf_set()) {
            let combined = VersionSet::Union(vec![a.clone(), b.clone()]);
            for v in probe_versions() {
                let combined_says = combined.satisfies(&v);
                let or_says = a.satisfies(&v) || b.satisfies(&v);
                prop_assert_eq!(
                    combined_says,
                    or_says,
                    "Union disagrees with OR at {} (a={:?}, b={:?})",
                    v, a, b,
                );
            }
        }

        /// `Intersection([a, b]).satisfies(v) ≡ a.satisfies(v) && b.satisfies(v)`.
        #[test]
        fn intersection_distributes_over_satisfies(a in leaf_set(), b in leaf_set()) {
            let combined = VersionSet::Intersection(vec![a.clone(), b.clone()]);
            for v in probe_versions() {
                let combined_says = combined.satisfies(&v);
                let and_says = a.satisfies(&v) && b.satisfies(&v);
                prop_assert_eq!(
                    combined_says,
                    and_says,
                    "Intersection disagrees with AND at {} (a={:?}, b={:?})",
                    v, a, b,
                );
            }
        }

        /// Union is commutative under satisfaction: swapping the
        /// operands doesn't change which versions are accepted.
        #[test]
        fn union_is_commutative(a in leaf_set(), b in leaf_set()) {
            let ab = VersionSet::Union(vec![a.clone(), b.clone()]);
            let ba = VersionSet::Union(vec![b.clone(), a.clone()]);
            for v in probe_versions() {
                prop_assert_eq!(ab.satisfies(&v), ba.satisfies(&v));
            }
        }

        /// Display + parse should round-trip semantically: the
        /// re-parsed set has the same satisfaction profile across
        /// the probe set as the original. (Textual round-trip is
        /// stronger than what we need and would force the display
        /// form to be a canonical normal form.)
        #[test]
        fn display_parse_roundtrip_preserves_semantics(set in leaf_set()) {
            let rendered = set.to_string();
            let reparsed = match VersionSet::parse(&rendered) {
                Ok(s) => s,
                Err(_) => {
                    // Some rendered forms are intentionally
                    // non-parseable inputs (e.g., the `*` for `Any`
                    // parses but some exotic Range displays may not
                    // round-trip exactly). Skip those rather than
                    // fail — the parser surface is independently
                    // covered by the unit tests.
                    return Ok(());
                }
            };
            for v in probe_versions() {
                prop_assert_eq!(
                    set.satisfies(&v),
                    reparsed.satisfies(&v),
                    "round-trip changed semantics at {}: original {:?} → rendered {:?} → reparsed {:?}",
                    v, set, rendered, reparsed,
                );
            }
        }
    }
}