cedar_policy_core/
transitive_closure.rs

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

cedar_policy_core/
transitive_closure.rs
