openpgp: Rework KeyAmalgamation to preserve the key's role.

  - Introduce three KeyAmalgamation variants:
    `PrimaryKeyAmalgamation`, `SubordinateKeyAmalgamation`, and
    `ErasedKeyAmalgamation`.

  - Unlike a `Key` or a `KeyBundle` with an `UnspecifiedRole`, an
    `ErasedKeyAmalgamation` remembers its role.  This means that an
    `ErasedKeyAmalgamation` can implement the correct semantics even
    though the role marker has been erased (hence the name).

  - Have `Cert::keys` return `ErasedKeyAmalgamation`s.  Recall:
    `Cert::keys` can't return a more specific type, because it returns
    an iterator that can contain both primary and subordinate keys.

    - We use a concrete type instead of a trait object so that when
      the user converts a `KeyAmalgamation` to a
      `ValidKeyAmalgamation` (via `with_policy`), the
      `ValidKeyAmalgamation` retains the type information about the
      `KeyAmalgamation`'s role.

    - Preserving this type information increases type safety for users
      of this API.

11 files changed, 749 insertions, 475 deletions

diff --git a/examples/guide-exploring-openpgp.rs b/examples/guide-exploring-openpgp.rs
index 2263dfe0..298fcd6c 100644
--- a/examples/guide-exploring-openpgp.rs
+++ b/examples/guide-exploring-openpgp.rs
@@ -1,7 +1,6 @@
 //! https://sequoia-pgp.org/guide/exploring-openpgp/
 
 extern crate sequoia_openpgp as openpgp;
-use crate::openpgp::cert::prelude::*;
 use crate::openpgp::parse::Parse;
 use crate::openpgp::policy::StandardPolicy as P;
 
diff --git a/openpgp/src/cert/amalgamation.rs b/openpgp/src/cert/amalgamation.rs
index 9d5515d3..59728192 100644
--- a/openpgp/src/cert/amalgamation.rs
+++ b/openpgp/src/cert/amalgamation.rs
@@ -1,3 +1,16 @@
+//! Component amalgamations.
+//!
+//! Whereas a `ComponentBundle` groups a `Component` with its self
+//! signatures, its third-party signatures, and its revocation
+//! certificates, an `Amalgamation` groups a `ComponentBundle` with
+//! all of the necessary context needed to correctly implement
+//! relevant functionality related to the component.  Specifically, a
+//! `Amalgamation` includes a reference to the `ComponentBundle`, and
+//! a reference to the containing certificate.
+//!
+//! A notable differences between `ComponentBundle`s and
+//! `Amalgamation`s is that a `ComponentBundle`, owns its data, but an
+//! `Amalgamation` only references the contained data.
 use std::borrow::Borrow;
 use std::time;
 use std::time::SystemTime;
@@ -16,18 +29,16 @@ use crate::{
     },
 };
 
