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

            
5
mod deprecated;
6

            
7
use std::borrow::{Borrow, Cow};
8
use std::collections::HashMap;
9
use std::convert::Infallible;
10
use std::io::{self, ErrorKind};
11
use std::num::{
12
    NonZeroI128, NonZeroI16, NonZeroI32, NonZeroI64, NonZeroI8, NonZeroIsize, NonZeroU128,
13
    NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU8, NonZeroUsize, TryFromIntError,
14
};
15
use std::ops::Deref;
16
use std::string::FromUtf8Error;
17

            
18
use arc_bytes::serde::{Bytes, CowBytes};
19
use arc_bytes::ArcBytes;
20
pub use bonsaidb_macros::Key;
21
pub use deprecated::*;
22
use num_traits::{FromPrimitive, ToPrimitive};
23
use ordered_varint::{Signed, Unsigned, Variable};
24
use serde::{Deserialize, Serialize};
25
use transmog::BorrowedDeserializer;
26
pub use varint::{VarInt, VariableInteger};
27

            
28
use crate::connection::{Bound, BoundRef, MaybeOwned, RangeRef};
29
use crate::AnyError;
30

            
31
/// A trait that enables a type to convert itself into a `memcmp`-compatible
32
/// sequence of bytes.
33
pub trait KeyEncoding<K = Self>: Send + Sync {
34
    /// The error type that can be produced by either serialization or
35
    /// deserialization.
36
    type Error: AnyError;
37

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

            
42
    /// Describes this type by invoking functions on `visitor` describing the
43
    /// key being encoded.
44
    ///
45
    /// See the [`KeyVisitor`] trait for more information.
46
    ///
47
    /// [`KeyDescription::for_key()`]/[`KeyDescription::for_encoding()`] are
48
    /// built-in functions
49
    fn describe<Visitor>(visitor: &mut Visitor)
50
    where
51
        Visitor: KeyVisitor;
52

            
53
    /// Convert `self` into a `Cow<'_, [u8]>` containing bytes that are able to be
54
    /// compared via `memcmp` in a way that is comptaible with its own Ord
55
    /// implementation.
56
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error>;
57
}
58

            
59
/// A trait that enables a type to convert itself into a `memcmp`-compatible
60
/// sequence of bytes.
61
///
62
/// # Deriving this trait
63
///
64
/// This trait can be derived on structs and enums whose members all implement
65
/// `Key`. It is important to note that the order of individual fields and enum
66
/// variants is important, so special care must be taken when updating enums and
67
/// structs when trying to preserve backwards compatibility with existing data.
68
///
69
/// ```rust
70
/// use bonsaidb_core::key::Key;
71
///
72
/// #[derive(Key, Clone, Debug)]
73
/// # #[key(core = bonsaidb_core)]
74
/// struct CompositeKey {
75
///     user_id: u64,
76
///     task_id: u32,
77
/// }
78
/// ```
79
///
80
/// Each field or enum variant is encoded and decoded in the order in which it
81
/// appears in the source code. The implementation uses [`CompositeKeyEncoder`]
82
/// and [`CompositeKeyDecoder`] to encode each field.
83
///
84
/// ## Changing the `enum` representation type
85
///
86
/// By default, the derived `Key` implementation will use an `isize` for its
87
/// representation, which is encoded using [`ordered_varint`]. If you wish to
88
/// use a fixed-size encoding or use `usize`, `enum_repr` can be used to control
89
/// the type being encoded.
90
///
91
/// The default behavior produces compact output for simple enums, but can also
92
/// support growing to the limits of `isize`:
93
///
94
/// ```rust
95
/// use bonsaidb_core::key::{Key, KeyEncoding};
96
///
97
/// #[derive(Key, Clone, Debug)]
98
/// # #[key(core = bonsaidb_core)]
99
/// enum Color {
100
///     Red,
101
///     Green,
102
///     Blue,
103
/// }
104
///
105
/// let encoded = Color::Red.as_ord_bytes().unwrap();
106
/// assert_eq!(encoded.len(), 1);
107
/// ```
108
///
109
/// If a `#[repr(...)]` attribute exists and its parameter is a built-in integer
110
/// type, the `Key` derive will use that type for its representation instead:
111
///
112
/// ```rust
113
/// use bonsaidb_core::key::{Key, KeyEncoding};
114
///
115
/// #[derive(Key, Clone, Debug)]
116
/// # #[key(core = bonsaidb_core)]
117
/// #[repr(u32)]
118
/// enum Color {
119
///     Red = 0xFF0000FF,
120
///     Green = 0x00FF00FF,
121
///     Blue = 0x0000FFFF,
122
/// }
123
///
124
/// let encoded = Color::Red.as_ord_bytes().unwrap();
125
/// assert_eq!(encoded.len(), 4);
126
/// ```
127
///
128
/// If the type would rather use a different type for the key encoding than it
129
/// uses for in-memory representation, the `enum_repr` parameter can be used:
130
///
131
/// ```rust
132
/// use bonsaidb_core::key::{Key, KeyEncoding};
133
///
134
/// #[derive(Key, Clone, Debug)]
135
/// # #[key(core = bonsaidb_core)]
136
/// #[key(enum_repr = u32)]
137
/// #[repr(usize)]
138
/// enum Color {
139
///     Red = 0xFF0000FF,
140
///     Green = 0x00FF00FF,
141
///     Blue = 0x0000FFFF,
142
/// }
143
///
144
/// let encoded = Color::Red.as_ord_bytes().unwrap();
145
/// assert_eq!(encoded.len(), 4);
146
/// ```
147
///
148
/// ## `null_handling`
149
///
150
/// The derive macro offers an argument `null_handling`, which defaults to
151
/// `escape`. Escaping null bytes in variable length fields ensures all data
152
/// encoded will sort correctly. In situations where speed is more important
153
/// than sorting behavior, `allow` or `deny` can be specified. `allow` will
154
/// permit null bytes to pass through encoding and decoding without being
155
/// checked. `deny` will check for null bytes when encoding and return an error
156
/// if any are present.
157
///
158
/// Null bytes can cause problematic sort behavior when multiple variable-length
159
/// encoded fields are encoded as a composite key. Consider this example:
160
///
161
/// ```rust
162
/// use bonsaidb_core::key::Key;
163
///
164
/// #[derive(Key, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
165
/// #[key(null_handling = allow)]
166
/// # #[key(core = bonsaidb_core)]
167
/// struct CompositeKey {
168
///     a: String,
169
///     b: String,
170
/// }
171
/// ```
172
///
173
/// With this structure, we can cause sorting misbehaviors using this data set:
174
///
175
/// | `a`      | `b`   | Encoded Bytes         |
176
/// |----------|-------|-----------------------|
177
/// | `"a"`    | `"c"` | `6100 6300 0101`      |
178
/// | `"a\0b"` | `"a"` | `6100 6200 610003 01` |
179
/// | `"b"`    | `"a"` | `6200 6100 0101`      |
180
///
181
/// In this table, `a` and `b` are ordered as `CompositeKey` would be ordered
182
/// when compared using `Ord`. However, the order of the encoded bytes does not
183
/// match.
184
///
185
/// This null-byte edge case only applies to variable length [`Key`]s
186
/// ([`KeyEncoding::LENGTH`] is `None`).
187
pub trait Key<'k>: KeyEncoding<Self> + Clone + Send + Sync {
188
    /// If true, this type can benefit from an owned `Vec<u8>`. This flag is
189
    /// used as a hint of whether to attempt to do memcpy operations in some
190
    /// decoding operations to avoid extra allocations.
191
    const CAN_OWN_BYTES: bool;
192

            
193
    /// Deserialize a sequence of bytes previously encoded with
194
    /// [`KeyEncoding::as_ord_bytes`].
195
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error>;
196

            
197
    /// Return the first value in sequence for this type. Not all types
198
    /// implement this.
199
    fn first_value() -> Result<Self, NextValueError> {
200
        Err(NextValueError::Unsupported)
201
    }
202

            
203
    /// Return the next value in sequence for this type. Not all types implement
204
    /// this. Instead of wrapping/overflowing, None should be returned.
205
1
    fn next_value(&self) -> Result<Self, NextValueError> {
206
1
        Err(NextValueError::Unsupported)
207
1
    }
208
}
209

            
210
impl<'a, 'k, K, KE> KeyEncoding<K> for &'a KE
211
where
212
    KE: KeyEncoding<K> + ?Sized + PartialEq,
213
    K: Key<'k> + PartialEq<KE>,
214
{
215
    type Error = KE::Error;
216

            
217
    const LENGTH: Option<usize> = K::LENGTH;
218

            
219
    fn describe<Visitor>(visitor: &mut Visitor)
220
    where
221
        Visitor: KeyVisitor,
222
    {
223
        KE::describe(visitor);
224
    }
225

            
226
337
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
227
337
        (*self).as_ord_bytes()
228
337
    }
