#![cfg_attr(docsrs, feature(doc_cfg))]

#![doc = include_str!("../README.md")]

// @@ begin lint list maintained by maint/add_warning @@

#![allow(renamed_and_removed_lints)] // @@REMOVE_WHEN(ci_arti_stable)

#![allow(unknown_lints)] // @@REMOVE_WHEN(ci_arti_nightly)

#![warn(missing_docs)]

#![warn(noop_method_call)]

#![warn(unreachable_pub)]

#![warn(clippy::all)]

#![deny(clippy::await_holding_lock)]

#![deny(clippy::cargo_common_metadata)]

#![deny(clippy::cast_lossless)]

#![deny(clippy::checked_conversions)]

#![allow(clippy::cognitive_complexity)] // See arti#2556

#![deny(clippy::debug_assert_with_mut_call)]

#![deny(clippy::exhaustive_enums)]

#![deny(clippy::exhaustive_structs)]

#![deny(clippy::expl_impl_clone_on_copy)]

#![deny(clippy::fallible_impl_from)]

#![deny(clippy::implicit_clone)]

#![deny(clippy::large_stack_arrays)]

#![warn(clippy::manual_ok_or)]

#![deny(clippy::missing_docs_in_private_items)]

#![warn(clippy::needless_borrow)]

#![warn(clippy::needless_pass_by_value)]

#![warn(clippy::option_option)]

#![warn(clippy::or_fun_call)]

#![deny(clippy::print_stderr)]

#![deny(clippy::print_stdout)]

#![warn(clippy::rc_buffer)]

#![deny(clippy::ref_option_ref)]

#![warn(clippy::semicolon_if_nothing_returned)]

#![warn(clippy::trait_duplication_in_bounds)]

#![deny(clippy::unchecked_time_subtraction)]

#![deny(clippy::unnecessary_wraps)]

#![warn(clippy::unseparated_literal_suffix)]

#![deny(clippy::unwrap_used)]

#![deny(clippy::mod_module_files)]

#![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness

#![allow(clippy::uninlined_format_args)]

#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945

#![allow(clippy::result_large_err)] // temporary workaround for arti#587

#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best

#![allow(clippy::needless_lifetimes)] // See arti#1765

#![allow(mismatched_lifetime_syntaxes)] // temporary workaround for arti#2060

#![allow(clippy::collapsible_if)] // See arti#2342

#![deny(clippy::unused_async)]

#![deny(clippy::string_slice)] // See arti#2571

#![allow(recursion_depth_exceeding_limit)] // arti#2715, rust/issues/159228

//! <!-- @@ end lint list maintained by maint/add_warning @@ -->

use std::fmt::{Display, Formatter, Write};

use std::num::NonZeroUsize;

use std::str::FromStr;

mod err;

use digest::Digest;

pub use err::Error;

use imara_diff::{Algorithm, Diff, Hunk, InternedInput};

use tor_error::{internal, into_internal};

use tor_netdoc::parse2::{ErrorProblem, ItemStream, KeywordRef, ParseError, ParseInput};

use crate::err::GenEdDiffError;

/// Result type used by this crate

type Result<T> = std::result::Result<T, Error>;

/// The keyword that identifies a directory signature line.

// TODO: We probably want this in tor-netdoc.

const DIRECTORY_SIGNATURE_KEYWORD: KeywordRef = KeywordRef::new_const("directory-signature");

/// When hashing the signed part of the consensus, append this tail to the end.

const CONSENSUS_SIGNED_SHA3_256_HASH_TAIL: &str = "directory-signature ";

// Do not compile if we cannot safely convert a u32 into a usize.

static_assertions::const_assert!(std::mem::size_of::<usize>() >= std::mem::size_of::<u32>());

/// Generates a consensus diff.

///

/// This implementation is different from the one in CTor, because it uses a

/// different algorithm, namely [`Algorithm::Myers`] from the [`imara_diff`]

