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)

The depsolver repeats the following three steps until there are no new

requested installs or removals.

New packages phase. Walk the system and upstream package lists in

parallel, and:

    - For each package

	- 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

	- 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

Properties phase. Walk the system and upstream property lists in

parallel, and:

    - 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 add it to the requested-installs list 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:

	- 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.)

    - For each to-be-installed PROVIDES:

	- 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.

	- Check if the new PROVIDES conflicts with a to-be-installed

	  CONFLICTS. If so, we have an OLD_CONFLICT 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, add

	  the installed package to the requested-installs list to try

	  to upgrade it.

	- Check if the new CONFLICTS conflicts with a to-be-installed

	  PROVIDES. If so, we have an NEW_CONFLICT error.

    - For each to-be-installed OBSOLETES:

	- 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.)

	- If not, check if there's a to-be-installed package that

	  PROVIDES that property. If so, we have a CONTRADICTION

	  error.

    - 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 package

	      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 updated or obsoleted), then add the

		  requiring package to the requested-removals list.

		- Otherwise, add the requiring package to the

		  requested-installs list so it can be updated as

		  well.

	- (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 installed file REQUIRES:

	- Check that the file is still installed. If not, check if

	  a to-be-installed package also provides it.

	- If not:

	    - If the package originally providing it was removed (not

              updated or obsoleted), then add the requiring package to

              the requested-removals list.

	    - Otherwise, add the requiring package to the

              requested-installs list, in the hope that an upgrade

              will no longer require the file

(End)

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.)