mod padding;

use sha1::{digest::FixedOutput, Digest, Sha1};

use flate2::write::ZlibEncoder;
use flate2::Compression;

use std::env;
use std::fs;
use std::io;
use std::io::Write;
use std::ops;
use std::process;
use std::str;
use std::sync::mpsc;
use std::thread;
use std::u64;
use std::u8;

const SHA1_BYTE_LENGTH: usize = 20;

// See the comment in `process_commit_message` for the commit and padding layout.
const DYNAMIC_PADDING_LENGTH: usize = 48;

#[derive(Debug, PartialEq)]
struct HashPrefix {
    data: Vec<u8>,
    half_byte: Option<u8>,
}

impl Clone for HashPrefix {
    fn clone(&self) -> Self {
        HashPrefix {
            data: self.data.to_owned(),
            half_byte: self.half_byte.to_owned(),
        }
    }
}

struct SearchParams {
    current_message: String,
    desired_prefix: HashPrefix,
    counter_range: ops::Range<u64>,
}

#[derive(Debug, PartialEq)]
struct HashMatch {
    data: Vec<u8>,
    hash: [u8; SHA1_BYTE_LENGTH],
}

#[derive(Debug, PartialEq)]
struct ProcessedCommitMessage {
    full_message: Vec<u8>,
    whitespace_index: usize,
}

fn main() {
    let args: Vec<String> = env::args().collect();

    match args.len() {
        1 => run_lucky_commit(&parse_prefix("0000000").unwrap()),
        2 => match parse_prefix(&args[1]) {
            Some(prefix) => run_lucky_commit(&prefix),
            None => print_usage_and_exit(),
        },
        _ => print_usage_and_exit(),
    }
}

fn print_usage_and_exit() -> ! {
    fail_with_message("Usage: lucky-commit [commit-hash-prefix]")
}

fn fail_with_message(message: &str) -> ! {
    eprintln!("{}", message);
    process::exit(1)
}

fn parse_prefix(prefix: &str) -> Option<HashPrefix> {
    let mut data = Vec::new();
    for index in 0..(prefix.len() / 2) {
        match u8::from_str_radix(&prefix[2 * index..2 * index + 2], 16) {
            Ok(value) => data.push(value),
            Err(_) => return None,
        }
    }

    let parsed_prefix = HashPrefix {
        data,
        half_byte: if prefix.len() % 2 == 1 {
            match u8::from_str_radix(&prefix[prefix.len() - 1..], 16) {
                Ok(value) => Some(value << 4),
                Err(_) => return None,
            }
        } else {
            None
        },
    };

    Some(parsed_prefix)
}

fn run_lucky_commit(desired_prefix: &HashPrefix) {
    let current_message_bytes = run_command("git", &["cat-file", "commit", "HEAD"]);
    let current_message =
        &String::from_utf8(current_message_bytes).expect("Git commit contains invalid utf8");

    match find_match(current_message, desired_prefix) {
        Some(hash_match) => {
            create_git_object_file(&hash_match).expect("Failed to create git object file");
            git_reset_to_hash(&hash_match.hash);
        }
        None => fail_with_message("Failed to find a match"),
    }
}

fn run_command(command: &str, args: &[&str]) -> Vec<u8> {
    let output = process::Command::new(command)
        .args(args)
        .stderr(process::Stdio::inherit())
        .output()
        .expect("Failed to run command");

    if !output.status.success() {
        process::exit(1);
    }

    output.stdout
}

fn find_match(current_message: &str, desired_prefix: &HashPrefix) -> Option<HashMatch> {
    let num_threads = num_cpus::get_physical();
    let (shared_sender, receiver) = mpsc::channel();
    let counter_ranges = split_range(0, 1u64 << 48, num_threads);

    for thread_index in 0..num_threads {
        spawn_hash_searcher(
            shared_sender.clone(),
            SearchParams {
                current_message: current_message.to_owned(),
                desired_prefix: desired_prefix.clone(),
                counter_range: counter_ranges[thread_index].clone(),
            },
        );
    }

    for _ in 0..num_threads {
        let result = receiver.recv().unwrap();
        if result.is_some() {
            return result;
        }
    }

    None
}

