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
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
use core::{
  num::NonZeroUsize,
  pin::pin,
  task::{Context, Poll, Waker},
};
use std::sync::{Arc, Mutex};

use smol_bytes::Utf8Bytes;

use super::{AsyncVectorStore, VectorColumn, VectorEngine};
use crate::{
  AsyncVectorRead, AsyncVectorWrite, ColumnReader, ColumnWriter, Connected, Embedding, Field, Hits,
  Identifiable, Scored, Transformer, VectorRecord,
  store::column::testkit::{Col, Fallback, FallbackRead, Refusal},
};

/// The `k` every `knn` below hands the verb — the universal fact the seam now takes positionally,
/// spelled once so a test reads as a question rather than as a number.
const NEIGHBOURS: NonZeroUsize = NonZeroUsize::new(10).expect("10 is not zero");

/// Drive a `ready` future to its value without a runtime.
///
/// Hand-rolled rather than taken from an executor crate: every future here is already-ready, so what
/// this needs is one poll and a `Waker` that is never woken — and adding an async runtime as a
/// dev-dependency to spin a `Ready` would be a dependency the tests do not spend.
fn block_on<F: Future>(future: F) -> F::Output {
  let mut future = pin!(future);
  let mut cx = Context::from_waker(Waker::noop());
  loop {
    if let Poll::Ready(value) = future.as_mut().poll(&mut cx) {
      return value;
    }
  }
}

/// The width every fixture here declares, small enough to build in a test and spelled ONCE so the
/// record type, the slot's `dim` and the assertions cannot drift apart by hand.
const DIM: usize = 8;

// A keyed embedding: the compound lineage key `(media, ordinal)`, and the embedding as a FIELD at
// its own type. The shape every vector declaration has.
struct Keyframe {
  media: u64,
  ordinal: u32,
  embedding: Embedding<f32, DIM>,
}

#[derive(Debug, Clone, PartialEq)]
struct KeyframeKey {
  media: u64,
  ordinal: u32,
}

// THE KEY'S OWN ROW, in the column language: two columns, at their own widths, in the key's order.
// It names no engine, which is the whole of what the merged row bought — this one impl is what every
// engine below and every engine anywhere reads the key through.
impl Field for KeyframeKey {
  fn write(&self, w: &mut impl ColumnWriter) {
    self.media.write(w);
    self.ordinal.write(w);
  }

  fn read<R: ColumnReader>(r: &mut R) -> Result<Self, R::Error> {
    Ok(Self {
      media: u64::read(r)?,
      ordinal: u32::read(r)?,
    })
  }
}

// The ancestor half of that key: the `media` step, with the ordinal left off. It is also what a
// search over this record scopes by, which is why one type answers both — *nearest within media X*
// is the lineage, named as a filter.
#[derive(Debug, PartialEq)]
struct KeyframeLineage {
  media: u64,
}

impl Identifiable for Keyframe {
  type Id = u32;

  fn id_ref(&self) -> &u32 {
    &self.ordinal
  }
}

impl Transformer for Keyframe {
  type Key = KeyframeKey;
  type Lineage = KeyframeLineage;
  type Record = Self;
  // Nothing exposes this record on a wire, and the SEARCH SCOPE below answers a different question:
  // `KeyframeLineage` is `VectorRecord::Filter`, the lineage a knn is narrowed by, where this member
  // is the predicate a client sends against a row.
  type Graphql = ();

  fn key(&self) -> KeyframeKey {
    KeyframeKey {
      media: self.media,
      ordinal: self.ordinal,
    }
  }
}

// The one column this record elects, named once so the impl and the assertions cannot drift.
const EMBEDDING: VectorColumn = VectorColumn::new("embedding");

// Two associated types and one method, which is the whole face. A `const DIM` — or any third item —
// added to `VectorRecord` is `E0046` HERE and at every other impl below: an impl names what its
// trait declares, so the valve holding the width off this trait is enforced by these impls rather
// than by a comment. See the trait's own section on the width having one home.
//
// ONE election, written as a one-item iterator rather than as a second shape: N = 1 is the smallest
// N, and a face that answered a slice here would make the single-election case the one nothing else
// is like.
impl VectorRecord for Keyframe {
  type Element = f32;
  type Filter = KeyframeLineage;

  fn vectors(&self) -> impl Iterator<Item = (VectorColumn, &[f32])> {
    core::iter::once((EMBEDDING, self.embedding.coordinates()))
  }
}

