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