provenant/license_detection/index/

mod.rs

//! License index construction and querying.

pub mod builder;
pub mod dictionary;
pub mod token_sets;

// build_index is used by library tests (see spdx_lid/test.rs, index/builder/tests.rs)
// even though the binary doesn't use it directly.
#[allow(unused_imports)]
pub use builder::{
    build_index, build_index_from_loaded, loaded_license_to_license, loaded_rule_to_rule,
};

use crate::license_detection::index::dictionary::{TokenDictionary, TokenId};
use aho_corasick::AhoCorasick;
use std::collections::{HashMap, HashSet};

/// Type alias for Aho-Corasick automaton.
///
/// The automaton is built from u16 token sequences encoded as bytes.
/// Each token is encoded as 2 bytes in little-endian format.
///
/// Based on the Python ScanCode Toolkit implementation at:
/// reference/scancode-toolkit/src/licensedcode/match_aho.py
pub type Automaton = AhoCorasick;

/// License index containing all data structures for efficient license detection.
///
/// The LicenseIndex holds multiple index structures that enable different matching
/// strategies: hash-based exact matching, Aho-Corasick automaton matching, set-based
/// candidate selection, and sequence matching.
///
/// Based on the Python ScanCode Toolkit implementation at:
/// reference/scancode-toolkit/src/licensedcode/index.py
///
/// # Index Structures
///
/// The index maintains several data structures for different matching strategies:
///
/// - **Hash matching**: `rid_by_hash` for exact hash-based matches
/// - **Automaton matching**: `rules_automaton` and `unknown_automaton` for pattern matching
/// - **Candidate selection**: `sets_by_rid` and `msets_by_rid` for set-based ranking
/// - **Sequence matching**: `high_postings_by_rid` for high-value token position tracking
/// - **Rule classification**: `false_positive_rids`, `approx_matchable_rids`
#[derive(Debug, Clone)]
pub struct LicenseIndex {
    /// Token dictionary mapping token strings to integer IDs.
    ///
    /// IDs 0 to len_legalese-1 are reserved for legalese tokens (high-value words).
    /// IDs len_legalese and above are assigned to other tokens as encountered.
    pub dictionary: TokenDictionary,

    /// Number of legalese tokens.
    ///
    /// Tokens with ID < len_legalese are considered high-value legalese words.
    /// Tokens with ID >= len_legalese are considered low-value tokens.
    ///
    /// Corresponds to Python: `self.len_legalese = 0` (line 185)
    pub len_legalese: usize,

    /// Mapping from rule hash to rule ID for hash-based exact matching.
    ///
    /// This enables fast exact matches using a hash of the rule\'s token IDs.
    /// Each hash maps to exactly one rule ID.
    ///
    /// Note: The hash is a 20-byte SHA1 digest, stored as a key in HashMap.
    /// In practice, we use a HashMap<[u8; 20], usize>.
    ///
    /// Corresponds to Python: `self.rid_by_hash = {}` (line 216)
    pub rid_by_hash: HashMap<[u8; 20], usize>,

    /// Rules indexed by rule ID.
    ///
    /// Maps rule IDs to Rule objects for quick lookup.
    ///
    /// Corresponds to Python: `self.rules_by_rid = []` (line 201)
    pub rules_by_rid: Vec<crate::license_detection::models::Rule>,

    /// Token ID sequences indexed by rule ID.
    ///
    /// Maps rule IDs to their token ID sequences.
    ///
    /// Corresponds to Python: `self.tids_by_rid = []` (line 204)
    pub tids_by_rid: Vec<Vec<TokenId>>,

    /// Aho-Corasick automaton built from all rule token sequences.
    ///
    /// Supports efficient multi-pattern matching of token ID sequences.
    /// Used for exact matching of complete rules or rule fragments in query text.
    ///
    /// Corresponds to Python: `self.rules_automaton = match_aho.get_automaton()` (line 219)
    pub rules_automaton: Automaton,

    /// Aho-Corasick automaton for unknown license detection.
    ///
    /// Separate automaton used to detect license-like text that doesn\'t match
    /// any known rule. Populated with ngrams from all approx-matchable rules.
    ///
    /// Corresponds to Python: `self.unknown_automaton = match_unknown.get_automaton()` (line 222)
    pub unknown_automaton: Automaton,

