Throw errors when applying deltas that depend on missing state

[jimpick]

Introduces a new "delta depends on missing vertex" error.

Previously, applying deltas would succeed, but result in inconsistent results when state was applied afterwards.

For the 'push' and 'insertAt' mutations, this removes the redundant initial added vertex (but leaves the edge) ... and uses that as a signal to check to ensure that the vertex exists when applying the delta.

TODO: Other mutations: addRight, remove, removeAt

[pgte]

@jimpick Looking good, good catches! Do you want to add tests for the other methods?

[jimpick]

There's no need to throw exceptions for remove and removeAt, as those mutations can be safely applied in any order and won't get the rga crdt into an inconsistent state.

[jimpick]

I'll try testing this with PeerPad / peer-base to see if it causes any problems.

If PeerPad is behaving, it shouldn't throw any of the new exceptions.

[jimpick]

The peer-base unit tests pass.

When I try running PeerPad (local build), I have an instance of Firefox that is refusing to sync with a document started in Chrome. The console is showing 'delta depends on missing vertex' errors...

So it appears that PeerPad is trying to apply deltas even though it hasn't applied the base state yet (which would explain some of the consistency problems we were seeing).

[jimpick]

For the PeerPad issue ... I cleared the storage in Firefox and reloaded, and now it loads and doesn't throw the error. So the situation where the exception is thrown only happens some of the time.

[pgte]

Do you have a stack trace?

[CBaquero]

Hi. Ideally, all deltas mutations should be able to merge together with no issues and also merge with any full state. This is useful to allow them to be merged together and sent in a single delta block, for instance.

However a state might only make sense (to be consulted) if all the deltas applied there are causally consistent. I.e. there are no deltas applied that depend on a missing delta. One way to achieve this is to carefully track which deltas were successfully shipped and incorporated, before merging in new deltas into a given destination.

Not sure if this is related to the issue here, but just wanted to point it out.

[pgte]

@CBaquero that's a great insight, thank you!

The RGA is an adaptation of an op-based version that requires causal delivery, so it it's state has no place for "pending" operations, it simply consists of:

* vertices added
* vertices removed
* edges (map of vertex => next vertex)

As an example, this mutation:

delta = rga.push('something')

Would result in

a) creating a new vertex id (nvid) b) calculating the id of the previous vertex (pvid) b) producing the following delta:

• vertices added: { <nvid>: "something" }
• vertices removed: empty
• edges: `{ : , : END }`

As you can see, there would be a problem if you would deliver these without causal consistency, as the pvid could not exist in a replica yet..

As a suggested change, we can add a fourth element to the state that contains the pending edges...

[jimpick]

With this patch, I was able to track down the bug in peer-base which was causing the problem:

https://github.com/peer-base/peer-base/pull/210

With that fix to peer-base, PeerPad syncs again, and there shouldn't be corruption. So it should be ok to apply this patch.

[pgte]

@jimpick thank you! I'm going to merge this patch as it proves to be useful, and then we can continue this conversation in another issue.

[pgte]

Fix landed on v0.8.1.