Merge remote-tracking branch 'isis-github/bug24031_r5_squashed'

9 files changed, 1684 insertions, 940 deletions

diff --git a/changes/bug24031 b/changes/bug24031
new file mode 100644
index 0000000000..adffa46d8a
--- /dev/null
+++ b/changes/bug24031
@@ -0,0 +1,13 @@
+  o Major bugfixes (protover, voting):
+    - Revise Rust implementation of protover to use a more memory-efficient
+      voting algorithm and corresponding data structures, thus avoiding a
+      potential (but small impact) DoS attack where specially crafted protocol
+      strings would expand to several potential megabytes in memory.  In the
+      process, several portions of code were revised to be methods on new,
+      custom types, rather than functions taking interchangeable types, thus
+      increasing type safety of the module.  Custom error types and handling
+      were added as well, in order to facilitate better error dismissal/handling
+      in outside crates and avoid mistakenly passing an internal error string to
+      C over the FFI boundary.  Many tests were added, and some previous
+      differences between the C and Rust implementations have been
+      remedied. Fixes 24031; bugfix on 0.3.3.1-alpha.
diff --git a/src/or/protover.c b/src/or/protover.c
index cb168085c6..6532f09c2f 100644
--- a/src/or/protover.c
+++ b/src/or/protover.c
@@ -671,7 +671,9 @@ int
 protover_all_supported(const char *s, char **missing_out)
 {
   int all_supported = 1;
-  smartlist_t *missing;
+  smartlist_t *missing_some;
+  smartlist_t *missing_completely;
+  smartlist_t *missing_all;
 
   if (!s) {
     return 1;
@@ -684,7 +686,8 @@ protover_all_supported(const char *s, char **missing_out)
     return 1;
   }
 
-  missing = smartlist_new();
+  missing_some = smartlist_new();
+  missing_completely = smartlist_new();
 
   SMARTLIST_FOREACH_BEGIN(entries, const proto_entry_t *, ent) {
     protocol_type_t tp;
@@ -696,26 +699,86 @@ protover_all_supported(const char *s, char **missing_out)
     }
 
     SMARTLIST_FOREACH_BEGIN(ent->ranges, const proto_range_t *, range) {
+      proto_entry_t *unsupported = tor_malloc_zero(sizeof(proto_entry_t));
+      proto_range_t *versions = tor_malloc_zero(sizeof(proto_range_t));
       uint32_t i;
+
+      unsupported->name = tor_strdup(ent->name);
+      unsupported->ranges = smartlist_new();
+
       for (i = range->low; i <= range->high; ++i) {
         if (!protover_is_supported_here(tp, i)) {
-          goto unsupported;
+          if (versions->low == 0 && versions->high == 0) {
+            versions->low = i;
+            /* Pre-emptively add the high now, just in case we're in a single
+             * version range (e.g. "Link=999"). */
+            versions->high = i;
+          }
+          /* If the last one to be unsupported is one less than the current
+           * one, we're in a continous range, so set the high field. */
+          if ((versions->high && versions->high == i - 1) ||
+              /* Similarly, if the last high wasn't set and we're currently
+               * one higher than the low, add current index as the highest
+               * known high. */
+              (!versions->high && versions->low == i - 1)) {
+            versions->high = i;
+            continue;
+          }
+        } else {
+          /* If we hit a supported version, and we previously had a range,
+           * we've hit a non-continuity. Copy the previous range and add it to
+           * the unsupported->ranges list and zero-out the previous range for
+           * the next iteration. */
+          if (versions->low != 0 && versions->high != 0) {
+            proto_range_t *versions_to_add = tor_malloc(sizeof(proto_range_t));
+
+            versions_to_add->low = versions->low;
+            versions_to_add->high = versions->high;
+            smartlist_add(unsupported->ranges, versions_to_add);
+
+            versions->low = 0;
+            versions->high = 0;
+          }
         }
       }
+      /* Once we've run out of versions to check, see if we had any unsupported
+       * ones and, if so, add them to unsupported->ranges. */
+      if (versions->low != 0 && versions->high != 0) {
+        smartlist_add(unsupported->ranges, versions);
+      }
+      /* Finally, if we had something unsupported, add it to the list of
+       * missing_some things and mark that there was something missing. */
+      if (smartlist_len(unsupported->ranges) != 0) {
+        smartlist_add(missing_some, (void*) unsupported);
+        all_supported = 0;
+      } else {
+        proto_entry_free(unsupported);
+        tor_free(versions);
+      }
     } SMARTLIST_FOREACH_END(range);
 
     continue;
 
   unsupported:
     all_supported = 0;
-    smartlist_add(missing, (void*) ent);
+    smartlist_add(missing_completely, (void*) ent);
   } SMARTLIST_FOREACH_END(ent);
 
+  /* We keep the two smartlists separate so that we can free the proto_entry_t
+   * we created and put in missing_some, so here we add them together to build
+   * the string. */
+  missing_all = smartlist_new();
+  smartlist_add_all(missing_all, missing_some);
+  smartlist_add_all(missing_all, missing_completely);
+
   if (missing_out && !all_supported) {
-    tor_assert(0 != smartlist_len(missing));
-    *missing_out = encode_protocol_list(missing);
+    tor_assert(smartlist_len(missing_all) != 0);
+    *missing_out = encode_protocol_list(missing_all);
   }
-  smartlist_free(missing);
+  SMARTLIST_FOREACH(missing_some, proto_entry_t *, ent, proto_entry_free(ent));
+  smartlist_free(missing_some);
+  smartlist_free(missing_completely);
+  smartlist_free(missing_all);
 
   SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
   smartlist_free(entries);
diff --git a/src/rust/protover/errors.rs b/src/rust/protover/errors.rs
new file mode 100644
index 0000000000..56473d12e6
--- /dev/null
+++ b/src/rust/protover/errors.rs
@@ -0,0 +1,43 @@
+// Copyright (c) 2018, The Tor Project, Inc.
+// Copyright (c) 2018, isis agora lovecruft
+// See LICENSE for licensing information
+
+//! Various errors which may occur during protocol version parsing.
+
+use std::fmt;
+use std::fmt::Display;
+
+/// All errors which may occur during protover parsing routines.
+#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
+#[allow(missing_docs)] // See Display impl for error descriptions
+pub enum ProtoverError {
+    Overlap,
+    LowGreaterThanHigh,
+    Unparseable,
+    ExceedsMax,
+    ExceedsExpansionLimit,
+    UnknownProtocol,
+    ExceedsNameLimit,
+}
+
+/// Descriptive error messages for `ProtoverError` variants.
+impl Display for ProtoverError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match *self {
+            ProtoverError::Overlap
+                => write!(f, "Two or more (low, high) protover ranges would overlap once expanded."),
+            ProtoverError::LowGreaterThanHigh
+                => write!(f, "The low in a (low, high) protover range was greater than high."),
+            ProtoverError::Unparseable
+                => write!(f, "The protover string was unparseable."),
+            ProtoverError::ExceedsMax
+                => write!(f, "The high in a (low, high) protover range exceeds u32::MAX."),
+            ProtoverError::ExceedsExpansionLimit
+                => write!(f, "The protover string would exceed the maximum expansion limit."),
+            ProtoverError::UnknownProtocol
+                => write!(f, "A protocol in the protover string we attempted to parse is unknown."),
+            ProtoverError::ExceedsNameLimit
+                => write!(f, "An unrecognised protocol name was too long."),
+        }
+    }
+}
diff --git a/src/rust/protover/ffi.rs b/src/rust/protover/ffi.rs
index a9d5013c6d..2dfeda87b2 100644
--- a/src/rust/protover/ffi.rs
+++ b/src/rust/protover/ffi.rs
@@ -9,27 +9,29 @@ use libc::{c_char, c_int, uint32_t};
 use std::ffi::CStr;
 use std::ffi::CString;
 
-use protover::*;
 use smartlist::*;
 use tor_allocate::allocate_and_copy_string;
 
+use errors::ProtoverError;
+use protover::*;
+
 /// Translate C enums to Rust Proto enums, using the integer value of the C
-/// enum to map to its associated Rust enum
+/// enum to map to its associated Rust enum.
 ///
 /// C_RUST_COUPLED: src/or/protover.h `protocol_type_t`
-fn translate_to_rust(c_proto: uint32_t) -> Result<Proto, &'static str> {
+fn translate_to_rust(c_proto: uint32_t) -> Result<Protocol, ProtoverError> {
     match c_proto {
-        0 => Ok(Proto::Link),
-        1 => Ok(Proto::LinkAuth),
-        2 => Ok(Proto::Relay),
-        3 => Ok(Proto::DirCache),
-        4 => Ok(Proto::HSDir),
-        5 => Ok(Proto::HSIntro),
-        6 => Ok(Proto::HSRend),
-        7 => Ok(Proto::Desc),
-        8 => Ok(Proto::Microdesc),
-        9 => Ok(Proto::Cons),
-        _ => Err("Invalid protocol type"),
+        0 => Ok(Protocol::Link),
+        1 => Ok(Protocol::LinkAuth),
+        2 => Ok(Protocol::Relay),
+        3 => Ok(Protocol::DirCache),
+        4 => Ok(Protocol::HSDir),
+        5 => Ok(Protocol::HSIntro),
+        6 => Ok(Protocol::HSRend),
+        7 => Ok(Protocol::Desc),
+        8 => Ok(Protocol::Microdesc),
+        9 => Ok(Protocol::Cons),
+        _ => Err(ProtoverError::UnknownProtocol),
     }
 }
 
@@ -54,19 +56,26 @@ pub extern "C" fn protover_all_supported(
         Err(_) => return 1,
     };
 
-    let (is_supported, unsupported) = all_supported(relay_version);
+    let relay_proto_entry: UnvalidatedProtoEntry = match relay_version.parse() {
+        Ok(n)  => n,
+        Err(_) => return 1,
+    };
+    let maybe_unsupported: Option<UnvalidatedProtoEntry> = relay_proto_entry.all_supported();
 
-    if unsupported.len() > 0 {
-        let c_unsupported = match CString::new(unsupported) {
+    if maybe_unsupported.is_some() {
+        let unsupported: UnvalidatedProtoEntry = maybe_unsupported.unwrap();
+        let c_unsupported: CString = match CString::new(unsupported.to_string()) {
             Ok(n) => n,
             Err(_) => return 1,
         };
 
         let ptr = c_unsupported.into_raw();
         unsafe { *missing_out = ptr };
+
+        return 0;
     }
 
-    return if is_supported { 1 } else { 0 };
+    1
 }
 
 /// Provide an interface for C to translate arguments and return types for
@@ -89,16 +98,18 @@ pub extern "C" fn protocol_list_supports_protocol(
         Ok(n) => n,
         Err(_) => return 1,
     };
-
-    let protocol = match translate_to_rust(c_protocol) {
-        Ok(n) => n,
+    let proto_entry: UnvalidatedProtoEntry = match protocol_list.parse() {
+        Ok(n)  => n,
         Err(_) => return 0,
     };
-
-    let is_supported =
-        protover_string_supports_protocol(protocol_list, protocol, version);
-
-    return if is_supported { 1 } else { 0 };
+    let protocol: UnknownProtocol = match translate_to_rust(c_protocol) {
+        Ok(n) => n.into(),
+        Err(_) => return 0,
+    };
+    match proto_entry.supports_protocol(&protocol, &version) {
+        false => return 0,
+        true  => return 1,
+    }
 }
 
 /// Provide an interface for C to translate arguments and return types for
@@ -127,13 +138,15 @@ pub extern "C" fn protocol_list_supports_protocol_or_later(
         Err(_) => return 0,
     };
 
-    let is_supported = protover_string_supports_protocol_or_later(
-        protocol_list,
-        protocol,
-        version,
-    );
+    let proto_entry: UnvalidatedProtoEntry = match protocol_list.parse() {
+        Ok(n)  => n,
+        Err(_) => return 1,
+    };
 
-    return if is_supported { 1 } else { 0 };
+    if proto_entry.supports_protocol_or_later(&protocol.into(), &version) {
+        return 1;
+    }
+    0
 }
 
 /// Provide an interface for C to translate arguments and return types for
