use crate::Context;
use core::time::Duration;
use std::{
convert::Infallible,
sync::{Arc, Mutex},
thread,
time::SystemTime,
};
use super::{
super::{
AsyncLands, Attributes, Commit, Delivery, Item, ItemId, JournalRow, Ledger, Payload,
RecordingTap, Resident, Station, Taps, ack_channel, channel,
},
Answers, AsyncAnswers, Invoke, QueryArm, QueryError, door, reply,
};
use crate::{Arrival, Emitter, NodeName, Operator, drive::Drives};
const DEADLINE: Duration = Duration::from_secs(10);
type Vector = Vec<f32>;
type Hits = Vec<u64>;
#[derive(Debug, Clone, PartialEq, Eq)]
struct Keyframe {
id: u64,
}
#[derive(Debug, Clone, PartialEq)]
struct Entry {
key: u64,
vector: Vector,
}
#[derive(Debug, Clone, Default)]
struct Index(Arc<Mutex<Vec<Entry>>>);
impl Index {
fn write(&self, entries: &[Entry]) {
let mut held = self.0.lock().expect("the index");
for entry in entries {
match held.iter_mut().find(|held| held.key == entry.key) {
Some(existing) => existing.vector.clone_from(&entry.vector),
None => held.push(entry.clone()),
}
}
}
fn nearest(&self, query: &[f32], k: usize) -> Hits {
let held = self.0.lock().expect("the index");
let mut scored: Vec<(u64, f32)> = held
.iter()
.map(|entry| {
let distance = entry
.vector
.iter()
.zip(query)
.map(|(a, b)| (a - b) * (a - b))
.sum::<f32>();
(entry.key, distance)
})
.collect();
scored.sort_by(|a, b| a.1.partial_cmp(&b.1).expect("no NaN in a toy vector"));
scored.into_iter().take(k).map(|(key, _)| key).collect()
}
fn len(&self) -> usize {
self.0.lock().expect("the index").len()
}
}
struct ImageTower;
impl Operator for ImageTower {
type Error = Infallible;
type In = Keyframe;
type Out = Entry;
fn accept(
&mut self,
_ctx: &Context,
delivery: Delivery<Self::In>,
emitter: &mut Emitter<Entry>,
) -> Result<(), Self::Error> {
for item in delivery.into_items() {
let item = item.into_value();
#[expect(
clippy::cast_precision_loss,
reason = "a toy id is small by construction"
)]
let coordinate = item.id as f32;
emitter.emit(Entry {
key: item.id,
vector: vec![coordinate, 0.0],
});
}
Ok(())
}
}
struct Indexer;
impl Operator for Indexer {
type Error = Infallible;
type In = Entry;
type Out = Entry;
fn accept(
&mut self,
_ctx: &Context,
delivery: Delivery<Self::In>,
emitter: &mut Emitter<Entry>,
) -> Result<(), Self::Error> {
for item in delivery.into_items() {
let item = item.into_value();
emitter.emit(item);
}
Ok(())
}
}
#[derive(Debug, Clone)]
struct Latch {
entered: flume::Sender<()>,
release: flume::Receiver<()>,
}
struct IndexLane {
index: Index,
latch: Option<Latch>,
}
impl AsyncLands<Entry> for IndexLane {
type Error = Infallible;
async fn land(&mut self, items: &[Entry]) -> Commit<Self::Error> {
if let Some(latch) = &self.latch {
let _ = latch.entered.send(());
let _ = latch.release.recv();
}
self.index.write(items);
Commit::all()
}
}
struct TextTower;
#[derive(Debug, derive_more::Display)]
#[display("a query needs something to search for")]
struct EmptyQuery;
impl core::error::Error for EmptyQuery {}
impl Answers<String> for TextTower {
type Error = EmptyQuery;
type Output = Vector;
fn on_invoke(&mut self, input: String) -> Result<Vector, Self::Error> {
if input.is_empty() {
return Err(EmptyQuery);
}
#[expect(
clippy::cast_precision_loss,
reason = "a toy corpus is small by construction"
)]
let coordinate = input.split_whitespace().count() as f32;
Ok(vec![coordinate, 0.0])
}
}
struct Lookup {
index: Index,
k: usize,
}
impl Answers<String> for Lookup {
type Error = EmptyQuery;
type Output = Hits;
fn on_invoke(&mut self, input: String) -> Result<Hits, Self::Error> {
let mut tower = TextTower;
let vector = tower.on_invoke(input)?;
Ok(self.index.nearest(&vector, self.k))
}
}
struct VectorSearch {
index: Index,
k: usize,
}
impl Answers<Vector> for VectorSearch {
type Error = Infallible;
type Output = Hits;
fn on_invoke(&mut self, input: Vector) -> Result<Hits, Self::Error> {
Ok(self.index.nearest(&input, self.k))
}
}
impl AsyncAnswers<Vector> for VectorSearch {
type Error = Infallible;
type Output = Hits;
async fn on_invoke(&mut self, input: Vector) -> Result<Hits, Self::Error> {
Ok(self.index.nearest(&input, self.k))
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
struct Row {
root: u64,
node: String,
station: Station,
}
impl JournalRow<u64> for Row {
fn of(root: &u64, node: &NodeName, arrival: &Arrival, _at: SystemTime) -> Self {
Self {
root: *root,
node: node.as_str().to_owned(),
station: arrival.station(),
}
}
}
type Rows = Arc<Mutex<Vec<Row>>>;
struct Runs(Rows);
impl Ledger for Runs {
type Error = Infallible;
type Row = Row;
fn record(&mut self, rows: &[Row]) -> Result<(), Self::Error> {
self.0.lock().expect("the rows").extend_from_slice(rows);
Ok(())
}
async fn record_async(&mut self, rows: &[Row]) -> Result<(), Self::Error> {
self.record(rows)
}
}
struct Roots;
impl Attributes<Entry> for Roots {
type Root = u64;
fn root(&self, record: &Entry) -> u64 {
record.key
}
fn observe(&self, _root: &u64, _worker: &NodeName, _arrival: &Arrival) {}
}
#[test]
fn a_reply_carries_the_result_and_a_dropped_one_is_a_typed_error() {
let (answer, awaiting) = reply::<Hits>();
assert!(answer.is_awaited());
assert!(answer.answer(vec![7, 9]));
assert_eq!(awaiting.take().expect("answered"), vec![7, 9]);
let (answer, awaiting) = reply::<Hits>();
drop(answer);
assert_eq!(awaiting.take().expect_err("dropped"), QueryError::Dropped);
}
#[test]
fn a_reply_nobody_is_waiting_for_is_dropped_rather_than_held() {
let (answer, awaiting) = reply::<Hits>();
drop(awaiting);
assert!(!answer.is_awaited());
assert!(
!answer.answer(vec![1]),
"a withdrawn question keeps nothing"
);
}
#[test]
fn a_door_with_nobody_behind_it_is_unreachable() {
let (front, invokes) = door::<String, Hits>(1);
drop(invokes);
assert!(front.is_closed());
assert_eq!(
front.invoke("red car".to_owned()).expect_err("nobody home"),
QueryError::Unreachable
);
}
#[test]
fn a_deadline_says_which_way_the_wait_ended() {
let (answer, awaiting) = reply::<Hits>();
assert_eq!(
awaiting
.take_within(Duration::from_millis(20))
.expect_err("nothing answered"),
QueryError::TimedOut
);
drop(answer);
let (answer, awaiting) = reply::<Hits>();
drop(answer);
assert_eq!(
awaiting.take_within(DEADLINE).expect_err("dropped"),
QueryError::Dropped
);
}
#[test]
fn the_query_errors_read_as_what_they_are() {
fn is_error<E: core::error::Error>(_: &E) {}
is_error(&QueryError::Dropped);
assert!(QueryError::Unreachable.is_unreachable());
assert!(
QueryError::Dropped
.to_string()
.contains("without an answer")
);
assert!(QueryError::TimedOut.to_string().contains("deadline"));
assert!(
QueryError::Unreachable
.to_string()
.contains("not listening")
);
}
#[test]
fn an_invoke_splits_into_the_input_and_the_reply_that_travels_past_it() {
let (answer, awaiting) = reply::<Hits>();
let invoke = Invoke::new("red car".to_owned(), answer);
assert_eq!(invoke.input(), "red car");
let (input, answer) = invoke.into_parts();
assert_eq!(input, "red car");
let onward = Invoke::new(vec![1.0_f32], answer);
let (_, answer) = onward.into_parts();
assert!(answer.answer(vec![3]));
assert_eq!(awaiting.take().expect("answered"), vec![3]);
}
#[test]
fn a_transient_inbox_carries_invokes_and_ends_when_every_door_is_gone() {
let (front, invokes) = door::<String, Hits>(4);
assert!(invokes.is_empty());
let first = front.invoke("a".to_owned()).expect("listening");
let second = front.invoke("b".to_owned()).expect("listening");
assert_eq!(invokes.len(), 2);
let taken = invokes.park().expect("queued");
assert_eq!(taken.input(), "a");
drop(taken);
drop(second);
drop(first);
let taken = invokes.park().expect("queued");
assert_eq!(taken.input(), "b");
drop(taken);
drop(front);
assert!(invokes.is_disconnected());
assert!(invokes.park().is_none(), "shutdown is every door gone");
}
#[test]
fn a_terminal_arm_answers_its_caller() {
let index = Index::default();
index.write(&[
Entry {
key: 1,
vector: vec![1.0, 0.0],
},
Entry {
key: 9,
vector: vec![9.0, 0.0],
},
]);
let (front, invokes) = door::<Vector, Hits>(4);
let mut arm = QueryArm::new("index", VectorSearch { index, k: 1 }, invokes);
assert_eq!(arm.name().as_str(), "index");
assert_eq!(arm.queued(), 0);
let awaiting = front.invoke(vec![8.6, 0.0]).expect("listening");
drop(front);
let served = arm.run();
assert_eq!(awaiting.take().expect("answered"), vec![9]);
assert_eq!(served.invokes(), 1);
assert_eq!(served.passed(), 1);
assert_eq!(served.abandoned(), 0);
assert_eq!(served.failed(), 0);
}
#[test]
fn a_refused_query_drops_the_reply_and_the_tap_keeps_the_error() {
let tap = Arc::new(RecordingTap::new());
let (front, invokes) = door::<String, Hits>(4);
let mut arm = QueryArm::new(
"tower",
Lookup {
index: Index::default(),
k: 1,
},
invokes,
)
.with_taps(Taps::new().with(tap.clone()));
let awaiting = front.invoke(String::new()).expect("listening");
drop(front);
let served = arm.run();
assert_eq!(awaiting.take().expect_err("refused"), QueryError::Dropped);
assert_eq!(served.failed(), 1);
assert_eq!(served.passed(), 0);
assert_eq!(tap.seen(), vec![("tower".to_owned(), Station::Failed)]);
}
#[test]
fn an_answer_nobody_waited_for_is_abandoned_and_never_retried() {
let (front, invokes) = door::<String, Hits>(4);
let mut arm = QueryArm::new(
"tower",
Lookup {
index: Index::default(),
k: 1,
},
invokes,
);
let awaiting = front.invoke("red car".to_owned()).expect("listening");
drop(awaiting);
drop(front);
let served = arm.run();
assert_eq!(served.invokes(), 1);
assert_eq!(served.abandoned(), 1);
assert_eq!(served.passed(), 0);
assert_eq!(served.failed(), 0);
}
#[test]
fn an_answered_query_is_observed_which_is_the_trace_the_exemption_claims() {
let tap = Arc::new(RecordingTap::new());
let (front, invokes) = door::<String, Hits>(4);
let mut arm = QueryArm::new(
"tower",
Lookup {
index: Index::default(),
k: 1,
},
invokes,
)
.with_taps(Taps::new().with(tap.clone()));
let awaiting = front.invoke("a red car".to_owned()).expect("listening");
drop(front);
arm.run();
assert_eq!(awaiting.take().expect("answered").len(), 0);
assert_eq!(tap.seen(), vec![("tower".to_owned(), Station::Processed)]);
}
#[test]
fn the_async_engine_serves_the_same_chain_as_the_thread_one() {
let index = Index::default();
index.write(&[Entry {
key: 4,
vector: vec![4.0, 0.0],
}]);
let (front, invokes) = door::<Vector, Hits>(4);
let mut arm = QueryArm::new("index", VectorSearch { index, k: 1 }, invokes);
let awaiting = front.invoke(vec![4.0, 0.0]).expect("listening");
drop(front);
let served = tokio::runtime::Builder::new_current_thread()
.build()
.expect("a current-thread runtime")
.block_on(arm.run_async());
assert_eq!(awaiting.take().expect("answered"), vec![4]);
assert_eq!(served.passed(), 1);
}
#[test]
fn a_query_round_trips_through_two_hops_into_a_true_fan_in() {
let index = Index::default();
let rows: Rows = Rows::default();
let (images_out, images_in) = channel::<ItemId, Keyframe>(8);
let (entries_out, entries_in) = channel::<ItemId, Entry>(8);
let (front, queries) = door::<String, Hits>(4);
let (search_door, searches) = door::<Vector, Hits>(4);
let mut tower = Resident::new("images", ImageTower, images_in).publish(entries_out);
let mut writer = Resident::new("index", Indexer, entries_in)
.land(IndexLane {
index: index.clone(),
latch: None,
})
.attributing(Roots)
.recording_to(Runs(Arc::clone(&rows)));
let mut text = QueryArm::new("text", TextTower, queries).forwarding_to(search_door);
let mut reader = QueryArm::new(
"index",
VectorSearch {
index: index.clone(),
k: 2,
},
searches,
);
let tower_run = thread::Builder::new()
.name("images".to_owned())
.spawn(move || tower.run())
.expect("the image tower's thread");
let writer_run = thread::Builder::new()
.name("index".to_owned())
.spawn(move || writer.run())
.expect("the index node's write arm");
let text_run = thread::Builder::new()
.name("text".to_owned())
.spawn(move || text.run())
.expect("the text tower's arm");
let reader_run = thread::Builder::new()
.name("search".to_owned())
.spawn(move || reader.run())
.expect("the index node's read arm");
let (ack, answers) = ack_channel();
images_out
.deliver(Delivery::new(
Payload::Batch(vec![
Item::new(ItemId::new(1), Keyframe { id: 1 }),
Item::new(ItemId::new(2), Keyframe { id: 2 }),
Item::new(ItemId::new(3), Keyframe { id: 3 }),
]),
ack,
))
.expect("the image tower is listening");
let indexed = crate::drive::invoke::tests::until(|| index.len() == 3);
assert!(indexed, "the indexing lane wrote its three entries");
drop(answers);
let hits = front
.invoke("two words".to_owned())
.expect("the text tower is listening")
.take_within(DEADLINE)
.expect("the chain answered");
assert_eq!(
hits,
vec![2, 1],
"nearest to the toy embedding of a 2-word query"
);
drop(front);
drop(images_out);
let tower_report = tower_run.join().expect("the image tower");
let writer_report = writer_run.join().expect("the index node");
let text_report = text_run.join().expect("the text tower");
let reader_report = reader_run.join().expect("the read arm");
assert_eq!(text_report.invokes(), 1);
assert_eq!(
text_report.passed(),
1,
"the text tower FORWARDED rather than answering"
);
assert_eq!(reader_report.invokes(), 1);
assert_eq!(
reader_report.passed(),
1,
"the read arm answered the caller"
);
assert_eq!(tower_report.deliveries(), 1);
assert_eq!(tower_report.items(), 3);
assert_eq!(writer_report.deliveries(), 1);
assert_eq!(writer_report.items(), 3);
assert_eq!(writer_report.tally().processed(), 3);
assert_eq!(writer_report.tally().failed(), 0);
assert_eq!(writer_report.tally().refused(), 0);
let rows = rows.lock().expect("the rows").clone();
assert_eq!(rows.len(), 3, "one completion per indexed root: {rows:?}");
let mut roots: Vec<u64> = rows.iter().map(|row| row.root).collect();
roots.sort_unstable();
assert_eq!(roots, [1, 2, 3]);
assert!(
rows
.iter()
.all(|row| row.node == "index" && row.station == Station::Persisted),
"{rows:?}"
);
assert!(
rows.iter().all(|row| row.station != Station::Processed),
"a query's own station never reaches the journal: {rows:?}"
);
}
#[test]
fn a_query_never_queues_behind_an_indexing_write_batch() {
let index = Index::default();
index.write(&[Entry {
key: 5,
vector: vec![5.0, 0.0],
}]);
let (entered, arrived) = flume::bounded::<()>(1);
let (release, held) = flume::bounded::<()>(1);
let (entries_out, entries_in) = channel::<ItemId, Entry>(8);
let (search_door, searches) = door::<Vector, Hits>(4);
let mut writer = Resident::new("index", Indexer, entries_in).land(IndexLane {
index: index.clone(),
latch: Some(Latch {
entered,
release: held,
}),
});
let mut reader = QueryArm::new(
"index",
VectorSearch {
index: index.clone(),
k: 1,
},
searches,
);
let writer_run = thread::Builder::new()
.name("index-write".to_owned())
.spawn(move || writer.run())
.expect("the write arm");
let reader_run = thread::Builder::new()
.name("index-read".to_owned())
.spawn(move || reader.run())
.expect("the read arm");
let (ack, answers) = ack_channel();
entries_out
.deliver(Delivery::new(
Payload::Batch(vec![
Item::new(
ItemId::new(0),
Entry {
key: 7,
vector: vec![7.0, 0.0],
},
),
Item::new(
ItemId::new(1),
Entry {
key: 8,
vector: vec![8.0, 0.0],
},
),
]),
ack,
))
.expect("the index node is listening");
arrived
.recv_timeout(DEADLINE)
.expect("the write batch entered the lane");
assert_eq!(index.len(), 1, "the parked batch has written nothing");
let hits = search_door
.invoke(vec![5.0, 0.0])
.expect("the read arm is listening")
.take_within(DEADLINE)
.expect("a query does not wait for a write batch");
assert_eq!(hits, vec![5]);
assert_eq!(index.len(), 1, "and the batch is STILL parked");
release.send(()).expect("the write arm is still there");
drop(entries_out);
drop(search_door);
let writer_report = writer_run.join().expect("the write arm");
let reader_report = reader_run.join().expect("the read arm");
drop(answers);
assert_eq!(index.len(), 3, "the batch landed once it was released");
assert_eq!(writer_report.items(), 2);
assert_eq!(reader_report.passed(), 1);
}
fn until(mut condition: impl FnMut() -> bool) -> bool {
let deadline = std::time::Instant::now() + DEADLINE;
while std::time::Instant::now() < deadline {
if condition() {
return true;
}
thread::yield_now();
}
condition()
}
#[test]
fn the_onward_destination_is_a_type_and_the_arm_body_is_one() {
use super::Onward;
let (answer, awaiting) = reply::<Hits>();
assert!(Onward::<Hits, Hits>::pass(&(), vec![1, 2], answer));
assert_eq!(awaiting.take().expect("answered"), vec![1, 2]);
let (next, invokes) = door::<Vector, Hits>(1);
let (answer, awaiting) = reply::<Hits>();
assert!(next.pass(vec![3.0], answer));
let forwarded = invokes.park().expect("queued");
assert_eq!(forwarded.input(), &vec![3.0]);
let (_, answer) = forwarded.into_parts();
answer.answer(vec![3]);
assert_eq!(awaiting.take().expect("answered"), vec![3]);
drop(invokes);
let (answer, awaiting) = reply::<Hits>();
assert!(!next.pass(vec![4.0], answer));
assert_eq!(awaiting.take().expect_err("gone"), QueryError::Dropped);
}
#[test]
fn a_failure_at_the_second_hop_reaches_the_first_hops_caller() {
let (front, queries) = door::<String, Hits>(4);
let (search_door, searches) = door::<Vector, Hits>(4);
let mut text = QueryArm::new("text", TextTower, queries).forwarding_to(search_door);
let awaiting = front.invoke("two words".to_owned()).expect("listening");
drop(front);
let served = text.run();
assert_eq!(served.passed(), 1, "the first hop did its part");
assert!(
awaiting
.take_within(Duration::from_millis(20))
.is_err_and(|error| error == QueryError::TimedOut),
"the query is queued at a hop that has not answered it"
);
drop(searches);
drop(text);
assert_eq!(
front_awaiting_again(),
QueryError::Dropped,
"a dead chain answers once, and it answers with this"
);
}
fn front_awaiting_again() -> QueryError {
let (front, queries) = door::<String, Hits>(4);
let (search_door, searches) = door::<Vector, Hits>(4);
let mut text = QueryArm::new("text", TextTower, queries).forwarding_to(search_door);
let awaiting = front.invoke("two words".to_owned()).expect("listening");
drop(front);
text.run();
drop(searches);
drop(text);
awaiting.take_within(DEADLINE).expect_err("nobody answered")
}