229
}
230

            
231
/// A Visitor for information about a [`KeyEncoding`].
232
///
233
/// This trait is used in [`KeyEncoding::describe`] to report information about
234
/// the type of data contained within the key. Using this information,
235
/// generically interpreting the bytes of a key type can be possible as long as
236
/// the key type uses [`CompositeKeyEncoder`].
237
///
238
/// This trait is not something that most users will ever need to implement.
239
/// Instead,
240
/// [`KeyDescription::for_key()`]/[`KeyDescription::for_encoding()`] are
241
/// built-in functions to retrieve the information reported by this trait in an
242
/// easier-to-use interface.
243
pub trait KeyVisitor {
244
    /// Report that a basic key type is encoded next in this key.
245
    fn visit_type(&mut self, kind: KeyKind);
246

            
247
    /// Report that a composite type made up of `count` fields is encoded next in
248
    /// this key.
249
    ///
250
    /// `KeyVisitor` implementations may panic if there are less than or more
251
    /// than `count` fields reported by either `visit_type()` or
252
    /// `visit_composite()`.
253
    fn visit_composite(&mut self, kind: CompositeKind, count: usize);
254

            
255
    /// Report that the current composite type has extra metadata.
256
    ///
257
    /// This can be used to encode const generic parameters that are helpful in
258
    /// interpretting the contents of a type. For example,
259
    /// [`LimitedResolutionTimestamp`](time::limited::LimitedResolutionTimestamp)
260
    /// uses this function to report the `TimeEpoch`'s nanoseconds since the
261
    /// Unix epoch.
262
    fn visit_composite_attribute(
263
        &mut self,
264
        key: impl Into<Cow<'static, str>>,
265
        value: impl Into<KeyAttibuteValue>,
266
    );
267
}
268

            
269
/// The type of a single field contained in a key.
270
4505
#[derive(Debug, Eq, PartialEq, Clone, Serialize, Deserialize)]
271
pub enum KeyKind {
272
    /// An `unit` type, encoded with no length.
273
    Unit,
274
    /// An `u8` encoded in big-endian encoding.
275
    U8,
276
    /// An `u16` encoded in big-endian encoding.
277
    U16,
278
    /// An `u32` encoded in big-endian encoding.
279
    U32,
280
    /// An `u64` encoded in big-endian encoding.
281
    U64,
282
    /// An `u128` encoded in big-endian encoding.
283
    U128,
284
    /// An `usize` encoded in big-endian encoding.
285
    Usize,
286
    /// An `i8` encoded in big-endian encoding.
287
    I8,
288
    /// An `i16` encoded in big-endian encoding.
289
    I16,
290
    /// An `i32` encoded in big-endian encoding.
291
    I32,
292
    /// An `i64` encoded in big-endian encoding.
293
    I64,
294
    /// An `i128` encoded in big-endian encoding.
295
    I128,
296
    /// An `isize` encoded in big-endian encoding.
297
    Isize,
298
    /// A [`Signed`] number encoded using [`ordered_varint`].
299
    Signed,
300
    /// An [`Unsigned`] number encoded using [`ordered_varint`].
301
    Unsigned,
302
    /// A `bool` encoded as a single byte.
303
    Bool,
304
    /// A String encoded using BonsaiDb's built-in `KeyEncoding`.
305
    String,
306
    /// A byte array encoded using BonsaiDb's built-in `KeyEncoding`.
307
    Bytes,
308
}
309

            
310
/// A value used as part of [`KeyVisitor::visit_composite_attribute`].
311
1
#[derive(Debug, Eq, PartialEq, Clone, Serialize, Deserialize)]
312
pub enum KeyAttibuteValue {
313
    /// An `u8` value.
314
    U8(u8),
315
    /// An `i8` value.
316
    I8(i8),
317
    /// An `u16` value.
318
    U16(u16),
319
    /// An `i16` value.
320
    I16(i16),
321
    /// An `u32` value.
322
    U32(u32),
323
    /// An `i32` value.
324
    I32(i32),
325
    /// An `u64` value.
326
    U64(u64),
327
    /// An `i64` value.
328
    I64(i64),
329
    /// An `u128` value.
330
    U128(u128),
331
    /// An `i128` value.
332
    I128(i128),
333
    /// An `usize` value.
334
    Usize(usize),
335
    /// An `isize` value.
336
    Isize(isize),
337
    /// A `bool` value.
338
    Bool(bool),
339
    /// A string value.
340
    Str(Cow<'static, str>),
341
    /// A byte array value.
342
    Bytes(Cow<'static, [u8]>),
343
}
344

            
345
macro_rules! impl_const_key_from {
346
    ($from:ty, $constkey:expr) => {
347
        impl From<$from> for KeyAttibuteValue {
348
1
            fn from(value: $from) -> Self {
349
1
                #[allow(clippy::redundant_closure_call)]
350
1
                $constkey(value)
351
1
            }
352
        }
353
    };
354
}
355

            
356
impl_const_key_from!(u8, KeyAttibuteValue::U8);
357
impl_const_key_from!(i8, KeyAttibuteValue::I8);
358
impl_const_key_from!(u16, KeyAttibuteValue::U16);
359
impl_const_key_from!(i16, KeyAttibuteValue::I16);
360
impl_const_key_from!(u32, KeyAttibuteValue::U32);
361
impl_const_key_from!(i32, KeyAttibuteValue::I32);
362
impl_const_key_from!(u64, KeyAttibuteValue::U64);
363
impl_const_key_from!(i64, KeyAttibuteValue::I64);
364
impl_const_key_from!(u128, KeyAttibuteValue::U128);
365
impl_const_key_from!(i128, KeyAttibuteValue::I128);
366
impl_const_key_from!(usize, KeyAttibuteValue::Usize);
367
impl_const_key_from!(isize, KeyAttibuteValue::Isize);
368
impl_const_key_from!(bool, KeyAttibuteValue::Bool);
369
impl_const_key_from!(&'static str, |s: &'static str| KeyAttibuteValue::Str(
370
    Cow::Borrowed(s)
371
));
372
impl_const_key_from!(String, |s: String| KeyAttibuteValue::Str(Cow::Owned(s)));
373
impl_const_key_from!(&'static [u8], |b: &'static [u8]| KeyAttibuteValue::Bytes(
374
    Cow::Borrowed(b)
375
));
376
impl_const_key_from!(Vec<u8>, |b: Vec<u8>| KeyAttibuteValue::Bytes(Cow::Owned(b)));
377

            
378
/// A description of the kind of a composite key.
379
326
#[derive(Debug, Eq, PartialEq, Clone, Serialize, Deserialize)]
380
pub enum CompositeKind {
381
    /// An [`Option`], which always contains a single field.
382
    Option,
383
    /// An [`Result`], which reports two fields -- the first for the `Ok` type,
384
    /// and the second for the `Err` type.
385
    Result,
386
    /// A sequence of fields.
387
    Tuple,
388
    /// A sequence of fields, identified by the fully qualified name. E.g.,
389
    /// `"std::time::SystemTime"` is the value that the
390
    /// [`SystemTime`](std::time::SystemTime)'s `KeyEncoding` implementation
391
    /// reports.
392
    Struct(Cow<'static, str>),
393
}
394

            
395
/// A description of an encoded [`Key`].
396
4831
#[derive(Debug, Eq, PartialEq, Clone, Serialize, Deserialize)]
397
pub enum KeyDescription {
398
    /// A basic key type.
399
    Basic(KeyKind),
400
    /// A composite key made up of more than one field.
401
    Composite(CompositeKeyDescription),
402
    /// Another type with a custom encoding format.
403
    Other(Cow<'static, str>),
404
}
405

            
406
impl KeyDescription {
407
    /// Returns a description of the given [`KeyEncoding`] implementor.
408
    ///
409
    /// # Panics
410
    ///
411
    /// This function will panic if `KE` emits an imbalanced sequence of visit
412
    /// calls.
413
    #[must_use]
414
5837444
    pub fn for_encoding<KE: KeyEncoding<K>, K: for<'k> Key<'k>>() -> Self {
415
5837444
        let mut describer = KeyDescriber::default();
416
5837444
        KE::describe(&mut describer);
417
5837444
        describer
418
5837444
            .result
419
5837444
            .expect("invalid KeyEncoding::describe implementation -- imbalanced visit calls")
420
5837444
    }
421

            
422
    /// Returns the description of a given [`Key`] implementor.
423
    ///
424
    /// # Panics
425
    ///
426
    /// This function will panic if `KE` emits an imbalanced sequence of visit
427
    /// calls.
428
    #[must_use]
429
5837444
    pub fn for_key<K: for<'k> Key<'k>>() -> Self {
430
5837444
        Self::for_encoding::<K, K>()
431
5837444
    }
432
}
433

            
434
/// A description of a multi-field key encoded using [`CompositeKeyEncoder`].
435
1136
#[derive(Debug, Eq, PartialEq, Clone, Serialize, Deserialize)]
436
pub struct CompositeKeyDescription {
437
    /// The kind of composite key.
438
    pub kind: CompositeKind,
439
    /// The fields contained within this key.
440
    pub fields: Vec<KeyDescription>,
441
    /// The attributes of this key.
442
    pub attributes: HashMap<Cow<'static, str>, KeyAttibuteValue>,
443
}
444

            
445
5837444
#[derive(Default)]
446
struct KeyDescriber {
447
    stack: Vec<CompositeKeyDescription>,
448
    result: Option<KeyDescription>,
449
}
450

            
451
impl KeyDescriber {
452
12791488
    fn record(&mut self, description: KeyDescription) {
453
12791488
        match self.stack.last_mut() {
454
1124
            Some(composite) => {
455
1124
                composite.fields.push(description);
456
1124
                if composite.fields.len() == composite.fields.capacity() {
457
1042
                    // The composite key is finished, pop the state.
458
1042
                    let completed = self.stack.pop().expect("just matched");
459
1042
                    self.record(KeyDescription::Composite(completed));
460
1042
                }
461
            }
462
            None => {
463
                // Stack has been completed.
464
12790364
                assert!(self.result.replace(description).is_none());
465
            }
466
        }
467
12791488
    }
468
}
469

            
470
impl KeyVisitor for KeyDescriber {
471
12790446
    fn visit_type(&mut self, kind: KeyKind) {
472
12790446
        let description = KeyDescription::Basic(kind);
473
12790446
        self.record(description);
474
12790446
    }
475

            
476
1042
    fn visit_composite(&mut self, kind: CompositeKind, count: usize) {
477
1042
        self.stack.push(CompositeKeyDescription {
478
1042
            kind,
479
1042
            fields: Vec::with_capacity(count),
480
1042
            attributes: HashMap::new(),
481
1042
        });
482
1042
    }
483

            
484
1
    fn visit_composite_attribute(
485
1
        &mut self,
486
1
        key: impl Into<Cow<'static, str>>,
487
1
        value: impl Into<KeyAttibuteValue>,
488
1
    ) {
489
1
        let current = self
490
1
            .stack
491
1
            .last_mut()
492
1
            .expect("visit_composite_attribute must be called only after visit_composite");
493
1
        current.attributes.insert(key.into(), value.into());
494
1
    }
495
}
496

            
497
/// The error types for [`Key::next_value()`].
498
#[derive(Clone, thiserror::Error, Debug, Serialize, Deserialize)]
499
pub enum NextValueError {
500
    /// The key type does not support this operation.
501
    #[error("the key type does not support automatic ids")]
502
    Unsupported,
503
    /// Generating a new value would wrap the underlying value.
504
    #[error("the key type has run out of unique values")]
505
    WouldWrap,
506
}
507

            
508
/// A source of bytes from a `&'borrowed [u8]`, `&'ephemeral [u8]` or `Vec<u8>`.
509
///
510
/// This is used by the [`Key`] trait to allow `'ephemeral` borrows of an owned
511
/// `Vec<u8>` while also allowing for code paths that support borrowing from a
512
/// `'borrowed` byte slice.
513
pub enum ByteSource<'borrowed, 'ephemeral> {
514
    /// Borrowed bytes valid for `'borrowed`.
515
    Borrowed(&'borrowed [u8]),
516

            
517
    /// Borrowed bytes valid for `'ephemeral`.
518
    Ephemeral(&'ephemeral [u8]),
519

            
520
    /// Owned bytes.
521
    Owned(Vec<u8>),
522
}
523

            
524
impl<'borrowed, 'ephemeral> ByteSource<'borrowed, 'ephemeral>
525
where
526
    'borrowed: 'ephemeral,
527
{
528
    /// Coerce a `ByteSource` into `Cow<'borrowed, [u8]>`
529
    ///
530
    /// This will allocate if this is an `'ephemeral` reference.
531
    #[must_use]
532
124
    pub fn into_borrowed(self) -> Cow<'borrowed, [u8]> {
533
124
        match self {
534
123
            Self::Borrowed(bytes) => Cow::Borrowed(bytes),
535
            Self::Ephemeral(bytes) => Cow::Owned(Vec::from(bytes)),
536
1
            Self::Owned(bytes) => Cow::Owned(bytes),
537
        }
538
124
    }
539

            
540
    /// Coerce a `ByteSource` into a `Vec<u8>`
541
    ///
542
    /// This will allocate if the source is `'borrowed` or `'ephemeral`.
543
    #[must_use]
544
    #[allow(clippy::match_same_arms)] // Lifetimes are different.
545
543139
    pub fn into_owned(self) -> Vec<u8> {
546
543139
        match self {
547
543139
            Self::Borrowed(bytes) => Vec::from(bytes),
548
            Self::Ephemeral(bytes) => Vec::from(bytes),
549
            Self::Owned(bytes) => bytes,
550
        }
551
543139
    }
552
}
553

            
554
impl<'borrowed, 'ephemeral> AsRef<[u8]> for ByteSource<'borrowed, 'ephemeral> {
555
    #[allow(clippy::match_same_arms)] // Lifetimes are different.
556
326211754
    fn as_ref(&self) -> &[u8] {
557
326211754
        match self {
558
326211754
            Self::Borrowed(bytes) => bytes,
559
            Self::Ephemeral(bytes) => bytes,
560
            Self::Owned(ref bytes) => bytes.as_slice(),
561
        }
562
326211754
    }
563
}
564

            
565
impl<'borrowed, 'ephemeral> Deref for ByteSource<'borrowed, 'ephemeral> {
566
    type Target = [u8];
567

            
568
5696
    fn deref(&self) -> &Self::Target {
569
5696
        self.as_ref()
570
5696
    }
571
}
572

            
573
impl<'borrowed, 'ephemeral> Default for ByteSource<'borrowed, 'ephemeral> {
574
    fn default() -> Self {
575
        Self::Owned(Vec::default())
576
    }
577
}
578

            
579
impl<'borrowed, 'ephemeral> From<Cow<'borrowed, [u8]>> for ByteSource<'borrowed, 'ephemeral> {
580
    fn from(cow: Cow<'borrowed, [u8]>) -> Self {
581
        match cow {
582
            Cow::Borrowed(bytes) => ByteSource::Borrowed(bytes),
583
            Cow::Owned(bytes) => ByteSource::Owned(bytes),
584
        }
585
    }
586
}
587

            
588
/// A type that can be used as a prefix range in range-based queries.
589
pub trait IntoPrefixRange<'a, TOwned>: PartialEq
590
where
591
    TOwned: Borrow<Self> + PartialEq<Self>,
592
{
593
    /// Returns the value as a prefix-range, which will match all values that
594
    /// start with `self`.
595
    fn to_prefix_range(&'a self) -> RangeRef<'a, TOwned, Self>;
596
}
597

            
598
20
fn next_byte_sequence(start: &[u8]) -> Option<Vec<u8>> {
599
20
    let mut end = start.to_vec();
600
    // Modify the last byte by adding one. If it would wrap, we proceed to the
601
    // next byte.
602
30
    while let Some(last_byte) = end.pop() {
603
20
        if let Some(next) = last_byte.checked_add(1) {
604
10
            end.push(next);
605
10
            return Some(end);
606
10
        }
607
    }
608

            
609
10
    None
610
20
}
611

            
612
impl<'k> Key<'k> for Cow<'k, [u8]> {
613
    const CAN_OWN_BYTES: bool = true;
614

            
615
4
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
616
4
        Ok(bytes.into_borrowed())
617
4
    }
618
}
619

            
620
impl<'k, 'ke> KeyEncoding<Cow<'ke, [u8]>> for Cow<'k, [u8]> {
621
    type Error = Infallible;
622

            
623
    const LENGTH: Option<usize> = None;
624

            
625
    fn describe<Visitor>(visitor: &mut Visitor)
626
    where
627
        Visitor: KeyVisitor,
628
    {
629
        visitor.visit_type(KeyKind::Bytes);
630
    }
631

            
632
1
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
633
1
        Ok(self.clone())
634
1
    }
635
}
636

            
637
macro_rules! impl_u8_slice_key_encoding {
638
    ($type:ty) => {
639
        impl<'k> KeyEncoding<$type> for &'k [u8] {
640
            type Error = Infallible;
641

            
642
            const LENGTH: Option<usize> = None;
643

            
644
            fn describe<Visitor>(visitor: &mut Visitor)
645
            where
646
                Visitor: KeyVisitor,
647
            {
648
                visitor.visit_type(KeyKind::Bytes)
649
            }
650

            
651
            fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
652
                Ok(Cow::Borrowed(self))
653
            }
654
        }
655
    };
656
}
657

            
658
impl_u8_slice_key_encoding!(Cow<'k, [u8]>);
659

            
660
impl<'a, 'k> IntoPrefixRange<'a, Self> for Cow<'k, [u8]> {
661
    fn to_prefix_range(&'a self) -> RangeRef<'a, Self> {
662
4
        if let Some(next) = next_byte_sequence(self) {
663
2
            RangeRef {
664
2
                start: BoundRef::borrowed(Bound::Included(self)),
665
2
                end: BoundRef::owned(Bound::Excluded(Cow::Owned(next))),
666
2
            }
667
        } else {
668
2
            RangeRef {
669
2
                start: BoundRef::borrowed(Bound::Included(self)),
670
2
                end: BoundRef::Unbounded,
671
2
            }
672
        }
673
4
    }
674
}
675

            
676
impl<'a, 'k, TOwned, TBorrowed> Key<'k> for MaybeOwned<'a, TOwned, TBorrowed>
677
where
678
    TBorrowed: KeyEncoding<TOwned, Error = TOwned::Error> + PartialEq + ?Sized,
679
    TOwned: Key<'k> + PartialEq<TBorrowed>,
680
{
681
    const CAN_OWN_BYTES: bool = TOwned::CAN_OWN_BYTES;
682

            
683
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
684
        TOwned::from_ord_bytes(bytes).map(Self::Owned)
685
    }
686
}
687

            
688
impl<'a, 'k, TOwned, TBorrowed> KeyEncoding<Self> for MaybeOwned<'a, TOwned, TBorrowed>
689
where
690
    TBorrowed: KeyEncoding<TOwned, Error = TOwned::Error> + PartialEq + ?Sized,
691
    TOwned: Key<'k> + PartialEq<TBorrowed>,
692
{
693
    type Error = TOwned::Error;
694

            
695
    const LENGTH: Option<usize> = TBorrowed::LENGTH;
696

            
697
    fn describe<Visitor>(visitor: &mut Visitor)
698
    where
699
        Visitor: KeyVisitor,
700
    {
701
        TBorrowed::describe(visitor);
702
    }
703

            
704
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
705
        match self {
706
            MaybeOwned::Owned(value) => value.as_ord_bytes(),
707
            MaybeOwned::Borrowed(value) => value.as_ord_bytes(),
708
        }
709
    }
710
}
711

            
712
1
#[test]
713
1
fn cow_prefix_range_tests() {
714
1
    use std::ops::RangeBounds;
715
1
    assert!(Cow::<'_, [u8]>::Borrowed(b"a")
716
1
        .to_prefix_range()
717
1
        .contains(&Cow::Borrowed(&b"aa"[..])));
718
1
    assert!(!Cow::<'_, [u8]>::Borrowed(b"a")
719
1
        .to_prefix_range()
720
1
        .contains(&Cow::Borrowed(&b"b"[..])));
721
1
    assert!(Cow::<'_, [u8]>::Borrowed(b"\xff")
722
1
        .to_prefix_range()
723
1
        .contains(&Cow::Borrowed(&b"\xff\xff"[..])));
724
1
    assert!(!Cow::<'_, [u8]>::Borrowed(b"\xff")
725
1
        .to_prefix_range()
726
1
        .contains(&Cow::Borrowed(&b"\xfe"[..])));
727
1
}
728

            
729
impl<'k> Key<'k> for Vec<u8> {
730
    const CAN_OWN_BYTES: bool = true;
731

            
732
8
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
733
8
        Ok(bytes.into_owned())
734
8
    }
735
}
736

            
737
impl KeyEncoding<Self> for Vec<u8> {
738
    type Error = Infallible;
739

            
740
    const LENGTH: Option<usize> = None;
741

            
742
1
    fn describe<Visitor>(visitor: &mut Visitor)
743
1
    where
744
1
        Visitor: KeyVisitor,
745
1
    {
746
1
        visitor.visit_type(KeyKind::Bytes);
747
1
    }
748

            
749
11
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
750
11
        Ok(Cow::Borrowed(self))
751
11
    }
