Imported Upstream version 0.6.9upstream/0.6.9

Change-Id: Icf4a1aa6525f6c2bfc9da6f3ba1609728f39a073
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>

9 files changed, 537 insertions, 138 deletions

diff --git a/src/knownid.h b/src/knownid.h
index a229121..c094bf5 100644
--- a/src/knownid.h
+++ b/src/knownid.h
@@ -258,6 +258,8 @@ KNOWNID(SIGNATURE_DATA,		        "signature:data"),
 
 KNOWNID(PRODUCT_REGISTER_FLAVOR,	"product:regflavor"),		/* installed and available product */
 
+KNOWNID(SOLVABLE_INSTALLSTATUS,		"solvable:installstatus"),	/* debian install status */
+
 KNOWNID(ID_NUM_INTERNAL,		0)
 
 #ifdef KNOWNID_INITIALIZE
diff --git a/src/libsolv.ver b/src/libsolv.ver
index 91337ea..c795b7a 100644
--- a/src/libsolv.ver
+++ b/src/libsolv.ver
@@ -314,6 +314,8 @@ SOLV_1.0 {
 		solvable_trivial_installable_repo;
 		solvable_unset;
 		solver_allruleinfos;
+		solver_alternative2str;
+		solver_alternatives_count;
 		solver_calc_duchanges;
 		solver_calc_installsizechange;
 		solver_calculate_multiversionmap;
@@ -329,6 +331,7 @@ SOLV_1.0 {
 		solver_findproblemrule;
 		solver_free;
 		solver_freedupmaps;
+		solver_get_alternative;
 		solver_get_decisionblock;
 		solver_get_decisionlevel;
 		solver_get_decisionqueue;
@@ -360,6 +363,7 @@ SOLV_1.0 {
 		solver_problemruleinfo2str;
 		solver_rule2job;
 		solver_rule2jobidx;
+		solver_rule2pkgrule;
 		solver_rule2rules;
 		solver_rule2solvable;
 		solver_ruleclass;
diff --git a/src/policy.c b/src/policy.c
index 9e5a934..a0ecec1 100644
--- a/src/policy.c
+++ b/src/policy.c
@@ -406,11 +406,41 @@ policy_update_recommendsmap(Solver *solv)
     }
 }
 
+/* bring suggested/enhanced packages to front
+ * installed packages count as suggested */
+static void
+prefer_suggested(Solver *solv, Queue *plist)
+{
+  Pool *pool = solv->pool;
+  int i, count;
+
+  /* update our recommendsmap/suggestsmap */
+  if (solv->recommends_index < solv->decisionq.count)
+    policy_update_recommendsmap(solv);
+
+  for (i = 0, count = plist->count; i < count; i++)
+    {
+      Id p = plist->elements[i];
+      Solvable *s = pool->solvables + p;
+      if ((pool->installed && s->repo == pool->installed) ||
+          MAPTST(&solv->suggestsmap, p) ||
+          solver_is_enhancing(solv, s))
+	continue;	/* good package */
+      /* bring to back */
+     if (i < plist->count - 1)
+	{
+	  memmove(plist->elements + i, plist->elements + i + 1, (plist->count - 1 - i) * sizeof(Id));
+	  plist->elements[plist->count - 1] = p;
+	}
+      i--;
+      count--;
+    }
+}
+
 /*
  * prune to recommended/suggested packages.
  * does not prune installed packages (they are also somewhat recommended).
  */
-
 static void
 prune_to_recommended(Solver *solv, Queue *plist)
 {
@@ -467,6 +497,7 @@ prune_to_recommended(Solver *solv, Queue *plist)
   if (j)
     plist->count = j;
 
+#if 0
   /* anything left to prune? */
   if (plist->count - ninst < 2)
     return;
@@ -500,6 +531,7 @@ prune_to_recommended(Solver *solv, Queue *plist)
     }
   if (j)
     plist->count = j;
+#endif
 }
 
 static void
@@ -836,6 +868,240 @@ prune_to_best_version(Pool *pool, Queue *plist)
 }
 
 
