Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit f6fd776f528905e346c7f1caec97945535c7ca43 created 12 years 4 months ago. By Werner Almesberger, m1/patches/rtems/: Milkymist-specific patches are in upstream (update by Xiangfu) | |
---|---|
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 <assert.h> |
18 | |
19 | #include "util.h" |
20 | #include "id.h" |
21 | #include "pkg.h" |
22 | #include "qpkg.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 | |
43 | |
44 | /* ----- List of packages considered for installation ---------------------- */ |
45 | |
46 | |
47 | static void done(void) |
48 | { |
49 | int size; |
50 | |
51 | if (best && n_best <= n_install) |
52 | return; |
53 | free(best); |
54 | size = sizeof(*installs)*(n_install+1); |
55 | best = alloc_size(size); |
56 | memcpy(best, installs, sizeof(*installs)*n_install); |
57 | n_best = n_install; |
58 | best[n_best] = NULL; |
59 | } |
60 | |
61 | |
62 | static void append_install(struct pkg *pkg) |
63 | { |
64 | if (n_install == install_max) { |
65 | install_max = (install_max+1)*2; |
66 | installs = realloc(installs, sizeof(*installs)*install_max); |
67 | if (!installs) { |
68 | perror("realloc"); |
69 | exit(1); |
70 | } |
71 | } |
72 | installs[n_install++] = pkg; |
73 | assert(!pkg->mark && !(pkg->flags & QPKG_INSTALLED)); |
74 | pkg->mark = 1; |
75 | } |
76 | |
77 | |
78 | static void backtrack(void) |
79 | { |
80 | assert(n_install); |
81 | n_install--; |
82 | installs[n_install]->mark = 0; |
83 | } |
84 | |
85 | |
86 | /* ----- Check dependencies and conflicts ---------------------------------- */ |
87 | |
88 | |
89 | static int satisfies(const struct pkg *pkg, const struct ref *ref) |
90 | { |
91 | int cmp; |
92 | |
93 | if (pkg->id != ref->pkg) |
94 | return 0; |
95 | if (!ref->version) |
96 | return 1; |
97 | /* @@@ error in the database, not qpkg's fault */ |
98 | assert(pkg->version); |
99 | cmp = comp_versions(pkg->version, ref->version); |
100 | //fprintf(stderr, "%.*s <%d> %.*s\n", |
101 | // ID2PF(pkg->version), cmp, ID2PF(ref->version)); |
102 | switch (ref->relop) { |
103 | case rel_eq: |
104 | return !cmp; |
105 | case rel_ge: |
106 | return cmp >= 0; |
107 | case rel_lt: |
108 | return cmp < 0; |
109 | default: |
110 | abort(); |
111 | } |
112 | } |
113 | |
114 | |
115 | static int old_conflicts(const struct pkg *pkg, const struct list *conf) |
116 | { |
117 | const struct ref *ref; |
118 | |
119 | while (conf) { |
120 | for (ref = conf->refs; ref; ref = ref->next) |
121 | if (satisfies(pkg, ref)) |
122 | return 1; |
123 | conf = conf->next; |
124 | } |
125 | return 0; |
126 | } |
127 | |
128 | |
129 | static int new_conflicts(const struct ref *refs) |
130 | { |
131 | const struct ref *ref; |
132 | const struct pkg *pkg; |
133 | |
134 | for (ref = refs; ref; ref = ref->next) |
135 | for (pkg = ref->pkg->jrb->val; pkg; pkg = pkg->more) |
136 | if ((pkg->flags & (QPKG_INSTALLED | QPKG_ADDING)) || |
137 | pkg->mark) |
138 | if (satisfies(pkg, ref)) |
139 | return 1; |
140 | return 0; |
141 | } |
142 | |
143 | |
144 | /* ----- Recurse through lists and layers of dependencies ------------------ */ |
145 | |
146 | |
147 | static void print_debug(const struct pkg *pkg, const struct stack *top, |
148 | int level) |
149 | { |
150 | const struct stack *p; |
151 | |
152 | fprintf(stderr, "%*s", level, ""); |
153 | fprintf(stderr, "%.*s %p", ID2PF(pkg->id), pkg); |
154 | if (pkg->version) |
155 | fprintf(stderr, " %.*s", ID2PF(pkg->version)); |
156 | fprintf(stderr, " ("); |
157 | for (p = top; p; p = p->next) |
158 | fprintf(stderr, "%s%.*s", |
159 | p == top ? "" : " ", ID2PF(p->pkg->id)); |
160 | fprintf(stderr, ")"); |
161 | if (pkg->mark) |
162 | fprintf(stderr, " +"); |
163 | if (pkg->flags & QPKG_INSTALLED) |
164 | fprintf(stderr, " ***"); |
165 | fprintf(stderr, "\n"); |
166 | } |
167 | |
168 | |
169 | static void resolve(struct list *next_deps, const struct ref *dep, |
170 | struct stack *top, struct list *conf) |
171 | { |
172 | static int level = 0; |
173 | struct list more_deps; |
174 | struct list more_conf = { |
175 | .next = conf |
176 | }; |
177 | struct stack stack; |
178 | struct pkg *pkg; |
179 | |
180 | while (!dep) { |
181 | if (!next_deps) { |
182 | done(); |
183 | return; |
184 | } |
185 | assert(top->pkg->flags & QPKG_ADDING); |
186 | top->pkg->flags &= ~QPKG_ADDING; |
187 | top = top->next; |
188 | dep = next_deps->refs; |
189 | next_deps = next_deps->next; |
190 | } |
191 | for (pkg = dep->pkg->jrb->val; pkg; pkg = pkg->more) { |
192 | if (best && n_install == n_best) |
193 | break; |
194 | if (pkg->flags & QPKG_PROVIDED) |
195 | continue; |
196 | if (debug) |
197 | print_debug(pkg, top, level); |
198 | if (!satisfies(pkg, dep)) |
199 | continue; |
200 | if (pkg->flags & QPKG_ADDING) { |
201 | fprintf(stderr, "package %.*s version %.*s " |
202 | "has cyclic dependency\n", |
203 | ID2PF(pkg->id), ID2PF(pkg->version)); |
204 | exit(1); |
205 | } |
206 | if ((pkg->flags & QPKG_INSTALLED) || pkg->mark) { |
207 | assert(!old_conflicts(pkg, conf)); |
208 | resolve(next_deps, dep->next, top, conf); |
209 | continue; |
210 | } |
211 | if (old_conflicts(pkg, conf)) |
212 | continue; |
213 | if (new_conflicts(pkg->conflicts)) |
214 | continue; |
215 | level++; |
216 | append_install(pkg); |
217 | more_deps.refs = dep->next; |
218 | more_deps.next = next_deps; |
219 | more_conf.refs = pkg->conflicts; |
220 | more_conf.next = conf; |
221 | stack.pkg = pkg; |
222 | stack.next = top; |
223 | pkg->flags |= QPKG_ADDING; |
224 | resolve(&more_deps, pkg->depends, &stack, &more_conf); |
225 | backtrack(); |
226 | level--; |
227 | } |
228 | |
229 | /* |
230 | * @@@ this shouldn't be all of the story yet. If we fail a dependency |
231 | * due to a conflict, the current algorithm may leave packages marked |
232 | * as QPKG_ADDING, possibly triggering a false cyclic dependency error. |
233 | * See test/bug-adding for an example. |
234 | * |
235 | * In the case of cycle detection, we could avoid all the hassle of |
236 | * maintaining this flag and just walk down the stack to see if we're |
237 | * already trying to add the package (the stack should be correct with |
238 | * the current algorithm), but we'll need this kind of accurate |
239 | * tracking of package state for ordering the dependencies and for |
240 | * "Provides" anyway. |
241 | */ |
242 | |
243 | #if 1 |
244 | while (next_deps) { |
245 | assert(top->pkg->flags & QPKG_ADDING); |
246 | top->pkg->flags &= ~QPKG_ADDING; |
247 | top = top->next; |
248 | next_deps = next_deps->next; |
249 | } |
250 | #endif |
251 | } |
252 | |
253 | |
254 | static struct list *installed_conflicts(void) |
255 | { |
256 | struct list *list = NULL, *new; |
257 | const struct jrb *n; |
258 | const struct pkg *pkg; |
259 | |
260 | for (n = jrb_first(packages->root); n != jrb_nil(packages->root); |
261 | n = jrb_next(n)) { |
262 | pkg = n->val; |
263 | if (!pkg) |
264 | continue; |
265 | if (!(pkg->flags & QPKG_INSTALLED)) |
266 | continue; |
267 | if (!pkg->conflicts) /* optimization */ |
268 | continue; |
269 | new = alloc_type(struct list); |
270 | new->refs = pkg->conflicts; |
271 | new->next = list; |
272 | list = new; |
273 | } |
274 | return list; |
275 | } |
276 | |
277 | |
278 | static void free_conflicts(struct list *conf) |
279 | { |
280 | struct list *next; |
281 | |
282 | while (conf) { |
283 | next = conf->next; |
284 | free(conf); |
285 | conf = next; |
286 | } |
287 | } |
288 | |
289 | |
290 | struct pkg **prereq(struct pkg *pkg) |
291 | { |
292 | struct stack stack = { |
293 | .pkg = pkg, |
294 | .next = NULL |
295 | }; |
296 | struct list conf = { |
297 | .refs = pkg->conflicts, |
298 | .next = installed_conflicts() |
299 | }; |
300 | |
301 | if (old_conflicts(pkg, &conf) || new_conflicts(pkg->conflicts)) { |
302 | fprintf(stderr, "%.*s conflicts with installed packages\n", |
303 | ID2PF(pkg->id)); |
304 | exit(1); |
305 | } |
306 | pkg->flags |= QPKG_ADDING; |
307 | resolve(NULL, pkg->depends, &stack, &conf); |
308 | pkg->flags &= ~QPKG_ADDING; |
309 | free(installs); |
310 | free_conflicts(conf.next); |
311 | return best; |
312 | } |
313 |
Branches:
master