Pubgrub draft RangeSet trait for Semver

#Pubgrub draft RangeSet trait for Semver

This is still a proof of concept. I don't think it has all the corner cases correct, but it demonstrates what's possible.

Cargo.toml

[package]
name = "semver-pubgrub"
version = "0.1.0"
edition = "2018"

[dependencies]
rayon="1"
semver = "1"
crates-index = "0.16"
pubgrub = { git = "https://github.com/pubgrub-rs/pubgrub", branch = "range-trait" }

doubleSet.rs

use std::marker::PhantomData;

use pubgrub::range::RangeSet;

trait Differentiater<V> {
    fn differentiate(_: &V) -> bool;
}

#[derive(PartialEq, Eq, PartialOrd, Ord, Debug)]
struct DoubleSet<V, F> {
    cons: [V; 2],
    differentiate: PhantomData<F>,
}

impl<V: Clone, F> Clone for DoubleSet<V, F> {
    fn clone(&self) -> Self {
        Self {
            cons: self.cons.clone(),
            differentiate: PhantomData,
        }
    }
}

impl<V, F> std::fmt::Display for DoubleSet<V, F> {
    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
        std::fmt::Display::fmt(&"TODO", formatter)
    }
}

impl<V, F> DoubleSet<V, F> {
    pub fn new(cons: [V; 2]) -> Self {
        Self {
            cons,
            differentiate: PhantomData,
        }
    }
}

impl<V, F> RangeSet for DoubleSet<V, F>
where
    F: Differentiater<V::VERSION> + Eq + std::fmt::Debug,
    V: RangeSet + Ord + From<V>,
{
    type VERSION = V::VERSION;

    fn none() -> Self {
        Self {
            cons: [V::none(), V::none()],
            differentiate: PhantomData,
        }
    }

    fn any() -> Self {
        Self {
            cons: [V::any(), V::any()],
            differentiate: PhantomData,
        }
    }

    fn exact(v: impl Into<Self::VERSION>) -> Self {
        let v = v.into();
        if F::differentiate(&v) {
            Self {
                cons: [V::none(), V::exact(v)],
                differentiate: PhantomData,
            }
        } else {
            Self {
                cons: [V::exact(v), V::none()],
                differentiate: PhantomData,
            }
        }
    }

    fn negate(&self) -> Self {
        Self {
            cons: [self.cons[0].negate(), self.cons[1].negate()],
            differentiate: PhantomData,
        }
    }

    fn intersection(&self, other: &Self) -> Self {
        Self {
            cons: [
                self.cons[0].intersection(&other.cons[0]),
                self.cons[1].intersection(&other.cons[1]),
            ],
            differentiate: PhantomData,
        }
    }
}

main.rs

use std::collections::{BTreeSet, HashSet};

use pubgrub::{
    range::{Range, RangeSet},
    version::RangeVersion,
};
use rayon::prelude::*;
use semver::{BuildMetadata, Comparator, Prerelease, Version, VersionReq};

/// to get around the orphan rule
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
struct MyVersion(Version);

impl std::fmt::Display for MyVersion {
    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
        self.0.fmt(formatter)
    }
}

impl RangeVersion for MyVersion {
    fn lowest() -> Self {
        MyVersion(Version {
            major: 0,
            minor: 0,
            patch: 0,
            pre: Prerelease::new("0").unwrap(),
            build: semver::BuildMetadata::EMPTY,
        })
    }

    fn bump(&self) -> Self {
        self.bump_build()
    }
}

impl MyVersion {
    fn bump_major(&self) -> Self {
        MyVersion(Version {
            major: self.0.major + 1,
            minor: 0,
            patch: 0,
            pre: Prerelease::EMPTY,
            build: BuildMetadata::EMPTY,
        })
    }

    fn bump_minor(&self) -> Self {
        MyVersion(Version {
            major: self.0.major,
            minor: self.0.minor + 1,
            patch: 0,
            pre: Prerelease::EMPTY,
            build: BuildMetadata::EMPTY,
        })
    }

