partial eval: cover comprehensions that do not depend on unknowns

[tsandall]

Comprehensions that do not depend on unknown values should be partially evaluated. Today they are not, they are simply saved off. For example, given:

allow {
  # where ... does not depend on input
  rows = [[x, y] | ...]
  rows[i][0] == input.x
  rows[i][1] == input.y
}

This rule could be expanded out to:

allow {
  rows = <array literal>
  rows[0][0] == input.x
  rows[0][1] == input.y
}

allow {
  rows = <array literal>
  rows[1][0] == input.x
  rows[1][1] == input.y
}

...

allow {
  rows = <array literal>
  rows[...][0] == input.x
  rows[...][1] == input.y
}

For now, it should be fine to inline the comprehension result into the query. For comprehensions that don't depend on variables in the query, this is inefficient, but these comprehensions should be lifted out of the rule at compile time anyway.

[t83714]

@tsandall
We use partial eval to integrate with elastic search & dataset for data filtering.
As comprehensions will not be partially evaluated even not depend on unknown values, does that mean we should avoid using comprehensions for any policies for data filtering purpose?

Do we have any timelines on this feature?

[t83714]

@tsandall
More info on this one. For sample rule (allowRead) below, is there an alternative way to achieve the same logic without comprehensions?

### if not listed on controlledItems, assume allowed
controlledItems[item] {
    item := {
        "uri": "xxxx/xxx/a",
         # put as boolean value to make it simple. The actual value may depend on another rule
        "allow": false
    }
}

controlledItems[item] {
    item := {
        "uri": "xxxx/xxx/b",
        "allow": true
    }
}

default allowRead = false

allowRead {
    
    ## It's not a pattern
    contains(input.operationUri, "*") != true

    disallowedUris := [uri | uri := controlledItems[i].uri; controlledItems[i].allow = false]

    disallowedUris[_] != input.operationUri
    
    input.object.content.id == input.operationUri
}

allowRead {
    
    ## It's a pattern
    contains(input.operationUri, "*") == true

    disallowedUris := [uri | uri := controlledItems[i].uri; 
                             glob.match(input.operationUri, ["/"], uri) == true;
                             controlledItems[i].allow = false]

    count(disallowedUris) == 0
    # No matched disallowedUris found, thus, allow
}

allowRead {
    
    ## It's a pattern
    contains(input.operationUri, "*") == true

    disallowedUris := [uri | uri := controlledItems[i].uri; 
                             glob.match(input.operationUri, ["/"], uri) == true;
                             controlledItems[i].allow = false]

    count(disallowedUris) > 0
    
    input.object.content.id != disallowedUris[_]
}

[tsandall]

@t83714 here's an example that I think implements your intended policy: https://play.openpolicyagent.org/p/aiipr4eQm3

Note the playground example has an important difference: allowRead is true if input.object.content.id is not equal to ALL matching disallowed URIs. In your example above, input.object.content.id != disallowedUris[_] doesn't mean "for all", it means "for any", i.e., your example says allowRead is true if input.object.content.id is not equal to ANY matching disallowed URIs. This means that if input.object.content.id was "foo" and disallowdUris contained "foo" and "bar", allowRead would be true because "foo" is not equal to "bar".

We have an open issue to improve the docs to explicitly call out how to express "FOR ALL" vs. "FOR ANY" (the default): #1307

[t83714]

@tsandall

Thanks a lot for the example and your comments regarding "FOR ALL" vs. "FOR ANY"~

And thanks for the hint of using negation as an alternative way to implement the similar "For All" logic 👍

You example logic work very well, but I still have some issues around partial eval result when trying to implement this for our data filtering purpose.

• When I test it for partial eval in the terminal, I got the empty result (Please let me know If I did it incorrectly ):

OPA 0.10.7 (commit 0f39c27e, built at 2019-04-09T00:29:06Z)

Run 'help' to see a list of commands.

> unknown input.object.content
> data.play.allowRead with input as {
|   "operationUri": "xxxx/**"
| }
| 
+---------+---------------------------------------------------------------+
| Query 1 | data.play.allowRead with input as {"operationUri": "xxxx/**"} |
+---------+---------------------------------------------------------------+
> 

