#![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)]

#![warn(clippy::cognitive_complexity)]

#![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)]

#![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

#![deny(clippy::unused_async)]

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

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

use std::num::NonZeroUsize;

use std::str::FromStr;

mod err;

pub use err::Error;

/// Result type used by this crate

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

/// 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.

    }

/// 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> {

        }

}

#[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)]

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

    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(())

    }

}