+static int
+sort_by_name_evr_sortcmp(const void *ap, const void *bp, void *dp)
+{
+  Pool *pool = dp;
+  Id a, *aa = (Id *)ap;
+  Id b, *bb = (Id *)bp;
+  Id r = aa[1] - bb[1];
+  if (r)
+    return r < 0 ? -1 : 1;
+  a = aa[2] < 0 ? -aa[2] : aa[2];
+  b = bb[2] < 0 ? -bb[2] : bb[2];
+  if (pool->disttype != DISTTYPE_DEB)
+    {
+      /* treat release-less versions different */
+      const char *as = pool_id2str(pool, a);
+      const char *bs = pool_id2str(pool, b);
+      if (strchr(as, '-'))
+	{
+	  if (!strchr(bs, '-'))
+	    return -2;
+	}
+      else
+	{
+	  if (strchr(bs, '-'))
+	    return 2;
+	}
+    }
+  r = pool_evrcmp(pool, b, a, EVRCMP_COMPARE);
+  if (!r && (aa[2] < 0 || bb[2] < 0))
+    {
+      if (bb[2] >= 0)
+	return 1;
+      if (aa[2] >= 0)
+	return -1;
+    }
+  if (r)
+    return r < 0 ? -1 : 1;
+  return 0;
+}
+
+/* common end of sort_by_srcversion and sort_by_common_dep */
+static void
+sort_by_name_evr_array(Pool *pool, Queue *plist, int count, int ent)
+{
+  Id lastname;
+  int i, j, bad, havebad;
+  Id *pp, *elements = plist->elements;
+
+  if (ent < 2)
+    {
+      queue_truncate(plist, count);
+      return;
+    }
+  solv_sort(elements + count * 2, ent, sizeof(Id) * 3, sort_by_name_evr_sortcmp, pool);
+  lastname = 0;
+  bad = havebad = 0;
+  for (i = 0, pp = elements + count * 2; i < ent; i++, pp += 3)
+    {
+      if (lastname && pp[1] == lastname)
+	{
+          if (pp[0] != pp[-3] && sort_by_name_evr_sortcmp(pp - 3, pp, pool) == -1)
+	    {
+#if 0
+	      printf("%s - %s: bad %s %s - %s\n", pool_solvid2str(pool, elements[pp[-3]]), pool_solvid2str(pool, elements[pp[0]]), pool_dep2str(pool, lastname), pool_id2str(pool, pp[-1] < 0 ? -pp[-1] : pp[-1]), pool_id2str(pool, pp[2] < 0 ? -pp[2] : pp[2]));
+#endif
+	      bad++;
+	      havebad = 1;
+	    }
+	}
+      else
+	{
+	  bad = 0;
+	  lastname = pp[1];
+	}
+      elements[count + pp[0]] += bad;
+    }
+
+#if 0
+for (i = 0; i < count; i++)
+  printf("%s badness %d\n", pool_solvid2str(pool, elements[i]), elements[count + i]);
+#endif
+
+  if (havebad)
+    {
+      /* simple stable insertion sort */
+      if (pool->installed)
+	for (i = 0; i < count; i++)
+	  if (pool->solvables[elements[i]].repo == pool->installed)
+	    elements[i + count] = 0;
+      for (i = 1; i < count; i++)
+	for (j = i, pp = elements + count + j; j > 0; j--, pp--)
+	  if (pp[-1] > pp[0])
+	    {
+	      Id *pp2 = pp - count;
+	      Id p = pp[-1];
+	      pp[-1] = pp[0];
+	      pp[0] = p;
+	      p = pp2[-1];
+	      pp2[-1] = pp2[0];
+	      pp2[0] = p;
+	    }
+	  else
+	    break;
+    }
+  queue_truncate(plist, count);
+}
+
+#if 0
+static void
+sort_by_srcversion(Pool *pool, Queue *plist)
+{
+  int i, count = plist->count, ent = 0;
+  queue_insertn(plist, count, count, 0);
+  for (i = 0; i < count; i++)
+    {
+      Id name, evr, p = plist->elements[i];
+      Solvable *s = pool->solvables + p;
+      if (solvable_lookup_void(s, SOLVABLE_SOURCENAME))
+	name = s->name;
+      else
+        name = solvable_lookup_id(s, SOLVABLE_SOURCENAME);
+      if (solvable_lookup_void(s, SOLVABLE_SOURCEEVR))
+	evr = s->evr;
+      else
+        evr = solvable_lookup_id(s, SOLVABLE_SOURCEEVR);
+      if (!name || !evr || ISRELDEP(evr))
+	continue;
+      queue_push(plist, i);
+      queue_push2(plist, name, evr);
+      ent++;
+    }
+  sort_by_name_evr_array(pool, plist, count, ent);
+}
+#endif
+
+static void
+sort_by_common_dep(Pool *pool, Queue *plist)
+{
+  int i, count = plist->count, ent = 0;
+  Id id, *dp;
+  queue_insertn(plist, count, count, 0);
+  for (i = 0; i < count; i++)
+    {
+      Id p = plist->elements[i];
+      Solvable *s = pool->solvables + p;
+      if (!s->provides)
+	continue;
+      for (dp = s->repo->idarraydata + s->provides; (id = *dp++) != 0; )
+	{
+	  Reldep *rd;
+	  if (!ISRELDEP(id))
+	    continue;
+	  rd = GETRELDEP(pool, id);
+	  if ((rd->flags == REL_EQ || rd->flags == (REL_EQ | REL_LT) || rd->flags == REL_LT) && !ISRELDEP(rd->evr))
+	    {
+	      if (rd->flags == REL_EQ)
+		{
+		  /* ignore hashes */
+		  const char *s = pool_id2str(pool, rd->evr);
+		  if (strlen(s) >= 4)
+		    {
+		      while ((*s >= 'a' && *s <= 'f') || (*s >= '0' && *s <= '9'))
+			s++;
+		      if (!*s)
+			continue;
+		    }
+		}
+	      queue_push(plist, i);
+	      queue_push2(plist, rd->name, rd->flags == REL_LT ? -rd->evr : rd->evr);
+	      ent++;
+	    }
+	}
+    }
+  sort_by_name_evr_array(pool, plist, count, ent);
+}
+
+/* check if we have an update candidate */
+static void
+dislike_old_versions(Pool *pool, Queue *plist)
+{
+  int i, count = plist->count;
+  Id *elements = plist->elements;
+  int bad = 0;
+
+  for (i = 0; i < count; i++)
+    {
+      Id p = elements[i];
+      Solvable *s = pool->solvables + p;
+      Repo *repo = s->repo;
+      Id q, qq;
+
+      if (!repo || repo == pool->installed)
+	continue;
+      FOR_PROVIDES(q, qq, s->name)
+	{
+	  Solvable *qs = pool->solvables + q;
+	  if (q == p)
+	    continue;
+	  if (s->name != qs->name || s->arch != qs->arch)
+	    continue;
+	  if (repo->priority != qs->repo->priority)
+	    {
+	      if (repo->priority > qs->repo->priority)
+		continue;
+	      elements[i] = -p;
+	      bad = 1;
+	      break;
+	    }
+	  if (pool_evrcmp(pool, qs->evr, s->evr, EVRCMP_COMPARE) > 0)
+	    {
+	      elements[i] = -p;
+	      bad = 1;
+	      break;
+	    }
+	}
+    }
+  if (!bad)
+    return;
+  /* now move negative elements to the back */
+  for (i = 0; i < count; i++)
+    {
+      Id p = elements[i];
+      if (p >= 0)
+	continue;
+      if (i < plist->count - 1)
+	{
+	  memmove(elements + i, elements + i + 1, (plist->count - 1 - i) * sizeof(Id));
+	  elements[plist->count - 1] = -p;
+	}
+      i--;
+      count--;
+    }
+}
+
 /*
  *  POLICY_MODE_CHOOSE:     default, do all pruning steps
  *  POLICY_MODE_RECOMMEND:  leave out prune_to_recommended
@@ -857,7 +1123,19 @@ policy_filter_unwanted(Solver *solv, Queue *plist, int mode)
   if (plist->count > 1)
     prune_to_best_version(pool, plist);
   if (plist->count > 1 && mode == POLICY_MODE_CHOOSE)
-    prune_to_recommended(solv, plist);
+    {
+      prune_to_recommended(solv, plist);
+      if (plist->count > 1)
+	{
+	  /* do some fancy reordering */
+#if 0
+	  sort_by_srcversion(pool, plist);
+#endif
+	  dislike_old_versions(pool, plist);
+	  sort_by_common_dep(pool, plist);
+	  prefer_suggested(solv, plist);
+	}
+    }
 }
 
 
