dot: github.com/dotchain/dot/changes Index | Files | Directories

package changes

import "github.com/dotchain/dot/changes"

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

Package Files

atomic.go changes.go empty.go meta.go move.go path.go replace.go splice.go

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.

type Atomic Uses

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.

func (Atomic) Apply Uses

func (a Atomic) Apply(ctx Context, c Change) Value

Apply only accepts one type of change: one that Replace's the value.

type Change Uses

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)

func Merge Uses

func Merge(c1, c2 Change) (c1x, c2x Change)

Merge is effectively c1.Merge(c2) except that c1 can be nil.

As with individual merge implementations, applying c1+c1x is effectively the same as applying c2+c2x.

func Simplify Uses

func Simplify(c Change) Change

Simplify converts a change to a simpler form if possible

type ChangeSet Uses

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 Uses

func (c ChangeSet) ApplyTo(ctx Context, v Value) Value

ApplyTo simply walks through the individual changes and applies them to the value.

func (ChangeSet) Merge Uses

func (c ChangeSet) Merge(other Change) (otherx, cx Change)

Merge implements Change.Merge.

func (ChangeSet) ReverseMerge Uses

func (c ChangeSet) ReverseMerge(other Change) (otherx, cx Change)

ReverseMerge is like merge except with receiver and args inverted

func (ChangeSet) Revert Uses

func (c ChangeSet) Revert() Change

Revert implements Change.Revert.

func (ChangeSet) Simplify Uses

func (c ChangeSet) Simplify() Change

Simplify converts an empty or single element change-set into a simpler version

type Collection Uses

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 Uses

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"

func MetaValue Uses

func MetaValue(ctx Context) (v interface{}, p Context)

MetaValue fetches the meta value and the previous context associated with the current change context.

type Custom Uses

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 Uses

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) ApplyTo Uses

func (m Meta) ApplyTo(ctx Context, v Value) Value

ApplyTo implements Custom.ApplyTo

func (Meta) Merge Uses

func (m Meta) Merge(other Change) (otherx, cx Change)

Merge merges the change preserving the meta data

func (Meta) ReverseMerge Uses

func (m Meta) ReverseMerge(c Change) (Change, Change)

ReverseMerge implements Custom.ReverseMerge

func (Meta) Revert Uses

func (m Meta) Revert() Change

Revert reverts the change preserving the meta data

type Move Uses

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) Change Uses

func (m *Move) Change() Change

Change returns either nil or the underlying Move as a change.

func (Move) MapIndex Uses

func (m Move) MapIndex(idx int) int

MapIndex maps a particular index to the new location of the index after the move

func (Move) Merge Uses

func (m Move) Merge(other Change) (otherx, cx Change)

Merge implements the Change.Merge method

func (Move) MergeMove Uses

func (m Move) MergeMove(o Move) (ox []Move, mx []Move)

MergeMove merges a move against another Move

func (Move) MergeReplace Uses

func (m Move) MergeReplace(other Replace) (other1 *Replace, m1 *Splice)

MergeReplace merges a move against a Replace. The replace always wins

func (Move) MergeSplice Uses

func (m Move) MergeSplice(o Splice) (Change, Change)

MergeSplice merges a splice with a move.

func (Move) Normalize Uses

func (m Move) Normalize() Move

Normalize ensures that distance is always positive

func (Move) Revert Uses

func (m Move) Revert() Change

Revert reverts the move.

type PathChange Uses

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 Uses

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 Uses

func (pc PathChange) Merge(o Change) (Change, Change)

Merge implements Change.Merge

func (PathChange) ReverseMerge Uses

func (pc PathChange) ReverseMerge(o Change) (Change, Change)

ReverseMerge implements but with receiver and arg interchanged.

func (PathChange) Revert Uses

func (pc PathChange) Revert() Change

Revert implements Change.Revert

func (PathChange) Simplify Uses

func (pc PathChange) Simplify() Change

Simplify returns a simpler version of this change removing empty paths or coalescing paths as needed

type Replace Uses

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) Change Uses

func (s *Replace) Change() Change

Change returns either nil or a Change

func (Replace) IsCreate Uses

func (s Replace) IsCreate() bool

IsCreate identifies if the change is a create

func (Replace) IsDelete Uses

func (s Replace) IsDelete() bool

IsDelete identifies if the change is a delete

func (Replace) Merge Uses

func (s Replace) Merge(other Change) (otherx, cx Change)

Merge implements the Change.Merge method

func (Replace) MergeMove Uses

func (s Replace) MergeMove(other Move) (other1 *Move, s1 *Replace)

MergeMove merges against a Move change. The replace wins

func (Replace) MergeReplace Uses

func (s Replace) MergeReplace(other Replace) (other1, s1 *Replace)

MergeReplace merges against another Replace change. The last writer wins here with the receiver assumed to be the earlier change

func (Replace) MergeSplice Uses

func (s Replace) MergeSplice(other Splice) (other1 *Splice, s1 *Replace)

MergeSplice merges against a Splice change. The replace wins

func (Replace) Revert Uses

func (s Replace) Revert() Change

Revert inverts the effect of the replace

type Splice Uses

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) Change Uses

func (s *Splice) Change() Change

Change returns nil or the underlying Splice

func (Splice) MapIndex Uses

func (s Splice) MapIndex(idx int) (int, bool)

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) Merge Uses

func (s Splice) Merge(other Change) (otherx, cx Change)

Merge implements the Change.Merge method

func (Splice) MergeMove Uses

func (s Splice) MergeMove(o Move) (ox, sx Change)

MergeMove merges a splice against a move

func (Splice) MergeReplace Uses

func (s Splice) MergeReplace(other Replace) (other1 *Replace, s1 *Splice)

MergeReplace merges a move against a Replace. The replace always wins

func (Splice) MergeSplice Uses

func (s Splice) MergeSplice(other Splice) (other1, s1 *Splice)

MergeSplice merges a splice against another Splice.

func (Splice) Revert Uses

func (s Splice) Revert() Change

Revert inverts the effect of the splice.

type Value Uses

type Value interface {
    // Apply applies the specified change on the object and
    // returns the updated value.
    Apply(ctx Context, c Change) Value
}

Value represents an immutable JSON object that can apply changes. Array like values should also implement Collection

Directories

PathSynopsis
crdtPackage crdt implements CRDT types and associated changes
diffPackage diff compares two values and returns the changes
runPackage run implements a custom change that applies to a sequence of array elements.
tablePackage table implements a loose 2d collection of values
typesPackage types implements OT-compatible immutable values.

Package changes is imported by 25 packages. Updated 2019-06-24. Refresh now. Tools for package owners.