// 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 gc

import (
	"cmd/internal/gcprog"
	"cmd/internal/obj"
	"fmt"
	"os"
)

/*
 * runtime interface and reflection data structures
 */
var signatlist *NodeList

func sigcmp(a *Sig, b *Sig) int {
	i := stringsCompare(a.name, b.name)
	if i != 0 {
		return i
	}
	if a.pkg == b.pkg {
		return 0
	}
	if a.pkg == nil {
		return -1
	}
	if b.pkg == nil {
		return +1
	}
	return stringsCompare(a.pkg.Path, b.pkg.Path)
}

func lsort(l *Sig, f func(*Sig, *Sig) int) *Sig {
	if l == nil || l.link == nil {
		return l
	}

	l1 := l
	l2 := l
	for {
		l2 = l2.link
		if l2 == nil {
			break
		}
		l2 = l2.link
		if l2 == nil {
			break
		}
		l1 = l1.link
	}

	l2 = l1.link
	l1.link = nil
	l1 = lsort(l, f)
	l2 = lsort(l2, f)

	/* set up lead element */
	if f(l1, l2) < 0 {
		l = l1
		l1 = l1.link
	} else {
		l = l2
		l2 = l2.link
	}

	le := l

	for {
		if l1 == nil {
			for l2 != nil {
				le.link = l2
				le = l2
				l2 = l2.link
			}

			le.link = nil
			break
		}

		if l2 == nil {
			for l1 != nil {
				le.link = l1
				le = l1
				l1 = l1.link
			}

			break
		}

		if f(l1, l2) < 0 {
			le.link = l1
			le = l1
			l1 = l1.link
		} else {
			le.link = l2
			le = l2
			l2 = l2.link
		}
	}

	le.link = nil
	return l
}

// Builds a type representing a Bucket structure for
// the given map type.  This type is not visible to users -
// we include only enough information to generate a correct GC
// program for it.
// Make sure this stays in sync with ../../runtime/hashmap.go!
const (
	BUCKETSIZE = 8
	MAXKEYSIZE = 128
	MAXVALSIZE = 128
)

func makefield(name string, t *Type) *Type {
	f := typ(TFIELD)
	f.Type = t
	f.Sym = new(Sym)
	f.Sym.Name = name
	return f
}

func mapbucket(t *Type) *Type {
	if t.Bucket != nil {
		return t.Bucket
	}

	bucket := typ(TSTRUCT)
	keytype := t.Down
	valtype := t.Type
	dowidth(keytype)
	dowidth(valtype)
	if keytype.Width > MAXKEYSIZE {
		keytype = Ptrto(keytype)
	}
	if valtype.Width > MAXVALSIZE {
		valtype = Ptrto(valtype)
	}

	// The first field is: uint8 topbits[BUCKETSIZE].
	arr := typ(TARRAY)

	arr.Type = Types[TUINT8]
	arr.Bound = BUCKETSIZE
	field := make([]*Type, 0, 5)
	field = append(field, makefield("topbits", arr))
	arr = typ(TARRAY)
	arr.Type = keytype
	arr.Bound = BUCKETSIZE
	field = append(field, makefield("keys", arr))
	arr = typ(TARRAY)
	arr.Type = valtype
	arr.Bound = BUCKETSIZE
	field = append(field, makefield("values", arr))

	// Make sure the overflow pointer is the last memory in the struct,
	// because the runtime assumes it can use size-ptrSize as the
	// offset of the overflow pointer. We double-check that property
	// below once the offsets and size are computed.
	//
	// BUCKETSIZE is 8, so the struct is aligned to 64 bits to this point.
	// On 32-bit systems, the max alignment is 32-bit, and the
	// overflow pointer will add another 32-bit field, and the struct
	// will end with no padding.
	// On 64-bit systems, the max alignment is 64-bit, and the
	// overflow pointer will add another 64-bit field, and the struct
	// will end with no padding.
	// On nacl/amd64p32, however, the max alignment is 64-bit,
	// but the overflow pointer will add only a 32-bit field,
	// so if the struct needs 64-bit padding (because a key or value does)
	// then it would end with an extra 32-bit padding field.
	// Preempt that by emitting the padding here.
	if int(t.Type.Align) > Widthptr || int(t.Down.Align) > Widthptr {
		field = append(field, makefield("pad", Types[TUINTPTR]))
	}

	// If keys and values have no pointers, the map implementation
	// can keep a list of overflow pointers on the side so that
	// buckets can be marked as having no pointers.
	// Arrange for the bucket to have no pointers by changing
	// the type of the overflow field to uintptr in this case.
	// See comment on hmap.overflow in ../../../../runtime/hashmap.go.
	otyp := Ptrto(bucket)
	if !haspointers(t.Type) && !haspointers(t.Down) && t.Type.Width <= MAXKEYSIZE && t.Down.Width <= MAXVALSIZE {
		otyp = Types[TUINTPTR]
	}
	ovf := makefield("overflow", otyp)
	field = append(field, ovf)

	// link up fields
	bucket.Noalg = 1
	bucket.Local = t.Local
	bucket.Type = field[0]
	for n := int32(0); n < int32(len(field)-1); n++ {
		field[n].Down = field[n+1]
	}
	field[len(field)-1].Down = nil
	dowidth(bucket)

	// Double-check that overflow field is final memory in struct,
	// with no padding at end. See comment above.
	if ovf.Width != bucket.Width-int64(Widthptr) {
		Yyerror("bad math in mapbucket for %v", t)
	}

	t.Bucket = bucket

	bucket.Map = t
	return bucket
}

// Builds a type representing a Hmap structure for the given map type.
// Make sure this stays in sync with ../../runtime/hashmap.go!
func hmap(t *Type) *Type {
	if t.Hmap != nil {
		return t.Hmap
	}

	bucket := mapbucket(t)
	var field [8]*Type
	field[0] = makefield("count", Types[TINT])
	field[1] = makefield("flags", Types[TUINT8])
	field[2] = makefield("B", Types[TUINT8])
	field[3] = makefield("hash0", Types[TUINT32])
	field[4] = makefield("buckets", Ptrto(bucket))
	field[5] = makefield("oldbuckets", Ptrto(bucket))
	field[6] = makefield("nevacuate", Types[TUINTPTR])
	field[7] = makefield("overflow", Types[TUNSAFEPTR])

	h := typ(TSTRUCT)
	h.Noalg = 1
	h.Local = t.Local
	h.Type = field[0]
	for n := int32(0); n < int32(len(field)-1); n++ {
		field[n].Down = field[n+1]
	}
	field[len(field)-1].Down = nil
	dowidth(h)
	t.Hmap = h
	h.Map = t
	return h
}

