Root/qpkg/prereq.c

Source at commit 0bc4b6046baa19f393ea3ebd6064178a080cfe35 created 8 years 8 months 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
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;
42static int debug = 0;
43
44
45static 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
61static 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
103static 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
118static 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
134static void backtrack(void)
135{
136    assert(n_install);
137    n_install--;
138    installs[n_install]->mark = 0;
139}
140
141
142static 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
167static int conflicts(const struct pkg *pkg, const struct list *conf)
168{
169    /* @@@ */
170    return 0;
171}
172
173
174static 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
261struct 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

Archive Download this file

Branches:
master



interactive