// 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;use std::iter::zip;use std::ops::Deref;use std::slice;use std::sync::Arc; use futures::future::try_join_all;use itertools::Itertools as _;use smallvec::SmallVec;use smallvec::smallvec;use smallvec::smallvec_inline; use crate::backend::BackendResult;use crate::backend::CopyId;use crate::backend::FileId;use crate::backend::TreeValue;use crate::conflict_labels::ConflictLabels;use crate::content_hash::ContentHash;use crate::content_hash::DigestUpdate;use crate::repo_path::RepoPath;use crate::repo_path::RepoPathComponent;use crate::store::Store;use crate::tree::Tree; /// A generic diff/transition from one value to another.////// This is not a diff in the `patch(1)` sense. See `diff::ContentDiff` for/// that.#[derive(Copy, Clone, Debug, PartialEq, Eq)]pub struct Diff<T> { /// The state before pub before: T, /// The state after pub after: T,} impl<T> Diff<T> { /// Create a new diff pub fn new(before: T, after: T) -> Self { Self { before, after } } /// Apply a function to both values pub fn map<U>(self, mut f: impl FnMut(T) -> U) -> Diff<U> { Diff { before: f(self.before), after: f(self.after), } } /// Combine a `Diff<T>` and a `Diff<U>` into a `Diff<(T, U)>`. pub fn zip<U>(self, other: Diff<U>) -> Diff<(T, U)> { Diff { before: (self.before, other.before), after: (self.after, other.after), } } /// Inverts a diff, swapping the before and after terms. pub fn invert(self) -> Self { Self { before: self.after, after: self.before, } } /// Convert a `&Diff<T>` into a `Diff<&T>`. pub fn as_ref(&self) -> Diff<&T> { Diff { before: &self.before, after: &self.after, } } /// Converts a `Diff<T>` or `&Diff<T>` to `Diff<&T::Target>`. (e.g. /// `Diff<String>` to `Diff<&str>`) pub fn as_deref(&self) -> Diff<&T::Target> where T: Deref, { self.as_ref().map(Deref::deref) } /// Convert a diff into an array `[before, after]`. pub fn into_array(self) -> [T; 2] { [self.before, self.after] }} impl<T: Eq> Diff<T> { /// Whether the diff represents a change, i.e. if `before` and `after` are /// not equal pub fn is_changed(&self) -> bool { self.before != self.after }} /// Whether to resolve conflict that makes the same change at all sides.#[derive(Clone, Copy, Debug, Eq, PartialEq, serde::Deserialize)]#[serde(rename_all = "kebab-case")]pub enum SameChange { /// Leaves same-change conflict unresolved. Keep, /// Resolves same-change conflict as if one side were unchanged. /// (i.e. `A+(A-B)=A`) /// /// 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. Accept,} /// Attempt to resolve trivial conflicts between the inputs. There must be/// an odd number of terms.pub fn trivial_merge<T>(values: &[T], same_change: SameChange) -> 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 && same_change == SameChange::Accept { 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 // canceled 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 && same_change == SameChange::Accept { // All sides made the same change. let [(value1, count1), (value2, count2)] = counts.into_iter().next_array().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, serde::Serialize)]#[serde(transparent)]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"); Self { 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]); } Self { values } } /// Creates a `Merge` from a first side and a series of diffs to apply to /// that side. pub fn from_diffs(first_side: T, diffs: impl IntoIterator<Item = Diff<T>>) -> Self { let values = iter::once(first_side) .chain(diffs.into_iter().flat_map(Diff::into_array)) .collect(); Self { values } } /// Creates a `Merge` with a single resolved value. pub const fn resolved(value: T) -> Self { Self { values: smallvec_inline![value], } } /// Creates a `Merge` by repeating a single value. pub fn repeated(value: T, num_sides: usize) -> Self where T: Clone, { Self { values: smallvec![value; num_sides * 2 - 1], } } /// 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) } /// Return the removed values and added values and take the ownership. pub fn into_removes_adds( self, ) -> ( impl ExactSizeIterator<Item = T>, impl ExactSizeIterator<Item = T>, ) { let (removes, adds): (Vec<_>, Vec<_>) = self .values .into_iter() .enumerate() .partition(|(n, _)| *n % 2 == 1); ( removes.into_iter().map(|(_, item)| item), adds.into_iter().map(|(_, item)| item), ) } /// 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, Self> { 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 } /// Apply the mapping returned by [`Self::get_simplified_mapping`]. #[must_use] fn apply_simplified_mapping(&self, mapping: &[usize]) -> Self where T: Clone, { // Reorder values based on their new indices in the simplified merge. let values = mapping .iter() .map(|index| self.values[*index].clone()) .collect(); Self { values } } /// Simplify the merge by joining diffs like A->B and B->C into A->C. /// Also drops trivial diffs like A->A. #[must_use] pub fn simplify(&self) -> Self where T: PartialEq + Clone, { let mapping = self.get_simplified_mapping(); self.apply_simplified_mapping(&mapping) } /// Simplify the merge, using a function to choose which values to compare. #[must_use] pub fn simplify_by<'a, U>(&'a self, f: impl FnMut(&'a T) -> U) -> Self where T: Clone, U: PartialEq, { let mapping = self.map(f).get_simplified_mapping(); self.apply_simplified_mapping(&mapping) } /// Updates the merge based on the given simplified merge. pub fn update_from_simplified(mut self, simplified: Self) -> 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) { self.values[index] = value; } self } /// If this merge can be trivially resolved, returns the value it resolves /// to. pub fn resolve_trivial(&self, same_change: SameChange) -> Option<&T> where T: Eq + Hash, { trivial_merge(&self.values, same_change) } /// 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, consuming /// `self`. pub fn into_map<U>(self, f: impl FnMut(T) -> U) -> Merge<U> { let values = self.values.into_iter().map(f).collect();Lines 1–500 of 1596. Load more
// 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; use std::iter::zip; use std::ops::Deref; use std::slice; use std::sync::Arc; use futures::future::try_join_all; use itertools::Itertools as _; use smallvec::SmallVec; use smallvec::smallvec; use smallvec::smallvec_inline; use crate::backend::BackendResult; use crate::backend::CopyId; use crate::backend::FileId; use crate::backend::TreeValue; use crate::conflict_labels::ConflictLabels; use crate::content_hash::ContentHash; use crate::content_hash::DigestUpdate; use crate::repo_path::RepoPath; use crate::repo_path::RepoPathComponent; use crate::store::Store; use crate::tree::Tree; /// A generic diff/transition from one value to another. /// /// This is not a diff in the `patch(1)` sense. See `diff::ContentDiff` for /// that. #[derive(Copy, Clone, Debug, PartialEq, Eq)] pub struct Diff<T> { /// The state before pub before: T, /// The state after pub after: T, } impl<T> Diff<T> { /// Create a new diff pub fn new(before: T, after: T) -> Self { Self { before, after } } /// Apply a function to both values pub fn map<U>(self, mut f: impl FnMut(T) -> U) -> Diff<U> { Diff { before: f(self.before), after: f(self.after), } } /// Combine a `Diff<T>` and a `Diff<U>` into a `Diff<(T, U)>`. pub fn zip<U>(self, other: Diff<U>) -> Diff<(T, U)> { Diff { before: (self.before, other.before), after: (self.after, other.after), } } /// Inverts a diff, swapping the before and after terms. pub fn invert(self) -> Self { Self { before: self.after, after: self.before, } } /// Convert a `&Diff<T>` into a `Diff<&T>`. pub fn as_ref(&self) -> Diff<&T> { Diff { before: &self.before, after: &self.after, } } /// Converts a `Diff<T>` or `&Diff<T>` to `Diff<&T::Target>`. (e.g. /// `Diff<String>` to `Diff<&str>`) pub fn as_deref(&self) -> Diff<&T::Target> where T: Deref, { self.as_ref().map(Deref::deref) } /// Convert a diff into an array `[before, after]`. pub fn into_array(self) -> [T; 2] { [self.before, self.after] } } impl<T: Eq> Diff<T> { /// Whether the diff represents a change, i.e. if `before` and `after` are /// not equal pub fn is_changed(&self) -> bool { self.before != self.after } } /// Whether to resolve conflict that makes the same change at all sides. #[derive(Clone, Copy, Debug, Eq, PartialEq, serde::Deserialize)] #[serde(rename_all = "kebab-case")] pub enum SameChange { /// Leaves same-change conflict unresolved. Keep, /// Resolves same-change conflict as if one side were unchanged. /// (i.e. `A+(A-B)=A`) /// /// 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. Accept, } /// Attempt to resolve trivial conflicts between the inputs. There must be /// an odd number of terms. pub fn trivial_merge<T>(values: &[T], same_change: SameChange) -> 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 && same_change == SameChange::Accept { 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 // canceled 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 && same_change == SameChange::Accept { // All sides made the same change. let [(value1, count1), (value2, count2)] = counts.into_iter().next_array().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, serde::Serialize)] #[serde(transparent)] 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"); Self { 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]); } Self { values } } /// Creates a `Merge` from a first side and a series of diffs to apply to /// that side. pub fn from_diffs(first_side: T, diffs: impl IntoIterator<Item = Diff<T>>) -> Self { let values = iter::once(first_side) .chain(diffs.into_iter().flat_map(Diff::into_array)) .collect(); Self { values } } /// Creates a `Merge` with a single resolved value. pub const fn resolved(value: T) -> Self { Self { values: smallvec_inline![value], } } /// Creates a `Merge` by repeating a single value. pub fn repeated(value: T, num_sides: usize) -> Self where T: Clone, { Self { values: smallvec![value; num_sides * 2 - 1], } } /// 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) } /// Return the removed values and added values and take the ownership. pub fn into_removes_adds( self, ) -> ( impl ExactSizeIterator<Item = T>, impl ExactSizeIterator<Item = T>, ) { let (removes, adds): (Vec<_>, Vec<_>) = self .values .into_iter() .enumerate() .partition(|(n, _)| *n % 2 == 1); ( removes.into_iter().map(|(_, item)| item), adds.into_iter().map(|(_, item)| item), ) } /// 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, Self> { 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 } /// Apply the mapping returned by [`Self::get_simplified_mapping`]. #[must_use] fn apply_simplified_mapping(&self, mapping: &[usize]) -> Self where T: Clone, { // Reorder values based on their new indices in the simplified merge. let values = mapping .iter() .map(|index| self.values[*index].clone()) .collect(); Self { values } } /// Simplify the merge by joining diffs like A->B and B->C into A->C. /// Also drops trivial diffs like A->A. #[must_use] pub fn simplify(&self) -> Self where T: PartialEq + Clone, { let mapping = self.get_simplified_mapping(); self.apply_simplified_mapping(&mapping) } /// Simplify the merge, using a function to choose which values to compare. #[must_use] pub fn simplify_by<'a, U>(&'a self, f: impl FnMut(&'a T) -> U) -> Self where T: Clone, U: PartialEq, { let mapping = self.map(f).get_simplified_mapping(); self.apply_simplified_mapping(&mapping) } /// Updates the merge based on the given simplified merge. pub fn update_from_simplified(mut self, simplified: Self) -> 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) { self.values[index] = value; } self } /// If this merge can be trivially resolved, returns the value it resolves /// to. pub fn resolve_trivial(&self, same_change: SameChange) -> Option<&T> where T: Eq + Hash, { trivial_merge(&self.values, same_change) } /// 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, consuming /// `self`. pub fn into_map<U>(self, f: impl FnMut(T) -> U) -> Merge<U> { let values = self.values.into_iter().map(f).collect();