Update to current Go library.

[official-gcc.git] / libgo / go / gob / type.go

// Copyright 2009 The Go 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 gob

import (
        "fmt"
        "os"
        "reflect"
        "sync"
        "unicode"
        "utf8"
)

// userTypeInfo stores the information associated with a type the user has handed
// to the package.  It's computed once and stored in a map keyed by reflection
// type.
type userTypeInfo struct {
        user         reflect.Type // the type the user handed us
        base         reflect.Type // the base type after all indirections
        indir        int          // number of indirections to reach the base type
        isGobEncoder bool         // does the type implement GobEncoder?
        isGobDecoder bool         // does the type implement GobDecoder?
        encIndir     int8         // number of indirections to reach the receiver type; may be negative
        decIndir     int8         // number of indirections to reach the receiver type; may be negative
}

var (
        // Protected by an RWMutex because we read it a lot and write
        // it only when we see a new type, typically when compiling.
        userTypeLock  sync.RWMutex
        userTypeCache = make(map[reflect.Type]*userTypeInfo)
)

// validType returns, and saves, the information associated with user-provided type rt.
// If the user type is not valid, err will be non-nil.  To be used when the error handler
// is not set up.
func validUserType(rt reflect.Type) (ut *userTypeInfo, err os.Error) {
        userTypeLock.RLock()
        ut = userTypeCache[rt]
        userTypeLock.RUnlock()
        if ut != nil {
                return
        }
        // Now set the value under the write lock.
        userTypeLock.Lock()
        defer userTypeLock.Unlock()
        if ut = userTypeCache[rt]; ut != nil {
                // Lost the race; not a problem.
                return
        }
        ut = new(userTypeInfo)
        ut.base = rt
        ut.user = rt
        // A type that is just a cycle of pointers (such as type T *T) cannot
        // be represented in gobs, which need some concrete data.  We use a
        // cycle detection algorithm from Knuth, Vol 2, Section 3.1, Ex 6,
        // pp 539-540.  As we step through indirections, run another type at
        // half speed. If they meet up, there's a cycle.
        slowpoke := ut.base // walks half as fast as ut.base
        for {
                pt, ok := ut.base.(*reflect.PtrType)
                if !ok {
                        break
                }
                ut.base = pt.Elem()
                if ut.base == slowpoke { // ut.base lapped slowpoke
                        // recursive pointer type.
                        return nil, os.ErrorString("can't represent recursive pointer type " + ut.base.String())
                }
                if ut.indir%2 == 0 {
                        slowpoke = slowpoke.(*reflect.PtrType).Elem()
                }
                ut.indir++
        }
        ut.isGobEncoder, ut.encIndir = implementsInterface(ut.user, gobEncoderCheck)
        ut.isGobDecoder, ut.decIndir = implementsInterface(ut.user, gobDecoderCheck)
        userTypeCache[rt] = ut
        return
}

const (
        gobEncodeMethodName = "GobEncode"
        gobDecodeMethodName = "GobDecode"
)

// implements returns whether the type implements the interface, as encoded
// in the check function.
func implements(typ reflect.Type, check func(typ reflect.Type) bool) bool {
        if typ.NumMethod() == 0 { // avoid allocations etc. unless there's some chance
                return false
        }
        return check(typ)
}

// gobEncoderCheck makes the type assertion a boolean function.
func gobEncoderCheck(typ reflect.Type) bool {
        _, ok := reflect.MakeZero(typ).Interface().(GobEncoder)
        return ok
}

// gobDecoderCheck makes the type assertion a boolean function.
func gobDecoderCheck(typ reflect.Type) bool {
        _, ok := reflect.MakeZero(typ).Interface().(GobDecoder)
        return ok
}

