/*

 * Copyright (c) 2007-2009, Novell Inc.

 *

 * This program is licensed under the BSD license, read LICENSE.BSD

 * for further information

 */

/*

 * problems.c

 *

 */

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>

#include <string.h>

#include <assert.h>

#include "solver.h"

#include "solver_private.h"

#include "bitmap.h"

#include "pool.h"

#include "util.h"

#include "evr.h"

#include "solverdebug.h"

/**********************************************************************************/

/* a problem is an item on the solver's problem list. It can either be >0, in that

 * case it is a update/infarch/dup rule, or it can be <0, which makes it refer to a job

 * consisting of multiple job rules.

 */

static void

solver_disableproblem(Solver *solv, Id v)

{

  int i;

  Id *jp;

  if (v > 0)

    {

      if (v >= solv->infarchrules && v < solv->infarchrules_end)

	{

	  Pool *pool = solv->pool;

	  Id name = pool->solvables[-solv->rules[v].p].name;

	  while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)

	    v--;

	  for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)

	    solver_disablerule(solv, solv->rules + v);

	  return;

	}

      if (v >= solv->duprules && v < solv->duprules_end)

	{

	  Pool *pool = solv->pool;

	  Id name = pool->solvables[-solv->rules[v].p].name;

	  while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)

	    v--;

	  for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)

	    solver_disablerule(solv, solv->rules + v);

	  return;

	}

      solver_disablerule(solv, solv->rules + v);

      return;

    }

  v = -(v + 1);

  jp = solv->ruletojob.elements;

  if (solv->bestrules_info)

    {

      int ni = solv->bestrules_up - solv->bestrules;

      for (i = 0; i < ni; i++)

	{

	  int j = solv->bestrules_info[i];

	  if (j < 0 && jp[-j - solv->jobrules] == v)

	    solver_disablerule(solv, solv->rules + solv->bestrules + i);

	}

    }

  for (i = solv->jobrules; i < solv->jobrules_end; i++, jp++)

    if (*jp == v)

      solver_disablerule(solv, solv->rules + i);

}

/*-------------------------------------------------------------------

 * enableproblem

 */

static void

solver_enableproblem(Solver *solv, Id v)

{

  Rule *r;

  int i;

  Id *jp;

  if (v > 0)

    {

      if (v >= solv->infarchrules && v < solv->infarchrules_end)

	{

	  Pool *pool = solv->pool;

	  Id name = pool->solvables[-solv->rules[v].p].name;

	  while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)

	    v--;

	  for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)

	    solver_enablerule(solv, solv->rules + v);

	  return;

	}

      if (v >= solv->duprules && v < solv->duprules_end)

	{

	  Pool *pool = solv->pool;

	  Id name = pool->solvables[-solv->rules[v].p].name;

	  while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)

	    v--;

	  for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)

	    solver_enablerule(solv, solv->rules + v);

	  return;

	}

      if (v >= solv->featurerules && v < solv->featurerules_end)

	{

	  /* do not enable feature rule if update rule is enabled */

	  r = solv->rules + (v - solv->featurerules + solv->updaterules);

	  if (r->d >= 0)

	    return;

	}

      solver_enablerule(solv, solv->rules + v);

      if (v >= solv->updaterules && v < solv->updaterules_end)

	{

	  /* disable feature rule when enabling update rule */

	  r = solv->rules + (v - solv->updaterules + solv->featurerules);

	  if (r->p)

	    solver_disablerule(solv, r);

	}

      return;

    }

  v = -(v + 1);

  jp = solv->ruletojob.elements;

  if (solv->bestrules_info)

    {

      int ni = solv->bestrules_up - solv->bestrules;

      for (i = 0; i < ni; i++)

	{

	  int j = solv->bestrules_info[i];

	  if (j < 0 && jp[-j - solv->jobrules] == v)

	    solver_enablerule(solv, solv->rules + solv->bestrules + i);

	}

    }

  for (i = solv->jobrules; i < solv->jobrules_end; i++, jp++)

    if (*jp == v)

      solver_enablerule(solv, solv->rules + i);

}

