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 || rd->flags == REL_UNLESS)     /* 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 #ifdef CPLXDEBUG
  72 static void
  73 print_depblocks(Pool *pool, Queue *bq, int start)
  74 {
  75   int i;
  76
  77   for (i = start; i < bq->count; i++)
  78     {
  79       if (bq->elements[i] == pool->nsolvables)
  80         {
  81           Id *dp = pool->whatprovidesdata + bq->elements[++i];
  82           printf(" (");
  83           while (*dp)
  84             printf(" %s", pool_solvid2str(pool, *dp++));
  85           printf(" )");
  86         }
  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]));
  91       else
  92         printf(" ||");
  93     }
  94   printf("\n");
  95 }
  96 #endif
  97
  98 /* invert all literals in the blocks. note that this also turns DNF into CNF and vice versa */
  99 static int
 100 invert_depblocks(Pool *pool, Queue *bq, int start, int r)
 101 {
 102   int i, j, end;
 103   if (r == 0 || r == 1)
 104     return r ? 0 : 1;
 105   expand_simpledeps(pool, bq, start, 0);
 106   end = bq->count;
 107   for (i = j = start; i < end; i++)
 108     {
 109       if (bq->elements[i])
 110         {
 111           bq->elements[i] = -bq->elements[i];
 112           continue;
 113         }
 114       /* end of block reached, reverse */
 115       if (i - 1 > j)
 116         {
 117           int k;
 118           for (k = i - 1; j < k; j++, k--)
 119             {
 120               Id t = bq->elements[j];
 121               bq->elements[j] = bq->elements[k];
 122               bq->elements[k] = t;
 123             }
 124         }
 125       j = i + 1;
 126     }
 127   return -1;
 128 }
 129
 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 */
 132 static int
 133 distribute_depblocks(Pool *pool, Queue *bq, int bqcnt, int bqcnt2, int flags)
 134 {
 135   int i, j, bqcnt3;
 136 #ifdef CPLXDEBUG
 137   printf("COMPLEX DISTRIBUTE %d %d %d\n", bqcnt, bqcnt2, bq->count);
 138 #endif
 139   bqcnt2 = expand_simpledeps(pool, bq, bqcnt, bqcnt2);
 140   bqcnt3 = bq->count;
 141   for (i = bqcnt; i < bqcnt2; i++)
 142     {
 143       for (j = bqcnt2; j < bqcnt3; j++)
 144         {
 145           int a, b;
 146           int bqcnt4 = bq->count;
 147           int k = i;
 148
 149           /* mix i block with j block, both blocks are sorted */
 150           while (bq->elements[k] && bq->elements[j])
 151             {
 152               if (bq->elements[k] < bq->elements[j])
 153                 queue_push(bq, bq->elements[k++]);
 154               else
 155                 {
 156                   if (bq->elements[k] == bq->elements[j])
 157                     k++;
 158                   queue_push(bq, bq->elements[j++]);
 159                 }
 160             }
 161           while (bq->elements[j])
 162             queue_push(bq, bq->elements[j++]);
 163           while (bq->elements[k])
 164             queue_push(bq, bq->elements[k++]);
 165
 166           /* block is finished, check for A + -A */
 167           for (a = bqcnt4, b = bq->count - 1; a < b; )
 168             {
 169               if (-bq->elements[a] == bq->elements[b])
 170                 break;
 171               if (-bq->elements[a] > bq->elements[b])
 172                 a++;
 173               else
 174                 b--;
 175             }
 176           if (a < b)
 177             queue_truncate(bq, bqcnt4); /* ignore this block */
 178           else
 179             queue_push(bq, 0);  /* finish block */
 180         }
 181       /* advance to next block */
 182       while (bq->elements[i])
 183         i++;
 184     }
 185   queue_deleten(bq, bqcnt, bqcnt3 - bqcnt);
 186   if (bqcnt == bq->count)
 187     return flags & CPLXDEPS_TODNF ? 0 : 1;
 188   return -1;
 189 }
 190
 191 static int normalize_dep(Pool *pool, Id dep, Queue *bq, int flags);
 192
 193 static int
 194 normalize_dep_or(Pool *pool, Id dep1, Id dep2, Queue *bq, int flags, int invflags)
 195 {
 196   int r1, r2, bqcnt2, bqcnt = bq->count;
 197   r1 = normalize_dep(pool, dep1, bq, flags);
 198   if (r1 == 1)
 199     return 1;           /* early exit */
 200   bqcnt2 = bq->count;
 201   r2 = normalize_dep(pool, dep2, bq, flags ^ invflags);
 202   if (invflags)
 203     r2 = invert_depblocks(pool, bq, bqcnt2, r2);
 204   if (r1 == 1 || r2 == 1)
 205     {
 206       queue_truncate(bq, bqcnt);
 207       return 1;
 208     }
 209   if (r1 == 0)
 210     return r2;
 211   if (r2 == 0)
 212     return r1;
 213   if ((flags & CPLXDEPS_TODNF) == 0)
 214     return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
 215   return -1;
 216 }
 217
 218 static int
 219 normalize_dep_and(Pool *pool, Id dep1, Id dep2, Queue *bq, int flags, int invflags)
 220 {
 221   int r1, r2, bqcnt2, bqcnt = bq->count;
 222   r1 = normalize_dep(pool, dep1, bq, flags);
 223   if (r1 == 0)
 224     return 0;           /* early exit */
 225   bqcnt2 = bq->count;
 226   r2 = normalize_dep(pool, dep2, bq, flags ^ invflags);
 227   if (invflags)
 228     r2 = invert_depblocks(pool, bq, bqcnt2, r2);
 229   if (r1 == 0 || r2 == 0)
 230     {
 231       queue_truncate(bq, bqcnt);
 232       return 0;
 233     }
 234   if (r1 == 1)
 235     return r2;
 236   if (r2 == 1)
 237     return r1;
 238   if ((flags & CPLXDEPS_TODNF) != 0)
 239     return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
 240   return -1;
 241 }
 242
 243 static int
 244 normalize_dep_if_else(Pool *pool, Id dep1, Id dep2, Id dep3, Queue *bq, int flags)
 245 {
 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);
 249   if (r1 == 0)
 250     return 0;           /* early exit */
 251   bqcnt2 = bq->count;
 252   r2 = normalize_dep_or(pool, dep2, dep3, bq, flags, 0);
 253   if (r1 == 0 || r2 == 0)
 254     {
 255       queue_truncate(bq, bqcnt);
 256       return 0;
 257     }
 258   if (r1 == 1)
 259     return r2;
 260   if (r2 == 1)
 261     return r1;
 262   if ((flags & CPLXDEPS_TODNF) != 0)
 263     return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
 264   return -1;
 265 }
 266
 267 static int
 268 normalize_dep_unless_else(Pool *pool, Id dep1, Id dep2, Id dep3, Queue *bq, int flags)
 269 {
 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);
 273   if (r1 == 1)
 274     return 1;           /* early exit */
 275   bqcnt2 = bq->count;
 276   r2 = normalize_dep_and(pool, dep2, dep3, bq, flags, 0);
 277   if (r1 == 1 || r2 == 1)
 278     {
 279       queue_truncate(bq, bqcnt);
 280       return 1;
 281     }
 282   if (r1 == 0)
 283     return r2;
 284   if (r2 == 0)
 285     return r1;
 286   if ((flags & CPLXDEPS_TODNF) == 0)
 287     return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
 288   return -1;
 289 }
 290
 291 /*
 292  * returns:
 293  *   0: no blocks
 294  *   1: matches all
 295  *  -1: at least one block
 296  */
 297 static int
 298 normalize_dep(Pool *pool, Id dep, Queue *bq, int flags)
 299 {
 300   Id p, dp;
 301   int bqcnt;
 302
 303   if (pool_is_complex_dep(pool, dep))
 304     {
 305       Reldep *rd = GETRELDEP(pool, dep);
 306       if (rd->flags == REL_COND)
 307         {
 308           Id evr = rd->evr;
 309           if (ISRELDEP(evr))
 310             {
 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);
 314             }
 315           return normalize_dep_or(pool, rd->name, rd->evr, bq, flags, CPLXDEPS_TODNF);
 316         }
 317       if (rd->flags == REL_UNLESS)
 318         {
 319           Id evr = rd->evr;
 320           if (ISRELDEP(evr))
 321             {
 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);
 325             }
 326           return normalize_dep_and(pool, rd->name, rd->evr, bq, flags, CPLXDEPS_TODNF);
 327         }
 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);
 332     }
 333
 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)
 339     return 1;
 340   bqcnt = bq->count;
 341   if ((flags & CPLXDEPS_NAME) != 0)
 342     {
 343       while ((p = pool->whatprovidesdata[dp++]) != 0)
 344         {
 345           if (!pool_match_nevr(pool, pool->solvables + p, dep))
 346             continue;
 347           queue_push(bq, p);
 348           if ((flags & CPLXDEPS_TODNF) != 0)
 349             queue_push(bq, 0);
 350         }
 351     }
 352   else if ((flags & CPLXDEPS_TODNF) != 0)
 353     {
 354       while ((p = pool->whatprovidesdata[dp++]) != 0)
 355         queue_push2(bq, p, 0);
 356     }
 357   else
 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 */
 363   return -1;
 364 }
 365
 366 int
 367 pool_normalize_complex_dep(Pool *pool, Id dep, Queue *bq, int flags)
 368 {
 369   int i, bqcnt = bq->count;
 370
 371   i = normalize_dep(pool, dep, bq, flags);
 372   if ((flags & CPLXDEPS_EXPAND) != 0)
 373     {
 374       if (i != 0 && i != 1)
 375         expand_simpledeps(pool, bq, bqcnt, 0);
 376     }
 377   if ((flags & CPLXDEPS_INVERT) != 0)
 378     i = invert_depblocks(pool, bq, bqcnt, i);
 379 #ifdef CPLXDEBUG
 380   if (i == 0)
 381     printf("NONE\n");
 382   else if (i == 1)
 383     printf("ALL\n");
 384   else
 385     print_depblocks(pool, bq, bqcnt);
 386 #endif
 387   return i;
 388 }
 389
 390 void
 391 pool_add_pos_literals_complex_dep(Pool *pool, Id dep, Queue *q, Map *m, int neg)
 392 {
 393   while (ISRELDEP(dep))
 394     {
 395       Reldep *rd = GETRELDEP(pool, dep);
 396       if (rd->flags != REL_AND && rd->flags != REL_OR && rd->flags != REL_COND && rd->flags != REL_UNLESS)
 397         break;
 398       pool_add_pos_literals_complex_dep(pool, rd->name, q, m, neg);
 399       dep = rd->evr;
 400       if (rd->flags == REL_COND || rd->flags == REL_UNLESS)
 401         {
 402           neg = !neg;
 403           if (ISRELDEP(dep))
 404             {
 405               Reldep *rd2 = GETRELDEP(pool, rd->evr);
 406               if (rd2->flags == REL_ELSE)
 407                 {
 408                   pool_add_pos_literals_complex_dep(pool, rd2->evr, q, m, !neg);
 409                   dep = rd2->name;
 410                 }
 411             }
 412         }
 413     }
 414   if (!neg)
 415     {
 416       Id p, pp;
 417       FOR_PROVIDES(p, pp, dep)
 418         if (!MAPTST(m, p))
 419           queue_push(q, p);
 420     }
 421 }
 422
 423 #endif  /* ENABLE_COMPLEX_DEPS */
 424