path: root/librazor/transaction.c

/*
 * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
 * Copyright (C) 2008  Red Hat, Inc
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#define _GNU_SOURCE

#include <stdlib.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <ctype.h>
#include <fnmatch.h>

#include "razor-internal.h"
#include "razor.h"

static int
provider_satisfies_requirement(struct razor_property *provider,
			       const char *provider_strings,
			       uint32_t flags,
			       const char *required)
{
	int cmp, len;
	const char *provided = &provider_strings[provider->version];

	if (!*required)
		return 1;
	if (!*provided) {
		if (flags & RAZOR_PROPERTY_LESS)
			return 0;
		else
			return 1;
	}

	cmp = razor_versioncmp(provided, required);

	switch (flags & RAZOR_PROPERTY_RELATION_MASK) {
	case RAZOR_PROPERTY_LESS:
		return cmp < 0;

	case RAZOR_PROPERTY_LESS | RAZOR_PROPERTY_EQUAL:
		if (cmp <= 0)
			return 1;
		/* fall through: FIXME, make sure this is correct */

	case RAZOR_PROPERTY_EQUAL:
		if (cmp == 0)
			return 1;

		/* "foo == 1.1" is satisfied by "foo 1.1-2" */
		len = strlen(required);
		if (!strncmp(required, provided, len) && provided[len] == '-')
			return 1;
		return 0;

	case RAZOR_PROPERTY_GREATER | RAZOR_PROPERTY_EQUAL:
		return cmp >= 0;

	case RAZOR_PROPERTY_GREATER:
		return cmp > 0;
	}

	/* shouldn't happen */
	return 0;
}

#define TRANS_PACKAGE_PRESENT		1
#define TRANS_PACKAGE_UPDATE		2
#define TRANS_PROPERTY_SATISFIED	0x80000000

struct transaction_set {
	struct razor_set *set;
	uint32_t *packages;
	uint32_t *properties;
};

struct razor_transaction {
	int package_count, errors;
	struct transaction_set system, upstream;
	int changes;
};

static void
transaction_set_init(struct transaction_set *ts, struct razor_set *set)
{
	int count;

	ts->set = set;
	count = set->packages.size / sizeof (struct razor_package);
	ts->packages = zalloc(count * sizeof *ts->packages);
	count = set->properties.size / sizeof (struct razor_property);
	ts->properties = zalloc(count * sizeof *ts->properties);
}

static void
transaction_set_release(struct transaction_set *ts)
{
	free(ts->packages);
	free(ts->properties);
}

static void
transaction_set_install_package(struct transaction_set *ts,
				struct razor_package *package)
{
	struct razor_package *pkgs;
	struct list *prop;
	int i;

	pkgs = ts->set->packages.data;
	i = package - pkgs;
	if (ts->packages[i] == TRANS_PACKAGE_PRESENT)
		return;

	ts->packages[i] = TRANS_PACKAGE_PRESENT;

	prop = list_first(&package->properties, &ts->set->property_pool);
	while (prop) {
		ts->properties[prop->data]++;
		prop = list_next(prop);
	}
}

static void
transaction_set_remove_package(struct transaction_set *ts,
			       struct razor_package *package)
{
	struct razor_package *pkgs;
	struct list *prop;
	int i;

	pkgs = ts->set->packages.data;
	i = package - pkgs;
	if (ts->packages[i] == 0)
		return;

	ts->packages[i] = 0;

	prop = list_first(&package->properties, &ts->set->property_pool);
	while (prop) {
		ts->properties[prop->data]--;
		prop = list_next(prop);
	}
}

RAZOR_EXPORT struct razor_transaction *
razor_transaction_create(struct razor_set *system, struct razor_set *upstream)
{
	struct razor_transaction *trans;
	struct razor_package *p, *spkgs, *pend;

	trans = zalloc(sizeof *trans);
	transaction_set_init(&trans->system, system);
	transaction_set_init(&trans->upstream, upstream);

	spkgs = trans->system.set->packages.data;
	pend = trans->system.set->packages.data +
		trans->system.set->packages.size;
	for (p = spkgs; p < pend; p++)
		transaction_set_install_package(&trans->system, p);

	return trans;
}

RAZOR_EXPORT void
razor_transaction_install_package(struct razor_transaction *trans,
				  struct razor_package *package)
{
	transaction_set_install_package(&trans->upstream, package);
	trans->changes++;
}