fn spawn_hash_searcher(result_sender: mpsc::Sender<Option<HashMatch>>, params: SearchParams) {
    thread::spawn(move || {
        /*
         * If an error occurs when sending, then the receiver has already received
         * a match from another thread, so ignore the error.
         */
        let _ = result_sender.send(iterate_for_match(&params));
    });
}

fn split_range(min: u64, max: u64, num_segments: usize) -> Vec<ops::Range<u64>> {
    let segment_size = (max - min) / (num_segments as u64);

    let mut segments = Vec::new();
    let mut last_range_end = 0;
    for _ in 0..num_segments {
        segments.push(last_range_end..last_range_end + segment_size);
        last_range_end += segment_size;
    }

    segments
}

fn iterate_for_match(params: &SearchParams) -> Option<HashMatch> {
    let desired_prefix = &params.desired_prefix;
    let mut processed_message = process_commit_message(&params.current_message);

    // SHA1 works by splitting the input data into 64-byte blocks. Each 64-byte block
    // can be processed in sequence. Since we're adding whitespace near the end of a
    // commit object, the first few 64-byte blocks of the message will always be the same.
    // Instead of reprocessing those blocks every time, we can just cache the SHA1 state
    // after processing those blocks, and only process the new padding each time.
    let mut sha1_state_preceding_whitespace = Sha1::new();
    sha1_state_preceding_whitespace
        .update(&processed_message.full_message[0..processed_message.whitespace_index]);

    let commit_starting_at_whitespace =
        &mut processed_message.full_message[processed_message.whitespace_index..];
    let mut hash_result = Default::default();

    for counter in params.counter_range.clone() {
        for index_within_padding in (0..DYNAMIC_PADDING_LENGTH).step_by(8) {
            &mut commit_starting_at_whitespace[index_within_padding..index_within_padding + 8]
                .copy_from_slice(
                    &padding::PADDING_LIST[(counter >> index_within_padding) as u8 as usize],
                );
        }

        let mut sha1_hash = sha1_state_preceding_whitespace.clone();
        sha1_hash.update(&commit_starting_at_whitespace);
        sha1_hash.finalize_into_reset(&mut hash_result);

        if matches_desired_prefix(hash_result.as_ref(), desired_prefix) {
            return Some(HashMatch {
                data: processed_message.full_message,
                hash: hash_result.into(),
            });
        }
    }

    None
}

fn process_commit_message(original_message: &str) -> ProcessedCommitMessage {
    // The fully padded data that gets hashed is the concatenation of all the following:
    // * "commit " + length + "\x00", where `length` is the base-10 representation of the length
    //    of everything that follows the null character.
    // * The original commit object, containing everything up to the point where padding should be
    //   added.
    // * Up to 63 space characters, as static padding. This is inserted so that the dynamic padding
    //   that follows it will be at a multiple-of-64-byte offset. Since the performance-intensive
    //   search involves hashing all of the 64-byte blocks starting with the dynamic padding, this
    //   ensures that the dynamic padding is always in a single block. Note that it sometimes won't
    //   be possible to align the dynamic padding perfectly, because adding static padding also
    //   increases the length of the commit object used in the initial header, and this could
    //   bump the alignment twice if e.g. the length increases from 999 to 1000. As a result, in
    //   rare cases the dynamic padding will actually be at a multiple-of-64-byte + 1 offset,
    //   which isn't the end of the world because everything that follows the static padding
    //   will usually fit in one block anyway.
    // * 48 bytes of dynamic padding, consisting of space and tab characters. The ultimate goal
    //   is to find some combination of spaces and tabs that produces the desired hash. A 48-byte
    //   length was chosen with the goal of having everything that follows the static padding
    //   fit into one block for non-GPG-signed commits. (This allows 8 bytes for SHA1's final
    //   length padding, as well as a couple bytes for the remainder of the commit object and
    //   any alignment issues, while still using a multiple of 8 bytes for easily copying padding.)
    // * The rest of the original commit object. For non-GPG-signed commits, this will just be
    //   a single newline. For GPG-signed commits, this will contain the commit message.

    const DYNAMIC_PADDING_ALIGNMENT: usize = 64;
    let commit_split_index = get_commit_message_split_index(original_message);
    let trimmable_paddings: &[_] = &[' ', '\t'];
    let trimmed_end_half =
        original_message[commit_split_index..].trim_start_matches(trimmable_paddings);
    let length_before_static_padding =
        format!("commit {}\x00", commit_split_index).len() + commit_split_index;
    let static_padding_length = (DYNAMIC_PADDING_ALIGNMENT
        - (length_before_static_padding % DYNAMIC_PADDING_ALIGNMENT))
        % DYNAMIC_PADDING_ALIGNMENT;

    let mut message_object: Vec<u8> = format!(
        "commit {}\x00",
        commit_split_index
            + static_padding_length
            + DYNAMIC_PADDING_LENGTH
            + trimmed_end_half.len()
    )
    .into_bytes();

    let whitespace_index = message_object.len() + commit_split_index + static_padding_length;
    assert!(whitespace_index % DYNAMIC_PADDING_ALIGNMENT <= 2);

    for character in original_message[..commit_split_index].as_bytes() {
        // Add the first half of the original commit
        message_object.push(*character);
    }

    for _ in 0..static_padding_length {
        // Add static padding
        message_object.push(padding::SPACE);
    }

    for _ in 0..DYNAMIC_PADDING_LENGTH {
        // Add dynamic padding, initialized to tabs for now
        message_object.push(padding::TAB);
    }

    for character in trimmed_end_half.as_bytes() {
        // Add the rest of the commit
        message_object.push(*character);
    }

    ProcessedCommitMessage {
        full_message: message_object,
        whitespace_index,
    }
}

