by Witold Wysota

Qt's Undo/Redo framework, introduced in Qt 4.2 makes it possible to equip application users with the means to undo changes made to documents, while providing developers with an easy to use API based on the command pattern.

• Choosing an Approach
• Undo/Redo in Custom Models
• Making Standard Models Undoable
• Ready to Redo

At first glance, combining undo/redo functionality with the model/view framework seems like a daunting task. In this article, we aim to turn what appears to be a challenge into a straightforward task that can be applied to a range of models.

Choosing an Approach

There are two approaches we can take to integrate the model/view and undo frameworks with each other.

• We can build the undo/redo infrastructure on top of the model: undo and redo commands call the QAbstractItemModel API to change the underlying data.
• We can write the model so that it creates commands and pushes them onto an undo stack.

For instance, a QUndoCommand subclass that changes the check states of items might provide this implementation:

    class ChStateCmd : public QUndoCommand{
    public:
      ChStateCmd(const QModelIndex &index, Qt::CheckState s, 
                 QString text, QUndoCommand *parent = 0)
      : QUndoCommand(text, parent), ind(index) {
        Old = qvariant_cast<Qt::CheckState>(
                           index.data(Qt::CheckStateRole));
        New = s;
      }
      void redo() { 
        ind.model()->setData(ind, New, Qt::CheckStateRole);
        ind.model()->setData(ind, New==Qt::Checked 
                ? Qt::green : Qt::red, Qt::BackgroundRole);
      }
      void undo() { 
        ind.model()->setData(ind, Old, Qt::CheckStateRole);
        ind.model()->setData(ind, Old==Qt::Checked 
                ? Qt::green : Qt::red, Qt::BackgroundRole);
      }
    private:
      QPersistentModelIndex ind;
      Qt::CheckState Old, New;
    };

Implementing such a pattern is a minor effort in most cases. However, main drawback is that if something calls your model directly without interfacing through the undo/redo framework, the undo stack will lose coherence and won't be able to bring the model back to a desired state---some changes will be ignored and some will be overwritten with those stored in the undo stack.

One example where this occurs is with drag and drop. In this situation, it is the view that calls QAbstractItemModel::dropMimeData(), so there is no way of controlling the call or knowing how to undo it. You could subclass the view and try to reimplement some of the routines to try and make it possible to wrap the dropMimeData() call in a command, but this breaks code modularity and, above all, it's just tedious and cumbersome.

At this point it becomes obvious that embedding the undo functionality inside the model itself is a better idea.

Undo/Redo in Custom Models

It is often simpler and easier to build the desired undo infrastructure inside your own custom models. They provide total control over the data and do exactly what you want---there is no risk of missing some vulnerable spot where data gets injected into the model without you knowing.

In this section we'll implement a simple Sudoku model with the ability to undo and redo moves performed by the player. A Sudoku board consists of nine square subfields, each with 9 squares each. The goal of the player is to fill the board with numbers 1--9 so that all numbers within a row, a column and a subfield are unique. For that we'll need a table model with constant size.

An abridged version of our model class looks like this:

    class SudokuBoard : public QAbstractTableModel
    {
      Q_OBJECT
 
      friend class ChangeValueCommand;
      friend class MoveDataCommand;
 
    public:
      SudokuBoard(QObject *parent = 0);
      ...
      bool setData(const QModelIndex &index, ...);
      QStringList mimeTypes() const;
      QMimeData *mimeData(const QModelIndexList &) const;
      bool dropMimeData(const QMimeData *data, ...);
      QUndoStack *undoStack() const;
      Qt::DropActions supportedDropActions () const;
 
    protected:
      void emitDataChanged(const QModelIndex &index)
      { 
        emit dataChanged(index, index); 
      }
 
      QUndoStack *m_stack;
      int m_data[9][9];
    };

As you can see, we keep the undo stack directly within the model so that we have something to work with. Also note the friendship declaration with the two command classes. This allows us to manipulate private model data. As an alternative to this, we could provide a helper class with access to private data and make it emit signals on behalf of the model. This approach is very useful if you use private implementation or if you have many types of commands and want to hide them from the outside world. Here, we only use two commands, so it's easier just to use one class.

    QUndoStack *SudokuBoard::undoStack() const
    { 
        return m_stack; 
    }

    Qt::DropActions SudokuBoard::supportedDropActions() const
    { 
        return Qt::CopyAction | Qt::MoveAction; 
    }

We'll skip the code for the constructor (where we zero all the cells in the table and construct an undo stack), the destructor, and the data() function. As we want to allow the user to drop data on cells, the model needs to inform other components about the kinds of data it can handle. For that we need to reimplement mimeTypes() to return a custom MIME type:

    QStringList SudokuBoard::mimeTypes()
    {
      return QStringList() << "application/x-sudokucell";
    }

Of course, we have to be able to create such drags (for the sake of simplicity we only allow one item to be dragged at once):

    QMimeData *SudokuBoard::mimeData(
               const QModelIndexList &list) const
    {
      if (list.isEmpty()) return 0;
      QMimeData *mime = new QMimeData;
      QModelIndex index = list.at(0);
      QString cell = QString("%1x%2=%3")
                     .arg(index.column())
                     .arg(index.row())
                     .arg(index.data(Qt::DisplayRole));
      QByteArray ba = cell.toAscii();
      mime->setData("application/x-sudokucell", ba);
      return mime;
    }

