<commit_before>/*-
 * Copyright (c) 2011-2012 <NAME> <<EMAIL>>
 * Copyright (c) 2011-2012 <NAME> <<EMAIL>>
 * Copyright (c) 2011-2012 <NAME> <<EMAIL>>
 * Copyright (c) 2013 <NAME> <<EMAIL>>
 * Copyright (c) 2013-2014 <NAME> <<EMAIL>>
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer
 *    in this position and unchanged.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/param.h>
#include <sys/mount.h>
#include <sys/types.h>

#include <archive.h>
#include <archive_entry.h>
#include <assert.h>
#include <errno.h>
#include <libutil.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <ctype.h>

#include "pkg.h"
#include "private/event.h"
#include "private/pkg.h"
#include "private/pkgdb.h"

static int pkg_jobs_find_remote_pkg(struct pkg_jobs *j, const char *pattern, match_t m,
		bool root, bool recursive, bool add_request);
static struct pkg *pkg_jobs_get_local_pkg(struct pkg_jobs *j, const char *uid, unsigned flag);
static struct pkg *pkg_jobs_get_remote_pkg(struct pkg_jobs *j, const char *uid, unsigned flag);
static int pkg_jobs_fetch(struct pkg_jobs *j);
static bool pkg_jobs_newer_than_local(struct pkg_jobs *j, struct pkg *rp, bool force);
static bool pkg_need_upgrade(struct pkg *rp, struct pkg *lp, bool recursive);
static bool new_pkg_version(struct pkg_jobs *j);
static int pkg_jobs_check_conflicts(struct pkg_jobs *j);

#define IS_DELETE(j) ((j)->type == PKG_JOBS_DEINSTALL || (j)->type == PKG_JOBS_AUTOREMOVE)

int
pkg_jobs_new(struct pkg_jobs **j, pkg_jobs_t t, struct pkgdb *db)
{
	assert(db != NULL);

	if ((*j = calloc(1, sizeof(struct pkg_jobs))) == NULL) {
		pkg_emit_errno("calloc", "pkg_jobs");
		return (EPKG_FATAL);
	}

	(*j)->db = db;
	(*j)->type = t;
	(*j)->solved = 0;
	(*j)->flags = PKG_FLAG_NONE;

	return (EPKG_OK);
}

void
pkg_jobs_set_flags(struct pkg_jobs *j, pkg_flags flags)
{
	j->flags = flags;
}

int
pkg_jobs_set_repository(struct pkg_jobs *j, const char *ident)
{
	if ((pkg_repo_find(ident)) == NULL) {
		pkg_emit_error("Unknown repository: %s", ident);
		return (EPKG_FATAL);
	}

	j->reponame = ident;

	return (EPKG_OK);
}

static void
pkg_jobs_pattern_free(struct job_pattern *jp)
{
	if (jp->pattern != NULL)
		free(jp->pattern);
	if (jp->path != NULL)
		free(jp->path);

	free(jp);
}

static void
pkg_jobs_provide_free(struct pkg_job_provide *pr)
{
	struct pkg_job_provide *cur, *tmp;

	DL_FOREACH_SAFE(pr, cur, tmp) {
		free (cur);
	}
}

static void
pkg_jobs_replacement_free(struct pkg_job_replace *r)
{
	free(r->new_uid);
	free(r->old_uid);
	free(r);
}

void
pkg_jobs_free(struct pkg_jobs *j)
{
	struct pkg_job_request *req, *tmp;
	struct pkg_job_universe_item *un, *untmp, *cur, *curtmp;


	if (j == NULL)
		return;

	HASH_ITER(hh, j->request_add, req, tmp) {
		HASH_DEL(j->request_add, req);
		free(req);
	}
	HASH_ITER(hh, j->request_delete, req, tmp) {
		HASH_DEL(j->request_delete, req);
		free(req);
	}
	HASH_ITER(hh, j->universe, un, untmp) {
		HASH_DEL(j->universe, un);

		if (un->reinstall != NULL)
			pkg_free(un->reinstall);

		LL_FOREACH_SAFE(un, cur, curtmp) {
			pkg_free(cur->pkg);
			free(cur);
		}
	}
	HASH_FREE(j->seen, free);
	HASH_FREE(j->patterns, pkg_jobs_pattern_free);
	HASH_FREE(j->provides, pkg_jobs_provide_free);
	LL_FREE(j->jobs, free);
	LL_FREE(j->uid_replaces, pkg_jobs_replacement_free);

	free(j);
}

static bool
pkg_jobs_maybe_match_file(struct job_pattern *jp, const char *pattern)
{
	const char *dot_pos;
	char *pkg_path;

	assert(jp != NULL);
	assert(pattern != NULL);

	dot_pos = strrchr(pattern, '.');
	if (dot_pos != NULL) {
		/*
		 * Compare suffix with .txz or .tbz
		 */
		dot_pos ++;
		if (strcmp(dot_pos, "txz") == 0 ||
			strcmp(dot_pos, "tbz") == 0 ||
			strcmp(dot_pos, "tgz") == 0 ||
			strcmp(dot_pos, "tar") == 0) {
			if ((pkg_path = realpath(pattern, NULL)) != NULL) {
				/* Dot pos is one character after the dot */
				int len = dot_pos - pattern;

				jp->is_file = true;
				jp->path = pkg_path;
				jp->pattern = malloc(len);
				strlcpy(jp->pattern, pattern, len);

				return (true);
			}
		}
	}
	else if (strcmp(pattern, "-") == 0) {
		/*
		 * Read package from stdin
		 */
		jp->is_file = true;
		jp->path = strdup(pattern);
		jp->pattern = strdup(pattern);
	}

	return (false);
}

int
pkg_jobs_add(struct pkg_jobs *j, match_t match, char **argv, int argc)
{
	struct job_pattern *jp;
	int i = 0;

	if (j->solved) {
		pkg_emit_error("The job has already been solved. "
		    "Impossible to append new elements");
		return (EPKG_FATAL);
	}

	for (i = 0; i < argc; i++) {
		jp = calloc(1, sizeof(struct job_pattern));
		if (!pkg_jobs_maybe_match_file(jp, argv[i])) {
			jp->pattern = strdup(argv[i]);
			jp->match = match;
		}
		HASH_ADD_KEYPTR(hh, j->patterns, jp->pattern, strlen(jp->pattern), jp);
	}

	if (argc == 0 && match == MATCH_ALL) {
		jp = calloc(1, sizeof(struct job_pattern));
		jp->pattern = NULL;
		jp->match = match;
		HASH_ADD_KEYPTR(hh, j->patterns, "all", 3, jp);
	}

	return (EPKG_OK);
}

bool
pkg_jobs_iter(struct pkg_jobs *jobs, void **iter,
				struct pkg **new, struct pkg **old,
				int *type)
{
	struct pkg_solved *s;
	assert(iter != NULL);
	if (jobs->jobs == NULL) {
		return (false);
	}
	if (*iter == NULL) {
		s = jobs->jobs;
	}
	else if (*iter == jobs->jobs) {
		return (false);
	}
	else {
		s = *iter;
	}
	*new = s->items[0]->pkg;
	*old = s->items[1] ? s->items[1]->pkg : NULL;
	*type = s->type;
	*iter = s->next ? s->next : jobs->jobs;
	return (true);
}

static void
pkg_jobs_add_req(struct pkg_jobs *j, const char *uid,
		struct pkg_job_universe_item *item)
{
	struct pkg_job_request *req, *test, **head;

	if (!IS_DELETE(j))
		head = &j->request_add;
	else
		head = &j->request_delete;

	HASH_FIND(hh, *head, uid, strlen(uid), test);

	if (test != NULL)
		return;

	req = calloc(1, sizeof (struct pkg_job_request));
	if (req == NULL) {
		pkg_emit_errno("malloc", "struct pkg_job_request");
		return;
	}
	req->item = item;

	HASH_ADD_KEYPTR(hh, *head, uid, strlen(uid), req);
}

enum pkg_priority_update_type {
	PKG_PRIORITY_UPDATE_REQUEST = 0,
	PKG_PRIORITY_UPDATE_UNIVERSE,
	PKG_PRIORITY_UPDATE_CONFLICT,
	PKG_PRIORITY_UPDATE_DELETE
};

#define RECURSION_LIMIT 1024

static void
pkg_jobs_update_universe_priority(struct pkg_jobs *j,
		struct pkg_job_universe_item *item, int priority,
		enum pkg_priority_update_type type)
{
	const char *uid, *digest;
	struct pkg_dep *d = NULL;
	struct pkg_conflict *c = NULL;
	struct pkg_job_universe_item *found, *cur, *it;
	const char *is_local;
	int maxpri;

	int (*deps_func)(const struct pkg *pkg, struct pkg_dep **d);
	int (*rdeps_func)(const struct pkg *pkg, struct pkg_dep **d);

	if (priority > RECURSION_LIMIT) {
		pkg_debug(1, "recursion limit has been reached, something is bad"
					" with dependencies/conflicts graph");
		return;
	}
	else if (priority + 10 > RECURSION_LIMIT) {
		pkg_get(item->pkg, PKG_UNIQUEID, &uid);
		pkg_debug(2, "approaching recursion limit at %d, while processing of"
					" package %s", priority, uid);
	}

