20111913541

Committed 10 Dec 2025 08:11PM UTC coverage: 57.688% (-0.04%) from 57.724%

Build # 20111913541

Build Type

push

github

Committed by

fasterthanlime

Commit Message

mh

Run Details

28366 of 49171 relevant lines covered (57.69%)

6269.04 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.14

/facet-diff/src/sequences.rs

//! Sequence diffing using Myers' algorithm.

use facet_diff_core::Updates;
use facet_reflect::Peek;
use log::trace;

use crate::diff::{diff_closeness, diff_new_peek};

/// Maximum size for sequences to use Myers' algorithm.
/// Larger sequences fall back to simple element-by-element comparison
/// to prevent exponential blowup.
const MAX_SEQUENCE_SIZE: usize = 100;

/// Gets the diff of a sequence by using Myers' algorithm
pub fn diff<'mem, 'facet>(
    a: Vec<Peek<'mem, 'facet>>,
    b: Vec<Peek<'mem, 'facet>>,
) -> Updates<'mem, 'facet> {
    // trace!("sequences::diff called with a.len()={}, b.len()={}", a.len(), b.len());

    // Quick check: if lengths match and all elements are structurally equal, return empty
    if a.len() == b.len() {
        let all_equal = a
            .iter()
            .zip(&b)
            .all(|(a_item, b_item)| diff_new_peek(*a_item, *b_item).is_equal());
        if all_equal {
            return Updates::default();
        }
    }

    // For very large sequences, fall back to simple comparison to avoid
    // exponential blowup in flatten_with
    if a.len() > MAX_SEQUENCE_SIZE || b.len() > MAX_SEQUENCE_SIZE {
        trace!("Using simple_diff fallback (size limit exceeded)");
        return simple_diff(a, b);
    }
    // Moving l-t-r represents removing an element from a
    // Moving t-t-b represents adding an element from b
    //
    // Moving diagonally does both, which has no effect and thus has no cost
    // This can only be done when the items are the same
    //
    let mut mem = vec![vec![0; a.len() + 1]];

    for y in 0..b.len() {
        let mut next = vec![0];
        for x in 0..a.len() {
            let mut v = mem[y][x + 1].min(next[x]) + 1;
            if diff_new_peek(a[x], b[y]).is_equal() {
                v = v.min(mem[y][x]);
            }

            next.push(v);
        }

        mem.push(next);
    }

    let mut updates = Updates::default();

    let mut x = a.len();
    let mut y = b.len();
    while x > 0 || y > 0 {
        if y == 0 {
            updates.push_remove(a[x - 1]);
            x -= 1;
        } else if x == 0 {
            updates.push_add(b[y - 1]);
            y -= 1;
        } else if diff_new_peek(a[x - 1], b[y - 1]).is_equal()
            && mem[y - 1][x - 1] <= mem[y][x - 1].min(mem[y - 1][x]) + 1
        {
            updates.push_keep(a[x - 1]);
            x -= 1;
            y -= 1;
        } else if mem[y][x - 1] <= mem[y - 1][x] {
            // When costs are equal, prefer removes first to maintain the invariant
            // that within a replace group, all removals come before additions
            updates.push_remove(a[x - 1]);
            x -= 1;
        } else {
            updates.push_add(b[y - 1]);
            y -= 1;
        }
    }

    // TODO: flatten_with causes exponential blowup with nested structures
    // Temporarily disabled until we can add proper depth tracking
    // if a.len() <= 2 && b.len() <= 2 {
    //     updates.flatten_with(|a, b| diff_closeness(&diff_new_peek(a, b)), diff_new_peek);
    // }
    updates
}

/// Simple fallback diff for large sequences that doesn't use Myers' algorithm.
/// Just treats all differences as removes followed by adds.
fn simple_diff<'mem, 'facet>(
    a: Vec<Peek<'mem, 'facet>>,
    b: Vec<Peek<'mem, 'facet>>,
) -> Updates<'mem, 'facet> {
    trace!(
        "simple_diff: creating replace group with {} removals and {} additions",
        a.len(),
        b.len()
    );
    let mut updates = Updates::default();

    // Remove all from a
    for item in a.iter().rev() {
        updates.push_remove(*item);
    }

    // Add all from b
    for item in b.iter().rev() {
        updates.push_add(*item);
    }

    updates
}

