1
/// [`Key`] implementations for time types.
2
pub mod time;
3

            
4
use std::{
5
    borrow::Cow,
6
    convert::Infallible,
7
    io::{ErrorKind, Write},
8
    num::TryFromIntError,
9
    string::FromUtf8Error,
10
};
11

            
12
use arc_bytes::{
13
    serde::{Bytes, CowBytes},
14
    ArcBytes,
15
};
16
use num_traits::{FromPrimitive, ToPrimitive};
17
use ordered_varint::{Signed, Unsigned, Variable};
18
use serde::{Deserialize, Serialize};
19

            
20
use crate::{connection::Range, AnyError};
21

            
22
/// A trait that enables a type to convert itself into a `memcmp`-compatible
23
/// sequence of bytes.
24
pub trait KeyEncoding<'k, K>: std::fmt::Debug + Send + Sync
25
where
26
    K: Key<'k>,
27
{
28
    /// The error type that can be produced by either serialization or
29
    /// deserialization.
30
    type Error: AnyError;
31

            
32
    /// The size of the key, if constant. If this type doesn't produce the same
33
    /// number of bytes for each value, this should be `None`.
34
    const LENGTH: Option<usize>;
35

            
36
    /// Convert `self` into a `Cow<[u8]>` containing bytes that are able to be
37
    /// compared via `memcmp` in a way that is comptaible with its own Ord
38
    /// implementation.
39
    fn as_ord_bytes(&'k self) -> Result<Cow<'k, [u8]>, Self::Error>;
40
}
41

            
42
/// A trait that enables a type to convert itself into a `memcmp`-compatible
43
/// sequence of bytes.
44
pub trait Key<'k>: KeyEncoding<'k, Self> + Clone + std::fmt::Debug + Send + Sync {
45
    /// Deserialize a sequence of bytes previously encoded with
46
    /// [`KeyEncoding::as_ord_bytes`].
47
    fn from_ord_bytes(bytes: &'k [u8]) -> Result<Self, Self::Error>;
48

            
49
    /// Return the first value in sequence for this type. Not all types
50
    /// implement this.
51
    fn first_value() -> Result<Self, NextValueError> {
52
        Err(NextValueError::Unsupported)
53
    }
54

            
55
    /// Return the next value in sequence for this type. Not all types implement
56
    /// this. Instead of wrapping/overflowing, None should be returned.
57
1
    fn next_value(&self) -> Result<Self, NextValueError> {
58
1
        Err(NextValueError::Unsupported)
59
1
    }
60
}
61

            
62
impl<'a, 'k, K> KeyEncoding<'k, K> for &'a K
63
where
64
    K: Key<'k>,
65
{
66
    type Error = K::Error;
67

            
68
    const LENGTH: Option<usize> = K::LENGTH;
69

            
70
180
    fn as_ord_bytes(&'k self) -> Result<Cow<'k, [u8]>, Self::Error> {
71
180
        (*self).as_ord_bytes()
72
180
    }
73
}
74

            
75
/// The error types for [`Key::next_value()`].
76
#[derive(Clone, thiserror::Error, Debug, Serialize, Deserialize)]
77
pub enum NextValueError {
78
    /// The key type does not support this operation.
79
    #[error("the key type does not support automatic ids")]
80
    Unsupported,
81
    /// Generating a new value would wrap the underlying value.
82
    #[error("the key type has run out of unique values")]
83
    WouldWrap,
84
}
85

            
86
/// A type that can be used as a prefix range in range-based queries.
87
pub trait IntoPrefixRange: Sized {
88
    /// Returns the value as a prefix-range, which will match all values that
89
    /// start with `self`.
90
    fn into_prefix_range(self) -> Range<Self>;
91
}
92

            
93
20
fn next_byte_sequence(start: &[u8]) -> Option<Vec<u8>> {
94
20
    let mut end = start.to_vec();
95
    // Modify the last byte by adding one. If it would wrap, we proceed to the
96
    // next byte.
97
30
    while let Some(last_byte) = end.pop() {
98
20
        if let Some(next) = last_byte.checked_add(1) {
99
10
            end.push(next);
100
10
            return Some(end);
101
10
        }
102
    }
103

            
104
10
    None
105
20
}
106

            
107
impl<'k> Key<'k> for Cow<'k, [u8]> {
108
1
    fn from_ord_bytes(bytes: &[u8]) -> Result<Self, Self::Error> {
109
1
        Ok(Cow::Owned(bytes.to_vec()))
110
1
    }
111
}
112

            
113
impl<'k> KeyEncoding<'k, Self> for Cow<'k, [u8]> {
114
    type Error = Infallible;
115

            
116
    const LENGTH: Option<usize> = None;
117

            
118
1
    fn as_ord_bytes(&'k self) -> Result<Cow<'k, [u8]>, Self::Error> {
119
1
        Ok(self.clone())
120
1
    }
121
}
122

            
123
macro_rules! impl_u8_slice_key_encoding {
124
    ($type:ty) => {
125
        impl<'a, 'k> KeyEncoding<'k, $type> for &'a [u8] {
126
            type Error = Infallible;
127

            
128
            const LENGTH: Option<usize> = None;
129

            
130
            fn as_ord_bytes(&'k self) -> Result<Cow<'k, [u8]>, Self::Error> {
131
                Ok(Cow::Borrowed(self))
132
            }
133
        }
134
    };
135
}
136

            
137
impl_u8_slice_key_encoding!(Cow<'k, [u8]>);
138

            
139
impl<'k> IntoPrefixRange for Cow<'k, [u8]> {
140
    fn into_prefix_range(self) -> Range<Self> {
141
4
        if let Some(next) = next_byte_sequence(&self) {
142
2
            Range::from(self..Cow::Owned(next))
143
        } else {
144
2
            Range::from(self..)
145
        }
146
4
    }
147
}
148

            
149
1
#[test]
150
1
fn cow_prefix_range_tests() {
151
1
    use std::ops::RangeBounds;
152
1
    assert!(Cow::<'_, [u8]>::Borrowed(b"a")
153
1
        .into_prefix_range()
154
1
        .contains(&Cow::Borrowed(b"aa")));
155
1
    assert!(!Cow::<'_, [u8]>::Borrowed(b"a")
156
1
        .into_prefix_range()
157
1
        .contains(&Cow::Borrowed(b"b")));
158
1
    assert!(Cow::<'_, [u8]>::Borrowed(b"\xff")
159
1
        .into_prefix_range()
160
1
        .contains(&Cow::Borrowed(b"\xff\xff")));
161
1
    assert!(!Cow::<'_, [u8]>::Borrowed(b"\xff")
162
1
        .into_prefix_range()
163
1
        .contains(&Cow::Borrowed(b"\xfe")));
164
1
}
165

            
166
impl<'a> Key<'a> for Vec<u8> {
167
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
168
        Ok(bytes.to_vec())
169
    }
170
}
171

            
172
impl<'a> KeyEncoding<'a, Self> for Vec<u8> {
173
    type Error = Infallible;
174

            
175
    const LENGTH: Option<usize> = None;
176

            
177
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
178
        Ok(Cow::Borrowed(self))
179
    }
180
}
181

            
182
impl_u8_slice_key_encoding!(Vec<u8>);
183

            
184
impl<'k> IntoPrefixRange for Vec<u8> {
185
    fn into_prefix_range(self) -> Range<Self> {
186
4
        if let Some(next) = next_byte_sequence(&self) {
187
2
            Range::from(self..next)
188
        } else {
189
2
            Range::from(self..)
190
        }
191
4
    }
192
}
193

            
194
impl<'a, const N: usize> Key<'a> for [u8; N] {
195
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
196
        if bytes.len() == N {
197
            let mut array = [0; N];
198
            array.copy_from_slice(bytes);
199
            Ok(array)
200
        } else {
201
            Err(IncorrectByteLength)
202
        }
203
    }
204
}
205

            
206
impl<'a, const N: usize> KeyEncoding<'a, Self> for [u8; N] {
207
    type Error = IncorrectByteLength;
208

            
209
    const LENGTH: Option<usize> = Some(N);
210

            
211
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
212
        Ok(Cow::Borrowed(self))
213
    }
