00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #include <stdio.h>
00015 #include <stdlib.h>
00016 #include <unistd.h>
00017 #include <string.h>
00018 #include <assert.h>
00019
00020 #include "transaction.h"
00021 #include "solver.h"
00022 #include "bitmap.h"
00023 #include "pool.h"
00024 #include "poolarch.h"
00025 #include "evr.h"
00026 #include "util.h"
00027
00028 static int
00029 obsq_sortcmp(const void *ap, const void *bp, void *dp)
00030 {
00031 Id a, b, oa, ob;
00032 Pool *pool = dp;
00033 Solvable *s, *oas, *obs;
00034 int r;
00035
00036 a = ((Id *)ap)[0];
00037 oa = ((Id *)ap)[1];
00038 b = ((Id *)bp)[0];
00039 ob = ((Id *)bp)[1];
00040 if (a != b)
00041 return a - b;
00042 if (oa == ob)
00043 return 0;
00044 s = pool->solvables + a;
00045 oas = pool->solvables + oa;
00046 obs = pool->solvables + ob;
00047 if (oas->name != obs->name)
00048 {
00049 if (oas->name == s->name)
00050 return -1;
00051 if (obs->name == s->name)
00052 return 1;
00053 return strcmp(id2str(pool, oas->name), id2str(pool, obs->name));
00054 }
00055 r = evrcmp(pool, oas->evr, obs->evr, EVRCMP_COMPARE);
00056 if (r)
00057 return -r;
00058 return oa - ob;
00059 }
00060
00061 void
00062 transaction_all_obs_pkgs(Transaction *trans, Id p, Queue *pkgs)
00063 {
00064 Pool *pool = trans->pool;
00065 Solvable *s = pool->solvables + p;
00066 Queue *ti = &trans->transaction_info;
00067 Id q;
00068 int i;
00069
00070 queue_empty(pkgs);
00071 if (p <= 0 || !s->repo)
00072 return;
00073 if (s->repo == pool->installed)
00074 {
00075 q = trans->transaction_installed[p - pool->installed->start];
00076 if (!q)
00077 return;
00078 if (q > 0)
00079 {
00080 queue_push(pkgs, q);
00081 return;
00082 }
00083
00084 for (i = 0; i < ti->count; i += 2)
00085 if (ti->elements[i + 1] == p)
00086 {
00087 queue_push(pkgs, p);
00088 queue_push(pkgs, ti->elements[i]);
00089 }
00090
00091 if (pkgs->count > 2)
00092 sat_sort(pkgs->elements, pkgs->count / 2, 2 * sizeof(Id), obsq_sortcmp, pool);
00093 for (i = 0; i < pkgs->count; i += 2)
00094 pkgs->elements[i / 2] = pkgs->elements[i + 1];
00095 pkgs->count /= 2;
00096 }
00097 else
00098 {
00099
00100 for (i = 0; i < ti->count; i += 2)
00101 {
00102 if (ti->elements[i] == p)
00103 queue_push(pkgs, ti->elements[i + 1]);
00104 else if (pkgs->count)
00105 break;
00106 }
00107 }
00108 }
00109
00110 Id
00111 transaction_obs_pkg(Transaction *trans, Id p)
00112 {
00113 Pool *pool = trans->pool;
00114 Solvable *s = pool->solvables + p;
00115 Queue ti;
00116 Id tibuf[5];
00117
00118 if (p <= 0 || !s->repo)
00119 return 0;
00120 if (s->repo == pool->installed)
00121 {
00122 p = trans->transaction_installed[p - pool->installed->start];
00123 return p < 0 ? -p : p;
00124 }
00125 queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
00126 transaction_all_obs_pkgs(trans, p, &ti);
00127 p = ti.count ? ti.elements[0] : 0;
00128 queue_free(&ti);
00129 return p;
00130 }
00131
00132
00133
00134
00135
00136
00137 static Id
00138 transaction_base_type(Transaction *trans, Id p)
00139 {
00140 Pool *pool = trans->pool;
00141 Solvable *s, *s2;
00142 int r;
00143 Id p2;
00144
00145 if (!MAPTST(&trans->transactsmap, p))
00146 return SOLVER_TRANSACTION_IGNORE;
00147 p2 = transaction_obs_pkg(trans, p);
00148 if (pool->installed && pool->solvables[p].repo == pool->installed)
00149 {
00150
00151 if (!p2)
00152 return SOLVER_TRANSACTION_ERASE;
00153 s = pool->solvables + p;
00154 s2 = pool->solvables + p2;
00155 if (s->name == s2->name)
00156 {
00157 if (s->evr == s2->evr && solvable_identical(s, s2))
00158 return SOLVER_TRANSACTION_REINSTALLED;
00159 r = evrcmp(pool, s->evr, s2->evr, EVRCMP_COMPARE);
00160 if (r < 0)
00161 return SOLVER_TRANSACTION_UPGRADED;
00162 else if (r > 0)
00163 return SOLVER_TRANSACTION_DOWNGRADED;
00164 return SOLVER_TRANSACTION_CHANGED;
00165 }
00166 return SOLVER_TRANSACTION_OBSOLETED;
00167 }
00168 else
00169 {
00170 int noobs = trans->noobsmap.size && MAPTST(&trans->noobsmap, p);
00171 if (noobs)
00172 return p2 ? SOLVER_TRANSACTION_MULTIREINSTALL : SOLVER_TRANSACTION_MULTIINSTALL;
00173 if (!p2)
00174 return SOLVER_TRANSACTION_INSTALL;
00175 s = pool->solvables + p;
00176 s2 = pool->solvables + p2;
00177 if (s->name == s2->name)
00178 {
00179 if (s->evr == s2->evr && solvable_identical(s, s2))
00180 return SOLVER_TRANSACTION_REINSTALL;
00181 r = evrcmp(pool, s->evr, s2->evr, EVRCMP_COMPARE);
00182 if (r > 0)
00183 return SOLVER_TRANSACTION_UPGRADE;
00184 else if (r < 0)
00185 return SOLVER_TRANSACTION_DOWNGRADE;
00186 else
00187 return SOLVER_TRANSACTION_CHANGE;
00188 }
00189 return SOLVER_TRANSACTION_OBSOLETES;
00190 }
00191 }
00192
00193
00194
00195
00196
00197
00198
00199
00200 Id
00201 transaction_type(Transaction *trans, Id p, int mode)
00202 {
00203 Pool *pool = trans->pool;
00204 Solvable *s = pool->solvables + p;
00205 Queue oq, rq;
00206 Id type, q;
00207 int i, j, ref = 0;
00208 const char *n;
00209
00210 if (!s->repo)
00211 return SOLVER_TRANSACTION_IGNORE;
00212
00213 n = id2str(pool, s->name);
00214 if (!strncmp(n, "patch:", 6))
00215 return SOLVER_TRANSACTION_IGNORE;
00216 if (!strncmp(n, "pattern:", 8))
00217 return SOLVER_TRANSACTION_IGNORE;
00218
00219 type = transaction_base_type(trans, p);
00220
00221 if (type == SOLVER_TRANSACTION_IGNORE)
00222 return SOLVER_TRANSACTION_IGNORE;
00223
00224 if ((mode & SOLVER_TRANSACTION_RPM_ONLY) != 0)
00225 {
00226
00227 if (type == SOLVER_TRANSACTION_ERASE || type == SOLVER_TRANSACTION_INSTALL || type == SOLVER_TRANSACTION_MULTIINSTALL)
00228 return type;
00229 if (s->repo == pool->installed)
00230 return SOLVER_TRANSACTION_IGNORE;
00231 if (type == SOLVER_TRANSACTION_MULTIREINSTALL)
00232 return SOLVER_TRANSACTION_MULTIINSTALL;
00233 return SOLVER_TRANSACTION_INSTALL;
00234 }
00235
00236 if ((mode & SOLVER_TRANSACTION_SHOW_MULTIINSTALL) == 0)
00237 {
00238
00239
00240 if (type == SOLVER_TRANSACTION_MULTIINSTALL)
00241 type = SOLVER_TRANSACTION_INSTALL;
00242 if (type == SOLVER_TRANSACTION_MULTIREINSTALL)
00243 type = SOLVER_TRANSACTION_REINSTALL;
00244 }
00245
00246 if ((mode & SOLVER_TRANSACTION_CHANGE_IS_REINSTALL))
00247 {
00248
00249
00250 if (type == SOLVER_TRANSACTION_CHANGED)
00251 type = SOLVER_TRANSACTION_REINSTALLED;
00252 else if (type == SOLVER_TRANSACTION_CHANGE)
00253 type = SOLVER_TRANSACTION_REINSTALL;
00254 }
00255
00256 if (type == SOLVER_TRANSACTION_ERASE || type == SOLVER_TRANSACTION_INSTALL || type == SOLVER_TRANSACTION_MULTIINSTALL)
00257 return type;
00258
00259 if (s->repo == pool->installed && (mode & SOLVER_TRANSACTION_SHOW_ACTIVE) == 0)
00260 {
00261
00262 if ((mode & SOLVER_TRANSACTION_SHOW_OBSOLETES) == 0 && type == SOLVER_TRANSACTION_OBSOLETED)
00263 type = SOLVER_TRANSACTION_ERASE;
00264 return type;
00265 }
00266 if (s->repo != pool->installed && (mode & SOLVER_TRANSACTION_SHOW_ACTIVE) != 0)
00267 {
00268
00269 if ((mode & SOLVER_TRANSACTION_SHOW_OBSOLETES) == 0 && type == SOLVER_TRANSACTION_OBSOLETES)
00270 type = SOLVER_TRANSACTION_INSTALL;
00271 return type;
00272 }
00273
00274
00275
00276
00277 if ((mode & (SOLVER_TRANSACTION_SHOW_ALL|SOLVER_TRANSACTION_SHOW_OBSOLETES)) == (SOLVER_TRANSACTION_SHOW_ALL|SOLVER_TRANSACTION_SHOW_OBSOLETES))
00278 return SOLVER_TRANSACTION_IGNORE;
00279
00280
00281
00282
00283
00284
00285 q = transaction_obs_pkg(trans, p);
00286
00287 if ((mode & SOLVER_TRANSACTION_SHOW_OBSOLETES) == 0)
00288 {
00289 Solvable *sq = pool->solvables + q;
00290 if (sq->name != s->name)
00291 {
00292
00293 if (s->repo == pool->installed)
00294 return SOLVER_TRANSACTION_ERASE;
00295 else if (type == SOLVER_TRANSACTION_MULTIREINSTALL)
00296 return SOLVER_TRANSACTION_MULTIINSTALL;
00297 else
00298 return SOLVER_TRANSACTION_INSTALL;
00299 }
00300 }
00301
00302
00303
00304 if (transaction_obs_pkg(trans, q) == p)
00305 return SOLVER_TRANSACTION_IGNORE;
00306
00307
00308 queue_init(&oq);
00309 queue_init(&rq);
00310 transaction_all_obs_pkgs(trans, p, &oq);
00311 for (i = 0; i < oq.count; i++)
00312 {
00313 q = oq.elements[i];
00314 if ((mode & SOLVER_TRANSACTION_SHOW_OBSOLETES) == 0)
00315 {
00316 Solvable *sq = pool->solvables + q;
00317 if (sq->name != s->name)
00318 continue;
00319 }
00320
00321 if ((mode & SOLVER_TRANSACTION_SHOW_ALL) != 0)
00322 {
00323 transaction_all_obs_pkgs(trans, q, &rq);
00324 for (j = 0; j < rq.count; j++)
00325 if (rq.elements[j] == p)
00326 {
00327 ref = 1;
00328 break;
00329 }
00330 if (ref)
00331 break;
00332 }
00333 else if (transaction_obs_pkg(trans, q) == p)
00334 {
00335 ref = 1;
00336 break;
00337 }
00338 }
00339 queue_free(&oq);
00340 queue_free(&rq);
00341
00342 if (!ref)
00343 {
00344
00345 if (s->repo == pool->installed)
00346 return SOLVER_TRANSACTION_ERASE;
00347 else if (type == SOLVER_TRANSACTION_MULTIREINSTALL)
00348 return SOLVER_TRANSACTION_MULTIINSTALL;
00349 else
00350 return SOLVER_TRANSACTION_INSTALL;
00351 }
00352
00353 return SOLVER_TRANSACTION_IGNORE;
00354 }
00355
00356
00357
00358 static int
00359 classify_cmp(const void *ap, const void *bp, void *dp)
00360 {
00361 Transaction *trans = dp;
00362 Pool *pool = trans->pool;
00363 const Id *a = ap;
00364 const Id *b = bp;
00365 int r;
00366
00367 r = a[0] - b[0];
00368 if (r)
00369 return r;
00370 r = a[2] - b[2];
00371 if (r)
00372 return a[2] && b[2] ? strcmp(id2str(pool, a[2]), id2str(pool, b[2])) : r;
00373 r = a[3] - b[3];
00374 if (r)
00375 return a[3] && b[3] ? strcmp(id2str(pool, a[3]), id2str(pool, b[3])) : r;
00376 return 0;
00377 }
00378
00379 static int
00380 classify_cmp_pkgs(const void *ap, const void *bp, void *dp)
00381 {
00382 Transaction *trans = dp;
00383 Pool *pool = trans->pool;
00384 Id a = *(Id *)ap;
00385 Id b = *(Id *)bp;
00386 Solvable *sa, *sb;
00387
00388 sa = pool->solvables + a;
00389 sb = pool->solvables + b;
00390 if (sa->name != sb->name)
00391 return strcmp(id2str(pool, sa->name), id2str(pool, sb->name));
00392 if (sa->evr != sb->evr)
00393 {
00394 int r = evrcmp(pool, sa->evr, sb->evr, EVRCMP_COMPARE);
00395 if (r)
00396 return r;
00397 }
00398 return a - b;
00399 }
00400
00401 void
00402 transaction_classify(Transaction *trans, int mode, Queue *classes)
00403 {
00404 Pool *pool = trans->pool;
00405 int ntypes[SOLVER_TRANSACTION_MAXTYPE + 1];
00406 Solvable *s, *sq;
00407 Id v, vq, type, p, q;
00408 int i, j;
00409
00410 queue_empty(classes);
00411 memset(ntypes, 0, sizeof(ntypes));
00412
00413 for (i = 0; i < trans->steps.count; i++)
00414 {
00415 p = trans->steps.elements[i];
00416 s = pool->solvables + p;
00417 type = transaction_type(trans, p, mode);
00418 ntypes[type]++;
00419 if (!pool->installed || s->repo != pool->installed)
00420 continue;
00421
00422 q = transaction_obs_pkg(trans, p);
00423 if (!q)
00424 continue;
00425 sq = pool->solvables + q;
00426
00427 v = s->arch;
00428 vq = sq->arch;
00429 if (v != vq)
00430 {
00431 if ((mode & SOLVER_TRANSACTION_MERGE_ARCHCHANGES) != 0)
00432 v = vq = 0;
00433 for (j = 0; j < classes->count; j += 4)
00434 if (classes->elements[j] == SOLVER_TRANSACTION_ARCHCHANGE && classes->elements[j + 2] == v && classes->elements[j + 3] == vq)
00435 break;
00436 if (j == classes->count)
00437 {
00438 queue_push(classes, SOLVER_TRANSACTION_ARCHCHANGE);
00439 queue_push(classes, 1);
00440 queue_push(classes, v);
00441 queue_push(classes, vq);
00442 }
00443 else
00444 classes->elements[j + 1]++;
00445 }
00446
00447 v = s->vendor ? s->vendor : 1;
00448 vq = sq->vendor ? sq->vendor : 1;
00449 if (v != vq)
00450 {
00451 if ((mode & SOLVER_TRANSACTION_MERGE_VENDORCHANGES) != 0)
00452 v = vq = 0;
00453 for (j = 0; j < classes->count; j += 4)
00454 if (classes->elements[j] == SOLVER_TRANSACTION_VENDORCHANGE && classes->elements[j + 2] == v && classes->elements[j + 3] == vq)
00455 break;
00456 if (j == classes->count)
00457 {
00458 queue_push(classes, SOLVER_TRANSACTION_VENDORCHANGE);
00459 queue_push(classes, 1);
00460 queue_push(classes, v);
00461 queue_push(classes, vq);
00462 }
00463 else
00464 classes->elements[j + 1]++;
00465 }
00466 }
00467
00468 if (classes->count > 4)
00469 sat_sort(classes->elements, classes->count / 4, 4 * sizeof(Id), classify_cmp, trans);
00470
00471 i = SOLVER_TRANSACTION_ERASE;
00472 if (ntypes[i])
00473 {
00474 queue_unshift(classes, 0);
00475 queue_unshift(classes, 0);
00476 queue_unshift(classes, ntypes[i]);
00477 queue_unshift(classes, i);
00478 }
00479 for (i = SOLVER_TRANSACTION_MAXTYPE; i > 0; i--)
00480 {
00481 if (!ntypes[i])
00482 continue;
00483 if (i == SOLVER_TRANSACTION_ERASE)
00484 continue;
00485 queue_unshift(classes, 0);
00486 queue_unshift(classes, 0);
00487 queue_unshift(classes, ntypes[i]);
00488 queue_unshift(classes, i);
00489 }
00490 }
00491
00492 void
00493 transaction_classify_pkgs(Transaction *trans, int mode, Id class, Id from, Id to, Queue *pkgs)
00494 {
00495 Pool *pool = trans->pool;
00496 int i;
00497 Id type, p, q;
00498 Solvable *s, *sq;
00499
00500 queue_empty(pkgs);
00501 for (i = 0; i < trans->steps.count; i++)
00502 {
00503 p = trans->steps.elements[i];
00504 s = pool->solvables + p;
00505 if (class <= SOLVER_TRANSACTION_MAXTYPE)
00506 {
00507 type = transaction_type(trans, p, mode);
00508 if (type == class)
00509 queue_push(pkgs, p);
00510 continue;
00511 }
00512 if (!pool->installed || s->repo != pool->installed)
00513 continue;
00514 q = transaction_obs_pkg(trans, p);
00515 if (!q)
00516 continue;
00517 sq = pool->solvables + q;
00518 if (class == SOLVER_TRANSACTION_ARCHCHANGE)
00519 {
00520 if ((!from && !to) || (s->arch == from && sq->arch == to))
00521 queue_push(pkgs, p);
00522 continue;
00523 }
00524 if (class == SOLVER_TRANSACTION_VENDORCHANGE)
00525 {
00526 Id v = s->vendor ? s->vendor : 1;
00527 Id vq = sq->vendor ? sq->vendor : 1;
00528 if ((!from && !to) || (v == from && vq == to))
00529 queue_push(pkgs, p);
00530 continue;
00531 }
00532 }
00533 if (pkgs->count > 1)
00534 sat_sort(pkgs->elements, pkgs->count, sizeof(Id), classify_cmp_pkgs, trans);
00535 }
00536
00537 static void
00538 create_transaction_info(Transaction *trans, Queue *decisionq)
00539 {
00540 Pool *pool = trans->pool;
00541 Queue *ti = &trans->transaction_info;
00542 Repo *installed = pool->installed;
00543 int i, j, noobs;
00544 Id p, p2, pp2;
00545 Solvable *s, *s2;
00546
00547 queue_empty(ti);
00548 trans->transaction_installed = sat_free(trans->transaction_installed);
00549 if (!installed)
00550 return;
00551 for (i = 0; i < decisionq->count; i++)
00552 {
00553 p = decisionq->elements[i];
00554 if (p <= 0 || p == SYSTEMSOLVABLE)
00555 continue;
00556 s = pool->solvables + p;
00557 if (!s->repo || s->repo == installed)
00558 continue;
00559 noobs = trans->noobsmap.size && MAPTST(&trans->noobsmap, p);
00560 FOR_PROVIDES(p2, pp2, s->name)
00561 {
00562 if (!MAPTST(&trans->transactsmap, p2))
00563 continue;
00564 s2 = pool->solvables + p2;
00565 if (s2->repo != installed)
00566 continue;
00567 if (noobs && (s->name != s2->name || s->evr != s2->evr || s->arch != s2->arch))
00568 continue;
00569 if (!pool->implicitobsoleteusesprovides && s->name != s2->name)
00570 continue;
00571 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
00572 continue;
00573 queue_push(ti, p);
00574 queue_push(ti, p2);
00575 }
00576 if (s->obsoletes && !noobs)
00577 {
00578 Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
00579 while ((obs = *obsp++) != 0)
00580 {
00581 FOR_PROVIDES(p2, pp2, obs)
00582 {
00583 s2 = pool->solvables + p2;
00584 if (s2->repo != installed)
00585 continue;
00586 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
00587 continue;
00588 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
00589 continue;
00590 queue_push(ti, p);
00591 queue_push(ti, p2);
00592 }
00593 }
00594 }
00595 }
00596 sat_sort(ti->elements, ti->count / 2, 2 * sizeof(Id), obsq_sortcmp, pool);
00597
00598 for (i = j = 0; i < ti->count; i += 2)
00599 {
00600 if (j && ti->elements[i] == ti->elements[j - 2] && ti->elements[i + 1] == ti->elements[j - 1])
00601 continue;
00602 ti->elements[j++] = ti->elements[i];
00603 ti->elements[j++] = ti->elements[i + 1];
00604 }
00605 ti->count = j;
00606
00607
00608 trans->transaction_installed = sat_calloc(installed->end - installed->start, sizeof(Id));
00609 for (i = 0; i < ti->count; i += 2)
00610 {
00611 j = ti->elements[i + 1] - installed->start;
00612 if (!trans->transaction_installed[j])
00613 trans->transaction_installed[j] = ti->elements[i];
00614 else
00615 {
00616
00617 Id q[4];
00618 if (trans->transaction_installed[j] > 0)
00619 trans->transaction_installed[j] = -trans->transaction_installed[j];
00620 q[0] = q[2] = ti->elements[i + 1];
00621 q[1] = ti->elements[i];
00622 q[3] = -trans->transaction_installed[j];
00623 if (obsq_sortcmp(q, q + 2, pool) < 0)
00624 trans->transaction_installed[j] = -ti->elements[i];
00625 }
00626 }
00627 }
00628
00629
00630 void
00631 transaction_calculate(Transaction *trans, Queue *decisionq, Map *noobsmap)
00632 {
00633 Pool *pool = trans->pool;
00634 Repo *installed = pool->installed;
00635 int i, neednoobs;
00636 Id p;
00637 Solvable *s;
00638
00639 if (noobsmap && !noobsmap->size)
00640 noobsmap = 0;
00641 queue_empty(&trans->steps);
00642 map_init(&trans->transactsmap, pool->nsolvables);
00643 neednoobs = 0;
00644 for (i = 0; i < decisionq->count; i++)
00645 {
00646 p = decisionq->elements[i];
00647 s = pool->solvables + (p > 0 ? p : -p);
00648 if (!s->repo)
00649 continue;
00650 if (installed && s->repo == installed && p < 0)
00651 MAPSET(&trans->transactsmap, -p);
00652 if ((!installed || s->repo != installed) && p > 0)
00653 {
00654 #if 0
00655 const char *n = id2str(pool, s->name);
00656 if (!strncmp(n, "patch:", 6))
00657 continue;
00658 if (!strncmp(n, "pattern:", 8))
00659 continue;
00660 #endif
00661 MAPSET(&trans->transactsmap, p);
00662 if (noobsmap && MAPTST(noobsmap, p))
00663 neednoobs = 1;
00664 }
00665 }
00666 MAPCLR(&trans->transactsmap, SYSTEMSOLVABLE);
00667 if (neednoobs)
00668 map_init_clone(&trans->noobsmap, noobsmap);
00669
00670 create_transaction_info(trans, decisionq);
00671
00672 if (installed)
00673 {
00674 FOR_REPO_SOLVABLES(installed, p, s)
00675 {
00676 if (MAPTST(&trans->transactsmap, p))
00677 queue_push(&trans->steps, p);
00678 }
00679 }
00680 for (i = 0; i < decisionq->count; i++)
00681 {
00682 p = decisionq->elements[i];
00683 if (p > 0 && MAPTST(&trans->transactsmap, p))
00684 queue_push(&trans->steps, p);
00685 }
00686 }
00687
00688 int
00689 transaction_installedresult(Transaction *trans, Queue *installedq)
00690 {
00691 Pool *pool = trans->pool;
00692 Repo *installed = pool->installed;
00693 Solvable *s;
00694 int i, cutoff;
00695 Id p;
00696
00697 queue_empty(installedq);
00698
00699 for (i = 0; i < trans->steps.count; i++)
00700 {
00701 p = trans->steps.elements[i];
00702 s = pool->solvables + p;
00703 if (installed && s->repo == installed)
00704 continue;
00705 queue_push(installedq, p);
00706 }
00707 cutoff = installedq->count;
00708 if (installed)
00709 {
00710 FOR_REPO_SOLVABLES(installed, p, s)
00711 if (!MAPTST(&trans->transactsmap, p))
00712 queue_push(installedq, p);
00713 }
00714 return cutoff;
00715 }
00716
00717 static void
00718 transaction_create_installedmap(Transaction *trans, Map *installedmap)
00719 {
00720 Pool *pool = trans->pool;
00721 Repo *installed = pool->installed;
00722 Solvable *s;
00723 Id p;
00724 int i;
00725
00726 map_init(installedmap, pool->nsolvables);
00727 for (i = 0; i < trans->steps.count; i++)
00728 {
00729 p = trans->steps.elements[i];
00730 s = pool->solvables + p;
00731 if (!installed || s->repo != installed)
00732 MAPSET(installedmap, p);
00733 }
00734 if (installed)
00735 {
00736 FOR_REPO_SOLVABLES(installed, p, s)
00737 if (!MAPTST(&trans->transactsmap, p))
00738 MAPSET(installedmap, p);
00739 }
00740 }
00741
00742 int
00743 transaction_calc_installsizechange(Transaction *trans)
00744 {
00745 Map installedmap;
00746 int change;
00747
00748 transaction_create_installedmap(trans, &installedmap);
00749 change = pool_calc_installsizechange(trans->pool, &installedmap);
00750 map_free(&installedmap);
00751 return change;
00752 }
00753
00754 void
00755 transaction_calc_duchanges(Transaction *trans, DUChanges *mps, int nmps)
00756 {
00757 Map installedmap;
00758
00759 transaction_create_installedmap(trans, &installedmap);
00760 pool_calc_duchanges(trans->pool, &installedmap, mps, nmps);
00761 map_free(&installedmap);
00762 }
00763
00764 struct _TransactionElement {
00765 Id p;
00766 Id edges;
00767 Id mark;
00768 };
00769
00770 struct _TransactionOrderdata {
00771 struct _TransactionElement *tes;
00772 int ntes;
00773 Id *invedgedata;
00774 int ninvedgedata;
00775 };
00776
00777 #define TYPE_BROKEN (1<<0)
00778 #define TYPE_CON (1<<1)
00779
00780 #define TYPE_REQ_P (1<<2)
00781 #define TYPE_PREREQ_P (1<<3)
00782
00783 #define TYPE_REQ (1<<4)
00784 #define TYPE_PREREQ (1<<5)
00785
00786 #define TYPE_CYCLETAIL (1<<16)
00787 #define TYPE_CYCLEHEAD (1<<17)
00788
00789 #define EDGEDATA_BLOCK 127
00790
00791 void
00792 transaction_init(Transaction *trans, Pool *pool)
00793 {
00794 memset(trans, 0, sizeof(*trans));
00795 trans->pool = pool;
00796 }
00797
00798 void
00799 transaction_init_clone(Transaction *trans, Transaction *srctrans)
00800 {
00801 memset(trans, 0, sizeof(*trans));
00802 trans->pool = srctrans->pool;
00803 queue_init_clone(&trans->steps, &srctrans->steps);
00804 queue_init_clone(&trans->transaction_info, &srctrans->transaction_info);
00805 if (srctrans->transaction_installed)
00806 {
00807 Repo *installed = srctrans->pool->installed;
00808 trans->transaction_installed = sat_calloc(installed->end - installed->start, sizeof(Id));
00809 memcpy(trans->transaction_installed, srctrans->transaction_installed, (installed->end - installed->start) * sizeof(Id));
00810 }
00811 map_init_clone(&trans->transactsmap, &srctrans->transactsmap);
00812 map_init_clone(&trans->noobsmap, &srctrans->noobsmap);
00813 if (srctrans->orderdata)
00814 {
00815 struct _TransactionOrderdata *od = srctrans->orderdata;
00816 trans->orderdata = sat_calloc(1, sizeof(*trans->orderdata));
00817 trans->orderdata->tes = sat_malloc2(od->ntes, sizeof(*od->tes));
00818 memcpy(trans->orderdata->tes, od->tes, od->ntes * sizeof(*od->tes));
00819 trans->orderdata->ntes = od->ntes;
00820 trans->orderdata->invedgedata = sat_malloc2(od->ninvedgedata, sizeof(Id));
00821 memcpy(trans->orderdata->invedgedata, od->invedgedata, od->ninvedgedata * sizeof(Id));
00822 trans->orderdata->ninvedgedata = od->ninvedgedata;
00823 }
00824 }
00825
00826 void
00827 transaction_free(Transaction *trans)
00828 {
00829 queue_free(&trans->steps);
00830 queue_free(&trans->transaction_info);
00831 trans->transaction_installed = sat_free(trans->transaction_installed);
00832 map_free(&trans->transactsmap);
00833 map_free(&trans->noobsmap);
00834 transaction_free_orderdata(trans);
00835 }
00836
00837 void
00838 transaction_free_orderdata(Transaction *trans)
00839 {
00840 if (trans->orderdata)
00841 {
00842 struct _TransactionOrderdata *od = trans->orderdata;
00843 od->tes = sat_free(od->tes);
00844 od->invedgedata = sat_free(od->invedgedata);
00845 trans->orderdata = sat_free(trans->orderdata);
00846 }
00847 }
00848
00849 struct orderdata {
00850 Transaction *trans;
00851 struct _TransactionElement *tes;
00852 int ntes;
00853 Id *edgedata;
00854 int nedgedata;
00855 Id *invedgedata;
00856
00857 Queue cycles;
00858 Queue cyclesdata;
00859 int ncycles;
00860 };
00861
00862 static int
00863 addteedge(struct orderdata *od, int from, int to, int type)
00864 {
00865 int i;
00866 struct _TransactionElement *te;
00867
00868 if (from == to)
00869 return 0;
00870
00871
00872
00873 te = od->tes + from;
00874 for (i = te->edges; od->edgedata[i]; i += 2)
00875 if (od->edgedata[i] == to)
00876 break;
00877
00878 if (type == TYPE_BROKEN)
00879 return od->edgedata[i] && (od->edgedata[i + 1] & TYPE_BROKEN) != 0 ? 1 : 0;
00880 if (od->edgedata[i])
00881 {
00882 od->edgedata[i + 1] |= type;
00883 return 0;
00884 }
00885 if (i + 1 == od->nedgedata)
00886 {
00887
00888 if (!i)
00889 te->edges = ++i;
00890 od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3, sizeof(Id), EDGEDATA_BLOCK);
00891 }
00892 else
00893 {
00894
00895 od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3 + (i - te->edges), sizeof(Id), EDGEDATA_BLOCK);
00896 if (i > te->edges)
00897 memcpy(od->edgedata + od->nedgedata, od->edgedata + te->edges, sizeof(Id) * (i - te->edges));
00898 i = od->nedgedata + (i - te->edges);
00899 te->edges = od->nedgedata;
00900 }
00901 od->edgedata[i] = to;
00902 od->edgedata[i + 1] = type;
00903 od->edgedata[i + 2] = 0;
00904 od->nedgedata = i + 3;
00905 return 0;
00906 }
00907
00908 static int
00909 addedge(struct orderdata *od, Id from, Id to, int type)
00910 {
00911 Transaction *trans = od->trans;
00912 Pool *pool = trans->pool;
00913 Solvable *s;
00914 struct _TransactionElement *te;
00915 int i;
00916
00917
00918 s = pool->solvables + from;
00919 if (s->repo == pool->installed && trans->transaction_installed[from - pool->installed->start])
00920 {
00921
00922 if (trans->transaction_installed[from - pool->installed->start] > 0)
00923 from = trans->transaction_installed[from - pool->installed->start];
00924 else
00925 {
00926 int ret = 0;
00927 Queue ti;
00928 Id tibuf[5];
00929
00930 queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
00931 transaction_all_obs_pkgs(trans, from, &ti);
00932 for (i = 0; i < ti.count; i++)
00933 ret |= addedge(od, ti.elements[i], to, type);
00934 queue_free(&ti);
00935 return ret;
00936 }
00937 }
00938 s = pool->solvables + to;
00939 if (s->repo == pool->installed && trans->transaction_installed[to - pool->installed->start])
00940 {
00941
00942 if (trans->transaction_installed[to - pool->installed->start] > 0)
00943 to = trans->transaction_installed[to - pool->installed->start];
00944 else
00945 {
00946 int ret = 0;
00947 Queue ti;
00948 Id tibuf[5];
00949
00950 queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
00951 transaction_all_obs_pkgs(trans, to, &ti);
00952 for (i = 0; i < ti.count; i++)
00953 ret |= addedge(od, from, ti.elements[i], type);
00954 queue_free(&ti);
00955 return ret;
00956 }
00957 }
00958
00959
00960 for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
00961 if (te->p == to)
00962 break;
00963 if (i == od->ntes)
00964 return 0;
00965 to = i;
00966
00967 for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
00968 if (te->p == from)
00969 break;
00970 if (i == od->ntes)
00971 return 0;
00972
00973 return addteedge(od, i, to, type);
00974 }
00975
00976 #if 1
00977 static int
00978 havechoice(struct orderdata *od, Id p, Id q1, Id q2)
00979 {
00980 Transaction *trans = od->trans;
00981 Pool *pool = trans->pool;
00982 Id ti1buf[5], ti2buf[5];
00983 Queue ti1, ti2;
00984 int i, j;
00985
00986
00987
00988 #if 0
00989 printf("havechoice %d %d %d\n", p, q1, q2);
00990 #endif
00991 if (trans->transaction_installed[q1 - pool->installed->start] == 0)
00992 return 1;
00993 if (trans->transaction_installed[q2 - pool->installed->start] == 0)
00994 return 1;
00995 if (trans->transaction_installed[q1 - pool->installed->start] == trans->transaction_installed[q2 - pool->installed->start])
00996 return 0;
00997 if (trans->transaction_installed[q1 - pool->installed->start] > 0 && trans->transaction_installed[q2 - pool->installed->start] > 0)
00998 return 1;
00999 queue_init_buffer(&ti1, ti1buf, sizeof(ti1buf)/sizeof(*ti1buf));
01000 transaction_all_obs_pkgs(trans, q1, &ti1);
01001 queue_init_buffer(&ti2, ti2buf, sizeof(ti2buf)/sizeof(*ti2buf));
01002 transaction_all_obs_pkgs(trans, q2, &ti2);
01003 for (i = 0; i < ti1.count; i++)
01004 for (j = 0; j < ti2.count; j++)
01005 if (ti1.elements[i] == ti2.elements[j])
01006 {
01007
01008 queue_free(&ti1);
01009 queue_free(&ti2);
01010 return 0;
01011 }
01012 queue_free(&ti1);
01013 queue_free(&ti2);
01014 return 1;
01015 }
01016 #endif
01017
01018 static inline int
01019 havescripts(Pool *pool, Id solvid)
01020 {
01021 Solvable *s = pool->solvables + solvid;
01022 const char *dep;
01023 if (s->requires)
01024 {
01025 Id req, *reqp;
01026 int inpre = 0;
01027 reqp = s->repo->idarraydata + s->requires;
01028 while ((req = *reqp++) != 0)
01029 {
01030 if (req == SOLVABLE_PREREQMARKER)
01031 {
01032 inpre = 1;
01033 continue;
01034 }
01035 if (!inpre)
01036 continue;
01037 dep = id2str(pool, req);
01038 if (*dep == '/' && strcmp(dep, "/sbin/ldconfig") != 0)
01039 return 1;
01040 }
01041 }
01042 return 0;
01043 }
01044
01045 static void
01046 addsolvableedges(struct orderdata *od, Solvable *s)
01047 {
01048 Transaction *trans = od->trans;
01049 Pool *pool = trans->pool;
01050 Id req, *reqp, con, *conp;
01051 Id p, p2, pp2;
01052 int i, j, pre, numins;
01053 Repo *installed = pool->installed;
01054 Solvable *s2;
01055 Queue reqq;
01056 int provbyinst;
01057
01058 #if 0
01059 printf("addsolvableedges %s\n", solvable2str(pool, s));
01060 #endif
01061 p = s - pool->solvables;
01062 queue_init(&reqq);
01063 if (s->requires)
01064 {
01065 reqp = s->repo->idarraydata + s->requires;
01066 pre = TYPE_REQ;
01067 while ((req = *reqp++) != 0)
01068 {
01069 if (req == SOLVABLE_PREREQMARKER)
01070 {
01071 pre = TYPE_PREREQ;
01072 continue;
01073 }
01074 #if 0
01075 if (pre != TYPE_PREREQ && installed && s->repo == installed)
01076 {
01077
01078 if (trans->transaction_installed[p - pool->installed->start])
01079 continue;
01080 }
01081 #endif
01082 queue_empty(&reqq);
01083 numins = 0;
01084 provbyinst = 0;
01085 FOR_PROVIDES(p2, pp2, req)
01086 {
01087 s2 = pool->solvables + p2;
01088 if (p2 == p)
01089 {
01090 reqq.count = 0;
01091 break;
01092 }
01093 if (s2->repo == installed && !MAPTST(&trans->transactsmap, p2))
01094 {
01095 provbyinst = 1;
01096 #if 0
01097 printf("IGNORE inst provides %s by %s\n", dep2str(pool, req), solvable2str(pool, s2));
01098 reqq.count = 0;
01099 break;
01100 #else
01101 continue;
01102 #endif
01103 }
01104 if (s2->repo != installed && !MAPTST(&trans->transactsmap, p2))
01105 continue;
01106
01107 if (s->repo == installed)
01108 {
01109
01110 queue_pushunique(&reqq, p2);
01111 if (s2->repo != installed)
01112 numins++;
01113 }
01114 else
01115 {
01116 if (s2->repo == installed)
01117 continue;
01118 queue_pushunique(&reqq, p2);
01119 }
01120 }
01121 if (provbyinst)
01122 {
01123
01124 for (i = j = 0; i < reqq.count; i++)
01125 if (pool->solvables[reqq.elements[i]].repo != installed)
01126 reqq.elements[j++] = reqq.elements[i];
01127 reqq.count = j;
01128 }
01129
01130 if (numins && reqq.count)
01131 {
01132 if (s->repo == installed)
01133 {
01134 for (i = 0; i < reqq.count; i++)
01135 {
01136 if (pool->solvables[reqq.elements[i]].repo == installed)
01137 {
01138 for (j = 0; j < reqq.count; j++)
01139 {
01140 if (pool->solvables[reqq.elements[j]].repo != installed)
01141 {
01142 if (trans->transaction_installed[reqq.elements[i] - pool->installed->start] == reqq.elements[j])
01143 continue;
01144 #if 0
01145 printf("add interrreq uninst->inst edge (%s -> %s -> %s)\n", solvid2str(pool, reqq.elements[i]), dep2str(pool, req), solvid2str(pool, reqq.elements[j]));
01146 #endif
01147 addedge(od, reqq.elements[i], reqq.elements[j], pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
01148 }
01149 }
01150 }
01151 }
01152 }
01153
01154 for (i = j = 0; i < reqq.count; i++)
01155 if (pool->solvables[reqq.elements[i]].repo != installed)
01156 reqq.elements[j++] = reqq.elements[i];
01157 reqq.count = j;
01158 }
01159 if (!reqq.count)
01160 continue;
01161 for (i = 0; i < reqq.count; i++)
01162 {
01163 int choice = 0;
01164 p2 = reqq.elements[i];
01165 if (pool->solvables[p2].repo != installed)
01166 {
01167
01168 choice = reqq.count - 1;
01169 if (pool->solvables[p].repo != installed)
01170 {
01171 #if 0
01172 printf("add inst->inst edge choice %d (%s -> %s -> %s)\n", choice, solvid2str(pool, p), dep2str(pool, req), solvid2str(pool, p2));
01173 #endif
01174 addedge(od, p, p2, pre);
01175 }
01176 else
01177 {
01178 #if 0
01179 printf("add uninst->inst edge choice %d (%s -> %s -> %s)\n", choice, solvid2str(pool, p), dep2str(pool, req), solvid2str(pool, p2));
01180 #endif
01181 addedge(od, p, p2, pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
01182 }
01183 }
01184 else
01185 {
01186 if (s->repo != installed)
01187 continue;
01188
01189
01190 if (trans->transaction_installed[p - installed->start] && !havescripts(pool, p))
01191 {
01192
01193
01194 continue;
01195 }
01196 #if 1
01197 choice = 0;
01198 for (j = 0; j < reqq.count; j++)
01199 {
01200 if (i == j)
01201 continue;
01202 if (havechoice(od, p, reqq.elements[i], reqq.elements[j]))
01203 choice++;
01204 }
01205 #endif
01206 #if 0
01207 printf("add uninst->uninst edge choice %d (%s -> %s -> %s)\n", choice, solvid2str(pool, p), dep2str(pool, req), solvid2str(pool, p2));
01208 #endif
01209 addedge(od, p2, p, pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
01210 }
01211 }
01212 }
01213 }
01214 if (s->conflicts)
01215 {
01216 conp = s->repo->idarraydata + s->conflicts;
01217 while ((con = *conp++) != 0)
01218 {
01219 FOR_PROVIDES(p2, pp2, con)
01220 {
01221 if (p2 == p)
01222 continue;
01223 s2 = pool->solvables + p2;
01224 if (!s2->repo)
01225 continue;
01226 if (s->repo == installed)
01227 {
01228 if (s2->repo != installed && MAPTST(&trans->transactsmap, p2))
01229 {
01230
01231 #if 0
01232 printf("add conflict uninst->inst edge (%s -> %s -> %s)\n", solvid2str(pool, p2), dep2str(pool, con), solvid2str(pool, p));
01233 #endif
01234 addedge(od, p2, p, TYPE_CON);
01235 }
01236 }
01237 else
01238 {
01239 if (s2->repo == installed && MAPTST(&trans->transactsmap, p2))
01240 {
01241
01242 #if 0
01243 printf("add conflict uninst->inst edge (%s -> %s -> %s)\n", solvid2str(pool, p), dep2str(pool, con), solvid2str(pool, p2));
01244 #endif
01245 addedge(od, p, p2, TYPE_CON);
01246 }
01247 }
01248
01249 }
01250 }
01251 }
01252 if (s->repo == installed && solvable_lookup_idarray(s, SOLVABLE_TRIGGERS, &reqq) && reqq.count)
01253 {
01254
01255
01256 for (i = 0; i < reqq.count; i++)
01257 {
01258 Id tri = reqq.elements[i];
01259 FOR_PROVIDES(p2, pp2, tri)
01260 {
01261 if (p2 == p)
01262 continue;
01263 s2 = pool->solvables + p2;
01264 if (!s2->repo)
01265 continue;
01266 if (s2->name == s->name)
01267 continue;
01268 if (s2->repo != installed && MAPTST(&trans->transactsmap, p2))
01269 {
01270
01271 #if 0
01272 printf("add trigger uninst->inst edge (%s -> %s -> %s)\n", solvid2str(pool, p2), dep2str(pool, tri), solvid2str(pool, p));
01273 #endif
01274 addedge(od, p2, p, TYPE_CON);
01275 }
01276 }
01277 }
01278 }
01279 queue_free(&reqq);
01280 }
01281
01282
01283
01284 static void
01285 breakcycle(struct orderdata *od, Id *cycle)
01286 {
01287 Pool *pool = od->trans->pool;
01288 Id ddegmin, ddegmax, ddeg;
01289 int k, l;
01290 struct _TransactionElement *te;
01291
01292 l = 0;
01293 ddegmin = ddegmax = 0;
01294 for (k = 0; cycle[k + 1]; k += 2)
01295 {
01296 ddeg = od->edgedata[cycle[k + 1] + 1];
01297 if (ddeg > ddegmax)
01298 ddegmax = ddeg;
01299 if (!k || ddeg < ddegmin)
01300 {
01301 l = k;
01302 ddegmin = ddeg;
01303 continue;
01304 }
01305 if (ddeg == ddegmin)
01306 {
01307 if (havescripts(pool, od->tes[cycle[l]].p) && !havescripts(pool, od->tes[cycle[k]].p))
01308 {
01309
01310 l = k;
01311 ddegmin = ddeg;
01312 continue;
01313 }
01314
01315 }
01316 }
01317
01318
01319 queue_push(&od->cycles, od->cyclesdata.count);
01320 queue_push(&od->cycles, k / 2);
01321 queue_push(&od->cycles, od->edgedata[cycle[l + 1] + 1]);
01322 od->ncycles++;
01323 for (k = l;;)
01324 {
01325 k += 2;
01326 if (!cycle[k + 1])
01327 k = 0;
01328 queue_push(&od->cyclesdata, cycle[k]);
01329 if (k == l)
01330 break;
01331 }
01332 queue_push(&od->cyclesdata, 0);
01333
01334
01335 od->edgedata[cycle[l + 1] + 1] |= TYPE_BROKEN;
01336
01337 #if 1
01338 if (ddegmin < TYPE_REQ)
01339 return;
01340 #endif
01341
01342
01343 if (ddegmin >= TYPE_REQ && (ddegmax & TYPE_PREREQ) != 0)
01344 POOL_DEBUG(SAT_DEBUG_STATS, "CRITICAL ");
01345 POOL_DEBUG(SAT_DEBUG_STATS, "cycle: --> ");
01346 for (k = 0; cycle[k + 1]; k += 2)
01347 {
01348 te = od->tes + cycle[k];
01349 if ((od->edgedata[cycle[k + 1] + 1] & TYPE_BROKEN) != 0)
01350 POOL_DEBUG(SAT_DEBUG_STATS, "%s ##%x##> ", solvid2str(pool, te->p), od->edgedata[cycle[k + 1] + 1]);
01351 else
01352 POOL_DEBUG(SAT_DEBUG_STATS, "%s --%x--> ", solvid2str(pool, te->p), od->edgedata[cycle[k + 1] + 1]);
01353 }
01354 POOL_DEBUG(SAT_DEBUG_STATS, "\n");
01355 }
01356
01357 static inline void
01358 dump_tes(struct orderdata *od)
01359 {
01360 Pool *pool = od->trans->pool;
01361 int i, j;
01362 Queue obsq;
01363 struct _TransactionElement *te, *te2;
01364
01365 queue_init(&obsq);
01366 for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
01367 {
01368 Solvable *s = pool->solvables + te->p;
01369 POOL_DEBUG(SAT_DEBUG_RESULT, "TE %4d: %c%s\n", i, s->repo == pool->installed ? '-' : '+', solvable2str(pool, s));
01370 if (s->repo != pool->installed)
01371 {
01372 queue_empty(&obsq);
01373 transaction_all_obs_pkgs(od->trans, te->p, &obsq);
01374 for (j = 0; j < obsq.count; j++)
01375 POOL_DEBUG(SAT_DEBUG_RESULT, " -%s\n", solvid2str(pool, obsq.elements[j]));
01376 }
01377 for (j = te->edges; od->edgedata[j]; j += 2)
01378 {
01379 te2 = od->tes + od->edgedata[j];
01380 if ((od->edgedata[j + 1] & TYPE_BROKEN) == 0)
01381 POOL_DEBUG(SAT_DEBUG_RESULT, " --%x--> TE %4d: %s\n", od->edgedata[j + 1], od->edgedata[j], solvid2str(pool, te2->p));
01382 else
01383 POOL_DEBUG(SAT_DEBUG_RESULT, " ##%x##> TE %4d: %s\n", od->edgedata[j + 1], od->edgedata[j], solvid2str(pool, te2->p));
01384 }
01385 }
01386 }
01387
01388 #if 1
01389 static void
01390 reachable(struct orderdata *od, Id i)
01391 {
01392 struct _TransactionElement *te = od->tes + i;
01393 int j, k;
01394
01395 if (te->mark != 0)
01396 return;
01397 te->mark = 1;
01398 for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
01399 {
01400 if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
01401 continue;
01402 if (!od->tes[k].mark)
01403 reachable(od, k);
01404 if (od->tes[k].mark == 2)
01405 {
01406 te->mark = 2;
01407 return;
01408 }
01409 }
01410 te->mark = -1;
01411 }
01412 #endif
01413
01414 static void
01415 addcycleedges(struct orderdata *od, Id *cycle, Queue *todo)
01416 {
01417 #if 0
01418 Transaction *trans = od->trans;
01419 Pool *pool = trans->pool;
01420 #endif
01421 struct _TransactionElement *te;
01422 int i, j, k, tail;
01423 #if 1
01424 int head;
01425 #endif
01426
01427 #if 0
01428 printf("addcycleedges\n");
01429 for (i = 0; (j = cycle[i]) != 0; i++)
01430 printf("cycle %s\n", solvid2str(pool, od->tes[j].p));
01431 #endif
01432
01433
01434
01435
01436 queue_empty(todo);
01437 for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
01438 te->mark = 0;
01439 for (i = 0; (j = cycle[i]) != 0; i++)
01440 {
01441 od->tes[j].mark = -1;
01442 queue_push(todo, j);
01443 }
01444 while (todo->count)
01445 {
01446 i = queue_pop(todo);
01447 te = od->tes + i;
01448 if (te->mark > 0)
01449 continue;
01450 te->mark = te->mark < 0 ? 2 : 1;
01451 for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
01452 {
01453 if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
01454 continue;
01455 if (od->tes[k].mark > 0)
01456 continue;
01457 queue_push(todo, k);
01458 }
01459 }
01460
01461
01462 tail = cycle[0];
01463 od->tes[tail].mark = 1;
01464
01465 for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
01466 {
01467 if (te->mark)
01468 continue;
01469 for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
01470 {
01471 if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
01472 continue;
01473 if (od->tes[k].mark != 2)
01474 continue;
01475
01476
01477 #if 0
01478 printf("adding TO TAIL cycle edge %d->%d %s->%s!\n", i, tail, solvid2str(pool, od->tes[i].p), solvid2str(pool, od->tes[tail].p));
01479 #endif
01480 j -= te->edges;
01481 addteedge(od, i, tail, TYPE_CYCLETAIL);
01482 j += te->edges;
01483 break;
01484 }
01485 }
01486
01487 #if 1
01488
01489
01490
01491 for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
01492 te->mark = 0;
01493 head = 0;
01494 for (i = 0; (j = cycle[i]) != 0; i++)
01495 {
01496 head = j;
01497 od->tes[j].mark = 2;
01498 }
01499
01500 te = od->tes + head;
01501 for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
01502 {
01503 if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
01504 continue;
01505 if (!od->tes[k].mark)
01506 reachable(od, k);
01507 if (od->tes[k].mark == -1)
01508 od->tes[k].mark = -2;
01509 }
01510 for (i = 0; cycle[i] != 0; i++)
01511 {
01512 if (cycle[i] == head)
01513 break;
01514 te = od->tes + cycle[i];
01515 for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
01516 {
01517 if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
01518 continue;
01519
01520 if (!od->tes[k].mark)
01521 reachable(od, k);
01522 if (od->tes[k].mark == -1)
01523 {
01524 #if 0
01525 printf("adding FROM HEAD cycle edge %d->%d %s->%s [%s]!\n", head, k, solvid2str(pool, od->tes[head].p), solvid2str(pool, od->tes[k].p), solvid2str(pool, od->tes[cycle[i]].p));
01526 #endif
01527 addteedge(od, head, k, TYPE_CYCLEHEAD);
01528 od->tes[k].mark = -2;
01529 }
01530 }
01531 }
01532 #endif
01533 }
01534
01535 void
01536 transaction_order(Transaction *trans, int flags)
01537 {
01538 Pool *pool = trans->pool;
01539 Queue *tr = &trans->steps;
01540 Repo *installed = pool->installed;
01541 Id p;
01542 Solvable *s;
01543 int i, j, k, numte, numedge;
01544 struct orderdata od;
01545 struct _TransactionElement *te;
01546 Queue todo, obsq, samerepoq, uninstq;
01547 int cycstart, cycel;
01548 Id *cycle;
01549 int oldcount;
01550 int start, now;
01551 Repo *lastrepo;
01552 int lastmedia;
01553 Id *temedianr;
01554
01555 start = now = sat_timems(0);
01556 POOL_DEBUG(SAT_DEBUG_STATS, "ordering transaction\n");
01557
01558 if (trans->orderdata)
01559 {
01560 struct _TransactionOrderdata *od = trans->orderdata;
01561 od->tes = sat_free(od->tes);
01562 od->invedgedata = sat_free(od->invedgedata);
01563 trans->orderdata = sat_free(trans->orderdata);
01564 }
01565
01566
01567 numte = 0;
01568 for (i = 0; i < tr->count; i++)
01569 {
01570 p = tr->elements[i];
01571 s = pool->solvables + p;
01572 if (installed && s->repo == installed && trans->transaction_installed[p - installed->start])
01573 continue;
01574 numte++;
01575 }
01576 POOL_DEBUG(SAT_DEBUG_STATS, "transaction elements: %d\n", numte);
01577 if (!numte)
01578 return;
01579
01580 numte++;
01581 memset(&od, 0, sizeof(od));
01582 od.trans = trans;
01583 od.ntes = numte;
01584 od.tes = sat_calloc(numte, sizeof(*od.tes));
01585 od.edgedata = sat_extend(0, 0, 1, sizeof(Id), EDGEDATA_BLOCK);
01586 od.edgedata[0] = 0;
01587 od.nedgedata = 1;
01588 queue_init(&od.cycles);
01589
01590
01591 for (i = 0, te = od.tes + 1; i < tr->count; i++)
01592 {
01593 p = tr->elements[i];
01594 s = pool->solvables + p;
01595 if (installed && s->repo == installed && trans->transaction_installed[p - installed->start])
01596 continue;
01597 te->p = p;
01598 te++;
01599 }
01600
01601
01602 for (i = 0; i < tr->count; i++)
01603 addsolvableedges(&od, pool->solvables + tr->elements[i]);
01604
01605
01606 numedge = 0;
01607 for (i = 1, te = od.tes + i; i < numte; i++, te++)
01608 for (j = te->edges; od.edgedata[j]; j += 2)
01609 numedge++;
01610 POOL_DEBUG(SAT_DEBUG_STATS, "edges: %d, edge space: %d\n", numedge, od.nedgedata / 2);
01611 POOL_DEBUG(SAT_DEBUG_STATS, "edge creation took %d ms\n", sat_timems(now));
01612
01613 #if 0
01614 dump_tes(&od);
01615 #endif
01616
01617 now = sat_timems(0);
01618
01619 queue_init(&todo);
01620 for (i = numte - 1; i > 0; i--)
01621 queue_push(&todo, i);
01622
01623 while (todo.count)
01624 {
01625 i = queue_pop(&todo);
01626
01627 if (i < 0)
01628 {
01629 i = -i;
01630 od.tes[i].mark = 2;
01631 continue;
01632 }
01633 te = od.tes + i;
01634 if (te->mark == 2)
01635 continue;
01636 if (te->mark == 0)
01637 {
01638 int edgestovisit = 0;
01639
01640 for (j = te->edges; (k = od.edgedata[j]) != 0; j += 2)
01641 {
01642 if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
01643 continue;
01644 if (od.tes[k].mark == 2)
01645 continue;
01646 if (!edgestovisit++)
01647 queue_push(&todo, -i);
01648 queue_push(&todo, k);
01649 }
01650 if (!edgestovisit)
01651 te->mark = 2;
01652 else
01653 te->mark = 1;
01654 continue;
01655 }
01656
01657
01658 for (j = todo.count - 1; j >= 0; j--)
01659 if (todo.elements[j] == -i)
01660 break;
01661 assert(j >= 0);
01662 cycstart = j;
01663
01664 k = cycstart;
01665 for (j = k; j < todo.count; j++)
01666 if (todo.elements[j] < 0)
01667 todo.elements[k++] = -todo.elements[j];
01668 cycel = k - cycstart;
01669 assert(cycel > 1);
01670
01671 while (todo.count < cycstart + 2 * cycel + 2)
01672 queue_push(&todo, 0);
01673 cycle = todo.elements + cycstart;
01674 cycle[cycel] = i;
01675 cycle[2 * cycel + 1] = 0;
01676 for (k = cycel; k > 0; k--)
01677 {
01678 cycle[k * 2] = cycle[k];
01679 te = od.tes + cycle[k - 1];
01680 assert(te->mark == 1);
01681 te->mark = 0;
01682
01683 for (j = te->edges; od.edgedata[j]; j += 2)
01684 if (od.edgedata[j] == cycle[k])
01685 break;
01686 assert(od.edgedata[j]);
01687 cycle[k * 2 - 1] = j;
01688 }
01689
01690
01691 breakcycle(&od, cycle);
01692
01693 todo.count = cycstart + 1;
01694 }
01695 POOL_DEBUG(SAT_DEBUG_STATS, "cycles broken: %d\n", od.ncycles);
01696 POOL_DEBUG(SAT_DEBUG_STATS, "cycle breaking took %d ms\n", sat_timems(now));
01697
01698 now = sat_timems(0);
01699
01700
01701 for (i = od.cycles.count - 3; i >= 0; i -= 3)
01702 {
01703 if (od.cycles.elements[i + 2] >= TYPE_REQ)
01704 addcycleedges(&od, od.cyclesdata.elements + od.cycles.elements[i], &todo);
01705 }
01706 for (i = od.cycles.count - 3; i >= 0; i -= 3)
01707 {
01708 if (od.cycles.elements[i + 2] < TYPE_REQ)
01709 addcycleedges(&od, od.cyclesdata.elements + od.cycles.elements[i], &todo);
01710 }
01711 POOL_DEBUG(SAT_DEBUG_STATS, "cycle edge creation took %d ms\n", sat_timems(now));
01712
01713 #if 0
01714 dump_tes(&od);
01715 #endif
01716
01717
01718 now = sat_timems(0);
01719
01720 for (i = 1, te = od.tes + i; i < numte; i++, te++)
01721 te->mark = 1;
01722 for (i = 1, te = od.tes + i; i < numte; i++, te++)
01723 {
01724 for (j = te->edges; od.edgedata[j]; j += 2)
01725 {
01726 if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
01727 continue;
01728 od.tes[od.edgedata[j]].mark++;
01729 }
01730 }
01731 j = 1;
01732 for (i = 1, te = od.tes + i; i < numte; i++, te++)
01733 {
01734 te->mark += j;
01735 j = te->mark;
01736 }
01737 POOL_DEBUG(SAT_DEBUG_STATS, "invedge space: %d\n", j + 1);
01738 od.invedgedata = sat_calloc(j + 1, sizeof(Id));
01739 for (i = 1, te = od.tes + i; i < numte; i++, te++)
01740 {
01741 for (j = te->edges; od.edgedata[j]; j += 2)
01742 {
01743 if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
01744 continue;
01745 od.invedgedata[--od.tes[od.edgedata[j]].mark] = i;
01746 }
01747 }
01748 for (i = 1, te = od.tes + i; i < numte; i++, te++)
01749 te->edges = te->mark;
01750 od.edgedata = sat_free(od.edgedata);
01751 od.nedgedata = j + 1;
01752
01753
01754 for (i = 1, te = od.tes + i; i < numte; i++, te++)
01755 te->mark = 0;
01756 for (i = 1, te = od.tes + i; i < numte; i++, te++)
01757 for (j = te->edges; od.invedgedata[j]; j++)
01758 od.tes[od.invedgedata[j]].mark++;
01759
01760 queue_init(&samerepoq);
01761 queue_init(&uninstq);
01762 queue_empty(&todo);
01763 for (i = 1, te = od.tes + i; i < numte; i++, te++)
01764 if (te->mark == 0)
01765 {
01766 if (installed && pool->solvables[te->p].repo == installed)
01767 queue_push(&uninstq, i);
01768 else
01769 queue_push(&todo, i);
01770 }
01771 assert(todo.count > 0 || uninstq.count > 0);
01772 oldcount = tr->count;
01773 queue_empty(tr);
01774
01775 queue_init(&obsq);
01776
01777 lastrepo = 0;
01778 lastmedia = 0;
01779 temedianr = sat_calloc(numte, sizeof(Id));
01780 for (i = 1; i < numte; i++)
01781 {
01782 Solvable *s = pool->solvables + od.tes[i].p;
01783 if (installed && s->repo == installed)
01784 j = 1;
01785 else
01786 j = solvable_lookup_num(s, SOLVABLE_MEDIANR, 1);
01787 temedianr[i] = j;
01788 }
01789 for (;;)
01790 {
01791
01792 if (uninstq.count)
01793 i = queue_shift(&uninstq);
01794 else if (samerepoq.count)
01795 i = queue_shift(&samerepoq);
01796 else if (todo.count)
01797 {
01798
01799 for (j = 0; j < todo.count; j++)
01800 {
01801 if (!j || temedianr[todo.elements[j]] < lastmedia)
01802 {
01803 i = j;
01804 lastmedia = temedianr[todo.elements[j]];
01805 }
01806 }
01807 lastrepo = pool->solvables[od.tes[todo.elements[i]].p].repo;
01808
01809
01810 for (i = j = 0; j < todo.count; j++)
01811 {
01812 int k = todo.elements[j];
01813 if (temedianr[k] == lastmedia && pool->solvables[od.tes[k].p].repo == lastrepo)
01814 queue_push(&samerepoq, k);
01815 else
01816 todo.elements[i++] = k;
01817 }
01818 todo.count = i;
01819
01820 assert(samerepoq.count);
01821 i = queue_shift(&samerepoq);
01822 }
01823 else
01824 break;
01825
01826 te = od.tes + i;
01827 queue_push(tr, te->p);
01828 #if 0
01829 printf("do %s [%d]\n", solvid2str(pool, te->p), temedianr[i]);
01830 #endif
01831 s = pool->solvables + te->p;
01832 for (j = te->edges; od.invedgedata[j]; j++)
01833 {
01834 struct _TransactionElement *te2 = od.tes + od.invedgedata[j];
01835 assert(te2->mark > 0);
01836 if (--te2->mark == 0)
01837 {
01838 Solvable *s = pool->solvables + te2->p;
01839 #if 0
01840 printf("free %s [%d]\n", solvid2str(pool, te2->p), temedianr[od.invedgedata[j]]);
01841 #endif
01842 if (installed && s->repo == installed)
01843 queue_push(&uninstq, od.invedgedata[j]);
01844 else if (s->repo == lastrepo && temedianr[od.invedgedata[j]] == lastmedia)
01845 queue_push(&samerepoq, od.invedgedata[j]);
01846 else
01847 queue_push(&todo, od.invedgedata[j]);
01848 }
01849 }
01850 }
01851 sat_free(temedianr);
01852 queue_free(&todo);
01853 queue_free(&samerepoq);
01854 queue_free(&uninstq);
01855 queue_free(&obsq);
01856 for (i = 1, te = od.tes + i; i < numte; i++, te++)
01857 assert(te->mark == 0);
01858
01859
01860 transaction_add_obsoleted(trans);
01861 assert(tr->count == oldcount);
01862
01863 POOL_DEBUG(SAT_DEBUG_STATS, "creating new transaction took %d ms\n", sat_timems(now));
01864 POOL_DEBUG(SAT_DEBUG_STATS, "transaction ordering took %d ms\n", sat_timems(start));
01865
01866 if ((flags & SOLVER_TRANSACTION_KEEP_ORDERDATA) != 0)
01867 {
01868 trans->orderdata = sat_calloc(1, sizeof(*trans->orderdata));
01869 trans->orderdata->tes = od.tes;
01870 trans->orderdata->ntes = numte;
01871 trans->orderdata->invedgedata = od.invedgedata;
01872 trans->orderdata->ninvedgedata = od.nedgedata;
01873 }
01874 else
01875 {
01876 sat_free(od.tes);
01877 sat_free(od.invedgedata);
01878 }
01879 }
01880
01881
01882 int
01883 transaction_order_add_choices(Transaction *trans, Id chosen, Queue *choices)
01884 {
01885 int i, j;
01886 struct _TransactionOrderdata *od = trans->orderdata;
01887 struct _TransactionElement *te;
01888
01889 if (!od)
01890 return choices->count;
01891 if (!chosen)
01892 {
01893
01894 for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
01895 te->mark = 0;
01896 for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
01897 {
01898 for (j = te->edges; od->invedgedata[j]; j++)
01899 od->tes[od->invedgedata[j]].mark++;
01900 }
01901 for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
01902 if (!te->mark)
01903 queue_push(choices, te->p);
01904 return choices->count;
01905 }
01906 for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
01907 if (te->p == chosen)
01908 break;
01909 if (i == od->ntes)
01910 return choices->count;
01911 if (te->mark > 0)
01912 {
01913
01914 te->mark = -1;
01915 }
01916 for (j = te->edges; od->invedgedata[j]; j++)
01917 {
01918 te = od->tes + od->invedgedata[j];
01919 assert(te->mark > 0 || te->mark == -1);
01920 if (te->mark > 0 && --te->mark == 0)
01921 queue_push(choices, te->p);
01922 }
01923 return choices->count;
01924 }
01925
01926 void
01927 transaction_add_obsoleted(Transaction *trans)
01928 {
01929 Pool *pool = trans->pool;
01930 Repo *installed = pool->installed;
01931 Id p;
01932 Solvable *s;
01933 int i, j, k, max, oldcount;
01934 Map done;
01935 Queue obsq, *steps;
01936
01937 if (!installed || !trans->steps.count)
01938 return;
01939
01940 max = 0;
01941 FOR_REPO_SOLVABLES(installed, p, s)
01942 if (MAPTST(&trans->transactsmap, p))
01943 max++;
01944 if (!max)
01945 return;
01946
01947 steps = &trans->steps;
01948 oldcount = steps->count;
01949 queue_insertn(steps, 0, max);
01950
01951
01952 map_init(&done, installed->end - installed->start);
01953 queue_init(&obsq);
01954 for (j = 0, i = max; i < steps->count; i++)
01955 {
01956 p = trans->steps.elements[i];
01957 if (pool->solvables[p].repo == installed)
01958 {
01959 if (!trans->transaction_installed[p - pool->installed->start])
01960 trans->steps.elements[j++] = p;
01961 continue;
01962 }
01963 trans->steps.elements[j++] = p;
01964 queue_empty(&obsq);
01965 transaction_all_obs_pkgs(trans, p, &obsq);
01966 for (k = 0; k < obsq.count; k++)
01967 {
01968 p = obsq.elements[k];
01969 assert(p >= installed->start && p < installed->end);
01970 if (MAPTST(&done, p - installed->start))
01971 continue;
01972 MAPSET(&done, p - installed->start);
01973 trans->steps.elements[j++] = p;
01974 }
01975 }
01976
01977
01978 queue_truncate(steps, j);
01979 map_free(&done);
01980 queue_free(&obsq);
01981 }
01982
01983 static void
01984 transaction_check_pkg(Transaction *trans, Id tepkg, Id pkg, Map *ins, Map *seen, int onlyprereq, Id noconfpkg, int depth)
01985 {
01986 Pool *pool = trans->pool;
01987 Id p, pp;
01988 Solvable *s;
01989 int good;
01990
01991 if (MAPTST(seen, pkg))
01992 return;
01993 MAPSET(seen, pkg);
01994 s = pool->solvables + pkg;
01995 #if 0
01996 printf("- %*s%c%s\n", depth * 2, "", s->repo == pool->installed ? '-' : '+', solvable2str(pool, s));
01997 #endif
01998 if (s->requires)
01999 {
02000 Id req, *reqp;
02001 int inpre = 0;
02002 reqp = s->repo->idarraydata + s->requires;
02003 while ((req = *reqp++) != 0)
02004 {
02005 if (req == SOLVABLE_PREREQMARKER)
02006 {
02007 inpre = 1;
02008 continue;
02009 }
02010 if (onlyprereq && !inpre)
02011 continue;
02012 if (!strncmp(id2str(pool, req), "rpmlib(", 7))
02013 continue;
02014 good = 0;
02015
02016 FOR_PROVIDES(p, pp, req)
02017 {
02018 if (!MAPTST(ins, p))
02019 continue;
02020 if (MAPTST(&trans->transactsmap, p))
02021 continue;
02022 good++;
02023 transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
02024 }
02025 if (!good)
02026 {
02027 FOR_PROVIDES(p, pp, req)
02028 {
02029 if (!MAPTST(ins, p))
02030 continue;
02031 if (pool->solvables[p].repo == pool->installed)
02032 continue;
02033 good++;
02034 transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
02035 }
02036 }
02037 if (!good)
02038 {
02039 FOR_PROVIDES(p, pp, req)
02040 {
02041 if (!MAPTST(ins, p))
02042 continue;
02043 good++;
02044 transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
02045 }
02046 }
02047 if (!good)
02048 {
02049 POOL_DEBUG(SAT_DEBUG_RESULT, " %c%s: nothing provides %s needed by %c%s\n", pool->solvables[tepkg].repo == pool->installed ? '-' : '+', solvid2str(pool, tepkg), dep2str(pool, req), s->repo == pool->installed ? '-' : '+', solvable2str(pool, s));
02050 }
02051 }
02052 }
02053 }
02054
02055 void
02056 transaction_check_order(Transaction *trans)
02057 {
02058 Pool *pool = trans->pool;
02059 Solvable *s;
02060 Id p, lastins;
02061 Map ins, seen;
02062 int i;
02063
02064 POOL_DEBUG(SAT_WARN, "\nchecking transaction order...\n");
02065 map_init(&ins, pool->nsolvables);
02066 map_init(&seen, pool->nsolvables);
02067 if (pool->installed)
02068 FOR_REPO_SOLVABLES(pool->installed, p, s)
02069 MAPSET(&ins, p);
02070 lastins = 0;
02071 for (i = 0; i < trans->steps.count; i++)
02072 {
02073 p = trans->steps.elements[i];
02074 s = pool->solvables + p;
02075 if (s->repo != pool->installed)
02076 lastins = p;
02077 if (s->repo != pool->installed)
02078 MAPSET(&ins, p);
02079 if (havescripts(pool, p))
02080 {
02081 MAPZERO(&seen);
02082 transaction_check_pkg(trans, p, p, &ins, &seen, 1, lastins, 0);
02083 }
02084 if (s->repo == pool->installed)
02085 MAPCLR(&ins, p);
02086 }
02087 map_free(&seen);
02088 map_free(&ins);
02089 POOL_DEBUG(SAT_WARN, "transaction order check done.\n");
02090 }