rework branch handling so that the old decisions are still available

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

diff --git a/src/policy.c b/src/policy.c
index cf05de0..5b72517 100644 (file)
--- 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 (file)
--- 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 (file)
--- 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;