/*-------------------------------------------------------------------

 * turn a problem rule into a problem id by normalizing it

 */

static Id

solver_ruletoproblem(Solver *solv, Id rid)

{

  if (rid >= solv->jobrules && rid < solv->jobrules_end)

    rid = -(solv->ruletojob.elements[rid - solv->jobrules] + 1);

  else if (rid >= solv->bestrules && rid < solv->bestrules_up && solv->bestrules_info[rid - solv->bestrules] < 0)

    rid = -(solv->ruletojob.elements[-solv->bestrules_info[rid - solv->bestrules] - solv->jobrules] + 1);

  else if (rid > solv->infarchrules && rid < solv->infarchrules_end)

    {

      Pool *pool = solv->pool;

      Id name = pool->solvables[-solv->rules[rid].p].name;

      while (rid > solv->infarchrules && pool->solvables[-solv->rules[rid - 1].p].name == name)

        rid--;

    }

  else if (rid > solv->duprules && rid < solv->duprules_end)

    {

      Pool *pool = solv->pool;

      Id name = pool->solvables[-solv->rules[rid].p].name;

      while (rid > solv->duprules && pool->solvables[-solv->rules[rid - 1].p].name == name)

        rid--;

    }

  return rid;

}

/*-------------------------------------------------------------------

 * when the solver runs into a problem, it needs to disable all

 * involved non-pkg rules and record the rules for solution

 * generation.

 */

void

solver_recordproblem(Solver *solv, Id rid)

{

  Id v = solver_ruletoproblem(solv, rid);

  /* return if problem already countains our rule */

  if (solv->problems.count)

    {

      int i;

      for (i = solv->problems.count - 1; i >= 0; i--)

        if (solv->problems.elements[i] == 0)    /* end of last problem reached? */

          break;

        else if (solv->problems.elements[i] == v)

          return;

    }

  queue_push(&solv->problems, v);

}

/*-------------------------------------------------------------------

 * this is called when a problem is solved by disabling a rule.

 * It calls disableproblem and then re-enables policy rules

 */

void

solver_fixproblem(Solver *solv, Id rid)

{

  Id v = solver_ruletoproblem(solv, rid);

  solver_disableproblem(solv, v);

  if (v < 0)

    solver_reenablepolicyrules(solv, -v);

}

/*-------------------------------------------------------------------

 * disable a set of problems

 */

void

solver_disableproblemset(Solver *solv, int start)

{

  int i;

  for (i = start + 1; i < solv->problems.count - 1; i++)

    solver_disableproblem(solv, solv->problems.elements[i]);

}

/*-------------------------------------------------------------------

 * try to fix a problem by auto-uninstalling packages

 */

Id

solver_autouninstall(Solver *solv, int start)

