use std::borrow::Cow;
use std::collections::BTreeMap;
use std::path::Path;
use std::path::PathBuf;
use std::sync::Arc;
use std::sync::Mutex;
use std::sync::Weak;
use std::sync::atomic::AtomicBool;

use anyhow::Context as _;

use cryptoki::object::Attribute;
use cryptoki::object::AttributeType;
use cryptoki::object::ObjectClass;
use cryptoki::object::ObjectHandle;
use cryptoki::session::Session;
use cryptoki::session::UserType;
use cryptoki::slot::Slot;
use cryptoki::slot::TokenInfo;
use cryptoki::types::AuthPin;

use sequoia_openpgp as openpgp;
use openpgp::Fingerprint;
use openpgp::packet::key::PublicParts;
use openpgp::packet::key::UnspecifiedRole;
use openpgp::packet;

use crate::Context;
use crate::Result;
use crate::KeySelector;
use crate::TokenSelector;

const TRACE: bool = false;

struct Pkcs11 {
    inner: Option<cryptoki::context::Pkcs11>,
}

impl std::fmt::Debug for Pkcs11 {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result
    {
        if let Some(pkcs11) = self.inner.as_ref() {
            write!(f, "{:?}", pkcs11)
        } else {
            write!(f, "<finalized PKCS11 context>")
        }
    }
}

impl Drop for Pkcs11 {
    fn drop(&mut self) {
        if let Some(pkcs11) = self.inner.take() {
            if let Err(err) = pkcs11.finalize() {
                eprintln!("Finalizing PKCS11 context: {}", err);
            }
        }
    }
}

impl std::ops::Deref for Pkcs11 {
    type Target = cryptoki::context::Pkcs11;

    fn deref(&self) -> &Self::Target {
        // `self.inner` is only `None` if `self` has been dropped.
        self.inner.as_ref().expect("not finalized")
    }
}

impl From<cryptoki::context::Pkcs11> for Pkcs11 {
    fn from(pkcs11: cryptoki::context::Pkcs11) -> Self {
        Self {
            inner: Some(pkcs11),
        }
    }
}

/// A PKCS#11 backend.
///
/// A backend corresponds to a PKCS#11 library.
///
/// A [`Backend`] provides access to one or more slots, which may or
/// may not contain a token.  Each token holds one or more [`Key`]s.
#[derive(Clone, Debug)]
pub struct Backend {
    lib: PathBuf,
    // `lib`, but encoded with String::from_utf8_lossy.
    pub(crate) lib_str: String,
    context: Arc<Pkcs11>,
}

impl Backend {
    /// Returns the low-level context.
    pub fn context(&self) -> &cryptoki::context::Pkcs11 {
        &self.context
    }

    /// Returns the location of the library.
    pub fn lib(&self) -> &Path {
        &self.lib
    }

    /// Returns a short name for the library.
    ///
    /// The short name is the file name with all extensions and any
    /// leading lib stripped.  Any invalid UTF-8 sequences are
    /// replaced with `U+FFFD REPLACEMENT CHARACTER`.
    ///
    /// Consider the library
    /// `/usr/lib/x86_64-linux-gnu/libykcs11.so.2`.  The short name is
    /// `ykcs11`.
    pub fn lib_short(&self) -> &str {
        let lib = &self.lib_str[..];

        if let Some(i) = lib.rfind('/') {
            // Don't return an empty string.
            if i < lib.len() - 1 {
                let file_name = &lib[i + 1 ..];

                // Strip any extensions.
                if let Some(dot) = file_name.find('.') {
                    let prefix = &file_name[..dot];
                    // Strip a leading lib.
                    if let Some(inner) = prefix.strip_prefix("lib") {
                        return inner;
                    } else {
                        return prefix;
                    }
                }
                return file_name;
            }
        }

        &lib[..]
    }

    /// Returns whether `query` matches the backend.
    ///
    /// Consider the library
    /// `/usr/lib/x86_64-linux-gnu/libykcs11.so.2`.  This matches on
    /// the full path, on the filename (`libykcs11.so.2`), the
    /// filename with each trailing component stripped
    /// (`libykcs11.so`, and `libykcs11`), and the filename with any
    /// initial `lib` prefix and all trailing components striped
    /// (`ykcs11`).
    pub fn is_lib(&self, query: &str) -> bool {
        tracer!(false, "is_lib");
        t!("Checking if {} matches {}", query, self.lib.display());

        if query.as_bytes() == self.lib.as_os_str().as_encoded_bytes() {
            // Exact match.
            t!("Exact match");
            return true;
        } else if query.contains(&['/', '\\']) {
            // `query` contains a path separator so only an exact match
            // is possible.
            t!("Not an exact match, and name contains a path separator.  Giving up.");
            return false;
        };

        let path = PathBuf::from(&self.lib);
        if let Some(file_name) = path.file_name() {
            t!("Considering {}",
               String::from_utf8_lossy(file_name.as_encoded_bytes()));
            if file_name == query {
                // Matches on the filename.
                t!("Match");
                return true;
            }

            let query = query.as_bytes();
            let file_name = file_name.as_encoded_bytes();

            let mut first = true;
            for (i, c) in file_name.iter().enumerate() {
                if *c == b'.' {
                    let prefix = &file_name[..i];

                    t!("Considering {}",
                       String::from_utf8_lossy(prefix));

                    if prefix == query {
                        t!("Match");
                        return true;
                    }

                    if first {
                        if prefix.starts_with(b"lib") {
                            let middle = &prefix[3..];

                            t!("Considering {}",
                               String::from_utf8_lossy(middle));
                            if middle == query {
                                t!("Match");
                                return true;
                            }
                        }
                    }
                    first = false;
                }
            }
        }

        t!("Not a match");
        false
    }
}