So far, this is nothing new to the experienced model maker. All that is left to do is write the two methods that perform changes on the model data. This is where the magic begins.

    bool SudokuBoard::setData(const QModelIndex &index,
         const QVariant &val, int role)
    {
      ...
      if (role != Qt::EditRole)
          return false;
      m_stack.push(new ChangeValueCommand(index, val, this));
      return true;
    }

The setData() implementation is pretty simple---we only allow modification using Qt::EditRole and we do that by pushing a ChangeValueCommand object onto the undo stack. Note that we don't emit the dataChanged() signal anywhere---it will be the command's responsibility to do this.

The next step is to implement data dropping in a similar way:

    bool SudokuBoard::dropMimeData(const QMimeData *data, 
         Qt::DropAction action, int row, int column,
         const QModelIndex &par)
    {
      QString str(data->data("application/x-sudokucell"));
      if (str.isEmpty()) return false;
      int c = str[0].toAscii()-'0';
      int r = str[2].toAscii()-'0';
      int v = str[4].toAscii()-'0';
      if (par.data().toInt() == v) return false;
 
      switch (action) {
      case Qt::CopyAction:
        m_stack.push(new ChangeValueCommand(index(par.row(),
                         par.column()), v, this));
        return true;
      case Qt::MoveAction:
        m_stack.push(new MoveDataCommand(index(r, c), 
                         par, this));
        return true;
      default:
        return false;
      }
    }

All that remains for us to do is to implement the commands themselves.

    class ChangeValueCommand : public QUndoCommand
    {
    public:
      ChangeValueCommand(const QModelIndex &index, 
                 const QVariant &value, SudokuBoard *model)
      : QUndoCommand(), m_model(model)
      {
        m_old = index.data(Qt::DisplayRole);
        m_new = value;
        m_row = index.row();
        m_col = index.column();
        setText(QApplication::translate("ChangeValueCommand",
            "Set (%1,%2) to %3").arg(m_col+1)
            .arg(m_row+1).arg(m_new.toInt()));
      }
      void redo()
      {
        QModelIndex index = m_model->index(m_row, m_col);
        m_model->m_data[m_col][m_row] = m_new.toInt();
        m_model->emitDataChanged(index);
      }
      void undo()
      {
        QModelIndex index = m_model->index(m_row, m_col);
        m_model->m_data[m_col][m_row] = m_old.toInt();
        m_model->emitDataChanged(index);
      }
    private:
      SudokuBoard *m_model;
      QVariant m_new, m_old;
      int m_row, m_col;
    };

In the constructor, we store all the needed data, and in redo() and undo() we modify the data and emit a signal using a protected member function of the model. MoveDataCommand is similar---the difference is that we modify both the source and the target cells.

Our Sudoku model is very simple---it is flat and it doesn't allow rows and columns to be added or removed. For a more complex model, more commands are needed, taking into consideration all the model features plus any custom data manipulation methods you may want to add to the model's API. Also, consider the fact that you can create custom commands from outside the model using QUndoStack::beginMacro() for free ---use it to create more complex commands.

Making Standard Models Undoable

Very often we use default models bundled with Qt instead of using our own. In such cases it is not possible to embed the undo/redo functionality inside the model as we don't have access to its internals.

Fortunately we can still have the undo/redo infrastructure inside a model without even touching the original model---we can use a proxy model to manipulate the original model on demand.

Since we only need to provide a one-to-one mapping between indexes, the easiest place to start from is QSortFilterProxyModel. We don't even need to set the filter or do any sorting.

    class UndoRedoProxy : public QSortFilterProxyModel
    {
      friend class UndoRedoProxyHelper;
    public:
      UndoRedoProxy(QObject *parent=0);
      bool setData( ... );
      ...
      QUndoStack *undoStack() const { return m_stack; }
 
    protected:
      virtual QString setDataText(const QModelIndex &, 
                               const QVariant &, int) const;
    private:
      QUndoStack *m_stack;
      UndoRedoProxyHelper *m_helper;
      bool m_cachedResult;
      void setData_helper(const QModelIndex &index,
                          const QVariant &value, int role);
      ...
    };

Again, in our model class we provide access to the undo stack and reimplement methods that perform changes to the model. This time, instead of declaring each of the undo commands as friends of the proxy, let's have a single object of class UndoRedoProxyHelper that will call the private *_helper() methods of the proxy on behalf of commands.

    struct UndoRedoProxyHelper
    {
      UndoRedoProxy *proxy;
      void setData(const QModelIndex &index, 
                   const QVariant &value, int role){
        proxy->setData_helper(index, value, role);
      }
      ...
    };

Helper methods simply call the underlying model's method to perform the desired work and emit proper signals where needed.

    void UndoRedoProxy::setData_helper(const QModelIndex &i,
                        const QVariant &value, int role){
      m_cachedResult = QSortFilterProxyModel::setData(i,
                                              value, role);
      emit dataChanged(i, i);
    }

