r? @epage

(rustbot has picked a reviewer for you, use r? to override)

One clarification, I don't think "old" is useful piece of terminology (at least at this time). The older Dependency Resolver works on an NP-Hard problem of determining which versions of transitive dependencies to select. When it hits conflicts it solves them by backtracking and attempting another solution. Its output is reified into a lock file, which must be the same even if created on different systems or when building different artifacts. The newer Feature Resolver takes a concrete set of dependency versions, as outputted by the Dependency Resolver, and decides which features and dependencies actually need to be built for the given invocation. Algorithmically this is a much simpler problem, although the implementation gets tricky with all of the interacting filters it supports. Many new pieces of functionality for the Feature Resolver cannot be included in the Dependency Resolver, because it would lead to different architectures or invocations including different information in the lock file.

I do not have enough implementation detail loaded into my brain at the moment to know if this is a problem, but any change to the Dependency Resolver needs to have a solution for backtracking. (Extensive tests, or detailed comments). Specifically, imagine that Foo is in the tree from three different dependencies, A depends on Foo without any optional features, B depends on Foo with a feature that activates Bar, and C depends on Foo with a week dependency on Bar?/qux. For any order these requirements are processed, will they always get correct solution? Now Furthermore, imagine that qux cannot be resolved, all versions are yanked or something. This can be solved by trying a different version of B or C but not A. Will all of those versions be correctly tried?

Thanks for your reply, @Eh2406 !

I don't think "old" is useful piece of terminology (at least at this time).

I used "old" because of the explanation in the comments of the resolver module referring to the other one as the "new" one, so I inferred the other one would be the old one, but I will change the PR description.

The issue with calling the new resolver as the feature aware one is that one might think that the Dependency Resolver has no concept of features at all, which is not the case, very importantly so for this PR as it builds on that. Correct me if I'm wrong but the main difference between the Dependency Resolver and the Feature Resolver is that former performs more aggressive unification, and enables more features at the start that might not be needed in the end (like platform specific ones).

but any change to the Dependency Resolver needs to have a solution for backtracking. (Extensive tests, or detailed comments).

I will add more tests once I find time to work on this PR.

I used "old" because

That is entirely fair. It is the terminology we use then. And I am sorry for the confusion that terminology has caused over the years.

The issue with calling the new resolver as the feature aware one is that one might think that the Dependency Resolver has no concept of features at all,

That makes sense. And I'm open to better terminology.

main difference between the Dependency Resolver and the Feature Resolver is that former performs more aggressive unification, and enables more features at the start that might not be needed in the end (like platform specific ones).

The Dependency Resolver specifies the version of every dependency (even if optional and activated by a feature) that will be used for any invocation on any system. Whereas the Feature Resolver figures out which features and dependencies are needed for this particular invocation on this particular system. Because of this distinction there will always be two phases, one of which enables more features to generate a lock file followed by one that more aggressively filters.

Is there any other way to solve this problem now?

I'm sorry if I wasn't clear. I do think this is a reasonable and correct approach. I think Ed had some concerns about exactly how we opt into it, and I would like to see more testing. But I am supportive of this work moving forward.

From my perspective, if a new lockfile version is what is needed, ok. I was then waiting on a response to Jacob's request for tests.

I'm sorry if I wasn't clear. I do think this is a reasonable and correct approach. I think Ed had some concerns about exactly how we opt into it, and I would like to see more testing.

Good then I understood it correctly. I didn't think you didn't like the approach of this PR. I agree that tests are important. The reason why I haven't worked more on this PR is that I have other projects going on so I didn't get to it. It is on my TODO list. It doesn't help that the weather is really good now and I go outside in my free time 😆 .

I'm pretty sure this approach won't work. There are several situations where weak dependencies are included through mechanisms that don't directly enable those features (like the user didn't specify the feature, or things like deferred features and such). I think the only option to minimize the entries in the resolve is to include all of the logic from the feature resolver in the dependency resolver, and we avoided that due to the level of complexity needed.

like the user didn't specify the feature

The Cargo.lock generating resolver enables all features that a crate has. If that enables any features of dependencies, those are also enabled. This will also enable the weak dependencies. This PR changes nothing about that. However, the weak dependencies of dependencies are only enabled if that feature is. That's precisely what the two present tests test for: disabled_weak_direct_dep and disabled_weak_optional_deps.

deferred features

WDYM by that? I grepped the cargo sources for that, the only place I could find was deferred profiles, which was something about debuginfo, and the deferred_weak_dependencies hashmap of the new resolver. Which seems like an implementation detail of the new resolver to me.

Since the dependency resolver doesn't know about dep: features, it isn't able to have a feature associated with the dependency in order to also trigger a weak dependency.

Deferred features is indeed related to the implementation of the feature resolver. When it sees the ? syntax, and it isn't already enabled, it needs to defer it in case something else enables it later.

I still don't understand your first paragraph. Would it be possible to give an example?

