search

pubgrub-rs / pubgrub

PubGrub version solving algorithm implemented in Rust
https://pubgrub-rs.github.io/pubgrub/pubgrub/
Mozilla Public License 2.0
337 stars 30 forks source link

DependencyOnTheEmptySet #125

Closed baszalmstra closed 8 months ago

baszalmstra commented 1 year ago

For the Conda solver I build I implemented a VersionSet that builds a bitset of applicable version from a Conda specific range specifier. I can do this because I can know upfront exactly which versions are available of any given package. This makes implementing complement, intersection, etc very easy and fast. An Empty can also be very easily expressed if all bits are set to zero.

However, sometimes I encounter a package version (lets call it A) that has a dependency range that doesn't select any package version. This is fine and should indicate that package version A should also not be selected. However, because the range equals to empty I get the DependencyOnTheEmptySet error and the solve process aborts.

I was wondering if that behavior is an optimization or if that's something that is required by the algorithm. In my case, due to the way my VersionSet implementation behaves it doesn't make sense. Is it something that I could optionally turn off?

Eh2406 commented 1 year ago

A bit set is a very clever backing for a VersionSet, I would love to see that brought out as an example on its own. How do you implement singleton, without knowing what package it is for?

There are a number of hacks available for modeling a version known to be unavailable. The most direct example is to return Dependencies::Unknown. But yes, this is a hack.

I don't think it's technically required by the algorithm. However, there are many places in the code where the implications of depending on an empty set have not been thought about. I would not be surprised if there are bugs that will emerge if the check is just removed. I don't have a good way to track them all down.

Perhaps you could do some kind of differential testing for us, on a large corpus of examples that involve packages with that kind of dependency, run your resolver using Dependencies::Unknown and stock PubGrub and record the results. Then run it again with dependencies on the empty set, and a fork of PubGrub that allows it, and compare the results. If the two different inclinations return the same then there probably aren't significant bugs.

mpizenberg commented 1 year ago

Hi, I wouldn't bet for sure, but I think it is required that we don't have empty sets at unexpected places because of how incompatibilities are reduced, and how we detect conflict.

On Wed, Nov 9, 2022, 00:45 Jacob Finkelman @.***> wrote:

A bit set is a very clever backing for a VersionSet, I would love to see that brought out as an example on its own. How do you implement singleton, without knowing what package it is for?

There are a number of hacks available for modeling a version known to be unavailable. The most direct example is to return Dependencies::Unknown. But yes, this is a hack.

I don't think it's technically required by the algorithm. However, there are many places in the code where the implications of depending on an empty set have not been thought about. I would not be surprised if there are bugs that will emerge if the check is just removed. I don't have a good way to track them all down.

Perhaps you could do some kind of differential testing for us, on a large corpus of examples that involve packages with that kind of dependency, run your resolver using Dependencies::Unknown and stock PubGrub and record the results. Then run it again with dependencies on the empty set, and a fork of PubGrub that allows it, and compare the results. If the two different inclinations return the same then there probably aren't significant bugs.

— Reply to this email directly, view it on GitHub https://github.com/pubgrub-rs/pubgrub/issues/125#issuecomment-1307986350, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAWFOCKYH327NAA2L3ZC2KTWHLQY7ANCNFSM6AAAAAAR2WEHCY . You are receiving this because you are subscribed to this thread.Message ID: @.***>

baszalmstra commented 1 year ago

A bit set is a very clever backing for a VersionSet, I would love to see that brought out as an example on its own. How do you implement singleton, without knowing what package it is for?

The VersionSet is either Full, Empty or a bitset. If the bitset only contains 0s it will become Empty and if it only contains 1s it will be Full. A version is represented as just an index in the bitset. A version also contains a pointer to the full set of variants. Singleton constructs a bitset of 0s from the full set of variants where only the index of the version is set to 1.

The downside is that I lose the original constrains when converting to a bitset which makes the error messages a bit trickier. I haven't found a proper solution for that yet.

Returning Dependencies::Unknown when a range is empty or a certain dependendant package is missing works but the errors are not that great because it now just says: dependencies or __ROOT__ at version .. are unavailable. If its possible to return some more information in the Dependencies::Unknown that would solve my issues though!

Eh2406 commented 9 months ago

Adding more flexibility to the error message for Dependencies::Unknown seems like a good improvement!

This morning I experimented with a branch where I removed the check. Details in the PR #133 :-P

Eh2406 commented 8 months ago

This was fixed in #133!