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

44.79

/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	2,666✔
23	where	2,666✔
24	A: Default,	2,666✔
25	{
26	self.first.get_or_insert_default()	2,666✔
27	}	2,666✔
28
29	/// Get or insert a default at the front for the B type
30	pub fn front_b(&mut self) -> &mut B	158✔
31	where	158✔
32	B: Default,	158✔
33	{
34	if let Some(a) = self.first.take() {	158✔
35	self.values.insert(0, (B::default(), a));	36✔
36	}	122✔
37
38	if let Some((b, _)) = self.values.first_mut() {	158✔
39	b	81✔
40	} else {
41	self.last.get_or_insert_default()	77✔
42	}
43	}	158✔
44	}
45
46	impl<A, B> Default for Interspersed<A, B> {
47	fn default() -> Self {	189,895✔
48	Self {	189,895✔
49	first: Default::default(),	189,895✔
50	values: Default::default(),	189,895✔
51	last: Default::default(),	189,895✔
52	}	189,895✔
53	}	189,895✔
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>) {	721✔
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);	721✔
71	}	721✔
72
73	/// Push a removal at the front
74	pub fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {	612✔
75	self.removals.insert(0, removal);	612✔
76	}	612✔
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>) {	721✔
89	self.0.front_a().push_add(addition);	721✔
90	}	721✔
91
92	/// Push a removal
93	pub fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {	612✔
94	self.0.front_a().push_remove(removal);	612✔
95	}	612✔
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)	×
102	where	×
103	C: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> usize,	×
104	D: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> Diff<'mem, 'facet>,	×
105	{
106	let Some(updates) = self.0.first.take() else {	×
107	return;	×
108	};
109
110	let mut mem = vec![vec![0; updates.removals.len() + 1]];	×
111
112	for x in 0..updates.removals.len() {	×
113	let mut row = vec![0];	×
114
115	for (y, addition) in updates.additions.iter().enumerate() {	×
116	row.push(	×
117	row.last()	×
118	.copied()	×
119	.unwrap()	×
120	.max(mem[x][y] + closeness_fn(updates.removals[x], *addition)),	×
121	);	×
122	}	×
123
124	mem.push(row);	×
125	}
126
127	let mut x = updates.removals.len();	×
128	let mut y = updates.additions.len();	×
129
130	while x > 0 \|\| y > 0 {	×
131	if x == 0 {	×
132	self.push_add(updates.additions[y - 1]);	×
133	y -= 1;	×
134	} else if y == 0 {	×
135	self.push_remove(updates.removals[x - 1]);	×
136	x -= 1;	×
137	} else if mem[x][y - 1] == mem[x][y] {	×
138	self.push_add(updates.additions[y - 1]);	×
139	y -= 1;	×
140	} else {	×
141	let diff = diff_fn(updates.removals[x - 1], updates.additions[y - 1]);	×
142	self.0.front_b().insert(0, diff);	×
143		×
144	x -= 1;	×
145	y -= 1;	×
146	}	×
147	}
148	}	×
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>) {	721✔
164	self.0.front_a().push_add(addition);	721✔
165	}	721✔
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>) {	612✔
172	self.0.front_a().push_remove(removal);	612✔
173	}	612✔
174
175	/// Returns a measure of how similar the sequences are (higher = more similar)
176	pub fn closeness(&self) -> usize {	×
177	self.0.values.iter().map(\|(x, _)\| x.len()).sum::<usize>()	×
178	+ self.0.last.as_ref().map(\|x\| x.len()).unwrap_or_default()	×
179	}	×
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>) {	158✔
186	self.0.front_b().insert(0, value);	158✔
187	}	158✔
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)	×
191	where	×
192	C: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> usize + Copy,	×
193	D: Fn(Peek<'mem, 'facet>, Peek<'mem, 'facet>) -> Diff<'mem, 'facet> + Copy,	×
194	{
195	if let Some(update) = &mut self.0.first {	×
196	update.flatten_with(closeness_fn, diff_fn);	×
197	}	×
198
199	for (_, update) in &mut self.0.values {	×
200	update.flatten_with(closeness_fn, diff_fn);	×
201	}	×
202	}	×
203	}

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