🥮 mooncakes.io

ripple

Incremental computation library for MoonBit - changes ripple through the dependency graph

incremental
memoization
cache
dependency-tracking
moon add mizchi/ripple@0.1.4
Download zip
Author
Version
0.1.4
License
MIT
Repository
Last updated
2 months ago
Downloads
59K
README

#ripple

Incremental computation library for MoonBit, inspired by Rust's salsa. Changes ripple through the dependency graph, recomputing only what's necessary.

#Usage

let db = @ripple.Database::new()
let rt = db.runtime()

// Define inputs
let source_files : @ripple.Input[String, String] = db.input()
source_files.register(rt)

// Define queries
let parse : @ripple.Query[String, Array[String]] = db.query(
  fn(rt, path) {
    match source_files.get(rt, path) {
      Some(content) => parse_imports(content)
      None => []
    }
  }
)
parse.register(rt)

// Set inputs and run queries
source_files.set(rt, "a.mbt", "import b") |> ignore
let result = parse.fetch(rt, "a.mbt")  // ["b"]

// Change input - only affected queries recompute
source_files.set(rt, "a.mbt", "import b, c") |> ignore
let result2 = parse.fetch(rt, "a.mbt")  // ["b", "c"] - recomputed

#Features

  • Automatic dependency tracking: Dependencies recorded during query execution
  • Minimal recomputation: Only changed inputs trigger recomputation
  • Deep verification: Cached results validated against dependency graph
  • Cycle detection: CycleQuery handles recursive dependencies
  • Value interning: Deduplicate values with stable IDs
  • Accumulator: Collect diagnostics/warnings during computation

#
Accumulator

source
pub struct Accumulator[V] {
  ingredient_index : Int
  values : 
HashMap[(Int, Int), Array[V]]
}

Accumulator collects values during query computation. Useful for gathering diagnostics, warnings, or other side-effect data without affecting the main computation result.

Example use cases:
  • Collecting compiler warnings during type checking
  • Gathering dependency information during module resolution
  • Accumulating metrics during computation

#
Accumulator::clear

source
fn[V] Accumulator::clear(self : Accumulator[V], query_index : Int, key_hash : Int) -> Unit

Clear all accumulated values for a specific query execution. Called when the query is invalidated and needs to be recomputed.

#
Accumulator::clear_all

source
fn[V] Accumulator::clear_all(self : Accumulator[V]) -> Unit

Clear all accumulated values.

#
Accumulator::clear_for_query

source
fn[K : Hash, Q, V] Accumulator::clear_for_query(self : Accumulator[V], query : Query[K, Q], key : K) -> Unit

Clear all accumulated values for a query, given its Query instance and key.

#
Accumulator::count

source
fn[V] Accumulator::count(self : Accumulator[V], query_index : Int, key_hash : Int) -> Int

Get the count of accumulated values for a specific query execution.

#
Accumulator::get

source
fn[V] Accumulator::get(self : Accumulator[V], query_index : Int, key_hash : Int) -> Array[V]

Collect all values accumulated for a specific query execution. Returns an empty array if no values were accumulated.

#
Accumulator::get_for_cycle_query

source
fn[K : Hash, Q, V] Accumulator::get_for_cycle_query(self : Accumulator[V], query : CycleQuery[K, Q], key : K) -> Array[V]

Collect all values accumulated for a CycleQuery, given its instance and key.

#
Accumulator::get_for_query

source
fn[K : Hash, Q, V] Accumulator::get_for_query(self : Accumulator[V], query : Query[K, Q], key : K) -> Array[V]

Collect all values accumulated for a query, given its Query instance and key.

#
Accumulator::get_index

source
fn[V] Accumulator::get_index(self : Accumulator[V]) -> Int

Get the ingredient index.

#
Accumulator::has_values

source
fn[V] Accumulator::has_values(self : Accumulator[V], query_index : Int, key_hash : Int) -> Bool

Check if any values have been accumulated for a specific query execution.

#
Accumulator::iter

source
fn[V] Accumulator::iter(self : Accumulator[V]) -> Iter[((Int, Int), Array[V])]

Iterate over all accumulated values across all queries.

#
Accumulator::new

source
fn[V] Accumulator::new(ingredient_index : Int) -> Accumulator[V]

Create a new Accumulator with the given ingredient index.

#
Accumulator::push

source
fn[V] Accumulator::push(self : Accumulator[V], rt : Runtime, value : V) -> Unit