214
}
215

            
216
1
#[test]
217
1
fn vec_prefix_range_tests() {
218
1
    use std::ops::RangeBounds;
219
1
    assert!(b"a".to_vec().into_prefix_range().contains(&b"aa".to_vec()));
220
1
    assert!(!b"a".to_vec().into_prefix_range().contains(&b"b".to_vec()));
221
1
    assert!(b"\xff"
222
1
        .to_vec()
223
1
        .into_prefix_range()
224
1
        .contains(&b"\xff\xff".to_vec()));
225
1
    assert!(!b"\xff"
226
1
        .to_vec()
227
1
        .into_prefix_range()
228
1
        .contains(&b"\xfe".to_vec()));
229
1
}
230

            
231
impl<'a> Key<'a> for ArcBytes<'a> {
232
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
233
        Ok(Self::from(bytes))
234
    }
235
}
236

            
237
impl<'a> KeyEncoding<'a, Self> for ArcBytes<'a> {
238
    type Error = Infallible;
239

            
240
    const LENGTH: Option<usize> = None;
241

            
242
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
243
        Ok(Cow::Borrowed(self))
244
    }
245
}
246

            
247
impl_u8_slice_key_encoding!(ArcBytes<'k>);
248

            
249
impl<'k> IntoPrefixRange for ArcBytes<'k> {
250
    fn into_prefix_range(self) -> Range<Self> {
251
4
        if let Some(next) = next_byte_sequence(&self) {
252
2
            Range::from(self..Self::owned(next))
253
        } else {
254
2
            Range::from(self..)
255
        }
256
4
    }
257
}
258

            
259
1
#[test]
260
1
fn arcbytes_prefix_range_tests() {
261
1
    use std::ops::RangeBounds;
262
1
    assert!(ArcBytes::from(b"a")
263
1
        .into_prefix_range()
264
1
        .contains(&ArcBytes::from(b"aa")));
265
1
    assert!(!ArcBytes::from(b"a")
266
1
        .into_prefix_range()
267
1
        .contains(&ArcBytes::from(b"b")));
268
1
    assert!(ArcBytes::from(b"\xff")
269
1
        .into_prefix_range()
270
1
        .contains(&ArcBytes::from(b"\xff\xff")));
271
1
    assert!(!ArcBytes::from(b"\xff")
272
1
        .into_prefix_range()
273
1
        .contains(&ArcBytes::from(b"\xfe")));
274
1
}
275

            
276
impl<'a> Key<'a> for CowBytes<'a> {
277
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
278
        Ok(Self::from(bytes))
279
    }
