Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit 0bc4b6046baa19f393ea3ebd6064178a080cfe35 created 9 years 24 days ago. By Werner Almesberger, qpkg: added detection of cyclic dependencies | |
---|---|
1 | /* |
2 | * prereq.c - Determine prerequisite packages |
3 | * |
4 | * Written 2010 by Werner Almesberger |
5 | * Copyright 2010 Werner Almesberger |
6 | * |
7 | * This program is free software; you can redistribute it and/or modify |
8 | * it under the terms of the GNU General Public License as published by |
9 | * the Free Software Foundation; either version 2 of the License, or |
10 | * (at your option) any later version. |
11 | */ |
12 | |
13 | |
14 | #include <stdlib.h> |
15 | #include <stdio.h> |
16 | #include <string.h> |
17 | #include <ctype.h> |
18 | #include <assert.h> |
19 | |
20 | #include "id.h" |
21 | #include "qpkg.h" |
22 | #include "util.h" |
23 | #include "prereq.h" |
24 | |
25 | |
26 | struct list { |
27 | const struct ref *refs; |
28 | struct list *next; |
29 | }; |
30 | |
31 | struct stack { |
32 | struct pkg *pkg; |
33 | struct stack *next; |
34 | }; |
35 | |
36 | |
37 | static struct pkg **best = NULL; |
38 | static struct pkg **installs = NULL; |
39 | static int n_best; /* undefined if best == NULL */ |
40 | static int n_install = 0; |
41 | static int install_max = 0; |
42 | static int debug = 0; |
43 | |
44 | |
45 | static int epoch(const char **s, const struct id *id) |
46 | { |
47 | const char *end = id->s+id->len; |
48 | int n = 0; |
49 | |
50 | while (*s != end && isdigit(**s)) { |
51 | n = 10*n+**s-'0'; |
52 | (*s)++; |
53 | } |
54 | if (*s == id->s || (*s != end && **s == ':')) |
55 | return n; |
56 | *s = id->s; |
57 | return 0; |
58 | } |
59 | |
60 | |
61 | static int comp_versions(const struct id *va, const struct id *vb) |
62 | { |
63 | int epoch_a = 0, epoch_b = 0; |
64 | const char *a = va->s; |
65 | const char *b = vb->s; |
66 | const char *ea = a+va->len; |
67 | const char *eb = b+vb->len; |
68 | |
69 | epoch_a = epoch(&a, va); |
70 | epoch_b = epoch(&b, vb); |
71 | if (epoch_a != epoch_b) |
72 | return epoch_a-epoch_b; |
73 | |
74 | while (1) { |
75 | if (a == ea || b == eb) |
76 | return (a != ea)-(b != eb); |
77 | if (isdigit(*a) && isdigit(*b)) { |
78 | int na = 0, nb = 0; |
79 | |
80 | while (a != ea && isdigit(*a)) { |
81 | na = na*10+*a-'0'; |
82 | a++; |
83 | } |
84 | while (b != eb && isdigit(*b)) { |
85 | nb = nb*10+*b-'0'; |
86 | b++; |
87 | } |
88 | if (na == nb) |
89 | continue; |
90 | |
91 | return na-nb; |
92 | } |
93 | if (*a > *b) |
94 | return 1; |
95 | if (*a < *b) |
96 | return 1; |
97 | a++; |
98 | b++; |
99 | } |
100 | } |
101 | |
102 | |
103 | static void done(void) |
104 | { |
105 | int size; |
106 | |
107 | if (best && n_best <= n_install) |
108 | return; |
109 | free(best); |
110 | size = sizeof(*installs)*(n_install+1); |
111 | best = alloc_size(size); |
112 | memcpy(best, installs, sizeof(*installs)*n_install); |
113 | n_best = n_install; |
114 | best[n_best] = NULL; |
115 | } |
116 | |
117 | |
118 | static void append_install(struct pkg *pkg) |
119 | { |
120 | if (n_install == install_max) { |
121 | install_max = (install_max+1)*2; |
122 | installs = realloc(installs, sizeof(*installs)*install_max); |
123 | if (!installs) { |
124 | perror("realloc"); |
125 | exit(1); |
126 | } |
127 | } |
128 | installs[n_install++] = pkg; |
129 | assert(!pkg->mark && !(pkg->flags & QPKG_INSTALLED)); |
130 | pkg->mark = 1; |
131 | } |
132 | |
133 | |
134 | static void backtrack(void) |
135 | { |
136 | assert(n_install); |
137 | n_install--; |
138 | installs[n_install]->mark = 0; |
139 | } |
140 | |
141 | |
142 | static int satisfies(const struct pkg *pkg, const struct ref *ref) |
143 | { |
144 | int cmp; |
145 | |
146 | if (pkg->id != ref->pkg) |
147 | return 0; |
148 | if (!ref->version) |
149 | return 1; |
150 | assert(pkg->version); |
151 | cmp = comp_versions(pkg->version, ref->version); |
152 | //fprintf(stderr, "%.*s <%d> %.*s\n", |
153 | // ID2PF(pkg->version), cmp, ID2PF(ref->version)); |
154 | switch (ref->relop) { |
155 | case rel_eq: |
156 | return !cmp; |
157 | case rel_ge: |
158 | return cmp >= 0; |
159 | case rel_lt: |
160 | return cmp < 0; |
161 | default: |
162 | abort(); |
163 | } |
164 | } |
165 | |
166 | |
167 | static int conflicts(const struct pkg *pkg, const struct list *conf) |
168 | { |
169 | /* @@@ */ |
170 | return 0; |
171 | } |
172 | |
173 | |
174 | static void resolve(struct list *next_dep, const struct ref *dep, |
175 | struct stack *top, struct list *conf) |
176 | { |
177 | static int level = 0; |
178 | struct list more_deps; |
179 | struct list more_conf = { |
180 | .next = conf |
181 | }; |
182 | struct stack stack; |
183 | struct pkg *pkg; |
184 | |
185 | while (!dep) { |
186 | if (!next_dep) { |
187 | done(); |
188 | return; |
189 | } |
190 | assert(top->pkg->flags & QPKG_ADDING); |
191 | top->pkg->flags &= ~QPKG_ADDING; |
192 | top = top->next; |
193 | dep = next_dep->refs; |
194 | next_dep = next_dep->next; |
195 | } |
196 | for (pkg = dep->pkg->jrb->val; pkg; pkg = pkg->more) { |
197 | if (best && n_install == n_best) |
198 | return; |
199 | if (debug) { |
200 | struct stack *p; |
201 | |
202 | fprintf(stderr, "%*s", level, ""); |
203 | fprintf(stderr, "%.*s %p", ID2PF(pkg->id), pkg); |
204 | if (pkg->version) |
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, ")"); |
211 | if (pkg->mark) |
212 | fprintf(stderr, " +"); |
213 | if (pkg->flags & QPKG_INSTALLED) |
214 | fprintf(stderr, " ***"); |
215 | fprintf(stderr, "\n"); |
216 | } |
217 | if (!satisfies(pkg, dep)) |
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 | } |
225 | if ((pkg->flags & QPKG_INSTALLED) || pkg->mark) { |
226 | assert(!conflicts(pkg, conf)); |
227 | resolve(next_dep, dep->next, top, conf); |
228 | continue; |
229 | } |
230 | if (conflicts(pkg, conf)) |
231 | continue; |
232 | level++; |
233 | append_install(pkg); |
234 | more_deps.refs = dep->next; |
235 | more_deps.next = next_dep; |
236 | more_conf.refs = pkg->conflicts; |
237 | more_conf.next = conf; |
238 | stack.pkg = pkg; |
239 | stack.next = top; |
240 | pkg->flags |= QPKG_ADDING; |
241 | resolve(&more_deps, pkg->depends, &stack, &more_conf); |
242 | backtrack(); |
243 | level--; |
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 | */ |
258 | } |
259 | |
260 | |
261 | struct pkg **prereq(struct pkg *pkg) |
262 | { |
263 | struct stack stack = { |
264 | .pkg = pkg, |
265 | .next = NULL |
266 | }; |
267 | /* @@@ make list of pre-existing conflicts */ |
268 | pkg->flags |= QPKG_ADDING; |
269 | resolve(NULL, pkg->depends, &stack, NULL); |
270 | pkg->flags &= ~QPKG_ADDING; |
271 | free(installs); |
272 | return best; |
273 | } |
274 |
Branches:
master