RAZOR_EXPORT void
razor_transaction_remove_package(struct razor_transaction *trans,
				 struct razor_package *package)
{
	transaction_set_remove_package(&trans->system, package);
	trans->changes++;
}

RAZOR_EXPORT void
razor_transaction_update_package(struct razor_transaction *trans,
				  struct razor_package *package)
{
	struct razor_package *spkgs, *upkgs, *end;

	spkgs = trans->system.set->packages.data;
	upkgs = trans->upstream.set->packages.data;
	end = trans->system.set->packages.data +
		trans->system.set->packages.size;
	if (spkgs <= package && package < end)
		trans->system.packages[package - spkgs] |= TRANS_PACKAGE_UPDATE;
	else
		trans->upstream.packages[package - upkgs] |= TRANS_PACKAGE_UPDATE;
}

struct prop_iter {
	struct razor_property *p, *start, *end;
	const char *pool;
	uint32_t *present;
};

static void
prop_iter_init(struct prop_iter *pi, struct transaction_set *ts)
{
	pi->p = ts->set->properties.data;
	pi->start = ts->set->properties.data;
	pi->end = ts->set->properties.data + ts->set->properties.size;
	pi->pool = ts->set->string_pool.data;
	pi->present = ts->properties;
}

static int
prop_iter_next(struct prop_iter *pi, uint32_t flags, struct razor_property **p)
{
	while (pi->p < pi->end) {
		if ((pi->present[pi->p - pi->start] & ~TRANS_PROPERTY_SATISFIED) &&
		    (pi->p->flags & RAZOR_PROPERTY_TYPE_MASK) == flags) {
			*p = pi->p++;
			return 1;
		}
		pi->p++;
	}

	return 0;
}

static struct razor_property *
prop_iter_seek_to(struct prop_iter *pi,
		  uint32_t flags, const char *match)
{
	uint32_t name;

	while (pi->p < pi->end && strcmp(&pi->pool[pi->p->name], match) < 0)
		pi->p++;

	if (pi->p == pi->end || strcmp(&pi->pool[pi->p->name], match) > 0)
		return NULL;

	name = pi->p->name;
	while (pi->p < pi->end &&
	       pi->p->name == name &&
	       (pi->p->flags & RAZOR_PROPERTY_TYPE_MASK) != flags)
		pi->p++;

	if (pi->p == pi->end || pi->p->name != name)
		return NULL;

	return pi->p;
}

/* Remove packages from set that provide any of the matching (same
 * name and type) providers from ppi onwards that match the
 * requirement that rpi points to. */
static void
remove_matching_providers(struct razor_transaction *trans,
			  struct prop_iter *ppi,
			  uint32_t flags,
			  const char *version)
{
	struct razor_property *p;
	struct razor_package *pkg, *pkgs;
	struct razor_package_iterator pkg_iter;
	struct razor_set *set;
	const char *n, *v, *a;
	uint32_t type;

	if (ppi->present == trans->system.properties)
		set = trans->system.set;
	else
		set = trans->upstream.set;

	pkgs = (struct razor_package *) set->packages.data;
	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;
	for (p = ppi->p;
	     p < ppi->end &&
	     p->name == ppi->p->name &&
	     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type;
	     p++) {
		if (!ppi->present[p - ppi->start])
			continue;
		if (!provider_satisfies_requirement(p, ppi->pool,
						    flags, version))
			continue;

		razor_package_iterator_init_for_property(&pkg_iter, set, p);
		while (razor_package_iterator_next(&pkg_iter,
						   &pkg, &n, &v, &a)) {
			fprintf(stderr, "removing %s-%s\n", n, v);
			razor_transaction_remove_package(trans, pkg);
		}
	}
}

