sequoia-cert-store 0.7.3

use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::collections::VecDeque;
use std::str;
use std::sync::RwLock;
use std::sync::{RwLockReadGuard, RwLockWriteGuard};

use sequoia_openpgp as openpgp;
use openpgp::Fingerprint;
use openpgp::Result;
use openpgp::packet::UserID;

use crate::store::StoreError;
use crate::store::UserIDQueryParams;

use super::TRACE;

/// A helper data structure for implementations of [`Store`].
///
/// This data structure maintains an in-memory index of User IDs and
/// email addresses, and maps them to fingerprints.  It is a
/// convenient helper for a [`Store`] implementing
/// [`Store::select_userid`].
///
/// [`Store`]: crate::Store
/// [`Store::select_userid`]: crate::Store::select_userid
///
/// This data structure returns certificates with a given User ID or
/// email address in `O(log n)` time.  Substring and case insensitive
/// matching, however, currently requires `O(n)` time.
pub struct UserIDIndex {
    inner: RwLock<UserIDIndexInner>,
}
assert_send_and_sync!(UserIDIndex);

pub(crate) struct UserIDIndexInner {
    by_userid: BTreeMap<UserID, BTreeSet<Fingerprint>>,

    // The *normalized* email.
    //
    // XXX: As we also want to search by domain, it would be better to
    // use a different representation / different data structure to
    // avoid having to do a full scan.  One possibility would be to
    // use a `BTreeMap::range`.  That requires a bit of gymnastics.
    // Alternatively we could use a trie, which is keyed on (domain,
    // localpart).
    by_email: BTreeMap<String, BTreeSet<Fingerprint>>,
    // Because extracting the email address is expensive, we wait
    // until a caller actually needs `by_email`.  In particular, when
    // used in a one-shot context, `by_email` is not access at all.
    by_email_pending: VecDeque<(UserID, Fingerprint)>,
}

impl UserIDIndexInner {
    /// Inserts the given mapping.
    ///
    /// `email` is the canonicalized email address.  If that hasn't
    /// been computed, hand in `None`, and it will be computed on
    /// demand.
    pub(crate) fn insert(&mut self,
                         fp: Fingerprint,
                         userid: UserID,
                         email: Option<String>)
    {
        if let Some(email) = email {
            self.by_email
                .entry(email)
                .or_default()
                .insert(fp.clone());
        } else {
            self.by_email_pending
                .push_back((userid.clone(), fp.clone()));
        }

        self.by_userid
            .entry(userid)
            .or_default()
            .insert(fp);
    }
}

impl Default for UserIDIndex {
    fn default() -> Self {
        UserIDIndex {
            inner: RwLock::new(UserIDIndexInner {
                by_userid: Default::default(),
                by_email: Default::default(),
                by_email_pending: VecDeque::new(),
            }),
        }
    }
}

impl FromIterator<(Fingerprint, UserID, Option<String>)> for UserIDIndex {
    fn from_iter<I: IntoIterator<Item=(Fingerprint, UserID, Option<String>)>>(iter: I) -> Self {
        let index = UserIDIndex::default();

        let mut inner = index.inner.write().unwrap();
        for (fp, userid, email) in iter {
            inner.insert(fp, userid, email);
        }
        drop(inner);

        index
    }
}

impl UserIDIndex {
    /// Returns a new, empty UserIDIndex.
    pub fn new() -> Self {
        Self::default()
    }

    /// Adds an entry to UserIDIndex.
    ///
    /// This does *not* support removing mappings from the index.
    /// That is, if this function is called with the same fingerprint,
    /// but a User ID is removed, then the User ID is not removed from
    /// the index.  Normally, this doesn't matter as User IDs are not
    /// removed (certificates are append only data structures).
    pub fn insert<I>(&mut self, fpr: &Fingerprint, userids: I)
        where I: Iterator<Item=UserID>
    {
        let mut inner = self.inner.write().unwrap();

        for userid in userids {
            inner.by_userid
                .entry(userid.clone())
                .or_default()
                .insert(fpr.clone());

            inner.by_email_pending
                .push_back((userid, fpr.clone()));
        }
    }

