1 We start with two razor_sets, system and upstream, and a list of
2 requested installations and removals.
4 FIXME: what about multiple upstream repos? Having to deal with
5 arbitrary numbers of razor_sets is possible, but will probably be
6 messy... It might be easier to either store all upstream repo data
7 in a single .repo file, or else merge all upstream .repo files
8 together into a single razor_set at startup. (Or some combination
11 We create a bit array of the packages in each set, indicating which
12 ones are installed; the system bitarray starts out all 1s, and the
13 upstream bitarray all 0s. Each bit is only allowed to change state
14 once during the transaction; an installed package can be removed, or
15 an uninstalled package installed, but trying to reinstall a removed
16 package, or uninstall a newly-installed package is an error. This
17 means the packages break down into four categories:
19 - installed (1 bit in the system bit array)
20 - to-be-removed (0 bit in the system bit array)
21 - to-be-installed (1 bit in the upstream bit array)
22 - installable (0 bit in the upstream bit array)
25 The depsolver repeats the following three steps until there are no new
26 requested installs or removals.
28 New packages phase. Walk the system and upstream package lists in
33 - If it has newly been added to the requested-installs list,
34 create a razor_transaction_package for it, and set the
35 appropriate bit in the upstream bitarray; if it is an
36 update, clear the appropriate bit in the system bitarray
38 - If it has newly been added to the requested-removals list,
39 create a razor_transaction_package for it, and clear the
40 appropriate bit in the system bitarray
42 Properties phase. Walk the system and upstream property lists in
45 - For each to-be-installed non-file REQUIRES:
47 - See if there's an installed or to-be-installed package that
48 PROVIDES that property.
50 - If not, see if there's an installable package that PROVIDES
51 that property, and add it to the requested-installs list if
54 - If not, see if there's a to-be-removed package that PROVIDES
55 that property. (If we find such a package, we have a
58 - If none of the above, then we have an UNSATISFIABLE error
60 - For each to-be-installed file REQUIRES:
62 - Same as for property REQUIRES, except that since we have to
63 search the file tree, this is not O(1). (See below for more
66 - For each to-be-installed PROVIDES:
68 - Check if the new PROVIDES conflicts with an installed
69 CONFLICTS. If so, add the installed package to the
70 requested-installs list, so we can try to upgrade it to a
71 non-conflicting version.
73 - Check if the new PROVIDES conflicts with a to-be-installed
74 CONFLICTS. If so, we have an OLD_CONFLICT error.
76 - For each to-be-installed CONFLICTS:
78 - Basically the reverse of the previous case: check if the new
79 CONFLICTS conflicts with an installed PROVIDES. If so, add
80 the installed package to the requested-installs list to try
83 - Check if the new CONFLICTS conflicts with a to-be-installed
84 PROVIDES. If so, we have an NEW_CONFLICT error.
86 - For each to-be-installed OBSOLETES:
88 - Check if there's an installed package that PROVIDES that
89 property. If so, add that package to the requested-removals
90 list, noting it should be marked obsolete. ("Obsolete" means
91 that the to-be-removed PROVIDES step below will treat it
92 like it was upgraded, not removed.)
94 - If not, check if there's a to-be-installed package that
95 PROVIDES that property. If so, we have a CONTRADICTION
98 - For each to-be-removed PROVIDES:
100 - If there's also an identical to-be-installed PROVIDES, we're
103 - Otherwise, for each installed REQUIRES of this property:
105 - Look for some other installed or to-be-installed package
106 that satisfies the REQUIRES.
108 - If there isn't one, then for each installed package in
109 this REQUIRES's package list:
111 - If the PROVIDES was lost because the old package was
112 removed (not updated or obsoleted), then add the
113 requiring package to the requested-removals list.
115 - Otherwise, add the requiring package to the
116 requested-installs list so it can be updated as
119 - (We don't need to look at to-be-installed REQUIRES of this
120 property, because if there are any, they will cause a
121 CONTRADICTION error when we try to re-satisfy them the next
124 - For each installed file REQUIRES:
126 - Check that the file is still installed. If not, check if
127 a to-be-installed package also provides it.
131 - If the package originally providing it was removed (not
132 updated or obsoleted), then add the requiring package to
133 the requested-removals list.
135 - Otherwise, add the requiring package to the
136 requested-installs list, in the hope that an upgrade
137 will no longer require the file
142 Note on file dependencies
144 - With this algorithm, the total time spent satisfying file
145 dependencies is O(D * log F), where D is the total number of
146 file dependencies being added or removed, and F is the total
149 - If we sorted the file list differently, we could walk it in
150 parallel with the property lists, resulting in an overall
151 file-require-satisfying time of O(F). However, F is likely to be
152 much much greater than D * log F, so this would probably end up
153 actually being a pessimization.
155 - A better solution (assuming that we do actually need an O(1)
156 algorithm here) would be to add explicit file PROVIDES
157 properties to the set as needed. That is, whenever we add a
158 package containing a "REQUIRES /foo" property to a set, we also
159 add a "PROVIDES /foo" property to the set, pointing to the
160 correct provider packages. More than half of all file requires
161 are on /bin/sh or /sbin/ldconfig, and of the 7263 file requires
162 in 9306 packages currently in rawhide.repo, only 154 are not
163 satisfied by my system.repo. So storing file provides in the
164 property list as they are needed would eliminate the need to
165 search through the file list 99% of the time.
167 (We might need a separate optimization for the
168 building-the-system-up-from-empty case in the installer, since
169 we'd be resolving the whole transaction without having explicit
170 PROVIDES listed for /bin/sh, etc.)