static void
flag_matching_providers(struct razor_transaction *trans,
			struct prop_iter *ppi,
			struct razor_property *r,
			struct prop_iter *rpi,
			unsigned int flag)
{
	struct razor_property *p;
	struct razor_package *pkg, *pkgs;
	struct razor_package_iterator pkg_iter;
	struct razor_set *set;
	const char *name, *version, *arch;
	uint32_t *flags, type;

	if (ppi->present == trans->system.properties) {
		set = trans->system.set;
		flags = trans->system.packages;
	} else {
		set = trans->upstream.set;
		flags = trans->upstream.packages;
	}

	pkgs = (struct razor_package *) set->packages.data;
	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;
	for (p = ppi->p;
	     p < ppi->end &&
		     p->name == ppi->p->name &&
		     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type;
	     p++) {
		if (!ppi->present[p - ppi->start])
			continue;
		if (!provider_satisfies_requirement(p, ppi->pool,
						    r->flags,
						    &rpi->pool[r->version]))
			continue;

		razor_package_iterator_init_for_property(&pkg_iter, set, p);
		while (razor_package_iterator_next(&pkg_iter, &pkg,
						   &name, &version, &arch)) {

			fprintf(stderr, "flagging %s-%s for providing %s matching %s %s\n",
				name, version,
				ppi->pool + p->name,
				rpi->pool + r->name,
				rpi->pool + r->version);
			flags[pkg - pkgs] |= flag;
		}
	}
}

static struct razor_package *
pick_matching_provider(struct razor_set *set,
		       struct prop_iter *ppi,
		       uint32_t flags,
		       const char *version)
{
	struct razor_property *p;
	struct razor_package *pkgs;
	struct list *i;
	uint32_t type;

	/* This is where we decide which pkgs to pull in to satisfy a
	 * requirement.  There may be several different providers
	 * (different versions) and each version of a provider may
	 * come from a number of packages.  We pick the first package
	 * from the first provider that matches. */

	pkgs = set->packages.data;
	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;
	for (p = ppi->p;
	     p < ppi->end &&
		     p->name == ppi->p->name &&
		     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type &&
		     ppi->present[p - ppi->start] == 0;
	     p++) {
		if (!provider_satisfies_requirement(p, ppi->pool,
						    flags, version))
			continue;

		i = list_first(&p->packages, &set->package_pool);

		return &pkgs[i->data];
	}

	return NULL;
}

static void
remove_obsoleted_packages(struct razor_transaction *trans)
{
	struct razor_property *up;
	struct razor_package *spkgs;
	struct prop_iter spi, upi;

	spkgs = trans->system.set->packages.data;
	prop_iter_init(&spi, &trans->system);
	prop_iter_init(&upi, &trans->upstream);

	while (prop_iter_next(&upi, RAZOR_PROPERTY_OBSOLETES, &up)) {
		if (!prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES,
				       &upi.pool[up->name]))
			continue;
		remove_matching_providers(trans, &spi, up->flags,
					  &upi.pool[up->version]);
	}
}

static int
any_provider_satisfies_requirement(struct prop_iter *ppi,
				   uint32_t flags,
				   const char *version)
{
	struct razor_property *p;
	uint32_t type;

	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;
	for (p = ppi->p;
	     p < ppi->end &&
		     p->name == ppi->p->name &&
		     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type;
	     p++) {
		if (ppi->present[p - ppi->start] > 0 &&
		    provider_satisfies_requirement(p, ppi->pool,
						   flags, version))
			return 1;
	}

	return 0;
}

static void
clear_requires_flags(struct transaction_set *ts)
{
	struct razor_property *p;
	const char *pool;
	int i, count;

	count = ts->set->properties.size / sizeof *p;
	p = ts->set->properties.data;
	pool = ts->set->string_pool.data;
	for (i = 0; i < count; i++) {
		ts->properties[i] &= ~TRANS_PROPERTY_SATISFIED;
		if (strncmp(&pool[p[i].name], "rpmlib(", 7) == 0)
			ts->properties[i] |= TRANS_PROPERTY_SATISFIED;
	}
}

static void
mark_satisfied_requires(struct razor_transaction *trans,
			struct transaction_set *rts,
			struct transaction_set *pts)
{
	struct prop_iter rpi, ppi;
	struct razor_property *rp;

	prop_iter_init(&rpi, rts);
	prop_iter_init(&ppi, pts);

	while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
		if (!prop_iter_seek_to(&ppi, RAZOR_PROPERTY_PROVIDES,
				       &rpi.pool[rp->name]))
			continue;

		if (any_provider_satisfies_requirement(&ppi, rp->flags,
						       &rpi.pool[rp->version]))
			rpi.present[rp - rpi.start] |= TRANS_PROPERTY_SATISFIED;
	}
}

