Root/qpkg/prereq.c

Source at commit efacc76bace28fb955a0dd7f8638b8f0ad69253a created 9 years 3 months ago.
By root, fisl2011/: corrected flow.fig; straightened narrative
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
244
245static struct list *installed_conflicts(void)
246{
247    struct list *list = NULL, *new;
248    const struct jrb *n;
249    const struct pkg *pkg;
250    
251    for (n = jrb_first(packages->root); n != jrb_nil(packages->root);
252        n = jrb_next(n)) {
253        pkg = n->val;
254        if (!pkg)
255            continue;
256        if (!(pkg->flags & QPKG_INSTALLED))
257            continue;
258        if (!pkg->conflicts) /* optimization */
259            continue;
260        new = alloc_type(struct list);
261        new->refs = pkg->conflicts;
262        new->next = list;
263        list = new;
264    }
265    return list;
266}
267
268
269static void free_conflicts(struct list *conf)
270{
271    struct list *next;
272
273    while (conf) {
274        next = conf->next;
275        free(conf);
276        conf = next;
277    }
278}
279
280
281struct pkg **prereq(struct pkg *pkg)
282{
283    struct stack stack = {
284        .pkg = pkg,
285        .next = NULL
286    };
287    struct list conf = {
288        .refs = pkg->conflicts,
289        .next = installed_conflicts()
290    };
291
292    if (old_conflicts(pkg, &conf) || new_conflicts(pkg->conflicts)) {
293        fprintf(stderr, "%.*s conflicts with installed packages\n",
294          ID2PF(pkg->id));
295        exit(1);
296    }
297    pkg->flags |= QPKG_ADDING;
298    resolve(NULL, pkg->depends, &stack, &conf);
299    pkg->flags &= ~QPKG_ADDING;
300    free(installs);
301    free_conflicts(conf.next);
302    return best;
303}
304

Archive Download this file

Branches:
master



interactive