ctx/
fingerprint.rs

1//! Structural fingerprinting for near-duplicate function detection.
2//!
3//! This module implements a MinHash-based pipeline over normalized token
4//! shingles:
5//!
6//! 1. **Tokenize** a whole source file with tree-sitter and normalize the
7//!    leaf tokens: identifiers become `ID`, string/number literals become
8//!    `LIT`, comments are dropped, and keywords/operators/structure tokens
9//!    are kept verbatim.
10//! 2. **Shingle** each function/method symbol's token stream into k=5 token
11//!    windows, hashed with FNV-1a (fixed seeds, little-endian byte order, so
12//!    hashes are deterministic across runs and platforms).
13//! 3. **MinHash** the shingle set with 128 permutations
14//!    (`h_i(x) = splitmix64(x ^ SEED[i])`) into a 1024-byte signature stored
15//!    in the `symbol_fingerprints` table during `ctx index`.
16//! 4. **LSH banding** (16 bands x 8 rows) over the signatures produces
17//!    candidate pairs at query time, which are then verified with the exact
18//!    Jaccard similarity over re-derived shingle sets.
19//!
20//! Notes and limitations:
21//! - Solidity is parsed with solang-parser (no tree-sitter grammar), so
22//!   Solidity functions are not fingerprinted and never appear in results.
23//! - Nested functions share tokens with their enclosing function: both are
24//!   fingerprinted over their own line ranges, and the parent's range
25//!   includes the child's tokens.
26//! - Idiomatic boilerplate (builders, trait impls, small CRUD handlers) can
27//!   legitimately look structurally similar; tune `--min-tokens` to filter
28//!   short functions.
29
30use std::cell::RefCell;
31use std::collections::hash_map::Entry;
32use std::collections::{HashMap, HashSet};
33use std::path::Path;
34
35use tree_sitter::Parser;
36
37use crate::db::{Database, Fingerprint, Symbol, SymbolKind};
38use crate::error::Result;
39use crate::parser::Language;
40
41/// Number of MinHash permutations (signature length in u64 words).
42pub const NUM_PERMS: usize = 128;
43
44/// Shingle size in tokens.
45pub const SHINGLE_K: usize = 5;
46
47/// Number of LSH bands.
48pub const LSH_BANDS: usize = 16;
49
50/// Rows (signature words) per LSH band.
51pub const LSH_ROWS: usize = 8;
52
53/// Minimum usable similarity threshold. Below this the 16x8 LSH banding
54/// misses too many candidate pairs to be trustworthy, so callers clamp to it.
55pub const MIN_THRESHOLD: f64 = 0.5;
56
57const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
58const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
59
60/// Fixed seed for the SplitMix64 stream that generates the permutation seeds.
61const SEED_STATE: u64 = 0x0c7f_1d5e_a5ed_c0de;
62
63/// SplitMix64 mixing function (Steele, Lea & Flood). Deterministic and
64/// platform-independent; used both to derive the permutation seeds and as
65/// the per-permutation hash `h_i(x) = splitmix64(x ^ SEED[i])`.
66const fn splitmix64(mut z: u64) -> u64 {
67    z = z.wrapping_add(0x9e37_79b9_7f4a_7c15);
68    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
69    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
70    z ^ (z >> 31)
71}
72
73/// Per-permutation seeds, generated by a SplitMix64 stream from a fixed
74/// constant at compile time.
75const SEEDS: [u64; NUM_PERMS] = {
76    let mut seeds = [0u64; NUM_PERMS];
77    let mut state = SEED_STATE;
78    let mut i = 0;
79    while i < NUM_PERMS {
80        state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
81        seeds[i] = splitmix64(state);
82        i += 1;
83    }
84    seeds
85};
86
87/// FNV-1a 64-bit hash.
88fn fnv1a(bytes: &[u8]) -> u64 {
89    let mut h = FNV_OFFSET;
90    for &b in bytes {
91        h = (h ^ b as u64).wrapping_mul(FNV_PRIME);
92    }
93    h
94}
95
96/// A normalized token: the normalized text plus the 1-indexed source line.
97#[derive(Debug, Clone, PartialEq, Eq)]
98pub struct Tok {
99    pub text: String,
100    pub line: u32,
101}
102
103/// Map a [`Language`] to its tree-sitter grammar, or `None` for languages
104/// without one (Solidity is parsed with solang-parser and is skipped).
105fn ts_language(lang: Language) -> Option<tree_sitter::Language> {
106    match lang {
107        Language::Rust => Some(tree_sitter_rust::language()),
108        Language::TypeScript => Some(tree_sitter_typescript::language_typescript()),
109        Language::Tsx => Some(tree_sitter_typescript::language_tsx()),
110        Language::JavaScript | Language::Jsx => Some(tree_sitter_javascript::language()),
111        Language::Python => Some(tree_sitter_python::language()),
112        Language::Go => Some(tree_sitter_go::language()),
113        Language::Solidity | Language::Yaml | Language::Unknown => None,
114    }
115}
116
117thread_local! {
118    /// Per-thread parser cache (indexing is rayon-parallel; tree-sitter
119    /// parsers are not Sync). Keyed by language name.
120    static PARSERS: RefCell<HashMap<&'static str, Parser>> = RefCell::new(HashMap::new());
121}
122
123/// Normalize a leaf node into its token text.
124fn normalize_leaf(kind: &str, text: &str) -> String {
125    if kind.contains("identifier") {
126        return "ID".to_string();
127    }
128    if kind.contains("string")
129        || kind.contains("char")
130        || kind.contains("template")
131        || kind.contains("rune")
132    {
133        return "LIT".to_string();
134    }
135    // Numeric literal node kinds across the supported grammars
136    // (rust, typescript/javascript, python, go).
137    if matches!(
138        kind,
139        "integer_literal"
140            | "float_literal"
141            | "number"
142            | "int_literal"
143            | "imaginary_literal"
144            | "integer"
145            | "float"
146    ) {
147        return "LIT".to_string();
148    }
149    text.to_string()
150}
151
152/// Tokenize a whole source file into a normalized token stream.
153///
154/// Returns `None` for languages without a tree-sitter grammar (Solidity,
155/// YAML, unknown) or when parsing fails. Tokens are the leaf nodes of the
156/// AST in document order; comments (and their subtrees) are dropped.
157pub fn tokenize(lang: Language, source: &str) -> Option<Vec<Tok>> {
158    let ts_lang = ts_language(lang)?;
159
160    PARSERS.with(|cell| {
161        let mut parsers = cell.borrow_mut();
162        let parser = parsers.entry(lang.as_str()).or_insert_with(|| {
163            let mut p = Parser::new();
164            p.set_language(ts_lang)
165                .expect("grammar/version mismatch for fingerprint parser");
166            p
167        });
168
169        let tree = parser.parse(source, None)?;
170        let bytes = source.as_bytes();
171        let mut tokens = Vec::new();
172
173        // Iterative DFS (explicit stack) to avoid recursion depth limits on
174        // deeply nested code. Children are pushed in reverse so tokens come
175        // out in document order.
176        let mut stack = vec![tree.root_node()];
177        while let Some(node) = stack.pop() {
178            let kind = node.kind();
179            if kind.contains("comment") {
180                continue;
181            }
182            if node.child_count() == 0 {
183                let range = node.byte_range();
184                if range.is_empty() {
185                    continue; // zero-width "missing" nodes
186                }
187                let text = std::str::from_utf8(&bytes[range]).unwrap_or("");
188                tokens.push(Tok {
189                    text: normalize_leaf(kind, text),
190                    line: node.start_position().row as u32 + 1,
191                });
192                continue;
193            }
194            for i in (0..node.child_count()).rev() {
195                if let Some(child) = node.child(i) {
196                    stack.push(child);
197                }
198            }
199        }
200
201        Some(tokens)
202    })
203}
204
205/// Build the set of k-shingle hashes for a token stream.
206///
207/// Each token is hashed with FNV-1a; each shingle hash is FNV-1a over the
208/// k token hashes' little-endian bytes. Streams shorter than
209/// [`SHINGLE_K`] tokens produce an empty set.
210pub fn shingle_set(tokens: &[Tok]) -> HashSet<u64> {
211    let mut shingles = HashSet::new();
212    if tokens.len() < SHINGLE_K {
213        return shingles;
214    }
215    let hashes: Vec<u64> = tokens.iter().map(|t| fnv1a(t.text.as_bytes())).collect();
216    for window in hashes.windows(SHINGLE_K) {
217        let mut h = FNV_OFFSET;
218        for th in window {
219            for b in th.to_le_bytes() {
220                h = (h ^ b as u64).wrapping_mul(FNV_PRIME);
221            }
222        }
223        shingles.insert(h);
224    }
225    shingles
226}
227
228/// Compute the 128-permutation MinHash signature of a shingle set.
229///
230/// Returns `None` for an empty set (no signature can be defined).
231pub fn minhash(shingles: &HashSet<u64>) -> Option<[u64; NUM_PERMS]> {
232    if shingles.is_empty() {
233        return None;
234    }
235    let mut sig = [u64::MAX; NUM_PERMS];
236    for &x in shingles {
237        for (i, slot) in sig.iter_mut().enumerate() {
238            let h = splitmix64(x ^ SEEDS[i]);
239            if h < *slot {
240                *slot = h;
241            }
242        }
243    }
244    Some(sig)
245}
246
247/// Serialize a signature into a 1024-byte little-endian BLOB.
248pub fn signature_to_blob(sig: &[u64; NUM_PERMS]) -> Vec<u8> {
249    let mut blob = Vec::with_capacity(NUM_PERMS * 8);
250    for v in sig {
251        blob.extend_from_slice(&v.to_le_bytes());
252    }
253    blob
254}
255
256/// Deserialize a 1024-byte little-endian BLOB into a signature.
257pub fn blob_to_signature(blob: &[u8]) -> Option<[u64; NUM_PERMS]> {
258    if blob.len() != NUM_PERMS * 8 {
259        return None;
260    }
261    let mut sig = [0u64; NUM_PERMS];
262    for (i, chunk) in blob.chunks_exact(8).enumerate() {
263        sig[i] = u64::from_le_bytes(chunk.try_into().ok()?);
264    }
265    Some(sig)
266}
267
268/// Estimate Jaccard similarity from two MinHash signatures (fraction of
269/// matching permutation slots).
270pub fn estimate_similarity(a: &[u64; NUM_PERMS], b: &[u64; NUM_PERMS]) -> f64 {
271    let matching = a.iter().zip(b.iter()).filter(|(x, y)| x == y).count();
272    matching as f64 / NUM_PERMS as f64
273}
274
275/// Exact Jaccard similarity between two shingle sets.
276pub fn jaccard(a: &HashSet<u64>, b: &HashSet<u64>) -> f64 {
277    if a.is_empty() && b.is_empty() {
278        return 1.0;
279    }
280    if a.is_empty() || b.is_empty() {
281        return 0.0;
282    }
283    let intersection = a.intersection(b).count();
284    let union = a.len() + b.len() - intersection;
285    intersection as f64 / union as f64
286}
287
288/// Compute the LSH bucket key for each of the 16 bands (FNV-1a over the
289/// band's 8 signature words in little-endian byte order).
290pub fn band_keys(sig: &[u64; NUM_PERMS]) -> [u64; LSH_BANDS] {
291    let mut keys = [0u64; LSH_BANDS];
292    for (band, key) in keys.iter_mut().enumerate() {
293        let mut h = FNV_OFFSET;
294        for v in &sig[band * LSH_ROWS..(band + 1) * LSH_ROWS] {
295            for b in v.to_le_bytes() {
296                h = (h ^ b as u64).wrapping_mul(FNV_PRIME);
297            }
298        }
299        *key = h;
300    }
301    keys
302}
303
304/// Compute fingerprints for all function/method symbols of one parsed file.
305///
306/// `symbols` are the parser-produced symbols (pre-id-rewrite); `id_map`
307/// translates their ids to the stored `path::[parent::]name@line` form.
308/// Symbols with fewer than [`SHINGLE_K`] tokens (no shingles) get no
309/// fingerprint. Returns an empty vec for languages without a tree-sitter
310/// grammar (e.g. Solidity).
311pub fn file_fingerprints(
312    lang: Language,
313    source: &str,
314    rel_path: &str,
315    symbols: &[Symbol],
316    id_map: &HashMap<String, String>,
317) -> Vec<Fingerprint> {
318    let Some(tokens) = tokenize(lang, source) else {
319        return Vec::new();
320    };
321
322    let mut fingerprints = Vec::new();
323    for symbol in symbols {
324        if !matches!(symbol.kind, SymbolKind::Function | SymbolKind::Method) {
325            continue;
326        }
327        let Some(symbol_id) = id_map.get(&symbol.id) else {
328            continue;
329        };
330        let symbol_tokens: Vec<Tok> = tokens
331            .iter()
332            .filter(|t| t.line >= symbol.line_start && t.line <= symbol.line_end)
333            .cloned()
334            .collect();
335        let shingles = shingle_set(&symbol_tokens);
336        let Some(sig) = minhash(&shingles) else {
337            continue;
338        };
339        fingerprints.push(Fingerprint {
340            symbol_id: symbol_id.clone(),
341            file_path: rel_path.to_string(),
342            minhash: signature_to_blob(&sig),
343            token_count: symbol_tokens.len() as i64,
344        });
345    }
346    fingerprints
347}
348
349/// A verified near-duplicate pair, ordered so that `a.id < b.id`.
350#[derive(Debug, Clone)]
351pub struct DuplicatePair {
352    pub a: Symbol,
353    pub b: Symbol,
354    /// Exact Jaccard similarity over normalized token shingles.
355    pub similarity: f64,
356    pub token_count_a: i64,
357    pub token_count_b: i64,
358}
359
360/// Find near-duplicate function pairs in the index.
361///
362/// Loads all fingerprints with at least `min_tokens` tokens, buckets them
363/// with LSH banding, optionally keeps only pairs touching `changed_files`,
364/// then verifies each candidate pair with the exact Jaccard similarity over
365/// shingle sets re-derived from the symbols' stored source snippets.
366///
367/// Results are sorted by similarity (descending), then by the two symbol
368/// ids (ascending) for a stable order.
369pub fn find_near_duplicates(
370    db: &Database,
371    threshold: f64,
372    min_tokens: i64,
373    changed_files: Option<&HashSet<String>>,
374) -> Result<Vec<DuplicatePair>> {
375    let fingerprints = db.get_fingerprints(min_tokens)?;
376
377    // Decode signatures once (fingerprints are ordered by symbol_id, so
378    // index order is id order and (i, j) with i < j is the canonical pair).
379    let signatures: Vec<Option<[u64; NUM_PERMS]>> = fingerprints
380        .iter()
381        .map(|fp| blob_to_signature(&fp.minhash))
382        .collect();
383
384    // LSH banding: symbols sharing any band bucket become candidates.
385    let mut buckets: HashMap<(usize, u64), Vec<usize>> = HashMap::new();
386    for (idx, sig) in signatures.iter().enumerate() {
387        let Some(sig) = sig else { continue };
388        for (band, key) in band_keys(sig).iter().enumerate() {
389            buckets.entry((band, *key)).or_default().push(idx);
390        }
391    }
392
393    let mut candidates: HashSet<(usize, usize)> = HashSet::new();
394    for members in buckets.values() {
395        if members.len() < 2 {
396            continue;
397        }
398        for (n, &i) in members.iter().enumerate() {
399            for &j in &members[n + 1..] {
400                let pair = if i < j { (i, j) } else { (j, i) };
401                if pair.0 != pair.1 {
402                    candidates.insert(pair);
403                }
404            }
405        }
406    }
407
408    // --against filter: at least one endpoint must be in a changed file.
409    if let Some(changed) = changed_files {
410        candidates.retain(|&(i, j)| {
411            changed.contains(&fingerprints[i].file_path)
412                || changed.contains(&fingerprints[j].file_path)
413        });
414    }
415
416    // Verify candidates with exact Jaccard over re-derived shingle sets.
417    // Shingle sets are not stored; they are rebuilt by re-tokenizing each
418    // symbol's stored source snippet.
419    let mut shingle_cache: HashMap<usize, Option<HashSet<u64>>> = HashMap::new();
420    let mut symbol_cache: HashMap<usize, Option<Symbol>> = HashMap::new();
421    let mut pairs = Vec::new();
422
423    let mut sorted_candidates: Vec<(usize, usize)> = candidates.into_iter().collect();
424    sorted_candidates.sort_unstable();
425
426    for (i, j) in sorted_candidates {
427        for idx in [i, j] {
428            if let Entry::Vacant(entry) = symbol_cache.entry(idx) {
429                entry.insert(db.get_symbol(&fingerprints[idx].symbol_id)?);
430            }
431            if let Entry::Vacant(entry) = shingle_cache.entry(idx) {
432                entry.insert(symbol_cache[&idx].as_ref().and_then(symbol_shingles));
433            }
434        }
435
436        let (Some(sa), Some(sb)) = (&shingle_cache[&i], &shingle_cache[&j]) else {
437            continue;
438        };
439        let similarity = jaccard(sa, sb);
440        if similarity < threshold {
441            continue;
442        }
443        let (Some(a), Some(b)) = (&symbol_cache[&i], &symbol_cache[&j]) else {
444            continue;
445        };
446        pairs.push(DuplicatePair {
447            a: a.clone(),
448            b: b.clone(),
449            similarity,
450            token_count_a: fingerprints[i].token_count,
451            token_count_b: fingerprints[j].token_count,
452        });
453    }
454
455    pairs.sort_by(|x, y| {
456        y.similarity
457            .partial_cmp(&x.similarity)
458            .unwrap_or(std::cmp::Ordering::Equal)
459            .then_with(|| x.a.id.cmp(&y.a.id))
460            .then_with(|| x.b.id.cmp(&y.b.id))
461    });
462
463    Ok(pairs)
464}
465
466/// Rebuild a symbol's shingle set from its stored source snippet.
467///
468/// The language is detected from the file extension. Tree-sitter is
469/// error-tolerant, so tokenizing the snippet in isolation yields the same
470/// normalized token stream as slicing a whole-file parse (verified by test).
471/// Also used by `ctx score` to derive baseline shingles for symbols in
472/// unchanged files.
473pub fn symbol_shingles(symbol: &Symbol) -> Option<HashSet<u64>> {
474    let source = symbol.source.as_ref()?;
475    let lang = Language::from_path(Path::new(&symbol.file_path));
476    let tokens = tokenize(lang, source)?;
477    Some(shingle_set(&tokens))
478}
479
480#[cfg(test)]
481mod tests {
482    use super::*;
483
484    fn texts(lang: Language, source: &str) -> Vec<String> {
485        tokenize(lang, source)
486            .expect("tokenize failed")
487            .into_iter()
488            .map(|t| t.text)
489            .collect()
490    }
491
492    #[test]
493    fn test_tokenize_rust_normalization() {
494        let src = "fn add(first: i32) -> i32 {\n    // a helpful remark\n    first + 42\n}\n";
495        let toks = texts(Language::Rust, src);
496
497        // Identifiers -> ID, numeric literals -> LIT, keywords kept.
498        assert!(toks.contains(&"ID".to_string()));
499        assert!(toks.contains(&"LIT".to_string()));
500        assert!(toks.contains(&"fn".to_string()));
501        // Raw identifier/literal text is gone.
502        assert!(!toks.contains(&"first".to_string()));
503        assert!(!toks.contains(&"42".to_string()));
504        // Comments are dropped entirely.
505        assert!(!toks.iter().any(|t| t.contains("remark")));
506
507        // Renamed identifiers + changed literals produce the same stream.
508        let renamed = "fn add(second: i32) -> i32 {\n    second + 7\n}\n";
509        assert_eq!(toks, texts(Language::Rust, renamed));
510    }
511
512    #[test]
513    fn test_tokenize_typescript_normalization() {
514        let src = "function greet(name: string): number {\n  /* block comment */\n  return name.length + 1;\n}\n";
515        let toks = texts(Language::TypeScript, src);
516        assert!(toks.contains(&"ID".to_string()));
517        assert!(toks.contains(&"LIT".to_string())); // 1 -> number -> LIT
518        assert!(toks.contains(&"function".to_string()));
519        assert!(!toks.contains(&"name".to_string()));
520        assert!(!toks.contains(&"1".to_string()));
521        assert!(!toks.iter().any(|t| t.contains("block comment")));
522    }
523
524    #[test]
525    fn test_tokenize_python_normalization() {
526        let src = "def add(x):\n    # trailing note\n    return x + 42\n";
527        let toks = texts(Language::Python, src);
528        assert!(toks.contains(&"ID".to_string()));
529        assert!(toks.contains(&"LIT".to_string())); // 42 -> integer -> LIT
530        assert!(toks.contains(&"def".to_string()));
531        assert!(!toks.contains(&"x".to_string()));
532        assert!(!toks.contains(&"42".to_string()));
533        assert!(!toks.iter().any(|t| t.contains("note")));
534    }
535
536    #[test]
537    fn test_tokenize_go_normalization() {
538        let src = "package main\n\nfunc add(a int) int {\n\t// short comment\n\treturn a + 42\n}\n";
539        let toks = texts(Language::Go, src);
540        assert!(toks.contains(&"ID".to_string()));
541        assert!(toks.contains(&"LIT".to_string())); // 42 -> int_literal -> LIT
542        assert!(toks.contains(&"func".to_string()));
543        assert!(!toks.contains(&"a".to_string()));
544        assert!(!toks.contains(&"42".to_string()));
545        assert!(!toks.iter().any(|t| t.contains("short comment")));
546    }
547
548    #[test]
549    fn test_tokenize_unsupported_languages() {
550        // Solidity is parsed with solang-parser, not tree-sitter: skipped.
551        assert!(tokenize(Language::Solidity, "contract C {}").is_none());
552        assert!(tokenize(Language::Yaml, "a: 1").is_none());
553        assert!(tokenize(Language::Unknown, "whatever").is_none());
554    }
555
556    #[test]
557    fn test_shingle_set_requires_k_tokens() {
558        let short: Vec<Tok> = (0..SHINGLE_K - 1)
559            .map(|i| Tok {
560                text: format!("t{}", i),
561                line: 1,
562            })
563            .collect();
564        assert!(shingle_set(&short).is_empty());
565        assert!(minhash(&shingle_set(&short)).is_none());
566
567        let exact: Vec<Tok> = (0..SHINGLE_K)
568            .map(|i| Tok {
569                text: format!("t{}", i),
570                line: 1,
571            })
572            .collect();
573        assert_eq!(shingle_set(&exact).len(), 1);
574    }
575
576    #[test]
577    fn test_minhash_estimate_close_to_exact_jaccard() {
578        // Synthetic shingle sets with a known overlap.
579        let a: HashSet<u64> = (0..1000u64).map(splitmix64).collect();
580        let b: HashSet<u64> = (200..1200u64).map(splitmix64).collect();
581        let exact = jaccard(&a, &b);
582        assert!((exact - 800.0 / 1200.0).abs() < 1e-9);
583
584        let est = estimate_similarity(&minhash(&a).unwrap(), &minhash(&b).unwrap());
585        assert!(
586            (est - exact).abs() <= 0.08,
587            "estimate {} too far from exact {}",
588            est,
589            exact
590        );
591
592        // Identical and disjoint sets hit the extremes exactly.
593        assert_eq!(
594            estimate_similarity(&minhash(&a).unwrap(), &minhash(&a).unwrap()),
595            1.0
596        );
597        let c: HashSet<u64> = (10_000..10_500u64).map(splitmix64).collect();
598        let low = estimate_similarity(&minhash(&a).unwrap(), &minhash(&c).unwrap());
599        assert!(low <= 0.08, "disjoint sets estimated at {}", low);
600    }
601
602    #[test]
603    fn test_lsh_banding_finds_similar_pair() {
604        // Two shingle sets with Jaccard ~0.9: at least one of the 16 bands
605        // should collide (detection probability ~0.994 at J=0.85).
606        let a: HashSet<u64> = (0..200u64).map(splitmix64).collect();
607        let mut b = a.clone();
608        for i in 0..10u64 {
609            b.remove(&splitmix64(i));
610            b.insert(splitmix64(1_000_000 + i));
611        }
612        assert!(jaccard(&a, &b) > 0.89);
613
614        let keys_a = band_keys(&minhash(&a).unwrap());
615        let keys_b = band_keys(&minhash(&b).unwrap());
616        assert!(
617            keys_a.iter().zip(keys_b.iter()).any(|(x, y)| x == y),
618            "expected at least one shared LSH band for a ~0.9-similar pair"
619        );
620
621        // A dissimilar set should not collide in any band.
622        let c: HashSet<u64> = (5_000..5_200u64).map(splitmix64).collect();
623        let keys_c = band_keys(&minhash(&c).unwrap());
624        assert!(!keys_a.iter().zip(keys_c.iter()).any(|(x, y)| x == y));
625    }
626
627    #[test]
628    fn test_fingerprints_are_deterministic() {
629        let src = "fn f(a: i32) -> i32 {\n    let b = a * 2;\n    b + 1\n}\n";
630        let t1 = tokenize(Language::Rust, src).unwrap();
631        let t2 = tokenize(Language::Rust, src).unwrap();
632        assert_eq!(t1, t2);
633
634        let blob1 = signature_to_blob(&minhash(&shingle_set(&t1)).unwrap());
635        let blob2 = signature_to_blob(&minhash(&shingle_set(&t2)).unwrap());
636        assert_eq!(blob1, blob2);
637        assert_eq!(blob1.len(), NUM_PERMS * 8);
638
639        // Blob round-trip is lossless.
640        let sig = minhash(&shingle_set(&t1)).unwrap();
641        assert_eq!(blob_to_signature(&blob1).unwrap(), sig);
642        assert!(blob_to_signature(&blob1[..100]).is_none());
643    }
644
645    #[test]
646    fn test_snippet_tokenization_matches_whole_file_slice() {
647        // Verification re-tokenizes stored source snippets (e.g. a method
648        // without its impl block); tree-sitter's error tolerance must yield
649        // the same normalized stream as slicing a whole-file parse.
650        let file = "struct Foo {\n    x: i32,\n}\n\nimpl Foo {\n    fn double(&self) -> i32 {\n        let value = self.x * 2;\n        value + 1\n    }\n}\n";
651        let whole = tokenize(Language::Rust, file).unwrap();
652
653        // The method spans lines 6-9.
654        let sliced: Vec<String> = whole
655            .iter()
656            .filter(|t| t.line >= 6 && t.line <= 9)
657            .map(|t| t.text.clone())
658            .collect();
659        assert!(!sliced.is_empty());
660
661        let snippet: String = file.lines().skip(5).take(4).collect::<Vec<_>>().join("\n");
662        let snippet_toks: Vec<String> = tokenize(Language::Rust, &snippet)
663            .unwrap()
664            .into_iter()
665            .map(|t| t.text)
666            .collect();
667
668        assert_eq!(sliced, snippet_toks);
669    }
670
671    #[test]
672    fn test_jaccard_edge_cases() {
673        let empty: HashSet<u64> = HashSet::new();
674        let some: HashSet<u64> = [1, 2, 3].into_iter().collect();
675        assert_eq!(jaccard(&empty, &empty), 1.0);
676        assert_eq!(jaccard(&empty, &some), 0.0);
677        assert_eq!(jaccard(&some, &some), 1.0);
678    }
679}
ctx/fingerprint.rs

ctx/
fingerprint.rs
