Repository: cedar-policy/cedar (rust)

Issue:
Allow identical duplicates when adding to `Entities`
### Category

User level API features/changes

### Describe the feature you'd like to request

Currently when adding entities to an `Entities` instance an error is returned if any of the added entities have the same `EntityUID` that is already present in the `Entities`. This is good to ensure that there are no accidental errors that would be missed by silently ignoring duplicates. However, there are times when both the principal and the resource may share some parent entities, in which case it may be difficult to know if there are going to be any duplicate entries. To prevent the duplicates from causing errors the list of entities to be added would have to be pre-filtered by the user to contain no duplicates, which means extra work in checking for duplicates and extra work in building a filtered list of entities before addition.

It would be good if there would be a way to add entities to an `Entities` instance which would allow duplicates, but only if the added entity is exactly the same as the entity already present. This may be made the default mode of adding entities, or it may be a separate API. By doing this internally inside the library, any performance penalty of extra duplicate checking and filtering is eliminated, and only the penalty of comparing entities for equivalence remains – a check which is a beneficial sanity check with relatively low cost.

### Describe alternatives you've considered

Alternative for the user is to not keep any `Entities` instances alive except momentarily. Any precomputed entity lists for principal and resource may be kept in data structures that are not handled by this library, deduplicated in those data structures and then simply converted to `Entities` just before the authorization check.

### Additional context

_No response_

### Is this something that you'd be interested in working on?

- [X] 👋 I may be able to implement this feature request
- [ ] ⚠️ This feature might incur a breaking change

Pull request description:
Allow identical duplicate entities
## Description of changes
* Changed Entities::add_entities and Entities::from_entities to ignore identical entities with the same EUID
* Refactored common code from Entities::add_entities and Entities::create_entity_map into private function
* Updated documentation to describe the new behavior
* Modified tests to reflect the new behavior
* Added tests for the new behavior

## Issue #, if available
Closes #613 

## 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] Does not require updates because my change does not impact the Cedar formal model or DRT infrastructure.


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/entities.rs b/cedar-policy-core/src/entities.rs
index 06cfdd35..2ed2b886 100644
--- a/cedar-policy-core/src/entities.rs
+++ b/cedar-policy-core/src/entities.rs
@@ -123,8 +123,10 @@ impl Entities {
     }
 
     /// Adds the [`crate::ast::Entity`]s in the iterator to this [`Entities`].
-    /// Fails if the passed iterator contains any duplicate entities with this structure,
-    /// or if any error is encountered in the transitive closure computation.
+    /// Fails if
+    ///  - there is a pair of non-identical entities in the passed iterator with the same Entity UID, or
+    ///  - there is an entity in the passed iterator with the same Entity UID as a non-identical entity in this structure, or
+    ///  - any error is encountered in the transitive closure computation.
     ///
     /// If `schema` is present, then the added entities will be validated
     /// against the `schema`, returning an error if they do not conform to the