// implementsInterface reports whether the type implements the
// interface. (The actual check is done through the provided function.)
// It also returns the number of indirections required to get to the
// implementation.
func implementsInterface(typ reflect.Type, check func(typ reflect.Type) bool) (success bool, indir int8) {
        if typ == nil {
                return
        }
        rt := typ
        // The type might be a pointer and we need to keep
        // dereferencing to the base type until we find an implementation.
        for {
                if implements(rt, check) {
                        return true, indir
                }
                if p, ok := rt.(*reflect.PtrType); ok {
                        indir++
                        if indir > 100 { // insane number of indirections
                                return false, 0
                        }
                        rt = p.Elem()
                        continue
                }
                break
        }
        // No luck yet, but if this is a base type (non-pointer), the pointer might satisfy.
        if _, ok := typ.(*reflect.PtrType); !ok {
                // Not a pointer, but does the pointer work?
                if implements(reflect.PtrTo(typ), check) {
                        return true, -1
                }
        }
        return false, 0
}

// userType returns, and saves, the information associated with user-provided type rt.
// If the user type is not valid, it calls error.
func userType(rt reflect.Type) *userTypeInfo {
        ut, err := validUserType(rt)
        if err != nil {
                error(err)
        }
        return ut
}
// A typeId represents a gob Type as an integer that can be passed on the wire.
// Internally, typeIds are used as keys to a map to recover the underlying type info.
type typeId int32

var nextId typeId       // incremented for each new type we build
var typeLock sync.Mutex // set while building a type
const firstUserId = 64  // lowest id number granted to user

type gobType interface {
        id() typeId
        setId(id typeId)
        name() string
        string() string // not public; only for debugging
        safeString(seen map[typeId]bool) string
}

var types = make(map[reflect.Type]gobType)
var idToType = make(map[typeId]gobType)
var builtinIdToType map[typeId]gobType // set in init() after builtins are established

func setTypeId(typ gobType) {
        nextId++
        typ.setId(nextId)
        idToType[nextId] = typ
}

func (t typeId) gobType() gobType {
        if t == 0 {
                return nil
        }
        return idToType[t]
}

// string returns the string representation of the type associated with the typeId.
func (t typeId) string() string {
        if t.gobType() == nil {
                return "<nil>"
        }
        return t.gobType().string()
}

// Name returns the name of the type associated with the typeId.
func (t typeId) name() string {
        if t.gobType() == nil {
                return "<nil>"
        }
        return t.gobType().name()
}

// Common elements of all types.
type CommonType struct {
        Name string
        Id   typeId
}

func (t *CommonType) id() typeId { return t.Id }

func (t *CommonType) setId(id typeId) { t.Id = id }

func (t *CommonType) string() string { return t.Name }

func (t *CommonType) safeString(seen map[typeId]bool) string {
        return t.Name
}

func (t *CommonType) name() string { return t.Name }

// Create and check predefined types
// The string for tBytes is "bytes" not "[]byte" to signify its specialness.

var (
        // Primordial types, needed during initialization.
        // Always passed as pointers so the interface{} type
        // goes through without losing its interfaceness.
        tBool      = bootstrapType("bool", (*bool)(nil), 1)
        tInt       = bootstrapType("int", (*int)(nil), 2)
        tUint      = bootstrapType("uint", (*uint)(nil), 3)
        tFloat     = bootstrapType("float", (*float64)(nil), 4)
        tBytes     = bootstrapType("bytes", (*[]byte)(nil), 5)
        tString    = bootstrapType("string", (*string)(nil), 6)
        tComplex   = bootstrapType("complex", (*complex128)(nil), 7)
        tInterface = bootstrapType("interface", (*interface{})(nil), 8)
        // Reserve some Ids for compatible expansion
        tReserved7 = bootstrapType("_reserved1", (*struct{ r7 int })(nil), 9)
        tReserved6 = bootstrapType("_reserved1", (*struct{ r6 int })(nil), 10)
        tReserved5 = bootstrapType("_reserved1", (*struct{ r5 int })(nil), 11)
        tReserved4 = bootstrapType("_reserved1", (*struct{ r4 int })(nil), 12)
        tReserved3 = bootstrapType("_reserved1", (*struct{ r3 int })(nil), 13)
        tReserved2 = bootstrapType("_reserved1", (*struct{ r2 int })(nil), 14)
        tReserved1 = bootstrapType("_reserved1", (*struct{ r1 int })(nil), 15)
)

