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.

    - while there are new rtps:

	- qsort the new rtps

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

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