func hiter(t *Type) *Type {
	if t.Hiter != nil {
		return t.Hiter
	}

	// build a struct:
	// hash_iter {
	//    key *Key
	//    val *Value
	//    t *MapType
	//    h *Hmap
	//    buckets *Bucket
	//    bptr *Bucket
	//    overflow0 unsafe.Pointer
	//    overflow1 unsafe.Pointer
	//    startBucket uintptr
	//    stuff uintptr
	//    bucket uintptr
	//    checkBucket uintptr
	// }
	// must match ../../runtime/hashmap.go:hash_iter.
	var field [12]*Type
	field[0] = makefield("key", Ptrto(t.Down))

	field[1] = makefield("val", Ptrto(t.Type))
	field[2] = makefield("t", Ptrto(Types[TUINT8]))
	field[3] = makefield("h", Ptrto(hmap(t)))
	field[4] = makefield("buckets", Ptrto(mapbucket(t)))
	field[5] = makefield("bptr", Ptrto(mapbucket(t)))
	field[6] = makefield("overflow0", Types[TUNSAFEPTR])
	field[7] = makefield("overflow1", Types[TUNSAFEPTR])
	field[8] = makefield("startBucket", Types[TUINTPTR])
	field[9] = makefield("stuff", Types[TUINTPTR]) // offset+wrapped+B+I
	field[10] = makefield("bucket", Types[TUINTPTR])
	field[11] = makefield("checkBucket", Types[TUINTPTR])

	// build iterator struct holding the above fields
	i := typ(TSTRUCT)

	i.Noalg = 1
	i.Type = field[0]
	for n := int32(0); n < int32(len(field)-1); n++ {
		field[n].Down = field[n+1]
	}
	field[len(field)-1].Down = nil
	dowidth(i)
	if i.Width != int64(12*Widthptr) {
		Yyerror("hash_iter size not correct %d %d", i.Width, 12*Widthptr)
	}
	t.Hiter = i
	i.Map = t
	return i
}

/*
 * f is method type, with receiver.
 * return function type, receiver as first argument (or not).
 */
func methodfunc(f *Type, receiver *Type) *Type {
	var in *NodeList
	if receiver != nil {
		d := Nod(ODCLFIELD, nil, nil)
		d.Type = receiver
		in = list(in, d)
	}

	var d *Node
	for t := getinargx(f).Type; t != nil; t = t.Down {
		d = Nod(ODCLFIELD, nil, nil)
		d.Type = t.Type
		d.Isddd = t.Isddd
		in = list(in, d)
	}

	var out *NodeList
	for t := getoutargx(f).Type; t != nil; t = t.Down {
		d = Nod(ODCLFIELD, nil, nil)
		d.Type = t.Type
		out = list(out, d)
	}

	t := functype(nil, in, out)
	if f.Nname != nil {
		// Link to name of original method function.
		t.Nname = f.Nname
	}

	return t
}

/*
 * return methods of non-interface type t, sorted by name.
 * generates stub functions as needed.
 */
func methods(t *Type) *Sig {
	// method type
	mt := methtype(t, 0)

	if mt == nil {
		return nil
	}
	expandmeth(mt)

	// type stored in interface word
	it := t

	if !isdirectiface(it) {
		it = Ptrto(t)
	}

	// make list of methods for t,
	// generating code if necessary.
	var a *Sig

	var this *Type
	var b *Sig
	var method *Sym
	for f := mt.Xmethod; f != nil; f = f.Down {
		if f.Etype != TFIELD {
			Fatal("methods: not field %v", f)
		}
		if f.Type.Etype != TFUNC || f.Type.Thistuple == 0 {
			Fatal("non-method on %v method %v %v\n", mt, f.Sym, f)
		}
		if getthisx(f.Type).Type == nil {
			Fatal("receiver with no type on %v method %v %v\n", mt, f.Sym, f)
		}
		if f.Nointerface {
			continue
		}

		method = f.Sym
		if method == nil {
			continue
		}

		// get receiver type for this particular method.
		// if pointer receiver but non-pointer t and
		// this is not an embedded pointer inside a struct,
		// method does not apply.
		this = getthisx(f.Type).Type.Type

		if Isptr[this.Etype] && this.Type == t {
			continue
		}
		if Isptr[this.Etype] && !Isptr[t.Etype] && f.Embedded != 2 && !isifacemethod(f.Type) {
			continue
		}

		b = new(Sig)
		b.link = a
		a = b

		a.name = method.Name
		if !exportname(method.Name) {
			if method.Pkg == nil {
				Fatal("methods: missing package")
			}
			a.pkg = method.Pkg
		}

		a.isym = methodsym(method, it, 1)
		a.tsym = methodsym(method, t, 0)
		a.type_ = methodfunc(f.Type, t)
		a.mtype = methodfunc(f.Type, nil)

		if a.isym.Flags&SymSiggen == 0 {
			a.isym.Flags |= SymSiggen
			if !Eqtype(this, it) || this.Width < Types[Tptr].Width {
				compiling_wrappers = 1
				genwrapper(it, f, a.isym, 1)
				compiling_wrappers = 0
			}
		}

		if a.tsym.Flags&SymSiggen == 0 {
			a.tsym.Flags |= SymSiggen
			if !Eqtype(this, t) {
				compiling_wrappers = 1
				genwrapper(t, f, a.tsym, 0)
				compiling_wrappers = 0
			}
		}
	}

	return lsort(a, sigcmp)
}

/*
 * return methods of interface type t, sorted by name.
 */