	LL_FOREACH(item, it) {

		pkg_get(it->pkg, PKG_UNIQUEID, &uid, PKG_DIGEST, &digest);
		if ((item->next != NULL || item->prev != NULL) &&
				it->pkg->type != PKG_INSTALLED &&
				(type == PKG_PRIORITY_UPDATE_CONFLICT ||
				 type == PKG_PRIORITY_UPDATE_DELETE)) {
			/*
			 * We do not update priority of a remote part of conflict, as we know
			 * that remote packages should not contain conflicts (they should be
			 * resolved in request prior to calling of this function)
			 */
			pkg_debug(4, "skip update priority for %s-%s", uid, digest);
			continue;
		}
		if (it->priority > priority)
			continue;

		is_local = it->pkg->type == PKG_INSTALLED ? "local" : "remote";
		pkg_debug(2, "universe: update %s priority of %s(%s): %d -> %d, reason: %d",
				is_local, uid, digest, it->priority, priority, type);
		it->priority = priority;

		if (type == PKG_PRIORITY_UPDATE_DELETE) {
			/*
			 * For delete requests we inverse deps and rdeps logic
			 */
			deps_func = pkg_rdeps;
			rdeps_func = pkg_deps;
		}
		else {
			deps_func = pkg_deps;
			rdeps_func = pkg_rdeps;
		}

		while (deps_func(it->pkg, &d) == EPKG_OK) {
			HASH_FIND_STR(j->universe, d->uid, found);
			if (found != NULL) {
				LL_FOREACH(found, cur) {
					if (cur->priority < priority + 1)
						pkg_jobs_update_universe_priority(j, cur,
								priority + 1, type);
				}
			}
		}

		d = NULL;
		maxpri = priority;
		while (rdeps_func(it->pkg, &d) == EPKG_OK) {
			HASH_FIND_STR(j->universe, d->uid, found);
			if (found != NULL) {
				LL_FOREACH(found, cur) {
					if (cur->priority >= maxpri) {
						maxpri = cur->priority + 1;
					}
				}
			}
		}
		if (maxpri != priority) {
			pkg_jobs_update_universe_priority(j, it,
					maxpri, type);
			return;
		}
		if (it->pkg->type != PKG_INSTALLED) {
			while (pkg_conflicts(it->pkg, &c) == EPKG_OK) {
				HASH_FIND_STR(j->universe, pkg_conflict_uniqueid(c), found);
				if (found != NULL) {
					LL_FOREACH(found, cur) {
						if (cur->pkg->type == PKG_INSTALLED) {
							/*
							 * Move delete requests to be done before installing
							 */
							if (cur->priority <= it->priority)
								pkg_jobs_update_universe_priority(j, cur,
									it->priority + 1, PKG_PRIORITY_UPDATE_CONFLICT);
						}
					}
				}
			}
		}
	}
}

static void
pkg_jobs_update_conflict_priority(struct pkg_jobs *j, struct pkg_solved *req)
{
	struct pkg_conflict *c = NULL;
	struct pkg *lp = req->items[1]->pkg;
	struct pkg_job_universe_item *found, *cur, *rit = NULL;

	while (pkg_conflicts(lp, &c) == EPKG_OK) {
		rit = NULL;
		HASH_FIND_STR(j->universe, pkg_conflict_uniqueid(c), found);
		assert(found != NULL);

		LL_FOREACH(found, cur) {
			if (cur->pkg->type != PKG_INSTALLED) {
				rit = cur;
				break;
			}
		}

		assert(rit != NULL);
		if (rit->priority >= req->items[1]->priority) {
			pkg_jobs_update_universe_priority(j, req->items[1],
					rit->priority + 1, PKG_PRIORITY_UPDATE_CONFLICT);
			/*
			 * Update priorities for a remote part as well
			 */
			pkg_jobs_update_universe_priority(j, req->items[0],
					req->items[0]->priority, PKG_PRIORITY_UPDATE_REQUEST);
		}
	}
}

static int
pkg_jobs_set_request_priority(struct pkg_jobs *j, struct pkg_solved *req)
{
	struct pkg_solved *treq;
	const char *uid;

	if (req->type == PKG_SOLVED_UPGRADE
			&& req->items[1]->pkg->conflicts != NULL) {
		/*
		 * We have an upgrade request that has some conflicting packages, therefore
		 * update priorities of local packages and try to update priorities of remote ones
		 */
		if (req->items[0]->priority == 0)
			pkg_jobs_update_conflict_priority(j, req);

		if (req->items[1]->priority > req->items[0]->priority &&
				!req->already_deleted) {
			/*
			 * Split conflicting upgrade request into delete -> upgrade request
			 */
			treq = calloc(1, sizeof(struct pkg_solved));
			if (treq == NULL) {
				pkg_emit_errno("calloc", "pkg_solved");
				return (EPKG_FATAL);
			}

			treq->type = PKG_SOLVED_UPGRADE_REMOVE;
			treq->items[0] = req->items[1];
			DL_APPEND(j->jobs, treq);
			j->count ++;
			req->already_deleted = true;
			pkg_get(treq->items[0]->pkg, PKG_UNIQUEID, &uid);
			pkg_debug(2, "split upgrade request for %s", uid);
			return (EPKG_CONFLICT);
		}
	}
	else if (req->type == PKG_SOLVED_DELETE) {
		if (req->items[0]->priority == 0)
			pkg_jobs_update_universe_priority(j, req->items[0], 0,
					PKG_PRIORITY_UPDATE_DELETE);
	}
	else {
		if (req->items[0]->priority == 0)
			pkg_jobs_update_universe_priority(j, req->items[0], 0,
					PKG_PRIORITY_UPDATE_REQUEST);
	}

	return (EPKG_OK);
}

static int
pkg_jobs_sort_priority(struct pkg_solved *r1, struct pkg_solved *r2)
{
	if (r1->items[0]->priority == r2->items[0]->priority) {
		if (r1->type == PKG_SOLVED_DELETE && r2->type != PKG_SOLVED_DELETE)
			return (-1);
		else if (r2->type == PKG_SOLVED_DELETE && r1->type != PKG_SOLVED_DELETE)
			return (1);

		return (0);
	}
	return (r2->items[0]->priority - r1->items[0]->priority);
}

static void
pkg_jobs_set_priorities(struct pkg_jobs *j)
{
	struct pkg_solved *req;

iter_again:
	LL_FOREACH(j->jobs, req) {
		req->items[0]->priority = 0;
		if (req->items[1] != NULL)
			req->items[1]->priority = 0;
	}
	LL_FOREACH(j->jobs, req) {
		if (pkg_jobs_set_request_priority(j, req) == EPKG_CONFLICT)
			goto iter_again;
	}

	DL_SORT(j->jobs, pkg_jobs_sort_priority);
}

#undef PRIORITY_CAN_UPDATE


/**
 * Check whether a package is in the universe already or add it
 * @return item or NULL
 */
static int
pkg_jobs_handle_pkg_universe(struct pkg_jobs *j, struct pkg *pkg,
		struct pkg_job_universe_item **found)
{
	struct pkg_job_universe_item *item, *cur, *tmp = NULL;
	const char *uid, *digest, *version, *name;
	struct pkg_job_seen *seen;

	pkg_get(pkg, PKG_UNIQUEID, &uid, PKG_DIGEST, &digest,
			PKG_VERSION, &version, PKG_NAME, &name);
	if (digest == NULL) {
		pkg_debug(3, "no digest found for package %s (%s-%s)", uid,
				name, version);
		if (pkg_checksum_calculate(pkg, j->db) != EPKG_OK) {
			*found = NULL;
			return (EPKG_FATAL);
		}
		pkg_get(pkg, PKG_DIGEST, &digest);
	}

	HASH_FIND_STR(j->seen, digest, seen);
	if (seen != NULL) {
		cur = seen->un;
		if (found != NULL)
			*found = seen->un;

		return (EPKG_END);
	}

	pkg_debug(2, "universe: add new %s pkg: %s, (%s-%s:%s)",
				(pkg->type == PKG_INSTALLED ? "local" : "remote"), uid,
				name, version, digest);

	item = calloc(1, sizeof (struct pkg_job_universe_item));
	if (item == NULL) {
		pkg_emit_errno("pkg_jobs_pkg_insert_universe", "calloc: struct pkg_job_universe_item");
		return (EPKG_FATAL);
	}

	item->pkg = pkg;

	HASH_FIND_STR(j->universe, uid, tmp);
	if (tmp == NULL) {
		HASH_ADD_KEYPTR(hh, j->universe, uid, strlen(uid), item);
	}

	DL_APPEND(tmp, item);

	seen = calloc(1, sizeof(struct pkg_job_seen));
	seen->digest = digest;
	seen->un = item;
	HASH_ADD_KEYPTR(hh, j->seen, seen->digest, strlen(seen->digest), seen);

	j->total++;

	if (found != NULL)
		*found = item;

	return (EPKG_OK);
}