    /// Token ID sets per rule for candidate selection.
    ///
    /// Maps rule IDs to sets of unique token IDs present in that rule.
    /// Used for efficient candidate selection based on token overlap.
    ///
    /// Corresponds to Python: `self.sets_by_rid = []` (line 212)
    pub sets_by_rid: HashMap<usize, HashSet<TokenId>>,

    /// Token ID multisets per rule for candidate ranking.
    ///
    /// Maps rule IDs to multisets (bags) of token IDs with their frequencies.
    /// Used for ranking candidates by token frequency overlap.
    ///
    /// Corresponds to Python: `self.msets_by_rid = []` (line 213)
    pub msets_by_rid: HashMap<usize, HashMap<TokenId, usize>>,

    /// High-value token sets per rule for early candidate rejection.
    ///
    /// Maps rule IDs to sets containing only high-value (legalese) token IDs.
    /// This is a subset of `sets_by_rid` for faster intersection computation
    /// and early rejection of candidates that won't pass the high-token threshold.
    ///
    /// Precomputed during index building to avoid redundant filtering at runtime.
    pub high_sets_by_rid: HashMap<usize, HashSet<TokenId>>,

    /// Inverted index of high-value token positions per rule.
    ///
    /// Maps rule IDs to a mapping from high-value token IDs to their positions
    /// within the rule. Only contains positions for tokens with IDs < len_legalese.
    ///
    /// This structure speeds up sequence matching by allowing quick lookup of
    /// where high-value tokens appear in each rule.
    ///
    /// Corresponds to Python: `self.high_postings_by_rid = []` (line 209)
    /// In Python: `postings = {tid: array('h', [positions, ...])}`
    pub high_postings_by_rid: HashMap<usize, HashMap<TokenId, Vec<usize>>>,

    /// Set of rule IDs for false positive rules.
    ///
    /// False positive rules are used for exact matching and post-matching
    /// filtering to subtract spurious matches.
    ///
    /// Corresponds to Python: `self.false_positive_rids = set()` (line 230)
    pub false_positive_rids: HashSet<usize>,

    /// Set of rule IDs that can be matched approximately.
    ///
    /// Only rules marked as approx-matchable participate in sequence matching.
    /// Other rules can only be matched exactly using the automaton.
    ///
    /// Note: This field is kept for Python parity documentation and test usage.
    /// The inverted index (`rids_by_high_tid`) now handles candidate filtering
    /// more efficiently, making direct iteration over this set unnecessary.
    ///
    /// Corresponds to Python: `self.approx_matchable_rids = set()` (line 234)
    #[allow(dead_code)]
    pub approx_matchable_rids: HashSet<usize>,

    /// Mapping from ScanCode license key to License object.
    ///
    /// Provides access to license metadata for building SPDX mappings
    /// and validating license expressions.
    ///
    /// Corresponds to Python: `get_licenses_db()` in models.py
    pub licenses_by_key: HashMap<String, crate::license_detection::models::License>,

    /// Maps AhoCorasick pattern_id to rule id (rid).
    ///
    /// This is needed because the AhoCorasick pattern_id is just the index
    /// in the patterns iterator used to build the automaton, not the actual
    /// rule id. In Python, the automaton stores (rid, start, end) tuples as
    /// values, so the rid is retrieved from the stored value. In Rust, we
    /// maintain this mapping instead.
    ///
    /// Corresponds to Python: automaton values contain (rid, istart, iend)
    pub pattern_id_to_rid: Vec<usize>,

    /// Mapping from SPDX license key to rule ID.
    ///
    /// Enables direct lookup of rules by their SPDX license key,
    /// including aliases like "GPL-2.0+" -> gpl-2.0-plus.
    ///
    /// Keys are stored lowercase for case-insensitive lookup.
    ///
    /// Corresponds to Python: `self.licenses_by_spdx_key` in cache.py
    pub rid_by_spdx_key: HashMap<String, usize>,

    /// Rule ID for the unknown-spdx license.
    ///
    /// Used as a fallback when an SPDX identifier is not recognized.
    ///
    /// Corresponds to Python: `get_unknown_spdx_symbol()` in cache.py
    pub unknown_spdx_rid: Option<usize>,

