1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/DEPSOLVE.txt Fri Mar 07 15:38:31 2008 -0500
1.3 @@ -0,0 +1,170 @@
1.4 +We start with two razor_sets, system and upstream, and a list of
1.5 +requested installations and removals.
1.6 +
1.7 + FIXME: what about multiple upstream repos? Having to deal with
1.8 + arbitrary numbers of razor_sets is possible, but will probably be
1.9 + messy... It might be easier to either store all upstream repo data
1.10 + in a single .repo file, or else merge all upstream .repo files
1.11 + together into a single razor_set at startup. (Or some combination
1.12 + of those.)
1.13 +
1.14 +We create a bit array of the packages in each set, indicating which
1.15 +ones are installed; the system bitarray starts out all 1s, and the
1.16 +upstream bitarray all 0s. Each bit is only allowed to change state
1.17 +once during the transaction; an installed package can be removed, or
1.18 +an uninstalled package installed, but trying to reinstall a removed
1.19 +package, or uninstall a newly-installed package is an error. This
1.20 +means the packages break down into four categories:
1.21 +
1.22 + - installed (1 bit in the system bit array)
1.23 + - to-be-removed (0 bit in the system bit array)
1.24 + - to-be-installed (1 bit in the upstream bit array)
1.25 + - installable (0 bit in the upstream bit array)
1.26 +
1.27 +
1.28 +The depsolver repeats the following three steps until there are no new
1.29 +requested installs or removals.
1.30 +
1.31 +New packages phase. Walk the system and upstream package lists in
1.32 +parallel, and:
1.33 +
1.34 + - For each package
1.35 +
1.36 + - If it has newly been added to the requested-installs list,
1.37 + create a razor_transaction_package for it, and set the
1.38 + appropriate bit in the upstream bitarray; if it is an
1.39 + update, clear the appropriate bit in the system bitarray
1.40 +
1.41 + - If it has newly been added to the requested-removals list,
1.42 + create a razor_transaction_package for it, and clear the
1.43 + appropriate bit in the system bitarray
1.44 +
1.45 +Properties phase. Walk the system and upstream property lists in
1.46 +parallel, and:
1.47 +
1.48 + - For each to-be-installed non-file REQUIRES:
1.49 +
1.50 + - See if there's an installed or to-be-installed package that
1.51 + PROVIDES that property.
1.52 +
1.53 + - If not, see if there's an installable package that PROVIDES
1.54 + that property, and add it to the requested-installs list if
1.55 + so.
1.56 +
1.57 + - If not, see if there's a to-be-removed package that PROVIDES
1.58 + that property. (If we find such a package, we have a
1.59 + CONTRADICTION error.)
1.60 +
1.61 + - If none of the above, then we have an UNSATISFIABLE error
1.62 +
1.63 + - For each to-be-installed file REQUIRES:
1.64 +
1.65 + - Same as for property REQUIRES, except that since we have to
1.66 + search the file tree, this is not O(1). (See below for more
1.67 + discussion.)
1.68 +
1.69 + - For each to-be-installed PROVIDES:
1.70 +
1.71 + - Check if the new PROVIDES conflicts with an installed
1.72 + CONFLICTS. If so, add the installed package to the
1.73 + requested-installs list, so we can try to upgrade it to a
1.74 + non-conflicting version.
1.75 +
1.76 + - Check if the new PROVIDES conflicts with a to-be-installed
1.77 + CONFLICTS. If so, we have an OLD_CONFLICT error.
1.78 +
1.79 + - For each to-be-installed CONFLICTS:
1.80 +
1.81 + - Basically the reverse of the previous case: check if the new
1.82 + CONFLICTS conflicts with an installed PROVIDES. If so, add
1.83 + the installed package to the requested-installs list to try
1.84 + to upgrade it.
1.85 +
1.86 + - Check if the new CONFLICTS conflicts with a to-be-installed
1.87 + PROVIDES. If so, we have an NEW_CONFLICT error.
1.88 +
1.89 + - For each to-be-installed OBSOLETES:
1.90 +
1.91 + - Check if there's an installed package that PROVIDES that
1.92 + property. If so, add that package to the requested-removals
1.93 + list, noting it should be marked obsolete. ("Obsolete" means
1.94 + that the to-be-removed PROVIDES step below will treat it
1.95 + like it was upgraded, not removed.)
1.96 +
1.97 + - If not, check if there's a to-be-installed package that
1.98 + PROVIDES that property. If so, we have a CONTRADICTION
1.99 + error.
1.100 +
1.101 + - For each to-be-removed PROVIDES:
1.102 +
1.103 + - If there's also an identical to-be-installed PROVIDES, we're
1.104 + ok and can skip this
1.105 +
1.106 + - Otherwise, for each installed REQUIRES of this property:
1.107 +
1.108 + - Look for some other installed or to-be-installed package
1.109 + that satisfies the REQUIRES.
1.110 +
1.111 + - If there isn't one, then for each installed package in
1.112 + this REQUIRES's package list:
1.113 +
1.114 + - If the PROVIDES was lost because the old package was
1.115 + removed (not updated or obsoleted), then add the
1.116 + requiring package to the requested-removals list.
1.117 +
1.118 + - Otherwise, add the requiring package to the
1.119 + requested-installs list so it can be updated as
1.120 + well.
1.121 +
1.122 + - (We don't need to look at to-be-installed REQUIRES of this
1.123 + property, because if there are any, they will cause a
1.124 + CONTRADICTION error when we try to re-satisfy them the next
1.125 + time through.)
1.126 +
1.127 + - For each installed file REQUIRES:
1.128 +
1.129 + - Check that the file is still installed. If not, check if
1.130 + a to-be-installed package also provides it.
1.131 +
1.132 + - If not:
1.133 +
1.134 + - If the package originally providing it was removed (not
1.135 + updated or obsoleted), then add the requiring package to
1.136 + the requested-removals list.
1.137 +
1.138 + - Otherwise, add the requiring package to the
1.139 + requested-installs list, in the hope that an upgrade
1.140 + will no longer require the file
1.141 +
1.142 +(End)
1.143 +
1.144 +
1.145 +Note on file dependencies
1.146 +
1.147 + - With this algorithm, the total time spent satisfying file
1.148 + dependencies is O(D * log F), where D is the total number of
1.149 + file dependencies being added or removed, and F is the total
1.150 + number of files.
1.151 +
1.152 + - If we sorted the file list differently, we could walk it in
1.153 + parallel with the property lists, resulting in an overall
1.154 + file-require-satisfying time of O(F). However, F is likely to be
1.155 + much much greater than D * log F, so this would probably end up
1.156 + actually being a pessimization.
1.157 +
1.158 + - A better solution (assuming that we do actually need an O(1)
1.159 + algorithm here) would be to add explicit file PROVIDES
1.160 + properties to the set as needed. That is, whenever we add a
1.161 + package containing a "REQUIRES /foo" property to a set, we also
1.162 + add a "PROVIDES /foo" property to the set, pointing to the
1.163 + correct provider packages. More than half of all file requires
1.164 + are on /bin/sh or /sbin/ldconfig, and of the 7263 file requires
1.165 + in 9306 packages currently in rawhide.repo, only 154 are not
1.166 + satisfied by my system.repo. So storing file provides in the
1.167 + property list as they are needed would eliminate the need to
1.168 + search through the file list 99% of the time.
1.169 +
1.170 + (We might need a separate optimization for the
1.171 + building-the-system-up-from-empty case in the installer, since
1.172 + we'd be resolving the whole transaction without having explicit
1.173 + PROVIDES listed for /bin/sh, etc.)