752
}
753

            
754
impl_u8_slice_key_encoding!(Vec<u8>);
755

            
756
impl<'k> IntoPrefixRange<'k, Self> for Vec<u8> {
757
    fn to_prefix_range(&'k self) -> RangeRef<'k, Self> {
758
4
        if let Some(next) = next_byte_sequence(self) {
759
2
            RangeRef {
760
2
                start: BoundRef::borrowed(Bound::Included(self)),
761
2
                end: BoundRef::owned(Bound::Excluded(next)),
762
2
            }
763
        } else {
764
2
            RangeRef {
765
2
                start: BoundRef::borrowed(Bound::Included(self)),
766
2
                end: BoundRef::Unbounded,
767
2
            }
768
        }
769
4
    }
770
}
771

            
772
impl<'k, const N: usize> Key<'k> for [u8; N] {
773
    const CAN_OWN_BYTES: bool = false;
774

            
775
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
776
        if bytes.as_ref().len() == N {
777
            let mut array = [0; N];
778
            array.copy_from_slice(bytes.as_ref());
779
            Ok(array)
780
        } else {
781
            Err(IncorrectByteLength)
782
        }
783
    }
784
}
785

            
786
impl<const N: usize> KeyEncoding<Self> for [u8; N] {
787
    type Error = IncorrectByteLength;
788

            
789
    const LENGTH: Option<usize> = Some(N);
790

            
791
    fn describe<Visitor>(visitor: &mut Visitor)
792
    where
793
        Visitor: KeyVisitor,
794
    {
795
        visitor.visit_type(KeyKind::Bytes);
796
    }
797

            
798
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
799
        Ok(Cow::Borrowed(self))
800
    }
801
}
802

            
803
1
#[test]
804
1
fn vec_prefix_range_tests() {
805
1
    use std::ops::RangeBounds;
806
1
    assert!(b"a".to_vec().to_prefix_range().contains(&b"aa".to_vec()));
807
1
    assert!(!b"a".to_vec().to_prefix_range().contains(&b"b".to_vec()));
808
1
    assert!(b"\xff"
809
1
        .to_vec()
810
1
        .to_prefix_range()
811
1
        .contains(&b"\xff\xff".to_vec()));
812
1
    assert!(!b"\xff"
813
1
        .to_vec()
814
1
        .to_prefix_range()
815
1
        .contains(&b"\xfe".to_vec()));
816
1
}
817

            
818
impl<'k> Key<'k> for ArcBytes<'k> {
819
    const CAN_OWN_BYTES: bool = true;
820

            
821
    fn from_ord_bytes<'b>(bytes: ByteSource<'k, 'b>) -> Result<Self, Self::Error> {
822
        Ok(Self::from(bytes.into_borrowed()))
823
    }
824
}
825

            
826
impl<'k> KeyEncoding<Self> for ArcBytes<'k> {
827
    type Error = Infallible;
828

            
829
    const LENGTH: Option<usize> = None;
830

            
831
    fn describe<Visitor>(visitor: &mut Visitor)
832
    where
833
        Visitor: KeyVisitor,
834
    {
835
        visitor.visit_type(KeyKind::Bytes);
836
    }
837

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

            
843
impl_u8_slice_key_encoding!(ArcBytes<'k>);
844

            
845
impl<'a, 'k> IntoPrefixRange<'a, Self> for ArcBytes<'k> {
846
    fn to_prefix_range(&'a self) -> RangeRef<'a, Self> {
847
4
        if let Some(next) = next_byte_sequence(self) {
848
2
            RangeRef {
849
2
                start: BoundRef::borrowed(Bound::Included(self)),
850
2
                end: BoundRef::owned(Bound::Excluded(Self::owned(next))),
851
2
            }
852
        } else {
853
2
            RangeRef {
854
2
                start: BoundRef::borrowed(Bound::Included(self)),
855
2
                end: BoundRef::Unbounded,
856
2
            }
857
        }
858
4
    }
859
}
860

            
861
1
#[test]
862
1
fn arcbytes_prefix_range_tests() {
863
1
    use std::ops::RangeBounds;
864
1
    assert!(ArcBytes::from(b"a")
865
1
        .to_prefix_range()
866
1
        .contains(&ArcBytes::from(b"aa")));
867
1
    assert!(!ArcBytes::from(b"a")
868
1
        .to_prefix_range()
869
1
        .contains(&ArcBytes::from(b"b")));
870
1
    assert!(ArcBytes::from(b"\xff")
871
1
        .to_prefix_range()
872
1
        .contains(&ArcBytes::from(b"\xff\xff")));
873
1
    assert!(!ArcBytes::from(b"\xff")
874
1
        .to_prefix_range()
875
1
        .contains(&ArcBytes::from(b"\xfe")));
876
1
}
877

            
878
impl<'k> Key<'k> for CowBytes<'k> {
879
    const CAN_OWN_BYTES: bool = true;
880

            
881
    fn from_ord_bytes<'b>(bytes: ByteSource<'k, 'b>) -> Result<Self, Self::Error> {
882
        Ok(Self(bytes.into_borrowed()))
883
    }
884
}
885

            
886
impl<'k> KeyEncoding<Self> for CowBytes<'k> {
887
    type Error = Infallible;
888

            
889
    const LENGTH: Option<usize> = None;
890

            
891
    fn describe<Visitor>(visitor: &mut Visitor)
892
    where
893
        Visitor: KeyVisitor,
894
    {
895
        visitor.visit_type(KeyKind::Bytes);
896
    }
897

            
898
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
899
        Ok(self.0.clone())
900
    }
901
}
902

            
903
impl_u8_slice_key_encoding!(CowBytes<'k>);
904

            
905
impl<'a, 'k> IntoPrefixRange<'a, Self> for CowBytes<'k> {
906
    fn to_prefix_range(&'a self) -> RangeRef<'_, Self> {
907
4
        if let Some(next) = next_byte_sequence(self) {
908
2
            RangeRef {
909
2
                start: BoundRef::borrowed(Bound::Included(self)),
910
2
                end: BoundRef::owned(Bound::Excluded(Self::from(next))),
911
2
            }
912
        } else {
913
2
            RangeRef {
914
2
                start: BoundRef::borrowed(Bound::Included(self)),
915
2
                end: BoundRef::Unbounded,
916
2
            }
917
        }
918
4
    }
919
}
920

            
921
1
#[test]
922
1
fn cowbytes_prefix_range_tests() {
923
1
    use std::ops::RangeBounds;
924
1
    assert!(CowBytes::from(&b"a"[..])
925
1
        .to_prefix_range()
926
1
        .contains(&CowBytes::from(&b"aa"[..])));
927
1
    assert!(!CowBytes::from(&b"a"[..])
928
1
        .to_prefix_range()
929
1
        .contains(&CowBytes::from(&b"b"[..])));
930
1
    assert!(CowBytes::from(&b"\xff"[..])
931
1
        .to_prefix_range()
932
1
        .contains(&CowBytes::from(&b"\xff\xff"[..])));
933
1
    assert!(!CowBytes::from(&b"\xff"[..])
934
1
        .to_prefix_range()
935
1
        .contains(&CowBytes::from(&b"\xfe"[..])));
936
1
}
937

            
938
impl<'k> Key<'k> for Bytes {
939
    const CAN_OWN_BYTES: bool = true;
940

            
941
    fn from_ord_bytes<'b>(bytes: ByteSource<'k, 'b>) -> Result<Self, Self::Error> {
942
        Ok(Self(bytes.into_owned()))
943
    }
944
}
945

            
946
impl KeyEncoding<Self> for Bytes {
947
    type Error = Infallible;
948

            
949
    const LENGTH: Option<usize> = None;
950

            
951
1
    fn describe<Visitor>(visitor: &mut Visitor)
952
1
    where
953
1
        Visitor: KeyVisitor,
954
1
    {
955
1
        visitor.visit_type(KeyKind::Bytes);
956
1
    }
957

            
958
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
959
        Ok(Cow::Borrowed(self))
960
    }
961
}
962

            
963
impl_u8_slice_key_encoding!(Bytes);
964

            
965
impl<'a> IntoPrefixRange<'a, Self> for Bytes {
966
    fn to_prefix_range(&'a self) -> RangeRef<'a, Self> {
967
4
        if let Some(next) = next_byte_sequence(self) {
968
2
            RangeRef {
969
2
                start: BoundRef::borrowed(Bound::Included(self)),
970
2
                end: BoundRef::owned(Bound::Excluded(Self::from(next))),
971
2
            }
972
        } else {
973
2
            RangeRef {
974
2
                start: BoundRef::borrowed(Bound::Included(self)),
975
2
                end: BoundRef::Unbounded,
976
2
            }
977
        }
978
4
    }
979
}
980

            
981
1
#[test]
982
1
fn bytes_prefix_range_tests() {
983
1
    use std::ops::RangeBounds;
984
1
    assert!(Bytes::from(b"a".to_vec())
985
1
        .to_prefix_range()
986
1
        .contains(&Bytes::from(b"aa".to_vec())));
987
1
    assert!(!Bytes::from(b"a".to_vec())
988
1
        .to_prefix_range()
989
1
        .contains(&Bytes::from(b"b".to_vec())));
990
1
    assert!(Bytes::from(b"\xff".to_vec())
991
1
        .to_prefix_range()
992
1
        .contains(&Bytes::from(b"\xff\xff".to_vec())));
993
1
    assert!(!Bytes::from(b"\xff".to_vec())
994
1
        .to_prefix_range()
995
1
        .contains(&Bytes::from(b"\xfe".to_vec())));
996
1
}
997

            
998
impl<'k> Key<'k> for String {
999
    const CAN_OWN_BYTES: bool = true;

            
543130
    fn from_ord_bytes<'b>(bytes: ByteSource<'k, 'b>) -> Result<Self, Self::Error> {
543130
        Self::from_utf8(bytes.into_owned())
543130
    }
}

            
impl KeyEncoding<Self> for String {
    type Error = FromUtf8Error;

            
    const LENGTH: Option<usize> = None;

            
3361
    fn describe<Visitor>(visitor: &mut Visitor)
3361
    where
3361
        Visitor: KeyVisitor,
3361
    {
3361
        visitor.visit_type(KeyKind::String);
3361
    }

            
134167
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
134167
        Ok(Cow::Borrowed(self.as_bytes()))
134167
    }
}

            
impl KeyEncoding<String> for str {
    type Error = FromUtf8Error;

            
    const LENGTH: Option<usize> = None;

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_type(KeyKind::String);
    }

            
