reauthorize only practically works with one unknown

[luxas]

Before opening, please confirm:

• I have searched for duplicate or closed issues.
• I have read the guide for submitting bug reports.
• I have done my best to include a minimal, self-contained set of instructions for consistently reproducing the issue.

Bug Category

Policy Evaluation

Describe the bug

Hi! Thanks for open sourcing Cedar, I'm really excited to use it in a Kubernetes (API) context. (And yes, I've been in contact with Micah already some time :D)

One of the gotchas I ran into the other day when experimenting with partial evaluation for multi-stage authorizations, when gradually supplying more data as needed, was that practically (usually) only one unknown is supported, as the partial evaluation stops whenever it encounters a residual on the LHS of an && (#1445)

So for a policy that refers to two unknowns (resource.first_unknown and resource.second_unknown) in the initial partial_evaluate stage, the following happens:

1. partial_evaluate without the two unknowns specified simplifies the policy the best it can, until it sees unknown("first_unknown") && resource.second_unknown && ... more concrete stuff, and feeds this into a partial response. If evaluation would have proceeded fully, or until an error occurs (Full Evaluation Option for Policy Expressions. #1445), then resource.second_unknown would have evaluated to unknown("second_unknown"), but it did not.
2. reauthorize with the two unknowns now specified first traverses the expression and maps unknowns to concrete values, but as partial_evaluate returned early, it is not known at this time that resource.second_unknown will evaluate to unknown("second_unknown"), so second_unknown is not populated from the reauthorize mappings, only unknown("first_unknown") is mapped.
3. partial_evaluate is invoked on the mapped expression, and is able to concretize the first unknown (let's assume, to true), thus proceeding to the second unknown, first now realizing that it is unknown. However, the reauthorize mappings are not part of this stage, thus must the PE terminate at the residual unknown("second_unknown") && ... more concrete stuff, although unknown("second_unknown") indeed was concretely known at reauthorize time.

I played with some quick ways to fix this, for my own learning and exploration of the Cedar codebase. In simplicity order:

1. A full evaluation option Full Evaluation Option for Policy Expressions. #1445 during the first partial_evaluate pass would make PE realize both resource fields are indeed unknowns. However, this has some limiations, especially around typing and errors.
2. Running expr.substitute and then partial_evaluate in a loop until N times in reauthorize works, but it's really hacky, inefficient, and won't work in a generic way (only until N unknowns)
3. Move unknown substitution to concrete values from reauthorize to partial_evaluate, that is, add an Option with the mappings hashmap as an argument to internal functions of partial_interpret, and substitute the unknowns on the fly when encountering one, allowing to resolve them directly.

(One detail, I here described resource.first_unknown and resource.second_unknown as two different attributes, but I think they can in fact just be two expr references to the same attribute.)

I have validated that option 3 works locally, and I can send a PR for it.
It could resolve the issue while RFC 95, indeed the long-term solution, is implemented.

I can send the PR later today, to show the sketch of it, to have something concrete to discuss about, but also I understand if we don't want to make the current partial evaluator more complex, and focus on the typed PE instead in the RFC 95 proposal.

Expected behavior

When reauthorize is called with mappings to resolve unknowns, all given unknowns will be concretized correctly.

Reproduction steps

See code snippet below, using latest Cedar version.

Code Snippet

fn test_reauthorize() -> Result<(), Box<dyn Error>> {
    let principal = EntityUid::from_type_name_and_id("partialeval::User".parse().unwrap(), "luxas".parse().unwrap());
    let action = EntityUid::from_type_name_and_id("partialeval::Action".parse().unwrap(), "update".parse().unwrap());
    let resource = EntityUid::from_type_name_and_id("partialeval::ResourceUpdate".parse().unwrap(), "f5ac263c-6ffe-43f1-819e-9278606a992e".parse().unwrap());
    
    let schema_str = r#"namespace partialeval {
    entity User = {
        "name": String,
    };
    type RequestAttributes = {
        "group": String,
        "resource": String,
        "namespace": String,
        "name": String,
    };
    type LabelAssignment = {
        "key": String,
        "value": String,
    };
    type LabelAssignments = Set<LabelAssignment>;
    entity ResourceUpdate = {
        "requestAttrs": RequestAttributes,
        "newlabels": LabelAssignments,
        "oldlabels": LabelAssignments,
    };
    action update appliesTo {
        principal: User,
        resource: ResourceUpdate,
    };
}"#;
    let (schema, _) = Schema::from_cedarschema_str(&schema_str).unwrap();

    let request: Request = Request::new(principal, action, resource, Context::empty(), Some(&schema)).expect("request validation error");

    let policies_str = r#"permit (
    principal is partialeval::User,
    action == partialeval::Action::"update",
    resource is partialeval::ResourceUpdate
)
when {
    resource.requestAttrs.group == "luxaslabs.com" && 
    resource.requestAttrs.resource == "foobars" &&
    resource.oldlabels.contains({"key": "owner", "value": principal.name}) &&
    resource.newlabels.contains({"key": "owner", "value": principal.name}) 
};"#;
    let policy_set = PolicySet::from_str(&policies_str).unwrap();
    
    let entities_str = r#"[
    {
        "uid": {
            "type": "partialeval::User",
            "id": "luxas"
        },
        "attrs": {
            "name": "luxas"
        },
        "parents": []
    },
    {
        "uid": {
            "type": "partialeval::ResourceUpdate",
            "id": "f5ac263c-6ffe-43f1-819e-9278606a992e"
        },
        "attrs": {
            "requestAttrs": {
                "group": "luxaslabs.com",
                "resource": "foobars",
                "namespace": "default",
                "name": "baz"
            },
            "oldlabels": { "__extn" : {
                "fn" : "unknown",
                "arg" : "resource.oldlabels"
            }},
            "newlabels": { "__extn" : {
                "fn" : "unknown",
                "arg" : "resource.newlabels"
            }}
        },
        "parents": []
    }
]"#;
    let entities = Entities::from_json_str(&entities_str, Some(&schema)).expect("entity parse error");
    
    let authorizer = Authorizer::new();

    let partialresp = authorizer.is_authorized_partial(&request, &policy_set, &entities);
    print_residuals(&partialresp);

    let mut m: HashMap<&str, &RestrictedExpression> = HashMap::new();
    let oldlabels = RestrictedExpression::from_str(r#"[
        {"key": "owner", "value": "luxas"}
    ]"#).unwrap();
    m.insert("resource.oldlabels", &oldlabels);
    let newlabels = RestrictedExpression::from_str(r#"[
        {"key": "owner", "value": "luxas"},
        {"key": "otherlabel", "value": "foobar"}
    ]"#).unwrap();
    m.insert("resource.newlabels", &newlabels);
    
    let partialresp2 = partialresp.reauthorize_with_bindings(m, &authorizer, &entities).unwrap();
    print_residuals(&partialresp2);

    assert_eq!(partialresp2.concretize().decision(), Decision::Allow);
    return Ok(())
}

fn print_residuals(partialresp: &PartialResponse) {
    match partialresp.decision() {
        Some(d) => println!("{:?}", d),
        None => {
            println!("Residuals:");
            for residual in partialresp.nontrivial_residuals() {
                println!("{residual}");
            }
        }
    }
}

Log output

// Put your output below this line
Residuals:
permit(
  principal,
  action,
  resource
) when {
  true && ((true && ((unknown("resource.oldlabels")).contains({"key": "owner", "value": "luxas"}))) && ((resource["newlabels"]).contains({"key": "owner", "value": principal["name"]})))
};
Residuals:
permit(
  principal,
  action,
  resource
) when {
  true && (true && (true && ((unknown("resource.newlabels")).contains({"key": "owner", "value": "luxas"}))))
};
thread 'test_reauthorize' panicked at cedar-policy/tests/public_interface.rs:129:5:
assertion `left == right` failed
  left: Deny
 right: Allow

Expected "Allowed" output.

Additional configuration

No response

Operating System

No response

Additional information and screenshots

No response