undoredo is an undo-redo Rust library that works by wrapping a collection inside a recorder decorator that observes the incoming insertions, removals and pushes while recording the changes in an invertible and reversible incremental diff structure.

This recorder decorator approach makes undoredo easier to use than other undo-redo libraries. Storing incremental diffs typically results in much more succint and reliable code than the commonly used Command pattern, which is what the popular and venerable undo and undo_2 crates use. The programmer is relieved from having to maintain application-specific implementations of commands, often complicated and prone to elusive runtime bugs, on which the Command pattern has to operate.

This library is no_std-compatible and has no mandatory dependencies except for alloc. For ease of use, undoredo has convenience implementations for standard library collections, HashMap and BTreeMap, and for some foreign feature-gated types: StableVec, thunderdome::Arena and rstar::RTree (read more in Supported collections section).

First, add undoredo to your Cargo.toml:

[dependencies]
undoredo = "0.2"

Following is a basic usage example of undoredo over std::collections::HashMap. You can find more examples in the examples/ directory.

use std::collections::HashMap;
use undoredo::{Insert, Recorder, UndoRedo};

fn main() {
    // The recorder records the ongoing changes to the underlying collection.
    let mut recorder: Recorder<usize, char, HashMap<usize, char>> = Recorder::new(HashMap::new());

    // The undo-redo struct maintains the undo-redo bistack.
    let mut undoredo: UndoRedo<HashMap<usize, char>> = UndoRedo::new();

    // Push elements while recording the changes in an edit.
    recorder.insert(1, 'A');
    recorder.insert(2, 'B');
    recorder.insert(3, 'C');

    // Flush the recorder and commit the recorded edit of pushing 'A', 'B', 'C'
    // into the undo-redo history.
    undoredo.commit(recorder.flush());

    // The pushed elements are now present in the collection.
    assert!(*recorder.collection() == HashMap::from([(1, 'A'), (2, 'B'), (3, 'C')]));

    // Now undo the action.
    undoredo.undo(&mut recorder);

    // The collection is now empty; the action of pushing elements has been undone.
    assert!(*recorder.collection() == HashMap::from([]));

    // Now redo the action.
    undoredo.redo(&mut recorder);

    // The elements are back in the collection; the action has been redone.
    assert!(*recorder.collection() == HashMap::from([(1, 'A'), (2, 'B'), (3, 'C')]));

    // Once you are done recording, you can dissolve the recorder to regain
    // ownership and mutability over the underlying collection.
    let (mut hashmap, ..) = recorder.dissolve();
    assert!(hashmap == HashMap::from([(1, 'A'), (2, 'B'), (3, 'C')]));
}

It is often desirable to store some metadata along with every recorded edit, usually a representation of the command that originated it. This can be done by instead committing the edit using the .cmd_commit() method.

The bistack of done and undone committed edits, together with their command metadatas ("cmd") if present, can be accessed as slices from the .done() and .undone() accessor methods.

use std::collections::HashMap;
use undoredo::{Insert, Recorder, UndoRedo};

// Representation of the command that originated the recorded edit.
#[derive(Debug, Clone, PartialEq)]
enum Command {
    PushChar,
}

fn main() {
    let mut recorder: Recorder<usize, char, HashMap<usize, char>> = Recorder::new(HashMap::new());
    let mut undoredo: UndoRedo<HashMap<usize, char>, Command> = UndoRedo::new();

    recorder.insert(1, 'A');
    recorder.insert(2, 'B');

    // Commit `Command::PushChar` enum variant as command metadata ("cmd") along
    // with the recorded edit.
    undoredo.cmd_commit(Command::PushChar, recorder.flush());

    // `Command::PushChar` is now the top element of the stack of done cmd-edits.
    assert_eq!(undoredo.done().last().unwrap().cmd, Command::PushChar);

    undoredo.undo(&mut recorder);

    // After undo, `Command::PushChar` is now the top element of the stack of
    // undone cmd-edits.
    assert_eq!(undoredo.undone().last().unwrap().cmd, Command::PushChar);
}

Some data structures have set semantics: they operate only on values, without exposing any usable notion of key or index. undoredo can provide its functionality to a set by treating it as a ()-valued map whose keys are the set's values. This is actually also how Rust's standard library represents HashSet and BTreeSet internally.

As an example, the following code will construct a recorder and an undo-redo bistack for a BTreeSet:

let mut recorder: Recorder<usize, char, BTreeSet<char, ()>> = Recorder::new(BTreeSet::new());
let mut undoredo: UndoRedo<BTreeSet<char, ()>> = UndoRedo::new();

Keeping in mind to pass values as keys, recorder and undoredo can then be used the same way as with maps above. See examples/btreeset.rs for a complete example.

Among the supported foreign types, rstar::RTree is an instance of a data structure with a convenience implementation over set semantics. See examples/rstar.rs for an example of its usage.

NOTE: Some set-like data structures are actually multisets: they allow to insert the same value multiple times without overriding the first one. In fact, rstar::RTree is a multiset. undoredo will work correctly with such data structures, seeing them as sets, but only if you never make use of their multiset property: you must never insert a value to the collection that is already there.

Rust's standard library maps and sets are supported via built-in convenience implementations:

• HashMap behind the std feature (enabled by default),
• HashSet behind the std feature (enabled by default),
• BTreeMap (not feature-gated),
• BTreeSet (not feature-gated).

In addition to the standard library, undoredo has built-in feature-gated convenience implementations for data structures from certain external crates:

• stable_vec::StableVec behind the stable-vec feature. (example usage: examples/stable_vec.rs),
• thunderdome::Arena behind the thunderdome feature. (example usage: examples/thunderdome.rs),
• rstar::RTree behind the rstar feature. (example usage: examples/rstar.rs).

To use these, enabled their features next to your undoredo dependency in your Cargo.toml. For example, to enable all foreign type implementations, write

[dependencies]
undoredo = { version = "0.2", features = ["stable-vec", "thunderdome", "rstar"]}

Technical sidenote: Unlike maps and sets, not all stable vec data structures allow insertion and removal at arbitrary indexes regardless of whether they are vacant, occupied or out of bounds at the time of insertion. For StableVec, we managed to implement inserting at out-of-bound indexes by changing the length before insertion using the .reserve_for() method. For thunderdome::Arena, we insert at arbitrary key directly via the .insert_at() method. Collections for which we could not achieve this are documented in the section below.

Slab, SlotMap, generational-arena cannot be supported because they lack interfaces for insertion at an arbitrary key.

Technical sidenote: For Slab, such interface is missing apparently because the freelist Slab uses to keep track of its vacant indexes is only singly-linked, not doubly-linked. Inserting an element at an arbitrary vacant index would require removing that index from the freelist. But since there is no backwards link available at a given key, doing so would require traversing the freelist from the beginning to find the position of the previous node, which would incur an overly slow O(n) time cost.

We welcome issues and pull requests from anyone both to our canonical repository on Codeberg and to our GitHub mirror.

NOTE: This repository contains a Git submodule: src/maplike. After git clone, remember to run

git submodule update --init

We share the src/maplike module with another crate, rstared, via a Git submodule instead of making it a Cargo dependency because we are not yet sure how it should be called and what interface it should have.

undoredo is dual-licensed as under either of

• MIT license,
• Apache License, Version 2.0.

at your option.