406404
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
406404
        Ok(Cow::Borrowed(self.as_bytes()))
406404
    }
}

            
impl<'a> IntoPrefixRange<'a, Self> for String {
6
    fn to_prefix_range(&'a self) -> RangeRef<'a, Self> {
6
        let mut bytes = self.as_bytes().to_vec();
6
        for (index, char) in self.char_indices().rev() {
6
            let mut next_char = u32::from(char) + 1;
6
            if next_char == 0xd800 {
                next_char = 0xE000;
6
            } else if next_char > u32::from(char::MAX) {
2
                continue;
4
            }

            
4
            let mut char_bytes = [0; 6];
4
            bytes.splice(
4
                index..,
4
                char::try_from(next_char)
4
                    .unwrap()
4
                    .encode_utf8(&mut char_bytes)
4
                    .bytes(),
4
            );
4
            return RangeRef {
4
                start: BoundRef::borrowed(Bound::Included(self)),
4
                end: BoundRef::owned(Bound::Excluded(Self::from_utf8(bytes).unwrap())),
4
            };
        }

            
2
        RangeRef {
2
            start: BoundRef::borrowed(Bound::Included(self)),
2
            end: BoundRef::Unbounded,
2
        }
6
    }
}

            
impl<'a> IntoPrefixRange<'a, String> for str {
40
    fn to_prefix_range(&'a self) -> RangeRef<'a, String, Self> {
40
        let mut bytes = self.as_bytes().to_vec();
40
        for (index, char) in self.char_indices().rev() {
40
            let mut next_char = u32::from(char) + 1;
40
            if next_char == 0xd800 {
                next_char = 0xE000;
40
            } else if next_char > u32::from(char::MAX) {
                continue;
40
            }

            
40
            let mut char_bytes = [0; 6];
40
            bytes.splice(
40
                index..,
40
                char::try_from(next_char)
40
                    .unwrap()
40
                    .encode_utf8(&mut char_bytes)
40
                    .bytes(),
40
            );
40
            return RangeRef {
40
                start: BoundRef::borrowed(Bound::Included(self)),
40
                end: BoundRef::owned(Bound::Excluded(String::from_utf8(bytes).unwrap())),
40
            };
        }

            
        RangeRef {
            start: BoundRef::borrowed(Bound::Included(self)),
            end: BoundRef::Unbounded,
        }
40
    }
}

            
impl<'k> Key<'k> for Cow<'k, str> {
    const CAN_OWN_BYTES: bool = true;

            
120
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
120
        match bytes.into_borrowed() {
120
            Cow::Borrowed(bytes) => std::str::from_utf8(bytes).map(Cow::Borrowed),
            Cow::Owned(bytes) => String::from_utf8(bytes)
                .map(Cow::Owned)
                .map_err(|e| e.utf8_error()),
        }
120
    }
}

            
impl<'k> KeyEncoding<Self> for Cow<'k, str> {
    type Error = std::str::Utf8Error;

            
    const LENGTH: Option<usize> = None;

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_type(KeyKind::String);
    }

            
4440
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
4440
        Ok(Cow::Borrowed(self.as_bytes()))
4440
    }
}

            
1
#[test]
1
fn string_prefix_range_tests() {
1
    use std::ops::RangeBounds;
1
    assert!(String::from("a")
1
        .to_prefix_range()
1
        .contains(&String::from("aa")));
1
    assert!(!String::from("a")
1
        .to_prefix_range()
1
        .contains(&String::from("b")));
1
    assert!(String::from("\u{d799}")
1
        .to_prefix_range()
1
        .contains(&String::from("\u{d799}a")));
1
    assert!(!String::from("\u{d799}")
1
        .to_prefix_range()
1
        .contains(&String::from("\u{e000}")));
1
    assert!(String::from("\u{10ffff}")
1
        .to_prefix_range()
1
        .contains(&String::from("\u{10ffff}a")));
1
    assert!(!String::from("\u{10ffff}")
1
        .to_prefix_range()
1
        .contains(&String::from("\u{10fffe}")));
1
}

            
impl<'k> Key<'k> for () {
    const CAN_OWN_BYTES: bool = false;

            
121
    fn from_ord_bytes<'b>(_: ByteSource<'k, 'b>) -> Result<Self, Self::Error> {
121
        Ok(())
121
    }
}

            
impl KeyEncoding<Self> for () {
    type Error = Infallible;

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

            
640
    fn describe<Visitor>(visitor: &mut Visitor)
640
    where
640
        Visitor: KeyVisitor,
640
    {
640
        visitor.visit_type(KeyKind::Unit);
640
    }

            
81
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
81
        Ok(Cow::default())
81
    }
}

            
impl<'k> Key<'k> for bool {
    const CAN_OWN_BYTES: bool = false;

            
2
    fn from_ord_bytes<'b>(bytes: ByteSource<'k, 'b>) -> Result<Self, Self::Error> {
2
        let bytes = bytes.as_ref();
2
        if bytes.is_empty() || bytes[0] == 0 {
1
            Ok(false)
        } else {
1
            Ok(true)
        }
2
    }
}

            
impl KeyEncoding<Self> for bool {
    type Error = Infallible;

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

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_type(KeyKind::Bool);
    }

            
2
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
2
        if *self {
1
            Ok(Cow::Borrowed(&[1_u8]))
        } else {
1
            Ok(Cow::Borrowed(&[0_u8]))
        }