{

  Pool *pool = solv->pool;

  int i;

  int lastfeature = 0, lastupdate = 0;

  Id v;

  Id extraflags = -1;

  Map *m = 0;

  if (!solv->allowuninstall && !solv->allowuninstall_all)

    {

      if (!solv->allowuninstallmap.size)

	return 0;		/* why did we get called? */

      m = &solv->allowuninstallmap;

    }

  for (i = start + 1; i < solv->problems.count - 1; i++)

    {

      v = solv->problems.elements[i];

      if (v < 0)

	extraflags &= solv->job.elements[-v - 1];

      if (v >= solv->updaterules && v < solv->updaterules_end)

	{

	  Rule *r;

	  Id p = solv->installed->start + (v - solv->updaterules);

	  if (m && !MAPTST(m, v - solv->updaterules))

	    continue;

	  if (pool->considered && !MAPTST(pool->considered, p))

	    continue;	/* do not uninstalled disabled packages */

	  if (solv->bestrules_info && solv->bestrules_end > solv->bestrules)

	    {

	      int j;

	      for (j = start + 1; j < solv->problems.count - 1; j++)

		{

		  Id vv = solv->problems.elements[j];

		  if (vv >= solv->bestrules && vv < solv->bestrules_end && solv->bestrules_info[vv - solv->bestrules] == p)

		    break;

		}

	      if (j < solv->problems.count - 1)

		continue;	/* best rule involved, do not uninstall */

	    }

	  /* check if identical to feature rule, we don't like that (except for orphans) */

	  r = solv->rules + solv->featurerules + (v - solv->updaterules);

	  if (!r->p)

	    {

	      /* update rule == feature rule */

	      if (v > lastfeature)

		lastfeature = v;

	      /* prefer orphaned packages in dup mode */

	      if (solv->keep_orphans)

		{

		  r = solv->rules + v;

		  if (!r->d && !r->w2 && r->p == p)

		    {

		      lastfeature = v;

		      lastupdate = 0;

		      break;

		    }

		}

	      continue;

	    }

	  if (v > lastupdate)

	    lastupdate = v;

	}

    }

  if (!lastupdate && !lastfeature)

    return 0;

  v = lastupdate ? lastupdate : lastfeature;

  POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "allowuninstall disabling ");

  solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + v);

  /* should really be solver_fixproblem, but we know v is an update/feature rule */

  solver_disableproblem(solv, v);

  if (extraflags != -1 && (extraflags & SOLVER_CLEANDEPS) != 0 && solv->cleandepsmap.size)

    {

      /* add the package to the updatepkgs list, this will automatically turn

       * on cleandeps mode */

      Id p = solv->rules[v].p;

      if (!solv->cleandeps_updatepkgs)

	{

	  solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));

	  queue_init(solv->cleandeps_updatepkgs);

	}

      if (p > 0)

	{

	  int oldupdatepkgscnt = solv->cleandeps_updatepkgs->count;

          queue_pushunique(solv->cleandeps_updatepkgs, p);

	  if (solv->cleandeps_updatepkgs->count != oldupdatepkgscnt)

	    solver_disablepolicyrules(solv);

	}

    }

  return v;

}

/*-------------------------------------------------------------------

 * enable weak rules

 *

 * Reenable all disabled weak rules (marked in weakrulemap)

 *

 */

static void

enableweakrules(Solver *solv)

{

  int i;

  Rule *r;

  if (!solv->weakrulemap.size)

    return;

  for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)

    {

      if (r->d >= 0) /* already enabled? */

	continue;

      if (!MAPTST(&solv->weakrulemap, i))

	continue;

      solver_enablerule(solv, r);

    }

  /* make sure broken orphan rules stay disabled */

  if (solv->brokenorphanrules)

    for (i = 0; i < solv->brokenorphanrules->count; i++)

      solver_disablerule(solv, solv->rules + solv->brokenorphanrules->elements[i]);

}

/*-------------------------------------------------------------------

 *

 * refine_suggestion

 *

 * at this point, all rules that led to conflicts are disabled.

 * we re-enable all rules of a problem set but rule "sug", then

 * continue to disable more rules until there as again a solution.

 */

/* FIXME: think about conflicting assertions */

static void

refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined, int essentialok)

