Working memory: everything a session knows, as one immutable value.
Internal. Not part of the public API. It is documented rather than hidden, because durability, checkpointing, and advanced tooling will need to reach in here. Treat its functions as liable to change.
Five memories, one index over them, and one flag:
elements node_id => join_key => Bucket of Element right of a beta node
tokens node_id => join_key => Bucket of Token left of a beta node
accum node_id => join_key => group_key => [member] what a collection gathered
insertions node_id => token => [[fact]] truth maintenance
facts fact => count what it was told
inserters fact => {node_id, token} => count `insertions`, reversedinserters is not a memory. It is insertions indexed by fact, for the readers that ask
"which matches inserted this fact". It stays nil until index_inserters/1 builds it,
and it is left out of dump/1, being a cache.
Arrival order is load-bearing. A bucket decides the order tokens propagate, so it
decides the order two matches of one rule fire. One that gave items back in a different
order would reorder every :activation_fired event.
docs/design/engine.md §4 has the other two properties, and why the index is built late.
root_seeded? is not a memory. It records that the beta root's empty token has been
planted. This must happen exactly once per session. See docs/design/engine.md §6.
iex> alias Rete.Memory
iex> {memory, :new} = Memory.add_fact(Memory.new(), {:order, 1})
iex> {memory, :duplicate} = Memory.add_fact(memory, {:order, 1})
iex> {memory, :remaining} = Memory.remove_fact(memory, {:order, 1})
iex> Memory.facts(memory)
[{:order, 1}]Summary
Types
One match at one production, identified by where it fired and what it matched.
Functions
Adds elements at a node under a join key.
Records a fact, returning {memory, :new | :duplicate}.
Records the facts one activation of a production inserted.
Adds one member to a collection group, in front of the ones already there. O(1).
Adds tokens at a node under a join key.
Every element at a node, whatever its join key.
Every token at a node, whatever its join key.
Whether a node holds anything under a join key, without building the list.
The whole memory as plain data, every bucket rendered as a list in arrival order.
The elements stored at a node under a join key, in arrival order.
Every distinct fact the session holds.
The members of one collection group, or nil if there is no such group. O(1).
The group keys a node holds under a join key.
The collection groups at a node under a join key, group_key => members.
Builds the inserters index if it is not built, and returns the memory holding it.
The matches whose activation inserted fact, as {node_id, token} pairs.
Records that the beta root's empty token has been propagated.
An empty memory.
Removes one occurrence of each given element, returning {memory, removed}.
Drops one occurrence of a fact, returning {memory, :gone | :remaining | :absent}.
Removes one occurrence of a member from a collection group, reporting whether it was there. O(position).
Removes one occurrence of each given token, returning what was found.
Takes back one batch of facts a token's activation inserted.
The tokens stored at a node under a join key, in arrival order.
Types
@type inserter() :: {node_id(), Rete.Token.t()}
One match at one production, identified by where it fired and what it matched.
@type node_id() :: term()
@type t() :: %Rete.Memory{ accum: %{ required(node_id()) => %{required(key()) => %{required(key()) => [term()]}} }, elements: %{required(node_id()) => %{required(key()) => Rete.Bucket.t()}}, facts: %{required(term()) => pos_integer()}, inserters: %{required(term()) => %{required(inserter()) => pos_integer()}} | nil, insertions: %{ required(node_id()) => %{required(Rete.Token.t()) => [[term()]]} }, root_seeded?: boolean(), tokens: %{required(node_id()) => %{required(key()) => Rete.Bucket.t()}} }
Functions
@spec add_elements(t(), node_id(), key(), [Rete.Element.t()]) :: t()
Adds elements at a node under a join key.
Records a fact, returning {memory, :new | :duplicate}.
Only :new propagates. A second insertion of an equal fact bumps its count instead, so
that one retraction does not remove it. The matches it would make already exist.
@spec add_insertion(t(), node_id(), Rete.Token.t(), [term()]) :: t()
Records the facts one activation of a production inserted.
This is stored as a list of lists. The same token can activate a production more than once, over a session's life, and each activation owns its own batch.
Adds one member to a collection group, in front of the ones already there. O(1).
Reverse arrival order, and no sort. The new list shares its whole tail with the old one, so adding a member allocates a single cons cell however large the group is.
Do not reintroduce a sort here. This node used to keep members in term order, so that a
collection's order — and not merely its membership — was a function of the fact set.
Nothing asks for that. docs/dsl.md has always said that a rule may not depend on the
gathered order. The sort could thus help only the rules that were already outside the
contract, and it charged O(k) to every member change of every collection. A rule
that needs a particular order sorts in its own right hand side, once per firing rather
than once per member.
@spec add_tokens(t(), node_id(), key(), [Rete.Token.t()]) :: t()
Adds tokens at a node under a join key.
@spec all_elements(t(), node_id()) :: [Rete.Element.t()]
Every element at a node, whatever its join key.
@spec all_tokens(t(), node_id()) :: [Rete.Token.t()]
Every token at a node, whatever its join key.
Whether a node holds anything under a join key, without building the list.
A plain Rete.Network.Node.Negation has no filter, so "does anything match this token"
is the same question for every token: is the bucket empty. Answering that with
elements/3 would cost a pass over the bucket per arriving element.
@spec dump(t()) :: %{ elements: %{required(node_id()) => %{required(key()) => [Rete.Element.t()]}}, tokens: %{required(node_id()) => %{required(key()) => [Rete.Token.t()]}}, accum: %{ required(node_id()) => %{required(key()) => %{required(key()) => [term()]}} }, insertions: %{ required(node_id()) => %{required(Rete.Token.t()) => [[term()]]} }, facts: %{required(term()) => pos_integer()}, root_seeded?: boolean() }
The whole memory as plain data, every bucket rendered as a list in arrival order.
Use this instead of the struct. A Rete.Bucket holds a queue with tombstones in it, so
two memories that agree on every match can still disagree there. This is the view that is
meaningful to compare, assert on, and write down.
Note that :accum is not canonical even here: a collection group is kept in reverse
arrival order, so two sessions holding the same members can list them differently. Sort
it before comparing sessions that were fed differently. See add_to_group/5.
@spec elements(t(), node_id(), key()) :: [Rete.Element.t()]
The elements stored at a node under a join key, in arrival order.
Every distinct fact the session holds.
The members of one collection group, or nil if there is no such group. O(1).
nil and [] are different answers. A group with no members does not exist. An empty
collection a rule can legitimately see is [], and only Rete.Engine.Nodes knows which
of the two an absent group means. See remove_from_group/5.
This is the list that the node gives to the rule. It is not a view built for one call. That is deliberate: a member change must produce the old value of the collection and the new one. To build either one would be O(k), on the path that runs most often.
The group keys a node holds under a join key.
The collection groups at a node under a join key, group_key => members.
A member is whatever the node stored. A plain collection keeps facts, because that is
what it binds. A filtered one keeps Rete.Elements, because its filter needs the bindings
that the alpha produced. Rete.Memory does not interpret them.
Builds the inserters index if it is not built, and returns the memory holding it.
One pass over every insertion record. After this, add_insertion/4 and
take_insertion/3 keep it in step. The pass thus happens one time in a session at most.
It does not happen at all in a session where no rule concludes what another rule already
concluded, because only that consults the index.
The matches whose activation inserted fact, as {node_id, token} pairs.
Empty for a fact the user asserted. A fact two rules concluded has two entries, and one rule may appear twice if it concluded the fact on two activations of the same match.
This is the index behind well-founded support. To read it is a map lookup, and that is the purpose of it. Before, the engine recomputed the answer from every insertion record in the session, for every conclusion that was already present.
This falls back to that recomputation when the index is not built, so a reader that asks
one time gets a correct answer without forcing a build on a session that would never need
one. A caller that asks repeatedly must call index_inserters/1 first, and keep what it
returns. The fallback is a pass over every insertion record, so asking per fact without
the index is quadratic in the size of the session. Rete.Inspect.explain/1,2 builds it
for that reason.
Records that the beta root's empty token has been propagated.
Rete.Engine.Nodes seeds only while this is false. So a session plants exactly one
root token, however many times it is asked.
@spec new() :: t()
An empty memory.
@spec remove_elements(t(), node_id(), key(), [Rete.Element.t()]) :: {t(), [Rete.Element.t()]}
Removes one occurrence of each given element, returning {memory, removed}.
An element that was not there is left out of removed. So a caller can tell a real
retraction from a no-op. Propagating a retraction that never happened would corrupt the
counts downstream.
Drops one occurrence of a fact, returning {memory, :gone | :remaining | :absent}.
Only :gone propagates — that is, only the last occurrence.
Removes one occurrence of a member from a collection group, reporting whether it was there. O(position).
This returns :absent, and not a no-op with no message. remove_elements/4 leaves an
absent element out of what it returns for the same reason. A caller could otherwise emit a
retract-and-resend for a group that did not change, and disturb every match below it.
A group that loses its last member is dropped. The join key that held the last group goes with it, and so does the node, if that was its last join key. Both are binding values, so leaving them behind would leak one entry per entity the session has seen.
@spec remove_tokens(t(), node_id(), key(), [Rete.Token.t()]) :: {t(), [Rete.Token.t()]}
Removes one occurrence of each given token, returning what was found.
@spec take_insertion(t(), node_id(), Rete.Token.t()) :: {t(), [term()]}
Takes back one batch of facts a token's activation inserted.
Returns {memory, facts}, or {memory, []} when the token never inserted anything.
That case is a production retracted before it fired, or one whose body returned
nothing.
@spec tokens(t(), node_id(), key()) :: [Rete.Token.t()]
The tokens stored at a node under a join key, in arrival order.