280
}
281

            
282
impl<'a> KeyEncoding<'a, Self> for CowBytes<'a> {
283
    type Error = Infallible;
284

            
285
    const LENGTH: Option<usize> = None;
286

            
287
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
288
        Ok(self.0.clone())
289
    }
290
}
291

            
292
impl_u8_slice_key_encoding!(CowBytes<'k>);
293

            
294
impl<'k> IntoPrefixRange for CowBytes<'k> {
295
    fn into_prefix_range(self) -> Range<Self> {
296
4
        if let Some(next) = next_byte_sequence(&self) {
297
2
            Range::from(self..Self::from(next))
298
        } else {
299
2
            Range::from(self..)
300
        }
301
4
    }
302
}
303

            
304
1
#[test]
305
1
fn cowbytes_prefix_range_tests() {
306
1
    use std::ops::RangeBounds;
307
1
    assert!(CowBytes::from(&b"a"[..])
308
1
        .into_prefix_range()
309
1
        .contains(&CowBytes::from(&b"aa"[..])));
310
1
    assert!(!CowBytes::from(&b"a"[..])
311
1
        .into_prefix_range()
312
1
        .contains(&CowBytes::from(&b"b"[..])));
313
1
    assert!(CowBytes::from(&b"\xff"[..])
314
1
        .into_prefix_range()
315
1
        .contains(&CowBytes::from(&b"\xff\xff"[..])));
316
1
    assert!(!CowBytes::from(&b"\xff"[..])
317
1
        .into_prefix_range()
318
1
        .contains(&CowBytes::from(&b"\xfe"[..])));
319
1
}
320

            
321
impl<'a> Key<'a> for Bytes {
322
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
323
        Ok(Self::from(bytes))
324
    }
325
}
326

            
327
impl<'a> KeyEncoding<'a, Self> for Bytes {
328
    type Error = Infallible;
329

            
330
    const LENGTH: Option<usize> = None;
331

            
332
851756
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
333
851756
        Ok(Cow::Borrowed(self))
334
851756
    }
335
}
336

            
337
impl_u8_slice_key_encoding!(Bytes);
338

            
339
impl IntoPrefixRange for Bytes {
340
    fn into_prefix_range(self) -> Range<Self> {
341
4
        if let Some(next) = next_byte_sequence(&self) {
342
2
            Range::from(self..Self::from(next))
343
        } else {
344
2
            Range::from(self..)
345
        }
346
4
    }
347
}
348

            
349
1
#[test]
350
1
fn bytes_prefix_range_tests() {
351
1
    use std::ops::RangeBounds;
352
1
    assert!(Bytes::from(b"a".to_vec())
353
1
        .into_prefix_range()
354
1
        .contains(&Bytes::from(b"aa".to_vec())));
355
1
    assert!(!Bytes::from(b"a".to_vec())
356
1
        .into_prefix_range()
357
1
        .contains(&Bytes::from(b"b".to_vec())));
358
1
    assert!(Bytes::from(b"\xff".to_vec())
359
1
        .into_prefix_range()
360
1
        .contains(&Bytes::from(b"\xff\xff".to_vec())));
361
1
    assert!(!Bytes::from(b"\xff".to_vec())
362
1
        .into_prefix_range()
363
1
        .contains(&Bytes::from(b"\xfe".to_vec())));
364
1
}
365

            
366
impl<'a> Key<'a> for String {
367
406193
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
368
406193
        Self::from_utf8(bytes.to_vec())
369
406193
    }
370
}
371

            
372
impl<'a> KeyEncoding<'a, Self> for String {
373
    type Error = FromUtf8Error;
374

            
375
    const LENGTH: Option<usize> = None;
376

            
377
407093
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
378
407093
        Ok(Cow::Borrowed(self.as_bytes()))
379
407093
    }