-/// Represents a component.
-pub trait Amalgamation<'a, C: 'a> {
+/// Applies a policy to an amalgamation.
+///
+/// Note: This trait is split off from the `Amalgamation` trait, to
+/// reduce code duplication: it is often possible to provide blanket
+/// implementations of `Amalgamation`, but the `ValidateAmalgamation`
+/// trait can only be implemented on more concrete types.
+pub trait ValidateAmalgamation<'a, C: 'a> {
     /// The type returned by `with_policy`.
     type V;
 
-    /// Returns the certificate that the component came from.
-    fn cert(&self) -> &'a Cert;
-
-
-    /// Returns this component's bundle.
-    fn bundle(&self) -> &'a ComponentBundle<C>;
-
     /// Changes the amalgamation's policy.
     ///
     /// If `time` is `None`, the current time is used.
@@ -36,8 +47,25 @@ pub trait Amalgamation<'a, C: 'a> {
               Self: Sized;
 }
 
-/// Represents a component under a given policy.
-pub trait ValidAmalgamation<'a, C: 'a> : Amalgamation<'a, C> {
+/// An amalgamation with a policy and a reference time.
+///
+/// In a certain sense, a `ValidAmalgamation` provides a view of an
+/// `Amalgamation` as it was at a particular time.  That is,
+/// signatures and components that are not valid at the reference
+/// time, because they were created after the reference time, for
+/// instance, are ignored.
+///
+/// The methods exposed by a `ValidAmalgamation` are similar to those
+/// exposed by an `Amalgamation`, but the policy and reference time
+/// are taken from the `ValidAmalgamation`.  This helps prevent using
+/// different policies or different reference times when using a
+/// component, which can easily happen when the checks span multiple
+/// functions.
+pub trait ValidAmalgamation<'a, C: 'a>
+{
+    /// Returns the certificate.
+    fn cert(&self) -> &'a Cert;
+
     /// Returns the amalgamation's reference time.
     ///
     /// For queries that are with respect to a point in time, this
@@ -234,17 +262,136 @@ impl<'a, C> std::ops::Deref for ComponentAmalgamation<'a, C> {
     }
 }
 
-impl<'a, C> Amalgamation<'a, C> for ComponentAmalgamation<'a, C> {
-    type V = ValidComponentAmalgamation<'a, C>;
-
-    fn cert(&self) -> &'a Cert {
-        self.cert
+impl<'a, C> ComponentAmalgamation<'a, C> {
+    /// Returns the certificate that the component came from.
+    pub fn cert(&self) -> &'a Cert {
+        &self.cert
     }
 
-    fn bundle(&self) -> &'a ComponentBundle<C> {
+    /// Returns this amalgamation's bundle.
+    ///
+    /// Note: although `Amalgamation` derefs to a
+    /// `ComponentBundle`, this method provides a more accurate
+    /// lifetime, which is helpful when returning the reference
+    /// from a function.
+    ///
+    /// Consider the following, which doesn't work:
+    ///
+    /// ```compile_fail
+    /// # extern crate sequoia_openpgp as openpgp;
+    /// use openpgp::cert::prelude::*;
+    /// use openpgp::packet::prelude::*;
+    ///
+    /// # let (cert, _) = CertBuilder::new()
+    /// #     .add_userid("Alice")
+    /// #     .add_signing_subkey()
+    /// #     .add_transport_encryption_subkey()
+    /// #     .generate().unwrap();
+    /// cert.keys()
+    ///     .map(|ka| {
+    ///         let b : &KeyBundle<_, _> = &ka;
+    ///         b
+    ///     })
+    ///     .collect::<Vec<&KeyBundle<_, _>>>();
+    /// ```
+    ///
+    /// Compiling the above code results in the following error:
+    ///
+    /// > `b` returns a value referencing data owned by the current
+    /// function
+    ///
+    /// This error occurs because the [`Deref` trait] says that the
+    /// lifetime of the target, i.e., `&KeyBundle`, is
+    /// bounded by `ka`'s lifetime, whose lifetime is indeed
+    /// limited to the closure.  But, `&KeyBundle` is independent
+    /// of `ka`!  It is a copy of the `KeyAmalgamation`'s
+    /// reference to the `KeyBundle` whose lifetime is `'a`.
+    /// Unfortunately, this can't be expressed using `Deref`, but
+    /// it can be done using a separate method:
+    ///
+    /// ```
+    /// # extern crate sequoia_openpgp as openpgp;
+    /// use openpgp::cert::prelude::*;
+    /// use openpgp::packet::prelude::*;
+    ///
+    /// # let (cert, _) = CertBuilder::new()
+    /// #     .add_userid("Alice")
+    /// #     .add_signing_subkey()
+    /// #     .add_transport_encryption_subkey()
+    /// #     .generate().unwrap();
+    /// cert.keys().map(|ka| ka.bundle())
+    ///     .collect::<Vec<&KeyBundle<_, _>>>();
+    /// ```
+    ///
+    /// [`Deref` trait]: https://doc.rust-lang.org/stable/std/ops/trait.Deref.html
+    pub fn bundle(&self) -> &'a ComponentBundle<C> {
         &self.bundle
     }
 
+    /// Returns this amalgamation's component.
+    ///
+    /// Note: although `Amalgamation` derefs to a `Component` (via
+    /// `ComponentBundle`), this method provides a more accurate
+    /// lifetime, which is helpful when returning the reference
+    /// from a function.
+    ///
+    /// Consider the following, which doesn't work:
+    ///
+    /// ```compile_fail
+    /// # extern crate sequoia_openpgp as openpgp;
+    /// use openpgp::cert::prelude::*;
+    /// use openpgp::packet::prelude::*;
+    ///
+    /// # let (cert, _) = CertBuilder::new()
+    /// #     .add_userid("Alice")
+    /// #     .add_signing_subkey()
+    /// #     .add_transport_encryption_subkey()
+    /// #     .generate().unwrap();
+    /// cert.keys()
+    ///     .map(|ka| {
+    ///         let k : &Key<_, _> = &ka;
+    ///         k
+    ///     })
+    ///     .collect::<Vec<&Key<_, _>>>();
+    /// ```
+    ///
+    /// Compiling the above code results in the following error:
+    ///
+    /// > `k` returns a value referencing data owned by the current
+    /// function
+    ///
+    /// This error occurs because the [`Deref` trait] says that the
+    /// lifetime of the target, i.e., `&Key`, is bounded by
+    /// the `ka`'s lifetime, whose lifetime is indeed limited to
+    /// the closure.  But, `&Key` is independent of `ka`!  It is a
+    /// copy of the `KeyAmalgamation`'s reference to the `Key`
+    /// whose lifetime is `'a`.  Unfortunately, this can't be
+    /// expressed using `Deref`, but it can be done using a
+    /// separate method:
+    ///
+    /// ```
+    /// # extern crate sequoia_openpgp as openpgp;
+    /// use openpgp::cert::prelude::*;
+    /// use openpgp::packet::prelude::*;
+    ///
+    /// # let (cert, _) = CertBuilder::new()
+    /// #     .add_userid("Alice")
+    /// #     .add_signing_subkey()
+    /// #     .add_transport_encryption_subkey()
+    /// #     .generate().unwrap();
+    /// cert.keys().map(|ka| ka.key())
+    ///     .collect::<Vec<&Key<_, _>>>();
+    /// ```
+    ///
+    /// [`Deref` trait]: https://doc.rust-lang.org/stable/std/ops/trait.Deref.html
+    pub fn component(&self) -> &'a C {
+        self.bundle().component()
+    }
+}
+
+impl<'a, C> ValidateAmalgamation<'a, C> for ComponentAmalgamation<'a, C> {
+    type V = ValidComponentAmalgamation<'a, C>;
+
     fn with_policy<T>(self, policy: &'a dyn Policy, time: T) -> Result<Self::V>
         where T: Into<Option<time::SystemTime>>,
               Self: Sized
@@ -290,14 +437,14 @@ impl<'a, C> ComponentAmalgamation<'a, C> {
 impl<'a> ComponentAmalgamation<'a, crate::packet::UserID> {
     /// Returns a reference to the User ID.
     pub fn userid(&self) -> &'a crate::packet::UserID {
-        self.bundle().userid()
+        self.component()
     }
 }
 
 impl<'a> ComponentAmalgamation<'a, crate::packet::UserAttribute> {
     /// Returns a reference to the User Attribute.
     pub fn user_attribute(&self) -> &'a crate::packet::UserAttribute {
-        self.bundle().user_attribute()
+        self.component()
     }
 }
 