Push a value to the accumulator in the context of the current query. The value is associated with the currently executing query. If no query is executing, the value is silently ignored.

#
ActiveQuery

source
type ActiveQuery

ActiveQuery represents a query that is currently being executed. It tracks dependencies as the query runs.

#
ActiveQuery::add_edge

source
fn ActiveQuery::add_edge(self : ActiveQuery, ingredient_index : Int, key_index : Int, changed_at : Revision, durability : Durability) -> Unit

Add a dependency edge to the active query.

#
ActiveQuery::get_changed_at

source
fn ActiveQuery::get_changed_at(self : ActiveQuery) -> Revision

Get the maximum changed_at revision.

#
ActiveQuery::get_durability

source
fn ActiveQuery::get_durability(self : ActiveQuery) -> Durability

Get the minimum durability among all dependencies.

#
ActiveQuery::get_edges

source
fn ActiveQuery::get_edges(self : ActiveQuery) -> Array[QueryEdge]

Get the recorded edges.

#
ActiveQuery::new

source
fn ActiveQuery::new(ingredient_index : Int, key_index : Int) -> ActiveQuery

Create a new ActiveQuery.

#
CycleMemo

source
type CycleMemo[V]

CycleMemo extends Memo with provisional value tracking for fixpoint iteration.

#
CycleQuery

source
pub struct CycleQuery[K, V] {
  ingredient_index : Int
  compute : (Runtime, K) -> V
  memos : 
HashMap[K, CycleMemo[V]]
  hash_to_key : 
HashMap[Int, K]
  strategy : CycleStrategy[K, V]
}

CycleQuery is a Query that supports cycle recovery. When a cycle is detected, instead of panicking, it uses the configured strategy.

#
CycleQuery::changed_at

source
fn[K : Hash + Eq, V] CycleQuery::changed_at(self : CycleQuery[K, V], key : K) -> Revision?

Get the changed_at revision for a key.

#
CycleQuery::fetch

source
fn[K : Hash + Eq, V : Eq] CycleQuery::fetch(self : CycleQuery[K, V], rt : Runtime, key : K) -> V

Fetch the result for a key, with cycle recovery support.

#
CycleQuery::get_durability

source
fn[K : Hash + Eq, V] CycleQuery::get_durability(self : CycleQuery[K, V], key : K) -> Durability?

Get the durability for a key.

#
CycleQuery::get_index

source
fn[K, V] CycleQuery::get_index(self : CycleQuery[K, V]) -> Int

Get the ingredient index.

#
CycleQuery::maybe_changed_after

source
fn[K : Hash + Eq, V] CycleQuery::maybe_changed_after(self : CycleQuery[K, V], key : K, revision : Revision) -> Bool

Check if the query might have changed after a given revision.

#
CycleQuery::new

source
fn[K, V] CycleQuery::new(ingredient_index : Int, compute : (Runtime, K) -> V) -> CycleQuery[K, V]

Create a new CycleQuery with Panic strategy (same as regular Query).

#
CycleQuery::new_with_fallback

source
fn[K, V] CycleQuery::new_with_fallback(ingredient_index : Int, compute : (Runtime, K) -> V, fallback : V) -> CycleQuery[K, V]

Create a new CycleQuery with a fallback value for cycle recovery.

#
CycleQuery::new_with_recover

source
fn[K, V] CycleQuery::new_with_recover(ingredient_index : Int, compute : (Runtime, K) -> V, recover : (Runtime, K) -> V) -> CycleQuery[K, V]

Create a new CycleQuery with a recovery function for cycle recovery.

#
CycleQuery::register

source
fn[K : Hash + Eq, V : Eq] CycleQuery::register(self : CycleQuery[K, V], rt : Runtime) -> Unit

Register this query's verifier with the runtime.

#
CycleStrategy

source
pub enum CycleStrategy[K, V] {
  Panic
  Fallback(V)
  Recover((Runtime, K) -> V)
}

CycleStrategy defines how to handle cycles in query execution.

#
Database

source
pub struct Database {
  runtime : Runtime
  next_index : Int
}

Database is the main facade for the incremental computation system. It manages the runtime, inputs, and queries.

#
Database::accumulator

source
fn[V] Database::accumulator(self : Database) -> Accumulator[V]

Create a new Accumulator registered with this database.

#
Database::current_revision