380
}
381

            
382
impl<'a, 'k> KeyEncoding<'k, String> for &'a str {
383
    type Error = FromUtf8Error;
384

            
385
    const LENGTH: Option<usize> = None;
386

            
387
124
    fn as_ord_bytes(&'k self) -> Result<Cow<'k, [u8]>, Self::Error> {
388
124
        Ok(Cow::Borrowed(self.as_bytes()))
389
124
    }
390
}
391

            
392
impl IntoPrefixRange for String {
393
37
    fn into_prefix_range(self) -> Range<Self> {
394
37
        let mut bytes = self.as_bytes().to_vec();
395
37
        for (index, char) in self.char_indices().rev() {
396
37
            let mut next_char = u32::from(char) + 1;
397
37
            if next_char == 0xd800 {
398
                next_char = 0xE000;
399
37
            } else if next_char > u32::from(char::MAX) {
400
2
                continue;
401
35
            }
402

            
403
35
            let mut char_bytes = [0; 6];
404
35
            bytes.splice(
405
35
                index..,
406
35
                char::try_from(next_char)
407
35
                    .unwrap()
408
35
                    .encode_utf8(&mut char_bytes)
409
35
                    .bytes(),
410
35
            );
411
35
            return Range::from(self..Self::from_utf8(bytes).unwrap());
412
        }
413

            
414
2
        Range::from(self..)
415
37
    }
416
}
417

            
418
1
#[test]
419
1
fn string_prefix_range_tests() {
420
1
    use std::ops::RangeBounds;
421
1
    assert!(String::from("a")
422
1
        .into_prefix_range()
423
1
        .contains(&String::from("aa")));
424
1
    assert!(!String::from("a")
425
1
        .into_prefix_range()
426
1
        .contains(&String::from("b")));
427
1
    assert!(String::from("\u{d799}")
428
1
        .into_prefix_range()
429
1
        .contains(&String::from("\u{d799}a")));
430
1
    assert!(!String::from("\u{d799}")
431
1
        .into_prefix_range()
432
1
        .contains(&String::from("\u{e000}")));
433
1
    assert!(String::from("\u{10ffff}")
434
1
        .into_prefix_range()
435
1
        .contains(&String::from("\u{10ffff}a")));
436
1
    assert!(!String::from("\u{10ffff}")
437
1
        .into_prefix_range()
438
1
        .contains(&String::from("\u{10fffe}")));
439
1
}
440

            
441
impl<'a> Key<'a> for () {
442
94
    fn from_ord_bytes(_: &'a [u8]) -> Result<Self, Self::Error> {
443
94
        Ok(())
444
94
    }
445
}
446

            
447
impl<'a> KeyEncoding<'a, Self> for () {
448
    type Error = Infallible;
449

            
450
    const LENGTH: Option<usize> = Some(0);
451

            
452
63
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
453
63
        Ok(Cow::default())
454
63
    }
455
}
456

            
457
impl<'a> Key<'a> for bool {
458
2
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
459
2
        if bytes.is_empty() || bytes[0] == 0 {
460
1
            Ok(false)
461
        } else {
462
1
            Ok(true)
463
        }
464
2
    }
465
}
466

            
467
impl<'a> KeyEncoding<'a, Self> for bool {
468
    type Error = Infallible;
469

            
470
    const LENGTH: Option<usize> = Some(1);
471

            
472
2
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
473
2
        if *self {
474
1
            Ok(Cow::Borrowed(&[1_u8]))
475
        } else {
476
1
            Ok(Cow::Borrowed(&[0_u8]))
477
        }
478
2
    }
