dpm_engine/change/
independence.rs

1use crate::gates::{UnmetGate, evaluate};
2use crate::{EngineError, Transition};
3use chrono::{DateTime, Utc};
4use dpm_model::{
5    ActorId, Applicability, Dependency, DependencyId, DependencyKind, DependencyPolicy, Key, Plan,
6    StartBasis, Timeline, WorkItemId, WorkKind,
7};
8use serde::{Deserialize, Serialize};
9use std::collections::BTreeSet;
10use std::fmt;
11
12/// How a reviewed change weakens an edge that touches the applying actor's own work.
13#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
14#[serde(rename_all = "snake_case")]
15pub enum EdgeRelaxation {
16    /// No edge between the same two work items remains, including when an endpoint is deleted.
17    Removed,
18    /// A Hard edge would become Soft, and so waivable.
19    Policy,
20    /// The lag would be lower.
21    Lag,
22    /// The relation would no longer imply the old one (FS implies SS and FF; each implies SF).
23    Kind,
24    /// A verified-finish start basis would accept a pending submission.
25    StartBasis,
26    /// Any other difference; only a strictly tighter or equal edge is accepted.
27    Other,
28}
29
30/// A constraint that a reviewed change would relax for work the applying actor owns.
31#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
32#[serde(tag = "type", rename_all = "snake_case")]
33pub enum RelaxedConstraint {
34    /// An edge into or out of the actor's work would be removed or weakened.
35    Dependency {
36        /// Identity of the current edge.
37        dependency: DependencyId,
38        /// Predecessor key.
39        predecessor: Key,
40        /// Successor key.
41        successor: Key,
42        /// How the edge would be weakened.
43        relaxation: EdgeRelaxation,
44    },
45    /// A gate that is unmet now would no longer hold.
46    Gate {
47        /// Work whose transition the gate governs.
48        work: Key,
49        /// Governed transition.
50        transition: Transition,
51        /// The gate as `explain` reports it before the change.
52        gate: UnmetGate,
53    },
54}
55
56impl fmt::Display for RelaxedConstraint {
57    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
58        match self {
59            Self::Dependency {
60                dependency,
61                predecessor,
62                successor,
63                relaxation,
64            } => write!(
65                f,
66                "dependency {dependency} ({predecessor} -> {successor}): {relaxation:?}"
67            ),
68            Self::Gate {
69                work,
70                transition,
71                gate,
72            } => write!(
73                f,
74                "the {transition} gate of {work}: {}",
75                crate::gates::describe(gate)
76            ),
77        }
78    }
79}
80
81/// Refuse a reviewed change that relaxes a gate on the actor's own work or on the result it
82/// hands on.
83///
84/// The rule is the one waivers follow: an owner certifying that its own work, or the work waiting
85/// for its result, needs less would be judging its own case. Edges are compared structurally, so a
86/// relaxation counts even while the gate is closed for another reason; gates are compared through
87/// the shared evaluator before and after, so relaxations through decisions, conditions or joins
88/// count without being enumerated here.
89pub(crate) fn refuse_own_relaxation(
90    current: &Plan,
91    proposed: &Plan,
92    actor: &ActorId,
93    at: DateTime<Utc>,
94) -> Result<(), EngineError> {
95    let owned: BTreeSet<WorkItemId> = current
96        .work_items
97        .values()
98        .filter(|w| w.held_by(actor))
99        .map(|w| w.id)
100        .collect();
101    if owned.is_empty() {
102        return Ok(());
103    }
104    let downstream = through_milestones(current, &owned, Direction::Downstream);
105    let upstream = through_milestones(current, &owned, Direction::Upstream);
106    let refuse = |work: Key, relaxed| EngineError::OwnGateRelaxed {
107        actor: actor.clone(),
108        work,
109        relaxed: Box::new(relaxed),
110    };
111    for edge in current.dependencies.iter().filter(|e| {
112        owned.contains(&e.predecessor)
113            || owned.contains(&e.successor)
114            || downstream.contains(&e.predecessor)
115            || upstream.contains(&e.successor)
116    }) {
117        if let Some(relaxation) = edge_relaxation(edge, proposed) {
118            let mine =
119                if owned.contains(&edge.predecessor) || downstream.contains(&edge.predecessor) {
120                    edge.predecessor
121                } else {
122                    edge.successor
123                };
124            let relaxed = RelaxedConstraint::Dependency {
125                dependency: edge.id,
126                predecessor: key(current, edge.predecessor),
127                successor: key(current, edge.successor),
128                relaxation,
129            };
130            return Err(refuse(key(current, mine), relaxed));
131        }
132    }
133    // Gates downstream of a forwarding milestone wait on the owned result as if it were direct.
134    let forwarding: BTreeSet<WorkItemId> = owned.union(&downstream).copied().collect();
135    match relaxed_gate(current, proposed, &owned, &forwarding, at) {
136        Some((mine, relaxed)) => Err(refuse(mine, relaxed)),
137        None => Ok(()),
138    }
139}
140
141/// Which way a milestone chain is followed from the owned work.
142#[derive(Clone, Copy)]
143enum Direction {
144    /// Milestones forwarding the owned work's result to later work.
145    Downstream,
146    /// Milestones forwarding earlier results into the owned work.
147    Upstream,
148}
149
150/// Milestones reached from owned work through milestone-only chains in one direction.
151///
152/// A milestone is a zero-duration point that forwards its prerequisites' results, so an edge out of
153/// a downstream milestone carries the owned result on, and an edge into an upstream milestone gates
154/// the owned work, exactly as if the edge touched the owned work directly. Other edges of those
155/// milestones concern other work and stay outside the rule.
156fn through_milestones(
157    plan: &Plan,
158    owned: &BTreeSet<WorkItemId>,
159    direction: Direction,
160) -> BTreeSet<WorkItemId> {
161    let is_milestone = |id: &WorkItemId| {
162        plan.work_items
163            .get(id)
164            .is_some_and(|w| w.kind == WorkKind::Milestone)
165    };
166    let mut reached = BTreeSet::new();
167    let mut frontier: Vec<WorkItemId> = owned.iter().copied().collect();
168    while let Some(node) = frontier.pop() {
169        for edge in &plan.dependencies {
170            let next = match direction {
171                Direction::Downstream if edge.predecessor == node => edge.successor,
172                Direction::Upstream if edge.successor == node => edge.predecessor,
173                _ => continue,
174            };
175            if is_milestone(&next) && reached.insert(next) {
176                frontier.push(next);
177            }
178        }
179    }
180    reached
181}
182
183/// The weakening of `old`, unless the proposal keeps an edge between the same endpoints that is
184/// at least as strict (whatever its identity).
185fn edge_relaxation(old: &Dependency, proposed: &Plan) -> Option<EdgeRelaxation> {
186    let same_pair: Vec<_> = proposed
187        .dependencies
188        .iter()
189        .filter(|e| e.predecessor == old.predecessor && e.successor == old.successor)
190        .collect();
191    let weakenings: Vec<_> = same_pair.iter().map(|e| weakening(old, e)).collect();
192    if weakenings.iter().any(Option::is_none) {
193        return None;
194    }
195    let nearest = same_pair
196        .iter()
197        .position(|e| e.id == old.id)
198        .or((!same_pair.is_empty()).then_some(0));
199    Some(
200        nearest
201            .and_then(|i| weakenings.get(i).copied().flatten())
202            .unwrap_or(EdgeRelaxation::Removed),
203    )
204}
205
206fn weakening(old: &Dependency, new: &Dependency) -> Option<EdgeRelaxation> {
207    if old.policy == DependencyPolicy::Hard && new.policy == DependencyPolicy::Soft {
208        return Some(EdgeRelaxation::Policy);
209    }
210    if new.lag_hours < old.lag_hours {
211        return Some(EdgeRelaxation::Lag);
212    }
213    if !implies(new.kind, old.kind) {
214        return Some(EdgeRelaxation::Kind);
215    }
216    if old.start_basis == StartBasis::Verified && new.start_basis == StartBasis::Provisional {
217        return Some(EdgeRelaxation::StartBasis);
218    }
219    let normalized = Dependency {
220        id: old.id,
221        kind: old.kind,
222        lag_hours: old.lag_hours,
223        policy: old.policy,
224        start_basis: old.start_basis,
225        rationale: old.rationale.clone(),
226        ..new.clone()
227    };
228    (normalized != *old).then_some(EdgeRelaxation::Other)
229}
230
231/// Whether relation `new` with the same lag bounds the successor at least as late as `old`: a
232/// finish follows its start, so FS implies SS and FF, and each of those implies SF.
233fn implies(new: DependencyKind, old: DependencyKind) -> bool {
234    use DependencyKind::{FinishFinish, FinishStart, StartFinish, StartStart};
235    new == old
236        || new == FinishStart
237        || (old == StartFinish && matches!(new, StartStart | FinishFinish))
238}
239
240/// A gate unmet now on owned work, or on a successor because of owned work, that the proposal
241/// releases, with the key of the owned work it concerns.
242fn relaxed_gate(
243    current: &Plan,
244    proposed: &Plan,
245    owned: &BTreeSet<WorkItemId>,
246    forwarding: &BTreeSet<WorkItemId>,
247    at: DateTime<Utc>,
248) -> Option<(Key, RelaxedConstraint)> {
249    let (before, after) = (Timeline::at(current, at), Timeline::at(proposed, at));
250    let forwarding_keys: BTreeSet<Key> = forwarding.iter().map(|id| key(current, *id)).collect();
251    let successors = current
252        .dependencies
253        .iter()
254        .filter(|e| forwarding.contains(&e.predecessor))
255        .map(|e| e.successor);
256    let scope: BTreeSet<_> = forwarding.iter().copied().chain(successors).collect();
257    for id in scope {
258        let (Some(old), Some(new)) = (current.work_items.get(&id), proposed.work_items.get(&id))
259        else {
260            continue;
261        };
262        for transition in Transition::ALL {
263            let was = evaluate(current, old, transition, &before).unmet;
264            let now = evaluate(proposed, new, transition, &after).unmet;
265            for gate in was {
266                let concerns = if owned.contains(&id) {
267                    Some(old.key.clone())
268                } else {
269                    owned_subject(&gate, forwarding, &forwarding_keys)
270                };
271                if let Some(mine) = concerns
272                    && !now.iter().any(|g| same_gate(g, &gate))
273                {
274                    let relaxed = RelaxedConstraint::Gate {
275                        work: old.key.clone(),
276                        transition,
277                        gate,
278                    };
279                    return Some((mine, relaxed));
280                }
281            }
282        }
283    }
284    None
285}
286
287/// The owned predecessor a successor's gate waits on, if any.
288fn owned_subject(
289    gate: &UnmetGate,
290    owned: &BTreeSet<WorkItemId>,
291    owned_keys: &BTreeSet<Key>,
292) -> Option<Key> {
293    match gate {
294        UnmetGate::Dependency {
295            predecessor, key, ..
296        }
297        | UnmetGate::BasisInvalidated {
298            predecessor, key, ..
299        } if owned.contains(predecessor) => Some(Key::new(key.clone())),
300        UnmetGate::Applicability {
301            applicability:
302                Applicability::Stranded { predecessor, .. }
303                | Applicability::AwaitingChoice { predecessor },
304        } if owned_keys.contains(predecessor) => Some(predecessor.clone()),
305        _ => None,
306    }
307}
308
309/// Whether two unmet gates hold the same condition, whatever their current release detail.
310fn same_gate(a: &UnmetGate, b: &UnmetGate) -> bool {
311    match (a, b) {
312        (
313            UnmetGate::Dependency { predecessor: x, .. },
314            UnmetGate::Dependency { predecessor: y, .. },
315        ) => x == y,
316        (
317            UnmetGate::BasisInvalidated { dependency: x, .. },
318            UnmetGate::BasisInvalidated { dependency: y, .. },
319        ) => x == y,
320        (UnmetGate::Decision { key: x }, UnmetGate::Decision { key: y })
321        | (UnmetGate::Choice { key: x, .. }, UnmetGate::Choice { key: y, .. }) => x == y,
322        _ => std::mem::discriminant(a) == std::mem::discriminant(b),
323    }
324}
325
326fn key(plan: &Plan, id: WorkItemId) -> Key {
327    plan.work_items
328        .get(&id)
329        .map_or_else(|| Key::new(id.to_string()), |w| w.key.clone())
330}
331
332#[cfg(test)]
333mod tests;
dpm_engine/change/independence.rs

dpm_engine/change/
independence.rs