func imethods(t *Type) *Sig {
	var a *Sig
	var method *Sym
	var isym *Sym

	var all *Sig
	var last *Sig
	for f := t.Type; f != nil; f = f.Down {
		if f.Etype != TFIELD {
			Fatal("imethods: not field")
		}
		if f.Type.Etype != TFUNC || f.Sym == nil {
			continue
		}
		method = f.Sym
		a = new(Sig)
		a.name = method.Name
		if !exportname(method.Name) {
			if method.Pkg == nil {
				Fatal("imethods: missing package")
			}
			a.pkg = method.Pkg
		}

		a.mtype = f.Type
		a.offset = 0
		a.type_ = methodfunc(f.Type, nil)

		if last != nil && sigcmp(last, a) >= 0 {
			Fatal("sigcmp vs sortinter %s %s", last.name, a.name)
		}
		if last == nil {
			all = a
		} else {
			last.link = a
		}
		last = a

		// Compiler can only refer to wrappers for non-blank methods.
		if isblanksym(method) {
			continue
		}

		// NOTE(rsc): Perhaps an oversight that
		// IfaceType.Method is not in the reflect data.
		// Generate the method body, so that compiled
		// code can refer to it.
		isym = methodsym(method, t, 0)

		if isym.Flags&SymSiggen == 0 {
			isym.Flags |= SymSiggen
			genwrapper(t, f, isym, 0)
		}
	}

	return all
}

var dimportpath_gopkg *Pkg

func dimportpath(p *Pkg) {
	if p.Pathsym != nil {
		return
	}

	// If we are compiling the runtime package, there are two runtime packages around
	// -- localpkg and Runtimepkg.  We don't want to produce import path symbols for
	// both of them, so just produce one for localpkg.
	if myimportpath == "runtime" && p == Runtimepkg {
		return
	}

	if dimportpath_gopkg == nil {
		dimportpath_gopkg = mkpkg("go")
		dimportpath_gopkg.Name = "go"
	}

	nam := "importpath." + p.Prefix + "."

	n := Nod(ONAME, nil, nil)
	n.Sym = Pkglookup(nam, dimportpath_gopkg)

	n.Class = PEXTERN
	n.Xoffset = 0
	p.Pathsym = n.Sym

	if p == localpkg {
		// Note: myimportpath != "", or else dgopkgpath won't call dimportpath.
		gdatastring(n, myimportpath)
	} else {
		gdatastring(n, p.Path)
	}
	ggloblsym(n.Sym, int32(Types[TSTRING].Width), obj.DUPOK|obj.RODATA)
}

func dgopkgpath(s *Sym, ot int, pkg *Pkg) int {
	if pkg == nil {
		return dgostringptr(s, ot, "")
	}

	if pkg == localpkg && myimportpath == "" {
		// If we don't know the full path of the package being compiled (i.e. -p
		// was not passed on the compiler command line), emit reference to
		// go.importpath.""., which 6l will rewrite using the correct import path.
		// Every package that imports this one directly defines the symbol.
		var ns *Sym

		if ns == nil {
			ns = Pkglookup("importpath.\"\".", mkpkg("go"))
		}
		return dsymptr(s, ot, ns, 0)
	}

	dimportpath(pkg)
	return dsymptr(s, ot, pkg.Pathsym, 0)
}

/*
 * uncommonType
 * ../../runtime/type.go:/uncommonType
 */
func dextratype(sym *Sym, off int, t *Type, ptroff int) int {
	m := methods(t)
	if t.Sym == nil && m == nil {
		return off
	}

	// fill in *extraType pointer in header
	off = int(Rnd(int64(off), int64(Widthptr)))

	dsymptr(sym, ptroff, sym, off)

	n := 0
	for a := m; a != nil; a = a.link {
		dtypesym(a.type_)
		n++
	}

	ot := off
	s := sym
	if t.Sym != nil {
		ot = dgostringptr(s, ot, t.Sym.Name)
		if t != Types[t.Etype] && t != errortype {
			ot = dgopkgpath(s, ot, t.Sym.Pkg)
		} else {
			ot = dgostringptr(s, ot, "")
		}
	} else {
		ot = dgostringptr(s, ot, "")
		ot = dgostringptr(s, ot, "")
	}

	// slice header
	ot = dsymptr(s, ot, s, ot+Widthptr+2*Widthint)

	ot = duintxx(s, ot, uint64(n), Widthint)
	ot = duintxx(s, ot, uint64(n), Widthint)

	// methods
	for a := m; a != nil; a = a.link {
		// method
		// ../../runtime/type.go:/method
		ot = dgostringptr(s, ot, a.name)

		ot = dgopkgpath(s, ot, a.pkg)
		ot = dsymptr(s, ot, dtypesym(a.mtype), 0)
		ot = dsymptr(s, ot, dtypesym(a.type_), 0)
		if a.isym != nil {
			ot = dsymptr(s, ot, a.isym, 0)
		} else {
			ot = duintptr(s, ot, 0)
		}
		if a.tsym != nil {
			ot = dsymptr(s, ot, a.tsym, 0)
		} else {
			ot = duintptr(s, ot, 0)
		}
	}

	return ot
}

var kinds = []int{
	TINT:        obj.KindInt,
	TUINT:       obj.KindUint,
	TINT8:       obj.KindInt8,
	TUINT8:      obj.KindUint8,
	TINT16:      obj.KindInt16,
	TUINT16:     obj.KindUint16,
	TINT32:      obj.KindInt32,
	TUINT32:     obj.KindUint32,
	TINT64:      obj.KindInt64,
	TUINT64:     obj.KindUint64,
	TUINTPTR:    obj.KindUintptr,
	TFLOAT32:    obj.KindFloat32,
	TFLOAT64:    obj.KindFloat64,
	TBOOL:       obj.KindBool,
	TSTRING:     obj.KindString,
	TPTR32:      obj.KindPtr,
	TPTR64:      obj.KindPtr,
	TSTRUCT:     obj.KindStruct,
	TINTER:      obj.KindInterface,
	TCHAN:       obj.KindChan,
	TMAP:        obj.KindMap,
	TARRAY:      obj.KindArray,
	TFUNC:       obj.KindFunc,
	TCOMPLEX64:  obj.KindComplex64,
	TCOMPLEX128: obj.KindComplex128,
	TUNSAFEPTR:  obj.KindUnsafePointer,
}