/// crate, which is more efficient than CTor in terms of runtime and about as

/// equally efficient as CTor in output size.

///

/// The CTor implementation makes heavy use of the fact that the input is a

/// valid consensus and that the routers in it are ordered.  This allows for

/// some divide-and-conquer mechanisms and the cost of requiring more parsing.

///

/// Here, we only minimally parse the consensus, in order to only obtain the

/// first `directory-signature` item and to cut everything including itself off

/// from the input, as demanded by the specification.

///

/// All outputs of this function are guaranteed to work with this

/// [`apply_diff()`] implementation as a check is performed before returning,

/// because returning an unusable diff would be terrible.

    // Throw away the signatures.

    // Compute the hashes for the header.

    });

    // Compose the result with header.

        "network-status-diff-version 1\n\

        hash {base_signed_hash} {target_hash}\n\

        {base_lines},$d\n\

        {ed_diff}"

    );

    // Ensure it is valid, refuse to emit an invalid diff.

    };

/// Splits `input` at the first `directory-signature`.

    // Parse the consensus item by item until the first `directory-signature`.

    loop {

        // We only peek in order to get the proper byte offset.

        // This is required because doing next() and breaking in the case of

        // a `directory-signature` would then lead to `.byte_offset()` yielding

        // the start of the second signature and not the start of the first one.

            }

            None => {

                // We are finished.

            }

        }

    }

/// Generates an input agnostic ed diff.

///

/// This function does the general logic of [`gen_cons_diff()`] but works in a

/// document agnostic fashion.

    // We use Myers' algorithm as benchmarks have shown that it provides an

    // equal diff size as the ctor one while keeping an acceptable performance.

    // Iterate through every a hunk, with a hunk being a block of changes.

        // Format the header.

            // No need to do +1 because append is AFTER.

            HunkType::Delete | HunkType::Change => {

                    // +1 because 1-indexed.

                } else {

                    // +1 because 1-indexed; no need to do +1 on end because

                    // the range is inclusive.

                        "{},{}{hunk_type}",

                        hunk.before.end

                }

            }

        }

        // Format the body.

            HunkType::Append | HunkType::Change => {

                    // Check that all lines end with a Unix line ending.

                        // +1 because 1-indexed.

                    // Check for lines consisting of a single dot plus trailing

                    // whitespace characters.  No need to bother about "\r\n",

                    // because we checked that one above.  Although technically

                    // lines such as `. \n` are possible and understood

                    // as part of ed diffs, they are not legal in tor netdocs, and

                    // we want to be more defensive here for now; if it becomes a

                    // problem, we may remove it later.

                        // +1 because 1-indexed.

                    // All lines are newline terminated, no need to use writeln!

                }

                // Write the terminating dot.

            }

        }

    }

/// The operational type of the hunk.

#[derive(Clone, Copy, Debug, derive_more::Display)]

enum HunkType {

    /// This is a pure appending.

    #[display("a")]

    Append,

    /// This is a pure deletion.

    #[display("d")]

    Delete,

    /// This is change with potential additions and deletions.

    #[display("c")]

    Change,

}

impl HunkType {

    /// Determines the type of the hunk.

        } else {

        }

}

/// Return true if `s` looks more like a consensus diff than some other kind

/// of document.

/// Apply a given diff to an input text, and return the result from applying

/// that diff.

///

/// This is a slow version, for testing and correctness checking.  It uses

/// an O(n) operation to apply diffs, and therefore runs in O(n^2) time.

#[cfg(any(test, feature = "slow-diff-apply"))]

    }

/// Apply a given diff to an input text, and return the result from applying

/// that diff.

///

/// If `check_digest_in` is provided, require the diff to say that it

/// applies to a document with the provided digest.

    // This actually counts newlines, and can be off-by-one, but that's okay.

    }

/// A degree of strictness to apply when checking the size of a diff versus

/// the size of the associated consensus.

#[derive(Clone, Copy, Debug)]

#[non_exhaustive]

