2 * Copyright (c) 2007, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
13 #ifndef SATSOLVER_SOLVER_H
14 #define SATSOLVER_SOLVER_H
20 #include "pooltypes.h"
26 * Callback definitions in order to "overwrite" the policies by an external application.
29 typedef void (*BestSolvableCb) (Pool *pool, Queue *canditates);
30 typedef int (*ArchCheckCb) (Pool *pool, Solvable *solvable1, Solvable *solvable2);
31 typedef int (*VendorCheckCb) (Pool *pool, Solvable *solvable1, Solvable *solvable2);
32 typedef void (*UpdateCandidateCb) (Pool *pool, Solvable *solvable, Queue *canditates);
35 /* ----------------------------------------------
38 * providerN(B) == Package Id of package providing tag B
39 * N = 1, 2, 3, in case of multiple providers
41 * A requires B : !A | provider1(B) | provider2(B)
43 * A conflicts B : (!A | !provider1(B)) & (!A | !provider2(B)) ...
45 * 'not' is encoded as a negative Id
47 * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
51 Id p; /* first literal in rule */
52 Id d; /* Id offset into 'list of providers terminated by 0' as used by whatprovides; pool->whatprovides + d */
53 /* in case of binary rules, d == 0, w1 == p, w2 == other literal */
54 /* in case of disabled rules: ~d, aka -d - 1 */
55 Id w1, w2; /* watches, literals not-yet-decided */
56 /* if !w2, assertion, not rule */
57 Id n1, n2; /* next rules in linked list, corresponding to w1,w2 */
62 typedef struct solver {
66 /* list of rules, ordered
67 * rpm rules first, then features, updates, jobs, learnt
68 * see start/end offsets below
70 Rule *rules; /* all rules */
71 Id nrules; /* [Offset] index of the last rule */
73 Queue ruleassertions; /* Queue of all assertion rules */
75 /* start/end offset for rule 'areas' */
77 Id rpmrules_end; /* [Offset] rpm rules end */
79 Id featurerules; /* feature rules start/end */
82 Id updaterules; /* policy rules, e.g. keep packages installed or update. All literals > 0 */
85 Id jobrules; /* user rules */
88 Id learntrules; /* learnt rules, (end == nrules) */
90 Map noupdate; /* don't try to update these
91 installed solvables */
92 Map noobsoletes; /* ignore obsoletes for these
95 Queue weakruleq; /* index into 'rules' for weak ones */
96 Map weakrulemap; /* map rule# to '1' for weak rules, 1..learntrules */
98 Id *watches; /* Array of rule offsets
99 * watches has nsolvables*2 entries and is addressed from the middle
100 * middle-solvable : decision to conflict, offset point to linked-list of rules
101 * middle+solvable : decision to install: offset point to linked-list of rules
104 Queue ruletojob; /* index into job queue: jobs for which a rule exits */
107 Queue decisionq; /* >0:install, <0:remove/conflict */
108 Queue decisionq_why; /* index of rule, Offset into rules */
109 int directdecisions; /* number of decisions with no rule */
111 Id *decisionmap; /* map for all available solvables,
113 * > 0: level of decision when installed,
114 * < 0: level of decision when conflict */
116 /* learnt rule history */
121 int (*solution_callback)(struct solver *solv, void *data);
122 void *solution_callback_data;
124 int propagate_index; /* index into decisionq for non-propagated decisions */
126 Queue problems; /* index of conflicting rules, < 0 for job rules */
127 Queue recommendations; /* recommended packages */
128 Queue suggestions; /* suggested packages */
129 Queue orphaned; /* orphaned packages */
131 int stats_learned; /* statistic */
132 int stats_unsolvable; /* statistic */
134 Map recommendsmap; /* recommended packages from decisionmap */
135 Map suggestsmap; /* suggested packages from decisionmap */
136 int recommends_index; /* recommendsmap/suggestsmap is created up to this level */
138 Id *obsoletes; /* obsoletes for each installed solvable */
139 Id *obsoletes_data; /* data area for obsoletes */
140 Id *multiversionupdaters; /* updaters for multiversion packages in updatesystem mode */
142 /*-------------------------------------------------------------------------------------------------------------
143 * Solver configuration
144 *-------------------------------------------------------------------------------------------------------------*/
146 int fixsystem; /* repair errors in rpm dependency graph */
147 int allowdowngrade; /* allow to downgrade installed solvable */
148 int allowarchchange; /* allow to change architecture of installed solvables */
149 int allowvendorchange; /* allow to change vendor of installed solvables */
150 int allowuninstall; /* allow removal of installed solvables */
151 int updatesystem; /* distupgrade */
152 int allowvirtualconflicts; /* false: conflicts on package name, true: conflicts on package provides */
153 int allowselfconflicts; /* true: packages wich conflict with itself are installable */
154 int obsoleteusesprovides; /* true: obsoletes are matched against provides, not names */
155 int implicitobsoleteusesprovides; /* true: implicit obsoletes due to same name are matched against provides, not names */
156 int noupdateprovide; /* true: update packages needs not to provide old package */
157 int dosplitprovides; /* true: consider legacy split provides */
158 int dontinstallrecommended; /* true: do not install recommended packages */
159 int ignorealreadyrecommended; /* true: ignore recommended packages that were already recommended by the installed packages */
160 int dontshowinstalledrecommended; /* true: do not show recommended packages that are already installed */
162 /* distupgrade also needs updatesystem and dosplitprovides */
164 int distupgrade_removeunsupported;
166 /* Callbacks for defining the bahaviour of the SAT solver */
168 /* Finding best candidate
170 * Callback definition:
171 * void bestSolvable (Pool *pool, Queue *canditates)
172 * candidates : List of canditates which has to be sorted by the function call
173 * return candidates: Sorted list of the candidates(first is the best).
175 BestSolvableCb bestSolvableCb;
177 /* Checking if two solvables has compatible architectures
179 * Callback definition:
180 * int archCheck (Pool *pool, Solvable *solvable1, Solvable *solvable2);
182 * return 0 it the two solvables has compatible architectures
184 ArchCheckCb archCheckCb;
186 /* Checking if two solvables has compatible vendors
188 * Callback definition:
189 * int vendorCheck (Pool *pool, Solvable *solvable1, Solvable *solvable2);
191 * return 0 it the two solvables has compatible architectures
193 VendorCheckCb vendorCheckCb;
195 /* Evaluate update candidate
197 * Callback definition:
198 * void pdateCandidateCb (Pool *pool, Solvable *solvable, Queue *canditates)
199 * solvable : for which updates should be search
200 * candidates : List of candidates (This list depends on other
201 * restrictions like architecture and vendor policies too)
203 UpdateCandidateCb updateCandidateCb;
206 /* some strange queue that doesn't belong here */
207 Queue covenantq; /* Covenants honored by this solver (generic locks) */
210 Queue *job; /* tmp store for job we're working on */
211 Id infarchrules; /* inferior arch rules */
213 Id duprules; /* dist upgrade rules */
215 Map updatemap; /* bring those packages to the newest version */
216 Map dupmap; /* packages from dup repos */
217 Map dupinvolvedmap; /* packages involved in dup process */
224 #define SOLVER_SOLVABLE 0x01
225 #define SOLVER_SOLVABLE_NAME 0x02
226 #define SOLVER_SOLVABLE_PROVIDES 0x03
227 #define SOLVER_SOLVABLE_ONE_OF 0x04
229 #define SOLVER_SELECTMASK 0xff
231 #define SOLVER_INSTALL 0x0100
232 #define SOLVER_ERASE 0x0200
233 #define SOLVER_UPDATE 0x0300
234 #define SOLVER_WEAKENDEPS 0x0400
235 #define SOLVER_NOOBSOLETES 0x0500
236 #define SOLVER_LOCK 0x0600
237 #define SOLVER_DISTUPGRADE 0x0700
239 #define SOLVER_JOBMASK 0xff00
241 #define SOLVER_WEAK 0x010000
242 #define SOLVER_ESSENTIAL 0x020000
244 /* old API compatibility, do not use in new code */
246 #define SOLVER_INSTALL_SOLVABLE (SOLVER_INSTALL|SOLVER_SOLVABLE)
247 #define SOLVER_ERASE_SOLVABLE (SOLVER_ERASE|SOLVER_SOLVABLE)
248 #define SOLVER_INSTALL_SOLVABLE_NAME (SOLVER_INSTALL|SOLVER_SOLVABLE_NAME)
249 #define SOLVER_ERASE_SOLVABLE_NAME (SOLVER_ERASE|SOLVER_SOLVABLE_NAME)
250 #define SOLVER_INSTALL_SOLVABLE_PROVIDES (SOLVER_INSTALL|SOLVER_SOLVABLE_PROVIDES)
251 #define SOLVER_ERASE_SOLVABLE_PROVIDES (SOLVER_ERASE|SOLVER_SOLVABLE_PROVIDES)
252 #define SOLVER_INSTALL_SOLVABLE_UPDATE (SOLVER_UPDATE|SOLVER_SOLVABLE)
253 #define SOLVER_INSTALL_SOLVABLE_ONE_OF (SOLVER_INSTALL|SOLVER_SOLVABLE_ONE_OF)
254 #define SOLVER_WEAKEN_SOLVABLE_DEPS (SOLVER_WEAKENDEPS|SOLVER_SOLVABLE)
255 #define SOLVER_NOOBSOLETES_SOLVABLE (SOLVER_NOOBSOLETES|SOLVER_SOLVABLE)
256 #define SOLVER_NOOBSOLETES_SOLVABLE_NAME (SOLVER_NOOBSOLETES|SOLVER_SOLVABLE_NAME)
257 #define SOLVER_NOOBSOLETES_SOLVABLE_PROVIDES (SOLVER_NOOBSOLETES|SOLVER_SOLVABLE_PROVIDES)
261 SOLVER_PROBLEM_UPDATE_RULE,
262 SOLVER_PROBLEM_JOB_RULE,
263 SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP,
264 SOLVER_PROBLEM_NOT_INSTALLABLE,
265 SOLVER_PROBLEM_NOTHING_PROVIDES_DEP,
266 SOLVER_PROBLEM_SAME_NAME,
267 SOLVER_PROBLEM_PACKAGE_CONFLICT,
268 SOLVER_PROBLEM_PACKAGE_OBSOLETES,
269 SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE,
270 SOLVER_PROBLEM_SELF_CONFLICT,
271 SOLVER_PROBLEM_RPM_RULE,
272 SOLVER_PROBLEM_DISTUPGRADE_RULE,
273 SOLVER_PROBLEM_INFARCH_RULE
276 #define SOLVER_SOLUTION_JOB (0)
277 #define SOLVER_SOLUTION_DISTUPGRADE (-1)
278 #define SOLVER_SOLUTION_INFARCH (-2)
280 extern Solver *solver_create(Pool *pool);
281 extern void solver_free(Solver *solv);
282 extern void solver_solve(Solver *solv, Queue *job);
283 extern int solver_dep_installed(Solver *solv, Id dep);
284 extern int solver_splitprovides(Solver *solv, Id dep);
286 extern Id solver_next_problem(Solver *solv, Id problem);
287 extern Id solver_next_solution(Solver *solv, Id problem, Id solution);
288 extern Id solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp);
289 extern Id solver_findproblemrule(Solver *solv, Id problem);
290 extern void solver_findallproblemrules(Solver *solv, Id problem, Queue *rules);
292 extern SolverProbleminfo solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp);
294 /* XXX: why is this not static? */
295 Id *solver_create_decisions_obsoletesmap(Solver *solv);
298 solver_dep_fulfilled(Solver *solv, Id dep)
300 Pool *pool = solv->pool;
305 Reldep *rd = GETRELDEP(pool, dep);
306 if (rd->flags == REL_AND)
308 if (!solver_dep_fulfilled(solv, rd->name))
310 return solver_dep_fulfilled(solv, rd->evr);
312 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
313 return solver_splitprovides(solv, rd->evr);
314 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
315 return solver_dep_installed(solv, rd->evr);
317 FOR_PROVIDES(p, pp, dep)
319 if (solv->decisionmap[p] > 0)
326 solver_is_supplementing(Solver *solv, Solvable *s)
331 supp = s->repo->idarraydata + s->supplements;
332 while ((sup = *supp++) != 0)
333 if (solver_dep_fulfilled(solv, sup))
339 solver_is_enhancing(Solver *solv, Solvable *s)
344 enhp = s->repo->idarraydata + s->enhances;
345 while ((enh = *enhp++) != 0)
346 if (solver_dep_fulfilled(solv, enh))
351 void solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps);
352 int solver_calc_installsizechange(Solver *solv);
354 void solver_find_involved(Solver *solv, Queue *installedq, Solvable *s, Queue *q);
357 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
359 pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
362 /* iterate over all literals of a rule */
363 /* WARNING: loop body must not relocate whatprovidesdata, e.g. by
364 * looking up the providers of a dependency */
365 #define FOR_RULELITERALS(l, dp, r) \
366 for (l = r->d < 0 ? -r->d - 1 : r->d, \
367 dp = !l ? &r->w2 : pool->whatprovidesdata + l, \
368 l = r->p; l; l = (dp != &r->w2 + 1 ? *dp++ : 0))
370 /* iterate over all packages selected by a job */
371 #define FOR_JOB_SELECT(p, pp, select, what) \
372 for (pp = (select == SOLVER_SOLVABLE ? 0 : \
373 select == SOLVER_SOLVABLE_ONE_OF ? what : \
374 pool_whatprovides(pool, what)), \
375 p = (select == SOLVER_SOLVABLE ? what : pool->whatprovidesdata[pp++]) ; p ; p = pool->whatprovidesdata[pp++]) \
376 if (select != SOLVER_SOLVABLE_NAME || pool_match_nevr(pool, pool->solvables + p, what))
382 #endif /* SATSOLVER_SOLVER_H */