/*

 * 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);

	}

}

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;

}

void

razor_transaction_install_package(struct razor_transaction *trans,

				  struct razor_package *package)

{

	transaction_set_install_package(&trans->upstream, package);

	trans->changes++;

}

void

razor_transaction_remove_package(struct razor_transaction *trans,

				 struct razor_package *package)

{

	transaction_set_remove_package(&trans->system, package);

	trans->changes++;

}

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;

	}

}

const char *

razor_property_relation_to_string(struct razor_property *p)

{

	switch (p->flags & RAZOR_PROPERTY_RELATION_MASK) {

	case RAZOR_PROPERTY_LESS:

		return "<";

	case RAZOR_PROPERTY_LESS | RAZOR_PROPERTY_EQUAL:

		return "<=";

	case RAZOR_PROPERTY_EQUAL:

		return "=";

	case RAZOR_PROPERTY_GREATER | RAZOR_PROPERTY_EQUAL:

		return ">=";

	case RAZOR_PROPERTY_GREATER:

		return ">";

	default:

		return "?";

	}

}

const char *

razor_property_type_to_string(struct razor_property *p)

{

	switch (p->flags & RAZOR_PROPERTY_TYPE_MASK) {

	case RAZOR_PROPERTY_REQUIRES:

		return "requires";

	case RAZOR_PROPERTY_PROVIDES:

		return "provides";

	case RAZOR_PROPERTY_CONFLICTS:

		return "conflicts";

	case RAZOR_PROPERTY_OBSOLETES:

		return "obsoletes";

	default:

		return NULL;

	}

}

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;

		}

	}

}

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);

	}

}

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);

	}

}

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;

}

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, &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, &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;

}

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);

}

void

razor_transaction_destroy(struct razor_transaction *trans)

{

	transaction_set_release(&trans->system);

	transaction_set_release(&trans->upstream);

	free(trans);

}