Stream: t-cargo/PubGrub

Topic: pre-releases


view this post on Zulip Matthieu Pizenberg (Jul 17 2021 at 22:49):

I have some thoughts regarding pre-release versions, and I'll just throw them out here, see what you think.

When I tried the Interval approach (https://github.com/pubgrub-rs/pubgrub/pull/99), you identified a problem with the contains function.
It not being "pure" by potentially returning different results depending on the interpretation of bounds (is there a pre-release marker in a bound?) can mess up with backtracking.
That problem logically arises because we are not being "mathematically strict" (hand waving) about the definition of our sets of versions.
I was mixing the set of pre-releases and the set of normal versions into one unique ordered set of versions, which is not correct with the semantics of the contains function.
If I remember well, in your range trait approach, you solved that problem by duplicating the normal versions, and pre-release versions, and duplicating the code for contains and intersection.

The thing I was trying to solve with the Interval approach was preventing users of pubgrub to have to implement their own intersection function.
But by letting them implement contains, I introduced a flaw.

The question I'm now asking myself is the following.
Can we have a system, where contains and intersection are rigorously implemented by ourselves, stricly based on some kind of interval bounds, but where our space for versions is not 1-dimensional, but can be multi-dimensional, like 1D for normal versions and 1D for pre-release versions.
We can still have a 1D approximation for humans, but just for ease of notation.
So for example ">= 1.0-alpha2" would actually be the 2D specification { normal: ">= 1.0", pre: ">= 1.0-alpha2" }.
And ">= 2.0" would be { normal: ">= 2.0", pre: empty }.

For contains, we could easily make a canonical implementation as follows.

fn contains(x,set) { singleton(x).intersection(set) == singleton(x) }

For intersection to be implementable by ourselves, we need to be able to access each parallel dimension.
But each dimension may have versions of a different type so I don't know how we could define such things.

pub struct MultiDimRange<const D: usize> {
    dimensions: [Range<dyn Interval>; D]
}

Is there a way to correctly write the struct above?

Alternatively, we could make concrete 2D, 3D etc implementations.
Constraints semantics could easily reach 3D with things like normal + pre-release + long-term-support for example, where normal releases are to LTS releases what pre-releases are to normal releases.
So I would not feel very comfortable manually writing a few and deciding when to stop.

Anyway, that was my random thoughts of today on the pre-release subject.

view this post on Zulip Eh2406 (Jul 18 2021 at 18:45):

That all makes sense.

If I remember well, in your range trait approach, you solved that problem by duplicating the normal versions, and pre-release versions, and duplicating the code for contains and intersection.

Theoretically Yes. But in practice the implementation was just a wrapper around two Pubgrub::Ranges, so the implementation was just "delegate to the correct one". link
It is probably worth looking into generalizations of that. Like a TwoRange who's new(l: RS, r: RS, is_r: Fn(&RS::VERSION) -> bool) where RS: RangeSet. Or a EitherRange who's that can have a VERSION = Either from the Either crate.

If it is true that is possible to build composable wrappers that implement RangeSet if there arguments do, and we can provide the most common building blocks in PubGrub, then I am not as bothered by how tricky it is to imple RangeSet by hand.

view this post on Zulip Eh2406 (Jul 19 2021 at 02:37):

So I gave it a try, and here is a POC of a 2D using Either:

// use https://docs.rs/either/1.6.1/either/ next
#[derive(Debug, PartialEq, Eq, Clone, PartialOrd, Ord)]
pub enum Either<L, R> {
    Left(L),
    Right(R),
}

impl<L, R> std::fmt::Display for Either<L, R> {
    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
        "TODO".fmt(formatter)
    }
}

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct EitherSet<L, R> {
    left: L,
    right: R,
}

impl<L, R> std::fmt::Display for EitherSet<L, R> {
    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
        "TODO".fmt(formatter)
    }
}

impl<L, R> RangeSet for EitherSet<L, R>
where
    L: RangeSet,
    R: RangeSet,
{
    type VERSION = Either<L::VERSION, R::VERSION>;

    fn none() -> Self {
        Self {
            left: L::none(),
            right: R::none(),
        }
    }

    fn any() -> Self {
        Self {
            left: L::any(),
            right: R::any(),
        }
    }

    fn exact(v: impl Into<Self::VERSION>) -> Self {
        match v.into() {
            Either::Left(v) => Self {
                left: L::exact(v),
                right: R::none(),
            },
            Either::Right(v) => Self {
                left: L::none(),
                right: R::exact(v),
            },
        }
    }

    fn negate(&self) -> Self {
        Self {
            left: self.left.negate(),
            right: self.right.negate(),
        }
    }

    fn intersection(&self, other: &Self) -> Self {
        Self {
            left: self.left.intersection(&other.left),
            right: self.right.intersection(&other.right),
        }
    }

    /// Check if a range contains a given version.
    fn contains(&self, version: &Self::VERSION) -> bool {
        match version {
            Either::Left(v) => self.left.contains(v),
            Either::Right(v) => self.right.contains(v),
        }
    }
}

One can build a 3D using EitherSet<A, EitherSet<B, C>>, but I don't know how good the ergonomics are.

view this post on Zulip Matthieu Pizenberg (Jul 19 2021 at 07:54):

Interesting, that's relatively straightforward indeed, and I wonder if it could be even shorter with the Interval API and the right amount of automatically derived impls

view this post on Zulip Matthieu Pizenberg (Jul 19 2021 at 07:55):

I'll leave that thought for later since I'll still have to fix the bugs in the Interval approach first


Last updated: Oct 21 2021 at 20:03 UTC