From c74b6658a6ab63b403682a479be5c7dcb794fc61 Mon Sep 17 00:00:00 2001 From: Michael Schroeder Date: Wed, 30 Jun 2021 15:03:41 +0200 Subject: [PATCH] Conda: add experimental trackfeature minimizing support --- ext/testcase.c | 1 + src/problems.c | 68 ++++++++++++++++++++++++++++++++ src/problems.h | 1 + src/rules.c | 99 +++++++++++++++++++++++++++++++++++++++++++++++ src/rules.h | 7 +++- src/solver.c | 24 +++++++++++- src/solver.h | 5 +++ src/solverdebug.c | 2 + 8 files changed, 205 insertions(+), 2 deletions(-) diff --git a/ext/testcase.c b/ext/testcase.c index 20b0c48f..a064407a 100644 --- a/ext/testcase.c +++ b/ext/testcase.c @@ -1193,6 +1193,7 @@ static struct rclass2str { { SOLVER_RULE_YUMOBS, "yumobs" }, { SOLVER_RULE_BLACK, "black" }, { SOLVER_RULE_RECOMMENDS, "recommends" }, + { SOLVER_RULE_TRACKFEATURE, "trackfeature" }, { 0, 0 } }; diff --git a/src/problems.c b/src/problems.c index a6b9394f..9a89ed0e 100644 --- a/src/problems.c +++ b/src/problems.c @@ -316,6 +316,74 @@ solver_autouninstall(Solver *solv, int start) return v; } +static inline int +queue_contains(Queue *q, Id id) +{ + int i; + for (i = 0; i < q->count; i++) + if (q->elements[i] == id) + return 1; + return 0; +} + +static int +autoallowtrackfeature_sortcmp(const void *ap, const void *bp, void *dp) +{ + Pool *pool = dp; + Id *a = (Id *)ap, *b = (Id *)bp; + if (a[1] != b[1]) + return a[1] - b[1]; + if (a[0] != b[0]) + return strcmp(pool_id2str(pool, b[0]), pool_id2str(pool, a[0])); + return 0; +} + +/*------------------------------------------------------------------- + * try to fix a problem by autodisabling trackfeature rules + */ +Id +solver_autoallowtrackfeature(Solver *solv, int start) +{ + Pool *pool = solv->pool; + int i, j, cnt, oldcount; + Id v, p, id; + Queue q, dq; + + if (!solv->allowedtrackfeatureq) + return 0; + queue_init(&q); + queue_init(&dq); + for (i = start + 1; i < solv->problems.count - 1; i++) + { + v = solv->problems.elements[i]; + if (v < solv->trackfeaturerules || v >= solv->trackfeaturerules_end) + continue; + p = -solv->rules[v].p; + solvable_lookup_idarray(pool->solvables + p, SOLVABLE_TRACK_FEATURES, &q); + cnt = 0; + oldcount = dq.count; + for (j = 0; j < q.count; j++) + { + if (queue_contains(solv->allowedtrackfeatureq, q.elements[j])) + continue; + queue_push2(&dq, q.elements[j], 0); + cnt++; + } + for (j = oldcount; j < dq.count; j += 2) + dq.elements[j + 1] = cnt; + } + if (dq.count > 2) + solv_sort(dq.elements, dq.count / 2, sizeof(Id) * 2, autoallowtrackfeature_sortcmp, pool); + id = dq.count ? dq.elements[0] : 0; + queue_free(&dq); + queue_free(&q); + if (id) + { + POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "autoallowing track feature %s\n", pool_id2str(pool, id)); + solver_allow_trackfeature(solv, id); + } + return id; +} /*------------------------------------------------------------------- * enable weak rules diff --git a/src/problems.h b/src/problems.h index 45e4e7c6..2915d725 100644 --- a/src/problems.h +++ b/src/problems.h @@ -32,6 +32,7 @@ struct s_Solver; void solver_recordproblem(struct s_Solver *solv, Id rid); void solver_fixproblem(struct s_Solver *solv, Id rid); Id solver_autouninstall(struct s_Solver *solv, int start); +Id solver_autoallowtrackfeature(struct s_Solver *solv, int start); void solver_disableproblemset(struct s_Solver *solv, int start); int solver_prepare_solutions(struct s_Solver *solv); diff --git a/src/rules.c b/src/rules.c index b1b5f09c..6a4aa771 100644 --- a/src/rules.c +++ b/src/rules.c @@ -2992,6 +2992,12 @@ solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp) *fromp = -r->p; return SOLVER_RULE_BLACK; } + if (rid >= solv->trackfeaturerules && rid < solv->trackfeaturerules_end) + { + if (fromp) + *fromp = -r->p; + return SOLVER_RULE_TRACKFEATURE; + } if (rid >= solv->choicerules && rid < solv->choicerules_end) return SOLVER_RULE_CHOICE; if (rid >= solv->recommendsrules && rid < solv->recommendsrules_end) @@ -3030,6 +3036,8 @@ solver_ruleclass(Solver *solv, Id rid) return SOLVER_RULE_RECOMMENDS; if (rid >= solv->blackrules && rid < solv->blackrules_end) return SOLVER_RULE_BLACK; + if (rid >= solv->trackfeaturerules && rid < solv->trackfeaturerules_end) + return SOLVER_RULE_TRACKFEATURE; if (rid >= solv->learntrules && rid < solv->nrules) return SOLVER_RULE_LEARNT; return SOLVER_RULE_UNKNOWN; @@ -4227,3 +4235,94 @@ solver_check_brokenorphanrules(Solver *solv, Queue *dq) } } +static int +queue_contains_sorted(Queue *q, Id id, int insert) +{ + int i; + for (i = 0; i < q->count; i++) + { + if (q->elements[i] == id) + return 1; + if (q->elements[i] > id) + break; + } + if (insert) + queue_insert(q, i, id); + return 0; +} + +void +solver_allow_trackfeature(Solver *solv, Id id) +{ + Pool *pool = solv->pool; + int i, j; + Rule *r; + Queue q; + Id p; + if (queue_contains_sorted(solv->allowedtrackfeatureq, id, 1)) + return; /* already allowed? */ + queue_init(&q); + for (i = solv->trackfeaturerules, r = solv->rules + i; i < solv->trackfeaturerules_end; i++, r++) + { + if (r->d < 0) + continue; /* already disabled */ + p = -r->p; + solvable_lookup_idarray(pool->solvables + p, SOLVABLE_TRACK_FEATURES, &q); + if (!queue_contains_sorted(&q, id, 0)) + continue; + for (j = 0; j < q.count; j++) + if (q.elements[j] != id && !queue_contains_sorted(solv->allowedtrackfeatureq, q.elements[j], 0)) + break; + if (j == q.count) + solver_disablerule(solv, r); + } + queue_free(&q); +} + +void +solver_addtrackfeaturerules(Solver *solv, Map *addedmap) +{ + Pool *pool = solv->pool; + Repo *installed = solv->installed; + Id p; + Solvable *s; + Queue q; + int i; + + solv->trackfeaturerules = solv->nrules; + queue_init(&q); + solv->allowedtrackfeatureq = solv_calloc(1, sizeof(Queue)); + queue_init(solv->allowedtrackfeatureq); + FOR_REPO_SOLVABLES(installed, p, s) + { + solvable_lookup_idarray(s, SOLVABLE_TRACK_FEATURES, &q); + if (!q.elements) + continue; + for (i = 0; i < q.count; i++) + queue_contains_sorted(solv->allowedtrackfeatureq, q.elements[i], 1); + } + FOR_POOL_SOLVABLES(p) + { + Solvable *s = pool->solvables + p; + if (s->repo == installed) + continue; + if (!MAPTST(addedmap, p)) + continue; /* not possible to install */ + solvable_lookup_idarray(s, SOLVABLE_TRACK_FEATURES, &q); + if (!q.count) + continue; + for (i = 0; i < q.count; i++) + if (!queue_contains_sorted(solv->allowedtrackfeatureq, q.elements[i], 0)) + break; + if (i < q.count) { + solver_addrule(solv, -p, 0, 0); +} + } + solv->trackfeaturerules_end = solv->nrules; + if (solv->trackfeaturerules == solv->trackfeaturerules_end) + { + queue_free(solv->allowedtrackfeatureq); + solv->allowedtrackfeatureq = solv_free(solv->allowedtrackfeatureq); + } + queue_free(&q); +} diff --git a/src/rules.h b/src/rules.h index 3fcede07..e2a7f33b 100644 --- a/src/rules.h +++ b/src/rules.h @@ -74,7 +74,8 @@ typedef enum { SOLVER_RULE_BEST = 0x900, SOLVER_RULE_YUMOBS = 0xa00, SOLVER_RULE_RECOMMENDS = 0xb00, - SOLVER_RULE_BLACK = 0xc00 + SOLVER_RULE_BLACK = 0xc00, + SOLVER_RULE_TRACKFEATURE = 0xd00 } SolverRuleinfo; #define SOLVER_RULE_TYPEMASK 0xff00 @@ -142,6 +143,10 @@ extern void solver_addblackrules(struct s_Solver *solv); /* recommends rules */ extern void solver_addrecommendsrules(struct s_Solver *solv); +/* trackfeature rules */ +void solver_allow_trackfeature(struct s_Solver *solv, Id id); +void solver_addtrackfeaturerules(struct s_Solver *solv, Map *addedmap); + /* policy rule disabling/reenabling */ extern void solver_disablepolicyrules(struct s_Solver *solv); extern void solver_reenablepolicyrules(struct s_Solver *solv, int jobidx); diff --git a/src/solver.c b/src/solver.c index 89a2ed10..5d269f58 100644 --- a/src/solver.c +++ b/src/solver.c @@ -253,6 +253,13 @@ makeruledecisions(Solver *solv, int disablerules) } queue_push(&solv->problems, 0); /* finish problem */ + if (solv->allowedtrackfeatureq && solver_autoallowtrackfeature(solv, oldproblemcount) != 0) + { + solv->problems.count = oldproblemcount; + havedisabled = 1; + break; /* start over */ + } + /* try autouninstall if requested */ if (doautouninstall) { @@ -1028,6 +1035,14 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) } queue_free(&weakq); + if (solv->allowedtrackfeatureq && solver_autoallowtrackfeature(solv, oldproblemcount) != 0) + { + solv->problems.count = oldproblemcount; + solv->learnt_pool.count = oldlearntpoolcount; + solver_reset(solv); + return 0; + } + if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size) if (solver_autouninstall(solv, oldproblemcount) != 0) { @@ -1383,6 +1398,7 @@ solver_free(Solver *solv) queuep_free(&solv->suggestscplxq); queuep_free(&solv->brokenorphanrules); queuep_free(&solv->recommendsruleq); + queuep_free(&solv->allowedtrackfeatureq); map_free(&solv->recommendsmap); map_free(&solv->suggestsmap); @@ -3415,6 +3431,7 @@ solver_solve(Solver *solv, Queue *job) /* free old stuff in case we re-run a solver */ queuep_free(&solv->update_targets); queuep_free(&solv->cleandeps_updatepkgs); + queuep_free(&solv->allowedtrackfeatureq); queue_empty(&solv->ruleassertions); solv->bestrules_info = solv_free(solv->bestrules_info); solv->yumobsrules_info = solv_free(solv->yumobsrules_info); @@ -4057,6 +4074,11 @@ solver_solve(Solver *solv, Queue *job) else solv->blackrules = solv->blackrules_end = solv->nrules; + if (pool->disttype == DISTTYPE_CONDA) + solver_addtrackfeaturerules(solv, &addedmap); + else + solv->trackfeaturerules = solv->trackfeaturerules_end = solv->nrules; + if (solv->havedisfavored && solv->strongrecommends && solv->recommendsruleq) solver_addrecommendsrules(solv); else @@ -4077,7 +4099,7 @@ solver_solve(Solver *solv, Queue *job) map_free(&installcandidatemap); queue_free(&q); - POOL_DEBUG(SOLV_DEBUG_STATS, "%d pkg rules, 2 * %d update rules, %d job rules, %d infarch rules, %d dup rules, %d choice rules, %d best rules, %d yumobs rules\n", solv->pkgrules_end - 1, solv->updaterules_end - solv->updaterules, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules, solv->choicerules_end - solv->choicerules, solv->bestrules_end - solv->bestrules, solv->yumobsrules_end - solv->yumobsrules); + POOL_DEBUG(SOLV_DEBUG_STATS, "%d pkg rules, 2 * %d update rules, %d job rules, %d infarch rules, %d dup rules, %d choice rules, %d best rules, %d yumobs rules, %d trackfeature rules\n", solv->pkgrules_end - 1, solv->updaterules_end - solv->updaterules, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules, solv->choicerules_end - solv->choicerules, solv->bestrules_end - solv->bestrules, solv->yumobsrules_end - solv->yumobsrules, solv->trackfeaturerules_end - solv->trackfeaturerules); POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024); /* create weak map */ diff --git a/src/solver.h b/src/solver.h index 2dec2590..03c61f5c 100644 --- a/src/solver.h +++ b/src/solver.h @@ -79,6 +79,9 @@ struct s_Solver { Id blackrules; /* rules from blacklisted packages */ Id blackrules_end; + Id trackfeaturerules; /* rules from packages containing track features */ + Id trackfeaturerules_end; + Id choicerules; /* choice rules (always weak) */ Id choicerules_end; Id *choicerules_info; /* the rule we used to generate the choice rule */ @@ -215,6 +218,8 @@ struct s_Solver { int do_extra_reordering; /* reorder for future installed packages */ Queue *recommendsruleq; /* pkg rules comming from recommends */ + + Queue *allowedtrackfeatureq; /* which track features may be installed */ #endif /* LIBSOLV_INTERNAL */ }; diff --git a/src/solverdebug.c b/src/solverdebug.c index 0b2879b0..1f7b41b9 100644 --- a/src/solverdebug.c +++ b/src/solverdebug.c @@ -132,6 +132,8 @@ solver_printruleclass(Solver *solv, int type, Rule *r) POOL_DEBUG(type, "BLACK "); else if (p >= solv->recommendsrules && p < solv->recommendsrules_end) POOL_DEBUG(type, "RECOMMENDS "); + else if (p >= solv->trackfeaturerules && p < solv->trackfeaturerules_end) + POOL_DEBUG(type, "TRACKFEATURE "); solver_printrule(solv, type, r); } -- 2.47.2