openpgp: De-duplicate cert components before checking signatures.

  - Before we do anything, we'll order and deduplicate the components.
    If two components are the same, they will be merged, and their
    signatures will also be deduplicated.  This improves the
    performance considerably when we update a certificate, because the
    certificates will be most likely almost identical, and we avoid
    about half of the signature verifications.

  - And indeed, benchmarking shows a 45% performance improvement on a
    typical cert.

  - Fixes #644.

3 files changed, 73 insertions, 31 deletions

diff --git a/openpgp/benches/merge_cert.rs b/openpgp/benches/merge_cert.rs
new file mode 100644
index 00000000..a628e60a
--- /dev/null
+++ b/openpgp/benches/merge_cert.rs
@@ -0,0 +1,20 @@
+use criterion::{
+    criterion_group, Criterion,
+};
+
+use sequoia_openpgp as openpgp;
+use openpgp::cert::Cert;
+use openpgp::parse::Parse;
+
+/// Benchmark merging a typical cert with itself.
+fn bench_merge_certs(c: &mut Criterion) {
+    let mut group = c.benchmark_group("merge cert with itself");
+    let neal = Cert::from_bytes(include_bytes!("../tests/data/keys/neal.pgp"))
+        .unwrap();
+    group.bench_function("neal.pgp", |b| b.iter(|| {
+        neal.clone().merge_public(neal.clone()).unwrap();
+    }));
+    group.finish();
+}
+
+criterion_group!(benches, bench_merge_certs);
diff --git a/openpgp/benches/run_benchmarks.rs b/openpgp/benches/run_benchmarks.rs
index fc872af7..f5210747 100644
--- a/openpgp/benches/run_benchmarks.rs
+++ b/openpgp/benches/run_benchmarks.rs
@@ -18,6 +18,8 @@ mod generate_cert;
 use generate_cert::benches as generate_cert;
 mod parse_cert;
 use parse_cert::benches as parse_cert;
+mod merge_cert;
+use merge_cert::benches as merge_cert;
 
 // Add all benchmark functions here
 criterion_main!(
@@ -28,5 +30,6 @@ criterion_main!(
     encrypt,
     decrypt,
     generate_cert,
-    parse_cert
+    parse_cert,
+    merge_cert,
 );
diff --git a/openpgp/src/cert.rs b/openpgp/src/cert.rs
index adb201f9..64b16bf7 100644
--- a/openpgp/src/cert.rs
+++ b/openpgp/src/cert.rs
@@ -1461,12 +1461,52 @@ impl Cert {
         self.into()
     }
 
+    /// Sorts and deduplicates all components and all signatures of
+    /// all components.
+    fn sort_and_dedup(&mut self) {
+        self.primary.sort_and_dedup();
+
+        self.bad.sort_by(Signature::normalized_cmp);
+        self.bad.dedup_by(|a, b| a.normalized_eq(b));
+        // Order bad signatures so that the most recent one comes
+        // first.
+        self.bad.sort_by(sig_cmp);
+
+        self.userids.sort_and_dedup(UserID::cmp, |_, _| {});
+        self.user_attributes.sort_and_dedup(UserAttribute::cmp, |_, _| {});
+        // XXX: If we have two keys with the same public parts and
+        // different non-empty secret parts, then one will be dropped
+        // (non-deterministicly)!
+        //
+        // This can happen if:
+        //
+        //   - One is corrupted
+        //   - There are two versions that are encrypted differently
+        self.subkeys.sort_and_dedup(Key::public_cmp,
+            |a, b| {
+                // Recall: if a and b are equal, a will be dropped.
+                if ! b.has_secret() && a.has_secret() {
+                    std::mem::swap(a, b);
+                }
+            });
+
+        self.unknowns.sort_and_dedup(Unknown::best_effort_cmp, |_, _| {});
+    }
+
     fn canonicalize(mut self) -> Self {
         tracer!(TRACE, "canonicalize", 0);
 
-        // The very first thing that we do is verify the
-        // self signatures.  There are a few things that we need to be
-        // aware of:
+        // Before we do anything, we'll order and deduplicate the
+        // components.  If two components are the same, they will be
+        // merged, and their signatures will also be deduplicated.
+        // This improves the performance considerably when we update a
+        // certificate, because the certificates will be most likely
+        // almost identical, and we avoid about half of the signature
+        // verifications.
+        self.sort_and_dedup();
+
+        // Now we verify the self signatures.  There are a few things
+        // that we need to be aware of:
         //
         //  - Signatures may be invalid.  These should be dropped.
         //
@@ -1968,38 +2008,17 @@ impl Cert {
                self.keyid(), self.bad.len());
         }
 
-        self.primary.sort_and_dedup();
-
-        self.bad.sort_by(Signature::normalized_cmp);
-        self.bad.dedup_by(|a, b| a.normalized_eq(b));
-        // Order bad signatures so that the most recent one comes
-        // first.
-        self.bad.sort_by(sig_cmp);
-
-        self.userids.sort_and_dedup(UserID::cmp, |_, _| {});
-        self.user_attributes.sort_and_dedup(UserAttribute::cmp, |_, _| {});
-        // XXX: If we have two keys with the same public parts and
-        // different non-empty secret parts, then one will be dropped
-        // (non-deterministicly)!
-        //
-        // This can happen if:
-        //
-        //   - One is corrupted
-        //   - There are two versions that are encrypted differently
-        self.subkeys.sort_and_dedup(Key::public_cmp,
-            |a, b| {
-                // Recall: if a and b are equal, a will be dropped.
-                if ! b.has_secret() && a.has_secret() {
-                    std::mem::swap(a, b);
-                }
-            });
-
+        // Split signatures on unknown components.
         let primary_fp: KeyHandle = self.key_handle();
         let primary_keyid = KeyHandle::KeyID(primary_fp.clone().into());
         for c in self.unknowns.iter_mut() {
             parser::split_sigs(&primary_fp, &primary_keyid, c);
         }
-        self.unknowns.sort_and_dedup(Unknown::best_effort_cmp, |_, _| {});
+
+        // Sort again.  We may have moved signatures to the right
+        // component, and we need to ensure they are in the right spot
+        // (i.e. newest first).
+        self.sort_and_dedup();
 
         // XXX: Check if the sigs in other_sigs issuer are actually
         // designated revokers for this key (listed in a "Revocation