1	//! Sequence diffing using Myers' algorithm.
2
3	use facet_diff_core::Updates;
4	use facet_reflect::Peek;
5	use log::trace;
6
7	use crate::diff::{diff_closeness, diff_new_peek};
8
9	/// Maximum size for sequences to use Myers' algorithm.
10	/// Larger sequences fall back to simple element-by-element comparison
11	/// to prevent exponential blowup.
12	const MAX_SEQUENCE_SIZE: usize = 100;
13
14	/// Gets the diff of a sequence by using Myers' algorithm
15	pub fn diff<'mem, 'facet>(	189,409✔
16	a: Vec<Peek<'mem, 'facet>>,	189,409✔
17	b: Vec<Peek<'mem, 'facet>>,	189,409✔
18	) -> Updates<'mem, 'facet> {	189,409✔
19	// trace!("sequences::diff called with a.len()={}, b.len()={}", a.len(), b.len());
20
21	// Quick check: if lengths match and all elements are structurally equal, return empty
22	if a.len() == b.len() {	189,409✔
23	let all_equal = a	189,389✔
24	.iter()	189,389✔
25	.zip(&b)	189,389✔
26	.all(\|(a_item, b_item)\| diff_new_peek(a_item, b_item).is_equal());	189,389✔
27	if all_equal {	189,389✔
28	return Updates::default();	188,934✔
29	}	455✔
30	}	20✔
31
32	// For very large sequences, fall back to simple comparison to avoid
33	// exponential blowup in flatten_with
34	if a.len() > MAX_SEQUENCE_SIZE \|\| b.len() > MAX_SEQUENCE_SIZE {	475✔
35	trace!("Using simple_diff fallback (size limit exceeded)");	1✔
36	return simple_diff(a, b);	1✔
37	}	474✔
38	// Moving l-t-r represents removing an element from a
39	// Moving t-t-b represents adding an element from b
40	//
41	// Moving diagonally does both, which has no effect and thus has no cost
42	// This can only be done when the items are the same
43	//
44	let mut mem = vec![vec![0; a.len() + 1]];	474✔
45
46	for y in 0..b.len() {	679✔
47	let mut next = vec![0];	679✔
48	for x in 0..a.len() {	1,735✔
49	let mut v = mem[y][x + 1].min(next[x]) + 1;	1,735✔
50	if diff_new_peek(a[x], b[y]).is_equal() {	1,735✔
51	v = v.min(mem[y][x]);	303✔
52	}	1,432✔
53
54	next.push(v);	1,735✔
55	}
56
57	mem.push(next);	679✔
58	}
59
60	let mut updates = Updates::default();	474✔
61
62	let mut x = a.len();	474✔
63	let mut y = b.len();	474✔
64	while x > 0 \|\| y > 0 {	1,665✔
65	if y == 0 {	1,191✔
66	updates.push_remove(a[x - 1]);	9✔
67	x -= 1;	9✔
68	} else if x == 0 {	1,182✔
69	updates.push_add(b[y - 1]);	490✔
70	y -= 1;	490✔
71	} else if diff_new_peek(a[x - 1], b[y - 1]).is_equal()	692✔
72	&& mem[y - 1][x - 1] <= mem[y][x - 1].min(mem[y - 1][x]) + 1	158✔
73	{	158✔
74	updates.push_keep(a[x - 1]);	158✔
75	x -= 1;	158✔
76	y -= 1;	158✔
77	} else if mem[y][x - 1] <= mem[y - 1][x] {	534✔
78	// When costs are equal, prefer removes first to maintain the invariant	503✔
79	// that within a replace group, all removals come before additions	503✔
80	updates.push_remove(a[x - 1]);	503✔
81	x -= 1;	503✔
82	} else {	503✔
83	updates.push_add(b[y - 1]);	31✔
84	y -= 1;	31✔
85	}	31✔
86	}
87
88	// TODO: flatten_with causes exponential blowup with nested structures
89	// Temporarily disabled until we can add proper depth tracking
90	// if a.len() <= 2 && b.len() <= 2 {
91	// updates.flatten_with(\|a, b\| diff_closeness(&diff_new_peek(a, b)), diff_new_peek);
92	// }
93	updates	474✔
94	}	189,409✔
95
96	/// Simple fallback diff for large sequences that doesn't use Myers' algorithm.
97	/// Just treats all differences as removes followed by adds.
98	fn simple_diff<'mem, 'facet>(	1✔
99	a: Vec<Peek<'mem, 'facet>>,	1✔
100	b: Vec<Peek<'mem, 'facet>>,	1✔
101	) -> Updates<'mem, 'facet> {	1✔
102	trace!(	1✔
103	"simple_diff: creating replace group with {} removals and {} additions",
104	a.len(),	×
105	b.len()	×
106	);
107	let mut updates = Updates::default();	1✔
108
109	// Remove all from a
110	for item in a.iter().rev() {	100✔
111	updates.push_remove(*item);	100✔
112	}	100✔
113
114	// Add all from b
115	for item in b.iter().rev() {	200✔
116	updates.push_add(*item);	200✔
117	}	200✔
118
119	updates	1✔
120	}	1✔

facet-rs / facet / 20111913541

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous