llvm-native-core 0.1.14

//! FoldingSet — Hash-consed uniquing set for deduplicating AST/IR nodes.
//!
//! A FoldingSet stores objects by content hash and ensures only one copy
//! of each unique object exists. Used heavily in LLVM for:
//! - Type uniquing (only one i32 type exists)
//! - Constant folding (only one constant 42 exists)
//! - SelectionDAG node uniquing
//!
//! Clean-room behavioral reconstruction. No LLVM source is consulted.

use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::marker::PhantomData;

// ═══════════════════════════════════════════════════════════════════════════
// FoldingSet
// ═══════════════════════════════════════════════════════════════════════════

/// A hash-consed set that ensures at most one copy of each unique object.
///
/// Objects are stored by hash; insertions that match an existing object
/// return the existing one instead of creating a duplicate.
pub struct FoldingSet<T: FoldingSetNode> {
    /// The underlying hash table mapping hashes to nodes.
    nodes: HashMap<u64, Vec<T>>,
    /// Number of nodes currently in the set.
    size: usize,
}

/// Trait required for objects to be stored in a FoldingSet.
pub trait FoldingSetNode: Clone + Eq + Hash {
    /// Compute a profile (hash) of this node's content.
    /// Two nodes that are equal must have the same profile.
    fn profile(&self) -> u64;

    /// Compare this node's content to another for equality.
    fn equals(&self, other: &Self) -> bool {
        self == other
    }
}

impl<T: FoldingSetNode> FoldingSet<T> {
    /// Create an empty folding set.
    pub fn new() -> Self {
        Self {
            nodes: HashMap::new(),
            size: 0,
        }
    }

    /// Insert a node. If an identical node already exists, returns the
    /// existing one and discards the new one. Otherwise inserts and
    /// returns the new one.
    pub fn insert(&mut self, node: T) -> T {
        let profile = node.profile();
        let bucket = self.nodes.entry(profile).or_insert_with(Vec::new);

        // Check for existing match
        for existing in bucket.iter() {
            if node.equals(existing) {
                return existing.clone();
            }
        }

        // No match — insert
        bucket.push(node.clone());
        self.size += 1;
        node
    }

    /// Try to find a node matching the given profile.
    pub fn find(&self, profile: u64, equals_fn: impl Fn(&T) -> bool) -> Option<&T> {
        self.nodes
            .get(&profile)
            .and_then(|bucket| bucket.iter().find(|n| equals_fn(n)))
    }

    /// Remove a node by profile and equality check.
    pub fn remove(&mut self, profile: u64, equals_fn: impl Fn(&T) -> bool) -> Option<T> {
        if let Some(bucket) = self.nodes.get_mut(&profile) {
            if let Some(pos) = bucket.iter().position(|n| equals_fn(n)) {
                let removed = bucket.remove(pos);
                self.size -= 1;
                if bucket.is_empty() {
                    self.nodes.remove(&profile);
                }
                return Some(removed);
            }
        }
        None
    }

    /// Number of unique nodes in the set.
    pub fn len(&self) -> usize {
        self.size
    }

    /// Whether the set is empty.
    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    /// Clear all nodes.
    pub fn clear(&mut self) {
        self.nodes.clear();
        self.size = 0;
    }

    /// Iterate over all nodes.
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        self.nodes.values().flat_map(|bucket| bucket.iter())
    }

    /// Check if a node exists matching the given profile and predicate.
    pub fn contains(&self, profile: u64, equals_fn: impl Fn(&T) -> bool) -> bool {
        self.find(profile, equals_fn).is_some()
    }
}

impl<T: FoldingSetNode> Default for FoldingSet<T> {
    fn default() -> Self {
        Self::new()
    }
}

// ═══════════════════════════════════════════════════════════════════════════
// FoldingSetNodeID — hash value helper
// ═══════════════════════════════════════════════════════════════════════════

/// Helper for computing FoldingSet profile hashes from multiple components.
#[derive(Debug, Clone)]
pub struct FoldingSetNodeID {
    hash: u64,
}

impl FoldingSetNodeID {
    pub fn new() -> Self {
        Self {
            hash: 0x9e37_79b9_7f4a_7c15,
        } // FNV offset basis
    }

