Split ordering code to separate source file

3 files changed, 709 insertions, 693 deletions

diff --git a/lib/Makefile.am b/lib/Makefile.am
index cd01d2748..456ccff0f 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -24,7 +24,7 @@ librpm_la_SOURCES = \
 	hdrNVR.c header.c headerfmt.c header_internal.c header_internal.h \
 	poptDB.c rpmhash.c rpmhash.h rpmdb.c rpmdb_internal.h \
 	fprint.c fprint.h tagname.c rpmtd.c \
-	cpio.c cpio.h depends.c formats.c tagexts.c fs.c fsm.c fsm.h \
+	cpio.c cpio.h depends.c order.c formats.c tagexts.c fs.c fsm.c fsm.h \
 	manifest.c manifest.h misc.c package.c \
 	poptALL.c poptI.c poptQV.c psm.c psm.h query.c \
 	rpmal.c rpmal.h rpmchecksig.c rpmds.c rpmfi.c rpmfi_internal.h rpmgi.c \
diff --git a/lib/depends.c b/lib/depends.c
index 77868da30..c96702856 100644
--- a/lib/depends.c
+++ b/lib/depends.c
@@ -8,14 +8,12 @@
 
 #include <rpm/rpmlib.h>		/* rpmVersionCompare, rpmlib provides */
 #include <rpm/rpmtag.h>
-#include <rpm/rpmmacro.h>       /* XXX rpmExpand("%{_dependency_whiteout */
 #include <rpm/rpmlog.h>
 #include <rpm/rpmdb.h>
 #include <rpm/rpmds.h>
 #include <rpm/rpmfi.h>
 
 #include "lib/rpmdb_internal.h"	/* XXX response cache needs dbiOpen et al. */
-#include "lib/rpmte_internal.h"	/* XXX tsortInfo_s */
 #include "lib/rpmts_internal.h"
 
 #include "debug.h"
@@ -32,19 +30,6 @@ const int rpmFLAGS = RPMSENSE_EQUAL;
 /* rpmlib provides */
 static rpmds rpmlibP = NULL;
 
