README
¶
cooperate 
Package cooperate is a library for implementing Operational Transformation.
This package was primarily written to teach myself about the mathematical underpinnings of Operational Transformation. No guarantees are made about the correctness, efficiency, or reliability of this implementation. :)
Status
Really, only the most basic fundamentals exist right now: the Compose and Transform are implemented for text-based data.
I haven't gotten to work on any of the client-server interaction yet.
References
- Google's What's different about the new Google Docs blog post series.
- Daniel Spiewak's thorough treatise Understanding and Applying Operational Transformation
- The wonderful OT Explained summary and visualizer.
Documentation
¶
Overview ¶
Package cooperate is an Operational Transformation library for real-time collaborative applications.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrDocumentSizeMismatch indicates that the operation does not account for // the entire length of the existing document. ErrDocumentSizeMismatch = errors.New("document size mismatch") // ErrDeleteMismatch indicates that an action requested to delete data that // was not present in the existing document. ErrDeleteMismatch = errors.New("delete mismatch") // ErrUnknownAction indicates that an unrecognized action was provided. ErrUnknownAction = errors.New("unknown action") )
Functions ¶
This section is empty.
Types ¶
type Action ¶
type Action interface{}
An Action is something that can be performed as part of an operation.
type Client ¶
type Client struct {
Document Document
InFlight Operation
Buffer Operation
// these implement the core OT operations
ExpandReducer
ComposeTransformer
}
A Client serves as the editing entity in the OT paradigm. It maintains its own independent state and proposes updates to some OT server.
func (*Client) ApplyLocal ¶
ApplyLocal applies an operation that this client produced. If no pending operations exist, this operation is immediately proposed; otherwise it is composed into the buffer and held for future proposal.
func (*Client) ApplyReceived ¶
ApplyReceived transforms an Operation received from the server for local application and adapts InFlight and Buffer accordingly.
type ComposeTransformer ¶
type ComposeTransformer interface {
Composer
Transformer
}
A ComposeTransformer implements the two core OT functions.
type Composer ¶
type Composer interface {
Compose(a, b *OperationIterator) (Operation, error)
}
A Composer provides an application-aware implementation of the OT compose function. Mathematically, it's defined as
Compose(a, b) ≡ a ◦ b
In other words, given two operations a and b, it is expected to produce a single operation c that produces the same effect as applying a then b.
type Document ¶
A Document is data that may be collaboratively edited via a series of distributed Operations.
type ExpandReducer ¶
type ExpandReducer interface {
// Expand inflates a single action to its atomic parts.
Expand(a Action) []Action
// Reduce merges actions a and b, or indicates that they are unmergable. The
// arguments are provided such that the action a happens before action b.
Reduce(a, b Action) (Action, bool)
}
An ExpandReducer converts an Operation to its most and least verbose forms, respectively. It may help simplify implementations of Compose and Transform.
type History ¶
type History interface {
// SequenceNumber returns the sequence number of the current state.
SequenceNumber() int
// Store appends an operation to the history, and returns its seqno.
Store(op Operation) (seqno int, err error)
// Iterate traverses through all operations between startingSeqno and
// SequenceNumber() inclusive.
Iterate(startingSeqno int, cb func(seqno int, op Operation) error) error
}
History implements storage of a sequence of Operations.
type MemoryHistory ¶
type MemoryHistory []Operation
MemoryHistory is the simplest possible History implementation, storing a sequence of Operations in an in-memory slice.
func (*MemoryHistory) SequenceNumber ¶
func (mh *MemoryHistory) SequenceNumber() int
type Operation ¶
type Operation []Action
An Operation is a list of component actions that together define one complete iteration through a document.
func Expand ¶
func Expand(er ExpandReducer, op Operation) Operation
Expand inflates op such that each action affects only one element. For example, a RetainAction(6) becomes six consecutive RetainAction(1).
func Reduce ¶
func Reduce(er ExpandReducer, op Operation) Operation
Reduce collapses op into the minumum possible number of actions that have an identical effect.
type OperationIterator ¶
An OperationIterator provides an interface to the actions within an Operation that helps simplify Composer and Transformer implementations.
func NewOperationIterator ¶
func NewOperationIterator(op Operation) *OperationIterator
func (*OperationIterator) Consume ¶
func (oit *OperationIterator) Consume() Action
Consume advances the iterator over foremost action and returns it. It panics if no actions remain.
func (*OperationIterator) Len ¶
func (oit *OperationIterator) Len() int
Len reports the number of unconsumed actions remaining.
func (*OperationIterator) More ¶
func (oit *OperationIterator) More() bool
More indicates whether any unconsumed actions remain.
func (*OperationIterator) Peek ¶
func (oit *OperationIterator) Peek() Action
Peek returns the foremost action. It panics if none remain.
func (*OperationIterator) PeekType ¶
func (oit *OperationIterator) PeekType() reflect.Type
PeekType returns the reflect.Type of the foremost action, or nil if none remain.
type Server ¶
type Server struct {
Document Document
History History
// these implement the core OT operations
ExpandReducer
ComposeTransformer
}
type Transformer ¶
type Transformer interface {
Transform(a, b *OperationIterator) (aa, bb Operation, err error)
}
A Transformer provides an application-aware implementation of the OT transform function by producing the operational inverses of a and b. Mathematically:
transform(a, b) = (a', b') where a ◦ b' ≡ b ◦ a'
Implementations of Transformer are expected to behave such that the above equality holds.
Source Files
Directories