2
    }
}

            
macro_rules! count_args {
    () => (0usize);
    ( $arg:tt $($remaining:tt)* ) => (1usize + count_args!($($remaining)*));
}

            
macro_rules! impl_key_for_tuple {
    ($(($index:tt, $varname:ident, $generic:ident)),+) => {
        impl<'k, $($generic),+> Key<'k> for ($($generic),+,)
        where
            $($generic: for<'ke> Key<'ke>),+
        {
            const CAN_OWN_BYTES: bool = false;
87391
            fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
87391
                let mut decoder = CompositeKeyDecoder::default_for(bytes);
87391
                $(let $varname = decoder.decode::<$generic>()?;)+
87391
                decoder.finish()?;

            
87391
                Ok(($($varname),+,))
87391
            }
        }

            
        impl<$($generic),+> KeyEncoding<Self> for ($($generic),+,)
        where
            $($generic: for<'k> Key<'k>),+
        {
            type Error = CompositeKeyError;

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

            
1
            fn describe<Visitor>(visitor: &mut Visitor)
1
            where
1
                Visitor: KeyVisitor,
1
            {
1
                visitor.visit_composite(CompositeKind::Tuple, count_args!($($generic) +));
1
                $($generic::describe(visitor);)+
1
            }

            
87391
            fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
87391
                let mut encoder = CompositeKeyEncoder::default();
87391

            
87391
                $(encoder.encode(&self.$index)?;)+

            
87391
                Ok(Cow::Owned(encoder.finish()))
87391
            }
        }
    };
}

            
impl_key_for_tuple!((0, t1, T1));
impl_key_for_tuple!((0, t1, T1), (1, t2, T2));
impl_key_for_tuple!((0, t1, T1), (1, t2, T2), (2, t3, T3));
impl_key_for_tuple!((0, t1, T1), (1, t2, T2), (2, t3, T3), (3, t4, T4));
impl_key_for_tuple!(
    (0, t1, T1),
    (1, t2, T2),
    (2, t3, T3),
    (3, t4, T4),
    (4, t5, T5)
);
impl_key_for_tuple!(
    (0, t1, T1),
    (1, t2, T2),
    (2, t3, T3),
    (3, t4, T4),
    (4, t5, T5),
    (5, t6, T6)
);
impl_key_for_tuple!(
    (0, t1, T1),
    (1, t2, T2),
    (2, t3, T3),
    (3, t4, T4),
    (4, t5, T5),
    (5, t6, T6),
    (6, t7, T7)
);
impl_key_for_tuple!(
    (0, t1, T1),
    (1, t2, T2),
    (2, t3, T3),
    (3, t4, T4),
    (4, t5, T5),
    (5, t6, T6),
    (6, t7, T7),
    (7, t8, T8)
);

            
/// Encodes multiple [`KeyEncoding`] implementors into a single byte buffer,
/// preserving the ordering guarantees necessary for [`Key`].
///
/// The produced bytes can be decoded using [`CompositeKeyDecoder`].
pub struct CompositeKeyEncoder<NullHandling = EscapeNullBytes> {
    bytes: Vec<u8>,
    encoded_lengths: Vec<u16>,
    null_handling: NullHandling,
}

            
impl<NullHandling> CompositeKeyEncoder<NullHandling>
where
    NullHandling: CompositeKeyNullHandler,
{
    /// Encodes a single [`KeyEncoding`] implementing value.
    ///
    /// ```rust
    /// # use bonsaidb_core::key::{ByteSource, CompositeKeyEncoder, CompositeKeyDecoder};
    ///
    /// let value1 = String::from("hello");
    /// let value2 = 42_u32;
    /// let mut encoder = CompositeKeyEncoder::default();
    /// encoder.encode(&value1).unwrap();
    /// encoder.encode(&value2).unwrap();
    /// let encoded = encoder.finish();
    ///
    /// let mut decoder = CompositeKeyDecoder::default_for(ByteSource::Borrowed(&encoded));
    /// let decoded_string = decoder.decode::<String>().unwrap();
    /// assert_eq!(decoded_string, value1);
    /// let decoded_u32 = decoder.decode::<u32>().unwrap();
    /// assert_eq!(decoded_u32, value2);
    /// decoder.finish().expect("trailing bytes");
    /// ```
670379
    pub fn encode<'k, K: Key<'k>, T: KeyEncoding<K> + ?Sized>(
670379
        &mut self,
670379
        value: &'k T,
670379
    ) -> Result<(), CompositeKeyError> {
670379
        let mut encoded = T::as_ord_bytes(value).map_err(CompositeKeyError::new)?;
670379
        if T::LENGTH.is_none() {
439
            self.null_handling.handle_nulls(&mut encoded)?;
438
            let encoded_length = u16::try_from(encoded.len())?;
438
            self.encoded_lengths.push(encoded_length);
669940
        }
670378
        self.bytes.extend_from_slice(&encoded);
670378
        if T::LENGTH.is_none() {
438
            // With variable length data, we need the key to have a delimiter to
438
            // ensure that "a" sorts before "aa".
438
            self.bytes.push(0);
670352
        }
670378
        Ok(())
670379
    }

            
    /// Finishes encoding the field and returns the encoded bytes.
    #[must_use]
    #[allow(clippy::missing_panics_doc)] // All unreachable
87715
    pub fn finish(mut self) -> Vec<u8> {
87715
        self.bytes.reserve_exact(self.encoded_lengths.len() * 2);
87889
        for length in self.encoded_lengths.into_iter().rev() {
513
            match length {
513
                0..=0x7F => {
507
                    self.bytes.push(u8::try_from(length).unwrap());
507
                }
6
                0x80..=0x3FFF => {
4
                    self.bytes.push(u8::try_from(length >> 7).unwrap());
4
                    self.bytes
4
                        .push(u8::try_from((length & 0x7F) | 0x80).unwrap());
4
                }
2
                0x4000.. => {
2
                    self.bytes.push(u8::try_from(length >> 14).unwrap());
2
                    self.bytes
2
                        .push(u8::try_from(((length >> 7) & 0x7F) | 0x80).unwrap());
2
                    self.bytes
2
                        .push(u8::try_from((length & 0x7F) | 0x80).unwrap());
2
                }
            }
        }
87715
        self.bytes
87715
    }
}

            
impl Default for CompositeKeyEncoder<EscapeNullBytes> {
91272
    fn default() -> Self {
91272
        Self {
91272
            bytes: Vec::new(),
91272
            encoded_lengths: Vec::new(),
91272
            null_handling: EscapeNullBytes,
91272
        }
91272
    }
}

            
impl CompositeKeyEncoder<AllowNullBytes> {
    /// Returns an encoder that allows null bytes in variable length fields.
    ///
    /// See [`CompositeKeyFieldContainsNullByte`] for information about the edge
    /// cases this may introduce.
    #[must_use]
1
    pub const fn allowing_null_bytes() -> Self {
1
        Self {
1
            bytes: Vec::new(),
1
            encoded_lengths: Vec::new(),
1
            null_handling: AllowNullBytes,
1
        }
1
    }
}

            
impl CompositeKeyEncoder<DenyNullBytes> {
    /// Returns an encoder that denies null bytes in variable length fields by
    /// returning an error when any null bytes are detected.
    #[must_use]
1
    pub const fn denying_null_bytes() -> Self {
1
        Self {
1
            bytes: Vec::new(),
1
            encoded_lengths: Vec::new(),
1
            null_handling: DenyNullBytes,
1
        }
1
    }
}

            
/// Escapes null bytes in variable length fields in composite keys. This option
/// ensures proper sort order is maintained even when null bytes are used within
/// vairable fields.
///
/// To see more information about the edge case encoding prevents, see
/// [`CompositeKeyFieldContainsNullByte`].
#[derive(Default, Debug, Clone, Copy)]
pub struct EscapeNullBytes;
/// Prevents checking for null bytes in variable length fields in composite
/// keys. [`Key`] types that have a fixed width have no edge cases with null
/// bytes. See [`CompositeKeyFieldContainsNullByte`] for an explanation and
/// example of the edge case introduced when allowing null bytes to be used
/// without escaping.
#[derive(Default, Debug, Clone, Copy)]
pub struct AllowNullBytes;
#[derive(Default, Debug, Clone, Copy)]
/// Checks for null bytes when encoding variable length fields in composite keys
/// and returns an error if any are encountered. This prevents extra processing
/// when encoding fields, but may introduce incorrect sort ordering (see
/// [`CompositeKeyFieldContainsNullByte`] for more).
pub struct DenyNullBytes;

            
/// A null-byte handling approach for [`CompositeKeyEncoder`] and
/// [`CompositeKeyDecoder`]. This type is only used when the fields being
/// encoded are variable length.
///
/// Ensuring proper sort order with composite keys requires special handling of
/// null bytes. The safest option is to use [`EscapeNullBytes`], but this option
/// will cause extra allocations when keys contain null bytes.
/// [`AllowNullBytes`] allows null-bytes through without any extra checks, but
/// their usage can cause incorrect sorting behavior. See
/// [`CompositeKeyFieldContainsNullByte`] for more information on this edge
/// case. The last implementation is [`DenyNullBytes`] which checks for null
/// bytes when encoding and returns an error if any are encountered. When
/// decoding with this option, there is no extra processing performed before
/// decoding individual fields.
pub trait CompositeKeyNullHandler {
    /// Process the null bytes in `field_bytes`, if needed.
    fn handle_nulls(&self, field_bytes: &mut Cow<'_, [u8]>) -> Result<(), CompositeKeyError>;
    /// Decode the null bytes in `encoded`, if needed.
    fn decode_nulls_if_needed<'b, 'e>(
        &self,
        encoded: ByteSource<'b, 'e>,
    ) -> Result<ByteSource<'b, 'e>, CompositeKeyError>;
}

            
impl CompositeKeyNullHandler for DenyNullBytes {
    #[inline]
1
    fn handle_nulls(&self, encoded: &mut Cow<'_, [u8]>) -> Result<(), CompositeKeyError> {
1
        if encoded.iter().any(|b| *b == 0) {
1
            Err(CompositeKeyError::new(io::Error::new(
1
                ErrorKind::InvalidData,
1
                CompositeKeyFieldContainsNullByte,
1
            )))
        } else {
            Ok(())
        }
1
    }

            
    #[inline]
1
    fn decode_nulls_if_needed<'b, 'e>(
1
        &self,
1
        encoded: ByteSource<'b, 'e>,
1
    ) -> Result<ByteSource<'b, 'e>, CompositeKeyError> {
1
        Ok(encoded)
1
    }
}

            
impl CompositeKeyNullHandler for AllowNullBytes {
    #[inline]
1
    fn handle_nulls(&self, _encoded: &mut Cow<'_, [u8]>) -> Result<(), CompositeKeyError> {
1
        Ok(())
1
    }

            
    #[inline]
1
    fn decode_nulls_if_needed<'b, 'e>(
1
        &self,
1
        encoded: ByteSource<'b, 'e>,
1
    ) -> Result<ByteSource<'b, 'e>, CompositeKeyError> {
1
        Ok(encoded)
1
    }
}

            
impl CompositeKeyNullHandler for EscapeNullBytes {
    #[inline]
437
    fn handle_nulls(&self, unescaped: &mut Cow<'_, [u8]>) -> Result<(), CompositeKeyError> {
437
        let null_bytes = bytecount::count(unescaped, 0);
437
        if null_bytes > 0 {
1
            let mut null_encoded = Vec::with_capacity(unescaped.len() + null_bytes);
3
            for unescaped in unescaped.as_ref() {
3
                if *unescaped == 0 {
1
                    null_encoded.extend_from_slice(&[0, 0]);
2
                } else {
2
                    null_encoded.push(*unescaped);
2
                }
            }
1
            *unescaped = Cow::Owned(null_encoded);
436
        }
437
        Ok(())
437
    }

            
    #[inline]
308
    fn decode_nulls_if_needed<'b, 'e>(
308
        &self,
308
        mut encoded: ByteSource<'b, 'e>,
308
    ) -> Result<ByteSource<'b, 'e>, CompositeKeyError> {
        // Find the first null byte
308
        if let Some(mut index) = encoded
308
            .iter()
308
            .enumerate()
68066
            .find_map(|(index, b)| (*b == 0).then_some(index))
        {
            // The field has at least one null byte, we need to mutate the
            // bytes.
1
            let mut bytes = encoded.into_owned();
            loop {
                // Check that the next byte is a null. If so, we remove the
                // current byte and look for the next null.
1
                let next_index = index + 1;
1
                if Some(0) == bytes.get(next_index).copied() {
1
                    bytes.remove(index);
1
                    index = next_index;
1
                } else {
                    todo!("error: unescaped null byte")
                    // return Err(CompositeKeyError::new("unescaped null byte encountered"));
                }

            
                // Find the next null byte, if one exists.
1
                let Some(next_index) = bytes[index..]
1
                    .iter()
1
                    .enumerate()
1
                    .find_map(|(index, b)| (*b == 0).then_some(index))
                else {
1
                    break;
                };
                index += next_index;
            }
1
            encoded = ByteSource::Owned(bytes);
307
        }
308
        Ok(encoded)
308
    }
}

            
/// Null bytes in variable fields encoded with [`CompositeKeyEncoder`] can cause
/// sort order to misbehave.
///
/// Consider these tuples:
///
/// | Tuple          | Encoded          |
/// |----------------|------------------|
/// | `("a", "b")`   | `9700 9800 0101` |
/// | `("a\0", "a")` | `9700 9700 0101` |
///
/// The encoded bytes, when compared, will produce a different sort result than
/// when comparing the tuples.
///
/// By default, [`CompositeKeyEncoder`] checks for null bytes and returns an
/// error when a null byte is found. See
/// [`CompositeKeyEncoder::allowing_null_bytes()`] if you wish
/// to allow null bytes despite this edge case.
#[derive(thiserror::Error, Debug)]
#[error("a variable length field contained a null byte.")]
pub struct CompositeKeyFieldContainsNullByte;

            
/// Decodes multiple [`Key`] values from a byte slice previously encoded with
/// [`CompositeKeyEncoder`].
pub struct CompositeKeyDecoder<'key, 'ephemeral, NullHandling = EscapeNullBytes> {
    bytes: ByteSource<'key, 'ephemeral>,
    offset: usize,
    end: usize,
    null_handling: NullHandling,
}

            
impl<'key, 'ephemeral> CompositeKeyDecoder<'key, 'ephemeral, EscapeNullBytes> {
    /// Returns a decoder for `bytes` that decodes escaped null bytes.
    ///
    /// This function is compatible with keys encoded with
    /// [`CompositeKeyEncoder::default()`].
    #[must_use]
90352
    pub fn default_for(bytes: ByteSource<'key, 'ephemeral>) -> Self {
90352
        Self {
90352
            end: bytes.as_ref().len(),
90352
            bytes,
90352
            offset: 0,
90352
            null_handling: EscapeNullBytes,
90352
        }
90352
    }
}

            
impl<'key, 'ephemeral> CompositeKeyDecoder<'key, 'ephemeral, AllowNullBytes> {
    /// Returns a decoder for `bytes` that ignores null bytes.
    ///
    /// This function is compatible with keys encoded with
    /// [`CompositeKeyEncoder::allowing_null_bytes()`].
    #[must_use]
1
    pub fn allowing_null_bytes(bytes: ByteSource<'key, 'ephemeral>) -> Self {
1
        Self {
1
            end: bytes.as_ref().len(),
1
            bytes,
1
            offset: 0,
1
            null_handling: AllowNullBytes,
1
        }
1
    }
}

            
impl<'key, 'ephemeral> CompositeKeyDecoder<'key, 'ephemeral, DenyNullBytes> {
    /// Returns a decoder for `bytes` that ignores null bytes.
    ///
    /// This function is compatible with keys encoded with
    /// [`CompositeKeyEncoder::denying_null_bytes()`].
    #[must_use]
1
    pub fn denying_null_bytes(bytes: ByteSource<'key, 'ephemeral>) -> Self {
1
        Self {
1
            end: bytes.as_ref().len(),
1
            bytes,
1
            offset: 0,
1
            null_handling: DenyNullBytes,
1
        }
1
    }
}

            
impl<'key, 'ephemeral, NullHandling> CompositeKeyDecoder<'key, 'ephemeral, NullHandling>
where
    NullHandling: CompositeKeyNullHandler,
{
    /// Decodes a value previously encoded using [`CompositeKeyEncoder`]. Calls
    /// to decode must be made in the same order as the values were encoded in.
    ///
    /// ```rust
    /// # use bonsaidb_core::key::{ByteSource, CompositeKeyEncoder, CompositeKeyDecoder};
    ///
    /// let value1 = String::from("hello");
    /// let value2 = 42_u32;
    /// let mut encoder = CompositeKeyEncoder::default();
    /// encoder.encode(&value1).unwrap();
    /// encoder.encode(&value2).unwrap();
    /// let encoded = encoder.finish();
    ///
    /// let mut decoder = CompositeKeyDecoder::default_for(ByteSource::Borrowed(&encoded));
    /// let decoded_string = decoder.decode::<String>().unwrap();
    /// assert_eq!(decoded_string, value1);
    /// let decoded_u32 = decoder.decode::<u32>().unwrap();
    /// assert_eq!(decoded_u32, value2);
    /// decoder.finish().expect("trailing bytes");
    /// ```
670247
    pub fn decode<T: Key<'key>>(&mut self) -> Result<T, CompositeKeyError> {
670247
        let length = if let Some(length) = T::LENGTH {
669937
            length
        } else {
            // Read a variable-encoded length from the tail of the bytes.
310
            let mut length = 0;
310
            let mut found_end = false;
310

            
310
            let bytes = self.bytes.as_ref();
310

            
310
            let iterator = bytes[self.offset..self.end]
310
                .iter()
310
                .copied()
310
                .rev()
310
                .enumerate();

            
318
            for (index, byte) in iterator {
318
                length |= usize::from(byte & 0x7f) << (index * 7);
318

            
318
                if byte & 0x80 == 0 {
310
                    self.end = self.end - index - 1;
310
                    found_end = true;
310
                    break;
8
                }
            }

            
310
            if !found_end {
                return Err(CompositeKeyError::new(io::Error::from(
                    ErrorKind::UnexpectedEof,
                )));
310
            }
310
            length
        };
670247
        let end = self.offset + length;
670247
        if end <= self.end {
670247
            let mut bytes = match &self.bytes {
670247
                ByteSource::Borrowed(bytes) => ByteSource::Borrowed(&bytes[self.offset..end]),
                ByteSource::Ephemeral(bytes) => ByteSource::Ephemeral(&bytes[self.offset..end]),
                ByteSource::Owned(bytes) => ByteSource::Ephemeral(&bytes[self.offset..end]),
            };
670247
            if T::LENGTH.is_none() {
310
                bytes = self.null_handling.decode_nulls_if_needed(bytes)?;
669937
            }
670247
            let decoded = T::from_ord_bytes(bytes).map_err(CompositeKeyError::new)?;
670247
            self.offset = end;
670247
            if T::LENGTH.is_none() {
310
                // Variable fields always have an extra null byte to delimit the data
310
                self.offset += 1;
670223
            }
670247
            Ok(decoded)
        } else {
            Err(CompositeKeyError::new(io::Error::from(
                ErrorKind::UnexpectedEof,
            )))
        }
670247
    }

            
    /// Verifies the underlying byte slice has been fully consumed.
87585
    pub fn finish(self) -> Result<(), CompositeKeyError> {
87585
        if self.offset == self.end {
87585
            Ok(())
        } else {
            Err(CompositeKeyError::new(io::Error::from(
                ErrorKind::InvalidData,
            )))
        }
87585
    }
}

            
1
#[test]
1
fn composite_key_null_check_test() {
1
    let mut encoder = CompositeKeyEncoder::denying_null_bytes();
1
    encoder.encode(&vec![0_u8]).unwrap_err();
1

            
1
    let mut encoder = CompositeKeyEncoder::allowing_null_bytes();
1
    encoder.encode(&vec![0_u8]).unwrap();
1
    let bytes = encoder.finish();
1
    let mut decoder = CompositeKeyDecoder::allowing_null_bytes(ByteSource::Borrowed(&bytes));
1
    let decoded_value = decoder.decode::<Cow<'_, [u8]>>().unwrap();
1
    assert_eq!(decoded_value.as_ref(), &[0]);
1
    let mut decoder = CompositeKeyDecoder::denying_null_bytes(ByteSource::Borrowed(&bytes));
1
    let decoded_value = decoder.decode::<Cow<'_, [u8]>>().unwrap();
1
    assert_eq!(decoded_value.as_ref(), &[0]);

            
1
    let mut encoder = CompositeKeyEncoder::default();
1
    encoder.encode(&vec![1_u8, 0, 1]).unwrap();
1
    let bytes = encoder.finish();
1
    // One byte for the length, 3 original bytes, 1 escaped null, 1 field-delimiting null
1
    assert_eq!(bytes.len(), 6);
1
    let mut decoder = CompositeKeyDecoder::default_for(ByteSource::Borrowed(&bytes));
1
    let decoded_value = decoder.decode::<Cow<'_, [u8]>>().unwrap();
1
    assert_eq!(decoded_value.as_ref(), &[1, 0, 1]);
1
}

            
1
#[test]
#[allow(clippy::cognitive_complexity)] // There's no way to please clippy with this
1
fn composite_key_tests() {
1
    /// This test generates various combinations of every tuple type supported.
1
    /// Each test calls this function, which builds a second Vec containing all
1
    /// of the encoded key values. Next, both the original vec and the encoded
1
    /// vec are sorted. The encoded entries are decoded, and the sorted original
1
    /// vec is compared against the decoded vec to ensure the ordering is the
1
    /// same.
1
    ///
1
    /// The macros just make it less verbose to create the nested loops which
1
    /// create the tuples.
12
    fn verify_key_ordering<T: for<'k> Key<'k> + Ord + Eq + std::fmt::Debug>(
12
        mut cases: Vec<T>,
12
        already_ordered: bool,
12
    ) {
12
        let mut encoded = {
12
            cases
12
                .iter()
87391
                .map(|tuple| tuple.as_ord_bytes().unwrap().to_vec())
12
                .collect::<Vec<Vec<u8>>>()
12
        };
12
        if !already_ordered {
8
            cases.sort();
8
        }
12
        encoded.sort();
12
        println!("Tested {} entries", cases.len());
12
        let decoded = encoded
12
            .iter()
87391
            .map(|encoded| T::from_ord_bytes(ByteSource::Borrowed(encoded)).unwrap())
12
            .collect::<Vec<_>>();
12
        assert_eq!(cases, decoded);
12
    }
1

            
1
    // Simple mixed-length tests
1
    let a2 = (String::from("a"), 2_u8);
1
    let aa1 = (String::from("aa"), 1_u8);
1
    let aa2 = (String::from("aa"), 2_u8);
1
    let b1 = (String::from("b"), 1_u8);
1
    let b2 = (String::from("b"), 2_u8);
1
    verify_key_ordering(vec![a2.clone(), aa1.clone()], true);
1
    verify_key_ordering(vec![a2, aa1, aa2, b1, b2], true);
1

            
1
    // Two byte length (0x80)
1
    verify_key_ordering(
1
        vec![(vec![1; 127], vec![2; 128]), (vec![1; 128], vec![2; 127])],
1
        true,
1
    );
1
    // Three byte length (0x80)
1
    verify_key_ordering(
1
        vec![
1
            (vec![1; 16383], vec![1; 16384]),
1
            (vec![1; 16384], vec![2; 16383]),
1
        ],
1
        true,
1
    );
1

            
1
    let values = [0_u16, 0xFF00, 0x0FF0, 0xFF];
    macro_rules! test_enum_variations {
        ($($ident:ident),+) => {
            let mut cases = Vec::new();
            test_enum_variations!(for cases $($ident),+; $($ident),+);
            verify_key_ordering(cases, false);
        };
        (for $cases:ident $first:ident, $($ident:ident),+; $($variable:ident),+) => {
            for $first in values {
                test_enum_variations!(for $cases $($ident),+; $($variable),+);
            }
        };
        (for $cases:ident $first:ident; $($ident:ident),+) => {
            for $first in values {
                $cases.push(($($ident),+,));
            }
        };
    }
    macro_rules! recursive_test_enum_variations {
        ($ident:ident, $($last_ident:ident),+) => {
            recursive_test_enum_variations!($($last_ident),+);
            test_enum_variations!($ident, $($last_ident),+);
        };
        ($ident:ident) => {
            test_enum_variations!($ident);
        }
    }
87380
    recursive_test_enum_variations!(t1, t2, t3, t4, t5, t6, t7, t8);
1
}

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

            
impl CompositeKeyError {
    /// Returns a new instance wrapping `error`.
1
    pub fn new<E: AnyError>(error: E) -> Self {
1
        Self(Box::new(error))
1
    }
}

            
impl From<TryFromIntError> for CompositeKeyError {
    fn from(err: TryFromIntError) -> Self {
        Self::new(err)
    }
}

            
impl From<io::Error> for CompositeKeyError {
    fn from(err: io::Error) -> Self {
        Self::new(err)
    }
}

            
impl<'k> Key<'k> for Signed {
    const CAN_OWN_BYTES: bool = false;

            
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
        Self::decode_variable(bytes.as_ref())
    }

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

            
    fn next_value(&self) -> Result<Self, NextValueError> {
        i128::try_from(*self)
            .ok()
            .and_then(|key| key.checked_add(1))
            .map(Self::from)
            .ok_or(NextValueError::WouldWrap)
    }
}

            
impl KeyEncoding<Self> for Signed {
    type Error = io::Error;

            
    const LENGTH: Option<usize> = None;

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_type(KeyKind::Signed);
    }

            
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
        self.to_variable_vec().map(Cow::Owned)
    }
}

            
impl<'k> Key<'k> for Unsigned {
    const CAN_OWN_BYTES: bool = false;

            
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
        Self::decode_variable(bytes.as_ref())
    }

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

            
    fn next_value(&self) -> Result<Self, NextValueError> {
        u128::try_from(*self)
            .ok()
            .and_then(|key| key.checked_add(1))
            .map(Self::from)
            .ok_or(NextValueError::WouldWrap)
    }
}

            
impl KeyEncoding<Self> for Unsigned {
    type Error = io::Error;

            
    const LENGTH: Option<usize> = None;

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_type(KeyKind::Unsigned);
    }

            
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
        self.to_variable_vec().map(Cow::Owned)
    }
}

            
impl<'k> Key<'k> for isize {
    const CAN_OWN_BYTES: bool = false;

            
2
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
2
        Self::decode_variable(bytes.as_ref())
2
    }

            
    fn first_value() -> Result<Self, NextValueError> {
        Ok(0)
    }

            
    fn next_value(&self) -> Result<Self, NextValueError> {
        self.checked_add(1).ok_or(NextValueError::WouldWrap)
    }
}

            
impl KeyEncoding<Self> for isize {
    type Error = io::Error;

            
    const LENGTH: Option<usize> = None;

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_type(KeyKind::Signed);
    }

            
