narju/
wire.rs

1use crate::floor::host::registry;
2use crate::floor::{rc_val, RcVal, Val};
3use std::collections::HashMap;
4
5const NIL: u8 = 0;
6const NUM: u8 = 1;
7const FLO: u8 = 2;
8const SYM: u8 = 3;
9const PAIR: u8 = 4;
10const ATOM: u8 = 5;
11/// A pair later bytes may refer back to; it takes the next position in the
12/// numbering, and a plain [`PAIR`] takes none.
13const PAIRX: u8 = 6;
14const REF: u8 = 7;
15
16/// A sender that framed something this end cannot read is a protocol
17/// disagreement, not a task's error, so it goes to whoever owns the link.
18#[derive(Debug, PartialEq)]
19pub enum Bad {
20    Short,
21    Tag(u8),
22    /// The fleet disagrees about what types exist, which is a deployment fact
23    /// rather than a corrupt frame.
24    Unknown(String),
25    /// The right tag and length, but the type's own decoder refused it.
26    Payload(String),
27    Utf8,
28    /// A reference to a pair never written, or one the frame has not finished
29    /// writing. A sender walking an acyclic graph cannot emit either.
30    Ref(usize),
31    Trailing,
32}
33
34fn put_len(out: &mut Vec<u8>, n: usize) {
35    out.extend_from_slice(&(n as u32).to_be_bytes());
36}
37
38/// `None` for anything that is not data, which is the same judgement `send`
39/// makes at the primitive - so a closure reaching here is a bug above.
40pub fn encode(v: &Val) -> Option<Vec<u8>> {
41    let mut out = Vec::new();
42    // Cdr before car, so the car is written first: the order `decode` rebuilds in.
43    let mut work = vec![rc_val(v.clone())];
44    // Pointer identity is the sharing, so every key is held alive alongside -
45    // an address only names a node for as long as the node is there.
46    let mut seen: HashMap<*const Val, u32> = HashMap::new();
47    let mut alive: Vec<RcVal> = Vec::new();
48
49    while let Some(rv) = work.pop() {
50        if let Val::Pair(a, b) = &*rv {
51            // A pair at two handles is held by one parent and by this walk, so
52            // it cannot come round again and need not be remembered. The count
53            // means parents-plus-one only because `v` is borrowed: a walk that
54            // owned the graph would consume handles as it went and read sharing
55            // still ahead of it as sharing that is not there.
56            if rv.refs() > 2 {
57                let at = &*rv as *const Val;
58                if let Some(&already) = seen.get(&at) {
59                    out.push(REF);
60                    put_len(&mut out, already as usize);
61                    continue;
62                }
63                let id = seen.len() as u32;
64                seen.insert(at, id);
65                alive.push(RcVal::clone(&rv));
66                out.push(PAIRX);
67            } else {
68                out.push(PAIR);
69            }
70            work.push(RcVal::clone(b));
71            work.push(RcVal::clone(a));
72            continue;
73        }
74        match Val::clone(&rv) {
75            Val::Nil => out.push(NIL),
76            Val::Num(n) => {
77                out.push(NUM);
78                out.extend_from_slice(&n.to_be_bytes());
79            }
80            Val::Flo(x) => {
81                out.push(FLO);
82                out.extend_from_slice(&x.to_bits().to_be_bytes());
83            }
84            Val::Sym(s) => {
85                out.push(SYM);
86                put_len(&mut out, s.len());
87                out.extend_from_slice(s.as_bytes());
88            }
89            Val::Pair(_, _) => unreachable!("handled above"),
90            Val::Atom(a) => {
91                out.push(ATOM);
92                let name = a.type_name();
93                put_len(&mut out, name.len());
94                out.extend_from_slice(name.as_bytes());
95                // Length-prefixed after the fact: a type's encoding is opaque
96                // here, so its size is not known until it has run.
97                let at = out.len();
98                out.extend_from_slice(&[0; 4]);
99                a.0.encode(&mut out);
100                let n = out.len() - at - 4;
101                out[at..at + 4].copy_from_slice(&(n as u32).to_be_bytes());
102            }
103            Val::Clo(_, _) | Val::Code(_) | Val::Cell(_) | Val::Raise(_) => return None,
104        }
105    }
106    Some(out)
107}
108
109struct Cursor<'a> {
110    b: &'a [u8],
111    at: usize,
112}
113
114impl<'a> Cursor<'a> {
115    fn take(&mut self, n: usize) -> Result<&'a [u8], Bad> {
116        let end = self.at.checked_add(n).ok_or(Bad::Short)?;
117        let s = self.b.get(self.at..end).ok_or(Bad::Short)?;
118        self.at = end;
119        Ok(s)
120    }
121
122    fn byte(&mut self) -> Result<u8, Bad> {
123        Ok(self.take(1)?[0])
124    }
125
126    fn u32(&mut self) -> Result<usize, Bad> {
127        let b: [u8; 4] = self.take(4)?.try_into().expect("four bytes");
128        Ok(u32::from_be_bytes(b) as usize)
129    }
130
131    fn u64(&mut self) -> Result<[u8; 8], Bad> {
132        Ok(self.take(8)?.try_into().expect("eight bytes"))
133    }
134
135    fn text(&mut self) -> Result<&'a str, Bad> {
136        let n = self.u32()?;
137        std::str::from_utf8(self.take(n)?).map_err(|_| Bad::Utf8)
138    }
139}
140
141/// What is still owed to a pair being rebuilt, and the position it was written
142/// at, which is the name a later back-reference uses.
143enum Need {
144    Car(Option<usize>),
145    Cdr(Option<usize>, RcVal),
146}
147
148/// Which must be the whole of `bytes`. Carried as [`RcVal`] so a back-reference
149/// rebuilds the sharing rather than a copy: a frame naming the same pair a
150/// thousand times decodes to one pair.
151pub fn decode(bytes: &[u8]) -> Result<Val, Bad> {
152    let mut c = Cursor { b: bytes, at: 0 };
153    let mut stack: Vec<Need> = Vec::new();
154    // A slot is `None` for exactly as long as the pair it names is still being
155    // read, which makes a reference into an unfinished pair - the one shape a
156    // cycle would need - reportable.
157    let mut built: Vec<Option<RcVal>> = Vec::new();
158
159    let v = 'build: loop {
160        let mut v = match c.byte()? {
161            NIL => rc_val(Val::Nil),
162            NUM => rc_val(Val::Num(i64::from_be_bytes(c.u64()?))),
163            FLO => rc_val(Val::Flo(f64::from_bits(u64::from_be_bytes(c.u64()?)))),
164            SYM => rc_val(Val::Sym(c.text()?.into())),
165            ATOM => {
166                let name = c.text()?.to_string();
167                let n = c.u32()?;
168                let body = c.take(n)?;
169                let d = registry()
170                    .decoder(&name)
171                    .ok_or(Bad::Unknown(name.clone()))?;
172                rc_val(Val::Atom(d(body).ok_or(Bad::Payload(name))?))
173            }
174            PAIR => {
175                stack.push(Need::Car(None));
176                continue;
177            }
178            PAIRX => {
179                built.push(None);
180                stack.push(Need::Car(Some(built.len() - 1)));
181                continue;
182            }
183            REF => {
184                let id = c.u32()?;
185                match built.get(id).and_then(|s| s.as_ref()) {
186                    Some(v) => RcVal::clone(v),
187                    None => return Err(Bad::Ref(id)),
188                }
189            }
190            other => return Err(Bad::Tag(other)),
191        };
192        loop {
193            match stack.pop() {
194                None => break 'build v,
195                Some(Need::Car(id)) => {
196                    stack.push(Need::Cdr(id, v));
197                    continue 'build;
198                }
199                Some(Need::Cdr(id, car)) => {
200                    v = rc_val(Val::Pair(car, v));
201                    if let Some(id) = id {
202                        built[id] = Some(RcVal::clone(&v));
203                    }
204                }
205            }
206        }
207    };
208
209    if c.at == bytes.len() {
210        Ok(Val::clone(&v))
211    } else {
212        Err(Bad::Trailing)
213    }
214}
215
216#[cfg(test)]
217mod tests {
218    use super::*;
219    use crate::floor::host::Str;
220    use crate::floor::{list, pair};
221
222    fn sym(s: &str) -> Val {
223        Val::Sym(s.into())
224    }
225
226    fn round(v: Val) {
227        let bytes = encode(&v).expect("data");
228        assert_eq!(decode(&bytes), Ok(v));
229    }
230
231    #[test]
232    fn the_shapes_a_printer_could_not_carry() {
233        round(Val::Nil);
234        round(sym("hi"));
235        round(list(&[sym("a"), sym("b")]));
236        round(pair(Val::Num(1), sym("b")));
237        round(list(&[sym("req"), sym("hi")]));
238    }
239
240    #[test]
241    fn printing_and_reading_is_not_a_round_trip() {
242        let back = |v: &Val| {
243            let forms = crate::floor::read::read(&format!("{v}")).expect("reads");
244            assert_eq!(forms.len(), 1);
245            Val::clone(&forms[0])
246        };
247        for v in [sym("hi"), list(&[sym("a")]), pair(Val::Num(1), sym("b"))] {
248            assert_ne!(back(&v), v, "{v}");
249        }
250        // A number is not a counterexample, and neither is a bare list.
251        assert_eq!(back(&Val::Num(42)), Val::Num(42));
252        assert_eq!(
253            back(&list(&[Val::Num(1), Val::Num(2)])),
254            list(&[Val::Num(1), Val::Num(2)])
255        );
256    }
257
258    #[test]
259    fn an_address_is_carried_as_written() {
260        use crate::sched::{addr, Addr};
261        round(addr(0));
262        round(addr(3));
263        round(Addr::Remote(2, 5).val());
264        round(list(&[sym("req"), addr(1), Val::Num(9), sym("ping")]));
265    }
266
267    #[test]
268    fn scalars_survive() {
269        round(Val::Num(0));
270        round(Val::Num(-7));
271        round(Val::Num(i64::MIN));
272        round(Val::Num(i64::MAX));
273        round(Val::Flo(1.5));
274        round(Val::Flo(-0.0));
275        round(Val::Flo(f64::INFINITY));
276    }
277
278    #[test]
279    fn a_host_atom_travels_as_its_type_name_and_bytes() {
280        round(Str::val("hello"));
281        round(Str::val(""));
282        round(Str::val("a\nb\"c"));
283        round(list(&[sym("read"), Str::val("arith.naj")]));
284    }
285
286    #[test]
287    fn a_value_that_is_not_data_has_no_encoding() {
288        assert_eq!(encode(&Val::Cell(0)), None);
289        assert_eq!(encode(&pair(Val::Num(1), Val::Cell(0))), None);
290        assert_eq!(encode(&Val::Raise(rc_val(sym("boom")))), None);
291    }
292
293    #[test]
294    fn a_long_list_costs_no_stack() {
295        let deep = (0..10_000).fold(Val::Nil, |t, i| pair(Val::Num(i), t));
296        round(deep);
297    }
298
299    #[test]
300    fn a_deep_car_chain_costs_no_stack() {
301        let deep = (0..10_000).fold(Val::Nil, |t, _| pair(t, Val::Nil));
302        round(deep);
303    }
304
305    #[test]
306    fn sharing_is_carried_rather_than_unfolded() {
307        let mut v = Val::Num(1);
308        for _ in 0..20 {
309            let rc = rc_val(v);
310            v = Val::Pair(RcVal::clone(&rc), rc);
311        }
312        let bytes = encode(&v).expect("data");
313        // A tag per pair, a back-reference for every cdr but the
314        // innermost, and the leaf twice - a scalar is not shared, because
315        // it has no children to amplify.
316        assert_eq!(bytes.len(), 20 + 19 * 5 + 2 * 9);
317        round(v);
318    }
319
320    #[test]
321    fn a_node_two_parents_apart_is_still_recognised() {
322        let x = rc_val(pair(sym("x"), Val::Nil));
323        let a = rc_val(Val::Pair(RcVal::clone(&x), rc_val(Val::Nil)));
324        let b = rc_val(Val::Pair(RcVal::clone(&x), rc_val(Val::Nil)));
325        let r = Val::Pair(a, b);
326        let bytes = encode(&r).expect("data");
327        // Four pairs written, one back-reference, and `x` once.
328        assert_eq!(
329            bytes.iter().filter(|&&t| t == PAIR || t == PAIRX).count(),
330            4
331        );
332        assert_eq!(bytes.iter().filter(|&&t| t == REF).count(), 1);
333        round(r);
334    }
335
336    #[test]
337    fn a_decoded_graph_shares_what_the_sender_shared() {
338        let mut v = Val::Num(1);
339        for _ in 0..20 {
340            let rc = rc_val(v);
341            v = Val::Pair(RcVal::clone(&rc), rc);
342        }
343        let back = decode(&encode(&v).expect("data")).expect("decodes");
344        let Val::Pair(a, b) = &back else {
345            panic!("expected a pair");
346        };
347        assert!(std::ptr::eq(&**a as *const Val, &**b as *const Val));
348        assert_eq!(encode(&back).map(|b| b.len()), encode(&v).map(|b| b.len()));
349    }
350
351    #[test]
352    fn a_frame_that_is_not_one_is_reported_rather_than_panicking() {
353        assert_eq!(decode(&[]), Err(Bad::Short));
354        assert_eq!(decode(&[NUM, 0, 0]), Err(Bad::Short));
355        assert_eq!(decode(&[99]), Err(Bad::Tag(99)));
356        assert_eq!(decode(&[PAIR, NIL]), Err(Bad::Short));
357        // One complete value and then some.
358        assert_eq!(decode(&[NIL, NIL]), Err(Bad::Trailing));
359        // A type nothing here can build.
360        let mut b = vec![ATOM];
361        b.extend_from_slice(&3u32.to_be_bytes());
362        b.extend_from_slice(b"zzz");
363        b.extend_from_slice(&0u32.to_be_bytes());
364        assert_eq!(decode(&b), Err(Bad::Unknown("zzz".to_string())));
365    }
366
367    #[test]
368    fn a_back_reference_that_names_nothing_is_reported() {
369        let r = |id: u32| {
370            let mut b = vec![REF];
371            b.extend_from_slice(&id.to_be_bytes());
372            b
373        };
374        assert_eq!(decode(&r(0)), Err(Bad::Ref(0)));
375        assert_eq!(decode(&r(7)), Err(Bad::Ref(7)));
376        // `(cons <itself> nil)`: position 0 is open until its cdr lands.
377        let mut b = vec![PAIRX];
378        b.extend_from_slice(&r(0));
379        b.push(NIL);
380        assert_eq!(decode(&b), Err(Bad::Ref(0)));
381        // A plain pair takes no position, so naming one is naming nothing.
382        let mut b = vec![PAIR, PAIR, NIL, NIL];
383        b.extend_from_slice(&r(1));
384        assert_eq!(decode(&b), Err(Bad::Ref(1)));
385        // Whereas the completed numbered pair may be named afterwards.
386        let mut b = vec![PAIRX, PAIRX, NIL, NIL];
387        b.extend_from_slice(&r(1));
388        assert_eq!(
389            decode(&b),
390            Ok(pair(pair(Val::Nil, Val::Nil), pair(Val::Nil, Val::Nil)))
391        );
392    }
393}
narju/wire.rs

narju/
wire.rs
