2 * Copyright (c) 2014, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
11 * normalize complex dependencies into CNF/DNF form
23 #ifdef ENABLE_COMPLEX_DEPS
28 pool_is_complex_dep_rd(Pool *pool, Reldep *rd)
32 if (rd->flags == REL_AND || rd->flags == REL_COND || rd->flags == REL_UNLESS) /* those two are the complex ones */
34 if (rd->flags != REL_OR)
36 if (ISRELDEP(rd->name) && pool_is_complex_dep_rd(pool, GETRELDEP(pool, rd->name)))
38 if (!ISRELDEP(rd->evr))
40 rd = GETRELDEP(pool, rd->evr);
44 /* expand simple dependencies into package lists */
46 expand_simpledeps(Pool *pool, Queue *bq, int start, int split)
51 for (i = start; i < end; i++)
54 newsplit = bq->count - (end - start);
56 if (x == pool->nsolvables)
58 Id *dp = pool->whatprovidesdata + bq->elements[++i];
66 newsplit = bq->count - (end - start);
67 queue_deleten(bq, start, end - start);
73 print_depblocks(Pool *pool, Queue *bq, int start)
77 for (i = start; i < bq->count; i++)
79 if (bq->elements[i] == pool->nsolvables)
81 Id *dp = pool->whatprovidesdata + bq->elements[++i];
84 printf(" %s", pool_solvid2str(pool, *dp++));
87 else if (bq->elements[i] > 0)
88 printf(" %s", pool_solvid2str(pool, bq->elements[i]));
89 else if (bq->elements[i] < 0)
90 printf(" -%s", pool_solvid2str(pool, -bq->elements[i]));
98 /* invert all literals in the blocks. note that this also turns DNF into CNF and vice versa */
100 invert_depblocks(Pool *pool, Queue *bq, int start, int r)
103 if (r == 0 || r == 1)
105 expand_simpledeps(pool, bq, start, 0);
107 for (i = j = start; i < end; i++)
111 bq->elements[i] = -bq->elements[i];
114 /* end of block reached, reverse */
118 for (k = i - 1; j < k; j++, k--)
120 Id t = bq->elements[j];
121 bq->elements[j] = bq->elements[k];
130 /* distributive property: (a1*a2 + b1*b2) * (c1*c2 + d1*d2) =
131 a1*a2*c1*c2 + a1*a2*d1*d2 + b1*b2*c1*c2 + b1*b2*d1*d2 */
133 distribute_depblocks(Pool *pool, Queue *bq, int bqcnt, int bqcnt2, int flags)
137 printf("COMPLEX DISTRIBUTE %d %d %d\n", bqcnt, bqcnt2, bq->count);
139 bqcnt2 = expand_simpledeps(pool, bq, bqcnt, bqcnt2);
141 for (i = bqcnt; i < bqcnt2; i++)
143 for (j = bqcnt2; j < bqcnt3; j++)
146 int bqcnt4 = bq->count;
149 /* mix i block with j block, both blocks are sorted */
150 while (bq->elements[k] && bq->elements[j])
152 if (bq->elements[k] < bq->elements[j])
153 queue_push(bq, bq->elements[k++]);
156 if (bq->elements[k] == bq->elements[j])
158 queue_push(bq, bq->elements[j++]);
161 while (bq->elements[j])
162 queue_push(bq, bq->elements[j++]);
163 while (bq->elements[k])
164 queue_push(bq, bq->elements[k++]);
166 /* block is finished, check for A + -A */
167 for (a = bqcnt4, b = bq->count - 1; a < b; )
169 if (-bq->elements[a] == bq->elements[b])
171 if (-bq->elements[a] > bq->elements[b])
177 queue_truncate(bq, bqcnt4); /* ignore this block */
179 queue_push(bq, 0); /* finish block */
181 /* advance to next block */
182 while (bq->elements[i])
185 queue_deleten(bq, bqcnt, bqcnt3 - bqcnt);
186 if (bqcnt == bq->count)
187 return flags & CPLXDEPS_TODNF ? 0 : 1;
191 static int normalize_dep(Pool *pool, Id dep, Queue *bq, int flags);
194 normalize_dep_or(Pool *pool, Id dep1, Id dep2, Queue *bq, int flags, int invflags)
196 int r1, r2, bqcnt2, bqcnt = bq->count;
197 r1 = normalize_dep(pool, dep1, bq, flags);
199 return 1; /* early exit */
201 r2 = normalize_dep(pool, dep2, bq, flags ^ invflags);
203 r2 = invert_depblocks(pool, bq, bqcnt2, r2);
204 if (r1 == 1 || r2 == 1)
206 queue_truncate(bq, bqcnt);
213 if ((flags & CPLXDEPS_TODNF) == 0)
214 return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
219 normalize_dep_and(Pool *pool, Id dep1, Id dep2, Queue *bq, int flags, int invflags)
221 int r1, r2, bqcnt2, bqcnt = bq->count;
222 r1 = normalize_dep(pool, dep1, bq, flags);
224 return 0; /* early exit */
226 r2 = normalize_dep(pool, dep2, bq, flags ^ invflags);
228 r2 = invert_depblocks(pool, bq, bqcnt2, r2);
229 if (r1 == 0 || r2 == 0)
231 queue_truncate(bq, bqcnt);
238 if ((flags & CPLXDEPS_TODNF) != 0)
239 return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
244 normalize_dep_if_else(Pool *pool, Id dep1, Id dep2, Id dep3, Queue *bq, int flags)
246 /* A IF (B ELSE C) -> (A OR ~B) AND (C OR B) */
247 int r1, r2, bqcnt2, bqcnt = bq->count;
248 r1 = normalize_dep_or(pool, dep1, dep2, bq, flags, CPLXDEPS_TODNF);
250 return 0; /* early exit */
252 r2 = normalize_dep_or(pool, dep2, dep3, bq, flags, 0);
253 if (r1 == 0 || r2 == 0)
255 queue_truncate(bq, bqcnt);
262 if ((flags & CPLXDEPS_TODNF) != 0)
263 return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
268 normalize_dep_unless_else(Pool *pool, Id dep1, Id dep2, Id dep3, Queue *bq, int flags)
270 /* A UNLESS (B ELSE C) -> (A AND ~B) OR (C AND B) */
271 int r1, r2, bqcnt2, bqcnt = bq->count;
272 r1 = normalize_dep_and(pool, dep1, dep2, bq, flags, CPLXDEPS_TODNF);
274 return 1; /* early exit */
276 r2 = normalize_dep_and(pool, dep2, dep3, bq, flags, 0);
277 if (r1 == 1 || r2 == 1)
279 queue_truncate(bq, bqcnt);
286 if ((flags & CPLXDEPS_TODNF) == 0)
287 return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
295 * -1: at least one block
298 normalize_dep(Pool *pool, Id dep, Queue *bq, int flags)
303 if (pool_is_complex_dep(pool, dep))
305 Reldep *rd = GETRELDEP(pool, dep);
306 if (rd->flags == REL_COND)
311 Reldep *rd2 = GETRELDEP(pool, evr);
312 if (rd2->flags == REL_ELSE)
313 return normalize_dep_if_else(pool, rd->name, rd2->name, rd2->evr, bq, flags);
315 return normalize_dep_or(pool, rd->name, rd->evr, bq, flags, CPLXDEPS_TODNF);
317 if (rd->flags == REL_UNLESS)
322 Reldep *rd2 = GETRELDEP(pool, evr);
323 if (rd2->flags == REL_ELSE)
324 return normalize_dep_unless_else(pool, rd->name, rd2->name, rd2->evr, bq, flags);
326 return normalize_dep_and(pool, rd->name, rd->evr, bq, flags, CPLXDEPS_TODNF);
328 if (rd->flags == REL_OR)
329 return normalize_dep_or(pool, rd->name, rd->evr, bq, flags, 0);
330 if (rd->flags == REL_AND)
331 return normalize_dep_and(pool, rd->name, rd->evr, bq, flags, 0);
334 /* fallback case: just use package list */
335 dp = pool_whatprovides(pool, dep);
336 if (dp <= 2 || !pool->whatprovidesdata[dp])
337 return dp == 2 ? 1 : 0;
338 if (pool->whatprovidesdata[dp] == SYSTEMSOLVABLE)
341 if ((flags & CPLXDEPS_NAME) != 0)
343 while ((p = pool->whatprovidesdata[dp++]) != 0)
345 if (!pool_match_nevr(pool, pool->solvables + p, dep))
348 if ((flags & CPLXDEPS_TODNF) != 0)
352 else if ((flags & CPLXDEPS_TODNF) != 0)
354 while ((p = pool->whatprovidesdata[dp++]) != 0)
355 queue_push2(bq, p, 0);
358 queue_push2(bq, pool->nsolvables, dp); /* not yet expanded marker + offset */
359 if (bq->count == bqcnt)
360 return 0; /* no provider */
361 if (!(flags & CPLXDEPS_TODNF))
362 queue_push(bq, 0); /* finish block */
367 pool_normalize_complex_dep(Pool *pool, Id dep, Queue *bq, int flags)
369 int i, bqcnt = bq->count;
371 i = normalize_dep(pool, dep, bq, flags);
372 if ((flags & CPLXDEPS_EXPAND) != 0)
374 if (i != 0 && i != 1)
375 expand_simpledeps(pool, bq, bqcnt, 0);
377 if ((flags & CPLXDEPS_INVERT) != 0)
378 i = invert_depblocks(pool, bq, bqcnt, i);
385 print_depblocks(pool, bq, bqcnt);
391 pool_add_pos_literals_complex_dep(Pool *pool, Id dep, Queue *q, Map *m, int neg)
393 while (ISRELDEP(dep))
395 Reldep *rd = GETRELDEP(pool, dep);
396 if (rd->flags != REL_AND && rd->flags != REL_OR && rd->flags != REL_COND && rd->flags != REL_UNLESS)
398 pool_add_pos_literals_complex_dep(pool, rd->name, q, m, neg);
400 if (rd->flags == REL_COND || rd->flags == REL_UNLESS)
405 Reldep *rd2 = GETRELDEP(pool, rd->evr);
406 if (rd2->flags == REL_ELSE)
408 pool_add_pos_literals_complex_dep(pool, rd2->evr, q, m, !neg);
417 FOR_PROVIDES(p, pp, dep)
423 #endif /* ENABLE_COMPLEX_DEPS */