danw@157: We start with two razor_sets, system and upstream, and a list of danw@157: requested installations and removals. danw@157: danw@157: FIXME: what about multiple upstream repos? Having to deal with danw@157: arbitrary numbers of razor_sets is possible, but will probably be danw@157: messy... It might be easier to either store all upstream repo data danw@157: in a single .repo file, or else merge all upstream .repo files danw@157: together into a single razor_set at startup. (Or some combination danw@157: of those.) danw@157: danw@157: We create a bit array of the packages in each set, indicating which danw@157: ones are installed; the system bitarray starts out all 1s, and the danw@157: upstream bitarray all 0s. Each bit is only allowed to change state danw@157: once during the transaction; an installed package can be removed, or danw@157: an uninstalled package installed, but trying to reinstall a removed danw@157: package, or uninstall a newly-installed package is an error. This danw@157: means the packages break down into four categories: danw@157: danw@157: - installed (1 bit in the system bit array) danw@157: - to-be-removed (0 bit in the system bit array) danw@157: - to-be-installed (1 bit in the upstream bit array) danw@157: - installable (0 bit in the upstream bit array) danw@157: danw@157: danw@157: The depsolver repeats the following three steps until there are no new danw@157: requested installs or removals. danw@157: danw@157: New packages phase. Walk the system and upstream package lists in danw@157: parallel, and: danw@157: danw@157: - For each package danw@157: danw@157: - If it has newly been added to the requested-installs list, danw@157: create a razor_transaction_package for it, and set the danw@157: appropriate bit in the upstream bitarray; if it is an danw@157: update, clear the appropriate bit in the system bitarray danw@157: danw@157: - If it has newly been added to the requested-removals list, danw@157: create a razor_transaction_package for it, and clear the danw@157: appropriate bit in the system bitarray danw@157: danw@157: Properties phase. Walk the system and upstream property lists in danw@157: parallel, and: danw@157: danw@157: - For each to-be-installed non-file REQUIRES: danw@157: danw@157: - See if there's an installed or to-be-installed package that danw@157: PROVIDES that property. danw@157: danw@157: - If not, see if there's an installable package that PROVIDES danw@157: that property, and add it to the requested-installs list if danw@157: so. danw@157: danw@157: - If not, see if there's a to-be-removed package that PROVIDES danw@157: that property. (If we find such a package, we have a danw@157: CONTRADICTION error.) danw@157: danw@157: - If none of the above, then we have an UNSATISFIABLE error danw@157: danw@157: - For each to-be-installed file REQUIRES: danw@157: danw@157: - Same as for property REQUIRES, except that since we have to danw@157: search the file tree, this is not O(1). (See below for more danw@157: discussion.) danw@157: danw@157: - For each to-be-installed PROVIDES: danw@157: danw@157: - Check if the new PROVIDES conflicts with an installed danw@157: CONFLICTS. If so, add the installed package to the danw@157: requested-installs list, so we can try to upgrade it to a danw@157: non-conflicting version. danw@157: danw@157: - Check if the new PROVIDES conflicts with a to-be-installed danw@157: CONFLICTS. If so, we have an OLD_CONFLICT error. danw@157: danw@157: - For each to-be-installed CONFLICTS: danw@157: danw@157: - Basically the reverse of the previous case: check if the new danw@157: CONFLICTS conflicts with an installed PROVIDES. If so, add danw@157: the installed package to the requested-installs list to try danw@157: to upgrade it. danw@157: danw@157: - Check if the new CONFLICTS conflicts with a to-be-installed danw@157: PROVIDES. If so, we have an NEW_CONFLICT error. danw@157: danw@157: - For each to-be-installed OBSOLETES: danw@157: danw@157: - Check if there's an installed package that PROVIDES that danw@157: property. If so, add that package to the requested-removals danw@157: list, noting it should be marked obsolete. ("Obsolete" means danw@157: that the to-be-removed PROVIDES step below will treat it danw@157: like it was upgraded, not removed.) danw@157: danw@157: - If not, check if there's a to-be-installed package that danw@157: PROVIDES that property. If so, we have a CONTRADICTION danw@157: error. danw@157: danw@157: - For each to-be-removed PROVIDES: danw@157: danw@157: - If there's also an identical to-be-installed PROVIDES, we're danw@157: ok and can skip this danw@157: danw@157: - Otherwise, for each installed REQUIRES of this property: danw@157: danw@157: - Look for some other installed or to-be-installed package danw@157: that satisfies the REQUIRES. danw@157: danw@157: - If there isn't one, then for each installed package in danw@157: this REQUIRES's package list: danw@157: danw@157: - If the PROVIDES was lost because the old package was danw@157: removed (not updated or obsoleted), then add the danw@157: requiring package to the requested-removals list. danw@157: danw@157: - Otherwise, add the requiring package to the danw@157: requested-installs list so it can be updated as danw@157: well. danw@157: danw@157: - (We don't need to look at to-be-installed REQUIRES of this danw@157: property, because if there are any, they will cause a danw@157: CONTRADICTION error when we try to re-satisfy them the next danw@157: time through.) danw@157: danw@157: - For each installed file REQUIRES: danw@157: danw@157: - Check that the file is still installed. If not, check if danw@157: a to-be-installed package also provides it. danw@157: danw@157: - If not: danw@157: danw@157: - If the package originally providing it was removed (not danw@157: updated or obsoleted), then add the requiring package to danw@157: the requested-removals list. danw@157: danw@157: - Otherwise, add the requiring package to the danw@157: requested-installs list, in the hope that an upgrade danw@157: will no longer require the file danw@157: danw@157: (End) danw@157: danw@157: danw@157: Note on file dependencies danw@157: danw@157: - With this algorithm, the total time spent satisfying file danw@157: dependencies is O(D * log F), where D is the total number of danw@157: file dependencies being added or removed, and F is the total danw@157: number of files. danw@157: danw@157: - If we sorted the file list differently, we could walk it in danw@157: parallel with the property lists, resulting in an overall danw@157: file-require-satisfying time of O(F). However, F is likely to be danw@157: much much greater than D * log F, so this would probably end up danw@157: actually being a pessimization. danw@157: danw@157: - A better solution (assuming that we do actually need an O(1) danw@157: algorithm here) would be to add explicit file PROVIDES danw@157: properties to the set as needed. That is, whenever we add a danw@157: package containing a "REQUIRES /foo" property to a set, we also danw@157: add a "PROVIDES /foo" property to the set, pointing to the danw@157: correct provider packages. More than half of all file requires danw@157: are on /bin/sh or /sbin/ldconfig, and of the 7263 file requires danw@157: in 9306 packages currently in rawhide.repo, only 154 are not danw@157: satisfied by my system.repo. So storing file provides in the danw@157: property list as they are needed would eliminate the need to danw@157: search through the file list 99% of the time. danw@157: danw@157: (We might need a separate optimization for the danw@157: building-the-system-up-from-empty case in the installer, since danw@157: we'd be resolving the whole transaction without having explicit danw@157: PROVIDES listed for /bin/sh, etc.)