Module: Ruby::Rego::Builtins::Graph

Extended by:
RegistryHelpers
Defined in:
lib/ruby/rego/builtins/graph.rb

Overview

Graph-walk built-ins (graph.reachable, graph.reachable_paths), matching OPA. A graph is an object mapping each node to its neighbours (an array or set); the initial set is an array or set of nodes. A neighbour that is not itself a key in the graph is followed but not treated as a node (it has no edges), exactly as OPA’s implementation does.

Node identity uses Ruby Hash/Set membership. Like the rest of the gem (and unlike OPA), numbers 1 and 1.0 are distinct here, so a graph whose node labels mix integer and float forms of the same value can diverge from OPA — part of the known SetValue/ObjectValue numeric-normalisation gap. String-labelled graphs (the common case) are exact.

Constant Summary collapse

GRAPH_FUNCTIONS = 
{
  "graph.reachable" => { arity: 2, handler: :reachable },
  "graph.reachable_paths" => { arity: 2, handler: :reachable_paths }
}.freeze

Class Method Summary collapse

Methods included from RegistryHelpers

register_configured_functions

Class Method Details

.reachable(graph_value, initial_value) ⇒ Ruby::Rego::SetValue

The set of nodes reachable from the initial set. A node is included only when it is a key in the graph (a dangling neighbour is skipped); cycles terminate.

Parameters:

Returns:



42
43
44
45
46
 
# File 'lib/ruby/rego/builtins/graph.rb', line 42

def self.reachable(graph_value, initial_value)
  graph = object_arg(graph_value, "graph.reachable")
  queue = vertices(initial_value, "graph.reachable")
  SetValue.new(walk_reachable(graph, queue, Set.new(queue)))
end

.reachable_paths(graph_value, initial_value) ⇒ Ruby::Rego::SetValue

The set of all paths (arrays) walkable from the initial set, stopping at leaves and at the first repeated node on a path (cycle).

Parameters:

Returns:



72
73
74
75
76
77
78
79
80
81
 
# File 'lib/ruby/rego/builtins/graph.rb', line 72

def self.reachable_paths(graph_value, initial_value)
  graph = object_arg(graph_value, "graph.reachable_paths")
  paths = Set.new # @type var paths: Set[Array[untyped]]
  vertices(initial_value, "graph.reachable_paths").each do |node|
    next unless graph.key?(node)

    walk_roots(graph, node, paths)
  end
  SetValue.new(paths)
end

.register! ⇒ Ruby::Rego::Builtins::BuiltinRegistry

Returns:



28
29
30
31
32
 
# File 'lib/ruby/rego/builtins/graph.rb', line 28

def self.register!
  registry = BuiltinRegistry.instance
  register_configured_functions(registry, GRAPH_FUNCTIONS)
  registry
end