fn get_commit_message_split_index(message: &str) -> usize {
    /*
     * If the commit has a GPG signature (detected by the presence of "-----END PGP SIGNATURE-----"
     * after a line that starts with "gpgsig "), then add the padding whitespace immediately after
     * the text "-----END PGP SIGNATURE-----".
     * Otherwise, add the padding whitespace right before the end of the commit message.
     *
     * To save time hashing, we want the padding to be as close to the end of the commit message
     * as possible. However, if a signature is present, modifying the commit message would make
     * the signature invalid
     */
    let mut found_gpgsig_line = false;
    const SIGNATURE_MARKER: &str = "-----END PGP SIGNATURE-----";
    for (index, _character) in message.char_indices() {
        if message[index..].starts_with("\ngpgsig ") {
            found_gpgsig_line = true;
        } else if !found_gpgsig_line && message[index..].starts_with("\n\n") {
            // We've reached the commit message and no GPG signature has been found.
            // Add the padding to the end of the commit.
            break;
        } else if found_gpgsig_line && message[index..].starts_with(SIGNATURE_MARKER) {
            return index + SIGNATURE_MARKER.len();
        }
    }

    message.trim_end().len()
}

fn matches_desired_prefix(hash: &[u8; SHA1_BYTE_LENGTH], prefix: &HashPrefix) -> bool {
    prefix.data == &hash[..prefix.data.len()]
        && match prefix.half_byte {
            Some(half_byte) => (hash[prefix.data.len()] & 0xf0) == half_byte,
            None => true,
        }
}

fn create_git_object_file(search_result: &HashMatch) -> io::Result<()> {
    let compressed_object = zlib_compress(&search_result.data)?;
    let git_dir_bytes = run_command("git", &["rev-parse", "--git-dir"]);
    let mut git_dir =
        String::from_utf8(git_dir_bytes).expect("git rev-parse --git-dir returned invalid utf8");
    git_dir.truncate(git_dir.len() - 1);
    let dir_path = format!("{}/objects/{:02x}", git_dir, search_result.hash[0]);
    let file_path = format!("{}/{}", dir_path, to_hex_string(&search_result.hash[1..]));

    fs::DirBuilder::new().recursive(true).create(dir_path)?;

    fs::File::create(file_path)?.write_all(&compressed_object)
}

fn zlib_compress(data: &[u8]) -> io::Result<Vec<u8>> {
    let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
    encoder.write(data)?;
    encoder.finish()
}

fn git_reset_to_hash(hash: &[u8; SHA1_BYTE_LENGTH]) {
    run_command("git", &["reset", &to_hex_string(hash)]);
}

fn to_hex_string(hash: &[u8]) -> String {
    hash.iter()
        .map(|byte| format!("{:02x}", *byte))
        .collect::<String>()
}

#[cfg(test)]
mod tests {
    use std::iter;

    use super::*;

