libalpm
Arch Linux Package Manager Library
|
00001 /* 00002 * deps.c 00003 * 00004 * Copyright (c) 2006-2011 Pacman Development Team <pacman-dev@archlinux.org> 00005 * Copyright (c) 2002-2006 by Judd Vinet <jvinet@zeroflux.org> 00006 * Copyright (c) 2005 by Aurelien Foret <orelien@chez.com> 00007 * Copyright (c) 2005, 2006 by Miklos Vajna <vmiklos@frugalware.org> 00008 * 00009 * This program is free software; you can redistribute it and/or modify 00010 * it under the terms of the GNU General Public License as published by 00011 * the Free Software Foundation; either version 2 of the License, or 00012 * (at your option) any later version. 00013 * 00014 * This program is distributed in the hope that it will be useful, 00015 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00017 * GNU General Public License for more details. 00018 * 00019 * You should have received a copy of the GNU General Public License 00020 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00021 */ 00022 00023 #include <stdlib.h> 00024 #include <stdio.h> 00025 #include <string.h> 00026 00027 /* libalpm */ 00028 #include "deps.h" 00029 #include "alpm_list.h" 00030 #include "util.h" 00031 #include "log.h" 00032 #include "graph.h" 00033 #include "package.h" 00034 #include "db.h" 00035 #include "handle.h" 00036 #include "trans.h" 00037 00038 void _alpm_dep_free(alpm_depend_t *dep) 00039 { 00040 FREE(dep->name); 00041 FREE(dep->version); 00042 FREE(dep); 00043 } 00044 00045 static alpm_depmissing_t *depmiss_new(const char *target, alpm_depend_t *dep, 00046 const char *causingpkg) 00047 { 00048 alpm_depmissing_t *miss; 00049 00050 MALLOC(miss, sizeof(alpm_depmissing_t), return NULL); 00051 00052 STRDUP(miss->target, target, return NULL); 00053 miss->depend = _alpm_dep_dup(dep); 00054 STRDUP(miss->causingpkg, causingpkg, return NULL); 00055 00056 return miss; 00057 } 00058 00059 void _alpm_depmiss_free(alpm_depmissing_t *miss) 00060 { 00061 _alpm_dep_free(miss->depend); 00062 FREE(miss->target); 00063 FREE(miss->causingpkg); 00064 FREE(miss); 00065 } 00066 00067 /* Does pkg1 depend on pkg2, ie. does pkg2 satisfy a dependency of pkg1? */ 00068 static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2) 00069 { 00070 alpm_list_t *i; 00071 for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) { 00072 if(_alpm_depcmp(pkg2, i->data)) { 00073 return 1; 00074 } 00075 } 00076 return 0; 00077 } 00078 00079 /* Convert a list of alpm_pkg_t * to a graph structure, 00080 * with a edge for each dependency. 00081 * Returns a list of vertices (one vertex = one package) 00082 * (used by alpm_sortbydeps) 00083 */ 00084 static alpm_list_t *dep_graph_init(alpm_list_t *targets) 00085 { 00086 alpm_list_t *i, *j; 00087 alpm_list_t *vertices = NULL; 00088 /* We create the vertices */ 00089 for(i = targets; i; i = i->next) { 00090 alpm_graph_t *vertex = _alpm_graph_new(); 00091 vertex->data = (void *)i->data; 00092 vertices = alpm_list_add(vertices, vertex); 00093 } 00094 00095 /* We compute the edges */ 00096 for(i = vertices; i; i = i->next) { 00097 alpm_graph_t *vertex_i = i->data; 00098 alpm_pkg_t *p_i = vertex_i->data; 00099 /* TODO this should be somehow combined with alpm_checkdeps */ 00100 for(j = vertices; j; j = j->next) { 00101 alpm_graph_t *vertex_j = j->data; 00102 alpm_pkg_t *p_j = vertex_j->data; 00103 if(_alpm_dep_edge(p_i, p_j)) { 00104 vertex_i->children = 00105 alpm_list_add(vertex_i->children, vertex_j); 00106 } 00107 } 00108 vertex_i->childptr = vertex_i->children; 00109 } 00110 return vertices; 00111 } 00112 00113 /* Re-order a list of target packages with respect to their dependencies. 00114 * 00115 * Example (reverse == 0): 00116 * A depends on C 00117 * B depends on A 00118 * Target order is A,B,C,D 00119 * 00120 * Should be re-ordered to C,A,B,D 00121 * 00122 * if reverse is > 0, the dependency order will be reversed. 00123 * 00124 * This function returns the new alpm_list_t* target list. 00125 * 00126 */ 00127 alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, 00128 alpm_list_t *targets, int reverse) 00129 { 00130 alpm_list_t *newtargs = NULL; 00131 alpm_list_t *vertices = NULL; 00132 alpm_list_t *vptr; 00133 alpm_graph_t *vertex; 00134 00135 if(targets == NULL) { 00136 return NULL; 00137 } 00138 00139 _alpm_log(handle, ALPM_LOG_DEBUG, "started sorting dependencies\n"); 00140 00141 vertices = dep_graph_init(targets); 00142 00143 vptr = vertices; 00144 vertex = vertices->data; 00145 while(vptr) { 00146 /* mark that we touched the vertex */ 00147 vertex->state = -1; 00148 int found = 0; 00149 while(vertex->childptr && !found) { 00150 alpm_graph_t *nextchild = vertex->childptr->data; 00151 vertex->childptr = vertex->childptr->next; 00152 if(nextchild->state == 0) { 00153 found = 1; 00154 nextchild->parent = vertex; 00155 vertex = nextchild; 00156 } 00157 else if(nextchild->state == -1) { 00158 alpm_pkg_t *vertexpkg = vertex->data; 00159 alpm_pkg_t *childpkg = nextchild->data; 00160 const char *message; 00161 00162 _alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n")); 00163 if(reverse) { 00164 message =_("%s will be removed after its %s dependency\n"); 00165 } else { 00166 message =_("%s will be installed before its %s dependency\n"); 00167 } 00168 _alpm_log(handle, ALPM_LOG_WARNING, message, vertexpkg->name, childpkg->name); 00169 } 00170 } 00171 if(!found) { 00172 newtargs = alpm_list_add(newtargs, vertex->data); 00173 /* mark that we've left this vertex */ 00174 vertex->state = 1; 00175 vertex = vertex->parent; 00176 if(!vertex) { 00177 vptr = vptr->next; 00178 while(vptr) { 00179 vertex = vptr->data; 00180 if(vertex->state == 0) break; 00181 vptr = vptr->next; 00182 } 00183 } 00184 } 00185 } 00186 00187 _alpm_log(handle, ALPM_LOG_DEBUG, "sorting dependencies finished\n"); 00188 00189 if(reverse) { 00190 /* reverse the order */ 00191 alpm_list_t *tmptargs = alpm_list_reverse(newtargs); 00192 /* free the old one */ 00193 alpm_list_free(newtargs); 00194 newtargs = tmptargs; 00195 } 00196 00197 alpm_list_free_inner(vertices, _alpm_graph_free); 00198 alpm_list_free(vertices); 00199 00200 return newtargs; 00201 } 00202 00203 static int no_dep_version(alpm_handle_t *handle) 00204 { 00205 int flags = alpm_trans_get_flags(handle); 00206 return flags != -1 && (flags & ALPM_TRANS_FLAG_NODEPVERSION); 00207 } 00208 00209 static alpm_depend_t *filtered_depend(alpm_depend_t *dep, int nodepversion) 00210 { 00211 if(nodepversion) { 00212 alpm_depend_t *newdep = _alpm_dep_dup(dep); 00213 ASSERT(newdep, return dep); 00214 newdep->mod = ALPM_DEP_MOD_ANY; 00215 dep = newdep; 00216 } 00217 return dep; 00218 } 00219 00220 static void release_filtered_depend(alpm_depend_t *dep, int nodepversion) 00221 { 00222 if(nodepversion) { 00223 free(dep); 00224 } 00225 } 00226 00227 static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep) 00228 { 00229 alpm_list_t *i; 00230 00231 for(i = pkgs; i; i = i->next) { 00232 alpm_pkg_t *pkg = i->data; 00233 if(_alpm_depcmp(pkg, dep)) { 00234 return pkg; 00235 } 00236 } 00237 return NULL; 00238 } 00239 00240 /** Find a package satisfying a specified dependency. 00241 * The dependency can include versions with depmod operators. 00242 * @param pkgs an alpm_list_t* of alpm_pkg_t where the satisfier will be searched 00243 * @param depstring package or provision name, versioned or not 00244 * @return a alpm_pkg_t* satisfying depstring 00245 */ 00246 alpm_pkg_t SYMEXPORT *alpm_find_satisfier(alpm_list_t *pkgs, const char *depstring) 00247 { 00248 alpm_depend_t *dep = _alpm_splitdep(depstring); 00249 if(!dep) { 00250 return NULL; 00251 } 00252 alpm_pkg_t *pkg = find_dep_satisfier(pkgs, dep); 00253 _alpm_dep_free(dep); 00254 return pkg; 00255 } 00256 00257 /** Checks dependencies and returns missing ones in a list. 00258 * Dependencies can include versions with depmod operators. 00259 * @param handle the context handle 00260 * @param pkglist the list of local packages 00261 * @param remove an alpm_list_t* of packages to be removed 00262 * @param upgrade an alpm_list_t* of packages to be upgraded (remove-then-upgrade) 00263 * @param reversedeps handles the backward dependencies 00264 * @return an alpm_list_t* of alpm_depmissing_t pointers. 00265 */ 00266 alpm_list_t SYMEXPORT *alpm_checkdeps(alpm_handle_t *handle, 00267 alpm_list_t *pkglist, alpm_list_t *remove, alpm_list_t *upgrade, 00268 int reversedeps) 00269 { 00270 alpm_list_t *i, *j; 00271 alpm_list_t *dblist = NULL, *modified = NULL; 00272 alpm_list_t *baddeps = NULL; 00273 int nodepversion; 00274 00275 CHECK_HANDLE(handle, return NULL); 00276 00277 for(i = pkglist; i; i = i->next) { 00278 alpm_pkg_t *pkg = i->data; 00279 if(_alpm_pkg_find(remove, pkg->name) || _alpm_pkg_find(upgrade, pkg->name)) { 00280 modified = alpm_list_add(modified, pkg); 00281 } else { 00282 dblist = alpm_list_add(dblist, pkg); 00283 } 00284 } 00285 00286 nodepversion = no_dep_version(handle); 00287 00288 /* look for unsatisfied dependencies of the upgrade list */ 00289 for(i = upgrade; i; i = i->next) { 00290 alpm_pkg_t *tp = i->data; 00291 _alpm_log(handle, ALPM_LOG_DEBUG, "checkdeps: package %s-%s\n", 00292 tp->name, tp->version); 00293 00294 for(j = alpm_pkg_get_depends(tp); j; j = j->next) { 00295 alpm_depend_t *depend = j->data; 00296 depend = filtered_depend(depend, nodepversion); 00297 /* 1. we check the upgrade list */ 00298 /* 2. we check database for untouched satisfying packages */ 00299 if(!find_dep_satisfier(upgrade, depend) && 00300 !find_dep_satisfier(dblist, depend)) { 00301 /* Unsatisfied dependency in the upgrade list */ 00302 alpm_depmissing_t *miss; 00303 char *missdepstring = alpm_dep_compute_string(depend); 00304 _alpm_log(handle, ALPM_LOG_DEBUG, "checkdeps: missing dependency '%s' for package '%s'\n", 00305 missdepstring, tp->name); 00306 free(missdepstring); 00307 miss = depmiss_new(tp->name, depend, NULL); 00308 baddeps = alpm_list_add(baddeps, miss); 00309 } 00310 release_filtered_depend(depend, nodepversion); 00311 } 00312 } 00313 00314 if(reversedeps) { 00315 /* reversedeps handles the backwards dependencies, ie, 00316 * the packages listed in the requiredby field. */ 00317 for(i = dblist; i; i = i->next) { 00318 alpm_pkg_t *lp = i->data; 00319 for(j = alpm_pkg_get_depends(lp); j; j = j->next) { 00320 alpm_depend_t *depend = j->data; 00321 depend = filtered_depend(depend, nodepversion); 00322 alpm_pkg_t *causingpkg = find_dep_satisfier(modified, depend); 00323 /* we won't break this depend, if it is already broken, we ignore it */ 00324 /* 1. check upgrade list for satisfiers */ 00325 /* 2. check dblist for satisfiers */ 00326 if(causingpkg && 00327 !find_dep_satisfier(upgrade, depend) && 00328 !find_dep_satisfier(dblist, depend)) { 00329 alpm_depmissing_t *miss; 00330 char *missdepstring = alpm_dep_compute_string(depend); 00331 _alpm_log(handle, ALPM_LOG_DEBUG, "checkdeps: transaction would break '%s' dependency of '%s'\n", 00332 missdepstring, lp->name); 00333 free(missdepstring); 00334 miss = depmiss_new(lp->name, depend, causingpkg->name); 00335 baddeps = alpm_list_add(baddeps, miss); 00336 } 00337 release_filtered_depend(depend, nodepversion); 00338 } 00339 } 00340 } 00341 00342 alpm_list_free(modified); 00343 alpm_list_free(dblist); 00344 00345 return baddeps; 00346 } 00347 00348 static int dep_vercmp(const char *version1, alpm_depmod_t mod, 00349 const char *version2) 00350 { 00351 int equal = 0; 00352 00353 if(mod == ALPM_DEP_MOD_ANY) { 00354 equal = 1; 00355 } else { 00356 int cmp = alpm_pkg_vercmp(version1, version2); 00357 switch(mod) { 00358 case ALPM_DEP_MOD_EQ: equal = (cmp == 0); break; 00359 case ALPM_DEP_MOD_GE: equal = (cmp >= 0); break; 00360 case ALPM_DEP_MOD_LE: equal = (cmp <= 0); break; 00361 case ALPM_DEP_MOD_LT: equal = (cmp < 0); break; 00362 case ALPM_DEP_MOD_GT: equal = (cmp > 0); break; 00363 default: equal = 1; break; 00364 } 00365 } 00366 return equal; 00367 } 00368 00369 int _alpm_depcmp_literal(alpm_pkg_t *pkg, alpm_depend_t *dep) 00370 { 00371 if(pkg->name_hash != dep->name_hash 00372 || strcmp(pkg->name, dep->name) != 0) { 00373 /* skip more expensive checks */ 00374 return 0; 00375 } 00376 return dep_vercmp(pkg->version, dep->mod, dep->version); 00377 } 00378 00379 int _alpm_depcmp(alpm_pkg_t *pkg, alpm_depend_t *dep) 00380 { 00381 alpm_list_t *i; 00382 int satisfy = _alpm_depcmp_literal(pkg, dep); 00383 00384 if(satisfy) { 00385 return satisfy; 00386 } 00387 00388 /* check provisions, name and version if available */ 00389 for(i = alpm_pkg_get_provides(pkg); i && !satisfy; i = i->next) { 00390 alpm_depend_t *provision = i->data; 00391 00392 if(dep->mod == ALPM_DEP_MOD_ANY) { 00393 /* any version will satisfy the requirement */ 00394 satisfy = (provision->name_hash == dep->name_hash 00395 && strcmp(provision->name, dep->name) == 0); 00396 } else if(provision->mod == ALPM_DEP_MOD_EQ) { 00397 /* provision specifies a version, so try it out */ 00398 satisfy = (provision->name_hash == dep->name_hash 00399 && strcmp(provision->name, dep->name) == 0 00400 && dep_vercmp(provision->version, dep->mod, dep->version)); 00401 } 00402 } 00403 00404 return satisfy; 00405 } 00406 00407 alpm_depend_t *_alpm_splitdep(const char *depstring) 00408 { 00409 alpm_depend_t *depend; 00410 const char *ptr, *version; 00411 size_t deplen; 00412 00413 if(depstring == NULL) { 00414 return NULL; 00415 } 00416 00417 MALLOC(depend, sizeof(alpm_depend_t), return NULL); 00418 deplen = strlen(depstring); 00419 00420 /* Find a version comparator if one exists. If it does, set the type and 00421 * increment the ptr accordingly so we can copy the right strings. */ 00422 if((ptr = memchr(depstring, '<', deplen))) { 00423 if(ptr[1] == '=') { 00424 depend->mod = ALPM_DEP_MOD_LE; 00425 version = ptr + 2; 00426 } else { 00427 depend->mod = ALPM_DEP_MOD_LT; 00428 version = ptr + 1; 00429 } 00430 } else if((ptr = memchr(depstring, '>', deplen))) { 00431 if(ptr[1] == '=') { 00432 depend->mod = ALPM_DEP_MOD_GE; 00433 version = ptr + 2; 00434 } else { 00435 depend->mod = ALPM_DEP_MOD_GT; 00436 version = ptr + 1; 00437 } 00438 } else if((ptr = memchr(depstring, '=', deplen))) { 00439 /* Note: we must do =,<,> checks after <=, >= checks */ 00440 depend->mod = ALPM_DEP_MOD_EQ; 00441 version = ptr + 1; 00442 } else { 00443 /* no version specified, leave ptr NULL and set version to NULL */ 00444 depend->mod = ALPM_DEP_MOD_ANY; 00445 depend->version = NULL; 00446 version = NULL; 00447 } 00448 00449 /* copy the right parts to the right places */ 00450 if(ptr) { 00451 STRNDUP(depend->name, depstring, ptr - depstring, return NULL); 00452 } else { 00453 STRDUP(depend->name, depstring, return NULL); 00454 } 00455 depend->name_hash = _alpm_hash_sdbm(depend->name); 00456 if(version) { 00457 STRDUP(depend->version, version, return NULL); 00458 } 00459 00460 return depend; 00461 } 00462 00463 alpm_depend_t *_alpm_dep_dup(const alpm_depend_t *dep) 00464 { 00465 alpm_depend_t *newdep; 00466 CALLOC(newdep, 1, sizeof(alpm_depend_t), return NULL); 00467 00468 STRDUP(newdep->name, dep->name, return NULL); 00469 newdep->name_hash = dep->name_hash; 00470 STRDUP(newdep->version, dep->version, return NULL); 00471 newdep->mod = dep->mod; 00472 00473 return newdep; 00474 } 00475 00476 /* These parameters are messy. We check if this package, given a list of 00477 * targets and a db is safe to remove. We do NOT remove it if it is in the 00478 * target list, or if if the package was explictly installed and 00479 * include_explicit == 0 */ 00480 static int can_remove_package(alpm_db_t *db, alpm_pkg_t *pkg, 00481 alpm_list_t *targets, int include_explicit) 00482 { 00483 alpm_list_t *i; 00484 00485 if(_alpm_pkg_find(targets, pkg->name)) { 00486 return 0; 00487 } 00488 00489 if(!include_explicit) { 00490 /* see if it was explicitly installed */ 00491 if(alpm_pkg_get_reason(pkg) == ALPM_PKG_REASON_EXPLICIT) { 00492 _alpm_log(db->handle, ALPM_LOG_DEBUG, 00493 "excluding %s -- explicitly installed\n", pkg->name); 00494 return 0; 00495 } 00496 } 00497 00498 /* TODO: checkdeps could be used here, it handles multiple providers 00499 * better, but that also makes it slower. 00500 * Also this would require to first add the package to the targets list, 00501 * then call checkdeps with it, then remove the package from the targets list 00502 * if checkdeps detected it would break something */ 00503 00504 /* see if other packages need it */ 00505 for(i = _alpm_db_get_pkgcache(db); i; i = i->next) { 00506 alpm_pkg_t *lpkg = i->data; 00507 if(_alpm_dep_edge(lpkg, pkg) && !_alpm_pkg_find(targets, lpkg->name)) { 00508 return 0; 00509 } 00510 } 00511 00512 /* it's ok to remove */ 00513 return 1; 00514 } 00515 00516 /** 00517 * @brief Adds unneeded dependencies to an existing list of packages. 00518 * By unneeded, we mean dependencies that are only required by packages in the 00519 * target list, so they can be safely removed. 00520 * If the input list was topo sorted, the output list will be topo sorted too. 00521 * 00522 * @param db package database to do dependency tracing in 00523 * @param *targs pointer to a list of packages 00524 * @param include_explicit if 0, explicitly installed packages are not included 00525 * @return 0 on success, -1 on errors 00526 */ 00527 int _alpm_recursedeps(alpm_db_t *db, alpm_list_t *targs, int include_explicit) 00528 { 00529 alpm_list_t *i, *j; 00530 00531 if(db == NULL || targs == NULL) { 00532 return -1; 00533 } 00534 00535 for(i = targs; i; i = i->next) { 00536 alpm_pkg_t *pkg = i->data; 00537 for(j = _alpm_db_get_pkgcache(db); j; j = j->next) { 00538 alpm_pkg_t *deppkg = j->data; 00539 if(_alpm_dep_edge(pkg, deppkg) 00540 && can_remove_package(db, deppkg, targs, include_explicit)) { 00541 alpm_pkg_t *copy; 00542 _alpm_log(db->handle, ALPM_LOG_DEBUG, "adding '%s' to the targets\n", 00543 deppkg->name); 00544 /* add it to the target list */ 00545 if(_alpm_pkg_dup(deppkg, ©)) { 00546 return -1; 00547 } 00548 targs = alpm_list_add(targs, copy); 00549 } 00550 } 00551 } 00552 return 0; 00553 } 00554 00555 /** 00556 * helper function for resolvedeps: search for dep satisfier in dbs 00557 * 00558 * @param handle the context handle 00559 * @param dep is the dependency to search for 00560 * @param dbs are the databases to search 00561 * @param excluding are the packages to exclude from the search 00562 * @param prompt if true, will cause an unresolvable dependency to issue an 00563 * interactive prompt asking whether the package should be removed from 00564 * the transaction or the transaction aborted; if false, simply returns 00565 * an error code without prompting 00566 * @return the resolved package 00567 **/ 00568 static alpm_pkg_t *resolvedep(alpm_handle_t *handle, alpm_depend_t *dep, 00569 alpm_list_t *dbs, alpm_list_t *excluding, int prompt) 00570 { 00571 alpm_list_t *i, *j; 00572 int ignored = 0; 00573 00574 alpm_list_t *providers = NULL; 00575 int count; 00576 00577 /* 1. literals */ 00578 for(i = dbs; i; i = i->next) { 00579 alpm_pkg_t *pkg = _alpm_db_get_pkgfromcache(i->data, dep->name); 00580 if(pkg && _alpm_depcmp_literal(pkg, dep) 00581 && !_alpm_pkg_find(excluding, pkg->name)) { 00582 if(_alpm_pkg_should_ignore(handle, pkg)) { 00583 int install = 0; 00584 if(prompt) { 00585 QUESTION(handle, ALPM_QUESTION_INSTALL_IGNOREPKG, pkg, 00586 NULL, NULL, &install); 00587 } else { 00588 _alpm_log(handle, ALPM_LOG_WARNING, _("ignoring package %s-%s\n"), 00589 pkg->name, pkg->version); 00590 } 00591 if(!install) { 00592 ignored = 1; 00593 continue; 00594 } 00595 } 00596 return pkg; 00597 } 00598 } 00599 /* 2. satisfiers (skip literals here) */ 00600 for(i = dbs; i; i = i->next) { 00601 for(j = _alpm_db_get_pkgcache(i->data); j; j = j->next) { 00602 alpm_pkg_t *pkg = j->data; 00603 /* with hash != hash, we can even skip the strcmp() as we know they can't 00604 * possibly be the same string */ 00605 if(pkg->name_hash != dep->name_hash && _alpm_depcmp(pkg, dep) 00606 && !_alpm_pkg_find(excluding, pkg->name)) { 00607 if(_alpm_pkg_should_ignore(handle, pkg)) { 00608 int install = 0; 00609 if(prompt) { 00610 QUESTION(handle, ALPM_QUESTION_INSTALL_IGNOREPKG, 00611 pkg, NULL, NULL, &install); 00612 } else { 00613 _alpm_log(handle, ALPM_LOG_WARNING, _("ignoring package %s-%s\n"), 00614 pkg->name, pkg->version); 00615 } 00616 if(!install) { 00617 ignored = 1; 00618 continue; 00619 } 00620 } 00621 _alpm_log(handle, ALPM_LOG_DEBUG, "provider found (%s provides %s)\n", 00622 pkg->name, dep->name); 00623 providers = alpm_list_add(providers, pkg); 00624 /* keep looking for other providers in the all dbs */ 00625 } 00626 } 00627 } 00628 00629 /* first check if one provider is already installed locally */ 00630 for(i = providers; i; i = i->next) { 00631 alpm_pkg_t *pkg = i->data; 00632 if(_alpm_db_get_pkgfromcache(handle->db_local, pkg->name)) { 00633 alpm_list_free(providers); 00634 return pkg; 00635 } 00636 } 00637 count = alpm_list_count(providers); 00638 if(count >= 1) { 00639 /* default to first provider if there is no QUESTION callback */ 00640 int index = 0; 00641 if(count > 1) { 00642 /* if there is more than one provider, we ask the user */ 00643 QUESTION(handle, ALPM_QUESTION_SELECT_PROVIDER, 00644 providers, dep, NULL, &index); 00645 } 00646 if(index >= 0 && index < count) { 00647 alpm_list_t *nth = alpm_list_nth(providers, index); 00648 alpm_pkg_t *pkg = nth->data; 00649 alpm_list_free(providers); 00650 return pkg; 00651 } 00652 alpm_list_free(providers); 00653 providers = NULL; 00654 } 00655 00656 if(ignored) { /* resolvedeps will override these */ 00657 handle->pm_errno = ALPM_ERR_PKG_IGNORED; 00658 } else { 00659 handle->pm_errno = ALPM_ERR_PKG_NOT_FOUND; 00660 } 00661 return NULL; 00662 } 00663 00664 /** Find a package satisfying a specified dependency. 00665 * First look for a literal, going through each db one by one. Then look for 00666 * providers. The first satisfier found is returned. 00667 * The dependency can include versions with depmod operators. 00668 * @param handle the context handle 00669 * @param dbs an alpm_list_t* of alpm_db_t where the satisfier will be searched 00670 * @param depstring package or provision name, versioned or not 00671 * @return a alpm_pkg_t* satisfying depstring 00672 */ 00673 alpm_pkg_t SYMEXPORT *alpm_find_dbs_satisfier(alpm_handle_t *handle, 00674 alpm_list_t *dbs, const char *depstring) 00675 { 00676 alpm_depend_t *dep; 00677 alpm_pkg_t *pkg; 00678 00679 CHECK_HANDLE(handle, return NULL); 00680 ASSERT(dbs, RET_ERR(handle, ALPM_ERR_WRONG_ARGS, NULL)); 00681 00682 dep = _alpm_splitdep(depstring); 00683 ASSERT(dep, return NULL); 00684 pkg = resolvedep(handle, dep, dbs, NULL, 1); 00685 _alpm_dep_free(dep); 00686 return pkg; 00687 } 00688 00689 /** 00690 * Computes resolvable dependencies for a given package and adds that package 00691 * and those resolvable dependencies to a list. 00692 * 00693 * @param handle the context handle 00694 * @param localpkgs is the list of local packages 00695 * @param pkg is the package to resolve 00696 * @param preferred packages to prefer when resolving 00697 * @param packages is a pointer to a list of packages which will be 00698 * searched first for any dependency packages needed to complete the 00699 * resolve, and to which will be added any [pkg] and all of its 00700 * dependencies not already on the list 00701 * @param remove is the set of packages which will be removed in this 00702 * transaction 00703 * @param data returns the dependency which could not be satisfied in the 00704 * event of an error 00705 * @return 0 on success, with [pkg] and all of its dependencies not already on 00706 * the [*packages] list added to that list, or -1 on failure due to an 00707 * unresolvable dependency, in which case the [*packages] list will be 00708 * unmodified by this function 00709 */ 00710 int _alpm_resolvedeps(alpm_handle_t *handle, alpm_list_t *localpkgs, 00711 alpm_pkg_t *pkg, alpm_list_t *preferred, alpm_list_t **packages, 00712 alpm_list_t *remove, alpm_list_t **data) 00713 { 00714 int ret = 0; 00715 alpm_list_t *i, *j; 00716 alpm_list_t *targ; 00717 alpm_list_t *deps = NULL; 00718 alpm_list_t *packages_copy; 00719 00720 if(_alpm_pkg_find(*packages, pkg->name) != NULL) { 00721 return 0; 00722 } 00723 00724 if(handle->trans->flags & ALPM_TRANS_FLAG_RECURSE) { 00725 /* removing local packages from the equation causes the entire dep chain to 00726 * get pulled for each target- e.g., pactree -u output */ 00727 localpkgs = NULL; 00728 } 00729 00730 /* Create a copy of the packages list, so that it can be restored 00731 on error */ 00732 packages_copy = alpm_list_copy(*packages); 00733 /* [pkg] has not already been resolved into the packages list, so put it 00734 on that list */ 00735 *packages = alpm_list_add(*packages, pkg); 00736 00737 _alpm_log(handle, ALPM_LOG_DEBUG, "started resolving dependencies\n"); 00738 for(i = alpm_list_last(*packages); i; i = i->next) { 00739 alpm_pkg_t *tpkg = i->data; 00740 targ = alpm_list_add(NULL, tpkg); 00741 deps = alpm_checkdeps(handle, localpkgs, remove, targ, 0); 00742 alpm_list_free(targ); 00743 00744 for(j = deps; j; j = j->next) { 00745 alpm_depmissing_t *miss = j->data; 00746 alpm_depend_t *missdep = miss->depend; 00747 /* check if one of the packages in the [*packages] list already satisfies 00748 * this dependency */ 00749 if(find_dep_satisfier(*packages, missdep)) { 00750 _alpm_depmiss_free(miss); 00751 continue; 00752 } 00753 /* check if one of the packages in the [preferred] list already satisfies 00754 * this dependency */ 00755 alpm_pkg_t *spkg = find_dep_satisfier(preferred, missdep); 00756 if(!spkg) { 00757 /* find a satisfier package in the given repositories */ 00758 spkg = resolvedep(handle, missdep, handle->dbs_sync, *packages, 0); 00759 } 00760 if(!spkg) { 00761 handle->pm_errno = ALPM_ERR_UNSATISFIED_DEPS; 00762 char *missdepstring = alpm_dep_compute_string(missdep); 00763 _alpm_log(handle, ALPM_LOG_WARNING, 00764 _("cannot resolve \"%s\", a dependency of \"%s\"\n"), 00765 missdepstring, tpkg->name); 00766 free(missdepstring); 00767 if(data) { 00768 *data = alpm_list_add(*data, miss); 00769 } 00770 ret = -1; 00771 } else { 00772 _alpm_log(handle, ALPM_LOG_DEBUG, 00773 "pulling dependency %s (needed by %s)\n", 00774 spkg->name, tpkg->name); 00775 *packages = alpm_list_add(*packages, spkg); 00776 _alpm_depmiss_free(miss); 00777 } 00778 } 00779 alpm_list_free(deps); 00780 } 00781 00782 if(handle->trans->flags & ALPM_TRANS_FLAG_NEEDED) { 00783 /* remove any deps that were pulled that match installed version */ 00784 /* odd loop syntax so we can modify the list as we iterate */ 00785 i = *packages; 00786 while(i) { 00787 alpm_pkg_t *tpkg = i->data; 00788 alpm_pkg_t *local = _alpm_db_get_pkgfromcache( 00789 handle->db_local, tpkg->name); 00790 if(local && _alpm_pkg_compare_versions(tpkg, local) == 0) { 00791 /* with the NEEDED flag, packages up to date are not reinstalled */ 00792 _alpm_log(handle, ALPM_LOG_DEBUG, 00793 "not adding dep %s-%s as it is not needed, same version\n", 00794 local->name, local->version); 00795 j = i; 00796 i = i->next; 00797 *packages = alpm_list_remove_item(*packages, j); 00798 free(j); 00799 } else { 00800 i = i->next; 00801 } 00802 } 00803 } 00804 00805 if(ret != 0) { 00806 alpm_list_free(*packages); 00807 *packages = packages_copy; 00808 } else { 00809 alpm_list_free(packages_copy); 00810 } 00811 _alpm_log(handle, ALPM_LOG_DEBUG, "finished resolving dependencies\n"); 00812 return ret; 00813 } 00814 00815 /** Reverse of splitdep; make a dep string from a alpm_depend_t struct. 00816 * The string must be freed! 00817 * @param dep the depend to turn into a string 00818 * @return a string-formatted dependency with operator if necessary 00819 */ 00820 char SYMEXPORT *alpm_dep_compute_string(const alpm_depend_t *dep) 00821 { 00822 const char *name, *opr, *ver; 00823 char *str; 00824 size_t len; 00825 00826 ASSERT(dep != NULL, return NULL); 00827 00828 if(dep->name) { 00829 name = dep->name; 00830 } else { 00831 name = ""; 00832 } 00833 00834 switch(dep->mod) { 00835 case ALPM_DEP_MOD_ANY: 00836 opr = ""; 00837 break; 00838 case ALPM_DEP_MOD_GE: 00839 opr = ">="; 00840 break; 00841 case ALPM_DEP_MOD_LE: 00842 opr = "<="; 00843 break; 00844 case ALPM_DEP_MOD_EQ: 00845 opr = "="; 00846 break; 00847 case ALPM_DEP_MOD_LT: 00848 opr = "<"; 00849 break; 00850 case ALPM_DEP_MOD_GT: 00851 opr = ">"; 00852 break; 00853 default: 00854 opr = ""; 00855 break; 00856 } 00857 00858 if(dep->mod != ALPM_DEP_MOD_ANY && dep->version) { 00859 ver = dep->version; 00860 } else { 00861 ver = ""; 00862 } 00863 00864 /* we can always compute len and print the string like this because opr 00865 * and ver will be empty when ALPM_DEP_MOD_ANY is the depend type. the 00866 * reassignments above also ensure we do not do a strlen(NULL). */ 00867 len = strlen(name) + strlen(opr) + strlen(ver) + 1; 00868 MALLOC(str, len, return NULL); 00869 snprintf(str, len, "%s%s%s", name, opr, ver); 00870 00871 return str; 00872 } 00873 /* vim: set ts=2 sw=2 noet: */