Repository: cedar-policy/cedar
Pull request #1462 (2025-02-11 17:11:25)

Update ast type annotation to never eliminate expressions
Even when this should be possible, like when there are singleton boolean types in `if`, `&&`, and `||` expression, it can cause trouble for downstream analysis. In particular this change fixes a bug in entity manifests where a slice based on a manifest would not capture an attributes access in the guard of an `if` when the guard had a singleton boolean type.

Any downstream analysis that wants the reduced AST should instead inspect the types of expressions and handle any singleton boolean types as appropriate for that analysis.

## Description of changes

## Issue #, if available

## Checklist for requesting a review

The change in this PR is (choose one, and delete the other options):

- [ ] A breaking change requiring a major version bump to `cedar-policy` (e.g., changes to the signature of an existing API).
- [ ] A backwards-compatible change requiring a minor version bump to `cedar-policy` (e.g., addition of a new API).
- [ ] A bug fix or other functionality change requiring a patch to `cedar-policy`.
- [ ] A change "invisible" to users (e.g., documentation, changes to "internal" crates like `cedar-policy-core`, `cedar-validator`, etc.)
- [x] A change (breaking or otherwise) that only impacts unreleased or experimental code.

I confirm that this PR (choose one, and delete the other options):

- [ ] Updates the "Unreleased" section of the CHANGELOG with a description of my change (required for major/minor version bumps).
- [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.
- [ ] Requires updates, and I have made / will make these updates myself. (Please include in your description a timeline or link to the relevant PR in `cedar-spec`, and how you have tested that your updates are correct.)
- [ ] Requires updates, but I do not plan to make them in the near future. (Make sure that your changes are hidden behind a feature flag to mark them as experimental.)
- [ ] 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.
- [ ] Requires updates, and I have made / will make these updates myself. (Please include in your description a timeline or link to the relevant PR in [`cedar-docs`](https://github.com/cedar-policy/cedar-docs). PRs should be targeted at a `staging-X.Y` branch, not `main`.)
- [ ] I'm not sure how my change impacts the documentation. (Post your PR anyways, and we'll discuss in the comments.)



Patch:
diff --git a/cedar-policy-validator/src/entity_manifest/slicing.rs b/cedar-policy-validator/src/entity_manifest/slicing.rs
index 3f3e25e9..adcc5a9b 100644
--- a/cedar-policy-validator/src/entity_manifest/slicing.rs
+++ b/cedar-policy-validator/src/entity_manifest/slicing.rs
@@ -974,6 +974,65 @@ action BeSad appliesTo {
         );
     }
 
+    #[test]
+    fn test_slice_in_const_true_guard() {
+        let schema = ValidatorSchema::from_cedarschema_str(
+            "
+entity User = {
+  foo: String,
+  bar: String,
+  baz: String,
+};
+
+entity Document;
+
+action Read appliesTo {
+  principal: [User],
+  resource: [Document]
+};",
+            Extensions::all_available(),
+        )
+        .unwrap()
+        .0;
+
+        let pset = parser::parse_policyset(
+            r#"permit(principal, action, resource) when {
+                if (principal.foo == "foo") || true then
+                    principal.bar == "bar"
+                else
+                    principal.baz == "baz"
+            };"#,
+        )
+        .unwrap();
+        let manifest = compute_entity_manifest(&schema, &pset).unwrap();
+        let entities_json = serde_json::json!([{
+            "uid" : { "type" : "User", "id" : "oliver"},
+            "parents": [],
+            "attrs": {
+                "foo": "foo",
+                "bar": "bar",
+                "baz": "baz",
+            }
+        }]);
+        // We need `foo` to evaluate the guard even though we know it's always
+        // `true`. We need `bar` to evaluate the `then` branch. We don't need
+        // `baz` because we'll never evaluate the `else` branch.
+        let expected_json = serde_json::json!([{
+            "uid" : { "type" : "User", "id" : "oliver"},
+            "parents": [],
+            "attrs": {
+                "foo": "foo",
+                "bar": "bar",
+            }
+        }]);
+        expect_entity_slice_to(
+            entities_json.clone(),
+            expected_json.clone(),
+            &schema,
+            &manifest,
+        );
+    }
+
     #[test]
     fn test_slice_with_entity_alias_with_two_attrs() {
         let schema = ValidatorSchema::from_cedarschema_str(
diff --git a/cedar-policy-validator/src/typecheck.rs b/cedar-policy-validator/src/typecheck.rs
index 9918f485..33b51493 100644
--- a/cedar-policy-validator/src/typecheck.rs
+++ b/cedar-policy-validator/src/typecheck.rs
@@ -497,7 +497,16 @@ impl<'a> SingleEnvTypechecker<'a> {
 
                         ans_then.then_typecheck(|typ_then, then_capability| {
                             TypecheckAnswer::success_with_capability(
-                                typ_then,
+                                ExprBuilder::with_data(typ_then.data().clone())
+                                    .with_same_source_loc(e)
+                                    .ite(
+                                        typ_test,
+                                        typ_then.clone(),
+                                        // The type of the test expression is `True`, so we know the `else` branch
+                                        // will never be evaluated. We still need to put something here, so we use
+                                        // a copy of the `then` branch.
+                                        typ_then,
+                                    ),
                                 // The output capability of the whole `if` expression also
                                 // needs to contain the capability of the condition.
                                 then_capability.union(&test_capability),
@@ -511,7 +520,19 @@ impl<'a> SingleEnvTypechecker<'a> {
                         let ans_else = self.typecheck(prior_capability, else_expr, type_errors);
 
                         ans_else.then_typecheck(|typ_else, else_capability| {
-                            TypecheckAnswer::success_with_capability(typ_else, else_capability)
+                            TypecheckAnswer::success_with_capability(
+                                ExprBuilder::with_data(typ_else.data().clone())
+                                    .with_same_source_loc(e)
+                                    .ite(
+                                        typ_test,
+                                        // The type of the test expression is `False`, so we know the `then` branch
+                                        // will never be evaluated. We still need to put something here, so we use
+                                        // a copy of the `else` branch.
+                                        typ_else.clone(),
+                                        typ_else,
+                                    ),
+                                else_capability,
+                            )
                         })
                     } else {
                         // When we don't short circuit, the `then` and `else`
@@ -575,15 +596,15 @@ impl<'a> SingleEnvTypechecker<'a> {
                 );
                 ans_left.then_typecheck(|typ_left, capability_left| {
                     match typ_left.data() {
-                        // First argument is false, so short circuit the `&&` to
-                        // false _without_ typechecking the second argument.
-                        // Since the type of the `&&` is `false`, it is known to
-                        // always evaluate to `false` at run time. The `&&`
-                        // expression typechecks with an empty capability rather
-                        // than the capability of the lhs.
-                        // The right operand is not typechecked, so it is not
-                        // included in the type annotated AST.
-                        Some(Type::False) => TypecheckAnswer::success(typ_left),
+                        // LHS argument is false, so short circuit the `&&` to `False` _without_
+                        // typechecking the RHS.  We still need to build an annotated `&&` with
+                        // some RHS, so we use a literal `true`. The `&&` expression typechecks
+                        // with an empty capability rather than the capability of the lhs.
+                        Some(Type::False) => TypecheckAnswer::success(
+                            ExprBuilder::with_data(Some(Type::False))
+                                .with_same_source_loc(e)
+                                .and(typ_left, ExprBuilder::new().val(true)),
+                        ),
                         _ => {
                             // Similar to the `then` branch of an `if`
                             // expression, the rhs of an `&&` is typechecked
@@ -670,14 +691,18 @@ impl<'a> SingleEnvTypechecker<'a> {
                     |_| None,
                 );
                 ans_left.then_typecheck(|ty_expr_left, capability_left| match ty_expr_left.data() {
-                    // Contrary to `&&` where short circuiting did not permit
-                    // any capability, a capability can be maintained when short
-                    // circuiting `||`. We know the left operand is `true`, so
-                    // its capability is maintained. The right operand is not
-                    // evaluated, so its capability does not need to be considered.
-                    // The right operand is not typechecked, so it is not
-                    // included in the type annotated AST.
-                    Some(Type::True) => TypecheckAnswer::success(ty_expr_left),
+                    // LHS argument is true, so short circuit the `|| to `True` _without_
+                    // typechecking the RHS. We still need to build an annotated `||` with
+                    // some RHS, so we use a literal `true`.  Contrary to `&&`, we keep a
+                    // capability  when short circuiting `||`. The left operand is `true`,
+                    // so its capability is maintained. The right operand is not evaluated,
+                    // so its capability is not considered.
+                    Some(Type::True) => TypecheckAnswer::success_with_capability(
+                        ExprBuilder::with_data(Some(Type::True))
+                            .with_same_source_loc(e)
+                            .or(ty_expr_left, ExprBuilder::new().val(true)),
+                        capability_left,
+                    ),
                     _ => {
                         // The right operand of an `||` cannot be typechecked
                         // using the capability learned from the left because the
@@ -1718,12 +1743,7 @@ impl<'a> SingleEnvTypechecker<'a> {
         context: LubContext,
     ) -> TypecheckAnswer<'b> {
         match annotated_expr.data() {
-            Some(Type::False) => {
-                TypecheckAnswer::success(ExprBuilder::with_data(Some(Type::False)).val(false))
-            }
-            Some(Type::True) => {
-                TypecheckAnswer::success(ExprBuilder::with_data(Some(Type::True)).val(true))
-            }
+            Some(Type::True | Type::False) => TypecheckAnswer::success(annotated_expr),
             _ => match (lhs_ty, rhs_ty) {
                 (Some(lhs_ty), Some(rhs_ty)) => {
                     if let Err(lub_hint) =
@@ -1952,12 +1972,8 @@ impl<'a> SingleEnvTypechecker<'a> {
                 .then_typecheck(|type_of_in, _| {
                     if !self.mode.is_strict() {
                         TypecheckAnswer::success(type_of_in)
-                    } else if matches!(type_of_in.data(), Some(Type::False)) {
-                        TypecheckAnswer::success(
-                            ExprBuilder::with_data(Some(Type::False)).val(false),
-                        )
-                    } else if matches!(type_of_in.data(), Some(Type::True)) {
-                        TypecheckAnswer::success(ExprBuilder::with_data(Some(Type::True)).val(true))
+                    } else if matches!(type_of_in.data(), Some(Type::True | Type::False)) {
+                        TypecheckAnswer::success(type_of_in)
                     } else {
                         match (lhs_ty, rhs_ty) {
                             (Some(lhs_ty), Some(rhs_ty)) => {
diff --git a/cedar-policy/CHANGELOG.md b/cedar-policy/CHANGELOG.md
index c27fdeb2..0d15a330 100644
--- a/cedar-policy/CHANGELOG.md
+++ b/cedar-policy/CHANGELOG.md
@@ -24,6 +24,13 @@ Cedar Language Version: TBD
   that large inputs may result in stack overflows and crashing the process.
   On all platforms supported by `stacker` (Linux, macOS, ...), Cedar will
   continue to return the graceful error `RecursionLimit` instead of crashing.
+- Fixed a bug in the experimental `entity-manifest` feature. If an entity appears as
+  both a possible value for a scope variable and an entity literal, slicing
+  using entity manifests will now correctly capture all necessary attributes.
+- Fixed a bug in the experimental `entity-manifest` and `level-validate`
+  features. These features failed to consider any attribute accesses occurring
+  inside the guard of an `if` expression when guard expression had a singleton
+  boolean type.
 
 ## [4.3.1] - Coming soon
 Cedar Language Version: 4.2


Test patch:
diff --git a/cedar-policy-validator/src/typecheck/test/type_annotation.rs b/cedar-policy-validator/src/typecheck/test/type_annotation.rs
index 752205cd..dd7f578d 100644
--- a/cedar-policy-validator/src/typecheck/test/type_annotation.rs
+++ b/cedar-policy-validator/src/typecheck/test/type_annotation.rs
@@ -16,6 +16,7 @@
 
 use cool_asserts::assert_matches;
 use serde_json::json;
+use similar_asserts::assert_eq;
 use std::collections::HashSet;
 
 use cedar_policy_core::{
@@ -68,6 +69,14 @@ fn expr_typechecks_with_correct_annotation() {
             ExprBuilder::with_data(Some(Type::singleton_boolean(false))).val(false),
         ),
     );
+    assert_expr_has_annotated_ast(
+        &Expr::and(Expr::val(false), Expr::val(1)),
+        &ExprBuilder::with_data(Some(Type::singleton_boolean(false))).and(
+            ExprBuilder::with_data(Some(Type::singleton_boolean(false))).val(false),
+            // Doesn't contain `1` because we didn't typecheck this side
+            ExprBuilder::new().val(true),
+        ),
+    );
     assert_expr_has_annotated_ast(
         &Expr::or(Expr::greater(Expr::val(1), Expr::val(1)), Expr::val(true)),
         &ExprBuilder::with_data(Some(Type::singleton_boolean(true))).or(
@@ -78,6 +87,14 @@ fn expr_typechecks_with_correct_annotation() {
             ExprBuilder::with_data(Some(Type::singleton_boolean(true))).val(true),
         ),
     );
+    assert_expr_has_annotated_ast(
+        &Expr::or(Expr::val(true), Expr::val(1)),
+        &ExprBuilder::with_data(Some(Type::singleton_boolean(true))).or(
+            ExprBuilder::with_data(Some(Type::singleton_boolean(true))).val(true),
+            // Doesn't contain `1` because we didn't typecheck this side
+            ExprBuilder::new().val(true),
+        ),
+    );
     assert_expr_has_annotated_ast(
         &Expr::ite(
             Expr::less(Expr::val(1), Expr::val(0)),
@@ -93,6 +110,24 @@ fn expr_typechecks_with_correct_annotation() {
             ExprBuilder::with_data(Some(Type::primitive_string())).val("foo"),
         ),
     );
+    assert_expr_has_annotated_ast(
+        &Expr::ite(Expr::val(true), Expr::val("bar"), Expr::val("foo")),
+        &ExprBuilder::with_data(Some(Type::primitive_string())).ite(
+            ExprBuilder::with_data(Some(Type::True)).val(true),
+            ExprBuilder::with_data(Some(Type::primitive_string())).val("bar"),
+            // Contains `bar` instead of `foo` because we didn't typecheck the `else` branch
+            ExprBuilder::with_data(Some(Type::primitive_string())).val("bar"),
+        ),
+    );
+    assert_expr_has_annotated_ast(
+        &Expr::ite(Expr::val(false), Expr::val("bar"), Expr::val("foo")),
+        &ExprBuilder::with_data(Some(Type::primitive_string())).ite(
+            ExprBuilder::with_data(Some(Type::False)).val(false),
+            // Contains `foo` instead of `bar` because we didn't typecheck the `else` branch
+            ExprBuilder::with_data(Some(Type::primitive_string())).val("foo"),
+            ExprBuilder::with_data(Some(Type::primitive_string())).val("foo"),
+        ),
+    );
     assert_expr_has_annotated_ast(
         &Expr::not(Expr::val(false)),
         &ExprBuilder::with_data(Some(Type::singleton_boolean(true)))