Hello, Am Mittwoch, den 22.06.2011, 19:14 +0200 schrieb Stefano Zacchiroli: > This analysis, of course, relies on the assumption that package > dependencies can be arbitrarily complex, with inter-related conflicts > and alternative dependencies. As Joachim and others have already pointed > out, conflicts are not really taken into account in his proposal. Maybe > it is indeed possible to find a good approximation of the problem by > ignoring conflicts and doing some subsequent repair-step, by hand or > automatically. However, we have problems of understanding what exactly > the justification of such an approximation would be. Can we really make > any assumptions on what kind of conflicts would be RC bugs, and hence do > not have to be taken into account? If we can find such assumptions then > we should probably cast them into policy. How to deal with conflicts > seems to be a crucial point to evaluate the proposal in more depth. A clean solution would be to require package maintainers to be specific in their Conflicts, and have different fields for „This package should generally not be installed along the other package.“ and „There is something temporary wrong with the combination of this package and the other package (usually with some version constarint) so that a release should not contain this and the other package“. The first corresponds to 3 and 4 in Raphael’s mail, the latter to 1 and 2. My thesis is that for testing migration it is sufficient to only consider the latter kind. But introducing a separate field and expecting all maintainers to use it is not realistic, hence the suggested heuristic of considering Conflicts with an upper version bound as of the latter kind, and all other of former kind. > Besides this principal scepticism some more specific remarks: > > - having all packages installable in testing is a noble goal, however > during a release cycle it typically gets lost even in i386, and has to > be restored by the release team before the release. Note that my proposal allows the release team to individually kill certain constraints. They could, for example, say „Ignore the X’s dependency on Y“. I am assuming that package installability should only be broken if the release team wants it to for some reason (e.g. with the recent haskell-dummy migration), and never by the britney alone. > Even then it is > usually not satisfied on the less popular architectures, at least not > for arch:all packages (see [3]) arch:all are, besides Conflicts, another flaw in my proposal that I recently discovered: First, the semantics is not clear to me (should it be installable on all arches? one any arch? on one particular, as it is now?). A solution would be something like this: Generate logical atoms for arch:all packages for each architecture (e.g. assume there is one separate package for each architecture), and then add a constraint that the arch:all package can migrate if at least one of the arch:any package can migrate. (But this is not fully thought through yet.) > For this reason one probably would > rather want to say something like: any package that was installable > before the migration should also be installable after the > migration. I don’t think this has to be a problem, at least after an initial bootstrapping: After one migration run, testing is in a state that satisfied all generated clauses, plus and minus the manually added hints. These hints still prevail, so in the next run, testing is already consistent (modulo these hints). A package that was previously installable would be installable afterwards, a package that was previously not installable can only be there because it was allowed by a hint, and this hint continues to allow it. > Otherwise, a maximal solution could imply to > migrate 2 packages to testing and to remove one. No, removal of packages would be prevented by a constraint that says: „If a package is in testing and exists in unstable, at least one version has to be in testing afterwards.“, unless overridden by the release team. > - About efficiency: as Mark said, modern SAT solvers are extremly > efficient. However, one should not forget that one has to consider all > architectures in parallel, that is we need a solution that works on > all achitectures. You would have at least one variable per package in > testing, plus one per migration candidate plus variables for source > packages and probably also for virtual packages. This would yield, as > a very rough estimate, 50k variables, multiplied by 11 release > architectures gives 550k variables. And that's a lot. I was not planning to add virtual packages but rather resolve these to a disjunction of fulfilling package-version pairs, just as versioned dependencies would be resolved before starting the SAT-solver. But your point stands: The problem becomes very large. On the other hand, if we have less conflicts than in a debcheck run, solutions might be easier to find, as in the absence of conflicts hardly any backtracking is needed and the complexity should go down considerably. > But according to our experience, for it to happen > the problem should not be underestimated and, more importantly, should > be properly formalized in a way which is independent of some specific > encoding technique. Correct. That is why I suggested to use the format already used in a MAX-SAT competition: http://maxsat.ia.udl.cat/requirements/ Actually, MAX-SAT is more that we need: I don’t think we really have to find the largest (by numbers) set of packages that can migrate, and inclusion-maximal set of packages should suffice. This might also take the complexity down. My impression is that the release team is happy with their current tools and that the new britney2 is meant to improve the things that are not so good today, so maybe a SAT-based britney would not be so great after all. Thanks for your feedback, Joachim -- Joachim "nomeata" Breitner Debian Developer nomeata@debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C JID: nomeata@joachim-breitner.de | http://people.debian.org/~nomeata
Attachment:
signature.asc
Description: This is a digitally signed message part