20114574768

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

Build # 20114574768

Build Type

push

github

Committed by

fasterthanlime

Commit Message

Fix: Allow dead_code and remove unused import in sequences.rs

Run Details

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

facet-rs / facet / 20114574768

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