In the front-end rich interactive editing, the stable undo/redo function is a big guarantee of user security. What are the pain points in designing and implementing such features, and how can they be addressed? StateShot encapsulates some of our thoughts on this setting.

background

If a product manager decides to ask for an undo feature on your form, how do you get it out of the way? The simplest and most straightforward implementation would be a class like this:

class History {
  push () {}
  redo () {}
  undo () {}
}
Copy the code

Insert a full deep copy of the page state each time you push, and then remove the corresponding state from undo/redo. Is it easy? To store all the states in a linear array, it is sufficient to maintain an array index to the current state, like this:

However, in a real-world scenario, these are all potential challenges:

  • Incremental storage – Constant data in multiple records, no need to duplicate it, right?
  • Record on demand – edits are centralized on the same page, no need to record the status of other pages, right?
  • Asynchronous logging – Never mind how trivial user events are, just push them, okay?
  • Customizability – need to be used elsewhere, coupling to a specific data structure is not a good idea?
  • Access speed – try not to jam, right?

Of these concerns, storage space and access speed are the most closely related to the actual experience. There is a silver bullet that provides the theoretically elegant implementation of both: Immutable data structures. Based on such a data structure, each state change creates a reference to the new state in constant time, and these references inherently share unchanged content: this is called structural sharing.

However, Immutable is highly intrusive to the architecture. You can only achieve the desired undo/redo capability if the entire project adopts the apis it encapsulates to update status from the bottom up. Many direct assignment operations such as state.x = y, which are common in Vue and even native JS scenarios, need to be rewritten to fit — paying off the technical debt can be as costly as starting from scratch.

So, do we have a Plan B?

design

In technical interviews, “deep-copy data” can be a cliche. This question has a way of writing that many people scoff at:

copy = JSON.parse(JSON.stringify(data))
Copy the code

It seems like a bit more of a gimme than the deep copy of the “elegant recursion” implementations of various nuggets articles. However, this implementation has a special property: it is easy to calculate the hash value of a serialized string. Since the same state has the same hash, it is easy to use a Map to “de-duplicate” each serialized state as long as the hash value is used as the key, thus implementing the “multiple identical states occupy only one piece of storage” feature. By refining the granularity of this operation to each node in the state tree, we get a coherently structured tree where each node stores the hash of the original node:

Thus, node-level structure sharing can be achieved by converting the structure of the State tree into a Record tree that stores hash indexes and serializing each node into Chunk data blocks.

use

From this simple concept we came up with StateShot wheels. It’s very simple to use:

import { History } from 'stateshot'

const state = { a: 1.b: 2 }

const history = new History()
history.pushSync(state) // The more common push API is asynchronous

state.a = 2 // mutation!
history.pushSync(state) // Record the status again

history.get() // { a: 2, b: 2 }
history.undo().get() // { a: 1, b: 2 }
history.redo().get() // { a: 2, b: 2 }
Copy the code

StateShot will automatically handle data – hash – data conversion for you. But this example doesn’t seem like anything special, right? Indeed, for ease of use, we designed it to be usable without any customization, but you can also Opt In for more fine-grained optimization on demand. This brings us to the rule-driven concept. By specifying rules, you can tell StateShot how to traverse your state tree. The structure of a rule looks like this:

const rules = [{
  match: Function.toRecord: Function.fromRecord: Function
}]

const history = new History({ rules })
Copy the code

In the rules, we can specify finer grained chunking optimization. For example, for the following scenario:

We move the image node slightly, leaving its SRC field unchanged. In the case of Bliss, the Windows XP desktop prototype, the node has reached a size of 30M after Base64, which would be a huge burden to store its new state in full every time it moved. In this case, you can configure the StateShot rules to split the single node into multiple chunks to store the SRC field separately from the rest of the node for finer structure sharing within the single node:

This corresponds to a rule like this:

const rule = {
  match: node= > node.type === 'image'.toRecord: node= > ({
    // Split the SRC and other fields of the node into two chunks
    chunks: [{ ...node, src: null }, node.src],
  })
  fromRecord: ({ chunks }) = > ({
    // Restore the original state from the chunk array. chunks[0].src: chunks[1]})}Copy the code

Another common scenario is when the state tree is “multi-page” : if the user edits on only one page, it is not economical to hash all the page states. As an optimization, StateShot supports specifying a pickIndex to determine which child of the root node to hash, so that the state of the other page (the direct child of the root node) is a shallow copy of the previous record. In this case, although the full state is also stored, the cost of recording the historical state is significantly reduced:

The corresponding API is also simple:

history.push(state, 0) // Specify that only the first child of state is hashed
Copy the code

Almost forgot, the API also supports chained calls and promises, which were probably standard for “elegant” in 8012:

// Get undo and redo are O(1)
const state = history.undo().undo().redo().undo().get()

// The asynchronous throttling delay can be controlled by the delay parameter
hisoty.push().then(/ *... * /)
Copy the code

conclusion

We are already using StateShot in the Authoring Technology developed editor. At Benchmark, it’s about three times faster than the old history module (thanks to the new MurmurHash hash algorithm instead of sha-1). Moreover, the memory footprint of snapshots is reduced by more than 90% in scenarios where small changes such as multiple drag-and-drops are made to a single element in a row after fine-grained rules are customized based on it. Overall, it provides:

  • Non-invasive API out of the box
  • Support for chained calls and promises
  • Rule-driven customization and optimization strategies
  • < 2KB min + gzipped volume
  • 100% test coverage

StateShot has been opened to the public under the official GitHub organization of Draft Technologies, welcome students who have history state management needs to try XD

Xuebi at gaoding.com (xuebi at Gaoding.com