lib/order.c

   1 /** \ingroup rpmts
   2  * \file lib/depends.c
   3  */
   4
   5 #include "system.h"
   6
   7 #include <rpm/rpmtag.h>
   8 #include <rpm/rpmmacro.h>
   9 #include <rpm/rpmlog.h>
  10 #include <rpm/rpmds.h>
  11
  12 #include "lib/rpmte_internal.h" /* XXX tsortInfo_s */
  13 #include "lib/rpmts_internal.h"
  14
  15 #include "debug.h"
  16
  17 /*
  18  * Strongly Connected Components
  19  * set of packages (indirectly) requiering each other
  20  */
  21 struct scc_s {
  22     int count; /* # of external requires this SCC has */
  23     /* int qcnt;  # of external requires pointing to this SCC */
  24     int size;  /* # of members */
  25     tsortInfo * members;
  26 };
  27
  28 typedef struct scc_s * scc;
  29
  30 struct relation_s {
  31     tsortInfo   rel_suc;  // pkg requiring this package
  32     rpmsenseFlags rel_flags; // accumulated flags of the requirements
  33     struct relation_s * rel_next;
  34 };
  35
  36 typedef struct relation_s * relation;
  37
  38 struct tsortInfo_s {
  39     rpmte te;
  40     int      tsi_count;     // #pkgs this pkg requires
  41     int      tsi_qcnt;      // #pkgs requiring this package
  42     int      tsi_reqx;       // requires Idx/mark as (queued/loop)
  43     struct relation_s * tsi_relations;
  44     struct relation_s * tsi_forward_relations;
  45     tsortInfo tsi_suc;        // used for queuing (addQ)
  46     int      tsi_SccIdx;     // # of the SCC the node belongs to
  47                              // (1 for trivial SCCs)
  48     int      tsi_SccLowlink; // used for SCC detection
  49 };
  50
  51 static void rpmTSIFree(tsortInfo tsi)
  52 {
  53     relation rel;
  54
  55     while (tsi->tsi_relations != NULL) {
  56         rel = tsi->tsi_relations;
  57         tsi->tsi_relations = tsi->tsi_relations->rel_next;
  58         free(rel);
  59     }
  60     while (tsi->tsi_forward_relations != NULL) {
  61         rel = tsi->tsi_forward_relations;
  62         tsi->tsi_forward_relations = \
  63             tsi->tsi_forward_relations->rel_next;
  64         free(rel);
  65     }
  66 }
  67
  68 static inline int addSingleRelation(rpmte p,
  69                                     rpmte q,
  70                                     rpmsenseFlags dsflags)
  71 {
  72     struct tsortInfo_s *tsi_p, *tsi_q;
  73     relation rel;
  74     rpmElementType teType = rpmteType(p);
  75     rpmsenseFlags flags;
  76
  77     /* Avoid deps outside this transaction and self dependencies */
  78     if (q == NULL || q == p)
  79         return 0;
  80
  81     /* Erasures are reversed installs. */
  82     if (teType == TR_REMOVED) {
  83         rpmte r = p;
  84         p = q;
  85         q = r;
  86         flags = isErasePreReq(dsflags);
  87     } else {
  88         flags = isInstallPreReq(dsflags);
  89     }
  90
  91     /* map legacy prereq to pre/preun as needed */
  92     if (isLegacyPreReq(dsflags)) {
  93         flags |= (teType == TR_ADDED) ?
  94             RPMSENSE_SCRIPT_PRE : RPMSENSE_SCRIPT_PREUN;
  95     }
  96
  97     tsi_p = rpmteTSI(p);
  98     tsi_q = rpmteTSI(q);
  99
 100     /* if relation got already added just update the flags */
 101     if (tsi_q->tsi_relations && tsi_q->tsi_relations->rel_suc == tsi_p) {
 102         tsi_q->tsi_relations->rel_flags |= flags;
 103         tsi_p->tsi_forward_relations->rel_flags |= flags;
 104         return 0;
 105     }
 106
 107     /* Record next "q <- p" relation (i.e. "p" requires "q"). */
 108     if (p != q) {
 109         /* bump p predecessor count */
 110         tsi_p->tsi_count++;
 111     }
 112
 113     rel = xcalloc(1, sizeof(*rel));
 114     rel->rel_suc = tsi_p;
 115     rel->rel_flags = flags;
 116
 117     rel->rel_next = tsi_q->tsi_relations;
 118     tsi_q->tsi_relations = rel;
 119     if (p != q) {
 120         /* bump q successor count */
 121         tsi_q->tsi_qcnt++;
 122     }
 123
 124     rel = xcalloc(1, sizeof(*rel));
 125     rel->rel_suc = tsi_q;
 126     rel->rel_flags = flags;
 127
 128     rel->rel_next = tsi_p->tsi_forward_relations;
 129     tsi_p->tsi_forward_relations = rel;
 130
 131     return 0;
 132 }
 133
 134 /**
 135  * Record next "q <- p" relation (i.e. "p" requires "q").
 136  * @param ts            transaction set
 137  * @param p             predecessor (i.e. package that "Requires: q")
 138  * @param requires      relation
 139  * @return              0 always
 140  */
 141 static inline int addRelation(rpmts ts,
 142                               rpmal al,
 143                               rpmte p,
 144                               rpmds requires)
 145 {
 146     rpmte q;
 147     rpmsenseFlags dsflags;
 148
 149     dsflags = rpmdsFlags(requires);
 150
 151     /* Avoid dependendencies which are not relevant for ordering */
 152     if (dsflags & (RPMSENSE_RPMLIB|RPMSENSE_CONFIG|RPMSENSE_PRETRANS|RPMSENSE_POSTTRANS))
 153         return 0;
 154
 155     q = rpmalSatisfiesDepend(al, requires);
 156
 157     /* Avoid deps outside this transaction and self dependencies */
 158     if (q == NULL || q == p)
 159         return 0;
 160
 161     addSingleRelation(p, q, dsflags);
 162
 163     return 0;
 164 }
 165
 166 /*
 167  * Collections might have special ordering requirements. Notably
 168  * sepolicy collection requires having all the bits in the collection
 169  * close to each other. We try to ensure this by creating a strongly
 170  * connected component of such "grouped" collections, by introducing
 171  * an artificial relation loop across the all its members.
 172  */
 173 static int addCollRelations(rpmal al, rpmte p, ARGV_t *seenColls)
 174 {
 175     ARGV_const_t qcolls;
 176
 177     for (qcolls = rpmteCollections(p); qcolls && *qcolls; qcolls++) {
 178         char * flags;
 179         if (argvSearch(*seenColls, *qcolls, NULL))
 180             continue;
 181
 182         flags = rstrscat(NULL, "%{__collection_", *qcolls, "_flags}", NULL);
 183         if (rpmExpandNumeric(flags) & 0x1) {
 184             rpmte *tes = rpmalAllInCollection(al, *qcolls);
 185             for (rpmte *te = tes; te && *te; te++) {
 186                 rpmte next = (*(te + 1) != NULL) ? *(te + 1) : *tes;
 187                 addSingleRelation(*te, next, RPMSENSE_ANY);
 188             }
 189             _free(tes);
 190         }
 191         free(flags);
 192
 193         argvAdd(seenColls, *qcolls);
 194         argvSort(*seenColls, NULL);
 195     }
 196
 197     return 0;
 198 }
 199
 200 /**
 201  * Add element to list sorting by tsi_qcnt.
 202  * @param p             new element
 203  * @retval qp           address of first element
 204  * @retval rp           address of last element
 205  * @param prefcolor
 206  */
 207 static void addQ(tsortInfo p, tsortInfo * qp, tsortInfo * rp,
 208                 rpm_color_t prefcolor)
 209 {
 210     tsortInfo q, qprev;
 211     rpm_color_t pcolor = rpmteColor(p->te);
 212     int tailcond;
 213
 214     /* Mark the package as queued. */
 215     p->tsi_reqx = 1;
 216
 217     if ((*rp) == NULL) {        /* 1st element */
 218         /* FIX: double indirection */
 219         (*rp) = (*qp) = p;
 220         return;
 221     }
 222
 223     if (rpmteType(p->te) == TR_ADDED)
 224         tailcond = (pcolor && pcolor != prefcolor);
 225     else
 226         tailcond = (pcolor && pcolor == prefcolor);
 227
 228     /* Find location in queue using metric tsi_qcnt and color. */
 229     for (qprev = NULL, q = (*qp);
 230          q != NULL;
 231          qprev = q, q = q->tsi_suc)
 232     {
 233         /* Place preferred color towards queue head on install, tail on erase */
 234         if (tailcond && (pcolor != rpmteColor(q->te)))
 235             continue;
 236
 237         if (q->tsi_qcnt <= p->tsi_qcnt)
 238             break;
 239     }
 240
 241     if (qprev == NULL) {        /* insert at beginning of list */
 242         p->tsi_suc = q;
 243         (*qp) = p;              /* new head */
 244     } else if (q == NULL) {     /* insert at end of list */
 245         qprev->tsi_suc = p;
 246         (*rp) = p;              /* new tail */
 247     } else {                    /* insert between qprev and q */
 248         p->tsi_suc = q;
 249         qprev->tsi_suc = p;
 250     }
 251 }
 252
 253 typedef struct sccData_s {
 254     int index;                  /* DFS node number counter */
 255     tsortInfo *stack;           /* Stack of nodes */
 256     int stackcnt;               /* Stack top counter */
 257     scc SCCs;                   /* Array of SCC's found */
 258     int sccCnt;                 /* Number of SCC's found */
 259 } * sccData;
 260
 261 static void tarjan(sccData sd, tsortInfo tsi)
 262 {
 263     tsortInfo tsi_q;
 264     relation rel;
 265
 266     /* use negative index numbers */
 267     sd->index--;
 268     /* Set the depth index for p */
 269     tsi->tsi_SccIdx = sd->index;
 270     tsi->tsi_SccLowlink = sd->index;
 271
 272     sd->stack[sd->stackcnt++] = tsi;                   /* Push p on the stack */
 273     for (rel=tsi->tsi_relations; rel != NULL; rel=rel->rel_next) {
 274         /* Consider successors of p */
 275         tsi_q = rel->rel_suc;
 276         if (tsi_q->tsi_SccIdx > 0)
 277             /* Ignore already found SCCs */
 278             continue;
 279         if (tsi_q->tsi_SccIdx == 0){
 280             /* Was successor q not yet visited? */
 281             tarjan(sd, tsi_q);                       /* Recurse */
 282             /* negative index numers: use max as it is closer to 0 */
 283             tsi->tsi_SccLowlink = (
 284                 tsi->tsi_SccLowlink > tsi_q->tsi_SccLowlink
 285                 ? tsi->tsi_SccLowlink : tsi_q->tsi_SccLowlink);
 286         } else {
 287             tsi->tsi_SccLowlink = (
 288                 tsi->tsi_SccLowlink > tsi_q->tsi_SccIdx
 289                 ? tsi->tsi_SccLowlink : tsi_q->tsi_SccIdx);
 290         }
 291     }
 292
 293     if (tsi->tsi_SccLowlink == tsi->tsi_SccIdx) {
 294         /* v is the root of an SCC? */
 295         if (sd->stack[sd->stackcnt-1] == tsi) {
 296             /* ignore trivial SCCs */
 297             tsi_q = sd->stack[--sd->stackcnt];
 298             tsi_q->tsi_SccIdx = 1;
 299         } else {
 300             int stackIdx = sd->stackcnt;
 301             do {
 302                 tsi_q = sd->stack[--stackIdx];
 303                 tsi_q->tsi_SccIdx = sd->sccCnt;
 304             } while (tsi_q != tsi);
 305
 306             stackIdx = sd->stackcnt;
 307             do {
 308                 tsi_q = sd->stack[--stackIdx];
 309                 /* Calculate count for the SCC */
 310                 sd->SCCs[sd->sccCnt].count += tsi_q->tsi_count;
 311                 /* Subtract internal relations */
 312                 for (rel=tsi_q->tsi_relations; rel != NULL;
 313                                                     rel=rel->rel_next) {
 314                     if (rel->rel_suc != tsi_q &&
 315                             rel->rel_suc->tsi_SccIdx == sd->sccCnt)
 316                         sd->SCCs[sd->sccCnt].count--;
 317                 }
 318             } while (tsi_q != tsi);
 319             sd->SCCs[sd->sccCnt].size = sd->stackcnt - stackIdx;
 320             /* copy members */
 321             sd->SCCs[sd->sccCnt].members = xcalloc(sd->SCCs[sd->sccCnt].size,
 322                                            sizeof(tsortInfo));
 323             memcpy(sd->SCCs[sd->sccCnt].members, sd->stack + stackIdx,
 324                    sd->SCCs[sd->sccCnt].size * sizeof(tsortInfo));
 325             sd->stackcnt = stackIdx;
 326             sd->sccCnt++;
 327         }
 328     }
 329 }
 330
 331 /* Search for SCCs and return an array last entry has a .size of 0 */
 332 static scc detectSCCs(tsortInfo orderInfo, int nelem, int debugloops)
 333 {
 334     /* Set up data structures needed for the tarjan algorithm */
 335     scc SCCs = xcalloc(nelem+3, sizeof(*SCCs));
 336     tsortInfo *stack = xcalloc(nelem, sizeof(*stack));
 337     struct sccData_s sd = { 0, stack, 0, SCCs, 2 };
 338
 339     for (int i = 0; i < nelem; i++) {
 340         tsortInfo tsi = &orderInfo[i];
 341         /* Start a DFS at each node */
 342         if (tsi->tsi_SccIdx == 0)
 343             tarjan(&sd, tsi);
 344     }
 345
 346     free(stack);
 347
 348     SCCs = xrealloc(SCCs, (sd.sccCnt+1)*sizeof(struct scc_s));
 349
 350     /* Debug output */
 351     if (sd.sccCnt > 2) {
 352         int msglvl = debugloops ?  RPMLOG_WARNING : RPMLOG_DEBUG;
 353         rpmlog(msglvl, "%i Strongly Connected Components\n", sd.sccCnt-2);
 354         for (int i = 2; i < sd.sccCnt; i++) {
 355             rpmlog(msglvl, "SCC #%i: %i members (%i external dependencies)\n",
 356                            i-1, SCCs[i].size, SCCs[i].count);
 357
 358             /* loop over members */
 359             for (int j = 0; j < SCCs[i].size; j++) {
 360                 tsortInfo member = SCCs[i].members[j];
 361                 rpmlog(msglvl, "\t%s\n", rpmteNEVRA(member->te));
 362                 /* show relations between members */
 363                 relation rel = member->tsi_forward_relations;
 364                 for (; rel != NULL; rel=rel->rel_next) {
 365                     if (rel->rel_suc->tsi_SccIdx!=i) continue;
 366                     rpmlog(msglvl, "\t\t%s %s\n",
 367                            rel->rel_flags ? "=>" : "->",
 368                            rpmteNEVRA(rel->rel_suc->te));
 369                 }
 370             }
 371         }
 372     }
 373     return SCCs;
 374 }
 375
 376 static void collectTE(rpm_color_t prefcolor, tsortInfo q,
 377                       rpmte * newOrder, int * newOrderCount,
 378                       scc SCCs,
 379                       tsortInfo * queue_end,
 380                       tsortInfo * outer_queue,
 381                       tsortInfo * outer_queue_end)
 382 {
 383     char deptypechar = (rpmteType(q->te) == TR_REMOVED ? '-' : '+');
 384
 385     if (rpmIsDebug()) {
 386         int depth = 1;
 387         /* figure depth in tree for nice formatting */
 388         for (rpmte p = q->te; (p = rpmteParent(p)); depth++) {}
 389         rpmlog(RPMLOG_DEBUG, "%5d%5d%5d%5d %*s%c%s\n",
 390                *newOrderCount, q->tsi_count, q->tsi_qcnt,
 391                depth, (2 * depth), "",
 392                deptypechar, rpmteNEVRA(q->te));
 393     }
 394
 395     newOrder[*newOrderCount] = q->te;
 396     (*newOrderCount)++;
 397
 398     /* T6. Erase relations. */
 399     for (relation rel = q->tsi_relations; rel != NULL; rel = rel->rel_next) {
 400         tsortInfo p = rel->rel_suc;
 401         /* ignore already collected packages */
 402         if (p->tsi_SccIdx == 0) continue;
 403         if (p == q) continue;
 404
 405         if (p && (--p->tsi_count) == 0) {
 406             (void) rpmteSetParent(p->te, q->te);
 407
 408             if (q->tsi_SccIdx > 1 && q->tsi_SccIdx != p->tsi_SccIdx) {
 409                 /* Relation point outside of this SCC: add to outside queue */
 410                 assert(outer_queue != NULL && outer_queue_end != NULL);
 411                 addQ(p, outer_queue, outer_queue_end, prefcolor);
 412             } else {
 413                 addQ(p, &q->tsi_suc, queue_end, prefcolor);
 414             }
 415         }
 416         if (p && p->tsi_SccIdx > 1 &&
 417                          p->tsi_SccIdx != q->tsi_SccIdx) {
 418             if (--SCCs[p->tsi_SccIdx].count == 0) {
 419                 /* New SCC is ready, add this package as representative */
 420                 (void) rpmteSetParent(p->te, q->te);
 421
 422                 if (outer_queue != NULL) {
 423                     addQ(p, outer_queue, outer_queue_end, prefcolor);
 424                 } else {
 425                     addQ(p, &q->tsi_suc, queue_end, prefcolor);
 426                 }
 427             }
 428         }
 429     }
 430     q->tsi_SccIdx = 0;
 431 }
 432
 433 static void dijkstra(const struct scc_s *SCC, int sccNr)
 434 {
 435     int start, end;
 436     relation rel;
 437
 438     /* can use a simple queue as edge weights are always 1 */
 439     tsortInfo * queue = xmalloc((SCC->size+1) * sizeof(*queue));
 440
 441     /*
 442      * Find packages that are prerequired and use them as
 443      * starting points for the Dijkstra algorithm
 444      */
 445     start = end = 0;
 446     for (int i = 0; i < SCC->size; i++) {
 447         tsortInfo tsi = SCC->members[i];
 448         tsi->tsi_SccLowlink = INT_MAX;
 449         for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
 450             if (rel->rel_flags && rel->rel_suc->tsi_SccIdx == sccNr) {
 451                 if (rel->rel_suc != tsi) {
 452                     tsi->tsi_SccLowlink =  0;
 453                     queue[end++] = tsi;
 454                 } else {
 455                     tsi->tsi_SccLowlink =  INT_MAX/2;
 456                 }
 457                 break;
 458             }
 459         }
 460     }
 461
 462     if (start == end) { /* no regular prereqs; add self prereqs to queue */
 463         for (int i = 0; i < SCC->size; i++) {
 464             tsortInfo tsi = SCC->members[i];
 465             if (tsi->tsi_SccLowlink != INT_MAX) {
 466                 queue[end++] = tsi;
 467             }
 468         }
 469     }
 470
 471     /* Do Dijkstra */
 472     while (start != end) {
 473         tsortInfo tsi = queue[start++];
 474         for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
 475             tsortInfo next_tsi = rel->rel_suc;
 476             if (next_tsi->tsi_SccIdx != sccNr) continue;
 477             if (next_tsi->tsi_SccLowlink > tsi->tsi_SccLowlink+1) {
 478                 next_tsi->tsi_SccLowlink = tsi->tsi_SccLowlink + 1;
 479                 queue[end++] = rel->rel_suc;
 480             }
 481         }
 482     }
 483     free(queue);
 484 }
 485
 486 static void collectSCC(rpm_color_t prefcolor, tsortInfo p_tsi,
 487                        rpmte * newOrder, int * newOrderCount,
 488                        scc SCCs, tsortInfo * queue_end)
 489 {
 490     int sccNr = p_tsi->tsi_SccIdx;
 491     const struct scc_s * SCC = SCCs+sccNr;
 492
 493     /* remove p from the outer queue */
 494     tsortInfo outer_queue_start = p_tsi->tsi_suc;
 495     p_tsi->tsi_suc = NULL;
 496
 497     /*
 498      * Run a multi source Dijkstra's algorithm to find relations
 499      * that can be zapped with least danger to pre reqs.
 500      * As weight of the edges is always 1 it is not necessary to
 501      * sort the vertices by distance as the queue gets them
 502      * already in order
 503     */
 504     dijkstra(SCC, sccNr);
 505
 506     while (1) {
 507         tsortInfo best = NULL;
 508         tsortInfo inner_queue_start, inner_queue_end;
 509         int best_score = 0;
 510
 511         /* select best candidate to start with */
 512         for (int i = 0; i < SCC->size; i++) {
 513             tsortInfo tsi = SCC->members[i];
 514             if (tsi->tsi_SccIdx == 0) /* package already collected */
 515                 continue;
 516             if (tsi->tsi_SccLowlink >= best_score) {
 517                 best = tsi;
 518                 best_score = tsi->tsi_SccLowlink;
 519             }
 520         }
 521
 522         if (best == NULL) /* done */
 523             break;
 524
 525         /* collect best candidate and all packages that get freed */
 526         inner_queue_start = inner_queue_end = NULL;
 527         addQ(best, &inner_queue_start, &inner_queue_end, prefcolor);
 528
 529         for (; inner_queue_start != NULL;
 530              inner_queue_start = inner_queue_start->tsi_suc) {
 531             /* Mark the package as unqueued. */
 532             inner_queue_start->tsi_reqx = 0;
 533             collectTE(prefcolor, inner_queue_start, newOrder, newOrderCount,
 534                       SCCs, &inner_queue_end, &outer_queue_start, queue_end);
 535         }
 536     }
 537
 538     /* restore outer queue */
 539     p_tsi->tsi_suc = outer_queue_start;
 540 }
 541
 542 int rpmtsOrder(rpmts ts)
 543 {
 544     tsMembers tsmem = rpmtsMembers(ts);
 545     rpm_color_t prefcolor = rpmtsPrefColor(ts);
 546     rpmtsi pi; rpmte p;
 547     tsortInfo q, r;
 548     rpmte * newOrder;
 549     int newOrderCount = 0;
 550     int rc;
 551     rpmal erasedPackages;
 552     scc SCCs;
 553     int nelem = rpmtsNElements(ts);
 554     tsortInfo sortInfo = xcalloc(nelem, sizeof(struct tsortInfo_s));
 555     ARGV_t seenColls = NULL;
 556
 557     (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
 558
 559     /* Create erased package index. */
 560     erasedPackages = rpmtsCreateAl(ts, TR_REMOVED);
 561
 562     for (int i = 0; i < nelem; i++) {
 563         sortInfo[i].te = tsmem->order[i];
 564         rpmteSetTSI(tsmem->order[i], &sortInfo[i]);
 565     }
 566
 567     /* Record relations. */
 568     rpmlog(RPMLOG_DEBUG, "========== recording tsort relations\n");
 569     pi = rpmtsiInit(ts);
 570     while ((p = rpmtsiNext(pi, 0)) != NULL) {
 571         rpmal al = (rpmteType(p) == TR_REMOVED) ?
 572                    erasedPackages : tsmem->addedPackages;
 573         rpmds requires = rpmdsInit(rpmteDS(p, RPMTAG_REQUIRENAME));
 574         rpmds order = rpmdsInit(rpmteDS(p, RPMTAG_ORDERNAME));
 575
 576         while (rpmdsNext(requires) >= 0) {
 577             /* Record next "q <- p" relation (i.e. "p" requires "q"). */
 578             (void) addRelation(ts, al, p, requires);
 579         }
 580
 581         while (rpmdsNext(order) >= 0) {
 582             /* Record next "q <- p" ordering request */
 583             (void) addRelation(ts, al, p, order);
 584         }
 585
 586         addCollRelations(al, p, &seenColls);
 587     }
 588
 589     seenColls = argvFree(seenColls);
 590     rpmtsiFree(pi);
 591
 592     newOrder = xcalloc(tsmem->orderCount, sizeof(*newOrder));
 593     SCCs = detectSCCs(sortInfo, nelem, (rpmtsFlags(ts) & RPMTRANS_FLAG_DEPLOOPS));
 594
 595     rpmlog(RPMLOG_DEBUG, "========== tsorting packages (order, #predecessors, #succesors, depth)\n");
 596
 597     for (int i = 0; i < 2; i++) {
 598         /* Do two separate runs: installs first - then erases */
 599         int oType = !i ? TR_ADDED : TR_REMOVED;
 600         q = r = NULL;
 601         /* Scan for zeroes and add them to the queue */
 602         for (int e = 0; e < nelem; e++) {
 603             tsortInfo p = &sortInfo[e];
 604             if (rpmteType(p->te) != oType) continue;
 605             if (p->tsi_count != 0)
 606                 continue;
 607             p->tsi_suc = NULL;
 608             addQ(p, &q, &r, prefcolor);
 609         }
 610
 611         /* Add one member of each leaf SCC */
 612         for (int i = 2; SCCs[i].members != NULL; i++) {
 613             tsortInfo member = SCCs[i].members[0];
 614             if (SCCs[i].count == 0 && rpmteType(member->te) == oType) {
 615                 addQ(member, &q, &r, prefcolor);
 616             }
 617         }
 618
 619         while (q != NULL) {
 620             /* Mark the package as unqueued. */
 621             q->tsi_reqx = 0;
 622             if (q->tsi_SccIdx > 1) {
 623                 collectSCC(prefcolor, q, newOrder, &newOrderCount, SCCs, &r);
 624             } else {
 625                 collectTE(prefcolor, q, newOrder, &newOrderCount, SCCs, &r,
 626                           NULL, NULL);
 627             }
 628             q = q->tsi_suc;
 629         }
 630     }
 631
 632     /* Clean up tsort data */
 633     for (int i = 0; i < nelem; i++) {
 634         rpmteSetTSI(tsmem->order[i], NULL);
 635         rpmTSIFree(&sortInfo[i]);
 636     }
 637     free(sortInfo);
 638
 639     assert(newOrderCount == tsmem->orderCount);
 640
 641     tsmem->order = _free(tsmem->order);
 642     tsmem->order = newOrder;
 643     tsmem->orderAlloced = tsmem->orderCount;
 644     rc = 0;
 645
 646     for (int i = 2; SCCs[i].members != NULL; i++) {
 647         free(SCCs[i].members);
 648     }
 649     free(SCCs);
 650     rpmalFree(erasedPackages);
 651
 652     (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
 653
 654     return rc;
 655 }