undoredo and maplike: New Rust Libraries
Category:
In our previous blog
post we mentioned
that we have spun off and published some parts of Topola as standalone Rust
libraries. In this development update, we will introduce two of
these libraries, undoredo and
maplike.
undoredo
Undo and redo are basic operations that are widely expected by users to be present in any interactive design software. The animation below shows them in an earlier version of Topola.
Usually, these operations are implemented using the Command pattern. For each command, there is some programmer-defined application logic code for performing (doing or redoing it) and reversing (undoing) it. But this is however inconvenient: pieces of application logic to perform and reverse a command has to be kept in sync with each other and the rest of code, which is easy to get subtly wrong and can thus result in elusive bugs.
undoredo takes a different approach.
It records sparse deltas
(alternative terms: diffs, patches) of changes to your data structures,
or, if you prefer, whole snapshots of past states (also known as the Memento
pattern). There is no undo-redo
application logic to maintain, thus preventing bugs from occuring. No code,
no bugs.
Delta-based undo-redo is much cheaper in memory (and often in computation) than
snapshotting, but it needs a delta type for each data structure. For custom data
types, undoredo provides a powerful
#[derive(Delta)]
macro that generates their delta types automatically.
The animation below shows undo and redo over polygons that are added and subtracted while an R-tree keeps spatial indexes up to date. Neither commands nor full snapshots are stored; every edit in the history is a sparse delta of the polygon container and of the associated R-tree:
maplike
undoredo needs to be able to operate over containers in a uniform way: insert
a key, remove a key, iterate entries, and so on, whether the container is a map,
vec, or something more exotic.
maplike is a library that
provides a set of Rust traits for abstract containers and operations
over them. Roughly speaking, it is Rust’s counterpart to Python’s
collections.abc, with
traits not only for kinds of containers, but also for individual operations.
Every container is treated as if it was a map. The same code can work on a
B-tree maps, hash maps, vecs, deques, but also smart pointers, optional types,
and so on.