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

/*
 * solver_util.c
 *
 * Dependency solver helper functions
 */

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

#include "solver.h"
#include "solver_private.h"
#include "bitmap.h"
#include "pool.h"
#include "poolarch.h"
#include "util.h"


/*-------------------------------------------------------------------
 * check if a installed package p is being updated
 */
static int
solver_is_updating(Solver *solv, Id p)
{
  /* check if the update rule is true */
  Pool *pool = solv->pool;
  Rule *r;
  Id l, pp;
  if (solv->decisionmap[p] >= 0)
    return 0;	/* old package stayed */
  r = solv->rules + solv->updaterules + (p - solv->installed->start);
  FOR_RULELITERALS(l, pp, r)
    if (l > 0 && l != p && solv->decisionmap[l] > 0)
      return 1;
  return 0;
}

/*-------------------------------------------------------------------
 * handle split provides
 *
 * a splitprovides dep looks like
 *     namespace:splitprovides(pkg REL_WITH path)
 * and is only true if pkg is installed and contains the specified path.
 * we also make sure that pkg is selected for an update, otherwise the
 * update would always be forced onto the user.
 * Map m is the map used when called from dep_possible.
 */
int
solver_splitprovides(Solver *solv, Id dep, Map *m)
{
  Pool *pool = solv->pool;
  Id p, pp;
  Reldep *rd;
  Solvable *s;

  if (!solv->dosplitprovides || !solv->installed)
    return 0;
  if (!ISRELDEP(dep))
    return 0;
  rd = GETRELDEP(pool, dep);
  if (rd->flags != REL_WITH)
    return 0;
  /*
   * things are a bit tricky here if pool->addedprovides == 1, because most split-provides are in
   * a non-standard location. If we simply call pool_whatprovides, we'll drag in the complete
   * file list. Instead we rely on pool_addfileprovides ignoring the addfileprovidesfiltered flag
   * for installed packages and check the lazywhatprovidesq (ignoring the REL_WITH part, but
   * we filter the package name further down anyway).
   */
  if (pool->addedfileprovides == 1 && !ISRELDEP(rd->evr) && !pool->whatprovides[rd->evr])
    pp = pool_searchlazywhatprovidesq(pool, rd->evr);
  else
    pp = pool_whatprovides(pool, dep);
  while ((p = pool->whatprovidesdata[pp++]) != 0)
    {
      /* here we have packages that provide the correct name and contain the path,
       * now do extra filtering */
      s = pool->solvables + p;
      if (s->repo != solv->installed || s->name != rd->name)
	continue;
      /* check if the package is updated. if m is set, we're called from dep_possible */
      if (m || solver_is_updating(solv, p))
	return 1;
    }
  return 0;
}

int
solver_dep_possible_slow(Solver *solv, Id dep, Map *m)
{
  Pool *pool = solv->pool;
  Id p, pp;

  if (ISRELDEP(dep))
    {
      Reldep *rd = GETRELDEP(pool, dep);
      if (rd->flags >= 8)
         {
          if (rd->flags == REL_COND || rd->flags == REL_UNLESS)
            return 1;
          if (rd->flags == REL_AND)
            {
              if (!solver_dep_possible_slow(solv, rd->name, m))
                return 0;
              return solver_dep_possible_slow(solv, rd->evr, m);
            }
          if (rd->flags == REL_OR)
            {
              if (solver_dep_possible_slow(solv, rd->name, m))
                return 1;
              return solver_dep_possible_slow(solv, rd->evr, m);
            }
          if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
            return solver_splitprovides(solv, rd->evr, m);
        }
    }
  FOR_PROVIDES(p, pp, dep)
    {
      if (MAPTST(m, p))
        return 1;
    }
  return 0;
}

int
solver_dep_fulfilled_cplx(Solver *solv, Reldep *rd)
{
  Pool *pool = solv->pool;
  if (rd->flags == REL_COND)
    {
      if (ISRELDEP(rd->evr))
	{
	  Reldep *rd2 = GETRELDEP(pool, rd->evr);
	  if (rd2->flags == REL_ELSE)
	    {
	      if (solver_dep_fulfilled(solv, rd2->name))
		return solver_dep_fulfilled(solv, rd->name);
	      return solver_dep_fulfilled(solv, rd2->evr);
	    }
	}
      if (solver_dep_fulfilled(solv, rd->name))
	return 1;
      return !solver_dep_fulfilled(solv, rd->evr);
    }
  if (rd->flags == REL_UNLESS)
    {
      if (ISRELDEP(rd->evr))
	{
	  Reldep *rd2 = GETRELDEP(pool, rd->evr);
	  if (rd2->flags == REL_ELSE)
	    {
	      if (!solver_dep_fulfilled(solv, rd2->name))
		return solver_dep_fulfilled(solv, rd->name);
	      return solver_dep_fulfilled(solv, rd2->evr);
	    }
	}
      if (!solver_dep_fulfilled(solv, rd->name))
	return 0;
      return !solver_dep_fulfilled(solv, rd->evr);
    }
  if (rd->flags == REL_AND)
    {
      if (!solver_dep_fulfilled(solv, rd->name))
	return 0;
      return solver_dep_fulfilled(solv, rd->evr);
    }
  if (rd->flags == REL_OR)
    {
      if (solver_dep_fulfilled(solv, rd->name))
	return 1;
      return solver_dep_fulfilled(solv, rd->evr);
    }
  return 0;
}

