haskell / haskell/cabal

Solver: Consider checking for conflicting dependencies more eagerly

Open
#9,489 3 comments 1 reaction 0 assignees View on GitHub
cabal-install: solver type: enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.