rust: Implement more memory-efficient protover datatype.

 * ADD new protover::protoset module.
 * ADD new protover::protoset::ProtoSet class for holding protover versions.
 * REMOVE protover::Versions type implementation and its method
   `from_version_string()`, and instead implement this behaviour in a more
   rust-like manner as `impl FromStr for ProtoSet`.
 * MOVE the `find_range()` utility function from protover::protover to
   protover::protoset since it's only used internally in the
   implementation of ProtoSet.
 * REMOVE the `contract_protocol_list()` function from protover::protover and
   instead refactor it (reusing nearly the entire thing, with minor superficial,
   i.e. non-behavioural, changes) into a more rusty
   `impl ToString for ProtoSet`.
 * REMOVE the `expand_version_range()` function from protover::protover and
   instead refactor it into a more rusty implementation of
   `impl Into<Vec<Version>> for ProtoSet` using the new error types in
   protover::errors.
 * FIXES part of #24031: https://bugs.torproject.org/24031.

3 files changed, 641 insertions, 209 deletions

diff --git a/src/rust/protover/lib.rs b/src/rust/protover/lib.rs
index 371d1ae58f..483260bca8 100644
--- a/src/rust/protover/lib.rs
+++ b/src/rust/protover/lib.rs
@@ -31,6 +31,7 @@ extern crate tor_allocate;
 extern crate tor_util;
 
 pub mod errors;
+pub mod protoset;
 mod protover;
 pub mod ffi;
 
