pelicode_detect/lib.rs
1//! Detection of functions similar to the stored ones (specification ยง7).
2//!
3//! Candidates are searched in stages: exact hashes from the weakest to the
4//! strongest normalization, then LSH buckets, then the fingerprint sets of
5//! the LSH candidates are compared.
6
7#![warn(missing_docs)]
8
9use std::cell::{Cell, RefCell};
10use std::collections::{BTreeMap, HashMap, HashSet};
11use std::path::PathBuf;
12
13use pelicode_core::{FileFeatures, FunctionFeatures, Language, Level};
14use pelicode_db::{Database, FunctionInfo, Occurrence};
15use serde::Serialize;
16
17pub mod dependencies;
18
19pub use pelicode_db::Error;
20
21/// Result of the detection, whose errors are those of the database.
22pub type Result<T> = std::result::Result<T, Error>;
23
24/// Levels searched for exact matches, in order of preference.
25const EXACT_LEVELS: [Level; 3] = [Level::N0, Level::N1, Level::N2];
26
27/// Parameters of the search.
28///
29/// # Examples
30///
31/// ```
32/// use pelicode_detect::Options;
33///
34/// let options = Options { threshold: 0.5, stop_packages: 0, ..Options::default() };
35/// assert_eq!(options.max_candidates, 5);
36/// ```
37#[derive(Debug, Clone)]
38pub struct Options {
39 /// Functions with fewer tokens are not checked.
40 pub min_tokens: usize,
41 /// Minimum Jaccard similarity of fingerprint sets to report a candidate.
42 pub threshold: f64,
43 /// Candidates reported per function.
44 pub max_candidates: usize,
45 /// Occurrences listed per candidate.
46 pub max_occurrences: usize,
47 /// Packages whose functions are never reported, as `(ecosystem, name)`.
48 pub exclude_packages: Vec<(String, String)>,
49 /// Hashes found in at least this many packages are ignored (0 disables).
50 /// Needs the statistics of [`Database::refresh_hash_stats`].
51 pub stop_packages: usize,
52 /// Minimum number of shared (non-common) fingerprints for a similar match.
53 /// Without it, a function whose fingerprints are almost all common could
54 /// reach a high similarity through one or two remaining ones.
55 pub min_shared: usize,
56 /// Weight fingerprints by inverse document frequency, `ln(1 + N / df)`,
57 /// where N is the number of packages and df those containing the fingerprint.
58 pub idf: bool,
59 /// Packages the checked code depends on (see [`dependencies`]): candidates
60 /// found only in them are not reported, and their occurrences are left out
61 /// of the other candidates.
62 pub dependencies: dependencies::Dependencies,
63}
64
65impl Default for Options {
66 fn default() -> Self {
67 Options {
68 min_tokens: 50,
69 threshold: 0.7,
70 max_candidates: 5,
71 max_occurrences: 5,
72 exclude_packages: Vec::new(),
73 stop_packages: 100,
74 min_shared: 5,
75 idf: false,
76 dependencies: dependencies::Dependencies::default(),
77 }
78 }
79}
80
81/// How a candidate matched.
82#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize)]
83#[serde(tag = "type", content = "level", rename_all = "lowercase")]
84pub enum MatchKind {
85 /// Identical after normalization at the level.
86 Exact(Level),
87 /// Similar fingerprint sets at the level.
88 Similar(Level),
89}
90
91/// A stored function similar to a checked function.
92#[derive(Debug, Clone, Serialize)]
93pub struct Candidate {
94 /// How the candidate matched.
95 #[serde(rename = "match")]
96 pub kind: MatchKind,
97 /// 1.0 for exact matches; the (weighted) Jaccard similarity of fingerprint sets otherwise.
98 pub similarity: f64,
99 /// (Weighted) share of the checked function's fingerprints found in the candidate.
100 pub containment: f64,
101 /// For exact matches, the number of packages containing the same normalized function.
102 #[serde(skip_serializing_if = "Option::is_none")]
103 pub package_count: Option<usize>,
104 /// Number of fingerprints the two functions share, common ones excluded.
105 pub shared_fingerprints: usize,
106 /// Lines of the checked function covered by shared fingerprints.
107 pub matched_lines: Vec<(u32, u32)>,
108 /// Lines of the candidate covered by shared fingerprints.
109 pub candidate_lines: Vec<(u32, u32)>,
110 /// The stored function.
111 pub function: FunctionInfo,
112 /// Where the candidate appears, earliest publication first (at most `max_occurrences`).
113 pub occurrences: Vec<Occurrence>,
114 /// Number of places the stored function was found, excluded packages aside.
115 pub occurrence_count: usize,
116 /// Position of the database of the candidate in the detectors given to
117 /// [`detect_all`]; `function.id` is an id in that database.
118 #[serde(skip)]
119 pub database: usize,
120}
121
122/// Detection result of one checked function.
123#[derive(Debug, Clone, Serialize)]
124pub struct Report {
125 /// File of the checked function.
126 pub path: PathBuf,
127 /// Language of the checked function.
128 pub language: Language,
129 /// Name of the checked function.
130 pub name: String,
131 /// First line of the checked function (1-based).
132 pub start_line: usize,
133 /// Last line of the checked function (1-based, inclusive).
134 pub end_line: usize,
135 /// Number of tokens of the checked function.
136 pub token_count: usize,
137 /// Candidates, best first.
138 pub candidates: Vec<Candidate>,
139}
140
141/// Searches a database for functions similar to checked ones.
142///
143/// # Examples
144///
145/// ```
146/// # use pelicode_core::{Config, Language, extract_bytes};
147/// # use pelicode_db::{Database, PackageInfo};
148/// # use pelicode_detect::{Detector, MatchKind, Options};
149/// # let dir = tempfile::tempdir().unwrap();
150/// # let config = Config::default();
151/// # let mut db = Database::open(dir.path().join("pelicode.db"), &config).unwrap();
152/// let original = br#"class Search {
153/// static int find(int[] values, int key) {
154/// int low = 0, high = values.length - 1;
155/// while (low <= high) {
156/// int mid = (low + high) >>> 1;
157/// if (values[mid] < key) low = mid + 1;
158/// else if (values[mid] > key) high = mid - 1;
159/// else return mid;
160/// }
161/// return -(low + 1);
162/// }
163/// }"#;
164/// let package = PackageInfo {
165/// ecosystem: "maven".into(),
166/// name: "org.example:search".into(),
167/// version: "1.0".into(),
168/// ..PackageInfo::default()
169/// };
170/// let stored = extract_bytes("Search.java".as_ref(), Language::Java, original, &config).unwrap();
171/// db.index(&package, &[stored]).unwrap();
172///
173/// // The same code with other names.
174/// let copy = String::from_utf8_lossy(original)
175/// .replace("Search", "Finder").replace("values", "xs").replace("key", "target");
176/// let checked = extract_bytes("Finder.java".as_ref(), Language::Java, copy.as_bytes(), &config).unwrap();
177/// let detector = Detector::new(&db, Options { min_tokens: 20, ..Options::default() }).unwrap();
178/// let reports = detector.detect(&[checked], |_, _| true).unwrap();
179/// assert_eq!(reports[0].name, "find");
180/// assert_eq!(reports[0].candidates[0].kind, MatchKind::Exact(pelicode_core::Level::N1));
181/// assert_eq!(reports[0].candidates[0].occurrences[0].package, "org.example:search");
182/// ```
183pub struct Detector<'a> {
184 db: &'a Database,
185 options: Options,
186 /// Packages in the database, the N of IDF.
187 packages: usize,
188 document_frequencies: RefCell<HashMap<(Level, u64), usize>>,
189 /// Candidates left out because they were found only in dependencies.
190 excluded_as_dependencies: Cell<usize>,
191}
192
193impl<'a> Detector<'a> {
194 /// `db` must have been opened for features computed like the checked ones
195 /// (see [`Database::config_from_meta`]).
196 ///
197 /// # Errors
198 ///
199 /// [`Error`] when the database cannot be read.
200 ///
201 /// # Examples
202 ///
203 /// ```
204 /// use pelicode_core::Config;
205 /// use pelicode_db::Database;
206 /// use pelicode_detect::{Detector, Options};
207 ///
208 /// let dir = tempfile::tempdir().unwrap();
209 /// let db = Database::open(dir.path().join("pelicode.db"), &Config::default()).unwrap();
210 /// let detector = Detector::new(&db, Options::default()).unwrap();
211 /// ```
212 pub fn new(db: &'a Database, options: Options) -> Result<Detector<'a>> {
213 Ok(Detector {
214 db,
215 options,
216 packages: db.package_count()?,
217 document_frequencies: RefCell::new(HashMap::new()),
218 excluded_as_dependencies: Cell::new(0),
219 })
220 }
221
222 /// Number of candidates left out so far because they were found only in
223 /// [`Options::dependencies`].
224 ///
225 /// # Examples
226 ///
227 /// ```
228 /// use pelicode_core::{Config, Language, extract_bytes};
229 /// use pelicode_db::{Database, PackageInfo};
230 /// use pelicode_detect::{Detector, Options, dependencies::Dependencies};
231 ///
232 /// let dir = tempfile::tempdir().unwrap();
233 /// let config = Config { min_tokens: 0, ..Config::default() };
234 /// let mut db = Database::open(dir.path().join("pelicode.db"), &config).unwrap();
235 /// let source = b"def total(xs):\n s = 0\n for x in xs:\n s += x * 2\n return s\n";
236 /// let file = extract_bytes("calc.py".as_ref(), Language::Python, source, &config).unwrap();
237 /// let package = PackageInfo {
238 /// ecosystem: "pypi".into(), name: "calc".into(), version: "1.0".into(), ..PackageInfo::default()
239 /// };
240 /// db.index(&package, &[file.clone()]).unwrap();
241 ///
242 /// // The checked project depends on calc.
243 /// let mut dependencies = Dependencies::default();
244 /// dependencies.add_file("requirements.txt", "calc>=1\n");
245 /// let options = Options { min_tokens: 0, dependencies, ..Options::default() };
246 /// let detector = Detector::new(&db, options).unwrap();
247 /// assert!(detector.detect(&[file], |_, _| true).unwrap().is_empty());
248 /// assert_eq!(detector.excluded_as_dependencies(), 1);
249 /// ```
250 pub fn excluded_as_dependencies(&self) -> usize {
251 self.excluded_as_dependencies.get()
252 }
253
254 fn is_common(&self, package_count: usize) -> bool {
255 self.options.stop_packages > 0 && package_count >= self.options.stop_packages
256 }
257
258 /// Weight of a fingerprint; 0 for common ones.
259 fn weight(&self, level: Level, hash: u64) -> Result<f64> {
260 let cached = self
261 .document_frequencies
262 .borrow()
263 .get(&(level, hash))
264 .copied();
265 let df = match cached {
266 Some(df) => df,
267 None => {
268 let df = self.db.fingerprint_package_count(level, hash)?;
269 self.document_frequencies
270 .borrow_mut()
271 .insert((level, hash), df);
272 df
273 }
274 };
275 Ok(if self.is_common(df) {
276 0.0
277 } else if self.options.idf {
278 (1.0 + self.packages.max(1) as f64 / df.max(1) as f64).ln()
279 } else {
280 1.0
281 })
282 }
283
284 fn weights(
285 &self,
286 level: Level,
287 hashes: impl Iterator<Item = u64>,
288 ) -> Result<HashMap<u64, f64>> {
289 let mut weights = HashMap::new();
290 for hash in hashes {
291 if let std::collections::hash_map::Entry::Vacant(e) = weights.entry(hash) {
292 e.insert(self.weight(level, hash)?);
293 }
294 }
295 Ok(weights)
296 }
297
298 /// Checks the functions of `files` accepted by `select`; only functions
299 /// with at least one candidate are reported.
300 ///
301 /// # Errors
302 ///
303 /// [`Error`] when the database cannot be read.
304 ///
305 /// # Examples
306 ///
307 /// Only the functions accepted by `select` are checked, here those starting
308 /// after line 1:
309 ///
310 /// ```
311 /// # use pelicode_core::{Config, Language, extract_bytes};
312 /// # use pelicode_db::{Database, PackageInfo};
313 /// # use pelicode_detect::{Detector, MatchKind, Options};
314 /// # let dir = tempfile::tempdir().unwrap();
315 /// # let config = Config::default();
316 /// # let mut db = Database::open(dir.path().join("pelicode.db"), &config).unwrap();
317 /// let original = br#"class Search {
318 /// static int find(int[] values, int key) {
319 /// int low = 0, high = values.length - 1;
320 /// while (low <= high) {
321 /// int mid = (low + high) >>> 1;
322 /// if (values[mid] < key) low = mid + 1;
323 /// else if (values[mid] > key) high = mid - 1;
324 /// else return mid;
325 /// }
326 /// return -(low + 1);
327 /// }
328 /// }"#;
329 /// let package = PackageInfo {
330 /// ecosystem: "maven".into(),
331 /// name: "org.example:search".into(),
332 /// version: "1.0".into(),
333 /// ..PackageInfo::default()
334 /// };
335 /// let stored = extract_bytes("Search.java".as_ref(), Language::Java, original, &config).unwrap();
336 /// db.index(&package, &[stored]).unwrap();
337 ///
338 /// // The same code with other names.
339 /// let copy = String::from_utf8_lossy(original)
340 /// .replace("Search", "Finder").replace("values", "xs").replace("key", "target");
341 /// let checked = extract_bytes("Finder.java".as_ref(), Language::Java, copy.as_bytes(), &config).unwrap();
342 /// let detector = Detector::new(&db, Options { min_tokens: 20, ..Options::default() }).unwrap();
343 /// let reports = detector.detect(&[checked], |_, f| f.start_line > 1).unwrap();
344 /// assert_eq!(reports.len(), 1);
345 /// ```
346 pub fn detect(
347 &self,
348 files: &[FileFeatures],
349 select: impl Fn(&FileFeatures, &FunctionFeatures) -> bool,
350 ) -> Result<Vec<Report>> {
351 detect_all(std::slice::from_ref(self), files, select)
352 }
353
354 /// Candidates for one function, best first.
355 ///
356 /// Unlike [`Detector::detect`], the function is checked whatever its size.
357 ///
358 /// # Errors
359 ///
360 /// [`Error`] when the database cannot be read.
361 ///
362 /// # Examples
363 ///
364 /// ```
365 /// # use pelicode_core::{Config, Language, extract_bytes};
366 /// # use pelicode_db::{Database, PackageInfo};
367 /// # use pelicode_detect::{Detector, MatchKind, Options};
368 /// # let dir = tempfile::tempdir().unwrap();
369 /// # let config = Config::default();
370 /// # let mut db = Database::open(dir.path().join("pelicode.db"), &config).unwrap();
371 /// let original = br#"class Search {
372 /// static int find(int[] values, int key) {
373 /// int low = 0, high = values.length - 1;
374 /// while (low <= high) {
375 /// int mid = (low + high) >>> 1;
376 /// if (values[mid] < key) low = mid + 1;
377 /// else if (values[mid] > key) high = mid - 1;
378 /// else return mid;
379 /// }
380 /// return -(low + 1);
381 /// }
382 /// }"#;
383 /// let package = PackageInfo {
384 /// ecosystem: "maven".into(),
385 /// name: "org.example:search".into(),
386 /// version: "1.0".into(),
387 /// ..PackageInfo::default()
388 /// };
389 /// let stored = extract_bytes("Search.java".as_ref(), Language::Java, original, &config).unwrap();
390 /// db.index(&package, &[stored]).unwrap();
391 ///
392 /// // The same code with other names.
393 /// let copy = String::from_utf8_lossy(original)
394 /// .replace("Search", "Finder").replace("values", "xs").replace("key", "target");
395 /// let checked = extract_bytes("Finder.java".as_ref(), Language::Java, copy.as_bytes(), &config).unwrap();
396 /// let detector = Detector::new(&db, Options::default()).unwrap();
397 /// let candidates = detector.candidates(&checked.functions[0]).unwrap();
398 /// assert_eq!(candidates[0].similarity, 1.0);
399 /// assert_eq!(candidates[0].function.name, "find");
400 /// ```
401 pub fn candidates(&self, function: &FunctionFeatures) -> Result<Vec<Candidate>> {
402 let mut found: HashMap<i64, Match> = HashMap::new();
403
404 for level in EXACT_LEVELS {
405 let Some(hash) = function.exact_hashes.get(&level) else {
406 continue;
407 };
408 let package_count = self.db.exact_package_count(level, hash)?;
409 if self.is_common(package_count) {
410 continue;
411 }
412 for id in self.db.functions_by_exact_hash(level, hash)? {
413 found.entry(id).or_insert(Match {
414 kind: MatchKind::Exact(level),
415 similarity: 1.0,
416 containment: 1.0,
417 package_count: Some(package_count),
418 shared: 0,
419 matched_lines: vec![(function.start_line as u32, function.end_line as u32)],
420 candidate_lines: Vec::new(),
421 });
422 }
423 }
424
425 for (level, features) in &function.features {
426 let mut lsh_hits: HashSet<i64> = HashSet::new();
427 for (band, bucket) in features.lsh_buckets.iter().enumerate() {
428 lsh_hits.extend(self.db.functions_by_lsh_bucket(*level, band, *bucket)?);
429 }
430 let query = self.weights(*level, features.fingerprints.iter().map(|f| f.hash))?;
431 let query_weight: f64 = query.values().sum();
432 if query_weight == 0.0 {
433 // Nothing but common code.
434 continue;
435 }
436 for id in lsh_hits {
437 if found
438 .get(&id)
439 .is_some_and(|m| matches!(m.kind, MatchKind::Exact(_)))
440 {
441 continue;
442 }
443 let stored = self.db.fingerprints(id, *level)?;
444 let other = self.weights(*level, stored.iter().map(|f| f.hash))?;
445 let shared: HashSet<u64> = query
446 .iter()
447 .filter(|(h, w)| **w > 0.0 && other.contains_key(h))
448 .map(|(h, _)| *h)
449 .collect();
450 let shared_weight: f64 = shared.iter().map(|h| query[h]).sum();
451 let union = query_weight + other.values().sum::<f64>() - shared_weight;
452 let similarity = if union > 0.0 {
453 shared_weight / union
454 } else {
455 0.0
456 };
457 if similarity < self.options.threshold
458 || shared.is_empty()
459 || shared.len() < self.options.min_shared
460 {
461 continue;
462 }
463 let candidate = Match {
464 kind: MatchKind::Similar(*level),
465 similarity,
466 containment: shared_weight / query_weight,
467 package_count: None,
468 shared: shared.len(),
469 matched_lines: merge(
470 features
471 .fingerprints
472 .iter()
473 .filter(|f| shared.contains(&f.hash))
474 .map(|f| (f.start_line, f.end_line)),
475 ),
476 candidate_lines: merge(
477 stored
478 .iter()
479 .filter(|f| shared.contains(&f.hash))
480 .map(|f| (f.start_line, f.end_line)),
481 ),
482 };
483 // Keep the most similar level when several levels hit.
484 if found.get(&id).is_none_or(|m| m.similarity < similarity) {
485 found.insert(id, candidate);
486 }
487 }
488 }
489
490 let mut candidates = Vec::new();
491 for (id, m) in found {
492 let mut occurrences = self.db.occurrences(id)?;
493 occurrences.retain(|o| !self.is_excluded(o));
494 if occurrences.is_empty() {
495 continue;
496 }
497 occurrences.retain(|o| !self.options.dependencies.contains(&o.ecosystem, &o.package));
498 if occurrences.is_empty() {
499 self.excluded_as_dependencies
500 .set(self.excluded_as_dependencies.get() + 1);
501 continue;
502 }
503 let function_info = self.db.function_info(id)?;
504 let candidate_lines = if m.candidate_lines.is_empty() {
505 vec![(
506 function_info.start_line as u32,
507 function_info.end_line as u32,
508 )]
509 } else {
510 m.candidate_lines
511 };
512 let occurrence_count = occurrences.len();
513 occurrences.truncate(self.options.max_occurrences);
514 candidates.push(Candidate {
515 kind: m.kind,
516 similarity: m.similarity,
517 containment: m.containment,
518 package_count: m.package_count,
519 shared_fingerprints: m.shared,
520 matched_lines: m.matched_lines,
521 candidate_lines,
522 function: function_info,
523 occurrences,
524 occurrence_count,
525 database: 0,
526 });
527 }
528 candidates.sort_by(|a, b| {
529 b.similarity
530 .total_cmp(&a.similarity)
531 .then(a.kind.cmp(&b.kind))
532 .then(a.function.id.cmp(&b.function.id))
533 });
534 candidates.truncate(self.options.max_candidates);
535 Ok(candidates)
536 }
537
538 fn is_excluded(&self, o: &Occurrence) -> bool {
539 self.options
540 .exclude_packages
541 .iter()
542 .any(|(eco, name)| *eco == o.ecosystem && *name == o.package)
543 }
544}
545
546struct Match {
547 kind: MatchKind,
548 similarity: f64,
549 containment: f64,
550 package_count: Option<usize>,
551 shared: usize,
552 matched_lines: Vec<(u32, u32)>,
553 candidate_lines: Vec<(u32, u32)>,
554}
555
556/// Merges overlapping or adjacent line ranges.
557/// Checks the functions of `files` that `select` accepts against several
558/// databases at once, one detector each, and merges their candidates, best
559/// first. Each detector filters common code with the package counts of its
560/// own database. The size limits of the first detector's options apply.
561///
562/// The databases must hold features computed with the same parameters, the
563/// fingerprint levels aside (see [`Database::config_from_meta`]).
564///
565/// # Errors
566///
567/// [`Error`] when a database cannot be read.
568///
569/// # Examples
570///
571/// ```
572/// use pelicode_core::{Config, Language, extract_bytes};
573/// use pelicode_db::{Database, PackageInfo};
574/// use pelicode_detect::{Detector, Options, detect_all};
575///
576/// let dir = tempfile::tempdir().unwrap();
577/// let config = Config { min_tokens: 0, ..Config::default() };
578/// let source = b"def total(xs):\n s = 0\n for x in xs:\n s += x * 2\n return s\n";
579/// let file = extract_bytes("calc.py".as_ref(), Language::Python, source, &config).unwrap();
580/// let mut databases = Vec::new();
581/// for ecosystem in ["pypi", "crates"] {
582/// let mut db = Database::open(dir.path().join(format!("{ecosystem}.db")), &config).unwrap();
583/// let package = PackageInfo {
584/// ecosystem: ecosystem.into(), name: "calc".into(), version: "1.0".into(), ..PackageInfo::default()
585/// };
586/// db.index(&package, &[file.clone()]).unwrap();
587/// databases.push(db);
588/// }
589/// let options = Options { min_tokens: 0, ..Options::default() };
590/// let detectors: Vec<Detector> = databases
591/// .iter()
592/// .map(|db| Detector::new(db, options.clone()).unwrap())
593/// .collect();
594/// let reports = detect_all(&detectors, &[file], |_, _| true).unwrap();
595/// let found: Vec<_> = reports[0].candidates.iter().map(|c| c.occurrences[0].ecosystem.as_str()).collect();
596/// assert_eq!(found, ["pypi", "crates"]);
597/// ```
598pub fn detect_all(
599 detectors: &[Detector<'_>],
600 files: &[FileFeatures],
601 select: impl Fn(&FileFeatures, &FunctionFeatures) -> bool,
602) -> Result<Vec<Report>> {
603 let Some(first) = detectors.first() else {
604 return Ok(Vec::new());
605 };
606 let mut reports = Vec::new();
607 for file in files {
608 for function in &file.functions {
609 if function.token_count < first.options.min_tokens || !select(file, function) {
610 continue;
611 }
612 let mut candidates = Vec::new();
613 for (database, detector) in detectors.iter().enumerate() {
614 for mut candidate in detector.candidates(function)? {
615 candidate.database = database;
616 candidates.push(candidate);
617 }
618 }
619 if candidates.is_empty() {
620 continue;
621 }
622 candidates.sort_by(|a, b| {
623 b.similarity
624 .total_cmp(&a.similarity)
625 .then(a.kind.cmp(&b.kind))
626 .then(a.database.cmp(&b.database))
627 .then(a.function.id.cmp(&b.function.id))
628 });
629 candidates.truncate(first.options.max_candidates);
630 reports.push(Report {
631 path: file.path.clone(),
632 language: file.language,
633 name: function.name.clone(),
634 start_line: function.start_line,
635 end_line: function.end_line,
636 token_count: function.token_count,
637 candidates,
638 });
639 }
640 }
641 Ok(reports)
642}
643
644fn merge(ranges: impl Iterator<Item = (u32, u32)>) -> Vec<(u32, u32)> {
645 let sorted: BTreeMap<u32, u32> = ranges.fold(BTreeMap::new(), |mut acc, (s, e)| {
646 let end = acc.entry(s).or_insert(e);
647 *end = (*end).max(e);
648 acc
649 });
650 let mut merged: Vec<(u32, u32)> = Vec::new();
651 for (start, end) in sorted {
652 match merged.last_mut() {
653 Some(last) if start <= last.1 + 1 => last.1 = last.1.max(end),
654 _ => merged.push((start, end)),
655 }
656 }
657 merged
658}
659
660#[cfg(test)]
661mod tests {
662 use super::*;
663
664 #[test]
665 fn weights_follow_document_frequency() {
666 let dir = tempfile::tempdir().unwrap();
667 let db =
668 Database::open(dir.path().join("t.db"), &pelicode_core::Config::default()).unwrap();
669 let mut detector = Detector::new(&db, Options::default()).unwrap();
670 detector.packages = 3;
671 detector
672 .document_frequencies
673 .borrow_mut()
674 .insert((Level::N1, 1), 3);
675 detector
676 .document_frequencies
677 .borrow_mut()
678 .insert((Level::N1, 2), 1);
679 assert_eq!(detector.weight(Level::N1, 1).unwrap(), 1.0);
680 detector.options.idf = true;
681 assert!((detector.weight(Level::N1, 1).unwrap() - 2f64.ln()).abs() < 1e-9);
682 assert!((detector.weight(Level::N1, 2).unwrap() - 4f64.ln()).abs() < 1e-9);
683 detector.options.stop_packages = 3;
684 assert_eq!(detector.weight(Level::N1, 1).unwrap(), 0.0);
685 }
686
687 #[test]
688 fn merges_line_ranges() {
689 let ranges = [(5, 6), (1, 2), (3, 4), (10, 12), (11, 11), (8, 8)];
690 assert_eq!(merge(ranges.into_iter()), [(1, 6), (8, 8), (10, 12)]);
691 }
692}