gnu: Add libsolv.

* gnu/packages/patches/libsolv-conda-variant-priorization.patch: New file.
* gnu/local.mk (dist_patch_DATA): Add reference to it.
* gnu/packages/package-management.scm (libsolv): New variable.
[source]: Use patch.

Change-Id: Ie6cb43385b3489804f9a8fd8e1ddf1d2bb50f4cd

3 files changed, 502 insertions, 0 deletions

diff --git a/gnu/local.mk b/gnu/local.mk
index c87c83230ba..ada9f9ed086 100644
--- a/gnu/local.mk
+++ b/gnu/local.mk
@@ -1712,6 +1712,7 @@ dist_patch_DATA =						\
   %D%/packages/patches/librewolf-compare-paths.patch		\
   %D%/packages/patches/librewolf-neuter-locale-download.patch	\
   %D%/packages/patches/librewolf-use-system-wide-dir.patch	\
+  %D%/packages/patches/libsolv-conda-variant-priorization.patch	\
   %D%/packages/patches/libvirt-add-install-prefix.patch	\
   %D%/packages/patches/libvirt-respect-modules-path.patch	\
   %D%/packages/patches/libzmf-doxygen-1.14.patch		\
diff --git a/gnu/packages/package-management.scm b/gnu/packages/package-management.scm
index 4f5b8110592..434448c7e7d 100644
--- a/gnu/packages/package-management.scm
+++ b/gnu/packages/package-management.scm
@@ -97,8 +97,10 @@
   #:use-module (gnu packages jupyter)
   #:use-module (gnu packages less)
   #:use-module (gnu packages libedit)
+  #:use-module (gnu packages libffi)
   #:use-module (gnu packages linux)
   #:use-module (gnu packages lisp)
+  #:use-module (gnu packages logging)
   #:use-module (gnu packages lua)
   #:use-module (gnu packages man)
   #:use-module (gnu packages markup)
@@ -113,6 +115,7 @@
   #:use-module (gnu packages pkg-config)
   #:use-module (gnu packages polkit)
   #:use-module (gnu packages popt)
+  #:use-module (gnu packages pretty-print)
   #:use-module (gnu packages python)
   #:use-module (gnu packages python-build)
   #:use-module (gnu packages python-check)
@@ -1661,6 +1664,49 @@ it easy to create independent environments even for C libraries.  Conda is
 written entirely in Python.")
     (license license:bsd-3)))
 
