123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673 |
- // Copyright (c) 2018, The Tor Project, Inc.
- // Copyright (c) 2018, isis agora lovecruft
- // See LICENSE for licensing information
- //! Sets for lazily storing ordered, non-overlapping ranges of integers.
- use std::cmp;
- use std::iter;
- use std::slice;
- use std::str::FromStr;
- use std::u32;
- use errors::ProtoverError;
- /// A single version number.
- pub type Version = u32;
- /// A `ProtoSet` stores an ordered `Vec<T>` of `(low, high)` pairs of ranges of
- /// non-overlapping protocol versions.
- ///
- /// # Examples
- ///
- /// ```
- /// use std::str::FromStr;
- ///
- /// use protover::errors::ProtoverError;
- /// use protover::protoset::ProtoSet;
- /// use protover::protoset::Version;
- ///
- /// # fn do_test() -> Result<ProtoSet, ProtoverError> {
- /// let protoset: ProtoSet = ProtoSet::from_str("3-5,8")?;
- ///
- /// // We could also equivalently call:
- /// let protoset: ProtoSet = "3-5,8".parse()?;
- ///
- /// assert!(protoset.contains(&4));
- /// assert!(!protoset.contains(&7));
- ///
- /// let expanded: Vec<Version> = protoset.clone().into();
- ///
- /// assert_eq!(&expanded[..], &[3, 4, 5, 8]);
- ///
- /// let contracted: String = protoset.clone().to_string();
- ///
- /// assert_eq!(contracted, "3-5,8".to_string());
- /// # Ok(protoset)
- /// # }
- /// # fn main() { do_test(); } // wrap the test so we can use the ? operator
- #[derive(Clone, Debug, Eq, PartialEq, Hash)]
- pub struct ProtoSet {
- pub(crate) pairs: Vec<(Version, Version)>,
- }
- impl Default for ProtoSet {
- fn default() -> Self {
- let pairs: Vec<(Version, Version)> = Vec::new();
- ProtoSet{ pairs }
- }
- }
- impl<'a> ProtoSet {
- /// Create a new `ProtoSet` from a slice of `(low, high)` pairs.
- ///
- /// # Inputs
- ///
- /// We do not assume the input pairs are deduplicated or ordered.
- pub fn from_slice(low_high_pairs: &'a [(Version, Version)]) -> Result<Self, ProtoverError> {
- let mut pairs: Vec<(Version, Version)> = Vec::with_capacity(low_high_pairs.len());
- for &(low, high) in low_high_pairs {
- pairs.push((low, high));
- }
- // Sort the pairs without reallocation and remove all duplicate pairs.
- pairs.sort_unstable();
- pairs.dedup();
- ProtoSet{ pairs }.is_ok()
- }
- }
- /// Expand this `ProtoSet` to a `Vec` of all its `Version`s.
- ///
- /// # Examples
- ///
- /// ```
- /// use std::str::FromStr;
- /// use protover::protoset::ProtoSet;
- /// use protover::protoset::Version;
- /// # use protover::errors::ProtoverError;
- ///
- /// # fn do_test() -> Result<Vec<Version>, ProtoverError> {
- /// let protoset: ProtoSet = ProtoSet::from_str("3-5,21")?;
- /// let versions: Vec<Version> = protoset.into();
- ///
- /// assert_eq!(&versions[..], &[3, 4, 5, 21]);
- /// #
- /// # Ok(versions)
- /// # }
- /// # fn main() { do_test(); } // wrap the test so we can use the ? operator
- /// ```
- impl Into<Vec<Version>> for ProtoSet {
- fn into(self) -> Vec<Version> {
- let mut versions: Vec<Version> = Vec::new();
- for &(low, high) in self.iter() {
- versions.extend(low..high + 1);
- }
- versions
- }
- }
- impl ProtoSet {
- /// Get an iterator over the `(low, high)` `pairs` in this `ProtoSet`.
- pub fn iter(&self) -> slice::Iter<(Version, Version)> {
- self.pairs.iter()
- }
- /// Expand this `ProtoSet` into a `Vec` of all its `Version`s.
- ///
- /// # Examples
- ///
- /// ```
- /// # use protover::errors::ProtoverError;
- /// use protover::protoset::ProtoSet;
- ///
- /// # fn do_test() -> Result<bool, ProtoverError> {
- /// let protoset: ProtoSet = "3-5,9".parse()?;
- ///
- /// assert_eq!(protoset.expand(), vec![3, 4, 5, 9]);
- ///
- /// let protoset: ProtoSet = "1,3,5-7".parse()?;
- ///
- /// assert_eq!(protoset.expand(), vec![1, 3, 5, 6, 7]);
- /// #
- /// # Ok(true)
- /// # }
- /// # fn main() { do_test(); } // wrap the test so we can use the ? operator
- /// ```
- pub fn expand(self) -> Vec<Version> {
- self.into()
- }
- pub fn len(&self) -> usize {
- let mut length: usize = 0;
- for &(low, high) in self.iter() {
- length += (high as usize - low as usize) + 1;
- }
- length
- }
- /// Check that this `ProtoSet` is well-formed.
- ///
- /// This is automatically called in `ProtoSet::from_str()`.
- ///
- /// # Errors
- ///
- /// * `ProtoverError::LowGreaterThanHigh`: if its `pairs` were not
- /// well-formed, i.e. a `low` in a `(low, high)` was higher than the
- /// previous `high`,
- /// * `ProtoverError::Overlap`: if one or more of the `pairs` are
- /// overlapping,
- /// * `ProtoverError::ExceedsMax`: if the number of versions when expanded
- /// would exceed `MAX_PROTOCOLS_TO_EXPAND`, and
- ///
- /// # Returns
- ///
- /// A `Result` whose `Ok` is this `Protoset`, and whose `Err` is one of the
- /// errors enumerated in the Errors section above.
- fn is_ok(self) -> Result<ProtoSet, ProtoverError> {
- let mut last_high: Version = 0;
- for &(low, high) in self.iter() {
- if low == u32::MAX || high == u32::MAX {
- return Err(ProtoverError::ExceedsMax);
- }
- if low <= last_high {
- return Err(ProtoverError::Overlap);
- } else if low > high {
- return Err(ProtoverError::LowGreaterThanHigh);
- }
- last_high = high;
- }
- Ok(self)
- }
- /// Determine if this `ProtoSet` contains no `Version`s.
- ///
- /// # Returns
- ///
- /// * `true` if this `ProtoSet`'s length is zero, and
- /// * `false` otherwise.
- ///
- /// # Examples
- ///
- /// ```
- /// use protover::protoset::ProtoSet;
- ///
- /// let protoset: ProtoSet = ProtoSet::default();
- ///
- /// assert!(protoset.is_empty());
- /// ```
- pub fn is_empty(&self) -> bool {
- self.pairs.len() == 0
- }
- /// Determine if `version` is included within this `ProtoSet`.
- ///
- /// # Inputs
- ///
- /// * `version`: a `Version`.
- ///
- /// # Returns
- ///
- /// `true` if the `version` is contained within this set; `false` otherwise.
- ///
- /// # Examples
- ///
- /// ```
- /// # use protover::errors::ProtoverError;
- /// use protover::protoset::ProtoSet;
- ///
- /// # fn do_test() -> Result<ProtoSet, ProtoverError> {
- /// let protoset: ProtoSet = ProtoSet::from_slice(&[(0, 5), (7, 9), (13, 14)])?;
- ///
- /// assert!(protoset.contains(&5));
- /// assert!(!protoset.contains(&10));
- /// #
- /// # Ok(protoset)
- /// # }
- /// # fn main() { do_test(); } // wrap the test so we can use the ? operator
- /// ```
- pub fn contains(&self, version: &Version) -> bool {
- for &(low, high) in self.iter() {
- if low <= *version && *version <= high {
- return true;
- }
- }
- false
- }
- /// Returns all the `Version`s in `self` which are not also in the `other`
- /// `ProtoSet`.
- ///
- /// # Examples
- ///
- /// ```
- /// # use protover::errors::ProtoverError;
- /// use protover::protoset::ProtoSet;
- ///
- /// # fn do_test() -> Result<bool, ProtoverError> {
- /// let protoset: ProtoSet = "1,3-6,10-12,15-16".parse()?;
- /// let other: ProtoSet = "2,5-7,9-11,14-20".parse()?;
- ///
- /// let subset: ProtoSet = protoset.and_not_in(&other);
- ///
- /// assert_eq!(subset.expand(), vec![1, 3, 4, 12]);
- /// #
- /// # Ok(true)
- /// # }
- /// # fn main() { do_test(); } // wrap the test so we can use the ? operator
- /// ```
- pub fn and_not_in(&self, other: &Self) -> Self {
- if self.is_empty() || other.is_empty() {
- return self.clone();
- }
- let pairs = self.iter().flat_map(|&(lo, hi)| {
- let the_end = (hi + 1, hi + 1); // special case to mark the end of the range.
- let excluded_ranges = other
- .iter()
- .cloned() // have to be owned tuples, to match iter::once(the_end).
- .skip_while(move|&(_, hi2)| hi2 < lo) // skip the non-overlapping ranges.
- .take_while(move|&(lo2, _)| lo2 <= hi) // take all the overlapping ones.
- .chain(iter::once(the_end));
- let mut nextlo = lo;
- excluded_ranges.filter_map(move |(excluded_lo, excluded_hi)| {
- let pair = if nextlo < excluded_lo {
- Some((nextlo, excluded_lo - 1))
- } else {
- None
- };
- nextlo = cmp::min(excluded_hi, u32::MAX - 1) + 1;
- pair
- })
- });
- let pairs = pairs.collect();
- ProtoSet::is_ok(ProtoSet{ pairs }).expect("should be already sorted")
- }
- }
- impl FromStr for ProtoSet {
- type Err = ProtoverError;
- /// Parse the unique version numbers supported by a subprotocol from a string.
- ///
- /// # Inputs
- ///
- /// * `version_string`, a string comprised of "[0-9,-]"
- ///
- /// # Returns
- ///
- /// A `Result` whose `Ok` value is a `ProtoSet` holding all of the unique
- /// version numbers.
- ///
- /// The returned `Result`'s `Err` value is an `ProtoverError` appropriate to
- /// the error.
- ///
- /// # Errors
- ///
- /// This function will error if:
- ///
- /// * the `version_string` is an equals (`"="`) sign,
- /// * the expansion of a version range produces an error (see
- /// `expand_version_range`),
- /// * any single version number is not parseable as an `u32` in radix 10, or
- /// * there are greater than 2^16 version numbers to expand.
- ///
- /// # Examples
- ///
- /// ```
- /// use std::str::FromStr;
- ///
- /// use protover::errors::ProtoverError;
- /// use protover::protoset::ProtoSet;
- ///
- /// # fn do_test() -> Result<ProtoSet, ProtoverError> {
- /// let protoset: ProtoSet = ProtoSet::from_str("2-5,8")?;
- ///
- /// assert!(protoset.contains(&5));
- /// assert!(!protoset.contains(&10));
- ///
- /// // We can also equivalently call `ProtoSet::from_str` by doing (all
- /// // implementations of `FromStr` can be called this way, this one isn't
- /// // special):
- /// let protoset: ProtoSet = "4-6,12".parse()?;
- ///
- /// // Calling it (either way) can take really large ranges (up to `u32::MAX`):
- /// let protoset: ProtoSet = "1-70000".parse()?;
- /// let protoset: ProtoSet = "1-4294967296".parse()?;
- ///
- /// // There are lots of ways to get an `Err` from this function. Here are
- /// // a few:
- /// assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("="));
- /// assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("-"));
- /// assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("not_an_int"));
- /// assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("3-"));
- /// assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("1-,4"));
- ///
- /// // Things which would get parsed into an _empty_ `ProtoSet` are,
- /// // however, legal, and result in an empty `ProtoSet`:
- /// assert_eq!(Ok(ProtoSet::default()), ProtoSet::from_str(""));
- /// assert_eq!(Ok(ProtoSet::default()), ProtoSet::from_str(",,,"));
- /// #
- /// # Ok(protoset)
- /// # }
- /// # fn main() { do_test(); } // wrap the test so we can use the ? operator
- /// ```
- fn from_str(version_string: &str) -> Result<Self, Self::Err> {
- let mut pairs: Vec<(Version, Version)> = Vec::new();
- let pieces: ::std::str::Split<char> = version_string.split(',');
- for p in pieces {
- if p.is_empty() {
- continue;
- } else if p.contains('-') {
- let mut pair = p.splitn(2, '-');
- let low = pair.next().ok_or(ProtoverError::Unparseable)?;
- let high = pair.next().ok_or(ProtoverError::Unparseable)?;
- let lo: Version = low.parse().or(Err(ProtoverError::Unparseable))?;
- let hi: Version = high.parse().or(Err(ProtoverError::Unparseable))?;
- if lo == u32::MAX || hi == u32::MAX {
- return Err(ProtoverError::ExceedsMax);
- }
- pairs.push((lo, hi));
- } else {
- let v: u32 = p.parse().or(Err(ProtoverError::Unparseable))?;
- if v == u32::MAX {
- return Err(ProtoverError::ExceedsMax);
- }
- pairs.push((v, v));
- }
- }
- // If we were passed in an empty string, or
- // simply a comma, or a pile of commas, then return an empty ProtoSet.
- if pairs.len() == 0 {
- return Ok(ProtoSet::default());
- }
- ProtoSet::from_slice(&pairs[..])
- }
- }
- impl ToString for ProtoSet {
- /// Contracts a `ProtoSet` of versions into a string.
- ///
- /// # Returns
- ///
- /// A `String` representation of this `ProtoSet` in ascending order.
- fn to_string(&self) -> String {
- let mut final_output: Vec<String> = Vec::new();
- for &(lo, hi) in self.iter() {
- if lo != hi {
- debug_assert!(lo < hi);
- final_output.push(format!("{}-{}", lo, hi));
- } else {
- final_output.push(format!("{}", lo));
- }
- }
- final_output.join(",")
- }
- }
- /// Checks to see if there is a continuous range of integers, starting at the
- /// first in the list. Returns the last integer in the range if a range exists.
- ///
- /// # Inputs
- ///
- /// `list`, an ordered vector of `u32` integers of "[0-9,-]" representing the
- /// supported versions for a single protocol.
- ///
- /// # Returns
- ///
- /// A `bool` indicating whether the list contains a range, starting at the first
- /// in the list, a`Version` of the last integer in the range, and a `usize` of
- /// the index of that version.
- ///
- /// For example, if given vec![1, 2, 3, 5], find_range will return true,
- /// as there is a continuous range, and 3, which is the last number in the
- /// continuous range, and 2 which is the index of 3.
- fn find_range(list: &Vec<Version>) -> (bool, Version, usize) {
- if list.len() == 0 {
- return (false, 0, 0);
- }
- let mut index: usize = 0;
- let mut iterable = list.iter().peekable();
- let mut range_end = match iterable.next() {
- Some(n) => *n,
- None => return (false, 0, 0),
- };
- let mut has_range = false;
- while iterable.peek().is_some() {
- let n = *iterable.next().unwrap();
- if n != range_end + 1 {
- break;
- }
- has_range = true;
- range_end = n;
- index += 1;
- }
- (has_range, range_end, index)
- }
- impl From<Vec<Version>> for ProtoSet {
- fn from(mut v: Vec<Version>) -> ProtoSet {
- let mut version_pairs: Vec<(Version, Version)> = Vec::new();
- v.sort_unstable();
- v.dedup();
- 'vector: while !v.is_empty() {
- let (has_range, end, index): (bool, Version, usize) = find_range(&v);
- if has_range {
- let first: Version = match v.first() {
- Some(x) => *x,
- None => continue,
- };
- let last: Version = match v.get(index) {
- Some(x) => *x,
- None => continue,
- };
- debug_assert!(last == end, format!("last = {}, end = {}", last, end));
- version_pairs.push((first, last));
- v = v.split_off(index + 1);
- if v.len() == 0 {
- break 'vector;
- }
- } else {
- let last: Version = match v.get(index) {
- Some(x) => *x,
- None => continue,
- };
- version_pairs.push((last, last));
- v.remove(index);
- }
- }
- ProtoSet::from_slice(&version_pairs[..]).unwrap_or(ProtoSet::default())
- }
- }
- #[cfg(test)]
- mod test {
- use super::*;
- #[test]
- fn test_find_range() {
- assert_eq!((false, 0, 0), find_range(&vec![]));
- assert_eq!((false, 1, 0), find_range(&vec![1]));
- assert_eq!((true, 2, 1), find_range(&vec![1, 2]));
- assert_eq!((true, 3, 2), find_range(&vec![1, 2, 3]));
- assert_eq!((true, 3, 2), find_range(&vec![1, 2, 3, 5]));
- }
- macro_rules! assert_contains_each {
- ($protoset:expr, $versions:expr) => (
- for version in $versions {
- assert!($protoset.contains(version));
- }
- )
- }
- macro_rules! test_protoset_contains_versions {
- ($list:expr, $str:expr) => (
- let versions: &[Version] = $list;
- let protoset: Result<ProtoSet, ProtoverError> = ProtoSet::from_str($str);
- assert!(protoset.is_ok());
- let p = protoset.unwrap();
- assert_contains_each!(p, versions);
- )
- }
- #[test]
- fn test_versions_from_str() {
- test_protoset_contains_versions!(&[], "");
- test_protoset_contains_versions!(&[1], "1");
- test_protoset_contains_versions!(&[1, 2], "1,2");
- test_protoset_contains_versions!(&[1, 2, 3], "1-3");
- test_protoset_contains_versions!(&[1, 2, 5], "1-2,5");
- test_protoset_contains_versions!(&[1, 3, 4, 5], "1,3-5");
- test_protoset_contains_versions!(&[42, 55, 56, 57, 58], "42,55-58");
- }
- #[test]
- fn test_versions_from_str_ab() {
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("a,b"));
- }
- #[test]
- fn test_versions_from_str_negative_1() {
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("-1"));
- }
- #[test]
- fn test_versions_from_str_hyphens() {
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("--1"));
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("-1-2"));
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("1--2"));
- }
- #[test]
- fn test_versions_from_str_triple() {
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("1-2-3"));
- }
- #[test]
- fn test_versions_from_str_1exclam() {
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("1,!"));
- }
- #[test]
- fn test_versions_from_str_percent_equal() {
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("%="));
- }
- #[test]
- fn test_versions_from_str_whitespace() {
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("1,2\n"));
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("1\r,2"));
- assert_eq!(Err(ProtoverError::Unparseable), ProtoSet::from_str("1,\t2"));
- }
- #[test]
- fn test_versions_from_str_overlap() {
- assert_eq!(Err(ProtoverError::Overlap), ProtoSet::from_str("1-3,2-4"));
- }
- #[test]
- fn test_versions_from_slice_overlap() {
- assert_eq!(Err(ProtoverError::Overlap), ProtoSet::from_slice(&[(1, 3), (2, 4)]));
- }
- #[test]
- fn test_versions_from_str_max() {
- assert_eq!(Err(ProtoverError::ExceedsMax), ProtoSet::from_str("4294967295"));
- }
- #[test]
- fn test_versions_from_slice_max() {
- assert_eq!(Err(ProtoverError::ExceedsMax), ProtoSet::from_slice(&[(4294967295, 4294967295)]));
- }
- #[test]
- fn test_protoset_contains() {
- let protoset: ProtoSet = ProtoSet::from_slice(&[(1, 5), (7, 9), (13, 14)]).unwrap();
- for x in 1..6 { assert!(protoset.contains(&x), format!("should contain {}", x)); }
- for x in 7..10 { assert!(protoset.contains(&x), format!("should contain {}", x)); }
- for x in 13..15 { assert!(protoset.contains(&x), format!("should contain {}", x)); }
- for x in [6, 10, 11, 12, 15, 42, 43, 44, 45, 1234584].iter() {
- assert!(!protoset.contains(&x), format!("should not contain {}", x));
- }
- }
- #[test]
- fn test_protoset_contains_1_3() {
- let protoset: ProtoSet = ProtoSet::from_slice(&[(1, 3)]).unwrap();
- for x in 1..4 { assert!(protoset.contains(&x), format!("should contain {}", x)); }
- }
- macro_rules! assert_protoset_from_vec_contains_all {
- ($($x:expr),*) => (
- let vec: Vec<Version> = vec!($($x),*);
- let protoset: ProtoSet = vec.clone().into();
- for x in vec.iter() {
- assert!(protoset.contains(&x));
- }
- )
- }
- #[test]
- fn test_protoset_from_vec_123() {
- assert_protoset_from_vec_contains_all!(1, 2, 3);
- }
- #[test]
- fn test_protoset_from_vec_1_315() {
- assert_protoset_from_vec_contains_all!(1, 2, 3, 15);
- }
- #[test]
- fn test_protoset_from_vec_unordered() {
- let v: Vec<Version> = vec!(2, 3, 8, 4, 3, 9, 7, 2);
- let ps: ProtoSet = v.into();
- assert_eq!(ps.to_string(), "2-4,7-9");
- }
- #[test]
- fn test_protoset_into_vec() {
- let ps: ProtoSet = "1-13,42,9001,4294967294".parse().unwrap();
- let v: Vec<Version> = ps.into();
- assert!(v.contains(&7));
- assert!(v.contains(&9001));
- assert!(v.contains(&4294967294));
- }
- }
- #[cfg(all(test, feature = "bench"))]
- mod bench {
- use super::*;
- }
|