src/transaction.c

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