source
fn Database::current_revision(self : Database) -> Revision

Get the current revision.

#
Database::cycle_query

source
fn[K, V] Database::cycle_query(self : Database, compute : (Runtime, K) -> V) -> CycleQuery[K, V]

Create a new CycleQuery with Panic strategy (same as regular Query).

#
Database::cycle_query_with_fallback

source
fn[K, V] Database::cycle_query_with_fallback(self : Database, compute : (Runtime, K) -> V, fallback : V) -> CycleQuery[K, V]

Create a new CycleQuery with a fallback value for cycle recovery.

#
Database::cycle_query_with_recover

source
fn[K, V] Database::cycle_query_with_recover(self : Database, compute : (Runtime, K) -> V, recover : (Runtime, K) -> V) -> CycleQuery[K, V]

Create a new CycleQuery with a recovery function for cycle recovery.

#
Database::input

source
fn[K, V] Database::input(self : Database) -> Input[K, V]

Create a new Input registered with this database (default Low durability).

#
Database::input_with_durability

source
fn[K, V] Database::input_with_durability(self : Database, durability : Durability) -> Input[K, V]

Create a new Input with specified durability.

#
Database::intern

source
fn[V] Database::intern(self : Database) -> Intern[V]

Create a new Intern registered with this database (default High durability).

#
Database::intern_with_durability

source
fn[V] Database::intern_with_durability(self : Database, durability : Durability) -> Intern[V]

Create a new Intern with specified durability.

#
Database::new

source
fn Database::new() -> Database

Create a new Database.

#
Database::query

source
fn[K, V] Database::query(self : Database, compute : (Runtime, K) -> V) -> Query[K, V]

Create a new Query registered with this database.

#
Database::runtime

source
fn Database::runtime(self : Database) -> Runtime

Get the runtime (for use with inputs and queries).

#
Durability

source
pub(all) enum Durability {
  Low
  Medium
  High
} derive(Compare, Eq, Hash, 
Debug)

Durability indicates how often a value is expected to change. Higher durability means the value changes less frequently. This is used to optimize cache invalidation.
impl Show for Durability

#
Durability::min

source
fn Durability::min(self : Durability, other : Durability) -> Durability

Get the minimum of two durabilities.

#
Durability::to_index

source
fn Durability::to_index(self : Durability) -> Int

Convert durability to array index.

#
Input

source
pub struct Input[K, V] {
  ingredient_index : Int
  durability : Durability
  values : 
HashMap[K, InputValue[V]]
  hash_to_changed_at : 
HashMap[Int, Revision]
}

Input represents an external input to the incremental computation system. Values can be set at any time, which increments the revision.

#
Input::changed_at

source
fn[K : Hash + Eq, V] Input::changed_at(self : Input[K, V], key : K) -> Revision?

Get the changed_at revision for a key.

#
Input::contains

source
fn[K : Hash + Eq, V] Input::contains(self : Input[K, V], key : K) -> Bool

Check if a key exists in the input.

#
Input::get

source
fn[K : Hash + Eq, V] Input::get(self : Input[K, V], rt : Runtime, key : K) -> V?

Get a value from the input. Records a dependency if there's an active query.

#
Input::get_durability

source
fn[K, V] Input::get_durability(self : Input[K, V]) -> Durability

Get the durability of this input.

#
Input::get_index

source
fn[K, V] Input::get_index(self : Input[K, V]) -> Int

Get the ingredient index.

#
Input::maybe_changed_after

source
fn[K : Hash + Eq, V] Input::maybe_changed_after(self : Input[K, V], key : K, revision : Revision) -> Bool

Check if the input might have changed after a given revision.

#
Input::new

source
fn[K, V] Input::new(ingredient_index : Int) -> Input[K, V]

Create a new Input with the given ingredient index and default Low durability.

#
Input::new_with_durability

source
fn[K, V] Input::new_with_durability(ingredient_index : Int, durability : Durability) -> Input[K, V]

Create a new Input with the given ingredient index and durability.

#
Input::register

source
fn[K, V] Input::register(self : Input[K, V], rt : Runtime) -> Unit

Register this input's verifier with the runtime. This enables deep verify for queries that depend on this input.

#
Input::set

source
fn[K : Hash + Eq, V : Eq] Input::set(self : Input[K, V], rt : Runtime, key : K, value : V) -> Revision

Set a value in the input. Returns the new revision. If the value hasn't changed, no revision bump occurs.