diff --git a/src/rust/protover/protoset.rs b/src/rust/protover/protoset.rs
new file mode 100644
index 0000000000..f94e6299c9
--- /dev/null
+++ b/src/rust/protover/protoset.rs
@@ -0,0 +1,634 @@
+// 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::slice;
+use std::str::FromStr;
+use std::u32;
+
+use protover::MAX_PROTOCOLS_TO_EXPAND;
+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;
+        }
+
+        if self.len() > MAX_PROTOCOLS_TO_EXPAND {
+            return Err(ProtoverError::ExceedsMax);
+        }
+
+        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
+    }
+
+    /// Retain only the `Version`s in this `ProtoSet` for which the predicate
+    /// `F` returns `true`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use protover::errors::ProtoverError;
+    /// use protover::protoset::ProtoSet;
+    ///
+    /// # fn do_test() -> Result<bool, ProtoverError> {
+    /// let mut protoset: ProtoSet = "1,3-5,9".parse()?;
+    ///
+    /// // Keep only versions less than or equal to 8:
+    /// protoset.retain(|x| x <= &8);
+    ///
+    /// assert_eq!(protoset.expand(), vec![1, 3, 4, 5]);
+    /// #
+    /// # Ok(true)
+    /// # }
+    /// # fn main() { do_test(); }  // wrap the test so we can use the ? operator
+    /// ```
+    // XXX we could probably do something more efficient here. —isis
+    pub fn retain<F>(&mut self, f: F)
+        where F: FnMut(&Version) -> bool
+    {
+        let mut expanded: Vec<Version> = self.clone().expand();
+        expanded.retain(f);
+        *self = expanded.into();
+    }
+}
+
+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:
+    /// let protoset: ProtoSet = "4-6,12".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"));
+    /// assert_eq!(Err(ProtoverError::ExceedsMax), ProtoSet::from_str("1-70000"));
+    ///
+    /// // 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.trim().split(',');
+
+        for piece in pieces {
+            let p: &str = piece.trim();
+
+            if p.is_empty() {
+                continue;
+            } else if p.contains('-') {
+                let mut pair = p.split('-');
+
+                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 a bunch of whitespace, 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!(&[0, 1], "0-1");
+        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_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_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(&[(0, 5), (7, 9), (13, 14)]).unwrap();
+
+        for x in 0..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_0_3() {
+        let protoset: ProtoSet = ProtoSet::from_slice(&[(0, 3)]).unwrap();
+
+        for x in 0..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_0_315() {
+        assert_protoset_from_vec_contains_all!(0, 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::*;
+}
diff --git a/src/rust/protover/protover.rs b/src/rust/protover/protover.rs
index 8ce182cf1b..d74ca00c17 100644
--- a/src/rust/protover/protover.rs
+++ b/src/rust/protover/protover.rs
@@ -14,6 +14,7 @@ use std::u32;
 use tor_util::strings::NUL_BYTE;
 
 use errors::ProtoverError;
+use protoset::Version;
 
 /// The first version of Tor that included "proto" entries in its descriptors.
 /// Authorities should use this to decide whether to guess proto lines.
@@ -26,7 +27,7 @@ const FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS: &'static str = "0.2.9.3-alpha";
 /// before concluding that someone is trying to DoS us
 ///
 /// C_RUST_COUPLED: src/or/protover.c `MAX_PROTOCOLS_TO_EXPAND`
-const MAX_PROTOCOLS_TO_EXPAND: usize = (1<<16);
+pub(crate) const MAX_PROTOCOLS_TO_EXPAND: usize = (1<<16);
 
 /// Currently supported protocols and their versions, as a byte-slice.
 ///
@@ -159,70 +160,6 @@ impl SupportedProtocols {
     }
 }
 
-type Version = u32;
-
-/// Set of versions for a protocol.
-#[derive(Debug, PartialEq, Eq)]
-pub struct Versions(HashSet<Version>);
-
-impl Versions {
-    /// Get the unique version numbers supported by a subprotocol.
-    ///
-    /// # Inputs
-    ///
-    /// * `version_string`, a string comprised of "[0-9,-]"
-    ///
-    /// # Returns
-    ///
-    /// A `Result` whose `Ok` value is a `HashSet<u32>` holding all of the unique
-    /// version numbers.  If there were ranges in the `version_string`, then these
-    /// are expanded, i.e. `"1-3"` would expand to `HashSet<u32>::new([1, 2, 3])`.
-    /// The returned HashSet is *unordered*.
-    ///
-    /// The returned `Result`'s `Err` value is an `&'static str` with a description
-    /// of the error.
-    ///
-    /// # Errors
-    ///
-    /// This function will error if:
-    ///
-    /// * the `version_string` is empty or contains 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.
-    ///
-    fn from_version_string(
-        version_string: &str,
-    ) -> Result<Self, &'static str> {
-        let mut versions = HashSet::<Version>::new();
-
-        for piece in version_string.split(",") {
-            if piece.contains("-") {
-                for p in expand_version_range(piece)? {
-                    versions.insert(p);
-                }
-            } else if piece == "" {
-                continue;
-            } else {
-                let v = u32::from_str(piece).or(
-                    Err("invalid protocol entry"),
-                )?;
-                if v == u32::MAX {
-                    return Err("invalid protocol entry");
-                }
-                versions.insert(v);
-            }
-
-            if versions.len() > MAX_PROTOCOLS_TO_EXPAND {
-                return Err("Too many versions to expand");
-            }
-        }
-        Ok(Versions(versions))
-    }
-}
-
-
 /// Parse the subprotocol type and its version numbers.
 ///
 /// # Inputs
@@ -409,149 +346,6 @@ pub fn protover_string_supports_protocol_or_later(
     supported_versions.0.iter().any(|v| v >= &vers)
 }
 
-/// Fully expand a version range. For example, 1-3 expands to 1,2,3
-/// Helper for Versions::from_version_string
-///
-/// # Inputs
-///
-/// `range`, a string comprised of "[0-9,-]"
-///
-/// # Returns
-///
-/// A `Result` whose `Ok` value a vector of unsigned integers representing the
-/// expanded range of supported versions by a single protocol.
-/// Otherwise, the `Err` value of this `Result` is a description of the error
-///
-/// # Errors
-///
-/// This function will error if:
-///
-/// * the specified range is empty
-/// * the version range does not contain both a valid lower and upper bound.
-///
-fn expand_version_range(range: &str) -> Result<Range<u32>, &'static str> {
-    if range.is_empty() {
-        return Err("version string empty");
-    }
-
-    let mut parts = range.split("-");
-
-    let lower_string = parts.next().ok_or(
-        "cannot parse protocol range lower bound",
-    )?;
-
-    let lower = u32::from_str_radix(lower_string, 10).or(Err(
-        "cannot parse protocol range lower bound",
-    ))?;
-
-    let higher_string = parts.next().ok_or(
-        "cannot parse protocol range upper bound",
-    )?;
-
-    let higher = u32::from_str_radix(higher_string, 10).or(Err(
-        "cannot parse protocol range upper bound",
-    ))?;
-
-    if lower == u32::MAX || higher == u32::MAX {
-        return Err("protocol range value out of range");
-    }
-
-    if lower > higher {
-        return Err("protocol range is badly formed");
-    }
-
-    // We can use inclusive range syntax when it becomes stable.
-    let result = lower..higher + 1;
-
-    if result.len() > MAX_PROTOCOLS_TO_EXPAND {
-        Err("Too many protocols in expanded range")
-    } else {
-        Ok(result)
-    }
-}
-
-/// 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.
-/// Helper for compute_vote
-///
-/// # 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, and an `u32` of the last integer in the range.
-///
-/// 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.
-///
-fn find_range(list: &Vec<u32>) -> (bool, u32) {
-    if list.len() == 0 {
-        return (false, 0);
-    }
-
-    let mut iterable = list.iter().peekable();
-    let mut range_end = match iterable.next() {
-        Some(n) => *n,
-        None => return (false, 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;
-    }
-
-    (has_range, range_end)
-}
-
-/// Contracts a HashSet representation of supported versions into a string.
-/// Helper for compute_vote
-///
-/// # Inputs
-///
-/// `supported_set`, a set of integers of "[0-9,-]" representing the
-/// supported versions for a single protocol.
-///
-/// # Returns
-///
-/// A `String` representation of this set in ascending order.
-///
-fn contract_protocol_list<'a>(supported_set: &'a HashSet<Version>) -> String {
-    let mut supported: Vec<Version> =
-        supported_set.iter().map(|x| *x).collect();
-    supported.sort();
-
-    let mut final_output: Vec<String> = Vec::new();
-
-    while supported.len() != 0 {
-        let (has_range, end) = find_range(&supported);
-        let current = supported.remove(0);
-
-        if has_range {
-            final_output.push(format!(
-                "{}-{}",
-                current.to_string(),
-                &end.to_string(),
-            ));
-            supported.retain(|&x| x > end);
-        } else {
-            final_output.push(current.to_string());
-        }
-    }
-
-    final_output.join(",")
-}
-
 /// Parses a protocol list without validating the protocol names
 ///
 /// # Inputs
@@ -790,7 +584,10 @@ pub fn compute_for_old_tor(version: &str) -> &'static [u8] {
 
 #[cfg(test)]
 mod test {
-    use super::Version;
+    use std::str::FromStr;
+    use std::string::ToString;
+
+    use super::*;
 
     #[test]
     fn test_versions_from_version_string() {