{

  Pool *pool = solv->pool;

  int i, j;

  Id v;

  Queue disabled;

  int disabledcnt;

  IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)

    {

      POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion start\n");

      for (i = 0; problem[i]; i++)

	{

	  if (problem[i] == sug)

	    POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "=> ");

	  solver_printproblem(solv, problem[i]);

	}

    }

  queue_empty(refined);

  if (!essentialok && sug < 0 && (solv->job.elements[-sug - 1] & SOLVER_ESSENTIAL) != 0)

    return;

  queue_push(refined, sug);

  /* re-enable all problem rules with the exception of "sug"(gestion) */

  solver_reset(solv);

  for (i = 0; problem[i]; i++)

    if (problem[i] != sug)

      solver_enableproblem(solv, problem[i]);

  if (sug < 0)

    solver_reenablepolicyrules(solv, -sug);

  /* here is where the feature rules come into play: if we disabled an

   * update rule, we enable the corresponding feature rule if there is

   * one. We do this to make the solver downgrade packages instead of

   * deinstalling them */

  if (sug >= solv->updaterules && sug < solv->updaterules_end)

    {

      /* enable feature rule */

      Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);

      if (r->p)

	solver_enablerule(solv, r);

    }

  enableweakrules(solv);

  /* disabled contains all of the rules we disabled in the refinement process */

  queue_init(&disabled);

  for (;;)

    {

      int nother, nfeature, nupdate, pass;

      queue_empty(&solv->problems);

      solver_reset(solv);

      /* we set disablerules to zero because we are only interested in

       * the first problem and we don't want the solver to disable the problems */

      solver_run_sat(solv, 0, 0);

      if (!solv->problems.count)

	{

	  POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no more problems!\n");

	  break;		/* great, no more problems */

	}

      disabledcnt = disabled.count;

      nother = nfeature = nupdate = 0;

      for (pass = 0; pass < 2; pass++)

	{

	  /* start with 1 to skip over proof index */

	  for (i = 1; i < solv->problems.count - 1; i++)

	    {

	      /* ignore solutions in refined */

	      v = solv->problems.elements[i];

	      if (v == 0)

		break;	/* end of problem reached */

	      if (!essentialok && v < 0 && (solv->job.elements[-v - 1] & SOLVER_ESSENTIAL) != 0)

		continue;	/* not that one! */

	      if (sug != v)

		{

		  /* check if v is in the given problems list

		   * we allow disabling all problem rules *after* sug in

		   * pass 2, to prevent getting the same solution twice */

		  for (j = 0; problem[j]; j++)

		    if (problem[j] == v || (pass && problem[j] == sug))

		      break;

		  if (problem[j] == v)

		    continue;

		}

	      if (v >= solv->featurerules && v < solv->featurerules_end)

		nfeature++;

	      else if (v > solv->updaterules && v < solv->updaterules_end)

		nupdate++;

	      else

	        nother++;

	      queue_push(&disabled, v);

	    }

	  if (disabled.count != disabledcnt)

	    break;

	}

      if (disabled.count == disabledcnt)

	{

	  /* no solution found, this was an invalid suggestion! */

	  POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no solution found!\n");

	  refined->count = 0;

	  break;

	}

      if (!nother && nupdate && nfeature)

	{

	  /* got only update rules, filter out feature rules */

	  POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "throwing away feature rules\n");

	  for (i = j = disabledcnt; i < disabled.count; i++)

	    {

	      v = disabled.elements[i];

	      if (v < solv->featurerules || v >= solv->featurerules_end)

	        disabled.elements[j++] = v;

	    }

	  disabled.count = j;

	  nfeature = 0;

	}

      if (disabled.count == disabledcnt + 1)

	{

	  /* just one suggestion, add it to refined list */

	  v = disabled.elements[disabledcnt];

	  if (!nfeature && v != sug)

	    queue_push(refined, v);	/* do not record feature rules */

	  solver_disableproblem(solv, v);

	  if (v < 0)

	    solver_reenablepolicyrules(solv, -v);

	  if (v >= solv->updaterules && v < solv->updaterules_end)

	    {

	      Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);

	      if (r->p)

		solver_enablerule(solv, r);	/* enable corresponding feature rule */

	    }

	}

      else

	{

	  /* more than one solution, disable all */

	  /* do not push anything on refine list, as we do not know which solution to choose */

	  /* thus, the user will get another problem if he selects this solution, where he

           * can choose the right one */

	  IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)

	    {

	      POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "more than one solution found:\n");

	      for (i = disabledcnt; i < disabled.count; i++)

		solver_printproblem(solv, disabled.elements[i]);

	    }

	  for (i = disabledcnt; i < disabled.count; i++)

	    {

	      v = disabled.elements[i];

	      solver_disableproblem(solv, v);

	      if (v >= solv->updaterules && v < solv->updaterules_end)

		{

		  Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);

		  if (r->p)

		    solver_enablerule(solv, r);

		}

	    }

	}

    }

  /* all done, get us back into the same state as before */

  /* enable refined rules again */

  for (i = 0; i < disabled.count; i++)

    solver_enableproblem(solv, disabled.elements[i]);

  queue_free(&disabled);

  /* reset policy rules */

  for (i = 0; problem[i]; i++)

    solver_enableproblem(solv, problem[i]);

  solver_disablepolicyrules(solv);

  /* disable problem rules again */

  for (i = 0; problem[i]; i++)

    solver_disableproblem(solv, problem[i]);

  POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion end\n");

}

