Stream: t-cargo/PubGrub

Topic: A Range trate


view this post on Zulip Eh2406 (Nov 23 2020 at 16:02):

In pubgrub#49 and advanced_dependency_providers#3 we've been discussing making a Range trate in addition to the Range type that we use now. When should we give this a try? Clearly before pubgrub#59 lands, that change needs to be compatible with a Range trate. Do you want to deal with a PR now or later in the week or after a perf focused 2.1 release or what are you thinking?

view this post on Zulip Eh2406 (Nov 23 2020 at 16:21):

I think getting this done needs to be done before talking to semver maintainers about how to proceed with integration. Can they add the apis we need, a big ask as semver is not getting much maintenance. Or do we fork. Or do we write our own. Or something else. But we need to know exactly what API's we need before we can start that discussion.

view this post on Zulip Matthieu Pizenberg (Nov 23 2020 at 20:53):

Experimenting with range should happen before 59 yes, and it needs quite some work in my opinion. Both to design it and to prove it's actually useful by making examples that take advantage of it and would have been impossible or too cumbersome to implement without. I don't think there is a need for a perf focused release, we can just roll perf improvements into other releases.

view this post on Zulip Matthieu Pizenberg (Nov 23 2020 at 20:55):

That being said, I'll mostly be in reader mode for a few weeks and not make much progress on my own so if you want to prioritize your work differently of course do as you prefer

view this post on Zulip Matthieu Pizenberg (Nov 23 2020 at 20:58):

a big ask as semver is not getting much maintenance

Agreed, for the few things I've done last weekend I've forked the repo. We should take our time for this and make progress without asking for their attention as long as we can.

view this post on Zulip Eh2406 (Nov 23 2020 at 22:42):

I'll mostly be in reader mode for a few weeks

So I guess the question is what kind of PR's are landable while you work on other things. I don't want to pressure you to review something you don't have time for. But it would be nice to keep some momentum going. Perf, or this range trate, or other suggestions...

view this post on Zulip Matthieu Pizenberg (Nov 24 2020 at 07:48):

The small vec and small map are definitely landable, I've already read most of it, mostly waiting on Alex approval. Other perf work might be tricky to review since it definitely requires more than reading (at least testing on my machine). I think the Range trait could occupy whoever works on it for quite some time so that's a good option too. Error reporting messages could also be worked on. Don't hesitate to steal things from there too if you feel like it: https://github.com/pubgrub-rs/advanced_dependency_providers/issues/5.

view this post on Zulip Matthieu Pizenberg (Nov 24 2020 at 07:52):

I suppose porting some dart tests could be useful too https://github.com/pubgrub-rs/pubgrub/issues/30. but don't know since I've not looked at them.

view this post on Zulip Matthieu Pizenberg (Nov 24 2020 at 07:57):

Working on registry stats and resolver stats could be useful too. Determine if a given set of dependencies generates lots of conflicts or not.

view this post on Zulip Matthieu Pizenberg (Nov 24 2020 at 08:01):

Study another package manager with a concrete use case analysis would be interesting too. Maybe current capabilities are enough to solve dependencies of all packages or a subset of npm or conda or another one.

view this post on Zulip Eh2406 (Nov 27 2020 at 16:27):

Work and the holiday and other things used up my time this week and so I have made very little progress, I do have a branch where I am working on a range trate, but still working to get it to compile. Just an update.

view this post on Zulip Eh2406 (Nov 30 2020 at 14:57):

It compiles now. So nets steps include cleaning up the trate and trying to use it for something.

view this post on Zulip MrGreenTea (Dec 06 2020 at 16:18):

What's the current plan for a Range trait?
To me it looks like it could solve a few problems, for example with pre-release versions.
There also a few things I haven't found to be easy with the current Range, for example expressing strictly greater than.

I would love to take a crack at some ideas I have

view this post on Zulip MrGreenTea (Dec 06 2020 at 16:23):

The only thing I am unsure about is if then Range can usably be indepent of Version or if I will end up implementing one Range for one Version