203
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
203
        self.to_variable_vec().map(Cow::Owned)
203
    }
}

            
impl<'k> Key<'k> for usize {
    const CAN_OWN_BYTES: bool = false;

            
2
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
2
        Self::decode_variable(bytes.as_ref())
2
    }

            
    fn first_value() -> Result<Self, NextValueError> {
        Ok(0)
    }

            
    fn next_value(&self) -> Result<Self, NextValueError> {
        self.checked_add(1).ok_or(NextValueError::WouldWrap)
    }
}

            
impl KeyEncoding<Self> for usize {
    type Error = io::Error;

            
    const LENGTH: Option<Self> = None;

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_type(KeyKind::Unsigned);
    }

            
3
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
3
        self.to_variable_vec().map(Cow::Owned)
3
    }
}

            
impl<'k> Key<'k> for NonZeroIsize {
    const CAN_OWN_BYTES: bool = false;

            
2
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
2
        let possibly_zero = isize::decode_variable(bytes.as_ref())?;
1
        Self::new(possibly_zero)
1
            .ok_or_else(|| io::Error::new(ErrorKind::InvalidData, NonZeroKeyError::ValueIsZero))
2
    }

            
1
    fn first_value() -> Result<Self, NextValueError> {
1
        Ok(Self::new(1).expect("one is not zero"))
1
    }

            
1
    fn next_value(&self) -> Result<Self, NextValueError> {
1
        let next = self.get().checked_add(1).ok_or(NextValueError::WouldWrap)?;
1
        Ok(Self::new(next)
1
            .unwrap_or_else(|| Self::first_value().expect("first_value returned error")))
1
    }
}

            
impl KeyEncoding<Self> for NonZeroIsize {
    type Error = io::Error;

            
    const LENGTH: Option<usize> = None;

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_type(KeyKind::Signed);
    }

            
2
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
2
        self.get().to_variable_vec().map(Cow::Owned)
2
    }
}

            
impl<'k> Key<'k> for NonZeroUsize {
    const CAN_OWN_BYTES: bool = false;

            
3
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
3
        let possibly_zero = usize::decode_variable(bytes.as_ref())?;
3
        Self::new(possibly_zero)
3
            .ok_or_else(|| io::Error::new(ErrorKind::InvalidData, NonZeroKeyError::ValueIsZero))
3
    }

            
    fn first_value() -> Result<Self, NextValueError> {
        Ok(Self::new(1).expect("one is not zero"))
    }

            
    fn next_value(&self) -> Result<Self, NextValueError> {
        self.checked_add(1).ok_or(NextValueError::WouldWrap)
    }
}

            
impl KeyEncoding<Self> for NonZeroUsize {
    type Error = io::Error;

            
    const LENGTH: Option<usize> = None;

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_type(KeyKind::Unsigned);
    }

            
3
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
3
        self.get().to_variable_vec().map(Cow::Owned)
