/
util.go
441 lines (418 loc) · 15.4 KB
/
util.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
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
// Copyright 2015 The Vanadium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package vdl
import (
"fmt"
"reflect"
"sync"
"unsafe"
)
const (
// IEEE 754 represents float64 using 52 bits to represent the mantissa, with
// an extra implied leading bit. That gives us 53 bits to store integers
// without overflow - i.e. [0, (2^53)-1]. And since 2^53 is a small power of
// two, it can also be stored without loss via mantissa=1 exponent=53. Thus
// we have our max and min values. Ditto for float32, which uses 23 bits with
// an extra implied leading bit.
float64MaxInt = (1 << 53)
float64MinInt = -(1 << 53)
float32MaxInt = (1 << 24)
float32MinInt = -(1 << 24)
)
var (
bitlenReflect = [...]uintptr{
reflect.Uint8: 8,
reflect.Uint16: 16,
reflect.Uint32: 32,
reflect.Uint64: 64,
reflect.Uint: 8 * unsafe.Sizeof(uint(0)),
reflect.Uintptr: 8 * unsafe.Sizeof(uintptr(0)),
reflect.Int8: 8,
reflect.Int16: 16,
reflect.Int32: 32,
reflect.Int64: 64,
reflect.Int: 8 * unsafe.Sizeof(int(0)),
reflect.Float32: 32,
reflect.Float64: 64,
}
bitlenVDL = [...]uintptr{
Byte: 8,
Uint16: 16,
Uint32: 32,
Uint64: 64,
Int8: 8,
Int16: 16,
Int32: 32,
Int64: 64,
Float32: 32,
Float64: 64,
}
)
// bitlen{R,V} enforce static type safety on kind.
//nolint:deadcode,unused
func bitlenR(kind reflect.Kind) uintptr { return bitlenReflect[kind] }
//nolint:deadcode,unused
func bitlenV(kind Kind) uintptr { return bitlenVDL[kind] }
// isRTBytes returns true iff rt is an array or slice of bytes.
//nolint:deadcode,unused
func isRTBytes(rt reflect.Type) bool {
return (rt.Kind() == reflect.Array || rt.Kind() == reflect.Slice) && rt.Elem().Kind() == reflect.Uint8
}
// rtBytes extracts []byte from rv. Assumes isRTBytes(rv.Type()) == true.
//nolint:deadcode,unused
func rtBytes(rv reflect.Value) []byte {
// Fastpath if the underlying type is []byte
if rv.Kind() == reflect.Slice && rv.Type().Elem() == rtByte {
return rv.Bytes()
}
// Slowpath copying bytes one by one.
ret := make([]byte, rv.Len())
for ix := 0; ix < rv.Len(); ix++ {
ret[ix] = rv.Index(ix).Convert(rtByte).Interface().(byte)
}
return ret
}
// IsZeroer is the interface that wraps the VDLIsZero method.
//
// VDLIsZero returns true iff the receiver that implements this method is the
// VDL zero value.
type IsZeroer interface {
VDLIsZero() bool
}
type stringer interface {
String() string
}
type namer interface {
Name() string
}
type indexer interface {
Index() int
}
// rvFlattenPointers repeatedly dereferences pointers, creating new values if
// the pointer is nil, and returns the final non-pointer reflect value. As a
// special-case, *Type is returned as a pointer.
func rvFlattenPointers(rv reflect.Value) reflect.Value {
for rv.Kind() == reflect.Ptr {
if rv.Type() == rtPtrToType {
// Special-case to stop at *Type, which is filled in via readNonReflect by
// the reader, or by rvZeroValue.
return rv
}
if rv.IsNil() {
rv.Set(reflect.New(rv.Type().Elem()))
}
rv = rv.Elem()
}
return rv
}
// zeroDecoder is a decoder that only returns zero values.
type zeroDecoder struct{ tt *Type }
func (z zeroDecoder) StartValue(want *Type) error {
if !Compatible(z.tt, want) {
return fmt.Errorf("vdl: zero incompatible decode from %v into %v", z.tt, want)
}
return nil
}
func (z zeroDecoder) FinishValue() error { return nil }
func (z zeroDecoder) SkipValue() error { return nil }
func (z zeroDecoder) IgnoreNextStartValue() {}
func (z zeroDecoder) NextEntry() (bool, error) { return true, nil }
func (z zeroDecoder) NextField() (int, error) { return -1, nil }
func (z zeroDecoder) Type() *Type { return z.tt }
func (z zeroDecoder) IsAny() bool { return z.tt == AnyType }
func (z zeroDecoder) IsOptional() bool { return z.tt.Kind() == Optional }
func (z zeroDecoder) IsNil() bool { return z.IsAny() || z.IsOptional() }
func (z zeroDecoder) Index() int { return 0 }
func (z zeroDecoder) LenHint() int { return 0 }
func (z zeroDecoder) DecodeBool() (bool, error) { return false, nil }
func (z zeroDecoder) DecodeString() (string, error) { return "", nil }
func (z zeroDecoder) DecodeUint(int) (uint64, error) { return 0, nil }
func (z zeroDecoder) DecodeInt(int) (int64, error) { return 0, nil }
func (z zeroDecoder) DecodeFloat(int) (float64, error) { return 0, nil }
func (z zeroDecoder) DecodeTypeObject() (*Type, error) { return AnyType, nil }
func (z zeroDecoder) DecodeBytes(fixedLen int, x *[]byte) error {
if fixedLen >= 0 {
for i := 0; i < fixedLen; i++ {
(*x)[i] = 0
}
} else {
*x = nil
}
return nil
}
func (z zeroDecoder) ReadValueBool() (bool, error) { return false, nil }
func (z zeroDecoder) ReadValueString() (string, error) { return "", nil }
func (z zeroDecoder) ReadValueUint(bitlen int) (uint64, error) { return 0, nil }
func (z zeroDecoder) ReadValueInt(bitlen int) (int64, error) { return 0, nil }
func (z zeroDecoder) ReadValueFloat(bitlen int) (float64, error) { return 0, nil }
func (z zeroDecoder) ReadValueTypeObject() (*Type, error) { return AnyType, nil }
func (z zeroDecoder) ReadValueBytes(fixedLen int, x *[]byte) error {
return z.DecodeBytes(fixedLen, x)
}
func (z zeroDecoder) NextEntryValueBool() (bool, bool, error) { return true, false, nil }
func (z zeroDecoder) NextEntryValueString() (bool, string, error) { return true, "", nil }
func (z zeroDecoder) NextEntryValueUint(bitlen int) (bool, uint64, error) { return true, 0, nil }
func (z zeroDecoder) NextEntryValueInt(bitlen int) (bool, int64, error) { return true, 0, nil }
func (z zeroDecoder) NextEntryValueFloat(bitlen int) (bool, float64, error) { return true, 0, nil }
func (z zeroDecoder) NextEntryValueTypeObject() (bool, *Type, error) { return true, nil, nil }
var (
//nolint:deadcode,unused,varcheck
rvAnyType = reflect.ValueOf(AnyType)
kkZeroValueNotCanonical = []Kind{Any, TypeObject, Union}
//nolint:deadcode,unused,varcheck
kkZeroValueNotUnique = []Kind{Any, TypeObject, Union, List, Set, Map}
)
// rvZeroValue returns the zero value of rt, using the vdl zero rules.
//
// VDL and Go define zero values differently. According to VDL:
// Any: nil
// TypeObject: AnyType
// Union: zero value of the type at index 0
// The Go zero value isn't always right. Here are the Go zero values:
// Any: interface{}(nil), *vom.RawBytes(nil) or *vdl.Value(nil)
// TypeObject: (*Type)(nil)
// Union: UnionInterface(nil)
// Here are the Go values we actually want:
// Any: *vom.RawBytes or *vdl.Value representing any(nil)
// TypeObject: AnyType
// Union: UnionStruct0
//
// Thus we must special-case values of these types, or any types that contain
// these types inline. I.e. if an array, struct, or union contains one of these
// types, it will show up in the zero value, and needs special-casing.
//
// TODO(toddw): Cache the generated zero values, if it's too expensive to
// generate them each time.
func rvZeroValue(rt reflect.Type, tt *Type) (reflect.Value, error) { //nolint:gocyclo
// Easy fastpath; if the type doesn't contain the hard types inline, the
// regular Go zero value is sufficient.
if !tt.ContainsKind(WalkInline, kkZeroValueNotCanonical...) {
return reflect.Zero(rt), nil
}
// Create the result we'll return.
result := reflect.New(rt).Elem()
// Flatten pointers and check for fast non-reflect support. We re-use the
// readNonReflect logic with a decoder that only produces zero values. This
// handles vom.RawBytes/vdl.Value, as well as TypeObject.
rv := rvFlattenPointers(result)
rt = rv.Type()
if err := readNonReflect(zeroDecoder{tt}, false, rv.Addr().Interface()); err != errReadMustReflect {
return result, err
}
// The only representation left for Any types is nil interfaces
if tt == AnyType && rt.Kind() == reflect.Interface {
return result, nil
}
// Handle native types by returning the native value filled in with a zero
// value of the wire type.
if ni := nativeInfoFromNative(rt); ni != nil {
rvWire := reflect.New(ni.WireType).Elem()
ttWire, err := TypeFromReflect(ni.WireType)
if err != nil {
return reflect.Value{}, err
}
switch zero, err := rvZeroValue(ni.WireType, ttWire); {
case err != nil:
return reflect.Value{}, err
default:
rvWire.Set(zero)
}
if err := ni.ToNative(rvWire, rv.Addr()); err != nil {
return reflect.Value{}, err
}
return result, nil
}
// Handle composite types with inline subtypes.
switch {
case tt.Kind() == Union && rt.Kind() == reflect.Interface:
// Set the union interface with the zero value of the type at index 0.
ri, _, err := deriveReflectInfo(rt)
if err != nil {
return reflect.Value{}, err
}
rvFieldStruct := reflect.New(ri.UnionFields[0].RepType).Elem()
switch zero, err := rvZeroValue(rvFieldStruct.Field(0).Type(), tt.Field(0).Type); {
case err != nil:
return reflect.Value{}, err
default:
rvFieldStruct.Field(0).Set(zero)
rv.Set(rvFieldStruct)
}
case tt.Kind() == Array && rt.Kind() == reflect.Array:
for ix := 0; ix < rt.Len(); ix++ {
switch zero, err := rvZeroValue(rt.Elem(), tt.Elem()); {
case err != nil:
return reflect.Value{}, err
default:
rv.Index(ix).Set(zero)
}
}
case tt.Kind() == Struct && rt.Kind() == reflect.Struct:
for ix := 0; ix < tt.NumField(); ix++ {
field := tt.Field(ix)
rvField := rv.Field(rtFieldIndexByName(rt, field.Name))
switch zero, err := rvZeroValue(rvField.Type(), field.Type); {
case err != nil:
return reflect.Value{}, err
default:
rvField.Set(zero)
}
}
default:
return reflect.Value{}, fmt.Errorf("vdl: rvZeroValue unhandled rt: %v tt: %v", rt, tt)
}
return result, nil
}
// rvIsZeroValue returns true iff rv represents the VDL zero value. Here are
// the types with multiple VDL zero value representations:
// Any: nil, or VDLIsZero on vdl.Value/vom.RawBytes
// TypeObject: nil, or AnyType
// Union: nil, or zero value of field 0
// List, Set, Map: nil, or empty
func rvIsZeroValue(rv reflect.Value, tt *Type) (bool, error) { //nolint:gocyclo
// Walk pointers and interfaces, and handle nil values.
for rv.Kind() == reflect.Ptr || rv.Kind() == reflect.Interface {
if rv.IsNil() {
// All nil pointers and nil interfaces are considered to be zero. Note
// that we may have a non-optional type that happens to be represented by
// a pointer; technically nil might be considered an error, but it's
// easier for the user (and for us) to treat it as zero.
return true, nil
}
rv = rv.Elem()
}
// Optional types can only be zero via a nil pointer or interface.
if tt.Kind() == Optional {
return false, nil
}
rt := rv.Type()
// Now we know that rv isn't a pointer or interface, and also isn't nil. Call
// VDLIsZero if it exists. This handles the vdl.Value/vom.RawBytes cases, as
// well generated code and user-implemented VDLIsZero methods.
if rt.Implements(rtIsZeroer) {
return rv.Interface().(IsZeroer).VDLIsZero(), nil
}
if reflect.PtrTo(rt).Implements(rtIsZeroer) {
if rv.CanAddr() {
return rv.Addr().Interface().(IsZeroer).VDLIsZero(), nil
}
// Handle the harder case where *T implements IsZeroer, but we can't take
// the address of rv to turn it into *T. Create a new *T value and fill it
// in with rv, so that we can call VDLIsZero. This is conceptually similar
// to storing rv in a temporary variable, so that we can take the address.
rvPtr := reflect.New(rt)
rvPtr.Elem().Set(rv)
return rvPtr.Interface().(IsZeroer).VDLIsZero(), nil
}
// Handle native types, by converting and checking the wire value for zero.
if ni := nativeInfoFromNative(rt); ni != nil {
rvWirePtr := reflect.New(ni.WireType)
if err := ni.FromNative(rvWirePtr, rv); err != nil {
return false, err
}
return rvIsZeroValue(rvWirePtr.Elem(), tt)
}
// The interface form of any was handled above in the nil checks, while the
// non-interface forms were handled via VDLIsZero.
if tt.Kind() == Optional || tt.Kind() == Any {
return false, nil
}
// TODO(toddw): We could consider adding a "fastpath" here to check against
// the go zero value, or the zero value created by rvZeroValue, and possibly
// returning early. This is tricky though; we can't use this fastpath if rt
// contains any native types, but the only way to know whether rt contains any
// native types is to look through the entire type, which might actually be
// slower than the benefit of this "fastpath". The cases where it'll help are
// large arrays or structs.
//
// Handle all reflect cases.
switch rv.Kind() {
case reflect.Bool:
return !rv.Bool(), nil
case reflect.String:
return rv.String() == "", nil
case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
return rv.Int() == 0, nil
case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
return rv.Uint() == 0, nil
case reflect.Float32, reflect.Float64:
return rv.Float() == 0, nil
case reflect.Complex64, reflect.Complex128:
return rv.Complex() == 0, nil
case reflect.UnsafePointer:
return rv.Pointer() == 0, nil
case reflect.Slice, reflect.Map:
return rv.Len() == 0, nil
case reflect.Array:
for ix := 0; ix < rv.Len(); ix++ {
if z, err := rvIsZeroValue(rv.Index(ix), tt.Elem()); err != nil || !z {
return false, err
}
}
return true, nil
case reflect.Struct:
switch tt.Kind() {
case Struct:
for ix := 0; ix < tt.NumField(); ix++ {
ttField := tt.Field(ix)
rvField := rv.Field(rtFieldIndexByName(rt, ttField.Name))
if z, err := rvIsZeroValue(rvField, ttField.Type); err != nil || !z {
return false, err
}
}
return true, nil
case Union:
// We already handled the nil union interface case above in the regular
// pointer/interface walking. Here we check to make sure the union field
// struct represents field 0, and is set to its zero value.
//
// TypeFromReflect already validated Index(); call without error checking.
if index := rv.Interface().(indexer).Index(); index != 0 {
return false, nil
}
return rvIsZeroValue(rv.Field(0), tt.Field(0).Type)
}
}
return false, fmt.Errorf("vdl: rvIsZeroValue unhandled rt: %v tt: %v", rt, tt)
}
// rtFieldIndexByName returns the index of the struct field in rt with the given
// name. Returns -1 if the field doesn't exist.
//
// This function is purely a performance optimization; the current
// implementation of reflect.Type.Field(index) causes an allocation, which is
// avoided in the common case by caching the result.
//
// REQUIRES: rt.Kind() == reflect.Struct
func rtFieldIndexByName(rt reflect.Type, name string) int {
rtFieldCache.RLock()
m, ok := rtFieldCache.Map[rt]
rtFieldCache.RUnlock()
// Fastpath cache hit.
if ok {
return m[name] - 1
}
// Slowpath cache miss, populate the cache.
rtFieldCache.Lock()
defer rtFieldCache.Unlock()
// Handle benign race, where the cache was filled in while we upgraded from a
// reader lock to an exclusive lock.
if m, ok := rtFieldCache.Map[rt]; ok {
return m[name] - 1
}
if numField := rt.NumField(); numField > 0 {
m = make(map[string]int, numField)
for i := 0; i < numField; i++ {
m[rt.Field(i).Name] = i + 1
}
}
rtFieldCache.Map[rt] = m
return m[name] - 1
}
var rtFieldCache = &rtFieldCacheType{
Map: make(map[reflect.Type]map[string]int),
}
type rtFieldCacheType struct {
sync.RWMutex
Map map[reflect.Type]map[string]int
}