kernel.core.conflict-cache
Conflict Cache, CC for short. Caches all conflicts a site detected.
The conflict cache is only a performance optimization and not essential. It is useful because conflict detection is pure (always yields the same results) and expensive.
Conflicts are cached by mapping from pairs of conflicting operations to a Conflict record, which currently stores the human-readable reason for the conflict.
Note that only conflicts are stored. If two operations are compatible, nothing is stored (this is the expected case). Therefore, the most recently arrived operation is saved (if any). This is used to identify whether the cache may be used (hittable?).
As the conflict detection also considers conflict-succeeding operations a conflict, those operations will also be stored in the conflict cache.
Without garbage collection, the conflict cache may grow quadratically with time.
_remove
(_remove CC CO-ID)Removes all conflicts which involve a given operation in O(n). Called by the garbage collector, which is in turn only called between operation generation/reception, i.e., the most recent compound operation is always nil and does not have to be checked.
get-all-conflicts
(get-all-conflicts CC)Returns all conflicts stored in the conflict cache, which are all conflicts known to the system.
get-conflict
(get-conflict CC CO-ID-a CO-ID-b)Hits the cache for two given operations in O(1). Returns the Conflict record of the operations conflict. Otherwise, returns nil. Requires previous check whether the cache is hittable?.
get-conflicts
(get-conflicts CC CO-ID)Returns all operations conflicting with a given operation as a mapping from operation IDs to Conflict records.
hittable?
(hittable? CC CO-ID-a CO-ID-b)Returns whether the conflict cache may be used for two particular operations in O(1). The conflict cache can only be hit for two operations that have not just arrived, as only then the cache has previously been written.
insert
(insert CC CO-ID-a CO-ID-b conflict)Inserts a new conflict for two operations into the conflict cache in O(1).
make-conflict
(make-conflict & reason)Creates a new Conflict record that includes a reason for a conflict.
with-most-recent
(with-most-recent CC CO-ID)Sets the conflict cache’s most recently arrived operation.