foundationdb_tuple/
subspace.rs

1// Copyright 2018 foundationdb-rs developers, https://github.com/Clikengo/foundationdb-rs/graphs/contributors
2// Copyright 2013-2018 Apple, Inc and the FoundationDB project authors.
3//
4// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
5// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
6// http://opensource.org/licenses/MIT>, at your option. This file may not be
7// copied, modified, or distributed except according to those terms.
8
9use super::*;
10use std::fmt::Formatter;
11use std::hash::Hash;
12
13/// Represents a well-defined region of keyspace in a FoundationDB database
14///
15/// It provides a convenient way to use FoundationDB tuples to define namespaces for
16/// different categories of data. The namespace is specified by a prefix tuple which is prepended
17/// to all tuples packed by the subspace. When unpacking a key with the subspace, the prefix tuple
18/// will be removed from the result.
19///
20/// As a best practice, API clients should use at least one subspace for application data. For
21/// general guidance on subspace usage, see the Subspaces section of the [Developer Guide].
22///
23/// [Developer Guide]: https://apple.github.io/foundationdb/developer-guide.html#subspaces
24#[derive(Debug, Clone, Eq, PartialEq, Hash)]
25pub struct Subspace {
26    prefix: Vec<u8>,
27    versionstamp_offset: VersionstampOffset,
28}
29
30impl Display for Subspace {
31    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
32        for &b in &self.prefix {
33            if (32..127).contains(&b) && b != b'\\' {
34                write!(f, "{}", b as char)?;
35            } else if b == b'\\' {
36                write!(f, "\\\\")?;
37            } else {
38                write!(f, "\\x{b:02x}")?;
39            }
40        }
41        Ok(())
42    }
43}
44
45impl<E: TuplePack> From<E> for Subspace {
46    fn from(e: E) -> Self {
47        let mut prefix = vec![];
48        let versionstamp_offset = pack_into(&e, &mut prefix);
49        Self {
50            prefix,
51            versionstamp_offset,
52        }
53    }
54}
55
56impl Subspace {
57    /// `all` returns the Subspace corresponding to all keys in a FoundationDB database.
58    pub fn all() -> Self {
59        Self {
60            prefix: Vec::new(),
61            versionstamp_offset: VersionstampOffset::None { size: 0 },
62        }
63    }
64
65    /// Returns a new Subspace from the provided bytes.
66    pub fn from_bytes(prefix: impl Into<Vec<u8>>) -> Self {
67        let prefix = prefix.into();
68        Self {
69            versionstamp_offset: VersionstampOffset::None {
70                size: u32::try_from(prefix.len()).expect("data doesn't fit u32"),
71            },
72            prefix,
73        }
74    }
75
76    /// Convert into prefix key bytes
77    pub fn into_bytes(self) -> Vec<u8> {
78        self.prefix
79    }
80
81    /// Returns a new Subspace whose prefix extends this Subspace with a given tuple encodable.
82    pub fn subspace<T: TuplePack>(&self, t: &T) -> Self {
83        let mut prefix = self.prefix.clone();
84        let mut versionstamp_offset = self.versionstamp_offset;
85        versionstamp_offset += pack_into(t, &mut prefix);
86        Self {
87            prefix,
88            versionstamp_offset,
89        }
90    }
91
92    /// `bytes` returns the literal bytes of the prefix of this Subspace.
93    pub fn bytes(&self) -> &[u8] {
94        self.prefix.as_slice()
95    }
96
97    /// Returns the key encoding the specified Tuple with the prefix of this Subspace
98    /// prepended.
99    pub fn pack<T: TuplePack>(&self, t: &T) -> Vec<u8> {
100        let mut out = self.prefix.clone();
101        pack_into(t, &mut out);
102        out
103    }
104
105    /// Returns the key encoding the specified Tuple with the prefix of this Subspace
106    /// prepended, with a versionstamp offset for API 520 and later.
107    ///
108    /// Incomplete stamps append a four-byte offset. For earlier runtime APIs, use
109    /// [`Self::pack_with_versionstamp_for_key`]. Complete stamps are packed without
110    /// an offset suffix.
111    pub fn pack_with_versionstamp<T: TuplePack>(&self, t: &T) -> Vec<u8> {
112        let mut output = self.prefix.clone();
113        let mut versionstamp_offset = self.versionstamp_offset;
114        versionstamp_offset += pack_into(t, &mut output);
115        match versionstamp_offset {
116            VersionstampOffset::OneIncomplete { offset } => {
117                output.extend_from_slice(&offset.to_le_bytes());
118            }
119            VersionstampOffset::MultipleIncomplete => {
120                panic!("Subspace cannot contain more than one incomplete versionstamp");
121            }
122            _ => {}
123        }
124        output
125    }
126
127    /// Pack a tuple key with this subspace's prefix for the selected runtime API.
128    ///
129    /// See [`pack_with_versionstamp_for_key`] for the encoding and version contract.
130    /// The offset includes the entire prefix, including any incomplete stamp in
131    /// the subspace itself. A raw prefix supplied via [`Self::from_bytes`] is
132    /// opaque: only stamps in the tuple are tracked in that case.
133    ///
134    /// # Panics
135    ///
136    /// Panics if there are multiple incomplete stamps, the encoded size does not
137    /// fit in `u32`, or a legacy key's stamp offset does not fit in `u16`.
138    pub fn pack_with_versionstamp_for_key<T: TuplePack>(&self, t: &T, api_version: i32) -> Vec<u8> {
139        let mut output = self.prefix.clone();
140        let mut offset = self.versionstamp_offset;
141        offset += pack_into(t, &mut output);
142        offset.append_key_offset(&mut output, api_version);
143        output
144    }
145
146    /// `unpack` returns the Tuple encoded by the given key with the prefix of this Subspace
147    /// removed.  `unpack` will return an error if the key is not in this Subspace or does not
148    /// encode a well-formed Tuple.
149    pub fn unpack<'de, T: TupleUnpack<'de>>(&self, key: &'de [u8]) -> PackResult<T> {
150        if !self.is_start_of(key) {
151            return Err(PackError::BadPrefix);
152        }
153        let key = &key[self.prefix.len()..];
154        unpack(key)
155    }
156
157    /// `is_start_of` returns true if the provided key starts with the prefix of this Subspace,
158    /// indicating that the Subspace logically contains the key.
159    pub fn is_start_of(&self, key: &[u8]) -> bool {
160        key.starts_with(&self.prefix)
161    }
162
163    /// `range` returns first and last key of given Subspace
164    pub fn range(&self) -> (Vec<u8>, Vec<u8>) {
165        let mut begin = Vec::with_capacity(self.prefix.len() + 1);
166        begin.extend_from_slice(&self.prefix);
167        begin.push(0x00);
168
169        let mut end = Vec::with_capacity(self.prefix.len() + 1);
170        end.extend_from_slice(&self.prefix);
171        end.push(0xff);
172
173        (begin, end)
174    }
175}
176
177#[cfg(test)]
178mod tests {
179    use super::*;
180    use std::collections::HashMap;
181
182    #[test]
183    fn sub() {
184        let ss0: Subspace = 1.into();
185        let ss1 = ss0.subspace(&2);
186
187        let ss2: Subspace = (1, 2).into();
188
189        assert_eq!(ss1.bytes(), ss2.bytes());
190    }
191
192    #[test]
193    fn pack_unpack() {
194        let ss0: Subspace = 1.into();
195        let tup = (2, 3);
196
197        let packed = ss0.pack(&tup);
198        let expected = pack(&(1, 2, 3));
199        assert_eq!(expected, packed);
200
201        let tup_unpack: (i64, i64) = ss0.unpack(&packed).unwrap();
202        assert_eq!(tup, tup_unpack);
203
204        assert!(ss0.unpack::<(i64, i64, i64)>(&packed).is_err());
205    }
206
207    #[test]
208    fn subspace_pack_with_versionstamp() {
209        let subspace: Subspace = 1.into();
210        let tup = (Versionstamp::incomplete(0), 2);
211
212        let packed = subspace.pack_with_versionstamp(&tup);
213        let expected = pack_with_versionstamp(&(1, Versionstamp::incomplete(0), 2));
214        assert_eq!(expected, packed);
215    }
216
217    #[test]
218    fn versionstamp_key_encoding_includes_prefix_and_nested_tuple() {
219        let stamp = Versionstamp::incomplete(9);
220        for api_version in [510, 520, 740] {
221            let subspace = Subspace::from("prefix");
222            assert_eq!(
223                subspace.pack_with_versionstamp_for_key(&((&stamp,), 2), api_version),
224                pack_with_versionstamp_for_key(&("prefix", (&stamp,), 2), api_version)
225            );
226            let subspace = subspace.subspace(&(&stamp,));
227            assert_eq!(
228                subspace.pack_with_versionstamp_for_key(&2, api_version),
229                pack_with_versionstamp_for_key(&("prefix", &stamp, 2), api_version)
230            );
231            assert!(
232                std::panic::catch_unwind(
233                    || subspace.pack_with_versionstamp_for_key(&stamp, api_version)
234                )
235                .is_err()
236            );
237        }
238    }
239
240    #[test]
241    fn legacy_key_offset_is_checked_including_raw_prefix() {
242        let stamp = Versionstamp::incomplete(0);
243        let subspace = Subspace::from_bytes(vec![b'x'; u16::MAX as usize - 1]);
244        let key = subspace.pack_with_versionstamp_for_key(&stamp, 510);
245        assert_eq!(&key[key.len() - 2..], &u16::MAX.to_le_bytes());
246
247        let subspace = Subspace::from_bytes(vec![b'x'; u16::MAX as usize]);
248        assert!(
249            std::panic::catch_unwind(|| subspace.pack_with_versionstamp_for_key(&stamp, 510))
250                .is_err()
251        );
252        let key = subspace.pack_with_versionstamp_for_key(&stamp, 520);
253        assert_eq!(&key[key.len() - 4..], &65536_u32.to_le_bytes());
254        let complete = Versionstamp::complete([7; 10], 0);
255        assert_eq!(
256            subspace.pack_with_versionstamp_for_key(&complete, 510),
257            subspace.pack(&complete)
258        );
259    }
260
261    #[test]
262    fn subspace_unpack_with_versionstamp() {
263        // On unpack, the versionstamp will be complete, so pack_with_versionstamp won't append
264        // the offset.
265        let subspace: Subspace = 1.into();
266        let tup = (Versionstamp::complete([1; 10], 0), 2);
267        let packed = subspace.pack_with_versionstamp(&tup);
268        let tup_unpack: (Versionstamp, i64) = subspace.unpack(&packed).unwrap();
269        assert_eq!(tup, tup_unpack);
270
271        assert!(
272            subspace
273                .unpack::<(i64, Versionstamp, i64)>(&packed)
274                .is_err()
275        );
276    }
277
278    #[test]
279    fn unpack_with_subspace_versionstamp() {
280        let subspace: Subspace = Versionstamp::complete([1; 10], 2).into();
281        let tup = (Versionstamp::complete([1; 10], 0), 2);
282        let packed = subspace.pack_with_versionstamp(&tup);
283        let tup_unpack: (Versionstamp, i64) = subspace.unpack(&packed).unwrap();
284        assert_eq!(tup, tup_unpack);
285        assert!(
286            subspace
287                .unpack::<(Versionstamp, Versionstamp, i64)>(&packed)
288                .is_err()
289        );
290    }
291
292    #[test]
293    fn subspace_can_use_incomplete_versionstamp() {
294        let subspace: Subspace = Versionstamp::incomplete(0).into();
295        let tup = (1, 2);
296
297        let packed = subspace.pack_with_versionstamp(&tup);
298        let expected = pack_with_versionstamp(&(Versionstamp::incomplete(0), 1, 2));
299        assert_eq!(expected, packed);
300    }
301
302    #[test]
303    fn child_subspace_can_use_incomplete_versionstamp() {
304        let subspace: Subspace = 1.into();
305        let subspace = subspace.subspace(&Versionstamp::incomplete(0));
306        let tup = (1, 2);
307        let packed = subspace.pack_with_versionstamp(&tup);
308        let expected = pack_with_versionstamp(&(1, Versionstamp::incomplete(0), 1, 2));
309        assert_eq!(expected, packed);
310    }
311
312    #[test]
313    #[should_panic]
314    fn subspace_cannot_use_multiple_incomplete_versionstamps() {
315        let subspace: Subspace = Versionstamp::incomplete(0).into();
316        let subspace = subspace.subspace(&Versionstamp::incomplete(0));
317        subspace.pack_with_versionstamp(&1);
318    }
319
320    #[test]
321    #[should_panic]
322    fn subspace_cannot_pack_multiple_incomplete_versionstamps() {
323        let subspace: Subspace = Versionstamp::incomplete(0).into();
324        subspace.pack_with_versionstamp(&Versionstamp::incomplete(0));
325    }
326
327    #[test]
328    fn is_start_of() {
329        let ss0: Subspace = 1.into();
330        let ss1: Subspace = 2.into();
331        let tup = (2, 3);
332
333        assert!(ss0.is_start_of(&ss0.pack(&tup)));
334        assert!(!ss1.is_start_of(&ss0.pack(&tup)));
335        assert!(Subspace::from("start").is_start_of(&pack(&"start")));
336        assert!(Subspace::from("start").is_start_of(&pack(&"start".to_string())));
337        assert!(!Subspace::from("start").is_start_of(&pack(&"starting")));
338        assert!(Subspace::from("start").is_start_of(&pack(&("start", "end"))));
339        assert!(Subspace::from(("start", 42)).is_start_of(&pack(&("start", 42, "end"))));
340    }
341
342    #[test]
343    fn range() {
344        let ss: Subspace = 1.into();
345        let tup = (2, 3);
346        let packed = ss.pack(&tup);
347
348        let (begin, end) = ss.range();
349        assert!(packed >= begin && packed <= end);
350    }
351
352    #[test]
353    fn equality() {
354        let sub1 = Subspace::all().subspace(&"test");
355        let sub2 = Subspace::all().subspace(&"test");
356        let sub3 = Subspace::all().subspace(&"test2");
357        assert_eq!(sub1, sub2);
358        assert_ne!(sub1, sub3);
359    }
360
361    #[test]
362    fn hash() {
363        let sub1 = Subspace::all().subspace(&"test");
364        let sub2 = Subspace::all().subspace(&"test2");
365
366        let map: HashMap<Subspace, u8> = HashMap::from([(sub1, 1), (sub2, 2)]);
367
368        assert_eq!(map.get(&Subspace::all().subspace(&"test")).unwrap(), &1);
369        assert_eq!(map.get(&Subspace::all().subspace(&"test2")).unwrap(), &2);
370    }
371
372    #[test]
373    fn display() {
374        let sub1 = Subspace::all().subspace(&"test");
375        let sub2 = Subspace::all().subspace(&"test2").subspace(&"path1");
376        let sub3 = Subspace::all().subspace(&"test3").subspace(&"__커피__");
377        let sub4 = Subspace::all().subspace(&"test4\\path1\\path2");
378
379        assert_eq!(format!("{sub1}"), r#"\x02test\x00"#);
380        assert_eq!(format!("{sub2}"), r#"\x02test2\x00\x02path1\x00"#);
381        assert_eq!(
382            format!("{sub3}"),
383            r#"\x02test3\x00\x02__\xec\xbb\xa4\xed\x94\xbc__\x00"#
384        );
385        assert_eq!(format!("{sub4}"), r#"\x02test4\\path1\\path2\x00"#);
386    }
387}