use std::ops::{Bound, RangeBounds};
use bytes::Bytes;
use crate::record::AsKey;
mod private {
pub trait Sealed {}
}
pub trait AsRange: private::Sealed {
#[doc(hidden)]
fn as_boundaries(&self) -> (Bytes, Bytes);
}
fn specify_boundaries(start_bound: Bound<&[u8]>, end_bound: Bound<&[u8]>) -> (Bytes, Bytes) {
let lower = match start_bound {
Bound::Included([]) | Bound::Unbounded => Bytes::from_static(&[0]),
Bound::Included(val) => Bytes::copy_from_slice(val.as_key()),
Bound::Excluded(val) => successor(val.as_key()).into(),
};
match end_bound {
Bound::Included([]) | Bound::Excluded([] | [0]) => {
let lower = lower.max(Bytes::from_static(&[0, 0]));
(lower.clone(), lower)
}
Bound::Included(val) => (lower, successor(val.as_key()).into()),
Bound::Excluded(val) => (lower, Bytes::copy_from_slice(val.as_key())),
Bound::Unbounded => (lower, Bytes::from_static(&[0])),
}
}
fn range_to_boundaries<R: RangeBounds<impl AsKey>>(range: &R) -> (Bytes, Bytes) {
specify_boundaries(
range.start_bound().map(AsKey::as_key),
range.end_bound().map(AsKey::as_key),
)
}
macro_rules! impl_as_range_for_range_type {
($template:ident) => {
impl<T: AsKey> private::Sealed for std::ops::$template<T> {}
impl<T: AsKey> AsRange for std::ops::$template<T> {
fn as_boundaries(&self) -> (Bytes, Bytes) {
range_to_boundaries(self)
}
}
};
($($template:ident),* $(,)?) => {
$(impl_as_range_for_range_type!($template);)*
}
}
impl_as_range_for_range_type! {
Range,
RangeInclusive,
RangeFrom,
RangeTo,
RangeToInclusive,
}
impl private::Sealed for std::ops::RangeFull {}
impl AsRange for std::ops::RangeFull {
fn as_boundaries(&self) -> (Bytes, Bytes) {
(Bytes::from_static(&[0]), Bytes::from_static(&[0]))
}
}
#[derive(Debug, Clone, Copy)]
pub struct Prefix<T: ?Sized>(pub T);
impl<T: AsKey + ?Sized> private::Sealed for Prefix<T> {}
impl<T: AsKey + ?Sized> AsRange for Prefix<T> {
fn as_boundaries(&self) -> (Bytes, Bytes) {
match self.0.as_key() {
[] => (..).as_boundaries(),
prefix => (Bytes::copy_from_slice(prefix), prefix_end(prefix).into()),
}
}
}
impl<T: AsKey + ?Sized> private::Sealed for T {}
impl<T: AsKey + ?Sized> AsRange for T {
fn as_boundaries(&self) -> (Bytes, Bytes) {
(Bytes::copy_from_slice(self.as_key()), Bytes::new())
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum TargetRange<'a> {
All,
Single(&'a [u8]),
Span(&'a [u8], &'a [u8]),
ToEnd(&'a [u8]),
}
impl<'a> TargetRange<'a> {
pub fn from_wire(key: &'a [u8], range_end: &'a [u8]) -> Self {
match (key, range_end) {
([0], [0]) => TargetRange::All,
(k, []) => TargetRange::Single(k),
(k, [0]) => TargetRange::ToEnd(k),
(k, e) => TargetRange::Span(k, e),
}
}
}
fn prefix_end(input: &[u8]) -> Vec<u8> {
let mut out = input.to_owned();
while let Some(last) = out.last_mut() {
if *last < u8::MAX {
*last += 1;
break;
} else {
out.pop();
}
}
if out.is_empty() {
out.push(0);
}
out
}
pub(crate) fn successor(input: &[u8]) -> Vec<u8> {
let mut out = Vec::with_capacity(input.len() + 1);
input.clone_into(&mut out);
out.push(0);
out
}
#[cfg(test)]
mod tests {
use super::{AsRange, Prefix, TargetRange, prefix_end};
#[track_caller]
fn assert_wire(range: impl AsRange, expected: TargetRange<'_>) {
let (key, range_end) = range.as_boundaries();
assert_eq!(TargetRange::from_wire(&key, &range_end), expected);
}
#[test]
fn target_range_from_wire() {
assert_eq!(TargetRange::from_wire(&[0], &[0]), TargetRange::All);
assert_eq!(TargetRange::from_wire(b"foo", b""), TargetRange::Single(b"foo"));
assert_eq!(TargetRange::from_wire(b"foo", &[0]), TargetRange::ToEnd(b"foo"));
assert_eq!(
TargetRange::from_wire(b"foo/", b"foo0"),
TargetRange::Span(b"foo/", b"foo0"),
);
}
#[test]
fn inclusive_upper_bound_ends_after_its_key() {
assert_wire("a"..="a", TargetRange::Span(b"a", b"a\0"));
assert_wire(..="b", TargetRange::Span(b"\0", b"b\0"));
assert_wire(..="\0", TargetRange::Span(b"\0", b"\0\0"));
assert_wire(..=b"\xff", TargetRange::Span(b"\0", b"\xff\0"));
}
#[test]
fn upper_bound_below_every_key_is_empty() {
assert_wire(..="", TargetRange::Span(b"\0\0", b"\0\0"));
assert_wire(.."", TargetRange::Span(b"\0\0", b"\0\0"));
assert_wire(.."\0", TargetRange::Span(b"\0\0", b"\0\0"));
assert_wire(""..="", TargetRange::Span(b"\0\0", b"\0\0"));
assert_wire("a"..="", TargetRange::Span(b"a", b"a"));
assert_wire("a".."", TargetRange::Span(b"a", b"a"));
assert_wire("a".."\0", TargetRange::Span(b"a", b"a"));
}
#[test]
fn empty_lower_bound_starts_at_the_first_key() {
assert_wire("".., TargetRange::All);
assert_wire(Prefix(""), TargetRange::All);
assert_wire("".."b", TargetRange::Span(b"\0", b"b"));
assert_wire(""..="b", TargetRange::Span(b"\0", b"b\0"));
assert_wire("", TargetRange::Single(b""));
}
#[test]
fn test_prefix_end() {
let cases: &[(&[u8], &[u8])] = &[
(b"aa", b"ab"),
(b"a\xff", b"b"),
(b"\xff", b"\0"),
(b"\xff\xff\xff", b"\0"),
];
for (input, expected) in cases {
let output = prefix_end(input);
assert_eq!(*expected, output);
}
}
}