Date:2010-11-22 00:31:20 (13 years 4 months ago)
Author:Werner Almesberger
Commit:0bc4b6046baa19f393ea3ebd6064178a080cfe35
Message:qpkg: added detection of cyclic dependencies

We define a cyclic dependency as the possibility (!) of the prerequisites
of a package X including a package that depends on X, and issue an error
if encountering such a situation.

Note that, if the dependencies of X can be resolved in a manner that does
not include the cyclic dependency, qpkg will still fail if it encounters
the cycle. Also note that qpkg (at least so far) does no perform an
exhaustive search to ferret out cyclic dependencies.

Furthermore, we don't consider that a cyclic dependency may not necessarily
imply a real life problem. E.g., if a package A contains elements X and
Y, with X needing package B, and the content of package B has a run-time
dependency on Y, the cyclic dependency between A and B would not exist
when considering its constituents. Since we don't have this information, we
just err on the side of caution.

- qpkg.h (enum flags): divide flags into categories (parse-time and
run-time) and add flag QPKG_ADDING to mark packets whose dependencies we
are processing
- prereq.c (resolve, prereq): track which packages we're tentatively
considering for installation and detect cyclic dependencies
- test/cyclic: regression test for detection of cyclic dependencies
- TODO: updated with recent changes
Files: qpkg/TODO (2 diffs)
qpkg/prereq.c (7 diffs)
qpkg/qpkg.h (1 diff)
qpkg/test/cyclic (1 diff)

Change Details

qpkg/TODO
1313
1414- consider Architecture:
1515
16  Update: we parse and record it now but don't use it yet.
17
1618- what to do with explicit and implicit replacement ?
1719
1820- if we can't resolve the prerequisites, give at least a hint of what one
...... 
2022
2123- check database for internal consistency
2224
25  Update: added detection of cyclic dependencies (in progress)
26
2327- implement keyword search
2428
2529- consider also supporting the similar but not identical (parent ?) format
qpkg/prereq.c
2828    struct list *next;
2929};
3030
31struct stack {
32    struct pkg *pkg;
33    struct stack *next;
34};
35
3136
3237static struct pkg **best = NULL;
3338static struct pkg **installs = NULL;
...... 
119124            perror("realloc");
120125            exit(1);
121126        }
122
123127    }
124128    installs[n_install++] = pkg;
125129    assert(!pkg->mark && !(pkg->flags & QPKG_INSTALLED));
...... 
168172
169173
170174static void resolve(struct list *next_dep, const struct ref *dep,
171    struct list *conf)
175    struct stack *top, struct list *conf)
172176{
173177    static int level = 0;
174178    struct list more_deps;
175179    struct list more_conf = {
176180        .next = conf
177181    };
182    struct stack stack;
178183    struct pkg *pkg;
179184
180185    while (!dep) {
...... 
182187            done();
183188            return;
184189        }
190        assert(top->pkg->flags & QPKG_ADDING);
191        top->pkg->flags &= ~QPKG_ADDING;
192        top = top->next;
185193        dep = next_dep->refs;
186194        next_dep = next_dep->next;
187195    }
...... 
189197        if (best && n_install == n_best)
190198            return;
191199        if (debug) {
200            struct stack *p;
201
192202            fprintf(stderr, "%*s", level, "");
193203            fprintf(stderr, "%.*s %p", ID2PF(pkg->id), pkg);
194204            if (pkg->version)
195205                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, ")");
196211            if (pkg->mark)
197212                fprintf(stderr, " +");
198213            if (pkg->flags & QPKG_INSTALLED)
...... 
201216        }
202217        if (!satisfies(pkg, dep))
203218            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        }
204225        if ((pkg->flags & QPKG_INSTALLED) || pkg->mark) {
205226            assert(!conflicts(pkg, conf));
206            resolve(next_dep, dep->next, conf);
227            resolve(next_dep, dep->next, top, conf);
207228            continue;
208229        }
209230        if (conflicts(pkg, conf))
...... 
214235        more_deps.next = next_dep;
215236        more_conf.refs = pkg->conflicts;
216237        more_conf.next = conf;
217        resolve(&more_deps, pkg->depends, &more_conf);
238        stack.pkg = pkg;
239        stack.next = top;
240        pkg->flags |= QPKG_ADDING;
241        resolve(&more_deps, pkg->depends, &stack, &more_conf);
218242        backtrack();
219243        level--;
220244    }
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     */
221258}
222259
223260
224261struct pkg **prereq(struct pkg *pkg)
225262{
263    struct stack stack = {
264        .pkg = pkg,
265        .next = NULL
266    };
226267    /* @@@ make list of pre-existing conflicts */
227    resolve(NULL, pkg->depends, NULL);
268    pkg->flags |= QPKG_ADDING;
269    resolve(NULL, pkg->depends, &stack, NULL);
270    pkg->flags &= ~QPKG_ADDING;
228271    free(installs);
229272    return best;
230273}
qpkg/qpkg.h
1414#define QPKG_H
1515
1616enum flags {
17    /* parse-time flags */
1718    QPKG_INSTALLED = 1 << 0, /* installed on target */
19
20    /* run-time flags */
21    QPKG_ADDING = 1 << 10, /* resolving dependencies */
1822};
1923
2024enum relop {
qpkg/test/cyclic
1#!/bin/sh
2. ./Common
3
4###############################################################################
5
6qpkg_fail "cyclic dependency (one step)" prereq foo <<EOF
7Package: foo
8Version: 0
9Architecture: test
10Depends: foo
11Filename: foo_0_test.ipkg
12EOF
13expect <<EOF
14package foo version 0 has cyclic dependency
15EOF
16
17###############################################################################
18
19qpkg_fail "cyclic dependency (two steps)" prereq foo <<EOF
20Package: bar
21Version: 1
22Architecture: test
23Depends: foo
24Filename: bar_1_test.ipkg
25
26Package: foo
27Version: 0
28Architecture: test
29Depends: bar
30Filename: foo_0_test.ipkg
31EOF
32expect <<EOF
33package foo version 0 has cyclic dependency
34EOF

Archive Download the corresponding diff file

Branches:
master



interactive