/// Encapsulates a token.
///
/// A [`Backend`] provides access to one or more slots, which may or
/// may not contain a token.  Each token holds one or more [`Key`]s.
/// Before a token has been initialize its slot ID is the only way to
/// identify it.  Afterwards, the token's unique ID (which not all
/// backends support) or the token's label (which is not guaranteed to
/// be unique, but is by convention) should be used.
#[derive(Clone, Debug)]
pub struct Token {
    backend: Backend,
    slot: Slot,
    info: TokenInfo,
}

impl Token {
    /// Returns the backend.
    pub fn backend(&self) -> &Backend {
        &self.backend
    }

    /// Returns the slot.
    pub fn slot(&self) -> &Slot {
        &self.slot
    }

    /// Returns information about the token.
    ///
    /// See [`cryptoki::TokenInfo`] for more details.
    ///
    ///   [`cryptoki::TokenInfo`]: https://docs.rs/cryptoki/latest/cryptoki/slot/struct.TokenInfo.html
    pub fn info(&self) -> &TokenInfo {
        &self.info
    }

    /// Opens a read-only session to the token.
    ///
    /// This is needed to sign or decrypt a message, for instance.
    ///
    /// A user is not logged into the session.  You should either use
    /// [`Token::open_ro_user_session`], or follow up by calling the
    /// low-level `Session`'s [`login`] method.
    ///
    ///   [`login`]: https://docs.rs/cryptoki/latest/cryptoki/session/struct.Session.html#method.login
    pub fn open_ro_session(&self)
        -> Result<cryptoki::session::Session>
    {
        let session = self.backend().context.clone()
            .open_ro_session(self.slot().clone())?;
        Ok(session)
    }

    /// Opens a read-only session to the token, and logs in as the
    /// user.
    ///
    /// This is needed to sign or decrypt a message, for instance.
    pub fn open_ro_user_session<P>(&self, pin: P)
        -> Result<cryptoki::session::Session>
    where
        P: Into<AuthPin>
    {
        let session = self.open_ro_session()?;
        session.login(UserType::User, Some(&pin.into()))?;
        Ok(session)
    }

    /// Opens a read-write session to the token.
    ///
    /// This is needed to generate or import a key, for instance.
    ///
    /// A user is not logged into the session.  You should either use
    /// [`Token::open_rw_user_session`], or follow up by calling the
    /// low-level `Session`'s [`login`] method.
    ///
    ///   [`login`]: https://docs.rs/cryptoki/latest/cryptoki/session/struct.Session.html#method.login
    pub fn open_rw_session(&self)
        -> Result<cryptoki::session::Session>
    {
        let session = self.backend().context.clone()
            .open_rw_session(self.slot().clone())?;
        Ok(session)
    }

    /// Opens a read-write session to the token, and logs in as the
    /// user.
    ///
    /// This is needed to generate or import a key, for instance.
    pub fn open_rw_user_session<P>(&self, pin: P)
        -> Result<cryptoki::session::Session>
    where
        P: Into<AuthPin>
    {
        let session = self.backend().context.clone()
            .open_rw_session(self.slot().clone())?;
        session.login(UserType::User, Some(&pin.into()))?;
        Ok(session)
    }
}

impl std::fmt::Display for Token {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>)
        -> std::result::Result<(), std::fmt::Error>
    {
        let mut label = self.info().label();
        if label.is_empty() {
            label = "<no label>";
        }
        let manufacturer_id = self.info().manufacturer_id();
        let model = self.info().model();
        let serial_number = self.info().serial_number();

        let product = match (manufacturer_id.is_empty(), model.is_empty()) {
            (true, true) => Cow::Borrowed("Unknown product"),
            (true, false) => manufacturer_id.into(),
            (false, true) => model.into(),
            (false, false) => {
                if model.contains(manufacturer_id) {
                    model.into()
                } else {
                    format!("{} {}", manufacturer_id, model).into()
                }
            }
        };

        let mut id = if serial_number.is_empty() {
            format!("{} ({})", label, product)
        } else {
            format!("{} ({}, serial number: {})", label, product, serial_number)
        };

        if id.chars().any(|c| c.is_control()) {
            // Escape control characters.
            id = format!("{:?}", id);
        } else {
            // Replace newlines with dashes.
            id = id.replace("\n", "-");
            id = id.replace("\r", "-");
        }

        write!(f, "{}", id)
    }
}

