Add UndoStack class - a custom undo/redo engine

It will be hooked up to the markdown editor later

2 files changed, 417 insertions, 0 deletions

diff --git a/spec/frontend/lib/utils/common_utils_spec.js b/spec/frontend/lib/utils/common_utils_spec.js
new file mode 100644
index 00000000000..e3d3b82d2f3
--- /dev/null
+++ b/spec/frontend/lib/utils/common_utils_spec.js
@@ -0,0 +1,180 @@
+import * as cu from '~/lib/utils/common_utils';
+
+const CMD_ENTITY = '⌘';
+
+// Redefine `navigator.platform` because it's unsettable by default in JSDOM.
+let platform;
+Object.defineProperty(navigator, 'platform', {
+  configurable: true,
+  get: () => platform,
+  set: val => {
+    platform = val;
+  },
+});
+
+describe('common_utils', () => {
+  describe('platform leader key helpers', () => {
+    const CTRL_EVENT = { ctrlKey: true };
+    const META_EVENT = { metaKey: true };
+    const BOTH_EVENT = { ctrlKey: true, metaKey: true };
+
+    it('should return "ctrl" if navigator.platform is unset', () => {
+      expect(cu.getPlatformLeaderKey()).toBe('ctrl');
+      expect(cu.getPlatformLeaderKeyHTML()).toBe('Ctrl');
+      expect(cu.isPlatformLeaderKey(CTRL_EVENT)).toBe(true);
+      expect(cu.isPlatformLeaderKey(META_EVENT)).toBe(false);
+      expect(cu.isPlatformLeaderKey(BOTH_EVENT)).toBe(true);
+    });
+
+    it('should return "meta" on MacOS', () => {
+      navigator.platform = 'MacIntel';
+      expect(cu.getPlatformLeaderKey()).toBe('meta');
+      expect(cu.getPlatformLeaderKeyHTML()).toBe(CMD_ENTITY);
+      expect(cu.isPlatformLeaderKey(CTRL_EVENT)).toBe(false);
+      expect(cu.isPlatformLeaderKey(META_EVENT)).toBe(true);
+      expect(cu.isPlatformLeaderKey(BOTH_EVENT)).toBe(true);
+    });
+
+    it('should return "ctrl" on Linux', () => {
+      navigator.platform = 'Linux is great';
+      expect(cu.getPlatformLeaderKey()).toBe('ctrl');
+      expect(cu.getPlatformLeaderKeyHTML()).toBe('Ctrl');
+      expect(cu.isPlatformLeaderKey(CTRL_EVENT)).toBe(true);
+      expect(cu.isPlatformLeaderKey(META_EVENT)).toBe(false);
+      expect(cu.isPlatformLeaderKey(BOTH_EVENT)).toBe(true);
+    });
+
+    it('should return "ctrl" on Windows', () => {
+      navigator.platform = 'Win32';
+      expect(cu.getPlatformLeaderKey()).toBe('ctrl');
+      expect(cu.getPlatformLeaderKeyHTML()).toBe('Ctrl');
+      expect(cu.isPlatformLeaderKey(CTRL_EVENT)).toBe(true);
+      expect(cu.isPlatformLeaderKey(META_EVENT)).toBe(false);
+      expect(cu.isPlatformLeaderKey(BOTH_EVENT)).toBe(true);
+    });
+  });
+
+  describe('keystroke', () => {
+    const CODE_BACKSPACE = 8;
+    const CODE_TAB = 9;
+    const CODE_ENTER = 13;
+    const CODE_SPACE = 32;
+    const CODE_4 = 52;
+    const CODE_F = 70;
+    const CODE_Z = 90;
+
+    // Helper function that quickly creates KeyboardEvents
+    const k = (code, modifiers = '') => ({
+      keyCode: code,
+      which: code,
+      altKey: modifiers.includes('a'),
+      ctrlKey: modifiers.includes('c'),
+      metaKey: modifiers.includes('m'),
+      shiftKey: modifiers.includes('s'),
+    });
+
+    const EV_F = k(CODE_F);
+    const EV_ALT_F = k(CODE_F, 'a');
+    const EV_CONTROL_F = k(CODE_F, 'c');
+    const EV_META_F = k(CODE_F, 'm');
+    const EV_SHIFT_F = k(CODE_F, 's');
+    const EV_CONTROL_SHIFT_F = k(CODE_F, 'cs');
+    const EV_ALL_F = k(CODE_F, 'scma');
+    const EV_ENTER = k(CODE_ENTER);
+    const EV_TAB = k(CODE_TAB);
+    const EV_SPACE = k(CODE_SPACE);
+    const EV_BACKSPACE = k(CODE_BACKSPACE);
+    const EV_4 = k(CODE_4);
+    const EV_$ = k(CODE_4, 's');
+
+    const { keystroke } = cu;
+
+    it('short-circuits with bad arguments', () => {
+      expect(keystroke()).toBe(false);
+      expect(keystroke({})).toBe(false);
+    });
+
+    it('handles keystrokes using key codes', () => {
+      // Test a letter key with modifiers
+      expect(keystroke(EV_F, CODE_F)).toBe(true);
+      expect(keystroke(EV_F, CODE_F, '')).toBe(true);
+      expect(keystroke(EV_ALT_F, CODE_F, 'a')).toBe(true);
+      expect(keystroke(EV_CONTROL_F, CODE_F, 'c')).toBe(true);
+      expect(keystroke(EV_META_F, CODE_F, 'm')).toBe(true);
+      expect(keystroke(EV_SHIFT_F, CODE_F, 's')).toBe(true);
+      expect(keystroke(EV_CONTROL_SHIFT_F, CODE_F, 'cs')).toBe(true);
+      expect(keystroke(EV_ALL_F, CODE_F, 'acms')).toBe(true);
+
+      // Test non-letter keys
+      expect(keystroke(EV_TAB, CODE_TAB)).toBe(true);
+      expect(keystroke(EV_ENTER, CODE_ENTER)).toBe(true);
+      expect(keystroke(EV_SPACE, CODE_SPACE)).toBe(true);
+      expect(keystroke(EV_BACKSPACE, CODE_BACKSPACE)).toBe(true);
+
+      // Test a number/symbol key
+      expect(keystroke(EV_4, CODE_4)).toBe(true);
+      expect(keystroke(EV_$, CODE_4, 's')).toBe(true);
+
+      // Test wrong input
+      expect(keystroke(EV_F, CODE_Z)).toBe(false);
+      expect(keystroke(EV_SHIFT_F, CODE_F)).toBe(false);
+      expect(keystroke(EV_SHIFT_F, CODE_F, 'c')).toBe(false);
+    });
+
+    it('is case-insensitive', () => {
+      expect(keystroke(EV_ALL_F, CODE_F, 'ACMS')).toBe(true);
+    });
+
+    it('handles bogus inputs', () => {
+      expect(keystroke(EV_F, 'not a keystroke')).toBe(false);
+      expect(keystroke(EV_F, null)).toBe(false);
+    });
+
+    it('handles exact modifier keys, in any order', () => {
+      // Test permutations of modifiers
+      expect(keystroke(EV_ALL_F, CODE_F, 'acms')).toBe(true);
+      expect(keystroke(EV_ALL_F, CODE_F, 'smca')).toBe(true);
+      expect(keystroke(EV_ALL_F, CODE_F, 'csma')).toBe(true);
+      expect(keystroke(EV_CONTROL_SHIFT_F, CODE_F, 'cs')).toBe(true);
+      expect(keystroke(EV_CONTROL_SHIFT_F, CODE_F, 'sc')).toBe(true);
+
+      // Test wrong modifiers
+      expect(keystroke(EV_ALL_F, CODE_F, 'smca')).toBe(true);
+      expect(keystroke(EV_ALL_F, CODE_F)).toBe(false);
+      expect(keystroke(EV_ALL_F, CODE_F, '')).toBe(false);
+      expect(keystroke(EV_ALL_F, CODE_F, 'c')).toBe(false);
+      expect(keystroke(EV_ALL_F, CODE_F, 'ca')).toBe(false);
+      expect(keystroke(EV_ALL_F, CODE_F, 'ms')).toBe(false);
+      expect(keystroke(EV_CONTROL_SHIFT_F, CODE_F, 'cs')).toBe(true);
+      expect(keystroke(EV_CONTROL_SHIFT_F, CODE_F, 'c')).toBe(false);
+      expect(keystroke(EV_CONTROL_SHIFT_F, CODE_F, 's')).toBe(false);
+      expect(keystroke(EV_CONTROL_SHIFT_F, CODE_F, 'csa')).toBe(false);
+      expect(keystroke(EV_CONTROL_SHIFT_F, CODE_F, 'm')).toBe(false);
+      expect(keystroke(EV_SHIFT_F, CODE_F, 's')).toBe(true);
+      expect(keystroke(EV_SHIFT_F, CODE_F, 'c')).toBe(false);
+      expect(keystroke(EV_SHIFT_F, CODE_F, 'csm')).toBe(false);
+    });
+
+    it('handles the platform-dependent leader key', () => {
+      navigator.platform = 'Win32';
+      let EV_UNDO = k(CODE_Z, 'c');
+      let EV_REDO = k(CODE_Z, 'cs');
+      expect(keystroke(EV_UNDO, CODE_Z, 'l')).toBe(true);
+      expect(keystroke(EV_UNDO, CODE_Z, 'c')).toBe(true);
+      expect(keystroke(EV_UNDO, CODE_Z, 'm')).toBe(false);
+      expect(keystroke(EV_REDO, CODE_Z, 'sl')).toBe(true);
+      expect(keystroke(EV_REDO, CODE_Z, 'sc')).toBe(true);
+      expect(keystroke(EV_REDO, CODE_Z, 'sm')).toBe(false);
+
+      navigator.platform = 'MacIntel';
+      EV_UNDO = k(CODE_Z, 'm');
+      EV_REDO = k(CODE_Z, 'ms');
+      expect(keystroke(EV_UNDO, CODE_Z, 'l')).toBe(true);
+      expect(keystroke(EV_UNDO, CODE_Z, 'c')).toBe(false);
+      expect(keystroke(EV_UNDO, CODE_Z, 'm')).toBe(true);
+      expect(keystroke(EV_REDO, CODE_Z, 'sl')).toBe(true);
+      expect(keystroke(EV_REDO, CODE_Z, 'sc')).toBe(false);
+      expect(keystroke(EV_REDO, CODE_Z, 'sm')).toBe(true);
+    });
+  });
+});
diff --git a/spec/frontend/lib/utils/undo_stack_spec.js b/spec/frontend/lib/utils/undo_stack_spec.js
new file mode 100644
index 00000000000..31ad0e77d6f
--- /dev/null
+++ b/spec/frontend/lib/utils/undo_stack_spec.js
@@ -0,0 +1,237 @@
+import UndoStack from '~/lib/utils/undo_stack';
+
+import { isEqual } from 'underscore';
+
+describe('UndoStack', () => {
+  let stack;
+
+  beforeEach(() => {
+    stack = new UndoStack();
+  });
+
+  afterEach(() => {
+    // Make sure there's not pending saves
+    const history = Array.from(stack.history);
+    jest.runAllTimers();
+    expect(stack.history).toEqual(history);
+  });
+
+  it('is blank on construction', () => {
+    expect(stack.isEmpty()).toBe(true);
+    expect(stack.history).toEqual([]);
+    expect(stack.cursor).toBe(-1);
+    expect(stack.canUndo()).toBe(false);
+    expect(stack.canRedo()).toBe(false);
+  });
+
+  it('handles simple undo/redo behaviour', () => {
+    stack.save(10);
+    stack.save(11);
+    stack.save(12);
+
+    expect(stack.history).toEqual([10, 11, 12]);
+    expect(stack.cursor).toBe(2);
+    expect(stack.current()).toBe(12);
+    expect(stack.isEmpty()).toBe(false);
+    expect(stack.canUndo()).toBe(true);
+    expect(stack.canRedo()).toBe(false);
+
+    stack.undo();
+    expect(stack.history).toEqual([10, 11, 12]);
+    expect(stack.current()).toBe(11);
+    expect(stack.canUndo()).toBe(true);
+    expect(stack.canRedo()).toBe(true);
+
+    stack.undo();
+    expect(stack.current()).toBe(10);
+    expect(stack.canUndo()).toBe(false);
+    expect(stack.canRedo()).toBe(true);
+
+    stack.redo();
+    expect(stack.current()).toBe(11);
+
+    stack.redo();
+    expect(stack.current()).toBe(12);
+    expect(stack.isEmpty()).toBe(false);
+    expect(stack.canUndo()).toBe(true);
+    expect(stack.canRedo()).toBe(false);
+
+    // Saving should clear the redo stack
+    stack.undo();
+    stack.save(13);
+    expect(stack.history).toEqual([10, 11, 13]);
+    expect(stack.current()).toBe(13);
+  });
+
+  it('clear() should clear the undo history', () => {
+    stack.save(0);
+    stack.save(1);
+    stack.save(2);
+    stack.clear();
+    expect(stack.history).toEqual([]);
+    expect(stack.current()).toBeUndefined();
+  });
+
+  it('undo and redo are no-ops if unavailable', () => {
+    stack.save(10);
+    expect(stack.canRedo()).toBe(false);
+    expect(stack.canUndo()).toBe(false);
+
+    stack.save(11);
+    expect(stack.canRedo()).toBe(false);
+    expect(stack.canUndo()).toBe(true);
+
+    expect(stack.redo()).toBeUndefined();
+    expect(stack.history).toEqual([10, 11]);
+    expect(stack.current()).toBe(11);
+    expect(stack.canRedo()).toBe(false);
+    expect(stack.canUndo()).toBe(true);
+
+    expect(stack.undo()).toBe(10);
+    expect(stack.undo()).toBeUndefined();
+    expect(stack.history).toEqual([10, 11]);
+    expect(stack.current()).toBe(10);
+    expect(stack.canRedo()).toBe(true);
+    expect(stack.canUndo()).toBe(false);
+  });
+
+  it('should not save a duplicate state', () => {
+    stack.save(10);
+    stack.save(11);
+    stack.save(11);
+    stack.save(10);
+    stack.save(10);
+
+    expect(stack.history).toEqual([10, 11, 10]);
+  });
+
+  it('uses the === operator to detect duplicates', () => {
+    stack.save(10);
+    stack.save(10);
+    expect(stack.history).toEqual([10]);
+
+    // eslint-disable-next-line eqeqeq
+    expect(2 == '2' && '2' == 2).toBe(true);
+    stack.clear();
+    stack.save(2);
+    stack.save(2);
+    stack.save('2');
+    stack.save('2');
+    stack.save(2);
+    expect(stack.history).toEqual([2, '2', 2]);
+
+    const obj = {};
+    stack.clear();
+    stack.save(obj);
+    stack.save(obj);
+    stack.save({});
+    stack.save({});
+    expect(stack.history).toEqual([{}, {}, {}]);
+  });
+
+  it('should allow custom comparators', () => {
+    stack.comparator = isEqual;
+    const obj = {};
+    stack.clear();
+    stack.save(obj);
+    stack.save(obj);
+    stack.save({});
+    stack.save({});
+    expect(stack.history).toEqual([{}]);
+  });
+
+  it('should enforce a max number of undo states', () => {
+    // Try 2000 saves. Only the last 1000 should be preserved.
+    const sequence = Array(2000)
+      .fill(0)
+      .map((el, i) => i);
+    sequence.forEach(stack.save.bind(stack));
+    expect(stack.history.length).toBe(1000);
+    expect(stack.history).toEqual(sequence.slice(1000));
+    expect(stack.current()).toBe(1999);
+    expect(stack.canUndo()).toBe(true);
+    expect(stack.canRedo()).toBe(false);
+
+    // Saving drops the oldest elements from the stack
+    stack.save('end');
+    expect(stack.history.length).toBe(1000);
+    expect(stack.current()).toBe('end');
+    expect(stack.history).toEqual([...sequence.slice(1001), 'end']);
+
+    // If states were undone but the history is full, can still add.
+    stack.undo();
+    stack.undo();
+    expect(stack.current()).toBe(1998);
+    stack.save(3000);
+    expect(stack.history.length).toBe(999);
+    // should be [1001, 1002, ..., 1998, 3000]
+    expect(stack.history).toEqual([...sequence.slice(1001, 1999), 3000]);
+
+    // Try a different max length
+    stack = new UndoStack(2);
+    stack.save(0);
+    expect(stack.history).toEqual([0]);
+    stack.save(1);
+    expect(stack.history).toEqual([0, 1]);
+    stack.save(2);
+    expect(stack.history).toEqual([1, 2]);
+  });
+
+  describe('scheduled saves', () => {
+    it('should work', () => {
+      // Schedules 1000 ms ahead by default
+      stack.save(0);
+      stack.scheduleSave(1);
+      expect(stack.history).toEqual([0]);
+      jest.advanceTimersByTime(999);
+      expect(stack.history).toEqual([0]);
+      jest.advanceTimersByTime(1);
+      expect(stack.history).toEqual([0, 1]);
+    });
+
+    it('should have an adjustable delay', () => {
+      stack.scheduleSave(2, 100);
+      jest.advanceTimersByTime(100);
+      expect(stack.history).toEqual([2]);
+    });
+
+    it('should cancel previous scheduled saves', () => {
+      stack.scheduleSave(3);
+      jest.advanceTimersByTime(100);
+      stack.scheduleSave(4);
+      jest.runAllTimers();
+      expect(stack.history).toEqual([4]);
+    });
+
+    it('should be canceled by explicit saves', () => {
+      stack.scheduleSave(5);
+      stack.save(6);
+      jest.runAllTimers();
+      expect(stack.history).toEqual([6]);
+    });
+
+    it('should be canceled by undos and redos', () => {
+      stack.save(1);
+      stack.save(2);
+      stack.scheduleSave(3);
+      stack.undo();
+      jest.runAllTimers();
+      expect(stack.history).toEqual([1, 2]);
+      expect(stack.current()).toBe(1);
+
+      stack.scheduleSave(4);
+      stack.redo();
+      jest.runAllTimers();
+      expect(stack.history).toEqual([1, 2]);
+      expect(stack.current()).toBe(2);
+    });
+
+    it('should be persisted immediately with saveNow()', () => {
+      stack.scheduleSave(7);
+      stack.scheduleSave(8);
+      stack.saveNow();
+      jest.runAllTimers();
+      expect(stack.history).toEqual([8]);
+    });
+  });
+});