big-code-analysis 2.1.0

//! Hashing for the collections on the metric walk that are keyed by
//! integers this crate produced itself.
//!
//! Two of them are hot enough to matter: the node-id keyed
//! [`NestingMap`](crate::spaces::NestingMap) the walker threads through
//! `Cognitive`, and the `kind_id`-keyed operator map in
//! [`HalsteadMaps`](crate::metrics::halstead::HalsteadMaps). The first
//! is probed at least once per AST node; the second once per node the
//! language's `Getter` classifies as a non-primitive operator, which
//! over the corpus repositories works out at roughly one probe per 15
//! bytes of source.
//!
//! `Ploc` / `Cloc`'s per-space line sets used to be the third. They are
//! now a word-array bitset ([`crate::metrics::loc`]), which hashes
//! nothing at all — line numbers are dense, so the table was paying for
//! a probe per row where a bit index does (#1109).
//!
//! Halstead's two *other* per-space maps — `primitive_operators` and
//! `operands` — are keyed by source text and deliberately stay on the
//! standard-library SipHash. They are just as hot, but their keys are
//! identifiers and literals lifted verbatim out of the file being
//! analysed, which for this crate *is* the untrusted input: `bca` runs
//! over whatever a repository contains and `bca-web` accepts source in
//! a request body. That is precisely the hash-flooding case the note on
//! [`IntKeyHasher`] rules out, so the flooding resistance is
//! load-bearing there and the SipHash round is the price of it.

use std::collections::HashMap;
use std::hash::{BuildHasherDefault, Hasher};

/// Hasher for maps and sets keyed by an integer this crate produced.
///
/// The keys are tree-sitter node ids (pointer-derived `usize` values),
/// and tree-sitter `kind_id` grammar symbols
/// (`u16`, drawn from a fixed per-grammar alphabet of at most a few
/// hundred values): all generated by us, never attacker-chosen. The
/// input being analysed selects *which* of them occur but cannot invent
/// new ones. The default SipHash-1-3 exists to resist
/// hash-flooding from untrusted *keys*, so on these collections it buys
/// nothing and costs a full keyed round per probe — on paths that run
/// several times per AST node.
///
/// This is FxHash as of `rustc-hash` 2.x, including the `finish` rotate
/// that 2.0 added. It is **not** collision-resistant and must not be
/// used for any collection whose keys come from user input.
#[derive(Default)]
pub(crate) struct IntKeyHasher {
    hash: u64,
}

impl IntKeyHasher {
    /// FxHash's multiplier. Being *odd* is the load-bearing property: it
    /// makes `n * SEED (mod 2^64)` a bijection, so distinct keys can
    /// never produce the same hash — and an arithmetic sequence such as
    /// a grammar's `kind_id` alphabet lands in distinct buckets more
    /// reliably than a random oracle would (see
    /// `int_key_hasher_spreads_consecutive_keys`).
    const SEED: u64 = 0x51_7c_c1_b7_27_22_0a_95;

    /// Rotate applied in `finish`. A multiplicative hash concentrates
    /// entropy in the *top* bits, but hashbrown takes the bucket index
    /// from the *bottom* ones. Node ids are pointer-aligned, so without
    /// this every hash would end in at least three zero bits and only
    /// one home bucket in eight would be reachable — cheap on x86-64,
    /// where the SSE2 probe group is 16 wide, but measurably worse on
    /// aarch64, whose NEON group is 8. Value matches `rustc-hash` 2.x.
    const FINISH_ROTATE: u32 = 26;

    #[inline]
    fn add(&mut self, word: u64) {
        self.hash = (self.hash.rotate_left(5) ^ word).wrapping_mul(Self::SEED);
    }
}