static int
pkg_jobs_add_universe(struct pkg_jobs *j, struct pkg *pkg,
		bool recursive, bool deps_only, struct pkg_job_universe_item **result)
{
	struct pkg_dep *d = NULL;
	struct pkg_conflict *c = NULL;
	struct pkg *npkg, *rpkg;
	struct pkg_job_universe_item *unit;
	struct pkg_shlib *shlib = NULL;
	struct pkgdb_it *it;
	struct pkg_job_provide *pr, *prhead;
	struct pkg_job_seen *seen;
	int ret;
	bool automatic = false;
	const char *uid, *name, *digest;
	unsigned flags = PKG_LOAD_BASIC|PKG_LOAD_OPTIONS|PKG_LOAD_DEPS|
			PKG_LOAD_SHLIBS_REQUIRED|PKG_LOAD_SHLIBS_PROVIDED|
			PKG_LOAD_ANNOTATIONS|PKG_LOAD_CONFLICTS;

	if (!deps_only) {
		/* Add the requested package itself */
		ret = pkg_jobs_handle_pkg_universe(j, pkg, result);

		if (ret == EPKG_END)
			return (EPKG_OK);
		else if (ret == EPKG_OK && !recursive)
			return (EPKG_OK);
		else if (ret != EPKG_OK)
			return (EPKG_FATAL);
	}

	/* Go through all depends */
	while (pkg_deps(pkg, &d) == EPKG_OK) {
		/* XXX: this assumption can be applied only for the current plain dependencies */
		HASH_FIND_STR(j->universe, d->uid, unit);
		if (unit != NULL) {
			continue;
		}

		rpkg = NULL;
		npkg = pkg_jobs_get_local_pkg(j, d->uid, 0);
		if (npkg == NULL && !IS_DELETE(j)) {
			/*
			 * We have a package installed, but its dependencies are not,
			 * try to search a remote dependency
			 */
			pkg_get(pkg, PKG_NAME, &name);
			pkg_debug(1, "dependency %s of local package %s is not installed",
					pkg_dep_get(d, PKG_DEP_NAME), name);
			npkg = pkg_jobs_get_remote_pkg(j, d->uid, 0);
			if (npkg == NULL) {
				/* Cannot continue */
				pkg_emit_error("Missing dependency matching '%s'",
						pkg_dep_get(d, PKG_DEP_NAME));
				if ((j->flags & PKG_FLAG_FORCE_MISSING) == PKG_FLAG_FORCE_MISSING) {
					continue;
				}
				return (EPKG_FATAL);
			}
		}
		else if (npkg == NULL) {
			/* For delete jobs we don't care about uninstalled dependencies */
			continue;
		}
		else if (!IS_DELETE(j) && npkg->type == PKG_INSTALLED) {
			/* For upgrade jobs we need to ensure that we do not have a newer version */
			rpkg = pkg_jobs_get_remote_pkg(j, d->uid, 0);
			if (rpkg != NULL) {
				if (!pkg_need_upgrade(rpkg, npkg, false)) {
					/*
					 * We can do it safely here, as rpkg is definitely NOT in
					 * the universe
					 */
					pkg_free(rpkg);
					rpkg = NULL;
				}
			}
		}

		if (pkg_jobs_add_universe(j, npkg, recursive, false, NULL) != EPKG_OK)
			return (EPKG_FATAL);
		if (rpkg != NULL) {
			/* Save automatic flag */
			pkg_get(npkg, PKG_AUTOMATIC, &automatic);
			pkg_set(rpkg, PKG_AUTOMATIC, automatic);

			if (pkg_jobs_add_universe(j, rpkg, recursive, false, NULL) != EPKG_OK)
				return (EPKG_FATAL);
		}
	}

	/* Go through all rdeps */
	d = NULL;
	while (pkg_rdeps(pkg, &d) == EPKG_OK) {
		/* XXX: this assumption can be applied only for the current plain dependencies */
		HASH_FIND_STR(j->universe, d->uid, unit);
		if (unit != NULL)
			continue;

		npkg = pkg_jobs_get_local_pkg(j, d->uid, 0);
		if (npkg != NULL) {
			/* Do not bother about remote deps */
			if (pkg_jobs_add_universe(j, npkg, recursive, false, NULL) != EPKG_OK)
				return (EPKG_FATAL);
		}
	}

	if (!IS_DELETE(j)) {
		/* Examine conflicts */
		while (pkg_conflicts(pkg, &c) == EPKG_OK) {
			/* XXX: this assumption can be applied only for the current plain dependencies */
			HASH_FIND_STR(j->universe, pkg_conflict_uniqueid(c), unit);
			if (unit != NULL)
				continue;

			/* Check local and remote conflicts */
			if (pkg->type == PKG_INSTALLED) {
				/* Installed packages can conflict with remote ones */
				npkg = pkg_jobs_get_remote_pkg(j, pkg_conflict_uniqueid(c), 0);
				if (npkg == NULL)
					continue;

				if (pkg_jobs_add_universe(j, npkg, recursive, false, NULL) != EPKG_OK)
					return (EPKG_FATAL);
			}
			else {
				/* Remote packages can conflict with remote and local */
				npkg = pkg_jobs_get_local_pkg(j, pkg_conflict_uniqueid(c), 0);
				if (npkg == NULL)
					continue;

				if (pkg_jobs_add_universe(j, npkg, recursive, false, NULL) != EPKG_OK)
					return (EPKG_FATAL);

				if (c->type != PKG_CONFLICT_REMOTE_LOCAL) {
					npkg = pkg_jobs_get_remote_pkg(j, pkg_conflict_uniqueid(c), 0);
					if (npkg == NULL)
						continue;

					if (pkg_jobs_add_universe(j, npkg, recursive, false, NULL)
							!= EPKG_OK)
						return (EPKG_FATAL);
				}
			}
		}
	}

	/* For remote packages we should also handle shlib deps */
	if (pkg->type != PKG_INSTALLED && !IS_DELETE(j)) {
		while (pkg_shlibs_required(pkg, &shlib) == EPKG_OK) {
			HASH_FIND_STR(j->provides, pkg_shlib_name(shlib), pr);
			if (pr != NULL)
				continue;

			/* Not found, search in the repos */
			it = pkgdb_repo_shlib_provide(j->db, pkg_shlib_name(shlib), j->reponame);
			if (it != NULL) {
				rpkg = NULL;
				prhead = NULL;
				while (pkgdb_it_next(it, &rpkg, flags) == EPKG_OK) {
					pkg_get(rpkg, PKG_DIGEST, &digest, PKG_UNIQUEID, &uid);
					/* Check for local packages */
					HASH_FIND_STR(j->universe, uid, unit);
					if (unit != NULL) {
						if (pkg_need_upgrade (rpkg, unit->pkg, false)) {
							/* Remote provide is newer, so we can add it */
							if (pkg_jobs_add_universe(j, rpkg, recursive, false,
																&unit) != EPKG_OK)
								return (EPKG_FATAL);

							rpkg = NULL;
						}
					}
					else {
						/* Maybe local package has just been not added */
						npkg = pkg_jobs_get_local_pkg(j, uid, 0);
						if (npkg != NULL) {
							if (pkg_jobs_add_universe(j, npkg, recursive, false,
									&unit) != EPKG_OK)
								return (EPKG_FATAL);
							if (pkg_need_upgrade (rpkg, npkg, false)) {
								/* Remote provide is newer, so we can add it */
								if (pkg_jobs_add_universe(j, rpkg, recursive, false,
										&unit) != EPKG_OK)
									return (EPKG_FATAL);
							}
						}
					}
					/* Skip seen packages */
					if (unit == NULL) {
						if (digest == NULL) {
							pkg_debug(3, "no digest found for package %s", uid);
							if (pkg_checksum_calculate(pkg, j->db) != EPKG_OK) {
								return (EPKG_FATAL);
							}
							pkg_get(pkg, PKG_DIGEST, &digest);
						}
						HASH_FIND_STR(j->seen, digest, seen);
						if (seen == NULL) {
							pkg_jobs_add_universe(j, rpkg, recursive, false,
									&unit);

							/* Reset package to avoid freeing */
							rpkg = NULL;
						}
						else {
							unit = seen->un;
						}
					}

					pr = calloc (1, sizeof (*pr));
					if (pr == NULL) {
						pkg_emit_errno("pkg_jobs_add_universe", "calloc: "
								"struct pkg_job_provide");
						return (EPKG_FATAL);
					}
					pr->un = unit;
					pr->provide = pkg_shlib_name(shlib);
					if (prhead == NULL) {
						DL_APPEND(prhead, pr);
						HASH_ADD_KEYPTR(hh, j->provides, pr->provide,
								strlen(pr->provide), prhead);
					}
					else {
						DL_APPEND(prhead, pr);
					}
				}
				pkgdb_it_free(it);
				if (prhead == NULL) {
					pkg_get(pkg, PKG_NAME, &name);
					pkg_debug(1, "cannot find packages that provide %s required for %s",
							pkg_shlib_name(shlib), name);
					/*
					 * XXX: this is not normal but it is very common for the existing
					 * repos, hence we just ignore this stale dependency
					 */
				}
			}
		}
	}

	return (EPKG_OK);
}

/**
 * Test whether package specified is automatic with all its rdeps
 * @param j
 * @param p
 * @return
 */
static bool
pkg_jobs_test_automatic(struct pkg_jobs *j, struct pkg *p)
{
	struct pkg_dep *d = NULL;
	struct pkg_job_universe_item *unit;
	struct pkg *npkg;
	bool ret = true;
	bool automatic;

	while (pkg_rdeps(p, &d) == EPKG_OK && ret) {
		HASH_FIND_STR(j->universe, d->uid, unit);
		if (unit != NULL) {
			pkg_get(unit->pkg, PKG_AUTOMATIC, &automatic);
			if (!automatic) {
				return (false);
			}
			npkg = unit->pkg;
		}
		else {
			npkg = pkg_jobs_get_local_pkg(j, d->uid,
					PKG_LOAD_BASIC|PKG_LOAD_RDEPS|PKG_LOAD_ANNOTATIONS);
			pkg_get(npkg, PKG_AUTOMATIC, &automatic);
			if (npkg == NULL)
				return (false);
			if (!automatic) {
				/*
				 * Safe to free, as d->uid is not in the universe
				 */
				pkg_free(npkg);
				return (false);
			}
			if (pkg_jobs_add_universe(j, npkg, false, false, NULL) != EPKG_OK)
				return (false);
		}

		ret = pkg_jobs_test_automatic(j, npkg);
	}

	return (ret);
}



static bool
new_pkg_version(struct pkg_jobs *j)
{
	struct pkg *p;
	const char *uid = "pkg~ports-mgmt/pkg";
	pkg_flags old_flags;
	bool ret = false;

	/* Disable -f for pkg self-check, and restore at end. */
	old_flags = j->flags;
	j->flags &= ~(PKG_FLAG_FORCE|PKG_FLAG_RECURSIVE);

	/* determine local pkgng */
	p = pkg_jobs_get_local_pkg(j, uid, PKG_LOAD_BASIC|PKG_LOAD_ANNOTATIONS);

	if (p == NULL) {
		uid = "pkg~ports-mgmt/pkg-devel";
		p = pkg_jobs_get_local_pkg(j, uid, PKG_LOAD_BASIC|PKG_LOAD_ANNOTATIONS);
	}

	/* you are using git version skip */
	if (p == NULL) {
		ret = false;
		goto end;
	}

	pkg_jobs_add_universe(j, p, true, false, NULL);

	/* Use maximum priority for pkg */
	if (pkg_jobs_find_remote_pkg(j, uid, MATCH_EXACT, false, true, true) == EPKG_OK) {
		ret = true;
		goto end;
	}

end:
	j->flags = old_flags;

	return (ret);
}

