prehash 1.0.0

//
// Copyright (C) 2023 Nathan Sharp.
//
// This Source Code Form is subject to the terms of the Mozilla Public License,
// v. 2.0. If a copy of the MPL was not distributed with this file, You can
// obtain one at https://mozilla.org/MPL/2.0/
//
// This Source Code Form is "Incompatible With Secondary Licenses", as defined
// by the Mozilla Public License, v. 2.0.
//

#![cfg_attr(not(feature = "std"), no_std)]
#![cfg_attr(feature = "doc_cfg", feature(doc_cfg))]

//! The `prehash` crate provides the type [`Prehashed`], which stores a value of
//! any type along with a precomputed hash. This makes it possible to avoid
//! computing large expensive hashes many times, for example when searching for
//! a particular value in a variety of hash tables.
//!
//! The crate also defines an extremely simple [`Hasher`], [`Passthru`], which
//! is tailor built for use with [`Prehashed`]. If the `std` feature is
//! selected (which is done by default), type definitions and constructors are
//! provided for the standard [`HashMap`] and [`HashSet`] collections which
//! combine [`Prehashed`] keys/elements with the [`Passthru`] hasher for optimum
//! performance.
//!
//! # Example
//! ```
//! # #[cfg(feature = "std")] {
//! use prehash::{new_prehashed_set, DefaultPrehasher, Prehasher};
//!
//! let prehasher = DefaultPrehasher::new();
//! let mut zeros = new_prehashed_set();
//! let mut evens = new_prehashed_set();
//! let mut odds = new_prehashed_set();
//!
//! // 'evens' and 'odds' are going to re-hash a couple times, but they'll only
//! // need to recompute the hashes of their keys once. (The rehashing process
//! // does provide some resilience against denial-of-service attacks in some
//! // theoretical cases, but the primary form of resilience comes from using an
//! // unpredictable hash function in the first place.)
//!
//! zeros.insert(prehasher.prehash(0));
//!
//! for num in 0..100000 {
//!     if num % 2 == 0 {
//!         evens.insert(prehasher.prehash(num));
//!     } else {
//!         odds.insert(prehasher.prehash(num));
//!     }
//! }
//!
//! for num in 0..100000 {
//!     // We only have to compute the hash of 'num' once, despite checking it
//!     // against three different sets. This would be a big deal if computing
//!     // the hash of 'num' is expensive.
//!     let prehashed = prehasher.prehash(num);
//!
//!     if zeros.contains(&prehashed) {
//!         assert_eq!(num, 0)
//!     }
//!
//!     if evens.contains(&prehashed) {
//!         assert_eq!(num % 2, 0);
//!     }
//!
//!     if odds.contains(&prehashed) {
//!         assert_eq!(num % 2, 1);
//!     }
//! }
//!
//! # }
//! ```
//!
//! # License
//!`prehash` is licensed under the terms of the
//! [Mozilla Public License, v. 2.0][MPL]. All Source Code Forms are
//! "Incompatible With Secondary Licenses", as described in *§3.3* of the
//! license.
//!
//! # Development
//! `prehash` is developed at [GitLab].
//!
//! [GitLab]: https://gitlab.com/nwsharp/prehash
//! [`HashMap`]: std::collections::HashMap
//! [`HashSet`]: std::collections::HashSet
//! [MPL]: https://mozilla.org/MPL/2.0

use core::fmt::{self, Display, Formatter};
use core::hash::{BuildHasher, BuildHasherDefault, Hash, Hasher};
use core::ops::Deref;

#[cfg(feature = "std")]
mod std_utils;

#[cfg(feature = "std")]
pub use std_utils::*;

/// A value (of type `T`) stored along with a precomputed hash (of type `H`,
/// which defaults to [`u64`]).
///
/// When a [hash] of this value is requested, the stored precomputed hash is
/// hashed instead of the value itself. However, when an [equality] test is
/// requested, the contained value is used.
///
/// `Prehashed` values are unaware of the hash algorithm used to compute the
/// hash. Algorithms may misbehave if used with `Prehashed` values created by
/// different [hashers].
///
/// # Example
/// See the [crate-level documentation].
///
/// [crate-level documentation]: crate#Example
/// [equality]: core::cmp::PartialEq::eq
/// [hash]: core::hash::Hash::hash
/// [hashers]: core::hash::Hasher
#[derive(Copy, Debug)]
pub struct Prehashed<T: ?Sized, H = u64> {
    hash: H,
    value: T,
}

