Preliminaries: Queries are of the form: maximize versions P1, P2, P3, ... Pk in that order (so P1 has priority over P2 which has priority over P3 ...) and then conditions on the versions of other packages up to n such that the initial working configuration of versions is included in the list of possible responses. Unknown execution ordering which could have cycles. Definition: Two configurations are equal if they have the same versions for every package. Definition: We say that configuration C' = P1.v1', P2.v2', ..., Pk.vk', ..., Pn.vn' is lexicographically greater (>) than C = P1.v1, P2.v2, ...., Pk.vk, ..., Pn.vn if either P1.v1' > P1.v1 or (P1.v1' = P1.v1 and P2.v2' > P2.v2) or ... or (P1.v1' = P1.v1 and P2.v2' = P2.v2 and ... and Pk-1.vk-1' = Pk-1.vk-1 and Pk.vk' > Pk.vk) Definition: A configuration "works" if it executes to completion. Definition: Pushing a package means advancing by one version level. A maximization-push is done for purposes of maximizing the version of a package. A failure-push is done for purposes of trying to avoid incompatibilities Assumptions: 1. Pairwise/Global assumption (pairwise compatible implies global compatibility): An execution using configuration P1.v1, .... , Pn.vn works iff for all i, j (1 <= i,j <= n) Pi.vi is compatible with Pj.vj. 2. Historicity: Suppose vi < vi' < vi'' and vj < vj' < vj'' and that Pi.vi' works with Pj.vj' but Pi.vi'' does not work with Pj.vj'. Then (i) Pi.vi'' will not work with Pj.vj and (ii) if vi''' > vi'', then Pi.vi''' will not work with Pj.vj'. 3. If (i) neither Pi nor Pj has been maximization-pushed and (ii) Pi.vi calls Pj.vj fails, then for all x >= vi and for all y <= vj Pi.x will fail on Pj.y. Algorithm: LiquidClimber This starts from a configuration that works (e.g. the one that was run by the original creators of the virtual machine). It assumes that there is some query that maximizes the versions of some packages (perhaps with constraints) and may have constraints but no maximization function on other versions. The result of the algorithm is a revised configuration that is lexicographically maximum and that satisfies the constraints. This is under the assumption that the original configuration satisfies the constraints. If not, then we will return the original configuration (the one that produced the initial virtual machine). current := package version pairs in the initial configuration todolist := packages requiring maximization in descending order of priority constraints := some constraints on versions of various packages sourcemap := for each package the versions that exist and satisfy constraints for each package p in todolist in descending order of priority update current to the highest version of p that works # use git binary on sourcemap if current has less than last version of p then versionstodo = find all greater versions of p or major releases in ascending order of version number within sourcemap for each v in versionstodo in order # could be parallelized but then we have to make # sure we take lexicographically greatest ret temp := current with p set to v # maximization push ret := trytomakework(p, temp) if ret is not null then # we've had success current:= ret # adjust temp to make it work trytomakework(p, temp) initialtemp := temp while temp doesn't work in the execution of temp, Find the first call, say from Pi.vi' to Pj.vj', that fails Record in memo that Pi.vi' calling Pj.vj' fails Form a new version of temp with Pj.vj'' which is the next version above vj' in Pj and for which we don't know from the memo that Pi.vi' calling Pj.vj'' will fail. if there is no such version vj'' then advance Pi within temp to the next version vi'' for which we don't know from the memo that Pi.vi'' calling Pj.vj' fails and start Pj from the version in initialtemp if there is neither a version for Pi nor Pj return null execute temp endwhile return temp # adjust temp to make it work trytomakeworkheuristic(p, temp) maximizepushed = {p} while temp doesn't work in the execution of temp, find the first call, say from Pi.vi' to Pj.vj', that fails record in memo that Pi.vi' to Pj.vj' fails if Pi is in maximizepushed then add Pj to maxmizedpushed (ret, vi_new, vj_new) = exponentialsearch(Pi, vi', Pj, vj', maximizepushed) if ret == True then replace Pi by version vi_new and Pj by version vj_new in temp else return null endwhile return temp # uses history and other axioms (heuristic) except the part exponentialsearch(Pi,vi', Pj, vj') consider all possible versions of Pi and Pj if Pi.vi' works with Pj.vj for vj < vj', then can do binary search in between vj and vj' if we want the max version of Pj [Sarah: I think this works by historicity] if neither Pi nor Pj has been maximize pushed, then for all x >= vi' and y <= vj', Pi.x will fail on Pj.y so discard advance Pj by more or less depending on how much we've already advanced Pj (each time you try to advance Pj and fail, take a bigger jump next time) if there is some vi_new >= vi', vj_new, Pi.vi_new calling Pj.vj_new does not cause a failure return (True, vi_new, vj_new) else return False Optimizations: Here are the filters we can do: 1. History: If a configuration includes Pi.vi and Pj.vj and a call from Pi.vi to Pj.vj already failed, then this configuration will fail too. 2. The optimizations of axioms 2 and 4. That is the heuristic version. Naive Time Complexity based only on axiom 1 and memoization: if there are n packages, then there are at most (n choose 2)*2 = n (n-1) calling arrangements (where Pi calls Pj is distinct from Pj calls Pi). If the max number of versions any package has is M, then we have n (n-1) * M * M in the absolute worst case. After that, we will know all compatibilities. We might be able to make this k (k-1) * M *M with some more careful thought where k is the number of packages to optimize. Better time complexity just assuming memoization: each time you maximize push one package by a single version, at the worst you have time equal to the total number of remaining versions of all other packages. So if we have just k packages that must be pushed and n packages altogether where each package has M versions, then the time is k*n*M. Example like this maximizing P1 and P2 and these two are compatible for all q, i.e. P1.q is compatible with P2.q. For all other packages P, for r > 1, P.M is compatible with P1.r and P.M is compatible with P2.r but no other version of P is compatible with P1.r or P2.r. Extended Example: Let's say we have 7 packages and we want to maximize P1, then P2. All packages have 10 versions and what works is P1.1, P2.1, ..., P7.1 also P1.2, P2.2, ..., P7.2 and P1.2, P2.4, P3.4, ..., P7.4. Nothing else Execution order is P5, P2, P7, P1, P5, P4, P2, P3, P6 Here is what will happen: maximization-push P1 to P1.2. P5.1 calls P2.1 calls P7.1 calls P1.2 and fails. Because this is a case where Pi (P7) calls Pj (P1) and P1 was maximization-pushed, we will maximization-push Pi (P7) to P7.2. New execution will fail when P2 calls P7, but because P7 was maximization pushed, P2 will maximization-pushed to P2.2. New execution will fail when P5.1 calls P2.2. Because P2 was maximization-pushed, P5 will be maximizaiton pushed to P5.2 At this point we have P1.2, P2.2, P3.1, P4.1, P5.2, P6.1, P7.2 So we execute and we get through P5, P2, P7, P1, P5 and then fail on the call from P5 to P4. In this case P4 has not been maximization-pushed, so P4 advances to P4.2. Similarly for P3 and P6. Ok, so now everyone is at version 2. P1.2, P2.2, P3.2, P4.2, P5.2, P6.2, P7.2 So now we maximization push P1 again, P7 will then be maximization-pushed to P7.3. Then to P7.4, .... P7.10. Then we try pushing P1 to P1.4 and maximization-push P7 all the way up from P7.2 to P7.10. So this is quadratic, but these calls can be memoized so won't have to repeat them. We will keep pushing P1 all the way. This is where it is quadratic. So we try to maximize package P2 starting from P1.2, P2.2, P3.2, P4.2, P5.2, P6.2, P7.2 We maximization-push P2 to version 3. In the execution, the call from P5.2 to P2.3 will fail. So, P5 will be pushed to P5.3. That won't work. Neither will P5.4, P5.5, ... So now we advance P2 to version 4 and restart P5 at version 2. That fails, but then P5 advances to version 3, then 4. This works. Now P2 calls P7.2 which will advance to version 4 eventually and so on down the line. New execution Optimization: The algorithm as written would execute a configuration even if there are previously discovered incompatibilities between package-version pairs. The optimization is to detect such incompatibilities and determine "temp doesn't work" without execution. What you get to prove: 1. The algorithm finds the lexicographically maximum configuration. 2. The algorithm runs in linear time times the number of packages to maximize (k). Equivalently, once a version is pushed for maximization purposes, it will either stay, continue advancing or go back to last working configuration and stop. Proof ideas from before Why should this work? Theorem: Under the assumption of historicity, the value of current at the end of this algorithm is the lexicographically maximum. Proof sketch: Suppose that this algorithm arrives at a lexicographically maximum configuration of P1.v1', P2.v2', ...., Pn.vn' that works. Suppose that there is a another configuration P1.v1'', P2.v2'', ...., Pn.vn'' that is lexicographically greater and that also works. We prove that P1.v1'', P2.v2'', ...., Pn.vn'' must have been tried by our algorithm.. If v1'' > v1' then the algorithm must have tried v1'' by construction of versionstodo. When trying P1.v1'', P2.v2', ...., Pn.vn', let j be the package that first fails. Then Pj.vj'' != Pj.vj', or there would not have been a failure since C'' works. Further Pj.vj'' > Pj.vj' by historicity. So, some version of Pj, vj''' will be found that allows the execution to pass that call to Pj. As the iterations through trytomakework continue the version of Pj may or may not continue to increase. If Pj is one of the packages whose version should be maximized, then if vj'' > vj''', then vj'' will be tried by construction of versionstodo. Inductive step: this is true up to m-1 for 1 < m-1 < k-1, then it will be true for m. If vm'' > vm', then when trying P1.v1'', P2.v2'', ..., Pm.vm'', ...., Pn.vn', let j be the package that first fails. ===== # adjust temp to make it work trytomakework(p, temp) while temp doesn't work in the execution of temp, if temp fails find the first call, say from Pi to Pj, that fails if Pj was maximization-pushed then maximize-push Pi to the next version v in temp if no such version v then return null else failure-push Pj to the next version in temp if no such version v then return null endwhile return temp