pub enum DiffSizeStrictness {

    /// Do not perform any checks.

    None,

    /// Check whether the diff is reasonable to apply to the input.

    Apply,

    /// Check whether the diff is reasonable to serve as a diff against the input.

    ///

    /// This is an even stricter version of [`DiffSizeStrictness::Apply`].

    Generate,

}

impl DiffSizeStrictness {

    /// Check whether a given diff is implausibly or uselessly large in comparison with

    /// the input, and return an error if so.

        use DiffSizeStrictness as S;

        use Error::DiffTooLarge;

            S::Generate => {

                // If we just generated a diff that isn't smaller than the consensus we started with,

                // there is no point in serving it. It wouldn't save size.

                // Also, check whether the client would reject this diff when trying to apply it.

            }

            S::Apply => {

                const BYTE_THRESHOLD: usize = 64 * 1024;

                const LINE_THRESHOLD: usize = 1024;

            }

        }

}

/// Given a line iterator, check to make sure the first two lines are

/// a valid diff header as specified in dir-spec.txt.

{

    }

/// A command that can appear in a diff.  Each command tells us to

/// remove zero or more lines, and insert zero or more lines in their

/// place.

///

/// Commands refer to lines by 1-indexed line number.

#[derive(Clone, Debug)]

enum DiffCommand<'a> {

    /// Remove the lines from low through high, inclusive.

    Delete {

        /// The first line to remove

        low: usize,

        /// The last line to remove

        high: usize,

    },

    /// Remove the lines from low through the end of the file, inclusive.

    DeleteToEnd {

        /// The first line to remove

        low: usize,

    },

    /// Replace the lines from low through high, inclusive, with the

    /// lines in 'lines'.

    Replace {

        /// The first line to replace

        low: usize,

        /// The last line to replace

        high: usize,

        /// The text to insert instead

        lines: Vec<&'a str>,

    },

    /// Insert the provided 'lines' after the line with index 'pos'.

    Insert {

        /// The position after which to insert the text

        pos: usize,

        /// The text to insert

        lines: Vec<&'a str>,

    },

}

/// The result of applying one or more diff commands to an input string.

///

/// It refers to lines from the diff and the input by reference, to

/// avoid copying.

#[derive(Clone, Debug)]

pub struct DiffResult<'a> {

    /// An expected digest of the output, after it has been assembled.

    d_post: [u8; 32],

    /// The lines in the output.

    lines: Vec<&'a str>,

}

/// A possible value for the end of a range.  It can be either a line number,

/// or a dollar sign indicating "end of file".

#[derive(Clone, Copy, Debug)]

enum RangeEnd {

    /// A line number in the file.

    Num(NonZeroUsize),

    /// A dollar sign, indicating "end of file" in a delete command.

    DollarSign,

}

impl FromStr for RangeEnd {

    type Err = Error;

        } else {

        }

}

impl<'a> DiffCommand<'a> {

    /// Transform 'target' according to the this command.

    ///

    /// Because DiffResult internally uses a vector of line, this

    /// implementation is potentially O(n) in the size of the input.

