path: root/src/cplxdeps.c

/*
 * Copyright (c) 2014, Novell Inc.
 *
 * This program is licensed under the BSD license, read LICENSE.BSD
 * for further information
 */

/*
 * cplxdeps.c
 *
 * normalize complex dependencies into CNF/DNF form
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>

#include "pool.h"
#include "cplxdeps.h"

#ifdef ENABLE_COMPLEX_DEPS

#undef CPLXDEBUG

int
pool_is_complex_dep_rd(Pool *pool, Reldep *rd)
{
  for (;;)
    {
      if (rd->flags == REL_AND || rd->flags == REL_COND || rd->flags == REL_UNLESS)	/* those two are the complex ones */
	return 1;
      if (rd->flags != REL_OR)
	return 0;
      if (ISRELDEP(rd->name) && pool_is_complex_dep_rd(pool, GETRELDEP(pool, rd->name)))
	return 1;
      if (!ISRELDEP(rd->evr))
	return 0;
      rd = GETRELDEP(pool, rd->evr);
    }
}

/* expand simple dependencies into package lists */
static int
expand_simpledeps(Pool *pool, Queue *bq, int start, int split)
{
  int end = bq->count;
  int i, x;
  int newsplit = 0;
  for (i = start; i < end; i++)
    {
      if (i == split)
	newsplit = bq->count - (end - start);
      x = bq->elements[i];
      if (x == pool->nsolvables)
	{
	  Id *dp = pool->whatprovidesdata + bq->elements[++i];
	  for (; *dp; dp++)
	    queue_push(bq, *dp);
	}
      else
	queue_push(bq, x);
    }
  if (i == split)
    newsplit = bq->count - (end - start);
  queue_deleten(bq, start, end - start);
  return newsplit;
}

#ifdef CPLXDEBUG
static void
print_depblocks(Pool *pool, Queue *bq, int start)
{
  int i;

  for (i = start; i < bq->count; i++)
    {
      if (bq->elements[i] == pool->nsolvables)
	{
	  Id *dp = pool->whatprovidesdata + bq->elements[++i];
	  printf(" (");
	  while (*dp)
	    printf(" %s", pool_solvid2str(pool, *dp++));
	  printf(" )");
	}
      else if (bq->elements[i] > 0)
	printf(" %s", pool_solvid2str(pool, bq->elements[i]));
      else if (bq->elements[i] < 0)
	printf(" -%s", pool_solvid2str(pool, -bq->elements[i]));
      else
	printf(" ||");
    }
  printf("\n");
}
#endif

/* invert all literals in the blocks. note that this also turns DNF into CNF and vice versa */
static int
invert_depblocks(Pool *pool, Queue *bq, int start, int r)
{
  int i, j, end;
  if (r == 0 || r == 1)
    return r ? 0 : 1;
  expand_simpledeps(pool, bq, start, 0);
  end = bq->count;
  for (i = j = start; i < end; i++)
    {
      if (bq->elements[i])
	{
          bq->elements[i] = -bq->elements[i];
	  continue;
	}
      /* end of block reached, reverse */
      if (i - 1 > j)
	{
	  int k;
	  for (k = i - 1; j < k; j++, k--)
	    {
	      Id t = bq->elements[j];
	      bq->elements[j] = bq->elements[k];
	      bq->elements[k] = t;
	    }
	}
      j = i + 1;
    }
  return -1;
}

/* distributive property: (a1*a2 + b1*b2) * (c1*c2 + d1*d2) = 
   a1*a2*c1*c2 + a1*a2*d1*d2 + b1*b2*c1*c2 + b1*b2*d1*d2 */
static int
distribute_depblocks(Pool *pool, Queue *bq, int bqcnt, int bqcnt2, int flags)
{
  int i, j, bqcnt3;
#ifdef CPLXDEBUG
  printf("COMPLEX DISTRIBUTE %d %d %d\n", bqcnt, bqcnt2, bq->count);
#endif
  bqcnt2 = expand_simpledeps(pool, bq, bqcnt, bqcnt2);
  bqcnt3 = bq->count;
  for (i = bqcnt; i < bqcnt2; i++)
    {
      for (j = bqcnt2; j < bqcnt3; j++)
	{
	  int a, b;
	  int bqcnt4 = bq->count;
	  int k = i;

	  /* mix i block with j block, both blocks are sorted */
	  while (bq->elements[k] && bq->elements[j])
	    {
	      if (bq->elements[k] < bq->elements[j])
		queue_push(bq, bq->elements[k++]);
	      else
		{
		  if (bq->elements[k] == bq->elements[j])
		    k++;
		  queue_push(bq, bq->elements[j++]);
		}
	    }
	  while (bq->elements[j])
	    queue_push(bq, bq->elements[j++]);
	  while (bq->elements[k])
	    queue_push(bq, bq->elements[k++]);

	  /* block is finished, check for A + -A */
	  for (a = bqcnt4, b = bq->count - 1; a < b; )
	    {
	      if (-bq->elements[a] == bq->elements[b])
		break;
	      if (-bq->elements[a] > bq->elements[b])
		a++;
	      else
		b--;
	    }
	  if (a < b)
	    queue_truncate(bq, bqcnt4);	/* ignore this block */
	  else
	    queue_push(bq, 0);	/* finish block */
	}
      /* advance to next block */
      while (bq->elements[i])
	i++;
    }
  queue_deleten(bq, bqcnt, bqcnt3 - bqcnt);
  if (bqcnt == bq->count)
    return flags & CPLXDEPS_TODNF ? 0 : 1;
  return -1;
}

