Traversing recursive documents

[nchengyeeshen]

I am wondering if it is possible to express a Rego rule to collect an entity and all its children (recursively).

Given the following input:

{
  "group": "parent"
}

I'm trying to get the following result:

{
  "groups": ["parent", "childA", "childB", "childC"]
}

Given the following data:

{
  "entities": [
    {
      "name": "parent",
      "relations": [
        {
          "type": "parentOf",
          "name": "childA"
        },
        {
          "type": "parentOf",
          "name": "childB"
        }
      ]
    },
    {
      "name": "childA",
      "relations": [
        {
          "type": "parentOf",
          "name": "childC"
        }
      ]
    },
    {
      "name": "childB",
      "relations": []
    },
    {
      "name": "childC",
      "relations": []
    }
  ]
}

• entities represents a data store of JSON documents, with each entry being an 'entity'.
• The relationships between each entity is stored in relations.
• Note that the nesting of the parentOf relation is arbitrary, we could have any number of levels of nesting.
• To access an entity, I have to make an API call to an HTTP service.

[srenatus]

Heya. This might not be possible in rego, as recursion is forbidden.

One workaround is to unroll the logic for a bounded depth, but it would need you to drop this constraint:

• Note that the nesting of the parentOf relation is arbitrary, we could have any number of levels of nesting.

Say, if you only allow nesting of level <= 3, you could write out the rules explicitly.

This is a start, to get the gist of it 👇

package play
import future.keywords

# direct decendants
result[entity.name] contains child if {
    some entity in input.entities
    some rel in entity.relations
    rel.type == "parentOf"
    child := rel.name
}

# one indirection
result[entity.name] contains child if {
    some entity in input.entities
    some rel in entity.relations
    rel.type == "parentOf"
    
    some other_entity in input.entities
    other_entity.name == rel.name
    some other_rel in other_entity.relations
    other_rel.type == "parentOf"
    child := other_rel.name
}

playground

[nchengyeeshen]

That clarifies things. Thank you!

[anderseknert]

@srenatus is probably right, as he often is :) But I wonder if this could be modeled for input to graph.reachable_paths? I'm sick at home right now, so my brain isn't going to handle graphs today, but could be worth looking into, I guess.

There are some known issues with that built-in function to be aware of though: open-policy-agent/opa#5871

[nchengyeeshen]

I was hoping to use graph.reachable_paths to express my authz rule. The problem was I couldn't build the graph data structure needed to pass in to graph.reachable_paths 😂

[charlieegan3]

Something like this might work: https://play.openpolicyagent.org/p/KOwkoqBLD3