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
#![cfg_attr(not(ci_arti_stable), allow(renamed_and_removed_lints))]
5
#![cfg_attr(not(ci_arti_nightly), allow(unknown_lints))]
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::unnecessary_wraps)]
34
#![warn(clippy::unseparated_literal_suffix)]
35
#![deny(clippy::unwrap_used)]
36
#![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness
37
#![allow(clippy::uninlined_format_args)]
38
#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945
39
#![allow(clippy::result_large_err)] // temporary workaround for arti#587
40
#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best
41
//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
42

            
43
use std::fmt::{Display, Formatter};
44
use std::num::NonZeroUsize;
45
use std::str::FromStr;
46

            
47
mod err;
48
pub use err::Error;
49

            
50
/// Result type used by this crate
51
type Result<T> = std::result::Result<T, Error>;
52

            
53
/// Return true if `s` looks more like a consensus diff than some other kind
54
/// of document.
55
19
pub fn looks_like_diff(s: &str) -> bool {
56
19
    s.starts_with("network-status-diff-version")
57
19
}
58

            
59
/// Apply a given diff to an input text, and return the result from applying
60
/// that diff.
61
///
62
/// This is a slow version, for testing and correctness checking.  It uses
63
/// an O(n) operation to apply diffs, and therefore runs in O(n^2) time.
64
#[cfg(any(test, fuzzing, feature = "slow-diff-apply"))]
65
pub fn apply_diff_trivial<'a>(input: &'a str, diff: &'a str) -> Result<DiffResult<'a>> {
66
    let mut diff_lines = diff.lines();
67
    let (_, d2) = parse_diff_header(&mut diff_lines)?;
68

            
69
    let mut diffable = DiffResult::from_str(input, d2);
70

            
71
    for command in DiffCommandIter::new(diff_lines) {
72
        command?.apply_to(&mut diffable)?;
73
    }
74

            
75
    Ok(diffable)
76
}
77

            
78
/// Apply a given diff to an input text, and return the result from applying
79
/// that diff.
80
///
81
/// If `check_digest_in` is provided, require the diff to say that it
82
/// applies to a document with the provided digest.
83
pub fn apply_diff<'a>(
84
    input: &'a str,
85
    diff: &'a str,
86
    check_digest_in: Option<[u8; 32]>,
87
) -> Result<DiffResult<'a>> {
88
    let mut input = DiffResult::from_str(input, [0; 32]);
89

            
90
    let mut diff_lines = diff.lines();
91
    let (d1, d2) = parse_diff_header(&mut diff_lines)?;
92
    if let Some(d_want) = check_digest_in {
93
        if d1 != d_want {
94
            return Err(Error::CantApply("listed digest does not match document"));
95
        }
96
    }
97

            
98
    let mut output = DiffResult::new(d2);
99

            
100
    for command in DiffCommandIter::new(diff_lines) {
101
        command?.apply_transformation(&mut input, &mut output)?;
102
    }
103

            
104
    output.push_reversed(&input.lines[..]);
105

            
106
    output.lines.reverse();
107
    Ok(output)
108
}
109

            
110
/// Given a line iterator, check to make sure the first two lines are
111
/// a valid diff header as specified in dir-spec.txt.
112
fn parse_diff_header<'a, I>(iter: &mut I) -> Result<([u8; 32], [u8; 32])>
113
where
114
    I: Iterator<Item = &'a str>,
115
{
116
    let line1 = iter.next();
117
    if line1 != Some("network-status-diff-version 1") {
118
        return Err(Error::BadDiff("unrecognized or missing header"));
119
    }
120
    let line2 = iter.next().ok_or(Error::BadDiff("header truncated"))?;
121
    if !line2.starts_with("hash ") {
122
        return Err(Error::BadDiff("missing 'hash' line"));
123
    }
124
    let elts: Vec<_> = line2.split_ascii_whitespace().collect();
125
    if elts.len() != 3 {
126
        return Err(Error::BadDiff("invalid 'hash' line"));
127
    }
128
    let d1 = hex::decode(elts[1])?;
129
    let d2 = hex::decode(elts[2])?;
130
    match (d1.try_into(), d2.try_into()) {
131
        (Ok(a), Ok(b)) => Ok((a, b)),
132
        _ => Err(Error::BadDiff("wrong digest lengths on 'hash' line")),
133
    }
134
}
135

            
136
/// A command that can appear in a diff.  Each command tells us to
137
/// remove zero or more lines, and insert zero or more lines in their
138
/// place.
139
///
140
/// Commands refer to lines by 1-indexed line number.
141
#[derive(Clone, Debug)]
142
enum DiffCommand<'a> {
143
    /// Remove the lines from low through high, inclusive.