A boolean variable m_cachedResult helps us return a proper value from methods that are meant to do so. Its use is shown in the public setData() method of the proxy.

    bool UndoRedoProxy::setData( ... ){
      if (!index.isValid() || index.data(role) == value 
                           || value.isNull()) return false;
      SetDataCommand *cmd = new SetDataCommand(index, value,
                                role, m_helper);
      cmd->setText(setDataText(index, value, role));
      m_stack->push(cmd);
      if(!m_cachedResult) delete m_stack->command(0);
      return m_cachedResult;
    }
 
    QString UndoRedoProxy::setDataText(const QModelIndex &,
                           const QVariant &, int) const{
      return tr("Set Data");
    }

When we push a command onto the stack, redo() will be called that will in turn call the helper command which will store the result of the operation on the underlying model in the boolean variable. Then we can return the value obtained to our environment. Note how we delete a command if setData() fails in the source model and how we fetch text for the command using a virtual protected method setDataText(); this makes it possible to add your own descriptions by subclassing the model and reimplementing the respective methods.

Now for the command classes themselves. First, we are going to create a base class for all our commands. It will make it possible to easily operate on the proxy using the auxilliary object.

    class UndoProxyCommand : public QUndoCommand
    {
    public:
      UndoProxyCommand(UndoRedoProxyHelper *h, 
      QUndoCommand *par=0):QUndoCommand(par){ m_helper = h;}
      UndoRedoProxyHelper *helper() const{return m_helper;}
      UndoRedoProxy *proxy() const{return m_helper->proxy;}
    private:
      UndoRedoProxyHelper *m_helper;
    };

You'll find all of the command classes implemented in the code accompanying the article, so we'll only show the simplest: the one that operates on setData().

    class SetDataCommand : public UndoProxyCommand
    {
    public:
      SetDataCommand(const QModelIndex &index, 
                     const QVariant &value, int role,
                     UndoRedoProxyHelper *helper) 
      : UndoProxyCommand(helper)
      {
        m_index = pathFromIndex(index);
        m_value = value;
        m_role = role;
      }
      void undo()
      {
        QModelIndex index = pathToIndex(m_index, proxy()); 
        QVariant old = index.data(m_role);
        helper()->setData(index, m_value, m_role);
        m_value = old;
      }
      void redo()
      {
        QModelIndex index = pathToIndex(m_index, proxy()); 
        QVariant old = index.data(m_role);
        helper()->setData(index, m_value, m_role);
        m_value = old;
      }
    private:
      Path m_index;
      QVariant m_value;
      int m_role;
    };

The Path object and the two functions that operate on it, pathToIndex() and pathFromIndex(), are used to help us operate on hierarchical and quickly-changing models.

The path is used to get a proper model index---as we know, these objects are volatile and we shouldn't store them anywhere. It might be tempting to use QPersistentModelIndex instead but this turns out to be the wrong approach as the index will become invalid if we remove the item it points to. In any case, it wouldn't be possible to operate on a sequence of commands that contain at least one operation that inserts or removes items. Because of that we need a way to store the position of an item without using model indexes.

This is where the previously mentioned functions come in---they convert QModelIndex into an entity that lets us find the item later when we need it. How do you hide pirate treasure so that you know you'll be able to find it later? You bury the coins under a tree, find some object that is easy to locate (like a rock on the beach), and write down set of steps you need to perform to walk from the rock to the tree! "108 paces to the left, 207 paces to the right, 42 paces to the left, dig under the tree that looks like a bottle of rum."

We can do exactly the same with our model. Just take a look at the diagram--- we can store a list of row and column numbers we have to walk through from the root index of the model to reach the item we look for. Path is a list of [row,column] pairs showing us the way through the model.

    typedef QPair<int, int> PathItem;
    typedef QList<PathItem> Path;
 
    Path pathFromIndex(const QModelIndex &index){
      QModelIndex iter = index;
      Path path;
      while(iter.isValid()){
        path.prepend(PathItem(iter.row(), iter.column()));
        iter = iter.parent(); 
      }
      return path;
    }
 
    QModelIndex pathToIndex(const Path &path, 
                            const QAbstractItemModel *model){
      QModelIndex iter;
      for(int i=0;i<path.size();i++){
                  iter = model->index(path[i].first, 
                                      path[i].second, iter);
      }
      return iter;
    }

This allows us to store paths instead of indexes so that we can access the item regardless of how many insert or remove operations have been performed in the meantime. Using this approach it is easy to implement the remaining commands.

There are two things to remember. The first is that, if you delete items, rows or columns, you should save the data of all the items getting deleted (including children) somewhere so that you can later revert the deletion. The second is that it would be nice to be able to set meaningful descriptions of commands pushed on the stack. To do that you can provide methods in the model, that are called each time a command is pushed onto the stack, which should each return a description based on the parameters of the command being executed.

Ready to Redo

You can test the proxy by modifying the Editable Tree Model example that comes with Qt. After you are done playing, why not go and equip some of your previously implemented models with undo/redo capabilities. Have fun!