/// Describes a key.
///
/// A [`Backend`] provides access to one or more slots, which may or
/// may not contain a token.  Each token holds one or more [`Key`]s.
///
/// This data structure contains a reference to a PKCS#11 context, and
/// everything needed to find a particular key.
///
/// We don't store a `Session` in this data structure for two reasons.
/// First, an open session locks the token, which may interfere with
/// other users of the token.  Second, `Session`s are not `Sync`,
/// which means that `Key` would not be `Sync` without wrapping the
/// `Session` in something like a `Mutex`.  Instead, we open a session
/// on demand.
///
/// Because we don't have a session, we can't store an object handle,
/// which is only meaningful for a particular session.  According to
/// PKCS#11, v3.2, draft 13, Section 3.4:
///
/// > When an object is created or found on a token by an application,
/// > Cryptoki assigns it an object handle for that application’s
/// > sessions to use to access it. A particular object on a token
/// > does not necessarily have a handle which is fixed for the
/// > lifetime of the object; however, if a particular session can use
/// > a particular handle to access a particular object, then that
/// > session will continue to be able to use that handle to access
/// > that object as long as the session continues to exist, the
/// > object continues to exist, and the object continues to be
/// > accessible to the session.
///
/// To workaround this, we cache what we can about a key so that we
/// can *unambiguously* find it later.  In principle, the unique ID
/// (`CKA_UNIQUE_ID`) attribute is enough.  From PKCS#11, v3.2, draft
/// 13, Section 4.4.1:
///
/// > Any time a new object is created, a value for `CKA_UNIQUE_ID` MUST
/// > be generated by the token and stored with the object. The
/// > specific algorithm used to generate unique ID values for objects
/// > is token-specific, but values generated MUST be unique across
/// > all objects visible to any particular session, and SHOULD be
/// > unique across all objects created by the token.
///
/// Unfortunately, this was only added in PKCS#11 v3.0, and we want to
/// support older tokens.
///
/// So, in addition to opportunistically using the unique ID, we also
/// use the following to distinguish keys, and hope for the best:
///
///   - `CKA_LABEL`: Set by the user.
///
///   - `CKA_ID`: Set at key generation time by the application.  By
///   convention, this is the same for the public key, private key and
///   certificate tuple.
///
///   - `CKA_URL`: Set at key generation time by the application.  By
///   convention, this is used as a unique identifier.
#[derive(Debug)]
pub struct Key {
    token: Token,

    /// The other constituent of a composite key.
    ///
    /// Some OpenPGP algorithms combine two cryptographic algorithms
    /// in one key, e.g. `PublicKeyAlgorithm::MLDSA65_Ed25519`.
    composite_key: Option<Box<Key>>,

    // Cached values that are normally static.
    object_class: Option<ObjectClass>,
    key_unique_id: Option<Vec<u8>>,
    key_label: Option<Vec<u8>>,
    key_id: Option<Vec<u8>>,
    key_url: Option<Vec<u8>>,
    pub(crate) openpgp_key: Mutex<Option<packet::Key<PublicParts, UnspecifiedRole>>>,

    pub(crate) got_capabilities: AtomicBool,
    pub(crate) signing_capable: AtomicBool,
    pub(crate) decryption_capable: AtomicBool,
}

impl Clone for Key {
    fn clone(&self) -> Self {
        Self {
            token: self.token.clone(),
            composite_key: self.composite_key.clone(),
            object_class: self.object_class.clone(),
            key_unique_id: self.key_unique_id.clone(),
            key_label: self.key_label.clone(),
            key_id: self.key_id.clone(),
            key_url: self.key_url.clone(),
            openpgp_key: Mutex::new(
                self.openpgp_key.lock().unwrap().as_ref().map(|k| k.clone())),

            got_capabilities: false.into(),
            signing_capable: false.into(),
            decryption_capable: false.into(),
        }
    }
}

impl Key {
    /// Returns the other constituent of a composite key.
    ///
    /// Some OpenPGP algorithms combine two cryptographic algorithms
    /// in one key, e.g. [`PublicKeyAlgorithm::MLDSA65_Ed25519`].
    pub(crate) fn composite_key(&self) -> Option<&Key> {
        self.composite_key.as_deref()
    }

    /// Attaches a key to form a composite key.
    pub(crate) fn combine_with(&mut self, key: Key) {
        assert!(self.composite_key.is_none());
        assert!(key.composite_key.is_none());
        self.composite_key = Some(Box::new(key));
    }

