psibase/
to_key.rs

1use crate::Hex;
2use async_graphql::connection::CursorType;
3use std::collections::{BTreeSet, LinkedList, VecDeque};
4
5/// ToKey defines a conversion from a type to a sequence of bytes
6/// whose lexicographical ordering is the same as the ordering of
7/// the original type.
8///
9/// For any two objects of the same type T, a and b:
10/// - a.to_key() < b.to_key() iff a < b
11/// - a.to_key() is not a prefix of b.to_key()
12///
13/// This format doesn't have the guarantees that fracpack has.
14/// e.g. adding new fields at the end of a struct or tuple can
15/// corrupt data in some cases.
16///
17/// The encoding rules match psibase's `to_key.hpp` implementation.
18/// If there are any ordering differences between Rust and C++, the
19/// C++ rules win. So far I haven't encountered any; e.g. Rust's
20/// `Option` ordering matches C++'s `optional` ordering.
21///
22/// # Caution
23///
24/// In Rust, it's easy to accidentally convert from a fixed-size
25/// array reference (`&[T;7]`) to a slice (`&[T]`). This matters
26/// to ToKey, which has different, and incompatible, encodings
27/// for the two types.
28pub trait ToKey {
29    /// Convert to key
30    fn to_key(&self) -> Vec<u8> {
31        let mut key = Vec::new();
32        self.append_key(&mut key);
33        key
34    }
35
36    /// Append to key
37    fn append_key(&self, key: &mut Vec<u8>);
38
39    /// Append to key
40    fn append_option_key(obj: &Option<&Self>, key: &mut Vec<u8>) {
41        if let Some(x) = obj {
42            key.push(1);
43            x.append_key(key);
44        } else {
45            key.push(0);
46        }
47    }
48}
49
50/// A serialized key
51///
52/// The serialized data has the same sort order as the non-serialized form
53#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
54pub struct RawKey {
55    pub data: Vec<u8>,
56}
57
58impl RawKey {
59    pub fn new(data: Vec<u8>) -> Self {
60        RawKey { data }
61    }
62}
63
64impl ToKey for RawKey {
65    fn append_key(&self, key: &mut Vec<u8>) {
66        key.extend_from_slice(&self.data[..]);
67    }
68}
69
70impl CursorType for RawKey {
71    type Error = &'static str;
72    fn decode_cursor(s: &str) -> Result<Self, Self::Error> {
73        Ok(Self::new(s.parse::<Hex<Vec<u8>>>()?.0))
74    }
75    fn encode_cursor(&self) -> String {
76        Hex(self.data.as_slice()).to_string()
77    }
78}
79
80/// A serialized key (not owning)
81///
82/// The serialized data has the same sort order as the non-serialized form
83#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
84pub struct KeyView<'a> {
85    pub data: &'a [u8],
86}
87
88impl<'a> KeyView<'a> {
89    pub fn new(data: &'a [u8]) -> Self {
90        KeyView { data }
91    }
92}
93
94impl<'a> ToKey for KeyView<'a> {
95    fn append_key(&self, key: &mut Vec<u8>) {
96        key.extend_from_slice(self.data);
97    }
98}
99
100impl<T: ToKey + ?Sized> ToKey for &T {
101    fn append_key(&self, key: &mut Vec<u8>) {
102        T::append_key(self, key)
103    }
104}
105
106impl<T: ToKey + ?Sized> ToKey for &mut T {
107    fn append_key(&self, key: &mut Vec<u8>) {
108        T::append_key(self, key)
109    }
110}
111
112impl ToKey for bool {
113    fn append_key(&self, key: &mut Vec<u8>) {
114        key.push(match self {
115            false => 0,
116            true => 1,
117        });
118    }
119
120    fn append_option_key(obj: &Option<&Self>, key: &mut Vec<u8>) {
121        key.push(match obj {
122            None => 0,
123            Some(false) => 1,
124            Some(true) => 2,
125        });
126    }
127}
128
129macro_rules! byte_impl {
130    ($t:ty) => {
131        impl ToKey for $t {
132            fn append_key(&self, key: &mut Vec<u8>) {
133                key.extend_from_slice(&self.to_be_bytes());
134            }
135
136            fn append_option_key(obj: &Option<&Self>, key: &mut Vec<u8>) {
137                match obj {
138                    None => {
139                        key.push(0);
140                        key.push(0)
141                    }
142                    Some(value) => {
143                        key.push(**value as u8);
144                        if **value == 0 {
145                            key.push(1);
146                        }
147                    }
148                }
149            }
150        }
151    };
152}
153byte_impl! {u8}
154byte_impl! {i8}
155
156macro_rules! scalar_impl {
157    ($t:ty) => {
158        impl ToKey for $t {
159            fn append_key(&self, key: &mut Vec<u8>) {
160                key.extend_from_slice(&self.wrapping_sub(<$t>::MIN).to_be_bytes());
161            }
162        }
163    };
164}
165scalar_impl! {u16}
166scalar_impl! {u32}
167scalar_impl! {u64}
168scalar_impl! {i16}
169scalar_impl! {i32}
170scalar_impl! {i64}
171
172macro_rules! float_impl {
173    ($t:ty, $t2:ty) => {
174        impl ToKey for $t {
175            fn append_key(&self, key: &mut Vec<u8>) {
176                let mut result = self.to_bits();
177                let signbit = 1 << (<$t2>::BITS - 1);
178                let mut mask = 0;
179                if result == signbit {
180                    result = 0;
181                }
182                if (result & signbit) != 0 {
183                    mask = !mask;
184                }
185                result ^= mask | signbit;
186                result.append_key(key)
187            }
188        }
189    };
190}
191float_impl! {f32,u32}
192float_impl! {f64,u64}
193
194impl<T: ToKey> ToKey for Option<T> {
195    fn append_key(&self, key: &mut Vec<u8>) {
196        T::append_option_key(&self.into(), key)
197    }
198}
199
200macro_rules! str_impl {
201    ($t:ty) => {
202        impl ToKey for $t {
203            fn append_key(&self, key: &mut Vec<u8>) {
204                for byte in self.bytes() {
205                    key.push(byte);
206                    if byte == 0 {
207                        key.push(1);
208                    }
209                }
210                key.push(0);
211                key.push(0)
212            }
213        }
214    };
215}
216str_impl! {String}
217str_impl! {&str}
218
219macro_rules! container_impl {
220    ($t:ident) => {
221        impl<T: ToKey> ToKey for $t<T> {
222            fn append_key(&self, key: &mut Vec<u8>) {
223                for item in self.iter() {
224                    T::append_option_key(&Some(item), key);
225                }
226                T::append_option_key(&None, key);
227            }
228        }
229    };
230}
231container_impl! {Vec}
232container_impl! {VecDeque}
233container_impl! {LinkedList}
234container_impl! {BTreeSet}
235
236impl<T: ToKey> ToKey for [T] {
237    fn append_key(&self, key: &mut Vec<u8>) {
238        for item in self.iter() {
239            T::append_option_key(&Some(item), key);
240        }
241        T::append_option_key(&None, key);
242    }
243}
244
245impl<T: ToKey, const N: usize> ToKey for [T; N] {
246    fn append_key(&self, key: &mut Vec<u8>) {
247        for item in self {
248            item.append_key(key);
249        }
250    }
251}
252
253macro_rules! tuple_impls {
254    ($($len:expr => ($($n:tt $name:ident)*))+) => {
255        $(
256            impl<$($name: ToKey),*> ToKey for ($($name,)*) {
257                #[allow(non_snake_case)]
258                fn append_key(&self, _key: &mut Vec<u8>) {
259                    $(
260                        self.$n.append_key(_key);
261                    )*
262                }
263            }
264        )+
265    }
266}
267
268tuple_impls! {
269    0 => ()
270    1 => (0 T0)
271    2 => (0 T0 1 T1)
272    3 => (0 T0 1 T1 2 T2)
273    4 => (0 T0 1 T1 2 T2 3 T3)
274    5 => (0 T0 1 T1 2 T2 3 T3 4 T4)
275    6 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5)
276    7 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5 6 T6)
277    8 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5 6 T6 7 T7)
278    9 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5 6 T6 7 T7 8 T8)
279    10 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5 6 T6 7 T7 8 T8 9 T9)
280    11 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5 6 T6 7 T7 8 T8 9 T9 10 T10)
281    12 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5 6 T6 7 T7 8 T8 9 T9 10 T10 11 T11)
282    13 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5 6 T6 7 T7 8 T8 9 T9 10 T10 11 T11 12 T12)
283    14 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5 6 T6 7 T7 8 T8 9 T9 10 T10 11 T11 12 T12 13 T13)
284    15 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5 6 T6 7 T7 8 T8 9 T9 10 T10 11 T11 12 T12 13 T13 14 T14)
285    16 => (0 T0 1 T1 2 T2 3 T3 4 T4 5 T5 6 T6 7 T7 8 T8 9 T9 10 T10 11 T11 12 T12 13 T13 14 T14 15 T15)
286}
psibase/to_key.rs

psibase/
to_key.rs