static void
mark_all_satisfied_requires(struct razor_transaction *trans)
{
	clear_requires_flags(&trans->system);
	clear_requires_flags(&trans->upstream);
	mark_satisfied_requires(trans, &trans->system, &trans->system);
	mark_satisfied_requires(trans, &trans->system, &trans->upstream);
	mark_satisfied_requires(trans, &trans->upstream, &trans->system);
	mark_satisfied_requires(trans, &trans->upstream, &trans->upstream);
}

static void
update_unsatisfied_packages(struct razor_transaction *trans)
{
	struct razor_package *spkgs, *pkg;
	struct razor_property *sp;
	struct prop_iter spi;
	struct razor_package_iterator pkg_iter;
	const char *name, *version, *arch;

	spkgs = trans->system.set->packages.data;
	prop_iter_init(&spi, &trans->system);

	while (prop_iter_next(&spi, RAZOR_PROPERTY_REQUIRES, &sp)) {
		if (spi.present[sp - spi.start] & TRANS_PROPERTY_SATISFIED)
			continue;

		razor_package_iterator_init_for_property(&pkg_iter,
							 trans->system.set,
							 sp);
		while (razor_package_iterator_next(&pkg_iter, &pkg,
						   &name, &version, &arch)) {
			fprintf(stderr, "updating %s because %s %s %s "
				"isn't satisfied\n",
				name, spi.pool + sp->name,
				razor_property_relation_to_string(sp),
				spi.pool + sp->version);
			trans->system.packages[pkg - spkgs] |=
				TRANS_PACKAGE_UPDATE;
		}
	}
}

RAZOR_EXPORT void
razor_transaction_update_all(struct razor_transaction *trans)
{
	struct razor_package *p;
	int i, count;

	count = trans->system.set->packages.size / sizeof *p;
	for (i = 0; i < count; i++)
		trans->system.packages[i] |= TRANS_PACKAGE_UPDATE;
}

static void
update_conflicted_packages(struct razor_transaction *trans)
{
	struct razor_package *pkg, *spkgs;
	struct razor_property *up, *sp;
	struct prop_iter spi, upi;
	struct razor_package_iterator pkg_iter;
	const char *name, *version, *arch;

	spkgs = trans->system.set->packages.data;
	prop_iter_init(&spi, &trans->system);
	prop_iter_init(&upi, &trans->upstream);

	while (prop_iter_next(&spi, RAZOR_PROPERTY_CONFLICTS, &sp)) {
		if (!prop_iter_seek_to(&upi, RAZOR_PROPERTY_PROVIDES,
				       &spi.pool[sp->name]))
			continue;

		if (!any_provider_satisfies_requirement(&upi, sp->flags,
							&spi.pool[sp->version]))
			continue;

		razor_package_iterator_init_for_property(&pkg_iter,
							 trans->system.set,
							 sp);
		while (razor_package_iterator_next(&pkg_iter, &pkg,
						   &name, &version, &arch)) {
			fprintf(stderr, "updating %s %s because it conflicts with %s",
				name, version, spi.pool + sp->name);
			trans->system.packages[pkg - spkgs] |=
				TRANS_PACKAGE_UPDATE;
		}
	}

	prop_iter_init(&spi, &trans->system);
	prop_iter_init(&upi, &trans->upstream);

	while (prop_iter_next(&upi, RAZOR_PROPERTY_CONFLICTS, &up)) {
		sp = prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES,
				       &upi.pool[upi.p->name]);

		if (sp)
			flag_matching_providers(trans, &spi, up, &upi,
						TRANS_PACKAGE_UPDATE);
	}
}

static void
pull_in_requirements(struct razor_transaction *trans,
		     struct prop_iter *rpi, struct prop_iter *ppi)
{
	struct razor_property *rp, *pp;
	struct razor_package *pkg, *upkgs;

