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 #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 void
 100 invert_depblocks(Pool *pool, Queue *bq, int start)
 101 {
 102   int i, j, end;
 103   expand_simpledeps(pool, bq, start, 0);
 104   end = bq->count;
 105   for (i = j = start; i < end; i++)
 106     {
 107       if (bq->elements[i])
 108         {
 109           bq->elements[i] = -bq->elements[i];
 110           continue;
 111         }
 112       /* end of block reached, reverse */
 113       if (i - 1 > j)
 114         {
 115           int k;
 116           for (k = i - 1; j < k; j++, k--)
 117             {
 118               Id t = bq->elements[j];
 119               bq->elements[j] = bq->elements[k];
 120               bq->elements[k] = t;
 121             }
 122         }
 123       j = i + 1;
 124     }
 125 }
 126
 127 /*
 128  * returns:
 129  *   0: no blocks
 130  *   1: matches all
 131  *  -1: at least one block
 132  */
 133 static int
 134 normalize_dep(Pool *pool, Id dep, Queue *bq, int flags)
 135 {
 136   int bqcnt = bq->count;
 137   int bqcnt2;
 138   int todnf = flags & CPLXDEPS_TODNF ? 1 : 0;
 139   Id p, dp;
 140
 141 #ifdef CPLXDEBUG
 142   printf("normalize_dep %s todnf:%d\n", pool_dep2str(pool, dep), todnf);
 143 #endif
 144   if (pool_is_complex_dep(pool, dep))
 145     {
 146       Reldep *rd = GETRELDEP(pool, dep);
 147       if (rd->flags == REL_AND || rd->flags == REL_OR || rd->flags == REL_COND)
 148         {
 149           int rdflags = rd->flags;
 150           int r, mode;
 151
 152           /* in inverted mode, COND means AND. otherwise it means OR NOT */
 153           if (rdflags == REL_COND && todnf)
 154             rdflags = REL_AND;
 155           mode = rdflags == REL_AND ? 0 : 1;
 156
 157           /* get blocks of first argument */
 158           r = normalize_dep(pool, rd->name, bq, flags);
 159           if (r == 0)
 160             {
 161               if (rdflags == REL_AND && (flags & CPLXDEPS_DONTFIX) == 0)
 162                 return 0;
 163               if (rdflags == REL_COND)
 164                 {
 165                   r = normalize_dep(pool, rd->evr, bq, (flags ^ CPLXDEPS_TODNF) & ~CPLXDEPS_DONTFIX);
 166                   if (r == 0 || r == 1)
 167                     return r == 0 ? 1 : 0;
 168                   invert_depblocks(pool, bq, bqcnt);    /* invert block for COND */
 169                   return r;
 170                 }
 171               return normalize_dep(pool, rd->evr, bq, flags);
 172             }
 173           if (r == 1)
 174             {
 175               if (rdflags != REL_AND)
 176                 return 1;
 177               return normalize_dep(pool, rd->evr, bq, flags);
 178             }
 179
 180           /* get blocks of second argument */
 181           bqcnt2 = bq->count;
 182           /* COND is OR with NEG on evr block, so we invert the todnf flag in that case */
 183           r = normalize_dep(pool, rd->evr, bq, rdflags == REL_COND ? ((flags ^ CPLXDEPS_TODNF) & ~CPLXDEPS_DONTFIX) : flags);
 184           if (r == 0)
 185             {
 186               if (rdflags == REL_OR)
 187                 return -1;
 188               if (rdflags == REL_AND && (flags & CPLXDEPS_DONTFIX) != 0)
 189                 return -1;
 190               queue_truncate(bq, bqcnt);
 191               return rdflags == REL_COND ? 1 : 0;
 192             }
 193           if (r == 1)
 194             {
 195               if (rdflags == REL_OR)
 196                 {
 197                   queue_truncate(bq, bqcnt);
 198                   return 1;
 199                 }
 200               return -1;
 201             }
 202           if (rdflags == REL_COND)
 203             invert_depblocks(pool, bq, bqcnt2); /* invert 2nd block */
 204           if (mode == todnf)
 205             {
 206               /* simple case: just join em. nothing more to do here. */
 207 #ifdef CPLXDEBUG
 208               printf("SIMPLE JOIN %d %d %d\n", bqcnt, bqcnt2, bq->count);
 209 #endif
 210               return -1;
 211             }
 212           else
 213             {
 214               /* complex case: mix em */
 215               int i, j, bqcnt3;
 216 #ifdef CPLXDEBUG
 217               printf("COMPLEX JOIN %d %d %d\n", bqcnt, bqcnt2, bq->count);
 218 #endif
 219               bqcnt2 = expand_simpledeps(pool, bq, bqcnt, bqcnt2);
 220               bqcnt3 = bq->count;
 221               for (i = bqcnt; i < bqcnt2; i++)
 222                 {
 223                   for (j = bqcnt2; j < bqcnt3; j++)
 224                     {
 225                       int a, b;
 226                       int bqcnt4 = bq->count;
 227                       int k = i;
 228
 229                       /* mix i block with j block, both blocks are sorted */
 230                       while (bq->elements[k] && bq->elements[j])
 231                         {
 232                           if (bq->elements[k] < bq->elements[j])
 233                             queue_push(bq, bq->elements[k++]);
 234                           else
 235                             {
 236                               if (bq->elements[k] == bq->elements[j])
 237                                 k++;
 238                               queue_push(bq, bq->elements[j++]);
 239                             }
 240                         }
 241                       while (bq->elements[j])
 242                         queue_push(bq, bq->elements[j++]);
 243                       while (bq->elements[k])
 244                         queue_push(bq, bq->elements[k++]);
 245
 246                       /* block is finished, check for A + -A */
 247                       for (a = bqcnt4, b = bq->count - 1; a < b; )
 248                         {
 249                           if (-bq->elements[a] == bq->elements[b])
 250                             break;
 251                           if (-bq->elements[a] > bq->elements[b])
 252                             a++;
 253                           else
 254                             b--;
 255                         }
 256                       if (a < b)
 257                         queue_truncate(bq, bqcnt4);     /* ignore this block */
 258                       else
 259                         queue_push(bq, 0);      /* finish block */
 260                     }
 261                   /* advance to next block */
 262                   while (bq->elements[i])
 263                     i++;
 264                 }
 265               i = -1;
 266               if (bqcnt3 == bq->count)  /* ignored all blocks? */
 267                 i = todnf ? 0 : 1;
 268               queue_deleten(bq, bqcnt, bqcnt3 - bqcnt);
 269               return i;
 270             }
 271         }
 272     }
 273
 274   /* fallback case: just use package list */
 275   dp = pool_whatprovides(pool, dep);
 276   if (dp <= 2 || !pool->whatprovidesdata[dp])
 277     return dp == 2 ? 1 : 0;
 278   if (pool->whatprovidesdata[dp] == SYSTEMSOLVABLE)
 279     return 1;
 280   bqcnt = bq->count;
 281   if ((flags & CPLXDEPS_NAME) != 0)
 282     {
 283       while ((p = pool->whatprovidesdata[dp++]) != 0)
 284         {
 285           if (!pool_match_nevr(pool, pool->solvables + p, dep))
 286             continue;
 287           queue_push(bq, p);
 288           if (todnf)
 289             queue_push(bq, 0);
 290         }
 291     }
 292   else if (todnf)
 293     {
 294       while ((p = pool->whatprovidesdata[dp++]) != 0)
 295         queue_push2(bq, p, 0);
 296     }
 297   else
 298     queue_push2(bq, pool->nsolvables, dp);      /* not yet expanded marker + offset */
 299   if (bq->count == bqcnt)
 300     return 0;   /* no provider */
 301   if (!todnf)
 302     queue_push(bq, 0);  /* finish block */
 303   return -1;
 304 }
 305
 306 int
 307 pool_normalize_complex_dep(Pool *pool, Id dep, Queue *bq, int flags)
 308 {
 309   int i, bqcnt = bq->count;
 310
 311   i = normalize_dep(pool, dep, bq, flags);
 312   if ((flags & CPLXDEPS_EXPAND) != 0)
 313     {
 314       if (i != 0 && i != 1)
 315         expand_simpledeps(pool, bq, bqcnt, 0);
 316     }
 317   if ((flags & CPLXDEPS_INVERT) != 0)
 318     {
 319       if (i == 0 || i == 1)
 320         i ^= 1;
 321       else
 322         invert_depblocks(pool, bq, bqcnt);
 323     }
 324 #ifdef CPLXDEBUG
 325   if (i == 0)
 326     printf("NONE\n");
 327   else if (i == 1)
 328     printf("ALL\n");
 329   else
 330     print_depblocks(pool, bq, bqcnt);
 331 #endif
 332   return i;
 333 }
 334
 335 #endif  /* ENABLE_COMPLEX_DEPS */
 336