multimap-resolve.rego

package notes

# Part 1: multimap
# ================

# Some boilerplate.
servers = [
  {
    "name": "nginx",
    "tags": ["Prod", "Staging"]
  },
  {
    "name": "postfix",
    "tags": ["Staging", "Dev"]
  }
]

# Problem: in a number of rules; I would be able to easily obtain all
# servers tagged "Prod", all servers tagged "Dev", etc.
servers_by_tag = {tag: tag_servers |
  server_tags[tag]
  tag_servers = [server | server = servers[_]; server.tags[_] == tag]
}

# Utility for the above.
server_tags = {tag | tag = servers[_].tags[_]}

# Idea: multimap takes an array of pairs and builds an object of arrays.
servers_by_tag_2 = multimap([[tag, server] |
  server = servers[_]
  tag = server.tags[_]
])

# Problem: this implementation is a relatively slow since it needs to do a
# full traversal of the pairs list for each unique key, and another one to
# find all the keys.  I suspect this will become a bottleneck for us.

multimap(pairs) = ret {
  keys := {k | k = pairs[_][0]}
  ret := {k: vs |
    keys[k]
    vs := [v | pair = pairs[_]; pair[0] == k; v = pair[1]]
  }
}

# Part 2: resolve
# ===============

# Some more interesting boilerplate.  I opted for short boilerplate that really
# illustrates the problem concisely; a more concrete example would be "policies
# that can have aliases to other policies in a DAG".
policies = {
  "alpha": {"ref": "beta"},
  "beta": {"ref": "gamma"},
  "gamma": {"val": "Hello, world!"}
}

# Idea: offer a function like resolve as a built-in.
resolve(dag) = ret {
  ret := {k: resolve_term(dag, v) | v := dag[k]}
}

# Recurse up to a certain depth.
resolve_term   (g, t) = v {v = t.val} else = v {v = resolve_term_01(g, g[t.ref])}
resolve_term_01(g, t) = v {v = t.val} else = v {v = resolve_term_02(g, g[t.ref])}
resolve_term_02(g, t) = v {v = t.val} else = v {v = resolve_term_03(g, g[t.ref])}
resolve_term_03(g, t) = v {v = t.val} else = v {v = resolve_term_04(g, g[t.ref])}
resolve_term_04(g, t) = v {v = t.val} else = v {v = resolve_term_05(g, g[t.ref])}
resolve_term_05(g, t) = v {v = t.val} else = v {v = resolve_term_06(g, g[t.ref])}
resolve_term_06(g, t) = v {v = t.val} else = v {v = resolve_term_07(g, g[t.ref])}
resolve_term_07(g, t) = v {v = t.val} else = v {v = resolve_term_08(g, g[t.ref])}
resolve_term_08(g, t) = v {v = t.val} else = v {v = resolve_term_09(g, g[t.ref])}
resolve_term_09(g, t) = v {v = t.val} else = v {v = resolve_term_10(g, g[t.ref])}
resolve_term_10(g, t) = v {v = t.val}