3
    }
}

            
#[cfg(feature = "uuid")]
impl<'k> Key<'k> for uuid::Uuid {
    const CAN_OWN_BYTES: bool = false;

            
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
        Ok(Self::from_bytes(bytes.as_ref().try_into()?))
    }
}

            
#[cfg(feature = "uuid")]
impl KeyEncoding<Self> for uuid::Uuid {
    type Error = std::array::TryFromSliceError;

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

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_composite(CompositeKind::Struct(Cow::Borrowed("uuid::Uuid")), 1);
        visitor.visit_type(KeyKind::Bytes);
    }

            
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
        Ok(Cow::Borrowed(self.as_bytes()))
    }
}

            
fn decode_skipping_first_byte<'k, 'e, T>(bytes: ByteSource<'k, 'e>) -> Result<T, T::Error>
where
    T: Key<'k>,
{
    match bytes {
13255
        ByteSource::Borrowed(bytes) => T::from_ord_bytes(ByteSource::Borrowed(&bytes[1..])),
        ByteSource::Ephemeral(bytes) => T::from_ord_bytes(ByteSource::Ephemeral(&bytes[1..])),
        ByteSource::Owned(mut bytes) if T::CAN_OWN_BYTES => {
            bytes.remove(0);
            T::from_ord_bytes(ByteSource::Owned(bytes))
        }
        ByteSource::Owned(bytes) => T::from_ord_bytes(ByteSource::Ephemeral(&bytes[1..])),
    }
13255
}

            
impl<'k, T> Key<'k> for Option<T>
where
    T: Key<'k>,
    Self: KeyEncoding<Self, Error = <T as KeyEncoding<T>>::Error>,
{
    const CAN_OWN_BYTES: bool = T::CAN_OWN_BYTES;

            
160876652
    fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
160876652
        if bytes.as_ref().is_empty() || bytes.as_ref()[0] == 0 {
160863401
            Ok(None)
        } else {
13251
            decode_skipping_first_byte(bytes).map(Some)
        }
160876652
    }

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

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

            
impl<'k, T, K> KeyEncoding<Option<K>> for Option<T>
where
    T: KeyEncoding<K>,
    K: Key<'k>,
{
    type Error = T::Error;

            
    const LENGTH: Option<usize> = match T::LENGTH {
        Some(length) => Some(1 + length),
        None => None,
    };

            
960
    fn describe<Visitor>(visitor: &mut Visitor)
960
    where
960
        Visitor: KeyVisitor,
960
    {
960
        visitor.visit_composite(CompositeKind::Option, 1);
960
        T::describe(visitor);
960
    }

            
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
507931
        if let Some(contents) = self {
13890
            let mut contents = contents.as_ord_bytes()?.to_vec();
13890
            contents.insert(0, 1);
13890
            Ok(Cow::Owned(contents))
        } else {
494041
            Ok(Cow::Borrowed(b"\0"))
        }
507931
    }
}

            
const RESULT_OK: u8 = 0;
const RESULT_ERR: u8 = 1;

            
impl<'k, T, E> Key<'k> for Result<T, E>
where
    T: Key<'k>,
    E: Key<'k, Error = <T as KeyEncoding<T>>::Error>,
    Self: KeyEncoding<Self, Error = <T as KeyEncoding<T>>::Error>,
{
    const CAN_OWN_BYTES: bool = T::CAN_OWN_BYTES || E::CAN_OWN_BYTES;

            
4
    fn from_ord_bytes<'b>(bytes: ByteSource<'k, 'b>) -> Result<Self, Self::Error> {
4
        match bytes.as_ref().first() {
2
            Some(&RESULT_OK) => decode_skipping_first_byte(bytes).map(Ok),
2
            Some(_) => decode_skipping_first_byte(bytes).map(Err),
            None => {
                // Empty buffer, but we don't have an error type.
                E::from_ord_bytes(bytes).map(Err)
            }
        }
4
    }

            
1
    fn first_value() -> Result<Self, NextValueError> {
1
        Ok(Ok(T::first_value()?))
1
    }

            
2
    fn next_value(&self) -> Result<Self, NextValueError> {
2
        match self {
1
            Ok(value) => value.next_value().map(Ok),
1
            Err(err) => err.next_value().map(Err),
        }
2
    }
}

            
impl<'k, T, E, TBorrowed, EBorrowed> KeyEncoding<Result<T, E>> for Result<TBorrowed, EBorrowed>
where
    TBorrowed: KeyEncoding<T>,
    T: Key<'k, Error = TBorrowed::Error>,
    EBorrowed: KeyEncoding<E, Error = TBorrowed::Error>,
    E: Key<'k, Error = TBorrowed::Error>,
{
    type Error = <TBorrowed as KeyEncoding<T>>::Error;

            
    const LENGTH: Option<usize> = None;

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_composite(CompositeKind::Result, 2);
        TBorrowed::describe(visitor);
        EBorrowed::describe(visitor);
    }

            
4
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
4
        let (header, contents) = match self {
2
            Ok(value) => (RESULT_OK, value.as_ord_bytes()?),
2
            Err(value) => (RESULT_ERR, value.as_ord_bytes()?),
        };
4
        let mut contents = contents.to_vec();
4
        contents.insert(0, header);
4
        Ok(Cow::Owned(contents))
