rework branch handling so that the old decisions are still available

This allows us to auto-minimize packages that got supplemented
later on.

3 files changed, 140 insertions, 62 deletions

diff --git a/src/policy.c b/src/policy.c
index cf05de0..5b72517 100644
--- a/src/policy.c
+++ b/src/policy.c
@@ -331,34 +331,14 @@ recheck_complex_dep(Solver *solv, Id p, Map *m, Queue **cqp)
 
 #endif
 
-/*
- * prune to recommended/suggested packages.
- * does not prune installed packages (they are also somewhat recommended).
- */
 
-static void
-prune_to_recommended(Solver *solv, Queue *plist)
+void
+policy_update_recommendsmap(Solver *solv)
 {
   Pool *pool = solv->pool;
-  int i, j, k, ninst;
   Solvable *s;
   Id p, pp, rec, *recp, sug, *sugp;
 
-  ninst = 0;
-  if (pool->installed)
-    {
-      for (i = 0; i < plist->count; i++)
-	{
-	  p = plist->elements[i];
-	  s = pool->solvables + p;
-	  if (pool->installed && s->repo == pool->installed)
-	    ninst++;
-	}
-    }
-  if (plist->count - ninst < 2)
-    return;
-
-  /* update our recommendsmap/suggestsmap */
   if (solv->recommends_index < 0)
     {
       MAPZERO(&solv->recommendsmap);
@@ -424,6 +404,38 @@ prune_to_recommended(Solver *solv, Queue *plist)
 	    }
 	}
     }
+}
+
+/*
+ * prune to recommended/suggested packages.
+ * does not prune installed packages (they are also somewhat recommended).
+ */
+
+static void
+prune_to_recommended(Solver *solv, Queue *plist)
+{
+  Pool *pool = solv->pool;
+  int i, j, k, ninst;
+  Solvable *s;
+  Id p;
+
+  ninst = 0;
+  if (pool->installed)
+    {
+      for (i = 0; i < plist->count; i++)
+	{
+	  p = plist->elements[i];
+	  s = pool->solvables + p;
+	  if (pool->installed && s->repo == pool->installed)
+	    ninst++;
+	}
+    }
+  if (plist->count - ninst < 2)
+    return;
+
+  /* update our recommendsmap/suggestsmap */
+  if (solv->recommends_index < solv->decisionq.count)
+    policy_update_recommendsmap(solv);
 
   /* prune to recommended/supplemented */
   ninst = 0;
diff --git a/src/policy.h b/src/policy.h
index c3ddb32..d034f0d 100644
--- a/src/policy.h
+++ b/src/policy.h
@@ -32,6 +32,7 @@ extern int  policy_illegal_vendorchange(Solver *solv, Solvable *s1, Solvable *s2
 extern int  policy_is_illegal(Solver *solv, Solvable *s1, Solvable *s2, int ignore);
 extern void policy_findupdatepackages(Solver *solv, Solvable *s, Queue *qs, int allowall);
 extern const char *policy_illegal2str(Solver *solv, int illegal, Solvable *s, Solvable *rs);
+extern void policy_update_recommendsmap(Solver *solv);
 
 extern void policy_create_obsolete_index(Solver *solv);
 
diff --git a/src/solver.c b/src/solver.c
index 403d9f8..b0f1bce 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -1242,11 +1242,13 @@ revert(Solver *solv, int level)
       solv->decisionq_why.count--;
       solv->propagate_index = solv->decisionq.count;
     }
-  while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
+  while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= level)
     {
       solv->branches.count--;
       while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
 	solv->branches.count--;
+      while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] < 0)
+	solv->branches.count--;
     }
   if (solv->recommends_index > solv->decisionq.count)
     solv->recommends_index = -1;	/* rebuild recommends/suggests maps */
@@ -1457,9 +1459,10 @@ selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid
   if (dq->count > 1)
     {
       /* multiple candidates, open a branch */
+      queue_push(&solv->branches, -dq->elements[0]);
       for (i = 1; i < dq->count; i++)
 	queue_push(&solv->branches, dq->elements[i]);
-      queue_push(&solv->branches, -level);
+      queue_push(&solv->branches, level);
     }
   p = dq->elements[0];
 
@@ -2672,9 +2675,10 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
 		      if (dq.count > 1)
 			{
 			  /* multiple candidates, open a branch */
+			  queue_push(&solv->branches, -dq.elements[0]);
 			  for (i = 1; i < dq.count; i++)
 			    queue_push(&solv->branches, dq.elements[i]);
-			  queue_push(&solv->branches, -level);
+			  queue_push(&solv->branches, level);
 			}
 		      p = dq.elements[0];
 		      POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