impl<T: ?Sized, H> Prehashed<T, H> {
    /// Returns references to the value and its precomputed hash.
    ///
    /// # Invocation
    /// This is an associated function, so it is invoked like
    /// `Prehashed::as_parts(prehashed)`. This is so this method does not
    /// interfere with [automatic dereferencing] as the contained value.
    ///
    /// # Notes
    /// If the value or hash are [interiorly mutable], it is possible to cause a
    /// mismatch between the precomputed hash and the value. This may cause
    /// certain algorithms to malfunction.
    ///
    /// [automatic dereferencing]: core::ops::Deref
    /// [interiorly mutable]: core::cell
    #[must_use]
    pub fn as_parts(pre: &Self) -> (&T, &H) {
        (&pre.value, &pre.hash)
    }

    /// Returns a reference to the contained value.
    ///
    /// # Invocation
    /// This is an associated function, so it is invoked like
    /// `Prehashed::as_inner(prehashed)`. This is so this method does not
    /// interfere with [automatic dereferencing] as the contained value.
    ///
    /// # Notes
    /// If the value is [interiorly mutable], it is possible to cause a mismatch
    /// between the precomputed hash and the value. This may cause certain
    /// algorithms to malfunction.
    ///
    /// [automatic dereferencing]: core::ops::Deref
    /// [interiorly mutable]: core::cell
    #[must_use]
    pub fn as_inner(pre: &Self) -> &T {
        Self::as_parts(pre).0
    }

    /// Returns a reference to the contained hash.
    ///
    /// # Invocation
    /// This is an associated function, so it is invoked like
    /// `Prehashed::as_hash(prehashed)`. This is so this method does not
    /// interfere with [automatic dereferencing] as the contained value.
    ///
    /// # Notes
    /// If the hash is [interiorly mutable], it is possible to cause a mismatch
    /// between the precomputed hash and the value. This may cause certain
    /// algorithms to malfunction.
    ///
    /// [automatic dereferencing]: core::ops::Deref
    /// [interiorly mutable]: core::cell
    #[must_use]
    pub fn as_hash(pre: &Self) -> &H {
        Self::as_parts(pre).1
    }
}

impl<T, H> Prehashed<T, H> {
    /// Creates a new `Prehashed` object from the specified value and
    /// precomputed hash.
    #[must_use]
    pub const fn new(value: T, hash: H) -> Self {
        Self { hash, value }
    }

    /// Deconstructs the `Prehashed` object into the value and its precomputed
    /// hash.
    ///
    /// These parts can be passed to [`new`] to reconstruct the original
    /// `Prehashed` object.
    ///
    /// # Invocation
    /// This is an associated function, so it is invoked like
    /// `Prehashed::into_parts(prehashed)`. This is so this method does not
    /// interfere with [automatic dereferencing] as the contained value.
    ///
    /// [automatic dereferencing]: core::ops::Deref
    /// [`new`]: Prehashed::new
    #[must_use]
    pub fn into_parts(pre: Self) -> (T, H) {
        (pre.value, pre.hash)
    }

    /// Deconstructs the `Prehashed` object and returns the contained value.
    ///
    /// The precomputed hash is [discarded].
    ///
    /// # Invocation
    /// This is an associated function, so it is invoked like
    /// `Prehashed::into_inner(prehashed)`. This is so this method does not
    /// interfere with [automatic dereferencing] as the contained value.
    ///
    /// [automatic dereferencing]: core::ops::Deref
    /// [discarded]: core::ops::Drop::drop
    #[must_use]
    pub fn into_inner(pre: Self) -> T {
        Self::into_parts(pre).0
    }
}

impl<T: Hash> Prehashed<T, u64> {
    /// Constructs a `Prehashed` object by hashing a value with the
    /// [default hasher].
    ///
    /// # Security
    /// Consider using [`with_builder`] if [collision-based denial of service
    /// attacks][DoS] are a potential concern.
    ///
    /// [DoS]: https://en.wikipedia.org/w/index.php?title=Collision_attack&oldid=971803090#Usage_in_DoS_attacks
    /// [default hasher]: std::collections::hash_map::DefaultHasher
    /// [`with_builder`]: Self::with_builder
    #[cfg(feature = "std")]
    #[cfg_attr(feature = "doc_cfg", doc(cfg(feature = "std")))]
    #[must_use]
    pub fn with_default(value: T) -> Self {
        Self::with_hasher::<std::collections::hash_map::DefaultHasher>(value)
    }

    /// Constructs a `Prehashed` object by hashing a value with a default
    /// instance of the specified [`Hasher`] type, `H`.
    ///
    /// # Invocation
    /// You will need to use "turbofish operator" to invoke this method:
    /// `Prehashed::with_hasher::<Hasher>(value)`
    ///
    /// # Security
    /// Consider using [`with_builder`] if [collision-based denial of service
    /// attacks][DoS] are a potential concern.
    ///
    /// [DoS]: https://en.wikipedia.org/w/index.php?title=Collision_attack&oldid=971803090#Usage_in_DoS_attacks
    /// [`Hasher`]: core::hash::Hasher
    /// [`with_builder`]: Self::with_builder
    #[must_use]
    pub fn with_hasher<H: Default + Hasher>(value: T) -> Self {
        Self::with_builder(value, &BuildHasherDefault::<H>::default())
    }

