Memo table: the cache layer that stores query results.
Each entry records the computed value, when it changed, when it was last validated, and what dependencies were read during computation. This is the data structure that makes incrementality work.
Entries are stored as flat tuples in ETS for efficiency and to support
atomic partial updates via :ets.select_replace/2.
Restored values stay encoded
An entry restored from a manifest (restore_persisted/2) keeps its
value in the external term format until something reads it: get/2,
entries/1 and reduce_entries/3 decode it on the way out, and the
value-free accessors never touch it. A warm run validates thousands of
entries and reads the values of a handful, so decoding every value up
front and copying it into ETS was most of the cost of restoring a
manifest (on a 350-module scry project, 13 million words decoded and
copied, of which a warm run that changed nothing reads about 15,000).
The encoding also goes back out unchanged: persisted/2 hands a
still-encoded value to the next manifest without encoding it again.
Nothing writes a decoded value back into the table. Doing that safely
would need a compare-and-swap against a concurrent put/3 of a newer
entry for the same key, and a lost race would pair the newer entry's
metadata with the older value. A process that reads a restored value
more than once caches it itself (Roux.Runtime does, per revision).
Values held by digest
An entry of a store: :blob query (Roux.Query) restored from a
manifest holds {:blob, digest} instead of an encoding: its value is
in the database's Roux.Blob store (Roux.Database.new/1's blob:),
read from there by the first read that needs it. A value whose blob is
gone — collected, or no store to read it from — reads as absent:
get/2 misses it, and fetch_value/2 says so, for a caller that
recomputes it (Roux.Runtime does, transparently).
Summary
Types
What an entry read: a query or input, an entity field, the absence
of an input ({:input_absent, input_name, key}, recorded by
Roux.Runtime.input/4 with a default), or a fan-out's queries
({:parallel, max_concurrency, keys}, recorded by
Roux.Runtime.parallel/3).
A value as a manifest holds it: in the external term format, or by the
digest of its blob ({:blob, digest}, a store: :blob query's).
An entry as a manifest persists it: every field of Roux.Memo.Entry
but persist (implied by the encoding), with the value encoded. See
persisted/3.
Functions
Reads an entry's changed_at without its value.
Reads an entry's code_version without its value.
Decodes a persisted entry (persisted/2) into {query_key, entry},
for inspecting a manifest without restoring it.
Removes a memo entry. Called during GC. No-op if the key doesn't exist.
Clears all memo entries. Called on database reset.
Reads just the two fields dependency validation needs, without materializing the entry's value.
Reads an entry's dependency list without its value.
Reads an entry's durability without its value.
Returns all memo entries with their keys.
An entry's value: {:ok, value}, :miss when there is no entry, or
:missing for an entry whose value's blob is gone.
Looks up a memo entry. Returns {:ok, entry}, or :miss — also for
an entry whose value's blob is gone (see "Values held by digest").
The digest an entry's value is held by, when it is held by one (a
restored store: :blob entry not replaced since): {:ok, digest}, or
:none. Read without the value.
The keys of the entries whose persist is persist.
The entries keep? accepts, in the form a manifest persists them.
Whether entry has the shape of a persisted entry (persisted/3).
Reads what re-executing an entry needs from the entry it replaces — its
hash, changed_at and output entities — without its value.
Stores a memo entry, overwriting any existing entry for this key.
Stores entry over an entry whose value is equal to (===)
entry.value, keeping the stored value.
Every entry's key and dependencies, folded without touching a value: the dependency graph, for a pass over it (a manifest's transient cascade, a GC sweep).
Folds over every entry as {query_key, entry} without materializing
the table as a list: each entry is copied out of ETS on its own turn
(a restored value decoded) and is garbage once the reducer is done
with it. An entry whose value's blob is gone is passed over.
Inserts persisted entries (persisted/2) with their values still
encoded: each is decoded by the first read that needs it.
Updates only the verified_at field of an existing entry.
Updates verified_at and durability together.
Reads an entry's verified_at and durability without its value.
Types
@type dependency() :: query_key() | {:entity_field, module(), term(), atom()} | {:input_absent, atom(), term()} | {:parallel, pos_integer(), [query_key()]}
What an entry read: a query or input, an entity field, the absence
of an input ({:input_absent, input_name, key}, recorded by
Roux.Runtime.input/4 with a default), or a fan-out's queries
({:parallel, max_concurrency, keys}, recorded by
Roux.Runtime.parallel/3).
@type encoded() :: binary() | {:blob, Roux.Blob.digest()}
A value as a manifest holds it: in the external term format, or by the
digest of its blob ({:blob, digest}, a store: :blob query's).
@type persisted() :: {query_key(), hash :: integer(), changed_at :: Roux.Revision.revision(), verified_at :: Roux.Revision.revision(), [dependency()], Roux.Revision.durability(), output_entities :: [{module(), term()}], encoded(), code_version :: binary() | nil, blobs :: [Roux.Blob.digest()]}
An entry as a manifest persists it: every field of Roux.Memo.Entry
but persist (implied by the encoding), with the value encoded. See
persisted/3.
Functions
@spec changed_at(Roux.Database.t(), query_key()) :: {:ok, Roux.Revision.revision()} | :miss
Reads an entry's changed_at without its value.
@spec code_version(Roux.Database.t(), query_key()) :: {:ok, binary() | nil} | :miss
Reads an entry's code_version without its value.
@spec decode_persisted(persisted(), Roux.Blob.t() | nil) :: {query_key(), Roux.Memo.Entry.t() | :missing}
Decodes a persisted entry (persisted/2) into {query_key, entry},
for inspecting a manifest without restoring it.
@spec delete(Roux.Database.t(), query_key()) :: :ok
Removes a memo entry. Called during GC. No-op if the key doesn't exist.
@spec delete_all(Roux.Database.t()) :: :ok
Clears all memo entries. Called on database reset.
@spec dep_state(Roux.Database.t(), query_key()) :: {:ok, Roux.Revision.revision(), Roux.Revision.durability()} | :miss
Reads just the two fields dependency validation needs, without materializing the entry's value.
Validation asks one question of each dependency — "did you change after I
was verified, and how durable are you?" — and answering it through
get/2 copies the dependency's whole value out of ETS to read two
integers.
That is not the cheap operation it looks like. ETS copies terms on read; a large binary is refcounted and so escapes with a pointer copy, but a memoized structure does not. Fact rows — lists of lists of short binaries, which is what most of planchette's memo values are — get deep copied in full. Measured at 747× the cost of reading the two fields directly, and validating a dependency graph touches every dependency of every node, so it dominated the per-edit budget: a comment edit on a 256-module project spent 2.5s validating entries it then discarded.
Returns {:ok, changed_at, durability} or :miss.
@spec dependencies(Roux.Database.t(), query_key()) :: {:ok, [dependency()]} | :miss
Reads an entry's dependency list without its value.
Only needed on the path that actually walks dependencies, which is why it
is separate from verification_state/2 rather than returned alongside.
@spec durability(Roux.Database.t(), query_key()) :: {:ok, Roux.Revision.durability()} | :miss
Reads an entry's durability without its value.
@spec entries(Roux.Database.t()) :: [{query_key(), Roux.Memo.Entry.t()}]
Returns all memo entries with their keys.
Returns [{query_key, entry}] rather than [entry] so that callers (e.g.
GC) can identify entries for deletion without a second lookup. Every
value is materialized, restored ones decoded.
@spec fetch_value(Roux.Database.t(), query_key()) :: {:ok, term()} | :miss | :missing
An entry's value: {:ok, value}, :miss when there is no entry, or
:missing for an entry whose value's blob is gone.
@spec get(Roux.Database.t(), query_key()) :: {:ok, Roux.Memo.Entry.t()} | :miss
Looks up a memo entry. Returns {:ok, entry}, or :miss — also for
an entry whose value's blob is gone (see "Values held by digest").
@spec held_digest(Roux.Database.t(), query_key()) :: {:ok, Roux.Blob.digest()} | :none
The digest an entry's value is held by, when it is held by one (a
restored store: :blob entry not replaced since): {:ok, digest}, or
:none. Read without the value.
@spec keys_persisted_as(Roux.Database.t(), Roux.Memo.Entry.persist()) :: [query_key()]
The keys of the entries whose persist is persist.
@spec persisted( Roux.Database.t(), (query_key(), Roux.Revision.durability() -> boolean()) | (query_key(), Roux.Revision.durability(), Roux.Memo.Entry.persist() -> boolean()), (term() -> {:blob, Roux.Blob.digest()}) | nil ) :: [persisted()]
The entries keep? accepts, in the form a manifest persists them.
keep? receives each entry's key and durability — and, when it takes
three arguments, its persist (Roux.Memo.Entry) — before its value
is touched. A restored value that was never replaced goes out in the
encoding it came in with, or by the digest it was held by; any other
value is encoded here, one entry at a time — by hold, when given, for
a :blob entry: it stores the value and returns {:blob, digest}.
Whether entry has the shape of a persisted entry (persisted/3).
@spec prior_state(Roux.Database.t(), query_key()) :: {:ok, integer(), Roux.Revision.revision(), [{module(), term()}]} | :miss
Reads what re-executing an entry needs from the entry it replaces — its
hash, changed_at and output entities — without its value.
The three fields are read one at a time, so a put/3 racing the read
can mix two entries' fields: read it where no other put of the key can
happen (Roux.Runtime reads it while it holds the key's computation
claim).
Returns {:ok, hash, changed_at, output_entities} or :miss.
@spec put(Roux.Database.t(), query_key(), Roux.Memo.Entry.t()) :: :ok
Stores a memo entry, overwriting any existing entry for this key.
Called after successful query execution with the buffered result.
@spec put_unchanged(Roux.Database.t(), query_key(), Roux.Memo.Entry.t()) :: :ok
Stores entry over an entry whose value is equal to (===)
entry.value, keeping the stored value.
Re-execution that comes back to the value it had (early cutoff) rewrites everything about the entry but its value. Keeping the stored value saves copying the equal new one into the table and, for a value restored from a manifest and not yet replaced, keeps its encoding, so the next manifest does not encode it again. The caller vouches for the equality; nothing here compares the values.
Behaves as put/3 when there is no stored entry.
@spec reduce_dependencies(Roux.Database.t(), acc, (query_key(), [dependency()], acc -> acc)) :: acc when acc: term()
Every entry's key and dependencies, folded without touching a value: the dependency graph, for a pass over it (a manifest's transient cascade, a GC sweep).
@spec reduce_entries(Roux.Database.t(), acc, ({query_key(), Roux.Memo.Entry.t()}, acc -> acc)) :: acc when acc: term()
Folds over every entry as {query_key, entry} without materializing
the table as a list: each entry is copied out of ETS on its own turn
(a restored value decoded) and is garbage once the reducer is done
with it. An entry whose value's blob is gone is passed over.
@spec restore_persisted(Roux.Database.t(), [persisted()]) :: :ok
Inserts persisted entries (persisted/2) with their values still
encoded: each is decoded by the first read that needs it.
Used by manifest restore. Overwrites entries with the same keys.
Raises ArgumentError for anything that is not a persisted entry.
@spec update_verified(Roux.Database.t(), query_key(), Roux.Revision.revision()) :: :ok
Updates only the verified_at field of an existing entry.
Called when validation determines the cached value is still valid (early
cutoff). Uses :ets.select_replace/2 for atomicity — the entry is never
partially updated.
A no-op if no entry exists for the given key.
@spec update_verified( Roux.Database.t(), query_key(), non_neg_integer(), Roux.Revision.durability() ) :: :ok
Updates verified_at and durability together.
Durability is the minimum over an entry's transitive inputs, computed when the entry EXECUTES. Early cutoff means a dependent is frequently validated WITHOUT executing, so without refreshing it here an entry keeps whatever level it was first computed with — and then skips a change at a lower level, serving a stale value with no error. Validation already reads every dependency's entry, so the current minimum is in hand exactly where it needs to be written.
@spec verification_state(Roux.Database.t(), query_key()) :: {:ok, Roux.Revision.revision(), Roux.Revision.durability()} | :miss
Reads an entry's verified_at and durability without its value.
The first two questions validation asks of an entry — "have I already
checked you this revision?" and "can I skip you on durability?" — and
neither needs the value. See dep_state/2 for why reading it anyway is
expensive.
Returns {:ok, verified_at, durability} or :miss.