func haspointers(t *Type) bool {
	if t.Haspointers != 0 {
		return t.Haspointers-1 != 0
	}

	var ret bool
	switch t.Etype {
	case TINT,
		TUINT,
		TINT8,
		TUINT8,
		TINT16,
		TUINT16,
		TINT32,
		TUINT32,
		TINT64,
		TUINT64,
		TUINTPTR,
		TFLOAT32,
		TFLOAT64,
		TCOMPLEX64,
		TCOMPLEX128,
		TBOOL:
		ret = false

	case TARRAY:
		if t.Bound < 0 { // slice
			ret = true
			break
		}

		if t.Bound == 0 { // empty array
			ret = false
			break
		}

		ret = haspointers(t.Type)

	case TSTRUCT:
		ret = false
		for t1 := t.Type; t1 != nil; t1 = t1.Down {
			if haspointers(t1.Type) {
				ret = true
				break
			}
		}

	case TSTRING,
		TPTR32,
		TPTR64,
		TUNSAFEPTR,
		TINTER,
		TCHAN,
		TMAP,
		TFUNC:
		fallthrough
	default:
		ret = true

	case TFIELD:
		Fatal("haspointers: unexpected type, %v", t)
	}

	t.Haspointers = 1 + uint8(obj.Bool2int(ret))
	return ret
}

// typeptrdata returns the length in bytes of the prefix of t
// containing pointer data. Anything after this offset is scalar data.
func typeptrdata(t *Type) int64 {
	if !haspointers(t) {
		return 0
	}

	switch t.Etype {
	case TPTR32,
		TPTR64,
		TUNSAFEPTR,
		TFUNC,
		TCHAN,
		TMAP:
		return int64(Widthptr)

	case TSTRING:
		// struct { byte *str; intgo len; }
		return int64(Widthptr)

	case TINTER:
		// struct { Itab *tab;	void *data; } or
		// struct { Type *type; void *data; }
		return 2 * int64(Widthptr)

	case TARRAY:
		if Isslice(t) {
			// struct { byte *array; uintgo len; uintgo cap; }
			return int64(Widthptr)
		}
		// haspointers already eliminated t.Bound == 0.
		return (t.Bound-1)*t.Type.Width + typeptrdata(t.Type)

	case TSTRUCT:
		// Find the last field that has pointers.
		var lastPtrField *Type
		for t1 := t.Type; t1 != nil; t1 = t1.Down {
			if haspointers(t1.Type) {
				lastPtrField = t1
			}
		}
		return lastPtrField.Width + typeptrdata(lastPtrField.Type)

	default:
		Fatal("typeptrdata: unexpected type, %v", t)
		return 0
	}
}

/*
 * commonType
 * ../../runtime/type.go:/commonType
 */

var dcommontype_algarray *Sym

func dcommontype(s *Sym, ot int, t *Type) int {
	if ot != 0 {
		Fatal("dcommontype %d", ot)
	}

	sizeofAlg := 2 * Widthptr
	if dcommontype_algarray == nil {
		dcommontype_algarray = Pkglookup("algarray", Runtimepkg)
	}
	dowidth(t)
	alg := algtype(t)
	var algsym *Sym
	if alg < 0 || alg == AMEM {
		algsym = dalgsym(t)
	}

	var sptr *Sym
	tptr := Ptrto(t)
	if !Isptr[t.Etype] && (t.Sym != nil || methods(tptr) != nil) {
		sptr = dtypesym(tptr)
	} else {
		sptr = weaktypesym(tptr)
	}

	// All (non-reflect-allocated) Types share the same zero object.
	// Each place in the compiler where a pointer to the zero object
	// might be returned by a runtime call (map access return value,
	// 2-arg type cast) declares the size of the zerovalue it needs.
	// The linker magically takes the max of all the sizes.
	zero := Pkglookup("zerovalue", Runtimepkg)

	gcsym, useGCProg, ptrdata := dgcsym(t)

	// We use size 0 here so we get the pointer to the zero value,
	// but don't allocate space for the zero value unless we need it.
	// TODO: how do we get this symbol into bss?  We really want
	// a read-only bss, but I don't think such a thing exists.

	// ../../pkg/reflect/type.go:/^type.commonType
	// actual type structure
	//	type commonType struct {
	//		size          uintptr
	//		ptrsize       uintptr
	//		hash          uint32
	//		_             uint8
	//		align         uint8
	//		fieldAlign    uint8
	//		kind          uint8
	//		alg           unsafe.Pointer
	//		gcdata        unsafe.Pointer
	//		string        *string
	//		*extraType
	//		ptrToThis     *Type
	//		zero          unsafe.Pointer
	//	}
	ot = duintptr(s, ot, uint64(t.Width))
	ot = duintptr(s, ot, uint64(ptrdata))

	ot = duint32(s, ot, typehash(t))
	ot = duint8(s, ot, 0) // unused

	// runtime (and common sense) expects alignment to be a power of two.
	i := int(t.Align)

	if i == 0 {
		i = 1
	}
	if i&(i-1) != 0 {
		Fatal("invalid alignment %d for %v", t.Align, t)
	}
	ot = duint8(s, ot, t.Align) // align
	ot = duint8(s, ot, t.Align) // fieldAlign

	i = kinds[t.Etype]
	if t.Etype == TARRAY && t.Bound < 0 {
		i = obj.KindSlice
	}
	if !haspointers(t) {
		i |= obj.KindNoPointers
	}
	if isdirectiface(t) {
		i |= obj.KindDirectIface
	}
	if useGCProg {
		i |= obj.KindGCProg
	}
	ot = duint8(s, ot, uint8(i)) // kind
	if algsym == nil {
		ot = dsymptr(s, ot, dcommontype_algarray, alg*sizeofAlg)
	} else {
		ot = dsymptr(s, ot, algsym, 0)
	}
	ot = dsymptr(s, ot, gcsym, 0)

	p := Tconv(t, obj.FmtLeft|obj.FmtUnsigned)

	//print("dcommontype: %s\n", p);
	ot = dgostringptr(s, ot, p) // string

	// skip pointer to extraType,
	// which follows the rest of this type structure.
	// caller will fill in if needed.
	// otherwise linker will assume 0.
	ot += Widthptr

	ot = dsymptr(s, ot, sptr, 0) // ptrto type
	ot = dsymptr(s, ot, zero, 0) // ptr to zero value
	return ot
}

