When can the algorithm use simplify

[Eh2406]

Our implementation of range just gained a new simplify method (cc #156). It would not be too hard to make this a method on DependencyProvider and so available to the Solver. Unfortunately, if done naively it breaks important set properties we rely on. What are those properties? Why does it break them? We don't know.

Before we can merge a new method to DependencyProvider we need to be able to articulate what properties it must uphold. We also need to figure out where it is safe for us to use the new method.

Hopefully by simplifying internally complex VS's we can solve the performance problems found in #135

[Eh2406]

Some obvious thoughts about when it is safe/efficient to call the new simplify.

• If the user provided us with the VS, then we should not simplify. If they wanted it simplified they could have done so before handing it to us.
• If it contains information about "no versions", then we must not call simplify. If everything works correctly any no version incompatibilities will always simplify to empty. Which is not helpful.
• We must not call it in the loop. Simplify is efficient, but that doesn't mean it's fast. If before we relied on A.intersection(B) == empty but we find that A.simplify().intersection(B.simplify()) != empty (substitute whatever set property makes this relevant), we should be very careful before fix it by checking (A.simplify().intersection(B.simplify())).simplify() != empty. (I'm looking at you satisfier code.)
• We should avoid calling it on the happy path. As running simplify requires the dependency provider to know all versions of the package, which could be expensive. For example, it would be a shame if you need to update the registry so that you can call simplify on the version you expect to work as a in the lock file and you know exists from the cached version of the registry. Alternatively, we must not rely on simplify always returning the same result.

I am hoping that we can solve all the real problems using 80/20 solutions like #163. If most of the large VS come from normal patterns that we can identify and merge then we may not need a general solution for identifying all cases where it's safe to simplify.

[Eh2406]

Some more thoughts:

• It is extremely risky to utilize simplify in the construction of partial_solution or relation. It runs the risk of computing inferences that cannot be proven from incompatibilities. I'm not saying we can't do it, I'm just saying it's risky.
• It is probably inefficient to utilize simplify in the satisfier search. Because those are terms that are constructed tested and thrown away. If we end up simplifying in partial_solution then we probably need to be consistent in satisfier search. Otherwise we run the risk of partial_solution telling us were satisfied but satisfier search not finding a satisfying assignment. So if we utilize simplify in the construction of partial_solution, that needs to be saved in such a way that it can be consistently reused in satisfier search.
• The last big place we call intersection is in prior_cause. Which seems like a perfect fit for simplify, as long as we are careful about "no versions". Fundamentally, prior_cause is already simplifying to incompatibilities into one. So simplifying the terms while were at it seems reasonable.