Repository: cedar-policy/cedar
Pull request #1474 (2025-02-15 11:04:58)

Correctly merge schema errors
## Description of changes
In https://github.com/cedar-policy/cedar/issues/1471 @hakanson demonstrates that current cedar schema validator sometimes fails to report all accumulated errors, and just returns the first one encountered.
Even though `ActionNotDefinedError`, `TypeNotDefinedError` and `SchemaError` are all capable of merging multiple instances of themselves into one, this behavior is not triggered when collect::<Result<_>> is used on an iterator producing such results.

I've reproduced this issue, and solved it using an iterator extension trait providing partition_nonempty().
This allowed simplifying some callsites where Itertools::partition_result was used to correctly get errors, and reducing the turbosfish type annotations needed in some cases.

## Issue #, if available
https://github.com/cedar-policy/cedar/issues/1471

## Checklist for requesting a review

The change in this PR is (choose one, and delete the other options):

- [x] A bug fix or other functionality change requiring a patch to `cedar-policy`.

I confirm that this PR (choose one, and delete the other options):

- [x] Does not update the CHANGELOG because my change does not significantly impact released code.

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/Cargo.lock b/Cargo.lock
index 090d5131..5b63c083 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -261,9 +261,9 @@ checksum = "37b2a672a2cb129a2e41c10b1224bb368f9f37a2b16b612598138befd7b37eb5"
 
 [[package]]
 name = "cc"
-version = "1.2.13"
+version = "1.2.14"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "c7777341816418c02e033934a09f20dc0ccaf65a5201ef8a450ae0105a573fda"
+checksum = "0c3d1b2e905a3a7b00a6141adb0e4c0bb941d11caf55349d863942a1cc44e3c9"
 dependencies = [
  "shlex",
 ]
