src/order.c

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