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
#![allow(mismatched_lifetime_syntaxes)] // temporary workaround for arti#2060
45
//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
46

            
47
#![allow(non_upper_case_globals)]
48
#![allow(clippy::upper_case_acronyms)]
49

            
50
use caret::caret_int;
51

            
52
use thiserror::Error;
53

            
54
pub mod named;
55

            
56
caret_int! {
57
    /// A recognized subprotocol.
58
    ///
59
    /// These names are kept in sync with the names used in consensus
60
    /// documents; the values are kept in sync with the values in the
61
    /// cbor document format in the walking onions proposal.
62
    ///
63
    /// For the full semantics of each subprotocol, see tor-spec.txt.
64
    #[derive(Hash,Ord,PartialOrd)]
65
    pub struct ProtoKind(u8) {
66
        /// Initiating and receiving channels, and getting cells on them.
67
        Link = 0,
68
        /// Different kinds of authenticate cells
69
        LinkAuth = 1,
70
        /// CREATE cells, CREATED cells, and the encryption that they
71
        /// create.
72
        Relay = 2,
73
        /// Serving and fetching network directory documents.
74
        DirCache = 3,
75
        /// Serving onion service descriptors
76
        HSDir = 4,
77
        /// Providing an onion service introduction point
78
        HSIntro = 5,
79
        /// Providing an onion service rendezvous point
80
        HSRend = 6,
81
        /// Describing a relay's functionality using router descriptors.
82
        Desc = 7,
83
        /// Describing a relay's functionality using microdescriptors.
84
        Microdesc = 8,
85
        /// Describing the network as a consensus directory document.
86
        Cons = 9,
87
        /// Sending and accepting circuit-level padding
88
        Padding = 10,
89
        /// Improved means of flow control on circuits.
90
        FlowCtrl = 11,
91
        /// Multi-path circuit support.
92
        Conflux = 12,
93
    }
94
}
95

            
96
/// How many recognized protocols are there?
97
const N_RECOGNIZED: usize = 13;
98

            
99
/// Maximum allowable value for a protocol's version field.
100
const MAX_VER: usize = 63;
101

            
102
/// A specific, named subversion of a protocol.
103
#[derive(Eq, PartialEq, Copy, Clone, Debug)]
104
pub struct NamedSubver {
105
    /// The protocol in question
106
    ///
107
    /// Must be in-range for ProtoKind (0..N_RECOGNIZED).
108
    kind: ProtoKind,
109
    /// The version of the protocol
110
    ///
111
    /// Must be in 0..=MAX_VER
112
    version: u8,
113
}
114

            
115
impl NamedSubver {
116
    /// Create a new NamedSubver.
117
    ///
118
    /// # Panics
119
    ///
120
    /// Panics if `kind` is unrecognized or `version` is invalid.
121
    const fn new(kind: ProtoKind, version: u8) -> Self {
122
        assert!((kind.0 as usize) < N_RECOGNIZED);
123
        assert!((version as usize) <= MAX_VER);
124
        Self { kind, version }
125
    }
126
}
127

            
128
/// A subprotocol capability as represented by a (kind, version) tuple.
129
///
130
/// Does not necessarily represent a real subprotocol capability;
131
/// this type is meant for use in other pieces of the protocol.
132
///
133
/// # Ordering
134
///
135
/// Instances of `NumberedSubver` are sorted in lexicographic order by
136
/// their (kind, version) tuples.
137
//
138
// TODO: As with most other types in the crate, we should decide how to rename them as as part
139
// of #1934.
140
#[derive(Clone, Copy, Debug, Ord, PartialOrd, Eq, PartialEq)]
141
pub struct NumberedSubver {
142
    /// The protocol in question
143
    kind: ProtoKind,
144
    /// The version of the protocol
145
    version: u8,
146
}
147

            
148
impl NumberedSubver {
149
    /// Construct a new [`NumberedSubver`]
150
411
    pub fn new(kind: impl Into<ProtoKind>, version: u8) -> Self {
151
411
        Self {
152
411
            kind: kind.into(),
153
411
            version,
154
411
        }
155
411
    }
156
    /// Return the ProtoKind and version for this [`NumberedSubver`].
157
    pub fn into_parts(self) -> (ProtoKind, u8) {
158
        (self.kind, self.version)
159
    }
160
}
161
impl From<NamedSubver> for NumberedSubver {
162
456
    fn from(value: NamedSubver) -> Self {
163
456
        Self {
164
456
            kind: value.kind,
165
456
            version: value.version,
166
456
        }
167
456
    }
168
}
169

            
170
#[cfg(feature = "tor-bytes")]
171
impl tor_bytes::Readable for NumberedSubver {
172
456
    fn take_from(b: &mut tor_bytes::Reader<'_>) -> tor_bytes::Result<Self> {
173
456
        let kind = b.take_u8()?;
174
456
        let version = b.take_u8()?;
175
399
        Ok(Self::new(kind, version))
176
456
    }
177
}
178

            
179
#[cfg(feature = "tor-bytes")]
180
impl tor_bytes::Writeable for NumberedSubver {
181
4
    fn write_onto<B: tor_bytes::Writer + ?Sized>(&self, b: &mut B) -> tor_bytes::EncodeResult<()> {
182
4
        b.write_u8(self.kind.into());
183
4
        b.write_u8(self.version);
184
4
        Ok(())
185
4
    }
186
}
187

            
188
/// Representation for a known or unknown protocol.
189
#[derive(Eq, PartialEq, Clone, Debug, Hash, Ord, PartialOrd)]
190
enum Protocol {
191
    /// A known protocol; represented by one of ProtoKind.
192
    ///
193
    /// ProtoKind must always be in the range 0..N_RECOGNIZED.
194
    Proto(ProtoKind),
195
    /// An unknown protocol; represented by its name.
196
    Unrecognized(String),
197
}
198

            
199
impl Protocol {
200
    /// Return true iff `s` is the name of a protocol we do not recognize.
201
608
    fn is_unrecognized(&self, s: &str) -> bool {
202
608
        match self {
203
608
            Protocol::Unrecognized(s2) => s2 == s,
204
            _ => false,
205
        }
206
608
    }
207
    /// Return a string representation of this protocol.
208
1087
    fn to_str(&self) -> &str {
209
1087
        match self {
210
            Protocol::Proto(k) => k.to_str().unwrap_or("<bug>"),
211
1087
            Protocol::Unrecognized(s) => s,
212
        }
213
1087
    }
214
}
215

            
216
/// Representation of a set of versions supported by a protocol.
217
///
218
/// For now, we only use this type for unrecognized protocols.
219
#[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
220
struct SubprotocolEntry {
221
    /// Which protocol's versions does this describe?
222
    proto: Protocol,
223
    /// A bit-vector defining which versions are supported.  If bit
224
    /// `(1<<i)` is set, then protocol version `i` is supported.
225
    supported: u64,
226
}
227

            
228
/// A set of supported or required subprotocol versions.
229
///
230
/// This type supports both recognized subprotocols (listed in ProtoKind),
231
/// and unrecognized subprotocols (stored by name).
232
///
233
/// To construct an instance, use the FromStr trait:
234
/// ```
235
/// use tor_protover::Protocols;
236
/// let p: Result<Protocols,_> = "Link=1-3 LinkAuth=2-3 Relay=1-2".parse();
237
/// ```
238
#[derive(Debug, Clone, Default, Eq, PartialEq, Hash)]
239
#[cfg_attr(
240
    feature = "serde",