+(define-public libsolv
+  (package
+    (name "libsolv")
+    (version "0.7.35")
+    (source
+     (origin
+       (method git-fetch)
+       (uri (git-reference
+             (url "https://github.com/openSUSE/libsolv")
+             (commit version)))
+       (file-name (git-file-name name version))
+       (sha256
+        (base32 "0gfzh9qzb7z4z7kr8fj0gafky0zvnrr6j6rb9fhmvcxvss6h4w8c"))
+       (patches
+        (search-patches "libsolv-conda-variant-priorization.patch"))))
+    (build-system cmake-build-system)
+    (arguments
+     (list
+      #:configure-flags
+      #~(list "-DENABLE_CONDA=ON"
+              "-DWITH_LIBXML2=ON"
+              "-DENABLE_LZMA_COMPRESSION=ON"
+              "-DENABLE_BZIP2_COMPRESSION=ON"
+              "-DENABLE_ZSTD_COMPRESSION=ON"
+              (string-append "-DZSTD_INCLUDE_DIRS="
+                             (assoc-ref %build-inputs "zstd")
+                             "/include")
+              (string-append "-DZSTD_LIBRARY="
+                             (assoc-ref %build-inputs "zstd")
+                             "/lib/libzstd.so"))))
+    (native-inputs
+     (list pkg-config))
+    (inputs
+     (list libxml2
+           xz
+           bzip2
+           `(,zstd "lib")))
+    (home-page "https://github.com/openSUSE/libsolv")
+    (synopsis "Library for solving package dependencies")
+    (description
+     "Libsolv is a library for solving package dependencies using a SAT solver.
+It is used by the RPM package manager and the Mamba/Conda package managers.")
+    (license license:bsd-3)))
 (define-public conan
   (package
     (name "conan")
diff --git a/gnu/packages/patches/libsolv-conda-variant-priorization.patch b/gnu/packages/patches/libsolv-conda-variant-priorization.patch
new file mode 100644
index 00000000000..4e72698dd82
--- /dev/null
+++ b/gnu/packages/patches/libsolv-conda-variant-priorization.patch
@@ -0,0 +1,455 @@
+Author: Wolf Vollprecht <w.vollprecht@gmail.com>
+Date: Wed Jun 30 12:19:34 2021 +0200
+Subject: Conda variant prioritization for libsolv.
+SPDX-License-Identifier: BSD-3-Clause
+
+This patch adds timestamp-based tie-breaking for conda packages when other
+criteria (version, build number, etc.) are equal.  It ensures that packages
+with later timestamps are preferred.
+
+Origin: <https://github.com/conda-forge/libsolv-feedstock/blob/main/recipe/conda_variant_priorization.patch>
+
+This patch is also included in the libsolv package from conda's defaults
+channel (repo.anaconda.com/pkgs/main).  Verified by extracting from:
+<https://repo.anaconda.com/pkgs/main/linux-64/libsolv-0.7.30-h6f1ccf3_2.tar.bz2>
+at path info/recipe/parent/patches/conda_variant_priorization.patch
+(sha256: 9864c23404c0ab75880b8784b1b34fdb61416de7319371702e4ef0f886ea6c3c)
+
+diff --git a/src/conda.c b/src/conda.c
+index 21ad6bfb..408a236a 100644
+--- a/src/conda.c
++++ b/src/conda.c
+@@ -134,7 +134,7 @@ solv_vercmp_conda(const char *s1, const char *q1, const char *s2, const char *q2
+ 		return -1;
+ 	      if (s1p - s1 > s2p - s2)
+ 		return 1;
+-	      r = s1p - s1 ? strncmp(s1, s2, s1p - s1) : 0;
++	      r = (s1p - s1) ? strncmp(s1, s2, s1p - s1) : 0;
+ 	      if (r)
+ 		return r;
+ 	    }
+diff --git a/src/policy.c b/src/policy.c
+index c02d2373..d6354cd2 100644
+--- a/src/policy.c
++++ b/src/policy.c
+@@ -833,6 +833,79 @@ move_installed_to_front(Pool *pool, Queue *plist)
+     }
+ }
+ 
++/*
++ * prune_to_best_version
++ *
++ * sort list of packages (given through plist) by name and evr
++ * return result through plist
++ */
++void
++prune_to_best_version(Pool *pool, Queue *plist)
++{
++#ifdef ENABLE_CONDA
++  if (pool->disttype == DISTTYPE_CONDA)
++     return prune_to_best_version_conda(pool, plist);
++#endif
++
++  int i, j, r;
++  Solvable *s, *best;
++
++  if (plist->count < 2)		/* no need to prune for a single entry */
++    return;
++  POOL_DEBUG(SOLV_DEBUG_POLICY, "prune_to_best_version %d\n", plist->count);
++
++  /* sort by name first, prefer installed */
++  solv_sort(plist->elements, plist->count, sizeof(Id), prune_to_best_version_sortcmp, pool);
++
++  /* now find best 'per name' */
++  best = 0;
++  for (i = j = 0; i < plist->count; i++)
++    {
++      s = pool->solvables + plist->elements[i];
++
++      POOL_DEBUG(SOLV_DEBUG_POLICY, "- %s [%d]%s\n",
++		 pool_solvable2str(pool, s), plist->elements[i], 
++		 (pool->installed && s->repo == pool->installed) ? "I" : "");
++
++      if (!best)		/* if no best yet, the current is best */
++        {
++          best = s;
++          continue;
++        }
++
++      /* name switch: finish group, re-init */
++      if (best->name != s->name)   /* new name */
++        {
++          plist->elements[j++] = best - pool->solvables; /* move old best to front */
++          best = s;		/* take current as new best */
++          continue;
++        }
++     
++      r = 0; 
++      if (r == 0)
++        r = best->evr != s->evr ? pool_evrcmp(pool, best->evr, s->evr, EVRCMP_COMPARE) : 0;
++#ifdef ENABLE_LINKED_PKGS
++      if (r == 0 && has_package_link(pool, s))
++        r = pool_link_evrcmp(pool, best, s);
++#endif
++      if (r < 0)
++	best = s;
++    }
++
++  plist->elements[j++] = best - pool->solvables;	/* finish last group */
++  plist->count = j;
++
++  /* we reduced the list to one package per name, now look at
++   * package obsoletes */
++  if (plist->count > 1)
++    {
++      if (plist->count == 2)
++        prune_obsoleted_2(pool, plist);
++      else
++        prune_obsoleted(pool, plist);
++    }
++}
++
+ #ifdef ENABLE_CONDA
+ static int
+ pool_featurecountcmp(Pool *pool, Solvable *s1, Solvable *s2)
+@@ -863,23 +936,221 @@ pool_buildflavorcmp(Pool *pool, Solvable *s1, Solvable *s2)
+     return 0;
+   return pool_evrcmp_str(pool, f1 ? f1 : "" , f2 ? f2 : "", EVRCMP_COMPARE);
+ }
+-#endif
++
++void intersect_selection(Pool* pool, Id dep, Queue* prev)
++{
++  Queue tmp;
++  int i = 0, j = 0, isectidx = 0;
++
++  queue_init(&tmp);
++
++  Id* pp, p;
++  pp = pool_whatprovides_ptr(pool, dep);
++  while ((p = *pp++) != 0)
++    queue_push(&tmp, p);
++
++  // set intersection, assuming sorted arrays
++  while (i < prev->count && j < tmp.count) 
++    if (prev->elements[i] < tmp.elements[j])
++      i++;
++    else if (tmp.elements[j] < prev->elements[i])
++      j++;
++    else
++      {
++        if (isectidx != i)
++          prev->elements[isectidx] = prev->elements[i];
++        i++, j++, isectidx++;
++      }
++
++  prev->count = isectidx;
++  queue_free(&tmp);
++}
++
++int check_deps_unequal(Pool* pool, Queue* q1, Queue* q2, Id name)
++{
++  Id dep;
++  int i, j;
++  int found = 0;
++  for (i = 0; i < q1->count; ++i)
++  {
++    dep = q1->elements[i];
++    if (ISRELDEP(dep) && GETRELDEP(pool, dep)->name == name)
++    {
++      for (j = 0; j < q2->count; ++j)
++      {
++        if (q2->elements[j] == dep)
++        {
++          found = 1;
++          break;
++        }
++      }
++      if (!found)
++        return 1;
++
++      found = 0;
++    }
++  }
++  return 0;
++}
++
++Id best_matching(Pool* pool, Queue* q, Id name, int* all_have_trackfeatures)
++{
++  int first = 1;
++  Id dep, p, *pp;
++
++  Queue selection;
++  queue_init(&selection);
++
++  for (int i = 0; i < q->count; ++i)
++  {
++    dep = q->elements[i];
++    if (!ISRELDEP(dep) || GETRELDEP(pool, dep)->name != name) continue;
++
++    if (first)
++    {
++      pp = pool_whatprovides_ptr(pool, dep);
++      while ((p = *pp++) != 0)
++        queue_push(&selection, p);
++      first = 0;
++    }
++    else
++      intersect_selection(pool, dep, &selection);
++  }
++
++  if (selection.count == 0)
++    return 0;
++
++  Solvable *stmp, *best = pool_id2solvable(pool, selection.elements[0]);
++  int cmp;
++
++  *all_have_trackfeatures = 1;
++  for (int i = 0; i < selection.count; ++i)
++    if (solvable_lookup_count(pool_id2solvable(pool, selection.elements[i]),
++                              SOLVABLE_TRACK_FEATURES) == 0)
++      {
++        *all_have_trackfeatures = 0;
++        break;
++      }
++  
++  for (int i = 0; i < selection.count; ++i)
++  {
++    stmp = pool_id2solvable(pool, selection.elements[i]);
++    cmp = pool_evrcmp(pool, best->evr, stmp->evr, 0);
++    if (cmp < 0) best = stmp;
++  }
++
++  return best->evr;
++}
++
++int conda_compare_dependencies(Pool *pool, Solvable *s1, Solvable *s2)
++{
++  int i, j, has_seen;
++  Queue q1, q2, seen;
++
++  queue_init(&q1);
++  queue_init(&q2);
++  queue_init(&seen);
++
++  solvable_lookup_deparray(s1, SOLVABLE_REQUIRES, &q1, -1);
++  solvable_lookup_deparray(s2, SOLVABLE_REQUIRES, &q2, -1);
++
++  int comparison_result = 0;
++
++  for (i = 0; i < q1.count; ++i)
++  {
++    Id x1 = q1.elements[i];
++    has_seen = 0;
++
++    if (!ISRELDEP(x1))
++      continue;
++
++    Reldep* rd1 = GETRELDEP(pool, x1);
++    for (j = 0; j < seen.count && has_seen == 0; ++j)
++      if (seen.elements[j] == rd1->name)
++        has_seen = 1;
++
++    if (has_seen)
++      continue;
++
++    // first make sure that deps are different between a & b
++    int deps_unequal = check_deps_unequal(pool, &q1, &q2, rd1->name);
++    if (!deps_unequal)
++      {
++        queue_push(&seen, rd1->name);
++        continue;
++      }
++
++    int aht_1, aht_2; // all have track features check
++    Id b1 = best_matching(pool, &q1, rd1->name, &aht_1);
++    Id b2 = best_matching(pool, &q2, rd1->name, &aht_2);
++
++    // one of both or both is not solvable...
++    // ignoring this case for now
++    if (b1 == 0 || b2 == 0)
++      continue;
++
++    // if one has deps with track features, and the other does not, 
++    // downweight the one with track features
++    if (aht_1 != aht_2)
++      comparison_result += (aht_1 - aht_2) * 100;
++
++    comparison_result += pool_evrcmp(pool, b2, b1, 0);
++  }
++
++  queue_free(&q1);
++  queue_free(&q2);
++  queue_free(&seen);
++
++  return comparison_result;
++}
++
++static int
++sort_by_best_dependencies(const void *ap, const void *bp, void *dp)
++{
++  Pool* pool = (Pool*) dp;
++
++  Id a = *(Id *)ap;
++  Id b = *(Id *)bp;
++  Solvable *sa, *sb;
++
++  sa = pool->solvables + a;
++  sb = pool->solvables + b;
++
++  int res = conda_compare_dependencies(pool, sa, sb);
++  if (res == 0)
++  {
++    // no differences, select later build
++    Repodata* ra = repo_last_repodata(sa->repo);
++    Repodata* rb = repo_last_repodata(sb->repo);
++
++    unsigned long long bta = repodata_lookup_num(ra, a, SOLVABLE_BUILDTIME, 0ull);
++    unsigned long long btb = repodata_lookup_num(rb, b, SOLVABLE_BUILDTIME, 0ull);
++
++    res = (btb > bta) ? 1 : -1;
++    POOL_DEBUG(SOLV_DEBUG_POLICY, "Fallback to timestamp comparison: %llu vs %llu: [%d]\n", bta, btb, res);
++  }
++
++  POOL_DEBUG(SOLV_DEBUG_POLICY, "Selecting variant [%c] of (a) %s vs (b) %s (score: %d)\n",
++             (res < 0 ? 'a' : 'b'), pool_solvable2str(pool, sa), pool_solvable2str(pool, sb), res);
++
++  return res; 
++}
+ 
+ /*
+- * prune_to_best_version
++ * prune_to_best_version_conda
+  *
+  * sort list of packages (given through plist) by name and evr
+  * return result through plist
+  */
+ void
+-prune_to_best_version(Pool *pool, Queue *plist)
++prune_to_best_version_conda(Pool *pool, Queue *plist)
+ {
+   int i, j, r;
+   Solvable *s, *best;
+ 
+-  if (plist->count < 2)		/* no need to prune for a single entry */
++  if (plist->count < 2)         /* no need to prune for a single entry */
+     return;
+-  POOL_DEBUG(SOLV_DEBUG_POLICY, "prune_to_best_version %d\n", plist->count);
++  POOL_DEBUG(SOLV_DEBUG_POLICY, "prune_to_best_version_conda %d\n", plist->count);
+ 
+   /* sort by name first, prefer installed */
+   solv_sort(plist->elements, plist->count, sizeof(Id), prune_to_best_version_sortcmp, pool);
+@@ -891,10 +1162,10 @@ prune_to_best_version(Pool *pool, Queue *plist)
+       s = pool->solvables + plist->elements[i];
+ 
+       POOL_DEBUG(SOLV_DEBUG_POLICY, "- %s [%d]%s\n",
+-		 pool_solvable2str(pool, s), plist->elements[i], 
+-		 (pool->installed && s->repo == pool->installed) ? "I" : "");
++                 pool_solvable2str(pool, s), plist->elements[i], 
++                 (pool->installed && s->repo == pool->installed) ? "I" : "");
+ 
+-      if (!best)		/* if no best yet, the current is best */
++      if (!best)                /* if no best yet, the current is best */
+         {
+           best = s;
+           continue;
+@@ -904,49 +1175,54 @@ prune_to_best_version(Pool *pool, Queue *plist)
+       if (best->name != s->name)   /* new name */
+         {
+           plist->elements[j++] = best - pool->solvables; /* move old best to front */
+-          best = s;		/* take current as new best */
++          best = s;             /* take current as new best */
+           continue;
+         }
+      
+       r = 0; 
+-#ifdef ENABLE_CONDA
+-      if (pool->disttype == DISTTYPE_CONDA)
+-        r = pool_featurecountcmp(pool, best, s);
+-#endif
++      r = pool_featurecountcmp(pool, best, s);
+       if (r == 0)
+         r = best->evr != s->evr ? pool_evrcmp(pool, best->evr, s->evr, EVRCMP_COMPARE) : 0;
+-#ifdef ENABLE_LINKED_PKGS
+-      if (r == 0 && has_package_link(pool, s))
+-        r = pool_link_evrcmp(pool, best, s);
+-#endif
+-#ifdef ENABLE_CONDA
+-      if (pool->disttype == DISTTYPE_CONDA)
+-	{
+-	  if (r == 0)
+-	    r = (best->repo ? best->repo->subpriority : 0) - (s->repo ? s->repo->subpriority : 0);
+-	  if (r == 0)
+-	    r = pool_buildversioncmp(pool, best, s);
+-	  if (r == 0)
+-	    r = pool_buildflavorcmp(pool, best, s);
+-	}
+-#endif
++      if (r == 0)
++        r = (best->repo ? best->repo->subpriority : 0) - (s->repo ? s->repo->subpriority : 0);
++      if (r == 0)
++        r = pool_buildversioncmp(pool, best, s);
++      // this can be removed as this comparison doesn't effect anything
++      if (r == 0)
++        r = pool_buildflavorcmp(pool, best, s);
+       if (r < 0)
+-	best = s;
++        best = s;
+     }
+-  plist->elements[j++] = best - pool->solvables;	/* finish last group */
+-  plist->count = j;
+ 
+-  /* we reduced the list to one package per name, now look at
+-   * package obsoletes */
+-  if (plist->count > 1)
++  Queue q;
++  queue_init(&q);
++  for (i = 0; i < plist->count; i++)
+     {
+-      if (plist->count == 2)
+-        prune_obsoleted_2(pool, plist);
+-      else
+-        prune_obsoleted(pool, plist);
++      s = pool->solvables + plist->elements[i];
++      r = pool_featurecountcmp(pool, best, s);
++      if (r == 0)
++        r = best->evr != s->evr ? pool_evrcmp(pool, best->evr, s->evr, EVRCMP_COMPARE) : 0;
++      if (r == 0)
++        r = (best->repo ? best->repo->subpriority : 0) - (s->repo ? s->repo->subpriority : 0);
++      if (r == 0)
++        r = pool_buildversioncmp(pool, best, s);
++      if (r == 0)
++        queue_push(&q, s - pool->solvables);
+     }
+-}
+ 
++  if (q.count > 1)
++    {
++      // order by first-level deps
++      solv_sort(q.elements, q.count, sizeof(Id), sort_by_best_dependencies, pool);
++    }
++
++  for (i = 0; i < q.count; ++i)
++    plist->elements[i] = q.elements[i];
++  plist->count = q.count;
++
++  queue_free(&q);
++}
++#endif  // ENABLE_CONDA
+ 
+ static int
+ sort_by_name_evr_sortcmp(const void *ap, const void *bp, void *dp)
+diff --git a/src/policy.h b/src/policy.h
+index 3ae1005a..a79483a4 100644
+--- a/src/policy.h
++++ b/src/policy.h
+@@ -45,6 +45,9 @@ extern void pool_best_solvables(Pool *pool, Queue *plist, int flags);
+ extern void prune_to_best_version(Pool *pool, Queue *plist);
+ extern void policy_prefer_favored(Solver *solv, Queue *plist);
+ 
++#ifdef ENABLE_CONDA
++extern void prune_to_best_version_conda(Pool *pool, Queue *plist);
++#endif
+ 
+ #ifdef __cplusplus
+ }