Zipper Combinators and Abstract Tries

In the prior Zipper section, we introduced zipper types that move over a concrete trie in memory. However zippers may also reference (and often move within) tries that are defined parametrically. These are called "abstract" or "virtual" tries.

Many abstract zipper types work using other zippers as parameters. This allows zippers to be combined to create virtual tries with the desired characteristics.

NOTE: The current set of abstract zippers reflects what we needed to build MORK, as opposed to a deliberate process to create a complete API. If you have ideas or needs that aren't addressed, please consider adding other abstract zippers, or reach out and discuss your use case.

PrefixZipper

[PrefixZipper] wraps another zipper and prepends an arbitrary path prefix to the wrapped zipper's space. This allows creating a virtual trie that appears to be rooted at a different location.

#![allow(unused)]
fn main() {
extern crate pathmap;
use pathmap::{PathMap, zipper::*};

let map: PathMap<()> = [(b"A", ()), (b"B", ())].into_iter().collect();
let mut rz = PrefixZipper::new(b"origin.prefix.", map.read_zipper());
rz.set_root_prefix_path(b"origin.").unwrap();

rz.descend_to(b"prefix.A");
assert_eq!(rz.path_exists(), true);
assert_eq!(rz.origin_path(), b"origin.prefix.A");
assert_eq!(rz.path(), b"prefix.A");
}

OverlayZipper

[OverlayZipper] traverses a virtual trie formed by fusing two other zippers. It combines the path structures of both source zippers, and has configurable value mapping to reconcile the values in the final virtual trie.

#![allow(unused)]
fn main() {
extern crate pathmap;
use pathmap::{PathMap, zipper::*};

let map_a: PathMap<&str> = [(b"shared", "from_a"), (b"only_a", "a_value")].into_iter().collect();
let map_b: PathMap<&str> = [(b"shared", "from_b"), (b"only_b", "b_value")].into_iter().collect();

// Default mapping prefers values from the first zipper
let mut overlay = OverlayZipper::new(map_a.read_zipper(), map_b.read_zipper());

// Access value that exists in both - first zipper takes precedence
overlay.descend_to(b"shared");
assert_eq!(overlay.val(), Some(&"from_a"));

// Access value that exists only in first zipper
overlay.reset();
overlay.descend_to(b"only_a");
assert_eq!(overlay.val(), Some(&"a_value"));

// Access value that exists only in second zipper
overlay.reset();
overlay.descend_to(b"only_b");
assert_eq!(overlay.val(), Some(&"b_value"));
}

PolyZipper

[PolyZipper] is a derive macro that enables creating polymorphic zippers - enum-based zippers that can represent different underlying zipper types and dispatch to the appropriate implementation at runtime. This is conceptually similar to using &dyn trait objects, but with enum-based dispatch.

The macro automatically generates implementations for most zipper traits ([Zipper], [ZipperMoving], [ZipperIteration], etc.) by dispatching each method call to the appropriate variant. Note that [ZipperForking] is intentionally not implemented, as the mapping between child zipper types and output types is not always straightforward and should be implemented manually when needed.

#![allow(unused)]
fn main() {
extern crate pathmap;
use pathmap::{PathMap, zipper::*};

#[derive(PolyZipper)]
enum MyPolyZipper<'trie, V: Clone + Send + Sync + Unpin = ()> {
    Tracked(ReadZipperTracked<'trie, 'trie, V>),
    Untracked(ReadZipperUntracked<'trie, 'trie, V>),
}

let map: PathMap<&str> = [(b"foo", "value1"), (b"bar", "value2")].into_iter().collect();

// Create a PolyZipper from either variant
let mut poly_z = MyPolyZipper::from(map.read_zipper());

// Use like any other zipper
poly_z.descend_to(b"foo");
assert_eq!(poly_z.val(), Some(&"value1"));
}

ProductZipper

[ProductZipper] creates a Cartesian product trie by extending each path in the primary trie with the root of the next secondary trie, recursively for all secondary zippers.

#![allow(unused)]
fn main() {
extern crate pathmap;
use pathmap::{PathMap, zipper::*};

let primary: PathMap<()> = [(b"base-", ())].into_iter().collect();
let secondary: PathMap<()> = [(b"nextA-", ()), (b"nextB-", ()), (b"nextC-", ())].into_iter().collect();

let mut pz = ProductZipper::new(primary.read_zipper(), [secondary.read_zipper(), secondary.read_zipper()]);

// Navigate to value in the third factor
pz.descend_to(b"base-nextB-nextA-");
assert_eq!(pz.focus_factor(), 2);
assert!(pz.is_val());
}

ProductZipper Virtual Trie from Example Above