func typesym(t *Type) *Sym {
	return Pkglookup(Tconv(t, obj.FmtLeft), typepkg)
}

func tracksym(t *Type) *Sym {
	return Pkglookup(Tconv(t.Outer, obj.FmtLeft)+"."+t.Sym.Name, trackpkg)
}

func typelinksym(t *Type) *Sym {
	// %-uT is what the generated Type's string field says.
	// It uses (ambiguous) package names instead of import paths.
	// %-T is the complete, unambiguous type name.
	// We want the types to end up sorted by string field,
	// so use that first in the name, and then add :%-T to
	// disambiguate. We use a tab character as the separator to
	// ensure the types appear sorted by their string field. The
	// names are a little long but they are discarded by the linker
	// and do not end up in the symbol table of the final binary.
	p := Tconv(t, obj.FmtLeft|obj.FmtUnsigned) + "\t" + Tconv(t, obj.FmtLeft)

	s := Pkglookup(p, typelinkpkg)

	//print("typelinksym: %s -> %+S\n", p, s);

	return s
}

func typesymprefix(prefix string, t *Type) *Sym {
	p := prefix + "." + Tconv(t, obj.FmtLeft)
	s := Pkglookup(p, typepkg)

	//print("algsym: %s -> %+S\n", p, s);

	return s
}

func typenamesym(t *Type) *Sym {
	if t == nil || (Isptr[t.Etype] && t.Type == nil) || isideal(t) {
		Fatal("typename %v", t)
	}
	s := typesym(t)
	if s.Def == nil {
		n := Nod(ONAME, nil, nil)
		n.Sym = s
		n.Type = Types[TUINT8]
		n.Addable = true
		n.Ullman = 1
		n.Class = PEXTERN
		n.Xoffset = 0
		n.Typecheck = 1
		s.Def = n

		signatlist = list(signatlist, typenod(t))
	}

	return s.Def.Sym
}

func typename(t *Type) *Node {
	s := typenamesym(t)
	n := Nod(OADDR, s.Def, nil)
	n.Type = Ptrto(s.Def.Type)
	n.Addable = true
	n.Ullman = 2
	n.Typecheck = 1
	return n
}

func weaktypesym(t *Type) *Sym {
	p := Tconv(t, obj.FmtLeft)
	s := Pkglookup(p, weaktypepkg)

	//print("weaktypesym: %s -> %+S\n", p, s);

	return s
}

/*
 * Returns 1 if t has a reflexive equality operator.
 * That is, if x==x for all x of type t.
 */
func isreflexive(t *Type) bool {
	switch t.Etype {
	case TBOOL,
		TINT,
		TUINT,
		TINT8,
		TUINT8,
		TINT16,
		TUINT16,
		TINT32,
		TUINT32,
		TINT64,
		TUINT64,
		TUINTPTR,
		TPTR32,
		TPTR64,
		TUNSAFEPTR,
		TSTRING,
		TCHAN:
		return true

	case TFLOAT32,
		TFLOAT64,
		TCOMPLEX64,
		TCOMPLEX128,
		TINTER:
		return false

	case TARRAY:
		if Isslice(t) {
			Fatal("slice can't be a map key: %v", t)
		}
		return isreflexive(t.Type)

	case TSTRUCT:
		for t1 := t.Type; t1 != nil; t1 = t1.Down {
			if !isreflexive(t1.Type) {
				return false
			}
		}

		return true

	default:
		Fatal("bad type for map key: %v", t)
		return false
	}
}

