libgo/go/gob/decode.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 // TODO(rsc): When garbage collector changes, revisit
   8 // the allocations in this file that use unsafe.Pointer.
   9
  10 import (
  11         "bytes"
  12         "io"
  13         "math"
  14         "os"
  15         "reflect"
  16         "unsafe"
  17 )
  18
  19 var (
  20         errBadUint = os.NewError("gob: encoded unsigned integer out of range")
  21         errBadType = os.NewError("gob: unknown type id or corrupted data")
  22         errRange   = os.NewError("gob: bad data: field numbers out of bounds")
  23 )
  24
  25 // decoderState is the execution state of an instance of the decoder. A new state
  26 // is created for nested objects.
  27 type decoderState struct {
  28         dec *Decoder
  29         // The buffer is stored with an extra indirection because it may be replaced
  30         // if we load a type during decode (when reading an interface value).
  31         b        *bytes.Buffer
  32         fieldnum int // the last field number read.
  33         buf      []byte
  34         next     *decoderState // for free list
  35 }
  36
  37 // We pass the bytes.Buffer separately for easier testing of the infrastructure
  38 // without requiring a full Decoder.
  39 func (dec *Decoder) newDecoderState(buf *bytes.Buffer) *decoderState {
  40         d := dec.freeList
  41         if d == nil {
  42                 d = new(decoderState)
  43                 d.dec = dec
  44                 d.buf = make([]byte, uint64Size)
  45         } else {
  46                 dec.freeList = d.next
  47         }
  48         d.b = buf
  49         return d
  50 }
  51
  52 func (dec *Decoder) freeDecoderState(d *decoderState) {
  53         d.next = dec.freeList
  54         dec.freeList = d
  55 }
  56
  57 func overflow(name string) os.Error {
  58         return os.NewError(`value for "` + name + `" out of range`)
  59 }
  60
  61 // decodeUintReader reads an encoded unsigned integer from an io.Reader.
  62 // Used only by the Decoder to read the message length.
  63 func decodeUintReader(r io.Reader, buf []byte) (x uint64, width int, err os.Error) {
  64         width = 1
  65         _, err = r.Read(buf[0:width])
  66         if err != nil {
  67                 return
  68         }
  69         b := buf[0]
  70         if b <= 0x7f {
  71                 return uint64(b), width, nil
  72         }
  73         nb := -int(int8(b))
  74         if nb > uint64Size {
  75                 err = errBadUint
  76                 return
  77         }
  78         var n int
  79         n, err = io.ReadFull(r, buf[0:nb])
  80         if err != nil {
  81                 if err == os.EOF {
  82                         err = io.ErrUnexpectedEOF
  83                 }
  84                 return
  85         }
  86         // Could check that the high byte is zero but it's not worth it.
  87         for i := 0; i < n; i++ {
  88                 x <<= 8
  89                 x |= uint64(buf[i])
  90                 width++
  91         }
  92         return
  93 }
  94
  95 // decodeUint reads an encoded unsigned integer from state.r.
  96 // Does not check for overflow.
  97 func (state *decoderState) decodeUint() (x uint64) {
  98         b, err := state.b.ReadByte()
  99         if err != nil {
 100                 error(err)
 101         }
 102         if b <= 0x7f {
 103                 return uint64(b)
 104         }
 105         nb := -int(int8(b))
 106         if nb > uint64Size {
 107                 error(errBadUint)
 108         }
 109         n, err := state.b.Read(state.buf[0:nb])
 110         if err != nil {
 111                 error(err)
 112         }
 113         // Don't need to check error; it's safe to loop regardless.
 114         // Could check that the high byte is zero but it's not worth it.
 115         for i := 0; i < n; i++ {
 116                 x <<= 8
 117                 x |= uint64(state.buf[i])
 118         }
 119         return x
 120 }
 121
 122 // decodeInt reads an encoded signed integer from state.r.
 123 // Does not check for overflow.
 124 func (state *decoderState) decodeInt() int64 {
 125         x := state.decodeUint()
 126         if x&1 != 0 {
 127                 return ^int64(x >> 1)
 128         }
 129         return int64(x >> 1)
 130 }
 131
 132 // decOp is the signature of a decoding operator for a given type.
 133 type decOp func(i *decInstr, state *decoderState, p unsafe.Pointer)
 134
 135 // The 'instructions' of the decoding machine
 136 type decInstr struct {
 137         op     decOp
 138         field  int      // field number of the wire type
 139         indir  int      // how many pointer indirections to reach the value in the struct
 140         offset uintptr  // offset in the structure of the field to encode
 141         ovfl   os.Error // error message for overflow/underflow (for arrays, of the elements)
 142 }
 143
 144 // Since the encoder writes no zeros, if we arrive at a decoder we have
 145 // a value to extract and store.  The field number has already been read
 146 // (it's how we knew to call this decoder).
 147 // Each decoder is responsible for handling any indirections associated
 148 // with the data structure.  If any pointer so reached is nil, allocation must
 149 // be done.
 150
 151 // Walk the pointer hierarchy, allocating if we find a nil.  Stop one before the end.
 152 func decIndirect(p unsafe.Pointer, indir int) unsafe.Pointer {
 153         for ; indir > 1; indir-- {
 154                 if *(*unsafe.Pointer)(p) == nil {
 155                         // Allocation required
 156                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(unsafe.Pointer))
 157                 }
 158                 p = *(*unsafe.Pointer)(p)
 159         }
 160         return p
 161 }
 162
 163 // ignoreUint discards a uint value with no destination.
 164 func ignoreUint(i *decInstr, state *decoderState, p unsafe.Pointer) {
 165         state.decodeUint()
 166 }
 167
 168 // ignoreTwoUints discards a uint value with no destination. It's used to skip
 169 // complex values.
 170 func ignoreTwoUints(i *decInstr, state *decoderState, p unsafe.Pointer) {
 171         state.decodeUint()
 172         state.decodeUint()
 173 }
 174
 175 // decBool decodes a uint and stores it as a boolean through p.
 176 func decBool(i *decInstr, state *decoderState, p unsafe.Pointer) {
 177         if i.indir > 0 {
 178                 if *(*unsafe.Pointer)(p) == nil {
 179                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(bool))
 180                 }
 181                 p = *(*unsafe.Pointer)(p)
 182         }
 183         *(*bool)(p) = state.decodeUint() != 0
 184 }
 185
 186 // decInt8 decodes an integer and stores it as an int8 through p.
 187 func decInt8(i *decInstr, state *decoderState, p unsafe.Pointer) {
 188         if i.indir > 0 {
 189                 if *(*unsafe.Pointer)(p) == nil {
 190                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(int8))
 191                 }
 192                 p = *(*unsafe.Pointer)(p)
 193         }
 194         v := state.decodeInt()
 195         if v < math.MinInt8 || math.MaxInt8 < v {
 196                 error(i.ovfl)
 197         } else {
 198                 *(*int8)(p) = int8(v)
 199         }
 200 }
 201
 202 // decUint8 decodes an unsigned integer and stores it as a uint8 through p.
 203 func decUint8(i *decInstr, state *decoderState, p unsafe.Pointer) {
 204         if i.indir > 0 {
 205                 if *(*unsafe.Pointer)(p) == nil {
 206                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(uint8))
 207                 }
 208                 p = *(*unsafe.Pointer)(p)
 209         }
 210         v := state.decodeUint()
 211         if math.MaxUint8 < v {
 212                 error(i.ovfl)
 213         } else {
 214                 *(*uint8)(p) = uint8(v)
 215         }
 216 }
 217
 218 // decInt16 decodes an integer and stores it as an int16 through p.
 219 func decInt16(i *decInstr, state *decoderState, p unsafe.Pointer) {
 220         if i.indir > 0 {
 221                 if *(*unsafe.Pointer)(p) == nil {
 222                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(int16))
 223                 }
 224                 p = *(*unsafe.Pointer)(p)
 225         }
 226         v := state.decodeInt()
 227         if v < math.MinInt16 || math.MaxInt16 < v {
 228                 error(i.ovfl)
 229         } else {
 230                 *(*int16)(p) = int16(v)
 231         }
 232 }
 233
 234 // decUint16 decodes an unsigned integer and stores it as a uint16 through p.
 235 func decUint16(i *decInstr, state *decoderState, p unsafe.Pointer) {
 236         if i.indir > 0 {
 237                 if *(*unsafe.Pointer)(p) == nil {
 238                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(uint16))
 239                 }
 240                 p = *(*unsafe.Pointer)(p)
 241         }
 242         v := state.decodeUint()
 243         if math.MaxUint16 < v {
 244                 error(i.ovfl)
 245         } else {
 246                 *(*uint16)(p) = uint16(v)
 247         }
 248 }
 249
 250 // decInt32 decodes an integer and stores it as an int32 through p.
 251 func decInt32(i *decInstr, state *decoderState, p unsafe.Pointer) {
 252         if i.indir > 0 {
 253                 if *(*unsafe.Pointer)(p) == nil {
 254                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(int32))
 255                 }
 256                 p = *(*unsafe.Pointer)(p)
 257         }
 258         v := state.decodeInt()
 259         if v < math.MinInt32 || math.MaxInt32 < v {
 260                 error(i.ovfl)
 261         } else {
 262                 *(*int32)(p) = int32(v)
 263         }
 264 }
 265
 266 // decUint32 decodes an unsigned integer and stores it as a uint32 through p.
 267 func decUint32(i *decInstr, state *decoderState, p unsafe.Pointer) {
 268         if i.indir > 0 {
 269                 if *(*unsafe.Pointer)(p) == nil {
 270                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(uint32))
 271                 }
 272                 p = *(*unsafe.Pointer)(p)
 273         }
 274         v := state.decodeUint()
 275         if math.MaxUint32 < v {
 276                 error(i.ovfl)
 277         } else {
 278                 *(*uint32)(p) = uint32(v)
 279         }
 280 }
 281
 282 // decInt64 decodes an integer and stores it as an int64 through p.
 283 func decInt64(i *decInstr, state *decoderState, p unsafe.Pointer) {
 284         if i.indir > 0 {
 285                 if *(*unsafe.Pointer)(p) == nil {
 286                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(int64))
 287                 }
 288                 p = *(*unsafe.Pointer)(p)
 289         }
 290         *(*int64)(p) = int64(state.decodeInt())
 291 }
 292
 293 // decUint64 decodes an unsigned integer and stores it as a uint64 through p.
 294 func decUint64(i *decInstr, state *decoderState, p unsafe.Pointer) {
 295         if i.indir > 0 {
 296                 if *(*unsafe.Pointer)(p) == nil {
 297                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(uint64))
 298                 }
 299                 p = *(*unsafe.Pointer)(p)
 300         }
 301         *(*uint64)(p) = uint64(state.decodeUint())
 302 }
 303
 304 // Floating-point numbers are transmitted as uint64s holding the bits
 305 // of the underlying representation.  They are sent byte-reversed, with
 306 // the exponent end coming out first, so integer floating point numbers
 307 // (for example) transmit more compactly.  This routine does the
 308 // unswizzling.
 309 func floatFromBits(u uint64) float64 {
 310         var v uint64
 311         for i := 0; i < 8; i++ {
 312                 v <<= 8
 313                 v |= u & 0xFF
 314                 u >>= 8
 315         }
 316         return math.Float64frombits(v)
 317 }
 318
 319 // storeFloat32 decodes an unsigned integer, treats it as a 32-bit floating-point
 320 // number, and stores it through p. It's a helper function for float32 and complex64.
 321 func storeFloat32(i *decInstr, state *decoderState, p unsafe.Pointer) {
 322         v := floatFromBits(state.decodeUint())
 323         av := v
 324         if av < 0 {
 325                 av = -av
 326         }
 327         // +Inf is OK in both 32- and 64-bit floats.  Underflow is always OK.
 328         if math.MaxFloat32 < av && av <= math.MaxFloat64 {
 329                 error(i.ovfl)
 330         } else {
 331                 *(*float32)(p) = float32(v)
 332         }
 333 }
 334
 335 // decFloat32 decodes an unsigned integer, treats it as a 32-bit floating-point
 336 // number, and stores it through p.
 337 func decFloat32(i *decInstr, state *decoderState, p unsafe.Pointer) {
 338         if i.indir > 0 {
 339                 if *(*unsafe.Pointer)(p) == nil {
 340                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(float32))
 341                 }
 342                 p = *(*unsafe.Pointer)(p)
 343         }
 344         storeFloat32(i, state, p)
 345 }
 346
 347 // decFloat64 decodes an unsigned integer, treats it as a 64-bit floating-point
 348 // number, and stores it through p.
 349 func decFloat64(i *decInstr, state *decoderState, p unsafe.Pointer) {
 350         if i.indir > 0 {
 351                 if *(*unsafe.Pointer)(p) == nil {
 352                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(float64))
 353                 }
 354                 p = *(*unsafe.Pointer)(p)
 355         }
 356         *(*float64)(p) = floatFromBits(uint64(state.decodeUint()))
 357 }
 358
 359 // decComplex64 decodes a pair of unsigned integers, treats them as a
 360 // pair of floating point numbers, and stores them as a complex64 through p.
 361 // The real part comes first.
 362 func decComplex64(i *decInstr, state *decoderState, p unsafe.Pointer) {
 363         if i.indir > 0 {
 364                 if *(*unsafe.Pointer)(p) == nil {
 365                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(complex64))
 366                 }
 367                 p = *(*unsafe.Pointer)(p)
 368         }
 369         storeFloat32(i, state, p)
 370         storeFloat32(i, state, unsafe.Pointer(uintptr(p)+unsafe.Sizeof(float32(0))))
 371 }
 372
 373 // decComplex128 decodes a pair of unsigned integers, treats them as a
 374 // pair of floating point numbers, and stores them as a complex128 through p.
 375 // The real part comes first.
 376 func decComplex128(i *decInstr, state *decoderState, p unsafe.Pointer) {
 377         if i.indir > 0 {
 378                 if *(*unsafe.Pointer)(p) == nil {
 379                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(complex128))
 380                 }
 381                 p = *(*unsafe.Pointer)(p)
 382         }
 383         real := floatFromBits(uint64(state.decodeUint()))
 384         imag := floatFromBits(uint64(state.decodeUint()))
 385         *(*complex128)(p) = complex(real, imag)
 386 }
 387
 388 // decUint8Array decodes byte array and stores through p a slice header
 389 // describing the data.
 390 // uint8 arrays are encoded as an unsigned count followed by the raw bytes.
 391 func decUint8Array(i *decInstr, state *decoderState, p unsafe.Pointer) {
 392         if i.indir > 0 {
 393                 if *(*unsafe.Pointer)(p) == nil {
 394                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new([]uint8))
 395                 }
 396                 p = *(*unsafe.Pointer)(p)
 397         }
 398         b := make([]uint8, state.decodeUint())
 399         state.b.Read(b)
 400         *(*[]uint8)(p) = b
 401 }
 402
 403 // decString decodes byte array and stores through p a string header
 404 // describing the data.
 405 // Strings are encoded as an unsigned count followed by the raw bytes.
 406 func decString(i *decInstr, state *decoderState, p unsafe.Pointer) {
 407         if i.indir > 0 {
 408                 if *(*unsafe.Pointer)(p) == nil {
 409                         *(*unsafe.Pointer)(p) = unsafe.Pointer(new(string))
 410                 }
 411                 p = *(*unsafe.Pointer)(p)
 412         }
 413         b := make([]byte, state.decodeUint())
 414         state.b.Read(b)
 415         // It would be a shame to do the obvious thing here,
 416         //      *(*string)(p) = string(b)
 417         // because we've already allocated the storage and this would
 418         // allocate again and copy.  So we do this ugly hack, which is even
 419         // even more unsafe than it looks as it depends the memory
 420         // representation of a string matching the beginning of the memory
 421         // representation of a byte slice (a byte slice is longer).
 422         *(*string)(p) = *(*string)(unsafe.Pointer(&b))
 423 }
 424
 425 // ignoreUint8Array skips over the data for a byte slice value with no destination.
 426 func ignoreUint8Array(i *decInstr, state *decoderState, p unsafe.Pointer) {
 427         b := make([]byte, state.decodeUint())
 428         state.b.Read(b)
 429 }
 430
 431 // Execution engine
 432
 433 // The encoder engine is an array of instructions indexed by field number of the incoming
 434 // decoder.  It is executed with random access according to field number.
 435 type decEngine struct {
 436         instr    []decInstr
 437         numInstr int // the number of active instructions
 438 }
 439
 440 // allocate makes sure storage is available for an object of underlying type rtyp
 441 // that is indir levels of indirection through p.
 442 func allocate(rtyp reflect.Type, p uintptr, indir int) uintptr {
 443         if indir == 0 {
 444                 return p
 445         }
 446         up := unsafe.Pointer(p)
 447         if indir > 1 {
 448                 up = decIndirect(up, indir)
 449         }
 450         if *(*unsafe.Pointer)(up) == nil {
 451                 // Allocate object.
 452                 *(*unsafe.Pointer)(up) = unsafe.New(rtyp)
 453         }
 454         return *(*uintptr)(up)
 455 }
 456
 457 // decodeSingle decodes a top-level value that is not a struct and stores it through p.
 458 // Such values are preceded by a zero, making them have the memory layout of a
 459 // struct field (although with an illegal field number).
 460 func (dec *Decoder) decodeSingle(engine *decEngine, ut *userTypeInfo, p uintptr) (err os.Error) {
 461         indir := ut.indir
 462         if ut.isGobDecoder {
 463                 indir = int(ut.decIndir)
 464         }
 465         p = allocate(ut.base, p, indir)
 466         state := dec.newDecoderState(&dec.buf)
 467         state.fieldnum = singletonField
 468         basep := p
 469         delta := int(state.decodeUint())
 470         if delta != 0 {
 471                 errorf("decode: corrupted data: non-zero delta for singleton")
 472         }
 473         instr := &engine.instr[singletonField]
 474         ptr := unsafe.Pointer(basep) // offset will be zero
 475         if instr.indir > 1 {
 476                 ptr = decIndirect(ptr, instr.indir)
 477         }
 478         instr.op(instr, state, ptr)
 479         dec.freeDecoderState(state)
 480         return nil
 481 }
 482
 483 // decodeSingle decodes a top-level struct and stores it through p.
 484 // Indir is for the value, not the type.  At the time of the call it may
 485 // differ from ut.indir, which was computed when the engine was built.
 486 // This state cannot arise for decodeSingle, which is called directly
 487 // from the user's value, not from the innards of an engine.
 488 func (dec *Decoder) decodeStruct(engine *decEngine, ut *userTypeInfo, p uintptr, indir int) {
 489         p = allocate(ut.base, p, indir)
 490         state := dec.newDecoderState(&dec.buf)
 491         state.fieldnum = -1
 492         basep := p
 493         for state.b.Len() > 0 {
 494                 delta := int(state.decodeUint())
 495                 if delta < 0 {
 496                         errorf("decode: corrupted data: negative delta")
 497                 }
 498                 if delta == 0 { // struct terminator is zero delta fieldnum
 499                         break
 500                 }
 501                 fieldnum := state.fieldnum + delta
 502                 if fieldnum >= len(engine.instr) {
 503                         error(errRange)
 504                         break
 505                 }
 506                 instr := &engine.instr[fieldnum]
 507                 p := unsafe.Pointer(basep + instr.offset)
 508                 if instr.indir > 1 {
 509                         p = decIndirect(p, instr.indir)
 510                 }
 511                 instr.op(instr, state, p)
 512                 state.fieldnum = fieldnum
 513         }
 514         dec.freeDecoderState(state)
 515 }
 516
 517 // ignoreStruct discards the data for a struct with no destination.
 518 func (dec *Decoder) ignoreStruct(engine *decEngine) {
 519         state := dec.newDecoderState(&dec.buf)
 520         state.fieldnum = -1
 521         for state.b.Len() > 0 {
 522                 delta := int(state.decodeUint())
 523                 if delta < 0 {
 524                         errorf("ignore decode: corrupted data: negative delta")
 525                 }
 526                 if delta == 0 { // struct terminator is zero delta fieldnum
 527                         break
 528                 }
 529                 fieldnum := state.fieldnum + delta
 530                 if fieldnum >= len(engine.instr) {
 531                         error(errRange)
 532                 }
 533                 instr := &engine.instr[fieldnum]
 534                 instr.op(instr, state, unsafe.Pointer(nil))
 535                 state.fieldnum = fieldnum
 536         }
 537         dec.freeDecoderState(state)
 538 }
 539
 540 // ignoreSingle discards the data for a top-level non-struct value with no
 541 // destination. It's used when calling Decode with a nil value.
 542 func (dec *Decoder) ignoreSingle(engine *decEngine) {
 543         state := dec.newDecoderState(&dec.buf)
 544         state.fieldnum = singletonField
 545         delta := int(state.decodeUint())
 546         if delta != 0 {
 547                 errorf("decode: corrupted data: non-zero delta for singleton")
 548         }
 549         instr := &engine.instr[singletonField]
 550         instr.op(instr, state, unsafe.Pointer(nil))
 551         dec.freeDecoderState(state)
 552 }
 553
 554 // decodeArrayHelper does the work for decoding arrays and slices.
 555 func (dec *Decoder) decodeArrayHelper(state *decoderState, p uintptr, elemOp decOp, elemWid uintptr, length, elemIndir int, ovfl os.Error) {
 556         instr := &decInstr{elemOp, 0, elemIndir, 0, ovfl}
 557         for i := 0; i < length; i++ {
 558                 up := unsafe.Pointer(p)
 559                 if elemIndir > 1 {
 560                         up = decIndirect(up, elemIndir)
 561                 }
 562                 elemOp(instr, state, up)
 563                 p += uintptr(elemWid)
 564         }
 565 }
 566
 567 // decodeArray decodes an array and stores it through p, that is, p points to the zeroth element.
 568 // The length is an unsigned integer preceding the elements.  Even though the length is redundant
 569 // (it's part of the type), it's a useful check and is included in the encoding.
 570 func (dec *Decoder) decodeArray(atyp reflect.Type, state *decoderState, p uintptr, elemOp decOp, elemWid uintptr, length, indir, elemIndir int, ovfl os.Error) {
 571         if indir > 0 {
 572                 p = allocate(atyp, p, 1) // All but the last level has been allocated by dec.Indirect
 573         }
 574         if n := state.decodeUint(); n != uint64(length) {
 575                 errorf("length mismatch in decodeArray")
 576         }
 577         dec.decodeArrayHelper(state, p, elemOp, elemWid, length, elemIndir, ovfl)
 578 }
 579
 580 // decodeIntoValue is a helper for map decoding.  Since maps are decoded using reflection,
 581 // unlike the other items we can't use a pointer directly.
 582 func decodeIntoValue(state *decoderState, op decOp, indir int, v reflect.Value, ovfl os.Error) reflect.Value {
 583         instr := &decInstr{op, 0, indir, 0, ovfl}
 584         up := unsafe.Pointer(unsafeAddr(v))
 585         if indir > 1 {
 586                 up = decIndirect(up, indir)
 587         }
 588         op(instr, state, up)
 589         return v
 590 }
 591
 592 // decodeMap decodes a map and stores its header through p.
 593 // Maps are encoded as a length followed by key:value pairs.
 594 // Because the internals of maps are not visible to us, we must
 595 // use reflection rather than pointer magic.
 596 func (dec *Decoder) decodeMap(mtyp reflect.Type, state *decoderState, p uintptr, keyOp, elemOp decOp, indir, keyIndir, elemIndir int, ovfl os.Error) {
 597         if indir > 0 {
 598                 p = allocate(mtyp, p, 1) // All but the last level has been allocated by dec.Indirect
 599         }
 600         up := unsafe.Pointer(p)
 601         if *(*unsafe.Pointer)(up) == nil { // maps are represented as a pointer in the runtime
 602                 // Allocate map.
 603                 *(*unsafe.Pointer)(up) = unsafe.Pointer(reflect.MakeMap(mtyp).Pointer())
 604         }
 605         // Maps cannot be accessed by moving addresses around the way
 606         // that slices etc. can.  We must recover a full reflection value for
 607         // the iteration.
 608         v := reflect.ValueOf(unsafe.Unreflect(mtyp, unsafe.Pointer(p)))
 609         n := int(state.decodeUint())
 610         for i := 0; i < n; i++ {
 611                 key := decodeIntoValue(state, keyOp, keyIndir, allocValue(mtyp.Key()), ovfl)
 612                 elem := decodeIntoValue(state, elemOp, elemIndir, allocValue(mtyp.Elem()), ovfl)
 613                 v.SetMapIndex(key, elem)
 614         }
 615 }
 616
 617 // ignoreArrayHelper does the work for discarding arrays and slices.
 618 func (dec *Decoder) ignoreArrayHelper(state *decoderState, elemOp decOp, length int) {
 619         instr := &decInstr{elemOp, 0, 0, 0, os.NewError("no error")}
 620         for i := 0; i < length; i++ {
 621                 elemOp(instr, state, nil)
 622         }
 623 }
 624
 625 // ignoreArray discards the data for an array value with no destination.
 626 func (dec *Decoder) ignoreArray(state *decoderState, elemOp decOp, length int) {
 627         if n := state.decodeUint(); n != uint64(length) {
 628                 errorf("length mismatch in ignoreArray")
 629         }
 630         dec.ignoreArrayHelper(state, elemOp, length)
 631 }
 632
 633 // ignoreMap discards the data for a map value with no destination.
 634 func (dec *Decoder) ignoreMap(state *decoderState, keyOp, elemOp decOp) {
 635         n := int(state.decodeUint())
 636         keyInstr := &decInstr{keyOp, 0, 0, 0, os.NewError("no error")}
 637         elemInstr := &decInstr{elemOp, 0, 0, 0, os.NewError("no error")}
 638         for i := 0; i < n; i++ {
 639                 keyOp(keyInstr, state, nil)
 640                 elemOp(elemInstr, state, nil)
 641         }
 642 }
 643
 644 // decodeSlice decodes a slice and stores the slice header through p.
 645 // Slices are encoded as an unsigned length followed by the elements.
 646 func (dec *Decoder) decodeSlice(atyp reflect.Type, state *decoderState, p uintptr, elemOp decOp, elemWid uintptr, indir, elemIndir int, ovfl os.Error) {
 647         n := int(uintptr(state.decodeUint()))
 648         if indir > 0 {
 649                 up := unsafe.Pointer(p)
 650                 if *(*unsafe.Pointer)(up) == nil {
 651                         // Allocate the slice header.
 652                         *(*unsafe.Pointer)(up) = unsafe.Pointer(new([]unsafe.Pointer))
 653                 }
 654                 p = *(*uintptr)(up)
 655         }
 656         // Allocate storage for the slice elements, that is, the underlying array.
 657         // Always write a header at p.
 658         hdrp := (*reflect.SliceHeader)(unsafe.Pointer(p))
 659         hdrp.Data = uintptr(unsafe.NewArray(atyp.Elem(), n))
 660         hdrp.Len = n
 661         hdrp.Cap = n
 662         dec.decodeArrayHelper(state, hdrp.Data, elemOp, elemWid, n, elemIndir, ovfl)
 663 }
 664
 665 // ignoreSlice skips over the data for a slice value with no destination.
 666 func (dec *Decoder) ignoreSlice(state *decoderState, elemOp decOp) {
 667         dec.ignoreArrayHelper(state, elemOp, int(state.decodeUint()))
 668 }
 669
 670 // setInterfaceValue sets an interface value to a concrete value,
 671 // but first it checks that the assignment will succeed.
 672 func setInterfaceValue(ivalue reflect.Value, value reflect.Value) {
 673         if !value.Type().AssignableTo(ivalue.Type()) {
 674                 errorf("cannot assign value of type %s to %s", value.Type(), ivalue.Type())
 675         }
 676         ivalue.Set(value)
 677 }
 678
 679 // decodeInterface decodes an interface value and stores it through p.
 680 // Interfaces are encoded as the name of a concrete type followed by a value.
 681 // If the name is empty, the value is nil and no value is sent.
 682 func (dec *Decoder) decodeInterface(ityp reflect.Type, state *decoderState, p uintptr, indir int) {
 683         // Create a writable interface reflect.Value.  We need one even for the nil case.
 684         ivalue := allocValue(ityp)
 685         // Read the name of the concrete type.
 686         b := make([]byte, state.decodeUint())
 687         state.b.Read(b)
 688         name := string(b)
 689         if name == "" {
 690                 // Copy the representation of the nil interface value to the target.
 691                 // This is horribly unsafe and special.
 692                 *(*[2]uintptr)(unsafe.Pointer(p)) = ivalue.InterfaceData()
 693                 return
 694         }
 695         // The concrete type must be registered.
 696         typ, ok := nameToConcreteType[name]
 697         if !ok {
 698                 errorf("name not registered for interface: %q", name)
 699         }
 700         // Read the type id of the concrete value.
 701         concreteId := dec.decodeTypeSequence(true)
 702         if concreteId < 0 {
 703                 error(dec.err)
 704         }
 705         // Byte count of value is next; we don't care what it is (it's there
 706         // in case we want to ignore the value by skipping it completely).
 707         state.decodeUint()
 708         // Read the concrete value.
 709         value := allocValue(typ)
 710         dec.decodeValue(concreteId, value)
 711         if dec.err != nil {
 712                 error(dec.err)
 713         }
 714         // Allocate the destination interface value.
 715         if indir > 0 {
 716                 p = allocate(ityp, p, 1) // All but the last level has been allocated by dec.Indirect
 717         }
 718         // Assign the concrete value to the interface.
 719         // Tread carefully; it might not satisfy the interface.
 720         setInterfaceValue(ivalue, value)
 721         // Copy the representation of the interface value to the target.
 722         // This is horribly unsafe and special.
 723         *(*[2]uintptr)(unsafe.Pointer(p)) = ivalue.InterfaceData()
 724 }
 725
 726 // ignoreInterface discards the data for an interface value with no destination.
 727 func (dec *Decoder) ignoreInterface(state *decoderState) {
 728         // Read the name of the concrete type.
 729         b := make([]byte, state.decodeUint())
 730         _, err := state.b.Read(b)
 731         if err != nil {
 732                 error(err)
 733         }
 734         id := dec.decodeTypeSequence(true)
 735         if id < 0 {
 736                 error(dec.err)
 737         }
 738         // At this point, the decoder buffer contains a delimited value. Just toss it.
 739         state.b.Next(int(state.decodeUint()))
 740 }
 741
 742 // decodeGobDecoder decodes something implementing the GobDecoder interface.
 743 // The data is encoded as a byte slice.
 744 func (dec *Decoder) decodeGobDecoder(state *decoderState, v reflect.Value) {
 745         // Read the bytes for the value.
 746         b := make([]byte, state.decodeUint())
 747         _, err := state.b.Read(b)
 748         if err != nil {
 749                 error(err)
 750         }
 751         // We know it's a GobDecoder, so just call the method directly.
 752         err = v.Interface().(GobDecoder).GobDecode(b)
 753         if err != nil {
 754                 error(err)
 755         }
 756 }
 757
 758 // ignoreGobDecoder discards the data for a GobDecoder value with no destination.
 759 func (dec *Decoder) ignoreGobDecoder(state *decoderState) {
 760         // Read the bytes for the value.
 761         b := make([]byte, state.decodeUint())
 762         _, err := state.b.Read(b)
 763         if err != nil {
 764                 error(err)
 765         }
 766 }
 767
 768 // Index by Go types.
 769 var decOpTable = [...]decOp{
 770         reflect.Bool:       decBool,
 771         reflect.Int8:       decInt8,
 772         reflect.Int16:      decInt16,
 773         reflect.Int32:      decInt32,
 774         reflect.Int64:      decInt64,
 775         reflect.Uint8:      decUint8,
 776         reflect.Uint16:     decUint16,
 777         reflect.Uint32:     decUint32,
 778         reflect.Uint64:     decUint64,
 779         reflect.Float32:    decFloat32,
 780         reflect.Float64:    decFloat64,
 781         reflect.Complex64:  decComplex64,
 782         reflect.Complex128: decComplex128,
 783         reflect.String:     decString,
 784 }
 785
 786 // Indexed by gob types.  tComplex will be added during type.init().
 787 var decIgnoreOpMap = map[typeId]decOp{
 788         tBool:    ignoreUint,
 789         tInt:     ignoreUint,
 790         tUint:    ignoreUint,
 791         tFloat:   ignoreUint,
 792         tBytes:   ignoreUint8Array,
 793         tString:  ignoreUint8Array,
 794         tComplex: ignoreTwoUints,
 795 }
 796
 797 // decOpFor returns the decoding op for the base type under rt and
 798 // the indirection count to reach it.
 799 func (dec *Decoder) decOpFor(wireId typeId, rt reflect.Type, name string, inProgress map[reflect.Type]*decOp) (*decOp, int) {
 800         ut := userType(rt)
 801         // If the type implements GobEncoder, we handle it without further processing.
 802         if ut.isGobDecoder {
 803                 return dec.gobDecodeOpFor(ut)
 804         }
 805         // If this type is already in progress, it's a recursive type (e.g. map[string]*T).
 806         // Return the pointer to the op we're already building.
 807         if opPtr := inProgress[rt]; opPtr != nil {
 808                 return opPtr, ut.indir
 809         }
 810         typ := ut.base
 811         indir := ut.indir
 812         var op decOp
 813         k := typ.Kind()
 814         if int(k) < len(decOpTable) {
 815                 op = decOpTable[k]
 816         }
 817         if op == nil {
 818                 inProgress[rt] = &op
 819                 // Special cases
 820                 switch t := typ; t.Kind() {
 821                 case reflect.Array:
 822                         name = "element of " + name
 823                         elemId := dec.wireType[wireId].ArrayT.Elem
 824                         elemOp, elemIndir := dec.decOpFor(elemId, t.Elem(), name, inProgress)
 825                         ovfl := overflow(name)
 826                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 827                                 state.dec.decodeArray(t, state, uintptr(p), *elemOp, t.Elem().Size(), t.Len(), i.indir, elemIndir, ovfl)
 828                         }
 829
 830                 case reflect.Map:
 831                         name = "element of " + name
 832                         keyId := dec.wireType[wireId].MapT.Key
 833                         elemId := dec.wireType[wireId].MapT.Elem
 834                         keyOp, keyIndir := dec.decOpFor(keyId, t.Key(), name, inProgress)
 835                         elemOp, elemIndir := dec.decOpFor(elemId, t.Elem(), name, inProgress)
 836                         ovfl := overflow(name)
 837                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 838                                 up := unsafe.Pointer(p)
 839                                 state.dec.decodeMap(t, state, uintptr(up), *keyOp, *elemOp, i.indir, keyIndir, elemIndir, ovfl)
 840                         }
 841
 842                 case reflect.Slice:
 843                         name = "element of " + name
 844                         if t.Elem().Kind() == reflect.Uint8 {
 845                                 op = decUint8Array
 846                                 break
 847                         }
 848                         var elemId typeId
 849                         if tt, ok := builtinIdToType[wireId]; ok {
 850                                 elemId = tt.(*sliceType).Elem
 851                         } else {
 852                                 elemId = dec.wireType[wireId].SliceT.Elem
 853                         }
 854                         elemOp, elemIndir := dec.decOpFor(elemId, t.Elem(), name, inProgress)
 855                         ovfl := overflow(name)
 856                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 857                                 state.dec.decodeSlice(t, state, uintptr(p), *elemOp, t.Elem().Size(), i.indir, elemIndir, ovfl)
 858                         }
 859
 860                 case reflect.Struct:
 861                         // Generate a closure that calls out to the engine for the nested type.
 862                         enginePtr, err := dec.getDecEnginePtr(wireId, userType(typ))
 863                         if err != nil {
 864                                 error(err)
 865                         }
 866                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 867                                 // indirect through enginePtr to delay evaluation for recursive structs.
 868                                 dec.decodeStruct(*enginePtr, userType(typ), uintptr(p), i.indir)
 869                         }
 870                 case reflect.Interface:
 871                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 872                                 state.dec.decodeInterface(t, state, uintptr(p), i.indir)
 873                         }
 874                 }
 875         }
 876         if op == nil {
 877                 errorf("decode can't handle type %s", rt.String())
 878         }
 879         return &op, indir
 880 }
 881
 882 // decIgnoreOpFor returns the decoding op for a field that has no destination.
 883 func (dec *Decoder) decIgnoreOpFor(wireId typeId) decOp {
 884         op, ok := decIgnoreOpMap[wireId]
 885         if !ok {
 886                 if wireId == tInterface {
 887                         // Special case because it's a method: the ignored item might
 888                         // define types and we need to record their state in the decoder.
 889                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 890                                 state.dec.ignoreInterface(state)
 891                         }
 892                         return op
 893                 }
 894                 // Special cases
 895                 wire := dec.wireType[wireId]
 896                 switch {
 897                 case wire == nil:
 898                         errorf("bad data: undefined type %s", wireId.string())
 899                 case wire.ArrayT != nil:
 900                         elemId := wire.ArrayT.Elem
 901                         elemOp := dec.decIgnoreOpFor(elemId)
 902                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 903                                 state.dec.ignoreArray(state, elemOp, wire.ArrayT.Len)
 904                         }
 905
 906                 case wire.MapT != nil:
 907                         keyId := dec.wireType[wireId].MapT.Key
 908                         elemId := dec.wireType[wireId].MapT.Elem
 909                         keyOp := dec.decIgnoreOpFor(keyId)
 910                         elemOp := dec.decIgnoreOpFor(elemId)
 911                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 912                                 state.dec.ignoreMap(state, keyOp, elemOp)
 913                         }
 914
 915                 case wire.SliceT != nil:
 916                         elemId := wire.SliceT.Elem
 917                         elemOp := dec.decIgnoreOpFor(elemId)
 918                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 919                                 state.dec.ignoreSlice(state, elemOp)
 920                         }
 921
 922                 case wire.StructT != nil:
 923                         // Generate a closure that calls out to the engine for the nested type.
 924                         enginePtr, err := dec.getIgnoreEnginePtr(wireId)
 925                         if err != nil {
 926                                 error(err)
 927                         }
 928                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 929                                 // indirect through enginePtr to delay evaluation for recursive structs
 930                                 state.dec.ignoreStruct(*enginePtr)
 931                         }
 932
 933                 case wire.GobEncoderT != nil:
 934                         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 935                                 state.dec.ignoreGobDecoder(state)
 936                         }
 937                 }
 938         }
 939         if op == nil {
 940                 errorf("bad data: ignore can't handle type %s", wireId.string())
 941         }
 942         return op
 943 }
 944
 945 // gobDecodeOpFor returns the op for a type that is known to implement
 946 // GobDecoder.
 947 func (dec *Decoder) gobDecodeOpFor(ut *userTypeInfo) (*decOp, int) {
 948         rcvrType := ut.user
 949         if ut.decIndir == -1 {
 950                 rcvrType = reflect.PtrTo(rcvrType)
 951         } else if ut.decIndir > 0 {
 952                 for i := int8(0); i < ut.decIndir; i++ {
 953                         rcvrType = rcvrType.Elem()
 954                 }
 955         }
 956         var op decOp
 957         op = func(i *decInstr, state *decoderState, p unsafe.Pointer) {
 958                 // Caller has gotten us to within one indirection of our value.
 959                 if i.indir > 0 {
 960                         if *(*unsafe.Pointer)(p) == nil {
 961                                 *(*unsafe.Pointer)(p) = unsafe.New(ut.base)
 962                         }
 963                 }
 964                 // Now p is a pointer to the base type.  Do we need to climb out to
 965                 // get to the receiver type?
 966                 var v reflect.Value
 967                 if ut.decIndir == -1 {
 968                         v = reflect.ValueOf(unsafe.Unreflect(rcvrType, unsafe.Pointer(&p)))
 969                 } else {
 970                         v = reflect.ValueOf(unsafe.Unreflect(rcvrType, p))
 971                 }
 972                 state.dec.decodeGobDecoder(state, v)
 973         }
 974         return &op, int(ut.indir)
 975
 976 }
 977
 978 // compatibleType asks: Are these two gob Types compatible?
 979 // Answers the question for basic types, arrays, maps and slices, plus
 980 // GobEncoder/Decoder pairs.
 981 // Structs are considered ok; fields will be checked later.
 982 func (dec *Decoder) compatibleType(fr reflect.Type, fw typeId, inProgress map[reflect.Type]typeId) bool {
 983         if rhs, ok := inProgress[fr]; ok {
 984                 return rhs == fw
 985         }
 986         inProgress[fr] = fw
 987         ut := userType(fr)
 988         wire, ok := dec.wireType[fw]
 989         // If fr is a GobDecoder, the wire type must be GobEncoder.
 990         // And if fr is not a GobDecoder, the wire type must not be either.
 991         if ut.isGobDecoder != (ok && wire.GobEncoderT != nil) { // the parentheses look odd but are correct.
 992                 return false
 993         }
 994         if ut.isGobDecoder { // This test trumps all others.
 995                 return true
 996         }
 997         switch t := ut.base; t.Kind() {
 998         default:
 999                 // chan, etc: cannot handle.
1000                 return false
1001         case reflect.Bool:
1002                 return fw == tBool
1003         case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
1004                 return fw == tInt
1005         case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
1006                 return fw == tUint
1007         case reflect.Float32, reflect.Float64:
1008                 return fw == tFloat
1009         case reflect.Complex64, reflect.Complex128:
1010                 return fw == tComplex
1011         case reflect.String:
1012                 return fw == tString
1013         case reflect.Interface:
1014                 return fw == tInterface
1015         case reflect.Array:
1016                 if !ok || wire.ArrayT == nil {
1017                         return false
1018                 }
1019                 array := wire.ArrayT
1020                 return t.Len() == array.Len && dec.compatibleType(t.Elem(), array.Elem, inProgress)
1021         case reflect.Map:
1022                 if !ok || wire.MapT == nil {
1023                         return false
1024                 }
1025                 MapType := wire.MapT
1026                 return dec.compatibleType(t.Key(), MapType.Key, inProgress) && dec.compatibleType(t.Elem(), MapType.Elem, inProgress)
1027         case reflect.Slice:
1028                 // Is it an array of bytes?
1029                 if t.Elem().Kind() == reflect.Uint8 {
1030                         return fw == tBytes
1031                 }
1032                 // Extract and compare element types.
1033                 var sw *sliceType
1034                 if tt, ok := builtinIdToType[fw]; ok {
1035                         sw = tt.(*sliceType)
1036                 } else {
1037                         sw = dec.wireType[fw].SliceT
1038                 }
1039                 elem := userType(t.Elem()).base
1040                 return sw != nil && dec.compatibleType(elem, sw.Elem, inProgress)
1041         case reflect.Struct:
1042                 return true
1043         }
1044         return true
1045 }
1046
1047 // typeString returns a human-readable description of the type identified by remoteId.
1048 func (dec *Decoder) typeString(remoteId typeId) string {
1049         if t := idToType[remoteId]; t != nil {
1050                 // globally known type.
1051                 return t.string()
1052         }
1053         return dec.wireType[remoteId].string()
1054 }
1055
1056 // compileSingle compiles the decoder engine for a non-struct top-level value, including
1057 // GobDecoders.
1058 func (dec *Decoder) compileSingle(remoteId typeId, ut *userTypeInfo) (engine *decEngine, err os.Error) {
1059         rt := ut.base
1060         if ut.isGobDecoder {
1061                 rt = ut.user
1062         }
1063         engine = new(decEngine)
1064         engine.instr = make([]decInstr, 1) // one item
1065         name := rt.String()                // best we can do
1066         if !dec.compatibleType(rt, remoteId, make(map[reflect.Type]typeId)) {
1067                 return nil, os.NewError("gob: wrong type received for local value " + name + ": " + dec.typeString(remoteId))
1068         }
1069         op, indir := dec.decOpFor(remoteId, rt, name, make(map[reflect.Type]*decOp))
1070         ovfl := os.NewError(`value for "` + name + `" out of range`)
1071         engine.instr[singletonField] = decInstr{*op, singletonField, indir, 0, ovfl}
1072         engine.numInstr = 1
1073         return
1074 }
1075
1076 // compileIgnoreSingle compiles the decoder engine for a non-struct top-level value that will be discarded.
1077 func (dec *Decoder) compileIgnoreSingle(remoteId typeId) (engine *decEngine, err os.Error) {
1078         engine = new(decEngine)
1079         engine.instr = make([]decInstr, 1) // one item
1080         op := dec.decIgnoreOpFor(remoteId)
1081         ovfl := overflow(dec.typeString(remoteId))
1082         engine.instr[0] = decInstr{op, 0, 0, 0, ovfl}
1083         engine.numInstr = 1
1084         return
1085 }
1086
1087 // compileDec compiles the decoder engine for a value.  If the value is not a struct,
1088 // it calls out to compileSingle.
1089 func (dec *Decoder) compileDec(remoteId typeId, ut *userTypeInfo) (engine *decEngine, err os.Error) {
1090         rt := ut.base
1091         srt := rt
1092         if srt.Kind() != reflect.Struct ||
1093                 ut.isGobDecoder {
1094                 return dec.compileSingle(remoteId, ut)
1095         }
1096         var wireStruct *structType
1097         // Builtin types can come from global pool; the rest must be defined by the decoder.
1098         // Also we know we're decoding a struct now, so the client must have sent one.
1099         if t, ok := builtinIdToType[remoteId]; ok {
1100                 wireStruct, _ = t.(*structType)
1101         } else {
1102                 wire := dec.wireType[remoteId]
1103                 if wire == nil {
1104                         error(errBadType)
1105                 }
1106                 wireStruct = wire.StructT
1107         }
1108         if wireStruct == nil {
1109                 errorf("type mismatch in decoder: want struct type %s; got non-struct", rt.String())
1110         }
1111         engine = new(decEngine)
1112         engine.instr = make([]decInstr, len(wireStruct.Field))
1113         seen := make(map[reflect.Type]*decOp)
1114         // Loop over the fields of the wire type.
1115         for fieldnum := 0; fieldnum < len(wireStruct.Field); fieldnum++ {
1116                 wireField := wireStruct.Field[fieldnum]
1117                 if wireField.Name == "" {
1118                         errorf("empty name for remote field of type %s", wireStruct.Name)
1119                 }
1120                 ovfl := overflow(wireField.Name)
1121                 // Find the field of the local type with the same name.
1122                 localField, present := srt.FieldByName(wireField.Name)
1123                 // TODO(r): anonymous names
1124                 if !present || !isExported(wireField.Name) {
1125                         op := dec.decIgnoreOpFor(wireField.Id)
1126                         engine.instr[fieldnum] = decInstr{op, fieldnum, 0, 0, ovfl}
1127                         continue
1128                 }
1129                 if !dec.compatibleType(localField.Type, wireField.Id, make(map[reflect.Type]typeId)) {
1130                         errorf("wrong type (%s) for received field %s.%s", localField.Type, wireStruct.Name, wireField.Name)
1131                 }
1132                 op, indir := dec.decOpFor(wireField.Id, localField.Type, localField.Name, seen)
1133                 engine.instr[fieldnum] = decInstr{*op, fieldnum, indir, uintptr(localField.Offset), ovfl}
1134                 engine.numInstr++
1135         }
1136         return
1137 }
1138
1139 // getDecEnginePtr returns the engine for the specified type.
1140 func (dec *Decoder) getDecEnginePtr(remoteId typeId, ut *userTypeInfo) (enginePtr **decEngine, err os.Error) {
1141         rt := ut.base
1142         decoderMap, ok := dec.decoderCache[rt]
1143         if !ok {
1144                 decoderMap = make(map[typeId]**decEngine)
1145                 dec.decoderCache[rt] = decoderMap
1146         }
1147         if enginePtr, ok = decoderMap[remoteId]; !ok {
1148                 // To handle recursive types, mark this engine as underway before compiling.
1149                 enginePtr = new(*decEngine)
1150                 decoderMap[remoteId] = enginePtr
1151                 *enginePtr, err = dec.compileDec(remoteId, ut)
1152                 if err != nil {
1153                         decoderMap[remoteId] = nil, false
1154                 }
1155         }
1156         return
1157 }
1158
1159 // emptyStruct is the type we compile into when ignoring a struct value.
1160 type emptyStruct struct{}
1161
1162 var emptyStructType = reflect.TypeOf(emptyStruct{})
1163
1164 // getDecEnginePtr returns the engine for the specified type when the value is to be discarded.
1165 func (dec *Decoder) getIgnoreEnginePtr(wireId typeId) (enginePtr **decEngine, err os.Error) {
1166         var ok bool
1167         if enginePtr, ok = dec.ignorerCache[wireId]; !ok {
1168                 // To handle recursive types, mark this engine as underway before compiling.
1169                 enginePtr = new(*decEngine)
1170                 dec.ignorerCache[wireId] = enginePtr
1171                 wire := dec.wireType[wireId]
1172                 if wire != nil && wire.StructT != nil {
1173                         *enginePtr, err = dec.compileDec(wireId, userType(emptyStructType))
1174                 } else {
1175                         *enginePtr, err = dec.compileIgnoreSingle(wireId)
1176                 }
1177                 if err != nil {
1178                         dec.ignorerCache[wireId] = nil, false
1179                 }
1180         }
1181         return
1182 }
1183
1184 // decodeValue decodes the data stream representing a value and stores it in val.
1185 func (dec *Decoder) decodeValue(wireId typeId, val reflect.Value) {
1186         defer catchError(&dec.err)
1187         // If the value is nil, it means we should just ignore this item.
1188         if !val.IsValid() {
1189                 dec.decodeIgnoredValue(wireId)
1190                 return
1191         }
1192         // Dereference down to the underlying struct type.
1193         ut := userType(val.Type())
1194         base := ut.base
1195         var enginePtr **decEngine
1196         enginePtr, dec.err = dec.getDecEnginePtr(wireId, ut)
1197         if dec.err != nil {
1198                 return
1199         }
1200         engine := *enginePtr
1201         if st := base; st.Kind() == reflect.Struct && !ut.isGobDecoder {
1202                 if engine.numInstr == 0 && st.NumField() > 0 && len(dec.wireType[wireId].StructT.Field) > 0 {
1203                         name := base.Name()
1204                         errorf("type mismatch: no fields matched compiling decoder for %s", name)
1205                 }
1206                 dec.decodeStruct(engine, ut, uintptr(unsafeAddr(val)), ut.indir)
1207         } else {
1208                 dec.decodeSingle(engine, ut, uintptr(unsafeAddr(val)))
1209         }
1210 }
1211
1212 // decodeIgnoredValue decodes the data stream representing a value of the specified type and discards it.
1213 func (dec *Decoder) decodeIgnoredValue(wireId typeId) {
1214         var enginePtr **decEngine
1215         enginePtr, dec.err = dec.getIgnoreEnginePtr(wireId)
1216         if dec.err != nil {
1217                 return
1218         }
1219         wire := dec.wireType[wireId]
1220         if wire != nil && wire.StructT != nil {
1221                 dec.ignoreStruct(*enginePtr)
1222         } else {
1223                 dec.ignoreSingle(*enginePtr)
1224         }
1225 }
1226
1227 func init() {
1228         var iop, uop decOp
1229         switch reflect.TypeOf(int(0)).Bits() {
1230         case 32:
1231                 iop = decInt32
1232                 uop = decUint32
1233         case 64:
1234                 iop = decInt64
1235                 uop = decUint64
1236         default:
1237                 panic("gob: unknown size of int/uint")
1238         }
1239         decOpTable[reflect.Int] = iop
1240         decOpTable[reflect.Uint] = uop
1241
1242         // Finally uintptr
1243         switch reflect.TypeOf(uintptr(0)).Bits() {
1244         case 32:
1245                 uop = decUint32
1246         case 64:
1247                 uop = decUint64
1248         default:
1249                 panic("gob: unknown size of uintptr")
1250         }
1251         decOpTable[reflect.Uintptr] = uop
1252 }
1253
1254 // Gob assumes it can call UnsafeAddr on any Value
1255 // in order to get a pointer it can copy data from.
1256 // Values that have just been created and do not point
1257 // into existing structs or slices cannot be addressed,
1258 // so simulate it by returning a pointer to a copy.
1259 // Each call allocates once.
1260 func unsafeAddr(v reflect.Value) uintptr {
1261         if v.CanAddr() {
1262                 return v.UnsafeAddr()
1263         }
1264         x := reflect.New(v.Type()).Elem()
1265         x.Set(v)
1266         return x.UnsafeAddr()
1267 }
1268
1269 // Gob depends on being able to take the address
1270 // of zeroed Values it creates, so use this wrapper instead
1271 // of the standard reflect.Zero.
1272 // Each call allocates once.
1273 func allocValue(t reflect.Type) reflect.Value {
1274         return reflect.New(t).Elem()
1275 }