ingraph 0.1.0

A declaration-driven indexing framework: records and nodes are written as Rust types, and the storage rows, the dataflow between them and the GraphQL query surface are emitted from the declaration.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
//! The fold's arithmetic, pinned against values computed BY HAND rather than against the
//! implementation's own answer.
//!
//! Every expected score below is written as a decimal somebody worked out from `1 / (k + rank)`, and
//! compared within `1e-15`. The tolerance is for `f64` representation and nothing else: every
//! misreading this file is built to catch — the list position instead of the engine ordinal, a
//! second sighting added instead of dropped, the damping constant ignored — moves a score by parts
//! in a thousand or reorders the answer outright, which is four orders of magnitude past what the
//! epsilon admits.

use std::rc::Rc;

use super::super::{EqJoin, Fused, Fusion, HashJoin, Rooted, fuse};

/// The evidence an emitted union would carry, standing in for it: one variant per member, and
/// nothing the fold could read even if it wanted to.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Saw {
  Transcript,
  Voiceprint,
  Caption,
}

/// A root that CANNOT hash — the escape [`EqJoin`] exists for, stated as a type.
#[derive(Debug, Clone, PartialEq)]
struct Coordinate(f64);

/// How close a hand-computed decimal has to be to count.
const EPSILON: f64 = 1e-15;

