Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Comprehension indexing picks wrong candidates #3579

Closed
tsandall opened this issue Jun 22, 2021 · 0 comments · Fixed by #3709
Closed

Comprehension indexing picks wrong candidates #3579

tsandall opened this issue Jun 22, 2021 · 0 comments · Fixed by #3709
Assignees
Labels

Comments

@tsandall
Copy link
Member

tsandall commented Jun 22, 2021

The comprehension indexing feature is picking the wrong candidates for index keys (or is not restrictive enough) when there are nested comprehensions that close over variables in the outer-most body. For example:

p := {x: vs |
        some x
        q[x]

        vs := {y: vs2 |
                some y
                r[y]

                vs2 := {z |         # index created with 'y' as key
                        some z
                        s[z]
                        z[0] = x    # indexer excludes 'x' as a candidate
                        z[1] = y    # indexer includes 'y' as a candidate
                        # f(z, x, y)  # uncomment this line and comment previous two to see correct result
                }
        }
}

q["A"]
q["B"]
r["C"]
r["D"]
s[["A", "C"]]
s[["A", "D"]]
s[["B", "C"]]

In this case, the correct result for p is:

{
        "A": {
            "C": [
                [
                    "A",
                    "C"
                ]
            ],
            "D": [
                [
                    "A",
                    "D"
                ]
            ]
        },
        "B": {
            "C": [
                [
                    "B",
                    "C"
                ]
            ],
            "D": []
        }
    }

However, because the compiler decides to index with only y as the index key, the actual result is:

{
        "A": {
            "C": [
                [
                    "A",
                    "C"
                ],
                [
                    "B",
                    "C"
                ]
            ],
            "D": [
                [
                    "A",
                    "D"
                ]
            ]
        },
        "B": {
            "C": [
                [
                    "A",
                    "C"
                ],
                [
                    "B",
                    "C"
                ]
            ],
            "D": [
                [
                    "A",
                    "D"
                ]
            ]
        }
    }

This appears to be a bug in the comprehension index build here. The indexer should either exclude the nested comprehension entirely (safer but worse performance) or it should include the correct candidates in the key.

@tsandall tsandall added the bug label Jun 22, 2021
@tsandall tsandall changed the title Comprehension indexing not restrictive enough Comprehension indexing picks wrong candidates Jun 22, 2021
@tsandall tsandall self-assigned this Jun 23, 2021
@srenatus srenatus self-assigned this Aug 5, 2021
srenatus added a commit to srenatus/opa that referenced this issue Aug 16, 2021
Before, we'd only looked at the vars preceding the comprehension in the body
containing it. In the case of nested comprehensions, that would have excluded
the rule body OUTSIDE of the nested body.

Now, we'll accumulate candidates over multiple bodies -- capturing the ones
that had been missing before.

Fixes open-policy-agent#3579.

Signed-off-by: Stephan Renatus <[email protected]>
srenatus added a commit that referenced this issue Aug 17, 2021
Before, we'd only looked at the vars preceding the comprehension in the body
containing it. In the case of nested comprehensions, that would have excluded
the rule body OUTSIDE of the nested body.

Now, we'll accumulate candidates over multiple bodies -- capturing the ones
that had been missing before.

Fixes #3579.

Signed-off-by: Stephan Renatus <[email protected]>
jgchn pushed a commit to jgchn/opa that referenced this issue Aug 20, 2021
…olicy-agent#3709)

Before, we'd only looked at the vars preceding the comprehension in the body
containing it. In the case of nested comprehensions, that would have excluded
the rule body OUTSIDE of the nested body.

Now, we'll accumulate candidates over multiple bodies -- capturing the ones
that had been missing before.

Fixes open-policy-agent#3579.

Signed-off-by: Stephan Renatus <[email protected]>
dolevf pushed a commit to dolevf/opa that referenced this issue Nov 4, 2021
…olicy-agent#3709)

Before, we'd only looked at the vars preceding the comprehension in the body
containing it. In the case of nested comprehensions, that would have excluded
the rule body OUTSIDE of the nested body.

Now, we'll accumulate candidates over multiple bodies -- capturing the ones
that had been missing before.

Fixes open-policy-agent#3579.

Signed-off-by: Stephan Renatus <[email protected]>
Signed-off-by: Dolev Farhi <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
Archived in project
Development

Successfully merging a pull request may close this issue.

2 participants