    const TEST_COMMIT_MESSAGE_WITHOUT_SIGNATURE: &str = "\
         tree 0123456701234567012345670123456701234567\n\
         parent 7654321076543210765432107654321076543210\n\
         author Foo Bár <foo@example.com> 1513980859 -0500\n\
         committer Baz Qux <baz@example.com> 1513980898 -0500\n\
         \n\
         Do a thing\n\
         \n\
         Makes some changes to the foo feature\n\
         ";

    const TEST_COMMIT_MESSAGE_WITH_SIGNATURE: &str = "\
         tree 0123456701234567012345670123456701234567\n\
         parent 7654321076543210765432107654321076543210\n\
         author Foo Bár <foo@example.com> 1513980859 -0500\n\
         committer Baz Qux <baz@example.com> 1513980898 -0500\n\
         gpgsig -----BEGIN PGP SIGNATURE-----\n\
         \n\
         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
         =AAAA\n\
         -----END PGP SIGNATURE-----\n\
         \n\
         Do a thing\n\
         \n\
         Makes some changes to the foo feature\n\
         ";

    const TEST_COMMIT_MESSAGE_WITH_SIGNATURE_AND_MULTIPLE_PARENTS: &str = "\
        tree 0123456701234567012345670123456701234567\n\
        parent 7654321076543210765432107654321076543210\n\
        parent 2468246824682468246824682468246824682468\n\
        author Foo Bár <foo@example.com> 1513980859 -0500\n\
        committer Baz Qux <baz@example.com> 1513980898 -0500\n\
        gpgsig -----BEGIN PGP SIGNATURE-----\n\
        \n\
        AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
        AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
        AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
        AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
        AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
        AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
        =AAAA\n\
        -----END PGP SIGNATURE-----\n\
        \n\
        Do a thing\n\
        \n\
        Makes some changes to the foo feature\n\
        ";

    const TEST_COMMIT_WITH_GPG_STUFF_IN_MESSAGE: &str = "\
        tree 0123456701234567012345670123456701234567\n\
        parent 7654321076543210765432107654321076543210\n\
        author Foo Bár <foo@example.com> 1513980859 -0500\n\
        committer Baz Qux <baz@example.com> 1513980898 -0500\n\
        \n\
        For no particular reason, this commit message looks like a GPG signature.\n\
        gpgsig -----END PGP SIGNATURE-----\n\
        \n\
        So anyway, that's fun.\n\
        ";

    const TEST_COMMIT_WITH_GPG_STUFF_IN_EMAIL: &str = "\
        tree 0123456701234567012345670123456701234567\n\
        parent 7654321076543210765432107654321076543210\n\
        author Foo Bár <-----END PGP SIGNATURE-----@example.com> 1513980859 -0500\n\
        committer Baz Qux <baz@example.com> 1513980898 -0500\n\
        \n\
        For no particular reason, the commit author's email has a GPG signature marker.\n\
        ";

    #[test]
    fn parse_prefix_empty() {
        assert_eq!(
            Some(HashPrefix {
                data: Vec::new(),
                half_byte: None
            }),
            parse_prefix("")
        )
    }

    #[test]
    fn parse_prefix_single_char() {
        assert_eq!(
            Some(HashPrefix {
                data: Vec::new(),
                half_byte: Some(0xa0)
            }),
            parse_prefix("a")
        )
    }

    #[test]
    fn parse_prefix_even_chars() {
        assert_eq!(
            Some(HashPrefix {
                data: vec![0xab, 0xcd, 0xef],
                half_byte: None
            }),
            parse_prefix("abcdef")
        )
    }

    #[test]
    fn parse_prefix_odd_chars() {
        assert_eq!(
            Some(HashPrefix {
                data: vec![0xab, 0xcd, 0xef],
                half_byte: Some(0x50)
            }),
            parse_prefix("abcdef5")
        )
    }

    #[test]
    fn parse_prefix_capital_letters() {
        assert_eq!(
            Some(HashPrefix {
                data: vec![0xab, 0xcd, 0xef],
                half_byte: Some(0xb0)
            }),
            parse_prefix("ABCDEFB")
        )
    }

    #[test]
    fn parse_prefix_invalid_even_chars() {
        assert_eq!(None, parse_prefix("abcdgeb"))
    }