diff --git a/src/repodata.c b/src/repodata.c
index 4d57790..4ba1345 100644
--- a/src/repodata.c
+++ b/src/repodata.c
@@ -1444,6 +1444,8 @@ dataiterator_filelistcheck(Dataiterator *di)
   if (!needcomplete)
     {
       /* we don't need the complete filelist, so ignore all stubs */
+      if (data->repo->nrepodata == 2)
+	return 1;
       for (j = 1; j < data->nkeys; j++)
 	if (data->keys[j].name != REPOSITORY_SOLVABLES && data->keys[j].name != SOLVABLE_FILELIST)
 	  return 1;
diff --git a/src/rules.c b/src/rules.c
index 048cd99..c9bbf81 100644
--- a/src/rules.c
+++ b/src/rules.c
@@ -65,7 +65,7 @@ dep_possible(Solver *solv, Id dep, Map *m)
 	      return dep_possible(solv, rd->evr, m);
 	    }
 	  if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
-	    return solver_splitprovides(solv, rd->evr);
+	    return solver_splitprovides(solv, rd->evr, m);
 	  if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
 	    return solver_dep_installed(solv, rd->evr);
 	}
@@ -541,7 +541,7 @@ add_complex_deprules(Solver *solv, Id p, Id dep, int type, int dontfix, Queue *w
   queue_init(&bq);
 
   /* CNF expansion for requires, DNF + INVERT expansion for conflicts */
-  i = pool_normalize_complex_dep(pool, dep, &bq, type == SOLVER_RULE_DEP_PACKAGE_REQUIRES ? 0 : (CPLXDEPS_TODNF | CPLXDEPS_EXPAND | CPLXDEPS_INVERT));
+  i = pool_normalize_complex_dep(pool, dep, &bq, type == SOLVER_RULE_PKG_REQUIRES ? 0 : (CPLXDEPS_TODNF | CPLXDEPS_EXPAND | CPLXDEPS_INVERT));
   /* handle special cases */
   if (i == 0)
     {
@@ -2763,6 +2763,14 @@ solver_rule2solvable(Solver *solv, Id rid)
   return 0;
 }
 
+Id
+solver_rule2pkgrule(Solver *solv, Id rid)
+{
+  if (rid >= solv->choicerules && rid < solv->choicerules_end)
+    return solv->choicerules_ref[rid - solv->choicerules];
+  return 0;
+}
+
 static void
 solver_rule2rules_rec(Solver *solv, Id rid, Queue *q, Map *seen)
 {
@@ -3563,7 +3571,11 @@ check_xsupp(Solver *solv, Queue *depq, Id dep)
 	      return check_xsupp(solv, depq, rd->evr);
 	    }
 	  if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
+#if 0
 	    return solver_splitprovides(solv, rd->evr);
+#else
+	    return 0;
+#endif
 	  if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
 	    return solver_dep_installed(solv, rd->evr);
 	}