4
    }
}

            
1
#[test]
1
fn result_key_tests() {
1
    let ok_0 = Result::<u8, u16>::first_value().unwrap();
1
    let ok_1 = ok_0.next_value().unwrap();
1
    assert_eq!(ok_1, Ok(1));
1
    let ok_2 = Result::<u8, u16>::Ok(2_u8);
1
    let err_1 = Result::<u8, u16>::Err(1_u16);
1
    let err_2 = err_1.next_value().unwrap();
1
    assert_eq!(err_2, Err(2));
1
    let ok_1_encoded = ok_1.as_ord_bytes().unwrap();
1
    let ok_2_encoded = ok_2.as_ord_bytes().unwrap();
1
    let err_1_encoded = err_1.as_ord_bytes().unwrap();
1
    let err_2_encoded = err_2.as_ord_bytes().unwrap();
1
    assert!(ok_1_encoded < ok_2_encoded);
1
    assert!(ok_2_encoded < err_1_encoded);
1
    assert!(err_1_encoded < err_2_encoded);
1
    assert_eq!(
1
        Result::from_ord_bytes(ByteSource::Borrowed(&ok_1_encoded)).unwrap(),
1
        ok_1
1
    );
1
    assert_eq!(
1
        Result::from_ord_bytes(ByteSource::Borrowed(&ok_2_encoded)).unwrap(),
1
        ok_2
1
    );
1
    assert_eq!(
1
        Result::from_ord_bytes(ByteSource::Borrowed(&err_1_encoded)).unwrap(),
1
        err_1
1
    );
1
    assert_eq!(
1
        Result::from_ord_bytes(ByteSource::Borrowed(&err_2_encoded)).unwrap(),
1
        err_2
1
    );
1
}

            
/// Adds `Key` support to an enum. Requires implementing
/// [`ToPrimitive`](num_traits::ToPrimitive) and
/// [`FromPrimitive`](num_traits::FromPrimitive), or using a crate like
/// [num-derive](https://crates.io/crates/num-derive) to do it automatically.
/// Take care when using enums as keys: if the order changes or if the meaning
/// of existing numerical values changes, make sure to update any related views'
/// version number to ensure the values are re-evaluated.
#[derive(Debug, Clone, Copy, Eq, PartialEq, Ord, PartialOrd)]
pub struct EnumKey<T>(pub T)
where
    T: ToPrimitive + FromPrimitive + Clone + Eq + Ord + std::fmt::Debug + Send + Sync;

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

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

            
impl From<std::array::TryFromSliceError> for IncorrectByteLength {
    fn from(_: std::array::TryFromSliceError) -> Self {
        Self
    }
}

            
// ANCHOR: impl_key_for_enumkey
impl<'k, T> Key<'k> for EnumKey<T>
where
    T: ToPrimitive + FromPrimitive + Clone + Eq + Ord + std::fmt::Debug + Send + Sync,
{
    const CAN_OWN_BYTES: bool = false;

            
2
    fn from_ord_bytes<'b>(bytes: ByteSource<'k, 'b>) -> Result<Self, Self::Error> {
2
        let primitive = u64::decode_variable(bytes.as_ref())?;
2
        T::from_u64(primitive)
2
            .map(Self)
2
            .ok_or_else(|| io::Error::new(ErrorKind::InvalidData, UnknownEnumVariant))
2
    }
}

            
impl<T> KeyEncoding<Self> for EnumKey<T>
where
    T: ToPrimitive + FromPrimitive + Clone + Eq + Ord + std::fmt::Debug + Send + Sync,
{
    type Error = io::Error;

            
    const LENGTH: Option<usize> = None;

            
    fn describe<Visitor>(visitor: &mut Visitor)
    where
        Visitor: KeyVisitor,
    {
        visitor.visit_type(KeyKind::Unsigned);
    }

            
2
    fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
2
        let integer = self
2
            .0
2
            .to_u64()
2
            .map(Unsigned::from)
2
            .ok_or_else(|| io::Error::new(ErrorKind::InvalidData, IncorrectByteLength))?;
2
        Ok(Cow::Owned(integer.to_variable_vec()?))
2
    }
}
// ANCHOR_END: impl_key_for_enumkey

            
macro_rules! impl_key_for_primitive {
    ($type:ident, $keykind:expr) => {
        impl<'k> Key<'k> for $type {
            const CAN_OWN_BYTES: bool = false;

            
4355918
            fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
4355918
                Ok($type::from_be_bytes(bytes.as_ref().try_into()?))
4355918
            }

            
44121
            fn first_value() -> Result<Self, NextValueError> {
44121
                Ok(0)
44121
            }

            
649122
            fn next_value(&self) -> Result<Self, NextValueError> {
649122
                self.checked_add(1).ok_or(NextValueError::WouldWrap)
649122
            }
        }
        impl KeyEncoding<Self> for $type {
            type Error = IncorrectByteLength;

            
            const LENGTH: Option<usize> = Some(std::mem::size_of::<$type>());

            
5833523
            fn describe<Visitor>(visitor: &mut Visitor)
5833523
            where
5833523
                Visitor: KeyVisitor,
5833523
            {
5833523
                visitor.visit_type($keykind);
5833523
            }

            
4033249
            fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
4033249
                Ok(Cow::from(self.to_be_bytes().to_vec()))
4033249
            }
        }
    };
}

            
impl_key_for_primitive!(i8, KeyKind::I8);
impl_key_for_primitive!(u8, KeyKind::U8);
impl_key_for_primitive!(i16, KeyKind::I16);
impl_key_for_primitive!(u16, KeyKind::U16);
impl_key_for_primitive!(i32, KeyKind::I32);
impl_key_for_primitive!(u32, KeyKind::U32);
impl_key_for_primitive!(i64, KeyKind::I64);
impl_key_for_primitive!(u64, KeyKind::U64);
impl_key_for_primitive!(i128, KeyKind::I128);
impl_key_for_primitive!(u128, KeyKind::U128);

            
macro_rules! impl_key_for_nonzero_primitive {
    ($nonzero:ident, $type:ident) => {
        impl<'k> Key<'k> for $nonzero {
            const CAN_OWN_BYTES: bool = false;

            
30
            fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
30
                let contents = $type::from_be_bytes(bytes.as_ref().try_into()?);
30
                $nonzero::new(contents).ok_or(NonZeroKeyError::ValueIsZero)
30
            }

            
5
            fn first_value() -> Result<Self, NextValueError> {
5
                Ok($nonzero::new(1).expect("one is not zero"))
5
            }

            
5
            fn next_value(&self) -> Result<Self, NextValueError> {
                if let Some(nonzero) =
5
                    $nonzero::new(self.get().checked_add(1).ok_or(NextValueError::WouldWrap)?)
                {
                    Ok(nonzero)
                } else {
                    // Since we've done a checked_add, we know the only failure
                    // case here is going from negative to positive. In this
                    // sitaution, we skip 0.
5
                    Self::first_value()
                }
5
            }
        }

            
        impl KeyEncoding<Self> for $nonzero {
            type Error = NonZeroKeyError;

            
            const LENGTH: Option<usize> = Some(std::mem::size_of::<$type>());

            
            fn describe<Visitor>(visitor: &mut Visitor)
            where
                Visitor: KeyVisitor,
            {
                $type::describe(visitor);
            }

            
30
            fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
30
                Ok(Cow::from(self.get().to_be_bytes().to_vec()))
30
            }
        }
    };
}

            
impl_key_for_nonzero_primitive!(NonZeroI8, i8);
impl_key_for_nonzero_primitive!(NonZeroU8, u8);
impl_key_for_nonzero_primitive!(NonZeroI16, i16);
impl_key_for_nonzero_primitive!(NonZeroU16, u16);
impl_key_for_nonzero_primitive!(NonZeroI32, i32);
impl_key_for_nonzero_primitive!(NonZeroU32, u32);
impl_key_for_nonzero_primitive!(NonZeroI64, i64);
impl_key_for_nonzero_primitive!(NonZeroU64, u64);
impl_key_for_nonzero_primitive!(NonZeroI128, i128);
impl_key_for_nonzero_primitive!(NonZeroU128, u128);

            
/// An error occurred during a [`Key`] or [`KeyEncoding`] implementation for a
/// non-zero type.
#[derive(thiserror::Error, Debug)]
pub enum NonZeroKeyError {
    /// An incorrect number of bytes were encounted for the type specified.
    #[error("incorrect byte length")]
    IncorrectByteLength,
    /// A zero value was encountered for a non-zero type.
    #[error("zero is not valid for a non-zero type")]
    ValueIsZero,
}

            
impl From<std::array::TryFromSliceError> for NonZeroKeyError {
    fn from(_value: std::array::TryFromSliceError) -> Self {
        Self::IncorrectByteLength
    }
}

            
1
#[test]
#[allow(clippy::cognitive_complexity)] // I disagree - @ecton
1
fn primitive_key_encoding_tests() -> anyhow::Result<()> {
1
    macro_rules! test_primitive_extremes {
1
        ($type:ident) => {
1
            assert_eq!(
1
                &$type::MAX.to_be_bytes(),
1
                $type::MAX.as_ord_bytes()?.as_ref()
1
            );
1
            assert_eq!(
1
                $type::MAX,
1
                $type::from_ord_bytes(ByteSource::Borrowed(&$type::MAX.as_ord_bytes()?))?
1
            );
1
            assert_eq!(
1
                $type::MIN,
1
                $type::from_ord_bytes(ByteSource::Borrowed(&$type::MIN.as_ord_bytes()?))?
1
            );
1
        };
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
    assert_eq!(
1
        usize::from_ord_bytes(ByteSource::Borrowed(&usize::MAX.as_ord_bytes().unwrap())).unwrap(),
1
        usize::MAX
1
    );
1
    assert_eq!(
1
        usize::from_ord_bytes(ByteSource::Borrowed(&usize::MIN.as_ord_bytes().unwrap())).unwrap(),
1
        usize::MIN
1
    );
1
    assert_eq!(
1
        isize::from_ord_bytes(ByteSource::Borrowed(&isize::MAX.as_ord_bytes().unwrap())).unwrap(),
1
        isize::MAX
1
    );
1
    assert_eq!(
1
        isize::from_ord_bytes(ByteSource::Borrowed(&isize::MIN.as_ord_bytes().unwrap())).unwrap(),
1
        isize::MIN
1
    );

            
1
    Ok(())
1
}

            
1
#[test]
1
fn nonzero_key_encoding_tests() -> anyhow::Result<()> {
1
    macro_rules! test_nonzero {
1
        ($nonzero:ident, $inner:ident) => {
1
            let zero_bytes = [0; ($inner::BITS / 8) as usize];
1
            assert!(matches!(
1
                $nonzero::from_ord_bytes(ByteSource::Borrowed(&zero_bytes)),
1
                Err(NonZeroKeyError::ValueIsZero)
1
            ));
1
            let max = $nonzero::new($inner::MAX).unwrap();
1
            assert_eq!(&max.get().to_be_bytes(), max.as_ord_bytes()?.as_ref());
1
            assert_eq!(
1
                max,
1
                $nonzero::from_ord_bytes(ByteSource::Borrowed(&max.as_ord_bytes()?))?
1
            );
1
            let min = $nonzero::new(if $inner::MIN == 0 { 1 } else { $inner::MIN }).unwrap();
1
            assert_eq!(
1
                min,
1
                $nonzero::from_ord_bytes(ByteSource::Borrowed(&min.as_ord_bytes()?))?
1
            );
1
        };
1
    }
1
    macro_rules! test_signed {
1
        ($nonzero:ident, $inner:ident) => {
1
            test_nonzero!($nonzero, $inner);
1
            let negative_one = $nonzero::new(-1).unwrap();
1
            assert_eq!(negative_one.next_value().unwrap().get(), 1);
1
        };
1
    }
1

            
1
    test_nonzero!(NonZeroU8, u8);
1
    test_nonzero!(NonZeroU16, u16);
1
    test_nonzero!(NonZeroU32, u32);
1
    test_nonzero!(NonZeroU64, u64);
1
    test_nonzero!(NonZeroU128, u128);
1
    test_signed!(NonZeroI8, i8);
1
    test_signed!(NonZeroI16, i16);
1
    test_signed!(NonZeroI32, i32);
1
    test_signed!(NonZeroI64, i64);
1
    test_signed!(NonZeroI128, i128);

            
    // NonZeroUsize
1
    let zero_bytes = [0; (usize::BITS / 8) as usize];
1
    assert!(NonZeroUsize::from_ord_bytes(ByteSource::Borrowed(&zero_bytes)).is_err());
1
    let max = NonZeroUsize::new(usize::MAX).unwrap();
1
    assert_eq!(
1
        max.get().as_ord_bytes()?.as_ref(),
1
        max.as_ord_bytes()?.as_ref()
    );
1
    assert_eq!(
1
        max,
1
        NonZeroUsize::from_ord_bytes(ByteSource::Borrowed(&max.as_ord_bytes()?))?
    );
1
    let min = NonZeroUsize::new(1).unwrap();
1
    assert_eq!(
1
        min,
1
        NonZeroUsize::from_ord_bytes(ByteSource::Borrowed(&min.as_ord_bytes()?))?
    );

            
    // NonZeroIsize
1
    assert!(NonZeroIsize::from_ord_bytes(ByteSource::Borrowed(&zero_bytes)).is_err());
1
    let max = NonZeroIsize::new(isize::MAX).unwrap();
1
    assert_eq!(max.get().as_ord_bytes()?, max.as_ord_bytes()?.as_ref());
1
    let min = NonZeroIsize::new(isize::MIN).unwrap();
1
    assert_eq!(
1
        min,
1
        NonZeroIsize::from_ord_bytes(ByteSource::Borrowed(&min.as_ord_bytes()?))?
    );
1
    let negative_one = NonZeroIsize::new(-1).unwrap();
1
    assert_eq!(negative_one.next_value().unwrap().get(), 1);

            
1
    Ok(())
1
}

            
/// A Transmog [`Format`](transmog::Format) implementation that uses [`Key`] to
/// serialize and deserialize the contents.
2
#[derive(Default, Debug)]
pub struct KeyFormat;

            
impl KeyFormat {
1
    fn get_bytes<T: KeyEncoding>(value: &T) -> io::Result<Cow<'_, [u8]>> {
1
        value
1
            .as_ord_bytes()
1
            .map_err(|err| io::Error::new(ErrorKind::InvalidInput, err))
1
    }
}

            
impl<'a, T> transmog::Format<'a, T> for KeyFormat
where
    T: KeyEncoding,
{
    type Error = io::Error;

            
    fn serialize_into<W: io::Write>(&self, value: &T, mut writer: W) -> Result<(), Self::Error> {
        let data = Self::get_bytes(value)?;
        writer.write_all(&data)
    }

            
    fn serialized_size(&self, _value: &T) -> Result<Option<usize>, Self::Error> {
        Ok(T::LENGTH)
    }

            
1
    fn serialize(&self, value: &T) -> Result<Vec<u8>, Self::Error> {
1
        Ok(Self::get_bytes(value)?.into_owned())
1
    }
}

            
impl<'a, T> transmog::BorrowedDeserializer<'a, T> for KeyFormat
where
    T: Key<'a>,
{
1
    fn deserialize_borrowed(&self, data: &'a [u8]) -> Result<T, Self::Error> {
1
        T::from_ord_bytes(ByteSource::Borrowed(data))
1
            .map_err(|err| io::Error::new(ErrorKind::InvalidData, err))
1
    }
}

            
impl<T> transmog::OwnedDeserializer<T> for KeyFormat
where
    T: for<'a> Key<'a> + 'static,
{
    fn deserialize_from<R: io::Read>(&self, mut reader: R) -> Result<T, Self::Error> {
        let mut buffer = Vec::new();
        reader.read_to_end(&mut buffer)?;
        self.deserialize_owned(&buffer)
    }

            
1
    fn deserialize_owned(&self, data: &[u8]) -> Result<T, Self::Error> {
1
        let possibly_borrowed = self.deserialize_borrowed(data)?;
1
        Ok(possibly_borrowed)
1
    }
}

            
1
#[test]
1
fn optional_key_encoding_tests() -> anyhow::Result<()> {
1
    let some_string = Some("hello").as_ord_bytes()?;
1
    let empty_string = Some("").as_ord_bytes()?;
1
    let none_string = Option::<String>::None.as_ord_bytes()?;
1
    assert_eq!(
1
        Option::<String>::from_ord_bytes(ByteSource::Borrowed(&some_string))
1
            .unwrap()
1
            .as_deref(),
1
        Some("hello")
1
    );
1
    assert_eq!(
1
        Option::<String>::from_ord_bytes(ByteSource::Borrowed(&empty_string))
1
            .unwrap()
1
            .as_deref(),
1
        Some("")
1
    );
1
    assert_eq!(
1
        Option::<String>::from_ord_bytes(ByteSource::Borrowed(&none_string)).unwrap(),
1
        None
1
    );

            
    #[allow(deprecated)]
    {
1
        let some_string = OptionKeyV1(Some("hello")).as_ord_bytes()?.to_vec();
1
        let none_string = OptionKeyV1::<String>(None).as_ord_bytes()?;
1
        assert_eq!(
1
            OptionKeyV1::<String>::from_ord_bytes(ByteSource::Borrowed(&some_string))
1
                .unwrap()
1
                .0
1
                .as_deref(),
1
            Some("hello")
1
        );
1
        assert_eq!(
1
            OptionKeyV1::<String>::from_ord_bytes(ByteSource::Borrowed(&none_string))
1
                .unwrap()
1
                .0,
1
            None
1
        );
    }
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(ByteSource::Borrowed(&[]))?);
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(ByteSource::Borrowed(&true_as_bytes))?);
1
    assert!(!bool::from_ord_bytes(ByteSource::Borrowed(
1
        &false_as_bytes
1
    ))?);
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!(
1
        vec.clone(),
1
        Cow::<'_, [u8]>::from_ord_bytes(ByteSource::Borrowed(&vec.as_ord_bytes()?))?
    );
1
    Ok(())
1
}

            
1
#[test]
1
fn enum_derive_tests() -> anyhow::Result<()> {
    #[derive(
        Debug,
        Clone,
4
        num_derive::ToPrimitive,
2
        num_derive::FromPrimitive,
        Ord,
        PartialOrd,
        Eq,
        PartialEq,
    )]
    enum SomeEnum {
        One = 1,
        NineNineNine = 999,
    }

            
1
    let encoded = EnumKey(SomeEnum::One).as_ord_bytes()?;
1
    let value = EnumKey::<SomeEnum>::from_ord_bytes(ByteSource::Borrowed(&encoded))?;
1
    assert!(matches!(value.0, SomeEnum::One));

            
1
    let encoded = EnumKey(SomeEnum::NineNineNine).as_ord_bytes()?;
1
    let value = EnumKey::<SomeEnum>::from_ord_bytes(ByteSource::Borrowed(&encoded))?;
1
    assert!(matches!(value.0, SomeEnum::NineNineNine));

            
1
    Ok(())
1
}

            
1
#[test]
1
fn key_descriptions() {
1
    use time::limited::TimeEpoch;
1
    assert_eq!(
1
        KeyDescription::for_key::<Vec<u8>>(),
1
        KeyDescription::Basic(KeyKind::Bytes)
1
    );
1
    assert_eq!(
1
        dbg!(KeyDescription::for_key::<time::TimestampAsNanoseconds>()),
1
        KeyDescription::Composite(CompositeKeyDescription {
1
            kind: CompositeKind::Struct(Cow::Borrowed(
1
                "bonsaidb::core::key::time::LimitedResolutionTimestamp"
1
            )),
1
            fields: vec![KeyDescription::Basic(KeyKind::I64),],
1
            attributes: [(
1
                Cow::Borrowed("epoch"),
1
                KeyAttibuteValue::U128(time::limited::BonsaiEpoch::epoch_offset().as_nanos())
1
            )]
1
            .into_iter()
1
            .collect()
1
        })
1
    );
1
    assert_eq!(
1
        KeyDescription::for_key::<(u64, String, Bytes)>(),
1
        KeyDescription::Composite(CompositeKeyDescription {
1
            kind: CompositeKind::Tuple,
1
            fields: vec![
1
                KeyDescription::Basic(KeyKind::U64),
1
                KeyDescription::Basic(KeyKind::String),
1
                KeyDescription::Basic(KeyKind::Bytes),
1
            ],
1
            attributes: HashMap::new(),
1
        })
1
    );
1
}

            
1
#[test]
1
fn key_serialization() {
2
    #[derive(crate::schema::Collection, Key, Clone, Eq, PartialEq, Debug)]
1
    #[collection(core = crate, name = "test", serialization = Key)]
1
    #[key(core = crate)]
1
    struct Test {
1
        field: u64,
1
    }
1
    let start = Test { field: 42 };
1
    let encoded = <Test as crate::schema::SerializedCollection>::serialize(&start).unwrap();
1
    assert_eq!(encoded, &[0, 0, 0, 0, 0, 0, 0, 42]);
1
    let decoded = <Test as crate::schema::SerializedCollection>::deserialize(&encoded).unwrap();
1
    assert_eq!(decoded, start);
1
}