redb/
types.rs

Help
1use std::cmp::Ordering;
2use std::convert::TryInto;
3use std::fmt::Debug;
4use std::mem::size_of;
5
6#[derive(Eq, PartialEq, Clone, Debug)]
7enum TypeClassification {
8    Internal,
9    UserDefined,
10}
11
12impl TypeClassification {
13    fn to_byte(&self) -> u8 {
14        match self {
15            TypeClassification::Internal => 1,
16            TypeClassification::UserDefined => 2,
17        }
18    }
19
20    fn from_byte(value: u8) -> Self {
21        match value {
22            1 => TypeClassification::Internal,
23            2 => TypeClassification::UserDefined,
24            _ => unreachable!(),
25        }
26    }
27}
28
29#[derive(Eq, PartialEq, Debug, Clone)]
30pub struct TypeName {
31    classification: TypeClassification,
32    name: String,
33}
34
35impl TypeName {
36    /// It is recommended that `name` be prefixed with the crate name to minimize the chance of
37    /// it coliding with another user defined type
38    pub fn new(name: &str) -> Self {
39        Self {
40            classification: TypeClassification::UserDefined,
41            name: name.to_string(),
42        }
43    }
44
45    pub(crate) fn internal(name: &str) -> Self {
46        Self {
47            classification: TypeClassification::Internal,
48            name: name.to_string(),
49        }
50    }
51
52    pub(crate) fn to_bytes(&self) -> Vec<u8> {
53        let mut result = Vec::with_capacity(self.name.as_bytes().len() + 1);
54        result.push(self.classification.to_byte());
55        result.extend_from_slice(self.name.as_bytes());
56        result
57    }
58
59    pub(crate) fn from_bytes(bytes: &[u8]) -> Self {
60        let classification = TypeClassification::from_byte(bytes[0]);
61        let name = std::str::from_utf8(&bytes[1..]).unwrap().to_string();
62
63        Self {
64            classification,
65            name,
66        }
67    }
68
69    pub(crate) fn name(&self) -> &str {
70        &self.name
71    }
72}
73
74pub trait Value: Debug {
75    /// `SelfType<'a>` must be the same type as Self with all lifetimes replaced with 'a
76    type SelfType<'a>: Debug + 'a
77    where
78        Self: 'a;
79
80    type AsBytes<'a>: AsRef<[u8]> + 'a
81    where
82        Self: 'a;
83
84    /// Width of a fixed type, or None for variable width
85    fn fixed_width() -> Option<usize>;
86
87    /// Deserializes data
88    /// Implementations may return a view over data, or an owned type
89    fn from_bytes<'a>(data: &'a [u8]) -> Self::SelfType<'a>
90    where
91        Self: 'a;
92
93    /// Serialize the value to a slice
94    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> Self::AsBytes<'a>
95    where
96        Self: 'b;
97
98    /// Globally unique identifier for this type
99    fn type_name() -> TypeName;
100}
101
102/// Implementing this trait indicates that the type can be mutated in-place as a &mut [u8].
103/// This enables the `.insert_reserve()` method on Table
104pub trait MutInPlaceValue: Value {
105    /// The base type such that &mut [u8] can be safely transmuted to `&mut BaseRefType`
106    type BaseRefType: Debug + ?Sized;
107
108    // Initialize `data` to a valid value. This method will be called (at some point, not necessarily immediately)
109    // before from_bytes_mut() is called on a slice.
110    fn initialize(data: &mut [u8]);
111
112    fn from_bytes_mut(data: &mut [u8]) -> &mut Self::BaseRefType;
113}
114
115impl MutInPlaceValue for &[u8] {
116    type BaseRefType = [u8];
117
118    fn initialize(_data: &mut [u8]) {
119        // no-op. All values are valid.
120    }
121
122    fn from_bytes_mut(data: &mut [u8]) -> &mut Self::BaseRefType {
123        data
124    }
125}
126
127pub trait Key: Value {
128    /// Compare data1 with data2
129    fn compare(data1: &[u8], data2: &[u8]) -> Ordering;
130}
131
132impl Value for () {
133    type SelfType<'a> = ()
134    where
135        Self: 'a;
136    type AsBytes<'a> = &'a [u8]
137    where
138        Self: 'a;
139
140    fn fixed_width() -> Option<usize> {
141        Some(0)
142    }
143
144    #[allow(clippy::unused_unit, clippy::semicolon_if_nothing_returned)]
145    fn from_bytes<'a>(_data: &'a [u8]) -> ()
146    where
147        Self: 'a,
148    {
149        ()
150    }
151
152    #[allow(clippy::ignored_unit_patterns)]
153    fn as_bytes<'a, 'b: 'a>(_: &'a Self::SelfType<'b>) -> &'a [u8]
154    where
155        Self: 'b,
156    {
157        &[]
158    }
159
160    fn type_name() -> TypeName {
161        TypeName::internal("()")
162    }
163}
164
165impl Key for () {
166    fn compare(_data1: &[u8], _data2: &[u8]) -> Ordering {
167        Ordering::Equal
168    }
169}
170
171impl Value for bool {
172    type SelfType<'a> = bool
173        where
174            Self: 'a;
175    type AsBytes<'a> = &'a [u8]
176        where
177            Self: 'a;
178
179    fn fixed_width() -> Option<usize> {
180        Some(1)
181    }
182
183    fn from_bytes<'a>(data: &'a [u8]) -> bool
184    where
185        Self: 'a,
186    {
187        match data[0] {
188            0 => false,
189            1 => true,
190            _ => unreachable!(),
191        }
192    }
193
194    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> &'a [u8]
195    where
196        Self: 'b,
197    {
198        match value {
199            true => &[1],
200            false => &[0],
201        }
202    }
203
204    fn type_name() -> TypeName {
205        TypeName::internal("bool")
206    }
207}
208
209impl Key for bool {
210    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
211        let value1 = Self::from_bytes(data1);
212        let value2 = Self::from_bytes(data2);
213        value1.cmp(&value2)
214    }
215}
216
217impl<T: Value> Value for Option<T> {
218    type SelfType<'a> = Option<T::SelfType<'a>>
219    where
220        Self: 'a;
221    type AsBytes<'a> = Vec<u8>
222    where
223        Self: 'a;
224
225    fn fixed_width() -> Option<usize> {
226        T::fixed_width().map(|x| x + 1)
227    }
228
229    fn from_bytes<'a>(data: &'a [u8]) -> Option<T::SelfType<'a>>
230    where
231        Self: 'a,
232    {
233        match data[0] {
234            0 => None,
235            1 => Some(T::from_bytes(&data[1..])),
236            _ => unreachable!(),
237        }
238    }
239
240    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> Vec<u8>
241    where
242        Self: 'b,
243    {
244        let mut result = vec![0];
245        if let Some(x) = value {
246            result[0] = 1;
247            result.extend_from_slice(T::as_bytes(x).as_ref());
248        } else if let Some(fixed_width) = T::fixed_width() {
249            result.extend_from_slice(&vec![0; fixed_width]);
250        }
251        result
252    }
253
254    fn type_name() -> TypeName {
255        TypeName::internal(&format!("Option<{}>", T::type_name().name()))
256    }
257}
258
259impl<T: Key> Key for Option<T> {
260    #[allow(clippy::collapsible_else_if)]
261    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
262        if data1[0] == 0 {
263            if data2[0] == 0 {
264                Ordering::Equal
265            } else {
266                Ordering::Less
267            }
268        } else {
269            if data2[0] == 0 {
270                Ordering::Greater
271            } else {
272                T::compare(&data1[1..], &data2[1..])
273            }
274        }
275    }
276}
277
278impl Value for &[u8] {
279    type SelfType<'a> = &'a [u8]
280    where
281        Self: 'a;
282    type AsBytes<'a> = &'a [u8]
283    where
284        Self: 'a;
285
286    fn fixed_width() -> Option<usize> {
287        None
288    }
289
290    fn from_bytes<'a>(data: &'a [u8]) -> &'a [u8]
291    where
292        Self: 'a,
293    {
294        data
295    }
296
297    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> &'a [u8]
298    where
299        Self: 'b,
300    {
301        value
302    }
303
304    fn type_name() -> TypeName {
305        TypeName::internal("&[u8]")
306    }
307}
308
309impl Key for &[u8] {
310    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
311        data1.cmp(data2)
312    }
313}
314
315impl<const N: usize> Value for &[u8; N] {
316    type SelfType<'a> = &'a [u8; N]
317    where
318        Self: 'a;
319    type AsBytes<'a> = &'a [u8; N]
320    where
321        Self: 'a;
322
323    fn fixed_width() -> Option<usize> {
324        Some(N)
325    }
326
327    fn from_bytes<'a>(data: &'a [u8]) -> &'a [u8; N]
328    where
329        Self: 'a,
330    {
331        data.try_into().unwrap()
332    }
333
334    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> &'a [u8; N]
335    where
336        Self: 'b,
337    {
338        value
339    }
340
341    fn type_name() -> TypeName {
342        TypeName::internal(&format!("[u8;{N}]"))
343    }
344}
345
346impl<const N: usize> Key for &[u8; N] {
347    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
348        data1.cmp(data2)
349    }
350}
351
352impl<const N: usize, T: Value> Value for [T; N] {
353    type SelfType<'a> = [T::SelfType<'a>; N]
354        where
355            Self: 'a;
356    type AsBytes<'a> = Vec<u8>
357        where
358            Self: 'a;
359
360    fn fixed_width() -> Option<usize> {
361        T::fixed_width().map(|x| x * N)
362    }
363
364    fn from_bytes<'a>(data: &'a [u8]) -> [T::SelfType<'a>; N]
365    where
366        Self: 'a,
367    {
368        let mut result = Vec::with_capacity(N);
369        if let Some(fixed) = T::fixed_width() {
370            for i in 0..N {
371                result.push(T::from_bytes(&data[fixed * i..fixed * (i + 1)]));
372            }
373        } else {
374            // Set offset to the first data item
375            let mut start = size_of::<u32>() * N;
376            for i in 0..N {
377                let range = size_of::<u32>() * i..size_of::<u32>() * (i + 1);
378                let end = u32::from_le_bytes(data[range].try_into().unwrap()) as usize;
379                result.push(T::from_bytes(&data[start..end]));
380                start = end;
381            }
382        }
383        result.try_into().unwrap()
384    }
385
386    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> Vec<u8>
387    where
388        Self: 'b,
389    {
390        if let Some(fixed) = T::fixed_width() {
391            let mut result = Vec::with_capacity(fixed * N);
392            for item in value {
393                result.extend_from_slice(T::as_bytes(item).as_ref());
394            }
395            result
396        } else {
397            // Reserve space for the end offsets
398            let mut result = vec![0u8; size_of::<u32>() * N];
399            for i in 0..N {
400                result.extend_from_slice(T::as_bytes(&value[i]).as_ref());
401                let end: u32 = result.len().try_into().unwrap();
402                result[size_of::<u32>() * i..size_of::<u32>() * (i + 1)]
403                    .copy_from_slice(&end.to_le_bytes());
404            }
405            result
406        }
407    }
408
409    fn type_name() -> TypeName {
410        // Uses the same type name as [T;N] so that tables are compatible with [u8;N] and &[u8;N] types
411        // This requires that the binary encoding be the same
412        TypeName::internal(&format!("[{};{N}]", T::type_name().name()))
413    }
414}
415
416impl<const N: usize, T: Key> Key for [T; N] {
417    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
418        if let Some(fixed) = T::fixed_width() {
419            for i in 0..N {
420                let range = fixed * i..fixed * (i + 1);
421                let comparison = T::compare(&data1[range.clone()], &data2[range]);
422                if !comparison.is_eq() {
423                    return comparison;
424                }
425            }
426        } else {
427            // Set offset to the first data item
428            let mut start1 = size_of::<u32>() * N;
429            let mut start2 = size_of::<u32>() * N;
430            for i in 0..N {
431                let range = size_of::<u32>() * i..size_of::<u32>() * (i + 1);
432                let end1 = u32::from_le_bytes(data1[range.clone()].try_into().unwrap()) as usize;
433                let end2 = u32::from_le_bytes(data2[range].try_into().unwrap()) as usize;
434                let comparison = T::compare(&data1[start1..end1], &data2[start2..end2]);
435                if !comparison.is_eq() {
436                    return comparison;
437                }
438                start1 = end1;
439                start2 = end2;
440            }
441        }
442        Ordering::Equal
443    }
444}
445
446impl Value for &str {
447    type SelfType<'a> = &'a str
448    where
449        Self: 'a;
450    type AsBytes<'a> = &'a str
451    where
452        Self: 'a;
453
454    fn fixed_width() -> Option<usize> {
455        None
456    }
457
458    fn from_bytes<'a>(data: &'a [u8]) -> &'a str
459    where
460        Self: 'a,
461    {
462        std::str::from_utf8(data).unwrap()
463    }
464
465    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> &'a str
466    where
467        Self: 'b,
468    {
469        value
470    }
471
472    fn type_name() -> TypeName {
473        TypeName::internal("&str")
474    }
475}
476
477impl Key for &str {
478    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
479        let str1 = Self::from_bytes(data1);
480        let str2 = Self::from_bytes(data2);
481        str1.cmp(str2)
482    }
483}
484
485impl Value for String {
486    type SelfType<'a> = String
487    where
488        Self: 'a;
489    type AsBytes<'a> = &'a str
490    where
491        Self: 'a;
492
493    fn fixed_width() -> Option<usize> {
494        None
495    }
496
497    fn from_bytes<'a>(data: &'a [u8]) -> String
498    where
499        Self: 'a,
500    {
501        std::str::from_utf8(data).unwrap().to_string()
502    }
503
504    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> &'a str
505    where
506        Self: 'b,
507    {
508        value.as_str()
509    }
510
511    fn type_name() -> TypeName {
512        TypeName::internal("String")
513    }
514}
515
516impl Key for String {
517    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
518        let str1 = std::str::from_utf8(data1).unwrap();
519        let str2 = std::str::from_utf8(data2).unwrap();
520        str1.cmp(str2)
521    }
522}
523
524impl Value for char {
525    type SelfType<'a> = char;
526    type AsBytes<'a> = [u8; 3] where Self: 'a;
527
528    fn fixed_width() -> Option<usize> {
529        Some(3)
530    }
531
532    fn from_bytes<'a>(data: &'a [u8]) -> char
533    where
534        Self: 'a,
535    {
536        char::from_u32(u32::from_le_bytes([data[0], data[1], data[2], 0])).unwrap()
537    }
538
539    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> [u8; 3]
540    where
541        Self: 'b,
542    {
543        let bytes = u32::from(*value).to_le_bytes();
544        [bytes[0], bytes[1], bytes[2]]
545    }
546
547    fn type_name() -> TypeName {
548        TypeName::internal(stringify!(char))
549    }
550}
551
552impl Key for char {
553    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
554        Self::from_bytes(data1).cmp(&Self::from_bytes(data2))
555    }
556}
557
558macro_rules! le_value {
559    ($t:ty) => {
560        impl Value for $t {
561            type SelfType<'a> = $t;
562            type AsBytes<'a> = [u8; std::mem::size_of::<$t>()] where Self: 'a;
563
564            fn fixed_width() -> Option<usize> {
565                Some(std::mem::size_of::<$t>())
566            }
567
568            fn from_bytes<'a>(data: &'a [u8]) -> $t
569            where
570                Self: 'a,
571            {
572                <$t>::from_le_bytes(data.try_into().unwrap())
573            }
574
575            fn as_bytes<'a, 'b: 'a>(
576                value: &'a Self::SelfType<'b>,
577            ) -> [u8; std::mem::size_of::<$t>()]
578            where
579                Self: 'a,
580                Self: 'b,
581            {
582                value.to_le_bytes()
583            }
584
585            fn type_name() -> TypeName {
586                TypeName::internal(stringify!($t))
587            }
588        }
589    };
590}
591
592macro_rules! le_impl {
593    ($t:ty) => {
594        le_value!($t);
595
596        impl Key for $t {
597            fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
598                Self::from_bytes(data1).cmp(&Self::from_bytes(data2))
599            }
600        }
601    };
602}
603
604le_impl!(u8);
605le_impl!(u16);
606le_impl!(u32);
607le_impl!(u64);
608le_impl!(u128);
609le_impl!(i8);
610le_impl!(i16);
611le_impl!(i32);
612le_impl!(i64);
613le_impl!(i128);
614le_value!(f32);
615le_value!(f64);
redb/types.rs

redb/
types.rs