static int normalize_dep(Pool *pool, Id dep, Queue *bq, int flags);

static int
normalize_dep_or(Pool *pool, Id dep1, Id dep2, Queue *bq, int flags, int invflags)
{
  int r1, r2, bqcnt2, bqcnt = bq->count;
  r1 = normalize_dep(pool, dep1, bq, flags);
  if (r1 == 1)
    return 1;		/* early exit */
  bqcnt2 = bq->count;
  r2 = normalize_dep(pool, dep2, bq, flags ^ invflags);
  if (invflags)
    r2 = invert_depblocks(pool, bq, bqcnt2, r2);
  if (r1 == 1 || r2 == 1)
    {
      queue_truncate(bq, bqcnt);
      return 1;
    }
  if (r1 == 0)
    return r2;
  if (r2 == 0)
    return r1;
  if ((flags & CPLXDEPS_TODNF) == 0)
    return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
  return -1;
}

static int
normalize_dep_and(Pool *pool, Id dep1, Id dep2, Queue *bq, int flags, int invflags)
{
  int r1, r2, bqcnt2, bqcnt = bq->count;
  r1 = normalize_dep(pool, dep1, bq, flags);
  if (r1 == 0)
    return 0;		/* early exit */
  bqcnt2 = bq->count;
  r2 = normalize_dep(pool, dep2, bq, flags ^ invflags);
  if (invflags)
    r2 = invert_depblocks(pool, bq, bqcnt2, r2); 
  if (r1 == 0 || r2 == 0)
    {    
      queue_truncate(bq, bqcnt);
      return 0;
    }    
  if (r1 == 1)
    return r2;
  if (r2 == 1)
    return r1;
  if ((flags & CPLXDEPS_TODNF) != 0)
    return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
  return -1;
}

static int
normalize_dep_if_else(Pool *pool, Id dep1, Id dep2, Id dep3, Queue *bq, int flags)
{
  /* A IF (B ELSE C) -> (A OR ~B) AND (C OR B) */
  int r1, r2, bqcnt2, bqcnt = bq->count;
  r1 = normalize_dep_or(pool, dep1, dep2, bq, flags, CPLXDEPS_TODNF);
  if (r1 == 0)
    return 0;		/* early exit */
  bqcnt2 = bq->count;
  r2 = normalize_dep_or(pool, dep2, dep3, bq, flags, 0);
  if (r1 == 0 || r2 == 0)
    {
      queue_truncate(bq, bqcnt);
      return 0;
    }
  if (r1 == 1)
    return r2;
  if (r2 == 1)
    return r1;
  if ((flags & CPLXDEPS_TODNF) != 0)
    return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
  return -1;
}

static int
normalize_dep_unless_else(Pool *pool, Id dep1, Id dep2, Id dep3, Queue *bq, int flags)
{
  /* A UNLESS (B ELSE C) -> (A AND ~B) OR (C AND B) */
  int r1, r2, bqcnt2, bqcnt = bq->count;
  r1 = normalize_dep_and(pool, dep1, dep2, bq, flags, CPLXDEPS_TODNF);
  if (r1 == 1)
    return 1;		/* early exit */
  bqcnt2 = bq->count;
  r2 = normalize_dep_and(pool, dep2, dep3, bq, flags, 0);
  if (r1 == 1 || r2 == 1)
    {
      queue_truncate(bq, bqcnt);
      return 1;
    }
  if (r1 == 0)
    return r2;
  if (r2 == 0)
    return r1;
  if ((flags & CPLXDEPS_TODNF) == 0)
    return distribute_depblocks(pool, bq, bqcnt, bqcnt2, flags);
  return -1;
}

/*
 * returns:
 *   0: no blocks
 *   1: matches all
 *  -1: at least one block
 */