-/*
- * Strongly Connected Components
- * set of packages (indirectly) requiering each other
- */
-struct scc_s {
-    int count; /* # of external requires this SCC has */
-    /* int qcnt;  # of external requires pointing to this SCC */
-    int size;  /* # of members */
-    rpmte * members;
-};
-
-typedef struct scc_s * scc;
-
 /**
  * Compare removed package instances (qsort/bsearch).
  * @param a		1st instance address
@@ -715,683 +700,6 @@ static int checkDependentConflicts(rpmts ts, const char * dep)
     return rc;
 }
 
-struct badDeps_s {
-    char * pname;
-    const char * qname;
-};
-
-static int badDepsInitialized = 0;
-static struct badDeps_s * badDeps = NULL;
-
-/**
- */
-static void freeBadDeps(void)
-{
-    if (badDeps) {
-	struct badDeps_s * bdp;
-	/* bdp->qname is a pointer to pname so doesn't need freeing */
-	for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++)
-	    bdp->pname = _free(bdp->pname);
-	badDeps = _free(badDeps);
-    }
-    badDepsInitialized = 0;
-}
-
-/**
- * Check for dependency relations to be ignored.
- *
- * @param ts		transaction set
- * @param p		successor element (i.e. with Requires: )
- * @param q		predecessor element (i.e. with Provides: )
- * @return		1 if dependency is to be ignored.
- */
-static int ignoreDep(const rpmts ts, const rpmte p, const rpmte q)
-{
-    struct badDeps_s * bdp;
-
-    if (!badDepsInitialized) {
-	char * s = rpmExpand("%{?_dependency_whiteout}", NULL);
-	const char ** av = NULL;
-	int msglvl = (rpmtsFlags(ts) & RPMTRANS_FLAG_DEPLOOPS)
-			? RPMLOG_WARNING : RPMLOG_DEBUG;
-	int ac = 0;
-	int i;
-
-	if (s != NULL && *s != '\0'
-	&& !(i = poptParseArgvString(s, &ac, (const char ***)&av))
-	&& ac > 0 && av != NULL)
-	{
-	    bdp = badDeps = xcalloc(ac+1, sizeof(*badDeps));
-	    for (i = 0; i < ac; i++, bdp++) {
-		char * pname, * qname;
-
-		if (av[i] == NULL)
-		    break;
-		pname = xstrdup(av[i]);
-		if ((qname = strchr(pname, '>')) != NULL)
-		    *qname++ = '\0';
-		bdp->pname = pname;
-		bdp->qname = qname;
-		rpmlog(msglvl,
-			_("ignore package name relation(s) [%d]\t%s -> %s\n"),
-			i, bdp->pname, (bdp->qname ? bdp->qname : "???"));
-	    }
-	    bdp->pname = NULL;
-	    bdp->qname = NULL;
-	}
-	av = _free(av);
-	s = _free(s);
-	badDepsInitialized++;
-    }
-
-    if (badDeps != NULL)
-    for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++) {
-	if (!strcmp(rpmteN(p), bdp->pname) && !strcmp(rpmteN(q), bdp->qname))
-	    return 1;
-    }
-    return 0;
-}
-
-static inline const char * identifyDepend(rpmsenseFlags f)
-{
-    f = _notpre(f);
-    if (f & RPMSENSE_SCRIPT_PRE)
-	return "Requires(pre):";
-    if (f & RPMSENSE_SCRIPT_POST)
-	return "Requires(post):";
-    if (f & RPMSENSE_SCRIPT_PREUN)
-	return "Requires(preun):";
-    if (f & RPMSENSE_SCRIPT_POSTUN)
-	return "Requires(postun):";
-    if (f & RPMSENSE_SCRIPT_VERIFY)
-	return "Requires(verify):";
-    if (f & RPMSENSE_FIND_REQUIRES)
-	return "Requires(auto):";
-    return "Requires:";
-}
-
-/**
- * Record next "q <- p" relation (i.e. "p" requires "q").
- * @param ts		transaction set
- * @param p		predecessor (i.e. package that "Requires: q")
- * @param requires	relation
- * @return		0 always
- */
-static inline int addRelation(rpmts ts,
-			      rpmal al,
-			      rpmte p,
-			      rpmds requires)
-{
-    rpmte q;
-    struct tsortInfo_s * tsi_p, * tsi_q;
-    relation rel;
-    const char * Name;
-    rpmElementType teType = rpmteType(p);
-    rpmsenseFlags flags, dsflags;
-
-    if ((Name = rpmdsN(requires)) == NULL)
-	return 0;
-
-    dsflags = rpmdsFlags(requires);
-
-    /* Avoid rpmlib feature and package config dependencies */
-    if (dsflags & (RPMSENSE_RPMLIB|RPMSENSE_CONFIG))
-	return 0;
-
-    q = rpmalSatisfiesDepend(al, requires);
-
-    /* Avoid deps outside this transaction and self dependencies */
-    if (q == NULL || q == p)
-	return 0;
-
-    /* Avoid certain dependency relations. */
-    if (ignoreDep(ts, p, q))
-	return 0;
-
-    /* Erasures are reversed installs. */
-    if (teType == TR_REMOVED) {
-        rpmte r = p;
-        p = q;
-        q = r;
-	flags = isErasePreReq(dsflags);
-    } else {
-	flags = isInstallPreReq(dsflags);
-    }
-
-    /* map legacy prereq to pre/preun as needed */
-    if (isLegacyPreReq(dsflags)) {
-	flags |= (teType == TR_ADDED) ?
-		 RPMSENSE_SCRIPT_PRE : RPMSENSE_SCRIPT_PREUN;
-    }
-
-    tsi_p = rpmteTSI(p);
-    tsi_q = rpmteTSI(q);
-
-    /* if relation got already added just update the flags */
-    if (tsi_q->tsi_relations && tsi_q->tsi_relations->rel_suc == p) {
-	tsi_q->tsi_relations->rel_flags |= flags;
-	tsi_p->tsi_forward_relations->rel_flags |= flags;
-	return 0;
-    }
-
-    /* Record next "q <- p" relation (i.e. "p" requires "q"). */
-    if (p != q) {
-	/* bump p predecessor count */
-	rpmteTSI(p)->tsi_count++;
-    }
-
-    /* Save max. depth in dependency tree */
-    if (rpmteDepth(p) <= rpmteDepth(q))
-	(void) rpmteSetDepth(p, (rpmteDepth(q) + 1));
-    if (rpmteDepth(p) > ts->maxDepth)
-	ts->maxDepth = rpmteDepth(p);
-
-    rel = xcalloc(1, sizeof(*rel));
-    rel->rel_suc = p;
-    rel->rel_flags = flags;
-
-    rel->rel_next = rpmteTSI(q)->tsi_relations;
-    rpmteTSI(q)->tsi_relations = rel;
-    if (p != q) {
-	/* bump q successor count */
-	rpmteTSI(q)->tsi_qcnt++;
-    }
-
-    rel = xcalloc(1, sizeof(*rel));
-    rel->rel_suc = q;
-    rel->rel_flags = flags;
-
-    rel->rel_next = rpmteTSI(p)->tsi_forward_relations;
-    rpmteTSI(p)->tsi_forward_relations = rel;
-
-    return 0;
-}
-
-/**
- * Add element to list sorting by tsi_qcnt.
- * @param p		new element
- * @retval qp		address of first element
- * @retval rp		address of last element
- * @param prefcolor
- */
-static void addQ(rpmte p,
-		rpmte * qp,
-		rpmte * rp,
-		rpm_color_t prefcolor)
-{
-    rpmte q, qprev;
-
-    /* Mark the package as queued. */
-    rpmteTSI(p)->tsi_reqx = 1;
-
-    if ((*rp) == NULL) {	/* 1st element */
-	/* FIX: double indirection */
-	(*rp) = (*qp) = p;
-	return;
-    }
-
-    /* Find location in queue using metric tsi_qcnt. */
-    for (qprev = NULL, q = (*qp);
-	 q != NULL;
-	 qprev = q, q = rpmteTSI(q)->tsi_suc)
-    {
-	/* XXX Insure preferred color first. */
-	if (rpmteColor(p) != prefcolor && rpmteColor(p) != rpmteColor(q))
-	    continue;
-
-	if (rpmteTSI(q)->tsi_qcnt <= rpmteTSI(p)->tsi_qcnt)
-	    break;
-    }
-
-    if (qprev == NULL) {	/* insert at beginning of list */
-	rpmteTSI(p)->tsi_suc = q;
-	(*qp) = p;		/* new head */
-    } else if (q == NULL) {	/* insert at end of list */
-	rpmteTSI(qprev)->tsi_suc = p;
-	(*rp) = p;		/* new tail */
-    } else {			/* insert between qprev and q */
-	rpmteTSI(p)->tsi_suc = q;
-	rpmteTSI(qprev)->tsi_suc = p;
-    }
-}
-
-/* Search for SCCs and return an array last entry has a .size of 0 */
-static scc detectSCCs(rpmts ts)
-{
-    int index = 0;                /* DFS node number counter */
-    rpmte stack[ts->orderCount];  /* An empty stack of nodes */
-    int stackcnt = 0;
-    rpmtsi pi;
-    rpmte p;
-
-    int sccCnt = 2;
-    scc SCCs = xcalloc(ts->orderCount+3, sizeof(struct scc_s));
-
-    auto void tarjan(rpmte p);
-
-    void tarjan(rpmte p) {
-	tsortInfo tsi = rpmteTSI(p);
-	rpmte q;
-	tsortInfo tsi_q;
-	relation rel;
-
-        /* use negative index numbers */
-	index--;
-	/* Set the depth index for p */
-	tsi->tsi_SccIdx = index;
-	tsi->tsi_SccLowlink = index;
-
-	stack[stackcnt++] = p;                   /* Push p on the stack */
-	for (rel=tsi->tsi_relations; rel != NULL; rel=rel->rel_next) {
-	    /* Consider successors of p */
-	    q = rel->rel_suc;
-	    tsi_q = rpmteTSI(q);
-	    if (tsi_q->tsi_SccIdx > 0)
-		/* Ignore already found SCCs */
-		continue;
-	    if (tsi_q->tsi_SccIdx == 0){
-		/* Was successor q not yet visited? */
-		tarjan(q);                       /* Recurse */
-		/* negative index numers: use max as it is closer to 0 */
-		tsi->tsi_SccLowlink = (
-		    tsi->tsi_SccLowlink > tsi_q->tsi_SccLowlink
-		    ? tsi->tsi_SccLowlink : tsi_q->tsi_SccLowlink);
-	    } else {
-		tsi->tsi_SccLowlink = (
-		    tsi->tsi_SccLowlink > tsi_q->tsi_SccIdx
-		    ? tsi->tsi_SccLowlink : tsi_q->tsi_SccIdx);
-	    }
-	}
-
-	if (tsi->tsi_SccLowlink == tsi->tsi_SccIdx) {
-	    /* v is the root of an SCC? */
-	    if (stack[stackcnt-1] == p) {
-		/* ignore trivial SCCs */
-		q = stack[--stackcnt];
-		tsi_q = rpmteTSI(q);
-		tsi_q->tsi_SccIdx = 1;
-	    } else {
-		int stackIdx = stackcnt;
-		do {
-		    q = stack[--stackIdx];
-		    tsi_q = rpmteTSI(q);
-		    tsi_q->tsi_SccIdx = sccCnt;
-		} while (q != p);
-
-		stackIdx = stackcnt;
-		do {
-		    q = stack[--stackIdx];
-		    tsi_q = rpmteTSI(q);
-		    /* Calculate count for the SCC */
-		    SCCs[sccCnt].count += tsi_q->tsi_count;
-		    /* Subtract internal relations */
-		    for (rel=tsi_q->tsi_relations; rel != NULL;
-							rel=rel->rel_next) {
-			if (rel->rel_suc != q &&
-				rpmteTSI(rel->rel_suc)->tsi_SccIdx == sccCnt)
-			    SCCs[sccCnt].count--;
-		    }
-		} while (q != p);
-		SCCs[sccCnt].size = stackcnt - stackIdx;
-		/* copy members */
-		SCCs[sccCnt].members = xcalloc(SCCs[sccCnt].size,
-					       sizeof(rpmte));
-		memcpy(SCCs[sccCnt].members, stack + stackIdx,
-		       SCCs[sccCnt].size * sizeof(rpmte));
-		stackcnt = stackIdx;
-		sccCnt++;
-	    }
-	}
-    }
-
-    pi = rpmtsiInit(ts);
-    while ((p=rpmtsiNext(pi, 0)) != NULL) {
-	/* Start a DFS at each node */
-	if (rpmteTSI(p)->tsi_SccIdx == 0)
-	    tarjan(p);
-    }
-    pi = rpmtsiFree(pi);
-
-    SCCs = xrealloc(SCCs, (sccCnt+1)*sizeof(struct scc_s));
-    /* Debug output */
-    if (sccCnt > 2) {
-	int msglvl = (rpmtsFlags(ts) & RPMTRANS_FLAG_DEPLOOPS) ?
-		     RPMLOG_WARNING : RPMLOG_DEBUG;
-	rpmlog(msglvl, "%i Strongly Connected Components\n", sccCnt-2);
-	for (int i = 2; i < sccCnt; i++) {
-	    rpmlog(msglvl, "SCC #%i: requires %i packages\n",
-		   i, SCCs[i].count);
-	    /* loop over members */
-	    for (int j = 0; j < SCCs[i].size; j++) {
-		rpmlog(msglvl, "\t%s\n", rpmteNEVRA(SCCs[i].members[j]));
-		/* show relations between members */
-		rpmte member = SCCs[i].members[j];
-		relation rel = rpmteTSI(member)->tsi_forward_relations;
-		for (; rel != NULL; rel=rel->rel_next) {
-		    if (rpmteTSI(rel->rel_suc)->tsi_SccIdx!=i) continue;
-		    rpmlog(msglvl, "\t\t%s %s\n",
-			   rel->rel_flags ? "=>" : "->",
-			   rpmteNEVRA(rel->rel_suc));
-		}
-	    }
-	}
-    }
-    return SCCs;
-}
-
-static void collectTE(rpm_color_t prefcolor, rpmte q,
-		      rpmte * newOrder, int * newOrderCount,
-		      scc SCCs,
-		      rpmte * queue_end,
-		      rpmte * outer_queue,
-		      rpmte * outer_queue_end)
-{
-    int treex = rpmteTree(q);
-    int depth = rpmteDepth(q);
-    char deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+');
-    tsortInfo tsi = rpmteTSI(q);
-
-    rpmlog(RPMLOG_DEBUG, "%5d%5d%5d%5d%5d %*s%c%s\n",
-	   *newOrderCount, rpmteNpreds(q),
-	   rpmteTSI(q)->tsi_qcnt,
-	   treex, depth,
-	   (2 * depth), "",
-	   deptypechar,
-	   (rpmteNEVRA(q) ? rpmteNEVRA(q) : "???"));
-
-    (void) rpmteSetDegree(q, 0);
-
-    newOrder[*newOrderCount] = q;
-    (*newOrderCount)++;
-
-    /* T6. Erase relations. */
-    for (relation rel = rpmteTSI(q)->tsi_relations;
-	 				rel != NULL; rel = rel->rel_next) {
-	rpmte p = rel->rel_suc;
-	tsortInfo p_tsi = rpmteTSI(p);
-	/* ignore already collected packages */
-	if (p_tsi->tsi_SccIdx == 0) continue;
-	if (p == q) continue;
-
-	if (p && (--p_tsi->tsi_count) == 0) {
-
-	    (void) rpmteSetTree(p, treex);
-	    (void) rpmteSetDepth(p, depth+1);
-	    (void) rpmteSetParent(p, q);
-	    (void) rpmteSetDegree(q, rpmteDegree(q)+1);
-
-	    if (tsi->tsi_SccIdx > 1 && tsi->tsi_SccIdx != p_tsi->tsi_SccIdx) {
-                /* Relation point outside of this SCC: add to outside queue */
-		assert(outer_queue != NULL && outer_queue_end != NULL);
-		addQ(p, outer_queue, outer_queue_end, prefcolor);
-	    } else {
-		addQ(p, &tsi->tsi_suc, queue_end, prefcolor);
-	    }
-	}
-	if (p && p_tsi->tsi_SccIdx > 1 &&
-	                 p_tsi->tsi_SccIdx != rpmteTSI(q)->tsi_SccIdx) {
-	    if (--SCCs[p_tsi->tsi_SccIdx].count == 0) {
-		/* New SCC is ready, add this package as representative */
-
-		(void) rpmteSetTree(p, treex);
-		(void) rpmteSetDepth(p, depth+1);
-		(void) rpmteSetParent(p, q);
-		(void) rpmteSetDegree(q, rpmteDegree(q)+1);
-
-		if (outer_queue != NULL) {
-		    addQ(p, outer_queue, outer_queue_end, prefcolor);
-		} else {
-		    addQ(p, &rpmteTSI(q)->tsi_suc, queue_end, prefcolor);
-		}
-	    }
-	}
-    }
-    tsi->tsi_SccIdx = 0;
-}
-
-static void collectSCC(rpm_color_t prefcolor, rpmte p,
-		       rpmte * newOrder, int * newOrderCount,
-		       scc SCCs, rpmte * queue_end)
-{
-    int sccNr = rpmteTSI(p)->tsi_SccIdx;
-    struct scc_s SCC = SCCs[sccNr];
-    int i;
-    int start, end;
-    relation rel;
-
-    /* remove p from the outer queue */
-    rpmte outer_queue_start = rpmteTSI(p)->tsi_suc;
-    rpmteTSI(p)->tsi_suc = NULL;
-
-    /*
-     * Run a multi source Dijkstra's algorithm to find relations
-     * that can be zapped with least danger to pre reqs.
-     * As weight of the edges is always 1 it is not necessary to
-     * sort the vertices by distance as the queue gets them
-     * already in order
-    */
-
-    /* can use a simple queue as edge weights are always 1 */
-    rpmte * queue = xmalloc((SCC.size+1) * sizeof(rpmte));
-
-    /*
-     * Find packages that are prerequired and use them as
-     * starting points for the Dijkstra algorithm
-     */
-    start = end = 0;
-    for (i = 0; i < SCC.size; i++) {
-	rpmte q = SCC.members[i];
-	tsortInfo tsi = rpmteTSI(q);
-	tsi->tsi_SccLowlink = INT_MAX;
-	for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
-	    if (rel->rel_flags && rpmteTSI(rel->rel_suc)->tsi_SccIdx == sccNr) {
-		if (rel->rel_suc != q) {
-		    tsi->tsi_SccLowlink =  0;
-		    queue[end++] = q;
-		} else {
-		    tsi->tsi_SccLowlink =  INT_MAX/2;
-		}
-		break;
-	    }
-	}
-    }
-
-    if (start == end) { /* no regular prereqs; add self prereqs to queue */
-	for (i = 0; i < SCC.size; i++) {
-	    rpmte q = SCC.members[i];
-	    tsortInfo tsi = rpmteTSI(q);
-	    if (tsi->tsi_SccLowlink != INT_MAX) {
-		queue[end++] = q;
-	    }
-	}
-    }
-
-    /* Do Dijkstra */
-    while (start != end) {
-	rpmte q = queue[start++];
-	tsortInfo tsi = rpmteTSI(q);
-	for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
-	    tsortInfo next_tsi = rpmteTSI(rel->rel_suc);
-	    if (next_tsi->tsi_SccIdx != sccNr) continue;
-	    if (next_tsi->tsi_SccLowlink > tsi->tsi_SccLowlink+1) {
-		next_tsi->tsi_SccLowlink = tsi->tsi_SccLowlink + 1;
-		queue[end++] = rel->rel_suc;
-	    }
-	}
-    }
-    queue = _free(queue);
-
-
-    while (1) {
-	rpmte best = NULL;
-	rpmte inner_queue_start, inner_queue_end;
-	int best_score = 0;
-
-	/* select best candidate to start with */
-	for (int i = 0; i < SCC.size; i++) {
-	    rpmte q = SCC.members[i];
-	    tsortInfo tsi = rpmteTSI(q);
-	    if (tsi->tsi_SccIdx == 0) /* package already collected */
-		continue;
-	    if (tsi->tsi_SccLowlink >= best_score) {
-		best = q;
-		best_score = tsi->tsi_SccLowlink;
-	    }
-	}
-
-	if (best == NULL) /* done */
-	    break;
-
-	/* collect best candidate and all packages that get freed */
-	inner_queue_start = inner_queue_end = NULL;
-	addQ(best, &inner_queue_start, &inner_queue_end, prefcolor);
-
-	for (; inner_queue_start != NULL;
-	     inner_queue_start = rpmteTSI(inner_queue_start)->tsi_suc) {
-	    /* Mark the package as unqueued. */
-	    rpmteTSI(inner_queue_start)->tsi_reqx = 0;
-	    collectTE(prefcolor, inner_queue_start, newOrder, newOrderCount,
-		      SCCs, &inner_queue_end, &outer_queue_start, queue_end);
-	}
-    }
-
-    /* restore outer queue */
-    rpmteTSI(p)->tsi_suc = outer_queue_start;
-}
-
-int rpmtsOrder(rpmts ts)
-{
-    rpm_color_t prefcolor = rpmtsPrefColor(ts);
-    rpmtsi pi; rpmte p;
-    rpmte q;
-    rpmte r;
-    rpmte * newOrder;
-    int newOrderCount = 0;
-    int treex;
-    int rc;
-    rpmal erasedPackages = rpmalCreate(5, rpmtsColor(ts));
-    scc SCCs;
-
-    (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
-
-    /*
-     * XXX FIXME: this gets needlesly called twice on normal usage patterns,
-     * should track the need for generating the index somewhere
-     */
-    rpmalMakeIndex(ts->addedPackages);
-
-    /* Create erased package index. */
-    pi = rpmtsiInit(ts);
-    while ((p = rpmtsiNext(pi, TR_REMOVED)) != NULL) {
-        rpmalAdd(erasedPackages, p);
-    }
-    pi = rpmtsiFree(pi);
-    rpmalMakeIndex(erasedPackages);
-
-    pi = rpmtsiInit(ts);
-    while ((p = rpmtsiNext(pi, 0)) != NULL)
-	rpmteNewTSI(p);
-    pi = rpmtsiFree(pi);
-
-    /* Record relations. */
-    rpmlog(RPMLOG_DEBUG, "========== recording tsort relations\n");
-    pi = rpmtsiInit(ts);
-    while ((p = rpmtsiNext(pi, 0)) != NULL) {
-	rpmal al = (rpmteType(p) == TR_REMOVED) ? 
-		   erasedPackages : ts->addedPackages;
-	rpmds requires = rpmdsInit(rpmteDS(p, RPMTAG_REQUIRENAME));
-
-	while (rpmdsNext(requires) >= 0) {
-	    /* Record next "q <- p" relation (i.e. "p" requires "q"). */
-	    (void) addRelation(ts, al, p, requires);
-	}
-    }
-    pi = rpmtsiFree(pi);
-
-    /* Save predecessor count and mark tree roots. */
-    treex = 0;
-    pi = rpmtsiInit(ts);
-    while ((p = rpmtsiNext(pi, 0)) != NULL) {
-	int npreds = rpmteTSI(p)->tsi_count;
-
-	(void) rpmteSetNpreds(p, npreds);
-	(void) rpmteSetDepth(p, 1);
-
-	if (npreds == 0)
-	    (void) rpmteSetTree(p, treex++);
-	else
-	    (void) rpmteSetTree(p, -1);
-    }
-    pi = rpmtsiFree(pi);
-    ts->ntrees = treex;
-
-    newOrder = xcalloc(ts->orderCount, sizeof(*newOrder));
-    SCCs = detectSCCs(ts);
-
-    rpmlog(RPMLOG_DEBUG, "========== tsorting packages (order, #predecessors, #succesors, tree, depth)\n");
-
-    for (int i = 0; i < 2; i++) {
-	/* Do two separate runs: installs first - then erases */
-	int oType = !i ? TR_ADDED : TR_REMOVED;
-	q = r = NULL;
-	pi = rpmtsiInit(ts);
-	/* Scan for zeroes and add them to the queue */
-	while ((p = rpmtsiNext(pi, oType)) != NULL) {
-	    if (rpmteTSI(p)->tsi_count != 0)
-		continue;
-	    rpmteTSI(p)->tsi_suc = NULL;
-	    addQ(p, &q, &r, prefcolor);
-	}
-	pi = rpmtsiFree(pi);
-
-	/* Add one member of each leaf SCC */
-	for (int i = 2; SCCs[i].members != NULL; i++) {
-	    if (SCCs[i].count == 0 && rpmteType(SCCs[i].members[0]) == oType) {
-		p = SCCs[i].members[0];
-		rpmteTSI(p)->tsi_suc = NULL;
-		addQ(p, &q, &r, prefcolor);
-	    }
-	}
-
-	/* Process queue */
-	for (; q != NULL; q = rpmteTSI(q)->tsi_suc) {
-	    /* Mark the package as unqueued. */
-	    rpmteTSI(q)->tsi_reqx = 0;
-	    if (rpmteTSI(q)->tsi_SccIdx > 1) {
-		collectSCC(prefcolor, q, newOrder, &newOrderCount, SCCs, &r);
-	    } else {
-		collectTE(prefcolor, q, newOrder, &newOrderCount, SCCs, &r,
-			  NULL, NULL);
-	    }
-	}
-    }
-
-    /* Clean up tsort data */
-    pi = rpmtsiInit(ts);
-    while ((p = rpmtsiNext(pi, 0)) != NULL)
-	rpmteFreeTSI(p);
-    pi = rpmtsiFree(pi);
-
-    assert(newOrderCount == ts->orderCount);
-
-    ts->order = _free(ts->order);
-    ts->order = newOrder;
-    ts->orderAlloced = ts->orderCount;
-    rc = 0;
-
-    freeBadDeps();
-
-    for (int i = 2; SCCs[i].members != NULL; i++) {
-	free(SCCs[i].members);
-    }
-    free(SCCs);
-    rpmalFree(erasedPackages);
-
-    (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
-
-    return rc;
-}
-
 int rpmtsCheck(rpmts ts)
 {
     rpm_color_t tscolor = rpmtsColor(ts);
diff --git a/lib/order.c b/lib/order.c
new file mode 100644
index 000000000..2409908c3
--- /dev/null
+++ b/lib/order.c
@@ -0,0 +1,708 @@
+/** \ingroup rpmts
+ * \file lib/depends.c
+ */
+
+#include "system.h"
+
+#include <popt.h>
+
+#include <rpm/rpmtag.h>
+#include <rpm/rpmmacro.h>       /* XXX rpmExpand("%{_dependency_whiteout */
+#include <rpm/rpmlog.h>
+#include <rpm/rpmds.h>
+#include <rpm/rpmfi.h>
+
+#include "lib/rpmte_internal.h"	/* XXX tsortInfo_s */
+#include "lib/rpmts_internal.h"
+
+#include "debug.h"
+
+/*
+ * Strongly Connected Components
+ * set of packages (indirectly) requiering each other
+ */
+struct scc_s {
+    int count; /* # of external requires this SCC has */
+    /* int qcnt;  # of external requires pointing to this SCC */
+    int size;  /* # of members */
+    rpmte * members;
+};
+
+typedef struct scc_s * scc;
+
+struct badDeps_s {
+    char * pname;
+    const char * qname;
+};
+
+static int badDepsInitialized = 0;
+static struct badDeps_s * badDeps = NULL;
+
+/**
+ */
+static void freeBadDeps(void)
+{
+    if (badDeps) {
+	struct badDeps_s * bdp;
+	/* bdp->qname is a pointer to pname so doesn't need freeing */
+	for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++)
+	    bdp->pname = _free(bdp->pname);
+	badDeps = _free(badDeps);
+    }
+    badDepsInitialized = 0;
+}
+
+/**
+ * Check for dependency relations to be ignored.
+ *
+ * @param ts		transaction set
+ * @param p		successor element (i.e. with Requires: )
+ * @param q		predecessor element (i.e. with Provides: )
+ * @return		1 if dependency is to be ignored.
+ */
+static int ignoreDep(const rpmts ts, const rpmte p, const rpmte q)
+{
+    struct badDeps_s * bdp;
+
+    if (!badDepsInitialized) {
+	char * s = rpmExpand("%{?_dependency_whiteout}", NULL);
+	const char ** av = NULL;
+	int msglvl = (rpmtsFlags(ts) & RPMTRANS_FLAG_DEPLOOPS)
+			? RPMLOG_WARNING : RPMLOG_DEBUG;
+	int ac = 0;
+	int i;
+
+	if (s != NULL && *s != '\0'
+	&& !(i = poptParseArgvString(s, &ac, (const char ***)&av))
+	&& ac > 0 && av != NULL)
+	{
+	    bdp = badDeps = xcalloc(ac+1, sizeof(*badDeps));
+	    for (i = 0; i < ac; i++, bdp++) {
+		char * pname, * qname;
+
+		if (av[i] == NULL)
+		    break;
+		pname = xstrdup(av[i]);
+		if ((qname = strchr(pname, '>')) != NULL)
+		    *qname++ = '\0';
+		bdp->pname = pname;
+		bdp->qname = qname;
+		rpmlog(msglvl,
+			_("ignore package name relation(s) [%d]\t%s -> %s\n"),
+			i, bdp->pname, (bdp->qname ? bdp->qname : "???"));
+	    }
+	    bdp->pname = NULL;
+	    bdp->qname = NULL;
+	}
+	av = _free(av);
+	s = _free(s);
+	badDepsInitialized++;
+    }
+
+    if (badDeps != NULL)
+    for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++) {
+	if (!strcmp(rpmteN(p), bdp->pname) && !strcmp(rpmteN(q), bdp->qname))
+	    return 1;
+    }
+    return 0;
+}
+
+static inline const char * identifyDepend(rpmsenseFlags f)
+{
+    f = _notpre(f);
+    if (f & RPMSENSE_SCRIPT_PRE)
+	return "Requires(pre):";
+    if (f & RPMSENSE_SCRIPT_POST)
+	return "Requires(post):";
+    if (f & RPMSENSE_SCRIPT_PREUN)
+	return "Requires(preun):";
+    if (f & RPMSENSE_SCRIPT_POSTUN)
+	return "Requires(postun):";
+    if (f & RPMSENSE_SCRIPT_VERIFY)
+	return "Requires(verify):";
+    if (f & RPMSENSE_FIND_REQUIRES)
+	return "Requires(auto):";
+    return "Requires:";
+}
+
+/**
+ * Record next "q <- p" relation (i.e. "p" requires "q").
+ * @param ts		transaction set
+ * @param p		predecessor (i.e. package that "Requires: q")
+ * @param requires	relation
+ * @return		0 always
+ */
+static inline int addRelation(rpmts ts,
+			      rpmal al,
+			      rpmte p,
+			      rpmds requires)
+{
+    rpmte q;
+    struct tsortInfo_s * tsi_p, * tsi_q;
+    relation rel;
+    const char * Name;
+    rpmElementType teType = rpmteType(p);
+    rpmsenseFlags flags, dsflags;
+
+    if ((Name = rpmdsN(requires)) == NULL)
+	return 0;
+
+    dsflags = rpmdsFlags(requires);
+
+    /* Avoid rpmlib feature and package config dependencies */
+    if (dsflags & (RPMSENSE_RPMLIB|RPMSENSE_CONFIG))
+	return 0;
+
+    q = rpmalSatisfiesDepend(al, requires);
+
+    /* Avoid deps outside this transaction and self dependencies */
+    if (q == NULL || q == p)
+	return 0;
+
+    /* Avoid certain dependency relations. */
+    if (ignoreDep(ts, p, q))
+	return 0;
+
+    /* Erasures are reversed installs. */
+    if (teType == TR_REMOVED) {
+        rpmte r = p;
+        p = q;
+        q = r;
+	flags = isErasePreReq(dsflags);
+    } else {
+	flags = isInstallPreReq(dsflags);
+    }
+
+    /* map legacy prereq to pre/preun as needed */
+    if (isLegacyPreReq(dsflags)) {
+	flags |= (teType == TR_ADDED) ?
+		 RPMSENSE_SCRIPT_PRE : RPMSENSE_SCRIPT_PREUN;
+    }
+
+    tsi_p = rpmteTSI(p);
+    tsi_q = rpmteTSI(q);
+
+    /* if relation got already added just update the flags */
+    if (tsi_q->tsi_relations && tsi_q->tsi_relations->rel_suc == p) {
+	tsi_q->tsi_relations->rel_flags |= flags;
+	tsi_p->tsi_forward_relations->rel_flags |= flags;
+	return 0;
+    }
+
+    /* Record next "q <- p" relation (i.e. "p" requires "q"). */
+    if (p != q) {
+	/* bump p predecessor count */
+	rpmteTSI(p)->tsi_count++;
+    }
+
+    /* Save max. depth in dependency tree */
+    if (rpmteDepth(p) <= rpmteDepth(q))
+	(void) rpmteSetDepth(p, (rpmteDepth(q) + 1));
+    if (rpmteDepth(p) > ts->maxDepth)
+	ts->maxDepth = rpmteDepth(p);
+
+    rel = xcalloc(1, sizeof(*rel));
+    rel->rel_suc = p;
+    rel->rel_flags = flags;
+
+    rel->rel_next = rpmteTSI(q)->tsi_relations;
+    rpmteTSI(q)->tsi_relations = rel;
+    if (p != q) {
+	/* bump q successor count */
+	rpmteTSI(q)->tsi_qcnt++;
+    }
+
+    rel = xcalloc(1, sizeof(*rel));
+    rel->rel_suc = q;
+    rel->rel_flags = flags;
+
+    rel->rel_next = rpmteTSI(p)->tsi_forward_relations;
+    rpmteTSI(p)->tsi_forward_relations = rel;
+
+    return 0;
+}
+
+/**
+ * Add element to list sorting by tsi_qcnt.
+ * @param p		new element
+ * @retval qp		address of first element
+ * @retval rp		address of last element
+ * @param prefcolor
+ */
+static void addQ(rpmte p,
+		rpmte * qp,
+		rpmte * rp,
+		rpm_color_t prefcolor)
+{
+    rpmte q, qprev;
+
+    /* Mark the package as queued. */
+    rpmteTSI(p)->tsi_reqx = 1;
+
+    if ((*rp) == NULL) {	/* 1st element */
+	/* FIX: double indirection */
+	(*rp) = (*qp) = p;
+	return;
+    }
+
+    /* Find location in queue using metric tsi_qcnt. */
+    for (qprev = NULL, q = (*qp);
+	 q != NULL;
+	 qprev = q, q = rpmteTSI(q)->tsi_suc)
+    {
+	/* XXX Insure preferred color first. */
+	if (rpmteColor(p) != prefcolor && rpmteColor(p) != rpmteColor(q))
+	    continue;
+
+	if (rpmteTSI(q)->tsi_qcnt <= rpmteTSI(p)->tsi_qcnt)
+	    break;
+    }
+
+    if (qprev == NULL) {	/* insert at beginning of list */
+	rpmteTSI(p)->tsi_suc = q;
+	(*qp) = p;		/* new head */
+    } else if (q == NULL) {	/* insert at end of list */
+	rpmteTSI(qprev)->tsi_suc = p;
+	(*rp) = p;		/* new tail */
+    } else {			/* insert between qprev and q */
+	rpmteTSI(p)->tsi_suc = q;
+	rpmteTSI(qprev)->tsi_suc = p;
+    }
+}
+
+/* Search for SCCs and return an array last entry has a .size of 0 */
+static scc detectSCCs(rpmts ts)
+{
+    int index = 0;                /* DFS node number counter */
+    rpmte stack[ts->orderCount];  /* An empty stack of nodes */
+    int stackcnt = 0;
+    rpmtsi pi;
+    rpmte p;
+
+    int sccCnt = 2;
+    scc SCCs = xcalloc(ts->orderCount+3, sizeof(struct scc_s));
+
+    auto void tarjan(rpmte p);
+
+    void tarjan(rpmte p) {
+	tsortInfo tsi = rpmteTSI(p);
+	rpmte q;
+	tsortInfo tsi_q;
+	relation rel;
+
+        /* use negative index numbers */
+	index--;
+	/* Set the depth index for p */
+	tsi->tsi_SccIdx = index;
+	tsi->tsi_SccLowlink = index;
+
+	stack[stackcnt++] = p;                   /* Push p on the stack */
+	for (rel=tsi->tsi_relations; rel != NULL; rel=rel->rel_next) {
+	    /* Consider successors of p */
+	    q = rel->rel_suc;
+	    tsi_q = rpmteTSI(q);
+	    if (tsi_q->tsi_SccIdx > 0)
+		/* Ignore already found SCCs */
+		continue;
+	    if (tsi_q->tsi_SccIdx == 0){
+		/* Was successor q not yet visited? */
+		tarjan(q);                       /* Recurse */
+		/* negative index numers: use max as it is closer to 0 */
+		tsi->tsi_SccLowlink = (
+		    tsi->tsi_SccLowlink > tsi_q->tsi_SccLowlink
+		    ? tsi->tsi_SccLowlink : tsi_q->tsi_SccLowlink);
+	    } else {
+		tsi->tsi_SccLowlink = (
+		    tsi->tsi_SccLowlink > tsi_q->tsi_SccIdx
+		    ? tsi->tsi_SccLowlink : tsi_q->tsi_SccIdx);
+	    }
+	}
+
+	if (tsi->tsi_SccLowlink == tsi->tsi_SccIdx) {
+	    /* v is the root of an SCC? */
+	    if (stack[stackcnt-1] == p) {
+		/* ignore trivial SCCs */
+		q = stack[--stackcnt];
+		tsi_q = rpmteTSI(q);
+		tsi_q->tsi_SccIdx = 1;
+	    } else {
+		int stackIdx = stackcnt;
+		do {
+		    q = stack[--stackIdx];
+		    tsi_q = rpmteTSI(q);
+		    tsi_q->tsi_SccIdx = sccCnt;
+		} while (q != p);
+
+		stackIdx = stackcnt;
+		do {
+		    q = stack[--stackIdx];
+		    tsi_q = rpmteTSI(q);
+		    /* Calculate count for the SCC */
+		    SCCs[sccCnt].count += tsi_q->tsi_count;
+		    /* Subtract internal relations */
+		    for (rel=tsi_q->tsi_relations; rel != NULL;
+							rel=rel->rel_next) {
+			if (rel->rel_suc != q &&
+				rpmteTSI(rel->rel_suc)->tsi_SccIdx == sccCnt)
+			    SCCs[sccCnt].count--;
+		    }
+		} while (q != p);
+		SCCs[sccCnt].size = stackcnt - stackIdx;
+		/* copy members */
+		SCCs[sccCnt].members = xcalloc(SCCs[sccCnt].size,
+					       sizeof(rpmte));
+		memcpy(SCCs[sccCnt].members, stack + stackIdx,
+		       SCCs[sccCnt].size * sizeof(rpmte));
+		stackcnt = stackIdx;
+		sccCnt++;
+	    }
+	}
+    }
+
+    pi = rpmtsiInit(ts);
+    while ((p=rpmtsiNext(pi, 0)) != NULL) {
+	/* Start a DFS at each node */
+	if (rpmteTSI(p)->tsi_SccIdx == 0)
+	    tarjan(p);
+    }
+    pi = rpmtsiFree(pi);
+
+    SCCs = xrealloc(SCCs, (sccCnt+1)*sizeof(struct scc_s));
+    /* Debug output */
+    if (sccCnt > 2) {
+	int msglvl = (rpmtsFlags(ts) & RPMTRANS_FLAG_DEPLOOPS) ?
+		     RPMLOG_WARNING : RPMLOG_DEBUG;
+	rpmlog(msglvl, "%i Strongly Connected Components\n", sccCnt-2);
+	for (int i = 2; i < sccCnt; i++) {
+	    rpmlog(msglvl, "SCC #%i: requires %i packages\n",
+		   i, SCCs[i].count);
+	    /* loop over members */
+	    for (int j = 0; j < SCCs[i].size; j++) {
+		rpmlog(msglvl, "\t%s\n", rpmteNEVRA(SCCs[i].members[j]));
+		/* show relations between members */
+		rpmte member = SCCs[i].members[j];
+		relation rel = rpmteTSI(member)->tsi_forward_relations;
+		for (; rel != NULL; rel=rel->rel_next) {
+		    if (rpmteTSI(rel->rel_suc)->tsi_SccIdx!=i) continue;
+		    rpmlog(msglvl, "\t\t%s %s\n",
+			   rel->rel_flags ? "=>" : "->",
+			   rpmteNEVRA(rel->rel_suc));
+		}
+	    }
+	}
+    }
+    return SCCs;
+}
+
+static void collectTE(rpm_color_t prefcolor, rpmte q,
+		      rpmte * newOrder, int * newOrderCount,
+		      scc SCCs,
+		      rpmte * queue_end,
+		      rpmte * outer_queue,
+		      rpmte * outer_queue_end)
+{
+    int treex = rpmteTree(q);
+    int depth = rpmteDepth(q);
+    char deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+');
+    tsortInfo tsi = rpmteTSI(q);
+
+    rpmlog(RPMLOG_DEBUG, "%5d%5d%5d%5d%5d %*s%c%s\n",
+	   *newOrderCount, rpmteNpreds(q),
+	   rpmteTSI(q)->tsi_qcnt,
+	   treex, depth,
+	   (2 * depth), "",
+	   deptypechar,
+	   (rpmteNEVRA(q) ? rpmteNEVRA(q) : "???"));
+
+    (void) rpmteSetDegree(q, 0);
+
+    newOrder[*newOrderCount] = q;
+    (*newOrderCount)++;
+
+    /* T6. Erase relations. */
+    for (relation rel = rpmteTSI(q)->tsi_relations;
+	 				rel != NULL; rel = rel->rel_next) {
+	rpmte p = rel->rel_suc;
+	tsortInfo p_tsi = rpmteTSI(p);
+	/* ignore already collected packages */
+	if (p_tsi->tsi_SccIdx == 0) continue;
+	if (p == q) continue;
+
+	if (p && (--p_tsi->tsi_count) == 0) {
+
+	    (void) rpmteSetTree(p, treex);
+	    (void) rpmteSetDepth(p, depth+1);
+	    (void) rpmteSetParent(p, q);
+	    (void) rpmteSetDegree(q, rpmteDegree(q)+1);
+
+	    if (tsi->tsi_SccIdx > 1 && tsi->tsi_SccIdx != p_tsi->tsi_SccIdx) {
+                /* Relation point outside of this SCC: add to outside queue */
+		assert(outer_queue != NULL && outer_queue_end != NULL);
+		addQ(p, outer_queue, outer_queue_end, prefcolor);
+	    } else {
+		addQ(p, &tsi->tsi_suc, queue_end, prefcolor);
+	    }
+	}
+	if (p && p_tsi->tsi_SccIdx > 1 &&
+	                 p_tsi->tsi_SccIdx != rpmteTSI(q)->tsi_SccIdx) {
+	    if (--SCCs[p_tsi->tsi_SccIdx].count == 0) {
+		/* New SCC is ready, add this package as representative */
+
+		(void) rpmteSetTree(p, treex);
+		(void) rpmteSetDepth(p, depth+1);
+		(void) rpmteSetParent(p, q);
+		(void) rpmteSetDegree(q, rpmteDegree(q)+1);
+
+		if (outer_queue != NULL) {
+		    addQ(p, outer_queue, outer_queue_end, prefcolor);
+		} else {
+		    addQ(p, &rpmteTSI(q)->tsi_suc, queue_end, prefcolor);
+		}
+	    }
+	}
+    }
+    tsi->tsi_SccIdx = 0;
+}
+
+static void collectSCC(rpm_color_t prefcolor, rpmte p,
+		       rpmte * newOrder, int * newOrderCount,
+		       scc SCCs, rpmte * queue_end)
+{
+    int sccNr = rpmteTSI(p)->tsi_SccIdx;
+    struct scc_s SCC = SCCs[sccNr];
+    int i;
+    int start, end;
+    relation rel;
+
+    /* remove p from the outer queue */
+    rpmte outer_queue_start = rpmteTSI(p)->tsi_suc;
+    rpmteTSI(p)->tsi_suc = NULL;
+
+    /*
+     * Run a multi source Dijkstra's algorithm to find relations
+     * that can be zapped with least danger to pre reqs.
+     * As weight of the edges is always 1 it is not necessary to
+     * sort the vertices by distance as the queue gets them
+     * already in order
+    */
+
+    /* can use a simple queue as edge weights are always 1 */
+    rpmte * queue = xmalloc((SCC.size+1) * sizeof(rpmte));
+
+    /*
+     * Find packages that are prerequired and use them as
+     * starting points for the Dijkstra algorithm
+     */
+    start = end = 0;
+    for (i = 0; i < SCC.size; i++) {
+	rpmte q = SCC.members[i];
+	tsortInfo tsi = rpmteTSI(q);
+	tsi->tsi_SccLowlink = INT_MAX;
+	for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
+	    if (rel->rel_flags && rpmteTSI(rel->rel_suc)->tsi_SccIdx == sccNr) {
+		if (rel->rel_suc != q) {
+		    tsi->tsi_SccLowlink =  0;
+		    queue[end++] = q;
+		} else {
+		    tsi->tsi_SccLowlink =  INT_MAX/2;
+		}
+		break;
+	    }
+	}
+    }
+
+    if (start == end) { /* no regular prereqs; add self prereqs to queue */
+	for (i = 0; i < SCC.size; i++) {
+	    rpmte q = SCC.members[i];
+	    tsortInfo tsi = rpmteTSI(q);
+	    if (tsi->tsi_SccLowlink != INT_MAX) {
+		queue[end++] = q;
+	    }
+	}
+    }
+
+    /* Do Dijkstra */
+    while (start != end) {
+	rpmte q = queue[start++];
+	tsortInfo tsi = rpmteTSI(q);
+	for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
+	    tsortInfo next_tsi = rpmteTSI(rel->rel_suc);
+	    if (next_tsi->tsi_SccIdx != sccNr) continue;
+	    if (next_tsi->tsi_SccLowlink > tsi->tsi_SccLowlink+1) {
+		next_tsi->tsi_SccLowlink = tsi->tsi_SccLowlink + 1;
+		queue[end++] = rel->rel_suc;
+	    }
+	}
+    }
+    queue = _free(queue);
+
+
+    while (1) {
+	rpmte best = NULL;
+	rpmte inner_queue_start, inner_queue_end;
+	int best_score = 0;
+
+	/* select best candidate to start with */
+	for (int i = 0; i < SCC.size; i++) {
+	    rpmte q = SCC.members[i];
+	    tsortInfo tsi = rpmteTSI(q);
+	    if (tsi->tsi_SccIdx == 0) /* package already collected */
+		continue;
+	    if (tsi->tsi_SccLowlink >= best_score) {
+		best = q;
+		best_score = tsi->tsi_SccLowlink;
+	    }
+	}
+
+	if (best == NULL) /* done */
+	    break;
+
+	/* collect best candidate and all packages that get freed */
+	inner_queue_start = inner_queue_end = NULL;
+	addQ(best, &inner_queue_start, &inner_queue_end, prefcolor);
+
+	for (; inner_queue_start != NULL;
+	     inner_queue_start = rpmteTSI(inner_queue_start)->tsi_suc) {
+	    /* Mark the package as unqueued. */
+	    rpmteTSI(inner_queue_start)->tsi_reqx = 0;
+	    collectTE(prefcolor, inner_queue_start, newOrder, newOrderCount,
+		      SCCs, &inner_queue_end, &outer_queue_start, queue_end);
+	}
+    }
+
+    /* restore outer queue */
+    rpmteTSI(p)->tsi_suc = outer_queue_start;
+}
+
+int rpmtsOrder(rpmts ts)
+{
+    rpm_color_t prefcolor = rpmtsPrefColor(ts);
+    rpmtsi pi; rpmte p;
+    rpmte q;
+    rpmte r;
+    rpmte * newOrder;
+    int newOrderCount = 0;
+    int treex;
+    int rc;
+    rpmal erasedPackages = rpmalCreate(5, rpmtsColor(ts));
+    scc SCCs;
+
+    (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
+
+    /*
+     * XXX FIXME: this gets needlesly called twice on normal usage patterns,
+     * should track the need for generating the index somewhere
+     */
+    rpmalMakeIndex(ts->addedPackages);
+
+    /* Create erased package index. */
+    pi = rpmtsiInit(ts);
+    while ((p = rpmtsiNext(pi, TR_REMOVED)) != NULL) {
+        rpmalAdd(erasedPackages, p);
+    }
+    pi = rpmtsiFree(pi);
+    rpmalMakeIndex(erasedPackages);
+
+    pi = rpmtsiInit(ts);
+    while ((p = rpmtsiNext(pi, 0)) != NULL)
+	rpmteNewTSI(p);
+    pi = rpmtsiFree(pi);
+
+    /* Record relations. */
+    rpmlog(RPMLOG_DEBUG, "========== recording tsort relations\n");
+    pi = rpmtsiInit(ts);
+    while ((p = rpmtsiNext(pi, 0)) != NULL) {
+	rpmal al = (rpmteType(p) == TR_REMOVED) ? 
+		   erasedPackages : ts->addedPackages;
+	rpmds requires = rpmdsInit(rpmteDS(p, RPMTAG_REQUIRENAME));
+
+	while (rpmdsNext(requires) >= 0) {
+	    /* Record next "q <- p" relation (i.e. "p" requires "q"). */
+	    (void) addRelation(ts, al, p, requires);
+	}
+    }
+    pi = rpmtsiFree(pi);
+
+    /* Save predecessor count and mark tree roots. */
+    treex = 0;
+    pi = rpmtsiInit(ts);
+    while ((p = rpmtsiNext(pi, 0)) != NULL) {
+	int npreds = rpmteTSI(p)->tsi_count;
+
+	(void) rpmteSetNpreds(p, npreds);
+	(void) rpmteSetDepth(p, 1);
+
+	if (npreds == 0)
+	    (void) rpmteSetTree(p, treex++);
+	else
+	    (void) rpmteSetTree(p, -1);
+    }
+    pi = rpmtsiFree(pi);
+    ts->ntrees = treex;
+
+    newOrder = xcalloc(ts->orderCount, sizeof(*newOrder));
+    SCCs = detectSCCs(ts);
+
+    rpmlog(RPMLOG_DEBUG, "========== tsorting packages (order, #predecessors, #succesors, tree, depth)\n");
+
+    for (int i = 0; i < 2; i++) {
+	/* Do two separate runs: installs first - then erases */
+	int oType = !i ? TR_ADDED : TR_REMOVED;
+	q = r = NULL;
+	pi = rpmtsiInit(ts);
+	/* Scan for zeroes and add them to the queue */
+	while ((p = rpmtsiNext(pi, oType)) != NULL) {
+	    if (rpmteTSI(p)->tsi_count != 0)
+		continue;
+	    rpmteTSI(p)->tsi_suc = NULL;
+	    addQ(p, &q, &r, prefcolor);
+	}
+	pi = rpmtsiFree(pi);
+
+	/* Add one member of each leaf SCC */
+	for (int i = 2; SCCs[i].members != NULL; i++) {
+	    if (SCCs[i].count == 0 && rpmteType(SCCs[i].members[0]) == oType) {
+		p = SCCs[i].members[0];
+		rpmteTSI(p)->tsi_suc = NULL;
+		addQ(p, &q, &r, prefcolor);
+	    }
+	}
+
+	/* Process queue */
+	for (; q != NULL; q = rpmteTSI(q)->tsi_suc) {
+	    /* Mark the package as unqueued. */
+	    rpmteTSI(q)->tsi_reqx = 0;
+	    if (rpmteTSI(q)->tsi_SccIdx > 1) {
+		collectSCC(prefcolor, q, newOrder, &newOrderCount, SCCs, &r);
+	    } else {
+		collectTE(prefcolor, q, newOrder, &newOrderCount, SCCs, &r,
+			  NULL, NULL);
+	    }
+	}
+    }
+
+    /* Clean up tsort data */
+    pi = rpmtsiInit(ts);
+    while ((p = rpmtsiNext(pi, 0)) != NULL)
+	rpmteFreeTSI(p);
+    pi = rpmtsiFree(pi);
+
+    assert(newOrderCount == ts->orderCount);
+
+    ts->order = _free(ts->order);
+    ts->order = newOrder;
+    ts->orderAlloced = ts->orderCount;
+    rc = 0;
+
+    freeBadDeps();
+
+    for (int i = 2; SCCs[i].members != NULL; i++) {
+	free(SCCs[i].members);
+    }
+    free(SCCs);
+    rpmalFree(erasedPackages);
+
+    (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
+
+    return rc;
+}