static int
pkg_jobs_process_remote_pkg(struct pkg_jobs *j, struct pkg *p,
		bool root, bool force, bool recursive,
		struct pkg_job_universe_item **unit,
		bool add_request)
{
	struct pkg *p1;
	struct pkg_job_universe_item *jit;
	struct pkg_job_seen *seen;
	struct pkg_job_request *jreq;
	int rc = EPKG_FATAL;
	const char *uid, *digest;

	p1 = NULL;
	pkg_get(p, PKG_UNIQUEID, &uid, PKG_DIGEST, &digest);

	if (digest == NULL) {
		if (pkg_checksum_calculate(p, j->db) != EPKG_OK) {
			return (EPKG_FATAL);
		}
		pkg_get(p, PKG_DIGEST, &digest);
	}
	HASH_FIND_STR(j->seen, digest, seen);
	if (seen != NULL) {
		/* We have already added exactly the same package to the universe */
		pkg_debug(3, "already seen package %s-%s(%c) in the universe, do not add it again",
				uid, digest,
				seen->un->pkg->type == PKG_INSTALLED ? 'l' : 'r');
		if (seen->un->pkg->type != p->type && !force) {
			/* Remote package is the same as local */
			return (EPKG_INSTALLED);
		}
		else {
			/* However, we may want to add it to the job request */
			HASH_FIND_STR(j->request_add, uid, jreq);
			if (jreq == NULL)
				pkg_jobs_add_req(j, uid, seen->un);
			if (force)
				seen->un->reinstall = p;
		}
		return (EPKG_OK);
	}
	HASH_FIND_STR(j->universe, uid, jit);
	if (jit != NULL) {
		/* We have a more recent package */
		if (!force && !pkg_need_upgrade(p, jit->pkg, false)) {
			/*
			 * We can have package from another repo in the
			 * universe, but if it is older than this one we just
			 * do not add it.
			 */
			if (jit->pkg->type == PKG_INSTALLED) {
				return (EPKG_INSTALLED);
			}
			else {
				pkg_debug(3, "already added newer package %s to the universe, do not add it again",
								uid);
				if (add_request)
					pkg_jobs_add_req(j, uid, jit);
				return (EPKG_OK);
			}
		}
		/*
		 * XXX: what happens if we have multirepo enabled and we add
		 * two packages from different repos?
		 */
	}
	else {
		if (j->type != PKG_JOBS_FETCH) {
			if (!pkg_jobs_newer_than_local(j, p, force)) {
				return (EPKG_INSTALLED);
			}
		}
	}

	rc = EPKG_OK;
	p->direct = root;
	/* Add a package to request chain and populate universe */
	rc = pkg_jobs_add_universe(j, p, recursive, false, &jit);
	if (add_request)
		pkg_jobs_add_req(j, uid, jit);

	if (unit != NULL)
		*unit = jit;

	return (rc);
}

static void
pkg_jobs_change_uid(struct pkg_jobs *j, struct pkg_job_universe_item *unit,
	const char *new_uid, size_t uidlen, bool update_rdeps)
{
	struct pkg_dep *rd = NULL, *d = NULL;
	struct pkg_job_universe_item *found;
	struct pkg *lp;
	const char *old_uid;
	struct pkg_job_replace *replacement;

	pkg_get(unit->pkg, PKG_UNIQUEID, &old_uid);

	if (update_rdeps) {
		/* For all rdeps update deps accordingly */
		while (pkg_rdeps(unit->pkg, &rd) == EPKG_OK) {
			HASH_FIND(hh, j->universe, rd->uid, strlen(rd->uid), found);
			if (found == NULL) {
				lp = pkg_jobs_get_local_pkg(j, rd->uid, 0);
				pkg_jobs_add_universe(j, lp, true, false, &found);
			}

			if (found != NULL) {
				while (pkg_deps(found->pkg, &d) == EPKG_OK) {
					if (strcmp(d->uid, old_uid) == 0) {
						free(d->uid);
						d->uid = strdup(new_uid);
					}
				}
			}
		}
	}

	replacement = calloc(1, sizeof(*replacement));
	if (replacement != NULL) {
		replacement->old_uid = strdup(old_uid);
		replacement->new_uid = strdup(new_uid);
		LL_PREPEND(j->uid_replaces, replacement);
	}

	HASH_DELETE(hh, j->universe, unit);
	pkg_set(unit->pkg, PKG_UNIQUEID, new_uid);
	HASH_FIND(hh, j->universe, new_uid, uidlen, found);
	if (found != NULL)
		DL_APPEND(found, unit);
	else
		HASH_ADD_KEYPTR(hh, j->universe, new_uid, uidlen, unit);

}

static int
pkg_jobs_try_remote_candidate(struct pkg_jobs *j, const char *pattern,
		const char *uid, match_t m)
{
	struct pkg *p = NULL;
	struct pkgdb_it *it;
	unsigned flags = PKG_LOAD_BASIC|PKG_LOAD_OPTIONS|PKG_LOAD_DEPS|
				PKG_LOAD_SHLIBS_REQUIRED|PKG_LOAD_SHLIBS_PROVIDED|
				PKG_LOAD_ANNOTATIONS|PKG_LOAD_CONFLICTS;
	int rc = EPKG_FATAL;
	struct sbuf *qmsg;
	const char *fuid;
	struct pkg_job_universe_item *unit;

	if ((it = pkgdb_repo_query(j->db, pattern, m, j->reponame)) == NULL)
		return (EPKG_FATAL);

	qmsg = sbuf_new_auto();

	while (it != NULL && pkgdb_it_next(it, &p, flags) == EPKG_OK) {
		pkg_get(p, PKG_UNIQUEID, &fuid);
		sbuf_printf(qmsg, "%s has no direct installation candidates, change it to "
				"%s [Y/n]: ", uid, fuid);
		sbuf_finish(qmsg);
		if (pkg_emit_query_yesno(true, sbuf_data(qmsg))) {
			/* Change the origin of the local package */
			HASH_FIND(hh, j->universe, uid, strlen(uid), unit);
			if (unit != NULL)
				pkg_jobs_change_uid(j, unit, fuid, strlen(fuid), false);

			rc = pkg_jobs_process_remote_pkg(j, p, true, false, true,
				NULL, true);
			if (rc == EPKG_OK) {
				/* Avoid freeing */
				p = NULL;
			}
			break;
		}
		sbuf_reset(qmsg);
	}


	if (p != NULL)
		pkg_free(p);

	sbuf_free(qmsg);
	pkgdb_it_free(it);

	return (rc);
}

static int
pkg_jobs_guess_upgrade_candidate(struct pkg_jobs *j, const char *pattern)
{

	int rc = EPKG_FATAL;
	const char *pos, *opattern = pattern;
	char *cpy;
	size_t len, olen;

	/* First of all, try to search a package with the same name */
	pos = strchr(pattern, '/');
	if (pos != NULL && pos[1] != '\0') {
		if (pkg_jobs_try_remote_candidate(j, pos + 1, opattern, MATCH_EXACT) == EPKG_OK)
			return (EPKG_OK);
		pos ++;
		pattern = pos;
	}
	else {
		pos = pattern;
	}

	/* Figure, if we have any numbers at the end of the package */
	olen = strlen(pos);
	len = olen;
	while (len > 0) {
		if (isdigit(pos[len - 1]) || pos[len - 1] == '.')
			len --;
		else
			break;
	}

	if (olen != len) {
		/* Try exact pattern without numbers */
		cpy = malloc(len + 1);
		strlcpy(cpy, pos, len + 1);
		if (pkg_jobs_try_remote_candidate(j, cpy, opattern, MATCH_EXACT) != EPKG_OK) {
			free(cpy);
			cpy = sqlite3_mprintf(" WHERE name REGEXP ('^' || %.*Q || '[0-9.]*$')",
					len, pos);
			if (pkg_jobs_try_remote_candidate(j, cpy, opattern, MATCH_CONDITION)
					== EPKG_OK)
				rc = EPKG_OK;
			sqlite3_free(cpy);
		}
		else {
			free(cpy);
			rc = EPKG_OK;
		}
	}

	return (rc);
}

