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_REQ        (1<<1)
 400 #define TYPE_PREREQ     (1<<2)
 401 #define TYPE_CON        (1<<3)
 402 #define TYPE_ERASE      (1<<4)
 403
 404 #define EDGEDATA_BLOCK  127
 405
 406 struct transel {
 407   Id p;
 408   Id edges;
 409   Id mark;
 410   Id ddeg;
 411 };
 412
 413 struct orderdata {
 414   Solver *solv;
 415   struct transel *tes;
 416   int ntes;
 417   Id *edgedata;
 418   int nedgedata;
 419 };
 420
 421 static void
 422 addedge(struct orderdata *od, Id from, Id to, int type)
 423 {
 424   Solver *solv = od->solv;
 425   Pool *pool = solv->pool;
 426   Solvable *s;
 427   struct transel *te;
 428   int i;
 429
 430   // printf("addedge %d %d type %d\n", from, to, type);
 431   s = pool->solvables + from;
 432   if (s->repo == solv->installed && solv->transaction_installed[from - solv->installed->start])
 433     {
 434       /* passive, map to active */
 435       if (solv->transaction_installed[from - solv->installed->start] > 0)
 436         from = solv->transaction_installed[from - solv->installed->start];
 437       else
 438         {
 439           Queue ti;
 440           Id tibuf[5];
 441           queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
 442           solver_transaction_all_pkgs(solv, from, &ti);
 443           for (i = 0; i < ti.count; i++)
 444             addedge(od, ti.elements[i], to, type);
 445           queue_free(&ti);
 446         }
 447       return;
 448     }
 449   s = pool->solvables + to;
 450   if (s->repo == solv->installed && solv->transaction_installed[to - solv->installed->start])
 451     {
 452       /* passive, map to active */
 453       if (solv->transaction_installed[to - solv->installed->start] > 0)
 454         to = solv->transaction_installed[to - solv->installed->start];
 455       else
 456         {
 457           Queue ti;
 458           Id tibuf[5];
 459           queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
 460           solver_transaction_all_pkgs(solv, to, &ti);
 461           for (i = 0; i < ti.count; i++)
 462             addedge(od, from, ti.elements[i], type);
 463           queue_free(&ti);
 464           return;
 465         }
 466     }
 467
 468   /* map target to te num */
 469   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
 470     if (te->p == to)
 471       break;
 472   if (i == od->ntes)
 473     return;
 474   to = i;
 475
 476   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
 477     if (te->p == from)
 478       break;
 479   if (i == od->ntes)
 480     return;
 481
 482   if (i == to)
 483     return;     /* no edges to ourselfes */
 484
 485   // printf("edge %d -> %d type %x\n", i, to, type);
 486
 487   for (i = te->edges; od->edgedata[i]; i += 2)
 488     if (od->edgedata[i] == to)
 489       break;
 490   if (od->edgedata[i])
 491     {
 492       od->edgedata[i + 1] |= type;
 493       return;
 494     }
 495   if (i + 1 == od->nedgedata)
 496     {
 497       // printf("tail add %d\n", i - te->edges);
 498       if (!i)
 499         te->edges = ++i;
 500       od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3, sizeof(Id), EDGEDATA_BLOCK);
 501     }
 502   else
 503     {
 504       // printf("extend %d\n", i - te->edges);
 505       od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3 + (i - te->edges), sizeof(Id), EDGEDATA_BLOCK);
 506       if (i > te->edges)
 507         memcpy(od->edgedata + od->nedgedata, od->edgedata + te->edges, sizeof(Id) * (i - te->edges));
 508       i = od->nedgedata + (i - te->edges);
 509       te->edges = od->nedgedata;
 510     }
 511   od->edgedata[i] = to;
 512   od->edgedata[i + 1] = type;
 513   od->edgedata[i + 2] = 0;
 514   od->nedgedata = i + 3;
 515   te->ddeg++;
 516   od->tes[to].ddeg--;
 517 }
 518
 519 static void
 520 addsolvableedges(struct orderdata *od, Solvable *s)
 521 {
 522   Solver *solv = od->solv;
 523   Pool *pool = solv->pool;
 524   Id req, *reqp, con, *conp;
 525   Id p, p2, pp2;
 526   int pre;
 527   Repo *installed = solv->installed;
 528   Solvable *s2;
 529
 530   p = s - pool->solvables;
 531   if (s->requires)
 532     {
 533       reqp = s->repo->idarraydata + s->requires;
 534       pre = TYPE_REQ;
 535       while ((req = *reqp++) != 0)
 536         {
 537           int eraseonly = 0;
 538           if (req == SOLVABLE_PREREQMARKER)
 539             {
 540               pre = TYPE_PREREQ;
 541               continue;
 542             }
 543 #if 1
 544           if (s->repo == installed && pre != TYPE_PREREQ)
 545             continue;
 546 #endif
 547           FOR_PROVIDES(p2, pp2, req)
 548             {
 549               if (p2 == p)
 550                 continue;
 551               s2 = pool->solvables + p2;
 552               if (!s2->repo)
 553                 continue;
 554               if (s2->repo == installed && solv->decisionmap[p2] > 0)
 555                 continue;
 556               if (s2->repo != installed && solv->decisionmap[p2] < 0)
 557                 continue;       /* not interesting */
 558               if (s->repo == installed)
 559                 {
 560                   /* we're uninstalling s */
 561                   if (s2->repo == installed)
 562                     {
 563                       if (eraseonly == 0)
 564                         eraseonly = 1;
 565                     }
 566                   if (s2->repo != installed)
 567                     {
 568                       /* update p2 before erasing p */
 569 #if 1
 570                       addedge(od, p, p2, pre);
 571 #endif
 572                       eraseonly = -1;
 573                     }
 574                 }
 575               else
 576                 {
 577                   /* install p2 before installing p */
 578                   if (s2->repo != installed)
 579                     addedge(od, p, p2, pre);
 580                 }
 581             }
 582           if (eraseonly == 1)
 583             {
 584               printf("eraseonlyedge for %s req %s\n", solvable2str(pool, s), dep2str(pool, req));
 585               /* need edges to uninstalled pkgs */
 586 #if 1
 587               FOR_PROVIDES(p2, pp2, req)
 588                 {
 589                   if (p2 == p)
 590                     continue;
 591                   s2 = pool->solvables + p2;
 592                   if (!s2->repo || s2->repo != installed)
 593                     continue;
 594                   if (solv->decisionmap[p2] > 0)
 595                     continue;
 596 #if 0
 597                   addedge(od, p2, p, pre);
 598 #else
 599                   addedge(od, p2, p, TYPE_ERASE);
 600 #endif
 601                 }
 602 #endif
 603             }
 604         }
 605     }
 606   if (s->conflicts)
 607     {
 608       conp = s->repo->idarraydata + s->conflicts;
 609       while ((con = *conp++) != 0)
 610         {
 611 #if 1
 612           FOR_PROVIDES(p2, pp2, con)
 613             {
 614               if (p2 == p)
 615                 continue;
 616               s2 = pool->solvables + p2;
 617               if (!s2->repo)
 618                 continue;
 619               if (s->repo == installed)
 620                 {
 621                   if (s2->repo != installed && solv->decisionmap[p2] >= 0)
 622                     {
 623                       /* deinstall p before installing p2 */
 624                       addedge(od, p2, p, TYPE_CON);
 625                     }
 626                 }
 627               else
 628                 {
 629                   if (s2->repo == installed && solv->decisionmap[p2] < 0)
 630                     {
 631                       /* deinstall p2 before installing p */
 632 #if 1
 633                       addedge(od, p, p2, TYPE_CON);
 634 #endif
 635                     }
 636                 }
 637
 638             }
 639 #endif
 640         }
 641     }
 642 }
 643
 644 void
 645 breakcycle(struct orderdata *od, Id *cycle)
 646 {
 647   Pool *pool = od->solv->pool;
 648   Id ddeg, ddegm;
 649   int k, l;
 650   struct transel *te;
 651
 652   l = 0;
 653   ddegm = 0;
 654   for (k = 0; cycle[k + 1]; k += 2)
 655     {
 656       ddeg = od->tes[cycle[k]].ddeg - od->tes[cycle[k + 2]].ddeg;
 657       if (!k || ddeg < ddegm)
 658         {
 659           l = k;
 660           ddegm = ddeg;
 661         }
 662     }
 663 #if 0
 664   l = 0;
 665 #endif
 666
 667   od->edgedata[cycle[l + 1] + 1] |= TYPE_BROKEN;
 668
 669   /* cycle recorded, print it */
 670   printf("cycle: --> ");
 671   for (k = 0; cycle[k + 1]; k += 2)
 672     {
 673       te = od->tes +  cycle[k];
 674       if ((od->edgedata[cycle[k + 1] + 1] & TYPE_BROKEN) != 0)
 675         printf("%s ##%x##> ", solvid2str(pool, te->p), od->edgedata[cycle[k + 1] + 1]);
 676       else
 677         printf("%s --%x--> ", solvid2str(pool, te->p), od->edgedata[cycle[k + 1] + 1]);
 678     }
 679   printf("\n");
 680 }
 681
 682 void
 683 solver_order_transaction(Solver *solv)
 684 {
 685   Pool *pool = solv->pool;
 686   Queue *tr = &solv->transaction;
 687   Repo *installed = solv->installed;
 688   Id type, p;
 689   Solvable *s;
 690   int i, j, k, numte, numedge;
 691   struct orderdata od;
 692   struct transel *te;
 693   Queue todo;
 694   int cycstart, cycel, broken;
 695   Id *cycle;
 696
 697   /* create a transaction element for every active component */
 698   numte = 0;
 699   for (i = 0; i < tr->count; i += 2)
 700     {
 701       p = tr->elements[i + 1];
 702       s = pool->solvables + p;
 703       if (s->repo != installed || !solv->transaction_installed[p - solv->installed->start])
 704         numte++;
 705     }
 706   if (!numte)
 707     return;     /* nothing to do... */
 708
 709
 710   printf("numte = %d\n", numte);
 711   numte++;      /* leave first one zero */
 712   od.solv = solv;
 713   od.ntes = numte;
 714   od.tes = sat_calloc(numte, sizeof(*od.tes));
 715   od.edgedata = sat_extend(0, 0, 1, sizeof(Id), EDGEDATA_BLOCK);
 716   od.edgedata[0] = 0;
 717   od.nedgedata = 1;
 718
 719   for (i = 0, te = od.tes + 1; i < tr->count; i += 2)
 720     {
 721       p = tr->elements[i + 1];
 722       s = pool->solvables + p;
 723       if (s->repo == installed && solv->transaction_installed[p - solv->installed->start])
 724         continue;
 725       te->p = p;
 726       te++;
 727     }
 728
 729   /* create dependency graph */
 730   for (i = 0; i < tr->count; i += 2)
 731     {
 732       type = tr->elements[i];
 733       p = tr->elements[i + 1];
 734       addsolvableedges(&od, pool->solvables + p);
 735     }
 736
 737   /* kill all cycles */
 738   broken = 0;
 739
 740   queue_init(&todo);
 741   for (i = numte - 1; i > 0; i--)
 742     queue_push(&todo, i);
 743
 744   while (todo.count)
 745     {
 746       i = queue_pop(&todo);
 747       /* printf("- look at TE %d\n", i); */
 748       if (i < 0)
 749         {
 750           i = -i;
 751           od.tes[i].mark = 2;   /* done with that one */
 752           continue;
 753         }
 754       te = od.tes + i;
 755       if (te->mark == 2)
 756         continue;               /* already finished before */
 757       if (te->mark == 0)
 758         {
 759           int edgestovisit = 0;
 760           /* new node, visit edges */
 761           for (j = te->edges; (k = od.edgedata[j]) != 0; j += 2)
 762             {
 763               if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 764                 continue;
 765               if (od.tes[k].mark == 2)
 766                 continue;       /* no need to visit again */
 767               if (!edgestovisit++)
 768                 queue_push(&todo, -i);  /* end of edges marker */
 769               queue_push(&todo, k);
 770             }
 771           if (!edgestovisit)
 772             te->mark = 2;       /* no edges, done with that one */
 773           else
 774             te->mark = 1;       /* under investigation */
 775           continue;
 776         }
 777       /* oh no, we found a cycle */
 778       /* find start of cycle node (<0) */
 779       for (j = todo.count - 1; j >= 0; j--)
 780         if (todo.elements[j] == -i)
 781           break;
 782       assert(j >= 0);
 783       cycstart = j;
 784       /* build te/edge chain */
 785       k = cycstart;
 786       for (j = k; j < todo.count; j++)
 787         if (todo.elements[j] < 0)
 788           todo.elements[k++] = -todo.elements[j];
 789       cycel = k - cycstart;
 790       assert(cycel > 1);
 791       /* make room for edges, two extra element for cycle loop + terminating 0 */
 792       while (todo.count < cycstart + 2 * cycel + 2)
 793         queue_push(&todo, 0);
 794       cycle = todo.elements + cycstart;
 795       cycle[cycel] = i;         /* close the loop */
 796       cycle[2 * cycel + 1] = 0; /* terminator */
 797       for (k = cycel; k > 0; k--)
 798         {
 799           cycle[k * 2] = cycle[k];
 800           te = od.tes + cycle[k - 1];
 801           if (te->mark == 1)
 802             te->mark = 0;       /* reset investigation marker */
 803           /* printf("searching for edge from %d to %d\n", cycle[k - 1], cycle[k]); */
 804           for (j = te->edges; od.edgedata[j]; j += 2)
 805             if (od.edgedata[j] == cycle[k])
 806               break;
 807           assert(od.edgedata[j]);
 808           cycle[k * 2 - 1] = j;
 809         }
 810       /* now cycle looks like this: */
 811       /* te1 edge te2 edge te3 ... teN edge te1 0 */
 812       breakcycle(&od, cycle);
 813       broken++;
 814       /* restart with start of cycle */
 815       todo.count = cycstart + 1;
 816     }
 817   printf("Broken: %d\n", broken);
 818
 819   numedge = 0;
 820   for (i = 1, te = od.tes + i; i < numte; i++, te++)
 821     {
 822 #if 0
 823       printf("TE #%d, %d(%s)\n", i, te->p, solvid2str(pool, te->p));
 824 #endif
 825       for (j = te->edges; od.edgedata[j]; j += 2)
 826         {
 827 #if 0
 828           struct transel *te2 = od.tes + od.edgedata[j];
 829           if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 830             continue;
 831           printf("  depends %x on TE %d, %d(%s)\n", od.edgedata[j + 1], od.edgedata[j], te2->p, solvid2str(pool, te2->p));
 832 #endif
 833           numedge++;
 834         }
 835     }
 836   printf("TEs: %d, Edges: %d, Space: %d\n", numte - 1, numedge, od.nedgedata / 2);
 837 }