// Copyright 2023 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. //! Generic algorithms for working with merged values, plus specializations for//! some common types of merged values. use std::borrow::Borrow;use std::collections::HashMap;use std::fmt::Debug;use std::fmt::Formatter;use std::fmt::Write as _;use std::hash::Hash;use std::iter::zip;use std::slice;use std::sync::Arc; use itertools::Itertools as _;use smallvec::smallvec_inline;use smallvec::SmallVec; use crate::backend;use crate::backend::BackendResult;use crate::backend::FileId;use crate::backend::TreeId;use crate::backend::TreeValue;use crate::content_hash::ContentHash;use crate::content_hash::DigestUpdate;use crate::repo_path::RepoPath;use crate::store::Store;use crate::tree::Tree; /// Attempt to resolve trivial conflicts between the inputs. There must be/// an odd number of terms.pub fn trivial_merge<T>(values: &[T]) -> Option<&T>where    T: Eq + Hash,{    assert!(        values.len() % 2 == 1,        "trivial_merge() requires an odd number of terms"    );    // Optimize the common cases of 3-way merge and 1-way (non-)merge    if let [add] = values {        return Some(add);    } else if let [add0, remove, add1] = values {        return if add0 == add1 {            Some(add0)        } else if add0 == remove {            Some(add1)        } else if add1 == remove {            Some(add0)        } else {            None        };    }     // Number of occurrences of each value, with positive indexes counted as +1 and    // negative as -1, thereby letting positive and negative terms with the same    // value (i.e. key in the map) cancel each other.    let mut counts: HashMap<&T, i32> = HashMap::new();    for (value, n) in zip(values, [1, -1].into_iter().cycle()) {        counts.entry(value).and_modify(|e| *e += n).or_insert(n);    }     // Collect non-zero value. Values with a count of 0 means that they have    // cancelled out.    counts.retain(|_, count| *count != 0);    if counts.len() == 1 {        // If there is a single value with a count of 1 left, then that is the result.        let (value, count) = counts.into_iter().next().unwrap();        assert_eq!(count, 1);        Some(value)    } else if counts.len() == 2 {        // All sides made the same change.        // This matches what Git and Mercurial do (in the 3-way case at least), but not        // what Darcs does. It means that repeated 3-way merging of multiple trees may        // give different results depending on the order of merging.        // TODO: Consider removing this special case, making the algorithm more strict,        // and maybe add a more lenient version that is used when the user explicitly        // asks for conflict resolution.        let ((value1, count1), (value2, count2)) = counts.into_iter().next_tuple().unwrap();        assert_eq!(count1 + count2, 1);        if count1 > 0 {            Some(value1)        } else {            Some(value2)        }    } else {        None    }} /// A generic representation of merged values.////// There is exactly one more `adds()` than `removes()`. When interpreted as a/// series of diffs, the merge's (i+1)-st add is matched with the i-th/// remove. The zeroth add is considered a diff from the non-existent state.#[derive(PartialEq, Eq, Hash, Clone)]pub struct Merge<T> {    /// Alternates between positive and negative terms, starting with positive.    values: SmallVec<[T; 1]>,} impl<T: Debug> Debug for Merge<T> {    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {        // Format like an enum with two variants to make it less verbose in the common        // case of a resolved state.        if let Some(value) = self.as_resolved() {            f.debug_tuple("Resolved").field(value).finish()        } else {            f.debug_tuple("Conflicted").field(&self.values).finish()        }    }} impl<T> Merge<T> {    /// Creates a `Merge` from the given values, in which positive and negative    /// terms alternate.    pub fn from_vec(values: impl Into<SmallVec<[T; 1]>>) -> Self {        let values = values.into();        assert!(values.len() % 2 != 0, "must have an odd number of terms");        Merge { values }    }     /// Creates a new merge object from the given removes and adds.    pub fn from_removes_adds(        removes: impl IntoIterator<Item = T>,        adds: impl IntoIterator<Item = T>,    ) -> Self {        let removes = removes.into_iter();        let mut adds = adds.into_iter();        let mut values = SmallVec::with_capacity(removes.size_hint().0 * 2 + 1);        values.push(adds.next().expect("must have at least one add"));        for diff in removes.zip_longest(adds) {            let (remove, add) = diff.both().expect("must have one more adds than removes");            values.extend([remove, add]);        }        Merge { values }    }     /// Creates a `Merge` with a single resolved value.    pub fn resolved(value: T) -> Self {        Merge {            values: smallvec_inline![value],        }    }     /// Create a `Merge` from a `removes` and `adds`, padding with `None` to    /// make sure that there is exactly one more `adds` than `removes`.    pub fn from_legacy_form(        removes: impl IntoIterator<Item = T>,        adds: impl IntoIterator<Item = T>,    ) -> Merge<Option<T>> {        let removes = removes.into_iter();        let mut adds = adds.into_iter().fuse();        let mut values = smallvec_inline![adds.next()];        for diff in removes.zip_longest(adds) {            let (remove, add) = diff.map_any(Some, Some).or_default();            values.extend([remove, add]);        }        Merge { values }    }     /// The removed values, also called negative terms.    pub fn removes(&self) -> impl ExactSizeIterator<Item = &T> {        self.values[1..].iter().step_by(2)    }     /// The added values, also called positive terms.    pub fn adds(&self) -> impl ExactSizeIterator<Item = &T> {        self.values.iter().step_by(2)    }     /// Returns the zeroth added value, which is guaranteed to exist.    pub fn first(&self) -> &T {        &self.values[0]    }     /// Returns the `index`-th removed value, which is considered belonging to    /// the `index`-th diff pair.    pub fn get_remove(&self, index: usize) -> Option<&T> {        self.values.get(index * 2 + 1)    }     /// Returns the `index`-th added value, which is considered belonging to the    /// `index-1`-th diff pair. The zeroth add is a diff from the non-existent    /// state.    pub fn get_add(&self, index: usize) -> Option<&T> {        self.values.get(index * 2)    }     /// Removes the specified "removed"/"added" values. The removed slots are    /// replaced by the last "removed"/"added" values.    pub fn swap_remove(&mut self, remove_index: usize, add_index: usize) -> (T, T) {        // Swap with the last "added" and "removed" values in order.        let add = self.values.swap_remove(add_index * 2);        let remove = self.values.swap_remove(remove_index * 2 + 1);        (remove, add)    }     /// The number of positive terms in the conflict.    pub fn num_sides(&self) -> usize {        self.values.len() / 2 + 1    }     /// Whether this merge is resolved. Does not resolve trivial merges.    pub fn is_resolved(&self) -> bool {        self.values.len() == 1    }     /// Returns the resolved value, if this merge is resolved. Does not    /// resolve trivial merges.    pub fn as_resolved(&self) -> Option<&T> {        if let [value] = &self.values[..] {            Some(value)        } else {            None        }    }     /// Returns the resolved value, if this merge is resolved. Otherwise returns    /// the merge itself as an `Err`. Does not resolve trivial merges.    pub fn into_resolved(mut self) -> Result<T, Merge<T>> {        if self.values.len() == 1 {            Ok(self.values.pop().unwrap())        } else {            Err(self)        }    }     /// Returns a vector mapping of a value's index in the simplified merge to    /// its original index in the unsimplified merge.    ///    /// The merge is simplified by removing identical values in add and remove    /// values.    fn get_simplified_mapping(&self) -> Vec<usize>    where        T: PartialEq,    {        let unsimplified_len = self.values.len();        let mut simplified_to_original_indices = (0..unsimplified_len).collect_vec();         let mut add_index = 0;        while add_index < simplified_to_original_indices.len() {            let add = &self.values[simplified_to_original_indices[add_index]];            let mut remove_indices = simplified_to_original_indices                .iter()                .enumerate()                .skip(1)                .step_by(2);            if let Some((remove_index, _)) = remove_indices                .find(|&(_, original_remove_index)| &self.values[*original_remove_index] == add)            {                // Align the current "add" value to the `remove_index/2`-th diff, then                // delete the diff pair.                simplified_to_original_indices.swap(remove_index + 1, add_index);                simplified_to_original_indices.drain(remove_index..remove_index + 2);            } else {                add_index += 2;            }        }         simplified_to_original_indices    }     /// Simplify the merge by joining diffs like A->B and B->C into A->C.    /// Also drops trivial diffs like A->A.    pub fn simplify(mut self) -> Self    where        T: PartialEq + Clone,    {        let mapping = self.get_simplified_mapping();        // Reorder values based on their new indices in the simplified merge.        self.values = mapping            .iter()            .map(|index| self.values[*index].clone())            .collect();        self    }     /// Updates the merge based on the given simplified merge.    pub fn update_from_simplified(mut self, simplified: Merge<T>) -> Self    where        T: PartialEq,    {        let mapping = self.get_simplified_mapping();        assert_eq!(mapping.len(), simplified.values.len());        for (index, value) in mapping.into_iter().zip(simplified.values.into_iter()) {            self.values[index] = value;        }        self    }     /// If this merge can be trivially resolved, returns the value it resolves    /// to.    pub fn resolve_trivial(&self) -> Option<&T>    where        T: Eq + Hash,    {        trivial_merge(&self.values)    }     /// Pads this merge with to the specified number of sides with the specified    /// value. No-op if the requested size is not larger than the current size.    pub fn pad_to(&mut self, num_sides: usize, value: &T)    where        T: Clone,    {        if num_sides <= self.num_sides() {            return;        }        self.values.resize(num_sides * 2 - 1, value.clone());    }     /// Returns a slice containing the terms. The items will alternate between    /// positive and negative terms, starting with positive (since there's one    /// more of those).    pub fn as_slice(&self) -> &[T] {        &self.values    }     /// Returns an iterator over references to the terms. The items will    /// alternate between positive and negative terms, starting with    /// positive (since there's one more of those).    pub fn iter(&self) -> slice::Iter<'_, T> {        self.values.iter()    }     /// A version of `Merge::iter()` that iterates over mutable references.    pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> {        self.values.iter_mut()    }     /// Creates a new merge by applying `f` to each remove and add.    pub fn map<'a, U>(&'a self, f: impl FnMut(&'a T) -> U) -> Merge<U> {        let values = self.values.iter().map(f).collect();        Merge { values }    }     /// Creates a new merge by applying `f` to each remove and add, returning    /// `None if `f` returns `None` for any of them.    pub fn maybe_map<'a, U>(&'a self, f: impl FnMut(&'a T) -> Option<U>) -> Option<Merge<U>> {        let values = self.values.iter().map(f).collect::<Option<_>>()?;        Some(Merge { values })    }     /// Creates a new merge by applying `f` to each remove and add, returning    /// `Err if `f` returns `Err` for any of them.    pub fn try_map<'a, U, E>(        &'a self,        f: impl FnMut(&'a T) -> Result<U, E>,    ) -> Result<Merge<U>, E> {        let values = self.values.iter().map(f).try_collect()?;        Ok(Merge { values })    }} /// Helper for consuming items from an iterator and then creating a `Merge`.////// By not collecting directly into `Merge`, we can avoid creating invalid/// instances of it. If we had `Merge::from_iter()` we would need to allow it to/// accept iterators of any length (including 0). We couldn't make it panic on/// even lengths because we can get passed such iterators from e.g./// `Option::from_iter()`. By collecting into `MergeBuilder` instead, we move/// the checking until after `from_iter()` (to `MergeBuilder::build()`).#[derive(Clone, Debug, PartialEq, Eq)]pub struct MergeBuilder<T> {    values: SmallVec<[T; 1]>,} impl<T> Default for MergeBuilder<T> {    fn default() -> Self {        Self {            values: Default::default(),        }    }} impl<T> MergeBuilder<T> {    /// Requires that exactly one more "adds" than "removes" have been added to    /// this builder.    pub fn build(self) -> Merge<T> {        Merge::from_vec(self.values)    }} impl<T> IntoIterator for Merge<T> {    type Item = T;    type IntoIter = smallvec::IntoIter<[T; 1]>;     fn into_iter(self) -> Self::IntoIter {        self.values.into_iter()    }} impl<T> FromIterator<T> for MergeBuilder<T> {    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {        let mut builder = MergeBuilder::default();        builder.extend(iter);        builder    }} impl<T> Extend<T> for MergeBuilder<T> {    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {        self.values.extend(iter);    }} impl<T> Merge<Option<T>> {    /// Creates a resolved merge with a value of `None`.    pub fn absent() -> Self {        Self::resolved(None)    }     /// Creates a resolved merge with a value of `Some(value)`.    pub fn normal(value: T) -> Self {        Self::resolved(Some(value))    }     /// Whether this represents a resolved value of `None`.    pub fn is_absent(&self) -> bool {        matches!(self.as_resolved(), Some(None))    }     /// The opposite of `is_absent()`.    pub fn is_present(&self) -> bool {        !self.is_absent()    }     /// Returns the value if this is present and non-conflicting.    pub fn as_normal(&self) -> Option<&T> {        self.as_resolved()?.as_ref()    }     /// Creates lists of `removes` and `adds` from a `Merge` by dropping    /// `None` values. Note that the conversion is lossy: the order of `None`    /// values is not preserved when converting back to a `Merge`.    pub fn into_legacy_form(self) -> (Vec<T>, Vec<T>) {        // Allocate the maximum size assuming there would be few `None`s.        let mut removes = Vec::with_capacity(self.values.len() / 2);        let mut adds = Vec::with_capacity(self.values.len() / 2 + 1);        let mut values = self.values.into_iter();        adds.extend(values.next().unwrap());        while let Some(remove) = values.next() {            removes.extend(remove);            adds.extend(values.next().unwrap());        }        (removes, adds)    }} impl<T: Clone> Merge<Option<&T>> {    /// Creates a new merge by cloning inner `Option<&T>`s.    pub fn cloned(&self) -> Merge<Option<T>> {        self.map(|value| value.cloned())    }} impl<T> Merge<Merge<T>> {    /// Flattens a nested merge into a regular merge.    ///    /// Let's say we have a 3-way merge of 3-way merges like this:    ///    /// 4 5   7 8    ///  3     6    ///    1 2    ///     0    ///    /// Flattening that results in this 9-way merge:    ///    /// 4 5 0 7 8    ///  3 2 1 6    pub fn flatten(self) -> Merge<T> {        let mut outer_values = self.values.into_iter();        let mut result = outer_values.next().unwrap();        while let Some(mut remove) = outer_values.next() {            // Add removes reversed, and with the first element moved last, so we preserve            // the diffs            remove.values.rotate_left(1);            for i in 0..remove.values.len() / 2 {                remove.values.swap(i * 2, i * 2 + 1);            }            result.values.extend(remove.values);            let add = outer_values.next().unwrap();            result.values.extend(add.values);        }        result    }

Lines 1–500 of 1170. Load more