20101200810

Committed 10 Dec 2025 02:01PM UTC coverage: 58.178% (-0.4%) from 58.588%

Build # 20101200810

Build Type

Pull #1220

github

Committed by

web-flow

Commit Message

Merge b5c63945b into eaae4b56d

Pull Request Pull Request #1220: feat(cinereus): improve tree matching for leaf nodes and filter no-op moves

Run Details

1584 of 2959 new or added lines in 18 files covered. (53.53%)

111 existing lines in 3 files now uncovered.

28391 of 48800 relevant lines covered (58.18%)

819.21 hits per line

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

98.96

/facet-diff-core/src/sequences.rs

//! Sequence diff types.
//!
//! These types represent the result of sequence diffing using Myers' algorithm.

use facet_reflect::Peek;

use crate::Diff;

/// An interspersed sequence of A and B values.
/// Pattern: [A?, (B, A)*, B?]
pub struct Interspersed<A, B> {
    /// The first A value (if any)
    pub first: Option<A>,
    /// Pairs of (B, A) values
    pub values: Vec<(B, A)>,
    /// The trailing B value (if any)
    pub last: Option<B>,
}

impl<A, B> Interspersed<A, B> {
    /// Get or insert a default at the front for the A type
    pub fn front_a(&mut self) -> &mut A
    where
        A: Default,
    {
        self.first.get_or_insert_default()
    }

    /// Get or insert a default at the front for the B type
    pub fn front_b(&mut self) -> &mut B
    where
        B: Default,
    {
        if let Some(a) = self.first.take() {
            self.values.insert(0, (B::default(), a));
        }

        if let Some((b, _)) = self.values.first_mut() {
            b
        } else {
            self.last.get_or_insert_default()
        }
    }
}

impl<A, B> Default for Interspersed<A, B> {
    fn default() -> Self {
        Self {
            first: Default::default(),
            values: Default::default(),
            last: Default::default(),
        }
    }
}

/// A group of values being replaced (removals paired with additions).
#[derive(Default)]
pub struct ReplaceGroup<'mem, 'facet> {
    /// The values being removed
    pub removals: Vec<Peek<'mem, 'facet>>,
    /// The values being added
    pub additions: Vec<Peek<'mem, 'facet>>,
}

impl<'mem, 'facet> ReplaceGroup<'mem, 'facet> {
    /// Push an addition at the front
    pub fn push_add(&mut self, addition: Peek<'mem, 'facet>) {
        // Note: The Myers algorithm backtracks and may interleave adds/removes
        // when costs are equal. We handle this by just collecting both.
        self.additions.insert(0, addition);
    }

    /// Push a removal at the front
    pub fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {
        self.removals.insert(0, removal);
    }
}

/// A group of updates containing replace groups interspersed with nested diffs.
#[derive(Default)]
pub struct UpdatesGroup<'mem, 'facet>(
    /// The interspersed structure of replace groups and diffs
    pub Interspersed<ReplaceGroup<'mem, 'facet>, Vec<Diff<'mem, 'facet>>>,
);

impl<'mem, 'facet> UpdatesGroup<'mem, 'facet> {
    /// Push an addition
    pub fn push_add(&mut self, addition: Peek<'mem, 'facet>) {
        self.0.front_a().push_add(addition);
    }

    /// Push a removal
    pub fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {
        self.0.front_a().push_remove(removal);
    }

    /// Flatten replace groups using closeness and diff-creating functions.
    ///
    /// - `closeness_fn`: takes two Peeks and returns a score (higher = more similar)
    /// - `diff_fn`: takes two Peeks and returns a Diff
    pub fn flatten_with<C, D>(&mut self, closeness_fn: C, diff_fn: D)
    where
        C: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> usize,
        D: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> Diff<'mem, 'facet>,
    {
        let Some(updates) = self.0.first.take() else {
            return;
        };

        let mut mem = vec![vec![0; updates.removals.len() + 1]];

        for x in 0..updates.removals.len() {
            let mut row = vec![0];

            for (y, addition) in updates.additions.iter().enumerate() {
                row.push(
                    row.last()
                        .copied()
                        .unwrap()
                        .max(mem[x][y] + closeness_fn(updates.removals[x], *addition)),
                );
            }

            mem.push(row);
        }

        let mut x = updates.removals.len();
        let mut y = updates.additions.len();

        while x > 0 || y > 0 {
            if x == 0 {
                self.push_add(updates.additions[y - 1]);
                y -= 1;
            } else if y == 0 {
                self.push_remove(updates.removals[x - 1]);
                x -= 1;
            } else if mem[x][y - 1] == mem[x][y] {
                self.push_add(updates.additions[y - 1]);
                y -= 1;
            } else {
                let diff = diff_fn(updates.removals[x - 1], updates.additions[y - 1]);
                self.0.front_b().insert(0, diff);

                x -= 1;
                y -= 1;
            }
        }
    }
}

