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