On Fri, Jan 16, 2009 at 8:13 PM, Bryan Ischo <[email protected]> wrote: > This change reorganizes the internal code so that packages are resolved one > at a time instead of all at once from a list. This will allow a future > checkin to prompt the user to see if they'd rather remove unresolvable > packages from the tranasaction and continue, or fail the transaction. This > change does not affect the actual behavior of libalpm and all tests pass > without changes.
Please wrap your commit message at 76 characters so it doesn't make the git-log console output go crazy. > > Signed-off-by: Bryan Ischo <[email protected]> > --- > lib/libalpm/deps.c | 64 > +++++++++++++++++++++++++++++++++++++++++++--------- > lib/libalpm/deps.h | 5 ++- > lib/libalpm/sync.c | 52 +++++++++++++++++++++++++++++++++--------- > 3 files changed, 97 insertions(+), 24 deletions(-) > > diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c > index 940f12c..a5b57ad 100644 > --- a/lib/libalpm/deps.c > +++ b/lib/libalpm/deps.c > @@ -546,17 +546,33 @@ pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t > *dbs, alpm_list_t *exclud > return(NULL); > } > > -/* populates list with packages that need to be installed to satisfy all > - * dependencies of packages in list > - * > - * @param remove contains packages elected for removal > +/* Computes resolvable dependencies for a given package and adds that > package > + * and those resolvable dependencies to a list. > + * > + * @param local is the local database > + * @param dbs_sync are the sync databases > + * @param pkg is the package to resolve > + * @param packages is a pointer to a list of packages which will be > + * searched first for any dependency packages needed to complete the > + * resolve, and to which will be added any [pkg] and all of its > + * dependencies not already on the list > + * @param remove is the set of packages which will be removed in this > + * transaction > + * @param data returns the dependency which could not be satisfied in the > + * event of an error > + * @return 0 on success, with [pkg] and all of its dependencies not already > on > + * the [*packages] list added to that list, or -1 on failure due to > an > + * unresolvable dependency, in which case the [*packages] list will > be > + * unmodified by this function > */ > -int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, alpm_list_t > *list, > - alpm_list_t *remove, alpm_list_t **data) > +int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *pkg, > + alpm_list_t **packages, > alpm_list_t *remove, > + alpm_list_t **data) No need to use two lines for what will fit on one line. > { > alpm_list_t *i, *j; > alpm_list_t *targ; > alpm_list_t *deps = NULL; > + alpm_list_t *working; > > ALPM_LOG_FUNC; > > @@ -564,8 +580,21 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t > *dbs_sync, alpm_list_t *list, > return(-1); > } > > + if(_alpm_pkg_find(*packages, pkg->name) != NULL) { > + /* It's already on the list, meaning it's already been > resolved and > + it and all of its dependencies have already been added */ Drop this comment- its pretty obvious what the conditional is checking. > + return(0); > + } > + > + /* [pkg] has not already been resolved into the packages list, so > put it > + * on that list */ > + *packages = alpm_list_add(*packages, pkg); > + /* And keep track of the head of the newly-added elements, so that > they > + can be quickly cut from the list on error */ > + working = alpm_list_last(*packages); > + > _alpm_log(PM_LOG_DEBUG, "started resolving dependencies\n"); > - for(i = list; i; i = i->next) { > + for(i = working; i; i = i->next) { > pmpkg_t *tpkg = i->data; > targ = alpm_list_add(NULL, tpkg); > deps = alpm_checkdeps(_alpm_db_get_pkgcache(local), 0, > remove, targ); > @@ -573,12 +602,12 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t > *dbs_sync, alpm_list_t *list, > for(j = deps; j; j = j->next) { > pmdepmissing_t *miss = j->data; > pmdepend_t *missdep = alpm_miss_get_dep(miss); > - /* check if one of the packages in list already > satisfies this dependency */ > - if(_alpm_find_dep_satisfier(list, missdep)) { > + /* check if one of the packages in the [*packages] > list already satisfies this dependency */ > + if(_alpm_find_dep_satisfier(*packages, missdep)) { > continue; > } > /* find a satisfier package in the given repositories > */ > - pmpkg_t *spkg = _alpm_resolvedep(missdep, dbs_sync, > list, tpkg); > + pmpkg_t *spkg = _alpm_resolvedep(missdep, dbs_sync, > *packages, tpkg); > if(!spkg) { > pm_errno = PM_ERR_UNSATISFIED_DEPS; > char *missdepstring = > alpm_dep_compute_string(missdep); > @@ -592,13 +621,26 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t > *dbs_sync, alpm_list_t *list, > *data = alpm_list_add(*data, > missd); > } > } > + /* Remove all packages that were added to > [*packages], so that > + * we return from error cleanly without > having affected the > + * [*packages] list. Detach the tail of the > list beginning at > + * [working] from the packages list and free > it. */ > + if (working == *packages) { > + *packages = NULL; > + } > + else { > + (*packages)->prev = working->prev; > + (*packages)->prev->next = NULL; > + working->prev = NULL; > + } > + alpm_list_free(working); Hmm, I'm not a fan of this manual manipulation- the data structures are there for a reason, so we aren't playing with pointers. The problem here is edge cases are likely to break- I'm not sure if you know, but we ensured alpm_list_last() is an O(1) operation for example by linking first->prev to the last item (the inverse is not true). You might be better off keeping two independent lists and then finding a way to join them when we are past the point of no return. > alpm_list_free_inner(deps, > (alpm_list_fn_free)_alpm_depmiss_free); > alpm_list_free(deps); > return(-1); > } else { > _alpm_log(PM_LOG_DEBUG, "pulling dependency > %s (needed by %s)\n", > alpm_pkg_get_name(spkg), > alpm_pkg_get_name(tpkg)); > - list = alpm_list_add(list, spkg); > + *packages = alpm_list_add(*packages, spkg); > } > } > alpm_list_free_inner(deps, > (alpm_list_fn_free)_alpm_depmiss_free); > diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h > index 2f3c450..9dca91d 100644 > --- a/lib/libalpm/deps.h > +++ b/lib/libalpm/deps.h > @@ -48,8 +48,9 @@ void _alpm_depmiss_free(pmdepmissing_t *miss); > alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, int reverse); > void _alpm_recursedeps(pmdb_t *db, alpm_list_t *targs, int > include_explicit); > pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t *dbs, alpm_list_t > *excluding, pmpkg_t *tpkg); > -int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, alpm_list_t > *list, > - alpm_list_t *remove, alpm_list_t **data); > +int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *pkg, > + alpm_list_t **packages, > alpm_list_t *remove, > + alpm_list_t **data); Coalesce the previous two lines. If you do that I'll stop pulling stupid words like 'coalesce' out of my vocab too. :) > int _alpm_dep_edge(pmpkg_t *pkg1, pmpkg_t *pkg2); > pmdepend_t *_alpm_splitdep(const char *depstring); > pmpkg_t *_alpm_find_dep_satisfier(alpm_list_t *pkgs, pmdepend_t *dep); > diff --git a/lib/libalpm/sync.c b/lib/libalpm/sync.c > index b458874..5daadbd 100644 > --- a/lib/libalpm/sync.c > +++ b/lib/libalpm/sync.c > @@ -399,6 +399,7 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t > *db_local, alpm_list_t *dbs_sync > { > alpm_list_t *deps = NULL; > alpm_list_t *list = NULL, *remove = NULL; /* allow checkdeps usage > with trans->packages */ > + alpm_list_t *unresolvable = NULL; > alpm_list_t *i, *j; > int ret = 0; > > @@ -411,15 +412,14 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t > *db_local, alpm_list_t *dbs_sync > *data = NULL; > } > > - for(i = trans->packages; i; i = i->next) { > - pmsyncpkg_t *sync = i->data; > - list = alpm_list_add(list, sync->pkg); > - } > - > - if(!(trans->flags & PM_TRANS_FLAG_NODEPS)) { > - /* store a pointer to the last original target so we can > tell what was > - * pulled by resolvedeps */ > - alpm_list_t *pulled = alpm_list_last(list); > + if(trans->flags & PM_TRANS_FLAG_NODEPS) { > + /* Simply build up [list] from all of the transaction > packages */ Unnecessary comment. > + for(i = trans->packages; i; i = i->next) { > + pmsyncpkg_t *sync = i->data; > + list = alpm_list_add(list, sync->pkg); > + } > + } else { > + /* Build up list by repeatedly resolving each transaction > package */ > /* Resolve targets dependencies */ > EVENT(trans, PM_TRANS_EVT_RESOLVEDEPS_START, NULL, NULL); > _alpm_log(PM_LOG_DEBUG, "resolving target's dependencies\n"); > @@ -432,14 +432,43 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t > *db_local, alpm_list_t *dbs_sync > } > } > > - if(_alpm_resolvedeps(db_local, dbs_sync, list, remove, data) > == -1) { > + /* Resolve packages in the transaction one at a time, in > addtion > + building up a list of packages which could not be > resolved. */ > + for(i = trans->packages; i; i = i->next) { > + pmpkg_t *pkg = ((pmsyncpkg_t *) i->data)->pkg; > + if(_alpm_resolvedeps(db_local, dbs_sync, pkg, &list, > remove, data) == -1) { > + /* Failed to resolve a dependency of [pkg]. > It goes on the > + unresolvable list. [list] was not > touched, so no > + unnecessary dependency packages were > added to it. */ I know it sounds weird to hate on comments, but it takes me a lot longer to get through the comment than just reading the code and seeing what it says. Shorten or kill this one. > + unresolvable = alpm_list_add(unresolvable, > pkg); > + } > + /* Else, [list] now additionally contains [pkg] and > all of its > + dependencies not already on the list */ > + } > + > + /* If there were unresolvable top-level packages, fail the > + transaction. In a future checkin, the user will be asked > if they'd > + like to drop the unresolvable packages intead. */ Don't tie in future checkins, we all know its coming. Just drop the comment. > + if(unresolvable != NULL) { > /* pm_errno is set by resolvedeps */ > ret = -1; > goto cleanup; > } > > - for(i = pulled->next; i; i = i->next) { > + /* Add all packages which were "pulled" (i.e. weren't > already in the > + transaction) to the transaction in pmsyncpkg_t structures > */ > + for(i = list; i; i = i->next) { > pmpkg_t *spkg = i->data; > + for(j = trans->packages; j; j = j->next) { > + if(_alpm_pkg_cmp(spkg, ((pmsyncpkg_t *) > j->data)->pkg) == 0) { > + spkg = NULL; > + break; > + } > + } > + if (spkg == NULL) { > + continue; > + } > + > pmsyncpkg_t *sync = > _alpm_sync_new(PM_PKG_REASON_DEPEND, spkg, NULL); > if(sync == NULL) { > ret = -1; > @@ -627,6 +656,7 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t > *db_local, alpm_list_t *dbs_sync > cleanup: > alpm_list_free(list); > alpm_list_free(remove); > + alpm_list_free(unresolvable); > > return(ret); > } I know I commented a lot, but overall this patch looks fine to me. If you make the adjustments I've pointed out I'll merge this. -Dan _______________________________________________ pacman-dev mailing list [email protected] http://archlinux.org/mailman/listinfo/pacman-dev