view this post on Zulip MrGreenTea (Dec 06 2020 at 16:29):

This should also remove the need for Version::bump I think

view this post on Zulip MrGreenTea (Dec 06 2020 at 16:31):

And even lowest could be removed and with that is there even any need for the Version trait or wouldn't all needed logic be moved to the Range?

view this post on Zulip Matthieu Pizenberg (Dec 06 2020 at 16:50):

@MrGreenTea you can have a look at the discussion started here: https://github.com/pubgrub-rs/pubgrub/issues/49
There are possibly things not up to date with the work @Eh2406 started though (don't know myself)

view this post on Zulip Matthieu Pizenberg (Dec 06 2020 at 17:00):

Indeed I also believe that there would be no more constraint related to Version, only to Range. The one perilous thing is that we let people implement their range intersection and equality that can be treacherous to implement right. It is highly important that ranges can be compared for equality in an efficient way, so canonical representations are ideal. Enabling open brackets on a lower bound and closed brackets on a higher bound are amongst the things that make equality check treacherous.

view this post on Zulip MrGreenTea (Dec 06 2020 at 17:04):

I think so too, a useful default implentation should then probably be provided? I'll play around with a few ideas and come back to you

view this post on Zulip Eh2406 (Dec 06 2020 at 19:17):

Sorry for the delay. Some things came up and ate all of my available time. (https://github.com/rust-lang/cargo/pull/8890, and something I can't talk about.)
The range trait seems to work and to obviate the need for a version trait. I wanted to use if for something before I made a PR. I just pushed it https://github.com/pubgrub-rs/pubgrub/tree/range-trait if you want to give it a try. If it works for you then that is a good sine.
One gotcha is that if a range can have no members then it should Eq it's none repozentation.

view this post on Zulip Eh2406 (Dec 06 2020 at 19:19):

All the names and documentation need to be updated. But it is good enough to figure out if it is good for anything.

view this post on Zulip Eh2406 (Dec 06 2020 at 19:19):

There also a few things I haven't found to be easy with the current Range, for example expressing strictly greater than.

We should just add constructors for that to the existing Range.

view this post on Zulip Matthieu Pizenberg (Dec 06 2020 at 19:50):

https://github.com/rust-lang/cargo/pull/8890

That looks like a huge amount of work!

view this post on Zulip MrGreenTea (Dec 07 2020 at 13:20):

Eh2406 said:

Sorry for the delay. Some things came up and ate all of my available time. (https://github.com/rust-lang/cargo/pull/8890, and something I can't talk about.)
The range trait seems to work and to obviate the need for a version trait. I wanted to use if for something before I made a PR. I just pushed it https://github.com/pubgrub-rs/pubgrub/tree/range-trait if you want to give it a try. If it works for you then that is a good sine.
One gotcha is that if a range can have no members then it should Eq it's none repozentation.

Why not have Range::is_empty ?

view this post on Zulip MrGreenTea (Dec 07 2020 at 13:36):

Is Range::negate really needed? I can't see it's usage besides in Range::union.

view this post on Zulip Matthieu Pizenberg (Dec 07 2020 at 13:46):

Yes it's needed for Range::union, itself needed for the intersection of two negative terms

view this post on Zulip Matthieu Pizenberg (Dec 07 2020 at 14:05):

by the way, regarding names, complement and singleton and empty would be better fits than negate, exact and none if we are to make a range trait

view this post on Zulip Eh2406 (Dec 07 2020 at 14:39):

Making sure all the methods are needed, considering if all the traits are needed (yes, removing Eq and adding is_empty makes sense), and renaming things, was on my todo list for after demonstrating that it could be used for something.

view this post on Zulip Eh2406 (Dec 07 2020 at 17:39):

Range::is_empty

unfortunately, we also use self.intersection(other) == other. So switching away from Eq is not in scope for a first PR. If pubgrub#59 is merged, then it may be possible to remove the Eq bound then.

view this post on Zulip Eh2406 (Dec 07 2020 at 17:49):

Range::negate

The only use is in Term::intersection where it is used as r1.intersection(&r2.negate()) we could make that one method call with something like r1.subtract(&r2) if that would be easier to implement.

view this post on Zulip MrGreenTea (Dec 08 2020 at 20:28):

(deleted)

view this post on Zulip Eh2406 (Dec 08 2020 at 20:28):

No it is also used for Term::intersection

view this post on Zulip MrGreenTea (Dec 08 2020 at 20:29):

Yeah I just noticed that, sorry!

view this post on Zulip MrGreenTea (Dec 08 2020 at 20:30):

Thanks for the information, I'm mostly just trying to understand it and the design :)

view this post on Zulip Matthieu Pizenberg (Dec 08 2020 at 20:34):

For understanding the code I'd suggest the following steps:

It might take you some time but will definitely improve understanding I think

view this post on Zulip Eh2406 (Dec 08 2020 at 20:43):

Those are all great resources, but I am happy to answer questions (even without the background) if that is your preferred learning style.

view this post on Zulip Eh2406 (Dec 09 2020 at 15:08):

BTW a new memory profiler for rust was just released. Someone should try it to see if it points to good perf opportunities.

view this post on Zulip Eh2406 (Dec 09 2020 at 16:52):

Successfully ran it on large_case_u16_NumberVersion with the smallmap and smallvec.
The report lets you sort many different things:

view this post on Zulip Eh2406 (Dec 09 2020 at 20:06):

Trying this (for cargo) just got easier: https://github.com/steveklabnik/semver/pull/223

view this post on Zulip Eh2406 (Dec 23 2020 at 17:03):

When we get this project moving again and we get the perf work merged. I want to massively increase the size of the end-to-end proptests. And I want to set up a separate build that runs those tests in a loop to see if we find anything interesting by running on my desktop for a few days.

view this post on Zulip Matthieu Pizenberg (Jan 04 2021 at 13:23):

Personally, I'll have few busy weeks until end of january. I'll try have a look again at the perf PR next weekend. Except if @Alex Tokarev objects I think we can merge it then.

view this post on Zulip Eh2406 (Jan 04 2021 at 14:27):

Sounds like a plan. I recall having several more PRs of perf work, hopefully I can remember what they where when we get started agen.

view this post on Zulip Matthieu Pizenberg (May 01 2021 at 17:57):

Seems like another person again needs pre-release. We are starting a streak ahah, 2 days in a row

view this post on Zulip Eh2406 (May 01 2021 at 18:27):

I love that people are using pubgrub.

view this post on Zulip Matthieu Pizenberg (May 01 2021 at 21:19):

I love that people are using pubgrub.

Or trying at least XD

view this post on Zulip Eh2406 (May 01 2021 at 21:21):

I sat down to work on rebasing the Range trait, but found another (small) perf win. So oops, and PR incoming.

view this post on Zulip Eh2406 (May 02 2021 at 00:51):

I just rebased and force pushed the range trate branch.

view this post on Zulip Matthieu Pizenberg (Jun 20 2021 at 15:20):

By the way, few weeks ago I had a look at this fork https://github.com/PhotonQuantum/pubgrub/tree/release
They didn't interact with us verbally but maybe what they did is useful? There are 3 commits where they switched our Range impl by the one of the ranges crate: https://crates.io/crates/ranges

The commit says "feat: support continuous and infinite domain". Maybe it's useful? I can see from briefly looking at the commit changes that there is a notion of closed segment on both sides since they do not need the bump method to define Range::exact.

Just thought I would bring this to you in case it can help for your ongoing experiments.

view this post on Zulip Eh2406 (Jun 20 2021 at 15:25):

I am getting distracted by a new plan to impl the RangeTrait for Cargos Semver. I think this may work.

It work in that for all VersionReq on crates.io for all Version on crates.io my MyRange.contanes(ver) == Semver.matchs(ver), and MyRange.negate().contanes(ver) == !Semver.matchs(ver) (including pre releases vers)!
I am still testing if MyRange1.intersection(MyRange2).contanes(ver) == (Semver1.matchs(ver) && Semver2.matchs(ver)). My little lap top will have checked them all in ~3h more.

view this post on Zulip Eh2406 (Jun 20 2021 at 15:34):

I had not hared of the ranges crate. We should look into it. If it is "better" we should us it for our Range for v3, if it is not better then we should use it as an example of how the RangeSet can let you pick your representation of Range in v3. I will try to remember to be in touch with them!

view this post on Zulip Matthieu Pizenberg (Jun 20 2021 at 20:30):

I was reading Python PEP 440 today and oh boy that's quite the mess! That's what it feels writing spec that try to be compatible with the wide variety of already existing practices. They not only have pre-releases, they also have dev realease, post-release, local release and epochs. You could end up with a version looking like this: 42!2021.06rc5.post9.dev3

view this post on Zulip Matthieu Pizenberg (Jun 20 2021 at 20:34):

And then, when specifying version ranges, exclusive ordered comparisons (> and <) specifically exclude pre-releases (and dev releases) and post-releases of the specified version (not of the earlier or later releases). And pre-releases and dev releases are implicitly excluded from all versions specifiers, unless already present on the local system, explicitly required by the user, or the only available version satisfying a given specifier.

view this post on Zulip Eh2406 (Jun 20 2021 at 22:40):

Cargo only has Pre releases, but still has different semantics for what can get matched by them. It was pretty tricky to get everything to get the same answer., but I am happy to report that I have done it! The test for intersection just came back, and it got the same ancere for all pairs of VersionReq and Version on crates.io.

view this post on Zulip Eh2406 (Jun 20 2021 at 22:48):

For Cargo >=1.2.3 can not match any versions with a pre release. So ">=1.2.3".negate() would have to be "<1.2.3" or (is any pre release).

view this post on Zulip Eh2406 (Jun 20 2021 at 22:52):

>=1.2.3-alfa can match pre releases that also start 1.2.3. So it is more like >=1.2.3 or (is pre release >=1.2.3-alfa and <1.2.4)

view this post on Zulip Eh2406 (Jun 20 2021 at 22:56):

The most extreme case is * witch matches any non pre release version. "*".negate() matches any pre release version, but no stable versions. That is going to be hard to represent in one number line.

view this post on Zulip Eh2406 (Jun 20 2021 at 22:56):

On friday I was thinking about how to represent theas, and thought that the ranges for normal releases and for pre releases seam totally independent.

view this post on Zulip Eh2406 (Jun 20 2021 at 22:59):

This leads to:

struct SemverPubgrub {
    norml: Range<Version>,
    pre: Range<Version>,
}
fn contains(&self, version: &Version) -> bool {
    if version.pre.is_empty() {
        self.norml.contains(version)
    } else {
        self.pre.contains(version)
    }
}

view this post on Zulip Eh2406 (Jun 20 2021 at 23:00):

intersection, negate, any, and none can be done by doing the same thing to both parts.

view this post on Zulip Eh2406 (Jun 20 2021 at 23:02):

The hard (344 loc) part was converting the Semver syntax into ranges. But It worked!

view this post on Zulip Eh2406 (Jun 21 2021 at 00:29):

and here is the code: https://gist.github.com/Eh2406/88b8c799be3f3a6589073e8e58504a11

view this post on Zulip Matthieu Pizenberg (Jun 21 2021 at 18:15):

Nice! I've been reading a bit the ranges crate API and taking some inspiration to have a try and an improved API for us around all this. I think I'll try something looking like this and see where that goes:

use std::ops::{Bound, RangeBounds};

pub trait Version: Clone + Ord + Debug + Display {
    fn minimum() -> Bound<Self>;
    fn maximum() -> Bound<Self>;
}

struct Ranges<I, V> {
    segments: SmallVec<I>,
    phantom: PhantomData<V>,
}

trait Interval<V>: RangeBounds<V> {
    fn new(start_bound: Bound<V>, end_bound: Bound<V>) -> Self;
}

Last updated: Oct 21 2021 at 21:32 UTC