static int
normalize_dep(Pool *pool, Id dep, Queue *bq, int flags)
{
  Id p, dp;
  int bqcnt;

  if (pool_is_complex_dep(pool, dep))
    {
      Reldep *rd = GETRELDEP(pool, dep);
      if (rd->flags == REL_COND)
	{
	  Id evr = rd->evr;
	  if (ISRELDEP(evr))
	    {
	      Reldep *rd2 = GETRELDEP(pool, evr);
	      if (rd2->flags == REL_ELSE)
		return normalize_dep_if_else(pool, rd->name, rd2->name, rd2->evr, bq, flags);
	    }
	  return normalize_dep_or(pool, rd->name, rd->evr, bq, flags, CPLXDEPS_TODNF);
	}
      if (rd->flags == REL_UNLESS)
	{
	  Id evr = rd->evr;
	  if (ISRELDEP(evr))
	    {
	      Reldep *rd2 = GETRELDEP(pool, evr);
	      if (rd2->flags == REL_ELSE)
		return normalize_dep_unless_else(pool, rd->name, rd2->name, rd2->evr, bq, flags);
	    }
	  return normalize_dep_and(pool, rd->name, rd->evr, bq, flags, CPLXDEPS_TODNF);
	}
      if (rd->flags == REL_OR)
	return normalize_dep_or(pool, rd->name, rd->evr, bq, flags, 0);
      if (rd->flags == REL_AND)
	return normalize_dep_and(pool, rd->name, rd->evr, bq, flags, 0);
    }

  /* fallback case: just use package list */
  dp = pool_whatprovides(pool, dep);
  if (dp <= 2 || !pool->whatprovidesdata[dp])
    return dp == 2 ? 1 : 0;
  if (pool->whatprovidesdata[dp] == SYSTEMSOLVABLE)
    return 1;
  bqcnt = bq->count;
  if ((flags & CPLXDEPS_NAME) != 0)
    {
      while ((p = pool->whatprovidesdata[dp++]) != 0)
	{
	  if (!pool_match_nevr(pool, pool->solvables + p, dep))
	    continue;
	  queue_push(bq, p);
	  if ((flags & CPLXDEPS_TODNF) != 0)
	    queue_push(bq, 0);
	}
    }
  else if ((flags & CPLXDEPS_TODNF) != 0)
    {
      while ((p = pool->whatprovidesdata[dp++]) != 0)
        queue_push2(bq, p, 0);
    }
  else
    queue_push2(bq, pool->nsolvables, dp);	/* not yet expanded marker + offset */
  if (bq->count == bqcnt)
    return 0;	/* no provider */
  if (!(flags & CPLXDEPS_TODNF))
    queue_push(bq, 0);	/* finish block */
  return -1;
}

int
pool_normalize_complex_dep(Pool *pool, Id dep, Queue *bq, int flags)
{
  int i, bqcnt = bq->count;

  i = normalize_dep(pool, dep, bq, flags);
  if ((flags & CPLXDEPS_EXPAND) != 0)
    {
      if (i != 0 && i != 1)
        expand_simpledeps(pool, bq, bqcnt, 0);
    }
  if ((flags & CPLXDEPS_INVERT) != 0)
    i = invert_depblocks(pool, bq, bqcnt, i);
#ifdef CPLXDEBUG
  if (i == 0)
    printf("NONE\n");
  else if (i == 1)
    printf("ALL\n");
  else
    print_depblocks(pool, bq, bqcnt);
#endif
  return i;
}

void
pool_add_pos_literals_complex_dep(Pool *pool, Id dep, Queue *q, Map *m, int neg)
{
  while (ISRELDEP(dep))
    {
      Reldep *rd = GETRELDEP(pool, dep);
      if (rd->flags != REL_AND && rd->flags != REL_OR && rd->flags != REL_COND && rd->flags != REL_UNLESS)
	break;
      pool_add_pos_literals_complex_dep(pool, rd->name, q, m, neg);
      dep = rd->evr;
      if (rd->flags == REL_COND || rd->flags == REL_UNLESS)
	{
	  neg = !neg;
	  if (ISRELDEP(dep))
	    {
	      Reldep *rd2 = GETRELDEP(pool, rd->evr);
	      if (rd2->flags == REL_ELSE)
		{
	          pool_add_pos_literals_complex_dep(pool, rd2->evr, q, m, !neg);
		  dep = rd2->name;
		}
	    }
	}
    }
  if (!neg)
    {
      Id p, pp;
      FOR_PROVIDES(p, pp, dep)
	if (!MAPTST(m, p))
	  queue_push(q, p);
    }
}

#endif	/* ENABLE_COMPLEX_DEPS */