[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,(Offscreen) So welcome to the talk\Nfrom Niels
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,about dependency resolution in\Npolynomial time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,(Neils) I'm Neils, I'm doing my second\Ntalk today.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This time about something slightly\Nmore technical.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I wanted to do dependency resolution\Nin deterministic polynomial time,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,which is what this is all about.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I didn't get as far with this as I wanted.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I wanted to have a tool ready and have\Nsome results, which I didn't quite finish.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So these will be my findings work in\Nprogress notes.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We have six topics I have to cover.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,A quick introduction.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then something about the hard problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then the part the part where it actually\Nturns out to be highly tractable
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,in practice, if you don't think too much\Nabout it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And then there is some installing,\Nupgrading, and installing again
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,for how to improve your solvers.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Starting with introduction.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I'm hoping mostly to debunk the myth\Nthat dependency resolution is a very
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,hard problem that we cannot solve,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and we should remove packages in the hopes\Nthat they will somehow keep the archive
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,from exploding, and the dependency\Nresolvers to break, and apt to die,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and god knows what.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I've been working on Britney, which is a\Ndifferent problem to solve, but it
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,involves the same techniques, or uses some\Nof the same techniques.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Some will be directly applicable to apt,\Nsome will not.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,There's not a one size fits all solution,\Nsorry.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And I much less haven't wrote it yet,\Neven if there was.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So defining the problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,When you try to install a package on your\Nsystem,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,there's actually two problems\Nbeing solved.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,One is the part where apt figures out if I\Nhave to install Eclipse.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You'll be needing a lot of Java packages,\Nyou'll be needing a lot of other stuff.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And so it figures out which packages are\Nneeded for this to make sense.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The separate part of the problem,\Nthe second problem is,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,once you have this list, they have to be\Nunpackaged and configured in a certain
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,order for this all to make sense.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,They are in theory two distinct problems.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I'll be talking about the first problem,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,because that's actually\Ndependency resolution.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The other thing is just ordering.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The ordering thing is certainly also very\Nimportant part.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I don't want to dismiss that, it's just
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it is in fact theoretically a polynomial\Ntime problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So to solve the ordering problem, you\Nbasically compute all the action-
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Given a set of actions that need\Nto be done,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,then there are some constraints between\Nsome of them,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,like you unpack things before you\Nconfigure it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Maybe you deconfigure something else\Nbefore that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So you end up with a list of partial ??\Nconstraints.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,From that you build a graph with ordering.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It's fairly simple to do, in practice,\Nif you have the right tools for it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then without cycles, this is a trivial\Nthings where it just orders it
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and gives you this is the order,\Ngo fix.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,When there's cycles you will get a single\Naction consisting of multiple things
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,to do at the same time, which is really\Nimpossible to do.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It turns out that the way we defined this\Nwhole thing,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,if you have a package that does not have a\Npost install script,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it does not need to be\Nconfigured separately.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That means that it's just unpacked or\Nnot unpacked.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That tends to break most cylcles.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If you want, there's problems with\Nordering constraints.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Help us to find a way to get rid of most\Nof the post install scripts,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,such as the ones just running lvconfig\Nand nothing else.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That could solve some of the cycles,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and otherwise it's just feeding it to dpkg\Nand it works.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If you have a cycle, it's a separate\Nproblem fixing that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I won't be covering that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,As I said, the runtime is polynomial.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It's something like the size of the\Npackage, a regular graph.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Which is fairly polynomial.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This even covers finding cycles.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Again breaking cycles is just removing\Npost install scripts.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And of course if you think this is too\Nsimple,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,you can always implement more features\Non top of it,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,such as trying to optimize for minimal\Ndowntime of services and all that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You can make any trivial problem very hard\Nvery soon with that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So, the hard problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,First of all, the players.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We've got apt, aptitude, cupt, whatever.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We've got Britney.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We've got DOSE, edos, whatever its\Nname is today.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,They solve the hard problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Or they should be trying to do.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Notable tools not affected by it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,dpkg.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So dpkg surely figures out if you are\Nmissing dependencies. It says,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,"I cannot resolve this, and I don't know\Nwhere to fetch it, so I'm just giving up."
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And that is the only thing you can do.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Which means it only verifies the solution\Nwhich is known to be polynomial,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and is therefore is not a game player.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,DAK rm is also doing a polynomial time\Ncheck, it just happens to be so
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,for other reasons.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That's basically the known players.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,There are probably others.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,But we're moving onto the\Nhard problem itself
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So the problem we actually have is,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,we've got version dependencies,\Nwe've got alternative choices,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,we've got virtual packages.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,All three makes this problem hard.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You basically have to remove all possible\Nalternative choices, guesses, whatever,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,to make this simple.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It just so happens if you move version\Ndependencies among other things,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,things become really fun.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,?? to solve the problem, but upgrading\Ngets really really spicy.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So how do we ensure that dpkg\Nis configured before your new package,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,use a feature new dev package\Nis installed.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That's sort of impossible.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It becomes simple, but we end up with a\Nbroken dependency ??,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,so it's not really an option.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Technically there's also a way to make\Nit simple by having multiple versions
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,of things, and removing negative\Ndependencies,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,but that's not necessarily\Neasy to do either.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Presumably file configs will get in our\Nway or something.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We have to redefine where we place all of\Nthe files, that's not going to be
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,something we're doing anytime soon.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So yeah, it's not really an option.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,To give you a better understanding of the\Nproblem, please consider this example.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If we have coreutils at some version,\Ndepending on either this version
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,of libc or a newer one.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,From this can we immediately conclude
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,that if libc 2.19 is known to be\Ninstallable,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,that coreutils will also be installable?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,How many people think we can immediately\Nconclude something from this?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,How many people think we {\i1}cannot{\i0}\Nconclude anything from this?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We'll that's good.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So it turns out that with negative\Ndependencies and without negative
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,dependencies, it doesn't really matter.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,With negative dependencies, libc or\Nwhatever it depends on could
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,just conflict with coreutils, we're\Nbroken, it's out.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And without negative dependencies, you\Ncould have one of the things where
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it depends on a version that's newer or\Nolder, and no.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It's not really trivial to do.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You can't conclude something locally,\Nin theory.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That's something that can\Nbecome a problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Anyway, it is highly tractable\Nin practice.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Because if you do have a break, conflicts,\Nor otherwise negative dependency,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it tends to be upper bound.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So if the previous version of coreutils\Nwas installable with that version,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,the new version will also probably be.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Likewise, most dependencies, circular or\Notherwise, tend to be upper bound.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,There are cases of version ranges which\Nis a lower bound and upper bound
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,at the same time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,They exist, they are just not so\Ncommon yet.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And that's a good thing.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The number of possible solutions to\Nany clause
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,actually tends to be fairly limited.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Of course there are the exceptions.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Packages from unstable.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,They might just be missing, in which case\Nit's really hard to solve the dependency.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You've got mutually exclusive packages\Nall the sendmail stuff, MTAs.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The version ranges I mentioned before.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And then of course the strictly equal\Nversions, which we see inside
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,packages built from the same\Nsource packages.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The redeeming feature here: same source.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Because that is actually very simple\Nto figure out
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,if they are from the same source.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So they tend to be upgraded ??\Nanyhow.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The new versions tend to be available\Nat the same time sorta thing.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The problem made hard in a nutshell, is\Nthis contrived example for example.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You have a package you want to try,\Nand it depends on any number of foos.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Each of the foos can either be solved by
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,picking up the bar package\Nor the good one.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Which might be a hint to which one we\Nwould choose if we want to solve it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And the bar packages, depends on a\Nbad package that does not work
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,with the starting-package,\Nand we are broken.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And the good package just doesn't have any\Ndependencies and is therefore good.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,In the perfect example you saw,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,you try foo, good, foo1, and then good\Nand be done.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,In practice, if you don't have some way\Nof ordering these so you know
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,one of them is better than the other.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You now have an N times M trace, where\Nyou have to guess up and down, which
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,one am I doing, backtrack back and forth\Nand all, and it's going to be horrible.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And this contrived example can of course\Nbe solved by some solvers that can see
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,the pattern, but you can always a\Nmore contrived pattern
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,that's harder to understand.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So I tried to keep it somewhat simple.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The good thing is, very few people write\Nsoftware like this.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And that is the most redeeming feature\Nabout the package ??.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We do have exceptions.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Aspell-dictionaries, ispell-dictionaries.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Basically if you depend on\Nispell-dictionary,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,which is a virtual package provided by 50\Ndifferent ispell packages,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,or aspell packages, and then they depend\Non something else after that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So in theory they can be a part of\Ncreating this problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Fortunately, they themselves are fairly\Nsimple once you've passed them.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You also have multiarch foreign, or\Nmultiarch allowed with
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,package interdependencies.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So if you have multiple architectures,\Nyou in theory can have any number
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,of things satisfying the same clause.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This gives extra unnecssary work for most\Nresolvers,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,if you enable them to do\Nmultiarch and cross things.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We have 12 of them, but I suspect most\Nusers of multiarch are somewhat limited
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,to maybe 3.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Possible exception being people like\Nwriting resolvers and trying them out,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,torture test them.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The real problem, if you had to do this in\Nthe archive you would need to do,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,for example something like, write\Nindifferent awk implementations.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We have three.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And then afterwards, for example,\Nhave m different distinct,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,but equally valid libc implementations.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It's not something we're likely to do in\Nthe near future.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And you have to do this on multiple\Nlevels,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,because you can just presolve the\Nessential set most of the time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The real problem: if you had to do this in\Nthe archive, you would need to do,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,for example, something like write\NN different awk implementations.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We have 3.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then afterwards for example, have\NM different distinct but equally valid
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,libc implementations.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It's not something we're likely to do\Nin the near future.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And you have to do this on multiple\Nlevels.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Because you can just presolve the\Nessential set most of the time,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,this particular thing is not very\Ninteresting.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And the data packages can in theory\Nblow up,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,when you have truly interchangable data,\Nlike we do with the aspell packages.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,But they tend to either not have any\Ndependencies after the aspell,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,after the data package, or they have a\Nsimple loopback into what you came from.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So the blowup blowup tends to be limited\Nto one level.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If you have enough of those, it's still\Ngoing to be a problem,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,but it keeps it simple.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Onto installing.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The easier case, as mentioned is when you\Nhave a single suit
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and a single architecture.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,All things in the graph collapse into\Nwhat looks like a regular graph,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and therefore become simple,\Ntrivial.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This actually happens so much that\Nif you take Lintian,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it has 26 distinct dependency clauses.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If you look at each of them,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,when you only have a single suite\Nand architecture, there's at most
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,one package directly solving each\Nclause locally.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then further down the graph somewhere\Nyou depend on for example, debconf,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,or debconf-2.0 which is one of these\Nalternatives, giving rise to its ??
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Linitan itself is not subject to becoming\Na backtrack point.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,There's no guesswork when you reach\NLintian, which of its dependencies
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,should I pick, which version of\Nit and all.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That's not there, you have to go further\Ndown to see that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Actually, but the time you reach the\Ndebconf thing,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it has already been solved by\Nsomething else, as I recall.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Oh, no wait. The dependencies of debconf\Nis already covered by the time you're
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,forced to resolve this choice,\Nso it's not really a big issue, either.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You just pick the debconf one, c-debconf\Ncurrently depends on debconf,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,so it's trivial that way.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The question is, when do we have\Nthese conditions.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We do that a lot actually.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If you do builts in unstable for example.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,??, only one suite only one architecture,\Npiece of cake.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If you install packages of a pure\NJessie system, with multiarch,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,you have the single suite one,\Nwhich limits a lot of them,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and then you have not the single\Narchitecture.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That's what it is, but in pure Squeeze,\Nyou won't have multiarch because
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,because it didn't work back then.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So that's even simpler.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Also you can do unstable + experimental,\Nor stable + backports if you fiddle a bit
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,with the end resolver and say that it is\Nnot allowed to pick experimental,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,unless it is explicitly requested to pick\Nexperimental,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and from there it only picks\Nwhat it absolutely needs to solve it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You basically get the same result with a\Nsingle suite restriction,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,but that requires you to actually code\Nsomething for it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And then there's Britney, with the testing\Nmigration thing, and that's because
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,she basically takes things, moves it into\Na new version of testing,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and tries to test that this is still\Nthe same solution.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So she forces it into a single\Nsuite currently.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So these are common cases where\Nit happens.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This is not everywhere where it happens,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,so the stable upgrades are still funny\Nenough, not a single suite and all that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It happens because there is only one\Npackage and architecture.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Only one instance of package, you only\Nhave one version, one architecture that
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,solves that particular dependency.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Whereas with multiarch you could have,\Ni386 and the amd64 version.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If you do an upgrade you could have the\Nold version and the new version
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,that may or may not satisfy it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Also we have this thing where we\Ndon't like libraries to have
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,alternative implementations, it sort of\Nbreaks things horribly.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Especially when they are not actually\Nagreeing on the interface they provide.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,There's the social aspect of it that we\Ndon't really bother having
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,200 interchangeable implementations of\Neverything.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I think the record is something like
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,five or six different versions\Nof sendmail, implemenatations.\N
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,??
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I don't think so, but ?? might have.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And even when you do have one of these\Nexplosions,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it has to actually hide the breakage\Nbeneath one of these choice
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,explosion alternative explosions for\Nit to be a problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You might have aspell over here on the\Nright hand side,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and you have a breakage over here which\N?? to find out.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So if you use the resolver to just the\Nfirst explosion to solve the other part,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it realizes this is not working,\NI'll bail out.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,There's a couple things that we do to\Nmake this easier.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The mos interesting thing is of course,\Ncan we still make this simple without
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,the single suite and single\Narchitecture restriction.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We can to some extent.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And that's where we move to upgrading,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,in deterministic polynomial time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This is where I spent most of my\Ntime working.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So to start with, when we do an upgrade\Nfrom stable to stable,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and here I'm taking pure stable, no\Nbackports and all.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The general recommended way to do it is\Nto replace Wheezy with Jessie,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,hit apt-get update, and\Nupgrade afterwards,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and apt replaces all the old packages with\Nthe new version,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,if there is a new version.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We also want all the packages from Wheezy\Nthat did not have any version in Jessie
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,to be removed, and there might be a new\Nessential package somewhere.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So long story short, upgrade if it's\Npresent, remove if it is not present,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and then install the new essential\Npackages, if any.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,They don't tend to change that often.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I'll be ignoring the installing part\Nfor now.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It is of course valid and interesting,\Nbut we'll skip it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So let's take a simple example, somewhat\Ncontrived, somewhat made up the numbers.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,They are not too far from reality, but\Nthey are not exact either.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We have have a system that we are\Nupgrading from Wheezy to Jessie.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I claim that there are 30 thousand\Npackages in Wheezy,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,we've got 35 thousand in Jessie.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The system we are working with has\Ntwo thousand packages installed.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Mine here has something like 1200.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If you do a simple dpkg -L
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and then do a line count, you can see\Nhow many you have on your system,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,plus-minus five or so, to give you an idea\Nof how many packages
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,you're actually working with.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We assume that all Wheezy package got a\Nnew version in Jessie,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,because I'm about to do a pop quiz!
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So with these numbers, what is the maximum\Nproblem size of this upgrade.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Any takers?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Is it 30?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Anyone for 35?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,37?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,One for 65.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,One for 67.5 thousand.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And who believes that I was an asshole\Nand did not include the right answer?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Oh, so little faith.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I'm glad you believe me.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The right answer is 35 thousand.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The trick is, when we do the upgrade, we\Nreplace Wheezy with Jessie,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,we do an update, so all the Wheezy\Npackages not installed
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,on our system disappears.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then you get all of the Jessie packages,\Nwith the assumption that
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,no Jessie packages have a new version\Ncompared to Wheezy.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You've got the two thousand from\NWheezy on your system,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,plus the 35 thousand\Npackages from Jessie.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So that means your average\Nstable-to-stable upgrade,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,if you do it this way, is actually only\Nabout 40% of the worst case
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,that it could've been if you kept the\Nold stable as well.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,There's also another awesome feature with\Nremoving the old stable repository.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It means that every time you\Nupgrade a package,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,your effective problem size\Ndecreased by one.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That's not always useful, it's not\Nalways awesome,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and it's not always the thing that solves\Nyour problem,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,but it means that if you can actually make\Napt upgrade a single thing
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,every now and then, eventually it might\Nbe able to figure out the rest of
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,the upgrade path, after ??\N200 packages or so.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,As we upgrade, we end up to moving towards\Na single suite situation,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,so the more things we upgrade, the more we\Nget to a single suite situation.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Again, most ?? pure stable to stable\Nupgrades.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And of course the right answer would've\Nbeen 65 thousand packages
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,if you kept your stable.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So that would've been a possible\Nanswer as well.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Now upgrading.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This should be as easy as mark new\Nessential packages for install,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Mark everything that has a new version for\Nupgrade, remove stuff,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and then figure out if something is\Nmissing, then install that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This solves upgrading by installing, so\NI'm not really interested in doing this,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,because installing is hard.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We can do something smarter than\Nthat for upgrading.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,When we do upgrades in a polynomial\Ndeterministic time,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I'm not going to give you a 100% solution,\Nthat's not going to work.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If I could, I would be very very rich.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So, I intended this to sort of find some\Neasy low hanging fruits
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,that can be solved cheaply, and then you can\Nthrow a general purpose resolver at
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,the rest of the problem, after you've done\Nthe simple parts.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Or you can feed your solver a partial\Nsolution and ask it to fix it up
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,so it would be a slightly\Nsmaller problem size.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It relies on two things.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,One, it exploits a lot of common patterns\Non how we do dependencies.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And the other thing is, if you have a\Nvalid system state,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,so if you have a system where all of your\Npackages are in fact installable,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,which dpkg tends to enforce,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,you can verify that is true\Nin polynomial time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You can also verify a change to it in\Npolynomial time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So here I'm going to do a bit of theory,\Nand a bit of English inbetween.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We start with a not-broken system,\Nthat is we have a set of installable
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,packages that are mutually\Nco-installable and all that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We call that 'I'.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then we can add things to I, we can remove\Nthings from this set, we can take something
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,in the set and replace it with something else,\Nbasically add and remove.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That can be done in linear time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If I take a random package, mash it in,\Nthat's constant, maybe,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,depending on your implementation.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The theory is we can compute a new\Nset, where we remove something,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,add something else, we get a new set.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then we can verify this new set is indeed\Nstill a valid solution in polynomial time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So, a constant time modification\Ncan be verified in polynomial time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The issue of the day is, randomly feeding\Npackages in and out of the set
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,is not going to work very well.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So we need something smarter than\Njust random modifications.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Ah well, somebody might actually write\Nsomething that works with that but anyway.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So the first thing I did,\Nas I mentioned earlier,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,we have these exclusively equal\Ndependencies inside binaries,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,?? binaries from the same source.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So I grouped binaries from the same source.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If I was to mark one of them for upgrade,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I would immediately pull the rest of\Nthem as well, if they were installed.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It also happens to sort out a very\Ncommon case of breaks-replaces,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,when you move files between two binaries\Nin the same source.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then you just try to upgrade each of these\Ngroups, in some order.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Preferably deterministically,\Nbut I didn't get that far.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And if the result of one of these\Nmodifications is upgradable,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,we can test that fairly cheap, we commit\Nit, and you just rinse-and-repeat
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,until you run out of things to test,\Nthat leads to something new.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This works largely depending\Non what you have installed,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,unsurpisingly.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So if you have very few packages,\Nit may work better than if you have more,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And sometimes it works better when you\Nhave more, and that's really exciting.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So I did an example Wheezy installation\Nbased on what I have installed
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,on my machine.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Not quite, but close, well related.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So libc for example was immediately\Nupgradable by this procedure.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,As well as some Java package,\Nworked fine.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,man-db, eclipse, xterm, then I had to do a\Ncouple packages before that,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,which were all upgradable.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I think libc was primarily ?? and maybe\Nsome libc linux thing.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,But there are actually a set of packages\Nyou can upgrade with this.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This is of course not testing on\Nconfigurations.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,In this particular configuration, I could\Nupgrade dpkg like this,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,but I don't expect you to be able\Nto do that in all cases.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,In fact I find it highly unlikely\Nbecause in Wheezy to Jessie,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,dpkg has tons of breaks for\Nall sorts of things,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,so if you have the right thing there,\Nyou break something else,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and that has to be upgraded\Nat the same time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And that is sure to build\Na loop eventually.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So basically what we are exploiting here\Nis the greater-than-equal version,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,which is the common way of doing things.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We rebuild a package, it gets the new\Ndependencies on a higher
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,version of things.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That means the foo in stable ??.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Right so, everything depending on foo is\Nequally happy with the version
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,in Jessie as well, cause it's a lower\Nbound, and Jessie has a newer version.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So that works very well.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This is the common case for libraries\Nwithout ABI transitions.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Apparently including libc
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and enables you to upgrade from the inside\Nout, from the core of the onion and out,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,if you think of the graph as an onion.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The algorithm is fairly dumb,\Nunsurprisingly.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It cannot solve Perl, it can't talk Python\Nbecause they tend to involve
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,pulling in a new package so you have to\Ninstall that and all that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,In Perl it could technically solve if it\Nwould merge groups together
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,into larger groups, but anyway the runtime\Nof this is something like I2 * I+E.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Which is upper bound by\NI to the power of 4.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So it's fairly cheap, it is fairly polynomial.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It's very trivial to do.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We can do better than that as mentioned,\Nif we can have it figure out that
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,dpkg needs a new version of libc,\Nwe could upgrade those together.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That's not a problem on my system,\Nbut it might be on others.