Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

improve the proptest of the resolver. #6120

Open
3 of 9 tasks
Eh2406 opened this issue Oct 2, 2018 · 4 comments
Open
3 of 9 tasks

improve the proptest of the resolver. #6120

Eh2406 opened this issue Oct 2, 2018 · 4 comments
Labels
A-dependency-resolution Area: dependency resolution and the resolver A-testing-cargo-itself Area: cargo's tests E-hard Experience: Hard S-needs-mentor Status: Issue or feature is accepted, but needs a team member to commit to helping and reviewing.

Comments

@Eh2406
Copy link
Contributor

Eh2406 commented Oct 2, 2018 •
edited
Loading

We have some proptests that are used to fuzz the resolver. They were introduced in #5921. However, not all the good ideas from that discussion got implemented in the initial push. This is a list of good ideas related to using proptests on the resolver to act as a hub.

The current strategy does not:

The current properties do not test:

  • If resolution was successful, then all the transitive requirements are met.
  • The resolver agrees with some orical. Maybe an SAT solver, or the cargo that we are being built with, or the last cargo on crates.io.
  • Anything about error messages.
  • @maurer suggested testing for consistency. Same registry, same cargo version, same lockfile, every time.
  • @maurer suggested a pareto optimality property (if all else stays the same, but new package versions are released, we don't get a new lockfile where every version is <= the old one, and at least one is < the old one)
@Eh2406 Eh2406 added E-hard Experience: Hard A-testing-cargo-itself Area: cargo's tests A-dependency-resolution Area: dependency resolution and the resolver labels Oct 2, 2018
@Eh2406 Eh2406 mentioned this issue Oct 6, 2018
Merged
bors added a commit that referenced this issue Oct 8, 2018
@bors
Auto merge of #6149 - Eh2406:proptest, r=alexcrichton
aa06d7c 
proptest basic validation

This adds a function for testing that the output of the resolver is basically reasonable. This function has the same signature as the function for running the resolver in a test. So it is easy to switch back and forth, depending on the thoroughness vs speed tradeoff. This also adds a proptest/fuzz that runs this validation against arbitrary registry.

cc #6120
Sorry about the cargo fmt.
@Eh2406
Copy link
Contributor Author

Eh2406 commented Oct 19, 2018

Cc, @necaris

@Eh2406
Copy link
Contributor Author

Eh2406 commented Oct 24, 2018

Another property, that I think will shrink well, that will take some design work, is order randomization.
For example, we address more constrained deps before lease constrained once, but we do not guarantee what order we address equale constrained deps. We guarantee that it is deterministic, but not what it is. We use BinaryHeap's default, I think it is FIFO, we could test that resolve(..., FIFO).is_ok() == resolve(..., FILO).is_ok().

@Eh2406 Eh2406 mentioned this issue Nov 2, 2018
Merged
bors added a commit that referenced this issue Nov 3, 2018
@bors
Auto merge of #6249 - Eh2406:cleanup, r=alexcrichton
0c6bb24 
Resolver cleanups and a new fuzz test

This is the commits from my on going work on pub/priv deps that did not relate to that functionality. Then it also adds a fuzz test that minimal-versions does not change whether resolution is possible.

cc #6120
@Eh2406
Copy link
Contributor Author

Eh2406 commented Nov 19, 2018

Just came across this excellent summary of how to make properties.

@Eh2406
Copy link
Contributor Author

Eh2406 commented May 6, 2019

The resolver agrees with some orical.

varisat is on crates.io, and may work. At the moment @jix recommendations for xor constraints are in this comment.

@Eh2406 Eh2406 mentioned this issue May 23, 2019
Merged
bors added a commit that referenced this issue May 28, 2019
@bors
Auto merge of #6980 - Eh2406:varisat, r=alexcrichton
a7648c7 
Test the Resolver against the varisat Library

Resolution can be reduced to the SAT problem. So this is an alternative implementation of the resolver that uses a SAT library for the hard work. This is intended to be easy to read, as compared to the real resolver, and run as part of the test sweet to make sure the real resolver works as expected. Part of #6120.

Some notes on performance:
The initial version did not support public & private deps:
~64 loc, `O(nln(n))` vars, `O(nln(n) + n*d)` clauses, 0.5x slower on `prop_passes_validation`
The final version:
~163 loc, `O(dn^2`) vars, `O(dn^3)`  clauses, 1.5x slower on `prop_passes_validation`

That comparison makes me feel better about spending months trying to get public & private deps to be fast enough for stabilization.
@epage epage added the S-needs-mentor Status: Issue or feature is accepted, but needs a team member to commit to helping and reviewing. label Oct 24, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
A-dependency-resolution Area: dependency resolution and the resolver A-testing-cargo-itself Area: cargo's tests E-hard Experience: Hard S-needs-mentor Status: Issue or feature is accepted, but needs a team member to commit to helping and reviewing.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@epage @Eh2406