    fn bump_patch(&self) -> Self {
        MyVersion(Version {
            major: self.0.major,
            minor: self.0.minor,
            patch: self.0.patch + 1,
            pre: Prerelease::EMPTY,
            build: BuildMetadata::EMPTY,
        })
    }

    fn bump_pre(&self) -> Self {
        MyVersion(Version {
            major: self.0.major,
            minor: self.0.minor,
            patch: self.0.patch,
            pre: if self.0.pre.is_empty() {
                Prerelease::new("0").unwrap()
            } else {
                Prerelease::new(&(self.0.pre.to_string() + ".0")).unwrap()
            },
            build: BuildMetadata::EMPTY,
        })
    }

    fn bump_build(&self) -> Self {
        MyVersion(Version {
            major: self.0.major,
            minor: self.0.minor,
            patch: self.0.patch,
            pre: self.0.pre.clone(),
            build: if self.0.build.is_empty() {
                BuildMetadata::new("0").unwrap()
            } else {
                BuildMetadata::new(&(self.0.build.to_string() + ".0")).unwrap()
            },
        })
    }
}

#[derive(Debug, PartialEq, Eq, Clone)]
struct SemverPubgrub {
    norml: Range<MyVersion>,
    pre: Range<MyVersion>,
}

impl std::fmt::Display for SemverPubgrub {
    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
        "SemverPubgrub { norml: ".fmt(formatter)?;
        self.norml.fmt(formatter)?;
        ", pre: ".fmt(formatter)?;
        self.pre.fmt(formatter)?;
        " } ".fmt(formatter)
    }
}

impl RangeSet for SemverPubgrub {
    type VERSION = MyVersion;

    fn none() -> Self {
        SemverPubgrub {
            norml: Range::none(),
            pre: Range::none(),
        }
    }

    fn any() -> Self {
        SemverPubgrub {
            norml: Range::any(),
            pre: Range::any(),
        }
    }

    fn exact(v: impl Into<Self::VERSION>) -> Self {
        let ver: Self::VERSION = v.into();
        if ver.0.pre.is_empty() {
            SemverPubgrub {
                norml: Range::exact(ver),
                pre: Range::none(),
            }
        } else {
            SemverPubgrub {
                norml: Range::none(),
                pre: Range::exact(ver),
            }
        }
    }

    fn negate(&self) -> Self {
        SemverPubgrub {
            norml: self.norml.negate(),
            pre: self.pre.negate(),
        }
    }

    fn intersection(&self, other: &Self) -> Self {
        SemverPubgrub {
            norml: self.norml.intersection(&other.norml),
            pre: self.pre.intersection(&other.pre),
        }
    }

    /// Check if a range contains a given version.
    fn contains(&self, version: &Self::VERSION) -> bool {
        if version.0.pre.is_empty() {
            self.norml.contains(version)
        } else {
            self.pre.contains(version)
        }
    }
}

fn norml_from_comparator(com: &Comparator) -> Range<MyVersion> {
    use semver::Op::*;
    let ver = MyVersion(Version {
        major: com.major,
        minor: com.minor.unwrap_or(0),
        patch: com.patch.unwrap_or(0),
        pre: com.pre.clone(),
        build: BuildMetadata::EMPTY,
    });
    match &com.op {
        Exact | Wildcard => {
            let next_ver = if com.minor.is_none() {
                ver.bump_major()
            } else if com.patch.is_none() {
                ver.bump_minor()
            } else if com.pre == Prerelease::EMPTY {
                ver.bump_patch()
            } else {
                ver.bump_pre()
            };
            Range::between(ver, next_ver)
        }
        Greater => {
            let next_ver = if com.minor.is_none() {
                ver.bump_major()
            } else if com.patch.is_none() {
                ver.bump_minor()
            } else if com.pre == Prerelease::EMPTY {
                ver.bump_patch()
            } else {
                ver.bump_pre()
            };
            Range::higher_than(next_ver)
        }
        GreaterEq => Range::higher_than(ver),
        Less => Range::strictly_lower_than(ver),
        LessEq => {
            if com.minor.is_none() {
                Range::strictly_lower_than(ver.bump_major())
            } else if com.patch.is_none() {
                Range::strictly_lower_than(ver.bump_minor())
            } else if com.pre == Prerelease::EMPTY {
                Range::strictly_lower_than(ver.bump_patch())
            } else {
                Range::strictly_lower_than(ver.bump_pre())
            }
        }
        Tilde => {
            let next_ver = if com.minor.is_none() {
                ver.bump_major()
            } else {
                ver.bump_minor()
            };
            Range::between(ver, next_ver)
        }
        Caret => {
            let next_ver = match (com.major, &com.minor, &com.patch) {
                (0, Some(0), Some(_)) => ver.bump_patch(),
                (0, Some(_), _) => ver.bump_minor(),
                _ => ver.bump_major(),
            };
            Range::between(ver, next_ver)
        }
        _ => todo!(),
    }
}

