// 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;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> + '_ {    text.iter().copied().filter(|b| !b.is_ascii_whitespace())} fn bytes_ignore_whitespace_amount(text: &[u8]) -> impl Iterator<Item = u8> + '_ {    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);    }} /// 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 {        WordComparator {            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 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.#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]struct WordPosition(usize); #[derive(Clone, Debug)]struct DiffSource<'input, 'aux> {    text: &'input BStr,    ranges: &'aux [Range<usize>],    /// The number of preceding word ranges excluded from the self `ranges`.    global_offset: WordPosition,} impl<'input, 'aux> DiffSource<'input, 'aux> {    fn new<T: AsRef<[u8]> + ?Sized>(text: &'input T, ranges: &'aux [Range<usize>]) -> Self {        DiffSource {            text: BStr::new(text),            ranges,            global_offset: WordPosition(0),        }    }     fn narrowed(&self, positions: Range<WordPosition>) -> Self {        DiffSource {            text: self.text,            ranges: &self.ranges[positions.start.0..positions.end.0],            global_offset: self.map_to_global(positions.start),        }    }     fn range_at(&self, position: WordPosition) -> Range<usize> {        self.ranges[position.0].clone()    }     fn map_to_global(&self, position: WordPosition) -> WordPosition {        WordPosition(self.global_offset.0 + position.0)    }} struct Histogram<'input> {    word_to_positions: HashTable<HistogramEntry<'input>>,} type HistogramEntry<'input> = (&'input BStr, Vec<WordPosition>); impl<'input> Histogram<'input> {    fn calculate<C: CompareBytes, S: BuildHasher>(        source: &DiffSource<'input, '_>,        comp: &WordComparator<C, S>,        max_occurrences: usize,    ) -> Self {        let mut word_to_positions: HashTable<HistogramEntry> = HashTable::new();        for (i, range) in source.ranges.iter().enumerate() {            let word = &source.text[range.clone()];            let hash = comp.hash_one(word);            let (_, positions) = word_to_positions                .entry(hash, |(w, _)| comp.eq(w, word), |(w, _)| comp.hash_one(w))                .or_insert_with(|| (word, vec![]))                .into_mut();            // Allow one more than max_occurrences, so we can later skip those with more            // than max_occurrences            if positions.len() <= max_occurrences {                positions.push(WordPosition(i));            }        }        Histogram { 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: &BStr,        comp: &WordComparator<C, S>,    ) -> Option<&[WordPosition]> {        let hash = comp.hash_one(word);        let (_, positions) = self            .word_to_positions            .find(hash, |(w, _)| comp.eq(w, word))?;        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: &DiffSource,    right: &DiffSource,    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.ranges, right.ranges)        .take_while(|&(l, r)| comp.eq(&left.text[l.clone()], &right.text[r.clone()]))        .count();    let left_ranges = &left.ranges[common_leading_len..];    let right_ranges = &right.ranges[common_leading_len..];     // Trim trailing common ranges (i.e. grow next unchanged region)    let common_trailing_len = iter::zip(left_ranges.iter().rev(), right_ranges.iter().rev())        .take_while(|&(l, r)| comp.eq(&left.text[l.clone()], &right.text[r.clone()]))        .count();     found_positions.extend(itertools::chain(        (0..common_leading_len).map(|i| {            (                left.map_to_global(WordPosition(i)),                right.map_to_global(WordPosition(i)),            )        }),        (1..=common_trailing_len).rev().map(|i| {            (                left.map_to_global(WordPosition(left.ranges.len() - i)),                right.map_to_global(WordPosition(right.ranges.len() - i)),            )        }),    ));} fn collect_unchanged_words_lcs<C: CompareBytes, S: BuildHasher>(    found_positions: &mut Vec<(WordPosition, WordPosition)>,    left: &DiffSource,    right: &DiffSource,    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 #})]    let (mut left_positions, mut right_positions): (Vec<_>, Vec<_>) =        uncommon_shared_word_positions            .flat_map(|(lefts, rights)| iter::zip(lefts, rights))            .enumerate()            .map(|(serial, (&left_pos, &right_pos))| ((left_pos, serial), (right_pos, serial)))            .unzip();    left_positions.sort_unstable_by_key(|&(pos, _serial)| pos);    right_positions.sort_unstable_by_key(|&(pos, _serial)| pos);    let left_index_by_right_index: Vec<usize> = {        let mut left_index_map = vec![0; left_positions.len()];        for (i, &(_pos, serial)) in left_positions.iter().enumerate() {            left_index_map[serial] = i;        }        right_positions            .iter()            .map(|&(_pos, serial)| left_index_map[serial])            .collect()    };     let lcs = find_lcs(&left_index_by_right_index);     // Produce output word positions, recursing into the modified areas between    // the elements in the LCS.    let mut previous_left_position = WordPosition(0);    let mut previous_right_position = WordPosition(0);    for (left_index, right_index) in lcs {        let (left_position, _) = left_positions[left_index];        let (right_position, _) = right_positions[right_index];        collect_unchanged_words(            found_positions,            &left.narrowed(previous_left_position..left_position),            &right.narrowed(previous_right_position..right_position),            comp,        );        found_positions.push((            left.map_to_global(left_position),            right.map_to_global(right_position),        ));        previous_left_position = WordPosition(left_position.0 + 1);        previous_right_position = WordPosition(right_position.0 + 1);    }    // Also recurse into range at end (after common ranges).    collect_unchanged_words(        found_positions,        &left.narrowed(previous_left_position..WordPosition(left.ranges.len())),        &right.narrowed(previous_right_position..WordPosition(right.ranges.len())),        comp,    );} /// Intersects two sorted sequences of `(base, other)` word positions by/// `base`. `base` positions should refer to the same source text.fn intersect_unchanged_words(    current_positions: Vec<(WordPosition, Vec<WordPosition>)>,    new_positions: &[(WordPosition, WordPosition)],) -> Vec<(WordPosition, Vec<WordPosition>)> {    itertools::merge_join_by(        current_positions,        new_positions,

Lines 1–500 of 1712. Load more