fn list(hits: &[(&'static str, u64, Saw)]) -> Vec<Rooted<&'static str, Saw>> {
  hits
    .iter()
    .map(|(root, rank, saw)| Rooted::new(*root, *rank, *saw))
    .collect()
}

/// WHAT EACH MEMBER SAID, in the order the fold put them — the evidence with its contribution set
/// aside, so a claim about PROVENANCE reads as one list rather than as a list of pairs.
fn saw<R>(row: &Fused<R, Saw>) -> Vec<Saw> {
  row.evidence().iter().map(|held| *held.seen()).collect()
}

/// The roots, in the order the fold ranked them.
fn order<V>(fused: &[Fused<&'static str, V>]) -> Vec<&'static str> {
  fused.iter().map(|row| row.root()).collect()
}

fn score<V>(fused: &[Fused<&'static str, V>], root: &str) -> f64 {
  fused
    .iter()
    .find(|row| *row.root_ref() == root)
    .unwrap_or_else(|| panic!("{root} is in the answer"))
    .score()
    .get()
}

#[track_caller]
fn close(got: f64, hand_computed: f64) {
  assert!(
    (got - hand_computed).abs() < EPSILON,
    "{got} is not {hand_computed}"
  );
}

/// **The overlapping case, every number worked out by hand at `k = 60`.**
///
/// ```text
/// transcript:  m1@1  m2@2  m3@3
/// voiceprint:  m2@1  m3@2  m4@3
///
/// m1 = 1/61                  = 0.01639344262295082
/// m2 = 1/62 + 1/61           = 0.03252247488101534
/// m3 = 1/63 + 1/62           = 0.03200204813108039
/// m4 = 1/63                  = 0.015873015873015872
/// ```
///
/// Which is the whole ruled pipeline's payoff in one answer: `m2` was neither member's best hit and
/// it wins, because two members agreeing beats one member's certainty.
#[test]
fn two_overlapping_lists_fuse_to_the_hand_computed_scores() {
  let fused = fuse::<_, _, HashJoin<_>>(
    vec![
      list(&[
        ("m1", 1, Saw::Transcript),
        ("m2", 2, Saw::Transcript),
        ("m3", 3, Saw::Transcript),
      ]),
      list(&[
        ("m2", 1, Saw::Voiceprint),
        ("m3", 2, Saw::Voiceprint),
        ("m4", 3, Saw::Voiceprint),
      ]),
    ],
    Fusion::rrf(),
  );

  assert_eq!(order(&fused), vec!["m2", "m3", "m1", "m4"]);
  close(score(&fused, "m1"), 0.016_393_442_622_950_82);
  close(score(&fused, "m2"), 0.032_522_474_881_015_34);
  close(score(&fused, "m3"), 0.032_002_048_131_080_39);
  close(score(&fused, "m4"), 0.015_873_015_873_015_872);
}

/// **The evidence is CONTRIBUTION-ordered, which is not member order.**
///
/// `m2` was the voiceprint's first hit and the transcript's second, so the voiceprint contributed
/// `1/61` against the transcript's `1/62` and goes first — the reverse of the order the lists were
/// passed in. A fold that carried evidence in member order would pass every assertion above and fail
/// only here, which is why this is its own test.
#[test]
fn the_evidence_leads_with_the_member_that_moved_the_root_most() {
  let fused = fuse::<_, _, HashJoin<_>>(
    vec![
      list(&[("m2", 2, Saw::Transcript)]),
      list(&[("m2", 1, Saw::Voiceprint)]),
    ],
    Fusion::rrf(),
  );

  assert_eq!(
    saw(&fused[0]),
    [Saw::Voiceprint, Saw::Transcript],
    "the biggest contribution is the UI's primary jump point"
  );
  // AND THE NUMBER THAT ORDERED THEM IS CARRIED (#296-L2): the list is not merely in contribution
  // order, it says what each contribution was — the half a reader cannot recover from the order.
  let terms: Vec<f64> = fused[0]
    .evidence()
    .iter()
    .map(super::super::Sighting::contribution)
    .collect();
  assert!(terms[0] > terms[1], "{terms:?}");
  assert!(
    (terms.iter().sum::<f64>() - fused[0].score().get()).abs() < 1e-12,
    "the entries do not add up to the score they made: {terms:?}",
  );
}

/// **A member that did not rank the root has NO entry** — evidence is one per contributor, never one
/// per member of the catalog.
#[test]
fn evidence_names_only_the_members_that_ranked_it() {
  let fused = fuse::<_, _, HashJoin<_>>(
    vec![
      list(&[("m1", 1, Saw::Transcript)]),
      list(&[("m2", 1, Saw::Voiceprint)]),
      list(&[("m1", 1, Saw::Caption)]),
    ],
    Fusion::rrf(),
  );

  assert_eq!(saw(&fused[0]), [Saw::Transcript, Saw::Caption]);
  assert_eq!(saw(&fused[1]), [Saw::Voiceprint]);
}

/// **The disjoint case, and the TIE LAW it exposes.**
///
/// Nothing overlaps, so every root wears exactly one member's term and the two lists produce two
/// pairs of identical scores. No ruling sets a tie-break, and the sort is stable, so equal scores
/// come back in FIRST-SIGHTING order across the member lists as they were passed: `a` then `c` at
/// `1/61`, `b` then `d` at `1/62`.
#[test]
fn disjoint_lists_interleave_by_score_and_ties_keep_first_sighting_order() {
  let fused = fuse::<_, _, HashJoin<_>>(
    vec![
      list(&[("a", 1, Saw::Transcript), ("b", 2, Saw::Transcript)]),
      list(&[("c", 1, Saw::Voiceprint), ("d", 2, Saw::Voiceprint)]),
    ],
    Fusion::rrf(),
  );

  assert_eq!(order(&fused), vec!["a", "c", "b", "d"]);
  close(score(&fused, "a"), 0.016_393_442_622_950_82);
  close(score(&fused, "c"), 0.016_393_442_622_950_82);
  close(score(&fused, "b"), 0.016_129_032_258_064_516);
  close(score(&fused, "d"), 0.016_129_032_258_064_516);
}

/// **Nothing to fuse is an empty answer, at all three shapes of nothing.**
#[test]
fn the_empty_cases_answer_empty() {
  let no_members = fuse::<&str, Saw, HashJoin<_>>(vec![], Fusion::rrf());
  assert!(no_members.is_empty(), "no members at all");

  let empty_members = fuse::<&str, Saw, HashJoin<_>>(vec![vec![], vec![]], Fusion::rrf());
  assert!(empty_members.is_empty(), "members that returned nothing");

  let one_answered = fuse::<_, _, HashJoin<_>>(
    vec![vec![], list(&[("m1", 1, Saw::Transcript)]), vec![]],
    Fusion::rrf(),
  );
  assert_eq!(order(&one_answered), vec!["m1"]);
  close(score(&one_answered, "m1"), 0.016_393_442_622_950_82);
}

/// **The rank is the ENGINE's ordinal, holes and all — and the holes change the answer.**
///
/// The transcript returned two survivors out of a hundred hits: `p` at 1 and `q` at 100. Reading the
/// engine's numbers, `q`'s term is `1/160` and it finishes LAST, behind `r`'s single `1/62`. A fold
/// reading LIST POSITIONS instead would score `q` at `1/62` — a tie with `r`, broken by first
/// sighting in `q`'s favour — and answer `[p, s, q, r]`.
///
/// Both readings agree on everything else in this fixture, which is the point of it: the two differ
/// in exactly one swap, and only a corpus whose floor actually dropped hits can produce it.
#[test]
fn a_hole_in_the_ranks_is_read_as_the_engine_meant_it() {
  let fused = fuse::<_, _, HashJoin<_>>(
    vec![
      list(&[("p", 1, Saw::Transcript), ("q", 100, Saw::Transcript)]),
      list(&[("s", 1, Saw::Voiceprint), ("r", 2, Saw::Voiceprint)]),
    ],
    Fusion::rrf(),
  );

  assert_eq!(
    order(&fused),
    vec!["p", "s", "r", "q"],
    "reading list positions would answer [p, s, q, r]"
  );
  close(score(&fused, "q"), 0.006_25);
  close(score(&fused, "r"), 0.016_129_032_258_064_516);
}

/// **`k` is a real knob: the same two lists rank differently under two values of it.**
///
/// `x` is one member's top hit; `y` is two members' third. At `k = 0` a first place is worth `1.0`
/// and `y`'s two thirds are worth `2/3`, so certainty wins. At the shipped `k = 60` the top of each
/// list is damped to `1/61` and `y`'s agreement — `2/63` — wins instead. That crossover is the only
/// thing the constant does.
#[test]
fn the_damping_constant_decides_between_certainty_and_agreement() {
  let lists = || {
    vec![
      list(&[("x", 1, Saw::Transcript), ("y", 3, Saw::Transcript)]),
      list(&[("y", 3, Saw::Voiceprint)]),
    ]
  };

  let undamped = fuse::<_, _, HashJoin<_>>(lists(), Fusion::Rrf { k: 0 });
  assert_eq!(order(&undamped), vec!["x", "y"]);
  close(score(&undamped, "x"), 1.0);
  close(score(&undamped, "y"), 0.666_666_666_666_666_6);

  let shipped = fuse::<_, _, HashJoin<_>>(lists(), Fusion::rrf());
  assert_eq!(order(&shipped), vec!["y", "x"]);
  close(score(&shipped, "x"), 0.016_393_442_622_950_82);
  close(score(&shipped, "y"), 0.031_746_031_746_031_744);
}

/// **One member counts ONCE per root, and the sighting it counts is the first.**
///
/// The transcript hands the same root back twice, at ranks 1 and 5. The `@5` sighting is dropped
/// whole: `m1`'s score is `1/61` alone and its evidence has one entry, so it merely TIES the root a
/// different member ranked first rather than beating it.
///
/// Adding the second term instead would score `m1` at `1/61 + 1/65 = 0.031778…`, put it strictly
/// first, and give it two pieces of evidence — which is a fused ranking measuring how many segments
/// of a video matched instead of how many members agreed.
#[test]
fn a_members_second_sighting_of_a_root_is_dropped_whole() {
  let fused = fuse::<_, _, HashJoin<_>>(
    vec![
      list(&[("m1", 1, Saw::Transcript), ("m1", 5, Saw::Transcript)]),
      list(&[("m2", 1, Saw::Voiceprint)]),
    ],
    Fusion::rrf(),
  );

  assert_eq!(order(&fused), vec!["m1", "m2"], "a tie, not a win");
  close(score(&fused, "m1"), 0.016_393_442_622_950_82);
  close(score(&fused, "m2"), 0.016_393_442_622_950_82);
  assert_eq!(saw(&fused[0]), [Saw::Transcript]);
}

/// **Adding a member never lowers a root's SCORE, and raises it wherever that member ranked it.**
///
/// The sound half of the monotonicity claim, and the one RRF actually makes: a contribution is
/// positive, so fusing one more list is an addition to some accumulators and a no-op on the rest.
#[test]
fn adding_a_member_can_only_raise_a_score() {
  let first = list(&[
    ("d", 1, Saw::Transcript),
    ("e", 2, Saw::Transcript),
    ("f", 3, Saw::Transcript),
  ]);
  let second = list(&[("e", 1, Saw::Voiceprint), ("d", 5, Saw::Voiceprint)]);

  let alone = fuse::<_, _, HashJoin<_>>(vec![first.clone()], Fusion::rrf());
  let both = fuse::<_, _, HashJoin<_>>(vec![first, second], Fusion::rrf());

  for root in ["d", "e", "f"] {
    assert!(
      score(&both, root) >= score(&alone, root),
      "{root} lost score by being fused with more evidence"
    );
  }
  assert!(score(&both, "d") > score(&alone, "d"), "ranked by both");
  assert!(score(&both, "e") > score(&alone, "e"), "ranked by both");
  close(score(&both, "f"), score(&alone, "f"));
}

/// **A root's POSITION can still fall, and the property that says otherwise is FALSE.**
///
/// The plausible-sounding claim — *a document in both lists never ranks below its single-list self*
/// — does not hold under RRF, and this is the counterexample rather than a caveat about one:
///
/// ```text
/// transcript:  d@1  e@2          voiceprint:  e@1  d@5
///
/// transcript alone:  d = 1/61 = 0.016393…   e = 1/62 = 0.016129…      → [d, e]
/// both fused:        d = 1/61 + 1/65 = 0.031778…
///                    e = 1/62 + 1/61 = 0.032522…                      → [e, d]
/// ```
///
/// `d` is in BOTH lists, its score ROSE, and it moved from first to second — because `e` was in both
/// lists too and gained more. Rank is a comparison, so a claim about one row's position is a claim
/// about every other row's gain, and nothing bounds that.
///
/// Recorded as a test rather than as a sentence so the false property cannot be asserted later by
/// someone who reasoned about it the same way and stopped one step earlier.
#[test]
fn a_roots_position_can_fall_even_where_its_score_rose() {
  let first = list(&[("d", 1, Saw::Transcript), ("e", 2, Saw::Transcript)]);
  let second = list(&[("e", 1, Saw::Voiceprint), ("d", 5, Saw::Voiceprint)]);

  let alone = fuse::<_, _, HashJoin<_>>(vec![first.clone()], Fusion::rrf());
  assert_eq!(order(&alone), vec!["d", "e"]);

  let both = fuse::<_, _, HashJoin<_>>(vec![first, second], Fusion::rrf());
  assert_eq!(order(&both), vec!["e", "d"]);

  close(score(&both, "d"), 0.031_778_058_007_566_21);
  close(score(&both, "e"), 0.032_522_474_881_015_34);
  assert!(
    score(&both, "d") > score(&alone, "d"),
    "the score rose while the position fell"
  );
}

/// **Both join mechanisms answer the same fusion**, which is what makes the choice a bounds choice
/// rather than a semantic one — [`Seen`](crate::Seen)'s own claim, one stage up.
#[test]
fn the_equality_mechanism_fuses_the_same_answer() {
  let lists = || {
    vec![
      list(&[("m1", 1, Saw::Transcript), ("m2", 4, Saw::Transcript)]),
      list(&[("m2", 1, Saw::Voiceprint), ("m3", 2, Saw::Voiceprint)]),
    ]
  };

  let hashed = fuse::<_, _, HashJoin<_>>(lists(), Fusion::rrf());
  let walked = fuse::<_, _, EqJoin<_>>(lists(), Fusion::rrf());

  assert_eq!(hashed, walked);
}

/// **A root that cannot hash fuses through the equality mechanism** — the escape actually escapes,
/// and the same call against [`HashJoin`] would not compile.
#[test]
fn a_root_that_cannot_hash_still_fuses() {
  let fused = fuse::<_, _, EqJoin<_>>(
    vec![
      vec![Rooted::new(Coordinate(0.5), 1, Saw::Transcript)],
      vec![Rooted::new(Coordinate(0.5), 2, Saw::Voiceprint)],
    ],
    Fusion::rrf(),
  );

  assert_eq!(fused.len(), 1, "one root, sighted twice");
  close(fused[0].score().get(), 0.032_522_474_881_015_34);
}

/// **The fold asks NOTHING of the evidence type.**
///
/// `Opaque` holds an `Rc`, so it is neither `Send` nor `Sync`; it derives nothing, implements
/// nothing, and cannot be cloned, compared or hashed. It rides through the fold and comes back in
/// contribution order, which is the whole of the seat's contract — the emitted evidence union is a
/// type this crate has never seen, and a bound here would be a bound on every declaration.
#[test]
fn the_evidence_seat_is_bare() {
  struct Opaque(Rc<str>);

  let fused = fuse::<_, _, HashJoin<_>>(
    vec![
      vec![Rooted::new("m1", 9, Opaque(Rc::from("second")))],
      vec![Rooted::new("m1", 1, Opaque(Rc::from("first")))],
    ],
    Fusion::rrf(),
  );

  let names: Vec<&str> = fused[0]
    .evidence()
    .iter()
    .map(|held| held.seen().0.as_ref())
    .collect();
  assert_eq!(names, vec!["first", "second"]);
}

/// **A rank of zero is clamped rather than turned into an infinity.**
///
/// Not an ordinal any engine produces — the walk mints them 1-based — so this is the caller who
/// passed a list index. The clamp keeps the answer finite and therefore diagnosable: at `k = 0` the
/// hit scores `1.0`, exactly as a first place would, instead of an `inf` that outranks the corpus
/// for a reason no one can see.
#[test]
fn a_zero_rank_cannot_become_an_infinity() {
  let fused = fuse::<_, _, HashJoin<_>>(
    vec![vec![Rooted::new("m1", 0, Saw::Transcript)]],
    Fusion::Rrf { k: 0 },
  );

  close(fused[0].score().get(), 1.0);
  assert!(fused[0].score().get().is_finite());
}

/// **A saturating denominator**: a rank at the top of `u64` cannot wrap into a small one and turn the
/// worst hit in a stream into the best row in the answer.
#[test]
fn an_enormous_rank_saturates_instead_of_wrapping() {
  let fused = fuse::<_, _, HashJoin<_>>(
    vec![
      vec![Rooted::new("far", u64::MAX, Saw::Transcript)],
      vec![Rooted::new("near", 1, Saw::Voiceprint)],
    ],
    Fusion::rrf(),
  );

  assert_eq!(order(&fused), vec!["near", "far"]);
  assert!(score(&fused, "far") > 0.0, "still a contribution");
  assert!(score(&fused, "far") < 1e-18, "and a vanishing one");
}