diff --git a/src/rules.h b/src/rules.h
index 83a2679..8f55af3 100644
--- a/src/rules.h
+++ b/src/rules.h
@@ -145,6 +145,7 @@ extern int  solver_rule2jobidx(struct _Solver *solv, Id rid);
 extern Id   solver_rule2job(struct _Solver *solv, Id rid, Id *whatp);
 extern Id   solver_rule2solvable(struct _Solver *solv, Id rid);
 extern void solver_rule2rules(struct _Solver *solv, Id rid, Queue *q, int recursive);
+extern Id   solver_rule2pkgrule(struct _Solver *solv, Id rid);
 
 /* orphan handling */
 extern void solver_breakorphans(struct _Solver *solv);
diff --git a/src/solver.c b/src/solver.c
index 14fe78d..46d0ca3 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -44,16 +44,34 @@
  * 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.
  */
+
+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;
+}
+
 int
-solver_splitprovides(Solver *solv, Id dep)
+solver_splitprovides(Solver *solv, Id dep, Map *m)
 {
   Pool *pool = solv->pool;
   Id p, pp;
   Reldep *rd;
   Solvable *s;
 
-  if (!solv->dosplitprovides || !solv->installed || (!solv->updatemap_all && !solv->updatemap.size))
+  if (!solv->dosplitprovides || !solv->installed)
     return 0;
   if (!ISRELDEP(dep))
     return 0;
@@ -76,8 +94,10 @@ solver_splitprovides(Solver *solv, Id dep)
       /* 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 &&
-          (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, p - solv->installed->start))))
+      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;
@@ -147,7 +167,7 @@ solver_check_installsuppdepq_dep(Solver *solv, Id dep)
           return r1 == 2 || r2 == 2 ? 2 : 1;
 	}
       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
-        return solver_splitprovides(solv, rd->evr);
+        return solver_splitprovides(solv, rd->evr, 0);
       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
         return solver_dep_installed(solv, rd->evr);
       if (rd->flags == REL_NAMESPACE && (q = solv->installsuppdepq) != 0)
@@ -1243,13 +1263,7 @@ revert(Solver *solv, int level)
       solv->propagate_index = solv->decisionq.count;
     }
   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--;
-    }
+    solv->branches.count -= solv->branches.elements[solv->branches.count - 2];
   if (solv->recommends_index > solv->decisionq.count)
     solv->recommends_index = -1;	/* rebuild recommends/suggests maps */
   if (solv->decisionq.count < solv->decisioncnt_jobs)
@@ -1379,6 +1393,7 @@ reorder_dq_for_jobrules(Solver *solv, int level, Queue *dq)
 {
   Pool *pool = solv->pool;
   int i, j, haveone = 0, dqcount = dq->count;
+  int decisionqcount = solv->decisionq.count;
   Id p;
   Solvable *s;
 
@@ -1390,25 +1405,34 @@ reorder_dq_for_jobrules(Solver *solv, int level, Queue *dq)
 	continue;
       if (solv->decisionmap[p] == 0)
 	{
+	  if (s->recommends || s->suggests)
+	    queue_push(&solv->decisionq, p);
 	  solv->decisionmap[p] = level + 1;
 	  haveone = 1;
 	}
     }
   if (!haveone)
     return;
+  policy_update_recommendsmap(solv);
   for (i = 0; i < dqcount; i++)
-    if (!solver_is_enhancing(solv, pool->solvables + dq->elements[i]))
-      {
-	queue_push(dq, dq->elements[i]);
-	dq->elements[i] = 0;
-      }
+    {
+      p = dq->elements[i];
+      if (!(pool->solvables[p].repo == solv->installed || MAPTST(&solv->suggestsmap, p) || solver_is_enhancing(solv, pool->solvables + p)))
+        {
+	  queue_push(dq, p);
+	  dq->elements[i] = 0;
+        }
+    }
   dqcount = dq->count;
   for (i = 0; i < dqcount; i++)
-    if (dq->elements[i] && !solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
-      {
-	queue_push(dq, dq->elements[i]);
-	dq->elements[i] = 0;
-      }
+    {
+      p = dq->elements[i];
+      if (p && !(pool->solvables[p].repo == solv->installed || MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
+        {
+	  queue_push(dq, p);
+	  dq->elements[i] = 0;
+        }
+    }
   for (i = j = 0; i < dq->count; i++)
     if (dq->elements[i])
       dq->elements[j++] = dq->elements[i];
@@ -1416,6 +1440,62 @@ reorder_dq_for_jobrules(Solver *solv, int level, Queue *dq)
   FOR_REPO_SOLVABLES(solv->installed, p, s)
     if (solv->decisionmap[p] == level + 1)
       solv->decisionmap[p] = 0;
+  if (solv->decisionq.count != decisionqcount)
+    {
+      solv->recommends_index = -1;
+      queue_truncate(&solv->decisionq, decisionqcount);
+    }
+}
+
+/*-------------------------------------------------------------------
+ *
+ * branch handling
+ */
+
+static void
+createbranch(Solver *solv, int level, Queue *dq, Id p, Id data)
+{
+  Pool *pool = solv->pool;
+  int i;
+  IF_POOLDEBUG (SOLV_DEBUG_POLICY)
+    {
+      POOL_DEBUG (SOLV_DEBUG_POLICY, "creating a branch:\n");
+      for (i = 0; i < dq->count; i++)
+	POOL_DEBUG (SOLV_DEBUG_POLICY, "  - %s\n", pool_solvid2str(pool, dq->elements[i]));
+    }
+  queue_push(&solv->branches, -dq->elements[0]);
+  for (i = 1; i < dq->count; i++)
+    queue_push(&solv->branches, dq->elements[i]);
+  queue_push2(&solv->branches, p, data);
+  queue_push2(&solv->branches, dq->count + 4, level);
+}
+
+static int
+takebranch(Solver *solv, int pos, int end, const char *msg, int disablerules)
+{
+  Pool *pool = solv->pool;
+  int level;
+  Id p, why;
+#if 0
+  {
+    int i;
+    printf("branch group level %d [%d-%d] %d %d:\n", solv->branches.elements[end - 1], start, end, solv->branches.elements[end - 4], solv->branches.elements[end - 3]);
+    for (i = end - solv->branches.elements[end - 2]; i < end - 4; i++)
+      printf("%c %c%s\n", i == pos ? 'x' : ' ', solv->branches.elements[i] >= 0 ? ' ' : '-', pool_solvid2str(pool, solv->branches.elements[i] >= 0 ? solv->branches.elements[i] : -solv->branches.elements[i]));
+  }
+#endif
+  level = solv->branches.elements[end - 1];
+  p = solv->branches.elements[pos];
+  solv->branches.elements[pos] = -p;
+  POOL_DEBUG(SOLV_DEBUG_SOLVER, "%s %d -> %d with %s\n", msg, solv->decisionmap[p], level, pool_solvid2str(pool, p));
+  /* hack: set level to zero so that revert does not remove the branch */
+  solv->branches.elements[end - 1] = 0;
+  revert(solv, level);
+  solv->branches.elements[end - 1] = level;
+  /* 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);
+  return setpropagatelearn(solv, level, p, disablerules, why);
 }
 
 /*-------------------------------------------------------------------
@@ -1434,40 +1514,18 @@ selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid
 {
   Pool *pool = solv->pool;
   Id p;
-  int i;
 
   if (dq->count > 1)
     policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
-  if (dq->count > 1)
-    {
-      /* XXX: didn't we already do that? */
-      /* XXX: shouldn't we prefer installed packages? */
-      /* XXX: move to policy.c? */
-      /* choose the supplemented one */
-      for (i = 0; i < dq->count; i++)
-	if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
-	  {
-	    dq->elements[0] = dq->elements[i];
-	    dq->count = 1;
-	    break;
-	  }
-    }
   /* if we're resolving job rules and didn't resolve the installed packages yet,
    * do some special supplements ordering */
   if (dq->count > 1 && ruleid >= solv->jobrules && ruleid < solv->jobrules_end && solv->installed && !solv->focus_installed)
     reorder_dq_for_jobrules(solv, level, dq);
+  /* if we have multiple candidates we open a branch */
   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);
-    }
+    createbranch(solv, level, dq, 0, ruleid);
   p = dq->elements[0];
-
   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p));
