diff -r 57e8182f59bc -r 00f19df51272 DEPSOLVE.txt --- a/DEPSOLVE.txt Fri Mar 07 15:38:31 2008 -0500 +++ b/DEPSOLVE.txt Tue Mar 11 11:43:54 2008 -0400 @@ -22,149 +22,145 @@ - installable (0 bit in the upstream bit array) -The depsolver repeats the following three steps until there are no new -requested installs or removals. +Depsolver: -New packages phase. Walk the system and upstream package lists in -parallel, and: + - Create new razor_transaction_packages ("rtp"s) for each + requested install or remove. - - For each package + - while there are new rtps: - - If it has newly been added to the requested-installs list, - create a razor_transaction_package for it, and set the - appropriate bit in the upstream bitarray; if it is an - update, clear the appropriate bit in the system bitarray + - qsort the new rtps - - If it has newly been added to the requested-removals list, - create a razor_transaction_package for it, and clear the - appropriate bit in the system bitarray + - Walk the system package list, upstream package list, and new + rtps in parallel. For each new INSTALL/FORCED_UPDATE rtp, + set the "new_package" field and the appropriate bit in the + upstream bit array. (For any not-found packages, set an + UNAVAILABLE error.) For each new rtp of any type (INSTALL, + REMOVE, FORCED_UPDATE, OBSOLETED), if there's a matching + system package, set the "old_package" field and clear the + appropriate bit in the system bit array. -Properties phase. Walk the system and upstream property lists in -parallel, and: + - Walk the system and upstream property lists in parallel, + and: - - For each to-be-installed non-file REQUIRES: + - For each to-be-installed non-file REQUIRES: - - See if there's an installed or to-be-installed package that - PROVIDES that property. + - See if there's an installed or to-be-installed + package that PROVIDES that property. - - If not, see if there's an installable package that PROVIDES - that property, and add it to the requested-installs list if - so. + - If not, see if there's an installable package that + PROVIDES that property, and create a new INSTALL rtp + for it if so. - - If not, see if there's a to-be-removed package that PROVIDES - that property. (If we find such a package, we have a - CONTRADICTION error.) + - If not, see if there's a to-be-removed package that + PROVIDES that property. (If we find such a package, + we have a CONTRADICTION error.) - - If none of the above, then we have an UNSATISFIABLE error + - If none of the above, then we have an UNSATISFIABLE + error - - For each to-be-installed file REQUIRES: + - For each to-be-installed file REQUIRES: - - Same as for property REQUIRES, except that since we have to - search the file tree, this is not O(1). (See below for more - discussion.) + - (We create fake file PROVIDES to match file REQUIRES + when importing/merging razor sets, so if there is + already another installed package that REQUIRES this + file, there will be a PROVIDES listed for it as well.) - - For each to-be-installed PROVIDES: + - See if there's an installed package that PROVIDES + that file. - - Check if the new PROVIDES conflicts with an installed - CONFLICTS. If so, add the installed package to the - requested-installs list, so we can try to upgrade it to a - non-conflicting version. + - If not, do a binary search of the system file tree + looking to see if some installed package provides + that file but does not have a PROVIDES for it. - - Check if the new PROVIDES conflicts with a to-be-installed - CONFLICTS. If so, we have an OLD_CONFLICT error. + - If not, see if there's an installable package that + PROVIDES that property, and create a new INSTALL rtp + for it if so. - - For each to-be-installed CONFLICTS: + - (If we actually work with multiple upstream + razor_sets, then we will need to search the upstream + file trees at this point, because it's possible that + a package in one upstream repo would require a file + in another upstream repo. But if we merge the + multiple upstream repos into a single razor_set at + some point, then we would not need to do that, + because it would be guaranteed that we would have + already created a fake PROVIDES if any package + provides the file.) - - Basically the reverse of the previous case: check if the new - CONFLICTS conflicts with an installed PROVIDES. If so, add - the installed package to the requested-installs list to try - to upgrade it. + - If no installed or installable package provides the + file, see if there's a to-be-removed package that + provides the file. (If we find such a package, we + have a CONTRADICTION error.) - - Check if the new CONFLICTS conflicts with a to-be-installed - PROVIDES. If so, we have an NEW_CONFLICT error. + - If none of the above, then we have an UNSATISFIABLE + error - - For each to-be-installed OBSOLETES: + - For each to-be-installed PROVIDES: - - Check if there's an installed package that PROVIDES that - property. If so, add that package to the requested-removals - list, noting it should be marked obsolete. ("Obsolete" means - that the to-be-removed PROVIDES step below will treat it - like it was upgraded, not removed.) + - Check if the new PROVIDES conflicts with an + installed CONFLICTS. If so, create a new + FORCED_UPDATE rtp for the installed package, so we + can try to upgrade it to a non-conflicting version. + (If we can't, we'll have an OLD_CONFLICT error.) - - If not, check if there's a to-be-installed package that - PROVIDES that property. If so, we have a CONTRADICTION - error. + - Check if the new PROVIDES conflicts with an + installed OBSOLETES *and* the PROVIDES property + corresponds to the name of its package. (That is, + OBSOLETES are only matched against package names, + not arbitrary provided properties.) If so, we have + an ALREADY_OBSOLETE error. - - For each to-be-removed PROVIDES: + - Check if the new PROVIDES conflicts with a + to-be-installed CONFLICTS. If so, we have a + CONTRADICTION error. - - If there's also an identical to-be-installed PROVIDES, we're - ok and can skip this + - For each to-be-installed CONFLICTS: - - Otherwise, for each installed REQUIRES of this property: + - Basically the reverse of the previous case: check if + the new CONFLICTS conflicts with an installed + PROVIDES. If so, create a new FORCED_UPDATE rtp for + the installed package, so we can try to upgrade it + to a non-conflicting version. (If we can't, we'll + have an NEW_CONFLICT error.) - - Look for some other installed or to-be-installed package - that satisfies the REQUIRES. + - Check if the new CONFLICTS conflicts with a + to-be-installed PROVIDES. If so, we have a + CONTRADICTION error. - - If there isn't one, then for each installed package in - this REQUIRES's package list: + - For each to-be-installed OBSOLETES: - - If the PROVIDES was lost because the old package was - removed (not updated or obsoleted), then add the - requiring package to the requested-removals list. + - Check if there's an installed package that PROVIDES + that property. If so, create an OBSOLETED rtp for + the installed package. - - Otherwise, add the requiring package to the - requested-installs list so it can be updated as - well. + - If not, check if there's a to-be-installed package + that PROVIDES that property. If so, we have a + CONTRADICTION error. - - (We don't need to look at to-be-installed REQUIRES of this - property, because if there are any, they will cause a - CONTRADICTION error when we try to re-satisfy them the next - time through.) + - For each to-be-removed PROVIDES: - - For each installed file REQUIRES: + - If there's also an identical to-be-installed + PROVIDES, we're ok and can skip this - - Check that the file is still installed. If not, check if - a to-be-installed package also provides it. + - Otherwise, for each installed REQUIRES of this + property: - - If not: + - Look for some other installed or to-be-installed + property that satisfies the REQUIRES. - - If the package originally providing it was removed (not - updated or obsoleted), then add the requiring package to - the requested-removals list. + - If there isn't one, then for each installed + package in this REQUIRES's package list: - - Otherwise, add the requiring package to the - requested-installs list, in the hope that an upgrade - will no longer require the file + - If the PROVIDES was lost because the old + package was REMOVEd (not FORCED_UPDATE or + OBSOLETED), then create a new REMOVE rtp for + this package. -(End) + - Otherwise, create a new FORCED_UPDATE rtp + for this package. - -Note on file dependencies - - - With this algorithm, the total time spent satisfying file - dependencies is O(D * log F), where D is the total number of - file dependencies being added or removed, and F is the total - number of files. - - - If we sorted the file list differently, we could walk it in - parallel with the property lists, resulting in an overall - file-require-satisfying time of O(F). However, F is likely to be - much much greater than D * log F, so this would probably end up - actually being a pessimization. - - - A better solution (assuming that we do actually need an O(1) - algorithm here) would be to add explicit file PROVIDES - properties to the set as needed. That is, whenever we add a - package containing a "REQUIRES /foo" property to a set, we also - add a "PROVIDES /foo" property to the set, pointing to the - correct provider packages. More than half of all file requires - are on /bin/sh or /sbin/ldconfig, and of the 7263 file requires - in 9306 packages currently in rawhide.repo, only 154 are not - satisfied by my system.repo. So storing file provides in the - property list as they are needed would eliminate the need to - search through the file list 99% of the time. - - (We might need a separate optimization for the - building-the-system-up-from-empty case in the installer, since - we'd be resolving the whole transaction without having explicit - PROVIDES listed for /bin/sh, etc.) + - (We don't need to look at to-be-installed REQUIRES + of this property, because if there are any, they + will cause a CONTRADICTION error when we try to + re-satisfy them the next time through.)