libgo/go/gob/encode.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package gob
   6
   7 import (
   8         "bytes"
   9         "io"
  10         "math"
  11         "os"
  12         "reflect"
  13         "unsafe"
  14 )
  15
  16 const uint64Size = unsafe.Sizeof(uint64(0))
  17
  18 // The global execution state of an instance of the encoder.
  19 // Field numbers are delta encoded and always increase. The field
  20 // number is initialized to -1 so 0 comes out as delta(1). A delta of
  21 // 0 terminates the structure.
  22 type encoderState struct {
  23         enc      *Encoder
  24         b        *bytes.Buffer
  25         sendZero bool                 // encoding an array element or map key/value pair; send zero values
  26         fieldnum int                  // the last field number written.
  27         buf      [1 + uint64Size]byte // buffer used by the encoder; here to avoid allocation.
  28 }
  29
  30 func newEncoderState(enc *Encoder, b *bytes.Buffer) *encoderState {
  31         return &encoderState{enc: enc, b: b}
  32 }
  33
  34 // Unsigned integers have a two-state encoding.  If the number is less
  35 // than 128 (0 through 0x7F), its value is written directly.
  36 // Otherwise the value is written in big-endian byte order preceded
  37 // by the byte length, negated.
  38
  39 // encodeUint writes an encoded unsigned integer to state.b.
  40 func encodeUint(state *encoderState, x uint64) {
  41         if x <= 0x7F {
  42                 err := state.b.WriteByte(uint8(x))
  43                 if err != nil {
  44                         error(err)
  45                 }
  46                 return
  47         }
  48         var n, m int
  49         m = uint64Size
  50         for n = 1; x > 0; n++ {
  51                 state.buf[m] = uint8(x & 0xFF)
  52                 x >>= 8
  53                 m--
  54         }
  55         state.buf[m] = uint8(-(n - 1))
  56         n, err := state.b.Write(state.buf[m : uint64Size+1])
  57         if err != nil {
  58                 error(err)
  59         }
  60 }
  61
  62 // encodeInt writes an encoded signed integer to state.w.
  63 // The low bit of the encoding says whether to bit complement the (other bits of the)
  64 // uint to recover the int.
  65 func encodeInt(state *encoderState, i int64) {
  66         var x uint64
  67         if i < 0 {
  68                 x = uint64(^i<<1) | 1
  69         } else {
  70                 x = uint64(i << 1)
  71         }
  72         encodeUint(state, uint64(x))
  73 }
  74
  75 type encOp func(i *encInstr, state *encoderState, p unsafe.Pointer)
  76
  77 // The 'instructions' of the encoding machine
  78 type encInstr struct {
  79         op     encOp
  80         field  int     // field number
  81         indir  int     // how many pointer indirections to reach the value in the struct
  82         offset uintptr // offset in the structure of the field to encode
  83 }
  84
  85 // Emit a field number and update the state to record its value for delta encoding.
  86 // If the instruction pointer is nil, do nothing
  87 func (state *encoderState) update(instr *encInstr) {
  88         if instr != nil {
  89                 encodeUint(state, uint64(instr.field-state.fieldnum))
  90                 state.fieldnum = instr.field
  91         }
  92 }
  93
  94 // Each encoder is responsible for handling any indirections associated
  95 // with the data structure.  If any pointer so reached is nil, no bytes are written.
  96 // If the data item is zero, no bytes are written.
  97 // Otherwise, the output (for a scalar) is the field number, as an encoded integer,
  98 // followed by the field data in its appropriate format.
  99
 100 func encIndirect(p unsafe.Pointer, indir int) unsafe.Pointer {
 101         for ; indir > 0; indir-- {
 102                 p = *(*unsafe.Pointer)(p)
 103                 if p == nil {
 104                         return unsafe.Pointer(nil)
 105                 }
 106         }
 107         return p
 108 }
 109
 110 func encBool(i *encInstr, state *encoderState, p unsafe.Pointer) {
 111         b := *(*bool)(p)
 112         if b || state.sendZero {
 113                 state.update(i)
 114                 if b {
 115                         encodeUint(state, 1)
 116                 } else {
 117                         encodeUint(state, 0)
 118                 }
 119         }
 120 }
 121
 122 func encInt(i *encInstr, state *encoderState, p unsafe.Pointer) {
 123         v := int64(*(*int)(p))
 124         if v != 0 || state.sendZero {
 125                 state.update(i)
 126                 encodeInt(state, v)
 127         }
 128 }
 129
 130 func encUint(i *encInstr, state *encoderState, p unsafe.Pointer) {
 131         v := uint64(*(*uint)(p))
 132         if v != 0 || state.sendZero {
 133                 state.update(i)
 134                 encodeUint(state, v)
 135         }
 136 }
 137
 138 func encInt8(i *encInstr, state *encoderState, p unsafe.Pointer) {
 139         v := int64(*(*int8)(p))
 140         if v != 0 || state.sendZero {
 141                 state.update(i)
 142                 encodeInt(state, v)
 143         }
 144 }
 145
 146 func encUint8(i *encInstr, state *encoderState, p unsafe.Pointer) {
 147         v := uint64(*(*uint8)(p))
 148         if v != 0 || state.sendZero {
 149                 state.update(i)
 150                 encodeUint(state, v)
 151         }
 152 }
 153
 154 func encInt16(i *encInstr, state *encoderState, p unsafe.Pointer) {
 155         v := int64(*(*int16)(p))
 156         if v != 0 || state.sendZero {
 157                 state.update(i)
 158                 encodeInt(state, v)
 159         }
 160 }
 161
 162 func encUint16(i *encInstr, state *encoderState, p unsafe.Pointer) {
 163         v := uint64(*(*uint16)(p))
 164         if v != 0 || state.sendZero {
 165                 state.update(i)
 166                 encodeUint(state, v)
 167         }
 168 }
 169
 170 func encInt32(i *encInstr, state *encoderState, p unsafe.Pointer) {
 171         v := int64(*(*int32)(p))
 172         if v != 0 || state.sendZero {
 173                 state.update(i)
 174                 encodeInt(state, v)
 175         }
 176 }
 177
 178 func encUint32(i *encInstr, state *encoderState, p unsafe.Pointer) {
 179         v := uint64(*(*uint32)(p))
 180         if v != 0 || state.sendZero {
 181                 state.update(i)
 182                 encodeUint(state, v)
 183         }
 184 }
 185
 186 func encInt64(i *encInstr, state *encoderState, p unsafe.Pointer) {
 187         v := *(*int64)(p)
 188         if v != 0 || state.sendZero {
 189                 state.update(i)
 190                 encodeInt(state, v)
 191         }
 192 }
 193
 194 func encUint64(i *encInstr, state *encoderState, p unsafe.Pointer) {
 195         v := *(*uint64)(p)
 196         if v != 0 || state.sendZero {
 197                 state.update(i)
 198                 encodeUint(state, v)
 199         }
 200 }
 201
 202 func encUintptr(i *encInstr, state *encoderState, p unsafe.Pointer) {
 203         v := uint64(*(*uintptr)(p))
 204         if v != 0 || state.sendZero {
 205                 state.update(i)
 206                 encodeUint(state, v)
 207         }
 208 }
 209
 210 // Floating-point numbers are transmitted as uint64s holding the bits
 211 // of the underlying representation.  They are sent byte-reversed, with
 212 // the exponent end coming out first, so integer floating point numbers
 213 // (for example) transmit more compactly.  This routine does the
 214 // swizzling.
 215 func floatBits(f float64) uint64 {
 216         u := math.Float64bits(f)
 217         var v uint64
 218         for i := 0; i < 8; i++ {
 219                 v <<= 8
 220                 v |= u & 0xFF
 221                 u >>= 8
 222         }
 223         return v
 224 }
 225
 226 func encFloat(i *encInstr, state *encoderState, p unsafe.Pointer) {
 227         f := *(*float)(p)
 228         if f != 0 || state.sendZero {
 229                 v := floatBits(float64(f))
 230                 state.update(i)
 231                 encodeUint(state, v)
 232         }
 233 }
 234
 235 func encFloat32(i *encInstr, state *encoderState, p unsafe.Pointer) {
 236         f := *(*float32)(p)
 237         if f != 0 || state.sendZero {
 238                 v := floatBits(float64(f))
 239                 state.update(i)
 240                 encodeUint(state, v)
 241         }
 242 }
 243
 244 func encFloat64(i *encInstr, state *encoderState, p unsafe.Pointer) {
 245         f := *(*float64)(p)
 246         if f != 0 || state.sendZero {
 247                 state.update(i)
 248                 v := floatBits(f)
 249                 encodeUint(state, v)
 250         }
 251 }
 252
 253 // Complex numbers are just a pair of floating-point numbers, real part first.
 254 func encComplex(i *encInstr, state *encoderState, p unsafe.Pointer) {
 255         c := *(*complex)(p)
 256         if c != 0+0i || state.sendZero {
 257                 rpart := floatBits(float64(real(c)))
 258                 ipart := floatBits(float64(imag(c)))
 259                 state.update(i)
 260                 encodeUint(state, rpart)
 261                 encodeUint(state, ipart)
 262         }
 263 }
 264
 265 func encComplex64(i *encInstr, state *encoderState, p unsafe.Pointer) {
 266         c := *(*complex64)(p)
 267         if c != 0+0i || state.sendZero {
 268                 rpart := floatBits(float64(real(c)))
 269                 ipart := floatBits(float64(imag(c)))
 270                 state.update(i)
 271                 encodeUint(state, rpart)
 272                 encodeUint(state, ipart)
 273         }
 274 }
 275
 276 func encComplex128(i *encInstr, state *encoderState, p unsafe.Pointer) {
 277         c := *(*complex128)(p)
 278         if c != 0+0i || state.sendZero {
 279                 rpart := floatBits(real(c))
 280                 ipart := floatBits(imag(c))
 281                 state.update(i)
 282                 encodeUint(state, rpart)
 283                 encodeUint(state, ipart)
 284         }
 285 }
 286
 287 // Byte arrays are encoded as an unsigned count followed by the raw bytes.
 288 func encUint8Array(i *encInstr, state *encoderState, p unsafe.Pointer) {
 289         b := *(*[]byte)(p)
 290         if len(b) > 0 || state.sendZero {
 291                 state.update(i)
 292                 encodeUint(state, uint64(len(b)))
 293                 state.b.Write(b)
 294         }
 295 }
 296
 297 // Strings are encoded as an unsigned count followed by the raw bytes.
 298 func encString(i *encInstr, state *encoderState, p unsafe.Pointer) {
 299         s := *(*string)(p)
 300         if len(s) > 0 || state.sendZero {
 301                 state.update(i)
 302                 encodeUint(state, uint64(len(s)))
 303                 io.WriteString(state.b, s)
 304         }
 305 }
 306
 307 // The end of a struct is marked by a delta field number of 0.
 308 func encStructTerminator(i *encInstr, state *encoderState, p unsafe.Pointer) {
 309         encodeUint(state, 0)
 310 }
 311
 312 // Execution engine
 313
 314 // The encoder engine is an array of instructions indexed by field number of the encoding
 315 // data, typically a struct.  It is executed top to bottom, walking the struct.
 316 type encEngine struct {
 317         instr []encInstr
 318 }
 319
 320 const singletonField = 0
 321
 322 func (enc *Encoder) encodeSingle(b *bytes.Buffer, engine *encEngine, basep uintptr) {
 323         state := newEncoderState(enc, b)
 324         state.fieldnum = singletonField
 325         // There is no surrounding struct to frame the transmission, so we must
 326         // generate data even if the item is zero.  To do this, set sendZero.
 327         state.sendZero = true
 328         instr := &engine.instr[singletonField]
 329         p := unsafe.Pointer(basep) // offset will be zero
 330         if instr.indir > 0 {
 331                 if p = encIndirect(p, instr.indir); p == nil {
 332                         return
 333                 }
 334         }
 335         instr.op(instr, state, p)
 336 }
 337
 338 func (enc *Encoder) encodeStruct(b *bytes.Buffer, engine *encEngine, basep uintptr) {
 339         state := newEncoderState(enc, b)
 340         state.fieldnum = -1
 341         for i := 0; i < len(engine.instr); i++ {
 342                 instr := &engine.instr[i]
 343                 p := unsafe.Pointer(basep + instr.offset)
 344                 if instr.indir > 0 {
 345                         if p = encIndirect(p, instr.indir); p == nil {
 346                                 continue
 347                         }
 348                 }
 349                 instr.op(instr, state, p)
 350         }
 351 }
 352
 353 func (enc *Encoder) encodeArray(b *bytes.Buffer, p uintptr, op encOp, elemWid uintptr, elemIndir int, length int) {
 354         state := newEncoderState(enc, b)
 355         state.fieldnum = -1
 356         state.sendZero = true
 357         encodeUint(state, uint64(length))
 358         for i := 0; i < length; i++ {
 359                 elemp := p
 360                 up := unsafe.Pointer(elemp)
 361                 if elemIndir > 0 {
 362                         if up = encIndirect(up, elemIndir); up == nil {
 363                                 errorf("gob: encodeArray: nil element")
 364                         }
 365                         elemp = uintptr(up)
 366                 }
 367                 op(nil, state, unsafe.Pointer(elemp))
 368                 p += uintptr(elemWid)
 369         }
 370 }
 371
 372 func encodeReflectValue(state *encoderState, v reflect.Value, op encOp, indir int) {
 373         for i := 0; i < indir && v != nil; i++ {
 374                 v = reflect.Indirect(v)
 375         }
 376         if v == nil {
 377                 errorf("gob: encodeReflectValue: nil element")
 378         }
 379         op(nil, state, unsafe.Pointer(v.Addr()))
 380 }
 381
 382 func (enc *Encoder) encodeMap(b *bytes.Buffer, mv *reflect.MapValue, keyOp, elemOp encOp, keyIndir, elemIndir int) {
 383         state := newEncoderState(enc, b)
 384         state.fieldnum = -1
 385         state.sendZero = true
 386         keys := mv.Keys()
 387         encodeUint(state, uint64(len(keys)))
 388         for _, key := range keys {
 389                 encodeReflectValue(state, key, keyOp, keyIndir)
 390                 encodeReflectValue(state, mv.Elem(key), elemOp, elemIndir)
 391         }
 392 }
 393
 394 // To send an interface, we send a string identifying the concrete type, followed
 395 // by the type identifier (which might require defining that type right now), followed
 396 // by the concrete value.  A nil value gets sent as the empty string for the name,
 397 // followed by no value.
 398 func (enc *Encoder) encodeInterface(b *bytes.Buffer, iv *reflect.InterfaceValue) {
 399         state := newEncoderState(enc, b)
 400         state.fieldnum = -1
 401         state.sendZero = true
 402         if iv.IsNil() {
 403                 encodeUint(state, 0)
 404                 return
 405         }
 406
 407         typ, _ := indirect(iv.Elem().Type())
 408         name, ok := concreteTypeToName[typ]
 409         if !ok {
 410                 errorf("gob: type not registered for interface: %s", typ)
 411         }
 412         // Send the name.
 413         encodeUint(state, uint64(len(name)))
 414         _, err := io.WriteString(state.b, name)
 415         if err != nil {
 416                 error(err)
 417         }
 418         // Send (and maybe first define) the type id.
 419         enc.sendTypeDescriptor(typ)
 420         // Encode the value into a new buffer.
 421         data := new(bytes.Buffer)
 422         err = enc.encode(data, iv.Elem())
 423         if err != nil {
 424                 error(err)
 425         }
 426         encodeUint(state, uint64(data.Len()))
 427         _, err = state.b.Write(data.Bytes())
 428         if err != nil {
 429                 error(err)
 430         }
 431 }
 432
 433 var encOpMap = []encOp{
 434         reflect.Bool:       encBool,
 435         reflect.Int:        encInt,
 436         reflect.Int8:       encInt8,
 437         reflect.Int16:      encInt16,
 438         reflect.Int32:      encInt32,
 439         reflect.Int64:      encInt64,
 440         reflect.Uint:       encUint,
 441         reflect.Uint8:      encUint8,
 442         reflect.Uint16:     encUint16,
 443         reflect.Uint32:     encUint32,
 444         reflect.Uint64:     encUint64,
 445         reflect.Uintptr:    encUintptr,
 446         reflect.Float:      encFloat,
 447         reflect.Float32:    encFloat32,
 448         reflect.Float64:    encFloat64,
 449         reflect.Complex:    encComplex,
 450         reflect.Complex64:  encComplex64,
 451         reflect.Complex128: encComplex128,
 452         reflect.String:     encString,
 453 }
 454
 455 // Return the encoding op for the base type under rt and
 456 // the indirection count to reach it.
 457 func (enc *Encoder) encOpFor(rt reflect.Type) (encOp, int) {
 458         typ, indir := indirect(rt)
 459         var op encOp
 460         k := typ.Kind()
 461         if int(k) < len(encOpMap) {
 462                 op = encOpMap[k]
 463         }
 464         if op == nil {
 465                 // Special cases
 466                 switch t := typ.(type) {
 467                 case *reflect.SliceType:
 468                         if t.Elem().Kind() == reflect.Uint8 {
 469                                 op = encUint8Array
 470                                 break
 471                         }
 472                         // Slices have a header; we decode it to find the underlying array.
 473                         elemOp, indir := enc.encOpFor(t.Elem())
 474                         op = func(i *encInstr, state *encoderState, p unsafe.Pointer) {
 475                                 slice := (*reflect.SliceHeader)(p)
 476                                 if slice.Len == 0 {
 477                                         return
 478                                 }
 479                                 state.update(i)
 480                                 state.enc.encodeArray(state.b, slice.Data, elemOp, t.Elem().Size(), indir, int(slice.Len))
 481                         }
 482                 case *reflect.ArrayType:
 483                         // True arrays have size in the type.
 484                         elemOp, indir := enc.encOpFor(t.Elem())
 485                         op = func(i *encInstr, state *encoderState, p unsafe.Pointer) {
 486                                 state.update(i)
 487                                 state.enc.encodeArray(state.b, uintptr(p), elemOp, t.Elem().Size(), indir, t.Len())
 488                         }
 489                 case *reflect.MapType:
 490                         keyOp, keyIndir := enc.encOpFor(t.Key())
 491                         elemOp, elemIndir := enc.encOpFor(t.Elem())
 492                         op = func(i *encInstr, state *encoderState, p unsafe.Pointer) {
 493                                 // Maps cannot be accessed by moving addresses around the way
 494                                 // that slices etc. can.  We must recover a full reflection value for
 495                                 // the iteration.
 496                                 v := reflect.NewValue(unsafe.Unreflect(t, unsafe.Pointer((p))))
 497                                 mv := reflect.Indirect(v).(*reflect.MapValue)
 498                                 if mv.Len() == 0 {
 499                                         return
 500                                 }
 501                                 state.update(i)
 502                                 state.enc.encodeMap(state.b, mv, keyOp, elemOp, keyIndir, elemIndir)
 503                         }
 504                 case *reflect.StructType:
 505                         // Generate a closure that calls out to the engine for the nested type.
 506                         enc.getEncEngine(typ)
 507                         info := mustGetTypeInfo(typ)
 508                         op = func(i *encInstr, state *encoderState, p unsafe.Pointer) {
 509                                 state.update(i)
 510                                 // indirect through info to delay evaluation for recursive structs
 511                                 state.enc.encodeStruct(state.b, info.encoder, uintptr(p))
 512                         }
 513                 case *reflect.InterfaceType:
 514                         op = func(i *encInstr, state *encoderState, p unsafe.Pointer) {
 515                                 // Interfaces transmit the name and contents of the concrete
 516                                 // value they contain.
 517                                 v := reflect.NewValue(unsafe.Unreflect(t, unsafe.Pointer((p))))
 518                                 iv := reflect.Indirect(v).(*reflect.InterfaceValue)
 519                                 if !state.sendZero && (iv == nil || iv.IsNil()) {
 520                                         return
 521                                 }
 522                                 state.update(i)
 523                                 state.enc.encodeInterface(state.b, iv)
 524                         }
 525                 }
 526         }
 527         if op == nil {
 528                 errorf("gob enc: can't happen: encode type %s", rt.String())
 529         }
 530         return op, indir
 531 }
 532
 533 // The local Type was compiled from the actual value, so we know it's compatible.
 534 func (enc *Encoder) compileEnc(rt reflect.Type) *encEngine {
 535         srt, isStruct := rt.(*reflect.StructType)
 536         engine := new(encEngine)
 537         if isStruct {
 538                 engine.instr = make([]encInstr, srt.NumField()+1) // +1 for terminator
 539                 for fieldnum := 0; fieldnum < srt.NumField(); fieldnum++ {
 540                         f := srt.Field(fieldnum)
 541                         op, indir := enc.encOpFor(f.Type)
 542                         engine.instr[fieldnum] = encInstr{op, fieldnum, indir, uintptr(f.Offset)}
 543                 }
 544                 engine.instr[srt.NumField()] = encInstr{encStructTerminator, 0, 0, 0}
 545         } else {
 546                 engine.instr = make([]encInstr, 1)
 547                 op, indir := enc.encOpFor(rt)
 548                 engine.instr[0] = encInstr{op, singletonField, indir, 0} // offset is zero
 549         }
 550         return engine
 551 }
 552
 553 // typeLock must be held (or we're in initialization and guaranteed single-threaded).
 554 // The reflection type must have all its indirections processed out.
 555 func (enc *Encoder) getEncEngine(rt reflect.Type) *encEngine {
 556         info, err1 := getTypeInfo(rt)
 557         if err1 != nil {
 558                 error(err1)
 559         }
 560         if info.encoder == nil {
 561                 // mark this engine as underway before compiling to handle recursive types.
 562                 info.encoder = new(encEngine)
 563                 info.encoder = enc.compileEnc(rt)
 564         }
 565         return info.encoder
 566 }
 567
 568 // Put this in a function so we can hold the lock only while compiling, not when encoding.
 569 func (enc *Encoder) lockAndGetEncEngine(rt reflect.Type) *encEngine {
 570         typeLock.Lock()
 571         defer typeLock.Unlock()
 572         return enc.getEncEngine(rt)
 573 }
 574
 575 func (enc *Encoder) encode(b *bytes.Buffer, value reflect.Value) (err os.Error) {
 576         defer catchError(&err)
 577         // Dereference down to the underlying object.
 578         rt, indir := indirect(value.Type())
 579         for i := 0; i < indir; i++ {
 580                 value = reflect.Indirect(value)
 581         }
 582         engine := enc.lockAndGetEncEngine(rt)
 583         if value.Type().Kind() == reflect.Struct {
 584                 enc.encodeStruct(b, engine, value.Addr())
 585         } else {
 586                 enc.encodeSingle(b, engine, value.Addr())
 587         }
 588         return nil
 589 }