fn keyframe(media: u64, ordinal: u32) -> Keyframe {
  Keyframe {
    media,
    ordinal,
    embedding: Embedding::new(Arc::from(vec![0.5; DIM])).expect("the fixture declares DIM"),
  }
}

// An element that implements NOTHING — not a numeric trait, not `Copy`, not a framework marker.
//
// It is the ELEMENT SETTLEMENT stated as a type. `VectorRecord::Element` is the element itself and
// carries no bound, so what an engine can MATERIALIZE stays that engine's question, asked at its own
// impl. Any bound added to that member turns this fixture red, which is the pin the settlement gets
// instead of the mutation a bound-carrying member would have had.
struct Q8(u8);

struct Quantized(Vec<Q8>);

impl VectorRecord for Quantized {
  type Element = Q8;
  type Filter = ();

  fn vectors(&self) -> impl Iterator<Item = (VectorColumn, &[Q8])> {
    core::iter::once((VectorColumn::new("quantized"), self.0.as_slice()))
  }
}

/// The coordinates of a record's ONE column, for the fixtures here that elect one.
///
/// # Panics
/// Never for the two records above, each of which yields exactly one.
fn only(record: &impl VectorRecord<Element = f32>) -> &[f32] {
  let mut columns = record.vectors();
  let (_, coordinates) = columns.next().expect("one election");
  assert!(columns.next().is_none(), "and only one");
  coordinates
}

/// The record face: the elected columns by reference, each at the element the record declared.
///
/// The width comes off the FIELD's type rather than off the trait, which is why the assertion reads
/// `Embedding::<f32, DIM>::DIM` — one fact, asked where it lives. The COLUMN comes off the election,
/// and a record electing one still names it: what a `knn` selects by is a property of a column, so a
/// slot with one column has one name rather than no name.
#[test]
fn a_vector_record_states_its_coordinates() {
  let frame = keyframe(7, 12);

  assert_eq!(
    frame.vectors().collect::<Vec<_>>(),
    [(EMBEDDING, &[0.5; DIM][..])],
    "one election, under the name it was elected by",
  );
  assert_eq!(only(&frame).len(), Embedding::<f32, DIM>::DIM);

  fn coordinates_of<T: VectorRecord>(record: &T) -> Vec<(VectorColumn, &[T::Element])> {
    record.vectors().collect()
  }
  assert_eq!(coordinates_of(&frame)[0].1.len(), DIM);
}

/// The two capabilities are independent: a bound naming [`VectorRecord`] alone reaches the
/// coordinates, and a record with no [`Transformer`] address still has them.
///
/// `Quantized` is that record, and its element is a type implementing nothing at all — so this also
/// asserts what the element member does NOT require.
#[test]
fn the_embedding_face_carries_no_identity() {
  fn width_of<T: VectorRecord>(record: &T) -> usize {
    record.vectors().map(|(_, held)| held.len()).sum()
  }

  let quantized = Quantized(vec![Q8(1), Q8(2), Q8(3)]);

  assert_eq!(width_of(&quantized), 3);
  assert_eq!(quantized.vectors().next().expect("one election").1[2].0, 3);
}

/// The unused face is a live implementation of the seam, which is what makes the seam's shape
/// provable: every associated type resolves, `upsert` takes the engine's own entry, and `knn` takes
/// the engine's own element.
///
/// The verbs are reached through the FACES now — the base carries none — and the base's own three
/// phases are asked for beside them, which is the whole of what it has left to answer.
#[test]
fn the_unused_face_answers_the_whole_seam() {
  assert_eq!(
    block_on(AsyncVectorWrite::upsert(&(), Connected::new(&(), ()), ())),
    Ok(())
  );
  assert_eq!(
    block_on(AsyncVectorRead::knn(
      &(),
      Connected::new(&(), ()),
      VectorColumn::new("nothing"),
      &[],
      NEIGHBOURS,
      None
    )),
    Ok(Vec::new())
  );

  // The whole lifecycle at the unit: a buffer that accepts every column and drops it, an address
  // that is the unit, and a read phase whose only honest answer is that it landed nothing.
  //
  // Generic in the BASE, as the full-text twin is: the three phases compose for every engine, and
  // the unit is where the composition is instantiated. What the unit adds is the pair below — a
  // column written and then not there — and that pair is the engine's answer rather than the walk's.
  fn write_then_read<E: VectorEngine>() -> (Result<i64, E::Error>, Result<(), E::Error>) {
    let mut buffer = E::buffer();
    7_i64.write(&mut buffer);
    let mut phase = E::open(E::finalize(buffer));
    let read = i64::read(&mut phase);
    (read, phase.finish())
  }

  assert_eq!(write_then_read::<()>(), (Err(crate::NoColumns), Ok(())));
}