impl Hasher for IntKeyHasher {
    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        for byte in bytes {
            self.add(u64::from(*byte));
        }
    }

    // The integer writes are overridden so a key type change cannot
    // silently fall back to `write`'s byte-at-a-time loop, which would
    // cost eight dependent rounds per word and be slower than the
    // SipHash this replaced.
    #[inline]
    fn write_usize(&mut self, n: usize) {
        self.add(n as u64);
    }

    #[inline]
    fn write_u64(&mut self, n: u64) {
        self.add(n);
    }

    #[inline]
    fn write_u32(&mut self, n: u32) {
        self.add(u64::from(n));
    }

    #[inline]
    fn write_u16(&mut self, n: u16) {
        self.add(u64::from(n));
    }

    #[inline]
    fn write_u8(&mut self, n: u8) {
        self.add(u64::from(n));
    }

    #[inline]
    fn finish(&self) -> u64 {
        self.hash.rotate_left(Self::FINISH_ROTATE)
    }
}

/// [`HashMap`] keyed by a self-produced integer. See [`IntKeyHasher`]
/// for the precondition on the keys.
pub(crate) type IntKeyHashMap<K, V> = HashMap<K, V, BuildHasherDefault<IntKeyHasher>>;

#[cfg(test)]
mod tests {
    use std::hash::Hasher;

    use super::IntKeyHasher;

    /// `IntKeyHasher`'s integer writes must all agree for the same value.
    ///
    /// Two of the overrides are live: `HashMap<usize, _>` calls
    /// `write_usize` for the node-id keyed nesting map, and
    /// `HashMap<u16, _>` calls `write_u16` for Halstead's `kind_id`
    /// operator map. The rest are unreachable today and exist so that
    /// changing a key type (to `u64`, say, when the node id gains a
    /// newtype) cannot silently fall back to `Hasher::write`'s
    /// byte-at-a-time default, which costs one dependent round per byte
    /// and would be slower than the SipHash this replaced. That
    /// regression is invisible: results stay correct and only speed
    /// changes. This pins the equivalence so the fallback cannot creep
    /// back in unnoticed.
    #[test]
    fn int_key_hasher_integer_writes_agree() {
        let hash_of = |write: &dyn Fn(&mut IntKeyHasher)| {
            let mut h = IntKeyHasher::default();
            write(&mut h);
            h.finish()
        };

        // `639` is the largest `kind_id` any grammar in the workspace
        // emits (`mozcpp`). It is in the list because it is the only
        // entry above `255`: below that a `u16`'s leading byte is zero,
        // so on a big-endian target the byte-loop fallback collapses to
        // one effective round and the `write_u16` check below would pass
        // whether or not the override exists.
        for value in [
            0_u64,
            1,
            42,
            639,
            0x0123_4567,
            u64::from(u32::MAX),
            u64::MAX,
        ] {
            let via_u64 = hash_of(&|h| h.write_u64(value));

            // Each narrower write is checked only for the values it can
            // represent, so the test says the same thing on a 32-bit
            // target as on a 64-bit one instead of silently comparing a
            // truncated input.
            if let Ok(narrow) = usize::try_from(value) {
                assert_eq!(
                    hash_of(&|h| h.write_usize(narrow)),
                    via_u64,
                    "write_usize must agree for {value:#x}"
                );
            }
            if let Ok(narrow) = u32::try_from(value) {
                assert_eq!(
                    hash_of(&|h| h.write_u32(narrow)),
                    via_u64,
                    "write_u32 must agree for {value:#x}"
                );
            }
            // `write_u16` is the one that is *not* hypothetical: it is
            // the call `HashMap<u16, _>` makes for every `kind_id` probe
            // in `HalsteadMaps::operators`. Drop the override and the
            // default forwards to `write(&n.to_ne_bytes())`, which folds
            // two dependent rounds instead of one — so this assertion
            // fails rather than merely getting slower.
            if let Ok(narrow) = u16::try_from(value) {
                assert_eq!(
                    hash_of(&|h| h.write_u16(narrow)),
                    via_u64,
                    "write_u16 must agree for {value:#x}"
                );
            }
            if let Ok(narrow) = u8::try_from(value) {
                assert_eq!(
                    hash_of(&|h| h.write_u8(narrow)),
                    via_u64,
                    "write_u8 must agree for {value:#x}"
                );
            }
        }

        // The byte-slice path is the fallback the overrides exist to avoid.
        // It must still work, and must NOT coincide with the word writes —
        // if it did, the overrides would be pointless and their removal
        // would go unnoticed.
        let via_bytes = hash_of(&|h| h.write(&7_u64.to_ne_bytes()));
        assert_ne!(
            via_bytes,
            hash_of(&|h| h.write_u64(7)),
            "the byte loop folds one round per byte, so it cannot match the \
             single-round word write; if these ever agree, the overrides are \
             no longer doing anything"
        );
    }

