/home/brain/Projects/upstream/libsolv/src/solver.c

Bug Summary

File:	src/solver.c
Warning:	line 2997, column 8 Value stored to 'p' is never read

Annotated Source Code

1	/*
2	* Copyright (c) 2007-2008, Novell Inc.
3	*
4	* This program is licensed under the BSD license, read LICENSE.BSD
5	* for further information
6	*/
7
8	/*
9	* solver.c
10	*
11	* SAT based dependency solver
12	*/
13
14	#include <stdio.h>
15	#include <stdlib.h>
16	#include <unistd.h>
17	#include <string.h>
18	#include <assert.h>
19
20	#include "solver.h"
21	#include "solver_private.h"
22	#include "bitmap.h"
23	#include "pool.h"
24	#include "util.h"
25	#include "policy.h"
26	#include "poolarch.h"
27	#include "solverdebug.h"
28	#include "cplxdeps.h"
29	#include "linkedpkg.h"
30
31	#define RULES_BLOCK63 63
32
33
34	/********************************************************************
35	*
36	* dependency check helpers
37	*
38	*/
39
40	/*-------------------------------------------------------------------
41	* handle split provides
42	*
43	* a splitprovides dep looks like
44	* namespace:splitprovides(pkg REL_WITH path)
45	* and is only true if pkg is installed and contains the specified path.
46	* we also make sure that pkg is selected for an update, otherwise the
47	* update would always be forced onto the user.
48	* Map m is the map used when called from dep_possible.
49	*/
50
51	static int
52	solver_is_updating(Solver *solv, Id p)
53	{
54	/* check if the update rule is true */
55	Pool *pool = solv->pool;
56	Rule *r;
57	Id l, pp;
58	if (solv->decisionmap[p] >= 0)
59	return 0; /* old package stayed */
60	r = solv->rules + solv->updaterules + (p - solv->installed->start);
61	FOR_RULELITERALS(l, pp, r)for (pp = r->d < 0 ? -r->d - 1 : r->d, l = r-> p; l; l = (pp <= 0 ? (pp-- ? 0 : r->w2) : pool->whatprovidesdata [pp++]))
62	if (l > 0 && l != p && solv->decisionmap[l] > 0)
63	return 1;
64	return 0;
65	}
66
67	int
68	solver_splitprovides(Solver solv, Id dep, Map m)
69	{
70	Pool *pool = solv->pool;
71	Id p, pp;
72	Reldep *rd;
73	Solvable *s;
74
75	if (!solv->dosplitprovides \|\| !solv->installed)
76	return 0;
77	if (!ISRELDEP(dep)(((dep) & 0x80000000) != 0))
78	return 0;
79	rd = GETRELDEP(pool, dep)((pool)->rels + ((dep) ^ 0x80000000));
80	if (rd->flags != REL_WITH18)
81	return 0;
82	/*
83	* things are a bit tricky here if pool->addedprovides == 1, because most split-provides are in
84	* a non-standard location. If we simply call pool_whatprovides, we'll drag in the complete
85	* file list. Instead we rely on pool_addfileprovides ignoring the addfileprovidesfiltered flag
86	* for installed packages and check the lazywhatprovidesq (ignoring the REL_WITH part, but
87	* we filter the package name further down anyway).
88	*/
89	if (pool->addedfileprovides == 1 && !ISRELDEP(rd->evr)(((rd->evr) & 0x80000000) != 0) && !pool->whatprovides[rd->evr])
90	pp = pool_searchlazywhatprovidesq(pool, rd->evr);
91	else
92	pp = pool_whatprovides(pool, dep);
93	while ((p = pool->whatprovidesdata[pp++]) != 0)
94	{
95	/* here we have packages that provide the correct name and contain the path,
96	* now do extra filtering */
97	s = pool->solvables + p;
98	if (s->repo != solv->installed \|\| s->name != rd->name)
99	continue;
100	/* check if the package is updated. if m is set, we're called from dep_possible */
101	if (m \|\| solver_is_updating(solv, p))
102	return 1;
103	}
104	return 0;
105	}
106
107
108	/* mirrors solver_dep_fulfilled, but returns 2 if a new package
109	* was involved */
110	static int
111	solver_dep_fulfilled_alreadyinstalled(Solver *solv, Id dep)
112	{
113	Pool *pool = solv->pool;
114	Id p, pp;
115	int r;
116
117	if (ISRELDEP(dep)(((dep) & 0x80000000) != 0))
118	{
119	Reldep *rd = GETRELDEP(pool, dep)((pool)->rels + ((dep) ^ 0x80000000));
120	if (rd->flags == REL_COND22)
121	{
122	int r1, r2;
123	if (ISRELDEP(rd->evr)(((rd->evr) & 0x80000000) != 0))
124	{
125	Reldep *rd2 = GETRELDEP(pool, rd->evr)((pool)->rels + ((rd->evr) ^ 0x80000000));
126	if (rd2->flags == REL_ELSE26)
127	{
128	r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd2->name);
129	if (r1)
130	{
131	r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
132	return r2 && r1 == 2 ? 2 : r2;
133	}
134	return solver_dep_fulfilled_alreadyinstalled(solv, rd2->evr);
135	}
136	}
137	r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
138	r2 = !solver_dep_fulfilled_alreadyinstalled(solv, rd->evr);
139	if (!r1 && !r2)
140	return 0;
141	return r1 == 2 ? 2 : 1;
142	}
143	if (rd->flags == REL_AND16)
144	{
145	int r2, r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
146	if (!r1)
147	return 0;
148	r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->evr);
149	if (!r2)
150	return 0;
151	return r1 == 2 \|\| r2 == 2 ? 2 : 1;
152	}
153	if (rd->flags == REL_OR17)
154	{
155	int r2, r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
156	r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->evr);
157	if (!r1 && !r2)
158	return 0;
159	return r1 == 2 \|\| r2 == 2 ? 2 : 1;
160	}
161	if (rd->flags == REL_NAMESPACE19 && rd->name == NAMESPACE_SPLITPROVIDES)
162	return solver_splitprovides(solv, rd->evr, 0);
163	if (rd->flags == REL_NAMESPACE19 && solv->installsuppdepq)
164	{
165	Queue *q = solv->installsuppdepq;
166	int i;
167	for (i = 0; i < q->count; i++)
168	if (q->elements[i] == dep \|\| q->elements[i] == rd->name)
169	return 2;
170	}
171	}
172	r = 0;
173	FOR_PROVIDES(p, pp, dep)for (pp = pool_whatprovides(pool, dep) ; (p = pool->whatprovidesdata [pp++]) != 0; )
174	if (solv->decisionmap[p] > 0)
175	{
176	Solvable *s = pool->solvables + p;
177	if (s->repo && s->repo != solv->installed)
178	return 2;
179	r = 1;
180	}
181	return r;
182	}
183
184	static int
185	solver_is_supplementing_alreadyinstalled(Solver solv, Solvable s)
186	{
187	Id sup, *supp;
188	supp = s->repo->idarraydata + s->supplements;
189	while ((sup = *supp++) != 0)
190	if (solver_dep_fulfilled_alreadyinstalled(solv, sup) == 2)
191	return 1;
192	return 0;
193	}
194
195	static Id
196	autouninstall(Solver solv, Id problem)
197	{
198	Pool *pool = solv->pool;
199	int i;
200	int lastfeature = 0, lastupdate = 0;
201	Id v;
202	Id extraflags = -1;
203	Map *m = 0;
204
205	if (!solv->allowuninstall && !solv->allowuninstall_all)
206	{
207	if (!solv->allowuninstallmap.size)
208	return 0; /* why did we get called? */
209	m = &solv->allowuninstallmap;
210	}
211	for (i = 0; (v = problem[i]) != 0; i++)
212	{
213	if (v < 0)
214	extraflags &= solv->job.elements[-v - 1];
215	if (v >= solv->updaterules && v < solv->updaterules_end)
216	{
217	Rule *r;
218	if (m && !MAPTST(m, v - solv->updaterules)((m)->map[(v - solv->updaterules) >> 3] & (1 << ((v - solv->updaterules) & 7))))
219	continue;
220	/* check if identical to feature rule, we don't like that (except for orphans) */
221	r = solv->rules + solv->featurerules + (v - solv->updaterules);
222	if (!r->p)
223	{
224	/* update rule == feature rule */
225	if (v > lastfeature)
226	lastfeature = v;
227	/* prefer orphaned packages in dup mode */
228	if (solv->keep_orphans)
229	{
230	r = solv->rules + v;
231	if (!r->d && !r->w2 && r->p == (solv->installed->start + (v - solv->updaterules)))
232	{
233	lastfeature = v;
234	lastupdate = 0;
235	break;
236	}
237	}
238	continue;
239	}
240	if (v > lastupdate)
241	lastupdate = v;
242	}
243	}
244	if (!lastupdate && !lastfeature)
245	return 0;
246	v = lastupdate ? lastupdate : lastfeature;
247	POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "allowuninstall disabling ")do {if ((pool->debugmask & ((1<<7))) != 0) pool_debug (pool, ((1<<7)), "allowuninstall disabling ");} while ( 0);
248	solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE(1<<7), solv->rules + v);
249	solver_disableproblem(solv, v);
250	if (extraflags != -1 && (extraflags & SOLVER_CLEANDEPS0x040000) != 0 && solv->cleandepsmap.size)
251	{
252	/* add the package to the updatepkgs list, this will automatically turn
253	* on cleandeps mode */
254	Id p = solv->rules[v].p;
255	if (!solv->cleandeps_updatepkgs)
256	{
257	solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
258	queue_init(solv->cleandeps_updatepkgs);
259	}
260	if (p > 0)
261	{
262	int oldupdatepkgscnt = solv->cleandeps_updatepkgs->count;
263	queue_pushunique(solv->cleandeps_updatepkgs, p);
264	if (solv->cleandeps_updatepkgs->count != oldupdatepkgscnt)
265	solver_disablepolicyrules(solv);
266	}
267	}
268	return v;
269	}
270
271	/************************************************************************/
272
273	/*
274	* enable/disable learnt rules
275	*
276	* we have enabled or disabled some of our rules. We now reenable all
277	* of our learnt rules except the ones that were learnt from rules that
278	* are now disabled.
279	*/
280	static void
281	enabledisablelearntrules(Solver *solv)
282	{
283	Pool *pool = solv->pool;
284	Rule *r;
285	Id why, *whyp;
286	int i;
287
288	POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n")do {if ((pool->debugmask & ((1<<8))) != 0) pool_debug (pool, ((1<<8)), "enabledisablelearntrules called\n");} while (0);
289	for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
290	{
291	whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
292	while ((why = *whyp++) != 0)
293	{
294	assert(why > 0 && why < i)({ if (why > 0 && why < i) ; else __assert_fail ("why > 0 && why < i", "/home/brain/Projects/upstream/libsolv/src/solver.c" , 294, __PRETTY_FUNCTION__); });
295	if (solv->rules[why].d < 0)
296	break;
297	}
298	/* why != 0: we found a disabled rule, disable the learnt rule */
299	if (why && r->d >= 0)
300	{
301	IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)if ((pool->debugmask & ((1<<8))) != 0)
302	{
303	POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "disabling ")do {if ((pool->debugmask & ((1<<8))) != 0) pool_debug (pool, ((1<<8)), "disabling ");} while (0);
304	solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS(1<<8), r);
305	}
306	solver_disablerule(solv, r);
307	}
308	else if (!why && r->d < 0)
309	{
310	IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)if ((pool->debugmask & ((1<<8))) != 0)
311	{
312	POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "re-enabling ")do {if ((pool->debugmask & ((1<<8))) != 0) pool_debug (pool, ((1<<8)), "re-enabling ");} while (0);
313	solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS(1<<8), r);
314	}
315	solver_enablerule(solv, r);
316	}
317	}
318	}
319
320
321	/*
322	* make assertion rules into decisions
323	*
324	* Go through rules and add direct assertions to the decisionqueue.
325	* If we find a conflict, disable rules and add them to problem queue.
326	*/
327
328	static void
329	makeruledecisions(Solver *solv)
330	{
331	Pool *pool = solv->pool;
332	int i, ri, ii;
333	Rule r, rr;
334	Id v, vv;
335	int decisionstart;
336	int record_proof = 1;
337	int oldproblemcount;
338	int havedisabled = 0;
339
340	/* The system solvable is always installed first */
341	assert(solv->decisionq.count == 0)({ if (solv->decisionq.count == 0) ; else __assert_fail ("solv->decisionq.count == 0" , "/home/brain/Projects/upstream/libsolv/src/solver.c", 341, __PRETTY_FUNCTION__ ); });
342	queue_push(&solv->decisionq, SYSTEMSOLVABLE1);
343	queue_push(&solv->decisionq_why, 0);
344	queue_push2(&solv->decisionq_reason, 0, 0);
345	solv->decisionmap[SYSTEMSOLVABLE1] = 1; /* installed at level '1' */
346
347	decisionstart = solv->decisionq.count;
348	for (;;)
349	{
350	/* if we needed to re-run, back up decisions to decisionstart */
351	while (solv->decisionq.count > decisionstart)
352	{
353	v = solv->decisionq.elements[--solv->decisionq.count];
354	--solv->decisionq_why.count;
355	vv = v > 0 ? v : -v;
356	solv->decisionmap[vv] = 0;
357	}
358
359	/* note that the ruleassertions queue is ordered */
360	for (ii = 0; ii < solv->ruleassertions.count; ii++)
361	{
362	ri = solv->ruleassertions.elements[ii];
363	r = solv->rules + ri;
364
365	if (havedisabled && ri >= solv->learntrules)
366	{
367	/* just started with learnt rule assertions. If we have disabled
368	* some rules, adapt the learnt rule status */
369	enabledisablelearntrules(solv);
370	havedisabled = 0;
371	}
372
373	if (r->d < 0 \|\| !r->p \|\| r->w2) /* disabled, dummy or no assertion */
374	continue;
375
376	/* do weak rules in phase 2 */
377	if (ri < solv->learntrules && solv->weakrulemap.size && MAPTST(&solv->weakrulemap, ri)((&solv->weakrulemap)->map[(ri) >> 3] & ( 1 << ((ri) & 7))))
378	continue;
379
380	v = r->p;
381	vv = v > 0 ? v : -v;
382
383	if (!solv->decisionmap[vv]) /* if not yet decided */
384	{
385	queue_push(&solv->decisionq, v);
386	queue_push(&solv->decisionq_why, r - solv->rules);
387	solv->decisionmap[vv] = v > 0 ? 1 : -1;
388	IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)if ((pool->debugmask & ((1<<5))) != 0)
389	{
390	Solvable *s = solv->pool->solvables + vv;
391	if (v < 0)
392	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", pool_solvable2str(solv->pool, s))do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), "conflicting %s (assertion)\n", pool_solvable2str (solv->pool, s));} while (0);
393	else
394	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing %s (assertion)\n", pool_solvable2str(solv->pool, s))do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), "installing %s (assertion)\n", pool_solvable2str (solv->pool, s));} while (0);
395	}
396	continue;
397	}
398
399	/* check against previous decision: is there a conflict? */
400	if (v > 0 && solv->decisionmap[vv] > 0) /* ok to install */
401	continue;
402	if (v < 0 && solv->decisionmap[vv] < 0) /* ok to remove */
403	continue;
404
405	/*
406	* found a conflict!
407	*
408	* The rule (r) we're currently processing says something
409	* different (v = r->p) than a previous decision (decisionmap[abs(v)])
410	* on this literal
411	*/
412
413	if (ri >= solv->learntrules)
414	{
415	/* conflict with a learnt rule */
416	/* can happen when packages cannot be installed for multiple reasons. */
417	/* we disable the learnt rule in this case */
418	/* (XXX: we should really call analyze_unsolvable_rule here!) */
419	solver_disablerule(solv, r);
420	continue;
421	}
422
423	/*
424	* find the decision which is the "opposite" of the rule
425	*/
426	for (i = 0; i < solv->decisionq.count; i++)
427	if (solv->decisionq.elements[i] == -v)
428	break;
429	assert(i < solv->decisionq.count)({ if (i < solv->decisionq.count) ; else __assert_fail ( "i < solv->decisionq.count", "/home/brain/Projects/upstream/libsolv/src/solver.c" , 429, __PRETTY_FUNCTION__); }); /* assert that we found it */
430	oldproblemcount = solv->problems.count;
431
432	/*
433	* conflict with system solvable ?
434	*/
435	if (v == -SYSTEMSOLVABLE1)
436	{
437	if (record_proof)
438	{
439	queue_push(&solv->problems, solv->learnt_pool.count);
440	queue_push(&solv->learnt_pool, ri);
441	queue_push(&solv->learnt_pool, 0);
442	}
443	else
444	queue_push(&solv->problems, 0);
445	POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri)do {if ((pool->debugmask & ((1<<7))) != 0) pool_debug (pool, ((1<<7)), "conflict with system solvable, disabling rule #%d\n" , ri);} while (0);
446	if (ri >= solv->jobrules && ri < solv->jobrules_end)
447	v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
448	else
449	v = ri;
450	queue_push(&solv->problems, v);
451	queue_push(&solv->problems, 0);
452	if (v >= solv->featurerules && v < solv->updaterules_end)
453	{
454	if (solv->allowuninstall \|\| solv->allowuninstall_all \|\| solv->allowuninstallmap.size)
455	if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
456	{
457	solv->problems.count = oldproblemcount;
458	havedisabled = 1;
459	break; /* start over */
460	}
461	}
462	solver_disableproblem(solv, v);
463	havedisabled = 1;
464	break; /* start over */
465	}
466
467	assert(solv->decisionq_why.elements[i] > 0)({ if (solv->decisionq_why.elements[i] > 0) ; else __assert_fail ("solv->decisionq_why.elements[i] > 0", "/home/brain/Projects/upstream/libsolv/src/solver.c" , 467, __PRETTY_FUNCTION__); });
468
469	/*
470	* conflict with a pkg rule ?
471	*/
472	if (solv->decisionq_why.elements[i] < solv->pkgrules_end)
473	{
474	if (record_proof)
475	{
476	queue_push(&solv->problems, solv->learnt_pool.count);
477	queue_push(&solv->learnt_pool, ri);
478	queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
479	queue_push(&solv->learnt_pool, 0);
480	}
481	else
482	queue_push(&solv->problems, 0);
483	assert(v > 0 \|\| v == -SYSTEMSOLVABLE)({ if (v > 0 \|\| v == -1) ; else __assert_fail ("v > 0 \|\| v == -SYSTEMSOLVABLE" , "/home/brain/Projects/upstream/libsolv/src/solver.c", 483, __PRETTY_FUNCTION__ ); });
484	POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with pkg rule, disabling rule #%d\n", ri)do {if ((pool->debugmask & ((1<<7))) != 0) pool_debug (pool, ((1<<7)), "conflict with pkg rule, disabling rule #%d\n" , ri);} while (0);
485	if (ri >= solv->jobrules && ri < solv->jobrules_end)
486	v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
487	else
488	v = ri;
489	queue_push(&solv->problems, v);
490	queue_push(&solv->problems, 0);
491	if (v >= solv->featurerules && v < solv->updaterules_end)
492	{
493	if (solv->allowuninstall \|\| solv->allowuninstall_all \|\| solv->allowuninstallmap.size)
494	if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
495	{
496	solv->problems.count = oldproblemcount;
497	havedisabled = 1;
498	break; /* start over */
499	}
500	}
501	solver_disableproblem(solv, v);
502	havedisabled = 1;
503	break; /* start over */
504	}
505
506	/*
507	* conflict with another job or update/feature rule
508	*/
509
510	/* record proof */
511	if (record_proof)
512	{
513	queue_push(&solv->problems, solv->learnt_pool.count);
514	queue_push(&solv->learnt_pool, ri);
515	queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
516	queue_push(&solv->learnt_pool, 0);
517	}
518	else
519	queue_push(&solv->problems, 0);
520
521	POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv)do {if ((pool->debugmask & ((1<<7))) != 0) pool_debug (pool, ((1<<7)), "conflicting update/job assertions over literal %d\n" , vv);} while (0);
522
523	/*
524	* push all of our rules (can only be feature or job rules)
525	* asserting this literal on the problem stack
526	*/
527	for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
528	{
529	if (rr->d < 0 /* disabled */
530	\|\| rr->w2) /* or no assertion */
531	continue;
532	if (rr->p != vv /* not affecting the literal */
533	&& rr->p != -vv)
534	continue;
535	if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, i)((&solv->weakrulemap)->map[(i) >> 3] & (1 << ((i) & 7)))) /* weak: silently ignore */
536	continue;
537
538	POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i)do {if ((pool->debugmask & ((1<<7))) != 0) pool_debug (pool, ((1<<7)), " - disabling rule #%d\n", i);} while ( 0);
539	solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE(1<<7), solv->rules + i);
540
541	v = i;
542	if (i >= solv->jobrules && i < solv->jobrules_end)
543	v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
544	queue_push(&solv->problems, v);
545	}
546	queue_push(&solv->problems, 0);
547
548	if (solv->allowuninstall \|\| solv->allowuninstall_all \|\| solv->allowuninstallmap.size)
549	if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
550	{
551	solv->problems.count = oldproblemcount;
552	havedisabled = 1;
553	break; /* start over */
554	}
555
556	for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
557	solver_disableproblem(solv, solv->problems.elements[i]);
558	havedisabled = 1;
559	break; /* start over */
560	}
561	if (ii < solv->ruleassertions.count)
562	continue;
563
564	/*
565	* phase 2: now do the weak assertions
566	*/
567	if (!solv->weakrulemap.size)
568	break; /* no weak rules, no phase 2 */
569	for (ii = 0; ii < solv->ruleassertions.count; ii++)
570	{
571	ri = solv->ruleassertions.elements[ii];
572	r = solv->rules + ri;
573	if (r->d < 0 \|\| r->w2) /* disabled or no assertion */
574	continue;
575	if (ri >= solv->learntrules \|\| !MAPTST(&solv->weakrulemap, ri)((&solv->weakrulemap)->map[(ri) >> 3] & ( 1 << ((ri) & 7)))) /* skip non-weak */
576	continue;
577	v = r->p;
578	vv = v > 0 ? v : -v;
579
580	if (!solv->decisionmap[vv]) /* if not yet decided */
581	{
582	queue_push(&solv->decisionq, v);
583	queue_push(&solv->decisionq_why, r - solv->rules);
584	solv->decisionmap[vv] = v > 0 ? 1 : -1;
585	IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)if ((pool->debugmask & ((1<<5))) != 0)
586	{
587	Solvable *s = solv->pool->solvables + vv;
588	if (v < 0)
589	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", pool_solvable2str(solv->pool, s))do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), "conflicting %s (weak assertion)\n", pool_solvable2str (solv->pool, s));} while (0);
590	else
591	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing %s (weak assertion)\n", pool_solvable2str(solv->pool, s))do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), "installing %s (weak assertion)\n", pool_solvable2str (solv->pool, s));} while (0);
592	}
593	continue;
594	}
595	/* check against previous decision: is there a conflict? */
596	if (v > 0 && solv->decisionmap[vv] > 0)
597	continue;
598	if (v < 0 && solv->decisionmap[vv] < 0)
599	continue;
600
601	POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ")do {if ((pool->debugmask & ((1<<7))) != 0) pool_debug (pool, ((1<<7)), "assertion conflict, but I am weak, disabling " );} while (0);
602	solver_printrule(solv, SOLV_DEBUG_UNSOLVABLE(1<<7), r);
603
604	if (ri >= solv->jobrules && ri < solv->jobrules_end)
605	v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
606	else
607	v = ri;
608	solver_disableproblem(solv, v);
609	if (v < 0)
610	solver_reenablepolicyrules(solv, -v);
611	havedisabled = 1;
612	break; /* start over */
613	}
614	if (ii == solv->ruleassertions.count)
615	break; /* finished! */
616	}
617	}
618
619
620	/********************************************************************/
621	/* watches */
622
623
624	/*-------------------------------------------------------------------
625	* makewatches
626	*
627	* initial setup for all watches
628	*/
629
630	static void
631	makewatches(Solver *solv)
632	{
633	Rule *r;
634	int i;
635	int nsolvables = solv->pool->nsolvables;
636
637	solv_free(solv->watches);
638	/* lower half for removals, upper half for installs */
639	solv->watches = solv_calloc(2 * nsolvables, sizeof(Id));
640	for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
641	{
642	if (!r->w2) /* assertions do not need watches */
643	continue;
644
645	/* see addwatches_rule(solv, r) */
646	r->n1 = solv->watches[nsolvables + r->w1];
647	solv->watches[nsolvables + r->w1] = r - solv->rules;
648
649	r->n2 = solv->watches[nsolvables + r->w2];
650	solv->watches[nsolvables + r->w2] = r - solv->rules;
651	}
652	}
653
654
655	/*-------------------------------------------------------------------
656	*
657	* add watches (for a new learned rule)
658	* sets up watches for a single rule
659	*
660	* see also makewatches() above.
661	*/
662
663	static inline void
664	addwatches_rule(Solver solv, Rule r)
665	{
666	int nsolvables = solv->pool->nsolvables;
667
668	r->n1 = solv->watches[nsolvables + r->w1];
669	solv->watches[nsolvables + r->w1] = r - solv->rules;
670
671	r->n2 = solv->watches[nsolvables + r->w2];
672	solv->watches[nsolvables + r->w2] = r - solv->rules;
673	}
674
675
676	/********************************************************************/
677	/*
678	* rule propagation
679	*/
680
681
682	/* shortcuts to check if a literal (positive or negative) assignment
683	* evaluates to 'true' or 'false'
684	*/
685	#define DECISIONMAP_TRUE(p)((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0)) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
686	#define DECISIONMAP_FALSE(p)((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0)) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
687	#define DECISIONMAP_UNDEF(p)(decisionmap[(p) > 0 ? (p) : -(p)] == 0) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
688
689	/*-------------------------------------------------------------------
690	*
691	* propagate
692	*
693	* make decision and propagate to all rules
694	*
695	* Evaluate each term affected by the decision (linked through watches).
696	* If we find unit rules we make new decisions based on them.
697	*
698	* return : 0 = everything is OK
699	* rule = conflict found in this rule
700	*/
701
702	static Rule *
703	propagate(Solver *solv, int level)
704	{
705	Pool *pool = solv->pool;
706	Id rp, next_rp; /* rule pointer, next rule pointer in linked list */
707	Rule r; / rule */
708	Id p, pkg, other_watch;
709	Id *dp;
710	Id *decisionmap = solv->decisionmap;
711	Id watches = solv->watches + pool->nsolvables; / place ptr in middle */
712
713	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate -----\n")do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), "----- propagate -----\n");} while (0);
714
715	/* foreach non-propagated decision */
716	while (solv->propagate_index < solv->decisionq.count)
717	{
718	/*
719	* 'pkg' was just decided
720	* negate because our watches trigger if literal goes FALSE
721	*/
722	pkg = -solv->decisionq.elements[solv->propagate_index++];
723
724	IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)if ((pool->debugmask & ((1<<5))) != 0)
725	{
726	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level)do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), "propagate for decision %d level %d\n" , -pkg, level);} while (0);
727	solver_printruleelement(solv, SOLV_DEBUG_PROPAGATE(1<<5), 0, -pkg);
728	}
729
730	/* foreach rule where 'pkg' is now FALSE */
731	for (rp = watches + pkg; *rp; rp = next_rp)
732	{
733	r = solv->rules + *rp;
734	if (r->d < 0)
735	{
736	/* rule is disabled, goto next */
737	if (pkg == r->w1)
738	next_rp = &r->n1;
739	else
740	next_rp = &r->n2;
741	continue;
742	}
743
744	IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)if ((pool->debugmask & ((1<<5))) != 0)
745	{
746	POOL_DEBUG(SOLV_DEBUG_PROPAGATE," watch triggered ")do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), " watch triggered ");} while (0);
747	solver_printrule(solv, SOLV_DEBUG_PROPAGATE(1<<5), r);
748	}
749
750	/*
751	* 'pkg' was just decided (was set to FALSE), so this rule
752	* may now be unit.
753	*/
754	/* find the other watch */
755	if (pkg == r->w1)
756	{
757	other_watch = r->w2;
758	next_rp = &r->n1;
759	}
760	else
761	{
762	other_watch = r->w1;
763	next_rp = &r->n2;
764	}
765
766	/*
767	* if the other watch is true we have nothing to do
768	*/
769	if (DECISIONMAP_TRUE(other_watch)((other_watch) > 0 ? (decisionmap[other_watch] > 0) : ( decisionmap[-other_watch] < 0)))
770	continue;
771
772	/*
773	* The other literal is FALSE or UNDEF
774	*
775	*/
776
777	if (r->d)
778	{
779	/* Not a binary clause, try to move our watch.
780	*
781	* Go over all literals and find one that is
782	* not other_watch
783	* and not FALSE
784	*
785	* (TRUE is also ok, in that case the rule is fulfilled)
786	* As speed matters here we do not use the FOR_RULELITERALS
787	* macro.
788	*/
789	if (r->p /* we have a 'p' */
790	&& r->p != other_watch /* which is not watched */
791	&& !DECISIONMAP_FALSE(r->p)((r->p) > 0 ? (decisionmap[r->p] < 0) : (decisionmap [-r->p] > 0))) /* and not FALSE */
792	{
793	p = r->p;
794	}
795	else /* go find a 'd' to make 'true' */
796	{
797	/* foreach p in 'd'
798	we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
799	*/
800	for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
801	{
802	if (p != other_watch /* which is not watched */
803	&& !DECISIONMAP_FALSE(p)((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))) /* and not FALSE */
804	break;
805	}
806	}
807
808	if (p)
809	{
810	/*
811	* if we found some p that is UNDEF or TRUE, move
812	* watch to it
813	*/
814	IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)if ((pool->debugmask & ((1<<5))) != 0)
815	{
816	if (p > 0)
817	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), " -> move w%d to %s\n", (pkg == r ->w1 ? 1 : 2), pool_solvid2str(pool, p));} while (0);
818	else
819	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p))do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), " -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p));} while (0);
820	}
821
822	rp = next_rp;
823	next_rp = rp;
824
825	if (pkg == r->w1)
826	{
827	r->w1 = p;
828	r->n1 = watches[p];
829	}
830	else
831	{
832	r->w2 = p;
833	r->n2 = watches[p];
834	}
835	watches[p] = r - solv->rules;
836	continue;
837	}
838	/* search failed, thus all unwatched literals are FALSE */
839
840	} /* not binary */
841
842	/*
843	* unit clause found, set literal other_watch to TRUE
844	*/
845
846	if (DECISIONMAP_FALSE(other_watch)((other_watch) > 0 ? (decisionmap[other_watch] < 0) : ( decisionmap[-other_watch] > 0))) /* check if literal is FALSE */
847	return r; /* eek, a conflict! */
848
849	IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)if ((pool->debugmask & ((1<<5))) != 0)
850	{
851	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " unit ")do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), " unit ");} while (0);
852	solver_printrule(solv, SOLV_DEBUG_PROPAGATE(1<<5), r);
853	}
854
855	if (other_watch > 0)
856	decisionmap[other_watch] = level; /* install! */
857	else
858	decisionmap[-other_watch] = -level; /* remove! */
859
860	queue_push(&solv->decisionq, other_watch);
861	queue_push(&solv->decisionq_why, r - solv->rules);
862
863	IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)if ((pool->debugmask & ((1<<5))) != 0)
864	{
865	if (other_watch > 0)
866	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> decided to install %s\n", pool_solvid2str(pool, other_watch))do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), " -> decided to install %s\n", pool_solvid2str (pool, other_watch));} while (0);
867	else
868	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> decided to conflict %s\n", pool_solvid2str(pool, -other_watch))do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), " -> decided to conflict %s\n", pool_solvid2str (pool, -other_watch));} while (0);
869	}
870
871	} /* foreach rule involving 'pkg' */
872
873	} /* while we have non-decided decisions */
874
875	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate end-----\n")do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), "----- propagate end-----\n");} while ( 0);
876
877	return 0; /* all is well */
878	}
879
880
881	/********************************************************************/
882	/* Analysis */
883
884	/*-------------------------------------------------------------------
885	*
886	* revert
887	* revert decisionq to a level
888	*/
889
890	static void
891	revert(Solver *solv, int level)
892	{
893	Pool *pool = solv->pool;
894	Id v, vv;
895	while (solv->decisionq.count)
896	{
897	v = solv->decisionq.elements[solv->decisionq.count - 1];
898	vv = v > 0 ? v : -v;
899	if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
900	break;
901	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv])do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), "reverting decision %d at %d\n", v, solv ->decisionmap[vv]);} while (0);
902	solv->decisionmap[vv] = 0;
903	solv->decisionq.count--;
904	solv->decisionq_why.count--;
905	solv->propagate_index = solv->decisionq.count;
906	}
907	while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= level)
908	solv->branches.count -= solv->branches.elements[solv->branches.count - 2];
909	if (solv->recommends_index > solv->decisionq.count)
910	solv->recommends_index = -1; /* rebuild recommends/suggests maps */
911	solv->decisionq_reason.count = level + 1;
912	}
913
914	/*-------------------------------------------------------------------
915	*
916	* watch2onhighest - put watch2 on literal with highest level
917	*/
918
919	static inline void
920	watch2onhighest(Solver solv, Rule r)
921	{
922	int l, wl = 0;
923	Id d, v, *dp;
924
925	d = r->d < 0 ? -r->d - 1 : r->d;
926	if (!d)
927	return; /* binary rule, both watches are set */
928	dp = solv->pool->whatprovidesdata + d;
929	while ((v = *dp++) != 0)
930	{
931	l = solv->decisionmap[v < 0 ? -v : v];
932	if (l < 0)
933	l = -l;
934	if (l > wl)
935	{
936	r->w2 = dp[-1];
937	wl = l;
938	}
939	}
940	}
941
942
943	/*-------------------------------------------------------------------
944	*
945	* analyze
946	* and learn
947	*/
948
949	static int
950	analyze(Solver solv, int level, Rule c, Rule **lrp)
951	{
952	Pool *pool = solv->pool;
953	Queue q;
954	Rule *r;
955	Id q_buf[8];
956	int rlevel = 1;
957	Map seen; /* global? */
958	Id p = 0, pp, v, vv, why;
959	int l, i, idx;
960	int num = 0, l1num = 0;
961	int learnt_why = solv->learnt_pool.count;
962	Id *decisionmap = solv->decisionmap;
963
964	queue_init_buffer(&q, q_buf, sizeof(q_buf)/sizeof(*q_buf));
965
966	POOL_DEBUG(SOLV_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level)do {if ((pool->debugmask & ((1<<6))) != 0) pool_debug (pool, ((1<<6)), "ANALYZE at %d ----------------------\n" , level);} while (0);
967	map_init(&seen, pool->nsolvables);
968	idx = solv->decisionq.count;
969	for (;;)
970	{
971	IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)if ((pool->debugmask & ((1<<6))) != 0)
972	solver_printruleclass(solv, SOLV_DEBUG_ANALYZE(1<<6), c);
973	queue_push(&solv->learnt_pool, c - solv->rules);
974	FOR_RULELITERALS(v, pp, c)for (pp = c->d < 0 ? -c->d - 1 : c->d, v = c-> p; v; v = (pp <= 0 ? (pp-- ? 0 : c->w2) : pool->whatprovidesdata [pp++]))
975	{
976	if (DECISIONMAP_TRUE(v)((v) > 0 ? (decisionmap[v] > 0) : (decisionmap[-v] < 0))) /* the one true literal */
977	continue;
978	vv = v > 0 ? v : -v;
979	if (MAPTST(&seen, vv)((&seen)->map[(vv) >> 3] & (1 << ((vv) & 7))))
980	continue;
981	MAPSET(&seen, vv)((&seen)->map[(vv) >> 3] \|= 1 << ((vv) & 7)); /* mark that we also need to look at this literal */
982	l = solv->decisionmap[vv];
983	if (l < 0)
984	l = -l;
985	if (l == 1)
986	l1num++; /* need to do this one in level1 pass */
987	else if (l == level)
988	num++; /* need to do this one as well */
989	else
990	{
991	queue_push(&q, v); /* not level1 or conflict level, add to new rule */
992	if (l > rlevel)
993	rlevel = l;
994	}
995	}
996	l1retry:
997	if (!num && !--l1num)
998	break; /* all literals done */
999
1000	/* find the next literal to investigate */
1001	/* (as num + l1num > 0, we know that we'll always find one) */
1002	for (;;)
1003	{
1004	assert(idx > 0)({ if (idx > 0) ; else __assert_fail ("idx > 0", "/home/brain/Projects/upstream/libsolv/src/solver.c" , 1004, __PRETTY_FUNCTION__); });
1005	v = solv->decisionq.elements[--idx];
1006	vv = v > 0 ? v : -v;
1007	if (MAPTST(&seen, vv)((&seen)->map[(vv) >> 3] & (1 << ((vv) & 7))))
1008	break;
1009	}
1010	MAPCLR(&seen, vv)((&seen)->map[(vv) >> 3] &= ~(1 << ((vv ) & 7)));
1011
1012	if (num && --num == 0)
1013	{
1014	/* done with normal literals, now start level 1 literal processing */
1015	p = -v; /* so that v doesn't get lost */
1016	if (!l1num)
1017	break;
1018	POOL_DEBUG(SOLV_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num)do {if ((pool->debugmask & ((1<<6))) != 0) pool_debug (pool, ((1<<6)), "got %d involved level 1 decisions\n", l1num);} while (0);
1019	/* clear non-l1 bits from seen map */
1020	for (i = 0; i < q.count; i++)
1021	{
1022	v = q.elements[i];
1023	MAPCLR(&seen, v > 0 ? v : -v)((&seen)->map[(v > 0 ? v : -v) >> 3] &= ~ (1 << ((v > 0 ? v : -v) & 7)));
1024	}
1025	/* only level 1 marks left in seen map */
1026	l1num++; /* as l1retry decrements it */
1027	goto l1retry;
1028	}
1029
1030	why = solv->decisionq_why.elements[idx];
1031	if (why <= 0) /* just in case, maybe for SYSTEMSOLVABLE */
1032	goto l1retry;
1033	c = solv->rules + why;
1034	}
1035	map_free(&seen);
1036	assert(p != 0)({ if (p != 0) ; else __assert_fail ("p != 0", "/home/brain/Projects/upstream/libsolv/src/solver.c" , 1036, __PRETTY_FUNCTION__); });
1037	assert(rlevel > 0 && rlevel < level)({ if (rlevel > 0 && rlevel < level) ; else __assert_fail ("rlevel > 0 && rlevel < level", "/home/brain/Projects/upstream/libsolv/src/solver.c" , 1037, __PRETTY_FUNCTION__); });
1038	IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)if ((pool->debugmask & ((1<<6))) != 0)
1039	{
1040	POOL_DEBUG(SOLV_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level)do {if ((pool->debugmask & ((1<<6))) != 0) pool_debug (pool, ((1<<6)), "learned rule for level %d (am %d)\n", rlevel, level);} while (0);
1041	solver_printruleelement(solv, SOLV_DEBUG_ANALYZE(1<<6), 0, p);
1042	for (i = 0; i < q.count; i++)
1043	solver_printruleelement(solv, SOLV_DEBUG_ANALYZE(1<<6), 0, q.elements[i]);
1044	}
1045	/* push end marker on learnt reasons stack */
1046	queue_push(&solv->learnt_pool, 0);
1047	solv->stats_learned++;
1048
1049	POOL_DEBUG(SOLV_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, rlevel)do {if ((pool->debugmask & ((1<<6))) != 0) pool_debug (pool, ((1<<6)), "reverting decisions (level %d -> %d)\n" , level, rlevel);} while (0);
1050	level = rlevel;
1051	revert(solv, level);
1052	if (q.count < 2)
1053	{
1054	Id d = q.count ? q.elements[0] : 0;
1055	queue_free(&q);
1056	r = solver_addrule(solv, p, d, 0);
1057	}
1058	else
1059	{
1060	Id d = pool_queuetowhatprovides(pool, &q);
1061	queue_free(&q);
1062	r = solver_addrule(solv, p, 0, d);
1063	}
1064	assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules)({ if (solv->learnt_why.count == (r - solv->rules) - solv ->learntrules) ; else __assert_fail ("solv->learnt_why.count == (r - solv->rules) - solv->learntrules" , "/home/brain/Projects/upstream/libsolv/src/solver.c", 1064, __PRETTY_FUNCTION__); });
1065	queue_push(&solv->learnt_why, learnt_why);
1066	if (r->w2)
1067	{
1068	/* needs watches */
1069	watch2onhighest(solv, r);
1070	addwatches_rule(solv, r);
1071	}
1072	else
1073	{
1074	/* rule is an assertion */
1075	queue_push(&solv->ruleassertions, r - solv->rules);
1076	}
1077	*lrp = r;
1078	return level;
1079	}
1080
1081
1082	/*-------------------------------------------------------------------
1083	*
1084	* solver_reset
1085	*
1086	* reset all solver decisions
1087	* called after rules have been enabled/disabled
1088	*/
1089
1090	void
1091	solver_reset(Solver *solv)
1092	{
1093	int i;
1094	Id v;
1095
1096	/* rewind all decisions */
1097	for (i = solv->decisionq.count - 1; i >= 0; i--)
1098	{
1099	v = solv->decisionq.elements[i];
1100	solv->decisionmap[v > 0 ? v : -v] = 0;
1101	}
1102	queue_empty(&solv->decisionq_why);
1103	queue_empty(&solv->decisionq);
1104	queue_empty(&solv->decisionq_reason);
1105	solv->recommends_index = -1;
1106	solv->propagate_index = 0;
1107	queue_empty(&solv->branches);
1108
1109	/* adapt learnt rule status to new set of enabled/disabled rules */
1110	enabledisablelearntrules(solv);
1111	}
1112
1113	static inline int
1114	queue_contains(Queue *q, Id id)
1115	{
1116	int i;
1117	for (i = 0; i < q->count; i++)
1118	if (q->elements[i] == id)
1119	return 1;
1120	return 0;
1121	}
1122
1123	static void
1124	disable_recommendsrules(Solver solv, Queue weakq)
1125	{
1126	Pool *pool = solv->pool;
1127	int i;
1128	for (i = 0; i < weakq->count; i++)
1129	{
1130	Rule *r;
1131	if (!queue_contains(solv->recommendsruleq, weakq->elements[i]))
1132	continue;
1133	r = solv->rules + weakq->elements[i];
1134	if (r->d >= 0)
1135	{
1136	POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ")do {if ((pool->debugmask & ((1<<7))) != 0) pool_debug (pool, ((1<<7)), "disabling ");} while (0);
1137	solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE(1<<7), r);
1138	solver_disablerule(solv, r);
1139	}
1140	}
1141	}
1142
1143	/*-------------------------------------------------------------------
1144	*
1145	* analyze_unsolvable_rule
1146	*
1147	* recursion helper used by analyze_unsolvable
1148	*/
1149
1150	static void
1151	analyze_unsolvable_rule(Solver solv, Rule r, Queue weakq, Map rseen)
1152	{
1153	Pool *pool = solv->pool;
1154	int i;
1155	Id why = r - solv->rules;
1156
1157	IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)if ((pool->debugmask & ((1<<7))) != 0)
1158	solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE(1<<7), r);
1159	if (solv->learntrules && why >= solv->learntrules)
1160	{
1161	if (MAPTST(rseen, why - solv->learntrules)((rseen)->map[(why - solv->learntrules) >> 3] & (1 << ((why - solv->learntrules) & 7))))
1162	return;
1163	MAPSET(rseen, why - solv->learntrules)((rseen)->map[(why - solv->learntrules) >> 3] \|= 1 << ((why - solv->learntrules) & 7));
1164	for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1165	if (solv->learnt_pool.elements[i] > 0)
1166	analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], weakq, rseen);
1167	return;
1168	}
1169	if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, why)((&solv->weakrulemap)->map[(why) >> 3] & ( 1 << ((why) & 7))) && weakq)
1170	queue_push(weakq, why);
1171	/* do not add pkg rules to problem */
1172	if (why < solv->pkgrules_end)
1173	return;
1174	/* turn rule into problem */
1175	if (why >= solv->jobrules && why < solv->jobrules_end)
1176	why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1177	/* normalize dup/infarch rules */
1178	if (why > solv->infarchrules && why < solv->infarchrules_end)
1179	{
1180	Id name = pool->solvables[-solv->rules[why].p].name;
1181	while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
1182	why--;
1183	}
1184	if (why > solv->duprules && why < solv->duprules_end)
1185	{
1186	Id name = pool->solvables[-solv->rules[why].p].name;
1187	while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
1188	why--;
1189	}
1190
1191	/* return if problem already countains our rule */
1192	if (solv->problems.count)
1193	{
1194	for (i = solv->problems.count - 1; i >= 0; i--)
1195	if (solv->problems.elements[i] == 0) /* end of last problem reached? */
1196	break;
1197	else if (solv->problems.elements[i] == why)
1198	return;
1199	}
1200	queue_push(&solv->problems, why);
1201	}
1202
1203
1204	/*-------------------------------------------------------------------
1205	*
1206	* analyze_unsolvable (called from setpropagatelearn)
1207	*
1208	* We know that the problem is not solvable. Record all involved
1209	* rules (i.e. the "proof") into solv->learnt_pool.
1210	* Record the learnt pool index and all non-pkg rules into
1211	* solv->problems. (Our solutions to fix the problems are to
1212	* disable those rules.)
1213	*
1214	* If the proof contains at least one weak rule, we disable the
1215	* last of them.
1216	*
1217	* Otherwise we return -1 if disablerules is not set or disable
1218	* _all_ of the problem rules and return 0.
1219	*
1220	* return: 0 - disabled some rules, try again
1221	* -1 - hopeless
1222	*/
1223
1224	static int
1225	analyze_unsolvable(Solver solv, Rule cr, int disablerules)
1226	{
1227	Pool *pool = solv->pool;
1228	Rule *r;
1229	Map involved; /* global to speed things up? */
1230	Map rseen;
1231	Queue weakq;
1232	Id pp, v, vv, why;
1233	int i, idx;
1234	Id *decisionmap = solv->decisionmap;
1235	int oldproblemcount;
1236	int oldlearntpoolcount;
1237	int record_proof = 1;
1238
1239	POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n")do {if ((pool->debugmask & ((1<<7))) != 0) pool_debug (pool, ((1<<7)), "ANALYZE UNSOLVABLE ----------------------\n" );} while (0);
1240	solv->stats_unsolvable++;
1241	oldproblemcount = solv->problems.count;
1242	oldlearntpoolcount = solv->learnt_pool.count;
1243
1244	/* make room for proof index */
1245	/* must update it later, as analyze_unsolvable_rule would confuse
1246	* it with a rule index if we put the real value in already */
1247	queue_push(&solv->problems, 0);
1248
1249	r = cr;
1250	map_init(&involved, pool->nsolvables);
1251	map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1252	queue_init(&weakq);
1253	if (record_proof)
1254	queue_push(&solv->learnt_pool, r - solv->rules);
1255	analyze_unsolvable_rule(solv, r, &weakq, &rseen);
1256	FOR_RULELITERALS(v, pp, r)for (pp = r->d < 0 ? -r->d - 1 : r->d, v = r-> p; v; v = (pp <= 0 ? (pp-- ? 0 : r->w2) : pool->whatprovidesdata [pp++]))
1257	{
1258	if (DECISIONMAP_TRUE(v)((v) > 0 ? (decisionmap[v] > 0) : (decisionmap[-v] < 0))) /* the one true literal */
1259	continue;
1260	vv = v > 0 ? v : -v;
1261	MAPSET(&involved, vv)((&involved)->map[(vv) >> 3] \|= 1 << ((vv) & 7));
1262	}
1263	idx = solv->decisionq.count;
1264	while (idx > 0)
1265	{
1266	v = solv->decisionq.elements[--idx];
1267	vv = v > 0 ? v : -v;
1268	if (!MAPTST(&involved, vv)((&involved)->map[(vv) >> 3] & (1 << ( (vv) & 7))) \|\| vv == SYSTEMSOLVABLE1)
1269	continue;
1270	why = solv->decisionq_why.elements[idx];
1271	assert(why > 0)({ if (why > 0) ; else __assert_fail ("why > 0", "/home/brain/Projects/upstream/libsolv/src/solver.c" , 1271, __PRETTY_FUNCTION__); });
1272	if (record_proof)
1273	queue_push(&solv->learnt_pool, why);
1274	r = solv->rules + why;
1275	analyze_unsolvable_rule(solv, r, &weakq, &rseen);
1276	FOR_RULELITERALS(v, pp, r)for (pp = r->d < 0 ? -r->d - 1 : r->d, v = r-> p; v; v = (pp <= 0 ? (pp-- ? 0 : r->w2) : pool->whatprovidesdata [pp++]))
1277	{
1278	if (DECISIONMAP_TRUE(v)((v) > 0 ? (decisionmap[v] > 0) : (decisionmap[-v] < 0))) /* the one true literal */
1279	continue;
1280	vv = v > 0 ? v : -v;
1281	MAPSET(&involved, vv)((&involved)->map[(vv) >> 3] \|= 1 << ((vv) & 7));
1282	}
1283	}
1284	map_free(&involved);
1285	map_free(&rseen);
1286	queue_push(&solv->problems, 0); /* mark end of this problem */
1287
1288	if (weakq.count)
1289	{
1290	Id lastweak;
1291	/* revert problems */
1292	solv->problems.count = oldproblemcount;
1293	solv->learnt_pool.count = oldlearntpoolcount;
1294	/* find last weak */
1295	lastweak = 0;
1296	for (i = 0; i < weakq.count; i++)
1297	if (weakq.elements[i] > lastweak)
1298	lastweak = weakq.elements[i];
1299	if (lastweak < solv->pkgrules_end && solv->strongrecommends && solv->recommendsruleq && queue_contains(solv->recommendsruleq, lastweak))
1300	{
1301	disable_recommendsrules(solv, &weakq);
1302	queue_free(&weakq);
1303	solver_reset(solv);
1304	return 0;
1305	}
1306	queue_free(&weakq);
1307	if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
1308	v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
1309	else
1310	v = lastweak;
1311	POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ")do {if ((pool->debugmask & ((1<<7))) != 0) pool_debug (pool, ((1<<7)), "disabling ");} while (0);
1312	solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE(1<<7), solv->rules + lastweak);
1313	if (lastweak >= solv->choicerules && lastweak < solv->choicerules_end)
1314	solver_disablechoicerules(solv, solv->rules + lastweak);
1315	solver_disableproblem(solv, v);
1316	if (v < 0)
1317	solver_reenablepolicyrules(solv, -v);
1318	solver_reset(solv);
1319	return 0;
1320	}
1321	queue_free(&weakq);
1322
1323	if (solv->allowuninstall \|\| solv->allowuninstall_all \|\| solv->allowuninstallmap.size)
1324	if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
1325	{
1326	solv->problems.count = oldproblemcount;
1327	solv->learnt_pool.count = oldlearntpoolcount;
1328	solver_reset(solv);
1329	return 0;
1330	}
1331
1332	/* finish proof */
1333	if (record_proof)
1334	{
1335	queue_push(&solv->learnt_pool, 0);
1336	solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1337	}
1338
1339	/* + 2: index + trailing zero */
1340	if (disablerules && oldproblemcount + 2 < solv->problems.count)
1341	{
1342	for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1343	solver_disableproblem(solv, solv->problems.elements[i]);
1344	/* XXX: might want to enable all weak rules again */
1345	solver_reset(solv);
1346	return 0;
1347	}
1348	POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "UNSOLVABLE\n")do {if ((pool->debugmask & ((1<<7))) != 0) pool_debug (pool, ((1<<7)), "UNSOLVABLE\n");} while (0);
1349	return -1;
1350	}
1351
1352
1353	/*-------------------------------------------------------------------
1354	*
1355	* setpropagatelearn
1356	*
1357	* add free decision (solvable to install) to decisionq
1358	* increase level and propagate decision
1359	* return if no conflict.
1360	*
1361	* in conflict case, analyze conflict rule, add resulting
1362	* rule to learnt rule set, make decision from learnt
1363	* rule (always unit) and re-propagate.
1364	*
1365	* returns the new solver level or -1 if unsolvable
1366	*
1367	*/
1368
1369	static int
1370	setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid, Id reason)
1371	{
1372	Pool *pool = solv->pool;
1373	Rule r, lr;
1374
1375	if (decision)
1376	{
1377	level++;
1378	if (decision > 0)
1379	solv->decisionmap[decision] = level;
1380	else
1381	solv->decisionmap[-decision] = -level;
1382	queue_push(&solv->decisionq, decision);
1383	queue_push(&solv->decisionq_why, -ruleid); /* <= 0 -> free decision */
1384	queue_push(&solv->decisionq_reason, reason);
1385	}
1386	assert(ruleid >= 0 && level > 0)({ if (ruleid >= 0 && level > 0) ; else __assert_fail ("ruleid >= 0 && level > 0", "/home/brain/Projects/upstream/libsolv/src/solver.c" , 1386, __PRETTY_FUNCTION__); });
1387	for (;;)
1388	{
1389	r = propagate(solv, level);
1390	if (!r)
1391	break;
1392	if (level == 1)
1393	return analyze_unsolvable(solv, r, disablerules);
1394	POOL_DEBUG(SOLV_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules))do {if ((pool->debugmask & ((1<<6))) != 0) pool_debug (pool, ((1<<6)), "conflict with rule #%d\n", (int)(r - solv ->rules));} while (0);
1395	level = analyze(solv, level, r, &lr);
1396	/* the new rule is unit by design */
1397	decision = lr->p;
1398	solv->decisionmap[decision > 0 ? decision : -decision] = decision > 0 ? level : -level;
1399	queue_push(&solv->decisionq, decision);
1400	queue_push(&solv->decisionq_why, lr - solv->rules);
1401	IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)if ((pool->debugmask & ((1<<6))) != 0)
1402	{
1403	POOL_DEBUG(SOLV_DEBUG_ANALYZE, "decision: ")do {if ((pool->debugmask & ((1<<6))) != 0) pool_debug (pool, ((1<<6)), "decision: ");} while (0);
1404	solver_printruleelement(solv, SOLV_DEBUG_ANALYZE(1<<6), 0, decision);
1405	POOL_DEBUG(SOLV_DEBUG_ANALYZE, "new rule: ")do {if ((pool->debugmask & ((1<<6))) != 0) pool_debug (pool, ((1<<6)), "new rule: ");} while (0);
1406	solver_printrule(solv, SOLV_DEBUG_ANALYZE(1<<6), lr);
1407	}
1408	}
1409	return level;
1410	}
1411
1412	static void
1413	reorder_dq_for_future_installed(Solver solv, int level, Queue dq)
1414	{
1415	Pool *pool = solv->pool;
1416	int i, j, haveone = 0, dqcount = dq->count;
1417	int decisionqcount = solv->decisionq.count;
1418	Id p;
1419	Solvable *s;
1420
1421	/* at the time we process jobrules the installed packages are not kept yet */
1422	/* reorder so that "future-supplemented" packages come first */
1423	FOR_REPO_SOLVABLES(solv->installed, p, s)for (p = (solv->installed)->start, s = (solv->installed )->pool->solvables + p; p < (solv->installed)-> end; p++, s = (solv->installed)->pool->solvables + p ) if (s->repo != (solv->installed)) continue; else
1424	{
1425	if (MAPTST(&solv->noupdate, p - solv->installed->start)((&solv->noupdate)->map[(p - solv->installed-> start) >> 3] & (1 << ((p - solv->installed ->start) & 7))))
1426	continue;
1427	if (solv->decisionmap[p] == 0)
1428	{
1429	if (s->recommends \|\| s->suggests)
1430	queue_push(&solv->decisionq, p);
1431	solv->decisionmap[p] = level + 1;
1432	haveone = 1;
1433	}
1434	}
1435	if (!haveone)
1436	return;
1437	policy_update_recommendsmap(solv);
1438	for (i = 0; i < dqcount; i++)
1439	{
1440	p = dq->elements[i];
1441	if (!(pool->solvables[p].repo == solv->installed \|\| MAPTST(&solv->suggestsmap, p)((&solv->suggestsmap)->map[(p) >> 3] & (1 << ((p) & 7))) \|\| solver_is_enhancing(solv, pool->solvables + p)))
1442	{
1443	queue_push(dq, p);
1444	dq->elements[i] = 0;
1445	}
1446	}
1447	dqcount = dq->count;
1448	for (i = 0; i < dqcount; i++)
1449	{
1450	p = dq->elements[i];
1451	if (p && !(pool->solvables[p].repo == solv->installed \|\| MAPTST(&solv->recommendsmap, p)((&solv->recommendsmap)->map[(p) >> 3] & ( 1 << ((p) & 7))) \|\| solver_is_supplementing(solv, pool->solvables + p)))
1452	{
1453	queue_push(dq, p);
1454	dq->elements[i] = 0;
1455	}
1456	}
1457	for (i = j = 0; i < dq->count; i++)
1458	if (dq->elements[i])
1459	dq->elements[j++] = dq->elements[i];
1460	queue_truncate(dq, j);
1461	FOR_REPO_SOLVABLES(solv->installed, p, s)for (p = (solv->installed)->start, s = (solv->installed )->pool->solvables + p; p < (solv->installed)-> end; p++, s = (solv->installed)->pool->solvables + p ) if (s->repo != (solv->installed)) continue; else
1462	if (solv->decisionmap[p] == level + 1)
1463	solv->decisionmap[p] = 0;
1464	if (solv->decisionq.count != decisionqcount)
1465	{
1466	solv->recommends_index = -1;
1467	queue_truncate(&solv->decisionq, decisionqcount);
1468	}
1469	/* but obey favored maps */
1470	policy_prefer_favored(solv, dq);
1471	}
1472
1473	/*-------------------------------------------------------------------
1474	*
1475	* branch handling
1476	*/
1477
1478	static void
1479	createbranch(Solver solv, int level, Queue dq, Id p, Id data)
1480	{
1481	Pool *pool = solv->pool;
1482	int i;
1483	IF_POOLDEBUG (SOLV_DEBUG_POLICY)if ((pool->debugmask & ((1<<9))) != 0)
1484	{
1485	POOL_DEBUG (SOLV_DEBUG_POLICY, "creating a branch:\n")do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "creating a branch:\n");} while (0);
1486	for (i = 0; i < dq->count; i++)
1487	POOL_DEBUG (SOLV_DEBUG_POLICY, " - %s\n", pool_solvid2str(pool, dq->elements[i]))do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), " - %s\n", pool_solvid2str(pool, dq-> elements[i]));} while (0);
1488	}
1489	queue_push(&solv->branches, -dq->elements[0]);
1490	for (i = 1; i < dq->count; i++)
1491	queue_push(&solv->branches, dq->elements[i]);
1492	queue_push2(&solv->branches, p, data);
1493	queue_push2(&solv->branches, dq->count + 4, level);
1494	}
1495
1496	static int
1497	takebranch(Solver solv, int pos, int end, const char msg, int disablerules)
1498	{
1499	Pool *pool = solv->pool;
1500	int level;
1501	Id p, why, reason;
1502	#if 0
1503	{
1504	int i;
1505	printf("branch group level %d [%d-%d] %d %d:\n", solv->branches.elements[end - 1], start, end, solv->branches.elements[end - 4], solv->branches.elements[end - 3]);
1506	for (i = end - solv->branches.elements[end - 2]; i < end - 4; i++)
1507	printf("%c %c%s\n", i == pos ? 'x' : ' ', solv->branches.elements[i] >= 0 ? ' ' : '-', pool_solvid2str(pool, solv->branches.elements[i] >= 0 ? solv->branches.elements[i] : -solv->branches.elements[i]));
1508	}
1509	#endif
1510	level = solv->branches.elements[end - 1];
1511	p = solv->branches.elements[pos];
1512	solv->branches.elements[pos] = -p;
1513	POOL_DEBUG(SOLV_DEBUG_SOLVER, "%s %d -> %d with %s\n", msg, solv->decisionmap[p], level, pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "%s %d -> %d with %s\n", msg, solv ->decisionmap[p], level, pool_solvid2str(pool, p));} while (0);
1514	/* hack: set level to zero so that revert does not remove the branch */
1515	solv->branches.elements[end - 1] = 0;
1516	revert(solv, level);
1517	solv->branches.elements[end - 1] = level;
1518	/* hack: revert simply sets the count, so we can still access the reverted elements */
1519	why = -solv->decisionq_why.elements[solv->decisionq_why.count];
1520	assert(why >= 0)({ if (why >= 0) ; else __assert_fail ("why >= 0", "/home/brain/Projects/upstream/libsolv/src/solver.c" , 1520, __PRETTY_FUNCTION__); });
1521	reason = solv->decisionq_reason.elements[level + 1];
1522	return setpropagatelearn(solv, level, p, disablerules, why, reason);
1523	}
1524
1525	/*-------------------------------------------------------------------
1526	*
1527	* select and install
1528	*
1529	* install best package from the queue. We add an extra package, inst, if
1530	* provided. See comment in weak install section.
1531	*
1532	* returns the new solver level or -1 if unsolvable
1533	*
1534	*/
1535
1536	static int
1537	selectandinstall(Solver solv, int level, Queue dq, int disablerules, Id ruleid, Id reason)
1538	{
1539	Pool *pool = solv->pool;
1540	Id p;
1541
1542	if (dq->count > 1)
1543	policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE0);
1544	/* if we're resolving rules and didn't resolve the installed packages yet,
1545	* do some special supplements ordering */
1546	if (dq->count > 1 && solv->do_extra_reordering)
1547	reorder_dq_for_future_installed(solv, level, dq);
1548	/* if we have multiple candidates we open a branch */
1549	if (dq->count > 1)
1550	createbranch(solv, level, dq, 0, ruleid);
1551	p = dq->elements[0];
1552	POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "installing %s\n", pool_solvid2str(pool , p));} while (0);
1553	return setpropagatelearn(solv, level, p, disablerules, ruleid, reason);
1554	}
1555
1556
1557	/********************************************************************/
1558	/* Main solver interface */
1559
1560
1561	/*-------------------------------------------------------------------
1562	*
1563	* solver_create
1564	* create solver structure
1565	*
1566	* pool: all available solvables
1567	* installed: installed Solvables
1568	*
1569	*
1570	* Upon solving, rules are created to flag the Solvables
1571	* of the 'installed' Repo as installed.
1572	*/
1573
1574	Solver *
1575	solver_create(Pool *pool)
1576	{
1577	Solver *solv;
1578	solv = (Solver *)solv_calloc(1, sizeof(Solver));
1579	solv->pool = pool;
1580	solv->installed = pool->installed;
1581
1582	solv->allownamechange = 1;
1583
1584	solv->dup_allowdowngrade = 1;
1585	solv->dup_allownamechange = 1;
1586	solv->dup_allowarchchange = 1;
1587	solv->dup_allowvendorchange = 1;
1588
1589	solv->keepexplicitobsoletes = pool->noobsoletesmultiversion ? 0 : 1;
1590
1591	queue_init(&solv->ruletojob);
1592	queue_init(&solv->decisionq);
1593	queue_init(&solv->decisionq_why);
1594	queue_init(&solv->decisionq_reason);
1595	queue_init(&solv->problems);
1596	queue_init(&solv->orphaned);
1597	queue_init(&solv->learnt_why);
1598	queue_init(&solv->learnt_pool);
1599	queue_init(&solv->branches);
1600	queue_init(&solv->weakruleq);
1601	queue_init(&solv->ruleassertions);
1602	queue_init(&solv->addedmap_deduceq);
1603
1604	queue_push(&solv->learnt_pool, 0); /* so that 0 does not describe a proof */
1605
1606	map_init(&solv->recommendsmap, pool->nsolvables);
1607	map_init(&solv->suggestsmap, pool->nsolvables);
1608	map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
1609	solv->recommends_index = 0;
1610
1611	solv->decisionmap = (Id *)solv_calloc(pool->nsolvables, sizeof(Id));
1612	solv->nrules = 1;
1613	solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK63);
1614	memset(solv->rules, 0, sizeof(Rule));
1615
1616	return solv;
1617	}
1618
1619
1620
1621	/*-------------------------------------------------------------------
1622	*
1623	* solver_free
1624	*/
1625
1626	static inline void
1627	queuep_free(Queue **qp)
1628	{
1629	if (!*qp)
1630	return;
1631	queue_free(*qp);
1632	qp = solv_free(qp);
1633	}
1634
1635	static inline void
1636	map_zerosize(Map *m)
1637	{
1638	if (m->size)
1639	{
1640	map_free(m);
1641	map_init(m, 0);
1642	}
1643	}
1644
1645	void
1646	solver_free(Solver *solv)
1647	{
1648	queue_free(&solv->job);
1649	queue_free(&solv->ruletojob);
1650	queue_free(&solv->decisionq);
1651	queue_free(&solv->decisionq_why);
1652	queue_free(&solv->decisionq_reason);
1653	queue_free(&solv->learnt_why);
1654	queue_free(&solv->learnt_pool);
1655	queue_free(&solv->problems);
1656	queue_free(&solv->solutions);
1657	queue_free(&solv->orphaned);
1658	queue_free(&solv->branches);
1659	queue_free(&solv->weakruleq);
1660	queue_free(&solv->ruleassertions);
1661	queue_free(&solv->addedmap_deduceq);
1662	queuep_free(&solv->cleandeps_updatepkgs);
1663	queuep_free(&solv->cleandeps_mistakes);
1664	queuep_free(&solv->update_targets);
1665	queuep_free(&solv->installsuppdepq);
1666	queuep_free(&solv->recommendscplxq);
1667	queuep_free(&solv->suggestscplxq);
1668	queuep_free(&solv->brokenorphanrules);
1669	queuep_free(&solv->favorq);
1670	queuep_free(&solv->recommendsruleq);
1671
1672	map_free(&solv->recommendsmap);
1673	map_free(&solv->suggestsmap);
1674	map_free(&solv->noupdate);
1675	map_free(&solv->weakrulemap);
1676	map_free(&solv->multiversion);
1677
1678	map_free(&solv->updatemap);
1679	map_free(&solv->bestupdatemap);
1680	map_free(&solv->fixmap);
1681	map_free(&solv->dupmap);
1682	map_free(&solv->dupinvolvedmap);
1683	map_free(&solv->droporphanedmap);
1684	map_free(&solv->cleandepsmap);
1685	map_free(&solv->allowuninstallmap);
1686	map_free(&solv->favormap);
1687	map_free(&solv->isdisfavormap);
1688
1689	solv_free(solv->decisionmap);
1690	solv_free(solv->rules);
1691	solv_free(solv->watches);
1692	solv_free(solv->obsoletes);
1693	solv_free(solv->obsoletes_data);
1694	solv_free(solv->specialupdaters);
1695	solv_free(solv->choicerules_ref);
1696	solv_free(solv->bestrules_pkg);
1697	solv_free(solv->yumobsrules_info);
1698	solv_free(solv->instbuddy);
1699	solv_free(solv);
1700	}
1701
1702	int
1703	solver_get_flag(Solver *solv, int flag)
1704	{
1705	switch (flag)
1706	{
1707	case SOLVER_FLAG_ALLOW_DOWNGRADE1:
1708	return solv->allowdowngrade;
1709	case SOLVER_FLAG_ALLOW_NAMECHANGE10:
1710	return solv->allownamechange;
1711	case SOLVER_FLAG_ALLOW_ARCHCHANGE2:
1712	return solv->allowarchchange;
1713	case SOLVER_FLAG_ALLOW_VENDORCHANGE3:
1714	return solv->allowvendorchange;
1715	case SOLVER_FLAG_ALLOW_UNINSTALL4:
1716	return solv->allowuninstall;
1717	case SOLVER_FLAG_NO_UPDATEPROVIDE5:
1718	return solv->noupdateprovide;
1719	case SOLVER_FLAG_SPLITPROVIDES6:
1720	return solv->dosplitprovides;
1721	case SOLVER_FLAG_IGNORE_RECOMMENDED7:
1722	return solv->dontinstallrecommended;
1723	case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED8:
1724	return solv->addalreadyrecommended;
1725	case SOLVER_FLAG_NO_INFARCHCHECK9:
1726	return solv->noinfarchcheck;
1727	case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES11:
1728	return solv->keepexplicitobsoletes;
1729	case SOLVER_FLAG_BEST_OBEY_POLICY12:
1730	return solv->bestobeypolicy;
1731	case SOLVER_FLAG_NO_AUTOTARGET13:
1732	return solv->noautotarget;
1733	case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE14:
1734	return solv->dup_allowdowngrade;
1735	case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE17:
1736	return solv->dup_allownamechange;
1737	case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE15:
1738	return solv->dup_allowarchchange;
1739	case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE16:
1740	return solv->dup_allowvendorchange;
1741	case SOLVER_FLAG_KEEP_ORPHANS18:
1742	return solv->keep_orphans;
1743	case SOLVER_FLAG_BREAK_ORPHANS19:
1744	return solv->break_orphans;
1745	case SOLVER_FLAG_FOCUS_INSTALLED20:
1746	return solv->focus_installed;
1747	case SOLVER_FLAG_FOCUS_BEST24:
1748	return solv->focus_best;
1749	case SOLVER_FLAG_YUM_OBSOLETES21:
1750	return solv->do_yum_obsoletes;
1751	case SOLVER_FLAG_NEED_UPDATEPROVIDE22:
1752	return solv->needupdateprovide;
1753	case SOLVER_FLAG_URPM_REORDER23:
1754	return solv->urpmreorder;
1755	case SOLVER_FLAG_STRONG_RECOMMENDS25:
1756	return solv->strongrecommends;
1757	case SOLVER_FLAG_INSTALL_ALSO_UPDATES26:
1758	return solv->install_also_updates;
1759	default:
1760	break;
1761	}
1762	return -1;
1763	}
1764
1765	int
1766	solver_set_flag(Solver *solv, int flag, int value)
1767	{
1768	int old = solver_get_flag(solv, flag);
1769	switch (flag)
1770	{
1771	case SOLVER_FLAG_ALLOW_DOWNGRADE1:
1772	solv->allowdowngrade = value;
1773	break;
1774	case SOLVER_FLAG_ALLOW_NAMECHANGE10:
1775	solv->allownamechange = value;
1776	break;
1777	case SOLVER_FLAG_ALLOW_ARCHCHANGE2:
1778	solv->allowarchchange = value;
1779	break;
1780	case SOLVER_FLAG_ALLOW_VENDORCHANGE3:
1781	solv->allowvendorchange = value;
1782	break;
1783	case SOLVER_FLAG_ALLOW_UNINSTALL4:
1784	solv->allowuninstall = value;
1785	break;
1786	case SOLVER_FLAG_NO_UPDATEPROVIDE5:
1787	solv->noupdateprovide = value;
1788	break;
1789	case SOLVER_FLAG_SPLITPROVIDES6:
1790	solv->dosplitprovides = value;
1791	break;
1792	case SOLVER_FLAG_IGNORE_RECOMMENDED7:
1793	solv->dontinstallrecommended = value;
1794	break;
1795	case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED8:
1796	solv->addalreadyrecommended = value;
1797	break;
1798	case SOLVER_FLAG_NO_INFARCHCHECK9:
1799	solv->noinfarchcheck = value;
1800	break;
1801	case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES11:
1802	solv->keepexplicitobsoletes = value;
1803	break;
1804	case SOLVER_FLAG_BEST_OBEY_POLICY12:
1805	solv->bestobeypolicy = value;
1806	break;
1807	case SOLVER_FLAG_NO_AUTOTARGET13:
1808	solv->noautotarget = value;
1809	break;
1810	case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE14:
1811	solv->dup_allowdowngrade = value;
1812	break;
1813	case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE17:
1814	solv->dup_allownamechange = value;
1815	break;
1816	case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE15:
1817	solv->dup_allowarchchange = value;
1818	break;
1819	case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE16:
1820	solv->dup_allowvendorchange = value;
1821	break;
1822	case SOLVER_FLAG_KEEP_ORPHANS18:
1823	solv->keep_orphans = value;
1824	break;
1825	case SOLVER_FLAG_BREAK_ORPHANS19:
1826	solv->break_orphans = value;
1827	break;
1828	case SOLVER_FLAG_FOCUS_INSTALLED20:
1829	solv->focus_installed = value;
1830	break;
1831	case SOLVER_FLAG_FOCUS_BEST24:
1832	solv->focus_best = value;
1833	break;
1834	case SOLVER_FLAG_YUM_OBSOLETES21:
1835	solv->do_yum_obsoletes = value;
1836	break;
1837	case SOLVER_FLAG_NEED_UPDATEPROVIDE22:
1838	solv->needupdateprovide = value;
1839	break;
1840	case SOLVER_FLAG_URPM_REORDER23:
1841	solv->urpmreorder = value;
1842	break;
1843	case SOLVER_FLAG_STRONG_RECOMMENDS25:
1844	solv->strongrecommends = value;
1845	break;
1846	case SOLVER_FLAG_INSTALL_ALSO_UPDATES26:
1847	solv->install_also_updates = value;
1848	break;
1849	default:
1850	break;
1851	}
1852	return old;
1853	}
1854
1855	static int
1856	resolve_jobrules(Solver solv, int level, int disablerules, Queue dq)
1857	{
1858	Pool *pool = solv->pool;
1859	int oldlevel = level;
1860	int i, olevel;
1861	Rule *r;
1862
1863	POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n")do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "resolving job rules\n");} while (0);
1864	for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1865	{
1866	Id l, pp;
1867	if (r->d < 0) /* ignore disabled rules */
1868	continue;
1869	queue_empty(dq);
1870	FOR_RULELITERALS(l, pp, r)for (pp = r->d < 0 ? -r->d - 1 : r->d, l = r-> p; l; l = (pp <= 0 ? (pp-- ? 0 : r->w2) : pool->whatprovidesdata [pp++]))
1871	{
1872	if (l < 0)
1873	{
1874	if (solv->decisionmap[-l] <= 0)
1875	break;
1876	}
1877	else
1878	{
1879	if (solv->decisionmap[l] > 0)
1880	break;
1881	if (solv->decisionmap[l] == 0)
1882	queue_push(dq, l);
1883	}
1884	}
1885	if (l \|\| !dq->count)
1886	continue;
1887	/* prune to installed if not updating */
1888	if (dq->count > 1 && solv->installed && !solv->updatemap_all &&
1889	!solv->install_also_updates &&
1890	!(solv->job.elements[solv->ruletojob.elements[i - solv->jobrules]] & SOLVER_ORUPDATE0x080000))
1891	{
1892	int j = dq->count, k;
1893	if (solv->updatemap.size)
1894	{
1895	/* do not prune if an installed package wants to be updated */
1896	for (j = 0; j < dq->count; j++)
1897	if (pool->solvables[dq->elements[j]].repo == solv->installed
1898	&& MAPTST(&solv->updatemap, dq->elements[j] - solv->installed->start)((&solv->updatemap)->map[(dq->elements[j] - solv ->installed->start) >> 3] & (1 << ((dq-> elements[j] - solv->installed->start) & 7))))
1899	break;
1900	}
1901	if (j == dq->count)
1902	{
1903	for (j = k = 0; j < dq->count; j++)
1904	if (pool->solvables[dq->elements[j]].repo == solv->installed)
1905	dq->elements[k++] = dq->elements[j];
1906	if (k)
1907	dq->count = k;
1908	}
1909	}
1910	olevel = level;
1911	level = selectandinstall(solv, level, dq, disablerules, i, SOLVER_REASON_RESOLVE_JOB3);
1912	if (level <= olevel)
1913	{
1914	if (level == olevel)
1915	{
1916	i--;
1917	r--;
1918	continue; /* try something else */
1919	}
1920	if (level < oldlevel)
1921	return level;
1922	/* redo from start of jobrules */
1923	i = solv->jobrules - 1;
1924	r = solv->rules + i;
1925	}
1926	}
1927	return level;
1928	}
1929
1930	static int
1931	cleandeps_check_mistakes(Solver *solv)
1932	{
1933	Pool *pool = solv->pool;
1934	Rule *r;
1935	Id p, pp;
1936	int i;
1937	int mademistake = 0;
1938
1939	if (!solv->cleandepsmap.size)
1940	return 0;
1941	/* check for mistakes */
1942	for (i = solv->installed->start; i < solv->installed->end; i++)
1943	{
1944	if (!MAPTST(&solv->cleandepsmap, i - solv->installed->start)((&solv->cleandepsmap)->map[(i - solv->installed ->start) >> 3] & (1 << ((i - solv->installed ->start) & 7))))
1945	continue;
1946	r = solv->rules + solv->featurerules + (i - solv->installed->start);
1947	/* a mistake is when the featurerule is true but the updaterule is false */
1948	if (!r->p)
1949	continue;
1950	FOR_RULELITERALS(p, pp, r)for (pp = r->d < 0 ? -r->d - 1 : r->d, p = r-> p; p; p = (pp <= 0 ? (pp-- ? 0 : r->w2) : pool->whatprovidesdata [pp++]))
1951	if (p > 0 && solv->decisionmap[p] > 0)
1952	break;
1953	if (!p)
1954	continue; /* feature rule is not true */
1955	r = solv->rules + solv->updaterules + (i - solv->installed->start);
1956	if (!r->p)
1957	continue;
1958	FOR_RULELITERALS(p, pp, r)for (pp = r->d < 0 ? -r->d - 1 : r->d, p = r-> p; p; p = (pp <= 0 ? (pp-- ? 0 : r->w2) : pool->whatprovidesdata [pp++]))
1959	if (p > 0 && solv->decisionmap[p] > 0)
1960	break;
1961	if (p)
1962	continue; /* update rule is true */
1963	POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: ")do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "cleandeps mistake: ");} while (0);
1964	solver_printruleclass(solv, SOLV_DEBUG_SOLVER(1<<12), r);
1965	POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: ")do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "feature rule: ");} while (0);
1966	solver_printruleclass(solv, SOLV_DEBUG_SOLVER(1<<12), solv->rules + solv->featurerules + (i - solv->installed->start));
1967	if (!solv->cleandeps_mistakes)
1968	{
1969	solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue));
1970	queue_init(solv->cleandeps_mistakes);
1971	}
1972	queue_push(solv->cleandeps_mistakes, i);
1973	MAPCLR(&solv->cleandepsmap, i - solv->installed->start)((&solv->cleandepsmap)->map[(i - solv->installed ->start) >> 3] &= ~(1 << ((i - solv->installed ->start) & 7)));
1974	solver_reenablepolicyrules_cleandeps(solv, i);
1975	mademistake = 1;
1976	}
1977	return mademistake;
1978	}
1979
1980	static void
1981	prune_to_update_targets(Solver solv, Id cp, Queue *q)
1982	{
1983	int i, j;
1984	Id p, *cp2;
1985	for (i = j = 0; i < q->count; i++)
1986	{
1987	p = q->elements[i];
1988	for (cp2 = cp; *cp2; cp2++)
1989	if (*cp2 == p)
1990	{
1991	q->elements[j++] = p;
1992	break;
1993	}
1994	}
1995	queue_truncate(q, j);
1996	}
1997
1998	static int
1999	resolve_installed(Solver solv, int level, int disablerules, Queue dq)
2000	{
2001	Pool *pool = solv->pool;
2002	Repo *installed = solv->installed;
2003	int i, n, pass;
2004	int installedpos = solv->installedpos;
2005	Solvable *s;
2006	Id p, pp;
2007	int olevel, origlevel = level;
2008
2009	POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n")do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "resolving installed packages\n");} while (0);
2010	if (!installedpos)
2011	installedpos = installed->start;
2012	/* we use two passes if we need to update packages
2013	* to create a better user experience */
2014	for (pass = solv->updatemap.size ? 0 : 1; pass < 2; )
2015	{
2016	int passlevel = level;
2017	Id *specialupdaters = solv->specialupdaters;
2018	/* start with installedpos, the position that gave us problems the last time */
2019	for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
2020	{
2021	Rule r, rr;
2022	Id d;
2023
2024	if (i == installed->end)
2025	i = installed->start;
2026	s = pool->solvables + i;
2027	if (s->repo != installed)
2028	continue;
2029
2030	if (solv->decisionmap[i] > 0 && (!specialupdaters \|\| !specialupdaters[i - installed->start]))
2031	continue; /* already decided */
2032	if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start)((&solv->updatemap)->map[(i - installed->start) >> 3] & (1 << ((i - installed->start) & 7))))
2033	continue; /* updates first */
2034	r = solv->rules + solv->updaterules + (i - installed->start);
2035	rr = r;
2036	if (!rr->p \|\| rr->d < 0) /* disabled -> look at feature rule */
2037	rr -= solv->installed->end - solv->installed->start;
2038	if (!rr->p) /* identical to update rule? */
2039	rr = r;
2040	if (!rr->p)
2041	continue; /* orpaned package or pseudo package */
2042
2043	/* check if we should update this package to the latest version
2044	* noupdate is set for erase jobs, in that case we want to deinstall
2045	* the installed package and not replace it with a newer version
2046	* rr->p != i is for dup jobs where the installed package cannot be kept */
2047	if (dq->count)
2048	queue_empty(dq);
2049	if (!MAPTST(&solv->noupdate, i - installed->start)((&solv->noupdate)->map[(i - installed->start) >> 3] & (1 << ((i - installed->start) & 7))) && (solv->decisionmap[i] < 0 \|\| solv->updatemap_all \|\| (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)((&solv->updatemap)->map[(i - installed->start) >> 3] & (1 << ((i - installed->start) & 7)))) \|\| (rr->p && rr->p != i)))
2050	{
2051	if (specialupdaters && (d = specialupdaters[i - installed->start]) != 0)
2052	{
2053	/* special multiversion handling, make sure best version is chosen */
2054	if (rr->p == i && solv->decisionmap[i] >= 0)
2055	queue_push(dq, i);
2056	while ((p = pool->whatprovidesdata[d++]) != 0)
2057	if (solv->decisionmap[p] >= 0)
2058	queue_push(dq, p);
2059	if (dq->count && solv->update_targets && solv->update_targets->elements[i - installed->start])
2060	prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], dq);
2061	if (dq->count)
2062	{
2063	policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE0);
2064	p = dq->elements[0];
2065	if (p != i && solv->decisionmap[p] == 0)
2066	{
2067	rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2068	if (!rr->p) /* update rule == feature rule? */
2069	rr = rr - solv->featurerules + solv->updaterules;
2070	dq->count = 1;
2071	}
2072	else
2073	dq->count = 0;
2074	}
2075	}
2076	else
2077	{
2078	/* update to best package of the update rule */
2079	FOR_RULELITERALS(p, pp, rr)for (pp = rr->d < 0 ? -rr->d - 1 : rr->d, p = rr-> p; p; p = (pp <= 0 ? (pp-- ? 0 : rr->w2) : pool->whatprovidesdata [pp++]))
2080	{
2081	if (solv->decisionmap[p] > 0)
2082	{
2083	dq->count = 0; /* already fulfilled */
2084	break;
2085	}
2086	if (!solv->decisionmap[p])
2087	queue_push(dq, p);
2088	}
2089	}
2090	}
2091	if (dq->count && solv->update_targets && solv->update_targets->elements[i - installed->start])
2092	prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], dq);
2093	/* install best version */
2094	if (dq->count)
2095	{
2096	olevel = level;
2097	level = selectandinstall(solv, level, dq, disablerules, rr - solv->rules, SOLVER_REASON_UPDATE_INSTALLED4);
2098	if (level <= olevel)
2099	{
2100	if (level < passlevel)
2101	break; /* trouble */
2102	if (level < olevel)
2103	n = installed->start; /* redo all */
2104	i--;
2105	n--;
2106	continue;
2107	}
2108	}
2109	/* if still undecided keep package */
2110	if (solv->decisionmap[i] == 0)
2111	{
2112	olevel = level;
2113	if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start)((&solv->cleandepsmap)->map[(i - installed->start ) >> 3] & (1 << ((i - installed->start) & 7))))
2114	{
2115	#if 0
2116	POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i))do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "cleandeps erasing %s\n", pool_solvid2str (pool, i));} while (0);
2117	level = setpropagatelearn(solv, level, -i, disablerules, 0, SOLVER_REASON_CLEANDEPS_ERASE5);
2118	#else
2119	continue;
2120	#endif
2121	}
2122	else
2123	{
2124	POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i))do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "keeping %s\n", pool_solvid2str(pool, i ));} while (0);
2125	level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules, SOLVER_REASON_KEEP_INSTALLED2);
2126	}
2127	if (level <= olevel)
2128	{
2129	if (level < passlevel)
2130	break; /* trouble */
2131	if (level < olevel)
2132	n = installed->start; /* redo all */
2133	i--;
2134	n--;
2135	continue; /* retry with learnt rule */
2136	}
2137	}
2138	}
2139	if (n < installed->end)
2140	{
2141	installedpos = i; /* retry problem solvable next time */
2142	if (level < origlevel)
2143	break; /* ran into trouble */
2144	/* re-run all passes */
2145	pass = solv->updatemap.size ? 0 : 1;
2146	continue;
2147	}
2148	/* reset installedpos, advance to next pass */
2149	installedpos = installed->start;
2150	pass++;
2151	}
2152	solv->installedpos = installedpos;
2153	return level;
2154	}
2155
2156	static int
2157	resolve_dependencies(Solver solv, int level, int disablerules, Queue dq)
2158	{
2159	Pool *pool = solv->pool;
2160	int i, j, n;
2161	int postponed;
2162	Rule *r;
2163	int origlevel = level;
2164	Id p, *dp;
2165
2166	/*
2167	* decide
2168	*/
2169	POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n")do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "deciding unresolved rules\n");} while (0);
2170	postponed = 0;
2171	for (i = 1, n = 1; ; i++, n++)
2172	{
2173	if (n >= solv->nrules)
2174	{
2175	if (postponed <= 0)
2176	break;
2177	i = postponed;
2178	postponed = -1;
2179	n = 1;
2180	}
2181	if (i == solv->nrules)
2182	i = 1;
2183	r = solv->rules + i;
2184	if (r->d < 0) /* ignore disabled rules */
2185	continue;
2186	if (r->p < 0) /* most common cases first */
2187	{
2188	if (r->d == 0 \|\| solv->decisionmap[-r->p] <= 0)
2189	continue;
2190	}
2191	if (dq->count)
2192	queue_empty(dq);
2193	if (r->d == 0)
2194	{
2195	/* binary or unary rule */
2196	/* need two positive undecided literals, r->p already checked above */
2197	if (r->w2 <= 0)
2198	continue;
2199	if (solv->decisionmap[r->p] \|\| solv->decisionmap[r->w2])
2200	continue;
2201	queue_push(dq, r->p);
2202	queue_push(dq, r->w2);
2203	}
2204	else
2205	{
2206	/* make sure that
2207	* all negative literals are installed
2208	* no positive literal is installed
2209	* i.e. the rule is not fulfilled and we
2210	* just need to decide on the positive literals
2211	* (decisionmap[-r->p] for the r->p < 0 case is already checked above)
2212	*/
2213	if (r->p >= 0)
2214	{
2215	if (solv->decisionmap[r->p] > 0)
2216	continue;
2217	if (solv->decisionmap[r->p] == 0)
2218	queue_push(dq, r->p);
2219	}
2220	dp = pool->whatprovidesdata + r->d;
2221	while ((p = *dp++) != 0)
2222	{
2223	if (p < 0)
2224	{
2225	if (solv->decisionmap[-p] <= 0)
2226	break;
2227	}
2228	else
2229	{
2230	if (solv->decisionmap[p] > 0)
2231	break;
2232	if (solv->decisionmap[p] == 0)
2233	queue_push(dq, p);
2234	}
2235	}
2236	if (p)
2237	continue;
2238	}
2239	IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)if ((pool->debugmask & ((1<<5))) != 0)
2240	{
2241	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ")do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), "unfulfilled ");} while (0);
2242	solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE(1<<5), r);
2243	}
2244	/* dq->count < 2 cannot happen as this means that
2245	* the rule is unit */
2246	assert(dq->count > 1)({ if (dq->count > 1) ; else __assert_fail ("dq->count > 1" , "/home/brain/Projects/upstream/libsolv/src/solver.c", 2246, __PRETTY_FUNCTION__); });
2247
2248	/* prune to cleandeps packages */
2249	if (solv->cleandepsmap.size && solv->installed)
2250	{
2251	Repo *installed = solv->installed;
2252	for (j = 0; j < dq->count; j++)
2253	if (pool->solvables[dq->elements[j]].repo == installed && MAPTST(&solv->cleandepsmap, dq->elements[j] - installed->start)((&solv->cleandepsmap)->map[(dq->elements[j] - installed ->start) >> 3] & (1 << ((dq->elements[j ] - installed->start) & 7))))
2254	break;
2255	if (j < dq->count)
2256	{
2257	dq->elements[0] = dq->elements[j];
2258	queue_truncate(dq, 1);
2259	}
2260	}
2261
2262	if (dq->count > 1 && postponed >= 0)
2263	{
2264	policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE_NOREORDER3);
2265	if (dq->count > 1)
2266	{
2267	if (!postponed)
2268	postponed = i;
2269	continue;
2270	}
2271	}
2272
2273	level = selectandinstall(solv, level, dq, disablerules, r - solv->rules, SOLVER_REASON_RESOLVE6);
2274	if (level < origlevel)
2275	break; /* trouble */
2276	/* something changed, so look at all rules again */
2277	n = 0;
2278	}
2279	return level;
2280	}
2281
2282
2283	#ifdef ENABLE_COMPLEX_DEPS
2284
2285	static void
2286	add_complex_recommends(Solver solv, Id rec, Queue dq, Map *dqmap)
2287	{
2288	Pool *pool = solv->pool;
2289	int oldcnt = dq->count;
2290	int cutcnt, blkcnt;
2291	Id p;
2292	int i, j;
2293
2294	#if 0
2295	printf("ADD_COMPLEX_RECOMMENDS %s\n", pool_dep2str(pool, rec));
2296	#endif
2297	i = pool_normalize_complex_dep(pool, rec, dq, CPLXDEPS_EXPAND(1 << 1));
2298	if (i == 0 \|\| i == 1)
2299	return;
2300	cutcnt = dq->count;
2301	for (i = oldcnt; i < cutcnt; i++)
2302	{
2303	blkcnt = dq->count;
2304	for (; (p = dq->elements[i]) != 0; i++)
2305	{
2306	if (p < 0)
2307	{
2308	if (solv->decisionmap[-p] <= 0)
2309	break;
2310	continue;
2311	}
2312	if (solv->decisionmap[p] > 0)
2313	{
2314	queue_truncate(dq, blkcnt);
2315	break;
2316	}
2317	if (dqmap)
2318	{
2319	if (!MAPTST(dqmap, p)((dqmap)->map[(p) >> 3] & (1 << ((p) & 7))))
2320	continue;
2321	}
2322	else
2323	{
2324	if (solv->decisionmap[p] < 0)
2325	continue;
2326	if (solv->dupmap_all && solv->installed && pool->solvables[p].repo == solv->installed && (solv->droporphanedmap_all \|\| (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start)((&solv->droporphanedmap)->map[(p - solv->installed ->start) >> 3] & (1 << ((p - solv->installed ->start) & 7))))))
2327	continue;
2328	}
2329	queue_push(dq, p);
2330	}
2331	while (dq->elements[i])
2332	i++;
2333	}
2334	queue_deleten(dq, oldcnt, cutcnt - oldcnt);
2335	/* unify */
2336	if (dq->count != oldcnt)
2337	{
2338	for (j = oldcnt; j < dq->count; j++)
2339	{
2340	p = dq->elements[j];
2341	for (i = 0; i < j; i++)
2342	if (dq->elements[i] == p)
2343	{
2344	dq->elements[j] = 0;
2345	break;
2346	}
2347	}
2348	for (i = j = oldcnt; j < dq->count; j++)
2349	if (dq->elements[j])
2350	dq->elements[i++] = dq->elements[j];
2351	queue_truncate(dq, i);
2352	}
2353	#if 0
2354	printf("RETURN:\n");
2355	for (i = oldcnt; i < dq->count; i++)
2356	printf(" - %s\n", pool_solvid2str(pool, dq->elements[i]));
2357	#endif
2358	}
2359
2360	static void
2361	do_complex_recommendations(Solver solv, Id rec, Map m, int noselected)
2362	{
2363	Pool *pool = solv->pool;
2364	Queue dq;
2365	Id p;
2366	int i, blk;
2367
2368	#if 0
2369	printf("DO_COMPLEX_RECOMMENDATIONS %s\n", pool_dep2str(pool, rec));
2370	#endif
2371	queue_init(&dq);
2372	i = pool_normalize_complex_dep(pool, rec, &dq, CPLXDEPS_EXPAND(1 << 1));
2373	if (i == 0 \|\| i == 1)
2374	{
2375	queue_free(&dq);
2376	return;
2377	}
2378	for (i = 0; i < dq.count; i++)
2379	{
2380	blk = i;
2381	for (; (p = dq.elements[i]) != 0; i++)
2382	{
2383	if (p < 0)
2384	{
2385	if (solv->decisionmap[-p] <= 0)
2386	break;
2387	continue;
2388	}
2389	if (solv->decisionmap[p] > 0)
2390	{
2391	if (noselected)
2392	break;
2393	MAPSET(m, p)((m)->map[(p) >> 3] \|= 1 << ((p) & 7));
2394	for (i++; (p = dq.elements[i]) != 0; i++)
2395	if (p > 0 && solv->decisionmap[p] > 0)
2396	MAPSET(m, p)((m)->map[(p) >> 3] \|= 1 << ((p) & 7));
2397	p = 1;
2398	break;
2399	}
2400	}
2401	if (!p)
2402	{
2403	for (i = blk; (p = dq.elements[i]) != 0; i++)
2404	if (p > 0)
2405	MAPSET(m, p)((m)->map[(p) >> 3] \|= 1 << ((p) & 7));
2406	}
2407	while (dq.elements[i])
2408	i++;
2409	}
2410	queue_free(&dq);
2411	}
2412
2413	#endif
2414
2415	static void
2416	prune_disfavored(Solver solv, Queue plist)
2417	{
2418	int i, j;
2419	if (!solv->isdisfavormap.size)
2420	return;
2421	for (i = j = 0; i < plist->count; i++)
2422	{
2423	Id p = plist->elements[i];
2424	if (!MAPTST(&solv->isdisfavormap, p)((&solv->isdisfavormap)->map[(p) >> 3] & ( 1 << ((p) & 7))))
2425	plist->elements[j++] = p;
2426	}
2427	if (i != j)
2428	queue_truncate(plist, j);
2429	}
2430
2431	static int
2432	resolve_weak(Solver solv, int level, int disablerules, Queue dq, Queue dqs, int rerunp)
2433	{
2434	Pool *pool = solv->pool;
2435	int i, j, qcount;
2436	int olevel;
2437	Solvable *s;
2438	Map dqmap;
2439	int decisioncount;
2440	Id p;
2441
2442	POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n")do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "installing recommended packages\n");} while (0);
2443	if (dq->count)
2444	queue_empty(dq); /* recommended packages */
2445	if (dqs->count)
2446	queue_empty(dqs); /* supplemented packages */
2447	for (i = 1; i < pool->nsolvables; i++)
2448	{
2449	if (solv->decisionmap[i] < 0)
2450	continue;
2451	s = pool->solvables + i;
2452	if (solv->decisionmap[i] > 0)
2453	{
2454	/* installed, check for recommends */
2455	Id *recp, rec, pp, p;
2456	if (!solv->addalreadyrecommended && s->repo == solv->installed)
2457	continue;
2458	/* XXX need to special case AND ? */
2459	if (s->recommends)
2460	{
2461	recp = s->repo->idarraydata + s->recommends;
2462	while ((rec = *recp++) != 0)
2463	{
2464	#ifdef ENABLE_COMPLEX_DEPS
2465	if (pool_is_complex_dep(pool, rec))
2466	{
2467	add_complex_recommends(solv, rec, dq, 0);
2468	continue;
2469	}
2470	#endif
2471	qcount = dq->count;
2472	FOR_PROVIDES(p, pp, rec)for (pp = pool_whatprovides(pool, rec) ; (p = pool->whatprovidesdata [pp++]) != 0; )
2473	{
2474	if (solv->decisionmap[p] > 0)
2475	{
2476	dq->count = qcount;
2477	break;
2478	}
2479	else if (solv->decisionmap[p] == 0)
2480	{
2481	if (solv->dupmap_all && solv->installed && pool->solvables[p].repo == solv->installed && (solv->droporphanedmap_all \|\| (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start)((&solv->droporphanedmap)->map[(p - solv->installed ->start) >> 3] & (1 << ((p - solv->installed ->start) & 7))))))
2482	continue;
2483	queue_pushunique(dq, p);
2484	}
2485	}
2486	}
2487	}
2488	}
2489	else
2490	{
2491	/* not yet installed, check if supplemented */
2492	if (!s->supplements)
2493	continue;
2494	if (!pool_installable(pool, s))
2495	continue;
2496	if (!solver_is_supplementing(solv, s))
2497	continue;
2498	if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all \|\| (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start)((&solv->droporphanedmap)->map[(i - solv->installed ->start) >> 3] & (1 << ((i - solv->installed ->start) & 7))))))
2499	continue;
2500	if (solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, i)((&solv->isdisfavormap)->map[(i) >> 3] & ( 1 << ((i) & 7))))
2501	continue; /* disfavored supplements, do not install */
2502	queue_push(dqs, i);
2503	}
2504	}
2505
2506	/* filter out disfavored recommended packages */
2507	if (dq->count && solv->isdisfavormap.size)
2508	prune_disfavored(solv, dq);
2509
2510	/* filter out all packages obsoleted by installed packages */
2511	/* this is no longer needed if we have (and trust) reverse obsoletes */
2512	if ((dqs->count \|\| dq->count) && solv->installed)
2513	{
2514	Map obsmap;
2515	Id obs, *obsp, po, ppo;
2516
2517	map_init(&obsmap, pool->nsolvables);
2518	for (p = solv->installed->start; p < solv->installed->end; p++)
2519	{
2520	s = pool->solvables + p;
2521	if (s->repo != solv->installed \|\| !s->obsoletes)
2522	continue;
2523	if (solv->decisionmap[p] <= 0)
2524	continue;
2525	if (!solv->keepexplicitobsoletes && solv->multiversion.size && MAPTST(&solv->multiversion, p)((&solv->multiversion)->map[(p) >> 3] & ( 1 << ((p) & 7))))
2526	continue;
2527	obsp = s->repo->idarraydata + s->obsoletes;
2528	/* foreach obsoletes */
2529	while ((obs = *obsp++) != 0)
2530	FOR_PROVIDES(po, ppo, obs)for (ppo = pool_whatprovides(pool, obs) ; (po = pool->whatprovidesdata [ppo++]) != 0; )
2531	{
2532	Solvable *pos = pool->solvables + po;
2533	if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pos, obs))
2534	continue;
2535	if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pos))
2536	continue;
2537	MAPSET(&obsmap, po)((&obsmap)->map[(po) >> 3] \|= 1 << ((po) & 7));
2538	}
2539	}
2540	for (i = j = 0; i < dqs->count; i++)
2541	if (!MAPTST(&obsmap, dqs->elements[i])((&obsmap)->map[(dqs->elements[i]) >> 3] & (1 << ((dqs->elements[i]) & 7))))
2542	dqs->elements[j++] = dqs->elements[i];
2543	dqs->count = j;
2544	for (i = j = 0; i < dq->count; i++)
2545	if (!MAPTST(&obsmap, dq->elements[i])((&obsmap)->map[(dq->elements[i]) >> 3] & (1 << ((dq->elements[i]) & 7))))
2546	dq->elements[j++] = dq->elements[i];
2547	dq->count = j;
2548	map_free(&obsmap);
2549	}
2550
2551	/* filter out all already supplemented packages if requested */
2552	if (!solv->addalreadyrecommended && dqs->count)
2553	{
2554	/* filter out old supplements */
2555	for (i = j = 0; i < dqs->count; i++)
2556	{
2557	p = dqs->elements[i];
2558	s = pool->solvables + p;
2559	if (s->supplements && solver_is_supplementing_alreadyinstalled(solv, s))
2560	dqs->elements[j++] = p;
2561	}
2562	dqs->count = j;
2563	}
2564
2565	/* multiversion doesn't mix well with supplements.
2566	* filter supplemented packages where we already decided
2567	* to install a different version (see bnc#501088) */
2568	if (dqs->count && solv->multiversion.size)
2569	{
2570	for (i = j = 0; i < dqs->count; i++)
2571	{
2572	p = dqs->elements[i];
2573	if (MAPTST(&solv->multiversion, p)((&solv->multiversion)->map[(p) >> 3] & ( 1 << ((p) & 7))))
2574	{
2575	Id p2, pp2;
2576	s = pool->solvables + p;
2577	FOR_PROVIDES(p2, pp2, s->name)for (pp2 = pool_whatprovides(pool, s->name) ; (p2 = pool-> whatprovidesdata[pp2++]) != 0; )
2578	if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2579	break;
2580	if (p2)
2581	continue; /* ignore this package */
2582	}
2583	dqs->elements[j++] = p;
2584	}
2585	dqs->count = j;
2586	}
2587
2588	/* implicitobsoleteusescolors doesn't mix well with supplements.
2589	* filter supplemented packages where we already decided
2590	* to install a different architecture */
2591	if (dqs->count && pool->implicitobsoleteusescolors)
2592	{
2593	for (i = j = 0; i < dqs->count; i++)
2594	{
2595	Id p2, pp2;
2596	p = dqs->elements[i];
2597	s = pool->solvables + p;
2598	FOR_PROVIDES(p2, pp2, s->name)for (pp2 = pool_whatprovides(pool, s->name) ; (p2 = pool-> whatprovidesdata[pp2++]) != 0; )
2599	if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name && pool->solvables[p2].arch != s->arch)
2600	break;
2601	if (p2)
2602	continue; /* ignore this package */
2603	dqs->elements[j++] = p;
2604	}
2605	dqs->count = j;
2606	}
2607
2608	/* make dq contain both recommended and supplemented pkgs */
2609	if (dqs->count)
2610	{
2611	for (i = 0; i < dqs->count; i++)
2612	queue_pushunique(dq, dqs->elements[i]);
2613	}
2614
2615	if (!dq->count)
2616	return level;
2617	*rerunp = 1;
2618
2619	if (dq->count == 1)
2620	{
2621	/* simple case, just one package. no need to choose to best version */
2622	p = dq->elements[0];
2623	if (dqs->count)
2624	POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "installing supplemented %s\n", pool_solvid2str (pool, p));} while (0);
2625	else
2626	POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "installing recommended %s\n", pool_solvid2str (pool, p));} while (0);
2627	return setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP7);
2628	}
2629
2630	/* filter packages, this gives us the best versions */
2631	policy_filter_unwanted(solv, dq, POLICY_MODE_RECOMMEND1);
2632
2633	/* create map of result */
2634	map_init(&dqmap, pool->nsolvables);
2635	for (i = 0; i < dq->count; i++)
2636	MAPSET(&dqmap, dq->elements[i])((&dqmap)->map[(dq->elements[i]) >> 3] \|= 1 << ((dq->elements[i]) & 7));
2637
2638	/* prune dqs so that it only contains the best versions */
2639	for (i = j = 0; i < dqs->count; i++)
2640	{
2641	p = dqs->elements[i];
2642	if (MAPTST(&dqmap, p)((&dqmap)->map[(p) >> 3] & (1 << ((p) & 7))))
2643	dqs->elements[j++] = p;
2644	}
2645	dqs->count = j;
2646
2647	/* install all supplemented packages, but order first */
2648	if (dqs->count > 1)
2649	policy_filter_unwanted(solv, dqs, POLICY_MODE_SUPPLEMENT4);
2650	decisioncount = solv->decisionq.count;
2651	for (i = 0; i < dqs->count; i++)
2652	{
2653	p = dqs->elements[i];
2654	if (solv->decisionmap[p])
2655	continue;
2656	POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "installing supplemented %s\n", pool_solvid2str (pool, p));} while (0);
2657	olevel = level;
2658	level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP7);
2659	if (level <= olevel)
2660	break;
2661	}
2662	if (i < dqs->count \|\| solv->decisionq.count < decisioncount)
2663	{
2664	map_free(&dqmap);
2665	return level;
2666	}
2667
2668	/* install all recommended packages */
2669	/* more work as we want to created branches if multiple
2670	* choices are valid */
2671	for (i = 0; i < decisioncount; i++)
2672	{
2673	Id rec, *recp, pp;
2674	p = solv->decisionq.elements[i];
2675	if (p < 0)
2676	continue;
2677	s = pool->solvables + p;
2678	if (!s->repo \|\| (!solv->addalreadyrecommended && s->repo == solv->installed))
2679	continue;
2680	if (!s->recommends)
2681	continue;
2682	recp = s->repo->idarraydata + s->recommends;
2683	while ((rec = *recp++) != 0)
2684	{
2685	queue_empty(dq);
2686	#ifdef ENABLE_COMPLEX_DEPS
2687	if (pool_is_complex_dep(pool, rec))
2688	add_complex_recommends(solv, rec, dq, &dqmap);
2689	else
2690	#endif
2691	FOR_PROVIDES(p, pp, rec)for (pp = pool_whatprovides(pool, rec) ; (p = pool->whatprovidesdata [pp++]) != 0; )
2692	{
2693	if (solv->decisionmap[p] > 0)
2694	{
2695	dq->count = 0;
2696	break;
2697	}
2698	else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p)((&dqmap)->map[(p) >> 3] & (1 << ((p) & 7))))
2699	queue_push(dq, p);
2700	}
2701	if (!dq->count)
2702	continue;
2703	if (dq->count > 1)
2704	policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE0);
2705	/* if we have multiple candidates we open a branch */
2706	if (dq->count > 1)
2707	createbranch(solv, level, dq, s - pool->solvables, rec);
2708	p = dq->elements[0];
2709	POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "installing recommended %s\n", pool_solvid2str (pool, p));} while (0);
2710	olevel = level;
2711	level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP7);
2712	if (level <= olevel \|\| solv->decisionq.count < decisioncount)
2713	break; /* we had to revert some decisions */
2714	}
2715	if (rec)
2716	break; /* had a problem above, quit loop */
2717	}
2718	map_free(&dqmap);
2719	return level;
2720	}
2721
2722
2723	static int
2724	resolve_orphaned(Solver solv, int level, int disablerules, Queue dq, int *rerunp)
2725	{
2726	Pool *pool = solv->pool;
2727	int i;
2728	Id p;
2729	int installedone = 0;
2730	int olevel;
2731
2732	/* let's see if we can install some unsupported package */
2733	POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n")do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "deciding orphaned packages\n");} while (0);
2734	for (i = 0; i < solv->orphaned.count; i++)
2735	{
2736	p = solv->orphaned.elements[i];
2737	if (solv->decisionmap[p])
2738	continue; /* already decided */
2739	if (solv->droporphanedmap_all)
2740	continue;
2741	if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start)((&solv->droporphanedmap)->map[(p - solv->installed ->start) >> 3] & (1 << ((p - solv->installed ->start) & 7))))
2742	continue;
2743	POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "keeping orphaned %s\n", pool_solvid2str (pool, p));} while (0);
2744	olevel = level;
2745	level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN8);
2746	installedone = 1;
2747	if (level < olevel)
2748	break;
2749	}
2750	if (installedone \|\| i < solv->orphaned.count)
2751	{
2752	*rerunp = 1;
2753	return level;
2754	}
2755	for (i = 0; i < solv->orphaned.count; i++)
2756	{
2757	p = solv->orphaned.elements[i];
2758	if (solv->decisionmap[p])
2759	continue; /* already decided */
2760	POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "removing orphaned %s\n", pool_solvid2str (pool, p));} while (0);
2761	olevel = level;
2762	level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN8);
2763	if (level < olevel)
2764	{
2765	*rerunp = 1;
2766	return level;
2767	}
2768	}
2769	if (solv->brokenorphanrules)
2770	{
2771	solver_check_brokenorphanrules(solv, dq);
2772	if (dq->count)
2773	{
2774	policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE0);
2775	for (i = 0; i < dq->count; i++)
2776	{
2777	p = dq->elements[i];
2778	POOL_DEBUG(SOLV_DEBUG_POLICY, "installing orphaned dep %s\n", pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "installing orphaned dep %s\n", pool_solvid2str (pool, p));} while (0);
2779	olevel = level;
2780	level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN8);
2781	if (level < olevel)
2782	break;
2783	}
2784	*rerunp = 1;
2785	}
2786	}
2787	return level;
2788	}
2789
2790	/*-------------------------------------------------------------------
2791	*
2792	* solver_run_sat
2793	*
2794	* all rules have been set up, now actually run the solver
2795	*
2796	*/
2797
2798	void
2799	solver_run_sat(Solver *solv, int disablerules, int doweak)
2800	{
2801	Queue dq; /* local decisionqueue */
2802	Queue dqs; /* local decisionqueue for supplements */
2803	int systemlevel;
2804	int level, olevel;
2805	Rule *r;
2806	int i;
2807	Solvable *s;
2808	Pool *pool = solv->pool;
2809	Id p;
2810	int minimizationsteps;
2811
2812	IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)if ((pool->debugmask & ((1<<4))) != 0)
2813	{
2814	POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules)do {if ((pool->debugmask & ((1<<4))) != 0) pool_debug (pool, ((1<<4)), "number of rules: %d\n", solv->nrules );} while (0);
2815	for (i = 1; i < solv->nrules; i++)
2816	solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION(1<<4), solv->rules + i);
2817	}
2818
2819	/* start SAT algorithm */
2820	level = 0;
2821	systemlevel = level + 1;
2822	POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n")do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "solving...\n");} while (0);
2823
2824	queue_init(&dq);
2825	queue_init(&dqs);
2826	solv->installedpos = 0;
2827	solv->do_extra_reordering = 0;
2828
2829	/*
2830	* here's the main loop:
2831	* 1) decide assertion rules and propagate
2832	* 2) fulfill jobs
2833	* 3) try to keep installed packages
2834	* 4) fulfill all unresolved rules
2835	* 5) install recommended packages
2836	* 6) minimalize solution if we had choices
2837	* if we encounter a problem, we rewind to a safe level and restart
2838	* with step 1
2839	*/
2840
2841	minimizationsteps = 0;
2842	for (;;)
2843	{
2844	/*
2845	* initial propagation of the assertions
2846	*/
2847	if (level <= 0)
2848	{
2849	if (level < 0)
2850	break;
2851	makeruledecisions(solv);
2852	level = 1;
2853	if (!disablerules && solv->problems.count)
2854	{
2855	level = -1;
2856	break;
2857	}
2858	POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "initial propagate (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count)do {if ((pool->debugmask & ((1<<5))) != 0) pool_debug (pool, ((1<<5)), "initial propagate (propagate_index: %d; size decisionq: %d)...\n" , solv->propagate_index, solv->decisionq.count);} while (0);
2859	if ((r = propagate(solv, level)) != 0)
2860	{
2861	level = analyze_unsolvable(solv, r, disablerules);
2862	continue;
2863	}
2864	systemlevel = level + 1;
2865	}
2866
2867	/*
2868	* resolve jobs first (unless focus_installed is set)
2869	*/
2870	if (level < systemlevel && !solv->focus_installed)
2871	{
2872	if (solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2873	solv->do_extra_reordering = 1;
2874	olevel = level;
2875	level = resolve_jobrules(solv, level, disablerules, &dq);
2876	solv->do_extra_reordering = 0;
2877	if (level < olevel)
2878	continue;
2879	systemlevel = level + 1;
2880	}
2881
2882	/* resolve job dependencies in the focus_best case */
2883	if (level < systemlevel && solv->focus_best && !solv->focus_installed && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2884	{
2885	solv->do_extra_reordering = 1;
2886	olevel = level;
2887	level = resolve_dependencies(solv, level, disablerules, &dq);
2888	solv->do_extra_reordering = 0;
2889	if (level < olevel)
2890	continue; /* start over */
2891	systemlevel = level + 1;
2892	}
2893
2894	/*
2895	* installed packages
2896	*/
2897	if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2898	{
2899	olevel = level;
2900	level = resolve_installed(solv, level, disablerules, &dq);
2901	if (level < olevel)
2902	continue;
2903	systemlevel = level + 1;
2904	}
2905
2906	/* resolve jobs in focus_installed case */
2907	if (level < systemlevel && solv->focus_installed)
2908	{
2909	olevel = level;
2910	level = resolve_jobrules(solv, level, disablerules, &dq);
2911	if (level < olevel)
2912	continue;
2913	systemlevel = level + 1;
2914	}
2915
2916	if (level < systemlevel)
2917	systemlevel = level;
2918
2919	/* resolve all dependencies */
2920	olevel = level;
2921	level = resolve_dependencies(solv, level, disablerules, &dq);
2922	if (level < olevel)
2923	continue; /* start over */
2924
2925	/* decide leftover cleandeps packages */
2926	if (solv->cleandepsmap.size && solv->installed)
2927	{
2928	for (p = solv->installed->start; p < solv->installed->end; p++)
2929	{
2930	s = pool->solvables + p;
2931	if (s->repo != solv->installed)
2932	continue;
2933	if (solv->decisionmap[p] == 0 && MAPTST(&solv->cleandepsmap, p - solv->installed->start)((&solv->cleandepsmap)->map[(p - solv->installed ->start) >> 3] & (1 << ((p - solv->installed ->start) & 7))))
2934	{
2935	POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<9))) != 0) pool_debug (pool, ((1<<9)), "cleandeps erasing %s\n", pool_solvid2str (pool, p));} while (0);
2936	olevel = level;
2937	level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_CLEANDEPS_ERASE5);
2938	if (level < olevel)
2939	break;
2940	}
2941	}
2942	if (p < solv->installed->end)
2943	continue;
2944	}
2945
2946	/* at this point we have a consistent system. now do the extras... */
2947
2948	if (doweak)
2949	{
2950	int rerun = 0;
2951	level = resolve_weak(solv, level, disablerules, &dq, &dqs, &rerun);
2952	if (rerun)
2953	continue;
2954	}
2955
2956	if (solv->installed && (solv->orphaned.count \|\| solv->brokenorphanrules))
2957	{
2958	int rerun = 0;
2959	level = resolve_orphaned(solv, level, disablerules, &dq, &rerun);
2960	if (rerun)
2961	continue;
2962	}
2963
2964	/* one final pass to make sure we decided all installed packages */
2965	if (solv->installed)
2966	{
2967	for (p = solv->installed->start; p < solv->installed->end; p++)
2968	{
2969	if (solv->decisionmap[p])
2970	continue; /* already decided */
2971	s = pool->solvables + p;
2972	if (s->repo != solv->installed)
2973	continue;
2974	POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing unwanted %s\n", pool_solvid2str(pool, p))do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "removing unwanted %s\n", pool_solvid2str (pool, p));} while (0);
2975	olevel = level;
2976	level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_CLEANDEPS_ERASE5);
2977	if (level < olevel)
2978	break;
2979	}
2980	if (p < solv->installed->end)
2981	continue; /* back to main loop */
2982	}
2983
2984	if (solv->installed && solv->cleandepsmap.size && cleandeps_check_mistakes(solv))
2985	{
2986	solver_reset(solv);
2987	level = 0; /* restart from scratch */
2988	continue;
2989	}
2990
2991	if (solv->solution_callback)
2992	{
2993	solv->solution_callback(solv, solv->solution_callback_data);
2994	if (solv->branches.count)
2995	{
2996	int l, endi = 0;
2997	p = l = 0;
	Value stored to 'p' is never read
2998	for (i = solv->branches.count - 1; i >= 0; i--)
2999	{
3000	p = solv->branches.elements[i];
3001	if (p > 0 && !l)
3002	{
3003	endi = i + 1;
3004	l = p;
3005	i -= 3; /* skip: p data count */
3006	}
3007	else if (p > 0)
3008	break;
3009	else if (p < 0)
3010	l = 0;
3011	}
3012	if (i >= 0)
3013	{
3014	while (i > 0 && solv->branches.elements[i - 1] > 0)
3015	i--;
3016	level = takebranch(solv, i, endi, "branching", disablerules);
3017	continue;
3018	}
3019	}
3020	/* all branches done, we're finally finished */
3021	break;
3022	}
3023
3024	/* auto-minimization step */
3025	if (solv->branches.count)
3026	{
3027	int endi, lasti = -1, lastiend = -1;
3028	if (solv->recommends_index < solv->decisionq.count)
3029	policy_update_recommendsmap(solv);
3030	for (endi = solv->branches.count; endi > 0;)
3031	{
3032	int l, lastsi = -1, starti = endi - solv->branches.elements[endi - 2];
3033	l = solv->branches.elements[endi - 1];
3034	for (i = starti; i < endi - 4; i++)
3035	{
3036	p = solv->branches.elements[i];
3037	if (p <= 0)
3038	continue;
3039	if (solv->decisionmap[p] > l)
3040	{
3041	lasti = i;
3042	lastiend = endi;
3043	lastsi = -1;
3044	break;
3045	}
3046	if (solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, p)((&solv->isdisfavormap)->map[(p) >> 3] & ( 1 << ((p) & 7))))
3047	continue;
3048	if (lastsi < 0 && (MAPTST(&solv->recommendsmap, p)((&solv->recommendsmap)->map[(p) >> 3] & ( 1 << ((p) & 7))) \|\| solver_is_supplementing(solv, pool->solvables + p)))
3049	lastsi = i;
3050	}
3051	if (lastsi >= 0)
3052	{
3053	/* we have a recommended package that could not be installed */
3054	/* take it if our current selection is not recommended */
3055	for (i = starti; i < endi - 4; i++)
3056	{
3057	p = -solv->branches.elements[i];
3058	if (p <= 0 \|\| solv->decisionmap[p] != l + 1)
3059	continue;
3060	if (solv->favormap.size && MAPTST(&solv->favormap, p)((&solv->favormap)->map[(p) >> 3] & (1 << ((p) & 7))))
3061	if (!(solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, p)((&solv->isdisfavormap)->map[(p) >> 3] & ( 1 << ((p) & 7)))))
3062	continue; /* current selection is favored */
3063	if (!(MAPTST(&solv->recommendsmap, p)((&solv->recommendsmap)->map[(p) >> 3] & ( 1 << ((p) & 7))) \|\| solver_is_supplementing(solv, pool->solvables + p)))
3064	{
3065	lasti = lastsi;
3066	lastiend = endi;
3067	break;
3068	}
3069	}
3070	}
3071	endi = starti;
3072	}
3073	if (lasti >= 0)
3074	{
3075	minimizationsteps++;
3076	level = takebranch(solv, lasti, lastiend, "minimizing", disablerules);
3077	continue; /* back to main loop */
3078	}
3079	}
3080	/* no minimization found, we're finally finished! */
3081	break;
3082	}
3083	assert(level == -1 \|\| level + 1 == solv->decisionq_reason.count)({ if (level == -1 \|\| level + 1 == solv->decisionq_reason. count) ; else __assert_fail ("level == -1 \|\| level + 1 == solv->decisionq_reason.count" , "/home/brain/Projects/upstream/libsolv/src/solver.c", 3083, __PRETTY_FUNCTION__); });
3084
3085	POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n" , solv->stats_learned, solv->stats_unsolvable, minimizationsteps );} while (0);
3086
3087	POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n")do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "done solving.\n\n");} while (0);
3088	queue_free(&dq);
3089	queue_free(&dqs);
3090	#if 0
3091	solver_printdecisionq(solv, SOLV_DEBUG_RESULT(1<<10));
3092	#endif
3093	}
3094
3095
3096	/*-------------------------------------------------------------------
3097	*
3098	* remove disabled conflicts
3099	*
3100	* purpose: update the decisionmap after some rules were disabled.
3101	* this is used to calculate the suggested/recommended package list.
3102	* Also returns a "removed" list to undo the discisionmap changes.
3103	*/
3104
3105	static void
3106	removedisabledconflicts(Solver solv, Queue removed)
3107	{
3108	Pool *pool = solv->pool;
3109	int i, n;
3110	Id p, why, *dp;
3111	Id new;
3112	Rule *r;
3113	Id *decisionmap = solv->decisionmap;
3114
3115	queue_empty(removed);
3116	for (i = 0; i < solv->decisionq.count; i++)
3117	{
3118	p = solv->decisionq.elements[i];
3119	if (p > 0)
3120	continue; /* conflicts only, please */
3121	why = solv->decisionq_why.elements[i];
3122	if (why == 0)
3123	{
3124	/* no rule involved, must be a orphan package drop */
3125	continue;
3126	}
3127	/* we never do conflicts on free decisions, so there
3128	* must have been an unit rule */
3129	assert(why > 0)({ if (why > 0) ; else __assert_fail ("why > 0", "/home/brain/Projects/upstream/libsolv/src/solver.c" , 3129, __PRETTY_FUNCTION__); });
3130	r = solv->rules + why;
3131	if (r->d < 0 && decisionmap[-p])
3132	{
3133	/* rule is now disabled, remove from decisionmap */
3134	POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p)do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "removing conflict for package %s[%d]\n" , pool_solvid2str(pool, -p), -p);} while (0);
3135	queue_push(removed, -p);
3136	queue_push(removed, decisionmap[-p]);
3137	decisionmap[-p] = 0;
3138	}
3139	}
3140	if (!removed->count)
3141	return;
3142	/* we removed some confliced packages. some of them might still
3143	* be in conflict, so search for unit rules and re-conflict */
3144	new = 0;
3145	for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
3146	{
3147	if (i == solv->nrules)
3148	{
3149	i = 1;
3150	r = solv->rules + i;
3151	}
3152	if (r->d < 0)
3153	continue;
3154	if (!r->w2)
3155	{
3156	if (r->p < 0 && !decisionmap[-r->p])
3157	new = r->p;
3158	}
3159	else if (!r->d)
3160	{
3161	/* binary rule */
3162	if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2)((r->w2) > 0 ? (decisionmap[r->w2] < 0) : (decisionmap [-r->w2] > 0)))
3163	new = r->p;
3164	else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p)((r->p) > 0 ? (decisionmap[r->p] < 0) : (decisionmap [-r->p] > 0)))
3165	new = r->w2;
3166	}
3167	else
3168	{
3169	if (r->p < 0 && decisionmap[-r->p] == 0)
3170	new = r->p;
3171	if (new \|\| DECISIONMAP_FALSE(r->p)((r->p) > 0 ? (decisionmap[r->p] < 0) : (decisionmap [-r->p] > 0)))
3172	{
3173	dp = pool->whatprovidesdata + r->d;
3174	while ((p = *dp++) != 0)
3175	{
3176	if (new && p == new)
3177	continue;
3178	if (p < 0 && decisionmap[-p] == 0)
3179	{
3180	if (new)
3181	{
3182	new = 0;
3183	break;
3184	}
3185	new = p;
3186	}
3187	else if (!DECISIONMAP_FALSE(p)((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0)))
3188	{
3189	new = 0;
3190	break;
3191	}
3192	}
3193	}
3194	}
3195	if (new)
3196	{
3197	POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new)do {if ((pool->debugmask & ((1<<12))) != 0) pool_debug (pool, ((1<<12)), "re-conflicting package %s[%d]\n", pool_solvid2str (pool, -new), -new);} while (0);
3198	decisionmap[-new] = -1;
3199	new = 0;
3200	n = 0; /* redo all rules */
3201	}
3202	}
3203	}
3204
3205	static inline void
3206	undo_removedisabledconflicts(Solver solv, Queue removed)
3207	{
3208	int i;
3209	for (i = 0; i < removed->count; i += 2)
3210	solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
3211	}
3212
3213
3214	/*-------------------------------------------------------------------
3215	*
3216	* weaken solvable dependencies
3217	*/
3218
3219	static void
3220	weaken_solvable_deps(Solver *solv, Id p)
3221	{
3222	int i;
3223	Rule *r;
3224
3225	for (i = 1, r = solv->rules + i; i < solv->pkgrules_end; i++, r++)
3226	{
3227	if (r->p != -p)
3228	continue;
3229	if ((r->d == 0 \|\| r->d == -1) && r->w2 < 0)
3230	continue; /* conflict */
3231	queue_push(&solv->weakruleq, i);
3232	}
3233	}
3234
3235
3236	/********************************************************************/
3237	/* main() */
3238
3239
3240	void
3241	solver_calculate_multiversionmap(Pool pool, Queue job, Map *multiversionmap)
3242	{
3243	int i;
3244	Id how, what, select;
3245	Id p, pp;
3246	for (i = 0; i < job->count; i += 2)
3247	{
3248	how = job->elements[i];
3249	if ((how & SOLVER_JOBMASK0xff00) != SOLVER_MULTIVERSION0x0500)
3250	continue;
3251	what = job->elements[i + 1];
3252	select = how & SOLVER_SELECTMASK0xff;
3253	if (!multiversionmap->size)
3254	map_grow(multiversionmap, pool->nsolvables);
3255	if (select == SOLVER_SOLVABLE_ALL0x06)
3256	{
3257	FOR_POOL_SOLVABLES(p)for (p = 2; p < pool->nsolvables; p++) if (pool->solvables [p].repo == 0) continue; else
3258	MAPSET(multiversionmap, p)((multiversionmap)->map[(p) >> 3] \|= 1 << ((p) & 7));
3259	}
3260	else if (select == SOLVER_SOLVABLE_REPO0x05)
3261	{
3262	Solvable *s;
3263	Repo *repo = pool_id2repo(pool, what);
3264	if (repo)
3265	{
3266	FOR_REPO_SOLVABLES(repo, p, s)for (p = (repo)->start, s = (repo)->pool->solvables + p; p < (repo)->end; p++, s = (repo)->pool->solvables + p) if (s->repo != (repo)) continue; else
3267	MAPSET(multiversionmap, p)((multiversionmap)->map[(p) >> 3] \|= 1 << ((p) & 7));
3268	}
3269	}
3270	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
3271	MAPSET(multiversionmap, p)((multiversionmap)->map[(p) >> 3] \|= 1 << ((p) & 7));
3272	}
3273	}
3274
3275	void
3276	solver_calculate_noobsmap(Pool pool, Queue job, Map *multiversionmap)
3277	{
3278	solver_calculate_multiversionmap(pool, job, multiversionmap);
3279	}
3280
3281	/*
3282	* add a rule created by a job, record job number and weak flag
3283	*/
3284	static inline void
3285	solver_addjobrule(Solver *solv, Id p, Id p2, Id d, Id job, int weak)
3286	{
3287	solver_addrule(solv, p, p2, d);
3288	queue_push(&solv->ruletojob, job);
3289	if (weak)
3290	queue_push(&solv->weakruleq, solv->nrules - 1);
3291	}
3292
3293	static inline void
3294	add_cleandeps_package(Solver *solv, Id p)
3295	{
3296	if (!solv->cleandeps_updatepkgs)
3297	{
3298	solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
3299	queue_init(solv->cleandeps_updatepkgs);
3300	}
3301	queue_pushunique(solv->cleandeps_updatepkgs, p);
3302	}
3303
3304	static void
3305	add_update_target(Solver *solv, Id p, Id how)
3306	{
3307	Pool *pool = solv->pool;
3308	Solvable *s = pool->solvables + p;
3309	Repo *installed = solv->installed;
3310	Id pi, pip;
3311	if (!solv->update_targets)
3312	{
3313	solv->update_targets = solv_calloc(1, sizeof(Queue));
3314	queue_init(solv->update_targets);
3315	}
3316	if (s->repo == installed)
3317	{
3318	queue_push2(solv->update_targets, p, p);
3319	return;
3320	}
3321	FOR_PROVIDES(pi, pip, s->name)for (pip = pool_whatprovides(pool, s->name) ; (pi = pool-> whatprovidesdata[pip++]) != 0; )
3322	{
3323	Solvable *si = pool->solvables + pi;
3324	if (si->repo != installed \|\| si->name != s->name)
3325	continue;
3326	if (how & SOLVER_FORCEBEST0x100000)
3327	{
3328	if (!solv->bestupdatemap.size)
3329	map_grow(&solv->bestupdatemap, installed->end - installed->start);
3330	MAPSET(&solv->bestupdatemap, pi - installed->start)((&solv->bestupdatemap)->map[(pi - installed->start ) >> 3] \|= 1 << ((pi - installed->start) & 7));
3331	}
3332	if (how & SOLVER_CLEANDEPS0x040000)
3333	add_cleandeps_package(solv, pi);
3334	queue_push2(solv->update_targets, pi, p);
3335	/* check if it's ok to keep the installed package */
3336	if (s->evr == si->evr && solvable_identical(s, si))
3337	queue_push2(solv->update_targets, pi, pi);
3338	}
3339	if (s->obsoletes)
3340	{
3341	Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
3342	while ((obs = *obsp++) != 0)
3343	{
3344	FOR_PROVIDES(pi, pip, obs)for (pip = pool_whatprovides(pool, obs) ; (pi = pool->whatprovidesdata [pip++]) != 0; )
3345	{
3346	Solvable *si = pool->solvables + pi;
3347	if (si->repo != installed)
3348	continue;
3349	if (si->name == s->name)
3350	continue; /* already handled above */
3351	if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
3352	continue;
3353	if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
3354	continue;
3355	if (how & SOLVER_FORCEBEST0x100000)
3356	{
3357	if (!solv->bestupdatemap.size)
3358	map_grow(&solv->bestupdatemap, installed->end - installed->start);
3359	MAPSET(&solv->bestupdatemap, pi - installed->start)((&solv->bestupdatemap)->map[(pi - installed->start ) >> 3] \|= 1 << ((pi - installed->start) & 7));
3360	}
3361	if (how & SOLVER_CLEANDEPS0x040000)
3362	add_cleandeps_package(solv, pi);
3363	queue_push2(solv->update_targets, pi, p);
3364	}
3365	}
3366	}
3367	}
3368
3369	static int
3370	transform_update_targets_sortfn(const void ap, const void bp, void *dp)
3371	{
3372	const Id *a = ap;
3373	const Id *b = bp;
3374	if (a[0] - b[0])
3375	return a[0] - b[0];
3376	return a[1] - b[1];
3377	}
3378
3379	static void
3380	transform_update_targets(Solver *solv)
3381	{
3382	Repo *installed = solv->installed;
3383	Queue *update_targets = solv->update_targets;
3384	int i, j;
3385	Id p, q, lastp, lastq;
3386
3387	if (!update_targets->count)
3388	{
3389	queue_free(update_targets);
3390	solv->update_targets = solv_free(update_targets);
3391	return;
3392	}
3393	if (update_targets->count > 2)
3394	solv_sort(update_targets->elements, update_targets->count >> 1, 2 * sizeof(Id), transform_update_targets_sortfn, solv);
3395	queue_insertn(update_targets, 0, installed->end - installed->start, 0);
3396	lastp = lastq = 0;
3397	for (i = j = installed->end - installed->start; i < update_targets->count; i += 2)
3398	{
3399	if ((p = update_targets->elements[i]) != lastp)
3400	{
3401	if (!solv->updatemap.size)
3402	map_grow(&solv->updatemap, installed->end - installed->start);
3403	MAPSET(&solv->updatemap, p - installed->start)((&solv->updatemap)->map[(p - installed->start) >> 3] \|= 1 << ((p - installed->start) & 7));
3404	update_targets->elements[j++] = 0; /* finish old set */
3405	update_targets->elements[p - installed->start] = j; /* start new set */
3406	lastp = p;
3407	lastq = 0;
3408	}
3409	if ((q = update_targets->elements[i + 1]) != lastq)
3410	{
3411	update_targets->elements[j++] = q;
3412	lastq = q;
3413	}
3414	}
3415	queue_truncate(update_targets, j);
3416	queue_push(update_targets, 0); /* finish last set */
3417	}
3418
3419
3420	static void
3421	addedmap2deduceq(Solver solv, Map addedmap)
3422	{
3423	Pool *pool = solv->pool;
3424	int i, j;
3425	Id p;
3426	Rule *r;
3427
3428	queue_empty(&solv->addedmap_deduceq);
3429	for (i = 2, j = solv->pkgrules_end - 1; i < pool->nsolvables && j > 0; j--)
3430	{
3431	r = solv->rules + j;
3432	if (r->p >= 0)
3433	continue;
3434	if ((r->d == 0 \|\| r->d == -1) && r->w2 < 0)
3435	continue;
3436	p = -r->p;
3437	if (!MAPTST(addedmap, p)((addedmap)->map[(p) >> 3] & (1 << ((p) & 7))))
3438	{
3439	/* should never happen, but... */
3440	if (!solv->addedmap_deduceq.count \|\| solv->addedmap_deduceq.elements[solv->addedmap_deduceq.count - 1] != -p)
3441	queue_push(&solv->addedmap_deduceq, -p);
3442	continue;
3443	}
3444	for (; i < p; i++)
3445	if (MAPTST(addedmap, i)((addedmap)->map[(i) >> 3] & (1 << ((i) & 7))))
3446	queue_push(&solv->addedmap_deduceq, i);
3447	if (i == p)
3448	i++;
3449	}
3450	for (; i < pool->nsolvables; i++)
3451	if (MAPTST(addedmap, i)((addedmap)->map[(i) >> 3] & (1 << ((i) & 7))))
3452	queue_push(&solv->addedmap_deduceq, i);
3453	j = 0;
3454	for (i = 2; i < pool->nsolvables; i++)
3455	if (MAPTST(addedmap, i)((addedmap)->map[(i) >> 3] & (1 << ((i) & 7))))
3456	j++;
3457	}
3458
3459	static void
3460	deduceq2addedmap(Solver solv, Map addedmap)
3461	{
3462	int j;
3463	Id p;
3464	Rule *r;
3465	for (j = solv->pkgrules_end - 1; j > 0; j--)
3466	{
3467	r = solv->rules + j;
3468	if (r->d < 0 && r->p)
3469	solver_enablerule(solv, r);
3470	if (r->p >= 0)
3471	continue;
3472	if ((r->d == 0 \|\| r->d == -1) && r->w2 < 0)
3473	continue;
3474	p = -r->p;
3475	MAPSET(addedmap, p)((addedmap)->map[(p) >> 3] \|= 1 << ((p) & 7 ));
3476	}
3477	for (j = 0; j < solv->addedmap_deduceq.count; j++)
3478	{
3479	p = solv->addedmap_deduceq.elements[j];
3480	if (p > 0)
3481	MAPSET(addedmap, p)((addedmap)->map[(p) >> 3] \|= 1 << ((p) & 7 ));
3482	else
3483	MAPCLR(addedmap, p)((addedmap)->map[(p) >> 3] &= ~(1 << ((p) & 7)));
3484	}
3485	}
3486
3487	#ifdef ENABLE_COMPLEX_DEPS
3488	static int
3489	add_complex_jobrules(Solver *solv, Id dep, int flags, int jobidx, int weak)
3490	{
3491	Pool *pool = solv->pool;
3492	Queue bq;
3493	int i, j;
3494
3495	queue_init(&bq);
3496	i = pool_normalize_complex_dep(pool, dep, &bq, flags \| CPLXDEPS_EXPAND(1 << 1));
3497	if (i == 0 \|\| i == 1)
3498	{
3499	queue_free(&bq);
3500	if (i == 0)
3501	solver_addjobrule(solv, -SYSTEMSOLVABLE1, 0, 0, jobidx, weak);
3502	return 0;
3503	}
3504	for (i = 0; i < bq.count; i++)
3505	{
3506	if (!bq.elements[i])
3507	continue;
3508	for (j = 0; bq.elements[i + j + 1]; j++)
3509	;
3510	if (j > 1)
3511	solver_addjobrule(solv, bq.elements[i], 0, pool_ids2whatprovides(pool, bq.elements + i + 1, j), jobidx, weak);
3512	else
3513	solver_addjobrule(solv, bq.elements[i], bq.elements[i + 1], 0, jobidx, weak);
3514	i += j + 1;
3515	}
3516	queue_free(&bq);
3517	return 1;
3518	}
3519	#endif
3520
3521	/* sort by package id, last entry wins */
3522	static int
3523	setup_favormaps_cmp(const void ap, const void bp, void *dp)
3524	{
3525	const Id a = ap, b = bp;
3526	if ((a - b) != 0)
3527	return a - b;
3528	return (b[1] < 0 ? -b[1] : b[1]) - (a[1] < 0 ? -a[1] : a[1]);
3529	}
3530
3531	static void
3532	setup_favormaps(Solver *solv)
3533	{
3534	Queue *q = solv->favorq;
3535	Pool *pool = solv->pool;
3536	int i;
3537	Id oldp = 0;
3538	if (q->count > 2)
3539	solv_sort(q->elements, q->count / 2, 2 * sizeof(Id), setup_favormaps_cmp, solv);
3540	map_grow(&solv->favormap, pool->nsolvables);
3541	for (i = 0; i < q->count; i += 2)
3542	{
3543	Id p = q->elements[i];
3544	if (p == oldp)
3545	continue;
3546	oldp = p;
3547	MAPSET(&solv->favormap, p)((&solv->favormap)->map[(p) >> 3] \|= 1 << ((p) & 7));
3548	if (q->elements[i + 1] < 0)
3549	{
3550	if (!solv->isdisfavormap.size)
3551	map_grow(&solv->isdisfavormap, pool->nsolvables);
3552	MAPSET(&solv->isdisfavormap, p)((&solv->isdisfavormap)->map[(p) >> 3] \|= 1 << ((p) & 7));
3553	}
3554	}
3555	}
3556
3557	/*
3558	*
3559	* solve job queue
3560	*
3561	*/
3562
3563	int
3564	solver_solve(Solver solv, Queue job)
3565	{
3566	Pool *pool = solv->pool;
3567	Repo *installed = solv->installed;
3568	int i;
3569	int oldnrules, initialnrules;
3570	Map addedmap; /* '1' == have pkg-rules for solvable */
3571	Map installcandidatemap;
3572	Id how, what, select, name, weak, p, pp, d;
3573	Queue q;
3574	Solvable s, name_s;
3575	Rule *r;
3576	int now, solve_start;
3577	int needduprules = 0;
3578	int hasbestinstalljob = 0;
3579
3580	solve_start = solv_timems(0);
3581
3582	/* log solver options */
3583	POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n")do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "solver started\n");} while (0);
3584	POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n" , solv->dosplitprovides, solv->noupdateprovide, solv-> noinfarchcheck);} while (0);
3585	POOL_DEBUG(SOLV_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allownamechange=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allownamechange, solv->allowarchchange, solv->allowvendorchange)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "allowuninstall=%d, allowdowngrade=%d, allownamechange=%d, allowarchchange=%d, allowvendorchange=%d\n" , solv->allowuninstall, solv->allowdowngrade, solv-> allownamechange, solv->allowarchchange, solv->allowvendorchange );} while (0);
3586	POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "promoteepoch=%d, forbidselfconflicts=%d\n" , pool->promoteepoch, pool->forbidselfconflicts);} while (0);
3587	POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d, implicitobsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors, pool->implicitobsoleteusescolors)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d, implicitobsoleteusescolors=%d\n" , pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides , pool->obsoleteusescolors, pool->implicitobsoleteusescolors );} while (0);
3588	POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "dontinstallrecommended=%d, addalreadyrecommended=%d\n" , solv->dontinstallrecommended, solv->addalreadyrecommended );} while (0);
3589
3590	/* create whatprovides if not already there */
3591	if (!pool->whatprovides)
3592	pool_createwhatprovides(pool);
3593
3594	/* create obsolete index */
3595	policy_create_obsolete_index(solv);
3596
3597	/* remember job */
3598	queue_free(&solv->job);
3599	queue_init_clone(&solv->job, job);
3600	solv->pooljobcnt = pool->pooljobs.count;
3601	if (pool->pooljobs.count)
3602	queue_insertn(&solv->job, 0, pool->pooljobs.count, pool->pooljobs.elements);
3603	job = &solv->job;
3604
3605	/* free old stuff in jase we re-run a solver */
3606	queuep_free(&solv->update_targets);
3607	queuep_free(&solv->cleandeps_updatepkgs);
3608	queue_empty(&solv->ruleassertions);
3609	solv->bestrules_pkg = solv_free(solv->bestrules_pkg);
3610	solv->yumobsrules_info = solv_free(solv->yumobsrules_info);
3611	solv->choicerules_ref = solv_free(solv->choicerules_ref);
3612	if (solv->noupdate.size)
3613	map_empty(&solv->noupdate);
3614	map_zerosize(&solv->multiversion);
3615	solv->updatemap_all = 0;
3616	map_zerosize(&solv->updatemap);
3617	solv->bestupdatemap_all = 0;
3618	map_zerosize(&solv->bestupdatemap);
3619	solv->fixmap_all = 0;
3620	map_zerosize(&solv->fixmap);
3621	solv->dupmap_all = 0;
3622	map_zerosize(&solv->dupmap);
3623	map_zerosize(&solv->dupinvolvedmap);
3624	solv->droporphanedmap_all = 0;
3625	map_zerosize(&solv->droporphanedmap);
3626	solv->allowuninstall_all = 0;
3627	map_zerosize(&solv->allowuninstallmap);
3628	map_zerosize(&solv->cleandepsmap);
3629	map_zerosize(&solv->weakrulemap);
3630	map_zerosize(&solv->favormap);
3631	map_zerosize(&solv->isdisfavormap);
3632	queue_empty(&solv->weakruleq);
3633	solv->watches = solv_free(solv->watches);
3634	queue_empty(&solv->ruletojob);
3635	if (solv->decisionq.count)
3636	memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
3637	queue_empty(&solv->decisionq);
3638	queue_empty(&solv->decisionq_why);
3639	queue_empty(&solv->decisionq_reason);
3640	queue_empty(&solv->learnt_why);
3641	queue_empty(&solv->learnt_pool);
3642	queue_empty(&solv->branches);
3643	solv->propagate_index = 0;
3644	queue_empty(&solv->problems);
3645	queue_empty(&solv->solutions);
3646	queue_empty(&solv->orphaned);
3647	solv->stats_learned = solv->stats_unsolvable = 0;
3648	if (solv->recommends_index)
3649	{
3650	map_empty(&solv->recommendsmap);
3651	map_empty(&solv->suggestsmap);
3652	queuep_free(&solv->recommendscplxq);
3653	queuep_free(&solv->suggestscplxq);
3654	solv->recommends_index = 0;
3655	}
3656	queuep_free(&solv->brokenorphanrules);
3657	solv->specialupdaters = solv_free(solv->specialupdaters);
3658
3659
3660	/*
3661	* create basic rule set of all involved packages
3662	* use addedmap bitmap to make sure we don't create rules twice
3663	*/
3664
3665	/* create multiversion map if needed */
3666	solver_calculate_multiversionmap(pool, job, &solv->multiversion);
3667
3668	map_init(&addedmap, pool->nsolvables);
3669	MAPSET(&addedmap, SYSTEMSOLVABLE)((&addedmap)->map[(1) >> 3] \|= 1 << ((1) & 7));
3670
3671	map_init(&installcandidatemap, pool->nsolvables);
3672	queue_init(&q);
3673
3674	now = solv_timems(0);
3675	/*
3676	* create rules for all package that could be involved with the solving
3677	* so called: pkg rules
3678	*
3679	*/
3680	initialnrules = solv->pkgrules_end ? solv->pkgrules_end : 1;
3681	if (initialnrules > 1)
3682	deduceq2addedmap(solv, &addedmap);
3683	if (solv->nrules != initialnrules)
3684	solver_shrinkrules(solv, initialnrules);
3685	solv->nrules = initialnrules;
3686	solv->lastpkgrule = 0;
3687	solv->pkgrules_end = 0;
3688
3689	if (installed)
3690	{
3691	/* check for update/verify jobs as they need to be known early */
3692	/* also setup the droporphaned map, we need it when creating update rules */
3693	for (i = 0; i < job->count; i += 2)
3694	{
3695	how = job->elements[i];
3696	what = job->elements[i + 1];
3697	select = how & SOLVER_SELECTMASK0xff;
3698	switch (how & SOLVER_JOBMASK0xff00)
3699	{
3700	case SOLVER_VERIFY0x0800:
3701	if (select == SOLVER_SOLVABLE_ALL0x06 \|\| (select == SOLVER_SOLVABLE_REPO0x05 && installed && what == installed->repoid))
3702	solv->fixmap_all = 1;
3703	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
3704	{
3705	s = pool->solvables + p;
3706	if (s->repo != installed)
3707	continue;
3708	if (!solv->fixmap.size)
3709	map_grow(&solv->fixmap, installed->end - installed->start);
3710	MAPSET(&solv->fixmap, p - installed->start)((&solv->fixmap)->map[(p - installed->start) >> 3] \|= 1 << ((p - installed->start) & 7));
3711	}
3712	break;
3713	case SOLVER_UPDATE0x0300:
3714	if (select == SOLVER_SOLVABLE_ALL0x06)
3715	{
3716	solv->updatemap_all = 1;
3717	if (how & SOLVER_FORCEBEST0x100000)
3718	solv->bestupdatemap_all = 1;
3719	if (how & SOLVER_CLEANDEPS0x040000)
3720	{
3721	FOR_REPO_SOLVABLES(installed, p, s)for (p = (installed)->start, s = (installed)->pool-> solvables + p; p < (installed)->end; p++, s = (installed )->pool->solvables + p) if (s->repo != (installed)) continue ; else
3722	add_cleandeps_package(solv, p);
3723	}
3724	}
3725	else if (select == SOLVER_SOLVABLE_REPO0x05)
3726	{
3727	Repo *repo = pool_id2repo(pool, what);
3728	if (!repo)
3729	break;
3730	if (repo == installed && !(how & SOLVER_TARGETED0x200000))
3731	{
3732	solv->updatemap_all = 1;
3733	if (how & SOLVER_FORCEBEST0x100000)
3734	solv->bestupdatemap_all = 1;
3735	if (how & SOLVER_CLEANDEPS0x040000)
3736	{
3737	FOR_REPO_SOLVABLES(installed, p, s)for (p = (installed)->start, s = (installed)->pool-> solvables + p; p < (installed)->end; p++, s = (installed )->pool->solvables + p) if (s->repo != (installed)) continue ; else
3738	add_cleandeps_package(solv, p);
3739	}
3740	break;
3741	}
3742	if (solv->noautotarget && !(how & SOLVER_TARGETED0x200000))
3743	break;
3744	/* targeted update */
3745	FOR_REPO_SOLVABLES(repo, p, s)for (p = (repo)->start, s = (repo)->pool->solvables + p; p < (repo)->end; p++, s = (repo)->pool->solvables + p) if (s->repo != (repo)) continue; else
3746	add_update_target(solv, p, how);
3747	}
3748	else
3749	{
3750	if (!(how & SOLVER_TARGETED0x200000))
3751	{
3752	int targeted = 1;
3753	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
3754	{
3755	s = pool->solvables + p;
3756	if (s->repo != installed)
3757	continue;
3758	if (!solv->updatemap.size)
3759	map_grow(&solv->updatemap, installed->end - installed->start);
3760	MAPSET(&solv->updatemap, p - installed->start)((&solv->updatemap)->map[(p - installed->start) >> 3] \|= 1 << ((p - installed->start) & 7));
3761	if (how & SOLVER_FORCEBEST0x100000)
3762	{
3763	if (!solv->bestupdatemap.size)
3764	map_grow(&solv->bestupdatemap, installed->end - installed->start);
3765	MAPSET(&solv->bestupdatemap, p - installed->start)((&solv->bestupdatemap)->map[(p - installed->start ) >> 3] \|= 1 << ((p - installed->start) & 7 ));
3766	}
3767	if (how & SOLVER_CLEANDEPS0x040000)
3768	add_cleandeps_package(solv, p);
3769	targeted = 0;
3770	}
3771	if (!targeted \|\| solv->noautotarget)
3772	break;
3773	}
3774	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
3775	add_update_target(solv, p, how);
3776	}
3777	break;
3778	case SOLVER_DROP_ORPHANED0x0900:
3779	if (select == SOLVER_SOLVABLE_ALL0x06 \|\| (select == SOLVER_SOLVABLE_REPO0x05 && what == installed->repoid))
3780	solv->droporphanedmap_all = 1;
3781	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
3782	{
3783	s = pool->solvables + p;
3784	if (s->repo != installed)
3785	continue;
3786	if (!solv->droporphanedmap.size)
3787	map_grow(&solv->droporphanedmap, installed->end - installed->start);
3788	MAPSET(&solv->droporphanedmap, p - installed->start)((&solv->droporphanedmap)->map[(p - installed->start ) >> 3] \|= 1 << ((p - installed->start) & 7 ));
3789	}
3790	break;
3791	case SOLVER_ALLOWUNINSTALL0x0b00:
3792	if (select == SOLVER_SOLVABLE_ALL0x06 \|\| (select == SOLVER_SOLVABLE_REPO0x05 && installed && what == installed->repoid))
3793	solv->allowuninstall_all = 1;
3794	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
3795	{
3796	s = pool->solvables + p;
3797	if (s->repo != installed)
3798	continue;
3799	if (!solv->allowuninstallmap.size)
3800	map_grow(&solv->allowuninstallmap, installed->end - installed->start);
3801	MAPSET(&solv->allowuninstallmap, p - installed->start)((&solv->allowuninstallmap)->map[(p - installed-> start) >> 3] \|= 1 << ((p - installed->start) & 7));
3802	}
3803	break;
3804	default:
3805	break;
3806	}
3807	}
3808
3809	if (solv->update_targets)
3810	transform_update_targets(solv);
3811
3812	oldnrules = solv->nrules;
3813	FOR_REPO_SOLVABLES(installed, p, s)for (p = (installed)->start, s = (installed)->pool-> solvables + p; p < (installed)->end; p++, s = (installed )->pool->solvables + p) if (s->repo != (installed)) continue ; else
3814	solver_addpkgrulesforsolvable(solv, s, &addedmap);
3815	POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for installed solvables\n", solv->nrules - oldnrules)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "added %d pkg rules for installed solvables\n" , solv->nrules - oldnrules);} while (0);
3816	oldnrules = solv->nrules;
3817	FOR_REPO_SOLVABLES(installed, p, s)for (p = (installed)->start, s = (installed)->pool-> solvables + p; p < (installed)->end; p++, s = (installed )->pool->solvables + p) if (s->repo != (installed)) continue ; else
3818	solver_addpkgrulesforupdaters(solv, s, &addedmap, 1);
3819	POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for updaters of installed solvables\n", solv->nrules - oldnrules)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "added %d pkg rules for updaters of installed solvables\n" , solv->nrules - oldnrules);} while (0);
3820	}
3821
3822	/*
3823	* create rules for all packages involved in the job
3824	* (to be installed or removed)
3825	*/
3826
3827	oldnrules = solv->nrules;
3828	for (i = 0; i < job->count; i += 2)
3829	{
3830	how = job->elements[i];
3831	what = job->elements[i + 1];
3832	select = how & SOLVER_SELECTMASK0xff;
3833
3834	switch (how & SOLVER_JOBMASK0xff00)
3835	{
3836	case SOLVER_INSTALL0x0100:
3837	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
3838	{
3839	MAPSET(&installcandidatemap, p)((&installcandidatemap)->map[(p) >> 3] \|= 1 << ((p) & 7));
3840	solver_addpkgrulesforsolvable(solv, pool->solvables + p, &addedmap);
3841	}
3842	break;
3843	case SOLVER_DISTUPGRADE0x0700:
3844	if (select == SOLVER_SOLVABLE_ALL0x06)
3845	{
3846	solv->dupmap_all = 1;
3847	solv->updatemap_all = 1;
3848	if (how & SOLVER_FORCEBEST0x100000)
3849	solv->bestupdatemap_all = 1;
3850	}
3851	if ((how & SOLVER_TARGETED0x200000) != 0)
3852	needduprules = 1;
3853	if (!solv->dupmap_all \|\| solv->allowuninstall \|\| solv->allowuninstall_all \|\| solv->allowuninstallmap.size \|\| solv->keep_orphans)
3854	needduprules = 1;
3855	break;
3856	default:
3857	break;
3858	}
3859	}
3860	POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for packages involved in a job\n", solv->nrules - oldnrules)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "added %d pkg rules for packages involved in a job\n" , solv->nrules - oldnrules);} while (0);
3861
3862
3863	/*
3864	* add rules for suggests, enhances
3865	*/
3866	oldnrules = solv->nrules;
3867	solver_addpkgrulesforweak(solv, &addedmap);
3868	POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of weak dependencies\n", solv->nrules - oldnrules)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "added %d pkg rules because of weak dependencies\n" , solv->nrules - oldnrules);} while (0);
3869
3870	#ifdef ENABLE_LINKED_PKGS
3871	oldnrules = solv->nrules;
3872	solver_addpkgrulesforlinked(solv, &addedmap);
3873	POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of linked packages\n", solv->nrules - oldnrules)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "added %d pkg rules because of linked packages\n" , solv->nrules - oldnrules);} while (0);
3874	#endif
3875
3876	/*
3877	* first pass done, we now have all the pkg rules we need.
3878	* unify existing rules before going over all job rules and
3879	* policy rules.
3880	* at this point the system is always solvable,
3881	* as an empty system (remove all packages) is a valid solution
3882	*/
3883
3884	IF_POOLDEBUG (SOLV_DEBUG_STATS)if ((pool->debugmask & ((1<<3))) != 0)
3885	{
3886	int possible = 0, installable = 0;
3887	for (i = 1; i < pool->nsolvables; i++)
3888	{
3889	if (pool_installable(pool, pool->solvables + i))
3890	installable++;
3891	if (MAPTST(&addedmap, i)((&addedmap)->map[(i) >> 3] & (1 << (( i) & 7))))
3892	possible++;
3893	}
3894	POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "%d of %d installable solvables considered for solving\n" , possible, installable);} while (0);
3895	}
3896
3897	if (solv->nrules > initialnrules)
3898	solver_unifyrules(solv); /* remove duplicate pkg rules */
3899	solv->pkgrules_end = solv->nrules; /* mark end of pkg rules */
3900	solv->lastpkgrule = 0;
3901
3902	if (solv->nrules > initialnrules)
3903	addedmap2deduceq(solv, &addedmap); /* so that we can recreate the addedmap */
3904
3905	POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "pkg rule memory used: %d K\n", solv-> nrules * (int)sizeof(Rule) / 1024);} while (0);
3906	POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule creation took %d ms\n", solv_timems(now))do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "pkg rule creation took %d ms\n", solv_timems (now));} while (0);
3907
3908	/* create dup maps if needed. We need the maps early to create our
3909	* update rules */
3910	if (needduprules)
3911	solver_createdupmaps(solv);
3912
3913	/*
3914	* create feature rules
3915	*
3916	* foreach installed:
3917	* create assertion (keep installed, if no update available)
3918	* or
3919	* create update rule (A\|update1(A)\|update2(A)\|...)
3920	*
3921	* those are used later on to keep a version of the installed packages in
3922	* best effort mode
3923	*/
3924
3925	solv->featurerules = solv->nrules; /* mark start of feature rules */
3926	if (installed)
3927	{
3928	/* foreach possibly installed solvable */
3929	for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3930	{
3931	if (s->repo != installed)
3932	{
3933	solver_addrule(solv, 0, 0, 0); /* create dummy rule */
3934	continue;
3935	}
3936	solver_addfeaturerule(solv, s);
3937	}
3938	/* make sure we accounted for all rules */
3939	assert(solv->nrules - solv->featurerules == installed->end - installed->start)({ if (solv->nrules - solv->featurerules == installed-> end - installed->start) ; else __assert_fail ("solv->nrules - solv->featurerules == installed->end - installed->start" , "/home/brain/Projects/upstream/libsolv/src/solver.c", 3939, __PRETTY_FUNCTION__); });
3940	}
3941	solv->featurerules_end = solv->nrules;
3942
3943	/*
3944	* Add update rules for installed solvables
3945	*
3946	* almost identical to feature rules
3947	* except that downgrades/archchanges/vendorchanges are not allowed
3948	*/
3949
3950	solv->updaterules = solv->nrules;
3951
3952	if (installed)
3953	{ /* foreach installed solvables */
3954	/* we create all update rules, but disable some later on depending on the job */
3955	for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3956	{
3957	Rule *sr;
3958
3959	if (s->repo != installed)
3960	{
3961	solver_addrule(solv, 0, 0, 0); /* create dummy rule */
3962	continue;
3963	}
3964	solver_addupdaterule(solv, s);
3965	/*
3966	* check for and remove duplicate
3967	*/
3968	r = solv->rules + solv->nrules - 1; /* r: update rule */
3969	sr = r - (installed->end - installed->start); /* sr: feature rule */
3970	if (!r->p)
3971	{
3972	if (sr->p)
3973	memset(sr, 0, sizeof(sr)); / no feature rules without update rules */
3974	continue;
3975	}
3976	/* it's also orphaned if the feature rule consists just of the installed package */
3977	if (!solv->dupmap_all && sr->p == i && !sr->d && !sr->w2)
3978	queue_push(&solv->orphaned, i);
3979
3980	if (!solver_rulecmp(solv, r, sr))
3981	memset(sr, 0, sizeof(sr)); / delete unneeded feature rule */
3982	else if (sr->p)
3983	solver_disablerule(solv, sr); /* disable feature rule for now */
3984	}
3985	/* consistency check: we added a rule for _every_ installed solvable */
3986	assert(solv->nrules - solv->updaterules == installed->end - installed->start)({ if (solv->nrules - solv->updaterules == installed-> end - installed->start) ; else __assert_fail ("solv->nrules - solv->updaterules == installed->end - installed->start" , "/home/brain/Projects/upstream/libsolv/src/solver.c", 3986, __PRETTY_FUNCTION__); });
3987	}
3988	solv->updaterules_end = solv->nrules;
3989
3990
3991	/*
3992	* now add all job rules
3993	*/
3994
3995	solv->jobrules = solv->nrules;
3996	for (i = 0; i < job->count; i += 2)
3997	{
3998	oldnrules = solv->nrules;
3999
4000	if (i && i == solv->pooljobcnt)
4001	POOL_DEBUG(SOLV_DEBUG_JOB, "end of pool jobs\n")do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "end of pool jobs\n");} while (0);
4002	how = job->elements[i];
4003	what = job->elements[i + 1];
4004	weak = how & SOLVER_WEAK0x010000;
4005	select = how & SOLVER_SELECTMASK0xff;
4006	switch (how & SOLVER_JOBMASK0xff00)
4007	{
4008	case SOLVER_INSTALL0x0100:
4009	POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));} while (0);
4010	if ((how & SOLVER_CLEANDEPS0x040000) != 0 && !solv->cleandepsmap.size && installed)
4011	map_grow(&solv->cleandepsmap, installed->end - installed->start);
4012	if (select == SOLVER_SOLVABLE0x01)
4013	{
4014	p = what;
4015	d = 0;
4016	}
4017	#ifdef ENABLE_COMPLEX_DEPS
4018	else if ((select == SOLVER_SOLVABLE_PROVIDES0x03 \|\| select == SOLVER_SOLVABLE_NAME0x02) && pool_is_complex_dep(pool, what))
4019	{
4020	if (add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME0x02 ? CPLXDEPS_NAME(1 << 3) : 0, i, weak))
4021	if (how & SOLVER_FORCEBEST0x100000)
4022	hasbestinstalljob = 1;
4023	break;
4024	}
4025	#endif
4026	else
4027	{
4028	queue_empty(&q);
4029	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
4030	queue_push(&q, p);
4031	if (!q.count)
4032	{
4033	if (select == SOLVER_SOLVABLE_ONE_OF0x04)
4034	break; /* ignore empty installs */
4035	/* no candidate found or unsupported, make this an impossible rule */
4036	queue_push(&q, -SYSTEMSOLVABLE1);
4037	}
4038	p = queue_shift(&q); /* get first candidate */
4039	d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q); /* internalize */
4040	}
4041	/* force install of namespace supplements hack */
4042	if (select == SOLVER_SOLVABLE_PROVIDES0x03 && !d && (p == SYSTEMSOLVABLE1 \|\| p == -SYSTEMSOLVABLE1) && ISRELDEP(what)(((what) & 0x80000000) != 0))
4043	{
4044	Reldep *rd = GETRELDEP(pool, what)((pool)->rels + ((what) ^ 0x80000000));
4045	if (rd->flags == REL_NAMESPACE19)
4046	{
4047	p = SYSTEMSOLVABLE1;
4048	if (!solv->installsuppdepq)
4049	{
4050	solv->installsuppdepq = solv_calloc(1, sizeof(Queue));
4051	queue_init(solv->installsuppdepq);
4052	}
4053	queue_pushunique(solv->installsuppdepq, rd->evr == 0 ? rd->name : what);
4054	}
4055	}
4056	solver_addjobrule(solv, p, 0, d, i, weak);
4057	if (how & SOLVER_FORCEBEST0x100000)
4058	hasbestinstalljob = 1;
4059	break;
4060	case SOLVER_ERASE0x0200:
4061	POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: %s%serase %s\n", weak ? "weak " : "", how & 0x040000 ? "clean deps " : "", solver_select2str (pool, select, what));} while (0);
4062	if ((how & SOLVER_CLEANDEPS0x040000) != 0 && !solv->cleandepsmap.size && installed)
4063	map_grow(&solv->cleandepsmap, installed->end - installed->start);
4064	/* specific solvable: by id or by nevra */
4065	name = (select == SOLVER_SOLVABLE0x01 \|\| (select == SOLVER_SOLVABLE_NAME0x02 && ISRELDEP(what)(((what) & 0x80000000) != 0))) ? 0 : -1;
4066	name_s = 0;
4067	if (select == SOLVER_SOLVABLE_ALL0x06) /* hmmm ;) */
4068	{
4069	FOR_POOL_SOLVABLES(p)for (p = 2; p < pool->nsolvables; p++) if (pool->solvables [p].repo == 0) continue; else
4070	solver_addjobrule(solv, -p, 0, 0, i, weak);
4071	}
4072	else if (select == SOLVER_SOLVABLE_REPO0x05)
4073	{
4074	Repo *repo = pool_id2repo(pool, what);
4075	if (repo)
4076	{
4077	FOR_REPO_SOLVABLES(repo, p, s)for (p = (repo)->start, s = (repo)->pool->solvables + p; p < (repo)->end; p++, s = (repo)->pool->solvables + p) if (s->repo != (repo)) continue; else
4078	solver_addjobrule(solv, -p, 0, 0, i, weak);
4079	}
4080	}
4081	#ifdef ENABLE_COMPLEX_DEPS
4082	else if ((select == SOLVER_SOLVABLE_PROVIDES0x03 \|\| select == SOLVER_SOLVABLE_NAME0x02) && pool_is_complex_dep(pool, what))
4083	{
4084	/* no special "erase a specific solvable" handling? */
4085	add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME0x02 ? (CPLXDEPS_NAME(1 << 3) \| CPLXDEPS_TODNF(1 << 0) \| CPLXDEPS_INVERT(1 << 2)) : (CPLXDEPS_TODNF(1 << 0) \| CPLXDEPS_INVERT(1 << 2)), i, weak);
4086	break;
4087	}
4088	#endif
4089	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
4090	{
4091	s = pool->solvables + p;
4092	if (installed && s->repo == installed)
4093	{
4094	name = !name ? s->name : -1;
4095	name_s = s;
4096	}
4097	solver_addjobrule(solv, -p, 0, 0, i, weak);
4098	}
4099	/* special case for "erase a specific solvable": we also
4100	* erase all other solvables with that name, so that they
4101	* don't get picked up as replacement.
4102	* name is > 0 if exactly one installed solvable matched.
4103	*/
4104	/* XXX: look also at packages that obsolete this package? */
4105	if (name > 0)
4106	{
4107	int j, k;
4108	k = solv->nrules;
4109	FOR_PROVIDES(p, pp, name)for (pp = pool_whatprovides(pool, name) ; (p = pool->whatprovidesdata [pp++]) != 0; )
4110	{
4111	s = pool->solvables + p;
4112	if (s->name != name)
4113	continue;
4114	/* keep other versions installed */
4115	if (s->repo == installed)
4116	continue;
4117	/* keep installcandidates of other jobs */
4118	if (MAPTST(&installcandidatemap, p)((&installcandidatemap)->map[(p) >> 3] & (1 << ((p) & 7))))
4119	continue;
4120	if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, name_s, s))
4121	continue;
4122	/* don't add the same rule twice */
4123	for (j = oldnrules; j < k; j++)
4124	if (solv->rules[j].p == -p)
4125	break;
4126	if (j == k)
4127	solver_addjobrule(solv, -p, 0, 0, i, weak); /* remove by id */
4128	}
4129	}
4130	break;
4131
4132	case SOLVER_UPDATE0x0300:
4133	POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));} while (0);
4134	break;
4135	case SOLVER_VERIFY0x0800:
4136	POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));} while (0);
4137	break;
4138	case SOLVER_WEAKENDEPS0x0400:
4139	POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));} while (0);
4140	if (select != SOLVER_SOLVABLE0x01)
4141	break;
4142	s = pool->solvables + what;
4143	weaken_solvable_deps(solv, what);
4144	break;
4145	case SOLVER_MULTIVERSION0x0500:
4146	POOL_DEBUG(SOLV_DEBUG_JOB, "job: %smultiversion %s\n", weak ? "weak " : "", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: %smultiversion %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));} while (0);
4147	break;
4148	case SOLVER_LOCK0x0600:
4149	POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: %slock %s\n", weak ? "weak " : "" , solver_select2str(pool, select, what));} while (0);
4150	if (select == SOLVER_SOLVABLE_ALL0x06)
4151	{
4152	FOR_POOL_SOLVABLES(p)for (p = 2; p < pool->nsolvables; p++) if (pool->solvables [p].repo == 0) continue; else
4153	solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
4154	}
4155	else if (select == SOLVER_SOLVABLE_REPO0x05)
4156	{
4157	Repo *repo = pool_id2repo(pool, what);
4158	if (repo)
4159	{
4160	FOR_REPO_SOLVABLES(repo, p, s)for (p = (repo)->start, s = (repo)->pool->solvables + p; p < (repo)->end; p++, s = (repo)->pool->solvables + p) if (s->repo != (repo)) continue; else
4161	solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
4162	}
4163	}
4164	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
4165	solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
4166	break;
4167	case SOLVER_DISTUPGRADE0x0700:
4168	POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: distupgrade %s\n", solver_select2str (pool, select, what));} while (0);
4169	break;
4170	case SOLVER_DROP_ORPHANED0x0900:
4171	POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: drop orphaned %s\n", solver_select2str (pool, select, what));} while (0);
4172	break;
4173	case SOLVER_USERINSTALLED0x0a00:
4174	POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: user installed %s\n", solver_select2str (pool, select, what));} while (0);
4175	break;
4176	case SOLVER_ALLOWUNINSTALL0x0b00:
4177	POOL_DEBUG(SOLV_DEBUG_JOB, "job: allowuninstall %s\n", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: allowuninstall %s\n", solver_select2str (pool, select, what));} while (0);
4178	break;
4179	case SOLVER_FAVOR0x0c00:
4180	case SOLVER_DISFAVOR0x0d00:
4181	POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s %s\n", (how & SOLVER_JOBMASK) == SOLVER_FAVOR ? "favor" : "disfavor", solver_select2str(pool, select, what))do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: %s %s\n", (how & 0xff00) == 0x0c00 ? "favor" : "disfavor", solver_select2str(pool, select , what));} while (0);
4182	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
4183	{
4184	int j;
4185	if (!solv->favorq)
4186	{
4187	solv->favorq = solv_calloc(1, sizeof(Queue));
4188	queue_init(solv->favorq);
4189	}
4190	j = solv->favorq->count + 1;
4191	queue_push2(solv->favorq, p, (how & SOLVER_JOBMASK0xff00) == SOLVER_FAVOR0x0c00 ? j : -j);
4192	}
4193	break;
4194	default:
4195	POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n")do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), "job: unknown job\n");} while (0);
4196	break;
4197	}
4198
4199	IF_POOLDEBUG (SOLV_DEBUG_JOB)if ((pool->debugmask & ((1<<11))) != 0)
4200	{
4201	int j;
4202	if (solv->nrules == oldnrules)
4203	POOL_DEBUG(SOLV_DEBUG_JOB, " - no rule created\n")do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), " - no rule created\n");} while (0);
4204	for (j = oldnrules; j < solv->nrules; j++)
4205	{
4206	POOL_DEBUG(SOLV_DEBUG_JOB, " - job ")do {if ((pool->debugmask & ((1<<11))) != 0) pool_debug (pool, ((1<<11)), " - job ");} while (0);
4207	solver_printrule(solv, SOLV_DEBUG_JOB(1<<11), solv->rules + j);
4208	}
4209	}
4210	}
4211	assert(solv->ruletojob.count == solv->nrules - solv->jobrules)({ if (solv->ruletojob.count == solv->nrules - solv-> jobrules) ; else __assert_fail ("solv->ruletojob.count == solv->nrules - solv->jobrules" , "/home/brain/Projects/upstream/libsolv/src/solver.c", 4211, __PRETTY_FUNCTION__); });
4212	solv->jobrules_end = solv->nrules;
4213
4214	/* transform favorq into two maps */
4215	if (solv->favorq)
4216	setup_favormaps(solv);
4217
4218	/* now create infarch and dup rules */
4219	if (!solv->noinfarchcheck)
4220	{
4221	solver_addinfarchrules(solv, &addedmap);
4222	#if 0
4223	if (pool->implicitobsoleteusescolors)
4224	{
4225	/* currently doesn't work well with infarch rules, so make
4226	* them weak */
4227	for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
4228	queue_push(&solv->weakruleq, i);
4229	}
4230	#endif
4231	}
4232	else
4233	solv->infarchrules = solv->infarchrules_end = solv->nrules;
4234
4235	if (needduprules)
4236	solver_addduprules(solv, &addedmap);
4237	else
4238	solv->duprules = solv->duprules_end = solv->nrules;
4239
4240	#ifdef ENABLE_LINKED_PKGS
4241	if (solv->instbuddy && solv->updatemap.size)
4242	extend_updatemap_to_buddies(solv);
4243	#endif
4244
4245	if (solv->bestupdatemap_all \|\| solv->bestupdatemap.size \|\| hasbestinstalljob)
4246	solver_addbestrules(solv, hasbestinstalljob);
4247	else
4248	solv->bestrules = solv->bestrules_end = solv->nrules;
4249
4250	if (needduprules)
4251	solver_freedupmaps(solv); /* no longer needed */
4252
4253	if (solv->do_yum_obsoletes)
4254	solver_addyumobsrules(solv);
4255	else
4256	solv->yumobsrules = solv->yumobsrules_end = solv->nrules;
4257
4258	if (1)
4259	solver_addchoicerules(solv);
4260	else
4261	solv->choicerules = solv->choicerules_end = solv->nrules;
4262
4263	if (0)
4264	{
4265	for (i = solv->featurerules; i < solv->nrules; i++)
4266	solver_printruleclass(solv, SOLV_DEBUG_RESULT(1<<10), solv->rules + i);
4267	}
4268	/* all rules created
4269	* --------------------------------------------------------------
4270	* prepare for solving
4271	*/
4272
4273	/* free unneeded memory */
4274	map_free(&addedmap);
4275	map_free(&installcandidatemap);
4276	queue_free(&q);
4277
4278	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\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)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "%d pkg rules, 2 * %d update rules, %d job rules, %d infarch rules, %d dup rules, %d choice rules, %d best 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);} while (0);
4279	POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "overall rule memory used: %d K\n", solv ->nrules * (int)sizeof(Rule) / 1024);} while (0);
4280
4281	/* create weak map */
4282	if (solv->weakruleq.count \|\| solv->recommendsruleq)
4283	{
4284	map_grow(&solv->weakrulemap, solv->nrules);
4285	for (i = 0; i < solv->weakruleq.count; i++)
4286	{
4287	p = solv->weakruleq.elements[i];
4288	MAPSET(&solv->weakrulemap, p)((&solv->weakrulemap)->map[(p) >> 3] \|= 1 << ((p) & 7));
4289	}
4290	if (solv->recommendsruleq)
4291	{
4292	for (i = 0; i < solv->recommendsruleq->count; i++)
4293	{
4294	p = solv->recommendsruleq->elements[i];
4295	MAPSET(&solv->weakrulemap, p)((&solv->weakrulemap)->map[(p) >> 3] \|= 1 << ((p) & 7));
4296	}
4297	}
4298	}
4299
4300	/* enable cleandepsmap creation if we have updatepkgs */
4301	if (solv->cleandeps_updatepkgs && !solv->cleandepsmap.size)
4302	map_grow(&solv->cleandepsmap, installed->end - installed->start);
4303	/* no mistakes */
4304	if (solv->cleandeps_mistakes)
4305	{
4306	queue_free(solv->cleandeps_mistakes);
4307	solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
4308	}
4309
4310	/* all new rules are learnt after this point */
4311	solv->learntrules = solv->nrules;
4312
4313	/* create watches chains */
4314	makewatches(solv);
4315
4316	/* create assertion index. it is only used to speed up
4317	* makeruledecsions() a bit */
4318	for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
4319	if (r->p && !r->w2 && (r->d == 0 \|\| r->d == -1))
4320	queue_push(&solv->ruleassertions, i);
4321
4322	/* disable update rules that conflict with our job */
4323	solver_disablepolicyrules(solv);
4324
4325	/* break orphans if requested */
4326	if (solv->dupmap_all && solv->orphaned.count && solv->break_orphans)
4327	solver_breakorphans(solv);
4328
4329	/*
4330	* ********************************************
4331	* solve!
4332	* ********************************************
4333	*/
4334
4335	now = solv_timems(0);
4336	solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
4337	POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now))do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "solver took %d ms\n", solv_timems(now ));} while (0);
4338
4339	/*
4340	* prepare solution queue if there were problems
4341	*/
4342	solver_prepare_solutions(solv);
4343
4344	POOL_DEBUG(SOLV_DEBUG_STATS, "final solver statistics: %d problems, %d learned rules, %d unsolvable\n", solv->problems.count / 2, solv->stats_learned, solv->stats_unsolvable)do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "final solver statistics: %d problems, %d learned rules, %d unsolvable\n" , solv->problems.count / 2, solv->stats_learned, solv-> stats_unsolvable);} while (0);
4345	POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start))do {if ((pool->debugmask & ((1<<3))) != 0) pool_debug (pool, ((1<<3)), "solver_solve took %d ms\n", solv_timems (solve_start));} while (0);
4346
4347	/* return number of problems */
4348	return solv->problems.count ? solv->problems.count / 2 : 0;
4349	}
4350
4351	Transaction *
4352	solver_create_transaction(Solver *solv)
4353	{
4354	return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->multiversion);
4355	}
4356
4357	void solver_get_orphaned(Solver solv, Queue orphanedq)
4358	{
4359	queue_free(orphanedq);
4360	queue_init_clone(orphanedq, &solv->orphaned);
4361	}
4362
4363	void solver_get_recommendations(Solver solv, Queue recommendationsq, Queue *suggestionsq, int noselected)
4364	{
4365	Pool *pool = solv->pool;
4366	Queue redoq, disabledq;
4367	int goterase, i;
4368	Solvable *s;
4369	Rule *r;
4370	Map obsmap;
4371
4372	if (!recommendationsq && !suggestionsq)
4373	return;
4374
4375	map_init(&obsmap, pool->nsolvables);
4376	if (solv->installed)
4377	{
4378	Id obs, *obsp, p, po, ppo;
4379	for (p = solv->installed->start; p < solv->installed->end; p++)
4380	{
4381	s = pool->solvables + p;
4382	if (s->repo != solv->installed \|\| !s->obsoletes)
4383	continue;
4384	if (solv->decisionmap[p] <= 0)
4385	continue;
4386	if (solv->multiversion.size && MAPTST(&solv->multiversion, p)((&solv->multiversion)->map[(p) >> 3] & ( 1 << ((p) & 7))))
4387	continue;
4388	obsp = s->repo->idarraydata + s->obsoletes;
4389	/* foreach obsoletes */
4390	while ((obs = *obsp++) != 0)
4391	FOR_PROVIDES(po, ppo, obs)for (ppo = pool_whatprovides(pool, obs) ; (po = pool->whatprovidesdata [ppo++]) != 0; )
4392	MAPSET(&obsmap, po)((&obsmap)->map[(po) >> 3] \|= 1 << ((po) & 7));
4393	}
4394	}
4395
4396	queue_init(&redoq);
4397	queue_init(&disabledq);
4398	goterase = 0;
4399	/* disable all erase jobs (including weak "keep uninstalled" rules) */
4400	for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
4401	{
4402	if (r->d < 0) /* disabled ? */
4403	continue;
4404	if (r->p >= 0) /* install job? */
4405	continue;
4406	queue_push(&disabledq, i);
4407	solver_disablerule(solv, r);
4408	goterase++;
4409	}
4410
4411	if (goterase)
4412	{
4413	enabledisablelearntrules(solv);
4414	removedisabledconflicts(solv, &redoq);
4415	}
4416
4417	/*
4418	* find recommended packages
4419	*/
4420	if (recommendationsq)
4421	{
4422	Id rec, *recp, p, pp;
4423
4424	queue_empty(recommendationsq);
4425	/* create map of all recommened packages */
4426	solv->recommends_index = -1;
4427	MAPZERO(&solv->recommendsmap)(memset((&solv->recommendsmap)->map, 0, (&solv-> recommendsmap)->size));
4428
4429	/* put all packages the solver already chose in the map */
4430	for (i = 1; i < solv->decisionq.count; i++)
4431	if ((p = solv->decisionq.elements[i]) > 0 && solv->decisionq_why.elements[i] == 0)
4432	{
4433	if (solv->decisionq_reason.elements[solv->decisionmap[p]] == SOLVER_REASON_WEAKDEP7)
4434	MAPSET(&solv->recommendsmap, p)((&solv->recommendsmap)->map[(p) >> 3] \|= 1 << ((p) & 7));
4435	}
4436
4437	for (i = 0; i < solv->decisionq.count; i++)
4438	{
4439	p = solv->decisionq.elements[i];
4440	if (p < 0)
4441	continue;
4442	s = pool->solvables + p;
4443	if (s->recommends)
4444	{
4445	recp = s->repo->idarraydata + s->recommends;
4446	while ((rec = *recp++) != 0)
4447	{
4448	#ifdef ENABLE_COMPLEX_DEPS
4449	if (pool_is_complex_dep(pool, rec))
4450	{
4451	do_complex_recommendations(solv, rec, &solv->recommendsmap, noselected);
4452	continue;
4453	}
4454	#endif
4455	FOR_PROVIDES(p, pp, rec)for (pp = pool_whatprovides(pool, rec) ; (p = pool->whatprovidesdata [pp++]) != 0; )
4456	if (solv->decisionmap[p] > 0)
4457	break;
4458	if (p)
4459	{
4460	if (!noselected)
4461	{
4462	FOR_PROVIDES(p, pp, rec)for (pp = pool_whatprovides(pool, rec) ; (p = pool->whatprovidesdata [pp++]) != 0; )
4463	if (solv->decisionmap[p] > 0)
4464	MAPSET(&solv->recommendsmap, p)((&solv->recommendsmap)->map[(p) >> 3] \|= 1 << ((p) & 7));
4465	}
4466	continue; /* p != 0: already fulfilled */
4467	}
4468	FOR_PROVIDES(p, pp, rec)for (pp = pool_whatprovides(pool, rec) ; (p = pool->whatprovidesdata [pp++]) != 0; )
4469	MAPSET(&solv->recommendsmap, p)((&solv->recommendsmap)->map[(p) >> 3] \|= 1 << ((p) & 7));
4470	}
4471	}
4472	}
4473	for (i = 1; i < pool->nsolvables; i++)
4474	{
4475	if (solv->decisionmap[i] < 0)
4476	continue;
4477	if (solv->decisionmap[i] > 0 && noselected)
4478	continue;
4479	if (MAPTST(&obsmap, i)((&obsmap)->map[(i) >> 3] & (1 << ((i) & 7))))
4480	continue;
4481	s = pool->solvables + i;
4482	if (!MAPTST(&solv->recommendsmap, i)((&solv->recommendsmap)->map[(i) >> 3] & ( 1 << ((i) & 7))))
4483	{
4484	if (!s->supplements)
4485	continue;
4486	if (!pool_installable(pool, s))
4487	continue;
4488	if (!solver_is_supplementing(solv, s))
4489	continue;
4490	}
4491	queue_push(recommendationsq, i);
4492	}
4493	/* we use MODE_SUGGEST here so that repo prio is ignored */
4494	policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST2);
4495	}
4496
4497	/*
4498	* find suggested packages
4499	*/
4500
4501	if (suggestionsq)
4502	{
4503	Id sug, *sugp, p, pp;
4504
4505	queue_empty(suggestionsq);
4506	/* create map of all suggests that are still open */
4507	solv->recommends_index = -1;
4508	MAPZERO(&solv->suggestsmap)(memset((&solv->suggestsmap)->map, 0, (&solv-> suggestsmap)->size));
4509	for (i = 0; i < solv->decisionq.count; i++)
4510	{
4511	p = solv->decisionq.elements[i];
4512	if (p < 0)
4513	continue;
4514	s = pool->solvables + p;
4515	if (s->suggests)
4516	{
4517	sugp = s->repo->idarraydata + s->suggests;
4518	while ((sug = *sugp++) != 0)
4519	{
4520	#ifdef ENABLE_COMPLEX_DEPS
4521	if (pool_is_complex_dep(pool, sug))
4522	{
4523	do_complex_recommendations(solv, sug, &solv->suggestsmap, noselected);
4524	continue;
4525	}
4526	#endif
4527	FOR_PROVIDES(p, pp, sug)for (pp = pool_whatprovides(pool, sug) ; (p = pool->whatprovidesdata [pp++]) != 0; )
4528	if (solv->decisionmap[p] > 0)
4529	break;
4530	if (p)
4531	{
4532	if (!noselected)
4533	{
4534	FOR_PROVIDES(p, pp, sug)for (pp = pool_whatprovides(pool, sug) ; (p = pool->whatprovidesdata [pp++]) != 0; )
4535	if (solv->decisionmap[p] > 0)
4536	MAPSET(&solv->suggestsmap, p)((&solv->suggestsmap)->map[(p) >> 3] \|= 1 << ((p) & 7));
4537	}
4538	continue; /* already fulfilled */
4539	}
4540	FOR_PROVIDES(p, pp, sug)for (pp = pool_whatprovides(pool, sug) ; (p = pool->whatprovidesdata [pp++]) != 0; )
4541	MAPSET(&solv->suggestsmap, p)((&solv->suggestsmap)->map[(p) >> 3] \|= 1 << ((p) & 7));
4542	}
4543	}
4544	}
4545	for (i = 1; i < pool->nsolvables; i++)
4546	{
4547	if (solv->decisionmap[i] < 0)
4548	continue;
4549	if (solv->decisionmap[i] > 0 && noselected)
4550	continue;
4551	if (MAPTST(&obsmap, i)((&obsmap)->map[(i) >> 3] & (1 << ((i) & 7))))
4552	continue;
4553	s = pool->solvables + i;
4554	if (!MAPTST(&solv->suggestsmap, i)((&solv->suggestsmap)->map[(i) >> 3] & (1 << ((i) & 7))))
4555	{
4556	if (!s->enhances)
4557	continue;
4558	if (!pool_installable(pool, s))
4559	continue;
4560	if (!solver_is_enhancing(solv, s))
4561	continue;
4562	}
4563	queue_push(suggestionsq, i);
4564	}
4565	policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST2);
4566	}
4567
4568	/* undo removedisabledconflicts */
4569	if (redoq.count)
4570	undo_removedisabledconflicts(solv, &redoq);
4571	queue_free(&redoq);
4572
4573	/* undo job rule disabling */
4574	for (i = 0; i < disabledq.count; i++)
4575	solver_enablerule(solv, solv->rules + disabledq.elements[i]);
4576	queue_free(&disabledq);
4577	map_free(&obsmap);
4578	}
4579
4580
4581	/***********************************************************************/
4582	/* disk usage computations */
4583
4584	/*-------------------------------------------------------------------
4585	*
4586	* calculate DU changes
4587	*/
4588
4589	void
4590	solver_calc_duchanges(Solver solv, DUChanges mps, int nmps)
4591	{
4592	Map installedmap;
4593
4594	solver_create_state_maps(solv, &installedmap, 0);
4595	pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
4596	map_free(&installedmap);
4597	}
4598
4599
4600	/*-------------------------------------------------------------------
4601	*
4602	* calculate changes in install size
4603	*/
4604
4605	int
4606	solver_calc_installsizechange(Solver *solv)
4607	{
4608	Map installedmap;
4609	int change;
4610
4611	solver_create_state_maps(solv, &installedmap, 0);
4612	change = pool_calc_installsizechange(solv->pool, &installedmap);
4613	map_free(&installedmap);
4614	return change;
4615	}
4616
4617	void
4618	solver_create_state_maps(Solver solv, Map installedmap, Map *conflictsmap)
4619	{
4620	pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
4621	}
4622
4623	/*-------------------------------------------------------------------
4624	*
4625	* decision introspection
4626	*/
4627
4628	int
4629	solver_get_decisionlevel(Solver *solv, Id p)
4630	{
4631	return solv->decisionmap[p];
4632	}
4633
4634	void
4635	solver_get_decisionqueue(Solver solv, Queue decisionq)
4636	{
4637	queue_free(decisionq);
4638	queue_init_clone(decisionq, &solv->decisionq);
4639	}
4640
4641	int
4642	solver_get_lastdecisionblocklevel(Solver *solv)
4643	{
4644	Id p;
4645	if (solv->decisionq.count == 0)
4646	return 0;
4647	p = solv->decisionq.elements[solv->decisionq.count - 1];
4648	if (p < 0)
4649	p = -p;
4650	return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
4651	}
4652
4653	void
4654	solver_get_decisionblock(Solver solv, int level, Queue decisionq)
4655	{
4656	Id p;
4657	int i;
4658
4659	queue_empty(decisionq);
4660	for (i = 0; i < solv->decisionq.count; i++)
4661	{
4662	p = solv->decisionq.elements[i];
4663	if (p < 0)
4664	p = -p;
4665	if (solv->decisionmap[p] == level \|\| solv->decisionmap[p] == -level)
4666	break;
4667	}
4668	if (i == solv->decisionq.count)
4669	return;
4670	for (i = 0; i < solv->decisionq.count; i++)
4671	{
4672	p = solv->decisionq.elements[i];
4673	if (p < 0)
4674	p = -p;
4675	if (solv->decisionmap[p] == level \|\| solv->decisionmap[p] == -level)
4676	queue_push(decisionq, p);
4677	else
4678	break;
4679	}
4680	}
4681
4682	int
4683	solver_describe_decision(Solver solv, Id p, Id infop)
4684	{
4685	int i;
4686	Id pp, why;
4687
4688	if (infop)
4689	*infop = 0;
4690	if (!solv->decisionmap[p])
4691	return SOLVER_REASON_UNRELATED0;
4692	pp = solv->decisionmap[p] < 0 ? -p : p;
4693	for (i = 0; i < solv->decisionq.count; i++)
4694	if (solv->decisionq.elements[i] == pp)
4695	break;
4696	if (i == solv->decisionq.count) /* just in case... */
4697	return SOLVER_REASON_UNRELATED0;
4698	why = solv->decisionq_why.elements[i];
4699	if (infop)
4700	*infop = why > 0 ? why : -why;
4701	if (why > 0)
4702	return SOLVER_REASON_UNIT_RULE1;
4703	i = solv->decisionmap[p] >= 0 ? solv->decisionmap[p] : -solv->decisionmap[p];
4704	return solv->decisionq_reason.elements[i];
4705	}
4706
4707
4708	void
4709	solver_describe_weakdep_decision(Solver solv, Id p, Queue whyq)
4710	{
4711	Pool *pool = solv->pool;
4712	int i;
4713	int level = solv->decisionmap[p];
4714	int decisionno;
4715	Solvable *s;
4716
4717	queue_empty(whyq);
4718	if (level < 0)
4719	return; /* huh? */
4720	for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
4721	if (solv->decisionq.elements[decisionno] == p)
4722	break;
4723	if (decisionno == solv->decisionq.count)
4724	return; /* huh? */
4725	i = solv->decisionmap[p] >= 0 ? solv->decisionmap[p] : -solv->decisionmap[p];
4726	if (solv->decisionq_reason.elements[i] != SOLVER_REASON_WEAKDEP7)
4727	return; /* huh? */
4728
4729	/* 1) list all packages that recommend us */
4730	for (i = 1; i < pool->nsolvables; i++)
4731	{
4732	Id *recp, rec, pp2, p2;
4733	if (solv->decisionmap[i] < 0 \|\| solv->decisionmap[i] >= level)
4734	continue;
4735	s = pool->solvables + i;
4736	if (!s->recommends)
4737	continue;
4738	if (!solv->addalreadyrecommended && s->repo == solv->installed)
4739	continue;
4740	recp = s->repo->idarraydata + s->recommends;
4741	while ((rec = *recp++) != 0)
4742	{
4743	int found = 0;
4744	FOR_PROVIDES(p2, pp2, rec)for (pp2 = pool_whatprovides(pool, rec) ; (p2 = pool->whatprovidesdata [pp2++]) != 0; )
4745	{
4746	if (p2 == p)
4747	found = 1;
4748	else
4749	{
4750	/* if p2 is already installed, this recommends is ignored */
4751	if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4752	break;
4753	}
4754	}
4755	if (!p2 && found)
4756	{
4757	queue_push(whyq, SOLVER_REASON_RECOMMENDED16);
4758	queue_push2(whyq, i, rec);
4759	}
4760	}
4761	}
4762	/* 2) list all supplements */
4763	s = pool->solvables + p;
4764	if (s->supplements && level > 0)
4765	{
4766	Id *supp, sup, pp2, p2;
4767	/* this is a hack. to use solver_dep_fulfilled we temporarily clear
4768	* everything above our level in the decisionmap */
4769	for (i = decisionno; i < solv->decisionq.count; i++ )
4770	{
4771	p2 = solv->decisionq.elements[i];
4772	if (p2 > 0)
4773	solv->decisionmap[p2] = -solv->decisionmap[p2];
4774	}
4775	supp = s->repo->idarraydata + s->supplements;
4776	while ((sup = *supp++) != 0)
4777	if (solver_dep_fulfilled(solv, sup))
4778	{
4779	int found = 0;
4780	/* let's see if this is an easy supp */
4781	FOR_PROVIDES(p2, pp2, sup)for (pp2 = pool_whatprovides(pool, sup) ; (p2 = pool->whatprovidesdata [pp2++]) != 0; )
4782	{
4783	if (!solv->addalreadyrecommended && solv->installed)
4784	{
4785	if (pool->solvables[p2].repo == solv->installed)
4786	continue;
4787	}
4788	if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4789	{
4790	queue_push(whyq, SOLVER_REASON_SUPPLEMENTED17);
4791	queue_push2(whyq, p2, sup);
4792	found = 1;
4793	}
4794	}
4795	if (!found)
4796	{
4797	/* hard case, just note dependency with no package */
4798	queue_push(whyq, SOLVER_REASON_SUPPLEMENTED17);
4799	queue_push2(whyq, 0, sup);
4800	}
4801	}
4802	for (i = decisionno; i < solv->decisionq.count; i++)
4803	{
4804	p2 = solv->decisionq.elements[i];
4805	if (p2 > 0)
4806	solv->decisionmap[p2] = -solv->decisionmap[p2];
4807	}
4808	}
4809	}
4810
4811	void
4812	pool_job2solvables(Pool pool, Queue pkgs, Id how, Id what)
4813	{
4814	Id p, pp;
4815	how &= SOLVER_SELECTMASK0xff;
4816	queue_empty(pkgs);
4817	if (how == SOLVER_SOLVABLE_ALL0x06)
4818	{
4819	FOR_POOL_SOLVABLES(p)for (p = 2; p < pool->nsolvables; p++) if (pool->solvables [p].repo == 0) continue; else
4820	queue_push(pkgs, p);
4821	}
4822	else if (how == SOLVER_SOLVABLE_REPO0x05)
4823	{
4824	Repo *repo = pool_id2repo(pool, what);
4825	Solvable *s;
4826	if (repo)
4827	{
4828	FOR_REPO_SOLVABLES(repo, p, s)for (p = (repo)->start, s = (repo)->pool->solvables + p; p < (repo)->end; p++, s = (repo)->pool->solvables + p) if (s->repo != (repo)) continue; else
4829	queue_push(pkgs, p);
4830	}
4831	}
4832	else
4833	{
4834	FOR_JOB_SELECT(p, pp, how, what)if (how == 0x05 \|\| how == 0x06) p = pp = 0; else for (pp = (how == 0x01 ? 0 : how == 0x04 ? what : pool_whatprovides(pool, what )), p = (how == 0x01 ? what : pool->whatprovidesdata[pp++] ); p ; p = pool->whatprovidesdata[pp++]) if (how == 0x02 && pool_match_nevr(pool, pool->solvables + p, what) == 0) continue ; else
4835	queue_push(pkgs, p);
4836	}
4837	}
4838
4839	int
4840	pool_isemptyupdatejob(Pool *pool, Id how, Id what)
4841	{
4842	Id p, pp, pi, pip;
4843	Id select = how & SOLVER_SELECTMASK0xff;
4844	if ((how & SOLVER_JOBMASK0xff00) != SOLVER_UPDATE0x0300)
4845	return 0;
4846	if (select == SOLVER_SOLVABLE_ALL0x06 \|\| select == SOLVER_SOLVABLE_REPO0x05)
4847	return 0;
4848	if (!pool->installed)
4849	return 1;
4850	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
4851	if (pool->solvables[p].repo == pool->installed)
4852	return 0;
4853	/* hard work */
4854	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
4855	{
4856	Solvable *s = pool->solvables + p;
4857	FOR_PROVIDES(pi, pip, s->name)for (pip = pool_whatprovides(pool, s->name) ; (pi = pool-> whatprovidesdata[pip++]) != 0; )
4858	{
4859	Solvable *si = pool->solvables + pi;
4860	if (si->repo != pool->installed \|\| si->name != s->name)
4861	continue;
4862	return 0;
4863	}
4864	if (s->obsoletes)
4865	{
4866	Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4867	while ((obs = *obsp++) != 0)
4868	{
4869	FOR_PROVIDES(pi, pip, obs)for (pip = pool_whatprovides(pool, obs) ; (pi = pool->whatprovidesdata [pip++]) != 0; )
4870	{
4871	Solvable *si = pool->solvables + pi;
4872	if (si->repo != pool->installed)
4873	continue;
4874	if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
4875	continue;
4876	if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
4877	continue;
4878	return 0;
4879	}
4880	}
4881	}
4882	}
4883	return 1;
4884	}
4885
4886	static int
4887	get_userinstalled_cmp(const void ap, const void bp, void *dp)
4888	{
4889	return (Id )ap - (Id )bp;
4890	}
4891
4892	static int
4893	get_userinstalled_cmp_names(const void ap, const void bp, void *dp)
4894	{
4895	Pool *pool = dp;
4896	return strcmp(pool_id2str(pool, (Id )ap), pool_id2str(pool, (Id )bp));
4897	}
4898
4899	static int
4900	get_userinstalled_cmp_namearch(const void ap, const void bp, void *dp)
4901	{
4902	Pool *pool = dp;
4903	int r;
4904	r = strcmp(pool_id2str(pool, ((Id )ap)[0]), pool_id2str(pool, ((Id )bp)[0]));
4905	if (r)
4906	return r;
4907	return strcmp(pool_id2str(pool, ((Id )ap)[1]), pool_id2str(pool, ((Id )bp)[1]));
4908	}
4909
4910	static void
4911	get_userinstalled_sort_uniq(Pool pool, Queue q, int flags)
4912	{
4913	Id lastp = -1, lasta = -1;
4914	int i, j;
4915	if (q->count < ((flags & GET_USERINSTALLED_NAMEARCH(1 << 2)) ? 4 : 2))
4916	return;
4917	if ((flags & GET_USERINSTALLED_NAMEARCH(1 << 2)) != 0)
4918	solv_sort(q->elements, q->count / 2, 2 * sizeof(Id), get_userinstalled_cmp_namearch, pool);
4919	else if ((flags & GET_USERINSTALLED_NAMES(1 << 0)) != 0)
4920	solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp_names, pool);
4921	else
4922	solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp, 0);
4923	if ((flags & GET_USERINSTALLED_NAMEARCH(1 << 2)) != 0)
4924	{
4925	for (i = j = 0; i < q->count; i += 2)
4926	if (q->elements[i] != lastp \|\| q->elements[i + 1] != lasta)
4927	{
4928	q->elements[j++] = lastp = q->elements[i];
4929	q->elements[j++] = lasta = q->elements[i + 1];
4930	}
4931	}
4932	else
4933	{
4934	for (i = j = 0; i < q->count; i++)
4935	if (q->elements[i] != lastp)
4936	q->elements[j++] = lastp = q->elements[i];
4937	}
4938	queue_truncate(q, j);
4939	}
4940
4941	static void
4942	namearch2solvables(Pool pool, Queue q, Queue *qout, int job)
4943	{
4944	int i;
4945	if (!pool->installed)
4946	return;
4947	for (i = 0; i < q->count; i += 2)
4948	{
4949	Id p, pp, name = q->elements[i], arch = q->elements[i + 1];
4950	FOR_PROVIDES(p, pp, name)for (pp = pool_whatprovides(pool, name) ; (p = pool->whatprovidesdata [pp++]) != 0; )
4951	{
4952	Solvable *s = pool->solvables + p;
4953	if (s->repo != pool->installed \|\| s->name != name \|\| (arch && s->arch != arch))
4954	continue;
4955	if (job)
4956	queue_push(qout, job);
4957	queue_push(qout, p);
4958	}
4959	}
4960	}
4961
4962	void
4963	solver_get_userinstalled(Solver solv, Queue q, int flags)
4964	{
4965	Pool *pool = solv->pool;
4966	Id p, p2, pp;
4967	Solvable *s;
4968	Repo *installed = solv->installed;
4969	int i, j;
4970	Map userinstalled;
4971
4972	map_init(&userinstalled, 0);
4973	queue_empty(q);
4974	/* first process jobs */
4975	for (i = 0; i < solv->job.count; i += 2)
4976	{
4977	Id how = solv->job.elements[i];
4978	Id what, select;
4979	if (installed && (how & SOLVER_JOBMASK0xff00) == SOLVER_USERINSTALLED0x0a00)
4980	{
4981	if (!userinstalled.size)
4982	map_grow(&userinstalled, installed->end - installed->start);
4983	what = solv->job.elements[i + 1];
4984	select = how & SOLVER_SELECTMASK0xff;
4985	if (select == SOLVER_SOLVABLE_ALL0x06 \|\| (select == SOLVER_SOLVABLE_REPO0x05 && what == installed->repoid))
4986	{
4987	FOR_REPO_SOLVABLES(installed, p, s)for (p = (installed)->start, s = (installed)->pool-> solvables + p; p < (installed)->end; p++, s = (installed )->pool->solvables + p) if (s->repo != (installed)) continue ; else
4988	MAPSET(&userinstalled, p - installed->start)((&userinstalled)->map[(p - installed->start) >> 3] \|= 1 << ((p - installed->start) & 7));
4989	}
4990	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
4991	if (pool->solvables[p].repo == installed)
4992	MAPSET(&userinstalled, p - installed->start)((&userinstalled)->map[(p - installed->start) >> 3] \|= 1 << ((p - installed->start) & 7));
4993	continue;
4994	}
4995	if ((how & SOLVER_JOBMASK0xff00) != SOLVER_INSTALL0x0100)
4996	continue;
4997	if ((how & SOLVER_NOTBYUSER0x400000) != 0)
4998	continue;
4999	what = solv->job.elements[i + 1];
5000	select = how & SOLVER_SELECTMASK0xff;
5001	FOR_JOB_SELECT(p, pp, select, what)if (select == 0x05 \|\| select == 0x06) p = pp = 0; else for (pp = (select == 0x01 ? 0 : select == 0x04 ? what : pool_whatprovides (pool, what)), p = (select == 0x01 ? what : pool->whatprovidesdata [pp++]); p ; p = pool->whatprovidesdata[pp++]) if (select == 0x02 && pool_match_nevr(pool, pool->solvables + p , what) == 0) continue; else
5002	if (solv->decisionmap[p] > 0)
5003	{
5004	queue_push(q, p);
5005	#ifdef ENABLE_LINKED_PKGS
5006	if (has_package_link(pool, pool->solvables + p))
5007	{
5008	int j;
5009	Queue lq;
5010	queue_init(&lq);
5011	find_package_link(pool, pool->solvables + p, 0, &lq, 0, 0);
5012	for (j = 0; j < lq.count; j++)
5013	if (solv->decisionmap[lq.elements[j]] > 0)
5014	queue_push(q, lq.elements[j]);
5015	}
5016	#endif
5017	}
5018	}
5019	/* now process updates of userinstalled packages */
5020	if (installed && userinstalled.size)
5021	{
5022	for (i = 1; i < solv->decisionq.count; i++)
5023	{
5024	p = solv->decisionq.elements[i];
5025	if (p <= 0)
5026	continue;
5027	s = pool->solvables + p;
5028	if (!s->repo)
5029	continue;
5030	if (s->repo == installed)
5031	{
5032	if (MAPTST(&userinstalled, p - installed->start)((&userinstalled)->map[(p - installed->start) >> 3] & (1 << ((p - installed->start) & 7))))
5033	queue_push(q, p);
5034	continue;
5035	}
5036	/* new package, check if we replace a userinstalled one */
5037	FOR_PROVIDES(p2, pp, s->name)for (pp = pool_whatprovides(pool, s->name) ; (p2 = pool-> whatprovidesdata[pp++]) != 0; )
5038	{
5039	Solvable *ps = pool->solvables + p2;
5040	if (p2 == p \|\| ps->repo != installed \|\| !MAPTST(&userinstalled, p2 - installed->start)((&userinstalled)->map[(p2 - installed->start) >> 3] & (1 << ((p2 - installed->start) & 7))))
5041	continue;
5042	if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
5043	continue;
5044	if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
5045	continue;
5046	queue_push(q, p);
5047	break;
5048	}
5049	if (!p2 && s->repo != installed && s->obsoletes)
5050	{
5051	Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
5052	while ((obs = *obsp++) != 0)
5053	{
5054	FOR_PROVIDES(p2, pp, obs)for (pp = pool_whatprovides(pool, obs) ; (p2 = pool->whatprovidesdata [pp++]) != 0; )
5055	{
5056	Solvable *ps = pool->solvables + p2;
5057	if (p2 == p \|\| ps->repo != installed \|\| !MAPTST(&userinstalled, p2 - installed->start)((&userinstalled)->map[(p2 - installed->start) >> 3] & (1 << ((p2 - installed->start) & 7))))
5058	continue;
5059	if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
5060	continue;
5061	if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
5062	continue;
5063	queue_push(q, p);
5064	break;
5065	}
5066	if (p2)
5067	break;
5068	}
5069	}
5070	}
5071	}
5072	map_free(&userinstalled);
5073
5074	/* convert to desired output format */
5075	if ((flags & GET_USERINSTALLED_NAMEARCH(1 << 2)) != 0)
5076	{
5077	int qcount = q->count;
5078	queue_insertn(q, 0, qcount, 0);
5079	for (i = j = 0; i < qcount; i++)
5080	{
5081	s = pool->solvables + q->elements[i + qcount];
5082	q->elements[j++] = s->name;
5083	q->elements[j++] = s->arch;
5084	}
5085	}
5086	else if ((flags & GET_USERINSTALLED_NAMES(1 << 0)) != 0)
5087	{
5088	for (i = 0; i < q->count; i++)
5089	{
5090	s = pool->solvables + q->elements[i];
5091	q->elements[i] = s->name;
5092	}
5093	}
5094	/* sort and unify */
5095	get_userinstalled_sort_uniq(pool, q, flags);
5096
5097	/* invert if asked for */
5098	if ((flags & GET_USERINSTALLED_INVERTED(1 << 1)) != 0)
5099	{
5100	/* first generate queue with all installed packages */
5101	Queue invq;
5102	queue_init(&invq);
5103	for (i = 1; i < solv->decisionq.count; i++)
5104	{
5105	p = solv->decisionq.elements[i];
5106	if (p <= 0)
5107	continue;
5108	s = pool->solvables + p;
5109	if (!s->repo)
5110	continue;
5111	if ((flags & GET_USERINSTALLED_NAMEARCH(1 << 2)) != 0)
5112	queue_push2(&invq, s->name, s->arch);
5113	else if ((flags & GET_USERINSTALLED_NAMES(1 << 0)) != 0)
5114	queue_push(&invq, s->name);
5115	else
5116	queue_push(&invq, p);
5117	}
5118	/* push q on invq, just in case... */
5119	queue_insertn(&invq, invq.count, q->count, q->elements);
5120	get_userinstalled_sort_uniq(pool, &invq, flags);
5121	/* subtract queues (easy as they are sorted and invq is a superset of q) */
5122	if ((flags & GET_USERINSTALLED_NAMEARCH(1 << 2)) != 0)
5123	{
5124	if (q->count)
5125	{
5126	for (i = j = 0; i < invq.count; i += 2)
5127	if (invq.elements[i] == q->elements[j] && invq.elements[i + 1] == q->elements[j + 1])
5128	{
5129	invq.elements[i] = invq.elements[i + 1] = 0;
5130	j += 2;
5131	if (j >= q->count)
5132	break;
5133	}
5134	queue_empty(q);
5135	}
5136	for (i = 0; i < invq.count; i += 2)
5137	if (invq.elements[i])
5138	queue_push2(q, invq.elements[i], invq.elements[i + 1]);
5139	}
5140	else
5141	{
5142	if (q->count)
5143	{
5144	for (i = j = 0; i < invq.count; i++)
5145	if (invq.elements[i] == q->elements[j])
5146	{
5147	invq.elements[i] = 0;
5148	if (++j >= q->count)
5149	break;
5150	}
5151	queue_empty(q);
5152	}
5153	for (i = 0; i < invq.count; i++)
5154	if (invq.elements[i])
5155	queue_push(q, invq.elements[i]);
5156	}
5157	queue_free(&invq);
5158	}
5159	}
5160
5161	void
5162	pool_add_userinstalled_jobs(Pool pool, Queue q, Queue *job, int flags)
5163	{
5164	int i;
5165
5166	if ((flags & GET_USERINSTALLED_INVERTED(1 << 1)) != 0)
5167	{
5168	Queue invq;
5169	Id p, lastid;
5170	Solvable *s;
5171	int bad;
5172	if (!pool->installed)
5173	return;
5174	queue_init(&invq);
5175	if ((flags & GET_USERINSTALLED_NAMEARCH(1 << 2)) != 0)
5176	flags &= ~GET_USERINSTALLED_NAMES(1 << 0); /* just in case */
5177	FOR_REPO_SOLVABLES(pool->installed, p, s)for (p = (pool->installed)->start, s = (pool->installed )->pool->solvables + p; p < (pool->installed)-> end; p++, s = (pool->installed)->pool->solvables + p ) if (s->repo != (pool->installed)) continue; else
5178	queue_push(&invq, flags & GET_USERINSTALLED_NAMES(1 << 0) ? s->name : p);
5179	if ((flags & GET_USERINSTALLED_NAMEARCH(1 << 2)) != 0)
5180	{
5181	/* for namearch we convert to packages */
5182	namearch2solvables(pool, q, &invq, 0);
5183	get_userinstalled_sort_uniq(pool, &invq, flags);
5184	namearch2solvables(pool, q, &invq, 0);
5185	flags = 0;
5186	}
5187	else
5188	{
5189	queue_insertn(&invq, invq.count, q->count, q->elements);
5190	get_userinstalled_sort_uniq(pool, &invq, flags);
5191	/* now the fun part, add q again, sort, and remove all dups */
5192	queue_insertn(&invq, invq.count, q->count, q->elements);
5193	}
5194	if (invq.count > 1)
5195	{
5196	if ((flags & GET_USERINSTALLED_NAMES(1 << 0)) != 0)
5197	solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp_names, pool);
5198	else
5199	solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp, 0);
5200	}
5201	lastid = -1;
5202	bad = 1;
5203	for (i = 0; i < invq.count; i++)
5204	{
5205	if (invq.elements[i] == lastid)
5206	{
5207	bad = 1;
5208	continue;
5209	}
5210	if (!bad)
5211	queue_push2(job, SOLVER_USERINSTALLED0x0a00 \| (flags & GET_USERINSTALLED_NAMES(1 << 0) ? SOLVER_SOLVABLE_NAME0x02 : SOLVER_SOLVABLE0x01), lastid);
5212	bad = 0;
5213	lastid = invq.elements[i];
5214	}
5215	if (!bad)
5216	queue_push2(job, SOLVER_USERINSTALLED0x0a00 \| (flags & GET_USERINSTALLED_NAMES(1 << 0) ? SOLVER_SOLVABLE_NAME0x02 : SOLVER_SOLVABLE0x01), lastid);
5217	queue_free(&invq);
5218	}
5219	else
5220	{
5221	if (flags & GET_USERINSTALLED_NAMEARCH(1 << 2))
5222	namearch2solvables(pool, q, job, SOLVER_USERINSTALLED0x0a00 \| SOLVER_SOLVABLE0x01);
5223	else
5224	{
5225	for (i = 0; i < q->count; i++)
5226	queue_push2(job, SOLVER_USERINSTALLED0x0a00 \| (flags & GET_USERINSTALLED_NAMES(1 << 0) ? SOLVER_SOLVABLE_NAME0x02 : SOLVER_SOLVABLE0x01), q->elements[i]);
5227	}
5228	}
5229	}
5230
5231	int
5232	solver_alternatives_count(Solver *solv)
5233	{
5234	Id *elements = solv->branches.elements;
5235	int res, count;
5236	for (res = 0, count = solv->branches.count; count; res++)
5237	count -= elements[count - 2];
5238	return res;
5239	}
5240
5241	int
5242	solver_get_alternative(Solver solv, Id alternative, Id idp, Id fromp, Id chosenp, Queue choices, int levelp)
5243	{
5244	int cnt = solver_alternatives_count(solv);
5245	int count = solv->branches.count;
5246	Id *elements = solv->branches.elements;
5247	if (choices)
5248	queue_empty(choices);
5249	if (alternative <= 0 \|\| alternative > cnt)
5250	return 0;
5251	elements += count;
5252	for (; cnt > alternative; cnt--)
5253	elements -= elements[-2];
5254	if (levelp)
5255	*levelp = elements[-1];
5256	if (fromp)
5257	*fromp = elements[-4];
5258	if (idp)
5259	*idp = elements[-3];
5260	if (chosenp)
5261	{
5262	int i;
5263	*chosenp = 0;
5264	for (i = elements[-2]; i > 4; i--)
5265	{
5266	Id p = -elements[-i];
5267	if (p > 0 && solv->decisionmap[p] == elements[-1] + 1)
5268	{
5269	*chosenp = p;
5270	break;
5271	}
5272	}
5273	}
5274	if (choices)
5275	queue_insertn(choices, 0, elements[-2] - 4, elements - elements[-2]);
5276	return elements[-4] ? SOLVER_ALTERNATIVE_TYPE_RECOMMENDS2 : SOLVER_ALTERNATIVE_TYPE_RULE1;
5277	}
5278
5279	const char *
5280	solver_select2str(Pool *pool, Id select, Id what)
5281	{
5282	const char *s;
5283	char *b;
5284	select &= SOLVER_SELECTMASK0xff;
5285	if (select == SOLVER_SOLVABLE0x01)
5286	return pool_solvid2str(pool, what);
5287	if (select == SOLVER_SOLVABLE_NAME0x02)
5288	return pool_dep2str(pool, what);
5289	if (select == SOLVER_SOLVABLE_PROVIDES0x03)
5290	{
5291	s = pool_dep2str(pool, what);
5292	b = pool_alloctmpspace(pool, 11 + strlen(s));
5293	sprintf(b, "providing %s", s);
5294	return b;
5295	}
5296	if (select == SOLVER_SOLVABLE_ONE_OF0x04)
5297	{
5298	Id p;
5299	b = 0;
5300	while ((p = pool->whatprovidesdata[what++]) != 0)
5301	{
5302	s = pool_solvid2str(pool, p);
5303	if (b)
5304	b = pool_tmpappend(pool, b, ", ", s);
5305	else
5306	b = pool_tmpjoin(pool, s, 0, 0);
5307	pool_freetmpspace(pool, s);
5308	}
5309	return b ? b : "nothing";
5310	}
5311	if (select == SOLVER_SOLVABLE_REPO0x05)
5312	{
5313	b = pool_alloctmpspace(pool, 20);
5314	sprintf(b, "repo #%d", what);
5315	return b;
5316	}
5317	if (select == SOLVER_SOLVABLE_ALL0x06)
5318	return "all packages";
5319	return "unknown job select";
5320	}
5321
5322	const char *
5323	pool_job2str(Pool *pool, Id how, Id what, Id flagmask)
5324	{
5325	Id select = how & SOLVER_SELECTMASK0xff;
5326	const char strstart = 0, strend = 0;
5327	char *s;
5328	int o;
5329
5330	switch (how & SOLVER_JOBMASK0xff00)
5331	{
5332	case SOLVER_NOOP0x0000:
5333	return "do nothing";
5334	case SOLVER_INSTALL0x0100:
5335	if (select == SOLVER_SOLVABLE0x01 && pool->installed && pool->solvables[what].repo == pool->installed)
5336	strstart = "keep ", strend = " installed";
5337	else if (select == SOLVER_SOLVABLE0x01 \|\| select == SOLVER_SOLVABLE_NAME0x02)
5338	strstart = "install ";
5339	else if (select == SOLVER_SOLVABLE_PROVIDES0x03)
5340	strstart = "install a package ";
5341	else
5342	strstart = "install one of ";
5343	break;
5344	case SOLVER_ERASE0x0200:
5345	if (select == SOLVER_SOLVABLE0x01 && !(pool->installed && pool->solvables[what].repo == pool->installed))
5346	strstart = "keep ", strend = " uninstalled";
5347	else if (select == SOLVER_SOLVABLE_PROVIDES0x03)
5348	strstart = "deinstall all packages ";
5349	else
5350	strstart = "deinstall ";
5351	break;
5352	case SOLVER_UPDATE0x0300:
5353	strstart = "update ";
5354	break;
5355	case SOLVER_WEAKENDEPS0x0400:
5356	strstart = "weaken deps of ";
5357	break;
5358	case SOLVER_MULTIVERSION0x0500:
5359	strstart = "multi version ";
5360	break;
5361	case SOLVER_LOCK0x0600:
5362	strstart = "lock ";
5363	break;
5364	case SOLVER_DISTUPGRADE0x0700:
5365	strstart = "dist upgrade ";
5366	break;
5367	case SOLVER_VERIFY0x0800:
5368	strstart = "verify ";
5369	break;
5370	case SOLVER_DROP_ORPHANED0x0900:
5371	strstart = "deinstall ", strend = " if orphaned";
5372	break;
5373	case SOLVER_USERINSTALLED0x0a00:
5374	strstart = "regard ", strend = " as userinstalled";
5375	break;
5376	case SOLVER_ALLOWUNINSTALL0x0b00:
5377	strstart = "allow deinstallation of ";
5378	break;
5379	case SOLVER_FAVOR0x0c00:
5380	strstart = "favor ";
5381	break;
5382	case SOLVER_DISFAVOR0x0d00:
5383	strstart = "disfavor ";
5384	break;
5385	default:
5386	strstart = "unknown job ";
5387	break;
5388	}
5389	s = pool_tmpjoin(pool, strstart, solver_select2str(pool, select, what), strend);
5390	how &= flagmask;
5391	if ((how & ~(SOLVER_SELECTMASK0xff\|SOLVER_JOBMASK0xff00)) == 0)
5392	return s;
5393	o = strlen(s);
5394	s = pool_tmpappend(pool, s, " ", 0);
5395	if (how & SOLVER_WEAK0x010000)
5396	s = pool_tmpappend(pool, s, ",weak", 0);
5397	if (how & SOLVER_ESSENTIAL0x020000)
5398	s = pool_tmpappend(pool, s, ",essential", 0);
5399	if (how & SOLVER_CLEANDEPS0x040000)
5400	s = pool_tmpappend(pool, s, ",cleandeps", 0);
5401	if (how & SOLVER_ORUPDATE0x080000)
5402	s = pool_tmpappend(pool, s, ",orupdate", 0);
5403	if (how & SOLVER_FORCEBEST0x100000)
5404	s = pool_tmpappend(pool, s, ",forcebest", 0);
5405	if (how & SOLVER_TARGETED0x200000)
5406	s = pool_tmpappend(pool, s, ",targeted", 0);
5407	if (how & SOLVER_SETEV0x01000000)
5408	s = pool_tmpappend(pool, s, ",setev", 0);
5409	if (how & SOLVER_SETEVR0x02000000)
5410	s = pool_tmpappend(pool, s, ",setevr", 0);
5411	if (how & SOLVER_SETARCH0x04000000)
5412	s = pool_tmpappend(pool, s, ",setarch", 0);
5413	if (how & SOLVER_SETVENDOR0x08000000)
5414	s = pool_tmpappend(pool, s, ",setvendor", 0);
5415	if (how & SOLVER_SETREPO0x10000000)
5416	s = pool_tmpappend(pool, s, ",setrepo", 0);
5417	if (how & SOLVER_SETNAME0x40000000)
5418	s = pool_tmpappend(pool, s, ",setname", 0);
5419	if (how & SOLVER_NOAUTOSET0x20000000)
5420	s = pool_tmpappend(pool, s, ",noautoset", 0);
5421	if (s[o + 1] != ',')
5422	s = pool_tmpappend(pool, s, ",?", 0);
5423	s[o + 1] = '[';
5424	return pool_tmpappend(pool, s, "]", 0);
5425	}
5426
5427	const char *
5428	solver_alternative2str(Solver *solv, int type, Id id, Id from)
5429	{
5430	Pool *pool = solv->pool;
5431	if (type == SOLVER_ALTERNATIVE_TYPE_RECOMMENDS2)
5432	{
5433	const char *s = pool_dep2str(pool, id);
5434	return pool_tmpappend(pool, s, ", recommended by ", pool_solvid2str(pool, from));
5435	}
5436	if (type == SOLVER_ALTERNATIVE_TYPE_RULE1)
5437	{
5438	int rtype;
5439	Id depfrom, depto, dep;
5440	char buf[64];
5441	if (solver_ruleclass(solv, id) == SOLVER_RULE_CHOICE)
5442	id = solver_rule2pkgrule(solv, id);
5443	rtype = solver_ruleinfo(solv, id, &depfrom, &depto, &dep);
5444	if ((rtype & SOLVER_RULE_TYPEMASK0xff00) == SOLVER_RULE_JOB)
5445	{
5446	if ((depto & SOLVER_SELECTMASK0xff) == SOLVER_SOLVABLE_PROVIDES0x03)
5447	return pool_dep2str(pool, dep);
5448	return solver_select2str(pool, depto & SOLVER_SELECTMASK0xff, dep);
5449	}
5450	if (rtype == SOLVER_RULE_PKG_REQUIRES)
5451	{
5452	const char *s = pool_dep2str(pool, dep);
5453	return pool_tmpappend(pool, s, ", required by ", pool_solvid2str(pool, depfrom));
5454	}
5455	sprintf(buf, "Rule #%d", id);
5456	return pool_tmpjoin(pool, buf, 0, 0);
5457	}
5458	return "unknown alternative type";
5459	}
5460