/
serializable.go
377 lines (317 loc) · 13.1 KB
/
serializable.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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
package serializer
import (
"bytes"
"encoding/binary"
"encoding/json"
"fmt"
"sort"
)
// Serializable is something which knows how to serialize/deserialize itself from/into bytes
// while also performing syntactical checks on the written/read data.
type Serializable interface {
json.Marshaler
json.Unmarshaler
// Deserialize deserializes the given data (by copying) into the object and returns the amount of bytes consumed from data.
// If the passed data is not big enough for deserialization, an error must be returned.
// During deserialization additional validation may be performed if the given modes are set.
Deserialize(data []byte, deSeriMode DeSerializationMode, deSeriCtx interface{}) (int, error)
// Serialize returns a serialized byte representation.
// During serialization additional validation may be performed if the given modes are set.
Serialize(deSeriMode DeSerializationMode, deSeriCtx interface{}) ([]byte, error)
}
// SerializableWithSize implements Serializable interface and has the extra functionality of returning the size of the
// resulting serialized object (ideally without actually serializing it).
type SerializableWithSize interface {
Serializable
// Size returns the size of the serialized object
Size() int
}
// Serializables is a slice of Serializable.
type Serializables []Serializable
// SerializableSlice is a slice of a type which can convert itself to Serializables.
type SerializableSlice interface {
// ToSerializables returns the representation of the slice as a Serializables.
ToSerializables() Serializables
// FromSerializables updates the slice itself with the given Serializables.
FromSerializables(seris Serializables)
}
// SerializableReadGuardFunc is a function that given a type prefix, returns an empty instance of the given underlying type.
// If the type doesn't resolve or is not supported in the deserialization context, an error is returned.
type SerializableReadGuardFunc func(ty uint32) (Serializable, error)
// SerializablePostReadGuardFunc is a function which inspects the read Serializable add runs additional validation against it.
type SerializablePostReadGuardFunc func(seri Serializable) error
// SerializableWriteGuardFunc is a function that given a Serializable, tells whether the given type is allowed to be serialized.
type SerializableWriteGuardFunc func(seri Serializable) error
// SerializableGuard defines the guards to de/serialize Serializable.
type SerializableGuard struct {
// The read guard applied before reading an entire object.
ReadGuard SerializableReadGuardFunc
// The read guard applied after an object has been read.
PostReadGuard SerializablePostReadGuardFunc
// The write guard applied when writing objects.
WriteGuard SerializableWriteGuardFunc
}
// DeSerializationMode defines the mode of de/serialization.
type DeSerializationMode byte
const (
// DeSeriModeNoValidation instructs de/serialization to perform no validation.
DeSeriModeNoValidation DeSerializationMode = 0
// DeSeriModePerformValidation instructs de/serialization to perform validation.
DeSeriModePerformValidation DeSerializationMode = 1 << 0
// DeSeriModePerformLexicalOrdering instructs de/deserialization to automatically perform ordering of
// certain arrays by their lexical serialized form.
DeSeriModePerformLexicalOrdering DeSerializationMode = 1 << 1
)
// HasMode checks whether the de/serialization mode includes the given mode.
func (sm DeSerializationMode) HasMode(mode DeSerializationMode) bool {
return sm&mode > 0
}
// ArrayValidationMode defines the mode of array validation.
type ArrayValidationMode byte
const (
// ArrayValidationModeNone instructs the array validation to perform no validation.
ArrayValidationModeNone ArrayValidationMode = 0
// ArrayValidationModeNoDuplicates instructs the array validation to check for duplicates.
ArrayValidationModeNoDuplicates ArrayValidationMode = 1 << 0
// ArrayValidationModeLexicalOrdering instructs the array validation to check for lexical order.
ArrayValidationModeLexicalOrdering ArrayValidationMode = 1 << 1
// ArrayValidationModeAtMostOneOfEachTypeByte instructs the array validation to allow a given type prefix byte to occur only once in the array.
ArrayValidationModeAtMostOneOfEachTypeByte ArrayValidationMode = 1 << 2
// ArrayValidationModeAtMostOneOfEachTypeUint32 instructs the array validation to allow a given type prefix uint32 to occur only once in the array.
ArrayValidationModeAtMostOneOfEachTypeUint32 ArrayValidationMode = 1 << 3
)
// HasMode checks whether the array element validation mode includes the given mode.
func (av ArrayValidationMode) HasMode(mode ArrayValidationMode) bool {
return av&mode > 0
}
// TypePrefixes defines a set of type prefixes.
type TypePrefixes map[uint32]struct{}
// Subset checks whether every type prefix is a member of other.
func (typePrefixes TypePrefixes) Subset(other TypePrefixes) bool {
for typePrefix := range typePrefixes {
if _, has := other[typePrefix]; !has {
return false
}
}
return true
}
// ArrayRules defines rules around a to be deserialized array.
// Min and Max at 0 define an unbounded array.
type ArrayRules struct {
// The min array bound.
Min uint
// The max array bound.
Max uint
// A map of types which must occur within the array.
MustOccur TypePrefixes
// The guards applied while de/serializing Serializables.
Guards SerializableGuard
// The mode of validation.
ValidationMode ArrayValidationMode
// The slice reduction function for uniqueness checks.
UniquenessSliceFunc ElementUniquenessSliceFunc
}
// CheckBounds checks whether the given count violates the array bounds.
func (ar *ArrayRules) CheckBounds(count uint) error {
if ar.Min != 0 && count < ar.Min {
return fmt.Errorf("%w: min is %d but count is %d", ErrArrayValidationMinElementsNotReached, ar.Min, count)
}
if ar.Max != 0 && count > ar.Max {
return fmt.Errorf("%w: max is %d but count is %d", ErrArrayValidationMaxElementsExceeded, ar.Max, count)
}
return nil
}
// ElementUniquenessSliceFunc is a function which takes a byte slice and reduces it to
// the part which is deemed relevant for uniqueness checks.
// If this function is used in conjunction with ArrayValidationModeLexicalOrdering, then the reduction
// must only reduce the slice from index 0 onwards, as otherwise lexical ordering on the set elements
// can not be enforced.
type ElementUniquenessSliceFunc func(next []byte) []byte
// ElementValidationFunc is a function which runs during array validation (e.g. lexical ordering).
type ElementValidationFunc func(index int, next []byte) error
// ElementUniqueValidator returns an ElementValidationFunc which returns an error if the given element is not unique.
func (ar *ArrayRules) ElementUniqueValidator() ElementValidationFunc {
set := map[string]int{}
return func(index int, next []byte) error {
if ar.UniquenessSliceFunc != nil {
next = ar.UniquenessSliceFunc(next)
}
k := string(next)
if j, has := set[k]; has {
return fmt.Errorf("%w: element %d and %d are duplicates", ErrArrayValidationViolatesUniqueness, j, index)
}
set[k] = index
return nil
}
}
// LexicalOrderValidator returns an ElementValidationFunc which returns an error if the given byte slices
// are not ordered lexicographically.
func (ar *ArrayRules) LexicalOrderValidator() ElementValidationFunc {
var prev []byte
var prevIndex int
return func(index int, next []byte) error {
switch {
case prev == nil:
prev = next
prevIndex = index
case bytes.Compare(prev, next) > 0:
return fmt.Errorf("%w: element %d should have been before element %d", ErrArrayValidationOrderViolatesLexicalOrder, index, prevIndex)
default:
prev = next
prevIndex = index
}
return nil
}
}
// LexicalOrderWithoutDupsValidator returns an ElementValidationFunc which returns an error if the given byte slices
// are not ordered lexicographically or any elements are duplicated.
func (ar *ArrayRules) LexicalOrderWithoutDupsValidator() ElementValidationFunc {
var prev []byte
var prevIndex int
return func(index int, next []byte) error {
if prev == nil {
prevIndex = index
if ar.UniquenessSliceFunc != nil {
prev = ar.UniquenessSliceFunc(next)
return nil
}
prev = next
return nil
}
if ar.UniquenessSliceFunc != nil {
next = ar.UniquenessSliceFunc(next)
}
switch bytes.Compare(prev, next) {
case 1:
return fmt.Errorf("%w: element %d should have been before element %d", ErrArrayValidationOrderViolatesLexicalOrder, index, prevIndex)
case 0:
// dup
return fmt.Errorf("%w: element %d and %d are duplicates", ErrArrayValidationViolatesUniqueness, index, prevIndex)
}
prevIndex = index
if ar.UniquenessSliceFunc != nil {
prev = ar.UniquenessSliceFunc(next)
return nil
}
prev = next
return nil
}
}
// AtMostOneOfEachTypeValidator returns an ElementValidationFunc which returns an error if a given type occurs multiple
// times within the array.
func (ar *ArrayRules) AtMostOneOfEachTypeValidator(typeDenotation TypeDenotationType) ElementValidationFunc {
seen := map[uint32]int{}
return func(index int, next []byte) error {
var key uint32
switch typeDenotation {
case TypeDenotationUint32:
if len(next) < UInt32ByteSize {
return fmt.Errorf("%w: not enough bytes to check type uniquness in array", ErrInvalidBytes)
}
key = binary.LittleEndian.Uint32(next)
case TypeDenotationByte:
if len(next) < OneByte {
return fmt.Errorf("%w: not enough bytes to check type uniquness in array", ErrInvalidBytes)
}
key = uint32(next[0])
default:
panic(fmt.Sprintf("unknown type denotation in AtMostOneOfEachTypeValidator passed: %d", typeDenotation))
}
prevIndex, has := seen[key]
if has {
return fmt.Errorf("%w: element %d and %d have the same type", ErrArrayValidationViolatesTypeUniqueness, index, prevIndex)
}
seen[key] = index
return nil
}
}
// ElementValidationFunc returns a new ElementValidationFunc according to the given mode.
func (ar *ArrayRules) ElementValidationFunc() ElementValidationFunc {
var arrayElementValidator ElementValidationFunc
wrap := func(f ElementValidationFunc, f2 ElementValidationFunc) ElementValidationFunc {
return func(index int, next []byte) error {
if f != nil {
if err := f(index, next); err != nil {
return err
}
}
return f2(index, next)
}
}
for i := byte(1); i != 0; i <<= 1 {
switch ArrayValidationMode(byte(ar.ValidationMode) & i) {
case ArrayValidationModeNone:
case ArrayValidationModeNoDuplicates:
if ar.ValidationMode.HasMode(ArrayValidationModeLexicalOrdering) {
continue
}
arrayElementValidator = wrap(arrayElementValidator, ar.ElementUniqueValidator())
case ArrayValidationModeLexicalOrdering:
// optimization: if lexical order and no dups are enforced, then byte comparison
// to the previous element can be done instead of using a map
if ar.ValidationMode.HasMode(ArrayValidationModeNoDuplicates) {
arrayElementValidator = wrap(arrayElementValidator, ar.LexicalOrderWithoutDupsValidator())
continue
}
arrayElementValidator = wrap(arrayElementValidator, ar.LexicalOrderValidator())
case ArrayValidationModeAtMostOneOfEachTypeByte:
arrayElementValidator = wrap(arrayElementValidator, ar.AtMostOneOfEachTypeValidator(TypeDenotationByte))
case ArrayValidationModeAtMostOneOfEachTypeUint32:
arrayElementValidator = wrap(arrayElementValidator, ar.AtMostOneOfEachTypeValidator(TypeDenotationUint32))
}
}
return arrayElementValidator
}
// LexicalOrderedByteSlices are byte slices ordered in lexical order.
type LexicalOrderedByteSlices [][]byte
func (l LexicalOrderedByteSlices) Len() int {
return len(l)
}
func (l LexicalOrderedByteSlices) Less(i, j int) bool {
return bytes.Compare(l[i], l[j]) < 0
}
func (l LexicalOrderedByteSlices) Swap(i, j int) {
l[i], l[j] = l[j], l[i]
}
// LexicalOrdered32ByteArrays are 32 byte arrays ordered in lexical order.
type LexicalOrdered32ByteArrays [][32]byte
func (l LexicalOrdered32ByteArrays) Len() int {
return len(l)
}
func (l LexicalOrdered32ByteArrays) Less(i, j int) bool {
return bytes.Compare(l[i][:], l[j][:]) < 0
}
func (l LexicalOrdered32ByteArrays) Swap(i, j int) {
l[i], l[j] = l[j], l[i]
}
// RemoveDupsAndSortByLexicalOrderArrayOf32Bytes returns a new SliceOfArraysOf32Bytes sorted by lexical order and without duplicates.
func RemoveDupsAndSortByLexicalOrderArrayOf32Bytes(slice SliceOfArraysOf32Bytes) SliceOfArraysOf32Bytes {
seen := make(map[string]struct{})
orderedArray := make(LexicalOrdered32ByteArrays, len(slice))
uniqueElements := 0
for _, v := range slice {
k := string(v[:])
if _, has := seen[k]; has {
continue
}
seen[k] = struct{}{}
orderedArray[uniqueElements] = v
uniqueElements++
}
orderedArray = orderedArray[:uniqueElements]
sort.Sort(orderedArray)
return orderedArray
}
// SortedSerializables are Serializables sorted by their serialized form.
type SortedSerializables Serializables
func (ss SortedSerializables) Len() int {
return len(ss)
}
func (ss SortedSerializables) Less(i, j int) bool {
iData, _ := ss[i].Serialize(DeSeriModeNoValidation, nil)
jData, _ := ss[j].Serialize(DeSeriModeNoValidation, nil)
return bytes.Compare(iData, jData) < 0
}
func (ss SortedSerializables) Swap(i, j int) {
ss[i], ss[j] = ss[j], ss[i]
}