How can I adapt this reused-storage undo stack pattern from a generic vector to a typed model?

Question

I've been trying to fully digest the undo pattern demoed in Sean Parent's talk "Inheritance Is The Base Class of Evil". The talk covers a number of bases, including C++ move semantics, and the use of concepts to implement polymorphism instead of inheritance, but the delta-undo storage pattern is the one I've been trying to get my head around. Here is a working adaptation of the example Parent gave in his talk:

#include <iostream>
#include <memory>
#include <vector>
#include <assert.h>

using namespace std;

template <typename T>
void draw(const T& x, ostream& out, size_t position)
{
    out << string(position, ' ') << x << endl;
}


class object_t {
public:
    template <typename T>
    object_t(T x) : self_(make_shared<model<T>>(move(x))) {}
    friend void draw(const object_t& x, ostream& out, size_t position)
    { x.self_->draw_(out, position); }
private:
    struct concept_t {
        virtual ~concept_t() = default;
        virtual void draw_(ostream&, size_t) const = 0;
    };
    template <typename T>
    struct model : concept_t {
        model(T x) : data_(move(x)) { }
        void draw_(ostream& out, size_t position) const
        { draw(data_, out, position); }
        T data_; };
    shared_ptr<const concept_t> self_;
};


// The document itself is drawable
using document_t = vector<object_t>;
void draw(const document_t& x, ostream& out, size_t position)
{
    out << string(position, ' ') << "<document>" << endl;
    for (const auto& e : x) draw(e, out, position + 2);
    out << string(position, ' ') << "</document>" << endl;
}

// An arbitrary class
class my_class_t {
    /* ... */
};

void draw(const my_class_t&, ostream& out, size_t position)
{ out << string(position, ' ') << "my_class_t" << endl; }

// Undo management...
using history_t = vector<document_t>;
void commit(history_t& x) { assert(x.size()); x.push_back(x.back()); }
void undo(history_t& x) { assert(x.size()); x.pop_back(); }
document_t& current(history_t& x) { assert(x.size()); return x.back(); }

// Usage example.
int main(int argc, const char * argv[])
{

    history_t h(1);


    current(h).emplace_back(0);
    current(h).emplace_back(string("Hello!"));
    draw(current(h), cout, 0);
    cout << "--------------------------" << endl;

    commit(h);

    current(h).emplace_back(current(h));
    current(h).emplace_back(my_class_t());
    current(h)[1] = string("World");
    draw(current(h), cout, 0);

    cout << "--------------------------" << endl;
    undo(h);
    draw(current(h), cout, 0);

    return EXIT_SUCCESS;
}

Instead of tracking undo as a stack of commands which capture their before and after states, this pattern tracks undo states as a stack of "whole documents" where every entry is, in effect, a complete copy of the document. The trick of the pattern is that, storage/allocations are only incurred for the portions of the document which are different between each state, using some indirection and shared_ptr. Each "copy" only incurs the storage penalty for what's different between it and the prior state.

The pattern in Parent's example shows that the "current" document is completely mutable, but gets committed to the history when you call commit on the history. This pushes a "copy" of the current state onto the history.

In the abstract, I find this pattern compelling. The example Parent presents in this talk was clearly contrived primarily to demonstrate his points about concept-based polymorphism and move semantics. Relative to those, the undo pattern feels ancillary, although I think its role is to point out the value of value semantics.

In the example, the document "model" is just "a vector of objects conforming to the concept". That served it's purpose for the demo, but I'm finding it hard to extrapolate from "vector of concepts" to "real world, typed model." (Let's just say that for the purposes of this question the concept-based polymorphism is not relevant.) So, for instance, consider the following trivial model where the "document" is a company with some number of employees, each with a name, a salary, and a picture:

struct image {
    uint8_t bitmapData[640 * 480 * 4];
};

struct employee {
    string name;
    double salary;
    image picture;
};

struct company {
    string name;
    string bio;
    vector<employee> employees;
};

The question I have is: How can I introduce the indirection necessary to get the storage sharing without losing the ability to interact with the model directly and simply? By simplicity of interaction, I mean that you should be able to continue to interact with the model in a straightforward manner without lots of RTTI or casting, etc. For instance, if you were trying to give everyone named "Susan" a 10% raise, capturing an undo state after every change, a simple interaction might look something like this:

using document_t = company;
using history_t = vector<document_t>;
void commit(history_t& x) { assert(x.size()); x.push_back(x.back()); }
void undo(history_t& x) { assert(x.size()); x.pop_back(); }
document_t& current(history_t& x) { assert(x.size()); return x.back(); }

void doStuff()
{
    history_t h(1);
    for (auto& e : current(h).employees)
    {
        if (e.name.find("Susan") == 0)
        {
            e.salary *= 1.1;
            commit(h);
        }
    }
}

The trick seems to be injecting the indirection provided by object_t, but it's not clear how I can both introduce the necessary indirection and subsequently traverse that indirection transparently. I can generally get around in C++ code, but it's not my everyday language, so this could very well be something dead simple. Regardless, it's unsurprising that Parent's example doesn't cover this since a large part of his point was the ability to hide the type through the use of concepts.

Anyone have any thoughts on this?

Answer 1

While the document is mutable, the objects are not.

In order to edit an object, you need to create a new one.

In a practical solution, each object might be a cooy on write smart pointer holder that you can access either by reading or writing. A write access duplicates the object iff it has a reference count above one.

If you are willing to restrict all mutation to accessor methods, you can do the copy on write in them. If not, the get_writable method does the copy on write. Note that a modification usually implies a modification all the way back to the root as well, so your write method may need to take a path to the root where the copy on write is propagated up to there. Alternatively, you can use a document context and guid equivalent identifiers and a hash map, so editing foo contained in bar leaves bar unchanged, as it identifies foo by its name not a pointer.