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