func dtypesym(t *Type) *Sym {
	// Replace byte, rune aliases with real type.
	// They've been separate internally to make error messages
	// better, but we have to merge them in the reflect tables.
	if t == bytetype || t == runetype {
		t = Types[t.Etype]
	}

	if isideal(t) {
		Fatal("dtypesym %v", t)
	}

	s := typesym(t)
	if s.Flags&SymSiggen != 0 {
		return s
	}
	s.Flags |= SymSiggen

	// special case (look for runtime below):
	// when compiling package runtime,
	// emit the type structures for int, float, etc.
	tbase := t

	if Isptr[t.Etype] && t.Sym == nil && t.Type.Sym != nil {
		tbase = t.Type
	}
	dupok := 0
	if tbase.Sym == nil {
		dupok = obj.DUPOK
	}

	if compiling_runtime != 0 && (tbase == Types[tbase.Etype] || tbase == bytetype || tbase == runetype || tbase == errortype) { // int, float, etc
		goto ok
	}

	// named types from other files are defined only by those files
	if tbase.Sym != nil && !tbase.Local {
		return s
	}
	if isforw[tbase.Etype] {
		return s
	}

ok:
	ot := 0
	xt := 0
	switch t.Etype {
	default:
		ot = dcommontype(s, ot, t)
		xt = ot - 3*Widthptr

	case TARRAY:
		if t.Bound >= 0 {
			// ../../runtime/type.go:/ArrayType
			s1 := dtypesym(t.Type)

			t2 := typ(TARRAY)
			t2.Type = t.Type
			t2.Bound = -1 // slice
			s2 := dtypesym(t2)
			ot = dcommontype(s, ot, t)
			xt = ot - 3*Widthptr
			ot = dsymptr(s, ot, s1, 0)
			ot = dsymptr(s, ot, s2, 0)
			ot = duintptr(s, ot, uint64(t.Bound))
		} else {
			// ../../runtime/type.go:/SliceType
			s1 := dtypesym(t.Type)

			ot = dcommontype(s, ot, t)
			xt = ot - 3*Widthptr
			ot = dsymptr(s, ot, s1, 0)
		}

		// ../../runtime/type.go:/ChanType
	case TCHAN:
		s1 := dtypesym(t.Type)

		ot = dcommontype(s, ot, t)
		xt = ot - 3*Widthptr
		ot = dsymptr(s, ot, s1, 0)
		ot = duintptr(s, ot, uint64(t.Chan))

	case TFUNC:
		for t1 := getthisx(t).Type; t1 != nil; t1 = t1.Down {
			dtypesym(t1.Type)
		}
		isddd := false
		for t1 := getinargx(t).Type; t1 != nil; t1 = t1.Down {
			isddd = t1.Isddd
			dtypesym(t1.Type)
		}

		for t1 := getoutargx(t).Type; t1 != nil; t1 = t1.Down {
			dtypesym(t1.Type)
		}

		ot = dcommontype(s, ot, t)
		xt = ot - 3*Widthptr
		ot = duint8(s, ot, uint8(obj.Bool2int(isddd)))

		// two slice headers: in and out.
		ot = int(Rnd(int64(ot), int64(Widthptr)))

		ot = dsymptr(s, ot, s, ot+2*(Widthptr+2*Widthint))
		n := t.Thistuple + t.Intuple
		ot = duintxx(s, ot, uint64(n), Widthint)
		ot = duintxx(s, ot, uint64(n), Widthint)
		ot = dsymptr(s, ot, s, ot+1*(Widthptr+2*Widthint)+n*Widthptr)
		ot = duintxx(s, ot, uint64(t.Outtuple), Widthint)
		ot = duintxx(s, ot, uint64(t.Outtuple), Widthint)

		// slice data
		for t1 := getthisx(t).Type; t1 != nil; t1 = t1.Down {
			ot = dsymptr(s, ot, dtypesym(t1.Type), 0)
			n++
		}
		for t1 := getinargx(t).Type; t1 != nil; t1 = t1.Down {
			ot = dsymptr(s, ot, dtypesym(t1.Type), 0)
			n++
		}
		for t1 := getoutargx(t).Type; t1 != nil; t1 = t1.Down {
			ot = dsymptr(s, ot, dtypesym(t1.Type), 0)
			n++
		}

	case TINTER:
		m := imethods(t)
		n := 0
		for a := m; a != nil; a = a.link {
			dtypesym(a.type_)
			n++
		}

		// ../../runtime/type.go:/InterfaceType
		ot = dcommontype(s, ot, t)

		xt = ot - 3*Widthptr
		ot = dsymptr(s, ot, s, ot+Widthptr+2*Widthint)
		ot = duintxx(s, ot, uint64(n), Widthint)
		ot = duintxx(s, ot, uint64(n), Widthint)
		for a := m; a != nil; a = a.link {
			// ../../runtime/type.go:/imethod
			ot = dgostringptr(s, ot, a.name)

			ot = dgopkgpath(s, ot, a.pkg)
			ot = dsymptr(s, ot, dtypesym(a.type_), 0)
		}

		// ../../runtime/type.go:/MapType
	case TMAP:
		s1 := dtypesym(t.Down)

		s2 := dtypesym(t.Type)
		s3 := dtypesym(mapbucket(t))
		s4 := dtypesym(hmap(t))
		ot = dcommontype(s, ot, t)
		xt = ot - 3*Widthptr
		ot = dsymptr(s, ot, s1, 0)
		ot = dsymptr(s, ot, s2, 0)
		ot = dsymptr(s, ot, s3, 0)
		ot = dsymptr(s, ot, s4, 0)
		if t.Down.Width > MAXKEYSIZE {
			ot = duint8(s, ot, uint8(Widthptr))
			ot = duint8(s, ot, 1) // indirect
		} else {
			ot = duint8(s, ot, uint8(t.Down.Width))
			ot = duint8(s, ot, 0) // not indirect
		}

		if t.Type.Width > MAXVALSIZE {
			ot = duint8(s, ot, uint8(Widthptr))
			ot = duint8(s, ot, 1) // indirect
		} else {
			ot = duint8(s, ot, uint8(t.Type.Width))
			ot = duint8(s, ot, 0) // not indirect
		}

		ot = duint16(s, ot, uint16(mapbucket(t).Width))
		ot = duint8(s, ot, uint8(obj.Bool2int(isreflexive(t.Down))))

	case TPTR32, TPTR64:
		if t.Type.Etype == TANY {
			// ../../runtime/type.go:/UnsafePointerType
			ot = dcommontype(s, ot, t)

			break
		}

		// ../../runtime/type.go:/PtrType
		s1 := dtypesym(t.Type)

		ot = dcommontype(s, ot, t)
		xt = ot - 3*Widthptr
		ot = dsymptr(s, ot, s1, 0)

		// ../../runtime/type.go:/StructType
	// for security, only the exported fields.
	case TSTRUCT:
		n := 0

		for t1 := t.Type; t1 != nil; t1 = t1.Down {
			dtypesym(t1.Type)
			n++
		}

		ot = dcommontype(s, ot, t)
		xt = ot - 3*Widthptr
		ot = dsymptr(s, ot, s, ot+Widthptr+2*Widthint)
		ot = duintxx(s, ot, uint64(n), Widthint)
		ot = duintxx(s, ot, uint64(n), Widthint)
		for t1 := t.Type; t1 != nil; t1 = t1.Down {
			// ../../runtime/type.go:/structField
			if t1.Sym != nil && t1.Embedded == 0 {
				ot = dgostringptr(s, ot, t1.Sym.Name)
				if exportname(t1.Sym.Name) {
					ot = dgostringptr(s, ot, "")
				} else {
					ot = dgopkgpath(s, ot, t1.Sym.Pkg)
				}
			} else {
				ot = dgostringptr(s, ot, "")
				if t1.Type.Sym != nil && t1.Type.Sym.Pkg == builtinpkg {
					ot = dgopkgpath(s, ot, localpkg)
				} else {
					ot = dgostringptr(s, ot, "")
				}
			}

			ot = dsymptr(s, ot, dtypesym(t1.Type), 0)
			ot = dgostrlitptr(s, ot, t1.Note)
			ot = duintptr(s, ot, uint64(t1.Width)) // field offset
		}
	}

	ot = dextratype(s, ot, t, xt)
	ggloblsym(s, int32(ot), int16(dupok|obj.RODATA))

	// generate typelink.foo pointing at s = type.foo.
	// The linker will leave a table of all the typelinks for
	// types in the binary, so reflect can find them.
	// We only need the link for unnamed composites that
	// we want be able to find.
	if t.Sym == nil {
		switch t.Etype {
		case TPTR32, TPTR64:
			// The ptrto field of the type data cannot be relied on when
			// dynamic linking: a type T may be defined in a module that makes
			// no use of pointers to that type, but another module can contain
			// a package that imports the first one and does use *T pointers.
			// The second module will end up defining type data for *T and a
			// type.*T symbol pointing at it. It's important that calling
			// .PtrTo() on the reflect.Type for T returns this type data and
			// not some synthesized object, so we need reflect to be able to
			// find it!
			if !Ctxt.Flag_dynlink {
				break
			}
			fallthrough
		case TARRAY, TCHAN, TFUNC, TMAP:
			slink := typelinksym(t)
			dsymptr(slink, 0, s, 0)
			ggloblsym(slink, int32(Widthptr), int16(dupok|obj.RODATA))
		}
	}

	return s
}