// Predefined because it's needed by the Decoder
var tWireType = mustGetTypeInfo(reflect.Typeof(wireType{})).id
var wireTypeUserInfo *userTypeInfo // userTypeInfo of (*wireType)

func init() {
        // Some magic numbers to make sure there are no surprises.
        checkId(16, tWireType)
        checkId(17, mustGetTypeInfo(reflect.Typeof(arrayType{})).id)
        checkId(18, mustGetTypeInfo(reflect.Typeof(CommonType{})).id)
        checkId(19, mustGetTypeInfo(reflect.Typeof(sliceType{})).id)
        checkId(20, mustGetTypeInfo(reflect.Typeof(structType{})).id)
        checkId(21, mustGetTypeInfo(reflect.Typeof(fieldType{})).id)
        checkId(23, mustGetTypeInfo(reflect.Typeof(mapType{})).id)

        builtinIdToType = make(map[typeId]gobType)
        for k, v := range idToType {
                builtinIdToType[k] = v
        }

        // Move the id space upwards to allow for growth in the predefined world
        // without breaking existing files.
        if nextId > firstUserId {
                panic(fmt.Sprintln("nextId too large:", nextId))
        }
        nextId = firstUserId
        registerBasics()
        wireTypeUserInfo = userType(reflect.Typeof((*wireType)(nil)))
}

// Array type
type arrayType struct {
        CommonType
        Elem typeId
        Len  int
}

func newArrayType(name string) *arrayType {
        a := &arrayType{CommonType{Name: name}, 0, 0}
        return a
}

func (a *arrayType) init(elem gobType, len int) {
        // Set our type id before evaluating the element's, in case it's our own.
        setTypeId(a)
        a.Elem = elem.id()
        a.Len = len
}

func (a *arrayType) safeString(seen map[typeId]bool) string {
        if seen[a.Id] {
                return a.Name
        }
        seen[a.Id] = true
        return fmt.Sprintf("[%d]%s", a.Len, a.Elem.gobType().safeString(seen))
}

func (a *arrayType) string() string { return a.safeString(make(map[typeId]bool)) }

// GobEncoder type (something that implements the GobEncoder interface)
type gobEncoderType struct {
        CommonType
}

func newGobEncoderType(name string) *gobEncoderType {
        g := &gobEncoderType{CommonType{Name: name}}
        setTypeId(g)
        return g
}

func (g *gobEncoderType) safeString(seen map[typeId]bool) string {
        return g.Name
}

func (g *gobEncoderType) string() string { return g.Name }

// Map type
type mapType struct {
        CommonType
        Key  typeId
        Elem typeId
}

func newMapType(name string) *mapType {
        m := &mapType{CommonType{Name: name}, 0, 0}
        return m
}

func (m *mapType) init(key, elem gobType) {
        // Set our type id before evaluating the element's, in case it's our own.
        setTypeId(m)
        m.Key = key.id()
        m.Elem = elem.id()
}

func (m *mapType) safeString(seen map[typeId]bool) string {
        if seen[m.Id] {
                return m.Name
        }
        seen[m.Id] = true
        key := m.Key.gobType().safeString(seen)
        elem := m.Elem.gobType().safeString(seen)
        return fmt.Sprintf("map[%s]%s", key, elem)
}

func (m *mapType) string() string { return m.safeString(make(map[typeId]bool)) }

// Slice type
type sliceType struct {
        CommonType
        Elem typeId
}

func newSliceType(name string) *sliceType {
        s := &sliceType{CommonType{Name: name}, 0}
        return s
}

func (s *sliceType) init(elem gobType) {
        // Set our type id before evaluating the element's, in case it's our own.
        setTypeId(s)
        s.Elem = elem.id()
}

func (s *sliceType) safeString(seen map[typeId]bool) string {
        if seen[s.Id] {
                return s.Name
        }
        seen[s.Id] = true
        return fmt.Sprintf("[]%s", s.Elem.gobType().safeString(seen))
}

func (s *sliceType) string() string { return s.safeString(make(map[typeId]bool)) }

// Struct type
type fieldType struct {
        Name string
        Id   typeId
}

type structType struct {
        CommonType
        Field []*fieldType
}

