comemo

Standard memoization caches results based on function arguments. If a function takes a large state object (like a file system) as an argument, any change to that state invalidates all cached results.

comemo provides constrained memoization, which uses fine-grained access tracking. Instead of invalidating everything when the state changes, it only invalidates results if the specific parts of the state accessed during the function execution have changed.

To implement this, you follow three steps:

1. Annotate the target function with #[memoize].
2. Annotate the implementation block of the state object with #[track].
3. Wrap the state object argument in the Tracked<T> container.

This allows the system to automatically track which specific methods or data points were accessed during a call and reuse results as long as those specific dependencies remain unchanged.

use comemo::{memoize, track, Tracked};

// 1. Add #[memoize] to the function
#[memoize]
fn evaluate(script: &str, files: Tracked<Files>) -> i32 {
    // ... implementation ...
}

// 2. Add #[track] to the implementation block of the state
#[track]
impl Files {
    fn read(&self, path: &str) -> String {
        // ... implementation ...
    }
}

Comemo requires memoized functions to be reorderably deterministic to ensure efficient cache lookups and correctness.

Definition

If we compare two executions (A and B) of a function:

• In-order determinism (Strict): If the first $N$ tracked calls and their results are identical in A and B, then the $(N+1)^{th}$ call must also be identical. This is often too restrictive for modern code (e.g., multi-threaded code).
• Reorderable determinism (Required): If, for the first $N$ calls in A, B has matching calls (same arguments, same return value) somewhere in its call sequence, then the $(N+1)^{th}$ call invoked by A must also occur somewhere in the call sequence of B.

Consequences

• Debug Mode: If a function is not reorderably deterministic, comemo may panic to alert the developer.
• Release Mode: The function will still yield correct results, but caching may be ineffective (cache misses will occur more frequently).

By default, Tracked<T, C> is invariant over T due to compiler limitations. This can prevent you from creating a chain of tracked types (e.g., a struct containing a Tracked version of itself).

To create a tracked chain or require covariance, you must manually specify the call type using the generic parameter C. Using a 'static lifetime in the associated constraint helps the compiler understand the relationship.

Example of a tracked chain:

struct Chain<'a> {
    // Manually specifying the call type to allow covariance
    outer: Tracked<'a, Self, <Chain<'static> as Track>::Call>,
    data: u32,
}

#[comemo::track]
impl<'a> Chain<'a> {}

// Standard (invariant) usage:
struct Chain<'a> {
    outer: Tracked<'a, Self>,
    data: u32,
}

// Covariant usage for chains:
struct Chain<'a> {
    outer: Tracked<'a, Self, <Chain<'static> as Track>::Call>,
    data: u32,
}

The CallTree<C, T> is a data structure used to associate a value (T) with a key hash and a specific sequence of calls and their return values. It allows for efficient querying of values by traversing the tree using an 'oracle' function that simulates the return values of the calls in the sequence.

Key Operations

• new(): Creates an empty CallTree.
• insert(key, sequence, value): Inserts a new computation path into the tree. This can fail if the sequence is a prefix of an existing path or if the sequence is non-deterministic (missing calls required by an existing path).
• get(key, oracle): Retrieves a value from the tree. The oracle is a closure FnMut(&C) -> u128 that takes a call and returns its expected return hash. The tree follows the path where every call matches the oracle's output.
• retain(predicate): Prunes the tree by removing all values for which the provided predicate returns false. It automatically cleans up unused parent nodes to maintain tree integrity.

// Example conceptual usage
let mut tree = CallTree::new();

// Insert a value with a sequence of calls
// sequence would be a CallSequence<C>
tree.insert(key_hash, sequence, value).unwrap();

// Retrieve a value using an oracle
let retrieved = tree.get(key_hash, |call| {
    // The oracle simulates the return hash for a given call
    get_expected_hash(call)
});

In comemo, dependency tracking is achieved by wrapping a type that implements the Track trait in either a Tracked or TrackedMut wrapper.

• Tracked<'a, T>: Encapsulates an immutable reference to a value. It provides access to the type's tracked API surface via Deref. Only methods defined in an implementation block annotated with #[track] are accessible.
• TrackedMut<'a, T>: Encapsulates a mutable reference. It provides access to the mutable tracked API surface via DerefMut.

When you call methods on these wrappers, comemo records the calls (the Call type) and their results (as a u128 hash). This allows the system to know exactly which parts of a data structure were accessed or mutated, enabling fine-grained memoization.

