Imported Upstream version 0.7.22upstream/0.7.22

33 files changed, 667 insertions, 222 deletions

diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
new file mode 100644
index 0000000..7506127
--- /dev/null
+++ b/.github/workflows/ci.yml
@@ -0,0 +1,30 @@
+---
+name: CI
+
+on:
+  push:
+    branches:
+      - master
+      - 0.6.x
+  pull_request:
+    branches:
+      - master
+
+jobs:
+  build:
+    runs-on: ubuntu-latest
+    steps:
+      - uses: actions/checkout@v2
+      - name: Setup
+        run:  |
+          sudo apt-get install cmake
+      - name: Build
+        run:  |
+          mkdir build
+          cd build
+          cmake -DDEBIAN=1 -DMULTI_SEMANTICS=1 ..
+          make
+      - name: Test
+        run:  |
+          cd build
+          make test
diff --git a/NEWS b/NEWS
index 6560320..509a991 100644
--- a/NEWS
+++ b/NEWS
@@ -1,6 +1,13 @@
 
 This file contains the major changes between libsolv versions:
 
+Version 0.7.22
+- selected bug fixes:
+  * reworked choice rule generation to cover more usecases
+  * support SOLVABLE_PREREQ_IGNOREINST in the ordering code
+- new features:
+  * support parsing of Debian's Multi-Arch indicator
+
 Version 0.7.21
 - selected bug fixes:
   * fix segfault on conflict resolution when using bindings
diff --git a/VERSION.cmake b/VERSION.cmake
index f9dbee0..4640fb0 100644
--- a/VERSION.cmake
+++ b/VERSION.cmake
@@ -49,5 +49,5 @@ SET(LIBSOLVEXT_SOVERSION "1")
 
 SET(LIBSOLV_MAJOR "0")
 SET(LIBSOLV_MINOR "7")
-SET(LIBSOLV_PATCH "21")
+SET(LIBSOLV_PATCH "22")
 
diff --git a/doc/gen/libsolv-bindings.3 b/doc/gen/libsolv-bindings.3
index 7384d2a..6d298af 100644
--- a/doc/gen/libsolv-bindings.3
+++ b/doc/gen/libsolv-bindings.3
@@ -2,12 +2,12 @@
 .\"     Title: Libsolv-Bindings
 .\"    Author: [see the "Author" section]
 .\" Generator: DocBook XSL Stylesheets vsnapshot <http://docbook.sf.net/>
-.\"      Date: 11/18/2020
+.\"      Date: 03/02/2022
 .\"    Manual: LIBSOLV
 .\"    Source: libsolv
 .\"  Language: English
 .\"
-.TH "LIBSOLV\-BINDINGS" "3" "11/18/2020" "libsolv" "LIBSOLV"
+.TH "LIBSOLV\-BINDINGS" "3" "03/02/2022" "libsolv" "LIBSOLV"
 .\" -----------------------------------------------------------------
 .\" * Define some portability stuff
 .\" -----------------------------------------------------------------
@@ -31,7 +31,7 @@
 libsolv-bindings \- access libsolv from perl/python/ruby
 .SH "DESCRIPTION"
 .sp
