src/order.c

   1 /*
   2  * Copyright (c) 2007-2015, SUSE LLC
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * order.c
  10  *
  11  * Transaction ordering
  12  */
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <unistd.h>
  17 #include <string.h>
  18 #include <assert.h>
  19
  20 #include "transaction.h"
  21 #include "bitmap.h"
  22 #include "pool.h"
  23 #include "repo.h"
  24 #include "util.h"
  25
  26 struct s_TransactionElement {
  27   Id p;         /* solvable id */
  28   Id edges;     /* pointer into edges data */
  29   Id mark;
  30 };
  31
  32 struct s_TransactionOrderdata {
  33   struct s_TransactionElement *tes;
  34   int ntes;
  35   Id *invedgedata;
  36   int ninvedgedata;
  37   Queue *cycles;
  38 };
  39
  40 #define TYPE_BROKEN     (1<<0)
  41 #define TYPE_CON        (1<<1)
  42
  43 #define TYPE_REQ_P      (1<<2)
  44 #define TYPE_PREREQ_P   (1<<3)
  45
  46 #define TYPE_SUG        (1<<4)
  47 #define TYPE_REC        (1<<5)
  48
  49 #define TYPE_REQ        (1<<6)
  50 #define TYPE_PREREQ     (1<<7)
  51
  52 #define TYPE_CYCLETAIL  (1<<16)
  53 #define TYPE_CYCLEHEAD  (1<<17)
  54
  55 #define EDGEDATA_BLOCK  127
  56
  57 void
  58 transaction_clone_orderdata(Transaction *trans, Transaction *srctrans)
  59 {
  60   struct s_TransactionOrderdata *od = srctrans->orderdata;
  61   if (!od)
  62     return;
  63   trans->orderdata = solv_calloc(1, sizeof(*trans->orderdata));
  64   trans->orderdata->tes = solv_memdup2(od->tes, od->ntes, sizeof(*od->tes));
  65   trans->orderdata->ntes = od->ntes;
  66   trans->orderdata->invedgedata = solv_memdup2(od->invedgedata, od->ninvedgedata, sizeof(Id));
  67   trans->orderdata->ninvedgedata = od->ninvedgedata;
  68   if (od->cycles)
  69     {
  70       trans->orderdata->cycles = solv_calloc(1, sizeof(Queue));
  71       queue_init_clone(trans->orderdata->cycles, od->cycles);
  72     }
  73 }
  74
  75 void
  76 transaction_free_orderdata(Transaction *trans)
  77 {
  78   if (trans->orderdata)
  79     {
  80       struct s_TransactionOrderdata *od = trans->orderdata;
  81       od->tes = solv_free(od->tes);
  82       od->invedgedata = solv_free(od->invedgedata);
  83       if (od->cycles)
  84         {
  85           queue_free(od->cycles);
  86           od->cycles = solv_free(od->cycles);
  87         }
  88       trans->orderdata = solv_free(trans->orderdata);
  89     }
  90 }
  91
  92 struct orderdata {
  93   Transaction *trans;
  94   struct s_TransactionElement *tes;
  95   int ntes;
  96   Id *edgedata;
  97   int nedgedata;
  98   Id *invedgedata;
  99
 100   Queue cycles;
 101   Queue cyclesdata;
 102   int ncycles;
 103 };
 104
 105 static int
 106 addteedge(struct orderdata *od, int from, int to, int type)
 107 {
 108   int i;
 109   struct s_TransactionElement *te;
 110
 111   if (from == to)
 112     return 0;
 113
 114   /* printf("edge %d(%s) -> %d(%s) type %x\n", from, pool_solvid2str(pool, od->tes[from].p), to, pool_solvid2str(pool, od->tes[to].p), type); */
 115
 116   te = od->tes + from;
 117   for (i = te->edges; od->edgedata[i]; i += 2)
 118     if (od->edgedata[i] == to)
 119       break;
 120   /* test of brokenness */
 121   if (type == TYPE_BROKEN)
 122     return od->edgedata[i] && (od->edgedata[i + 1] & TYPE_BROKEN) != 0 ? 1 : 0;
 123   if (od->edgedata[i])
 124     {
 125       od->edgedata[i + 1] |= type;
 126       return 0;
 127     }
 128   if (i + 1 == od->nedgedata)
 129     {
 130       /* printf("tail add %d\n", i - te->edges); */
 131       if (!i)
 132         te->edges = ++i;
 133       od->edgedata = solv_extend(od->edgedata, od->nedgedata, 3, sizeof(Id), EDGEDATA_BLOCK);
 134     }
 135   else
 136     {
 137       /* printf("extend %d\n", i - te->edges); */
 138       od->edgedata = solv_extend(od->edgedata, od->nedgedata, 3 + (i - te->edges), sizeof(Id), EDGEDATA_BLOCK);
 139       if (i > te->edges)
 140         memcpy(od->edgedata + od->nedgedata, od->edgedata + te->edges, sizeof(Id) * (i - te->edges));
 141       i = od->nedgedata + (i - te->edges);
 142       te->edges = od->nedgedata;
 143     }
 144   od->edgedata[i] = to;
 145   od->edgedata[i + 1] = type;
 146   od->edgedata[i + 2] = 0;      /* end marker */
 147   od->nedgedata = i + 3;
 148   return 0;
 149 }
 150
 151 static int
 152 addedge(struct orderdata *od, Id from, Id to, int type)
 153 {
 154   Transaction *trans = od->trans;
 155   Pool *pool = trans->pool;
 156   Solvable *s;
 157   struct s_TransactionElement *te;
 158   int i;
 159
 160   /* printf("addedge %d %d type %d\n", from, to, type); */
 161   s = pool->solvables + from;
 162   if (s->repo == pool->installed && trans->transaction_installed[from - pool->installed->start])
 163     {
 164       /* obsolete, map to install */
 165       if (trans->transaction_installed[from - pool->installed->start] > 0)
 166         from = trans->transaction_installed[from - pool->installed->start];
 167       else
 168         {
 169           int ret = 0;
 170           Queue ti;
 171           Id tibuf[5];
 172
 173           queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
 174           transaction_all_obs_pkgs(trans, from, &ti);
 175           for (i = 0; i < ti.count; i++)
 176             ret |= addedge(od, ti.elements[i], to, type);
 177           queue_free(&ti);
 178           return ret;
 179         }
 180     }
 181   s = pool->solvables + to;
 182   if (s->repo == pool->installed && trans->transaction_installed[to - pool->installed->start])
 183     {
 184       /* obsolete, map to install */
 185       if (trans->transaction_installed[to - pool->installed->start] > 0)
 186         to = trans->transaction_installed[to - pool->installed->start];
 187       else
 188         {
 189           int ret = 0;
 190           Queue ti;
 191           Id tibuf[5];
 192
 193           queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
 194           transaction_all_obs_pkgs(trans, to, &ti);
 195           for (i = 0; i < ti.count; i++)
 196             ret |= addedge(od, from, ti.elements[i], type);
 197           queue_free(&ti);
 198           return ret;
 199         }
 200     }
 201
 202   /* map from/to to te numbers */
 203   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
 204     if (te->p == to)
 205       break;
 206   if (i == od->ntes)
 207     return 0;
 208   to = i;
 209
 210   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
 211     if (te->p == from)
 212       break;
 213   if (i == od->ntes)
 214     return 0;
 215
 216   return addteedge(od, i, to, type);
 217 }
 218
 219 static inline int
 220 havescripts(Pool *pool, Id solvid)
 221 {
 222   Solvable *s = pool->solvables + solvid;
 223   const char *dep;
 224   if (s->requires)
 225     {
 226       Id req, *reqp;
 227       int inpre = 0;
 228       reqp = s->repo->idarraydata + s->requires;
 229       while ((req = *reqp++) != 0)
 230         {
 231           if (req == SOLVABLE_PREREQMARKER)
 232             {
 233               inpre = 1;
 234               continue;
 235             }
 236           if (!inpre)
 237             continue;
 238           dep = pool_id2str(pool, req);
 239           if (*dep == '/' && strcmp(dep, "/sbin/ldconfig") != 0)
 240             return 1;
 241         }
 242     }
 243   return 0;
 244 }
 245
 246 static void
 247 addsolvableedges(struct orderdata *od, Solvable *s)
 248 {
 249   Transaction *trans = od->trans;
 250   Pool *pool = trans->pool;
 251   Id p, p2, pp2;
 252   int i, j, pre, numins;
 253   Repo *installed = pool->installed;
 254   Solvable *s2;
 255   Queue depq;
 256   int provbyinst;
 257
 258 #if 0
 259   printf("addsolvableedges %s\n", pool_solvable2str(pool, s));
 260 #endif
 261   p = s - pool->solvables;
 262   queue_init(&depq);
 263   if (s->requires)
 264     {
 265       Id req, *reqp;
 266       reqp = s->repo->idarraydata + s->requires;
 267       pre = TYPE_REQ;
 268       while ((req = *reqp++) != 0)
 269         {
 270           if (req == SOLVABLE_PREREQMARKER)
 271             {
 272               pre = TYPE_PREREQ;
 273               continue;
 274             }
 275           queue_empty(&depq);
 276           numins = 0;   /* number of packages to be installed providing it */
 277           provbyinst = 0;       /* provided by kept package */
 278           FOR_PROVIDES(p2, pp2, req)
 279             {
 280               s2 = pool->solvables + p2;
 281               if (p2 == p)
 282                 {
 283                   depq.count = 0;       /* self provides */
 284                   break;
 285                 }
 286               if (s2->repo == installed && !MAPTST(&trans->transactsmap, p2))
 287                 {
 288                   provbyinst = 1;
 289                   continue;
 290                 }
 291               if (s2->repo != installed && !MAPTST(&trans->transactsmap, p2))
 292                 continue;               /* package stays uninstalled */
 293
 294               if (s->repo == installed)
 295                 {
 296                   /* s gets uninstalled */
 297                   queue_pushunique(&depq, p2);
 298                   if (s2->repo != installed)
 299                     numins++;
 300                 }
 301               else
 302                 {
 303                   if (s2->repo == installed)
 304                     continue;   /* s2 gets uninstalled */
 305                   queue_pushunique(&depq, p2);
 306                 }
 307             }
 308           if (provbyinst)
 309             {
 310               /* prune to harmless ->inst edges */
 311               for (i = j = 0; i < depq.count; i++)
 312                 if (pool->solvables[depq.elements[i]].repo != installed)
 313                   depq.elements[j++] = depq.elements[i];
 314               depq.count = j;
 315             }
 316
 317           if (numins && depq.count)
 318             {
 319               if (s->repo == installed)
 320                 {
 321                   for (i = 0; i < depq.count; i++)
 322                     {
 323                       if (pool->solvables[depq.elements[i]].repo == installed)
 324                         {
 325                           for (j = 0; j < depq.count; j++)
 326                             {
 327                               if (pool->solvables[depq.elements[j]].repo != installed)
 328                                 {
 329                                   if (trans->transaction_installed[depq.elements[i] - pool->installed->start] == depq.elements[j])
 330                                     continue;   /* no self edge */
 331 #if 0
 332                                   printf("add interrreq uninst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, depq.elements[i]), pool_dep2str(pool, req), pool_solvid2str(pool, depq.elements[j]));
 333 #endif
 334                                   addedge(od, depq.elements[i], depq.elements[j], pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
 335                                 }
 336                             }
 337                         }
 338                     }
 339                 }
 340               /* no mixed types, remove all deps on uninstalls */
 341               for (i = j = 0; i < depq.count; i++)
 342                 if (pool->solvables[depq.elements[i]].repo != installed)
 343                   depq.elements[j++] = depq.elements[i];
 344               depq.count = j;
 345             }
 346           for (i = 0; i < depq.count; i++)
 347             {
 348               p2 = depq.elements[i];
 349               if (pool->solvables[p2].repo != installed)
 350                 {
 351                   /* all elements of depq are installs, thus have different TEs */
 352                   if (pool->solvables[p].repo != installed)
 353                     {
 354 #if 0
 355                       printf("add inst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p), pool_dep2str(pool, req), pool_solvid2str(pool, p2));
 356 #endif
 357                       addedge(od, p, p2, pre);
 358                     }
 359                   else
 360                     {
 361 #if 0
 362                       printf("add uninst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p), pool_dep2str(pool, req), pool_solvid2str(pool, p2));
 363 #endif
 364                       addedge(od, p, p2, pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
 365                     }
 366                 }
 367               else
 368                 {
 369                   if (s->repo != installed)
 370                     continue;   /* no inst->uninst edges, please! */
 371
 372                   /* uninst -> uninst edge. Those make trouble. Only add if we must */
 373                   if (trans->transaction_installed[p - installed->start] && !havescripts(pool, p))
 374                     {
 375                       /* p is obsoleted by another package and has no scripts */
 376                       /* we assume that the obsoletor is good enough to replace p */
 377                       continue;
 378                     }
 379 #if 0
 380                   printf("add uninst->uninst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p), pool_dep2str(pool, req), pool_solvid2str(pool, p2));
 381 #endif
 382                   addedge(od, p2, p, pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
 383                 }
 384             }
 385         }
 386     }
 387   if (s->conflicts)
 388     {
 389       Id con, *conp;
 390       conp = s->repo->idarraydata + s->conflicts;
 391       while ((con = *conp++) != 0)
 392         {
 393           FOR_PROVIDES(p2, pp2, con)
 394             {
 395               if (p2 == p)
 396                 continue;
 397               s2 = pool->solvables + p2;
 398               if (!s2->repo)
 399                 continue;
 400               if (s->repo == installed)
 401                 {
 402                   if (s2->repo != installed && MAPTST(&trans->transactsmap, p2))
 403                     {
 404                       /* deinstall p before installing p2 */
 405 #if 0
 406                       printf("add conflict uninst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p2), pool_dep2str(pool, con), pool_solvid2str(pool, p));
 407 #endif
 408                       addedge(od, p2, p, TYPE_CON);
 409                     }
 410                 }
 411               else
 412                 {
 413                   if (s2->repo == installed && MAPTST(&trans->transactsmap, p2))
 414                     {
 415                       /* deinstall p2 before installing p */
 416 #if 0
 417                       printf("add conflict uninst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p), pool_dep2str(pool, con), pool_solvid2str(pool, p2));
 418 #endif
 419                       addedge(od, p, p2, TYPE_CON);
 420                     }
 421                 }
 422
 423             }
 424         }
 425     }
 426   if (s->recommends && s->repo != installed)
 427     {
 428       Id rec, *recp;
 429       recp = s->repo->idarraydata + s->recommends;
 430       while ((rec = *recp++) != 0)
 431         {
 432           queue_empty(&depq);
 433           FOR_PROVIDES(p2, pp2, rec)
 434             {
 435               s2 = pool->solvables + p2;
 436               if (p2 == p)
 437                 {
 438                   depq.count = 0;       /* self provides */
 439                   break;
 440                 }
 441               if (s2->repo == installed && !MAPTST(&trans->transactsmap, p2))
 442                 continue;
 443               if (s2->repo != installed && !MAPTST(&trans->transactsmap, p2))
 444                 continue;               /* package stays uninstalled */
 445               if (s2->repo != installed)
 446                 queue_pushunique(&depq, p2);
 447             }
 448           for (i = 0; i < depq.count; i++)
 449             {
 450               p2 = depq.elements[i];
 451               if (pool->solvables[p2].repo != installed)
 452                 {
 453 #if 0
 454                   printf("add recommends inst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p), pool_dep2str(pool, rec), pool_solvid2str(pool, p2));
 455 #endif
 456                   addedge(od, p, p2, TYPE_REC);
 457                 }
 458             }
 459         }
 460     }
 461   if (s->suggests && s->repo != installed)
 462     {
 463       Id sug, *sugp;
 464       sugp = s->repo->idarraydata + s->suggests;
 465       while ((sug = *sugp++) != 0)
 466         {
 467           queue_empty(&depq);
 468           FOR_PROVIDES(p2, pp2, sug)
 469             {
 470               s2 = pool->solvables + p2;
 471               if (p2 == p)
 472                 {
 473                   depq.count = 0;       /* self provides */
 474                   break;
 475                 }
 476               if (s2->repo == installed && !MAPTST(&trans->transactsmap, p2))
 477                 continue;
 478               if (s2->repo != installed && !MAPTST(&trans->transactsmap, p2))
 479                 continue;               /* package stays uninstalled */
 480               if (s2->repo != installed)
 481                 queue_pushunique(&depq, p2);
 482             }
 483           for (i = 0; i < depq.count; i++)
 484             {
 485               p2 = depq.elements[i];
 486               if (pool->solvables[p2].repo != installed)
 487                 {
 488 #if 0
 489                   printf("add suggests inst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p), pool_dep2str(pool, sug), pool_solvid2str(pool, p2));
 490 #endif
 491                   addedge(od, p, p2, TYPE_SUG);
 492                 }
 493             }
 494         }
 495     }
 496   if (s->repo == installed && solvable_lookup_idarray(s, SOLVABLE_TRIGGERS, &depq) && depq.count)
 497     {
 498       /* we're getting deinstalled/updated. Try to do this before our
 499        * triggers are hit */
 500       for (i = 0; i < depq.count; i++)
 501         {
 502           Id tri = depq.elements[i];
 503           FOR_PROVIDES(p2, pp2, tri)
 504             {
 505               if (p2 == p)
 506                 continue;
 507               s2 = pool->solvables + p2;
 508               if (!s2->repo)
 509                 continue;
 510               if (s2->name == s->name)
 511                 continue;       /* obsoleted anyway */
 512               if (s2->repo != installed && MAPTST(&trans->transactsmap, p2))
 513                 {
 514                   /* deinstall/update p before installing p2 */
 515 #if 0
 516                   printf("add trigger uninst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p2), pool_dep2str(pool, tri), pool_solvid2str(pool, p));
 517 #endif
 518                   addedge(od, p2, p, TYPE_CON);
 519                 }
 520             }
 521         }
 522     }
 523   queue_free(&depq);
 524 }
 525
 526
 527 /* break an edge in a cycle */
 528 static void
 529 breakcycle(struct orderdata *od, Id *cycle)
 530 {
 531   Pool *pool = od->trans->pool;
 532   Id ddegmin, ddegmax, ddeg;
 533   int k, l;
 534   struct s_TransactionElement *te;
 535
 536   l = 0;
 537   ddegmin = ddegmax = 0;
 538   for (k = 0; cycle[k + 1]; k += 2)
 539     {
 540       ddeg = od->edgedata[cycle[k + 1] + 1];
 541       if (ddeg > ddegmax)
 542         ddegmax = ddeg;
 543       if (!k || ddeg < ddegmin)
 544         {
 545           l = k;
 546           ddegmin = ddeg;
 547           continue;
 548         }
 549       if (ddeg == ddegmin)
 550         {
 551           if (havescripts(pool, od->tes[cycle[l]].p) && !havescripts(pool, od->tes[cycle[k]].p))
 552             {
 553               /* prefer k, as l comes from a package with contains scriptlets */
 554               l = k;
 555               continue;
 556             }
 557           /* same edge value, check for prereq */
 558         }
 559     }
 560
 561   /* record brkoen cycle starting with the tail */
 562   queue_push(&od->cycles, od->cyclesdata.count);                /* offset into data */
 563   queue_push(&od->cycles, k / 2);                               /* cycle elements */
 564   queue_push(&od->cycles, od->edgedata[cycle[l + 1] + 1]);      /* broken edge */
 565   queue_push(&od->cycles, (ddegmax << 16) | ddegmin);           /* max/min values */
 566   od->ncycles++;
 567   for (k = l;;)
 568     {
 569       k += 2;
 570       if (!cycle[k + 1])
 571         k = 0;
 572       queue_push(&od->cyclesdata, cycle[k]);
 573       if (k == l)
 574         break;
 575     }
 576   queue_push(&od->cyclesdata, 0);       /* mark end */
 577
 578   /* break that edge */
 579   od->edgedata[cycle[l + 1] + 1] |= TYPE_BROKEN;
 580
 581 #if 1
 582   if (ddegmin < TYPE_REQ)
 583     return;
 584 #endif
 585
 586   /* cycle recorded, print it */
 587   if (ddegmin >= TYPE_REQ && (ddegmax & TYPE_PREREQ) != 0)
 588     POOL_DEBUG(SOLV_DEBUG_STATS, "CRITICAL ");
 589   POOL_DEBUG(SOLV_DEBUG_STATS, "cycle: --> ");
 590   for (k = 0; cycle[k + 1]; k += 2)
 591     {
 592       te = od->tes + cycle[k];
 593       if ((od->edgedata[cycle[k + 1] + 1] & TYPE_BROKEN) != 0)
 594         POOL_DEBUG(SOLV_DEBUG_STATS, "%s ##%x##> ", pool_solvid2str(pool, te->p), od->edgedata[cycle[k + 1] + 1]);
 595       else
 596         POOL_DEBUG(SOLV_DEBUG_STATS, "%s --%x--> ", pool_solvid2str(pool, te->p), od->edgedata[cycle[k + 1] + 1]);
 597     }
 598   POOL_DEBUG(SOLV_DEBUG_STATS, "\n");
 599 }
 600
 601 static inline void
 602 dump_tes(struct orderdata *od)
 603 {
 604   Pool *pool = od->trans->pool;
 605   int i, j;
 606   Queue obsq;
 607   struct s_TransactionElement *te, *te2;
 608
 609   queue_init(&obsq);
 610   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
 611     {
 612       Solvable *s = pool->solvables + te->p;
 613       POOL_DEBUG(SOLV_DEBUG_RESULT, "TE %4d: %c%s\n", i, s->repo == pool->installed ? '-' : '+', pool_solvable2str(pool, s));
 614       if (s->repo != pool->installed)
 615         {
 616           queue_empty(&obsq);
 617           transaction_all_obs_pkgs(od->trans, te->p, &obsq);
 618           for (j = 0; j < obsq.count; j++)
 619             POOL_DEBUG(SOLV_DEBUG_RESULT, "         -%s\n", pool_solvid2str(pool, obsq.elements[j]));
 620         }
 621       for (j = te->edges; od->edgedata[j]; j += 2)
 622         {
 623           te2 = od->tes + od->edgedata[j];
 624           if ((od->edgedata[j + 1] & TYPE_BROKEN) == 0)
 625             POOL_DEBUG(SOLV_DEBUG_RESULT, "       --%x--> TE %4d: %s\n", od->edgedata[j + 1], od->edgedata[j], pool_solvid2str(pool, te2->p));
 626           else
 627             POOL_DEBUG(SOLV_DEBUG_RESULT, "       ##%x##> TE %4d: %s\n", od->edgedata[j + 1], od->edgedata[j], pool_solvid2str(pool, te2->p));
 628         }
 629     }
 630 }
 631
 632 static void
 633 reachable(struct orderdata *od, Id i)
 634 {
 635   struct s_TransactionElement *te = od->tes + i;
 636   int j, k;
 637
 638   if (te->mark != 0)
 639     return;
 640   te->mark = 1;
 641   for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
 642     {
 643       if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
 644         continue;
 645       if (!od->tes[k].mark)
 646         reachable(od, k);
 647       if (od->tes[k].mark == 2)
 648         {
 649           te->mark = 2;
 650           return;
 651         }
 652     }
 653   te->mark = -1;
 654 }
 655
 656 static void
 657 addcycleedges(struct orderdata *od, Id *cycle, Queue *todo)
 658 {
 659 #if 0
 660   Transaction *trans = od->trans;
 661   Pool *pool = trans->pool;
 662 #endif
 663   struct s_TransactionElement *te;
 664   int i, j, k, tail;
 665   int head;
 666
 667 #if 0
 668   printf("addcycleedges\n");
 669   for (i = 0; (j = cycle[i]) != 0; i++)
 670     printf("cycle %s\n", pool_solvid2str(pool, od->tes[j].p));
 671 #endif
 672
 673   /* first add all the tail cycle edges */
 674
 675   /* see what we can reach from the cycle */
 676   queue_empty(todo);
 677   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
 678     te->mark = 0;
 679   for (i = 0; (j = cycle[i]) != 0; i++)
 680     {
 681       od->tes[j].mark = -1;
 682       queue_push(todo, j);
 683     }
 684   while (todo->count)
 685     {
 686       i = queue_pop(todo);
 687       te = od->tes + i;
 688       if (te->mark > 0)
 689         continue;
 690       te->mark = te->mark < 0 ? 2 : 1;
 691       for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
 692         {
 693           if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
 694             continue;
 695           if (od->tes[k].mark > 0)
 696             continue;   /* no need to visit again */
 697           queue_push(todo, k);
 698         }
 699     }
 700   /* now all cycle TEs are marked with 2, all TEs reachable
 701    * from the cycle are marked with 1 */
 702   tail = cycle[0];
 703   od->tes[tail].mark = 1;       /* no need to add edges */
 704
 705   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
 706     {
 707       if (te->mark)
 708         continue;       /* reachable from cycle */
 709       for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
 710         {
 711           if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
 712             continue;
 713           if (od->tes[k].mark != 2)
 714             continue;
 715           /* We found an edge to the cycle. Add an extra edge to the tail */
 716           /* the TE was not reachable, so we're not creating a new cycle! */
 717 #if 0
 718           printf("adding TO TAIL cycle edge %d->%d %s->%s!\n", i, tail, pool_solvid2str(pool, od->tes[i].p), pool_solvid2str(pool, od->tes[tail].p));
 719 #endif
 720           j -= te->edges;       /* in case we move */
 721           addteedge(od, i, tail, TYPE_CYCLETAIL);
 722           j += te->edges;
 723           break;        /* one edge is enough */
 724         }
 725     }
 726
 727   /* now add all head cycle edges */
 728
 729   /* reset marks */
 730   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
 731     te->mark = 0;
 732   head = 0;
 733   for (i = 0; (j = cycle[i]) != 0; i++)
 734     {
 735       head = j;
 736       od->tes[j].mark = 2;
 737     }
 738   /* first the head to save some time */
 739   te = od->tes + head;
 740   for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
 741     {
 742       if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
 743         continue;
 744       if (!od->tes[k].mark)
 745         reachable(od, k);
 746       if (od->tes[k].mark == -1)
 747         od->tes[k].mark = -2;   /* no need for another edge */
 748     }
 749   for (i = 0; cycle[i] != 0; i++)
 750     {
 751       if (cycle[i] == head)
 752         break;
 753       te = od->tes + cycle[i];
 754       for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
 755         {
 756           if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
 757             continue;
 758           /* see if we can reach a cycle TE from k */
 759           if (!od->tes[k].mark)
 760             reachable(od, k);
 761           if (od->tes[k].mark == -1)
 762             {
 763 #if 0
 764               printf("adding FROM HEAD cycle edge %d->%d %s->%s [%s]!\n", head, k, pool_solvid2str(pool, od->tes[head].p), pool_solvid2str(pool, od->tes[k].p), pool_solvid2str(pool, od->tes[cycle[i]].p));
 765 #endif
 766               addteedge(od, head, k, TYPE_CYCLEHEAD);
 767               od->tes[k].mark = -2;     /* no need to add that one again */
 768             }
 769         }
 770     }
 771 }
 772
 773 void
 774 transaction_order(Transaction *trans, int flags)
 775 {
 776   Pool *pool = trans->pool;
 777   Queue *tr = &trans->steps;
 778   Repo *installed = pool->installed;
 779   Id p;
 780   Solvable *s;
 781   int i, j, k, numte, numedge;
 782   struct orderdata od;
 783   struct s_TransactionElement *te;
 784   Queue todo, obsq, samerepoq, uninstq;
 785   int cycstart, cycel;
 786   Id *cycle;
 787   int oldcount;
 788   int start, now;
 789   Repo *lastrepo;
 790   int lastmedia;
 791   Id *temedianr;
 792
 793   start = now = solv_timems(0);
 794   POOL_DEBUG(SOLV_DEBUG_STATS, "ordering transaction\n");
 795   /* free old data if present */
 796   if (trans->orderdata)
 797     {
 798       struct s_TransactionOrderdata *od = trans->orderdata;
 799       od->tes = solv_free(od->tes);
 800       od->invedgedata = solv_free(od->invedgedata);
 801       trans->orderdata = solv_free(trans->orderdata);
 802     }
 803
 804   /* create a transaction element for every active component */
 805   numte = 0;
 806   for (i = 0; i < tr->count; i++)
 807     {
 808       p = tr->elements[i];
 809       s = pool->solvables + p;
 810       if (installed && s->repo == installed && trans->transaction_installed[p - installed->start])
 811         continue;
 812       numte++;
 813     }
 814   POOL_DEBUG(SOLV_DEBUG_STATS, "transaction elements: %d\n", numte);
 815   if (!numte)
 816     return;     /* nothing to do... */
 817
 818   numte++;      /* leave first one zero */
 819   memset(&od, 0, sizeof(od));
 820   od.trans = trans;
 821   od.ntes = numte;
 822   od.tes = solv_calloc(numte, sizeof(*od.tes));
 823   od.edgedata = solv_extend(0, 0, 1, sizeof(Id), EDGEDATA_BLOCK);
 824   od.edgedata[0] = 0;
 825   od.nedgedata = 1;
 826   queue_init(&od.cycles);
 827
 828   /* initialize TEs */
 829   for (i = 0, te = od.tes + 1; i < tr->count; i++)
 830     {
 831       p = tr->elements[i];
 832       s = pool->solvables + p;
 833       if (installed && s->repo == installed && trans->transaction_installed[p - installed->start])
 834         continue;
 835       te->p = p;
 836       te++;
 837     }
 838
 839   /* create dependency graph */
 840   for (i = 0; i < tr->count; i++)
 841     addsolvableedges(&od, pool->solvables + tr->elements[i]);
 842
 843   /* count edges */
 844   numedge = 0;
 845   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 846     for (j = te->edges; od.edgedata[j]; j += 2)
 847       numedge++;
 848   POOL_DEBUG(SOLV_DEBUG_STATS, "edges: %d, edge space: %d\n", numedge, od.nedgedata / 2);
 849   POOL_DEBUG(SOLV_DEBUG_STATS, "edge creation took %d ms\n", solv_timems(now));
 850
 851 #if 0
 852   dump_tes(&od);
 853 #endif
 854
 855   now = solv_timems(0);
 856   /* kill all cycles */
 857   queue_init(&todo);
 858   for (i = numte - 1; i > 0; i--)
 859     queue_push(&todo, i);
 860
 861   while (todo.count)
 862     {
 863       i = queue_pop(&todo);
 864       /* printf("- look at TE %d\n", i); */
 865       if (i < 0)
 866         {
 867           i = -i;
 868           od.tes[i].mark = 2;   /* done with that one */
 869           continue;
 870         }
 871       te = od.tes + i;
 872       if (te->mark == 2)
 873         continue;               /* already finished before */
 874       if (te->mark == 0)
 875         {
 876           int edgestovisit = 0;
 877           /* new node, visit edges */
 878           for (j = te->edges; (k = od.edgedata[j]) != 0; j += 2)
 879             {
 880               if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 881                 continue;
 882               if (od.tes[k].mark == 2)
 883                 continue;       /* no need to visit again */
 884               if (!edgestovisit++)
 885                 queue_push(&todo, -i);  /* end of edges marker */
 886               queue_push(&todo, k);
 887             }
 888           if (!edgestovisit)
 889             te->mark = 2;       /* no edges, done with that one */
 890           else
 891             te->mark = 1;       /* under investigation */
 892           continue;
 893         }
 894       /* oh no, we found a cycle */
 895       /* find start of cycle node (<0) */
 896       for (j = todo.count - 1; j >= 0; j--)
 897         if (todo.elements[j] == -i)
 898           break;
 899       assert(j >= 0);
 900       cycstart = j;
 901       /* build te/edge chain */
 902       k = cycstart;
 903       for (j = k; j < todo.count; j++)
 904         if (todo.elements[j] < 0)
 905           todo.elements[k++] = -todo.elements[j];
 906       cycel = k - cycstart;
 907       assert(cycel > 1);
 908       /* make room for edges, two extra element for cycle loop + terminating 0 */
 909       while (todo.count < cycstart + 2 * cycel + 2)
 910         queue_push(&todo, 0);
 911       cycle = todo.elements + cycstart;
 912       cycle[cycel] = i;         /* close the loop */
 913       cycle[2 * cycel + 1] = 0; /* terminator */
 914       for (k = cycel; k > 0; k--)
 915         {
 916           cycle[k * 2] = cycle[k];
 917           te = od.tes + cycle[k - 1];
 918           assert(te->mark == 1);
 919           te->mark = 0; /* reset investigation marker */
 920           /* printf("searching for edge from %d to %d\n", cycle[k - 1], cycle[k]); */
 921           for (j = te->edges; od.edgedata[j]; j += 2)
 922             if (od.edgedata[j] == cycle[k])
 923               break;
 924           assert(od.edgedata[j]);
 925           cycle[k * 2 - 1] = j;
 926         }
 927       /* now cycle looks like this: */
 928       /* te1 edge te2 edge te3 ... teN edge te1 0 */
 929       breakcycle(&od, cycle);
 930       /* restart with start of cycle */
 931       todo.count = cycstart + 1;
 932     }
 933   POOL_DEBUG(SOLV_DEBUG_STATS, "cycles broken: %d\n", od.ncycles);
 934   POOL_DEBUG(SOLV_DEBUG_STATS, "cycle breaking took %d ms\n", solv_timems(now));
 935
 936   now = solv_timems(0);
 937   /* now go through all broken cycles and create cycle edges to help
 938      the ordering */
 939    for (i = od.cycles.count - 4; i >= 0; i -= 4)
 940      {
 941        if (od.cycles.elements[i + 2] >= TYPE_REQ)
 942          addcycleedges(&od, od.cyclesdata.elements + od.cycles.elements[i], &todo);
 943      }
 944    for (i = od.cycles.count - 4; i >= 0; i -= 4)
 945      {
 946        if (od.cycles.elements[i + 2] < TYPE_REQ)
 947          addcycleedges(&od, od.cyclesdata.elements + od.cycles.elements[i], &todo);
 948      }
 949   POOL_DEBUG(SOLV_DEBUG_STATS, "cycle edge creation took %d ms\n", solv_timems(now));
 950
 951 #if 0
 952   dump_tes(&od);
 953 #endif
 954   /* all edges are finally set up and there are no cycles, now the easy part.
 955    * Create an ordered transaction */
 956   now = solv_timems(0);
 957   /* first invert all edges */
 958   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 959     te->mark = 1;       /* term 0 */
 960   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 961     {
 962       for (j = te->edges; od.edgedata[j]; j += 2)
 963         {
 964           if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 965             continue;
 966           od.tes[od.edgedata[j]].mark++;
 967         }
 968     }
 969   j = 1;
 970   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 971     {
 972       te->mark += j;
 973       j = te->mark;
 974     }
 975   POOL_DEBUG(SOLV_DEBUG_STATS, "invedge space: %d\n", j + 1);
 976   od.invedgedata = solv_calloc(j + 1, sizeof(Id));
 977   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 978     {
 979       for (j = te->edges; od.edgedata[j]; j += 2)
 980         {
 981           if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 982             continue;
 983           od.invedgedata[--od.tes[od.edgedata[j]].mark] = i;
 984         }
 985     }
 986   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 987     te->edges = te->mark;       /* edges now points into invedgedata */
 988   od.edgedata = solv_free(od.edgedata);
 989   od.nedgedata = j + 1;
 990
 991   /* now the final ordering */
 992   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 993     te->mark = 0;
 994   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 995     for (j = te->edges; od.invedgedata[j]; j++)
 996       od.tes[od.invedgedata[j]].mark++;
 997
 998   queue_init(&samerepoq);
 999   queue_init(&uninstq);
1000   queue_empty(&todo);
1001   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1002     if (te->mark == 0)
1003       {
1004         if (installed && pool->solvables[te->p].repo == installed)
1005           queue_push(&uninstq, i);
1006         else
1007           queue_push(&todo, i);
1008       }
1009   assert(todo.count > 0 || uninstq.count > 0);
1010   oldcount = tr->count;
1011   queue_empty(tr);
1012
1013   queue_init(&obsq);
1014
1015   lastrepo = 0;
1016   lastmedia = 0;
1017   temedianr = solv_calloc(numte, sizeof(Id));
1018   for (i = 1; i < numte; i++)
1019     {
1020       Solvable *s = pool->solvables + od.tes[i].p;
1021       if (installed && s->repo == installed)
1022         j = 1;
1023       else
1024         j = solvable_lookup_num(s, SOLVABLE_MEDIANR, 1);
1025       temedianr[i] = j;
1026     }
1027   for (;;)
1028     {
1029       /* select an TE i */
1030       if (uninstq.count)
1031         i = queue_shift(&uninstq);
1032       else if (samerepoq.count)
1033         i = queue_shift(&samerepoq);
1034       else if (todo.count)
1035         {
1036           /* find next repo/media */
1037           for (j = 0; j < todo.count; j++)
1038             {
1039               if (!j || temedianr[todo.elements[j]] < lastmedia)
1040                 {
1041                   i = j;
1042                   lastmedia = temedianr[todo.elements[j]];
1043                 }
1044             }
1045           lastrepo = pool->solvables[od.tes[todo.elements[i]].p].repo;
1046
1047           /* move all matching TEs to samerepoq */
1048           for (i = j = 0; j < todo.count; j++)
1049             {
1050               int k = todo.elements[j];
1051               if (temedianr[k] == lastmedia && pool->solvables[od.tes[k].p].repo == lastrepo)
1052                 queue_push(&samerepoq, k);
1053               else
1054                 todo.elements[i++] = k;
1055             }
1056           todo.count = i;
1057
1058           assert(samerepoq.count);
1059           i = queue_shift(&samerepoq);
1060         }
1061       else
1062         break;
1063
1064       te = od.tes + i;
1065       queue_push(tr, te->p);
1066 #if 0
1067 printf("do %s [%d]\n", pool_solvid2str(pool, te->p), temedianr[i]);
1068 #endif
1069       for (j = te->edges; od.invedgedata[j]; j++)
1070         {
1071           struct s_TransactionElement *te2 = od.tes + od.invedgedata[j];
1072           assert(te2->mark > 0);
1073           if (--te2->mark == 0)
1074             {
1075               Solvable *s = pool->solvables + te2->p;
1076 #if 0
1077 printf("free %s [%d]\n", pool_solvid2str(pool, te2->p), temedianr[od.invedgedata[j]]);
1078 #endif
1079               if (installed && s->repo == installed)
1080                 queue_push(&uninstq, od.invedgedata[j]);
1081               else if (s->repo == lastrepo && temedianr[od.invedgedata[j]] == lastmedia)
1082                 queue_push(&samerepoq, od.invedgedata[j]);
1083               else
1084                 queue_push(&todo, od.invedgedata[j]);
1085             }
1086         }
1087     }
1088   solv_free(temedianr);
1089   queue_free(&todo);
1090   queue_free(&samerepoq);
1091   queue_free(&uninstq);
1092   queue_free(&obsq);
1093   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1094     assert(te->mark == 0);
1095
1096   /* add back obsoleted packages */
1097   transaction_add_obsoleted(trans);
1098   assert(tr->count == oldcount);
1099
1100   POOL_DEBUG(SOLV_DEBUG_STATS, "creating new transaction took %d ms\n", solv_timems(now));
1101   POOL_DEBUG(SOLV_DEBUG_STATS, "transaction ordering took %d ms\n", solv_timems(start));
1102
1103   if ((flags & (SOLVER_TRANSACTION_KEEP_ORDERDATA | SOLVER_TRANSACTION_KEEP_ORDERCYCLES)) != 0)
1104     {
1105       struct s_TransactionOrderdata *tod;
1106       trans->orderdata = tod = solv_calloc(1, sizeof(*trans->orderdata));
1107       if ((flags & SOLVER_TRANSACTION_KEEP_ORDERCYCLES) != 0)
1108         {
1109           Queue *cycles = tod->cycles = solv_calloc(1, sizeof(Queue));
1110           queue_init_clone(cycles, &od.cyclesdata);
1111           /* map from tes to packages */
1112           for (i = 0; i < cycles->count; i++)
1113             if (cycles->elements[i])
1114               cycles->elements[i] = od.tes[cycles->elements[i]].p;
1115           queue_insertn(cycles, cycles->count, od.cycles.count, od.cycles.elements);
1116           queue_push(cycles, od.cycles.count / 4);
1117         }
1118       if ((flags & SOLVER_TRANSACTION_KEEP_ORDERDATA) != 0)
1119         {
1120           tod->tes = od.tes;
1121           tod->ntes = numte;
1122           tod->invedgedata = od.invedgedata;
1123           tod->ninvedgedata = od.nedgedata;
1124           od.tes = 0;
1125           od.invedgedata = 0;
1126         }
1127     }
1128   solv_free(od.tes);
1129   solv_free(od.invedgedata);
1130   queue_free(&od.cycles);
1131   queue_free(&od.cyclesdata);
1132 }
1133
1134
1135 int
1136 transaction_order_add_choices(Transaction *trans, Id chosen, Queue *choices)
1137 {
1138   int i, j;
1139   struct s_TransactionOrderdata *od = trans->orderdata;
1140   struct s_TransactionElement *te;
1141
1142   if (!od)
1143      return choices->count;
1144   if (!chosen)
1145     {
1146       /* initialization step */
1147       for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
1148         te->mark = 0;
1149       for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
1150         {
1151           for (j = te->edges; od->invedgedata[j]; j++)
1152             od->tes[od->invedgedata[j]].mark++;
1153         }
1154       for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
1155         if (!te->mark)
1156           queue_push(choices, te->p);
1157       return choices->count;
1158     }
1159   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
1160     if (te->p == chosen)
1161       break;
1162   if (i == od->ntes)
1163     return choices->count;
1164   if (te->mark > 0)
1165     {
1166       /* hey! out-of-order installation! */
1167       te->mark = -1;
1168     }
1169   for (j = te->edges; od->invedgedata[j]; j++)
1170     {
1171       te = od->tes + od->invedgedata[j];
1172       assert(te->mark > 0 || te->mark == -1);
1173       if (te->mark > 0 && --te->mark == 0)
1174         queue_push(choices, te->p);
1175     }
1176   return choices->count;
1177 }
1178
1179 void
1180 transaction_add_obsoleted(Transaction *trans)
1181 {
1182   Pool *pool = trans->pool;
1183   Repo *installed = pool->installed;
1184   Id p;
1185   Solvable *s;
1186   int i, j, k, max;
1187   Map done;
1188   Queue obsq, *steps;
1189
1190   if (!installed || !trans->steps.count)
1191     return;
1192   /* calculate upper bound */
1193   max = 0;
1194   FOR_REPO_SOLVABLES(installed, p, s)
1195     if (MAPTST(&trans->transactsmap, p))
1196       max++;
1197   if (!max)
1198     return;
1199   /* make room */
1200   steps = &trans->steps;
1201   queue_insertn(steps, 0, max, 0);
1202
1203   /* now add em */
1204   map_init(&done, installed->end - installed->start);
1205   queue_init(&obsq);
1206   for (j = 0, i = max; i < steps->count; i++)
1207     {
1208       p = trans->steps.elements[i];
1209       if (pool->solvables[p].repo == installed)
1210         {
1211           if (!trans->transaction_installed[p - pool->installed->start])
1212             trans->steps.elements[j++] = p;
1213           continue;
1214         }
1215       trans->steps.elements[j++] = p;
1216       queue_empty(&obsq);
1217       transaction_all_obs_pkgs(trans, p, &obsq);
1218       for (k = 0; k < obsq.count; k++)
1219         {
1220           p = obsq.elements[k];
1221           assert(p >= installed->start && p < installed->end);
1222           if (!MAPTST(&trans->transactsmap, p)) /* just in case */
1223             continue;
1224           if (MAPTST(&done, p - installed->start))
1225             continue;
1226           MAPSET(&done, p - installed->start);
1227           trans->steps.elements[j++] = p;
1228         }
1229     }
1230
1231   /* free unneeded space */
1232   queue_truncate(steps, j);
1233   map_free(&done);
1234   queue_free(&obsq);
1235 }
1236
1237 static void
1238 transaction_check_pkg(Transaction *trans, Id tepkg, Id pkg, Map *ins, Map *seen, int onlyprereq, Id noconfpkg, int depth)
1239 {
1240   Pool *pool = trans->pool;
1241   Id p, pp;
1242   Solvable *s;
1243   int good;
1244
1245   if (MAPTST(seen, pkg))
1246     return;
1247   MAPSET(seen, pkg);
1248   s = pool->solvables + pkg;
1249 #if 0
1250   printf("- %*s%c%s\n", depth * 2, "", s->repo == pool->installed ? '-' : '+', pool_solvable2str(pool, s));
1251 #endif
1252   if (s->requires)
1253     {
1254       Id req, *reqp;
1255       int inpre = 0;
1256       reqp = s->repo->idarraydata + s->requires;
1257       while ((req = *reqp++) != 0)
1258         {
1259           if (req == SOLVABLE_PREREQMARKER)
1260             {
1261               inpre = 1;
1262               continue;
1263             }
1264           if (onlyprereq && !inpre)
1265             continue;
1266           if (!strncmp(pool_id2str(pool, req), "rpmlib(", 7))
1267             continue;
1268           good = 0;
1269           /* first check kept packages, then freshly installed, then not yet uninstalled */
1270           FOR_PROVIDES(p, pp, req)
1271             {
1272               if (!MAPTST(ins, p))
1273                 continue;
1274               if (MAPTST(&trans->transactsmap, p))
1275                 continue;
1276               good++;
1277               transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
1278             }
1279           if (!good)
1280             {
1281               FOR_PROVIDES(p, pp, req)
1282                 {
1283                   if (!MAPTST(ins, p))
1284                     continue;
1285                   if (pool->solvables[p].repo == pool->installed)
1286                     continue;
1287                   good++;
1288                   transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
1289                 }
1290             }
1291           if (!good)
1292             {
1293               FOR_PROVIDES(p, pp, req)
1294                 {
1295                   if (!MAPTST(ins, p))
1296                     continue;
1297                   good++;
1298                   transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
1299                 }
1300             }
1301           if (!good)
1302             {
1303               POOL_DEBUG(SOLV_DEBUG_RESULT, "  %c%s: nothing provides %s needed by %c%s\n", pool->solvables[tepkg].repo == pool->installed ? '-' : '+', pool_solvid2str(pool, tepkg), pool_dep2str(pool, req), s->repo == pool->installed ? '-' : '+', pool_solvable2str(pool, s));
1304             }
1305         }
1306     }
1307 }
1308
1309 void
1310 transaction_check_order(Transaction *trans)
1311 {
1312   Pool *pool = trans->pool;
1313   Solvable *s;
1314   Id p, lastins;
1315   Map ins, seen;
1316   int i;
1317
1318   POOL_DEBUG(SOLV_DEBUG_RESULT, "\nchecking transaction order...\n");
1319   map_init(&ins, pool->nsolvables);
1320   map_init(&seen, pool->nsolvables);
1321   if (pool->installed)
1322     {
1323       FOR_REPO_SOLVABLES(pool->installed, p, s)
1324         MAPSET(&ins, p);
1325     }
1326   lastins = 0;
1327   for (i = 0; i < trans->steps.count; i++)
1328     {
1329       p = trans->steps.elements[i];
1330       s = pool->solvables + p;
1331       if (s->repo != pool->installed)
1332         lastins = p;
1333       if (s->repo != pool->installed)
1334         MAPSET(&ins, p);
1335       if (havescripts(pool, p))
1336         {
1337           MAPZERO(&seen);
1338           transaction_check_pkg(trans, p, p, &ins, &seen, 1, lastins, 0);
1339         }
1340       if (s->repo == pool->installed)
1341         MAPCLR(&ins, p);
1342     }
1343   map_free(&seen);
1344   map_free(&ins);
1345   POOL_DEBUG(SOLV_DEBUG_RESULT, "transaction order check done.\n");
1346 }
1347
1348 void
1349 transaction_order_get_cycleids(Transaction *trans, Queue *q, int minseverity)
1350 {
1351   struct s_TransactionOrderdata *od = trans->orderdata;
1352   Queue *cq;
1353   int i, cid, ncycles;
1354
1355   queue_empty(q);
1356   if (!od || !od->cycles || !od->cycles->count)
1357     return;
1358   cq = od->cycles;
1359   ncycles = cq->elements[cq->count - 1];
1360   i = cq->count - 1 - ncycles * 4;
1361   for (cid = 1; cid <= ncycles; cid++, i += 4)
1362     {
1363       if (minseverity)
1364         {
1365           int cmin = cq->elements[i + 3] & 0xffff;
1366           int cmax = (cq->elements[i + 3] >> 16) & 0xffff;
1367           if (minseverity >= SOLVER_ORDERCYCLE_NORMAL && cmin < TYPE_REQ)
1368             continue;
1369           if (minseverity >= SOLVER_ORDERCYCLE_CRITICAL && (cmax & TYPE_PREREQ) == 0)
1370             continue;
1371         }
1372       queue_push(q, cid);
1373     }
1374 }
1375
1376 int
1377 transaction_order_get_cycle(Transaction *trans, Id cid, Queue *q)
1378 {
1379   struct s_TransactionOrderdata *od = trans->orderdata;
1380   Queue *cq;
1381   int cmin, cmax, severity;
1382   int ncycles;
1383
1384   queue_empty(q);
1385   if (!od || !od->cycles || !od->cycles->count)
1386     return SOLVER_ORDERCYCLE_HARMLESS;
1387   cq = od->cycles;
1388   ncycles = cq->elements[cq->count - 1];
1389   if (cid < 1 || cid > ncycles)
1390     return SOLVER_ORDERCYCLE_HARMLESS;
1391   cid =  cq->count - 1 - 4 * (ncycles - cid + 1);
1392   cmin = cq->elements[cid + 3] & 0xffff;
1393   cmax = (cq->elements[cid + 3] >> 16) & 0xffff;
1394   if (cmin < TYPE_REQ)
1395     severity = SOLVER_ORDERCYCLE_HARMLESS;
1396   else if ((cmax & TYPE_PREREQ) == 0)
1397     severity = SOLVER_ORDERCYCLE_NORMAL;
1398   else
1399     severity = SOLVER_ORDERCYCLE_CRITICAL;
1400   if (q)
1401     queue_insertn(q, 0, cq->elements[cid + 1], cq->elements + cq->elements[cid]);
1402   return severity;
1403 }
1404