2 * Copyright (c) 2017, SUSE Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
11 * code to find and erase unneeded packages
20 #include "solverdebug.h"
21 #include "solver_private.h"
31 * This functions collects all packages that are looked at
32 * when a dependency is checked. We need it to "pin" installed
33 * packages when removing a supplemented package in createcleandepsmap.
34 * Here's an not uncommon example:
35 * A contains "Supplements: packageand(B, C)"
36 * B contains "Requires: A"
37 * Now if we remove C, the supplements is no longer true,
38 * thus we also remove A. Without the dep_pkgcheck function, we
39 * would now also remove B, but this is wrong, as adding back
40 * C doesn't make the supplements true again. Thus we "pin" B
42 * There's probably a better way to do this, but I haven't come
46 dep_pkgcheck_slow(Solver *solv, Id dep, Map *m, Queue *q)
48 Pool *pool = solv->pool;
53 Reldep *rd = GETRELDEP(pool, dep);
56 if (rd->flags == REL_AND)
58 dep_pkgcheck_slow(solv, rd->name, m, q);
59 dep_pkgcheck_slow(solv, rd->evr, m, q);
62 if (rd->flags == REL_COND || rd->flags == REL_UNLESS)
64 dep_pkgcheck_slow(solv, rd->name, m, q);
65 if (ISRELDEP(rd->evr))
67 Reldep *rd2 = GETRELDEP(pool, rd->evr);
68 if (rd2->flags == REL_ELSE)
69 dep_pkgcheck_slow(solv, rd2->evr, m, q);
73 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
77 FOR_PROVIDES(p, pp, dep)
78 if (!m || MAPTST(m, p))
83 dep_pkgcheck(Solver *solv, Id dep, Map *m, Queue *q)
85 Pool *pool = solv->pool;
88 if (!ISSIMPLEDEP(pool, dep))
90 dep_pkgcheck_slow(solv, dep, m, q);
93 FOR_PROVIDES(p, pp, dep)
94 if (!m || MAPTST(m, p))
99 check_xsupp(Solver *solv, Queue *depq, Id dep)
101 Pool *pool = solv->pool;
106 Reldep *rd = GETRELDEP(pool, dep);
109 if (rd->flags == REL_AND)
111 if (!check_xsupp(solv, depq, rd->name))
113 return check_xsupp(solv, depq, rd->evr);
115 if (rd->flags == REL_OR)
117 if (check_xsupp(solv, depq, rd->name))
119 return check_xsupp(solv, depq, rd->evr);
121 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
123 if (depq && rd->flags == REL_NAMESPACE)
126 for (i = 0; i < depq->count; i++)
127 if (depq->elements[i] == dep || depq->elements[i] == rd->name)
132 FOR_PROVIDES(p, pp, dep)
133 if (p == SYSTEMSOLVABLE || pool->solvables[p].repo == solv->installed)
146 /* Tarjan's SCC algorithm, slightly modifed */
148 trj_visit(struct trj_data *trj, Id node)
151 Queue *edges = trj->edges;
152 Id nnode, myidx, stackstart;
155 low[node] = myidx = trj->idx++;
156 low[(stackstart = trj->nstack++)] = node;
157 for (i = edges->elements[node]; (nnode = edges->elements[i]) != 0; i++)
162 if (!edges->elements[edges->elements[nnode]])
168 trj_visit(trj, nnode);
173 if (l < trj->firstidx)
176 for (k = l; low[low[k]] == l; k++)
179 else if (l < low[node])
182 if (low[node] == myidx)
184 if (myidx != trj->firstidx)
186 for (i = stackstart; i < trj->nstack; i++)
188 trj->nstack = stackstart;
192 #ifdef ENABLE_COMPLEX_DEPS
194 complex_filter_unneeded(Pool *pool, Id ip, Id req, Queue *edges, Map *cleandepsmap, Queue *unneededq)
201 i = pool_normalize_complex_dep(pool, req, &dq, CPLXDEPS_EXPAND);
202 if (i == 0 || i == 1)
207 for (i = 0; i < dq.count; i++)
209 for (; (p = dq.elements[i]) != 0; i++)
213 if (pool->solvables[-p].repo != pool->installed)
217 if (p == ip || pool->solvables[p].repo != pool->installed || !MAPTST(cleandepsmap, p - pool->installed->start))
219 for (j = 0; j < unneededq->count; j++)
220 if (p == unneededq->elements[j])
222 if (edges->elements[edges->count - 1] != j + 1)
223 queue_push(edges, j + 1);
227 while (dq.elements[i])
236 filter_unneeded(Solver *solv, Queue *unneededq, Map *unneededmap, int justone)
238 Pool *pool = solv->pool;
239 Repo *installed = solv->installed;
243 int i, j, pass, count = unneededq->count;
246 if (unneededq->count < 2)
252 map_grow(unneededmap, installed->end - installed->start);
253 for (i = 0; i < count; i++)
254 MAPSET(unneededmap, unneededq->elements[i] - installed->start);
256 map_init(&installedm, pool->nsolvables);
257 for (i = installed->start; i < installed->end; i++)
258 if (pool->solvables[i].repo == installed)
259 MAPSET(&installedm, i);
261 nrequires = solv_calloc(count, sizeof(Id));
263 queue_prealloc(&edges, count * 4 + 10); /* pre-size */
266 * Go through the solvables in the nodes queue and create edges for
267 * all requires/recommends/supplements between the nodes.
268 * The edges are stored in the edges queue, we add 1 to the node
269 * index so that nodes in the edges queue are != 0 and we can
270 * terminate the edge list with 0.
271 * Thus for node element 5, the edges are stored starting at
272 * edges.elements[6] and are 0-terminated.
274 /* leave first element zero to make things easier */
275 /* also add trailing zero */
276 queue_insertn(&edges, 0, 1 + count + 1, 0);
278 /* first requires and recommends */
279 for (i = 0; i < count; i++)
281 Solvable *s = pool->solvables + unneededq->elements[i];
282 int oldcount = edges.count;
283 edges.elements[i + 1] = oldcount;
284 for (pass = 0; pass < 2; pass++)
286 unsigned int off = pass == 0 ? s->requires : s->recommends;
289 for (dp = s->repo->idarraydata + off; (dep = *dp) != 0; dp++)
291 #ifdef ENABLE_COMPLEX_DEPS
292 if (pool_is_complex_dep(pool, dep))
294 complex_filter_unneeded(pool, s - pool->solvables, dep, &edges, unneededmap, unneededq);
301 FOR_PROVIDES(p, pp, dep)
303 Solvable *sp = pool->solvables + p;
304 if (s == sp || sp->repo != installed)
311 FOR_PROVIDES(p, pp, dep)
313 Solvable *sp = pool->solvables + p;
314 if (s == sp || sp->repo != installed || !MAPTST(unneededmap, p - installed->start))
316 for (j = 0; j < count; j++)
317 if (p == unneededq->elements[j])
319 if (edges.elements[edges.count - 1] != j + 1)
320 queue_push(&edges, j + 1);
325 nrequires[i] = edges.count - oldcount;
327 queue_push(&edges, 0);
330 printf("requires + recommends\n");
331 for (i = 0; i < count; i++)
334 printf(" %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]);
335 for (j = edges.elements[i + 1]; edges.elements[j]; j++)
336 printf(" - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1]));
340 /* then add supplements */
341 for (i = 0; i < count; i++)
343 Solvable *s = pool->solvables + unneededq->elements[i];
348 for (dp = s->repo->idarraydata + s->supplements; *dp; dp++)
349 if (solver_dep_possible(solv, *dp, &installedm))
353 queue_init_buffer(&iq, iqbuf, sizeof(iqbuf)/sizeof(*iqbuf));
354 dep_pkgcheck(solv, *dp, 0, &iq);
355 if (justone && iq.count != 1)
360 for (k = 0; k < iq.count; k++)
362 Id p = iq.elements[k];
363 Solvable *sp = pool->solvables + p;
364 if (p == unneededq->elements[i] || sp->repo != installed || !MAPTST(unneededmap, p - installed->start))
366 for (j = 0; j < count; j++)
367 if (p == unneededq->elements[j])
369 /* now add edge from j + 1 to i + 1 */
370 queue_insert(&edges, edges.elements[j + 1] + nrequires[j], i + 1);
371 /* addapt following edge pointers */
372 for (j = j + 2; j < count + 1; j++)
381 printf("+ supplements\n");
382 for (i = 0; i < count; i++)
385 printf(" %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]);
386 for (j = edges.elements[i + 1]; edges.elements[j]; j++)
387 printf(" - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1]));
390 map_free(&installedm);
392 /* now run SCC algo two times, first with requires+recommends+supplements,
393 * then again without the requires. We run it the second time to get rid
394 * of packages that got dragged in via recommends/supplements */
396 * low will contain the result of the SCC search.
397 * it must be of at least size 2 * (count + 1) and
398 * must be zero initialized.
400 * 0 low low ... low stack stack ...stack 0
403 low = solv_calloc(count + 1, 2 * sizeof(Id));
404 for (pass = 0; pass < 2; pass++)
409 memset(low, 0, (count + 1) * (2 * sizeof(Id)));
410 for (i = 0; i < count; i++)
412 edges.elements[i + 1] += nrequires[i];
413 if (!unneededq->elements[i])
414 low[i + 1] = -1; /* ignore this node */
419 trj.idx = count + 1; /* stack starts here */
420 for (i = 1; i <= count; i++)
424 if (edges.elements[edges.elements[i]])
426 trj.firstidx = trj.nstack = trj.idx;
431 Id myidx = trj.idx++;
437 for (i = 0; i < count; i++)
439 unneededq->elements[i] = 0;
442 solv_free(nrequires);
445 /* finally remove all pruned entries from unneededq */
446 for (i = j = 0; i < count; i++)
447 if (unneededq->elements[i])
448 unneededq->elements[j++] = unneededq->elements[i];
449 queue_truncate(unneededq, j);
454 #ifdef ENABLE_COMPLEX_DEPS
456 complex_cleandeps_remove(Pool *pool, Id ip, Id req, Map *im, Map *installedm, Queue *iq)
463 i = pool_normalize_complex_dep(pool, req, &dq, CPLXDEPS_EXPAND);
464 if (i == 0 || i == 1)
469 for (i = 0; i < dq.count; i++)
471 for (; (p = dq.elements[i]) != 0; i++)
475 if (!MAPTST(installedm, -p))
479 if (p != SYSTEMSOLVABLE && MAPTST(im, p))
481 #ifdef CLEANDEPSDEBUG
482 printf("%s requires/recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
487 while (dq.elements[i])
494 complex_cleandeps_addback(Pool *pool, Id ip, Id req, Map *im, Map *installedm, Queue *iq, Map *userinstalled)
501 i = pool_normalize_complex_dep(pool, req, &dq, CPLXDEPS_EXPAND);
502 if (i == 0 || i == 1)
507 for (i = 0; i < dq.count; i++)
510 for (; (p = dq.elements[i]) != 0; i++)
514 if (!MAPTST(installedm, -p))
522 for (i = blk; (p = dq.elements[i]) != 0; i++)
528 if (!MAPTST(installedm, p))
530 if (p == ip || MAPTST(userinstalled, p - pool->installed->start))
532 #ifdef CLEANDEPSDEBUG
533 printf("%s requires/recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
539 while (dq.elements[i])
548 queue_contains(Queue *q, Id id)
551 for (i = 0; i < q->count; i++)
552 if (q->elements[i] == id)
558 find_update_seeds(Solver *solv, Queue *updatepkgs_filtered, Map *userinstalled)
560 Pool *pool = solv->pool;
561 Repo *installed = solv->installed;
562 Queue *cleandeps_updatepkgs = solv->cleandeps_updatepkgs;
566 queue_prealloc(updatepkgs_filtered, cleandeps_updatepkgs->count);
567 for (i = 0; i < cleandeps_updatepkgs->count; i++)
569 p = cleandeps_updatepkgs->elements[i];
570 if (pool->solvables[p].repo == installed)
572 #ifdef ENABLE_LINKED_PKGS
573 const char *name = pool_id2str(pool, pool->solvables[p].name);
574 if (strncmp(name, "pattern:", 8) == 0 || strncmp(name, "application:", 12) == 0)
577 queue_push(updatepkgs_filtered, p);
580 #ifdef CLEANDEPSDEBUG
581 printf("SEEDS IN (%d)\n", updatepkgs_filtered->count);
582 for (i = 0; i < updatepkgs_filtered->count; i++)
583 printf(" - %s\n", pool_solvid2str(pool, updatepkgs_filtered->elements[i]));
585 filter_unneeded(solv, updatepkgs_filtered, 0, 1);
586 #ifdef CLEANDEPSDEBUG
587 printf("SEEDS OUT (%d)\n", updatepkgs_filtered->count);
588 for (i = 0; i < updatepkgs_filtered->count; i++)
589 printf(" - %s\n", pool_solvid2str(pool, updatepkgs_filtered->elements[i]));
591 /* make sure userinstalled packages are in the seeds */
592 for (i = j = 0; i < updatepkgs_filtered->count; i++)
594 p = updatepkgs_filtered->elements[i];
595 if (!MAPTST(userinstalled, p - installed->start))
596 updatepkgs_filtered->elements[j++] = p;
598 queue_truncate(updatepkgs_filtered, j);
599 for (i = 0; i < cleandeps_updatepkgs->count; i++)
601 p = cleandeps_updatepkgs->elements[i];
602 if (pool->solvables[p].repo == installed)
604 #ifdef ENABLE_LINKED_PKGS
605 const char *name = pool_id2str(pool, pool->solvables[p].name);
606 if (strncmp(name, "pattern:", 8) == 0 || strncmp(name, "application:", 12) == 0)
608 queue_push(updatepkgs_filtered, p);
612 if (MAPTST(userinstalled, p - installed->start))
613 queue_push(updatepkgs_filtered, p);
616 #ifdef CLEANDEPSDEBUG
617 printf("SEEDS FINAL\n");
618 for (i = 0; i < updatepkgs_filtered->count; i++)
619 printf(" - %s\n", pool_solvid2str(pool, updatepkgs_filtered->elements[i]));
624 * Find all installed packages that are no longer
625 * needed regarding the current solver job.
628 * - remove pass: remove all packages that could have
629 * been dragged in by the obsoleted packages.
630 * i.e. if package A is obsolete and contains "Requires: B",
631 * also remove B, as installing A will have pulled in B.
632 * after this pass, we have a set of still installed packages
633 * with broken dependencies.
635 * now add back all packages that the still installed packages
638 * The cleandeps packages are the packages removed in the first
639 * pass and not added back in the second pass.
641 * If we search for unneeded packages (unneeded is true), we
642 * simply remove all packages except the userinstalled ones in
646 solver_createcleandepsmap(Solver *solv, Map *cleandepsmap, int unneeded)
648 Pool *pool = solv->pool;
649 Repo *installed = solv->installed;
650 Queue *job = &solv->job;
655 Id rid, how, what, select;
657 Id req, *reqp, sup, *supp;
659 Queue iq, iqcopy, xsuppq;
660 Queue updatepkgs_filtered;
663 map_empty(cleandepsmap);
664 if (!installed || installed->end == installed->start)
666 map_init(&userinstalled, installed->end - installed->start);
667 map_init(&im, pool->nsolvables);
668 map_init(&installedm, pool->nsolvables);
672 /* setup userinstalled map and search for special namespace cleandeps erases */
673 for (i = 0; i < job->count; i += 2)
675 how = job->elements[i];
676 if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
678 what = job->elements[i + 1];
679 select = how & SOLVER_SELECTMASK;
680 if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
682 FOR_REPO_SOLVABLES(installed, p, s)
683 MAPSET(&userinstalled, p - installed->start);
685 FOR_JOB_SELECT(p, pp, select, what)
686 if (pool->solvables[p].repo == installed)
687 MAPSET(&userinstalled, p - installed->start);
689 if ((how & (SOLVER_JOBMASK | SOLVER_SELECTMASK)) == (SOLVER_ERASE | SOLVER_SOLVABLE_PROVIDES))
691 what = job->elements[i + 1];
694 Reldep *rd = GETRELDEP(pool, what);
695 if (rd->flags != REL_NAMESPACE)
699 queue_pushunique(&iq, rd->name);
702 FOR_PROVIDES(p, pp, what)
707 queue_pushunique(&iq, what);
712 /* have special namespace cleandeps erases */
715 for (ip = installed->start; ip < installed->end; ip++)
717 s = pool->solvables + ip;
718 if (s->repo != installed)
722 supp = s->repo->idarraydata + s->supplements;
723 while ((sup = *supp++) != 0)
724 if (ISRELDEP(sup) && check_xsupp(solv, &iq, sup) && !check_xsupp(solv, 0, sup))
726 #ifdef CLEANDEPSDEBUG
727 printf("xsupp %s from %s\n", pool_dep2str(pool, sup), pool_solvid2str(pool, ip));
729 queue_pushunique(&xsuppq, sup);
735 /* also add visible patterns to userinstalled for openSUSE */
739 dataiterator_init(&di, pool, 0, 0, SOLVABLE_ISVISIBLE, 0, 0);
740 while (dataiterator_step(&di))
745 s = pool->solvables + di.solvid;
746 if (!s->repo || !s->requires)
748 if (s->repo != installed && !pool_installable(pool, s))
750 if (strncmp(pool_id2str(pool, s->name), "pattern:", 8) != 0)
752 for (dp = s->repo->idarraydata + s->requires; *dp; dp++)
753 FOR_PROVIDES(p, pp, *dp)
754 if (pool->solvables[p].repo == installed)
756 if (strncmp(pool_id2str(pool, pool->solvables[p].name), "pattern", 7) != 0)
758 MAPSET(&userinstalled, p - installed->start);
761 dataiterator_free(&di);
765 /* all products and their buddies are userinstalled */
766 for (p = installed->start; p < installed->end; p++)
768 Solvable *s = pool->solvables + p;
769 if (s->repo != installed)
771 if (!strncmp("product:", pool_id2str(pool, s->name), 8))
773 MAPSET(&userinstalled, p - installed->start);
774 #ifdef ENABLE_LINKED_PKGS
775 if (solv->instbuddy && solv->instbuddy[p - installed->start] > 1)
777 Id buddy = solv->instbuddy[p - installed->start];
778 if (buddy >= installed->start && buddy < installed->end)
779 MAPSET(&userinstalled, buddy - installed->start);
786 /* add all positive elements (e.g. locks) to "userinstalled" */
787 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
789 r = solv->rules + rid;
792 i = solv->ruletojob.elements[rid - solv->jobrules];
793 if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS)
795 FOR_RULELITERALS(p, jp, r)
796 if (p > 0 && pool->solvables[p].repo == installed)
797 MAPSET(&userinstalled, p - installed->start);
800 /* add all cleandeps candidates to iq */
801 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
803 r = solv->rules + rid;
804 if (r->d < 0) /* disabled? */
806 if (r->d == 0 && r->p < 0 && r->w2 == 0) /* negative assertion (erase job)? */
809 if (pool->solvables[p].repo != installed)
811 MAPCLR(&userinstalled, p - installed->start);
814 i = solv->ruletojob.elements[rid - solv->jobrules];
815 how = job->elements[i];
816 if ((how & (SOLVER_JOBMASK|SOLVER_CLEANDEPS)) == (SOLVER_ERASE|SOLVER_CLEANDEPS))
819 else if (r->p > 0) /* install job */
823 i = solv->ruletojob.elements[rid - solv->jobrules];
824 if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS)
826 /* check if the literals all obsolete some installed package */
830 /* just one installed literal */
831 if (r->d == 0 && r->w2 == 0 && pool->solvables[r->p].repo == installed)
833 /* multiversion is bad */
834 if (solv->multiversion.size && !solv->keepexplicitobsoletes)
836 FOR_RULELITERALS(p, jp, r)
837 if (MAPTST(&solv->multiversion, p))
840 continue; /* found a multiversion package that will not obsolate anything */
845 FOR_RULELITERALS(p, jp, r)
849 queue_truncate(&iq, iqstart); /* abort */
852 if (pool->solvables[p].repo == installed)
854 if (iq.count == iqstart)
858 for (i = iqstart; i < iq.count; i++)
859 if (iq.elements[i] == p)
861 queue_truncate(&iq, iqstart);
867 solver_intersect_obsoleted(solv, p, &iq, iqstart, &om);
868 if (iq.count == iqstart)
876 queue_init_clone(&iqcopy, &iq);
879 queue_empty(&iq); /* just in case... */
881 /* clear userinstalled bits for the packages we really want to delete */
882 for (i = 0; i < iq.count; i++)
885 if (pool->solvables[p].repo == installed)
886 MAPCLR(&userinstalled, p - installed->start);
888 /* set userinstalled bits for all packages not in the considered map */
889 if (pool->considered)
891 for (p = installed->start; p < installed->end; p++)
892 if (!MAPTST(pool->considered, p))
893 MAPSET(&userinstalled, p - installed->start); /* we may not remove those */
895 if (!unneeded && solv->cleandeps_updatepkgs)
897 /* find update seeds */
898 queue_init(&updatepkgs_filtered);
899 find_update_seeds(solv, &updatepkgs_filtered, &userinstalled);
900 /* clear userinstalled bit for the packages we want to update */
901 /* also add them to the erase list */
902 for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
904 p = solv->cleandeps_updatepkgs->elements[i];
905 if (pool->considered && !MAPTST(pool->considered, p))
908 MAPCLR(&userinstalled, p - installed->start);
912 for (p = installed->start; p < installed->end; p++)
914 if (pool->solvables[p].repo != installed)
916 MAPSET(&installedm, p);
917 if (unneeded && !MAPTST(&userinstalled, p - installed->start))
921 MAPSET(&installedm, SYSTEMSOLVABLE);
922 MAPSET(&im, SYSTEMSOLVABLE);
924 #ifdef CLEANDEPSDEBUG
925 printf("REMOVE PASS\n");
934 /* supplements pass */
935 for (ip = installed->start; ip < installed->end; ip++)
937 if (!MAPTST(&installedm, ip))
939 s = pool->solvables + ip;
942 if (!MAPTST(&im, ip))
944 if (MAPTST(&userinstalled, ip - installed->start))
946 supp = s->repo->idarraydata + s->supplements;
947 while ((sup = *supp++) != 0)
948 if (solver_dep_possible(solv, sup, &im))
952 supp = s->repo->idarraydata + s->supplements;
953 while ((sup = *supp++) != 0)
954 if (solver_dep_possible(solv, sup, &installedm) || (xsuppq.count && queue_contains(&xsuppq, sup)))
956 /* no longer supplemented, also erase */
957 int iqcount = iq.count;
958 /* pin packages, see comment above dep_pkgcheck */
959 dep_pkgcheck(solv, sup, &im, &iq);
960 for (i = iqcount; i < iq.count; i++)
962 Id pqp = iq.elements[i];
963 if (pool->solvables[pqp].repo == installed)
964 MAPSET(&userinstalled, pqp - installed->start);
966 queue_truncate(&iq, iqcount);
967 #ifdef CLEANDEPSDEBUG
968 printf("%s supplemented [%s]\n", pool_solvid2str(pool, ip), pool_dep2str(pool, sup));
975 break; /* no supplementing package found, we're done */
977 ip = queue_shift(&iq);
978 s = pool->solvables + ip;
979 if (!MAPTST(&im, ip))
981 if (!MAPTST(&installedm, ip))
983 if (s->repo == installed && MAPTST(&userinstalled, ip - installed->start))
986 #ifdef CLEANDEPSDEBUG
987 printf("removing %s\n", pool_solvable2str(pool, s));
991 reqp = s->repo->idarraydata + s->requires;
992 while ((req = *reqp++) != 0)
994 if (req == SOLVABLE_PREREQMARKER)
996 #ifdef ENABLE_COMPLEX_DEPS
997 if (pool_is_complex_dep(pool, req))
999 complex_cleandeps_remove(pool, ip, req, &im, &installedm, &iq);
1003 FOR_PROVIDES(p, pp, req)
1005 if (p != SYSTEMSOLVABLE && MAPTST(&im, p))
1007 #ifdef CLEANDEPSDEBUG
1008 printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
1017 reqp = s->repo->idarraydata + s->recommends;
1018 while ((req = *reqp++) != 0)
1020 #ifdef ENABLE_COMPLEX_DEPS
1021 if (pool_is_complex_dep(pool, req))
1023 complex_cleandeps_remove(pool, ip, req, &im, &installedm, &iq);
1027 FOR_PROVIDES(p, pp, req)
1029 if (p != SYSTEMSOLVABLE && MAPTST(&im, p))
1031 #ifdef CLEANDEPSDEBUG
1032 printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
1041 /* turn userinstalled into remove set for pruning */
1042 map_empty(&userinstalled);
1043 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
1045 r = solv->rules + rid;
1046 if (r->p >= 0 || r->d != 0 || r->w2 != 0)
1047 continue; /* disabled or not erase */
1050 if (pool->solvables[p].repo == installed)
1051 MAPSET(&userinstalled, p - installed->start);
1053 if (!unneeded && solv->cleandeps_updatepkgs)
1055 for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
1057 p = solv->cleandeps_updatepkgs->elements[i];
1058 if (pool->solvables[p].repo == installed)
1059 MAPSET(&userinstalled, p - installed->start);
1062 MAPSET(&im, SYSTEMSOLVABLE); /* in case we cleared it above */
1063 for (p = installed->start; p < installed->end; p++)
1066 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
1068 r = solv->rules + rid;
1071 FOR_RULELITERALS(p, jp, r)
1075 /* also put directly addressed packages on the install queue
1076 * so we can mark patterns as installed */
1077 for (i = 0; i < job->count; i += 2)
1079 how = job->elements[i];
1080 if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
1082 what = job->elements[i + 1];
1083 select = how & SOLVER_SELECTMASK;
1084 if (select == SOLVER_SOLVABLE && pool->solvables[what].repo != installed)
1085 queue_push(&iq, what);
1089 #ifdef CLEANDEPSDEBUG
1090 printf("ADDBACK PASS\n");
1096 /* supplements pass */
1097 for (ip = installed->start; ip < installed->end; ip++)
1099 if (!MAPTST(&installedm, ip))
1101 if (MAPTST(&userinstalled, ip - installed->start))
1103 s = pool->solvables + ip;
1104 if (!s->supplements)
1106 if (MAPTST(&im, ip))
1108 supp = s->repo->idarraydata + s->supplements;
1109 while ((sup = *supp++) != 0)
1110 if (solver_dep_possible(solv, sup, &im))
1114 #ifdef CLEANDEPSDEBUG
1115 printf("%s supplemented\n", pool_solvid2str(pool, ip));
1118 queue_push(&iq, ip);
1124 ip = queue_shift(&iq);
1125 s = pool->solvables + ip;
1126 #ifdef CLEANDEPSDEBUG
1127 printf("adding back %s\n", pool_solvable2str(pool, s));
1129 if (s->repo == installed && pool->implicitobsoleteusescolors)
1131 unsigned int a, bestscore = 0;
1132 FOR_PROVIDES(p, pp, s->name)
1134 Solvable *ps = pool->solvables + p;
1135 if (ps->name != s->name || ps->repo == installed)
1137 a = pool_arch2score(pool, ps->arch);
1138 if (a && a != 1 && (!bestscore || a < bestscore))
1141 if (bestscore && pool_arch2score(pool, s->arch) != bestscore)
1143 FOR_PROVIDES(p, pp, s->name)
1145 Solvable *ps = pool->solvables + p;
1146 if (ps->repo == installed && ps->name == s->name && ps->evr == s->evr && ps->arch != s->arch && pool_arch2score(pool, ps->arch) == bestscore)
1147 if (!MAPTST(&im, p))
1149 #ifdef CLEANDEPSDEBUG
1150 printf("%s lockstep %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
1160 reqp = s->repo->idarraydata + s->requires;
1161 while ((req = *reqp++) != 0)
1163 #ifdef ENABLE_COMPLEX_DEPS
1164 if (pool_is_complex_dep(pool, req))
1166 complex_cleandeps_addback(pool, ip, req, &im, &installedm, &iq, &userinstalled);
1170 FOR_PROVIDES(p, pp, req)
1175 FOR_PROVIDES(p, pp, req)
1179 if (MAPTST(&installedm, p))
1183 if (MAPTST(&userinstalled, p - installed->start))
1185 #ifdef CLEANDEPSDEBUG
1186 printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
1196 reqp = s->repo->idarraydata + s->recommends;
1197 while ((req = *reqp++) != 0)
1199 #ifdef ENABLE_COMPLEX_DEPS
1200 if (pool_is_complex_dep(pool, req))
1202 complex_cleandeps_addback(pool, ip, req, &im, &installedm, &iq, &userinstalled);
1206 FOR_PROVIDES(p, pp, req)
1211 FOR_PROVIDES(p, pp, req)
1215 if (MAPTST(&installedm, p))
1219 if (MAPTST(&userinstalled, p - installed->start))
1221 #ifdef CLEANDEPSDEBUG
1222 printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
1233 /* make sure the updatepkgs and mistakes are not in the cleandeps map */
1234 if (!unneeded && solv->cleandeps_updatepkgs)
1236 for (i = 0; i < updatepkgs_filtered.count; i++)
1237 MAPSET(&im, updatepkgs_filtered.elements[i]);
1238 queue_free(&updatepkgs_filtered);
1240 if (solv->cleandeps_mistakes)
1241 for (i = 0; i < solv->cleandeps_mistakes->count; i++)
1242 MAPSET(&im, solv->cleandeps_mistakes->elements[i]);
1243 /* also remove original iq packages */
1244 for (i = 0; i < iqcopy.count; i++)
1245 MAPSET(&im, iqcopy.elements[i]);
1246 queue_free(&iqcopy);
1247 for (p = installed->start; p < installed->end; p++)
1249 if (pool->solvables[p].repo != installed)
1251 if (pool->considered && !MAPTST(pool->considered, p))
1253 if (!MAPTST(&im, p))
1254 MAPSET(cleandepsmap, p - installed->start);
1257 map_free(&installedm);
1258 map_free(&userinstalled);
1259 queue_free(&xsuppq);
1260 #ifdef CLEANDEPSDEBUG
1261 printf("=== final cleandeps map:\n");
1262 for (p = installed->start; p < installed->end; p++)
1263 if (MAPTST(cleandepsmap, p - installed->start))
1264 printf(" - %s\n", pool_solvid2str(pool, p));
1269 solver_get_unneeded(Solver *solv, Queue *unneededq, int filtered)
1271 Repo *installed = solv->installed;
1275 queue_empty(unneededq);
1276 if (!installed || installed->end == installed->start)
1279 map_init(&cleandepsmap, installed->end - installed->start);
1280 solver_createcleandepsmap(solv, &cleandepsmap, 1);
1281 for (i = installed->start; i < installed->end; i++)
1282 if (MAPTST(&cleandepsmap, i - installed->start))
1283 queue_push(unneededq, i);
1286 filter_unneeded(solv, unneededq, &cleandepsmap, 0);
1287 map_free(&cleandepsmap);
1291 add_cleandeps_mistake(Solver *solv, Id p)
1293 if (!solv->cleandeps_mistakes)
1295 solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue));
1296 queue_init(solv->cleandeps_mistakes);
1298 queue_push(solv->cleandeps_mistakes, p);
1299 MAPCLR(&solv->cleandepsmap, p - solv->installed->start);
1300 solver_reenablepolicyrules_cleandeps(solv, p);
1304 cleandeps_rule_is_true(Solver *solv, Rule *r)
1306 Pool *pool = solv->pool;
1308 FOR_RULELITERALS(p, pp, r)
1309 if (p > 0 && solv->decisionmap[p] > 0)
1315 solver_check_cleandeps_mistakes(Solver *solv)
1317 Pool *pool = solv->pool;
1318 Repo *installed = solv->installed;
1321 int mademistake = 0;
1323 if (!solv->cleandepsmap.size || !installed)
1325 /* check for mistakes */
1326 policy_update_recommendsmap(solv);
1327 for (i = installed->start; i < installed->end; i++)
1329 if (pool->solvables[i].repo != installed)
1331 if (solv->decisionmap[i] > 0)
1334 Solvable *s = pool->solvables + i;
1335 /* kept package, check requires. we need to do this for things like requires(pre) */
1336 reqp = s->repo->idarraydata + s->requires;
1337 while ((req = *reqp++) != 0)
1340 FOR_PROVIDES(p2, pp2, req)
1342 if (pool->solvables[p2].repo != installed)
1344 if (p2 == i || solv->decisionmap[p2] > 0)
1346 if (!MAPTST(&solv->cleandepsmap, p2 - installed->start))
1348 POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps requires mistake: %s %s %s\n", pool_solvid2str(pool, i), pool_dep2str(pool, req), pool_solvid2str(pool, p2));
1349 add_cleandeps_mistake(solv, p2);
1354 if (!MAPTST(&solv->cleandepsmap, i - installed->start))
1356 /* a mistake is when the featurerule is true but the updaterule is false */
1357 fr = solv->rules + solv->featurerules + (i - installed->start);
1359 fr = solv->rules + solv->updaterules + (i - installed->start);
1362 if (!cleandeps_rule_is_true(solv, fr))
1364 /* feature rule is not true, thus we cleandeps erased the package */
1365 /* check if the package is recommended/supplemented. if yes, we made a mistake. */
1366 if (!MAPTST(&solv->recommendsmap, i) && !solver_is_supplementing(solv, pool->solvables + i))
1367 continue; /* feature rule is not true */
1368 POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps recommends mistake: ");
1369 solver_printruleclass(solv, SOLV_DEBUG_SOLVER, fr);
1373 Rule *r = solv->rules + solv->updaterules + (i - installed->start);
1374 if (!r->p || r == fr || cleandeps_rule_is_true(solv, r))
1376 /* update rule is true, check best rules */
1377 if (!solv->bestrules_info)
1379 nj = solv->bestrules_end - solv->bestrules;
1380 for (j = solv->bestrules_up - solv->bestrules; j < nj; j++)
1381 if (solv->bestrules_info[j] == i)
1383 r = solv->rules + solv->bestrules + j;
1384 if (!cleandeps_rule_is_true(solv, r))
1390 POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: ");
1391 solver_printruleclass(solv, SOLV_DEBUG_SOLVER, r);
1392 POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: ");
1393 solver_printruleclass(solv, SOLV_DEBUG_SOLVER, fr);
1395 add_cleandeps_mistake(solv, i);