/*-------------------------------------------------------------------

 * sorting helper for problems

 *

 * bring update rules before job rules

 * make essential job rules last

 */

static int

problems_sortcmp(const void *ap, const void *bp, void *dp)

{

  Queue *job = dp;

  Id a = *(Id *)ap, b = *(Id *)bp;

  if (a < 0 && b > 0)

    return 1;

  if (a > 0 && b < 0)

    return -1;

  if (a < 0 && b < 0)

    {

      int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;

      int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;

      int x = af - bf;

      if (x)

	return x;

    }

  return a - b;

}

/*

 * convert a solution rule into a job modifier

 */

static void

convertsolution(Solver *solv, Id why, Queue *solutionq)

{

  Pool *pool = solv->pool;

  if (why < 0)

    {

      why = -why;

      if (why < solv->pooljobcnt)

	{

	  queue_push(solutionq, SOLVER_SOLUTION_POOLJOB);

	  queue_push(solutionq, why);

	}

      else

	{

	  queue_push(solutionq, SOLVER_SOLUTION_JOB);

	  queue_push(solutionq, why - solv->pooljobcnt);

	}

      return;

    }

  if (why >= solv->infarchrules && why < solv->infarchrules_end)

    {

      Id p, name;

      /* infarch rule, find replacement */

      assert(solv->rules[why].p < 0);

      name = pool->solvables[-solv->rules[why].p].name;

      while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)

	why--;

      p = 0;

      for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)

	if (solv->decisionmap[-solv->rules[why].p] > 0)

	  {

	    p = -solv->rules[why].p;

	    break;

	  }

      if (!p)

	return;		/* false alarm */

      queue_push(solutionq, SOLVER_SOLUTION_INFARCH);

      queue_push(solutionq, p);

      return;

    }

  if (why >= solv->duprules && why < solv->duprules_end)

    {

      Id p, name;

      /* dist upgrade rule, find replacement */

      assert(solv->rules[why].p < 0);

      name = pool->solvables[-solv->rules[why].p].name;

      while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)

	why--;

      p = 0;

      for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++)

	if (solv->decisionmap[-solv->rules[why].p] > 0)

	  {

	    p = -solv->rules[why].p;

	    break;

	  }

      if (!p)

	return;		/* false alarm */

      queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);

      queue_push(solutionq, p);

      return;

    }

  if (why >= solv->updaterules && why < solv->updaterules_end)

    {

      /* update rule, find replacement package */

      Id p, pp, rp = 0;

      Rule *rr;

      /* check if this is a false positive, i.e. the update rule is fulfilled */

      rr = solv->rules + why;

      FOR_RULELITERALS(p, pp, rr)

	if (p > 0 && solv->decisionmap[p] > 0)

	  return;	/* false alarm */

      p = solv->installed->start + (why - solv->updaterules);

      if (solv->decisionmap[p] > 0)

	return;		/* false alarm, turned out we can keep the package */

      rr = solv->rules + solv->featurerules + (why - solv->updaterules);

      if (!rr->p)

	rr = solv->rules + why;

      if (rr->w2)

	{

	  int mvrp = 0;		/* multi-version replacement */

	  FOR_RULELITERALS(rp, pp, rr)

	    {

	      if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)

		{

		  mvrp = rp;

		  if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp)))

		    break;

		}

	    }

	  if (!rp && mvrp)

	    {

	      /* found only multi-version replacements */

	      /* have to split solution into two parts */

	      queue_push(solutionq, p);

	      queue_push(solutionq, mvrp);

	    }

	}

      queue_push(solutionq, p);

      queue_push(solutionq, rp);

      return;

    }

  if (why >= solv->bestrules && why < solv->bestrules_end)

    {

      int mvrp;

      Id p, pp, rp = 0;

      Rule *rr;

      /* check false positive */

      rr = solv->rules + why;

      FOR_RULELITERALS(p, pp, rr)

	if (p > 0 && solv->decisionmap[p] > 0)

	  return;	/* false alarm */

      /* check update/feature rule */

      p = solv->bestrules_info[why - solv->bestrules];

      if (p < 0)

	{

	  /* install job */

	  queue_push(solutionq, 0);

	  queue_push(solutionq, solv->ruletojob.elements[-p - solv->jobrules] + 1);

	  return;

	}

      if (solv->decisionmap[p] > 0)

	{

	  /* disable best rule by keeping the old package */

	  queue_push(solutionq, SOLVER_SOLUTION_BEST);

	  queue_push(solutionq, p);

	  return;

	}

      rr = solv->rules + solv->featurerules + (p - solv->installed->start);

      if (!rr->p)

	rr = solv->rules + solv->updaterules + (p - solv->installed->start);

      mvrp = 0;		/* multi-version replacement */

      FOR_RULELITERALS(rp, pp, rr)

	if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)

	  {

	    mvrp = rp;

	    if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp)))

	      break;

	  }

      if (!rp && mvrp)

	{

	  queue_push(solutionq, SOLVER_SOLUTION_BEST);	/* split, see above */

	  queue_push(solutionq, mvrp);

	  queue_push(solutionq, p);

	  queue_push(solutionq, 0);

	  return;

	}

      if (rp)

	{

	  queue_push(solutionq, SOLVER_SOLUTION_BEST);

	  queue_push(solutionq, rp);

	}

      return;

    }

  if (why >= solv->blackrules && why < solv->blackrules_end)

    {

      queue_push(solutionq, SOLVER_SOLUTION_BLACK);

      assert(solv->rules[why].p < 0);

      queue_push(solutionq, -solv->rules[why].p);

    }

}

