Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit 4797aed31346dc4c7fe76919736b5251a51bdbd0 created 12 years 8 months ago. By Werner Almesberger, mm1rc3/: renamed to m1rc3/ | |
---|---|
1 | Open policy decisions |
2 | ===================== |
3 | |
4 | http://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 | |
114 | Still 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 | |
153 | Done |
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 |
Branches:
master