static int
pkg_jobs_find_remote_pkg(struct pkg_jobs *j, const char *pattern,
		match_t m, bool root, bool recursive, bool add_request)
{
	struct pkg *p = NULL;
	struct pkgdb_it *it;
	bool force = false, found = false;
	int rc = EPKG_FATAL;
	struct pkg_dep *rdep = NULL;
	unsigned flags = PKG_LOAD_BASIC|PKG_LOAD_OPTIONS|PKG_LOAD_DEPS|
			PKG_LOAD_SHLIBS_REQUIRED|PKG_LOAD_SHLIBS_PROVIDED|
			PKG_LOAD_ANNOTATIONS|PKG_LOAD_CONFLICTS;

	if (root && (j->flags & PKG_FLAG_FORCE) == PKG_FLAG_FORCE)
		force = true;

	if (((j->flags & PKG_FLAG_FORCE) == PKG_FLAG_FORCE) &&
	    ((j->flags & PKG_FLAG_RECURSIVE) == PKG_FLAG_RECURSIVE))
	    force = true;

	if (j->type == PKG_JOBS_UPGRADE && (j->flags & PKG_FLAG_FORCE) == PKG_FLAG_FORCE)
		force = true;

	if ((it = pkgdb_repo_query(j->db, pattern, m, j->reponame)) == NULL)
		rc = EPKG_FATAL;

	while (it != NULL && pkgdb_it_next(it, &p, flags) == EPKG_OK) {
		rc = pkg_jobs_process_remote_pkg(j, p, root, force, recursive,
				NULL, add_request);
		if (rc == EPKG_FATAL)
			break;
		else if (rc == EPKG_OK)
			found = true;

		p = NULL;
	}

	pkgdb_it_free(it);

	if (root && !found && rc != EPKG_INSTALLED) {
		/*
		 * Here we need to ensure that this package has no
		 * reverse deps installed
		 */
		p = pkg_jobs_get_local_pkg(j, pattern, PKG_LOAD_BASIC|PKG_LOAD_RDEPS);
		if (p == NULL)
			return (EPKG_END);

		pkg_jobs_add_universe(j, p, true, false, NULL);
<commit_msg>Fix message if a pattern has not been found.<commit_after>/*-
 * Copyright (c) 2011-2012 <NAME> <<EMAIL>>
 * Copyright (c) 2011-2012 <NAME> <<EMAIL>>
 * Copyright (c) 2011-2012 <NAME> <<EMAIL>>
 * Copyright (c) 2013 <NAME> <<EMAIL>>
 * Copyright (c) 2013-2014 <NAME> <<EMAIL>>
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer
 *    in this position and unchanged.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/param.h>
#include <sys/mount.h>
#include <sys/types.h>

#include <archive.h>
#include <archive_entry.h>
#include <assert.h>
#include <errno.h>
#include <libutil.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <ctype.h>

#include "pkg.h"
#include "private/event.h"
#include "private/pkg.h"
#include "private/pkgdb.h"

static int pkg_jobs_find_remote_pkg(struct pkg_jobs *j, const char *pattern, match_t m,
		bool root, bool recursive, bool add_request);
static struct pkg *pkg_jobs_get_local_pkg(struct pkg_jobs *j, const char *uid, unsigned flag);
static struct pkg *pkg_jobs_get_remote_pkg(struct pkg_jobs *j, const char *uid, unsigned flag);
static int pkg_jobs_fetch(struct pkg_jobs *j);
static bool pkg_jobs_newer_than_local(struct pkg_jobs *j, struct pkg *rp, bool force);
static bool pkg_need_upgrade(struct pkg *rp, struct pkg *lp, bool recursive);
static bool new_pkg_version(struct pkg_jobs *j);
static int pkg_jobs_check_conflicts(struct pkg_jobs *j);

#define IS_DELETE(j) ((j)->type == PKG_JOBS_DEINSTALL || (j)->type == PKG_JOBS_AUTOREMOVE)

int
pkg_jobs_new(struct pkg_jobs **j, pkg_jobs_t t, struct pkgdb *db)
{
	assert(db != NULL);

	if ((*j = calloc(1, sizeof(struct pkg_jobs))) == NULL) {
		pkg_emit_errno("calloc", "pkg_jobs");
		return (EPKG_FATAL);
	}

	(*j)->db = db;
	(*j)->type = t;
	(*j)->solved = 0;
	(*j)->flags = PKG_FLAG_NONE;

	return (EPKG_OK);
}

void
pkg_jobs_set_flags(struct pkg_jobs *j, pkg_flags flags)
{
	j->flags = flags;
}

int
pkg_jobs_set_repository(struct pkg_jobs *j, const char *ident)
{
	if ((pkg_repo_find(ident)) == NULL) {
		pkg_emit_error("Unknown repository: %s", ident);
		return (EPKG_FATAL);
	}

	j->reponame = ident;

	return (EPKG_OK);
}

static void
pkg_jobs_pattern_free(struct job_pattern *jp)
{
	if (jp->pattern != NULL)
		free(jp->pattern);
	if (jp->path != NULL)
		free(jp->path);

	free(jp);
}

static void
pkg_jobs_provide_free(struct pkg_job_provide *pr)
{
	struct pkg_job_provide *cur, *tmp;

	DL_FOREACH_SAFE(pr, cur, tmp) {
		free (cur);
	}
}

static void
pkg_jobs_replacement_free(struct pkg_job_replace *r)
{
	free(r->new_uid);
	free(r->old_uid);
	free(r);
}

void
pkg_jobs_free(struct pkg_jobs *j)
{
	struct pkg_job_request *req, *tmp;
	struct pkg_job_universe_item *un, *untmp, *cur, *curtmp;


	if (j == NULL)
		return;

	HASH_ITER(hh, j->request_add, req, tmp) {
		HASH_DEL(j->request_add, req);
		free(req);
	}
	HASH_ITER(hh, j->request_delete, req, tmp) {
		HASH_DEL(j->request_delete, req);
		free(req);
	}
	HASH_ITER(hh, j->universe, un, untmp) {
		HASH_DEL(j->universe, un);

		if (un->reinstall != NULL)
			pkg_free(un->reinstall);

		LL_FOREACH_SAFE(un, cur, curtmp) {
			pkg_free(cur->pkg);
			free(cur);
		}
	}
	HASH_FREE(j->seen, free);
	HASH_FREE(j->patterns, pkg_jobs_pattern_free);
	HASH_FREE(j->provides, pkg_jobs_provide_free);
	LL_FREE(j->jobs, free);
	LL_FREE(j->uid_replaces, pkg_jobs_replacement_free);

	free(j);
}

static bool
pkg_jobs_maybe_match_file(struct job_pattern *jp, const char *pattern)
{
	const char *dot_pos;
	char *pkg_path;

	assert(jp != NULL);
	assert(pattern != NULL);

	dot_pos = strrchr(pattern, '.');
	if (dot_pos != NULL) {
		/*
		 * Compare suffix with .txz or .tbz
		 */
		dot_pos ++;
		if (strcmp(dot_pos, "txz") == 0 ||
			strcmp(dot_pos, "tbz") == 0 ||
			strcmp(dot_pos, "tgz") == 0 ||
			strcmp(dot_pos, "tar") == 0) {
			if ((pkg_path = realpath(pattern, NULL)) != NULL) {
				/* Dot pos is one character after the dot */
				int len = dot_pos - pattern;

				jp->is_file = true;
				jp->path = pkg_path;
				jp->pattern = malloc(len);
				strlcpy(jp->pattern, pattern, len);

				return (true);
			}
		}
	}
	else if (strcmp(pattern, "-") == 0) {
		/*
		 * Read package from stdin
		 */
		jp->is_file = true;
		jp->path = strdup(pattern);
		jp->pattern = strdup(pattern);
	}

	return (false);
}

int
pkg_jobs_add(struct pkg_jobs *j, match_t match, char **argv, int argc)
{
	struct job_pattern *jp;
	int i = 0;

	if (j->solved) {
		pkg_emit_error("The job has already been solved. "
		    "Impossible to append new elements");
		return (EPKG_FATAL);
	}

	for (i = 0; i < argc; i++) {
		jp = calloc(1, sizeof(struct job_pattern));
		if (!pkg_jobs_maybe_match_file(jp, argv[i])) {
			jp->pattern = strdup(argv[i]);
			jp->match = match;
		}
		HASH_ADD_KEYPTR(hh, j->patterns, jp->pattern, strlen(jp->pattern), jp);
	}

	if (argc == 0 && match == MATCH_ALL) {
		jp = calloc(1, sizeof(struct job_pattern));
		jp->pattern = NULL;
		jp->match = match;
		HASH_ADD_KEYPTR(hh, j->patterns, "all", 3, jp);
	}

	return (EPKG_OK);
}

bool
pkg_jobs_iter(struct pkg_jobs *jobs, void **iter,
				struct pkg **new, struct pkg **old,
				int *type)
{
	struct pkg_solved *s;
	assert(iter != NULL);
	if (jobs->jobs == NULL) {
		return (false);
	}
	if (*iter == NULL) {
		s = jobs->jobs;
	}
	else if (*iter == jobs->jobs) {
		return (false);
	}
	else {
		s = *iter;
	}
	*new = s->items[0]->pkg;
	*old = s->items[1] ? s->items[1]->pkg : NULL;
	*type = s->type;
	*iter = s->next ? s->next : jobs->jobs;
	return (true);
}

static void
pkg_jobs_add_req(struct pkg_jobs *j, const char *uid,
		struct pkg_job_universe_item *item)
{
	struct pkg_job_request *req, *test, **head;

	if (!IS_DELETE(j))
		head = &j->request_add;
	else
		head = &j->request_delete;

	HASH_FIND(hh, *head, uid, strlen(uid), test);

	if (test != NULL)
		return;

	req = calloc(1, sizeof (struct pkg_job_request));
	if (req == NULL) {
		pkg_emit_errno("malloc", "struct pkg_job_request");
		return;
	}
	req->item = item;

	HASH_ADD_KEYPTR(hh, *head, uid, strlen(uid), req);
}

enum pkg_priority_update_type {
	PKG_PRIORITY_UPDATE_REQUEST = 0,
	PKG_PRIORITY_UPDATE_UNIVERSE,
	PKG_PRIORITY_UPDATE_CONFLICT,
	PKG_PRIORITY_UPDATE_DELETE
};

#define RECURSION_LIMIT 1024

static void
pkg_jobs_update_universe_priority(struct pkg_jobs *j,
		struct pkg_job_universe_item *item, int priority,
		enum pkg_priority_update_type type)
{
	const char *uid, *digest;
	struct pkg_dep *d = NULL;
	struct pkg_conflict *c = NULL;
	struct pkg_job_universe_item *found, *cur, *it;
	const char *is_local;
	int maxpri;

	int (*deps_func)(const struct pkg *pkg, struct pkg_dep **d);
	int (*rdeps_func)(const struct pkg *pkg, struct pkg_dep **d);

	if (priority > RECURSION_LIMIT) {
		pkg_debug(1, "recursion limit has been reached, something is bad"
					" with dependencies/conflicts graph");
		return;
	}
	else if (priority + 10 > RECURSION_LIMIT) {
		pkg_get(item->pkg, PKG_UNIQUEID, &uid);
		pkg_debug(2, "approaching recursion limit at %d, while processing of"
					" package %s", priority, uid);
	}