@@ -336,6 +483,14 @@ impl<'a, C> std::ops::Deref for ValidComponentAmalgamation<'a, C> {
     }
 }
 
+impl<'a, C: 'a> From<ValidComponentAmalgamation<'a, C>>
+    for ComponentAmalgamation<'a, C>
+{
+    fn from(vca: ValidComponentAmalgamation<'a, C>) -> Self {
+        vca.ca
+    }
+}
+
 impl<'a, C> ValidComponentAmalgamation<'a, C>
     where C: Ord
 {
@@ -413,19 +568,9 @@ impl<'a, C> ValidComponentAmalgamation<'a, C>
     }
 }
 
-impl<'a, C> Amalgamation<'a, C> for ValidComponentAmalgamation<'a, C> {
+impl<'a, C> ValidateAmalgamation<'a, C> for ValidComponentAmalgamation<'a, C> {
     type V = Self;
 
-    // NOTE: No docstring, because ComponentAmalgamation has the same method.
-    // Returns the certificate that the component came from.
-    fn cert(&self) -> &'a Cert {
-        self.cert
-    }
-
-    fn bundle(&self) -> &'a ComponentBundle<C> {
-        self.bundle
-    }
-
     fn with_policy<T>(self, policy: &'a dyn Policy, time: T) -> Result<Self::V>
         where T: Into<Option<time::SystemTime>>,
               Self: Sized,
@@ -436,6 +581,10 @@ impl<'a, C> Amalgamation<'a, C> for ValidComponentAmalgamation<'a, C> {
 }
 
 impl<'a, C> ValidAmalgamation<'a, C> for ValidComponentAmalgamation<'a, C> {
