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