Skip to main content

unityrs_export/ngui/
winners.rs

1//! The winners across inputs (`docs/BATCH_SPEC.md` 4.5, steps 1 to 3;
2//! `docs/plans/extract.md` E31, E32, E61): units decided first per unit
3//! key, their keys reserved, then every other key among its plain
4//! candidates. 4.6's prefix conflicts are the engine's phase 6, after this.
5//!
6//! [`decide`] holds every candidate in memory. It is the model, not the
7//! engine's phase 6: that phase decides the same keys by streaming steps
8//! over the committed records, `docs/plans/batch.md` 2.9's external sorts
9//! under the phase budget, and its tests compare their decisions with
10//! [`decide`]'s on the same candidates.
11
12use std::collections::{BTreeMap, BTreeSet};
13
14/// One input's candidate for a key: an output it made.
15#[derive(Clone, Debug, PartialEq, Eq)]
16pub struct Candidate {
17    /// The input's id.
18    pub input: String,
19    /// The output's key.
20    pub key: String,
21    /// Its unit key, or none for a plain candidate.
22    pub unit: Option<String>,
23    /// The output's MD5.
24    pub md5: [u8; 16],
25}
26
27/// A `prefer` entry (1.5): an input, an MD5, or both.
28#[derive(Clone, Debug, Default, PartialEq, Eq)]
29pub struct Prefer {
30    /// The preferred input.
31    pub input: Option<String>,
32    /// The preferred MD5.
33    pub md5: Option<[u8; 16]>,
34}
35
36/// A candidate's rule (7.3's `collisions.rule`).
37#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
38pub enum Rule {
39    /// E31 rule 1.
40    PreferInput,
41    /// E31 rule 2.
42    PreferMd5,
43    /// E31 rule 3.
44    FirstInput,
45    /// A plain candidate for a reserved key.
46    Unit,
47    /// The winning unit step 2 withheld.
48    UnitConflict,
49    /// E61.
50    Withheld,
51}
52
53impl Rule {
54    /// Its name.
55    #[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/// One candidate as decided.
69#[derive(Clone, Debug, PartialEq, Eq)]
70pub struct Decided {
71    /// Its input.
72    pub input: String,
73    /// Its unit key.
74    pub unit: Option<String>,
75    /// Its rule.
76    pub rule: Rule,
77    /// Whether it is the key's row (the winner, or the row of a withheld
78    /// key).
79    pub winner: bool,
80}
81
82/// A key's decision.
83#[derive(Clone, Debug, PartialEq, Eq)]
84pub struct Decision {
85    /// The key.
86    pub key: String,
87    /// Whether it is published.
88    pub publish: bool,
89    /// Why it is withheld: `withheld`, `unit_conflict`, `unit_lost` or
90    /// `publish_incomplete`.
91    pub reason: Option<&'static str>,
92    /// Whether rule 3 decided it among candidates of different MD5s.
93    pub flip: bool,
94    /// The row's input.
95    pub winner: String,
96    /// Every candidate, by bytewise input.
97    pub candidates: Vec<Decided>,
98}
99
100/// E31 among `options` (input, MD5), sorted by input: the chosen index and
101/// its rule. `eligible` says whether rule 1's input has a candidate.
102fn 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
118/// Whether E61 withholds a key: its entry names a failed input.
119fn 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
125/// A unit key's step 1: the winning input, the rule, whether E61 withholds
126/// it, and whether step 2 withheld its winner.
127struct 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/// Decides every key of `candidates` (each input's outputs) under
139/// `prefer`, with `failed` the inputs that failed in the run.
140#[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    // Each unit's keys, by (unit key, input).
155    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    // Step 1.
165    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
225/// Step 2: each key a unit's winner (or, withheld by E61, each of its
226/// inputs) claims goes to the least unit key claiming it; a unit losing a
227/// claim that E61 does not withhold is marked a conflict. The keeper of each
228/// reserved key.
229fn 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
257/// Step 2's row for a key reserved by unit key `u`.
258fn 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
305/// Step 3 for a key no unit reserved.
306fn 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    //! E31's entries the fixture's cases do not reach (review round 1).
367
368    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        // `z` did not fail, so E61 does not withhold the key; it has no
409        // candidate, so rule 1 does not choose; rule 3 does, among
410        // different MD5s.
411        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        // An MD5 no candidate has leaves rule 3.
422        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}