    #[cfg(any(test, feature = "slow-diff-apply"))]

            }

            }

            }

                // This '+1' seems off, but it's what the spec says. I wonder

                // if the spec is wrong.

            }

        };

    /// Apply this command to 'input', moving lines into 'output'.

    ///

    /// This is a more efficient algorithm, but it requires that the

    /// diff commands are sorted in reverse order by line

    /// number. (Fortunately, the Tor ed diff format guarantees this.)

    ///

    /// Before calling this method, input and output must contain the

    /// results of having applied the previous command in the diff.

    /// (When no commands have been applied, input starts out as the

    /// original text, and output starts out empty.)

    ///

    /// This method applies the command by copying unaffected lines

    /// from the _end_ of input into output, adding any lines inserted

    /// by this command, and finally deleting any affected lines from

    /// input.

    ///

    /// We build the `output` value in reverse order, and then put it

    /// back to normal before giving it to the user.

                // Oops, dubious line number.

            }

    /// Return the lines that we should add to the output

        }

    /// Return a mutable reference to the vector of lines we should

    /// add to the output.

        }

    /// Return the (1-indexed) line number of the first line in the

    /// input that comes _after_ this command, and is not affected by it.

    ///

    /// We use this line number to know which lines we should copy.

        }

    /// Return the (1-indexed) line number of the first line that we

    /// should clear from the input when processing this command.

    ///

    /// This can be the same as following_lines(), if we shouldn't

    /// actually remove any lines.

        }

    /// Return true if this is an Insert command.

    /// Extract a single command from a line iterator that yields lines

    /// of the diffs.  Return None if we're at the end of the iterator.

    {

        };

        // `command` can be of these forms: `Rc`, `Rd`, `N,$d`, and `Na`,

        // where R is a range of form `N,N`, and where N is a line number.

        } else {

        };

            }

        }

        };

            // The 'c' and 'a' commands take a series of lines followed by a

            // line containing a period.

            loop {

                }

            }

}

/// Iterator that wraps a line iterator and returns a sequence of

/// `Result<DiffCommand>`.

///

/// This iterator forces the commands to affect the file in reverse order,

/// so that we can use the O(n) algorithm for applying these diffs.

struct DiffCommandIter<'a, I>

where

    I: Iterator<Item = &'a str>,

{

    /// The underlying iterator.

    iter: I,

    /// The 'first removed line' of the last-parsed command; used to ensure

    /// that commands appear in reverse order.

    last_cmd_first_removed: Option<usize>,

}

impl<'a, I> DiffCommandIter<'a, I>

where

    I: Iterator<Item = &'a str>,

{

    /// Construct a new DiffCommandIter wrapping `iter`.

}

impl<'a, I> Iterator for DiffCommandIter<'a, I>

where

    I: Iterator<Item = &'a str>,

{

    type Item = Result<DiffCommand<'a>>;

                (_, _) => {

                }

            },

        }

}

impl<'a> DiffResult<'a> {

    /// Construct a new DiffResult containing the provided string

    /// split into lines, and an expected post-transformation digest.

        // As per the [netdoc syntax], newlines should be discarded and ignored.

        //

        // [netdoc syntax]: https://spec.torproject.org/dir-spec/netdoc.html#netdoc-syntax

    /// Return a new empty DiffResult with an expected

    /// post-transformation digests

    /// Put every member of `lines` at the end of this DiffResult, in

    /// reverse order.

    /// Remove the 1-indexed lines from `first` through `last` inclusive.

    ///

    /// This has to move elements around within the vector, and so it

    /// is potentially O(n) in its length.

    #[cfg(any(test, feature = "slow-diff-apply"))]

        } else {

        }

    /// Insert the provided `lines` so that they appear at 1-indexed

    /// position `pos`.

    ///

    /// This has to move elements around within the vector, and so it

    /// is potentially O(n) in its length.

    #[cfg(any(test, feature = "slow-diff-apply"))]

        } else {

        }

    /// See whether the output of this diff matches the target digest.

    ///

    /// If not, return an error.

        use digest::Digest;

        use tor_llcrypto::d::Sha3_256;

        } else {

        }

}

impl<'a> Display for DiffResult<'a> {

        }

}

/// Count the number of newlines that appear in s.

///

/// This is potentially one less than the number of lines in s, if the final line is not terminated,

///but that's okay for our uses here.

#[cfg(test)]

mod test {

    // @@ begin test lint list maintained by maint/add_warning @@

    #![allow(clippy::bool_assert_comparison)]

    #![allow(clippy::clone_on_copy)]

    #![allow(clippy::dbg_macro)]

    #![allow(clippy::mixed_attributes_style)]

    #![allow(clippy::print_stderr)]

    #![allow(clippy::print_stdout)]

    #![allow(clippy::single_char_pattern)]

