]>
Commit | Line | Data |
---|---|---|
d04baaba JV |
1 | /* |
2 | * deps.c | |
23229097 | 3 | * |
326c6a8e | 4 | * Copyright (c) 2006-2012 Pacman Development Team <pacman-dev@archlinux.org> |
c72b4543 | 5 | * Copyright (c) 2002-2006 by Judd Vinet <jvinet@zeroflux.org> |
d37ad048 AG |
6 | * Copyright (c) 2005 by Aurelien Foret <orelien@chez.com> |
7 | * Copyright (c) 2005, 2006 by Miklos Vajna <vmiklos@frugalware.org> | |
23229097 | 8 | * |
d04baaba JV |
9 | * This program is free software; you can redistribute it and/or modify |
10 | * it under the terms of the GNU General Public License as published by | |
11 | * the Free Software Foundation; either version 2 of the License, or | |
12 | * (at your option) any later version. | |
13 | * | |
14 | * This program is distributed in the hope that it will be useful, | |
15 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
17 | * GNU General Public License for more details. | |
18 | * | |
19 | * You should have received a copy of the GNU General Public License | |
9781d0d6 | 20 | * along with this program. If not, see <http://www.gnu.org/licenses/>. |
d04baaba JV |
21 | */ |
22 | ||
23 | #include <stdlib.h> | |
24 | #include <stdio.h> | |
25 | #include <string.h> | |
869e81e1 DM |
26 | |
27 | /* libalpm */ | |
28 | #include "deps.h" | |
29 | #include "alpm_list.h" | |
d04baaba JV |
30 | #include "util.h" |
31 | #include "log.h" | |
92ab7c33 | 32 | #include "graph.h" |
d04baaba JV |
33 | #include "package.h" |
34 | #include "db.h" | |
90b9888d | 35 | #include "handle.h" |
991b3ff7 | 36 | #include "trans.h" |
90b9888d | 37 | |
9540dfc4 | 38 | void _alpm_dep_free(alpm_depend_t *dep) |
3e133524 DM |
39 | { |
40 | FREE(dep->name); | |
41 | FREE(dep->version); | |
00f29cbc | 42 | FREE(dep->desc); |
3e133524 DM |
43 | FREE(dep); |
44 | } | |
45 | ||
6d876f9b | 46 | static alpm_depmissing_t *depmiss_new(const char *target, alpm_depend_t *dep, |
e63366ae | 47 | const char *causingpkg) |
6dd2ecf4 | 48 | { |
6d876f9b | 49 | alpm_depmissing_t *miss; |
6dd2ecf4 | 50 | |
6d876f9b | 51 | MALLOC(miss, sizeof(alpm_depmissing_t), return NULL); |
6dd2ecf4 | 52 | |
e2aa9526 | 53 | STRDUP(miss->target, target, return NULL); |
3e133524 | 54 | miss->depend = _alpm_dep_dup(dep); |
e2aa9526 | 55 | STRDUP(miss->causingpkg, causingpkg, return NULL); |
6dd2ecf4 | 56 | |
0303b26b | 57 | return miss; |
6dd2ecf4 AF |
58 | } |
59 | ||
6d876f9b | 60 | void _alpm_depmiss_free(alpm_depmissing_t *miss) |
ccc1c731 | 61 | { |
3e133524 | 62 | _alpm_dep_free(miss->depend); |
ccc1c731 | 63 | FREE(miss->target); |
e63366ae | 64 | FREE(miss->causingpkg); |
ccc1c731 DM |
65 | FREE(miss); |
66 | } | |
67 | ||
3bc3999b | 68 | /* Does pkg1 depend on pkg2, ie. does pkg2 satisfy a dependency of pkg1? */ |
8a04bc25 | 69 | static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2) |
3bc3999b DM |
70 | { |
71 | alpm_list_t *i; | |
72 | for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) { | |
73 | if(_alpm_depcmp(pkg2, i->data)) { | |
3f269503 | 74 | return 1; |
3bc3999b DM |
75 | } |
76 | } | |
3f269503 | 77 | return 0; |
3bc3999b DM |
78 | } |
79 | ||
8a04bc25 | 80 | /* Convert a list of alpm_pkg_t * to a graph structure, |
c68d3cc3 CX |
81 | * with a edge for each dependency. |
82 | * Returns a list of vertices (one vertex = one package) | |
83 | * (used by alpm_sortbydeps) | |
84 | */ | |
92ab7c33 | 85 | static alpm_list_t *dep_graph_init(alpm_list_t *targets) |
c68d3cc3 | 86 | { |
f7199f36 | 87 | alpm_list_t *i, *j; |
c68d3cc3 CX |
88 | alpm_list_t *vertices = NULL; |
89 | /* We create the vertices */ | |
90 | for(i = targets; i; i = i->next) { | |
57b9b19b | 91 | alpm_graph_t *vertex = _alpm_graph_new(); |
c68d3cc3 CX |
92 | vertex->data = (void *)i->data; |
93 | vertices = alpm_list_add(vertices, vertex); | |
94 | } | |
95 | ||
96 | /* We compute the edges */ | |
97 | for(i = vertices; i; i = i->next) { | |
57b9b19b | 98 | alpm_graph_t *vertex_i = i->data; |
8a04bc25 | 99 | alpm_pkg_t *p_i = vertex_i->data; |
7d37d927 | 100 | /* TODO this should be somehow combined with alpm_checkdeps */ |
c68d3cc3 | 101 | for(j = vertices; j; j = j->next) { |
57b9b19b | 102 | alpm_graph_t *vertex_j = j->data; |
8a04bc25 | 103 | alpm_pkg_t *p_j = vertex_j->data; |
f7199f36 | 104 | if(_alpm_dep_edge(p_i, p_j)) { |
c68d3cc3 CX |
105 | vertex_i->children = |
106 | alpm_list_add(vertex_i->children, vertex_j); | |
107 | } | |
108 | } | |
109 | vertex_i->childptr = vertex_i->children; | |
110 | } | |
0303b26b | 111 | return vertices; |
c68d3cc3 CX |
112 | } |
113 | ||
d04baaba JV |
114 | /* Re-order a list of target packages with respect to their dependencies. |
115 | * | |
e7a22329 | 116 | * Example (reverse == 0): |
d04baaba JV |
117 | * A depends on C |
118 | * B depends on A | |
119 | * Target order is A,B,C,D | |
120 | * | |
121 | * Should be re-ordered to C,A,B,D | |
23229097 | 122 | * |
e7a22329 | 123 | * if reverse is > 0, the dependency order will be reversed. |
7c847fd7 | 124 | * |
61670172 | 125 | * This function returns the new alpm_list_t* target list. |
d04baaba | 126 | * |
23229097 | 127 | */ |
64c1cf79 | 128 | alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, |
52bffd24 | 129 | alpm_list_t *targets, int reverse) |
d04baaba | 130 | { |
61670172 | 131 | alpm_list_t *newtargs = NULL; |
544bcbe6 NG |
132 | alpm_list_t *vertices = NULL; |
133 | alpm_list_t *vptr; | |
57b9b19b | 134 | alpm_graph_t *vertex; |
d04baaba JV |
135 | |
136 | if(targets == NULL) { | |
0303b26b | 137 | return NULL; |
d04baaba JV |
138 | } |
139 | ||
ca43fdd9 | 140 | _alpm_log(handle, ALPM_LOG_DEBUG, "started sorting dependencies\n"); |
544bcbe6 | 141 | |
92ab7c33 | 142 | vertices = dep_graph_init(targets); |
0bc06918 | 143 | |
544bcbe6 NG |
144 | vptr = vertices; |
145 | vertex = vertices->data; | |
146 | while(vptr) { | |
147 | /* mark that we touched the vertex */ | |
148 | vertex->state = -1; | |
149 | int found = 0; | |
150 | while(vertex->childptr && !found) { | |
57b9b19b | 151 | alpm_graph_t *nextchild = vertex->childptr->data; |
d4d304cd | 152 | vertex->childptr = vertex->childptr->next; |
4af6c72d | 153 | if(nextchild->state == 0) { |
544bcbe6 NG |
154 | found = 1; |
155 | nextchild->parent = vertex; | |
156 | vertex = nextchild; | |
157 | } | |
158 | else if(nextchild->state == -1) { | |
8a04bc25 AM |
159 | alpm_pkg_t *vertexpkg = vertex->data; |
160 | alpm_pkg_t *childpkg = nextchild->data; | |
2f967640 | 161 | |
ca43fdd9 | 162 | _alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n")); |
e7a22329 | 163 | if(reverse) { |
a8a1b093 DM |
164 | _alpm_log(handle, ALPM_LOG_WARNING, |
165 | _("%s will be removed after its %s dependency\n"), | |
166 | vertexpkg->name, childpkg->name); | |
7cf28a75 | 167 | } else { |
a8a1b093 DM |
168 | _alpm_log(handle, ALPM_LOG_WARNING, |
169 | _("%s will be installed before its %s dependency\n"), | |
170 | vertexpkg->name, childpkg->name); | |
7cf28a75 | 171 | } |
544bcbe6 | 172 | } |
d04baaba | 173 | } |
544bcbe6 NG |
174 | if(!found) { |
175 | newtargs = alpm_list_add(newtargs, vertex->data); | |
176 | /* mark that we've left this vertex */ | |
177 | vertex->state = 1; | |
178 | vertex = vertex->parent; | |
179 | if(!vertex) { | |
180 | vptr = vptr->next; | |
181 | while(vptr) { | |
182 | vertex = vptr->data; | |
4af6c72d | 183 | if(vertex->state == 0) break; |
544bcbe6 | 184 | vptr = vptr->next; |
d04baaba | 185 | } |
d04baaba JV |
186 | } |
187 | } | |
d04baaba | 188 | } |
544bcbe6 | 189 | |
ca43fdd9 | 190 | _alpm_log(handle, ALPM_LOG_DEBUG, "sorting dependencies finished\n"); |
a5e4fec7 | 191 | |
e7a22329 CX |
192 | if(reverse) { |
193 | /* reverse the order */ | |
61670172 | 194 | alpm_list_t *tmptargs = alpm_list_reverse(newtargs); |
7c847fd7 | 195 | /* free the old one */ |
a57b2f23 | 196 | alpm_list_free(newtargs); |
a5e4fec7 | 197 | newtargs = tmptargs; |
7c847fd7 AF |
198 | } |
199 | ||
544bcbe6 | 200 | alpm_list_free_inner(vertices, _alpm_graph_free); |
01e92e9d | 201 | alpm_list_free(vertices); |
544bcbe6 | 202 | |
0303b26b | 203 | return newtargs; |
d04baaba JV |
204 | } |
205 | ||
64c1cf79 | 206 | static int no_dep_version(alpm_handle_t *handle) |
68701a98 | 207 | { |
ac239c54 DM |
208 | if(!handle->trans) { |
209 | return 0; | |
210 | } | |
211 | return (handle->trans->flags & ALPM_TRANS_FLAG_NODEPVERSION); | |
68701a98 DM |
212 | } |
213 | ||
9540dfc4 | 214 | static alpm_depend_t *filtered_depend(alpm_depend_t *dep, int nodepversion) |
68701a98 DM |
215 | { |
216 | if(nodepversion) { | |
9540dfc4 | 217 | alpm_depend_t *newdep = _alpm_dep_dup(dep); |
3f269503 | 218 | ASSERT(newdep, return dep); |
f818f570 | 219 | newdep->mod = ALPM_DEP_MOD_ANY; |
68701a98 DM |
220 | dep = newdep; |
221 | } | |
222 | return dep; | |
223 | } | |
224 | ||
9540dfc4 | 225 | static void release_filtered_depend(alpm_depend_t *dep, int nodepversion) |
68701a98 DM |
226 | { |
227 | if(nodepversion) { | |
228 | free(dep); | |
229 | } | |
230 | } | |
231 | ||
9540dfc4 | 232 | static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep) |
616b5967 NG |
233 | { |
234 | alpm_list_t *i; | |
235 | ||
5d291d05 | 236 | for(i = pkgs; i; i = i->next) { |
8a04bc25 | 237 | alpm_pkg_t *pkg = i->data; |
68701a98 | 238 | if(_alpm_depcmp(pkg, dep)) { |
0303b26b | 239 | return pkg; |
616b5967 NG |
240 | } |
241 | } | |
0303b26b | 242 | return NULL; |
616b5967 NG |
243 | } |
244 | ||
a03daad0 XC |
245 | /** Find a package satisfying a specified dependency. |
246 | * The dependency can include versions with depmod operators. | |
8a04bc25 | 247 | * @param pkgs an alpm_list_t* of alpm_pkg_t where the satisfier will be searched |
a03daad0 | 248 | * @param depstring package or provision name, versioned or not |
8a04bc25 | 249 | * @return a alpm_pkg_t* satisfying depstring |
a03daad0 | 250 | */ |
8a04bc25 | 251 | alpm_pkg_t SYMEXPORT *alpm_find_satisfier(alpm_list_t *pkgs, const char *depstring) |
a03daad0 | 252 | { |
9540dfc4 | 253 | alpm_depend_t *dep = _alpm_splitdep(depstring); |
e2aa9526 DM |
254 | if(!dep) { |
255 | return NULL; | |
256 | } | |
8a04bc25 | 257 | alpm_pkg_t *pkg = find_dep_satisfier(pkgs, dep); |
a03daad0 | 258 | _alpm_dep_free(dep); |
0303b26b | 259 | return pkg; |
a03daad0 XC |
260 | } |
261 | ||
f21c45c0 CX |
262 | /** Checks dependencies and returns missing ones in a list. |
263 | * Dependencies can include versions with depmod operators. | |
8b62d9bc | 264 | * @param handle the context handle |
07013562 | 265 | * @param pkglist the list of local packages |
7d37d927 NG |
266 | * @param remove an alpm_list_t* of packages to be removed |
267 | * @param upgrade an alpm_list_t* of packages to be upgraded (remove-then-upgrade) | |
8b62d9bc | 268 | * @param reversedeps handles the backward dependencies |
6d876f9b | 269 | * @return an alpm_list_t* of alpm_depmissing_t pointers. |
d04baaba | 270 | */ |
1f6afe6b | 271 | alpm_list_t SYMEXPORT *alpm_checkdeps(alpm_handle_t *handle, |
e533478e | 272 | alpm_list_t *pkglist, alpm_list_t *rem, alpm_list_t *upgrade, |
1f6afe6b | 273 | int reversedeps) |
d04baaba | 274 | { |
2ed6b482 | 275 | alpm_list_t *i, *j; |
f612e5ed | 276 | alpm_list_t *dblist = NULL, *modified = NULL; |
61670172 | 277 | alpm_list_t *baddeps = NULL; |
68701a98 | 278 | int nodepversion; |
d04baaba | 279 | |
ee015f08 DM |
280 | CHECK_HANDLE(handle, return NULL); |
281 | ||
07013562 | 282 | for(i = pkglist; i; i = i->next) { |
8a04bc25 | 283 | alpm_pkg_t *pkg = i->data; |
e533478e | 284 | if(_alpm_pkg_find(rem, pkg->name) || _alpm_pkg_find(upgrade, pkg->name)) { |
633dbeac NG |
285 | modified = alpm_list_add(modified, pkg); |
286 | } else { | |
287 | dblist = alpm_list_add(dblist, pkg); | |
288 | } | |
289 | } | |
2ed6b482 | 290 | |
24000b83 | 291 | nodepversion = no_dep_version(handle); |
68701a98 | 292 | |
7d37d927 NG |
293 | /* look for unsatisfied dependencies of the upgrade list */ |
294 | for(i = upgrade; i; i = i->next) { | |
8a04bc25 | 295 | alpm_pkg_t *tp = i->data; |
ca43fdd9 | 296 | _alpm_log(handle, ALPM_LOG_DEBUG, "checkdeps: package %s-%s\n", |
1f6afe6b | 297 | tp->name, tp->version); |
7d37d927 NG |
298 | |
299 | for(j = alpm_pkg_get_depends(tp); j; j = j->next) { | |
9540dfc4 | 300 | alpm_depend_t *depend = j->data; |
68701a98 | 301 | depend = filtered_depend(depend, nodepversion); |
7d37d927 | 302 | /* 1. we check the upgrade list */ |
7d37d927 | 303 | /* 2. we check database for untouched satisfying packages */ |
3bc3999b | 304 | if(!find_dep_satisfier(upgrade, depend) && |
1f6afe6b | 305 | !find_dep_satisfier(dblist, depend)) { |
2ed6b482 | 306 | /* Unsatisfied dependency in the upgrade list */ |
6d876f9b | 307 | alpm_depmissing_t *miss; |
4da70d80 | 308 | char *missdepstring = alpm_dep_compute_string(depend); |
ca43fdd9 | 309 | _alpm_log(handle, ALPM_LOG_DEBUG, "checkdeps: missing dependency '%s' for package '%s'\n", |
1f6afe6b | 310 | missdepstring, tp->name); |
7d37d927 | 311 | free(missdepstring); |
1f6afe6b | 312 | miss = depmiss_new(tp->name, depend, NULL); |
2ed6b482 | 313 | baddeps = alpm_list_add(baddeps, miss); |
7d37d927 | 314 | } |
68701a98 | 315 | release_filtered_depend(depend, nodepversion); |
7d37d927 NG |
316 | } |
317 | } | |
318 | ||
319 | if(reversedeps) { | |
320 | /* reversedeps handles the backwards dependencies, ie, | |
321 | * the packages listed in the requiredby field. */ | |
2ed6b482 | 322 | for(i = dblist; i; i = i->next) { |
8a04bc25 | 323 | alpm_pkg_t *lp = i->data; |
2ed6b482 | 324 | for(j = alpm_pkg_get_depends(lp); j; j = j->next) { |
9540dfc4 | 325 | alpm_depend_t *depend = j->data; |
68701a98 | 326 | depend = filtered_depend(depend, nodepversion); |
8a04bc25 | 327 | alpm_pkg_t *causingpkg = find_dep_satisfier(modified, depend); |
2ed6b482 NG |
328 | /* we won't break this depend, if it is already broken, we ignore it */ |
329 | /* 1. check upgrade list for satisfiers */ | |
330 | /* 2. check dblist for satisfiers */ | |
e63366ae | 331 | if(causingpkg && |
3bc3999b DM |
332 | !find_dep_satisfier(upgrade, depend) && |
333 | !find_dep_satisfier(dblist, depend)) { | |
6d876f9b | 334 | alpm_depmissing_t *miss; |
4da70d80 | 335 | char *missdepstring = alpm_dep_compute_string(depend); |
ca43fdd9 | 336 | _alpm_log(handle, ALPM_LOG_DEBUG, "checkdeps: transaction would break '%s' dependency of '%s'\n", |
1f6afe6b | 337 | missdepstring, lp->name); |
7d37d927 | 338 | free(missdepstring); |
1f6afe6b | 339 | miss = depmiss_new(lp->name, depend, causingpkg->name); |
2ed6b482 | 340 | baddeps = alpm_list_add(baddeps, miss); |
d04baaba | 341 | } |
68701a98 | 342 | release_filtered_depend(depend, nodepversion); |
d04baaba | 343 | } |
d04baaba JV |
344 | } |
345 | } | |
d4d304cd | 346 | |
633dbeac | 347 | alpm_list_free(modified); |
2ed6b482 | 348 | alpm_list_free(dblist); |
d04baaba | 349 | |
0303b26b | 350 | return baddeps; |
d04baaba JV |
351 | } |
352 | ||
0a80cf31 | 353 | static int dep_vercmp(const char *version1, alpm_depmod_t mod, |
240bdf59 CX |
354 | const char *version2) |
355 | { | |
356 | int equal = 0; | |
357 | ||
f818f570 | 358 | if(mod == ALPM_DEP_MOD_ANY) { |
240bdf59 CX |
359 | equal = 1; |
360 | } else { | |
a8ee1854 | 361 | int cmp = alpm_pkg_vercmp(version1, version2); |
240bdf59 | 362 | switch(mod) { |
f818f570 AM |
363 | case ALPM_DEP_MOD_EQ: equal = (cmp == 0); break; |
364 | case ALPM_DEP_MOD_GE: equal = (cmp >= 0); break; | |
365 | case ALPM_DEP_MOD_LE: equal = (cmp <= 0); break; | |
366 | case ALPM_DEP_MOD_LT: equal = (cmp < 0); break; | |
367 | case ALPM_DEP_MOD_GT: equal = (cmp > 0); break; | |
240bdf59 CX |
368 | default: equal = 1; break; |
369 | } | |
370 | } | |
0303b26b | 371 | return equal; |
240bdf59 CX |
372 | } |
373 | ||
d008a816 DM |
374 | int _alpm_depcmp_literal(alpm_pkg_t *pkg, alpm_depend_t *dep) |
375 | { | |
376 | if(pkg->name_hash != dep->name_hash | |
377 | || strcmp(pkg->name, dep->name) != 0) { | |
378 | /* skip more expensive checks */ | |
379 | return 0; | |
380 | } | |
381 | return dep_vercmp(pkg->version, dep->mod, dep->version); | |
382 | } | |
383 | ||
9540dfc4 | 384 | int _alpm_depcmp(alpm_pkg_t *pkg, alpm_depend_t *dep) |
20f73d62 | 385 | { |
84ebf823 | 386 | alpm_list_t *i; |
d008a816 | 387 | int satisfy = _alpm_depcmp_literal(pkg, dep); |
240bdf59 | 388 | |
d008a816 DM |
389 | if(satisfy) { |
390 | return satisfy; | |
34a78d93 | 391 | } |
240bdf59 | 392 | |
a628feee | 393 | /* check provisions, name and version if available */ |
84ebf823 | 394 | for(i = alpm_pkg_get_provides(pkg); i && !satisfy; i = i->next) { |
a628feee DM |
395 | alpm_depend_t *provision = i->data; |
396 | ||
397 | if(dep->mod == ALPM_DEP_MOD_ANY) { | |
398 | /* any version will satisfy the requirement */ | |
399 | satisfy = (provision->name_hash == dep->name_hash | |
400 | && strcmp(provision->name, dep->name) == 0); | |
3d4656c0 | 401 | } else if(provision->mod == ALPM_DEP_MOD_EQ) { |
a628feee DM |
402 | /* provision specifies a version, so try it out */ |
403 | satisfy = (provision->name_hash == dep->name_hash | |
404 | && strcmp(provision->name, dep->name) == 0 | |
405 | && dep_vercmp(provision->version, dep->mod, dep->version)); | |
20f73d62 DM |
406 | } |
407 | } | |
408 | ||
0303b26b | 409 | return satisfy; |
20f73d62 DM |
410 | } |
411 | ||
9540dfc4 | 412 | alpm_depend_t *_alpm_splitdep(const char *depstring) |
d04baaba | 413 | { |
9540dfc4 | 414 | alpm_depend_t *depend; |
00f29cbc | 415 | const char *ptr, *version, *desc; |
499e0973 | 416 | size_t deplen; |
d04baaba | 417 | |
e24c22e3 | 418 | if(depstring == NULL) { |
0303b26b | 419 | return NULL; |
e24c22e3 | 420 | } |
23229097 | 421 | |
69962184 | 422 | MALLOC(depend, sizeof(alpm_depend_t), return NULL); |
00f29cbc DM |
423 | |
424 | /* Note the extra space in ": " to avoid matching the epoch */ | |
425 | if((desc = strstr(depstring, ": ")) != NULL) { | |
426 | STRDUP(depend->desc, desc + 2, return NULL); | |
427 | deplen = desc - depstring; | |
428 | } else { | |
429 | /* no description- point desc at NULL at end of string for later use */ | |
430 | depend->desc = NULL; | |
431 | deplen = strlen(depstring); | |
432 | desc = depstring + deplen; | |
433 | } | |
d04baaba | 434 | |
e24c22e3 DM |
435 | /* Find a version comparator if one exists. If it does, set the type and |
436 | * increment the ptr accordingly so we can copy the right strings. */ | |
499e0973 DM |
437 | if((ptr = memchr(depstring, '<', deplen))) { |
438 | if(ptr[1] == '=') { | |
439 | depend->mod = ALPM_DEP_MOD_LE; | |
440 | version = ptr + 2; | |
441 | } else { | |
442 | depend->mod = ALPM_DEP_MOD_LT; | |
443 | version = ptr + 1; | |
444 | } | |
445 | } else if((ptr = memchr(depstring, '>', deplen))) { | |
446 | if(ptr[1] == '=') { | |
447 | depend->mod = ALPM_DEP_MOD_GE; | |
448 | version = ptr + 2; | |
449 | } else { | |
450 | depend->mod = ALPM_DEP_MOD_GT; | |
451 | version = ptr + 1; | |
452 | } | |
453 | } else if((ptr = memchr(depstring, '=', deplen))) { | |
735a197f | 454 | /* Note: we must do =,<,> checks after <=, >= checks */ |
f818f570 | 455 | depend->mod = ALPM_DEP_MOD_EQ; |
01c8f39a | 456 | version = ptr + 1; |
d04baaba | 457 | } else { |
00f29cbc DM |
458 | /* no version specified, set ptr to end of string and version to NULL */ |
459 | ptr = depstring + deplen; | |
f818f570 | 460 | depend->mod = ALPM_DEP_MOD_ANY; |
69962184 DM |
461 | depend->version = NULL; |
462 | version = NULL; | |
d04baaba | 463 | } |
d35e4894 | 464 | |
01c8f39a | 465 | /* copy the right parts to the right places */ |
00f29cbc | 466 | STRNDUP(depend->name, depstring, ptr - depstring, return NULL); |
735a197f | 467 | depend->name_hash = _alpm_hash_sdbm(depend->name); |
01c8f39a | 468 | if(version) { |
00f29cbc | 469 | STRNDUP(depend->version, version, desc - version, return NULL); |
01c8f39a | 470 | } |
d04baaba | 471 | |
0303b26b | 472 | return depend; |
d04baaba JV |
473 | } |
474 | ||
9540dfc4 | 475 | alpm_depend_t *_alpm_dep_dup(const alpm_depend_t *dep) |
3e133524 | 476 | { |
9540dfc4 AM |
477 | alpm_depend_t *newdep; |
478 | CALLOC(newdep, 1, sizeof(alpm_depend_t), return NULL); | |
3e133524 | 479 | |
e2aa9526 | 480 | STRDUP(newdep->name, dep->name, return NULL); |
e2aa9526 | 481 | STRDUP(newdep->version, dep->version, return NULL); |
00f29cbc DM |
482 | STRDUP(newdep->desc, dep->desc, return NULL); |
483 | newdep->name_hash = dep->name_hash; | |
3e133524 DM |
484 | newdep->mod = dep->mod; |
485 | ||
0303b26b | 486 | return newdep; |
3e133524 DM |
487 | } |
488 | ||
1c9f30b9 CX |
489 | /* These parameters are messy. We check if this package, given a list of |
490 | * targets and a db is safe to remove. We do NOT remove it if it is in the | |
491 | * target list, or if if the package was explictly installed and | |
492 | * include_explicit == 0 */ | |
1f6afe6b DM |
493 | static int can_remove_package(alpm_db_t *db, alpm_pkg_t *pkg, |
494 | alpm_list_t *targets, int include_explicit) | |
f62f3750 | 495 | { |
f7199f36 | 496 | alpm_list_t *i; |
f62f3750 | 497 | |
1f6afe6b | 498 | if(_alpm_pkg_find(targets, pkg->name)) { |
0303b26b | 499 | return 0; |
f62f3750 AG |
500 | } |
501 | ||
1c9f30b9 CX |
502 | if(!include_explicit) { |
503 | /* see if it was explicitly installed */ | |
eb39a948 | 504 | if(alpm_pkg_get_reason(pkg) == ALPM_PKG_REASON_EXPLICIT) { |
1f6afe6b DM |
505 | _alpm_log(db->handle, ALPM_LOG_DEBUG, |
506 | "excluding %s -- explicitly installed\n", pkg->name); | |
0303b26b | 507 | return 0; |
1c9f30b9 | 508 | } |
f62f3750 AG |
509 | } |
510 | ||
1c9f30b9 CX |
511 | /* TODO: checkdeps could be used here, it handles multiple providers |
512 | * better, but that also makes it slower. | |
513 | * Also this would require to first add the package to the targets list, | |
514 | * then call checkdeps with it, then remove the package from the targets list | |
515 | * if checkdeps detected it would break something */ | |
516 | ||
f62f3750 | 517 | /* see if other packages need it */ |
1fcc4967 | 518 | for(i = _alpm_db_get_pkgcache(db); i; i = i->next) { |
8a04bc25 | 519 | alpm_pkg_t *lpkg = i->data; |
f7199f36 | 520 | if(_alpm_dep_edge(lpkg, pkg) && !_alpm_pkg_find(targets, lpkg->name)) { |
0303b26b | 521 | return 0; |
f62f3750 AG |
522 | } |
523 | } | |
524 | ||
525 | /* it's ok to remove */ | |
0303b26b | 526 | return 1; |
f62f3750 AG |
527 | } |
528 | ||
1c9f30b9 CX |
529 | /** |
530 | * @brief Adds unneeded dependencies to an existing list of packages. | |
531 | * By unneeded, we mean dependencies that are only required by packages in the | |
532 | * target list, so they can be safely removed. | |
85b06f12 | 533 | * If the input list was topo sorted, the output list will be topo sorted too. |
1c9f30b9 CX |
534 | * |
535 | * @param db package database to do dependency tracing in | |
536 | * @param *targs pointer to a list of packages | |
537 | * @param include_explicit if 0, explicitly installed packages are not included | |
6d544984 | 538 | * @return 0 on success, -1 on errors |
d04baaba | 539 | */ |
6d544984 | 540 | int _alpm_recursedeps(alpm_db_t *db, alpm_list_t *targs, int include_explicit) |
d04baaba | 541 | { |
f7199f36 | 542 | alpm_list_t *i, *j; |
d04baaba | 543 | |
1c9f30b9 | 544 | if(db == NULL || targs == NULL) { |
6d544984 | 545 | return -1; |
d04baaba JV |
546 | } |
547 | ||
85b06f12 | 548 | for(i = targs; i; i = i->next) { |
8a04bc25 | 549 | alpm_pkg_t *pkg = i->data; |
1fcc4967 | 550 | for(j = _alpm_db_get_pkgcache(db); j; j = j->next) { |
8a04bc25 | 551 | alpm_pkg_t *deppkg = j->data; |
f7199f36 NG |
552 | if(_alpm_dep_edge(pkg, deppkg) |
553 | && can_remove_package(db, deppkg, targs, include_explicit)) { | |
6d544984 | 554 | alpm_pkg_t *copy; |
ca43fdd9 | 555 | _alpm_log(db->handle, ALPM_LOG_DEBUG, "adding '%s' to the targets\n", |
1f6afe6b | 556 | deppkg->name); |
f7199f36 | 557 | /* add it to the target list */ |
6d544984 DM |
558 | if(_alpm_pkg_dup(deppkg, ©)) { |
559 | return -1; | |
560 | } | |
561 | targs = alpm_list_add(targs, copy); | |
d04baaba JV |
562 | } |
563 | } | |
564 | } | |
6d544984 | 565 | return 0; |
d04baaba JV |
566 | } |
567 | ||
f57f8d33 BI |
568 | /** |
569 | * helper function for resolvedeps: search for dep satisfier in dbs | |
570 | * | |
8b62d9bc | 571 | * @param handle the context handle |
f57f8d33 BI |
572 | * @param dep is the dependency to search for |
573 | * @param dbs are the databases to search | |
574 | * @param excluding are the packages to exclude from the search | |
575 | * @param prompt if true, will cause an unresolvable dependency to issue an | |
576 | * interactive prompt asking whether the package should be removed from | |
577 | * the transaction or the transaction aborted; if false, simply returns | |
578 | * an error code without prompting | |
579 | * @return the resolved package | |
580 | **/ | |
9540dfc4 | 581 | static alpm_pkg_t *resolvedep(alpm_handle_t *handle, alpm_depend_t *dep, |
8b62d9bc | 582 | alpm_list_t *dbs, alpm_list_t *excluding, int prompt) |
72c0ab5c NG |
583 | { |
584 | alpm_list_t *i, *j; | |
77efd512 | 585 | int ignored = 0; |
4097c98c XC |
586 | |
587 | alpm_list_t *providers = NULL; | |
588 | int count; | |
589 | ||
72c0ab5c NG |
590 | /* 1. literals */ |
591 | for(i = dbs; i; i = i->next) { | |
8a04bc25 | 592 | alpm_pkg_t *pkg = _alpm_db_get_pkgfromcache(i->data, dep->name); |
6cfc4757 DM |
593 | if(pkg && _alpm_depcmp_literal(pkg, dep) |
594 | && !_alpm_pkg_find(excluding, pkg->name)) { | |
0074cadb | 595 | if(_alpm_pkg_should_ignore(handle, pkg)) { |
f57f8d33 | 596 | int install = 0; |
4af6c72d | 597 | if(prompt) { |
98fdfa19 | 598 | QUESTION(handle, ALPM_QUESTION_INSTALL_IGNOREPKG, pkg, |
f57f8d33 | 599 | NULL, NULL, &install); |
56fd24ec | 600 | } else { |
6cfc4757 DM |
601 | _alpm_log(handle, ALPM_LOG_WARNING, _("ignoring package %s-%s\n"), |
602 | pkg->name, pkg->version); | |
f57f8d33 | 603 | } |
72c0ab5c | 604 | if(!install) { |
77efd512 | 605 | ignored = 1; |
72c0ab5c NG |
606 | continue; |
607 | } | |
608 | } | |
0303b26b | 609 | return pkg; |
72c0ab5c NG |
610 | } |
611 | } | |
612 | /* 2. satisfiers (skip literals here) */ | |
613 | for(i = dbs; i; i = i->next) { | |
1fcc4967 | 614 | for(j = _alpm_db_get_pkgcache(i->data); j; j = j->next) { |
8a04bc25 | 615 | alpm_pkg_t *pkg = j->data; |
6cfc4757 DM |
616 | /* with hash != hash, we can even skip the strcmp() as we know they can't |
617 | * possibly be the same string */ | |
618 | if(pkg->name_hash != dep->name_hash && _alpm_depcmp(pkg, dep) | |
619 | && !_alpm_pkg_find(excluding, pkg->name)) { | |
0074cadb | 620 | if(_alpm_pkg_should_ignore(handle, pkg)) { |
f57f8d33 | 621 | int install = 0; |
4af6c72d | 622 | if(prompt) { |
98fdfa19 | 623 | QUESTION(handle, ALPM_QUESTION_INSTALL_IGNOREPKG, |
f57f8d33 | 624 | pkg, NULL, NULL, &install); |
56fd24ec | 625 | } else { |
6cfc4757 DM |
626 | _alpm_log(handle, ALPM_LOG_WARNING, _("ignoring package %s-%s\n"), |
627 | pkg->name, pkg->version); | |
f57f8d33 | 628 | } |
72c0ab5c | 629 | if(!install) { |
77efd512 | 630 | ignored = 1; |
72c0ab5c NG |
631 | continue; |
632 | } | |
633 | } | |
ca43fdd9 | 634 | _alpm_log(handle, ALPM_LOG_DEBUG, "provider found (%s provides %s)\n", |
4097c98c XC |
635 | pkg->name, dep->name); |
636 | providers = alpm_list_add(providers, pkg); | |
637 | /* keep looking for other providers in the all dbs */ | |
72c0ab5c NG |
638 | } |
639 | } | |
640 | } | |
4097c98c XC |
641 | |
642 | /* first check if one provider is already installed locally */ | |
643 | for(i = providers; i; i = i->next) { | |
8a04bc25 | 644 | alpm_pkg_t *pkg = i->data; |
9363e7dc | 645 | if(_alpm_db_get_pkgfromcache(handle->db_local, pkg->name)) { |
4097c98c | 646 | alpm_list_free(providers); |
0303b26b | 647 | return pkg; |
4097c98c XC |
648 | } |
649 | } | |
650 | count = alpm_list_count(providers); | |
4af6c72d | 651 | if(count >= 1) { |
4097c98c | 652 | /* default to first provider if there is no QUESTION callback */ |
e533478e | 653 | int idx = 0; |
4097c98c XC |
654 | if(count > 1) { |
655 | /* if there is more than one provider, we ask the user */ | |
98fdfa19 | 656 | QUESTION(handle, ALPM_QUESTION_SELECT_PROVIDER, |
e533478e | 657 | providers, dep, NULL, &idx); |
4097c98c | 658 | } |
e533478e DR |
659 | if(idx >= 0 && idx < count) { |
660 | alpm_list_t *nth = alpm_list_nth(providers, idx); | |
79cbce60 | 661 | alpm_pkg_t *pkg = nth->data; |
4097c98c | 662 | alpm_list_free(providers); |
0303b26b | 663 | return pkg; |
4097c98c XC |
664 | } |
665 | alpm_list_free(providers); | |
666 | providers = NULL; | |
667 | } | |
668 | ||
77efd512 | 669 | if(ignored) { /* resolvedeps will override these */ |
afc96f2a | 670 | handle->pm_errno = ALPM_ERR_PKG_IGNORED; |
77efd512 | 671 | } else { |
afc96f2a | 672 | handle->pm_errno = ALPM_ERR_PKG_NOT_FOUND; |
77efd512 | 673 | } |
0303b26b | 674 | return NULL; |
72c0ab5c NG |
675 | } |
676 | ||
5a9a570d DM |
677 | /** Find a package satisfying a specified dependency. |
678 | * First look for a literal, going through each db one by one. Then look for | |
679 | * providers. The first satisfier found is returned. | |
680 | * The dependency can include versions with depmod operators. | |
8b62d9bc | 681 | * @param handle the context handle |
939d5a95 | 682 | * @param dbs an alpm_list_t* of alpm_db_t where the satisfier will be searched |
5a9a570d | 683 | * @param depstring package or provision name, versioned or not |
8a04bc25 | 684 | * @return a alpm_pkg_t* satisfying depstring |
5a9a570d | 685 | */ |
8a04bc25 | 686 | alpm_pkg_t SYMEXPORT *alpm_find_dbs_satisfier(alpm_handle_t *handle, |
8b62d9bc | 687 | alpm_list_t *dbs, const char *depstring) |
5a9a570d | 688 | { |
9540dfc4 | 689 | alpm_depend_t *dep; |
8a04bc25 | 690 | alpm_pkg_t *pkg; |
5a9a570d | 691 | |
ee015f08 | 692 | CHECK_HANDLE(handle, return NULL); |
afc96f2a | 693 | ASSERT(dbs, RET_ERR(handle, ALPM_ERR_WRONG_ARGS, NULL)); |
5a9a570d DM |
694 | |
695 | dep = _alpm_splitdep(depstring); | |
3f269503 | 696 | ASSERT(dep, return NULL); |
8b62d9bc | 697 | pkg = resolvedep(handle, dep, dbs, NULL, 1); |
5a9a570d | 698 | _alpm_dep_free(dep); |
3f269503 | 699 | return pkg; |
5a9a570d DM |
700 | } |
701 | ||
702 | /** | |
703 | * Computes resolvable dependencies for a given package and adds that package | |
6c4d702c | 704 | * and those resolvable dependencies to a list. |
d04baaba | 705 | * |
8b62d9bc | 706 | * @param handle the context handle |
eada558e | 707 | * @param localpkgs is the list of local packages |
6c4d702c | 708 | * @param pkg is the package to resolve |
2517ba33 | 709 | * @param preferred packages to prefer when resolving |
6c4d702c BI |
710 | * @param packages is a pointer to a list of packages which will be |
711 | * searched first for any dependency packages needed to complete the | |
712 | * resolve, and to which will be added any [pkg] and all of its | |
713 | * dependencies not already on the list | |
714 | * @param remove is the set of packages which will be removed in this | |
715 | * transaction | |
716 | * @param data returns the dependency which could not be satisfied in the | |
717 | * event of an error | |
718 | * @return 0 on success, with [pkg] and all of its dependencies not already on | |
719 | * the [*packages] list added to that list, or -1 on failure due to an | |
720 | * unresolvable dependency, in which case the [*packages] list will be | |
721 | * unmodified by this function | |
d04baaba | 722 | */ |
1f6afe6b DM |
723 | int _alpm_resolvedeps(alpm_handle_t *handle, alpm_list_t *localpkgs, |
724 | alpm_pkg_t *pkg, alpm_list_t *preferred, alpm_list_t **packages, | |
e533478e | 725 | alpm_list_t *rem, alpm_list_t **data) |
d04baaba | 726 | { |
2f967640 | 727 | int ret = 0; |
72c0ab5c | 728 | alpm_list_t *i, *j; |
61670172 AG |
729 | alpm_list_t *targ; |
730 | alpm_list_t *deps = NULL; | |
6c4d702c | 731 | alpm_list_t *packages_copy; |
d04baaba | 732 | |
6c4d702c | 733 | if(_alpm_pkg_find(*packages, pkg->name) != NULL) { |
0303b26b | 734 | return 0; |
6c4d702c BI |
735 | } |
736 | ||
737 | /* Create a copy of the packages list, so that it can be restored | |
738 | on error */ | |
739 | packages_copy = alpm_list_copy(*packages); | |
740 | /* [pkg] has not already been resolved into the packages list, so put it | |
741 | on that list */ | |
742 | *packages = alpm_list_add(*packages, pkg); | |
743 | ||
ca43fdd9 | 744 | _alpm_log(handle, ALPM_LOG_DEBUG, "started resolving dependencies\n"); |
6c4d702c | 745 | for(i = alpm_list_last(*packages); i; i = i->next) { |
8a04bc25 | 746 | alpm_pkg_t *tpkg = i->data; |
72c0ab5c | 747 | targ = alpm_list_add(NULL, tpkg); |
e533478e | 748 | deps = alpm_checkdeps(handle, localpkgs, rem, targ, 0); |
72c0ab5c | 749 | alpm_list_free(targ); |
d4d304cd | 750 | |
72c0ab5c | 751 | for(j = deps; j; j = j->next) { |
6d876f9b | 752 | alpm_depmissing_t *miss = j->data; |
9540dfc4 | 753 | alpm_depend_t *missdep = miss->depend; |
d4d304cd DM |
754 | /* check if one of the packages in the [*packages] list already satisfies |
755 | * this dependency */ | |
3bc3999b | 756 | if(find_dep_satisfier(*packages, missdep)) { |
2f967640 | 757 | _alpm_depmiss_free(miss); |
55a74551 NG |
758 | continue; |
759 | } | |
d4d304cd DM |
760 | /* check if one of the packages in the [preferred] list already satisfies |
761 | * this dependency */ | |
8a04bc25 | 762 | alpm_pkg_t *spkg = find_dep_satisfier(preferred, missdep); |
db3e1665 BI |
763 | if(!spkg) { |
764 | /* find a satisfier package in the given repositories */ | |
8b62d9bc | 765 | spkg = resolvedep(handle, missdep, handle->dbs_sync, *packages, 0); |
db3e1665 | 766 | } |
72c0ab5c | 767 | if(!spkg) { |
afc96f2a | 768 | handle->pm_errno = ALPM_ERR_UNSATISFIED_DEPS; |
4da70d80 | 769 | char *missdepstring = alpm_dep_compute_string(missdep); |
ca43fdd9 | 770 | _alpm_log(handle, ALPM_LOG_WARNING, |
2f967640 | 771 | _("cannot resolve \"%s\", a dependency of \"%s\"\n"), |
db3e1665 | 772 | missdepstring, tpkg->name); |
72c0ab5c NG |
773 | free(missdepstring); |
774 | if(data) { | |
2f967640 | 775 | *data = alpm_list_add(*data, miss); |
fc8be933 | 776 | } |
2f967640 | 777 | ret = -1; |
77efd512 | 778 | } else { |
1f6afe6b DM |
779 | _alpm_log(handle, ALPM_LOG_DEBUG, |
780 | "pulling dependency %s (needed by %s)\n", | |
781 | spkg->name, tpkg->name); | |
6c4d702c | 782 | *packages = alpm_list_add(*packages, spkg); |
2f967640 | 783 | _alpm_depmiss_free(miss); |
d04baaba | 784 | } |
d04baaba | 785 | } |
72c0ab5c | 786 | alpm_list_free(deps); |
d04baaba | 787 | } |
2f967640 DM |
788 | |
789 | if(ret != 0) { | |
790 | alpm_list_free(*packages); | |
791 | *packages = packages_copy; | |
792 | } else { | |
793 | alpm_list_free(packages_copy); | |
794 | } | |
ca43fdd9 | 795 | _alpm_log(handle, ALPM_LOG_DEBUG, "finished resolving dependencies\n"); |
0303b26b | 796 | return ret; |
d04baaba JV |
797 | } |
798 | ||
9540dfc4 | 799 | /** Reverse of splitdep; make a dep string from a alpm_depend_t struct. |
1b2817f5 DM |
800 | * The string must be freed! |
801 | * @param dep the depend to turn into a string | |
802 | * @return a string-formatted dependency with operator if necessary | |
803 | */ | |
9540dfc4 | 804 | char SYMEXPORT *alpm_dep_compute_string(const alpm_depend_t *dep) |
0cff7c6b | 805 | { |
00f29cbc | 806 | const char *name, *opr, *ver, *desc_delim, *desc; |
7f480ccc | 807 | char *str; |
1b2817f5 DM |
808 | size_t len; |
809 | ||
0303b26b | 810 | ASSERT(dep != NULL, return NULL); |
0cff7c6b | 811 | |
ccc1c731 DM |
812 | if(dep->name) { |
813 | name = dep->name; | |
814 | } else { | |
815 | name = ""; | |
816 | } | |
817 | ||
0cff7c6b | 818 | switch(dep->mod) { |
f818f570 | 819 | case ALPM_DEP_MOD_ANY: |
1b2817f5 | 820 | opr = ""; |
0cff7c6b | 821 | break; |
f818f570 | 822 | case ALPM_DEP_MOD_GE: |
1b2817f5 | 823 | opr = ">="; |
0cff7c6b | 824 | break; |
f818f570 | 825 | case ALPM_DEP_MOD_LE: |
1b2817f5 DM |
826 | opr = "<="; |
827 | break; | |
f818f570 | 828 | case ALPM_DEP_MOD_EQ: |
1b2817f5 DM |
829 | opr = "="; |
830 | break; | |
f818f570 | 831 | case ALPM_DEP_MOD_LT: |
13dd2864 NG |
832 | opr = "<"; |
833 | break; | |
f818f570 | 834 | case ALPM_DEP_MOD_GT: |
13dd2864 NG |
835 | opr = ">"; |
836 | break; | |
1b2817f5 DM |
837 | default: |
838 | opr = ""; | |
0cff7c6b NG |
839 | break; |
840 | } | |
841 | ||
f818f570 | 842 | if(dep->mod != ALPM_DEP_MOD_ANY && dep->version) { |
ccc1c731 DM |
843 | ver = dep->version; |
844 | } else { | |
845 | ver = ""; | |
846 | } | |
847 | ||
00f29cbc DM |
848 | if(dep->desc) { |
849 | desc_delim = ": "; | |
850 | desc = dep->desc; | |
851 | } else { | |
852 | desc_delim = ""; | |
853 | desc = ""; | |
854 | } | |
855 | ||
1b2817f5 | 856 | /* we can always compute len and print the string like this because opr |
f818f570 | 857 | * and ver will be empty when ALPM_DEP_MOD_ANY is the depend type. the |
ccc1c731 | 858 | * reassignments above also ensure we do not do a strlen(NULL). */ |
00f29cbc DM |
859 | len = strlen(name) + strlen(opr) + strlen(ver) |
860 | + strlen(desc_delim) + strlen(desc) + 1; | |
e2aa9526 | 861 | MALLOC(str, len, return NULL); |
00f29cbc | 862 | snprintf(str, len, "%s%s%s%s%s", name, opr, ver, desc_delim, desc); |
1b2817f5 | 863 | |
0303b26b | 864 | return str; |
0cff7c6b | 865 | } |
d04baaba | 866 | /* vim: set ts=2 sw=2 noet: */ |