A few tests were failing which exposed the fact that if skip is `B` (the
out factor of the OpTree) then we set `skip = None` and this causes us
to attempt to return `Skip` in a non root node. I ported the failing
test from JS to Rust and fixed the problem.
I also fixed the formatting issues.
Context: currently we store a mapping from ChangeHash -> Clock, where
`Clock` is the set of (ActorId, (Sequence number, max Op)) pairs derived
from the given change and it's dependencies. This clock is used to
determine what operations are visible at a given set of heads.
Problem: populating this mapping for documents with large histories
containing many actors can be very slow as for each change we have to
allocate and merge a bunch of hashmaps.
Solution: instead of creating the clocks on load, create an adjacency
list based representation of the change graph and then derive the clock
from this graph when it is needed. Traversing even large graphs is still
almost as fast as looking up the clock in a hashmap.
Problem: when running the sync protocol for a new document the API
requires that the user create an empty document and then call
`receive_sync_message` on that document. This results in the OpObserver
for the new document being called with every single op in the document
history. For documents with a large history this can be extremely time
consuming, but the OpObserver doesn't need to know about all the hidden
states.
Solution: Modify `Automerge::load_with` and
`Automerge::apply_changes_with` to check if the document is empty before
applying changes. If the document _is_ empty then we don't call the
observer for every change, but instead use
`automerge::observe_current_state` to notify the observer of the new
state once all the changes have been applied.
Problem: When loading a document whilst passing an `OpObserver` we call
the OpObserver for every change in the loaded document. This slows down
the loading process for two reasons: 1) we have to make a call to the
observer for every op 2) we cannot just stream the ops into the OpSet in
topological order but must instead buffer them to pass to the observer.
Solution: Construct the OpSet first, then only traverse the visible ops
in the OpSet, calling the observer. For documents with a deep history
this results in vastly fewer calls to the observer and also allows us to
construct the OpSet much more quickly. It is slightly different
semantically because the observer never gets notified of changes which
are not visible, but that shouldn't matter to most observers.
The fields of `automerge::Automerge` were crate public, which made it
hard to change the structure of `Automerge` with confidence. Make all
fields private and put them behind accessors where necessary to allow
for easy internal changes.
Before this change i64 decoding did not work for negative numbers (not a
real problem because it is only used for the timestamp of a change),
and both u64 and i64 would allow overlong LEB encodings.
The Rust API has so far grown somewhat organically driven by the needs of the
javascript implementation. This has led to an API which is quite awkward and
unfamiliar to Rust programmers. Additionally there is no documentation to speak
of. This commit is the first movement towards cleaning things up a bit. We touch
a lot of files but the changes are all very mechanical. We introduce a few
traits to abstract over the common operations between `Automerge` and
`AutoCommit`, and add a whole bunch of documentation.
* Add a `ReadDoc` trait to describe methods which read value from a document.
make `Transactable` extend `ReadDoc`
* Add a `SyncDoc` trait to describe methods necessary for synchronizing
documents.
* Put the `SyncDoc` implementation for `AutoCommit` behind `AutoCommit::sync` to
ensure that any open transactions are closed before taking part in the sync
protocol
* Split `OpObserver` into two traits: `OpObserver` + `BranchableObserver`.
`BranchableObserver` captures the methods which are only needed for observing
transactions.
* Add a whole bunch of documentation.
The main changes Rust users will need to make is:
* Import the `ReadDoc` trait wherever you are using the methods which have been
moved to it. Optionally change concrete paramters on functions to `ReadDoc`
constraints.
* Likewise import the `SyncDoc` trait wherever you are doing synchronisation
work
* If you are using the `AutoCommit::*_sync_message` methods you will need to add
a call to `AutoCommit::sync()` first. E.g. `doc.generate_sync_message` becomes
`doc.sync().generate_sync_message`
* If you have an implementation of `OpObserver` which you are using in an
`AutoCommit` then split it into an implementation of `OpObserver` and
`BranchableObserver`
Problem: In `automerge::query::Index::change_vis` we use `-=` to
subtract the width of an operation which is being hidden from the text
widths which we store on the index of each node in the optree. This
index represents the width of all the visible text operations in this
node and below. This was causing an integer underflow error when
encountering some list operations. More specifically, when a
`ScalarValue::Str` in a list was made invisible by a later operation
which contained a _shorter_ string, the width subtracted from the indexed
text widths could be longer than the current index.
Solution: use `saturating_sub` instead. This is technically papering
over the problem because really the width should never go below zero,
but the text widths are only relevant for text objects where the
existing logic works as advertised because we don't have a `set`
operation for text indices. A more robust solution would be to track the
type of the Index (and consequently of the `OpTree`) at the type level,
but time is limited and problems are infinite.
Also, add a lengthy description of the reason we are using
`saturating_sub` so that when I read it in about a month I don't have
to redo the painful debugging process that got me to this commit.
Before this change numbits_i64() was incorrect for every value of the
form 0 - 2^x. This only manifested in a visible error if x%7 == 6 (so
for -64, -8192, etc.) at which point `lebsize` would return a value one
too large, causing a panic in commit().
Problem: the `OpSet::export_key` method uses `query::ElemIdPos` to
determine the index of sequence elements when exporting a key. This
query returned `None` for invisible elements. The `Parents` iterator
which is used to generate paths to objects in patches in
`automerge-wasm` used `export_key`. The end result is that applying a
remote change which deletes an object in a sequence would panic as it
tries to generate a path for an invisible object.
Solution: modify `query::ElemIdPos` to include invisible objects. This
does mean that the path generated will refer to the previous visible
object in the sequence as it's index, but this is probably fine as for
an invisible object the path shouldn't be used anyway.
While we're here also change the return value of `OpSet::export_key` to
an `Option` and make `query::Index::ops` private as obeisance to the
Lady of the Golden Blade.
The `ExId` structure has some internal details which make lookups for
object IDs which were produced by the document doing the looking up
faster. These internal details are quite specific to the implementation
so we don't want to expose them as a public API. On the other hand, we
need to be able to serialize `ExId`s so that FFI clients can hold on to
them without referencing memory which is owned by the document (ahem,
looking at you Java).
Introduce `ExId::to_bytes` and `TryFrom<&[u8]> ExId` implementing a
canonical serialization which includes a version tag, giveing us
compatibility options if we decide to change the implementation.
In #480 we fixed an issue where `SeekOp` calculated an incorrect
insertion index on optrees where the only visible ops were on internal
nodes. We forgot to port this fix to `SeekOpWithPatch`, which has almost
the same logic just with additional work done in order to notify an
`OpObserver` of changes. Add a test and fix to `SeekOpWithPatch`
The wasm codebase assumed that clients want to represent text as a
string of characters. This is faster, but in order to enable backwards
compatibility we add a `TextRepresentation` argument to
`automerge_wasm::Automerge::new` to allow clients to choose between a
`string` or `Array<any>` representation. The `automerge_wasm::Observer`
will consult this setting to determine what kind of diffs to generate.
The `SeekOp` query can produce incorrect results when the optree it is
searching only has visible ops on the internal nodes. Add some tests to
demonstrate the issue as well as a fix.
This is primarily useful when debugging documents which have been
corrupted somehow so you would like to see the ops even if you can't
trust them. Note that this is _not_ currently useful for performance
reasons as the hash graph is still constructed, just not verified.
* Don't panic on invalid gzip stream
Before this change automerge-rs would panic if the gzip data in
a raw column was invalid; after this change the error is propagated
to the caller correctly.
The error messages produced by various conversions in `automerge-wasm`
were quite uninformative - often consisting of just returning the
offending value with no description of the problem. The logic of these
error messages was often hard to trace due to the use of `JsValue` to
represent both error conditions and valid values - evidenced by most of
the public functions of `automerge-wasm` having return types of
`Result<JsValue, JsValue>`. Change these return types to mention
specific errors, thus enlisting the compilers help in ensuring that
specific error messages are emitted.
Transactions with no ops in them are generally undesirable. They take up
space in the change log but do nothing else. They are not useless
though, it may occasionally be necessary to create an empty change in
order to list all the current heads of the document as dependents of the
empty change.
The current API makes no distinction between empty changes and non-empty
changes. If the user calls `Transaction::commit` a change is created
regardless of whether there are ops to commit. To provide a more useful
API modify `commit` so that if there is a no-op transaction then no
changes are created, but provide explicit methods to create an empty
change via `Transaction::empty_change`, `Automerge::empty_change` and
`Autocommit::empty_change`. Also make these APIs available in Javascript
and C.
It's tricky to modify these structs with the fields public as every
change requires scanning the codebase for references to make sure you're
not breaking any invariants. Make the fields private to ease
development.
Sometimes it is necessary to query the heads of a document at the time a
transaction started without having a mutable reference to the
transactable. Add `Transactable::base_heads` to do this.
The API of Automerge::generate_sync_message requires that the user keep
track of in flight messages themselves if they want to avoid sending
duplicate messages. To avoid this add a flag to `automerge::sync::State`
to track if there are any in flight messages and return `None` from
`generate_sync_message` if there are.
Generating patches to text objects (a la the edit-trace benchmark) was
very slow due to appending to the back of a Vec. Use the SequenceTree
(effectively a B-tree) instead so as to speed up sequence patch
generation.
After some discussion with PVH I realise that the repo structure in the
last reorg was very rust-centric. In an attempt to put each language on
a level footing move the rust code and project files into ./rust
