Root/qpkg/prereq.c

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
26struct list {
27    const struct ref *refs;
28    struct list *next;
29};
30
31struct stack {
32    struct pkg *pkg;
33    struct stack *next;
34};
35
36
37static struct pkg **best = NULL;
38static struct pkg **installs = NULL;
39static int n_best; /* undefined if best == NULL */
40static int n_install = 0;
41static int install_max = 0;
42
43
44/* ----- List of packages considered for installation ---------------------- */
45
46
47static 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
62static 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
78static 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
89static 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
115static 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
129static 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
147static 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
169static 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
254static 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
278static 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
290struct 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

Archive Download this file

Branches:
master



interactive