#
InputValue

source
type InputValue[V]

InputValue stores a value along with its revision metadata.

#
Intern

source
pub struct Intern[V] {
  ingredient_index : Int
  durability : Durability
  value_to_id : 
HashMap[V, InternId]
  id_to_value : Array[V]
  changed_at : Revision
}

Intern stores deduplicated values and assigns stable IDs.
  • Same value always returns same ID
  • ID can be used to retrieve original value
  • Useful for strings, symbols, AST nodes

#
Intern::contains

source
fn[V : Hash + Eq] Intern::contains(self : Intern[V], value : V) -> Bool

Check if a value has been interned.

#
Intern::get_durability

source
fn[V] Intern::get_durability(self : Intern[V]) -> Durability

Get the durability of this intern.

#
Intern::get_id

source
fn[V : Hash + Eq] Intern::get_id(self : Intern[V], value : V) -> InternId?

Get the ID for a value without recording a dependency. Returns None if the value hasn't been interned.

#
Intern::get_index

source
fn[V] Intern::get_index(self : Intern[V]) -> Int

Get the ingredient index.

#
Intern::intern

source
fn[V : Hash + Eq] Intern::intern(self : Intern[V], rt : Runtime, value : V) -> InternId

Intern a value and return its ID. If the value was already interned, returns the existing ID. Records a dependency if there's an active query.

#
Intern::is_empty

source
fn[V] Intern::is_empty(self : Intern[V]) -> Bool

Check if the intern is empty.

#
Intern::len

source
fn[V] Intern::len(self : Intern[V]) -> Int

Get the number of interned values.

#
Intern::lookup

source
fn[V] Intern::lookup(self : Intern[V], rt : Runtime, id : InternId) -> V?

Look up a value by its ID. Returns None if the ID is invalid. Records a dependency if there's an active query.

#
Intern::new

source
fn[V] Intern::new(ingredient_index : Int) -> Intern[V]

Create a new Intern with the given ingredient index. Default durability is High (interned values rarely change).

#
Intern::new_with_durability

source
fn[V] Intern::new_with_durability(ingredient_index : Int, durability : Durability) -> Intern[V]

Create a new Intern with custom durability.

#
Intern::register

source
fn[V] Intern::register(self : Intern[V], rt : Runtime) -> Unit

Register this intern's verifier with the runtime.

#
InternId

source
pub(all) struct InternId(Int) derive(Compare, Eq, Hash, 
Debug)

InternId is a lightweight identifier for interned values. Same value always gets the same ID, enabling O(1) comparison.
impl Show for InternId

#
InternId::from_raw

source
fn InternId::from_raw(value : Int) -> InternId

Create an InternId from a raw integer. Warning: Only use this if you know the ID is valid.

#
InternId::get

source
fn InternId::get(self : InternId) -> Int

Get the raw integer value of the InternId.

#
Memo

source
type Memo[V]

Memo stores a cached query result with its revision metadata.

#
Query

source
pub struct Query[K, V] {
  ingredient_index : Int
  compute : (Runtime, K) -> V
  memos : 
HashMap[K, Memo[V]]
  hash_to_key : 
HashMap[Int, K]
}

Query represents a memoized computation. It caches results and automatically invalidates when dependencies change.

#
Query::changed_at

source
fn[K : Hash + Eq, V] Query::changed_at(self : Query[K, V], key : K) -> Revision?

Get the changed_at revision for a key (for dependency tracking).

#
Query::fetch

source
fn[K : Hash + Eq, V : Eq] Query::fetch(self : Query[K, V], rt : Runtime, key : K) -> V

Fetch the result for a key, using cache if valid or recomputing if necessary.

#
Query::get_durability

source
fn[K : Hash + Eq, V] Query::get_durability(self : Query[K, V], key : K) -> Durability?

Get the durability for a key.

#
Query::get_index

source
fn[K, V] Query::get_index(self : Query[K, V]) -> Int

Get the ingredient index.

#
Query::maybe_changed_after

source
fn[K : Hash + Eq, V] Query::maybe_changed_after(self : Query[K, V], key : K, revision : Revision) -> Bool

Check if the query might have changed after a given revision.

#
Query::new

source
fn[K, V] Query::new(ingredient_index : Int, compute : (Runtime, K) -> V) -> Query[K, V]

Create a new Query with the given index and computation function.

#
Query::register

