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