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 static int
 771 share_cycle(struct orderdata *od, Id p1, Id p2)
 772 {
 773   int i, seen = 0;
 774   for (i = 0; i < od->cyclesdata.count; i++)
 775     {
 776       Id p = od->cyclesdata.elements[i];
 777       if (p == 0)
 778         seen = 0;
 779       else if ((p == p1 || p == p2) && ++seen == 2)
 780         return 1;
 781     }
 782   return 0;
 783 }
 784
 785 void
 786 transaction_order(Transaction *trans, int flags)
 787 {
 788   Pool *pool = trans->pool;
 789   Queue *tr = &trans->steps;
 790   Repo *installed = pool->installed;
 791   Id p;
 792   Solvable *s;
 793   int i, j, k, numte, numedge;
 794   struct orderdata od;
 795   struct s_TransactionElement *te;
 796   Queue todo, obsq, samerepoq, uninstq;
 797   int cycstart, cycel;
 798   Id *cycle;
 799   int oldcount;
 800   int start, now;
 801   Repo *lastrepo;
 802   int lastmedia, lastte;
 803   Id *temedianr;
 804   unsigned char *incycle;
 805
 806   start = now = solv_timems(0);
 807   POOL_DEBUG(SOLV_DEBUG_STATS, "ordering transaction\n");
 808   /* free old data if present */
 809   if (trans->orderdata)
 810     {
 811       struct s_TransactionOrderdata *od = trans->orderdata;
 812       od->tes = solv_free(od->tes);
 813       od->invedgedata = solv_free(od->invedgedata);
 814       trans->orderdata = solv_free(trans->orderdata);
 815     }
 816
 817   /* create a transaction element for every active component */
 818   numte = 0;
 819   for (i = 0; i < tr->count; i++)
 820     {
 821       p = tr->elements[i];
 822       s = pool->solvables + p;
 823       if (installed && s->repo == installed && trans->transaction_installed[p - installed->start])
 824         continue;
 825       numte++;
 826     }
 827   POOL_DEBUG(SOLV_DEBUG_STATS, "transaction elements: %d\n", numte);
 828   if (!numte)
 829     return;     /* nothing to do... */
 830
 831   numte++;      /* leave first one zero */
 832   memset(&od, 0, sizeof(od));
 833   od.trans = trans;
 834   od.ntes = numte;
 835   od.tes = solv_calloc(numte, sizeof(*od.tes));
 836   od.edgedata = solv_extend(0, 0, 1, sizeof(Id), EDGEDATA_BLOCK);
 837   od.edgedata[0] = 0;
 838   od.nedgedata = 1;
 839   queue_init(&od.cycles);
 840
 841   /* initialize TEs */
 842   for (i = 0, te = od.tes + 1; i < tr->count; i++)
 843     {
 844       p = tr->elements[i];
 845       s = pool->solvables + p;
 846       if (installed && s->repo == installed && trans->transaction_installed[p - installed->start])
 847         continue;
 848       te->p = p;
 849       te++;
 850     }
 851
 852   /* create dependency graph */
 853   for (i = 0; i < tr->count; i++)
 854     addsolvableedges(&od, pool->solvables + tr->elements[i]);
 855
 856   /* count edges */
 857   numedge = 0;
 858   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 859     for (j = te->edges; od.edgedata[j]; j += 2)
 860       numedge++;
 861   POOL_DEBUG(SOLV_DEBUG_STATS, "edges: %d, edge space: %d\n", numedge, od.nedgedata / 2);
 862   POOL_DEBUG(SOLV_DEBUG_STATS, "edge creation took %d ms\n", solv_timems(now));
 863
 864 #if 0
 865   dump_tes(&od);
 866 #endif
 867
 868   now = solv_timems(0);
 869   /* kill all cycles */
 870   queue_init(&todo);
 871   for (i = numte - 1; i > 0; i--)
 872     queue_push(&todo, i);
 873
 874   while (todo.count)
 875     {
 876       i = queue_pop(&todo);
 877       /* printf("- look at TE %d\n", i); */
 878       if (i < 0)
 879         {
 880           i = -i;
 881           od.tes[i].mark = 2;   /* done with that one */
 882           continue;
 883         }
 884       te = od.tes + i;
 885       if (te->mark == 2)
 886         continue;               /* already finished before */
 887       if (te->mark == 0)
 888         {
 889           int edgestovisit = 0;
 890           /* new node, visit edges */
 891           for (j = te->edges; (k = od.edgedata[j]) != 0; j += 2)
 892             {
 893               if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 894                 continue;
 895               if (od.tes[k].mark == 2)
 896                 continue;       /* no need to visit again */
 897               if (!edgestovisit++)
 898                 queue_push(&todo, -i);  /* end of edges marker */
 899               queue_push(&todo, k);
 900             }
 901           if (!edgestovisit)
 902             te->mark = 2;       /* no edges, done with that one */
 903           else
 904             te->mark = 1;       /* under investigation */
 905           continue;
 906         }
 907       /* oh no, we found a cycle */
 908       /* find start of cycle node (<0) */
 909       for (j = todo.count - 1; j >= 0; j--)
 910         if (todo.elements[j] == -i)
 911           break;
 912       assert(j >= 0);
 913       cycstart = j;
 914       /* build te/edge chain */
 915       k = cycstart;
 916       for (j = k; j < todo.count; j++)
 917         if (todo.elements[j] < 0)
 918           todo.elements[k++] = -todo.elements[j];
 919       cycel = k - cycstart;
 920       assert(cycel > 1);
 921       /* make room for edges, two extra element for cycle loop + terminating 0 */
 922       while (todo.count < cycstart + 2 * cycel + 2)
 923         queue_push(&todo, 0);
 924       cycle = todo.elements + cycstart;
 925       cycle[cycel] = i;         /* close the loop */
 926       cycle[2 * cycel + 1] = 0; /* terminator */
 927       for (k = cycel; k > 0; k--)
 928         {
 929           cycle[k * 2] = cycle[k];
 930           te = od.tes + cycle[k - 1];
 931           assert(te->mark == 1);
 932           te->mark = 0; /* reset investigation marker */
 933           /* printf("searching for edge from %d to %d\n", cycle[k - 1], cycle[k]); */
 934           for (j = te->edges; od.edgedata[j]; j += 2)
 935             if (od.edgedata[j] == cycle[k])
 936               break;
 937           assert(od.edgedata[j]);
 938           cycle[k * 2 - 1] = j;
 939         }
 940       /* now cycle looks like this: */
 941       /* te1 edge te2 edge te3 ... teN edge te1 0 */
 942       breakcycle(&od, cycle);
 943       /* restart with start of cycle */
 944       todo.count = cycstart + 1;
 945     }
 946   POOL_DEBUG(SOLV_DEBUG_STATS, "cycles broken: %d\n", od.ncycles);
 947   POOL_DEBUG(SOLV_DEBUG_STATS, "cycle breaking took %d ms\n", solv_timems(now));
 948
 949   incycle = 0;
 950   if (od.cycles.count)
 951     {
 952       now = solv_timems(0);
 953       incycle = solv_calloc(numte, 1);
 954       /* now go through all broken cycles and create cycle edges to help
 955          the ordering */
 956       for (i = od.cycles.count - 4; i >= 0; i -= 4)
 957         {
 958           if (od.cycles.elements[i + 2] >= TYPE_REQ)
 959             addcycleedges(&od, od.cyclesdata.elements + od.cycles.elements[i], &todo);
 960         }
 961       for (i = od.cycles.count - 4; i >= 0; i -= 4)
 962         {
 963           if (od.cycles.elements[i + 2] < TYPE_REQ)
 964             addcycleedges(&od, od.cyclesdata.elements + od.cycles.elements[i], &todo);
 965         }
 966       for (i = od.cycles.count - 4; i >= 0; i -= 4)
 967         {
 968           for (j = od.cycles.elements[i]; od.cyclesdata.elements[j]; j++)
 969             incycle[od.cyclesdata.elements[j]] = 1;
 970         }
 971       POOL_DEBUG(SOLV_DEBUG_STATS, "cycle edge creation took %d ms\n", solv_timems(now));
 972     }
 973
 974 #if 0
 975   dump_tes(&od);
 976 #endif
 977   /* all edges are finally set up and there are no cycles, now the easy part.
 978    * Create an ordered transaction */
 979   now = solv_timems(0);
 980   /* first invert all edges */
 981   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 982     te->mark = 1;       /* term 0 */
 983   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 984     {
 985       for (j = te->edges; od.edgedata[j]; j += 2)
 986         {
 987           if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 988             continue;
 989           od.tes[od.edgedata[j]].mark++;
 990         }
 991     }
 992   j = 1;
 993   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 994     {
 995       te->mark += j;
 996       j = te->mark;
 997     }
 998   POOL_DEBUG(SOLV_DEBUG_STATS, "invedge space: %d\n", j + 1);
 999   od.invedgedata = solv_calloc(j + 1, sizeof(Id));
1000   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1001     {
1002       for (j = te->edges; od.edgedata[j]; j += 2)
1003         {
1004           if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
1005             continue;
1006           od.invedgedata[--od.tes[od.edgedata[j]].mark] = i;
1007         }
1008     }
1009   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1010     te->edges = te->mark;       /* edges now points into invedgedata */
1011   od.edgedata = solv_free(od.edgedata);
1012   od.nedgedata = j + 1;
1013
1014   /* now the final ordering */
1015   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1016     te->mark = 0;
1017   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1018     for (j = te->edges; od.invedgedata[j]; j++)
1019       od.tes[od.invedgedata[j]].mark++;
1020
1021   queue_init(&samerepoq);
1022   queue_init(&uninstq);
1023   queue_empty(&todo);
1024   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1025     if (te->mark == 0)
1026       {
1027         if (installed && pool->solvables[te->p].repo == installed)
1028           queue_push(&uninstq, i);
1029         else
1030           queue_push(&todo, i);
1031       }
1032   assert(todo.count > 0 || uninstq.count > 0);
1033   oldcount = tr->count;
1034   queue_empty(tr);
1035
1036   queue_init(&obsq);
1037
1038   lastrepo = 0;
1039   lastmedia = 0;
1040   lastte = 0;
1041   temedianr = solv_calloc(numte, sizeof(Id));
1042   for (i = 1; i < numte; i++)
1043     {
1044       Solvable *s = pool->solvables + od.tes[i].p;
1045       if (installed && s->repo == installed)
1046         j = 1;
1047       else
1048         j = solvable_lookup_num(s, SOLVABLE_MEDIANR, 1);
1049       temedianr[i] = j;
1050     }
1051   for (;;)
1052     {
1053       /* select an TE i */
1054       if (uninstq.count)
1055         i = queue_shift(&uninstq);
1056       else if (samerepoq.count)
1057         {
1058           if (lastte && incycle && incycle[lastte])
1059             {
1060               /* last installed package was in a cycle, prefer packages from the same cycle */
1061               for (j = 0; j < samerepoq.count; j++)
1062                 if (incycle[samerepoq.elements[j]] && share_cycle(&od, lastte, samerepoq.elements[j]))
1063                   {
1064                     /* yes, bring to front! */
1065                     i = samerepoq.elements[j];
1066                     queue_delete(&samerepoq, j);
1067                     queue_unshift(&samerepoq, i);
1068                     break;
1069                   }
1070             }
1071           i = queue_shift(&samerepoq);
1072         }
1073       else if (todo.count)
1074         {
1075           /* find next repo/media */
1076           for (j = 0; j < todo.count; j++)
1077             {
1078               if (!j || temedianr[todo.elements[j]] < lastmedia)
1079                 {
1080                   i = j;
1081                   lastmedia = temedianr[todo.elements[j]];
1082                 }
1083             }
1084           lastrepo = pool->solvables[od.tes[todo.elements[i]].p].repo;
1085
1086           /* move all matching TEs to samerepoq */
1087           for (i = j = 0; j < todo.count; j++)
1088             {
1089               int k = todo.elements[j];
1090               if (temedianr[k] == lastmedia && pool->solvables[od.tes[k].p].repo == lastrepo)
1091                 queue_push(&samerepoq, k);
1092               else
1093                 todo.elements[i++] = k;
1094             }
1095           todo.count = i;
1096
1097           assert(samerepoq.count);
1098           i = queue_shift(&samerepoq);
1099         }
1100       else
1101         break;
1102
1103       te = od.tes + i;
1104       queue_push(tr, te->p);
1105       if (pool->solvables[te->p].repo != installed)
1106         lastte = i;
1107
1108 #if 0
1109 printf("do %s [%d]\n", pool_solvid2str(pool, te->p), temedianr[i]);
1110 #endif
1111       for (j = te->edges; od.invedgedata[j]; j++)
1112         {
1113           struct s_TransactionElement *te2 = od.tes + od.invedgedata[j];
1114           assert(te2->mark > 0);
1115           if (--te2->mark == 0)
1116             {
1117               Solvable *s = pool->solvables + te2->p;
1118 #if 0
1119 printf("free %s [%d]\n", pool_solvid2str(pool, te2->p), temedianr[od.invedgedata[j]]);
1120 #endif
1121               if (installed && s->repo == installed)
1122                 queue_push(&uninstq, od.invedgedata[j]);
1123               else if (s->repo == lastrepo && temedianr[od.invedgedata[j]] == lastmedia)
1124                 queue_push(&samerepoq, od.invedgedata[j]);
1125               else
1126                 queue_push(&todo, od.invedgedata[j]);
1127             }
1128         }
1129     }
1130   solv_free(temedianr);
1131   solv_free(incycle);
1132   queue_free(&todo);
1133   queue_free(&samerepoq);
1134   queue_free(&uninstq);
1135   queue_free(&obsq);
1136   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1137     assert(te->mark == 0);
1138
1139   /* add back obsoleted packages */
1140   transaction_add_obsoleted(trans);
1141   assert(tr->count == oldcount);
1142
1143   POOL_DEBUG(SOLV_DEBUG_STATS, "creating new transaction took %d ms\n", solv_timems(now));
1144   POOL_DEBUG(SOLV_DEBUG_STATS, "transaction ordering took %d ms\n", solv_timems(start));
1145
1146   if ((flags & (SOLVER_TRANSACTION_KEEP_ORDERDATA | SOLVER_TRANSACTION_KEEP_ORDERCYCLES)) != 0)
1147     {
1148       struct s_TransactionOrderdata *tod;
1149       trans->orderdata = tod = solv_calloc(1, sizeof(*trans->orderdata));
1150       if ((flags & SOLVER_TRANSACTION_KEEP_ORDERCYCLES) != 0)
1151         {
1152           Queue *cycles = tod->cycles = solv_calloc(1, sizeof(Queue));
1153           queue_init_clone(cycles, &od.cyclesdata);
1154           /* map from tes to packages */
1155           for (i = 0; i < cycles->count; i++)
1156             if (cycles->elements[i])
1157               cycles->elements[i] = od.tes[cycles->elements[i]].p;
1158           queue_insertn(cycles, cycles->count, od.cycles.count, od.cycles.elements);
1159           queue_push(cycles, od.cycles.count / 4);
1160         }
1161       if ((flags & SOLVER_TRANSACTION_KEEP_ORDERDATA) != 0)
1162         {
1163           tod->tes = od.tes;
1164           tod->ntes = numte;
1165           tod->invedgedata = od.invedgedata;
1166           tod->ninvedgedata = od.nedgedata;
1167           od.tes = 0;
1168           od.invedgedata = 0;
1169         }
1170     }
1171   solv_free(od.tes);
1172   solv_free(od.invedgedata);
1173   queue_free(&od.cycles);
1174   queue_free(&od.cyclesdata);
1175 }
1176
1177
1178 int
1179 transaction_order_add_choices(Transaction *trans, Id chosen, Queue *choices)
1180 {
1181   int i, j;
1182   struct s_TransactionOrderdata *od = trans->orderdata;
1183   struct s_TransactionElement *te;
1184
1185   if (!od)
1186      return choices->count;
1187   if (!chosen)
1188     {
1189       /* initialization step */
1190       for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
1191         te->mark = 0;
1192       for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
1193         {
1194           for (j = te->edges; od->invedgedata[j]; j++)
1195             od->tes[od->invedgedata[j]].mark++;
1196         }
1197       for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
1198         if (!te->mark)
1199           queue_push(choices, te->p);
1200       return choices->count;
1201     }
1202   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
1203     if (te->p == chosen)
1204       break;
1205   if (i == od->ntes)
1206     return choices->count;
1207   if (te->mark > 0)
1208     {
1209       /* hey! out-of-order installation! */
1210       te->mark = -1;
1211     }
1212   for (j = te->edges; od->invedgedata[j]; j++)
1213     {
1214       te = od->tes + od->invedgedata[j];
1215       assert(te->mark > 0 || te->mark == -1);
1216       if (te->mark > 0 && --te->mark == 0)
1217         queue_push(choices, te->p);
1218     }
1219   return choices->count;
1220 }
1221
1222 void
1223 transaction_add_obsoleted(Transaction *trans)
1224 {
1225   Pool *pool = trans->pool;
1226   Repo *installed = pool->installed;
1227   Id p;
1228   Solvable *s;
1229   int i, j, k, max;
1230   Map done;
1231   Queue obsq, *steps;
1232
1233   if (!installed || !trans->steps.count)
1234     return;
1235   /* calculate upper bound */
1236   max = 0;
1237   FOR_REPO_SOLVABLES(installed, p, s)
1238     if (MAPTST(&trans->transactsmap, p))
1239       max++;
1240   if (!max)
1241     return;
1242   /* make room */
1243   steps = &trans->steps;
1244   queue_insertn(steps, 0, max, 0);
1245
1246   /* now add em */
1247   map_init(&done, installed->end - installed->start);
1248   queue_init(&obsq);
1249   for (j = 0, i = max; i < steps->count; i++)
1250     {
1251       p = trans->steps.elements[i];
1252       if (pool->solvables[p].repo == installed)
1253         {
1254           if (!trans->transaction_installed[p - pool->installed->start])
1255             trans->steps.elements[j++] = p;
1256           continue;
1257         }
1258       trans->steps.elements[j++] = p;
1259       queue_empty(&obsq);
1260       transaction_all_obs_pkgs(trans, p, &obsq);
1261       for (k = 0; k < obsq.count; k++)
1262         {
1263           p = obsq.elements[k];
1264           assert(p >= installed->start && p < installed->end);
1265           if (!MAPTST(&trans->transactsmap, p)) /* just in case */
1266             continue;
1267           if (MAPTST(&done, p - installed->start))
1268             continue;
1269           MAPSET(&done, p - installed->start);
1270           trans->steps.elements[j++] = p;
1271         }
1272     }
1273
1274   /* free unneeded space */
1275   queue_truncate(steps, j);
1276   map_free(&done);
1277   queue_free(&obsq);
1278 }
1279
1280 static void
1281 transaction_check_pkg(Transaction *trans, Id tepkg, Id pkg, Map *ins, Map *seen, int onlyprereq, Id noconfpkg, int depth)
1282 {
1283   Pool *pool = trans->pool;
1284   Id p, pp;
1285   Solvable *s;
1286   int good;
1287
1288   if (MAPTST(seen, pkg))
1289     return;
1290   MAPSET(seen, pkg);
1291   s = pool->solvables + pkg;
1292 #if 0
1293   printf("- %*s%c%s\n", depth * 2, "", s->repo == pool->installed ? '-' : '+', pool_solvable2str(pool, s));
1294 #endif
1295   if (s->requires)
1296     {
1297       Id req, *reqp;
1298       int inpre = 0;
1299       reqp = s->repo->idarraydata + s->requires;
1300       while ((req = *reqp++) != 0)
1301         {
1302           if (req == SOLVABLE_PREREQMARKER)
1303             {
1304               inpre = 1;
1305               continue;
1306             }
1307           if (onlyprereq && !inpre)
1308             continue;
1309           if (!strncmp(pool_id2str(pool, req), "rpmlib(", 7))
1310             continue;
1311           good = 0;
1312           /* first check kept packages, then freshly installed, then not yet uninstalled */
1313           FOR_PROVIDES(p, pp, req)
1314             {
1315               if (!MAPTST(ins, p))
1316                 continue;
1317               if (MAPTST(&trans->transactsmap, p))
1318                 continue;
1319               good++;
1320               transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
1321             }
1322           if (!good)
1323             {
1324               FOR_PROVIDES(p, pp, req)
1325                 {
1326                   if (!MAPTST(ins, p))
1327                     continue;
1328                   if (pool->solvables[p].repo == pool->installed)
1329                     continue;
1330                   good++;
1331                   transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
1332                 }
1333             }
1334           if (!good)
1335             {
1336               FOR_PROVIDES(p, pp, req)
1337                 {
1338                   if (!MAPTST(ins, p))
1339                     continue;
1340                   good++;
1341                   transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
1342                 }
1343             }
1344           if (!good)
1345             {
1346               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));
1347             }
1348         }
1349     }
1350 }
1351
1352 void
1353 transaction_check_order(Transaction *trans)
1354 {
1355   Pool *pool = trans->pool;
1356   Solvable *s;
1357   Id p, lastins;
1358   Map ins, seen;
1359   int i;
1360
1361   POOL_DEBUG(SOLV_DEBUG_RESULT, "\nchecking transaction order...\n");
1362   map_init(&ins, pool->nsolvables);
1363   map_init(&seen, pool->nsolvables);
1364   if (pool->installed)
1365     {
1366       FOR_REPO_SOLVABLES(pool->installed, p, s)
1367         MAPSET(&ins, p);
1368     }
1369   lastins = 0;
1370   for (i = 0; i < trans->steps.count; i++)
1371     {
1372       p = trans->steps.elements[i];
1373       s = pool->solvables + p;
1374       if (s->repo != pool->installed)
1375         lastins = p;
1376       if (s->repo != pool->installed)
1377         MAPSET(&ins, p);
1378       if (havescripts(pool, p))
1379         {
1380           MAPZERO(&seen);
1381           transaction_check_pkg(trans, p, p, &ins, &seen, 1, lastins, 0);
1382         }
1383       if (s->repo == pool->installed)
1384         MAPCLR(&ins, p);
1385     }
1386   map_free(&seen);
1387   map_free(&ins);
1388   POOL_DEBUG(SOLV_DEBUG_RESULT, "transaction order check done.\n");
1389 }
1390
1391 void
1392 transaction_order_get_cycleids(Transaction *trans, Queue *q, int minseverity)
1393 {
1394   struct s_TransactionOrderdata *od = trans->orderdata;
1395   Queue *cq;
1396   int i, cid, ncycles;
1397
1398   queue_empty(q);
1399   if (!od || !od->cycles || !od->cycles->count)
1400     return;
1401   cq = od->cycles;
1402   ncycles = cq->elements[cq->count - 1];
1403   i = cq->count - 1 - ncycles * 4;
1404   for (cid = 1; cid <= ncycles; cid++, i += 4)
1405     {
1406       if (minseverity)
1407         {
1408           int cmin = cq->elements[i + 3] & 0xffff;
1409           int cmax = (cq->elements[i + 3] >> 16) & 0xffff;
1410           if (minseverity >= SOLVER_ORDERCYCLE_NORMAL && cmin < TYPE_REQ)
1411             continue;
1412           if (minseverity >= SOLVER_ORDERCYCLE_CRITICAL && (cmax & TYPE_PREREQ) == 0)
1413             continue;
1414         }
1415       queue_push(q, cid);
1416     }
1417 }
1418
1419 int
1420 transaction_order_get_cycle(Transaction *trans, Id cid, Queue *q)
1421 {
1422   struct s_TransactionOrderdata *od = trans->orderdata;
1423   Queue *cq;
1424   int cmin, cmax, severity;
1425   int ncycles;
1426
1427   queue_empty(q);
1428   if (!od || !od->cycles || !od->cycles->count)
1429     return SOLVER_ORDERCYCLE_HARMLESS;
1430   cq = od->cycles;
1431   ncycles = cq->elements[cq->count - 1];
1432   if (cid < 1 || cid > ncycles)
1433     return SOLVER_ORDERCYCLE_HARMLESS;
1434   cid =  cq->count - 1 - 4 * (ncycles - cid + 1);
1435   cmin = cq->elements[cid + 3] & 0xffff;
1436   cmax = (cq->elements[cid + 3] >> 16) & 0xffff;
1437   if (cmin < TYPE_REQ)
1438     severity = SOLVER_ORDERCYCLE_HARMLESS;
1439   else if ((cmax & TYPE_PREREQ) == 0)
1440     severity = SOLVER_ORDERCYCLE_NORMAL;
1441   else
1442     severity = SOLVER_ORDERCYCLE_CRITICAL;
1443   if (q)
1444     queue_insertn(q, 0, cq->elements[cid + 1], cq->elements + cq->elements[cid]);
1445   return severity;
1446 }
1447