Inconsistent responses from glob.match under certain conditions

[nickhiggs]

I haven't had the chance to dig too deeply into this yet but for certain policies the glob.match function appears to be returning inconsistent responses.

Expected Behavior

Consistent responses from:

for X in {1..20}; do go run main.go test ./policies; done

Actual Behavior

for X in {1..20}; do go run main.go test ./policies; done
PASS: 1/1
PASS: 1/1
PASS: 1/1
PASS: 1/1
PASS: 1/1
PASS: 1/1
data.repro.test_block_existing_namespace: FAIL (633.142µs)
--------------------------------------------------------------------------------
FAIL: 1/1
exit status 2
PASS: 1/1
data.repro.test_block_existing_namespace: FAIL (627.004µs)
--------------------------------------------------------------------------------
FAIL: 1/1
exit status 2
...

Steps to Reproduce the Problem

We first observed this on OPA v0.21.0 though I pulled down the latest version to verify it still exists. To reproduce it I put the following two files in the policies directory and ran for X in {1..20}; do go run main.go test ./policies; done

policy.rego

package repro

import input as req

write_methods = {
  "PUT": true,
  "POST": true,
  "PATCH": true,
  "DELETE": true,
}

update_methods = {
  "PUT": true,
  "PATCH": true,
  "DELETE": true,
}

deny["auth required on read"] {
  req.method == "GET"
  req.policy["anonymous-read"] == false
}

deny["cannot write to namespace"] {
  write_methods[req.method]
  not startswith(req.path, "/_auth/")
}

deny["cannot create namespace"] {
  req.method = "POST"
  glob.match("/_auth/*", ["/"], req.path)
  is_object(req.policy)
}

deny["cannot modify namespace"] {
  update_methods[req.method]
  startswith(req.path, "/_auth/")
}

policy_test.rego

package repro

test_block_existing_namespace {
  deny != set() with input as {
    "path": "/_auth/foo",
    "principals": ["admins"],
    "mechanism": "group",
    "method": "POST",
    "policy": {
      "owner": "buymore",
      "build": ["prefix:", "glob:*:main"]
    }
  }
}

[tsandall]

The problem is inside the rule indexer with how glob.match is handled. Here's a minimal repro:

package repro

deny {
	glob.match("foo/*", ["/"], input.x)
}

deny {
	input.x = x2
}

With this ordering, the indexer only returns the second deny rule. If the order is reversed, both rules are returned (as expected).

The problem is related to how the rule index was constructed.

Incorrect:

self:0xc0000be780 next:0xc0000be7e0
 self:0xc0000be7e0 input.x any:0xc0000be960 array:0xc0000be840
  self:0xc0000be960 1 rule(s): x.rego:7
  self:0xc0000be840 scalar("foo"):0xc0000be8a0
   self:0xc0000be8a0 any:0xc0000be900
    self:0xc0000be900 1 rule(s): x.rego:3

Correct:

self:0xc00008c7e0 next:0xc00008c840
 self:0xc00008c840 input.x any:0xc00008c8a0 array:0xc00008c900 mapper
  self:0xc00008c8a0 1 rule(s): x.rego:3
  self:0xc00008c900 scalar("foo"):0xc00008c960
   self:0xc00008c960 any:0xc00008c9c0
    self:0xc00008c9c0 1 rule(s): x.rego:7

When the index is built incorrectly, the value mapper is missing from the trie node. The value mapper is needed to translate the incoming value (which is a string) into a value that the index/trie node can match on. For more details see tsandall@096670b.