func dumptypestructs() {
	var n *Node

	// copy types from externdcl list to signatlist
	for l := externdcl; l != nil; l = l.Next {
		n = l.N
		if n.Op != OTYPE {
			continue
		}
		signatlist = list(signatlist, n)
	}

	// process signatlist
	var t *Type
	for l := signatlist; l != nil; l = l.Next {
		n = l.N
		if n.Op != OTYPE {
			continue
		}
		t = n.Type
		dtypesym(t)
		if t.Sym != nil {
			dtypesym(Ptrto(t))
		}
	}

	// generate import strings for imported packages
	for _, p := range pkgs {
		if p.Direct != 0 {
			dimportpath(p)
		}
	}

	// do basic types if compiling package runtime.
	// they have to be in at least one package,
	// and runtime is always loaded implicitly,
	// so this is as good as any.
	// another possible choice would be package main,
	// but using runtime means fewer copies in .6 files.
	if compiling_runtime != 0 {
		for i := 1; i <= TBOOL; i++ {
			dtypesym(Ptrto(Types[i]))
		}
		dtypesym(Ptrto(Types[TSTRING]))
		dtypesym(Ptrto(Types[TUNSAFEPTR]))

		// emit type structs for error and func(error) string.
		// The latter is the type of an auto-generated wrapper.
		dtypesym(Ptrto(errortype))

		dtypesym(functype(nil, list1(Nod(ODCLFIELD, nil, typenod(errortype))), list1(Nod(ODCLFIELD, nil, typenod(Types[TSTRING])))))

		// add paths for runtime and main, which 6l imports implicitly.
		dimportpath(Runtimepkg)

		if flag_race != 0 {
			dimportpath(racepkg)
		}
		dimportpath(mkpkg("main"))
	}
}

func dalgsym(t *Type) *Sym {
	var s *Sym
	var hashfunc *Sym
	var eqfunc *Sym

	// dalgsym is only called for a type that needs an algorithm table,
	// which implies that the type is comparable (or else it would use ANOEQ).

	if algtype(t) == AMEM {
		// we use one algorithm table for all AMEM types of a given size
		p := fmt.Sprintf(".alg%d", t.Width)

		s = Pkglookup(p, typepkg)

		if s.Flags&SymAlgGen != 0 {
			return s
		}
		s.Flags |= SymAlgGen

		// make hash closure
		p = fmt.Sprintf(".hashfunc%d", t.Width)

		hashfunc = Pkglookup(p, typepkg)

		ot := 0
		ot = dsymptr(hashfunc, ot, Pkglookup("memhash_varlen", Runtimepkg), 0)
		ot = duintxx(hashfunc, ot, uint64(t.Width), Widthptr) // size encoded in closure
		ggloblsym(hashfunc, int32(ot), obj.DUPOK|obj.RODATA)

		// make equality closure
		p = fmt.Sprintf(".eqfunc%d", t.Width)

		eqfunc = Pkglookup(p, typepkg)

		ot = 0
		ot = dsymptr(eqfunc, ot, Pkglookup("memequal_varlen", Runtimepkg), 0)
		ot = duintxx(eqfunc, ot, uint64(t.Width), Widthptr)
		ggloblsym(eqfunc, int32(ot), obj.DUPOK|obj.RODATA)
	} else {
		// generate an alg table specific to this type
		s = typesymprefix(".alg", t)

		hash := typesymprefix(".hash", t)
		eq := typesymprefix(".eq", t)
		hashfunc = typesymprefix(".hashfunc", t)
		eqfunc = typesymprefix(".eqfunc", t)

		genhash(hash, t)
		geneq(eq, t)

		// make Go funcs (closures) for calling hash and equal from Go
		dsymptr(hashfunc, 0, hash, 0)

		ggloblsym(hashfunc, int32(Widthptr), obj.DUPOK|obj.RODATA)
		dsymptr(eqfunc, 0, eq, 0)
		ggloblsym(eqfunc, int32(Widthptr), obj.DUPOK|obj.RODATA)
	}

	// ../../runtime/alg.go:/typeAlg
	ot := 0

	ot = dsymptr(s, ot, hashfunc, 0)
	ot = dsymptr(s, ot, eqfunc, 0)
	ggloblsym(s, int32(ot), obj.DUPOK|obj.RODATA)
	return s
}

// maxPtrmaskBytes is the maximum length of a GC ptrmask bitmap,
// which holds 1-bit entries describing where pointers are in a given type.
// 16 bytes is enough to describe 128 pointer-sized words, 512 or 1024 bytes
// depending on the system. Above this length, the GC information is
// recorded as a GC program, which can express repetition compactly.
// In either form, the information is used by the runtime to initialize the
// heap bitmap, and for large types (like 128 or more words), they are
// roughly the same speed. GC programs are never much larger and often
// more compact. (If large arrays are involved, they can be arbitrarily more
// compact.)
//
// The cutoff must be large enough that any allocation large enough to
// use a GC program is large enough that it does not share heap bitmap
// bytes with any other objects, allowing the GC program execution to
// assume an aligned start and not use atomic operations. In the current
// runtime, this means all malloc size classes larger than the cutoff must
// be multiples of four words. On 32-bit systems that's 16 bytes, and
// all size classes >= 16 bytes are 16-byte aligned, so no real constraint.
// On 64-bit systems, that's 32 bytes, and 32-byte alignment is guaranteed
// for size classes >= 256 bytes. On a 64-bit sytem, 256 bytes allocated
// is 32 pointers, the bits for which fit in 4 bytes. So maxPtrmaskBytes
// must be >= 4.
//
// We used to use 16 because the GC programs do have some constant overhead
// to get started, and processing 128 pointers seems to be enough to
// amortize that overhead well.
//
// To make sure that the runtime's chansend can call typeBitsBulkBarrier,
// we raised the limit to 2048, so that even 32-bit systems are guaranteed to
// use bitmaps for objects up to 64 kB in size.
//
// Also known to reflect/type.go.
//
const maxPtrmaskBytes = 2048

