/*

 * 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);

}