479
}
480

            
481
macro_rules! impl_key_for_tuple {
482
    ($(($index:tt, $varname:ident, $generic:ident)),+) => {
483
        impl<'a, $($generic),+> Key<'a> for ($($generic),+)
484
        where
485
            $($generic: Key<'a>),+
486
        {
487
511
            fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
488
511
                $(let ($varname, bytes) = decode_composite_field::<$generic>(bytes)?;)+
489

            
490
511
                if bytes.is_empty() {
491
511
                    Ok(($($varname),+))
492
                } else {
493
                    Err(CompositeKeyError::new(std::io::Error::from(
494
                        ErrorKind::InvalidData,
495
                    )))
496
                }
497
511
            }
498
        }
499

            
500
        impl<'a, $($generic),+> KeyEncoding<'a, Self> for ($($generic),+)
501
        where
502
            $($generic: Key<'a>),+
503
        {
504
            type Error = CompositeKeyError;
505

            
506
            const LENGTH: Option<usize> = match ($($generic::LENGTH),+) {
507
                ($(Some($varname)),+) => Some($($varname +)+ 0),
508
                _ => None,
509
            };
510

            
511
510
            fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
512
510
                let mut bytes = Vec::new();
513
510

            
514
510
                $(encode_composite_field(&self.$index, &mut bytes)?;)+
515

            
516
510
                Ok(Cow::Owned(bytes))
517
510
            }
518
        }
519
    };
520
}
521

            
522
impl_key_for_tuple!((0, t1, T1), (1, t2, T2));
523
impl_key_for_tuple!((0, t1, T1), (1, t2, T2), (2, t3, T3));
524
impl_key_for_tuple!((0, t1, T1), (1, t2, T2), (2, t3, T3), (3, t4, T4));
525
impl_key_for_tuple!(
526
    (0, t1, T1),
527
    (1, t2, T2),
528
    (2, t3, T3),
529
    (3, t4, T4),
530
    (4, t5, T5)
531
);
532
impl_key_for_tuple!(
533
    (0, t1, T1),
534
    (1, t2, T2),
535
    (2, t3, T3),
536
    (3, t4, T4),
537
    (4, t5, T5),
538
    (5, t6, T6)
539
);
540
impl_key_for_tuple!(
541
    (0, t1, T1),
542
    (1, t2, T2),
543
    (2, t3, T3),
544
    (3, t4, T4),
545
    (4, t5, T5),
546
    (5, t6, T6),
547
    (6, t7, T7)
548
);
549
impl_key_for_tuple!(
550
    (0, t1, T1),
551
    (1, t2, T2),
552
    (2, t3, T3),
553
    (3, t4, T4),
554
    (4, t5, T5),
555
    (5, t6, T6),
556
    (6, t7, T7),
557
    (7, t8, T8)
558
);
559

            
560
/// Encodes a value using the `Key` trait in such a way that multiple values can
561
/// still be ordered at the byte level when chained together.
562
///
563
/// ```rust
564
/// # use bonsaidb_core::key::{encode_composite_field, decode_composite_field};
565
///
566
/// let value1 = String::from("hello");
567
/// let value2 = 42_u32;
568
/// let mut key_bytes = Vec::new();
569
/// encode_composite_field(&value1, &mut key_bytes).unwrap();
570
/// encode_composite_field(&value2, &mut key_bytes).unwrap();
571
///
572
/// let (decoded_string, remaining_bytes) = decode_composite_field::<String>(&key_bytes).unwrap();
573
/// assert_eq!(decoded_string, value1);
574
/// let (decoded_u32, remaining_bytes) = decode_composite_field::<u32>(&remaining_bytes).unwrap();
575
/// assert_eq!(decoded_u32, value2);
576
/// assert!(remaining_bytes.is_empty());
577
/// ```
578
3588
pub fn encode_composite_field<'a, T: Key<'a>, Bytes: Write>(
579
3588
    value: &'a T,
580
3588
    bytes: &mut Bytes,
581
3588
) -> Result<(), CompositeKeyError> {
582
3588
    let t2 = T::as_ord_bytes(value).map_err(CompositeKeyError::new)?;
583
3588
    if T::LENGTH.is_none() {
584
3584
        (t2.len() as u64)
585
3584
            .encode_variable(bytes)
586
3584
            .map_err(CompositeKeyError::new)?;
587
4
    }
588
3588
    bytes.write_all(&t2)?;
589
3588
    Ok(())
590
3588
}
591

            
592
/// Decodes a value previously encoded using [`encode_composite_field()`].
593
/// The result is a tuple with the first element being the decoded value, and
594
/// the second element is the remainig byte slice.
595
///
596
/// ```rust
597
/// # use bonsaidb_core::key::{encode_composite_field, decode_composite_field};
598
///
599
/// let value1 = String::from("hello");
600
/// let value2 = 42_u32;
601
/// let mut key_bytes = Vec::new();
602
/// encode_composite_field(&value1, &mut key_bytes).unwrap();
603
/// encode_composite_field(&value2, &mut key_bytes).unwrap();
604
///
605
/// let (decoded_string, remaining_bytes) = decode_composite_field::<String>(&key_bytes).unwrap();
606
/// assert_eq!(decoded_string, value1);
607
/// let (decoded_u32, remaining_bytes) = decode_composite_field::<u32>(&remaining_bytes).unwrap();
608
/// assert_eq!(decoded_u32, value2);
609
/// assert!(remaining_bytes.is_empty());
610
/// ```
611
3590
pub fn decode_composite_field<'a, T: Key<'a>>(
612
3590
    mut bytes: &'a [u8],
613
3590
) -> Result<(T, &[u8]), CompositeKeyError> {
614
3590
    let length = if let Some(length) = T::LENGTH {
615
6
        length
616
    } else {
617
3584
        usize::try_from(u64::decode_variable(&mut bytes)?)?
618
    };
619
3590
    let (t2, remaining) = bytes.split_at(length);
620
3590
    Ok((
621
3590
        T::from_ord_bytes(t2).map_err(CompositeKeyError::new)?,
622
3590
        remaining,
623
    ))
624
3590
}
625

            
626
1
#[test]
627
#[allow(clippy::too_many_lines, clippy::cognitive_complexity)] // couldn't figure out how to macro-ize it
628
1
fn composite_key_tests() {
629
7
    fn roundtrip<T: for<'a> Key<'a> + Ord + Eq + std::fmt::Debug>(mut cases: Vec<T>) {
630
7
        let mut encoded = {
631
7
            cases
632
7
                .iter()
633
508
                .map(|tuple| tuple.as_ord_bytes().unwrap().to_vec())
634
7
                .collect::<Vec<Vec<u8>>>()
635
7
        };
636
7
        cases.sort();
637
7
        encoded.sort();
638
7
        let decoded = encoded
639
7
            .iter()
640
508
            .map(|encoded| T::from_ord_bytes(encoded).unwrap())
641
7
            .collect::<Vec<_>>();
642
7
        assert_eq!(cases, decoded);
643
7
    }
644
1

            
645
1
    let values = [Unsigned::from(0_u8), Unsigned::from(16_u8)];
646
1
    let mut cases = Vec::new();
647
3
    for t1 in values {
648
6
        for t2 in values {
649
4
            cases.push((t1, t2));
650
4
        }
651
    }
652
1
    roundtrip(cases);
653
1

            
654
1
    let mut cases = Vec::new();
655
3
    for t1 in values {
656
6
        for t2 in values {
657
12
            for t3 in values {
658
8
                cases.push((t1, t2, t3));
659
8
            }
660
        }
661
    }
662
1
    roundtrip(cases);
663
1

            
664
1
    let mut cases = Vec::new();
665
3
    for t1 in values {
666
6
        for t2 in values {
667
12
            for t3 in values {
668
24
                for t4 in values {
669
16
                    cases.push((t1, t2, t3, t4));
670
16
                }
671
            }
672
        }
673
    }
674
1
    roundtrip(cases);
675
1

            
676
1
    let mut cases = Vec::new();
677
3
    for t1 in values {
678
6
        for t2 in values {
679
12
            for t3 in values {
680
24
                for t4 in values {
681
48
                    for t5 in values {
682
32
                        cases.push((t1, t2, t3, t4, t5));
683
32
                    }
684
                }
685
            }
686
        }
687
    }
688
1
    roundtrip(cases);
689
1

            
690
1
    let mut cases = Vec::new();
691
3
    for t1 in values {
692
6
        for t2 in values {
693
12
            for t3 in values {
694
24
                for t4 in values {
695
48
                    for t5 in values {
696
96
                        for t6 in values {
697
64
                            cases.push((t1, t2, t3, t4, t5, t6));
698
64
                        }
699
                    }
700
                }
701
            }
702
        }
703
    }
704
1
    roundtrip(cases);
705
1

            
706
1
    let mut cases = Vec::new();
707
3
    for t1 in values {
708
6
        for t2 in values {
709
12
            for t3 in values {
710
24
                for t4 in values {
711
48
                    for t5 in values {
712
96
                        for t6 in values {
713
192
                            for t7 in values {
714
128
                                cases.push((t1, t2, t3, t4, t5, t6, t7));
715
128
                            }
716
                        }
717
                    }
718
                }
719
            }
720
        }
721
    }
722
1
    roundtrip(cases);
723
1

            
724
1
    let mut cases = Vec::new();
725
3
    for t1 in values {
726
6
        for t2 in values {
727
12
            for t3 in values {
728
24
                for t4 in values {
729
48
                    for t5 in values {
730
96
                        for t6 in values {
731
192
                            for t7 in values {
732
384
                                for t8 in values {
733
256
                                    cases.push((t1, t2, t3, t4, t5, t6, t7, t8));
734
256
                                }
735
                            }
736
                        }
737
                    }
738
                }
739
            }
740
        }
741
    }
742
1
    roundtrip(cases);
743
1
}
744

            
745
/// An error occurred inside of one of the composite key fields.
746
#[derive(thiserror::Error, Debug)]
747
#[error("key error: {0}")]
748
pub struct CompositeKeyError(Box<dyn AnyError>);
749

            
750
impl CompositeKeyError {
751
    pub(crate) fn new<E: AnyError>(error: E) -> Self {
752
        Self(Box::new(error))
753
    }
754
}
755

            
756
impl From<TryFromIntError> for CompositeKeyError {
757
    fn from(err: TryFromIntError) -> Self {
758
        Self::new(err)
759
    }
760
}
761

            
762
impl From<std::io::Error> for CompositeKeyError {
763
    fn from(err: std::io::Error) -> Self {
764
        Self::new(err)
765
    }
766
}
767

            
768
impl<'a> Key<'a> for Signed {
769
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
770
        Self::decode_variable(bytes)
771
    }
