openpgp: Change KeyHandle's PartialOrd and PartialEq implementations.

  - The current PartialOrd and PartialEq implementations for
    KeyHandles considers KeyIDs and Fingerprints to not be equal.
    Since most users of this interface expect key identifiers to be
    interchangeable, this means that they have to pull KeyHandles
    apart when comparing them, like this:

      match (a, b) {
          (KeyHandle::Fingerprint(a),
           KeyHandle::Fingerprint(b)) => a == b,
          (KeyHandle::Fingerprint(a),
           KeyHandle::KeyID(b)) => a.keyid() == b,
          ...
      }

    This is unergonomic, and easy to forget to do.

  - The obvious fix would be to change the PartialOrd and PartialEq
    implementations to do this for the user.  Unfortunately, this is
    not possible, because they must be transitive and two
    fingerprints (a and b) maybe different but have the same keyid.
    That is, the following is possible:

      a == keyid, b == keyid, but a != b

    That makes this comparison function non-transitive and
    inappropriate for the PartialOrd and PartialEq traits.

  - Nevertheless, we can implement PartialOrd and PartialEq and return
    None when a keyid and a fingerprint match.  (A consequence of this
    is that KeyHandle can no longer implement Eq or Ord.)  This
    prevents users of this interface from naively comparing
    KeyHandles.

  - Using this interface, we provide the desired, non-transitive,
    comparison function via a method (KeyHandle::aliases).

  - This change means that a `KeyHandle` can no longer be used as a
    Key in a HashMap.  In these cases, we instead use a vector.

  - Fixes #412.

4 files changed, 146 insertions, 35 deletions

diff --git a/openpgp/src/keyhandle.rs b/openpgp/src/keyhandle.rs
index 18de1566..fafbe36b 100644
--- a/openpgp/src/keyhandle.rs
+++ b/openpgp/src/keyhandle.rs
@@ -1,4 +1,7 @@
 use std::convert::TryFrom;