    #![allow(clippy::unwrap_used)]

    #![allow(clippy::unchecked_time_subtraction)]

    #![allow(clippy::useless_vec)]

    #![allow(clippy::needless_pass_by_value)]

    #![allow(clippy::string_slice)] // See arti#2571

    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->

    use rand::seq::IndexedRandom;

    use tor_basic_utils::test_rng::testing_rng;

    use super::DiffSizeStrictness as DSS;

    use super::*;

    #[test]

    fn remove() -> Result<()> {

        let example = DiffResult::from_str("1\n2\n3\n4\n5\n6\n7\n8\n9\n", [0; 32]);

        let mut d = example.clone();

        d.remove_lines(5, 7)?;

        assert_eq!(d.to_string(), "1\n2\n3\n4\n8\n9\n");

        let mut d = example.clone();

        d.remove_lines(1, 9)?;

        assert_eq!(d.to_string(), "");

        let mut d = example.clone();

        d.remove_lines(1, 1)?;

        assert_eq!(d.to_string(), "2\n3\n4\n5\n6\n7\n8\n9\n");

        let mut d = example.clone();

        d.remove_lines(6, 9)?;

        assert_eq!(d.to_string(), "1\n2\n3\n4\n5\n");

        let mut d = example.clone();

        assert!(d.remove_lines(6, 10).is_err());

        assert!(d.remove_lines(0, 1).is_err());

        assert_eq!(d.to_string(), "1\n2\n3\n4\n5\n6\n7\n8\n9\n");

        Ok(())

    }

    #[test]

    fn insert() -> Result<()> {

        let example = DiffResult::from_str("1\n2\n3\n4\n5\n", [0; 32]);

        let mut d = example.clone();

        d.insert_at(3, &["hello", "world"])?;

        assert_eq!(d.to_string(), "1\n2\nhello\nworld\n3\n4\n5\n");

        let mut d = example.clone();

        d.insert_at(6, &["hello", "world"])?;

        assert_eq!(d.to_string(), "1\n2\n3\n4\n5\nhello\nworld\n");

        let mut d = example.clone();

        assert!(d.insert_at(0, &["hello", "world"]).is_err());

        assert!(d.insert_at(7, &["hello", "world"]).is_err());

        Ok(())

    }

    #[test]

    fn push_reversed() {

        let mut d = DiffResult::new([0; 32]);

        d.push_reversed(&["7", "8", "9"]);

        assert_eq!(d.to_string(), "9\n8\n7\n");

        d.push_reversed(&["world", "hello", ""]);

        assert_eq!(d.to_string(), "9\n8\n7\n\nhello\nworld\n");

    }

    #[test]

    fn apply_command_simple() {

        let example = DiffResult::from_str("a\nb\nc\nd\ne\nf\n", [0; 32]);

        let mut d = example.clone();

        assert_eq!(d.to_string(), "a\nb\nc\nd\ne\nf\n".to_string());

        assert!(DiffCommand::DeleteToEnd { low: 5 }.apply_to(&mut d).is_ok());

        assert_eq!(d.to_string(), "a\nb\nc\nd\n".to_string());

        let mut d = example.clone();

        assert!(

            DiffCommand::Delete { low: 3, high: 5 }

                .apply_to(&mut d)

                .is_ok()

        );

        assert_eq!(d.to_string(), "a\nb\nf\n".to_string());

        let mut d = example.clone();

        assert!(

            DiffCommand::Replace {

                low: 3,

                high: 5,

                lines: vec!["hello", "world"]

            }

            .apply_to(&mut d)

            .is_ok()

        );

        assert_eq!(d.to_string(), "a\nb\nhello\nworld\nf\n".to_string());

        let mut d = example.clone();

        assert!(

            DiffCommand::Insert {

                pos: 3,

                lines: vec!["hello", "world"]

            }

            .apply_to(&mut d)

            .is_ok()

        );

        assert_eq!(

            d.to_string(),

            "a\nb\nc\nhello\nworld\nd\ne\nf\n".to_string()

        );

    }