	upkgs = trans->upstream.set->packages.data;
	while (prop_iter_next(rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
		if (rpi->present[rp - rpi->start] & TRANS_PROPERTY_SATISFIED)
			continue;

		pp = prop_iter_seek_to(ppi, RAZOR_PROPERTY_PROVIDES,
				       &rpi->pool[rp->name]);
		if (pp == NULL)
			continue;
		pkg = pick_matching_provider(trans->upstream.set,
					     ppi, rp->flags,
					     &rpi->pool[rp->version]);
		if (pkg == NULL)
			continue;

		rpi->present[rp - rpi->start] |= TRANS_PROPERTY_SATISFIED;

		fprintf(stderr, "pulling in %s-%s.%s which provides %s %s %s "
			"to satisfy %s %s %s\n",
			ppi->pool + pkg->name,
			ppi->pool + pkg->version,
			ppi->pool + pkg->arch,
			ppi->pool + pp->name,
			razor_property_relation_to_string(pp),
			ppi->pool + pp->version,
			&rpi->pool[rp->name],
			razor_property_relation_to_string(rp),
			&rpi->pool[rp->version]);

		trans->upstream.packages[pkg - upkgs] |= TRANS_PACKAGE_UPDATE;
	}
}

static void
pull_in_all_requirements(struct razor_transaction *trans)
{
	struct prop_iter rpi, ppi;

	prop_iter_init(&rpi, &trans->system);
	prop_iter_init(&ppi, &trans->upstream);
	pull_in_requirements(trans, &rpi, &ppi);

	prop_iter_init(&rpi, &trans->upstream);
	prop_iter_init(&ppi, &trans->upstream);
	pull_in_requirements(trans, &rpi, &ppi);
}

static void
flush_scheduled_system_updates(struct razor_transaction *trans)
{
 	struct razor_package_iterator *pi;
 	struct razor_package *p, *pkg, *spkgs;
	struct prop_iter ppi;
	const char *name, *version, *arch;

	spkgs = trans->system.set->packages.data;
	pi = razor_package_iterator_create(trans->system.set);
	prop_iter_init(&ppi, &trans->upstream);

	while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {
		if (!(trans->system.packages[p - spkgs] & TRANS_PACKAGE_UPDATE))
			continue;

		if (!prop_iter_seek_to(&ppi, RAZOR_PROPERTY_PROVIDES, name))
			continue;

		pkg = pick_matching_provider(trans->upstream.set, &ppi,
					     RAZOR_PROPERTY_GREATER, version);
		if (pkg == NULL)
			continue;

		fprintf(stderr, "updating %s-%s to %s-%s\n",
			name, version,
			&ppi.pool[pkg->name], &ppi.pool[pkg->version]);

		razor_transaction_remove_package(trans, p);
		razor_transaction_install_package(trans, pkg);
	}

	razor_package_iterator_destroy(pi);
}

static void
flush_scheduled_upstream_updates(struct razor_transaction *trans)
{
 	struct razor_package_iterator *pi;
 	struct razor_package *p, *upkgs;
	struct prop_iter spi;
	const char *name, *version, *arch;

	upkgs = trans->upstream.set->packages.data;
	pi = razor_package_iterator_create(trans->upstream.set);
	prop_iter_init(&spi, &trans->system);

	while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {
		if (!(trans->upstream.packages[p - upkgs] & TRANS_PACKAGE_UPDATE))
			continue;

		if (prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES, name))
			remove_matching_providers(trans,
						  &spi,
						  RAZOR_PROPERTY_LESS,
						  version);
		razor_transaction_install_package(trans, p);
		fprintf(stderr, "installing %s-%s\n", name, version);
	}
}

RAZOR_EXPORT int
razor_transaction_resolve(struct razor_transaction *trans)
{
	int last = 0;

	flush_scheduled_system_updates(trans);
	flush_scheduled_upstream_updates(trans);

	while (last < trans->changes) {
		last = trans->changes;
		remove_obsoleted_packages(trans);
		mark_all_satisfied_requires(trans);
		update_unsatisfied_packages(trans);
		update_conflicted_packages(trans);
		pull_in_all_requirements(trans);
		flush_scheduled_system_updates(trans);
		flush_scheduled_upstream_updates(trans);
	}

	return trans->changes;
}

static void
describe_unsatisfied(struct razor_set *set, struct razor_property *rp)
{
	struct razor_package_iterator pi;
	struct razor_package *pkg;
	const char *name, *version, *arch, *pool;

	pool = set->string_pool.data;
	if (pool[rp->version] == '\0') {
		razor_package_iterator_init_for_property(&pi, set, rp);
		while (razor_package_iterator_next(&pi, &pkg,
						   &name, &version, &arch))
			fprintf(stderr, "%s is needed by %s-%s.%s\n",
				&pool[rp->name],
				name, version, arch);
	} else {
		razor_package_iterator_init_for_property(&pi, set, rp);
		while (razor_package_iterator_next(&pi, &pkg,
						   &name, &version, &arch))
			fprintf(stderr, "%s %s %s is needed by %s-%s.%s\n",
				&pool[rp->name],
				razor_property_relation_to_string(rp),
				&pool[rp->version],
				name, version, arch);
	}
}

