...
Run Format

Source file src/runtime/type.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	// Runtime type representation.
     6	
     7	package runtime
     8	
     9	import "unsafe"
    10	
    11	// tflag is documented in reflect/type.go.
    12	//
    13	// tflag values must be kept in sync with copies in:
    14	//	cmd/compile/internal/gc/reflect.go
    15	//	cmd/link/internal/ld/decodesym.go
    16	//	reflect/type.go
    17	type tflag uint8
    18	
    19	const (
    20		tflagUncommon  tflag = 1 << 0
    21		tflagExtraStar tflag = 1 << 1
    22		tflagNamed     tflag = 1 << 2
    23	)
    24	
    25	// Needs to be in sync with ../cmd/compile/internal/ld/decodesym.go:/^func.commonsize,
    26	// ../cmd/compile/internal/gc/reflect.go:/^func.dcommontype and
    27	// ../reflect/type.go:/^type.rtype.
    28	type _type struct {
    29		size       uintptr
    30		ptrdata    uintptr // size of memory prefix holding all pointers
    31		hash       uint32
    32		tflag      tflag
    33		align      uint8
    34		fieldalign uint8
    35		kind       uint8
    36		alg        *typeAlg
    37		// gcdata stores the GC type data for the garbage collector.
    38		// If the KindGCProg bit is set in kind, gcdata is a GC program.
    39		// Otherwise it is a ptrmask bitmap. See mbitmap.go for details.
    40		gcdata    *byte
    41		str       nameOff
    42		ptrToThis typeOff
    43	}
    44	
    45	func (t *_type) string() string {
    46		s := t.nameOff(t.str).name()
    47		if t.tflag&tflagExtraStar != 0 {
    48			return s[1:]
    49		}
    50		return s
    51	}
    52	
    53	func (t *_type) uncommon() *uncommontype {
    54		if t.tflag&tflagUncommon == 0 {
    55			return nil
    56		}
    57		switch t.kind & kindMask {
    58		case kindStruct:
    59			type u struct {
    60				structtype
    61				u uncommontype
    62			}
    63			return &(*u)(unsafe.Pointer(t)).u
    64		case kindPtr:
    65			type u struct {
    66				ptrtype
    67				u uncommontype
    68			}
    69			return &(*u)(unsafe.Pointer(t)).u
    70		case kindFunc:
    71			type u struct {
    72				functype
    73				u uncommontype
    74			}
    75			return &(*u)(unsafe.Pointer(t)).u
    76		case kindSlice:
    77			type u struct {
    78				slicetype
    79				u uncommontype
    80			}
    81			return &(*u)(unsafe.Pointer(t)).u
    82		case kindArray:
    83			type u struct {
    84				arraytype
    85				u uncommontype
    86			}
    87			return &(*u)(unsafe.Pointer(t)).u
    88		case kindChan:
    89			type u struct {
    90				chantype
    91				u uncommontype
    92			}
    93			return &(*u)(unsafe.Pointer(t)).u
    94		case kindMap:
    95			type u struct {
    96				maptype
    97				u uncommontype
    98			}
    99			return &(*u)(unsafe.Pointer(t)).u
   100		case kindInterface:
   101			type u struct {
   102				interfacetype
   103				u uncommontype
   104			}
   105			return &(*u)(unsafe.Pointer(t)).u
   106		default:
   107			type u struct {
   108				_type
   109				u uncommontype
   110			}
   111			return &(*u)(unsafe.Pointer(t)).u
   112		}
   113	}
   114	
   115	func hasPrefix(s, prefix string) bool {
   116		return len(s) >= len(prefix) && s[:len(prefix)] == prefix
   117	}
   118	
   119	func (t *_type) name() string {
   120		if t.tflag&tflagNamed == 0 {
   121			return ""
   122		}
   123		s := t.string()
   124		i := len(s) - 1
   125		for i >= 0 {
   126			if s[i] == '.' {
   127				break
   128			}
   129			i--
   130		}
   131		return s[i+1:]
   132	}
   133	
   134	// reflectOffs holds type offsets defined at run time by the reflect package.
   135	//
   136	// When a type is defined at run time, its *rtype data lives on the heap.
   137	// There are a wide range of possible addresses the heap may use, that
   138	// may not be representable as a 32-bit offset. Moreover the GC may
   139	// one day start moving heap memory, in which case there is no stable
   140	// offset that can be defined.
   141	//
   142	// To provide stable offsets, we add pin *rtype objects in a global map
   143	// and treat the offset as an identifier. We use negative offsets that
   144	// do not overlap with any compile-time module offsets.
   145	//
   146	// Entries are created by reflect.addReflectOff.
   147	var reflectOffs struct {
   148		lock mutex
   149		next int32
   150		m    map[int32]unsafe.Pointer
   151		minv map[unsafe.Pointer]int32
   152	}
   153	
   154	func reflectOffsLock() {
   155		lock(&reflectOffs.lock)
   156		if raceenabled {
   157			raceacquire(unsafe.Pointer(&reflectOffs.lock))
   158		}
   159	}
   160	
   161	func reflectOffsUnlock() {
   162		if raceenabled {
   163			racerelease(unsafe.Pointer(&reflectOffs.lock))
   164		}
   165		unlock(&reflectOffs.lock)
   166	}
   167	
   168	func resolveNameOff(ptrInModule unsafe.Pointer, off nameOff) name {
   169		if off == 0 {
   170			return name{}
   171		}
   172		base := uintptr(ptrInModule)
   173		for md := &firstmoduledata; md != nil; md = md.next {
   174			if base >= md.types && base < md.etypes {
   175				res := md.types + uintptr(off)
   176				if res > md.etypes {
   177					println("runtime: nameOff", hex(off), "out of range", hex(md.types), "-", hex(md.etypes))
   178					throw("runtime: name offset out of range")
   179				}
   180				return name{(*byte)(unsafe.Pointer(res))}
   181			}
   182		}
   183	
   184		// No module found. see if it is a run time name.
   185		reflectOffsLock()
   186		res, found := reflectOffs.m[int32(off)]
   187		reflectOffsUnlock()
   188		if !found {
   189			println("runtime: nameOff", hex(off), "base", hex(base), "not in ranges:")
   190			for next := &firstmoduledata; next != nil; next = next.next {
   191				println("\ttypes", hex(next.types), "etypes", hex(next.etypes))
   192			}
   193			throw("runtime: name offset base pointer out of range")
   194		}
   195		return name{(*byte)(res)}
   196	}
   197	
   198	func (t *_type) nameOff(off nameOff) name {
   199		return resolveNameOff(unsafe.Pointer(t), off)
   200	}
   201	
   202	func (t *_type) typeOff(off typeOff) *_type {
   203		if off == 0 {
   204			return nil
   205		}
   206		base := uintptr(unsafe.Pointer(t))
   207		var md *moduledata
   208		for next := &firstmoduledata; next != nil; next = next.next {
   209			if base >= next.types && base < next.etypes {
   210				md = next
   211				break
   212			}
   213		}
   214		if md == nil {
   215			reflectOffsLock()
   216			res := reflectOffs.m[int32(off)]
   217			reflectOffsUnlock()
   218			if res == nil {
   219				println("runtime: typeOff", hex(off), "base", hex(base), "not in ranges:")
   220				for next := &firstmoduledata; next != nil; next = next.next {
   221					println("\ttypes", hex(next.types), "etypes", hex(next.etypes))
   222				}
   223				throw("runtime: type offset base pointer out of range")
   224			}
   225			return (*_type)(res)
   226		}
   227		if t := md.typemap[off]; t != nil {
   228			return t
   229		}
   230		res := md.types + uintptr(off)
   231		if res > md.etypes {
   232			println("runtime: typeOff", hex(off), "out of range", hex(md.types), "-", hex(md.etypes))
   233			throw("runtime: type offset out of range")
   234		}
   235		return (*_type)(unsafe.Pointer(res))
   236	}
   237	
   238	func (t *_type) textOff(off textOff) unsafe.Pointer {
   239		base := uintptr(unsafe.Pointer(t))
   240		var md *moduledata
   241		for next := &firstmoduledata; next != nil; next = next.next {
   242			if base >= next.types && base < next.etypes {
   243				md = next
   244				break
   245			}
   246		}
   247		if md == nil {
   248			reflectOffsLock()
   249			res := reflectOffs.m[int32(off)]
   250			reflectOffsUnlock()
   251			if res == nil {
   252				println("runtime: textOff", hex(off), "base", hex(base), "not in ranges:")
   253				for next := &firstmoduledata; next != nil; next = next.next {
   254					println("\ttypes", hex(next.types), "etypes", hex(next.etypes))
   255				}
   256				throw("runtime: text offset base pointer out of range")
   257			}
   258			return res
   259		}
   260		res := md.text + uintptr(off)
   261		if res > md.etext {
   262			println("runtime: textOff", hex(off), "out of range", hex(md.text), "-", hex(md.etext))
   263			throw("runtime: text offset out of range")
   264		}
   265		return unsafe.Pointer(res)
   266	}
   267	
   268	func (t *functype) in() []*_type {
   269		// See funcType in reflect/type.go for details on data layout.
   270		uadd := uintptr(unsafe.Sizeof(functype{}))
   271		if t.typ.tflag&tflagUncommon != 0 {
   272			uadd += unsafe.Sizeof(uncommontype{})
   273		}
   274		return (*[1 << 20]*_type)(add(unsafe.Pointer(t), uadd))[:t.inCount]
   275	}
   276	
   277	func (t *functype) out() []*_type {
   278		// See funcType in reflect/type.go for details on data layout.
   279		uadd := uintptr(unsafe.Sizeof(functype{}))
   280		if t.typ.tflag&tflagUncommon != 0 {
   281			uadd += unsafe.Sizeof(uncommontype{})
   282		}
   283		outCount := t.outCount & (1<<15 - 1)
   284		return (*[1 << 20]*_type)(add(unsafe.Pointer(t), uadd))[t.inCount : t.inCount+outCount]
   285	}
   286	
   287	func (t *functype) dotdotdot() bool {
   288		return t.outCount&(1<<15) != 0
   289	}
   290	
   291	type nameOff int32
   292	type typeOff int32
   293	type textOff int32
   294	
   295	type method struct {
   296		name nameOff
   297		mtyp typeOff
   298		ifn  textOff
   299		tfn  textOff
   300	}
   301	
   302	type uncommontype struct {
   303		pkgpath nameOff
   304		mcount  uint16 // number of methods
   305		_       uint16 // unused
   306		moff    uint32 // offset from this uncommontype to [mcount]method
   307		_       uint32 // unused
   308	}
   309	
   310	type imethod struct {
   311		name nameOff
   312		ityp typeOff
   313	}
   314	
   315	type interfacetype struct {
   316		typ     _type
   317		pkgpath name
   318		mhdr    []imethod
   319	}
   320	
   321	type maptype struct {
   322		typ           _type
   323		key           *_type
   324		elem          *_type
   325		bucket        *_type // internal type representing a hash bucket
   326		hmap          *_type // internal type representing a hmap
   327		keysize       uint8  // size of key slot
   328		indirectkey   bool   // store ptr to key instead of key itself
   329		valuesize     uint8  // size of value slot
   330		indirectvalue bool   // store ptr to value instead of value itself
   331		bucketsize    uint16 // size of bucket
   332		reflexivekey  bool   // true if k==k for all keys
   333		needkeyupdate bool   // true if we need to update key on an overwrite
   334	}
   335	
   336	type arraytype struct {
   337		typ   _type
   338		elem  *_type
   339		slice *_type
   340		len   uintptr
   341	}
   342	
   343	type chantype struct {
   344		typ  _type
   345		elem *_type
   346		dir  uintptr
   347	}
   348	
   349	type slicetype struct {
   350		typ  _type
   351		elem *_type
   352	}
   353	
   354	type functype struct {
   355		typ      _type
   356		inCount  uint16
   357		outCount uint16
   358	}
   359	
   360	type ptrtype struct {
   361		typ  _type
   362		elem *_type
   363	}
   364	
   365	type structfield struct {
   366		name   name
   367		typ    *_type
   368		offset uintptr
   369	}
   370	
   371	type structtype struct {
   372		typ     _type
   373		pkgPath name
   374		fields  []structfield
   375	}
   376	
   377	// name is an encoded type name with optional extra data.
   378	// See reflect/type.go for details.
   379	type name struct {
   380		bytes *byte
   381	}
   382	
   383	func (n name) data(off int) *byte {
   384		return (*byte)(add(unsafe.Pointer(n.bytes), uintptr(off)))
   385	}
   386	
   387	func (n name) isExported() bool {
   388		return (*n.bytes)&(1<<0) != 0
   389	}
   390	
   391	func (n name) nameLen() int {
   392		return int(uint16(*n.data(1))<<8 | uint16(*n.data(2)))
   393	}
   394	
   395	func (n name) tagLen() int {
   396		if *n.data(0)&(1<<1) == 0 {
   397			return 0
   398		}
   399		off := 3 + n.nameLen()
   400		return int(uint16(*n.data(off))<<8 | uint16(*n.data(off + 1)))
   401	}
   402	
   403	func (n name) name() (s string) {
   404		if n.bytes == nil {
   405			return ""
   406		}
   407		nl := n.nameLen()
   408		if nl == 0 {
   409			return ""
   410		}
   411		hdr := (*stringStruct)(unsafe.Pointer(&s))
   412		hdr.str = unsafe.Pointer(n.data(3))
   413		hdr.len = nl
   414		return s
   415	}
   416	
   417	func (n name) tag() (s string) {
   418		tl := n.tagLen()
   419		if tl == 0 {
   420			return ""
   421		}
   422		nl := n.nameLen()
   423		hdr := (*stringStruct)(unsafe.Pointer(&s))
   424		hdr.str = unsafe.Pointer(n.data(3 + nl + 2))
   425		hdr.len = tl
   426		return s
   427	}
   428	
   429	func (n name) pkgPath() string {
   430		if n.bytes == nil || *n.data(0)&(1<<2) == 0 {
   431			return ""
   432		}
   433		off := 3 + n.nameLen()
   434		if tl := n.tagLen(); tl > 0 {
   435			off += 2 + tl
   436		}
   437		var nameOff nameOff
   438		copy((*[4]byte)(unsafe.Pointer(&nameOff))[:], (*[4]byte)(unsafe.Pointer(n.data(off)))[:])
   439		pkgPathName := resolveNameOff(unsafe.Pointer(n.bytes), nameOff)
   440		return pkgPathName.name()
   441	}
   442	
   443	// typelinksinit scans the types from extra modules and builds the
   444	// moduledata typemap used to de-duplicate type pointers.
   445	func typelinksinit() {
   446		if firstmoduledata.next == nil {
   447			return
   448		}
   449		typehash := make(map[uint32][]*_type)
   450	
   451		modules := []*moduledata{}
   452		for md := &firstmoduledata; md != nil; md = md.next {
   453			modules = append(modules, md)
   454		}
   455		prev, modules := modules[len(modules)-1], modules[:len(modules)-1]
   456		for len(modules) > 0 {
   457			// Collect types from the previous module into typehash.
   458		collect:
   459			for _, tl := range prev.typelinks {
   460				var t *_type
   461				if prev.typemap == nil {
   462					t = (*_type)(unsafe.Pointer(prev.types + uintptr(tl)))
   463				} else {
   464					t = prev.typemap[typeOff(tl)]
   465				}
   466				// Add to typehash if not seen before.
   467				tlist := typehash[t.hash]
   468				for _, tcur := range tlist {
   469					if tcur == t {
   470						continue collect
   471					}
   472				}
   473				typehash[t.hash] = append(tlist, t)
   474			}
   475	
   476			// If any of this module's typelinks match a type from a
   477			// prior module, prefer that prior type by adding the offset
   478			// to this module's typemap.
   479			md := modules[len(modules)-1]
   480			md.typemap = make(map[typeOff]*_type, len(md.typelinks))
   481			for _, tl := range md.typelinks {
   482				t := (*_type)(unsafe.Pointer(md.types + uintptr(tl)))
   483				for _, candidate := range typehash[t.hash] {
   484					if typesEqual(t, candidate) {
   485						t = candidate
   486						break
   487					}
   488				}
   489				md.typemap[typeOff(tl)] = t
   490			}
   491	
   492			prev, modules = md, modules[:len(modules)-1]
   493		}
   494	}
   495	
   496	// typesEqual reports whether two types are equal.
   497	//
   498	// Everywhere in the runtime and reflect packages, it is assumed that
   499	// there is exactly one *_type per Go type, so that pointer equality
   500	// can be used to test if types are equal. There is one place that
   501	// breaks this assumption: buildmode=shared. In this case a type can
   502	// appear as two different pieces of memory. This is hidden from the
   503	// runtime and reflect package by the per-module typemap built in
   504	// typelinksinit. It uses typesEqual to map types from later modules
   505	// back into earlier ones.
   506	//
   507	// Only typelinksinit needs this function.
   508	func typesEqual(t, v *_type) bool {
   509		if t == v {
   510			return true
   511		}
   512		kind := t.kind & kindMask
   513		if kind != v.kind&kindMask {
   514			return false
   515		}
   516		if t.string() != v.string() {
   517			return false
   518		}
   519		ut := t.uncommon()
   520		uv := v.uncommon()
   521		if ut != nil || uv != nil {
   522			if ut == nil || uv == nil {
   523				return false
   524			}
   525			pkgpatht := t.nameOff(ut.pkgpath).name()
   526			pkgpathv := v.nameOff(uv.pkgpath).name()
   527			if pkgpatht != pkgpathv {
   528				return false
   529			}
   530		}
   531		if kindBool <= kind && kind <= kindComplex128 {
   532			return true
   533		}
   534		switch kind {
   535		case kindString, kindUnsafePointer:
   536			return true
   537		case kindArray:
   538			at := (*arraytype)(unsafe.Pointer(t))
   539			av := (*arraytype)(unsafe.Pointer(v))
   540			return typesEqual(at.elem, av.elem) && at.len == av.len
   541		case kindChan:
   542			ct := (*chantype)(unsafe.Pointer(t))
   543			cv := (*chantype)(unsafe.Pointer(v))
   544			return ct.dir == cv.dir && typesEqual(ct.elem, cv.elem)
   545		case kindFunc:
   546			ft := (*functype)(unsafe.Pointer(t))
   547			fv := (*functype)(unsafe.Pointer(v))
   548			if ft.outCount != fv.outCount || ft.inCount != fv.inCount {
   549				return false
   550			}
   551			tin, vin := ft.in(), fv.in()
   552			for i := 0; i < len(tin); i++ {
   553				if !typesEqual(tin[i], vin[i]) {
   554					return false
   555				}
   556			}
   557			tout, vout := ft.out(), fv.out()
   558			for i := 0; i < len(tout); i++ {
   559				if !typesEqual(tout[i], vout[i]) {
   560					return false
   561				}
   562			}
   563			return true
   564		case kindInterface:
   565			it := (*interfacetype)(unsafe.Pointer(t))
   566			iv := (*interfacetype)(unsafe.Pointer(v))
   567			if it.pkgpath.name() != iv.pkgpath.name() {
   568				return false
   569			}
   570			if len(it.mhdr) != len(iv.mhdr) {
   571				return false
   572			}
   573			for i := range it.mhdr {
   574				tm := &it.mhdr[i]
   575				vm := &iv.mhdr[i]
   576				tname := it.typ.nameOff(tm.name)
   577				vname := iv.typ.nameOff(vm.name)
   578				if tname.name() != vname.name() {
   579					return false
   580				}
   581				if tname.pkgPath() != vname.pkgPath() {
   582					return false
   583				}
   584				if !typesEqual(it.typ.typeOff(tm.ityp), iv.typ.typeOff(vm.ityp)) {
   585					return false
   586				}
   587			}
   588			return true
   589		case kindMap:
   590			mt := (*maptype)(unsafe.Pointer(t))
   591			mv := (*maptype)(unsafe.Pointer(v))
   592			return typesEqual(mt.key, mv.key) && typesEqual(mt.elem, mv.elem)
   593		case kindPtr:
   594			pt := (*ptrtype)(unsafe.Pointer(t))
   595			pv := (*ptrtype)(unsafe.Pointer(v))
   596			return typesEqual(pt.elem, pv.elem)
   597		case kindSlice:
   598			st := (*slicetype)(unsafe.Pointer(t))
   599			sv := (*slicetype)(unsafe.Pointer(v))
   600			return typesEqual(st.elem, sv.elem)
   601		case kindStruct:
   602			st := (*structtype)(unsafe.Pointer(t))
   603			sv := (*structtype)(unsafe.Pointer(v))
   604			if len(st.fields) != len(sv.fields) {
   605				return false
   606			}
   607			for i := range st.fields {
   608				tf := &st.fields[i]
   609				vf := &sv.fields[i]
   610				if tf.name.name() != vf.name.name() {
   611					return false
   612				}
   613				if tf.name.pkgPath() != vf.name.pkgPath() {
   614					return false
   615				}
   616				if !typesEqual(tf.typ, vf.typ) {
   617					return false
   618				}
   619				if tf.name.tag() != vf.name.tag() {
   620					return false
   621				}
   622				if tf.offset != vf.offset {
   623					return false
   624				}
   625			}
   626			return true
   627		default:
   628			println("runtime: impossible type kind", kind)
   629			throw("runtime: impossible type kind")
   630			return false
   631		}
   632	}
   633	

View as plain text