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