16482855623

Committed 23 Jul 2025 10:08PM UTC coverage: 58.447% (-0.2%) from 58.68%

Build # 16482855623

Build Type

Pull #855

github

Committed by

web-flow

Commit Message

Merge dca4c2302 into 5e8e214d1

Pull Request Pull Request #855: wip: Remove 'shape lifetime

Run Details

400 of 572 new or added lines in 70 files covered. (69.93%)

3 existing lines in 3 files now uncovered.

11939 of 20427 relevant lines covered (58.45%)

120.58 hits per line

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

0.0

/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>) {
        assert!(
            self.removals.is_empty(),
            "We want all blocks of updates to have removals first, then additions, this should follow from our implementation of myers' algorithm"
        );
        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 in 0..updates.additions.len() {
                row.push(row.last().copied().unwrap().max(
                    mem[x][y]
                        + Diff::new_peek(updates.removals[x], updates.additions[y]).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] {
            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	×
13	where	×
14	A: Default,	×
15	{
16	self.first.get_or_insert_default()	×
17	}	×
18
19	fn front_b(&mut self) -> &mut B	×
20	where	×
21	B: Default,	×
22	{
23	if let Some(a) = self.first.take() {	×
24	self.values.insert(0, (B::default(), a));	×
25	}	×
26
27	if let Some((b, _)) = self.values.first_mut() {	×
28	b	×
29	} else {
30	self.last.get_or_insert_default()	×
31	}
32	}	×
33	}
34
35	impl<A, B> Default for Interspersed<A, B> {
36	fn default() -> Self {	×
37	Self {	×
38	first: Default::default(),	×
39	values: Default::default(),	×
40	last: Default::default(),	×
41	}	×
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>) {	×
53	assert!(	×
54	self.removals.is_empty(),	×
55	"We want all blocks of updates to have removals first, then additions, this should follow from our implementation of myers' algorithm"	×
56	);
57	self.additions.insert(0, addition);	×
58	}	×
59
NEW 60	fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {	×
61	self.removals.insert(0, removal);	×
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>) {	×
72	self.0.front_a().push_add(addition);	×
73	}	×
74
NEW 75	fn push_remove(&mut self, removal: Peek<'mem, 'facet>) {	×
76	self.0.front_a().push_remove(removal);	×
77	}	×
78
79	fn flatten(&mut self) {	×
80	let Some(updates) = self.0.first.take() else {	×
81	return;	×
82	};
83
84	let mut mem = vec![vec![0; updates.removals.len() + 1]];	×
85
86	for x in 0..updates.removals.len() {	×
87	let mut row = vec![0];	×
88
89	for y in 0..updates.additions.len() {	×
90	row.push(row.last().copied().unwrap().max(	×
91	mem[x][y]	×
92	+ Diff::new_peek(updates.removals[x], updates.additions[y]).closeness(),	×
93	));	×
94	}	×
95
96	mem.push(row);	×
97	}
98
99	let mut x = updates.removals.len();	×
100	let mut y = updates.additions.len();	×
101
102	while x > 0 \|\| y > 0 {	×
103	if x == 0 {	×
104	self.push_add(updates.additions[y - 1]);	×
105	y -= 1;	×
106	} else if y == 0 {	×
107	self.push_remove(updates.removals[x - 1]);	×
108	x -= 1;	×
109	} else if mem[x][y - 1] == mem[x][y] {	×
110	self.push_add(updates.additions[y - 1]);	×
111	y -= 1;	×
112	} else {	×
113	let diff = Diff::new_peek(updates.removals[x - 1], updates.additions[y - 1]);	×
114	self.0.front_b().insert(0, diff);	×
115		×
116	x -= 1;	×
117	y -= 1;	×
118	}	×
119	}
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>) {	×
131	self.0.front_a().push_add(addition);	×
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>) {	×
136	self.0.front_a().push_remove(removal);	×
137	}	×
138
139	pub(crate) fn closeness(&self) -> usize {	×
140	self.0.values.iter().map(\|(x, _)\| x.len()).sum::<usize>()	×
141	+ self.0.last.as_ref().map(\|x\| x.len()).unwrap_or_default()	×
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>) {	×
146	self.0.front_b().insert(0, value);	×
147	}	×
148
149	fn flatten(&mut self) {	×
150	if let Some(update) = &mut self.0.first {	×
151	update.flatten()	×
152	}	×
153
154	for (_, update) in &mut self.0.values {	×
155	update.flatten()	×
156	}
157	}	×
158	}
159
160	/// Gets the diff of a sequence by using myers' algorithm
161	pub fn diff<'mem, 'facet>(	×
NEW 162	a: Vec<Peek<'mem, 'facet>>,	×
NEW 163	b: Vec<Peek<'mem, 'facet>>,	×
UNCOV 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	//
171	let mut mem = vec![vec![0; a.len() + 1]];	×
172
173	for y in 0..b.len() {	×
174	let mut next = vec![0];	×
175	for x in 0..a.len() {	×
176	let mut v = mem[y][x + 1].min(next[x]) + 1;	×
177	if Diff::new_peek(a[x], b[y]).is_equal() {	×
178	v = v.min(mem[y][x]);	×
179	}	×
180
181	next.push(v);	×
182	}
183
184	mem.push(next);	×
185	}
186
187	let mut updates = Updates::default();	×
188
189	let mut x = a.len();	×
190	let mut y = b.len();	×
191	while x > 0 \|\| y > 0 {	×
192	if y == 0 {	×
193	updates.push_remove(a[x - 1]);	×
194	x -= 1;	×
195	} else if x == 0 {	×
196	updates.push_add(b[y - 1]);	×
197	y -= 1;	×
198	} else if Diff::new_peek(a[x - 1], b[y - 1]).is_equal()	×
199	&& mem[y - 1][x - 1] <= mem[y][x - 1].min(mem[y - 1][x]) + 1	×
200	{	×
201	updates.push_keep(a[x - 1]);	×
202	x -= 1;	×
203	y -= 1;	×
204	} else if mem[y][x - 1] < mem[y - 1][x] {	×
205	updates.push_remove(a[x - 1]);	×
206	x -= 1;	×
207	} else {	×
208	updates.push_add(b[y - 1]);	×
209	y -= 1;	×
210	}	×
211	}
212
213	updates.flatten();	×
214	updates	×
215	}	×

facet-rs / facet / 16482855623

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