    /// Returns the backend.
    pub fn backend(&self) -> &Backend {
        self.token.backend()
    }

    /// Returns the token.
    pub fn token(&self) -> &Token {
        &self.token
    }

    /// Returns the slot.
    pub fn slot(&self) -> &Slot {
        self.token.slot()
    }

    /// Returns information about the token.
    ///
    /// See [`cryptoki::TokenInfo`] for more details.
    ///
    ///   [`cryptoki::TokenInfo`]: https://docs.rs/cryptoki/latest/cryptoki/slot/struct.TokenInfo.html
    pub fn info(&self) -> &TokenInfo {
        self.token.info()
    }

    /// Returns the key's object class, if any.
    ///
    /// See [`cryptoki::ObjectClass`] for more details.
    ///
    ///   [`cryptoki::ObjectClass`]: https://docs.rs/cryptoki/latest/cryptoki/object/struct.ObjectClass.html
    pub fn object_class(&self) -> Option<ObjectClass> {
        self.object_class.clone()
    }

    /// Returns the key's unique ID, if any.
    pub fn key_unique_id(&self) -> Option<&[u8]> {
        self.key_unique_id.as_deref()
    }

    /// Returns the key's hex encoded unique ID, if any.
    pub fn key_unique_id_hex(&self) -> Option<String> {
        self.key_unique_id()
            .map(|id| {
                id.iter()
                    .map(|x| format!("{:02x}", x))
                    .collect::<Vec<String>>()
                    .join("")
            })
    }

    /// Returns the key's label, if any.
    pub fn key_label(&self) -> Option<&[u8]> {
        self.key_label.as_deref()
    }

    /// Returns the key's key ID, if any.
    pub fn key_id(&self) -> Option<&[u8]> {
        self.key_id.as_deref()
    }

    /// Returns the key's URL, if any.
    pub fn key_url(&self) -> Option<&[u8]> {
        self.key_url.as_deref()
    }

    /// Returns a new session and an object handle to the object
    /// designated by the key descriptor.
    pub fn open_ro_session(&self)
        -> Result<(Session, ObjectHandle)>
    {
        let session
            = self.backend().context().open_ro_session(self.slot().clone())?;

        let mut attrs = Vec::with_capacity(5);
        if let Some(object_class) = self.object_class {
            attrs.push(Attribute::Class(object_class));
        }
        if let Some(unique_id) = self.key_unique_id() {
            attrs.push(Attribute::UniqueId(unique_id.to_vec()));
        }
        if let Some(label) = self.key_label() {
            attrs.push(Attribute::Label(label.to_vec()));
        }
        if let Some(id) = self.key_id() {
            attrs.push(Attribute::Id(id.to_vec()));
        }
        if let Some(url) = self.key_url() {
            attrs.push(Attribute::Url(url.to_vec()));
        }

        let mut objects = session.iter_objects(&attrs)
            .with_context(|| {
                format!("Listing {}'s objects",
                        self.backend().lib().display())
            })?;

        let first = objects.next();
        let second = objects.next();
        let object = match (first, second) {
            (Some(object), None) => object.context("Getting private key")?,
            (Some(_), Some(_)) => {
                return Err(anyhow::anyhow!(
                    "Multiple keys correspond to the key descriptor, \
                     cowardly refusing to continue."));
            }
            (None, _) => {
                return Err(anyhow::anyhow!("Key object disappeared"));
            }
        };
        drop(objects);

        Ok((session, object))
    }

    /// Wraps an object handle designating a key.
    ///
    /// This function does not cache the session or the object.  But
    /// you can use `Self::open_ro_session` to get a new session and a
    /// new object handle.
    pub fn from_object(token: Token, session: &Session, object: ObjectHandle)
        -> Result<Self>
    {
        // Get the label and the id, etc.
        let mut object_class = None;
        let mut key_unique_id = None;
        let mut key_label = None;
        let mut key_id = None;
        let mut key_url = None;

        // We need to be careful: unknown attributes
        // are skipped.
        let attributes = session.get_attributes(
            object,
            &[
                AttributeType::Class,
                AttributeType::UniqueId,
                AttributeType::Label,
                AttributeType::Id,
                AttributeType::Url,
            ])?;
        for attribute in attributes {
            if let Attribute::Class(value) = attribute {
                object_class = Some(value);
            } else if let Attribute::UniqueId(value) = attribute {
                key_unique_id = Some(value);
            } else if let Attribute::Label(value) = attribute {
                key_label = Some(value);
            } else if let Attribute::Id(value) = attribute {
                key_id = Some(value);
            } else if let Attribute::Url(value) = attribute {
                key_url = Some(value);
            } else {
                unreachable!("get_attributes only returns \
                              requested attributes");
            }
        }

        Ok(Self {
            token,
            composite_key: None,
            object_class,
            key_unique_id,
            key_label,
            key_id,
            key_url,
            openpgp_key: Mutex::new(None),

            got_capabilities: false.into(),
            signing_capable: false.into(),
            decryption_capable: false.into(),
        })
    }

