Solver: Consider checking for conflicting dependencies more eagerly
- Dominant language
- Haskell
- Stars
- 1.7k
- Forks
- 750
- Avg merge
- 4d 3h
- Merged PRs (30d)
- 28
Description
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:
https://github.com/haskell/cabal/blob/b34184e057324331d4e0184d7298c752090df08b/cabal-install-solver/src/Distribution/Solver/Modular/Validate.hs#L428-L430
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:
https://github.com/haskell/cabal/blob/b34184e057324331d4e0184d7298c752090df08b/cabal-install-solver/src/Distribution/Solver/Modular/Validate.hs#L472-L478
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`](https://github.com/haskell/cabal/blob/b34184e057324331d4e0184d7298c752090df08b/cabal-install-solver/src/Distribution/Solver/Modular/ConflictSet.hs#L57) to maintain good performance in the case of two conflicting version ranges.
Contributor guide
Assessment
This issue has not been assessed yet.