🥮 mooncakes.io
    Sign in

    ripple

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

    incremental
    memoization
    cache
    dependency-tracking
    Download zip
    Author
    Version
    0.1.3
    License
    MIT
    Repository
    Last updated
    7 months ago
    Downloads
    59K

    No dependencies

    #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]]
      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
    }

    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 Eq for Durability
    impl Hash for Durability
    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) type InternId Int

    InternId is a lightweight identifier for interned values. Same value always gets the same ID, enabling O(1) comparison.
    impl Compare for InternId
    impl Eq for InternId
    impl Hash for InternId
    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.

    InternId::inner

    source
    #deprecated("Use `struct T(A)` to declare a newtype and use `.0` access the underlying type instead.")
    fn InternId::inner(self : InternId) -> Int
    Convert newtype to its underlying type, automatically derived.

    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]]
    }

    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
    }

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

    Revision

    source
    pub type Revision Int

    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 Compare for Revision
    impl Eq for Revision
    impl Hash for Revision
    impl Show for Revision

    Revision::get

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

    Get the integer value of the revision.

    Revision::inner

    source
    #deprecated("Use `struct T(A)` to declare a newtype and use `.0` access the underlying type instead.")
    fn Revision::inner(self : Revision) -> Int
    Convert newtype to its underlying type, automatically derived.

    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