	LL_FOREACH(item, it) {

		pkg_get(it->pkg, PKG_UNIQUEID, &uid, PKG_DIGEST, &digest);
		if ((item->next != NULL || item->prev != NULL) &&
				it->pkg->type != PKG_INSTALLED &&
				(type == PKG_PRIORITY_UPDATE_CONFLICT ||
				 type == PKG_PRIORITY_UPDATE_DELETE)) {
			/*
			 * We do not update priority of a remote part of conflict, as we know
			 * that remote packages should not contain conflicts (they should be
			 * resolved in request prior to calling of this function)
			 */
			pkg_debug(4, "skip update priority for %s-%s", uid, digest);
			continue;
		}
		if (it->priority > priority)
			continue;

		is_local = it->pkg->type == PKG_INSTALLED ? "local" : "remote";
		pkg_debug(2, "universe: update %s priority of %s(%s): %d -> %d, reason: %d",
				is_local, uid, digest, it->priority, priority, type);
		it->priority = priority;

		if (type == PKG_PRIORITY_UPDATE_DELETE) {
			/*
			 * For delete requests we inverse deps and rdeps logic
			 */
			deps_func = pkg_rdeps;
			rdeps_func = pkg_deps;
		}
		else {
			deps_func = pkg_deps;
			rdeps_func = pkg_rdeps;
		}

		while (deps_func(it->pkg, &d) == EPKG_OK) {
			HASH_FIND_STR(j->universe, d->uid, found);
			if (found != NULL) {
				LL_FOREACH(found, cur) {
					if (cur->priority < priority + 1)
						pkg_jobs_update_universe_priority(j, cur,
								priority + 1, type);
				}
			}
		}

		d = NULL;
		maxpri = priority;
		while (rdeps_func(it->pkg, &d) == EPKG_OK) {
			HASH_FIND_STR(j->universe, d->uid, found);
			if (found != NULL) {
				LL_FOREACH(found, cur) {
					if (cur->priority >= maxpri) {
						maxpri = cur->priority + 1;
					}
				}
			}
		}
		if (maxpri != priority) {
			pkg_jobs_update_universe_priority(j, it,
					maxpri, type);
			return;
		}
		if (it->pkg->type != PKG_INSTALLED) {
			while (pkg_conflicts(it->pkg, &c) == EPKG_OK) {
				HASH_FIND_STR(j->universe, pkg_conflict_uniqueid(c), found);
				if (found != NULL) {
					LL_FOREACH(found, cur) {
						if (cur->pkg->type == PKG_INSTALLED) {
							/*
							 * Move delete requests to be done before installing
							 */
							if (cur->priority <= it->priority)
								pkg_jobs_update_universe_priority(j, cur,
									it->priority + 1, PKG_PRIORITY_UPDATE_CONFLICT);
						}
					}
				}
			}
		}
	}
}

static void
pkg_jobs_update_conflict_priority(struct pkg_jobs *j, struct pkg_solved *req)
{
	struct pkg_conflict *c = NULL;
	struct pkg *lp = req->items[1]->pkg;
	struct pkg_job_universe_item *found, *cur, *rit = NULL;

	while (pkg_conflicts(lp, &c) == EPKG_OK) {
		rit = NULL;
		HASH_FIND_STR(j->universe, pkg_conflict_uniqueid(c), found);
		assert(found != NULL);

		LL_FOREACH(found, cur) {
			if (cur->pkg->type != PKG_INSTALLED) {
				rit = cur;
				break;
			}
		}

		assert(rit != NULL);
		if (rit->priority >= req->items[1]->priority) {
			pkg_jobs_update_universe_priority(j, req->items[1],
					rit->priority + 1, PKG_PRIORITY_UPDATE_CONFLICT);
			/*
			 * Update priorities for a remote part as well
			 */
			pkg_jobs_update_universe_priority(j, req->items[0],
					req->items[0]->priority, PKG_PRIORITY_UPDATE_REQUEST);
		}
	}
}

static int
pkg_jobs_set_request_priority(struct pkg_jobs *j, struct pkg_solved *req)
{
	struct pkg_solved *treq;
	const char *uid;

	if (req->type == PKG_SOLVED_UPGRADE
			&& req->items[1]->pkg->conflicts != NULL) {
		/*
		 * We have an upgrade request that has some conflicting packages, therefore
		 * update priorities of local packages and try to update priorities of remote ones
		 */
		if (req->items[0]->priority == 0)
			pkg_jobs_update_conflict_priority(j, req);

		if (req->items[1]->priority > req->items[0]->priority &&
				!req->already_deleted) {
			/*
			 * Split conflicting upgrade request into delete -> upgrade request
			 */
			treq = calloc(1, sizeof(struct pkg_solved));
			if (treq == NULL) {
				pkg_emit_errno("calloc", "pkg_solved");
				return (EPKG_FATAL);
			}

			treq->type = PKG_SOLVED_UPGRADE_REMOVE;
			treq->items[0] = req->items[1];
			DL_APPEND(j->jobs, treq);
			j->count ++;
			req->already_deleted = true;
			pkg_get(treq->items[0]->pkg, PKG_UNIQUEID, &uid);
			pkg_debug(2, "split upgrade request for %s", uid);
			return (EPKG_CONFLICT);
		}
	}
	else if (req->type == PKG_SOLVED_DELETE) {
		if (req->items[0]->priority == 0)
			pkg_jobs_update_universe_priority(j, req->items[0], 0,
					PKG_PRIORITY_UPDATE_DELETE);
	}
	else {
		if (req->items[0]->priority == 0)
			pkg_jobs_update_universe_priority(j, req->items[0], 0,
					PKG_PRIORITY_UPDATE_REQUEST);
	}

	return (EPKG_OK);
}

static int
pkg_jobs_sort_priority(struct pkg_solved *r1, struct pkg_solved *r2)
{
	if (r1->items[0]->priority == r2->items[0]->priority) {
		if (r1->type == PKG_SOLVED_DELETE && r2->type != PKG_SOLVED_DELETE)
			return (-1);
		else if (r2->type == PKG_SOLVED_DELETE && r1->type != PKG_SOLVED_DELETE)
			return (1);

		return (0);
	}
	return (r2->items[0]->priority - r1->items[0]->priority);
}

static void
pkg_jobs_set_priorities(struct pkg_jobs *j)
{
	struct pkg_solved *req;

iter_again:
	LL_FOREACH(j->jobs, req) {
		req->items[0]->priority = 0;
		if (req->items[1] != NULL)
			req->items[1]->priority = 0;
	}
	LL_FOREACH(j->jobs, req) {
		if (pkg_jobs_set_request_priority(j, req) == EPKG_CONFLICT)
			goto iter_again;
	}

	DL_SORT(j->jobs, pkg_jobs_sort_priority);
}

#undef PRIORITY_CAN_UPDATE


/**
 * Check whether a package is in the universe already or add it
 * @return item or NULL
 */
static int
pkg_jobs_handle_pkg_universe(struct pkg_jobs *j, struct pkg *pkg,
		struct pkg_job_universe_item **found)
{
	struct pkg_job_universe_item *item, *cur, *tmp = NULL;
	const char *uid, *digest, *version, *name;
	struct pkg_job_seen *seen;

	pkg_get(pkg, PKG_UNIQUEID, &uid, PKG_DIGEST, &digest,
			PKG_VERSION, &version, PKG_NAME, &name);
	if (digest == NULL) {
		pkg_debug(3, "no digest found for package %s (%s-%s)", uid,
				name, version);
		if (pkg_checksum_calculate(pkg, j->db) != EPKG_OK) {
			*found = NULL;
			return (EPKG_FATAL);
		}
		pkg_get(pkg, PKG_DIGEST, &digest);
	}

	HASH_FIND_STR(j->seen, digest, seen);
	if (seen != NULL) {
		cur = seen->un;
		if (found != NULL)
			*found = seen->un;

		return (EPKG_END);
	}

	pkg_debug(2, "universe: add new %s pkg: %s, (%s-%s:%s)",
				(pkg->type == PKG_INSTALLED ? "local" : "remote"), uid,
				name, version, digest);

	item = calloc(1, sizeof (struct pkg_job_universe_item));
	if (item == NULL) {
		pkg_emit_errno("pkg_jobs_pkg_insert_universe", "calloc: struct pkg_job_universe_item");
		return (EPKG_FATAL);
	}

	item->pkg = pkg;

	HASH_FIND_STR(j->universe, uid, tmp);
	if (tmp == NULL) {
		HASH_ADD_KEYPTR(hh, j->universe, uid, strlen(uid), item);
	}

	DL_APPEND(tmp, item);

	seen = calloc(1, sizeof(struct pkg_job_seen));
	seen->digest = digest;
	seen->un = item;
	HASH_ADD_KEYPTR(hh, j->seen, seen->digest, strlen(seen->digest), seen);

	j->total++;

	if (found != NULL)
		*found = item;

	return (EPKG_OK);
}