    #[test]

    fn parse_command() -> Result<()> {

        fn parse(s: &str) -> Result<DiffCommand<'_>> {

            let mut iter = s.lines();

            let cmd = DiffCommand::from_line_iterator(&mut iter)?;

            let cmd2 = DiffCommand::from_line_iterator(&mut iter)?;

            if cmd2.is_some() {

                panic!("Unexpected second command");

            }

            Ok(cmd.unwrap())

        }

        fn parse_err(s: &str) {

            let mut iter = s.lines();

            let cmd = DiffCommand::from_line_iterator(&mut iter);

            assert!(matches!(cmd, Err(Error::BadDiff(_))));

        }

        let p = parse("3,8d\n")?;

        assert!(matches!(p, DiffCommand::Delete { low: 3, high: 8 }));

        let p = parse("3d\n")?;

        assert!(matches!(p, DiffCommand::Delete { low: 3, high: 3 }));

        let p = parse("100,$d\n")?;

        assert!(matches!(p, DiffCommand::DeleteToEnd { low: 100 }));

        let p = parse("30,40c\nHello\nWorld\n.\n")?;

        assert!(matches!(

            p,

            DiffCommand::Replace {

                low: 30,

                high: 40,

                ..

            }

        ));

        assert_eq!(p.lines(), Some(&["Hello", "World"][..]));

        let p = parse("30c\nHello\nWorld\n.\n")?;

        assert!(matches!(

            p,

            DiffCommand::Replace {

                low: 30,

                high: 30,

                ..

            }

        ));

        assert_eq!(p.lines(), Some(&["Hello", "World"][..]));

        let p = parse("999a\nHello\nWorld\n.\n")?;

        assert!(matches!(p, DiffCommand::Insert { pos: 999, .. }));

        assert_eq!(p.lines(), Some(&["Hello", "World"][..]));

        let p = parse("0a\nHello\nWorld\n.\n")?;

        assert!(matches!(p, DiffCommand::Insert { pos: 0, .. }));

        assert_eq!(p.lines(), Some(&["Hello", "World"][..]));

        parse_err("hello world");

        parse_err("\n\n");

        parse_err("$,5d");

        parse_err("5,6,8d");

        parse_err("8,5d");

        parse_err("6");

        parse_err("d");

        parse_err("-10d");

        parse_err("4,$c\na\n.");

        parse_err("foo");

        parse_err("5,10p");

        parse_err("18446744073709551615a");

        parse_err("1,18446744073709551615d");