@@ -148,6 +161,8 @@ pub extern "C" fn protover_get_supported_protocols() -> *const c_char {
 
 /// Provide an interface for C to translate arguments and return types for
 /// protover::compute_vote
+//
+// Why is the threshold a signed integer? —isis
 #[no_mangle]
 pub extern "C" fn protover_compute_vote(
     list: *const Stringlist,
@@ -162,10 +177,19 @@ pub extern "C" fn protover_compute_vote(
     // Dereference of raw pointer requires an unsafe block. The pointer is
     // checked above to ensure it is not null.
     let data: Vec<String> = unsafe { (*list).get_list() };
+    let hold: usize = threshold as usize;
+    let mut proto_entries: Vec<UnvalidatedProtoEntry> = Vec::new();
 
-    let vote = compute_vote(data, threshold);
+    for datum in data {
+        let entry: UnvalidatedProtoEntry = match datum.parse() {
+            Ok(x)  => x,
+            Err(_) => continue,
+        };
+        proto_entries.push(entry);
+    }
+    let vote: UnvalidatedProtoEntry = ProtoverVote::compute(&proto_entries, &hold);
 
-    allocate_and_copy_string(&vote)
+    allocate_and_copy_string(&vote.to_string())
 }
 
 /// Provide an interface for C to translate arguments and return types for
@@ -180,7 +204,7 @@ pub extern "C" fn protover_is_supported_here(
         Err(_) => return 0,
     };
 
-    let is_supported = is_supported_here(protocol, version);
+    let is_supported = is_supported_here(&protocol, &version);
 
     return if is_supported { 1 } else { 0 };
 }
@@ -207,6 +231,6 @@ pub extern "C" fn protover_compute_for_old_tor(version: *const c_char) -> *const
         Err(_) => return empty.as_ptr(),
     };
 
-    supported = compute_for_old_tor(&version);
+    supported = compute_for_old_tor_cstr(&version);
     supported.as_ptr()
 }
diff --git a/src/rust/protover/lib.rs b/src/rust/protover/lib.rs
index d1d49d2a59..ce964196fd 100644
--- a/src/rust/protover/lib.rs
+++ b/src/rust/protover/lib.rs
@@ -22,6 +22,8 @@
 //! protocols to develop independently, without having to claim compatibility
 //! with specific versions of Tor.
 
+#[deny(missing_docs)]
+
 extern crate libc;
 extern crate smartlist;
 extern crate external;
@@ -29,9 +31,8 @@ extern crate tor_allocate;
 #[macro_use]
 extern crate tor_util;
 
-#[macro_use]
-extern crate tor_log;
-
+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..4afc50edf8
--- /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 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
+    }
+
+    /// 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 (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.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 fd1f41d780..514aeffc58 100644
--- a/src/rust/protover/protover.rs
+++ b/src/rust/protover/protover.rs
@@ -1,18 +1,20 @@
 // Copyright (c) 2016-2017, The Tor Project, Inc. */
 // See LICENSE for licensing information */
 
-use std::str;
-use std::str::FromStr;
+use std::collections::HashMap;
+use std::collections::hash_map;
 use std::ffi::CStr;
 use std::fmt;
-use std::collections::{HashMap, HashSet};
-use std::ops::Range;
+use std::str;
+use std::str::FromStr;
 use std::string::String;
-use std::u32;
 
-use tor_log::{LogSeverity, LogDomain};
 use external::c_tor_version_as_new_as;
 
+use errors::ProtoverError;
+use protoset::Version;
+use protoset::ProtoSet;
+
 /// The first version of Tor that included "proto" entries in its descriptors.
 /// Authorities should use this to decide whether to guess proto lines.
 ///
@@ -29,8 +31,8 @@ const MAX_PROTOCOLS_TO_EXPAND: usize = (1<<16);
 /// Known subprotocols in Tor. Indicates which subprotocol a relay supports.
 ///
 /// C_RUST_COUPLED: src/or/protover.h `protocol_type_t`
-#[derive(Hash, Eq, PartialEq, Debug)]
-pub enum Proto {
+#[derive(Clone, Hash, Eq, PartialEq, Debug)]
+pub enum Protocol {
     Cons,
     Desc,
     DirCache,
@@ -43,7 +45,7 @@ pub enum Proto {
     Relay,
 }
 
-impl fmt::Display for Proto {
+impl fmt::Display for Protocol {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "{:?}", self)
     }
@@ -53,26 +55,51 @@ impl fmt::Display for Proto {
 /// Error if the string is an unrecognized protocol name.
 ///
 /// C_RUST_COUPLED: src/or/protover.c `PROTOCOL_NAMES`
-impl FromStr for Proto {
-    type Err = &'static str;
+impl FromStr for Protocol {
+    type Err = ProtoverError;
 
     fn from_str(s: &str) -> Result<Self, Self::Err> {
         match s {
-            "Cons" => Ok(Proto::Cons),
-            "Desc" => Ok(Proto::Desc),
-            "DirCache" => Ok(Proto::DirCache),
-            "HSDir" => Ok(Proto::HSDir),
-            "HSIntro" => Ok(Proto::HSIntro),
-            "HSRend" => Ok(Proto::HSRend),
-            "Link" => Ok(Proto::Link),
-            "LinkAuth" => Ok(Proto::LinkAuth),
-            "Microdesc" => Ok(Proto::Microdesc),
-            "Relay" => Ok(Proto::Relay),
-            _ => Err("Not a valid protocol type"),
+            "Cons" => Ok(Protocol::Cons),
+            "Desc" => Ok(Protocol::Desc),
+            "DirCache" => Ok(Protocol::DirCache),
+            "HSDir" => Ok(Protocol::HSDir),
+            "HSIntro" => Ok(Protocol::HSIntro),
+            "HSRend" => Ok(Protocol::HSRend),
+            "Link" => Ok(Protocol::Link),
+            "LinkAuth" => Ok(Protocol::LinkAuth),
+            "Microdesc" => Ok(Protocol::Microdesc),
+            "Relay" => Ok(Protocol::Relay),
+            _ => Err(ProtoverError::UnknownProtocol),
         }
     }
 }
 
+/// A protocol string which is not one of the `Protocols` we currently know
+/// about.
+#[derive(Clone, Debug, Hash, Eq, PartialEq)]
+pub struct UnknownProtocol(String);
+
+impl fmt::Display for UnknownProtocol {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.0)
+    }
+}
+
+impl FromStr for UnknownProtocol {
+    type Err = ProtoverError;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        Ok(UnknownProtocol(s.to_string()))
+    }
+}
+
+impl From<Protocol> for UnknownProtocol {
+    fn from(p: Protocol) -> UnknownProtocol {
+        UnknownProtocol(p.to_string())
+    }
+}
+
 /// Get a CStr representation of current supported protocols, for
 /// passing to C, or for converting to a `&str` for Rust.
 ///
@@ -102,639 +129,456 @@ pub(crate) fn get_supported_protocols_cstr() -> &'static CStr {
            Relay=1-2")
 }
 
