Undo stack

[tobiasBora]

I would love to bring an undo/redo stack to a dexie.js based app. I saw that dexie.js implements transactions, would it be technically possible to use this to define a "commit" of the database, and provide functions to list and move between commits? I don't know the internals of Dexie.js, but I'm thinking that it might already provide the notion of commits to achieve synchronization between client and server?

One might also be interested by this (sadly abandoned) project https://gitlab.com/onezoomin/bygonz/bygonz/

[dfahlander]

In dexie-cloud-addon we use a middleware to track all operations on the transaction and subscribe to the transaction's commmitted event to store the operations in a dedicated table for logging them. However, dexie-cloud-addon will cleanse out all old operations once they have been synced, so it would not work for an undo buffer. Moreover it doesn't keep the old value of the operation.

Don't know if your undo buffer need to be persisted or not? In any case, I think it would be best to do something similar.

1. Create a middleware that overrides the mutate method.
2. In the overrided version of mutate switch on req.type and query the existing value using the same transaction before sending on the mutation. Put this data in an array on a WeakMap associated with the transaction, (or as an expando prop on the trans object itself).
3. If transaction aborts, discard the operations from memory (if this is in-memory only, if persisted, they will automatically discard with the transaction being aborted)
4. In case of peristed undo buffer: When transaction commits, store the collected data into some custom table.

If the undo buffer should be persistent you would also need to:

1. Override schema declaration and add your custom table for tracking undo buffer:

   function undoAddon(db: Dexie) {
     db.Version.prototype['_parseStoresSpec'] = Dexie.override(
       dexie.Version.prototype['_parseStoresSpec'],
       (origFunc) => function (stores: {[tableName: string]: string}, dbSchema: DbSchema) {
         const storesClone = {
           $undoBuffer: '++id',
           ...stores
         };
         return origFunc.call(this, storesClone, dbSchema);
       }
     );
   
     ...
   }

2. Forcibly include the '$undoBuffer' in all write transactions:

   db.use({
     stack: "dbcore",
     name: "UndoMiddleware",
     create (downlevelDatabase) {
       // Return your own implementation of DBCore:
       return {
         // Copy default implementation.
         ...downlevelDatabase, 
         // Overrides
         transaction (stores, mode, ...rest) {
           if (mode === 'readwrite') {
             return downlevelDatabase.transaction(['$undoBuffer', ...stores], mode, ...rest);
           } else {
             return downlevelDatabase.transaction(stores, mode, ...rest);
           }
         },
         ...
       };
     }
   });

[tobiasBora]

Awesome, thanks a lot for the tricks, I'll see how far I can go. Would be great to have it natively in Dexie.js!

[dfahlander]

It would be nice with an addon for it. I've got the same question before.

[dfahlander]

In your case, would you prefer an in-memory undo buffer or a persistent one?

[tobiasBora]

In my case an in-memory undo buffer would be good enough I'd say.

[tobiasBora]

So I tried to start experimenting, and I got undo/redo for delete operation working with this:

import type { DBCore, DBCoreMutateRequest } from 'dexie';
import { PlanotoFileDexie } from '$lib/database/db';

type MyExtendedDBCoreMutateRequest = DBCoreMutateRequest & {
  myUndoTransactionsToApply?: ((db: PlanotoFileDexie) => void)[]
  myRedoTransactionsToApply?: ((db: PlanotoFileDexie) => void)[]
};