source
fn[K : Hash + Eq, V : Eq] Query::register(self : Query[K, V], rt : Runtime) -> Unit

Register this query's verifier with the runtime. This enables deep verify for queries that depend on this query. Note: For Query, the verifier must ensure the memo is up-to-date before checking if it changed. This requires calling verify_internal.

#
QueryEdge

source
pub struct QueryEdge {
  ingredient_index : Int
  key_index : Int
  changed_at : Revision
  durability : Durability
} derive(Eq, 
Debug)

QueryEdge represents a dependency edge in the query graph. It records which query/input was accessed and at what revision.
impl Show for QueryEdge

#
Revision

source
pub struct Revision(Int) derive(Compare, Eq, Hash, 
Debug)

Revision represents a monotonically increasing counter. Each time an input changes, the revision is incremented. This is the core mechanism for tracking changes in the incremental computation system. Using newtype struct for zero-cost abstraction.
impl Show for Revision

#
Revision::get

source
fn Revision::get(self : Revision) -> Int

Get the integer value of the revision.

#
Revision::is_after

source
fn Revision::is_after(self : Revision, other : Revision) -> Bool

Check if this revision is after another revision.

#
Revision::is_at_or_after

source
fn Revision::is_at_or_after(self : Revision, other : Revision) -> Bool

Check if this revision is at or after another revision.

#
Revision::max

source
fn Revision::max(self : Revision, other : Revision) -> Revision

Return the maximum of two revisions.

#
Revision::new

source
fn Revision::new(value : Int) -> Revision

Create a new Revision from an integer value.

#
Revision::next

source
fn Revision::next(self : Revision) -> Revision

Create the next revision (increment by 1).

#
Revision::zero

source
fn Revision::zero() -> Revision

Create a new Revision with value 0 (initial state).

#
Runtime

source
type Runtime

Runtime manages the global state of the incremental computation system.

#
Runtime::current_revision

source
fn Runtime::current_revision(self : Runtime) -> Revision

Get the current revision.

#
Runtime::get_current_query

source
fn Runtime::get_current_query(self : Runtime) -> (Int, Int)?

Get the currently executing query (top of the stack). Returns (ingredient_index, key_index) or None if no query is executing.

#
Runtime::has_active_query

source
fn Runtime::has_active_query(self : Runtime) -> Bool

Check if there is an active query on the stack.

#
Runtime::increment_revision

source
fn Runtime::increment_revision(self : Runtime, durability : Durability) -> Revision

Increment the revision (called when an input changes). Updates the durability revision for the given durability level.

#
Runtime::is_executing

source
fn Runtime::is_executing(self : Runtime, ingredient_index : Int, key_index : Int) -> Bool

Check if we are currently executing a specific query (for cycle detection).

#
Runtime::last_changed_at

source
fn Runtime::last_changed_at(self : Runtime, durability : Durability) -> Revision

Get the last changed revision for a durability level.

#
Runtime::maybe_changed_after

source
fn Runtime::maybe_changed_after(self : Runtime, ingredient_index : Int, key_index : Int, revision : Revision) -> Bool

Check if an ingredient might have changed after a revision. Returns true if changed or if no verifier is registered.

#
Runtime::new

source
fn Runtime::new() -> Runtime

Create a new Runtime.

#
Runtime::pop_query

source
fn Runtime::pop_query(self : Runtime) -> (Array[QueryEdge], Revision, Durability)?

Pop the active query from the stack and return its recorded edges, changed_at, and durability.

#
Runtime::push_query

source
fn Runtime::push_query(self : Runtime, ingredient_index : Int, key_index : Int) -> Unit

Push a new active query onto the stack.

#
Runtime::record_dependency

source
fn Runtime::record_dependency(self : Runtime, ingredient_index : Int, key_index : Int, changed_at : Revision, durability : Durability) -> Bool

Record a dependency in the currently executing query. Returns true if there is an active query, false otherwise.

#
Runtime::register_verifier

source
fn Runtime::register_verifier(self : Runtime, ingredient_index : Int, verifier : (Int, Revision) -> Bool) -> Unit

Register a verifier for an ingredient.

#
durability_count

source
let durability_count : Int

Number of durability levels (for array indexing).

#
max_fixpoint_iterations

source
let max_fixpoint_iterations : Int

Maximum iterations for fixpoint computation

Source Files

Powered by MoonBit

Site sourceReport issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io