Rule is recursive

[darapich92]

Dear everyone, I have a problem of dealing with the recursive in the rego. below is my code:

# Main rule to validate the input
validate := result if {
    constraints := input.pre_ConditionConstraint
	some constraint in constraints

    result := eval_conditions(constraint)
}

# Evaluate a list of conditions (recursively handles nested "and" and "or" operators)
eval_conditions(conditions) := result if {
	
	conditions.operator != ""
    # Base case: if the condition is a single UUID, evaluate it
    conditions.uuid
    # result := eval_condition(conditions)
	result := true
}

# Recursive case: Handle "and" operator (all conditions must be true)
eval_conditions(conditions) := result if {

	conditions.operator != ""
    conditions.operator == "http://www.w3.org/ns/odrl/operator/and"
	some condition in conditions.list
	print(condition.operator)
    
    # Recursively evaluate all conditions in the list
    results := eval_conditions(condition)

    # Ensure all results are true (logical AND)
    count(results) > 0  # Ensure we have values
    result := all_true(results)
}

# Recursive case: Handle "or" operator (at least one condition must be true)
eval_conditions(conditions) := result if {

	conditions.operator != ""
    conditions.operator == "http://www.w3.org/ns/odrl/operator/or"

	some condition in conditions.list

    # Recursively evaluate all conditions in the list
    results := eval_conditions(condition)

    # # Ensure at least one result is true (logical OR)
    count(results) > 0  # Ensure we have values
    result := any_true(results)
}

here is my input.json file

{ "pre_ConditionConstraint": [ { "operator": "http://www.w3.org/ns/odrl/operator/and", "list": [ { "operator": "http://www.w3.org/ns/odrl/operator/or", "list": [ { "uuid": "http://example.com/policy/mdr-chapter-1/1/1/a/cond" }, { "uuid": "http://example.com/policy/mdr-chapter-1/1/1/b/cond" }, { "uuid": "http://example.com/policy/mdr-chapter-1/1/1/c/cond" } ] }, { "uuid": "http://example.com/policy/mdr-chapter-1/2/1/cond" } ] } ] }

when executing the code, I always got the error that function of operator "or" and "and" is recursive while I tried to prevent if conditions.operator != "".

[anderseknert]

As you've noticed, Rego does not support recursion. A promise of Rego is that evaluation should be known to terminate, which is a promise that can't easily be made while supporting recursive (and potentially infinitely recursive) calls.

It's often possible to "unroll" recursion for at least some depth... but if you need to support unbounded recursion, Rego is probably not the right language for the use case.

[darapich92]

thank you very much for your answer! I thought that it is possible to implement recursive like another programming language.

[srenatus]

Hello, thanks for writing up your issue.

I'm afraid there's no direct fix here -- Rego does not allow recursion. It just doesn't, so whatever logic you add to make it "safe" is not going to make a difference. The analysis is static, it doesn't not look at your expressions, except to find out -- very cautiously, preferring false positives over false negatives -- if they could lead to recursion.

One thing that sometimes helps is unrolling a certain number of recursive calls. So if your constraint DSL is bounded, like, only allows a single layer of nesting, you could attempt something like

# level 0 conditions
eval_conditions(conditions) := result if {
	conditions.operator != ""
    	# Base case: if the condition is a single UUID, evaluate it
    	conditions.uuid
   	# result := eval_condition(conditions)
	result := true
}

# Recursive case: Handle "or" operator (at least one condition must be true)
eval_conditions(conditions) := result if {

	conditions.operator != ""
	conditions.operator == "http://www.w3.org/ns/odrl/operator/or"

	some condition in conditions.list

 	# Recursively evaluate all conditions in the list
 	results := eval_conditions_(condition)        # <---- call unrolled "recursive" function

	# Ensure at least one result is true (logical OR)
	count(results) > 0  # Ensure we have values
	result := any_true(results)
}

# level 1 unrolled
eval_conditions_(conditions) := result if {
	conditions.operator != ""
    	# Base case: if the condition is a single UUID, evaluate it
    	conditions.uuid
   	# result := eval_condition(conditions)
	result := true
}
# any other level 0 functions repeated
eval_conditions_(conditions) := result if {
...

If you want to support arbitrary levels of nesting, this approach will not work. ⚡

[darapich92]

Thank you for your answer. Actually, I have uncertainty structure of input.json. So, I will implement recursive using another language as a new layer for my rego.