144
    Delete {
145
        /// The first line to remove
146
        low: usize,
147
        /// The last line to remove
148
        high: usize,
149
    },
150
    /// Remove the lines from low through the end of the file, inclusive.
151
    DeleteToEnd {
152
        /// The first line to remove
153
        low: usize,
154
    },
155
    /// Replace the lines from low through high, inclusive, with the
156
    /// lines in 'lines'.
157
    Replace {
158
        /// The first line to replace
159
        low: usize,
160
        /// The last line to replace
161
        high: usize,
162
        /// The text to insert instead
163
        lines: Vec<&'a str>,
164
    },
165
    /// Insert the provided 'lines' after the line with index 'pos'.
166
    Insert {
167
        /// The position after which to insert the text
168
        pos: usize,
169
        /// The text to insert
170
        lines: Vec<&'a str>,
171
    },
172
}
173

            
174
/// The result of applying one or more diff commands to an input string.
175
///
176
/// It refers to lines from the diff and the input by reference, to
177
/// avoid copying.
178
#[derive(Clone, Debug)]
179
pub struct DiffResult<'a> {
180
    /// An expected digest of the output, after it has been assembled.
181
    d_post: [u8; 32],
182
    /// The lines in the output.
183
    lines: Vec<&'a str>,
184
}
185

            
186
/// A possible value for the end of a range.  It can be either a line number,
187
/// or a dollar sign indicating "end of file".
188
#[derive(Clone, Copy, Debug)]
189
enum RangeEnd {
190
    /// A line number in the file.
191
    Num(NonZeroUsize),
192
    /// A dollar sign, indicating "end of file" in a delete command.
193
    DollarSign,
194
}
195

            
196
impl FromStr for RangeEnd {
197
    type Err = Error;
198
    fn from_str(s: &str) -> Result<RangeEnd> {
199
        if s == "$" {
200
            Ok(RangeEnd::DollarSign)
201
        } else {
202
            let v: NonZeroUsize = s.parse()?;
203
            if v.get() == std::usize::MAX {
204
                return Err(Error::BadDiff("range end cannot at usize::MAX"));
205
            }
206
            Ok(RangeEnd::Num(v))
207
        }
208
    }
209
}
210

            
211
impl<'a> DiffCommand<'a> {
212
    /// Transform 'target' according to the this command.
213
    ///
214
    /// Because DiffResult internally uses a vector of line, this
215
    /// implementation is potentially O(n) in the size of the input.
216
    #[cfg(any(test, fuzzing, feature = "slow-diff-apply"))]
217
    fn apply_to(&self, target: &mut DiffResult<'a>) -> Result<()> {
218
        match self {
219
            Self::Delete { low, high } => {
220
                target.remove_lines(*low, *high)?;
221
            }
222
            Self::DeleteToEnd { low } => {
223
                target.remove_lines(*low, target.lines.len())?;
224
            }
225
            Self::Replace { low, high, lines } => {
226
                target.remove_lines(*low, *high)?;
227
                target.insert_at(*low, lines)?;
228
            }
229
            Self::Insert { pos, lines } => {
230
                // This '+1' seems off, but it's what the spec says. I wonder
231
                // if the spec is wrong.
232
                target.insert_at(*pos + 1, lines)?;
233
            }
234
        };
235
        Ok(())
236
    }
237

            
238
    /// Apply this command to 'input', moving lines into 'output'.
239
    ///
240
    /// This is a more efficient algorithm, but it requires that the
241
    /// diff commands are sorted in reverse order by line
242
    /// number. (Fortunately, the Tor ed diff format guarantees this.)
243
    ///
244
    /// Before calling this method, input and output must contain the
245
    /// results of having applied the previous command in the diff.
246
    /// (When no commands have been applied, input starts out as the
247
    /// original text, and output starts out empty.)
248
    ///
249
    /// This method applies the command by copying unaffected lines
250
    /// from the _end_ of input into output, adding any lines inserted
251
    /// by this command, and finally deleting any affected lines from
252
    /// input.
253
    ///
254
    /// We builds the `output` value in reverse order, and then put it
255
    /// back to normal before giving it to the user.
256
    fn apply_transformation(
257
        &self,
258
        input: &mut DiffResult<'a>,
259
        output: &mut DiffResult<'a>,
260
    ) -> Result<()> {
261
        if let Some(succ) = self.following_lines() {
262
            if let Some(subslice) = input.lines.get(succ - 1..) {
263
                // Lines from `succ` onwards are unaffected.  Copy them.
264
                output.push_reversed(subslice);
265
            } else {
266
                // Oops, dubious line number.
267
                return Err(Error::CantApply(
268
                    "ending line number didn't correspond to document",
269
                ));
270
            }
271
        }
272

            
273
        if let Some(lines) = self.lines() {
274
            // These are the lines we're inserting.
275
            output.push_reversed(lines);
276
        }
277

            
278
        let remove = self.first_removed_line();
279
        if remove == 0 || (!self.is_insert() && remove > input.lines.len()) {
280
            return Err(Error::CantApply(
281
                "starting line number didn't correspond to document",
282
            ));
283
        }
284
        input.lines.truncate(remove - 1);
285

            
286
        Ok(())
287
    }
288

            
289
    /// Return the lines that we should add to the output
290
    fn lines(&self) -> Option<&[&'a str]> {
291
        match self {
292
            Self::Replace { lines, .. } | Self::Insert { lines, .. } => Some(lines.as_slice()),
293
            _ => None,
294
        }
295
    }
296

            
297
    /// Return a mutable reference to the vector of lines we should
298
    /// add to the output.
299
    fn linebuf_mut(&mut self) -> Option<&mut Vec<&'a str>> {
300
        match self {
301
            Self::Replace { ref mut lines, .. } | Self::Insert { ref mut lines, .. } => Some(lines),
302
            _ => None,
303
        }
304
    }
