[pacman-dev] [PATCH 1/4] Internal code reorganization in preparation for changes to package resolution.
Dan McGee
dpmcgee at gmail.com
Fri Jan 16 21:35:44 EST 2009
On Fri, Jan 16, 2009 at 8:13 PM, Bryan Ischo
<bji-keyword-pacman.3644cb at www.ischo.com> 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 <bryan at ischo.com>
> ---
> 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
More information about the pacman-dev
mailing list