Solver: Consider checking for conflicting dependencies more eagerly

[grayjay]

The dependency solver currently only checks whether two dependencies on a package conflict when one of the dependencies is fixed, i.e., the solver has already picked a version or an installed package already depends on it. Here is a comment describing the behavior where it is implemented:

cabal/cabal-install-solver/src/Distribution/Solver/Modular/Validate.hs

Lines 428 to 430 in b34184e

	-- | Merge constrained instances. We currently adopt a lazy strategy for
	-- merging, i.e., we only perform actual checking if one of the two choices
	-- is fixed. If the merge fails, we return a conflict set indicating the

I think that it's worth testing the performance of a more eager algorithm that checks whether each new constraint conflicts with any existing constraint. For example, if A-1 depends on C == 1.2.* and B-1 depends on C == 1.3.*, the solver could backtrack immediately after choosing A-1 and B-1 rather than continuing until it fails to choose a version for C.

The change would affect this case:

cabal/cabal-install-solver/src/Distribution/Solver/Modular/Validate.hs

Lines 472 to 478 in b34184e

	merge (MergedDepConstrained vrOrigins) (PkgDep vs2 (PkgComponent _ comp2) (Constrained vr)) =
	Right (MergedDepConstrained $
	-- TODO: This line appends the new version range, to preserve the order used
	-- before a refactoring. Consider prepending the version range, if there is
	-- no negative performance impact.
	vrOrigins ++ [(vr, comp2, vs2)])

Possible benefits:

• Improve performance by allowing the solver to backtrack sooner.
• Reduce the size of conflict sets by not adding the conflicting dependency (C above) to the conflict set.
• Improve error messages by finding the conflict after fewer log lines.

We would probably also need to add a new constructor to Conflict to maintain good performance in the case of two conflicting version ranges.

[mpickering]

Is there a particular performance test or testcase which can be used to analyse the impact of this optimisation?

[grayjay]

Yes, the change could be tested by running the Hackage benchmark in https://github.com/haskell/cabal/tree/master/solver-benchmarks.

[Mikolaj]

That's a good question, but I'm really looking forward to the resulting error quality improvements. That can be crudely measured by the length of error messages (assuming that the display of errors in not modified).