2 * Copyright (c) 2017, SUSE Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
11 * Dependency solver helper functions
20 #include "solver_private.h"
28 /*-------------------------------------------------------------------
29 * check if a installed package p is being updated
32 solver_is_updating(Solver *solv, Id p)
34 /* check if the update rule is true */
35 Pool *pool = solv->pool;
38 if (solv->decisionmap[p] >= 0)
39 return 0; /* old package stayed */
40 r = solv->rules + solv->featurerules + (p - solv->installed->start);
42 r = solv->rules + solv->updaterules + (p - solv->installed->start);
43 FOR_RULELITERALS(l, pp, r)
44 if (l > 0 && l != p && solv->decisionmap[l] > 0)
46 /* check that this is really an upgrade */
47 Solvable *si = pool->solvables + p;
48 Solvable *s = pool->solvables + l;
49 if (s->name != si->name || pool_evrcmp(pool, s->evr, si->evr, EVRCMP_COMPARE) > 0)
55 /*-------------------------------------------------------------------
56 * handle split provides
58 * a splitprovides dep looks like
59 * namespace:splitprovides(pkg REL_WITH path)
60 * and is only true if pkg is installed and contains the specified path.
61 * we also make sure that pkg is selected for an update, otherwise the
62 * update would always be forced onto the user.
63 * Map m is the map used when called from dep_possible.
66 solver_splitprovides(Solver *solv, Id dep, Map *m)
68 Pool *pool = solv->pool;
73 if (!solv->dosplitprovides || !solv->installed)
77 rd = GETRELDEP(pool, dep);
78 if (rd->flags != REL_WITH)
81 * things are a bit tricky here if pool->addedprovides == 1, because most split-provides are in
82 * a non-standard location. If we simply call pool_whatprovides, we'll drag in the complete
83 * file list. Instead we rely on pool_addfileprovides ignoring the addfileprovidesfiltered flag
84 * for installed packages and check the lazywhatprovidesq (ignoring the REL_WITH part, but
85 * we filter the package name further down anyway).
87 if (pool->addedfileprovides == 1 && !ISRELDEP(rd->evr) && !pool->whatprovides[rd->evr])
88 pp = pool_searchlazywhatprovidesq(pool, rd->evr);
90 pp = pool_whatprovides(pool, dep);
91 while ((p = pool->whatprovidesdata[pp++]) != 0)
93 /* here we have packages that provide the correct name and contain the path,
94 * now do extra filtering */
95 s = pool->solvables + p;
96 if (s->repo != solv->installed || s->name != rd->name)
98 /* check if the package is updated. if m is set, we're called from dep_possible */
99 if (m || solver_is_updating(solv, p))
106 solver_dep_possible_slow(Solver *solv, Id dep, Map *m)
108 Pool *pool = solv->pool;
113 Reldep *rd = GETRELDEP(pool, dep);
116 if (rd->flags == REL_COND || rd->flags == REL_UNLESS)
118 if (rd->flags == REL_AND)
120 if (!solver_dep_possible_slow(solv, rd->name, m))
122 return solver_dep_possible_slow(solv, rd->evr, m);
124 if (rd->flags == REL_OR)
126 if (solver_dep_possible_slow(solv, rd->name, m))
128 return solver_dep_possible_slow(solv, rd->evr, m);
130 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
131 return solver_splitprovides(solv, rd->evr, m);
134 FOR_PROVIDES(p, pp, dep)
143 solver_dep_fulfilled_cplx(Solver *solv, Reldep *rd)
145 Pool *pool = solv->pool;
146 if (rd->flags == REL_COND)
148 if (ISRELDEP(rd->evr))
150 Reldep *rd2 = GETRELDEP(pool, rd->evr);
151 if (rd2->flags == REL_ELSE)
153 if (solver_dep_fulfilled(solv, rd2->name))
154 return solver_dep_fulfilled(solv, rd->name);
155 return solver_dep_fulfilled(solv, rd2->evr);
158 if (solver_dep_fulfilled(solv, rd->name))
160 return !solver_dep_fulfilled(solv, rd->evr);
162 if (rd->flags == REL_UNLESS)
164 if (ISRELDEP(rd->evr))
166 Reldep *rd2 = GETRELDEP(pool, rd->evr);
167 if (rd2->flags == REL_ELSE)
169 if (!solver_dep_fulfilled(solv, rd2->name))
170 return solver_dep_fulfilled(solv, rd->name);
171 return solver_dep_fulfilled(solv, rd2->evr);
174 if (!solver_dep_fulfilled(solv, rd->name))
176 return !solver_dep_fulfilled(solv, rd->evr);
178 if (rd->flags == REL_AND)
180 if (!solver_dep_fulfilled(solv, rd->name))
182 return solver_dep_fulfilled(solv, rd->evr);
184 if (rd->flags == REL_OR)
186 if (solver_dep_fulfilled(solv, rd->name))
188 return solver_dep_fulfilled(solv, rd->evr);
194 solver_dep_fulfilled_complex_func(Solver *solv, Reldep *rd, int (*dep_fullfilled)(Solver *, Id))
196 Pool *pool = solv->pool;
198 if (rd->flags == REL_COND)
200 if (ISRELDEP(rd->evr))
202 Reldep *rd2 = GETRELDEP(pool, rd->evr);
203 if (rd2->flags == REL_ELSE)
205 r1 = dep_fullfilled(solv, rd2->name);
208 r2 = dep_fullfilled(solv, rd->name);
209 return r2 && r1 == 2 ? 2 : r2;
211 return dep_fullfilled(solv, rd2->evr);
214 r1 = dep_fullfilled(solv, rd->name);
215 r2 = !dep_fullfilled(solv, rd->evr);
218 return r1 == 2 ? 2 : 1;
220 if (rd->flags == REL_UNLESS)
222 if (ISRELDEP(rd->evr))
224 Reldep *rd2 = GETRELDEP(pool, rd->evr);
225 if (rd2->flags == REL_ELSE)
227 r1 = dep_fullfilled(solv, rd2->name);
230 r2 = dep_fullfilled(solv, rd2->evr);
231 return r2 && r1 == 2 ? 2 : r2;
233 return dep_fullfilled(solv, rd->name);
237 r1 = dep_fullfilled(solv, rd->name);
238 r2 = !dep_fullfilled(solv, rd->evr);
241 return r1 == 2 ? 2 : 1;
243 if (rd->flags == REL_AND)
245 r1 = dep_fullfilled(solv, rd->name);
248 r2 = dep_fullfilled(solv, rd->evr);
251 return r1 == 2 || r2 == 2 ? 2 : 1;
253 if (rd->flags == REL_OR)
255 r1 = dep_fullfilled(solv, rd->name);
256 r2 = dep_fullfilled(solv, rd->evr);
259 return r1 == 2 || r2 == 2 ? 2 : 1;
264 /* mirrors solver_dep_fulfilled, but returns 2 if a new package
267 solver_dep_fulfilled_alreadyinstalled(Solver *solv, Id dep)
269 Pool *pool = solv->pool;
275 Reldep *rd = GETRELDEP(pool, dep);
276 if (rd->flags == REL_COND || rd->flags == REL_UNLESS || rd->flags == REL_AND || rd->flags == REL_OR)
277 return solver_dep_fulfilled_complex_func(solv, rd, solver_dep_fulfilled_alreadyinstalled);
278 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
279 return solver_splitprovides(solv, rd->evr, 0) ? 2 : 0;
280 if (rd->flags == REL_NAMESPACE && solv->installsuppdepq)
282 Queue *q = solv->installsuppdepq;
284 for (i = 0; i < q->count; i++)
285 if (q->elements[i] == dep || q->elements[i] == rd->name)
290 FOR_PROVIDES(p, pp, dep)
291 if (solv->decisionmap[p] > 0)
293 Solvable *s = pool->solvables + p;
294 if (s->repo && s->repo != solv->installed)
302 solver_dep_fulfilled_namespace(Solver *solv, Id dep)
304 Pool *pool = solv->pool;
310 Reldep *rd = GETRELDEP(pool, dep);
311 if (rd->flags == REL_COND || rd->flags == REL_UNLESS || rd->flags == REL_AND || rd->flags == REL_OR)
312 return solver_dep_fulfilled_complex_func(solv, rd, solver_dep_fulfilled_namespace);
313 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
314 return solver_splitprovides(solv, rd->evr, 0) ? 2 : 0;
315 if (rd->flags == REL_NAMESPACE)
318 FOR_PROVIDES(p, pp, dep)
319 if (solv->decisionmap[p] > 0)
325 solver_is_supplementing_alreadyinstalled(Solver *solv, Solvable *s)
328 supp = s->repo->idarraydata + s->supplements;
329 while ((sup = *supp++) != 0)
331 if (!solv->addalreadyrecommended && solver_dep_fulfilled_alreadyinstalled(solv, sup) != 2)
333 if (solv->only_namespace_recommended && solver_dep_fulfilled_namespace(solv, sup) != 2)
341 solver_is_namespace_dep_slow(Solver *solv, Reldep *rd)
343 Pool *pool = solv->pool;
346 if (rd->flags == REL_NAMESPACE)
348 if (ISRELDEP(rd->name) && solver_is_namespace_dep_slow(solv, GETRELDEP(pool, rd->name)))
350 if (!ISRELDEP(rd->evr))
352 rd = GETRELDEP(pool, rd->evr);
357 * add all installed packages that package p obsoletes to Queue q.
358 * Package p is not installed. Also, we know that if
359 * solv->keepexplicitobsoletes is not set, p is not in the multiversion map.
360 * Entries may get added multiple times.
363 solver_add_obsoleted(Solver *solv, Id p, Queue *q)
365 Pool *pool = solv->pool;
366 Repo *installed = solv->installed;
368 Solvable *s = pool->solvables + p;
372 if (!solv->keepexplicitobsoletes || !(solv->multiversion.size && MAPTST(&solv->multiversion, p)))
374 FOR_PROVIDES(p2, pp2, s->name)
376 Solvable *ps = pool->solvables + p2;
377 if (ps->repo != installed)
379 if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
381 if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
389 obsp = s->repo->idarraydata + s->obsoletes;
390 while ((obs = *obsp++) != 0)
391 FOR_PROVIDES(p2, pp2, obs)
393 Solvable *ps = pool->solvables + p2;
394 if (ps->repo != installed)
396 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
398 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
408 * Call solver_add_obsoleted and intersect the result with the
409 * elements in Queue q starting at qstart.
410 * Assumes that it's the first call if qstart == q->count.
411 * May use auxillary map m for the intersection process, all
412 * elements of q starting at qstart must have their bit cleared.
413 * (This is also true after the function returns.)
414 * (See solver_add_obsoleted for limitations of the package p)
417 solver_intersect_obsoleted(Solver *solv, Id p, Queue *q, int qstart, Map *m)
420 int qcount = q->count;
422 solver_add_obsoleted(solv, p, q);
423 if (qcount == qstart)
424 return; /* first call */
425 if (qcount == q->count)
427 else if (qcount == qstart + 1)
429 /* easy if there's just one element */
431 for (i = qcount; i < q->count; i++)
432 if (q->elements[i] == q->elements[qstart])
434 j++; /* keep the element */
438 else if (!m || (!m->size && q->count - qstart <= 8))
440 /* faster than a map most of the time */
442 for (i = j = qstart; i < qcount; i++)
444 Id ip = q->elements[i];
445 for (k = qcount; k < q->count; k++)
446 if (q->elements[k] == ip)
448 q->elements[j++] = ip;
455 /* for the really pathologic cases we use the map */
456 Repo *installed = solv->installed;
458 map_init(m, installed->end - installed->start);
459 for (i = qcount; i < q->count; i++)
460 MAPSET(m, q->elements[i] - installed->start);
461 for (i = j = qstart; i < qcount; i++)
462 if (MAPTST(m, q->elements[i] - installed->start))
464 MAPCLR(m, q->elements[i] - installed->start);
465 q->elements[j++] = q->elements[i];
468 queue_truncate(q, j);