tuple_key/
lib.rs

1#![doc = include_str!("../README.md")]
2
3use std::collections::HashMap;
4use std::fmt::Debug;
5
6use buffertk::{v64, Packable};
7
8use buffertk::Unpackable;
9use prototk::{FieldNumber, WireType};
10use prototk_derive::Message;
11use zerror::{iotoz, Z};
12use zerror_core::ErrorCore;
13
14mod combine7;
15mod iter7;
16mod ordered;
17
18use combine7::Combine7BitChunks;
19use iter7::Iterate7BitChunks;
20
21/////////////////////////////////////////////// Error //////////////////////////////////////////////
22
23#[derive(Clone, Message, zerror_derive::Z)]
24pub enum Error {
25    #[prototk(311296, message)]
26    Success {
27        #[prototk(1, message)]
28        core: ErrorCore,
29    },
30    #[prototk(311297, message)]
31    CouldNotExtend {
32        #[prototk(1, message)]
33        core: ErrorCore,
34        #[prototk(2, uint32)]
35        field_number: u32,
36    },
37    #[prototk(311298, message)]
38    UnpackError {
39        #[prototk(1, message)]
40        core: ErrorCore,
41        #[prototk(2, message)]
42        err: prototk::Error,
43    },
44    #[prototk(311299, message)]
45    NotValidUtf8 {
46        #[prototk(1, message)]
47        core: ErrorCore,
48    },
49    #[prototk(311300, message)]
50    InvalidTag {
51        #[prototk(1, message)]
52        core: ErrorCore,
53    },
54    #[prototk(311301, message)]
55    SchemaIncompatibility {
56        #[prototk(1, message)]
57        core: ErrorCore,
58        #[prototk(2, string)]
59        what: String,
60    },
61    #[prototk(311301, message)]
62    Corruption {
63        #[prototk(1, message)]
64        core: ErrorCore,
65        #[prototk(2, string)]
66        what: String,
67    },
68}
69
70impl Error {
71    pub fn schema_incompatibility(s: impl Into<String>) -> Self {
72        Self::SchemaIncompatibility {
73            core: ErrorCore::default(),
74            what: s.into(),
75        }
76    }
77}
78
79impl Default for Error {
80    fn default() -> Error {
81        Error::Success {
82            core: ErrorCore::default(),
83        }
84    }
85}
86
87impl From<buffertk::Error> for Error {
88    fn from(err: buffertk::Error) -> Self {
89        let err: prototk::Error = err.into();
90        Self::from(err)
91    }
92}
93
94impl From<prototk::Error> for Error {
95    fn from(err: prototk::Error) -> Self {
96        Self::UnpackError {
97            core: ErrorCore::default(),
98            err,
99        }
100    }
101}
102
103iotoz! {Error}
104
105//////////////////////////////////////////// KeyDataType ///////////////////////////////////////////
106
107#[derive(Copy, Clone, Debug, Default, Message, Eq, PartialEq, Ord, PartialOrd, Hash)]
108#[allow(non_camel_case_types)]
109pub enum KeyDataType {
110    #[default]
111    #[prototk(1, message)]
112    unit,
113    #[prototk(2, message)]
114    fixed32,
115    #[prototk(3, message)]
116    fixed64,
117    #[prototk(4, message)]
118    sfixed32,
119    #[prototk(5, message)]
120    sfixed64,
121    #[prototk(7, message)]
122    string,
123}
124
125impl KeyDataType {
126    pub fn wire_type(self) -> WireType {
127        match self {
128            KeyDataType::unit => WireType::LengthDelimited,
129            KeyDataType::fixed32 => WireType::ThirtyTwo,
130            KeyDataType::fixed64 => WireType::SixtyFour,
131            KeyDataType::sfixed32 => WireType::ThirtyTwo,
132            KeyDataType::sfixed64 => WireType::SixtyFour,
133            KeyDataType::string => WireType::LengthDelimited,
134        }
135    }
136}
137
138///////////////////////////////////////////// Direction ////////////////////////////////////////////
139
140#[derive(Copy, Clone, Debug, Default, Message, Eq, PartialEq, Ord, PartialOrd, Hash)]
141#[allow(non_camel_case_types)]
142pub enum Direction {
143    #[default]
144    #[prototk(1, message)]
145    Forward,
146    #[prototk(2, message)]
147    Reverse,
148}
149
150/////////////////////////////////////////// discriminant ///////////////////////////////////////////
151
152pub fn to_discriminant(key: KeyDataType, dir: Direction) -> u8 {
153    match (key, dir) {
154        (KeyDataType::unit, Direction::Forward) => 1,
155        (KeyDataType::fixed32, Direction::Forward) => 2,
156        (KeyDataType::fixed64, Direction::Forward) => 3,
157        (KeyDataType::sfixed32, Direction::Forward) => 4,
158        (KeyDataType::sfixed64, Direction::Forward) => 5,
159        (KeyDataType::string, Direction::Forward) => 6,
160
161        (KeyDataType::unit, Direction::Reverse) => 9,
162        (KeyDataType::fixed32, Direction::Reverse) => 10,
163        (KeyDataType::fixed64, Direction::Reverse) => 11,
164        (KeyDataType::sfixed32, Direction::Reverse) => 12,
165        (KeyDataType::sfixed64, Direction::Reverse) => 13,
166        (KeyDataType::string, Direction::Reverse) => 14,
167    }
168}
169
170pub fn from_discriminant(discriminant: u8) -> Option<(KeyDataType, Direction)> {
171    match discriminant {
172        1 => Some((KeyDataType::unit, Direction::Forward)),
173        2 => Some((KeyDataType::fixed32, Direction::Forward)),
174        3 => Some((KeyDataType::fixed64, Direction::Forward)),
175        4 => Some((KeyDataType::sfixed32, Direction::Forward)),
176        5 => Some((KeyDataType::sfixed64, Direction::Forward)),
177        6 => Some((KeyDataType::string, Direction::Forward)),
178
179        9 => Some((KeyDataType::unit, Direction::Reverse)),
180        10 => Some((KeyDataType::fixed32, Direction::Reverse)),
181        11 => Some((KeyDataType::fixed64, Direction::Reverse)),
182        12 => Some((KeyDataType::sfixed32, Direction::Reverse)),
183        13 => Some((KeyDataType::sfixed64, Direction::Reverse)),
184        14 => Some((KeyDataType::string, Direction::Reverse)),
185        _ => None,
186    }
187}
188
189///////////////////////////////////////////// TupleKey /////////////////////////////////////////////
190
191#[derive(Clone, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
192pub struct TupleKey {
193    buf: Vec<u8>,
194}
195
196impl TupleKey {
197    pub fn len(&self) -> usize {
198        self.buf.len()
199    }
200
201    pub fn is_empty(&self) -> bool {
202        self.buf.is_empty()
203    }
204
205    pub fn as_bytes(&self) -> &[u8] {
206        &self.buf
207    }
208
209    pub fn append(&mut self, other: &mut TupleKey) {
210        self.buf.append(&mut other.buf);
211    }
212
213    pub fn extend(&mut self, f: FieldNumber) {
214        self.extend_field_number(f, KeyDataType::unit, Direction::Forward);
215        ().append_to(self);
216    }
217
218    pub fn extend_with_key<E: Element>(&mut self, f: FieldNumber, elem: E, dir: Direction) {
219        self.extend_field_number(f, E::DATA_TYPE, dir);
220        let sz = self.buf.len();
221        elem.append_to(self);
222        if Direction::Reverse == dir {
223            reverse_encoding(&mut self.buf[sz..]);
224        }
225    }
226
227    pub fn iter(&self) -> TupleKeyIterator<'_> {
228        let buf: &[u8] = &self.buf;
229        TupleKeyIterator::from(buf)
230    }
231
232    pub fn conforms_to<T: Debug>(&self, schema: &Schema<T>) -> bool {
233        schema.lookup(self).is_ok()
234    }
235
236    fn append_bytes(&mut self, iter: impl Iterator<Item = u8>) -> usize {
237        let mut count = 0;
238        for c in iter {
239            self.buf.push(c);
240            count += 1;
241        }
242        count
243    }
244
245    fn field_number(f: FieldNumber, value: KeyDataType, dir: Direction) -> ([u8; 10], usize) {
246        let discriminant = to_discriminant(value, dir) as u64;
247        assert!(discriminant < 16);
248        let f: v64 = v64::from(((f.get() as u64) << 4) | discriminant);
249        let mut buf = [0u8; 10];
250        let sz = f.pack_sz();
251        v64::pack(&f, &mut buf[0..sz]);
252        // Shift the high order bit of the varint to the low order bit of the varint
253        buf[0..sz].iter_mut().for_each(|c| *c = c.rotate_left(1));
254        (buf, sz)
255    }
256
257    fn unfield_number(buf_in: &[u8]) -> Option<(FieldNumber, KeyDataType, Direction)> {
258        if buf_in.len() > 10 {
259            return None;
260        }
261        let mut buf = [0u8; 10];
262        for (f, t) in std::iter::zip(buf_in.iter(), buf.iter_mut()) {
263            *t = *f;
264        }
265        let sz = buf_in.len();
266        buf[0..sz].iter_mut().for_each(|c| *c = c.rotate_right(1));
267        let x = v64::unpack(&buf[0..sz]).ok()?.0;
268        let x: u64 = x.into();
269        let (key_type, direction) = from_discriminant(x as u8 & 15u8)?;
270        if x >> 4 > u32::MAX as u64 {
271            return None;
272        }
273        let field_number = FieldNumber::new((x >> 4) as u32).ok()?;
274        Some((field_number, key_type, direction))
275    }
276
277    fn extend_field_number(&mut self, f: FieldNumber, value: KeyDataType, dir: Direction) {
278        let (buf, sz) = Self::field_number(f, value, dir);
279        self.buf.extend_from_slice(&buf[0..sz])
280    }
281}
282
283impl std::ops::Deref for TupleKey {
284    type Target = [u8];
285
286    fn deref(&self) -> &Self::Target {
287        &self.buf
288    }
289}
290
291// NOTE(rescrv):  This is not a try_from.  Every byte string is a valid tuple key, because despite
292// our conventions above, a tuple key is just a sequence of byte strings.  The typing is such a
293// convenience that it's tied in.  If you need a tuple key to adhere to a given structure, you need
294// to parse and validate it separately from this function.
295impl From<&[u8]> for TupleKey {
296    fn from(buf: &[u8]) -> Self {
297        Self { buf: buf.to_vec() }
298    }
299}
300
301///////////////////////////////////////// TupleKeyIterator /////////////////////////////////////////
302
303#[derive(Clone, Debug)]
304pub struct TupleKeyIterator<'a> {
305    buf: &'a [u8],
306    offset: usize,
307}
308
309impl TupleKeyIterator<'_> {
310    pub fn number_of_elements_in_common_prefix(lhs: Self, rhs: Self) -> usize {
311        let mut max_idx = 0;
312        for (idx, (x, y)) in std::iter::zip(lhs, rhs).enumerate() {
313            if x != y {
314                return idx / 2;
315            }
316            max_idx = idx;
317        }
318        max_idx.div_ceil(2)
319    }
320}
321
322impl<'a> From<&'a [u8]> for TupleKeyIterator<'a> {
323    fn from(buf: &'a [u8]) -> Self {
324        Self { buf, offset: 0 }
325    }
326}
327
328impl<'a> From<&'a TupleKey> for TupleKeyIterator<'a> {
329    fn from(tk: &'a TupleKey) -> Self {
330        let buf: &'a [u8] = &tk.buf;
331        Self::from(buf)
332    }
333}
334
335impl<'a> Iterator for TupleKeyIterator<'a> {
336    type Item = &'a [u8];
337
338    fn next(&mut self) -> Option<Self::Item> {
339        if self.offset >= self.buf.len() {
340            None
341        } else {
342            let start = self.offset;
343            while self.offset < self.buf.len() && self.buf[self.offset] & 0x1 != 0 {
344                self.offset += 1;
345            }
346            if self.offset < self.buf.len() {
347                self.offset += 1;
348            }
349            let limit = self.offset;
350            Some(&self.buf[start..limit])
351        }
352    }
353}
354
355////////////////////////////////////////// TupleKeyParser //////////////////////////////////////////
356
357pub struct TupleKeyParser<'a> {
358    iter: TupleKeyIterator<'a>,
359}
360
361impl<'a> TupleKeyParser<'a> {
362    pub fn new(tk: &'a TupleKey) -> Self {
363        Self {
364            iter: TupleKeyIterator::from(tk),
365        }
366    }
367
368    pub fn peek_next(&self) -> Result<Option<(FieldNumber, KeyDataType, Direction)>, &'static str> {
369        let elem = match self.iter.clone().next() {
370            Some(elem) => elem,
371            None => {
372                return Ok(None);
373            }
374        };
375        Ok(Some(
376            TupleKey::unfield_number(elem).ok_or("not a valid tag")?,
377        ))
378    }
379
380    pub fn parse_next(&mut self, f: FieldNumber, dir: Direction) -> Result<(), &'static str> {
381        self.parse_next_tag(f, KeyDataType::unit, dir)?;
382        let pad = match self.iter.next() {
383            Some(pad) => pad,
384            None => {
385                return Err("no more elements to TupleKey");
386            }
387        };
388        if pad.len() != 1 {
389            return Err("unit struct with length != 1");
390        }
391        Ok(())
392    }
393
394    pub fn parse_next_with_key<E: Element>(
395        &mut self,
396        f: FieldNumber,
397        dir: Direction,
398    ) -> Result<E, &'static str> {
399        // First we parse_next as normal.
400        self.parse_next_tag(f, E::DATA_TYPE, dir)?;
401        // Read the value
402        let value = match self.iter.next() {
403            Some(value) => value,
404            None => {
405                return Err("missing value element");
406            }
407        };
408        if Direction::Reverse == dir {
409            let mut value = value.to_vec();
410            reverse_encoding(&mut value);
411            E::parse_from(&value)
412        } else {
413            E::parse_from(value)
414        }
415    }
416
417    fn parse_next_tag(
418        &mut self,
419        f: FieldNumber,
420        ty: KeyDataType,
421        dir: Direction,
422    ) -> Result<(), &'static str> {
423        let elem = match self.iter.next() {
424            Some(elem) => elem,
425            None => {
426                return Err("no more elements to TupleKey");
427            }
428        };
429        let (buf, sz) = TupleKey::field_number(f, ty, dir);
430        if &buf[0..sz] != elem {
431            return Err("tag does not match");
432        }
433        Ok(())
434    }
435}
436
437////////////////////////////////////////////// Element /////////////////////////////////////////////
438
439pub trait Element: Sized {
440    const DATA_TYPE: KeyDataType;
441
442    fn append_to(&self, key: &mut TupleKey);
443    fn parse_from(buf: &[u8]) -> Result<Self, &'static str>;
444
445    fn key_data_type(&self) -> KeyDataType {
446        <Self as Element>::DATA_TYPE
447    }
448}
449
450impl Element for () {
451    const DATA_TYPE: KeyDataType = KeyDataType::unit;
452
453    fn append_to(&self, key: &mut TupleKey) {
454        key.append_bytes(&mut [0u8].iter().copied());
455    }
456
457    fn parse_from(buf: &[u8]) -> Result<Self, &'static str> {
458        if buf.len() != 1 {
459            return Err("unit not exactly 1 bytes");
460        }
461        Ok(())
462    }
463}
464
465impl Element for u32 {
466    const DATA_TYPE: KeyDataType = KeyDataType::fixed32;
467
468    fn append_to(&self, key: &mut TupleKey) {
469        key.buf.push(((self >> 24) | 1) as u8);
470        key.buf.push(((self >> 17) | 1) as u8);
471        key.buf.push(((self >> 10) | 1) as u8);
472        key.buf.push(((self >> 3) | 1) as u8);
473        key.buf.push(((self & 0xf) << 4) as u8);
474    }
475
476    fn parse_from(buf: &[u8]) -> Result<Self, &'static str> {
477        if buf.len() != 5 {
478            return Err("buf not exactly 5 bytes");
479        }
480        let mut key = 0u32;
481        key |= ((buf[0] & 0xfe) as u32) << 24;
482        key |= ((buf[1] & 0xfe) as u32) << 17;
483        key |= ((buf[2] & 0xfe) as u32) << 10;
484        key |= ((buf[3] & 0xfe) as u32) << 3;
485        key |= ((buf[4] & 0xf0) as u32) >> 4;
486        Ok(key)
487    }
488}
489
490impl Element for u64 {
491    const DATA_TYPE: KeyDataType = KeyDataType::fixed64;
492
493    fn append_to(&self, key: &mut TupleKey) {
494        key.buf.push(((self >> 56) | 1) as u8);
495        key.buf.push(((self >> 49) | 1) as u8);
496        key.buf.push(((self >> 42) | 1) as u8);
497        key.buf.push(((self >> 35) | 1) as u8);
498        key.buf.push(((self >> 28) | 1) as u8);
499        key.buf.push(((self >> 21) | 1) as u8);
500        key.buf.push(((self >> 14) | 1) as u8);
501        key.buf.push(((self >> 7) | 1) as u8);
502        key.buf.push((self | 1) as u8);
503        key.buf.push(((self & 0x1) << 7) as u8);
504    }
505
506    fn parse_from(buf: &[u8]) -> Result<Self, &'static str> {
507        if buf.len() != 10 {
508            return Err("buf not exactly 10 bytes");
509        }
510        let mut key = 0u64;
511        key |= ((buf[0] & 0xfe) as u64) << 56;
512        key |= ((buf[1] & 0xfe) as u64) << 49;
513        key |= ((buf[2] & 0xfe) as u64) << 42;
514        key |= ((buf[3] & 0xfe) as u64) << 35;
515        key |= ((buf[4] & 0xfe) as u64) << 28;
516        key |= ((buf[5] & 0xfe) as u64) << 21;
517        key |= ((buf[6] & 0xfe) as u64) << 14;
518        key |= ((buf[7] & 0xfe) as u64) << 7;
519        key |= (buf[8] & 0xfe) as u64;
520        key |= ((buf[9] & 0x80) as u64) >> 7;
521        Ok(key)
522    }
523}
524
525impl Element for i32 {
526    const DATA_TYPE: KeyDataType = KeyDataType::sfixed32;
527
528    fn append_to(&self, key: &mut TupleKey) {
529        let num: u32 = ordered::encode_i32(*self);
530        key.buf.push(((num >> 24) | 1) as u8);
531        key.buf.push(((num >> 17) | 1) as u8);
532        key.buf.push(((num >> 10) | 1) as u8);
533        key.buf.push(((num >> 3) | 1) as u8);
534        key.buf.push(((num & 0xf) << 4) as u8);
535    }
536
537    fn parse_from(buf: &[u8]) -> Result<Self, &'static str> {
538        if buf.len() != 5 {
539            return Err("buf not exactly 5 bytes");
540        }
541        let mut key = 0u32;
542        key |= ((buf[0] & 0xfe) as u32) << 24;
543        key |= ((buf[1] & 0xfe) as u32) << 17;
544        key |= ((buf[2] & 0xfe) as u32) << 10;
545        key |= ((buf[3] & 0xfe) as u32) << 3;
546        key |= ((buf[4] & 0xf0) as u32) >> 4;
547        Ok(ordered::decode_i32(key))
548    }
549}
550
551impl Element for i64 {
552    const DATA_TYPE: KeyDataType = KeyDataType::sfixed64;
553
554    fn append_to(&self, key: &mut TupleKey) {
555        let num: u64 = ordered::encode_i64(*self);
556        key.buf.push(((num >> 56) | 1) as u8);
557        key.buf.push(((num >> 49) | 1) as u8);
558        key.buf.push(((num >> 42) | 1) as u8);
559        key.buf.push(((num >> 35) | 1) as u8);
560        key.buf.push(((num >> 28) | 1) as u8);
561        key.buf.push(((num >> 21) | 1) as u8);
562        key.buf.push(((num >> 14) | 1) as u8);
563        key.buf.push(((num >> 7) | 1) as u8);
564        key.buf.push((num | 1) as u8);
565        key.buf.push(((num & 0x1) << 7) as u8);
566    }
567
568    fn parse_from(buf: &[u8]) -> Result<Self, &'static str> {
569        if buf.len() != 10 {
570            return Err("buf not exactly 10 bytes");
571        }
572        let mut key = 0u64;
573        key |= ((buf[0] & 0xfe) as u64) << 56;
574        key |= ((buf[1] & 0xfe) as u64) << 49;
575        key |= ((buf[2] & 0xfe) as u64) << 42;
576        key |= ((buf[3] & 0xfe) as u64) << 35;
577        key |= ((buf[4] & 0xfe) as u64) << 28;
578        key |= ((buf[5] & 0xfe) as u64) << 21;
579        key |= ((buf[6] & 0xfe) as u64) << 14;
580        key |= ((buf[7] & 0xfe) as u64) << 7;
581        key |= (buf[8] & 0xfe) as u64;
582        key |= ((buf[9] & 0x80) as u64) >> 7;
583        Ok(ordered::decode_i64(key))
584    }
585}
586
587impl Element for String {
588    const DATA_TYPE: KeyDataType = KeyDataType::string;
589
590    fn append_to(&self, key: &mut TupleKey) {
591        let iter = Iterate7BitChunks::new(self.as_bytes());
592        if key.append_bytes(iter) == 0 {
593            key.append_bytes(&mut [0u8].iter().copied());
594        }
595    }
596
597    fn parse_from(buf: &[u8]) -> Result<Self, &'static str> {
598        if buf.len() == 1 {
599            return Ok(String::new());
600        }
601        let combiner = Combine7BitChunks::new(buf);
602        String::from_utf8(combiner.collect()).map_err(|_| "invalid UTF-8 sequence")
603    }
604}
605
606/////////////////////////////////////////// TypedTupleKey //////////////////////////////////////////
607
608pub trait TypedTupleKey: TryFrom<TupleKey> + Into<TupleKey> {}
609
610////////////////////////////////////////////// Schema //////////////////////////////////////////////
611
612#[derive(Debug)]
613pub struct Schema<T: Debug> {
614    node: T,
615    children: HashMap<FieldNumber, Schema<T>>,
616    names: HashMap<String, FieldNumber>,
617}
618
619impl<T: Debug> Schema<T> {
620    pub fn new<I: Iterator<Item = ((FieldNumber, String), Schema<T>)>>(node: T, sub: I) -> Self {
621        let mut children = HashMap::new();
622        let mut names = HashMap::new();
623        for ((field_number, name), schema) in sub {
624            names.insert(name, field_number);
625            children.insert(field_number, schema);
626        }
627        Self {
628            node,
629            children,
630            names,
631        }
632    }
633
634    pub fn field_number(&self, name: impl AsRef<str>) -> Option<FieldNumber> {
635        self.names.get(name.as_ref()).cloned()
636    }
637
638    pub fn child(&self, f: FieldNumber) -> Option<&Schema<T>> {
639        self.children.get(&f)
640    }
641
642    pub fn is_terminal(&self, tk: &TupleKey) -> Result<bool, Error> {
643        Ok(self.schema_for_key(tk)?.children.is_empty())
644    }
645
646    pub fn lookup(&self, tk: &TupleKey) -> Result<&T, Error> {
647        Ok(&self.schema_for_key(tk)?.node)
648    }
649
650    pub fn schema_for_key<'a>(&'a self, tk: &TupleKey) -> Result<&'a Schema<T>, Error> {
651        let mut tkp = TupleKeyParser::new(tk);
652        let mut args = vec![];
653        self.schema_for_key_recurse(&mut tkp, 0, &mut args)
654    }
655
656    pub fn args_for_key(&self, tk: &TupleKey) -> Result<Vec<String>, Error> {
657        let mut tkp = TupleKeyParser::new(tk);
658        let mut args = vec![];
659        self.schema_for_key_recurse(&mut tkp, 0, &mut args)?;
660        Ok(args)
661    }
662
663    fn schema_for_key_recurse<'a>(
664        &'a self,
665        tkp: &mut TupleKeyParser,
666        index: usize,
667        args: &mut Vec<String>,
668    ) -> Result<&'a Schema<T>, Error> {
669        if let Some((f, k, d)) = tkp.peek_next().map_err(Error::schema_incompatibility)? {
670            let Some(name) = self.names.iter().find(|(_, v)| **v == f) else {
671                return Err(Error::schema_incompatibility(format!(
672                    "unknown field {f} at index {index}"
673                )));
674            };
675            args.push(format!("--{}", name.0));
676            if let Some(recurse) = self.children.get(&f) {
677                match k {
678                    KeyDataType::unit => {
679                        tkp.parse_next(f, d)
680                            .map_err(Error::schema_incompatibility)?;
681                    }
682                    KeyDataType::fixed32 => {
683                        let v: u32 = tkp
684                            .parse_next_with_key(f, d)
685                            .map_err(Error::schema_incompatibility)?;
686                        args.push(v.to_string());
687                    }
688                    KeyDataType::sfixed32 => {
689                        let v: i32 = tkp
690                            .parse_next_with_key(f, d)
691                            .map_err(Error::schema_incompatibility)?;
692                        args.push(v.to_string());
693                    }
694                    KeyDataType::fixed64 => {
695                        let v: u64 = tkp
696                            .parse_next_with_key(f, d)
697                            .map_err(Error::schema_incompatibility)?;
698                        args.push(v.to_string());
699                    }
700                    KeyDataType::sfixed64 => {
701                        let v: i64 = tkp
702                            .parse_next_with_key(f, d)
703                            .map_err(Error::schema_incompatibility)?;
704                        args.push(v.to_string());
705                    }
706                    KeyDataType::string => {
707                        let v: String = tkp
708                            .parse_next_with_key(f, d)
709                            .map_err(Error::schema_incompatibility)?;
710                        args.push(v.to_string());
711                    }
712                };
713                recurse.schema_for_key_recurse(tkp, index + 1, args)
714            } else {
715                Err(Error::schema_incompatibility(format!(
716                    "unknown field {f} at index {index}"
717                )))
718            }
719        } else {
720            Ok(self)
721        }
722    }
723}
724
725///////////////////////////////////////// reverse_encoding /////////////////////////////////////////
726
727fn reverse_encoding(bytes: &mut [u8]) {
728    for b in bytes.iter_mut() {
729        *b = (!*b & 0xfe) | (*b & 0x1);
730    }
731}
732
733/////////////////////////////////////////////// tests //////////////////////////////////////////////
734
735#[cfg(test)]
736mod tuple_key {
737    use super::*;
738
739    mod append {
740        use super::*;
741
742        #[test]
743        fn two_empties() {
744            let mut tk1 = TupleKey::default();
745            let mut tk2 = TupleKey::default();
746            tk1.append(&mut tk2);
747            assert!(tk1.as_bytes().is_empty());
748            assert!(tk2.is_empty());
749        }
750
751        #[test]
752        fn two_triplets() {
753            let mut tk1 = TupleKey::default();
754            tk1.extend_with_key(FieldNumber::must(1), "A".to_owned(), Direction::Forward);
755            tk1.extend_with_key(FieldNumber::must(2), "B".to_owned(), Direction::Forward);
756            tk1.extend_with_key(FieldNumber::must(3), "C".to_owned(), Direction::Forward);
757            let mut tk2 = TupleKey::default();
758            tk2.extend_with_key(FieldNumber::must(4), "D".to_owned(), Direction::Forward);
759            tk2.extend_with_key(FieldNumber::must(5), "E".to_owned(), Direction::Forward);
760            tk2.extend_with_key(FieldNumber::must(6), "F".to_owned(), Direction::Forward);
761            // preconditions
762            assert_eq!(&[44, 65, 128, 76, 67, 0, 108, 67, 128], tk1.as_bytes());
763            assert_eq!(&[140, 69, 0, 172, 69, 128, 204, 71, 0], tk2.as_bytes());
764            // what we want to test
765            tk1.append(&mut tk2);
766            assert_eq!(
767                &[44, 65, 128, 76, 67, 0, 108, 67, 128, 140, 69, 0, 172, 69, 128, 204, 71, 0,],
768                tk1.as_bytes()
769            );
770            assert!(tk2.is_empty());
771        }
772    }
773
774    mod iterator {
775        use super::*;
776
777        #[test]
778        fn empty() {
779            let tk1 = TupleKey::default();
780            let mut iter = TupleKeyIterator::from(&tk1);
781            assert_eq!(None, iter.next());
782        }
783
784        #[test]
785        fn abc() {
786            let mut tk1 = TupleKey::default();
787            tk1.extend_with_key(FieldNumber::must(1), "A".to_string(), Direction::Forward);
788            tk1.extend_with_key(FieldNumber::must(2), "B".to_string(), Direction::Forward);
789            tk1.extend_with_key(FieldNumber::must(3), "C".to_string(), Direction::Forward);
790            let mut iter = TupleKeyIterator::from(&tk1);
791
792            let buf: &[u8] = &[44];
793            assert_eq!(Some(buf), iter.next());
794            let buf: &[u8] = &[65, 128];
795            assert_eq!(Some(buf), iter.next());
796
797            let buf: &[u8] = &[76];
798            assert_eq!(Some(buf), iter.next());
799            let buf: &[u8] = &[67, 0];
800            assert_eq!(Some(buf), iter.next());
801
802            let buf: &[u8] = &[108];
803            assert_eq!(Some(buf), iter.next());
804            let buf: &[u8] = &[67, 128];
805            assert_eq!(Some(buf), iter.next());
806
807            assert_eq!(None, iter.next());
808        }
809
810        #[test]
811        fn common_prefix() {
812            let mut tk1 = TupleKey::default();
813            tk1.extend_with_key(FieldNumber::must(1), "A".to_string(), Direction::Forward);
814            tk1.extend_with_key(FieldNumber::must(2), "B".to_string(), Direction::Forward);
815            tk1.extend_with_key(FieldNumber::must(3), "C".to_string(), Direction::Forward);
816            let mut tk2 = TupleKey::default();
817            // (A, B, C), (), 0
818            assert_eq!(
819                0,
820                TupleKeyIterator::number_of_elements_in_common_prefix(tk1.iter(), tk2.iter())
821            );
822            // (A, B, C), (A), 1
823            tk2.extend_with_key(FieldNumber::must(1), "A".to_string(), Direction::Forward);
824            assert_eq!(
825                1,
826                TupleKeyIterator::number_of_elements_in_common_prefix(tk1.iter(), tk2.iter())
827            );
828            // (A, B, C), (A, B), 2
829            tk2.extend_with_key(FieldNumber::must(2), "B".to_string(), Direction::Forward);
830            assert_eq!(
831                2,
832                TupleKeyIterator::number_of_elements_in_common_prefix(tk1.iter(), tk2.iter())
833            );
834            // (A, B, C), (A, B, C), 3
835            let mut tk3 = tk2.clone();
836            tk2.extend_with_key(FieldNumber::must(3), "C".to_string(), Direction::Forward);
837            assert_eq!(
838                3,
839                TupleKeyIterator::number_of_elements_in_common_prefix(tk1.iter(), tk2.iter())
840            );
841            // (A, B, C, D), (A, B, D), 2
842            tk3.extend_with_key(FieldNumber::must(4), "D".to_string(), Direction::Forward);
843            assert_eq!(
844                2,
845                TupleKeyIterator::number_of_elements_in_common_prefix(tk1.iter(), tk3.iter())
846            );
847        }
848    }
849
850    mod properties {
851        use super::*;
852
853        proptest::proptest! {
854            #[test]
855            fn field_number_round_trip(f in 1..prototk::FIRST_RESERVED_FIELD_NUMBER) {
856                for d in [Direction::Forward, Direction::Reverse] {
857                    for v in [
858                        KeyDataType::unit,
859                        KeyDataType::fixed32,
860                        KeyDataType::fixed64,
861                        KeyDataType::sfixed32,
862                        KeyDataType::sfixed64,
863                        KeyDataType::string,
864                    ] {
865                        let (buf, sz) = TupleKey::field_number(FieldNumber::must(f), v, d);
866                        let (f1, v1, d1) = TupleKey::unfield_number(&buf[..sz]).unwrap();
867                        assert_eq!(f1, f);
868                        assert_eq!(v1, v);
869                        assert_eq!(d1, d);
870                    }
871                }
872            }
873        }
874    }
875}
876
877#[cfg(test)]
878mod elements {
879    use super::*;
880
881    fn test_helper<E: Element + Debug + Eq>(elem: E, exp: &[u8]) {
882        let mut tk = TupleKey::default();
883        elem.append_to(&mut tk);
884        assert_eq!(exp, tk.as_bytes());
885        let got = E::parse_from(exp).unwrap();
886        assert_eq!(got, elem);
887    }
888
889    #[test]
890    fn to_from_unit() {
891        const VALUE: () = ();
892        test_helper(VALUE, &[0]);
893    }
894
895    #[test]
896    fn to_from_u32() {
897        const VALUE: u32 = 0x1eaff00du32;
898        test_helper(
899            VALUE,
900            &[0b00011111, 0b01010111, 0b11111101, 0b00000001, 0b11010000],
901        );
902    }
903
904    #[test]
905    fn to_from_u64() {
906        const VALUE: u64 = 0x1eaff00d00c0ffeeu64;
907        test_helper(
908            VALUE,
909            &[
910                0b00011111, 0b01010111, 0b11111101, 0b00000001, 0b11010001, 0b00000111, 0b00000011,
911                0b11111111, 0b11101111, 0b00000000,
912            ],
913        );
914    }
915
916    #[test]
917    fn to_from_i32() {
918        const VALUE: i32 = 0x1eaff00di32;
919        test_helper(
920            VALUE,
921            &[0b10011111, 0b01010111, 0b11111101, 0b00000001, 0b11010000],
922        );
923    }
924
925    #[test]
926    fn to_from_i64() {
927        const VALUE: i64 = 0x1eaff00d00c0ffeei64;
928        test_helper(
929            VALUE,
930            &[
931                0b10011111, 0b01010111, 0b11111101, 0b00000001, 0b11010001, 0b00000111, 0b00000011,
932                0b11111111, 0b11101111, 0b00000000,
933            ],
934        );
935    }
936
937    #[test]
938    fn to_from_string_empty() {
939        let value: String = "".to_owned();
940        test_helper(value, &[0]);
941    }
942
943    #[test]
944    fn to_from_string() {
945        let value: String = "hello world".to_owned();
946        test_helper(
947            value,
948            &[105, 51, 91, 141, 199, 121, 129, 239, 111, 185, 155, 141, 64],
949        );
950    }
951}
tuple_key/lib.rs

tuple_key/
lib.rs