static int
solver_dep_fulfilled_complex_func(Solver *solv, Reldep *rd, int (*dep_fullfilled)(Solver *, Id))
{
  Pool *pool = solv->pool;
  int r1, r2;
  if (rd->flags == REL_COND)
    {
      if (ISRELDEP(rd->evr))
	{
	  Reldep *rd2 = GETRELDEP(pool, rd->evr);
	  if (rd2->flags == REL_ELSE)
	    {
	      r1 = dep_fullfilled(solv, rd2->name);
	      if (r1)
		{
		  r2 = dep_fullfilled(solv, rd->name);
		  return r2 && r1 == 2 ? 2 : r2;
		}
	      return dep_fullfilled(solv, rd2->evr);
	    }
	}
      r1 = dep_fullfilled(solv, rd->name);
      r2 = !dep_fullfilled(solv, rd->evr);
      if (!r1 && !r2)
	return 0;
      return r1 == 2 ? 2 : 1;
    }
  if (rd->flags == REL_UNLESS)
    {
      if (ISRELDEP(rd->evr))
	{
	  Reldep *rd2 = GETRELDEP(pool, rd->evr);
	  if (rd2->flags == REL_ELSE)
	    {
	      r1 = dep_fullfilled(solv, rd2->name);
	      if (r1)
		{
		  r2 = dep_fullfilled(solv, rd2->evr);
		  return r2 && r1 == 2 ? 2 : r2;
		}
	      return dep_fullfilled(solv, rd->name);
	    }
	}
      /* A AND NOT(B) */
      r1 = dep_fullfilled(solv, rd->name);
      r2 = !dep_fullfilled(solv, rd->evr);
      if (!r1 || !r2)
	return 0;
      return r1 == 2 ? 2 : 1;
    }
  if (rd->flags == REL_AND)
    {
      r1 = dep_fullfilled(solv, rd->name);
      if (!r1)
	return 0;
      r2 = dep_fullfilled(solv, rd->evr);
      if (!r2)
	return 0;
      return r1 == 2 || r2 == 2 ? 2 : 1;
    }
  if (rd->flags == REL_OR)
    {
      r1 = dep_fullfilled(solv, rd->name);
      r2 = dep_fullfilled(solv, rd->evr);
      if (!r1 && !r2)
	return 0;
      return r1 == 2 || r2 == 2 ? 2 : 1;
    }
  return 0;
}

/* mirrors solver_dep_fulfilled, but returns 2 if a new package
 * was involved */
static int
solver_dep_fulfilled_alreadyinstalled(Solver *solv, Id dep)
{
  Pool *pool = solv->pool;
  Id p, pp;
  int r;

  if (ISRELDEP(dep))
    {
      Reldep *rd = GETRELDEP(pool, dep);
      if (rd->flags == REL_COND || rd->flags == REL_UNLESS || rd->flags == REL_AND || rd->flags == REL_OR)
	return solver_dep_fulfilled_complex_func(solv, rd, solver_dep_fulfilled_alreadyinstalled);
      if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
        return solver_splitprovides(solv, rd->evr, 0) ? 2 : 0;
      if (rd->flags == REL_NAMESPACE && solv->installsuppdepq)
	{
	  Queue *q = solv->installsuppdepq;
	  int i;
	  for (i = 0; i < q->count; i++)
	    if (q->elements[i] == dep || q->elements[i] == rd->name)
	      return 2;
	}
    }
  r = 0;
  FOR_PROVIDES(p, pp, dep)
    if (solv->decisionmap[p] > 0)
      {
	Solvable *s = pool->solvables + p;
	if (s->repo && s->repo != solv->installed)
	  return 2;
        r = 1;
      }
  return r;
}

