// 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::future::Future;use std::hash::Hash;use std::iter::zip;use std::slice;use std::sync::Arc; use futures::future::try_join_all;use itertools::Itertools as _;use smallvec::smallvec_inline;use smallvec::SmallVec; use crate::backend;use crate::backend::BackendResult;use crate::backend::CopyId;use crate::backend::FileId;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_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"); 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 const 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. #[must_use] pub fn simplify(&self) -> Self where T: PartialEq + Clone, { let mapping = self.get_simplified_mapping(); // Reorder values based on their new indices in the simplified merge. let values = mapping .iter() .map(|index| self.values[*index].clone()) .collect(); Merge { values } } /// 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 /// `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 }) } /// Creates a new merge by applying the async function `f` to each remove /// and add, running them concurrently, and returning `Err if `f` /// returns `Err` for any of them. pub async fn try_map_async<'a, F, U, E>( &'a self, f: impl FnMut(&'a T) -> F, ) -> Result<Merge<U>, E> where F: Future<Output = Result<U, E>>, { let values = try_join_all(self.values.iter().map(f)).await?; Ok(Merge { values: values.into(), }) }} /// 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();Lines 1–500 of 1212. 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::future::Future; use std::hash::Hash; use std::iter::zip; use std::slice; use std::sync::Arc; use futures::future::try_join_all; use itertools::Itertools as _; use smallvec::smallvec_inline; use smallvec::SmallVec; use crate::backend; use crate::backend::BackendResult; use crate::backend::CopyId; use crate::backend::FileId; 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_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"); 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 const 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. #[must_use] pub fn simplify(&self) -> Self where T: PartialEq + Clone, { let mapping = self.get_simplified_mapping(); // Reorder values based on their new indices in the simplified merge. let values = mapping .iter() .map(|index| self.values[*index].clone()) .collect(); Merge { values } } /// 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 /// `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 }) } /// Creates a new merge by applying the async function `f` to each remove /// and add, running them concurrently, and returning `Err if `f` /// returns `Err` for any of them. pub async fn try_map_async<'a, F, U, E>( &'a self, f: impl FnMut(&'a T) -> F, ) -> Result<Merge<U>, E> where F: Future<Output = Result<U, E>>, { let values = try_join_all(self.values.iter().map(f)).await?; Ok(Merge { values: values.into(), }) } } /// 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();