Rethink `ZipperValues::val_at` for computed / algebraic zippers

[marcin-rzeznicki]

Problem

The current ZipperValues trait is defined roughly as:

pub trait ZipperValues<V> {
    fn val(&self) -> Option<&V>;

    fn val_at<K: AsRef<[u8]>>(&self, path: K) -> Option<&V>;
}

This works well for zippers backed by a concrete trie, where values already exist in storage and both methods can return references into that storage.

However, this becomes problematic for computed or algebraic zippers, such as a virtual SubtractZipper<A, B> representing A - B.

At the current focus, SubtractZipper can cache the computed value internally, so implementing:

fn val(&self) -> Option<&V>

is straightforward.

For val_at, however, subtraction may need to construct a new value:

match lhs_val.psubtract(&rhs_val) {
    AlgebraicResult::None => None,
    AlgebraicResult::Identity(...) => lhs_val,
    AlgebraicResult::Element(v) => ??,
}

In the Element(v) case, v is newly created by the operation. It cannot be returned as &V, because it is only a temporary local value.

This means the current val_at(&self) -> Option<&V> contract assumes that every value queried through a zipper already has stable backing storage, which is not true for virtual/computed zippers.

Possible solutions

Option 1: Return Cow<'_, V> from val_at

Change the API to something like:

fn val_at<K: AsRef<[u8]>>(
    &self,
    path: K,
) -> Option<Cow<'_, V>>
where
    V: Clone;

This naturally represents both cases:

Cow::Borrowed(value)

when the result already exists in the underlying trie, and:

Cow::Owned(value)

when an algebraic zipper needs to synthesize a new value.

For example, subtraction could implement:

match lhs_val.psubtract(&rhs_val) {
    AlgebraicResult::None => None,

    AlgebraicResult::Identity(mask) if mask == SELF_IDENT => {
        lhs_val.map(Cow::Borrowed)
    }

    AlgebraicResult::Element(v) => {
        v.map(Cow::Owned)
    }

    _ => unreachable!(),
}

Advantages

• val_at works uniformly for concrete and computed zippers.
• The return type accurately describes the semantics: a value may either be borrowed or synthesized.
• Callers can usually treat Cow<V> similarly to &V via Deref.
• Computed zippers do not need artificial caches or interior mutability.

Disadvantages

• Changes the existing API for all ZipperValues implementations and callers.
• Introduces Cow into a relatively low-level zipper interface.
• May require a V: Clone bound, depending on how the API is structured.
• Callers that only deal with concrete zippers now receive a more general type than they actually need.

---

Option 2: Split focused-value and arbitrary-path value capabilities

The issue also suggests that val() and val_at() may represent two fundamentally different capabilities.

val() queries the zipper's current focus. A virtual zipper can maintain/cache the value at its focus.

val_at() queries an arbitrary descendant without moving the zipper. A computed zipper may need to synthesize that result dynamically.

We could therefore split the trait:

pub trait ZipperValue<V> {
    fn val(&self) -> Option<&V>;
}

pub trait ZipperValues<V>: ZipperValue<V> {
    fn val_at<K: AsRef<[u8]>>(
        &self,
        path: K,
    ) -> Option<&V>;
}

Concrete trie zippers could continue implementing ZipperValues<V> exactly as they do today.

Computed zippers such as SubtractZipper could implement only:

ZipperValue<V>

unless they can provide stable references for arbitrary paths.

If arbitrary-path access to computed values is needed, we could add a separate capability, for example:

pub enum ValueRef<'a, V> {
    Borrowed(&'a V),
    Owned(V),
}

pub trait ZipperComputedValues<V> {
    fn val_at<K: AsRef<[u8]>>(
        &self,
        path: K,
    ) -> Option<ValueRef<'_, V>>;
}

or use Cow<'_, V> there instead.

Advantages

• Preserves the existing zero-copy Option<&V> API for concrete zippers.
• Makes the capability distinction explicit.
• Computed zippers do not have to implement an operation they cannot naturally support.
• Avoids imposing Cow or ownership semantics on all zipper users.

Disadvantages

• Adds another trait/capability to the zipper API.
• Generic code that currently requires ZipperValues<V> may need to reconsider whether it actually needs val_at.
• Code that needs arbitrary-path access across both concrete and computed zippers may still require another abstraction.

Why not cache values returned by val_at?

A SubtractZipper could theoretically cache synthesized values by path and then return references into that cache.

However, this seems undesirable:

• val_at(&self) would require interior mutability.
• A normal RefCell/RwLock cache cannot trivially return a plain &V after releasing its guard.
• Stable-reference storage would require something closer to an arena or append-only allocation scheme.
• The cache could grow with every queried path.
• This adds significant complexity merely to preserve an API contract that does not naturally fit computed zippers.

Therefore, caching arbitrary val_at results does not appear to be a good general solution.

