tor_protover/lib.rs
1#![cfg_attr(docsrs, feature(doc_auto_cfg, doc_cfg))]
2#![doc = include_str!("../README.md")]
3// @@ begin lint list maintained by maint/add_warning @@
4#![allow(renamed_and_removed_lints)] // @@REMOVE_WHEN(ci_arti_stable)
5#![allow(unknown_lints)] // @@REMOVE_WHEN(ci_arti_nightly)
6#![warn(missing_docs)]
7#![warn(noop_method_call)]
8#![warn(unreachable_pub)]
9#![warn(clippy::all)]
10#![deny(clippy::await_holding_lock)]
11#![deny(clippy::cargo_common_metadata)]
12#![deny(clippy::cast_lossless)]
13#![deny(clippy::checked_conversions)]
14#![warn(clippy::cognitive_complexity)]
15#![deny(clippy::debug_assert_with_mut_call)]
16#![deny(clippy::exhaustive_enums)]
17#![deny(clippy::exhaustive_structs)]
18#![deny(clippy::expl_impl_clone_on_copy)]
19#![deny(clippy::fallible_impl_from)]
20#![deny(clippy::implicit_clone)]
21#![deny(clippy::large_stack_arrays)]
22#![warn(clippy::manual_ok_or)]
23#![deny(clippy::missing_docs_in_private_items)]
24#![warn(clippy::needless_borrow)]
25#![warn(clippy::needless_pass_by_value)]
26#![warn(clippy::option_option)]
27#![deny(clippy::print_stderr)]
28#![deny(clippy::print_stdout)]
29#![warn(clippy::rc_buffer)]
30#![deny(clippy::ref_option_ref)]
31#![warn(clippy::semicolon_if_nothing_returned)]
32#![warn(clippy::trait_duplication_in_bounds)]
33#![deny(clippy::unchecked_duration_subtraction)]
34#![deny(clippy::unnecessary_wraps)]
35#![warn(clippy::unseparated_literal_suffix)]
36#![deny(clippy::unwrap_used)]
37#![deny(clippy::mod_module_files)]
38#![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness
39#![allow(clippy::uninlined_format_args)]
40#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945
41#![allow(clippy::result_large_err)] // temporary workaround for arti#587
42#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best
43#![allow(clippy::needless_lifetimes)] // See arti#1765
44//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
45
46#![allow(non_upper_case_globals)]
47#![allow(clippy::upper_case_acronyms)]
48
49use caret::caret_int;
50
51use thiserror::Error;
52
53pub mod named;
54
55caret_int! {
56 /// A recognized subprotocol.
57 ///
58 /// These names are kept in sync with the names used in consensus
59 /// documents; the values are kept in sync with the values in the
60 /// cbor document format in the walking onions proposal.
61 ///
62 /// For the full semantics of each subprotocol, see tor-spec.txt.
63 #[derive(Hash,Ord,PartialOrd)]
64 pub struct ProtoKind(u8) {
65 /// Initiating and receiving channels, and getting cells on them.
66 Link = 0,
67 /// Different kinds of authenticate cells
68 LinkAuth = 1,
69 /// CREATE cells, CREATED cells, and the encryption that they
70 /// create.
71 Relay = 2,
72 /// Serving and fetching network directory documents.
73 DirCache = 3,
74 /// Serving onion service descriptors
75 HSDir = 4,
76 /// Providing an onion service introduction point
77 HSIntro = 5,
78 /// Providing an onion service rendezvous point
79 HSRend = 6,
80 /// Describing a relay's functionality using router descriptors.
81 Desc = 7,
82 /// Describing a relay's functionality using microdescriptors.
83 Microdesc = 8,
84 /// Describing the network as a consensus directory document.
85 Cons = 9,
86 /// Sending and accepting circuit-level padding
87 Padding = 10,
88 /// Improved means of flow control on circuits.
89 FlowCtrl = 11,
90 /// Multi-path circuit support.
91 Conflux = 12,
92 }
93}
94
95/// How many recognized protocols are there?
96const N_RECOGNIZED: usize = 13;
97
98/// Maximum allowable value for a protocol's version field.
99const MAX_VER: usize = 63;
100
101/// A specific, named subversion of a protocol.
102#[derive(Eq, PartialEq, Copy, Clone, Debug)]
103pub struct NamedSubver {
104 /// The protocol in question
105 ///
106 /// Must be in-range for ProtoKind (0..N_RECOGNIZED).
107 kind: ProtoKind,
108 /// The version of the protocol
109 ///
110 /// Must be in 0..=MAX_VER
111 version: u8,
112}
113
114impl NamedSubver {
115 /// Create a new NamedSubver.
116 ///
117 /// # Panics
118 ///
119 /// Panics if `kind` is unrecognized or `version` is invalid.
120 const fn new(kind: ProtoKind, version: u8) -> Self {
121 assert!((kind.0 as usize) < N_RECOGNIZED);
122 assert!((version as usize) <= MAX_VER);
123 Self { kind, version }
124 }
125}
126
127/// A subprotocol capability as represented by a (kind, version) tuple.
128///
129/// Does not necessarily represent a real subprotocol capability;
130/// this type is meant for use in other pieces of the protocol.
131///
132/// # Ordering
133///
134/// Instances of `NumberedSubver` are sorted in lexicographic order by
135/// their (kind, version) tuples.
136//
137// TODO: As with most other types in the crate, we should decide how to rename them as as part
138// of #1934.
139#[derive(Clone, Copy, Debug, Ord, PartialOrd, Eq, PartialEq)]
140pub struct NumberedSubver {
141 /// The protocol in question
142 kind: ProtoKind,
143 /// The version of the protocol
144 version: u8,
145}
146
147impl NumberedSubver {
148 /// Construct a new [`NumberedSubver`]
149 pub fn new(kind: impl Into<ProtoKind>, version: u8) -> Self {
150 Self {
151 kind: kind.into(),
152 version,
153 }
154 }
155 /// Return the ProtoKind and version for this [`NumberedSubver`].
156 pub fn into_parts(self) -> (ProtoKind, u8) {
157 (self.kind, self.version)
158 }
159}
160impl From<NamedSubver> for NumberedSubver {
161 fn from(value: NamedSubver) -> Self {
162 Self {
163 kind: value.kind,
164 version: value.version,
165 }
166 }
167}
168
169#[cfg(feature = "tor-bytes")]
170impl tor_bytes::Readable for NumberedSubver {
171 fn take_from(b: &mut tor_bytes::Reader<'_>) -> tor_bytes::Result<Self> {
172 let kind = b.take_u8()?;
173 let version = b.take_u8()?;
174 Ok(Self::new(kind, version))
175 }
176}
177
178#[cfg(feature = "tor-bytes")]
179impl tor_bytes::Writeable for NumberedSubver {
180 fn write_onto<B: tor_bytes::Writer + ?Sized>(&self, b: &mut B) -> tor_bytes::EncodeResult<()> {
181 b.write_u8(self.kind.into());
182 b.write_u8(self.version);
183 Ok(())
184 }
185}
186
187/// Representation for a known or unknown protocol.
188#[derive(Eq, PartialEq, Clone, Debug, Hash, Ord, PartialOrd)]
189enum Protocol {
190 /// A known protocol; represented by one of ProtoKind.
191 ///
192 /// ProtoKind must always be in the range 0..N_RECOGNIZED.
193 Proto(ProtoKind),
194 /// An unknown protocol; represented by its name.
195 Unrecognized(String),
196}
197
198impl Protocol {
199 /// Return true iff `s` is the name of a protocol we do not recognize.
200 fn is_unrecognized(&self, s: &str) -> bool {
201 match self {
202 Protocol::Unrecognized(s2) => s2 == s,
203 _ => false,
204 }
205 }
206 /// Return a string representation of this protocol.
207 fn to_str(&self) -> &str {
208 match self {
209 Protocol::Proto(k) => k.to_str().unwrap_or("<bug>"),
210 Protocol::Unrecognized(s) => s,
211 }
212 }
213}
214
215/// Representation of a set of versions supported by a protocol.
216///
217/// For now, we only use this type for unrecognized protocols.
218#[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
219struct SubprotocolEntry {
220 /// Which protocol's versions does this describe?
221 proto: Protocol,
222 /// A bit-vector defining which versions are supported. If bit
223 /// `(1<<i)` is set, then protocol version `i` is supported.
224 supported: u64,
225}
226
227/// A set of supported or required subprotocol versions.
228///
229/// This type supports both recognized subprotocols (listed in ProtoKind),
230/// and unrecognized subprotocols (stored by name).
231///
232/// To construct an instance, use the FromStr trait:
233/// ```
234/// use tor_protover::Protocols;
235/// let p: Result<Protocols,_> = "Link=1-3 LinkAuth=2-3 Relay=1-2".parse();
236/// ```
237#[derive(Debug, Clone, Default, Eq, PartialEq, Hash)]
238#[cfg_attr(
239 feature = "serde",
240 derive(serde_with::DeserializeFromStr, serde_with::SerializeDisplay)
241)]
242pub struct Protocols {
243 /// A mapping from protocols' integer encodings to bit-vectors.
244 recognized: [u64; N_RECOGNIZED],
245 /// A vector of unrecognized protocol versions,
246 /// in sorted order.
247 ///
248 /// Every entry in this list has supported != 0.
249 unrecognized: Vec<SubprotocolEntry>,
250}
251
252impl Protocols {
253 /// Return a new empty set of protocol versions.
254 pub fn new() -> Self {
255 Protocols::default()
256 }
257 /// Helper: return true iff this protocol set contains the
258 /// version `ver` of the protocol represented by the integer `proto`.
259 fn supports_recognized_ver(&self, proto: usize, ver: u8) -> bool {
260 if usize::from(ver) > MAX_VER {
261 return false;
262 }
263 if proto >= self.recognized.len() {
264 return false;
265 }
266 (self.recognized[proto] & (1 << ver)) != 0
267 }
268 /// Helper: return true iff this protocol set contains version
269 /// `ver` of the unrecognized protocol represented by the string
270 /// `proto`.
271 ///
272 /// Requires that `proto` is not the name of a recognized protocol.
273 fn supports_unrecognized_ver(&self, proto: &str, ver: u8) -> bool {
274 if usize::from(ver) > MAX_VER {
275 return false;
276 }
277 let ent = self
278 .unrecognized
279 .iter()
280 .find(|ent| ent.proto.is_unrecognized(proto));
281 match ent {
282 Some(e) => (e.supported & (1 << ver)) != 0,
283 None => false,
284 }
285 }
286
287 /// Return true if this list of protocols is empty.
288 pub fn is_empty(&self) -> bool {
289 self.recognized.iter().all(|v| *v == 0)
290 && self.unrecognized.iter().all(|p| p.supported == 0)
291 }
292
293 // TODO: Combine these next two functions into one by using a trait.
294 /// Check whether a known protocol version is supported.
295 ///
296 /// ```
297 /// use tor_protover::*;
298 /// let protos: Protocols = "Link=1-3 HSDir=2,4-5".parse().unwrap();
299 ///
300 /// assert!(protos.supports_known_subver(ProtoKind::Link, 2));
301 /// assert!(protos.supports_known_subver(ProtoKind::HSDir, 4));
302 /// assert!(! protos.supports_known_subver(ProtoKind::HSDir, 3));
303 /// assert!(! protos.supports_known_subver(ProtoKind::LinkAuth, 3));
304 /// ```
305 pub fn supports_known_subver(&self, proto: ProtoKind, ver: u8) -> bool {
306 self.supports_recognized_ver(proto.get() as usize, ver)
307 }
308 /// Check whether a protocol version identified by a string is supported.
309 ///
310 /// ```
311 /// use tor_protover::*;
312 /// let protos: Protocols = "Link=1-3 Foobar=7".parse().unwrap();
313 ///
314 /// assert!(protos.supports_subver("Link", 2));
315 /// assert!(protos.supports_subver("Foobar", 7));
316 /// assert!(! protos.supports_subver("Link", 5));
317 /// assert!(! protos.supports_subver("Foobar", 6));
318 /// assert!(! protos.supports_subver("Wombat", 3));
319 /// ```
320 pub fn supports_subver(&self, proto: &str, ver: u8) -> bool {
321 match ProtoKind::from_name(proto) {
322 Some(p) => self.supports_recognized_ver(p.get() as usize, ver),
323 None => self.supports_unrecognized_ver(proto, ver),
324 }
325 }
326
327 /// Check whether a protocol version is supported.
328 ///
329 /// ```
330 /// use tor_protover::*;
331 /// let protos: Protocols = "Link=1-5 Desc=2-4".parse().unwrap();
332 /// assert!(protos.supports_named_subver(named::DESC_FAMILY_IDS)); // Desc=4
333 /// assert!(! protos.supports_named_subver(named::CONFLUX_BASE)); // Conflux=1
334 /// ```
335 pub fn supports_named_subver(&self, protover: NamedSubver) -> bool {
336 self.supports_known_subver(protover.kind, protover.version)
337 }
338
339 /// Check whether a numbered subprotocol capability is supported.
340 ///
341 /// ```
342 /// use tor_protover::*;
343 /// let protos: Protocols = "Link=1-5 Desc=2-4".parse().unwrap();
344 /// assert!(protos.supports_numbered_subver(NumberedSubver::new(ProtoKind::Desc, 4)));
345 /// assert!(! protos.supports_numbered_subver(NumberedSubver::new(ProtoKind::Conflux, 1)));
346 /// ```
347 pub fn supports_numbered_subver(&self, protover: NumberedSubver) -> bool {
348 self.supports_known_subver(protover.kind, protover.version)
349 }
350
351 /// Return a Protocols holding every protocol flag that is present in `self`
352 /// but not `other`.
353 ///
354 /// ```
355 /// use tor_protover::*;
356 /// let protos: Protocols = "Desc=2-4 Microdesc=1-5".parse().unwrap();
357 /// let protos2: Protocols = "Desc=3 Microdesc=3".parse().unwrap();
358 /// assert_eq!(protos.difference(&protos2),
359 /// "Desc=2,4 Microdesc=1-2,4-5".parse().unwrap());
360 /// ```
361 pub fn difference(&self, other: &Protocols) -> Protocols {
362 let mut r = Protocols::default();
363
364 for i in 0..N_RECOGNIZED {
365 r.recognized[i] = self.recognized[i] & !other.recognized[i];
366 }
367 // This is not super efficient, but we don't have to do it often.
368 for ent in self.unrecognized.iter() {
369 let mut ent = ent.clone();
370 if let Some(other_ent) = other.unrecognized.iter().find(|e| e.proto == ent.proto) {
371 ent.supported &= !other_ent.supported;
372 }
373 if ent.supported != 0 {
374 r.unrecognized.push(ent);
375 }
376 }
377 r
378 }
379
380 /// Return a Protocols holding every protocol flag that is present in `self`
381 /// or `other` or both.
382 ///
383 /// ```
384 /// use tor_protover::*;
385 /// let protos: Protocols = "Desc=2-4 Microdesc=1-5".parse().unwrap();
386 /// let protos2: Protocols = "Desc=3 Microdesc=10".parse().unwrap();
387 /// assert_eq!(protos.union(&protos2),
388 /// "Desc=2-4 Microdesc=1-5,10".parse().unwrap());
389 /// ```
390 pub fn union(&self, other: &Protocols) -> Protocols {
391 let mut r = self.clone();
392 for i in 0..N_RECOGNIZED {
393 r.recognized[i] |= other.recognized[i];
394 }
395 for ent in other.unrecognized.iter() {
396 if let Some(my_ent) = r.unrecognized.iter_mut().find(|e| e.proto == ent.proto) {
397 my_ent.supported |= ent.supported;
398 } else {
399 r.unrecognized.push(ent.clone());
400 }
401 }
402 r.unrecognized.sort();
403 r
404 }
405
406 /// Return a Protocols holding every protocol flag that is present in both `self`
407 /// and `other`.
408 ///
409 /// ```
410 /// use tor_protover::*;
411 /// let protos: Protocols = "Desc=2-4 Microdesc=1-5".parse().unwrap();
412 /// let protos2: Protocols = "Desc=3 Microdesc=10".parse().unwrap();
413 /// assert_eq!(protos.intersection(&protos2),
414 /// "Desc=3".parse().unwrap());
415 /// ```
416 pub fn intersection(&self, other: &Protocols) -> Protocols {
417 let mut r = Protocols::default();
418 for i in 0..N_RECOGNIZED {
419 r.recognized[i] = self.recognized[i] & other.recognized[i];
420 }
421 for ent in self.unrecognized.iter() {
422 if let Some(other_ent) = other.unrecognized.iter().find(|e| e.proto == ent.proto) {
423 let supported = ent.supported & other_ent.supported;
424 if supported != 0 {
425 r.unrecognized.push(SubprotocolEntry {
426 proto: ent.proto.clone(),
427 supported,
428 });
429 }
430 }
431 }
432 r.unrecognized.sort();
433 r
434 }
435
436 /// Parsing helper: Try to add a new entry `ent` to this set of protocols.
437 ///
438 /// Uses `foundmask`, a bit mask saying which recognized protocols
439 /// we've already found entries for. Returns an error if `ent` is
440 /// for a protocol we've already added.
441 ///
442 /// Does not preserve sorting order; the caller must call `self.unrecognized.sort()` before returning.
443 fn add(&mut self, foundmask: &mut u64, ent: SubprotocolEntry) -> Result<(), ParseError> {
444 match ent.proto {
445 Protocol::Proto(k) => {
446 let idx = k.get() as usize;
447 assert!(idx < N_RECOGNIZED); // guaranteed by invariant on Protocol::Proto
448 let bit = 1 << u64::from(k.get());
449 if (*foundmask & bit) != 0 {
450 return Err(ParseError::Duplicate);
451 }
452 *foundmask |= bit;
453 self.recognized[idx] = ent.supported;
454 }
455 Protocol::Unrecognized(ref s) => {
456 if self
457 .unrecognized
458 .iter()
459 .any(|ent| ent.proto.is_unrecognized(s))
460 {
461 return Err(ParseError::Duplicate);
462 }
463 if ent.supported != 0 {
464 self.unrecognized.push(ent);
465 }
466 }
467 }
468 Ok(())
469 }
470}
471
472/// An error representing a failure to parse a set of protocol versions.
473#[derive(Error, Debug, PartialEq, Eq, Clone)]
474#[non_exhaustive]
475pub enum ParseError {
476 /// A protocol version was not in the range 0..=63.
477 #[error("Protocol version out of range")]
478 OutOfRange,
479 /// Some subprotocol or protocol version appeared more than once.
480 #[error("Duplicate protocol entry")]
481 Duplicate,
482 /// The list of protocol versions was malformed in some other way.
483 #[error("Malformed protocol entry")]
484 Malformed,
485}
486
487/// Helper: return a new u64 in which bits `lo` through `hi` inclusive
488/// are set to 1, and all the other bits are set to 0.
489///
490/// In other words, `bitrange(a,b)` is how we represent the range of
491/// versions `a-b` in a protocol version bitmask.
492///
493/// ```ignore
494/// # use tor_protover::bitrange;
495/// assert_eq!(bitrange(0, 5), 0b111111);
496/// assert_eq!(bitrange(2, 5), 0b111100);
497/// assert_eq!(bitrange(2, 7), 0b11111100);
498/// ```
499fn bitrange(lo: u64, hi: u64) -> u64 {
500 assert!(lo <= hi && lo <= 63 && hi <= 63);
501 let mut mask = !0;
502 mask <<= 63 - hi;
503 mask >>= 63 - hi + lo;
504 mask <<= lo;
505 mask
506}
507
508/// Helper: return true if the provided string is a valid "integer"
509/// in the form accepted by the protover spec. This is stricter than
510/// rust's integer parsing format.
511fn is_good_number(n: &str) -> bool {
512 n.chars().all(|ch| ch.is_ascii_digit()) && !n.starts_with('0')
513}
514
515/// A single SubprotocolEntry is parsed from a string of the format
516/// Name=Versions, where Versions is a comma-separated list of
517/// integers or ranges of integers.
518impl std::str::FromStr for SubprotocolEntry {
519 type Err = ParseError;
520
521 fn from_str(s: &str) -> Result<Self, ParseError> {
522 // split the string on the =.
523 let (name, versions) = {
524 let eq_idx = s.find('=').ok_or(ParseError::Malformed)?;
525 (&s[..eq_idx], &s[eq_idx + 1..])
526 };
527 // Look up the protocol by name.
528 let proto = match ProtoKind::from_name(name) {
529 Some(p) => Protocol::Proto(p),
530 None => Protocol::Unrecognized(name.to_string()),
531 };
532 if versions.is_empty() {
533 // We need to handle this case specially, since otherwise
534 // it would be treated below as a single empty value, which
535 // would be rejected.
536 return Ok(SubprotocolEntry {
537 proto,
538 supported: 0,
539 });
540 }
541 // Construct a bitmask based on the comma-separated versions.
542 let mut supported = 0_u64;
543 for ent in versions.split(',') {
544 // Find and parse lo and hi for a single range of versions.
545 // (If this is not a range, but rather a single version v,
546 // treat it as if it were a range v-v.)
547 let (lo_s, hi_s) = {
548 match ent.find('-') {
549 Some(pos) => (&ent[..pos], &ent[pos + 1..]),
550 None => (ent, ent),
551 }
552 };
553 if !is_good_number(lo_s) {
554 return Err(ParseError::Malformed);
555 }
556 if !is_good_number(hi_s) {
557 return Err(ParseError::Malformed);
558 }
559 let lo: u64 = lo_s.parse().map_err(|_| ParseError::Malformed)?;
560 let hi: u64 = hi_s.parse().map_err(|_| ParseError::Malformed)?;
561 // Make sure that lo and hi are in-bounds and consistent.
562 if lo > (MAX_VER as u64) || hi > (MAX_VER as u64) {
563 return Err(ParseError::OutOfRange);
564 }
565 if lo > hi {
566 return Err(ParseError::Malformed);
567 }
568 let mask = bitrange(lo, hi);
569 // Make sure that no version is included twice.
570 if (supported & mask) != 0 {
571 return Err(ParseError::Duplicate);
572 }
573 // Add the appropriate bits to the mask.
574 supported |= mask;
575 }
576 Ok(SubprotocolEntry { proto, supported })
577 }
578}
579
580/// A Protocols set can be parsed from a string according to the
581/// format used in Tor consensus documents.
582///
583/// A protocols set is represented by a space-separated list of
584/// entries. Each entry is of the form `Name=Versions`, where `Name`
585/// is the name of a protocol, and `Versions` is a comma-separated
586/// list of version numbers and version ranges. Each version range is
587/// a pair of integers separated by `-`.
588///
589/// No protocol name may be listed twice. No version may be listed
590/// twice for a single protocol. All versions must be in range 0
591/// through 63 inclusive.
592impl std::str::FromStr for Protocols {
593 type Err = ParseError;
594
595 fn from_str(s: &str) -> Result<Self, ParseError> {
596 let mut result = Protocols::new();
597 let mut foundmask = 0_u64;
598 for ent in s.split(' ') {
599 if ent.is_empty() {
600 continue;
601 }
602
603 let s: SubprotocolEntry = ent.parse()?;
604 result.add(&mut foundmask, s)?;
605 }
606 result.unrecognized.sort();
607 Ok(result)
608 }
609}
610
611/// Given a bitmask, return a list of the bits set in the mask, as a
612/// String in the format expected by Tor consensus documents.
613///
614/// This implementation constructs ranges greedily. For example, the
615/// bitmask `0b0111011` will be represented as `0-1,3-5`, and not
616/// `0,1,3,4,5` or `0,1,3-5`.
617///
618/// ```ignore
619/// # use tor_protover::dumpmask;
620/// assert_eq!(dumpmask(0b111111), "0-5");
621/// assert_eq!(dumpmask(0b111100), "2-5");
622/// assert_eq!(dumpmask(0b11111100), "2-7");
623/// ```
624fn dumpmask(mut mask: u64) -> String {
625 /// Helper: push a range (which may be a singleton) onto `v`.
626 fn append(v: &mut Vec<String>, lo: u32, hi: u32) {
627 if lo == hi {
628 v.push(lo.to_string());
629 } else {
630 v.push(format!("{}-{}", lo, hi));
631 }
632 }
633 // We'll be building up our result here, then joining it with
634 // commas.
635 let mut result = Vec::new();
636 // This implementation is a little tricky, but it should be more
637 // efficient than a raw search. Basically, we're using the
638 // function u64::trailing_zeros to count how large each range of
639 // 1s or 0s is, and then shifting by that amount.
640
641 // How many bits have we already shifted `mask`?
642 let mut shift = 0;
643 while mask != 0 {
644 let zeros = mask.trailing_zeros();
645 mask >>= zeros;
646 shift += zeros;
647 let ones = mask.trailing_ones();
648 append(&mut result, shift, shift + ones - 1);
649 shift += ones;
650 if ones == 64 {
651 // We have to do this check to avoid overflow when formatting
652 // the range `0-63`.
653 break;
654 }
655 mask >>= ones;
656 }
657 result.join(",")
658}
659
660/// The Display trait formats a protocol set in the format expected by Tor
661/// consensus documents.
662///
663/// ```
664/// use tor_protover::*;
665/// let protos: Protocols = "Link=1,2,3 Foobar=7 Relay=2".parse().unwrap();
666/// assert_eq!(format!("{}", protos),
667/// "Foobar=7 Link=1-3 Relay=2");
668/// ```
669impl std::fmt::Display for Protocols {
670 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
671 let mut entries = Vec::new();
672 for (idx, mask) in self.recognized.iter().enumerate() {
673 if *mask != 0 {
674 let pk: ProtoKind = (idx as u8).into();
675 entries.push(format!("{}={}", pk, dumpmask(*mask)));
676 }
677 }
678 for ent in &self.unrecognized {
679 if ent.supported != 0 {
680 entries.push(format!(
681 "{}={}",
682 ent.proto.to_str(),
683 dumpmask(ent.supported)
684 ));
685 }
686 }
687 // This sort is required.
688 entries.sort();
689 write!(f, "{}", entries.join(" "))
690 }
691}
692
693impl FromIterator<NamedSubver> for Protocols {
694 fn from_iter<T: IntoIterator<Item = NamedSubver>>(iter: T) -> Self {
695 let mut r = Protocols::new();
696 for named_subver in iter {
697 let proto_idx = usize::from(named_subver.kind.get());
698 let proto_ver = named_subver.version;
699
700 // These are guaranteed by invariants on NamedSubver.
701 assert!(proto_idx < N_RECOGNIZED);
702 assert!(usize::from(proto_ver) <= MAX_VER);
703 r.recognized[proto_idx] |= 1_u64 << proto_ver;
704 }
705 r
706 }
707}
708
709/// Documentation: when is a protocol "supported"?
710///
711/// Arti should consider itself to "support" a protocol if, _as built_,
712/// it implements the protocol completely.
713///
714/// Just having the protocol listed among the [`named`]
715/// protocols is not enough, and neither is an incomplete
716/// or uncompliant implementation.
717///
718/// Similarly, if the protocol is not compiled in,
719/// it is not technically _supported_.
720///
721/// When in doubt, ask yourself:
722/// - If another Tor implementation believed that we implemented this protocol,
723/// and began to speak it to us, would we be able to do so?
724/// - If the protocol were required,
725/// would this software as built actually meet that requirement?
726///
727/// If either answer is no, the protocol is not supported.
728pub mod doc_supported {}
729
730/// Documentation about changing lists of supported versions.
731///
732/// # Warning
733///
734/// You need to be extremely careful when removing
735/// _any_ entry from a list of supported protocols.
736///
737/// If you remove an entry while it still appears as "recommended" in the consensus,
738/// you'll cause all the instances without it to warn.
739///
740/// If you remove an entry while it still appears as "required" in the
741/// consensus, you'll cause all the instances without it to refuse to connect
742/// to the network, and shut down.
743///
744/// If you need to remove a version from a list of supported protocols,
745/// you need to make sure that it is not listed in the _current consensuses_:
746/// just removing it from the list that the authorities vote for is NOT ENOUGH.
747/// You need to remove it from the required list,
748/// and THEN let the authorities upgrade and vote on new
749/// consensuses without it. Only once those consensuses are out is it safe to
750/// remove from the list of required protocols.
751///
752/// ## Example
753///
754/// One concrete example of a very dangerous race that could occur:
755///
756/// Suppose that the client supports protocols "HsDir=1-2" and the consensus
757/// requires protocols "HsDir=1-2. If the client supported protocol list is
758/// then changed to "HSDir=2", while the consensus stills lists "HSDir=1-2",
759/// then these clients, even very recent ones, will shut down because they
760/// don't support "HSDir=1".
761///
762/// And so, changes need to be done in strict sequence as described above.
763pub mod doc_changing {}
764
765#[cfg(test)]
766mod test {
767 // @@ begin test lint list maintained by maint/add_warning @@
768 #![allow(clippy::bool_assert_comparison)]
769 #![allow(clippy::clone_on_copy)]
770 #![allow(clippy::dbg_macro)]
771 #![allow(clippy::mixed_attributes_style)]
772 #![allow(clippy::print_stderr)]
773 #![allow(clippy::print_stdout)]
774 #![allow(clippy::single_char_pattern)]
775 #![allow(clippy::unwrap_used)]
776 #![allow(clippy::unchecked_duration_subtraction)]
777 #![allow(clippy::useless_vec)]
778 #![allow(clippy::needless_pass_by_value)]
779 //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
780 use std::str::FromStr;
781
782 use super::*;
783
784 #[test]
785 fn test_bitrange() {
786 assert_eq!(0b1, bitrange(0, 0));
787 assert_eq!(0b10, bitrange(1, 1));
788 assert_eq!(0b11, bitrange(0, 1));
789 assert_eq!(0b1111110000000, bitrange(7, 12));
790 assert_eq!(!0, bitrange(0, 63));
791 }
792
793 #[test]
794 fn test_dumpmask() {
795 assert_eq!("", dumpmask(0));
796 assert_eq!("0-5", dumpmask(0b111111));
797 assert_eq!("4-5", dumpmask(0b110000));
798 assert_eq!("1,4-5", dumpmask(0b110010));
799 assert_eq!("0-63", dumpmask(!0));
800 }
801
802 #[test]
803 fn test_canonical() -> Result<(), ParseError> {
804 fn t(orig: &str, canonical: &str) -> Result<(), ParseError> {
805 let protos: Protocols = orig.parse()?;
806 let enc = format!("{}", protos);
807 assert_eq!(enc, canonical);
808 Ok(())
809 }
810
811 t("", "")?;
812 t(" ", "")?;
813 t("Link=5,6,7,9 Relay=4-7,2", "Link=5-7,9 Relay=2,4-7")?;
814 t("FlowCtrl= Padding=8,7 Desc=1-5,6-8", "Desc=1-8 Padding=7-8")?;
815 t("Zelda=7 Gannon=3,6 Link=4", "Gannon=3,6 Link=4 Zelda=7")?;
816
817 Ok(())
818 }
819
820 #[test]
821 fn test_invalid() {
822 fn t(s: &str) -> ParseError {
823 let protos: Result<Protocols, ParseError> = s.parse();
824 assert!(protos.is_err());
825 protos.err().unwrap()
826 }
827
828 assert_eq!(t("Link=1-100"), ParseError::OutOfRange);
829 assert_eq!(t("Zelda=100"), ParseError::OutOfRange);
830 assert_eq!(t("Link=100-200"), ParseError::OutOfRange);
831
832 assert_eq!(t("Link=1,1"), ParseError::Duplicate);
833 assert_eq!(t("Link=1 Link=1"), ParseError::Duplicate);
834 assert_eq!(t("Link=1 Link=3"), ParseError::Duplicate);
835 assert_eq!(t("Zelda=1 Zelda=3"), ParseError::Duplicate);
836
837 assert_eq!(t("Link=Zelda"), ParseError::Malformed);
838 assert_eq!(t("Link=6-2"), ParseError::Malformed);
839 assert_eq!(t("Link=6-"), ParseError::Malformed);
840 assert_eq!(t("Link=6-,2"), ParseError::Malformed);
841 assert_eq!(t("Link=1,,2"), ParseError::Malformed);
842 assert_eq!(t("Link=6-frog"), ParseError::Malformed);
843 assert_eq!(t("Link=gannon-9"), ParseError::Malformed);
844 assert_eq!(t("Link Zelda"), ParseError::Malformed);
845
846 assert_eq!(t("Link=01"), ParseError::Malformed);
847 assert_eq!(t("Link=waffle"), ParseError::Malformed);
848 assert_eq!(t("Link=1_1"), ParseError::Malformed);
849 }
850
851 #[test]
852 fn test_supports() -> Result<(), ParseError> {
853 let p: Protocols = "Link=4,5-7 Padding=2 Lonk=1-3,5".parse()?;
854
855 assert!(p.supports_known_subver(ProtoKind::Padding, 2));
856 assert!(!p.supports_known_subver(ProtoKind::Padding, 1));
857 assert!(p.supports_known_subver(ProtoKind::Link, 6));
858 assert!(!p.supports_known_subver(ProtoKind::Link, 255));
859 assert!(!p.supports_known_subver(ProtoKind::Cons, 1));
860 assert!(!p.supports_known_subver(ProtoKind::Cons, 0));
861 assert!(p.supports_subver("Link", 6));
862 assert!(!p.supports_subver("link", 6));
863 assert!(!p.supports_subver("Cons", 0));
864 assert!(p.supports_subver("Lonk", 3));
865 assert!(!p.supports_subver("Lonk", 4));
866 assert!(!p.supports_subver("lonk", 3));
867 assert!(!p.supports_subver("Lonk", 64));
868
869 Ok(())
870 }
871
872 #[test]
873 fn test_difference() -> Result<(), ParseError> {
874 let p1: Protocols = "Link=1-10 Desc=5-10 Relay=1,3,5,7,9 Other=7-60 Mine=1-20".parse()?;
875 let p2: Protocols = "Link=3-4 Desc=1-6 Relay=2-6 Other=8 Theirs=20".parse()?;
876
877 assert_eq!(
878 p1.difference(&p2),
879 Protocols::from_str("Link=1-2,5-10 Desc=7-10 Relay=1,7,9 Other=7,9-60 Mine=1-20")?
880 );
881 assert_eq!(
882 p2.difference(&p1),
883 Protocols::from_str("Desc=1-4 Relay=2,4,6 Theirs=20")?,
884 );
885
886 let nil = Protocols::default();
887 assert_eq!(p1.difference(&nil), p1);
888 assert_eq!(p2.difference(&nil), p2);
889 assert_eq!(nil.difference(&p1), nil);
890 assert_eq!(nil.difference(&p2), nil);
891
892 Ok(())
893 }
894
895 #[test]
896 fn test_union() -> Result<(), ParseError> {
897 let p1: Protocols = "Link=1-10 Desc=5-10 Relay=1,3,5,7,9 Other=7-60 Mine=1-20".parse()?;
898 let p2: Protocols = "Link=3-4 Desc=1-6 Relay=2-6 Other=2,8 Theirs=20".parse()?;
899
900 assert_eq!(
901 p1.union(&p2),
902 Protocols::from_str(
903 "Link=1-10 Desc=1-10 Relay=1-7,9 Other=2,7-60 Theirs=20 Mine=1-20"
904 )?
905 );
906 assert_eq!(
907 p2.union(&p1),
908 Protocols::from_str(
909 "Link=1-10 Desc=1-10 Relay=1-7,9 Other=2,7-60 Theirs=20 Mine=1-20"
910 )?
911 );
912
913 let nil = Protocols::default();
914 assert_eq!(p1.union(&nil), p1);
915 assert_eq!(p2.union(&nil), p2);
916 assert_eq!(nil.union(&p1), p1);
917 assert_eq!(nil.union(&p2), p2);
918
919 Ok(())
920 }
921
922 #[test]
923 fn test_intersection() -> Result<(), ParseError> {
924 let p1: Protocols = "Link=1-10 Desc=5-10 Relay=1,3,5,7,9 Other=7-60 Mine=1-20".parse()?;
925 let p2: Protocols = "Link=3-4 Desc=1-6 Relay=2-6 Other=2,8 Theirs=20".parse()?;
926
927 assert_eq!(
928 p1.intersection(&p2),
929 Protocols::from_str("Link=3-4 Desc=5-6 Relay=3,5 Other=8")?
930 );
931 assert_eq!(
932 p2.intersection(&p1),
933 Protocols::from_str("Link=3-4 Desc=5-6 Relay=3,5 Other=8")?
934 );
935
936 let nil = Protocols::default();
937 assert_eq!(p1.intersection(&nil), nil);
938 assert_eq!(p2.intersection(&nil), nil);
939 assert_eq!(nil.intersection(&p1), nil);
940 assert_eq!(nil.intersection(&p2), nil);
941
942 Ok(())
943 }
944
945 #[test]
946 fn from_iter() {
947 use named as n;
948 let empty: [NamedSubver; 0] = [];
949 let prs: Protocols = empty.iter().copied().collect();
950 assert_eq!(prs, Protocols::default());
951 let prs: Protocols = empty.into_iter().collect();
952 assert_eq!(prs, Protocols::default());
953
954 let prs = [
955 n::LINK_V3,
956 n::HSDIR_V3,
957 n::LINK_V4,
958 n::LINK_V5,
959 n::CONFLUX_BASE,
960 ]
961 .into_iter()
962 .collect::<Protocols>();
963 assert_eq!(prs, "Link=3-5 HSDir=2 Conflux=1".parse().unwrap());
964 }
965
966 #[test]
967 fn order_numbered_subvers() {
968 // We rely on this sort order elsewhere in our protocol.
969 assert!(NumberedSubver::new(5, 7) < NumberedSubver::new(7, 5));
970 assert!(NumberedSubver::new(7, 5) < NumberedSubver::new(7, 6));
971 assert!(NumberedSubver::new(7, 6) < NumberedSubver::new(8, 6));
972 }
973}