This is more or less a braindump of how dependency issues are being displayed and the evolution over the last couple of days; and not a high quality post. I’m happy to take feedback on understandability of the output 
Explaining unsatisfiable dependencies is hard!
the status quo is poor
Apt did a pretty poor job so far:
$ apt install exim4-daemon-heavy
Unsatisfied dependencies:
some-local-metapackage : Depends: postfix but it is not installable
Error: Unable to correct problems, you have held broken packages.
(in this example we have a custom meta package installed that has a Depends: postfix and is not allowed to be removed)
Now in this context, you might come to the conclusion yourself that oh postfix is not installable because I want to install exim4 (which are both mail-transport-agent that conflict with each other); but of course this can get a lot more complex and you are easily lost.
Maybe you know the hack for this already: Just append the names of things it says are not installable (after all, I want to install postfix and exim4-daemon-heavy, don’t I?):
$ apt install exim4-daemon-heavy postfix
Unsatisfied dependencies:
exim4-config : Conflicts: postfix but 3.9.1-10ubuntu1 is to be installed
exim4-daemon-heavy : Conflicts: mail-transport-agent
postfix : Conflicts: mail-transport-agent
Ah now it tells me it’s due to the mail-transport-agent Conflicts. It doesn’t tell me that both have Provides: mail-transport-agent but this is ok in most cases…
However, this doesn’t work programmatically and is very annoying, and not a good user experience. Imagine automated CI systems that just give you that a: Depends: b but is not going to be installed line; how are you going to find the root cause?
a step forward: 3.0 solver short explanations
In the first iteration of solver 3.0, we got a very basic rendering of the implication graph, yielding somewhat more informative messages that may be hard to read for users without a background in mathematics, particularly logic.
$ apt install exim4-daemon-heavy --solver 3.0
Error: Conflict: some-local-metapackage:amd64 -> postfix:amd64 but exim4-daemon-heavy:amd64=4.98-3ubuntu1 -> not postfix:amd64
You could also instead get:
Error: Conflict: exim4-daemon-heavy:amd64=4.98-3ubuntu1 -> not postfix:amd64 -> not some-local-metapackage:amd64 -> but some-local-metapackage:amd64
i.e. some-local-metapackage:amd64: Depends: postfix and not postfix invalidated the dependency, and hence not postfix implies not some-local-metapackage:amd64.
Without the actual dependencies printed, it can be a bit tough to find out what actually is going on.
a dead end: 3.0 solver long explanations (inverted method)
A couple weeks ago I started rewriting this into a full dump of the decision subgraph that lead to the unsatisfiability:
$ apt install exim4-daemon-heavy --solver 3.0
Error: Unable to satisfy dependencies. Reached two conflicting choices:
1. Remove postfix:amd64 due to conflict:
postfix:amd64 Conflicts mail-transport-agent
conflicting choices:
- Install exim4-daemon-heavy:amd64=4.98-3ubuntu1 by user request
2. Keep postfix:amd64 (see above)
This had a problem however; it is sort of upside-down reasoning from what we are used to, and was hard to understand, especially with larger reasoning chains:
$ apt install exim4 --solver 3.0
Error: Unable to satisfy dependencies. Reached two conflicting choices:
1. Install exim4:amd64=4.98-3ubuntu1 by user request
2. Do not install exim4:amd64=4.98-3ubuntu1 due to unsatisifed dependency:
exim4:amd64=4.98-3ubuntu1 Depends exim4-daemon-light (>= 4.98-3ubuntu1) | exim4-daemon-heavy (>= 4.98-3ubuntu1) | exim4-daemon-custom (>= 4.98-3ubuntu1)
unsatisfiable choices:
- Do not install exim4-daemon-light:amd64 due to conflict:
exim4-daemon-light:amd64 Conflicts mail-transport-agent
conflicting choices:
- Keep postfix:amd64 due to dependency:
some-local-metapackage:amd64 Depends postfix
because:
Keep some-local-metapackage:amd64 because it was previously installed
- Do not install exim4-daemon-heavy:amd64 due to conflict:
exim4-daemon-heavy:amd64 Conflicts mail-transport-agent
conflicting choices:
- Keep postfix:amd64 (see above)
2.9.32: 3.0 solver long explanations (strongest path + context)
I had a long discussion with a friend yesterday on the output and have ended up with a new approach now, which prints the strongest path to a decision, and then later it will print up any paths not taken.
$ apt install exim4-daemon-heavy --solver 3.0
Error: Unable to satisfy dependencies. Reached two conflicting decisions:
1. postfix:amd64 is selected for removal because:
1. exim4-daemon-heavy:amd64=4.98-3ubuntu1 is selected for install
2. postfix:amd64 Conflicts mail-transport-agent
[selected exim4-daemon-heavy:amd64=4.98-3ubuntu1]
2. postfix:amd64 is selected for install because:
1. some-local-metapackage:amd64 is selected for install
2. some-local-metapackage:amd64 Depends postfix
$ apt install exim4 --solver 3.0
Error: Unable to satisfy dependencies. Reached two conflicting decisions:
1. exim4:amd64=4.98-3ubuntu1 is selected for install
2. exim4:amd64=4.98-3ubuntu1 Depends exim4-daemon-light (>= 4.98-3ubuntu1) | exim4-daemon-heavy (>= 4.98-3ubuntu1) | exim4-daemon-custom (>= 4.98-3ubuntu1)
but none of the choices are installable:
- exim4-daemon-light:amd64 is not selected for install because:
1. some-local-metapackage:amd64 is selected for install
2. some-local-metapackage:amd64 Depends postfix
3. exim4-daemon-light:amd64 Conflicts mail-transport-agent
[selected postfix:amd64=3.9.1-10ubuntu1]
- exim4-daemon-heavy:amd64 is not selected for install because:
1-2. postfix:amd64 is selected for install as above
3. exim4-daemon-heavy:amd64 Conflicts mail-transport-agent
[selected postfix:amd64=3.9.1-10ubuntu1]
In fact, all solver errors are now reported as two conflicting paths through the decision tree.
let’s talk about that context
I mentioned further above, that we later print any path not yet taken, but the example does not show it, so let’s create an artificial one:
We have the packages
unsatwithDepends: a | bawithDepends: aa | abbwithDepends: ba | bbaa,abwithDepends: xba,bbwithDepends: y
In the output below, when trying to install unsat, we can see additional context that shows that it picked b to satisfy Depends: a | b because a is not selected for install:
E: Unable to satisfy dependencies. Reached two conflicting decisions:
1. bb:amd64 is selected for install because:
1. unsat:amd64=3 is selected for install
2. unsat:amd64 Depends a | b
[selected b:amd64 for install]
3. b:amd64 Depends ba | bb
[selected b:amd64]
For context, additional choices that could not be installed:
* In unsat:amd64 Depends a | b:
- a:amd64 is not selected for install
* In b:amd64 Depends ba | bb:
- ba:amd64 is not selected for install
2. bb:amd64 Depends y
but none of the choices are installable:
[no choices]
backtracking
Now what is still missing is the reason for a not being selected; or ba for that matter. What happens here is that we have performed back-tracking, that is we tried to install a and it failed, so we mark a as false; but we currently lose the data from backtracking.
We currently also cannot differentiate backtracking from user requests or policy requests that force a package to be installed, which is upcoming.
We expect to get better error messages for backtracking in a future release; however a particular issue with the solver right now is that we don’t really have real world backtracking test cases, so modifying it is risky.
other tbd
The above test case is actually showing a minor lack of optimization: This does not need backtracking at all; packages having dependencies with no solutions should just be marked not installable in the first place - which is not the case so far.
An open question is the grammar; Depends and friends are the field names but they do not form a proper sentence in a Depends b. Some translation essentially translate Depends to Depends on which would be correct grammar (with an invalid upper case), there are certainly arguments for any of a Depends b, a Depends on b and a depends on b.