Root/qpkg/TODO

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

Archive Download this file

Branches:
master



interactive