/*

  * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>

  * Copyright (C) 2008  Red Hat, Inc

  * Copyright (C) 2009  J. Ali Harlow <ali@juiblex.co.uk>

  *

  * 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 "config.h"

 #include <stdlib.h>

 #include <stddef.h>

 #include <stdint.h>

 #include <stdio.h>

 #include <stdarg.h>

 #include <string.h>

 #include <sys/types.h>

 #include <sys/stat.h>

 #include <unistd.h>

 #include <fcntl.h>

 #include <errno.h>

 #include <ctype.h>

 #include <fnmatch.h>

 #include <limits.h>

 #include <assert.h>

 #ifdef MSWIN_API

 #include <windows.h>

 #endif

 #include "razor-internal.h"

 #include "razor.h"

 #ifndef O_BINARY

 #define O_BINARY	0

 #endif

 void *

 zalloc(size_t size)

 {

 	void *p;

 	p = malloc(size);

 	memset(p, 0, size);

 	return p;

 }

 struct razor_set_section_index {

 	const char *name;

 	uint32_t offset;

 	uint32_t flags;

 };

 #define MAIN(type, field) \

 	{ type, offsetof(struct razor_set, field), RAZOR_SECTION_MAIN }

 #define FILES(type, field) \

 	{ type, offsetof(struct razor_set, field), RAZOR_SECTION_FILES }

 #define DETAILS(type, field) \

 	{ type, offsetof(struct razor_set, field), RAZOR_SECTION_DETAILS }

 struct razor_set_section_index razor_sections[] = {

 	MAIN(RAZOR_STRING_POOL, string_pool),

 	MAIN(RAZOR_PACKAGES, packages),

 	MAIN(RAZOR_PROPERTIES, properties),

 	MAIN(RAZOR_PACKAGE_POOL, package_pool),

 	MAIN(RAZOR_PROPERTY_POOL, property_pool),

 	MAIN(RAZOR_PREFIX_POOL, prefix_pool),

 	FILES(RAZOR_FILES, files),

 	FILES(RAZOR_FILE_POOL, file_pool),

 	FILES(RAZOR_FILE_STRING_POOL, file_string_pool),

 	DETAILS(RAZOR_DETAILS_STRING_POOL, details_string_pool)

 };

 RAZOR_EXPORT struct razor_set *

 razor_set_create_without_root(void)

 {

 	struct razor_set *set;

 	char *empty;

 	set = zalloc(sizeof *set);

 	empty = array_add(&set->string_pool, 1);

 	*empty = '\0';

 	set->lock_fd = -1;

 	return set;

 }

 RAZOR_EXPORT struct razor_set *

 razor_set_create(void)

 {

 	struct razor_set *set;

 	struct razor_entry *e;

 	set = razor_set_create_without_root();

 	e = array_add(&set->files, sizeof *e);

 	e->name = 0;

 	e->flags = RAZOR_ENTRY_LAST;

 	e->start = 0;

 	list_set_empty(&e->packages);

 	return set;

 }

 struct razor_mapped_file {

 	struct razor_set_header *header;

 	size_t size;

 	struct razor_mapped_file *next;

 };

 RAZOR_EXPORT int

 razor_set_bind_sections(struct razor_set *set, const char *filename)

 {

 	struct razor_set_section *s, *sections;

 	struct razor_mapped_file *file;

 	const char *pool;

 	struct array *array;

 	int i, j;

 	file = zalloc(sizeof *file);

 	if (file == NULL)

 		return -1;

 	file->header = razor_file_get_contents(filename, &file->size);

 	if (!file->header) {

 		free(file);

 		return -1;

 	}

 	if (file->size < sizeof *file->header ||

 	    file->header->magic != RAZOR_MAGIC ||

 	    file->header->version != RAZOR_VERSION) {

 		razor_file_free_contents(file->header, file->size);

 		free(file);

 		return -1;

 	}

 	if (set->mapped_files == NULL) {

 		for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {

 			array = (void *) set + razor_sections[i].offset;

 			array_release(array);

 		}

 	}

 	file->next = set->mapped_files;

 	set->mapped_files = file;

 	sections = (void *) file->header + sizeof *file->header;

 	pool = (void *) sections +

 		file->header->num_sections * sizeof *sections;

 	for (i = 0; i < file->header->num_sections; i++) {

 		s = sections + i;

 		for (j = 0; j < ARRAY_SIZE(razor_sections); j++)

 			if (!strcmp(razor_sections[j].name, &pool[s->name]))

 				break;

 		if (j == ARRAY_SIZE(razor_sections))

 			continue;

 		array = (void *) set + razor_sections[j].offset;

 		array->data = (void *) file->header + s->offset;

 		array->size = s->size;

 		array->alloc = s->size;

 	}

 	return 0;

 }

 RAZOR_EXPORT struct razor_set *

 razor_set_open(const char *filename)

 {

 	struct razor_set *set;

 	set = zalloc(sizeof *set);

 	set->lock_fd = -1;

 	if (razor_set_bind_sections(set, filename)){

 		free(set);

 		return NULL;

 	}

 	return set;

 }

 int

 razor_set_aquire_lock(struct razor_set *set, const char *path, int exclusive)

 {

 	int fd;

 	assert(set != NULL);

 	if (path) {

 		fd = open(path, O_CREAT | O_RDWR | O_TRUNC | O_BINARY, 0666);

 		if (fd < 0)

 			return -1;

 	} else {

 		fd = -1;

 	}

 #ifdef MSWIN_API

 	DWORD flags = LOCKFILE_FAIL_IMMEDIATELY;

 	OVERLAPPED lock = {0};

 	if (exclusive)

 		flags |= LOCKFILE_EXCLUSIVE_LOCK;

 	if (fd >= 0 && !LockFileEx(_get_osfhandle(fd), flags, 0, 1, 0, &lock)) {

 		close(fd);

 		return -1;

 	}

 	if (set->lock_fd >= 0)

 		(void)UnlockFile(_get_osfhandle(set->lock_fd), 0, 0, 1, 0);

 #else

 	struct flock lock = {0};

 	lock.l_type = exclusive ? F_WRLCK : F_RDLCK;

 	lock.l_whence = SEEK_SET;

 	lock.l_start = 0;

 	lock.l_len = 0;

 	if (fd >= 0 && fcntl(fd, F_SETLK, &lock) < 0) {

 		close(fd);

 		return -1;

 	}

 	if (set->lock_fd >= 0) {

 		lock.l_type = F_UNLCK;

 		(void)fcntl(set->lock_fd, F_SETLK, &lock);

 	}

 #endif

 	if (set->lock_fd >= 0)

 		close(set->lock_fd);

 	set->lock_fd = fd;

 	return 0;

 }

 RAZOR_EXPORT void

 razor_set_destroy(struct razor_set *set)

 {

 	struct razor_mapped_file *file, *next;

 	struct array *array;

 	int i;

 	assert (set != NULL);

 	if (set->mapped_files == NULL) {

 		for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {

 			array = (void *) set + razor_sections[i].offset;

 			array_release(array);

 		}

 	} else {

 		for (file = set->mapped_files; file != NULL; file = next) {

 			next = file->next;

 			razor_file_free_contents(file->header, file->size);

 			free(file);

 		}

 	}

 	razor_set_aquire_lock(set, NULL, 0);

 	free(set);

 }

 RAZOR_EXPORT int

 razor_set_write_to_fd(struct razor_set *set, int fd, uint32_t section_mask)

 {

 	struct razor_set_header header;

 	struct razor_set_section sections[ARRAY_SIZE(razor_sections)];

 	struct hashtable table;

 	struct array pool, *arrays[ARRAY_SIZE(razor_sections)];

 	uint32_t offset;

 	int count, i, j;

 	static const char padding[4];

 	array_init(&pool);

 	hashtable_init(&table, &pool);

 	j = 0;

 	for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {

 		if ((razor_sections[i].flags & section_mask) == 0)

 			continue;

 		arrays[j] = (void *) set + razor_sections[i].offset;

 		sections[j].name =

 			hashtable_tokenize(&table, razor_sections[i].name);

 		j++;

 	}

 	count = j;

 	header.magic = RAZOR_MAGIC;

 	header.version = RAZOR_VERSION;

 	header.num_sections = count;

 	offset = sizeof header + count * sizeof *sections + ALIGN(pool.size, 4);

 	for (i = 0; i < count; i++) {

 		sections[i].offset = offset;

 		sections[i].size = arrays[i]->size;

 		offset += ALIGN(arrays[i]->size, 4);

 	}

 	razor_write(fd, &header, sizeof header);

 	razor_write(fd, sections, count * sizeof *sections);

 	razor_write(fd, pool.data, pool.size);

 	razor_write(fd, padding, PADDING(pool.size, 4));

 	for (i = 0; i < count; i++) {

 		razor_write(fd, arrays[i]->data, arrays[i]->size);

 		razor_write(fd, padding, PADDING(arrays[i]->size, 4));

 	}

 	array_release(&pool);

 	hashtable_release(&table);

 	return 0;

 }

 RAZOR_EXPORT int

 razor_set_write(struct razor_set *set, const char *filename, uint32_t sections)

 {

 	int fd, status;

 	fd = open(filename, O_CREAT | O_WRONLY | O_TRUNC | O_BINARY, 0666);

 	if (fd < 0)

 		return -1;

 	status = razor_set_write_to_fd(set, fd, sections);

 	if (status) {

 	    close(fd);

 	    return status;

 	}

 	return close(fd);

 }

 RAZOR_EXPORT void

 razor_build_evr(char *evr_buf, int size, const char *epoch,

 		const char *version, const char *release)

 {

 	int len;

 	if (!version || !*version) {

 		*evr_buf = '\0';

 		return;

 	}

 	if (epoch && *epoch && strcmp(epoch, "0") != 0) {

 		len = snprintf(evr_buf, size, "%s:", epoch);

 		evr_buf += len;

 		size -= len;

 	}

 	len = snprintf(evr_buf, size, "%s", version);

 	evr_buf += len;

 	size -= len;

 	if (release && *release)

 		snprintf(evr_buf, size, "-%s", release);

 }

 RAZOR_EXPORT int

 razor_versioncmp(const char *s1, const char *s2)

 {

 	const char *p1, *p2;

 	long n1, n2;

 	int res;

 	assert (s1 != NULL);

 	assert (s2 != NULL);

 	n1 = strtol(s1, (char **) &p1, 10);

 	n2 = strtol(s2, (char **) &p2, 10);

 	/* Epoch; if one but not the other has an epoch set, default

 	 * the epoch-less version to 0. */

 	res = (*p1 == ':') - (*p2 == ':');

 	if (res < 0) {

 		n1 = 0;

 		p1 = s1;

 		p2++;

 	} else if (res > 0) {

 		p1++;

 		n2 = 0;

 		p2 = s2;

 	}

 	if (n1 != n2)

 		return n1 - n2;

 	while (*p1 && *p2) {

 		if (*p1 != *p2)

 			return *p1 - *p2;

 		p1++;

 		p2++;

 		if (isdigit(*p1) && isdigit(*p2))

 			return razor_versioncmp(p1, p2);

 	}

 	return *p1 - *p2;

 }

 static const char *

 razor_package_get_details_string(struct razor_set *set,

 				 struct razor_package *package,

 				 enum razor_detail_type type)

 {

 	const char *pool;

 	switch (type) {

 	case RAZOR_DETAIL_NAME:

 		pool = set->string_pool.data;

 		return &pool[package->name];

 	case RAZOR_DETAIL_VERSION:

 		pool = set->string_pool.data;

 		return &pool[package->version];

 	case RAZOR_DETAIL_ARCH:

 		pool = set->string_pool.data;

 		return &pool[package->arch];

 	case RAZOR_DETAIL_SUMMARY:

 		pool = set->details_string_pool.data;

 		return &pool[package->summary];

 	case RAZOR_DETAIL_DESCRIPTION:

 		pool = set->details_string_pool.data;

 		return &pool[package->description];

 	case RAZOR_DETAIL_URL:

 		pool = set->details_string_pool.data;

 		return &pool[package->url];

 	case RAZOR_DETAIL_LICENSE:

 		pool = set->details_string_pool.data;

 		return &pool[package->license];

 	case RAZOR_DETAIL_PREUNPROG:

 		pool = set->string_pool.data;

 		return &pool[package->preun.program];

 	case RAZOR_DETAIL_PREUN:

 		pool = set->string_pool.data;

 		return &pool[package->preun.body];

 	case RAZOR_DETAIL_POSTUNPROG:

 		pool = set->string_pool.data;

 		return &pool[package->postun.program];

 	case RAZOR_DETAIL_POSTUN:

 		pool = set->string_pool.data;

 		return &pool[package->postun.body];

 	default:

 		fprintf(stderr, "type %u not found\n", type);

 		return NULL;

 	}

 }

 static const char *const *

 razor_package_get_details_array(struct razor_set *set,

 				struct razor_package *package,

 				enum razor_detail_type type)

 {

 	switch (type) {

 	case RAZOR_DETAIL_PREFIXES:

 		/* We don't track prefixes in packages. Install prefixes

 		 * are tracked, but we don't provide an API to get them.

 		 */

 		return NULL;

 	default:

 		fprintf(stderr, "type %u not found\n", type);

 		return NULL;

 	}

 }

 /**

  * razor_package_get_details_varg:

  * @set: a %razor_set

  * @package: a %razor_package

  * @args: a va_list of arguments to set

  **/

 void

 razor_package_get_details_varg(struct razor_set *set,

 			       struct razor_package *package,

 			       va_list args)

 {

 	int i;

 	enum razor_detail_type type;

 	const char **string;

 	const char *const **array;

 	for (i = 0;; i += 2) {

 		type = va_arg(args, enum razor_detail_type);

 		if (type == RAZOR_DETAIL_LAST)

 			break;

 		if (type == RAZOR_DETAIL_PREFIXES) {

 			array = va_arg(args, const char *const **);

 			*array = razor_package_get_details_array(set, package,

 								 type);

 		} else {

 			string = va_arg(args, const char **);

 			*string = razor_package_get_details_string(set, package,

 								   type);

 		}

 	}

 }

 /**

  * razor_package_get_details:

  * @set: a %razor_set

  * @package: a %razor_package

  *

  * Gets details about a package using a varg interface

  * The vararg must be terminated with %RAZOR_DETAIL_LAST.

  *

  * Example: razor_package_get_details (set, package,

  *				       RAZOR_DETAIL_URL, &url,

  *				       RAZOR_DETAIL_LAST);

  **/

 RAZOR_EXPORT void

 razor_package_get_details(struct razor_set *set, struct razor_package *package, ...)

 {

 	va_list args;

 	assert (set != NULL);

 	assert (package != NULL);

 	va_start(args, NULL);

 	razor_package_get_details_varg (set, package, args);

 	va_end (args);

 }

 /**

  * razor_package_remove:

  * @prev: The %razor_set before the current transaction

  * @next: The %razor_set after the current transaction is applied

  * @package: a %razor_package

  * @root: the root into which the package is currently installed

  * @install_count: the value to pass to uninstall scripts

  *

  * Removes an installed package.

  **/

 RAZOR_EXPORT int

 razor_package_remove(struct razor_set *prev, struct razor_set *next,

 		     struct razor_package *package, const char *root,

 		     int install_count)

 {

 	struct razor_file_iterator *fi;

 	struct razor_package_iterator *pi;

 	struct razor_package *p;

 	char buffer[PATH_MAX];

 	const char *name, *program, *script;

 	int retval = 0, i, count;

 	struct environment env;

 	struct list *link;

 	const char *prefix;

 	environment_init(&env);

 	link = list_first(&package->install_prefixes, &prev->prefix_pool);

 	for (i = 0; link; i++) {

 		prefix = (const char *)prev->string_pool.data + link->data;

 		sprintf(buffer, "RPM_INSTALL_PREFIX%d", i);

 		environment_add_variable(&env, buffer, prefix);

 		link = list_next(link);

 	}

 	environment_set(&env);

 	razor_package_get_details(prev, package,

 				  RAZOR_DETAIL_PREUNPROG, &program,

 				  RAZOR_DETAIL_PREUN, &script,

 				  RAZOR_DETAIL_LAST);

 	retval = razor_run_script(root, RAZOR_PROPERTY_PREUN, program, script,

 				  install_count);

 	fi = razor_file_iterator_create(prev, package, 1);

 	while (razor_file_iterator_next(fi, &name)) {

 		pi = razor_package_iterator_create_for_file(next, name);

 		count = 0;

 		while (razor_package_iterator_next(pi, &p, RAZOR_DETAIL_LAST))

 			count++;

 		razor_package_iterator_destroy(pi);

 		if (count <= 0) {

 			snprintf(buffer, sizeof buffer, "%s%s", root, name);

 			if (razor_remove(buffer) && errno != ENOENT) {

 				perror(name);

 				retval = -1;

 			}

 		}

 	}

 	razor_file_iterator_destroy(fi);

 	razor_package_get_details(prev, package,

 				  RAZOR_DETAIL_POSTUNPROG, &program,

 				  RAZOR_DETAIL_POSTUN, &script,

 				  RAZOR_DETAIL_LAST);

 	if (razor_run_script(root, RAZOR_PROPERTY_POSTUN, program, script,

 			     install_count))

 		retval = -1;

 	environment_unset(&env);

 	environment_release(&env);

 	return retval;

 }

 RAZOR_EXPORT const char *

 razor_property_relation_to_string(struct razor_property *p)

 {

 	assert (p != NULL);

 	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 "?";

 	}

 }

 RAZOR_EXPORT const char *

 razor_property_type_to_string(struct razor_property *p)

 {

 	assert (p != NULL);

 	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;

 	}

 }

 RAZOR_EXPORT struct razor_entry *

 razor_set_find_entry(struct razor_set *set,

 		     struct razor_entry *dir, const char *pattern)

 {

 	struct razor_entry *e, *subdir;

 	const char *n, *pool = set->file_string_pool.data;

 	int len;

 	assert (set != NULL);

 	assert (pattern != NULL);

 	if (dir == NULL)

 		return NULL;

 	e = dir;

 	do {

 		n = pool + e->name;

 		if (strcmp(pattern, n) == 0)

 			return e;

 		len = strlen(n);

 		if (e->start != 0 && strncmp(pattern, n, len) == 0 &&

 		    pattern[len] == '/') {

 			subdir = (struct razor_entry *) set->files.data +

 				 e->start;

 			return razor_set_find_entry(set, subdir,

 						    pattern + len + 1);

 		}

 	} while (!((e++)->flags & RAZOR_ENTRY_LAST));

 	return NULL;

 }

 static void

 list_dir(struct razor_set *set, struct razor_entry *dir,

 	 char *prefix, const char *pattern)

 {

 	struct razor_entry *e, *subdir;

 	const char *n, *pool = set->file_string_pool.data;

 	e = dir;

 	do {

 		n = pool + e->name;

 		if (pattern && pattern[0] && fnmatch(pattern, n, 0) != 0)

 			continue;

 		printf("%s/%s\n", prefix, n);

 		if (e->start) {

 			char *sub = prefix + strlen (prefix);

 			*sub = '/';

 			strcpy (sub + 1, n);

 			subdir = (struct razor_entry *) set->files.data +

 				 e->start;

 			list_dir(set, subdir, prefix, pattern);

 			*sub = '\0';

 		}

 	} while (!((e++)->flags & RAZOR_ENTRY_LAST));

 }

 RAZOR_EXPORT void

 razor_set_list_files(struct razor_set *set, const char *pattern)

 {

 	struct razor_entry *root, *e;

 	char buffer[512], *p, *base;

 	assert (set != NULL);

 	root = (struct razor_entry *) set->files.data;

 	if (pattern == NULL) {

 		p = set->file_string_pool.data;

 		e = root;

 		do {

 			if (e->start) {

 				strcpy(buffer, p + e->name);

 				list_dir(set, root + e->start, buffer, NULL);

 			}

 		} while (!((e++)->flags & RAZOR_ENTRY_LAST));

 		return;

 	}

 	strcpy(buffer, pattern);

 	e = razor_set_find_entry(set, root, buffer);

 	if (e && e->start) {

 		base = NULL;

 	} else {

 		p = strrchr(buffer, '/');

 		if (p) {

 			*p = '\0';

 			base = p + 1;

 		} else {

 			base = NULL;

 		}

 	}

 	e = razor_set_find_entry(set, root, buffer);

 	if (e && e->start)

 		list_dir(set, root + e->start, buffer, base);

 }

 RAZOR_EXPORT void

 razor_set_list_package_files(struct razor_set *set,

 			     struct razor_package *package)

 {

 	struct razor_file_iterator *fi;

 	const char *name;

 	assert (set != NULL);

 	assert (package != NULL);

 	fi = razor_file_iterator_create(set, package, 0);

 	while (razor_file_iterator_next(fi, &name))

 		printf("%s\n", name);

 	razor_file_iterator_destroy(fi);

 }

 /*

  * Package data can potentially come from two places. The so-called

  * metadata (eg., from comps.xml) and from an RPM file. We consider

  * a package which has additional data from an RPM file as "fixed".

  * If a package needs fixing, then razor_transaction_fixup_package()

  * will do so. When considering what packages to add and to remove

  * we need to take this into account since we always want to add

  * unfixed packages (otherwise we have a potential conflict between

  * the existing package data and that present in the RPM).

  */

 static int

 razor_package_is_fixed(struct razor_set *set, struct razor_package *p)

 {

 	const char *preunprog, *preun, *postunprog, *postun;

 	if (!p)

 		return 0;

 	razor_package_get_details(set, p,

 				  RAZOR_DETAIL_PREUNPROG, &preunprog,

 				  RAZOR_DETAIL_PREUN, &preun,

 				  RAZOR_DETAIL_POSTUNPROG, &postunprog,

 				  RAZOR_DETAIL_POSTUN, &postun,

 				  RAZOR_DETAIL_LAST);

 	return *preunprog || *preun || *postunprog || *postun;

 }

 RAZOR_EXPORT void

 razor_set_diff(struct razor_set *set, struct razor_set *upstream,

 	       razor_diff_callback_t callback, void *data)

 {

  	struct razor_package_iterator *pi1, *pi2;

  	struct razor_package *p1, *p2;

 	const char *name1, *name2, *version1, *version2, *arch1, *arch2;

 	int res, is_fixed1, is_fixed2;

 	assert (set != NULL);

 	assert (upstream != NULL);

 	pi1 = razor_package_iterator_create(set);

 	pi2 = razor_package_iterator_create(upstream);

 	razor_package_iterator_next(pi1, &p1,

 				    RAZOR_DETAIL_NAME, &name1,

 				    RAZOR_DETAIL_VERSION, &version1,

 				    RAZOR_DETAIL_ARCH, &arch1,

 				    RAZOR_DETAIL_LAST);

 	is_fixed1 = razor_package_is_fixed(set, p1);

 	razor_package_iterator_next(pi2, &p2,

 				    RAZOR_DETAIL_NAME, &name2,

 				    RAZOR_DETAIL_VERSION, &version2,

 				    RAZOR_DETAIL_ARCH, &arch2,

 				    RAZOR_DETAIL_LAST);

 	is_fixed2 = razor_package_is_fixed(upstream, p2);

 	while (p1 || p2) {

 		if (p1 && p2) {

 			res = strcmp(name1, name2);

 			if (res == 0)

 				res = razor_versioncmp(version1, version2);

 			if (res == 0)

 				res = is_fixed1 - is_fixed2;

 		} else {

 			res = 0;

 		}

 		if (p2 == NULL || res < 0)

 			callback(RAZOR_DIFF_ACTION_REMOVE,

 				 p1, name1, version1, arch1, data);

 		else if (p1 == NULL || res > 0)

 			callback(RAZOR_DIFF_ACTION_ADD,

 				 p2, name2, version2, arch2, data);

 		if (p1 != NULL && res <= 0) {

 			razor_package_iterator_next(pi1, &p1,

 						    RAZOR_DETAIL_NAME, &name1,

 						    RAZOR_DETAIL_VERSION, &version1,

 						    RAZOR_DETAIL_ARCH, &arch1,

 						    RAZOR_DETAIL_LAST);

 			is_fixed1 = razor_package_is_fixed(set, p1);

 		}

 		if (p2 != NULL && res >= 0) {

 			razor_package_iterator_next(pi2, &p2,

 						    RAZOR_DETAIL_NAME, &name2,

 						    RAZOR_DETAIL_VERSION, &version2,

 						    RAZOR_DETAIL_ARCH, &arch2,

 						    RAZOR_DETAIL_LAST);

 			is_fixed2 = razor_package_is_fixed(upstream, p2);

 		}

 	}

 	razor_package_iterator_destroy(pi1);

 	razor_package_iterator_destroy(pi2);

 }

 struct install_action {

 	enum razor_install_action action;

 	struct razor_package *package;

 };

 struct razor_install_iterator {

 	struct razor_set *set;

 	struct razor_set *next;

 	struct array actions;

 	struct deque *order;

 };

 static void

 add_action(enum razor_diff_action action,

 	   struct razor_package *package,

 	   const char *name,

 	   const char *version,

 	   const char *arch,

 	   void *data)

 {

 	struct razor_install_iterator *ii = data;

 	struct install_action *a;

 	a = array_add(&ii->actions, sizeof *a);

 	a->package = package;

 	switch (action) {

 	case RAZOR_DIFF_ACTION_ADD:

 		a->action = RAZOR_INSTALL_ACTION_ADD;

 		break;

 	case RAZOR_DIFF_ACTION_REMOVE:

 		a->action = RAZOR_INSTALL_ACTION_REMOVE;

 		break;

 	}

 }

 RAZOR_EXPORT struct razor_install_iterator *

 razor_set_create_install_iterator(struct razor_set *set,

 				  struct razor_set *next)

 {

 	struct razor_install_iterator *ii;

 	struct razor_property *prop;

 	/* A graph of the actions to be perfomed where

 	 * A->B means action A should follow action B.

 	 */

 	struct graph follows;

 	struct install_action *actions, *ai, *aj;

 	int i, j, count, vertex_added;

 	struct list *link;

 	struct razor_set *rs;

 	assert (set != NULL);

 	assert (next != NULL);

 	ii = zalloc(sizeof *ii);

 	ii->set = set;

 	ii->next = next;

 	razor_set_diff(set, next, add_action, ii);

 	actions = ii->actions.data;

 	count = ii->actions.size / sizeof (struct install_action);

 	graph_init(&follows);

 	for(i = 0; i < count; i++) {

 		ai = actions + i;

 		rs = ai->action == RAZOR_INSTALL_ACTION_ADD ? next : set;

 		vertex_added = 0;

 		link = list_first(&ai->package->properties, &rs->property_pool);

 		for(; link; link = list_next(link)) {

 			prop = rs->properties.data;

 			prop += link->data;

 			switch(prop->flags & RAZOR_PROPERTY_TYPE_MASK) {

 			case RAZOR_PROPERTY_REQUIRES:

 			case RAZOR_PROPERTY_CONFLICTS:

 				for(j = 0; j < count; j++) {

 					if (j == i)

 						continue;

 					aj = actions + j;

 					if (aj->package->name == prop->name) {

 						if (ai->action ==

 						    RAZOR_INSTALL_ACTION_ADD)

 							graph_add_edge(&follows,

 								       i, j);

 						else

 							graph_add_edge(&follows,

 								       j, i);

 						vertex_added++;

 					}

 				}

 				break;

 			}

 		}

 		if (ai->action == RAZOR_INSTALL_ACTION_ADD) {

 			for(j = 0; j < count; j++) {

 				if (j == i)

 					continue;

 				aj = actions + j;

 				if (aj->package == ai->package &&

 				    aj->action == RAZOR_INSTALL_ACTION_REMOVE) {

 					graph_add_edge(&follows, i, j);

 					vertex_added++;

 				}

 			}

 		}

 		if (!vertex_added)

 			graph_add_edge(&follows, i, i);

 	}

 	ii->order = graph_sort(&follows);

 	graph_release(&follows);

 	return ii;

 }

 RAZOR_EXPORT int

 razor_install_iterator_next(struct razor_install_iterator *ii,

 			    struct razor_package **package,

 			    enum razor_install_action *action,

 			    int *count)

 {

 	struct install_action *a;

 	struct razor_package_iterator *pi;

 	struct razor_package *pkg;

 	const char *removing, *name;

 	if (deque_empty(ii->order))

 		return 0;

 	a = (struct install_action *)ii->actions.data + deque_pop(ii->order);

 	*package = a->package;

 	*action = a->action;

 	*count = 0;

 	if (a->action == RAZOR_INSTALL_ACTION_REMOVE) {

 		razor_package_get_details(ii->set, a->package,

 					  RAZOR_DETAIL_NAME, &removing,

 					  RAZOR_DETAIL_LAST);

 		pi = razor_package_iterator_create(ii->next);

 		while (razor_package_iterator_next(pi, &pkg,

 						   RAZOR_DETAIL_NAME, &name,

 						   RAZOR_DETAIL_LAST)) {

 			if (!strcmp(name, removing))

 				(*count)++;

 		}

 		razor_package_iterator_destroy(pi);

 	}

 	return 1;

 }

 RAZOR_EXPORT void

 razor_install_iterator_destroy(struct razor_install_iterator *ii)

 {

 	array_release(&ii->actions);

 	deque_free(ii->order);

 	free(ii);

 }