Implement a BD-Uninstallable build state

with the last batch of kde uploads, and ~50 packages ending up in broken state, needing manual give-backs, this did cost me a lot of work-time. and this is not kde, it's a constant pain, which always requires manual intervention.

this should have high priority.

<doko> Riddell, ScottK: I think we need to improve the kde situation for build-deps/breaks
<doko> e.g. kdenetwork fails with:
<ScottK> doko: Soyuz just needs to implement the same BD unistallable condition Debian has and it'll be fine.
<doko> The following packages have unmet dependencies:
<doko> kde-sc-dev-latest : Breaks: kde-workspace-dev (< 4:4.7.90) but 4:4.7.3a-0ubuntu4.1 is to be installed
<doko> Breaks: kdepimlibs5-dev (< 4:4.7.90) but 4:4.7.3-0ubuntu2 is to be installed
<doko> Breaks: libkonq5-dev (< 4:4.7.90) but 4:4.7.3-0ubuntu2 is to be installed
<doko> E: Unable to correct problems, you have held broken packages.
<doko> apt-get failed.
<doko> and doesn't automatically retry
<ScottK> Yep. On Debian that would get a BD uninstallable state, not a failed build and would eventually work.
<doko> if you know that, don't use it
<doko> just adjust the version for the b-d's
<doko> ScottK, is there a bug about this?
<ScottK> So you want us to fork the KDE packages from Debian?
<ScottK> I don't think that's going to happen.
<doko> ScottK, no, contribute to it. these adjusted versions don't hurt debian
<ScottK> No, the versions are correct.

I might implement this the way I always planned to in the past but never got around to (drilling down through the uninstallable stack until I find something I can actually dep-wait on). I have code locally that DTRT (or used to, a few years ago), just need to dust it off and sanely plug it into sbuild. No guarantees on timeframe here, but I'm hacking lp-buildd in the first months or two of the new year, so if this doesn't end up taking me much time, I might jam it in for "free".

I'd really like to fix this (speaking as a frequent Haskell stack uploader ...), but it's harder than it seems.

Just drilling down through the uninstallable stack can produce rather inaccurate build-deps, because a non-trivial case of unsatisfiability can be resolved in several different ways (for example, A Build-Depends: B Depends: C with C missing might be resolved by C appearing or by B changing so that it no longer depends on C). What Debian does is to analyse the whole package set on the equivalent of every retry-depwait run. For just Ubuntu I think that would be tractable, but, unlike Debian, Launchpad has to consider PPAs too. A dose-builddebcheck run on something the size of Ubuntu takes about eight seconds here for one series/architecture; a rough-estimate query suggests that retry-depwait needs to consider something on the order of 3000 archives, and presumably multiple series and architectures within many of those.

So, we can't quite do exactly what Debian does. Some thoughts that come to mind:

 * Since all PPAs today are based on the Ubuntu archive, most of the work is shared. In theory, dose-builddebcheck could be refactored to consider many archives and recalculate only what's changed. (I haven't profiled it, but perhaps most of the time is spent parsing the large baseline Packages files and not in resolving each set of build-dependencies on top of that?)
 * We could have two modes for retry-depwait, one of which is used for primary archives and one for PPAs. This is pretty inelegant and we normally like to avoid that kind of thing, but it might be a reasonable stopgap.

That also leaves the question of when this work is done. If I understand wanna-build correctly, Debian puts brand-new builds into the Needs-Build state first, and any retry ("give-back") goes to BD-Uninstallable first. The state for new builds is OK, but Launchpad users are used to retries being almost immediate and I think they'd be annoyed by retries taking a minute or so to go through dose-builddebcheck. So I think it would be more sensible to retain the behaviour where we dispatch both new builds and retries to buildds as soon as we can, but for any builds that end up dep-waiting have retry-depwait fill in a new column on BinaryPackageBuild with the processed dose-builddebcheck output for that build. Future retry-depwait runs would retry builds if they vanish from dose-builddebcheck's list of failures.

Once this is in place, we could change the buildd code to declare dep-wait any time apt-get's resolver fails; maybe continue to provide an approximate analysis where we can but otherwise you'd have to wait for the next retry-depwait run before you got a full analysis.

With the exception of the dose-builddebcheck refactoring which my OCaml really isn't up to, the rest of this seems tractable. I think it would depend on whether we're willing to include the special case for primary archives to make the performance workable.

Could you just fix this for the primary archive first? It seems that's more tractable and the most important thing to fix.