/// Sequence updates: update groups interspersed with unchanged items.
#[derive(Default)]
pub struct Updates<'mem, 'facet>(
    /// The interspersed structure
    pub Interspersed<UpdatesGroup<'mem, 'facet>, Vec<Peek<'mem, 'facet>>>,
);

impl<'mem, 'facet> Updates<'mem, 'facet> {
    /// Push an addition at the front
    ///
    /// All `push_*` methods push from the front, because Myers' algorithm
    /// finds updates back to front.
    pub fn push_add(&mut self, addition: Peek<'mem, 'facet>) {
        self.0.front_a().push_add(addition);
    }

    /// Push a removal at the front
    ///
    /// All `push_*` methods push from the front, because Myers' algorithm
    /// finds updates back to front.
    pub fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {
        self.0.front_a().push_remove(removal);
    }

    /// Returns a measure of how similar the sequences are (higher = more similar)
    pub fn closeness(&self) -> usize {
        self.0.values.iter().map(|(x, _)| x.len()).sum::<usize>()
            + self.0.last.as_ref().map(|x| x.len()).unwrap_or_default()
    }

    /// Push a kept value at the front
    ///
    /// All `push_*` methods push from the front, because Myers' algorithm
    /// finds updates back to front.
    pub fn push_keep(&mut self, value: Peek<'mem, 'facet>) {
        self.0.front_b().insert(0, value);
    }

    /// Flatten all update groups using the provided closeness and diff functions.
    pub fn flatten_with<C, D>(&mut self, closeness_fn: C, diff_fn: D)
    where
        C: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> usize + Copy,
        D: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> Diff<'mem, 'facet> + Copy,
    {
        if let Some(update) = &mut self.0.first {
            update.flatten_with(closeness_fn, diff_fn);
        }

        for (_, update) in &mut self.0.values {
            update.flatten_with(closeness_fn, diff_fn);
        }
    }
}