I now see what you mean in your second paragraph about deferred features. Indeed, if I adapt the deferred test from the testsuite, it fails. I have pushed the failing test to demonstrate it. I was a bit surprised that this didn't work before as similar logic is needed for dependency unification, but now I'm not sure if it's possible to implement such logic via backtracking. IDK.

FWIW, if we want to bump the lockfile version, I have a list of what could be bumped together.

Here's an example:

[package]
name = "z73"
version = "0.1.0"
edition = "2021"

[dependencies]
serde = {version = "1", optional = true }

[features]
foo = ["dep:serde"]
bar = ["serde?/derive"]

@ehuss thanks, that looks like the weak_namespaced test in weak_dep_features.rs. I will try to adapt it to v4 lockfiles, but in theory it should work with little modification as the Cargo.lock creating resolver can also handle FeatureValue::Dep. There might be one 1 line change needed though, the code doesn't look 100% correct.

Edit: pushed now, dep: works with a 1 line change. So only the unification support is an issue then (plus tests, plus any unknown issue).

☔ The latest upstream changes (presumably #12279) made this pull request unmergeable. Please resolve the merge conflicts.

@ehuss do you see any path forward here?

It's important to me that my Cargo.lock somewhat accurately reflects the dependencies that are being built for my products, and this makes that substantially harder. (See for example, launchbadge/sqlx#2579.)

The blocker is the unification support (see the failing test), which also is kinda important. I need to have a closer look but right now I don't even know if this PR's approach is viable at all. An alternative to this PR might be to use the "features"/new resolver with some different parameters (to make it similar to the "dependencies"/old resolver).

Unfortunately I don't see a path forward here. The current design was intentionally chosen to manage the complexity of the implementation. It might be possible to do post-resolution filtering, but that would require running feature resolution twice which could have a noticeable performance hit.

Should this PR be closed then @ehuss?

Yeah I think I will close this, even though I really want the feature. I don't have the time right now to fix the issues. Others are invited to work on this. Maybe in the future the approach could be tried out that we run feature resolution twice. It might have a performance impact, yes, but it will also create more correct output. Of course, if the existing dependency resolver could be made aware, that would be even better, but I'm not sure it is possible. Anyone, feel free to take my PR and make it work.

@ehuss So if I am understanding this correctly. In order to fix the bug, we would need to unify both resolvers to use the same logic? Do we have an idea of the scope of the work and if so would it be possible to provide some pointers. I would be willing to help, but I have no idea where I would start.

I am trying to see if there is a path forward for this issue that lingers and is becoming more problematic as many libraries are adopting the optional dependencies.

@Sytten The resolvers were not unified on purpose. The complexity of doing whole graph optimization like the feature resolver while the graph is still being constructed and can be changed like the dependency resolver is likely to be too complex to be maintainable. (There were some other implementation suggestions made above, the details of which I don't think I fully understood.)

The dependency resolver has to go back and reevaluate alternatives when it finds a problem. This makes it very sensitive to what order it tries to evaluate constraints. These are the backtracking concerns I mentioned above. This makes it incredibly difficult to be sure that a handful of tests actually covers all the important permutations of decision-making. (The tests not only needs to hit all the corner cases, it needs to try all of the orders of evaluation.) The only tool I have found useful for finding these bugs is the prop tests, which generate random crate version graphs and make sure the induced resolutions make sense. The most important of these is the SatResolve, where we compare the result to a simplified resolver that uses the varisat library. Unfortunately SatResolve does not (yet) know about features, and the prop test generator doesn't (yet) know how to generate them.

So I would start by:

1. add support for features to the SatResolve
2. add support for generating features to the prop test generator
3. fix the bugs in the dependency resolver exposed by the new test coverage
4. (Optional) re-factor the dependency resolver to treat features as a more first-class object that can be turned on and off, instead of an aspect of the dependency requirement.
5. propose new semantics for week dependencies in the dependency resolver, by specifying it in terms of the SatResolve
6. add support for generating week features to the prop test generator
7. attempt to add support for these new semantics to the dependency resolver. This PR will be a good place to start. But step 4, may be required to get the backtracking correct.

The easiest way to implement step 7 may be to adopt some wrapper around the pubgrub-rs library. I am busy working on that library to make it production ready for this purpose. I believe the lowering from cargo's understanding of dependency resolution to pubgrub's will automatically require/involve step 4, and should make at least "week" features not too complicated. I would happily support someone who wants to contribute by working on 1 - 6 while I continue to work on pubgrub!

P.S. @epage: having written this to do list up, is there a more appropriate place for it to be recorded?

@Eh2406 This is a really good starter thanks for that. I am going to try to tackle the first point this week. I have goos experience in rust but never contributed to cargo so I will likely need to have some reviews along the way. Is it ok if I tag you in draft PR?

@Sytten Absolutely! Also we have Office Hours if you want to chat synchronously. This week schedules may be odd for the US holidays, so ping us on the zulip thread for the slot you want to attend. The SatResolve code is not the best written for understandability, PR's that just refactor it so it makes sense to you are also welcome.