Repository: cedar-policy/cedar
Pull request #1453 (2025-02-06 16:15:30)

Entity removal
## Description of changes

Adds the ability to remove `Entity`s from  an `Entities` struct.

## Issue #701 

## Checklist for requesting a review

The change in this PR is (choose one, and delete the other options):

- [x] A backwards-compatible change requiring a minor version bump to `cedar-policy` (e.g., addition of a new API).

I confirm that this PR (choose one, and delete the other options):

- [x] Updates the "Unreleased" section of the CHANGELOG with a description of my change (required for major/minor version bumps).

I confirm that [`cedar-spec`](https://github.com/cedar-policy/cedar-spec) (choose one, and delete the other options):

- [x] I'm not sure how my change impacts `cedar-spec`. (Post your PR anyways, and we'll discuss in the comments.)

I confirm that [`docs.cedarpolicy.com`](https://docs.cedarpolicy.com/) (choose one, and delete the other options):

- [x] Does not require updates because my change does not impact the Cedar language specification.



Patch:
diff --git a/cedar-policy-core/src/ast/entity.rs b/cedar-policy-core/src/ast/entity.rs
index 0bc9d81f..f027dd4a 100644
--- a/cedar-policy-core/src/ast/entity.rs
+++ b/cedar-policy-core/src/ast/entity.rs
@@ -290,9 +290,15 @@ pub struct Entity {
     /// `RestrictedExpr`s, for mostly historical reasons.
     attrs: BTreeMap<SmolStr, PartialValueSerializedAsExpr>,
 
-    /// Set of ancestors of this `Entity` (i.e., all direct and transitive
-    /// parents), as UIDs
-    ancestors: HashSet<EntityUID>,
+    /// Set of indirect ancestors of this `Entity` as UIDs
+    indirect_ancestors: HashSet<EntityUID>,
+
+    /// Set of direct ancestors (i.e., parents) as UIDs
+    ///
+    /// indirect_ancestors and parents should be disjoint
+    /// even if a parent is also an indirect parent through
+    /// a different parent
+    parents: HashSet<EntityUID>,
 
     /// Tags on this entity (RFC 82)
     ///
@@ -318,7 +324,8 @@ impl Entity {
     pub fn new(
         uid: EntityUID,
         attrs: impl IntoIterator<Item = (SmolStr, RestrictedExpr)>,
-        ancestors: HashSet<EntityUID>,
+        indirect_ancestors: HashSet<EntityUID>,
+        parents: HashSet<EntityUID>,
         tags: impl IntoIterator<Item = (SmolStr, RestrictedExpr)>,
         extensions: &Extensions<'_>,
     ) -> Result<Self, EntityAttrEvaluationError> {
@@ -345,7 +352,8 @@ impl Entity {
         Ok(Entity {
             uid,
             attrs: evaluated_attrs,
-            ancestors,
+            indirect_ancestors,
+            parents,
             tags: evaluated_tags,
         })
     }
@@ -361,13 +369,15 @@ impl Entity {
     pub fn new_with_attr_partial_value(
         uid: EntityUID,
         attrs: impl IntoIterator<Item = (SmolStr, PartialValue)>,
-        ancestors: HashSet<EntityUID>,
+        indirect_ancestors: HashSet<EntityUID>,
+        parents: HashSet<EntityUID>,
         tags: impl IntoIterator<Item = (SmolStr, PartialValue)>,
     ) -> Self {
         Self::new_with_attr_partial_value_serialized_as_expr(
             uid,
             attrs.into_iter().map(|(k, v)| (k, v.into())).collect(),
-            ancestors,
+            indirect_ancestors,
+            parents,
             tags.into_iter().map(|(k, v)| (k, v.into())).collect(),
         )
     }
@@ -379,13 +389,15 @@ impl Entity {
     pub fn new_with_attr_partial_value_serialized_as_expr(
         uid: EntityUID,
         attrs: BTreeMap<SmolStr, PartialValueSerializedAsExpr>,
-        ancestors: HashSet<EntityUID>,
+        indirect_ancestors: HashSet<EntityUID>,
+        parents: HashSet<EntityUID>,
         tags: BTreeMap<SmolStr, PartialValueSerializedAsExpr>,
     ) -> Self {
         Entity {
             uid,
             attrs,
-            ancestors,
+            indirect_ancestors,
+            parents,
             tags,
         }
     }
@@ -405,14 +417,34 @@ impl Entity {
         self.tags.get(tag).map(|v| v.as_ref())
     }
 
-    /// Is this `Entity` a descendant of `e` in the entity hierarchy?
+    /// Is this `Entity` a (direct or indirect) descendant of `e` in the entity hierarchy?
     pub fn is_descendant_of(&self, e: &EntityUID) -> bool {
-        self.ancestors.contains(e)
+        self.parents.contains(e) || self.indirect_ancestors.contains(e)
+    }
+
+    /// Is this `Entity` a an indirect descendant of `e` in the entity hierarchy?
+    pub fn is_indirect_descendant_of(&self, e: &EntityUID) -> bool {
+        self.indirect_ancestors.contains(e)
+    }
+
+    /// Is this `Entity` a direct decendant (child) of `e` in the entity hierarchy?
+    pub fn is_child_of(&self, e: &EntityUID) -> bool {
+        self.parents.contains(e)
     }
 
-    /// Iterate over this entity's ancestors
+    /// Iterate over this entity's (direct or indirect) ancestors
     pub fn ancestors(&self) -> impl Iterator<Item = &EntityUID> {
-        self.ancestors.iter()
+        self.parents.iter().chain(self.indirect_ancestors.iter())
+    }
+
+    /// Iterate over this entity's indirect ancestors
+    pub fn indirect_ancestors(&self) -> impl Iterator<Item = &EntityUID> {
+        self.indirect_ancestors.iter()
+    }
+
+    /// Iterate over this entity's direct ancestors (parents)
+    pub fn parents(&self) -> impl Iterator<Item = &EntityUID> {
+        self.parents.iter()
     }
 
     /// Get the number of attributes on this entity
@@ -450,16 +482,22 @@ impl Entity {
         Self {
             uid,
             attrs: BTreeMap::new(),
-            ancestors: HashSet::new(),
+            indirect_ancestors: HashSet::new(),
+            parents: HashSet::new(),
             tags: BTreeMap::new(),
         }
     }
 
     /// Test if two `Entity` objects are deep/structurally equal.
     /// That is, not only do they have the same UID, but also the same
-    /// attributes, attribute values, and ancestors.
+    /// attributes, attribute values, and ancestors/parents.
+    ///
+    /// Does not test that they have the same _direct_ parents, only that they have the same overall ancestor set.
     pub(crate) fn deep_eq(&self, other: &Self) -> bool {
-        self.uid == other.uid && self.attrs == other.attrs && self.ancestors == other.ancestors
+        self.uid == other.uid
+            && self.attrs == other.attrs
+            && (self.ancestors().collect::<HashSet<_>>())
+                == (other.ancestors().collect::<HashSet<_>>())
     }
 
     /// Set the UID to the given value.
@@ -497,30 +535,68 @@ impl Entity {
         Ok(())
     }
 
-    /// Mark the given `UID` as an ancestor of this `Entity`
-    pub fn add_ancestor(&mut self, uid: EntityUID) {
-        self.ancestors.insert(uid);
+    /// Mark the given `UID` as an indirect ancestor of this `Entity`
+    ///
+    /// The given `UID` will not be added as an indirecty ancestor if
+    /// it is already a direct ancestor (parent) of this `Entity`
+    /// The caller of this code is responsible for maintaining
+    /// transitive closure of hierarchy.
+    pub fn add_indirect_ancestor(&mut self, uid: EntityUID) {
+        if !self.parents.contains(&uid) {
+            self.indirect_ancestors.insert(uid);
+        }
+    }
+
+    /// Mark the given `UID` as a (direct) parent of this `Entity`, and
+    /// remove the UID from indirect ancestors
+    /// if it was previously added as an indirect ancestor
+    /// The caller of this code is responsible for maintaining
+    /// transitive closure of hierarchy.
+    pub fn add_parent(&mut self, uid: EntityUID) {
+        self.indirect_ancestors.remove(&uid);
+        self.parents.insert(uid);
     }
 
-    /// Consume the entity and return the entity's owned Uid, attributes, parents, and tags.
+    /// Remove the given `UID` as an indirect ancestor of this `Entity`.
+    ///
+    /// No effect if the `UID` is a direct parent.
+    /// The caller of this code is responsible for maintaining
+    /// transitive closure of hierarchy.
+    pub fn remove_indirect_ancestor(&mut self, uid: &EntityUID) {
+        self.indirect_ancestors.remove(uid);
+    }
+
+    /// Remove the given `UID` as a (direct) parent of this `Entity`.
+    ///
+    /// No effect on the `Entity`'s indirect ancestors.
+    /// The caller of this code is responsible for maintaining
+    /// transitive closure of hierarchy.
+    pub fn remove_parent(&mut self, uid: &EntityUID) {
+        self.parents.remove(uid);
+    }
+
+    /// Consume the entity and return the entity's owned Uid, attributes, ancestors, parents, and tags.
     pub fn into_inner(
         self,
     ) -> (
         EntityUID,
         HashMap<SmolStr, PartialValue>,
         HashSet<EntityUID>,
+        HashSet<EntityUID>,
         HashMap<SmolStr, PartialValue>,
     ) {
         let Self {
             uid,
             attrs,
-            ancestors,
+            indirect_ancestors,
+            parents,
             tags,
         } = self;
         (
             uid,
             attrs.into_iter().map(|(k, v)| (k, v.0)).collect(),
-            ancestors,
+            indirect_ancestors,
+            parents,
             tags.into_iter().map(|(k, v)| (k, v.0)).collect(),
         )
     }
@@ -568,7 +644,7 @@ impl TCNode<EntityUID> for Entity {
     }
 
     fn add_edge_to(&mut self, k: EntityUID) {
-        self.add_ancestor(k)
+        self.add_indirect_ancestor(k);
     }
 
     fn out_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
@@ -587,7 +663,7 @@ impl TCNode<EntityUID> for Arc<Entity> {
 
     fn add_edge_to(&mut self, k: EntityUID) {
         // Use Arc::make_mut to get a mutable reference to the inner value
-        Arc::make_mut(self).add_ancestor(k)
+        Arc::make_mut(self).add_indirect_ancestor(k)
     }
 
     fn out_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
@@ -609,7 +685,7 @@ impl std::fmt::Display for Entity {
                 .iter()
                 .map(|(k, v)| format!("{}: {}", k, v))
                 .join("; "),
-            self.ancestors.iter().join(", ")
+            self.ancestors().join(", ")
         )
     }
 }
diff --git a/cedar-policy-core/src/entities.rs b/cedar-policy-core/src/entities.rs
index 8c0f3875..06cfdd35 100644
--- a/cedar-policy-core/src/entities.rs
+++ b/cedar-policy-core/src/entities.rs
@@ -55,7 +55,7 @@ pub struct Entities {
     /// `serde_as` annotation are used to serialize the data as associative
     /// lists instead.
     ///
-    /// Important internal invariant: for any `Entities` object that exists, the
+    /// Important internal invariant: for any `Entities` object that exists,
     /// the `ancestor` relation is transitively closed.
     #[serde_as(as = "Vec<(_, _)>")]
     entities: HashMap<EntityUID, Arc<Entity>>,
@@ -162,6 +162,42 @@ impl Entities {
         Ok(self)
     }
 
+    /// Removes the [`crate::ast::EntityUID`]s in the interator from this [`Entities`]
+    /// Fails if any error is encountered in the transitive closure computation.
+    ///
+    /// If you pass [`TCComputation::AssumeAlreadyComputed`], then the caller is
+    /// responsible for ensuring that TC and DAG hold before calling this method
+    pub fn remove_entities(
+        mut self,
+        collection: impl IntoIterator<Item = EntityUID>,
+        tc_computation: TCComputation,
+    ) -> Result<Self> {
+        for uid_to_remove in collection.into_iter() {
+            match self.entities.remove(&uid_to_remove) {
+                None => (),
+                Some(entity_to_remove) => {
+                    for entity in self.entities.values_mut() {
+                        if entity.is_descendant_of(&uid_to_remove) {
+                            // remove any direct or indirect link between `entity` and `entity_to_remove`
+                            Arc::make_mut(entity).remove_indirect_ancestor(&uid_to_remove);
+                            Arc::make_mut(entity).remove_parent(&uid_to_remove);
+                            // remove any indirect link between `entity` and the ancestors of `entity_to_remove`
+                            for ancestor_uid in entity_to_remove.ancestors() {
+                                Arc::make_mut(entity).remove_indirect_ancestor(ancestor_uid);
+                            }
+                        }
+                    }
+                }
+            }
+        }
+        match tc_computation {
+            TCComputation::AssumeAlreadyComputed => (),
+            TCComputation::EnforceAlreadyComputed => enforce_tc_and_dag(&self.entities)?,
+            TCComputation::ComputeNow => compute_tc(&mut self.entities, true)?,
+        }
+        Ok(self)
+    }
+
     /// Create an `Entities` object with the given entities.
     ///
     /// If `schema` is present, then action entities from that schema will also
@@ -1755,6 +1791,7 @@ mod json_parsing_tests {
                     ),
                 ),
             ],
+            [].into_iter().collect(),
             [
                 EntityUID::with_eid("parent1"),
                 EntityUID::with_eid("parent2"),
@@ -1799,6 +1836,7 @@ mod json_parsing_tests {
                 "oops".into(),
                 RestrictedExpr::record([("__entity".into(), RestrictedExpr::val("hi"))]).unwrap(),
             )],
+            [].into_iter().collect(),
             [
                 EntityUID::with_eid("parent1"),
                 EntityUID::with_eid("parent2"),
@@ -1919,6 +1957,7 @@ mod json_parsing_tests {
 #[cfg(test)]
 mod entities_tests {
     use super::*;
+    use cool_asserts::assert_matches;
 
     #[test]
     fn empty_entities() {
@@ -1966,8 +2005,8 @@ mod entities_tests {
         let mut e1 = Entity::with_uid(EntityUID::with_eid("a"));
         let mut e2 = Entity::with_uid(EntityUID::with_eid("b"));
         let e3 = Entity::with_uid(EntityUID::with_eid("c"));
-        e1.add_ancestor(EntityUID::with_eid("b"));
-        e2.add_ancestor(EntityUID::with_eid("c"));
+        e1.add_indirect_ancestor(EntityUID::with_eid("b"));
+        e2.add_indirect_ancestor(EntityUID::with_eid("c"));
 
         let es = Entities::from_entities(
             vec![e1, e2, e3],
@@ -1991,9 +2030,9 @@ mod entities_tests {
         let mut e1 = Entity::with_uid(EntityUID::with_eid("a"));
         let mut e2 = Entity::with_uid(EntityUID::with_eid("b"));
         let e3 = Entity::with_uid(EntityUID::with_eid("c"));
-        e1.add_ancestor(EntityUID::with_eid("b"));
-        e1.add_ancestor(EntityUID::with_eid("c"));
-        e2.add_ancestor(EntityUID::with_eid("c"));
+        e1.add_indirect_ancestor(EntityUID::with_eid("b"));
+        e1.add_indirect_ancestor(EntityUID::with_eid("c"));
+        e2.add_indirect_ancestor(EntityUID::with_eid("c"));
 
         Entities::from_entities(
             vec![e1, e2, e3],
@@ -2003,6 +2042,64 @@ mod entities_tests {
         )
         .expect("Should have succeeded");
     }
+
+    #[test]
+    fn test_remove_entities() {
+        // Original Hierarchy
+        // F -> A
+        // F -> D -> A, D -> B, D -> C
+        // F -> E -> C
+        let aid = EntityUID::with_eid("A");
+        let a = Entity::with_uid(aid.clone());
+        let bid = EntityUID::with_eid("B");
+        let b = Entity::with_uid(bid.clone());
+        let cid = EntityUID::with_eid("C");
+        let c = Entity::with_uid(cid.clone());
+        let did = EntityUID::with_eid("D");
+        let mut d = Entity::with_uid(did.clone());
+        let eid = EntityUID::with_eid("E");
+        let mut e = Entity::with_uid(eid.clone());
+        let fid = EntityUID::with_eid("F");
+        let mut f = Entity::with_uid(fid.clone());
+        f.add_parent(aid.clone());
+        f.add_parent(did.clone());
+        f.add_parent(eid.clone());
+        d.add_parent(aid.clone());
+        d.add_parent(bid.clone());
+        d.add_parent(cid.clone());
+        e.add_parent(cid.clone());
+
+        // Construct original hierarchy
+        let entities = Entities::from_entities(
+            vec![a, b, c, d, e, f],
+            None::<&NoEntitiesSchema>,
+            TCComputation::ComputeNow,
+            Extensions::all_available(),
+        )
+        .expect("Failed to construct entities")
+        // Remove D from hierarchy
+        .remove_entities(vec![EntityUID::with_eid("D")], TCComputation::ComputeNow)
+        .expect("Failed to remove entities");
+        // Post-Removal Hierarchy
+        // F -> A
+        // F -> E -> C
+        // B
+
+        assert_matches!(entities.entity(&did), Dereference::NoSuchEntity);
+
+        let e = entities.entity(&eid).unwrap();
+        let f = entities.entity(&fid).unwrap();
+
+        // Assert the existence of these edges in the hierarchy
+        assert!(f.is_descendant_of(&aid));
+        assert!(f.is_descendant_of(&eid));
+        assert!(f.is_descendant_of(&cid));
+        assert!(e.is_descendant_of(&cid));
+
+        // Assert that there is no longer an edge from F to B
+        // as the only link was through D
+        assert!(!f.is_descendant_of(&bid));
+    }
 }
 
 // PANIC SAFETY: Unit Test Code
@@ -2037,12 +2134,11 @@ mod schema_based_parsing_tests {
                 r#"Action::"view""# => Some(Arc::new(Entity::new_with_attr_partial_value(
                     action.clone(),
                     [(SmolStr::from("foo"), PartialValue::from(34))],
+                    [].into_iter().collect(),
                     std::iter::once(r#"Action::"readOnly""#.parse().expect("valid uid")).collect(),
                     [],
                 ))),
-                r#"Action::"readOnly""# => Some(Arc::new(Entity::with_uid(
-                    r#"Action::"readOnly""#.parse().expect("valid uid"),
-                ))),
+                r#"Action::"readOnly""# => Some(Arc::new(Entity::with_uid(action.clone()))),
                 _ => None,
             }
         }
diff --git a/cedar-policy-core/src/entities/json/entities.rs b/cedar-policy-core/src/entities/json/entities.rs
index b555176b..8c40ec4f 100644
--- a/cedar-policy-core/src/entities/json/entities.rs
+++ b/cedar-policy-core/src/entities/json/entities.rs
@@ -31,7 +31,10 @@ use serde::{Deserialize, Serialize};
 use serde_with::serde_as;
 use smol_str::SmolStr;
 use std::sync::Arc;
-use std::{collections::HashMap, io::Read};
+use std::{
+    collections::{HashMap, HashSet},
+    io::Read,
+};
 
 #[cfg(feature = "wasm")]
 extern crate tsify;
@@ -416,7 +419,14 @@ impl<'e, 's, S: Schema> EntityJsonParser<'e, 's, S> {
                 })
             })
             .collect::<Result<_, JsonDeserializationError>>()?;
-        Ok(Entity::new(uid, attrs, parents, tags, self.extensions)?)
+        Ok(Entity::new(
+            uid,
+            attrs,
+            HashSet::new(),
+            parents,
+            tags,
+            self.extensions,
+        )?)
     }
 }
 