func (s *structType) safeString(seen map[typeId]bool) string {
        if s == nil {
                return "<nil>"
        }
        if _, ok := seen[s.Id]; ok {
                return s.Name
        }
        seen[s.Id] = true
        str := s.Name + " = struct { "
        for _, f := range s.Field {
                str += fmt.Sprintf("%s %s; ", f.Name, f.Id.gobType().safeString(seen))
        }
        str += "}"
        return str
}

func (s *structType) string() string { return s.safeString(make(map[typeId]bool)) }

func newStructType(name string) *structType {
        s := &structType{CommonType{Name: name}, nil}
        // For historical reasons we set the id here rather than init.
        // See the comment in newTypeObject for details.
        setTypeId(s)
        return s
}

// newTypeObject allocates a gobType for the reflection type rt.
// Unless ut represents a GobEncoder, rt should be the base type
// of ut.
// This is only called from the encoding side. The decoding side
// works through typeIds and userTypeInfos alone.
func newTypeObject(name string, ut *userTypeInfo, rt reflect.Type) (gobType, os.Error) {
        // Does this type implement GobEncoder?
        if ut.isGobEncoder {
                return newGobEncoderType(name), nil
        }
        var err os.Error
        var type0, type1 gobType
        defer func() {
                if err != nil {
                        types[rt] = nil, false
                }
        }()
        // Install the top-level type before the subtypes (e.g. struct before
        // fields) so recursive types can be constructed safely.
        switch t := rt.(type) {
        // All basic types are easy: they are predefined.
        case *reflect.BoolType:
                return tBool.gobType(), nil

        case *reflect.IntType:
                return tInt.gobType(), nil

        case *reflect.UintType:
                return tUint.gobType(), nil

        case *reflect.FloatType:
                return tFloat.gobType(), nil

        case *reflect.ComplexType:
                return tComplex.gobType(), nil

        case *reflect.StringType:
                return tString.gobType(), nil

        case *reflect.InterfaceType:
                return tInterface.gobType(), nil

        case *reflect.ArrayType:
                at := newArrayType(name)
                types[rt] = at
                type0, err = getBaseType("", t.Elem())
                if err != nil {
                        return nil, err
                }
                // Historical aside:
                // For arrays, maps, and slices, we set the type id after the elements
                // are constructed. This is to retain the order of type id allocation after
                // a fix made to handle recursive types, which changed the order in
                // which types are built.  Delaying the setting in this way preserves
                // type ids while allowing recursive types to be described. Structs,
                // done below, were already handling recursion correctly so they
                // assign the top-level id before those of the field.
                at.init(type0, t.Len())
                return at, nil

        case *reflect.MapType:
                mt := newMapType(name)
                types[rt] = mt
                type0, err = getBaseType("", t.Key())
                if err != nil {
                        return nil, err
                }
                type1, err = getBaseType("", t.Elem())
                if err != nil {
                        return nil, err
                }
                mt.init(type0, type1)
                return mt, nil

        case *reflect.SliceType:
                // []byte == []uint8 is a special case
                if t.Elem().Kind() == reflect.Uint8 {
                        return tBytes.gobType(), nil
                }
                st := newSliceType(name)
                types[rt] = st
                type0, err = getBaseType(t.Elem().Name(), t.Elem())
                if err != nil {
                        return nil, err
                }
                st.init(type0)
                return st, nil

        case *reflect.StructType:
                st := newStructType(name)
                types[rt] = st
                idToType[st.id()] = st
                for i := 0; i < t.NumField(); i++ {
                        f := t.Field(i)
                        if !isExported(f.Name) {
                                continue
                        }
                        typ := userType(f.Type).base
                        tname := typ.Name()
                        if tname == "" {
                                t := userType(f.Type).base
                                tname = t.String()
                        }
                        gt, err := getBaseType(tname, f.Type)
                        if err != nil {
                                return nil, err
                        }
                        st.Field = append(st.Field, &fieldType{f.Name, gt.id()})
                }
                return st, nil

        default:
                return nil, os.ErrorString("gob NewTypeObject can't handle type: " + rt.String())
        }
        return nil, nil
}