-
   return setpropagatelearn(solv, level, p, disablerules, ruleid);
 }
 
@@ -2528,7 +2586,6 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
           /* filter out all already supplemented packages if requested */
           if (!solv->addalreadyrecommended && dqs.count)
 	    {
-	      int dosplitprovides_old = solv->dosplitprovides;
 	      /* turn off all new packages */
 	      for (i = 0; i < solv->decisionq.count; i++)
 		{
@@ -2539,7 +2596,6 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
 		  if (s->repo && s->repo != solv->installed)
 		    solv->decisionmap[p] = -solv->decisionmap[p];
 		}
-	      solv->dosplitprovides = 0;
 	      /* filter out old supplements */
 	      for (i = j = 0; i < dqs.count; i++)
 		{
@@ -2563,7 +2619,6 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
 		  if (s->repo && s->repo != solv->installed)
 		    solv->decisionmap[p] = -solv->decisionmap[p];
 		}
-	      solv->dosplitprovides = dosplitprovides_old;
 	    }
 
 	  /* multiversion doesn't mix well with supplements.
@@ -2679,13 +2734,10 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
 		      if (!dq.count)
 			continue;
 		      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);
-			}
+		        policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
+		      /* if we have multiple candidates we open a branch */
+		      if (dq.count > 1)
+			  createbranch(solv, level, &dq, s - pool->solvables, rec);
 		      p = dq.elements[0];
 		      POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
 		      olevel = level;