/*

 * convert problem data into a form usable for refining.

 * Returns the number of problems.

 */

int

solver_prepare_solutions(Solver *solv)

{

  int i, j = 1, idx;

  if (!solv->problems.count)

    return 0;

  queue_empty(&solv->solutions);

  queue_push(&solv->solutions, 0);	/* dummy so idx is always nonzero */

  idx = solv->solutions.count;

  queue_push(&solv->solutions, -1);	/* unrefined */

  /* proofidx stays in position, thus we start with 1 */

  for (i = 1; i < solv->problems.count; i++)

    {

      Id p = solv->problems.elements[i];

      queue_push(&solv->solutions, p);

      if (p)

        continue;

      /* end of problem reached */

      solv->problems.elements[j++] = idx;

      if (i + 1 >= solv->problems.count)

        break;

      /* start another problem */

      solv->problems.elements[j++] = solv->problems.elements[++i];  /* copy proofidx */

      idx = solv->solutions.count;

      queue_push(&solv->solutions, -1);	/* unrefined */

    }

  solv->problems.count = j;

  return j / 2;

}

/*

 * refine the simple solution rule list provided by

 * the solver into multiple lists of job modifiers.

 */

static void

create_solutions(Solver *solv, int probnr, int solidx)

{

  Pool *pool = solv->pool;

  Queue redoq;

  Queue problem, solution, problems_save, branches_save, decisionq_reason_save;

  int i, j, nsol;

  int essentialok;

  unsigned int now;

  int oldmistakes = solv->cleandeps_mistakes ? solv->cleandeps_mistakes->count : 0;

  Id extraflags = -1;

  now = solv_timems(0);

  queue_init(&redoq);

  /* save decisionq, decisionq_why, decisionmap, and decisioncnt */

  for (i = 0; i < solv->decisionq.count; i++)

    {

      Id p = solv->decisionq.elements[i];

      queue_push(&redoq, p);

      queue_push(&redoq, solv->decisionq_why.elements[i]);

      queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);

    }

  /* save problems queue */

  problems_save = solv->problems;

  memset(&solv->problems, 0, sizeof(solv->problems));

  /* save branches queue */

  branches_save = solv->branches;

  memset(&solv->branches, 0, sizeof(solv->branches));

  /* save decisionq_reason */

  decisionq_reason_save = solv->decisionq_reason;

  memset(&solv->decisionq_reason, 0, sizeof(solv->decisionq_reason));

  /* extract problem from queue */

  queue_init(&problem);

  for (i = solidx + 1; i < solv->solutions.count; i++)

    {

      Id v = solv->solutions.elements[i];

      if (!v)

	break;

      queue_push(&problem, v);

      if (v < 0)

	extraflags &= solv->job.elements[-v - 1];

    }

  if (extraflags == -1)

    extraflags = 0;

  if (problem.count > 1)

    solv_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job);

  queue_push(&problem, 0);	/* mark end for refine_suggestion */

  problem.count--;

