19747635368

Committed 27 Nov 2025 08:54PM UTC coverage: 61.141% (-1.9%) from 63.042%

Build # 19747635368

Build Type

Pull #939

github

Committed by

web-flow

Commit Message

Merge a8b8472ef into 9c55d8a6b

Pull Request Pull Request #939: Merge facet-csv, facet-diff, facet-xdr, facet-asn1 into monorepo

Coverage Stats

715 of 1830 new or added lines in 8 files covered. (39.07%)

14112 of 23081 relevant lines covered (61.14%)

156.22 hits per line

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

0.0

/facet-diff/src/sequences.rs

1	use facet_reflect::Peek;
2
3	use crate::Diff;
4
5	pub(crate) struct Interspersed<A, B> {
6	pub(crate) first: Option<A>,
7	pub(crate) values: Vec<(B, A)>,
8	pub(crate) last: Option<B>,
9	}
10
11	impl<A, B> Interspersed<A, B> {
NEW 12	fn front_a(&mut self) -> &mut A	×
NEW 13	where	×
NEW 14	A: Default,	×
15	{
NEW 16	self.first.get_or_insert_default()	×
NEW 17	}	×
18
NEW 19	fn front_b(&mut self) -> &mut B	×
NEW 20	where	×
NEW 21	B: Default,	×
22	{
NEW 23	if let Some(a) = self.first.take() {	×
NEW 24	self.values.insert(0, (B::default(), a));	×
NEW 25	}	×
26
NEW 27	if let Some((b, _)) = self.values.first_mut() {	×
NEW 28	b	×
29	} else {
NEW 30	self.last.get_or_insert_default()	×
31	}
NEW 32	}	×
33	}
34
35	impl<A, B> Default for Interspersed<A, B> {
NEW 36	fn default() -> Self {	×
NEW 37	Self {	×
NEW 38	first: Default::default(),	×
NEW 39	values: Default::default(),	×
NEW 40	last: Default::default(),	×
NEW 41	}	×
NEW 42	}	×
43	}
44
45	#[derive(Default)]
46	pub(crate) struct ReplaceGroup<'mem, 'facet> {
47	pub(crate) removals: Vec<Peek<'mem, 'facet>>,
48	pub(crate) additions: Vec<Peek<'mem, 'facet>>,
49	}
50
51	impl<'mem, 'facet> ReplaceGroup<'mem, 'facet> {
NEW 52	fn push_add(&mut self, addition: Peek<'mem, 'facet>) {	×
NEW 53	assert!(	×
NEW 54	self.removals.is_empty(),	×
NEW 55	"We want all blocks of updates to have removals first, then additions, this should follow from our implementation of myers' algorithm"	×
56	);
NEW 57	self.additions.insert(0, addition);	×
NEW 58	}	×
59
NEW 60	fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {	×
NEW 61	self.removals.insert(0, removal);	×
NEW 62	}	×
63	}
64
65	#[derive(Default)]
66	pub(crate) struct UpdatesGroup<'mem, 'facet>(
67	pub(crate) Interspersed<ReplaceGroup<'mem, 'facet>, Vec<Diff<'mem, 'facet>>>,
68	);
69
70	impl<'mem, 'facet> UpdatesGroup<'mem, 'facet> {
NEW 71	fn push_add(&mut self, addition: Peek<'mem, 'facet>) {	×
NEW 72	self.0.front_a().push_add(addition);	×
NEW 73	}	×
74
NEW 75	fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {	×
NEW 76	self.0.front_a().push_remove(removal);	×
NEW 77	}	×
78
NEW 79	fn flatten(&mut self) {	×
NEW 80	let Some(updates) = self.0.first.take() else {	×
NEW 81	return;	×
82	};
83
NEW 84	let mut mem = vec![vec![0; updates.removals.len() + 1]];	×
85
NEW 86	for x in 0..updates.removals.len() {	×
NEW 87	let mut row = vec![0];	×
88
NEW 89	for y in 0..updates.additions.len() {	×
NEW 90	row.push(row.last().copied().unwrap().max(	×
NEW 91	mem[x][y]	×
NEW 92	+ Diff::new_peek(updates.removals[x], updates.additions[y]).closeness(),	×
NEW 93	));	×
NEW 94	}	×
95
NEW 96	mem.push(row);	×
97	}
98
NEW 99	let mut x = updates.removals.len();	×
NEW 100	let mut y = updates.additions.len();	×
101
NEW 102	while x > 0 \|\| y > 0 {	×
NEW 103	if x == 0 {	×
NEW 104	self.push_add(updates.additions[y - 1]);	×
NEW 105	y -= 1;	×
NEW 106	} else if y == 0 {	×
NEW 107	self.push_remove(updates.removals[x - 1]);	×
NEW 108	x -= 1;	×
NEW 109	} else if mem[x][y - 1] == mem[x][y] {	×
NEW 110	self.push_add(updates.additions[y - 1]);	×
NEW 111	y -= 1;	×
NEW 112	} else {	×
NEW 113	let diff = Diff::new_peek(updates.removals[x - 1], updates.additions[y - 1]);	×
NEW 114	self.0.front_b().insert(0, diff);	×
NEW 115		×
NEW 116	x -= 1;	×
NEW 117	y -= 1;	×
NEW 118	}	×
119	}
NEW 120	}	×
121	}
122
123	#[derive(Default)]
124	pub struct Updates<'mem, 'facet>(
125	pub(crate) Interspersed<UpdatesGroup<'mem, 'facet>, Vec<Peek<'mem, 'facet>>>,
126	);
127
128	impl<'mem, 'facet> Updates<'mem, 'facet> {
129	/// All `push_*` methods on [`Updates`] push from the front, because the myers' algorithm finds updates back to front.
NEW 130	pub(crate) fn push_add(&mut self, addition: Peek<'mem, 'facet>) {	×
NEW 131	self.0.front_a().push_add(addition);	×
NEW 132	}	×
133
134	/// All `push_*` methods on [`Updates`] push from the front, because the myers' algorithm finds updates back to front.
NEW 135	pub(crate) fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {	×
NEW 136	self.0.front_a().push_remove(removal);	×
NEW 137	}	×
138
NEW 139	pub(crate) fn closeness(&self) -> usize {	×
NEW 140	self.0.values.iter().map(\|(x, _)\| x.len()).sum::<usize>()	×
NEW 141	+ self.0.last.as_ref().map(\|x\| x.len()).unwrap_or_default()	×
NEW 142	}	×
143
144	/// All `push_*` methods on [`Updates`] push from the front, because the myers' algorithm finds updates back to front.
NEW 145	fn push_keep(&mut self, value: Peek<'mem, 'facet>) {	×
NEW 146	self.0.front_b().insert(0, value);	×
NEW 147	}	×
148
NEW 149	fn flatten(&mut self) {	×
NEW 150	if let Some(update) = &mut self.0.first {	×
NEW 151	update.flatten()	×
NEW 152	}	×
153
NEW 154	for (_, update) in &mut self.0.values {	×
NEW 155	update.flatten()	×
156	}
NEW 157	}	×
158	}
159
160	/// Gets the diff of a sequence by using myers' algorithm
NEW 161	pub fn diff<'mem, 'facet>(	×
NEW 162	a: Vec<Peek<'mem, 'facet>>,	×
NEW 163	b: Vec<Peek<'mem, 'facet>>,	×
NEW 164	) -> Updates<'mem, 'facet> {	×
165	// Moving l-t-r represents removing an element from a
166	// Moving t-t-b represents adding an element from b
167	//
168	// Moving diagonally does both, which has no effect and thus has no cost
169	// This can only be done when the items are the same
170	//
NEW 171	let mut mem = vec![vec![0; a.len() + 1]];	×
172
NEW 173	for y in 0..b.len() {	×
NEW 174	let mut next = vec![0];	×
NEW 175	for x in 0..a.len() {	×
NEW 176	let mut v = mem[y][x + 1].min(next[x]) + 1;	×
NEW 177	if Diff::new_peek(a[x], b[y]).is_equal() {	×
NEW 178	v = v.min(mem[y][x]);	×
NEW 179	}	×
180
NEW 181	next.push(v);	×
182	}
183
NEW 184	mem.push(next);	×
185	}
186
NEW 187	let mut updates = Updates::default();	×
188
NEW 189	let mut x = a.len();	×
NEW 190	let mut y = b.len();	×
NEW 191	while x > 0 \|\| y > 0 {	×
NEW 192	if y == 0 {	×
NEW 193	updates.push_remove(a[x - 1]);	×
NEW 194	x -= 1;	×
NEW 195	} else if x == 0 {	×
NEW 196	updates.push_add(b[y - 1]);	×
NEW 197	y -= 1;	×
NEW 198	} else if Diff::new_peek(a[x - 1], b[y - 1]).is_equal()	×
NEW 199	&& mem[y - 1][x - 1] <= mem[y][x - 1].min(mem[y - 1][x]) + 1	×
NEW 200	{	×
NEW 201	updates.push_keep(a[x - 1]);	×
NEW 202	x -= 1;	×
NEW 203	y -= 1;	×
NEW 204	} else if mem[y][x - 1] < mem[y - 1][x] {	×
NEW 205	updates.push_remove(a[x - 1]);	×
NEW 206	x -= 1;	×
NEW 207	} else {	×
NEW 208	updates.push_add(b[y - 1]);	×
NEW 209	y -= 1;	×
NEW 210	}	×
211	}
212
NEW 213	updates.flatten();	×
NEW 214	updates	×
NEW 215	}	×

facet-rs / facet / 19747635368

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