Question

Which API direction do we prefer?

1. Generalize val_at to return Cow<'_, V>, allowing both borrowed and synthesized values through one interface.

2. Split the trait, keeping val() -> Option<&V> as the basic capability and reserving the current reference-returning val_at() for zippers backed by stable value storage.

A hybrid is also possible: split the traits first, then provide a separate computed-value val_at capability returning Cow<'_, V> or a custom Borrowed | Owned enum.

The decision mainly depends on whether we consider arbitrary-path value lookup an essential operation that should work uniformly across all zipper types, or an optional capability of zippers with suitable backing storage.

[luketpeterson]

I remember we (mainly Adam & I) had this discussion 18 months ago... I can't seem to find the notes. But essentially it tracked a lot of what you wrote.

I don't like Cow because it adds runtime overhead to an essentially compile-time distinction (some zipper / trie types store refs, others need to make them on the fly)

The _at was a small nudge towards an API that takes relative path arguments for a lot of functionality. We could move all of the _at APIs into their own trait. And maybe that should be how we organize them anyway.

I don't love the thought of what has to happen behind the scenes to make val work, i.e. keeping temporary memory for one value, computing it as needed, tracking whether it's stale. That certainly would work. But I don't love it.

My personal preference is yet more Zipper traits. Basically split the trait capable of returning z.val() -> &V from the trait that returns z.val_owned() -> V. Since V must implement clone, a default impl is always possible for the owned flavor.

[marcin-rzeznicki]

@luketpeterson Ok, this looks like a good approach. Will try to do it that way

[marcin-rzeznicki]

@luketpeterson I started to think that splitting the API into ZipperValue<V> and ZipperValueOwned<V> solves the immediate lifetime problem, but at a fairly significant cost to composability.

My main concern is that it forces every generic caller to choose between the borrowed and owned capability.

Suppose we currently have an algorithm like:

fn foo<V, Z>(zipper: &mut Z)
where
    Z: ZipperMoving + ZipperValue<V>,
{
    // ...
    if let Some(value) = zipper.val() {
        // ...
    }
}

If a computed zipper such as SubtractZipper<V, A, B> implements only ZipperValueOwned<V>, then it can no longer be used with foo, even though it is perfectly capable of exposing a value at its current focus.

This would effectively divide zipper implementations into two families:

borrowed-value zippers
owned-value zippers

and generic algorithms would either have to choose one family or acquire additional abstraction solely to support both.

That feels disproportionate to the original problem.

The important distinction, in my view, is not really borrowed vs owned values. It is:

value at the current focus
vs.
value at an arbitrary relative path

A computed zipper can support the first operation naturally.

For example, SubtractZipper can compute the value whenever its focus changes and cache that single value internally. There is a stable location inside the zipper from which the reference can be returned.
The problematic operation is specifically:

fn val_at(&self, path: ...) -> Option<&V>

because it may synthesize a new value for an arbitrary path without having anywhere stable to store it.

So I would prefer splitting the existing trait along that boundary:

pub trait ZipperValue<V> {
    fn val(&self) -> Option<&V>;
}

pub trait ZipperValueAt<V>: ZipperValue<V> {
    fn val_at<K: AsRef<[u8]>>(&self, path: K) -> Option<&V>;
}

This preserves the most useful common capability.

Concrete zippers can implement both:

ZipperValue<V>
ZipperValueAt<V>

while computed/algebraic zippers can still implement:

ZipperValue<V>

and therefore continue to work with all generic algorithms that only inspect the current focus.

Only algorithms that genuinely require arbitrary-path lookup need the stronger bound:

Z: ZipperValueAt<V>

This also seems to describe the actual semantics more accurately.

val() is fundamentally part of the zipper state: the zipper has a focus and can maintain whatever information is necessary to represent the value at that focus.

val_at() is an additional random-access capability. It assumes that values at arbitrary descendant paths can be returned through stable references without moving the zipper. That assumption does not hold for every virtual or algebraic zipper.

If we later decide that computed arbitrary-path lookup is useful, we can add a separate owned operation such as:

pub trait ZipperValueAtOwned<V> {
    fn val_at_owned<K: AsRef<[u8]>>(&self, path: K) -> Option<V>;
}

and concrete implementations could trivially provide it through:

self.val_at(path).cloned()

But I would avoid making owned-vs-borrowed the primary division in the zipper API.

In short, I think the capability hierarchy should be:

ZipperValue<V>
    val() -> Option<&V>

ZipperValueAt<V>: ZipperValue<V>
    val_at() -> Option<&V>

rather than:

ZipperValue<V>
    val() -> Option<&V>

ZipperValueOwned<V>
    val_owned() -> Option<V>

The former preserves compatibility and generic composability while isolating exactly the operation that cannot naturally be implemented by computed zippers.