1 // Copyright 2023 Google LLC
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 // http://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 use std::fmt::Debug;
16
17 /// Maximum number of edits which can exist before [`edit_list`] falls back to a
18 /// complete rewrite to produce the edit list.
19 ///
20 /// Increasing this limit increases the accuracy of [`edit_list`] while
21 /// quadratically increasing its worst-case runtime.
22 const MAX_DISTANCE: i32 = 50;
23
24 /// The difference between two inputs as produced by [`edit_list`].
25 #[derive(Debug)]
26 pub(crate) enum Difference<T> {
27 /// No differences were detected at all.
28 Equal,
29
30 /// At most [`MAX_DISTANCE`] edits are required to convert one input to the
31 /// other.
32 ///
33 /// Contains the list of [`Edit`] to perform the transformation.
34 Editable(Vec<Edit<T>>),
35
36 /// More than [`MAX_DISTANCE`] edits are required to convert one input to
37 /// the other.
38 ///
39 /// The inputs are therefore considered unrelated and no edit list is
40 /// provided.
41 Unrelated,
42 }
43
44 /// An edit operation on two sequences of `T`.
45 #[derive(Debug, Clone)]
46 pub(crate) enum Edit<T> {
47 /// An extra `T` was added to the actual sequence.
48 ExtraActual(T),
49
50 /// An extra `T` was added to the expected sequence.
51 ExtraExpected(T),
52
53 /// An element was added to each sequence.
54 Both(T),
55
56 /// Additional (unlisted) elements are present in the actual sequence.
57 ///
58 /// This is only output in the mode [`Mode::Prefix`]. Its presence precludes
59 /// reconstructing the actual sequence from the expected sequence.
60 AdditionalActual,
61 }
62
63 /// Controls the termination condition of [`edit_list`].
64 #[derive(Clone, Copy)]
65 pub(crate) enum Mode {
66 /// Indicates that the two arguments are intended to be equal.
67 ///
68 /// The entire edit list to transform between `actual` and `expected` is
69 /// returned.
70 Exact,
71
72 /// Indicates that `expected` is inteded to be a prefix of `actual`.
73 ///
74 /// Any additional parts of `actual` after the prefix `expected` are omitted
75 /// from the output.
76 Prefix,
77
78 /// Similar to [`Mode::Prefix`], except it is also assumed that `actual` has
79 /// some number of initial lines which should not be in the output.
80 ///
81 /// Any initial [`Edit::ExtraActual`] entries are replaced with
82 /// [`Edit::AdditionalActual`] in the edit list. If the first entry which is
83 /// not an [`Edit::ExtraActual`] is [`Edit::ExtraExpected`], then the last
84 /// [`Edit::ExtraActual`] is actual in the output.
85 Contains,
86 }
87
88 /// Computes the edit list of `actual` and `expected`.
89 ///
90 /// If `actual` and `expected` are equal, then this returns
91 /// [`Difference::Equal`]. If they are different but have an
92 /// [edit distance](https://en.wikipedia.org/wiki/Edit_distance)
93 /// of at most [`MAX_DISTANCE`], this returns [`Difference::Editable`] with the
94 /// sequence of [`Edit`] which can be applied to `actual` to obtain `expected`.
95 /// Otherwise this returns [`Difference::Unrelated`].
96 ///
97 /// This uses [Myers Algorithm](https://neil.fraser.name/writing/diff/myers.pdf)
98 /// with a maximum edit distance of [`MAX_DISTANCE`]. Thus the worst-case
99 /// runtime is linear in both the input length and [`MAX_DISTANCE`].
edit_list<T: PartialEq + Copy>( actual: impl IntoIterator<Item = T>, expected: impl IntoIterator<Item = T>, mode: Mode, ) -> Difference<T>100 pub(crate) fn edit_list<T: PartialEq + Copy>(
101 actual: impl IntoIterator<Item = T>,
102 expected: impl IntoIterator<Item = T>,
103 mode: Mode,
104 ) -> Difference<T> {
105 let actual: Vec<_> = actual.into_iter().collect();
106 let expected: Vec<_> = expected.into_iter().collect();
107
108 let mut paths_last: Vec<Path<T>> = Vec::new();
109
110 for distance in 0..=MAX_DISTANCE {
111 let mut paths_current = Vec::new();
112 for k in (-distance..=distance).step_by(2) {
113 // The following will be None when k is at the edges of the range,
114 // since no paths have been created for k outside the range in the
115 // previous iteration.
116 let path_k_minus_1 = paths_last.get(index_of_k(k - 1, -distance + 1));
117 let path_k_plus_1 = paths_last.get(index_of_k(k + 1, -distance + 1));
118
119 let (mut path, edit) = match (path_k_minus_1, path_k_plus_1) {
120 // This the first (outer) iteration.
121 (None, None) => (Path::default(), None),
122
123 // k = -distance. There is no previous parent path yet.
124 (None, Some(path_k_plus_1)) => (
125 path_k_plus_1.clone(),
126 expected.get(path_k_plus_1.expected_endpoint).copied().map(Edit::ExtraExpected),
127 ),
128
129 // k = distance. There is no next parent path yet.
130 (Some(path_k_minus_1), None) => (
131 path_k_minus_1.extend_actual_endpoint(),
132 actual.get(path_k_minus_1.actual_endpoint).copied().map(Edit::ExtraActual),
133 ),
134
135 // k is strictly between -distance and distance. Both parent paths were set in the
136 // last iteration.
137 (Some(path_k_minus_1), Some(path_k_plus_1)) => {
138 // This decides whether the algorithm prefers to add an edit
139 // from the actual or from the expected when the rows differ. We
140 // alternate so that the elements of differing blocks
141 // interleave rather than all elements of each respective
142 // side being output in a single block.
143 if (distance % 2 == 0
144 && path_k_plus_1.actual_endpoint > path_k_minus_1.actual_endpoint)
145 || (distance % 2 == 1
146 && path_k_plus_1.expected_endpoint > path_k_minus_1.expected_endpoint)
147 {
148 (
149 path_k_plus_1.clone(),
150 expected
151 .get(path_k_plus_1.expected_endpoint)
152 .copied()
153 .map(Edit::ExtraExpected),
154 )
155 } else {
156 (
157 path_k_minus_1.extend_actual_endpoint(),
158 actual
159 .get(path_k_minus_1.actual_endpoint)
160 .copied()
161 .map(Edit::ExtraActual),
162 )
163 }
164 }
165 };
166 path.edits.extend(edit);
167
168 // Advance through any common elements starting at the current path.
169 let (mut actual_endpoint, mut expected_endpoint) =
170 (path.actual_endpoint, (path.actual_endpoint as i32 - k) as usize);
171 while actual_endpoint < actual.len()
172 && expected_endpoint < expected.len()
173 && actual[actual_endpoint] == expected[expected_endpoint]
174 {
175 path.edits.push(Edit::Both(actual[actual_endpoint]));
176 (actual_endpoint, expected_endpoint) = (actual_endpoint + 1, expected_endpoint + 1);
177 }
178
179 // If we have exhausted both inputs, we are done.
180 if actual_endpoint == actual.len() && expected_endpoint == expected.len() {
181 return if path.edits.iter().any(|v| !matches!(v, Edit::Both(_))) {
182 if matches!(mode, Mode::Contains) {
183 compress_prefix_and_suffix(&mut path.edits);
184 }
185 Difference::Editable(path.edits)
186 } else {
187 Difference::Equal
188 };
189 }
190
191 path.actual_endpoint = actual_endpoint;
192 path.expected_endpoint = expected_endpoint;
193 paths_current.push(path);
194 }
195
196 if matches!(mode, Mode::Prefix) {
197 if let Some(path) = paths_current
198 .iter_mut()
199 .filter(|p| p.expected_endpoint == expected.len())
200 .max_by(|p1, p2| p1.edits.len().cmp(&p2.edits.len()))
201 {
202 // We've reached the end of the expected side but there could still be a
203 // corresponding line on the actual which we haven't picked up into the edit
204 // list. We'll just add it manually to the edit list. There's no
205 // real harm doing so -- worst case is that there's an
206 // additional line when there didn't have to be.
207 if let Some(Edit::ExtraExpected(_)) = path.edits.last() {
208 if path.actual_endpoint < actual.len() {
209 // The edits from the actual should come before the corresponding one from
210 // the expected, so we insert rather than push.
211 path.edits.insert(
212 path.edits.len() - 1,
213 Edit::ExtraActual(actual[path.actual_endpoint]),
214 );
215 }
216 }
217 path.edits.push(Edit::AdditionalActual);
218 return if path.edits.iter().any(|v| !matches!(v, Edit::Both(_))) {
219 Difference::Editable(std::mem::take(&mut path.edits))
220 } else {
221 Difference::Equal
222 };
223 }
224 }
225
226 paths_last = paths_current;
227 }
228
229 Difference::Unrelated
230 }
231
index_of_k(k: i32, k_min: i32) -> usize232 fn index_of_k(k: i32, k_min: i32) -> usize {
233 ((k - k_min) / 2) as usize
234 }
235
compress_prefix_and_suffix<T>(edits: &mut Vec<Edit<T>>)236 fn compress_prefix_and_suffix<T>(edits: &mut Vec<Edit<T>>) {
237 if let Some(mut first_non_extra_actual_edit) =
238 edits.iter().position(|e| !matches!(e, Edit::ExtraActual(_)))
239 {
240 if first_non_extra_actual_edit > 1
241 && matches!(edits[first_non_extra_actual_edit], Edit::ExtraExpected(_))
242 {
243 first_non_extra_actual_edit -= 1;
244 }
245 edits.splice(..first_non_extra_actual_edit, [Edit::AdditionalActual]);
246 }
247
248 if let Some(mut last_non_extra_actual_edit) =
249 edits.iter().rposition(|e| !matches!(e, Edit::ExtraActual(_)))
250 {
251 if last_non_extra_actual_edit < edits.len() - 1
252 && matches!(edits[last_non_extra_actual_edit], Edit::ExtraExpected(_))
253 {
254 last_non_extra_actual_edit += 1;
255 }
256 edits.splice(last_non_extra_actual_edit + 1.., [Edit::AdditionalActual]);
257 }
258 }
259
260 #[derive(Clone)]
261 struct Path<T: Clone> {
262 actual_endpoint: usize,
263 expected_endpoint: usize,
264 edits: Vec<Edit<T>>,
265 }
266
267 impl<T: Clone> Default for Path<T> {
default() -> Self268 fn default() -> Self {
269 Self { actual_endpoint: 0, expected_endpoint: 0, edits: vec![] }
270 }
271 }
272
273 impl<T: Clone> Path<T> {
extend_actual_endpoint(&self) -> Self274 fn extend_actual_endpoint(&self) -> Self {
275 Self {
276 actual_endpoint: self.actual_endpoint + 1,
277 expected_endpoint: self.expected_endpoint,
278 edits: self.edits.clone(),
279 }
280 }
281 }
282
283 #[cfg(test)]
284 mod tests {
285 use super::*;
286 use crate::prelude::*;
287 use quickcheck::{quickcheck, Arbitrary, TestResult};
288
289 #[test]
returns_equal_when_strings_are_equal() -> Result<()>290 fn returns_equal_when_strings_are_equal() -> Result<()> {
291 let result = edit_list(["A string"], ["A string"], Mode::Exact);
292 verify_that!(result, matches_pattern!(Difference::Equal))
293 }
294
295 #[test]
returns_sequence_of_two_common_parts() -> Result<()>296 fn returns_sequence_of_two_common_parts() -> Result<()> {
297 let result = edit_list(
298 ["A string (1)", "A string (2)"],
299 ["A string (1)", "A string (2)"],
300 Mode::Exact,
301 );
302 verify_that!(result, matches_pattern!(Difference::Equal))
303 }
304
305 #[test]
returns_extra_actual_when_only_actual_has_content() -> Result<()>306 fn returns_extra_actual_when_only_actual_has_content() -> Result<()> {
307 let result = edit_list(["A string"], [], Mode::Exact);
308 verify_that!(
309 result,
310 matches_pattern!(Difference::Editable(elements_are![matches_pattern!(
311 Edit::ExtraActual(eq("A string"))
312 )]))
313 )
314 }
315
316 #[test]
returns_extra_expected_when_only_expected_has_content() -> Result<()>317 fn returns_extra_expected_when_only_expected_has_content() -> Result<()> {
318 let result = edit_list([], ["A string"], Mode::Exact);
319 verify_that!(
320 result,
321 matches_pattern!(Difference::Editable(elements_are![matches_pattern!(
322 Edit::ExtraExpected(eq("A string"))
323 )]))
324 )
325 }
326
327 #[test]
returns_extra_actual_followed_by_extra_expected_with_two_unequal_strings() -> Result<()>328 fn returns_extra_actual_followed_by_extra_expected_with_two_unequal_strings() -> Result<()> {
329 let result = edit_list(["A string"], ["Another string"], Mode::Exact);
330 verify_that!(
331 result,
332 matches_pattern!(Difference::Editable(elements_are![
333 matches_pattern!(Edit::ExtraActual(eq("A string"))),
334 matches_pattern!(Edit::ExtraExpected(eq("Another string"))),
335 ]))
336 )
337 }
338
339 #[test]
interleaves_extra_actual_and_extra_expected_when_multiple_lines_differ() -> Result<()>340 fn interleaves_extra_actual_and_extra_expected_when_multiple_lines_differ() -> Result<()> {
341 let result =
342 edit_list(["A string", "A string"], ["Another string", "Another string"], Mode::Exact);
343 verify_that!(
344 result,
345 matches_pattern!(Difference::Editable(elements_are![
346 matches_pattern!(Edit::ExtraActual(eq("A string"))),
347 matches_pattern!(Edit::ExtraExpected(eq("Another string"))),
348 matches_pattern!(Edit::ExtraActual(eq("A string"))),
349 matches_pattern!(Edit::ExtraExpected(eq("Another string"))),
350 ]))
351 )
352 }
353
354 #[test]
returns_common_part_plus_difference_when_there_is_common_prefix() -> Result<()>355 fn returns_common_part_plus_difference_when_there_is_common_prefix() -> Result<()> {
356 let result = edit_list(
357 ["Common part", "Actual only"],
358 ["Common part", "Expected only"],
359 Mode::Exact,
360 );
361 verify_that!(
362 result,
363 matches_pattern!(Difference::Editable(elements_are![
364 matches_pattern!(Edit::Both(eq("Common part"))),
365 matches_pattern!(Edit::ExtraActual(eq("Actual only"))),
366 matches_pattern!(Edit::ExtraExpected(eq("Expected only"))),
367 ]))
368 )
369 }
370
371 #[test]
returns_common_part_plus_extra_actual_when_actual_has_extra_suffix() -> Result<()>372 fn returns_common_part_plus_extra_actual_when_actual_has_extra_suffix() -> Result<()> {
373 let result = edit_list(["Common part", "Actual only"], ["Common part"], Mode::Exact);
374 verify_that!(
375 result,
376 matches_pattern!(Difference::Editable(elements_are![
377 matches_pattern!(Edit::Both(eq("Common part"))),
378 matches_pattern!(Edit::ExtraActual(eq("Actual only"))),
379 ]))
380 )
381 }
382
383 #[test]
returns_common_part_plus_extra_expected_when_expected_has_extra_suffix() -> Result<()>384 fn returns_common_part_plus_extra_expected_when_expected_has_extra_suffix() -> Result<()> {
385 let result = edit_list(["Common part"], ["Common part", "Expected only"], Mode::Exact);
386 verify_that!(
387 result,
388 matches_pattern!(Difference::Editable(elements_are![
389 matches_pattern!(Edit::Both(eq("Common part"))),
390 matches_pattern!(Edit::ExtraExpected(eq("Expected only"))),
391 ]))
392 )
393 }
394
395 #[test]
returns_difference_plus_common_part_when_there_is_common_suffix() -> Result<()>396 fn returns_difference_plus_common_part_when_there_is_common_suffix() -> Result<()> {
397 let result = edit_list(
398 ["Actual only", "Common part"],
399 ["Expected only", "Common part"],
400 Mode::Exact,
401 );
402 verify_that!(
403 result,
404 matches_pattern!(Difference::Editable(elements_are![
405 matches_pattern!(Edit::ExtraActual(eq("Actual only"))),
406 matches_pattern!(Edit::ExtraExpected(eq("Expected only"))),
407 matches_pattern!(Edit::Both(eq("Common part"))),
408 ]))
409 )
410 }
411
412 #[test]
returns_difference_plus_common_part_plus_difference_when_there_is_common_infix() -> Result<()>413 fn returns_difference_plus_common_part_plus_difference_when_there_is_common_infix() -> Result<()>
414 {
415 let result = edit_list(
416 ["Actual only (1)", "Common part", "Actual only (2)"],
417 ["Expected only (1)", "Common part", "Expected only (2)"],
418 Mode::Exact,
419 );
420 verify_that!(
421 result,
422 matches_pattern!(Difference::Editable(elements_are![
423 matches_pattern!(Edit::ExtraActual(eq("Actual only (1)"))),
424 matches_pattern!(Edit::ExtraExpected(eq("Expected only (1)"))),
425 matches_pattern!(Edit::Both(eq("Common part"))),
426 matches_pattern!(Edit::ExtraActual(eq("Actual only (2)"))),
427 matches_pattern!(Edit::ExtraExpected(eq("Expected only (2)"))),
428 ]))
429 )
430 }
431
432 #[test]
returns_common_part_plus_difference_plus_common_part_when_there_is_common_prefix_and_suffix() -> Result<()>433 fn returns_common_part_plus_difference_plus_common_part_when_there_is_common_prefix_and_suffix()
434 -> Result<()> {
435 let result = edit_list(
436 ["Common part (1)", "Actual only", "Common part (2)"],
437 ["Common part (1)", "Expected only", "Common part (2)"],
438 Mode::Exact,
439 );
440 verify_that!(
441 result,
442 matches_pattern!(Difference::Editable(elements_are![
443 matches_pattern!(Edit::Both(eq("Common part (1)"))),
444 matches_pattern!(Edit::ExtraActual(eq("Actual only"))),
445 matches_pattern!(Edit::ExtraExpected(eq("Expected only"))),
446 matches_pattern!(Edit::Both(eq("Common part (2)"))),
447 ]))
448 )
449 }
450
451 #[test]
returns_common_part_plus_extra_actual_plus_common_part_when_there_is_common_prefix_and_suffix() -> Result<()>452 fn returns_common_part_plus_extra_actual_plus_common_part_when_there_is_common_prefix_and_suffix()
453 -> Result<()> {
454 let result = edit_list(
455 ["Common part (1)", "Actual only", "Common part (2)"],
456 ["Common part (1)", "Common part (2)"],
457 Mode::Exact,
458 );
459 verify_that!(
460 result,
461 matches_pattern!(Difference::Editable(elements_are![
462 matches_pattern!(Edit::Both(eq("Common part (1)"))),
463 matches_pattern!(Edit::ExtraActual(eq("Actual only"))),
464 matches_pattern!(Edit::Both(eq("Common part (2)"))),
465 ]))
466 )
467 }
468
469 #[test]
returns_common_part_plus_extra_expected_plus_common_part_when_there_is_common_prefix_and_suffix() -> Result<()>470 fn returns_common_part_plus_extra_expected_plus_common_part_when_there_is_common_prefix_and_suffix()
471 -> Result<()> {
472 let result = edit_list(
473 ["Common part (1)", "Common part (2)"],
474 ["Common part (1)", "Expected only", "Common part (2)"],
475 Mode::Exact,
476 );
477 verify_that!(
478 result,
479 matches_pattern!(Difference::Editable(elements_are![
480 matches_pattern!(Edit::Both(eq("Common part (1)"))),
481 matches_pattern!(Edit::ExtraExpected(eq("Expected only"))),
482 matches_pattern!(Edit::Both(eq("Common part (2)"))),
483 ]))
484 )
485 }
486
487 #[test]
skips_extra_parts_on_actual_at_end_in_prefix_mode() -> Result<()>488 fn skips_extra_parts_on_actual_at_end_in_prefix_mode() -> Result<()> {
489 let result = edit_list(
490 ["Common part", "Actual only"],
491 ["Expected only", "Common part"],
492 Mode::Prefix,
493 );
494 verify_that!(
495 result,
496 matches_pattern!(Difference::Editable(not(contains(matches_pattern!(
497 Edit::ExtraActual(eq("Actual only"))
498 )))))
499 )
500 }
501
502 #[test]
does_not_skip_extra_parts_on_actual_in_prefix_mode_at_end_when_they_are_in_common() -> Result<()>503 fn does_not_skip_extra_parts_on_actual_in_prefix_mode_at_end_when_they_are_in_common()
504 -> Result<()> {
505 let result = edit_list(
506 ["Actual only", "Common part"],
507 ["Expected only", "Common part"],
508 Mode::Prefix,
509 );
510 verify_that!(
511 result,
512 matches_pattern!(Difference::Editable(elements_are![
513 matches_pattern!(Edit::ExtraActual(eq("Actual only"))),
514 matches_pattern!(Edit::ExtraExpected(eq("Expected only"))),
515 matches_pattern!(Edit::Both(eq("Common part"))),
516 ]))
517 )
518 }
519
520 #[test]
does_not_skip_corresponding_line_on_actual_when_actual_and_expected_differ_in_prefix_mode() -> Result<()>521 fn does_not_skip_corresponding_line_on_actual_when_actual_and_expected_differ_in_prefix_mode()
522 -> Result<()> {
523 let result = edit_list(["Actual only"], ["Expected only"], Mode::Prefix);
524 verify_that!(
525 result,
526 matches_pattern!(Difference::Editable(elements_are![
527 matches_pattern!(Edit::ExtraActual(eq("Actual only"))),
528 matches_pattern!(Edit::ExtraExpected(eq("Expected only"))),
529 matches_pattern!(Edit::AdditionalActual),
530 ]))
531 )
532 }
533
534 #[test]
returns_unrelated_when_maximum_distance_exceeded() -> Result<()>535 fn returns_unrelated_when_maximum_distance_exceeded() -> Result<()> {
536 let result = edit_list(0..=50, 60..110, Mode::Exact);
537 verify_that!(result, matches_pattern!(Difference::Unrelated))
538 }
539
540 quickcheck! {
541 fn edit_list_edits_actual_to_expected(
542 actual: Vec<Alphabet>,
543 expected: Vec<Alphabet>
544 ) -> TestResult {
545 match edit_list(actual.clone(), expected.clone(), Mode::Exact) {
546 Difference::Equal => TestResult::from_bool(actual == expected),
547 Difference::Editable(edit_list) => {
548 TestResult::from_bool(apply_edits_to_actual(&edit_list, &actual) == expected)
549 }
550 Difference::Unrelated => {
551 if actual == expected {
552 TestResult::failed()
553 } else {
554 TestResult::discard()
555 }
556 }
557 }
558 }
559 }
560
561 quickcheck! {
562 fn edit_list_edits_expected_to_actual(
563 actual: Vec<Alphabet>,
564 expected: Vec<Alphabet>
565 ) -> TestResult {
566 match edit_list(actual.clone(), expected.clone(), Mode::Exact) {
567 Difference::Equal => TestResult::from_bool(actual == expected),
568 Difference::Editable(edit_list) => {
569 TestResult::from_bool(apply_edits_to_expected(&edit_list, &expected) == actual)
570 }
571 Difference::Unrelated => {
572 if actual == expected {
573 TestResult::failed()
574 } else {
575 TestResult::discard()
576 }
577 }
578 }
579 }
580 }
581
582 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
583 enum Alphabet {
584 A,
585 B,
586 C,
587 }
588
589 impl Arbitrary for Alphabet {
arbitrary(g: &mut quickcheck::Gen) -> Self590 fn arbitrary(g: &mut quickcheck::Gen) -> Self {
591 g.choose(&[Alphabet::A, Alphabet::B, Alphabet::C]).copied().unwrap()
592 }
593 }
594
apply_edits_to_actual<T: PartialEq + Debug + Copy>( edit_list: &[Edit<T>], actual: &[T], ) -> Vec<T>595 fn apply_edits_to_actual<T: PartialEq + Debug + Copy>(
596 edit_list: &[Edit<T>],
597 actual: &[T],
598 ) -> Vec<T> {
599 let mut result = Vec::new();
600 let mut actual_iter = actual.iter();
601 for edit in edit_list {
602 match edit {
603 Edit::ExtraActual(value) => {
604 assert_that!(actual_iter.next(), some(eq(value)));
605 }
606 Edit::ExtraExpected(value) => {
607 result.push(*value);
608 }
609 Edit::Both(value) => {
610 assert_that!(actual_iter.next(), some(eq(value)));
611 result.push(*value);
612 }
613 Edit::AdditionalActual => {
614 fail!("Unexpected Edit::AdditionalActual").unwrap();
615 }
616 }
617 }
618 assert_that!(actual_iter.next(), none());
619 result
620 }
621
apply_edits_to_expected<T: PartialEq + Debug + Copy>( edit_list: &[Edit<T>], expected: &[T], ) -> Vec<T>622 fn apply_edits_to_expected<T: PartialEq + Debug + Copy>(
623 edit_list: &[Edit<T>],
624 expected: &[T],
625 ) -> Vec<T> {
626 let mut result = Vec::new();
627 let mut expected_iter = expected.iter();
628 for edit in edit_list {
629 match edit {
630 Edit::ExtraActual(value) => {
631 result.push(*value);
632 }
633 Edit::ExtraExpected(value) => {
634 assert_that!(expected_iter.next(), some(eq(value)));
635 }
636 Edit::Both(value) => {
637 assert_that!(expected_iter.next(), some(eq(value)));
638 result.push(*value);
639 }
640 Edit::AdditionalActual => {
641 fail!("Unexpected Edit::AdditionalActual").unwrap();
642 }
643 }
644 }
645 assert_that!(expected_iter.next(), none());
646 result
647 }
648 }
649