lib/order.c

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