772

            
773
    fn first_value() -> Result<Self, NextValueError> {
774
        Ok(Self::from(0_i128))
775
    }
776

            
777
    fn next_value(&self) -> Result<Self, NextValueError> {
778
        i128::try_from(*self)
779
            .ok()
780
            .and_then(|key| key.checked_add(1))
781
            .map(Self::from)
782
            .ok_or(NextValueError::WouldWrap)
783
    }
784
}
785

            
786
impl<'a> KeyEncoding<'a, Self> for Signed {
787
    type Error = std::io::Error;
788

            
789
    const LENGTH: Option<usize> = None;
790

            
791
    fn as_ord_bytes(&self) -> Result<Cow<'a, [u8]>, Self::Error> {
792
        self.to_variable_vec().map(Cow::Owned)
793
    }
794
}
795

            
796
impl<'a> Key<'a> for Unsigned {
797
3584
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
798
3584
        Self::decode_variable(bytes)
799
3584
    }
800

            
801
    fn first_value() -> Result<Self, NextValueError> {
802
        Ok(Self::from(0_u128))
803
    }
804

            
805
    fn next_value(&self) -> Result<Self, NextValueError> {
806
        u128::try_from(*self)
807
            .ok()
808
            .and_then(|key| key.checked_add(1))
809
            .map(Self::from)
810
            .ok_or(NextValueError::WouldWrap)
811
    }
812
}
813

            
814
impl<'a> KeyEncoding<'a, Self> for Unsigned {
815
    type Error = std::io::Error;
816

            
817
    const LENGTH: Option<usize> = None;
818

            
819
3584
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
820
3584
        self.to_variable_vec().map(Cow::Owned)
821
3584
    }
