Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit ca5905ae5164aee98575fbf81032e7f4f7e98b6a created 12 years 8 months ago. By root, Merge branch 'master' of git@projects.qi-hardware.com:wernermisc | |
---|---|
1 | Open 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 | |
105 | Still 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 | |
141 | Done |
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 |
Branches:
master