@@ -2801,31 +2805,45 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
 	  solv->solution_callback(solv, solv->solution_callback_data);
 	  if (solv->branches.count)
 	    {
-	      int i = solv->branches.count - 1;
-	      int l = -solv->branches.elements[i];
+	      int l, endi = 0;
 	      Id why;
-
-	      for (; i > 0; i--)
-		if (solv->branches.elements[i - 1] < 0)
-		  break;
-	      p = solv->branches.elements[i];
-	      POOL_DEBUG(SOLV_DEBUG_SOLVER, "branching with %s\n", pool_solvid2str(pool, p));
-	      queue_empty(&dq);
-	      for (j = i + 1; j < solv->branches.count; j++)
-		queue_push(&dq, solv->branches.elements[j]);
-	      solv->branches.count = i;
-	      level = l;
-	      revert(solv, level);
-	      if (dq.count > 1)
-	        for (j = 0; j < dq.count; j++)
-		  queue_push(&solv->branches, dq.elements[j]);
-	      olevel = level;
-	      why = -solv->decisionq_why.elements[solv->decisionq_why.count];
-	      assert(why >= 0);
-	      level = setpropagatelearn(solv, level, p, disablerules, why);
-	      if (level == 0)
-		break;
-	      continue;
+	      p = l = 0;
+	      for (i = solv->branches.count - 1; i >= 0; i--)
+		{
+		  p = solv->branches.elements[i];
+		  if (p > 0 && !l)
+		    {
+		      endi = i + 1;
+		      l = p;
+		    }
+		  else if (p > 0)
+		    break;
+		  else if (p < 0)
+		    l = 0;
+		}
+	      if (i >= 0)
+		{
+		  while (i > 0 && solv->branches.elements[i - 1] > 0)
+		    i--;
+		  p = solv->branches.elements[i];
+		  solv->branches.elements[i] = -p;
+		  while (i > 0 && solv->branches.elements[i - 1] < 0)
+		    i--;
+		  POOL_DEBUG(SOLV_DEBUG_SOLVER, "branching with %s\n", pool_solvid2str(pool, p));
+		  queue_empty(&dq);
+		  queue_insertn(&dq, 0, endi - i, solv->branches.elements + i);
+		  level = l;
+		  revert(solv, level);
+		  queue_insertn(&solv->branches, solv->branches.count, dq.count, dq.elements);
+		  /* hack: revert simply sets the count, so we can still access the reverted elements */
+		  why = -solv->decisionq_why.elements[solv->decisionq_why.count];
+		  assert(why >= 0);
+		  olevel = level;
+		  level = setpropagatelearn(solv, level, p, disablerules, why);
+		  if (level == 0)
+		    break;
+		  continue;
+		}
 	    }
 	  /* all branches done, we're finally finished */
 	  break;
@@ -2834,31 +2852,78 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
       /* auto-minimization step */
       if (solv->branches.count)
 	{
-	  int l = 0, lasti = -1, lastl = -1;
+	  int l = 0, lasti = -1, lastsi = -1, endi = 0;
 	  Id why;
-
-	  p = 0;
+	  p = l = 0;
+	  if (solv->recommends_index < solv->decisionq.count)
+	    policy_update_recommendsmap(solv);
 	  for (i = solv->branches.count - 1; i >= 0; i--)
 	    {
 	      p = solv->branches.elements[i];
-	      if (p < 0)
-		l = -p;
-	      else if (p > 0 && solv->decisionmap[p] > l + 1)
+	      if (p > 0 && !l)
+		{
+		  l = p;
+		  endi = i + 1;
+		  lastsi = -1;
+		}
+	      else if (p > 0)
 		{
-		  lasti = i;
-		  lastl = l;
+		  if (solv->decisionmap[p] > l + 1)
+		    lasti = i;
+		  else
+		    {
+		      if (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p))
+			{
+			  lastsi = p;
+			}
+		    }
+		}
+	      else if (p < 0)
+		{
+		  l = 0;
+		  if (lastsi >= 0)
+		    {
+		      p = -p;
+		      if (solv->decisionmap[p] == l)
+			{
+			  if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
+			    lasti = lastsi;
+			}
+		    }
 		}
 	    }
 	  if (lasti >= 0)
 	    {
-	      /* kill old solvable so that we do not loop */
+	      int starti;
+	      /* find start of branch */
+	      for (i = lasti; i && solv->branches.elements[i] >= 0; )
+		i--;
+	      while (i > 0 && solv->branches.elements[i] < 0)
+		i--;
+	      starti = i ? i + 1 : 0;
+#if 0
+	      printf("minimization group level %d [%d-%d]:\n", solv->branches.elements[endi - 1], starti, endi);
+	      for (i = starti; i < endi - 1; i++)
+		printf("%c %c%s\n", i == lasti ? 'x' : ' ', solv->branches.elements[i] >= 0 ? ' ' : '-', pool_solvid2str(pool, solv->branches.elements[i] >= 0 ? solv->branches.elements[i] : -solv->branches.elements[i]));
+#endif
+	      l = solv->branches.elements[endi - 1];
 	      p = solv->branches.elements[lasti];
-	      solv->branches.elements[lasti] = 0;
-	      POOL_DEBUG(SOLV_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, pool_solvid2str(pool, p));
+	      solv->branches.elements[lasti] = -p;
+	      POOL_DEBUG(SOLV_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], l, pool_solvid2str(pool, p));
 	      minimizationsteps++;
-
-	      level = lastl;
+	      queue_empty(&dq);
+	      for (i = starti; i < endi - 1; i++)
+		if (solv->branches.elements[i] < 0)
+		  queue_push(&dq, solv->branches.elements[i]);
+	      for (i = starti; i < endi; i++)
+		if (solv->branches.elements[i] > 0)
+		  queue_push(&dq, solv->branches.elements[i]);
+	      if (dq.elements[dq.count - 2] <= 0)
+		queue_empty(&dq);
+	      level = l;
 	      revert(solv, level);
+	      queue_insertn(&solv->branches, solv->branches.count, dq.count, dq.elements);
+	      /* hack: revert simply sets the count, so we can still access the reverted elements */
 	      why = -solv->decisionq_why.elements[solv->decisionq_why.count];
 	      assert(why >= 0);
 	      olevel = level;