• The partial eval result through compile API looks correct 🎉 . But not ideal as it left unnecessary local var in the rule body.
  e.g. For the following request:

{
  "query": "data.play.allowRead == true",
  "input": {
  	"operationUri": "xxxx/**"
  },
  "unknowns": [
    "input.object.content"
  ]
}

I got the following rule body in support (the local var __local3__ & __local3__1 seems unnecessary):

{
  "body": [
    {
      "index": 0,
      "negated": true,
      "terms": [
        {
          "type": "ref",
          "value": [
            {
              "type": "var",
              "value": "eq"
            }
          ]
        },
        {
          "type": "var",
          "value": "__local3__1"
        },
        {
          "type": "string",
          "value": "xxxx/xxx/a"
        }
      ]
    },
    {
      "index": 1,
      "terms": [
        {
          "type": "ref",
          "value": [
            {
              "type": "var",
              "value": "eq"
            }
          ]
        },
        {
          "type": "var",
          "value": "__local3__"
        },
        {
          "type": "ref",
          "value": [
            {
              "type": "var",
              "value": "input"
            },
            {
              "type": "string",
              "value": "object"
            },
            {
              "type": "string",
              "value": "content"
            },
            {
              "type": "string",
              "value": "id"
            }
          ]
        }
      ]
    }
  ]
}

For our project, I think we can overcome it by making some further parsing & adjustment once received the partial eval result.

Not sure it's worth fixing and if so I can create a ticket for it 😄

Below is the full response (in case you need it):

{
    "result": {
        "queries": [
            [
                {
                    "index": 0,
                    "terms": [
                        {
                            "type": "ref",
                            "value": [
                                {
                                    "type": "var",
                                    "value": "equal"
                                }
                            ]
                        },
                        {
                            "type": "ref",
                            "value": [
                                {
                                    "type": "var",
                                    "value": "data"
                                },
                                {
                                    "type": "string",
                                    "value": "partial"
                                },
                                {
                                    "type": "string",
                                    "value": "play"
                                },
                                {
                                    "type": "string",
                                    "value": "allowRead"
                                }
                            ]
                        },
                        {
                            "type": "boolean",
                            "value": true
                        }
                    ]
                }
            ]
        ],
        "support": [
            {
                "package": {
                    "path": [
                        {
                            "type": "var",
                            "value": "data"
                        },
                        {
                            "type": "string",
                            "value": "partial"
                        },
                        {
                            "type": "string",
                            "value": "play"
                        }
                    ]
                },
                "rules": [
                    {
                        "head": {
                            "name": "allowRead",
                            "value": {
                                "type": "boolean",
                                "value": true
                            }
                        },
                        "body": [
                            {
                                "index": 0,
                                "negated": true,
                                "terms": [
                                    {
                                        "type": "ref",
                                        "value": [
                                            {
                                                "type": "var",
                                                "value": "eq"
                                            }
                                        ]
                                    },
                                    {
                                        "type": "var",
                                        "value": "__local3__1"
                                    },
                                    {
                                        "type": "string",
                                        "value": "xxxx/xxx/a"
                                    }
                                ]
                            },
                            {
                                "index": 1,
                                "terms": [
                                    {
                                        "type": "ref",
                                        "value": [
                                            {
                                                "type": "var",
                                                "value": "eq"
                                            }
                                        ]
                                    },
                                    {
                                        "type": "var",
                                        "value": "__local3__"
                                    },
                                    {
                                        "type": "ref",
                                        "value": [
                                            {
                                                "type": "var",
                                                "value": "input"
                                            },
                                            {
                                                "type": "string",
                                                "value": "object"
                                            },
                                            {
                                                "type": "string",
                                                "value": "content"
                                            },
                                            {
                                                "type": "string",
                                                "value": "id"
                                            }
                                        ]
                                    }
                                ]
                            }
                        ]
                    },
                    {
                        "default": true,
                        "head": {
                            "name": "allowRead",
                            "value": {
                                "type": "boolean",
                                "value": false
                            }
                        },
                        "body": [
                            {
                                "index": 0,
                                "terms": {
                                    "type": "boolean",
                                    "value": true
                                }
                            }
                        ]
                    }
                ]
            }
        ]
    }
}