Skip to main content

max / audiofiles

23.8 KB · 707 lines History Blame Raw
1 //! Tests for [`super`].
2
3 use super::*;
4 use crate::analysis::{self, AnalysisResult};
5 use crate::test_helpers::insert_fake_sample;
6
7 /// `(anchor, neighbours)` from a list of `(hash, distance)` pairs.
8 fn hood(anchor: &str, rows: &[(&str, f64)]) -> (String, Vec<SimilarResult>) {
9 (
10 anchor.to_owned(),
11 rows.iter()
12 .map(|(hash, distance)| SimilarResult {
13 hash: (*hash).to_owned(),
14 distance: *distance,
15 })
16 .collect(),
17 )
18 }
19
20 fn ranked(hits: &[BasketHit]) -> Vec<&str> {
21 hits.iter().map(|hit| hit.hash.as_str()).collect()
22 }
23
24 /// The contract the basket rests on: one anchor merged is the one-anchor
25 /// query, same rows in the same order. If this ever fails, a basket of one
26 /// has become a second kind of search rather than a special case of this one.
27 #[test]
28 fn a_basket_of_one_is_the_single_anchor_query() {
29 let rows = [("b", 0.1), ("c", 0.4), ("d", 0.2)];
30 let hits = merge_neighbourhoods(&[hood("a", &rows)], 10);
31
32 let mut expected: Vec<(&str, f64)> = rows.to_vec();
33 expected.sort_by(|a, b| a.1.total_cmp(&b.1));
34 assert_eq!(
35 ranked(&hits),
36 expected.iter().map(|(h, _)| *h).collect::<Vec<_>>()
37 );
38 for hit in &hits {
39 assert_eq!(hit.matched, vec!["a".to_owned()]);
40 }
41 }
42
43 /// "Near all of these" is the worst distance, not the sum and not the best.
44 /// `near_both` is further from the first anchor than `near_one` is, and still
45 /// wins, because `near_one` is not near the second anchor at all.
46 #[test]
47 fn the_ranking_minimises_the_worst_distance_to_any_anchor() {
48 let hits = merge_neighbourhoods(
49 &[
50 hood(
51 "a",
52 &[("near_one", 0.05), ("near_both", 0.30), ("far", 0.90)],
53 ),
54 hood("b", &[("near_both", 0.20), ("far", 0.80)]),
55 ],
56 10,
57 );
58
59 assert_eq!(ranked(&hits), vec!["near_both", "near_one", "far"]);
60 let near_both = &hits[0];
61 assert!(
62 (near_both.score - 0.30).abs() < f64::EPSILON,
63 "{near_both:?}"
64 );
65 assert_eq!(near_both.matched, vec!["a".to_owned(), "b".to_owned()]);
66 }
67
68 /// A sample missing from an anchor's neighbourhood is not at a known
69 /// distance from it. The last row that anchor did return stands in, so the
70 /// score is a lower bound: `near_one` scores 0.80 -- b's worst -- rather than
71 /// its own 0.05.
72 #[test]
73 fn a_sample_missing_from_a_neighbourhood_is_scored_from_that_anchors_last_row() {
74 let hits = merge_neighbourhoods(
75 &[
76 hood("a", &[("near_one", 0.05)]),
77 hood("b", &[("other", 0.80)]),
78 ],
79 10,
80 );
81
82 let near_one = hits.iter().find(|hit| hit.hash == "near_one").unwrap();
83 assert!((near_one.score - 0.80).abs() < f64::EPSILON, "{near_one:?}");
84 assert_eq!(near_one.matched, vec!["a".to_owned()]);
85 }
86
87 /// The accounting is the decided part, and it reads out in basket order
88 /// however the anchors happened to answer.
89 #[test]
90 fn each_hit_names_the_anchors_it_answered_to_in_basket_order() {
91 let hits = merge_neighbourhoods(
92 &[
93 hood("a", &[("x", 0.1)]),
94 hood("b", &[]),
95 hood("c", &[("x", 0.2)]),
96 ],
97 10,
98 );
99
100 let x = hits.iter().find(|hit| hit.hash == "x").unwrap();
101 assert_eq!(x.matched, vec!["a".to_owned(), "c".to_owned()]);
102 }
103
104 /// Every anchor, not merely the one being looked up. A per-anchor query drops
105 /// itself, so without this a basket of two hands back its own members.
106 #[test]
107 fn no_anchor_comes_back_as_its_own_result() {
108 let hits = merge_neighbourhoods(
109 &[
110 hood("a", &[("b", 0.01), ("x", 0.5)]),
111 hood("b", &[("a", 0.01), ("x", 0.6)]),
112 ],
113 10,
114 );
115
116 assert_eq!(ranked(&hits), vec!["x"]);
117 }
118
119 /// An anchor that came back cold says nothing about anything, so it must not
120 /// make every other anchor's answers unrankable.
121 #[test]
122 fn an_anchor_with_no_neighbours_penalises_nothing() {
123 let hits = merge_neighbourhoods(&[hood("a", &[("x", 0.2)]), hood("b", &[])], 10);
124
125 let x = hits.iter().find(|hit| hit.hash == "x").unwrap();
126 assert!((x.score - 0.2).abs() < f64::EPSILON, "{x:?}");
127 }
128
129 /// Two queries over an unchanged library give the same list in the same
130 /// order, including where scores tie. A ranking that shuffles is one the
131 /// reader cannot keep their place in.
132 #[test]
133 fn the_ranking_is_stable_where_scores_tie() {
134 let tied = [
135 hood("a", &[("q", 0.5), ("p", 0.5), ("r", 0.5)]),
136 hood("b", &[("r", 0.5), ("q", 0.5), ("p", 0.5)]),
137 ];
138 assert_eq!(
139 ranked(&merge_neighbourhoods(&tied, 10)),
140 vec!["p", "q", "r"]
141 );
142 assert_eq!(
143 merge_neighbourhoods(&tied, 10),
144 merge_neighbourhoods(&tied, 10)
145 );
146 }
147
148 #[test]
149 fn an_empty_basket_answers_nothing() {
150 assert!(merge_neighbourhoods(&[], 10).is_empty());
151 }
152
153 #[test]
154 fn the_limit_takes_the_nearest_rather_than_the_first_found() {
155 let hits = merge_neighbourhoods(
156 &[hood("a", &[("far", 0.9), ("near", 0.1), ("mid", 0.5)])],
157 2,
158 );
159 assert_eq!(ranked(&hits), vec!["near", "mid"]);
160 }
161
162 /// `feature_distance` is documented as a true weighted-Euclidean metric, the
163 /// VP-tree's triangle-inequality prune depends on it (a pseudometric could
164 /// drop a genuine nearest neighbour). Prove the property rather than assert it
165 /// in prose: over randomized vectors (incl. missing/imputed dims and the
166 /// non-finite values the ingest guard maps to imputed), the triangle
167 /// inequality d(a,c) <= d(a,b) + d(b,c) must hold.
168 #[test]
169 fn feature_distance_satisfies_triangle_inequality() {
170 // Deterministic LCG (no rand dep; reproducible). Numerical Recipes constants.
171 let mut state: u64 = 0x9E37_79B9_7F4A_7C15;
172 let mut next = || {
173 state = state
174 .wrapping_mul(6_364_136_223_846_793_005)
175 .wrapping_add(1_442_695_040_888_963_407);
176 (state >> 33) as f64 / (1u64 << 31) as f64 // [0, 2)
177 };
178 // A dim is None ~1/4 of the time, NaN ~1/16 (exercise the finite guard),
179 // else a value in roughly the normalized [0,1] range (with some spill).
180 let mut gen_vec = || {
181 let mut d = || -> Option<f64> {
182 let r = next();
183 if r < 0.5 {
184 None
185 } else if r < 0.625 {
186 Some(f64::NAN)
187 } else {
188 Some(next() / 2.0) // ~[0,1)
189 }
190 };
191 FeatureVector {
192 bpm: d(),
193 duration: d(),
194 lufs: d(),
195 spectral_centroid: d(),
196 spectral_flatness: d(),
197 spectral_rolloff: d(),
198 zero_crossing_rate: d(),
199 onset_strength: d(),
200 spectral_bandwidth: d(),
201 centroid_variance: d(),
202 crest_factor: d(),
203 attack_time: d(),
204 }
205 };
206
207 let weights = FeatureWeights::default();
208 for _ in 0..5000 {
209 let a = gen_vec();
210 let b = gen_vec();
211 let c = gen_vec();
212 let dab = feature_distance(&a, &b, &weights);
213 let dbc = feature_distance(&b, &c, &weights);
214 let dac = feature_distance(&a, &c, &weights);
215 // All distances finite (the non-finite guard holds).
216 assert!(dab.is_finite() && dbc.is_finite() && dac.is_finite());
217 // Triangle inequality with a small float-rounding tolerance.
218 assert!(
219 dac <= dab + dbc + 1e-9,
220 "triangle inequality violated: d(a,c)={dac} > d(a,b)+d(b,c)={}",
221 dab + dbc
222 );
223 }
224 }
225
226 fn insert_with_features(db: &Database, hash: &str, bpm: f64, duration: f64) {
227 insert_fake_sample(db, hash);
228 let result = AnalysisResult {
229 hash: hash.to_string(),
230 duration,
231 sample_rate: 44100,
232 channels: 1,
233 peak_db: None,
234 rms_db: None,
235 lufs: Some(-14.0),
236 bpm: Some(bpm),
237 musical_key: None,
238 is_loop: None,
239 spectral_centroid: Some(1000.0),
240 spectral_flatness: Some(0.5),
241 spectral_rolloff: Some(5000.0),
242 zero_crossing_rate: Some(0.1),
243 onset_strength: Some(20.0),
244 fingerprint: None,
245 spectral_bandwidth: Some(2000.0),
246 centroid_variance: Some(50000.0),
247 crest_factor: Some(3.0),
248 attack_time: Some(0.01),
249 feature_vector: None,
250 feature_version: None,
251 };
252 analysis::save_analysis_batch(db, std::slice::from_ref(&result)).unwrap();
253 }
254
255 #[test]
256 fn normalize_values() {
257 let fv = FeatureVector {
258 bpm: Some(120.0),
259 duration: Some(2.0),
260 ..Default::default()
261 };
262 let ranges = NormRanges {
263 bpm: (100.0, 200.0),
264 duration: (1.0, 3.0),
265 ..Default::default()
266 };
267 let normed = normalize(&fv, &ranges);
268 assert!((normed.bpm.unwrap() - 0.2).abs() < 1e-10);
269 assert!((normed.duration.unwrap() - 0.5).abs() < 1e-10);
270 }
271
272 #[test]
273 fn distance_zero_for_identical() {
274 let fv = FeatureVector {
275 bpm: Some(0.5),
276 duration: Some(0.5),
277 lufs: Some(0.5),
278 spectral_centroid: Some(0.5),
279 spectral_flatness: Some(0.5),
280 spectral_rolloff: Some(0.5),
281 zero_crossing_rate: Some(0.5),
282 onset_strength: Some(0.5),
283 spectral_bandwidth: Some(0.5),
284 centroid_variance: Some(0.5),
285 crest_factor: Some(0.5),
286 attack_time: Some(0.5),
287 };
288 let d = feature_distance(&fv, &fv, &FeatureWeights::default());
289 assert!((d - 0.0).abs() < f64::EPSILON);
290 }
291
292 #[test]
293 fn distance_symmetric() {
294 let a = FeatureVector {
295 bpm: Some(0.0),
296 duration: Some(1.0),
297 ..Default::default()
298 };
299 let b = FeatureVector {
300 bpm: Some(1.0),
301 duration: Some(0.0),
302 ..Default::default()
303 };
304 let w = FeatureWeights::default();
305 let d1 = feature_distance(&a, &b, &w);
306 let d2 = feature_distance(&b, &a, &w);
307 assert!((d1 - d2).abs() < f64::EPSILON);
308 }
309
310 #[test]
311 fn distance_satisfies_triangle_inequality_with_missing_dims() {
312 // The VP-tree index prunes on the triangle inequality, so the distance
313 // must satisfy d(a,c) <= d(a,b) + d(b,c) even when vectors have
314 // different sets of missing dimensions (the case the old per-pair
315 // denominator broke).
316 let w = FeatureWeights::default();
317 let a = FeatureVector {
318 bpm: Some(0.1),
319 duration: Some(0.9),
320 ..Default::default()
321 };
322 let b = FeatureVector {
323 bpm: Some(0.8),
324 lufs: Some(0.2),
325 ..Default::default()
326 };
327 let c = FeatureVector {
328 duration: Some(0.1),
329 spectral_centroid: Some(0.7),
330 ..Default::default()
331 };
332
333 let ab = feature_distance(&a, &b, &w);
334 let bc = feature_distance(&b, &c, &w);
335 let ac = feature_distance(&a, &c, &w);
336 assert!(
337 ac <= ab + bc + 1e-9,
338 "triangle inequality violated: d(a,c)={ac} > d(a,b)+d(b,c)={}",
339 ab + bc
340 );
341 }
342
343 #[test]
344 fn ranking_correctness() {
345 let db = Database::open_in_memory().unwrap();
346 insert_with_features(&db, "ref", 120.0, 1.0);
347 insert_with_features(&db, "close", 122.0, 1.1);
348 insert_with_features(&db, "far", 200.0, 10.0);
349
350 let results = find_similar(&db, "ref", 10).unwrap();
351 assert_eq!(results.len(), 2);
352 assert_eq!(results[0].hash, "close");
353 assert_eq!(results[1].hash, "far");
354 assert!(results[0].distance < results[1].distance);
355 }
356
357 #[test]
358 fn limit_respected() {
359 let db = Database::open_in_memory().unwrap();
360 insert_with_features(&db, "ref", 120.0, 1.0);
361 insert_with_features(&db, "a", 121.0, 1.0);
362 insert_with_features(&db, "b", 122.0, 1.0);
363 insert_with_features(&db, "c", 123.0, 1.0);
364
365 let results = find_similar(&db, "ref", 2).unwrap();
366 assert_eq!(results.len(), 2);
367 }
368
369 #[test]
370 fn missing_hash_errors() {
371 let db = Database::open_in_memory().unwrap();
372 let result = find_similar(&db, "nonexistent", 10);
373 assert!(result.is_err());
374 }
375
376 // --- SimilarityIndex tests ---
377
378 #[test]
379 fn index_build_empty() {
380 let db = Database::open_in_memory().unwrap();
381 let idx = SimilarityIndex::build(&db).unwrap();
382 assert!(idx.is_empty());
383 assert_eq!(idx.len(), 0);
384 }
385
386 #[test]
387 fn index_ranking_matches_linear() {
388 let db = Database::open_in_memory().unwrap();
389 insert_with_features(&db, "ref", 120.0, 1.0);
390 insert_with_features(&db, "close", 122.0, 1.1);
391 insert_with_features(&db, "far", 200.0, 10.0);
392
393 let linear = find_similar(&db, "ref", 10).unwrap();
394 let idx = SimilarityIndex::build(&db).unwrap();
395 let ref_features = load_features(&db, "ref").unwrap();
396 let indexed = idx.find_similar("ref", &ref_features, 10);
397
398 // Same ranking order.
399 assert_eq!(linear.len(), indexed.len());
400 for (l, i) in linear.iter().zip(indexed.iter()) {
401 assert_eq!(l.hash, i.hash, "Ranking order differs");
402 }
403 }
404
405 #[test]
406 fn index_limit_respected() {
407 let db = Database::open_in_memory().unwrap();
408 insert_with_features(&db, "ref", 120.0, 1.0);
409 insert_with_features(&db, "a", 121.0, 1.0);
410 insert_with_features(&db, "b", 122.0, 1.0);
411 insert_with_features(&db, "c", 123.0, 1.0);
412
413 let idx = SimilarityIndex::build(&db).unwrap();
414 let ref_features = load_features(&db, "ref").unwrap();
415 let results = idx.find_similar("ref", &ref_features, 2);
416 assert_eq!(results.len(), 2);
417 }
418
419 #[test]
420 fn index_excludes_self() {
421 let db = Database::open_in_memory().unwrap();
422 insert_with_features(&db, "only", 120.0, 1.0);
423
424 let idx = SimilarityIndex::build(&db).unwrap();
425 let features = load_features(&db, "only").unwrap();
426 let results = idx.find_similar("only", &features, 10);
427 assert!(results.is_empty());
428 }
429
430 // --- NeighbourGraph tests ---
431
432 /// A five-sample fixture whose pairwise distances are all distinct, so a
433 /// ranking disagreement is a real disagreement and never a tie broken two
434 /// ways. Only bpm and duration vary; the other ten dimensions are constant
435 /// across `insert_with_features`, which is what makes the arithmetic here
436 /// checkable by hand.
437 fn fixture_library() -> Database {
438 let db = Database::open_in_memory().unwrap();
439 insert_with_features(&db, "a", 100.0, 1.0);
440 insert_with_features(&db, "b", 120.0, 2.0);
441 insert_with_features(&db, "c", 150.0, 4.0);
442 insert_with_features(&db, "d", 180.0, 7.0);
443 insert_with_features(&db, "e", 200.0, 11.0);
444 db
445 }
446
447 /// Every stored edge, in a comparable order.
448 fn stored_edges(db: &Database) -> Vec<(String, String, f64, i64)> {
449 let mut stmt = db
450 .conn()
451 .prepare(
452 "SELECT hash, neighbour_hash, distance, rank FROM sample_neighbours
453 ORDER BY hash, rank",
454 )
455 .unwrap();
456 stmt.query_map([], |r| Ok((r.get(0)?, r.get(1)?, r.get(2)?, r.get(3)?)))
457 .unwrap()
458 .collect::<std::result::Result<_, _>>()
459 .unwrap()
460 }
461
462 /// The graph's ranking must be the brute-force oracle's ranking, for every
463 /// sample. This is the whole correctness claim: the table is a cache of an
464 /// answer that already has a right value, so it is checked against the
465 /// definition rather than against the index that produced it.
466 #[test]
467 fn graph_agrees_with_the_brute_force_oracle() {
468 let db = fixture_library();
469 let index = SimilarityIndex::build(&db).unwrap();
470 NeighbourGraph::rebuild(&db, &index).unwrap();
471
472 for hash in ["a", "b", "c", "d", "e"] {
473 let oracle = find_similar(&db, hash, GRAPH_K).unwrap();
474 let stored = NeighbourGraph::neighbours(&db, hash, GRAPH_K)
475 .unwrap()
476 .unwrap_or_else(|| panic!("graph declined to answer for {hash}"));
477 let oracle_hashes: Vec<&str> = oracle.iter().map(|r| r.hash.as_str()).collect();
478 let stored_hashes: Vec<&str> = stored.iter().map(|r| r.hash.as_str()).collect();
479 assert_eq!(stored_hashes, oracle_hashes, "ranking differs for {hash}");
480 for (s, o) in stored.iter().zip(oracle.iter()) {
481 assert!(
482 (s.distance - o.distance).abs() < 1e-12,
483 "distance differs for {hash} -> {}: {} vs {}",
484 s.hash,
485 s.distance,
486 o.distance
487 );
488 }
489 }
490 }
491
492 /// Patching one sample in must land on exactly the graph a rebuild would
493 /// have produced. If it does not, the incremental path is a second
494 /// implementation of the same idea rather than a cheaper route to it.
495 #[test]
496 fn incremental_insert_matches_a_full_rebuild() {
497 let db = fixture_library();
498 let before = SimilarityIndex::build(&db).unwrap();
499 NeighbourGraph::rebuild(&db, &before).unwrap();
500
501 // Interior on both varying dimensions, so the normalization ranges do
502 // not move and `refresh` is free to take the incremental path.
503 insert_with_features(&db, "f", 145.0, 3.5);
504 let after = SimilarityIndex::build(&db).unwrap();
505 NeighbourGraph::mark_dirty(&db, &["f".to_string()]).unwrap();
506 NeighbourGraph::refresh(&db, &after).unwrap();
507 let incremental = stored_edges(&db);
508
509 NeighbourGraph::rebuild(&db, &after).unwrap();
510 assert_eq!(incremental, stored_edges(&db));
511 }
512
513 /// Out-edges cascade with the sample row; back-edges have no foreign key to
514 /// cascade along, so they are the ones that rot. Nothing may point at a hash
515 /// that is gone, and the sources left short must be queued to refill.
516 #[test]
517 fn delete_leaves_no_edge_pointing_at_a_gone_sample() {
518 let db = fixture_library();
519 let index = SimilarityIndex::build(&db).unwrap();
520 NeighbourGraph::rebuild(&db, &index).unwrap();
521
522 db.conn()
523 .execute("DELETE FROM samples WHERE hash = 'c'", [])
524 .unwrap();
525
526 let dangling: i64 = db
527 .conn()
528 .query_row(
529 "SELECT COUNT(*) FROM sample_neighbours
530 WHERE neighbour_hash NOT IN (SELECT hash FROM samples)",
531 [],
532 |r| r.get(0),
533 )
534 .unwrap();
535 assert_eq!(dangling, 0, "back-edges to the deleted sample survived");
536
537 let own: i64 = db
538 .conn()
539 .query_row(
540 "SELECT COUNT(*) FROM sample_neighbours WHERE hash = 'c'",
541 [],
542 |r| r.get(0),
543 )
544 .unwrap();
545 assert_eq!(own, 0, "out-edges of the deleted sample survived");
546
547 let queued: i64 = db
548 .conn()
549 .query_row("SELECT COUNT(*) FROM neighbour_graph_dirty", [], |r| {
550 r.get(0)
551 })
552 .unwrap();
553 assert_eq!(queued, 4, "every source that lost an edge should be queued");
554 }
555
556 /// An insert outside the stored ranges invalidates every distance in the
557 /// table, not just the new sample's, because they were all normalized
558 /// against ranges that no longer hold. `refresh` has to notice and rebuild,
559 /// and the proof is that the graph still matches the oracle afterwards.
560 #[test]
561 fn a_widening_insert_rebuilds_rather_than_patches() {
562 let db = fixture_library();
563 let before = SimilarityIndex::build(&db).unwrap();
564 NeighbourGraph::rebuild(&db, &before).unwrap();
565
566 // Well outside both ranges the graph was built under. Outside on both
567 // axes rather than one, because widening a single axis rescales it
568 // alone and can leave two samples exactly equidistant from a third,
569 // where a ranking disagreement would be a coin toss rather than a bug.
570 insert_with_features(&db, "g", 400.0, 20.0);
571 let after = SimilarityIndex::build(&db).unwrap();
572 NeighbourGraph::mark_dirty(&db, &["g".to_string()]).unwrap();
573 NeighbourGraph::refresh(&db, &after).unwrap();
574
575 for hash in ["a", "b", "c", "d", "e", "g"] {
576 let oracle = find_similar(&db, hash, GRAPH_K).unwrap();
577 let stored = NeighbourGraph::neighbours(&db, hash, GRAPH_K)
578 .unwrap()
579 .unwrap_or_else(|| panic!("graph declined to answer for {hash}"));
580 let oracle_hashes: Vec<&str> = oracle.iter().map(|r| r.hash.as_str()).collect();
581 let stored_hashes: Vec<&str> = stored.iter().map(|r| r.hash.as_str()).collect();
582 assert_eq!(
583 stored_hashes, oracle_hashes,
584 "stale ranking survived a widening insert for {hash}"
585 );
586 }
587 }
588
589 /// The graph declines rather than answering wrongly: before it is built, once
590 /// it is marked stale, while a sample is queued, and past the k it stores.
591 /// Each of these sends the caller to the VP-tree, which is why a cold or
592 /// behind graph costs speed and never correctness.
593 #[test]
594 fn graph_declines_when_it_cannot_answer() {
595 let db = fixture_library();
596 assert!(NeighbourGraph::is_stale(&db).unwrap(), "never built");
597 assert!(NeighbourGraph::neighbours(&db, "a", 4).unwrap().is_none());
598
599 let index = SimilarityIndex::build(&db).unwrap();
600 NeighbourGraph::rebuild(&db, &index).unwrap();
601 assert!(!NeighbourGraph::is_stale(&db).unwrap());
602 assert!(NeighbourGraph::neighbours(&db, "a", 4).unwrap().is_some());
603
604 // Past the stored k there is no edge to answer with.
605 assert!(
606 NeighbourGraph::neighbours(&db, "a", GRAPH_K + 1)
607 .unwrap()
608 .is_none()
609 );
610
611 // Queued for update: the stored edges are known to be behind.
612 NeighbourGraph::mark_dirty(&db, &["a".to_string()]).unwrap();
613 assert!(NeighbourGraph::neighbours(&db, "a", 4).unwrap().is_none());
614 assert!(
615 NeighbourGraph::neighbours(&db, "b", 4).unwrap().is_some(),
616 "one queued sample should not silence the rest of the graph"
617 );
618
619 // Marked stale wholesale: nothing answers.
620 NeighbourGraph::mark_stale(&db).unwrap();
621 assert!(NeighbourGraph::is_stale(&db).unwrap());
622 assert!(NeighbourGraph::neighbours(&db, "b", 4).unwrap().is_none());
623 }
624
625 /// A sample unknown to the graph must not be answered with an empty list.
626 /// The short-row-set path trusts the row count only when the library really
627 /// is that small, and an unanalysed hash is the case that separates the two.
628 #[test]
629 fn an_unknown_sample_is_a_miss_not_an_empty_answer() {
630 let db = fixture_library();
631 let index = SimilarityIndex::build(&db).unwrap();
632 NeighbourGraph::rebuild(&db, &index).unwrap();
633 assert!(
634 NeighbourGraph::neighbours(&db, "nonexistent", 4)
635 .unwrap()
636 .is_none()
637 );
638 }
639
640 /// A one-sample library has no neighbours, and that is an answer rather than
641 /// a miss: the graph would otherwise never satisfy a library smaller than
642 /// the limit being asked for.
643 #[test]
644 fn a_complete_short_answer_is_still_an_answer() {
645 let db = Database::open_in_memory().unwrap();
646 insert_with_features(&db, "only", 120.0, 1.0);
647 let index = SimilarityIndex::build(&db).unwrap();
648 NeighbourGraph::rebuild(&db, &index).unwrap();
649 let rows = NeighbourGraph::neighbours(&db, "only", GRAPH_K)
650 .unwrap()
651 .expect("the whole library is covered");
652 assert!(rows.is_empty());
653 }
654
655 /// `remove` is the explicit form of what the delete trigger does, for a
656 /// caller unlinking a sample whose row stays.
657 #[test]
658 fn remove_unlinks_in_both_directions() {
659 let db = fixture_library();
660 let index = SimilarityIndex::build(&db).unwrap();
661 NeighbourGraph::rebuild(&db, &index).unwrap();
662
663 NeighbourGraph::remove(&db, "c").unwrap();
664
665 let touching: i64 = db
666 .conn()
667 .query_row(
668 "SELECT COUNT(*) FROM sample_neighbours WHERE hash = 'c' OR neighbour_hash = 'c'",
669 [],
670 |r| r.get(0),
671 )
672 .unwrap();
673 assert_eq!(touching, 0);
674 let queued: bool = db
675 .conn()
676 .query_row(
677 "SELECT EXISTS(SELECT 1 FROM neighbour_graph_dirty WHERE hash = 'a')",
678 [],
679 |r| r.get(0),
680 )
681 .unwrap();
682 assert!(queued, "sources left short should be queued to refill");
683 }
684
685 #[test]
686 fn index_sorted_by_distance() {
687 let db = Database::open_in_memory().unwrap();
688 insert_with_features(&db, "ref", 120.0, 1.0);
689 insert_with_features(&db, "a", 125.0, 2.0);
690 insert_with_features(&db, "b", 130.0, 3.0);
691 insert_with_features(&db, "c", 140.0, 5.0);
692 insert_with_features(&db, "d", 200.0, 10.0);
693
694 let idx = SimilarityIndex::build(&db).unwrap();
695 let ref_features = load_features(&db, "ref").unwrap();
696 let results = idx.find_similar("ref", &ref_features, 10);
697
698 for w in results.windows(2) {
699 assert!(
700 w[0].distance <= w[1].distance,
701 "Results not sorted: {} > {}",
702 w[0].distance,
703 w[1].distance
704 );
705 }
706 }
707