305

            
306
    /// Return the (1-indexed) line number of the first line in the
307
    /// input that comes _after_ this command, and is not affected by it.
308
    ///
309
    /// We use this line number to know which lines we should copy.
310
    fn following_lines(&self) -> Option<usize> {
311
        match self {
312
            Self::Delete { high, .. } | Self::Replace { high, .. } => Some(high + 1),
313
            Self::DeleteToEnd { .. } => None,
314
            Self::Insert { pos, .. } => Some(pos + 1),
315
        }
316
    }
317

            
318
    /// Return the (1-indexed) line number of the first line that we
319
    /// should clear from the input when processing this command.
320
    ///
321
    /// This can be the same as following_lines(), if we shouldn't
322
    /// actually remove any lines.
323
    fn first_removed_line(&self) -> usize {
324
        match self {
325
            Self::Delete { low, .. } => *low,
326
            Self::DeleteToEnd { low } => *low,
327
            Self::Replace { low, .. } => *low,
328
            Self::Insert { pos, .. } => *pos + 1,
329
        }
330
    }
331

            
332
    /// Return true if this is an Insert command.
333
    fn is_insert(&self) -> bool {
334
        matches!(self, Self::Insert { .. })
335
    }
336

            
337
    /// Extract a single command from a line iterator that yields lines
338
    /// of the diffs.  Return None if we're at the end of the iterator.
339
    fn from_line_iterator<I>(iter: &mut I) -> Result<Option<Self>>
340
    where
341
        I: Iterator<Item = &'a str>,
