Skip to main content

tor_consdiff/
lib.rs

1#![cfg_attr(docsrs, feature(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#![allow(clippy::cognitive_complexity)] // See arti#2556
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#![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)] // This can reasonably be done for explicitness
40#![allow(clippy::uninlined_format_args)]
41#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945
42#![allow(clippy::result_large_err)] // temporary workaround for arti#587
43#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best
44#![allow(clippy::needless_lifetimes)] // See arti#1765
45#![allow(mismatched_lifetime_syntaxes)] // temporary workaround for arti#2060
46#![allow(clippy::collapsible_if)] // See arti#2342
47#![deny(clippy::unused_async)]
48#![deny(clippy::string_slice)] // See arti#2571
49#![allow(recursion_depth_exceeding_limit)] // arti#2715, rust/issues/159228
50//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
51
52// TODO: add to the list maintained by maint/add_warning once it's available on all crates
53#![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
68/// Result type used by this crate
69type Result<T> = std::result::Result<T, Error>;
70
71/// The keyword that identifies a directory signature line.
72// TODO: We probably want this in tor-netdoc.
73const DIRECTORY_SIGNATURE_KEYWORD: KeywordRef = KeywordRef::new_const("directory-signature");
74
75/// When hashing the signed part of the consensus, append this tail to the end.
76const CONSENSUS_SIGNED_SHA3_256_HASH_TAIL: &str = "directory-signature ";
77
78// Do not compile if we cannot safely convert a u32 into a usize.
79static_assertions::const_assert!(std::mem::size_of::<usize>() >= std::mem::size_of::<u32>());
80
81/// Generates a consensus diff.
82///
83/// This implementation is different from the one in CTor, because it uses a
84/// different algorithm, namely [`Algorithm::Myers`] from the [`imara_diff`]
85/// crate, which is more efficient than CTor in terms of runtime and about as
86/// equally efficient as CTor in output size.
87///
88/// The CTor implementation makes heavy use of the fact that the input is a
89/// valid consensus and that the routers in it are ordered.  This allows for
90/// some divide-and-conquer mechanisms and the cost of requiring more parsing.
91///
92/// Here, we only minimally parse the consensus, in order to only obtain the
93/// first `directory-signature` item and to cut everything including itself off
94/// from the input, as demanded by the specification.
95///
96/// All outputs of this function are guaranteed to work with this
97/// [`apply_diff()`] implementation as a check is performed before returning,
98/// because returning an unusable diff would be terrible.
99pub fn gen_cons_diff(
100    base: &str,
101    target: &str,
102    size_strictness: DiffSizeStrictness,
103) -> Result<String> {
104    // Throw away the signatures.
105    let (base_signed, _) = split_directory_signatures(base)?;
106    let base_lines = base_signed.chars().filter(|c| *c == '\n').count() + 1;
107
108    // Compute the hashes for the header.
109    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    // Compose the result with header.
118    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    // Ensure it is valid, refuse to emit an invalid diff.
144    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
157/// Splits `input` at the first `directory-signature`.
158fn 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    // Parse the consensus item by item until the first `directory-signature`.
163    loop {
164        // We only peek in order to get the proper byte offset.
165        // This is required because doing next() and breaking in the case of
166        // a `directory-signature` would then lead to `.byte_offset()` yielding
167        // the start of the second signature and not the start of the first one.
168        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                // Consume the just peeked item.
181                let _ = items.next();
182            }
183            None => {
184                // We are finished.
185                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
199/// Generates an input agnostic ed diff.
200///
201/// This function does the general logic of [`gen_cons_diff()`] but works in a
202/// document agnostic fashion.
203fn gen_ed_diff(base: &str, target: &str) -> std::result::Result<String, GenEdDiffError> {
204    let mut result = String::new();
205
206    // We use Myers' algorithm as benchmarks have shown that it provides an
207    // equal diff size as the ctor one while keeping an acceptable performance.
208    let input = InternedInput::new(base, target);
209    let mut diff = Diff::compute(Algorithm::Myers, &input);
210    diff.postprocess_lines(&input);
211
212    // Iterate through every a hunk, with a hunk being a block of changes.
213    let hunks = diff.hunks().collect::<Vec<_>>();
214    for hunk in hunks.into_iter().rev() {
215        // Format the header.
216        let hunk_type = HunkType::determine(&hunk);
217        match hunk_type {
218            // No need to do +1 because append is AFTER.
219            HunkType::Append => writeln!(result, "{}{hunk_type}", hunk.before.start)?,
220            HunkType::Delete | HunkType::Change => {
221                if hunk.before.start + 1 == hunk.before.end {
222                    // +1 because 1-indexed.
223                    writeln!(result, "{}{hunk_type}", hunk.before.start + 1)?;
224                } else {
225                    // +1 because 1-indexed; no need to do +1 on end because
226                    // the range is inclusive.
227                    writeln!(
228                        result,
229                        "{},{}{hunk_type}",
230                        hunk.before.start + 1,
231                        hunk.before.end
232                    )?;
233                }
234            }
235        }
236
237        // Format the body.
238        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                    // Check that all lines end with a Unix line ending.
250                    if line.ends_with("\r\n") || !line.ends_with("\n") {
251                        // +1 because 1-indexed.
252                        return Err(GenEdDiffError::MissingUnixLineEnding { lno: lno + 1 });
253                    }
254
255                    // Check for lines consisting of a single dot plus trailing
256                    // whitespace characters.  No need to bother about "\r\n",
257                    // because we checked that one above.  Although technically
258                    // lines such as `. \n` are possible and understood
259                    // as part of ed diffs, they are not legal in tor netdocs, and
260                    // we want to be more defensive here for now; if it becomes a
261                    // problem, we may remove it later.
262                    if line.trim_end() == "." {
263                        // +1 because 1-indexed.
264                        return Err(GenEdDiffError::ContainsDotLine { lno: lno + 1 });
265                    }
266
267                    // All lines are newline terminated, no need to use writeln!
268                    write!(result, "{line}")?;
269                }
270
271                // Write the terminating dot.
272                writeln!(result, ".")?;
273            }
274            HunkType::Delete => {}
275        }
276    }
277
278    Ok(result)
279}
280
281/// The operational type of the hunk.
282#[derive(Clone, Copy, Debug, derive_more::Display)]
283enum HunkType {
284    /// This is a pure appending.
285    #[display("a")]
286    Append,
287    /// This is a pure deletion.
288    #[display("d")]
289    Delete,
290    /// This is change with potential additions and deletions.
291    #[display("c")]
292    Change,
293}
294
295impl HunkType {
296    /// Determines the type of the hunk.
297    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
308/// Return true if `s` looks more like a consensus diff than some other kind
309/// of document.
310pub fn looks_like_diff(s: &str) -> bool {
311    s.starts_with("network-status-diff-version")
312}
313
314/// Apply a given diff to an input text, and return the result from applying
315/// that diff.
316///
317/// This is a slow version, for testing and correctness checking.  It uses
318/// an O(n) operation to apply diffs, and therefore runs in O(n^2) time.
319#[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
333/// Apply a given diff to an input text, and return the result from applying
334/// that diff.
335///
336/// If `check_digest_in` is provided, require the diff to say that it
337/// applies to a document with the provided digest.
338pub 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    // This actually counts newlines, and can be off-by-one, but that's okay.
347    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/// A degree of strictness to apply when checking the size of a diff versus
375/// the size of the associated consensus.
376#[derive(Clone, Copy, Debug)]
377#[non_exhaustive]
378pub enum DiffSizeStrictness {
379    /// Do not perform any checks.
380    None,
381
382    /// Check whether the diff is reasonable to apply to the input.
383    Apply,
384
385    /// Check whether the diff is reasonable to serve as a diff against the input.
386    ///
387    /// This is an even stricter version of [`DiffSizeStrictness::Apply`].
388    Generate,
389}
390
391impl DiffSizeStrictness {
392    /// Check whether a given diff is implausibly or uselessly large in comparison with
393    /// the input, and return an error if so.
394    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 we just generated a diff that isn't smaller than the consensus we started with,
408                // there is no point in serving it. It wouldn't save size.
409                if diff_bytes >= input_bytes {
410                    return Err(DiffTooLarge);
411                }
412
413                // Also, check whether the client would reject this diff when trying to apply it.
414                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
432/// Given a line iterator, check to make sure the first two lines are
433/// a valid diff header as specified in dir-spec.txt.
434fn 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/// A command that can appear in a diff.  Each command tells us to
459/// remove zero or more lines, and insert zero or more lines in their
460/// place.
461///
462/// Commands refer to lines by 1-indexed line number.
463#[derive(Clone, Debug)]
464enum DiffCommand<'a> {
465    /// Remove the lines from low through high, inclusive.
466    Delete {
467        /// The first line to remove
468        low: usize,
469        /// The last line to remove
470        high: usize,
471    },
472    /// Remove the lines from low through the end of the file, inclusive.
473    DeleteToEnd {
474        /// The first line to remove
475        low: usize,
476    },
477    /// Replace the lines from low through high, inclusive, with the
478    /// lines in 'lines'.
479    Replace {
480        /// The first line to replace
481        low: usize,
482        /// The last line to replace
483        high: usize,
484        /// The text to insert instead
485        lines: Vec<&'a str>,
486    },
487    /// Insert the provided 'lines' after the line with index 'pos'.
488    Insert {
489        /// The position after which to insert the text
490        pos: usize,
491        /// The text to insert
492        lines: Vec<&'a str>,
493    },
494}
495
496/// The result of applying one or more diff commands to an input string.
497///
498/// It refers to lines from the diff and the input by reference, to
499/// avoid copying.
500#[derive(Clone, Debug)]
501pub struct DiffResult<'a> {
502    /// An expected digest of the output, after it has been assembled.
503    d_post: [u8; 32],
504    /// The lines in the output.
505    lines: Vec<&'a str>,
506}
507
508/// A possible value for the end of a range.  It can be either a line number,
509/// or a dollar sign indicating "end of file".
510#[derive(Clone, Copy, Debug)]
511enum RangeEnd {
512    /// A line number in the file.
513    Num(NonZeroUsize),
514    /// A dollar sign, indicating "end of file" in a delete command.
515    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    /// Transform 'target' according to the this command.
535    ///
536    /// Because DiffResult internally uses a vector of line, this
537    /// implementation is potentially O(n) in the size of the input.
538    #[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                // This '+1' seems off, but it's what the spec says. I wonder
553                // if the spec is wrong.
554                target.insert_at(*pos + 1, lines)?;
555            }
556        };
557        Ok(())
558    }
559
560    /// Apply this command to 'input', moving lines into 'output'.
561    ///
562    /// This is a more efficient algorithm, but it requires that the
563    /// diff commands are sorted in reverse order by line
564    /// number. (Fortunately, the Tor ed diff format guarantees this.)
565    ///
566    /// Before calling this method, input and output must contain the
567    /// results of having applied the previous command in the diff.
568    /// (When no commands have been applied, input starts out as the
569    /// original text, and output starts out empty.)
570    ///
571    /// This method applies the command by copying unaffected lines
572    /// from the _end_ of input into output, adding any lines inserted
573    /// by this command, and finally deleting any affected lines from
574    /// input.
575    ///
576    /// We build the `output` value in reverse order, and then put it
577    /// back to normal before giving it to the user.
578    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                // Lines from `succ` onwards are unaffected.  Copy them.
586                output.push_reversed(subslice);
587            } else {
588                // Oops, dubious line number.
589                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            // These are the lines we're inserting.
597            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    /// Return the lines that we should add to the output
612    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    /// Return a mutable reference to the vector of lines we should
620    /// add to the output.
621    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    /// Return the (1-indexed) line number of the first line in the
629    /// input that comes _after_ this command, and is not affected by it.
630    ///
631    /// We use this line number to know which lines we should copy.
632    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    /// Return the (1-indexed) line number of the first line that we
641    /// should clear from the input when processing this command.
642    ///
643    /// This can be the same as following_lines(), if we shouldn't
644    /// actually remove any lines.
645    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    /// Return true if this is an Insert command.
655    fn is_insert(&self) -> bool {
656        matches!(self, Self::Insert { .. })
657    }
658
659    /// Extract a single command from a line iterator that yields lines
660    /// of the diffs.  Return None if we're at the end of the iterator.
661    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        // `command` can be of these forms: `Rc`, `Rd`, `N,$d`, and `Na`,
671        // where R is a range of form `N,N`, and where N is a line number.
672
673        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            // The 'c' and 'a' commands take a series of lines followed by a
721            // line containing a period.
722            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
735/// Iterator that wraps a line iterator and returns a sequence of
736/// `Result<DiffCommand>`.
737///
738/// This iterator forces the commands to affect the file in reverse order,
739/// so that we can use the O(n) algorithm for applying these diffs.
740struct DiffCommandIter<'a, I>
741where
742    I: Iterator<Item = &'a str>,
743{
744    /// The underlying iterator.
745    iter: I,
746
747    /// The 'first removed line' of the last-parsed command; used to ensure
748    /// that commands appear in reverse order.
749    last_cmd_first_removed: Option<usize>,
750}
751
752impl<'a, I> DiffCommandIter<'a, I>
753where
754    I: Iterator<Item = &'a str>,
755{
756    /// Construct a new DiffCommandIter wrapping `iter`.
757    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    /// Construct a new DiffResult containing the provided string
788    /// split into lines, and an expected post-transformation digest.
789    fn from_str(s: &'a str, d_post: [u8; 32]) -> Self {
790        // As per the [netdoc syntax], newlines should be discarded and ignored.
791        //
792        // [netdoc syntax]: https://spec.torproject.org/dir-spec/netdoc.html#netdoc-syntax
793        let lines: Vec<_> = s.lines().collect();
794
795        DiffResult { d_post, lines }
796    }
797
798    /// Return a new empty DiffResult with an expected
799    /// post-transformation digests
800    fn new(d_post: [u8; 32]) -> Self {
801        DiffResult {
802            d_post,
803            lines: Vec::new(),
804        }
805    }
806
807    /// Put every member of `lines` at the end of this DiffResult, in
808    /// reverse order.
809    fn push_reversed(&mut self, lines: &[&'a str]) {
810        self.lines.extend(lines.iter().rev());
811    }
812
813    /// Remove the 1-indexed lines from `first` through `last` inclusive.
814    ///
815    /// This has to move elements around within the vector, and so it
816    /// is potentially O(n) in its length.
817    #[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    /// Insert the provided `lines` so that they appear at 1-indexed
832    /// position `pos`.
833    ///
834    /// This has to move elements around within the vector, and so it
835    /// is potentially O(n) in its length.
836    #[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    /// See whether the output of this diff matches the target digest.
851    ///
852    /// If not, return an error.
853    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
878/// Count the number of newlines that appear in s.
879///
880/// This is potentially one less than the number of lines in s, if the final line is not terminated,
881///but that's okay for our uses here.
882fn count_nl(s: &str) -> usize {
883    s.bytes().filter(|b| *b == b'\n').count()
884}
885
886#[cfg(test)]
887mod test {
888    // @@ begin test lint list maintained by maint/add_warning @@
889    #![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)] // See arti#2571
901    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
902
903    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 for cons diff using a random word generator.
1241    #[test]
1242    fn cons_diff() {
1243        // cat /usr/share/dict/words | sort -R | head -n 20 | sed 's/^/"/g' | sed 's/$/",/g'
1244        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        // Also check for dot lines with trailing spaces.
1294        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        // A line starting with a dot and not ending in WS shall be fine though.
1301        let target = "foo\nbar\n.   foo\nbaz\nfoo\n";
1302        let _ = gen_ed_diff(base, target).unwrap();
1303
1304        // Use gen_cons_diff here to assume that it is actually applied.
1305        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}