undoredo 0.1.1

Incremental-diff undo-redo decorator for collections such as HashMap, BTreeMap, StableVec, thunderdome::Arena.
Documentation

undoredo

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

This approach makes undoredo easier to use than other undo-redo libraries. Storing incremental diffs is much more succint and reliable than the commonly used Command pattern. 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 has no mandatory dependencies. For ease of use, undoredo has built-in implementations for standard library collections, as well as feature-gated convenience implementations for foreign types, StableVec and thunderdome::Arena (read more in Supported collections section).

Usage

First, add undoredo to your Cargo.toml:

[dependencies]
undoredo = "0.1"

Basic usage

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() {
    let mut recorder: Recorder<usize, char, HashMap<usize, char>> = Recorder::new(HashMap::new());
    let mut undoredo: UndoRedo<HashMap<usize, char>> = UndoRedo::new();

    // Push elements while recording this 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')]));
}

Storing and accessing command metadata along with edits

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

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

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

#[derive(Debug, Clone, PartialEq)]
enum Command {
    PushChars,
}

#[test]
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();

    // Push an element while recording.
    recorder.insert(1, 'A');

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

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

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

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

Supported collections

Standard library

Standard library maps HashMap and BTreeMap are supported via built-in implementations.

Convenience implementations on foreign types

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

To use these, specify them next to your undoredo dependency in your Cargo.toml. For example, to enable all foreign implementations, write

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

Technical detail: Unlike maps, which support insertion and removal at arbitrary keys, a stable-vec-style data structure can be only supported if it allows to insert elements at arbitrary indexes, including indexes that are out of bounds at the time of insertion. For StableVec, this is achieved by changing the length before insertion using the .reserve_for() method. With thunderdome::Arena, this is achieved directly by inserting via the .insert_at() method.

Unsupported collections

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

Technical detail: 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.

Contributing

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

Licence

undoredo is dual-licensed as under either of

at your option.