Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Commit Details
Date: | 2010-11-22 00:31:20 (13 years 4 months ago) |
---|---|
Author: | Werner Almesberger |
Commit: | 0bc4b6046baa19f393ea3ebd6064178a080cfe35 |
Message: | qpkg: added detection of cyclic dependencies We define a cyclic dependency as the possibility (!) of the prerequisites of a package X including a package that depends on X, and issue an error if encountering such a situation. Note that, if the dependencies of X can be resolved in a manner that does not include the cyclic dependency, qpkg will still fail if it encounters the cycle. Also note that qpkg (at least so far) does no perform an exhaustive search to ferret out cyclic dependencies. Furthermore, we don't consider that a cyclic dependency may not necessarily imply a real life problem. E.g., if a package A contains elements X and Y, with X needing package B, and the content of package B has a run-time dependency on Y, the cyclic dependency between A and B would not exist when considering its constituents. Since we don't have this information, we just err on the side of caution. - qpkg.h (enum flags): divide flags into categories (parse-time and run-time) and add flag QPKG_ADDING to mark packets whose dependencies we are processing - prereq.c (resolve, prereq): track which packages we're tentatively considering for installation and detect cyclic dependencies - test/cyclic: regression test for detection of cyclic dependencies - TODO: updated with recent changes |
Files: |
qpkg/TODO (2 diffs) qpkg/prereq.c (7 diffs) qpkg/qpkg.h (1 diff) qpkg/test/cyclic (1 diff) |
Change Details
qpkg/TODO | ||
---|---|---|
13 | 13 | |
14 | 14 | - consider Architecture: |
15 | 15 | |
16 | Update: we parse and record it now but don't use it yet. | |
17 | ||
16 | 18 | - what to do with explicit and implicit replacement ? |
17 | 19 | |
18 | 20 | - if we can't resolve the prerequisites, give at least a hint of what one |
... | ... | |
20 | 22 | |
21 | 23 | - check database for internal consistency |
22 | 24 | |
25 | Update: added detection of cyclic dependencies (in progress) | |
26 | ||
23 | 27 | - implement keyword search |
24 | 28 | |
25 | 29 | - consider also supporting the similar but not identical (parent ?) format |
qpkg/prereq.c | ||
---|---|---|
28 | 28 | struct list *next; |
29 | 29 | }; |
30 | 30 | |
31 | struct stack { | |
32 | struct pkg *pkg; | |
33 | struct stack *next; | |
34 | }; | |
35 | ||
31 | 36 | |
32 | 37 | static struct pkg **best = NULL; |
33 | 38 | static struct pkg **installs = NULL; |
... | ... | |
119 | 124 | perror("realloc"); |
120 | 125 | exit(1); |
121 | 126 | } |
122 | ||
123 | 127 | } |
124 | 128 | installs[n_install++] = pkg; |
125 | 129 | assert(!pkg->mark && !(pkg->flags & QPKG_INSTALLED)); |
... | ... | |
168 | 172 | |
169 | 173 | |
170 | 174 | static void resolve(struct list *next_dep, const struct ref *dep, |
171 | struct list *conf) | |
175 | struct stack *top, struct list *conf) | |
172 | 176 | { |
173 | 177 | static int level = 0; |
174 | 178 | struct list more_deps; |
175 | 179 | struct list more_conf = { |
176 | 180 | .next = conf |
177 | 181 | }; |
182 | struct stack stack; | |
178 | 183 | struct pkg *pkg; |
179 | 184 | |
180 | 185 | while (!dep) { |
... | ... | |
182 | 187 | done(); |
183 | 188 | return; |
184 | 189 | } |
190 | assert(top->pkg->flags & QPKG_ADDING); | |
191 | top->pkg->flags &= ~QPKG_ADDING; | |
192 | top = top->next; | |
185 | 193 | dep = next_dep->refs; |
186 | 194 | next_dep = next_dep->next; |
187 | 195 | } |
... | ... | |
189 | 197 | if (best && n_install == n_best) |
190 | 198 | return; |
191 | 199 | if (debug) { |
200 | struct stack *p; | |
201 | ||
192 | 202 | fprintf(stderr, "%*s", level, ""); |
193 | 203 | fprintf(stderr, "%.*s %p", ID2PF(pkg->id), pkg); |
194 | 204 | if (pkg->version) |
195 | 205 | fprintf(stderr, " %.*s", ID2PF(pkg->version)); |
206 | fprintf(stderr, " ("); | |
207 | for (p = top; p; p = p->next) | |
208 | fprintf(stderr, "%s%.*s", | |
209 | p == top ? "" : " ", ID2PF(p->pkg->id)); | |
210 | fprintf(stderr, ")"); | |
196 | 211 | if (pkg->mark) |
197 | 212 | fprintf(stderr, " +"); |
198 | 213 | if (pkg->flags & QPKG_INSTALLED) |
... | ... | |
201 | 216 | } |
202 | 217 | if (!satisfies(pkg, dep)) |
203 | 218 | continue; |
219 | if (pkg->flags & QPKG_ADDING) { | |
220 | fprintf(stderr, "package %.*s version %.*s " | |
221 | "has cyclic dependency\n", | |
222 | ID2PF(pkg->id), ID2PF(pkg->version)); | |
223 | exit(1); | |
224 | } | |
204 | 225 | if ((pkg->flags & QPKG_INSTALLED) || pkg->mark) { |
205 | 226 | assert(!conflicts(pkg, conf)); |
206 | resolve(next_dep, dep->next, conf); | |
227 | resolve(next_dep, dep->next, top, conf); | |
207 | 228 | continue; |
208 | 229 | } |
209 | 230 | if (conflicts(pkg, conf)) |
... | ... | |
214 | 235 | more_deps.next = next_dep; |
215 | 236 | more_conf.refs = pkg->conflicts; |
216 | 237 | more_conf.next = conf; |
217 | resolve(&more_deps, pkg->depends, &more_conf); | |
238 | stack.pkg = pkg; | |
239 | stack.next = top; | |
240 | pkg->flags |= QPKG_ADDING; | |
241 | resolve(&more_deps, pkg->depends, &stack, &more_conf); | |
218 | 242 | backtrack(); |
219 | 243 | level--; |
220 | 244 | } |
245 | ||
246 | /* | |
247 | * @@@ this shouldn't be all of the story yet. if we fail a dependency | |
248 | * due to a conflict, the current algorithm may leave packages marked | |
249 | * as QPKG_ADDING, possibly triggering a false cyclic dependency error. | |
250 | * | |
251 | * In the case if cycle detection, we could avoid all the hassle of | |
252 | * maintaining this flag and just walk down the stack to see if we're | |
253 | * already trying to add the package (the stack should be correct with | |
254 | * the current algorithm), but we'll need this kind of accurate | |
255 | * tracking of package state for ordering the dependencies and for | |
256 | * "Provides" anyway. | |
257 | */ | |
221 | 258 | } |
222 | 259 | |
223 | 260 | |
224 | 261 | struct pkg **prereq(struct pkg *pkg) |
225 | 262 | { |
263 | struct stack stack = { | |
264 | .pkg = pkg, | |
265 | .next = NULL | |
266 | }; | |
226 | 267 | /* @@@ make list of pre-existing conflicts */ |
227 | resolve(NULL, pkg->depends, NULL); | |
268 | pkg->flags |= QPKG_ADDING; | |
269 | resolve(NULL, pkg->depends, &stack, NULL); | |
270 | pkg->flags &= ~QPKG_ADDING; | |
228 | 271 | free(installs); |
229 | 272 | return best; |
230 | 273 | } |
qpkg/qpkg.h | ||
---|---|---|
14 | 14 | #define QPKG_H |
15 | 15 | |
16 | 16 | enum flags { |
17 | /* parse-time flags */ | |
17 | 18 | QPKG_INSTALLED = 1 << 0, /* installed on target */ |
19 | ||
20 | /* run-time flags */ | |
21 | QPKG_ADDING = 1 << 10, /* resolving dependencies */ | |
18 | 22 | }; |
19 | 23 | |
20 | 24 | enum relop { |
qpkg/test/cyclic | ||
---|---|---|
1 | #!/bin/sh | |
2 | . ./Common | |
3 | ||
4 | ############################################################################### | |
5 | ||
6 | qpkg_fail "cyclic dependency (one step)" prereq foo <<EOF | |
7 | Package: foo | |
8 | Version: 0 | |
9 | Architecture: test | |
10 | Depends: foo | |
11 | Filename: foo_0_test.ipkg | |
12 | EOF | |
13 | expect <<EOF | |
14 | package foo version 0 has cyclic dependency | |
15 | EOF | |
16 | ||
17 | ############################################################################### | |
18 | ||
19 | qpkg_fail "cyclic dependency (two steps)" prereq foo <<EOF | |
20 | Package: bar | |
21 | Version: 1 | |
22 | Architecture: test | |
23 | Depends: foo | |
24 | Filename: bar_1_test.ipkg | |
25 | ||
26 | Package: foo | |
27 | Version: 0 | |
28 | Architecture: test | |
29 | Depends: bar | |
30 | Filename: foo_0_test.ipkg | |
31 | EOF | |
32 | expect <<EOF | |
33 | package foo version 0 has cyclic dependency | |
34 | EOF |
Branches:
master