undoredo

undoredo is a Rust library that implements Undo/Redo functionality on arbitrary data structures automatically recording sparse deltas of changes (deltas are sometimes also called patches) or whole snapshots of past states (Memento pattern).

This approach is much easier than the commonly used (Command pattern), which is used by other Undo/Redo crates, as it does not require maintenance of any additional application logic, which can lead to elusive bugs. Nonetheless, undoredo can also store a command or other metadata along with every edit, allowing easy implementation of the Command pattern as well.

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

Usage

First, add undoredo as a dependency to your Cargo.toml:

[dependencies]
undoredo = "0.9"

Basic usage

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

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

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

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

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

    // Flush the recorder and commit the recorded delta of pushing 'A', 'B', 'C'
    // into the undo-redo bistack.
    undoredo.commit(&mut recorder);

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

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

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

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

    // The elements are back in the container; the action has been redone.
    assert!(*recorder.container() == 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 recorded container.
    let (mut hashmap, ..) = recorder.dissolve();
    assert!(hashmap == HashMap::from([(1, 'A'), (2, 'B'), (3, 'C')]));
}

Storing and accessing command metadata along with deltas

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

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

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

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

fn main() {
    let mut recorder: Recorder<HashMap<usize, char>> =
        Recorder::new(HashMap::new());
    let mut undoredo: UndoRedo<Delta<BTreeMap<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 delta.
    undoredo.cmd_commit(Command::PushChar, recorder.flush_delta());

    // `Command::PushChar` is now the top element of the stack of done cmd-deltas.
    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-deltas.
    assert_eq!(undoredo.undone().last().unwrap().cmd, Command::PushChar);
}

Undo-redo on maps with pushing

Some data structures with map semantics also provide a special type of insertion where a value is inserted without specifying a key, which the structure instead automatically generates and returns by itself. This operation is called "pushing".

If a supported type has a push interface, you can record its changes just as easily as insertions and removals by calling .push() on the recorder, like this:

recorder.push('A');

StableVec and thunderdome::Arena are instances of supported pushable maps. examples/stable_vec.rs and examples/thunderdome.rs for complete examples of their usage.

Undo-redo on sets

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 internally represents its two set types, HashSet and BTreeSet.

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

let mut recorder: Recorder<BTreeSet<char>> = Recorder::new(BTreeSet::new());
let mut undoredo: UndoRedo<Delta<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 third-party 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 key that is already present in a multiset.

Undo-redo on custom types

To make undoredo work with a map-like data structure for which there is no convenience implementation, you can create one on your own by implementing the traits from the maplike crate. Refer to that crate's documentation for details. These traits are also re-exported by undoredo, so it is not necessary to add another dependency.

If you believe that other people could benefit from your implementation, consider contributing it to maplike. We will integrate it in undoredo on our own afterwards (no need to open more than one pull request).

Supported containers

Standard library

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

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

Third-party types

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

stable_vec::StableVec, gated by the stable-vec feature (example usage: examples/stable_vec.rs),
thunderdome::Arena, gated by the thunderdome feature (example usage: examples/thunderdome.rs);
rstar::RTree, gated by the rstar feature (example usage: examples/rstar.rs);
rstared::RTreed, gated by the rstared feature (example usage: examples/rstared.rs).

To use these, enable their corresponding features next to your undoredo dependency in your Cargo.toml. For example, to enable all third-party type implementations, write

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

Unsupported containers

Some containers cannot be supported because they lack an interface on which maplike's traits could be implemented. See the Unsupported containers section in maplike's documentation for details.

Documentation

See the documentation for more information on undoredo's usage.

Packaging

undoredo is published as a crate on the Crates.io registry.

Contributing

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

Licence

Outbound licence

undoredo is dual-licensed as under either of

at your option.

Inbound licence

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this work by you will be dual-licensed as described above, without any additional terms or conditions.

undoredo 0.9.8