Serializing HyperFormula as Immutable Cell References

[BrianHung]

I've been exploring the HyperFormula codebase in an effort to implement a formulasUpdated event listener. The motivation for that listener was to sync different instances of HyperFormula for real-time collaboration.

However, after learning that HyperFormula lazily resolves formulas

Instead of transforming all of them at once, HyperFormula remembers the history of the operations and postpones the transformations until the formula needs to be displayed or recalculated.

I've concluded that formulasUpdated isn't a performant way to sync cell values when there are large CRUD operations like addRow.

For example, if we had a 60,000 row spreadsheet with relative cell references, adding a row at the top would result in 60,000 formulas being updated.

The solution that I've seen implemented in HyperFormula internally and elsewhere is to use immutable cell references. HyperFormula does this with incrementing ids in its dependency graph.

However, these IDs are not persisted across instances—HyperFormula's serialization and deserialization process handles formulas with standard cell references, not immutable ones.

Is it possible to introduce an alternative API that supports initialization from, and deserialization to, immutable cell references?

[sequba]

@BrianHung, I like the idea of a collaborative app on top of the HyperFormula engine. HyperFormula, though was not built with this in mind.

The existing serialization/deserialization API does not preserve the entire state of the engine. It keeps only the current contents of the spreadsheet (think: copying and pasting the spreadsheet contents), omitting undo/redo stack, the structure of the dependency graph, and other internal data structures (address mapping, sheet mapping, etc).

The unique ids that you're referring to exist only for the dependency graph nodes (actually, they were introduced only two months ago) and not for other components of the engine internal state.

We would like to support your project, but we are operating on limited resources and cannot afford to rewire the whole HyperFormula to be more collaborative-friendly. I think that, for a start, we could introduce methods to serialize/deserialize the entire HyperFormula state (including undo/redo stack, preserving the unique ids of the dependency graph nodes, etc) and then start thinking about designing a more efficient way of synchronizing the state between multiple HyperFormula instances which is ultimately what would be required for a robust collaborative app.

What do you think about it? Do you have other ideas of what API would be helpful for your project?

[sequba]

@BrianHung, thank you for such an insightful reply. I'll get back to you after discussing these ideas with the team.

[BrianHung]

@sequba This is a working demo branch

https://github.com/BrianHung/hyperformula/commits/REF/
BrianHung/hyperformula@50731c7...2b0fa64

along with a test file of what I was trying to accomplish

https://github.com/BrianHung/hyperformula/blob/REF/test/parser/immutable-ref.spec.ts

The TLDR of the approach is we need to sync immutable references (cell ids, etc) along with formulas themselves.

1. support immutable references directly in the formulas, e.g. =REF('cell', cell_id, isColAbs, isRowAbs). This is because of the CRUD optimizations, and in general, when you move rows or columns, you don't want to emit changes for all formulas for performance reasons.
2. custom range mapping, custom address mapping. This is so immutable references can be created and resolved when cells, rows, cols are used in the dependency graph.

[sequba]

@BrianHung, this looks like a decent feature. I'm trying to analyze it. I'm sorry if I misunderstood some of the concepts. They are not entirely clear to me.

1. Please, confirm, that I understand it correctly: The main idea of these immutable references is to use them to sync the internal state of HyperFormula (dependency graph, address mapping, etc) between multiple instances. An immutable reference is a unique id of a cell. Unlike regular cell reference, an immutable cell reference does not change when a cell is moved (e.g. as a result of adding a row/column before it).
2. Why do you need to support using immutable references (=REF(...)) in the formulas? I thought they are only for the purpose of serialization/deserialization the internal state of HyperFormula.
3. How exactly do you plan to use them to sync the internal state of HyperFormula after each CRUD operation? I assume that's what the getCellSerializedImmutable and getRangeSerializedImmutable is for. But you probably need something like setCellContentImmutable, don't you?

[BrianHung]

1. Yep!
2. The collaborative system should be storing and setting formulas with immutable references. So when a user types, =A1, it should be saved as =REF, and then broadcasted / written to other users' hyperformula instances using setCellContents with =REF. (The REF syntax was based on https://github.com/liveblocks/liveblocks/tree/main/examples/nextjs-spreadsheet-advanced/src/spreadsheet).
   It is possible to build a collaborative system that syncs operations instead of state, and in that case we wouldn't need immutable references in formulas. The specific library I used for multiplayer is https://replicache.dev/, which is state-based.
3. I didn't want to introduce another endpoint like setCellContentImmutable, so setCellContents does that already.

[sequba]

@BrianHung thank you for the explanation. Nice idea and a great example of a non-standard use-case for HyperFormula.

[sequba]

I'll leave it here as it's an interesting point and should be considered when designing a collaborative-friendly API: https://zknill.io/posts/collaboration-no-crdts/