Rego loop not terminating on first successful match

[ashwinhb]

Short description

We have a rego policy that iterates over a list of values and checks for each value to match an accepted state. Even after finding a successful accepted state, the iteration does not stop and continues for all the other values. We could not find a way to exit early to stop that iteration or break out of that loop the moment we encounter the first accepted state.

OPA details:
Version: 0.56.0
Build Commit: 016cb07
Build Timestamp: 2023-08-31T14:16:16Z
Build Hostname: 9f3376eb6d75
Go Version: go1.21.0
Platform: windows/amd64

Steps To Reproduce

1. Please find following files attached :
   a. Rego file: sample_rego.json
   b. Data: test_membership_ref_data_bundle.json, test_sample_all_children_data.json, test_sample_all_node_data.json, test_sample_all_parents_data.json

2. Use sample input :
   Endpoint: http://localhost:8181/v1/data/sample_rego/authz_check_for_node_access
   Input payload:
   {
   "input": {
   "request": {
   "userId": "user_id_1",
   "nodeName": "node_type_ABC",
   "nodeValue": "42189A",
   "subNodeName": "isDocument",
   "subNodeValue": "true"
   }
   }
   }

Expected behavior

Based on the given data a match occurs for node = C_42179 and the loop needs to terminate after that but the iteration continues until all nodes have been checked.

Additional context

Attached files provide sample data and rego.

sample_rego.json
test_sample_all_node_data.json
test_sample_all_children_data.json
test_sample_all_parents_data.json
test_sample_refdata.json

[srenatus]

It sounds like you're expecting this rule to exit on the first match?

authz_check_for_node_access = output {
        # Get all the assigned node values given a role and node name that user already has
        assigned_nodes := get_user_node_values(node_name)

        assigned_node = assigned_nodes[_]
        print("Assigned node to look into: ", assigned_node)

        # get all the nodes present in path(s) between source and target if a path exists
        nodes_in_path = get_all_covered_nodes(assigned_node, node_to_search)
        covered_node = nodes_in_path[_]

        # check if any of the node present in the path satisfies the given condition
        print("Covered nodes between source: ", assigned_node, " and target: ", node_name, " are: ", nodes_in_path)
        check_sub_nodes(covered_node, sub_node_name, sub_node_value) == true

        print("All the sub-nodes matched. Ending search now...")
        output := allowedResponse
} else = output {
        output := denyResponse
}

I'm afraid OPA can't do that. Early exist is only possible for rules with constant values, output is not constant.

OPA needs to check all over values to ensure that there's no conflict. Imagine for some other binding of the values inside the rule body output would be something else -- it would be an evaluation time conflict that OPA would error with.

However, the rule output can be made constant if you replace allowedResponse with true, and omit the else branch:

authz_check_for_node_access := true { 
   # ...
} # no else

and adapt your other code accordingly. Then the expectation of EE for that rule would be valid.

[srenatus]

@johanfylling is this the same pattern as the other bug we've been discussing around EE lately?

[johanfylling]

I believe this is one and the same, @srenatus.

We've already confirmed that this is an issue when doing multiple enumerations within the same rule body also when the rule has a constant result, so we should be able to adjust/simplify the provided example, and still see the behavior. I'll do that and report my findings here.

[johanfylling]

A fix for this issue has been merged to main, and will be part of the next OPA release.

Please note that Early Exit only applies to rules/functions with results known at compile-time. To have EE apply to the sample supplied in this issue, at least the "main" data.sample_rego.authz_check_for_node_access rule must be modified to not return a variable result, e.g.:

authz_check_for_node_access {
        # Get all the assigned node values given a role and node name that user already has
        assigned_nodes := get_user_node_values(node_name)

        assigned_node = assigned_nodes[_]
        print("Assigned node to look into: ", assigned_node)

        # get all the nodes present in path(s) between source and target if a path exists
        nodes_in_path = get_all_covered_nodes(assigned_node, node_to_search)
        covered_node = nodes_in_path[_]

        # check if any of the node present in the path satisfies the given condition
        print("Covered nodes between source: ", assigned_node, " and target: ", node_name, " are: ", nodes_in_path)
        check_sub_nodes(covered_node, sub_node_name, sub_node_value) == true

        print("All the sub-nodes matched. Ending search now...")
}