342
    {
343
        let command = match iter.next() {
344
            Some(s) => s,
345
            None => return Ok(None),
346
        };
347

            
348
        // `command` can be of these forms: `Rc`, `Rd`, `N,$d`, and `Na`,
349
        // where R is a range of form `N,N`, and where N is a line number.
350

            
351
        if command.len() < 2 || !command.is_ascii() {
352
            return Err(Error::BadDiff("command too short"));
353
        }
354

            
355
        let (range, command) = command.split_at(command.len() - 1);
356
        let (low, high) = if let Some(comma_pos) = range.find(',') {
357
            (
358
                range[..comma_pos].parse::<usize>()?,
359
                Some(range[comma_pos + 1..].parse::<RangeEnd>()?),
360
            )
361
        } else {
362
            (range.parse::<usize>()?, None)
363
        };
364

            
365
        if low == std::usize::MAX {
366
            return Err(Error::BadDiff("range cannot begin at usize::MAX"));
367
        }
368

            
369
        match (low, high) {
370
            (lo, Some(RangeEnd::Num(hi))) if lo > hi.into() => {
371
                return Err(Error::BadDiff("mis-ordered lines in range"))
372
            }
373
            (_, _) => (),
374
        }
375

            
376
        let mut cmd = match (command, low, high) {
377
            ("d", low, None) => Self::Delete { low, high: low },
378
            ("d", low, Some(RangeEnd::Num(high))) => Self::Delete {
379
                low,
380
                high: high.into(),
381
            },
382
            ("d", low, Some(RangeEnd::DollarSign)) => Self::DeleteToEnd { low },
383
            ("c", low, None) => Self::Replace {
384
                low,
385
                high: low,
386
                lines: Vec::new(),
387
            },
388
            ("c", low, Some(RangeEnd::Num(high))) => Self::Replace {
389
                low,
390
                high: high.into(),
391
                lines: Vec::new(),
392
            },
393
            ("a", low, None) => Self::Insert {
394
                pos: low,
395
                lines: Vec::new(),
396
            },
397
            (_, _, _) => return Err(Error::BadDiff("can't parse command line")),
398
        };
399

            
400
        if let Some(ref mut linebuf) = cmd.linebuf_mut() {
401
            // The 'c' and 'a' commands take a series of lines followed by a
402
            // line containing a period.
403
            loop {
404
                match iter.next() {
405
                    None => return Err(Error::BadDiff("unterminated block to insert")),
406
                    Some(".") => break,
407
                    Some(line) => linebuf.push(line),
408
                }
409
            }
410
        }
411

            
412
        Ok(Some(cmd))
413
    }
414
}
415

            
416
/// Iterator that wraps a line iterator and returns a sequence of
417
/// `Result<DiffCommand>`.
418
///
419
/// This iterator forces the commands to affect the file in reverse order,
420
/// so that we can use the O(n) algorithm for applying these diffs.
421
struct DiffCommandIter<'a, I>
422
where
423
    I: Iterator<Item = &'a str>,
424
{
425
    /// The underlying iterator.
426
    iter: I,
427

            
428
    /// The 'first removed line' of the last-parsed command; used to ensure
429
    /// that commands appear in reverse order.
430
    last_cmd_first_removed: Option<usize>,
431
}
432

            
433
impl<'a, I> DiffCommandIter<'a, I>
434
where
435
    I: Iterator<Item = &'a str>,
436
{
437
    /// Construct a new DiffCommandIter wrapping `iter`.
438
    fn new(iter: I) -> Self {
439
        DiffCommandIter {
440
            iter,
441
            last_cmd_first_removed: None,
442
        }
443
    }
444
}
445

            
446
impl<'a, I> Iterator for DiffCommandIter<'a, I>
447
where
448
    I: Iterator<Item = &'a str>,
449
{
450
    type Item = Result<DiffCommand<'a>>;
451
    fn next(&mut self) -> Option<Result<DiffCommand<'a>>> {
452
        match DiffCommand::from_line_iterator(&mut self.iter) {
453
            Err(e) => Some(Err(e)),
454
            Ok(None) => None,
455
            Ok(Some(c)) => match (self.last_cmd_first_removed, c.following_lines()) {
456
                (Some(_), None) => Some(Err(Error::BadDiff("misordered commands"))),
457
                (Some(a), Some(b)) if a < b => Some(Err(Error::BadDiff("misordered commands"))),
458
                (_, _) => {
459
                    self.last_cmd_first_removed = Some(c.first_removed_line());
460
                    Some(Ok(c))
461
                }
462
            },
463
        }
464
    }