diff --git a/cedar-policy-core/src/entities/json/schema.rs b/cedar-policy-core/src/entities/json/schema.rs
index 7aad6650..ac33edd2 100644
--- a/cedar-policy-core/src/entities/json/schema.rs
+++ b/cedar-policy-core/src/entities/json/schema.rs
@@ -98,6 +98,7 @@ impl Schema for AllEntitiesNoAttrsSchema {
             action.clone(),
             [],
             HashSet::new(),
+            HashSet::new(),
             [],
         )))
     }
diff --git a/cedar-policy-core/src/evaluator.rs b/cedar-policy-core/src/evaluator.rs
index c5234c82..a5866f86 100644
--- a/cedar-policy-core/src/evaluator.rs
+++ b/cedar-policy-core/src/evaluator.rs
@@ -1245,15 +1245,15 @@ pub(crate) mod test {
         let grandparent = Entity::with_uid(EntityUID::with_eid("grandparent"));
         let mut sibling = Entity::with_uid(EntityUID::with_eid("sibling"));
         let unrelated = Entity::with_uid(EntityUID::with_eid("unrelated"));
-        child.add_ancestor(parent.uid().clone());
-        sibling.add_ancestor(parent.uid().clone());
-        parent.add_ancestor(grandparent.uid().clone());
+        child.add_indirect_ancestor(parent.uid().clone());
+        sibling.add_indirect_ancestor(parent.uid().clone());
+        parent.add_indirect_ancestor(grandparent.uid().clone());
         let mut child_diff_type = Entity::with_uid(
             EntityUID::with_eid_and_type("other_type", "other_child")
                 .expect("should be a valid identifier"),
         );
-        child_diff_type.add_ancestor(parent.uid().clone());
-        child_diff_type.add_ancestor(grandparent.uid().clone());
+        child_diff_type.add_indirect_ancestor(parent.uid().clone());
+        child_diff_type.add_indirect_ancestor(grandparent.uid().clone());
 
         Entities::from_entities(
             vec![
@@ -2577,6 +2577,7 @@ pub(crate) mod test {
             r#"Foo::"bar""#.parse().unwrap(),
             attrs,
             HashSet::new(),
+            HashSet::new(),
             [],
             Extensions::none(),
         )
@@ -4083,7 +4084,7 @@ pub(crate) mod test {
         //Alice has parent "Friends" but we don't add "Friends" to the slice
         let mut alice = Entity::with_uid(EntityUID::with_eid("Alice"));
         let parent = Entity::with_uid(EntityUID::with_eid("Friends"));
-        alice.add_ancestor(parent.uid().clone());
+        alice.add_indirect_ancestor(parent.uid().clone());
         let entities = Entities::from_entities(
             vec![alice],
             None::<&NoEntitiesSchema>,
diff --git a/cedar-policy-core/src/transitive_closure.rs b/cedar-policy-core/src/transitive_closure.rs
index 4991483d..6c1e3a0b 100644
--- a/cedar-policy-core/src/transitive_closure.rs
+++ b/cedar-policy-core/src/transitive_closure.rs
@@ -188,9 +188,9 @@ mod tests {
     fn basic() {
         // start with A -> B -> C
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("B"));
+        a.add_indirect_ancestor(EntityUID::with_eid("B"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("C"));
+        b.add_indirect_ancestor(EntityUID::with_eid("C"));
         let c = Entity::with_uid(EntityUID::with_eid("C"));
         let mut entities = HashMap::from([
             (a.uid().clone(), a),
@@ -220,9 +220,9 @@ mod tests {
         // same as basic(), but we put the entities in the map in the reverse
         // order, which shouldn't make a difference
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("B"));
+        a.add_indirect_ancestor(EntityUID::with_eid("B"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("C"));
+        b.add_indirect_ancestor(EntityUID::with_eid("C"));
         let c = Entity::with_uid(EntityUID::with_eid("C"));
         let mut entities = HashMap::from([
             (c.uid().clone(), c),
@@ -251,13 +251,13 @@ mod tests {
     fn deeper() {
         // start with A -> B -> C -> D -> E
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("B"));
+        a.add_indirect_ancestor(EntityUID::with_eid("B"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("C"));
+        b.add_indirect_ancestor(EntityUID::with_eid("C"));
         let mut c = Entity::with_uid(EntityUID::with_eid("C"));
-        c.add_ancestor(EntityUID::with_eid("D"));
+        c.add_indirect_ancestor(EntityUID::with_eid("D"));
         let mut d = Entity::with_uid(EntityUID::with_eid("D"));
-        d.add_ancestor(EntityUID::with_eid("E"));
+        d.add_indirect_ancestor(EntityUID::with_eid("E"));
         let e = Entity::with_uid(EntityUID::with_eid("E"));
         let mut entities = HashMap::from([
             (a.uid().clone(), a),
@@ -294,13 +294,13 @@ mod tests {
         // even when we aren't processing the entities in hierarchy order.)
         // start with foo -> bar -> baz -> ham -> eggs
         let mut foo = Entity::with_uid(EntityUID::with_eid("foo"));
-        foo.add_ancestor(EntityUID::with_eid("bar"));
+        foo.add_indirect_ancestor(EntityUID::with_eid("bar"));
         let mut bar = Entity::with_uid(EntityUID::with_eid("bar"));
-        bar.add_ancestor(EntityUID::with_eid("baz"));
+        bar.add_indirect_ancestor(EntityUID::with_eid("baz"));
         let mut baz = Entity::with_uid(EntityUID::with_eid("baz"));
-        baz.add_ancestor(EntityUID::with_eid("ham"));
+        baz.add_indirect_ancestor(EntityUID::with_eid("ham"));
         let mut ham = Entity::with_uid(EntityUID::with_eid("ham"));
-        ham.add_ancestor(EntityUID::with_eid("eggs"));
+        ham.add_indirect_ancestor(EntityUID::with_eid("eggs"));
         let eggs = Entity::with_uid(EntityUID::with_eid("eggs"));
         let mut entities = HashMap::from([
             (ham.uid().clone(), ham),
@@ -338,13 +338,13 @@ mod tests {
         //   \
         //     D -> E
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("B"));
-        a.add_ancestor(EntityUID::with_eid("D"));
+        a.add_indirect_ancestor(EntityUID::with_eid("B"));
+        a.add_indirect_ancestor(EntityUID::with_eid("D"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("C"));
+        b.add_indirect_ancestor(EntityUID::with_eid("C"));
         let c = Entity::with_uid(EntityUID::with_eid("C"));
         let mut d = Entity::with_uid(EntityUID::with_eid("D"));
-        d.add_ancestor(EntityUID::with_eid("E"));
+        d.add_indirect_ancestor(EntityUID::with_eid("E"));
         let e = Entity::with_uid(EntityUID::with_eid("E"));
         let mut entities = HashMap::from([
             (a.uid().clone(), a),
@@ -383,20 +383,20 @@ mod tests {
         //   \        /
         //     F -> G
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("B"));
-        a.add_ancestor(EntityUID::with_eid("F"));
+        a.add_indirect_ancestor(EntityUID::with_eid("B"));
+        a.add_indirect_ancestor(EntityUID::with_eid("F"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("C"));
-        b.add_ancestor(EntityUID::with_eid("D"));
+        b.add_indirect_ancestor(EntityUID::with_eid("C"));
+        b.add_indirect_ancestor(EntityUID::with_eid("D"));
         let c = Entity::with_uid(EntityUID::with_eid("C"));
         let mut d = Entity::with_uid(EntityUID::with_eid("D"));
-        d.add_ancestor(EntityUID::with_eid("E"));
+        d.add_indirect_ancestor(EntityUID::with_eid("E"));
         let mut e = Entity::with_uid(EntityUID::with_eid("E"));
-        e.add_ancestor(EntityUID::with_eid("H"));
+        e.add_indirect_ancestor(EntityUID::with_eid("H"));
         let mut f = Entity::with_uid(EntityUID::with_eid("F"));
-        f.add_ancestor(EntityUID::with_eid("G"));
+        f.add_indirect_ancestor(EntityUID::with_eid("G"));
         let mut g = Entity::with_uid(EntityUID::with_eid("G"));
-        g.add_ancestor(EntityUID::with_eid("E"));
+        g.add_indirect_ancestor(EntityUID::with_eid("E"));
         let h = Entity::with_uid(EntityUID::with_eid("H"));
         let mut entities = HashMap::from([
             (a.uid().clone(), a),
@@ -447,17 +447,17 @@ mod tests {
         //   \   /
         //     D --> F
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("B"));
-        a.add_ancestor(EntityUID::with_eid("C"));
-        a.add_ancestor(EntityUID::with_eid("D"));
+        a.add_indirect_ancestor(EntityUID::with_eid("B"));
+        a.add_indirect_ancestor(EntityUID::with_eid("C"));
+        a.add_indirect_ancestor(EntityUID::with_eid("D"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("C"));
-        b.add_ancestor(EntityUID::with_eid("E"));
+        b.add_indirect_ancestor(EntityUID::with_eid("C"));
+        b.add_indirect_ancestor(EntityUID::with_eid("E"));
         let mut c = Entity::with_uid(EntityUID::with_eid("C"));
-        c.add_ancestor(EntityUID::with_eid("E"));
+        c.add_indirect_ancestor(EntityUID::with_eid("E"));
         let mut d = Entity::with_uid(EntityUID::with_eid("D"));
-        d.add_ancestor(EntityUID::with_eid("C"));
-        d.add_ancestor(EntityUID::with_eid("F"));
+        d.add_indirect_ancestor(EntityUID::with_eid("C"));
+        d.add_indirect_ancestor(EntityUID::with_eid("F"));
         let e = Entity::with_uid(EntityUID::with_eid("E"));
         let f = Entity::with_uid(EntityUID::with_eid("F"));
         let mut entities = HashMap::from([
@@ -498,16 +498,16 @@ mod tests {
         //   \
         //     F -> G
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("F"));
+        a.add_indirect_ancestor(EntityUID::with_eid("F"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("C"));
+        b.add_indirect_ancestor(EntityUID::with_eid("C"));
         let c = Entity::with_uid(EntityUID::with_eid("C"));
         let mut d = Entity::with_uid(EntityUID::with_eid("D"));
-        d.add_ancestor(EntityUID::with_eid("E"));
+        d.add_indirect_ancestor(EntityUID::with_eid("E"));
         let mut e = Entity::with_uid(EntityUID::with_eid("E"));
-        e.add_ancestor(EntityUID::with_eid("H"));
+        e.add_indirect_ancestor(EntityUID::with_eid("H"));
         let mut f = Entity::with_uid(EntityUID::with_eid("F"));
-        f.add_ancestor(EntityUID::with_eid("G"));
+        f.add_indirect_ancestor(EntityUID::with_eid("G"));
         let g = Entity::with_uid(EntityUID::with_eid("G"));
         let h = Entity::with_uid(EntityUID::with_eid("H"));
         let mut entities = HashMap::from([
@@ -557,9 +557,9 @@ mod tests {
         //
         // A -> B -> B
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("B"));
+        a.add_indirect_ancestor(EntityUID::with_eid("B"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("B"));
+        b.add_indirect_ancestor(EntityUID::with_eid("B"));
         let mut entities = HashMap::from([(a.uid().clone(), a), (b.uid().clone(), b)]);
         // computing TC should succeed without panicking, infinitely recursing, etc
         compute_tc_internal(&mut entities);
@@ -599,12 +599,12 @@ mod tests {
         //        /
         // A -> B -> C -> A
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("B"));
+        a.add_indirect_ancestor(EntityUID::with_eid("B"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("C"));
-        b.add_ancestor(EntityUID::with_eid("D"));
+        b.add_indirect_ancestor(EntityUID::with_eid("C"));
+        b.add_indirect_ancestor(EntityUID::with_eid("D"));
         let mut c = Entity::with_uid(EntityUID::with_eid("C"));
-        c.add_ancestor(EntityUID::with_eid("A"));
+        c.add_indirect_ancestor(EntityUID::with_eid("A"));
         let d = Entity::with_uid(EntityUID::with_eid("D"));
         let mut entities = HashMap::from([
             (a.uid().clone(), a),
@@ -660,20 +660,20 @@ mod tests {
         //   \
         //     F -> G
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("F"));
+        a.add_indirect_ancestor(EntityUID::with_eid("F"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("C"));
+        b.add_indirect_ancestor(EntityUID::with_eid("C"));
         let mut c = Entity::with_uid(EntityUID::with_eid("C"));
-        c.add_ancestor(EntityUID::with_eid("B"));
+        c.add_indirect_ancestor(EntityUID::with_eid("B"));
         let mut d = Entity::with_uid(EntityUID::with_eid("D"));
-        d.add_ancestor(EntityUID::with_eid("E"));
+        d.add_indirect_ancestor(EntityUID::with_eid("E"));
         let mut e = Entity::with_uid(EntityUID::with_eid("E"));
-        e.add_ancestor(EntityUID::with_eid("H"));
+        e.add_indirect_ancestor(EntityUID::with_eid("H"));
         let mut f = Entity::with_uid(EntityUID::with_eid("F"));
-        f.add_ancestor(EntityUID::with_eid("G"));
+        f.add_indirect_ancestor(EntityUID::with_eid("G"));
         let g = Entity::with_uid(EntityUID::with_eid("G"));
         let mut h = Entity::with_uid(EntityUID::with_eid("H"));
-        h.add_ancestor(EntityUID::with_eid("D"));
+        h.add_indirect_ancestor(EntityUID::with_eid("D"));
         let mut entities = HashMap::from([
             (a.uid().clone(), a),
             (b.uid().clone(), b),
@@ -719,19 +719,19 @@ mod tests {
         //    ^               |
         //    |___------------
         let mut a = Entity::with_uid(EntityUID::with_eid("A"));
-        a.add_ancestor(EntityUID::with_eid("B"));
+        a.add_indirect_ancestor(EntityUID::with_eid("B"));
         let mut b = Entity::with_uid(EntityUID::with_eid("B"));
-        b.add_ancestor(EntityUID::with_eid("C"));
+        b.add_indirect_ancestor(EntityUID::with_eid("C"));
         let mut c = Entity::with_uid(EntityUID::with_eid("C"));
-        c.add_ancestor(EntityUID::with_eid("E"));
+        c.add_indirect_ancestor(EntityUID::with_eid("E"));
         let mut d = Entity::with_uid(EntityUID::with_eid("D"));
-        d.add_ancestor(EntityUID::with_eid("A"));
-        d.add_ancestor(EntityUID::with_eid("B"));
-        d.add_ancestor(EntityUID::with_eid("F"));
+        d.add_indirect_ancestor(EntityUID::with_eid("A"));
+        d.add_indirect_ancestor(EntityUID::with_eid("B"));
+        d.add_indirect_ancestor(EntityUID::with_eid("F"));
         let mut e = Entity::with_uid(EntityUID::with_eid("E"));
-        e.add_ancestor(EntityUID::with_eid("D"));
+        e.add_indirect_ancestor(EntityUID::with_eid("D"));
         let mut f = Entity::with_uid(EntityUID::with_eid("F"));
-        f.add_ancestor(EntityUID::with_eid("E"));
+        f.add_indirect_ancestor(EntityUID::with_eid("E"));
         let mut entities = HashMap::from([
             (a.uid().clone(), a),
             (b.uid().clone(), b),
diff --git a/cedar-policy-validator/src/entity_manifest/loader.rs b/cedar-policy-validator/src/entity_manifest/loader.rs
index 23f28af4..623235b9 100644
--- a/cedar-policy-validator/src/entity_manifest/loader.rs
+++ b/cedar-policy-validator/src/entity_manifest/loader.rs
@@ -296,7 +296,7 @@ pub(crate) fn load_entities(
         if let Some(entity) = entities.get_mut(&request.entity_id) {
             ancestors
                 .into_iter()
-                .for_each(|ancestor| entity.add_ancestor(ancestor));
+                .for_each(|ancestor| entity.add_parent(ancestor));
         }
     }
 
@@ -323,8 +323,8 @@ pub(crate) fn load_entities(
 // attributes may differ only if they are records, and then only in what nested
 // attributes they contain.
 fn merge_entities(e1: Entity, e2: Entity) -> Entity {
-    let (uid1, mut attrs1, ancestors1, tags1) = e1.into_inner();
-    let (uid2, attrs2, ancestors2, tags2) = e2.into_inner();
+    let (uid1, mut attrs1, ancestors1, parents1, tags1) = e1.into_inner();
+    let (uid2, attrs2, ancestors2, parents2, tags2) = e2.into_inner();
 
     assert_eq!(
         uid1, uid2,
@@ -334,6 +334,10 @@ fn merge_entities(e1: Entity, e2: Entity) -> Entity {
         ancestors1, ancestors2,
         "attempting to merge entities with different ancestors!"
     );
+    assert_eq!(
+        parents1, parents2,
+        "attempting to merge entities with different parents!"
+    );
     assert!(
         tags1.is_empty() && tags2.is_empty(),
         "attempting to merge entities with tags!"
@@ -366,7 +370,7 @@ fn merge_entities(e1: Entity, e2: Entity) -> Entity {
         }
     }
 
-    Entity::new_with_attr_partial_value(uid1, attrs1, ancestors1, [])
+    Entity::new_with_attr_partial_value(uid1, attrs1, ancestors1, parents1, [])
 }
 
 /// Merge two value for corresponding attributes in the slice.
diff --git a/cedar-policy-validator/src/entity_manifest/slicing.rs b/cedar-policy-validator/src/entity_manifest/slicing.rs
index adcc5a9b..f91da04e 100644
--- a/cedar-policy-validator/src/entity_manifest/slicing.rs
+++ b/cedar-policy-validator/src/entity_manifest/slicing.rs
@@ -206,6 +206,7 @@ impl AccessTrie {
             entity.uid().clone(),
             new_entity,
             Default::default(),
+            Default::default(),
             [], // TODO: entity slicing does not yet support tags
         ))
     }
diff --git a/cedar-policy-validator/src/schema.rs b/cedar-policy-validator/src/schema.rs
index 57785937..9b195b2c 100644
--- a/cedar-policy-validator/src/schema.rs
+++ b/cedar-policy-validator/src/schema.rs
@@ -883,6 +883,7 @@ impl ValidatorSchema {
             Entity::new_with_attr_partial_value_serialized_as_expr(
                 action_id.clone(),
                 action.attributes.clone(),
+                HashSet::new(),
                 action_ancestors.remove(action_id).unwrap_or_default(),
                 BTreeMap::new(), // actions cannot have entity tags
             )
@@ -2580,7 +2581,13 @@ pub(crate) mod test {
         let view_photo = actions.entity(&action_uid);
         assert_eq!(
             view_photo.unwrap(),
-            &Entity::new_with_attr_partial_value(action_uid, [], HashSet::new(), [])
+            &Entity::new_with_attr_partial_value(
+                action_uid,
+                [],
+                HashSet::new(),
+                HashSet::new(),
+                []
+            )
         );
     }
 
@@ -2615,26 +2622,16 @@ pub(crate) mod test {
             &Entity::new_with_attr_partial_value(
                 view_photo_uid,
                 [],
+                HashSet::new(),
                 HashSet::from([view_uid.clone(), read_uid.clone()]),
                 [],
             )
         );
 
-        let view_entity = actions.entity(&view_uid);
-        assert_eq!(
-            view_entity.unwrap(),
-            &Entity::new_with_attr_partial_value(
-                view_uid,
-                [],
-                HashSet::from([read_uid.clone()]),
-                []
-            )
-        );
-
         let read_entity = actions.entity(&read_uid);
         assert_eq!(
             read_entity.unwrap(),
-            &Entity::new_with_attr_partial_value(read_uid, [], HashSet::new(), [])
+            &Entity::new_with_attr_partial_value(read_uid, [], HashSet::new(), HashSet::new(), [])
         );
     }
 
@@ -2663,6 +2660,7 @@ pub(crate) mod test {
                 action_uid,
                 [("attr".into(), RestrictedExpr::val("foo"))],
                 HashSet::new(),
+                HashSet::new(),
                 [],
                 Extensions::none(),
             )
diff --git a/cedar-policy/CHANGELOG.md b/cedar-policy/CHANGELOG.md
index 789a1c06..73f6aaf2 100644
--- a/cedar-policy/CHANGELOG.md
+++ b/cedar-policy/CHANGELOG.md
@@ -15,6 +15,7 @@ Cedar Language Version: TBD
 
 ### Added
 
+- Added `Entities::remove_entities()` to remove `Entity`s from an `Entities` struct (resolving #701)
 - Implemented [RFC 53 (enumerated entity types)](https://github.com/cedar-policy/rfcs/blob/main/text/0053-enum-entities.md)  (#1377)
 
 ### Fixed
diff --git a/cedar-policy/src/api.rs b/cedar-policy/src/api.rs
index cfd03349..bbd25393 100644
--- a/cedar-policy/src/api.rs
+++ b/cedar-policy/src/api.rs
@@ -131,6 +131,7 @@ impl Entity {
         Self(ast::Entity::new_with_attr_partial_value(
             uid.into(),
             [],
+            [].into_iter().collect(),
             parents.into_iter().map(EntityUid::into).collect(),
             [],
         ))
@@ -151,6 +152,7 @@ impl Entity {
         Ok(Self(ast::Entity::new(
             uid.into(),
             attrs.into_iter().map(|(k, v)| (k.into(), v.0)),
+            [].into_iter().collect(),
             parents.into_iter().map(EntityUid::into).collect(),
             tags.into_iter().map(|(k, v)| (k.into(), v.0)),
             Extensions::all_available(),
@@ -231,7 +233,8 @@ impl Entity {
         HashMap<String, RestrictedExpression>,
         HashSet<EntityUid>,
     ) {
-        let (uid, attrs, ancestors, _) = self.0.into_inner();
+        let (uid, attrs, ancestors, mut parents, _) = self.0.into_inner();
+        parents.extend(ancestors);
 
         let attrs = attrs
             .into_iter()
@@ -253,7 +256,7 @@ impl Entity {
         (
             uid.into(),
             attrs,
-            ancestors.into_iter().map(Into::into).collect(),
+            parents.into_iter().map(Into::into).collect(),
         )
     }
 
@@ -366,7 +369,7 @@ impl Entities {
     }
 
     /// Transform the store into a partial store, where
-    /// attempting to dereference a non-existent `EntityUID` results in
+    /// attempting to dereference a non-existent `EntityUid` results in
     /// a residual instead of an error.
     #[doc = include_str!("../experimental_warning.md")]
     #[must_use]
@@ -445,6 +448,22 @@ impl Entities {
         ))
     }
 
+    /// Removes each of the [`EntityUid`]s in the iterator
+    /// from this [`Entities`] structure, re-computing the transitive
+    /// closure after removing all edges to/from the removed entities.
+    ///
+    /// Re-computing the transitive closure can be expensive, so it is
+    /// advised to not call this method in a loop.
+    pub fn remove_entities(
+        self,
+        entity_ids: impl IntoIterator<Item = EntityUid>,
+    ) -> Result<Self, EntitiesError> {
+        Ok(Self(self.0.remove_entities(
+            entity_ids.into_iter().map(|euid| euid.0),
+            cedar_policy_core::entities::TCComputation::ComputeNow,
+        )?))
+    }
+
     /// Parse an entities JSON file (in [&str] form) and add them into this
     /// [`Entities`] structure, re-computing the transitive closure
     ///
diff --git a/cedar-policy/src/proto/ast.rs b/cedar-policy/src/proto/ast.rs
index 7410bbdb..c6048f2d 100644
--- a/cedar-policy/src/proto/ast.rs
+++ b/cedar-policy/src/proto/ast.rs
@@ -192,6 +192,7 @@ impl From<&models::Entity> for ast::Entity {
             ast::EntityUID::from(v.uid.as_ref().expect("uid field should exist")),
             attrs,
             ancestors,
+            HashSet::new(),
             tags,
         )
     }
@@ -744,6 +745,7 @@ mod test {
             r#"Foo::"bar""#.parse().unwrap(),
             attrs,
             HashSet::new(),
+            HashSet::new(),
             BTreeMap::new(),
             Extensions::none(),
         )
diff --git a/cedar-policy/src/proto/entities.rs b/cedar-policy/src/proto/entities.rs
index e8ff9aed..825169bf 100644
--- a/cedar-policy/src/proto/entities.rs
+++ b/cedar-policy/src/proto/entities.rs
@@ -93,6 +93,7 @@ mod test {
                 r#"Foo::"bar""#.parse().unwrap(),
                 attrs.clone(),
                 HashSet::new(),
+                HashSet::new(),
                 BTreeMap::new(),
                 extensions::Extensions::none(),
             )
@@ -118,6 +119,7 @@ mod test {
                 r#"Bar::"foo""#.parse().unwrap(),
                 attrs,
                 HashSet::new(),
+                HashSet::new(),
                 BTreeMap::new(),
                 extensions::Extensions::none(),
             )


Test patch:
diff --git a/cedar-policy/src/tests.rs b/cedar-policy/src/tests.rs
index 64b5cc1d..6e1c6e32 100644
--- a/cedar-policy/src/tests.rs
+++ b/cedar-policy/src/tests.rs
@@ -3768,7 +3768,7 @@ mod schema_based_parsing_tests {
 
         // Both entity jsons are ok (the default TC setting is `ComputeNow`)
         assert!(Entities::from_json_value(entitiesjson_tc, Some(&schema)).is_ok());
-        assert!(Entities::from_json_value(entitiesjson_no_tc.clone(), Some(&schema)).is_ok());
+        Entities::from_json_value(entitiesjson_no_tc.clone(), Some(&schema)).unwrap();
 
         // Parsing will fail if the TC doesn't match
         let entitiesjson_bad = json!(