+use std::cmp;
+use std::cmp::Ordering;
+use std::borrow::Borrow;
 
 use crate::{
     Error,
@@ -10,7 +13,7 @@ use crate::{
 /// Identifies OpenPGP keys.
 ///
 /// An `KeyHandle` is either a `Fingerprint` or a `KeyID`.
-#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Hash)]
+#[derive(Debug, Clone, Hash)]
 pub enum KeyHandle {
     /// A Fingerprint.
     Fingerprint(Fingerprint),
@@ -58,3 +61,111 @@ impl TryFrom<KeyHandle> for Fingerprint {
         }
     }
 }
+
+impl PartialOrd for KeyHandle {
+    fn partial_cmp(&self, other: &KeyHandle) -> Option<Ordering> {
+        let a = self.as_slice();
+        let b = other.as_slice();
+
+        let l = cmp::min(a.len(), b.len());
+
+        // Do a little endian comparison so that for v4 keys (where
+        // the KeyID is a suffix of the Fingerprint) equivalent KeyIDs
+        // and Fingerprints sort next to each other.
+        for (a, b) in a[a.len()-l..].iter().zip(b[b.len()-l..].iter()) {
+            let cmp = a.cmp(b);
+            if cmp != Ordering::Equal {
+                return Some(cmp);
+            }
+        }
+
+        if a.len() == b.len() {
+            Some(Ordering::Equal)
+        } else {
+            // One (a KeyID) is the suffix of the other (a
+            // Fingerprint).
+            None
+        }
+    }
+}
+
+impl PartialEq for KeyHandle {
+    fn eq(&self, other: &Self) -> bool {
+        self.partial_cmp(other) == Some(Ordering::Equal)
+    }
+}
+
+impl KeyHandle {
+    /// Returns a reference to the raw identifier.
+    pub fn as_slice(&self) -> &[u8] {
+        match self {
+            KeyHandle::Fingerprint(i) => i.as_slice(),
+            KeyHandle::KeyID(i) => i.as_slice(),
+        }
+    }
+
+    /// Returns whether `self` and `other` could be aliases of each other.
+    ///
+    /// `KeyHandle`'s `PartialEq` implementation cannot assert that a
+    /// `Fingerprint` and a `KeyID` are equal, because distinct
+    /// fingerprints may have the same `KeyID`, and `PartialEq` must
+    /// be [transitive], i.e.,
+    ///
+    /// ```text
+    /// a == b and b == c implies a == c.
+    /// ```
+    ///
+    /// [transitive]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
+    ///
+    /// That is, if `fpr1` and `fpr2` are distinct fingerprints with the
+    /// same key ID then:
+    ///
+    /// ```text
+    /// fpr1 == keyid and fpr2 == keyid, but fpr1 != fpr2.
+    /// ```
+    ///
+    /// In these cases (and only these cases) `KeyHandle`'s
+    /// `PartialOrd` implementation returns `None` to correctly
+    /// indicate that a comparison is not possible.
+    ///
+    /// This definition of equality makes searching for a given
+    /// `KeyHandle` using `PartialEq` awkward.  This function fills
+    /// that gap.  It answers the question: given two `KeyHandles`,
+    /// could they be aliases?  That is, it implements the desired,
+    /// non-transitive equality relation:
+    ///
+    /// ```
+    /// # extern crate sequoia_openpgp as openpgp;
+    /// # use openpgp::Fingerprint;
+    /// # use openpgp::KeyID;
+    /// # use openpgp::KeyHandle;
+    /// #
+    /// # let fpr1 : KeyHandle
+    /// #     = Fingerprint::from_hex(
+    /// #           "8F17 7771 18A3 3DDA 9BA4  8E62 AACB 3243 6300 52D9")
+    /// #       .unwrap().into();
+    /// #
+    /// # let fpr2 : KeyHandle
+    /// #     = Fingerprint::from_hex(
+    /// #           "0123 4567 8901 2345 6789  0123 AACB 3243 6300 52D9")
+    /// #       .unwrap().into();
+    /// #
+    /// # let keyid : KeyHandle = KeyID::from_hex("AACB 3243 6300 52D9")
+    /// #     .unwrap().into();
+    /// #
+    /// // fpr1 and fpr2 are different fingerprints with the same KeyID.
+    /// assert!(! fpr1.eq(&fpr2));
+    /// assert!(fpr1.aliases(&keyid));
+    /// assert!(fpr2.aliases(&keyid));
+    /// assert!(! fpr1.aliases(&fpr2));
+    /// ```
+    pub fn aliases<H>(&self, other: H) -> bool
+        where H: Borrow<KeyHandle>
+    {
+        // This works, because the PartialOrd implementation only
+        // returns None if one value is a fingerprint and the other is
+        // a key id that matches the fingerprint's key id.
+        self.partial_cmp(other.borrow()).unwrap_or(Ordering::Equal)
+            == Ordering::Equal
+    }
+}
diff --git a/openpgp/src/packet/signature/mod.rs b/openpgp/src/packet/signature/mod.rs
index 17810bbc..77f4a3f5 100644
--- a/openpgp/src/packet/signature/mod.rs
+++ b/openpgp/src/packet/signature/mod.rs
@@ -524,7 +524,7 @@ impl Signature4 {
     ///
     /// A signature can contain multiple hints as to who issued the
     /// signature.
-    pub fn get_issuers(&self) -> std::collections::HashSet<crate::KeyHandle> {
+    pub fn get_issuers(&self) -> Vec<crate::KeyHandle> {
         use crate::packet::signature::subpacket:: SubpacketValue;
 
         self.hashed_area().iter()
diff --git a/openpgp/src/parse/stream.rs b/openpgp/src/parse/stream.rs
index 43ce0ad2..fd278e16 100644
--- a/openpgp/src/parse/stream.rs
+++ b/openpgp/src/parse/stream.rs
@@ -11,7 +11,6 @@
 
 use std::cmp;
 use std::convert::TryFrom;
-use std::collections::HashMap;
 use std::io::{self, Read};
 use std::path::Path;
 use std::time;
@@ -124,7 +123,7 @@ pub struct Verifier<'a, H: VerificationHelper> {
     helper: H,
     certs: Vec<Cert>,
     /// Maps KeyID to certs[i].keys_all().nth(j).
-    keys: HashMap<crate::KeyHandle, (usize, usize)>,
+    keys: Vec<(crate::KeyHandle, (usize, usize))>,
     oppr: Option<PacketParserResult<'a>>,
     structure: IMessageStructure,
 
@@ -577,7 +576,7 @@ impl<'a, H: VerificationHelper> Verifier<'a, H> {
         let mut v = Verifier {
             helper: helper,
             certs: Vec::new(),
-            keys: HashMap::new(),
+            keys: Vec::new(),
             oppr: None,
             structure: IMessageStructure::new(),
             reserve: None,
@@ -608,18 +607,16 @@ impl<'a, H: VerificationHelper> Verifier<'a, H> {
                         if for_signing(cert.primary(),
                                        cert.primary_key_signature(None),
                                        time, tolerance) {
-                            v.keys.insert(cert.fingerprint().into(), (i, 0));
-                            v.keys.insert(cert.keyid().into(), (i, 0));
+                            v.keys.push((cert.fingerprint().into(),
+                                         (i, 0)));
                         }
 
                         for (j, skb) in cert.subkeys().enumerate() {
                             let key = skb.key();
                             if for_signing(key, skb.binding_signature(None),
                                            time, tolerance) {
-                                v.keys.insert(key.fingerprint().into(),
-                                              (i, j + 1));
-                                v.keys.insert(key.keyid().into(),
-                                              (i, j + 1));
+                                v.keys.push((key.fingerprint().into(),
+                                             (i, j + 1)));
                             }
                         }
                     }
@@ -693,7 +690,9 @@ impl<'a, H: VerificationHelper> Verifier<'a, H> {
                     results.new_signature_group();
                     'sigs: for sig in sigs.into_iter() {
                         for issuer in sig.get_issuers() {
-                            if let Some((i, j)) = self.keys.get(&issuer) {
+                            if let Some((_, (i, j))) = self.keys.iter().find(|(h, _)| {
+                                h.aliases(&issuer)
+                            }) {
                                 let cert = &self.certs[*i];
                                 let ka = cert.keys().policy(self.time).nth(*j).unwrap();
                                 results.push_verification_result(
@@ -1222,7 +1221,7 @@ pub struct Decryptor<'a, H: VerificationHelper + DecryptionHelper> {
     helper: H,
     certs: Vec<Cert>,
     /// Maps KeyID to certs[i].keys_all().nth(j).
-    keys: HashMap<crate::KeyHandle, (usize, usize)>,
+    keys: Vec<(crate::KeyHandle, (usize, usize))>,
     oppr: Option<PacketParserResult<'a>>,
     identity: Option<Fingerprint>,
     structure: IMessageStructure,
@@ -1361,7 +1360,7 @@ impl<'a, H: VerificationHelper + DecryptionHelper> Decryptor<'a, H> {
         let mut v = Decryptor {
             helper: helper,
             certs: Vec::new(),
-            keys: HashMap::new(),
+            keys: vec![],
             oppr: None,
             identity: None,
             structure: IMessageStructure::new(),
@@ -1446,17 +1445,15 @@ impl<'a, H: VerificationHelper + DecryptionHelper> Decryptor<'a, H> {
 
                         if for_signing(cert.primary().into(),
                                     cert.primary_key_signature(None)) {
-                            v.keys.insert(cert.fingerprint().into(), (i, 0));
-                            v.keys.insert(cert.keyid().into(), (i, 0));
+                            v.keys.push((cert.fingerprint().into(),
+                                         (i, 0)));
                         }
 
                         for (j, skb) in cert.subkeys().enumerate() {
                             let key = skb.key();
                             if for_signing(key.into(), skb.binding_signature(None)) {
-                                v.keys.insert(key.fingerprint().into(),
-                                              (i, j + 1));
-                                v.keys.insert(key.keyid().into(),
-                                              (i, j + 1));
+                                v.keys.push((key.fingerprint().into(),
+                                             (i, j + 1)));
                             }
                         }
                     }
@@ -1585,7 +1582,9 @@ impl<'a, H: VerificationHelper + DecryptionHelper> Decryptor<'a, H> {
                     results.new_signature_group();
                     'sigs: for sig in sigs.into_iter() {
                         for issuer in sig.get_issuers() {
-                            if let Some((i, j)) = self.keys.get(&issuer) {
+                            if let Some((_, (i, j))) = self.keys.iter().find(|(h, _)| {
+                                h.aliases(&issuer)
+                            }) {
                                 let cert = &self.certs[*i];
                                 let ka = cert.keys().policy(self.time).nth(*j).unwrap();
                                 results.push_verification_result(
diff --git a/sqv/src/sqv.rs b/sqv/src/sqv.rs
index fec3e1ff..380b52f4 100644
--- a/sqv/src/sqv.rs
+++ b/sqv/src/sqv.rs
@@ -159,7 +159,7 @@ fn real_main() -> Result<(), failure::Error> {
     }
 
     // Find the certs.
-    let mut certs: HashMap<KeyHandle, Rc<RefCell<Cert>>> = HashMap::new();
+    let mut certs: Vec<(KeyHandle, Rc<RefCell<Cert>>)> = Vec::new();
     for filename in matches.values_of_os("keyring")
         .expect("No keyring specified.")
     {
@@ -187,19 +187,19 @@ fn real_main() -> Result<(), failure::Error> {
             for (_, issuer) in sigs.iter() {
                 if cert_has_key(&cert, issuer) {
                     let fp: KeyHandle = cert.fingerprint().into();
-                    let id = KeyHandle::KeyID(fp.clone().into());
-
-                    let cert = if let Some(known) = certs.get(&fp) {
+                    let cert = if let Some(known) = certs.iter().position(|(h, _)| {
+                        h.aliases(&fp)
+                    }) {
                         if trace {
                             eprintln!("Found key {} again.  Merging.",
                                       fp);
                         }
 
                         // XXX: Use RefCell::replace_with once stabilized.
-                        let k = known.borrow().clone();
-                        known.replace(k.merge(cert)?);
+                        let k = certs[known].1.borrow().clone();
+                        certs[known].1.replace(k.merge(cert)?);
 
-                        known.clone()
+                        certs[known].1.clone()
                     } else {
                         if trace {
                             eprintln!("Found key {}.", issuer);
@@ -208,13 +208,10 @@ fn real_main() -> Result<(), failure::Error> {
                         Rc::new(RefCell::new(cert))
                     };
 
-                    certs.insert(fp, cert.clone());
-                    certs.insert(id, cert.clone());
+                    certs.push((fp, cert.clone()));
                     for c in cert.borrow().subkeys() {
                         let fp: KeyHandle = c.key().fingerprint().into();
-                        let id = KeyHandle::KeyID(fp.clone().into());
-                        certs.insert(fp, cert.clone());
-                        certs.insert(id, cert.clone());
+                        certs.push((fp, cert.clone()));
                     }
                     break;
                 }
@@ -226,11 +223,15 @@ fn real_main() -> Result<(), failure::Error> {
     let mut sigs_seen_from_cert = HashSet::new();
     let mut good = 0;
     'sig_loop: for (sig, issuer) in sigs.into_iter() {
+        let issuer : KeyHandle = issuer.into();
+
         if trace {
             eprintln!("Checking signature allegedly issued by {}.", issuer);
         }
 
-        if let Some(cert) = certs.get(&issuer.clone().into()) {
+        if let Some((_, cert)) = certs.iter().find(|(h, _)| {
+            h.aliases(&issuer)
+        }) {
             let cert = cert.borrow();
             // Find the right key.
             for ka in cert.keys().policy(None) {
@@ -241,7 +242,7 @@ fn real_main() -> Result<(), failure::Error> {
                 };
                 let key = ka.key();
 
-                if issuer == key.keyid() {
+                if issuer.aliases(&key.fingerprint().into()) {
                     if !binding.key_flags().for_signing() {
                         eprintln!("Cannot check signature, key has no signing \
                                    capability");