465
}
466

            
467
impl<'a> DiffResult<'a> {
468
    /// Construct a new DiffResult containing the provided string
469
    /// split into lines, and an expected post-transformation digests.
470
    fn from_str(s: &'a str, d_post: [u8; 32]) -> Self {
471
        // I'd like to use str::split_inclusive here, but that isn't stable yet
472
        // as of rust 1.48.
473

            
474
        let lines: Vec<_> = s.lines().collect();
475

            
476
        DiffResult { d_post, lines }
477
    }
478

            
479
    /// Return a new empty DiffResult with an expected
480
    /// post-transformation digests
481
    fn new(d_post: [u8; 32]) -> Self {
482
        DiffResult {
483
            d_post,
484
            lines: Vec::new(),
485
        }
486
    }
487

            
488
    /// Put every member of `lines` at the end of this DiffResult, in
489
    /// reverse order.
490
    fn push_reversed(&mut self, lines: &[&'a str]) {
491
        self.lines.extend(lines.iter().rev());
492
    }
493

            
494
    /// Remove the 1-indexed lines from `first` through `last` inclusive.
495
    ///
496
    /// This has to move elements around within the vector, and so it
497
    /// is potentially O(n) in its length.
498
    #[cfg(any(test, fuzzing, feature = "slow-diff-apply"))]
499
    fn remove_lines(&mut self, first: usize, last: usize) -> Result<()> {
500
        if first > self.lines.len() || last > self.lines.len() || first == 0 || last == 0 {
501
            Err(Error::CantApply("line out of range"))
502
        } else {
503
            let n_to_remove = last - first + 1;
504
            if last != self.lines.len() {
505
                self.lines[..].copy_within((last).., first - 1);
506
            }
507
            self.lines.truncate(self.lines.len() - n_to_remove);
508
            Ok(())
509
        }
510
    }
511

            
512
    /// Insert the provided `lines` so that they appear at 1-indexed
513
    /// position `pos`.
514
    ///
515
    /// This has to move elements around within the vector, and so it
516
    /// is potentially O(n) in its length.
517
    #[cfg(any(test, fuzzing, feature = "slow-diff-apply"))]
518
    fn insert_at(&mut self, pos: usize, lines: &[&'a str]) -> Result<()> {
519
        if pos > self.lines.len() + 1 || pos == 0 {
520
            Err(Error::CantApply("position out of range"))
521
        } else {
522
            let orig_len = self.lines.len();
523
            self.lines.resize(self.lines.len() + lines.len(), "");
524
            self.lines
525
                .copy_within(pos - 1..orig_len, pos - 1 + lines.len());
526
            self.lines[(pos - 1)..(pos + lines.len() - 1)].copy_from_slice(lines);
527
            Ok(())
528
        }
529
    }
530

            
531
    /// See whether the output of this diff matches the target digest.
532
    ///
533
    /// If not, return an error.
534
    pub fn check_digest(&self) -> Result<()> {
535
        use digest::Digest;
536
        use tor_llcrypto::d::Sha3_256;
537
        let mut d = Sha3_256::new();
538
        for line in &self.lines {
539
            d.update(line.as_bytes());
540
            d.update(b"\n");
541
        }
542
        if d.finalize() == self.d_post.into() {
543
            Ok(())
544
        } else {
545
            Err(Error::CantApply("Wrong digest after applying diff"))
546
        }
547
    }
548
}
549

            
550
impl<'a> Display for DiffResult<'a> {
551
    fn fmt(&self, f: &mut Formatter<'_>) -> std::result::Result<(), std::fmt::Error> {
552
        for elt in &self.lines {
553
            writeln!(f, "{}", elt)?;
554
        }
555
        Ok(())
556
    }
557
}
558

            
559
#[cfg(test)]
560
mod test {
561
    // @@ begin test lint list maintained by maint/add_warning @@
562
    #![allow(clippy::bool_assert_comparison)]
563
    #![allow(clippy::clone_on_copy)]
564
    #![allow(clippy::dbg_macro)]
565
    #![allow(clippy::print_stderr)]
566
    #![allow(clippy::print_stdout)]
567
    #![allow(clippy::single_char_pattern)]
568
    #![allow(clippy::unwrap_used)]
569
    #![allow(clippy::unchecked_duration_subtraction)]
570
    #![allow(clippy::useless_vec)]
571
    #![allow(clippy::needless_pass_by_value)]
572
    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
573
    use super::*;
574

            
575
    #[test]
576
    fn remove() -> Result<()> {
577
        let example = DiffResult::from_str("1\n2\n3\n4\n5\n6\n7\n8\n9\n", [0; 32]);
578

            
579
        let mut d = example.clone();
580
        d.remove_lines(5, 7)?;
581
        assert_eq!(d.to_string(), "1\n2\n3\n4\n8\n9\n");
582

            
583
        let mut d = example.clone();
584
        d.remove_lines(1, 9)?;
585
        assert_eq!(d.to_string(), "");
586

            
587
        let mut d = example.clone();
588
        d.remove_lines(1, 1)?;
589
        assert_eq!(d.to_string(), "2\n3\n4\n5\n6\n7\n8\n9\n");
590

            
591
        let mut d = example.clone();
592
        d.remove_lines(6, 9)?;
593
        assert_eq!(d.to_string(), "1\n2\n3\n4\n5\n");
594

            
595
        let mut d = example.clone();
596
        assert!(d.remove_lines(6, 10).is_err());
597
        assert!(d.remove_lines(0, 1).is_err());
598
        assert_eq!(d.to_string(), "1\n2\n3\n4\n5\n6\n7\n8\n9\n");
599

            
600
        Ok(())
601
    }
602

            
603
    #[test]
604
    fn insert() -> Result<()> {
605
        let example = DiffResult::from_str("1\n2\n3\n4\n5\n", [0; 32]);
606
        let mut d = example.clone();
607
        d.insert_at(3, &["hello", "world"])?;
608
        assert_eq!(d.to_string(), "1\n2\nhello\nworld\n3\n4\n5\n");
609

            
610
        let mut d = example.clone();
611
        d.insert_at(6, &["hello", "world"])?;
612
        assert_eq!(d.to_string(), "1\n2\n3\n4\n5\nhello\nworld\n");
613

            
614
        let mut d = example.clone();
615
        assert!(d.insert_at(0, &["hello", "world"]).is_err());
616
        assert!(d.insert_at(7, &["hello", "world"]).is_err());
617
        Ok(())
618
    }
619

            
620
    #[test]
621
    fn push_reversed() {
622
        let mut d = DiffResult::new([0; 32]);
623
        d.push_reversed(&["7", "8", "9"]);
624
        assert_eq!(d.to_string(), "9\n8\n7\n");
625
        d.push_reversed(&["world", "hello", ""]);
626
        assert_eq!(d.to_string(), "9\n8\n7\n\nhello\nworld\n");
627
    }
628

            
629
    #[test]
630
    fn apply_command_simple() {
631
        let example = DiffResult::from_str("a\nb\nc\nd\ne\nf\n", [0; 32]);
632

            
633
        let mut d = example.clone();
634
        assert_eq!(d.to_string(), "a\nb\nc\nd\ne\nf\n".to_string());
635
        assert!(DiffCommand::DeleteToEnd { low: 5 }.apply_to(&mut d).is_ok());
636
        assert_eq!(d.to_string(), "a\nb\nc\nd\n".to_string());
637

            
638
        let mut d = example.clone();
639
        assert!(DiffCommand::Delete { low: 3, high: 5 }
640
            .apply_to(&mut d)
641
            .is_ok());
642
        assert_eq!(d.to_string(), "a\nb\nf\n".to_string());
643

            
644
        let mut d = example.clone();
645
        assert!(DiffCommand::Replace {
646
            low: 3,
647
            high: 5,
648
            lines: vec!["hello", "world"]
649
        }
650
        .apply_to(&mut d)
651
        .is_ok());
652
        assert_eq!(d.to_string(), "a\nb\nhello\nworld\nf\n".to_string());
653

            
654
        let mut d = example.clone();
655
        assert!(DiffCommand::Insert {
656
            pos: 3,
657
            lines: vec!["hello", "world"]
658
        }
659
        .apply_to(&mut d)
660
        .is_ok());
661
        assert_eq!(
662
            d.to_string(),
663
            "a\nb\nc\nhello\nworld\nd\ne\nf\n".to_string()
664
        );
665
    }
666

            
667
    #[test]
668
    fn parse_command() -> Result<()> {
669
        fn parse(s: &str) -> Result<DiffCommand<'_>> {
670
            let mut iter = s.lines();
671
            let cmd = DiffCommand::from_line_iterator(&mut iter)?;
672
            let cmd2 = DiffCommand::from_line_iterator(&mut iter)?;
673
            if cmd2.is_some() {
674
                panic!("Unexpected second command");
675
            }
676
            Ok(cmd.unwrap())
677
        }
678

            
679
        fn parse_err(s: &str) {
680
            let mut iter = s.lines();
681
            let cmd = DiffCommand::from_line_iterator(&mut iter);
682
            assert!(matches!(cmd, Err(Error::BadDiff(_))));
683
        }
684

            
685
        let p = parse("3,8d\n")?;
686
        assert!(matches!(p, DiffCommand::Delete { low: 3, high: 8 }));
687
        let p = parse("3d\n")?;
688
        assert!(matches!(p, DiffCommand::Delete { low: 3, high: 3 }));
689
        let p = parse("100,$d\n")?;
690
        assert!(matches!(p, DiffCommand::DeleteToEnd { low: 100 }));
691

            
692
        let p = parse("30,40c\nHello\nWorld\n.\n")?;
693
        assert!(matches!(
694
            p,
695
            DiffCommand::Replace {
696
                low: 30,
697
                high: 40,
698
                ..
699
            }
700
        ));
701
        assert_eq!(p.lines(), Some(&["Hello", "World"][..]));
702
        let p = parse("30c\nHello\nWorld\n.\n")?;
703
        assert!(matches!(
704
            p,
705
            DiffCommand::Replace {
706
                low: 30,
707
                high: 30,
708
                ..
709
            }
710
        ));
711
        assert_eq!(p.lines(), Some(&["Hello", "World"][..]));
712

            
713
        let p = parse("999a\nHello\nWorld\n.\n")?;
714
        assert!(matches!(p, DiffCommand::Insert { pos: 999, .. }));
715
        assert_eq!(p.lines(), Some(&["Hello", "World"][..]));
716
        let p = parse("0a\nHello\nWorld\n.\n")?;
717
        assert!(matches!(p, DiffCommand::Insert { pos: 0, .. }));
718
        assert_eq!(p.lines(), Some(&["Hello", "World"][..]));
719

            
720
        parse_err("hello world");
721
        parse_err("\n\n");
722
        parse_err("$,5d");
723
        parse_err("5,6,8d");
724
        parse_err("8,5d");
725
        parse_err("6");
726
        parse_err("d");
727
        parse_err("-10d");
728
        parse_err("4,$c\na\n.");
729
        parse_err("foo");
730
        parse_err("5,10p");
731
        parse_err("18446744073709551615a");
732
        parse_err("1,18446744073709551615d");
733

            
734
        Ok(())
735
    }
736

            
737
    #[test]
738
    fn apply_transformation() -> Result<()> {
739
        let example = DiffResult::from_str("1\n2\n3\n4\n5\n6\n7\n8\n9\n", [0; 32]);
740
        let empty = DiffResult::new([1; 32]);
741

            
742
        let mut inp = example.clone();
743
        let mut out = empty.clone();
744
        DiffCommand::DeleteToEnd { low: 5 }.apply_transformation(&mut inp, &mut out)?;
745
        assert_eq!(inp.to_string(), "1\n2\n3\n4\n");
746
        assert_eq!(out.to_string(), "");
747

            
748
        let mut inp = example.clone();
749
        let mut out = empty.clone();
750
        DiffCommand::DeleteToEnd { low: 9 }.apply_transformation(&mut inp, &mut out)?;
751
        assert_eq!(inp.to_string(), "1\n2\n3\n4\n5\n6\n7\n8\n");
752
        assert_eq!(out.to_string(), "");
753

            
754
        let mut inp = example.clone();
755
        let mut out = empty.clone();
756
        DiffCommand::Delete { low: 3, high: 5 }.apply_transformation(&mut inp, &mut out)?;
757
        assert_eq!(inp.to_string(), "1\n2\n");
758
        assert_eq!(out.to_string(), "9\n8\n7\n6\n");
759

            
760
        let mut inp = example.clone();
761
        let mut out = empty.clone();
762
        DiffCommand::Replace {
763
            low: 5,
764
            high: 6,
765
            lines: vec!["oh hey", "there"],
766
        }
767
        .apply_transformation(&mut inp, &mut out)?;
768
        assert_eq!(inp.to_string(), "1\n2\n3\n4\n");
769
        assert_eq!(out.to_string(), "9\n8\n7\nthere\noh hey\n");
770

            
771
        let mut inp = example.clone();
772
        let mut out = empty.clone();
773
        DiffCommand::Insert {
774
            pos: 3,
775
            lines: vec!["oh hey", "there"],
776
        }
777
        .apply_transformation(&mut inp, &mut out)?;
778
        assert_eq!(inp.to_string(), "1\n2\n3\n");
779
        assert_eq!(out.to_string(), "9\n8\n7\n6\n5\n4\nthere\noh hey\n");
780
        DiffCommand::Insert {
781
            pos: 0,
782
            lines: vec!["boom!"],
783
        }
784
        .apply_transformation(&mut inp, &mut out)?;
785
        assert_eq!(inp.to_string(), "");
786
        assert_eq!(
787
            out.to_string(),
788
            "9\n8\n7\n6\n5\n4\nthere\noh hey\n3\n2\n1\nboom!\n"
789
        );
790

            
791
        let mut inp = example.clone();
792
        let mut out = empty.clone();
793
        let r = DiffCommand::Delete {
794
            low: 100,
795
            high: 200,
796
        }
797
        .apply_transformation(&mut inp, &mut out);
798
        assert!(r.is_err());
799
        let r = DiffCommand::Delete { low: 5, high: 200 }.apply_transformation(&mut inp, &mut out);
800
        assert!(r.is_err());
801
        let r = DiffCommand::Delete { low: 0, high: 1 }.apply_transformation(&mut inp, &mut out);
802
        assert!(r.is_err());
803
        let r = DiffCommand::DeleteToEnd { low: 10 }.apply_transformation(&mut inp, &mut out);
804
        assert!(r.is_err());
805
        Ok(())
806
    }
807

            
808
    #[test]
809
    fn header() -> Result<()> {
810
        fn header_from(s: &str) -> Result<([u8; 32], [u8; 32])> {
811
            let mut iter = s.lines();
812
            parse_diff_header(&mut iter)
813
        }
814

            
815
        let (a,b) = header_from(
816
            "network-status-diff-version 1
817
hash B03DA3ACA1D3C1D083E3FF97873002416EBD81A058B406D5C5946EAB53A79663 F6789F35B6B3BA58BB23D29E53A8ED6CBB995543DBE075DD5671481C4BA677FB"
818
        )?;
819

            
820
        assert_eq!(
821
            &a[..],
822
            hex::decode("B03DA3ACA1D3C1D083E3FF97873002416EBD81A058B406D5C5946EAB53A79663")?
823
        );
824
        assert_eq!(
825
            &b[..],
826
            hex::decode("F6789F35B6B3BA58BB23D29E53A8ED6CBB995543DBE075DD5671481C4BA677FB")?
827
        );
828

            
829
        assert!(header_from("network-status-diff-version 2\n").is_err());
830
        assert!(header_from("").is_err());
831
        assert!(header_from("5,$d\n1,2d\n").is_err());
832
        assert!(header_from("network-status-diff-version 1\n").is_err());
833
        assert!(header_from(
834
            "network-status-diff-version 1
835
hash x y
836
5,5d"
837
        )
838
        .is_err());
839
        assert!(header_from(
840
            "network-status-diff-version 1
841
hash x y
842
5,5d"
843
        )
844
        .is_err());
845
        assert!(header_from(
846
            "network-status-diff-version 1
847
hash AA BB
848
5,5d"
849
        )
850
        .is_err());
851
        assert!(header_from(
852
            "network-status-diff-version 1
853
oh hello there
854
5,5d"
855
        )
856
        .is_err());
857
        assert!(header_from("network-status-diff-version 1
858
hash B03DA3ACA1D3C1D083E3FF97873002416EBD81A058B406D5C5946EAB53A79663 F6789F35B6B3BA58BB23D29E53A8ED6CBB995543DBE075DD5671481C4BA677FB extra").is_err());
859

            
860
        Ok(())
861
    }
862

            
863
    #[test]
864
    fn apply_simple() {
865
        let pre = include_str!("../testdata/consensus1.txt");
866
        let diff = include_str!("../testdata/diff1.txt");
867
        let post = include_str!("../testdata/consensus2.txt");
868

            
869
        let result = apply_diff_trivial(pre, diff).unwrap();
870
        assert!(result.check_digest().is_ok());
871
        assert_eq!(result.to_string(), post);
872
    }
873

            
874
    #[test]
875
    fn sort_order() -> Result<()> {
876
        fn cmds(s: &str) -> Result<Vec<DiffCommand<'_>>> {
877
            let mut out = Vec::new();
878
            for cmd in DiffCommandIter::new(s.lines()) {
879
                out.push(cmd?);
880
            }
881
            Ok(out)
882
        }
883

            
884
        let _ = cmds("6,9d\n5,5d\n")?;
885
        assert!(cmds("5,5d\n6,9d\n").is_err());
886
        assert!(cmds("5,5d\n6,6d\n").is_err());
887
        assert!(cmds("5,5d\n5,6d\n").is_err());
888

            
889
        Ok(())
890
    }
891
}