1use std::collections::{BTreeMap, BTreeSet};
13
14#[derive(Clone, Debug, PartialEq, Eq)]
16pub struct Candidate {
17 pub input: String,
19 pub key: String,
21 pub unit: Option<String>,
23 pub md5: [u8; 16],
25}
26
27#[derive(Clone, Debug, Default, PartialEq, Eq)]
29pub struct Prefer {
30 pub input: Option<String>,
32 pub md5: Option<[u8; 16]>,
34}
35
36#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
38pub enum Rule {
39 PreferInput,
41 PreferMd5,
43 FirstInput,
45 Unit,
47 UnitConflict,
49 Withheld,
51}
52
53impl Rule {
54 #[must_use]
56 pub fn name(self) -> &'static str {
57 match self {
58 Self::PreferInput => "prefer_input",
59 Self::PreferMd5 => "prefer_md5",
60 Self::FirstInput => "first_input",
61 Self::Unit => "unit",
62 Self::UnitConflict => "unit_conflict",
63 Self::Withheld => "withheld",
64 }
65 }
66}
67
68#[derive(Clone, Debug, PartialEq, Eq)]
70pub struct Decided {
71 pub input: String,
73 pub unit: Option<String>,
75 pub rule: Rule,
77 pub winner: bool,
80}
81
82#[derive(Clone, Debug, PartialEq, Eq)]
84pub struct Decision {
85 pub key: String,
87 pub publish: bool,
89 pub reason: Option<&'static str>,
92 pub flip: bool,
94 pub winner: String,
96 pub candidates: Vec<Decided>,
98}
99
100fn e31(options: &[(&str, [u8; 16])], prefer: Option<&Prefer>) -> (usize, Rule) {
103 if let Some(p) = prefer {
104 if let Some(want) = &p.input
105 && let Some(i) = options.iter().position(|(input, _)| input == want)
106 {
107 return (i, Rule::PreferInput);
108 }
109 if let Some(md5) = &p.md5
110 && let Some(i) = options.iter().position(|(_, m)| m == md5)
111 {
112 return (i, Rule::PreferMd5);
113 }
114 }
115 (0, Rule::FirstInput)
116}
117
118fn e61(prefer: Option<&Prefer>, failed: &BTreeSet<String>) -> bool {
120 prefer
121 .and_then(|p| p.input.as_ref())
122 .is_some_and(|i| failed.contains(i))
123}
124
125struct UnitKey {
128 winner: String,
129 rule: Rule,
130 e61: bool,
131 conflict: bool,
132}
133
134fn all_same(md5s: &[[u8; 16]]) -> bool {
135 md5s.windows(2).all(|w| w.first() == w.get(1))
136}
137
138#[must_use]
141pub fn decide(
142 candidates: &[Candidate],
143 prefer: &BTreeMap<String, Prefer>,
144 failed: &BTreeSet<String>,
145 publish_incomplete: bool,
146) -> Vec<Decision> {
147 let mut by_key: BTreeMap<&str, Vec<&Candidate>> = BTreeMap::new();
148 for c in candidates {
149 by_key.entry(c.key.as_str()).or_default().push(c);
150 }
151 for list in by_key.values_mut() {
152 list.sort_by(|a, b| a.input.as_bytes().cmp(b.input.as_bytes()));
153 }
154 let mut units: BTreeMap<(&str, &str), BTreeSet<&str>> = BTreeMap::new();
156 for c in candidates {
157 if let Some(u) = &c.unit {
158 units
159 .entry((u.as_str(), c.input.as_str()))
160 .or_default()
161 .insert(c.key.as_str());
162 }
163 }
164 let mut decided: BTreeMap<&str, UnitKey> = BTreeMap::new();
166 let unit_keys: BTreeSet<&str> = units.keys().map(|(u, _)| *u).collect();
167 for &u in &unit_keys {
168 let options: Vec<(&str, [u8; 16])> = by_key
169 .get(u)
170 .map(|list| {
171 list.iter()
172 .filter(|c| c.unit.as_deref() == Some(u))
173 .map(|c| (c.input.as_str(), c.md5))
174 .collect()
175 })
176 .unwrap_or_default();
177 let p = prefer.get(u);
178 let (i, rule) = e31(&options, p);
179 let winner = options
180 .get(i)
181 .map(|(input, _)| (*input).to_owned())
182 .unwrap_or_default();
183 decided.insert(
184 u,
185 UnitKey {
186 winner,
187 rule,
188 e61: e61(p, failed),
189 conflict: false,
190 },
191 );
192 }
193 let keeper = reserve(&mut decided, &units);
194 let unit_rule = |c: &Candidate| -> Rule {
195 let Some(u) = c.unit.as_deref() else {
196 return Rule::Unit;
197 };
198 match decided.get(u) {
199 Some(d) if d.e61 => Rule::Withheld,
200 Some(d) if d.conflict && c.input == d.winner => Rule::UnitConflict,
201 Some(d) => d.rule,
202 None => Rule::FirstInput,
203 }
204 };
205 let mut out = Vec::new();
206 for (&key, list) in &by_key {
207 let decision = if let Some(&u) = keeper.get(key) {
208 reserved(key, list, u, &decided, &unit_rule)
209 } else {
210 plain(key, list, prefer.get(key), failed, &unit_rule)
211 };
212 out.push(decision);
213 }
214 if !publish_incomplete && !failed.is_empty() {
215 for d in &mut out {
216 if d.publish {
217 d.publish = false;
218 d.reason = Some("publish_incomplete");
219 }
220 }
221 }
222 out
223}
224
225fn reserve<'a>(
230 decided: &mut BTreeMap<&'a str, UnitKey>,
231 units: &BTreeMap<(&'a str, &'a str), BTreeSet<&'a str>>,
232) -> BTreeMap<&'a str, &'a str> {
233 let claims = |u: &str, d: &UnitKey| {
234 units
235 .iter()
236 .filter(move |((uk, input), _)| *uk == u && (d.e61 || *input == d.winner))
237 .flat_map(|(_, keys)| keys.iter().copied())
238 .collect::<Vec<&'a str>>()
239 };
240 let mut keeper: BTreeMap<&'a str, &'a str> = BTreeMap::new();
241 for (&u, d) in decided.iter() {
242 for k in claims(u, d) {
243 let held = keeper.entry(k).or_insert(u);
244 if u.as_bytes() < held.as_bytes() {
245 *held = u;
246 }
247 }
248 }
249 for (&u, d) in decided.iter_mut() {
250 if !d.e61 && claims(u, d).iter().any(|k| keeper.get(k) != Some(&u)) {
251 d.conflict = true;
252 }
253 }
254 keeper
255}
256
257fn reserved(
259 key: &str,
260 list: &[&Candidate],
261 u: &str,
262 decided: &BTreeMap<&str, UnitKey>,
263 unit_rule: &dyn Fn(&Candidate) -> Rule,
264) -> Decision {
265 let Some(d) = decided.get(u) else {
266 return plain(key, list, None, &BTreeSet::new(), unit_rule);
267 };
268 let of_u: Vec<&&Candidate> = list
269 .iter()
270 .filter(|c| c.unit.as_deref() == Some(u))
271 .collect();
272 let row = of_u
273 .iter()
274 .find(|c| c.input == d.winner)
275 .or_else(|| of_u.first())
276 .map(|c| c.input.clone())
277 .unwrap_or_default();
278 let md5s: Vec<[u8; 16]> = of_u.iter().map(|c| c.md5).collect();
279 let flip = d.rule == Rule::FirstInput && !all_same(&md5s);
280 let (publish, reason) = if d.e61 {
281 (false, Some("withheld"))
282 } else if d.conflict {
283 (false, Some("unit_conflict"))
284 } else {
285 (true, None)
286 };
287 Decision {
288 key: key.to_owned(),
289 publish,
290 reason,
291 flip,
292 candidates: list
293 .iter()
294 .map(|c| Decided {
295 input: c.input.clone(),
296 unit: c.unit.clone(),
297 rule: unit_rule(c),
298 winner: c.input == row && c.unit.as_deref() == Some(u),
299 })
300 .collect(),
301 winner: row,
302 }
303}
304
305fn plain(
307 key: &str,
308 list: &[&Candidate],
309 prefer: Option<&Prefer>,
310 failed: &BTreeSet<String>,
311 unit_rule: &dyn Fn(&Candidate) -> Rule,
312) -> Decision {
313 let plains: Vec<&&Candidate> = list.iter().filter(|c| c.unit.is_none()).collect();
314 if plains.is_empty() {
315 let row = list.first().map(|c| c.input.clone()).unwrap_or_default();
316 return Decision {
317 key: key.to_owned(),
318 publish: false,
319 reason: Some("unit_lost"),
320 flip: false,
321 candidates: list
322 .iter()
323 .map(|c| Decided {
324 input: c.input.clone(),
325 unit: c.unit.clone(),
326 rule: unit_rule(c),
327 winner: c.input == row,
328 })
329 .collect(),
330 winner: row,
331 };
332 }
333 let options: Vec<(&str, [u8; 16])> = plains.iter().map(|c| (c.input.as_str(), c.md5)).collect();
334 let (i, rule) = e31(&options, prefer);
335 let withheld = e61(prefer, failed);
336 let row = options
337 .get(i)
338 .map(|(input, _)| (*input).to_owned())
339 .unwrap_or_default();
340 let md5s: Vec<[u8; 16]> = options.iter().map(|(_, m)| *m).collect();
341 let plain_rule = if withheld { Rule::Withheld } else { rule };
342 Decision {
343 key: key.to_owned(),
344 publish: !withheld,
345 reason: withheld.then_some("withheld"),
346 flip: rule == Rule::FirstInput && !all_same(&md5s),
347 candidates: list
348 .iter()
349 .map(|c| Decided {
350 input: c.input.clone(),
351 unit: c.unit.clone(),
352 rule: if c.unit.is_none() {
353 plain_rule
354 } else {
355 unit_rule(c)
356 },
357 winner: c.unit.is_none() && c.input == row,
358 })
359 .collect(),
360 winner: row,
361 }
362}
363
364#[cfg(test)]
365mod tests {
366 use std::collections::{BTreeMap, BTreeSet};
369
370 use super::{Candidate, Prefer, Rule, decide};
371
372 fn plain(input: &str, md5: u8) -> Candidate {
373 Candidate {
374 input: input.to_owned(),
375 key: "k.png".to_owned(),
376 unit: None,
377 md5: [md5; 16],
378 }
379 }
380
381 fn one(prefer: Prefer, failed: &[&str]) -> (String, Rule, bool, bool) {
382 let candidates = [plain("a", 1), plain("b", 2)];
383 let prefer = BTreeMap::from([("k.png".to_owned(), prefer)]);
384 let failed: BTreeSet<String> = failed.iter().map(|f| (*f).to_owned()).collect();
385 let d = decide(&candidates, &prefer, &failed, true);
386 let [k] = d.as_slice() else {
387 panic!("one key");
388 };
389 let rule = k.candidates.iter().find(|c| c.winner).unwrap().rule;
390 (k.winner.clone(), rule, k.publish, k.flip)
391 }
392
393 #[test]
394 fn an_entrys_input_with_no_candidate_leaves_its_md5_to_decide() {
395 let p = Prefer {
396 input: Some("z".to_owned()),
397 md5: Some([2; 16]),
398 };
399 assert_eq!(one(p, &[]), ("b".to_owned(), Rule::PreferMd5, true, false));
400 }
401
402 #[test]
403 fn an_entry_naming_an_input_that_ran_and_made_nothing_is_rule_three() {
404 let p = Prefer {
405 input: Some("z".to_owned()),
406 md5: None,
407 };
408 assert_eq!(one(p, &[]), ("a".to_owned(), Rule::FirstInput, true, true));
412 }
413
414 #[test]
415 fn rule_two_decides_a_plain_key() {
416 let p = Prefer {
417 input: None,
418 md5: Some([2; 16]),
419 };
420 assert_eq!(one(p, &[]), ("b".to_owned(), Rule::PreferMd5, true, false));
421 let p = Prefer {
423 input: None,
424 md5: Some([9; 16]),
425 };
426 assert_eq!(one(p, &[]), ("a".to_owned(), Rule::FirstInput, true, true));
427 }
428
429 #[test]
430 fn an_entry_naming_a_failed_input_withholds_its_key() {
431 let p = Prefer {
432 input: Some("z".to_owned()),
433 md5: Some([2; 16]),
434 };
435 let (_, rule, publish, _) = one(p, &["z"]);
436 assert_eq!((rule, publish), (Rule::Withheld, false));
437 }
438}