// dgcsym emits and returns a data symbol containing GC information for type t,
// along with a boolean reporting whether the UseGCProg bit should be set in
// the type kind, and the ptrdata field to record in the reflect type information.
func dgcsym(t *Type) (sym *Sym, useGCProg bool, ptrdata int64) {
	ptrdata = typeptrdata(t)
	if ptrdata/int64(Widthptr) <= maxPtrmaskBytes*8 {
		sym = dgcptrmask(t)
		return
	}

	useGCProg = true
	sym, ptrdata = dgcprog(t)
	return
}

// dgcptrmask emits and returns the symbol containing a pointer mask for type t.
func dgcptrmask(t *Type) *Sym {
	ptrmask := make([]byte, (typeptrdata(t)/int64(Widthptr)+7)/8)
	fillptrmask(t, ptrmask)
	p := fmt.Sprintf("gcbits.%x", ptrmask)

	sym := Pkglookup(p, Runtimepkg)
	if sym.Flags&SymUniq == 0 {
		sym.Flags |= SymUniq
		for i, x := range ptrmask {
			duint8(sym, i, x)
		}
		ggloblsym(sym, int32(len(ptrmask)), obj.DUPOK|obj.RODATA|obj.LOCAL)
	}
	return sym
}

// fillptrmask fills in ptrmask with 1s corresponding to the
// word offsets in t that hold pointers.
// ptrmask is assumed to fit at least typeptrdata(t)/Widthptr bits.
func fillptrmask(t *Type, ptrmask []byte) {
	for i := range ptrmask {
		ptrmask[i] = 0
	}
	if !haspointers(t) {
		return
	}

	vec := bvalloc(8 * int32(len(ptrmask)))
	xoffset := int64(0)
	onebitwalktype1(t, &xoffset, vec)

	nptr := typeptrdata(t) / int64(Widthptr)
	for i := int64(0); i < nptr; i++ {
		if bvget(vec, int32(i)) == 1 {
			ptrmask[i/8] |= 1 << (uint(i) % 8)
		}
	}
}

// dgcprog emits and returns the symbol containing a GC program for type t
// along with the size of the data described by the program (in the range [typeptrdata(t), t.Width]).
// In practice, the size is typeptrdata(t) except for non-trivial arrays.
// For non-trivial arrays, the program describes the full t.Width size.
func dgcprog(t *Type) (*Sym, int64) {
	dowidth(t)
	if t.Width == BADWIDTH {
		Fatal("dgcprog: %v badwidth", t)
	}
	sym := typesymprefix(".gcprog", t)
	var p GCProg
	p.init(sym)
	p.emit(t, 0)
	offset := p.w.BitIndex() * int64(Widthptr)
	p.end()
	if ptrdata := typeptrdata(t); offset < ptrdata || offset > t.Width {
		Fatal("dgcprog: %v: offset=%d but ptrdata=%d size=%d", t, offset, ptrdata, t.Width)
	}
	return sym, offset
}

type GCProg struct {
	sym    *Sym
	symoff int
	w      gcprog.Writer
}

var Debug_gcprog int // set by -d gcprog

func (p *GCProg) init(sym *Sym) {
	p.sym = sym
	p.symoff = 4 // first 4 bytes hold program length
	p.w.Init(p.writeByte)
	if Debug_gcprog > 0 {
		fmt.Fprintf(os.Stderr, "compile: start GCProg for %v\n", sym)
		p.w.Debug(os.Stderr)
	}
}

func (p *GCProg) writeByte(x byte) {
	p.symoff = duint8(p.sym, p.symoff, x)
}

func (p *GCProg) end() {
	p.w.End()
	duint32(p.sym, 0, uint32(p.symoff-4))
	ggloblsym(p.sym, int32(p.symoff), obj.DUPOK|obj.RODATA|obj.LOCAL)
	if Debug_gcprog > 0 {
		fmt.Fprintf(os.Stderr, "compile: end GCProg for %v\n", p.sym)
	}
}

func (p *GCProg) emit(t *Type, offset int64) {
	dowidth(t)
	if !haspointers(t) {
		return
	}
	if t.Width == int64(Widthptr) {
		p.w.Ptr(offset / int64(Widthptr))
		return
	}
	switch t.Etype {
	default:
		Fatal("GCProg.emit: unexpected type %v", t)

	case TSTRING:
		p.w.Ptr(offset / int64(Widthptr))

	case TINTER:
		p.w.Ptr(offset / int64(Widthptr))
		p.w.Ptr(offset/int64(Widthptr) + 1)

	case TARRAY:
		if Isslice(t) {
			p.w.Ptr(offset / int64(Widthptr))
			return
		}
		if t.Bound == 0 {
			// should have been handled by haspointers check above
			Fatal("GCProg.emit: empty array")
		}

		// Flatten array-of-array-of-array to just a big array by multiplying counts.
		count := t.Bound
		elem := t.Type
		for Isfixedarray(elem) {
			count *= elem.Bound
			elem = elem.Type
		}

		if !p.w.ShouldRepeat(elem.Width/int64(Widthptr), count) {
			// Cheaper to just emit the bits.
			for i := int64(0); i < count; i++ {
				p.emit(elem, offset+i*elem.Width)
			}
			return
		}
		p.emit(elem, offset)
		p.w.ZeroUntil((offset + elem.Width) / int64(Widthptr))
		p.w.Repeat(elem.Width/int64(Widthptr), count-1)

	case TSTRUCT:
		for t1 := t.Type; t1 != nil; t1 = t1.Down {
			p.emit(t1.Type, offset+t1.Width)
		}
	}
}