241
188
    derive(serde_with::DeserializeFromStr, serde_with::SerializeDisplay)
242
)]
243
pub struct Protocols {
244
    /// A mapping from protocols' integer encodings to bit-vectors.
245
    recognized: [u64; N_RECOGNIZED],
246
    /// A vector of unrecognized protocol versions,
247
    /// in sorted order.
248
    ///
249
    /// Every entry in this list has supported != 0.
250
    unrecognized: Vec<SubprotocolEntry>,
251
}
252

            
253
impl Protocols {
254
    /// Return a new empty set of protocol versions.
255
448328
    pub fn new() -> Self {
256
448328
        Protocols::default()
257
448328
    }
258
    /// Helper: return true iff this protocol set contains the
259
    /// version `ver` of the protocol represented by the integer `proto`.
260
1286905
    fn supports_recognized_ver(&self, proto: usize, ver: u8) -> bool {
261
1286905
        if usize::from(ver) > MAX_VER {
262
2
            return false;
263
1286903
        }
264
1286903
        if proto >= self.recognized.len() {
265
            return false;
266
1286903
        }
267
1286903
        (self.recognized[proto] & (1 << ver)) != 0
268
1286905
    }
269
    /// Helper: return true iff this protocol set contains version
270
    /// `ver` of the unrecognized protocol represented by the string
271
    /// `proto`.
272
    ///
273
    /// Requires that `proto` is not the name of a recognized protocol.
274
10
    fn supports_unrecognized_ver(&self, proto: &str, ver: u8) -> bool {
275
10
        if usize::from(ver) > MAX_VER {
276
2
            return false;
277
8
        }
278
8
        let ent = self
279
8
            .unrecognized
280
8
            .iter()
281
12
            .find(|ent| ent.proto.is_unrecognized(proto));
282
8
        match ent {
283
4
            Some(e) => (e.supported & (1 << ver)) != 0,
284
4
            None => false,
285
        }
286
10
    }
287

            
288
    /// Return true if this list of protocols is empty.
289
969
    pub fn is_empty(&self) -> bool {
290
9365
        self.recognized.iter().all(|v| *v == 0)
291
570
            && self.unrecognized.iter().all(|p| p.supported == 0)
292
969
    }
293

            
294
    // TODO: Combine these next two functions into one by using a trait.
295
    /// Check whether a known protocol version is supported.
296
    ///
297
    /// ```
298
    /// use tor_protover::*;
299
    /// let protos: Protocols = "Link=1-3 HSDir=2,4-5".parse().unwrap();
300
    ///
301
    /// assert!(protos.supports_known_subver(ProtoKind::Link, 2));
302
    /// assert!(protos.supports_known_subver(ProtoKind::HSDir, 4));
303
    /// assert!(! protos.supports_known_subver(ProtoKind::HSDir, 3));
304
    /// assert!(! protos.supports_known_subver(ProtoKind::LinkAuth, 3));
305
    /// ```
306
1286787
    pub fn supports_known_subver(&self, proto: ProtoKind, ver: u8) -> bool {
307
1286787
        self.supports_recognized_ver(proto.get() as usize, ver)
308
1286787
    }
309
    /// Check whether a protocol version identified by a string is supported.
310
    ///
311
    /// ```
312
    /// use tor_protover::*;
313
    /// let protos: Protocols = "Link=1-3 Foobar=7".parse().unwrap();
314
    ///
315
    /// assert!(protos.supports_subver("Link", 2));
316
    /// assert!(protos.supports_subver("Foobar", 7));
317
    /// assert!(! protos.supports_subver("Link", 5));
318
    /// assert!(! protos.supports_subver("Foobar", 6));
319
    /// assert!(! protos.supports_subver("Wombat", 3));
320
    /// ```
321
128
    pub fn supports_subver(&self, proto: &str, ver: u8) -> bool {
322
128
        match ProtoKind::from_name(proto) {
323
118
            Some(p) => self.supports_recognized_ver(p.get() as usize, ver),
324
10
            None => self.supports_unrecognized_ver(proto, ver),
325
        }
326
128
    }
327

            
328
    /// Check whether a protocol version is supported.
329
    ///
330
    /// ```
331
    /// use tor_protover::*;
332
    /// let protos: Protocols = "Link=1-5 Desc=2-4".parse().unwrap();
333
    /// assert!(protos.supports_named_subver(named::DESC_FAMILY_IDS)); // Desc=4
334
    /// assert!(! protos.supports_named_subver(named::CONFLUX_BASE)); // Conflux=1
335
    /// ```
336
1286262
    pub fn supports_named_subver(&self, protover: NamedSubver) -> bool {
337
1286262
        self.supports_known_subver(protover.kind, protover.version)
338
1286262
    }
339

            
340
    /// Check whether a numbered subprotocol capability is supported.
341
    ///
342
    /// ```
343
    /// use tor_protover::*;
344
    /// let protos: Protocols = "Link=1-5 Desc=2-4".parse().unwrap();
345
    /// assert!(protos.supports_numbered_subver(NumberedSubver::new(ProtoKind::Desc, 4)));
346
    /// assert!(! protos.supports_numbered_subver(NumberedSubver::new(ProtoKind::Conflux, 1)));
347
    /// ```
348
513
    pub fn supports_numbered_subver(&self, protover: NumberedSubver) -> bool {
349
513
        self.supports_known_subver(protover.kind, protover.version)
350
513
    }
351

            
352
    /// Return a Protocols holding every protocol flag that is present in `self`
353
    /// but not `other`.
354
    ///
355
    /// ```
356
    /// use tor_protover::*;
357
    /// let protos: Protocols = "Desc=2-4 Microdesc=1-5".parse().unwrap();
358
    /// let protos2: Protocols = "Desc=3 Microdesc=3".parse().unwrap();
359
    /// assert_eq!(protos.difference(&protos2),
360
    ///            "Desc=2,4 Microdesc=1-2,4-5".parse().unwrap());
361
    /// ```
362
1038
    pub fn difference(&self, other: &Protocols) -> Protocols {
363
1038
        let mut r = Protocols::default();
364

            
365
14532
        for i in 0..N_RECOGNIZED {
366
13494
            r.recognized[i] = self.recognized[i] & !other.recognized[i];
367
13494
        }
368
        // This is not super efficient, but we don't have to do it often.
369
1042
        for ent in self.unrecognized.iter() {
370
73
            let mut ent = ent.clone();
371
80
            if let Some(other_ent) = other.unrecognized.iter().find(|e| e.proto == ent.proto) {
372
4
                ent.supported &= !other_ent.supported;
373
69
            }
374
73
            if ent.supported != 0 {
375
71
                r.unrecognized.push(ent);
376
71
            }
377
        }
378
1038
        r
379
1038
    }
380

            
381
    /// Return a Protocols holding every protocol flag that is present in `self`
382
    /// or `other` or both.
383
    ///
384
    /// ```
385
    /// use tor_protover::*;
386
    /// let protos: Protocols = "Desc=2-4 Microdesc=1-5".parse().unwrap();
387
    /// let protos2: Protocols = "Desc=3 Microdesc=10".parse().unwrap();
388
    /// assert_eq!(protos.union(&protos2),
389
    ///            "Desc=2-4 Microdesc=1-5,10".parse().unwrap());
390
    /// ```
391
1437
    pub fn union(&self, other: &Protocols) -> Protocols {
392
1437
        let mut r = self.clone();
393
20118
        for i in 0..N_RECOGNIZED {
394
18681
            r.recognized[i] |= other.recognized[i];
395
18681
        }
396
1441
        for ent in other.unrecognized.iter() {
397
26
            if let Some(my_ent) = r.unrecognized.iter_mut().find(|e| e.proto == ent.proto) {
398
4
                my_ent.supported |= ent.supported;
399
12
            } else {
400
12
                r.unrecognized.push(ent.clone());
401
12
            }
402
        }
403
1437
        r.unrecognized.sort();
404
1437
        r
405
1437
    }
406

            
407
    /// Return a Protocols holding every protocol flag that is present in both `self`
408
    /// and `other`.
409
    ///
410
    /// ```
411
    /// use tor_protover::*;
412
    /// let protos: Protocols = "Desc=2-4 Microdesc=1-5".parse().unwrap();
413
    /// let protos2: Protocols = "Desc=3 Microdesc=10".parse().unwrap();
414
    /// assert_eq!(protos.intersection(&protos2),
415
    ///            "Desc=3".parse().unwrap());
416
    /// ```
417
12
    pub fn intersection(&self, other: &Protocols) -> Protocols {
418
12
        let mut r = Protocols::default();
419
168
        for i in 0..N_RECOGNIZED {
420
156
            r.recognized[i] = self.recognized[i] & other.recognized[i];
421
156
        }
422
16
        for ent in self.unrecognized.iter() {
423
23
            if let Some(other_ent) = other.unrecognized.iter().find(|e| e.proto == ent.proto) {
424
4
                let supported = ent.supported & other_ent.supported;
425
4
                if supported != 0 {
426
4
                    r.unrecognized.push(SubprotocolEntry {
427
4
                        proto: ent.proto.clone(),
428
4
                        supported,
429
4
                    });
430
4
                }
431
12
            }
432
        }
433
12
        r.unrecognized.sort();
434
12
        r
435
12
    }
436

            
437
    /// Parsing helper: Try to add a new entry `ent` to this set of protocols.
438
    ///
439
    /// Uses `foundmask`, a bit mask saying which recognized protocols
440
    /// we've already found entries for.  Returns an error if `ent` is
441
    /// for a protocol we've already added.
442
    ///
443
    /// Does not preserve sorting order; the caller must call `self.unrecognized.sort()` before returning.
444
315651
    fn add(&mut self, foundmask: &mut u64, ent: SubprotocolEntry) -> Result<(), ParseError> {
445
315651
        match ent.proto {
446
314227
            Protocol::Proto(k) => {
447
314227
                let idx = k.get() as usize;
448
314227
                assert!(idx < N_RECOGNIZED); // guaranteed by invariant on Protocol::Proto
449
314227
                let bit = 1 << u64::from(k.get());
450
314227
                if (*foundmask & bit) != 0 {
451
4
                    return Err(ParseError::Duplicate);
452
314223
                }
453
314223
                *foundmask |= bit;
454
314223
                self.recognized[idx] = ent.supported;
455
            }
456
1424
            Protocol::Unrecognized(ref s) => {
457
1424
                if self
458
1424
                    .unrecognized
459
1424
                    .iter()
460
1449
                    .any(|ent| ent.proto.is_unrecognized(s))
461
                {
462
2
                    return Err(ParseError::Duplicate);
463
1422
                }
464
1422
                if ent.supported != 0 {
465
1422
                    self.unrecognized.push(ent);
466
1422
                }
467
            }
468
        }
469
315645
        Ok(())
470
315651
    }
471
}
472

            
473
/// An error representing a failure to parse a set of protocol versions.
474
#[derive(Error, Debug, PartialEq, Eq, Clone)]
475
#[non_exhaustive]
476
pub enum ParseError {
477
    /// A protocol version was not in the range 0..=63.
478
    #[error("Protocol version out of range")]
479
    OutOfRange,
480
    /// Some subprotocol or protocol version appeared more than once.
481
    #[error("Duplicate protocol entry")]
482
    Duplicate,
483
    /// The list of protocol versions was malformed in some other way.
484
    #[error("Malformed protocol entry")]
485
    Malformed,
486
}
487

            
488
/// Helper: return a new u64 in which bits `lo` through `hi` inclusive
489
/// are set to 1, and all the other bits are set to 0.
490
///
491
/// In other words, `bitrange(a,b)` is how we represent the range of
492
/// versions `a-b` in a protocol version bitmask.
493
///
494
/// ```ignore
495
/// # use tor_protover::bitrange;
496
/// assert_eq!(bitrange(0, 5), 0b111111);
497
/// assert_eq!(bitrange(2, 5), 0b111100);
498
/// assert_eq!(bitrange(2, 7), 0b11111100);
499
/// ```
500
322518
fn bitrange(lo: u64, hi: u64) -> u64 {
501
322518
    assert!(lo <= hi && lo <= 63 && hi <= 63);
502
322518
    let mut mask = !0;
503
322518
    mask <<= 63 - hi;
504
322518
    mask >>= 63 - hi + lo;
505
322518
    mask <<= lo;
506
322518
    mask
507
322518
}
508

            
509
/// Helper: return true if the provided string is a valid "integer"
510
/// in the form accepted by the protover spec.  This is stricter than
511
/// rust's integer parsing format.
512
645058
fn is_good_number(n: &str) -> bool {
513
659669
    n.chars().all(|ch| ch.is_ascii_digit()) && !n.starts_with('0')
514
645058
}
515

            
516
/// A single SubprotocolEntry is parsed from a string of the format
517
/// Name=Versions, where Versions is a comma-separated list of
518
/// integers or ranges of integers.
519
impl std::str::FromStr for SubprotocolEntry {
520
    type Err = ParseError;
521

            
522
315681
    fn from_str(s: &str) -> Result<Self, ParseError> {
523
        // split the string on the =.
524
315679
        let (name, versions) = {
525
315681
            let eq_idx = s.find('=').ok_or(ParseError::Malformed)?;
526
315679
            (&s[..eq_idx], &s[eq_idx + 1..])
527
        };
528
        // Look up the protocol by name.
529
315679
        let proto = match ProtoKind::from_name(name) {
530
314253
            Some(p) => Protocol::Proto(p),
531
1426
            None => Protocol::Unrecognized(name.to_string()),
532
        };
533
315679
        if versions.is_empty() {
534
            // We need to handle this case specially, since otherwise
535
            // it would be treated below as a single empty value, which
536
            // would be rejected.
537
2
            return Ok(SubprotocolEntry {
538
2
                proto,
539
2
                supported: 0,
540
2
            });
541
315677
        }
542
315677
        // Construct a bitmask based on the comma-separated versions.
543
315677
        let mut supported = 0_u64;
544
322534
        for ent in versions.split(',') {
545
            // Find and parse lo and hi for a single range of versions.
546
            // (If this is not a range, but rather a single version v,
547
            // treat it as if it were a range v-v.)
548
322534
            let (lo_s, hi_s) = {
549
322534
                match ent.find('-') {
550
74379
                    Some(pos) => (&ent[..pos], &ent[pos + 1..]),
551
248155
                    None => (ent, ent),
552
                }
553
            };
554
322534
            if !is_good_number(lo_s) {
555
10
                return Err(ParseError::Malformed);
556
322524
            }
557
322524
            if !is_good_number(hi_s) {
558
2
                return Err(ParseError::Malformed);
559
322522
            }
560
322523
            let lo: u64 = lo_s.parse().map_err(|_| ParseError::Malformed)?;
561
322522
            let hi: u64 = hi_s.parse().map_err(|_| ParseError::Malformed)?;
562
            // Make sure that lo and hi are in-bounds and consistent.
563
322516
            if lo > (MAX_VER as u64) || hi > (MAX_VER as u64) {
564
6
                return Err(ParseError::OutOfRange);
565
322510
            }
566
322510
            if lo > hi {
567
2
                return Err(ParseError::Malformed);
568
322508
            }
569
322508
            let mask = bitrange(lo, hi);
570
322508
            // Make sure that no version is included twice.
571
322508
            if (supported & mask) != 0 {
572
2
                return Err(ParseError::Duplicate);
573
322506
            }
574
322506
            // Add the appropriate bits to the mask.
575
322506
            supported |= mask;
576
        }
577
315649
        Ok(SubprotocolEntry { proto, supported })
578
315681
    }
579
}
580

            
581
/// A Protocols set can be parsed from a string according to the
582
/// format used in Tor consensus documents.
583
///
584
/// A protocols set is represented by a space-separated list of
585
/// entries.  Each entry is of the form `Name=Versions`, where `Name`
586
/// is the name of a protocol, and `Versions` is a comma-separated
587
/// list of version numbers and version ranges.  Each version range is
588
/// a pair of integers separated by `-`.
589
///
590
/// No protocol name may be listed twice.  No version may be listed
591
/// twice for a single protocol.  All versions must be in range 0
592
/// through 63 inclusive.
593
impl std::str::FromStr for Protocols {
594
    type Err = ParseError;
595

            
596
425864
    fn from_str(s: &str) -> Result<Self, ParseError> {
597
425864
        let mut result = Protocols::new();
598
425864
        let mut foundmask = 0_u64;
599
523395
        for ent in s.split(' ') {
600
523395
            if ent.is_empty() {
601
207714
                continue;
602
315681
            }
603

            
604
315681
            let s: SubprotocolEntry = ent.parse()?;
605
315651
            result.add(&mut foundmask, s)?;
606
        }
607
425828
        result.unrecognized.sort();
608
425828
        Ok(result)
609
425864
    }
610
}
611

            
612
/// Given a bitmask, return a list of the bits set in the mask, as a
613
/// String in the format expected by Tor consensus documents.
614
///
615
/// This implementation constructs ranges greedily.  For example, the
616
/// bitmask `0b0111011` will be represented as `0-1,3-5`, and not
617
/// `0,1,3,4,5` or `0,1,3-5`.
618
///
619
/// ```ignore
620
/// # use tor_protover::dumpmask;
621
/// assert_eq!(dumpmask(0b111111), "0-5");
622
/// assert_eq!(dumpmask(0b111100), "2-5");
623
/// assert_eq!(dumpmask(0b11111100), "2-7");
624
/// ```
625
3444
fn dumpmask(mut mask: u64) -> String {
626
    /// Helper: push a range (which may be a singleton) onto `v`.
627
3507
    fn append(v: &mut Vec<String>, lo: u32, hi: u32) {
628
3507
        if lo == hi {
629
1496
            v.push(lo.to_string());
630
2011
        } else {
631
2011
            v.push(format!("{}-{}", lo, hi));
632
2011
        }
633
3507
    }
634
    // We'll be building up our result here, then joining it with
635
    // commas.
636
3444
    let mut result = Vec::new();
637
3444
    // This implementation is a little tricky, but it should be more
638
3444
    // efficient than a raw search.  Basically, we're using the
639
3444
    // function u64::trailing_zeros to count how large each range of
640
3444
    // 1s or 0s is, and then shifting by that amount.
641
3444

            
642
3444
    // How many bits have we already shifted `mask`?
643
3444
    let mut shift = 0;
644
6949
    while mask != 0 {
645
3507
        let zeros = mask.trailing_zeros();
646
3507
        mask >>= zeros;
647
3507
        shift += zeros;
648
3507
        let ones = mask.trailing_ones();
649
3507
        append(&mut result, shift, shift + ones - 1);
650
3507
        shift += ones;
651
3507
        if ones == 64 {
652
            // We have to do this check to avoid overflow when formatting
653
            // the range `0-63`.
654
2
            break;
655
3505
        }
656
3505
        mask >>= ones;
657
    }
658
3444
    result.join(",")
659
3444
}
660

            
661
/// The Display trait formats a protocol set in the format expected by Tor
662
/// consensus documents.
663
///
664
/// ```
665
/// use tor_protover::*;
666
/// let protos: Protocols = "Link=1,2,3 Foobar=7 Relay=2".parse().unwrap();
667
/// assert_eq!(format!("{}", protos),
668
///            "Foobar=7 Link=1-3 Relay=2");
669
/// ```
670
impl std::fmt::Display for Protocols {
671
1891
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
672
1891
        let mut entries = Vec::new();
673
24583
        for (idx, mask) in self.recognized.iter().enumerate() {
674
24583
            if *mask != 0 {
675
2347
                let pk: ProtoKind = (idx as u8).into();
676
2347
                entries.push(format!("{}={}", pk, dumpmask(*mask)));
677
22236
            }
678
        }
679
2978
        for ent in &self.unrecognized {
680
1087
            if ent.supported != 0 {
681
1087
                entries.push(format!(
682
1087
                    "{}={}",
683
1087
                    ent.proto.to_str(),
684
1087
                    dumpmask(ent.supported)
685
1087
                ));
686
1087
            }
687
        }
688
        // This sort is required.
689
1891
        entries.sort();
690
1891
        write!(f, "{}", entries.join(" "))
691
1891
    }
