We start with two razor_sets, system and upstream, and a list of requested installations and removals. FIXME: what about multiple upstream repos? Having to deal with arbitrary numbers of razor_sets is possible, but will probably be messy... It might be easier to either store all upstream repo data in a single .repo file, or else merge all upstream .repo files together into a single razor_set at startup. (Or some combination of those.) We create a bit array of the packages in each set, indicating which ones are installed; the system bitarray starts out all 1s, and the upstream bitarray all 0s. Each bit is only allowed to change state once during the transaction; an installed package can be removed, or an uninstalled package installed, but trying to reinstall a removed package, or uninstall a newly-installed package is an error. This means the packages break down into four categories: - installed (1 bit in the system bit array) - to-be-removed (0 bit in the system bit array) - to-be-installed (1 bit in the upstream bit array) - installable (0 bit in the upstream bit array) Depsolver: - Create new razor_transaction_packages ("rtp"s) for each requested install or remove. These will be "unresolved", because we haven't yet found the razor_packages that correspond to them. - while there are new rtps: - sort the new rtps - Walk the system property list, upstream property list, and new rtp list in parallel, and: - For each uninstalled PROVIDES: - If the property is a valid package name (that is, either it's a package providing its own name, or it has a matching OBSOLETES), and it matches the name of a new rtp of type INSTALL or FORCED_UPDATE with an unresolved new_package, then set the rtp's new_package to point to the package providing this property and set the appropriate bit in the upstream bit array. - For each to-be-installed non-file REQUIRES: - 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 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 none of the above, then we have an UNSATISFIABLE error - For each to-be-installed file REQUIRES: - (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.) - See if there's an installed package that PROVIDES that file. - 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. - If not, see if there's an installable package that PROVIDES that property, and create a new INSTALL rtp for it if so. - (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.) - 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.) - If none of the above, then we have an UNSATISFIABLE error - For each to-be-installed PROVIDES: - 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.) - 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. - Check if the new PROVIDES conflicts with a to-be-installed CONFLICTS. If so, we have a CONTRADICTION error. - For each to-be-installed CONFLICTS: - 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.) - Check if the new CONFLICTS conflicts with a to-be-installed PROVIDES. If so, we have a CONTRADICTION error. - For each to-be-installed OBSOLETES: - Check if there's an installed package that PROVIDES that property. If so, create an OBSOLETED rtp for the installed package. - If not, check if there's a to-be-installed package that PROVIDES that property. If so, we have a CONTRADICTION error. - For each installed PROVIDES: - If the property is a valid package name (that is, it's a package providing its own name), and it matches the name of a new rtp with an unresolved old_package, then set the rtp's old_package to point to the package providing this property and clear the appropriate bit in the system bit array. - For each to-be-removed PROVIDES: - If there's also an identical to-be-installed PROVIDES, we're ok and can skip this - Otherwise, for each installed REQUIRES of this property: - Look for some other installed or to-be-installed property that satisfies the REQUIRES. - If there isn't one, then for each installed package in this REQUIRES's package list: - 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. - Otherwise, create a new FORCED_UPDATE rtp for this package. - (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.)