sim_incremental_core/projection/
graph.rs

1use std::{
2    collections::{BTreeMap, BTreeSet},
3    error::Error,
4    fmt,
5};
6
7use super::{ConclusionId, Explanation, FactId};
8
9/// One owner's canonical conclusion-to-fact dependency graph.
10#[derive(Clone, Debug, Eq, PartialEq)]
11pub struct OwnerProjectionGraph {
12    owner: String,
13    dependencies: BTreeMap<ConclusionId, BTreeSet<FactId>>,
14}
15
16impl OwnerProjectionGraph {
17    /// Constructs a local owner graph and rejects an empty owner or conclusion.
18    pub fn new(
19        owner: impl Into<String>,
20        dependencies: impl IntoIterator<Item = (ConclusionId, BTreeSet<FactId>)>,
21    ) -> Result<Self, ClosureError> {
22        let owner = owner.into();
23        if owner.trim().is_empty() {
24            return Err(ClosureError::EmptyOwner);
25        }
26        let mut canonical = BTreeMap::new();
27        for (conclusion, facts) in dependencies {
28            if facts.is_empty() {
29                return Err(ClosureError::ConclusionWithoutFacts(conclusion));
30            }
31            if canonical.insert(conclusion.clone(), facts).is_some() {
32                return Err(ClosureError::DuplicateConclusion(conclusion));
33            }
34        }
35        if canonical.is_empty() {
36            return Err(ClosureError::EmptyOwnerGraph(owner));
37        }
38        Ok(Self {
39            owner,
40            dependencies: canonical,
41        })
42    }
43
44    /// Returns the owner identity.
45    #[must_use]
46    pub fn owner(&self) -> &str {
47        &self.owner
48    }
49}
50
51/// Sealed union of local owner graphs with a canonical reverse dependency map.
52#[derive(Clone, Debug, Eq, PartialEq)]
53pub struct FederatedClosure {
54    owners: BTreeMap<ConclusionId, String>,
55    dependencies: BTreeMap<ConclusionId, BTreeSet<FactId>>,
56    consumers: BTreeMap<FactId, BTreeSet<ConclusionId>>,
57}
58
59impl FederatedClosure {
60    /// Joins owner-local graphs and refuses unknown facts or duplicate ownership.
61    pub fn seal(
62        facts: impl IntoIterator<Item = FactId>,
63        graphs: impl IntoIterator<Item = OwnerProjectionGraph>,
64    ) -> Result<Self, ClosureError> {
65        let facts = facts.into_iter().collect::<BTreeSet<_>>();
66        let mut owners = BTreeMap::new();
67        let mut dependencies = BTreeMap::new();
68        let mut consumers = facts
69            .iter()
70            .cloned()
71            .map(|fact| (fact, BTreeSet::new()))
72            .collect::<BTreeMap<_, _>>();
73        for graph in graphs {
74            for (conclusion, required) in graph.dependencies {
75                if let Some(first) = owners.insert(conclusion.clone(), graph.owner.clone()) {
76                    return Err(ClosureError::DuplicateOwner {
77                        conclusion,
78                        first,
79                        second: graph.owner,
80                    });
81                }
82                for fact in &required {
83                    let Some(fact_consumers) = consumers.get_mut(fact) else {
84                        return Err(ClosureError::UnknownFact {
85                            conclusion,
86                            fact: fact.clone(),
87                        });
88                    };
89                    fact_consumers.insert(conclusion.clone());
90                }
91                dependencies.insert(conclusion, required);
92            }
93        }
94        if dependencies.is_empty() {
95            return Err(ClosureError::EmptyClosure);
96        }
97        Ok(Self {
98            owners,
99            dependencies,
100            consumers,
101        })
102    }
103
104    /// Computes the exact conclusion closure affected by changed facts.
105    #[must_use]
106    pub fn affected(&self, changed: impl IntoIterator<Item = FactId>) -> Vec<ConclusionId> {
107        changed
108            .into_iter()
109            .filter_map(|fact| self.consumers.get(&fact))
110            .flatten()
111            .cloned()
112            .collect::<BTreeSet<_>>()
113            .into_iter()
114            .collect()
115    }
116
117    /// Iterates over every declared conclusion in canonical order.
118    pub fn conclusions(&self) -> impl ExactSizeIterator<Item = &ConclusionId> {
119        self.dependencies.keys()
120    }
121
122    /// Returns whether one exact conclusion-to-fact dependency is declared.
123    #[must_use]
124    pub fn depends_on(&self, conclusion: &ConclusionId, fact: &FactId) -> bool {
125        self.dependencies
126            .get(conclusion)
127            .is_some_and(|facts| facts.contains(fact))
128    }
129
130    /// Returns whether a fact belongs to the sealed semantic universe.
131    #[must_use]
132    pub fn contains_fact(&self, fact: &FactId) -> bool {
133        self.consumers.contains_key(fact)
134    }
135
136    /// Explains one exact conclusion-to-fact dependency.
137    pub fn explain(
138        &self,
139        conclusion: &ConclusionId,
140        fact: &FactId,
141    ) -> Result<Explanation, ClosureError> {
142        let Some(required) = self.dependencies.get(conclusion) else {
143            return Err(ClosureError::UnknownConclusion(conclusion.clone()));
144        };
145        if !required.contains(fact) {
146            return Err(ClosureError::Unrelated {
147                conclusion: conclusion.clone(),
148                fact: fact.clone(),
149            });
150        }
151        Ok(Explanation {
152            conclusion: conclusion.clone(),
153            fact: fact.clone(),
154            path: vec![
155                format!("owner/{}", self.owners[conclusion]),
156                format!("conclusion/{conclusion}"),
157                format!("fact/{fact}"),
158            ],
159        })
160    }
161}
162
163/// Fail-closed federated-closure construction or explanation error.
164#[derive(Clone, Debug, Eq, PartialEq)]
165pub enum ClosureError {
166    /// Owner identity is empty.
167    EmptyOwner,
168    /// Owner graph has no conclusions.
169    EmptyOwnerGraph(String),
170    /// A conclusion has no semantic dependency.
171    ConclusionWithoutFacts(ConclusionId),
172    /// One owner declared a conclusion twice.
173    DuplicateConclusion(ConclusionId),
174    /// Two owners claimed one conclusion.
175    DuplicateOwner {
176        /// Conflicting conclusion.
177        conclusion: ConclusionId,
178        /// First owner.
179        first: String,
180        /// Second owner.
181        second: String,
182    },
183    /// A graph referenced a fact outside the sealed world.
184    UnknownFact {
185        /// Referring conclusion.
186        conclusion: ConclusionId,
187        /// Missing fact.
188        fact: FactId,
189    },
190    /// No owner graph contributed a conclusion.
191    EmptyClosure,
192    /// Requested conclusion is absent.
193    UnknownConclusion(ConclusionId),
194    /// Conclusion does not consume the requested fact.
195    Unrelated {
196        /// Requested conclusion.
197        conclusion: ConclusionId,
198        /// Requested fact.
199        fact: FactId,
200    },
201}
202
203impl fmt::Display for ClosureError {
204    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
205        write!(formatter, "{self:?}")
206    }
207}
208
209impl Error for ClosureError {}
sim_incremental_core/projection/graph.rs

sim_incremental_core/projection/
graph.rs