static int
pkg_jobs_add_universe(struct pkg_jobs *j, struct pkg *pkg,
		bool recursive, bool deps_only, struct pkg_job_universe_item **result)
{
	struct pkg_dep *d = NULL;
	struct pkg_conflict *c = NULL;
	struct pkg *npkg, *rpkg;
	struct pkg_job_universe_item *unit;
	struct pkg_shlib *shlib = NULL;
	struct pkgdb_it *it;
	struct pkg_job_provide *pr, *prhead;
	struct pkg_job_seen *seen;
	int ret;
	bool automatic = false;
	const char *uid, *name, *digest;
	unsigned flags = PKG_LOAD_BASIC|PKG_LOAD_OPTIONS|PKG_LOAD_DEPS|
			PKG_LOAD_SHLIBS_REQUIRED|PKG_LOAD_SHLIBS_PROVIDED|
			PKG_LOAD_ANNOTATIONS|PKG_LOAD_CONFLICTS;

	if (!deps_only) {
		/* Add the requested package itself */
		ret = pkg_jobs_handle_pkg_universe(j, pkg, result);

		if (ret == EPKG_END)
			return (EPKG_OK);
		else if (ret == EPKG_OK && !recursive)
			return (EPKG_OK);
		else if (ret != EPKG_OK)
			return (EPKG_FATAL);
	}

	/* Go through all depends */
	while (pkg_deps(pkg, &d) == EPKG_OK) {
		/* XXX: this assumption can be applied only for the current plain dependencies */
		HASH_FIND_STR(j->universe, d->uid, unit);
		if (unit != NULL) {
			continue;
		}

		rpkg = NULL;
		npkg = pkg_jobs_get_local_pkg(j, d->uid, 0);
		if (npkg == NULL && !IS_DELETE(j)) {
			/*
			 * We have a package installed, but its dependencies are not,
			 * try to search a remote dependency
			 */
			pkg_get(pkg, PKG_NAME, &name);
			pkg_debug(1, "dependency %s of local package %s is not installed",
					pkg_dep_get(d, PKG_DEP_NAME), name);
			npkg = pkg_jobs_get_remote_pkg(j, d->uid, 0);
			if (npkg == NULL) {
				/* Cannot continue */
				pkg_emit_error("Missing dependency matching '%s'",
						pkg_dep_get(d, PKG_DEP_NAME));
				if ((j->flags & PKG_FLAG_FORCE_MISSING) == PKG_FLAG_FORCE_MISSING) {
					continue;
				}
				return (EPKG_FATAL);
			}
		}
		else if (npkg == NULL) {
			/* For delete jobs we don't care about uninstalled dependencies */
			continue;
		}
		else if (!IS_DELETE(j) && npkg->type == PKG_INSTALLED) {
			/* For upgrade jobs we need to ensure that we do not have a newer version */
			rpkg = pkg_jobs_get_remote_pkg(j, d->uid, 0);
			if (rpkg != NULL) {
				if (!pkg_need_upgrade(rpkg, npkg, false)) {
					/*
					 * We can do it safely here, as rpkg is definitely NOT in
					 * the universe
					 */
					pkg_free(rpkg);
					rpkg = NULL;
				}
			}
		}

		if (pkg_jobs_add_universe(j, npkg, recursive, false, NULL) != EPKG_OK)
			return (EPKG_FATAL);
		if (rpkg != NULL) {
			/* Save automatic flag */
			pkg_get(npkg, PKG_AUTOMATIC, &automatic);
			pkg_set(rpkg, PKG_AUTOMATIC, automatic);

			if (pkg_jobs_add_universe(j, rpkg, recursive, false, NULL) != EPKG_OK)
				return (EPKG_FATAL);
		}
	}

	/* Go through all rdeps */
	d = NULL;
	while (pkg_rdeps(pkg, &d) == EPKG_OK) {
		/* XXX: this assumption can be applied only for the current plain dependencies */
		HASH_FIND_STR(j->universe, d->uid, unit);
		if (unit != NULL)
			continue;

		npkg = pkg_jobs_get_local_pkg(j, d->uid, 0);
		if (npkg != NULL) {
			/* Do not bother about remote deps */
			if (pkg_jobs_add_universe(j, npkg, recursive, false, NULL) != EPKG_OK)
				return (EPKG_FATAL);
		}
	}

	if (!IS_DELETE(j)) {
		/* Examine conflicts */
		while (pkg_conflicts(pkg, &c) == EPKG_OK) {
			/* XXX: this assumption can be applied only for the current plain dependencies */
			HASH_FIND_STR(j->universe, pkg_conflict_uniqueid(c), unit);
			if (unit != NULL)
				continue;

			/* Check local and remote conflicts */
			if (pkg->type == PKG_INSTALLED) {
				/* Installed packages can conflict with remote ones */
				npkg = pkg_jobs_get_remote_pkg(j, pkg_conflict_uniqueid(c), 0);
				if (npkg == NULL)
					continue;

				if (pkg_jobs_add_universe(j, npkg, recursive, false, NULL) != EPKG_OK)
					return (EPKG_FATAL);
			}
			else {
				/* Remote packages can conflict with remote and local */
				npkg = pkg_jobs_get_local_pkg(j, pkg_conflict_uniqueid(c), 0);
				if (npkg == NULL)
					continue;

				if (pkg_jobs_add_universe(j, npkg, recursive, false, NULL) != EPKG_OK)
					return (EPKG_FATAL);

				if (c->type != PKG_CONFLICT_REMOTE_LOCAL) {
					npkg = pkg_jobs_get_remote_pkg(j, pkg_conflict_uniqueid(c), 0);
					if (npkg == NULL)
						continue;

					if (pkg_jobs_add_universe(j, npkg, recursive, false, NULL)
							!= EPKG_OK)
						return (EPKG_FATAL);
				}
			}
		}
	}

	/* For remote packages we should also handle shlib deps */
	if (pkg->type != PKG_INSTALLED && !IS_DELETE(j)) {
		while (pkg_shlibs_required(pkg, &shlib) == EPKG_OK) {
			HASH_FIND_STR(j->provides, pkg_shlib_name(shlib), pr);
			if (pr != NULL)
				continue;

			/* Not found, search in the repos */
			it = pkgdb_repo_shlib_provide(j->db, pkg_shlib_name(shlib), j->reponame);
			if (it != NULL) {
				rpkg = NULL;
				prhead = NULL;
				while (pkgdb_it_next(it, &rpkg, flags) == EPKG_OK) {
					pkg_get(rpkg, PKG_DIGEST, &digest, PKG_UNIQUEID, &uid);
					/* Check for local packages */
					HASH_FIND_STR(j->universe, uid, unit);
					if (unit != NULL) {
						if (pkg_need_upgrade (rpkg, unit->pkg, false)) {
							/* Remote provide is newer, so we can add it */
							if (pkg_jobs_add_universe(j, rpkg, recursive, false,
																&unit) != EPKG_OK)
								return (EPKG_FATAL);

							rpkg = NULL;
						}
					}
					else {
						/* Maybe local package has just been not added */
						npkg = pkg_jobs_get_local_pkg(j, uid, 0);
						if (npkg != NULL) {
							if (pkg_jobs_add_universe(j, npkg, recursive, false,
									&unit) != EPKG_OK)
								return (EPKG_FATAL);
							if (pkg_need_upgrade (rpkg, npkg, false)) {
								/* Remote provide is newer, so we can add it */
								if (pkg_jobs_add_universe(j, rpkg, recursive, false,
										&unit) != EPKG_OK)
									return (EPKG_FATAL);
							}
						}
					}
					/* Skip seen packages */
					if (unit == NULL) {
						if (digest == NULL) {
							pkg_debug(3, "no digest found for package %s", uid);
							if (pkg_checksum_calculate(pkg, j->db) != EPKG_OK) {
								return (EPKG_FATAL);
							}
							pkg_get(pkg, PKG_DIGEST, &digest);
						}
						HASH_FIND_STR(j->seen, digest, seen);
						if (seen == NULL) {
							pkg_jobs_add_universe(j, rpkg, recursive, false,
									&unit);

							/* Reset package to avoid freeing */
							rpkg = NULL;
						}
						else {
							unit = seen->un;
						}
					}

					pr = calloc (1, sizeof (*pr));
					if (pr == NULL) {
						pkg_emit_errno("pkg_jobs_add_universe", "calloc: "
								"struct pkg_job_provide");
						return (EPKG_FATAL);
					}
					pr->un = unit;
					pr->provide = pkg_shlib_name(shlib);
					if (prhead == NULL) {
						DL_APPEND(prhead, pr);
						HASH_ADD_KEYPTR(hh, j->provides, pr->provide,
								strlen(pr->provide), prhead);
					}
					else {
						DL_APPEND(prhead, pr);
					}
				}
				pkgdb_it_free(it);
				if (prhead == NULL) {
					pkg_get(pkg, PKG_NAME, &name);
					pkg_debug(1, "cannot find packages that provide %s required for %s",
							pkg_shlib_name(shlib), name);
					/*
					 * XXX: this is not normal but it is very common for the existing
					 * repos, hence we just ignore this stale dependency
					 */
				}
			}
		}
	}

	return (EPKG_OK);
}

/**
 * Test whether package specified is automatic with all its rdeps
 * @param j
 * @param p
 * @return
 */
static bool
pkg_jobs_test_automatic(struct pkg_jobs *j, struct pkg *p)
{
	struct pkg_dep *d = NULL;
	struct pkg_job_universe_item *unit;
	struct pkg *npkg;
	bool ret = true;
	bool automatic;

	while (pkg_rdeps(p, &d) == EPKG_OK && ret) {
		HASH_FIND_STR(j->universe, d->uid, unit);
		if (unit != NULL) {
			pkg_get(unit->pkg, PKG_AUTOMATIC, &automatic);
			if (!automatic) {
				return (false);
			}
			npkg = unit->pkg;
		}
		else {
			npkg = pkg_jobs_get_local_pkg(j, d->uid,
					PKG_LOAD_BASIC|PKG_LOAD_RDEPS|PKG_LOAD_ANNOTATIONS);
			pkg_get(npkg, PKG_AUTOMATIC, &automatic);
			if (npkg == NULL)
				return (false);
			if (!automatic) {
				/*
				 * Safe to free, as d->uid is not in the universe
				 */
				pkg_free(npkg);
				return (false);
			}
			if (pkg_jobs_add_universe(j, npkg, false, false, NULL) != EPKG_OK)
				return (false);
		}

		ret = pkg_jobs_test_automatic(j, npkg);
	}

	return (ret);
}



static bool
new_pkg_version(struct pkg_jobs *j)
{
	struct pkg *p;
	const char *uid = "pkg~ports-mgmt/pkg";
	pkg_flags old_flags;
	bool ret = false;

	/* Disable -f for pkg self-check, and restore at end. */
	old_flags = j->flags;
	j->flags &= ~(PKG_FLAG_FORCE|PKG_FLAG_RECURSIVE);

	/* determine local pkgng */
	p = pkg_jobs_get_local_pkg(j, uid, PKG_LOAD_BASIC|PKG_LOAD_ANNOTATIONS);

	if (p == NULL) {
		uid = "pkg~ports-mgmt/pkg-devel";
		p = pkg_jobs_get_local_pkg(j, uid, PKG_LOAD_BASIC|PKG_LOAD_ANNOTATIONS);
	}

	/* you are using git version skip */
	if (p == NULL) {
		ret = false;
		goto end;
	}

	pkg_jobs_add_universe(j, p, true, false, NULL);

	/* Use maximum priority for pkg */
	if (pkg_jobs_find_remote_pkg(j, uid, MATCH_EXACT, false, true, true) == EPKG_OK) {
		ret = true;
		goto end;
	}

end:
	j->flags = old_flags;

	return (ret);
}