#if 0

  for (i = 0; i < problem.count; i++)

    printf("PP %d %d\n", i, problem.elements[i]);

#endif

  /* refine each solution element */

  nsol = 0;

  essentialok = 0;

  queue_init(&solution);

  for (i = 0; i < problem.count; i++)

    {

      int solstart = solv->solutions.count;

      refine_suggestion(solv, problem.elements, problem.elements[i], &solution, essentialok);

      queue_push(&solv->solutions, 0);	/* reserve room for number of elements */

      for (j = 0; j < solution.count; j++)

	convertsolution(solv, solution.elements[j], &solv->solutions);

      if (solv->solutions.count == solstart + 1)

	{

	  solv->solutions.count--;	/* this one did not work out */

	  if (nsol || i + 1 < problem.count)

	    continue;			/* got one or still hope */

	  if (!essentialok)

	    {

	      /* nothing found, start over */

	      POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, re-run with essentialok = 1\n");

	      essentialok = 1;

	      i = -1;

	      continue;

	    }

	  /* this is bad, we found no solution */

	  /* for now just offer a rule */

	  POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, already did essentialok, fake it\n");

	  queue_push(&solv->solutions, 0);

	  for (j = 0; j < problem.count; j++)

	    {

	      convertsolution(solv, problem.elements[j], &solv->solutions);

	      if (solv->solutions.count > solstart + 1)

		break;

	    }

	  if (solv->solutions.count == solstart + 1)

	    {

	      solv->solutions.count--;

	      continue;		/* sorry */

	    }

	}

      /* patch in number of solution elements */

      solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2;

      queue_push(&solv->solutions, 0);	/* add end marker */

      queue_push(&solv->solutions, 0);	/* add end marker */

      queue_push(&solv->solutions, problem.elements[i]);	/* just for bookkeeping */

      queue_push(&solv->solutions, extraflags & SOLVER_CLEANDEPS);	/* our extraflags */

      solv->solutions.elements[solidx + 1 + nsol++] = solstart;

    }

  solv->solutions.elements[solidx + 1 + nsol] = 0;	/* end marker */

  solv->solutions.elements[solidx] = nsol;

  queue_free(&problem);

  queue_free(&solution);

  /* restore decisions */

  memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));