relateby-pattern 0.4.0

//! Property-based tests for Pattern Hash/Eq consistency
//!
//! These tests use proptest to verify that pattern hashing is consistent with equality:
//! if p1 == p2, then hash(p1) == hash(p2) for all patterns p1, p2
//!
//! This is a fundamental requirement for correct HashMap/HashSet behavior.

use pattern_core::{Pattern, Symbol};
use proptest::prelude::*;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

// ============================================================================
// Helper Functions
// ============================================================================

/// Computes the hash of a pattern using the default hasher
fn hash_pattern<V: Hash>(p: &Pattern<V>) -> u64 {
    let mut hasher = DefaultHasher::new();
    p.hash(&mut hasher);
    hasher.finish()
}

// ============================================================================
// Pattern Generators
// ============================================================================

/// Strategy for generating atomic patterns (no elements)
fn atomic_pattern() -> impl Strategy<Value = Pattern<String>> {
    any::<String>().prop_map(Pattern::point)
}

/// Strategy for generating shallow patterns (1-2 levels, 1-5 elements)
fn shallow_pattern() -> impl Strategy<Value = Pattern<String>> {
    (
        any::<String>(),
        prop::collection::vec(atomic_pattern(), 0..=5),
    )
        .prop_map(|(value, elements)| Pattern::pattern(value, elements))
}

/// Strategy for generating patterns with varying depths (0-10 levels)
fn varying_depth_pattern(max_depth: u32) -> BoxedStrategy<Pattern<String>> {
    let leaf = any::<String>().prop_map(Pattern::point).boxed();

    leaf.prop_recursive(
        max_depth, // Max depth
        256,       // Max nodes
        10,        // Items per collection
        |inner| {
            (any::<String>(), prop::collection::vec(inner, 0..=5))
                .prop_map(|(value, elements)| Pattern::pattern(value, elements))
                .boxed()
        },
    )
    .boxed()
}

/// Strategy for generating Symbol patterns
fn symbol_pattern() -> impl Strategy<Value = Pattern<Symbol>> {
    any::<String>()
        .prop_map(|s| Symbol(s))
        .prop_map(Pattern::point)
}

// ============================================================================
// Hash/Eq Consistency Tests
// ============================================================================

proptest! {
    /// Test that equal atomic patterns hash to the same value
    #[test]
    fn test_hash_eq_consistency_atomic(
        value in any::<String>(),
    ) {
        let p1 = Pattern::point(value.clone());
        let p2 = Pattern::point(value);

        let hash1 = hash_pattern(&p1);
        let hash2 = hash_pattern(&p2);

        prop_assert_eq!(p1, p2, "Patterns should be equal");
        prop_assert_eq!(
            hash1,
            hash2,
            "Equal patterns must hash to same value"
        );
    }
}

proptest! {
    /// Test that equal shallow patterns hash to the same value
    #[test]
    fn test_hash_eq_consistency_shallow(
        p1 in shallow_pattern(),
    ) {
        let p2 = p1.clone();

        let hash1 = hash_pattern(&p1);
        let hash2 = hash_pattern(&p2);

        prop_assert_eq!(p1, p2);
        prop_assert_eq!(hash1, hash2);
    }
}

proptest! {
    /// Test that equal nested patterns hash to the same value
    #[test]
    fn test_hash_eq_consistency_nested(
        p1 in varying_depth_pattern(10),
    ) {
        let p2 = p1.clone();

        // Compute hashes before comparison (which consumes values)
        let hash1 = hash_pattern(&p1);
        let hash2 = hash_pattern(&p2);

        prop_assert_eq!(p1, p2);
        prop_assert_eq!(
            hash1,
            hash2,
            "Equal nested patterns must hash to same value"
        );
    }
}

proptest! {
    /// Test hash consistency for Symbol patterns
    #[test]
    fn test_hash_eq_consistency_symbol(
        value in any::<String>(),
    ) {
        let p1 = Pattern::point(Symbol(value.clone()));
        let p2 = Pattern::point(Symbol(value));

        let hash1 = hash_pattern(&p1);
        let hash2 = hash_pattern(&p2);

        prop_assert_eq!(p1, p2);
        prop_assert_eq!(hash1, hash2);
    }
}

// ============================================================================
// Structure Distinguishes Hash Tests
// ============================================================================

proptest! {
    /// Test that atomic and compound patterns with same value likely hash differently
    ///
    /// Note: Hash collision is technically possible but extremely unlikely.
    /// This test catches obvious implementation bugs where structure is ignored.
    #[test]
    fn test_structure_distinguishes_hash(
        value in any::<String>(),
        child_value in any::<String>(),
    ) {
        let atomic = Pattern::point(value.clone());
        let compound = Pattern::pattern(
            value,
            vec![Pattern::point(child_value)]
        );

        if atomic != compound {
            // Different patterns should likely have different hashes
            // (not guaranteed due to hash collisions, but expected)
            let hash1 = hash_pattern(&atomic);
            let hash2 = hash_pattern(&compound);

            // We don't assert inequality (hash collisions are possible)
            // but we do check that they're not equal patterns
            prop_assert_ne!(atomic, compound, "Patterns should differ");

            // For most inputs, hashes should differ
            // This catches bugs where structure is completely ignored
            // We accept this test might rarely pass even with correct implementation
            if hash1 == hash2 {
                // Collision detected - acceptable but rare
                // Log but don't fail
            }
        }
    }
}

proptest! {
    /// Test that patterns with different element counts likely hash differently
    #[test]
    fn test_element_count_affects_hash(
        value in any::<String>(),
        child1 in any::<String>(),
        child2 in any::<String>(),
    ) {
        let p1 = Pattern::pattern(
            value.clone(),
            vec![Pattern::point(child1.clone())]
        );
        let p2 = Pattern::pattern(
            value,
            vec![Pattern::point(child1), Pattern::point(child2)]
        );

        // Compute hashes before comparison
        let hash1 = hash_pattern(&p1);
        let hash2 = hash_pattern(&p2);

        prop_assert_ne!(p1, p2, "Patterns with different element counts should differ");

        // We check they're not equal patterns (the important part)
        // Hash inequality is expected but not required
        if hash1 == hash2 {
            // Collision - rare but acceptable
        }
    }
}

// ============================================================================
// Reflexive Hash Tests
// ============================================================================

proptest! {
    /// Test that a pattern hashes to the same value when hashed multiple times
    #[test]
    fn test_hash_reflexive(
        p in varying_depth_pattern(10),
    ) {
        let hash1 = hash_pattern(&p);
        let hash2 = hash_pattern(&p);

        prop_assert_eq!(hash1, hash2, "Same pattern should always hash to same value");
    }
}

proptest! {
    /// Test hash reflexivity for deeply nested patterns
    #[test]
    fn test_hash_reflexive_deep(
        p in varying_depth_pattern(50),
    ) {
        let hash1 = hash_pattern(&p);
        let hash2 = hash_pattern(&p);

        prop_assert_eq!(hash1, hash2);
    }
}