-
Notifications
You must be signed in to change notification settings - Fork 0
/
cooperate.go
158 lines (135 loc) · 5.07 KB
/
cooperate.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
// Package cooperate is an Operational Transformation library for real-time collaborative applications.
package cooperate
import (
"errors"
"reflect"
)
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")
)
type (
// A Document is data that may be collaboratively edited via
// a series of distributed Operations.
Document interface {
Apply(Operation) error
}
// An Operation is a list of component actions that together define one
// complete iteration through a document.
Operation []Action
// // TODO(tylerchr): I think eventually we should use an "Operation" that looks more like this:
// Operation struct {
// ClientID int // the client who proposed this operation
// OperationID int // the client-assigned OperationID
// AppliedTime time.Time // the timestamp the client first applied this operation
// CommitTime time.Time // the timestamp the server committed this operation
// Root int // the Sequence Number of the server state at which this op was rooted
// Actions []Action // the enumeration of actions that form the operation
// }
// An Action is something that can be performed as part of an operation.
Action interface{}
// 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.
Composer interface {
Compose(a, b *OperationIterator) (Operation, 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.
Transformer interface {
Transform(a, b *OperationIterator) (aa, bb Operation, err error)
}
// A ComposeTransformer implements the two core OT functions.
ComposeTransformer interface {
Composer
Transformer
}
// An ExpandReducer converts an Operation to its most and least verbose forms,
// respectively. It may help simplify implementations of Compose and Transform.
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 OperationIterator provides an interface to the actions within an Operation
// that helps simplify Composer and Transformer implementations.
type OperationIterator struct {
Cursor int
Actions []Action
}
func NewOperationIterator(op Operation) *OperationIterator {
return &OperationIterator{Actions: []Action(op)}
}
// More indicates whether any unconsumed actions remain.
func (oit *OperationIterator) More() bool {
return oit.Len() > 0
}
// Len reports the number of unconsumed actions remaining.
func (oit *OperationIterator) Len() int {
return len(oit.Actions) - oit.Cursor
}
// Peek returns the foremost action. It panics if none remain.
func (oit *OperationIterator) Peek() Action {
if oit.Cursor >= len(oit.Actions) {
panic(errors.New("no actions remain in iterator"))
}
return oit.Actions[oit.Cursor]
}
// PeekType returns the reflect.Type of the foremost action, or nil if none remain.
func (oit *OperationIterator) PeekType() reflect.Type {
if oit.More() {
return reflect.TypeOf(oit.Peek())
}
return nil
}
// Consume advances the iterator over foremost action and returns it. It panics if
// no actions remain.
func (oit *OperationIterator) Consume() Action {
if oit.Cursor >= len(oit.Actions) {
panic(errors.New("no actions remain in iterator"))
}
oit.Cursor++
return oit.Actions[oit.Cursor-1]
}
// Expand inflates op such that each action affects only one element. For
// example, a RetainAction(6) becomes six consecutive RetainAction(1).
func Expand(er ExpandReducer, op Operation) Operation {
var actions []Action
for _, a := range []Action(op) {
actions = append(actions, er.Expand(a)...)
}
return Operation(actions)
}
// Reduce collapses op into the minumum possible number of actions that have
// an identical effect.
func Reduce(er ExpandReducer, op Operation) Operation {
var actions []Action
for _, a := range []Action(op) {
if len(actions) == 0 {
actions = append(actions, a)
} else if reduced, ok := er.Reduce(actions[len(actions)-1], a); ok {
actions[len(actions)-1] = reduced
} else {
actions = append(actions, a)
}
}
return Operation(actions)
}