692
}
693

            
694
impl FromIterator<NamedSubver> for Protocols {
695
1972
    fn from_iter<T: IntoIterator<Item = NamedSubver>>(iter: T) -> Self {
696
1972
        let mut r = Protocols::new();
697
8180
        for named_subver in iter {
698
6208
            let proto_idx = usize::from(named_subver.kind.get());
699
6208
            let proto_ver = named_subver.version;
700
6208

            
701
6208
            // These are guaranteed by invariants on NamedSubver.
702
6208
            assert!(proto_idx < N_RECOGNIZED);
703
6208
            assert!(usize::from(proto_ver) <= MAX_VER);
704
6208
            r.recognized[proto_idx] |= 1_u64 << proto_ver;
705
        }
706
1972
        r
707
1972
    }
708
}
709

            
710
/// Documentation: when is a protocol "supported"?
711
///
712
/// Arti should consider itself to "support" a protocol if, _as built_,
713
/// it implements the protocol completely.
714
///
715
/// Just having the protocol listed among the [`named`]
716
/// protocols is not enough, and neither is an incomplete
717
/// or uncompliant implementation.
718
///
719
/// Similarly, if the protocol is not compiled in,
720
/// it is not technically _supported_.
721
///
722
/// When in doubt, ask yourself:
723
/// - If another Tor implementation believed that we implemented this protocol,
724
///   and began to speak it to us, would we be able to do so?
725
/// - If the protocol were required,
726
///   would this software as built actually meet that requirement?
727
///
728
/// If either answer is no, the protocol is not supported.
729
pub mod doc_supported {}
730

            
731
/// Documentation about changing lists of supported versions.
732
///
733
/// # Warning
734
///
735
/// You need to be extremely careful when removing
736
/// _any_ entry from a list of supported protocols.
737
///
738
/// If you remove an entry while it still appears as "recommended" in the consensus,
739
/// you'll cause all the instances without it to warn.
740
///
741
/// If you remove an entry while it still appears as "required" in the
742
///  consensus, you'll cause all the instances without it to refuse to connect
743
/// to the network, and shut down.
744
///
745
/// If you need to remove a version from a list of supported protocols,
746
/// you need to make sure that it is not listed in the _current consensuses_:
747
/// just removing it from the list that the authorities vote for is NOT ENOUGH.
748
/// You need to remove it from the required list,
749
/// and THEN let the authorities upgrade and vote on new
750
/// consensuses without it. Only once those consensuses are out is it safe to
751
/// remove from the list of required protocols.
752
///
753
/// ## Example
754
///
755
/// One concrete example of a very dangerous race that could occur:
756
///
757
/// Suppose that the client supports protocols "HsDir=1-2" and the consensus
758
/// requires protocols "HsDir=1-2.  If the client supported protocol list is
759
/// then changed to "HSDir=2", while the consensus stills lists "HSDir=1-2",
760
/// then these clients, even very recent ones, will shut down because they
761
/// don't support "HSDir=1".
762
///
763
/// And so, changes need to be done in strict sequence as described above.
764
pub mod doc_changing {}
765

            
766
#[cfg(test)]
767
mod test {
768
    // @@ begin test lint list maintained by maint/add_warning @@
769
    #![allow(clippy::bool_assert_comparison)]
770
    #![allow(clippy::clone_on_copy)]
771
    #![allow(clippy::dbg_macro)]
772
    #![allow(clippy::mixed_attributes_style)]
773
    #![allow(clippy::print_stderr)]
774
    #![allow(clippy::print_stdout)]
775
    #![allow(clippy::single_char_pattern)]
776
    #![allow(clippy::unwrap_used)]
777
    #![allow(clippy::unchecked_duration_subtraction)]
778
    #![allow(clippy::useless_vec)]
779
    #![allow(clippy::needless_pass_by_value)]
780
    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
781
    use std::str::FromStr;
782

            
783
    use super::*;
784

            
785
    #[test]
786
    fn test_bitrange() {
787
        assert_eq!(0b1, bitrange(0, 0));
788
        assert_eq!(0b10, bitrange(1, 1));
789
        assert_eq!(0b11, bitrange(0, 1));
790
        assert_eq!(0b1111110000000, bitrange(7, 12));
791
        assert_eq!(!0, bitrange(0, 63));
792
    }
793

            
794
    #[test]
795
    fn test_dumpmask() {
796
        assert_eq!("", dumpmask(0));
797
        assert_eq!("0-5", dumpmask(0b111111));
798
        assert_eq!("4-5", dumpmask(0b110000));
799
        assert_eq!("1,4-5", dumpmask(0b110010));
800
        assert_eq!("0-63", dumpmask(!0));
801
    }
802

            
803
    #[test]
804
    fn test_canonical() -> Result<(), ParseError> {
805
        fn t(orig: &str, canonical: &str) -> Result<(), ParseError> {
806
            let protos: Protocols = orig.parse()?;
807
            let enc = format!("{}", protos);
808
            assert_eq!(enc, canonical);
809
            Ok(())
810
        }
811

            
812
        t("", "")?;
813
        t(" ", "")?;
814
        t("Link=5,6,7,9 Relay=4-7,2", "Link=5-7,9 Relay=2,4-7")?;
815
        t("FlowCtrl= Padding=8,7 Desc=1-5,6-8", "Desc=1-8 Padding=7-8")?;
816
        t("Zelda=7 Gannon=3,6 Link=4", "Gannon=3,6 Link=4 Zelda=7")?;
817

            
818
        Ok(())
819
    }
820

            
821
    #[test]
822
    fn test_invalid() {
823
        fn t(s: &str) -> ParseError {
824
            let protos: Result<Protocols, ParseError> = s.parse();
825
            assert!(protos.is_err());
826
            protos.err().unwrap()
827
        }
828

            
829
        assert_eq!(t("Link=1-100"), ParseError::OutOfRange);
830
        assert_eq!(t("Zelda=100"), ParseError::OutOfRange);
831
        assert_eq!(t("Link=100-200"), ParseError::OutOfRange);
832

            
833
        assert_eq!(t("Link=1,1"), ParseError::Duplicate);
834
        assert_eq!(t("Link=1 Link=1"), ParseError::Duplicate);
835
        assert_eq!(t("Link=1 Link=3"), ParseError::Duplicate);
836
        assert_eq!(t("Zelda=1 Zelda=3"), ParseError::Duplicate);
837

            
838
        assert_eq!(t("Link=Zelda"), ParseError::Malformed);
839
        assert_eq!(t("Link=6-2"), ParseError::Malformed);
840
        assert_eq!(t("Link=6-"), ParseError::Malformed);
841
        assert_eq!(t("Link=6-,2"), ParseError::Malformed);
842
        assert_eq!(t("Link=1,,2"), ParseError::Malformed);
843
        assert_eq!(t("Link=6-frog"), ParseError::Malformed);
844
        assert_eq!(t("Link=gannon-9"), ParseError::Malformed);
845
        assert_eq!(t("Link Zelda"), ParseError::Malformed);
846

            
847
        assert_eq!(t("Link=01"), ParseError::Malformed);
848
        assert_eq!(t("Link=waffle"), ParseError::Malformed);
849
        assert_eq!(t("Link=1_1"), ParseError::Malformed);
850
    }
851

            
852
    #[test]
853
    fn test_supports() -> Result<(), ParseError> {
854
        let p: Protocols = "Link=4,5-7 Padding=2 Lonk=1-3,5".parse()?;
855

            
856
        assert!(p.supports_known_subver(ProtoKind::Padding, 2));
857
        assert!(!p.supports_known_subver(ProtoKind::Padding, 1));
858
        assert!(p.supports_known_subver(ProtoKind::Link, 6));
859
        assert!(!p.supports_known_subver(ProtoKind::Link, 255));
860
        assert!(!p.supports_known_subver(ProtoKind::Cons, 1));
861
        assert!(!p.supports_known_subver(ProtoKind::Cons, 0));
862
        assert!(p.supports_subver("Link", 6));
863
        assert!(!p.supports_subver("link", 6));
864
        assert!(!p.supports_subver("Cons", 0));
865
        assert!(p.supports_subver("Lonk", 3));
866
        assert!(!p.supports_subver("Lonk", 4));
867
        assert!(!p.supports_subver("lonk", 3));
868
        assert!(!p.supports_subver("Lonk", 64));
869

            
870
        Ok(())
871
    }
872

            
873
    #[test]
874
    fn test_difference() -> Result<(), ParseError> {
875
        let p1: Protocols = "Link=1-10 Desc=5-10 Relay=1,3,5,7,9 Other=7-60 Mine=1-20".parse()?;
876
        let p2: Protocols = "Link=3-4 Desc=1-6 Relay=2-6 Other=8 Theirs=20".parse()?;
877

            
878
        assert_eq!(
879
            p1.difference(&p2),
880
            Protocols::from_str("Link=1-2,5-10 Desc=7-10 Relay=1,7,9 Other=7,9-60 Mine=1-20")?
881
        );
882
        assert_eq!(
883
            p2.difference(&p1),
884
            Protocols::from_str("Desc=1-4 Relay=2,4,6 Theirs=20")?,
885
        );
886

            
887
        let nil = Protocols::default();
888
        assert_eq!(p1.difference(&nil), p1);
889
        assert_eq!(p2.difference(&nil), p2);
890
        assert_eq!(nil.difference(&p1), nil);
891
        assert_eq!(nil.difference(&p2), nil);
892

            
893
        Ok(())
894
    }
895

            
896
    #[test]
897
    fn test_union() -> Result<(), ParseError> {
898
        let p1: Protocols = "Link=1-10 Desc=5-10 Relay=1,3,5,7,9 Other=7-60 Mine=1-20".parse()?;
899
        let p2: Protocols = "Link=3-4 Desc=1-6 Relay=2-6 Other=2,8 Theirs=20".parse()?;
900

            
901
        assert_eq!(
902
            p1.union(&p2),
903
            Protocols::from_str(
904
                "Link=1-10 Desc=1-10 Relay=1-7,9 Other=2,7-60 Theirs=20 Mine=1-20"
905
            )?
906
        );
907
        assert_eq!(
908
            p2.union(&p1),
909
            Protocols::from_str(
910
                "Link=1-10 Desc=1-10 Relay=1-7,9 Other=2,7-60 Theirs=20 Mine=1-20"
911
            )?
912
        );
913

            
914
        let nil = Protocols::default();
915
        assert_eq!(p1.union(&nil), p1);
916
        assert_eq!(p2.union(&nil), p2);
917
        assert_eq!(nil.union(&p1), p1);
918
        assert_eq!(nil.union(&p2), p2);
919

            
920
        Ok(())
921
    }
922

            
923
    #[test]
924
    fn test_intersection() -> Result<(), ParseError> {
925
        let p1: Protocols = "Link=1-10 Desc=5-10 Relay=1,3,5,7,9 Other=7-60 Mine=1-20".parse()?;
926
        let p2: Protocols = "Link=3-4 Desc=1-6 Relay=2-6 Other=2,8 Theirs=20".parse()?;
927

            
928
        assert_eq!(
929
            p1.intersection(&p2),
930
            Protocols::from_str("Link=3-4 Desc=5-6 Relay=3,5 Other=8")?
931
        );
932
        assert_eq!(
933
            p2.intersection(&p1),
934
            Protocols::from_str("Link=3-4 Desc=5-6 Relay=3,5 Other=8")?
935
        );
936

            
937
        let nil = Protocols::default();
938
        assert_eq!(p1.intersection(&nil), nil);
939
        assert_eq!(p2.intersection(&nil), nil);
940
        assert_eq!(nil.intersection(&p1), nil);
941
        assert_eq!(nil.intersection(&p2), nil);
942

            
943
        Ok(())
944
    }
945

            
946
    #[test]
947
    fn from_iter() {
948
        use named as n;
949
        let empty: [NamedSubver; 0] = [];
950
        let prs: Protocols = empty.iter().copied().collect();
951
        assert_eq!(prs, Protocols::default());
952
        let prs: Protocols = empty.into_iter().collect();
953
        assert_eq!(prs, Protocols::default());
954

            
955
        let prs = [
956
            n::LINK_V3,
957
            n::HSDIR_V3,
958
            n::LINK_V4,
959
            n::LINK_V5,
960
            n::CONFLUX_BASE,
961
        ]
962
        .into_iter()
963
        .collect::<Protocols>();
964
        assert_eq!(prs, "Link=3-5 HSDir=2 Conflux=1".parse().unwrap());
965
    }
966

            
967
    #[test]
968
    fn order_numbered_subvers() {
969
        // We rely on this sort order elsewhere in our protocol.
970
        assert!(NumberedSubver::new(5, 7) < NumberedSubver::new(7, 5));
971
        assert!(NumberedSubver::new(7, 5) < NumberedSubver::new(7, 6));
972
        assert!(NumberedSubver::new(7, 6) < NumberedSubver::new(8, 6));
973
    }
974
}