    /// Inverted index mapping high-value token IDs to rule IDs.
    ///
    /// This enables fast candidate selection by only examining rules
    /// that share at least one high-value (legalese) token with the query.
    /// Without this index, candidate selection would iterate over all 37,000+
    /// rules for every file, making license detection extremely slow.
    ///
    /// Only contains entries for tokens with ID < len_legalese (high-value tokens).
    /// Rules not in approx_matchable_rids are excluded from this index.
    pub rids_by_high_tid: HashMap<TokenId, HashSet<usize>>,
}

impl LicenseIndex {}

impl LicenseIndex {
    /// Create a new empty license index.
    ///
    /// This constructor initializes all index structures with empty collections.
    /// The index can be populated with rules using the indexing methods (to be
    /// implemented in future phases).
    ///
    /// # Returns
    /// A new LicenseIndex instance with empty index structures
    pub fn new(dictionary: TokenDictionary) -> Self {
        let len_legalese = dictionary.legalese_count();
        Self {
            dictionary,
            len_legalese,
            rid_by_hash: HashMap::new(),
            rules_by_rid: Vec::new(),
            tids_by_rid: Vec::new(),
            rules_automaton: Automaton::new(std::iter::empty::<&[u8]>())
                .expect("Failed to create empty automaton"),
            unknown_automaton: Automaton::new(std::iter::empty::<&[u8]>())
                .expect("Failed to create empty automaton"),
            sets_by_rid: HashMap::new(),
            msets_by_rid: HashMap::new(),
            high_sets_by_rid: HashMap::new(),
            high_postings_by_rid: HashMap::new(),
            false_positive_rids: HashSet::new(),
            approx_matchable_rids: HashSet::new(),
            licenses_by_key: HashMap::new(),
            pattern_id_to_rid: Vec::new(),
            rid_by_spdx_key: HashMap::new(),
            unknown_spdx_rid: None,
            rids_by_high_tid: HashMap::new(),
        }
    }

    /// Create a new empty license index with the specified legalese count.
    ///
    /// Convenience method that creates a new TokenDictionary and LicenseIndex
    /// in one call.
    ///
    /// # Arguments
    /// * `legalese_count` - Number of reserved legalese token IDs
    ///
    /// # Returns
    /// A new LicenseIndex instance with a new TokenDictionary
    pub fn with_legalese_count(legalese_count: usize) -> Self {
        Self::new(TokenDictionary::new(legalese_count))
    }
}

impl Default for LicenseIndex {
    fn default() -> Self {
        Self::with_legalese_count(0)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::license_detection::models::License;

    #[test]
    fn test_license_index_new() {
        let dict = TokenDictionary::new(10);
        let index = LicenseIndex::new(dict);

        assert_eq!(index.dictionary.legalese_count(), 10);
        assert!(index.rid_by_hash.is_empty());
        assert!(index.sets_by_rid.is_empty());
        assert!(index.msets_by_rid.is_empty());
        assert!(index.high_postings_by_rid.is_empty());
        assert!(index.false_positive_rids.is_empty());
        assert!(index.approx_matchable_rids.is_empty());
        assert!(index.licenses_by_key.is_empty());
    }

    #[test]
    fn test_license_index_with_legalese_count() {
        let index = LicenseIndex::with_legalese_count(15);

        assert_eq!(index.dictionary.legalese_count(), 15);
        assert!(index.rid_by_hash.is_empty());
    }

    #[test]
    fn test_license_index_default() {
        let index = LicenseIndex::default();

        assert_eq!(index.dictionary.legalese_count(), 0);
        assert!(index.rid_by_hash.is_empty());
    }

    #[test]
    fn test_automaton_default() {
        let automaton =
            Automaton::new(std::iter::empty::<&[u8]>()).expect("Failed to create automaton");
        let _ = format!("{:?}", automaton);
    }

    #[test]
    fn test_license_index_clone() {
        let index = LicenseIndex::with_legalese_count(5);
        let cloned = index.clone();

        assert_eq!(cloned.dictionary.legalese_count(), 5);
        assert!(cloned.rid_by_hash.is_empty());
    }

    #[test]
    fn test_license_index_add_license() {
        let mut index = LicenseIndex::default();

        let license = License {
            key: "test-license".to_string(),
            name: "Test License".to_string(),
            spdx_license_key: Some("TEST".to_string()),
            other_spdx_license_keys: vec![],
            category: Some("Permissive".to_string()),
            text: "Test license text".to_string(),
            reference_urls: vec![],
            notes: None,
            is_deprecated: false,
            replaced_by: vec![],
            minimum_coverage: None,
            ignorable_copyrights: None,
            ignorable_holders: None,
            ignorable_authors: None,
            ignorable_urls: None,
            ignorable_emails: None,
        };

        index.licenses_by_key.insert(license.key.clone(), license);

        assert_eq!(index.licenses_by_key.len(), 1);
        assert!(index.licenses_by_key.contains_key("test-license"));
    }

    #[test]
    fn test_license_index_add_licenses() {
        let mut index = LicenseIndex::default();

        let licenses = vec![
            License {
                key: "license-1".to_string(),
                name: "License 1".to_string(),
                spdx_license_key: Some("LIC1".to_string()),
                other_spdx_license_keys: vec![],
                category: Some("Permissive".to_string()),
                text: "License 1 text".to_string(),
                reference_urls: vec![],
                notes: None,
                is_deprecated: false,
                replaced_by: vec![],
                minimum_coverage: None,
                ignorable_copyrights: None,
                ignorable_holders: None,
                ignorable_authors: None,
                ignorable_urls: None,
                ignorable_emails: None,
            },
            License {
                key: "license-2".to_string(),
                name: "License 2".to_string(),
                spdx_license_key: Some("LIC2".to_string()),
                other_spdx_license_keys: vec![],
                category: Some("Copyleft".to_string()),
                text: "License 2 text".to_string(),
                reference_urls: vec![],
                notes: None,
                is_deprecated: false,
                replaced_by: vec![],
                minimum_coverage: None,
                ignorable_copyrights: None,
                ignorable_holders: None,
                ignorable_authors: None,
                ignorable_urls: None,
                ignorable_emails: None,
            },
        ];

        for license in licenses {
            index.licenses_by_key.insert(license.key.clone(), license);
        }

        assert_eq!(index.licenses_by_key.len(), 2);
        assert!(index.licenses_by_key.contains_key("license-1"));
        assert!(index.licenses_by_key.contains_key("license-2"));
    }

    #[test]
    fn test_license_index_get_license() {
        let mut index = LicenseIndex::default();

        let license = License {
            key: "mit".to_string(),
            name: "MIT License".to_string(),
            spdx_license_key: Some("MIT".to_string()),
            other_spdx_license_keys: vec![],
            category: Some("Permissive".to_string()),
            text: "MIT License text".to_string(),
            reference_urls: vec![],
            notes: None,
            is_deprecated: false,
            replaced_by: vec![],
            minimum_coverage: None,
            ignorable_copyrights: None,
            ignorable_holders: None,
            ignorable_authors: None,
            ignorable_urls: None,
            ignorable_emails: None,
        };

        index.licenses_by_key.insert(license.key.clone(), license);

        let retrieved = index.licenses_by_key.get("mit");
        assert!(retrieved.is_some());
        assert_eq!(retrieved.unwrap().name, "MIT License");

        assert!(!index.licenses_by_key.contains_key("unknown"));
    }

    #[test]
    fn test_license_index_license_count() {
        let mut index = LicenseIndex::default();

        assert_eq!(index.licenses_by_key.len(), 0);

        let license = License {
            key: "test".to_string(),
            name: "Test".to_string(),
            spdx_license_key: Some("TEST".to_string()),
            other_spdx_license_keys: vec![],
            category: Some("Permissive".to_string()),
            text: "Text".to_string(),
            reference_urls: vec![],
            notes: None,
            is_deprecated: false,
            replaced_by: vec![],
            minimum_coverage: None,
            ignorable_copyrights: None,
            ignorable_holders: None,
            ignorable_authors: None,
            ignorable_urls: None,
            ignorable_emails: None,
        };

        index.licenses_by_key.insert(license.key.clone(), license);

        assert_eq!(index.licenses_by_key.len(), 1);
    }
}