export function undoMiddleware() {
  let undoArray : MyExtendedDBCoreMutateRequest[] = [];
  let redoArray : MyExtendedDBCoreMutateRequest[] = [];
  return {
    undo: async (db : PlanotoFileDexie) => {
      const x = undoArray.pop();
      if(x && x.myUndoTransactionsToApply) {
        await Promise.all(x.myUndoTransactionsToApply.map(action => action(db)));
        if(x.myRedoTransactionsToApply) {
          redoArray.push(x);
        }
      };      
    },
    redo: async (db : PlanotoFileDexie) => {
      const x = redoArray.pop();
      if(x && x.myRedoTransactionsToApply) {
        await Promise.all(x.myRedoTransactionsToApply.map(action => action(db)));
        undoArray.push(x);
      };      
    },
    create: (downlevelDatabase: DBCore) => {
      console.log("Euh I am a middleware");
      // Return your own implementation of DBCore:
      return {
        // Copy default implementation.
        ...downlevelDatabase, 
        // Override table method
        table (tableName: string) {
          console.log("I am in my custom table method");
          // Call default table method
          const downlevelTable = downlevelDatabase.table(tableName);
          // Derive your own table from it:
          return {
            // Copy default table implementation:
            ...downlevelTable,
            // Override the mutate method:
            mutate: async (req: MyExtendedDBCoreMutateRequest) => {
              switch (req.type) {
                case "delete":
                  console.log("We will delete items ", req.keys);
                  await Promise.all(req.keys.map(async (id) => {
                    console.log("start with ", id);
                    if(undoArray[undoArray.length - 1] != req) {
                      console.log("New transaction");
                      undoArray.push(req);
                    }
                    if(!req.myUndoTransactionsToApply) {
                      req.myUndoTransactionsToApply = [];
                    }
                    if(!req.myRedoTransactionsToApply) {
                      req.myRedoTransactionsToApply = [];
                    }
                    const elmt = await downlevelTable.get({trans: req.trans, key: id});
                    req.myUndoTransactionsToApply.push(db => db.table(tableName).add(elmt));
                    req.myRedoTransactionsToApply.push(db => db.table(tableName).delete(id));
                  }));
                  ;
                case "add":
                  ;
                case "put":
                  ;
              };
              return downlevelTable.mutate(req);
            }
          }
        }
      }
    }
  }
}

Is it what you had in mind and correctly performed? There are multiple things I'm not sure how to deal with right now:

• For now I don't use mutatedParts nor criteria… and I don't even know what this is. Is it something I should worry about?
• You mention If transaction aborts, discard the operations from memory, but how can you detect that the transaction aborted?

I'm also a bit worried about efficiency, like I don't know if req.myUndoTransactionsToApply.push(db => db.table(tableName).add(elmt)); might take lot's of space in memory (and this certainly can't be put inside an indexeddb), so I'm thinking that it might be worth finding an encoding of this inside a regular object… but let's see how it goes. I'll now try to make it work for others.

But for this I have quite a few questions:

• In the Add version, is values and keys supposed to have the same size and correspond to the same values? And same, what should I do with mutatedParts and wantResults
• The DBCorePutRequest seems significantly more complicated with changeSpec, updates… what is this exactly? (I would maybe need it for the redo part, or maybe I can get the value after the mutation? Need to try)

[tobiasBora]

So I tried here to implement the add, seems to work so far, hope I have not forgotten weird edge cases. And now I realized that we don't need to furnish both an undo and redo command, the redo can be determined automatically when we play the undo:

// Create an undo mechanism based on recommendations I got from https://github.com/dexie/Dexie.js/issues/1933
// This is a middleware as defined in https://dexie.org/docs/Dexie/Dexie.use()
import type { DBCore, DBCoreMutateRequest } from 'dexie';
import { PlanotoFileDexie } from '$lib/database/db';

type MyExtendedDBCoreMutateRequest = DBCoreMutateRequest & {
  myUndoTransactionsToApply?: ((db: PlanotoFileDexie) => void)[]
  myRedoTransactionsToApply?: ((db: PlanotoFileDexie) => void)[]
};

