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