        Ok(())

    }

    #[test]

    fn apply_transformation() -> Result<()> {

        let example = DiffResult::from_str("1\n2\n3\n4\n5\n6\n7\n8\n9\n", [0; 32]);

        let empty = DiffResult::new([1; 32]);

        let mut inp = example.clone();

        let mut out = empty.clone();

        DiffCommand::DeleteToEnd { low: 5 }.apply_transformation(&mut inp, &mut out)?;

        assert_eq!(inp.to_string(), "1\n2\n3\n4\n");

        assert_eq!(out.to_string(), "");

        let mut inp = example.clone();

        let mut out = empty.clone();

        DiffCommand::DeleteToEnd { low: 9 }.apply_transformation(&mut inp, &mut out)?;

        assert_eq!(inp.to_string(), "1\n2\n3\n4\n5\n6\n7\n8\n");

        assert_eq!(out.to_string(), "");

        let mut inp = example.clone();

        let mut out = empty.clone();

        DiffCommand::Delete { low: 3, high: 5 }.apply_transformation(&mut inp, &mut out)?;

        assert_eq!(inp.to_string(), "1\n2\n");

        assert_eq!(out.to_string(), "9\n8\n7\n6\n");

        let mut inp = example.clone();

        let mut out = empty.clone();

        DiffCommand::Replace {

            low: 5,

            high: 6,

            lines: vec!["oh hey", "there"],

        }

        .apply_transformation(&mut inp, &mut out)?;

        assert_eq!(inp.to_string(), "1\n2\n3\n4\n");

        assert_eq!(out.to_string(), "9\n8\n7\nthere\noh hey\n");

        let mut inp = example.clone();

        let mut out = empty.clone();

        DiffCommand::Insert {

            pos: 3,

            lines: vec!["oh hey", "there"],

        }

        .apply_transformation(&mut inp, &mut out)?;

        assert_eq!(inp.to_string(), "1\n2\n3\n");

        assert_eq!(out.to_string(), "9\n8\n7\n6\n5\n4\nthere\noh hey\n");

        DiffCommand::Insert {

            pos: 0,

            lines: vec!["boom!"],

        }

        .apply_transformation(&mut inp, &mut out)?;

        assert_eq!(inp.to_string(), "");

        assert_eq!(

            out.to_string(),

            "9\n8\n7\n6\n5\n4\nthere\noh hey\n3\n2\n1\nboom!\n"

        );

        let mut inp = example.clone();

        let mut out = empty.clone();

        let r = DiffCommand::Delete {

            low: 100,

            high: 200,

        }

        .apply_transformation(&mut inp, &mut out);

        assert!(r.is_err());

        let r = DiffCommand::Delete { low: 5, high: 200 }.apply_transformation(&mut inp, &mut out);

        assert!(r.is_err());

        let r = DiffCommand::Delete { low: 0, high: 1 }.apply_transformation(&mut inp, &mut out);

        assert!(r.is_err());

        let r = DiffCommand::DeleteToEnd { low: 10 }.apply_transformation(&mut inp, &mut out);

        assert!(r.is_err());

        Ok(())

    }

    #[test]

    fn header() -> Result<()> {

        fn header_from(s: &str) -> Result<([u8; 32], [u8; 32])> {

            let mut iter = s.lines();

            parse_diff_header(&mut iter)

        }

        let (a,b) = header_from(

            "network-status-diff-version 1

hash B03DA3ACA1D3C1D083E3FF97873002416EBD81A058B406D5C5946EAB53A79663 F6789F35B6B3BA58BB23D29E53A8ED6CBB995543DBE075DD5671481C4BA677FB"

        )?;

        assert_eq!(

            &a[..],

            hex::decode("B03DA3ACA1D3C1D083E3FF97873002416EBD81A058B406D5C5946EAB53A79663")?

        );

        assert_eq!(

            &b[..],

            hex::decode("F6789F35B6B3BA58BB23D29E53A8ED6CBB995543DBE075DD5671481C4BA677FB")?

        );

        assert!(header_from("network-status-diff-version 2\n").is_err());

        assert!(header_from("").is_err());

        assert!(header_from("5,$d\n1,2d\n").is_err());

        assert!(header_from("network-status-diff-version 1\n").is_err());

        assert!(

            header_from(

                "network-status-diff-version 1

hash x y

5,5d"

            )

            .is_err()

        );

        assert!(

            header_from(

                "network-status-diff-version 1

hash x y

5,5d"

            )

            .is_err()

        );

        assert!(

            header_from(

                "network-status-diff-version 1

hash AA BB

5,5d"

            )

            .is_err()

        );

        assert!(

            header_from(

                "network-status-diff-version 1

oh hello there

5,5d"

            )

            .is_err()

        );

        assert!(header_from("network-status-diff-version 1

hash B03DA3ACA1D3C1D083E3FF97873002416EBD81A058B406D5C5946EAB53A79663 F6789F35B6B3BA58BB23D29E53A8ED6CBB995543DBE075DD5671481C4BA677FB extra").is_err());

        Ok(())

    }

    #[test]

    fn apply_simple() {

        let pre = include_str!("../testdata/consensus1.txt");

        let diff = include_str!("../testdata/diff1.txt");

        let post = include_str!("../testdata/consensus2.txt");

        let result = apply_diff_trivial(pre, diff).unwrap();

        assert!(result.check_digest().is_ok());

        assert_eq!(result.to_string(), post);

    }

    #[test]

    fn sort_order() -> Result<()> {

        fn cmds(s: &str) -> Result<Vec<DiffCommand<'_>>> {

            let mut out = Vec::new();

            for cmd in DiffCommandIter::new(s.lines()) {

                out.push(cmd?);

            }

            Ok(out)

        }

        let _ = cmds("6,9d\n5,5d\n")?;

        assert!(cmds("5,5d\n6,9d\n").is_err());

        assert!(cmds("5,5d\n6,6d\n").is_err());

        assert!(cmds("5,5d\n5,6d\n").is_err());

        Ok(())

    }

    /// Test for cons diff using a random word generator.

    #[test]

    fn cons_diff() {

        // cat /usr/share/dict/words | sort -R | head -n 20 | sed 's/^/"/g' | sed 's/$/",/g'

        const WORDS: &[&str] = &[

            "citole",

            "aflow",

            "plowfoot",

            "coom",

            "retape",

            "perish",

            "overstifle",

            "ramshackle",

            "Romeo",

            "alme",

            "expressivity",

            "Kieffer",

            "tobe",

            "pronucleus",

            "countersconce",

            "puli",

            "acupunctuate",

            "heterolysis",

            "unwattled",

            "bismerpund",

        ];

        let rng = &mut testing_rng();

        let mut left = (0..1000)

            .map(|_| WORDS.choose(rng).unwrap().to_string() + "\n")

            .collect::<String>();

        left += "directory-signature foo bar\n";

        let mut right = (0..1015)

            .map(|_| WORDS.choose(rng).unwrap().to_string() + "\n")

            .collect::<String>();

        right += "directory-signature foo baz\n";

        let diff = gen_cons_diff(&left, &right, DSS::None).unwrap();

        let check = apply_diff(&left, &diff, None, DSS::None)

            .unwrap()

            .to_string();

        assert_eq!(right, check);

    }

    #[test]

    fn dot_line() {

        let base = "";

        let target = "foo\nbar\n.\nbaz\nfoo\n";

        assert_eq!(

            gen_ed_diff(base, target).unwrap_err(),

            GenEdDiffError::ContainsDotLine { lno: 3 },

        );

        // Also check for dot lines with trailing spaces.

        let target = "foo\nbar\n.   \t \nbaz\nfoo\n";

        assert_eq!(

            gen_ed_diff(base, target).unwrap_err(),

            GenEdDiffError::ContainsDotLine { lno: 3 },

        );

        // A line starting with a dot and not ending in WS shall be fine though.

        let target = "foo\nbar\n.   foo\nbaz\nfoo\n";

        let _ = gen_ed_diff(base, target).unwrap();

        // Use gen_cons_diff here to assume that it is actually applied.

        let base = "directory-signature foo baz\n";

        let target = ".foo bar\n. bar\ndirectory-signature foo baz\n";

        assert_eq!(

            gen_cons_diff(base, target, DSS::None).unwrap(),

            "network-status-diff-version 1\n\

            hash D8138DC27D9A66F5760058A6BCB71B755462B9D26B811828F124D036DE329A58 \

            506AC3A4407BC5305DD0D08FED3F09C2FE69847541F642A8FD13D3BD06FFE432\n\

            1,$d\n\

            0a\n\

            .foo bar\n\

            . bar\n\

            directory-signature foo baz\n\

            .\n"

        );

    }

    #[test]

    fn missing_newline() {

        let base = "";

        let target = "foo\nbar\nbaz";

        assert_eq!(

            gen_ed_diff(base, target).unwrap_err(),

            GenEdDiffError::MissingUnixLineEnding { lno: 3 }

        );

    }

    #[test]

    fn mixed_with_crlf() {

        let base = "";

        let target = "foo\r\nbar\r\nbaz\nhello\r\n";

        assert_eq!(