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) /* 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];
134 * -1: at least one block
137 normalize_dep(Pool *pool, Id dep, Queue *bq, int flags)
139 int bqcnt = bq->count;
141 int todnf = flags & CPLXDEPS_TODNF ? 1 : 0;
145 printf("normalize_dep %s todnf:%d\n", pool_dep2str(pool, dep), todnf);
147 if (pool_is_complex_dep(pool, dep))
149 Reldep *rd = GETRELDEP(pool, dep);
150 if (rd->flags == REL_AND || rd->flags == REL_OR || rd->flags == REL_COND)
152 int rdflags = rd->flags;
157 if (rdflags == REL_COND)
159 /* check for relly complex ELSE case */
162 Reldep *rd2 = GETRELDEP(pool, evr);
163 if (rd2->flags == REL_ELSE)
166 /* really complex case */
167 if ((flags & CPLXDEPS_ELSE_MASK) == CPLXDEPS_ELSE_AND_1)
173 else if ((flags & CPLXDEPS_ELSE_MASK) == CPLXDEPS_ELSE_AND_2)
180 else if ((flags & CPLXDEPS_ELSE_MASK) == CPLXDEPS_ELSE_OR_1)
186 else if ((flags & CPLXDEPS_ELSE_MASK) == CPLXDEPS_ELSE_OR_2)
192 else if ((flags & CPLXDEPS_ELSE_MASK) == CPLXDEPS_ELSE_OR_3)
201 /* we want AND: A IF (B ELSE C) -> (A OR ~B) AND (C OR B) */
202 r = normalize_dep(pool, dep, bq, flags | CPLXDEPS_ELSE_AND_1);
203 if (r == 0 && (flags & CPLXDEPS_DONTFIX) == 0)
205 r2 = normalize_dep(pool, dep, bq, flags | CPLXDEPS_ELSE_AND_2);
206 if (r2 == 0 && (flags & CPLXDEPS_DONTFIX) == 0)
208 queue_truncate(bq, bqcnt);
211 if (r == -1 || r2 == -1)
213 return r == 1 || r2 == 1 ? 1 : 0;
218 /* we want OR: A IF (B ELSE C) -> (A AND B) OR (A AND C) OR (~B AND C) */
219 r = normalize_dep(pool, dep, bq, flags | CPLXDEPS_ELSE_OR_1);
222 r2 = normalize_dep(pool, dep, bq, flags | CPLXDEPS_ELSE_OR_2);
225 queue_truncate(bq, bqcnt);
228 r3 = normalize_dep(pool, dep, bq, flags | CPLXDEPS_ELSE_OR_3);
231 queue_truncate(bq, bqcnt);
234 if (r == -1 || r2 == -1 || r3 == -1)
241 mode = rdflags == REL_AND || rdflags == REL_ELSE ? 0 : 1;
243 /* get blocks of first argument */
244 r = normalize_dep(pool, name, bq, flags);
247 if (rdflags == REL_ELSE)
249 if (rdflags == REL_AND && (flags & CPLXDEPS_DONTFIX) == 0)
251 if (rdflags == REL_COND)
253 r = normalize_dep(pool, evr, bq, (flags ^ CPLXDEPS_TODNF) & ~CPLXDEPS_DONTFIX);
254 return invert_depblocks(pool, bq, bqcnt, r); /* invert block for COND */
256 return normalize_dep(pool, evr, bq, flags);
260 if (rdflags == REL_ELSE)
262 r = normalize_dep(pool, evr, bq, (flags ^ CPLXDEPS_TODNF) & ~CPLXDEPS_DONTFIX);
263 return invert_depblocks(pool, bq, bqcnt, r); /* invert block for ELSE */
265 if (rdflags == REL_OR || rdflags == REL_COND)
267 return normalize_dep(pool, evr, bq, flags);
270 /* get blocks of second argument */
272 /* COND is OR with NEG on evr block, so we invert the todnf flag in that case */
273 r = normalize_dep(pool, evr, bq, rdflags == REL_COND || rdflags == REL_ELSE ? ((flags ^ CPLXDEPS_TODNF) & ~CPLXDEPS_DONTFIX) : flags);
274 if (rdflags == REL_COND || rdflags == REL_ELSE)
275 r = invert_depblocks(pool, bq, bqcnt2, r); /* invert 2nd block */
278 if (rdflags == REL_OR)
280 if (rdflags == REL_AND && (flags & CPLXDEPS_DONTFIX) != 0)
282 queue_truncate(bq, bqcnt);
287 if (rdflags == REL_COND || rdflags == REL_OR)
289 queue_truncate(bq, bqcnt);
296 /* simple case: just join em. nothing more to do here. */
298 printf("SIMPLE JOIN %d %d %d\n", bqcnt, bqcnt2, bq->count);
304 /* complex case: mix em */
307 printf("COMPLEX JOIN %d %d %d\n", bqcnt, bqcnt2, bq->count);
309 bqcnt2 = expand_simpledeps(pool, bq, bqcnt, bqcnt2);
311 for (i = bqcnt; i < bqcnt2; i++)
313 for (j = bqcnt2; j < bqcnt3; j++)
316 int bqcnt4 = bq->count;
319 /* mix i block with j block, both blocks are sorted */
320 while (bq->elements[k] && bq->elements[j])
322 if (bq->elements[k] < bq->elements[j])
323 queue_push(bq, bq->elements[k++]);
326 if (bq->elements[k] == bq->elements[j])
328 queue_push(bq, bq->elements[j++]);
331 while (bq->elements[j])
332 queue_push(bq, bq->elements[j++]);
333 while (bq->elements[k])
334 queue_push(bq, bq->elements[k++]);
336 /* block is finished, check for A + -A */
337 for (a = bqcnt4, b = bq->count - 1; a < b; )
339 if (-bq->elements[a] == bq->elements[b])
341 if (-bq->elements[a] > bq->elements[b])
347 queue_truncate(bq, bqcnt4); /* ignore this block */
349 queue_push(bq, 0); /* finish block */
351 /* advance to next block */
352 while (bq->elements[i])
356 if (bqcnt3 == bq->count) /* ignored all blocks? */
358 queue_deleten(bq, bqcnt, bqcnt3 - bqcnt);
364 /* fallback case: just use package list */
365 dp = pool_whatprovides(pool, dep);
366 if (dp <= 2 || !pool->whatprovidesdata[dp])
367 return dp == 2 ? 1 : 0;
368 if (pool->whatprovidesdata[dp] == SYSTEMSOLVABLE)
371 if ((flags & CPLXDEPS_NAME) != 0)
373 while ((p = pool->whatprovidesdata[dp++]) != 0)
375 if (!pool_match_nevr(pool, pool->solvables + p, dep))
384 while ((p = pool->whatprovidesdata[dp++]) != 0)
385 queue_push2(bq, p, 0);
388 queue_push2(bq, pool->nsolvables, dp); /* not yet expanded marker + offset */
389 if (bq->count == bqcnt)
390 return 0; /* no provider */
392 queue_push(bq, 0); /* finish block */
397 pool_normalize_complex_dep(Pool *pool, Id dep, Queue *bq, int flags)
399 int i, bqcnt = bq->count;
401 i = normalize_dep(pool, dep, bq, flags);
402 if ((flags & CPLXDEPS_EXPAND) != 0)
404 if (i != 0 && i != 1)
405 expand_simpledeps(pool, bq, bqcnt, 0);
407 if ((flags & CPLXDEPS_INVERT) != 0)
408 i = invert_depblocks(pool, bq, bqcnt, i);
415 print_depblocks(pool, bq, bqcnt);
421 pool_add_pos_literals_complex_dep(Pool *pool, Id dep, Queue *q, Map *m, int neg)
423 while (ISRELDEP(dep))
425 Reldep *rd = GETRELDEP(pool, dep);
426 if (rd->flags != REL_AND && rd->flags != REL_OR && rd->flags != REL_COND)
428 pool_add_pos_literals_complex_dep(pool, rd->name, q, m, neg);
430 if (rd->flags == REL_COND)
435 Reldep *rd2 = GETRELDEP(pool, rd->evr);
436 if (rd2->flags == REL_ELSE)
438 pool_add_pos_literals_complex_dep(pool, rd2->evr, q, m, !neg);
447 FOR_PROVIDES(p, pp, dep)
453 #endif /* ENABLE_COMPLEX_DEPS */