fn pre_from_comparator(com: &Comparator) -> Range<MyVersion> {
    if com.pre == Prerelease::EMPTY {
        return Range::none();
    }
    let next_ver = MyVersion(Version {
        major: com.major,
        minor: com.minor.unwrap(),
        patch: com.patch.unwrap(),
        pre: Prerelease::EMPTY,
        build: BuildMetadata::EMPTY,
    });
    let ver = next_ver.bump_pre();
    Range::between(ver, next_ver)
}

impl Into<SemverPubgrub> for &VersionReq {
    fn into(self) -> SemverPubgrub {
        match self.comparators.as_slice() {
            [] => SemverPubgrub {
                norml: Range::any(),
                pre: Range::none(),
            },
            [c0, cn @ ..] => {
                let mut norml = norml_from_comparator(c0);
                let mut pre = pre_from_comparator(c0);
                for c in cn {
                    norml = norml.intersection(&norml_from_comparator(c));
                    pre = pre.union(&pre_from_comparator(c));
                }
                pre = norml.intersection(&pre);
                SemverPubgrub { norml, pre }
            }
        }
    }
}

fn main() {
    let index = crates_index::BareIndex::new_cargo_default();
    let index = index.open_or_clone().unwrap();
    let mut versions = BTreeSet::new();
    let mut requirements = HashSet::new();
    for crt in index.crates() {
        for ver in crt.versions() {
            if let Ok(ver) = Version::parse(ver.version()) {
                versions.insert(MyVersion(ver));
            }
            for dep in ver.dependencies() {
                if let Ok(req) = VersionReq::parse(dep.requirement()) {
                    requirements.insert(req);
                }
            }
        }
    }

    assert!(&MyVersion::lowest() <= versions.iter().next().unwrap());
    for vers in versions.iter().collect::<Vec<_>>().windows(2) {
        assert!(vers[0] < &vers[0].bump());
        assert!(&vers[0].bump() <= vers[1]);
    }

    let cout = std::sync::atomic::AtomicU64::new(0);
    let start_time = std::time::Instant::now();
    requirements.par_iter().for_each(|req| {
        let thing = cout.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
        if thing % 10 == 0 && thing > 0 {
            let time = std::time::Instant::now().duration_since(start_time).as_secs_f32();
            println!(
                "Done with {} / {} in {:.2} so {:.2} left",
                thing,
                requirements.len(),
                time,
                (requirements.len() as f32 - thing as f32) * (time / thing as f32)
            );
        }
        let pver: SemverPubgrub = req.into();
        for ver in &versions {
            assert_eq!(req.matches(&ver.0), pver.contains(ver));
        }
        let neg = pver.negate();
        for ver in &versions {
            assert_eq!(!req.matches(&ver.0), neg.contains(ver));
        }
        for req2 in &requirements {
            let pver2: SemverPubgrub = req2.into();
            let inter: SemverPubgrub = pver2.intersection(&pver);
            for ver in &versions {
                assert_eq!(
                    req.matches(&ver.0) && req2.matches(&ver.0),
                    inter.contains(ver)
                );
            }
        }
    })
}