Finding transitive closures of resource graphs (e.g. Cloud Formation)

transitive.jq

# Check whether the input array intersects the specified array of items
def intersects(items):
  reduce .[] as $item (false; . or (items | index($item)));

# Find all references to other resources
def references(ref):
  [.. | objects | ref | values];

# Remove entries whose keys do not match the predicate
def filter_keys(pred):
  with_entries(select(.key | pred));

# Find the transitive closure of the input resource graph given an array of seed ids
def transitive(seeds; selection; ref; boundary):
  . as $input |
  (seeds | map($input[.]) | references(ref) | flatten) as $seed_refs |
  $input | filter_keys(. as $key | selection | index($key) | not) |
  to_entries | map(
    .key as $id |
    references(ref) as $refs |
    if ($refs | intersects(seeds)) or ($seed_refs | index($id)) then $id else empty end
  ) as $additions |
  # ($additions | unique | debug) |
  if ($additions | length) > 0 then
    ((seeds + ($additions | map(select($input[.] | boundary | not)))) | unique) as $new_seeds |
    ((selection + $additions) | unique) as $new_selection |
    $input | transitive($new_seeds; $new_selection; ref; boundary)
  else
    $input | filter_keys(. as $key | selection | index($key))
  end;

# Find the transitive closure of the input resource graph given an array of seed ids
def transitive(seeds; ref; boundary):
  transitive(seeds; seeds; ref; boundary);