9:59:59.000,9:59:59.000 (Offscreen) So welcome to the talk from Niels 9:59:59.000,9:59:59.000 about dependency resolution in[br]polynomial time. 9:59:59.000,9:59:59.000 (Neils) I'm Neils, I'm doing my second[br]talk today. 9:59:59.000,9:59:59.000 This time about something slightly[br]more technical. 9:59:59.000,9:59:59.000 I wanted to do dependency resolution[br]in deterministic polynomial time, 9:59:59.000,9:59:59.000 which is what this is all about. 9:59:59.000,9:59:59.000 I didn't get as far with this as I wanted. 9:59:59.000,9:59:59.000 I wanted to have a tool ready and have[br]some results, which I didn't quite finish. 9:59:59.000,9:59:59.000 So these will be my findings work in[br]progress notes. 9:59:59.000,9:59:59.000 We have six topics I have to cover. 9:59:59.000,9:59:59.000 A quick introduction. 9:59:59.000,9:59:59.000 Then something about the hard problem. 9:59:59.000,9:59:59.000 Then the part the part where it actually[br]turns out to be highly tractable 9:59:59.000,9:59:59.000 in practice, if you don't think too much[br]about it. 9:59:59.000,9:59:59.000 And then there is some installing,[br]upgrading, and installing again 9:59:59.000,9:59:59.000 for how to improve your solvers. 9:59:59.000,9:59:59.000 Starting with introduction. 9:59:59.000,9:59:59.000 I'm hoping mostly to debunk the myth[br]that dependency resolution is a very 9:59:59.000,9:59:59.000 hard problem that we cannot solve, 9:59:59.000,9:59:59.000 and we should remove packages in the hopes[br]that they will somehow keep the archive 9:59:59.000,9:59:59.000 from exploding, and the dependency[br]resolvers to break, and apt to die, 9:59:59.000,9:59:59.000 and god knows what. 9:59:59.000,9:59:59.000 I've been working on Britney, which is a[br]different problem to solve, but it 9:59:59.000,9:59:59.000 involves the same techniques, or uses some[br]of the same techniques. 9:59:59.000,9:59:59.000 Some will be directly applicable to apt,[br]some will not. 9:59:59.000,9:59:59.000 There's not a one size fits all solution, sorry. 9:59:59.000,9:59:59.000 And I much less haven't wrote it yet,[br]even if there was. 9:59:59.000,9:59:59.000 So defining the problem. 9:59:59.000,9:59:59.000 When you try to install a package on your[br]system, 9:59:59.000,9:59:59.000 there's actually two problems[br]being solved. 9:59:59.000,9:59:59.000 One is the part where apt figures out if I[br]have to install Eclipse. 9:59:59.000,9:59:59.000 You'll be needing a lot of Java packages,[br]you'll be needing a lot of other stuff. 9:59:59.000,9:59:59.000 And so it figures out which packages are[br]needed for this to make sense. 9:59:59.000,9:59:59.000 The separate part of the problem,[br]the second problem is, 9:59:59.000,9:59:59.000 once you have this list, they have to be[br]unpackaged and configured in a certain 9:59:59.000,9:59:59.000 order for this all to make sense. 9:59:59.000,9:59:59.000 They are in theory two distinct problems. 9:59:59.000,9:59:59.000 I'll be talking about the first problem, 9:59:59.000,9:59:59.000 because that's actually[br]dependency resolution. 9:59:59.000,9:59:59.000 The other thing is just ordering. 9:59:59.000,9:59:59.000 The ordering thing is certainly also very[br]important part. 9:59:59.000,9:59:59.000 I don't want to dismiss that, it's just 9:59:59.000,9:59:59.000 it is in fact theoretically a polynomial[br]time problem. 9:59:59.000,9:59:59.000 So to solve the ordering problem, you[br]basically compute all the action- 9:59:59.000,9:59:59.000 Given a set of actions that need[br]to be done, 9:59:59.000,9:59:59.000 then there are some constraints between[br]some of them, 9:59:59.000,9:59:59.000 like you unpack things before you[br]configure it. 9:59:59.000,9:59:59.000 Maybe you deconfigure something else[br]before that. 9:59:59.000,9:59:59.000 So you end up with a list of partial ??[br]constraints. 9:59:59.000,9:59:59.000 From that you build a graph with ordering. 9:59:59.000,9:59:59.000 It's fairly simple to do, in practice,[br]if you have the right tools for it. 9:59:59.000,9:59:59.000 Then without cycles, this is a trivial[br]things where it just orders it 9:59:59.000,9:59:59.000 and gives you this is the order,[br]go fix. 9:59:59.000,9:59:59.000 When there's cycles you will get a single[br]action consisting of multiple things 9:59:59.000,9:59:59.000 to do at the same time, which is really[br]impossible to do. 9:59:59.000,9:59:59.000 It turns out that the way we defined this[br]whole thing, 9:59:59.000,9:59:59.000 if you have a package that does not have a[br]post install script, 9:59:59.000,9:59:59.000 it does not need to be configured separately. 9:59:59.000,9:59:59.000 That means that it's just unpacked or[br]not unpacked. 9:59:59.000,9:59:59.000 That tends to break most cylcles. 9:59:59.000,9:59:59.000 If you want, there's problems with[br]ordering constraints. 9:59:59.000,9:59:59.000 Help us to find a way to get rid of most[br]of the post install scripts, 9:59:59.000,9:59:59.000 such as the ones just running lvconfig[br]and nothing else. 9:59:59.000,9:59:59.000 That could solve some of the cycles, 9:59:59.000,9:59:59.000 and otherwise it's just feeding it to dpkg[br]and it works. 9:59:59.000,9:59:59.000 If you have a cycle, it's a separate[br]problem fixing that. 9:59:59.000,9:59:59.000 I won't be covering that. 9:59:59.000,9:59:59.000 As I said, the runtime is polynomial. 9:59:59.000,9:59:59.000 It's something like the size of the[br]package, a regular graph. 9:59:59.000,9:59:59.000 Which is fairly polynomial. 9:59:59.000,9:59:59.000 This even covers finding cycles. 9:59:59.000,9:59:59.000 Again breaking cycles is just removing[br]post install scripts. 9:59:59.000,9:59:59.000 And of course if you think this is too[br]simple, 9:59:59.000,9:59:59.000 you can always implement more features[br]on top of it, 9:59:59.000,9:59:59.000 such as trying to optimize for minimal[br]downtime of services and all that. 9:59:59.000,9:59:59.000 You can make any trivial problem very hard[br]very soon with that. 9:59:59.000,9:59:59.000 So, the hard problem. 9:59:59.000,9:59:59.000 First of all, the players. 9:59:59.000,9:59:59.000 We've got apt, aptitude, cupt, whatever. 9:59:59.000,9:59:59.000 We've got Britney. 9:59:59.000,9:59:59.000 We've got DOSE, edos, whatever its[br]name is today. 9:59:59.000,9:59:59.000 They solve the hard problem. 9:59:59.000,9:59:59.000 Or they should be trying to do. 9:59:59.000,9:59:59.000 Notable tools not affected by it. 9:59:59.000,9:59:59.000 dpkg. 9:59:59.000,9:59:59.000 So dpkg surely figures out if you are[br]missing dependencies. It says, 9:59:59.000,9:59:59.000 "I cannot resolve this, and I don't know[br]where to fetch it, so I'm just giving up." 9:59:59.000,9:59:59.000 And that is the only thing you can do. 9:59:59.000,9:59:59.000 Which means it only verifies the solution[br]which is known to be polynomial, 9:59:59.000,9:59:59.000 and is therefore is not a game player. 9:59:59.000,9:59:59.000 DAK rm is also doing a polynomial time[br]check, it just happens to be so 9:59:59.000,9:59:59.000 for other reasons. 9:59:59.000,9:59:59.000 That's basically the known players. 9:59:59.000,9:59:59.000 There are probably others. 9:59:59.000,9:59:59.000 But we're moving onto the[br]hard problem itself 9:59:59.000,9:59:59.000 So the problem we actually have is, 9:59:59.000,9:59:59.000 we've got version dependencies,[br]we've got alternative choices, 9:59:59.000,9:59:59.000 we've got virtual packages. 9:59:59.000,9:59:59.000 All three makes this problem hard. 9:59:59.000,9:59:59.000 You basically have to remove all possible[br]alternative choices, guesses, whatever, 9:59:59.000,9:59:59.000 to make this simple. 9:59:59.000,9:59:59.000 It just so happens if you move version[br]dependencies among other things, 9:59:59.000,9:59:59.000 things become really fun. 9:59:59.000,9:59:59.000 ?? to solve the problem, but upgrading[br]gets really really spicy. 9:59:59.000,9:59:59.000 So how do we ensure that dpkg[br]is configured before your new package, 9:59:59.000,9:59:59.000 use a feature new dev package[br]is installed. 9:59:59.000,9:59:59.000 That's sort of impossible. 9:59:59.000,9:59:59.000 It becomes simple, but we end up with a[br]broken dependency ??, 9:59:59.000,9:59:59.000 so it's not really an option. 9:59:59.000,9:59:59.000 Technically there's also a way to make[br]it simple by having multiple versions 9:59:59.000,9:59:59.000 of things, and removing negative[br]dependencies, 9:59:59.000,9:59:59.000 but that's not necessarily easy to do either. 9:59:59.000,9:59:59.000 Presumably file configs will get in our[br]way or something. 9:59:59.000,9:59:59.000 We have to redefine where we place all of[br]the files, that's not going to be 9:59:59.000,9:59:59.000 something we're doing anytime soon. 9:59:59.000,9:59:59.000 So yeah, it's not really an option. 9:59:59.000,9:59:59.000 To give you a better understanding of the[br]problem, please consider this example. 9:59:59.000,9:59:59.000 If we have coreutils at some version,[br]depending on either this version 9:59:59.000,9:59:59.000 of libc or a newer one. 9:59:59.000,9:59:59.000 From this can we immediately conclude 9:59:59.000,9:59:59.000 that if libc 2.19 is known to be[br]installable, 9:59:59.000,9:59:59.000 that coreutils will also be installable? 9:59:59.000,9:59:59.000 How many people think we can immediately[br]conclude something from this? 9:59:59.000,9:59:59.000 How many people think we cannot[br]conclude anything from this? 9:59:59.000,9:59:59.000 We'll that's good. 9:59:59.000,9:59:59.000 So it turns out that with negative[br]dependencies and without negative 9:59:59.000,9:59:59.000 dependencies, it doesn't really matter. 9:59:59.000,9:59:59.000 With negative dependencies, libc or[br]whatever it depends on could 9:59:59.000,9:59:59.000 just conflict with coreutils, we're[br]broken, it's out. 9:59:59.000,9:59:59.000 And without negative dependencies, you[br]could have one of the things where 9:59:59.000,9:59:59.000 it depends on a version that's newer or[br]older, and no. 9:59:59.000,9:59:59.000 It's not really trivial to do. 9:59:59.000,9:59:59.000 You can't conclude something locally,[br]in theory. 9:59:59.000,9:59:59.000 That's something that can[br]become a problem. 9:59:59.000,9:59:59.000 Anyway, it is highly tractable in practice.