This is a port of a fix previously merged into `main`.
The javascript implementation of automerge sorts actor IDs
lexicographically when encoding changes. We were sorting actor IDs in
the order the appear in the change we're encoding. This meant that the
index that we assigned to operations in the encoded change was different
to that which the javascript implementation assigns, resulting in
mismatched head errors as the hashes we created did not match the
javascript implementation.
This change fixes the issue by sorting actor IDs lexicographically. We
make a pass over the operations in the change before encoding to collect
the actor IDs and sort them. This means we no longer need to pass a
mutable `Vec<ActorId>` to the various encode functions, which cleans
things up a little.
Rather than returning an OpID for every mutation, we now return an
`Option<ObjId>`. This is `Some` only when a `make*` operation was
applied. This `ObjID` is an opaque type which can be used with any
document.
This commit adds a bunch of testing infrastructure as well as most of
the tests from the `legacy_tests.js` file in the js codebase that seem
applicable to this codebase.
The OpTree is a reasonably complicated data structure. This change adds
a method on the OpTree which is then exposed through
`Automerge::visualise` which prints the structure of the OpTree in
graphviz format. Each node in the tree is printed as a simple table of
operations with outgoing edges to tables representing the children of
the node. This is behind a compile time flag (optree-visualisation)
because it's probably not useful except when debugging.
Repeatedly setting the same value for a particular (obj, key)
combination now no longer generates an operation. To allow this we
modify the return value of `automerge::set` so that it may return an
`Option<OpId>` instead of an `OpId`.
Signed-off-by: Alex Good <alex@memoryandthought.me>
Rather than iterating through the children we can just skip straight to
the last. The last element is always in a leaf so we also don't need to
care about intermediate values.
