1#![cfg_attr(docsrs, feature(doc_cfg))]
2#![doc = include_str!("../README.md")]
3#![allow(renamed_and_removed_lints)] #![allow(unknown_lints)] #![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#![allow(clippy::cognitive_complexity)] #![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#![warn(clippy::or_fun_call)]
28#![deny(clippy::print_stderr)]
29#![deny(clippy::print_stdout)]
30#![warn(clippy::rc_buffer)]
31#![deny(clippy::ref_option_ref)]
32#![warn(clippy::semicolon_if_nothing_returned)]
33#![warn(clippy::trait_duplication_in_bounds)]
34#![deny(clippy::unchecked_time_subtraction)]
35#![deny(clippy::unnecessary_wraps)]
36#![warn(clippy::unseparated_literal_suffix)]
37#![deny(clippy::unwrap_used)]
38#![deny(clippy::mod_module_files)]
39#![allow(clippy::let_unit_value)] #![allow(clippy::uninlined_format_args)]
41#![allow(clippy::significant_drop_in_scrutinee)] #![allow(clippy::result_large_err)] #![allow(clippy::needless_raw_string_hashes)] #![allow(clippy::needless_lifetimes)] #![allow(mismatched_lifetime_syntaxes)] #![allow(clippy::collapsible_if)] #![deny(clippy::unused_async)]
48#![deny(clippy::string_slice)] #![allow(recursion_depth_exceeding_limit)] #![warn(unnameable_types)]
54
55use std::fmt::{Display, Formatter, Write};
56use std::num::NonZeroUsize;
57use std::str::FromStr;
58
59mod err;
60use digest::Digest;
61pub use err::Error;
62use imara_diff::{Algorithm, Diff, Hunk, InternedInput};
63use tor_error::{internal, into_internal};
64use tor_netdoc::parse2::{ErrorProblem, ItemStream, KeywordRef, ParseError, ParseInput};
65
66use crate::err::GenEdDiffError;
67
68type Result<T> = std::result::Result<T, Error>;
70
71const DIRECTORY_SIGNATURE_KEYWORD: KeywordRef = KeywordRef::new_const("directory-signature");
74
75const CONSENSUS_SIGNED_SHA3_256_HASH_TAIL: &str = "directory-signature ";
77
78static_assertions::const_assert!(std::mem::size_of::<usize>() >= std::mem::size_of::<u32>());
80
81pub fn gen_cons_diff(
100 base: &str,
101 target: &str,
102 size_strictness: DiffSizeStrictness,
103) -> Result<String> {
104 let (base_signed, _) = split_directory_signatures(base)?;
106 let base_lines = base_signed.chars().filter(|c| *c == '\n').count() + 1;
107
108 let base_signed_hash = hex::encode_upper({
110 let mut h = tor_llcrypto::d::Sha3_256::new();
111 h.update(base_signed);
112 h.update(CONSENSUS_SIGNED_SHA3_256_HASH_TAIL);
113 h.finalize()
114 });
115 let target_hash = hex::encode_upper(tor_llcrypto::d::Sha3_256::digest(target.as_bytes()));
116
117 let ed_diff = gen_ed_diff(base_signed, target).map_err(|e| match e {
119 GenEdDiffError::MissingUnixLineEnding { lno } => Error::InvalidInput(ParseError::new(
120 ErrorProblem::OtherBadDocument("line does not end with '\\n'"),
121 "consdiff",
122 "",
123 lno,
124 None,
125 )),
126 GenEdDiffError::ContainsDotLine { lno } => Error::InvalidInput(ParseError::new(
127 ErrorProblem::OtherBadDocument("contains dotline"),
128 "consdiff",
129 "",
130 lno,
131 None,
132 )),
133 GenEdDiffError::Write(_) => internal!("string write was not infallible?").into(),
134 })?;
135
136 let result = format!(
137 "network-status-diff-version 1\n\
138 hash {base_signed_hash} {target_hash}\n\
139 {base_lines},$d\n\
140 {ed_diff}"
141 );
142
143 let check = match apply_diff(base, &result, None, size_strictness) {
145 Ok(v) => v,
146 Err(Error::DiffTooLarge) => return Err(Error::DiffTooLarge),
147 Err(e) => return Err(into_internal!("unable to apply generated diff")(e).into()),
148 };
149
150 if check.to_string() != target {
151 Err(internal!("result does not match?"))?;
152 }
153
154 Ok(result)
155}
156
157fn split_directory_signatures(input: &str) -> Result<(&str, &str)> {
159 let parse_input = ParseInput::new(input, "");
160 let mut items = ItemStream::new(&parse_input);
161
162 loop {
164 let item = items
169 .peek_keyword()
170 .map_err(|e| ParseError::new(e, "consdiff", "", items.lno_for_error(), None))?;
171
172 match item {
173 Some(DIRECTORY_SIGNATURE_KEYWORD) => {
174 let offset = items.byte_position();
175 return Ok(input
176 .split_at_checked(offset)
177 .ok_or_else(|| internal!("Calculated an invalid offset"))?);
178 }
179 Some(_) => {
180 let _ = items.next();
182 }
183 None => {
184 return Err(Error::InvalidInput(ParseError::new(
186 ErrorProblem::MissingItem {
187 keyword: DIRECTORY_SIGNATURE_KEYWORD.as_str(),
188 },
189 "consdiff",
190 "",
191 items.lno_for_error(),
192 None,
193 )));
194 }
195 }
196 }
197}
198
199fn gen_ed_diff(base: &str, target: &str) -> std::result::Result<String, GenEdDiffError> {
204 let mut result = String::new();
205
206 let input = InternedInput::new(base, target);
209 let mut diff = Diff::compute(Algorithm::Myers, &input);
210 diff.postprocess_lines(&input);
211
212 let hunks = diff.hunks().collect::<Vec<_>>();
214 for hunk in hunks.into_iter().rev() {
215 let hunk_type = HunkType::determine(&hunk);
217 match hunk_type {
218 HunkType::Append => writeln!(result, "{}{hunk_type}", hunk.before.start)?,
220 HunkType::Delete | HunkType::Change => {
221 if hunk.before.start + 1 == hunk.before.end {
222 writeln!(result, "{}{hunk_type}", hunk.before.start + 1)?;
224 } else {
225 writeln!(
228 result,
229 "{},{}{hunk_type}",
230 hunk.before.start + 1,
231 hunk.before.end
232 )?;
233 }
234 }
235 }
236
237 match hunk_type {
239 HunkType::Append | HunkType::Change => {
240 let range = (hunk.after.start)..(hunk.after.end);
241 let tlines = range
242 .map(|idx| {
243 let idx = usize::try_from(idx).expect("32-bit static assertion violated?");
244 input.interner[input.after[idx]]
245 })
246 .collect::<Vec<_>>();
247
248 for (lno, line) in tlines.iter().copied().enumerate() {
249 if line.ends_with("\r\n") || !line.ends_with("\n") {
251 return Err(GenEdDiffError::MissingUnixLineEnding { lno: lno + 1 });
253 }
254
255 if line.trim_end() == "." {
263 return Err(GenEdDiffError::ContainsDotLine { lno: lno + 1 });
265 }
266
267 write!(result, "{line}")?;
269 }
270
271 writeln!(result, ".")?;
273 }
274 HunkType::Delete => {}
275 }
276 }
277
278 Ok(result)
279}
280
281#[derive(Clone, Copy, Debug, derive_more::Display)]
283enum HunkType {
284 #[display("a")]
286 Append,
287 #[display("d")]
289 Delete,
290 #[display("c")]
292 Change,
293}
294
295impl HunkType {
296 fn determine(hunk: &Hunk) -> Self {
298 if hunk.is_pure_insertion() {
299 Self::Append
300 } else if hunk.is_pure_removal() {
301 Self::Delete
302 } else {
303 Self::Change
304 }
305 }
306}
307
308pub fn looks_like_diff(s: &str) -> bool {
311 s.starts_with("network-status-diff-version")
312}
313
314#[cfg(any(test, feature = "slow-diff-apply"))]
320pub fn apply_diff_trivial<'a>(input: &'a str, diff: &'a str) -> Result<DiffResult<'a>> {
321 let mut diff_lines = diff.lines();
322 let (_, d2) = parse_diff_header(&mut diff_lines)?;
323
324 let mut diffable = DiffResult::from_str(input, d2);
325
326 for command in DiffCommandIter::new(diff_lines) {
327 command?.apply_to(&mut diffable)?;
328 }
329
330 Ok(diffable)
331}
332
333pub fn apply_diff<'a>(
339 input: &'a str,
340 diff: &'a str,
341 check_digest_in: Option<[u8; 32]>,
342 size_strictness: DiffSizeStrictness,
343) -> Result<DiffResult<'a>> {
344 let input_bytes = input.len();
345 let diff_bytes = diff.len();
346 let diff_lines = count_nl(diff);
348
349 let mut input = DiffResult::from_str(input, [0; 32]);
350 let input_lines = input.lines.len();
351
352 size_strictness.check(input_bytes, input_lines, diff_bytes, diff_lines)?;
353
354 let mut diff_lines = diff.lines();
355 let (d1, d2) = parse_diff_header(&mut diff_lines)?;
356 if let Some(d_want) = check_digest_in {
357 if d1 != d_want {
358 return Err(Error::CantApply("listed digest does not match document"));
359 }
360 }
361
362 let mut output = DiffResult::new(d2);
363
364 for command in DiffCommandIter::new(diff_lines) {
365 command?.apply_transformation(&mut input, &mut output)?;
366 }
367
368 output.push_reversed(&input.lines[..]);
369
370 output.lines.reverse();
371 Ok(output)
372}
373
374#[derive(Clone, Copy, Debug)]
377#[non_exhaustive]
378pub enum DiffSizeStrictness {
379 None,
381
382 Apply,
384
385 Generate,
389}
390
391impl DiffSizeStrictness {
392 fn check(
395 &self,
396 input_bytes: usize,
397 input_lines: usize,
398 diff_bytes: usize,
399 diff_lines: usize,
400 ) -> Result<()> {
401 use DiffSizeStrictness as S;
402 use Error::DiffTooLarge;
403
404 match self {
405 S::None => {}
406 S::Generate => {
407 if diff_bytes >= input_bytes {
410 return Err(DiffTooLarge);
411 }
412
413 S::Apply.check(input_bytes, input_lines, diff_bytes, diff_lines)?;
415 }
416 S::Apply => {
417 const BYTE_THRESHOLD: usize = 64 * 1024;
418 const LINE_THRESHOLD: usize = 1024;
419 if diff_bytes >= BYTE_THRESHOLD && diff_bytes >= input_bytes.saturating_mul(2) {
420 return Err(DiffTooLarge);
421 }
422 if diff_lines >= LINE_THRESHOLD && diff_lines >= input_lines.saturating_mul(3) {
423 return Err(DiffTooLarge);
424 }
425 }
426 }
427
428 Ok(())
429 }
430}
431
432fn parse_diff_header<'a, I>(iter: &mut I) -> Result<([u8; 32], [u8; 32])>
435where
436 I: Iterator<Item = &'a str>,
437{
438 let line1 = iter.next();
439 if line1 != Some("network-status-diff-version 1") {
440 return Err(Error::BadDiff("unrecognized or missing header"));
441 }
442 let line2 = iter.next().ok_or(Error::BadDiff("header truncated"))?;
443 if !line2.starts_with("hash ") {
444 return Err(Error::BadDiff("missing 'hash' line"));
445 }
446 let elts: Vec<_> = line2.split_ascii_whitespace().collect();
447 if elts.len() != 3 {
448 return Err(Error::BadDiff("invalid 'hash' line"));
449 }
450 let d1 = hex::decode(elts[1])?;
451 let d2 = hex::decode(elts[2])?;
452 match (d1.try_into(), d2.try_into()) {
453 (Ok(a), Ok(b)) => Ok((a, b)),
454 _ => Err(Error::BadDiff("wrong digest lengths on 'hash' line")),
455 }
456}
457
458#[derive(Clone, Debug)]
464enum DiffCommand<'a> {
465 Delete {
467 low: usize,
469 high: usize,
471 },
472 DeleteToEnd {
474 low: usize,
476 },
477 Replace {
480 low: usize,
482 high: usize,
484 lines: Vec<&'a str>,
486 },
487 Insert {
489 pos: usize,
491 lines: Vec<&'a str>,
493 },
494}
495
496#[derive(Clone, Debug)]
501pub struct DiffResult<'a> {
502 d_post: [u8; 32],
504 lines: Vec<&'a str>,
506}
507
508#[derive(Clone, Copy, Debug)]
511enum RangeEnd {
512 Num(NonZeroUsize),
514 DollarSign,
516}
517
518impl FromStr for RangeEnd {
519 type Err = Error;
520 fn from_str(s: &str) -> Result<RangeEnd> {
521 if s == "$" {
522 Ok(RangeEnd::DollarSign)
523 } else {
524 let v: NonZeroUsize = s.parse()?;
525 if v.get() == usize::MAX {
526 return Err(Error::BadDiff("range cannot end at usize::MAX"));
527 }
528 Ok(RangeEnd::Num(v))
529 }
530 }
531}
532
533impl<'a> DiffCommand<'a> {
534 #[cfg(any(test, feature = "slow-diff-apply"))]
539 fn apply_to(&self, target: &mut DiffResult<'a>) -> Result<()> {
540 match self {
541 Self::Delete { low, high } => {
542 target.remove_lines(*low, *high)?;
543 }
544 Self::DeleteToEnd { low } => {
545 target.remove_lines(*low, target.lines.len())?;
546 }
547 Self::Replace { low, high, lines } => {
548 target.remove_lines(*low, *high)?;
549 target.insert_at(*low, lines)?;
550 }
551 Self::Insert { pos, lines } => {
552 target.insert_at(*pos + 1, lines)?;
555 }
556 };
557 Ok(())
558 }
559
560 fn apply_transformation(
579 &self,
580 input: &mut DiffResult<'a>,
581 output: &mut DiffResult<'a>,
582 ) -> Result<()> {
583 if let Some(succ) = self.following_lines() {
584 if let Some(subslice) = input.lines.get(succ - 1..) {
585 output.push_reversed(subslice);
587 } else {
588 return Err(Error::CantApply(
590 "ending line number didn't correspond to document",
591 ));
592 }
593 }
594
595 if let Some(lines) = self.lines() {
596 output.push_reversed(lines);
598 }
599
600 let remove = self.first_removed_line();
601 if remove == 0 || (!self.is_insert() && remove > input.lines.len()) {
602 return Err(Error::CantApply(
603 "starting line number didn't correspond to document",
604 ));
605 }
606 input.lines.truncate(remove - 1);
607
608 Ok(())
609 }
610
611 fn lines(&self) -> Option<&[&'a str]> {
613 match self {
614 Self::Replace { lines, .. } | Self::Insert { lines, .. } => Some(lines.as_slice()),
615 _ => None,
616 }
617 }
618
619 fn linebuf_mut(&mut self) -> Option<&mut Vec<&'a str>> {
622 match self {
623 Self::Replace { lines, .. } | Self::Insert { lines, .. } => Some(lines),
624 _ => None,
625 }
626 }
627
628 fn following_lines(&self) -> Option<usize> {
633 match self {
634 Self::Delete { high, .. } | Self::Replace { high, .. } => Some(high + 1),
635 Self::DeleteToEnd { .. } => None,
636 Self::Insert { pos, .. } => Some(pos + 1),
637 }
638 }
639
640 fn first_removed_line(&self) -> usize {
646 match self {
647 Self::Delete { low, .. } => *low,
648 Self::DeleteToEnd { low } => *low,
649 Self::Replace { low, .. } => *low,
650 Self::Insert { pos, .. } => *pos + 1,
651 }
652 }
653
654 fn is_insert(&self) -> bool {
656 matches!(self, Self::Insert { .. })
657 }
658
659 fn from_line_iterator<I>(iter: &mut I) -> Result<Option<Self>>
662 where
663 I: Iterator<Item = &'a str>,
664 {
665 let command = match iter.next() {
666 Some(s) => s,
667 None => return Ok(None),
668 };
669
670 if command.len() < 2 || !command.is_ascii() {
674 return Err(Error::BadDiff("command too short"));
675 }
676
677 let (range, command) = command.split_at(command.len() - 1);
678 let (low, high) = if let Some((lo, hi)) = range.split_once(',') {
679 (lo.parse::<usize>()?, Some(hi.parse::<RangeEnd>()?))
680 } else {
681 (range.parse::<usize>()?, None)
682 };
683
684 if low == usize::MAX {
685 return Err(Error::BadDiff("range cannot begin at usize::MAX"));
686 }
687
688 match (low, high) {
689 (lo, Some(RangeEnd::Num(hi))) if lo > hi.into() => {
690 return Err(Error::BadDiff("mis-ordered lines in range"));
691 }
692 (_, _) => (),
693 }
694
695 let mut cmd = match (command, low, high) {
696 ("d", low, None) => Self::Delete { low, high: low },
697 ("d", low, Some(RangeEnd::Num(high))) => Self::Delete {
698 low,
699 high: high.into(),
700 },
701 ("d", low, Some(RangeEnd::DollarSign)) => Self::DeleteToEnd { low },
702 ("c", low, None) => Self::Replace {
703 low,
704 high: low,
705 lines: Vec::new(),
706 },
707 ("c", low, Some(RangeEnd::Num(high))) => Self::Replace {
708 low,
709 high: high.into(),
710 lines: Vec::new(),
711 },
712 ("a", low, None) => Self::Insert {
713 pos: low,
714 lines: Vec::new(),
715 },
716 (_, _, _) => return Err(Error::BadDiff("can't parse command line")),
717 };
718
719 if let Some(ref mut linebuf) = cmd.linebuf_mut() {
720 loop {
723 match iter.next() {
724 None => return Err(Error::BadDiff("unterminated block to insert")),
725 Some(".") => break,
726 Some(line) => linebuf.push(line),
727 }
728 }
729 }
730
731 Ok(Some(cmd))
732 }
733}
734
735struct DiffCommandIter<'a, I>
741where
742 I: Iterator<Item = &'a str>,
743{
744 iter: I,
746
747 last_cmd_first_removed: Option<usize>,
750}
751
752impl<'a, I> DiffCommandIter<'a, I>
753where
754 I: Iterator<Item = &'a str>,
755{
756 fn new(iter: I) -> Self {
758 DiffCommandIter {
759 iter,
760 last_cmd_first_removed: None,
761 }
762 }
763}
764
765impl<'a, I> Iterator for DiffCommandIter<'a, I>
766where
767 I: Iterator<Item = &'a str>,
768{
769 type Item = Result<DiffCommand<'a>>;
770 fn next(&mut self) -> Option<Result<DiffCommand<'a>>> {
771 match DiffCommand::from_line_iterator(&mut self.iter) {
772 Err(e) => Some(Err(e)),
773 Ok(None) => None,
774 Ok(Some(c)) => match (self.last_cmd_first_removed, c.following_lines()) {
775 (Some(_), None) => Some(Err(Error::BadDiff("misordered commands"))),
776 (Some(a), Some(b)) if a < b => Some(Err(Error::BadDiff("misordered commands"))),
777 (_, _) => {
778 self.last_cmd_first_removed = Some(c.first_removed_line());
779 Some(Ok(c))
780 }
781 },
782 }
783 }
784}
785
786impl<'a> DiffResult<'a> {
787 fn from_str(s: &'a str, d_post: [u8; 32]) -> Self {
790 let lines: Vec<_> = s.lines().collect();
794
795 DiffResult { d_post, lines }
796 }
797
798 fn new(d_post: [u8; 32]) -> Self {
801 DiffResult {
802 d_post,
803 lines: Vec::new(),
804 }
805 }
806
807 fn push_reversed(&mut self, lines: &[&'a str]) {
810 self.lines.extend(lines.iter().rev());
811 }
812
813 #[cfg(any(test, feature = "slow-diff-apply"))]
818 fn remove_lines(&mut self, first: usize, last: usize) -> Result<()> {
819 if first > self.lines.len() || last > self.lines.len() || first == 0 || last == 0 {
820 Err(Error::CantApply("line out of range"))
821 } else {
822 let n_to_remove = last - first + 1;
823 if last != self.lines.len() {
824 self.lines[..].copy_within((last).., first - 1);
825 }
826 self.lines.truncate(self.lines.len() - n_to_remove);
827 Ok(())
828 }
829 }
830
831 #[cfg(any(test, feature = "slow-diff-apply"))]
837 fn insert_at(&mut self, pos: usize, lines: &[&'a str]) -> Result<()> {
838 if pos > self.lines.len() + 1 || pos == 0 {
839 Err(Error::CantApply("position out of range"))
840 } else {
841 let orig_len = self.lines.len();
842 self.lines.resize(self.lines.len() + lines.len(), "");
843 self.lines
844 .copy_within(pos - 1..orig_len, pos - 1 + lines.len());
845 self.lines[(pos - 1)..(pos + lines.len() - 1)].copy_from_slice(lines);
846 Ok(())
847 }
848 }
849
850 pub fn check_digest(&self) -> Result<()> {
854 use digest::Digest;
855 use tor_llcrypto::d::Sha3_256;
856 let mut d = Sha3_256::new();
857 for line in &self.lines {
858 d.update(line.as_bytes());
859 d.update(b"\n");
860 }
861 if d.finalize() == self.d_post {
862 Ok(())
863 } else {
864 Err(Error::CantApply("Wrong digest after applying diff"))
865 }
866 }
867}
868
869impl<'a> Display for DiffResult<'a> {
870 fn fmt(&self, f: &mut Formatter<'_>) -> std::result::Result<(), std::fmt::Error> {
871 for elt in &self.lines {
872 writeln!(f, "{}", elt)?;
873 }
874 Ok(())
875 }
876}
877
878fn count_nl(s: &str) -> usize {
883 s.bytes().filter(|b| *b == b'\n').count()
884}
885
886#[cfg(test)]
887mod test {
888 #![allow(clippy::bool_assert_comparison)]
890 #![allow(clippy::clone_on_copy)]
891 #![allow(clippy::dbg_macro)]
892 #![allow(clippy::mixed_attributes_style)]
893 #![allow(clippy::print_stderr)]
894 #![allow(clippy::print_stdout)]
895 #![allow(clippy::single_char_pattern)]
896 #![allow(clippy::unwrap_used)]
897 #![allow(clippy::unchecked_time_subtraction)]
898 #![allow(clippy::useless_vec)]
899 #![allow(clippy::needless_pass_by_value)]
900 #![allow(clippy::string_slice)] use rand::seq::IndexedRandom;
904 use tor_basic_utils::test_rng::testing_rng;
905
906 use super::DiffSizeStrictness as DSS;
907 use super::*;
908
909 #[test]
910 fn remove() -> Result<()> {
911 let example = DiffResult::from_str("1\n2\n3\n4\n5\n6\n7\n8\n9\n", [0; 32]);
912
913 let mut d = example.clone();
914 d.remove_lines(5, 7)?;
915 assert_eq!(d.to_string(), "1\n2\n3\n4\n8\n9\n");
916
917 let mut d = example.clone();
918 d.remove_lines(1, 9)?;
919 assert_eq!(d.to_string(), "");
920
921 let mut d = example.clone();
922 d.remove_lines(1, 1)?;
923 assert_eq!(d.to_string(), "2\n3\n4\n5\n6\n7\n8\n9\n");
924
925 let mut d = example.clone();
926 d.remove_lines(6, 9)?;
927 assert_eq!(d.to_string(), "1\n2\n3\n4\n5\n");
928
929 let mut d = example.clone();
930 assert!(d.remove_lines(6, 10).is_err());
931 assert!(d.remove_lines(0, 1).is_err());
932 assert_eq!(d.to_string(), "1\n2\n3\n4\n5\n6\n7\n8\n9\n");
933
934 Ok(())
935 }
936
937 #[test]
938 fn insert() -> Result<()> {
939 let example = DiffResult::from_str("1\n2\n3\n4\n5\n", [0; 32]);
940 let mut d = example.clone();
941 d.insert_at(3, &["hello", "world"])?;
942 assert_eq!(d.to_string(), "1\n2\nhello\nworld\n3\n4\n5\n");
943
944 let mut d = example.clone();
945 d.insert_at(6, &["hello", "world"])?;
946 assert_eq!(d.to_string(), "1\n2\n3\n4\n5\nhello\nworld\n");
947
948 let mut d = example.clone();
949 assert!(d.insert_at(0, &["hello", "world"]).is_err());
950 assert!(d.insert_at(7, &["hello", "world"]).is_err());
951 Ok(())
952 }
953
954 #[test]
955 fn push_reversed() {
956 let mut d = DiffResult::new([0; 32]);
957 d.push_reversed(&["7", "8", "9"]);
958 assert_eq!(d.to_string(), "9\n8\n7\n");
959 d.push_reversed(&["world", "hello", ""]);
960 assert_eq!(d.to_string(), "9\n8\n7\n\nhello\nworld\n");
961 }
962
963 #[test]
964 fn apply_command_simple() {
965 let example = DiffResult::from_str("a\nb\nc\nd\ne\nf\n", [0; 32]);
966
967 let mut d = example.clone();
968 assert_eq!(d.to_string(), "a\nb\nc\nd\ne\nf\n".to_string());
969 assert!(DiffCommand::DeleteToEnd { low: 5 }.apply_to(&mut d).is_ok());
970 assert_eq!(d.to_string(), "a\nb\nc\nd\n".to_string());
971
972 let mut d = example.clone();
973 assert!(
974 DiffCommand::Delete { low: 3, high: 5 }
975 .apply_to(&mut d)
976 .is_ok()
977 );
978 assert_eq!(d.to_string(), "a\nb\nf\n".to_string());
979
980 let mut d = example.clone();
981 assert!(
982 DiffCommand::Replace {
983 low: 3,
984 high: 5,
985 lines: vec!["hello", "world"]
986 }
987 .apply_to(&mut d)
988 .is_ok()
989 );
990 assert_eq!(d.to_string(), "a\nb\nhello\nworld\nf\n".to_string());
991
992 let mut d = example.clone();
993 assert!(
994 DiffCommand::Insert {
995 pos: 3,
996 lines: vec!["hello", "world"]
997 }
998 .apply_to(&mut d)
999 .is_ok()
1000 );
1001 assert_eq!(
1002 d.to_string(),
1003 "a\nb\nc\nhello\nworld\nd\ne\nf\n".to_string()
1004 );
1005 }
1006
1007 #[test]
1008 fn parse_command() -> Result<()> {
1009 fn parse(s: &str) -> Result<DiffCommand<'_>> {
1010 let mut iter = s.lines();
1011 let cmd = DiffCommand::from_line_iterator(&mut iter)?;
1012 let cmd2 = DiffCommand::from_line_iterator(&mut iter)?;
1013 if cmd2.is_some() {
1014 panic!("Unexpected second command");
1015 }
1016 Ok(cmd.unwrap())
1017 }
1018
1019 fn parse_err(s: &str) {
1020 let mut iter = s.lines();
1021 let cmd = DiffCommand::from_line_iterator(&mut iter);
1022 assert!(matches!(cmd, Err(Error::BadDiff(_))));
1023 }
1024
1025 let p = parse("3,8d\n")?;
1026 assert!(matches!(p, DiffCommand::Delete { low: 3, high: 8 }));
1027 let p = parse("3d\n")?;
1028 assert!(matches!(p, DiffCommand::Delete { low: 3, high: 3 }));
1029 let p = parse("100,$d\n")?;
1030 assert!(matches!(p, DiffCommand::DeleteToEnd { low: 100 }));
1031
1032 let p = parse("30,40c\nHello\nWorld\n.\n")?;
1033 assert!(matches!(
1034 p,
1035 DiffCommand::Replace {
1036 low: 30,
1037 high: 40,
1038 ..
1039 }
1040 ));
1041 assert_eq!(p.lines(), Some(&["Hello", "World"][..]));
1042 let p = parse("30c\nHello\nWorld\n.\n")?;
1043 assert!(matches!(
1044 p,
1045 DiffCommand::Replace {
1046 low: 30,
1047 high: 30,
1048 ..
1049 }
1050 ));
1051 assert_eq!(p.lines(), Some(&["Hello", "World"][..]));
1052
1053 let p = parse("999a\nHello\nWorld\n.\n")?;
1054 assert!(matches!(p, DiffCommand::Insert { pos: 999, .. }));
1055 assert_eq!(p.lines(), Some(&["Hello", "World"][..]));
1056 let p = parse("0a\nHello\nWorld\n.\n")?;
1057 assert!(matches!(p, DiffCommand::Insert { pos: 0, .. }));
1058 assert_eq!(p.lines(), Some(&["Hello", "World"][..]));
1059
1060 parse_err("hello world");
1061 parse_err("\n\n");
1062 parse_err("$,5d");
1063 parse_err("5,6,8d");
1064 parse_err("8,5d");
1065 parse_err("6");
1066 parse_err("d");
1067 parse_err("-10d");
1068 parse_err("4,$c\na\n.");
1069 parse_err("foo");
1070 parse_err("5,10p");
1071 parse_err("18446744073709551615a");
1072 parse_err("1,18446744073709551615d");
1073
1074 Ok(())
1075 }
1076
1077 #[test]
1078 fn apply_transformation() -> Result<()> {
1079 let example = DiffResult::from_str("1\n2\n3\n4\n5\n6\n7\n8\n9\n", [0; 32]);
1080 let empty = DiffResult::new([1; 32]);
1081
1082 let mut inp = example.clone();
1083 let mut out = empty.clone();
1084 DiffCommand::DeleteToEnd { low: 5 }.apply_transformation(&mut inp, &mut out)?;
1085 assert_eq!(inp.to_string(), "1\n2\n3\n4\n");
1086 assert_eq!(out.to_string(), "");
1087
1088 let mut inp = example.clone();
1089 let mut out = empty.clone();
1090 DiffCommand::DeleteToEnd { low: 9 }.apply_transformation(&mut inp, &mut out)?;
1091 assert_eq!(inp.to_string(), "1\n2\n3\n4\n5\n6\n7\n8\n");
1092 assert_eq!(out.to_string(), "");
1093
1094 let mut inp = example.clone();
1095 let mut out = empty.clone();
1096 DiffCommand::Delete { low: 3, high: 5 }.apply_transformation(&mut inp, &mut out)?;
1097 assert_eq!(inp.to_string(), "1\n2\n");
1098 assert_eq!(out.to_string(), "9\n8\n7\n6\n");
1099
1100 let mut inp = example.clone();
1101 let mut out = empty.clone();
1102 DiffCommand::Replace {
1103 low: 5,
1104 high: 6,
1105 lines: vec!["oh hey", "there"],
1106 }
1107 .apply_transformation(&mut inp, &mut out)?;
1108 assert_eq!(inp.to_string(), "1\n2\n3\n4\n");
1109 assert_eq!(out.to_string(), "9\n8\n7\nthere\noh hey\n");
1110
1111 let mut inp = example.clone();
1112 let mut out = empty.clone();
1113 DiffCommand::Insert {
1114 pos: 3,
1115 lines: vec!["oh hey", "there"],
1116 }
1117 .apply_transformation(&mut inp, &mut out)?;
1118 assert_eq!(inp.to_string(), "1\n2\n3\n");
1119 assert_eq!(out.to_string(), "9\n8\n7\n6\n5\n4\nthere\noh hey\n");
1120 DiffCommand::Insert {
1121 pos: 0,
1122 lines: vec!["boom!"],
1123 }
1124 .apply_transformation(&mut inp, &mut out)?;
1125 assert_eq!(inp.to_string(), "");
1126 assert_eq!(
1127 out.to_string(),
1128 "9\n8\n7\n6\n5\n4\nthere\noh hey\n3\n2\n1\nboom!\n"
1129 );
1130
1131 let mut inp = example.clone();
1132 let mut out = empty.clone();
1133 let r = DiffCommand::Delete {
1134 low: 100,
1135 high: 200,
1136 }
1137 .apply_transformation(&mut inp, &mut out);
1138 assert!(r.is_err());
1139 let r = DiffCommand::Delete { low: 5, high: 200 }.apply_transformation(&mut inp, &mut out);
1140 assert!(r.is_err());
1141 let r = DiffCommand::Delete { low: 0, high: 1 }.apply_transformation(&mut inp, &mut out);
1142 assert!(r.is_err());
1143 let r = DiffCommand::DeleteToEnd { low: 10 }.apply_transformation(&mut inp, &mut out);
1144 assert!(r.is_err());
1145 Ok(())
1146 }
1147
1148 #[test]
1149 fn header() -> Result<()> {
1150 fn header_from(s: &str) -> Result<([u8; 32], [u8; 32])> {
1151 let mut iter = s.lines();
1152 parse_diff_header(&mut iter)
1153 }
1154
1155 let (a,b) = header_from(
1156 "network-status-diff-version 1
1157hash B03DA3ACA1D3C1D083E3FF97873002416EBD81A058B406D5C5946EAB53A79663 F6789F35B6B3BA58BB23D29E53A8ED6CBB995543DBE075DD5671481C4BA677FB"
1158 )?;
1159
1160 assert_eq!(
1161 &a[..],
1162 hex::decode("B03DA3ACA1D3C1D083E3FF97873002416EBD81A058B406D5C5946EAB53A79663")?
1163 );
1164 assert_eq!(
1165 &b[..],
1166 hex::decode("F6789F35B6B3BA58BB23D29E53A8ED6CBB995543DBE075DD5671481C4BA677FB")?
1167 );
1168
1169 assert!(header_from("network-status-diff-version 2\n").is_err());
1170 assert!(header_from("").is_err());
1171 assert!(header_from("5,$d\n1,2d\n").is_err());
1172 assert!(header_from("network-status-diff-version 1\n").is_err());
1173 assert!(
1174 header_from(
1175 "network-status-diff-version 1
1176hash x y
11775,5d"
1178 )
1179 .is_err()
1180 );
1181 assert!(
1182 header_from(
1183 "network-status-diff-version 1
1184hash x y
11855,5d"
1186 )
1187 .is_err()
1188 );
1189 assert!(
1190 header_from(
1191 "network-status-diff-version 1
1192hash AA BB
11935,5d"
1194 )
1195 .is_err()
1196 );
1197 assert!(
1198 header_from(
1199 "network-status-diff-version 1
1200oh hello there
12015,5d"
1202 )
1203 .is_err()
1204 );
1205 assert!(header_from("network-status-diff-version 1
1206hash B03DA3ACA1D3C1D083E3FF97873002416EBD81A058B406D5C5946EAB53A79663 F6789F35B6B3BA58BB23D29E53A8ED6CBB995543DBE075DD5671481C4BA677FB extra").is_err());
1207
1208 Ok(())
1209 }
1210
1211 #[test]
1212 fn apply_simple() {
1213 let pre = include_str!("../testdata/consensus1.txt");
1214 let diff = include_str!("../testdata/diff1.txt");
1215 let post = include_str!("../testdata/consensus2.txt");
1216
1217 let result = apply_diff_trivial(pre, diff).unwrap();
1218 assert!(result.check_digest().is_ok());
1219 assert_eq!(result.to_string(), post);
1220 }
1221
1222 #[test]
1223 fn sort_order() -> Result<()> {
1224 fn cmds(s: &str) -> Result<Vec<DiffCommand<'_>>> {
1225 let mut out = Vec::new();
1226 for cmd in DiffCommandIter::new(s.lines()) {
1227 out.push(cmd?);
1228 }
1229 Ok(out)
1230 }
1231
1232 let _ = cmds("6,9d\n5,5d\n")?;
1233 assert!(cmds("5,5d\n6,9d\n").is_err());
1234 assert!(cmds("5,5d\n6,6d\n").is_err());
1235 assert!(cmds("5,5d\n5,6d\n").is_err());
1236
1237 Ok(())
1238 }
1239
1240 #[test]
1242 fn cons_diff() {
1243 const WORDS: &[&str] = &[
1245 "citole",
1246 "aflow",
1247 "plowfoot",
1248 "coom",
1249 "retape",
1250 "perish",
1251 "overstifle",
1252 "ramshackle",
1253 "Romeo",
1254 "alme",
1255 "expressivity",
1256 "Kieffer",
1257 "tobe",
1258 "pronucleus",
1259 "countersconce",
1260 "puli",
1261 "acupunctuate",
1262 "heterolysis",
1263 "unwattled",
1264 "bismerpund",
1265 ];
1266
1267 let rng = &mut testing_rng();
1268 let mut left = (0..1000)
1269 .map(|_| WORDS.choose(rng).unwrap().to_string() + "\n")
1270 .collect::<String>();
1271 left += "directory-signature foo bar\n";
1272 let mut right = (0..1015)
1273 .map(|_| WORDS.choose(rng).unwrap().to_string() + "\n")
1274 .collect::<String>();
1275 right += "directory-signature foo baz\n";
1276
1277 let diff = gen_cons_diff(&left, &right, DSS::None).unwrap();
1278 let check = apply_diff(&left, &diff, None, DSS::None)
1279 .unwrap()
1280 .to_string();
1281 assert_eq!(right, check);
1282 }
1283
1284 #[test]
1285 fn dot_line() {
1286 let base = "";
1287 let target = "foo\nbar\n.\nbaz\nfoo\n";
1288 assert_eq!(
1289 gen_ed_diff(base, target).unwrap_err(),
1290 GenEdDiffError::ContainsDotLine { lno: 3 },
1291 );
1292
1293 let target = "foo\nbar\n. \t \nbaz\nfoo\n";
1295 assert_eq!(
1296 gen_ed_diff(base, target).unwrap_err(),
1297 GenEdDiffError::ContainsDotLine { lno: 3 },
1298 );
1299
1300 let target = "foo\nbar\n. foo\nbaz\nfoo\n";
1302 let _ = gen_ed_diff(base, target).unwrap();
1303
1304 let base = "directory-signature foo baz\n";
1306 let target = ".foo bar\n. bar\ndirectory-signature foo baz\n";
1307 assert_eq!(
1308 gen_cons_diff(base, target, DSS::None).unwrap(),
1309 "network-status-diff-version 1\n\
1310 hash D8138DC27D9A66F5760058A6BCB71B755462B9D26B811828F124D036DE329A58 \
1311 506AC3A4407BC5305DD0D08FED3F09C2FE69847541F642A8FD13D3BD06FFE432\n\
1312 1,$d\n\
1313 0a\n\
1314 .foo bar\n\
1315 . bar\n\
1316 directory-signature foo baz\n\
1317 .\n"
1318 );
1319 }
1320
1321 #[test]
1322 fn missing_newline() {
1323 let base = "";
1324 let target = "foo\nbar\nbaz";
1325 assert_eq!(
1326 gen_ed_diff(base, target).unwrap_err(),
1327 GenEdDiffError::MissingUnixLineEnding { lno: 3 }
1328 );
1329 }
1330
1331 #[test]
1332 fn mixed_with_crlf() {
1333 let base = "";
1334 let target = "foo\r\nbar\r\nbaz\nhello\r\n";
1335 assert_eq!(
1336 gen_ed_diff(base, target).unwrap_err(),
1337 GenEdDiffError::MissingUnixLineEnding { lno: 1 }
1338 );
1339 }
1340}