// 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::cmp::{max, min, Ordering};use std::collections::{BTreeMap, HashMap};use std::fmt::{Debug, Formatter};use std::ops::Range;use std::slice; use itertools::Itertools; pub fn find_line_ranges(text: &[u8]) -> Vec<Range<usize>> {    let mut ranges = vec![];    let mut start = 0;    loop {        match text[start..].iter().position(|b| *b == b'\n') {            None => {                break;            }            Some(i) => {                ranges.push(start..start + i + 1);                start += i + 1;            }        }    }    if start < text.len() {        ranges.push(start..text.len());    }    ranges} 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>> {    let mut ranges = vec![];    for (i, b) in text.iter().enumerate() {        if !is_word_byte(*b) {            ranges.push(i..i + 1);        }    }    ranges} struct Histogram<'a> {    word_to_positions: HashMap<&'a [u8], Vec<usize>>,    count_to_words: BTreeMap<usize, Vec<&'a [u8]>>,} impl Histogram<'_> {    fn calculate<'a>(        text: &'a [u8],        ranges: &[Range<usize>],        max_occurrences: usize,    ) -> Histogram<'a> {        let mut word_to_positions: HashMap<&[u8], Vec<usize>> = HashMap::new();        for (i, range) in ranges.iter().enumerate() {            let positions = word_to_positions.entry(&text[range.clone()]).or_default();            // Allow one more than max_occurrences, so we can later skip those with more            // than max_occurrences            if positions.len() <= max_occurrences {                positions.push(i);            }        }        let mut count_to_words: BTreeMap<usize, Vec<&[u8]>> = BTreeMap::new();        for (word, ranges) in &word_to_positions {            count_to_words.entry(ranges.len()).or_default().push(word);        }        Histogram {            word_to_positions,            count_to_words,        }    }} /// 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 ranges among the ones given as arguments. The data between/// those ranges is ignored.pub(crate) fn unchanged_ranges(    left: &[u8],    right: &[u8],    left_ranges: &[Range<usize>],    right_ranges: &[Range<usize>],) -> Vec<(Range<usize>, Range<usize>)> {    if left_ranges.is_empty() || right_ranges.is_empty() {        return vec![];    }     let max_occurrences = 100;    let mut left_histogram = Histogram::calculate(left, left_ranges, max_occurrences);    if *left_histogram.count_to_words.keys().next().unwrap() > max_occurrences {        // If there are very many occurrences of all words, then we just give up.        return vec![];    }    let mut right_histogram = Histogram::calculate(right, right_ranges, 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 mut uncommon_shared_words = vec![];    while !left_histogram.count_to_words.is_empty() && uncommon_shared_words.is_empty() {        let left_words = left_histogram            .count_to_words            .first_entry()            .map(|x| x.remove())            .unwrap();        for left_word in left_words {            if right_histogram.word_to_positions.contains_key(left_word) {                uncommon_shared_words.push(left_word);            }        }    }    if uncommon_shared_words.is_empty() {        return vec![];    }     // Let's say our inputs are "a b a b" and "a b c c b a b". We will have found    // the least common words to be "a" and "b". We now assume that each    // occurrence of each word lines up in the left and right input. We do that    // by numbering the shared occurrences, effectively instead comparing "a1 b1    // a2 b2" and "a1 b1 c c b2 a2 b". We then walk the common words in the    // right input in order (["a1", "b1", "b2", "a2"]), and record the index of    // that word in the left input ([0,1,3,2]). We then find the LCS and split    // points based on that ([0,1,3] or [0,1,2] are both valid).     // [(index into left_ranges, word, occurrence #)]    let mut left_positions = vec![];    let mut right_positions = vec![];    for uncommon_shared_word in uncommon_shared_words {        let left_occurrences = left_histogram            .word_to_positions            .get_mut(uncommon_shared_word)            .unwrap();        let right_occurrences = right_histogram            .word_to_positions            .get_mut(uncommon_shared_word)            .unwrap();        let shared_count = min(left_occurrences.len(), right_occurrences.len());        for occurrence in 0..shared_count {            left_positions.push((                left_occurrences[occurrence],                uncommon_shared_word,                occurrence,            ));            right_positions.push((                right_occurrences[occurrence],                uncommon_shared_word,                occurrence,            ));        }    }    left_positions.sort();    right_positions.sort();    let mut left_position_map = HashMap::new();    for (i, (_pos, word, occurrence)) in left_positions.iter().enumerate() {        left_position_map.insert((*word, *occurrence), i);    }    let mut left_index_by_right_index = vec![];    for (_pos, word, occurrence) in &right_positions {        left_index_by_right_index.push(*left_position_map.get(&(*word, *occurrence)).unwrap());    }     let lcs = find_lcs(&left_index_by_right_index);     // Produce output ranges, recursing into the modified areas between the elements    // in the LCS.    let mut result = vec![];    let mut previous_left_position = 0;    let mut previous_right_position = 0;    for (left_index, right_index) in lcs {        let left_position = left_positions[left_index].0;        let right_position = right_positions[right_index].0;        let skipped_left_positions = previous_left_position..left_position;        let skipped_right_positions = previous_right_position..right_position;        if !skipped_left_positions.is_empty() || !skipped_right_positions.is_empty() {            for unchanged_nested_range in unchanged_ranges(                left,                right,                &left_ranges[skipped_left_positions.clone()],                &right_ranges[skipped_right_positions.clone()],            ) {                result.push(unchanged_nested_range);            }        }        result.push((            left_ranges[left_position].clone(),            right_ranges[right_position].clone(),        ));        previous_left_position = left_position + 1;        previous_right_position = right_position + 1;    }    // Also recurse into range at end (after common ranges).    let skipped_left_positions = previous_left_position..left_ranges.len();    let skipped_right_positions = previous_right_position..right_ranges.len();    if !skipped_left_positions.is_empty() || !skipped_right_positions.is_empty() {        for unchanged_nested_range in unchanged_ranges(            left,            right,            &left_ranges[skipped_left_positions],            &right_ranges[skipped_right_positions],        ) {            result.push(unchanged_nested_range);        }    }     result} #[derive(Clone, PartialEq, Eq, Debug)]struct UnchangedRange {    base_range: Range<usize>,    offsets: Vec<isize>,} impl UnchangedRange {    fn start(&self, side: usize) -> usize {        self.base_range            .start            .wrapping_add(self.offsets[side] as usize)    }     fn end(&self, side: usize) -> usize {        self.base_range            .end            .wrapping_add(self.offsets[side] as usize)    }} impl PartialOrd for UnchangedRange {    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {        Some(self.cmp(other))    }} impl Ord for UnchangedRange {    fn cmp(&self, other: &Self) -> Ordering {        self.base_range            .start            .cmp(&other.base_range.start)            .then_with(|| self.base_range.end.cmp(&other.base_range.end))    }} /// Takes any number of inputs and finds regions that are them same between all/// of them.#[derive(Clone, Debug)]pub struct Diff<'input> {    base_input: &'input [u8],    other_inputs: Vec<&'input [u8]>,    // The key is a range in the base input. The value is the start of each non-base region    // relative to the base region's start. By making them relative, they don't need to change    // when the base range changes.    unchanged_regions: Vec<UnchangedRange>,} /// Takes the current regions and intersects it with the new unchanged ranges/// from a 2-way diff. The result is a map of unchanged regions with one more/// offset in the map's values.fn intersect_regions(    current_ranges: Vec<UnchangedRange>,    new_unchanged_ranges: &[(Range<usize>, Range<usize>)],) -> Vec<UnchangedRange> {    let mut result = vec![];    let mut current_ranges_iter = current_ranges.into_iter().peekable();    for (new_base_range, other_range) in new_unchanged_ranges.iter() {        assert_eq!(new_base_range.len(), other_range.len());        while let Some(UnchangedRange {            base_range,            offsets,        }) = current_ranges_iter.peek()        {            // No need to look further if we're past the new range.            if base_range.start >= new_base_range.end {                break;            }            // Discard any current unchanged regions that don't match between the base and            // the new input.            if base_range.end <= new_base_range.start {                current_ranges_iter.next();                continue;            }            let new_start = max(base_range.start, new_base_range.start);            let new_end = min(base_range.end, new_base_range.end);            let mut new_offsets = offsets.clone();            new_offsets.push(other_range.start.wrapping_sub(new_base_range.start) as isize);            result.push(UnchangedRange {                base_range: new_start..new_end,                offsets: new_offsets,            });            if base_range.end >= new_base_range.end {                // Break without consuming the item; there may be other new ranges that overlap                // with it.                break;            }            current_ranges_iter.next();        }    }    result} impl<'input> Diff<'input> {    pub fn for_tokenizer(        inputs: &[&'input [u8]],        tokenizer: &impl Fn(&[u8]) -> Vec<Range<usize>>,    ) -> Self {        assert!(!inputs.is_empty());        let base_input = inputs[0];        let other_inputs = inputs.iter().skip(1).copied().collect_vec();        // First tokenize each input        let base_token_ranges: Vec<Range<usize>> = tokenizer(base_input);        let other_token_ranges: Vec<Vec<Range<usize>>> = other_inputs            .iter()            .map(|other_input| tokenizer(other_input))            .collect_vec();         // Look for unchanged regions. Initially consider the whole range of the base        // input as unchanged (compared to itself). Then diff each other input        // against the base. Intersect the previously found ranges with the        // unchanged ranges in the diff.        let mut unchanged_regions = vec![UnchangedRange {            base_range: 0..base_input.len(),            offsets: vec![],        }];        for (i, other_token_ranges) in other_token_ranges.iter().enumerate() {            let unchanged_diff_ranges = unchanged_ranges(                base_input,                other_inputs[i],                &base_token_ranges,                other_token_ranges,            );            unchanged_regions = intersect_regions(unchanged_regions, &unchanged_diff_ranges);        }        // Add an empty range at the end to make life easier for hunks().        let offsets = other_inputs            .iter()            .map(|input| input.len().wrapping_sub(base_input.len()) as isize)            .collect_vec();        unchanged_regions.push(UnchangedRange {            base_range: base_input.len()..base_input.len(),            offsets,        });         let mut diff = Self {            base_input,            other_inputs,            unchanged_regions,        };        diff.compact_unchanged_regions();        diff    }     pub fn unrefined(inputs: &[&'input [u8]]) -> Self {        Diff::for_tokenizer(inputs, &|_| vec![])    }     // TODO: At least when merging, it's wasteful to refine the diff if e.g. if 2    // out of 3 inputs match in the differing regions. Perhaps the refine()    // method should be on the hunk instead (probably returning a new Diff)?    // That would let each user decide which hunks to refine. However, it would    // probably mean that many callers repeat the same code. Perhaps it    // should be possible to refine a whole diff *or* individual hunks.    pub fn default_refinement(inputs: &[&'input [u8]]) -> Self {        let mut diff = Diff::for_tokenizer(inputs, &find_line_ranges);        diff.refine_changed_regions(&find_word_ranges);        diff.refine_changed_regions(&find_nonword_ranges);        diff    }     pub fn hunks<'diff>(&'diff self) -> DiffHunkIterator<'diff, 'input> {        let previous_offsets = vec![0; self.other_inputs.len()];        DiffHunkIterator {            diff: self,            previous: UnchangedRange {                base_range: 0..0,                offsets: previous_offsets,            },            unchanged_emitted: true,            unchanged_iter: self.unchanged_regions.iter(),        }    }     /// Uses the given tokenizer to split the changed regions into smaller    /// regions. Then tries to finds unchanged regions among them.    pub fn refine_changed_regions(&mut self, tokenizer: &impl Fn(&[u8]) -> Vec<Range<usize>>) {        let mut previous = UnchangedRange {            base_range: 0..0,            offsets: vec![0; self.other_inputs.len()],        };        let mut new_unchanged_ranges = vec![];        for current in self.unchanged_regions.iter() {            // For the changed region between the previous region and the current one,            // create a new Diff instance. Then adjust the start positions and            // offsets to be valid in the context of the larger Diff instance            // (`self`).            let mut slices =                vec![&self.base_input[previous.base_range.end..current.base_range.start]];            for i in 0..current.offsets.len() {                let changed_range = previous.end(i)..current.start(i);                slices.push(&self.other_inputs[i][changed_range]);            }             let refined_diff = Diff::for_tokenizer(&slices, tokenizer);             for UnchangedRange {                base_range,                offsets,

Lines 1–500 of 1191. Load more