    #[test]
    fn parse_prefix_invalid_odd_char() {
        assert_eq!(None, parse_prefix("abcdefg"))
    }

    #[test]
    fn iterate_for_match_failure() {
        let search_params = SearchParams {
            current_message: TEST_COMMIT_MESSAGE_WITH_SIGNATURE.to_owned(),
            desired_prefix: HashPrefix {
                data: vec![1, 2, 3],
                half_byte: Some(0x40),
            },
            counter_range: 1..100,
        };

        assert_eq!(None, iterate_for_match(&search_params))
    }

    #[test]
    fn search_for_match_success() {
        let search_params = SearchParams {
            current_message: TEST_COMMIT_MESSAGE_WITH_SIGNATURE.to_owned(),
            desired_prefix: HashPrefix {
                data: vec![73, 174],
                half_byte: Some(0x80),
            },
            counter_range: 1..100,
        };

        assert_eq!(
            Some(HashMatch {
                data: format!(
                    "\
                     commit {}\x00\
                     tree 0123456701234567012345670123456701234567\n\
                     parent 7654321076543210765432107654321076543210\n\
                     author Foo Bár <foo@example.com> 1513980859 -0500\n\
                     committer Baz Qux <baz@example.com> 1513980898 -0500\n\
                     gpgsig -----BEGIN PGP SIGNATURE-----\n\
                     \n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     =AAAA\n\
                     -----END PGP SIGNATURE-----{}{}\n\
                     \n\
                     Do a thing\n\
                     \n\
                     Makes some changes to the foo feature\n\
                     ",
                    TEST_COMMIT_MESSAGE_WITH_SIGNATURE.len() + 40 + 48,
                    iter::repeat(" ").take(40).collect::<String>(),
                    "    \t \t                                         "
                )
                .into_bytes(),
                hash: [
                    73, 174, 143, 115, 152, 190, 169, 211, 5, 49, 116, 178, 8, 186, 106, 125, 3,
                    169, 65, 184
                ]
            }),
            iterate_for_match(&search_params)
        )
    }

    #[test]
    fn process_commit_message_without_gpg_signature() {
        assert_eq!(
            ProcessedCommitMessage {
                full_message: format!(
                    "\
                     commit {}\x00\
                     tree 0123456701234567012345670123456701234567\n\
                     parent 7654321076543210765432107654321076543210\n\
                     author Foo Bár <foo@example.com> 1513980859 -0500\n\
                     committer Baz Qux <baz@example.com> 1513980898 -0500\n\
                     \n\
                     Do a thing\n\
                     \n\
                     Makes some changes to the foo feature\
                     {}{}\n\
                     ",
                    TEST_COMMIT_MESSAGE_WITHOUT_SIGNATURE.len() + 61 + 48,
                    iter::repeat(" ").take(61).collect::<String>(),
                    iter::repeat("\t").take(48).collect::<String>()
                )
                .into_bytes(),
                whitespace_index: 320
            },
            process_commit_message(TEST_COMMIT_MESSAGE_WITHOUT_SIGNATURE)
        )
    }

    #[test]
    fn process_commit_message_with_gpg_signature() {
        assert_eq!(
            ProcessedCommitMessage {
                full_message: format!(
                    "\
                     commit {}\x00\
                     tree 0123456701234567012345670123456701234567\n\
                     parent 7654321076543210765432107654321076543210\n\
                     author Foo Bár <foo@example.com> 1513980859 -0500\n\
                     committer Baz Qux <baz@example.com> 1513980898 -0500\n\
                     gpgsig -----BEGIN PGP SIGNATURE-----\n\
                     \n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     =AAAA\n\
                     -----END PGP SIGNATURE-----{}{}\n\
                     \n\
                     Do a thing\n\
                     \n\
                     Makes some changes to the foo feature\n\
                     ",
                    TEST_COMMIT_MESSAGE_WITH_SIGNATURE.len() + 40 + 48,
                    iter::repeat(" ").take(40).collect::<String>(),
                    iter::repeat("\t").take(48).collect::<String>()
                )
                .into_bytes(),
                whitespace_index: 704
            },
            process_commit_message(TEST_COMMIT_MESSAGE_WITH_SIGNATURE)
        );
    }

    #[test]
    fn process_commit_message_already_padded() {
        assert_eq!(
            ProcessedCommitMessage {
                full_message: format!(
                    "\
                     commit {}\x00\
                     tree 0123456701234567012345670123456701234567\n\
                     parent 7654321076543210765432107654321076543210\n\
                     author Foo Bár <foo@example.com> 1513980859 -0500\n\
                     committer Baz Qux <baz@example.com> 1513980898 -0500\n\
                     gpgsig {}-----BEGIN PGP SIGNATURE-----\n\
                     \n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     =AAAA\n\
                     -----END PGP SIGNATURE-----{}{}\n\
                     \n\
                     Do a thing\n\
                     \n\
                     Makes some changes to the foo feature\n\
                     ",
                    TEST_COMMIT_MESSAGE_WITH_SIGNATURE.len() + 32 + 8 + 48,
                    iter::repeat("\t").take(32).collect::<String>(),
                    iter::repeat(" ").take(8).collect::<String>(),
                    iter::repeat("\t").take(48).collect::<String>()
                )
                .into_bytes(),
                whitespace_index: 704
            },
            process_commit_message(&format!(
                "\
                     tree 0123456701234567012345670123456701234567\n\
                     parent 7654321076543210765432107654321076543210\n\
                     author Foo Bár <foo@example.com> 1513980859 -0500\n\
                     committer Baz Qux <baz@example.com> 1513980898 -0500\n\
                     gpgsig {}-----BEGIN PGP SIGNATURE-----\n\
                     \n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     =AAAA\n\
                     -----END PGP SIGNATURE-----{}\n\
                     \n\
                     Do a thing\n\
                     \n\
                     Makes some changes to the foo feature\n\
                     ",
                iter::repeat("\t").take(32).collect::<String>(),
                iter::repeat(" ").take(100).collect::<String>()
            ))
        )
    }

    #[test]
    fn process_merge_commit_with_signature() {
        assert_eq!(
            ProcessedCommitMessage {
                full_message: format!(
                    "\
                     commit {}\x00\
                     tree 0123456701234567012345670123456701234567\n\
                     parent 7654321076543210765432107654321076543210\n\
                     parent 2468246824682468246824682468246824682468\n\
                     author Foo Bár <foo@example.com> 1513980859 -0500\n\
                     committer Baz Qux <baz@example.com> 1513980898 -0500\n\
                     gpgsig -----BEGIN PGP SIGNATURE-----\n\
                     \n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n\
                     =AAAA\n\
                     -----END PGP SIGNATURE-----{}{}\n\
                     \n\
                     Do a thing\n\
                     \n\
                     Makes some changes to the foo feature\n\
                     ",
                    TEST_COMMIT_MESSAGE_WITH_SIGNATURE_AND_MULTIPLE_PARENTS.len() + 56 + 48,
                    iter::repeat(" ").take(56).collect::<String>(),
                    iter::repeat("\t").take(48).collect::<String>()
                )
                .into_bytes(),
                whitespace_index: 768
            },
            process_commit_message(TEST_COMMIT_MESSAGE_WITH_SIGNATURE_AND_MULTIPLE_PARENTS)
        );
    }

    #[test]
    fn process_commit_message_with_gpg_stuff_in_message() {
        assert_eq!(
            ProcessedCommitMessage {
                full_message: format!(
                    "\
                     commit {}\x00\
                     tree 0123456701234567012345670123456701234567\n\
                     parent 7654321076543210765432107654321076543210\n\
                     author Foo Bár <foo@example.com> 1513980859 -0500\n\
                     committer Baz Qux <baz@example.com> 1513980898 -0500\n\
                     \n\
                     For no particular reason, this commit message looks like a GPG signature.\n\
                     gpgsig -----END PGP SIGNATURE-----\n\
                     \n\
                     So anyway, that's fun.{}{}\n\
                     ",
                    TEST_COMMIT_WITH_GPG_STUFF_IN_MESSAGE.len() + 42 + 48,
                    iter::repeat(" ").take(42).collect::<String>(),
                    iter::repeat("\t").take(48).collect::<String>()
                )
                .into_bytes(),
                whitespace_index: 384
            },
            process_commit_message(TEST_COMMIT_WITH_GPG_STUFF_IN_MESSAGE)
        )
    }

    #[test]
    fn process_commit_message_with_gpg_stuff_in_email() {
        assert_eq!(
            ProcessedCommitMessage {
                full_message: format!(
                    "\
                     commit {}\x00\
                     tree 0123456701234567012345670123456701234567\n\
                     parent 7654321076543210765432107654321076543210\n\
                     author Foo Bár <-----END PGP SIGNATURE-----@example.com> 1513980859 -0500\n\
                     committer Baz Qux <baz@example.com> 1513980898 -0500\n\
                     \n\
                     For no particular reason, the commit author's email has a GPG signature marker.{}{}\n\
                     ",
                    TEST_COMMIT_WITH_GPG_STUFF_IN_EMAIL.len() + 7 + 48,
                    iter::repeat(" ").take(7).collect::<String>(),
                    iter::repeat("\t").take(48).collect::<String>()
                )
                .into_bytes(),
                whitespace_index: 320
            },
            process_commit_message(TEST_COMMIT_WITH_GPG_STUFF_IN_EMAIL)
        )
    }

    #[test]
    fn split_range_u32_one_segment() {
        assert_eq!(vec![0..1u64 << 32], split_range(0, 1u64 << 32, 1));
    }

    #[test]
    fn split_range_u32_multiple_segments() {
        let range_max = 1u64 << 32;
        assert_eq!(
            vec![
                0..range_max / 5,
                range_max / 5..2 * range_max / 5,
                2 * range_max / 5..3 * range_max / 5,
                3 * range_max / 5..4 * range_max / 5,
                4 * range_max / 5..range_max - 1
            ],
            split_range(0, range_max, 5)
        );
    }

    #[test]
    fn split_range_u64_one_segment() {
        assert_eq!(vec![0..u64::MAX], split_range(0, u64::MAX, 1));
    }

    #[test]
    fn split_range_u64_multiple_segments() {
        let range_max = u64::MAX;
        assert_eq!(
            vec![
                0..range_max / 5,
                range_max / 5..range_max / 5 * 2,
                range_max / 5 * 2..range_max / 5 * 3,
                range_max / 5 * 3..range_max / 5 * 4,
                range_max / 5 * 4..range_max
            ],
            split_range(0, range_max, 5)
        );
    }

    #[test]
    fn matches_desired_prefix_empty() {
        assert!(matches_desired_prefix(
            &[0; SHA1_BYTE_LENGTH],
            &HashPrefix {
                data: Vec::new(),
                half_byte: None
            }
        ))
    }

    #[test]
    fn matches_desired_prefix_single_half() {
        assert!(matches_desired_prefix(
            &[0x1e; SHA1_BYTE_LENGTH],
            &HashPrefix {
                data: Vec::new(),
                half_byte: Some(0x10)
            }
        ))
    }

    #[test]
    fn matches_desired_prefix_single_half_mismatch() {
        assert!(!matches_desired_prefix(
            &[0x21; SHA1_BYTE_LENGTH],
            &HashPrefix {
                data: Vec::new(),
                half_byte: Some(0x10)
            }
        ))
    }

    #[test]
    fn matches_desired_prefix_data_without_half() {
        assert!(matches_desired_prefix(
            &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
            &HashPrefix {
                data: vec![1, 2, 3],
                half_byte: None
            }
        ))
    }

    #[test]
    fn matches_desired_prefix_matching_data_and_half() {
        assert!(matches_desired_prefix(
            &[1, 2, 3, 0x4f, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
            &HashPrefix {
                data: vec![1, 2, 3],
                half_byte: Some(0x40)
            }
        ))
    }

    #[test]
    fn matches_desired_prefix_matching_data_mismatching_half() {
        assert!(!matches_desired_prefix(
            &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
            &HashPrefix {
                data: vec![1, 2, 3],
                half_byte: Some(0x50)
            }
        ))
    }

    #[test]
    fn matches_desired_prefix_mismatching_data_matching_half() {
        assert!(!matches_desired_prefix(
            &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
            &HashPrefix {
                data: vec![1, 5, 3],
                half_byte: Some(0x40)
            }
        ))
    }

    #[test]
    fn to_hex_string_basic() {
        assert_eq!("00", to_hex_string(&[0]));
    }

    #[test]
    fn to_hex_string_multichar() {
        assert_eq!("00ff14", to_hex_string(&[0, 255, 20]));
    }
}
