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. 99:59:59.999 --> 99:59:59.999 So, the hard problem. 99:59:59.999 --> 99:59:59.999 First of all, the players. 99:59:59.999 --> 99:59:59.999 We've got apt, aptitude, cupt, whatever. 99:59:59.999 --> 99:59:59.999 We've got Britney. 99:59:59.999 --> 99:59:59.999 We've got DOSE, edos, whatever its name is today. 99:59:59.999 --> 99:59:59.999 They solve the hard problem. 99:59:59.999 --> 99:59:59.999 Or they should be trying to do. 99:59:59.999 --> 99:59:59.999 Notable tools not affected by it. 99:59:59.999 --> 99:59:59.999 dpkg. 99:59:59.999 --> 99:59:59.999 So dpkg surely figures out if you are missing dependencies. It says, 99:59:59.999 --> 99:59:59.999 "I cannot resolve this, and I don't know where to fetch it, so I'm just giving up." 99:59:59.999 --> 99:59:59.999 And that is the only thing you can do. 99:59:59.999 --> 99:59:59.999 Which means it only verifies the solution which is known to be polynomial, 99:59:59.999 --> 99:59:59.999 and is therefore is not a game player. 99:59:59.999 --> 99:59:59.999 DAK rm is also doing a polynomial time check, it just happens to be so 99:59:59.999 --> 99:59:59.999 for other reasons. 99:59:59.999 --> 99:59:59.999 That's basically the known players. 99:59:59.999 --> 99:59:59.999 There are probably others. 99:59:59.999 --> 99:59:59.999 But we're moving onto the hard problem itself 99:59:59.999 --> 99:59:59.999 So the problem we actually have is, 99:59:59.999 --> 99:59:59.999 we've got version dependencies, we've got alternative choices, 99:59:59.999 --> 99:59:59.999 we've got virtual packages. 99:59:59.999 --> 99:59:59.999 All three makes this problem hard. 99:59:59.999 --> 99:59:59.999 You basically have to remove all possible alternative choices, guesses, whatever, 99:59:59.999 --> 99:59:59.999 to make this simple. 99:59:59.999 --> 99:59:59.999 It just so happens if you move version dependencies among other things, 99:59:59.999 --> 99:59:59.999 things become really fun. 99:59:59.999 --> 99:59:59.999 ?? to solve the problem, but upgrading gets really really spicy. 99:59:59.999 --> 99:59:59.999 So how do we ensure that dpkg is configured before your new package, 99:59:59.999 --> 99:59:59.999 use a feature new dev package is installed. 99:59:59.999 --> 99:59:59.999 That's sort of impossible. 99:59:59.999 --> 99:59:59.999 It becomes simple, but we end up with a broken dependency ??, 99:59:59.999 --> 99:59:59.999 so it's not really an option. 99:59:59.999 --> 99:59:59.999 Technically there's also a way to make it simple by having multiple versions 99:59:59.999 --> 99:59:59.999 of things, and removing negative dependencies, 99:59:59.999 --> 99:59:59.999 but that's not necessarily easy to do either. 99:59:59.999 --> 99:59:59.999 Presumably file configs will get in our way or something. 99:59:59.999 --> 99:59:59.999 We have to redefine where we place all of the files, that's not going to be 99:59:59.999 --> 99:59:59.999 something we're doing anytime soon. 99:59:59.999 --> 99:59:59.999 So yeah, it's not really an option. 99:59:59.999 --> 99:59:59.999 To give you a better understanding of the problem, please consider this example. 99:59:59.999 --> 99:59:59.999 If we have coreutils at some version, depending on either this version 99:59:59.999 --> 99:59:59.999 of libc or a newer one. 99:59:59.999 --> 99:59:59.999 From this can we immediately conclude 99:59:59.999 --> 99:59:59.999 that if libc 2.19 is known to be installable, 99:59:59.999 --> 99:59:59.999 that coreutils will also be installable? 99:59:59.999 --> 99:59:59.999 How many people think we can immediately conclude something from this? 99:59:59.999 --> 99:59:59.999 How many people think we cannot conclude anything from this? 99:59:59.999 --> 99:59:59.999 We'll that's good. 99:59:59.999 --> 99:59:59.999 So it turns out that with negative dependencies and without negative 99:59:59.999 --> 99:59:59.999 dependencies, it doesn't really matter. 99:59:59.999 --> 99:59:59.999 With negative dependencies, libc or whatever it depends on could 99:59:59.999 --> 99:59:59.999 just conflict with coreutils, we're broken, it's out. 99:59:59.999 --> 99:59:59.999 And without negative dependencies, you could have one of the things where 99:59:59.999 --> 99:59:59.999 it depends on a version that's newer or older, and no. 99:59:59.999 --> 99:59:59.999 It's not really trivial to do. 99:59:59.999 --> 99:59:59.999 You can't conclude something locally, in theory. 99:59:59.999 --> 99:59:59.999 That's something that can become a problem. 99:59:59.999 --> 99:59:59.999 Anyway, it is highly tractable in practice. 99:59:59.999 --> 99:59:59.999 Because if you do have a break, conflicts, or otherwise negative dependency, 99:59:59.999 --> 99:59:59.999 it tends to be upper bound. 99:59:59.999 --> 99:59:59.999 So if the previous version of coreutils was installable with that version, 99:59:59.999 --> 99:59:59.999 the new version will also probably be. 99:59:59.999 --> 99:59:59.999 Likewise, most dependencies, circular or otherwise, tend to be upper bound. 99:59:59.999 --> 99:59:59.999 There are cases of version ranges which is a lower bound and upper bound 99:59:59.999 --> 99:59:59.999 at the same time. 99:59:59.999 --> 99:59:59.999 They exist, they are just not so common yet. 99:59:59.999 --> 99:59:59.999 And that's a good thing. 99:59:59.999 --> 99:59:59.999 The number of possible solutions to any clause 99:59:59.999 --> 99:59:59.999 actually tends to be fairly limited. 99:59:59.999 --> 99:59:59.999 Of course there are the exceptions. 99:59:59.999 --> 99:59:59.999 Packages from unstable. 99:59:59.999 --> 99:59:59.999 They might just be missing, in which case it's really hard to solve the dependency. 99:59:59.999 --> 99:59:59.999 You've got mutually exclusive packages all the sendmail stuff, MTAs. 99:59:59.999 --> 99:59:59.999 The version ranges I mentioned before. 99:59:59.999 --> 99:59:59.999 And then of course the strictly equal versions, which we see inside 99:59:59.999 --> 99:59:59.999 packages built from the same source packages. 99:59:59.999 --> 99:59:59.999 The redeeming feature here: same source. 99:59:59.999 --> 99:59:59.999 Because that is actually very simple to figure out 99:59:59.999 --> 99:59:59.999 if they are from the same source. 99:59:59.999 --> 99:59:59.999 So they tend to be upgraded ?? anyhow. 99:59:59.999 --> 99:59:59.999 The new versions tend to be available at the same time sorta thing. 99:59:59.999 --> 99:59:59.999 The problem made hard in a nutshell, is this contrived example for example. 99:59:59.999 --> 99:59:59.999 You have a package you want to try, and it depends on any number of foos. 99:59:59.999 --> 99:59:59.999 Each of the foos can either be solved by 99:59:59.999 --> 99:59:59.999 picking up the bar package or the good one. 99:59:59.999 --> 99:59:59.999 Which might be a hint to which one we would choose if we want to solve it. 99:59:59.999 --> 99:59:59.999 And the bar packages, depends on a bad package that does not work 99:59:59.999 --> 99:59:59.999 with the starting-package, and we are broken. 99:59:59.999 --> 99:59:59.999 And the good package just doesn't have any dependencies and is therefore good. 99:59:59.999 --> 99:59:59.999 In the perfect example you saw, 99:59:59.999 --> 99:59:59.999 you try foo, good, foo1, and then good and be done. 99:59:59.999 --> 99:59:59.999 In practice, if you don't have some way of ordering these so you know 99:59:59.999 --> 99:59:59.999 one of them is better than the other. 99:59:59.999 --> 99:59:59.999 You now have an N times M trace, where you have to guess up and down, which 99:59:59.999 --> 99:59:59.999 one am I doing, backtrack back and forth and all, and it's going to be horrible. 99:59:59.999 --> 99:59:59.999 And this contrived example can of course be solved by some solvers that can see 99:59:59.999 --> 99:59:59.999 the pattern, but you can always a more contrived pattern 99:59:59.999 --> 99:59:59.999 that's harder to understand. 99:59:59.999 --> 99:59:59.999 So I tried to keep it somewhat simple. 99:59:59.999 --> 99:59:59.999 The good thing is, very few people write software like this. 99:59:59.999 --> 99:59:59.999 And that is the most redeeming feature about the package ??. 99:59:59.999 --> 99:59:59.999 We do have exceptions. 99:59:59.999 --> 99:59:59.999 Aspell-dictionaries, ispell-dictionaries. 99:59:59.999 --> 99:59:59.999 Basically if you depend on ispell-dictionary, 99:59:59.999 --> 99:59:59.999 which is a virtual package provided by 50 different ispell packages, 99:59:59.999 --> 99:59:59.999 or aspell packages, and then they depend on something else after that. 99:59:59.999 --> 99:59:59.999 So in theory they can be a part of creating this problem. 99:59:59.999 --> 99:59:59.999 Fortunately, they themselves are fairly simple once you've passed them. 99:59:59.999 --> 99:59:59.999 You also have multiarch foreign, or multiarch allowed with 99:59:59.999 --> 99:59:59.999 package interdependencies. 99:59:59.999 --> 99:59:59.999 So if you have multiple architectures, you in theory can have any number 99:59:59.999 --> 99:59:59.999 of things satisfying the same clause. 99:59:59.999 --> 99:59:59.999 This gives extra unnecssary work for most resolvers, 99:59:59.999 --> 99:59:59.999 if you enable them to do multiarch and cross things. 99:59:59.999 --> 99:59:59.999 We have 12 of them, but I suspect most users of multiarch are somewhat limited 99:59:59.999 --> 99:59:59.999 to maybe 3. 99:59:59.999 --> 99:59:59.999 Possible exception being people like writing resolvers and trying them out, 99:59:59.999 --> 99:59:59.999 torture test them. 99:59:59.999 --> 99:59:59.999 The real problem, if you had to do this in the archive you would need to do, 99:59:59.999 --> 99:59:59.999 for example something like, write indifferent awk implementations. 99:59:59.999 --> 99:59:59.999 We have three. 99:59:59.999 --> 99:59:59.999 And then afterwards, for example, have m different distinct, 99:59:59.999 --> 99:59:59.999 but equally valid libc implementations. 99:59:59.999 --> 99:59:59.999 It's not something we're likely to do in the near future. 99:59:59.999 --> 99:59:59.999 And you have to do this on multiple levels, 99:59:59.999 --> 99:59:59.999 because you can just presolve the essential set most of the time. 99:59:59.999 --> 99:59:59.999 The real problem: if you had to do this in the archive, you would need to do, 99:59:59.999 --> 99:59:59.999 for example, something like write N different awk implementations. 99:59:59.999 --> 99:59:59.999 We have 3. 99:59:59.999 --> 99:59:59.999 Then afterwards for example, have M different distinct but equally valid 99:59:59.999 --> 99:59:59.999 libc implementations. 99:59:59.999 --> 99:59:59.999 It's not something we're likely to do in the near future. 99:59:59.999 --> 99:59:59.999 And you have to do this on multiple levels. 99:59:59.999 --> 99:59:59.999 Because you can just presolve the essential set most of the time, 99:59:59.999 --> 99:59:59.999 this particular thing is not very interesting. 99:59:59.999 --> 99:59:59.999 And the data packages can in theory blow up, 99:59:59.999 --> 99:59:59.999 when you have truly interchangable data, like we do with the aspell packages. 99:59:59.999 --> 99:59:59.999 But they tend to either not have any dependencies after the aspell, 99:59:59.999 --> 99:59:59.999 after the data package, or they have a simple loopback into what you came from. 99:59:59.999 --> 99:59:59.999 So the blowup blowup tends to be limited to one level. 99:59:59.999 --> 99:59:59.999 If you have enough of those, it's still going to be a problem, 99:59:59.999 --> 99:59:59.999 but it keeps it simple. 99:59:59.999 --> 99:59:59.999 Onto installing. 99:59:59.999 --> 99:59:59.999 The easier case, as mentioned is when you have a single suit 99:59:59.999 --> 99:59:59.999 and a single architecture. 99:59:59.999 --> 99:59:59.999 All things in the graph collapse into what looks like a regular graph, 99:59:59.999 --> 99:59:59.999 and therefore become simple, trivial. 99:59:59.999 --> 99:59:59.999 This actually happens so much that if you take Lintian, 99:59:59.999 --> 99:59:59.999 it has 26 distinct dependency clauses. 99:59:59.999 --> 99:59:59.999 If you look at each of them, 99:59:59.999 --> 99:59:59.999 when you only have a single suite and architecture, there's at most 99:59:59.999 --> 99:59:59.999 one package directly solving each clause locally. 99:59:59.999 --> 99:59:59.999 Then further down the graph somewhere you depend on for example, debconf, 99:59:59.999 --> 99:59:59.999 or debconf-2.0 which is one of these alternatives, giving rise to its ?? 99:59:59.999 --> 99:59:59.999 Linitan itself is not subject to becoming a backtrack point. 99:59:59.999 --> 99:59:59.999 There's no guesswork when you reach Lintian, which of its dependencies 99:59:59.999 --> 99:59:59.999 should I pick, which version of it and all. 99:59:59.999 --> 99:59:59.999 That's not there, you have to go further down to see that. 99:59:59.999 --> 99:59:59.999 Actually, but the time you reach the debconf thing, 99:59:59.999 --> 99:59:59.999 it has already been solved by something else, as I recall. 99:59:59.999 --> 99:59:59.999 Oh, no wait. The dependencies of debconf is already covered by the time you're 99:59:59.999 --> 99:59:59.999 forced to resolve this choice, so it's not really a big issue, either. 99:59:59.999 --> 99:59:59.999 You just pick the debconf one, c-debconf currently depends on debconf, 99:59:59.999 --> 99:59:59.999 so it's trivial that way. 99:59:59.999 --> 99:59:59.999 The question is, when do we have these conditions. 99:59:59.999 --> 99:59:59.999 We do that a lot actually. 99:59:59.999 --> 99:59:59.999 If you do builts in unstable for example. 99:59:59.999 --> 99:59:59.999 ??, only one suite only one architecture, piece of cake. 99:59:59.999 --> 99:59:59.999 If you install packages of a pure Jessie system, with multiarch, 99:59:59.999 --> 99:59:59.999 you have the single suite one, which limits a lot of them, 99:59:59.999 --> 99:59:59.999 and then you have not the single architecture. 99:59:59.999 --> 99:59:59.999 That's what it is, but in pure Squeeze, you won't have multiarch because 99:59:59.999 --> 99:59:59.999 because it didn't work back then. 99:59:59.999 --> 99:59:59.999 So that's even simpler. 99:59:59.999 --> 99:59:59.999 Also you can do unstable + experimental, or stable + backports if you fiddle a bit 99:59:59.999 --> 99:59:59.999 with the end resolver and say that it is not allowed to pick experimental, 99:59:59.999 --> 99:59:59.999 unless it is explicitly requested to pick experimental, 99:59:59.999 --> 99:59:59.999 and from there it only picks what it absolutely needs to solve it. 99:59:59.999 --> 99:59:59.999 You basically get the same result with a single suite restriction, 99:59:59.999 --> 99:59:59.999 but that requires you to actually code something for it. 99:59:59.999 --> 99:59:59.999 And then there's Britney, with the testing migration thing, and that's because 99:59:59.999 --> 99:59:59.999 she basically takes things, moves it into a new version of testing, 99:59:59.999 --> 99:59:59.999 and tries to test that this is still the same solution. 99:59:59.999 --> 99:59:59.999 So she forces it into a single suite currently. 99:59:59.999 --> 99:59:59.999 So these are common cases where it happens. 99:59:59.999 --> 99:59:59.999 This is not everywhere where it happens, 99:59:59.999 --> 99:59:59.999 so the stable upgrades are still funny enough, not a single suite and all that. 99:59:59.999 --> 99:59:59.999 It happens because there is only one package and architecture. 99:59:59.999 --> 99:59:59.999 Only one instance of package, you only have one version, one architecture that 99:59:59.999 --> 99:59:59.999 solves that particular dependency. 99:59:59.999 --> 99:59:59.999 Whereas with multiarch you could have, i386 and the amd64 version. 99:59:59.999 --> 99:59:59.999 If you do an upgrade you could have the old version and the new version 99:59:59.999 --> 99:59:59.999 that may or may not satisfy it. 99:59:59.999 --> 99:59:59.999 Also we have this thing where we don't like libraries to have 99:59:59.999 --> 99:59:59.999 alternative implementations, it sort of breaks things horribly. 99:59:59.999 --> 99:59:59.999 Especially when they are not actually agreeing on the interface they provide. 99:59:59.999 --> 99:59:59.999 There's the social aspect of it that we don't really bother having 99:59:59.999 --> 99:59:59.999 200 interchangeable implementations of everything. 99:59:59.999 --> 99:59:59.999 I think the record is something like 99:59:59.999 --> 99:59:59.999 five or six different versions of sendmail, implemenatations. 99:59:59.999 --> 99:59:59.999 ?? 99:59:59.999 --> 99:59:59.999 I don't think so, but ?? might have. 99:59:59.999 --> 99:59:59.999 And even when you do have one of these explosions, 99:59:59.999 --> 99:59:59.999 it has to actually hide the breakage beneath one of these choice 99:59:59.999 --> 99:59:59.999 explosion alternative explosions for it to be a problem. 99:59:59.999 --> 99:59:59.999 You might have aspell over here on the right hand side, 99:59:59.999 --> 99:59:59.999 and you have a breakage over here which ?? to find out. 99:59:59.999 --> 99:59:59.999 So if you use the resolver to just the first explosion to solve the other part, 99:59:59.999 --> 99:59:59.999 it realizes this is not working, I'll bail out. 99:59:59.999 --> 99:59:59.999 There's a couple things that we do to make this easier. 99:59:59.999 --> 99:59:59.999 The mos interesting thing is of course, can we still make this simple without 99:59:59.999 --> 99:59:59.999 the single suite and single architecture restriction. 99:59:59.999 --> 99:59:59.999 We can to some extent. 99:59:59.999 --> 99:59:59.999 And that's where we move to upgrading, 99:59:59.999 --> 99:59:59.999 in deterministic polynomial time. 99:59:59.999 --> 99:59:59.999 This is where I spent most of my time working. 99:59:59.999 --> 99:59:59.999 So to start with, when we do an upgrade from stable to stable, 99:59:59.999 --> 99:59:59.999 and here I'm taking pure stable, no backports and all. 99:59:59.999 --> 99:59:59.999 The general recommended way to do it is to replace Wheezy with Jessie, 99:59:59.999 --> 99:59:59.999 hit apt-get update, and upgrade afterwards, 99:59:59.999 --> 99:59:59.999 and apt replaces all the old packages with the new version, 99:59:59.999 --> 99:59:59.999 if there is a new version. 99:59:59.999 --> 99:59:59.999 We also want all the packages from Wheezy that did not have any version in Jessie 99:59:59.999 --> 99:59:59.999 to be removed, and there might be a new essential package somewhere. 99:59:59.999 --> 99:59:59.999 So long story short, upgrade if it's present, remove if it is not present, 99:59:59.999 --> 99:59:59.999 and then install the new essential packages, if any. 99:59:59.999 --> 99:59:59.999 They don't tend to change that often. 99:59:59.999 --> 99:59:59.999 I'll be ignoring the installing part for now. 99:59:59.999 --> 99:59:59.999 It is of course valid and interesting, but we'll skip it. 99:59:59.999 --> 99:59:59.999 So let's take a simple example, somewhat contrived, somewhat made up the numbers. 99:59:59.999 --> 99:59:59.999 They are not too far from reality, but they are not exact either. 99:59:59.999 --> 99:59:59.999 We have have a system that we are upgrading from Wheezy to Jessie. 99:59:59.999 --> 99:59:59.999 I claim that there are 30 thousand packages in Wheezy, 99:59:59.999 --> 99:59:59.999 we've got 35 thousand in Jessie. 99:59:59.999 --> 99:59:59.999 The system we are working with has two thousand packages installed. 99:59:59.999 --> 99:59:59.999 Mine here has something like 1200. 99:59:59.999 --> 99:59:59.999 If you do a simple dpkg -L 99:59:59.999 --> 99:59:59.999 and then do a line count, you can see how many you have on your system, 99:59:59.999 --> 99:59:59.999 plus-minus five or so, to give you an idea of how many packages 99:59:59.999 --> 99:59:59.999 you're actually working with. 99:59:59.999 --> 99:59:59.999 We assume that all Wheezy package got a new version in Jessie, 99:59:59.999 --> 99:59:59.999 because I'm about to do a pop quiz! 99:59:59.999 --> 99:59:59.999 So with these numbers, what is the maximum problem size of this upgrade. 99:59:59.999 --> 99:59:59.999 Any takers? 99:59:59.999 --> 99:59:59.999 Is it 30? 99:59:59.999 --> 99:59:59.999 Anyone for 35? 99:59:59.999 --> 99:59:59.999 37? 99:59:59.999 --> 99:59:59.999 One for 65. 99:59:59.999 --> 99:59:59.999 One for 67.5 thousand. 99:59:59.999 --> 99:59:59.999 And who believes that I was an asshole and did not include the right answer? 99:59:59.999 --> 99:59:59.999 Oh, so little faith. 99:59:59.999 --> 99:59:59.999 I'm glad you believe me. 99:59:59.999 --> 99:59:59.999 The right answer is 35 thousand. 99:59:59.999 --> 99:59:59.999 The trick is, when we do the upgrade, we replace Wheezy with Jessie, 99:59:59.999 --> 99:59:59.999 we do an update, so all the Wheezy packages not installed 99:59:59.999 --> 99:59:59.999 on our system disappears. 99:59:59.999 --> 99:59:59.999 Then you get all of the Jessie packages, with the assumption that 99:59:59.999 --> 99:59:59.999 no Jessie packages have a new version compared to Wheezy. 99:59:59.999 --> 99:59:59.999 You've got the two thousand from Wheezy on your system, 99:59:59.999 --> 99:59:59.999 plus the 35 thousand packages from Jessie. 99:59:59.999 --> 99:59:59.999 So that means your average stable-to-stable upgrade, 99:59:59.999 --> 99:59:59.999 if you do it this way, is actually only about 40% of the worst case 99:59:59.999 --> 99:59:59.999 that it could've been if you kept the old stable as well. 99:59:59.999 --> 99:59:59.999 There's also another awesome feature with removing the old stable repository. 99:59:59.999 --> 99:59:59.999 It means that every time you upgrade a package, 99:59:59.999 --> 99:59:59.999 your effective problem size decreased by one. 99:59:59.999 --> 99:59:59.999 That's not always useful, it's not always awesome, 99:59:59.999 --> 99:59:59.999 and it's not always the thing that solves your problem, 99:59:59.999 --> 99:59:59.999 but it means that if you can actually make apt upgrade a single thing 99:59:59.999 --> 99:59:59.999 every now and then, eventually it might be able to figure out the rest of 99:59:59.999 --> 99:59:59.999 the upgrade path, after ?? 200 packages or so. 99:59:59.999 --> 99:59:59.999 As we upgrade, we end up to moving towards a single suite situation, 99:59:59.999 --> 99:59:59.999 so the more things we upgrade, the more we get to a single suite situation. 99:59:59.999 --> 99:59:59.999 Again, most ?? pure stable to stable upgrades. 99:59:59.999 --> 99:59:59.999 And of course the right answer would've been 65 thousand packages 99:59:59.999 --> 99:59:59.999 if you kept your stable. 99:59:59.999 --> 99:59:59.999 So that would've been a possible answer as well. 99:59:59.999 --> 99:59:59.999 Now upgrading. 99:59:59.999 --> 99:59:59.999 This should be as easy as mark new essential packages for install, 99:59:59.999 --> 99:59:59.999 Mark everything that has a new version for upgrade, remove stuff, 99:59:59.999 --> 99:59:59.999 and then figure out if something is missing, then install that. 99:59:59.999 --> 99:59:59.999 This solves upgrading by installing, so I'm not really interested in doing this, 99:59:59.999 --> 99:59:59.999 because installing is hard. 99:59:59.999 --> 99:59:59.999 We can do something smarter than that for upgrading. 99:59:59.999 --> 99:59:59.999 When we do upgrades in a polynomial deterministic time, 99:59:59.999 --> 99:59:59.999 I'm not going to give you a 100% solution, that's not going to work. 99:59:59.999 --> 99:59:59.999 If I could, I would be very very rich. 99:59:59.999 --> 99:59:59.999 So, I intended this to sort of find some easy low hanging fruits 99:59:59.999 --> 99:59:59.999 that can be solved cheaply, and then you can throw a general purpose resolver at 99:59:59.999 --> 99:59:59.999 the rest of the problem, after you've done the simple parts. 99:59:59.999 --> 99:59:59.999 Or you can feed your solver a partial solution and ask it to fix it up 99:59:59.999 --> 99:59:59.999 so it would be a slightly smaller problem size. 99:59:59.999 --> 99:59:59.999 It relies on two things. 99:59:59.999 --> 99:59:59.999 One, it exploits a lot of common patterns on how we do dependencies. 99:59:59.999 --> 99:59:59.999 And the other thing is, if you have a valid system state, 99:59:59.999 --> 99:59:59.999 so if you have a system where all of your packages are in fact installable, 99:59:59.999 --> 99:59:59.999 which dpkg tends to enforce, 99:59:59.999 --> 99:59:59.999 you can verify that is true in polynomial time. 99:59:59.999 --> 99:59:59.999 You can also verify a change to it in polynomial time. 99:59:59.999 --> 99:59:59.999 So here I'm going to do a bit of theory, and a bit of English inbetween. 99:59:59.999 --> 99:59:59.999 We start with a not-broken system, that is we have a set of installable 99:59:59.999 --> 99:59:59.999 packages that are mutually co-installable and all that. 99:59:59.999 --> 99:59:59.999 We call that 'I'. 99:59:59.999 --> 99:59:59.999 Then we can add things to I, we can remove things from this set, we can take something 99:59:59.999 --> 99:59:59.999 in the set and replace it with something else, basically add and remove. 99:59:59.999 --> 99:59:59.999 That can be done in linear time. 99:59:59.999 --> 99:59:59.999 If I take a random package, mash it in, that's constant, maybe, 99:59:59.999 --> 99:59:59.999 depending on your implementation. 99:59:59.999 --> 99:59:59.999 The theory is we can compute a new set, where we remove something, 99:59:59.999 --> 99:59:59.999 add something else, we get a new set. 99:59:59.999 --> 99:59:59.999 Then we can verify this new set is indeed still a valid solution in polynomial time. 99:59:59.999 --> 99:59:59.999 So, a constant time modification can be verified in polynomial time. 99:59:59.999 --> 99:59:59.999 The issue of the day is, randomly feeding packages in and out of the set 99:59:59.999 --> 99:59:59.999 is not going to work very well. 99:59:59.999 --> 99:59:59.999 So we need something smarter than just random modifications. 99:59:59.999 --> 99:59:59.999 Ah well, somebody might actually write something that works with that but anyway. 99:59:59.999 --> 99:59:59.999 So the first thing I did, as I mentioned earlier, 99:59:59.999 --> 99:59:59.999 we have these exclusively equal dependencies inside binaries, 99:59:59.999 --> 99:59:59.999 ?? binaries from the same source. 99:59:59.999 --> 99:59:59.999 So I grouped binaries from the same source. 99:59:59.999 --> 99:59:59.999 If I was to mark one of them for upgrade, 99:59:59.999 --> 99:59:59.999 I would immediately pull the rest of them as well, if they were installed. 99:59:59.999 --> 99:59:59.999 It also happens to sort out a very common case of breaks-replaces, 99:59:59.999 --> 99:59:59.999 when you move files between two binaries in the same source. 99:59:59.999 --> 99:59:59.999 Then you just try to upgrade each of these groups, in some order. 99:59:59.999 --> 99:59:59.999 Preferably deterministically, but I didn't get that far. 99:59:59.999 --> 99:59:59.999 And if the result of one of these modifications is upgradable, 99:59:59.999 --> 99:59:59.999 we can test that fairly cheap, we commit it, and you just rinse-and-repeat 99:59:59.999 --> 99:59:59.999 until you run out of things to test, that leads to something new. 99:59:59.999 --> 99:59:59.999 This works largely depending on what you have installed, 99:59:59.999 --> 99:59:59.999 unsurpisingly. 99:59:59.999 --> 99:59:59.999 So if you have very few packages, it may work better than if you have more, 99:59:59.999 --> 99:59:59.999 And sometimes it works better when you have more, and that's really exciting. 99:59:59.999 --> 99:59:59.999 So I did an example Wheezy installation based on what I have installed 99:59:59.999 --> 99:59:59.999 on my machine. 99:59:59.999 --> 99:59:59.999 Not quite, but close, well related. 99:59:59.999 --> 99:59:59.999 So libc for example was immediately upgradable by this procedure. 99:59:59.999 --> 99:59:59.999 As well as some Java package, worked fine. 99:59:59.999 --> 99:59:59.999 man-db, eclipse, xterm, then I had to do a couple packages before that, 99:59:59.999 --> 99:59:59.999 which were all upgradable. 99:59:59.999 --> 99:59:59.999 I think libc was primarily ?? and maybe some libc linux thing. 99:59:59.999 --> 99:59:59.999 But there are actually a set of packages you can upgrade with this. 99:59:59.999 --> 99:59:59.999 This is of course not testing on configurations. 99:59:59.999 --> 99:59:59.999 In this particular configuration, I could upgrade dpkg like this, 99:59:59.999 --> 99:59:59.999 but I don't expect you to be able to do that in all cases. 99:59:59.999 --> 99:59:59.999 In fact I find it highly unlikely because in Wheezy to Jessie, 99:59:59.999 --> 99:59:59.999 dpkg has tons of breaks for all sorts of things, 99:59:59.999 --> 99:59:59.999 so if you have the right thing there, you break something else, 99:59:59.999 --> 99:59:59.999 and that has to be upgraded at the same time. 99:59:59.999 --> 99:59:59.999 And that is sure to build a loop eventually. 99:59:59.999 --> 99:59:59.999 So basically what we are exploiting here is the greater-than-equal version, 99:59:59.999 --> 99:59:59.999 which is the common way of doing things. 99:59:59.999 --> 99:59:59.999 We rebuild a package, it gets the new dependencies on a higher 99:59:59.999 --> 99:59:59.999 version of things. 99:59:59.999 --> 99:59:59.999 That means the foo in stable ??. 99:59:59.999 --> 99:59:59.999 Right so, everything depending on foo is equally happy with the version 99:59:59.999 --> 99:59:59.999 in Jessie as well, cause it's a lower bound, and Jessie has a newer version. 99:59:59.999 --> 99:59:59.999 So that works very well. 99:59:59.999 --> 99:59:59.999 This is the common case for libraries without ABI transitions. 99:59:59.999 --> 99:59:59.999 Apparently including libc 99:59:59.999 --> 99:59:59.999 and enables you to upgrade from the inside out, from the core of the onion and out, 99:59:59.999 --> 99:59:59.999 if you think of the graph as an onion. 99:59:59.999 --> 99:59:59.999 The algorithm is fairly dumb, unsurprisingly. 99:59:59.999 --> 99:59:59.999 It cannot solve Perl, it can't talk Python because they tend to involve 99:59:59.999 --> 99:59:59.999 pulling in a new package so you have to install that and all that. 99:59:59.999 --> 99:59:59.999 In Perl it could technically solve if it would merge groups together 99:59:59.999 --> 99:59:59.999 into larger groups, but anyway the runtime of this is something like I2 * I+E. 99:59:59.999 --> 99:59:59.999 Which is upper bound by I to the power of 4. 99:59:59.999 --> 99:59:59.999 So it's fairly cheap, it is fairly polynomial. 99:59:59.999 --> 99:59:59.999 It's very trivial to do. 99:59:59.999 --> 99:59:59.999 We can do better than that as mentioned, if we can have it figure out that 99:59:59.999 --> 99:59:59.999 dpkg needs a new version of libc, we could upgrade those together. 99:59:59.999 --> 99:59:59.999 That's not a problem on my system, but it might be on others. 99:59:59.999 --> 99:59:59.999 Then there's the part where dpkg is breaking all of this stuff, 99:59:59.999 --> 99:59:59.999 so you might have to upgrade it at the same time, or before dpkg. 99:59:59.999 --> 99:59:59.999 Then end up with some sort of big loop or three structure of groups you have to 99:59:59.999 --> 99:59:59.999 merge together or upgrade together, and it should just work. 99:59:59.999 --> 99:59:59.999 There's also the part were we have to handle rename packages. 99:59:59.999 --> 99:59:59.999 This comes into ?? basically. 99:59:59.999 --> 99:59:59.999 They become an API bump, which will be very useful for stretch due to dcc5. 99:59:59.999 --> 99:59:59.999 Basically if you want to do a same restriction on this you could do something 99:59:59.999 --> 99:59:59.999 like, we have a clause that is not satisfied, but the thing we need for it 99:59:59.999 --> 99:59:59.999 is a package introduced in the new source, then we pull that. 99:59:59.999 --> 99:59:59.999 If it has the same dependencies, we've already solved it, that sort of thing. 99:59:59.999 --> 99:59:59.999 There's also the part where people rename the package from foo to foo replacement 99:59:59.999 --> 99:59:59.999 or something like that. 99:59:59.999 --> 99:59:59.999 Again, if it is from the same source, we might do some magic here, 99:59:59.999 --> 99:59:59.999 some heuristics here. 99:59:59.999 --> 99:59:59.999 And also at some point you will end up needing to install stuff, 99:59:59.999 --> 99:59:59.999 that is actually required for Wheezy to Jessie 99:59:59.999 --> 99:59:59.999 because it pulls in a new a system. 99:59:59.999 --> 99:59:59.999 If it had trivial no-guess solutions, 99:59:59.999 --> 99:59:59.999 by which I mean the first thing is of the alternative choices is a real package, 99:59:59.999 --> 99:59:59.999 and there is only one of them, 99:59:59.999 --> 99:59:59.999 you could solve this automatically in a deterministic way. 99:59:59.999 --> 99:59:59.999 And otherwise, give up and try something else. 99:59:59.999 --> 99:59:59.999 So this is the basic algorithm, and the basic ideas I've put down, 99:59:59.999 --> 99:59:59.999 and I've been fiddling a bit with, and didn't get very far with so far. 99:59:59.999 --> 99:59:59.999 Installing part 2. 99:59:59.999 --> 99:59:59.999 So after we've learned this with upgrading, we can now, 99:59:59.999 --> 99:59:59.999 with single suite single architecture it is trivial. 99:59:59.999 --> 99:59:59.999 Upgrading we can usually ?? it, reduce the problem size to some extent. 99:59:59.999 --> 99:59:59.999 We can do better on the installing part as well. 99:59:59.999 --> 99:59:59.999 We can look at these aspell packages again, 99:59:59.999 --> 99:59:59.999 because they are one of the big problems. 99:59:59.999 --> 99:59:59.999 We have a couple packages that appear to be almost identical, 99:59:59.999 --> 99:59:59.999 and then we also have packages that are clearly superior to others. 99:59:59.999 --> 99:59:59.999 Packages that are identical, shows up like this. 99:59:59.999 --> 99:59:59.999 So we ?? long enough in the aspell package from Russia and the one 99:59:59.999 --> 99:59:59.999 from Ukraine, something very special happens. 99:59:59.999 --> 99:59:59.999 You will notice that primary difference between the fields I've selected are 99:59:59.999 --> 99:59:59.999 the package name and the version. 99:59:59.999 --> 99:59:59.999 Exiting, because that means that if I can install aspell-uk, 99:59:59.999 --> 99:59:59.999 that's the only thing on the system, 99:59:59.999 --> 99:59:59.999 then the same solution is valid for the Russian one. 99:59:59.999 --> 99:59:59.999 So ?? they are different, but semantically they differ only by name and version. 99:59:59.999 --> 99:59:59.999 Sometimes you can have version dependencies that always 99:59:59.999 --> 99:59:59.999 satisfied ?? for example, then that's the same game actually. 99:59:59.999 --> 99:59:59.999 This is a simplified view because in theory you could have a package 99:59:59.999 --> 99:59:59.999 that refuses to work with the Ukranian one, but not the Russian one, 99:59:59.999 --> 99:59:59.999 and vice versa, so they actually become distinct solutions. 99:59:59.999 --> 99:59:59.999 But the general use of aspell dictionaries tends to be any one of them, 99:59:59.999 --> 99:59:59.999 and I really don't care which one you pick. 99:59:59.999 --> 99:59:59.999 So we find those by saying they have the same effective dependencies clauses. 99:59:59.999 --> 99:59:59.999 We can also look at the negative dependencies, that's fairly important too, 99:59:59.999 --> 99:59:59.999 they have to have the same there. 99:59:59.999 --> 99:59:59.999 Here we need to remember that negative dependencies, we do not think of them 99:59:59.999 --> 99:59:59.999 as just directed, they're not. 99:59:59.999 --> 99:59:59.999 So it really doesn't matter if foo breaks bar or bar breaks foo, 99:59:59.999 --> 99:59:59.999 the important part is they don't work together. 99:59:59.999 --> 99:59:59.999 Then we have assert that they satisfy the same clause. 99:59:59.999 --> 99:59:59.999 Both of them are a valid solution to the same clause as the other one. 99:59:59.999 --> 99:59:59.999 And this becomes interesting when you have dependency ranges, 99:59:59.999 --> 99:59:59.999 which is not truly a dependency range, but you have two clauses that says, 99:59:59.999 --> 99:59:59.999 I will need foo greater than version 1, and I need it strictly 99:59:59.999 --> 99:59:59.999 less than version 2, then one of them contains both of them, 99:59:59.999 --> 99:59:59.999 and the other one does not, when you are doing upgrades for example. 99:59:59.999 --> 99:59:59.999 It has to satisfy the same clauses as well. 99:59:59.999 --> 99:59:59.999 A little trick thing that I discovered a little too late, but it's fun. 99:59:59.999 --> 99:59:59.999 These things things can generally be done in polynomial time, that ballpark. 99:59:59.999 --> 99:59:59.999 I haven't really computed the actual results. 99:59:59.999 --> 99:59:59.999 But we can go further than that because equivalent or identical packages 99:59:59.999 --> 99:59:59.999 are easy to find, but there is something better than that. 99:59:59.999 --> 99:59:59.999 We can also have the case where one of the packages is clearly better than the other. 99:59:59.999 --> 99:59:59.999 For example, it has fewer of the same effective dependencies. 99:59:59.999 --> 99:59:59.999 So I need less to solve this package. 99:59:59.999 --> 99:59:59.999 It has fewer of the same negative dependencies, fewer things to 99:59:59.999 --> 99:59:59.999 not work with this, this is also good. 99:59:59.999 --> 99:59:59.999 And finally it solves at least as many dependency clauses as the other one. 99:59:59.999 --> 99:59:59.999 This is typically something you find in upgrade scenarios. 99:59:59.999 --> 99:59:59.999 So your version and the new version do not have and different dependencies 99:59:59.999 --> 99:59:59.999 for example, then don't have any new config relations, but the new version 99:59:59.999 --> 99:59:59.999 might solve more ?? dependencies. 99:59:59.999 --> 99:59:59.999 It might have more packages it can solve. 99:59:59.999 --> 99:59:59.999 In that case, you can just unconditionally take the new version, 99:59:59.999 --> 99:59:59.999 because if a solution works for the new version, 99:59:59.999 --> 99:59:59.999 it may or may not work for the old one, 99:59:59.999 --> 99:59:59.999 but if the solution works with the old one, 99:59:59.999 --> 99:59:59.999 it definitely works with the new one. 99:59:59.999 --> 99:59:59.999 So that's sort of a freebie. 99:59:59.999 --> 99:59:59.999 You're just solving for one of them, if that doesn't work, 99:59:59.999 --> 99:59:59.999 you know you don't have to try the other, that's the important part. 99:59:59.999 --> 99:59:59.999 And the point with these is basically that identical packages are just 99:59:59.999 --> 99:59:59.999 two-way substitutable. 99:59:59.999 --> 99:59:59.999 This being a one-way substitution instead. 99:59:59.999 --> 99:59:59.999 I haven't figured out how to find these, in general, more effectively than 99:59:59.999 --> 99:59:59.999 I do the identical ones. 99:59:59.999 --> 99:59:59.999 The identical ones are easy to find, but I would like to get some where 99:59:59.999 --> 99:59:59.999 we can find these superior packages trivially, because they are more 99:59:59.999 --> 99:59:59.999 useful in general, or there might be more of them as well. 99:59:59.999 --> 99:59:59.999 This is as far as I got, including writing slides five minutes before the talk. 99:59:59.999 --> 99:59:59.999 So are there any questions? 99:59:59.999 --> 99:59:59.999 There's a mic there, or there's a runner. 99:59:59.999 --> 99:59:59.999 [question] Thanks for your interesting talk. I have two questions in fact. 99:59:59.999 --> 99:59:59.999 The first question concerns your problem of finding equivalent packages. 99:59:59.999 --> 99:59:59.999 Are you aware of the ?? tool. 99:59:59.999 --> 99:59:59.999 [Neils] I have through the article about it. 99:59:59.999 --> 99:59:59.999 The thing I remember with that was that it wrote somewhere that 99:59:59.999 --> 99:59:59.999 this should blow up exponentially but it doesn't. 99:59:59.999 --> 99:59:59.999 [question] We these are all theoretically hard problems, or course. 99:59:59.999 --> 99:59:59.999 [Neils] [laughing] Yes. [question] So this tool in fact 99:59:59.999 --> 99:59:59.999 tries to group to find out where to classify packages with respect to 99:59:59.999 --> 99:59:59.999 the switch other packages that are coninstallable. 99:59:59.999 --> 99:59:59.999 [Neils] Yes. [question] And this works. 99:59:59.999 --> 99:59:59.999 One of the steps is to group together packages which behave the same. 99:59:59.999 --> 99:59:59.999 With respect to coninstallability with other packages. 99:59:59.999 --> 99:59:59.999 So this would be your notion of ?? if I understood it correctly. 99:59:59.999 --> 99:59:59.999 [Neils] It sounds like it. [question] At least it is very similar, 99:59:59.999 --> 99:59:59.999 so maybe we can do this offline later, but this is definitely something you 99:59:59.999 --> 99:59:59.999 should look at I think. 99:59:59.999 --> 99:59:59.999 And my other question is about this deterministic ptime installability. 99:59:59.999 --> 99:59:59.999 Of course you are well aware of the fact that this is a result which holds under 99:59:59.999 --> 99:59:59.999 some restrictions of the problems, of course, 99:59:59.999 --> 99:59:59.999 as you don't plan to solve P = NP, so can you, for instance, if you already know 99:59:59.999 --> 99:59:59.999 that it has this good complexity when you don't have any alternatives. 99:59:59.999 --> 99:59:59.999 As you've already said these are explicitly, not implicitly, 99:59:59.999 --> 99:59:59.999 and also when you don't any conflicts, either implicitly or explicitly, 99:59:59.999 --> 99:59:59.999 you seem to have a different class. 99:59:59.999 --> 99:59:59.999 Can you clarify precisely under which conditions on the dependency graph 99:59:59.999 --> 99:59:59.999 you get a ptime complexity of the problem. 99:59:59.999 --> 99:59:59.999 [Neils] So actually the negative dependencies are not an issue. 99:59:59.999 --> 99:59:59.999 If you take a package and the entire transitive dependencies below it 99:59:59.999 --> 99:59:59.999 can always be solved by looking elsewhere in this. 99:59:59.999 --> 99:59:59.999 So you have a set of transitive dependencies, and you can always 99:59:59.999 --> 99:59:59.999 solve it by following a clause where there's only one option, 99:59:59.999 --> 99:59:59.999 or there's a package you've already picked earlier. 99:59:59.999 --> 99:59:59.999 Then locally this becomes a simple regular graph, well you can massage it into one. 99:59:59.999 --> 99:59:59.999 I don't think it happens often enough for us to rely on it 100%, 99:59:59.999 --> 99:59:59.999 I think there may be cases, or corners of the graph where it happens locally, 99:59:59.999 --> 99:59:59.999 and then when you leave that part, go further down the stack, 99:59:59.999 --> 99:59:59.999 or outside that part, you get back to the original problem, 99:59:59.999 --> 99:59:59.999 but will have parts of it that are locally polynomial, 99:59:59.999 --> 99:59:59.999 which will be interesting to find.