choir_merge/
safety.rs

1//! Merge-safety verdict: did a resolved merge stay inside what the author
2//! proposed? (internal/oak.md item 1.)
3//!
4//! Adapted from Oak's four-tree merge-safety invariant (oak.space, repo
5//! `oak/oak`, `cli/src/commands/merge_safety.rs`, Apache-2.0): *a path the
6//! target changed since fork and the branch never touched must survive the
7//! merge unchanged.* Re-derived for choir's single-file model as a
8//! containment claim: every edit the landing applies to the target must be
9//! an edit the author proposed. Any line the merge removes from the target
10//! beyond what `base -> proposed` removes has been silently reverted; any
11//! line it adds beyond what the author added has been silently injected.
12//!
13//! The comparison is over line *bags* (multisets), not edit scripts, so it
14//! is independent of which minimal diff a strategy's algorithm happens to
15//! produce. The trade-off is positional blindness: a merge that moves a
16//! target line, or applies a proposed edit at the wrong occurrence of a
17//! repeated line, is bag-neutral and passes. That misplacement class is
18//! CI's and review's to catch; this check exists for the reversion class,
19//! which CI misses precisely because reverted code still compiles and its
20//! tests were green before the work it reverts landed (DECISIONS.md D23).
21//!
22//! A violation is not a conflict. A conflict is the pipeline saying "I
23//! cannot resolve this"; a violation is a strategy claiming it resolved
24//! while its output discards work. The distinction matters most for the
25//! non-deterministic strategy slots — mergiraf and the future D19 LLM
26//! resolver — whose failure mode is exactly a confident wrong answer.
27
28use std::collections::BTreeMap;
29
30/// Evidence that a resolved merge edited the target beyond the proposal.
31#[derive(Debug, Clone, PartialEq, Eq)]
32pub struct Violation {
33    /// Lines removed from the target that `base -> proposed` never removed:
34    /// target-side work the merge silently reverted. Sorted, deduplicated.
35    pub reverted: Vec<String>,
36    /// Lines added to the result that `base -> proposed` never added:
37    /// content the merge invented or resurrected. Sorted, deduplicated.
38    pub injected: Vec<String>,
39}
40
41/// Verdict of [`check`] on one resolved merge.
42#[derive(Debug, Clone, PartialEq, Eq)]
43pub enum SafetyVerdict {
44    /// Every edit the merge applied to the target was proposed by the author.
45    Upholds,
46    /// The merge edited the target beyond the proposal; the evidence names
47    /// the unattributable lines.
48    Violation(Violation),
49}
50
51/// Line-occurrence bag of `text`, keyed by line content.
52fn bag(text: &str) -> BTreeMap<&str, usize> {
53    let mut out = BTreeMap::new();
54    for line in text.lines() {
55        *out.entry(line).or_insert(0) += 1;
56    }
57    out
58}
59
60/// Lines of `from` missing from `to` (with excess counts), and vice versa.
61fn bag_delta<'a>(
62    from: &BTreeMap<&'a str, usize>,
63    to: &BTreeMap<&'a str, usize>,
64) -> (BTreeMap<&'a str, usize>, BTreeMap<&'a str, usize>) {
65    let mut removed = BTreeMap::new();
66    let mut added = BTreeMap::new();
67    for (line, n) in from {
68        let have = to.get(line).copied().unwrap_or(0);
69        if *n > have {
70            removed.insert(*line, n - have);
71        }
72    }
73    for (line, n) in to {
74        let have = from.get(line).copied().unwrap_or(0);
75        if *n > have {
76            added.insert(*line, n - have);
77        }
78    }
79    (removed, added)
80}
81
82/// Checks a resolved merge against the safety invariant.
83///
84/// `base` is what the author wrote against, `proposed` is what they wrote,
85/// `target` is the state being merged onto (the speculative train state, or
86/// a ref head), and `result` is the strategy's resolved output. Returns
87/// [`SafetyVerdict::Upholds`] when `target -> result` removes and adds only
88/// lines that `base -> proposed` removes and adds, counted as bags.
89///
90/// An author who *explicitly* proposes reverting target-side content passes
91/// this check: the lines are attributable to their proposal, so nothing is
92/// silent. Refusing deliberate reverts is policy (review, D24), not safety.
93pub fn check(base: &str, target: &str, proposed: &str, result: &str) -> SafetyVerdict {
94    let (landing_removed, landing_added) = bag_delta(&bag(target), &bag(result));
95    let (proposed_removed, proposed_added) = bag_delta(&bag(base), &bag(proposed));
96
97    let excess = |landing: &BTreeMap<&str, usize>, proposal: &BTreeMap<&str, usize>| {
98        landing
99            .iter()
100            .filter(|(line, n)| **n > proposal.get(**line).copied().unwrap_or(0))
101            .map(|(line, _)| line.to_string())
102            .collect::<Vec<String>>()
103    };
104    let reverted = excess(&landing_removed, &proposed_removed);
105    let injected = excess(&landing_added, &proposed_added);
106
107    if reverted.is_empty() && injected.is_empty() {
108        SafetyVerdict::Upholds
109    } else {
110        SafetyVerdict::Violation(Violation { reverted, injected })
111    }
112}
choir_merge/safety.rs

choir_merge/
safety.rs
