Lines
77.03 %
Functions
32.67 %
Branches
100 %
/// [`Key`] implementations for time types.
pub mod time;
mod varint;
mod deprecated;
use std::any::type_name;
use std::borrow::{Borrow, Cow};
use std::collections::HashMap;
use std::convert::Infallible;
use std::io::{self, ErrorKind};
use std::num::{
NonZeroI128, NonZeroI16, NonZeroI32, NonZeroI64, NonZeroI8, NonZeroIsize, NonZeroU128,
NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU8, NonZeroUsize, TryFromIntError,
};
use std::ops::Deref;
use std::string::FromUtf8Error;
use arc_bytes::serde::{Bytes, CowBytes};
use arc_bytes::ArcBytes;
pub use bonsaidb_macros::Key;
pub use deprecated::*;
use num_traits::{FromPrimitive, ToPrimitive};
use ordered_varint::{Signed, Unsigned, Variable};
use serde::{Deserialize, Serialize};
use transmog::BorrowedDeserializer;
pub use varint::{VarInt, VariableInteger};
use crate::connection::{Bound, BoundRef, MaybeOwned, RangeRef};
use crate::AnyError;
/// A trait that enables a type to convert itself into a `memcmp`-compatible
/// sequence of bytes.
pub trait KeyEncoding<K = Self>: Send + Sync {
/// The error type that can be produced by either serialization or
/// deserialization.
type Error: AnyError;
/// The size of the key, if constant. If this type doesn't produce the same
/// number of bytes for each value, this should be `None`.
const LENGTH: Option<usize>;
/// Describes this type by invoking functions on `visitor` describing the
/// key being encoded.
///
/// See the [`KeyVisitor`] trait for more information.
/// [`KeyDescription::for_key()`]/[`KeyDescription::for_encoding()`] are
/// built-in functions
fn describe<Visitor>(visitor: &mut Visitor)
where
Visitor: KeyVisitor;
/// Convert `self` into a `Cow<'_, [u8]>` containing bytes that are able to be
/// compared via `memcmp` in a way that is comptaible with its own Ord
/// implementation.
fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error>;
}
/// # Deriving this trait
/// This trait can be derived on structs and enums whose members all implement
/// `Key`. It is important to note that the order of individual fields and enum
/// variants is important, so special care must be taken when updating enums and
/// structs when trying to preserve backwards compatibility with existing data.
/// ```rust
/// use bonsaidb_core::key::Key;
/// #[derive(Key, Clone, Debug)]
/// # #[key(core = bonsaidb_core)]
/// struct CompositeKey {
/// user_id: u64,
/// task_id: u32,
/// }
/// ```
/// Each field or enum variant is encoded and decoded in the order in which it
/// appears in the source code. The implementation uses [`CompositeKeyEncoder`]
/// and [`CompositeKeyDecoder`] to encode each field.
/// ## Changing the `enum` representation type
/// By default, the derived `Key` implementation will use an `isize` for its
/// representation, which is encoded using [`ordered_varint`]. If you wish to
/// use a fixed-size encoding or use `usize`, `enum_repr` can be used to control
/// the type being encoded.
/// The default behavior produces compact output for simple enums, but can also
/// support growing to the limits of `isize`:
/// use bonsaidb_core::key::{Key, KeyEncoding};
/// enum Color {
/// Red,
/// Green,
/// Blue,
/// let encoded = Color::Red.as_ord_bytes().unwrap();
/// assert_eq!(encoded.len(), 1);
/// If a `#[repr(...)]` attribute exists and its parameter is a built-in integer
/// type, the `Key` derive will use that type for its representation instead:
/// #[repr(u32)]
/// Red = 0xFF0000FF,
/// Green = 0x00FF00FF,
/// Blue = 0x0000FFFF,
/// assert_eq!(encoded.len(), 4);
/// If the type would rather use a different type for the key encoding than it
/// uses for in-memory representation, the `enum_repr` parameter can be used:
/// #[key(enum_repr = u32)]
/// #[repr(usize)]
/// ## `null_handling`
/// The derive macro offers an argument `null_handling`, which defaults to
/// `escape`. Escaping null bytes in variable length fields ensures all data
/// encoded will sort correctly. In situations where speed is more important
/// than sorting behavior, `allow` or `deny` can be specified. `allow` will
/// permit null bytes to pass through encoding and decoding without being
/// checked. `deny` will check for null bytes when encoding and return an error
/// if any are present.
/// Null bytes can cause problematic sort behavior when multiple variable-length
/// encoded fields are encoded as a composite key. Consider this example:
/// #[derive(Key, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
/// #[key(null_handling = allow)]
/// a: String,
/// b: String,
/// With this structure, we can cause sorting misbehaviors using this data set:
/// | `a` | `b` | Encoded Bytes |
/// |----------|-------|-----------------------|
/// | `"a"` | `"c"` | `6100 6300 0101` |
/// | `"a\0b"` | `"a"` | `6100 6200 610003 01` |
/// | `"b"` | `"a"` | `6200 6100 0101` |
/// In this table, `a` and `b` are ordered as `CompositeKey` would be ordered
/// when compared using `Ord`. However, the order of the encoded bytes does not
/// match.
/// This null-byte edge case only applies to variable length [`Key`]s
/// ([`KeyEncoding::LENGTH`] is `None`).
pub trait Key<'k>: KeyEncoding<Self> + Clone + Send + Sync {
/// If true, this type can benefit from an owned `Vec<u8>`. This flag is
/// used as a hint of whether to attempt to do memcpy operations in some
/// decoding operations to avoid extra allocations.
const CAN_OWN_BYTES: bool;
/// Deserialize a sequence of bytes previously encoded with
/// [`KeyEncoding::as_ord_bytes`].
fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error>;
/// Return the first value in sequence for this type. Not all types
/// implement this.
fn first_value() -> Result<Self, NextValueError> {
Err(NextValueError::Unsupported)
/// Return the next value in sequence for this type. Not all types implement
/// this. Instead of wrapping/overflowing, None should be returned.
fn next_value(&self) -> Result<Self, NextValueError> {
impl<'a, 'k, K, KE> KeyEncoding<K> for &'a KE
KE: KeyEncoding<K> + ?Sized + PartialEq,
K: Key<'k> + PartialEq<KE>,
{
type Error = KE::Error;
const LENGTH: Option<usize> = K::LENGTH;
Visitor: KeyVisitor,
KE::describe(visitor);
fn as_ord_bytes(&self) -> Result<Cow<'_, [u8]>, Self::Error> {
(*self).as_ord_bytes()
/// A Visitor for information about a [`KeyEncoding`].
/// This trait is used in [`KeyEncoding::describe`] to report information about
/// the type of data contained within the key. Using this information,
/// generically interpreting the bytes of a key type can be possible as long as
/// the key type uses [`CompositeKeyEncoder`].
/// This trait is not something that most users will ever need to implement.
/// Instead,
/// built-in functions to retrieve the information reported by this trait in an
/// easier-to-use interface.
pub trait KeyVisitor {
/// Report that a basic key type is encoded next in this key.
fn visit_type(&mut self, kind: KeyKind);
/// Report that a custom type is encoded next as a single byte sequence in
/// this key.
fn visit_other(&mut self, kind: impl Into<Cow<'static, str>>);
/// Report that a composite type made up of `count` fields is encoded next in
/// `KeyVisitor` implementations may panic if there are less than or more
/// than `count` fields reported by either `visit_type()` or
/// `visit_composite()`.
fn visit_composite(&mut self, kind: CompositeKind, count: usize);
/// Report that the current composite type has extra metadata.
/// This can be used to encode const generic parameters that are helpful in
/// interpretting the contents of a type. For example,
/// [`LimitedResolutionTimestamp`](time::limited::LimitedResolutionTimestamp)
/// uses this function to report the `TimeEpoch`'s nanoseconds since the
/// Unix epoch.
fn visit_composite_attribute(
&mut self,
key: impl Into<Cow<'static, str>>,
value: impl Into<KeyAttibuteValue>,
);
/// The type of a single field contained in a key.
#[derive(Debug, Eq, PartialEq, Clone, Serialize, Deserialize)]
pub enum KeyKind {
/// An `unit` type, encoded with no length.
Unit,
/// An `u8` encoded in big-endian encoding.
U8,
/// An `u16` encoded in big-endian encoding.
U16,
/// An `u32` encoded in big-endian encoding.
U32,
/// An `u64` encoded in big-endian encoding.
U64,
/// An `u128` encoded in big-endian encoding.
U128,
/// An `usize` encoded in big-endian encoding.
Usize,
/// An `i8` encoded in big-endian encoding.
I8,
/// An `i16` encoded in big-endian encoding.
I16,
/// An `i32` encoded in big-endian encoding.
I32,
/// An `i64` encoded in big-endian encoding.
I64,
/// An `i128` encoded in big-endian encoding.
I128,
/// An `isize` encoded in big-endian encoding.
Isize,
/// A [`Signed`] number encoded using [`ordered_varint`].
Signed,
/// An [`Unsigned`] number encoded using [`ordered_varint`].
Unsigned,
/// A `bool` encoded as a single byte.
Bool,
/// A String encoded using BonsaiDb's built-in `KeyEncoding`.
String,
/// A byte array encoded using BonsaiDb's built-in `KeyEncoding`.
Bytes,
/// A value used as part of [`KeyVisitor::visit_composite_attribute`].
pub enum KeyAttibuteValue {
/// An `u8` value.
U8(u8),
/// An `i8` value.
I8(i8),
/// An `u16` value.
U16(u16),
/// An `i16` value.
I16(i16),
/// An `u32` value.
U32(u32),
/// An `i32` value.
I32(i32),
/// An `u64` value.
U64(u64),
/// An `i64` value.
I64(i64),
/// An `u128` value.
U128(u128),
/// An `i128` value.
I128(i128),
/// An `usize` value.
Usize(usize),
/// An `isize` value.
Isize(isize),
/// A `bool` value.
Bool(bool),
/// A string value.
Str(Cow<'static, str>),
/// A byte array value.
Bytes(Cow<'static, [u8]>),
macro_rules! impl_const_key_from {
($from:ty, $constkey:expr) => {
impl From<$from> for KeyAttibuteValue {
fn from(value: $from) -> Self {
#[allow(clippy::redundant_closure_call)]
$constkey(value)
impl_const_key_from!(u8, KeyAttibuteValue::U8);
impl_const_key_from!(i8, KeyAttibuteValue::I8);
impl_const_key_from!(u16, KeyAttibuteValue::U16);
impl_const_key_from!(i16, KeyAttibuteValue::I16);
impl_const_key_from!(u32, KeyAttibuteValue::U32);
impl_const_key_from!(i32, KeyAttibuteValue::I32);
impl_const_key_from!(u64, KeyAttibuteValue::U64);
impl_const_key_from!(i64, KeyAttibuteValue::I64);
impl_const_key_from!(u128, KeyAttibuteValue::U128);
impl_const_key_from!(i128, KeyAttibuteValue::I128);
impl_const_key_from!(usize, KeyAttibuteValue::Usize);
impl_const_key_from!(isize, KeyAttibuteValue::Isize);
impl_const_key_from!(bool, KeyAttibuteValue::Bool);
impl_const_key_from!(&'static str, |s: &'static str| KeyAttibuteValue::Str(
Cow::Borrowed(s)
));
impl_const_key_from!(String, |s: String| KeyAttibuteValue::Str(Cow::Owned(s)));
impl_const_key_from!(&'static [u8], |b: &'static [u8]| KeyAttibuteValue::Bytes(
Cow::Borrowed(b)
impl_const_key_from!(Vec<u8>, |b: Vec<u8>| KeyAttibuteValue::Bytes(Cow::Owned(b)));
/// A description of the kind of a composite key.
pub enum CompositeKind {
/// An [`Option`], which always contains a single field.
Option,
/// An [`Result`], which reports two fields -- the first for the `Ok` type,
/// and the second for the `Err` type.
Result,
/// A sequence of fields.
Tuple,
/// A sequence of fields, identified by the fully qualified name. E.g.,
/// `"std::time::SystemTime"` is the value that the
/// [`SystemTime`](std::time::SystemTime)'s `KeyEncoding` implementation
/// reports.
Struct(Cow<'static, str>),
/// A description of an encoded [`Key`].
pub enum KeyDescription {
/// A basic key type.
Basic(KeyKind),
/// A composite key made up of more than one field.
Composite(CompositeKeyDescription),
/// Another type with a custom encoding format.
Other(Cow<'static, str>),
impl KeyDescription {
/// Returns a description of the given [`KeyEncoding`] implementor.
/// # Panics
/// This function will panic if `KE` emits an imbalanced sequence of visit
/// calls.
#[must_use]
pub fn for_encoding<KE: KeyEncoding<K>, K: for<'k> Key<'k> + 'static>() -> Self {
let mut describer = KeyDescriber::default();
KE::describe(&mut describer);
describer.finish_for::<K>()
/// Returns the description of a given [`Key`] implementor.
pub fn for_key<K: for<'k> Key<'k> + 'static>() -> Self {
Self::for_encoding::<K, K>()
/// A description of a multi-field key encoded using [`CompositeKeyEncoder`].
pub struct CompositeKeyDescription {
/// The kind of composite key.
pub kind: CompositeKind,
/// The fields contained within this key.
pub fields: Vec<KeyDescription>,
/// The attributes of this key.
pub attributes: HashMap<Cow<'static, str>, KeyAttibuteValue>,
#[derive(Default)]
struct KeyDescriber {
stack: Vec<CompositeKeyDescription>,
result: Option<KeyDescription>,
impl KeyDescriber {
fn record(&mut self, description: KeyDescription) {
match self.stack.last_mut() {
Some(composite) => {
composite.fields.push(description);
if composite.fields.len() == composite.fields.capacity() {
// The composite key is finished, pop the state.
let completed = self.stack.pop().expect("just matched");
self.record(KeyDescription::Composite(completed));
None => {
// Stack has been completed.
assert!(self.result.replace(description).is_none());
fn finish_for<T>(self) -> KeyDescription
T: 'static,
assert!(
self.stack.is_empty(),
"invalid KeyEncoding::describe implementation -- imbalanced visit calls"
self.result
.unwrap_or_else(|| KeyDescription::Other(Cow::Borrowed(type_name::<T>())))
impl KeyVisitor for KeyDescriber {
fn visit_type(&mut self, kind: KeyKind) {
let description = KeyDescription::Basic(kind);
self.record(description);
fn visit_other(&mut self, kind: impl Into<Cow<'static, str>>) {
self.record(KeyDescription::Other(kind.into()));
fn visit_composite(&mut self, kind: CompositeKind, count: usize) {
self.stack.push(CompositeKeyDescription {
kind,
fields: Vec::with_capacity(count),
attributes: HashMap::new(),
});
) {
let current = self
.stack
.last_mut()
.expect("visit_composite_attribute must be called only after visit_composite");
current.attributes.insert(key.into(), value.into());
/// The error types for [`Key::next_value()`].
#[derive(Clone, thiserror::Error, Debug, Serialize, Deserialize)]
pub enum NextValueError {
/// The key type does not support this operation.
#[error("the key type does not support automatic ids")]
Unsupported,
/// Generating a new value would wrap the underlying value.
#[error("the key type has run out of unique values")]
WouldWrap,
/// A source of bytes from a `&'borrowed [u8]`, `&'ephemeral [u8]` or `Vec<u8>`.
/// This is used by the [`Key`] trait to allow `'ephemeral` borrows of an owned
/// `Vec<u8>` while also allowing for code paths that support borrowing from a
/// `'borrowed` byte slice.
pub enum ByteSource<'borrowed, 'ephemeral> {
/// Borrowed bytes valid for `'borrowed`.
Borrowed(&'borrowed [u8]),
/// Borrowed bytes valid for `'ephemeral`.
Ephemeral(&'ephemeral [u8]),
/// Owned bytes.
Owned(Vec<u8>),
impl<'borrowed, 'ephemeral> ByteSource<'borrowed, 'ephemeral>
'borrowed: 'ephemeral,
/// Coerce a `ByteSource` into `Cow<'borrowed, [u8]>`
/// This will allocate if this is an `'ephemeral` reference.
pub fn into_borrowed(self) -> Cow<'borrowed, [u8]> {
match self {
Self::Borrowed(bytes) => Cow::Borrowed(bytes),
Self::Ephemeral(bytes) => Cow::Owned(Vec::from(bytes)),
Self::Owned(bytes) => Cow::Owned(bytes),
/// Coerce a `ByteSource` into a `Vec<u8>`
/// This will allocate if the source is `'borrowed` or `'ephemeral`.
#[allow(clippy::match_same_arms)] // Lifetimes are different.
pub fn into_owned(self) -> Vec<u8> {
Self::Borrowed(bytes) => Vec::from(bytes),
Self::Ephemeral(bytes) => Vec::from(bytes),
Self::Owned(bytes) => bytes,
impl<'borrowed, 'ephemeral> AsRef<[u8]> for ByteSource<'borrowed, 'ephemeral> {
fn as_ref(&self) -> &[u8] {
Self::Borrowed(bytes) => bytes,
Self::Ephemeral(bytes) => bytes,
Self::Owned(ref bytes) => bytes.as_slice(),
impl<'borrowed, 'ephemeral> Deref for ByteSource<'borrowed, 'ephemeral> {
type Target = [u8];
fn deref(&self) -> &Self::Target {
self.as_ref()
impl<'borrowed, 'ephemeral> Default for ByteSource<'borrowed, 'ephemeral> {
fn default() -> Self {
Self::Owned(Vec::default())
impl<'borrowed, 'ephemeral> From<Cow<'borrowed, [u8]>> for ByteSource<'borrowed, 'ephemeral> {
fn from(cow: Cow<'borrowed, [u8]>) -> Self {
match cow {
Cow::Borrowed(bytes) => ByteSource::Borrowed(bytes),
Cow::Owned(bytes) => ByteSource::Owned(bytes),
/// A type that can be used as a prefix range in range-based queries.
pub trait IntoPrefixRange<'a, TOwned>: PartialEq
TOwned: Borrow<Self> + PartialEq<Self>,
/// Returns the value as a prefix-range, which will match all values that
/// start with `self`.
fn to_prefix_range(&'a self) -> RangeRef<'a, TOwned, Self>;
fn next_byte_sequence(start: &[u8]) -> Option<Vec<u8>> {
let mut end = start.to_vec();
// Modify the last byte by adding one. If it would wrap, we proceed to the
// next byte.
while let Some(last_byte) = end.pop() {
if let Some(next) = last_byte.checked_add(1) {
end.push(next);
return Some(end);
None
impl<'k> Key<'k> for Cow<'k, [u8]> {
const CAN_OWN_BYTES: bool = true;
fn from_ord_bytes<'e>(bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
Ok(bytes.into_borrowed())
impl<'k, 'ke> KeyEncoding<Cow<'ke, [u8]>> for Cow<'k, [u8]> {
type Error = Infallible;
const LENGTH: Option<usize> = None;
visitor.visit_type(KeyKind::Bytes);
Ok(self.clone())
macro_rules! impl_u8_slice_key_encoding {
($type:ty) => {
impl<'k> KeyEncoding<$type> for &'k [u8] {
visitor.visit_type(KeyKind::Bytes)
Ok(Cow::Borrowed(self))
impl_u8_slice_key_encoding!(Cow<'k, [u8]>);
impl<'a, 'k> IntoPrefixRange<'a, Self> for Cow<'k, [u8]> {
fn to_prefix_range(&'a self) -> RangeRef<'a, Self> {
if let Some(next) = next_byte_sequence(self) {
RangeRef {
start: BoundRef::borrowed(Bound::Included(self)),
end: BoundRef::owned(Bound::Excluded(Cow::Owned(next))),
} else {
end: BoundRef::Unbounded,
impl<'a, 'k, TOwned, TBorrowed> Key<'k> for MaybeOwned<'a, TOwned, TBorrowed>
TBorrowed: KeyEncoding<TOwned, Error = TOwned::Error> + PartialEq + ?Sized,
TOwned: Key<'k> + PartialEq<TBorrowed>,
const CAN_OWN_BYTES: bool = TOwned::CAN_OWN_BYTES;
TOwned::from_ord_bytes(bytes).map(Self::Owned)
impl<'a, 'k, TOwned, TBorrowed> KeyEncoding<Self> for MaybeOwned<'a, TOwned, TBorrowed>
type Error = TOwned::Error;
const LENGTH: Option<usize> = TBorrowed::LENGTH;
TBorrowed::describe(visitor);
MaybeOwned::Owned(value) => value.as_ord_bytes(),
MaybeOwned::Borrowed(value) => value.as_ord_bytes(),
#[test]
fn cow_prefix_range_tests() {
use std::ops::RangeBounds;
assert!(Cow::<'_, [u8]>::Borrowed(b"a")
.to_prefix_range()
.contains(&Cow::Borrowed(&b"aa"[..])));
assert!(!Cow::<'_, [u8]>::Borrowed(b"a")
.contains(&Cow::Borrowed(&b"b"[..])));
assert!(Cow::<'_, [u8]>::Borrowed(b"\xff")
.contains(&Cow::Borrowed(&b"\xff\xff"[..])));
assert!(!Cow::<'_, [u8]>::Borrowed(b"\xff")
.contains(&Cow::Borrowed(&b"\xfe"[..])));
impl<'k> Key<'k> for Vec<u8> {
Ok(bytes.into_owned())
impl KeyEncoding<Self> for Vec<u8> {
impl_u8_slice_key_encoding!(Vec<u8>);
impl<'k> IntoPrefixRange<'k, Self> for Vec<u8> {
fn to_prefix_range(&'k self) -> RangeRef<'k, Self> {
end: BoundRef::owned(Bound::Excluded(next)),
impl<'k, const N: usize> Key<'k> for [u8; N] {
const CAN_OWN_BYTES: bool = false;
if bytes.as_ref().len() == N {
let mut array = [0; N];
array.copy_from_slice(bytes.as_ref());
Ok(array)
Err(IncorrectByteLength)
impl<const N: usize> KeyEncoding<Self> for [u8; N] {
type Error = IncorrectByteLength;
const LENGTH: Option<usize> = Some(N);
fn vec_prefix_range_tests() {
assert!(b"a".to_vec().to_prefix_range().contains(&b"aa".to_vec()));
assert!(!b"a".to_vec().to_prefix_range().contains(&b"b".to_vec()));
assert!(b"\xff"
.to_vec()
.contains(&b"\xff\xff".to_vec()));
assert!(!b"\xff"
.contains(&b"\xfe".to_vec()));
impl<'k> Key<'k> for ArcBytes<'k> {
fn from_ord_bytes<'b>(bytes: ByteSource<'k, 'b>) -> Result<Self, Self::Error> {
Ok(Self::from(bytes.into_borrowed()))
impl<'k> KeyEncoding<Self> for ArcBytes<'k> {
impl_u8_slice_key_encoding!(ArcBytes<'k>);
impl<'a, 'k> IntoPrefixRange<'a, Self> for ArcBytes<'k> {
end: BoundRef::owned(Bound::Excluded(Self::owned(next))),
fn arcbytes_prefix_range_tests() {
assert!(ArcBytes::from(b"a")
.contains(&ArcBytes::from(b"aa")));
assert!(!ArcBytes::from(b"a")
.contains(&ArcBytes::from(b"b")));
assert!(ArcBytes::from(b"\xff")
.contains(&ArcBytes::from(b"\xff\xff")));
assert!(!ArcBytes::from(b"\xff")
.contains(&ArcBytes::from(b"\xfe")));
impl<'k> Key<'k> for CowBytes<'k> {
Ok(Self(bytes.into_borrowed()))
impl<'k> KeyEncoding<Self> for CowBytes<'k> {
Ok(self.0.clone())
impl_u8_slice_key_encoding!(CowBytes<'k>);
impl<'a, 'k> IntoPrefixRange<'a, Self> for CowBytes<'k> {
fn to_prefix_range(&'a self) -> RangeRef<'_, Self> {
end: BoundRef::owned(Bound::Excluded(Self::from(next))),
fn cowbytes_prefix_range_tests() {
assert!(CowBytes::from(&b"a"[..])
.contains(&CowBytes::from(&b"aa"[..])));
assert!(!CowBytes::from(&b"a"[..])
.contains(&CowBytes::from(&b"b"[..])));
assert!(CowBytes::from(&b"\xff"[..])
.contains(&CowBytes::from(&b"\xff\xff"[..])));
assert!(!CowBytes::from(&b"\xff"[..])
.contains(&CowBytes::from(&b"\xfe"[..])));
impl<'k> Key<'k> for Bytes {
Ok(Self(bytes.into_owned()))
impl KeyEncoding<Self> for Bytes {
impl_u8_slice_key_encoding!(Bytes);
impl<'a> IntoPrefixRange<'a, Self> for Bytes {
fn bytes_prefix_range_tests() {
assert!(Bytes::from(b"a".to_vec())
.contains(&Bytes::from(b"aa".to_vec())));
assert!(!Bytes::from(b"a".to_vec())
.contains(&Bytes::from(b"b".to_vec())));
assert!(Bytes::from(b"\xff".to_vec())
.contains(&Bytes::from(b"\xff\xff".to_vec())));
assert!(!Bytes::from(b"\xff".to_vec())
.contains(&Bytes::from(b"\xfe".to_vec())));
impl<'k> Key<'k> for String {
Self::from_utf8(bytes.into_owned())
impl KeyEncoding<Self> for String {
type Error = FromUtf8Error;
visitor.visit_type(KeyKind::String);
Ok(Cow::Borrowed(self.as_bytes()))
impl KeyEncoding<String> for str {
impl<'a> IntoPrefixRange<'a, Self> for String {
let mut bytes = self.as_bytes().to_vec();
for (index, char) in self.char_indices().rev() {
let mut next_char = u32::from(char) + 1;
if next_char == 0xd800 {
next_char = 0xE000;
} else if next_char > u32::from(char::MAX) {
continue;
let mut char_bytes = [0; 6];
bytes.splice(
index..,
char::try_from(next_char)
.unwrap()
.encode_utf8(&mut char_bytes)
.bytes(),
return RangeRef {
end: BoundRef::owned(Bound::Excluded(Self::from_utf8(bytes).unwrap())),
impl<'a> IntoPrefixRange<'a, String> for str {
fn to_prefix_range(&'a self) -> RangeRef<'a, String, Self> {
end: BoundRef::owned(Bound::Excluded(String::from_utf8(bytes).unwrap())),
impl<'k> Key<'k> for Cow<'k, str> {
match bytes.into_borrowed() {
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()),
impl<'k> KeyEncoding<Self> for Cow<'k, str> {
type Error = std::str::Utf8Error;
fn string_prefix_range_tests() {
assert!(String::from("a")
.contains(&String::from("aa")));
assert!(!String::from("a")
.contains(&String::from("b")));
assert!(String::from("\u{d799}")
.contains(&String::from("\u{d799}a")));
assert!(!String::from("\u{d799}")
.contains(&String::from("\u{e000}")));
assert!(String::from("\u{10ffff}")
.contains(&String::from("\u{10ffff}a")));
assert!(!String::from("\u{10ffff}")
.contains(&String::from("\u{10fffe}")));
impl<'k> Key<'k> for () {
fn from_ord_bytes<'b>(_: ByteSource<'k, 'b>) -> Result<Self, Self::Error> {
Ok(())
impl KeyEncoding<Self> for () {
const LENGTH: Option<usize> = Some(0);
visitor.visit_type(KeyKind::Unit);
Ok(Cow::default())
impl<'k> Key<'k> for bool {
let bytes = bytes.as_ref();
if bytes.is_empty() || bytes[0] == 0 {
Ok(false)
Ok(true)
impl KeyEncoding<Self> for bool {
const LENGTH: Option<usize> = Some(1);
visitor.visit_type(KeyKind::Bool);
if *self {
Ok(Cow::Borrowed(&[1_u8]))
Ok(Cow::Borrowed(&[0_u8]))
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),+,)
$($generic: for<'ke> Key<'ke>),+
let mut decoder = CompositeKeyDecoder::default_for(bytes);
$(let $varname = decoder.decode::<$generic>()?;)+
decoder.finish()?;
Ok(($($varname),+,))
impl<$($generic),+> KeyEncoding<Self> for ($($generic),+,)
$($generic: for<'k> Key<'k>),+
type Error = CompositeKeyError;
const LENGTH: Option<usize> = match ($($generic::LENGTH),+,) {
($(Some($varname)),+,) => Some($($varname +)+ 0),
_ => None,
visitor.visit_composite(CompositeKind::Tuple, count_args!($($generic) +));
$($generic::describe(visitor);)+
let mut encoder = CompositeKeyEncoder::default();
$(encoder.encode(&self.$index)?;)+
Ok(Cow::Owned(encoder.finish()))
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)
(4, t5, T5),
(5, t6, T6)
(5, t6, T6),
(6, t7, T7)
(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>
NullHandling: CompositeKeyNullHandler,
/// Encodes a single [`KeyEncoding`] implementing value.
/// # 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");
pub fn encode<'k, K: Key<'k>, T: KeyEncoding<K> + ?Sized>(
value: &'k T,
) -> Result<(), CompositeKeyError> {
let mut encoded = T::as_ord_bytes(value).map_err(CompositeKeyError::new)?;
if T::LENGTH.is_none() {
self.null_handling.handle_nulls(&mut encoded)?;
let encoded_length = u16::try_from(encoded.len())?;
self.encoded_lengths.push(encoded_length);
self.bytes.extend_from_slice(&encoded);
// With variable length data, we need the key to have a delimiter to
// ensure that "a" sorts before "aa".
self.bytes.push(0);
/// Finishes encoding the field and returns the encoded bytes.
#[allow(clippy::missing_panics_doc)] // All unreachable
pub fn finish(mut self) -> Vec<u8> {
self.bytes.reserve_exact(self.encoded_lengths.len() * 2);
for length in self.encoded_lengths.into_iter().rev() {
match length {
0..=0x7F => {
self.bytes.push(u8::try_from(length).unwrap());
0x80..=0x3FFF => {
self.bytes.push(u8::try_from(length >> 7).unwrap());
self.bytes
.push(u8::try_from((length & 0x7F) | 0x80).unwrap());
0x4000.. => {
self.bytes.push(u8::try_from(length >> 14).unwrap());
.push(u8::try_from(((length >> 7) & 0x7F) | 0x80).unwrap());
impl Default for CompositeKeyEncoder<EscapeNullBytes> {
Self {
bytes: Vec::new(),
encoded_lengths: Vec::new(),
null_handling: EscapeNullBytes,
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.
pub const fn allowing_null_bytes() -> Self {
null_handling: AllowNullBytes,
impl CompositeKeyEncoder<DenyNullBytes> {
/// Returns an encoder that denies null bytes in variable length fields by
/// returning an error when any null bytes are detected.
pub const fn denying_null_bytes() -> Self {
null_handling: DenyNullBytes,
/// 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.
pub struct AllowNullBytes;
/// 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]
fn handle_nulls(&self, encoded: &mut Cow<'_, [u8]>) -> Result<(), CompositeKeyError> {
if encoded.iter().any(|b| *b == 0) {
Err(CompositeKeyError::new(io::Error::new(
ErrorKind::InvalidData,
CompositeKeyFieldContainsNullByte,
)))
) -> Result<ByteSource<'b, 'e>, CompositeKeyError> {
Ok(encoded)
impl CompositeKeyNullHandler for AllowNullBytes {
fn handle_nulls(&self, _encoded: &mut Cow<'_, [u8]>) -> Result<(), CompositeKeyError> {
impl CompositeKeyNullHandler for EscapeNullBytes {
fn handle_nulls(&self, unescaped: &mut Cow<'_, [u8]>) -> Result<(), CompositeKeyError> {
let null_bytes = bytecount::count(unescaped, 0);
if null_bytes > 0 {
let mut null_encoded = Vec::with_capacity(unescaped.len() + null_bytes);
for unescaped in unescaped.as_ref() {
if *unescaped == 0 {
null_encoded.extend_from_slice(&[0, 0]);
null_encoded.push(*unescaped);
*unescaped = Cow::Owned(null_encoded);
mut encoded: ByteSource<'b, 'e>,
// Find the first null byte
if let Some(mut index) = encoded
.iter()
.enumerate()
.find_map(|(index, b)| (*b == 0).then_some(index))
// The field has at least one null byte, we need to mutate the
// bytes.
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.
let next_index = index + 1;
if Some(0) == bytes.get(next_index).copied() {
bytes.remove(index);
index = next_index;
todo!("error: unescaped null byte")
// return Err(CompositeKeyError::new("unescaped null byte encountered"));
// Find the next null byte, if one exists.
let Some(next_index) = bytes[index..]
else {
break;
index += next_index;
encoded = ByteSource::Owned(bytes);
/// 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,
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()`].
pub fn default_for(bytes: ByteSource<'key, 'ephemeral>) -> Self {
end: bytes.as_ref().len(),
bytes,
offset: 0,
impl<'key, 'ephemeral> CompositeKeyDecoder<'key, 'ephemeral, AllowNullBytes> {
/// Returns a decoder for `bytes` that ignores null bytes.
/// [`CompositeKeyEncoder::allowing_null_bytes()`].
pub fn allowing_null_bytes(bytes: ByteSource<'key, 'ephemeral>) -> Self {
impl<'key, 'ephemeral> CompositeKeyDecoder<'key, 'ephemeral, DenyNullBytes> {
/// [`CompositeKeyEncoder::denying_null_bytes()`].
pub fn denying_null_bytes(bytes: ByteSource<'key, 'ephemeral>) -> Self {
impl<'key, 'ephemeral, NullHandling> CompositeKeyDecoder<'key, 'ephemeral, NullHandling>
/// Decodes a value previously encoded using [`CompositeKeyEncoder`]. Calls
/// to decode must be made in the same order as the values were encoded in.
pub fn decode<T: Key<'key>>(&mut self) -> Result<T, CompositeKeyError> {
let length = if let Some(length) = T::LENGTH {
length
// Read a variable-encoded length from the tail of the bytes.
let mut length = 0;
let mut found_end = false;
let bytes = self.bytes.as_ref();
let iterator = bytes[self.offset..self.end]
.copied()
.rev()
.enumerate();
for (index, byte) in iterator {
length |= usize::from(byte & 0x7f) << (index * 7);
if byte & 0x80 == 0 {
self.end = self.end - index - 1;
found_end = true;
if !found_end {
return Err(CompositeKeyError::new(io::Error::from(
ErrorKind::UnexpectedEof,
)));
let end = self.offset + length;
if end <= self.end {
let mut bytes = match &self.bytes {
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]),
bytes = self.null_handling.decode_nulls_if_needed(bytes)?;
let decoded = T::from_ord_bytes(bytes).map_err(CompositeKeyError::new)?;
self.offset = end;
// Variable fields always have an extra null byte to delimit the data
self.offset += 1;
Ok(decoded)
Err(CompositeKeyError::new(io::Error::from(
/// Verifies the underlying byte slice has been fully consumed.
pub fn finish(self) -> Result<(), CompositeKeyError> {
if self.offset == self.end {
fn composite_key_null_check_test() {
let mut encoder = CompositeKeyEncoder::denying_null_bytes();
encoder.encode(&vec![0_u8]).unwrap_err();
let mut encoder = CompositeKeyEncoder::allowing_null_bytes();
encoder.encode(&vec![0_u8]).unwrap();
let bytes = encoder.finish();
let mut decoder = CompositeKeyDecoder::allowing_null_bytes(ByteSource::Borrowed(&bytes));
let decoded_value = decoder.decode::<Cow<'_, [u8]>>().unwrap();
assert_eq!(decoded_value.as_ref(), &[0]);
let mut decoder = CompositeKeyDecoder::denying_null_bytes(ByteSource::Borrowed(&bytes));
encoder.encode(&vec![1_u8, 0, 1]).unwrap();
// One byte for the length, 3 original bytes, 1 escaped null, 1 field-delimiting null
assert_eq!(bytes.len(), 6);
let mut decoder = CompositeKeyDecoder::default_for(ByteSource::Borrowed(&bytes));
assert_eq!(decoded_value.as_ref(), &[1, 0, 1]);
#[allow(clippy::cognitive_complexity)] // There's no way to please clippy with this
fn composite_key_tests() {
/// This test generates various combinations of every tuple type supported.
/// Each test calls this function, which builds a second Vec containing all
/// of the encoded key values. Next, both the original vec and the encoded
/// vec are sorted. The encoded entries are decoded, and the sorted original
/// vec is compared against the decoded vec to ensure the ordering is the
/// same.
/// The macros just make it less verbose to create the nested loops which
/// create the tuples.
fn verify_key_ordering<T: for<'k> Key<'k> + Ord + Eq + std::fmt::Debug>(
mut cases: Vec<T>,
already_ordered: bool,
let mut encoded = {
cases
.map(|tuple| tuple.as_ord_bytes().unwrap().to_vec())
.collect::<Vec<Vec<u8>>>()
if !already_ordered {
cases.sort();
encoded.sort();
println!("Tested {} entries", cases.len());
let decoded = encoded
.map(|encoded| T::from_ord_bytes(ByteSource::Borrowed(encoded)).unwrap())
.collect::<Vec<_>>();
assert_eq!(cases, decoded);
// Simple mixed-length tests
let a2 = (String::from("a"), 2_u8);
let aa1 = (String::from("aa"), 1_u8);
let aa2 = (String::from("aa"), 2_u8);
let b1 = (String::from("b"), 1_u8);
let b2 = (String::from("b"), 2_u8);
verify_key_ordering(vec![a2.clone(), aa1.clone()], true);
verify_key_ordering(vec![a2, aa1, aa2, b1, b2], true);
// Two byte length (0x80)
verify_key_ordering(
vec![(vec![1; 127], vec![2; 128]), (vec![1; 128], vec![2; 127])],
true,
// Three byte length (0x80)
vec![
(vec![1; 16383], vec![1; 16384]),
(vec![1; 16384], vec![2; 16383]),
],
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),+) => {
$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);
recursive_test_enum_variations!(t1, t2, t3, t4, t5, t6, t7, t8);
/// An error occurred inside of one of the composite key fields.
#[error("key error: {0}")]
pub struct CompositeKeyError(Box<dyn AnyError>);
impl CompositeKeyError {
/// Returns a new instance wrapping `error`.
pub fn new<E: AnyError>(error: E) -> Self {
Self(Box::new(error))
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 {
impl<'k> Key<'k> for Signed {
Self::decode_variable(bytes.as_ref())
Ok(Self::from(0_i128))
i128::from(*self)
.checked_add(1)
.map(Self::from)
.ok_or(NextValueError::WouldWrap)
impl KeyEncoding<Self> for Signed {
type Error = io::Error;
visitor.visit_type(KeyKind::Signed);
self.to_variable_vec().map(Cow::Owned)
impl<'k> Key<'k> for Unsigned {
Ok(Self::from(0_u128))
u128::from(*self)
impl KeyEncoding<Self> for Unsigned {
visitor.visit_type(KeyKind::Unsigned);
impl<'k> Key<'k> for isize {
Ok(0)
self.checked_add(1).ok_or(NextValueError::WouldWrap)
impl KeyEncoding<Self> for isize {
impl<'k> Key<'k> for usize {
impl KeyEncoding<Self> for usize {
const LENGTH: Option<Self> = None;
impl<'k> Key<'k> for NonZeroIsize {
let possibly_zero = isize::decode_variable(bytes.as_ref())?;
Self::new(possibly_zero)
.ok_or_else(|| io::Error::new(ErrorKind::InvalidData, NonZeroKeyError::ValueIsZero))
Ok(Self::new(1).expect("one is not zero"))
let next = self.get().checked_add(1).ok_or(NextValueError::WouldWrap)?;
Ok(Self::new(next)
.unwrap_or_else(|| Self::first_value().expect("first_value returned error")))
impl KeyEncoding<Self> for NonZeroIsize {
self.get().to_variable_vec().map(Cow::Owned)
impl<'k> Key<'k> for NonZeroUsize {
let possibly_zero = usize::decode_variable(bytes.as_ref())?;
impl KeyEncoding<Self> for NonZeroUsize {
#[cfg(feature = "uuid")]
impl<'k> Key<'k> for uuid::Uuid {
Ok(Self::from_bytes(bytes.as_ref().try_into()?))
impl KeyEncoding<Self> for uuid::Uuid {
type Error = std::array::TryFromSliceError;
const LENGTH: Option<usize> = Some(16);
visitor.visit_composite(CompositeKind::Struct(Cow::Borrowed("uuid::Uuid")), 1);
fn decode_skipping_first_byte<'k, 'e, T>(bytes: ByteSource<'k, 'e>) -> Result<T, T::Error>
T: Key<'k>,
match bytes {
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..])),
impl<'k, T> Key<'k> for Option<T>
Self: KeyEncoding<Self, Error = <T as KeyEncoding<T>>::Error>,
const CAN_OWN_BYTES: bool = T::CAN_OWN_BYTES;
if bytes.as_ref().is_empty() || bytes.as_ref()[0] == 0 {
Ok(None)
decode_skipping_first_byte(bytes).map(Some)
Ok(Some(T::first_value()?))
self.as_ref().map(T::next_value).transpose()
impl<'k, T, K> KeyEncoding<Option<K>> for Option<T>
T: KeyEncoding<K>,
K: Key<'k>,
type Error = T::Error;
const LENGTH: Option<usize> = match T::LENGTH {
Some(length) => Some(1 + length),
None => None,
visitor.visit_composite(CompositeKind::Option, 1);
T::describe(visitor);
if let Some(contents) = self {
let mut contents = contents.as_ord_bytes()?.to_vec();
contents.insert(0, 1);
Ok(Cow::Owned(contents))
Ok(Cow::Borrowed(b"\0"))
const RESULT_OK: u8 = 0;
const RESULT_ERR: u8 = 1;
impl<'k, T, E> Key<'k> for Result<T, E>
E: Key<'k, Error = <T as KeyEncoding<T>>::Error>,
const CAN_OWN_BYTES: bool = T::CAN_OWN_BYTES || E::CAN_OWN_BYTES;
match bytes.as_ref().first() {
Some(&RESULT_OK) => decode_skipping_first_byte(bytes).map(Ok),
Some(_) => decode_skipping_first_byte(bytes).map(Err),
// Empty buffer, but we don't have an error type.
E::from_ord_bytes(bytes).map(Err)
Ok(Ok(T::first_value()?))
Ok(value) => value.next_value().map(Ok),
Err(err) => err.next_value().map(Err),
impl<'k, T, E, TBorrowed, EBorrowed> KeyEncoding<Result<T, E>> for Result<TBorrowed, EBorrowed>
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;
visitor.visit_composite(CompositeKind::Result, 2);
EBorrowed::describe(visitor);
let (header, contents) = match self {
Ok(value) => (RESULT_OK, value.as_ord_bytes()?),
Err(value) => (RESULT_ERR, value.as_ord_bytes()?),
let mut contents = contents.to_vec();
contents.insert(0, header);
fn result_key_tests() {
let ok_0 = Result::<u8, u16>::first_value().unwrap();
let ok_1 = ok_0.next_value().unwrap();
assert_eq!(ok_1, Ok(1));
let ok_2 = Result::<u8, u16>::Ok(2_u8);
let err_1 = Result::<u8, u16>::Err(1_u16);
let err_2 = err_1.next_value().unwrap();
assert_eq!(err_2, Err(2));
let ok_1_encoded = ok_1.as_ord_bytes().unwrap();
let ok_2_encoded = ok_2.as_ord_bytes().unwrap();
let err_1_encoded = err_1.as_ord_bytes().unwrap();
let err_2_encoded = err_2.as_ord_bytes().unwrap();
assert!(ok_1_encoded < ok_2_encoded);
assert!(ok_2_encoded < err_1_encoded);
assert!(err_1_encoded < err_2_encoded);
assert_eq!(
Result::from_ord_bytes(ByteSource::Borrowed(&ok_1_encoded)).unwrap(),
ok_1
Result::from_ord_bytes(ByteSource::Borrowed(&ok_2_encoded)).unwrap(),
ok_2
Result::from_ord_bytes(ByteSource::Borrowed(&err_1_encoded)).unwrap(),
err_1
Result::from_ord_bytes(ByteSource::Borrowed(&err_2_encoded)).unwrap(),
err_2
/// 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)
T: ToPrimitive + FromPrimitive + Clone + Eq + Ord + std::fmt::Debug + Send + Sync;
/// An error that indicates an unexpected number of bytes were present.
#[error("incorrect byte length")]
pub struct IncorrectByteLength;
/// An error that indicates an unexpected enum variant value was found.
#[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>
T: ToPrimitive + FromPrimitive + Clone + Eq + Ord + std::fmt::Debug + Send + Sync,
let primitive = u64::decode_variable(bytes.as_ref())?;
T::from_u64(primitive)
.map(Self)
.ok_or_else(|| io::Error::new(ErrorKind::InvalidData, UnknownEnumVariant))
impl<T> KeyEncoding<Self> for EnumKey<T>
let integer = self
.0
.to_u64()
.map(Unsigned::from)
.ok_or_else(|| io::Error::new(ErrorKind::InvalidData, IncorrectByteLength))?;
Ok(Cow::Owned(integer.to_variable_vec()?))
// ANCHOR_END: impl_key_for_enumkey
macro_rules! impl_key_for_primitive {
($type:ident, $keykind:expr) => {
impl<'k> Key<'k> for $type {
Ok($type::from_be_bytes(bytes.as_ref().try_into()?))
impl KeyEncoding<Self> for $type {
const LENGTH: Option<usize> = Some(std::mem::size_of::<$type>());
visitor.visit_type($keykind);
Ok(Cow::from(self.to_be_bytes().to_vec()))
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 {
let contents = $type::from_be_bytes(bytes.as_ref().try_into()?);
$nonzero::new(contents).ok_or(NonZeroKeyError::ValueIsZero)
Ok($nonzero::new(1).expect("one is not zero"))
if let Some(nonzero) =
$nonzero::new(self.get().checked_add(1).ok_or(NextValueError::WouldWrap)?)
Ok(nonzero)
// 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.
Self::first_value()
impl KeyEncoding<Self> for $nonzero {
type Error = NonZeroKeyError;
$type::describe(visitor);
Ok(Cow::from(self.get().to_be_bytes().to_vec()))
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.
pub enum NonZeroKeyError {
/// An incorrect number of bytes were encounted for the type specified.
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
#[allow(clippy::cognitive_complexity)] // I disagree - @ecton
fn primitive_key_encoding_tests() -> anyhow::Result<()> {
macro_rules! test_primitive_extremes {
($type:ident) => {
&$type::MAX.to_be_bytes(),
$type::MAX.as_ord_bytes()?.as_ref()
$type::MAX,
$type::from_ord_bytes(ByteSource::Borrowed(&$type::MAX.as_ord_bytes()?))?
$type::MIN,
$type::from_ord_bytes(ByteSource::Borrowed(&$type::MIN.as_ord_bytes()?))?
test_primitive_extremes!(i8);
test_primitive_extremes!(u8);
test_primitive_extremes!(i16);
test_primitive_extremes!(u16);
test_primitive_extremes!(i32);
test_primitive_extremes!(u32);
test_primitive_extremes!(i64);
test_primitive_extremes!(u64);
test_primitive_extremes!(i128);
test_primitive_extremes!(u128);
usize::from_ord_bytes(ByteSource::Borrowed(&usize::MAX.as_ord_bytes().unwrap())).unwrap(),
usize::MAX
usize::from_ord_bytes(ByteSource::Borrowed(&usize::MIN.as_ord_bytes().unwrap())).unwrap(),
usize::MIN
isize::from_ord_bytes(ByteSource::Borrowed(&isize::MAX.as_ord_bytes().unwrap())).unwrap(),
isize::MAX
isize::from_ord_bytes(ByteSource::Borrowed(&isize::MIN.as_ord_bytes().unwrap())).unwrap(),
isize::MIN
fn nonzero_key_encoding_tests() -> anyhow::Result<()> {
macro_rules! test_nonzero {
($nonzero:ident, $inner:ident) => {
let zero_bytes = [0; ($inner::BITS / 8) as usize];
assert!(matches!(
$nonzero::from_ord_bytes(ByteSource::Borrowed(&zero_bytes)),
Err(NonZeroKeyError::ValueIsZero)
let max = $nonzero::new($inner::MAX).unwrap();
assert_eq!(&max.get().to_be_bytes(), max.as_ord_bytes()?.as_ref());
max,
$nonzero::from_ord_bytes(ByteSource::Borrowed(&max.as_ord_bytes()?))?
let min = $nonzero::new(if $inner::MIN == 0 { 1 } else { $inner::MIN }).unwrap();
min,
$nonzero::from_ord_bytes(ByteSource::Borrowed(&min.as_ord_bytes()?))?
macro_rules! test_signed {
test_nonzero!($nonzero, $inner);
let negative_one = $nonzero::new(-1).unwrap();
assert_eq!(negative_one.next_value().unwrap().get(), 1);
test_nonzero!(NonZeroU8, u8);
test_nonzero!(NonZeroU16, u16);
test_nonzero!(NonZeroU32, u32);
test_nonzero!(NonZeroU64, u64);
test_nonzero!(NonZeroU128, u128);
test_signed!(NonZeroI8, i8);
test_signed!(NonZeroI16, i16);
test_signed!(NonZeroI32, i32);
test_signed!(NonZeroI64, i64);
test_signed!(NonZeroI128, i128);
// NonZeroUsize
let zero_bytes = [0; (usize::BITS / 8) as usize];
assert!(NonZeroUsize::from_ord_bytes(ByteSource::Borrowed(&zero_bytes)).is_err());
let max = NonZeroUsize::new(usize::MAX).unwrap();
max.get().as_ord_bytes()?.as_ref(),
max.as_ord_bytes()?.as_ref()
NonZeroUsize::from_ord_bytes(ByteSource::Borrowed(&max.as_ord_bytes()?))?
let min = NonZeroUsize::new(1).unwrap();
NonZeroUsize::from_ord_bytes(ByteSource::Borrowed(&min.as_ord_bytes()?))?
// NonZeroIsize
assert!(NonZeroIsize::from_ord_bytes(ByteSource::Borrowed(&zero_bytes)).is_err());
let max = NonZeroIsize::new(isize::MAX).unwrap();
assert_eq!(max.get().as_ord_bytes()?, max.as_ord_bytes()?.as_ref());
let min = NonZeroIsize::new(isize::MIN).unwrap();
NonZeroIsize::from_ord_bytes(ByteSource::Borrowed(&min.as_ord_bytes()?))?
let negative_one = NonZeroIsize::new(-1).unwrap();
/// A Transmog [`Format`](transmog::Format) implementation that uses [`Key`] to
/// serialize and deserialize the contents.
#[derive(Default, Debug)]
pub struct KeyFormat;
impl KeyFormat {
fn get_bytes<T: KeyEncoding>(value: &T) -> io::Result<Cow<'_, [u8]>> {
value
.as_ord_bytes()
.map_err(|err| io::Error::new(ErrorKind::InvalidInput, err))
impl<'a, T> transmog::Format<'a, T> for KeyFormat
T: KeyEncoding,
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)
fn serialize(&self, value: &T) -> Result<Vec<u8>, Self::Error> {
Ok(Self::get_bytes(value)?.into_owned())
impl<'a, T> transmog::BorrowedDeserializer<'a, T> for KeyFormat
T: Key<'a>,
fn deserialize_borrowed(&self, data: &'a [u8]) -> Result<T, Self::Error> {
T::from_ord_bytes(ByteSource::Borrowed(data))
.map_err(|err| io::Error::new(ErrorKind::InvalidData, err))
impl<T> transmog::OwnedDeserializer<T> for KeyFormat
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)
fn deserialize_owned(&self, data: &[u8]) -> Result<T, Self::Error> {
let possibly_borrowed = self.deserialize_borrowed(data)?;
Ok(possibly_borrowed)
fn optional_key_encoding_tests() -> anyhow::Result<()> {
let some_string = Some("hello").as_ord_bytes()?;
let empty_string = Some("").as_ord_bytes()?;
let none_string = Option::<String>::None.as_ord_bytes()?;
Option::<String>::from_ord_bytes(ByteSource::Borrowed(&some_string))
.as_deref(),
Some("hello")
Option::<String>::from_ord_bytes(ByteSource::Borrowed(&empty_string))
Some("")
Option::<String>::from_ord_bytes(ByteSource::Borrowed(&none_string)).unwrap(),
#[allow(deprecated)]
let some_string = OptionKeyV1(Some("hello")).as_ord_bytes()?.to_vec();
let none_string = OptionKeyV1::<String>(None).as_ord_bytes()?;
OptionKeyV1::<String>::from_ord_bytes(ByteSource::Borrowed(&some_string))
OptionKeyV1::<String>::from_ord_bytes(ByteSource::Borrowed(&none_string))
.0,
#[allow(clippy::unit_cmp)] // this is more of a compilation test
fn unit_key_encoding_tests() -> anyhow::Result<()> {
assert!(().as_ord_bytes()?.is_empty());
assert_eq!((), <() as Key>::from_ord_bytes(ByteSource::Borrowed(&[]))?);
fn bool_key_encoding_tests() -> anyhow::Result<()> {
let true_as_bytes = true.as_ord_bytes()?;
let false_as_bytes = false.as_ord_bytes()?;
assert!(bool::from_ord_bytes(ByteSource::Borrowed(&true_as_bytes))?);
assert!(!bool::from_ord_bytes(ByteSource::Borrowed(
&false_as_bytes
))?);
fn vec_key_encoding_tests() -> anyhow::Result<()> {
const ORIGINAL_VALUE: &[u8] = b"bonsaidb";
let vec = Cow::<'_, [u8]>::from(ORIGINAL_VALUE);
vec.clone(),
Cow::<'_, [u8]>::from_ord_bytes(ByteSource::Borrowed(&vec.as_ord_bytes()?))?
fn enum_derive_tests() -> anyhow::Result<()> {
#[derive(
Debug,
Clone,
num_derive::ToPrimitive,
num_derive::FromPrimitive,
Ord,
PartialOrd,
Eq,
PartialEq,
)]
enum SomeEnum {
One = 1,
NineNineNine = 999,
let encoded = EnumKey(SomeEnum::One).as_ord_bytes()?;
let value = EnumKey::<SomeEnum>::from_ord_bytes(ByteSource::Borrowed(&encoded))?;
assert!(matches!(value.0, SomeEnum::One));
let encoded = EnumKey(SomeEnum::NineNineNine).as_ord_bytes()?;
assert!(matches!(value.0, SomeEnum::NineNineNine));
fn key_descriptions() {
use time::limited::TimeEpoch;
#[derive(Clone)]
struct NoDescriptionKey;
impl<'k> Key<'k> for NoDescriptionKey {
fn from_ord_bytes<'e>(_bytes: ByteSource<'k, 'e>) -> Result<Self, Self::Error> {
Ok(NoDescriptionKey)
impl KeyEncoding<NoDescriptionKey> for NoDescriptionKey {
fn describe<Visitor>(_visitor: &mut Visitor)
Ok(Cow::Borrowed(b""))
KeyDescription::for_key::<Vec<u8>>(),
KeyDescription::Basic(KeyKind::Bytes)
dbg!(KeyDescription::for_key::<time::TimestampAsNanoseconds>()),
KeyDescription::Composite(CompositeKeyDescription {
kind: CompositeKind::Struct(Cow::Borrowed(
"bonsaidb::core::key::time::LimitedResolutionTimestamp"
)),
fields: vec![KeyDescription::Basic(KeyKind::I64),],
attributes: [(
Cow::Borrowed("epoch"),
KeyAttibuteValue::U128(time::limited::BonsaiEpoch::epoch_offset().as_nanos())
.into_iter()
.collect()
})
KeyDescription::for_key::<(u64, String, Bytes)>(),
kind: CompositeKind::Tuple,
fields: vec![
KeyDescription::Basic(KeyKind::U64),
KeyDescription::Basic(KeyKind::String),
KeyDescription::Basic(KeyKind::Bytes),
KeyDescription::for_key::<NoDescriptionKey>(),
KeyDescription::Other(Cow::Borrowed(
"bonsaidb_core::key::key_descriptions::NoDescriptionKey"
))
fn key_serialization() {
#[derive(crate::schema::Collection, Key, Clone, Eq, PartialEq, Debug)]
#[collection(core = crate, name = "test", serialization = Key)]
#[key(core = crate)]
struct Test {
field: u64,
let start = Test { field: 42 };
let encoded = <Test as crate::schema::SerializedCollection>::serialize(&start).unwrap();
assert_eq!(encoded, &[0, 0, 0, 0, 0, 0, 0, 42]);
let decoded = <Test as crate::schema::SerializedCollection>::deserialize(&encoded).unwrap();
assert_eq!(decoded, start);