@@ -145,14 +147,7 @@ impl Entities {
             if let Some(checker) = checker.as_ref() {
                 checker.validate_entity(&entity)?;
             }
-            match self.entities.entry(entity.uid().clone()) {
-                hash_map::Entry::Occupied(_) => {
-                    return Err(EntitiesError::duplicate(entity.uid().clone()))
-                }
-                hash_map::Entry::Vacant(vacant_entry) => {
-                    vacant_entry.insert(entity);
-                }
-            }
+            update_entity_map(&mut self.entities, entity)?;
         }
         match tc_computation {
             TCComputation::AssumeAlreadyComputed => (),
@@ -209,7 +204,9 @@ impl Entities {
     /// responsible for ensuring that TC and DAG hold before calling this method.
     ///
     /// # Errors
-    /// - [`EntitiesError::Duplicate`] if there are any duplicate entities in `entities`
+    /// - [`EntitiesError::Duplicate`] if there is a pair of non-identical entities in
+    ///   `entities` with the same Entity UID, or there is an entity in `entities` with the same
+    ///   Entity UID as a non-identical entity in this structure
     /// - [`EntitiesError::TransitiveClosureError`] if `tc_computation ==
     ///   TCComputation::EnforceAlreadyComputed` and the entities are not transitivly closed
     /// - [`EntitiesError::InvalidEntity`] if `schema` is not none and any entities do not conform
@@ -368,22 +365,40 @@ impl Entities {
     }
 }
 
-/// Create a map from EntityUids to Entities, erroring if there are any duplicates
+/// Creates a map from EntityUIDs to Entities, erroring if there is a pair of Entity
+/// instances with the same EntityUID that are not structurally equal.
 fn create_entity_map(
     es: impl Iterator<Item = Arc<Entity>>,
 ) -> Result<HashMap<EntityUID, Arc<Entity>>> {
-    let mut map = HashMap::new();
+    let mut map: HashMap<EntityUID, Arc<Entity>> = HashMap::new();
     for e in es {
-        match map.entry(e.uid().clone()) {
-            hash_map::Entry::Occupied(_) => return Err(EntitiesError::duplicate(e.uid().clone())),
-            hash_map::Entry::Vacant(v) => {
-                v.insert(e);
-            }
-        };
+        update_entity_map(&mut map, e)?;
     }
     Ok(map)
 }
 
+/// Adds an entry to the specified map associating the EntityUID of the specified entity
+/// to the specified entity. Checks whether there is an entity already in the map
+/// with the same EntityUID as the specified entity. If such an entity is found and is
+/// not structurally equal to the specified entity produces an error. Otherwise,
+/// if a structurally equal entity is found, the state of the map is unchanged.
+fn update_entity_map(map: &mut HashMap<EntityUID, Arc<Entity>>, entity: Arc<Entity>) -> Result<()> {
+    match map.entry(entity.uid().clone()) {
+        hash_map::Entry::Occupied(occupied_entry) => {
+            // Check whether the occupying entity is structurally equal to the
+            // entity being processed
+            if !entity.deep_eq(occupied_entry.get()) {
+                let entry = occupied_entry.remove_entry();
+                return Err(EntitiesError::duplicate(entry.0));
+            }
+        }
+        hash_map::Entry::Vacant(v) => {
+            v.insert(entity);
+        }
+    }
+    Ok(())
+}
+
 impl IntoIterator for Entities {
     type Item = Entity;
 
@@ -817,18 +832,58 @@ mod json_parsing_tests {
     }
 
     #[test]
-    fn add_duplicates_fail2() {
+    fn add_consistent_duplicates_in_iterator() {
         let parser: EntityJsonParser<'_, '_> =
             EntityJsonParser::new(None, Extensions::all_available(), TCComputation::ComputeNow);
+        // Create the entities to be added
         let new = serde_json::json!([
+            {"uid":{ "type" : "Test", "id" : "ruby" }, "attrs" : {}, "parents" : []},
             {"uid":{ "type" : "Test", "id" : "jeff" }, "attrs" : {}, "parents" : []},
             {"uid":{ "type" : "Test", "id" : "jeff" }, "attrs" : {}, "parents" : []}]);
+        let addl_entities = parser
+            .iter_from_json_value(new)
+            .unwrap_or_else(|e| panic!("{:?}", &miette::Report::new(e)))
+            .map(Arc::new);
+        // Create an initial structure
+        let original = simple_entities(&parser);
+        let original_size = original.entities.len();
+        // Add the new entities to an existing structure
+        let es = original
+            .add_entities(
+                addl_entities,
+                None::<&NoEntitiesSchema>,
+                TCComputation::ComputeNow,
+                Extensions::all_available(),
+            )
+            .unwrap();
+        // Check that the original conditions of the structure still hold
+        simple_entities_still_sane(&es);
+        // Check that jeff has been added
+        es.entity(&r#"Test::"jeff""#.parse().unwrap()).unwrap();
+        // Check that ruby has been added
+        es.entity(&r#"Test::"ruby""#.parse().unwrap()).unwrap();
+        // Check that the size of the structure increased by exactly two
+        assert_eq!(es.entities.len(), 2 + original_size);
+    }
+
+    #[test]
+    fn add_inconsistent_duplicates_in_iterator() {
+        let parser: EntityJsonParser<'_, '_> =
+            EntityJsonParser::new(None, Extensions::all_available(), TCComputation::ComputeNow);
+        // Create the entities to be added
+        let new = serde_json::json!([
+            {"uid":{ "type" : "Test", "id" : "ruby" }, "attrs" : {"location": "France"}, "parents" : []},
+            {"uid":{ "type" : "Test", "id" : "jeff" }, "attrs" : {"location": "France"}, "parents" : []},
+            {"uid":{ "type" : "Test", "id" : "jeff" }, "attrs" : {}, "parents" : []}]);
 
         let addl_entities = parser
             .iter_from_json_value(new)
             .unwrap_or_else(|e| panic!("{:?}", &miette::Report::new(e)))
             .map(Arc::new);
-        let err = simple_entities(&parser)
+        // Create an initial structure
+        let original = simple_entities(&parser);
+        // Add the new entities to an existing structure
+        let err = original
             .add_entities(
                 addl_entities,
                 None::<&NoEntitiesSchema>,
@@ -837,27 +892,81 @@ mod json_parsing_tests {
             )
             .err()
             .unwrap();
+        // Check that an error occurs indicating that an inconsistent duplicate was found
         let expected = r#"Test::"jeff""#.parse().unwrap();
         assert_matches!(err, EntitiesError::Duplicate(d) => assert_eq!(d.euid(), &expected));
     }
 
     #[test]
-    fn add_duplicates_fail1() {
+    fn add_consistent_duplicate() {
         let parser: EntityJsonParser<'_, '_> =
             EntityJsonParser::new(None, Extensions::all_available(), TCComputation::ComputeNow);
-        let new = serde_json::json!([{"uid":{ "type": "Test", "id": "alice" }, "attrs" : {}, "parents" : []}]);
+        // Create the entities to be added
+        let new = serde_json::json!([
+            {"uid":{ "type" : "Test", "id" : "ruby" }, "attrs" : {}, "parents" : []},
+            {"uid":{ "type" : "Test", "id" : "jeff" }, "attrs" : {}, "parents" : []}]);
         let addl_entities = parser
             .iter_from_json_value(new)
             .unwrap_or_else(|e| panic!("{:?}", &miette::Report::new(e)))
             .map(Arc::new);
-        let err = simple_entities(&parser).add_entities(
-            addl_entities,
-            None::<&NoEntitiesSchema>,
-            TCComputation::ComputeNow,
-            Extensions::all_available(),
-        );
-        let expected = r#"Test::"alice""#.parse().unwrap();
-        assert_matches!(err, Err(EntitiesError::Duplicate(d)) => assert_eq!(d.euid(), &expected));
+        // Create an initial structure
+        let json = serde_json::json!([
+            {"uid":{ "type" : "Test", "id" : "amy" }, "attrs" : {}, "parents" : []},
+            {"uid":{ "type" : "Test", "id" : "jeff" }, "attrs" : {}, "parents" : []}]);
+        let original = parser
+            .from_json_value(json)
+            .unwrap_or_else(|e| panic!("{:?}", &miette::Report::new(e)));
+        let original_size = original.entities.len();
+        // Add the new entities to an existing structure
+        let es = original
+            .add_entities(
+                addl_entities,
+                None::<&NoEntitiesSchema>,
+                TCComputation::ComputeNow,
+                Extensions::all_available(),
+            )
+            .unwrap();
+        // Check that jeff is still in the structure
+        es.entity(&r#"Test::"jeff""#.parse().unwrap()).unwrap();
+        // Check that amy is still in the structure
+        es.entity(&r#"Test::"amy""#.parse().unwrap()).unwrap();
+        // Check that ruby has been added
+        es.entity(&r#"Test::"ruby""#.parse().unwrap()).unwrap();
+        // Check that the size of the structure increased by exactly one
+        assert_eq!(es.entities.len(), 1 + original_size);
+    }
+
+    #[test]
+    fn add_inconsistent_duplicate() {
+        let parser: EntityJsonParser<'_, '_> =
+            EntityJsonParser::new(None, Extensions::all_available(), TCComputation::ComputeNow);
+        // Create the entities to be added
+        let new = serde_json::json!([
+            {"uid":{ "type" : "Test", "id" : "ruby" }, "attrs" : {}, "parents" : []},
+            {"uid":{ "type" : "Test", "id" : "jeff" }, "attrs" : {"location": "England"}, "parents" : []}]);
+        let addl_entities = parser
+            .iter_from_json_value(new)
+            .unwrap_or_else(|e| panic!("{:?}", &miette::Report::new(e)))
+            .map(Arc::new);
+        // Create an initial structure
+        let json = serde_json::json!([
+            {"uid":{ "type" : "Test", "id" : "amy" }, "attrs" : {}, "parents" : []},
+            {"uid":{ "type" : "Test", "id" : "jeff" }, "attrs" : {"location": "London"}, "parents" : []}]);
+        let original = parser
+            .from_json_value(json)
+            .unwrap_or_else(|e| panic!("{:?}", &miette::Report::new(e)));
+        let err = original
+            .add_entities(
+                addl_entities,
+                None::<&NoEntitiesSchema>,
+                TCComputation::ComputeNow,
+                Extensions::all_available(),
+            )
+            .err()
+            .unwrap();
+        // Check that an error occurs indicating that an inconsistent duplicate was found
+        let expected = r#"Test::"jeff""#.parse().unwrap();
+        assert_matches!(err, EntitiesError::Duplicate(d) => assert_eq!(d.euid(), &expected));
     }
 
     #[test]
diff --git a/cedar-policy-core/src/entities/err.rs b/cedar-policy-core/src/entities/err.rs
index e889718b..7e012698 100644
--- a/cedar-policy-core/src/entities/err.rs
+++ b/cedar-policy-core/src/entities/err.rs
@@ -30,7 +30,8 @@ pub enum EntitiesError {
     #[error("error during entity deserialization")]
     #[diagnostic(transparent)]
     Deserialization(#[from] crate::entities::json::err::JsonDeserializationError),
-    /// Error constructing the Entities collection as there is a duplicate Entity UID
+    /// Error constructing the Entities collection due to encountering two different entities
+    /// with the same Entity UID
     #[error(transparent)]
     #[diagnostic(transparent)]
     Duplicate(Duplicate),
diff --git a/cedar-policy-core/src/entities/json/entities.rs b/cedar-policy-core/src/entities/json/entities.rs
index 8c40ec4f..52c288d5 100644
--- a/cedar-policy-core/src/entities/json/entities.rs
+++ b/cedar-policy-core/src/entities/json/entities.rs
@@ -477,7 +477,7 @@ mod test {
     use cool_asserts::assert_matches;
 
     #[test]
-    fn reject_duplicates() {
+    fn reject_inconsistent_duplicates() {
         let json = serde_json::json!([
             {
                 "uid" : {
@@ -492,7 +492,7 @@ mod test {
                     "type" : "User",
                     "id" : "alice"
                 },
-                "attrs" : {},
+                "attrs" : {"location": "Greenland"},
                 "parents": []
             }
         ]);
diff --git a/cedar-policy/CHANGELOG.md b/cedar-policy/CHANGELOG.md
index 73f6aaf2..a51a676a 100644
--- a/cedar-policy/CHANGELOG.md
+++ b/cedar-policy/CHANGELOG.md
@@ -13,6 +13,10 @@ Starting with version 3.2.4, changes marked with a star (*) are _language breaki
 ## [Unreleased]
 Cedar Language Version: TBD
 
+### Changed
+
+- Changed `Entities::add_entities` and `Entities::from_entities` to ignore structurally equal entities with the same Entity UID.
+
 ### Added
 
 - Added `Entities::remove_entities()` to remove `Entity`s from an `Entities` struct (resolving #701)
diff --git a/cedar-policy/src/api.rs b/cedar-policy/src/api.rs
index bbd25393..1b1d65ca 100644
--- a/cedar-policy/src/api.rs
+++ b/cedar-policy/src/api.rs
@@ -428,7 +428,8 @@ impl Entities {
     /// Re-computing the transitive closure can be expensive, so it is advised
     /// to not call this method in a loop.
     /// ## Errors
-    /// - [`EntitiesError::Duplicate`] if there are any duplicate entities in `entities`
+    /// - [`EntitiesError::Duplicate`] if there is a pair of non-identical entities in `entities` with the same Entity UID,
+    ///   or there is an entity in `entities` with the same Entity UID as a non-identical entity in this structure
     /// - [`EntitiesError::InvalidEntity`] if `schema` is not none and any entities do not conform
     ///   to the schema
     pub fn add_entities(
@@ -478,7 +479,9 @@ impl Entities {
     /// Re-computing the transitive closure can be expensive, so it is advised
     /// to not call this method in a loop.
     /// ## Errors
-    /// - [`EntitiesError::Duplicate`] if there are any duplicate entities in `entities`
+    /// - [`EntitiesError::Duplicate`] if there is a pair of non-identical entities in
+    ///   `entities` with the same Entity UID, or there is an entity in `entities` with the
+    ///   same Entity UID as a non-identical entity in this structure
     /// - [`EntitiesError::InvalidEntity`] if `schema` is not none and any entities do not conform
     ///   to the schema
     /// - [`EntitiesError::Deserialization`] if there are errors while parsing the json
@@ -516,7 +519,9 @@ impl Entities {
     /// Re-computing the transitive closure can be expensive, so it is advised
     /// to not call this method in a loop.
     /// ## Errors
-    /// - [`EntitiesError::Duplicate`] if there are any duplicate entities in `entities`
+    /// - [`EntitiesError::Duplicate`] if there is a pair of non-identical entities in
+    ///   `entities` with the same Entity UID, or there is an entity in `entities` with the same
+    ///   Entity UID as a non-identical entity in this structure
     /// - [`EntitiesError::InvalidEntity`] if `schema` is not none and any entities do not conform
     ///   to the schema
     /// - [`EntitiesError::Deserialization`] if there are errors while parsing the json
@@ -555,7 +560,9 @@ impl Entities {
     /// to not call this method in a loop.
     ///
     /// ## Errors
-    /// - [`EntitiesError::Duplicate`] if there are any duplicate entities in `entities`
+    /// - [`EntitiesError::Duplicate`] if there is a pair of non-identical entities in `entities`
+    ///   with the same Entity UID, or there is an entity in `entities` with the same Entity UID as a
+    ///   non-identical entity in this structure
     /// - [`EntitiesError::InvalidEntity`] if `schema` is not none and any entities do not conform
     ///   to the schema
     /// - [`EntitiesError::Deserialization`] if there are errors while parsing the json
diff --git a/cedar-policy/src/ffi/is_authorized.rs b/cedar-policy/src/ffi/is_authorized.rs
index a5873e95..f46b488c 100644
--- a/cedar-policy/src/ffi/is_authorized.rs
+++ b/cedar-policy/src/ffi/is_authorized.rs
@@ -1446,7 +1446,7 @@ mod test {
     }
 
     #[test]
-    fn test_authorized_fails_duplicate_entity_uid() {
+    fn test_authorized_fails_inconsistent_duplicate_entity_uid() {
         let call = json!({
             "principal" : {
                 "type" : "User",
@@ -1468,7 +1468,7 @@ mod test {
                         "type" : "User",
                         "id" : "alice"
                     },
-                    "attrs": {},
+                    "attrs": {"location": "Greenland"},
                     "parents": []
                 },
                 {


Test patch:
diff --git a/cedar-policy/src/tests.rs b/cedar-policy/src/tests.rs
index 6e1c6e32..5d9a032d 100644
--- a/cedar-policy/src/tests.rs
+++ b/cedar-policy/src/tests.rs
@@ -3530,14 +3530,14 @@ mod schema_based_parsing_tests {
     }
 
     #[test]
-    fn entities_duplicates_fail() {
+    fn entities_inconsistent_duplicates_fail() {
         let json = serde_json::json!([
             {
                 "uid" : {
                     "type" : "User",
                     "id" : "alice"
                 },
-                "attrs" : {},
+                "attrs" : {"location": "Greenland"},
                 "parents": []
             },
             {