export function undoMiddleware() {
  let undoArray : MyExtendedDBCoreMutateRequest[] = [];
  let redoArray : MyExtendedDBCoreMutateRequest[] = [];
  // Needed so that undoing an operation does not create a new Undo entry.
  // There is certainly a better way but not sure how.
  let normalUndoOrRedo = 0; // 0, 1 or 2 depending on the case
  return {
    undo: async (db : PlanotoFileDexie) => {
      normalUndoOrRedo = 1;
      let middlewareEnabled = false;
      console.log("Length", undoArray.length, redoArray.length);
      const x = undoArray.pop();
      if(x && x.myUndoTransactionsToApply) {
        await Promise.all(x.myUndoTransactionsToApply.map(action => action(db)));
      };      
      normalUndoOrRedo = 0;
    },
    redo: async (db : PlanotoFileDexie) => {
      console.log("Starting redo");
      normalUndoOrRedo = 2;
      const x = redoArray.pop();
      if(x && x.myUndoTransactionsToApply) {
        await Promise.all(x.myUndoTransactionsToApply.map(action => action(db)));
      };
      normalUndoOrRedo = 0;
    },
    create: (downlevelDatabase: DBCore) => {
      console.log("Euh I am a middleware");
      // Return your own implementation of DBCore:
      return {
        // Copy default implementation.
        ...downlevelDatabase, 
        // Override table method
        table (tableName: string) {
          console.log("I am in my custom table method");
          // Call default table method
          const downlevelTable = downlevelDatabase.table(tableName);
          // Derive your own table from it:
          return {
            // Copy default table implementation:
            ...downlevelTable,
            // Override the mutate method:
            mutate: async (req: MyExtendedDBCoreMutateRequest) => {
              // https://github.com/dexie/Dexie.js/blob/master/src/public/types/dbcore.d.ts
              console.log("normalUndoOrRedo", normalUndoOrRedo);
              switch (normalUndoOrRedo) {
                case 0:
                  // Normal mode: we add the operation to the undo list, and we clean the redo mode
                  redoArray = [];
                  if(undoArray[undoArray.length - 1] != req) {
                    console.log("New transaction");
                    undoArray.push(req);
                  };
                  break;
                case 1:
                  // In undo mode: we add the operation to the redo list
                  if(redoArray[redoArray.length - 1] != req) {
                    console.log("New transaction in undo mode");
                    redoArray.push(req);
                    console.log("redoArray", redoArray.length, "undoArray", undoArray.length)
                  };
                  break;
                case 2:
                  // In redo mode: we add the operation to the undo list 
                  if(undoArray[undoArray.length - 1] != req) {
                    console.log("New transaction");
                    undoArray.push(req);
                  };
                  break;
              }
              // if(!req.myRedoTransactionsToApply) {
              //   req.myRedoTransactionsToApply = [];
              // }
              switch (req.type) {
                case "delete":
                  console.log("We will delete items ", req.keys);
                  await Promise.all(req.keys.map(async (id) => {
                    if(!req.myUndoTransactionsToApply) {
                      req.myUndoTransactionsToApply = [];
                    }
                    console.log("start with ", id);
                    console.log("will get element", id);
                    const elmt = await downlevelTable.get({trans: req.trans, key: id});
                    console.log("foo", elmt);
                    console.log("We will push in the undo array add ", tableName, elmt);
                    req.myUndoTransactionsToApply.push(async (db) => await db.table(tableName).add(elmt));
                    //req.myRedoTransactionsToApply.push(db => db.table(tableName).delete(id));
                  }));
                  break;
                  // For add we need to wait for the query to finish to get the ID
                case "put":
                  //TODO
                  break;
              };
              console.log("My middleware is called in a mutate query!", req);
              const res = await downlevelTable.mutate(req);
              // We first need to run the mutation to get the id of the new object to remove
              switch (req.type) {
                case "add":
                  console.log("After the mutation the result is ", res);
                  console.log("It created the ids", res.results);
                  if(res.results) {
                    res.results.forEach((id, i) => {
                      if(!req.myUndoTransactionsToApply) {
                        req.myUndoTransactionsToApply = [];
                      }
                      req.myUndoTransactionsToApply.push(async (db) => await db.table(tableName).delete(id));
                      //req.myRedoTransactionsToApply.push(db => db.table(tableName).add(req.values[i]));
                    });
                  }
                  break;
              }
              return res
            }
          }
        }
      }
    }
  }
}

Next step: the put! But this one seems more technical, I can't really understand how to get the key before the change is applied. I'm also wondering if it is not possible to have "race conditions" if during the same transaction a given table is changed by two or more elementary transactions. Is it possible?

[tobiasBora]

Ok, I also did it for put (so now only deleteRange is left) and fixed a few bugs with transactions, but not sure how robust is my solution (I basically look for the values, get the ID of all objects, copy the whole object, and insert it later when doing the undo).

So now I have 2 questions left:

