UI 算法：一个极简的 Undo 栈

· 2025年3月22日

我之前几次都需要用到它。这次我想找到一个足够小巧、灵活但又完整的解决方案。同时，我也想知道如何用非常简单的方式实现它。我觉得效果很好，所以我们深入研究一下。

Undo 历史和管理器

大多数 UI 都会有一些形式的 undo 功能。一般来说，有两种形式：undo 栈 和 版本历史。“版本历史”就像 Photoshop 历史记录提供的那样，可以“穿透”到系统的先前状态。您可以添加五个绘画笔触，然后显示您在 4 步前绘制的笔触。

但大多数应用程序不需要这个。您需要的是一个 undo 栈，可以按如下方式进行规范：

• 执行一个可 undo 的操作，并将其压入栈中。
• 如果请求 undo，则弹出栈，并对弹出的操作应用回滚操作。
• 如果 undo 了一个操作，则可以 redo 该操作。如果您已经 undo 了 2 个操作，则可以 redo 2 个操作。
• 如果您在存在可以 redo 的操作时，将一个可 undo 的操作压入栈中，则这些可 redo 的操作将被丢弃——记住，没有分支！

如果您想了解“大公司”过去是如何做的，请查看 NSUndoManager 文档

所以，像我通常喜欢做的那样，我想了解最佳的 API 应该是什么样的。对于这个用例——绘图——我有以下工作流程：

• 当您绘制一个笔触时，输入点被添加到 currentStroke。
• 当您释放笔时，currentStroke 被附加到 strokes 并重置以供下一个笔触使用。

我想要这样的东西：

let addStroke = () => strokes.push(currentPaintStroke);
let removeStroke = () => strokes.pop();
undoThing.push(addStroke, removeStroke);
// then, on user action
undoThing.undo(); // calls removeStroke()
undoThing.redo(); // calls strokes.push(...) again

栈指针的危险

这应该是世界上最简单的事情。现在，如果您查看大多数推荐的（以及一些现有的！）undo 栈实现，您会发现它们通常使用带有指针的栈。比如这里和这里——你将拥有一个栈，通常表示为 JS 数组，以及某种 pointer 或 index，您将使用它来索引到该栈中。

虽然它是可行的 且 标准的，但它与我不太协调。你看，使用数组的索引通常使 JS 代码容易受到两件事的影响，这两件事每次都会让我栽跟头：

• 索引到不存在的索引——你好，undefined 检查。
• 调用 Array.slice 和 Array.splice 时出现偏移量错误。哦，当然还有混淆 slice 和 splice。

Ruby 和 JS 对 slice 具有不同的语义——一个使用索引边界，另一个使用两个偏移量——这无济于事。如果 API 使用向量的偏移量会发生什么？确切地说：混淆这些偏移量是包含性的还是排他性的。哦，而且在您改变数组后，偏移量会发生变化，这使得它更加痛苦。

我们可以不使用索引吗？

所以我想到了：我们实际上有两个栈，而不是一个。我们有一个 undoStack（可以回滚的事情）和一个 redoStack（可以向前滚的事情）。我们对 undo-redo 操作所做的所有事情实际上并没有改变 指针——它们只是将东西从一个栈 移动 到另一个栈。并且这些栈之间的规则有所不同！当我们添加一个新的可 undo 的操作时，我们会擦除可 redo 的操作，还记得吗？因此，虽然可 undo 的栈很少被“置空”，但可 redo 的栈很可能会经常被置空。

一旦这一点变得清晰，实现几乎就自己写出来了：

function createUndoStack() {
 let past = [];
 let future = [];
 return {
  push(doFn, undoFn) {
   doFn();
   past.push({doFn, undoFn});
   // Adding a new action wipes the redoable steps
   future.length = 0;
  },
  undo() {
   let action = past.pop();
   if (action) {
    action.undoFn();
    future.unshift(action);
   }
  },
  redo() {
   let action = future.unshift();
   if (action) {
    action.doFn();
    past.push(action);
   }
  }
 };
}

因此，我们可以拥抱动态大小的数组，而不用试图通过只有一个数组来节省资源（并且可悲地失败并出现差一错误的索引错误），并完全忘记索引。太棒了！

让我们添加几个方法来显示我们的 UI：

 get canUndo() {
  return past.length > 0;
 },
 get canRedo() {
  return future.length > 0;
 }

按引用传递问题

但是我们的实现有一个问题。对于几乎所有类型，JS 都是按引用传递的。这意味着，当我们创建一个关于值的闭包——在这种情况下是 currentStroke——闭包将继续寻址 现在 存储在 currentStroke 中的任何内容。并且这些 doFn 和 undoFn 在一个特定的行为特征中非常特殊：它们必须是幂等的。无论您调用它们多少次，它们都应该导致相同的结果。

如果我们只是这样做：

let doFn = () => strokes.push(currentStroke)

每次我们调用 doFn 时——无论调用范围中的 currentStroke 是什么，最终都会被压入 strokes 栈中。这不是我们想要的——我们希望 doFn 使用 currentStroke 的克隆副本，并且我们希望它始终这样做。undoFnx 也是如此——尽管在这种情况下，它不需要知道 strokes 中存储的内容，也不需要知道 currentStroke 过去是什么，因为我们不会恢复绘制该 currentStroke。现代 JS 有一种叫做 structuredClone() 的东西，非常适合这种情况：

 push(doFn, undoFn, ...withArgumentsToClone) {
  const clonedArgs = structuredClone(withArgumentsToClone);
  const action = {
   doWithData() {
    doFn(...clonedArgs);
   },
   undoWithData() {
    undoFn(...clonedArgs);
   },
  };
  action.doWithData();
 
  // Adding a new action wipes the redoable steps
  past.push(action);
  future.length = 0;
 }

我们将相应地修改我们的函数。与其闭包化 currentStroke，不如将其作为一个参数：

let appendStroke = strokes.push.bind(strokes);
undoStack.push(appendStroke, () => strokes.pop(), currentStroke);

我们的 undoStack 的 push() 负责为我们做一个深度克隆。太好了！

完整的定义变为：

function createUndoStack() {
 const past = [];
 const future = [];
 return {
  push(doFn, undoFn, ...withArgumentsToClone) {
   const clonedArgs = structuredClone(withArgumentsToClone);
   const action = {
    doWithData() {
     doFn(...clonedArgs);
    },
    undoWithData() {
     undoFn(...clonedArgs);
    },
   };
   action.doWithData();
   // Adding a new action wipes the redoable steps
   past.push(action);
   future.length = 0;
  },
  undo() {
   let action = past.pop();
   if (action) {
    action.undoWithData();
    future.unshift(action);
   }
  },
  redo() {
   let action = future.shift();
   if (action) {
    action.doWithData();
    past.push(action);
   }
  },
  get undoAvailable() {
   return past.length > 0;
  },
  get redoAvailable() {
   return future.length > 0;
  },
  clear() {
   past.length = 0;
   future.length = 0;
   return true;
  }
 }
}
export {createUndoStack};

健壮、小巧且没有索引错误。这就是我的风格。 © Julik Tarkhanov 2025