1.1 --- a/DEPSOLVE.txt Tue Mar 11 11:44:51 2008 -0400
1.2 +++ b/DEPSOLVE.txt Thu Mar 13 08:29:05 2008 -0400
1.3 @@ -1,3 +1,74 @@
1.4 +YUM vs RAZOR
1.5 +------------
1.6 +
1.7 +At a very high level, yum's depsolver does something roughly
1.8 +equivalent to:
1.9 +
1.10 + - For each package being installed or removed
1.11 +
1.12 + - For each relevant property (provides, requires, conflicts,
1.13 + obsoletes):
1.14 +
1.15 + - Figure out what additional packages need to be added to
1.16 + or removed from the system to satisfy this property
1.17 +
1.18 +which ends up being roughly O(N^2 * M) where N is the total number of
1.19 +properties and M is the number of packages being acted on.
1.20 +
1.21 +(I just figured that out off the top of my head, and I'm not totally
1.22 +familiar with the yum code, so it may be wrong.)
1.23 +
1.24 +Razor's depsolver is something like:
1.25 +
1.26 + - do {
1.27 +
1.28 + - For each property to be added to or removed from the system:
1.29 +
1.30 + - Figure out what packages need to be added to or removed
1.31 + from the system to satisfy this property
1.32 +
1.33 + - } until we stop adding/remove more packages
1.34 +
1.35 +with the key being that it's very easy to find the PROVIDES
1.36 +corresponding to a REQUIRES and vice versa, because the property
1.37 +arrays are sorted, and so all properties with the same "name" will be
1.38 +adjacent to one another in the array, allowing many dependencies to be
1.39 +satisified in essentially constant time. (Actually... we've been
1.40 +calling it constant, but it's really O(log N) for heavily-depended-on
1.41 +packages, because the more packages you have, the more variations on
1.42 +"requires foo", "requires foo = 1.1", "requires foo > 1.0", etc you're
1.43 +going to have to scan through.)
1.44 +
1.45 +Ideally though, each iteration of the inner loop body happens in
1.46 +constant time, and thus the inner loop as a whole is O(N), and thus
1.47 +the depsolver as a whole is O(N * M) (or at least, less than
1.48 +O(N * M * log N).
1.49 +
1.50 +
1.51 +FILE DEPENDENCIES
1.52 +-----------------
1.53 +
1.54 +Whenever we add a package with a file REQUIRES to a razor_set, we also
1.55 +add a PROVIDES for that file to the package or packages which provide
1.56 +that file. This means that if we later add another package that
1.57 +requires the same file (eg, /bin/sh or /usr/bin/perl), we can resolve
1.58 +its file requirement exactly like we would resolve a property
1.59 +requirement, in nearly constant time.
1.60 +
1.61 +When adding a *new* file requirement (ie, a requirement on a file that
1.62 +no existing package depends on), we still have to scan through the
1.63 +file tree, which is O(log N) in the number of files.
1.64 +
1.65 +(AFAICT, there's no reason yum couldn't do the same optimization.
1.66 +Also, AFAICT, yum currently sticks property dependencies and file
1.67 +dependencies into the same hash table, so that if any package in the
1.68 +transaction has a file dependency, it causes *property* dependencies
1.69 +to become slower to resolve as well...)
1.70 +
1.71 +
1.72 +THE DEPSOLVER
1.73 +-------------
1.74 +
1.75 We start with two razor_sets, system and upstream, and a list of
1.76 requested installations and removals.
1.77
1.78 @@ -22,7 +93,7 @@
1.79 - installable (0 bit in the upstream bit array)
1.80
1.81
1.82 -Depsolver:
1.83 +Depsolver algorithm:
1.84
1.85 - Create new razor_transaction_packages ("rtp"s) for each
1.86 requested install or remove. These will be "unresolved", because
1.87 @@ -41,10 +112,20 @@
1.88 either it's a package providing its own name, or it
1.89 has a matching OBSOLETES), and it matches the name
1.90 of a new rtp of type INSTALL or FORCED_UPDATE with
1.91 - an unresolved new_package, then set the rtp's
1.92 - new_package to point to the package providing this
1.93 - property and set the appropriate bit in the upstream
1.94 - bit array.
1.95 + an unresolved new_package:
1.96 +
1.97 + - If the upstream package has the same version as
1.98 + the system package, we have an UP_TO_DATE error
1.99 + (FIXME: not quite right. This doesn't deal with
1.100 + the case where we try to update an application
1.101 + because of a library update, and it turns out
1.102 + there's no new version of the application, but
1.103 + there IS a compat package containing the old
1.104 + version of the library.)
1.105 +
1.106 + - Otherwise, set the rtp's new_package to point to
1.107 + the package providing this property and set the
1.108 + appropriate bit in the upstream bit array.
1.109
1.110 - For each to-be-installed non-file REQUIRES:
1.111