// Modified for gitoxide from the upstream imara-diff crate.// Upstream source: git cat-file -p 32d1e45d3df061e6ccba6db7fdce92db29e345d8:src/util.rs use crate::Hunk;use crate::intern::Token; /// Computes the number of common tokens at the start of two sequences.pub fn common_prefix(file1: &[Token], file2: &[Token]) -> u32 {    let mut off = 0;    for (token1, token2) in file1.iter().zip(file2) {        if token1 != token2 {            break;        }        off += 1;    }    off} /// Computes the number of common tokens at the end of two sequences.pub fn common_postfix(file1: &[Token], file2: &[Token]) -> u32 {    let mut off = 0;    for (token1, token2) in file1.iter().rev().zip(file2.iter().rev()) {        if token1 != token2 {            break;        }        off += 1;    }    off} /// Computes both the common prefix and postfix lengths of two sequences.pub fn common_edges(file1: &[Token], file2: &[Token]) -> (u32, u32) {    let prefix = common_prefix(file1, file2);    let postfix = common_postfix(&file1[prefix as usize..], &file2[prefix as usize..]);    (prefix, postfix)} /// Removes the common prefix from both sequences and returns its length.pub fn strip_common_prefix(file1: &mut &[Token], file2: &mut &[Token]) -> u32 {    let off = common_prefix(file1, file2);    *file1 = &file1[off as usize..];    *file2 = &file2[off as usize..];    off} /// Removes the common postfix from both sequences and returns its length.pub fn strip_common_postfix(file1: &mut &[Token], file2: &mut &[Token]) -> u32 {    let off = common_postfix(file1, file2);    *file1 = &file1[..file1.len() - off as usize];    *file2 = &file2[..file2.len() - off as usize];    off} /// Computes an approximation of the square root using bit operations.pub fn sqrt(val: usize) -> u32 {    let nbits = (usize::BITS - val.leading_zeros()) / 2;    1 << nbits} impl Hunk {    pub(crate) fn next_hunk(&mut self, removed: &[bool], added: &[bool]) -> bool {        let Some(off) = find_next_change(added, self.after.end) else {            return false;        };        let mut off_before = 0;        loop {            debug_assert!(                removed.len() as u32 != self.before.end || off == 0,                "broken hunk alignment {self:?} "            );            let unchanged_tokens =                find_next_change(removed, self.before.end).unwrap_or(removed.len() as u32 - self.before.end);            if off_before + unchanged_tokens > off {                self.before.start = self.before.end + (off - off_before);                self.before.end = self.before.start;                break;            }            off_before += unchanged_tokens;            self.before.start = self.before.end + unchanged_tokens;            self.before.end = find_hunk_end(removed, self.before.end + unchanged_tokens);            if off_before == off {                break;            }        }        self.after.start = self.after.end + off;        self.after.end = find_hunk_end(added, self.after.start);        true    }} /// Finds the offset to the next changed token starting from the given position.pub fn find_next_change(changes: &[bool], pos: u32) -> Option<u32> {    changes[pos as usize..]        .iter()        .position(|&changed| changed)        .map(|off| off as u32)} /// Finds the end position of a hunk of changed tokens starting from the given position.pub fn find_hunk_end(changes: &[bool], pos: u32) -> u32 {    pos + changes[pos as usize..].iter().take_while(|&&changed| changed).count() as u32} /// Finds the start position of a hunk of changed tokens ending at the given position.pub fn find_hunk_start(changes: &[bool], pos: u32) -> u32 {    pos - changes[..pos as usize]        .iter()        .rev()        .take_while(|&&changed| changed)        .count() as u32}