@@ -2812,7 +2864,6 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
 	  if (solv->branches.count)
 	    {
 	      int l, endi = 0;
-	      Id why;
 	      p = l = 0;
 	      for (i = solv->branches.count - 1; i >= 0; i--)
 		{
@@ -2821,6 +2872,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
 		    {
 		      endi = i + 1;
 		      l = p;
+		      i -= 3;	/* skip: p data count */
 		    }
 		  else if (p > 0)
 		    break;
@@ -2831,21 +2883,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
 		{
 		  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);
+		  level = takebranch(solv, i, endi, "branching", disablerules);
 		  if (level == 0)
 		    break;
 		  continue;
@@ -2858,82 +2896,51 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
       /* auto-minimization step */
       if (solv->branches.count)
 	{
-	  int l = 0, lasti = -1, lastsi = -1, endi = 0;
-	  Id why;
-	  p = l = 0;
+	  int endi, lasti = -1, lastiend = -1;
 	  if (solv->recommends_index < solv->decisionq.count)
 	    policy_update_recommendsmap(solv);
-	  for (i = solv->branches.count - 1; i >= 0; i--)
+	  for (endi = solv->branches.count; endi > 0;)
 	    {
-	      p = solv->branches.elements[i];
-	      if (p > 0 && !l)
-		{
-		  l = p;
-		  endi = i + 1;
-		  lastsi = -1;
-		}
-	      else if (p > 0)
+	      int l, lastsi = -1, starti = endi - solv->branches.elements[endi - 2];
+	      l = solv->branches.elements[endi - 1];
+	      for (i = starti; i < endi - 4; i++)
 		{
-		  if (solv->decisionmap[p] > l + 1)
-		    lasti = i;
-		  else
+		  p = solv->branches.elements[i];
+		  if (p <= 0)
+		    continue;
+		  if (solv->decisionmap[p] > l)
 		    {
-		      if (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p))
-			{
-			  lastsi = p;
-			}
+		      lasti = i;
+		      lastiend = endi;
+		      lastsi = -1;
+		      break;
 		    }
+		  if (lastsi < 0 && (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
+		    lastsi = i;
 		}
-	      else if (p < 0)
+	      if (lastsi >= 0)
 		{
-		  l = 0;
-		  if (lastsi >= 0)
+		  /* we have a recommended package that could not be installed */
+		  /* take it if our current selection is not recommended */
+		  for (i = starti; i < endi - 4; i++)
 		    {
-		      p = -p;
-		      if (solv->decisionmap[p] == l)
+		      p = -solv->branches.elements[i];
+		      if (p <= 0 || solv->decisionmap[p] != l + 1)
+			continue;
+		      if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
 			{
-			  if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
-			    lasti = lastsi;
+			  lasti = lastsi;
+			  lastiend = endi;
+			  break;
 			}
 		    }
 		}
+	      endi = starti;
 	    }
 	  if (lasti >= 0)
 	    {
-	      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] = -p;
-	      POOL_DEBUG(SOLV_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], l, pool_solvid2str(pool, p));
 	      minimizationsteps++;
-	      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;
-	      level = setpropagatelearn(solv, level, p, disablerules, why);
+	      level = takebranch(solv, lasti, lastiend, "minimizing", disablerules);
 	      if (level == 0)
 		break;
 	      continue;		/* back to main loop */
@@ -3644,7 +3651,10 @@ solver_solve(Solver *solv, Queue *job)
    * add rules for suggests, enhances
    */
   oldnrules = solv->nrules;
-  solver_addpkgrulesforweak(solv, &addedmap);
+  if (hasdupjob && !solv->updatemap_all && solv->dosplitprovides && solv->installed)
+    solver_addpkgrulesforweak(solv, &addedmap);
+  else
+    solver_addpkgrulesforweak(solv, &addedmap);
   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of weak dependencies\n", solv->nrules - oldnrules);
 
 #ifdef ENABLE_LINKED_PKGS
@@ -4886,6 +4896,54 @@ pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags)
     }
 }
 
