tikv_client/kv/
bound_range.rs

1// Copyright 2019 TiKV Project Authors. Licensed under Apache-2.0.
2
3use std::borrow::Borrow;
4use std::cmp::Eq;
5use std::cmp::PartialEq;
6use std::ops::Bound;
7use std::ops::Range;
8use std::ops::RangeBounds;
9use std::ops::RangeFrom;
10use std::ops::RangeFull;
11use std::ops::RangeInclusive;
12use std::ops::RangeTo;
13use std::ops::RangeToInclusive;
14
15#[cfg(test)]
16use proptest_derive::Arbitrary;
17
18use super::Key;
19use crate::proto::kvrpcpb;
20
21/// A struct for expressing ranges. This type is semi-opaque and is not really meant for users to
22/// deal with directly. Most functions which operate on ranges will accept any types which
23/// implement `Into<BoundRange>`.
24///
25/// In TiKV, keys are an ordered sequence of bytes. This means we can have ranges over those
26/// bytes. Eg `001` is before `010`.
27///
28/// **Minimum key**: there is the minimum key: empty key. So a range may not be unbounded below.
29/// The unbounded lower bound in a [`Range`](Range) will be converted to an empty key.
30///
31/// **Maximum key**: There is no limit of the maximum key. When an empty key is used as the upper bound, it means upper unbounded.
32/// The unbounded upper bound in a [`Range`](Range). The range covering all keys is just `Key::EMPTY..`.
33///
34/// **But, you should not need to worry about all this:** Most functions which operate
35/// on ranges will accept any types which implement `Into<BoundRange>`.
36/// Common range types like `a..b`, `a..=b` has implemented `Into<BoundRange>`where `a` and `b`
37/// `impl Into<Key>`. You can implement `Into<BoundRange>` for your own types by using `try_from`.
38/// It means all of the following types in the example can be passed directly to those functions.
39///
40/// # Examples
41/// ```rust
42/// # use std::ops::{Range, RangeInclusive, RangeTo, RangeToInclusive, RangeFrom, RangeFull, Bound};
43/// # use std::convert::TryInto;
44/// # use tikv_client::{Key, BoundRange};
45///
46/// let explict_range: Range<Key> = Range { start: Key::from("Rust".to_owned()), end: Key::from("TiKV".to_owned()) };
47/// let from_explict_range: BoundRange = explict_range.into();
48///
49/// let range: Range<String> = "Rust".to_owned().."TiKV".to_owned();
50/// let from_range: BoundRange = range.into();
51/// assert_eq!(from_explict_range, from_range);
52///
53/// let range: RangeInclusive<String> = "Rust".to_owned()..="TiKV".to_owned();
54/// let from_range: BoundRange = range.into();
55/// assert_eq!(
56///     from_range,
57///     (Bound::Included(Key::from("Rust".to_owned())), Bound::Included(Key::from("TiKV".to_owned()))),
58/// );
59///
60/// let range_from: RangeFrom<String> = "Rust".to_owned()..;
61/// let from_range_from: BoundRange = range_from.into();
62/// assert_eq!(
63///     from_range_from,
64///     (Bound::Included(Key::from("Rust".to_owned())), Bound::Unbounded),
65/// );
66/// ```
67#[derive(Clone, Debug, Eq, PartialEq)]
68#[cfg_attr(test, derive(Arbitrary))]
69pub struct BoundRange {
70    pub from: Bound<Key>,
71    pub to: Bound<Key>,
72}
73
74impl BoundRange {
75    /// Create a new BoundRange.
76    ///
77    /// The caller must ensure that `from` is not `Unbounded`.
78    pub fn new(from: Bound<Key>, to: Bound<Key>) -> BoundRange {
79        BoundRange { from, to }
80    }
81
82    /// Create a new BoundRange bounded below by `from` and unbounded above.
83    pub fn range_from(from: Key) -> BoundRange {
84        BoundRange {
85            from: Bound::Included(from),
86            to: Bound::Unbounded,
87        }
88    }
89
90    /// Ranges used in scanning TiKV have a particularity to them.
91    ///
92    /// The **start** of a scan is inclusive, unless appended with an '\0', then it is exclusive.
93    ///
94    /// The **end** of a scan is exclusive, unless appended with an '\0', then it is inclusive.
95    ///
96    /// # Examples
97    /// ```rust
98    /// use tikv_client::{BoundRange, Key, IntoOwnedRange};
99    /// // Exclusive
100    /// let range = "a".."z";
101    /// assert_eq!(
102    ///     BoundRange::from(range.into_owned()).into_keys(),
103    ///     (Key::from("a".to_owned()), Some(Key::from("z".to_owned()))),
104    /// );
105    /// // Inclusive
106    /// let range = "a"..="z";
107    /// assert_eq!(
108    ///     BoundRange::from(range.into_owned()).into_keys(),
109    ///     (Key::from("a".to_owned()), Some(Key::from("z\0".to_owned()))),
110    /// );
111    /// // Open right
112    /// let range = "a".to_owned()..;
113    /// assert_eq!(
114    ///     BoundRange::from(range).into_keys(),
115    ///     (Key::from("a".to_owned()), None),
116    /// );
117    /// // Left open right exclusive
118    /// let range = .."z";
119    /// assert_eq!(
120    ///     BoundRange::from(range.into_owned()).into_keys(),
121    ///     (Key::from("".to_owned()), Some(Key::from("z".to_owned()))),
122    /// );
123    /// // Left open right inclusive
124    /// let range = ..="z";
125    /// assert_eq!(
126    ///     BoundRange::from(range.into_owned()).into_keys(),
127    ///     (Key::from("".to_owned()), Some(Key::from("z\0".to_owned()))),
128    /// );
129    /// // Full range
130    /// let range = ..;
131    /// assert_eq!(
132    ///     BoundRange::from(range).into_keys(),
133    ///     (Key::from("".to_owned()), None),
134    /// );
135    // ```
136    pub fn into_keys(self) -> (Key, Option<Key>) {
137        let start = match self.from {
138            Bound::Included(v) => v,
139            Bound::Excluded(v) => v.next_key(),
140            Bound::Unbounded => Key::EMPTY,
141        };
142        let end = match self.to {
143            Bound::Included(v) => Some(v.next_key()),
144            Bound::Excluded(v) => Some(v),
145            Bound::Unbounded => None,
146        };
147        (start, end)
148    }
149}
150
151impl RangeBounds<Key> for BoundRange {
152    // clippy will act differently on nightly and stable, so we allow `needless_match` here.
153    #[allow(clippy::needless_match)]
154    fn start_bound(&self) -> Bound<&Key> {
155        match &self.from {
156            Bound::Included(f) => Bound::Included(f),
157            Bound::Excluded(f) => Bound::Excluded(f),
158            Bound::Unbounded => Bound::Unbounded,
159        }
160    }
161
162    fn end_bound(&self) -> Bound<&Key> {
163        match &self.to {
164            Bound::Included(t) => {
165                if t.is_empty() {
166                    Bound::Unbounded
167                } else {
168                    Bound::Included(t)
169                }
170            }
171            Bound::Excluded(t) => {
172                if t.is_empty() {
173                    Bound::Unbounded
174                } else {
175                    Bound::Excluded(t)
176                }
177            }
178            Bound::Unbounded => Bound::Unbounded,
179        }
180    }
181}
182
183// FIXME `==` should not `clone`
184impl<T: Into<Key> + Clone> PartialEq<(Bound<T>, Bound<T>)> for BoundRange {
185    fn eq(&self, other: &(Bound<T>, Bound<T>)) -> bool {
186        self.from == convert_to_bound_key(other.0.clone())
187            && self.to == convert_to_bound_key(other.1.clone())
188    }
189}
190
191impl<T: Into<Key>> From<Range<T>> for BoundRange {
192    fn from(other: Range<T>) -> BoundRange {
193        BoundRange::new(
194            Bound::Included(other.start.into()),
195            Bound::Excluded(other.end.into()),
196        )
197    }
198}
199
200impl<T: Into<Key>> From<RangeFrom<T>> for BoundRange {
201    fn from(other: RangeFrom<T>) -> BoundRange {
202        BoundRange::new(Bound::Included(other.start.into()), Bound::Unbounded)
203    }
204}
205
206impl<T: Into<Key>> From<RangeTo<T>> for BoundRange {
207    fn from(other: RangeTo<T>) -> BoundRange {
208        BoundRange::new(Bound::Unbounded, Bound::Excluded(other.end.into()))
209    }
210}
211
212impl<T: Into<Key>> From<RangeInclusive<T>> for BoundRange {
213    fn from(other: RangeInclusive<T>) -> BoundRange {
214        let (start, end) = other.into_inner();
215        BoundRange::new(Bound::Included(start.into()), Bound::Included(end.into()))
216    }
217}
218
219impl<T: Into<Key>> From<RangeToInclusive<T>> for BoundRange {
220    fn from(other: RangeToInclusive<T>) -> BoundRange {
221        BoundRange::new(Bound::Unbounded, Bound::Included(other.end.into()))
222    }
223}
224
225impl From<RangeFull> for BoundRange {
226    fn from(_other: RangeFull) -> BoundRange {
227        BoundRange::new(Bound::Unbounded, Bound::Unbounded)
228    }
229}
230
231impl<T: Into<Key>> From<(T, Option<T>)> for BoundRange {
232    fn from(other: (T, Option<T>)) -> BoundRange {
233        let to = match other.1 {
234            None => Bound::Unbounded,
235            Some(to) => to.into().into_upper_bound(),
236        };
237
238        BoundRange::new(other.0.into().into_lower_bound(), to)
239    }
240}
241
242impl<T: Into<Key>> From<(T, T)> for BoundRange {
243    fn from(other: (T, T)) -> BoundRange {
244        BoundRange::new(
245            other.0.into().into_lower_bound(),
246            other.1.into().into_upper_bound(),
247        )
248    }
249}
250
251impl<T: Into<Key> + Eq> From<(Bound<T>, Bound<T>)> for BoundRange {
252    fn from(bounds: (Bound<T>, Bound<T>)) -> BoundRange {
253        BoundRange::new(
254            convert_to_bound_key(bounds.0),
255            convert_to_bound_key(bounds.1),
256        )
257    }
258}
259
260impl From<BoundRange> for kvrpcpb::KeyRange {
261    fn from(bound_range: BoundRange) -> Self {
262        let (start, end) = bound_range.into_keys();
263        let mut range = kvrpcpb::KeyRange::default();
264        range.start_key = start.into();
265        range.end_key = end.unwrap_or_default().into();
266        range
267    }
268}
269
270impl From<kvrpcpb::KeyRange> for BoundRange {
271    fn from(range: kvrpcpb::KeyRange) -> Self {
272        let start_key = Key::from(range.start_key);
273        let end_key = Key::from(range.end_key);
274        BoundRange::new(start_key.into_lower_bound(), end_key.into_upper_bound())
275    }
276}
277
278/// A convenience trait for converting ranges of borrowed types into a `BoundRange`.
279///
280/// # Examples
281/// ```rust
282/// # use tikv_client::{IntoOwnedRange, BoundRange};
283/// # use std::ops::*;
284/// let r1: Range<&str> = "s".."e";
285/// let r1: BoundRange = r1.into_owned();
286///
287/// let r2: RangeFrom<&str> = "start"..;
288/// let r2: BoundRange = r2.into_owned();
289///
290/// let r3: RangeInclusive<&str> = "s"..="e";
291/// let r3: BoundRange = r3.into_owned();
292///
293/// let r4: RangeTo<&str> = .."z";
294/// let r4: BoundRange = r4.into_owned();
295///
296/// let k1: Vec<u8> = "start".to_owned().into_bytes();
297/// let k2: Vec<u8> = "end".to_owned().into_bytes();
298/// let r4: BoundRange = (&k1, &k2).into_owned();
299/// let r5: BoundRange = (&k1, None).into_owned();
300/// let r6: BoundRange = (&k1, Some(&k2)).into_owned();
301/// ```
302pub trait IntoOwnedRange {
303    /// Transform a borrowed range of some form into an owned `BoundRange`.
304    fn into_owned(self) -> BoundRange;
305}
306
307impl<T: Into<Key> + Borrow<U>, U: ToOwned<Owned = T> + ?Sized> IntoOwnedRange for Range<&U> {
308    fn into_owned(self) -> BoundRange {
309        From::from(Range {
310            start: self.start.to_owned(),
311            end: self.end.to_owned(),
312        })
313    }
314}
315
316impl<T: Into<Key> + Borrow<U>, U: ToOwned<Owned = T> + ?Sized> IntoOwnedRange for RangeFrom<&U> {
317    fn into_owned(self) -> BoundRange {
318        From::from(RangeFrom {
319            start: self.start.to_owned(),
320        })
321    }
322}
323
324impl<T: Into<Key> + Borrow<U>, U: ToOwned<Owned = T> + ?Sized> IntoOwnedRange for RangeTo<&U> {
325    fn into_owned(self) -> BoundRange {
326        From::from(RangeTo {
327            end: self.end.to_owned(),
328        })
329    }
330}
331
332impl<T: Into<Key> + Borrow<U>, U: ToOwned<Owned = T> + ?Sized> IntoOwnedRange
333    for RangeInclusive<&U>
334{
335    fn into_owned(self) -> BoundRange {
336        let (from, to) = self.into_inner();
337        From::from(RangeInclusive::new(from.to_owned(), to.to_owned()))
338    }
339}
340
341impl<T: Into<Key> + Borrow<U>, U: ToOwned<Owned = T> + ?Sized> IntoOwnedRange
342    for RangeToInclusive<&U>
343{
344    fn into_owned(self) -> BoundRange {
345        From::from(RangeToInclusive {
346            end: self.end.to_owned(),
347        })
348    }
349}
350
351impl IntoOwnedRange for RangeFull {
352    fn into_owned(self) -> BoundRange {
353        From::from(self)
354    }
355}
356
357impl<T: Into<Key> + Borrow<U>, U: ToOwned<Owned = T> + ?Sized> IntoOwnedRange for (&U, Option<&U>) {
358    fn into_owned(self) -> BoundRange {
359        From::from((self.0.to_owned(), self.1.map(|u| u.to_owned())))
360    }
361}
362
363impl<T: Into<Key> + Borrow<U>, U: ToOwned<Owned = T> + ?Sized> IntoOwnedRange for (&U, &U) {
364    fn into_owned(self) -> BoundRange {
365        From::from((self.0.to_owned(), self.1.to_owned()))
366    }
367}
368
369fn convert_to_bound_key<K: Into<Key>>(b: Bound<K>) -> Bound<Key> {
370    match b {
371        Bound::Included(k) => Bound::Included(k.into()),
372        Bound::Excluded(k) => Bound::Excluded(k.into()),
373        Bound::Unbounded => Bound::Unbounded,
374    }
375}
tikv_client/kv/bound_range.rs

tikv_client/kv/
bound_range.rs
