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 }
 328
 329 void
 330 transaction_calculate(Transaction *trans, Queue *decisionq, Map *noobsmap)
 331 {
 332   Pool *pool = trans->pool;
 333   Repo *installed = pool->installed;
 334   int i, r, noobs;
 335   Id p, p2;
 336   Solvable *s, *s2;
 337
 338   if (noobsmap && !noobsmap->size)
 339     noobsmap = 0;       /* ignore empty map */
 340   queue_empty(&trans->steps);
 341   map_init(&trans->transactsmap, pool->nsolvables);
 342   for (i = 0; i < decisionq->count; i++)
 343     {
 344       p = decisionq->elements[i];
 345       s = pool->solvables + (p > 0 ? p : -p);
 346       if (!s->repo)
 347         continue;
 348       if (installed && s->repo == installed && p < 0)
 349         MAPSET(&trans->transactsmap, -p);
 350       if ((!installed || s->repo != installed) && p > 0)
 351         MAPSET(&trans->transactsmap, p);
 352     }
 353   create_transaction_info(trans, decisionq, noobsmap);
 354
 355   if (installed)
 356     {
 357       FOR_REPO_SOLVABLES(installed, p, s)
 358         {
 359           if (!MAPTST(&trans->transactsmap, p))
 360             continue;
 361           p2 = solver_transaction_pkg(trans, p);
 362           if (!p2)
 363             queue_push(&trans->steps, SOLVER_TRANSACTION_ERASE);
 364           else
 365             {
 366               s2 = pool->solvables + p2;
 367               if (s->name == s2->name)
 368                 {
 369                   if (s->evr == s2->evr && solvable_identical(s, s2))
 370                     queue_push(&trans->steps, SOLVER_TRANSACTION_REINSTALLED);
 371                   else
 372                     {
 373                       r = evrcmp(pool, s->evr, s2->evr, EVRCMP_COMPARE);
 374                       if (r < 0)
 375                         queue_push(&trans->steps, SOLVER_TRANSACTION_UPGRADED);
 376                       else if (r > 0)
 377                         queue_push(&trans->steps, SOLVER_TRANSACTION_DOWNGRADED);
 378                       else
 379                         queue_push(&trans->steps, SOLVER_TRANSACTION_CHANGED);
 380                     }
 381                 }
 382               else
 383                 queue_push(&trans->steps, SOLVER_TRANSACTION_REPLACED);
 384             }
 385           queue_push(&trans->steps, p);
 386         }
 387     }
 388   for (i = 0; i < decisionq->count; i++)
 389     {
 390       p = decisionq->elements[i];
 391       if (p < 0 || p == SYSTEMSOLVABLE)
 392         continue;
 393       s = pool->solvables + p;
 394       if (installed && s->repo == installed)
 395         continue;
 396       noobs = noobsmap && MAPTST(noobsmap, p);
 397       p2 = solver_transaction_pkg(trans, p);
 398       if (noobs)
 399         queue_push(&trans->steps, p2 ? SOLVER_TRANSACTION_MULTIREINSTALL : SOLVER_TRANSACTION_MULTIINSTALL);
 400       else if (!p2)
 401         queue_push(&trans->steps, SOLVER_TRANSACTION_INSTALL);
 402       else
 403         {
 404           s2 = pool->solvables + p2;
 405           if (s->name == s2->name)
 406             {
 407               if (s->evr == s2->evr && solvable_identical(s, s2))
 408                 queue_push(&trans->steps, SOLVER_TRANSACTION_REINSTALL);
 409               else
 410                 {
 411                   r = evrcmp(pool, s->evr, s2->evr, EVRCMP_COMPARE);
 412                   if (r > 0)
 413                     queue_push(&trans->steps, SOLVER_TRANSACTION_UPGRADE);
 414                   else if (r < 0)
 415                     queue_push(&trans->steps, SOLVER_TRANSACTION_DOWNGRADE);
 416                   else
 417                     queue_push(&trans->steps, SOLVER_TRANSACTION_CHANGE);
 418                 }
 419             }
 420           else
 421             queue_push(&trans->steps, SOLVER_TRANSACTION_REPLACE);
 422         }
 423       queue_push(&trans->steps, p);
 424     }
 425 }
 426
 427 #define TYPE_BROKEN     (1<<0)
 428 #define TYPE_CON        (1<<1)
 429
 430 #define TYPE_REQ_P      (1<<2)
 431 #define TYPE_PREREQ_P   (1<<3)
 432
 433 #define TYPE_REQ        (1<<4)
 434 #define TYPE_PREREQ     (1<<5)
 435
 436 #define EDGEDATA_BLOCK  127
 437
 438 struct transel {
 439   Id p;
 440   Id type;
 441   Id edges;
 442   Id invedges;
 443   Id mark;
 444   Id medianr;
 445   Id ddeg;      /* unused */
 446 };
 447
 448 struct orderdata {
 449   Transaction *trans;
 450   struct transel *tes;
 451   int ntes;
 452   Id *edgedata;
 453   int nedgedata;
 454   Id *invedgedata;
 455   Map cycletes;
 456 };
 457
 458 static int
 459 addedge(struct orderdata *od, Id from, Id to, int type)
 460 {
 461   Transaction *trans = od->trans;
 462   Pool *pool = trans->pool;
 463   Solvable *s;
 464   struct transel *te;
 465   int i;
 466
 467   // printf("addedge %d %d type %d\n", from, to, type);
 468   s = pool->solvables + from;
 469   if (s->repo == pool->installed && trans->transaction_installed[from - pool->installed->start])
 470     {
 471       /* passive, map to active */
 472       if (trans->transaction_installed[from - pool->installed->start] > 0)
 473         from = trans->transaction_installed[from - pool->installed->start];
 474       else
 475         {
 476           int ret = 0;
 477           Queue ti;
 478           Id tibuf[5];
 479
 480           queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
 481           solver_transaction_all_pkgs(trans, from, &ti);
 482           for (i = 0; i < ti.count; i++)
 483             ret |= addedge(od, ti.elements[i], to, type);
 484           queue_free(&ti);
 485           return ret;
 486         }
 487     }
 488   s = pool->solvables + to;
 489   if (s->repo == pool->installed && trans->transaction_installed[to - pool->installed->start])
 490     {
 491       /* passive, map to active */
 492       if (trans->transaction_installed[to - pool->installed->start] > 0)
 493         to = trans->transaction_installed[to - pool->installed->start];
 494       else
 495         {
 496           int ret = 0;
 497           Queue ti;
 498           Id tibuf[5];
 499
 500           queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
 501           solver_transaction_all_pkgs(trans, to, &ti);
 502           for (i = 0; i < ti.count; i++)
 503             ret |= addedge(od, from, ti.elements[i], type);
 504           queue_free(&ti);
 505           return ret;
 506         }
 507     }
 508
 509   /* map target to te num */
 510   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
 511     if (te->p == to)
 512       break;
 513   if (i == od->ntes)
 514     return 0;
 515   to = i;
 516
 517   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
 518     if (te->p == from)
 519       break;
 520   if (i == od->ntes)
 521     return 0;
 522
 523   if (i == to)
 524     return 0;   /* no edges to ourselfes */
 525
 526   /* printf("edge %d(%s) -> %d(%s) type %x\n", i, solvid2str(pool, od->tes[i].p), to, solvid2str(pool, od->tes[to].p), type); */
 527
 528   for (i = te->edges; od->edgedata[i]; i += 2)
 529     if (od->edgedata[i] == to)
 530       break;
 531   /* test of brokenness */
 532   if (type == TYPE_BROKEN)
 533     return od->edgedata[i] && (od->edgedata[i + 1] & TYPE_BROKEN) != 0 ? 1 : 0;
 534   if (od->edgedata[i])
 535     {
 536       od->edgedata[i + 1] |= type;
 537       return 0;
 538     }
 539   if (i + 1 == od->nedgedata)
 540     {
 541       /* printf("tail add %d\n", i - te->edges); */
 542       if (!i)
 543         te->edges = ++i;
 544       od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3, sizeof(Id), EDGEDATA_BLOCK);
 545     }
 546   else
 547     {
 548       /* printf("extend %d\n", i - te->edges); */
 549       od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3 + (i - te->edges), sizeof(Id), EDGEDATA_BLOCK);
 550       if (i > te->edges)
 551         memcpy(od->edgedata + od->nedgedata, od->edgedata + te->edges, sizeof(Id) * (i - te->edges));
 552       i = od->nedgedata + (i - te->edges);
 553       te->edges = od->nedgedata;
 554     }
 555   od->edgedata[i] = to;
 556   od->edgedata[i + 1] = type;
 557   od->edgedata[i + 2] = 0;
 558   od->nedgedata = i + 3;
 559   te->ddeg++;
 560   od->tes[to].ddeg--;
 561   return 0;
 562 }
 563
 564 static int
 565 havechoice(struct orderdata *od, Id p, Id q1, Id q2)
 566 {
 567   Transaction *trans = od->trans;
 568   Pool *pool = trans->pool;
 569   Id ti1buf[5], ti2buf[5];
 570   Queue ti1, ti2;
 571   int i, j;
 572
 573   /* both q1 and q2 are uninstalls. check if their TEs intersect */
 574   /* common case: just one TE for both packages */
 575   printf("havechoice %d %d %d\n", p, q1, q2);
 576   if (trans->transaction_installed[q1 - pool->installed->start] == 0)
 577     return 1;
 578   if (trans->transaction_installed[q2 - pool->installed->start] == 0)
 579     return 1;
 580   if (trans->transaction_installed[q1 - pool->installed->start] == trans->transaction_installed[q2 - pool->installed->start])
 581     return 0;
 582   if (trans->transaction_installed[q1 - pool->installed->start] > 0 && trans->transaction_installed[q2 - pool->installed->start] > 0)
 583     return 1;
 584   queue_init_buffer(&ti1, ti1buf, sizeof(ti1buf)/sizeof(*ti1buf));
 585   solver_transaction_all_pkgs(trans, q1, &ti1);
 586   queue_init_buffer(&ti2, ti2buf, sizeof(ti2buf)/sizeof(*ti2buf));
 587   solver_transaction_all_pkgs(trans, q2, &ti2);
 588   for (i = 0; i < ti1.count; i++)
 589     for (j = 0; j < ti2.count; j++)
 590       if (ti1.elements[i] == ti2.elements[j])
 591         {
 592           /* found a common edge */
 593           queue_free(&ti1);
 594           queue_free(&ti2);
 595           return 0;
 596         }
 597   queue_free(&ti1);
 598   queue_free(&ti2);
 599   return 1;
 600 }
 601
 602 static void
 603 addsolvableedges(struct orderdata *od, Solvable *s)
 604 {
 605   Transaction *trans = od->trans;
 606   Pool *pool = trans->pool;
 607   Id req, *reqp, con, *conp;
 608   Id p, p2, pp2;
 609   int i, j, pre, numins;
 610   Repo *installed = pool->installed;
 611   Solvable *s2;
 612   Queue reqq;
 613
 614   p = s - pool->solvables;
 615   queue_init(&reqq);
 616   if (s->requires)
 617     {
 618       reqp = s->repo->idarraydata + s->requires;
 619       pre = TYPE_REQ;
 620       while ((req = *reqp++) != 0)
 621         {
 622           if (req == SOLVABLE_PREREQMARKER)
 623             {
 624               pre = TYPE_PREREQ;
 625               continue;
 626             }
 627           queue_empty(&reqq);
 628           numins = 0;   /* number of packages to be installed providing it */
 629           FOR_PROVIDES(p2, pp2, req)
 630             {
 631               s2 = pool->solvables + p2;
 632               if (p2 == p)
 633                 {
 634                   reqq.count = 0;       /* self provides */
 635                   break;
 636                 }
 637               if (s2->repo == installed && !MAPTST(&trans->transactsmap, p2))
 638                 {
 639                   reqq.count = 0;       /* provided by package that stays installed */
 640                   break;
 641                 }
 642               if (s2->repo != installed && !MAPTST(&trans->transactsmap, p2))
 643                 continue;               /* package stays uninstalled */
 644
 645               if (s->repo == installed)
 646                 {
 647                   /* s gets uninstalled */
 648                   queue_pushunique(&reqq, p2);
 649                   if (s2->repo != installed)
 650                     numins++;
 651                 }
 652               else
 653                 {
 654                   if (s2->repo == installed)
 655                     continue;   /* s2 gets uninstalled */
 656                   queue_pushunique(&reqq, p2);
 657                   /* EDGE s(A) -> s2(A) */
 658                 }
 659             }
 660           if (numins && reqq.count)
 661             {
 662               /* no mixed types, remove all deps on uninstalls */
 663               for (i = j = 0; i < reqq.count; i++)
 664                 if (pool->solvables[reqq.elements[i]].repo != installed)
 665                   reqq.elements[j++] = reqq.elements[i];
 666               reqq.count = j;
 667             }
 668           if (!reqq.count)
 669             continue;
 670           for (i = 0; i < reqq.count; i++)
 671             {
 672               int choice = 0;
 673               p2 = reqq.elements[i];
 674               if (pool->solvables[p2].repo != installed)
 675                 {
 676                   /* all elements of reqq are installs, thus have different TEs */
 677                   choice = reqq.count - 1;
 678                   if (pool->solvables[p].repo != installed)
 679                     {
 680 #if 0
 681                       printf("add inst edge choice %d (%s -> %s -> %s)\n", choice, solvid2str(pool, p), dep2str(pool, req), solvid2str(pool, p2));
 682 #endif
 683                       addedge(od, p, p2, pre);
 684                     }
 685                   else
 686                     {
 687 #if 0
 688                       printf("add uninst->inst edge choice %d (%s -> %s -> %s)\n", choice, solvid2str(pool, p), dep2str(pool, req), solvid2str(pool, p2));
 689 #endif
 690                       addedge(od, p, p2, pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
 691                     }
 692                 }
 693               else
 694                 {
 695 #if 1
 696                   choice = 0;
 697                   for (j = 0; j < reqq.count; j++)
 698                     {
 699                       if (i == j)
 700                         continue;
 701                       if (havechoice(od, p, reqq.elements[i], reqq.elements[j]))
 702                         choice++;
 703                     }
 704 #endif
 705 #if 0
 706                   printf("add uninst->uninst edge choice %d (%s -> %s -> %s)\n", choice, solvid2str(pool, p), dep2str(pool, req), solvid2str(pool, p2));
 707 #endif
 708                   addedge(od, p2, p, pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
 709                 }
 710             }
 711         }
 712     }
 713   if (s->conflicts)
 714     {
 715       conp = s->repo->idarraydata + s->conflicts;
 716       while ((con = *conp++) != 0)
 717         {
 718           FOR_PROVIDES(p2, pp2, con)
 719             {
 720               if (p2 == p)
 721                 continue;
 722               s2 = pool->solvables + p2;
 723               if (!s2->repo)
 724                 continue;
 725               if (s->repo == installed)
 726                 {
 727                   if (s2->repo != installed && MAPTST(&trans->transactsmap, p2))
 728                     {
 729                       /* deinstall p before installing p2 */
 730                       addedge(od, p2, p, TYPE_CON);
 731                     }
 732                 }
 733               else
 734                 {
 735                   if (s2->repo == installed && MAPTST(&trans->transactsmap, p2))
 736                     {
 737                       /* deinstall p2 before installing p */
 738                       addedge(od, p, p2, TYPE_CON);
 739                     }
 740                 }
 741
 742             }
 743         }
 744     }
 745   queue_free(&reqq);
 746 }
 747
 748 static inline int
 749 haveprereq(Pool *pool, Id solvid)
 750 {
 751   Solvable *s = pool->solvables + solvid;
 752   if (s->requires)
 753     {
 754       Id req, *reqp;
 755       int inpre = 0;
 756       reqp = s->repo->idarraydata + s->requires;
 757       while ((req = *reqp++) != 0)
 758         {
 759           if (req == SOLVABLE_PREREQMARKER)
 760             {
 761               inpre = 1;
 762               continue;
 763             }
 764           if (inpre && strncmp(id2str(pool, req), "rpmlib(", 7) != 0)
 765             return 1;
 766         }
 767     }
 768   return 0;
 769 }
 770
 771 void
 772 breakcycle(struct orderdata *od, Id *cycle)
 773 {
 774   Pool *pool = od->trans->pool;
 775   Id ddegmin, ddegmax, ddeg;
 776   int k, l;
 777   struct transel *te;
 778
 779   l = 0;
 780   ddegmin = ddegmax = 0;
 781   for (k = 0; cycle[k + 1]; k += 2)
 782     {
 783       MAPSET(&od->cycletes, cycle[k]);  /* this te is involved in a cycle */
 784       ddeg = od->edgedata[cycle[k + 1] + 1];
 785       if (ddeg > ddegmax)
 786         ddegmax = ddeg;
 787       if (!k || ddeg < ddegmin)
 788         {
 789           l = k;
 790           ddegmin = ddeg;
 791           continue;
 792         }
 793       if (ddeg == ddegmin)
 794         {
 795           if (haveprereq(pool, od->tes[cycle[l]].p) && !haveprereq(pool, od->tes[cycle[k]].p))
 796             {
 797               /* prefer k, as l comes from a package with contains scriptlets */
 798               l = k;
 799               ddegmin = ddeg;
 800               continue;
 801             }
 802           /* same edge value, check for prereq */
 803         }
 804     }
 805
 806   od->edgedata[cycle[l + 1] + 1] |= TYPE_BROKEN;
 807
 808 #if 1
 809   if (ddegmin < TYPE_REQ)
 810     return;
 811 #endif
 812
 813
 814   /* cycle recorded, print it */
 815   if ((ddegmax & TYPE_PREREQ) != 0)
 816     printf("CRITICAL ");
 817   printf("cycle: --> ");
 818   for (k = 0; cycle[k + 1]; k += 2)
 819     {
 820       te = od->tes +  cycle[k];
 821       if ((od->edgedata[cycle[k + 1] + 1] & TYPE_BROKEN) != 0)
 822         printf("%s ##%x##> ", solvid2str(pool, te->p), od->edgedata[cycle[k + 1] + 1]);
 823       else
 824         printf("%s --%x--> ", solvid2str(pool, te->p), od->edgedata[cycle[k + 1] + 1]);
 825     }
 826   printf("\n");
 827 }
 828
 829 void
 830 transaction_order(Transaction *trans)
 831 {
 832   Pool *pool = trans->pool;
 833   Queue *tr = &trans->steps;
 834   Repo *installed = pool->installed;
 835   Id type, p;
 836   Solvable *s;
 837   int i, j, k, numte, numedge;
 838   struct orderdata od;
 839   struct transel *te;
 840   Queue todo, obsq;
 841   int cycstart, cycel, broken;
 842   Id *cycle, *obstypes;
 843   int oldcount;
 844   int now;
 845
 846   POOL_DEBUG(SAT_DEBUG_STATS, "ordering transaction\n");
 847   now = sat_timems(0);
 848   /* create a transaction element for every active component */
 849   numte = 0;
 850   for (i = 0; i < tr->count; i += 2)
 851     {
 852       p = tr->elements[i + 1];
 853       s = pool->solvables + p;
 854       if (installed && s->repo == installed && trans->transaction_installed[p - installed->start])
 855         continue;
 856       numte++;
 857     }
 858   if (!numte)
 859     return;     /* nothing to do... */
 860
 861   POOL_DEBUG(SAT_DEBUG_STATS, "transaction elements: %d\n", numte);
 862   numte++;      /* leave first one zero */
 863   memset(&od, 0, sizeof(od));
 864   od.trans = trans;
 865   od.ntes = numte;
 866   od.tes = sat_calloc(numte, sizeof(*od.tes));
 867   od.edgedata = sat_extend(0, 0, 1, sizeof(Id), EDGEDATA_BLOCK);
 868   od.edgedata[0] = 0;
 869   od.nedgedata = 1;
 870   map_init(&od.cycletes, numte);
 871
 872   for (i = 0, te = od.tes + 1; i < tr->count; i += 2)
 873     {
 874       p = tr->elements[i + 1];
 875       s = pool->solvables + p;
 876       if (installed && s->repo == installed && trans->transaction_installed[p - installed->start])
 877         continue;
 878       te->p = p;
 879       te->type = tr->elements[i];
 880       te->medianr = solvable_lookup_num(s, SOLVABLE_MEDIANR, 0);
 881       te++;
 882     }
 883
 884   /* create dependency graph */
 885   for (i = 0; i < tr->count; i += 2)
 886     {
 887       type = tr->elements[i];
 888       p = tr->elements[i + 1];
 889       addsolvableedges(&od, pool->solvables + p);
 890     }
 891
 892   /* count edges */
 893   numedge = 0;
 894   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 895     for (j = te->edges; od.edgedata[j]; j += 2)
 896       numedge++;
 897   POOL_DEBUG(SAT_DEBUG_STATS, "edges: %d, edge space: %d\n", numedge, od.nedgedata / 2);
 898   POOL_DEBUG(SAT_DEBUG_STATS, "edge creation took %d ms\n", sat_timems(now));
 899
 900   /* kill all cycles */
 901   broken = 0;
 902
 903   queue_init(&todo);
 904   for (i = numte - 1; i > 0; i--)
 905     queue_push(&todo, i);
 906
 907   while (todo.count)
 908     {
 909       i = queue_pop(&todo);
 910       /* printf("- look at TE %d\n", i); */
 911       if (i < 0)
 912         {
 913           i = -i;
 914           od.tes[i].mark = 2;   /* done with that one */
 915           continue;
 916         }
 917       te = od.tes + i;
 918       if (te->mark == 2)
 919         continue;               /* already finished before */
 920       if (te->mark == 0)
 921         {
 922           int edgestovisit = 0;
 923           /* new node, visit edges */
 924           for (j = te->edges; (k = od.edgedata[j]) != 0; j += 2)
 925             {
 926               if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 927                 continue;
 928               if (od.tes[k].mark == 2)
 929                 continue;       /* no need to visit again */
 930               if (!edgestovisit++)
 931                 queue_push(&todo, -i);  /* end of edges marker */
 932               queue_push(&todo, k);
 933             }
 934           if (!edgestovisit)
 935             te->mark = 2;       /* no edges, done with that one */
 936           else
 937             te->mark = 1;       /* under investigation */
 938           continue;
 939         }
 940       /* oh no, we found a cycle */
 941       /* find start of cycle node (<0) */
 942       for (j = todo.count - 1; j >= 0; j--)
 943         if (todo.elements[j] == -i)
 944           break;
 945       assert(j >= 0);
 946       cycstart = j;
 947       /* build te/edge chain */
 948       k = cycstart;
 949       for (j = k; j < todo.count; j++)
 950         if (todo.elements[j] < 0)
 951           todo.elements[k++] = -todo.elements[j];
 952       cycel = k - cycstart;
 953       assert(cycel > 1);
 954       /* make room for edges, two extra element for cycle loop + terminating 0 */
 955       while (todo.count < cycstart + 2 * cycel + 2)
 956         queue_push(&todo, 0);
 957       cycle = todo.elements + cycstart;
 958       cycle[cycel] = i;         /* close the loop */
 959       cycle[2 * cycel + 1] = 0; /* terminator */
 960       for (k = cycel; k > 0; k--)
 961         {
 962           cycle[k * 2] = cycle[k];
 963           te = od.tes + cycle[k - 1];
 964           if (te->mark == 1)
 965             te->mark = 0;       /* reset investigation marker */
 966           /* printf("searching for edge from %d to %d\n", cycle[k - 1], cycle[k]); */
 967           for (j = te->edges; od.edgedata[j]; j += 2)
 968             if (od.edgedata[j] == cycle[k])
 969               break;
 970           assert(od.edgedata[j]);
 971           cycle[k * 2 - 1] = j;
 972         }
 973       /* now cycle looks like this: */
 974       /* te1 edge te2 edge te3 ... teN edge te1 0 */
 975       breakcycle(&od, cycle);
 976       broken++;
 977       /* restart with start of cycle */
 978       todo.count = cycstart + 1;
 979     }
 980   POOL_DEBUG(SAT_DEBUG_STATS, "cycles broken: %d\n", broken);
 981
 982   /* invert all edges */
 983   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 984     {
 985       te->invedges = 1; /* term 0 */
 986       te->mark = 0;     /* backref count */
 987     }
 988
 989   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 990     {
 991       for (j = te->edges; od.edgedata[j]; j += 2)
 992         {
 993           if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 994             continue;
 995           struct transel *te2 = od.tes + od.edgedata[j];
 996           te2->invedges++;
 997         }
 998     }
 999   j = 1;
1000   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1001     {
1002       te->invedges += j;
1003       j = te->invedges;
1004     }
1005   POOL_DEBUG(SAT_DEBUG_STATS, "invedge space: %d\n", j + 1);
1006   od.invedgedata = sat_calloc(j + 1, sizeof(Id));
1007   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1008     {
1009       for (j = te->edges; od.edgedata[j]; j += 2)
1010         {
1011           if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
1012             continue;
1013           struct transel *te2 = od.tes + od.edgedata[j];
1014           od.invedgedata[--te2->invedges] = i;
1015           te->mark++;
1016         }
1017     }
1018   /* now the final ordering */
1019   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1020     if (te->mark == 0)
1021       queue_push(&todo, i);
1022   assert(todo.count > 0);
1023   if (installed)
1024     {
1025       obstypes = sat_calloc(installed->end - installed->start, sizeof(Id));
1026       for (i = 0; i < tr->count; i += 2)
1027         {
1028           p = tr->elements[i + 1];
1029           s = pool->solvables + p;
1030           if (s->repo == installed && trans->transaction_installed[p - installed->start])
1031             obstypes[p - installed->start] = tr->elements[i];
1032         }
1033     }
1034   else
1035     obstypes = 0;
1036   oldcount = tr->count;
1037   queue_empty(tr);
1038   queue_init(&obsq);
1039
1040   while (todo.count)
1041     {
1042       /* select an i */
1043       i = todo.count;
1044       if (installed)
1045         {
1046           for (i = 0; i < todo.count; i++)
1047             {
1048               j = todo.elements[i];
1049               if (pool->solvables[od.tes[j].p].repo == installed)
1050                 break;
1051             }
1052         }
1053       if (i == todo.count)
1054         {
1055           for (i = 0; i < todo.count; i++)
1056             {
1057               j = todo.elements[i];
1058               if (MAPTST(&od.cycletes, j))
1059                 break;
1060             }
1061         }
1062       if (i == todo.count)
1063         i = 0;
1064       te = od.tes + todo.elements[i];
1065       queue_push(tr, te->type);
1066       queue_push(tr, te->p);
1067       s = pool->solvables + te->p;
1068       if (installed && s->repo != installed)
1069         {
1070           queue_empty(&obsq);
1071           solver_transaction_all_pkgs(trans, te->p, &obsq);
1072           for (j = 0; j < obsq.count; j++)
1073             {
1074               p = obsq.elements[j];
1075               assert(p >= installed->start && p < installed->end);
1076               if (obstypes[p - installed->start])
1077                 {
1078                   queue_push(tr, obstypes[p - installed->start]);
1079                   queue_push(tr, p);
1080                   obstypes[p - installed->start] = 0;
1081                 }
1082             }
1083         }
1084       if (i < todo.count - 1)
1085         memmove(todo.elements + i, todo.elements + i + 1, (todo.count - 1 - i) * sizeof(Id));
1086       queue_pop(&todo);
1087       for (j = te->invedges; od.invedgedata[j]; j++)
1088         {
1089           struct transel *te2 = od.tes + od.invedgedata[j];
1090           assert(te2->mark > 0);
1091           if (--te2->mark == 0)
1092             {
1093               queue_push(&todo, od.invedgedata[j]);
1094             }
1095         }
1096     }
1097   queue_free(&todo);
1098   queue_free(&obsq);
1099   for (i = 1, te = od.tes + i; i < numte; i++, te++)
1100     assert(te->mark == 0);
1101   assert(tr->count == oldcount);
1102   POOL_DEBUG(SAT_DEBUG_STATS, "transaction ordering took %d ms\n", sat_timems(now));
1103 }
1104