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@158: Depsolver: danw@157: danw@158: - Create new razor_transaction_packages ("rtp"s) for each danw@158: requested install or remove. danw@157: danw@158: - while there are new rtps: danw@157: danw@158: - qsort the new rtps danw@157: danw@158: - Walk the system package list, upstream package list, and new danw@158: rtps in parallel. For each new INSTALL/FORCED_UPDATE rtp, danw@158: set the "new_package" field and the appropriate bit in the danw@158: upstream bit array. (For any not-found packages, set an danw@158: UNAVAILABLE error.) For each new rtp of any type (INSTALL, danw@158: REMOVE, FORCED_UPDATE, OBSOLETED), if there's a matching danw@158: system package, set the "old_package" field and clear the danw@158: appropriate bit in the system bit array. danw@157: danw@158: - Walk the system and upstream property lists in parallel, danw@158: and: danw@157: danw@158: - For each to-be-installed non-file REQUIRES: danw@157: danw@158: - See if there's an installed or to-be-installed danw@158: package that PROVIDES that property. danw@157: danw@158: - If not, see if there's an installable package that danw@158: PROVIDES that property, and create a new INSTALL rtp danw@158: for it if so. danw@157: danw@158: - If not, see if there's a to-be-removed package that danw@158: PROVIDES that property. (If we find such a package, danw@158: we have a CONTRADICTION error.) danw@157: danw@158: - If none of the above, then we have an UNSATISFIABLE danw@158: error danw@157: danw@158: - For each to-be-installed file REQUIRES: danw@157: danw@158: - (We create fake file PROVIDES to match file REQUIRES danw@158: when importing/merging razor sets, so if there is danw@158: already another installed package that REQUIRES this danw@158: file, there will be a PROVIDES listed for it as well.) danw@157: danw@158: - See if there's an installed package that PROVIDES danw@158: that file. danw@157: danw@158: - If not, do a binary search of the system file tree danw@158: looking to see if some installed package provides danw@158: that file but does not have a PROVIDES for it. danw@157: danw@158: - If not, see if there's an installable package that danw@158: PROVIDES that property, and create a new INSTALL rtp danw@158: for it if so. danw@157: danw@158: - (If we actually work with multiple upstream danw@158: razor_sets, then we will need to search the upstream danw@158: file trees at this point, because it's possible that danw@158: a package in one upstream repo would require a file danw@158: in another upstream repo. But if we merge the danw@158: multiple upstream repos into a single razor_set at danw@158: some point, then we would not need to do that, danw@158: because it would be guaranteed that we would have danw@158: already created a fake PROVIDES if any package danw@158: provides the file.) danw@157: danw@158: - If no installed or installable package provides the danw@158: file, see if there's a to-be-removed package that danw@158: provides the file. (If we find such a package, we danw@158: have a CONTRADICTION error.) danw@157: danw@158: - If none of the above, then we have an UNSATISFIABLE danw@158: error danw@157: danw@158: - For each to-be-installed PROVIDES: danw@157: danw@158: - Check if the new PROVIDES conflicts with an danw@158: installed CONFLICTS. If so, create a new danw@158: FORCED_UPDATE rtp for the installed package, so we danw@158: can try to upgrade it to a non-conflicting version. danw@158: (If we can't, we'll have an OLD_CONFLICT error.) danw@157: danw@158: - Check if the new PROVIDES conflicts with an danw@158: installed OBSOLETES *and* the PROVIDES property danw@158: corresponds to the name of its package. (That is, danw@158: OBSOLETES are only matched against package names, danw@158: not arbitrary provided properties.) If so, we have danw@158: an ALREADY_OBSOLETE error. danw@157: danw@158: - Check if the new PROVIDES conflicts with a danw@158: to-be-installed CONFLICTS. If so, we have a danw@158: CONTRADICTION error. danw@157: danw@158: - For each to-be-installed CONFLICTS: danw@157: danw@158: - Basically the reverse of the previous case: check if danw@158: the new CONFLICTS conflicts with an installed danw@158: PROVIDES. If so, create a new FORCED_UPDATE rtp for danw@158: the installed package, so we can try to upgrade it danw@158: to a non-conflicting version. (If we can't, we'll danw@158: have an NEW_CONFLICT error.) danw@157: danw@158: - Check if the new CONFLICTS conflicts with a danw@158: to-be-installed PROVIDES. If so, we have a danw@158: CONTRADICTION error. danw@157: danw@158: - For each to-be-installed OBSOLETES: danw@157: danw@158: - Check if there's an installed package that PROVIDES danw@158: that property. If so, create an OBSOLETED rtp for danw@158: the installed package. danw@157: danw@158: - If not, check if there's a to-be-installed package danw@158: that PROVIDES that property. If so, we have a danw@158: CONTRADICTION error. danw@157: danw@158: - For each to-be-removed PROVIDES: danw@157: danw@158: - If there's also an identical to-be-installed danw@158: PROVIDES, we're ok and can skip this danw@157: danw@158: - Otherwise, for each installed REQUIRES of this danw@158: property: danw@157: danw@158: - Look for some other installed or to-be-installed danw@158: property that satisfies the REQUIRES. danw@157: danw@158: - If there isn't one, then for each installed danw@158: package in this REQUIRES's package list: danw@157: danw@158: - If the PROVIDES was lost because the old danw@158: package was REMOVEd (not FORCED_UPDATE or danw@158: OBSOLETED), then create a new REMOVE rtp for danw@158: this package. danw@157: danw@158: - Otherwise, create a new FORCED_UPDATE rtp danw@158: for this package. danw@157: danw@158: - (We don't need to look at to-be-installed REQUIRES danw@158: of this property, because if there are any, they danw@158: will cause a CONTRADICTION error when we try to danw@158: re-satisfy them the next time through.)