// isExported reports whether this is an exported - upper case - name.
func isExported(name string) bool {
        rune, _ := utf8.DecodeRuneInString(name)
        return unicode.IsUpper(rune)
}

// getBaseType returns the Gob type describing the given reflect.Type's base type.
// typeLock must be held.
func getBaseType(name string, rt reflect.Type) (gobType, os.Error) {
        ut := userType(rt)
        return getType(name, ut, ut.base)
}

// getType returns the Gob type describing the given reflect.Type.
// Should be called only when handling GobEncoders/Decoders,
// which may be pointers.  All other types are handled through the
// base type, never a pointer.
// typeLock must be held.
func getType(name string, ut *userTypeInfo, rt reflect.Type) (gobType, os.Error) {
        typ, present := types[rt]
        if present {
                return typ, nil
        }
        typ, err := newTypeObject(name, ut, rt)
        if err == nil {
                types[rt] = typ
        }
        return typ, err
}

func checkId(want, got typeId) {
        if want != got {
                fmt.Fprintf(os.Stderr, "checkId: %d should be %d\n", int(got), int(want))
                panic("bootstrap type wrong id: " + got.name() + " " + got.string() + " not " + want.string())
        }
}

// used for building the basic types; called only from init().  the incoming
// interface always refers to a pointer.
func bootstrapType(name string, e interface{}, expect typeId) typeId {
        rt := reflect.Typeof(e).(*reflect.PtrType).Elem()
        _, present := types[rt]
        if present {
                panic("bootstrap type already present: " + name + ", " + rt.String())
        }
        typ := &CommonType{Name: name}
        types[rt] = typ
        setTypeId(typ)
        checkId(expect, nextId)
        userType(rt) // might as well cache it now
        return nextId
}

// Representation of the information we send and receive about this type.
// Each value we send is preceded by its type definition: an encoded int.
// However, the very first time we send the value, we first send the pair
// (-id, wireType).
// For bootstrapping purposes, we assume that the recipient knows how
// to decode a wireType; it is exactly the wireType struct here, interpreted
// using the gob rules for sending a structure, except that we assume the
// ids for wireType and structType etc. are known.  The relevant pieces
// are built in encode.go's init() function.
// To maintain binary compatibility, if you extend this type, always put
// the new fields last.
type wireType struct {
        ArrayT      *arrayType
        SliceT      *sliceType
        StructT     *structType
        MapT        *mapType
        GobEncoderT *gobEncoderType
}

func (w *wireType) string() string {
        const unknown = "unknown type"
        if w == nil {
                return unknown
        }
        switch {
        case w.ArrayT != nil:
                return w.ArrayT.Name
        case w.SliceT != nil:
                return w.SliceT.Name
        case w.StructT != nil:
                return w.StructT.Name
        case w.MapT != nil:
                return w.MapT.Name
        case w.GobEncoderT != nil:
                return w.GobEncoderT.Name
        }
        return unknown
}

type typeInfo struct {
        id      typeId
        encoder *encEngine
        wire    *wireType
}

var typeInfoMap = make(map[reflect.Type]*typeInfo) // protected by typeLock

// typeLock must be held.
func getTypeInfo(ut *userTypeInfo) (*typeInfo, os.Error) {
        rt := ut.base
        if ut.isGobEncoder {
                // We want the user type, not the base type.
                rt = ut.user
        }
        info, ok := typeInfoMap[rt]
        if ok {
                return info, nil
        }
        info = new(typeInfo)
        gt, err := getBaseType(rt.Name(), rt)
        if err != nil {
                return nil, err
        }
        info.id = gt.id()

        if ut.isGobEncoder {
                userType, err := getType(rt.Name(), ut, rt)
                if err != nil {
                        return nil, err
                }
                info.wire = &wireType{GobEncoderT: userType.id().gobType().(*gobEncoderType)}
                typeInfoMap[ut.user] = info
                return info, nil
        }

        t := info.id.gobType()
        switch typ := rt.(type) {
        case *reflect.ArrayType:
                info.wire = &wireType{ArrayT: t.(*arrayType)}
        case *reflect.MapType:
                info.wire = &wireType{MapT: t.(*mapType)}
        case *reflect.SliceType:
                // []byte == []uint8 is a special case handled separately
                if typ.Elem().Kind() != reflect.Uint8 {
                        info.wire = &wireType{SliceT: t.(*sliceType)}
                }
        case *reflect.StructType:
                info.wire = &wireType{StructT: t.(*structType)}
        }
        typeInfoMap[rt] = info
        return info, nil
}

