Rewrite ordering

  - Detect strongly connected components (SCCs) using Tarjan's SCC algorithm
  - Use Dijkstra's algorithm to find the best relations to zap
  - Add forward relations for the Dijkstra's algorithm
  - Separate the per package ordering data and the relations

3 files changed, 432 insertions, 395 deletions

diff --git a/lib/depends.c b/lib/depends.c
index 326556f58..8a372a559 100644
--- a/lib/depends.c
+++ b/lib/depends.c
@@ -6,16 +6,16 @@
 
 #include <rpm/rpmcli.h>		/* XXX rpmcliPackagesTotal */
 
-#include <rpm/rpmlib.h>			/* rpmVersionCompare, rpmlib provides */
+#include <rpm/rpmlib.h>		/* rpmVersionCompare, rpmlib provides */
 #include <rpm/rpmtag.h>
-#include <rpm/rpmmacro.h>		/* XXX rpmExpand("%{_dependency_whiteout}" */
+#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/rpmte_internal.h"	/* XXX tsortInfo_s */
 #include "lib/rpmts_internal.h"
 
 #include "debug.h"
@@ -32,6 +32,19 @@ 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
@@ -779,26 +792,6 @@ static int ignoreDep(const rpmts ts, const rpmte p, const rpmte q)
     return 0;
 }
 
-/**
- * Recursively mark all nodes with their predecessors.
- * @param tsi		successor chain
- * @param q		predecessor
- */
-static void markLoop(tsortInfo tsi, rpmte q)
-{
-    rpmte p;
-
-    /* FIX: q is kept */
-    while (tsi != NULL && (p = tsi->tsi_suc) != NULL) {
-	tsi = tsi->tsi_next;
-	if (rpmteTSI(p)->tsi_chain != NULL)
-	    continue;
-	rpmteTSI(p)->tsi_chain = q;
-	if (rpmteTSI(p)->tsi_next != NULL)
-	    markLoop(rpmteTSI(p)->tsi_next, p);
-    }
-}
-
 static inline const char * identifyDepend(rpmsenseFlags f)
 {
     f = _notpre(f);
@@ -818,70 +811,6 @@ static inline const char * identifyDepend(rpmsenseFlags f)
 }
 
 /**
- * Find (and eliminate co-requisites) "q <- p" relation in dependency loop.
- * Search all successors of q for instance of p. Format the specific relation,
- * (e.g. p contains "Requires: q"). Unlink and free co-requisite (i.e.
- * pure Requires: dependencies) successor node(s).
- * @param q		sucessor (i.e. package required by p)
- * @param p		predecessor (i.e. package that "Requires: q")
- * @param requires	relation
- * @param zap		max. no. of co-requisites to remove (-1 is all)?
- * @retval nzaps	address of no. of relations removed
- * @param msglvl	message level at which to spew
- * @return		(possibly NULL) formatted "q <- p" releation (malloc'ed)
- */
-/* FIX: hack modifies, but -type disables */
-static char *
-zapRelation(rpmte q, rpmte p,
-		rpmds requires,
-		int zap, int * nzaps, int msglvl)
-{
-    tsortInfo tsi_prev;
-    tsortInfo tsi;
-    char *dp = NULL;
-
-    for (tsi_prev = rpmteTSI(q), tsi = rpmteTSI(q)->tsi_next;
-	 tsi != NULL;
-	/* XXX Note: the loop traverses "not found", break on "found". */
-	 tsi_prev = tsi, tsi = tsi->tsi_next)
-    {
-	rpmsenseFlags Flags;
-
-	if (tsi->tsi_suc != p)
-	    continue;
-
-	if (requires == NULL) continue;		/* XXX can't happen */
-
-	(void) rpmdsSetIx(requires, tsi->tsi_reqx);
-
-	Flags = rpmdsFlags(requires);
-
-	dp = rpmdsNewDNEVR( identifyDepend(Flags), requires);
-
-	/*
-	 * Attempt to unravel a dependency loop by eliminating Requires's.
-	 */
-	if (zap && !(isErasePreReq(Flags) || isInstallPreReq(Flags))) {
-	    rpmlog(msglvl,
-			_("removing %s \"%s\" from tsort relations.\n"),
-			(rpmteNEVRA(p) ?  rpmteNEVRA(p) : "???"), dp);
-	    rpmteTSI(p)->tsi_count--;
-	    if (tsi_prev) tsi_prev->tsi_next = tsi->tsi_next;
-	    tsi->tsi_next = NULL;
-	    tsi->tsi_suc = NULL;
-	    tsi = _free(tsi);
-	    if (nzaps)
-		(*nzaps)++;
-	    if (zap)
-		zap--;
-	}
-	/* XXX Note: the loop traverses "not found", get out now! */
-	break;
-    }
-    return dp;
-}
-
-/**
  * Record next "q <- p" relation (i.e. "p" requires "q").
  * @param ts		transaction set
  * @param p		predecessor (i.e. package that "Requires: q")
@@ -894,9 +823,11 @@ static inline int addRelation(rpmts ts,
 			      rpmds requires)
 {
     rpmte q;
-    tsortInfo tsi;
+    struct tsortInfo_s * tsi_p, * tsi_q;
+    relation rel;
     const char * Name;
     int teType = rpmteType(p);
+    int flags;
 
     if ((Name = rpmdsN(requires)) == NULL)
 	return 0;
@@ -923,31 +854,51 @@ static inline int addRelation(rpmts ts,
         rpmte r = p;
         p = q;
         q = r;
+	flags = isErasePreReq(rpmdsFlags(requires));
+    } else {
+	flags = isInstallPreReq(rpmdsFlags(requires));
     }
 
-    /* Avoid redundant relations. */
-    /* as we add all relations for p at once
-       only the latest added relation
-       can be from p already */
-    if (p==q || rpmteTSI(q)->tsi_suc == p)
+    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;
+    }
 
