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