// Called only when a panic is acceptable and unexpected.
func mustGetTypeInfo(rt reflect.Type) *typeInfo {
        t, err := getTypeInfo(userType(rt))
        if err != nil {
                panic("getTypeInfo: " + err.String())
        }
        return t
}

// GobEncoder is the interface describing data that provides its own
// representation for encoding values for transmission to a GobDecoder.
// A type that implements GobEncoder and GobDecoder has complete
// control over the representation of its data and may therefore
// contain things such as private fields, channels, and functions,
// which are not usually transmissable in gob streams.
//
// Note: Since gobs can be stored permanently, It is good design
// to guarantee the encoding used by a GobEncoder is stable as the
// software evolves.  For instance, it might make sense for GobEncode
// to include a version number in the encoding.
type GobEncoder interface {
        // GobEncode returns a byte slice representing the encoding of the
        // receiver for transmission to a GobDecoder, usually of the same
        // concrete type.
        GobEncode() ([]byte, os.Error)
}

// GobDecoder is the interface describing data that provides its own
// routine for decoding transmitted values sent by a GobEncoder.
type GobDecoder interface {
        // GobDecode overwrites the receiver, which must be a pointer,
        // with the value represented by the byte slice, which was written
        // by GobEncode, usually for the same concrete type.
        GobDecode([]byte) os.Error
}

var (
        nameToConcreteType = make(map[string]reflect.Type)
        concreteTypeToName = make(map[reflect.Type]string)
)

// RegisterName is like Register but uses the provided name rather than the
// type's default.
func RegisterName(name string, value interface{}) {
        if name == "" {
                // reserved for nil
                panic("attempt to register empty name")
        }
        base := userType(reflect.Typeof(value)).base
        // Check for incompatible duplicates.
        if t, ok := nameToConcreteType[name]; ok && t != base {
                panic("gob: registering duplicate types for " + name)
        }
        if n, ok := concreteTypeToName[base]; ok && n != name {
                panic("gob: registering duplicate names for " + base.String())
        }
        // Store the name and type provided by the user....
        nameToConcreteType[name] = reflect.Typeof(value)
        // but the flattened type in the type table, since that's what decode needs.
        concreteTypeToName[base] = name
}

// Register records a type, identified by a value for that type, under its
// internal type name.  That name will identify the concrete type of a value
// sent or received as an interface variable.  Only types that will be
// transferred as implementations of interface values need to be registered.
// Expecting to be used only during initialization, it panics if the mapping
// between types and names is not a bijection.
func Register(value interface{}) {
        // Default to printed representation for unnamed types
        rt := reflect.Typeof(value)
        name := rt.String()

        // But for named types (or pointers to them), qualify with import path.
        // Dereference one pointer looking for a named type.
        star := ""
        if rt.Name() == "" {
                if pt, ok := rt.(*reflect.PtrType); ok {
                        star = "*"
                        rt = pt
                }
        }
        if rt.Name() != "" {
                if rt.PkgPath() == "" {
                        name = star + rt.Name()
                } else {
                        name = star + rt.PkgPath() + "." + rt.Name()
                }
        }

        RegisterName(name, value)
}

func registerBasics() {
        Register(int(0))
        Register(int8(0))
        Register(int16(0))
        Register(int32(0))
        Register(int64(0))
        Register(uint(0))
        Register(uint8(0))
        Register(uint16(0))
        Register(uint32(0))
        Register(uint64(0))
        Register(float32(0))
        Register(float64(0))
        Register(complex64(0i))
        Register(complex128(0i))
        Register(false)
        Register("")
        Register([]byte(nil))
}