    /// Constructs a `Prehashed` object by hashing a value with a hasher created
    /// the specified builder.
    #[must_use]
    pub fn with_builder<B: BuildHasher + ?Sized>(value: T, build: &B) -> Self {
        let mut hasher = build.build_hasher();
        value.hash(&mut hasher);
        Self::new(value, hasher.finish())
    }
}

impl<T: PartialEq + ?Sized, H: Eq> Prehashed<T, H> {
    /// Compares two `Prehashed` values for equality, using the precomputed hash
    /// to quickly test for inequality.
    ///
    /// # Invocation
    /// This is an associated function, so it is invoked like
    /// `Prehashed::fast_eq(a, b)`. This is so this method does not interfere
    /// with [automatic dereferencing] as the contained value.
    ///
    /// # Notes
    /// The [`PartialEq`] implementation for `Prehashed` does not check the hash
    /// value for early inequality because this would slow down algorithms which
    /// execute a deep equality test only once a hash equality test has
    /// indicated possible equivalence. In that sense, `fast_eq` strictly
    /// slower if the hashes have already been tested for equality.
    ///
    /// [automatic dereferencing]: core::ops::Deref
    /// [`PartialEq`]: core::cmp::PartialEq
    #[must_use]
    pub fn fast_eq(lhs: &Self, rhs: &Self) -> bool {
        lhs.hash.eq(&rhs.hash) && lhs.value.eq(&rhs.value)
    }
}

impl<T: ?Sized, H> AsRef<T> for Prehashed<T, H> {
    fn as_ref(&self) -> &T {
        Self::as_inner(self)
    }
}

impl<T: Copy + ?Sized, H: Copy> Clone for Prehashed<T, H> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<T: ?Sized, H> Deref for Prehashed<T, H> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        Self::as_inner(self)
    }
}

impl<T: Display + ?Sized, H> Display for Prehashed<T, H> {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        self.value.fmt(f)
    }
}

impl<T: Eq + ?Sized, H> Eq for Prehashed<T, H> {}

impl<T: ?Sized, H: Hash> Hash for Prehashed<T, H> {
    fn hash<S: Hasher>(&self, state: &mut S) {
        self.hash.hash(state)
    }
}

impl<T: PartialEq + ?Sized, H> PartialEq for Prehashed<T, H> {
    fn eq(&self, other: &Self) -> bool {
        self.value.eq(&other.value)
    }
}

impl<T: PartialEq + ?Sized, H> PartialEq<T> for Prehashed<T, H> {
    fn eq(&self, other: &T) -> bool {
        self.value.eq(other)
    }
}

/// A convenience trait for producing `Prehashed` values from any
/// [hasher builder].
///
/// To take advantage of this convenience trait, simply write:
/// ```
/// use prehash::Prehasher;
/// ```
///
/// [hasher builder]: core::hash::BuildHasher
pub trait Prehasher {
    /// The type produced by hashing.
    type Hash;

    /// Create a prehashed value by hashing the specified value.
    #[must_use]
    fn prehash<T: Hash>(&self, value: T) -> Prehashed<T, Self::Hash>;
}

impl<B: BuildHasher> Prehasher for B {
    type Hash = u64;

    fn prehash<T: Hash>(&self, value: T) -> Prehashed<T, Self::Hash> {
        Prehashed::with_builder(value, self)
    }
}

/// A [`Hasher`] implementation which returns the last [`u64`] written.
///
/// ⚠️ All methods besides [`write_u64`] and [`finish`] panic if invoked.
///
/// [`finish`]: Passthru::finish
/// [`Hasher`]: core::hash::Hasher
/// [`write_u64`]: Passthru::write_u64
#[derive(Debug)]
pub struct Passthru {
    hash: u64,
}

impl Passthru {
    /// Constructs a new pass-through hasher.
    ///
    /// # Notes
    /// The hasher will return `0` from [`finish`] if [`write_u64`] is never
    /// called.
    ///
    /// [`finish`]: Passthru::finish
    /// [`write_u64`]: Passthru::write_u64
    #[must_use]
    pub fn new() -> Self {
        Self { hash: 0 }
    }
}

impl Default for Passthru {
    fn default() -> Self {
        Self::new()
    }
}

impl Hasher for Passthru {
    fn write(&mut self, _bytes: &[u8]) {
        panic!("unsupported operation");
    }

    fn write_u64(&mut self, i: u64) {
        self.hash = i;
    }

    fn finish(&self) -> u64 {
        self.hash
    }
}