## Stream: t-cargo/PubGrub

### Topic: pre-releases

#### 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.

#### 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.

#### 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.

#### 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

#### 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