RAZOR_EXPORT int
razor_transaction_describe(struct razor_transaction *trans)
{
	struct prop_iter rpi;
	struct razor_property *rp;
	int unsatisfied;

	flush_scheduled_system_updates(trans);
	flush_scheduled_upstream_updates(trans);
	mark_all_satisfied_requires(trans);

	unsatisfied = 0;
	prop_iter_init(&rpi, &trans->system);
	while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
		if (!(rpi.present[rp - rpi.start] & TRANS_PROPERTY_SATISFIED)) {
			describe_unsatisfied(trans->system.set, rp);
		        unsatisfied++;
		}
	}

	prop_iter_init(&rpi, &trans->upstream);
	while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
		if (!(rpi.present[rp - rpi.start] & TRANS_PROPERTY_SATISFIED)) {
			describe_unsatisfied(trans->upstream.set, rp);
			unsatisfied++;
		}
	}

	return unsatisfied;
}

RAZOR_EXPORT int
razor_transaction_unsatisfied_property(struct razor_transaction *trans,
				       const char *name,
				       uint32_t flags,
				       const char *version)
{
	struct prop_iter pi;
	struct razor_property *p;

	prop_iter_init(&pi, &trans->system);
	while (prop_iter_next(&pi, flags & RAZOR_PROPERTY_TYPE_MASK, &p)) {
		if (!(trans->system.properties[p - pi.start] & TRANS_PROPERTY_SATISFIED) &&
		    p->flags == flags &&
		    strcmp(&pi.pool[p->name], name) == 0 &&
		    strcmp(&pi.pool[p->version], version) == 0)

			return 1;
	}

	prop_iter_init(&pi, &trans->upstream);
	while (prop_iter_next(&pi, flags & RAZOR_PROPERTY_TYPE_MASK, &p)) {
		if (!(trans->upstream.properties[p - pi.start] & TRANS_PROPERTY_SATISFIED) &&
		    p->flags == flags &&
		    strcmp(&pi.pool[p->name], name) == 0 &&
		    strcmp(&pi.pool[p->version], version) == 0)

			return 1;
	}

	return 0;
}

RAZOR_EXPORT struct razor_set *
razor_transaction_finish(struct razor_transaction *trans)
{
	struct razor_merger *merger;
	struct razor_package *u, *uend, *upkgs, *s, *send, *spkgs;
	char *upool, *spool;
	int cmp;

	s = trans->system.set->packages.data;
	spkgs = trans->system.set->packages.data;
	send = trans->system.set->packages.data +
		trans->system.set->packages.size;
	spool = trans->system.set->string_pool.data;

	u = trans->upstream.set->packages.data;
	upkgs = trans->upstream.set->packages.data;
	uend = trans->upstream.set->packages.data +
		trans->upstream.set->packages.size;
	upool = trans->upstream.set->string_pool.data;

	merger = razor_merger_create(trans->system.set, trans->upstream.set);
	while (s < send || u < uend) {
		if (s < send && u < uend)
			cmp = strcmp(&spool[s->name], &upool[u->name]);
		else if (s < send)
			cmp = -1;
		else
			cmp = 1;

		if (cmp < 0) {
			if (trans->system.packages[s - spkgs] & TRANS_PACKAGE_PRESENT)
				razor_merger_add_package(merger, s);
			s++;
		} else if (cmp == 0) {
			if (trans->system.packages[s - spkgs] & TRANS_PACKAGE_PRESENT)
				razor_merger_add_package(merger, s);
			if (trans->upstream.packages[u - upkgs] & TRANS_PACKAGE_PRESENT)
				razor_merger_add_package(merger, u);

			s++;
			u++;
		} else {
			if (trans->upstream.packages[u - upkgs] & TRANS_PACKAGE_PRESENT)
				razor_merger_add_package(merger, u);
			u++;
		}
	}

	razor_transaction_destroy(trans);

	return razor_merger_finish(merger);
}

RAZOR_EXPORT void
razor_transaction_destroy(struct razor_transaction *trans)
{
	transaction_set_release(&trans->system);
	transaction_set_release(&trans->upstream);
	free(trans);
}