- map_free(&trans->noobsmap);
- transaction_free_orderdata(trans);
- free(trans);
-}
-
-void
-transaction_free_orderdata(Transaction *trans)
-{
- if (trans->orderdata)
- {
- struct _TransactionOrderdata *od = trans->orderdata;
- od->tes = sat_free(od->tes);
- od->invedgedata = sat_free(od->invedgedata);
- trans->orderdata = sat_free(trans->orderdata);
- }
-}
-
-struct orderdata {
- Transaction *trans;
- struct _TransactionElement *tes;
- int ntes;
- Id *edgedata;
- int nedgedata;
- Id *invedgedata;
-
- Queue cycles;
- Queue cyclesdata;
- int ncycles;
-};
-
-static int
-addteedge(struct orderdata *od, int from, int to, int type)
-{
- int i;
- struct _TransactionElement *te;
-
- if (from == to)
- return 0;
-
- /* 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); */
-
- te = od->tes + from;
- for (i = te->edges; od->edgedata[i]; i += 2)
- if (od->edgedata[i] == to)
- break;
- /* test of brokenness */
- if (type == TYPE_BROKEN)
- return od->edgedata[i] && (od->edgedata[i + 1] & TYPE_BROKEN) != 0 ? 1 : 0;
- if (od->edgedata[i])
- {
- od->edgedata[i + 1] |= type;
- return 0;
- }
- if (i + 1 == od->nedgedata)
- {
- /* printf("tail add %d\n", i - te->edges); */
- if (!i)
- te->edges = ++i;
- od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3, sizeof(Id), EDGEDATA_BLOCK);
- }
- else
- {
- /* printf("extend %d\n", i - te->edges); */
- od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3 + (i - te->edges), sizeof(Id), EDGEDATA_BLOCK);
- if (i > te->edges)
- memcpy(od->edgedata + od->nedgedata, od->edgedata + te->edges, sizeof(Id) * (i - te->edges));
- i = od->nedgedata + (i - te->edges);
- te->edges = od->nedgedata;
- }
- od->edgedata[i] = to;
- od->edgedata[i + 1] = type;
- od->edgedata[i + 2] = 0; /* end marker */
- od->nedgedata = i + 3;
- return 0;
-}
-
-static int
-addedge(struct orderdata *od, Id from, Id to, int type)
-{
- Transaction *trans = od->trans;
- Pool *pool = trans->pool;
- Solvable *s;
- struct _TransactionElement *te;
- int i;
-
- // printf("addedge %d %d type %d\n", from, to, type);
- s = pool->solvables + from;
- if (s->repo == pool->installed && trans->transaction_installed[from - pool->installed->start])
- {
- /* obsolete, map to install */
- if (trans->transaction_installed[from - pool->installed->start] > 0)
- from = trans->transaction_installed[from - pool->installed->start];
- else
- {
- int ret = 0;
- Queue ti;
- Id tibuf[5];
-
- queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
- transaction_all_obs_pkgs(trans, from, &ti);
- for (i = 0; i < ti.count; i++)
- ret |= addedge(od, ti.elements[i], to, type);
- queue_free(&ti);
- return ret;
- }
- }
- s = pool->solvables + to;
- if (s->repo == pool->installed && trans->transaction_installed[to - pool->installed->start])
- {
- /* obsolete, map to install */
- if (trans->transaction_installed[to - pool->installed->start] > 0)
- to = trans->transaction_installed[to - pool->installed->start];
- else
- {
- int ret = 0;
- Queue ti;
- Id tibuf[5];
-
- queue_init_buffer(&ti, tibuf, sizeof(tibuf)/sizeof(*tibuf));
- transaction_all_obs_pkgs(trans, to, &ti);
- for (i = 0; i < ti.count; i++)
- ret |= addedge(od, from, ti.elements[i], type);
- queue_free(&ti);
- return ret;
- }
- }
-
- /* map from/to to te numbers */
- for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
- if (te->p == to)
- break;
- if (i == od->ntes)
- return 0;
- to = i;
-
- for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
- if (te->p == from)
- break;
- if (i == od->ntes)
- return 0;
-
- return addteedge(od, i, to, type);
-}
-
-#if 1
-static int
-havechoice(struct orderdata *od, Id p, Id q1, Id q2)
-{
- Transaction *trans = od->trans;
- Pool *pool = trans->pool;
- Id ti1buf[5], ti2buf[5];
- Queue ti1, ti2;
- int i, j;
-
- /* both q1 and q2 are uninstalls. check if their TEs intersect */
- /* common case: just one TE for both packages */
-#if 0
- printf("havechoice %d %d %d\n", p, q1, q2);
-#endif
- if (trans->transaction_installed[q1 - pool->installed->start] == 0)
- return 1;
- if (trans->transaction_installed[q2 - pool->installed->start] == 0)
- return 1;
- if (trans->transaction_installed[q1 - pool->installed->start] == trans->transaction_installed[q2 - pool->installed->start])
- return 0;
- if (trans->transaction_installed[q1 - pool->installed->start] > 0 && trans->transaction_installed[q2 - pool->installed->start] > 0)
- return 1;
- queue_init_buffer(&ti1, ti1buf, sizeof(ti1buf)/sizeof(*ti1buf));
- transaction_all_obs_pkgs(trans, q1, &ti1);
- queue_init_buffer(&ti2, ti2buf, sizeof(ti2buf)/sizeof(*ti2buf));
- transaction_all_obs_pkgs(trans, q2, &ti2);
- for (i = 0; i < ti1.count; i++)
- for (j = 0; j < ti2.count; j++)
- if (ti1.elements[i] == ti2.elements[j])
- {
- /* found a common edge */
- queue_free(&ti1);
- queue_free(&ti2);
- return 0;
- }
- queue_free(&ti1);
- queue_free(&ti2);
- return 1;
-}
-#endif
-
-static inline int
-havescripts(Pool *pool, Id solvid)
-{
- Solvable *s = pool->solvables + solvid;
- const char *dep;
- if (s->requires)
- {
- Id req, *reqp;
- int inpre = 0;
- reqp = s->repo->idarraydata + s->requires;
- while ((req = *reqp++) != 0)
- {
- if (req == SOLVABLE_PREREQMARKER)
- {
- inpre = 1;
- continue;
- }
- if (!inpre)
- continue;
- dep = pool_id2str(pool, req);
- if (*dep == '/' && strcmp(dep, "/sbin/ldconfig") != 0)
- return 1;
- }
- }
- return 0;
-}
-
-static void
-addsolvableedges(struct orderdata *od, Solvable *s)
-{
- Transaction *trans = od->trans;
- Pool *pool = trans->pool;
- Id req, *reqp, con, *conp;
- Id p, p2, pp2;
- int i, j, pre, numins;
- Repo *installed = pool->installed;
- Solvable *s2;
- Queue reqq;
- int provbyinst;
-
-#if 0
- printf("addsolvableedges %s\n", pool_solvable2str(pool, s));
-#endif
- p = s - pool->solvables;
- queue_init(&reqq);
- if (s->requires)
- {
- reqp = s->repo->idarraydata + s->requires;
- pre = TYPE_REQ;
- while ((req = *reqp++) != 0)
- {
- if (req == SOLVABLE_PREREQMARKER)
- {
- pre = TYPE_PREREQ;
- continue;
- }
-#if 0
- if (pre != TYPE_PREREQ && installed && s->repo == installed)
- {
- /* ignore normal requires if we're getting obsoleted */
- if (trans->transaction_installed[p - pool->installed->start])
- continue;
- }
-#endif
- queue_empty(&reqq);
- numins = 0; /* number of packages to be installed providing it */
- provbyinst = 0; /* provided by kept package */
- FOR_PROVIDES(p2, pp2, req)
- {
- s2 = pool->solvables + p2;
- if (p2 == p)
- {
- reqq.count = 0; /* self provides */
- break;
- }
- if (s2->repo == installed && !MAPTST(&trans->transactsmap, p2))
- {
- provbyinst = 1;
-#if 0
- printf("IGNORE inst provides %s by %s\n", pool_dep2str(pool, req), pool_solvable2str(pool, s2));
- reqq.count = 0; /* provided by package that stays installed */
- break;
-#else
- continue;
-#endif
- }
- if (s2->repo != installed && !MAPTST(&trans->transactsmap, p2))
- continue; /* package stays uninstalled */
-
- if (s->repo == installed)
- {
- /* s gets uninstalled */
- queue_pushunique(&reqq, p2);
- if (s2->repo != installed)
- numins++;
- }
- else
- {
- if (s2->repo == installed)
- continue; /* s2 gets uninstalled */
- queue_pushunique(&reqq, p2);
- }
- }
- if (provbyinst)
- {
- /* prune to harmless ->inst edges */
- for (i = j = 0; i < reqq.count; i++)
- if (pool->solvables[reqq.elements[i]].repo != installed)
- reqq.elements[j++] = reqq.elements[i];
- reqq.count = j;
- }
-
- if (numins && reqq.count)
- {
- if (s->repo == installed)
- {
- for (i = 0; i < reqq.count; i++)
- {
- if (pool->solvables[reqq.elements[i]].repo == installed)
- {
- for (j = 0; j < reqq.count; j++)
- {
- if (pool->solvables[reqq.elements[j]].repo != installed)
- {
- if (trans->transaction_installed[reqq.elements[i] - pool->installed->start] == reqq.elements[j])
- continue; /* no self edge */
-#if 0
- 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]));
-#endif
- addedge(od, reqq.elements[i], reqq.elements[j], pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
- }
- }
- }
- }
- }
- /* no mixed types, remove all deps on uninstalls */
- for (i = j = 0; i < reqq.count; i++)
- if (pool->solvables[reqq.elements[i]].repo != installed)
- reqq.elements[j++] = reqq.elements[i];
- reqq.count = j;
- }
- if (!reqq.count)
- continue;
- for (i = 0; i < reqq.count; i++)
- {
- int choice = 0;
- p2 = reqq.elements[i];
- if (pool->solvables[p2].repo != installed)
- {
- /* all elements of reqq are installs, thus have different TEs */
- choice = reqq.count - 1;
- if (pool->solvables[p].repo != installed)
- {
-#if 0
- printf("add inst->inst edge choice %d (%s -> %s -> %s)\n", choice, pool_solvid2str(pool, p), pool_dep2str(pool, req), pool_solvid2str(pool, p2));
-#endif
- addedge(od, p, p2, pre);
- }
- else
- {
-#if 0
- printf("add uninst->inst edge choice %d (%s -> %s -> %s)\n", choice, pool_solvid2str(pool, p), pool_dep2str(pool, req), pool_solvid2str(pool, p2));
-#endif
- addedge(od, p, p2, pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
- }
- }
- else
- {
- if (s->repo != installed)
- continue; /* no inst->uninst edges, please! */
-
- /* uninst -> uninst edge. Those make trouble. Only add if we must */
- if (trans->transaction_installed[p - installed->start] && !havescripts(pool, p))
- {
- /* p is obsoleted by another package and has no scripts */
- /* we assume that the obsoletor is good enough to replace p */
- continue;
- }
-#if 1
- choice = 0;
- for (j = 0; j < reqq.count; j++)
- {
- if (i == j)
- continue;
- if (havechoice(od, p, reqq.elements[i], reqq.elements[j]))
- choice++;
- }
-#endif
-#if 0
- printf("add uninst->uninst edge choice %d (%s -> %s -> %s)\n", choice, pool_solvid2str(pool, p), pool_dep2str(pool, req), pool_solvid2str(pool, p2));
-#endif
- addedge(od, p2, p, pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
- }
- }
- }
- }
- if (s->conflicts)
- {
- conp = s->repo->idarraydata + s->conflicts;
- while ((con = *conp++) != 0)
- {
- FOR_PROVIDES(p2, pp2, con)
- {
- if (p2 == p)
- continue;
- s2 = pool->solvables + p2;
- if (!s2->repo)
- continue;
- if (s->repo == installed)
- {
- if (s2->repo != installed && MAPTST(&trans->transactsmap, p2))
- {
- /* deinstall p before installing p2 */
-#if 0
- printf("add conflict uninst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p2), pool_dep2str(pool, con), pool_solvid2str(pool, p));
-#endif
- addedge(od, p2, p, TYPE_CON);
- }
- }
- else
- {
- if (s2->repo == installed && MAPTST(&trans->transactsmap, p2))
- {
- /* deinstall p2 before installing p */
-#if 0
- printf("add conflict uninst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p), pool_dep2str(pool, con), pool_solvid2str(pool, p2));
-#endif
- addedge(od, p, p2, TYPE_CON);
- }
- }
-
- }
- }
- }
- if (s->repo == installed && solvable_lookup_idarray(s, SOLVABLE_TRIGGERS, &reqq) && reqq.count)
- {
- /* we're getting deinstalled/updated. Try to do this before our
- * triggers are hit */
- for (i = 0; i < reqq.count; i++)
- {
- Id tri = reqq.elements[i];
- FOR_PROVIDES(p2, pp2, tri)
- {
- if (p2 == p)
- continue;
- s2 = pool->solvables + p2;
- if (!s2->repo)
- continue;
- if (s2->name == s->name)
- continue; /* obsoleted anyway */
- if (s2->repo != installed && MAPTST(&trans->transactsmap, p2))
- {
- /* deinstall/update p before installing p2 */
-#if 0
- printf("add trigger uninst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p2), pool_dep2str(pool, tri), pool_solvid2str(pool, p));
-#endif
- addedge(od, p2, p, TYPE_CON);
- }
- }
- }
- }
- queue_free(&reqq);
-}
-
-
-/* break an edge in a cycle */
-static void
-breakcycle(struct orderdata *od, Id *cycle)
-{
- Pool *pool = od->trans->pool;
- Id ddegmin, ddegmax, ddeg;
- int k, l;
- struct _TransactionElement *te;
-
- l = 0;
- ddegmin = ddegmax = 0;
- for (k = 0; cycle[k + 1]; k += 2)
- {
- ddeg = od->edgedata[cycle[k + 1] + 1];
- if (ddeg > ddegmax)
- ddegmax = ddeg;
- if (!k || ddeg < ddegmin)
- {
- l = k;
- ddegmin = ddeg;
- continue;
- }
- if (ddeg == ddegmin)
- {
- if (havescripts(pool, od->tes[cycle[l]].p) && !havescripts(pool, od->tes[cycle[k]].p))
- {
- /* prefer k, as l comes from a package with contains scriptlets */
- l = k;
- ddegmin = ddeg;
- continue;
- }
- /* same edge value, check for prereq */
- }
- }
-
- /* record brkoen cycle starting with the tail */
- queue_push(&od->cycles, od->cyclesdata.count); /* offset into data */
- queue_push(&od->cycles, k / 2); /* cycle elements */
- queue_push(&od->cycles, od->edgedata[cycle[l + 1] + 1]); /* broken edge */
- od->ncycles++;
- for (k = l;;)
- {
- k += 2;
- if (!cycle[k + 1])
- k = 0;
- queue_push(&od->cyclesdata, cycle[k]);
- if (k == l)
- break;
- }
- queue_push(&od->cyclesdata, 0); /* mark end */
-
- /* break that edge */
- od->edgedata[cycle[l + 1] + 1] |= TYPE_BROKEN;
-
-#if 1
- if (ddegmin < TYPE_REQ)
- return;
-#endif
-
- /* cycle recorded, print it */
- if (ddegmin >= TYPE_REQ && (ddegmax & TYPE_PREREQ) != 0)
- POOL_DEBUG(SAT_DEBUG_STATS, "CRITICAL ");
- POOL_DEBUG(SAT_DEBUG_STATS, "cycle: --> ");
- for (k = 0; cycle[k + 1]; k += 2)
- {
- te = od->tes + cycle[k];
- if ((od->edgedata[cycle[k + 1] + 1] & TYPE_BROKEN) != 0)
- POOL_DEBUG(SAT_DEBUG_STATS, "%s ##%x##> ", pool_solvid2str(pool, te->p), od->edgedata[cycle[k + 1] + 1]);
- else
- POOL_DEBUG(SAT_DEBUG_STATS, "%s --%x--> ", pool_solvid2str(pool, te->p), od->edgedata[cycle[k + 1] + 1]);
- }
- POOL_DEBUG(SAT_DEBUG_STATS, "\n");
-}
-
-static inline void
-dump_tes(struct orderdata *od)
-{
- Pool *pool = od->trans->pool;
- int i, j;
- Queue obsq;
- struct _TransactionElement *te, *te2;
-
- queue_init(&obsq);
- for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
- {
- Solvable *s = pool->solvables + te->p;
- POOL_DEBUG(SAT_DEBUG_RESULT, "TE %4d: %c%s\n", i, s->repo == pool->installed ? '-' : '+', pool_solvable2str(pool, s));
- if (s->repo != pool->installed)
- {
- queue_empty(&obsq);
- transaction_all_obs_pkgs(od->trans, te->p, &obsq);
- for (j = 0; j < obsq.count; j++)
- POOL_DEBUG(SAT_DEBUG_RESULT, " -%s\n", pool_solvid2str(pool, obsq.elements[j]));
- }
- for (j = te->edges; od->edgedata[j]; j += 2)
- {
- te2 = od->tes + od->edgedata[j];
- if ((od->edgedata[j + 1] & TYPE_BROKEN) == 0)
- POOL_DEBUG(SAT_DEBUG_RESULT, " --%x--> TE %4d: %s\n", od->edgedata[j + 1], od->edgedata[j], pool_solvid2str(pool, te2->p));
- else
- POOL_DEBUG(SAT_DEBUG_RESULT, " ##%x##> TE %4d: %s\n", od->edgedata[j + 1], od->edgedata[j], pool_solvid2str(pool, te2->p));
- }
- }
-}
-
-#if 1
-static void
-reachable(struct orderdata *od, Id i)
-{
- struct _TransactionElement *te = od->tes + i;
- int j, k;
-
- if (te->mark != 0)
- return;
- te->mark = 1;
- for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
- {
- if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
- continue;
- if (!od->tes[k].mark)
- reachable(od, k);
- if (od->tes[k].mark == 2)
- {
- te->mark = 2;
- return;
- }
- }
- te->mark = -1;
-}
-#endif
-
-static void
-addcycleedges(struct orderdata *od, Id *cycle, Queue *todo)
-{
-#if 0
- Transaction *trans = od->trans;
- Pool *pool = trans->pool;
-#endif
- struct _TransactionElement *te;
- int i, j, k, tail;
-#if 1
- int head;
-#endif
-
-#if 0
- printf("addcycleedges\n");
- for (i = 0; (j = cycle[i]) != 0; i++)
- printf("cycle %s\n", pool_solvid2str(pool, od->tes[j].p));
-#endif
-
- /* first add all the tail cycle edges */
-
- /* see what we can reach from the cycle */
- queue_empty(todo);
- for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
- te->mark = 0;
- for (i = 0; (j = cycle[i]) != 0; i++)
- {
- od->tes[j].mark = -1;
- queue_push(todo, j);
- }
- while (todo->count)
- {
- i = queue_pop(todo);
- te = od->tes + i;
- if (te->mark > 0)
- continue;
- te->mark = te->mark < 0 ? 2 : 1;
- for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
- {
- if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
- continue;
- if (od->tes[k].mark > 0)
- continue; /* no need to visit again */
- queue_push(todo, k);
- }
- }
- /* now all cycle TEs are marked with 2, all TEs reachable
- * from the cycle are marked with 1 */
- tail = cycle[0];
- od->tes[tail].mark = 1; /* no need to add edges */
-
- for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
- {
- if (te->mark)
- continue; /* reachable from cycle */
- for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
- {
- if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
- continue;
- if (od->tes[k].mark != 2)
- continue;
- /* We found an edge to the cycle. Add an extra edge to the tail */
- /* the TE was not reachable, so we're not creating a new cycle! */
-#if 0
- 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));
-#endif
- j -= te->edges; /* in case we move */
- addteedge(od, i, tail, TYPE_CYCLETAIL);
- j += te->edges;
- break; /* one edge is enough */
- }
- }
-
-#if 1
- /* now add all head cycle edges */
-
- /* reset marks */
- for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
- te->mark = 0;
- head = 0;
- for (i = 0; (j = cycle[i]) != 0; i++)
- {
- head = j;
- od->tes[j].mark = 2;
- }
- /* first the head to save some time */
- te = od->tes + head;
- for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
- {
- if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
- continue;
- if (!od->tes[k].mark)
- reachable(od, k);
- if (od->tes[k].mark == -1)
- od->tes[k].mark = -2; /* no need for another edge */
- }
- for (i = 0; cycle[i] != 0; i++)
- {
- if (cycle[i] == head)
- break;
- te = od->tes + cycle[i];
- for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
- {
- if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
- continue;
- /* see if we can reach a cycle TE from k */
- if (!od->tes[k].mark)
- reachable(od, k);
- if (od->tes[k].mark == -1)
- {
-#if 0
- 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));
-#endif
- addteedge(od, head, k, TYPE_CYCLEHEAD);
- od->tes[k].mark = -2; /* no need to add that one again */
- }
- }
- }
-#endif
-}
-
-void
-transaction_order(Transaction *trans, int flags)
-{
- Pool *pool = trans->pool;
- Queue *tr = &trans->steps;
- Repo *installed = pool->installed;
- Id p;
- Solvable *s;
- int i, j, k, numte, numedge;
- struct orderdata od;
- struct _TransactionElement *te;
- Queue todo, obsq, samerepoq, uninstq;
- int cycstart, cycel;
- Id *cycle;
- int oldcount;
- int start, now;
- Repo *lastrepo;
- int lastmedia;
- Id *temedianr;
-
- start = now = sat_timems(0);
- POOL_DEBUG(SAT_DEBUG_STATS, "ordering transaction\n");
- /* free old data if present */