prikk_store/
merge_evidence.rs

1//! Public read-only merge/conflict evidence display boundary (DC-22).
2
3mod display;
4mod merge_plan;
5
6use std::collections::BTreeSet;
7
8use prikk_error::{PrikkError, Result};
9use prikk_object::{BlockKind, BlockPayload, ObjectId, ObjectType, RefStatePayload};
10
11pub use display::{
12    MergeEvidenceDisplay, MergeEvidenceDisplayItem, MergeEvidenceDisplayOperation,
13    MergeEvidenceDisplaySelector,
14};
15pub use merge_plan::MergePlanDisplay;
16
17use crate::lifecycle_cache::replay_derived_state;
18use crate::object_store::{ObjectReadSnapshot, ObjectReader};
19use crate::patch_algebra::{EvidenceScope, StorePatchAlgebraEvidence, analyze_merge_evidence};
20use crate::patch_replay::decode::{DecodedPatchOperation, decode_patch_operations};
21use crate::received::read_received_pointer;
22use crate::refs::RefStore;
23use crate::trust::{MaintainerTrustPolicy, verify_trusted_publication_envelope};
24use crate::{RepositoryLayout, validate_local_branch_ref};
25
26/// Target selector for `prikk merge-evidence`.
27#[derive(Debug, Clone, PartialEq, Eq)]
28pub enum MergeEvidenceTarget {
29    /// Select a sealed target block directly.
30    Block(ObjectId),
31    /// Select the current target block of a local branch ref.
32    Ref(String),
33    /// Select the current target block of a received ref (`remotes/<name>`, DC-85). Never valid as
34    /// a merge's `into_ref` — only as a source.
35    ReceivedRef(String),
36}
37
38/// Prepare a read-only merge evidence display report.
39pub fn prepare_merge_evidence(
40    layout: &RepositoryLayout,
41    baseline_block_id: ObjectId,
42    left_target: MergeEvidenceTarget,
43    right_target: MergeEvidenceTarget,
44) -> Result<MergeEvidenceDisplay> {
45    // RFC 111 §6.1: this function is read-only end to end (it never calls `write_object`; shared as
46    // infrastructure by `execute_merge`, which writes separately, afterward, through its own store --
47    // see `merge_execute.rs`), so it takes one decoded index snapshot here instead of paying a fresh
48    // decode per object read.
49    let object_store = ObjectReadSnapshot::open(layout)?;
50    let baseline_horizon = lineage_horizon(&object_store, baseline_block_id)?;
51    let replay = replay_derived_state(&object_store, baseline_block_id, baseline_horizon)?;
52    let evidence =
53        StorePatchAlgebraEvidence::from_replay_derived(&object_store, baseline_horizon, replay)
54            .map_err(|err| PrikkError::Integrity(format!("merge evidence baseline: {err:?}")))?;
55    let left_selector = resolve_target(layout, &object_store, left_target)?;
56    let right_selector = resolve_target(layout, &object_store, right_target)?;
57    let left_operations = candidate_sequence(
58        &object_store,
59        baseline_block_id,
60        left_selector.target_block_id,
61    )?;
62    let right_operations = candidate_sequence(
63        &object_store,
64        baseline_block_id,
65        right_selector.target_block_id,
66    )?;
67    let report = analyze_merge_evidence(
68        baseline_block_id,
69        Some(baseline_horizon),
70        evidence.baseline_state(),
71        &evidence,
72        EvidenceScope::SealedCandidateRequired,
73        &left_operations,
74        &right_operations,
75    );
76    Ok(MergeEvidenceDisplay::from_report(
77        report,
78        left_selector,
79        right_selector,
80    ))
81}
82
83/// Prepare a read-only merge plan display report.
84pub fn prepare_merge_plan(
85    layout: &RepositoryLayout,
86    baseline_block_id: ObjectId,
87    left_target: MergeEvidenceTarget,
88    right_target: MergeEvidenceTarget,
89) -> Result<MergePlanDisplay> {
90    let evidence = prepare_merge_evidence(layout, baseline_block_id, left_target, right_target)?;
91    Ok(MergePlanDisplay::from_evidence(evidence))
92}
93
94fn resolve_target(
95    layout: &RepositoryLayout,
96    object_store: &impl ObjectReader,
97    target: MergeEvidenceTarget,
98) -> Result<MergeEvidenceDisplaySelector> {
99    match target {
100        MergeEvidenceTarget::Block(block_id) => {
101            read_block(object_store, block_id)?;
102            Ok(MergeEvidenceDisplaySelector {
103                selector: format!("block {block_id}"),
104                target_block_id: block_id,
105            })
106        }
107        MergeEvidenceTarget::Ref(ref_name) => {
108            let ref_name = validate_local_branch_ref(&ref_name)?;
109            let ref_store = RefStore::new(layout.clone());
110            let ref_state_id = ref_store
111                .read_current_ref_state_id(&ref_name)?
112                .ok_or_else(|| PrikkError::Integrity(format!("ref {ref_name} is not published")))?;
113            let envelope = object_store
114                .read_typed(ref_state_id, ObjectType::RefState)?
115                .ok_or_else(|| {
116                    PrikkError::Integrity(format!("ref {ref_name} points to missing RefState"))
117                })?;
118            let ref_state = RefStatePayload::decode_canonical(
119                &envelope.canonical_payload,
120                envelope.schema_version,
121            )?;
122            if ref_state.ref_name != ref_name {
123                return Err(PrikkError::Integrity(format!(
124                    "RefState name mismatch: expected {ref_name}, got {}",
125                    ref_state.ref_name
126                )));
127            }
128            read_block(object_store, ref_state.target_object_id)?;
129            Ok(MergeEvidenceDisplaySelector {
130                selector: format!("ref {ref_name}"),
131                target_block_id: ref_state.target_object_id,
132            })
133        }
134        MergeEvidenceTarget::ReceivedRef(ref_name) => {
135            let pointer = read_received_pointer(layout, &ref_name)?.ok_or_else(|| {
136                PrikkError::Integrity(format!("received ref {ref_name} does not exist"))
137            })?;
138            let envelope = object_store
139                .read_typed(pointer.ref_state_id, ObjectType::RefState)?
140                .ok_or_else(|| {
141                    PrikkError::Integrity(format!(
142                        "received ref {ref_name} points to missing RefState"
143                    ))
144                })?;
145            let ref_state = RefStatePayload::decode_canonical(
146                &envelope.canonical_payload,
147                envelope.schema_version,
148            )?;
149            // Deliberately no name-equality check here (unlike the local-ref arm above): a received
150            // RefState's embedded `ref_name` is the *origin's* own name (e.g. "heads/main"), never
151            // the local "remotes/..." label — DC-85 §3A carries this asymmetry forward from DC-78's
152            // received-ref design, where it's why received refs cannot reuse `refs/by-id/`'s pointer
153            // format at all.
154            read_block(object_store, ref_state.target_object_id)?;
155            Ok(MergeEvidenceDisplaySelector {
156                selector: format!("received ref {ref_name}"),
157                target_block_id: ref_state.target_object_id,
158            })
159        }
160    }
161}
162
163fn lineage_horizon(object_store: &impl ObjectReader, baseline: ObjectId) -> Result<ObjectId> {
164    let mut visited = BTreeSet::new();
165    let mut current = baseline;
166    loop {
167        if !visited.insert(current) {
168            return Err(PrikkError::Integrity(format!(
169                "block parent chain contains a cycle at {current}"
170            )));
171        }
172        let block = read_block(object_store, current)?;
173        // State derivation, same category as `block_state.rs`'s replay walk (DC-75): a `Merge`
174        // block's own state is replayed from its mainline parent only, never its secondary.
175        match mainline_or_sole_parent(&block) {
176            Some(None) => return Ok(current),
177            Some(Some(parent)) => current = parent,
178            None => {
179                return Err(PrikkError::UnsupportedObjectType(format!(
180                    "merge evidence requires a single-parent baseline lineage; block {current} has {} parents",
181                    block.parent_block_ids.len()
182                )));
183            }
184        }
185    }
186}
187
188/// The parent state derivation continues through: mainline only for a `Merge` block (DC-75), the
189/// sole parent for `Normal`, none for `Root`. `Some(None)` is genesis, not an error; `None` is a
190/// shape this walk cannot follow — a non-`Merge` block with more than one parent, or a `Merge`
191/// block with no valid mainline parent.
192fn mainline_or_sole_parent(block: &BlockPayload) -> Option<Option<ObjectId>> {
193    if block.kind == BlockKind::Merge {
194        let mainline = block.mainline_parent_id?;
195        if !block.parent_block_ids.contains(&mainline) {
196            return None;
197        }
198        return Some(Some(mainline));
199    }
200    match block.parent_block_ids.as_slice() {
201        [] => Some(None),
202        [parent] => Some(Some(*parent)),
203        _ => None,
204    }
205}
206
207/// Full-DAG ancestor closure of `start` (inclusive), following **all** parents — the reachability
208/// primitive (DC-75), distinct from state derivation's mainline-only walk. A cycle (cryptographically
209/// impossible in honestly-generated data, since parent references are content hashes computed before
210/// the referencing block exists) is not distinguished from a legitimate diamond re-visit here: this
211/// closure is a set, used only for reachability/exclusion, never to decide state, so under-detecting a
212/// cycle can at worst leave a set slightly incomplete — it cannot make an unsound merge succeed. The
213/// state-derivation walks (`block_state.rs`, `lineage_horizon` above) retain explicit cycle errors,
214/// since those sit on the actual trust boundary.
215pub(crate) fn ancestors_inclusive(
216    object_store: &impl ObjectReader,
217    start: ObjectId,
218) -> Result<std::collections::BTreeMap<ObjectId, BlockPayload>> {
219    let mut ancestors = std::collections::BTreeMap::new();
220    let mut stack = vec![start];
221    while let Some(current) = stack.pop() {
222        if ancestors.contains_key(&current) {
223            continue;
224        }
225        let block = read_block(object_store, current)?;
226        crate::validate_block_v2_shape(&block)?;
227        stack.extend(block.parent_block_ids.iter().copied());
228        ancestors.insert(current, block);
229    }
230    Ok(ancestors)
231}
232
233/// Topologically order `new_ids` (parents before children), restricted to edges within `new_ids`
234/// itself — a parent outside the set is, by construction, already satisfied (it is an ancestor of
235/// `baseline`). Kahn's algorithm, O(V+E): for the overwhelmingly common case (a simple single-parent
236/// chain since baseline, no repeated merge involved) this is linear, same cost as the walk it
237/// replaces — verified in `baseline-recording-answer-v1.md` §1.
238fn topological_order(
239    new_ids: &BTreeSet<ObjectId>,
240    ancestors: &std::collections::BTreeMap<ObjectId, BlockPayload>,
241) -> Result<Vec<ObjectId>> {
242    let mut remaining_parents = std::collections::BTreeMap::new();
243    let mut children: std::collections::BTreeMap<ObjectId, Vec<ObjectId>> =
244        std::collections::BTreeMap::new();
245    for id in new_ids {
246        let Some(block) = ancestors.get(id) else {
247            return Err(PrikkError::Integrity(format!(
248                "candidate block set references untracked block {id}"
249            )));
250        };
251        let count = block
252            .parent_block_ids
253            .iter()
254            .filter(|parent| new_ids.contains(parent))
255            .count();
256        remaining_parents.insert(*id, count);
257        for parent in &block.parent_block_ids {
258            if new_ids.contains(parent) {
259                children.entry(*parent).or_default().push(*id);
260            }
261        }
262    }
263    let mut ready: Vec<ObjectId> = remaining_parents
264        .iter()
265        .filter(|(_, count)| **count == 0)
266        .map(|(id, _)| *id)
267        .collect();
268    ready.sort();
269    let mut queue: std::collections::VecDeque<ObjectId> = ready.into();
270    let mut order = Vec::with_capacity(new_ids.len());
271    while let Some(id) = queue.pop_front() {
272        order.push(id);
273        for child in children.get(&id).into_iter().flatten() {
274            let Some(entry) = remaining_parents.get_mut(child) else {
275                return Err(PrikkError::Integrity(
276                    "candidate block set topological sort lost a tracked child".to_string(),
277                ));
278            };
279            *entry -= 1;
280            if *entry == 0 {
281                queue.push_back(*child);
282            }
283        }
284    }
285    if order.len() != new_ids.len() {
286        return Err(PrikkError::Integrity(
287            "candidate block set contains a cycle".to_string(),
288        ));
289    }
290    Ok(order)
291}
292
293/// Blocks strictly between `baseline` (exclusive) and `target` (inclusive), oldest first, paired with
294/// their own object ids — the ancestor-closure difference `ancestors(target) \ ancestors(baseline)`,
295/// following **all** parents (DC-75; previously a single-parent-only walk, replaced because a `Merge`
296/// block's secondary parent can be the true, and only, path back to a repeated merge's baseline).
297/// Shared by `candidate_sequence` (decoded operations, for evidence), `candidate_patch_ids` (patch
298/// identity, for merge execution's adoption set — DC-74), and `verify_candidate_blocks_trusted` (DC-85
299/// — the same candidate set, not a second walk of the ancestor graph) so the walk is defined exactly
300/// once.
301fn candidate_blocks(
302    object_store: &impl ObjectReader,
303    baseline: ObjectId,
304    target: ObjectId,
305) -> Result<Vec<(ObjectId, BlockPayload)>> {
306    let target_ancestors = ancestors_inclusive(object_store, target)?;
307    if !target_ancestors.contains_key(&baseline) {
308        return Err(PrikkError::Integrity(format!(
309            "baseline Block {baseline} is not an ancestor of target Block {target}"
310        )));
311    }
312    let baseline_ancestors = ancestors_inclusive(object_store, baseline)?;
313    let new_ids: BTreeSet<ObjectId> = target_ancestors
314        .keys()
315        .filter(|id| !baseline_ancestors.contains_key(id))
316        .copied()
317        .collect();
318    topological_order(&new_ids, &target_ancestors)?
319        .into_iter()
320        .map(|id| {
321            let payload = target_ancestors.get(&id).cloned().ok_or_else(|| {
322                PrikkError::Integrity(format!("missing Block {id} in candidate set"))
323            })?;
324            Ok((id, payload))
325        })
326        .collect()
327}
328
329/// Patch ids already reachable from `baseline` via **any** parent path (DC-75 addendum-5): the set a
330/// side's candidate patches must exclude. A patch appearing here is either literally the baseline's
331/// own content or was already adopted into it by an earlier merge — replaying it again is not new
332/// content, and feeding it to confluence analysis breaks the proof rather than refusing cleanly
333/// (`reachability-vs-state-derivation-answer-v1.md` §2: `PairReplayFailed`, not a conflict).
334fn baseline_reachable_patch_ids(
335    object_store: &impl ObjectReader,
336    baseline: ObjectId,
337) -> Result<BTreeSet<ObjectId>> {
338    let ancestors = ancestors_inclusive(object_store, baseline)?;
339    Ok(ancestors
340        .values()
341        .flat_map(|block| block.patch_ids.iter().copied())
342        .collect())
343}
344
345fn candidate_sequence(
346    object_store: &impl ObjectReader,
347    baseline: ObjectId,
348    target: ObjectId,
349) -> Result<Vec<DecodedPatchOperation>> {
350    let excluded = baseline_reachable_patch_ids(object_store, baseline)?;
351    let mut operations = Vec::new();
352    for (_, block) in candidate_blocks(object_store, baseline, target)? {
353        for patch_id in block.patch_ids {
354            if excluded.contains(&patch_id) {
355                continue;
356            }
357            let envelope = object_store
358                .read_typed(patch_id, ObjectType::Patch)?
359                .ok_or_else(|| PrikkError::Integrity(format!("missing Patch {patch_id}")))?;
360            operations.extend(decode_patch_operations(
361                &envelope.canonical_payload,
362                envelope.schema_version,
363            )?);
364        }
365    }
366    Ok(operations)
367}
368
369/// Patch identities strictly between `baseline` (exclusive) and `target` (inclusive), in the order
370/// they were sealed — the set merge execution adopts verbatim onto the other side (DC-74). Excludes
371/// any patch already reachable from `baseline` (DC-75 addendum-5) — see `baseline_reachable_patch_ids`.
372pub(crate) fn candidate_patch_ids(
373    object_store: &impl ObjectReader,
374    baseline: ObjectId,
375    target: ObjectId,
376) -> Result<Vec<ObjectId>> {
377    let excluded = baseline_reachable_patch_ids(object_store, baseline)?;
378    Ok(candidate_blocks(object_store, baseline, target)?
379        .into_iter()
380        .flat_map(|(_, block)| block.patch_ids)
381        .filter(|patch_id| !excluded.contains(patch_id))
382        .collect())
383}
384
385/// DC-85 §3A.1's mandatory acceptance criterion: every candidate block a merge would adopt must carry
386/// a currently-trusted MAINTAINER signature, checked here — over the exact same candidate set
387/// `candidate_patch_ids` computes (`candidate_blocks`, not a second walk of the ancestor graph), and
388/// using the same trust machinery `verify` uses (`verify_trusted_publication_envelope`), not a new
389/// check invented for this path.
390///
391/// Required specifically because a received ref's blocks arrive via `import_bundle`, which performs
392/// no trust check at all (DC-78 Stage 3 §4, deliberate — "no automatic trust adoption on import").
393/// A local-to-local merge's adopted blocks are safe by induction: every block reachable from a local
394/// ref was itself created through this repository's own seal/merge path, each gated by
395/// `verify_signer_trusted` at creation. That induction does not hold for imported content, which was
396/// never gated on entry — so it must be gated here, before `into_ref` advances, not deferred to a
397/// later `verify` run.
398pub(crate) fn verify_candidate_blocks_trusted(
399    object_store: &impl ObjectReader,
400    policy: &MaintainerTrustPolicy,
401    baseline: ObjectId,
402    target: ObjectId,
403) -> Result<()> {
404    for (block_id, _) in candidate_blocks(object_store, baseline, target)? {
405        let envelope = object_store
406            .read_typed(block_id, ObjectType::Block)?
407            .ok_or_else(|| PrikkError::Integrity(format!("missing Block {block_id}")))?;
408        verify_trusted_publication_envelope(policy, &envelope).map_err(|issue| {
409            PrikkError::InvalidSignature(format!(
410                "adopted Block {block_id} has no trusted MAINTAINER signature ({}: {})",
411                issue.code, issue.message
412            ))
413        })?;
414    }
415    Ok(())
416}
417
418fn read_block(object_store: &impl ObjectReader, block_id: ObjectId) -> Result<BlockPayload> {
419    let envelope = object_store
420        .read_typed(block_id, ObjectType::Block)?
421        .ok_or_else(|| PrikkError::Integrity(format!("missing Block {block_id}")))?;
422    BlockPayload::decode_canonical(&envelope.canonical_payload)
423}
424
425#[cfg(test)]
426mod tests;
prikk_store/merge_evidence.rs

prikk_store/
merge_evidence.rs