/// NEITHER verb projects anything off a record, which is A′ as an assertion.
///
/// Written as two generic functions rather than as calls, because an ABSENCE of bounds is what is
/// being asserted: both are generic over the ENGINE alone, name no record type at all, and carry no
/// `where` beyond the seam itself.
///
/// MUTATION-CHECKED, as the full-text twin is: putting the record parameter back on the trait
/// (`trait VectorEngine<R>`) is `E0107` at both signatures below — *trait takes 1 generic argument
/// but 0 generic arguments were supplied* — and takes the toy face and the retrieve mirror's own
/// engine with it.
#[test]
fn neither_verb_projects_a_record() {
  fn index_anything<D>(db: &D, doc: D::Doc) -> impl Future<Output = Result<(), D::Error>>
  where
    D: AsyncVectorWrite<Connection = (), WriteContext<'static> = ()>,
  {
    db.upsert(Connected::new(&(), ()), doc)
  }

  fn search<D>(
    db: &D,
    column: VectorColumn,
    query: &[D::Element],
  ) -> impl Future<Output = Result<Hits<D::Address, D::Score>, D::Error>>
  where
    // `SearchOptions: 'static` — see the full-text twin for what a `None` costs a helper whose
    // returned future has no input lifetime to hang the borrow on.
    D: AsyncVectorRead<Connection = (), ReadContext<'static> = ()>,
    D::SearchOptions: 'static,
  {
    db.knn(Connected::new(&(), ()), column, query, NEIGHBOURS, None)
  }

  assert_eq!(block_on(index_anything::<()>(&(), ())), Ok(()));
  assert_eq!(block_on(search::<()>(&(), EMBEDDING, &[])), Ok(Vec::new()));
}

// A toy index over one slot: it records the WIDTH of everything written to it and answers every
// search with the single hit it was seeded with. Not a backend — what it proves is that the seam
// TURNS with a body in it.
//
// Its own carriers are its own: the entry is the width the emission measured off the record, and the
// address is what the key it was seeded with SEALED to. Neither is anything this crate names, which
// is the whole of what the R-free seam bought.
struct MemoryIndex {
  widths: Mutex<Vec<usize>>,
  hit: Vec<Col>,
}

/// The address type is no longer a free parameter, and the reason is the lifecycle rather than a
/// simplification: an engine's address is what ITS OWN buffer seals to, so the three phases pin the
/// three types to one another and a toy borrowing somebody else's key type as its address has
/// nothing to seal.
///
/// The phases here are `store::column`'s own toy pair — the sink with only the required kinds, so
/// every defaulted method's body runs and each landed column is opaque bytes.
impl VectorEngine for MemoryIndex {
  type Options = ();
  type SearchOptions = ();
  type Error = Refusal;
  type Score = f32;
  type Element = f32;
  type Address = Vec<Col>;
  type Connection = ();
  type WriteBuffer = Fallback;
  type ReadBuffer = FallbackRead;

  fn buffer() -> Self::WriteBuffer {
    Fallback::default()
  }

  fn finalize(buf: Self::WriteBuffer) -> Self::Address {
    buf.0
  }

  fn open(address: Self::Address) -> Self::ReadBuffer {
    Fallback(address).read()
  }
}

impl AsyncVectorWrite for MemoryIndex {
  type WriteContext<'a> = ();
  type Doc = usize;

  fn upsert(
    &self,
    _ctx: Connected<'_, Self::Connection, Self::WriteContext<'_>>,
    doc: Self::Doc,
  ) -> impl Future<Output = Result<(), Self::Error>> + Send {
    self
      .widths
      .lock()
      .expect("the toy index is not poisoned")
      .push(doc);
    core::future::ready(Ok(()))
  }
}

impl AsyncVectorRead for MemoryIndex {
  type ReadContext<'a> = ();

  fn knn(
    &self,
    _ctx: Connected<'_, Self::Connection, Self::ReadContext<'_>>,
    _column: VectorColumn,
    query: &[Self::Element],
    _k: NonZeroUsize,
    _options: ::core::option::Option<&Self::SearchOptions>,
  ) -> impl Future<Output = Result<Hits<Self::Address, Self::Score>, Self::Error>> + Send {
    // The score carries the query's width, so a caller can tell the query actually arrived —
    // a real face would answer a distance here, in whichever direction its metric runs.
    core::future::ready(Ok(vec![Scored::new(self.hit.clone(), query.len() as f32)]))
  }