    /// Returns the key's OpenPGP fingerprint.
    ///
    /// If the key is not an OpenPGP key, then this returns `None`.
    pub fn fingerprint(&self) -> Option<Fingerprint> {
        self.to_openpgp_key().ok().map(|key| key.fingerprint())
    }
}

/// Used by `Context::select_internal` to return a list of keys or
/// tokens.
#[derive(Debug)]
enum KeyOrToken {
    Key(Key),
    Token(Token),
}

impl KeyOrToken {
    fn is_key(&self) -> bool {
        self.key().is_some()
    }

    fn key(&self) -> Option<&Key> {
        match self {
            KeyOrToken::Key(key) => Some(key),
            KeyOrToken::Token(_) => None,
        }
    }

    fn key_unwrap(&self) -> &Key {
        self.key().expect(
            "Internal error: looked up a key, got a token")
    }

    fn key_mut(&mut self) -> Option<&mut Key> {
        match self {
            KeyOrToken::Key(key) => Some(key),
            KeyOrToken::Token(_) => None,
        }
    }

    fn key_mut_unwrap(&mut self) -> &mut Key {
        self.key_mut().expect(
            "Internal error: looked up a key, got a token")
    }

    fn into_key_unwrap(self) -> Key {
        match self {
            KeyOrToken::Key(key) => key,
            KeyOrToken::Token(_) =>
                panic!("Internal error: looked up a token, got a key"),
        }
    }

    fn into_token_unwrap(self) -> Token {
        match self {
            KeyOrToken::Key(_) =>
                panic!("Internal error: looked up a token, got a key"),
            KeyOrToken::Token(token) => token,
        }
    }

}

/// The number of allowed matches.
///
/// Used by `Context::select_internal`.
#[derive(Debug, Clone, Eq, PartialEq)]
enum AllowedMatches {
    None,
    One,
    Any,
}

/// The selector's scope.
///
/// Used by [`Context::select_one_key`], and [`Context::select_keys`]
/// to specify whether public or private keys should be considered.
#[derive(Debug, Clone, Eq, PartialEq)]
pub enum SelectorScope {
    All,
    PublicKeys,
    PrivateKeys,
}

// After initializing a backend, we have to finalize it before we can
// initialize it again.  Cache the backends.
static BACKENDS: Mutex<BTreeMap<PathBuf, Weak<Pkcs11>>>
    = Mutex::new(BTreeMap::new());

impl Context {
    /// Returns a reference to the PKCS#11 contexts.
    ///
    /// The context has bound the specified libraries.  As this loads
    /// the modules, this function may return an error if a module
    /// can't be loaded.
    pub fn backends(&self) -> Result<&[Backend]> {
        tracer!(TRACE, "Context::backends");

        if let Some(backends) = self.backends.get() {
            return Ok(backends);
        }

        let modules = self.config.modules();
        let mut backends = Vec::with_capacity(modules.len());
        let mut load_err = None;
        let mut init_err = None;
        for lib in modules {
            t!("Loading {}", lib.display());

            // See if we already initialize the backend.
            let mut backend = BACKENDS.lock().unwrap();
            if let Some(context) = backend.get(lib) {
                if let Some(context) = context.upgrade() {
                    t!("Loaded {} (cached)", lib.display());

                    backends.push(Backend {
                        lib: lib.clone(),
                        lib_str: lib.display().to_string(),
                        context,
                    });

                    continue;
                }
            }

            let context = match cryptoki::context::Pkcs11::new(lib) {
                Ok(context) => context,
                Err(err) => {
                    log::debug!("{}: Error loading {}: {}",
                                func!(), lib.display(), err);
                    if load_err.is_none() {
                        load_err = Some(err);
                    }
                    continue;
                }
            };

            // Check if it is already initialized...
            match context.initialize(
                cryptoki::context::CInitializeArgs::new(
                    cryptoki::context::CInitializeFlags::OS_LOCKING_OK))
            {
                Ok(context) => context,
                Err(err) => {
                    log::debug!("{}: Error initializing {}: {}",
                                func!(), lib.display(), err);
                    if init_err.is_none() {
                        init_err = Some(err);
                    }
                    continue;
                }
            };
            t!("Loaded {}", lib.display());

            let context = Arc::new(context.into());

            // Cache the context.
            backend.insert(lib.clone(), Arc::downgrade(&context));

            backends.push(Backend {
                lib: lib.clone(),
                lib_str: lib.display().to_string(),
                context,
            });
        }

        if let Some(err) = init_err {
            return Err(err.into());
        }
        if let Some(err) = load_err {
            return Err(err.into());
        }

        let _ = self.backends.set(backends);
        let backends = self.backends.get().expect("just set");
        Ok(backends)
    }