static int
pkg_jobs_process_remote_pkg(struct pkg_jobs *j, struct pkg *p,
		bool root, bool force, bool recursive,
		struct pkg_job_universe_item **unit,
		bool add_request)
{
	struct pkg *p1;
	struct pkg_job_universe_item *jit;
	struct pkg_job_seen *seen;
	struct pkg_job_request *jreq;
	int rc = EPKG_FATAL;
	const char *uid, *digest;

	p1 = NULL;
	pkg_get(p, PKG_UNIQUEID, &uid, PKG_DIGEST, &digest);

	if (digest == NULL) {
		if (pkg_checksum_calculate(p, j->db) != EPKG_OK) {
			return (EPKG_FATAL);
		}
		pkg_get(p, PKG_DIGEST, &digest);
	}
	HASH_FIND_STR(j->seen, digest, seen);
	if (seen != NULL) {
		/* We have already added exactly the same package to the universe */
		pkg_debug(3, "already seen package %s-%s(%c) in the universe, do not add it again",
				uid, digest,
				seen->un->pkg->type == PKG_INSTALLED ? 'l' : 'r');
		if (seen->un->pkg->type != p->type && !force) {
			/* Remote package is the same as local */
			return (EPKG_INSTALLED);
		}
		else {
			/* However, we may want to add it to the job request */
			HASH_FIND_STR(j->request_add, uid, jreq);
			if (jreq == NULL)
				pkg_jobs_add_req(j, uid, seen->un);
			if (force)
				seen->un->reinstall = p;
		}
		return (EPKG_OK);
	}
	HASH_FIND_STR(j->universe, uid, jit);
	if (jit != NULL) {
		/* We have a more recent package */
		if (!force && !pkg_need_upgrade(p, jit->pkg, false)) {
			/*
			 * We can have package from another repo in the
			 * universe, but if it is older than this one we just
			 * do not add it.
			 */
			if (jit->pkg->type == PKG_INSTALLED) {
				return (EPKG_INSTALLED);
			}
			else {
				pkg_debug(3, "already added newer package %s to the universe, do not add it again",
								uid);
				if (add_request)
					pkg_jobs_add_req(j, uid, jit);
				return (EPKG_OK);
			}
		}
		/*
		 * XXX: what happens if we have multirepo enabled and we add
		 * two packages from different repos?
		 */
	}
	else {
		if (j->type != PKG_JOBS_FETCH) {
			if (!pkg_jobs_newer_than_local(j, p, force)) {
				return (EPKG_INSTALLED);
			}
		}
	}

	rc = EPKG_OK;
	p->direct = root;
	/* Add a package to request chain and populate universe */
	rc = pkg_jobs_add_universe(j, p, recursive, false, &jit);
	if (add_request)
		pkg_jobs_add_req(j, uid, jit);

	if (unit != NULL)
		*unit = jit;

	return (rc);
}

static void
pkg_jobs_change_uid(struct pkg_jobs *j, struct pkg_job_universe_item *unit,
	const char *new_uid, size_t uidlen, bool update_rdeps)
{
	struct pkg_dep *rd = NULL, *d = NULL;
	struct pkg_job_universe_item *found;
	struct pkg *lp;
	const char *old_uid;
	struct pkg_job_replace *replacement;

	pkg_get(unit->pkg, PKG_UNIQUEID, &old_uid);

	if (update_rdeps) {
		/* For all rdeps update deps accordingly */
		while (pkg_rdeps(unit->pkg, &rd) == EPKG_OK) {
			HASH_FIND(hh, j->universe, rd->uid, strlen(rd->uid), found);
			if (found == NULL) {
				lp = pkg_jobs_get_local_pkg(j, rd->uid, 0);
				pkg_jobs_add_universe(j, lp, true, false, &found);
			}

			if (found != NULL) {
				while (pkg_deps(found->pkg, &d) == EPKG_OK) {
					if (strcmp(d->uid, old_uid) == 0) {
						free(d->uid);
						d->uid = strdup(new_uid);
					}
				}
			}
		}
	}

	replacement = calloc(1, sizeof(*replacement));
	if (replacement != NULL) {
		replacement->old_uid = strdup(old_uid);
		replacement->new_uid = strdup(new_uid);
		LL_PREPEND(j->uid_replaces, replacement);
	}

	HASH_DELETE(hh, j->universe, unit);
	pkg_set(unit->pkg, PKG_UNIQUEID, new_uid);
	HASH_FIND(hh, j->universe, new_uid, uidlen, found);
	if (found != NULL)
		DL_APPEND(found, unit);
	else
		HASH_ADD_KEYPTR(hh, j->universe, new_uid, uidlen, unit);

}

static int
pkg_jobs_try_remote_candidate(struct pkg_jobs *j, const char *pattern,
		const char *uid, match_t m)
{
	struct pkg *p = NULL;
	struct pkgdb_it *it;
	unsigned flags = PKG_LOAD_BASIC|PKG_LOAD_OPTIONS|PKG_LOAD_DEPS|
				PKG_LOAD_SHLIBS_REQUIRED|PKG_LOAD_SHLIBS_PROVIDED|
				PKG_LOAD_ANNOTATIONS|PKG_LOAD_CONFLICTS;
	int rc = EPKG_FATAL;
	struct sbuf *qmsg;
	const char *fuid;
	struct pkg_job_universe_item *unit;

	if ((it = pkgdb_repo_query(j->db, pattern, m, j->reponame)) == NULL)
		return (EPKG_FATAL);

	qmsg = sbuf_new_auto();

	while (it != NULL && pkgdb_it_next(it, &p, flags) == EPKG_OK) {
		pkg_get(p, PKG_UNIQUEID, &fuid);
		sbuf_printf(qmsg, "%s has no direct installation candidates, change it to "
				"%s [Y/n]: ", uid, fuid);
		sbuf_finish(qmsg);
		if (pkg_emit_query_yesno(true, sbuf_data(qmsg))) {
			/* Change the origin of the local package */
			HASH_FIND(hh, j->universe, uid, strlen(uid), unit);
			if (unit != NULL)
				pkg_jobs_change_uid(j, unit, fuid, strlen(fuid), false);

			rc = pkg_jobs_process_remote_pkg(j, p, true, false, true,
				NULL, true);
			if (rc == EPKG_OK) {
				/* Avoid freeing */
				p = NULL;
			}
			break;
		}
		sbuf_reset(qmsg);
	}


	if (p != NULL)
		pkg_free(p);

	sbuf_free(qmsg);
	pkgdb_it_free(it);

	return (rc);
}

static int
pkg_jobs_guess_upgrade_candidate(struct pkg_jobs *j, const char *pattern)
{

	int rc = EPKG_FATAL;
	const char *pos, *opattern = pattern;
	char *cpy;
	size_t len, olen;

	/* First of all, try to search a package with the same name */
	pos = strchr(pattern, '/');
	if (pos != NULL && pos[1] != '\0') {
		if (pkg_jobs_try_remote_candidate(j, pos + 1, opattern, MATCH_EXACT) == EPKG_OK)
			return (EPKG_OK);
		pos ++;
		pattern = pos;
	}
	else {
		pos = pattern;
	}

	/* Figure, if we have any numbers at the end of the package */
	olen = strlen(pos);
	len = olen;
	while (len > 0) {
		if (isdigit(pos[len - 1]) || pos[len - 1] == '.')
			len --;
		else
			break;
	}

	if (olen != len) {
		/* Try exact pattern without numbers */
		cpy = malloc(len + 1);
		strlcpy(cpy, pos, len + 1);
		if (pkg_jobs_try_remote_candidate(j, cpy, opattern, MATCH_EXACT) != EPKG_OK) {
			free(cpy);
			cpy = sqlite3_mprintf(" WHERE name REGEXP ('^' || %.*Q || '[0-9.]*$')",
					len, pos);
			if (pkg_jobs_try_remote_candidate(j, cpy, opattern, MATCH_CONDITION)
					== EPKG_OK)
				rc = EPKG_OK;
			sqlite3_free(cpy);
		}
		else {
			free(cpy);
			rc = EPKG_OK;
		}
	}

	return (rc);
}

static int
pkg_jobs_find_remote_pkg(struct pkg_jobs *j, const char *pattern,
		match_t m, bool root, bool recursive, bool add_request)
{
	struct pkg *p = NULL;
	struct pkgdb_it *it;
	bool force = false, found = false;
	int rc = EPKG_FATAL;
	struct pkg_dep *rdep = NULL;
	unsigned flags = PKG_LOAD_BASIC|PKG_LOAD_OPTIONS|PKG_LOAD_DEPS|
			PKG_LOAD_SHLIBS_REQUIRED|PKG_LOAD_SHLIBS_PROVIDED|
			PKG_LOAD_ANNOTATIONS|PKG_LOAD_CONFLICTS;

	if (root && (j->flags & PKG_FLAG_FORCE) == PKG_FLAG_FORCE)
		force = true;

	if (((j->flags & PKG_FLAG_FORCE) == PKG_FLAG_FORCE) &&
	    ((j->flags & PKG_FLAG_RECURSIVE) == PKG_FLAG_RECURSIVE))
	    force = true;

	if (j->type == PKG_JOBS_UPGRADE && (j->flags & PKG_FLAG_FORCE) == PKG_FLAG_FORCE)
		force = true;

	if ((it = pkgdb_repo_query(j->db, pattern, m, j->reponame)) == NULL)
		rc = EPKG_FATAL;

	while (it != NULL && pkgdb_it_next(it, &p, flags) == EPKG_OK) {
		rc = pkg_jobs_process_remote_pkg(j, p, root, force, recursive,
				NULL, add_request);
		if (rc == EPKG_FATAL)
			break;
		else if (rc == EPKG_OK)
			found = true;

		p = NULL;
	}

	pkgdb_it_free(it);

	if (root && !found && rc != EPKG_INSTALLED) {
		/*
		 * Here we need to ensure that this package has no
		 * reverse deps installed
		 */
		p = pkg_jobs_get_local_pkg(j, pattern, PKG_LOAD_BASIC|PKG_LOAD_RDEPS);
		if (p == NULL)
			return (EPKG_FATAL);

		pkg_jobs_add_universe(j, p, true, false, NULL);

{'fraction_non_alphanumeric': 0.14076649545634137, 'fraction_numerical': 0.00477281706835243, 'mean_word_length': 3.557476231633535, 'pattern_counts': {'":': 0, '<': 65, '<?xml version=': 0, '>': 563, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4693462', 'n_tokens_mistral': 28819, 'n_tokens_neox': 24394, 'n_words': 6108}