+int
+solver_alternatives_count(Solver *solv)
+{
+  Id *elements = solv->branches.elements;
+  int res, count;
+  for (res = 0, count = solv->branches.count; count; res++)
+    count -= elements[count - 2];
+  return res;
+}
+
+int
+solver_get_alternative(Solver *solv, Id alternative, Id *idp, Id *fromp, Id *chosenp, Queue *choices, int *levelp)
+{
+  int cnt = solver_alternatives_count(solv);
+  int count = solv->branches.count;
+  Id *elements = solv->branches.elements;
+  if (choices)
+    queue_empty(choices);
+  if (alternative <= 0 || alternative > cnt)
+    return 0;
+  elements += count;
+  for (; cnt > alternative; cnt--)
+    elements -= elements[-2];
+  if (levelp)
+    *levelp = elements[-1];
+  if (fromp)
+    *fromp = elements[-4];
+  if (idp)
+    *idp = elements[-3];
+  if (chosenp)
+    {
+      int i;
+      *chosenp = 0;
+      for (i = elements[-2]; i > 4; i--)
+	{
+	  Id p = -elements[-i];
+	  if (p > 0 && solv->decisionmap[p] == elements[-1] + 1)
+	    {
+	      *chosenp = p;
+	      break;
+	    }
+	}
+    }
+  if (choices)
+    queue_insertn(choices, 0, elements[-2] - 4, elements - elements[-2]);
+  return elements[-4] ? SOLVER_ALTERNATIVE_TYPE_RECOMMENDS : SOLVER_ALTERNATIVE_TYPE_RULE;
+}
+
 const char *
 solver_select2str(Pool *pool, Id select, Id what)
 {
@@ -5025,3 +5083,37 @@ pool_job2str(Pool *pool, Id how, Id what, Id flagmask)
   return pool_tmpappend(pool, s, "]", 0);
 }
 
