geop_core_math/solvers/repeat.rs
1//! Repeating a step until it says it is done: the driver of every loop that
2//! runs until a condition holds — a worklist rewritten until nothing is
3//! left to rewrite (the next split, merge or imprint found and made, until
4//! none is found), a march stepped on until it arrives or leaves, passes
5//! over a list until one changes nothing.
6//!
7//! What a step does, and when the work is done, are the caller's. The
8//! solver promises the bound: at most `most` steps, each taken once and in
9//! order, and an explicit [`Repeated::Exhausted`] when every one of them
10//! was taken and none said it was done. Running out is never read as done:
11//! a caller that can do nothing else with an unfinished run says so with
12//! [`Repeated::done`] or [`Repeated::done_or`].
13//!
14//! [`repeat`] is the driver; [`rewrite`] is its worklist form (find the next
15//! rewrite, make it, search again), and [`resolve`] its form for passes
16//! over a list, which needs no budget: it ends by its own count.
17
18use std::{convert::Infallible, fmt::Display};
19
20use crate::geop_error::{GeopError, GeopResult};
21
22/// What one step said.
23pub enum Step<T> {
24 /// Not done: take another step.
25 Again,
26 /// Done, with this.
27 Done(T),
28}
29
30/// How a run of steps ended.
31#[derive(Clone, Copy, Debug, PartialEq, Eq)]
32#[must_use]
33pub enum Repeated<T> {
34 /// A step said it was done, with `value`, after `steps` steps — that
35 /// one among them.
36 Done { value: T, steps: usize },
37 /// All `steps` steps were taken, and none said it was done: the work
38 /// is unfinished.
39 Exhausted { steps: usize },
40}
41
42impl<T> Repeated<T> {
43 /// What the run was done with, or `exhausted(steps)` for a run that
44 /// was not.
45 pub fn done_or<E>(self, exhausted: impl FnOnce(usize) -> E) -> Result<T, E> {
46 match self {
47 Repeated::Done { value, .. } => Ok(value),
48 Repeated::Exhausted { steps } => Err(exhausted(steps)),
49 }
50 }
51
52 /// What the run was done with, or an error saying that `what` did not
53 /// finish within the steps it was given.
54 pub fn done(self, what: impl Display) -> GeopResult<T> {
55 self.done_or(|steps| GeopError::new(format!("{what} did not finish within {steps} steps")))
56 }
57}
58
59/// Takes `step` until it says [`Step::Done`], at most `most` times.
60/// `step` keeps the state of the work itself, since every step is taken
61/// once, in order.
62pub fn repeat<T, E>(
63 most: usize,
64 mut step: impl FnMut() -> Result<Step<T>, E>,
65) -> Result<Repeated<T>, E> {
66 for steps in 1..=most {
67 if let Step::Done(value) = step()? {
68 return Ok(Repeated::Done { value, steps });
69 }
70 }
71 Ok(Repeated::Exhausted { steps: most })
72}
73
74/// Rewrites `state` until nothing is left to rewrite: `find` looks for the
75/// next rewrite in it, `apply` makes the one found, and the search starts
76/// over from the state that leaves — a rewrite changes what there is to
77/// find. At most `most` searches, the last of which, in a run that is done,
78/// finds nothing; done with how many rewrites were made.
79///
80/// `find` gets the state to read and `apply` to change, so a search can
81/// hold on to borrows of the state that a rewrite could not coexist with.
82pub fn rewrite<St: ?Sized, X, E>(
83 state: &mut St,
84 most: usize,
85 mut find: impl FnMut(&St) -> Result<Option<X>, E>,
86 mut apply: impl FnMut(&mut St, X) -> Result<(), E>,
87) -> Result<Repeated<usize>, E> {
88 let mut made = 0;
89 repeat(most, || match find(state)? {
90 None => Ok(Step::Done(made)),
91 Some(found) => {
92 apply(state, found)?;
93 made += 1;
94 Ok(Step::Again)
95 }
96 })
97}
98
99/// Resolves `items` in passes, each trying every item still unresolved, in
100/// order, until all are or a pass resolves none: what is left then never
101/// will be, and comes back, in order, with what its last try said. A try
102/// may depend on what the tries before it resolved, in this pass or an
103/// earlier one — that is what a later pass is for. Every pass but the last
104/// resolves one item at least, so it ends after as many passes as there
105/// are items, and one more.
106pub fn resolve<I, F>(items: Vec<I>, mut try_one: impl FnMut(&I) -> Result<(), F>) -> Vec<(I, F)> {
107 let mut left = items;
108 let passes = left.len() + 1;
109 let run = repeat::<_, Infallible>(passes, || {
110 let count = left.len();
111 let mut failed = Vec::new();
112 for item in std::mem::take(&mut left) {
113 if let Err(why) = try_one(&item) {
114 failed.push((item, why));
115 }
116 }
117 if failed.len() == count {
118 return Ok(Step::Done(failed));
119 }
120 left = failed.into_iter().map(|(item, _)| item).collect();
121 Ok(Step::Again)
122 });
123 match run {
124 Ok(Repeated::Done { value, .. }) => value,
125 // A pass that resolves nothing ends the run, and there are no more
126 // passes that resolve something than there are items.
127 Ok(Repeated::Exhausted { .. }) => {
128 unreachable!("resolve: every pass but the last resolves an item")
129 }
130 Err(never) => match never {},
131 }
132}
133
134#[cfg(test)]
135mod tests {
136 use super::*;
137
138 /// A step that says it is done ends the run there, with its value and
139 /// how many steps it took.
140 #[test]
141 fn a_run_ends_at_the_step_that_is_done() {
142 let mut n = 0;
143 let run = repeat::<_, ()>(10, || {
144 n += 1;
145 Ok(if n == 4 {
146 Step::Done(n * 10)
147 } else {
148 Step::Again
149 })
150 });
151 assert_eq!(
152 run,
153 Ok(Repeated::Done {
154 value: 40,
155 steps: 4
156 })
157 );
158 }
159
160 /// A run that is never done reports that it ran out — after taking
161 /// exactly `most` steps — and `done_or` turns that into the error.
162 #[test]
163 fn running_out_is_reported() {
164 let mut taken = 0;
165 let run = repeat::<(), ()>(5, || {
166 taken += 1;
167 Ok(Step::Again)
168 })
169 .unwrap();
170 assert_eq!((run, taken), (Repeated::Exhausted { steps: 5 }, 5));
171 assert_eq!(run.done_or(|steps| steps), Err(5));
172 let message = format!("{:?}", run.done("the search").unwrap_err());
173 assert!(
174 message.contains("the search did not finish within 5 steps"),
175 "{message}"
176 );
177 }
178
179 /// An error from a step ends the run with it.
180 #[test]
181 fn an_error_ends_the_run() {
182 let mut taken = 0;
183 let run = repeat::<(), &str>(5, || {
184 taken += 1;
185 if taken == 2 {
186 Err("no")
187 } else {
188 Ok(Step::Again)
189 }
190 });
191 assert_eq!((run, taken), (Err("no"), 2));
192 }
193
194 /// Merging equal neighbours until none are left: each search starts
195 /// over from the state the last merge left, and the run is done once a
196 /// search finds nothing.
197 #[test]
198 fn a_rewrite_runs_until_nothing_is_found() {
199 let mut v = vec![1, 1, 2, 2, 2, 3];
200 let run = rewrite::<_, _, ()>(
201 &mut v,
202 10,
203 |v| Ok(v.windows(2).position(|w| w[0] == w[1])),
204 |v, i| {
205 v.remove(i);
206 Ok(())
207 },
208 );
209 assert_eq!(run, Ok(Repeated::Done { value: 3, steps: 4 }));
210 assert_eq!(v, [1, 2, 3]);
211 }
212
213 /// A rewrite that always finds something more runs out, rather than
214 /// being taken for done.
215 #[test]
216 fn a_rewrite_that_never_settles_runs_out() {
217 let mut v = vec![0];
218 let run = rewrite::<_, _, ()>(
219 &mut v,
220 3,
221 |_| Ok(Some(1)),
222 |v, x| {
223 v.push(x);
224 Ok(())
225 },
226 );
227 assert_eq!(run, Ok(Repeated::Exhausted { steps: 3 }));
228 assert_eq!(v.len(), 4);
229 }
230
231 /// Definitions resolved in passes: one that depends on a later one is
232 /// resolved in a later pass, and ones that depend on each other, or on
233 /// nothing defined, are left with what their last try said.
234 #[test]
235 fn resolving_in_passes_leaves_what_never_resolves() {
236 let defs = [
237 ("a", "b"),
238 ("b", ""),
239 ("c", "a"),
240 ("x", "y"),
241 ("y", "x"),
242 ("z", "q"),
243 ];
244 let mut known: Vec<&str> = Vec::new();
245 let mut tries = 0;
246 let left = resolve(defs.to_vec(), |&(name, needs)| {
247 tries += 1;
248 if needs.is_empty() || known.contains(&needs) {
249 known.push(name);
250 Ok(())
251 } else {
252 Err(format!("{name} needs {needs}"))
253 }
254 });
255 assert_eq!(known, ["b", "a", "c"]);
256 let left: Vec<&str> = left.iter().map(|((n, _), _)| *n).collect();
257 assert_eq!(left, ["x", "y", "z"]);
258 // Pass one tries all six and resolves b; pass two a, then c, which
259 // needs a; pass three resolves nothing.
260 assert_eq!(tries, 6 + 5 + 3);
261 }
262}