    /// Returns the matching keys (`key = true`) or tokens (`key =
    /// false`).
    ///
    /// If `tokens` is `true`, then the selector's `key_unique_id`,
    /// `key_label`, `key_id` and `key_url` fields are ignored, and
    /// must be `None`.
    ///
    /// If `get_constituent` is `true`, then gets any constituent key.
    fn select_internal(&self, selector: &KeySelector, key: bool,
                       allowed_matches: AllowedMatches,
                       scope: SelectorScope,
                       get_constituent: bool)
        -> Result<Vec<KeyOrToken>>
    {
        tracer!(TRACE, "Context::select_internal");

        // All will only contain all of the objects if there are no
        // matches.
        let mut all: Vec<KeyOrToken> = Vec::new();
        let mut matches: Vec<KeyOrToken> = Vec::new();

        // If the user specified a backend, but it doesn't match any,
        // print a pretty error message.
        let mut backend_matched = false;
        let mut backend_names = Vec::new();

        for backend in self.backends()? {
            backend_names.push(backend.lib_short());
            if ! selector.backend_matches(&backend) {
                continue;
            } else {
                backend_matched = true;
            }

            let slots = match backend.context().get_all_slots() {
                Ok(slots) => slots,
                Err(err) => {
                    log::debug!("{}: Failed to enumerate slots for {}: {}",
                                func!(), backend.lib().display(), err);
                    continue;
                }
            };
            t!("{} has {} slots", backend.lib().display(), slots.len());
            'slot_loop: for slot in slots.into_iter() {
                let info = match backend.context().get_token_info(slot.clone()) {
                    Ok(info) => info,
                    Err(err) => {
                        t!("Failed to get token info for slot {}: {}",
                           slot.id(), err);
                        continue 'slot_loop;
                    }
                };

                let matches_token =
                    selector.slot_matches(slot.id())
                    && selector.token_label_matches(info.label())
                    && selector.token_serial_number_matches(
                        info.serial_number());

                if ! key {
                    // Matching tokens.
                    let token = Token {
                        backend: backend.clone(),
                        slot: slot,
                        info: info.clone(),
                    };

                    if matches_token {
                        matches.push(KeyOrToken::Token(token));
                    } else {
                        all.push(KeyOrToken::Token(token));
                    }
                } else {
                    // Matching keys.
                    let session = match backend.context().open_ro_session(slot) {
                        Ok(session) => session,
                        Err(err) => {
                            log::debug!(
                                "{}: Warning: {}'s slot {} is unusable: {}",
                                func!(),
                                backend.lib().display(), slot.id(),
                                err);
                            continue 'slot_loop;
                        }
                    };

                    // Iterate over the objects on the token.
                    let attrs = match scope {
                        SelectorScope::All => &[][..],
                        SelectorScope::PublicKeys => {
                            &[ Attribute::Class(ObjectClass::PUBLIC_KEY) ]
                        }
                        SelectorScope::PrivateKeys => {
                            &[ Attribute::Class(ObjectClass::PRIVATE_KEY) ]
                        }
                    };
                    let objects = match session.iter_objects(attrs) {
                        Ok(objects) => objects,
                        Err(err) => {
                            log::debug!(
                                "{}: Error listing {}'s objects: {}",
                                func!(),
                                backend.lib().display(),
                                err);
                            continue 'slot_loop;
                        }
                    };

                    'obj_loop: for (i, object) in objects.enumerate() {
                        let object = match object {
                            Ok(object) => object,
                            Err(err) => {
                                log::debug!(
                                    "{}: Error reading object #{}: {}",
                                    func!(), i + 1, err);
                                continue 'obj_loop;
                            }
                        };

                        // Get the label and the id.
                        let token = Token {
                            backend: backend.clone(),
                            slot: slot,
                            info: info.clone(),
                        };
                        let key = match Key::from_object(
                            token, &session, object)
                        {
                            Ok(key) => key,
                            Err(err) => {
                                t!("Reading object #{}'s attributes: {}",
                                   i + i, err);
                                continue 'obj_loop;
                            }
                        };
                        let matches_key_unique_id
                            = selector.key_unique_id_matches(key.key_unique_id());

                        let matches_key_label = if let Some(l) = selector.key_label() {
                            // The user is selecting by key label.
                            Some(l.as_bytes()) == key.key_label()
                        } else {
                            // key label not specified.  This is a match.
                            true
                        };

                        let matches_key_id = selector.key_id_matches(key.key_id());
                        let matches_key_url = selector.key_url_matches(key.key_url());

                        if matches_token
                            && matches_key_unique_id && matches_key_label
                            && matches_key_id && matches_key_url
                        {
                            matches.push(KeyOrToken::Key(key));
                        } else {
                            all.push(KeyOrToken::Key(key));
                        }
                    }
                }
            }
        }

        // For each composite key, find its constituent key.
        if key && get_constituent {
            'next_match: for i in 0..matches.len() {
                if i >= matches.len() {
                    // This could happen because we remove entries.
                    break;
                }

                // Figure out the name of the other key.
                //
                // Whether a key is part of a composite key and what
                // part it is is encoded in the key ID.
                let m = &matches[i];
                let key = m.key_unwrap();
                let key_id = if let Some(key_id) = key.key_id() {
                    match String::from_utf8(key_id.to_vec()) {
                        Ok(key_id) => key_id,
                        Err(_err) => {
                            // Not a key ID that we understand.
                            continue;
                        }
                    }
                } else {
                    continue;
                };

                // A bi-directional map between key ID prefixes for
                // composite keys.
                let map = &[
                    ("pgp:v6t:", "pgp:v6pq:"),
                    ("pgp:v4t:", "pgp:v4pq:"),
                ];

                let mut other_key_id = None;
                for (one, other) in map.into_iter().map(|(a, b)| (*a, *b))
                    // Flip the map around.
                    .chain(map.into_iter().map(|(a, b)| (*b, *a)))
                {
                    if let Some(suffix) = key_id.strip_prefix(one) {
                        other_key_id = Some(format!("{}{}", other, suffix));
                        break;
                    }
                }

                let other_key_id = if let Some(other_key_id) = other_key_id {
                    other_key_id
                } else {
                    // Not a (known) composite key.
                    continue;
                };

                // Look up the constituent key.

                // It may be that we already found the key that we're
                // looking for.
                if i + 1 < matches.len() {
                    for j in i + 1..matches.len() {
                        let other = matches[j].key_unwrap();
                        if other.key_id() == Some(other_key_id.as_bytes()) {
                            // Yup!  We're done.
                            let other = matches.remove(j).into_key_unwrap();
                            matches[i].key_mut_unwrap().combine_with(other);
                            continue 'next_match;
                        }
                    }
                }

                // We need to look up the other key manually.  We
                // recurse and are careful to indicate that we
                // shouldn't look for this key.
                let other = self.select_internal(
                    &KeySelector::from_key_id(other_key_id),
                    true, // key
                    AllowedMatches::One,
                    SelectorScope::PublicKeys,
                    false, // Don't recurse.
                );
                match other {
                    Ok(results) => {
                        assert_eq!(results.len(), 1);
                        let other = results.into_iter().next().unwrap();
                        let other = other.into_key_unwrap();
                        matches[i].key_mut_unwrap().combine_with(other);
                    }
                    Err(err) => {
                        log::debug!(
                            "{}: Warning: {} is a composite key, \
                             but half the key is missing: {}",
                            func!(), key_id, err);
                    }
                }
            }
        }

        let obj = if key { "key" } else { "token" };
        let objs = if key { "keys" } else { "tokens" };

        if allowed_matches == AllowedMatches::None {
            // Don't want any matches.
            if matches.len() == 0 {
                Ok(vec![])
            } else {
                log::debug!("{}: The {} selector {} matches existing {}:",
                            func!(), obj, selector.args(), objs);
                Self::list_matches(matches);

                if key {
                    Err(anyhow::anyhow!(
                        "The {} selector matches existing {}, choose a \
                         different label or use --ambiguous-key-label, \
                         or --random-key-label",
                        obj, objs))
                } else {
                    Err(anyhow::anyhow!(
                        "The {} selector matches existing {}", obj, objs))
                }
            }
        } else if allowed_matches == AllowedMatches::One && matches.len() == 0 {
            // No match, but want one.
            if let (Some(backend), false)
                = (selector.backend(), backend_matched)
            {
                Err(anyhow::anyhow!(
                    "The specified backend ({}) wasn't loaded (try: {})",
                    backend, backend_names.join(", ")))
            } else {
                log::debug!("{}: The {} selector {} does not match any of \
                             the {}.  Known {}:",
                            func!(), obj, selector.args(), objs, objs);
                Self::list_matches(all);

                Err(anyhow::anyhow!(
                    "The specified selector ({}) doesn't match any of the {}",
                    selector.args(), objs))
            }
        } else if allowed_matches == AllowedMatches::One && matches.len() > 1 {
            // Want one match, but got multiple.
            log::debug!("{}: The {} selector {} matches multiple {}:",
                        func!(), obj, selector.args(), objs);
            Self::list_matches(matches);

            Err(anyhow::anyhow!(
                "Multiple {} match {}, try being more specific.",
                objs, selector.args()))
        } else {
            Ok(matches)
        }
    }

    /// Prints the items as a bulleted list on stderr.
    fn list_matches(items: Vec<KeyOrToken>) {
        let is_key = items.iter().next()
            .map(|o| o.is_key())
            .unwrap_or(false);

        let list_token = |t: &Token| -> String {
            format!("--backend {} --slot {} --token-label {:?} \
                     --token-serial-number {}",
                    t.backend().lib_short(), t.slot().id(), t.info().label(),
                    t.info().serial_number())
        };

        for obj in items.into_iter() {
            match obj {
                KeyOrToken::Key(key) => {
                    assert!(is_key);
                    let mut bits: Vec<Cow<str>> = Vec::new();
                    bits.push(list_token(&key.token()).into());
                    if let Some(key_unique_id) = key.key_unique_id() {
                        bits.push(Cow::Borrowed("--key-unique-id"));
                        bits.push(format!(
                            "{:?}", String::from_utf8_lossy(key_unique_id)).into());
                    }
                    if let Some(key_label) = key.key_label() {
                        bits.push(Cow::Borrowed("--key-label"));
                        bits.push(format!(
                            "{:?}", String::from_utf8_lossy(key_label)).into());
                    }
                    if let Some(key_id) = key.key_id() {
                        bits.push(Cow::Borrowed("--key-id"));
                        bits.push(format!(
                            "{:?}", String::from_utf8_lossy(key_id)).into());
                    }
                    if let Some(key_url) = key.key_url() {
                        bits.push(Cow::Borrowed("--key-url"));
                        bits.push(format!(
                            "{:?}", String::from_utf8_lossy(key_url)).into());
                    }
                    eprintln!("  - {}", bits.join(" "));
                }
                KeyOrToken::Token(token) => {
                    assert!(! is_key);
                    eprintln!("  - {}", list_token(&token));
                }
            }
        }
    }

    /// Returns an iterator over all of the tokens.
    pub fn tokens(&self) -> Result<impl Iterator<Item=Token>> {
        let matches = self.select_internal(
            &KeySelector::unconstrained(), false,
            AllowedMatches::Any, SelectorScope::PublicKeys,
            // Resolve composite keys.
            false)?;

        Ok(matches
           .into_iter()
           .map(|obj| obj.into_token_unwrap()))
    }

    /// Selects the unique token designated by `selector`.
    ///
    /// Returns an error if no tokens or more than one token matches
    /// the selector.
    pub fn select_one_token(&self, selector: &TokenSelector)
        -> Result<Token>
    {
        let key_selector
            = KeySelector::from_token_selector(selector.clone());
        let matches = self.select_internal(&key_selector, false,
                                           AllowedMatches::One,
                                           SelectorScope::All,
                                           false)?;

        assert_eq!(matches.len(), 1);

        let token = matches.into_iter().next().unwrap().into_token_unwrap();

        Ok(token)
    }

    /// Returns an iterator over all of the keys.
    pub fn keys(&self) -> Result<impl Iterator<Item=Key>> {
        let matches = self.select_internal(
            &KeySelector::unconstrained(), true,
            AllowedMatches::Any, SelectorScope::PublicKeys,
            // Resolve composite keys.
            true)?;

        Ok(matches
           .into_iter()
           .map(|obj| obj.into_key_unwrap()))
    }

    /// Select the unique key designated by `selector`.
    ///
    /// Returns an error if no keys or more than one key matches the
    /// selector.
    pub fn select_one_key(&self, selector: &KeySelector, scope: SelectorScope)
        -> Result<Key>
    {
        let matches = self.select_internal(
            &selector, true, AllowedMatches::One, scope,
            // Resolve composite keys.
            true)?;

        assert_eq!(matches.len(), 1);

        let key = matches.into_iter().next().unwrap().into_key_unwrap();

        Ok(key)
    }

    /// Selects the keys designated by `selector`.
    ///
    /// Returns `Ok(vec![])` if there are no matches.  That is, no
    /// matches is not an error.
    pub fn select_keys(&self, selector: &KeySelector, scope: SelectorScope)
        -> Result<Vec<Key>>
    {
        let matches = self.select_internal(
            &selector, true, AllowedMatches::Any, scope,
            // Resolve composite keys.
            true)?;

        let keys = matches
            .into_iter()
            .map(|obj| obj.into_key_unwrap())
            .collect::<Vec<Key>>();

        Ok(keys)
    }

    /// Returns an error if any keys have the specified label.
    pub fn check_no_keys_have_label(&self, label: &str)
        -> Result<()>
    {
        tracer!(TRACE, "config::check_no_keys_have_label");
        t!("Checking that the key label {} is unique", label);

        let selector = KeySelector::from_key_label(label);
        self.select_internal(&selector, true,
                             AllowedMatches::None,
                             SelectorScope::All,
                             // Don't resolve composite keys.
                             false)?;

        Ok(())
    }

    /// Returns an error if any keys have the specified key ID.
    pub fn check_no_keys_have_id(&self, id: &str)
        -> Result<()>
    {
        tracer!(TRACE, "config::check_no_keys_have_id");
        t!("Checking that the key ID {} is unique", id);

        let selector = KeySelector::from_key_id(id);
        self.select_internal(&selector, true,
                             AllowedMatches::None,
                             SelectorScope::All,
                             // Don't resolve composite keys.
                             false)?;

        Ok(())
    }
}