-Libsolv\(cqs language bindings offer an abstract, object orientated interface to the library\&. The supported languages are currently perl, python, and ruby\&. All example code (except in the specifics sections, of course) lists first the \(lqC\-ish\(rq interface, then the syntax for perl, python, and ruby (in that order)\&.
+Libsolv\(cqs language bindings offer an abstract, object orientated interface to the library\&. The supported languages are currently perl, python, ruby and tcl\&. All example code (except in the specifics sections, of course) lists first the \(lqC\-ish\(rq interface, then the syntax for perl, python, and ruby (in that order)\&.
 .SH "PERL SPECIFICS"
 .sp
 Libsolv\(cqs perl bindings can be loaded with the following statement:
@@ -3617,6 +3617,11 @@ Prefer the specified packages if the solver encounters an alternative\&. If a jo
 Avoid the specified packages if the solver encounters an alternative\&. This can also be used to block recommended or supplemented packages from being installed\&.
 .RE
 .PP
+\fBSOLVER_EXCLUDEFROMWEAK\fR
+.RS 4
+Avoid the specified packages to satisfy recommended or supplemented dependencies\&. Unlike SOLVER_DISFAVOR, it does not interfere with other rules\&.
+.RE
+.PP
 \fBSOLVER_JOBMASK\fR
 .RS 4
 A mask containing all the above action bits\&.
@@ -3959,7 +3964,7 @@ A rule of an unknown class\&. You should never encounter those\&.
 .PP
 \fBSOLVER_RULE_PKG\fR
 .RS 4
-A package dependency rule\&.
+A rule generated because of a package dependency\&.
 .RE
 .PP
 \fBSOLVER_RULE_UPDATE\fR
@@ -4011,7 +4016,7 @@ The package contains a required dependency which was not provided by any package
 .PP
 \fBSOLVER_RULE_PKG_REQUIRES\fR
 .RS 4
-Similar to SOLVER_RULE_PKG_NOTHING_PROVIDES_DEP, but in this case some packages provided the dependency but none of them could be installed due to other dependency issues\&.
+The package contains a required dependency which was provided by at least one package\&.
 .RE
 .PP
 \fBSOLVER_RULE_PKG_SELF_CONFLICT\fR
@@ -4021,12 +4026,12 @@ The package conflicts with itself\&. This is not allowed by older rpm versions\&
 .PP
 \fBSOLVER_RULE_PKG_CONFLICTS\fR
 .RS 4
-To fulfill the dependencies two packages need to be installed, but one of the packages contains a conflict with the other one\&.
+The package conflices with some other package\&.
 .RE
 .PP
 \fBSOLVER_RULE_PKG_SAME_NAME\fR
 .RS 4
-The dependencies can only be fulfilled by multiple versions of a package, but installing multiple versions of the same package is not allowed\&.
+This rules make sure that only one version of a package is installed in the system\&.
 .RE
 .PP
 \fBSOLVER_RULE_PKG_OBSOLETES\fR
diff --git a/doc/gen/libsolv-constantids.3 b/doc/gen/libsolv-constantids.3
index 228dfdd..8dd0ed6 100644
--- a/doc/gen/libsolv-constantids.3
+++ b/doc/gen/libsolv-constantids.3
@@ -2,12 +2,12 @@
 .\"     Title: Libsolv-Constantids
 .\"    Author: [see the "Author" section]
 .\" Generator: DocBook XSL Stylesheets vsnapshot <http://docbook.sf.net/>
-.\"      Date: 09/14/2018
+.\"      Date: 03/02/2022
 .\"    Manual: LIBSOLV
 .\"    Source: libsolv
 .\"  Language: English
 .\"
-.TH "LIBSOLV\-CONSTANTIDS" "3" "09/14/2018" "libsolv" "LIBSOLV"
+.TH "LIBSOLV\-CONSTANTIDS" "3" "03/02/2022" "libsolv" "LIBSOLV"
 .\" -----------------------------------------------------------------
 .\" * Define some portability stuff
 .\" -----------------------------------------------------------------
@@ -31,7 +31,7 @@
 libsolv-constantids \- fixed Ids for often used strings
 .SH "DESCRIPTION"
 .sp
-Constant Ids are Ids of strings that are often needed\&. They are defined to ease programming and reduce the number of pool_str2id calls\&. The constant Ids are part of the binary ABI of libsolv, a minor version update will only add new constants and not change existing Ids to maintain compatible\&. The on\-disk solv format works does not use the fixed Ids, but instead references the strings, so solv files can still be read when the ABI is broken\&.
+Constant Ids are Ids of strings that are often needed\&. They are defined to ease programming and reduce the number of pool_str2id calls\&. The constant Ids are part of the binary ABI of libsolv, a minor version update will only add new constants and not change existing Ids to maintain compatibility\&. The on\-disk solv format does not use the fixed Ids, but instead references the strings, so solv files can still be read when the ABI is broken\&.
 .SH "SPECIAL STRINGS"
 .PP
 \fBID_EMPTY ""\fR
@@ -45,7 +45,7 @@ The name of the always installed "system" solvable\&.
 .RE
 .SH "SOLVABLE ATTRIBUTES"
 .sp
-These are Ids for keyname of attributes\&. They can be used in the lookup and storage functions to select the correct attribute in the solvable\&. The descriptions below describe the intended semantics of the values stored in the attribute with the keyname\&.
+These are Ids for keynames of attributes\&. They can be used in the lookup and storage functions to select the correct attribute in the solvable\&. The descriptions below describe the intended semantics of the values stored in the attribute with the keyname\&.
 .PP
 \fBSOLVABLE_NAME "solvable:name"\fR
 .RS 4
diff --git a/doc/gen/libsolv-history.3 b/doc/gen/libsolv-history.3
index fc2d69b..9ccec7e 100644
--- a/doc/gen/libsolv-history.3
+++ b/doc/gen/libsolv-history.3
@@ -2,12 +2,12 @@
 .\"     Title: Libsolv-History
 .\"    Author: [see the "Author" section]
 .\" Generator: DocBook XSL Stylesheets vsnapshot <http://docbook.sf.net/>
-.\"      Date: 09/14/2018
+.\"      Date: 03/02/2022
 .\"    Manual: LIBSOLV
 .\"    Source: libsolv
 .\"  Language: English
 .\"
-.TH "LIBSOLV\-HISTORY" "3" "09/14/2018" "libsolv" "LIBSOLV"
+.TH "LIBSOLV\-HISTORY" "3" "03/02/2022" "libsolv" "LIBSOLV"
 .\" -----------------------------------------------------------------
 .\" * Define some portability stuff
 .\" -----------------------------------------------------------------
@@ -65,9 +65,9 @@ Having a new repository format was one big step, but the other area where libzyp
 As I was not very pleased with the way the solver worked, I looked at other solver algorithms\&. I checked smart, yum and apt, but could not find a convincing algorithm\&. My own experiments also were not very convincing, they worked fine for some problems but failed miserably for other corner cases\&.
 .SS "Using SAT for solving"
 .sp
-SUSE\(cqs hack week at the end of June 2007 turned out to be a turning point for the solver\&. Googling for solver algorithms, I stumbled over some note saying that some people are trying to use SAT algorithms to improve solving on Debian\&. Looking at the SAT entry in Wikipedia, it was easy to see that this indeed was the missing piece: SAT algorithms are well researched and there are quite some open source implementations\&. I decided to look at the minisat code, as it is one of the fastest solvers while consisting of too many lines of code\&.
+SUSE\(cqs hack week at the end of June 2007 turned out to be a turning point for the solver\&. Googling for solver algorithms, I stumbled over some note saying that some people are trying to use SAT algorithms to improve solving on Debian\&. Looking at the SAT entry in Wikipedia, it was easy to see that this indeed was the missing piece: SAT algorithms are well researched and there are quite some open source implementations\&. I decided to look at the minisat code, as it is one of the fastest solvers while consisting of not too many lines of code\&.
 .sp
-Of course, directly using minisat would not work, as a package solver does not need to find just one correct solution, but it also has to optimize some metrics, i\&.e\&. keep as many packages installed as possible\&. Thus, I needed to write my own solver incorporation the ideas and algorithms used in minisat\&. This wasn\(cqt very hard, and at the end of the hack week the solver calculated the first right solutions\&.
+Of course, directly using minisat would not work, as a package solver does not need to find just one correct solution, but it also has to optimize some metrics, i\&.e\&. keep as many packages installed as possible\&. Thus, I needed to write my own solver, incorporating the ideas and algorithms used in minisat\&. This wasn\(cqt very hard, and at the end of the hack week the solver calculated the first right solutions\&.
 .SS "Selling it to libzypp"
 .sp
 With those encouraging results, I went to Klaus Kaempf, the system management architect at SUSE\&. We spoke about how to convince the team to make libzypp switch to the new solver\&. Fortunately, libzypp comes with a plethora of solver test cases, so we decided to make the solver pass most of the test cases first\&. Klaus wrote a "deptestomatic" implementation to check the test cases\&. Together with Stephan Kulow, who is responsible for the openSUSE distribution, we tweaked and extended the solver until most of the test cases looked good\&.
diff --git a/doc/gen/libsolv-pool.3 b/doc/gen/libsolv-pool.3
index ab1b3f0..0cd26a1 100644
--- a/doc/gen/libsolv-pool.3
+++ b/doc/gen/libsolv-pool.3
@@ -2,12 +2,12 @@
 .\"     Title: Libsolv-Pool
 .\"    Author: [see the "Author" section]
 .\" Generator: DocBook XSL Stylesheets vsnapshot <http://docbook.sf.net/>
-.\"      Date: 11/18/2020
+.\"      Date: 03/02/2022
 .\"    Manual: LIBSOLV
 .\"    Source: libsolv
 .\"  Language: English
 .\"
-.TH "LIBSOLV\-POOL" "3" "11/18/2020" "libsolv" "LIBSOLV"
+.TH "LIBSOLV\-POOL" "3" "03/02/2022" "libsolv" "LIBSOLV"
 .\" -----------------------------------------------------------------
 .\" * Define some portability stuff
 .\" -----------------------------------------------------------------
diff --git a/doc/gen/libsolv.3 b/doc/gen/libsolv.3
index a6ac359..91d2290 100644
--- a/doc/gen/libsolv.3
+++ b/doc/gen/libsolv.3
@@ -2,12 +2,12 @@
 .\"     Title: Libsolv
 .\"    Author: [see the "Author" section]
 .\" Generator: DocBook XSL Stylesheets vsnapshot <http://docbook.sf.net/>
-.\"      Date: 09/14/2018
+.\"      Date: 03/02/2022
 .\"    Manual: LIBSOLV
 .\"    Source: libsolv
 .\"  Language: English
 .\"
-.TH "LIBSOLV" "3" "09/14/2018" "libsolv" "LIBSOLV"
+.TH "LIBSOLV" "3" "03/02/2022" "libsolv" "LIBSOLV"
 .\" -----------------------------------------------------------------
 .\" * Define some portability stuff
 .\" -----------------------------------------------------------------
@@ -54,7 +54,7 @@ libsolv\(cqs pool object
 .RE
 .SH "POINTER VALIDITY"
 .sp
-Note that all pointers to objects that have an Id have only a limited validity period, with the exception of Repo pointers\&. There are only guaranteed to be valid until a new object of that type is added or an object of that type is removed\&. Thus pointers to Solvable objects are only valid until another solvable is created, because adding a Solvable may relocate the Pool\(cqs Solvable array\&. This is also true for Pool strings, you should use solv_strdup() to create a copy of the string if you want to use it at some later time\&. You should use the Ids in the code and not the pointers, except for short times where you know that the pointer is safe\&.
+Note that all pointers to objects that have an Id have only a limited validity period, with the exception of Repo pointers\&. They are only guaranteed to be valid until a new object of that type is added or an object of that type is removed\&. Thus pointers to Solvable objects are only valid until another solvable is created, because adding a Solvable may relocate the Pool\(cqs Solvable array\&. This is also true for Pool strings, you should use solv_strdup() to create a copy of the string if you want to use it at some later time\&. You should use the Ids in the code and not the pointers, except for short times where you know that the pointer is safe\&.
 .sp
 Note also that the data lookup functions or the dataiterator also return values with limited lifetime, this is especially true for data stored in the paged data segment of solv files\&. This is normally data that consists of big strings like package descriptions or is not often needed like package checksums\&. Thus looking up a description of a solvable and then looking up the description of a different solvable or even the checksum of the same solvable may invalidate the first result\&. (The dataiterator supports a dataiterator_strdup() function to create a safe copy\&.)
 .sp
diff --git a/doc/gen/rpmdb2solv.1 b/doc/gen/rpmdb2solv.1
index c54c319..67e6036 100644
--- a/doc/gen/rpmdb2solv.1
+++ b/doc/gen/rpmdb2solv.1
@@ -2,12 +2,12 @@
 .\"     Title: rpmdb2solv
 .\"    Author: [see the "Author" section]
 .\" Generator: DocBook XSL Stylesheets vsnapshot <http://docbook.sf.net/>
-.\"      Date: 11/18/2020
+.\"      Date: 03/02/2022
 .\"    Manual: LIBSOLV
 .\"    Source: libsolv
 .\"  Language: English
 .\"
-.TH "RPMDB2SOLV" "1" "11/18/2020" "libsolv" "LIBSOLV"
+.TH "RPMDB2SOLV" "1" "03/02/2022" "libsolv" "LIBSOLV"
 .\" -----------------------------------------------------------------
 .\" * Define some portability stuff
 .\" -----------------------------------------------------------------
diff --git a/doc/libsolv-bindings.txt b/doc/libsolv-bindings.txt
index cdead65..5d46c08 100644
--- a/doc/libsolv-bindings.txt
+++ b/doc/libsolv-bindings.txt
@@ -2390,7 +2390,7 @@ Basic rule types:
 A rule of an unknown class. You should never encounter those.
 
 *SOLVER_RULE_PKG*::
-A package dependency rule.
+A rule generated because of a package dependency.
 
 *SOLVER_RULE_UPDATE*::
 A rule to implement the update policy of installed packages. Every
@@ -2439,22 +2439,19 @@ The package contains a required dependency which was not provided by
 any package.
 
 *SOLVER_RULE_PKG_REQUIRES*::
-Similar to SOLVER_RULE_PKG_NOTHING_PROVIDES_DEP, but in this case
-some packages provided the dependency but none of them could be
-installed due to other dependency issues.
+The package contains a required dependency which was provided by at
+least one package.
 
 *SOLVER_RULE_PKG_SELF_CONFLICT*::
 The package conflicts with itself. This is not allowed by older rpm
 versions.
 
 *SOLVER_RULE_PKG_CONFLICTS*::
-To fulfill the dependencies two packages need to be installed, but
-one of the packages contains a conflict with the other one.
+The package conflices with some other package.
 
 *SOLVER_RULE_PKG_SAME_NAME*::
-The dependencies can only be fulfilled by multiple versions of
-a package, but installing multiple versions of the same package
-is not allowed.
+This rules make sure that only one version of a package is installed
+in the system.
 
 *SOLVER_RULE_PKG_OBSOLETES*::
 To fulfill the dependencies two packages need to be installed, but
diff --git a/ext/repo_deb.c b/ext/repo_deb.c
index ac01b65..d400f95 100644
--- a/ext/repo_deb.c
+++ b/ext/repo_deb.c
@@ -462,6 +462,10 @@ control2solvable(Solvable *s, Repodata *data, char *control)
 	      checksumtype = REPOKEY_TYPE_MD5;
 	    }
 	  break;
+	case 'M' << 8 | 'U':
+	  if (!strcasecmp(tag, "multi-arch"))
+	    repodata_set_poolstr(data, s - pool->solvables, SOLVABLE_MULTIARCH, q);
+	  break;
 	case 'P' << 8 | 'A':
 	  if (!strcasecmp(tag, "package"))
 	    s->name = pool_str2id(pool, q, 1);
diff --git a/ext/repo_pubkey.c b/ext/repo_pubkey.c
index 883e13a..a965a65 100644
--- a/ext/repo_pubkey.c
+++ b/ext/repo_pubkey.c
@@ -271,18 +271,32 @@ static void
 pgpsig_makesigdata(struct pgpsig *sig, unsigned char *p, int l, unsigned char *pubkey, int pubkeyl, unsigned char *userid, int useridl, Chksum *h)
 {
   int type = sig->type;
-  unsigned char b[6];
+  unsigned char b[10];
   const unsigned char *cs;
   int csl;
 
   if (!h || sig->mpioff < 2 || l <= sig->mpioff)
     return;
+  if (p[0] != 3 && p[0] != 4 && p[0] != 5)
+    return;	/* unsupported signature version */
   if ((type >= 0x10 && type <= 0x13) || type == 0x1f || type == 0x18 || type == 0x20 || type == 0x28)
     {
-      b[0] = 0x99;
-      b[1] = pubkeyl >> 8;
-      b[2] = pubkeyl;
-      solv_chksum_add(h, b, 3);
+      if (p[0] == 4)
+	{
+	  b[0] = 0x99;
+	  b[1] = pubkeyl >> 8;
+	  b[2] = pubkeyl;
+	  solv_chksum_add(h, b, 3);
+	}
+      else if (p[0] == 5)
+	{
+	  b[0] = 0x9a;
+	  b[1] = pubkeyl >> 24;
+	  b[2] = pubkeyl >> 16;
+	  b[3] = pubkeyl >> 8;
+	  b[4] = pubkeyl;
+	  solv_chksum_add(h, b, 5);
+	}
       solv_chksum_add(h, pubkey, pubkeyl);
     }
   if ((type >= 0x10 && type <= 0x13))
@@ -301,7 +315,7 @@ pgpsig_makesigdata(struct pgpsig *sig, unsigned char *p, int l, unsigned char *p
   /* add trailer */
   if (p[0] == 3)
     solv_chksum_add(h, p + 2, 5);
-  else
+  else if (p[0] == 4)
     {
       int hl = 6 + (p[4] << 8 | p[5]);
       solv_chksum_add(h, p, hl);
@@ -313,6 +327,27 @@ pgpsig_makesigdata(struct pgpsig *sig, unsigned char *p, int l, unsigned char *p
       b[5] = hl;
       solv_chksum_add(h, b, 6);
     }
+  else if (p[0] == 5)
+    {
+      int hl = 6 + (p[4] << 8 | p[5]);
+      solv_chksum_add(h, p, hl);
+      if (type == 0 || type == 1)
+	{
+	  memset(b, 0, 6);
+          solv_chksum_add(h, b, 6);
+	}
+      hl += 6;
+      b[0] = 5;
+      b[1] = 0xff;
+      b[2] = b[3] = b[4] = b[5] = 0;
+      b[6] = hl >> 24;
+      b[7] = hl >> 16;
+      b[8] = hl >> 8;
+      b[9] = hl;
+      solv_chksum_add(h, b, 10);
+    }
+  else
+    return;
   cs = solv_chksum_get(h, &csl);
   if (cs[0] == p[sig->mpioff - 2] && cs[1] == p[sig->mpioff - 1])
     {
@@ -629,7 +664,7 @@ parsepubkey(Solvable *s, Repodata *data, unsigned char *p, int pl, int flags)
 	      Chksum *h;
 	      unsigned char hdr[3];
 	      unsigned char fp[20];
-	      char fpx[40 + 1];
+	      char fpx[20 * 2 + 1];
 
 	      maxsigcr = kcr = p[1] << 24 | p[2] << 16 | p[3] << 8 | p[4];
 	      hdr[0] = 0x99;
@@ -642,7 +677,31 @@ parsepubkey(Solvable *s, Repodata *data, unsigned char *p, int pl, int flags)
 	      solv_chksum_free(h, fp);
 	      solv_bin2hex(fp, 20, fpx);
 	      repodata_set_str(data, s - pool->solvables, PUBKEY_FINGERPRINT, fpx);
-	      memcpy(keyid, fp + 12, 8);	/* keyid is last 64 bits of fingerprint */
+	      memcpy(keyid, fp + (20 - 8), 8);	/* keyid is last 64 bits of fingerprint */
+	      pubdata = p + 5;
+	      pubdatal = l - 5;
+	    }
+	  else if (p[0] == 5 && l >= 6)
+	    {
+	      Chksum *h;
+	      unsigned char hdr[5];
+	      unsigned char fp[32];
+	      char fpx[32 * 2 + 1];
+
+	      maxsigcr = kcr = p[1] << 24 | p[2] << 16 | p[3] << 8 | p[4];
+	      hdr[0] = 0x9a;
+	      hdr[1] = l >> 24;
+	      hdr[2] = l >> 16;
+	      hdr[3] = l >> 8;
+	      hdr[4] = l;
+	      /* fingerprint is the sha256 over the packet */
+	      h = solv_chksum_create(REPOKEY_TYPE_SHA256);
+	      solv_chksum_add(h, hdr, 5);
+	      solv_chksum_add(h, p, l);
+	      solv_chksum_free(h, fp);
+	      solv_bin2hex(fp, 32, fpx);
+	      repodata_set_str(data, s - pool->solvables, PUBKEY_FINGERPRINT, fpx);
+	      memcpy(keyid, fp + (32 - 8), 8);	/* keyid is last 64 bits of fingerprint */
 	      pubdata = p + 5;
 	      pubdatal = l - 5;
 	    }
@@ -1086,18 +1145,21 @@ repo_find_all_pubkeys(Repo *repo, const char *keyid, Queue *q)
 {
   Id p;
   Solvable *s;
+  size_t keyidlen;
 
   queue_empty(q);
   if (!keyid)
     return;
-  queue_init(q);
+  keyidlen = strlen(keyid);
+  if (keyidlen < 8 || keyidlen > 64)
+    return;
   FOR_REPO_SOLVABLES(repo, p, s)
     {
       const char *kidstr, *evr = pool_id2str(s->repo->pool, s->evr);
 
-      if (!evr || strncmp(evr, keyid + 8, 8) != 0)
-       continue;
-      kidstr = solvable_lookup_str(s, PUBKEY_KEYID);
+      if (!evr || strncmp(evr, keyid + keyidlen - 8, 8) != 0)
+	continue;
+      kidstr = solvable_lookup_str(s, keyidlen >= 32 ? PUBKEY_FINGERPRINT : PUBKEY_KEYID);
       if (kidstr && !strcmp(kidstr, keyid))
         queue_push(q, p);
     }
diff --git a/ext/repo_pubkey.h b/ext/repo_pubkey.h
index 51946bf..20136ef 100644
--- a/ext/repo_pubkey.h
+++ b/ext/repo_pubkey.h
@@ -26,7 +26,7 @@ typedef struct s_Solvsig {
   Id htype;
   unsigned int created;
   unsigned int expires;
-  char keyid[17];
+  char keyid[16 + 1];
 } Solvsig;
 
 Solvsig *solvsig_create(FILE *fp);
diff --git a/ext/testcase.c b/ext/testcase.c
index 4262199..035cfdb 100644
--- a/ext/testcase.c
+++ b/ext/testcase.c
@@ -101,6 +101,7 @@ static struct resultflags2str {
   { TESTCASE_RESULT_JOBS,		"jobs" },
   { TESTCASE_RESULT_USERINSTALLED,	"userinstalled" },
   { TESTCASE_RESULT_ORDER,		"order" },
+  { TESTCASE_RESULT_ORDEREDGES,		"orderedges" },
   { 0, 0 }
 };
 
@@ -1453,6 +1454,31 @@ testcase_solverresult(Solver *solv, int resultflags)
 	}
       transaction_free(trans);
     }
+  if ((resultflags & TESTCASE_RESULT_ORDEREDGES) != 0)
+    {
+      Queue q;
+      int i, j;
+      Id p, p2;
+      Transaction *trans = solver_create_transaction(solv);
+      transaction_order(trans, SOLVER_TRANSACTION_KEEP_ORDEREDGES);
+      queue_init(&q);
+      for (i = 0; i < trans->steps.count; i++)
+	{
+	  p = trans->steps.elements[i];
+	  transaction_order_get_edges(trans, p, &q, 1);
+	  for (j = 0; j < q.count; j += 2)
+	    {
+	      char typebuf[32], *s;
+	      p2 = q.elements[j];
+	      sprintf(typebuf, " -%x-> ", q.elements[j + 1]);
+	      s = pool_tmpjoin(pool, "orderedge ", testcase_solvid2str(pool, p), typebuf);
+	      s = pool_tmpappend(pool, s, testcase_solvid2str(pool, p2), 0);
+	      strqueue_push(&sq, s);
+	    }
+	}
+      queue_free(&q);
+      transaction_free(trans);
+    }
   if ((resultflags & TESTCASE_RESULT_ALTERNATIVES) != 0)
     {
       char *altprefix;
diff --git a/ext/testcase.h b/ext/testcase.h
index c69098d..d57f116 100644
--- a/ext/testcase.h
+++ b/ext/testcase.h
@@ -22,6 +22,7 @@
 #define TESTCASE_RESULT_JOBS		(1 << 10)
 #define TESTCASE_RESULT_USERINSTALLED	(1 << 11)
 #define TESTCASE_RESULT_ORDER		(1 << 12)
+#define TESTCASE_RESULT_ORDEREDGES	(1 << 13)
 
 /* reuse solver hack, testsolv use only */
 #define TESTCASE_RESULT_REUSE_SOLVER	(1 << 31)
diff --git a/package/libsolv.changes b/package/libsolv.changes
index f9d3fb7..75dadab 100644
--- a/package/libsolv.changes
+++ b/package/libsolv.changes
@@ -1,4 +1,13 @@
 -------------------------------------------------------------------
+Mon Mar 21 10:05:32 CET 2022 - mls@suse.de
+
+- reworked choice rule generation to cover more usecases
+- support SOLVABLE_PREREQ_IGNOREINST in the ordering code
+  [bsc#1196514]
+- support parsing of Debian's Multi-Arch indicator
+- bump version to 0.7.22
+
+-------------------------------------------------------------------
 Fri Feb 25 17:32:20 CET 2022 - mls@suse.de
 
 - fix segfault on conflict resolution when using bindings
diff --git a/src/knownid.h b/src/knownid.h
index d131e78..2bb27b2 100644
--- a/src/knownid.h
+++ b/src/knownid.h
@@ -270,7 +270,8 @@ KNOWNID(SOLVABLE_TRACK_FEATURES,	"solvable:track_features"),	/* conda */
 KNOWNID(SOLVABLE_ISDEFAULT,		"solvable:isdefault"),
 KNOWNID(SOLVABLE_LANGONLY,		"solvable:langonly"),
 
-KNOWNID(UPDATE_COLLECTIONLIST,      "update:collectionlist"),  /* list of UPDATE_COLLECTION (actually packages) and UPDATE_MODULE */
+KNOWNID(UPDATE_COLLECTIONLIST,		"update:collectionlist"),	/* list of UPDATE_COLLECTION (actually packages) and UPDATE_MODULE */
+KNOWNID(SOLVABLE_MULTIARCH,		"solvable:multiarch"),		/* debian multi-arch field */
 
 KNOWNID(ID_NUM_INTERNAL,		0)
 
diff --git a/src/libsolv.ver b/src/libsolv.ver
index 51819fb..c77f8d3 100644
--- a/src/libsolv.ver
+++ b/src/libsolv.ver
@@ -434,6 +434,7 @@ SOLV_1.0 {
 		transaction_order_add_choices;
 		transaction_order_get_cycle;
 		transaction_order_get_cycleids;
+		transaction_order_get_edges;
 		transaction_print;
 		transaction_type;
 	local:
diff --git a/src/order.c b/src/order.c
index a6be968..f36e446 100644
--- a/src/order.c
+++ b/src/order.c
@@ -35,19 +35,23 @@ struct s_TransactionOrderdata {
   Id *invedgedata;
   int ninvedgedata;
   Queue *cycles;
+  Queue *edgedataq;		/* from SOLVER_TRANSACTION_KEEP_ORDEREDGES */
 };
 
 #define TYPE_BROKEN	(1<<0)
 #define TYPE_CON    	(1<<1)
 
-#define TYPE_REQ_P    	(1<<2)
-#define TYPE_PREREQ_P 	(1<<3)
+/* uninstall edges */
+#define TYPE_REQ_UI    	(1<<4)
+#define TYPE_PREREQ_UI 	(1<<5)
+#define TYPE_REQ_UU    	(1<<6)
+#define TYPE_PREREQ_UU 	(1<<7)
 
-#define TYPE_SUG	(1<<4)
-#define TYPE_REC	(1<<5)
-
-#define TYPE_REQ    	(1<<6)
-#define TYPE_PREREQ 	(1<<7)
+/* install edges */
+#define TYPE_SUG	(1<<8)
+#define TYPE_REC	(1<<9)
+#define TYPE_REQ    	(1<<10)
+#define TYPE_PREREQ 	(1<<11)
 
 #define TYPE_CYCLETAIL  (1<<16)
 #define TYPE_CYCLEHEAD  (1<<17)
@@ -70,6 +74,11 @@ transaction_clone_orderdata(Transaction *trans, Transaction *srctrans)
       trans->orderdata->cycles = solv_calloc(1, sizeof(Queue));
       queue_init_clone(trans->orderdata->cycles, od->cycles);
     }
+  if (od->edgedataq)
+    {
+      trans->orderdata->edgedataq = solv_calloc(1, sizeof(Queue));
+      queue_init_clone(trans->orderdata->edgedataq, od->edgedataq);
+    }
 }
 
 void
@@ -85,6 +94,11 @@ transaction_free_orderdata(Transaction *trans)
 	  queue_free(od->cycles);
 	  od->cycles = solv_free(od->cycles);
 	}
+      if (od->edgedataq)
+	{
+	  queue_init(od->edgedataq);
+	  od->edgedataq = solv_free(od->edgedataq);
+	}
       trans->orderdata = solv_free(trans->orderdata);
     }
 }
@@ -100,6 +114,7 @@ struct orderdata {
   Queue cycles;
   Queue cyclesdata;
   int ncycles;
+  Queue edgedataq;
 };
 
 static void
@@ -212,27 +227,34 @@ addedge(struct orderdata *od, Id from, Id to, int type)
 }
 
 static inline int
-havescripts(Pool *pool, Id solvid)
+havescripts(Pool *pool, Id solvid, Queue *ignoreinst)
 {
   Solvable *s = pool->solvables + solvid;
-  const char *dep;
   if (s->requires)
     {
       Id req, *reqp;
-      int inpre = 0;
       reqp = s->repo->idarraydata + s->requires;
       while ((req = *reqp++) != 0)
+        if (req == SOLVABLE_PREREQMARKER)
+	  break;
+      if (!req)
+	return 0;
+      while ((req = *reqp++) != 0)
 	{
-          if (req == SOLVABLE_PREREQMARKER)
+	  const char *dep = pool_id2str(pool, req);
+	  if (*dep == '/' && strcmp(dep, "/sbin/ldconfig") != 0)
 	    {
-	      inpre = 1;
-	      continue;
+	      if (ignoreinst && ignoreinst->count)
+		{
+		  int i;
+		  for (i = 0; i < ignoreinst->count; i++)
+		    if (req == ignoreinst->elements[i])
+		      break;
+		  if (i < ignoreinst->count)
+		    continue;
+		}
+	      return 1;
 	    }
-	  if (!inpre)
-	    continue;
-	  dep = pool_id2str(pool, req);
-	  if (*dep == '/' && strcmp(dep, "/sbin/ldconfig") != 0)
-	    return 1;
 	}
     }
   return 0;
@@ -247,7 +269,7 @@ addsolvableedges(struct orderdata *od, Solvable *s)
   int i, j, pre, numins;
   Repo *installed = pool->installed;
   Solvable *s2;
-  Queue depq;
+  Queue depq, ignoreinst;
   int provbyinst;
 
 #if 0
@@ -255,9 +277,20 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 #endif
   p = s - pool->solvables;
   queue_init(&depq);
+  queue_init(&ignoreinst);
   if (s->requires)
     {
       Id req, *reqp;
+      if (installed && s->repo == installed)
+	{
+	  reqp = s->repo->idarraydata + s->requires;
+	  while ((req = *reqp++) != 0)
+	    if (req == SOLVABLE_PREREQMARKER)
+	      {
+	        solvable_lookup_idarray(s, SOLVABLE_PREREQ_IGNOREINST, &ignoreinst);
+		break;
+	      }
+	}
       reqp = s->repo->idarraydata + s->requires;
       pre = TYPE_REQ;
       while ((req = *reqp++) != 0)
@@ -267,6 +300,16 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 	      pre = TYPE_PREREQ;
 	      continue;
 	    }
+	  if (pre == TYPE_PREREQ && ignoreinst.count)
+	    {
+	      /* check if this req is filtered. assumes that ignoreinst.count is small */
+	      int i;
+	      for (i = 0; i < ignoreinst.count; i++)
+		if (req == ignoreinst.elements[i])
+		  break;
+	      if (i < ignoreinst.count)
+		continue;
+	    }
 	  queue_empty(&depq);
 	  numins = 0;	/* number of packages to be installed providing it */
 	  provbyinst = 0;	/* provided by kept package */
@@ -300,9 +343,9 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 		  queue_pushunique(&depq, p2);
 		}
 	    }
-	  if (provbyinst)
+	  if (provbyinst && s->repo == installed)
 	    {
-	      /* prune to harmless ->inst edges */
+	      /* prune to harmless uninst->inst edges */
 	      for (i = j = 0; i < depq.count; i++)
 		if (pool->solvables[depq.elements[i]].repo != installed)
 		  depq.elements[j++] = depq.elements[i];
@@ -326,7 +369,7 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 #if 0
 				  printf("add interrreq uninst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, depq.elements[i]), pool_dep2str(pool, req), pool_solvid2str(pool, depq.elements[j]));
 #endif
-				  addedge(od, depq.elements[i], depq.elements[j], pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
+				  addedge(od, depq.elements[i], depq.elements[j], pre == TYPE_PREREQ ? TYPE_PREREQ_UI : TYPE_REQ_UI);
 				}
 			    }
 			}
@@ -344,7 +387,7 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 	      if (pool->solvables[p2].repo != installed)
 		{
 		  /* all elements of depq are installs, thus have different TEs */
-		  if (pool->solvables[p].repo != installed)
+		  if (s->repo != installed)
 		    {
 #if 0
 		      printf("add inst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p), pool_dep2str(pool, req), pool_solvid2str(pool, p2));
@@ -356,7 +399,7 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 #if 0
 		      printf("add uninst->inst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p), pool_dep2str(pool, req), pool_solvid2str(pool, p2));
 #endif
-		      addedge(od, p, p2, pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
+		      addedge(od, p, p2, pre == TYPE_PREREQ ? TYPE_PREREQ_UI : TYPE_REQ_UI);
 		    }
 		}
 	      else
@@ -365,16 +408,16 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 		    continue;	/* no inst->uninst edges, please! */
 
 		  /* uninst -> uninst edge. Those make trouble. Only add if we must */
-		  if (trans->transaction_installed[p - installed->start] && !havescripts(pool, p))
+		  if (trans->transaction_installed[p - installed->start] && !havescripts(pool, p, &ignoreinst))
 		    {
 		      /* p is obsoleted by another package and has no scripts */
-		      /* we assume that the obsoletor is good enough to replace p */
+		      /* we assume that the obsoleter is good enough to replace p */
 		      continue;
 		    }
 #if 0
 		  printf("add uninst->uninst edge (%s -> %s -> %s)\n", pool_solvid2str(pool, p), pool_dep2str(pool, req), pool_solvid2str(pool, p2));
 #endif
-	          addedge(od, p2, p, pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
+	          addedge(od, p2, p, pre == TYPE_PREREQ ? TYPE_PREREQ_UU : TYPE_REQ_UU);
 		}
 	    }
 	}
@@ -515,9 +558,25 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 	    }
 	}
     }
+  queue_free(&ignoreinst);
   queue_free(&depq);
 }
 
+static inline int
+scriptletedge(Pool *pool, struct orderdata *od, Id *cycle, int k)
+{
+  int deg = od->edgedata[cycle[k + 1] + 1];
+  if ((deg & TYPE_REQ_UU) || (deg & TYPE_PREREQ_UU))
+    {
+      /* the UU edges are reverse edges, so we have to check the next element for scripts */
+      if (havescripts(pool, od->tes[cycle[k + 2]].p, 0))
+	return 1;
+      deg &= ~(TYPE_REQ_UU | TYPE_PREREQ_UU);
+    }
+  if (deg && havescripts(pool, od->tes[cycle[k]].p, 0))
+    return 1;
+  return 0;
+}
 
 /* break an edge in a cycle */
 static void
@@ -533,23 +592,31 @@ breakcycle(struct orderdata *od, Id *cycle)
   for (k = 0; cycle[k + 1]; k += 2)
     {
       ddeg = od->edgedata[cycle[k + 1] + 1];
+      /* map UU to UI for the comparison */
+      if (ddeg & TYPE_REQ_UU)
+	{
+	  ddeg ^= TYPE_REQ_UU;
+	  ddeg |= TYPE_REQ_UI;
+	}
+      if (ddeg & TYPE_PREREQ_UU)
+	{
+	  ddeg ^= TYPE_PREREQ_UU;
+	  ddeg |= TYPE_PREREQ_UI;
+	}
       if (ddeg > ddegmax)
 	ddegmax = ddeg;
       if (!k || ddeg < ddegmin)
 	{
 	  l = k;
 	  ddegmin = ddeg;
-	  continue;
 	}
-      if (ddeg == ddegmin)
+      else if (ddeg == ddegmin)
 	{
-	  if (havescripts(pool, od->tes[cycle[l]].p) && !havescripts(pool, od->tes[cycle[k]].p))
+          if (scriptletedge(pool, od, cycle, l) && !scriptletedge(pool, od, cycle, k))
 	    {
 	      /* prefer k, as l comes from a package with contains scriptlets */
 	      l = k;
-	      continue;
 	    }
-	  /* same edge value, check for prereq */
 	}
     }
 
@@ -573,10 +640,11 @@ breakcycle(struct orderdata *od, Id *cycle)
   /* break that edge */
   od->edgedata[cycle[l + 1] + 1] |= TYPE_BROKEN;
 
-#if 1
-  if (ddegmin < TYPE_REQ)
+    
+  IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
+    ;
+  else if (ddegmin < TYPE_REQ)
     return;
-#endif
 
   /* cycle recorded, print it */
   if (ddegmin >= TYPE_REQ && (ddegmax & TYPE_PREREQ) != 0)
@@ -807,12 +875,7 @@ transaction_order(Transaction *trans, int flags)
   POOL_DEBUG(SOLV_DEBUG_STATS, "ordering transaction\n");
   /* free old data if present */
   if (trans->orderdata)
-    {
-      struct s_TransactionOrderdata *od = trans->orderdata;
-      od->tes = solv_free(od->tes);
-      od->invedgedata = solv_free(od->invedgedata);
-      trans->orderdata = solv_free(trans->orderdata);
-    }
+    transaction_free_orderdata(trans);
 
   /* create a transaction element for every active component */
   numte = 0;
@@ -837,6 +900,8 @@ transaction_order(Transaction *trans, int flags)
   od.edgedata[0] = 0;
   od.nedgedata = 1;
   queue_init(&od.cycles);
+  queue_init(&od.cyclesdata);
+  queue_init(&od.edgedataq);
 
   /* initialize TEs */
   for (i = 0, te = od.tes + 1; i < tr->count; i++)
@@ -974,6 +1039,14 @@ transaction_order(Transaction *trans, int flags)
 #if 0
   dump_tes(&od);
 #endif
+  if ((flags & SOLVER_TRANSACTION_KEEP_ORDEREDGES) != 0)
+    {
+      queue_insertn(&od.edgedataq, 0, od.nedgedata, od.edgedata);
+      queue_insertn(&od.edgedataq, 0, numte, 0);
+      for (i = 1, te = od.tes + i; i < numte; i++, te++)
+	od.edgedataq.elements[i] = te->edges + numte;
+    }
+
   /* all edges are finally set up and there are no cycles, now the easy part.
    * Create an ordered transaction */
   now = solv_timems(0);
@@ -1143,7 +1216,7 @@ printf("free %s [%d]\n", pool_solvid2str(pool, te2->p), temedianr[od.invedgedata
   POOL_DEBUG(SOLV_DEBUG_STATS, "creating new transaction took %d ms\n", solv_timems(now));
   POOL_DEBUG(SOLV_DEBUG_STATS, "transaction ordering took %d ms\n", solv_timems(start));
 
-  if ((flags & (SOLVER_TRANSACTION_KEEP_ORDERDATA | SOLVER_TRANSACTION_KEEP_ORDERCYCLES)) != 0)
+  if ((flags & (SOLVER_TRANSACTION_KEEP_ORDERDATA | SOLVER_TRANSACTION_KEEP_ORDERCYCLES | SOLVER_TRANSACTION_KEEP_ORDEREDGES)) != 0)
     {
       struct s_TransactionOrderdata *tod;
       trans->orderdata = tod = solv_calloc(1, sizeof(*trans->orderdata));
@@ -1158,7 +1231,7 @@ printf("free %s [%d]\n", pool_solvid2str(pool, te2->p), temedianr[od.invedgedata
 	  queue_insertn(cycles, cycles->count, od.cycles.count, od.cycles.elements);
 	  queue_push(cycles, od.cycles.count / 4);
 	}
-      if ((flags & SOLVER_TRANSACTION_KEEP_ORDERDATA) != 0)
+      if ((flags & (SOLVER_TRANSACTION_KEEP_ORDERDATA | SOLVER_TRANSACTION_KEEP_ORDEREDGES)) != 0)
 	{
 	  tod->tes = od.tes;
 	  tod->ntes = numte;
@@ -1167,10 +1240,16 @@ printf("free %s [%d]\n", pool_solvid2str(pool, te2->p), temedianr[od.invedgedata
 	  od.tes = 0;
 	  od.invedgedata = 0;
 	}
+      if ((flags & SOLVER_TRANSACTION_KEEP_ORDEREDGES) != 0)
+	{
+	  Queue *edgedataq = tod->edgedataq = solv_calloc(1, sizeof(Queue));
+	  queue_init_clone(edgedataq, &od.edgedataq);
+	}
     }
   solv_free(od.tes);
   solv_free(od.invedgedata);
   queue_free(&od.cycles);
+  queue_free(&od.edgedataq);
   queue_free(&od.cyclesdata);
 }
 
@@ -1375,7 +1454,7 @@ transaction_check_order(Transaction *trans)
 	lastins = p;
       if (s->repo != pool->installed)
 	MAPSET(&ins, p);
-      if (havescripts(pool, p))
+      if (havescripts(pool, p, 0))
 	{
 	  MAPZERO(&seen);
 	  transaction_check_pkg(trans, p, p, &ins, &seen, 1, lastins, 0);
@@ -1445,3 +1524,32 @@ transaction_order_get_cycle(Transaction *trans, Id cid, Queue *q)
   return severity;
 }
 
+void
+transaction_order_get_edges(Transaction *trans, Id p, Queue *q, int unbroken)
+{
+  struct s_TransactionOrderdata *od = trans->orderdata;
+  struct s_TransactionElement *te;
+  int i;
+  Queue *eq;
+
+  queue_empty(q);
+  if (!od || !od->edgedataq)
+    return;
+  for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
+    if (te->p == p)
+      break;
+  if (i == od->ntes)
+    return;
+  eq = od->edgedataq;
+  for (i = eq->elements[i]; eq->elements[i]; i += 2)
+    {
+      int type = eq->elements[i + 1];
+      if (unbroken)
+	{
+	  type &= ~(TYPE_BROKEN | TYPE_CYCLETAIL | TYPE_CYCLEHEAD);
+	  if (type == 0)
+	    continue;
+	}
+      queue_push2(q, od->tes[eq->elements[i]].p, type);
+    }
+}
diff --git a/src/repo_write.c b/src/repo_write.c
index b3a6bbc..a73eebf 100644
--- a/src/repo_write.c
+++ b/src/repo_write.c
@@ -1179,9 +1179,9 @@ repowriter_set_userdata(Repowriter *writer, const void *data, int len)
 {
   writer->userdata = solv_free(writer->userdata);
   writer->userdatalen = 0;
-  if (len < 0 || len >= 65536)
+  if (len <= 0)
     return;
-  writer->userdata = len ? solv_memdup(data, len) : 0;
+  writer->userdata = solv_memdup(data, len);
   writer->userdatalen = len;
 }
 
@@ -1249,6 +1249,9 @@ repowriter_write(Repowriter *writer, FILE *fp)
 
   Id type_constantid = 0;
 
+  /* sanity checks */
+  if (writer->userdatalen < 0 || writer->userdatalen >= 65536)
+    return pool_error(pool, -1, "illegal userdata length: %d", writer->userdatalen);
 
   memset(&cbdata, 0, sizeof(cbdata));
   cbdata.pool = pool;
diff --git a/src/rules.c b/src/rules.c
index a260c2d..2c56959 100644
--- a/src/rules.c
+++ b/src/rules.c
@@ -3255,6 +3255,12 @@ solver_rule2rules(Solver *solv, Id rid, Queue *q, int recursive)
 
 
 /* check if the newest versions of pi still provides the dependency we're looking for */
+/* pi: installed package
+ * r: rule for the dependency
+ * m: map with all positive elements of r
+ * return 0: at least one provider
+ * return 1: the newest versions do not provide the dependency
+ */
 static int
 solver_choicerulecheck(Solver *solv, Id pi, Rule *r, Map *m, Queue *q)
 {
@@ -3303,94 +3309,6 @@ solver_choicerulecheck(Solver *solv, Id pi, Rule *r, Map *m, Queue *q)
   return 1;	/* none of the new packages provided it */
 }
 
-static int
-solver_choicerulecheck2(Solver *solv, Id pi, Id pt, Queue *q)
-{
-  Pool *pool = solv->pool;
-  Rule *ur;
-  Id p, pp;
-  int i;
-
-  if (!q->count || q->elements[0] != pi)
-    {
-      if (q->count)
-        queue_empty(q);
-      ur = solv->rules + solv->updaterules + (pi - pool->installed->start);
-      if (!ur->p)
-        ur = solv->rules + solv->featurerules + (pi - pool->installed->start);
-      if (!ur->p)
-	return 1;		/* orphaned, thus newest */
-      queue_push2(q, pi, 0);
-      FOR_RULELITERALS(p, pp, ur)
-	if (p > 0 && p != pi)
-	  queue_push(q, p);
-      queue_push(q, pi);
-    }
-  if (q->count <= 3)
-    return q->count == 3 && q->elements[2] == pt ? 1 : 0;
-  if (!q->elements[1])
-    {
-      queue_deleten(q, 0, 2);
-      policy_filter_unwanted(solv, q, POLICY_MODE_CHOOSE);
-      queue_unshift(q, 1);	/* filter mark */
-      queue_unshift(q, pi);
-    }
-  for (i = 2; i < q->count; i++)
-    if (q->elements[i] == pt)
-      return 1;
-  return 0;	/* not newest */
-}
-
-static int
-solver_choicerulecheck3(Solver *solv, Id pt, Queue *q)
-{
-  Pool *pool = solv->pool;
-  Id p, pp;
-  int i;
-
-  if (!q->count || q->elements[0] != pt)
-    {
-      Solvable *s = pool->solvables + pt;
-      if (q->count)
-        queue_empty(q);
-      /* no installed package, so check all with same name */
-      queue_push2(q, pt, 0);
-      FOR_PROVIDES(p, pp, s->name)
-        if (pool->solvables[p].name == s->name && p != pt)
-          queue_push(q, p);
-      queue_push(q, pt);
-    }
-  if (q->count <= 3)
-    return q->count == 3 && q->elements[2] == pt ? 1 : 0;
-  if (!q->elements[1])
-    {
-      queue_deleten(q, 0, 2);
-      policy_filter_unwanted(solv, q, POLICY_MODE_CHOOSE);
-      queue_unshift(q, 1);	/* filter mark */
-      queue_unshift(q, pt);
-    }
-  for (i = 2; i < q->count; i++)
-    if (q->elements[i] == pt)
-      return 1;
-  return 0;	/* not newest */
-}
-
-static inline void
-queue_removeelement(Queue *q, Id el)
-{
-  int i, j;
-  for (i = 0; i < q->count; i++)
-    if (q->elements[i] == el)
-      break;
-  if (i < q->count)
-    {
-      for (j = i++; i < q->count; i++)
-	if (q->elements[i] != el)
-	  q->elements[j++] = q->elements[i];
-      queue_truncate(q, j);
-    }
-}
-
 static Id
 choicerule_find_installed(Pool *pool, Id p)
 {
@@ -3439,14 +3357,14 @@ solver_addchoicerules(Solver *solv)
   Pool *pool = solv->pool;
   Map m, mneg;
   Rule *r;
-  Queue q, qi, qcheck, qcheck2, infoq;
+  Queue q, qi, qcheck, infoq;
   int i, j, rid, havechoice, negcnt;
   Id p, d, pp, p2;
   Solvable *s;
   Id lastaddedp, lastaddedd;
   int lastaddedcnt;
   unsigned int now;
-  int isnewest = 0;
+  int isinstalled;
 
   solv->choicerules = solv->nrules;
   if (!pool->installed)
@@ -3458,7 +3376,6 @@ solver_addchoicerules(Solver *solv)
   queue_init(&q);
   queue_init(&qi);
   queue_init(&qcheck);
-  queue_init(&qcheck2);
   queue_init(&infoq);
   map_init(&m, pool->nsolvables);
   map_init(&mneg, pool->nsolvables);
@@ -3478,20 +3395,28 @@ solver_addchoicerules(Solver *solv)
       if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 <= 0))
 	continue;	/* only look at requires rules */
       /* solver_printrule(solv, SOLV_DEBUG_RESULT, r); */
-      queue_empty(&q);
       queue_empty(&qi);
       havechoice = 0;
+      isinstalled = 0;
       FOR_RULELITERALS(p, pp, r)
 	{
 	  if (p < 0)
-	    continue;
+	    {
+	      Solvable *s = pool->solvables - p;
+	      p2 = s->repo == pool->installed ? -p : 0;
+	      if (p2)
+		{
+		  if (!(solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, p2 - solv->installed->start))))
+		    isinstalled = 1;
+		}
+	      continue;
+	    }
 	  s = pool->solvables + p;
 	  if (!s->repo)
 	    continue;
 	  if (s->repo == pool->installed)
 	    {
 	      queue_push2(&qi, p, p);
-	      queue_push(&q, p);
 	      continue;
 	    }
 	  /* find an installed package p2 that we can update/downgrade to p */
@@ -3503,7 +3428,6 @@ solver_addchoicerules(Solver *solv)
 	      if (policy_is_illegal(solv, pool->solvables + p2, s, 0))
 		continue;
 	      queue_push2(&qi, p2, p);
-	      queue_push(&q, p);
 	      continue;
 	    }
 	  /* package p is independent of the installed ones */
@@ -3512,47 +3436,31 @@ solver_addchoicerules(Solver *solv)
 #if 0
       printf("havechoice: %d qcount %d qicount %d\n", havechoice, q.count, qi.count);
 #endif
-      if (!havechoice || !q.count || !qi.count)
+      if (!havechoice || !qi.count)
 	continue;	/* no choice */
 
       FOR_RULELITERALS(p, pp, r)
         if (p > 0)
 	  MAPSET(&m, p);
 
-      isnewest = 1;
-      FOR_RULELITERALS(p, pp, r)
-	{
-	  if (p > 0)
-	    break;
-	  p2 = choicerule_find_installed(pool, -p);
-	  if (p2 && !solver_choicerulecheck2(solv, p2, -p, &qcheck2))
-	    {
-	      isnewest = 0;
-	      break;
-	    }
-	  if (!p2 && !solver_choicerulecheck3(solv, -p, &qcheck2))
-	    {
-	      isnewest = 0;
-	      break;
-	    }
-	}
-      /* do extra checking */
-      for (i = j = 0; i < qi.count; i += 2)
+      if (!isinstalled)
 	{
-	  p2 = qi.elements[i];
-	  if (!p2)
-	    continue;
-	  if (isnewest && solver_choicerulecheck(solv, p2, r, &m, &qcheck))
+	  /* do extra checking for packages related to installed packages */
+	  for (i = j = 0; i < qi.count; i += 2)
 	    {
-	      /* oops, remove element p from q */
-	      queue_removeelement(&q, qi.elements[i + 1]);
-	      continue;
+	      p2 = qi.elements[i];
+	      if (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, p2 - solv->installed->start)))
+		{
+		  if (solver_choicerulecheck(solv, p2, r, &m, &qcheck))
+		    continue;
+		}
+	      qi.elements[j++] = p2;
+	      qi.elements[j++] = qi.elements[i + 1];
 	    }
-	  qi.elements[j++] = p2;
+	  queue_truncate(&qi, j);
 	}
-      queue_truncate(&qi, j);
 
-      if (!q.count || !qi.count)
+      if (!qi.count)
 	{
 	  FOR_RULELITERALS(p, pp, r)
 	    if (p > 0)
@@ -3560,6 +3468,15 @@ solver_addchoicerules(Solver *solv)
 	  continue;
 	}
 
+      queue_empty(&q);
+      /* split q from qi */
+      for (i = j = 0; i < qi.count; i += 2)
+	{
+	  queue_push(&q, qi.elements[i + 1]);
+	  qi.elements[j++] = qi.elements[i];
+	}
+      queue_truncate(&qi, j);
+
 
       /* now check the update rules of the installed package.
        * if all packages of the update rules are contained in
@@ -3579,6 +3496,7 @@ solver_addchoicerules(Solver *solv)
 	      break;
 	  if (p)
 	    break;
+	  /* speed improvement: only check each package once */
 	  for (j = i + 1; j < qi.count; j++)
 	    if (qi.elements[i] == qi.elements[j])
 	      qi.elements[j] = 0;
@@ -3636,7 +3554,6 @@ solver_addchoicerules(Solver *solv)
   queue_free(&q);
   queue_free(&qi);
   queue_free(&qcheck);
-  queue_free(&qcheck2);
   queue_free(&infoq);
   map_free(&m);
   map_free(&mneg);
diff --git a/src/solver.c b/src/solver.c
index 23285ff..28341d6 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -2620,6 +2620,43 @@ resolve_orphaned(Solver *solv, int level, int disablerules, Queue *dq, int *reru
   return level;
 }
 
+int
+solver_check_unneeded_choicerules(Solver *solv)
+{
+  Pool *pool = solv->pool;
+  Rule *r, *or;
+  Id p, pp, p2, pp2;
+  int i;
+  int havedisabled = 0;
+
+  /* check if some choice rules could have been broken */
+  for (i = solv->choicerules, r = solv->rules + i; i < solv->choicerules_end; i++, r++)
+    {
+      if (r->d < 0)
+	continue;
+      or = solv->rules + solv->choicerules_info[i - solv->choicerules];
+      if (or->d < 0)
+	continue;
+      FOR_RULELITERALS(p, pp, or)
+	{
+	  if (p < 0 || solv->decisionmap[p] <= 0)
+	    continue;
+	  FOR_RULELITERALS(p2, pp2, r)
+	    if (p2 == p)
+	      break;
+	  if (!p2)
+	    {
+	      /* did not find p in choice rule, disable it */
+	      POOL_DEBUG(SOLV_DEBUG_SOLVER, "disabling unneeded choice rule #%d\n", i);
+	      solver_disablechoicerules(solv, r);
+	      havedisabled = 1;
+	      break;
+	    }
+	}
+    }
+  return havedisabled;
+}
+
 /*-------------------------------------------------------------------
  *
  * solver_run_sat
@@ -2805,6 +2842,14 @@ solver_run_sat(Solver *solv, int disablerules, int doweak)
 	  continue;
 	}
 
+      if (solv->choicerules != solv->choicerules_end && solver_check_unneeded_choicerules(solv))
+	{
+	  POOL_DEBUG(SOLV_DEBUG_SOLVER, "did choice rule minimization, rerunning solver\n");
+	  solver_reset(solv);
+	  level = 0;	/* restart from scratch */
+	  continue;
+	}
+
       if (solv->solution_callback)
 	{
 	  solv->solution_callback(solv, solv->solution_callback_data);
diff --git a/src/transaction.h b/src/transaction.h
index 5b01354..001412d 100644
--- a/src/transaction.h
+++ b/src/transaction.h
@@ -86,6 +86,7 @@ typedef struct s_Transaction {
 /* order flags */
 #define SOLVER_TRANSACTION_KEEP_ORDERDATA	(1 << 0)
 #define SOLVER_TRANSACTION_KEEP_ORDERCYCLES	(1 << 1)
+#define SOLVER_TRANSACTION_KEEP_ORDEREDGES	(1 << 2)
 
 /* cycle severities */
 #define SOLVER_ORDERCYCLE_HARMLESS		0
@@ -137,6 +138,7 @@ extern void transaction_check_order(Transaction *trans);
 /* order cycle introspection */
 extern void transaction_order_get_cycleids(Transaction *trans, Queue *q, int minseverity);
 extern int transaction_order_get_cycle(Transaction *trans, Id cid, Queue *q);
+extern void transaction_order_get_edges(Transaction *trans, Id p, Queue *q, int unbroken);
 
 extern void transaction_free_orderdata(Transaction *trans);
 extern void transaction_clone_orderdata(Transaction *trans, Transaction *srctrans);
diff --git a/test/runtestcases.sh b/test/runtestcases.sh
index 3d73663..40f60db 100755
--- a/test/runtestcases.sh
+++ b/test/runtestcases.sh
@@ -1,15 +1,15 @@
 #!/bin/bash
 
 cmd=$1
-dir=$2
+dir=${2:-.}
 
 if test -z "$cmd" -o -z "$dir"; then
-  echo "Usage: runtestcases <cmd> <dir>";
+  echo "Usage: runtestcases <cmd> [dir]";
   exit 1
 fi
 
 ex=0
-for tc in $(find $dir -name \*.t) ; do
+for tc in $(find $dir -name \*.t | sort) ; do
   $cmd $tc >/dev/null
   tex=$?
   tcn="${tc#$dir/} .................................................."
diff --git a/test/testcases/choicerules/choice1.t b/test/testcases/choicerules/choice1.t
new file mode 100644
index 0000000..fbd5184
--- /dev/null
+++ b/test/testcases/choicerules/choice1.t
@@ -0,0 +1,27 @@
+#
+#Rule #2:
+#    !A-2-1.noarch [3] (w1)
+#    B-2-1.noarch [4] (w2)
+#    C-2-1.noarch [5]
+#
+# ==> Choice Rule
+#    !A-2-1.noarch [3] (w1)
+#    B-2-1.noarch [4] (w2)
+#
+repo system 0 testtags <inline>
+#>=Pkg: B 1 1 noarch
+#>=Prv: P = 1
+repo available 0 testtags <inline>
+#>=Pkg: A 2 1 noarch
+#>=Req: P = 2
+#>=Pkg: B 2 1 noarch
+#>=Prv: P = 2
+#>=Pkg: C 2 1 noarch
+#>=Prv: P = 2
+system i686 rpm system
+
+job install name A
+result transaction,problems <inline>
+result transaction,problems <inline>
+#>install A-2-1.noarch@available
+#>upgrade B-1-1.noarch@system B-2-1.noarch@available
diff --git a/test/testcases/choicerules/choice1b.t b/test/testcases/choicerules/choice1b.t
new file mode 100644
index 0000000..cf6051c
--- /dev/null
+++ b/test/testcases/choicerules/choice1b.t
@@ -0,0 +1,19 @@
+feature complex_deps
+repo system 0 testtags <inline>
+#>=Pkg: B 1 1 noarch
+#>=Prv: P = 1
+repo available 0 testtags <inline>
+#>=Pkg: X 1 1 noarch
+#>=Pkg: Y 1 1 noarch
+#>=Pkg: A 2 1 noarch
+#>=Req: P = 2 <IF> (X & Y)
+#>=Pkg: B 2 1 noarch
+#>=Prv: P = 2
+#>=Pkg: C 2 1 noarch
+#>=Prv: P = 2
+system i686 rpm system
+
+job install name A
+result transaction,problems <inline>
+result transaction,problems <inline>
+#>install A-2-1.noarch@available
diff --git a/test/testcases/choicerules/choice2.t b/test/testcases/choicerules/choice2.t
index 7c78fc6..1eb6c7c 100644
--- a/test/testcases/choicerules/choice2.t
+++ b/test/testcases/choicerules/choice2.t
@@ -1,3 +1,24 @@
+#
+# Test that updating package B will update package A
+# instead of pulling in new package C
+#
+#Rule #5:
+#    !A-2-2.noarch [5] (w1)
+#    B-2-1.noarch [6] (w2)
+#    C-2-1.noarch [8]
+#Rule #7:
+#    !A-2-1.noarch [4] (w1)
+#    B-2-1.noarch [6] (w2)
+#    C-2-1.noarch [8]
+#Rule #8:
+#    !A-1-1.noarch [2]I (w1)
+#    B-1-1.noarch [3]I (w2)
+#    C-1-1.noarch [7]
+#
+# ==> Choice Rule for #8:
+#    !A-1-1.noarch [2]I (w1)
+#    B-1-1.noarch [3]I (w2)
+#
 repo system 0 testtags <inline>
 #>=Pkg: A 1 1 noarch
 #>=Req: P = 1
@@ -18,6 +39,5 @@ system i686 rpm system
 
 job update name B
 result transaction,problems <inline>
-result transaction,problems <inline>
 #>upgrade A-1-1.noarch@system A-2-2.noarch@available
 #>upgrade B-1-1.noarch@system B-2-1.noarch@available
diff --git a/test/testcases/choicerules/choice2b.t b/test/testcases/choicerules/choice2b.t
new file mode 100644
index 0000000..ae619f7
--- /dev/null
+++ b/test/testcases/choicerules/choice2b.t
@@ -0,0 +1,47 @@
+#
+# Test that updating package B will update package A
+# instead of pulling in new package C
+#
+#Rule #5:
+#    !A-2-2.noarch [5] (w1)
+#    B-2-1.noarch [6] (w2)
+#    C-2-1.noarch [8]
+#Rule #7:
+#    !A-2-1.noarch [4] (w1)
+#    B-2-1.noarch [6] (w2)
+#    C-2-1.noarch [8]
+#Rule #8:
+#    !A-1-1.noarch [2]I (w1)
+#    B-1-1.noarch [3]I (w2)
+#    C-1-1.noarch [7]
+#
+# ==> Choice Rule for #8:
+#    !A-1-1.noarch [2]I (w1)
+#    B-1-1.noarch [3]I (w2)
+#
+repo system 0 testtags <inline>
+#>=Pkg: A 1 1 noarch
+#>=Req: P = 1
+#>=Pkg: B 1 1 noarch
+#>=Prv: P = 1
+repo available 0 testtags <inline>
+#>=Pkg: A 1 1 noarch
+#>=Req: P = 1
+#>=Pkg: B 1 1 noarch
+#>=Prv: P = 1
+#>=Pkg: A 2 1 noarch
+#>=Req: P = 2
+#>=Pkg: A 2 2 noarch
+#>=Req: P = 2
+#>=Pkg: B 2 1 noarch
+#>=Prv: P = 2
+#>=Pkg: C 1 1 noarch
+#>=Prv: P = 1
+#>=Pkg: C 2 1 noarch
+#>=Prv: P = 2
+system i686 rpm system
+
+job update name B
+result transaction,problems <inline>
+#>upgrade A-1-1.noarch@system A-2-2.noarch@available
+#>upgrade B-1-1.noarch@system B-2-1.noarch@available
diff --git a/test/testcases/choicerules/choice3.t b/test/testcases/choicerules/choice3.t
index d5d41ac..1b82e69 100644
--- a/test/testcases/choicerules/choice3.t
+++ b/test/testcases/choicerules/choice3.t
@@ -1,3 +1,19 @@
+# Do not block an update because of a choice rule
+#
+#Rule #3:
+#    !B-1-1.noarch [4] (w1)
+#    A-1-1.noarch [2]I (w2)
+#    Anew-2-1.noarch [6]
+#Rule #4:
+#    !B-1-1.noarch [3]I (w1)
+#    A-1-1.noarch [2]I (w2)
+#    Anew-2-1.noarch [6]
+#
+# ==> No choice rule for Rule#4!
+# ==> Choice Rule for #3:
+#    !B-1-1.noarch [4] (w1)
+#    A-1-1.noarch [2]I (w2)
+#
 repo system 0 testtags <inline>
 #>=Pkg: A 1 1 noarch
 #>=Prv: libA
diff --git a/test/testcases/choicerules/choice3b.t b/test/testcases/choicerules/choice3b.t
new file mode 100644
index 0000000..fb9c725
--- /dev/null
+++ b/test/testcases/choicerules/choice3b.t
@@ -0,0 +1,31 @@
+# Do not block an update because of a choice rule
+#
+#Rule #3:
+#    !B-1-1.noarch [4] (w1)
+#    A-1-1.noarch [2]I (w2)
+#    Anew-2-1.noarch [6]
+#Rule #4:
+#    !B-1-1.noarch [3]I (w1)
+#    A-1-1.noarch [2]I (w2)
+#    Anew-2-1.noarch [6]
+#
+# ==> No choice rule for Rule#4!
+# ==> Choice Rule for #3:
+#    !B-1-1.noarch [4] (w1)
+#    A-1-1.noarch [2]I (w2)
+#
+repo system 0 testtags <inline>
+#>=Pkg: A 1 1 noarch
+#>=Prv: libA
+#>=Pkg: B 1 1 noarch
+#>=Req: libA
+repo available 0 testtags <inline>
+#>=Pkg: A 2 1 noarch
+#>=Pkg: Anew 2 1 noarch
+#>=Prv: libA
+system i686 rpm system
+
+job update all packages
+result transaction,problems <inline>
+#>install Anew-2-1.noarch@available
+#>upgrade A-1-1.noarch@system A-2-1.noarch@available
diff --git a/test/testcases/choicerules/choice4.t b/test/testcases/choicerules/choice4.t
index 1bf9f48..7378a56 100644
--- a/test/testcases/choicerules/choice4.t
+++ b/test/testcases/choicerules/choice4.t
@@ -1,3 +1,21 @@
+# This tests that A is updated instead of Anew being installed
+#
+#Rule #4:
+#    !B-2-2.noarch [11] (w1)
+#    A-2-2.noarch [9] (w2)
+#    Anew-2-2.noarch [10]
+#Rule #11:
+#    !B-2-1.noarch [8] (w1)
+#    A-2-1.noarch [6] (w2)
+#    Anew-2-1.noarch [7]
+#
+#Choice Rule for #4:
+#    !B-2-2.noarch [11] (w1)
+#    A-2-2.noarch [9] (w2)
+#Choice Rule for #11
+#    !B-2-1.noarch [8] (w1)
+#    A-2-1.noarch [6] (w2)
+#
 repo system 0 testtags <inline>
 #>=Pkg: A 1 1 noarch
 #>=Prv: libA = 1-1
diff --git a/test/testcases/choicerules/choice5.t b/test/testcases/choicerules/choice5.t
new file mode 100644
index 0000000..9f43c8a
--- /dev/null
+++ b/test/testcases/choicerules/choice5.t
@@ -0,0 +1,21 @@
+#
+# test that a package split does not update unrelated packages
+#
+repo system 0 testtags <inline>
+#>=Pkg: A 1 1 noarch
+#>=Prv: libA
+#>=Pkg: B 1 1 noarch
+#>=Req: libA
+repo available 0 testtags <inline>
+#>=Pkg: A 1 1 noarch
+#>=Prv: libA
+#>=Pkg: A 2 1 noarch
+#>=Pkg: Asplit 2 1 noarch
+#>=Prv: libA
+#>=Pkg: B 2 1 noarch
+#>=Req: libA
+system i686 rpm system
+job update name A
+result transaction,problems <inline>
+#>install Asplit-2-1.noarch@available
+#>upgrade A-1-1.noarch@system A-2-1.noarch@available
diff --git a/test/testcases/choicerules/choice6.t b/test/testcases/choicerules/choice6.t
new file mode 100644
index 0000000..e860ae2
--- /dev/null
+++ b/test/testcases/choicerules/choice6.t
@@ -0,0 +1,28 @@
+#Rule #4:
+#    !php-fpm-7.2.24-1.noarch [5] (w1)
+#    glibc-2.17-325.noarch [2]I (w2)
+#    libcrypt-4.1.1-6.noarch [7]
+#=> no choice rule for #4
+#
+repo @System 0 testtags <inline>
+#>=Pkg: glibc 2.17 325 noarch
+#>=Prv: libcrypt
+#>=Pkg: php 5.4.16 48 noarch
+repo available 0 testtags <inline>
+#>=Pkg: php 7.2.24 1 noarch
+#>=Rec: php-fpm = 7.2.24-1
+#>=Pkg: php-fpm 7.2.24 1 noarch
+#>=Req: libcrypt
+#>=Pkg: php-fpm 8.0.13 2 noarch
+#>=Req: libcrypt
+#>=Pkg: libcrypt 4.1.1 6 noarch
+#>=Req: libc
+#>=Pkg: glibc 2.28 181 noarch
+#>=Prv: libc
+system i686 rpm @System
+job update all packages
+result transaction,problems <inline>
+#>install libcrypt-4.1.1-6.noarch@available
+#>install php-fpm-7.2.24-1.noarch@available
+#>upgrade glibc-2.17-325.noarch@@System glibc-2.28-181.noarch@available
+#>upgrade php-5.4.16-48.noarch@@System php-7.2.24-1.noarch@available