    /// Add an integer to the hash.
    pub fn add_integer(&mut self, val: u64) {
        self.hash ^= val;
        self.hash = self.hash.wrapping_mul(0x100_0000_01b3);
    }

    /// Add a slice of bytes to the hash.
    pub fn add_bytes(&mut self, bytes: &[u8]) {
        for &b in bytes {
            self.hash ^= b as u64;
            self.hash = self.hash.wrapping_mul(0x100_0000_01b3);
        }
    }

    /// Add a string to the hash.
    pub fn add_string(&mut self, s: &str) {
        self.add_bytes(s.as_bytes());
    }

    /// Add a boolean to the hash.
    pub fn add_boolean(&mut self, b: bool) {
        self.add_integer(b as u64);
    }

    /// Get the computed hash.
    pub fn compute_hash(&self) -> u64 {
        self.hash
    }
}

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

// ═══════════════════════════════════════════════════════════════════════════
// Tests
// ═══════════════════════════════════════════════════════════════════════════

#[cfg(test)]
mod tests {
    use super::*;

    #[derive(Debug, Clone, PartialEq, Eq, Hash)]
    struct TestNode {
        id: u32,
        value: String,
    }

    impl FoldingSetNode for TestNode {
        fn profile(&self) -> u64 {
            let mut nid = FoldingSetNodeID::new();
            nid.add_integer(self.id as u64);
            nid.add_string(&self.value);
            nid.compute_hash()
        }
    }

    #[test]
    fn test_folding_set_insert_unique() {
        let mut set = FoldingSet::new();
        let n1 = TestNode {
            id: 1,
            value: "hello".into(),
        };
        let n2 = TestNode {
            id: 2,
            value: "world".into(),
        };
        set.insert(n1);
        set.insert(n2);
        assert_eq!(set.len(), 2);
    }

    #[test]
    fn test_folding_set_insert_duplicate() {
        let mut set = FoldingSet::new();
        let n1 = TestNode {
            id: 1,
            value: "dup".into(),
        };
        let n2 = TestNode {
            id: 1,
            value: "dup".into(),
        };
        let r1 = set.insert(n1);
        let r2 = set.insert(n2);
        assert_eq!(set.len(), 1); // Only one inserted
        assert_eq!(r1.id, r2.id);
    }

    #[test]
    fn test_folding_set_find() {
        let mut set = FoldingSet::new();
        let n1 = TestNode {
            id: 42,
            value: "findme".into(),
        };
        set.insert(n1);

        let mut nid = FoldingSetNodeID::new();
        nid.add_integer(42);
        nid.add_string("findme");
        let profile = nid.compute_hash();

        let found = set.find(profile, |n| n.id == 42);
        assert!(found.is_some());
        assert_eq!(found.unwrap().value, "findme");
    }

    #[test]
    fn test_folding_set_remove() {
        let mut set = FoldingSet::new();
        let n1 = TestNode {
            id: 1,
            value: "remove".into(),
        };
        set.insert(n1);

        let mut nid = FoldingSetNodeID::new();
        nid.add_integer(1);
        nid.add_string("remove");
        let profile = nid.compute_hash();

        let removed = set.remove(profile, |n| n.id == 1);
        assert!(removed.is_some());
        assert_eq!(set.len(), 0);
    }

    #[test]
    fn test_folding_set_clear() {
        let mut set = FoldingSet::new();
        for i in 0..10 {
            set.insert(TestNode {
                id: i,
                value: format!("node{}", i),
            });
        }
        assert_eq!(set.len(), 10);
        set.clear();
        assert_eq!(set.len(), 0);
        assert!(set.is_empty());
    }

    #[test]
    fn test_node_id_hash() {
        let mut nid = FoldingSetNodeID::new();
        nid.add_integer(12345);
        nid.add_string("test");
        nid.add_boolean(true);
        let h1 = nid.compute_hash();

        let mut nid2 = FoldingSetNodeID::new();
        nid2.add_integer(12345);
        nid2.add_string("test");
        nid2.add_boolean(true);
        let h2 = nid2.compute_hash();

        assert_eq!(h1, h2); // Deterministic
    }
}