static int
solver_dep_fulfilled_namespace(Solver *solv, Id dep)
{
  Pool *pool = solv->pool;
  Id p, pp;
  int r = 1;

  if (ISRELDEP(dep))
    {
      Reldep *rd = GETRELDEP(pool, dep);
      if (rd->flags == REL_COND || rd->flags == REL_UNLESS || rd->flags == REL_AND || rd->flags == REL_OR)
	return solver_dep_fulfilled_complex_func(solv, rd, solver_dep_fulfilled_namespace);
      if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
        return solver_splitprovides(solv, rd->evr, 0) ? 2 : 0;
      if (rd->flags == REL_NAMESPACE)
	r = 2;
    }
  FOR_PROVIDES(p, pp, dep)
    if (solv->decisionmap[p] > 0)
      return r;
  return 0;
}

int
solver_is_supplementing_alreadyinstalled(Solver *solv, Solvable *s)
{
  Id sup, *supp;
  supp = s->repo->idarraydata + s->supplements;
  while ((sup = *supp++) != 0)
    {
      if (!solv->addalreadyrecommended && solver_dep_fulfilled_alreadyinstalled(solv, sup) != 2)
	continue;
      if (solv->only_namespace_recommended && solver_dep_fulfilled_namespace(solv, sup) != 2)
	continue;
      return 1;
    }
  return 0;
}

int
solver_is_namespace_dep_slow(Solver *solv, Reldep *rd)
{
  Pool *pool = solv->pool;
  for (;;)
    {
      if (rd->flags == REL_NAMESPACE)
	return 1;
      if (ISRELDEP(rd->name) && solver_is_namespace_dep_slow(solv, GETRELDEP(pool, rd->name)))
	return 1;
      if (!ISRELDEP(rd->evr))
	return 0;
      rd = GETRELDEP(pool, rd->evr);
    }
}

/*
 * add all installed packages that package p obsoletes to Queue q.
 * Package p is not installed. Also, we know that if
 * solv->keepexplicitobsoletes is not set, p is not in the multiversion map.
 * Entries may get added multiple times.
 */
static void
solver_add_obsoleted(Solver *solv, Id p, Queue *q)
{
  Pool *pool = solv->pool;
  Repo *installed = solv->installed;
  Id p2, pp2;
  Solvable *s = pool->solvables + p;
  Id obs, *obsp;
  Id lastp2 = 0;

  if (!solv->keepexplicitobsoletes || !(solv->multiversion.size && MAPTST(&solv->multiversion, p)))
    {
      FOR_PROVIDES(p2, pp2, s->name)
        {
          Solvable *ps = pool->solvables + p2;
          if (ps->repo != installed)
            continue;
          if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
            continue;
          if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
            continue;
          queue_push(q, p2);
          lastp2 = p2;
        }
    }
  if (!s->obsoletes)
    return;
  obsp = s->repo->idarraydata + s->obsoletes;
  while ((obs = *obsp++) != 0)
    FOR_PROVIDES(p2, pp2, obs)
      {
        Solvable *ps = pool->solvables + p2;
        if (ps->repo != installed)
          continue;
        if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
          continue;
        if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
          continue;
        if (p2 == lastp2)
          continue;
        queue_push(q, p2);
        lastp2 = p2;
      }
}

/*
 * Call solver_add_obsoleted and intersect the result with the
 * elements in Queue q starting at qstart.
 * Assumes that it's the first call if qstart == q->count.
 * May use auxillary map m for the intersection process, all
 * elements of q starting at qstart must have their bit cleared.
 * (This is also true after the function returns.)
 * (See solver_add_obsoleted for limitations of the package p)
 */
void
solver_intersect_obsoleted(Solver *solv, Id p, Queue *q, int qstart, Map *m)
{
  int i, j;
  int qcount = q->count;

  solver_add_obsoleted(solv, p, q);
  if (qcount == qstart)
    return;     /* first call */
  if (qcount == q->count)
    j = qstart;
  else if (qcount == qstart + 1)
    {
      /* easy if there's just one element */
      j = qstart;
      for (i = qcount; i < q->count; i++)
        if (q->elements[i] == q->elements[qstart])
          {
            j++;        /* keep the element */
            break;
          }
    }
  else if (!m || (!m->size && q->count - qstart <= 8))
    {
      /* faster than a map most of the time */
      int k;
      for (i = j = qstart; i < qcount; i++)
        {
          Id ip = q->elements[i];
          for (k = qcount; k < q->count; k++)
            if (q->elements[k] == ip)
              {
                q->elements[j++] = ip;
                break;
              }
        }
    }
  else
    {
      /* for the really pathologic cases we use the map */
      Repo *installed = solv->installed;
      if (!m->size)
        map_init(m, installed->end - installed->start);
      for (i = qcount; i < q->count; i++)
        MAPSET(m, q->elements[i] - installed->start);
      for (i = j = qstart; i < qcount; i++)
        if (MAPTST(m, q->elements[i] - installed->start))
          {
            MAPCLR(m, q->elements[i] - installed->start);
            q->elements[j++] = q->elements[i];
          }
    }
  queue_truncate(q, j);
}