Tracking issue for proptest resolve errors.

[ehuss]

On rare occasions, the proptest resolver tests fail. I'm adding this issue as a place where they can be noted to help investigate what is wrong.

[ehuss]

• https://travis-ci.org/ehuss/cargo/jobs/450311735
  resolve::minimum_version_errors_the_same
xs 2190102961 1563536589 970293348 2495828083
  Found during PR Treat "proc-macro" crate type the same as proc-macro = true #6256 (Nov 3, 2018, 0c6bb24 on master)
• https://travis-ci.org/rust-lang/cargo/jobs/449931801
  resolve::passes_validation
xs 967936909 1201283255 932769839 1391602777
  Found during PR Pass --update-head-ok when fetching via git CLI #6250 (Nov 2, 2018)
• https://travis-ci.org/rust-lang/cargo/jobs/443510586
  resolve::passes_validation
xs 4046239366 4251345928 2853496428 906285373
  Found during PR Deny publishing packages with non-standard name formats (Fix #6043) #6186 (Oct 18, 2018)
• https://travis-ci.org/rust-lang/cargo/jobs/443390405
  resolve::passes_validation
xs 3745459850 3266619453 2241537326 3256275249
  Found during PR Prefix build script output with crate name when running in extra verbose mode. Fixes #6158. #6164 (Oct 18, 2018)
• https://travis-ci.org/rust-lang/cargo/jobs/442728428
  resolve::limited_independence_of_irrelevant_alternatives
xs 1940677808 3504257549 3236656445 2871459081
  Found during PR Add PackageError wrappers for activation errors #6175 (Oct 17, 2018)

[Eh2406]

Some investigations so far.
xs 1940677808 ..., I was able to reproduce on Oct 17, 2018. However, coming back to that branch on Nov 4 it is now taking ~40 sec. Maybe the nightly compiler got better or Std learned a new optimization. Looking with a profiler it is spending most of its time on find_conflicting as called here.
xs 967936909 ..., I was able to reproduce, and get proptest to minimize some, on Nov 2. Looking with a profiler it is spending most of its time on find_conflicting as called here. When running in release mode the test goes by very quickly, but the profiler shows that it is spending an even larger percentage of the time in that spot. I am going to make a wilde assumption that the others are also finding this same slow spot. This seems to occur because we are finding a large number (>2400) of conflicts for one of the deps. We currently store the cache as an unsorted Vec of conflicts. Perhaps a more complicated data structure would let us determine if there are any that are relevant in better then O(n). Or we could keep the Vec sorted by some kind of "relevance heuristic", so that in practice it does not end up being O(n). The complexity of keeping it sorted, depends on the heuristic.

[Eh2406]

Thinking about it some more, the Vec is not unsorted it is in insertion order. So the heuristic we defaulted to is testing oldest first, or "most fundamental" first. By changing .iter() to .iter().rev() we get the heuristic test the most recently added first. This "fixes" the example that have been found so far, but lots of things will do that. I have set the number of cases to a very large number, to see if there are cases that break this one as well.

Update: It looks like it has found a case where the Vec.len() > 3500, what I do not know is if that is a performance problem. When it is done shrinking I will try running the result in debug and see if it is slow.

[alexcrichton]

During #6130 saw https://ci.appveyor.com/project/rust-lang-libs/cargo/builds/20073278/job/junrs4vbwm6n67bc with xs 3860150206 2068122883 658593055 1696548328

[ehuss]

https://travis-ci.org/rust-lang/cargo/jobs/451581176
PR #6270
limited_independence_of_irrelevant_alternatives
xs 2915994434 1603094070 1567204550 1659049042

[Eh2406]

Looking at the shrunk case with .iter().rev() set, I think that it takes a more pure worst case to trigger the explosion. So I think that one line change will reduce the occurrence of this, but will not solve all of the underlying problem.

The pure worst underlying problem, is a case like:
There are many releases of s that all have different problematik dependencies,

        pkg!(("s", "0.0.0") => [dep_req("a-sys", "= 0.0.0"),]),
        pkg!(("s", "0.0.1") => [dep_req("b-sys", "= 0.0.0"),]),
...
        pkg!(("s", "0.0.12") => [dep_req("l-sys", "= 0.0.0"),]),
        pkg!(("s", "0.0.13") => [dep_req("m-sys", "= 0.0.0"),]),
or 
        pkg!(("s", "0.1.0") => [dep_req("a", "= 1.0.0"),]),
        pkg!(("s", "0.1.1") => [dep_req("b", "= 1.0.0"),]),
...
        pkg!(("s", "0.1.12") => [dep_req("l", "= 1.0.0"),]),
        pkg!(("s", "0.1.13") => [dep_req("m", "= 1.0.0"),]),

We have already picked a incompatible version for each of the dependencies,
and then we have to solve s="*".
We end up adding to the cache a conflict that looks like:
's="*"' = {"a-sys v99.99.99", ... "m-sys v99.99.99", "a v1.99.99", ... "m v1.99.99"}
and we need a separate cache conflict for all (Number of conflicting versions) ^ (Number of problematik dependencies)

I have a bunch of larger ideas for how to optimize this, but I should probably get .iter().rev() in before spending time designing vaporware.