src/order.c

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