-/// Get a string representation of current supported protocols.
-///
-/// # Returns
-///
-/// An `&'a str` whose value is the existing protocols supported by tor.
-/// Returned data is in the format as follows:
-///
-/// "HSDir=1-1 LinkAuth=1"
-pub fn get_supported_protocols<'a>() -> &'a str {
-    let supported_cstr: &'static CStr = get_supported_protocols_cstr();
-    let supported: &str = match supported_cstr.to_str() {
-        Ok(x)  => x,
-        Err(_) => "",
-    };
+/// A map of protocol names to the versions of them which are supported.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct ProtoEntry(HashMap<Protocol, ProtoSet>);
 
-    supported
+impl Default for ProtoEntry {
+    fn default() -> ProtoEntry {
+        ProtoEntry( HashMap::new() )
+    }
 }
 
-pub struct SupportedProtocols(HashMap<Proto, Versions>);
+impl ProtoEntry {
+    /// Get an iterator over the `Protocol`s and their `ProtoSet`s in this `ProtoEntry`.
+    pub fn iter(&self) -> hash_map::Iter<Protocol, ProtoSet> {
+        self.0.iter()
+    }
 
-impl SupportedProtocols {
-    pub fn from_proto_entries<I, S>(protocol_strs: I) -> Result<Self, &'static str>
-    where
-        I: Iterator<Item = S>,
-        S: AsRef<str>,
-    {
-        let mut parsed = HashMap::new();
-        for subproto in protocol_strs {
-            let (name, version) = get_proto_and_vers(subproto.as_ref())?;
-            parsed.insert(name, version);
-        }
-        Ok(SupportedProtocols(parsed))
+    /// Translate the supported tor versions from a string into a
+    /// ProtoEntry, which is useful when looking up a specific
+    /// subprotocol.
+    pub fn supported() -> Result<Self, ProtoverError> {
+        let supported_cstr: &'static CStr = get_supported_protocols_cstr();
+        let supported: &str = supported_cstr.to_str().unwrap_or("");
+
+        supported.parse()
     }
 
-    /// Translates a string representation of a protocol list to a
-    /// SupportedProtocols instance.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use protover::SupportedProtocols;
-    ///
-    /// let supported_protocols = SupportedProtocols::from_proto_entries_string(
-    ///     "HSDir=1-2 HSIntro=3-4"
-    /// );
-    /// ```
-    pub fn from_proto_entries_string(
-        proto_entries: &str,
-    ) -> Result<Self, &'static str> {
-        Self::from_proto_entries(proto_entries.split(" "))
+    pub fn len(&self) -> usize {
+        self.0.len()
     }
 
-    /// Translate the supported tor versions from a string into a
-    /// HashMap, which is useful when looking up a specific
-    /// subprotocol.
-    ///
-    fn tor_supported() -> Result<Self, &'static str> {
-        Self::from_proto_entries_string(get_supported_protocols())
+    pub fn get(&self, protocol: &Protocol) -> Option<&ProtoSet> {
+        self.0.get(protocol)
     }
-}
 
-type Version = u32;
+    pub fn insert(&mut self, key: Protocol, value: ProtoSet) {
+        self.0.insert(key, value);
+    }
+
+    pub fn remove(&mut self, key: &Protocol) -> Option<ProtoSet> {
+        self.0.remove(key)
+    }
 
-/// Set of versions for a protocol.
-#[derive(Debug, PartialEq, Eq)]
-pub struct Versions(HashSet<Version>);
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+}
 
-impl Versions {
-    /// Get the unique version numbers supported by a subprotocol.
+impl FromStr for ProtoEntry {
+    type Err = ProtoverError;
+
+    /// Parse a string of subprotocol types and their version numbers.
     ///
     /// # Inputs
     ///
-    /// * `version_string`, a string comprised of "[0-9,-]"
+    /// * A `protocol_entry` string, comprised of a keywords, an "=" sign, and
+    /// one or more version numbers, each separated by a space.  For example,
+    /// `"Cons=3-4 HSDir=1"`.
     ///
     /// # 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);
-            }
+    /// A `Result` whose `Ok` value is a `ProtoEntry`, where the
+    /// first element is the subprotocol type (see `protover::Protocol`) and the last
+    /// element is an ordered set of `(low, high)` unique version numbers which are supported.
+    /// Otherwise, the `Err` value of this `Result` is a `ProtoverError`.
+    fn from_str(protocol_entry: &str) -> Result<ProtoEntry, ProtoverError> {
+        let mut proto_entry: ProtoEntry = ProtoEntry::default();
+        let entries = protocol_entry.split(' ');
+
+        for entry in entries {
+            let mut parts = entry.splitn(2, '=');
+
+            let proto = match parts.next() {
+                Some(n) => n,
+                None => return Err(ProtoverError::Unparseable),
+            };
+
+            let vers = match parts.next() {
+                Some(n) => n,
+                None => return Err(ProtoverError::Unparseable),
+            };
+            let versions: ProtoSet = vers.parse()?;
+            let proto_name: Protocol = proto.parse()?;
 
-            if versions.len() > MAX_PROTOCOLS_TO_EXPAND {
-                return Err("Too many versions to expand");
+            proto_entry.insert(proto_name, versions);
+
+            if proto_entry.len() > MAX_PROTOCOLS_TO_EXPAND {
+                return Err(ProtoverError::ExceedsMax);
             }
         }
-        Ok(Versions(versions))
+        Ok(proto_entry)
     }
 }
 
-/// Parse the subprotocol type and its version numbers.
-///
-/// # Inputs
-///
-/// * A `protocol_entry` string, comprised of a keyword, an "=" sign, and one
-/// or more version numbers.
-///
-/// # Returns
-///
-/// A `Result` whose `Ok` value is a tuple of `(Proto, HashSet<u32>)`, where the
-/// first element is the subprotocol type (see `protover::Proto`) and the last
-/// element is a(n unordered) set of unique version numbers which are supported.
-/// Otherwise, the `Err` value of this `Result` is a description of the error
-///
-fn get_proto_and_vers<'a>(
-    protocol_entry: &'a str,
-) -> Result<(Proto, Versions), &'static str> {
-    let mut parts = protocol_entry.splitn(2, "=");
-
-    let proto = match parts.next() {
-        Some(n) => n,
-        None => return Err("invalid protover entry"),
-    };
-
-    let vers = match parts.next() {
-        Some(n) => n,
-        None => return Err("invalid protover entry"),
-    };
-
-    let versions = Versions::from_version_string(vers)?;
-    let proto_name = proto.parse()?;
-
-    Ok((proto_name, versions))
-}
+/// Generate an implementation of `ToString` for either a `ProtoEntry` or an
+/// `UnvalidatedProtoEntry`.
+macro_rules! impl_to_string_for_proto_entry {
+    ($t:ty) => (
+        impl ToString for $t {
+            fn to_string(&self) -> String {
+                let mut parts: Vec<String> = Vec::new();
 
-/// Parses a single subprotocol entry string into subprotocol and version
-/// parts, and then checks whether any of those versions are unsupported.
-/// Helper for protover::all_supported
-///
-/// # Inputs
-///
-/// Accepted data is in the string format as follows:
-///
-/// "HSDir=1-1"
-///
-/// # Returns
-///
-/// Returns `true` if the protocol entry is well-formatted and only contains
-/// versions that are also supported in tor. Otherwise, returns false
-///
-fn contains_only_supported_protocols(proto_entry: &str) -> bool {
-    let (name, mut vers) = match get_proto_and_vers(proto_entry) {
-        Ok(n) => n,
-        Err("Too many versions to expand") => {
-            tor_log_msg!(
-                LogSeverity::Warn,
-                LogDomain::Net,
-                "get_versions",
-                "When expanding a protocol list from an authority, I \
-                got too many protocols. This is possibly an attack or a bug, \
-                unless the Tor network truly has expanded to support over {} \
-                different subprotocol versions. The offending string was: {}",
-                MAX_PROTOCOLS_TO_EXPAND,
-                proto_entry
-            );
-            return false;
+                for (protocol, versions) in self.iter() {
+                    parts.push(format!("{}={}", protocol.to_string(), versions.to_string()));
+                }
+                parts.sort_unstable();
+                parts.join(" ")
+            }
         }
-        Err(_) => return false,
-    };
-
-    let currently_supported = match SupportedProtocols::tor_supported() {
-        Ok(n) => n.0,
-        Err(_) => return false,
-    };
-
-    let supported_versions = match currently_supported.get(&name) {
-        Some(n) => n,
-        None => return false,
-    };
-
-    vers.0.retain(|x| !supported_versions.0.contains(x));
-    vers.0.is_empty()
+    )
 }
 
-/// Determine if we support every protocol a client supports, and if not,
-/// determine which protocols we do not have support for.
-///
-/// # Inputs
-///
-/// Accepted data is in the string format as follows:
-///
-/// "HSDir=1-1 LinkAuth=1-2"
-///
-/// # Returns
-///
-/// Return `true` if every protocol version is one that we support.
-/// Otherwise, return `false`.
-/// Optionally, return parameters which the client supports but which we do not
-///
-/// # Examples
-/// ```
-/// use protover::all_supported;
-///
-/// let (is_supported, unsupported)  = all_supported("Link=1");
-/// assert_eq!(true, is_supported);
-///
-/// let (is_supported, unsupported)  = all_supported("Link=5-6");
-/// assert_eq!(false, is_supported);
-/// assert_eq!("Link=5-6", unsupported);
-///
-pub fn all_supported(protocols: &str) -> (bool, String) {
-    let unsupported = protocols
-        .split_whitespace()
-        .filter(|v| !contains_only_supported_protocols(v))
-        .collect::<Vec<&str>>();
+impl_to_string_for_proto_entry!(ProtoEntry);
+impl_to_string_for_proto_entry!(UnvalidatedProtoEntry);
+
+/// A `ProtoEntry`, but whose `Protocols` can be any `UnknownProtocol`, not just
+/// the supported ones enumerated in `Protocols`.  The protocol versions are
+/// validated, however.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct UnvalidatedProtoEntry(HashMap<UnknownProtocol, ProtoSet>);
 
-    (unsupported.is_empty(), unsupported.join(" "))
+impl Default for UnvalidatedProtoEntry {
+    fn default() -> UnvalidatedProtoEntry {
+        UnvalidatedProtoEntry( HashMap::new() )
+    }
 }
 
-/// Return true iff the provided protocol list includes support for the
-/// indicated protocol and version.
-/// Otherwise, return false
-///
-/// # Inputs
-///
-/// * `list`, a string representation of a list of protocol entries.
-/// * `proto`, a `Proto` to test support for
-/// * `vers`, a `Version` version which we will go on to determine whether the
-/// specified protocol supports.
-///
-/// # Examples
-/// ```
-/// use protover::*;
-///
-/// let is_supported = protover_string_supports_protocol("Link=3-4 Cons=1",
-///                                                      Proto::Cons,1);
-/// assert_eq!(true, is_supported);
-///
-/// let is_not_supported = protover_string_supports_protocol("Link=3-4 Cons=1",
-///                                                           Proto::Cons,5);
-/// assert_eq!(false, is_not_supported)
-/// ```
-pub fn protover_string_supports_protocol(
-    list: &str,
-    proto: Proto,
-    vers: Version,
-) -> bool {
-    let supported = match SupportedProtocols::from_proto_entries_string(list) {
-        Ok(result) => result.0,
-        Err(_) => return false,
-    };
+impl UnvalidatedProtoEntry {
+    /// Get an iterator over the `Protocol`s and their `ProtoSet`s in this `ProtoEntry`.
+    pub fn iter(&self) -> hash_map::Iter<UnknownProtocol, ProtoSet> {
+        self.0.iter()
+    }
 
-    let supported_versions = match supported.get(&proto) {
-        Some(n) => n,
-        None => return false,
-    };
+    pub fn get(&self, protocol: &UnknownProtocol) -> Option<&ProtoSet> {
+        self.0.get(protocol)
+    }
 
-    supported_versions.0.contains(&vers)
-}
+    pub fn insert(&mut self, key: UnknownProtocol, value: ProtoSet) {
+        self.0.insert(key, value);
+    }
 
-/// As protover_string_supports_protocol(), but also returns True if
-/// any later version of the protocol is supported.
-///
-/// # Examples
-/// ```
-/// use protover::*;
-///
-/// let is_supported = protover_string_supports_protocol_or_later(
-///                       "Link=3-4 Cons=5", Proto::Cons, 5);
-///
-/// assert_eq!(true, is_supported);
-///
-/// let is_supported = protover_string_supports_protocol_or_later(
-///                       "Link=3-4 Cons=5", Proto::Cons, 4);
-///
-/// assert_eq!(true, is_supported);
-///
-/// let is_supported = protover_string_supports_protocol_or_later(
-///                       "Link=3-4 Cons=5", Proto::Cons, 6);
-///
-/// assert_eq!(false, is_supported);
-/// ```
-pub fn protover_string_supports_protocol_or_later(
-    list: &str,
-    proto: Proto,
-    vers: u32,
-) -> bool {
-    let supported = match SupportedProtocols::from_proto_entries_string(list) {
-        Ok(result) => result.0,
-        Err(_) => return false,
-    };
+    pub fn remove(&mut self, key: &UnknownProtocol) -> Option<ProtoSet> {
+        self.0.remove(key)
+    }
 
-    let supported_versions = match supported.get(&proto) {
-        Some(n) => n,
-        None => return false,
-    };
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
 
-    supported_versions.0.iter().any(|v| v >= &vers)
-}
+    pub fn len(&self) -> usize {
+        let mut total: usize = 0;
 
-/// 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");
+        for (_, versions) in self.iter() {
+            total += versions.len();
+        }
+        total
     }
 
-    let mut parts = range.split("-");
+    /// Determine if we support every protocol a client supports, and if not,
+    /// determine which protocols we do not have support for.
+    ///
+    /// # Returns
+    ///
+    /// Optionally, return parameters which the client supports but which we do not.
+    ///
+    /// # Examples
+    /// ```
+    /// use protover::UnvalidatedProtoEntry;
+    ///
+    /// let protocols: UnvalidatedProtoEntry = "LinkAuth=1 Microdesc=1-2 Relay=2".parse().unwrap();
+    /// let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    /// assert_eq!(true, unsupported.is_none());
+    ///
+    /// let protocols: UnvalidatedProtoEntry = "Link=1-2 Wombat=9".parse().unwrap();
+    /// let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    /// assert_eq!(true, unsupported.is_some());
+    /// assert_eq!("Wombat=9", &unsupported.unwrap().to_string());
+    /// ```
+    pub fn all_supported(&self) -> Option<UnvalidatedProtoEntry> {
+        let mut unsupported: UnvalidatedProtoEntry = UnvalidatedProtoEntry::default();
+        let supported: ProtoEntry = match ProtoEntry::supported() {
+            Ok(x)  => x,
+            Err(_) => return None,
+        };
 
-    let lower_string = parts.next().ok_or(
-        "cannot parse protocol range lower bound",
-    )?;
+        for (protocol, versions) in self.iter() {
+            let is_supported: Result<Protocol, ProtoverError> = protocol.0.parse();
+            let supported_protocol: Protocol;
 
-    let lower = u32::from_str_radix(lower_string, 10).or(Err(
-        "cannot parse protocol range lower bound",
-    ))?;
+            // If the protocol wasn't even in the enum, then we definitely don't
+            // know about it and don't support any of its versions.
+            if is_supported.is_err() {
+                if !versions.is_empty() {
+                    unsupported.insert(protocol.clone(), versions.clone());
+                }
+                continue;
+            } else {
+                supported_protocol = is_supported.unwrap();
+            }
 
-    let higher_string = parts.next().ok_or(
-        "cannot parse protocol range upper bound",
-    )?;
+            let maybe_supported_versions: Option<&ProtoSet> = supported.get(&supported_protocol);
+            let supported_versions: &ProtoSet;
+            let mut unsupported_versions: ProtoSet;
 
-    let higher = u32::from_str_radix(higher_string, 10).or(Err(
-        "cannot parse protocol range upper bound",
-    ))?;
+            // If the protocol wasn't in the map, then we don't know about it
+            // and don't support any of its versions.  Add its versions to the
+            // map (if it has versions).
+            if maybe_supported_versions.is_none() {
+                if !versions.is_empty() {
+                    unsupported.insert(protocol.clone(), versions.clone());
+                }
+                continue;
+            } else {
+                supported_versions = maybe_supported_versions.unwrap();
+            }
+            unsupported_versions = versions.clone();
+            unsupported_versions.retain(|x| !supported_versions.contains(x));
 
-    if lower == u32::MAX || higher == u32::MAX {
-        return Err("protocol range value out of range");
-    }
+            if !unsupported_versions.is_empty() {
+                unsupported.insert(protocol.clone(), unsupported_versions);
+            }
+        }
 
-    if lower > higher {
-        return Err("protocol range is badly formed");
+        if unsupported.is_empty() {
+            return None;
+        }
+        Some(unsupported)
     }
 
-    // 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)
+    /// Determine if we have support for some protocol and version.
+    ///
+    /// # Inputs
+    ///
+    /// * `proto`, an `UnknownProtocol` to test support for
+    /// * `vers`, a `Version` which we will go on to determine whether the
+    /// specified protocol supports.
+    ///
+    /// # Return
+    ///
+    /// Returns `true` iff this `UnvalidatedProtoEntry` includes support for the
+    /// indicated protocol and version, and `false` otherwise.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use std::str::FromStr;
+    /// use protover::*;
+    /// # use protover::errors::ProtoverError;
+    ///
+    /// # fn do_test () -> Result<UnvalidatedProtoEntry, ProtoverError> {
+    /// let proto: UnvalidatedProtoEntry = "Link=3-4 Cons=1 Doggo=3-5".parse()?;
+    /// assert_eq!(true, proto.supports_protocol(&Protocol::Cons.into(), &1));
+    /// assert_eq!(false, proto.supports_protocol(&Protocol::Cons.into(), &5));
+    /// assert_eq!(true, proto.supports_protocol(&UnknownProtocol::from_str("Doggo")?, &4));
+    /// # Ok(proto)
+    /// # } fn main () { do_test(); }
+    /// ```
+    pub fn supports_protocol(&self, proto: &UnknownProtocol, vers: &Version) -> bool {
+        let supported_versions: &ProtoSet = match self.get(proto) {
+            Some(n) => n,
+            None => return false,
+        };
+        supported_versions.contains(&vers)
     }
-}
 
-/// 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);
+    /// As `UnvalidatedProtoEntry::supports_protocol()`, but also returns `true`
+    /// if any later version of the protocol is supported.
+    ///
+    /// # Examples
+    /// ```
+    /// use protover::*;
+    /// # use protover::errors::ProtoverError;
+    ///
+    /// # fn do_test () -> Result<UnvalidatedProtoEntry, ProtoverError> {
+    /// let proto: UnvalidatedProtoEntry = "Link=3-4 Cons=5".parse()?;
+    ///
+    /// assert_eq!(true, proto.supports_protocol_or_later(&Protocol::Cons.into(), &5));
+    /// assert_eq!(true, proto.supports_protocol_or_later(&Protocol::Cons.into(), &4));
+    /// assert_eq!(false, proto.supports_protocol_or_later(&Protocol::Cons.into(), &6));
+    /// # Ok(proto)
+    /// # } fn main () { do_test(); }
+    /// ```
+    pub fn supports_protocol_or_later(&self, proto: &UnknownProtocol, vers: &Version) -> bool {
+        let supported_versions: &ProtoSet = match self.get(&proto) {
+            Some(n) => n,
+            None => return false,
+        };
+        supported_versions.iter().any(|v| v.1 >= *vers)
     }
+}
 
-    let mut iterable = list.iter().peekable();
-    let mut range_end = match iterable.next() {
-        Some(n) => *n,
-        None => return (false, 0),
-    };
+impl FromStr for UnvalidatedProtoEntry {
+    type Err = ProtoverError;
 
-    let mut has_range = false;
+    /// Parses a protocol list without validating the protocol names.
+    ///
+    /// # Inputs
+    ///
+    /// * `protocol_string`, a string comprised of keys and values, both which are
+    /// strings. The keys are the protocol names while values are a string
+    /// representation of the supported versions.
+    ///
+    /// The input is _not_ expected to be a subset of the Protocol types
+    ///
+    /// # 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` whose `Display`
+    /// impl has a description of the error.
+    ///
+    /// # Errors
+    ///
+    /// This function will error if:
+    ///
+    /// * The protocol string does not follow the "protocol_name=version_list"
+    ///   expected format, or
+    /// * If the version string is malformed. See `impl FromStr for ProtoSet`.
+    fn from_str(protocol_string: &str) -> Result<UnvalidatedProtoEntry, ProtoverError> {
+        let mut parsed: UnvalidatedProtoEntry = UnvalidatedProtoEntry::default();
+
+        for subproto in protocol_string.split(' ') {
+            let mut parts = subproto.splitn(2, '=');
+
+            let name = match parts.next() {
+                Some("") => return Err(ProtoverError::Unparseable),
+                Some(n) => n,
+                None => return Err(ProtoverError::Unparseable),
+            };
+            let vers = match parts.next() {
+                Some(n) => n,
+                None => return Err(ProtoverError::Unparseable),
+            };
+            let versions = ProtoSet::from_str(vers)?;
+            let protocol = UnknownProtocol::from_str(name)?;
 
-    while iterable.peek().is_some() {
-        let n = *iterable.next().unwrap();
-        if n != range_end + 1 {
-            break;
+            parsed.insert(protocol, versions);
         }
-
-        has_range = true;
-        range_end = n;
+        Ok(parsed)
     }
-
-    (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();
+/// Pretend a `ProtoEntry` is actually an `UnvalidatedProtoEntry`.
+impl From<ProtoEntry> for UnvalidatedProtoEntry {
+    fn from(proto_entry: ProtoEntry) -> UnvalidatedProtoEntry {
+        let mut unvalidated: UnvalidatedProtoEntry = UnvalidatedProtoEntry::default();
 
-    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());
+        for (protocol, versions) in proto_entry.iter() {
+            unvalidated.insert(UnknownProtocol::from(protocol.clone()), versions.clone());
         }
+        unvalidated
     }
-
-    final_output.join(",")
 }
 
-/// Parses a protocol list without validating the protocol names
-///
-/// # Inputs
-///
-/// * `protocol_string`, a string comprised of keys and values, both which are
-/// strings. The keys are the protocol names while values are a string
-/// representation of the supported versions.
-///
-/// The input is _not_ expected to be a subset of the Proto types
-///
-/// # Returns
-///
-/// A `Result` whose `Ok` value is a `HashSet<Version>` holding all of the
-/// unique version numbers.
-///
-/// The returned `Result`'s `Err` value is an `&'static str` with a description
-/// of the error.
+/// A mapping of protocols to a count of how many times each of their `Version`s
+/// were voted for or supported.
 ///
-/// # Errors
+/// # Warning
 ///
-/// This function will error if:
-///
-/// * The protocol string does not follow the "protocol_name=version_list"
-/// expected format
-/// * If the version string is malformed. See `Versions::from_version_string`.
-///
-fn parse_protocols_from_string_with_no_validation<'a>(
-    protocol_string: &'a str,
-) -> Result<HashMap<String, Versions>, &'static str> {
-    let mut parsed: HashMap<String, Versions> = HashMap::new();
-
-    for subproto in protocol_string.split(" ") {
-        let mut parts = subproto.splitn(2, "=");
-
-        let name = match parts.next() {
-            Some("") => return Err("invalid protover entry"),
-            Some(n) => n,
-            None => return Err("invalid protover entry"),
-        };
+/// The "protocols" are *not* guaranteed to be known/supported `Protocol`s, in
+/// order to allow new subprotocols to be introduced even if Directory
+/// Authorities don't yet know of them.
+pub struct ProtoverVote( HashMap<UnknownProtocol, HashMap<Version, usize>> );
 
-        let vers = match parts.next() {
-            Some(n) => n,
-            None => return Err("invalid protover entry"),
-        };
-
-        let versions = Versions::from_version_string(vers)?;
-
-        parsed.insert(String::from(name), versions);
+impl Default for ProtoverVote {
+    fn default() -> ProtoverVote {
+        ProtoverVote( HashMap::new() )
     }
-    Ok(parsed)
 }
 
-/// Protocol voting implementation.
-///
-/// Given a list of strings describing protocol versions, return a new
-/// string encoding all of the protocols that are listed by at
-/// least threshold of the inputs.
-///
-/// The string is sorted according to the following conventions:
-///   - Protocols names are alphabetized
-///   - Protocols are in order low to high
-///   - Individual and ranges are listed together. For example,
-///     "3, 5-10,13"
-///   - All entries are unique
-///
-/// # Examples
-/// ```
-/// use protover::compute_vote;
-///
-/// let protos = vec![String::from("Link=3-4"), String::from("Link=3")];
-/// let vote = compute_vote(protos, 2);
-/// assert_eq!("Link=3", vote)
-/// ```
-pub fn compute_vote(
-    list_of_proto_strings: Vec<String>,
-    threshold: i32,
-) -> String {
-    let empty = String::from("");
+impl IntoIterator for ProtoverVote {
+    type Item = (UnknownProtocol, HashMap<Version, usize>);
+    type IntoIter = hash_map::IntoIter<UnknownProtocol, HashMap<Version, usize>>;
 
-    if list_of_proto_strings.is_empty() {
-        return empty;
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.into_iter()
     }
+}
 
-    // all_count is a structure to represent the count of the number of
-    // supported versions for a specific protocol. For example, in JSON format:
-    // {
-    //  "FirstSupportedProtocol": {
-    //      "1": "3",
-    //      "2": "1"
-    //  }
-    // }
-    // means that FirstSupportedProtocol has three votes which support version
-    // 1, and one vote that supports version 2
-    let mut all_count: HashMap<String, HashMap<Version, usize>> =
-        HashMap::new();
-
-    // parse and collect all of the protos and their versions and collect them
-    for vote in list_of_proto_strings {
-        let this_vote: HashMap<String, Versions> =
-            match parse_protocols_from_string_with_no_validation(&vote) {
-                Ok(result) => result,
-                Err(_) => continue,
-            };
-        for (protocol, versions) in this_vote {
-            let supported_vers: &mut HashMap<Version, usize> =
-                all_count.entry(protocol).or_insert(HashMap::new());
-
-            for version in versions.0 {
-                let counter: &mut usize =
-                    supported_vers.entry(version).or_insert(0);
-                *counter += 1;
-            }
-        }
+impl ProtoverVote {
+    pub fn entry(&mut self, key: UnknownProtocol)
+        -> hash_map::Entry<UnknownProtocol, HashMap<Version, usize>>
+    {
+        self.0.entry(key)
     }
 
-    let mut final_output: HashMap<String, String> =
-        HashMap::with_capacity(get_supported_protocols().split(" ").count());
+    /// Protocol voting implementation.
+    ///
+    /// Given a slice of `UnvalidatedProtoEntry`s and a vote `threshold`, return
+    /// a new `UnvalidatedProtoEntry` encoding all of the protocols that are
+    /// listed by at least `threshold` of the inputs.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use protover::ProtoverVote;
+    /// use protover::UnvalidatedProtoEntry;
+    ///
+    /// let protos: &[UnvalidatedProtoEntry] = &["Link=3-4".parse().unwrap(),
+    ///                                          "Link=3".parse().unwrap()];
+    /// let vote = ProtoverVote::compute(protos, &2);
+    /// assert_eq!("Link=3", vote.to_string());
+    /// ```
+    // C_RUST_COUPLED: /src/or/protover.c protover_compute_vote
+    pub fn compute(proto_entries: &[UnvalidatedProtoEntry], threshold: &usize) -> UnvalidatedProtoEntry {
+        let mut all_count: ProtoverVote = ProtoverVote::default();
+        let mut final_output: UnvalidatedProtoEntry = UnvalidatedProtoEntry::default();
 
-    // Go through and remove verstions that are less than the threshold
-    for (protocol, versions) in all_count {
-        let mut meets_threshold = HashSet::new();
-        for (version, count) in versions {
-            if count >= threshold as usize {
-                meets_threshold.insert(version);
-            }
+        if proto_entries.is_empty() {
+            return final_output;
         }
 
-        // For each protocol, compress its version list into the expected
-        // protocol version string format
-        let contracted = contract_protocol_list(&meets_threshold);
-        if !contracted.is_empty() {
-            final_output.insert(protocol, contracted);
+        // parse and collect all of the protos and their versions and collect them
+        for vote in proto_entries {
+            // C_RUST_DIFFERS: This doesn't actually differ, bu this check on
+            // the total is here to make it match.  Because the C version calls
+            // expand_protocol_list() which checks if there would be too many
+            // subprotocols *or* individual version numbers, i.e. more than
+            // MAX_PROTOCOLS_TO_EXPAND, and does this *per vote*, we need to
+            // match it's behaviour and ensure we're not allowing more than it
+            // would.
+            if vote.len() > MAX_PROTOCOLS_TO_EXPAND {
+                continue;
+            }
+
+            for (protocol, versions) in vote.iter() {
+                let supported_vers: &mut HashMap<Version, usize> =
+                    all_count.entry(protocol.clone()).or_insert(HashMap::new());
+
+                for version in versions.clone().expand() {
+                    let counter: &mut usize =
+                        supported_vers.entry(version).or_insert(0);
+                    *counter += 1;
+                }
+            }
         }
-    }
 
-    write_vote_to_string(&final_output)
-}
+        for (protocol, mut versions) in all_count {
+            // Go through and remove versions that are less than the threshold
+            versions.retain(|_, count| *count as usize >= *threshold);
 
-/// Return a String comprised of protocol entries in alphabetical order
-///
-/// # Inputs
-///
-/// * `vote`, a `HashMap` comprised of keys and values, both which are strings.
-/// The keys are the protocol names while values are a string representation of
-/// the supported versions.
-///
-/// # Returns
-///
-/// A `String` whose value is series of pairs, comprising of the protocol name
-/// and versions that it supports. The string takes the following format:
-///
-/// "first_protocol_name=1,2-5, second_protocol_name=4,5"
-///
-/// Sorts the keys in alphabetical order and creates the expected subprotocol
-/// entry format.
-///
-fn write_vote_to_string(vote: &HashMap<String, String>) -> String {
-    let mut keys: Vec<&String> = vote.keys().collect();
-    keys.sort();
+            if versions.len() > 0 {
+                let voted_versions: Vec<Version> = versions.keys().cloned().collect();
+                let voted_protoset: ProtoSet = ProtoSet::from(voted_versions);
 
-    let mut output = Vec::new();
-    for key in keys {
-        // TODO error in indexing here?
-        output.push(format!("{}={}", key, vote[key]));
+                final_output.insert(protocol, voted_protoset);
+            }
+        }
+        final_output
     }
-    output.join(" ")
 }
 
 /// Returns a boolean indicating whether the given protocol and version is
@@ -742,30 +586,29 @@ fn write_vote_to_string(vote: &HashMap<String, String>) -> String {
 ///
 /// # Examples
 /// ```
-/// use protover::*;
+/// use protover::is_supported_here;
+/// use protover::Protocol;
 ///
-/// let is_supported = is_supported_here(Proto::Link, 10);
+/// let is_supported = is_supported_here(&Protocol::Link, &10);
 /// assert_eq!(false, is_supported);
 ///
-/// let is_supported = is_supported_here(Proto::Link, 1);
+/// let is_supported = is_supported_here(&Protocol::Link, &1);
 /// assert_eq!(true, is_supported);
 /// ```
-pub fn is_supported_here(proto: Proto, vers: Version) -> bool {
-    let currently_supported = match SupportedProtocols::tor_supported() {
-        Ok(result) => result.0,
+pub fn is_supported_here(proto: &Protocol, vers: &Version) -> bool {
+    let currently_supported: ProtoEntry = match ProtoEntry::supported() {
+        Ok(result) => result,
         Err(_) => return false,
     };
-
-    let supported_versions = match currently_supported.get(&proto) {
+    let supported_versions = match currently_supported.get(proto) {
         Some(n) => n,
         None => return false,
     };
-
-    supported_versions.0.contains(&vers)
+    supported_versions.contains(vers)
 }
 
-/// Older versions of Tor cannot infer their own subprotocols
-/// Used to determine which subprotocols are supported by older Tor versions.
+/// Since older versions of Tor cannot infer their own subprotocols,
+/// determine which subprotocols are supported by older Tor versions.
 ///
 /// # Inputs
 ///
@@ -779,186 +622,194 @@ pub fn is_supported_here(proto: Proto, vers: Version) -> bool {
 /// "HSDir=1-1 LinkAuth=1"
 ///
 /// This function returns the protocols that are supported by the version input,
-/// only for tor versions older than FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS.
+/// only for tor versions older than `FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS`
+/// (but not older than 0.2.4.19).  For newer tors (or older than 0.2.4.19), it
+/// returns an empty string.
+///
+/// # Note
 ///
-/// C_RUST_COUPLED: src/rust/protover.c `compute_for_old_tor`
-pub fn compute_for_old_tor(version: &str) -> &'static CStr {
+/// This function is meant to be called for/within FFI code.  If you'd
+/// like to use this code in Rust, please see `compute_for_old_tor()`.
+//
+// C_RUST_COUPLED: src/rust/protover.c `compute_for_old_tor`
+pub(crate) fn compute_for_old_tor_cstr(version: &str) -> &'static CStr {
     let empty: &'static CStr = cstr!("");
 
     if c_tor_version_as_new_as(version, FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS) {
         return empty;
     }
-
     if c_tor_version_as_new_as(version, "0.2.9.1-alpha") {
         return cstr!("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1-2 \
                       Link=1-4 LinkAuth=1 Microdesc=1-2 Relay=1-2");
     }
-
     if c_tor_version_as_new_as(version, "0.2.7.5") {
         return cstr!("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 \
                       Link=1-4 LinkAuth=1 Microdesc=1-2 Relay=1-2");
     }
-
     if c_tor_version_as_new_as(version, "0.2.4.19") {
         return cstr!("Cons=1 Desc=1 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 \
                       Link=1-4 LinkAuth=1 Microdesc=1 Relay=1-2");
     }
-
     empty
 }
 
+/// Since older versions of Tor cannot infer their own subprotocols,
+/// determine which subprotocols are supported by older Tor versions.
+///
+/// # Inputs
+///
+/// * `version`, a string comprised of "[0-9a-z.-]"
+///
+/// # Returns
+///
+/// A `Result` whose `Ok` value is an `&'static str` encoding a list of protocol
+/// names and supported versions. The string takes the following format:
+///
+/// "HSDir=1-1 LinkAuth=1"
+///
+/// This function returns the protocols that are supported by the version input,
+/// only for tor versions older than `FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS`.
+/// (but not older than 0.2.4.19).  For newer tors (or older than 0.2.4.19), its
+/// `Ok` `Result` contains an empty string.
+///
+/// Otherwise, its `Err` contains a `ProtoverError::Unparseable` if the
+/// `version` string was invalid utf-8.
+///
+/// # Note
+///
+/// This function is meant to be called for/within non-FFI Rust code.
+//
+// C_RUST_COUPLED: src/rust/protover.c `compute_for_old_tor`
+pub fn compute_for_old_tor(version: &str) -> Result<&'static str, ProtoverError> {
+    // .to_str() fails with a Utf8Error if it couldn't validate the
+    // utf-8, so convert that here into an Unparseable ProtoverError.
+    compute_for_old_tor_cstr(version).to_str().or(Err(ProtoverError::Unparseable))
+}
+
 #[cfg(test)]
 mod test {
-    use super::Version;
+    use std::str::FromStr;
+    use std::string::ToString;
+
+    use super::*;
+
+    macro_rules! assert_protoentry_is_parseable {
+        ($e:expr) => (
+            let protoentry: Result<ProtoEntry, ProtoverError> = $e.parse();
+
+            assert!(protoentry.is_ok(), format!("{:?}", protoentry.err()));
+        )
+    }
+
+    macro_rules! assert_protoentry_is_unparseable {
+        ($e:expr) => (
+            let protoentry: Result<ProtoEntry, ProtoverError> = $e.parse();
+
+            assert!(protoentry.is_err());
+        )
+    }
 
     #[test]
-    fn test_versions_from_version_string() {
-        use std::collections::HashSet;
+    fn test_protoentry_from_str_multiple_protocols_multiple_versions() {
+        assert_protoentry_is_parseable!("Cons=3-4 Link=1,3-5");
+    }
 
-        use super::Versions;
+    #[test]
+    fn test_protoentry_from_str_empty() {
+        assert_protoentry_is_unparseable!("");
+    }
 
-        assert_eq!(Err("invalid protocol entry"), Versions::from_version_string("a,b"));
-        assert_eq!(Err("invalid protocol entry"), Versions::from_version_string("1,!"));
+    #[test]
+    fn test_protoentry_from_str_single_protocol_single_version() {
+        assert_protoentry_is_parseable!("HSDir=1");
+    }
 
-        {
-            let mut versions: HashSet<Version> = HashSet::new();
-            versions.insert(1);
-            assert_eq!(versions, Versions::from_version_string("1").unwrap().0);
-        }
-        {
-            let mut versions: HashSet<Version> = HashSet::new();
-            versions.insert(1);
-            versions.insert(2);
-            assert_eq!(versions, Versions::from_version_string("1,2").unwrap().0);
-        }
-        {
-            let mut versions: HashSet<Version> = HashSet::new();
-            versions.insert(1);
-            versions.insert(2);
-            versions.insert(3);
-            assert_eq!(versions, Versions::from_version_string("1-3").unwrap().0);
-        }
-        {
-            let mut versions: HashSet<Version> = HashSet::new();
-            versions.insert(1);
-            versions.insert(2);
-            versions.insert(5);
-            assert_eq!(versions, Versions::from_version_string("1-2,5").unwrap().0);
-        }
-        {
-            let mut versions: HashSet<Version> = HashSet::new();
-            versions.insert(1);
-            versions.insert(3);
-            versions.insert(4);
-            versions.insert(5);
-            assert_eq!(versions, Versions::from_version_string("1,3-5").unwrap().0);
-        }
+    #[test]
+    fn test_protoentry_from_str_unknown_protocol() {
+        assert_protoentry_is_unparseable!("Ducks=5-7,8");
     }
 
     #[test]
-    fn test_contains_only_supported_protocols() {
-        use super::contains_only_supported_protocols;
-
-        assert_eq!(false, contains_only_supported_protocols(""));
-        assert_eq!(true, contains_only_supported_protocols("Cons="));
-        assert_eq!(true, contains_only_supported_protocols("Cons=1"));
-        assert_eq!(false, contains_only_supported_protocols("Cons=0"));
-        assert_eq!(false, contains_only_supported_protocols("Cons=0-1"));
-        assert_eq!(false, contains_only_supported_protocols("Cons=5"));
-        assert_eq!(false, contains_only_supported_protocols("Cons=1-5"));
-        assert_eq!(false, contains_only_supported_protocols("Cons=1,5"));
-        assert_eq!(false, contains_only_supported_protocols("Cons=5,6"));
-        assert_eq!(false, contains_only_supported_protocols("Cons=1,5,6"));
-        assert_eq!(true, contains_only_supported_protocols("Cons=1,2"));
-        assert_eq!(true, contains_only_supported_protocols("Cons=1-2"));
+    fn test_protoentry_from_str_allowed_number_of_versions() {
+        assert_protoentry_is_parseable!("Desc=1-4294967294");
     }
 
     #[test]
-    fn test_find_range() {
-        use super::find_range;
+    fn test_protoentry_from_str_too_many_versions() {
+        assert_protoentry_is_unparseable!("Desc=1-4294967295");
+    }
 
-        assert_eq!((false, 0), find_range(&vec![]));
-        assert_eq!((false, 1), find_range(&vec![1]));
-        assert_eq!((true, 2), find_range(&vec![1, 2]));
-        assert_eq!((true, 3), find_range(&vec![1, 2, 3]));
-        assert_eq!((true, 3), find_range(&vec![1, 2, 3, 5]));
+    #[test]
+    fn test_protoentry_from_str_() {
+        assert_protoentry_is_unparseable!("");
     }
 
     #[test]
-    fn test_expand_version_range() {
-        use super::expand_version_range;
-
-        assert_eq!(Err("version string empty"), expand_version_range(""));
-        assert_eq!(Ok(1..3), expand_version_range("1-2"));
-        assert_eq!(Ok(1..5), expand_version_range("1-4"));
-        assert_eq!(
-            Err("cannot parse protocol range lower bound"),
-            expand_version_range("a")
-        );
-        assert_eq!(
-            Err("cannot parse protocol range upper bound"),
-            expand_version_range("1-a")
-        );
-        assert_eq!(Ok(1000..66536), expand_version_range("1000-66535"));
-        assert_eq!(Err("Too many protocols in expanded range"),
-                   expand_version_range("1000-66536"));
+    fn test_protoentry_all_supported_single_protocol_single_version() {
+        let protocol: UnvalidatedProtoEntry = "Cons=1".parse().unwrap();
+        let unsupported: Option<UnvalidatedProtoEntry> = protocol.all_supported();
+        assert_eq!(true, unsupported.is_none());
     }
 
     #[test]
-    fn test_contract_protocol_list() {
-        use std::collections::HashSet;
-        use super::contract_protocol_list;
+    fn test_protoentry_all_supported_multiple_protocol_multiple_versions() {
+        let protocols: UnvalidatedProtoEntry = "Link=3-4 Desc=2".parse().unwrap();
+        let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+        assert_eq!(true, unsupported.is_none());
+    }
 
-        {
-            let mut versions = HashSet::<Version>::new();
-            assert_eq!(String::from(""), contract_protocol_list(&versions));
+    #[test]
+    fn test_protoentry_all_supported_three_values() {
+        let protocols: UnvalidatedProtoEntry = "LinkAuth=1 Microdesc=1-2 Relay=2".parse().unwrap();
+        let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+        assert_eq!(true, unsupported.is_none());
+    }
 
-            versions.insert(1);
-            assert_eq!(String::from("1"), contract_protocol_list(&versions));
+    #[test]
+    fn test_protoentry_all_supported_unknown_protocol() {
+        let protocols: UnvalidatedProtoEntry = "Wombat=9".parse().unwrap();
+        let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+        assert_eq!(true, unsupported.is_some());
+        assert_eq!("Wombat=9", &unsupported.unwrap().to_string());
+    }
 
-            versions.insert(2);
-            assert_eq!(String::from("1-2"), contract_protocol_list(&versions));
-        }
+    #[test]
+    fn test_protoentry_all_supported_unsupported_high_version() {
+        let protocols: UnvalidatedProtoEntry = "HSDir=12-100".parse().unwrap();
+        let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+        assert_eq!(true, unsupported.is_some());
+        assert_eq!("HSDir=12-100", &unsupported.unwrap().to_string());
+    }
 
-        {
-            let mut versions = HashSet::<Version>::new();
-            versions.insert(1);
-            versions.insert(3);
-            assert_eq!(String::from("1,3"), contract_protocol_list(&versions));
-        }
+    #[test]
+    fn test_protoentry_all_supported_unsupported_low_version() {
+        let protocols: UnvalidatedProtoEntry = "Cons=0-1".parse().unwrap();
+        let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+        assert_eq!(true, unsupported.is_some());
+        assert_eq!("Cons=0", &unsupported.unwrap().to_string());
+    }
 
-        {
-            let mut versions = HashSet::<Version>::new();
-            versions.insert(1);
-            versions.insert(2);
-            versions.insert(3);
-            versions.insert(4);
-            assert_eq!(String::from("1-4"), contract_protocol_list(&versions));
-        }
+    #[test]
+    fn test_contract_protocol_list() {
+        let mut versions = "";
+        assert_eq!(String::from(versions), ProtoSet::from_str(&versions).unwrap().to_string());
 
-        {
-            let mut versions = HashSet::<Version>::new();
-            versions.insert(1);
-            versions.insert(3);
-            versions.insert(5);
-            versions.insert(6);
-            versions.insert(7);
-            assert_eq!(
-                String::from("1,3,5-7"),
-                contract_protocol_list(&versions)
-            );
-        }
+        versions = "1";
+        assert_eq!(String::from(versions), ProtoSet::from_str(&versions).unwrap().to_string());
 
-        {
-            let mut versions = HashSet::<Version>::new();
-            versions.insert(1);
-            versions.insert(2);
-            versions.insert(3);
-            versions.insert(500);
-            assert_eq!(
-                String::from("1-3,500"),
-                contract_protocol_list(&versions)
-            );
-        }
+        versions = "1-2";
+        assert_eq!(String::from(versions), ProtoSet::from_str(&versions).unwrap().to_string());
+
+        versions = "1,3";
+        assert_eq!(String::from(versions), ProtoSet::from_str(&versions).unwrap().to_string());
+
+        versions = "1-4";
+        assert_eq!(String::from(versions), ProtoSet::from_str(&versions).unwrap().to_string());
+
+        versions = "1,3,5-7";
+        assert_eq!(String::from(versions), ProtoSet::from_str(&versions).unwrap().to_string());
+
+        versions = "1-3,500";
+        assert_eq!(String::from(versions), ProtoSet::from_str(&versions).unwrap().to_string());
     }
 }
diff --git a/src/rust/protover/tests/protover.rs b/src/rust/protover/tests/protover.rs
index f4e394b3e2..2db01a1634 100644
--- a/src/rust/protover/tests/protover.rs
+++ b/src/rust/protover/tests/protover.rs
@@ -3,289 +3,392 @@
 
 extern crate protover;
 
+use protover::ProtoEntry;
+use protover::ProtoverVote;
+use protover::UnvalidatedProtoEntry;
+use protover::errors::ProtoverError;
+
 #[test]
-fn parse_protocol_list_with_single_proto_and_single_version() {
-    let protocol = "Cons=1";
-    let (is_supported, unsupported) = protover::all_supported(protocol);
-    assert_eq!(true, is_supported);
-    assert_eq!("", &unsupported);
+fn parse_protocol_with_single_proto_and_single_version() {
+    let _: ProtoEntry = "Cons=1".parse().unwrap();
 }
 
 #[test]
-fn parse_protocol_list_with_single_protocol_and_multiple_versions() {
-    let protocol = "Cons=1-2";
-    let (is_supported, unsupported) = protover::all_supported(protocol);
-    assert_eq!(true, is_supported);
-    assert_eq!("", &unsupported);
+fn parse_protocol_with_single_protocol_and_multiple_versions() {
+    let _: ProtoEntry = "Cons=1-2".parse().unwrap();
 }
 
 #[test]
-fn parse_protocol_list_with_different_single_protocol_and_single_version() {
-    let protocol = "HSDir=1";
-    let (is_supported, unsupported) = protover::all_supported(protocol);
-    assert_eq!(true, is_supported);
-    assert_eq!("", &unsupported);
+fn parse_protocol_with_different_single_protocol_and_single_version() {
+    let _: ProtoEntry = "HSDir=1".parse().unwrap();
 }
 
 #[test]
-fn parse_protocol_list_with_single_protocol_and_supported_version() {
-    let protocol = "Desc=2";
-    let (is_supported, unsupported) = protover::all_supported(protocol);
-    assert_eq!(true, is_supported);
-    assert_eq!("", &unsupported);
+fn parse_protocol_with_single_protocol_and_supported_version() {
+    let _: ProtoEntry = "Desc=2".parse().unwrap();
 }
 
 #[test]
-fn parse_protocol_list_with_two_protocols_and_single_version() {
-    let protocols = "Cons=1 HSDir=1";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!(true, is_supported);
-    assert_eq!("", &unsupported);
+fn parse_protocol_with_two_protocols_and_single_version() {
+    let _: ProtoEntry = "Cons=1 HSDir=1".parse().unwrap();
 }
 
-
 #[test]
-fn parse_protocol_list_with_single_protocol_and_two_nonsequential_versions() {
-    let protocol = "Desc=1,2";
-    let (is_supported, unsupported) = protover::all_supported(protocol);
-    assert_eq!(true, is_supported);
-    assert_eq!("", &unsupported);
+fn parse_protocol_with_single_protocol_and_two_sequential_versions() {
+    let _: ProtoEntry = "Desc=1-2".parse().unwrap();
 }
 
+#[test]
+fn parse_protocol_with_single_protocol_and_protocol_range() {
+    let _: ProtoEntry = "Link=1-4".parse().unwrap();
+}
 
 #[test]
-fn parse_protocol_list_with_single_protocol_and_two_sequential_versions() {
-    let protocol = "Desc=1-2";
-    let (is_supported, unsupported) = protover::all_supported(protocol);
-    assert_eq!(true, is_supported);
-    assert_eq!("", &unsupported);
+fn parse_protocol_with_single_protocol_and_protocol_set() {
+    let _: ProtoEntry = "Link=3-4 Desc=2".parse().unwrap();
 }
 
 #[test]
-fn parse_protocol_list_with_single_protocol_and_protocol_range_returns_set() {
-    let protocol = "Link=1-4";
-    let (is_supported, unsupported) = protover::all_supported(protocol);
-    assert_eq!(true, is_supported);
-    assert_eq!("", &unsupported);
+fn protocol_all_supported_with_single_protocol_and_protocol_set() {
+    let protocols: UnvalidatedProtoEntry = "Link=3-4 Desc=2".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    assert_eq!(true, unsupported.is_none());
 }
 
 #[test]
-fn parse_protocol_list_with_single_protocol_and_protocol_set() {
-    let protocols = "Link=3-4 Desc=2";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!(true, is_supported);
-    assert_eq!("", &unsupported);
+fn protocol_all_supported_with_two_values() {
+    let protocols: UnvalidatedProtoEntry = "Microdesc=1-2 Relay=2".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    assert_eq!(true, unsupported.is_none());
 }
 
 #[test]
-fn protover_all_supported_with_two_values() {
-    let protocols = "Microdesc=1-2 Relay=2";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!("", &unsupported);
-    assert_eq!(true, is_supported);
+fn protocol_all_supported_with_one_value() {
+    let protocols: UnvalidatedProtoEntry = "Microdesc=1-2".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    assert_eq!(true, unsupported.is_none());
 }
 
 #[test]
-fn protover_all_supported_with_one_value() {
-    let protocols = "Microdesc=1-2";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!("", &unsupported);
-    assert_eq!(true, is_supported);
+#[should_panic]
+fn parse_protocol_unvalidated_with_empty() {
+    let _: UnvalidatedProtoEntry = "".parse().unwrap();
 }
 
 #[test]
-fn protover_all_supported_with_empty() {
-    let protocols = "";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!(true, is_supported);
-    assert_eq!("", &unsupported);
+#[should_panic]
+fn parse_protocol_validated_with_empty() {
+    let _: UnvalidatedProtoEntry = "".parse().unwrap();
 }
 
 #[test]
-fn protover_all_supported_with_three_values() {
-    let protocols = "LinkAuth=1 Microdesc=1-2 Relay=2";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!("", &unsupported);
-    assert_eq!(true, is_supported);
+fn protocol_all_supported_with_three_values() {
+    let protocols: UnvalidatedProtoEntry = "LinkAuth=1 Microdesc=1-2 Relay=2".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    assert_eq!(true, unsupported.is_none());
 }
 
 #[test]
-fn protover_all_supported_with_unsupported_protocol() {
-    let protocols = "Wombat=9";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!(false, is_supported);
-    assert_eq!("Wombat=9", &unsupported);
+fn protocol_all_supported_with_unsupported_protocol() {
+    let protocols: UnvalidatedProtoEntry = "Wombat=9".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    assert_eq!(true, unsupported.is_some());
+    assert_eq!("Wombat=9", &unsupported.unwrap().to_string());
 }
 
 #[test]
-fn protover_all_supported_with_unsupported_versions() {
-    let protocols = "Link=3-999";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!(false, is_supported);
-    assert_eq!("Link=3-999", &unsupported);
+fn protocol_all_supported_with_unsupported_versions() {
+    let protocols: UnvalidatedProtoEntry = "Link=3-999".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    assert_eq!(true, unsupported.is_some());
+    assert_eq!("Link=6-999", &unsupported.unwrap().to_string());
 }
 
 #[test]
-fn protover_all_supported_with_unsupported_low_version() {
-    let protocols = "Cons=0-1";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!(false, is_supported);
-    assert_eq!("Cons=0-1", &unsupported);
+fn protocol_all_supported_with_unsupported_low_version() {
+    let protocols: UnvalidatedProtoEntry = "Cons=0-1".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    assert_eq!(true, unsupported.is_some());
+    assert_eq!("Cons=0", &unsupported.unwrap().to_string());
 }
 
 #[test]
-fn protover_all_supported_with_unsupported_high_version() {
-    let protocols = "Cons=1-3";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!(false, is_supported);
-    assert_eq!("Cons=1-3", &unsupported);
+fn protocol_all_supported_with_unsupported_high_version() {
+    let protocols: UnvalidatedProtoEntry = "Cons=1-2,999".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    assert_eq!(true, unsupported.is_some());
+    assert_eq!("Cons=999", &unsupported.unwrap().to_string());
 }
 
 #[test]
-fn protover_all_supported_with_mix_of_supported_and_unsupproted() {
-    let protocols = "Link=3-4 Wombat=9";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!(false, is_supported);
-    assert_eq!("Wombat=9", &unsupported);
+fn protocol_all_supported_with_mix_of_supported_and_unsupproted() {
+    let protocols: UnvalidatedProtoEntry = "Link=3-4 Wombat=9".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    assert_eq!(true, unsupported.is_some());
+    assert_eq!("Wombat=9", &unsupported.unwrap().to_string());
 }
 
 #[test]
 fn protover_string_supports_protocol_returns_true_for_single_supported() {
-    let protocols = "Link=3-4 Cons=1";
-    let is_supported = protover::protover_string_supports_protocol(
-        protocols,
-        protover::Proto::Cons,
-        1,
-    );
+    let protocols: UnvalidatedProtoEntry = "Link=3-4 Cons=1".parse().unwrap();
+    let is_supported = protocols.supports_protocol(&protover::Protocol::Cons.into(), &1);
     assert_eq!(true, is_supported);
 }
 
 #[test]
 fn protover_string_supports_protocol_returns_false_for_single_unsupported() {
-    let protocols = "Link=3-4 Cons=1";
-    let is_supported = protover::protover_string_supports_protocol(
-        protocols,
-        protover::Proto::Cons,
-        2,
-    );
+    let protocols: UnvalidatedProtoEntry = "Link=3-4 Cons=1".parse().unwrap();
+    let is_supported = protocols.supports_protocol(&protover::Protocol::Cons.into(), &2);
     assert_eq!(false, is_supported);
 }
 
 #[test]
 fn protover_string_supports_protocol_returns_false_for_unsupported() {
-    let protocols = "Link=3-4";
-    let is_supported = protover::protover_string_supports_protocol(
-        protocols,
-        protover::Proto::Cons,
-        2,
-    );
+    let protocols: UnvalidatedProtoEntry = "Link=3-4".parse().unwrap();
+    let is_supported = protocols.supports_protocol(&protover::Protocol::Cons.into(), &2);
     assert_eq!(false, is_supported);
 }
 
 #[test]
-fn protover_all_supported_with_unexpected_characters() {
-    let protocols = "Cons=*-%";
-    let (is_supported, unsupported) = protover::all_supported(protocols);
-    assert_eq!(false, is_supported);
-    assert_eq!("Cons=*-%", &unsupported);
+#[should_panic]
+fn parse_protocol_with_unexpected_characters() {
+    let _: UnvalidatedProtoEntry = "Cons=*-%".parse().unwrap();
 }
 
 #[test]
+#[should_panic]
 fn protover_compute_vote_returns_empty_for_empty_string() {
-    let protocols = vec![String::from("")];
-    let listed = protover::compute_vote(protocols, 1);
-    assert_eq!("", listed);
+    let protocols: &[UnvalidatedProtoEntry] = &["".parse().unwrap()];
+    let listed = ProtoverVote::compute(protocols, &1);
+    assert_eq!("", listed.to_string());
 }
 
 #[test]
 fn protover_compute_vote_returns_single_protocol_for_matching() {
-    let protocols = vec![String::from("Cons=1")];
-    let listed = protover::compute_vote(protocols, 1);
-    assert_eq!("Cons=1", listed);
+    let protocols: &[UnvalidatedProtoEntry] = &["Cons=1".parse().unwrap()];
+    let listed = ProtoverVote::compute(protocols, &1);
+    assert_eq!("Cons=1", listed.to_string());
 }
 
 #[test]
 fn protover_compute_vote_returns_two_protocols_for_two_matching() {
-    let protocols = vec![String::from("Link=1 Cons=1")];
-    let listed = protover::compute_vote(protocols, 1);
-    assert_eq!("Cons=1 Link=1", listed);
+    let protocols: &[UnvalidatedProtoEntry] = &["Link=1 Cons=1".parse().unwrap()];
+    let listed = ProtoverVote::compute(protocols, &1);
+    assert_eq!("Cons=1 Link=1", listed.to_string());
 }
 
 #[test]
 fn protover_compute_vote_returns_one_protocol_when_one_out_of_two_matches() {
-    let protocols = vec![String::from("Cons=1 Link=2"), String::from("Cons=1")];
-    let listed = protover::compute_vote(protocols, 2);
-    assert_eq!("Cons=1", listed);
+    let protocols: &[UnvalidatedProtoEntry] = &["Cons=1 Link=2".parse().unwrap(), "Cons=1".parse().unwrap()];
+    let listed = ProtoverVote::compute(protocols, &2);
+    assert_eq!("Cons=1", listed.to_string());
 }
 
 #[test]
 fn protover_compute_vote_returns_protocols_that_it_doesnt_currently_support() {
-    let protocols = vec![String::from("Foo=1 Cons=2"), String::from("Bar=1")];
-    let listed = protover::compute_vote(protocols, 1);
-    assert_eq!("Bar=1 Cons=2 Foo=1", listed);
+    let protocols: &[UnvalidatedProtoEntry] = &["Foo=1 Cons=2".parse().unwrap(), "Bar=1".parse().unwrap()];
+    let listed = ProtoverVote::compute(protocols, &1);
+    assert_eq!("Bar=1 Cons=2 Foo=1", listed.to_string());
 }
 
 #[test]
 fn protover_compute_vote_returns_matching_for_mix() {
-    let protocols = vec![String::from("Link=1-10,500 Cons=1,3-7,8")];
-    let listed = protover::compute_vote(protocols, 1);
-    assert_eq!("Cons=1,3-8 Link=1-10,500", listed);
+    let protocols: &[UnvalidatedProtoEntry] = &["Link=1-10,500 Cons=1,3-7,8".parse().unwrap()];
+    let listed = ProtoverVote::compute(protocols, &1);
+    assert_eq!("Cons=1,3-8 Link=1-10,500", listed.to_string());
 }
 
 #[test]
 fn protover_compute_vote_returns_matching_for_longer_mix() {
-    let protocols = vec![
-        String::from("Desc=1-10,500 Cons=1,3-7,8"),
-        String::from("Link=123-456,78 Cons=2-6,8 Desc=9"),
+    let protocols: &[UnvalidatedProtoEntry] = &[
+        "Desc=1-10,500 Cons=1,3-7,8".parse().unwrap(),
+        "Link=123-456,78 Cons=2-6,8 Desc=9".parse().unwrap(),
     ];
 
-    let listed = protover::compute_vote(protocols, 1);
-    assert_eq!("Cons=1-8 Desc=1-10,500 Link=78,123-456", listed);
+    let listed = ProtoverVote::compute(protocols, &1);
+    assert_eq!("Cons=1-8 Desc=1-10,500 Link=78,123-456", listed.to_string());
 }
 
 #[test]
 fn protover_compute_vote_returns_matching_for_longer_mix_with_threshold_two() {
-    let protocols = vec![
-        String::from("Desc=1-10,500 Cons=1,3-7,8"),
-        String::from("Link=123-456,78 Cons=2-6,8 Desc=9"),
+    let protocols: &[UnvalidatedProtoEntry] = &[
+        "Desc=1-10,500 Cons=1,3-7,8".parse().unwrap(),
+        "Link=123-456,78 Cons=2-6,8 Desc=9".parse().unwrap(),
     ];
 
-    let listed = protover::compute_vote(protocols, 2);
-    assert_eq!("Cons=3-6,8 Desc=9", listed);
+    let listed = ProtoverVote::compute(protocols, &2);
+    assert_eq!("Cons=3-6,8 Desc=9", listed.to_string());
 }
 
 #[test]
 fn protover_compute_vote_handles_duplicated_versions() {
-    let protocols = vec![String::from("Cons=1"), String::from("Cons=1")];
-    assert_eq!("Cons=1", protover::compute_vote(protocols, 2));
+    let protocols: &[UnvalidatedProtoEntry] = &["Cons=1".parse().unwrap(), "Cons=1".parse().unwrap()];
+    assert_eq!("Cons=1", ProtoverVote::compute(protocols, &2).to_string());
 
-    let protocols = vec![String::from("Cons=1-2"), String::from("Cons=1-2")];
-    assert_eq!("Cons=1-2", protover::compute_vote(protocols, 2));
+    let protocols: &[UnvalidatedProtoEntry] = &["Cons=1-2".parse().unwrap(), "Cons=1-2".parse().unwrap()];
+    assert_eq!("Cons=1-2", ProtoverVote::compute(protocols, &2).to_string());
 }
 
 #[test]
 fn protover_compute_vote_handles_invalid_proto_entries() {
-    let protocols = vec![
-        String::from("Cons=1"),
-        String::from("Cons=1"),
-        String::from("Link=a"),
+    let protocols: &[UnvalidatedProtoEntry] = &[
+        "Cons=1".parse().unwrap(),
+        "Cons=1".parse().unwrap(),
+        "Dinosaur=1".parse().unwrap(),
     ];
-    assert_eq!("Cons=1", protover::compute_vote(protocols, 2));
+    assert_eq!("Cons=1", ProtoverVote::compute(protocols, &2).to_string());
+}
 
-    let protocols = vec![
-        String::from("Cons=1"),
-        String::from("Cons=1"),
-        String::from("Link=1-%"),
-    ];
-    assert_eq!("Cons=1", protover::compute_vote(protocols, 2));
+#[test]
+fn parse_protocol_with_single_protocol_and_two_nonsequential_versions() {
+    let _: ProtoEntry = "Desc=1,2".parse().unwrap();
 }
 
 #[test]
 fn protover_is_supported_here_returns_true_for_supported_protocol() {
-    assert_eq!(true, protover::is_supported_here(protover::Proto::Cons, 1));
+    assert_eq!(true, protover::is_supported_here(&protover::Protocol::Cons, &1));
 }
 
 #[test]
 fn protover_is_supported_here_returns_false_for_unsupported_protocol() {
-    assert_eq!(false, protover::is_supported_here(protover::Proto::Cons, 5));
+    assert_eq!(false, protover::is_supported_here(&protover::Protocol::Cons, &5));
+}
+
+#[test]
+fn protocol_all_supported_with_single_proto_and_single_version() {
+    let protocol: UnvalidatedProtoEntry = "Cons=1".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocol.all_supported();
+    assert_eq!(true, unsupported.is_none());
+}
+
+#[test]
+fn protocol_all_supported_with_single_protocol_and_multiple_versions() {
+    let protocol: UnvalidatedProtoEntry = "Cons=1-2".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocol.all_supported();
+    assert_eq!(true, unsupported.is_none());
+}
+
+#[test]
+fn protocol_all_supported_with_different_single_protocol_and_single_version() {
+    let protocol: UnvalidatedProtoEntry = "HSDir=1".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocol.all_supported();
+    assert_eq!(true, unsupported.is_none());
+}
+
+#[test]
+fn protocol_all_supported_with_single_protocol_and_supported_version() {
+    let protocol: UnvalidatedProtoEntry = "Desc=2".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocol.all_supported();
+    assert_eq!(true, unsupported.is_none());
+}
+
+#[test]
+fn protocol_all_supported_with_two_protocols_and_single_version() {
+    let protocols: UnvalidatedProtoEntry = "Cons=1 HSDir=1".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocols.all_supported();
+    assert_eq!(true, unsupported.is_none());
+}
+
+#[test]
+fn protocol_all_supported_with_single_protocol_and_two_nonsequential_versions() {
+    let protocol: UnvalidatedProtoEntry = "Desc=1,2".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocol.all_supported();
+    assert_eq!(true, unsupported.is_none());
+}
+
+#[test]
+fn protocol_all_supported_with_single_protocol_and_two_sequential_versions() {
+    let protocol: UnvalidatedProtoEntry = "Desc=1-2".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocol.all_supported();
+    assert_eq!(true, unsupported.is_none());
+}
+
+#[test]
+fn protocol_all_supported_with_single_protocol_and_protocol_range() {
+    let protocol: UnvalidatedProtoEntry = "Link=1-4".parse().unwrap();
+    let unsupported: Option<UnvalidatedProtoEntry> = protocol.all_supported();
+    assert_eq!(true, unsupported.is_none());
+}
+
+// By allowing us to add to votes, the C implementation allows us to
+// exceed the limit.
+#[test]
+fn protover_compute_vote_may_exceed_limit() {
+    let proto1: UnvalidatedProtoEntry = "Sleen=1-65535".parse().unwrap();
+    let proto2: UnvalidatedProtoEntry = "Sleen=100000".parse().unwrap();
+
+    let _result: UnvalidatedProtoEntry = ProtoverVote::compute(&[proto1, proto2], &1);
+}
+
+#[test]
+fn protover_all_supported_should_exclude_versions_we_actually_do_support() {
+    let proto: UnvalidatedProtoEntry = "Link=3-999".parse().unwrap();
+    let result: String = proto.all_supported().unwrap().to_string();
+
+    assert_eq!(result, "Link=6-999".to_string());
+}
+
+#[test]
+fn protover_all_supported_should_exclude_versions_we_actually_do_support_complex1() {
+    let proto: UnvalidatedProtoEntry = "Link=1-3,345-666".parse().unwrap();
+    let result: String = proto.all_supported().unwrap().to_string();
+
+    assert_eq!(result, "Link=345-666".to_string());
+}
+
+#[test]
+fn protover_all_supported_should_exclude_versions_we_actually_do_support_complex2() {
+    let proto: UnvalidatedProtoEntry = "Link=1-3,5-12".parse().unwrap();
+    let result: String = proto.all_supported().unwrap().to_string();
+
+    assert_eq!(result, "Link=6-12".to_string());
+}
+
+#[test]
+fn protover_all_supported_should_exclude_some_versions_and_entire_protocols() {
+    let proto: UnvalidatedProtoEntry = "Link=1-3,5-12 Quokka=9000-9001".parse().unwrap();
+    let result: String = proto.all_supported().unwrap().to_string();
+
+    assert_eq!(result, "Link=6-12 Quokka=9000-9001".to_string());
+}
+
+#[test]
+fn protover_all_supported_should_not_dos_anyones_computer() {
+    let proto: UnvalidatedProtoEntry = "Sleen=0-2147483648".parse().unwrap();
+    let result: String = proto.all_supported().unwrap().to_string();
+
+    assert_eq!(result, "Sleen=0-2147483648".to_string());
+}
+
+#[test]
+fn protover_all_supported_should_not_dos_anyones_computer_max_versions() {
+    let proto: UnvalidatedProtoEntry = "Sleen=0-4294967294".parse().unwrap();
+    let result: String = proto.all_supported().unwrap().to_string();
+
+    assert_eq!(result, "Sleen=0-4294967294".to_string());
+}
+
+#[test]
+// C_RUST_DIFFERS: The C will return true (e.g. saying "yes, that's supported")
+// but set the msg to NULL (??? seems maybe potentially bad).  The Rust will
+// simply return a None.
+fn protover_all_supported_should_return_empty_string_for_weird_thing() {
+    let proto: UnvalidatedProtoEntry = "Fribble=".parse().unwrap();
+    let result: Option<UnvalidatedProtoEntry> = proto.all_supported();
+
+    assert!(result.is_none());
+}
+
+#[test]
+fn protover_unvalidatedprotoentry_should_err_entirely_unparseable_things() {
+    let proto: Result<UnvalidatedProtoEntry, ProtoverError> = "Fribble".parse();
+
+    assert_eq!(Err(ProtoverError::Unparseable), proto);
+}
+
+#[test]
+fn protover_all_supported_over_maximum_limit() {
+    let proto: Result<UnvalidatedProtoEntry, ProtoverError> = "Sleen=0-4294967295".parse();
+
+    assert_eq!(Err(ProtoverError::ExceedsMax), proto);
 }
diff --git a/src/test/test_protover.c b/src/test/test_protover.c
index c343e9957d..7bf1471ebd 100644
--- a/src/test/test_protover.c
+++ b/src/test/test_protover.c
@@ -254,11 +254,26 @@ test_protover_all_supported(void *arg)
   tt_assert(! protover_all_supported("Link=3-4 Wombat=9", &msg));
   tt_str_op(msg, OP_EQ, "Wombat=9");
   tor_free(msg);
+
+  /* Mix of things we support and don't support within a single protocol
+   * which we do support */
   tt_assert(! protover_all_supported("Link=3-999", &msg));
-  tt_str_op(msg, OP_EQ, "Link=3-999");
+  tt_str_op(msg, OP_EQ, "Link=6-999");
+  tor_free(msg);
+  tt_assert(! protover_all_supported("Link=1-3,345-666", &msg));
+  tt_str_op(msg, OP_EQ, "Link=345-666");
+  tor_free(msg);
+  tt_assert(! protover_all_supported("Link=1-3,5-12", &msg));
+  tt_str_op(msg, OP_EQ, "Link=6-12");
   tor_free(msg);
 
-  /* CPU/RAM DoS loop: Rust only */
+  /* Mix of protocols we do support and some we don't, where the protocols
+   * we do support have some versions we don't support. */
+  tt_assert(! protover_all_supported("Link=1-3,5-12 Quokka=9000-9001", &msg));
+  tt_str_op(msg, OP_EQ, "Link=6-12 Quokka=9000-9001");
+  tor_free(msg);
+
+  /* We shouldn't be able to DoS ourselves parsing a large range. */
   tt_assert(! protover_all_supported("Sleen=0-2147483648", &msg));
   tt_str_op(msg, OP_EQ, "Sleen=0-2147483648");
   tor_free(msg);
@@ -268,23 +283,22 @@ test_protover_all_supported(void *arg)
   tt_str_op(msg, OP_EQ, "Sleen=0-4294967294");
   tor_free(msg);
 
-  /* If we get an unparseable list, we say "yes, that's supported." */
-#ifndef HAVE_RUST
-  // XXXX let's make this section unconditional: rust should behave the
-  // XXXX same as C here!
+  /* If we get a (barely) valid (but unsupported list, we say "yes, that's
+   * supported." */
+  tt_assert(protover_all_supported("Fribble=", &msg));
+  tt_ptr_op(msg, OP_EQ, NULL);
+
+  /* If we get a completely unparseable list, protover_all_supported should
+   * hit a fatal assertion for BUG(entries == NULL). */
   tor_capture_bugs_(1);
   tt_assert(protover_all_supported("Fribble", &msg));
-  tt_ptr_op(msg, OP_EQ, NULL);
   tor_end_capture_bugs_();
 
-  /* This case is forbidden. Since it came from a protover_all_supported,
-   * it can trigger a bug message.  */
+  /* If we get a completely unparseable list, protover_all_supported should
+   * hit a fatal assertion for BUG(entries == NULL). */
   tor_capture_bugs_(1);
   tt_assert(protover_all_supported("Sleen=0-4294967295", &msg));
-  tt_ptr_op(msg, OP_EQ, NULL);
-  tor_free(msg);
   tor_end_capture_bugs_();
-#endif
 
  done:
   tor_end_capture_bugs_();
@@ -531,8 +545,6 @@ test_protover_vote_roundtrip(void *args)
     { "Link=1,9-8,3", NULL },
     { "Faux=-0", NULL },
     { "Faux=0--0", NULL },
-    // "These fail at the splitting stage in Rust, but the number parsing
-    // stage in C."
     { "Faux=-1", NULL },
     { "Faux=-1-3", NULL },
     { "Faux=1--1", NULL },
@@ -541,9 +553,9 @@ test_protover_vote_roundtrip(void *args)
     /* Large range */
     { "Sleen=1-501", "Sleen=1-501" },
     { "Sleen=1-65537", NULL },
-    /* CPU/RAM DoS Loop: Rust only. */
+    /* Both C/Rust implementations should be able to handle this mild DoS. */
     { "Sleen=0-2147483648", NULL },
-    /* Rust seems to experience an internal error here. */
+    /* Rust tests are built in debug mode, so ints are bounds-checked. */
     { "Sleen=0-4294967295", NULL },
   };
   unsigned u;