Rete.Compiler.BetaGraph (Rete v0.1.0)

Copy Markdown View Source

The beta side of the network: a graph of Rete.Network.Node descriptions.

Internal. Each production's sorted left hand side is walked in order, adding one node per condition under the nodes the previous condition produced. Node 0 is an artificial root, so the graph has a single entry point.

Parents are a list. A disjunction adds each branch as its own chain and hands the union of the branch terminals to the next condition, so the branches re-converge on it. That is why the LHS is never flattened to disjunctive normal form: whole-LHS DNF is exponential in the number of disjunctions, and fanning out per condition is linear.

Sharing requires equality and the same parent set. Equality alone is a correctness bug: in a({:customer, cid}, {:order, cid, amt}) and b({:vendor, cid}, {:order, cid, amt}) the two order conditions are equal but sit under different parents, and sharing them would let a :vendor token join a :customer's elements. A terminal keys on the production's identity, so two rules with an identical LHS fire independently.

{:or, []} is false, and nothing is built for a path through one. A keyless condition after a false element would otherwise become an entry point the alpha index feeds, and an unsatisfiable rule would fire on every fact. See docs/design/network.md §4.

Summary

Types

id()

Node ids, allocated in insertion order.

t()

Functions

add_production(graph, production)

Adds one production, sharing nodes with everything already in the graph.

build(productions)

Adds every production to a new graph, in order.

children(beta_graph, id)

The children of a node, in the order they were added.

filter(beta_graph, predicate)

Every node satisfying a predicate, by ascending id.

new()

An empty graph containing only the root.

node(beta_graph, id)

The node under an id, or nil.

parents(beta_graph, id)

The parents of a node.

root_id()

The id of the artificial root every rule hangs from.

roots(graph)

Every node whose only parent is the root: the entry points of the beta side.

Types

id()

@type id() :: non_neg_integer()

Node ids, allocated in insertion order.

t()

@type t() :: %Rete.Compiler.BetaGraph{
  backward: %{required(id()) => MapSet.t(id())},
  forward: %{required(id()) => [id()]},
  next_id: id(),
  nodes: %{required(id()) => Rete.Network.Node.t()}
}

Functions

add_production(graph, production)

@spec add_production(t(), Rete.IR.Production.t()) :: t()

Adds one production, sharing nodes with everything already in the graph.

A production whose left hand side is unsatisfiable — one that contains a {:or, []} outside every branch that could avoid it — adds nothing at all.

build(productions)

@spec build([Rete.IR.Production.t()]) :: t()

Adds every production to a new graph, in order.

Order matters only for id allocation, and therefore only for readability: the same productions in the same order always produce the same ids.

children(beta_graph, id)

@spec children(t(), id()) :: [id()]

The children of a node, in the order they were added.

filter(beta_graph, predicate)

@spec filter(t(), (Rete.Network.Node.t() -> boolean())) :: [Rete.Network.Node.t()]

Every node satisfying a predicate, by ascending id.

new()

@spec new() :: t()

An empty graph containing only the root.

node(beta_graph, id)

@spec node(t(), id()) :: Rete.Network.Node.t() | nil

The node under an id, or nil.

parents(beta_graph, id)

@spec parents(t(), id()) :: MapSet.t(id())

The parents of a node.

root_id()

@spec root_id() :: id()

The id of the artificial root every rule hangs from.

roots(graph)

@spec roots(t()) :: [id()]

Every node whose only parent is the root: the entry points of the beta side.