• how can I cancel the addition of the undo if the transaction fails?
• how robust is my approach? (I ignore for instance most fields but value and I don't know if this can be an issue, I assume that all objects have a downlevelTable.schema.primaryKey.keyPath available)

I still need to polish this a bit (e.g. maximum undo size) and add deleteRange, but for now I'm surprised by how well it works on my tiny examples.

// Create an undo mechanism based on recommendations I got from https://github.com/dexie/Dexie.js/issues/1933
// This is a middleware as defined in https://dexie.org/docs/Dexie/Dexie.use()
import type { DBCore, DBCoreMutateRequest, DBCoreTransaction } from 'dexie';
import { PlanotoFileDexie } from '$lib/database/db';

// Used to specify the list of tables that the actions might touch (needed to create a transaction)
interface ITablesAndActions {
  tables: string[];
  actions: ((db: PlanotoFileDexie) => void)[]
}

type MyExtendedDBCoreTransaction = DBCoreTransaction & {
  myUndoTransactionsToApply?: ITablesAndActions
};

export function undoMiddleware() {
  let undoArray : MyExtendedDBCoreTransaction[] = [];
  let redoArray : MyExtendedDBCoreTransaction[] = [];
  // Needed so that undoing an operation does not create a new Undo entry.
  // There is certainly a better way but not sure how.
  let normalUndoOrRedo = 0; // 0, 1 or 2 depending on the case
  return {
    undo: async (db : PlanotoFileDexie) => {
      let middlewareEnabled = false;
      console.log("Length", undoArray.length, redoArray.length);
      const x = undoArray.pop();
      if(x && x.myUndoTransactionsToApply) {
        await db.transaction("rw", x.myUndoTransactionsToApply.tables.flat(), async () => {
          normalUndoOrRedo = 1;
          if(x && x.myUndoTransactionsToApply) {
            await Promise.all(x.myUndoTransactionsToApply.actions.map(action => action(db)));
          }
          normalUndoOrRedo = 0;
        });
      }
    },
    redo: async (db : PlanotoFileDexie) => {
      console.log("Starting redo");
      const x = redoArray.pop();
      if(x && x.myUndoTransactionsToApply) {
        await db.transaction("rw", x.myUndoTransactionsToApply.tables.flat(), async () => {
          normalUndoOrRedo = 2;
          if(x && x.myUndoTransactionsToApply) {
            await Promise.all(x.myUndoTransactionsToApply.actions.map(action => action(db)));
          }
          normalUndoOrRedo = 0;
        });
      };
    },
    create: (downlevelDatabase: DBCore) => {
      console.log("Euh I am a middleware");
      // Return your own implementation of DBCore:
      return {
        // Copy default implementation.
        ...downlevelDatabase, 
        // Override table method
        table (tableName: string) {
          console.log("I am in my custom table method");
          // Call default table method
          const downlevelTable = downlevelDatabase.table(tableName);
          // Derive your own table from it:
          return {
            // Copy default table implementation:
            ...downlevelTable,
            // Override the mutate method:
            mutate: async (req: DBCoreMutateRequest & { trans: MyExtendedDBCoreTransaction }) => {
              // https://github.com/dexie/Dexie.js/blob/master/src/public/types/dbcore.d.ts
              console.log("normalUndoOrRedo", normalUndoOrRedo);
              console.log("req", req);
              switch (normalUndoOrRedo) {
                case 0:
                  // Normal mode: we add the operation to the undo list, and we clean the redo mode
                  redoArray = [];
                  if(undoArray[undoArray.length - 1] != req.trans) {
                    console.log("New transaction");
                    undoArray.push(req.trans);
                  };
                  break;
                case 1:
                  // In undo mode: we add the operation to the redo list
                  if(redoArray[redoArray.length - 1] != req.trans) {
                    console.log("New transaction in undo mode");
                    redoArray.push(req.trans);
                    console.log("redoArray", redoArray.length, "undoArray", undoArray.length)
                  };
                  break;
                case 2:
                  // In redo mode: we add the operation to the undo list 
                  if(undoArray[undoArray.length - 1] != req.trans) {
                    console.log("New transaction");
                    undoArray.push(req.trans);
                  };
                  break;
              }
              // if(!req.myRedoTransactionsToApply) {
              //   req.myRedoTransactionsToApply = [];
              // }
              switch (req.type) {
                case "delete":
                  console.log("We will delete items ", req.keys);
                  await Promise.all(req.keys.map(async (id) => {
                    if(!req.trans.myUndoTransactionsToApply) {
                      req.trans.myUndoTransactionsToApply = {tables: [tableName], actions: []};
                    }
                    console.log("start with ", id);
                    console.log("will get element", id);
                    const elmt = await downlevelTable.get({trans: req.trans, key: id});
                    console.log("foo", elmt);
                    console.log("We will push in the undo array add ", tableName, elmt);
                    req.trans.myUndoTransactionsToApply.actions.push(async (db) => await db.table(tableName).add(elmt));
                    //req.myRedoTransactionsToApply.push(db => db.table(tableName).delete(id));
                  }));
                  break;
                  // For add we need to wait for the query to finish to get the ID
                case "put":
                  //TODO
                  console.log("I am in put", downlevelTable.schema.primaryKey.keyPath);
                  const ids = req.values.map(obj => PlanotoFileDexie.getByKeyPath(obj, downlevelTable.schema.primaryKey.keyPath));
                  console.log("Ids to copy", ids);
                  await Promise.all(ids.map(async (id) => {
                    console.log("doing it for", id);
                    const elmt = await downlevelTable.get({trans: req.trans, key: id});
                    console.log("The elemt is", elmt);
                    if(!req.trans.myUndoTransactionsToApply) {
                      req.trans.myUndoTransactionsToApply = {tables: [tableName], actions: []};
                    }
                    req.trans.myUndoTransactionsToApply.actions.push(async (db) => db.table(tableName).put(elmt));
                    console.log("Element added");
                  }));
                  console.log("Done");
                  break;
              };
              console.log("My middleware is called in a mutate query!", req);
              const res = await downlevelTable.mutate(req);
              // We first need to run the mutation to get the id of the new object to remove
              console.log("After the mutation the result is ", res);
              switch (req.type) {
                case "add":
                  console.log("It created the ids", res.results);
                  if(res.results) {
                    res.results.forEach((id, i) => {
                      if(!req.trans.myUndoTransactionsToApply) {
                        req.trans.myUndoTransactionsToApply = {tables: [tableName], actions: []};
                      }
                      req.trans.myUndoTransactionsToApply.actions.push(async (db) => await db.table(tableName).delete(id));
                      //req.myRedoTransactionsToApply.push(db => db.table(tableName).add(req.values[i]));
                    });
                  }
                  break;
              }
              return res
            }
          }
        }
      }
    }
  }
}

[dfahlander]

Let normalUndoOrRedo be bound to the transaction. To do this you could:

// create a weakmap to associate state with the transaction:
const wmNormalUndoOrRedo = new WeakMap<object, number>();

...
// in the undo / redo
        await db.transaction("rw", x.myUndoTransactionsToApply.tables.flat(), async (tx) => {
          wmNormalUndoOrRedo.set(tx.idbtrans, 1); // or 2 for redo
          if(x && x.myUndoTransactionsToApply) {
            await Promise.all(x.myUndoTransactionsToApply.actions.map(action => action(db)));
          }
        });
...

// in the middleware
switch (wmNormalUndoOrRedo.get(trans)) {
  ...
}

Transactions can span over multiple operations. You need both to detect failing operations and aborted transactions. Instead of pushing the trans on every mutate, I think you should override the transaction function of your middleware and push all 'readwrite' transactions to the undoBuffer instead of doing it on every mutate call (which could lead to the same transaction being pushed several times).

To detect whether a transaction aborts, listen to the "abort" and "error" events of the IDBTransaction. This event can be listened to in the transaction() function of your middleware. Call downlevelDatabase.transaction() and check for addEventListener on it (as it will be certanty be an IDBTransaction returned). Then listen for "abort" and "error".

When abort or error happens on any 'readwrite' transaction, try finding it in the undoBuffer and remove your aborted transaction from your undoBuffer.

[dfahlander]

To detect failing operations, just catch the call to downlevelTable.mutate() and remove anything you've pushed to your undo buffer from it. Remember to re-throw the error also.

The reason for both checking aborted/errored transactions and failed operations is that operations can succeed but a later operation fail and then abort earlier operations, while a failing operation itself doesn't nescessarily abort the transaction in case the user catches it and continues doing other operations within the same transaction.

[tobiasBora]

Thanks a lot for your precious advices. But I tried to apply both advices:

1. Let normalUndoOrRedo be bound to the transaction.
2. I think you should override the transaction function of your middleware and push all 'readwrite' transactions to the undoBuffer instead of doing it on every mutate call

Unfortunately while 1 works well within the above code, if I tried to apply both 1 & 2 I have an issue: it seems that when the transaction defined in my middleware is called, the wmNormalUndoOrRedo map is not yet initialized as my understanding (based on experiments) is that the code async (tx) => { … } is called AFTER transaction. Not sure if you see how to run it before…

EDIT

I'm thinking… instead of pushing the code in transaction, I could simply push it in undo… but the issue is that I'm not so sure how to deal with normal transactions then…

EDIT2
I finally added in the middleware transaction a message to the transaction to know if the first mutate should reset or not the list of redo. This seems to work for now.

[tobiasBora]

Ok, so continuing my tests… now I'm trying to make it deal with aborted queries. But I'm quite disturbed by this: if I do in transactions

const tx : MyExtendedDBCoreTransaction = downlevelDatabase.transaction(stores, mode, options);
if(mode == 'readwrite') {
  tx.addEventListener('abort', () => {console.log("an abort");});
  tx.addEventListener('error', () => {console.log("an error");});
  tx.addEventListener('complete', () => {console.log("complete");});
}

and if I create a query like:

db.decks.toCollection().modify(deck => {throw new Error('Foo')})

then in the console I can see complete, meaning that the error was not detected… Any idea why?