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