provenant/license_detection/seq_match/
mod.rs

1// SPDX-FileCopyrightText: nexB Inc. and others
2// ScanCode is a trademark of nexB Inc.
3// SPDX-FileCopyrightText: Provenant contributors
4// SPDX-License-Identifier: Apache-2.0
5// Derived from ScanCode Toolkit (Apache-2.0); modified. See NOTICE.
6
7//! Approximate sequence matching for license detection.
8//!
9//! This module implements sequence-based matching using set similarity for
10//! candidate selection, followed by sequence alignment to find matching blocks.
11//!
12//! Based on Python ScanCode Toolkit implementation at:
13//! reference/scancode-toolkit/src/licensedcode/match_seq.py
14//!
15//! ## Near-Duplicate Detection
16//!
17//! This module implements Phase 2 of Python's 3-phase matching pipeline:
18//! 1. Phase 1: Hash & Aho-Corasick (exact matches)
19//! 2. Phase 2: Near-duplicate detection - check whole file for high-resemblance candidates
20//! 3. Phase 3: Query run matching (if no near-duplicates found)
21//!
22//! The near-duplicate detection finds rules with high resemblance (>= 0.8) to the
23//! entire query, which helps match combined rules instead of partial rules.
24
25mod candidates;
26mod matching;
27
28#[cfg(test)]
29mod gfdl_debug_test;
30
31pub(crate) use candidates::{select_seq_candidates, select_seq_candidates_with_deadline};
32pub(crate) use matching::{seq_match_with_candidates, seq_match_with_candidates_and_deadline};
33
34use crate::license_detection::models::MatcherKind;
35
36pub const MATCH_SEQ: MatcherKind = MatcherKind::Seq;
37
38pub const HIGH_RESEMBLANCE_THRESHOLD_TENTHS: u32 = 8;
39
40#[cfg(test)]
41pub const HIGH_RESEMBLANCE_THRESHOLD: f32 = HIGH_RESEMBLANCE_THRESHOLD_TENTHS as f32 / 10.0;
42
43/// Default number of top near-duplicate candidates to consider.
44pub const MAX_NEAR_DUPE_CANDIDATES: usize = 10;
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49    use crate::license_detection::index::IndexedRuleMetadata;
50    use crate::license_detection::index::LicenseIndex;
51    use crate::license_detection::models::RuleId;
52    use crate::license_detection::query::Query;
53    use crate::license_detection::test_utils::create_test_index;
54    use crate::models::LineNumber;
55
56    pub(super) fn create_seq_match_test_index() -> LicenseIndex {
57        create_test_index(
58            &[
59                ("license", 0),
60                ("copyright", 1),
61                ("permission", 2),
62                ("redistribute", 3),
63                ("granted", 4),
64            ],
65            5,
66        )
67    }
68
69    pub(super) fn add_test_rule(index: &mut LicenseIndex, text: &str, expression: &str) -> RuleId {
70        let identifier = format!("{}.test", expression);
71        crate::license_detection::test_utils::add_text_rule(index, &identifier, text, expression)
72    }
73
74    #[test]
75    fn test_seq_match_basic() {
76        let mut index = create_seq_match_test_index();
77
78        add_test_rule(&mut index, "license copyright granted", "test-license");
79
80        let text = "license copyright granted here";
81        let query = Query::from_extracted_text(text, &index, false).unwrap();
82        let query_run = query.whole_query_run();
83
84        let candidates = select_seq_candidates(&index, &query_run, false, 50);
85        let matches = seq_match_with_candidates(&index, &query_run, &candidates);
86
87        assert!(!matches.is_empty());
88        assert_eq!(matches[0].matcher, MATCH_SEQ);
89    }
90
91    #[test]
92    fn test_seq_match_uses_precomputed_spdx_expression() {
93        let mut index = create_seq_match_test_index();
94
95        add_test_rule(&mut index, "license copyright", "mit");
96        index.rule_metadata_by_identifier.insert(
97            "mit.test".to_string(),
98            IndexedRuleMetadata {
99                license_expression_spdx: Some("MIT".to_string()),
100                skip_for_required_phrase_generation: false,
101                replaced_by: vec![],
102            },
103        );
104
105        let text = "license copyright";
106        let query = Query::from_extracted_text(text, &index, false).unwrap();
107        let query_run = query.whole_query_run();
108        let candidates = select_seq_candidates(&index, &query_run, false, 50);
109        let matches = seq_match_with_candidates(&index, &query_run, &candidates);
110
111        assert_eq!(matches[0].license_expression_spdx.as_deref(), Some("MIT"));
112    }
113
114    #[test]
115    fn test_seq_match_partial_coverage_not_filtered() {
116        let mut index = create_seq_match_test_index();
117
118        add_test_rule(
119            &mut index,
120            "license copyright granted permission redistribute",
121            "test-long-license",
122        );
123
124        let text = "license copyright";
125        let query = Query::from_extracted_text(text, &index, false).unwrap();
126        let query_run = query.whole_query_run();
127
128        let candidates = select_seq_candidates(&index, &query_run, false, 50);
129        let matches = seq_match_with_candidates(&index, &query_run, &candidates);
130
131        assert!(
132            !matches.is_empty(),
133            "Partial coverage matches should NOT be filtered (Python has no 50% coverage filter)"
134        );
135        assert!(matches[0].match_coverage < 50.0);
136    }
137
138    #[test]
139    fn test_seq_match_empty_query() {
140        let mut index = create_seq_match_test_index();
141
142        add_test_rule(&mut index, "license copyright", "test-license");
143
144        let text = "";
145        let query = Query::from_extracted_text(text, &index, false).unwrap();
146        let query_run = query.whole_query_run();
147
148        let candidates = select_seq_candidates(&index, &query_run, false, 50);
149        let matches = seq_match_with_candidates(&index, &query_run, &candidates);
150
151        assert!(matches.is_empty());
152    }
153
154    #[test]
155    fn test_seq_match_constants() {
156        assert_eq!(MATCH_SEQ.as_str(), "3-seq");
157        assert_eq!(MATCH_SEQ.precedence(), 3);
158    }
159
160    #[test]
161    fn test_seq_match_with_no_legalese_intersection() {
162        let mut index = create_test_index(&[("word1", 10), ("word2", 11), ("word3", 12)], 5);
163
164        add_test_rule(&mut index, "word1 word2 word3", "test-license");
165
166        let text = "word1 word2 word3";
167        let query = Query::from_extracted_text(text, &index, false).unwrap();
168        let query_run = query.whole_query_run();
169
170        let candidates = select_seq_candidates(&index, &query_run, false, 50);
171        let matches = seq_match_with_candidates(&index, &query_run, &candidates);
172
173        assert!(
174            matches.is_empty(),
175            "Should not match when tokens are not legalese (above len_legalese)"
176        );
177    }
178
179    #[test]
180    fn test_seq_match_multiple_occurrences() {
181        let mut index = create_seq_match_test_index();
182
183        add_test_rule(&mut index, "license copyright granted", "test-license");
184
185        let text = "license copyright granted some text license copyright granted more text";
186        let query = Query::from_extracted_text(text, &index, false).unwrap();
187        let query_run = query.whole_query_run();
188
189        let candidates = select_seq_candidates(&index, &query_run, false, 50);
190        let matches = seq_match_with_candidates(&index, &query_run, &candidates);
191
192        assert!(
193            matches.len() >= 2,
194            "Should find multiple matches for the same rule appearing multiple times in query, got {} matches",
195            matches.len()
196        );
197
198        let license_expressions: Vec<&str> = matches
199            .iter()
200            .map(|m| m.license_expression.as_str())
201            .collect();
202        assert!(
203            license_expressions.iter().all(|&e| e == "test-license"),
204            "All matches should be for test-license"
205        );
206
207        let start_lines: Vec<usize> = matches.iter().map(|m| m.start_line.get()).collect();
208        let end_lines: Vec<usize> = matches.iter().map(|m| m.end_line.get()).collect();
209
210        assert!(
211            start_lines.iter().all(|&l| l >= 1),
212            "Start lines should be valid"
213        );
214        assert!(
215            end_lines.iter().all(|&l| l >= 1),
216            "End lines should be valid"
217        );
218    }
219
220    #[test]
221    fn test_seq_match_line_numbers_accurate() {
222        let mut index = create_seq_match_test_index();
223
224        add_test_rule(&mut index, "license copyright granted", "test-license");
225
226        let text = "line one\nlicense copyright granted\nline three";
227        let query = Query::from_extracted_text(text, &index, false).unwrap();
228        let query_run = query.whole_query_run();
229
230        let candidates = select_seq_candidates(&index, &query_run, false, 50);
231        let matches = seq_match_with_candidates(&index, &query_run, &candidates);
232
233        assert!(!matches.is_empty(), "Should find matches");
234
235        let first_match = &matches[0];
236
237        assert_eq!(
238            first_match.start_line,
239            LineNumber::new(2).unwrap(),
240            "Match should start on line 2 (where license tokens are), not line 1"
241        );
242        assert_eq!(
243            first_match.end_line,
244            LineNumber::new(2).unwrap(),
245            "Match should end on line 2 (where license tokens are), not line 3"
246        );
247
248        // matched_text is computed lazily at output time, not during matching
249        assert!(
250            first_match.matched_text.is_none(),
251            "matched_text should be None during matching (computed lazily at output)"
252        );
253
254        // Verify we can compute it from the query
255        let matched_text =
256            query.matched_text(first_match.start_line.get(), first_match.end_line.get());
257        assert!(
258            matched_text.contains("license"),
259            "Computed matched text should contain 'license'"
260        );
261    }
262
263    #[test]
264    fn test_seq_match_line_numbers_partial_match() {
265        let mut index = create_seq_match_test_index();
266
267        add_test_rule(
268            &mut index,
269            "license copyright granted permission",
270            "test-license",
271        );
272
273        let text = "line one\nlicense copyright\nline three";
274        let query = Query::from_extracted_text(text, &index, false).unwrap();
275        let query_run = query.whole_query_run();
276
277        let candidates = select_seq_candidates(&index, &query_run, false, 50);
278        let matches = seq_match_with_candidates(&index, &query_run, &candidates);
279
280        assert!(!matches.is_empty(), "Should find partial matches");
281
282        let first_match = &matches[0];
283
284        assert_eq!(
285            first_match.start_line,
286            LineNumber::new(2).unwrap(),
287            "Partial match should start on line 2"
288        );
289        assert_eq!(
290            first_match.end_line,
291            LineNumber::new(2).unwrap(),
292            "Partial match should end on line 2"
293        );
294
295        assert!(
296            first_match.match_coverage < 100.0,
297            "Should be partial coverage"
298        );
299    }
300}
provenant/license_detection/seq_match/mod.rs

provenant/license_detection/seq_match/
mod.rs
