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 holds nothing insertions does not, indexed the other way,
for the two readers that ask "which matches inserted this fact":
Rete.Engine.well_founded/3 on a conclusion already present, and
Rete.Inspect.derivations/2. Answering from insertions costs a pass over every insertion
record, which made two rules concluding one fact quadratic.
It is nil until something needs it. A ruleset where no rule re-concludes never
consults it, so index_inserters/1 builds it on first use and everything after is
maintained in step. It is a multiset keyed on {node_id, token}, so it does not depend on
the order the session reached it in. Being a cache, it is left out of dump/1.
Three properties are load-bearing. See docs/design/engine.md §4.
- Arrival order. It decides the order tokens propagate, and so the order two
matches of one rule fire. A bucket that gave items back in a different order would
reorder every
:activation_firedevent. - Removal collapses the level above. Every key above the leaf is a value, so an
entry pointing at an empty leaf leaks.
Rete.Engine.Nodesalso needs "no group" and "an empty group" to stay different answers. - Multisets, not sets. Inserting a fact twice, then retracting once, must leave it present. Two rules may each have concluded it.
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.
The node id one of a query's indexes stores under.
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 a rule may not depend on the
gathered order, so the sort could only ever help rules that were already outside the
contract, and it charged O(k) to every member change of every collection to do it. 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 the node hands to the rule, not a view built for the occasion. That is the point of it: a member change has to produce the collection's old value and its new one, and materialising either would be O(k) on the hottest path there is.
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, and a filtered one keeps Rete.Elements, because its filter needs the
bindings the alpha produced. Rete.Memory does not interpret them.
@spec index_id(node_id(), non_neg_integer()) :: node_id()
The node id one of a query's indexes stores under.
A node_id is any term, so an index gets a namespace of its own rather than a second
keying of the query's own store. Two keyings under one id would collide in
all_tokens/2, which unions a node's buckets.
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, so the pass happens at most once per session — and
not at all in a session where no rule ever concludes what another already concluded,
which is the only thing that consults it.
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. Reading it is a map lookup, which is the whole point: the answer used to be recomputed from every insertion record in the session, on every conclusion that was already present.
Falls back to that recomputation when the index has not been built, so a one-off reader
like Rete.Inspect.derivations/2 gets a correct answer without forcing a build on a
session that would otherwise never need one. A caller that will ask repeatedly should
call index_inserters/1 first and keep what it returns.
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).
:absent rather than a silent no-op, for the same reason remove_elements/4 leaves an
absent element out of what it returns: a caller that emitted a retract-and-resend for a
group nothing actually changed would churn every match downstream of 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.