Topological ordering of the left hand side of a production.
Internal. A rule reads best in the order the author thought of it. But the network needs an order where every join already has its keys in the token. This phase reorders the LHS, so a condition comes after the conditions that bind what it needs:
defrule r({:order, amt} when amt > t, {:threshold, t})sorts into {:threshold, t}, {:order, amt} when amt > t.
A condition needs only what it reads and cannot supply itself. The sort drops
_-prefixed names, since no ordering can satisfy one. What a condition binds comes
from Rete.IR.lhs_bindings/1, so this phase and the production's :bind cannot drift
apart.
Each pass takes every condition satisfiable right now, in author order. So equally
satisfiable conditions keep the order they were written in, and two rules sharing a
prefix still share their nodes. Collections and tests are deferred. A collection placed
too early would propagate [] before the conditions that would have filled it are
joined.
This runs after Rete.DSL.Normalize, because a Rete.IR.Gate reaching it raises. It
runs before Rete.DSL.Bindings, which reads :join_bind off the final order. See
docs/design/ir.md §1.
Summary
Functions
The variables an element needs bound before it can be placed.
Sorts the left hand side of a production topologically.
Types
Functions
@spec needs(Rete.IR.element()) :: vars()
The variables an element needs bound before it can be placed.
See the moduledoc. This is the whole ordering constraint.
@spec sort(Rete.IR.Production.t()) :: Rete.IR.Production.t()
Sorts the left hand side of a production topologically.
Returns the production with its :lhs reordered. The conditions themselves stay
untouched, except that a disjunction's branches and a Rete.IR.CompoundNegation's
conjunction are sorted the same way — against the variables bound where they sit.
This is idempotent. Sorting an already sorted LHS returns it unchanged.
iex> alias Rete.{Compiler.Sort, IR}
iex> order = %IR.Fact{bind: [:amt], __ast__: %{guard: quote(do: amt > t), bind: %{}}}
iex> threshold = %IR.Fact{bind: [:t]}
iex> production = %IR.Production{name: :r, lhs: [order, threshold]}
iex> Sort.sort(production).lhs |> Enum.map(& &1.bind)
[[:t], [:amt]]