+    fn cert(&self) -> &'a Cert {
+        self.ca.cert()
+    }
+
     /// Returns the amalgamation's reference time.
     ///
     /// For queries that are with respect to a point in time, this
diff --git a/openpgp/src/cert/components.rs b/openpgp/src/cert/components.rs
index 2db58947..ac949b59 100644
--- a/openpgp/src/cert/components.rs
+++ b/openpgp/src/cert/components.rs
@@ -24,7 +24,6 @@ use super::{
     canonical_signature_order,
 };
 pub use super::amalgamation::{
-    Amalgamation,
     ComponentAmalgamation,
     ValidAmalgamation,
     ValidComponentAmalgamation,
diff --git a/openpgp/src/cert/key_amalgamation.rs b/openpgp/src/cert/key_amalgamation.rs
index 01e6bcc1..eb2cfa85 100644
--- a/openpgp/src/cert/key_amalgamation.rs
+++ b/openpgp/src/cert/key_amalgamation.rs
@@ -1,19 +1,56 @@
+//! Key amalgamations.
+//!
+//! Whereas a `KeyBundle` groups a `Key` with its self signatures, its
+//! third-party signatures, and its revocation certificates, a
+//! `KeyAmalgamation` groups a `KeyBundle` with all of the necessary
+//! context needed to correctly implement relevant key-related
+//! functionality.  Specifically, a `KeyAmalgamation` includes a
+//! reference to the `KeyBundle`, a reference to the containing
+//! certificate, and the key's role (primary or subordinate).
+//!
+//! There are two notable differences between `KeyBundle`s and
+//! `KeyAmalgamation`s.  First, whereas a `KeyBundle`'s role is
+//! primarily a marker, a `KeyAmalgamation`'s role determines the
+//! `KeyAmalgamation`'s semantics.  As such, it is not possible to
+//! convert a `PrimaryKeyAmalgamation` to a `SubordinateAmalgamation`,
+//! and vice versa.  Second, a `KeyBundle`, owns its data, but a
+//! `KeyAmalgamation` only references the contained data.
+//!
+//! There are three `KeyAmalgamation` variants:
+//! `PrimaryKeyAmalgamation`, `SubordinateKeyAmalgamation`, and
+//! `ErasedKeyAmalgamation`.  Unlike a `Key` or a `KeyBundle` with an
+//! `UnspecifiedRole`, an `ErasedKeyAmalgamation` remembers its role.
+//! This means that an `ErasedKeyAmalgamation` implements the correct
+//! semantics even though the role marker has been erased (hence the
+//! name).
+//!
+//! `ErasedKeyAmalgamation`s are returned by `Cert::keys`.
+//! `Cert::keys` can't return a more specific type, because it returns
+//! an iterator that can contain both primary and subordinate keys.
+//! The reason that we use a concrete type instead of a trait object
+//! is so that when the user converts a `KeyAmalgamation` to a
+//! `ValidKeyAmalgamation`, the `ValidKeyAmalgamation` retains the
+//! type information about the role.  Preserving this type information
+//! increases type safety for users of this API.
 use std::time;
 use std::time::SystemTime;
 use std::ops::Deref;
+use std::convert::TryFrom;
+use std::convert::TryInto;
 
 use failure::ResultExt;
 
 use crate::{
     Cert,
-    cert::components::{
-        Amalgamation,
-        KeyBundle,
+    cert::components::KeyBundle,
+    cert::amalgamation::{
+        ComponentAmalgamation,
         ValidAmalgamation,
+        ValidateAmalgamation,
     },
     Error,
-    packet::key,
     packet::Key,
+    packet::key,
     packet::key::KeyParts,
     packet::Signature,
     policy::Policy,
@@ -21,354 +58,558 @@ use crate::{
     types::RevocationStatus,
 };
 
-/// The underlying `KeyAmalgamation` type.
+/// Methods specific to key amalgamations.
+// This trait exists primarily so that `ValidAmalgamation` can depend
+// on it, and use it in its default implementations.
+pub trait Primary<'a, P, R>
+    where P: 'a + key::KeyParts,
+          R: 'a + key::KeyRole,
+{
+    /// Returns whether the key amalgamation is a primary key
+    /// amalgamation.
+    fn primary(&self) -> bool;
+}
+
+/// A key amalgamation.
 ///
-/// We don't make this type public, because an enum's variant types
-/// must also all be public, and we don't want that here.  Wrapping
-/// this in a struct means that we can hide that.
-#[derive(Debug, Clone)]
-enum KeyAmalgamationBundle<'a, P: key::KeyParts> {
-    Primary(),
-    Subordinate(&'a KeyBundle<P, key::SubordinateRole>),
+/// Generally, you won't use this type directly, but instead use
+/// `PrimaryKeyAmalgamation`, `SubordinateKeyAmalgamation`, or
+/// `ErasedKeyAmalgamation`.
+///
+/// See the module-level documentation for information about key
+/// amalgamations.
+#[derive(Debug)]
+pub struct KeyAmalgamation<'a, P, R, R2>
+    where P: 'a + key::KeyParts,
+          R: 'a + key::KeyRole,
+{
+    ca: ComponentAmalgamation<'a, Key<P, R>>,
+    primary: R2,
 }
 
-/// A `Key` and its associated data.
-#[derive(Debug, Clone)]
-pub struct KeyAmalgamation<'a, P: key::KeyParts> {
-    cert: &'a Cert,
-    bundle: KeyAmalgamationBundle<'a, P>,
+// derive(Clone) doesn't work with generic parameters that don't
+// implement clone.  But, we don't need to require that C implements
+// Clone, because we're not cloning C, just the reference.
+//
+// See: https://github.com/rust-lang/rust/issues/26925
+impl<'a, P, R, R2> Clone for KeyAmalgamation<'a, P, R, R2>
+    where P: 'a + key::KeyParts,
+          R: 'a + key::KeyRole,
+          R2: Copy,
+{
+    fn clone(&self) -> Self {
+        Self {
+            ca: self.ca.clone(),
+            primary: self.primary,
+        }
+    }
 }
 
-impl<'a, P: key::KeyParts> Deref for KeyAmalgamation<'a, P> {
-    type Target = KeyBundle<P, key::UnspecifiedRole>;
+
+/// A primary key amalgamation.
+pub type PrimaryKeyAmalgamation<'a, P>
+    = KeyAmalgamation<'a, P, key::PrimaryRole, ()>;
+
+/// A subordinate key amalgamation.
+pub type SubordinateKeyAmalgamation<'a, P>
+    = KeyAmalgamation<'a, P, key::SubordinateRole, ()>;
+
+/// An amalgamation whose role is not known at compile time.
+///
+/// Note: unlike a `Key` or a `KeyBundle` with an unspecified role, an
+/// `ErasedKeyAmalgamation` remembers its role; it is just not exposed
+/// to the type system.  For details, see the documentation for
+/// `KeyAmalgamation`.
+pub type ErasedKeyAmalgamation<'a, P>
+    = KeyAmalgamation<'a, P, key::UnspecifiedRole, bool>;
+
+
+impl<'a, P, R, R2> Deref for KeyAmalgamation<'a, P, R, R2>
+    where P: 'a + key::KeyParts,
+          R: 'a + key::KeyRole,
+{
+    type Target = ComponentAmalgamation<'a, Key<P, R>>;
 
     fn deref(&self) -> &Self::Target {
-        self.bundle()
+        &self.ca
     }
 }
 
-impl<'a, P: 'a + key::KeyParts> Amalgamation<'a, Key<P, key::UnspecifiedRole>>
-    for KeyAmalgamation<'a, P>
+
+impl<'a, P> ValidateAmalgamation<'a, Key<P, key::PrimaryRole>>
+    for PrimaryKeyAmalgamation<'a, P>
+    where P: 'a + key::KeyParts
 {
-    type V = ValidKeyAmalgamation<'a, P>;
+    type V = ValidPrimaryKeyAmalgamation<'a, P>;
 
-    fn cert(&self) -> &'a Cert {
-        self.cert
-    }
-
-    fn bundle(&self) -> &'a KeyBundle<P, key::UnspecifiedRole> {
-        match self {
-            KeyAmalgamation { bundle: KeyAmalgamationBundle::Primary(), .. } =>
-                P::convert_bundle_ref((&self.cert.primary).into())
-                .expect("secret key amalgamations contain secret keys"),
-            KeyAmalgamation { bundle: KeyAmalgamationBundle::Subordinate(bundle), .. } =>
-                P::convert_bundle_ref((*bundle)
-                                      .mark_parts_unspecified_ref()
-                                      .mark_role_unspecified_ref())
-                .expect("secret key amalgamations contain secret keys"),
-        }
+    fn with_policy<T>(self, policy: &'a dyn Policy, time: T)
+        -> Result<Self::V>
+        where T: Into<Option<time::SystemTime>>
+    {
+        let ka : ErasedKeyAmalgamation<P> = self.into();
+        Ok(ka.with_policy(policy, time)?
+               .try_into().expect("conversion is symmetric"))
     }
+}
 
-    fn with_policy<T>(self, policy: &'a dyn Policy, time: T) -> Result<Self::V>
+impl<'a, P> ValidateAmalgamation<'a, Key<P, key::SubordinateRole>>
+    for SubordinateKeyAmalgamation<'a, P>
+    where P: 'a + key::KeyParts
+{
+    type V = ValidSubordinateKeyAmalgamation<'a, P>;
+
+    fn with_policy<T>(self, policy: &'a dyn Policy, time: T)
+        -> Result<Self::V>
+        where T: Into<Option<time::SystemTime>>
+    {
+        let ka : ErasedKeyAmalgamation<P> = self.into();
+        Ok(ka.with_policy(policy, time)?
+               .try_into().expect("conversion is symmetric"))
+    }
+}
+
+impl<'a, P> ValidateAmalgamation<'a, Key<P, key::UnspecifiedRole>>
+    for ErasedKeyAmalgamation<'a, P>
+    where P: 'a + key::KeyParts
+{
+    type V = ValidErasedKeyAmalgamation<'a, P>;
+
+    fn with_policy<T>(self, policy: &'a dyn Policy, time: T)
+        -> Result<Self::V>
         where T: Into<Option<time::SystemTime>>
     {
         let time = time.into().unwrap_or_else(SystemTime::now);
 
-        // First, we need to make sure the certificate is okay.  Only
-        // do this if we're using a subkey.
+        // We need to make sure the certificate is okay.  This means
+        // checking the primary key.  But, be careful: we don't need
+        // to double check.
         if ! self.primary() {
-            let pka : Self = KeyAmalgamation::new_primary(self.cert());
-            pka.with_policy(policy, time)
-                .context("primary key")?;
+            let pka = PrimaryKeyAmalgamation::new(self.cert());
+            pka.with_policy(policy, time).context("primary key")?;
         }
 
         if let Some(binding_signature) = self.binding_signature(policy, time) {
-            let ka = ValidKeyAmalgamation {
-                a: self,
+            let vka = ValidErasedKeyAmalgamation {
+                ka: KeyAmalgamation {
+                    ca: key::PublicParts::convert_key_amalgamation(
+                        self.ca.mark_parts_unspecified()).expect("to public"),
+                    primary: self.primary,
+                },
                 policy: policy,
                 time: time,
                 binding_signature: binding_signature,
             };
-            policy.key(
-                key::PublicParts::convert_valid_amalgamation_ref(
-                    (&ka).mark_parts_unspecified_ref())
-                    .expect("unspecified parts"))?;
-            Ok(ka)
+            policy.key(&vka)?;
+            Ok(ValidErasedKeyAmalgamation {
+                ka: KeyAmalgamation {
+                    ca: P::convert_key_amalgamation(
+                        vka.ka.ca.mark_parts_unspecified()).expect("roundtrip"),
+                    primary: vka.ka.primary,
+                },
+                policy: policy,
+                time: time,
+                binding_signature: binding_signature,
+            })
         } else {
             Err(Error::NoBindingSignature(time).into())
         }
     }
 }
 
-impl<'a, P: 'a + key::KeyParts> KeyAmalgamation<'a, P> {
-    pub(crate) fn new_primary(cert: &'a Cert) -> Self {
-        KeyAmalgamation {
-            cert: cert,
-            bundle: KeyAmalgamationBundle::Primary(),
+impl<'a, P> Primary<'a, P, key::PrimaryRole>
+    for PrimaryKeyAmalgamation<'a, P>
+    where P: 'a + key::KeyParts
+{
+    fn primary(&self) -> bool {
+        true
+    }
+}
+
+impl<'a, P> Primary<'a, P, key::SubordinateRole>
+    for SubordinateKeyAmalgamation<'a, P>
+    where P: 'a + key::KeyParts
+{
+    fn primary(&self) -> bool {
+        false
+    }
+}
+
+impl<'a, P> Primary<'a, P, key::UnspecifiedRole>
+    for ErasedKeyAmalgamation<'a, P>
+    where P: 'a + key::KeyParts
+{
+    fn primary(&self) -> bool {
+        self.primary
+    }
+}
+
+
+impl<'a, P: 'a + key::KeyParts> From<PrimaryKeyAmalgamation<'a, P>>
+    for ErasedKeyAmalgamation<'a, P>
+{
+    fn from(ka: PrimaryKeyAmalgamation<'a, P>) -> Self {
+        ErasedKeyAmalgamation {
+            ca: ka.ca.mark_role_unspecified(),
+            primary: true,
         }
     }
+}
 
-    pub(crate) fn new_subordinate(
-        cert: &'a Cert, bundle: &'a KeyBundle<P, key::SubordinateRole>)
-        -> Self
-    {
-        KeyAmalgamation {
-            cert: cert,
-            bundle: KeyAmalgamationBundle::Subordinate(bundle),
+impl<'a, P: 'a + key::KeyParts> From<SubordinateKeyAmalgamation<'a, P>>
+    for ErasedKeyAmalgamation<'a, P>
+{
+    fn from(ka: SubordinateKeyAmalgamation<'a, P>) -> Self {
+        ErasedKeyAmalgamation {
+            ca: ka.ca.mark_role_unspecified(),
+            primary: false,
         }
     }
+}
+
 
-    /// Returns whether the key is a primary key.
-    pub fn primary(&self) -> bool {
-        if let KeyAmalgamationBundle::Primary() = self.bundle {
-            true
+impl<'a, P: 'a + key::KeyParts> TryFrom<ErasedKeyAmalgamation<'a, P>>
+    for PrimaryKeyAmalgamation<'a, P>
+{
+    type Error = failure::Error;
+
+    fn try_from(ka: ErasedKeyAmalgamation<'a, P>) -> Result<Self> {
+        if ka.primary {
+            Ok(Self {
+                ca: ka.ca.mark_role_primary(),
+                primary: (),
+            })
         } else {
-            false
+            Err(Error::InvalidArgument(
+                "can't convert a SubordinateKeyAmalgamation \
+                 to a PrimaryKeyAmalgamation".into()).into())
         }
     }
+}
+
+impl<'a, P: 'a + key::KeyParts> TryFrom<ErasedKeyAmalgamation<'a, P>>
+    for SubordinateKeyAmalgamation<'a, P>
+{
+    type Error = failure::Error;
 
-    /// Returns the key.
-    pub fn key(&self) -> &'a Key<P, key::UnspecifiedRole> {
-        match self {
-            KeyAmalgamation { bundle: KeyAmalgamationBundle::Primary(), .. } =>
-                P::convert_key_ref(self.cert.primary.key().into())
-                .expect("secret key amalgamations contain secret keys"),
-            KeyAmalgamation { bundle: KeyAmalgamationBundle::Subordinate(bundle), .. } =>
-                P::convert_key_ref(bundle.key()
-                                   .mark_parts_unspecified_ref()
-                                   .mark_role_unspecified_ref())
-                .expect("secret key amalgamations contain secret keys"),
+    fn try_from(ka: ErasedKeyAmalgamation<'a, P>) -> Result<Self> {
+        if ka.primary {