20114490114

Committed 10 Dec 2025 09:54PM UTC coverage: 57.703% (+0.002%) from 57.701%

Build # 20114490114

Build Type

Pull #1239

github

Committed by

web-flow

Commit Message

Merge 322ec5557 into 505339da4

Pull Request Pull Request #1239: Unify facet-assert formatting with facet-diff

Run Details

73 of 78 new or added lines in 3 files covered. (93.59%)

9 existing lines in 1 file now uncovered.

28236 of 48933 relevant lines covered (57.7%)

6362.0 hits per line

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

83.13

/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::{DiffOptions, diff_new_peek, diff_new_peek_with_options};

/// 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> {
    diff_with_options(a, b, &DiffOptions::default())
}

/// Gets the diff of a sequence by using Myers' algorithm with options
pub fn diff_with_options<'mem, 'facet>(
    a: Vec<Peek<'mem, 'facet>>,
    b: Vec<Peek<'mem, 'facet>>,
    options: &DiffOptions,
) -> 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_with_options(*a_item, *b_item, options).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_with_options(a, b, options);
    }
    // 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_with_options(a[x], b[y], options).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_with_options(a[x - 1], b[y - 1], options).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> {
    simple_diff_with_options(a, b, &DiffOptions::default())
}

fn simple_diff_with_options<'mem, 'facet>(
    a: Vec<Peek<'mem, 'facet>>,
    b: Vec<Peek<'mem, 'facet>>,
    _options: &DiffOptions,
) -> 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::{DiffOptions, diff_new_peek, diff_new_peek_with_options};
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
NEW 15	pub fn diff<'mem, 'facet>(	×
UNCOV 16	a: Vec<Peek<'mem, 'facet>>,	×
UNCOV 17	b: Vec<Peek<'mem, 'facet>>,	×
UNCOV 18	) -> Updates<'mem, 'facet> {	×
NEW 19	diff_with_options(a, b, &DiffOptions::default())	×
NEW 20	}	×
21
22	/// Gets the diff of a sequence by using Myers' algorithm with options
23	pub fn diff_with_options<'mem, 'facet>(	189,409✔
24	a: Vec<Peek<'mem, 'facet>>,	189,409✔
25	b: Vec<Peek<'mem, 'facet>>,	189,409✔
26	options: &DiffOptions,	189,409✔
27	) -> Updates<'mem, 'facet> {	189,409✔
28	// trace!("sequences::diff called with a.len()={}, b.len()={}", a.len(), b.len());
29
30	// Quick check: if lengths match and all elements are structurally equal, return empty
31	if a.len() == b.len() {	189,409✔
32	let all_equal = a.iter().zip(&b).all(\|(a_item, b_item)\| {	189,389✔
33	diff_new_peek_with_options(a_item, b_item, options).is_equal()	188,860✔
34	});	188,860✔
35	if all_equal {	189,389✔
36	return Updates::default();	188,935✔
37	}	454✔
38	}	20✔
39
40	// For very large sequences, fall back to simple comparison to avoid
41	// exponential blowup in flatten_with
42	if a.len() > MAX_SEQUENCE_SIZE \|\| b.len() > MAX_SEQUENCE_SIZE {	474✔
43	trace!("Using simple_diff fallback (size limit exceeded)");	1✔
44	return simple_diff_with_options(a, b, options);	1✔
45	}	473✔
46	// Moving l-t-r represents removing an element from a
47	// Moving t-t-b represents adding an element from b
48	//
49	// Moving diagonally does both, which has no effect and thus has no cost
50	// This can only be done when the items are the same
51	//
52	let mut mem = vec![vec![0; a.len() + 1]];	473✔
53
54	for y in 0..b.len() {	676✔
55	let mut next = vec![0];	676✔
56	for x in 0..a.len() {	1,726✔
57	let mut v = mem[y][x + 1].min(next[x]) + 1;	1,726✔
58	if diff_new_peek_with_options(a[x], b[y], options).is_equal() {	1,726✔
59	v = v.min(mem[y][x]);	303✔
60	}	1,423✔
61
62	next.push(v);	1,726✔
63	}
64
65	mem.push(next);	676✔
66	}
67
68	let mut updates = Updates::default();	473✔
69
70	let mut x = a.len();	473✔
71	let mut y = b.len();	473✔
72	while x > 0 \|\| y > 0 {	1,658✔
73	if y == 0 {	1,185✔
74	updates.push_remove(a[x - 1]);	9✔
75	x -= 1;	9✔
76	} else if x == 0 {	1,176✔
77	updates.push_add(b[y - 1]);	487✔
78	y -= 1;	487✔
79	} else if diff_new_peek_with_options(a[x - 1], b[y - 1], options).is_equal()	689✔
80	&& mem[y - 1][x - 1] <= mem[y][x - 1].min(mem[y - 1][x]) + 1	158✔
81	{	158✔
82	updates.push_keep(a[x - 1]);	158✔
83	x -= 1;	158✔
84	y -= 1;	158✔
85	} else if mem[y][x - 1] <= mem[y - 1][x] {	531✔
86	// When costs are equal, prefer removes first to maintain the invariant	500✔
87	// that within a replace group, all removals come before additions	500✔
88	updates.push_remove(a[x - 1]);	500✔
89	x -= 1;	500✔
90	} else {	500✔
91	updates.push_add(b[y - 1]);	31✔
92	y -= 1;	31✔
93	}	31✔
94	}
95
96	// TODO: flatten_with causes exponential blowup with nested structures
97	// Temporarily disabled until we can add proper depth tracking
98	// if a.len() <= 2 && b.len() <= 2 {
99	// updates.flatten_with(\|a, b\| diff_closeness(&diff_new_peek(a, b)), diff_new_peek);
100	// }
101	updates	473✔
102	}	189,409✔
103
104	/// Simple fallback diff for large sequences that doesn't use Myers' algorithm.
105	/// Just treats all differences as removes followed by adds.
UNCOV 106	fn simple_diff<'mem, 'facet>(	×
NEW 107	a: Vec<Peek<'mem, 'facet>>,	×
UNCOV 108	b: Vec<Peek<'mem, 'facet>>,	×
UNCOV 109	) -> Updates<'mem, 'facet> {	×
UNCOV 110	simple_diff_with_options(a, b, &DiffOptions::default())	×
NEW 111	}	×
112
113	fn simple_diff_with_options<'mem, 'facet>(	1✔
114	a: Vec<Peek<'mem, 'facet>>,	1✔
115	b: Vec<Peek<'mem, 'facet>>,	1✔
116	_options: &DiffOptions,	1✔
117	) -> Updates<'mem, 'facet> {	1✔
118	trace!(	1✔
119	"simple_diff: creating replace group with {} removals and {} additions",
UNCOV 120	a.len(),	×
UNCOV 121	b.len()	×
122	);
123	let mut updates = Updates::default();	1✔
124
125	// Remove all from a
126	for item in a.iter().rev() {	100✔
127	updates.push_remove(*item);	100✔
128	}	100✔
129
130	// Add all from b
131	for item in b.iter().rev() {	200✔
132	updates.push_add(*item);	200✔
133	}	200✔
134
135	updates	1✔
136	}	1✔

facet-rs / facet / 20114490114

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