provenant/license_detection/index/

mod.rs

// SPDX-FileCopyrightText: nexB Inc. and others
// SPDX-FileCopyrightText: Provenant contributors
// SPDX-License-Identifier: Apache-2.0
// Derived from ScanCode Toolkit (Apache-2.0); modified. See NOTICE.

//! License index construction and querying.

pub mod builder;
pub mod dictionary;

#[allow(unused_imports)]
pub use builder::{
    build_index, build_index_from_loaded, loaded_license_to_license, loaded_rule_to_rule,
};

use crate::license_detection::automaton::{AsBytes, Automaton};
use crate::license_detection::index::dictionary::{TokenDictionary, TokenId};
use crate::license_detection::models::RuleId;
use crate::license_detection::{HighBitset, TokenMultiset, TokenSet};
use rkyv::Archive;
use std::collections::{HashMap, HashSet};

#[derive(Debug, Clone, Default, PartialEq, Eq, Archive, rkyv::Serialize, rkyv::Deserialize)]
pub struct IndexedRuleMetadata {
    pub license_expression_spdx: Option<String>,
    pub skip_for_required_phrase_generation: bool,
    pub replaced_by: Vec<String>,
}

/// 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
#[derive(Debug, Clone, Archive, rkyv::Serialize, rkyv::Deserialize)]
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], RuleId>.
    ///
    /// Corresponds to Python: `self.rid_by_hash = {}` (line 216)
    pub rid_by_hash: HashMap<[u8; 20], RuleId>,

    /// 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)
    #[rkyv(with = AsBytes)]
    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)
    #[rkyv(with = AsBytes)]
    pub unknown_automaton: Automaton,

    /// Token ID sets per rule for candidate selection.
    ///
    /// Indexed densely by `RuleId::raw()` (mirroring Python's `sets_by_rid = []`
    /// list). Entries are `None` for rule IDs that hold no set (e.g. false-positive
    /// rules), so the candidate-selection hot loop reads a `Vec` slot instead of a
    /// hashed lookup. Use [`LicenseIndex::set_for_rid`] to access.
    pub sets_by_rid: Vec<Option<TokenSet>>,

    pub rule_metadata_by_identifier: HashMap<String, IndexedRuleMetadata>,

    /// Token ID multisets per rule for candidate ranking.
    ///
    /// Indexed densely by `RuleId::raw()` (mirroring Python's `msets_by_rid = []`).
    /// `None` where no multiset exists. Use [`LicenseIndex::mset_for_rid`].
    pub msets_by_rid: Vec<Option<TokenMultiset>>,

    /// High-value token sets per rule for early candidate rejection.
    ///
    /// Indexed densely by `RuleId::raw()`. A subset of `sets_by_rid` containing
    /// only high-value (legalese) token IDs, for early rejection of candidates that
    /// won't pass the high-token threshold. `None` where the rule has no high-value
    /// tokens. Use [`LicenseIndex::high_set_for_rid`].
    pub high_sets_by_rid: Vec<Option<TokenSet>>,

    /// High-value token sets as fixed-width bitsets (width = `len_legalese`),
    /// densely indexed by `RuleId::raw()` and aligned with `high_sets_by_rid`
    /// (`Some` exactly where that is `Some`). Used by the candidate-selection
    /// high-token gate, where `AND`+`popcount` replaces the sorted-set merge
    /// walk. Use [`LicenseIndex::high_bitset_for_rid`].
    pub high_bitsets_by_rid: Vec<Option<HighBitset>>,

    /// 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<RuleId, HashMap<TokenId, Vec<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>,

    /// 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, RuleId>,

    /// 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<RuleId>,

    /// 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).
    /// Only approx-matchable rules are included in this index.
    pub rids_by_high_tid: HashMap<TokenId, HashSet<RuleId>>,

    /// SPDX license list version used to build this index.
    pub spdx_license_list_version: Option<String>,
}

impl LicenseIndex {
    /// Returns the rule for the given ID, or `None` if the ID is invalid
    /// or out of range.
    pub fn rule(&self, id: RuleId) -> Option<&crate::license_detection::models::Rule> {
        if id.is_none() {
            return None;
        }
        self.rules_by_rid.get(id.raw())
    }

    /// Returns the token ID sequence for the given rule, or `None` if the ID
    /// is invalid or out of range.
    pub fn rule_tokens(&self, id: RuleId) -> Option<&[TokenId]> {
        if id.is_none() {
            return None;
        }
        self.tids_by_rid.get(id.raw()).map(|v| v.as_slice())
    }

    pub fn is_false_positive(&self, id: RuleId) -> bool {
        self.rule(id).is_some_and(|r| r.is_false_positive)
    }
}

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 {
        use crate::license_detection::automaton::AutomatonBuilder;

        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: AutomatonBuilder::new().build(),
            unknown_automaton: AutomatonBuilder::new().build(),
            sets_by_rid: Vec::new(),
            rule_metadata_by_identifier: HashMap::new(),
            msets_by_rid: Vec::new(),
            high_sets_by_rid: Vec::new(),
            high_bitsets_by_rid: Vec::new(),
            high_postings_by_rid: HashMap::new(),
            licenses_by_key: HashMap::new(),
            rid_by_spdx_key: HashMap::new(),
            unknown_spdx_rid: None,
            rids_by_high_tid: HashMap::new(),
            spdx_license_list_version: None,
        }
    }

    /// Unique-token set for a rule, or `None` if the rule holds no set
    /// (e.g. a false-positive rule). Dense `Vec` lookup by `RuleId`.
    #[inline]
    pub fn set_for_rid(&self, rid: RuleId) -> Option<&TokenSet> {
        self.sets_by_rid.get(rid.raw()).and_then(Option::as_ref)
    }

    /// High-value (legalese) token set for a rule, or `None` if the rule has no
    /// high-value tokens. Dense `Vec` lookup by `RuleId`.
    #[inline]
    pub fn high_set_for_rid(&self, rid: RuleId) -> Option<&TokenSet> {
        self.high_sets_by_rid
            .get(rid.raw())
            .and_then(Option::as_ref)
    }

    /// Token multiset for a rule, or `None` if the rule holds no multiset.
    /// Dense `Vec` lookup by `RuleId`.
    #[inline]
    pub fn mset_for_rid(&self, rid: RuleId) -> Option<&TokenMultiset> {
        self.msets_by_rid.get(rid.raw()).and_then(Option::as_ref)
    }

    /// High-value token bitset for a rule, or `None` if the rule has no
    /// high-value tokens. Dense `Vec` lookup by `RuleId`.
    #[inline]
    pub fn high_bitset_for_rid(&self, rid: RuleId) -> Option<&HighBitset> {
        self.high_bitsets_by_rid
            .get(rid.raw())
            .and_then(Option::as_ref)
    }

    /// 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::*;

    fn simple_license(key: &str, name: &str, spdx: &str, category: &str, text: &str) -> License {
        License {
            key: key.to_string(),
            short_name: Some(name.to_string()),
            name: name.to_string(),
            language: Some("en".to_string()),
            spdx_license_key: Some(spdx.to_string()),
            other_spdx_license_keys: vec![],
            category: Some(category.to_string()),
            owner: None,
            homepage_url: None,
            text: text.to_string(),
            reference_urls: vec![],
            osi_license_key: Some(spdx.to_string()),
            text_urls: vec![],
            osi_url: None,
            faq_url: None,
            other_urls: vec![],
            notes: None,
            is_deprecated: false,
            is_exception: false,
            is_unknown: false,
            is_generic: false,
            replaced_by: vec![],
            minimum_coverage: None,
            standard_notice: None,
            ignorable_copyrights: None,
            ignorable_holders: None,
            ignorable_authors: None,
            ignorable_urls: None,
            ignorable_emails: None,
        }
    }
    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.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() {
        use crate::license_detection::automaton::AutomatonBuilder;

        let automaton = AutomatonBuilder::new().build();
        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 = simple_license(
            "test-license",
            "Test License",
            "TEST",
            "Permissive",
            "Test license text",
        );

        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![
            simple_license(
                "license-1",
                "License 1",
                "LIC1",
                "Permissive",
                "License 1 text",
            ),
            simple_license(
                "license-2",
                "License 2",
                "LIC2",
                "Copyleft",
                "License 2 text",
            ),
        ];

        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 = simple_license(
            "mit",
            "MIT License",
            "MIT",
            "Permissive",
            "MIT License text",
        );

        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 = simple_license("test", "Test", "TEST", "Permissive", "Text");

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

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