cedar_policy_core/
transitive_closure.rs

1/*
2 * Copyright Cedar Contributors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      https://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17//! Module containing code to compute the transitive closure of a graph.
18//! This is a generic utility, and not specific to Cedar.
19
20use std::collections::{HashMap, HashSet};
21use std::fmt::{Debug, Display};
22use std::hash::Hash;
23
24mod err;
25pub use err::*;
26use itertools::Itertools;
27
28/// Trait used to generalize transitive closure computation. This trait should
29/// be implemented for types representing a node in the hierarchy (e.g., the
30/// entity hierarchy) where we need to compute the transitive closure of the
31/// hierarchy starting from only direct adjacencies. This trait is parametrized
32/// by a type `K` which represents a unique identifier for graph nodes.
33pub trait TCNode<K> {
34    /// Extract a unique identifier for the node.
35    fn get_key(&self) -> K;
36
37    /// Add an edge out off this node to the node with key `k`.
38    fn add_edge_to(&mut self, k: K);
39
40    /// Retrieve an iterator for the edges out of this node.
41    fn out_edges(&self) -> Box<dyn Iterator<Item = &K> + '_>;
42
43    /// Return true when their is an edge between this node and the node with
44    /// key `k`.
45    fn has_edge_to(&self, k: &K) -> bool;
46}
47
48/// Given Graph as a map from keys with type `K` to implementations of `TCNode`
49/// with type `V`, compute the transitive closure of the hierarchy. In case of
50/// error, the result contains an error structure `Err<K>` which contains the
51/// keys (with type `K`) for the nodes in the graph which caused the error.
52/// If `enforce_dag` then also check that the heirarchy is a DAG
53pub fn compute_tc<K, V>(nodes: &mut HashMap<K, V>, enforce_dag: bool) -> Result<(), K>
54where
55    K: Clone + Eq + Hash + Debug + Display,
56    V: TCNode<K>,
57{
58    compute_tc_internal::<K, V>(nodes);
59    if enforce_dag {
60        return enforce_dag_from_tc(nodes);
61    }
62    Ok(())
63}
64
65/// Given graph as a map from keys with type `K` to implementations of `TCNode`
66/// with type `V`, compute the transitive closure of the hierarchy. In case of
67/// error, the result contains an error structure `Err<K>` which contains the
68/// keys (with type `K`) for the nodes in the graph which caused the error.
69fn compute_tc_internal<K, V>(nodes: &mut HashMap<K, V>)
70where
71    K: Clone + Eq + Hash,
72    V: TCNode<K>,
73{
74    // To avoid needing both immutable and mutable borrows of `nodes`,
75    // we collect all the needed updates in this structure
76    // (maps keys to ancestor UIDs to add to it)
77    // and then do all the updates at once in a second loop
78    let mut ancestors: HashMap<K, HashSet<K>> = HashMap::new();
79    for node in nodes.values() {
80        let this_node_ancestors: &mut HashSet<K> = ancestors.entry(node.get_key()).or_default();
81        add_ancestors_to_set(node, nodes, this_node_ancestors);
82    }
83    for node in nodes.values_mut() {
84        // PANIC SAFETY All nodes in `ancestors` came from `nodes`
85        #[allow(clippy::expect_used)]
86        for ancestor_uid in ancestors
87            .get(&node.get_key())
88            .expect("shouldn't have added any new values to the `nodes` map")
89        {
90            node.add_edge_to(ancestor_uid.clone());
91        }
92    }
93}
94
95/// Given a graph (as a map from keys to `TCNode`), enforce that
96/// all transitive edges are included, ie, the transitive closure has already
97/// been computed and that it is a DAG. If this is not the case, return an appropriate
98/// `TCEnforcementError`.
99pub fn enforce_tc_and_dag<K, V>(entities: &HashMap<K, V>) -> Result<(), K>
100where
101    K: Clone + Eq + Hash + Debug + Display,
102    V: TCNode<K>,
103{
104    let res = enforce_tc(entities);
105    if res.is_ok() {
106        return enforce_dag_from_tc(entities);
107    }
108    res
109}
110
111/// Given a DAG (as a map from keys to `TCNode`), enforce that
112/// all transitive edges are included, i.e., the transitive closure has already
113/// been computed. If this is not the case, return an appropriate
114/// `MissingTcEdge` error.
115fn enforce_tc<K, V>(entities: &HashMap<K, V>) -> Result<(), K>
116where
117    K: Clone + Eq + Hash + Debug + Display,
118    V: TCNode<K>,
119{
120    for entity in entities.values() {
121        for parent_uid in entity.out_edges() {
122            // check that `entity` is also a child of all of this parent's parents
123            if let Some(parent) = entities.get(parent_uid) {
124                for grandparent in parent.out_edges() {
125                    if !entity.has_edge_to(grandparent) {
126                        return Err(TcError::missing_tc_edge(
127                            entity.get_key(),
128                            parent_uid.clone(),
129                            grandparent.clone(),
130                        ));
131                    }
132                }
133            }
134        }
135    }
136    Ok(())
137}
138
139/// For the given `node` in the given `hierarchy`, add all of the `node`'s
140/// transitive ancestors to the given set. Assume that any nodes already in
141/// `ancestors` don't need to be searched -- they have been already handled.
142fn add_ancestors_to_set<K, V>(node: &V, hierarchy: &HashMap<K, V>, ancestors: &mut HashSet<K>)
143where
144    K: Clone + Eq + Hash,
145    V: TCNode<K>,
146{
147    for ancestor_uid in node.out_edges() {
148        if ancestors.insert(ancestor_uid.clone()) {
149            // discovered a new ancestor, so add the ancestors of `ancestor` as
150            // well
151            if let Some(ancestor) = hierarchy.get(ancestor_uid) {
152                add_ancestors_to_set(ancestor, hierarchy, ancestors);
153            }
154        }
155    }
156}
157
158/// Once the transitive closure (as defined above) is computed/enforced for the graph, we have:
159/// \forall u,v,w \in Vertices . (u,v) \in Edges /\ (v,w) \in Edges -> (u,w) \in Edges
160///
161/// Then the graph has a cycle if
162/// \exists v \in Vertices. (v,v) \in Edges
163fn enforce_dag_from_tc<K, V>(entities: &HashMap<K, V>) -> Result<(), K>
164where
165    K: Clone + Eq + Hash + Debug + Display,
166    V: TCNode<K>,
167{
168    for entity in entities.values() {
169        let key = entity.get_key();
170        if entity.out_edges().contains(&key) {
171            return Err(TcError::has_cycle(key));
172        }
173    }
174    Ok(())
175}
176
177// PANIC SAFETY test cases
178#[allow(clippy::indexing_slicing)]
179// PANIC SAFETY: Unit Test Code
180#[allow(clippy::panic)]
181#[cfg(test)]
182mod tests {
183    use crate::ast::{Entity, EntityUID};
184
185    use super::*;
186
187    #[test]
188    fn basic() {
189        // start with A -> B -> C
190        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
191        a.add_ancestor(EntityUID::with_eid("B"));
192        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
193        b.add_ancestor(EntityUID::with_eid("C"));
194        let c = Entity::with_uid(EntityUID::with_eid("C"));
195        let mut entities = HashMap::from([
196            (a.uid().clone(), a),
197            (b.uid().clone(), b),
198            (c.uid().clone(), c),
199        ]);
200        // currently doesn't pass TC enforcement
201        assert!(enforce_tc(&entities).is_err());
202        // compute TC
203        compute_tc_internal(&mut entities);
204        let a = &entities[&EntityUID::with_eid("A")];
205        let b = &entities[&EntityUID::with_eid("B")];
206        let c = &entities[&EntityUID::with_eid("C")];
207        // should have added the A -> C edge
208        assert!(a.is_descendant_of(&EntityUID::with_eid("C")));
209        // but we shouldn't have added other edges, like B -> A or C -> A
210        assert!(!b.is_descendant_of(&EntityUID::with_eid("A")));
211        assert!(!c.is_descendant_of(&EntityUID::with_eid("A")));
212        // now it should pass TC enforcement
213        assert!(enforce_tc(&entities).is_ok());
214        // passes cycle check after TC enforcement
215        assert!(enforce_dag_from_tc(&entities).is_ok());
216    }
217
218    #[test]
219    fn reversed() {
220        // same as basic(), but we put the entities in the map in the reverse
221        // order, which shouldn't make a difference
222        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
223        a.add_ancestor(EntityUID::with_eid("B"));
224        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
225        b.add_ancestor(EntityUID::with_eid("C"));
226        let c = Entity::with_uid(EntityUID::with_eid("C"));
227        let mut entities = HashMap::from([
228            (c.uid().clone(), c),
229            (b.uid().clone(), b),
230            (a.uid().clone(), a),
231        ]);
232        // currently doesn't pass TC enforcement
233        assert!(enforce_tc(&entities).is_err());
234        // compute TC
235        compute_tc_internal(&mut entities);
236        let a = &entities[&EntityUID::with_eid("A")];
237        let b = &entities[&EntityUID::with_eid("B")];
238        let c = &entities[&EntityUID::with_eid("C")];
239        // should have added the A -> C edge
240        assert!(a.is_descendant_of(&EntityUID::with_eid("C")));
241        // but we shouldn't have added other edges, like B -> A or C -> A
242        assert!(!b.is_descendant_of(&EntityUID::with_eid("A")));
243        assert!(!c.is_descendant_of(&EntityUID::with_eid("A")));
244        // now it should pass TC enforcement
245        assert!(enforce_tc(&entities).is_ok());
246        // passes cycle check after TC enforcement
247        assert!(enforce_dag_from_tc(&entities).is_ok());
248    }
249
250    #[test]
251    fn deeper() {
252        // start with A -> B -> C -> D -> E
253        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
254        a.add_ancestor(EntityUID::with_eid("B"));
255        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
256        b.add_ancestor(EntityUID::with_eid("C"));
257        let mut c = Entity::with_uid(EntityUID::with_eid("C"));
258        c.add_ancestor(EntityUID::with_eid("D"));
259        let mut d = Entity::with_uid(EntityUID::with_eid("D"));
260        d.add_ancestor(EntityUID::with_eid("E"));
261        let e = Entity::with_uid(EntityUID::with_eid("E"));
262        let mut entities = HashMap::from([
263            (a.uid().clone(), a),
264            (b.uid().clone(), b),
265            (c.uid().clone(), c),
266            (d.uid().clone(), d),
267            (e.uid().clone(), e),
268        ]);
269        // currently doesn't pass TC enforcement
270        assert!(enforce_tc(&entities).is_err());
271        // compute TC
272        compute_tc_internal(&mut entities);
273        let a = &entities[&EntityUID::with_eid("A")];
274        let b = &entities[&EntityUID::with_eid("B")];
275        let c = &entities[&EntityUID::with_eid("C")];
276        // should have added many edges which we check for
277        assert!(a.is_descendant_of(&EntityUID::with_eid("C")));
278        assert!(a.is_descendant_of(&EntityUID::with_eid("D")));
279        assert!(a.is_descendant_of(&EntityUID::with_eid("E")));
280        assert!(b.is_descendant_of(&EntityUID::with_eid("D")));
281        assert!(b.is_descendant_of(&EntityUID::with_eid("E")));
282        assert!(c.is_descendant_of(&EntityUID::with_eid("E")));
283        // now it should pass TC enforcement
284        assert!(enforce_tc(&entities).is_ok());
285        // passes cycle check after TC enforcement
286        assert!(enforce_dag_from_tc(&entities).is_ok());
287    }
288
289    #[test]
290    fn not_alphabetized() {
291        // same as deeper(), but the entities' parent relations don't follow
292        // alphabetical order. (In case we end up iterating through the map
293        // in alphabetical order, this test will ensure that everything works
294        // even when we aren't processing the entities in hierarchy order.)
295        // start with foo -> bar -> baz -> ham -> eggs
296        let mut foo = Entity::with_uid(EntityUID::with_eid("foo"));
297        foo.add_ancestor(EntityUID::with_eid("bar"));
298        let mut bar = Entity::with_uid(EntityUID::with_eid("bar"));
299        bar.add_ancestor(EntityUID::with_eid("baz"));
300        let mut baz = Entity::with_uid(EntityUID::with_eid("baz"));
301        baz.add_ancestor(EntityUID::with_eid("ham"));
302        let mut ham = Entity::with_uid(EntityUID::with_eid("ham"));
303        ham.add_ancestor(EntityUID::with_eid("eggs"));
304        let eggs = Entity::with_uid(EntityUID::with_eid("eggs"));
305        let mut entities = HashMap::from([
306            (ham.uid().clone(), ham),
307            (bar.uid().clone(), bar),
308            (foo.uid().clone(), foo),
309            (eggs.uid().clone(), eggs),
310            (baz.uid().clone(), baz),
311        ]);
312        // currently doesn't pass TC enforcement
313        assert!(enforce_tc(&entities).is_err());
314        // compute TC
315        compute_tc_internal(&mut entities);
316        let foo = &entities[&EntityUID::with_eid("foo")];
317        let bar = &entities[&EntityUID::with_eid("bar")];
318        let baz = &entities[&EntityUID::with_eid("baz")];
319        // should have added many edges which we check for
320        assert!(foo.is_descendant_of(&EntityUID::with_eid("baz")));
321        assert!(foo.is_descendant_of(&EntityUID::with_eid("ham")));
322        assert!(foo.is_descendant_of(&EntityUID::with_eid("eggs")));
323        assert!(bar.is_descendant_of(&EntityUID::with_eid("ham")));
324        assert!(bar.is_descendant_of(&EntityUID::with_eid("eggs")));
325        assert!(baz.is_descendant_of(&EntityUID::with_eid("eggs")));
326        // now it should pass TC enforcement
327        assert!(enforce_tc(&entities).is_ok());
328        // passes cycle check after TC enforcement
329        assert!(enforce_dag_from_tc(&entities).is_ok());
330    }
331
332    #[test]
333    fn multi_parents() {
334        // start with this:
335        //     B -> C
336        //   /
337        // A
338        //   \
339        //     D -> E
340        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
341        a.add_ancestor(EntityUID::with_eid("B"));
342        a.add_ancestor(EntityUID::with_eid("D"));
343        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
344        b.add_ancestor(EntityUID::with_eid("C"));
345        let c = Entity::with_uid(EntityUID::with_eid("C"));
346        let mut d = Entity::with_uid(EntityUID::with_eid("D"));
347        d.add_ancestor(EntityUID::with_eid("E"));
348        let e = Entity::with_uid(EntityUID::with_eid("E"));
349        let mut entities = HashMap::from([
350            (a.uid().clone(), a),
351            (b.uid().clone(), b),
352            (c.uid().clone(), c),
353            (d.uid().clone(), d),
354            (e.uid().clone(), e),
355        ]);
356        // currently doesn't pass TC enforcement
357        assert!(enforce_tc(&entities).is_err());
358        // compute TC
359        compute_tc_internal(&mut entities);
360        let a = &entities[&EntityUID::with_eid("A")];
361        let b = &entities[&EntityUID::with_eid("B")];
362        let d = &entities[&EntityUID::with_eid("D")];
363        // should have added the A -> C edge and the A -> E edge
364        assert!(a.is_descendant_of(&EntityUID::with_eid("C")));
365        assert!(a.is_descendant_of(&EntityUID::with_eid("E")));
366        // but it shouldn't have added these other edges
367        assert!(!b.is_descendant_of(&EntityUID::with_eid("D")));
368        assert!(!b.is_descendant_of(&EntityUID::with_eid("E")));
369        assert!(!d.is_descendant_of(&EntityUID::with_eid("B")));
370        assert!(!d.is_descendant_of(&EntityUID::with_eid("C")));
371        // now it should pass TC enforcement
372        assert!(enforce_tc(&entities).is_ok());
373        // passes cycle check after TC enforcement
374        assert!(enforce_dag_from_tc(&entities).is_ok());
375    }
376
377    #[test]
378    fn dag() {
379        // start with this:
380        //     B -> C
381        //   /  \
382        // A      D -> E -> H
383        //   \        /
384        //     F -> G
385        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
386        a.add_ancestor(EntityUID::with_eid("B"));
387        a.add_ancestor(EntityUID::with_eid("F"));
388        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
389        b.add_ancestor(EntityUID::with_eid("C"));
390        b.add_ancestor(EntityUID::with_eid("D"));
391        let c = Entity::with_uid(EntityUID::with_eid("C"));
392        let mut d = Entity::with_uid(EntityUID::with_eid("D"));
393        d.add_ancestor(EntityUID::with_eid("E"));
394        let mut e = Entity::with_uid(EntityUID::with_eid("E"));
395        e.add_ancestor(EntityUID::with_eid("H"));
396        let mut f = Entity::with_uid(EntityUID::with_eid("F"));
397        f.add_ancestor(EntityUID::with_eid("G"));
398        let mut g = Entity::with_uid(EntityUID::with_eid("G"));
399        g.add_ancestor(EntityUID::with_eid("E"));
400        let h = Entity::with_uid(EntityUID::with_eid("H"));
401        let mut entities = HashMap::from([
402            (a.uid().clone(), a),
403            (b.uid().clone(), b),
404            (c.uid().clone(), c),
405            (d.uid().clone(), d),
406            (e.uid().clone(), e),
407            (f.uid().clone(), f),
408            (g.uid().clone(), g),
409            (h.uid().clone(), h),
410        ]);
411        // currently doesn't pass TC enforcement
412        assert!(enforce_tc(&entities).is_err());
413        // compute TC
414        compute_tc_internal(&mut entities);
415        let a = &entities[&EntityUID::with_eid("A")];
416        let b = &entities[&EntityUID::with_eid("B")];
417        let f = &entities[&EntityUID::with_eid("F")];
418        // should have added many edges which we check for
419        assert!(a.is_descendant_of(&EntityUID::with_eid("C")));
420        assert!(a.is_descendant_of(&EntityUID::with_eid("D")));
421        assert!(a.is_descendant_of(&EntityUID::with_eid("E")));
422        assert!(a.is_descendant_of(&EntityUID::with_eid("F")));
423        assert!(a.is_descendant_of(&EntityUID::with_eid("G")));
424        assert!(a.is_descendant_of(&EntityUID::with_eid("H")));
425        assert!(b.is_descendant_of(&EntityUID::with_eid("E")));
426        assert!(b.is_descendant_of(&EntityUID::with_eid("H")));
427        assert!(f.is_descendant_of(&EntityUID::with_eid("E")));
428        assert!(f.is_descendant_of(&EntityUID::with_eid("H")));
429        // but it shouldn't have added these other edges
430        assert!(!b.is_descendant_of(&EntityUID::with_eid("F")));
431        assert!(!b.is_descendant_of(&EntityUID::with_eid("G")));
432        assert!(!f.is_descendant_of(&EntityUID::with_eid("C")));
433        assert!(!f.is_descendant_of(&EntityUID::with_eid("D")));
434        // now it should pass TC enforcement
435        assert!(enforce_tc(&entities).is_ok());
436        // passes cycle check after TC enforcement
437        assert!(enforce_dag_from_tc(&entities).is_ok());
438    }
439
440    #[test]
441    fn already_edges() {
442        // start with this, which already includes some (but not all) transitive
443        // edges
444        //     B --> E
445        //   /  \   /
446        // A ---> C
447        //   \   /
448        //     D --> F
449        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
450        a.add_ancestor(EntityUID::with_eid("B"));
451        a.add_ancestor(EntityUID::with_eid("C"));
452        a.add_ancestor(EntityUID::with_eid("D"));
453        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
454        b.add_ancestor(EntityUID::with_eid("C"));
455        b.add_ancestor(EntityUID::with_eid("E"));
456        let mut c = Entity::with_uid(EntityUID::with_eid("C"));
457        c.add_ancestor(EntityUID::with_eid("E"));
458        let mut d = Entity::with_uid(EntityUID::with_eid("D"));
459        d.add_ancestor(EntityUID::with_eid("C"));
460        d.add_ancestor(EntityUID::with_eid("F"));
461        let e = Entity::with_uid(EntityUID::with_eid("E"));
462        let f = Entity::with_uid(EntityUID::with_eid("F"));
463        let mut entities = HashMap::from([
464            (a.uid().clone(), a),
465            (b.uid().clone(), b),
466            (c.uid().clone(), c),
467            (d.uid().clone(), d),
468            (e.uid().clone(), e),
469            (f.uid().clone(), f),
470        ]);
471        // currently doesn't pass TC enforcement
472        assert!(enforce_tc(&entities).is_err());
473        // compute TC
474        compute_tc_internal(&mut entities);
475        let a = &entities[&EntityUID::with_eid("A")];
476        let b = &entities[&EntityUID::with_eid("B")];
477        let c = &entities[&EntityUID::with_eid("C")];
478        let d = &entities[&EntityUID::with_eid("D")];
479        // should have added many edges which we check for
480        assert!(a.is_descendant_of(&EntityUID::with_eid("E")));
481        assert!(a.is_descendant_of(&EntityUID::with_eid("F")));
482        assert!(d.is_descendant_of(&EntityUID::with_eid("E")));
483        // but it shouldn't have added these other edges
484        assert!(!b.is_descendant_of(&EntityUID::with_eid("F")));
485        assert!(!c.is_descendant_of(&EntityUID::with_eid("F")));
486        // now it should pass TC enforcement
487        assert!(enforce_tc(&entities).is_ok());
488        // passes cycle check after TC enforcement
489        assert!(enforce_dag_from_tc(&entities).is_ok());
490    }
491
492    #[test]
493    fn disjoint_dag() {
494        // graph with disconnected components:
495        //     B -> C
496        //
497        // A      D -> E -> H
498        //   \
499        //     F -> G
500        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
501        a.add_ancestor(EntityUID::with_eid("F"));
502        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
503        b.add_ancestor(EntityUID::with_eid("C"));
504        let c = Entity::with_uid(EntityUID::with_eid("C"));
505        let mut d = Entity::with_uid(EntityUID::with_eid("D"));
506        d.add_ancestor(EntityUID::with_eid("E"));
507        let mut e = Entity::with_uid(EntityUID::with_eid("E"));
508        e.add_ancestor(EntityUID::with_eid("H"));
509        let mut f = Entity::with_uid(EntityUID::with_eid("F"));
510        f.add_ancestor(EntityUID::with_eid("G"));
511        let g = Entity::with_uid(EntityUID::with_eid("G"));
512        let h = Entity::with_uid(EntityUID::with_eid("H"));
513        let mut entities = HashMap::from([
514            (a.uid().clone(), a),
515            (b.uid().clone(), b),
516            (c.uid().clone(), c),
517            (d.uid().clone(), d),
518            (e.uid().clone(), e),
519            (f.uid().clone(), f),
520            (g.uid().clone(), g),
521            (h.uid().clone(), h),
522        ]);
523        // currently doesn't pass TC enforcement
524        assert!(enforce_tc(&entities).is_err());
525        // compute TC
526        compute_tc_internal(&mut entities);
527        let a = &entities[&EntityUID::with_eid("A")];
528        let b = &entities[&EntityUID::with_eid("B")];
529        let d = &entities[&EntityUID::with_eid("D")];
530        let f = &entities[&EntityUID::with_eid("F")];
531        // should have added two edges
532        assert!(a.is_descendant_of(&EntityUID::with_eid("G")));
533        assert!(d.is_descendant_of(&EntityUID::with_eid("H")));
534        // but it shouldn't have added these other edges
535        assert!(!a.is_descendant_of(&EntityUID::with_eid("C")));
536        assert!(!a.is_descendant_of(&EntityUID::with_eid("D")));
537        assert!(!a.is_descendant_of(&EntityUID::with_eid("E")));
538        assert!(!a.is_descendant_of(&EntityUID::with_eid("H")));
539        assert!(!b.is_descendant_of(&EntityUID::with_eid("E")));
540        assert!(!b.is_descendant_of(&EntityUID::with_eid("H")));
541        assert!(!f.is_descendant_of(&EntityUID::with_eid("E")));
542        assert!(!f.is_descendant_of(&EntityUID::with_eid("H")));
543        assert!(!b.is_descendant_of(&EntityUID::with_eid("F")));
544        assert!(!b.is_descendant_of(&EntityUID::with_eid("G")));
545        assert!(!f.is_descendant_of(&EntityUID::with_eid("C")));
546        assert!(!f.is_descendant_of(&EntityUID::with_eid("D")));
547        // now it should pass TC enforcement
548        assert!(enforce_tc(&entities).is_ok());
549        // passes cycle check after TC enforcement
550        assert!(enforce_dag_from_tc(&entities).is_ok());
551    }
552
553    #[test]
554    fn trivial_cycle() {
555        // this graph is invalid, but we want to still have some reasonable behavior
556        // if we encounter it (and definitely not panic, infinitely recurse, etc)
557        //
558        // A -> B -> B
559        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
560        a.add_ancestor(EntityUID::with_eid("B"));
561        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
562        b.add_ancestor(EntityUID::with_eid("B"));
563        let mut entities = HashMap::from([(a.uid().clone(), a), (b.uid().clone(), b)]);
564        // computing TC should succeed without panicking, infinitely recursing, etc
565        compute_tc_internal(&mut entities);
566        // fails cycle check
567        match enforce_dag_from_tc(&entities) {
568            Ok(_) => panic!("enforce_dag_from_tc should have returned an error"),
569            Err(TcError::HasCycle(err)) => {
570                assert!(err.vertex_with_loop() == &EntityUID::with_eid("B"));
571            }
572            Err(_) => panic!("Unexpected error in enforce_dag_from_tc"),
573        }
574        let a = &entities[&EntityUID::with_eid("A")];
575        let b = &entities[&EntityUID::with_eid("B")];
576        // we check that the A -> B edge still exists
577        assert!(a.is_descendant_of(&EntityUID::with_eid("B")));
578        // but it shouldn't have added a B -> A edge
579        assert!(!b.is_descendant_of(&EntityUID::with_eid("A")));
580        // we also check that, whatever compute_tc_internal did with this invalid input, the
581        // final result still passes enforce_tc
582        assert!(enforce_tc(&entities).is_ok());
583        // still fails cycle check
584        match enforce_dag_from_tc(&entities) {
585            Ok(_) => panic!("enforce_dag_from_tc should have returned an error"),
586            Err(TcError::HasCycle(err)) => {
587                assert!(err.vertex_with_loop() == &EntityUID::with_eid("B"));
588            }
589            Err(_) => panic!("Unexpected error in enforce_dag_from_tc"),
590        }
591    }
592
593    #[test]
594    fn nontrivial_cycle() {
595        // this graph is invalid, but we want to still have some reasonable behavior
596        // if we encounter it (and definitely not panic, infinitely recurse, etc)
597        //
598        //          D
599        //        /
600        // A -> B -> C -> A
601        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
602        a.add_ancestor(EntityUID::with_eid("B"));
603        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
604        b.add_ancestor(EntityUID::with_eid("C"));
605        b.add_ancestor(EntityUID::with_eid("D"));
606        let mut c = Entity::with_uid(EntityUID::with_eid("C"));
607        c.add_ancestor(EntityUID::with_eid("A"));
608        let d = Entity::with_uid(EntityUID::with_eid("D"));
609        let mut entities = HashMap::from([
610            (a.uid().clone(), a),
611            (b.uid().clone(), b),
612            (c.uid().clone(), c),
613            (d.uid().clone(), d),
614        ]);
615        // computing TC should succeed without panicking, infinitely recursing, etc
616        compute_tc_internal(&mut entities);
617        // fails cycle check
618        match enforce_dag_from_tc(&entities) {
619            Ok(_) => panic!("enforce_dag_from_tc should have returned an error"),
620            Err(TcError::HasCycle(err)) => {
621                assert!(
622                    err.vertex_with_loop() == &EntityUID::with_eid("A")
623                        || err.vertex_with_loop() == &EntityUID::with_eid("B")
624                        || err.vertex_with_loop() == &EntityUID::with_eid("C")
625                );
626            }
627            Err(_) => panic!("Unexpected error in enforce_dag_from_tc"),
628        }
629        //TC tests
630        let a = &entities[&EntityUID::with_eid("A")];
631        let b = &entities[&EntityUID::with_eid("B")];
632        // we should have added A -> C and A -> D edges, at least
633        assert!(a.is_descendant_of(&EntityUID::with_eid("C")));
634        assert!(a.is_descendant_of(&EntityUID::with_eid("D")));
635        // and we should also have added a B -> A edge
636        assert!(b.is_descendant_of(&EntityUID::with_eid("A")));
637        // we also check that, whatever compute_tc_internal did with this invalid input, the
638        // final result still passes enforce_tc
639        assert!(enforce_tc(&entities).is_ok());
640        // still fails cycle check
641        match enforce_dag_from_tc(&entities) {
642            Ok(_) => panic!("enforce_dag_from_tc should have returned an error"),
643            Err(TcError::HasCycle(err)) => {
644                assert!(
645                    err.vertex_with_loop() == &EntityUID::with_eid("A")
646                        || err.vertex_with_loop() == &EntityUID::with_eid("B")
647                        || err.vertex_with_loop() == &EntityUID::with_eid("C")
648                );
649            }
650            Err(_) => panic!("Unexpected error in enforce_dag_from_tc"),
651        }
652    }
653
654    #[test]
655    fn disjoint_cycles() {
656        // graph with disconnected components including cycles:
657        //     B -> C -> B
658        //
659        // A      D -> E -> H -> D
660        //   \
661        //     F -> G
662        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
663        a.add_ancestor(EntityUID::with_eid("F"));
664        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
665        b.add_ancestor(EntityUID::with_eid("C"));
666        let mut c = Entity::with_uid(EntityUID::with_eid("C"));
667        c.add_ancestor(EntityUID::with_eid("B"));
668        let mut d = Entity::with_uid(EntityUID::with_eid("D"));
669        d.add_ancestor(EntityUID::with_eid("E"));
670        let mut e = Entity::with_uid(EntityUID::with_eid("E"));
671        e.add_ancestor(EntityUID::with_eid("H"));
672        let mut f = Entity::with_uid(EntityUID::with_eid("F"));
673        f.add_ancestor(EntityUID::with_eid("G"));
674        let g = Entity::with_uid(EntityUID::with_eid("G"));
675        let mut h = Entity::with_uid(EntityUID::with_eid("H"));
676        h.add_ancestor(EntityUID::with_eid("D"));
677        let mut entities = HashMap::from([
678            (a.uid().clone(), a),
679            (b.uid().clone(), b),
680            (c.uid().clone(), c),
681            (d.uid().clone(), d),
682            (e.uid().clone(), e),
683            (f.uid().clone(), f),
684            (g.uid().clone(), g),
685            (h.uid().clone(), h),
686        ]);
687        // currently doesn't pass TC enforcement
688        assert!(enforce_tc(&entities).is_err());
689        // compute TC
690        compute_tc_internal(&mut entities);
691        // now it should pass TC enforcement
692        assert!(enforce_tc(&entities).is_ok());
693        // still fails cycle check
694        match enforce_dag_from_tc(&entities) {
695            Ok(_) => panic!("enforce_dag_from_tc should have returned an error"),
696            Err(TcError::HasCycle(err)) => {
697                // two possible cycles
698                assert!(
699                    err.vertex_with_loop() == &EntityUID::with_eid("B")
700                        || err.vertex_with_loop() == &EntityUID::with_eid("C")
701                        || err.vertex_with_loop() == &EntityUID::with_eid("D")
702                        || err.vertex_with_loop() == &EntityUID::with_eid("E")
703                        || err.vertex_with_loop() == &EntityUID::with_eid("H")
704                );
705            }
706            Err(_) => panic!("Unexpected error in enforce_dag_from_tc"),
707        }
708    }
709
710    #[test]
711    fn intersecting_cycles() {
712        // graph with two intersecting cycles:
713        //  A -> B -> C -> E -
714        //  ^    ^         ^  |
715        //  |    |         |  |
716        //  |    |        /   |
717        //   \  /        /    |
718        //    D ------>F      |
719        //    ^               |
720        //    |___------------
721        let mut a = Entity::with_uid(EntityUID::with_eid("A"));
722        a.add_ancestor(EntityUID::with_eid("B"));
723        let mut b = Entity::with_uid(EntityUID::with_eid("B"));
724        b.add_ancestor(EntityUID::with_eid("C"));
725        let mut c = Entity::with_uid(EntityUID::with_eid("C"));
726        c.add_ancestor(EntityUID::with_eid("E"));
727        let mut d = Entity::with_uid(EntityUID::with_eid("D"));
728        d.add_ancestor(EntityUID::with_eid("A"));
729        d.add_ancestor(EntityUID::with_eid("B"));
730        d.add_ancestor(EntityUID::with_eid("F"));
731        let mut e = Entity::with_uid(EntityUID::with_eid("E"));
732        e.add_ancestor(EntityUID::with_eid("D"));
733        let mut f = Entity::with_uid(EntityUID::with_eid("F"));
734        f.add_ancestor(EntityUID::with_eid("E"));
735        let mut entities = HashMap::from([
736            (a.uid().clone(), a),
737            (b.uid().clone(), b),
738            (c.uid().clone(), c),
739            (d.uid().clone(), d),
740            (e.uid().clone(), e),
741            (f.uid().clone(), f),
742        ]);
743        // fails TC enforcement
744        assert!(enforce_tc(&entities).is_err());
745        // compute TC
746        compute_tc_internal(&mut entities);
747        // now it should pass TC enforcement
748        assert!(enforce_tc(&entities).is_ok());
749        // but still fail cycle check
750        match enforce_dag_from_tc(&entities) {
751            Ok(_) => panic!("enforce_dag_from_tc should have returned an error"),
752            Err(TcError::HasCycle(_)) => (), // Every vertex is in a cycle
753            Err(_) => panic!("Unexpected error in enforce_dag_from_tc"),
754        }
755    }
756}
cedar_policy_core/transitive_closure.rs

cedar_policy_core/
transitive_closure.rs