To start tracking, use the track(), track_mut(), track_with(), or track_mut_with() methods provided by the Track trait.

// Assuming T implements Track via #[track]
let tracked = value.track(); 
// Access tracked methods via deref
tracked.some_tracked_method();

let mut tracked_mut = value.track_mut();
tracked_mut.some_tracked_mutation();

In comemo, the Input<'a> trait defines what constitutes a valid input to a cached function. An input can be one of several types:

1. Hashable types: Any type implementing std::hash::Hash. These are treated as static keys; they do not support tracked calls.
2. Tracked types: Tracked<'a, T> or TrackedMut<'a, T> types. These allow the memoization system to observe and react to specific calls (side effects or data access) made on the input during function execution.
3. Tuples of inputs: Using the Multi wrapper, you can provide multiple inputs (up to twelve) as a single unit. The system will manage the combined calls and keys for the entire tuple.

When using Tracked inputs, the system can use an accelerator to cache the results of specific calls, improving performance during constraint validation traversal.

// Example of the types of inputs supported:
// 1. Simple Hashable
let x: u32 = 42;

// 2. Tracked (requires specific setup via comemo macros)
// let tracked_val = Tracked::new(...);

// 3. Multiple inputs via Multi
// let multi_input = Multi((x, tracked_val));

Comemo provides constrained memoization to enable fine-grained incremental computation. Instead of invalidating all cached results when any input changes, comemo tracks specific dependencies accessed during a function call.

To implement this, follow these three steps:

1. Apply the #[memoize] attribute to the function you want to cache.
2. Wrap any arguments that represent external dependencies (like file systems, databases, or state) in the Tracked<T> container.
3. Apply the #[track] attribute to the impl block of the type used inside the Tracked container to allow comemo to monitor its method calls.

This ensures that a memoized function only re-executes if the specific dependencies it actually accessed have changed.

use comemo::{memoize, track, Tracked};

#[track]
impl Files {
    fn read(&self, path: &str) -> String {
        // ... implementation
        String::new()
    }
}

#[memoize]
fn evaluate(script: &str, files: Tracked<Files>) -> i32 {
    // The function will only re-run if `script` changes 
    // or if the specific files accessed via `files.read()` change.
    0
}

The #[track] procedural macro allows you to make an impl block or a trait trackable by comemo. When applied, it generates the necessary boilerplate to enable memoization of the methods within that block or trait.

Supported Targets

• impl blocks: You can apply #[track] to an implementation block. All methods within the block must be either all mutable (&mut self) or all immutable (&self).
• traits: You can apply #[track] to a trait definition. This makes the trait trackable via a dynamic dispatch mechanism.

Constraints and Requirements

To use #[track], the following rules must be satisfied:

For impl blocks:

• No Type Generics: The impl block cannot use type generics (e.g., impl<T> MyStruct<T>).
• No Const Generics: The impl block cannot use const generics.
• Method Uniformity: You cannot mix mutable (&mut self) and immutable (&self) methods in a single #[track] block.

For all methods (within impl or trait):

• Must take self by reference: Methods must take &self or &mut self. They cannot take self by value.
• No Unsafe/Async/Const: Methods cannot be unsafe, async, or const.
• No Generics: Methods cannot be generic (except for lifetimes).
• No Mutable Parameters: Arguments cannot be passed as mutable references (e.g., &mut T is not allowed; use &T).
• No Mutable Return Values: Methods cannot return mutable references (&mut T).
• Immutable Method Return Values: If the method is immutable (&self), it can return values, but if the method is mutable (&mut self), it cannot have a return value.
• Simple Identifiers: Arguments must be simple identifiers (no complex patterns like Some(x) in the argument list).

Usage Example

#[track]
impl MyStruct {
    fn compute(&self, x: u32) -> u32 {
        x * 2
    }
}

The #[memoize] procedural macro automatically rewrites a function or method to use an internal cache. When the function is called, comemo checks if the result for the given arguments is already cached; if so, it returns the cached value instead of re-executing the body.

Requirements

• Target: The macro can only be applied to functions and methods.
• Arguments: All function arguments must be either Hashable or Trackable (verified via ::comemo::internal::assert_hashable_or_trackable).
• Immutability: Memoized functions cannot have mutable parameters. This includes both mut identifiers in the function signature and mutable references (e.g., &mut T).
• Simplicity: Only simple identifiers are supported as argument patterns (no complex destructuring).

#[memoize]
fn compute_expensive_value(x: u32, y: u32) -> u32 {
    // This body will only run if (x, y) is not in the cache
    x + y
}