  // This toy stores WIDTHS rather than coordinates, so it holds no vector at any address and says
  // exactly that. Empty is a legal answer at the seam — an engine owes no opinion about a key whose
  // vectors it does not keep — and the emitted door is where it becomes the unindexed refusal.
  fn get(
    &self,
    _ctx: Connected<'_, Self::Connection, Self::ReadContext<'_>>,
    _column: VectorColumn,
    _address: &Self::Address,
  ) -> impl Future<Output = Result<Vec<Vec<Self::Element>>, Self::Error>> + Send {
    core::future::ready(Ok(Vec::new()))
  }
}

/// `key`, sealed into this engine's address — the WRITE half of the lifecycle, spelled here as the
/// framework's own walk spells it one layer up.
fn addressed(key: &KeyframeKey) -> Vec<Col> {
  let mut buf = MemoryIndex::buffer();
  key.write(&mut buf);
  MemoryIndex::finalize(buf)
}

/// A face with a BODY: the write takes the entry the EMISSION built out of the record, and the
/// search hands back the engine's own addresses.
///
/// The emission is the two lines above the call — the record's elected column and `frame.key()` —
/// and that is exactly where A′ moved them to. Nothing is qualified: the seam names no record, so
/// there is no record for inference to be ambiguous about, where the record-generic form needed
/// `VectorDb::<Keyframe>::knn(…)` to escape `E0284`.
#[test]
fn a_written_face_takes_the_entry_and_answers_with_addresses() {
  let frame = keyframe(7, 12);
  let index = MemoryIndex {
    widths: Mutex::new(Vec::new()),
    hit: addressed(&frame.key()),
  };

  assert_eq!(
    block_on(index.upsert(Connected::new(&(), ()), only(&frame).len())),
    Ok(())
  );
  assert_eq!(
    *index.widths.lock().expect("the toy index is not poisoned"),
    vec![DIM]
  );

  let hits = block_on(index.knn(
    Connected::new(&(), ()),
    EMBEDDING,
    only(&frame),
    NEIGHBOURS,
    None,
  ))
  .expect("the toy index cannot fail");
  assert_eq!(hits.len(), 1);
  assert_eq!(hits[0].data_ref(), &addressed(&frame.key()));
  assert_eq!(hits[0].score(), DIM as f32);

  // THE ROUND TRIP, at the seam that owns it: the address a hit arrived under, opened and read back
  // into the key it was sealed from — and asked whether the key took all of it.
  let mut phase = MemoryIndex::open(hits[0].clone().into_data());
  assert_eq!(
    KeyframeKey::read(&mut phase).expect("the address is this key's"),
    frame.key()
  );
  assert_eq!(phase.finish(), Ok(()));
}

// A store standing in for a real backend's two layers: the manager is opened once, and it records
// what each per-slot handle was minted for.
struct RecordingStore {
  minted: Mutex<Vec<(Utf8Bytes, usize)>>,
}

impl AsyncVectorStore for RecordingStore {
  type Options = ();
  type Error = core::convert::Infallible;
  type Handle = ();

  async fn open(_options: Self::Options) -> Result<Self, Self::Error> {
    Ok(Self {
      minted: Mutex::new(Vec::new()),
    })
  }

  fn vector(&self, slot: impl Into<Utf8Bytes>, dim: usize) -> Self::Handle {
    self
      .minted
      .lock()
      .expect("the recording store is not poisoned")
      .push((slot.into(), dim));
  }
}

/// The construction layer: open once, mint per slot. `vector` is sync and infallible, so a caller
/// mints a handle wherever it needs one without threading a `Result` or an await.
///
/// And the width a DECLARED column is minted with comes off the field's own type — the call site
/// reads [`Embedding::DIM`], which is the one home the record trait deliberately does not duplicate.
/// The second call is the caller the `usize` keeps the door open for: a width nothing declared.
#[test]
fn a_declared_width_reaches_the_slot_through_the_field_type() {
  let store = block_on(RecordingStore::open(())).expect("the recording store opens");

  store.vector("keyframe_embedding", Embedding::<f32, DIM>::DIM);
  // A slot is text the caller supplies, so both doors into the crate's one string type reach it.
  store.vector(String::from("caption_embedding"), 4 * 96);

  let minted = store
    .minted
    .lock()
    .expect("the recording store is not poisoned");
  let minted: Vec<(&str, usize)> = minted.iter().map(|(slot, dim)| (&**slot, *dim)).collect();

  assert_eq!(
    minted,
    vec![("keyframe_embedding", DIM), ("caption_embedding", 384)]
  );
}