just playing with tangled
ilyagr.bsky.social
1// Copyright 2020 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![allow(missing_docs)]
16
17use std::borrow::Borrow;
18use std::hash::Hash;
19use std::io::Write;
20use std::sync::Arc;
21
22use itertools::Itertools;
23
24use crate::backend::{BackendError, BackendResult, FileId, ObjectId, TreeId, TreeValue};
25use crate::content_hash::ContentHash;
26use crate::diff::{find_line_ranges, Diff, DiffHunk};
27use crate::files::{ContentHunk, MergeResult};
28use crate::merge::trivial_merge;
29use crate::repo_path::RepoPath;
30use crate::store::Store;
31use crate::tree::Tree;
32use crate::{backend, files};
33
34const CONFLICT_START_LINE: &[u8] = b"<<<<<<<\n";
35const CONFLICT_END_LINE: &[u8] = b">>>>>>>\n";
36const CONFLICT_DIFF_LINE: &[u8] = b"%%%%%%%\n";
37const CONFLICT_MINUS_LINE: &[u8] = b"-------\n";
38const CONFLICT_PLUS_LINE: &[u8] = b"+++++++\n";
39
40/// A generic representation of conflicting values.
41///
42/// There is exactly one more `adds()` than `removes()`. When interpreted as a
43/// series of diffs, the conflict's (i+1)-st add is matched with the i-th
44/// remove. The zeroth add is considered a diff from the non-existent state.
45#[derive(PartialEq, Eq, Hash, Clone, Debug)]
46pub struct Conflict<T> {
47 removes: Vec<T>,
48 adds: Vec<T>,
49}
50
51impl<T> Conflict<T> {
52 pub fn new(removes: Vec<T>, adds: Vec<T>) -> Self {
53 assert_eq!(adds.len(), removes.len() + 1);
54 Conflict { removes, adds }
55 }
56
57 /// Creates a `Conflict` with a single resolved value.
58 pub fn resolved(value: T) -> Self {
59 Conflict::new(vec![], vec![value])
60 }
61
62 /// Create a `Conflict` from a `removes` and `adds`, padding with `None` to
63 /// make sure that there is exactly one more `adds` than `removes`.
64 pub fn from_legacy_form(
65 removes: impl IntoIterator<Item = T>,
66 adds: impl IntoIterator<Item = T>,
67 ) -> Conflict<Option<T>> {
68 let mut removes = removes.into_iter().map(Some).collect_vec();
69 let mut adds = adds.into_iter().map(Some).collect_vec();
70 while removes.len() + 1 < adds.len() {
71 removes.push(None);
72 }
73 while adds.len() < removes.len() + 1 {
74 adds.push(None);
75 }
76 Conflict::new(removes, adds)
77 }
78
79 /// Returns the removes and adds as a pair.
80 pub fn take(self) -> (Vec<T>, Vec<T>) {
81 (self.removes, self.adds)
82 }
83
84 pub fn removes(&self) -> &[T] {
85 &self.removes
86 }
87
88 pub fn adds(&self) -> &[T] {
89 &self.adds
90 }
91
92 /// Whether this conflict is resolved. Does not resolve trivial conflicts.
93 pub fn is_resolved(&self) -> bool {
94 self.removes.is_empty()
95 }
96
97 /// Returns the resolved value, if this conflict is resolved. Does not
98 /// resolve trivial conflicts.
99 pub fn as_resolved(&self) -> Option<&T> {
100 if let [value] = &self.adds[..] {
101 Some(value)
102 } else {
103 None
104 }
105 }
106
107 /// Simplify the conflict by joining diffs like A->B and B->C into A->C.
108 /// Also drops trivial diffs like A->A.
109 pub fn simplify(mut self) -> Self
110 where
111 T: PartialEq,
112 {
113 let mut add_index = 0;
114 while add_index < self.adds.len() {
115 let add = &self.adds[add_index];
116 if let Some(remove_index) = self.removes.iter().position(|remove| remove == add) {
117 // Move the value to the `add_index-1`th diff, then delete the `remove_index`th
118 // diff.
119 self.adds.swap(remove_index + 1, add_index);
120 self.removes.remove(remove_index);
121 self.adds.remove(remove_index + 1);
122 } else {
123 add_index += 1;
124 }
125 }
126 self
127 }
128
129 pub fn resolve_trivial(&self) -> Option<&T>
130 where
131 T: Eq + Hash,
132 {
133 trivial_merge(&self.removes, &self.adds)
134 }
135
136 /// Creates a new conflict by applying `f` to each remove and add.
137 pub fn map<'a, U>(&'a self, mut f: impl FnMut(&'a T) -> U) -> Conflict<U> {
138 self.maybe_map(|term| Some(f(term))).unwrap()
139 }
140
141 /// Creates a new conflict by applying `f` to each remove and add, returning
142 /// `None if `f` returns `None` for any of them.
143 pub fn maybe_map<'a, U>(
144 &'a self,
145 mut f: impl FnMut(&'a T) -> Option<U>,
146 ) -> Option<Conflict<U>> {
147 let removes = self.removes.iter().map(&mut f).collect::<Option<_>>()?;
148 let adds = self.adds.iter().map(&mut f).collect::<Option<_>>()?;
149 Some(Conflict { removes, adds })
150 }
151
152 /// Creates a new conflict by applying `f` to each remove and add, returning
153 /// `Err if `f` returns `Err` for any of them.
154 pub fn try_map<'a, U, E>(
155 &'a self,
156 mut f: impl FnMut(&'a T) -> Result<U, E>,
157 ) -> Result<Conflict<U>, E> {
158 let removes = self.removes.iter().map(&mut f).try_collect()?;
159 let adds = self.adds.iter().map(&mut f).try_collect()?;
160 Ok(Conflict { removes, adds })
161 }
162}
163
164impl<T> Conflict<Option<T>> {
165 /// Creates lists of `removes` and `adds` from a `Conflict` by dropping
166 /// `None` values. Note that the conversion is lossy: the order of `None`
167 /// values is not preserved when converting back to a `Conflict`.
168 pub fn into_legacy_form(self) -> (Vec<T>, Vec<T>) {
169 (
170 self.removes.into_iter().flatten().collect(),
171 self.adds.into_iter().flatten().collect(),
172 )
173 }
174}
175
176impl<T> Conflict<Conflict<T>> {
177 /// Flattens a nested conflict into a regular conflict.
178 ///
179 /// Let's say we have a 3-way merge of 3-way merges like this:
180 ///
181 /// 4 5 7 8
182 /// 3 6
183 /// 1 2
184 /// 0
185 ///
186 /// Flattening that results in this 9-way conflict:
187 ///
188 /// 4 5 0 7 8
189 /// 3 2 1 6
190 pub fn flatten(mut self) -> Conflict<T> {
191 self.removes.reverse();
192 self.adds.reverse();
193 let mut result = self.adds.pop().unwrap();
194 while let Some(mut remove) = self.removes.pop() {
195 // Add removes reversed, and with the first element moved last, so we preserve
196 // the diffs
197 let first_add = remove.adds.remove(0);
198 result.removes.extend(remove.adds);
199 result.removes.push(first_add);
200 result.adds.extend(remove.removes);
201 let add = self.adds.pop().unwrap();
202 result.removes.extend(add.removes);
203 result.adds.extend(add.adds);
204 }
205 assert!(self.adds.is_empty());
206 result
207 }
208}
209
210impl<T: ContentHash> ContentHash for Conflict<T> {
211 fn hash(&self, state: &mut impl digest::Update) {
212 self.removes().hash(state);
213 self.adds().hash(state);
214 }
215}
216
217impl Conflict<TreeId> {
218 // Creates a resolved conflict for a legacy tree id (same as
219 // `Conflict::resolved()`).
220 // TODO(#1624): delete when all callers have been updated to support tree-level
221 // conflicts
222 pub fn from_legacy_tree_id(value: TreeId) -> Self {
223 Conflict {
224 removes: vec![],
225 adds: vec![value],
226 }
227 }
228
229 // TODO(#1624): delete when all callers have been updated to support tree-level
230 // conflicts
231 pub fn as_legacy_tree_id(&self) -> &TreeId {
232 self.as_resolved().unwrap()
233 }
234}
235
236impl Conflict<Option<TreeValue>> {
237 /// Create a `Conflict` from a `backend::Conflict`, padding with `None` to
238 /// make sure that there is exactly one more `adds()` than `removes()`.
239 pub fn from_backend_conflict(conflict: backend::Conflict) -> Self {
240 let removes = conflict.removes.into_iter().map(|term| term.value);
241 let adds = conflict.adds.into_iter().map(|term| term.value);
242 Conflict::from_legacy_form(removes, adds)
243 }
244
245 /// Creates a `backend::Conflict` from a `Conflict` by dropping `None`
246 /// values. Note that the conversion is lossy: the order of `None` values is
247 /// not preserved when converting back to a `Conflict`.
248 pub fn into_backend_conflict(self) -> backend::Conflict {
249 let (removes, adds) = self.into_legacy_form();
250 let removes = removes
251 .into_iter()
252 .map(|value| backend::ConflictTerm { value })
253 .collect();
254 let adds = adds
255 .into_iter()
256 .map(|value| backend::ConflictTerm { value })
257 .collect();
258 backend::Conflict { removes, adds }
259 }
260
261 pub fn materialize(
262 &self,
263 store: &Store,
264 path: &RepoPath,
265 output: &mut dyn Write,
266 ) -> std::io::Result<()> {
267 if let Some(file_conflict) = self.to_file_conflict() {
268 let content = file_conflict.extract_as_single_hunk(store, path);
269 materialize_merge_result(&content, output)
270 } else {
271 // Unless all terms are regular files, we can't do much better than to try to
272 // describe the conflict.
273 self.describe(output)
274 }
275 }
276
277 pub fn to_file_conflict(&self) -> Option<Conflict<Option<FileId>>> {
278 self.maybe_map(|term| match term {
279 None => Some(None),
280 Some(TreeValue::File {
281 id,
282 executable: false,
283 }) => Some(Some(id.clone())),
284 _ => None,
285 })
286 }
287
288 /// Give a summary description of the conflict's "removes" and "adds"
289 pub fn describe(&self, file: &mut dyn Write) -> std::io::Result<()> {
290 file.write_all(b"Conflict:\n")?;
291 for term in self.removes().iter().flatten() {
292 file.write_all(format!(" Removing {}\n", describe_conflict_term(term)).as_bytes())?;
293 }
294 for term in self.adds().iter().flatten() {
295 file.write_all(format!(" Adding {}\n", describe_conflict_term(term)).as_bytes())?;
296 }
297 Ok(())
298 }
299
300 /// Returns `None` if there are no conflict markers in `content`.
301 pub fn update_from_content(
302 &self,
303 store: &Store,
304 path: &RepoPath,
305 content: &[u8],
306 ) -> BackendResult<Option<Conflict<Option<TreeValue>>>> {
307 // TODO: Check that the conflict only involves files and convert it to a
308 // `Conflict<Option<FileId>>` so we can remove the wildcard pattern in the loops
309 // further down.
310
311 // First check if the new content is unchanged compared to the old content. If
312 // it is, we don't need parse the content or write any new objects to the
313 // store. This is also a way of making sure that unchanged tree/file
314 // conflicts (for example) are not converted to regular files in the working
315 // copy.
316 let mut old_content = Vec::with_capacity(content.len());
317 self.materialize(store, path, &mut old_content).unwrap();
318 if content == old_content {
319 return Ok(Some(self.clone()));
320 }
321
322 let mut removed_content = vec![vec![]; self.removes().len()];
323 let mut added_content = vec![vec![]; self.adds().len()];
324 let Some(hunks) = parse_conflict(content, self.removes().len(), self.adds().len()) else {
325 // Either there are no self markers of they don't have the expected arity
326 return Ok(None);
327 };
328 for hunk in hunks {
329 if let Some(slice) = hunk.as_resolved() {
330 for buf in &mut removed_content {
331 buf.extend_from_slice(&slice.0);
332 }
333 for buf in &mut added_content {
334 buf.extend_from_slice(&slice.0);
335 }
336 } else {
337 let (removes, adds) = hunk.take();
338 for (i, buf) in removes.into_iter().enumerate() {
339 removed_content[i].extend(buf.0);
340 }
341 for (i, buf) in adds.into_iter().enumerate() {
342 added_content[i].extend(buf.0);
343 }
344 }
345 }
346 // Now write the new files contents we found by parsing the file
347 // with conflict markers. Update the Conflict object with the new
348 // FileIds.
349 let mut new_removes = vec![];
350 for (i, buf) in removed_content.iter().enumerate() {
351 match &self.removes()[i] {
352 Some(TreeValue::File { id: _, executable }) => {
353 let file_id = store.write_file(path, &mut buf.as_slice())?;
354 let new_value = TreeValue::File {
355 id: file_id,
356 executable: *executable,
357 };
358 new_removes.push(Some(new_value));
359 }
360 None if buf.is_empty() => {
361 // The missing side of a conflict is still represented by
362 // the empty string we materialized it as
363 new_removes.push(None);
364 }
365 _ => {
366 // The user edited a non-file side. This should never happen. We consider the
367 // conflict resolved for now.
368 return Ok(None);
369 }
370 }
371 }
372 let mut new_adds = vec![];
373 for (i, buf) in added_content.iter().enumerate() {
374 match &self.adds()[i] {
375 Some(TreeValue::File { id: _, executable }) => {
376 let file_id = store.write_file(path, &mut buf.as_slice())?;
377 let new_value = TreeValue::File {
378 id: file_id,
379 executable: *executable,
380 };
381 new_adds.push(Some(new_value));
382 }
383 None if buf.is_empty() => {
384 // The missing side of a conflict is still represented by
385 // the empty string we materialized it as => nothing to do
386 new_adds.push(None);
387 }
388 _ => {
389 // The user edited a non-file side. This should never happen. We consider the
390 // conflict resolved for now.
391 return Ok(None);
392 }
393 }
394 }
395 Ok(Some(Conflict::new(new_removes, new_adds)))
396 }
397}
398
399impl Conflict<Option<FileId>> {
400 pub fn extract_as_single_hunk(&self, store: &Store, path: &RepoPath) -> Conflict<ContentHunk> {
401 self.map(|term| get_file_contents(store, path, term))
402 }
403}
404
405impl<T> Conflict<Option<T>>
406where
407 T: Borrow<TreeValue>,
408{
409 /// If every non-`None` term of a `Conflict<Option<TreeValue>>`
410 /// is a `TreeValue::Tree`, this converts it to
411 /// a `Conflict<Tree>`, with empty trees instead of
412 /// any `None` terms. Otherwise, returns `None`.
413 pub fn to_tree_conflict(
414 &self,
415 store: &Arc<Store>,
416 dir: &RepoPath,
417 ) -> Result<Option<Conflict<Tree>>, BackendError> {
418 let tree_id_conflict = self.maybe_map(|term| match term {
419 None => Some(None),
420 Some(value) => {
421 if let TreeValue::Tree(id) = value.borrow() {
422 Some(Some(id))
423 } else {
424 None
425 }
426 }
427 });
428 if let Some(tree_id_conflict) = tree_id_conflict {
429 let get_tree = |id: &Option<&TreeId>| -> Result<Tree, BackendError> {
430 if let Some(id) = id {
431 store.get_tree(dir, id)
432 } else {
433 Ok(Tree::null(store.clone(), dir.clone()))
434 }
435 };
436 Ok(Some(tree_id_conflict.try_map(get_tree)?))
437 } else {
438 Ok(None)
439 }
440 }
441}
442
443fn describe_conflict_term(value: &TreeValue) -> String {
444 match value {
445 TreeValue::File {
446 id,
447 executable: false,
448 } => {
449 format!("file with id {}", id.hex())
450 }
451 TreeValue::File {
452 id,
453 executable: true,
454 } => {
455 format!("executable file with id {}", id.hex())
456 }
457 TreeValue::Symlink(id) => {
458 format!("symlink with id {}", id.hex())
459 }
460 TreeValue::Tree(id) => {
461 format!("tree with id {}", id.hex())
462 }
463 TreeValue::GitSubmodule(id) => {
464 format!("Git submodule with id {}", id.hex())
465 }
466 TreeValue::Conflict(id) => {
467 format!("Conflict with id {}", id.hex())
468 }
469 }
470}
471
472fn get_file_contents(store: &Store, path: &RepoPath, term: &Option<FileId>) -> ContentHunk {
473 match term {
474 Some(id) => {
475 let mut content = vec![];
476 store
477 .read_file(path, id)
478 .unwrap()
479 .read_to_end(&mut content)
480 .unwrap();
481 ContentHunk(content)
482 }
483 // If the conflict had removed the file on one side, we pretend that the file
484 // was empty there.
485 None => ContentHunk(vec![]),
486 }
487}
488
489fn write_diff_hunks(hunks: &[DiffHunk], file: &mut dyn Write) -> std::io::Result<()> {
490 for hunk in hunks {
491 match hunk {
492 DiffHunk::Matching(content) => {
493 for line in content.split_inclusive(|b| *b == b'\n') {
494 file.write_all(b" ")?;
495 file.write_all(line)?;
496 }
497 }
498 DiffHunk::Different(content) => {
499 for line in content[0].split_inclusive(|b| *b == b'\n') {
500 file.write_all(b"-")?;
501 file.write_all(line)?;
502 }
503 for line in content[1].split_inclusive(|b| *b == b'\n') {
504 file.write_all(b"+")?;
505 file.write_all(line)?;
506 }
507 }
508 }
509 }
510 Ok(())
511}
512
513pub fn materialize_merge_result(
514 single_hunk: &Conflict<ContentHunk>,
515 output: &mut dyn Write,
516) -> std::io::Result<()> {
517 let removed_slices = single_hunk
518 .removes
519 .iter()
520 .map(|hunk| hunk.0.as_slice())
521 .collect_vec();
522 let added_slices = single_hunk
523 .adds
524 .iter()
525 .map(|hunk| hunk.0.as_slice())
526 .collect_vec();
527 let merge_result = files::merge(&removed_slices, &added_slices);
528 match merge_result {
529 MergeResult::Resolved(content) => {
530 output.write_all(&content.0)?;
531 }
532 MergeResult::Conflict(hunks) => {
533 for hunk in hunks {
534 if let Some(content) = hunk.as_resolved() {
535 output.write_all(&content.0)?;
536 } else {
537 output.write_all(CONFLICT_START_LINE)?;
538 let mut add_index = 0;
539 for left in hunk.removes() {
540 let right1 = if let Some(right1) = hunk.adds().get(add_index) {
541 right1
542 } else {
543 // If we have no more positive terms, emit the remaining negative
544 // terms as snapshots.
545 output.write_all(CONFLICT_MINUS_LINE)?;
546 output.write_all(&left.0)?;
547 continue;
548 };
549 let diff1 = Diff::for_tokenizer(&[&left.0, &right1.0], &find_line_ranges)
550 .hunks()
551 .collect_vec();
552 // Check if the diff against the next positive term is better. Since
553 // we want to preserve the order of the terms, we don't match against
554 // any later positive terms.
555 if let Some(right2) = hunk.adds().get(add_index + 1) {
556 let diff2 =
557 Diff::for_tokenizer(&[&left.0, &right2.0], &find_line_ranges)
558 .hunks()
559 .collect_vec();
560 if diff_size(&diff2) < diff_size(&diff1) {
561 // If the next positive term is a better match, emit
562 // the current positive term as a snapshot and the next
563 // positive term as a diff.
564 output.write_all(CONFLICT_PLUS_LINE)?;
565 output.write_all(&right1.0)?;
566 output.write_all(CONFLICT_DIFF_LINE)?;
567 write_diff_hunks(&diff2, output)?;
568 add_index += 2;
569 continue;
570 }
571 }
572
573 output.write_all(CONFLICT_DIFF_LINE)?;
574 write_diff_hunks(&diff1, output)?;
575 add_index += 1;
576 }
577
578 // Emit the remaining positive terms as snapshots.
579 for slice in &hunk.adds()[add_index..] {
580 output.write_all(CONFLICT_PLUS_LINE)?;
581 output.write_all(&slice.0)?;
582 }
583 output.write_all(CONFLICT_END_LINE)?;
584 }
585 }
586 }
587 }
588 Ok(())
589}
590
591fn diff_size(hunks: &[DiffHunk]) -> usize {
592 hunks
593 .iter()
594 .map(|hunk| match hunk {
595 DiffHunk::Matching(_) => 0,
596 DiffHunk::Different(slices) => slices.iter().map(|slice| slice.len()).sum(),
597 })
598 .sum()
599}
600
601/// Parses conflict markers from a slice. Returns None if there were no valid
602/// conflict markers. The caller has to provide the expected number of removed
603/// and added inputs to the conflicts. Conflict markers that are otherwise valid
604/// will be considered invalid if they don't have the expected arity.
605// TODO: "parse" is not usually the opposite of "materialize", so maybe we
606// should rename them to "serialize" and "deserialize"?
607pub fn parse_conflict(
608 input: &[u8],
609 num_removes: usize,
610 num_adds: usize,
611) -> Option<Vec<Conflict<ContentHunk>>> {
612 if input.is_empty() {
613 return None;
614 }
615 let mut hunks = vec![];
616 let mut pos = 0;
617 let mut resolved_start = 0;
618 let mut conflict_start = None;
619 for line in input.split_inclusive(|b| *b == b'\n') {
620 if line == CONFLICT_START_LINE {
621 conflict_start = Some(pos);
622 } else if conflict_start.is_some() && line == CONFLICT_END_LINE {
623 let conflict_body = &input[conflict_start.unwrap() + CONFLICT_START_LINE.len()..pos];
624 let hunk = parse_conflict_hunk(conflict_body);
625 if hunk.removes().len() == num_removes && hunk.adds().len() == num_adds {
626 let resolved_slice = &input[resolved_start..conflict_start.unwrap()];
627 if !resolved_slice.is_empty() {
628 hunks.push(Conflict::resolved(ContentHunk(resolved_slice.to_vec())));
629 }
630 hunks.push(hunk);
631 resolved_start = pos + line.len();
632 }
633 conflict_start = None;
634 }
635 pos += line.len();
636 }
637
638 if hunks.is_empty() {
639 None
640 } else {
641 if resolved_start < input.len() {
642 hunks.push(Conflict::resolved(ContentHunk(
643 input[resolved_start..].to_vec(),
644 )));
645 }
646 Some(hunks)
647 }
648}
649
650fn parse_conflict_hunk(input: &[u8]) -> Conflict<ContentHunk> {
651 enum State {
652 Diff,
653 Minus,
654 Plus,
655 Unknown,
656 }
657 let mut state = State::Unknown;
658 let mut removes = vec![];
659 let mut adds = vec![];
660 for line in input.split_inclusive(|b| *b == b'\n') {
661 match line {
662 CONFLICT_DIFF_LINE => {
663 state = State::Diff;
664 removes.push(ContentHunk(vec![]));
665 adds.push(ContentHunk(vec![]));
666 continue;
667 }
668 CONFLICT_MINUS_LINE => {
669 state = State::Minus;
670 removes.push(ContentHunk(vec![]));
671 continue;
672 }
673 CONFLICT_PLUS_LINE => {
674 state = State::Plus;
675 adds.push(ContentHunk(vec![]));
676 continue;
677 }
678 _ => {}
679 };
680 match state {
681 State::Diff => {
682 if let Some(rest) = line.strip_prefix(b"-") {
683 removes.last_mut().unwrap().0.extend_from_slice(rest);
684 } else if let Some(rest) = line.strip_prefix(b"+") {
685 adds.last_mut().unwrap().0.extend_from_slice(rest);
686 } else if let Some(rest) = line.strip_prefix(b" ") {
687 removes.last_mut().unwrap().0.extend_from_slice(rest);
688 adds.last_mut().unwrap().0.extend_from_slice(rest);
689 } else {
690 // Doesn't look like a conflict
691 return Conflict::resolved(ContentHunk(vec![]));
692 }
693 }
694 State::Minus => {
695 removes.last_mut().unwrap().0.extend_from_slice(line);
696 }
697 State::Plus => {
698 adds.last_mut().unwrap().0.extend_from_slice(line);
699 }
700 State::Unknown => {
701 // Doesn't look like a conflict
702 return Conflict::resolved(ContentHunk(vec![]));
703 }
704 }
705 }
706
707 Conflict::new(removes, adds)
708}
709
710#[cfg(test)]
711mod tests {
712 use super::*;
713
714 fn c<T: Clone>(removes: &[T], adds: &[T]) -> Conflict<T> {
715 Conflict::new(removes.to_vec(), adds.to_vec())
716 }
717
718 #[test]
719 fn test_legacy_form_conversion() {
720 fn test_equivalent<T>(legacy_form: (Vec<T>, Vec<T>), conflict: Conflict<Option<T>>)
721 where
722 T: Clone + PartialEq + std::fmt::Debug,
723 {
724 assert_eq!(conflict.clone().into_legacy_form(), legacy_form);
725 assert_eq!(
726 Conflict::from_legacy_form(legacy_form.0, legacy_form.1),
727 conflict
728 );
729 }
730 // Non-conflict
731 test_equivalent((vec![], vec![0]), Conflict::new(vec![], vec![Some(0)]));
732 // Regular 3-way conflict
733 test_equivalent(
734 (vec![0], vec![1, 2]),
735 Conflict::new(vec![Some(0)], vec![Some(1), Some(2)]),
736 );
737 // Modify/delete conflict
738 test_equivalent(
739 (vec![0], vec![1]),
740 Conflict::new(vec![Some(0)], vec![Some(1), None]),
741 );
742 // Add/add conflict
743 test_equivalent(
744 (vec![], vec![0, 1]),
745 Conflict::new(vec![None], vec![Some(0), Some(1)]),
746 );
747 // 5-way conflict
748 test_equivalent(
749 (vec![0, 1], vec![2, 3, 4]),
750 Conflict::new(vec![Some(0), Some(1)], vec![Some(2), Some(3), Some(4)]),
751 );
752 // 5-way delete/delete conflict
753 test_equivalent(
754 (vec![0, 1], vec![]),
755 Conflict::new(vec![Some(0), Some(1)], vec![None, None, None]),
756 );
757 }
758
759 #[test]
760 fn test_as_resolved() {
761 assert_eq!(Conflict::new(vec![], vec![0]).as_resolved(), Some(&0));
762 // Even a trivially resolvable conflict is not resolved
763 assert_eq!(Conflict::new(vec![0], vec![0, 1]).as_resolved(), None);
764 }
765
766 #[test]
767 fn test_simplify() {
768 // 1-way "conflict"
769 assert_eq!(c(&[], &[0]).simplify(), c(&[], &[0]));
770 // 3-way conflict
771 assert_eq!(c(&[0], &[0, 0]).simplify(), c(&[], &[0]));
772 assert_eq!(c(&[0], &[0, 1]).simplify(), c(&[], &[1]));
773 assert_eq!(c(&[0], &[1, 0]).simplify(), c(&[], &[1]));
774 assert_eq!(c(&[0], &[1, 1]).simplify(), c(&[0], &[1, 1]));
775 assert_eq!(c(&[0], &[1, 2]).simplify(), c(&[0], &[1, 2]));
776 // 5-way conflict
777 assert_eq!(c(&[0, 0], &[0, 0, 0]).simplify(), c(&[], &[0]));
778 assert_eq!(c(&[0, 0], &[0, 0, 1]).simplify(), c(&[], &[1]));
779 assert_eq!(c(&[0, 0], &[0, 1, 0]).simplify(), c(&[], &[1]));
780 assert_eq!(c(&[0, 0], &[0, 1, 1]).simplify(), c(&[0], &[1, 1]));
781 assert_eq!(c(&[0, 0], &[0, 1, 2]).simplify(), c(&[0], &[1, 2]));
782 assert_eq!(c(&[0, 0], &[1, 0, 0]).simplify(), c(&[], &[1]));
783 assert_eq!(c(&[0, 0], &[1, 0, 1]).simplify(), c(&[0], &[1, 1]));
784 assert_eq!(c(&[0, 0], &[1, 0, 2]).simplify(), c(&[0], &[1, 2]));
785 assert_eq!(c(&[0, 0], &[1, 1, 0]).simplify(), c(&[0], &[1, 1]));
786 assert_eq!(c(&[0, 0], &[1, 1, 1]).simplify(), c(&[0, 0], &[1, 1, 1]));
787 assert_eq!(c(&[0, 0], &[1, 1, 2]).simplify(), c(&[0, 0], &[1, 1, 2]));
788 assert_eq!(c(&[0, 0], &[1, 2, 0]).simplify(), c(&[0], &[1, 2]));
789 assert_eq!(c(&[0, 0], &[1, 2, 1]).simplify(), c(&[0, 0], &[1, 2, 1]));
790 assert_eq!(c(&[0, 0], &[1, 2, 2]).simplify(), c(&[0, 0], &[1, 2, 2]));
791 assert_eq!(c(&[0, 0], &[1, 2, 3]).simplify(), c(&[0, 0], &[1, 2, 3]));
792 assert_eq!(c(&[0, 1], &[0, 0, 0]).simplify(), c(&[1], &[0, 0]));
793 assert_eq!(c(&[0, 1], &[0, 0, 1]).simplify(), c(&[], &[0]));
794 assert_eq!(c(&[0, 1], &[0, 0, 2]).simplify(), c(&[1], &[0, 2]));
795 assert_eq!(c(&[0, 1], &[0, 1, 0]).simplify(), c(&[], &[0]));
796 assert_eq!(c(&[0, 1], &[0, 1, 1]).simplify(), c(&[], &[1]));
797 assert_eq!(c(&[0, 1], &[0, 1, 2]).simplify(), c(&[], &[2]));
798 assert_eq!(c(&[0, 1], &[0, 2, 0]).simplify(), c(&[1], &[2, 0]));
799 assert_eq!(c(&[0, 1], &[0, 2, 1]).simplify(), c(&[], &[2]));
800 assert_eq!(c(&[0, 1], &[0, 2, 2]).simplify(), c(&[1], &[2, 2]));
801 assert_eq!(c(&[0, 1], &[0, 2, 3]).simplify(), c(&[1], &[2, 3]));
802 assert_eq!(c(&[0, 1], &[1, 0, 0]).simplify(), c(&[], &[0]));
803 assert_eq!(c(&[0, 1], &[1, 0, 1]).simplify(), c(&[], &[1]));
804 assert_eq!(c(&[0, 1], &[1, 0, 2]).simplify(), c(&[], &[2]));
805 assert_eq!(c(&[0, 1], &[1, 1, 0]).simplify(), c(&[], &[1]));
806 assert_eq!(c(&[0, 1], &[1, 1, 1]).simplify(), c(&[0], &[1, 1]));
807 assert_eq!(c(&[0, 1], &[1, 1, 2]).simplify(), c(&[0], &[2, 1]));
808 assert_eq!(c(&[0, 1], &[1, 2, 0]).simplify(), c(&[], &[2]));
809 assert_eq!(c(&[0, 1], &[1, 2, 1]).simplify(), c(&[0], &[1, 2]));
810 assert_eq!(c(&[0, 1], &[1, 2, 2]).simplify(), c(&[0], &[2, 2]));
811 assert_eq!(c(&[0, 1], &[1, 2, 3]).simplify(), c(&[0], &[3, 2]));
812 assert_eq!(c(&[0, 1], &[2, 0, 0]).simplify(), c(&[1], &[2, 0]));
813 assert_eq!(c(&[0, 1], &[2, 0, 1]).simplify(), c(&[], &[2]));
814 assert_eq!(c(&[0, 1], &[2, 0, 2]).simplify(), c(&[1], &[2, 2]));
815 assert_eq!(c(&[0, 1], &[2, 0, 3]).simplify(), c(&[1], &[2, 3]));
816 assert_eq!(c(&[0, 1], &[2, 1, 0]).simplify(), c(&[], &[2]));
817 assert_eq!(c(&[0, 1], &[2, 1, 1]).simplify(), c(&[0], &[2, 1]));
818 assert_eq!(c(&[0, 1], &[2, 1, 2]).simplify(), c(&[0], &[2, 2]));
819 assert_eq!(c(&[0, 1], &[2, 1, 3]).simplify(), c(&[0], &[2, 3]));
820 assert_eq!(c(&[0, 1], &[2, 2, 0]).simplify(), c(&[1], &[2, 2]));
821 assert_eq!(c(&[0, 1], &[2, 2, 1]).simplify(), c(&[0], &[2, 2]));
822 assert_eq!(c(&[0, 1], &[2, 2, 2]).simplify(), c(&[0, 1], &[2, 2, 2]));
823 assert_eq!(c(&[0, 1], &[2, 2, 3]).simplify(), c(&[0, 1], &[2, 2, 3]));
824 assert_eq!(c(&[0, 1], &[2, 3, 0]).simplify(), c(&[1], &[2, 3]));
825 assert_eq!(c(&[0, 1], &[2, 3, 1]).simplify(), c(&[0], &[2, 3]));
826 assert_eq!(c(&[0, 1], &[2, 3, 2]).simplify(), c(&[0, 1], &[2, 3, 2]));
827 assert_eq!(c(&[0, 1], &[2, 3, 3]).simplify(), c(&[0, 1], &[2, 3, 3]));
828 assert_eq!(c(&[0, 1], &[2, 3, 4]).simplify(), c(&[0, 1], &[2, 3, 4]));
829 assert_eq!(
830 c(&[0, 1, 2], &[3, 4, 5, 0]).simplify(),
831 c(&[1, 2], &[3, 5, 4])
832 );
833 }
834
835 #[test]
836 fn test_conflict_invariants() {
837 fn check_invariants(removes: &[u32], adds: &[u32]) {
838 let conflict = Conflict::new(removes.to_vec(), adds.to_vec());
839 // `simplify()` is idempotent
840 assert_eq!(
841 conflict.clone().simplify().simplify(),
842 conflict.clone().simplify(),
843 "simplify() not idempotent for {conflict:?}"
844 );
845 // `resolve_trivial()` is unaffected by `simplify()`
846 assert_eq!(
847 conflict.clone().simplify().resolve_trivial(),
848 conflict.resolve_trivial(),
849 "simplify() changed result of resolve_trivial() for {conflict:?}"
850 );
851 }
852 // 1-way "conflict"
853 check_invariants(&[], &[0]);
854 for i in 0..=1 {
855 for j in 0..=i + 1 {
856 // 3-way conflict
857 check_invariants(&[0], &[i, j]);
858 for k in 0..=j + 1 {
859 for l in 0..=k + 1 {
860 // 5-way conflict
861 check_invariants(&[0, i], &[j, k, l]);
862 }
863 }
864 }
865 }
866 }
867
868 #[test]
869 fn test_map() {
870 fn increment(i: &i32) -> i32 {
871 i + 1
872 }
873 // 1-way conflict
874 assert_eq!(c(&[], &[1]).map(increment), c(&[], &[2]));
875 // 3-way conflict
876 assert_eq!(c(&[1], &[3, 5]).map(increment), c(&[2], &[4, 6]));
877 }
878
879 #[test]
880 fn test_maybe_map() {
881 fn sqrt(i: &i32) -> Option<i32> {
882 if *i >= 0 {
883 Some((*i as f64).sqrt() as i32)
884 } else {
885 None
886 }
887 }
888 // 1-way conflict
889 assert_eq!(c(&[], &[1]).maybe_map(sqrt), Some(c(&[], &[1])));
890 assert_eq!(c(&[], &[-1]).maybe_map(sqrt), None);
891 // 3-way conflict
892 assert_eq!(c(&[1], &[4, 9]).maybe_map(sqrt), Some(c(&[1], &[2, 3])));
893 assert_eq!(c(&[-1], &[4, 9]).maybe_map(sqrt), None);
894 assert_eq!(c(&[1], &[-4, 9]).maybe_map(sqrt), None);
895 }
896
897 #[test]
898 fn test_try_map() {
899 fn sqrt(i: &i32) -> Result<i32, ()> {
900 if *i >= 0 {
901 Ok((*i as f64).sqrt() as i32)
902 } else {
903 Err(())
904 }
905 }
906 // 1-way conflict
907 assert_eq!(c(&[], &[1]).try_map(sqrt), Ok(c(&[], &[1])));
908 assert_eq!(c(&[], &[-1]).try_map(sqrt), Err(()));
909 // 3-way conflict
910 assert_eq!(c(&[1], &[4, 9]).try_map(sqrt), Ok(c(&[1], &[2, 3])));
911 assert_eq!(c(&[-1], &[4, 9]).try_map(sqrt), Err(()));
912 assert_eq!(c(&[1], &[-4, 9]).try_map(sqrt), Err(()));
913 }
914
915 #[test]
916 fn test_flatten() {
917 // 1-way conflict of 1-way conflict
918 assert_eq!(c(&[], &[c(&[], &[0])]).flatten(), c(&[], &[0]));
919 // 1-way conflict of 3-way conflict
920 assert_eq!(c(&[], &[c(&[0], &[1, 2])]).flatten(), c(&[0], &[1, 2]));
921 // 3-way conflict of 1-way conflicts
922 assert_eq!(
923 c(&[c(&[], &[0])], &[c(&[], &[1]), c(&[], &[2])]).flatten(),
924 c(&[0], &[1, 2])
925 );
926 // 3-way conflict of 3-way conflicts
927 assert_eq!(
928 c(&[c(&[0], &[1, 2])], &[c(&[3], &[4, 5]), c(&[6], &[7, 8])]).flatten(),
929 c(&[3, 2, 1, 6], &[4, 5, 0, 7, 8])
930 );
931 }
932}