-    /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
-    rpmteTSI(p)->tsi_count++;			/* bump p predecessor count */
+    /* Record next "q <- p" relation (i.e. "p" requires "q"). */
+    if (p != q) {
+	/* bump p predecessor count */
+	rpmteTSI(p)->tsi_count++;
+    }
 
-    if (rpmteDepth(p) <= rpmteDepth(q))	/* Save max. depth in dependency tree */
+    /* 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);
 
-    tsi = xcalloc(1, sizeof(*tsi));
-    tsi->tsi_suc = 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;
 
-    tsi->tsi_reqx = rpmdsIx(requires);
+    rel->rel_next = rpmteTSI(p)->tsi_forward_relations;
+    rpmteTSI(p)->tsi_forward_relations = rel;
 
-    tsi->tsi_next = rpmteTSI(q)->tsi_next;
-    rpmteTSI(q)->tsi_next = tsi;
-    rpmteTSI(q)->tsi_qcnt++;			/* bump q successor count */
     return 0;
 }
 
@@ -999,30 +950,323 @@ static void addQ(rpmte 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)
 {
     rpmds requires;
-    rpmsenseFlags Flags;
     rpm_color_t prefcolor = rpmtsPrefColor(ts);
     rpmtsi pi; rpmte p;
-    rpmtsi qi; rpmte q;
-    rpmtsi ri; rpmte r;
-    tsortInfo tsi;
-    tsortInfo tsi_next;
-    int loopcheck;
+    rpmte q;
+    rpmte r;
     rpmte * newOrder;
     int newOrderCount = 0;
-    int npeer = 128;	/* XXX more than deep enough for now. */
-    int *peer = xcalloc(npeer, sizeof(*peer));
-    int _printed = 0;
-    char deptypechar;
-    rpm_loff_t tsbytes;
     int treex;
-    int depth;
-    int breadth;
-    int qlen;
     int rc;
     rpmal erasedPackages = rpmalCreate(5, rpmtsColor(ts));
+    scc SCCs;
 
     (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
 
@@ -1040,15 +1284,12 @@ int rpmtsOrder(rpmts ts)
     pi = rpmtsiFree(pi);
     rpmalMakeIndex(erasedPackages);
 
-
-    tsbytes = 0;
-
     pi = rpmtsiInit(ts);
     while ((p = rpmtsiNext(pi, 0)) != NULL)
 	rpmteNewTSI(p);
     pi = rpmtsiFree(pi);
 
-    /* Record all relations. */
+    /* Record relations. */
     rpmlog(RPMLOG_DEBUG, "========== recording tsort relations\n");
     pi = rpmtsiInit(ts);
     while ((p = rpmtsiNext(pi, 0)) != NULL) {
@@ -1056,56 +1297,17 @@ int rpmtsOrder(rpmts ts)
 	if ((requires = rpmteDS(p, RPMTAG_REQUIRENAME)) == NULL)
 	    continue;
 
-	/* T2. Next "q <- p" relation. */
-
-	/* First, do pre-requisites. */
 	requires = rpmdsInit(requires);
 	if (requires != NULL)
 	while (rpmdsNext(requires) >= 0) {
-
-	    Flags = rpmdsFlags(requires);
-
 	    switch (rpmteType(p)) {
 	    case TR_REMOVED:
-		/* Skip if not %preun/%postun requires or legacy prereq. */
-		if (!( isErasePreReq(Flags) || isLegacyPreReq(Flags) ) )
-		    continue;
-		/* T3. Record next "q <- p" relation (i.e. "p" requires "q") but reversed. */
+		/* Record next "q <- p" relation (i.e. "p" requires "q")
+		   but reversed. */
 		(void) addRelation(ts, erasedPackages, p, requires);
-
 		break;
 	    case TR_ADDED:
-		/* Skip if not %pre/%post requires or legacy prereq. */
-		if (!( isInstallPreReq(Flags) || isLegacyPreReq(Flags) ) )
-		    continue;
-		/* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
-		(void) addRelation(ts, ts->addedPackages, p, requires);
-		break;
-	    }
-	}
-
-	/* Then do co-requisites. */
-	requires = rpmdsInit(requires);
-	if (requires != NULL)
-	while (rpmdsNext(requires) >= 0) {
-
-	    Flags = rpmdsFlags(requires);
-
-	    switch (rpmteType(p)) {
-	    case TR_REMOVED:
-		/* Skip if %preun/%postun requires or legacy prereq. */
-		if (isInstallPreReq(Flags)
-		 ||  ( isErasePreReq(Flags) || isLegacyPreReq(Flags) ) )
-		    continue;
-		/* T3. Record next "q <- p" relation (i.e. "p" requires "q") but reversed. */
-		(void) addRelation(ts, erasedPackages, p, requires);
-		break;
-	    case TR_ADDED:
-		/* Skip if %pre/%post requires or legacy prereq. */
-		if (isErasePreReq(Flags)
-		 ||  ( isInstallPreReq(Flags) || isLegacyPreReq(Flags) ) )
-		    continue;
-		/* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
+		/* Record next "q <- p" relation (i.e. "p" requires "q"). */
 		(void) addRelation(ts, ts->addedPackages, p, requires);
 		break;
 	    }
@@ -1136,242 +1338,66 @@ int rpmtsOrder(rpmts ts)
     pi = rpmtsiFree(pi);
     ts->ntrees = treex;
 
-    /* T4. Scan for zeroes. */
-    rpmlog(RPMLOG_DEBUG, "========== tsorting packages (order, #predecessors, #succesors, tree, depth, breadth)\n");
-
-    /* Put installs first */
-    int oType = TR_ADDED;
     newOrder = xcalloc(ts->orderCount, sizeof(*newOrder));
-    loopcheck = ts->numAddedPackages;
-
-rescan:
-    if (pi != NULL) pi = rpmtsiFree(pi);
-    q = r = NULL;
-    qlen = 0;
-    pi = rpmtsiInit(ts);
-    while ((p = rpmtsiNext(pi, oType)) != NULL) {
-	if (rpmteTSI(p)->tsi_count != 0)
-	    continue;
-	rpmteTSI(p)->tsi_suc = NULL;
-	addQ(p, &q, &r, prefcolor);
-	qlen++;
-    }
-    pi = rpmtsiFree(pi);
-
-    /* T5. Output front of queue (T7. Remove from queue.) */
-    for (; q != NULL; q = rpmteTSI(q)->tsi_suc) {
-
-	/* Mark the package as unqueued. */
-	rpmteTSI(q)->tsi_reqx = 0;
-
-	if (oType != 0)
-	switch (rpmteType(q)) {
-	case TR_ADDED:
-	    if (!(oType & TR_ADDED))
-		continue;
-	    break;
-	case TR_REMOVED:
-	    if (!(oType & TR_REMOVED))
+    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;
-	    break;
-	default:
-	    continue;
-	    break;
+	    rpmteTSI(p)->tsi_suc = NULL;
+	    addQ(p, &q, &r, prefcolor);
 	}
-	deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+');
-
-	treex = rpmteTree(q);
-	depth = rpmteDepth(q);
-	breadth = ((depth < npeer) ? peer[depth]++ : 0);
-	(void) rpmteSetBreadth(q, breadth);
-
-	rpmlog(RPMLOG_DEBUG, "%5d%5d%5d%5d%5d%5d %*s%c%s\n",
-			newOrderCount, rpmteNpreds(q),
-			rpmteTSI(q)->tsi_qcnt,
-			treex, depth, breadth,
-			(2 * depth), "",
-			deptypechar,
-			(rpmteNEVRA(q) ? rpmteNEVRA(q) : "???"));
-
-	(void) rpmteSetDegree(q, 0);
-	tsbytes += rpmtePkgFileSize(q);
-
-	newOrder[newOrderCount] = q;
-
-	newOrderCount++;
-	qlen--;
-	loopcheck--;
-
-	/* T6. Erase relations. */
-	tsi_next = rpmteTSI(q)->tsi_next;
-	rpmteTSI(q)->tsi_next = NULL;
-	while ((tsi = tsi_next) != NULL) {
-	    tsi_next = tsi->tsi_next;
-	    tsi->tsi_next = NULL;
-	    p = tsi->tsi_suc;
-	    if (p && (--rpmteTSI(p)->tsi_count) <= 0) {
-
-		(void) rpmteSetTree(p, treex);
-		(void) rpmteSetDepth(p, depth+1);
-		(void) rpmteSetParent(p, q);
-		(void) rpmteSetDegree(q, rpmteDegree(q)+1);
+	pi = rpmtsiFree(pi);
 
-		/* XXX TODO: add control bit. */
+	/* 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, &rpmteTSI(q)->tsi_suc, &r, prefcolor);
-		qlen++;
+		addQ(p, &q, &r, prefcolor);
 	    }
-	    tsi = _free(tsi);
 	}
-	if (!_printed && loopcheck == qlen && rpmteTSI(q)->tsi_suc != NULL) {
-	    _printed++;
-	    (void) rpmtsUnorderedSuccessors(ts, newOrderCount);
-	    rpmlog(RPMLOG_DEBUG, "========== successors only (%llu bytes)\n",
-		   (long long)tsbytes);
-
-	    /* Relink the queue in presentation order. */
-	    tsi = rpmteTSI(q);
-	    pi = rpmtsiInit(ts);
-	    while ((p = rpmtsiNext(pi, oType)) != NULL) {
-		/* Is this element in the queue? */
-		if (rpmteTSI(p)->tsi_reqx == 0)
-		    continue;
-		tsi->tsi_suc = p;
-		tsi = rpmteTSI(p);
-	    }
-	    pi = rpmtsiFree(pi);
-	    tsi->tsi_suc = NULL;
-	}
-    }
 
-    /* T8. End of process. Check for loops. */
-    if (loopcheck != 0) {
-	int nzaps;
-
-	/* T9. Initialize predecessor chain. */
-	nzaps = 0;
-	qi = rpmtsiInit(ts);
-	while ((q = rpmtsiNext(qi, oType)) != NULL) {
-	    rpmteTSI(q)->tsi_chain = NULL;
+	/* Process queue */
+	for (; q != NULL; q = rpmteTSI(q)->tsi_suc) {
+	    /* Mark the package as unqueued. */
 	    rpmteTSI(q)->tsi_reqx = 0;
-	    /* Mark packages already sorted. */
-	    if (rpmteTSI(q)->tsi_count == 0)
-		rpmteTSI(q)->tsi_count = -1;
-	}
-	qi = rpmtsiFree(qi);
-
-	/* T10. Mark all packages with their predecessors. */
-	qi = rpmtsiInit(ts);
-	while ((q = rpmtsiNext(qi, oType)) != NULL) {
-	    if ((tsi = rpmteTSI(q)->tsi_next) == NULL)
-		continue;
-	    rpmteTSI(q)->tsi_next = NULL;
-	    markLoop(tsi, q);
-	    rpmteTSI(q)->tsi_next = tsi;
-	}
-	qi = rpmtsiFree(qi);
-
-	/* T11. Print all dependency loops. */
-	ri = rpmtsiInit(ts);
-	while ((r = rpmtsiNext(ri, oType)) != NULL)
-	{
-	    int printed;
-
-	    printed = 0;
-
-	    /* T12. Mark predecessor chain, looking for start of loop. */
-	    for (q = rpmteTSI(r)->tsi_chain; q != NULL;
-		 q = rpmteTSI(q)->tsi_chain)
-	    {
-		if (rpmteTSI(q)->tsi_reqx)
-		    break;
-		rpmteTSI(q)->tsi_reqx = 1;
-	    }
-
-	    /* T13. Print predecessor chain from start of loop. */
-	    while ((p = q) != NULL && (q = rpmteTSI(p)->tsi_chain) != NULL) {
-		char * dp;
-		const char *nevra;
-		int msglvl = (rpmtsFlags(ts) & RPMTRANS_FLAG_DEPLOOPS)
-			? RPMLOG_WARNING : RPMLOG_DEBUG;
-;
-
-		/* Unchain predecessor loop. */
-		rpmteTSI(p)->tsi_chain = NULL;
-
-		if (!printed) {
-		    rpmlog(msglvl, _("LOOP:\n"));
-		    printed = 1;
-		}
-
-		/* Find (and destroy if co-requisite) "q <- p" relation. */
-		if (oType==TR_ADDED) {
-		    requires = rpmteDS(p, RPMTAG_REQUIRENAME);
-		} else {
-		    // ERASE relations are reversed, use requires of target
-		    requires = rpmteDS(q, RPMTAG_REQUIRENAME);
-		}
-		requires = rpmdsInit(requires);
-		if (requires == NULL)
-		    continue;	/* XXX can't happen */
-		dp = zapRelation(q, p, requires, 1, &nzaps, msglvl);
-
-		/* Print next member of loop. */
-		nevra = rpmteNEVRA(p);
-		rpmlog(msglvl, "    %-40s %s\n", (nevra ? nevra : "???"),
-			(dp ? dp : "not found!?!"));
-
-		dp = _free(dp);
+	    if (rpmteTSI(q)->tsi_SccIdx > 1) {
+		collectSCC(prefcolor, q, newOrder, &newOrderCount, SCCs, &r);
+	    } else {
+		collectTE(prefcolor, q, newOrder, &newOrderCount, SCCs, &r,
+			  NULL, NULL);
 	    }
-
-	    /* Walk (and erase) linear part of predecessor chain as well. */
-	    for (p = r, q = rpmteTSI(r)->tsi_chain; q != NULL;
-		 p = q, q = rpmteTSI(q)->tsi_chain)
-	    {
-		/* Unchain linear part of predecessor loop. */
-		rpmteTSI(p)->tsi_chain = NULL;
-		rpmteTSI(p)->tsi_reqx = 0;
-	    }
-	}
-	ri = rpmtsiFree(ri);
-
-	/* If a relation was eliminated, then continue sorting. */
-	/* XXX TODO: add control bit. */
-	if (nzaps) {
-	    rpmlog(RPMLOG_DEBUG, "========== continuing tsort ...\n");
-	    goto rescan;
 	}
-
-	/* Return no. of packages that could not be ordered. */
-	rpmlog(RPMLOG_ERR, _("rpmtsOrder failed, %d elements remain\n"),
-			loopcheck);
-	rc = loopcheck;
-	goto exit;
     }
 
-    if (oType == TR_ADDED) {
-	/* done with ordering installs, now rerun for erases */
-	oType = TR_REMOVED;
-	loopcheck = ts->numRemovedPackages;
-	goto rescan;
-    }
-
-    /* Clean up tsort remnants (if any). */
+    /* Clean up tsort data */
     pi = rpmtsiInit(ts);
     while ((p = rpmtsiNext(pi, 0)) != NULL)
 	rpmteFreeTSI(p);
     pi = rpmtsiFree(pi);
 
-assert(newOrderCount == ts->orderCount);
+    assert(newOrderCount == ts->orderCount);
 
     ts->order = _free(ts->order);
     ts->order = newOrder;
     ts->orderAlloced = ts->orderCount;
     rc = 0;
 
-exit:
     freeBadDeps();
-    free(peer);
+
+    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);
diff --git a/lib/rpmte.c b/lib/rpmte.c
index e1ef0604a..c7ee82a33 100644
--- a/lib/rpmte.c
+++ b/lib/rpmte.c
@@ -524,19 +524,21 @@ tsortInfo rpmteTSI(rpmte te)
 
 void rpmteFreeTSI(rpmte te)
 {
-    if (te != NULL && rpmteTSI(te) != NULL) {
-	tsortInfo tsi;
-
-	/* Clean up tsort remnants (if any). */
-	while ((tsi = rpmteTSI(te)->tsi_next) != NULL) {
-	    rpmteTSI(te)->tsi_next = tsi->tsi_next;
-	    tsi->tsi_next = NULL;
-	    tsi = _free(tsi);
-	}
-	te->tsi = _free(te->tsi);
+    relation rel;
+    if (te == NULL || rpmteTSI(te) == NULL) return;
+
+    while (te->tsi->tsi_relations != NULL) {
+	rel = te->tsi->tsi_relations;
+	te->tsi->tsi_relations = te->tsi->tsi_relations->rel_next;
+	rel = _free(rel);
     }
-    /* FIX: te->tsi is NULL */
-    return;
+    while (te->tsi->tsi_forward_relations != NULL) {
+	rel = te->tsi->tsi_forward_relations;
+	te->tsi->tsi_forward_relations = \
+	    te->tsi->tsi_forward_relations->rel_next;
+	rel = _free(rel);
+    }
+    te->tsi = _free(te->tsi);
 }
 
 void rpmteNewTSI(rpmte te)
@@ -544,6 +546,7 @@ void rpmteNewTSI(rpmte te)
     if (te != NULL) {
 	rpmteFreeTSI(te);
 	te->tsi = xcalloc(1, sizeof(*te->tsi));
+	memset(te->tsi, 0, sizeof(*te->tsi));
     }
 }
 
diff --git a/lib/rpmte_internal.h b/lib/rpmte_internal.h
index 60c52bd67..50554e749 100644
--- a/lib/rpmte_internal.h
+++ b/lib/rpmte_internal.h
@@ -6,17 +6,25 @@
 /** \ingroup rpmte
  * Dependncy ordering information.
  */
+
+struct relation_s {
+    rpmte   rel_suc;  // pkg requiring this package
+    int rel_flags; // accumulated flags of the requirements
+    struct relation_s * rel_next;
+};
+
+typedef struct relation_s * relation;
+
 struct tsortInfo_s {
-    union {
-	int	count;
-	rpmte	suc;
-    } tsi_u;
-#define	tsi_count	tsi_u.count
-#define	tsi_suc		tsi_u.suc
-    struct tsortInfo_s * tsi_next;
-    rpmte tsi_chain;
-    int		tsi_reqx;
-    int		tsi_qcnt;
+    int	     tsi_count;     // #pkgs this pkg requires
+    int	     tsi_qcnt;      // #pkgs requiring this package
+    int	     tsi_reqx;       // requires Idx/mark as (queued/loop)
+    struct relation_s * tsi_relations;
+    struct relation_s * tsi_forward_relations;
+    rpmte    tsi_suc;        // used for queuing (addQ)
+    int      tsi_SccIdx;     // # of the SCC the node belongs to
+                             // (1 for trivial SCCs)
+    int      tsi_SccLowlink; // used for SCC detection
 };
 
 /**