1	//! Sequence diff types.
2	//!
3	//! These types represent the result of sequence diffing using Myers' algorithm.
4
5	use facet_reflect::Peek;
6
7	use crate::Diff;
8
9	/// An interspersed sequence of A and B values.
10	/// Pattern: [A?, (B, A)*, B?]
11	pub struct Interspersed<A, B> {
12	/// The first A value (if any)
13	pub first: Option<A>,
14	/// Pairs of (B, A) values
15	pub values: Vec<(B, A)>,
16	/// The trailing B value (if any)
17	pub last: Option<B>,
18	}
19
20	impl<A, B> Interspersed<A, B> {
21	/// Get or insert a default at the front for the A type
22	pub fn front_a(&mut self) -> &mut A	6,248✔
23	where	6,248✔
24	A: Default,	6,248✔
25	{
26	self.first.get_or_insert_default()	6,248✔
27	}	6,248✔
28
29	/// Get or insert a default at the front for the B type
30	pub fn front_b(&mut self) -> &mut B	1,550✔
31	where	1,550✔
32	B: Default,	1,550✔
33	{
34	if let Some(a) = self.first.take() {	1,550✔
35	self.values.insert(0, (B::default(), a));	37✔
36	}	1,513✔
37
38	if let Some((b, _)) = self.values.first_mut() {	1,550✔
39	b	78✔
40	} else {
41	self.last.get_or_insert_default()	1,472✔
42	}
43	}	1,550✔
44	}
45
46	impl<A, B> Default for Interspersed<A, B> {
47	fn default() -> Self {	2,968✔
48	Self {	2,968✔
49	first: Default::default(),	2,968✔
50	values: Default::default(),	2,968✔
51	last: Default::default(),	2,968✔
52	}	2,968✔
53	}	2,968✔
54	}
55
56	/// A group of values being replaced (removals paired with additions).
57	#[derive(Default)]
58	pub struct ReplaceGroup<'mem, 'facet> {
59	/// The values being removed
60	pub removals: Vec<Peek<'mem, 'facet>>,
61	/// The values being added
62	pub additions: Vec<Peek<'mem, 'facet>>,
63	}
64
65	impl<'mem, 'facet> ReplaceGroup<'mem, 'facet> {
66	/// Push an addition at the front
67	pub fn push_add(&mut self, addition: Peek<'mem, 'facet>) {	1,614✔
68	// Note: The Myers algorithm backtracks and may interleave adds/removes
69	// when costs are equal. We handle this by just collecting both.
70	self.additions.insert(0, addition);	1,614✔
71	}	1,614✔
72
73	/// Push a removal at the front
74	pub fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {	1,590✔
75	self.removals.insert(0, removal);	1,590✔
76	}	1,590✔
77	}
78
79	/// A group of updates containing replace groups interspersed with nested diffs.
80	#[derive(Default)]
81	pub struct UpdatesGroup<'mem, 'facet>(
82	/// The interspersed structure of replace groups and diffs
83	pub Interspersed<ReplaceGroup<'mem, 'facet>, Vec<Diff<'mem, 'facet>>>,
84	);
85
86	impl<'mem, 'facet> UpdatesGroup<'mem, 'facet> {
87	/// Push an addition
88	pub fn push_add(&mut self, addition: Peek<'mem, 'facet>) {	1,614✔
89	self.0.front_a().push_add(addition);	1,614✔
90	}	1,614✔
91
92	/// Push a removal
93	pub fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {	1,590✔
94	self.0.front_a().push_remove(removal);	1,590✔
95	}	1,590✔
96
97	/// Flatten replace groups using closeness and diff-creating functions.
98	///
99	/// - `closeness_fn`: takes two Peeks and returns a score (higher = more similar)
100	/// - `diff_fn`: takes two Peeks and returns a Diff
101	pub fn flatten_with<C, D>(&mut self, closeness_fn: C, diff_fn: D)	1,486✔
102	where	1,486✔
103	C: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> usize,	1,486✔
104	D: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> Diff<'mem, 'facet>,	1,486✔
105	{
106	let Some(updates) = self.0.first.take() else {	1,486✔
NEW 107	return;	×
108	};
109
110	let mut mem = vec![vec![0; updates.removals.len() + 1]];	1,486✔
111
112	for x in 0..updates.removals.len() {	1,516✔
113	let mut row = vec![0];	1,516✔
114
115	for (y, addition) in updates.additions.iter().enumerate() {	1,668✔
116	row.push(	1,668✔
117	row.last()	1,668✔
118	.copied()	1,668✔
119	.unwrap()	1,668✔
120	.max(mem[x][y] + closeness_fn(updates.removals[x], *addition)),	1,668✔
121	);	1,668✔
122	}	1,668✔
123
124	mem.push(row);	1,516✔
125	}
126
127	let mut x = updates.removals.len();	1,486✔
128	let mut y = updates.additions.len();	1,486✔
129
130	while x > 0 \|\| y > 0 {	3,088✔
131	if x == 0 {	1,602✔
132	self.push_add(updates.additions[y - 1]);	30✔
133	y -= 1;	30✔
134	} else if y == 0 {	1,572✔
135	self.push_remove(updates.removals[x - 1]);	74✔
136	x -= 1;	74✔
137	} else if mem[x][y - 1] == mem[x][y] {	1,498✔
138	self.push_add(updates.additions[y - 1]);	56✔
139	y -= 1;	56✔
140	} else {	1,442✔
141	let diff = diff_fn(updates.removals[x - 1], updates.additions[y - 1]);	1,442✔
142	self.0.front_b().insert(0, diff);	1,442✔
143		1,442✔
144	x -= 1;	1,442✔
145	y -= 1;	1,442✔
146	}	1,442✔
147	}
148	}	1,486✔
149	}
150
151	/// Sequence updates: update groups interspersed with unchanged items.
152	#[derive(Default)]
153	pub struct Updates<'mem, 'facet>(
154	/// The interspersed structure
155	pub Interspersed<UpdatesGroup<'mem, 'facet>, Vec<Peek<'mem, 'facet>>>,
156	);
157
158	impl<'mem, 'facet> Updates<'mem, 'facet> {
159	/// Push an addition at the front
160	///
161	/// All `push_*` methods push from the front, because Myers' algorithm
162	/// finds updates back to front.
163	pub fn push_add(&mut self, addition: Peek<'mem, 'facet>) {	1,528✔
164	self.0.front_a().push_add(addition);	1,528✔
165	}	1,528✔
166
167	/// Push a removal at the front
168	///
169	/// All `push_*` methods push from the front, because Myers' algorithm
170	/// finds updates back to front.
171	pub fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {	1,516✔
172	self.0.front_a().push_remove(removal);	1,516✔
173	}	1,516✔
174
175	/// Returns a measure of how similar the sequences are (higher = more similar)
176	pub fn closeness(&self) -> usize {	292✔
177	self.0.values.iter().map(\|(x, _)\| x.len()).sum::<usize>()	292✔
178	+ self.0.last.as_ref().map(\|x\| x.len()).unwrap_or_default()	292✔
179	}	292✔
180
181	/// Push a kept value at the front
182	///
183	/// All `push_*` methods push from the front, because Myers' algorithm
184	/// finds updates back to front.
185	pub fn push_keep(&mut self, value: Peek<'mem, 'facet>) {	108✔
186	self.0.front_b().insert(0, value);	108✔
187	}	108✔
188
189	/// Flatten all update groups using the provided closeness and diff functions.
190	pub fn flatten_with<C, D>(&mut self, closeness_fn: C, diff_fn: D)	1,482✔
191	where	1,482✔
192	C: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> usize + Copy,	1,482✔
193	D: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> Diff<'mem, 'facet> + Copy,	1,482✔
194	{
195	if let Some(update) = &mut self.0.first {	1,482✔
196	update.flatten_with(closeness_fn, diff_fn);	1,453✔
197	}	1,453✔
198
199	for (_, update) in &mut self.0.values {	1,482✔
200	update.flatten_with(closeness_fn, diff_fn);	33✔
201	}	33✔
202	}	1,482✔
203	}

facet-rs / facet / 20101200810

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