// Copyright 2021 The Jujutsu Authors//// Licensed under the Apache License, Version 2.0 (the "License");// you may not use this file except in compliance with the License.// You may obtain a copy of the License at//// https://www.apache.org/licenses/LICENSE-2.0//// Unless required by applicable law or agreed to in writing, software// distributed under the License is distributed on an "AS IS" BASIS,// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.// See the License for the specific language governing permissions and// limitations under the License. #![allow(missing_docs)] use std::collections::BTreeMap;use std::hash::BuildHasher;use std::hash::Hash;use std::hash::Hasher;use std::hash::RandomState;use std::iter;use std::ops::Range;use std::slice; use bstr::BStr;use hashbrown::HashTable;use itertools::Itertools as _;use smallvec::SmallVec;use smallvec::smallvec; pub fn find_line_ranges(text: &[u8]) -> Vec<Range<usize>> {    text.split_inclusive(|b| *b == b'\n')        .scan(0, |total, line| {            let start = *total;            *total += line.len();            Some(start..*total)        })        .collect()} fn is_word_byte(b: u8) -> bool {    // TODO: Make this configurable (probably higher up in the call stack)    matches!(        b,        // Count 0x80..0xff as word bytes so multi-byte UTF-8 chars are        // treated as a single unit.        b'A'..=b'Z' | b'a'..=b'z' | b'0'..=b'9' | b'_' | b'\x80'..=b'\xff'    )} pub fn find_word_ranges(text: &[u8]) -> Vec<Range<usize>> {    let mut word_ranges = vec![];    let mut word_start_pos = 0;    let mut in_word = false;    for (i, b) in text.iter().enumerate() {        if in_word && !is_word_byte(*b) {            in_word = false;            word_ranges.push(word_start_pos..i);            word_start_pos = i;        } else if !in_word && is_word_byte(*b) {            in_word = true;            word_start_pos = i;        }    }    if in_word && word_start_pos < text.len() {        word_ranges.push(word_start_pos..text.len());    }    word_ranges} pub fn find_nonword_ranges(text: &[u8]) -> Vec<Range<usize>> {    text.iter()        .positions(|b| !is_word_byte(*b))        .map(|i| i..i + 1)        .collect()} fn bytes_ignore_all_whitespace(text: &[u8]) -> impl Iterator<Item = u8> + use<'_> {    text.iter().copied().filter(|b| !b.is_ascii_whitespace())} fn bytes_ignore_whitespace_amount(text: &[u8]) -> impl Iterator<Item = u8> + use<'_> {    let mut prev_was_space = false;    text.iter().filter_map(move |&b| {        let was_space = prev_was_space;        let is_space = b.is_ascii_whitespace();        prev_was_space = is_space;        match (was_space, is_space) {            (_, false) => Some(b),            (false, true) => Some(b' '),            (true, true) => None,        }    })} fn hash_with_length_suffix<I, H>(data: I, state: &mut H)where    I: IntoIterator,    I::Item: Hash,    H: Hasher,{    let mut len: usize = 0;    for d in data {        d.hash(state);        len += 1;    }    state.write_usize(len);} /// Compares byte sequences based on a certain equivalence property.////// This isn't a newtype `Wrapper<'a>(&'a [u8])` but an external comparison/// object for the following reasons:////// a. If it were newtype, a generic `wrap` function would be needed. It///    couldn't be expressed as a simple closure:///    `for<'a> Fn(&'a [u8]) -> ???<'a>`/// b. Dynamic comparison object can be implemented intuitively. For example,///    `pattern: &Regex` would have to be copied to all newtype instances if it///    were newtype./// c. Hash values can be cached if hashing is controlled externally.pub trait CompareBytes {    /// Returns true if `left` and `right` are equivalent.    fn eq(&self, left: &[u8], right: &[u8]) -> bool;     /// Generates hash which respects the following property:    /// `eq(left, right) => hash(left) == hash(right)`    fn hash<H: Hasher>(&self, text: &[u8], state: &mut H);} // An instance might have e.g. Regex pattern, which can't be trivially copied.// Such comparison object can be passed by reference.impl<C: CompareBytes + ?Sized> CompareBytes for &C {    fn eq(&self, left: &[u8], right: &[u8]) -> bool {        <C as CompareBytes>::eq(self, left, right)    }     fn hash<H: Hasher>(&self, text: &[u8], state: &mut H) {        <C as CompareBytes>::hash(self, text, state);    }} /// Compares byte sequences literally.#[derive(Clone, Debug, Default)]pub struct CompareBytesExactly; impl CompareBytes for CompareBytesExactly {    fn eq(&self, left: &[u8], right: &[u8]) -> bool {        left == right    }     fn hash<H: Hasher>(&self, text: &[u8], state: &mut H) {        text.hash(state);    }} /// Compares byte sequences ignoring any whitespace occurrences.#[derive(Clone, Debug, Default)]pub struct CompareBytesIgnoreAllWhitespace; impl CompareBytes for CompareBytesIgnoreAllWhitespace {    fn eq(&self, left: &[u8], right: &[u8]) -> bool {        bytes_ignore_all_whitespace(left).eq(bytes_ignore_all_whitespace(right))    }     fn hash<H: Hasher>(&self, text: &[u8], state: &mut H) {        hash_with_length_suffix(bytes_ignore_all_whitespace(text), state);    }} /// Compares byte sequences ignoring changes in whitespace amount.#[derive(Clone, Debug, Default)]pub struct CompareBytesIgnoreWhitespaceAmount; impl CompareBytes for CompareBytesIgnoreWhitespaceAmount {    fn eq(&self, left: &[u8], right: &[u8]) -> bool {        bytes_ignore_whitespace_amount(left).eq(bytes_ignore_whitespace_amount(right))    }     fn hash<H: Hasher>(&self, text: &[u8], state: &mut H) {        hash_with_length_suffix(bytes_ignore_whitespace_amount(text), state);    }} // Not implementing Eq because the text should be compared by WordComparator.#[derive(Clone, Copy, Debug)]struct HashedWord<'input> {    hash: u64,    text: &'input BStr,} /// Compares words (or tokens) under a certain hasher configuration.#[derive(Clone, Debug, Default)]struct WordComparator<C, S> {    compare: C,    hash_builder: S,} impl<C: CompareBytes> WordComparator<C, RandomState> {    fn new(compare: C) -> Self {        Self {            compare,            // TODO: switch to ahash for better performance?            hash_builder: RandomState::new(),        }    }} impl<C: CompareBytes, S: BuildHasher> WordComparator<C, S> {    fn eq(&self, left: &[u8], right: &[u8]) -> bool {        self.compare.eq(left, right)    }     fn eq_hashed(&self, left: HashedWord<'_>, right: HashedWord<'_>) -> bool {        left.hash == right.hash && self.compare.eq(left.text, right.text)    }     fn hash_one(&self, text: &[u8]) -> u64 {        let mut state = self.hash_builder.build_hasher();        self.compare.hash(text, &mut state);        state.finish()    }} /// Index in a list of word (or token) ranges in `DiffSource`.#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]struct WordPosition(usize); /// Index in a list of word (or token) ranges in `LocalDiffSource`.#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]struct LocalWordPosition(usize); #[derive(Clone, Debug)]struct DiffSource<'input, 'aux> {    text: &'input BStr,    ranges: &'aux [Range<usize>],    hashes: Vec<u64>,} impl<'input, 'aux> DiffSource<'input, 'aux> {    fn new<T: AsRef<[u8]> + ?Sized, C: CompareBytes, S: BuildHasher>(        text: &'input T,        ranges: &'aux [Range<usize>],        comp: &WordComparator<C, S>,    ) -> Self {        let text = BStr::new(text);        let hashes = ranges            .iter()            .map(|range| comp.hash_one(&text[range.clone()]))            .collect();        Self {            text,            ranges,            hashes,        }    }     fn local(&self) -> LocalDiffSource<'input, '_> {        LocalDiffSource {            text: self.text,            ranges: self.ranges,            hashes: &self.hashes,            global_offset: WordPosition(0),        }    }     fn range_at(&self, position: WordPosition) -> Range<usize> {        self.ranges[position.0].clone()    }} #[derive(Clone, Debug)]struct LocalDiffSource<'input, 'aux> {    text: &'input BStr,    ranges: &'aux [Range<usize>],    hashes: &'aux [u64],    /// The number of preceding word ranges excluded from the self `ranges`.    global_offset: WordPosition,} impl<'input> LocalDiffSource<'input, '_> {    fn narrowed(&self, positions: Range<LocalWordPosition>) -> Self {        Self {            text: self.text,            ranges: &self.ranges[positions.start.0..positions.end.0],            hashes: &self.hashes[positions.start.0..positions.end.0],            global_offset: self.map_to_global(positions.start),        }    }     fn map_to_global(&self, position: LocalWordPosition) -> WordPosition {        WordPosition(self.global_offset.0 + position.0)    }     fn hashed_words(        &self,    ) -> impl DoubleEndedIterator<Item = HashedWord<'input>> + ExactSizeIterator + use<'_, 'input>    {        iter::zip(self.ranges, self.hashes).map(|(range, &hash)| {            let text = &self.text[range.clone()];            HashedWord { hash, text }        })    }} struct Histogram<'input> {    word_to_positions: HashTable<HistogramEntry<'input>>,} // Many of the words are unique. We can inline up to 2 word positions (16 bytes// on 64-bit platform) in SmallVec for free.type HistogramEntry<'input> = (HashedWord<'input>, SmallVec<[LocalWordPosition; 2]>); impl<'input> Histogram<'input> {    fn calculate<C: CompareBytes, S: BuildHasher>(        source: &LocalDiffSource<'input, '_>,        comp: &WordComparator<C, S>,        max_occurrences: usize,    ) -> Self {        let mut word_to_positions: HashTable<HistogramEntry> = HashTable::new();        for (i, word) in source.hashed_words().enumerate() {            let pos = LocalWordPosition(i);            word_to_positions                .entry(                    word.hash,                    |(w, _)| comp.eq(w.text, word.text),                    |(w, _)| w.hash,                )                .and_modify(|(_, positions)| {                    // Allow one more than max_occurrences, so we can later skip                    // those with more than max_occurrences                    if positions.len() <= max_occurrences {                        positions.push(pos);                    }                })                .or_insert_with(|| (word, smallvec![pos]));        }        Self { word_to_positions }    }     fn build_count_to_entries(&self) -> BTreeMap<usize, Vec<&HistogramEntry<'input>>> {        let mut count_to_entries: BTreeMap<usize, Vec<_>> = BTreeMap::new();        for entry in &self.word_to_positions {            let (_, positions) = entry;            let entries = count_to_entries.entry(positions.len()).or_default();            entries.push(entry);        }        count_to_entries    }     fn positions_by_word<C: CompareBytes, S: BuildHasher>(        &self,        word: HashedWord<'input>,        comp: &WordComparator<C, S>,    ) -> Option<&[LocalWordPosition]> {        let (_, positions) = self            .word_to_positions            .find(word.hash, |(w, _)| comp.eq(w.text, word.text))?;        Some(positions)    }} /// Finds the LCS given a array where the value of `input[i]` indicates that/// the position of element `i` in the right array is at position `input[i]` in/// the left array.////// For example (some have multiple valid outputs):////// [0,1,2] => [(0,0),(1,1),(2,2)]/// [2,1,0] => [(0,2)]/// [0,1,4,2,3,5,6] => [(0,0),(1,1),(2,3),(3,4),(5,5),(6,6)]/// [0,1,4,3,2,5,6] => [(0,0),(1,1),(4,2),(5,5),(6,6)]fn find_lcs(input: &[usize]) -> Vec<(usize, usize)> {    if input.is_empty() {        return vec![];    }     let mut chain = vec![(0, 0, 0); input.len()];    let mut global_longest = 0;    let mut global_longest_right_pos = 0;    for (right_pos, &left_pos) in input.iter().enumerate() {        let mut longest_from_here = 1;        let mut previous_right_pos = usize::MAX;        for i in (0..right_pos).rev() {            let (previous_len, previous_left_pos, _) = chain[i];            if previous_left_pos < left_pos {                let len = previous_len + 1;                if len > longest_from_here {                    longest_from_here = len;                    previous_right_pos = i;                    if len > global_longest {                        global_longest = len;                        global_longest_right_pos = right_pos;                        // If this is the longest chain globally so far, we cannot find a                        // longer one by using a previous value, so break early.                        break;                    }                }            }        }        chain[right_pos] = (longest_from_here, left_pos, previous_right_pos);    }     let mut result = vec![];    let mut right_pos = global_longest_right_pos;    loop {        let (_, left_pos, previous_right_pos) = chain[right_pos];        result.push((left_pos, right_pos));        if previous_right_pos == usize::MAX {            break;        }        right_pos = previous_right_pos;    }    result.reverse();     result} /// Finds unchanged word (or token) positions among the ones given as/// arguments. The data between those words is ignored.fn collect_unchanged_words<C: CompareBytes, S: BuildHasher>(    found_positions: &mut Vec<(WordPosition, WordPosition)>,    left: &LocalDiffSource,    right: &LocalDiffSource,    comp: &WordComparator<C, S>,) {    if left.ranges.is_empty() || right.ranges.is_empty() {        return;    }     // Prioritize LCS-based algorithm than leading/trailing matches    let old_len = found_positions.len();    collect_unchanged_words_lcs(found_positions, left, right, comp);    if found_positions.len() != old_len {        return;    }     // Trim leading common ranges (i.e. grow previous unchanged region)    let common_leading_len = iter::zip(left.hashed_words(), right.hashed_words())        .take_while(|&(l, r)| comp.eq_hashed(l, r))        .count();    let left_hashed_words = left.hashed_words().skip(common_leading_len);    let right_hashed_words = right.hashed_words().skip(common_leading_len);     // Trim trailing common ranges (i.e. grow next unchanged region)    let common_trailing_len = iter::zip(left_hashed_words.rev(), right_hashed_words.rev())        .take_while(|&(l, r)| comp.eq_hashed(l, r))        .count();     found_positions.extend(itertools::chain(        (0..common_leading_len).map(|i| {            (                left.map_to_global(LocalWordPosition(i)),                right.map_to_global(LocalWordPosition(i)),            )        }),        (1..=common_trailing_len).rev().map(|i| {            (                left.map_to_global(LocalWordPosition(left.ranges.len() - i)),                right.map_to_global(LocalWordPosition(right.ranges.len() - i)),            )        }),    ));} fn collect_unchanged_words_lcs<C: CompareBytes, S: BuildHasher>(    found_positions: &mut Vec<(WordPosition, WordPosition)>,    left: &LocalDiffSource,    right: &LocalDiffSource,    comp: &WordComparator<C, S>,) {    let max_occurrences = 100;    let left_histogram = Histogram::calculate(left, comp, max_occurrences);    let left_count_to_entries = left_histogram.build_count_to_entries();    if *left_count_to_entries.keys().next().unwrap() > max_occurrences {        // If there are very many occurrences of all words, then we just give up.        return;    }    let right_histogram = Histogram::calculate(right, comp, max_occurrences);    // Look for words with few occurrences in `left` (could equally well have picked    // `right`?). If any of them also occur in `right`, then we add the words to    // the LCS.    let Some(uncommon_shared_word_positions) =        left_count_to_entries.values().find_map(|left_entries| {            let mut both_positions = left_entries                .iter()                .filter_map(|&(word, left_positions)| {                    let right_positions = right_histogram.positions_by_word(*word, comp)?;                    (left_positions.len() == right_positions.len())                        .then_some((left_positions, right_positions))                })                .peekable();            both_positions.peek().is_some().then_some(both_positions)        })    else {        return;    };     // [(index into ranges, serial to identify {word, occurrence #})]

Lines 1–500 of 1776. Load more