tobogganSe connecter

louise

The Louise language: compiler, runtime, std, tooling

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

1146 lignes · 29120 octetsBrut · Historique
1/// MessagePack encoding and decoding (issue gabla108/louise#140; `@derive(MsgPack)` is
2/// ADR 0051).
3///
4/// msgpack.write(Str("hi")) // the Bytes a2 68 69
5/// msgpack.read(data) // Result<Value, DecodeError>
6/// msgpack.encode([1, 2, 3]) // Bytes, through ToMsgPack
7/// msgpack.decode(data) // Result<a, DecodeError>, through FromMsgPack
8///
9/// `write` uses the smallest encoding of each integer and length, big-
10/// endian, as the specification asks of encoders. `read` is a parser of
11/// untrusted input (request bodies): a length prefix is checked against
12/// the bytes left before anything is taken, nesting is bounded (see
13/// [`max_depth`]), `str` payloads are checked as UTF-8 (ADR 0012), and a
14/// `float 32` is widened to a `Float`.
15///
16/// An `Int` is MessagePack's uint64 or int64; writing one outside that
17/// range panics (Louise's `Int` promotes to a big integer, ADR 0014, but
18/// the wire has no bigger integer — an `Ext` bignum is ADR 0051's
19/// decision). Reading a uint64 above 2^62 gives a big integer, as it
20/// should. An `Ext` tag is a signed 8-bit integer; writing any other tag
21/// panics.
22///
23/// The codec is pure Louise over `Bytes`, so both backends run it. If a
24/// benchmark shows it hot, a kernel in `louise_rt_prims` is ADR 0051's
25/// question, not a new extern's.
26
27import std/array.{type Array}
28import std/bytes
29import std/dict.{type Dict}
30import std/float
31import std/int
32import std/list
33import std/result
34
35/// A MessagePack value.
36@derive Eq Debug
37pub type Value
38{ Nil
39, Bool(Bool)
40, Int(Int)
41, Float(Float)
42, Str(String)
43, Bin(Bytes)
44, Array(List<Value>)
45, Map(List<(Value, Value)>)
46 /// An extension: MessagePack's "extension type" (`tag`, signed 8 bits)
47 /// and its payload.
48, Ext(tag: Int, data: Bytes)
49}
50
51/// Why [`read`] or [`from_msgpack`](FromMsgPack) failed.
52@derive Eq Debug
53pub type DecodeError
54{ /// The bytes are not a MessagePack value; `at` is the byte offset.
55 Malformed(at: Int, message: String)
56 /// The bytes decoded, but the value is not the one the type expected.
57, Mismatch(expected: String, found: String)
58}
59
60impl Show<DecodeError>
61{
62 fn show :: e
63 {
64 match e
65 { Malformed(at, message) -> "invalid MessagePack at byte {at}: {message}"
66 , Mismatch
67 (expected, found) -> "MessagePack: expected {expected}, found {found}"
68 }
69 }
70}
71
72/// The most nesting [`read`] accepts (arrays and maps; 512). Deeper
73/// input is an error, so a hostile body cannot overflow the stack.
74pub fn max_depth :: -> Int
75{
76 512
77}
78
79// ---- encoding ------------------------------------------------------------------
80
81/// `value` as MessagePack bytes (the smallest encoding of each integer
82/// and length). Panics on an `Int` outside the uint64/int64 range and on
83/// an `Ext` tag outside -128 to 127.
84pub fn write :: value: Value -> Bytes
85{
86 bytes.build (write_value (bytes.builder ()) value)
87}
88
89fn write_value :: b: bytes.Builder value: Value -> bytes.Builder
90{
91 match value
92 { Nil -> bytes.append_byte b 192
93 , Bool(False) -> bytes.append_byte b 194
94 , Bool(True) -> bytes.append_byte b 195
95 , Int(n) -> write_int b n
96 , Float(x) -> be64 (bytes.append_byte b 203) (float.to_bits x)
97 , Str(s) -> write_str b s
98 , Bin(data) -> write_bin b data
99 , Array(items) ->
100 {
101 let b = write_array_header b (list.length items)
102 list.fold items b write_value
103 }
104 , Map(entries) ->
105 {
106 let b = write_map_header b (list.length entries)
107 list.fold entries b write_entry
108 }
109 , Ext(tag, data) -> write_ext b tag data
110 }
111}
112
113fn write_entry :: b: bytes.Builder entry: (Value, Value) -> bytes.Builder
114{
115 write_value (write_value b entry.0) entry.1
116}
117
118/// The smallest encoding of `n`: positive fixint, then uint 8/16/32/64;
119/// negative fixint, then int 8/16/32/64.
120fn write_int :: b: bytes.Builder n: Int -> bytes.Builder
121{
122 if n >= 0
123 {
124 if n < 128
125 {
126 bytes.append_byte b n
127 }
128 else if n < 256
129 {
130 bytes.append_byte (bytes.append_byte b 204) n
131 }
132 else if n < 65536
133 {
134 be16 (bytes.append_byte b 205) n
135 }
136 else if n < 4294967296
137 {
138 be32 (bytes.append_byte b 206) n
139 }
140 else if int.bit_length n <= 64
141 {
142 be64 (bytes.append_byte b 207) n
143 }
144 else
145 {
146 panic "msgpack: an Int above 2^64 - 1 has no MessagePack encoding: {n}"
147 }
148 }
149 else if n >= -32
150 {
151 bytes.append_byte b (n + 256)
152 }
153 else if n >= -128
154 {
155 bytes.append_byte (bytes.append_byte b 208) (n + 256)
156 }
157 else if n >= -32768
158 {
159 be16 (bytes.append_byte b 209) n
160 }
161 else if n >= -2147483648
162 {
163 be32 (bytes.append_byte b 210) n
164 }
165 else
166 {
167 // -2^63 itself: its magnitude is 2^63, so a bit length cannot tell
168 // it from -2^63 - 1; compare against the computed bound.
169 let i64_min = 0 - int.shift_left 1 63
170 if n >= i64_min
171 {
172 be64 (bytes.append_byte b 211) n
173 }
174 else
175 {
176 panic "msgpack: an Int below -2^63 has no MessagePack encoding: {n}"
177 }
178 }
179}
180
181fn write_str :: b: bytes.Builder s: String -> bytes.Builder
182{
183 let data = bytes.from_string s
184 let b = write_str_header b (bytes.length data)
185 bytes.append b data
186}
187
188fn write_str_header :: b: bytes.Builder len: Int -> bytes.Builder
189{
190 if len < 32
191 {
192 bytes.append_byte b (160 + len)
193 }
194 else if len < 256
195 {
196 bytes.append_byte (bytes.append_byte b 217) len
197 }
198 else if len < 65536
199 {
200 be16 (bytes.append_byte b 218) len
201 }
202 else
203 {
204 be32 (bytes.append_byte b 219) (check_len len)
205 }
206}
207
208fn write_bin :: b: bytes.Builder data: Bytes -> bytes.Builder
209{
210 let len = bytes.length data
211 let b = if len < 256
212 {
213 bytes.append_byte (bytes.append_byte b 196) len
214 }
215 else if len < 65536
216 {
217 be16 (bytes.append_byte b 197) len
218 }
219 else
220 {
221 be32 (bytes.append_byte b 198) (check_len len)
222 }
223 bytes.append b data
224}
225
226fn write_array_header :: b: bytes.Builder len: Int -> bytes.Builder
227{
228 if len < 16
229 {
230 bytes.append_byte b (144 + len)
231 }
232 else if len < 65536
233 {
234 be16 (bytes.append_byte b 220) len
235 }
236 else
237 {
238 be32 (bytes.append_byte b 221) (check_len len)
239 }
240}
241
242fn write_map_header :: b: bytes.Builder len: Int -> bytes.Builder
243{
244 if len < 16
245 {
246 bytes.append_byte b (128 + len)
247 }
248 else if len < 65536
249 {
250 be16 (bytes.append_byte b 222) len
251 }
252 else
253 {
254 be32 (bytes.append_byte b 223) (check_len len)
255 }
256}
257
258fn write_ext :: b: bytes.Builder tag: Int data: Bytes -> bytes.Builder
259{
260 if tag < -128 || tag > 127
261 {
262 panic "msgpack: an Ext tag is a signed 8-bit integer, got {tag}"
263 }
264 else
265 {
266 let len = bytes.length data
267 let b = match len
268 { 1 -> bytes.append_byte b 212
269 , 2 -> bytes.append_byte b 213
270 , 4 -> bytes.append_byte b 214
271 , 8 -> bytes.append_byte b 215
272 , 16 -> bytes.append_byte b 216
273 , _ if len < 256 -> bytes.append_byte (bytes.append_byte b 199) len
274 , _ if len < 65536 -> be16 (bytes.append_byte b 200) len
275 , _ -> be32 (bytes.append_byte b 201) (check_len len)
276 }
277 let b = bytes.append_byte b (int.low_bits tag 8)
278 bytes.append b data
279 }
280}
281
282/// Lengths are 32 bits on the wire; more cannot be written.
283fn check_len :: len: Int -> Int
284{
285 if len >= 4294967296
286 {
287 panic "msgpack: more than 2^32 - 1 items or bytes cannot be written"
288 }
289 else
290 {
291 len
292 }
293}
294
295/// `n` as 2 big-endian bytes (its low 16 bits, two's complement).
296fn be16 :: b: bytes.Builder n: Int -> bytes.Builder
297{
298 let n = int.low_bits n 16
299 let b = bytes.append_byte b (int.and (int.shift_right n 8) 255)
300 bytes.append_byte b (int.and n 255)
301}
302
303/// `n` as 4 big-endian bytes (its low 32 bits).
304fn be32 :: b: bytes.Builder n: Int -> bytes.Builder
305{
306 let n = int.low_bits n 32
307 let b = bytes.append_byte b (int.and (int.shift_right n 24) 255)
308 let b = bytes.append_byte b (int.and (int.shift_right n 16) 255)
309 let b = bytes.append_byte b (int.and (int.shift_right n 8) 255)
310 bytes.append_byte b (int.and n 255)
311}
312
313/// `n` as 8 big-endian bytes (its low 64 bits).
314fn be64 :: b: bytes.Builder n: Int -> bytes.Builder
315{
316 let n = int.low_bits n 64
317 let b = bytes.append_byte b (int.and (int.shift_right n 56) 255)
318 let b = bytes.append_byte b (int.and (int.shift_right n 48) 255)
319 let b = bytes.append_byte b (int.and (int.shift_right n 40) 255)
320 let b = bytes.append_byte b (int.and (int.shift_right n 32) 255)
321 let b = bytes.append_byte b (int.and (int.shift_right n 24) 255)
322 let b = bytes.append_byte b (int.and (int.shift_right n 16) 255)
323 let b = bytes.append_byte b (int.and (int.shift_right n 8) 255)
324 bytes.append_byte b (int.and n 255)
325}
326
327// ---- decoding ------------------------------------------------------------------
328
329/// A cursor over the input.
330type Cursor { Cursor(bytes: Bytes, at: Int) }
331
332/// The first MessagePack value in `data`. Bytes after it are an error.
333pub fn read :: data: Bytes -> Result<Value, DecodeError>
334{
335 use (value, cur) <- result.try (read_value Cursor(data, 0) 0)
336 if cur.at == bytes.length data
337 {
338 Ok(value)
339 }
340 else
341 {
342 Error( Malformed( cur.at
343 , "{bytes.length data - cur.at} bytes after the value"
344 )
345 )
346 }
347}
348
349fn read_value :: cur: Cursor depth: Int -> Result<(Value, Cursor), DecodeError>
350{
351 if depth > max_depth ()
352 {
353 Error(Malformed(cur.at, "nesting deeper than {max_depth ()} levels"))
354 }
355 else
356 {
357 use (byte, cur) <- result.try (read_byte cur)
358 if byte < 128
359 {
360 Ok((Int(byte), cur))
361 }
362 else if byte >= 224
363 {
364 Ok((Int(byte - 256), cur))
365 }
366 else if byte < 144
367 {
368 read_map cur (byte - 128) depth
369 }
370 else if byte < 160
371 {
372 read_array cur (byte - 144) depth
373 }
374 else if byte < 192
375 {
376 read_str cur (byte - 160)
377 }
378 else
379 {
380 match byte
381 { 192 -> Ok((Nil, cur))
382 , 193 -> Error(Malformed(cur.at - 1, "0xc1 is not a MessagePack byte"))
383 , 194 -> Ok((Bool(False), cur))
384 , 195 -> Ok((Bool(True), cur))
385 , 196 -> read_bin_len cur 1
386 , 197 -> read_bin_len cur 2
387 , 198 -> read_bin_len cur 4
388 , 199 -> read_ext_len cur 1
389 , 200 -> read_ext_len cur 2
390 , 201 -> read_ext_len cur 4
391 , 202 -> read_float cur 4
392 , 203 -> read_float cur 8
393 , 204 -> read_uint_value cur 1
394 , 205 -> read_uint_value cur 2
395 , 206 -> read_uint_value cur 4
396 , 207 -> read_uint_value cur 8
397 , 208 -> read_int_value cur 1
398 , 209 -> read_int_value cur 2
399 , 210 -> read_int_value cur 4
400 , 211 -> read_int_value cur 8
401 , 212 -> read_ext cur 1
402 , 213 -> read_ext cur 2
403 , 214 -> read_ext cur 4
404 , 215 -> read_ext cur 8
405 , 216 -> read_ext cur 16
406 , 217 -> read_str_len cur 1
407 , 218 -> read_str_len cur 2
408 , 219 -> read_str_len cur 4
409 , 220 -> read_array_len cur 2 depth
410 , 221 -> read_array_len cur 4 depth
411 , 222 -> read_map_len cur 2 depth
412 , 223 -> read_map_len cur 4 depth
413 // Unreachable: the arms above cover 192 to 223.
414 , _ ->
415 Error(Malformed(cur.at - 1, "a byte the codec does not know: {byte}"))
416 }
417 }
418 }
419}
420
421fn read_uint_value ::
422 cur: Cursor
423 width: Int
424 -> Result<(Value, Cursor), DecodeError>
425{
426 use (n, cur) <- result.try (read_uint cur width)
427 Ok((Int(n), cur))
428}
429
430fn read_int_value ::
431 cur: Cursor
432 width: Int
433 -> Result<(Value, Cursor), DecodeError>
434{
435 use (n, cur) <- result.try (read_uint cur width)
436 Ok((Int(signed n (width * 8)), cur))
437}
438
439/// `n` (unsigned, `bits` wide) as signed: two's complement.
440fn signed :: n: Int bits: Int -> Int
441{
442 let sign = int.shift_left 1 (bits - 1)
443 if int.and n sign == 0
444 {
445 n
446 }
447 else
448 {
449 n - int.shift_left sign 1
450 }
451}
452
453/// A float 32 (`width` 4) is widened; a float 64 (`width` 8) is exact.
454fn read_float :: cur: Cursor width: Int -> Result<(Value, Cursor), DecodeError>
455{
456 use (bits, cur) <- result.try (read_uint cur width)
457 let x = if width == 4 { float.from_bits32 bits } else { float.from_bits bits }
458 Ok((Float(x), cur))
459}
460
461fn read_str_len ::
462 cur: Cursor
463 width: Int
464 -> Result<(Value, Cursor), DecodeError>
465{
466 use (len, cur) <- result.try (read_uint cur width)
467 read_str cur len
468}
469
470fn read_str :: cur: Cursor len: Int -> Result<(Value, Cursor), DecodeError>
471{
472 let left = bytes.length cur.bytes - cur.at
473 if len < 0 || len > left
474 {
475 Error(Malformed(cur.at, "a length of {len} with {left} bytes left"))
476 }
477 else
478 {
479 match bytes.to_string_range cur.bytes cur.at len
480 { Ok(s) -> Ok((Str(s), Cursor(cur.bytes, cur.at + len)))
481 , Error(e) -> Error(Malformed(cur.at, "a str that is not UTF-8: {e}"))
482 }
483 }
484}
485
486fn read_bin_len ::
487 cur: Cursor
488 width: Int
489 -> Result<(Value, Cursor), DecodeError>
490{
491 use (len, cur) <- result.try (read_uint cur width)
492 use (data, cur) <- result.try (take cur len)
493 Ok((Bin(data), cur))
494}
495
496fn read_ext_len ::
497 cur: Cursor
498 width: Int
499 -> Result<(Value, Cursor), DecodeError>
500{
501 use (len, cur) <- result.try (read_uint cur width)
502 read_ext cur len
503}
504
505fn read_ext :: cur: Cursor len: Int -> Result<(Value, Cursor), DecodeError>
506{
507 use (byte, cur) <- result.try (read_byte cur)
508 let tag = if byte >= 128 { byte - 256 } else { byte }
509 use (data, cur) <- result.try (take cur len)
510 Ok((Ext(tag, data), cur))
511}
512
513fn read_array_len ::
514 cur: Cursor
515 width: Int
516 depth: Int
517 -> Result<(Value, Cursor), DecodeError>
518{
519 use (count, cur) <- result.try (read_uint cur width)
520 read_array cur count depth
521}
522
523fn read_array ::
524 cur: Cursor
525 count: Int
526 depth: Int
527 -> Result<(Value, Cursor), DecodeError>
528{
529 use _ <- result.try (check_count cur count "an array")
530 read_items cur count depth []
531}
532
533fn read_items ::
534 cur: Cursor
535 count: Int
536 depth: Int
537 acc: List<Value>
538 -> Result<(Value, Cursor), DecodeError>
539{
540 if count == 0
541 {
542 Ok((Array(list.reverse acc), cur))
543 }
544 else
545 {
546 use (item, cur) <- result.try (read_value cur (depth + 1))
547 read_items cur (count - 1) depth [item, ..acc]
548 }
549}
550
551fn read_map_len ::
552 cur: Cursor
553 width: Int
554 depth: Int
555 -> Result<(Value, Cursor), DecodeError>
556{
557 use (count, cur) <- result.try (read_uint cur width)
558 read_map cur count depth
559}
560
561fn read_map ::
562 cur: Cursor
563 count: Int
564 depth: Int
565 -> Result<(Value, Cursor), DecodeError>
566{
567 use _ <- result.try (check_count cur count "a map")
568 read_entries cur count depth []
569}
570
571fn read_entries ::
572 cur: Cursor
573 count: Int
574 depth: Int
575 acc: List<(Value, Value)>
576 -> Result<(Value, Cursor), DecodeError>
577{
578 if count == 0
579 {
580 Ok((Map(list.reverse acc), cur))
581 }
582 else
583 {
584 use (key, cur) <- result.try (read_value cur (depth + 1))
585 use (value, cur) <- result.try (read_value cur (depth + 1))
586 read_entries cur (count - 1) depth [(key, value), ..acc]
587 }
588}
589
590/// A length prefix is checked against the bytes left before anything is
591/// read: each item takes at least one byte, so more items than bytes can
592/// never be there.
593fn check_count :: cur: Cursor count: Int what: String -> Result<(), DecodeError>
594{
595 let left = bytes.length cur.bytes - cur.at
596 if count > left
597 {
598 Error(Malformed(cur.at, "{what} of {count} items with {left} bytes left"))
599 }
600 else
601 {
602 Ok(())
603 }
604}
605
606fn read_byte :: cur: Cursor -> Result<(Int, Cursor), DecodeError>
607{
608 let byte = bytes.read_u8 cur.bytes cur.at
609 if byte < 0
610 {
611 Error(Malformed(cur.at, "the input ends early"))
612 }
613 else
614 {
615 Ok((byte, Cursor(cur.bytes, cur.at + 1)))
616 }
617}
618
619/// The unsigned big-endian integer of the next `width` bytes (1, 2, 4 or
620/// 8; 8 can be a big integer, above 2^62), read in place.
621fn read_uint :: cur: Cursor width: Int -> Result<(Int, Cursor), DecodeError>
622{
623 let left = bytes.length cur.bytes - cur.at
624 if width > left
625 {
626 Error(Malformed(cur.at, "a length of {width} with {left} bytes left"))
627 }
628 else
629 {
630 let n = match width
631 { 1 -> bytes.read_u8 cur.bytes cur.at
632 , 2 -> bytes.read_u16be cur.bytes cur.at
633 , 4 -> bytes.read_u32be cur.bytes cur.at
634 , _ -> bytes.read_u64be cur.bytes cur.at
635 }
636 if n < 0
637 {
638 // Unreachable: the bounds were checked above.
639 Error(Malformed(cur.at, "a length of {width} with {left} bytes left"))
640 }
641 else
642 {
643 Ok((n, Cursor(cur.bytes, cur.at + width)))
644 }
645 }
646}
647
648/// The next `n` bytes, if they are all there.
649fn take :: cur: Cursor n: Int -> Result<(Bytes, Cursor), DecodeError>
650{
651 let left = bytes.length cur.bytes - cur.at
652 if n < 0 || n > left
653 {
654 Error(Malformed(cur.at, "a length of {n} with {left} bytes left"))
655 }
656 else
657 {
658 Ok( ( bytes.slice cur.bytes cur.at (cur.at + n)
659 , Cursor(cur.bytes, cur.at + n)
660 )
661 )
662 }
663}
664
665// ---- the traits -----------------------------------------------------------------
666
667/// Encoding to MessagePack (ADR 0051). `@derive(ToMsgPack)` writes a
668/// record as a map keyed by field label, a positional constructor as a
669/// map from its name to its fields' array, and a constructor without
670/// fields as its name.
671@derivable to_msgpack_of_constructor
672pub trait ToMsgPack<a>
673{
674 fn to_msgpack :: x: a -> Value
675}
676
677/// The derive function of [`ToMsgPack`] (ADR 0019).
678fn to_msgpack_of_constructor :: c: Constructor<Value> -> Value
679{
680 match c.fields
681 { [] -> Str(c.name)
682 , [f, ..] if f.label != "" ->
683 Map(list.map c.fields fn f { (Str(f.label), f.value) })
684 , fields -> Map([(Str(c.name), Array(list.map fields fn f { f.value }))])
685 }
686}
687
688/// Decoding from MessagePack (ADR 0051). Hand-written until the ADR
689/// lands: ADR 0019's derives consume a value, they do not produce one.
690pub trait FromMsgPack<a>
691{
692 fn from_msgpack :: v: Value -> Result<a, DecodeError>
693}
694
695/// `x` as MessagePack bytes: [`write`] of [`to_msgpack`](ToMsgPack).
696pub fn encode :: x: a -> Bytes where ToMsgPack<a>
697{
698 write (to_msgpack x)
699}
700
701/// The `a` encoded in `data`: [`read`], then [`from_msgpack`](FromMsgPack).
702pub fn decode :: data: Bytes -> Result<a, DecodeError> where FromMsgPack<a>
703{
704 use value <- result.try (read data)
705 from_msgpack value
706}
707
708/// What a `Value` is, for error messages ("an Int", "a Map").
709pub fn kind :: v: Value -> String
710{
711 match v
712 { Nil -> "nil"
713 , Bool(_) -> "a Bool"
714 , Int(_) -> "an Int"
715 , Float(_) -> "a Float"
716 , Str(_) -> "a Str"
717 , Bin(_) -> "a Bin"
718 , Array(_) -> "an Array"
719 , Map(_) -> "a Map"
720 , Ext(_, _) -> "an Ext"
721 }
722}
723
724impl ToMsgPack<Int>
725{
726 fn to_msgpack :: n
727 {
728 Int(n)
729 }
730}
731
732impl FromMsgPack<Int>
733{
734 fn from_msgpack :: v
735 {
736 match v { Int(n) -> Ok(n), _ -> Error(Mismatch("an Int", kind v)) }
737 }
738}
739
740impl ToMsgPack<Float>
741{
742 fn to_msgpack :: x
743 {
744 Float(x)
745 }
746}
747
748impl FromMsgPack<Float>
749{
750 fn from_msgpack :: v
751 {
752 match v
753 { Float(x) -> Ok(x)
754 // Many encoders write a whole number as an integer.
755 , Int(n) -> Ok(float.from_int n)
756 , _ -> Error(Mismatch("a Float", kind v))
757 }
758 }
759}
760
761impl ToMsgPack<String>
762{
763 fn to_msgpack :: s
764 {
765 Str(s)
766 }
767}
768
769impl FromMsgPack<String>
770{
771 fn from_msgpack :: v
772 {
773 match v { Str(s) -> Ok(s), _ -> Error(Mismatch("a Str", kind v)) }
774 }
775}
776
777impl ToMsgPack<Bytes>
778{
779 fn to_msgpack :: b
780 {
781 Bin(b)
782 }
783}
784
785impl FromMsgPack<Bytes>
786{
787 fn from_msgpack :: v
788 {
789 match v { Bin(b) -> Ok(b), _ -> Error(Mismatch("a Bin", kind v)) }
790 }
791}
792
793impl ToMsgPack<Bool>
794{
795 fn to_msgpack :: b
796 {
797 Bool(b)
798 }
799}
800
801impl FromMsgPack<Bool>
802{
803 fn from_msgpack :: v
804 {
805 match v { Bool(b) -> Ok(b), _ -> Error(Mismatch("a Bool", kind v)) }
806 }
807}
808
809impl ToMsgPack<List<a>> where ToMsgPack<a>
810{
811 fn to_msgpack :: xs
812 {
813 Array(list.map xs to_msgpack)
814 }
815}
816
817impl FromMsgPack<List<a>> where FromMsgPack<a>
818{
819 fn from_msgpack :: v
820 {
821 match v
822 { Array(items) -> result.all (list.map items from_msgpack)
823 , _ -> Error(Mismatch("an Array", kind v))
824 }
825 }
826}
827
828impl ToMsgPack<Array<a>> where ToMsgPack<a>
829{
830 fn to_msgpack :: xs
831 {
832 Array(list.map (array.to_list xs) to_msgpack)
833 }
834}
835
836impl FromMsgPack<Array<a>> where FromMsgPack<a>
837{
838 fn from_msgpack :: v
839 {
840 match v
841 { Array(items) ->
842 result.map (result.all (list.map items from_msgpack)) array.from_list
843 , _ -> Error(Mismatch("an Array", kind v))
844 }
845 }
846}
847
848/// `None` is nil and `Some(x)` is `x` (the ecosystem's convention, as in
849/// rmp): a nested `Option<Option<a>>` cannot tell `Some(None)` from
850/// `None`.
851impl ToMsgPack<Option<a>> where ToMsgPack<a>
852{
853 fn to_msgpack :: o
854 {
855 match o { None -> Nil, Some(x) -> to_msgpack x }
856 }
857}
858
859impl FromMsgPack<Option<a>> where FromMsgPack<a>
860{
861 fn from_msgpack :: v
862 {
863 match v
864 { Nil -> Ok(None), _ -> result.map (from_msgpack v) fn x { Some(x) } }
865 }
866}
867
868/// As the derived format for a sum: `\{"Ok": [x]}` or `\{"Error": [e]}`.
869impl ToMsgPack<Result<a, e>> where ToMsgPack<a>, ToMsgPack<e>
870{
871 fn to_msgpack :: r
872 {
873 match r
874 { Ok(x) -> Map([(Str("Ok"), Array([to_msgpack x]))])
875 , Error(x) -> Map([(Str("Error"), Array([to_msgpack x]))])
876 }
877 }
878}
879
880impl FromMsgPack<Result<a, e>> where FromMsgPack<a>, FromMsgPack<e>
881{
882 fn from_msgpack :: v
883 {
884 match v
885 { Map([(key, Array([x]))]) if key == Str("Ok") ->
886 {
887 match from_msgpack x { Ok(y) -> Ok(Ok(y)), Error(e) -> Error(e) }
888 }
889 , Map([(key, Array([x]))]) if key == Str("Error") ->
890 {
891 match from_msgpack x { Ok(y) -> Ok(Error(y)), Error(e) -> Error(e) }
892 }
893 , _ ->
894 Error( Mismatch( "a Result (\{\"Ok\": [..]\} or \{\"Error\": [..]\})"
895 , kind v
896 )
897 )
898 }
899 }
900}
901
902/// A `Dict` is a map; decoding needs `Ord<k>` to rebuild it.
903impl ToMsgPack<Dict<k, v>> where ToMsgPack<k>, ToMsgPack<v>
904{
905 fn to_msgpack :: d
906 {
907 Map(list.map (dict.to_list d) fn p { (to_msgpack p.0, to_msgpack p.1) })
908 }
909}
910
911impl FromMsgPack<Dict<k, v>> where FromMsgPack<k>, FromMsgPack<v>, Ord<k>
912{
913 fn from_msgpack :: v
914 {
915 match v
916 { Map(entries) ->
917 {
918 use pairs <- result.try (result.all (list.map entries decode_entry))
919 Ok(dict.from_list pairs)
920 }
921 , _ -> Error(Mismatch("a Map", kind v))
922 }
923 }
924}
925
926fn decode_entry ::
927 p: (Value, Value)
928 -> Result<(k, v), DecodeError>
929 where FromMsgPack<k>, FromMsgPack<v>
930{
931 use k <- result.try (from_msgpack p.0)
932 use v <- result.try (from_msgpack p.1)
933 Ok((k, v))
934}
935
936// ---- tests ------------------------------------------------------------------------
937
938import std/string
939import std/test.{assert, assert_equal}
940
941@test
942fn integers_smallest_encoding ::
943{
944 assert_equal (bytes.to_list (write Int(0))) [0]
945 assert_equal (bytes.to_list (write Int(127))) [127]
946 assert_equal (bytes.to_list (write Int(128))) [204, 128]
947 assert_equal (bytes.to_list (write Int(255))) [204, 255]
948 assert_equal (bytes.to_list (write Int(256))) [205, 1, 0]
949 assert_equal (bytes.to_list (write Int(65535))) [205, 255, 255]
950 assert_equal (bytes.to_list (write Int(65536))) [206, 0, 1, 0, 0]
951 assert_equal (bytes.to_list (write Int(4294967295))) [206, 255, 255, 255, 255]
952 assert_equal
953 (bytes.to_list (write Int(4294967296)))
954 [207, 0, 0, 0, 1, 0, 0, 0, 0]
955 assert_equal (bytes.to_list (write Int(-1))) [255]
956 assert_equal (bytes.to_list (write Int(-32))) [224]
957 assert_equal (bytes.to_list (write Int(-33))) [208, 223]
958 assert_equal (bytes.to_list (write Int(-128))) [208, 128]
959 assert_equal (bytes.to_list (write Int(-129))) [209, 255, 127]
960 assert_equal (bytes.to_list (write Int(-32768))) [209, 128, 0]
961 assert_equal (bytes.to_list (write Int(-32769))) [210, 255, 255, 127, 255]
962 assert_equal (bytes.to_list (write Int(-2147483648))) [210, 128, 0, 0, 0]
963 assert_equal
964 (bytes.to_list (write Int(-2147483649)))
965 [211, 255, 255, 255, 255, 127, 255, 255, 255]
966}
967
968@test
969fn scalars_round_trip ::
970{
971 let values =
972 [ Nil
973 , Bool(True)
974 , Bool(False)
975 , Int(0 - int.shift_left 1 63)
976 , Int(int.shift_left 1 64 - 1)
977 , Float(-0.0)
978 , Float(3.14159)
979 , Str("")
980 , Str("héllo, 世界")
981 , Bin(bytes.empty ())
982 , Bin(bytes.from_list [0, 159, 146, 150])
983 , Array([])
984 , Map([])
985 , Ext(-1, bytes.from_list [1, 2, 3, 4])
986 , Ext(127, bytes.empty ())
987 , Ext(2, bytes.from_list [1, 2])
988 , Ext(3, bytes.from_list [1, 2, 3, 4, 5, 6, 7, 8])
989 , Ext( 4
990 , bytes.from_list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
991 )
992 ]
993 list.fold
994 values
995 ()
996 fn _ v { assert (read (write v) == Ok(v)) ("round trip of " <> debug v) }
997}
998
999@test
1000fn lengths_smallest_encoding ::
1001{
1002 // fixstr up to 31 bytes, str 8 from 32; fixarray up to 15 items,
1003 // array 16 from 16.
1004 assert_equal
1005 (bytes.to_list (bytes.slice (write Str(string.repeat "a" 31)) 0 1))
1006 [191]
1007 assert_equal
1008 (bytes.to_list (bytes.slice (write Str(string.repeat "a" 32)) 0 2))
1009 [217, 32]
1010 assert_equal
1011 (bytes.to_list (bytes.slice (write Str(string.repeat "a" 256)) 0 3))
1012 [218, 1, 0]
1013 let items = list.map (list.range 1 15) Int_of
1014 assert_equal (bytes.to_list (bytes.slice (write Array(items)) 0 1)) [159]
1015 let items = list.map (list.range 1 16) Int_of
1016 assert_equal
1017 (bytes.to_list (bytes.slice (write Array(items)) 0 3))
1018 [220, 0, 16]
1019 // fixext 1/2/4/8/16 for those sizes, ext 8 beyond.
1020 assert_equal
1021 (bytes.to_list (bytes.slice (write Ext(0, bytes.from_list [0])) 0 1))
1022 [212]
1023 assert_equal
1024 (bytes.to_list (bytes.slice (write Ext(0, bytes.from_list [0, 0])) 0 1))
1025 [213]
1026 assert_equal
1027 (bytes.to_list (bytes.slice (write Ext(0, bytes.from_list [0, 0, 0])) 0 2))
1028 [199, 3]
1029}
1030
1031fn Int_of :: n: Int -> Value
1032{
1033 Int(n)
1034}
1035
1036@test
1037fn malformed_inputs_are_errors ::
1038{
1039 // Truncated, a length past the bytes left, the reserved byte, and
1040 // nesting past the cap: an error, never a panic or an allocation.
1041 assert
1042 ( read (bytes.from_list [204])
1043 == Error(Malformed(1, "a length of 1 with 0 bytes left"))
1044 )
1045 (debug (read (bytes.from_list [204])))
1046 assert
1047 (read (bytes.empty ()) == Error(Malformed(0, "the input ends early")))
1048 (debug (read (bytes.empty ())))
1049 assert
1050 ( read (bytes.from_list [217, 5, 97])
1051 == Error(Malformed(2, "a length of 5 with 1 bytes left"))
1052 )
1053 (debug (read (bytes.from_list [217, 5, 97])))
1054 assert
1055 ( read (bytes.from_list [221, 255, 255, 255, 255, 1])
1056 == Error(Malformed(5, "an array of 4294967295 items with 1 bytes left"))
1057 )
1058 (debug (read (bytes.from_list [221, 255, 255, 255, 255, 1])))
1059 assert
1060 ( read (bytes.from_list [193])
1061 == Error(Malformed(0, "0xc1 is not a MessagePack byte"))
1062 )
1063 (debug (read (bytes.from_list [193])))
1064 assert
1065 ( read (bytes.from_list [161, 255])
1066 == Error( Malformed( 1
1067 , "a str that is not UTF-8: invalid UTF-8 at byte 0"
1068 )
1069 )
1070 )
1071 (debug (read (bytes.from_list [161, 255])))
1072 assert
1073 ( read (bytes.from_list [1, 1])
1074 == Error(Malformed(1, "1 bytes after the value"))
1075 )
1076 (debug (read (bytes.from_list [1, 1])))
1077 // A map entry's key without its value.
1078 assert
1079 ( read (bytes.from_list [129, 161, 97])
1080 == Error(Malformed(3, "the input ends early"))
1081 )
1082 (debug (read (bytes.from_list [129, 161, 97])))
1083 // Truncated at every width of integer read, and inside bin and ext
1084 // payloads.
1085 assert
1086 ( read (bytes.from_list [205, 1])
1087 == Error(Malformed(1, "a length of 2 with 1 bytes left"))
1088 )
1089 (debug (read (bytes.from_list [205, 1])))
1090 assert
1091 ( read (bytes.from_list [206, 1, 2, 3])
1092 == Error(Malformed(1, "a length of 4 with 3 bytes left"))
1093 )
1094 (debug (read (bytes.from_list [206, 1, 2, 3])))
1095 assert
1096 ( read (bytes.from_list [207, 1, 2, 3, 4, 5, 6, 7])
1097 == Error(Malformed(1, "a length of 8 with 7 bytes left"))
1098 )
1099 (debug (read (bytes.from_list [207, 1, 2, 3, 4, 5, 6, 7])))
1100 assert
1101 ( read (bytes.from_list [203, 1, 2, 3])
1102 == Error(Malformed(1, "a length of 8 with 3 bytes left"))
1103 )
1104 (debug (read (bytes.from_list [203, 1, 2, 3])))
1105 assert
1106 ( read (bytes.from_list [196, 5, 97])
1107 == Error(Malformed(2, "a length of 5 with 1 bytes left"))
1108 )
1109 (debug (read (bytes.from_list [196, 5, 97])))
1110 // fixext 1 without its tag byte, and fixext 2 without its payload.
1111 assert
1112 ( read (bytes.from_list [212])
1113 == Error(Malformed(1, "the input ends early"))
1114 )
1115 (debug (read (bytes.from_list [212])))
1116 assert
1117 ( read (bytes.from_list [213, 5])
1118 == Error(Malformed(2, "a length of 2 with 0 bytes left"))
1119 )
1120 (debug (read (bytes.from_list [213, 5])))
1121 // A str cut in the middle of a UTF-8 sequence.
1122 assert
1123 ( read (bytes.from_list [162, 104, 255])
1124 == Error( Malformed( 1
1125 , "a str that is not UTF-8: invalid UTF-8 at byte 1"
1126 )
1127 )
1128 )
1129 (debug (read (bytes.from_list [162, 104, 255])))
1130}
1131
1132@test
1133fn traits_encode_and_decode ::
1134{
1135 assert_equal (bytes.to_list (encode [1, 2, 3])) [147, 1, 2, 3]
1136 assert_equal (decode (bytes.from_list [147, 1, 2, 3])) Ok([1, 2, 3])
1137 let d = dict.from_list [("a", 1), ("b", 2)]
1138 match decode (encode d)
1139 { Ok(back) -> assert_equal (dict.to_list back) [("a", 1), ("b", 2)]
1140 , Error(e) -> panic (show e)
1141 }
1142 let none: Option<Int> = None
1143 assert_equal (bytes.to_list (encode none)) [192]
1144 let ok: Result<Int, String> = Ok(1)
1145 assert_equal (decode (encode ok)) Ok(ok)
1146}