Tracking issue for proptest resolve errors.

[ehuss]

View all comments

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.

[Eh2406]

That pure worst case is now in the tests (#6283), and that test is no longer timing out. However that test is still a very efficient way to make the resolver do a lot of work. Bump up the N and we hit the 50K limit.

A way to fix it, probably the way, is to more efficiently encode that "a dependency will fail if one of its dependencies cannot be resolved." This is currently done simply by copying the details of the problem from the dependant to the parent. This is simple because the conflicting_activations is just a list of pids where if all of them are active then we cannot succeed. The problem is that if we learn a new problem for the dependant, then we need to retrigger that situation to learn copy it to the parent. This raw pure worst case has an exponential number of situations to copy.

The thought that is in my head at the moment is to make conflicting_activations more complicated so in addition to a list of pids it can also directly encode a list of dependencys where if all of them are known to have problems then we cannot succeed. I believe that would fundamentally quash the exponential blowup from this case. At the additional complexity of making "does this dependency have any known conflicts" a fundamentally recursive question. I wish there was a way to determine how much it mattered for real users.

[Eh2406]

I don't know where to save this and don't want to lose it. Proptest does a good job of minimizing the input, but not a great job. It is often true that you can remove a crate (edit: or dep) from the example without changing the error, even after Proptest has done its best. I have found the following script very helpful for finding the extra parts:

    let the_erroring_case = |input: &[_]| {
        let reg = registry(input.to_vec());
        let _ = resolve_and_validated(pkg_id("root"), vec![dep("s")], &reg);
    };

    use proptest::strategy::ValueTree;
    use proptest::test_runner::TestRunner;
    use std::panic::{self, AssertUnwindSafe};

    'outer: loop {
        let indexes: Vec<usize> = (0..input.len()).collect();

        let shuffle = Just(indexes)
            .prop_shuffle()
            .new_tree(&mut TestRunner::default())
            .unwrap()
            .current();

        for i in shuffle {
            let mut new_input = input.clone();
            new_input.remove(i);

            // the erroring case
            if let Err(_) = panic::catch_unwind(AssertUnwindSafe(|| {
                the_erroring_case(&new_input);
            })) {
                input = new_input;
                println!("{:?}", PrettyPrintRegistry(input.clone()));
                continue 'outer;
            }

            let mut new_input = input.clone();
            let summary = &input[i];

            let deps_indexes: Vec<usize> = (0..summary.dependencies().len()).collect();

            let deps_shuffle = Just(deps_indexes)
                .prop_shuffle()
                .new_tree(&mut TestRunner::default())
                .unwrap()
                .current();
            for d in deps_shuffle {
                new_input[i] = remove_dep(&summary, d);

                // the erroring case
                if let Err(_) = panic::catch_unwind(AssertUnwindSafe(|| {
                    the_erroring_case(&new_input);
                })) {
                    input = new_input;
                    println!("{:?}", PrettyPrintRegistry(input.clone()));
                    continue 'outer;
                }
            }
        }

        println!("All passed, let's make sure the original still failed.");
        the_erroring_case(&input);
    }

[Eh2406]

#6561 (comment): https://travis-ci.com/rust-lang/cargo/jobs/171554937