    /// `finish` must rotate, not return the raw product.
    ///
    /// A multiplicative hash concentrates entropy in the top bits, but
    /// hashbrown takes the bucket index from the bottom ones — and node ids
    /// are pointer-aligned, so without the rotate every hash ends in at least
    /// three zero bits and only one home bucket in eight is reachable.
    /// `rustc-hash` added this in 2.0; a first cut of this hasher copied
    /// the 1.x algorithm and reproduced exactly the defect upstream removed.
    #[test]
    fn int_key_hasher_finish_rotates_entropy_down() {
        // Pointer-aligned ids, as tree-sitter produces.
        let low_bits_set = (1..64_usize).any(|i| {
            let mut h = IntKeyHasher::default();
            h.write_usize(i * 8);
            h.finish() & 0b111 != 0
        });
        assert!(
            low_bits_set,
            "every 8-aligned id hashed to a value with three zero low bits, so \
             only one home bucket in eight is reachable — `finish` is not \
             rotating"
        );
    }

    /// Consecutive keys — the pattern a grammar's `kind_id` alphabet
    /// feeds Halstead's operator map — must spread at least as well as a
    /// random oracle.
    ///
    /// Node ids arrive scattered and 8-aligned; `kind_id`s arrive dense
    /// and starting at zero, which is the pattern a hash that folded
    /// away the low input bits would degenerate on. Multiplying an
    /// arithmetic sequence by an odd constant does the opposite: it
    /// spreads *better* than random, because a random hash wastes
    /// buckets on coincidental collisions and this one cannot produce
    /// them until the rotate's bit window wraps.
    ///
    /// Run at 1 000 keys rather than a grammar's few hundred so the
    /// property is measured with the table under real load.
    #[test]
    fn int_key_hasher_spreads_consecutive_keys() {
        // A thousand dense keys, in the table hashbrown would hold them
        // in: capacity rounds up to a power of two above `keys / 0.875`.
        // Typed `u16` so the keys go through `write_u16`, the call
        // `HashMap<u16, _>` actually makes for a `kind_id`.
        const KEYS: u16 = 1_000;
        const BUCKETS: usize = 2_048;
        // Bounds a random hash does *not* clear on this input: it fills
        // ~813 of the buckets and piles 4 keys on its worst one.
        const MIN_DISTINCT_BUCKETS: usize = 900;
        const MAX_PER_BUCKET: usize = 3;

        let mut depth = vec![0_usize; BUCKETS];
        for key in 0..KEYS {
            let mut h = IntKeyHasher::default();
            h.write_u16(key);
            // Reduce first, so the index provably fits whatever width
            // `usize` has on the host.
            let bucket = usize::try_from(h.finish() % BUCKETS as u64)
                .expect("a value reduced modulo BUCKETS is below 2^16");
            depth[bucket] += 1;
        }
        let distinct = depth.iter().filter(|d| **d > 0).count();
        let deepest = depth.iter().copied().max().unwrap_or(0);
        assert!(
            distinct >= MIN_DISTINCT_BUCKETS && deepest <= MAX_PER_BUCKET,
            "keys 0..{KEYS} reached {distinct} of {BUCKETS} buckets with at \
             most {deepest} per bucket; expected at least \
             {MIN_DISTINCT_BUCKETS} and at most {MAX_PER_BUCKET} — the hasher \
             is clustering dense integer keys"
        );
    }
}