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