Rego graph.reachable not printing leaf nodes

[philip-couling-oxa]

I'm not totally certain if this is a bug or "working as designed".

I'm having a lot of trouble getting graph.reachable to return leaf nodes when using contains rules to generate the graph.

The problem seems to be that graph.reachable() doesn't include any keys that are not contained in the graph map keys, even if they are referred to. So this

graph.reachable({"foo": {"bar"}, "bar": {"baz"}}, {"foo"})

results with just {"foo", "bar"} not {"foo", "bar", "baz"}. To get graph.reachable to return the right result, I need to add the empty set "baz": {}.

However I can't find a way to get rule_name[foo] contains bar if rules to generate empty sets like that. If the rule matches nothing the whole object doesn't exist.

Trivial Example

Goal

I want to evaluate the set of all permissions in a role

Data

{
    "relations": {
        "roles": {
            "role:admin": {
                "grants": ["permission:edit", "role:viewer"]
            },
            "role:viewer": {
                "organizations": "organization:acme",
                "grants": ["permission:view", "role:other"]
            }
        }
    }
}

Policy

package foo

# In the real world examples I have many similar rules for: inherits_from[] contains if
inherits_from[role_id] contains other if {
    some role_id, role_details in data.relations.roles
    some other in role_details.grants
}

effective_permissions = graph.reachable(inherits_from, {"role:admin"})

Actual result

{
    "effective_subjects": [
        "role:admin",
        "role:viewer"
    ],
    "inherits_from": {
        "role:admin": [
            "permission:edit",
            "role:viewer"
        ],
        "role:viewer": [
            "permission:view",
            "role:other"
        ]
    }
}

Desired result

    "effective_subjects": [
        "role:admin",
        "role:viewer",
        "permission:edit",
        "permission:view"
    ], ...

[charlieegan3]

Hey, thanks for the clear question. This is a good one.

Graphs passed to graph.reachable need to be a list of all nodes and the other nodes they have edges to. This list of edges might be an empty list.

I would set it up more like this:

package foo
# nodes is a set of unique roles and grant names
nodes contains node if {
	some role, role_data in data.relations.roles
	grant_names := {n | some n in role_data.grants}
	# a node is both the role itself and all the grant names
	some node in (grant_names | {role})
}

inherits_from_graph[node] := edges if {
	some node in nodes
	edges := {e | some e in data.relations.roles[node].grants}
}

effective_permissions := graph.reachable(inherits_from_graph, {"role:admin"})

I think the desired output is:

    "effective_permissions": [
        "permission:edit",
        "permission:view",
        "role:admin",
        "role:other",
        "role:viewer"
    ]

Since, "role:other" is inherited from viewer?

https://play.openpolicyagent.org/p/dmO2UWGA0n

[philip-couling-oxa]

Sadly that won't work because it's swapped a contains foo if rule for := foo if. When there are multiple similar rules, this will raise an error because more than one rule tries to define the complete set.

However I can see the approach is sound if we add two layers of indirection...

# In the real world examples I have many similar rules for: inherits_from[] contains if
inherits_from[role_id] contains other if {
    some role_id, role_details in data.relations.roles
    some other in role_details.grants
}

inherits_from_all_nodes contains node if {
	some key, references in inherits_from
	node in {{key} | references}
}
inherits_from_graph[node] := edges if {
	some node in nodes
	edges := {e | some e in data.relations.roles[node].grants}
}
effective_permissions := graph.reachable(inherits_from_graph, {"role:admin"})

This would be much easier if graph.reachable didn't require the empty sets. Perhaps there was a good design decision for that.

[philip-couling-oxa]

... I'll also add that I don't know what this does to performance.

I'm unclear on whether OPA constructs partial objects if it doesn't need the whole object. Strictly speaking about logic, the inherits_from_all_nodes must explore all nodes of the graph to find every possibly key key. Whereas inherits_from logically only needs to explore given role_id keys.

I'm not sure if OPA actually makes that optimisation.

[charlieegan3]

I think if you have a lot of work to re-organize your data into a suitable graph structure for OPA, it'd be best to have that work done when building the data bundle rather than in each OPA instance.

[philip-couling-oxa]

From a purely ideological standpoint, I'd have to push back on that idea.

That cuts against the separation of concerns. Rego & policy syntax are for defining the the policy rules: if this and that then "yes" otherwise "no". Data connectors are for supplying data about the real world from supporting systems. It's not the job of supporting systems nor data-connectors to go defining the policy rules. The mapping of relations to graph links is unmistakably a policy decision. Indeed my whole reason for assessing OPA is to avoid what some of the "Zanzibar inspired" systems keep trying to do which is to apply policy without a rules engine. (Google themselves didn't do Zanzibar without a rules engine </rant>)

That's not to say I disagree with data-connectors optimising the data; but it's one step to far to ask data-connectors to pre-calculate full graphs which are themselves a core part of the permissions rule. If the permissions rule changes, I shouldn't generally need to go changing the data-connector unless it's failing to supply information I need.

[charlieegan3]

I think that's fair enough, ideally additional processing would not be required.

Speaking from experience however, graph datasets can get quite large and other users going down this path in the past have needed to do some pre-processing on the data loaded into OPA in order to meet their performance targets.

It might be that with your data this is not an issue and so building the graph as part of the policy would be preferable.

We can chat about this in the issue though. open-policy-agent/opa#7396