/* $Id: order.c,v 1.9 2009/05/07 21:22:52 imil Exp $ */

/*
 * Copyright (c) 2009 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Emile "iMil" Heitor <imil@NetBSD.org> .
 *
 * 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.
 * 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 AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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 "pkg_dry.h"

/*
 * order.c has only one purpose: arrange lists order in order to satisfy
 * pkg_add / pkg_delete.
 */

/* find dependency deepness for package removal and record it to pdp->level */
static void
remove_dep_deepness(Deptreehead *deptreehead)
{
	char *depname, *p;
	Pkgdeptree *pdp, *lvldp;
	Deptreehead lvldeptree;
	
	SLIST_INIT(&lvldeptree);
	
	/* get higher recursion level */
	SLIST_FOREACH(pdp, deptreehead, next) {
		if (pdp->level == -1) { /* unique package, just return */
			pdp->level = 0;
			return;
		}
		
		pdp->level = 0;

		/* depname received from deptreehead is in package format */
		XSTRDUP(depname, pdp->depname);

		if (pdp->depname == NULL)
			/* there's something wrong with database's record, probably
			 * a mistaken dependency
			 */
			continue;

		if ((p = strrchr(depname, '-')) != NULL)
			*p = '\0';
		
		full_dep_tree(depname, LOCAL_REVERSE_DEPS,
			&lvldeptree, __func__, 0);
		
		SLIST_FOREACH(lvldp, &lvldeptree, next)
			pdp->level++;
		
		XFREE(depname);
		free_deptree(&lvldeptree);

#if 0
		printf("%s -> %d\n", pdp->depname, pdp->level);
#endif
	}
}

/* order the remove list according to dependency level */
Deptreehead *
order_remove(Deptreehead *deptreehead)
{
	int i, maxlevel = 0;
	Pkgdeptree *pdp, *opdp = NULL;
	Deptreehead *ordtreehead;

	/* package removal cannot trust recorded dependencies, reorder */
	remove_dep_deepness(deptreehead);
	
	SLIST_FOREACH(pdp, deptreehead, next)
		if (pdp->level > maxlevel)
			maxlevel = pdp->level;
	
	XMALLOC(ordtreehead, sizeof(Deptreehead));
	SLIST_INIT(ordtreehead);

	for (i = maxlevel; i >=0; i--)
		SLIST_FOREACH(pdp, deptreehead, next) {
			if (pdp->level == i) {
				XMALLOC(opdp, sizeof(Pkgdeptree));
				memcpy(opdp, pdp, sizeof(Pkgdeptree));
				SLIST_INSERT_HEAD(ordtreehead, opdp, next);
			}
		}
	
	return ordtreehead;
}

/* find dependency deepness for upgrade and record it to pimpact->level */
static void
upgrade_dep_deepness(Impacthead *impacthead)
{
	char *depname, *p;
	Pkgimpact *pimpact;
	Pkgdeptree *lvldp;
	Deptreehead lvldeptree;
	
	SLIST_INIT(&lvldeptree);
	
	/* get higher recursion level */
	SLIST_FOREACH(pimpact, impacthead, next) {
		if (pimpact->level == -1) { /* unique package, just return */
			pimpact->level = 0;
			return;
		}

		if (pimpact->action == TOINSTALL) /* only deal with TOUPGRADE */
			continue;
		
		pimpact->level = 0;

		/* depname received from impact is in real dependency format */
		depname = end_expr(pimpact->depname);

		if ((p = strrchr(depname, DELIMITER)) != NULL)
			*p = '\0';
		
		full_dep_tree(depname, LOCAL_REVERSE_DEPS,
			&lvldeptree, __func__, 0);
		
		SLIST_FOREACH(lvldp, &lvldeptree, next)
			pimpact->level++;

#if 0
		printf("%s (%s) -> %d\n", pimpact->depname, depname, pimpact->level);
#endif
		
		XFREE(depname);
		free_deptree(&lvldeptree);
	}
}

/* order the remove-for-upgrade list according to dependency level */
Deptreehead *
order_upgrade_remove(Impacthead *impacthead)
{
	Deptreehead *ordtreehead;
	Pkgimpact *pimpact;
	Pkgdeptree *pdp;
	int i, maxlevel = 0;

	upgrade_dep_deepness(impacthead);
	
	/* record higher dependency level on impact upgrade list */
	SLIST_FOREACH(pimpact, impacthead, next)
		if (pimpact->action == TOUPGRADE && pimpact->level > maxlevel)
			maxlevel = pimpact->level;

	XMALLOC(ordtreehead, sizeof(Deptreehead));
	SLIST_INIT(ordtreehead);
	
	for (i = maxlevel; i >= 0; i--)
		SLIST_FOREACH(pimpact, impacthead, next) {
			if (pimpact->action == TOUPGRADE && pimpact->level == i) {
				XMALLOC(pdp, sizeof(Pkgdeptree));
				XSTRDUP(pdp->depname, pimpact->oldpkg);
				pdp->matchname = NULL; /* safety */
				SLIST_INSERT_HEAD(ordtreehead, pdp, next);
			}
		}
	
	return ordtreehead;
}

/*
 * order the install list according to dependency level
 * here we only rely on basic level given by pkg_summary, the only drawback
 * is that pkg_add will install direct dependencies, giving a "failed,
 * package already installed"
 */
Deptreehead *
order_install(Impacthead *impacthead)
{
	Deptreehead *ordtreehead;
	Pkgimpact *pimpact;
	Pkgdeptree *pdp;
	int i, maxlevel = 0;

	/* record higher dependency level on impact list */
	SLIST_FOREACH(pimpact, impacthead, next) {
		if ((pimpact->action == TOUPGRADE || pimpact->action == TOINSTALL) &&
			pimpact->level > maxlevel)
			maxlevel = pimpact->level;
	}

	XMALLOC(ordtreehead, sizeof(Deptreehead));
	SLIST_INIT(ordtreehead);

	for (i = 0; i <= maxlevel; i++) {
		SLIST_FOREACH(pimpact, impacthead, next) {
			if ((pimpact->action == TOUPGRADE ||
					pimpact->action == TOINSTALL) && pimpact->level == i) {
				XMALLOC(pdp, sizeof(Pkgdeptree));
				XSTRDUP(pdp->depname, pimpact->pkgname);
				pdp->matchname = NULL; /* safety */
				pdp->level = pimpact->level;
				
				SLIST_INSERT_HEAD(ordtreehead, pdp, next);
			}
		}
	}
	
	return ordtreehead;
}