1.1 --- a/DEPSOLVE.txt Fri Mar 07 15:38:31 2008 -0500
1.2 +++ b/DEPSOLVE.txt Mon Mar 10 14:12:31 2008 -0400
1.3 @@ -22,149 +22,145 @@
1.4 - installable (0 bit in the upstream bit array)
1.5
1.6
1.7 -The depsolver repeats the following three steps until there are no new
1.8 -requested installs or removals.
1.9 +Depsolver:
1.10
1.11 -New packages phase. Walk the system and upstream package lists in
1.12 -parallel, and:
1.13 + - Create new razor_transaction_packages ("rtp"s) for each
1.14 + requested install or remove.
1.15
1.16 - - For each package
1.17 + - while there are new rtps:
1.18
1.19 - - If it has newly been added to the requested-installs list,
1.20 - create a razor_transaction_package for it, and set the
1.21 - appropriate bit in the upstream bitarray; if it is an
1.22 - update, clear the appropriate bit in the system bitarray
1.23 + - qsort the new rtps
1.24
1.25 - - If it has newly been added to the requested-removals list,
1.26 - create a razor_transaction_package for it, and clear the
1.27 - appropriate bit in the system bitarray
1.28 + - Walk the system package list, upstream package list, and new
1.29 + rtps in parallel. For each new INSTALL/FORCED_UPDATE rtp,
1.30 + set the "new_package" field and the appropriate bit in the
1.31 + upstream bit array. (For any not-found packages, set an
1.32 + UNAVAILABLE error.) For each new rtp of any type (INSTALL,
1.33 + REMOVE, FORCED_UPDATE, OBSOLETED), if there's a matching
1.34 + system package, set the "old_package" field and clear the
1.35 + appropriate bit in the system bit array.
1.36
1.37 -Properties phase. Walk the system and upstream property lists in
1.38 -parallel, and:
1.39 + - Walk the system and upstream property lists in parallel,
1.40 + and:
1.41
1.42 - - For each to-be-installed non-file REQUIRES:
1.43 + - For each to-be-installed non-file REQUIRES:
1.44
1.45 - - See if there's an installed or to-be-installed package that
1.46 - PROVIDES that property.
1.47 + - See if there's an installed or to-be-installed
1.48 + package that PROVIDES that property.
1.49
1.50 - - If not, see if there's an installable package that PROVIDES
1.51 - that property, and add it to the requested-installs list if
1.52 - so.
1.53 + - If not, see if there's an installable package that
1.54 + PROVIDES that property, and create a new INSTALL rtp
1.55 + for it if 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 + - If not, see if there's a to-be-removed package that
1.61 + PROVIDES that property. (If we find such a package,
1.62 + we have a CONTRADICTION error.)
1.63
1.64 - - If none of the above, then we have an UNSATISFIABLE error
1.65 + - If none of the above, then we have an UNSATISFIABLE
1.66 + error
1.67
1.68 - - For each to-be-installed file REQUIRES:
1.69 + - For each to-be-installed file REQUIRES:
1.70
1.71 - - Same as for property REQUIRES, except that since we have to
1.72 - search the file tree, this is not O(1). (See below for more
1.73 - discussion.)
1.74 + - (We create fake file PROVIDES to match file REQUIRES
1.75 + when importing/merging razor sets, so if there is
1.76 + already another installed package that REQUIRES this
1.77 + file, there will be a PROVIDES listed for it as well.)
1.78
1.79 - - For each to-be-installed PROVIDES:
1.80 + - See if there's an installed package that PROVIDES
1.81 + that file.
1.82
1.83 - - Check if the new PROVIDES conflicts with an installed
1.84 - CONFLICTS. If so, add the installed package to the
1.85 - requested-installs list, so we can try to upgrade it to a
1.86 - non-conflicting version.
1.87 + - If not, do a binary search of the system file tree
1.88 + looking to see if some installed package provides
1.89 + that file but does not have a PROVIDES for it.
1.90
1.91 - - Check if the new PROVIDES conflicts with a to-be-installed
1.92 - CONFLICTS. If so, we have an OLD_CONFLICT error.
1.93 + - If not, see if there's an installable package that
1.94 + PROVIDES that property, and create a new INSTALL rtp
1.95 + for it if so.
1.96
1.97 - - For each to-be-installed CONFLICTS:
1.98 + - (If we actually work with multiple upstream
1.99 + razor_sets, then we will need to search the upstream
1.100 + file trees at this point, because it's possible that
1.101 + a package in one upstream repo would require a file
1.102 + in another upstream repo. But if we merge the
1.103 + multiple upstream repos into a single razor_set at
1.104 + some point, then we would not need to do that,
1.105 + because it would be guaranteed that we would have
1.106 + already created a fake PROVIDES if any package
1.107 + provides the file.)
1.108
1.109 - - Basically the reverse of the previous case: check if the new
1.110 - CONFLICTS conflicts with an installed PROVIDES. If so, add
1.111 - the installed package to the requested-installs list to try
1.112 - to upgrade it.
1.113 + - If no installed or installable package provides the
1.114 + file, see if there's a to-be-removed package that
1.115 + provides the file. (If we find such a package, we
1.116 + have a CONTRADICTION error.)
1.117
1.118 - - Check if the new CONFLICTS conflicts with a to-be-installed
1.119 - PROVIDES. If so, we have an NEW_CONFLICT error.
1.120 + - If none of the above, then we have an UNSATISFIABLE
1.121 + error
1.122
1.123 - - For each to-be-installed OBSOLETES:
1.124 + - For each to-be-installed PROVIDES:
1.125
1.126 - - Check if there's an installed package that PROVIDES that
1.127 - property. If so, add that package to the requested-removals
1.128 - list, noting it should be marked obsolete. ("Obsolete" means
1.129 - that the to-be-removed PROVIDES step below will treat it
1.130 - like it was upgraded, not removed.)
1.131 + - Check if the new PROVIDES conflicts with an
1.132 + installed CONFLICTS. If so, create a new
1.133 + FORCED_UPDATE rtp for the installed package, so we
1.134 + can try to upgrade it to a non-conflicting version.
1.135 + (If we can't, we'll have an OLD_CONFLICT error.)
1.136
1.137 - - If not, check if there's a to-be-installed package that
1.138 - PROVIDES that property. If so, we have a CONTRADICTION
1.139 - error.
1.140 + - Check if the new PROVIDES conflicts with an
1.141 + installed OBSOLETES *and* the PROVIDES property
1.142 + corresponds to the name of its package. (That is,
1.143 + OBSOLETES are only matched against package names,
1.144 + not arbitrary provided properties.) If so, we have
1.145 + an ALREADY_OBSOLETE error.
1.146
1.147 - - For each to-be-removed PROVIDES:
1.148 + - Check if the new PROVIDES conflicts with a
1.149 + to-be-installed CONFLICTS. If so, we have a
1.150 + CONTRADICTION error.
1.151
1.152 - - If there's also an identical to-be-installed PROVIDES, we're
1.153 - ok and can skip this
1.154 + - For each to-be-installed CONFLICTS:
1.155
1.156 - - Otherwise, for each installed REQUIRES of this property:
1.157 + - Basically the reverse of the previous case: check if
1.158 + the new CONFLICTS conflicts with an installed
1.159 + PROVIDES. If so, create a new FORCED_UPDATE rtp for
1.160 + the installed package, so we can try to upgrade it
1.161 + to a non-conflicting version. (If we can't, we'll
1.162 + have an NEW_CONFLICT error.)
1.163
1.164 - - Look for some other installed or to-be-installed package
1.165 - that satisfies the REQUIRES.
1.166 + - Check if the new CONFLICTS conflicts with a
1.167 + to-be-installed PROVIDES. If so, we have a
1.168 + CONTRADICTION error.
1.169
1.170 - - If there isn't one, then for each installed package in
1.171 - this REQUIRES's package list:
1.172 + - For each to-be-installed OBSOLETES:
1.173
1.174 - - If the PROVIDES was lost because the old package was
1.175 - removed (not updated or obsoleted), then add the
1.176 - requiring package to the requested-removals list.
1.177 + - Check if there's an installed package that PROVIDES
1.178 + that property. If so, create an OBSOLETED rtp for
1.179 + the installed package.
1.180
1.181 - - Otherwise, add the requiring package to the
1.182 - requested-installs list so it can be updated as
1.183 - well.
1.184 + - If not, check if there's a to-be-installed package
1.185 + that PROVIDES that property. If so, we have a
1.186 + CONTRADICTION error.
1.187
1.188 - - (We don't need to look at to-be-installed REQUIRES of this
1.189 - property, because if there are any, they will cause a
1.190 - CONTRADICTION error when we try to re-satisfy them the next
1.191 - time through.)
1.192 + - For each to-be-removed PROVIDES:
1.193
1.194 - - For each installed file REQUIRES:
1.195 + - If there's also an identical to-be-installed
1.196 + PROVIDES, we're ok and can skip this
1.197
1.198 - - Check that the file is still installed. If not, check if
1.199 - a to-be-installed package also provides it.
1.200 + - Otherwise, for each installed REQUIRES of this
1.201 + property:
1.202
1.203 - - If not:
1.204 + - Look for some other installed or to-be-installed
1.205 + property that satisfies the REQUIRES.
1.206
1.207 - - If the package originally providing it was removed (not
1.208 - updated or obsoleted), then add the requiring package to
1.209 - the requested-removals list.
1.210 + - If there isn't one, then for each installed
1.211 + package in this REQUIRES's package list:
1.212
1.213 - - Otherwise, add the requiring package to the
1.214 - requested-installs list, in the hope that an upgrade
1.215 - will no longer require the file
1.216 + - If the PROVIDES was lost because the old
1.217 + package was REMOVEd (not FORCED_UPDATE or
1.218 + OBSOLETED), then create a new REMOVE rtp for
1.219 + this package.
1.220
1.221 -(End)
1.222 + - Otherwise, create a new FORCED_UPDATE rtp
1.223 + for this package.
1.224
1.225 -
1.226 -Note on file dependencies
1.227 -
1.228 - - With this algorithm, the total time spent satisfying file
1.229 - dependencies is O(D * log F), where D is the total number of
1.230 - file dependencies being added or removed, and F is the total
1.231 - number of files.
1.232 -
1.233 - - If we sorted the file list differently, we could walk it in
1.234 - parallel with the property lists, resulting in an overall
1.235 - file-require-satisfying time of O(F). However, F is likely to be
1.236 - much much greater than D * log F, so this would probably end up
1.237 - actually being a pessimization.
1.238 -
1.239 - - A better solution (assuming that we do actually need an O(1)
1.240 - algorithm here) would be to add explicit file PROVIDES
1.241 - properties to the set as needed. That is, whenever we add a
1.242 - package containing a "REQUIRES /foo" property to a set, we also
1.243 - add a "PROVIDES /foo" property to the set, pointing to the
1.244 - correct provider packages. More than half of all file requires
1.245 - are on /bin/sh or /sbin/ldconfig, and of the 7263 file requires
1.246 - in 9306 packages currently in rawhide.repo, only 154 are not
1.247 - satisfied by my system.repo. So storing file provides in the
1.248 - property list as they are needed would eliminate the need to
1.249 - search through the file list 99% of the time.
1.250 -
1.251 - (We might need a separate optimization for the
1.252 - building-the-system-up-from-empty case in the installer, since
1.253 - we'd be resolving the whole transaction without having explicit
1.254 - PROVIDES listed for /bin/sh, etc.)
1.255 + - (We don't need to look at to-be-installed REQUIRES
1.256 + of this property, because if there are any, they
1.257 + will cause a CONTRADICTION error when we try to
1.258 + re-satisfy them the next time through.)