Root/qpkg/TODO

1Open policy decisions
2=====================
3
4http://www.debian.org/doc/debian-policy/ch-controlfields.html#s5.6.10
5
6- what to do about cyclic dependencies ?
7
8  Update: addressed in
9  http://www.debian.org/doc/debian-policy/ch-relationships.html#s-binarydeps
10
11  A cyclic dependency can be bad new or something perfectly normal,
12  depending on how we define the semantics of package A depending on
13  package B, and what policy we adopt with respect to the existence of
14  cyclic dependencies:
15
16  1) "B must be installed before A"
17
18     In this case, a cyclic dependency means that the package in
19     question cannot be installed using the respective sequence of
20     installations.
21
22     However, this does not mean that no other sequence can exist in which
23     the package could be installed.
24
25     Example:
26
27     A depends on B. There are two versions of B: B_0 depends on nothing
28     else while B_1 depends on A.
29
30     If we try to resolve A's dependency with B_1, we enter a circular
31     dependency and fail. If we use B_0 instead, there is no problem.
32
33     This means that there are (at least) the following three possible
34     policies:
35
36     1A) Cyclic dependencies are tolerated and just mean that the package
37         in question may not be installable (for whatever reason).
38
39     1B) A cyclic dependency is always considered an error.
40
41     1C) Cyclic dependencies are tolerated as long as there is a way around
42         them, as in the example above.
43
44  2) "B must be installed with A"
45
46     In this case, the cyclic dependency would not be a problem as long as
47     all the packages in the cycle are installed together.
48
49     Should an installation get interrupted and cause only part of the
50     packages to get installed, the system would then be in an anomalous
51     configuration.
52
53     If cyclic dependencies are to be interpreted this way, they are not a
54     problem per se. Policy may still discourage their use, though.
55
56- what to do if we need something that's "provided" ?
57
58  Update: "Provides" is described here, but without answering the above
59  question:
60  http://www.debian.org/doc/debian-policy/ch-relationships.html#s-virtual
61
62  When determining prerequisites, we may encounter a dependency on an item
63  that only appears in the Provides: field of a package but is not an
64  installable package itself.
65
66  Should we
67
68  1) consider installing the package that provides the requested item, or
69 
70  2) ignore the package, leaving it to the user to choose what to do.
71
72  3) if there's only one choice do 1) else do 2).
73
74  ?
75
76  Policy 1 would make sense if this is merely an alias or if a package
77  enumerates its constituents, which at some point in time - in the past
78  or in the future - are separate packages.
79
80  Example:
81
82  - package "dwarf-pluto" could provide "planet-pluto", for packages that
83    haven't been updated yet,
84
85  - "binutils" could provide "as", "ld", etc., to allow packages that only
86    need specific parts to depend on them (with the option of breaking
87    binutils into its constituents in the future),
88
89  - similarly, if "as", "ld", etc., where individual packages in the past
90    but are now combined into "binutils", "binutils" could still provide
91    its constituents for compatibility with packages whose dependencies
92    have not been updated yet.
93  
94  Policy 2 would seem more appropriate in the common case of multiple
95  choices.
96
97
98  Example:
99
100  - packages "emacs" and "vim" could both provide "editor", leaving the
101    choice to the user.
102
103  - similarly, message packages "foo-en", "foo-zh", etc., could both
104    provide "foo-messages".
105
106  In the above example, "Provides" could also be use to prioritize choices,
107  e.g., if "foo-en" provides "lang-en" and "foo-zh" provides "lang-zh",
108  future installations could prefer prerequisites that introduce fewer new
109  items. So a package "bar-en" providing "bar-messages" and "lang-en" would
110  be chosen over "bar-zh" providing "bar-messages" and "lang-zh" if we have
111  already installed "foo-en" but not "foo-zh" (or vice versa).
112
113
114Still left to do
115================
116
117- make comp_versions work according to
118  http://www.debian.org/doc/debian-policy/ch-controlfields.html#s-f-Version
119
120- consider reducing the size of the lists of conflicts, e.g., by making
121  them unique via a red-black tree
122
123- handle Provides:
124
125  Update: Provides data is now parsed and properly integrated in the
126  package database, but not yet used to resolve prerequisites.
127
128- sort prerequisites such that they can be installed in the specified order
129
130- consider Architecture:
131
132  Update: we parse and record it now but don't use it yet.
133
134- what to do with explicit and implicit replacement ?
135
136- if we can't resolve the prerequisites, give at least a hint of what one
137  can do to improve the situation
138
139- check database for internal consistency
140
141  Update: added detection of cyclic dependencies (in progress)
142
143  Update: added test for QPKG_ADDING cleanup bug
144
145- implement keyword search
146
147- consider also supporting the similar but not identical (parent ?) format
148  of /var/lib/dpkg/status and /var/lib/apt/lists/*Packages
149
150  Update: added as much as my Ubuntu system can reach before hitting |
151
152
153Done
154====
155
156- optimize the search trees. Right now, we have 81812 calls to make_id
157  for 14601 packages, resulting in 7420560 calls to comp_id.
158
159  There can be at most 2 new identifiers per package (package name and
160  version), so a perfectly balanced tree should have a depth of no more
161  than 14. If we assume that each call to make_id searches to the bottom,
162  we'd get 1145368 calls to comp_id, about 15% of the current number.
163
164  So the tree is clearly degenerated.
165
166  Update: after switching to red-black trees, we get only 1497604 calls
167  to comp_id. This is 130% of the "good case" estimate above. Insertion
168  of a new node is currently done with two lookups, so we'll get rid of
169  some more lookups after further optimization.
170
171  Update: after merging the two lookups per new node into one, we're at
172  1172642 calls to comp_id, or 102% of the predicted "good case".
173
174- if there are multiple choices, try to prefer more recent versions
175
176- check whether introducing a new package would cause a conflict
177
178  Update: conflicts among the packages considered for installation are now
179  checked.
180
181- compile the list of conflicts of installed packages
182

Archive Download this file

Branches:
master



interactive