/** \ingroup rpmts
* \file lib/depends.c
*/
#include "system.h"
#include <rpm/rpmtag.h>
#include <rpm/rpmmacro.h>
#include <rpm/rpmlog.h>
#include <rpm/rpmds.h>
#include "lib/rpmte_internal.h" /* XXX tsortInfo_s */
#include "lib/rpmts_internal.h"
#include "debug.h"
/*
* Strongly Connected Components
* set of packages (indirectly) requiering each other
*/
struct scc_s {
int count; /* # of external requires this SCC has */
/* int qcnt; # of external requires pointing to this SCC */
int size; /* # of members */
tsortInfo * members;
};
typedef struct scc_s * scc;
struct relation_s {
tsortInfo rel_suc; // pkg requiring this package
rpmsenseFlags rel_flags; // accumulated flags of the requirements
struct relation_s * rel_next;
};
typedef struct relation_s * relation;
struct tsortInfo_s {
rpmte te;
int tsi_count; // #pkgs this pkg requires
int tsi_qcnt; // #pkgs requiring this package
int tsi_reqx; // requires Idx/mark as (queued/loop)
struct relation_s * tsi_relations;
struct relation_s * tsi_forward_relations;
tsortInfo tsi_suc; // used for queuing (addQ)
int tsi_SccIdx; // # of the SCC the node belongs to
// (1 for trivial SCCs)
int tsi_SccLowlink; // used for SCC detection
};
static void rpmTSIFree(tsortInfo tsi)
{
relation rel;
while (tsi->tsi_relations != NULL) {
rel = tsi->tsi_relations;
tsi->tsi_relations = tsi->tsi_relations->rel_next;
free(rel);
}
while (tsi->tsi_forward_relations != NULL) {
rel = tsi->tsi_forward_relations;
tsi->tsi_forward_relations = \
tsi->tsi_forward_relations->rel_next;
free(rel);
}
}
static inline int addSingleRelation(rpmte p,
rpmte q,
rpmsenseFlags dsflags,
int reversed)
{
struct tsortInfo_s *tsi_p, *tsi_q;
relation rel;
rpmElementType teType = rpmteType(p);
rpmsenseFlags flags;
/* Avoid deps outside this transaction and self dependencies */
if (q == NULL || q == p)
return 0;
/* Erasures are reversed installs. */
if (teType == TR_REMOVED) {
reversed = ! reversed;
flags = isErasePreReq(dsflags);
} else {
flags = isInstallPreReq(dsflags);
}
/* map legacy prereq to pre/preun as needed */
if (isLegacyPreReq(dsflags)) {
flags |= (teType == TR_ADDED) ?
RPMSENSE_SCRIPT_PRE : RPMSENSE_SCRIPT_PREUN;
}
if (reversed) {
rpmte r = p;
p = q;
q = r;
}
tsi_p = rpmteTSI(p);
tsi_q = rpmteTSI(q);
/* if relation got already added just update the flags */
if (!reversed &&
tsi_q->tsi_relations && tsi_q->tsi_relations->rel_suc == tsi_p) {
/* must be latest one added to q as we add all rels to p at once */
tsi_q->tsi_relations->rel_flags |= flags;
/* search entry in p */
for (struct relation_s * tsi = tsi_p->tsi_forward_relations;
tsi; tsi = tsi->rel_next) {
if (tsi->rel_suc == tsi_q) {
tsi->rel_flags |= flags;
return 0;
}
}
assert(0);
}
/* if relation got already added just update the flags */
if (reversed && tsi_q->tsi_forward_relations &&
tsi_q->tsi_forward_relations->rel_suc == tsi_p) {
/* must be latest one added to q as we add all rels to p at once */
tsi_q->tsi_forward_relations->rel_flags |= flags;
/* search entry in p */
for (struct relation_s * tsi = tsi_p->tsi_relations;
tsi; tsi = tsi->rel_next) {
if (tsi->rel_suc == tsi_q) {
tsi->rel_flags |= flags;
return 0;
}
}
assert(0);
}
/* Record next "q <- p" relation (i.e. "p" requires "q"). */
/* bump p predecessor count */
tsi_p->tsi_count++;
rel = xcalloc(1, sizeof(*rel));
rel->rel_suc = tsi_p;
rel->rel_flags = flags;
rel->rel_next = tsi_q->tsi_relations;
tsi_q->tsi_relations = rel;
/* bump q successor count */
tsi_q->tsi_qcnt++;
rel = xcalloc(1, sizeof(*rel));
rel->rel_suc = tsi_q;
rel->rel_flags = flags;
rel->rel_next = tsi_p->tsi_forward_relations;
tsi_p->tsi_forward_relations = rel;
return 0;
}
/**
* Record next "q <- p" relation (i.e. "p" requires "q").
* @param ts transaction set
* @param al packages list
* @param p predecessor (i.e. package that "Requires: q")
* @param requires relation
* @return 0 always
*/
static inline int addRelation(rpmts ts,
rpmal al,
rpmte p,
rpmds requires,
int reversed)
{
rpmte q;
rpmsenseFlags dsflags;
dsflags = rpmdsFlags(requires);
/* Avoid dependendencies which are not relevant for ordering */
if (dsflags & (RPMSENSE_RPMLIB|RPMSENSE_CONFIG|RPMSENSE_PRETRANS|RPMSENSE_POSTTRANS))
return 0;
if (rpmdsIsRich(requires)) {
rpmds ds1, ds2;
rpmrichOp op;
if (rpmdsParseRichDep(requires, &ds1, &ds2, &op, NULL) == RPMRC_OK) {
if (op != RPMRICHOP_ELSE)
addRelation(ts, al, p, ds1, reversed);
if (op == RPMRICHOP_IF || op == RPMRICHOP_UNLESS) {
rpmds ds21, ds22;
rpmrichOp op2;
if (rpmdsParseRichDep(requires, &ds21, &ds22, &op2, NULL) == RPMRC_OK && op2 == RPMRICHOP_ELSE) {
addRelation(ts, al, p, ds22, reversed);
}
ds21 = rpmdsFree(ds21);
ds22 = rpmdsFree(ds22);
}
if (op == RPMRICHOP_AND || op == RPMRICHOP_OR)
addRelation(ts, al, p, ds2, reversed);
ds1 = rpmdsFree(ds1);
ds2 = rpmdsFree(ds2);
}
return 0;
}
q = rpmalSatisfiesDepend(al, p, requires);
/* Avoid deps outside this transaction and self dependencies */
if (q == NULL || q == p)
return 0;
addSingleRelation(p, q, dsflags, reversed);
return 0;
}
/**
* Add element to list sorting by tsi_qcnt.
* @param p new element
* @retval qp address of first element
* @retval rp address of last element
* @param prefcolor
*/
static void addQ(tsortInfo p, tsortInfo * qp, tsortInfo * rp,
rpm_color_t prefcolor)
{
tsortInfo q, qprev;
rpm_color_t pcolor = rpmteColor(p->te);
int tailcond;
/* Mark the package as queued. */
p->tsi_reqx = 1;
if ((*rp) == NULL) { /* 1st element */
/* FIX: double indirection */
(*rp) = (*qp) = p;
return;
}
if (rpmteType(p->te) == TR_ADDED)
tailcond = (pcolor && pcolor != prefcolor);
else
tailcond = (pcolor && pcolor == prefcolor);
/* Find location in queue using metric tsi_qcnt and color. */
for (qprev = NULL, q = (*qp);
q != NULL;
qprev = q, q = q->tsi_suc)
{
/* Place preferred color towards queue head on install, tail on erase */
if (tailcond && (pcolor != rpmteColor(q->te)))
continue;
if (q->tsi_qcnt <= p->tsi_qcnt)
break;
}
if (qprev == NULL) { /* insert at beginning of list */
p->tsi_suc = q;
(*qp) = p; /* new head */
} else if (q == NULL) { /* insert at end of list */
qprev->tsi_suc = p;
(*rp) = p; /* new tail */
} else { /* insert between qprev and q */
p->tsi_suc = q;
qprev->tsi_suc = p;
}
}
typedef struct sccData_s {
int index; /* DFS node number counter */
tsortInfo *stack; /* Stack of nodes */
int stackcnt; /* Stack top counter */
scc SCCs; /* Array of SCC's found */
int sccCnt; /* Number of SCC's found */
} * sccData;
static void tarjan(sccData sd, tsortInfo tsi)
{
tsortInfo tsi_q;
relation rel;
/* use negative index numbers */
sd->index--;
/* Set the depth index for p */
tsi->tsi_SccIdx = sd->index;
tsi->tsi_SccLowlink = sd->index;
sd->stack[sd->stackcnt++] = tsi; /* Push p on the stack */
for (rel=tsi->tsi_relations; rel != NULL; rel=rel->rel_next) {
/* Consider successors of p */
tsi_q = rel->rel_suc;
if (tsi_q->tsi_SccIdx > 0)
/* Ignore already found SCCs */
continue;
if (tsi_q->tsi_SccIdx == 0){
/* Was successor q not yet visited? */
tarjan(sd, tsi_q); /* Recurse */
/* negative index numers: use max as it is closer to 0 */
tsi->tsi_SccLowlink = (
tsi->tsi_SccLowlink > tsi_q->tsi_SccLowlink
? tsi->tsi_SccLowlink : tsi_q->tsi_SccLowlink);
} else {
tsi->tsi_SccLowlink = (
tsi->tsi_SccLowlink > tsi_q->tsi_SccIdx
? tsi->tsi_SccLowlink : tsi_q->tsi_SccIdx);
}
}
if (tsi->tsi_SccLowlink == tsi->tsi_SccIdx) {
/* v is the root of an SCC? */
if (sd->stack[sd->stackcnt-1] == tsi) {
/* ignore trivial SCCs */
tsi_q = sd->stack[--sd->stackcnt];
tsi_q->tsi_SccIdx = 1;
} else {
int stackIdx = sd->stackcnt;
do {
tsi_q = sd->stack[--stackIdx];
tsi_q->tsi_SccIdx = sd->sccCnt;
} while (tsi_q != tsi);
stackIdx = sd->stackcnt;
do {
tsi_q = sd->stack[--stackIdx];
/* Calculate count for the SCC */
sd->SCCs[sd->sccCnt].count += tsi_q->tsi_count;
/* Subtract internal relations */
for (rel=tsi_q->tsi_relations; rel != NULL;
rel=rel->rel_next) {
if (rel->rel_suc != tsi_q &&
rel->rel_suc->tsi_SccIdx == sd->sccCnt)
sd->SCCs[sd->sccCnt].count--;
}
} while (tsi_q != tsi);
sd->SCCs[sd->sccCnt].size = sd->stackcnt - stackIdx;
/* copy members */
sd->SCCs[sd->sccCnt].members = xcalloc(sd->SCCs[sd->sccCnt].size,
sizeof(tsortInfo));
memcpy(sd->SCCs[sd->sccCnt].members, sd->stack + stackIdx,
sd->SCCs[sd->sccCnt].size * sizeof(tsortInfo));
sd->stackcnt = stackIdx;
sd->sccCnt++;
}
}
}
/* Search for SCCs and return an array last entry has a .size of 0 */
static scc detectSCCs(tsortInfo orderInfo, int nelem, int debugloops)
{
/* Set up data structures needed for the tarjan algorithm */
scc SCCs = xcalloc(nelem+3, sizeof(*SCCs));
tsortInfo *stack = xcalloc(nelem, sizeof(*stack));
struct sccData_s sd = { 0, stack, 0, SCCs, 2 };
for (int i = 0; i < nelem; i++) {
tsortInfo tsi = &orderInfo[i];
/* Start a DFS at each node */
if (tsi->tsi_SccIdx == 0)
tarjan(&sd, tsi);
}
free(stack);
SCCs = xrealloc(SCCs, (sd.sccCnt+1)*sizeof(struct scc_s));
/* Debug output */
if (sd.sccCnt > 2) {
int msglvl = debugloops ? RPMLOG_WARNING : RPMLOG_DEBUG;
rpmlog(msglvl, "%i Strongly Connected Components\n", sd.sccCnt-2);
for (int i = 2; i < sd.sccCnt; i++) {
rpmlog(msglvl, "SCC #%i: %i members (%i external dependencies)\n",
i-1, SCCs[i].size, SCCs[i].count);
/* loop over members */
for (int j = 0; j < SCCs[i].size; j++) {
tsortInfo member = SCCs[i].members[j];
rpmlog(msglvl, "\t%s\n", rpmteNEVRA(member->te));
/* show relations between members */
relation rel = member->tsi_forward_relations;
for (; rel != NULL; rel=rel->rel_next) {
if (rel->rel_suc->tsi_SccIdx!=i) continue;
rpmlog(msglvl, "\t\t%s %s\n",
rel->rel_flags ? "=>" : "->",
rpmteNEVRA(rel->rel_suc->te));
}
}
}
}
return SCCs;
}
static void collectTE(rpm_color_t prefcolor, tsortInfo q,
rpmte * newOrder, int * newOrderCount,
scc SCCs,
tsortInfo * queue_end,
tsortInfo * outer_queue,
tsortInfo * outer_queue_end)
{
char deptypechar = (rpmteType(q->te) == TR_REMOVED ? '-' : '+');
if (rpmIsDebug()) {
int depth = 1;
/* figure depth in tree for nice formatting */
for (rpmte p = q->te; (p = rpmteParent(p)); depth++) {}
rpmlog(RPMLOG_DEBUG, "%5d%5d%5d%5d %*s%c%s\n",
*newOrderCount, q->tsi_count, q->tsi_qcnt,
depth, (2 * depth), "",
deptypechar, rpmteNEVRA(q->te));
}
newOrder[*newOrderCount] = q->te;
(*newOrderCount)++;
/* T6. Erase relations. */
for (relation rel = q->tsi_relations; rel != NULL; rel = rel->rel_next) {
tsortInfo p = rel->rel_suc;
/* ignore already collected packages */
if (p->tsi_SccIdx == 0) continue;
if (p == q) continue;
if (p && (--p->tsi_count) == 0) {
(void) rpmteSetParent(p->te, q->te);
if (q->tsi_SccIdx > 1 && q->tsi_SccIdx != p->tsi_SccIdx) {
/* Relation point outside of this SCC: add to outside queue */
assert(outer_queue != NULL && outer_queue_end != NULL);
addQ(p, outer_queue, outer_queue_end, prefcolor);
} else {
addQ(p, &q->tsi_suc, queue_end, prefcolor);
}
}
if (p && p->tsi_SccIdx > 1 &&
p->tsi_SccIdx != q->tsi_SccIdx) {
if (--SCCs[p->tsi_SccIdx].count == 0) {
/* New SCC is ready, add this package as representative */
(void) rpmteSetParent(p->te, q->te);
if (outer_queue != NULL) {
addQ(p, outer_queue, outer_queue_end, prefcolor);
} else {
addQ(p, &q->tsi_suc, queue_end, prefcolor);
}
}
}
}
q->tsi_SccIdx = 0;
}
static void dijkstra(const struct scc_s *SCC, int sccNr)
{
int start, end;
relation rel;
/* can use a simple queue as edge weights are always 1 */
tsortInfo * queue = xmalloc((SCC->size+1) * sizeof(*queue));
/*
* Find packages that are prerequired and use them as
* starting points for the Dijkstra algorithm
*/
start = end = 0;
for (int i = 0; i < SCC->size; i++) {
tsortInfo tsi = SCC->members[i];
tsi->tsi_SccLowlink = INT_MAX;
for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
if (rel->rel_flags && rel->rel_suc->tsi_SccIdx == sccNr) {
if (rel->rel_suc != tsi) {
tsi->tsi_SccLowlink = 0;
queue[end++] = tsi;
} else {
tsi->tsi_SccLowlink = INT_MAX/2;
}
break;
}
}
}
if (start == end) { /* no regular prereqs; add self prereqs to queue */
for (int i = 0; i < SCC->size; i++) {
tsortInfo tsi = SCC->members[i];
if (tsi->tsi_SccLowlink != INT_MAX) {
queue[end++] = tsi;
}
}
}
/* Do Dijkstra */
while (start != end) {
tsortInfo tsi = queue[start++];
for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
tsortInfo next_tsi = rel->rel_suc;
if (next_tsi->tsi_SccIdx != sccNr) continue;
if (next_tsi->tsi_SccLowlink > tsi->tsi_SccLowlink+1) {
next_tsi->tsi_SccLowlink = tsi->tsi_SccLowlink + 1;
queue[end++] = rel->rel_suc;
}
}
}
free(queue);
}
static void collectSCC(rpm_color_t prefcolor, tsortInfo p_tsi,
rpmte * newOrder, int * newOrderCount,
scc SCCs, tsortInfo * queue_end)
{
int sccNr = p_tsi->tsi_SccIdx;
const struct scc_s * SCC = SCCs+sccNr;
/* remove p from the outer queue */
tsortInfo outer_queue_start = p_tsi->tsi_suc;
p_tsi->tsi_suc = NULL;
/*
* Run a multi source Dijkstra's algorithm to find relations
* that can be zapped with least danger to pre reqs.
* As weight of the edges is always 1 it is not necessary to
* sort the vertices by distance as the queue gets them
* already in order
*/
dijkstra(SCC, sccNr);
while (1) {
tsortInfo best = NULL;
tsortInfo inner_queue_start, inner_queue_end;
int best_score = 0;
/* select best candidate to start with */
for (int i = 0; i < SCC->size; i++) {
tsortInfo tsi = SCC->members[i];
if (tsi->tsi_SccIdx == 0) /* package already collected */
continue;
if (tsi->tsi_SccLowlink >= best_score) {
best = tsi;
best_score = tsi->tsi_SccLowlink;
}
}
if (best == NULL) /* done */
break;
/* collect best candidate and all packages that get freed */
inner_queue_start = inner_queue_end = NULL;
addQ(best, &inner_queue_start, &inner_queue_end, prefcolor);
for (; inner_queue_start != NULL;
inner_queue_start = inner_queue_start->tsi_suc) {
/* Mark the package as unqueued. */
inner_queue_start->tsi_reqx = 0;
collectTE(prefcolor, inner_queue_start, newOrder, newOrderCount,
SCCs, &inner_queue_end, &outer_queue_start, queue_end);
}
}
/* restore outer queue */
p_tsi->tsi_suc = outer_queue_start;
}
int rpmtsOrder(rpmts ts)
{
tsMembers tsmem = rpmtsMembers(ts);
rpm_color_t prefcolor = rpmtsPrefColor(ts);
rpmtsi pi; rpmte p;
tsortInfo q, r;
rpmte * newOrder;
int newOrderCount = 0;
int rc;
rpmal erasedPackages;
scc SCCs;
int nelem = rpmtsNElements(ts);
tsortInfo sortInfo = xcalloc(nelem, sizeof(struct tsortInfo_s));
(void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
/* Create erased package index. */
erasedPackages = rpmtsCreateAl(ts, TR_REMOVED);
for (int i = 0; i < nelem; i++) {
sortInfo[i].te = tsmem->order[i];
rpmteSetTSI(tsmem->order[i], &sortInfo[i]);
}
/* Record relations. */
rpmlog(RPMLOG_DEBUG, "========== recording tsort relations\n");
pi = rpmtsiInit(ts);
while ((p = rpmtsiNext(pi, 0)) != NULL) {
rpmal al = (rpmteType(p) == TR_REMOVED) ?
erasedPackages : tsmem->addedPackages;
rpmds requires = rpmdsInit(rpmteDS(p, RPMTAG_REQUIRENAME));
rpmds recommends = rpmdsInit(rpmteDS(p, RPMTAG_RECOMMENDNAME));
rpmds suggests = rpmdsInit(rpmteDS(p, RPMTAG_SUGGESTNAME));
rpmds supplements = rpmdsInit(rpmteDS(p, RPMTAG_SUPPLEMENTNAME));
rpmds enhances = rpmdsInit(rpmteDS(p, RPMTAG_ENHANCENAME));
rpmds order = rpmdsInit(rpmteDS(p, RPMTAG_ORDERNAME));
while (rpmdsNext(requires) >= 0) {
/* Record next "q <- p" relation (i.e. "p" requires "q"). */
(void) addRelation(ts, al, p, requires, 0);
}
while (rpmdsNext(recommends) >= 0) {
/* Record next "q <- p" relation (i.e. "p" recommends "q"). */
(void) addRelation(ts, al, p, recommends, 0);
}
while (rpmdsNext(suggests) >= 0) {
/* Record next "q <- p" relation (i.e. "p" suggests "q"). */
(void) addRelation(ts, al, p, suggests, 0);
}
while (rpmdsNext(order) >= 0) {
/* Record next "q <- p" ordering request */
(void) addRelation(ts, al, p, order, 0);
}
while (rpmdsNext(supplements) >= 0) {
/* Record next "p -> q" relation (i.e. "q" supplemented by "p"). */
(void) addRelation(ts, al, p, supplements, 1);
}
while (rpmdsNext(enhances) >= 0) {
/* Record next "p <- q" relation (i.e. "q" is enhanced by "p"). */
(void) addRelation(ts, al, p, enhances, 1);
}
}
rpmtsiFree(pi);
newOrder = xcalloc(tsmem->orderCount, sizeof(*newOrder));
SCCs = detectSCCs(sortInfo, nelem, (rpmtsFlags(ts) & RPMTRANS_FLAG_DEPLOOPS));
rpmlog(RPMLOG_DEBUG, "========== tsorting packages (order, #predecessors, #succesors, depth)\n");
for (int i = 0; i < 2; i++) {
/* Do two separate runs: installs first - then erases */
int oType = !i ? TR_ADDED : TR_REMOVED;
q = r = NULL;
/* Scan for zeroes and add them to the queue */
for (int e = 0; e < nelem; e++) {
tsortInfo p = &sortInfo[e];
if (rpmteType(p->te) != oType) continue;
if (p->tsi_count != 0)
continue;
p->tsi_suc = NULL;
addQ(p, &q, &r, prefcolor);
}
/* Add one member of each leaf SCC */
for (int i = 2; SCCs[i].members != NULL; i++) {
tsortInfo member = SCCs[i].members[0];
if (SCCs[i].count == 0 && rpmteType(member->te) == oType) {
addQ(member, &q, &r, prefcolor);
}
}
while (q != NULL) {
/* Mark the package as unqueued. */
q->tsi_reqx = 0;
if (q->tsi_SccIdx > 1) {
collectSCC(prefcolor, q, newOrder, &newOrderCount, SCCs, &r);
} else {
collectTE(prefcolor, q, newOrder, &newOrderCount, SCCs, &r,
NULL, NULL);
}
q = q->tsi_suc;
}
}
/* Clean up tsort data */
for (int i = 0; i < nelem; i++) {
rpmteSetTSI(tsmem->order[i], NULL);
rpmTSIFree(&sortInfo[i]);
}
free(sortInfo);
assert(newOrderCount == tsmem->orderCount);
tsmem->order = _free(tsmem->order);
tsmem->order = newOrder;
tsmem->orderAlloced = tsmem->orderCount;
rc = 0;
for (int i = 2; SCCs[i].members != NULL; i++) {
free(SCCs[i].members);
}
free(SCCs);
rpmalFree(erasedPackages);
(void) rpmswExit(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
return rc;
}