822
}
823

            
824
#[cfg(feature = "uuid")]
825
impl<'k> Key<'k> for uuid::Uuid {
826
    fn from_ord_bytes(bytes: &'k [u8]) -> Result<Self, Self::Error> {
827
        Ok(Self::from_bytes(bytes.try_into()?))
828
    }
829
}
830

            
831
#[cfg(feature = "uuid")]
832
impl<'k> KeyEncoding<'k, Self> for uuid::Uuid {
833
    type Error = std::array::TryFromSliceError;
834

            
835
    const LENGTH: Option<usize> = Some(16);
836

            
837
    fn as_ord_bytes(&'k self) -> Result<Cow<'k, [u8]>, Self::Error> {
838
        Ok(Cow::Borrowed(self.as_bytes()))
839
    }
840
}
841

            
842
impl<'a, T> Key<'a> for Option<T>
843
where
844
    T: Key<'a>,
845
    Self: KeyEncoding<'a, Self, Error = <T as KeyEncoding<'a, T>>::Error>,
846
{
847
8752
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
848
8752
        if bytes.is_empty() {
849
2976
            Ok(None)
850
        } else {
851
5776
            Ok(Some(T::from_ord_bytes(bytes)?))
852
        }
853
8752
    }
854

            
855
    fn first_value() -> Result<Self, NextValueError> {
856
        Ok(Some(T::first_value()?))
857
    }
858

            
859
    fn next_value(&self) -> Result<Self, NextValueError> {
860
        self.as_ref().map(T::next_value).transpose()
861
    }
862
}
863

            
864
impl<'a, K, T> KeyEncoding<'a, Option<K>> for Option<T>
865
where
866
    T: KeyEncoding<'a, K>,
867
    K: for<'k> Key<'k>,
868
{
869
    type Error = T::Error;
870

            
871
    const LENGTH: Option<usize> = T::LENGTH;
872

            
873
    /// # Panics
874
    ///
875
    /// Panics if `T::into_big_endian_bytes` returns an empty `IVec`.
876
    // TODO consider removing this panic limitation by adding a single byte to
877
    // each key (at the end preferrably) so that we can distinguish between None
878
    // and a 0-byte type
879
8256
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
880
8256
        if let Some(contents) = self {
881
6767
            let contents = contents.as_ord_bytes()?;
882
6767
            assert!(!contents.is_empty());
883
6767
            Ok(contents)
884
        } else {
885
1489
            Ok(Cow::default())
886
        }
887
8256
    }
888
}
889

            
890
/// Adds `Key` support to an enum. Requires implementing
891
/// [`ToPrimitive`](num_traits::ToPrimitive) and
892
/// [`FromPrimitive`](num_traits::FromPrimitive), or using a crate like
893
/// [num-derive](https://crates.io/crates/num-derive) to do it automatically.
894
/// Take care when using enums as keys: if the order changes or if the meaning
895
/// of existing numerical values changes, make sure to update any related views'
896
/// version number to ensure the values are re-evaluated.
897
pub trait EnumKey: ToPrimitive + FromPrimitive + Clone + std::fmt::Debug + Send + Sync {}
898

            
899
/// An error that indicates an unexpected number of bytes were present.
900
#[derive(thiserror::Error, Debug)]
901
#[error("incorrect byte length")]
902
pub struct IncorrectByteLength;
903

            
904
/// An error that indicates an unexpected enum variant value was found.
905
#[derive(thiserror::Error, Debug)]
906
#[error("unknown enum variant")]
907
pub struct UnknownEnumVariant;
908

            
909
impl From<std::array::TryFromSliceError> for IncorrectByteLength {
910
    fn from(_: std::array::TryFromSliceError) -> Self {
911
        Self
912
    }
913
}
914

            
915
// ANCHOR: impl_key_for_enumkey
916
impl<'a, T> Key<'a> for T
917
where
918
    T: EnumKey,
919
{
920
2
    fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
921
2
        let primitive = u64::decode_variable(bytes)?;
922
2
        Self::from_u64(primitive)
923
2
            .ok_or_else(|| std::io::Error::new(ErrorKind::InvalidData, UnknownEnumVariant))
924
2
    }
925
}
926

            
927
impl<'a, T> KeyEncoding<'a, Self> for T
928
where
929
    T: EnumKey,
930
{
931
    type Error = std::io::Error;
932
    const LENGTH: Option<usize> = None;
933

            
934
4
    fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
935
4
        let integer = self
936
4
            .to_u64()
937
4
            .map(Unsigned::from)
938
4
            .ok_or_else(|| std::io::Error::new(ErrorKind::InvalidData, IncorrectByteLength))?;
939
4
        Ok(Cow::Owned(integer.to_variable_vec()?))
940
4
    }
