Crate topo

topo provides stable callgraph identifiers for implementing higher level Incremental Computing abstractions like those in the moxie crate.

Scoping queries with CallIds

There are several ways this crate’s caches can be indexed, but for incrementally computing repetitive hierarchical structures (like UI trees) it can be very useful to describe cache queries in terms of a function’s abstract “location” within the runtime callgraph.

To extract CallIds from code, the runtime callgraph must be “annotated” with invocations of call, call_in_slot, and user-defined nested-annotated functions. Each of these enters the scope of a child CallId when called, causing CallId::current calls in that inner scope to return the new CallId.

CallIds are deterministic and unique based on the preceding chain of parent CallIds and data slots. Every chain has a root, either defined implicitly by making a call without a parent, or explicitly by calling root. By controlling the creation of roots, a runtime can ensure that aside from changes to the executed graph itself, subsequent calls to the same function will produce the same CallIds.

Example

use topo::{call, root, CallId};

let returns_two_ids = || {
    let first = call(|| CallId::current());
    let second = call(|| CallId::current());
    assert_ne!(first, second, "these are always distinct calls");
    (first, second)
};

// running the closure as a nested call(...) gives different siblings
assert_ne!(call(returns_two_ids), call(returns_two_ids));

// a call to root(...) gives each of these closure calls an identical parent CallId
assert_eq!(root(returns_two_ids), root(returns_two_ids));

Caching slots

call_in_slot allows one to specify a “slot” – a runtime value that represents the call’s “location” within its parents scope. This is particularly useful for creating CallIds for child calls in collections whose iteration order does not map exactly to the child’s logical scope.

An example might be a list of users where usernames are stable and their associated resources should be cached by username, but the list order and length change in ways unrelated to usernames. The username would be used as the slot to prevent destruction and recreation of username-associated resources when the list order changes.

use topo::{call_in_slot, CallId};

let get_name_id = |name| call_in_slot(name, || CallId::current());

// reusing the same slot will get the same CallId
let bob = get_name_id("bob");
let bob_again = get_name_id("bob");
assert_eq!(bob, bob_again);

// different names produce different slots
let alice_hello = get_name_id("alice");
assert_ne!(bob, alice_hello);

Internally, slots are interned in a global [dyn-cache].

Structs

CallId

Identifies the scope of a nested function call in a way that can be deterministically reproduced across multiple executions.

Functions

call

Calls the provided function as a child of CallId::current, using for a slot the number of times the given source location has been called during the current parent’s scope.

call_in_slot

Calls the provided function as a child of CallId::current, using slot as an input for the new CallId.

root

Calls the provided function as the root of a new call tree, ignoring the current CallId.

Attribute Macros

nested

Gives a function a unique CallId in its caller’s topology by applying #[track_caller] to the function and wrapping its body in call or call_in_slot if the slot parameter is given.