+const char *
+solver_alternative2str(Solver *solv, int type, Id id, Id from)
+{
+  Pool *pool = solv->pool;
+  if (type == SOLVER_ALTERNATIVE_TYPE_RECOMMENDS)
+    {
+      const char *s = pool_dep2str(pool, id);
+      return pool_tmpappend(pool, s, ", recommended by ", pool_solvid2str(pool, from));
+    }
+  if (type == SOLVER_ALTERNATIVE_TYPE_RULE)
+    {
+      int rtype;
+      Id depfrom, depto, dep;
+      char buf[64];
+      if (solver_ruleclass(solv, id) == SOLVER_RULE_CHOICE)
+	id = solver_rule2pkgrule(solv, id);
+      rtype = solver_ruleinfo(solv, id, &depfrom, &depto, &dep);
+      if ((rtype & SOLVER_RULE_TYPEMASK) == SOLVER_RULE_JOB)
+	{
+	  if ((depto & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_PROVIDES)
+	    return pool_dep2str(pool, dep);
+	  return solver_select2str(pool, depto & SOLVER_SELECTMASK, dep);
+	}
+      if (rtype == SOLVER_RULE_PKG_REQUIRES)
+	{
+	  const char *s = pool_dep2str(pool, dep);
+	  return pool_tmpappend(pool, s, ", required by ", pool_solvid2str(pool, depfrom));
+	}
+      sprintf(buf, "Rule #%d", id);
+      return pool_tmpjoin(pool, buf, 0, 0);
+    }
+  return "unknown alternative type";
+}
+
diff --git a/src/solver.h b/src/solver.h
index 2a7f060..1cb9f15 100644
--- a/src/solver.h
+++ b/src/solver.h
@@ -299,6 +299,10 @@ typedef struct _Solver Solver;
 #define GET_USERINSTALLED_NAMES			(1 << 0)	/* package names instead if ids */
 #define GET_USERINSTALLED_INVERTED		(1 << 1)	/* autoinstalled */
 
+#define SOLVER_ALTERNATIVE_TYPE_RULE		1
+#define SOLVER_ALTERNATIVE_TYPE_RECOMMENDS	2
+#define SOLVER_ALTERNATIVE_TYPE_SUGGESTS	3
+
 extern Solver *solver_create(Pool *pool);
 extern void solver_free(Solver *solv);
 extern int  solver_solve(Solver *solv, Queue *job);
@@ -320,6 +324,8 @@ extern void pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int fl
 extern int  solver_describe_decision(Solver *solv, Id p, Id *infop);
 extern void solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq);
 
+extern int solver_alternatives_count(Solver *solv);
+extern int solver_get_alternative(Solver *solv, Id alternative, Id *idp, Id *fromp, Id *chosenp, Queue *choices, int *levelp);
 
 extern void solver_calculate_multiversionmap(Pool *pool, Queue *job, Map *multiversionmap);
 extern void solver_calculate_noobsmap(Pool *pool, Queue *job, Map *multiversionmap);	/* obsolete */
@@ -334,6 +340,8 @@ extern int  pool_isemptyupdatejob(Pool *pool, Id how, Id what);
 
 extern const char *solver_select2str(Pool *pool, Id select, Id what);
 extern const char *pool_job2str(Pool *pool, Id how, Id what, Id flagmask);
+extern const char *solver_alternative2str(Solver *solv, int type, Id id, Id from);
+
 
 /* iterate over all literals of a rule */
 #define FOR_RULELITERALS(l, pp, r)				\
diff --git a/src/solver_private.h b/src/solver_private.h
index 170efc2..f30b03a 100644
--- a/src/solver_private.h
+++ b/src/solver_private.h
@@ -17,7 +17,7 @@ extern void solver_run_sat(Solver *solv, int disablerules, int doweak);
 extern void solver_reset(Solver *solv);
 
 extern int solver_dep_installed(Solver *solv, Id dep);
-extern int solver_splitprovides(Solver *solv, Id dep);
+extern int solver_splitprovides(Solver *solv, Id dep, Map *m);
 
 static inline int
 solver_dep_fulfilled(Solver *solv, Id dep)
@@ -41,7 +41,7 @@ solver_dep_fulfilled(Solver *solv, Id dep)
           return solver_dep_fulfilled(solv, rd->evr);
 	}
       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
-        return solver_splitprovides(solv, rd->evr);
+        return solver_splitprovides(solv, rd->evr, 0);
       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
         return solver_dep_installed(solv, rd->evr);
     }