add support for complex dependencies
[platform/upstream/libsolv.git] / src / cplxdeps.c
1 /*
2  * Copyright (c) 2014, Novell Inc.
3  *
4  * This program is licensed under the BSD license, read LICENSE.BSD
5  * for further information
6  */
7
8 /*
9  * cplxdeps.c
10  *
11  * normalize complex dependencies into CNF/DNF form
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 "pool.h"
21 #include "cplxdeps.h"
22
23 #ifdef ENABLE_COMPLEX_DEPS
24
25 #undef CPLXDEBUG
26
27 int
28 pool_is_complex_dep_rd(Pool *pool, Reldep *rd)
29 {
30   for (;;)
31     {
32       if (rd->flags == REL_AND || rd->flags == REL_COND)        /* those two are the complex ones */
33         return 1;
34       if (rd->flags != REL_OR)
35         return 0;
36       if (ISRELDEP(rd->name) && pool_is_complex_dep_rd(pool, GETRELDEP(pool, rd->name)))
37         return 1;
38       if (!ISRELDEP(rd->evr))
39         return 0;
40       rd = GETRELDEP(pool, rd->evr);
41     }
42 }
43
44 /* expand simple dependencies into package lists */
45 static int
46 expand_simpledeps(Pool *pool, Queue *bq, int start, int split)
47 {
48   int end = bq->count;
49   int i, x;
50   int newsplit = 0;
51   for (i = start; i < end; i++)
52     {
53       if (i == split)
54         newsplit = bq->count - (end - start);
55       x = bq->elements[i];
56       if (x == pool->nsolvables)
57         {
58           Id *dp = pool->whatprovidesdata + bq->elements[++i];
59           for (; *dp; dp++)
60             queue_push(bq, *dp);
61         }
62       else
63         queue_push(bq, x);
64     }
65   if (i == split)
66     newsplit = bq->count - (end - start);
67   queue_deleten(bq, start, end - start);
68   return newsplit;
69 }
70
71 /* invert all literals in the blocks. note that this also turns DNF into CNF and vice versa */
72 static void
73 invert_depblocks(Pool *pool, Queue *bq, int start)
74 {
75   int i, j, end;
76   expand_simpledeps(pool, bq, start, 0);
77   end = bq->count;
78   for (i = j = start; i < end; i++)
79     {
80       if (bq->elements[i])
81         {
82           bq->elements[i] = -bq->elements[i];
83           continue;
84         }
85       /* end of block reached, reorder */
86       if (i - 1 > j)
87         {
88           int k;
89           for (k = i - 1; j < k; j++, k--)
90             {
91               Id t = bq->elements[j];
92               bq->elements[j] = bq->elements[k];
93               bq->elements[k] = t;
94             }
95         }
96       j = i + 1;
97     }
98 }
99
100 /*
101  * returns:
102  *   0: no blocks
103  *   1: matches all
104  *  -1: at least one block
105  */
106 static int
107 normalize_dep(Pool *pool, Id dep, Queue *bq, int todnf)
108 {
109   int bqcnt = bq->count;
110   int bqcnt2;
111   Id dp;
112
113 #ifdef CPLXDEBUG
114   printf("normalize_dep %s todnf:%d\n", pool_dep2str(pool, dep), todnf);
115 #endif
116   if (pool_is_complex_dep(pool, dep))
117     {
118       Reldep *rd = GETRELDEP(pool, dep);
119       if (rd->flags == REL_AND || rd->flags == REL_OR || rd->flags == REL_COND)
120         {
121           int flags = rd->flags;
122           int r, mode;
123           
124           /* in inverted mode, COND means AND. otherwise it means OR NOT */
125           if (flags == REL_COND && todnf)
126             flags = REL_AND;
127           mode = flags == REL_AND ? 0 : 1;
128
129           /* get blocks of first argument */
130           r = normalize_dep(pool, rd->name, bq, todnf);
131           if (r == 0)
132             {
133               if (flags == REL_AND)
134                 return 0;
135               if (flags == REL_COND)
136                 {
137                   r = normalize_dep(pool, rd->evr, bq, todnf ^ 1);
138                   if (r == 0 || r == 1)
139                     return r == 0 ? 1 : 0;
140                   invert_depblocks(pool, bq, bqcnt);    /* invert block for COND */
141                   return r;
142                 }
143               return normalize_dep(pool, rd->evr, bq, todnf);
144             }
145           if (r == 1)
146             {
147               if (flags != REL_AND)
148                 return 1;
149               return normalize_dep(pool, rd->evr, bq, todnf);
150             }
151
152           /* get blocks of second argument */
153           bqcnt2 = bq->count;
154           /* COND is OR with NEG on evr block, so we invert the todnf flag in that case*/
155           r = normalize_dep(pool, rd->evr, bq, flags == REL_COND ? todnf ^ 1 : todnf);
156           if (r == 0)
157             {
158               if (flags == REL_OR)
159                 return -1;
160               queue_truncate(bq, bqcnt);
161               return flags == REL_COND ? 1 : 0;
162             }
163           if (r == 1)
164             {
165               if (flags == REL_OR)
166                 {
167                   queue_truncate(bq, bqcnt);
168                   return 1;
169                 }
170               return -1;
171             }
172           if (flags == REL_COND)
173             invert_depblocks(pool, bq, bqcnt2); /* invert 2nd block */
174           if (mode == todnf)
175             {
176               /* simple case: just join em. nothing more to do here. */
177 #ifdef CPLXDEBUG
178               printf("SIMPLE JOIN %d %d %d\n", bqcnt, bqcnt2, bq->count);
179 #endif
180               return -1;
181             }
182           else
183             {
184               /* complex case: mix em */
185               int i, j, bqcnt3;
186 #ifdef CPLXDEBUG
187               printf("COMPLEX JOIN %d %d %d\n", bqcnt, bqcnt2, bq->count);
188 #endif
189               bqcnt2 = expand_simpledeps(pool, bq, bqcnt, bqcnt2);
190               bqcnt3 = bq->count;
191               for (i = bqcnt; i < bqcnt2; i++)
192                 {
193                   for (j = bqcnt2; j < bqcnt3; j++)
194                     {
195                       int a, b;
196                       int bqcnt4 = bq->count;
197                       int k = i;
198
199                       /* mix i block with j block, both blocks are sorted */
200                       while (bq->elements[k] && bq->elements[j])
201                         {
202                           if (bq->elements[k] < bq->elements[j])
203                             queue_push(bq, bq->elements[k++]);
204                           else
205                             {
206                               if (bq->elements[k] == bq->elements[j])
207                                 k++;
208                               queue_push(bq, bq->elements[j++]);
209                             }
210                         }
211                       while (bq->elements[j])
212                         queue_push(bq, bq->elements[j++]);
213                       while (bq->elements[k])
214                         queue_push(bq, bq->elements[k++]);
215
216                       /* block is finished, check for A + -A */
217                       for (a = bqcnt4, b = bq->count - 1; a < b; )
218                         {
219                           if (-bq->elements[a] == bq->elements[b])
220                             break;
221                           if (-bq->elements[a] > bq->elements[b])
222                             a++;
223                           else
224                             b--;
225                         }
226                       if (a < b)
227                         queue_truncate(bq, bqcnt4);     /* ignore this block */
228                       else
229                         queue_push(bq, 0);      /* finish block */
230                     }
231                   /* advance to next block */
232                   while (bq->elements[i])
233                     i++;
234                 }
235               i = -1;
236               if (bqcnt3 == bq->count)  /* ignored all blocks? */
237                 i = todnf ? 0 : 1;
238               queue_deleten(bq, bqcnt, bqcnt3 - bqcnt);
239               return i;
240             }
241         }
242     }
243
244   /* fallback case: just use package list */
245   dp = pool_whatprovides(pool, dep);
246   if (dp <= 2 || !pool->whatprovidesdata[dp])
247     return dp == 2 ? 1 : 0;
248   if (todnf)
249     {
250       for (; pool->whatprovidesdata[dp]; dp++)
251         queue_push2(bq, pool->whatprovidesdata[dp], 0);
252     }
253   else
254     {
255       queue_push2(bq, pool->nsolvables, dp);    /* not yet expanded marker */
256       queue_push(bq, 0);
257     }
258   return -1;
259 }
260
261 int
262 pool_normalize_complex_dep(Pool *pool, Id dep, Queue *bq, int flags)
263 {
264   int i, bqcnt = bq->count;
265
266   i = normalize_dep(pool, dep, bq, (flags & CPLXDEPS_TODNF) ? 1 : 0);
267   if ((flags & CPLXDEPS_EXPAND) != 0)
268     {
269       if (i != 0 && i != 1)
270         expand_simpledeps(pool, bq, bqcnt, 0);
271     }
272   if ((flags & CPLXDEPS_INVERT) != 0)
273     {
274       if (i == 0 || i == 1)
275         i ^= 1;
276       else
277         invert_depblocks(pool, bq, bqcnt);
278     }
279 #ifdef CPLXDEBUG
280   if (i == 0)
281     printf("NONE\n");
282   else if (i == 1)
283     printf("ALL\n");
284   else
285     {
286       for (i = bqcnt; i < bq->count; i++)
287         {
288           if (bq->elements[i] == pool->nsolvables)
289             {
290               Id *dp = pool->whatprovidesdata + bq->elements[++i];
291               printf(" (");
292               while (*dp)
293                 printf(" %s", pool_solvid2str(pool, *dp++));
294               printf(" )");
295             }
296           else if (bq->elements[i] > 0)
297             printf(" %s", pool_solvid2str(pool, bq->elements[i]));
298           else if (bq->elements[i] < 0)
299             printf(" -%s", pool_solvid2str(pool, -bq->elements[i]));
300           else
301             printf(" ||");
302         }
303       printf("\n");
304       i = -1;
305     }
306 #endif
307   return i;
308 }
309
310 #endif  /* ENABLE_COMPLEX_DEPS */
311