WEBVTT 99:59:59.999 --> 99:59:59.999 (Offscreen) So welcome to the talk from Niels 99:59:59.999 --> 99:59:59.999 about dependency resolution in polynomial time. 99:59:59.999 --> 99:59:59.999 (Neils) I'm Neils, I'm doing my second talk today. 99:59:59.999 --> 99:59:59.999 This time about something slightly more technical. 99:59:59.999 --> 99:59:59.999 I wanted to do dependency resolution in deterministic polynomial time, 99:59:59.999 --> 99:59:59.999 which is what this is all about. 99:59:59.999 --> 99:59:59.999 I didn't get as far with this as I wanted. 99:59:59.999 --> 99:59:59.999 I wanted to have a tool ready and have some results, which I didn't quite finish. 99:59:59.999 --> 99:59:59.999 So these will be my findings work in progress notes. 99:59:59.999 --> 99:59:59.999 We have six topics I have to cover. 99:59:59.999 --> 99:59:59.999 A quick introduction. 99:59:59.999 --> 99:59:59.999 Then something about the hard problem. 99:59:59.999 --> 99:59:59.999 Then the part the part where it actually turns out to be highly tractable 99:59:59.999 --> 99:59:59.999 in practice, if you don't think too much about it. 99:59:59.999 --> 99:59:59.999 And then there is some installing, upgrading, and installing again 99:59:59.999 --> 99:59:59.999 for how to improve your solvers. 99:59:59.999 --> 99:59:59.999 Starting with introduction. 99:59:59.999 --> 99:59:59.999 I'm hoping mostly to debunk the myth that dependency resolution is a very 99:59:59.999 --> 99:59:59.999 hard problem that we cannot solve, 99:59:59.999 --> 99:59:59.999 and we should remove packages in the hopes that they will somehow keep the archive 99:59:59.999 --> 99:59:59.999 from exploding, and the dependency resolvers to break, and apt to die, 99:59:59.999 --> 99:59:59.999 and god knows what. 99:59:59.999 --> 99:59:59.999 I've been working on Britney, which is a different problem to solve, but it 99:59:59.999 --> 99:59:59.999 involves the same techniques, or uses some of the same techniques. 99:59:59.999 --> 99:59:59.999 Some will be directly applicable to apt, some will not. 99:59:59.999 --> 99:59:59.999 There's not a one size fits all solution, sorry. 99:59:59.999 --> 99:59:59.999 And I much less haven't wrote it yet, even if there was. 99:59:59.999 --> 99:59:59.999 So defining the problem. 99:59:59.999 --> 99:59:59.999 When you try to install a package on your system, 99:59:59.999 --> 99:59:59.999 there's actually two problems being solved. 99:59:59.999 --> 99:59:59.999 One is the part where apt figures out if I have to install Eclipse. 99:59:59.999 --> 99:59:59.999 You'll be needing a lot of Java packages, you'll be needing a lot of other stuff. 99:59:59.999 --> 99:59:59.999 And so it figures out which packages are needed for this to make sense. 99:59:59.999 --> 99:59:59.999 The separate part of the problem, the second problem is, 99:59:59.999 --> 99:59:59.999 once you have this list, they have to be unpackaged and configured in a certain 99:59:59.999 --> 99:59:59.999 order for this all to make sense. 99:59:59.999 --> 99:59:59.999 They are in theory two distinct problems. 99:59:59.999 --> 99:59:59.999 I'll be talking about the first problem, 99:59:59.999 --> 99:59:59.999 because that's actually dependency resolution. 99:59:59.999 --> 99:59:59.999 The other thing is just ordering. 99:59:59.999 --> 99:59:59.999 The ordering thing is certainly also very important part. 99:59:59.999 --> 99:59:59.999 I don't want to dismiss that, it's just 99:59:59.999 --> 99:59:59.999 it is in fact theoretically a polynomial time problem. 99:59:59.999 --> 99:59:59.999 So to solve the ordering problem, you basically compute all the action- 99:59:59.999 --> 99:59:59.999 Given a set of actions that need to be done, 99:59:59.999 --> 99:59:59.999 then there are some constraints between some of them, 99:59:59.999 --> 99:59:59.999 like you unpack things before you configure it. 99:59:59.999 --> 99:59:59.999 Maybe you deconfigure something else before that. 99:59:59.999 --> 99:59:59.999 So you end up with a list of partial ?? constraints. 99:59:59.999 --> 99:59:59.999 From that you build a graph with ordering. 99:59:59.999 --> 99:59:59.999 It's fairly simple to do, in practice, if you have the right tools for it. 99:59:59.999 --> 99:59:59.999 Then without cycles, this is a trivial things where it just orders it 99:59:59.999 --> 99:59:59.999 and gives you this is the order, go fix. 99:59:59.999 --> 99:59:59.999 When there's cycles you will get a single action consisting of multiple things 99:59:59.999 --> 99:59:59.999 to do at the same time, which is really impossible to do. 99:59:59.999 --> 99:59:59.999 It turns out that the way we defined this whole thing, 99:59:59.999 --> 99:59:59.999 if you have a package that does not have a post install script, 99:59:59.999 --> 99:59:59.999 it does not need to be configured separately. 99:59:59.999 --> 99:59:59.999 That means that it's just unpacked or not unpacked. 99:59:59.999 --> 99:59:59.999 That tends to break most cylcles. 99:59:59.999 --> 99:59:59.999 If you want, there's problems with ordering constraints. 99:59:59.999 --> 99:59:59.999 Help us to find a way to get rid of most of the post install scripts, 99:59:59.999 --> 99:59:59.999 such as the ones just running lvconfig and nothing else. 99:59:59.999 --> 99:59:59.999 That could solve some of the cycles, 99:59:59.999 --> 99:59:59.999 and otherwise it's just feeding it to dpkg and it works. 99:59:59.999 --> 99:59:59.999 If you have a cycle, it's a separate problem fixing that. 99:59:59.999 --> 99:59:59.999 I won't be covering that. 99:59:59.999 --> 99:59:59.999 As I said, the runtime is polynomial. 99:59:59.999 --> 99:59:59.999 It's something like the size of the package, a regular graph. 99:59:59.999 --> 99:59:59.999 Which is fairly polynomial. 99:59:59.999 --> 99:59:59.999 This even covers finding cycles. 99:59:59.999 --> 99:59:59.999 Again breaking cycles is just removing post install scripts. 99:59:59.999 --> 99:59:59.999 And of course if you think this is too simple, 99:59:59.999 --> 99:59:59.999 you can always implement more features on top of it, 99:59:59.999 --> 99:59:59.999 such as trying to optimize for minimal downtime of services and all that. 99:59:59.999 --> 99:59:59.999 You can make any trivial problem very hard very soon with that.