    /// Executes any pending insertions.
    ///
    /// This needs to be called before accessing by_email.
    fn execute_pending_insertions(&'_ self) -> RwLockReadGuard<'_, UserIDIndexInner> {
        loop {
            // First, check if we have anything to do.
            let inner = self.inner.read().unwrap();
            if inner.by_email_pending.is_empty() {
                return inner;
            }
            drop(inner);

            // Looks like we do.  Get the writer lock.
            let mut inner = self.inner.write().unwrap();
            let mut pending = std::mem::take(&mut inner.by_email_pending);
            for (userid, fpr) in pending.drain(..) {
                if let Ok(Some(email)) = userid.email_normalized() {
                    inner.by_email
                        .entry(email)
                        .or_default()
                        .insert(fpr.clone());
                }
            }

            // std::sync::RwLock doesn't implement downgrading a
            // writer lock to a reader lock, so we loop.
            drop(inner);
        }
    }

    /// An implementation of [`Store::select_userid`].
    ///
    /// [`Store::select_userid`]: crate::Store::select_userid
    pub fn select_userid(&self, params: &UserIDQueryParams, pattern: &str)
        -> Result<Vec<Fingerprint>>
    {
        tracer!(TRACE, "UserIDIndex::select_userid");
        t!("params: {:?}, pattern: {:?}", params, pattern);

        // XXX: If you change this function,
        // UserIDQueryParams::select_userid contains similar code.
        // Update that too.
        let mut matches = match params {
            UserIDQueryParams {
                anchor_start: true,
                anchor_end: true,
                email: false,
                ignore_case: false,
            } => {
                // Exact User ID match.
                let userid = UserID::from(pattern);
                let inner = self.inner.read().unwrap();
                inner.by_userid.get(&userid)
                    .ok_or_else(|| {
                        StoreError::NoMatches(pattern.into())
                    })?
                    .iter()
                    .cloned()
                    .collect()
            }

            UserIDQueryParams {
                anchor_start: true,
                anchor_end: true,
                email: true,
                ignore_case: false,
            } => {
                // Exact email match.
                let inner = self.execute_pending_insertions();
                inner.by_email
                    .get(pattern)
                    .ok_or_else(|| {
                        StoreError::NoMatches(pattern.into())
                    })?
                    .iter()
                    .cloned()
                    .collect()
            }

            UserIDQueryParams {
                anchor_start,
                anchor_end,
                email,
                ignore_case,
            } => {
                // Substring search.
                let mut pattern = pattern;

                let _pattern;
                if *ignore_case {
                    // Convert to lowercase without tailoring,
                    // i.e. without taking any locale into account.
                    // See:
                    //
                    //  - https://www.w3.org/International/wiki/Case_folding
                    //  - https://doc.rust-lang.org/std/primitive.str.html#method.to_lowercase
                    //  - http://www.unicode.org/versions/Unicode7.0.0/ch03.pdf#G33992
                    _pattern = pattern.to_lowercase();
                    pattern = &_pattern[..];
                }

                // Checks if user id a match.
                let check = |userid: &str| -> bool {
                    let mut userid = userid;
                    let _userid: String;
                    if *ignore_case {
                        _userid = userid.to_lowercase();
                        userid = &_userid[..];
                    }

                    t!("Considering if {:?} matches {:?} \
                        (anchors: {}, {}, ignore case: {})",
                       pattern, userid, anchor_start, anchor_end,
                       ignore_case);

                    // XXX: Consider using
                    // https://crates.io/crates/memchr instead.
                    if match (*anchor_start, *anchor_end) {
                        (true, true) => userid == pattern,
                        (true, false) => userid.starts_with(pattern),
                        (false, true) => userid.ends_with(pattern),
                        (false, false) => userid.contains(pattern),
                    }
                    {
                        t!("*** {:?} matches {:?} (anchors: {}, {})",
                           pattern, userid, *anchor_start, anchor_end);
                        true
                    } else {
                        false
                    }
                };

                if *email {
                    let inner = self.execute_pending_insertions();
                    inner.by_email
                        .iter()
                        .filter_map(|(email, matches)| {
                            if check(email) {
                                Some(matches.iter())
                            } else {
                                None
                            }
                        })
                        .flatten()
                        .cloned()
                        .collect::<Vec<Fingerprint>>()
                } else {
                    let inner = self.inner.read().unwrap();
                    inner.by_userid
                        .iter()
                        .filter_map(|(userid, matches)| {
                            let userid = String::from_utf8_lossy(userid.value());
                            if check(&userid) {
                                Some(matches.iter())
                            } else {
                                None
                            }
                        })
                        .flatten()
                        .cloned()
                        .collect::<Vec<Fingerprint>>()
                }
            }
        };

        if matches.is_empty() {
            return Err(StoreError::NoMatches(pattern.into()).into());
        }

        matches.sort();
        matches.dedup();

        Ok(matches)
    }

    /// Returns a write-locked reference to the inner.
    ///
    /// Can be used to insert in bulk.
    pub(crate) fn inner_mut(&'_ self) -> RwLockWriteGuard<'_, UserIDIndexInner> {
        self.inner.write().unwrap()
    }
}