]>
Commit | Line | Data |
---|---|---|
d04baaba JV |
1 | /* |
2 | * deps.c | |
23229097 | 3 | * |
d2882404 | 4 | * Copyright (c) 2006-2011 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 | ||
869e81e1 DM |
23 | #include "config.h" |
24 | ||
d04baaba JV |
25 | #include <stdlib.h> |
26 | #include <stdio.h> | |
27 | #include <string.h> | |
869e81e1 DM |
28 | |
29 | /* libalpm */ | |
30 | #include "deps.h" | |
31 | #include "alpm_list.h" | |
d04baaba JV |
32 | #include "util.h" |
33 | #include "log.h" | |
92ab7c33 | 34 | #include "graph.h" |
d04baaba JV |
35 | #include "package.h" |
36 | #include "db.h" | |
90b9888d AF |
37 | #include "handle.h" |
38 | ||
3e133524 DM |
39 | void _alpm_dep_free(pmdepend_t *dep) |
40 | { | |
41 | FREE(dep->name); | |
42 | FREE(dep->version); | |
43 | FREE(dep); | |
44 | } | |
45 | ||
e63366ae NG |
46 | pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdepend_t *dep, |
47 | const char *causingpkg) | |
6dd2ecf4 AF |
48 | { |
49 | pmdepmissing_t *miss; | |
50 | ||
da648bc2 AG |
51 | ALPM_LOG_FUNC; |
52 | ||
cc754bc6 | 53 | MALLOC(miss, sizeof(pmdepmissing_t), RET_ERR(PM_ERR_MEMORY, NULL)); |
6dd2ecf4 | 54 | |
ccc1c731 | 55 | STRDUP(miss->target, target, RET_ERR(PM_ERR_MEMORY, NULL)); |
3e133524 | 56 | miss->depend = _alpm_dep_dup(dep); |
e63366ae | 57 | STRDUP(miss->causingpkg, causingpkg, RET_ERR(PM_ERR_MEMORY, NULL)); |
6dd2ecf4 AF |
58 | |
59 | return(miss); | |
60 | } | |
61 | ||
ccc1c731 DM |
62 | void _alpm_depmiss_free(pmdepmissing_t *miss) |
63 | { | |
3e133524 | 64 | _alpm_dep_free(miss->depend); |
ccc1c731 | 65 | FREE(miss->target); |
e63366ae | 66 | FREE(miss->causingpkg); |
ccc1c731 DM |
67 | FREE(miss); |
68 | } | |
69 | ||
c68d3cc3 CX |
70 | /* Convert a list of pmpkg_t * to a graph structure, |
71 | * with a edge for each dependency. | |
72 | * Returns a list of vertices (one vertex = one package) | |
73 | * (used by alpm_sortbydeps) | |
74 | */ | |
92ab7c33 | 75 | static alpm_list_t *dep_graph_init(alpm_list_t *targets) |
c68d3cc3 | 76 | { |
f7199f36 | 77 | alpm_list_t *i, *j; |
c68d3cc3 CX |
78 | alpm_list_t *vertices = NULL; |
79 | /* We create the vertices */ | |
80 | for(i = targets; i; i = i->next) { | |
81 | pmgraph_t *vertex = _alpm_graph_new(); | |
82 | vertex->data = (void *)i->data; | |
83 | vertices = alpm_list_add(vertices, vertex); | |
84 | } | |
85 | ||
86 | /* We compute the edges */ | |
87 | for(i = vertices; i; i = i->next) { | |
88 | pmgraph_t *vertex_i = i->data; | |
89 | pmpkg_t *p_i = vertex_i->data; | |
7d37d927 | 90 | /* TODO this should be somehow combined with alpm_checkdeps */ |
c68d3cc3 CX |
91 | for(j = vertices; j; j = j->next) { |
92 | pmgraph_t *vertex_j = j->data; | |
93 | pmpkg_t *p_j = vertex_j->data; | |
f7199f36 | 94 | if(_alpm_dep_edge(p_i, p_j)) { |
c68d3cc3 CX |
95 | vertex_i->children = |
96 | alpm_list_add(vertex_i->children, vertex_j); | |
97 | } | |
98 | } | |
99 | vertex_i->childptr = vertex_i->children; | |
100 | } | |
101 | return(vertices); | |
102 | } | |
103 | ||
d04baaba JV |
104 | /* Re-order a list of target packages with respect to their dependencies. |
105 | * | |
e7a22329 | 106 | * Example (reverse == 0): |
d04baaba JV |
107 | * A depends on C |
108 | * B depends on A | |
109 | * Target order is A,B,C,D | |
110 | * | |
111 | * Should be re-ordered to C,A,B,D | |
23229097 | 112 | * |
e7a22329 | 113 | * if reverse is > 0, the dependency order will be reversed. |
7c847fd7 | 114 | * |
61670172 | 115 | * This function returns the new alpm_list_t* target list. |
d04baaba | 116 | * |
23229097 | 117 | */ |
e7a22329 | 118 | alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, int reverse) |
d04baaba | 119 | { |
61670172 | 120 | alpm_list_t *newtargs = NULL; |
544bcbe6 NG |
121 | alpm_list_t *vertices = NULL; |
122 | alpm_list_t *vptr; | |
123 | pmgraph_t *vertex; | |
d04baaba | 124 | |
da648bc2 AG |
125 | ALPM_LOG_FUNC; |
126 | ||
d04baaba JV |
127 | if(targets == NULL) { |
128 | return(NULL); | |
129 | } | |
130 | ||
5c9eec55 | 131 | _alpm_log(PM_LOG_DEBUG, "started sorting dependencies\n"); |
544bcbe6 | 132 | |
92ab7c33 | 133 | vertices = dep_graph_init(targets); |
0bc06918 | 134 | |
544bcbe6 NG |
135 | vptr = vertices; |
136 | vertex = vertices->data; | |
137 | while(vptr) { | |
138 | /* mark that we touched the vertex */ | |
139 | vertex->state = -1; | |
140 | int found = 0; | |
141 | while(vertex->childptr && !found) { | |
142 | pmgraph_t *nextchild = (vertex->childptr)->data; | |
143 | vertex->childptr = (vertex->childptr)->next; | |
144 | if (nextchild->state == 0) { | |
145 | found = 1; | |
146 | nextchild->parent = vertex; | |
147 | vertex = nextchild; | |
148 | } | |
149 | else if(nextchild->state == -1) { | |
7cf28a75 NG |
150 | pmpkg_t *vertexpkg = vertex->data; |
151 | pmpkg_t *childpkg = nextchild->data; | |
152 | _alpm_log(PM_LOG_WARNING, _("dependency cycle detected:\n")); | |
e7a22329 | 153 | if(reverse) { |
7cf28a75 NG |
154 | _alpm_log(PM_LOG_WARNING, _("%s will be removed after its %s dependency\n"), vertexpkg->name, childpkg->name); |
155 | } else { | |
156 | _alpm_log(PM_LOG_WARNING, _("%s will be installed before its %s dependency\n"), vertexpkg->name, childpkg->name); | |
157 | } | |
544bcbe6 | 158 | } |
d04baaba | 159 | } |
544bcbe6 NG |
160 | if(!found) { |
161 | newtargs = alpm_list_add(newtargs, vertex->data); | |
162 | /* mark that we've left this vertex */ | |
163 | vertex->state = 1; | |
164 | vertex = vertex->parent; | |
165 | if(!vertex) { | |
166 | vptr = vptr->next; | |
167 | while(vptr) { | |
168 | vertex = vptr->data; | |
169 | if (vertex->state == 0) break; | |
170 | vptr = vptr->next; | |
d04baaba | 171 | } |
d04baaba JV |
172 | } |
173 | } | |
d04baaba | 174 | } |
544bcbe6 | 175 | |
5c9eec55 | 176 | _alpm_log(PM_LOG_DEBUG, "sorting dependencies finished\n"); |
a5e4fec7 | 177 | |
e7a22329 CX |
178 | if(reverse) { |
179 | /* reverse the order */ | |
61670172 | 180 | alpm_list_t *tmptargs = alpm_list_reverse(newtargs); |
7c847fd7 | 181 | /* free the old one */ |
a57b2f23 | 182 | alpm_list_free(newtargs); |
a5e4fec7 | 183 | newtargs = tmptargs; |
7c847fd7 AF |
184 | } |
185 | ||
544bcbe6 | 186 | alpm_list_free_inner(vertices, _alpm_graph_free); |
01e92e9d | 187 | alpm_list_free(vertices); |
544bcbe6 | 188 | |
a5e4fec7 | 189 | return(newtargs); |
d04baaba JV |
190 | } |
191 | ||
616b5967 NG |
192 | pmpkg_t *_alpm_find_dep_satisfier(alpm_list_t *pkgs, pmdepend_t *dep) |
193 | { | |
194 | alpm_list_t *i; | |
195 | ||
196 | for(i = pkgs; i; i = alpm_list_next(i)) { | |
197 | pmpkg_t *pkg = i->data; | |
d0d8f605 | 198 | if(_alpm_depcmp(pkg, dep)) { |
616b5967 NG |
199 | return(pkg); |
200 | } | |
201 | } | |
202 | return(NULL); | |
203 | } | |
204 | ||
a03daad0 XC |
205 | /** Find a package satisfying a specified dependency. |
206 | * The dependency can include versions with depmod operators. | |
207 | * @param pkgs an alpm_list_t* of pmpkg_t where the satisfier will be searched | |
208 | * @param depstring package or provision name, versioned or not | |
209 | * @return a pmpkg_t* satisfying depstring | |
210 | */ | |
211 | pmpkg_t SYMEXPORT *alpm_find_satisfier(alpm_list_t *pkgs, const char *depstring) | |
212 | { | |
213 | pmdepend_t *dep = _alpm_splitdep(depstring); | |
214 | pmpkg_t *pkg = _alpm_find_dep_satisfier(pkgs, dep); | |
215 | _alpm_dep_free(dep); | |
216 | return(pkg); | |
217 | } | |
218 | ||
f21c45c0 CX |
219 | /** Checks dependencies and returns missing ones in a list. |
220 | * Dependencies can include versions with depmod operators. | |
07013562 | 221 | * @param pkglist the list of local packages |
7d37d927 NG |
222 | * @param reversedeps handles the backward dependencies |
223 | * @param remove an alpm_list_t* of packages to be removed | |
224 | * @param upgrade an alpm_list_t* of packages to be upgraded (remove-then-upgrade) | |
c0a7d9d8 | 225 | * @return an alpm_list_t* of pmpkg_t* of missing_t pointers. |
d04baaba | 226 | */ |
07013562 | 227 | alpm_list_t SYMEXPORT *alpm_checkdeps(alpm_list_t *pkglist, int reversedeps, |
7d37d927 | 228 | alpm_list_t *remove, alpm_list_t *upgrade) |
d04baaba | 229 | { |
2ed6b482 | 230 | alpm_list_t *i, *j; |
633dbeac | 231 | alpm_list_t *targets, *dblist = NULL, *modified = NULL; |
61670172 | 232 | alpm_list_t *baddeps = NULL; |
d04baaba JV |
233 | pmdepmissing_t *miss = NULL; |
234 | ||
da648bc2 AG |
235 | ALPM_LOG_FUNC; |
236 | ||
633dbeac | 237 | targets = alpm_list_join(alpm_list_copy(remove), alpm_list_copy(upgrade)); |
07013562 | 238 | for(i = pkglist; i; i = i->next) { |
d1d163c5 DM |
239 | pmpkg_t *pkg = i->data; |
240 | if(_alpm_pkg_find(targets, pkg->name)) { | |
633dbeac NG |
241 | modified = alpm_list_add(modified, pkg); |
242 | } else { | |
243 | dblist = alpm_list_add(dblist, pkg); | |
244 | } | |
245 | } | |
246 | alpm_list_free(targets); | |
2ed6b482 | 247 | |
7d37d927 NG |
248 | /* look for unsatisfied dependencies of the upgrade list */ |
249 | for(i = upgrade; i; i = i->next) { | |
250 | pmpkg_t *tp = i->data; | |
7d37d927 NG |
251 | _alpm_log(PM_LOG_DEBUG, "checkdeps: package %s-%s\n", |
252 | alpm_pkg_get_name(tp), alpm_pkg_get_version(tp)); | |
253 | ||
254 | for(j = alpm_pkg_get_depends(tp); j; j = j->next) { | |
7d37d927 | 255 | pmdepend_t *depend = j->data; |
7d37d927 | 256 | /* 1. we check the upgrade list */ |
7d37d927 | 257 | /* 2. we check database for untouched satisfying packages */ |
616b5967 NG |
258 | if(!_alpm_find_dep_satisfier(upgrade, depend) && |
259 | !_alpm_find_dep_satisfier(dblist, depend)) { | |
2ed6b482 | 260 | /* Unsatisfied dependency in the upgrade list */ |
4da70d80 | 261 | char *missdepstring = alpm_dep_compute_string(depend); |
e95e346a | 262 | _alpm_log(PM_LOG_DEBUG, "checkdeps: missing dependency '%s' for package '%s'\n", |
7d37d927 NG |
263 | missdepstring, alpm_pkg_get_name(tp)); |
264 | free(missdepstring); | |
2b73d451 | 265 | miss = _alpm_depmiss_new(alpm_pkg_get_name(tp), depend, NULL); |
2ed6b482 | 266 | baddeps = alpm_list_add(baddeps, miss); |
7d37d927 NG |
267 | } |
268 | } | |
269 | } | |
270 | ||
271 | if(reversedeps) { | |
272 | /* reversedeps handles the backwards dependencies, ie, | |
273 | * the packages listed in the requiredby field. */ | |
2ed6b482 NG |
274 | for(i = dblist; i; i = i->next) { |
275 | pmpkg_t *lp = i->data; | |
2ed6b482 NG |
276 | for(j = alpm_pkg_get_depends(lp); j; j = j->next) { |
277 | pmdepend_t *depend = j->data; | |
616b5967 | 278 | pmpkg_t *causingpkg = _alpm_find_dep_satisfier(modified, depend); |
2ed6b482 NG |
279 | /* we won't break this depend, if it is already broken, we ignore it */ |
280 | /* 1. check upgrade list for satisfiers */ | |
281 | /* 2. check dblist for satisfiers */ | |
e63366ae | 282 | if(causingpkg && |
616b5967 NG |
283 | !_alpm_find_dep_satisfier(upgrade, depend) && |
284 | !_alpm_find_dep_satisfier(dblist, depend)) { | |
4da70d80 | 285 | char *missdepstring = alpm_dep_compute_string(depend); |
e95e346a | 286 | _alpm_log(PM_LOG_DEBUG, "checkdeps: transaction would break '%s' dependency of '%s'\n", |
2ed6b482 | 287 | missdepstring, alpm_pkg_get_name(lp)); |
7d37d927 | 288 | free(missdepstring); |
e63366ae | 289 | miss = _alpm_depmiss_new(lp->name, depend, alpm_pkg_get_name(causingpkg)); |
2ed6b482 | 290 | baddeps = alpm_list_add(baddeps, miss); |
d04baaba JV |
291 | } |
292 | } | |
d04baaba JV |
293 | } |
294 | } | |
633dbeac | 295 | alpm_list_free(modified); |
2ed6b482 | 296 | alpm_list_free(dblist); |
d04baaba JV |
297 | |
298 | return(baddeps); | |
299 | } | |
300 | ||
fe3a4617 | 301 | static int dep_vercmp(const char *version1, pmdepmod_t mod, |
240bdf59 CX |
302 | const char *version2) |
303 | { | |
304 | int equal = 0; | |
305 | ||
306 | if(mod == PM_DEP_MOD_ANY) { | |
307 | equal = 1; | |
308 | } else { | |
a8ee1854 | 309 | int cmp = alpm_pkg_vercmp(version1, version2); |
240bdf59 CX |
310 | switch(mod) { |
311 | case PM_DEP_MOD_EQ: equal = (cmp == 0); break; | |
312 | case PM_DEP_MOD_GE: equal = (cmp >= 0); break; | |
313 | case PM_DEP_MOD_LE: equal = (cmp <= 0); break; | |
13dd2864 NG |
314 | case PM_DEP_MOD_LT: equal = (cmp < 0); break; |
315 | case PM_DEP_MOD_GT: equal = (cmp > 0); break; | |
240bdf59 CX |
316 | default: equal = 1; break; |
317 | } | |
318 | } | |
319 | return(equal); | |
320 | } | |
321 | ||
d0d8f605 | 322 | int _alpm_depcmp(pmpkg_t *pkg, pmdepend_t *dep) |
20f73d62 | 323 | { |
84ebf823 | 324 | alpm_list_t *i; |
735a197f DM |
325 | const char *pkgname = pkg->name; |
326 | const char *pkgversion = pkg->version; | |
84ebf823 | 327 | int satisfy = 0; |
240bdf59 | 328 | |
84ebf823 | 329 | /* check (pkg->name, pkg->version) */ |
735a197f DM |
330 | if(pkg->name_hash && dep->name_hash |
331 | && pkg->name_hash != dep->name_hash) { | |
332 | /* skip more expensive checks */ | |
333 | } else { | |
334 | satisfy = (strcmp(pkgname, dep->name) == 0 | |
335 | && dep_vercmp(pkgversion, dep->mod, dep->version)); | |
336 | if(satisfy) { | |
337 | return(satisfy); | |
338 | } | |
34a78d93 | 339 | } |
240bdf59 | 340 | |
0c5b6887 | 341 | /* check provisions, format : "name=version" */ |
84ebf823 | 342 | for(i = alpm_pkg_get_provides(pkg); i && !satisfy; i = i->next) { |
34a78d93 DM |
343 | const char *provision = i->data; |
344 | const char *provver = strchr(provision, '='); | |
20f73d62 | 345 | |
84ebf823 NG |
346 | if(provver == NULL) { /* no provision version */ |
347 | satisfy = (dep->mod == PM_DEP_MOD_ANY | |
34a78d93 | 348 | && strcmp(provision, dep->name) == 0); |
20f73d62 | 349 | } else { |
34a78d93 DM |
350 | /* This is a bit tricker than the old code for performance reasons. To |
351 | * prevent the need to copy and duplicate strings, strncmp only the name | |
352 | * portion if they are the same length, since there is a version and | |
62f5da37 DM |
353 | * operator in play here. Cast is to silence sign conversion warning; |
354 | * we know provver >= provision if we are here. */ | |
355 | size_t namelen = (size_t)(provver - provision); | |
84ebf823 | 356 | provver += 1; |
34a78d93 DM |
357 | satisfy = (strlen(dep->name) == namelen |
358 | && strncmp(provision, dep->name, namelen) == 0 | |
84ebf823 | 359 | && dep_vercmp(provver, dep->mod, dep->version)); |
20f73d62 DM |
360 | } |
361 | } | |
362 | ||
84ebf823 | 363 | return(satisfy); |
20f73d62 DM |
364 | } |
365 | ||
b2914bf0 | 366 | pmdepend_t *_alpm_splitdep(const char *depstring) |
d04baaba | 367 | { |
e24c22e3 DM |
368 | pmdepend_t *depend; |
369 | char *ptr = NULL; | |
7653bb93 | 370 | char *newstr = NULL; |
d04baaba | 371 | |
e24c22e3 DM |
372 | if(depstring == NULL) { |
373 | return(NULL); | |
374 | } | |
ccc1c731 | 375 | STRDUP(newstr, depstring, RET_ERR(PM_ERR_MEMORY, NULL)); |
23229097 | 376 | |
69c6d59b | 377 | CALLOC(depend, 1, sizeof(pmdepend_t), RET_ERR(PM_ERR_MEMORY, NULL)); |
d04baaba | 378 | |
e24c22e3 DM |
379 | /* Find a version comparator if one exists. If it does, set the type and |
380 | * increment the ptr accordingly so we can copy the right strings. */ | |
7653bb93 | 381 | if((ptr = strstr(newstr, ">="))) { |
95ea99e1 | 382 | depend->mod = PM_DEP_MOD_GE; |
e24c22e3 DM |
383 | *ptr = '\0'; |
384 | ptr += 2; | |
7653bb93 | 385 | } else if((ptr = strstr(newstr, "<="))) { |
95ea99e1 | 386 | depend->mod = PM_DEP_MOD_LE; |
e24c22e3 DM |
387 | *ptr = '\0'; |
388 | ptr += 2; | |
735a197f DM |
389 | } else if((ptr = strstr(newstr, "="))) { |
390 | /* Note: we must do =,<,> checks after <=, >= checks */ | |
95ea99e1 | 391 | depend->mod = PM_DEP_MOD_EQ; |
e24c22e3 DM |
392 | *ptr = '\0'; |
393 | ptr += 1; | |
13dd2864 NG |
394 | } else if((ptr = strstr(newstr, "<"))) { |
395 | depend->mod = PM_DEP_MOD_LT; | |
396 | *ptr = '\0'; | |
397 | ptr += 1; | |
398 | } else if((ptr = strstr(newstr, ">"))) { | |
399 | depend->mod = PM_DEP_MOD_GT; | |
400 | *ptr = '\0'; | |
401 | ptr += 1; | |
d04baaba | 402 | } else { |
ccc1c731 | 403 | /* no version specified - copy the name and return it */ |
95ea99e1 | 404 | depend->mod = PM_DEP_MOD_ANY; |
ccc1c731 | 405 | STRDUP(depend->name, newstr, RET_ERR(PM_ERR_MEMORY, NULL)); |
735a197f | 406 | depend->name_hash = _alpm_hash_sdbm(depend->name); |
ccc1c731 | 407 | depend->version = NULL; |
7653bb93 | 408 | free(newstr); |
e24c22e3 | 409 | return(depend); |
d04baaba | 410 | } |
d35e4894 | 411 | |
e24c22e3 DM |
412 | /* if we get here, we have a version comparator, copy the right parts |
413 | * to the right places */ | |
ccc1c731 | 414 | STRDUP(depend->name, newstr, RET_ERR(PM_ERR_MEMORY, NULL)); |
735a197f | 415 | depend->name_hash = _alpm_hash_sdbm(depend->name); |
ccc1c731 | 416 | STRDUP(depend->version, ptr, RET_ERR(PM_ERR_MEMORY, NULL)); |
7653bb93 | 417 | free(newstr); |
d04baaba | 418 | |
e24c22e3 | 419 | return(depend); |
d04baaba JV |
420 | } |
421 | ||
3e133524 DM |
422 | pmdepend_t *_alpm_dep_dup(const pmdepend_t *dep) |
423 | { | |
424 | pmdepend_t *newdep; | |
69c6d59b | 425 | CALLOC(newdep, 1, sizeof(pmdepend_t), RET_ERR(PM_ERR_MEMORY, NULL)); |
3e133524 DM |
426 | |
427 | STRDUP(newdep->name, dep->name, RET_ERR(PM_ERR_MEMORY, NULL)); | |
735a197f | 428 | newdep->name_hash = dep->name_hash; |
3e133524 DM |
429 | STRDUP(newdep->version, dep->version, RET_ERR(PM_ERR_MEMORY, NULL)); |
430 | newdep->mod = dep->mod; | |
431 | ||
432 | return(newdep); | |
433 | } | |
434 | ||
1c9f30b9 CX |
435 | /* These parameters are messy. We check if this package, given a list of |
436 | * targets and a db is safe to remove. We do NOT remove it if it is in the | |
437 | * target list, or if if the package was explictly installed and | |
438 | * include_explicit == 0 */ | |
439 | static int can_remove_package(pmdb_t *db, pmpkg_t *pkg, alpm_list_t *targets, | |
440 | int include_explicit) | |
f62f3750 | 441 | { |
f7199f36 | 442 | alpm_list_t *i; |
f62f3750 | 443 | |
8248b4bf | 444 | if(_alpm_pkg_find(targets, alpm_pkg_get_name(pkg))) { |
f62f3750 AG |
445 | return(0); |
446 | } | |
447 | ||
1c9f30b9 CX |
448 | if(!include_explicit) { |
449 | /* see if it was explicitly installed */ | |
450 | if(alpm_pkg_get_reason(pkg) == PM_PKG_REASON_EXPLICIT) { | |
5c9eec55 | 451 | _alpm_log(PM_LOG_DEBUG, "excluding %s -- explicitly installed\n", |
1c9f30b9 CX |
452 | alpm_pkg_get_name(pkg)); |
453 | return(0); | |
454 | } | |
f62f3750 AG |
455 | } |
456 | ||
1c9f30b9 CX |
457 | /* TODO: checkdeps could be used here, it handles multiple providers |
458 | * better, but that also makes it slower. | |
459 | * Also this would require to first add the package to the targets list, | |
460 | * then call checkdeps with it, then remove the package from the targets list | |
461 | * if checkdeps detected it would break something */ | |
462 | ||
f62f3750 | 463 | /* see if other packages need it */ |
1b5a8518 NG |
464 | for(i = _alpm_db_get_pkgcache(db); i; i = i->next) { |
465 | pmpkg_t *lpkg = i->data; | |
f7199f36 NG |
466 | if(_alpm_dep_edge(lpkg, pkg) && !_alpm_pkg_find(targets, lpkg->name)) { |
467 | return(0); | |
f62f3750 AG |
468 | } |
469 | } | |
470 | ||
471 | /* it's ok to remove */ | |
472 | return(1); | |
473 | } | |
474 | ||
1c9f30b9 CX |
475 | /** |
476 | * @brief Adds unneeded dependencies to an existing list of packages. | |
477 | * By unneeded, we mean dependencies that are only required by packages in the | |
478 | * target list, so they can be safely removed. | |
85b06f12 | 479 | * If the input list was topo sorted, the output list will be topo sorted too. |
1c9f30b9 CX |
480 | * |
481 | * @param db package database to do dependency tracing in | |
482 | * @param *targs pointer to a list of packages | |
483 | * @param include_explicit if 0, explicitly installed packages are not included | |
d04baaba | 484 | */ |
85b06f12 | 485 | void _alpm_recursedeps(pmdb_t *db, alpm_list_t *targs, int include_explicit) |
d04baaba | 486 | { |
f7199f36 | 487 | alpm_list_t *i, *j; |
d04baaba | 488 | |
da648bc2 AG |
489 | ALPM_LOG_FUNC; |
490 | ||
1c9f30b9 CX |
491 | if(db == NULL || targs == NULL) { |
492 | return; | |
d04baaba JV |
493 | } |
494 | ||
85b06f12 NG |
495 | for(i = targs; i; i = i->next) { |
496 | pmpkg_t *pkg = i->data; | |
f7199f36 NG |
497 | for(j = _alpm_db_get_pkgcache(db); j; j = j->next) { |
498 | pmpkg_t *deppkg = j->data; | |
499 | if(_alpm_dep_edge(pkg, deppkg) | |
500 | && can_remove_package(db, deppkg, targs, include_explicit)) { | |
501 | _alpm_log(PM_LOG_DEBUG, "adding '%s' to the targets\n", | |
502 | alpm_pkg_get_name(deppkg)); | |
503 | /* add it to the target list */ | |
504 | targs = alpm_list_add(targs, _alpm_pkg_dup(deppkg)); | |
d04baaba JV |
505 | } |
506 | } | |
507 | } | |
d04baaba JV |
508 | } |
509 | ||
f57f8d33 BI |
510 | /** |
511 | * helper function for resolvedeps: search for dep satisfier in dbs | |
512 | * | |
513 | * @param dep is the dependency to search for | |
514 | * @param dbs are the databases to search | |
515 | * @param excluding are the packages to exclude from the search | |
516 | * @param prompt if true, will cause an unresolvable dependency to issue an | |
517 | * interactive prompt asking whether the package should be removed from | |
518 | * the transaction or the transaction aborted; if false, simply returns | |
519 | * an error code without prompting | |
520 | * @return the resolved package | |
521 | **/ | |
522 | pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t *dbs, | |
523 | alpm_list_t *excluding, int prompt) | |
72c0ab5c NG |
524 | { |
525 | alpm_list_t *i, *j; | |
77efd512 | 526 | int ignored = 0; |
72c0ab5c NG |
527 | /* 1. literals */ |
528 | for(i = dbs; i; i = i->next) { | |
529 | pmpkg_t *pkg = _alpm_db_get_pkgfromcache(i->data, dep->name); | |
d0d8f605 | 530 | if(pkg && _alpm_depcmp(pkg, dep) && !_alpm_pkg_find(excluding, pkg->name)) { |
72c0ab5c | 531 | if(_alpm_pkg_should_ignore(pkg)) { |
f57f8d33 BI |
532 | int install = 0; |
533 | if (prompt) { | |
534 | QUESTION(handle->trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, pkg, | |
535 | NULL, NULL, &install); | |
56fd24ec NG |
536 | } else { |
537 | _alpm_log(PM_LOG_WARNING, _("ignoring package %s-%s\n"), pkg->name, pkg->version); | |
f57f8d33 | 538 | } |
72c0ab5c | 539 | if(!install) { |
77efd512 | 540 | ignored = 1; |
72c0ab5c NG |
541 | continue; |
542 | } | |
543 | } | |
544 | return(pkg); | |
545 | } | |
546 | } | |
547 | /* 2. satisfiers (skip literals here) */ | |
548 | for(i = dbs; i; i = i->next) { | |
549 | for(j = _alpm_db_get_pkgcache(i->data); j; j = j->next) { | |
550 | pmpkg_t *pkg = j->data; | |
d0d8f605 | 551 | if(_alpm_depcmp(pkg, dep) && strcmp(pkg->name, dep->name) != 0 && |
72c0ab5c NG |
552 | !_alpm_pkg_find(excluding, pkg->name)) { |
553 | if(_alpm_pkg_should_ignore(pkg)) { | |
f57f8d33 BI |
554 | int install = 0; |
555 | if (prompt) { | |
556 | QUESTION(handle->trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, | |
557 | pkg, NULL, NULL, &install); | |
56fd24ec NG |
558 | } else { |
559 | _alpm_log(PM_LOG_WARNING, _("ignoring package %s-%s\n"), pkg->name, pkg->version); | |
f57f8d33 | 560 | } |
72c0ab5c | 561 | if(!install) { |
77efd512 | 562 | ignored = 1; |
72c0ab5c NG |
563 | continue; |
564 | } | |
565 | } | |
fd8969f6 NG |
566 | _alpm_log(PM_LOG_WARNING, _("provider package was selected (%s provides %s)\n"), |
567 | pkg->name, dep->name); | |
72c0ab5c NG |
568 | return(pkg); |
569 | } | |
570 | } | |
571 | } | |
77efd512 NG |
572 | if(ignored) { /* resolvedeps will override these */ |
573 | pm_errno = PM_ERR_PKG_IGNORED; | |
574 | } else { | |
575 | pm_errno = PM_ERR_PKG_NOT_FOUND; | |
576 | } | |
72c0ab5c NG |
577 | return(NULL); |
578 | } | |
579 | ||
6c4d702c BI |
580 | /* Computes resolvable dependencies for a given package and adds that package |
581 | * and those resolvable dependencies to a list. | |
d04baaba | 582 | * |
eada558e | 583 | * @param localpkgs is the list of local packages |
6c4d702c BI |
584 | * @param dbs_sync are the sync databases |
585 | * @param pkg is the package to resolve | |
586 | * @param packages is a pointer to a list of packages which will be | |
587 | * searched first for any dependency packages needed to complete the | |
588 | * resolve, and to which will be added any [pkg] and all of its | |
589 | * dependencies not already on the list | |
590 | * @param remove is the set of packages which will be removed in this | |
591 | * transaction | |
592 | * @param data returns the dependency which could not be satisfied in the | |
593 | * event of an error | |
594 | * @return 0 on success, with [pkg] and all of its dependencies not already on | |
595 | * the [*packages] list added to that list, or -1 on failure due to an | |
596 | * unresolvable dependency, in which case the [*packages] list will be | |
597 | * unmodified by this function | |
d04baaba | 598 | */ |
eada558e | 599 | int _alpm_resolvedeps(alpm_list_t *localpkgs, alpm_list_t *dbs_sync, pmpkg_t *pkg, |
db3e1665 BI |
600 | alpm_list_t *preferred, alpm_list_t **packages, |
601 | alpm_list_t *remove, alpm_list_t **data) | |
d04baaba | 602 | { |
72c0ab5c | 603 | alpm_list_t *i, *j; |
61670172 AG |
604 | alpm_list_t *targ; |
605 | alpm_list_t *deps = NULL; | |
6c4d702c | 606 | alpm_list_t *packages_copy; |
d04baaba | 607 | |
da648bc2 AG |
608 | ALPM_LOG_FUNC; |
609 | ||
6c4d702c BI |
610 | if(_alpm_pkg_find(*packages, pkg->name) != NULL) { |
611 | return(0); | |
612 | } | |
613 | ||
614 | /* Create a copy of the packages list, so that it can be restored | |
615 | on error */ | |
616 | packages_copy = alpm_list_copy(*packages); | |
617 | /* [pkg] has not already been resolved into the packages list, so put it | |
618 | on that list */ | |
619 | *packages = alpm_list_add(*packages, pkg); | |
620 | ||
5c9eec55 | 621 | _alpm_log(PM_LOG_DEBUG, "started resolving dependencies\n"); |
6c4d702c | 622 | for(i = alpm_list_last(*packages); i; i = i->next) { |
72c0ab5c NG |
623 | pmpkg_t *tpkg = i->data; |
624 | targ = alpm_list_add(NULL, tpkg); | |
eada558e | 625 | deps = alpm_checkdeps(localpkgs, 0, remove, targ); |
72c0ab5c NG |
626 | alpm_list_free(targ); |
627 | for(j = deps; j; j = j->next) { | |
628 | pmdepmissing_t *miss = j->data; | |
629 | pmdepend_t *missdep = alpm_miss_get_dep(miss); | |
6c4d702c BI |
630 | /* check if one of the packages in the [*packages] list already satisfies this dependency */ |
631 | if(_alpm_find_dep_satisfier(*packages, missdep)) { | |
55a74551 NG |
632 | continue; |
633 | } | |
db3e1665 BI |
634 | /* check if one of the packages in the [preferred] list already satisfies this dependency */ |
635 | pmpkg_t *spkg = _alpm_find_dep_satisfier(preferred, missdep); | |
636 | if(!spkg) { | |
637 | /* find a satisfier package in the given repositories */ | |
638 | spkg = _alpm_resolvedep(missdep, dbs_sync, *packages, 0); | |
639 | } | |
72c0ab5c NG |
640 | if(!spkg) { |
641 | pm_errno = PM_ERR_UNSATISFIED_DEPS; | |
4da70d80 | 642 | char *missdepstring = alpm_dep_compute_string(missdep); |
02685504 | 643 | _alpm_log(PM_LOG_WARNING, _("cannot resolve \"%s\", a dependency of \"%s\"\n"), |
db3e1665 | 644 | missdepstring, tpkg->name); |
72c0ab5c NG |
645 | free(missdepstring); |
646 | if(data) { | |
647 | pmdepmissing_t *missd = _alpm_depmiss_new(miss->target, | |
db3e1665 | 648 | miss->depend, miss->causingpkg); |
72c0ab5c NG |
649 | if(missd) { |
650 | *data = alpm_list_add(*data, missd); | |
651 | } | |
fc8be933 | 652 | } |
6c4d702c BI |
653 | alpm_list_free(*packages); |
654 | *packages = packages_copy; | |
72c0ab5c NG |
655 | alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free); |
656 | alpm_list_free(deps); | |
657 | return(-1); | |
77efd512 | 658 | } else { |
72c0ab5c | 659 | _alpm_log(PM_LOG_DEBUG, "pulling dependency %s (needed by %s)\n", |
db3e1665 | 660 | alpm_pkg_get_name(spkg), alpm_pkg_get_name(tpkg)); |
6c4d702c | 661 | *packages = alpm_list_add(*packages, spkg); |
d04baaba | 662 | } |
d04baaba | 663 | } |
72c0ab5c NG |
664 | alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free); |
665 | alpm_list_free(deps); | |
d04baaba | 666 | } |
6c4d702c | 667 | alpm_list_free(packages_copy); |
5c9eec55 | 668 | _alpm_log(PM_LOG_DEBUG, "finished resolving dependencies\n"); |
d04baaba | 669 | return(0); |
d04baaba JV |
670 | } |
671 | ||
f7199f36 NG |
672 | /* Does pkg1 depend on pkg2, ie. does pkg2 satisfy a dependency of pkg1? */ |
673 | int _alpm_dep_edge(pmpkg_t *pkg1, pmpkg_t *pkg2) | |
674 | { | |
675 | alpm_list_t *i; | |
676 | for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) { | |
d0d8f605 | 677 | if(_alpm_depcmp(pkg2, i->data)) { |
f7199f36 NG |
678 | return(1); |
679 | } | |
680 | } | |
681 | return(0); | |
682 | } | |
683 | ||
1b2817f5 | 684 | const char SYMEXPORT *alpm_miss_get_target(const pmdepmissing_t *miss) |
986409f9 | 685 | { |
da648bc2 AG |
686 | ALPM_LOG_FUNC; |
687 | ||
986409f9 | 688 | /* Sanity checks */ |
986409f9 AG |
689 | ASSERT(miss != NULL, return(NULL)); |
690 | ||
3e133524 | 691 | return(miss->target); |
986409f9 AG |
692 | } |
693 | ||
e63366ae NG |
694 | const char SYMEXPORT *alpm_miss_get_causingpkg(const pmdepmissing_t *miss) |
695 | { | |
696 | ALPM_LOG_FUNC; | |
697 | ||
698 | /* Sanity checks */ | |
699 | ASSERT(miss != NULL, return(NULL)); | |
700 | ||
701 | return miss->causingpkg; | |
702 | } | |
703 | ||
99572ed8 | 704 | pmdepend_t SYMEXPORT *alpm_miss_get_dep(pmdepmissing_t *miss) |
986409f9 | 705 | { |
da648bc2 AG |
706 | ALPM_LOG_FUNC; |
707 | ||
986409f9 | 708 | /* Sanity checks */ |
99572ed8 | 709 | ASSERT(miss != NULL, return(NULL)); |
986409f9 | 710 | |
3e133524 | 711 | return(miss->depend); |
986409f9 AG |
712 | } |
713 | ||
1b2817f5 | 714 | pmdepmod_t SYMEXPORT alpm_dep_get_mod(const pmdepend_t *dep) |
986409f9 | 715 | { |
da648bc2 AG |
716 | ALPM_LOG_FUNC; |
717 | ||
986409f9 | 718 | /* Sanity checks */ |
99572ed8 | 719 | ASSERT(dep != NULL, return(-1)); |
986409f9 | 720 | |
3e133524 | 721 | return(dep->mod); |
986409f9 AG |
722 | } |
723 | ||
1b2817f5 | 724 | const char SYMEXPORT *alpm_dep_get_name(const pmdepend_t *dep) |
986409f9 | 725 | { |
da648bc2 AG |
726 | ALPM_LOG_FUNC; |
727 | ||
986409f9 | 728 | /* Sanity checks */ |
99572ed8 | 729 | ASSERT(dep != NULL, return(NULL)); |
986409f9 | 730 | |
3e133524 | 731 | return(dep->name); |
986409f9 | 732 | } |
5e68e9d4 | 733 | |
1b2817f5 | 734 | const char SYMEXPORT *alpm_dep_get_version(const pmdepend_t *dep) |
5e68e9d4 AF |
735 | { |
736 | ALPM_LOG_FUNC; | |
737 | ||
738 | /* Sanity checks */ | |
5e68e9d4 AF |
739 | ASSERT(dep != NULL, return(NULL)); |
740 | ||
3e133524 | 741 | return(dep->version); |
5e68e9d4 AF |
742 | } |
743 | ||
1b2817f5 DM |
744 | /** Reverse of splitdep; make a dep string from a pmdepend_t struct. |
745 | * The string must be freed! | |
746 | * @param dep the depend to turn into a string | |
747 | * @return a string-formatted dependency with operator if necessary | |
748 | */ | |
4da70d80 | 749 | char SYMEXPORT *alpm_dep_compute_string(const pmdepend_t *dep) |
0cff7c6b | 750 | { |
ccc1c731 | 751 | char *name, *opr, *ver, *str = NULL; |
1b2817f5 DM |
752 | size_t len; |
753 | ||
0cff7c6b NG |
754 | ALPM_LOG_FUNC; |
755 | ||
756 | /* Sanity checks */ | |
0cff7c6b NG |
757 | ASSERT(dep != NULL, return(NULL)); |
758 | ||
ccc1c731 DM |
759 | if(dep->name) { |
760 | name = dep->name; | |
761 | } else { | |
762 | name = ""; | |
763 | } | |
764 | ||
0cff7c6b NG |
765 | switch(dep->mod) { |
766 | case PM_DEP_MOD_ANY: | |
1b2817f5 | 767 | opr = ""; |
0cff7c6b NG |
768 | break; |
769 | case PM_DEP_MOD_GE: | |
1b2817f5 | 770 | opr = ">="; |
0cff7c6b NG |
771 | break; |
772 | case PM_DEP_MOD_LE: | |
1b2817f5 DM |
773 | opr = "<="; |
774 | break; | |
775 | case PM_DEP_MOD_EQ: | |
776 | opr = "="; | |
777 | break; | |
13dd2864 NG |
778 | case PM_DEP_MOD_LT: |
779 | opr = "<"; | |
780 | break; | |
781 | case PM_DEP_MOD_GT: | |
782 | opr = ">"; | |
783 | break; | |
1b2817f5 DM |
784 | default: |
785 | opr = ""; | |
0cff7c6b NG |
786 | break; |
787 | } | |
788 | ||
ccc1c731 DM |
789 | if(dep->version) { |
790 | ver = dep->version; | |
791 | } else { | |
792 | ver = ""; | |
793 | } | |
794 | ||
1b2817f5 | 795 | /* we can always compute len and print the string like this because opr |
ccc1c731 DM |
796 | * and ver will be empty when PM_DEP_MOD_ANY is the depend type. the |
797 | * reassignments above also ensure we do not do a strlen(NULL). */ | |
798 | len = strlen(name) + strlen(opr) + strlen(ver) + 1; | |
1b2817f5 | 799 | MALLOC(str, len, RET_ERR(PM_ERR_MEMORY, NULL)); |
ccc1c731 | 800 | snprintf(str, len, "%s%s%s", name, opr, ver); |
1b2817f5 DM |
801 | |
802 | return(str); | |
0cff7c6b | 803 | } |
d04baaba | 804 | /* vim: set ts=2 sw=2 noet: */ |