20073264397

Committed 09 Dec 2025 05:52PM UTC coverage: 58.325% (-0.2%) from 58.514%

Build # 20073264397

Build Type

push

github

Committed by

fasterthanlime

Commit Message

feat(facet-reflect): add structural_hash method to Peek for Merkle-tree hashing

Run Details

0 of 146 new or added lines in 2 files covered. (0.0%)

1 existing line in 1 file now uncovered.

26311 of 45111 relevant lines covered (58.33%)

628.88 hits per line

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

99.23

/facet-diff/src/sequences.rs

use facet_reflect::Peek;

use crate::Diff;

pub(crate) struct Interspersed<A, B> {
    pub(crate) first: Option<A>,
    pub(crate) values: Vec<(B, A)>,
    pub(crate) last: Option<B>,
}

impl<A, B> Interspersed<A, B> {
    fn front_a(&mut self) -> &mut A
    where
        A: Default,
    {
        self.first.get_or_insert_default()
    }

    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(),
        }
    }
}

#[derive(Default)]
pub(crate) struct ReplaceGroup<'mem, 'facet> {
    pub(crate) removals: Vec<Peek<'mem, 'facet>>,
    pub(crate) additions: Vec<Peek<'mem, 'facet>>,
}

impl<'mem, 'facet> ReplaceGroup<'mem, 'facet> {
    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);
    }

    fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {
        self.removals.insert(0, removal);
    }
}

#[derive(Default)]
pub(crate) struct UpdatesGroup<'mem, 'facet>(
    pub(crate) Interspersed<ReplaceGroup<'mem, 'facet>, Vec<Diff<'mem, 'facet>>>,
);

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

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

    fn flatten(&mut self) {
        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] + Diff::new_peek(updates.removals[x], *addition).closeness(),
                    ),
                );
            }

            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::new_peek(updates.removals[x - 1], updates.additions[y - 1]);
                self.0.front_b().insert(0, diff);

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

#[derive(Default)]
pub struct Updates<'mem, 'facet>(
    pub(crate) Interspersed<UpdatesGroup<'mem, 'facet>, Vec<Peek<'mem, 'facet>>>,
);

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

    /// All `push_*` methods on [`Updates`] push from the front, because the myers' algorithm finds updates back to front.
    pub(crate) fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {
        self.0.front_a().push_remove(removal);
    }

    pub(crate) 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()
    }

    /// All `push_*` methods on [`Updates`] push from the front, because the myers' algorithm finds updates back to front.
    fn push_keep(&mut self, value: Peek<'mem, 'facet>) {
        self.0.front_b().insert(0, value);
    }

    fn flatten(&mut self) {
        if let Some(update) = &mut self.0.first {
            update.flatten()
        }

        for (_, update) in &mut self.0.values {
            update.flatten()
        }
    }
}

/// 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> {
    // 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(a[x], b[y]).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(a[x - 1], b[y - 1]).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;
        }
    }

    updates.flatten();
    updates
}

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

facet-rs / facet / 20073264397

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