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