941
}
942
// ANCHOR_END: impl_key_for_enumkey
943

            
944
macro_rules! impl_key_for_primitive {
945
    ($type:ident) => {
946
        impl<'a> Key<'a> for $type {
947
2010714
            fn from_ord_bytes(bytes: &'a [u8]) -> Result<Self, Self::Error> {
948
2010714
                Ok($type::from_be_bytes(bytes.try_into()?))
949
2010714
            }
950

            
951
30597
            fn first_value() -> Result<Self, NextValueError> {
952
30597
                Ok(0)
953
30597
            }
954

            
955
442773
            fn next_value(&self) -> Result<Self, NextValueError> {
956
442773
                self.checked_add(1).ok_or(NextValueError::WouldWrap)
957
442773
            }
958
        }
959
        impl<'a> KeyEncoding<'a, Self> for $type {
960
            type Error = IncorrectByteLength;
961
            const LENGTH: Option<usize> = Some(std::mem::size_of::<$type>());
962

            
963
2038067
            fn as_ord_bytes(&'a self) -> Result<Cow<'a, [u8]>, Self::Error> {
964
2038067
                Ok(Cow::from(self.to_be_bytes().to_vec()))
965
2038067
            }
966
        }
967
    };
968
}
969

            
970
impl_key_for_primitive!(i8);
971
impl_key_for_primitive!(u8);
972
impl_key_for_primitive!(i16);
973
impl_key_for_primitive!(u16);
974
impl_key_for_primitive!(i32);
975
impl_key_for_primitive!(u32);
976
impl_key_for_primitive!(i64);
977
impl_key_for_primitive!(u64);
978
impl_key_for_primitive!(i128);
979
impl_key_for_primitive!(u128);
980

            
981
1
#[test]
982
#[allow(clippy::cognitive_complexity)] // I disagree - @ecton
983
1
fn primitive_key_encoding_tests() -> anyhow::Result<()> {
984
1
    macro_rules! test_primitive_extremes {
985
1
        ($type:ident) => {
986
1
            assert_eq!(
987
1
                &$type::MAX.to_be_bytes(),
988
1
                $type::MAX.as_ord_bytes()?.as_ref()
989
1
            );
990
1
            assert_eq!(
991
1
                $type::MAX,
992
1
                $type::from_ord_bytes(&$type::MAX.as_ord_bytes()?)?
993
1
            );
994
1
            assert_eq!(
995
1
                $type::MIN,
996
1
                $type::from_ord_bytes(&$type::MIN.as_ord_bytes()?)?
997
1
            );
998
1
        };
999
1
    }
1

            
1
    test_primitive_extremes!(i8);
1
    test_primitive_extremes!(u8);
1
    test_primitive_extremes!(i16);
1
    test_primitive_extremes!(u16);
1
    test_primitive_extremes!(i32);
1
    test_primitive_extremes!(u32);
1
    test_primitive_extremes!(i64);
1
    test_primitive_extremes!(u64);
1
    test_primitive_extremes!(i128);
1
    test_primitive_extremes!(u128);

            
1
    Ok(())
1
}

            
1
#[test]
1
fn optional_key_encoding_tests() -> anyhow::Result<()> {
1
    assert!(Option::<i8>::None.as_ord_bytes()?.is_empty());
1
    assert_eq!(
1
        Some(1_i8),
1
        Option::from_ord_bytes(&Some(1_i8).as_ord_bytes()?)?
    );
1
    Ok(())
1
}

            
1
#[test]
#[allow(clippy::unit_cmp)] // this is more of a compilation test
1
fn unit_key_encoding_tests() -> anyhow::Result<()> {
1
    assert!(().as_ord_bytes()?.is_empty());
1
    assert_eq!((), <() as Key>::from_ord_bytes(&[])?);
1
    Ok(())
1
}

            
1
#[test]
#[allow(clippy::unit_cmp)] // this is more of a compilation test
1
fn bool_key_encoding_tests() -> anyhow::Result<()> {
1
    let true_as_bytes = true.as_ord_bytes()?;
1
    let false_as_bytes = false.as_ord_bytes()?;
1
    assert!(bool::from_ord_bytes(&true_as_bytes)?);
1
    assert!(!bool::from_ord_bytes(&false_as_bytes)?);
1
    Ok(())
1
}

            
1
#[test]
1
fn vec_key_encoding_tests() -> anyhow::Result<()> {
1
    const ORIGINAL_VALUE: &[u8] = b"bonsaidb";
1
    let vec = Cow::<'_, [u8]>::from(ORIGINAL_VALUE);
1
    assert_eq!(vec.clone(), Cow::from_ord_bytes(&vec.as_ord_bytes()?)?);
1
    Ok(())
1
}

            
1
#[test]
#[allow(clippy::use_self)] // Weird interaction with num_derive
1
fn enum_derive_tests() -> anyhow::Result<()> {
4
    #[derive(Debug, Clone, num_derive::ToPrimitive, num_derive::FromPrimitive)]
    enum SomeEnum {
        One = 1,
        NineNineNine = 999,
    }

            
    impl EnumKey for SomeEnum {}

            
1
    let encoded = SomeEnum::One.as_ord_bytes()?;
1
    let value = SomeEnum::from_ord_bytes(&encoded)?;
1
    assert!(matches!(value, SomeEnum::One));

            
1
    let encoded = SomeEnum::NineNineNine.as_ord_bytes()?;
1
    let value = SomeEnum::from_ord_bytes(&encoded)?;
1
    assert!(matches!(value, SomeEnum::NineNineNine));

            
1
    Ok(())
1
}