@@ -478,9 +478,9 @@ dependencies = [
 
 [[package]]
 name = "clap"
-version = "4.5.28"
+version = "4.5.29"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3e77c3243bd94243c03672cb5154667347c457ca271254724f9f393aee1c05ff"
+checksum = "8acebd8ad879283633b343856142139f2da2317c96b05b4dd6181c61e2480184"
 dependencies = [
  "clap_builder",
  "clap_derive",
@@ -488,9 +488,9 @@ dependencies = [
 
 [[package]]
 name = "clap_builder"
-version = "4.5.27"
+version = "4.5.29"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1b26884eb4b57140e4d2d93652abfa49498b938b3c9179f9fc487b0acc3edad7"
+checksum = "f6ba32cbda51c7e1dfd49acc1457ba1a7dec5b64fe360e828acb13ca8dc9c2f9"
 dependencies = [
  "anstream",
  "anstyle",
@@ -794,9 +794,9 @@ dependencies = [
 
 [[package]]
 name = "equivalent"
-version = "1.0.1"
+version = "1.0.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "5443807d6dff69373d433ab9ef5378ad8df50ca6298caf15de6e52e24aaf54d5"
+checksum = "877a4ace8713b0bcf2a4e7eec82529c029f1d0619886d18145fea96c3ffe5c0f"
 
 [[package]]
 name = "errno"
@@ -814,12 +814,6 @@ version = "2.3.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "37909eebbb50d72f9059c3b6d82c0463f2ff062c9e95845c43a6c9c0355411be"
 
-[[package]]
-name = "fixedbitset"
-version = "0.4.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "0ce7134b9999ecaf8bcd65542e436736ef32ddca1b3e06094cb6ec5755203b80"
-
 [[package]]
 name = "fixedbitset"
 version = "0.5.7"
@@ -1108,15 +1102,6 @@ dependencies = [
  "either",
 ]
 
-[[package]]
-name = "itertools"
-version = "0.13.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "413ee7dfc52ee1a4949ceeb7dbc8a33f2d6c088194d9f922fb8318faf1f01186"
-dependencies = [
- "either",
-]
-
 [[package]]
 name = "itertools"
 version = "0.14.0"
@@ -1162,7 +1147,7 @@ dependencies = [
  "ena",
  "itertools 0.14.0",
  "lalrpop-util",
- "petgraph 0.7.1",
+ "petgraph",
  "pico-args",
  "regex",
  "regex-syntax",
@@ -1307,9 +1292,9 @@ dependencies = [
 
 [[package]]
 name = "miniz_oxide"
-version = "0.8.3"
+version = "0.8.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b8402cab7aefae129c6977bb0ff1b8fd9a04eb5b51efc50a70bea51cda0c7924"
+checksum = "b3b1c9bd4fe1f0f8b387f6eb9eb3b4a1aa26185e5750efb9140301703f62cd1b"
 dependencies = [
  "adler2",
 ]
@@ -1412,23 +1397,13 @@ dependencies = [
  "windows-targets",
 ]
 
-[[package]]
-name = "petgraph"
-version = "0.6.5"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b4c5cc86750666a3ed20bdaf5ca2a0344f9c67674cae0515bec2da16fbaa47db"
-dependencies = [
- "fixedbitset 0.4.2",
- "indexmap 2.7.0",
-]
-
 [[package]]
 name = "petgraph"
 version = "0.7.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "3672b37090dbd86368a4145bc067582552b29c27377cad4e0a306c97f9bd7772"
 dependencies = [
- "fixedbitset 0.5.7",
+ "fixedbitset",
  "indexmap 2.7.0",
 ]
 
@@ -1619,9 +1594,9 @@ dependencies = [
 
 [[package]]
 name = "prost"
-version = "0.13.4"
+version = "0.13.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "2c0fef6c4230e4ccf618a35c59d7ede15dea37de8427500f50aff708806e42ec"
+checksum = "2796faa41db3ec313a31f7624d9286acf277b52de526150b7e69f3debf891ee5"
 dependencies = [
  "bytes",
  "prost-derive",
@@ -1629,16 +1604,16 @@ dependencies = [
 
 [[package]]
 name = "prost-build"
-version = "0.13.4"
+version = "0.13.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "d0f3e5beed80eb580c68e2c600937ac2c4eedabdfd5ef1e5b7ea4f3fba84497b"
+checksum = "be769465445e8c1474e9c5dac2018218498557af32d9ed057325ec9a41ae81bf"
 dependencies = [
  "heck",
- "itertools 0.13.0",
+ "itertools 0.14.0",
  "log",
  "multimap",
  "once_cell",
- "petgraph 0.6.5",
+ "petgraph",
  "prettyplease",
  "prost",
  "prost-types",
@@ -1649,12 +1624,12 @@ dependencies = [
 
 [[package]]
 name = "prost-derive"
-version = "0.13.4"
+version = "0.13.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "157c5a9d7ea5c2ed2d9fb8f495b64759f7816c7eaea54ba3978f0d63000162e3"
+checksum = "8a56d757972c98b346a9b766e3f02746cde6dd1cd1d1d563472929fdd74bec4d"
 dependencies = [
  "anyhow",
- "itertools 0.13.0",
+ "itertools 0.14.0",
  "proc-macro2",
  "quote",
  "syn",
@@ -1662,18 +1637,18 @@ dependencies = [
 
 [[package]]
 name = "prost-types"
-version = "0.13.4"
+version = "0.13.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "cc2f1e56baa61e93533aebc21af4d2134b70f66275e0fcdf3cbe43d77ff7e8fc"
+checksum = "52c2c1bf36ddb1a1c396b3601a3cec27c2462e45f07c386894ec3ccf5332bd16"
 dependencies = [
  "prost",
 ]
 
 [[package]]
 name = "psm"
-version = "0.1.24"
+version = "0.1.25"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "200b9ff220857e53e184257720a14553b2f4aa02577d2ed9842d45d4b9654810"
+checksum = "f58e5423e24c18cc840e1c98370b3993c6649cd1678b4d24318bcf0a083cbe88"
 dependencies = [
  "cc",
 ]
@@ -2072,9 +2047,9 @@ dependencies = [
 
 [[package]]
 name = "smallvec"
-version = "1.13.2"
+version = "1.14.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3c5e1a9a646d36c3599cd173a41282daf47c44583ad367b8e6837255952e5c67"
+checksum = "7fcf8323ef1faaee30a44a340193b1ac6814fd9b7b4e88e9d4519a3e4abe1cfd"
 
 [[package]]
 name = "smol_str"
@@ -2088,9 +2063,9 @@ dependencies = [
 
 [[package]]
 name = "stacker"
-version = "0.1.17"
+version = "0.1.18"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "799c883d55abdb5e98af1a7b3f23b9b6de8ecada0ecac058672d7635eb48ca7b"
+checksum = "1d08feb8f695b465baed819b03c128dc23f57a694510ab1f06c77f763975685e"
 dependencies = [
  "cc",
  "cfg-if",
@@ -2151,9 +2126,9 @@ dependencies = [
 
 [[package]]
 name = "tempfile"
-version = "3.16.0"
+version = "3.17.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "38c246215d7d24f48ae091a2902398798e05d978b24315d6efbc00ede9a8bb91"
+checksum = "a40f762a77d2afa88c2d919489e390a12bdd261ed568e60cfa7e48d4e20f0d33"
 dependencies = [
  "cfg-if",
  "fastrand",
@@ -2309,9 +2284,9 @@ checksum = "0dd7358ecb8fc2f8d014bf86f6f638ce72ba252a2c3a2572f2a795f1d23efb41"
 
 [[package]]
 name = "toml_edit"
-version = "0.22.23"
+version = "0.22.24"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "02a8b472d1a3d7c18e2d61a489aee3453fd9031c33e4f55bd533f4a7adca1bee"
+checksum = "17b4795ff5edd201c7cd6dca065ae59972ce77d1b80fa0a84d94950ece7d1474"
 dependencies = [
  "indexmap 2.7.0",
  "toml_datetime",
@@ -2669,9 +2644,9 @@ checksum = "589f6da84c646204747d1270a2a5661ea66ed1cced2631d546fdfb155959f9ec"
 
 [[package]]
 name = "winnow"
-version = "0.7.1"
+version = "0.7.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "86e376c75f4f43f44db463cf729e0d3acbf954d13e22c51e26e4c264b4ab545f"
+checksum = "59690dea168f2198d1a3b0cac23b8063efcd11012f10ae4698f284808c8ef603"
 dependencies = [
  "memchr",
 ]
diff --git a/cedar-policy-core/Cargo.toml b/cedar-policy-core/Cargo.toml
index eee8611e..ee448c75 100644
--- a/cedar-policy-core/Cargo.toml
+++ b/cedar-policy-core/Cargo.toml
@@ -24,7 +24,7 @@ ref-cast = "1.0"
 rustc_lexer = "0.1"
 thiserror = "2.0"
 smol_str = { version = "0.3", features = ["serde"] }
-stacker = "0.1.15"
+stacker = "0.1.18"
 arbitrary = { version = "1", features = ["derive"], optional = true }
 miette = { version = "7.5.0", features = ["serde"] }
 nonempty = { version = "0.10.0", features = ["serialize"] }
diff --git a/cedar-policy-core/src/ast/policy_set.rs b/cedar-policy-core/src/ast/policy_set.rs
index 1a45df51..b69ee6ce 100644
--- a/cedar-policy-core/src/ast/policy_set.rs
+++ b/cedar-policy-core/src/ast/policy_set.rs
@@ -264,6 +264,103 @@ impl PolicySet {
         Ok(())
     }
 
+    /// Helper function for `merge_policyset` to check if the `PolicyID` pid
+    /// appears in this `PolicySet`'s links or templates.
+    fn policy_id_is_bound(&self, pid: &PolicyID) -> bool {
+        self.templates.contains_key(pid) || self.links.contains_key(pid)
+    }
+
+    /// Helper function for `merge_policyset` to construct a renaming
+    /// that would resolve any conflicting `PolicyID`s. We use the type parameter `T`
+    /// to allow this code to be applied to both Templates and Policies.
+    fn update_renaming<T>(
+        &self,
+        this_contents: &HashMap<PolicyID, T>,
+        other: &Self,
+        other_contents: &HashMap<PolicyID, T>,
+        renaming: &mut HashMap<PolicyID, PolicyID>,
+        start_ind: &mut u32,
+    ) where
+        T: PartialEq + Clone,
+    {
+        for (pid, ot) in other_contents {
+            if let Some(tt) = this_contents.get(pid) {
+                if tt != ot {
+                    let mut new_pid = PolicyID::from_string(format!("policy{}", start_ind));
+                    *start_ind += 1;
+                    while self.policy_id_is_bound(&new_pid) || other.policy_id_is_bound(&new_pid) {
+                        new_pid = PolicyID::from_string(format!("policy{}", start_ind));
+                        *start_ind += 1;
+                    }
+                    renaming.insert(pid.clone(), new_pid);
+                }
+            }
+        }
+    }
+
+    /// Merges this `PolicySet` with another `PolicySet`.
+    /// This `PolicySet` is modified while the other `PolicySet`
+    /// remains unchanged.
+    ///
+    /// The flag `rename_duplicates` controls the expected behavior
+    /// when a `PolicyID` in this and the other `PolicySet` conflict.
+    ///
+    /// When `rename_duplicates` is false, conflicting `PolicyID`s result
+    /// in a occupied `PolicySetError`.
+    ///
+    /// Otherwise, when `rename_duplicates` is true, conflicting `PolicyID`s from
+    /// the other `PolicySet` are automatically renamed to avoid conflict.
+    /// This renaming is returned as a Hashmap from the old `PolicyID` to the
+    /// renamed `PolicyID`.
+    pub fn merge_policyset(
+        &mut self,
+        other: &PolicySet,
+        rename_duplicates: bool,
+    ) -> Result<HashMap<PolicyID, PolicyID>, PolicySetError> {
+        // Check for conflicting policy ids. If there is a conflict either
+        // throw an error or construct a renaming (if `rename_duplicates` is true)
+        let mut min_id = 0;
+        let mut renaming = HashMap::new();
+        self.update_renaming(
+            &self.templates,
+            other,
+            &other.templates,
+            &mut renaming,
+            &mut min_id,
+        );
+        self.update_renaming(&self.links, other, &other.links, &mut renaming, &mut min_id);
+        // If `rename_dupilicates` is false, then throw an error if any renaming should happen
+        if !rename_duplicates {
+            if let Some(pid) = renaming.keys().next() {
+                return Err(PolicySetError::Occupied { id: pid.clone() });
+            }
+        }
+        // either there are no conflicting policy ids
+        // or we should rename conflicting policy ids (using renaming) to avoid conflicting policy ids
+        for (pid, other_template) in &other.templates {
+            let pid = renaming.get(pid).unwrap_or(pid);
+            self.templates.insert(pid.clone(), other_template.clone());
+        }
+        for (pid, other_policy) in &other.links {
+            let pid = renaming.get(pid).unwrap_or(pid);
+            self.links.insert(pid.clone(), other_policy.clone());
+        }
+        for (tid, other_template_link_set) in &other.template_to_links_map {
+            let tid = renaming.get(tid).unwrap_or(tid);
+            let mut this_template_link_set = self
+                .template_to_links_map
+                .remove(tid)
+                .unwrap_or(HashSet::new());
+            for pid in other_template_link_set {
+                let pid = renaming.get(pid).unwrap_or(pid);
+                this_template_link_set.insert(pid.clone());
+            }
+            self.template_to_links_map
+                .insert(tid.clone(), this_template_link_set);
+        }
+        Ok(renaming)
+    }
+
     /// Remove a static `Policy`` from the `PolicySet`.
     pub fn remove_static(
         &mut self,
@@ -670,6 +767,110 @@ mod test {
         }
     }
 
+    #[test]
+    fn policy_merge_no_conflicts() {
+        let p1 = parser::parse_policy(
+            Some(PolicyID::from_string("policy0")),
+            "permit(principal,action,resource);",
+        )
+        .expect("Failed to parse");
+        let p2 = parser::parse_policy(
+            Some(PolicyID::from_string("policy1")),
+            "permit(principal,action,resource) when { false };",
+        )
+        .expect("Failed to parse");
+        let p3 = parser::parse_policy(
+            Some(PolicyID::from_string("policy0")),
+            "permit(principal,action,resource);",
+        )
+        .expect("Failed to parse");
+        let p4 = parser::parse_policy(
+            Some(PolicyID::from_string("policy2")),
+            "permit(principal,action,resource) when { true };",
+        )
+        .expect("Failed to parse");
+        let mut pset1 = PolicySet::new();
+        let mut pset2 = PolicySet::new();
+        pset1.add_static(p1).expect("Failed to add!");
+        pset1.add_static(p2).expect("Failed to add!");
+        pset2.add_static(p3).expect("Failed to add!");
+        pset2.add_static(p4).expect("Failed to add!");
+        // should not conflict because p1 == p3
+        match pset1.merge_policyset(&pset2, false) {
+            Ok(_) => (),
+            Err(PolicySetError::Occupied { id }) => panic!(
+                "There should not have been an error! Unexpected conflict for id {}",
+                id
+            ),
+        }
+    }
+
+    #[test]
+    fn policy_merge_with_conflicts() {
+        let pid0 = PolicyID::from_string("policy0");
+        let pid1 = PolicyID::from_string("policy1");
+        let pid2 = PolicyID::from_string("policy2");
+        let p1 = parser::parse_policy(Some(pid0.clone()), "permit(principal,action,resource);")
+            .expect("Failed to parse");
+        let p2 = parser::parse_policy(
+            Some(pid1.clone()),
+            "permit(principal,action,resource) when { false };",
+        )
+        .expect("Failed to parse");
+        let p3 = parser::parse_policy(Some(pid1.clone()), "permit(principal,action,resource);")
+            .expect("Failed to parse");
+        let p4 = parser::parse_policy(
+            Some(pid2.clone()),
+            "permit(principal,action,resource) when { true };",
+        )
+        .expect("Failed to parse");
+        let mut pset1 = PolicySet::new();
+        let mut pset2 = PolicySet::new();
+        pset1.add_static(p1.clone()).expect("Failed to add!");
+        pset1.add_static(p2.clone()).expect("Failed to add!");
+        pset2.add_static(p3.clone()).expect("Failed to add!");
+        pset2.add_static(p4.clone()).expect("Failed to add!");
+        // should conclict on pid "policy1"
+        match pset1.merge_policyset(&pset2, false) {
+            Ok(_) => panic!("`pset1` and `pset2` should conflict for PolicyID `policy1`"),
+            Err(PolicySetError::Occupied { id }) => {
+                assert_eq!(id, PolicyID::from_string("policy1"));
+            }
+        }
+        // should not conflict because of auto-renaming of conflicting policies
+        match pset1.merge_policyset(&pset2, true) {
+            Ok(renaming) => {
+                // ensure `policy1` was renamed
+                let new_pid1 = match renaming.get(&pid1) {
+                    Some(new_pid1) => new_pid1,
+                    None => panic!("Error: `policy1` is a conflict and should be renamed"),
+                };
+                // ensure no other policy was renamed
+                assert_eq!(renaming.keys().len(), 1);
+                match pset1.get(&pid0) {
+                    Some(new_p1) => assert_eq!(Policy::from(p1), new_p1.clone()),
+                    None => (),
+                }
+                match pset1.get(&pid1) {
+                    Some(new_p2) => assert_eq!(Policy::from(p2), new_p2.clone()),
+                    None => (),
+                }
+                match pset1.get(new_pid1) {
+                    Some(new_p3) => assert_eq!(Policy::from(p3), new_p3.clone()),
+                    None => (),
+                }
+                match pset1.get(&pid2) {
+                    Some(new_p4) => assert_eq!(Policy::from(p4), new_p4.clone()),
+                    None => (),
+                }
+            }
+            Err(PolicySetError::Occupied { id }) => panic!(
+                "There should not have been an error! Unexpected conflict for id {}",
+                id
+            ),
+        }
+    }
+
     #[test]
     fn policy_conflicts() {
         let mut pset = PolicySet::new();
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-validator/Cargo.toml b/cedar-policy-validator/Cargo.toml
index 76cb744b..5299ae5a 100644
--- a/cedar-policy-validator/Cargo.toml
+++ b/cedar-policy-validator/Cargo.toml
@@ -21,7 +21,7 @@ itertools = "0.14"
 ref-cast = "1.0"
 unicode-security = "0.1.0"
 smol_str = { version = "0.3", features = ["serde"] }
-stacker = "0.1.15"
+stacker = "0.1.18"
 arbitrary = { version = "1", features = ["derive"], optional = true }
 lalrpop-util = { version = "0.22.1", features = ["lexer", "unicode"] }
 lazy_static = "1.4.0"
diff --git a/cedar-policy-validator/src/lib.rs b/cedar-policy-validator/src/lib.rs
index d551c703..88c83736 100644
--- a/cedar-policy-validator/src/lib.rs
+++ b/cedar-policy-validator/src/lib.rs
@@ -52,6 +52,7 @@ pub use str_checks::confusable_string_checks;
 pub mod cedar_schema;
 pub mod typecheck;
 use typecheck::Typechecker;
+mod partition_nonempty;
 pub mod types;
 
 /// Used to select how a policy will be validated.
diff --git a/cedar-policy-validator/src/partition_nonempty.rs b/cedar-policy-validator/src/partition_nonempty.rs
new file mode 100644
index 00000000..fc98007c
--- /dev/null
+++ b/cedar-policy-validator/src/partition_nonempty.rs
@@ -0,0 +1,27 @@
+use itertools::Itertools;
+use nonempty::NonEmpty;
+
+/// A trait for partitioning a collection of `Result`s into a collection of `Ok` values or a `NonEmpty` of `Err` values.
+pub(crate) trait PartitionNonEmpty<T, E> {
+    fn partition_nonempty<C>(self) -> std::result::Result<C, NonEmpty<E>>
+    where
+        C: Default + Extend<T>;
+}
+
+impl<I, T, E> PartitionNonEmpty<T, E> for I
+where
+    I: Iterator<Item = Result<T, E>>,
+{
+    fn partition_nonempty<C>(self) -> Result<C, NonEmpty<E>>
+    where
+        C: Default + Extend<T>,
+    {
+        let (oks, errs): (_, Vec<_>) = self.partition_result();
+
+        if let Some(errs) = NonEmpty::from_vec(errs) {
+            Err(errs)
+        } else {
+            Ok(oks)
+        }
+    }
+}
diff --git a/cedar-policy-validator/src/schema.rs b/cedar-policy-validator/src/schema.rs
index 9b195b2c..ad903f35 100644
--- a/cedar-policy-validator/src/schema.rs
+++ b/cedar-policy-validator/src/schema.rs
@@ -27,7 +27,6 @@ use cedar_policy_core::{
     parser::Loc,
     transitive_closure::compute_tc,
 };
-use itertools::Itertools;
 use namespace_def::EntityTypeFragment;
 use nonempty::NonEmpty;
 use serde::{Deserialize, Serialize};
@@ -40,6 +39,7 @@ use std::sync::Arc;
 use crate::{
     cedar_schema::SchemaWarning,
     json_schema,
+    partition_nonempty::PartitionNonEmpty,
     types::{Attributes, EntityRecordKind, OpenTag, Type},
 };
 
@@ -124,7 +124,7 @@ impl ValidatorSchemaFragment<ConditionalName, ConditionalName> {
                         extensions,
                     )
                 })
-                .collect::<Result<Vec<_>>>()?,
+                .partition_nonempty()?,
         ))
     }
 
@@ -138,16 +138,12 @@ impl ValidatorSchemaFragment<ConditionalName, ConditionalName> {
         self,
         all_defs: &AllDefs,
     ) -> Result<ValidatorSchemaFragment<InternalName, EntityType>> {
-        let (nsdefs, errs) = self
-            .0
+        self.0
             .into_iter()
             .map(|ns_def| ns_def.fully_qualify_type_references(all_defs))
-            .partition_result::<Vec<ValidatorNamespaceDef<InternalName, EntityType>>, Vec<SchemaError>, _, _>();
-        if let Some(errs) = NonEmpty::from_vec(errs) {
-            Err(SchemaError::join_nonempty(errs))
-        } else {
-            Ok(ValidatorSchemaFragment(nsdefs))
-        }
+            .partition_nonempty()
+            .map(ValidatorSchemaFragment)
+            .map_err(SchemaError::join_nonempty)
     }
 }
 
@@ -463,13 +459,10 @@ impl ValidatorSchema {
         // come later.)
         // This produces an intermediate form of schema fragment,
         // `ValidatorSchemaFragment<InternalName, EntityType>`.
-        let (fragments, errs) = fragments
+        let fragments: Vec<_> = fragments
             .into_iter()
             .map(|frag| frag.fully_qualify_type_references(&all_defs))
-            .partition_result::<Vec<ValidatorSchemaFragment<InternalName, EntityType>>, Vec<SchemaError>, _, _>();
-        if let Some(errs) = NonEmpty::from_vec(errs) {
-            return Err(SchemaError::join_nonempty(errs));
-        }
+            .partition_nonempty()?;
 
         // Now that all references are fully-qualified, we can build the aggregate
         // maps for common types, entity types, and actions, checking that nothing
@@ -528,7 +521,6 @@ impl ValidatorSchema {
                     .insert(name.clone());
             }
         }
-
         let mut entity_types = entity_type_fragments
             .into_iter()
             .map(|(name, entity_type)| -> Result<_> {
@@ -582,7 +574,7 @@ impl ValidatorSchema {
                     }
                 }
             })
-            .collect::<Result<HashMap<_, _>>>()?;
+            .partition_nonempty()?;
 
         let mut action_children = HashMap::new();
         for (euid, action) in action_fragments.iter() {
@@ -619,7 +611,7 @@ impl ValidatorSchema {
                     },
                 ))
             })
-            .collect::<Result<HashMap<_, _>>>()?;
+            .partition_nonempty()?;
 
         // We constructed entity types and actions with child maps, but we need
         // transitively closed descendants.
@@ -1345,7 +1337,7 @@ impl<'a> CommonTypeResolver<'a> {
                     attributes: BTreeMap::from_iter(
                         attributes
                             .into_iter()
-                            .map(|(attr, attr_ty)| {
+                            .map(|(attr, attr_ty)| -> Result<_> {
                                 Ok((
                                     attr,
                                     json_schema::TypeOfAttribute {
@@ -1355,7 +1347,7 @@ impl<'a> CommonTypeResolver<'a> {
                                     },
                                 ))
                             })
-                            .collect::<Result<Vec<(_, _)>>>()?,
+                            .partition_nonempty::<Vec<_>>()?,
                     ),
                     additional_attributes,
                 }),
@@ -1584,6 +1576,85 @@ pub(crate) mod test {
         }
     }
 
+    #[test]
+    fn test_from_schema_file_missing_parent_action() {
+        let src = json!({
+            "": {
+                "entityTypes": {
+                    "Test": {}
+                },
+                "actions": {
+                    "doTests": {
+                        "memberOf": [
+                            { "type": "Action", "id": "test1" },
+                            { "type": "Action", "id": "test2" }
+                        ]
+                    }
+                }
+            }
+        });
+        match ValidatorSchema::from_json_value(src, Extensions::all_available()) {
+            Err(SchemaError::ActionNotDefined(missing)) => {
+                assert_eq!(missing.0.len(), 2);
+            }
+            _ => panic!("Expected ActionNotDefined due to unknown actions in memberOf."),
+        }
+    }
+
+    #[test]
+    fn test_from_schema_file_undefined_types_in_common() {
+        let src = json!({
+            "": {
+                "commonTypes": {
+                    "My1": {"type": "What"},
+                    "My2": {"type": "Ev"},
+                    "My3": {"type": "Er"}
+                },
+                "entityTypes": {
+                    "Test": {}
+                },
+                "actions": {},
+            }
+        });
+        match ValidatorSchema::from_json_value(src, Extensions::all_available()) {
+            Err(SchemaError::TypeNotDefined(missing)) => {
+                assert_eq!(missing.undefined_types.len(), 3);
+            }
+            x => panic!(
+                "Expected TypeNotDefined due to unknown types in commonTypes, found: {:?}",
+                x
+            ),
+        }
+    }
+
+    #[test]
+    fn test_from_schema_file_undefined_entities_in_one_action() {
+        let src = json!({
+            "": {
+                "entityTypes": {
+                    "Test": {}
+                },
+                "actions": {
+                    "doTests": {
+                        "appliesTo": {
+                            "principalTypes": ["Usr", "Group"],
+                            "resourceTypes": ["Phoot"]
+                        }
+                    }
+                }
+            }
+        });
+        match ValidatorSchema::from_json_value(src, Extensions::all_available()) {
+            Err(SchemaError::TypeNotDefined(missing)) => {
+                assert_eq!(missing.undefined_types.len(), 3);
+            }
+            x => panic!(
+                "Expected TypeNotDefined due to unknown entities in appliesTo, found: {:?}",
+                x
+            ),
+        }
+    }
+
     // Undefined entity types "Grop", "Usr", "Phoot"
     #[test]
     fn test_from_schema_file_undefined_entities() {
@@ -2623,7 +2694,7 @@ pub(crate) mod test {
                 view_photo_uid,
                 [],
                 HashSet::new(),
-                HashSet::from([view_uid.clone(), read_uid.clone()]),
+                HashSet::from([view_uid, read_uid.clone()]),
                 [],
             )
         );
diff --git a/cedar-policy-validator/src/schema/action.rs b/cedar-policy-validator/src/schema/action.rs
index 973f39c9..e4dd7989 100644
--- a/cedar-policy-validator/src/schema/action.rs
+++ b/cedar-policy-validator/src/schema/action.rs
@@ -20,14 +20,13 @@ use cedar_policy_core::{
     ast::{self, EntityType, EntityUID, PartialValueSerializedAsExpr},
     transitive_closure::TCNode,
 };
-use itertools::Itertools;
-use nonempty::NonEmpty;
 use serde::Serialize;
 use smol_str::SmolStr;
 use std::collections::{BTreeMap, HashSet};
 
 use super::internal_name_to_entity_type;
 use crate::{
+    partition_nonempty::PartitionNonEmpty,
     schema::{AllDefs, SchemaError},
     types::{Attributes, Type},
     ConditionalName,
@@ -239,33 +238,31 @@ impl ValidatorApplySpec<ConditionalName> {
         self,
         all_defs: &AllDefs,
     ) -> Result<ValidatorApplySpec<ast::EntityType>, crate::schema::SchemaError> {
-        let (principal_apply_spec, principal_errs) = self
+        let principal_apply_spec = self
             .principal_apply_spec
             .into_iter()
             .map(|cname| {
                 let internal_name = cname.resolve(all_defs)?;
                 internal_name_to_entity_type(internal_name).map_err(Into::into)
             })
-            .partition_result::<_, Vec<SchemaError>, _, _>();
-        let (resource_apply_spec, resource_errs) = self
+            .partition_nonempty();
+        let resource_apply_spec = self
             .resource_apply_spec
             .into_iter()
             .map(|cname| {
                 let internal_name = cname.resolve(all_defs)?;
                 internal_name_to_entity_type(internal_name).map_err(Into::into)
             })
-            .partition_result::<_, Vec<SchemaError>, _, _>();
-        match (
-            NonEmpty::from_vec(principal_errs),
-            NonEmpty::from_vec(resource_errs),
-        ) {
-            (None, None) => Ok(ValidatorApplySpec {
+            .partition_nonempty();
+
+        match (principal_apply_spec, resource_apply_spec) {
+            (Ok(principal_apply_spec), Ok(resource_apply_spec)) => Ok(ValidatorApplySpec {
                 principal_apply_spec,
                 resource_apply_spec,
             }),
-            (Some(principal_errs), None) => Err(SchemaError::join_nonempty(principal_errs)),
-            (None, Some(resource_errs)) => Err(SchemaError::join_nonempty(resource_errs)),
-            (Some(principal_errs), Some(resource_errs)) => {
+            (Ok(_), Err(errs)) => Err(SchemaError::join_nonempty(errs)),
+            (Err(resource_errs), Ok(_)) => Err(SchemaError::join_nonempty(resource_errs)),
+            (Err(principal_errs), Err(resource_errs)) => {
                 let mut errs = principal_errs;
                 errs.extend(resource_errs);
                 Err(SchemaError::join_nonempty(errs))
diff --git a/cedar-policy-validator/src/schema/err.rs b/cedar-policy-validator/src/schema/err.rs
index e334b65c..c6702cbb 100644
--- a/cedar-policy-validator/src/schema/err.rs
+++ b/cedar-policy-validator/src/schema/err.rs
@@ -310,6 +310,24 @@ impl SchemaError {
     }
 }
 
+impl From<NonEmpty<SchemaError>> for SchemaError {
+    fn from(errs: NonEmpty<SchemaError>) -> Self {
+        Self::join_nonempty(errs)
+    }
+}
+
+impl From<NonEmpty<schema_errors::ActionNotDefinedError>> for SchemaError {
+    fn from(errs: NonEmpty<schema_errors::ActionNotDefinedError>) -> Self {
+        Self::ActionNotDefined(schema_errors::ActionNotDefinedError::join_nonempty(errs))
+    }
+}
+
+impl From<NonEmpty<schema_errors::TypeNotDefinedError>> for SchemaError {
+    fn from(errs: NonEmpty<schema_errors::TypeNotDefinedError>) -> Self {
+        Self::TypeNotDefined(schema_errors::TypeNotDefinedError::join_nonempty(errs))
+    }
+}
+
 /// Convenience alias
 pub type Result<T> = std::result::Result<T, SchemaError>;
 
@@ -431,6 +449,12 @@ pub mod schema_errors {
         }
     }
 
+    impl From<NonEmpty<TypeNotDefinedError>> for TypeNotDefinedError {
+        fn from(value: NonEmpty<TypeNotDefinedError>) -> Self {
+            Self::join_nonempty(value)
+        }
+    }
+
     /// Action resolution error
     //
     // CAUTION: this type is publicly exported in `cedar-policy`.
@@ -452,6 +476,12 @@ pub mod schema_errors {
         }
     }
 
+    impl From<NonEmpty<ActionNotDefinedError>> for ActionNotDefinedError {
+        fn from(value: NonEmpty<ActionNotDefinedError>) -> Self {
+            Self::join_nonempty(value)
+        }
+    }
+
     impl Display for ActionNotDefinedError {
         fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
             if self.0.len() == 1 {
diff --git a/cedar-policy-validator/src/schema/namespace_def.rs b/cedar-policy-validator/src/schema/namespace_def.rs
index e1c3334e..425d3ac6 100644
--- a/cedar-policy-validator/src/schema/namespace_def.rs
+++ b/cedar-policy-validator/src/schema/namespace_def.rs
@@ -37,6 +37,7 @@ use super::{internal_name_to_entity_type, AllDefs, ValidatorApplySpec};
 use crate::{
     err::{schema_errors::*, SchemaError},
     json_schema::{self, CommonTypeId, EntityTypeKind},
+    partition_nonempty::PartitionNonEmpty,
     types::{AttributeType, Attributes, OpenTag, Type},
     ActionBehavior, ConditionalName, RawName, ReferenceType,
 };
@@ -360,7 +361,7 @@ impl CommonTypeDefs<ConditionalName> {
                 .defs
                 .into_iter()
                 .map(|(k, v)| Ok((k, v.fully_qualify_type_references(all_defs)?)))
-                .collect::<Result<_, TypeNotDefinedError>>()?,
+                .partition_nonempty()?,
         })
     }
 }
@@ -436,7 +437,7 @@ impl EntityTypesDef<ConditionalName> {
                 .defs
                 .into_iter()
                 .map(|(k, v)| Ok((k, v.fully_qualify_type_references(all_defs)?)))
-                .collect::<Result<_, TypeNotDefinedError>>()?,
+                .partition_nonempty()?,
         })
     }
 }
@@ -538,7 +539,7 @@ impl EntityTypeFragment<ConditionalName> {
                 let parents: HashSet<InternalName> = parents
                     .into_iter()
                     .map(|parent| parent.resolve(all_defs))
-                    .collect::<Result<_, TypeNotDefinedError>>()?;
+                    .partition_nonempty()?;
                 // Fully qualify typenames appearing in `tags`
                 let fully_qual_tags = tags
                     .map(|tags| tags.fully_qualify_type_references(all_defs))
@@ -659,8 +660,8 @@ impl ActionsDef<ConditionalName, ConditionalName> {
             actions: self
                 .actions
                 .into_iter()
-                .map(|(k, v)| Ok((k, v.fully_qualify_type_references(all_defs)?)))
-                .collect::<Result<_, SchemaError>>()?,
+                .map(|(k, v)| v.fully_qualify_type_references(all_defs).map(|v| (k, v)))
+                .partition_nonempty()?,
         })
     }
 }
@@ -765,12 +766,8 @@ impl ActionFragment<ConditionalName, ConditionalName> {
             parents: self
                 .parents
                 .into_iter()
-                .map(|parent| {
-                    parent
-                        .fully_qualify_type_references(all_defs)
-                        .map_err(Into::into)
-                })
-                .collect::<Result<_, SchemaError>>()?,
+                .map(|parent| parent.fully_qualify_type_references(all_defs))
+                .partition_nonempty()?,
             attribute_types: self.attribute_types,
             attributes: self.attributes,
         })
diff --git a/cedar-policy/CHANGELOG.md b/cedar-policy/CHANGELOG.md
index 73f6aaf2..15367ccf 100644
--- a/cedar-policy/CHANGELOG.md
+++ b/cedar-policy/CHANGELOG.md
@@ -13,9 +13,14 @@ 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)
+- Added `PolicySet::merge_policyset()` to merge a `PolicySet` into another `PolicySet` struct (resolving #610)
 - 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/Cargo.toml b/cedar-policy/Cargo.toml
index 6ee2748f..3099e251 100644
--- a/cedar-policy/Cargo.toml
+++ b/cedar-policy/Cargo.toml
@@ -104,7 +104,7 @@ name = "deeply_nested_est"
 harness = false
 
 [package.metadata.docs.rs]
-features = ["partial-eval", "permissive-validate", "partial-validate", "level-validate", "entity-manifest", "datetime"]
+features = ["experimental"]
 rustdoc-args = ["--cfg", "docsrs"]
 
 [lints]
diff --git a/cedar-policy/src/api.rs b/cedar-policy/src/api.rs
index bbd25393..9c1f29b7 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
@@ -2230,6 +2237,73 @@ impl PolicySet {
         Ok(set)
     }
 
+    /// Helper function for `merge_policyset`
+    /// Merges two sets and avoids name clashes by using the provided
+    /// renaming. The type parameter `T` allows this code to be used for
+    /// both Templates and Policies.
+    fn merge_sets<T>(
+        this: &mut HashMap<PolicyId, T>,
+        other: &HashMap<PolicyId, T>,
+        renaming: &HashMap<PolicyId, PolicyId>,
+    ) where
+        T: PartialEq + Clone,
+    {
+        for (pid, ot) in other {
+            match renaming.get(&pid) {
+                Some(new_pid) => {
+                    this.insert(new_pid.clone(), ot.clone());
+                }
+                None => {
+                    if this.get(pid).is_none() {
+                        this.insert(pid.clone(), ot.clone());
+                    }
+                    // If pid is not in the renaming but is in both
+                    // this and other, then by assumption
+                    // the element at pid in this and other are equal
+                    // i.e., the renaming is expected to track all
+                    // conflicting pids.
+                }
+            }
+        }
+    }
+
+    /// Merges this `PolicySet` with another `PolicySet`.
+    /// This `PolicySet` is modified while the other `PolicySet`
+    /// remains unchanged.
+    ///
+    /// The flag `rename_duplicates` controls the expected behavior
+    /// when a `PolicyId` in this and the other `PolicySet` conflict.
+    ///
+    /// When `rename_duplicates` is false, conflicting `PolicyId`s result
+    /// in a `PolicySetError::AlreadyDefined` error.
+    ///
+    /// Otherwise, when `rename_duplicates` is true, conflicting `PolicyId`s from
+    /// the other `PolicySet` are automatically renamed to avoid conflict.
+    /// This renaming is returned as a Hashmap from the old `PolicyId` to the
+    /// renamed `PolicyId`.
+    pub fn merge_policyset(
+        &mut self,
+        other: &PolicySet,
+        rename_duplicates: bool,
+    ) -> Result<HashMap<PolicyId, PolicyId>, PolicySetError> {
+        match self.ast.merge_policyset(&other.ast, rename_duplicates) {
+            Ok(renaming) => {
+                let renaming: HashMap<PolicyId, PolicyId> = renaming
+                    .into_iter()
+                    .map(|(old_pid, new_pid)| (PolicyId::new(old_pid), PolicyId::new(new_pid)))
+                    .collect();
+                Self::merge_sets(&mut self.templates, &other.templates, &renaming);
+                Self::merge_sets(&mut self.policies, &other.policies, &renaming);
+                Ok(renaming)
+            }
+            Err(ast::PolicySetError::Occupied { id }) => Err(PolicySetError::AlreadyDefined(
+                policy_set_errors::AlreadyDefined {
+                    id: PolicyId::new(id),
+                },
+            )),
+        }
+    }
+
     /// Add an static policy to the `PolicySet`. To add a template instance, use
     /// `link` instead. This function will return an error (and not modify
     /// the `PolicySet`) if a template-linked policy is passed in.
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": []
             },
             {