Documentation
¶
Overview ¶
Package changes implements the core mutation types for OT.
The three basic types are Replace, Splice and Move. Replace replaces a value altogether while Splice replaces a sub-sequence in an array-like object and Move shuffles a sub-sequence.
Both Slice and Move work on strings as well. The actual type for Slice and Move is represented by the Collection interface (while Replace uses a much more lax Value interface)
See https://godoc.org/github.com/dotchain/dot/changes/types#S16 for an implementation of an OT-compatible string type.
Composition ¶
ChangeSet allows a set of mutations to be grouped together.
PathChange allows a mutation to refer to a "path". For example, a field in a "struct type" can be thought of as having the path of "field name". An element of a collection can be thought of as having the path of the index in that array.
The type of the elements in the path is not specified but it is assumed that they are comparable for equality. Collections are required to use the index of type int for the path elements.
Custom Changes ¶
Custom change types can be defined. They should implement the Custom interface. See https://godoc.org/github.com/dotchain/dot/changes/x/rt#Run for an example custom change type.
The general asssumption underlying OT is that the Merge method produces convergence:
if: c1, c2 = changes on top of "initial" and: c1x, c2x := c1.Merge(c2) then: initial + c1 + c1x == initial + c2 + c2x
Notes ¶
Replace and Splice change both expect the Before and After fields to be non-nil Value implementations. Replace can use changes.Nil to represent empty values for the case where a value is being deleted or created. Slices must make sure that the Before and After use the "empty" representations of the respective types.
Slices also should generally make sure that the Before and After types are compatible -- i.e. each should be able to be spliced within the other.
Value Interface ¶
Any custom Value implementation should implement the Value interface. See https://godoc.org/github.com/dotchain/dot/changes/types for a set of custom value types such as string, arrays and counters.
See https://godoc.org/github.com/dotchain/dot/x/rt for a custom type that has a specific custom change associated with it.
It is common to have a value type (say *Node) that is meant as an atomic value. In that case, one can use the Atomic{} type to hold such values.
Index ¶
- Variables
- type Atomic
- type Change
- type ChangeSet
- type Collection
- type Context
- type Custom
- type Meta
- type Move
- func (m *Move) Change() Change
- func (m Move) MapIndex(idx int) int
- func (m Move) Merge(other Change) (otherx, cx Change)
- func (m Move) MergeMove(o Move) (ox []Move, mx []Move)
- func (m Move) MergeReplace(other Replace) (other1 *Replace, m1 *Splice)
- func (m Move) MergeSplice(o Splice) (Change, Change)
- func (m Move) Normalize() Move
- func (m Move) Revert() Change
- type PathChange
- type Replace
- func (s *Replace) Change() Change
- func (s Replace) IsCreate() bool
- func (s Replace) IsDelete() bool
- func (s Replace) Merge(other Change) (otherx, cx Change)
- func (s Replace) MergeMove(other Move) (other1 *Move, s1 *Replace)
- func (s Replace) MergeReplace(other Replace) (other1, s1 *Replace)
- func (s Replace) MergeSplice(other Splice) (other1 *Splice, s1 *Replace)
- func (s Replace) Revert() Change
- type Splice
- func (s *Splice) Change() Change
- func (s Splice) MapIndex(idx int) (int, bool)
- func (s Splice) Merge(other Change) (otherx, cx Change)
- func (s Splice) MergeMove(o Move) (ox, sx Change)
- func (s Splice) MergeReplace(other Replace) (other1 *Replace, s1 *Splice)
- func (s Splice) MergeSplice(other Splice) (other1, s1 *Splice)
- func (s Splice) Revert() Change
- type Value
Constants ¶
This section is empty.
Variables ¶
var Nil = empty{}
Nil represents an empty value. It can be used with Replace or Splice to indicate that Before or After is empty. The only operation that can be applied is a Replace. Count and Slice cannot be called on it.
Functions ¶
This section is empty.
Types ¶
type Atomic ¶
type Atomic struct {
Value interface{}
}
Atomic is an atomic Value. It can wrap any particular value and can be used in the Before, After fields of Replace or Splice.
type Change ¶
type Change interface {
// Merge takes the current change and another change that were
// both applied to the same virtual JSON and returns
// transformed versions such that:
//
// c + otherx = other + cx
//
// Otherx captures the intent behind other and cx captures the
// intent behind the current change. The equation above
// guarantees that the combined intent can be achieved by
// applying the transformed changes on top of the local
// change.
//
// Note that there is no requirement that c.Merge(other) and
// other.Merge(c) should both yield the same transforms. This
// requires that for correctness, there must be a clear way to
// decide which change is the receiver and which is the param.
Merge(other Change) (otherx, cx Change)
// Revert returns the opposite effect of the current
// change. If applied directly after the current change it
// should undo the effect of the current change.
Revert() Change
}
Change represents an OT-compatible mutation
The methods provided here are the core methods. Custom changes should implement the Custom interface in addition to this. Note that it is legal for a change to be nil (meaning the value isnt change at all)
type ChangeSet ¶
type ChangeSet []Change
ChangeSet represents a collection of changes. It implements the Change interface thereby allowing merging groups of changes against each other.
func (ChangeSet) ApplyTo ¶
ApplyTo simply walks through the individual changes and applies them to the value.
func (ChangeSet) ReverseMerge ¶
ReverseMerge is like merge except with receiver and args inverted
type Collection ¶
type Collection interface {
// must also implement Value
Value
// ApplyCollection is just strongly typed Apply
ApplyCollection(ctx Context, c Change) Collection
// Slice should only be called on collection-like objects such
// as the Before/After fields of a Splice. Note that unlike
// Go's slice notation, the arguments are offset and count.
Slice(offset, count int) Collection
// Count should noly be called on collection-like objects such
// as the Before/After fields of a Splice. It returns the size
// of the collection.
Count() int
}
Collection represents an immutable array-like value
type Context ¶
type Context interface {
Value(key interface{}) interface{}
}
Context defines the context in which a change is being applied. This is useful to capture data such as the "current user" or "virtual time" etc. For true convergence, the context itself should be derived from the change -- say via Meta.
Note that this interface is a subset of the standard golang "context.Context"
type Custom ¶
type Custom interface {
Change
// ReverseMerge is used when a "known" change type is merged
// with a custom type:
//
// move.Merge(myType)
//
// The known type has no way of figuring out how to merge. It
// calls ReverseMerge on the custom type to get the custom
// type to deal with this. This is separate from the regular
// Merge method because calling "myType.Merge(move)" may not
// be the same: the Merge() call is not required to be
// symmetric. A good example of a non-symmetric situation is
// when the left change and the right change both are
// "inserting" into the same array at the same point -- the
// changes will have to be ordered so that one of them ends up
// before the other.
//
// Basically, if:
//
// ax, bx := a.Merge(b)
//
// Then:
//
// bx, ax := b.ReverseMerge(a)
//
ReverseMerge(c Change) (Change, Change)
// ApplyTo allows custom change types to implement a method to
// apply their changes onto known "values". This allows Value
// implementations to be written without awareness of all
// possible Change implementations
ApplyTo(ctx Context, v Value) Value
}
Custom is the interface that custom change types should implement. This allows the "known" types to interact with custom types.
Custom changes might also need to implement the refs.PathMerger interface (see https://godoc.org/github.com/dotchain/dot/refs)
type Meta ¶
type Meta struct {
Data interface{}
Change
}
Meta wraps a change with some metadata that is maintained as the change is merged. This is useful for carrying contexts with changes. One example is the current user making the change
func (Meta) ReverseMerge ¶
ReverseMerge implements Custom.ReverseMerge
type Move ¶
type Move struct {
Offset, Count, Distance int
}
Move represents a shuffling of some elements (specified by Offset and Count) over to a different spot (specified by Distance, which can be negative to indicate a move over to the left).
func (Move) MapIndex ¶
MapIndex maps a particular index to the new location of the index after the move
func (Move) MergeReplace ¶
MergeReplace merges a move against a Replace. The replace always wins
func (Move) MergeSplice ¶
MergeSplice merges a splice with a move.
type PathChange ¶
type PathChange struct {
Path []interface{}
Change
}
PathChange represents a change at the provided "path" which can consist of strings (for map-like objects) and integers for array-like objects. In particular, each element of the path should be a proper comparable value (so slices and such cannot be part of th path)
func (PathChange) ApplyTo ¶
func (pc PathChange) ApplyTo(ctx Context, v Value) Value
ApplyTo is not relevant to PathChange. It only works when the path is empty. In all other cases, it panics.
func (PathChange) Merge ¶
func (pc PathChange) Merge(o Change) (Change, Change)
Merge implements Change.Merge
func (PathChange) ReverseMerge ¶
func (pc PathChange) ReverseMerge(o Change) (Change, Change)
ReverseMerge implements but with receiver and arg interchanged.
func (PathChange) Simplify ¶
func (pc PathChange) Simplify() Change
Simplify returns a simpler version of this change removing empty paths or coalescing paths as needed
type Replace ¶
type Replace struct {
Before, After Value
}
Replace represents create, delete and update of a value based on whether Before is Nil, After is Nil and both are non-Nil respectively.
func (Replace) MergeReplace ¶
MergeReplace merges against another Replace change. The last writer wins here with the receiver assumed to be the earlier change
func (Replace) MergeSplice ¶
MergeSplice merges against a Splice change. The replace wins
type Splice ¶
type Splice struct {
Offset int
Before, After Collection
}
Splice represents an array edit change. A set of elements from the specified offset are removed and replaced with a new set of elements.
func (Splice) MapIndex ¶
MapIndex maps an index to the new location of the index after the splice. It also returns whether the item at that index has been modified by the splice change.
func (Splice) MergeReplace ¶
MergeReplace merges a move against a Replace. The replace always wins
func (Splice) MergeSplice ¶
MergeSplice merges a splice against another Splice.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
Package crdt implements CRDT types and associated changes The main CRDT types are Dict and Seq which implement map-like and list-like container types.
|
Package crdt implements CRDT types and associated changes The main CRDT types are Dict and Seq which implement map-like and list-like container types. |
|
Package diff compares two values and returns the changes
|
Package diff compares two values and returns the changes |
|
Package run implements a custom change that applies to a sequence of array elements.
|
Package run implements a custom change that applies to a sequence of array elements. |
|
Package table implements a loose 2d collection of values
|
Package table implements a loose 2d collection of values |
|
Package types implements OT-compatible immutable values.
|
Package types implements OT-compatible immutable values. |