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 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 /*
 131  * returns:
 132  *   0: no blocks
 133  *   1: matches all
 134  *  -1: at least one block
 135  */
 136 static int
 137 normalize_dep(Pool *pool, Id dep, Queue *bq, int flags)
 138 {
 139   int bqcnt = bq->count;
 140   int bqcnt2;
 141   int todnf = flags & CPLXDEPS_TODNF ? 1 : 0;
 142   Id p, dp;
 143
 144 #ifdef CPLXDEBUG
 145   printf("normalize_dep %s todnf:%d\n", pool_dep2str(pool, dep), todnf);
 146 #endif
 147   if (pool_is_complex_dep(pool, dep))
 148     {
 149       Reldep *rd = GETRELDEP(pool, dep);
 150       if (rd->flags == REL_AND || rd->flags == REL_OR || rd->flags == REL_COND)
 151         {
 152           int rdflags = rd->flags;
 153           Id name = rd->name;
 154           Id evr = rd->evr;
 155           int r, mode;
 156
 157           if (rdflags == REL_COND)
 158             {
 159               /* check for relly complex ELSE case */
 160               if (ISRELDEP(evr))
 161                 {
 162                   Reldep *rd2 = GETRELDEP(pool, evr);
 163                   if (rd2->flags == REL_ELSE)
 164                     {
 165                       int r2;
 166                       /* really complex case */
 167                       if ((flags & CPLXDEPS_ELSE_MASK) == CPLXDEPS_ELSE_AND_1)
 168                         {
 169                           /* A OR ~B */
 170                           rdflags = REL_COND;
 171                           evr = rd2->name;
 172                         }
 173                       else if ((flags & CPLXDEPS_ELSE_MASK) == CPLXDEPS_ELSE_AND_2)
 174                         {
 175                           /* C OR B */
 176                           rdflags = REL_OR;
 177                           name = rd2->evr;
 178                           evr = rd2->name;
 179                         }
 180                       else if ((flags & CPLXDEPS_ELSE_MASK) == CPLXDEPS_ELSE_OR_1)
 181                         {
 182                           /* A AND B */
 183                           rdflags = REL_AND;
 184                           evr = rd2->name;
 185                         }
 186                       else if ((flags & CPLXDEPS_ELSE_MASK) == CPLXDEPS_ELSE_OR_2)
 187                         {
 188                           /* A AND C */
 189                           rdflags = REL_AND;
 190                           evr = rd2->evr;
 191                         }
 192                       else if ((flags & CPLXDEPS_ELSE_MASK) == CPLXDEPS_ELSE_OR_3)
 193                         {
 194                           /* C AND ~B */
 195                           rdflags = REL_ELSE;
 196                           name = rd2->evr;
 197                           evr = rd2->name;
 198                         }
 199                       else if (!todnf)
 200                         {
 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)
 204                             return 0;
 205                           r2 = normalize_dep(pool, dep, bq, flags | CPLXDEPS_ELSE_AND_2);
 206                           if (r2 == 0 && (flags & CPLXDEPS_DONTFIX) == 0)
 207                             {
 208                               queue_truncate(bq, bqcnt);
 209                               return 0;
 210                             }
 211                           if (r == -1 || r2 == -1)
 212                             return -1;
 213                           return r == 1 || r2 == 1 ? 1 : 0;
 214                         }
 215                       else
 216                         {
 217                           int r2, r3;
 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);
 220                           if (r == 1)
 221                             return 1;
 222                           r2 = normalize_dep(pool, dep, bq, flags | CPLXDEPS_ELSE_OR_2);
 223                           if (r2 == 1)
 224                             {
 225                               queue_truncate(bq, bqcnt);
 226                               return 1;
 227                             }
 228                           r3 = normalize_dep(pool, dep, bq, flags | CPLXDEPS_ELSE_OR_3);
 229                           if (r3 == 1)
 230                             {
 231                               queue_truncate(bq, bqcnt);
 232                               return 1;
 233                             }
 234                           if (r == -1 || r2 == -1 || r3 == -1)
 235                             return -1;
 236                           return 0;
 237                         }
 238                     }
 239                 }
 240             }
 241           mode = rdflags == REL_AND || rdflags == REL_ELSE ? 0 : 1;
 242
 243           /* get blocks of first argument */
 244           r = normalize_dep(pool, name, bq, flags);
 245           if (r == 0)
 246             {
 247               if (rdflags == REL_ELSE)
 248                 return 0;
 249               if (rdflags == REL_AND && (flags & CPLXDEPS_DONTFIX) == 0)
 250                 return 0;
 251               if (rdflags == REL_COND)
 252                 {
 253                   r = normalize_dep(pool, evr, bq, (flags ^ CPLXDEPS_TODNF) & ~CPLXDEPS_DONTFIX);
 254                   return invert_depblocks(pool, bq, bqcnt, r);  /* invert block for COND */
 255                 }
 256               return normalize_dep(pool, evr, bq, flags);
 257             }
 258           if (r == 1)
 259             {
 260               if (rdflags == REL_ELSE)
 261                 {
 262                   r = normalize_dep(pool, evr, bq, (flags ^ CPLXDEPS_TODNF) & ~CPLXDEPS_DONTFIX);
 263                   return invert_depblocks(pool, bq, bqcnt, r);  /* invert block for ELSE */
 264                 }
 265               if (rdflags == REL_OR || rdflags == REL_COND)
 266                 return 1;
 267               return normalize_dep(pool, evr, bq, flags);
 268             }
 269
 270           /* get blocks of second argument */
 271           bqcnt2 = bq->count;
 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 */
 276           if (r == 0)
 277             {
 278               if (rdflags == REL_OR)
 279                 return -1;
 280               if (rdflags == REL_AND && (flags & CPLXDEPS_DONTFIX) != 0)
 281                 return -1;
 282               queue_truncate(bq, bqcnt);
 283               return 0;
 284             }
 285           if (r == 1)
 286             {
 287               if (rdflags == REL_COND || rdflags == REL_OR)
 288                 {
 289                   queue_truncate(bq, bqcnt);
 290                   return 1;
 291                 }
 292               return -1;
 293             }
 294           if (mode == todnf)
 295             {
 296               /* simple case: just join em. nothing more to do here. */
 297 #ifdef CPLXDEBUG
 298               printf("SIMPLE JOIN %d %d %d\n", bqcnt, bqcnt2, bq->count);
 299 #endif
 300               return -1;
 301             }
 302           else
 303             {
 304               /* complex case: mix em */
 305               int i, j, bqcnt3;
 306 #ifdef CPLXDEBUG
 307               printf("COMPLEX JOIN %d %d %d\n", bqcnt, bqcnt2, bq->count);
 308 #endif
 309               bqcnt2 = expand_simpledeps(pool, bq, bqcnt, bqcnt2);
 310               bqcnt3 = bq->count;
 311               for (i = bqcnt; i < bqcnt2; i++)
 312                 {
 313                   for (j = bqcnt2; j < bqcnt3; j++)
 314                     {
 315                       int a, b;
 316                       int bqcnt4 = bq->count;
 317                       int k = i;
 318
 319                       /* mix i block with j block, both blocks are sorted */
 320                       while (bq->elements[k] && bq->elements[j])
 321                         {
 322                           if (bq->elements[k] < bq->elements[j])
 323                             queue_push(bq, bq->elements[k++]);
 324                           else
 325                             {
 326                               if (bq->elements[k] == bq->elements[j])
 327                                 k++;
 328                               queue_push(bq, bq->elements[j++]);
 329                             }
 330                         }
 331                       while (bq->elements[j])
 332                         queue_push(bq, bq->elements[j++]);
 333                       while (bq->elements[k])
 334                         queue_push(bq, bq->elements[k++]);
 335
 336                       /* block is finished, check for A + -A */
 337                       for (a = bqcnt4, b = bq->count - 1; a < b; )
 338                         {
 339                           if (-bq->elements[a] == bq->elements[b])
 340                             break;
 341                           if (-bq->elements[a] > bq->elements[b])
 342                             a++;
 343                           else
 344                             b--;
 345                         }
 346                       if (a < b)
 347                         queue_truncate(bq, bqcnt4);     /* ignore this block */
 348                       else
 349                         queue_push(bq, 0);      /* finish block */
 350                     }
 351                   /* advance to next block */
 352                   while (bq->elements[i])
 353                     i++;
 354                 }
 355               i = -1;
 356               if (bqcnt3 == bq->count)  /* ignored all blocks? */
 357                 i = todnf ? 0 : 1;
 358               queue_deleten(bq, bqcnt, bqcnt3 - bqcnt);
 359               return i;
 360             }
 361         }
 362     }
 363
 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)
 369     return 1;
 370   bqcnt = bq->count;
 371   if ((flags & CPLXDEPS_NAME) != 0)
 372     {
 373       while ((p = pool->whatprovidesdata[dp++]) != 0)
 374         {
 375           if (!pool_match_nevr(pool, pool->solvables + p, dep))
 376             continue;
 377           queue_push(bq, p);
 378           if (todnf)
 379             queue_push(bq, 0);
 380         }
 381     }
 382   else if (todnf)
 383     {
 384       while ((p = pool->whatprovidesdata[dp++]) != 0)
 385         queue_push2(bq, p, 0);
 386     }
 387   else
 388     queue_push2(bq, pool->nsolvables, dp);      /* not yet expanded marker + offset */
 389   if (bq->count == bqcnt)
 390     return 0;   /* no provider */
 391   if (!todnf)
 392     queue_push(bq, 0);  /* finish block */
 393   return -1;
 394 }
 395
 396 int
 397 pool_normalize_complex_dep(Pool *pool, Id dep, Queue *bq, int flags)
 398 {
 399   int i, bqcnt = bq->count;
 400
 401   i = normalize_dep(pool, dep, bq, flags);
 402   if ((flags & CPLXDEPS_EXPAND) != 0)
 403     {
 404       if (i != 0 && i != 1)
 405         expand_simpledeps(pool, bq, bqcnt, 0);
 406     }
 407   if ((flags & CPLXDEPS_INVERT) != 0)
 408     i = invert_depblocks(pool, bq, bqcnt, i);
 409 #ifdef CPLXDEBUG
 410   if (i == 0)
 411     printf("NONE\n");
 412   else if (i == 1)
 413     printf("ALL\n");
 414   else
 415     print_depblocks(pool, bq, bqcnt);
 416 #endif
 417   return i;
 418 }
 419
 420 void
 421 pool_add_pos_literals_complex_dep(Pool *pool, Id dep, Queue *q, Map *m, int neg)
 422 {
 423   while (ISRELDEP(dep))
 424     {
 425       Reldep *rd = GETRELDEP(pool, dep);
 426       if (rd->flags != REL_AND && rd->flags != REL_OR && rd->flags != REL_COND)
 427         break;
 428       pool_add_pos_literals_complex_dep(pool, rd->name, q, m, neg);
 429       dep = rd->evr;
 430       if (rd->flags == REL_COND)
 431         {
 432           neg = !neg;
 433           if (ISRELDEP(dep))
 434             {
 435               Reldep *rd2 = GETRELDEP(pool, rd->evr);
 436               if (rd2->flags == REL_ELSE)
 437                 {
 438                   pool_add_pos_literals_complex_dep(pool, rd2->evr, q, m, !neg);
 439                   dep = rd2->name;
 440                 }
 441             }
 442         }
 443     }
 444   if (!neg)
 445     {
 446       Id p, pp;
 447       FOR_PROVIDES(p, pp, dep)
 448         if (!MAPTST(m, p))
 449           queue_push(q, p);
 450     }
 451 }
 452
 453 #endif  /* ENABLE_COMPLEX_DEPS */
 454