subr.go 68.3 KB
Newer Older
1 2 3 4 5 6 7 8 9
// 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 (
	"bytes"
	"cmd/internal/obj"
10 11
	"crypto/md5"
	"encoding/binary"
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
	"fmt"
	"os"
	"sort"
	"strings"
	"unicode"
	"unicode/utf8"
)

type Error struct {
	lineno int
	seq    int
	msg    string
}

var errors []Error

var nerr int

var merr int

func errorexit() {
	Flusherrors()
	if outfile != "" {
		os.Remove(outfile)
	}
	os.Exit(2)
}

func parserline() int {
41 42
	if parsing && theparser.Lookahead() > 0 {
		// parser has one symbol lookahead
43 44 45 46 47 48 49 50 51
		return int(prevlineno)
	}
	return int(lineno)
}

func adderrorname(n *Node) {
	if n.Op != ODOT {
		return
	}
52
	old := fmt.Sprintf("%v: undefined: %v\n", n.Line(), Nconv(n.Left, 0))
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
	if len(errors) > 0 && int32(errors[len(errors)-1].lineno) == n.Lineno && errors[len(errors)-1].msg == old {
		errors[len(errors)-1].msg = fmt.Sprintf("%v: undefined: %v in %v\n", n.Line(), Nconv(n.Left, 0), Nconv(n, 0))
	}
}

func adderr(line int, format string, args []interface{}) {
	errors = append(errors, Error{
		seq:    len(errors),
		lineno: line,
		msg:    fmt.Sprintf("%v: %s\n", Ctxt.Line(line), fmt.Sprintf(format, args...)),
	})
}

type errcmp []Error

func (x errcmp) Len() int {
	return len(x)
}

func (x errcmp) Swap(i, j int) {
	x[i], x[j] = x[j], x[i]
}

func (x errcmp) Less(i, j int) bool {
77 78
	a := &x[i]
	b := &x[j]
79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
	if a.lineno != b.lineno {
		return a.lineno-b.lineno < 0
	}
	if a.seq != b.seq {
		return a.seq-b.seq < 0
	}
	return stringsCompare(a.msg, b.msg) < 0
}

func Flusherrors() {
	obj.Bflush(&bstdout)
	if len(errors) == 0 {
		return
	}
	sort.Sort(errcmp(errors[:len(errors)]))
94
	for i := 0; i < len(errors); i++ {
95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
		if i == 0 || errors[i].msg != errors[i-1].msg {
			fmt.Printf("%s", errors[i].msg)
		}
	}
	errors = errors[:0]
}

func hcrash() {
	if Debug['h'] != 0 {
		Flusherrors()
		if outfile != "" {
			os.Remove(outfile)
		}
		var x *int
		*x = 0
	}
}

func yyerrorl(line int, fmt_ string, args ...interface{}) {
	adderr(line, fmt_, args)

	hcrash()
	nerrors++
118
	if nsavederrors+nerrors >= 10 && Debug['e'] == 0 {
119 120 121 122 123 124 125 126 127 128 129 130 131
		Flusherrors()
		fmt.Printf("%v: too many errors\n", Ctxt.Line(line))
		errorexit()
	}
}

var yystate int

var yychar_subr int

var yyerror_lastsyntax int

func Yyerror(fmt_ string, args ...interface{}) {
132 133 134
	// bison used to invoke yyerror("syntax error").
	// With Go yacc we get yyerror("%s", "syntax error").
	// Convert to keep the old code working.
135
	if fmt_ == "%s" && len(args) == 1 && args[0] == "syntax error" {
136 137
		fmt_ = "syntax error"
		args = nil
138
	}
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
	if strings.HasPrefix(fmt_, "syntax error") {
		nsyntaxerrors++

		if Debug['x'] != 0 {
			fmt.Printf("yyerror: yystate=%d yychar=%d\n", yystate, yychar_subr)
		}

		// An unexpected EOF caused a syntax error. Use the previous
		// line number since getc generated a fake newline character.
		if curio.eofnl != 0 {
			lexlineno = prevlineno
		}

		// only one syntax error per line
		if int32(yyerror_lastsyntax) == lexlineno {
			return
		}
		yyerror_lastsyntax = int(lexlineno)

		if strings.Contains(fmt_, "{ or {") || strings.Contains(fmt_, " or ?") || strings.Contains(fmt_, " or @") {
			// The grammar has { and LBRACE but both show up as {.
			// Rewrite syntax error referring to "{ or {" to say just "{".
			// The grammar has ? and @ but only for reading imports.
			// Silence them in ordinary errors.
			fmt_ = strings.Replace(fmt_, "{ or {", "{", -1)
			fmt_ = strings.Replace(fmt_, " or ?", "", -1)
			fmt_ = strings.Replace(fmt_, " or @", "", -1)
		}

		// look for parse state-specific errors in list (see go.errors).
169
		for i := 0; i < len(yymsg); i++ {
170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195
			if yymsg[i].yystate == yystate && yymsg[i].yychar == yychar_subr {
				yyerrorl(int(lexlineno), "syntax error: %s", yymsg[i].msg)
				return
			}
		}

		// plain "syntax error" gets "near foo" added
		if fmt_ == "syntax error" {
			yyerrorl(int(lexlineno), "syntax error near %s", lexbuf.String())
			return
		}

		// if bison says "syntax error, more info"; print "syntax error: more info".
		if fmt_[12] == ',' {
			yyerrorl(int(lexlineno), "syntax error:%s", fmt_[13:])
			return
		}

		yyerrorl(int(lexlineno), "%s", fmt_)
		return
	}

	adderr(parserline(), fmt_, args)

	hcrash()
	nerrors++
196
	if nsavederrors+nerrors >= 10 && Debug['e'] == 0 {
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249
		Flusherrors()
		fmt.Printf("%v: too many errors\n", Ctxt.Line(parserline()))
		errorexit()
	}
}

func Warn(fmt_ string, args ...interface{}) {
	adderr(parserline(), fmt_, args)

	hcrash()
}

func Warnl(line int, fmt_ string, args ...interface{}) {
	adderr(line, fmt_, args)
	if Debug['m'] != 0 {
		Flusherrors()
	}
}

func Fatal(fmt_ string, args ...interface{}) {
	Flusherrors()

	fmt.Printf("%v: internal compiler error: ", Ctxt.Line(int(lineno)))
	fmt.Printf(fmt_, args...)
	fmt.Printf("\n")

	// If this is a released compiler version, ask for a bug report.
	if strings.HasPrefix(obj.Getgoversion(), "release") {
		fmt.Printf("\n")
		fmt.Printf("Please file a bug report including a short program that triggers the error.\n")
		fmt.Printf("https://golang.org/issue/new\n")
	}

	hcrash()
	errorexit()
}

func linehist(file string, off int32, relative int) {
	if Debug['i'] != 0 {
		if file != "" {
			if off < 0 {
				fmt.Printf("pragma %s", file)
			} else if off > 0 {
				fmt.Printf("line %s", file)
			} else {
				fmt.Printf("import %s", file)
			}
		} else {
			fmt.Printf("end of import")
		}
		fmt.Printf(" at line %v\n", Ctxt.Line(int(lexlineno)))
	}

250
	if off < 0 && file[0] != '/' && relative == 0 {
251 252 253 254 255 256
		file = fmt.Sprintf("%s/%s", Ctxt.Pathname, file)
	}
	obj.Linklinehist(Ctxt, int(lexlineno), file, int(off))
}

func setlineno(n *Node) int32 {
257
	lno := lineno
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279
	if n != nil {
		switch n.Op {
		case ONAME,
			OTYPE,
			OPACK,
			OLITERAL:
			break

		default:
			lineno = n.Lineno
			if lineno == 0 {
				if Debug['K'] != 0 {
					Warn("setlineno: line 0")
				}
				lineno = lno
			}
		}
	}

	return lno
}

280 281 282
func Lookup(name string) *Sym {
	return localpkg.Lookup(name)
}
283

284 285 286 287
func Lookupf(format string, a ...interface{}) *Sym {
	return Lookup(fmt.Sprintf(format, a...))
}

288 289 290
func LookupBytes(name []byte) *Sym {
	return localpkg.LookupBytes(name)
}
291

292 293
var initSyms []*Sym

294 295 296
var nopkg = &Pkg{
	Syms: make(map[string]*Sym),
}
297 298 299 300 301 302 303

func (pkg *Pkg) Lookup(name string) *Sym {
	if pkg == nil {
		pkg = nopkg
	}
	if s := pkg.Syms[name]; s != nil {
		return s
304 305
	}

306 307 308 309 310
	s := &Sym{
		Name:    name,
		Pkg:     pkg,
		Lexical: LNAME,
	}
311
	if name == "init" {
312 313 314 315
		initSyms = append(initSyms, s)
	}
	pkg.Syms[name] = s
	return s
316 317
}

318 319 320 321 322 323 324 325 326
func (pkg *Pkg) LookupBytes(name []byte) *Sym {
	if pkg == nil {
		pkg = nopkg
	}
	if s := pkg.Syms[string(name)]; s != nil {
		return s
	}
	str := internString(name)
	return pkg.Lookup(str)
327 328 329
}

func Pkglookup(name string, pkg *Pkg) *Sym {
330
	return pkg.Lookup(name)
331 332 333 334 335 336 337 338 339 340 341 342 343 344 345
}

func restrictlookup(name string, pkg *Pkg) *Sym {
	if !exportname(name) && pkg != localpkg {
		Yyerror("cannot refer to unexported name %s.%s", pkg.Name, name)
	}
	return Pkglookup(name, pkg)
}

// find all the exported symbols in package opkg
// and make them available in the current package
func importdot(opkg *Pkg, pack *Node) {
	var s1 *Sym
	var pkgerror string

346
	n := 0
347 348 349
	for _, s := range opkg.Syms {
		if s.Def == nil {
			continue
350
		}
351 352 353 354 355 356 357 358 359 360 361 362 363 364 365
		if !exportname(s.Name) || strings.ContainsRune(s.Name, 0xb7) { // 0xb7 = center dot
			continue
		}
		s1 = Lookup(s.Name)
		if s1.Def != nil {
			pkgerror = fmt.Sprintf("during import %q", opkg.Path)
			redeclare(s1, pkgerror)
			continue
		}

		s1.Def = s.Def
		s1.Block = s.Block
		s1.Def.Pack = pack
		s1.Origpkg = opkg
		n++
366 367 368 369
	}

	if n == 0 {
		// can't possibly be used - there were no symbols
370
		yyerrorl(int(pack.Lineno), "imported and not used: %q", opkg.Path)
371 372 373
	}
}

374
func gethunk() {
375
	nh := int32(NHUNK)
376 377 378
	if thunk >= 10*NHUNK {
		nh = 10 * NHUNK
	}
379
	h := string(make([]byte, nh))
380 381 382 383 384 385 386 387 388 389 390
	if h == "" {
		Flusherrors()
		Yyerror("out of memory")
		errorexit()
	}

	hunk = h
	nhunk = nh
	thunk += nh
}

391
func Nod(op int, nleft *Node, nright *Node) *Node {
392
	n := new(Node)
393 394 395 396 397 398 399 400 401 402 403 404 405 406
	n.Op = uint8(op)
	n.Left = nleft
	n.Right = nright
	n.Lineno = int32(parserline())
	n.Xoffset = BADWIDTH
	n.Orig = n
	n.Curfn = Curfn
	return n
}

func saveorignode(n *Node) {
	if n.Orig != nil {
		return
	}
407
	norig := Nod(int(n.Op), nil, nil)
408 409 410 411 412 413 414
	*norig = *n
	n.Orig = norig
}

// ispaddedfield reports whether the given field
// is followed by padding. For the case where t is
// the last field, total gives the size of the enclosing struct.
415
func ispaddedfield(t *Type, total int64) bool {
416 417 418 419
	if t.Etype != TFIELD {
		Fatal("ispaddedfield called non-field %v", Tconv(t, 0))
	}
	if t.Down == nil {
420
		return t.Width+t.Type.Width != total
421
	}
422
	return t.Width+t.Type.Width != t.Down.Width
423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484
}

func algtype1(t *Type, bad **Type) int {
	if bad != nil {
		*bad = nil
	}
	if t.Broke != 0 {
		return AMEM
	}
	if t.Noalg != 0 {
		return ANOEQ
	}

	switch t.Etype {
	// will be defined later.
	case TANY,
		TFORW:
		*bad = t

		return -1

	case TINT8,
		TUINT8,
		TINT16,
		TUINT16,
		TINT32,
		TUINT32,
		TINT64,
		TUINT64,
		TINT,
		TUINT,
		TUINTPTR,
		TBOOL,
		TPTR32,
		TPTR64,
		TCHAN,
		TUNSAFEPTR:
		return AMEM

	case TFUNC,
		TMAP:
		if bad != nil {
			*bad = t
		}
		return ANOEQ

	case TFLOAT32:
		return AFLOAT32

	case TFLOAT64:
		return AFLOAT64

	case TCOMPLEX64:
		return ACPLX64

	case TCOMPLEX128:
		return ACPLX128

	case TSTRING:
		return ASTRING

	case TINTER:
485
		if isnilinter(t) {
486 487 488 489 490
			return ANILINTER
		}
		return AINTER

	case TARRAY:
491
		if Isslice(t) {
492 493 494 495 496 497
			if bad != nil {
				*bad = t
			}
			return ANOEQ
		}

498
		a := algtype1(t.Type, bad)
499 500 501 502 503 504 505 506 507 508 509 510 511 512 513
		if a == ANOEQ || a == AMEM {
			if a == ANOEQ && bad != nil {
				*bad = t
			}
			return a
		}

		return -1 // needs special compare

	case TSTRUCT:
		if t.Type != nil && t.Type.Down == nil && !isblanksym(t.Type.Sym) {
			// One-field struct is same as that one field alone.
			return algtype1(t.Type.Type, bad)
		}

514 515 516
		ret := AMEM
		var a int
		for t1 := t.Type; t1 != nil; t1 = t1.Down {
517 518 519 520 521 522 523 524 525
			// All fields must be comparable.
			a = algtype1(t1.Type, bad)

			if a == ANOEQ {
				return ANOEQ
			}

			// Blank fields, padded fields, fields with non-memory
			// equality need special compare.
526
			if a != AMEM || isblanksym(t1.Sym) || ispaddedfield(t1, t.Width) {
527 528 529 530 531 532 533 534 535 536 537 538 539
				ret = -1
				continue
			}
		}

		return ret
	}

	Fatal("algtype1: unexpected type %v", Tconv(t, 0))
	return 0
}

func algtype(t *Type) int {
540
	a := algtype1(t, nil)
541
	if a == AMEM || a == ANOEQ {
542
		if Isslice(t) {
543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570
			return ASLICE
		}
		switch t.Width {
		case 0:
			return a + AMEM0 - AMEM

		case 1:
			return a + AMEM8 - AMEM

		case 2:
			return a + AMEM16 - AMEM

		case 4:
			return a + AMEM32 - AMEM

		case 8:
			return a + AMEM64 - AMEM

		case 16:
			return a + AMEM128 - AMEM
		}
	}

	return a
}

func maptype(key *Type, val *Type) *Type {
	if key != nil {
571 572 573
		var bad *Type
		atype := algtype1(key, &bad)
		var mtype int
574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601
		if bad == nil {
			mtype = int(key.Etype)
		} else {
			mtype = int(bad.Etype)
		}
		switch mtype {
		default:
			if atype == ANOEQ {
				Yyerror("invalid map key type %v", Tconv(key, 0))
			}

			// will be resolved later.
		case TANY:
			break

			// map[key] used during definition of key.
		// postpone check until key is fully defined.
		// if there are multiple uses of map[key]
		// before key is fully defined, the error
		// will only be printed for the first one.
		// good enough.
		case TFORW:
			if key.Maplineno == 0 {
				key.Maplineno = lineno
			}
		}
	}

602
	t := typ(TMAP)
603 604 605 606 607 608
	t.Down = key
	t.Type = val
	return t
}

func typ(et int) *Type {
609
	t := new(Type)
610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627
	t.Etype = uint8(et)
	t.Width = BADWIDTH
	t.Lineno = int(lineno)
	t.Orig = t
	return t
}

type methcmp []*Type

func (x methcmp) Len() int {
	return len(x)
}

func (x methcmp) Swap(i, j int) {
	x[i], x[j] = x[j], x[i]
}

func (x methcmp) Less(i, j int) bool {
628 629
	a := x[i]
	b := x[j]
630 631 632 633 634 635 636 637 638
	if a.Sym == nil && b.Sym == nil {
		return false
	}
	if a.Sym == nil {
		return true
	}
	if b.Sym == nil {
		return 1 < 0
	}
639
	k := stringsCompare(a.Sym.Name, b.Sym.Name)
640 641 642 643
	if k != 0 {
		return k < 0
	}
	if !exportname(a.Sym.Name) {
644
		k := stringsCompare(a.Sym.Pkg.Path, b.Sym.Pkg.Path)
645 646 647 648 649 650 651 652 653 654 655 656 657
		if k != 0 {
			return k < 0
		}
	}

	return false
}

func sortinter(t *Type) *Type {
	if t.Type == nil || t.Type.Down == nil {
		return t
	}

658 659
	i := 0
	for f := t.Type; f != nil; f = f.Down {
660 661
		i++
	}
662
	a := make([]*Type, i)
663
	i = 0
664
	var f *Type
665 666 667 668 669 670 671 672
	for f = t.Type; f != nil; f = f.Down {
		a[i] = f
		i++
	}
	sort.Sort(methcmp(a[:i]))
	for {
		tmp11 := i
		i--
673
		if tmp11 <= 0 {
674 675 676 677 678 679 680 681 682 683 684
			break
		}
		a[i].Down = f
		f = a[i]
	}

	t.Type = f
	return t
}

func Nodintconst(v int64) *Node {
685
	c := Nod(OLITERAL, nil, nil)
686 687 688 689 690 691 692 693 694 695
	c.Addable = 1
	c.Val.U.Xval = new(Mpint)
	Mpmovecfix(c.Val.U.Xval, v)
	c.Val.Ctype = CTINT
	c.Type = Types[TIDEAL]
	ullmancalc(c)
	return c
}

func nodfltconst(v *Mpflt) *Node {
696
	c := Nod(OLITERAL, nil, nil)
697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715
	c.Addable = 1
	c.Val.U.Fval = new(Mpflt)
	mpmovefltflt(c.Val.U.Fval, v)
	c.Val.Ctype = CTFLT
	c.Type = Types[TIDEAL]
	ullmancalc(c)
	return c
}

func Nodconst(n *Node, t *Type, v int64) {
	*n = Node{}
	n.Op = OLITERAL
	n.Addable = 1
	ullmancalc(n)
	n.Val.U.Xval = new(Mpint)
	Mpmovecfix(n.Val.U.Xval, v)
	n.Val.Ctype = CTINT
	n.Type = t

716
	if Isfloat[t.Etype] {
717 718 719 720 721
		Fatal("nodconst: bad type %v", Tconv(t, 0))
	}
}

func nodnil() *Node {
722
	c := Nodintconst(0)
723 724 725 726 727
	c.Val.Ctype = CTNIL
	c.Type = Types[TNIL]
	return c
}

728
func Nodbool(b bool) *Node {
729
	c := Nodintconst(0)
730
	c.Val.Ctype = CTBOOL
731
	c.Val.U.Bval = int16(bool2int(b))
732 733 734 735 736
	c.Type = idealbool
	return c
}

func aindex(b *Node, t *Type) *Type {
737
	bound := int64(-1) // open bound
738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753
	typecheck(&b, Erv)
	if b != nil {
		switch consttype(b) {
		default:
			Yyerror("array bound must be an integer expression")

		case CTINT,
			CTRUNE:
			bound = Mpgetfix(b.Val.U.Xval)
			if bound < 0 {
				Yyerror("array bound must be non negative")
			}
		}
	}

	// fixed array
754
	r := typ(TARRAY)
755 756 757 758 759 760 761 762 763 764 765

	r.Type = t
	r.Bound = bound
	return r
}

func treecopy(n *Node) *Node {
	if n == nil {
		return nil
	}

766
	var m *Node
767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802
	switch n.Op {
	default:
		m = Nod(OXXX, nil, nil)
		*m = *n
		m.Orig = m
		m.Left = treecopy(n.Left)
		m.Right = treecopy(n.Right)
		m.List = listtreecopy(n.List)
		if m.Defn != nil {
			panic("abort")
		}

	case ONONAME:
		if n.Sym == Lookup("iota") {
			// Not sure yet whether this is the real iota,
			// but make a copy of the Node* just in case,
			// so that all the copies of this const definition
			// don't have the same iota value.
			m = Nod(OXXX, nil, nil)

			*m = *n
			m.Iota = iota_
			break
		}
		fallthrough

		// fall through
	case ONAME,
		OLITERAL,
		OTYPE:
		m = n
	}

	return m
}

803
func isnil(n *Node) bool {
804
	if n == nil {
805
		return false
806 807
	}
	if n.Op != OLITERAL {
808
		return false
809 810
	}
	if n.Val.Ctype != CTNIL {
811
		return false
812
	}
813
	return true
814 815
}

816
func isptrto(t *Type, et int) bool {
817
	if t == nil {
818
		return false
819
	}
820
	if !Isptr[t.Etype] {
821
		return false
822 823 824
	}
	t = t.Type
	if t == nil {
825
		return false
826 827
	}
	if int(t.Etype) != et {
828
		return false
829
	}
830
	return true
831 832
}

833 834
func Istype(t *Type, et int) bool {
	return t != nil && int(t.Etype) == et
835 836
}

837 838
func Isfixedarray(t *Type) bool {
	return t != nil && t.Etype == TARRAY && t.Bound >= 0
839 840
}

841 842
func Isslice(t *Type) bool {
	return t != nil && t.Etype == TARRAY && t.Bound < 0
843 844 845 846 847 848 849 850 851 852 853 854 855
}

func isblank(n *Node) bool {
	if n == nil {
		return false
	}
	return isblanksym(n.Sym)
}

func isblanksym(s *Sym) bool {
	return s != nil && s.Name == "_"
}

856 857
func Isinter(t *Type) bool {
	return t != nil && t.Etype == TINTER
858 859
}

860 861 862
func isnilinter(t *Type) bool {
	if !Isinter(t) {
		return false
863 864
	}
	if t.Type != nil {
865
		return false
866
	}
867
	return true
868 869
}

870
func isideal(t *Type) bool {
871
	if t == nil {
872
		return false
873 874
	}
	if t == idealstring || t == idealbool {
875
		return true
876 877 878 879
	}
	switch t.Etype {
	case TNIL,
		TIDEAL:
880
		return true
881 882
	}

883
	return false
884 885 886 887 888 889 890 891 892 893 894 895
}

/*
 * given receiver of type t (t == r or t == *r)
 * return type to hang methods off (r).
 */
func methtype(t *Type, mustname int) *Type {
	if t == nil {
		return nil
	}

	// strip away pointer if it's there
896
	if Isptr[t.Etype] {
897 898 899 900 901 902 903 904 905 906 907 908 909 910 911
		if t.Sym != nil {
			return nil
		}
		t = t.Type
		if t == nil {
			return nil
		}
	}

	// need a type name
	if t.Sym == nil && (mustname != 0 || t.Etype != TSTRUCT) {
		return nil
	}

	// check types
912
	if !issimple[t.Etype] {
913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942
		switch t.Etype {
		default:
			return nil

		case TSTRUCT,
			TARRAY,
			TMAP,
			TCHAN,
			TSTRING,
			TFUNC:
			break
		}
	}

	return t
}

func cplxsubtype(et int) int {
	switch et {
	case TCOMPLEX64:
		return TFLOAT32

	case TCOMPLEX128:
		return TFLOAT64
	}

	Fatal("cplxsubtype: %v\n", Econv(int(et), 0))
	return 0
}

943 944
func eqnote(a, b *string) bool {
	return a == b || a != nil && b != nil && *a == *b
945 946 947 948 949 950 951 952
}

type TypePairList struct {
	t1   *Type
	t2   *Type
	next *TypePairList
}

953
func onlist(l *TypePairList, t1 *Type, t2 *Type) bool {
954 955
	for ; l != nil; l = l.next {
		if (l.t1 == t1 && l.t2 == t2) || (l.t1 == t2 && l.t2 == t1) {
956
			return true
957 958
		}
	}
959
	return false
960 961 962 963 964 965 966 967 968
}

// Return 1 if t1 and t2 are identical, following the spec rules.
//
// Any cyclic type must go through a named type, and if one is
// named, it is only identical to the other if they are the same
// pointer (t1 == t2), so there's no chance of chasing cycles
// ad infinitum, so no need for a depth counter.
func Eqtype(t1 *Type, t2 *Type) bool {
969
	return eqtype1(t1, t2, nil)
970 971
}

972
func eqtype1(t1 *Type, t2 *Type, assumed_equal *TypePairList) bool {
973
	if t1 == t2 {
974
		return true
975 976
	}
	if t1 == nil || t2 == nil || t1.Etype != t2.Etype {
977
		return false
978 979 980 981 982 983 984
	}
	if t1.Sym != nil || t2.Sym != nil {
		// Special case: we keep byte and uint8 separate
		// for error messages.  Treat them as equal.
		switch t1.Etype {
		case TUINT8:
			if (t1 == Types[TUINT8] || t1 == bytetype) && (t2 == Types[TUINT8] || t2 == bytetype) {
985
				return true
986 987 988 989 990
			}

		case TINT,
			TINT32:
			if (t1 == Types[runetype.Etype] || t1 == runetype) && (t2 == Types[runetype.Etype] || t2 == runetype) {
991
				return true
992 993 994
			}
		}

995
		return false
996 997
	}

998 999
	if onlist(assumed_equal, t1, t2) {
		return true
1000
	}
1001
	var l TypePairList
1002 1003 1004 1005 1006 1007 1008 1009 1010
	l.next = assumed_equal
	l.t1 = t1
	l.t2 = t2

	switch t1.Etype {
	case TINTER,
		TSTRUCT:
		t1 = t1.Type
		t2 = t2.Type
1011
		for ; t1 != nil && t2 != nil; t1, t2 = t1.Down, t2.Down {
1012 1013 1014
			if t1.Etype != TFIELD || t2.Etype != TFIELD {
				Fatal("struct/interface missing field: %v %v", Tconv(t1, 0), Tconv(t2, 0))
			}
1015
			if t1.Sym != t2.Sym || t1.Embedded != t2.Embedded || !eqtype1(t1.Type, t2.Type, &l) || !eqnote(t1.Note, t2.Note) {
Russ Cox's avatar
Russ Cox committed
1016
				return false
1017 1018 1019 1020
			}
		}

		if t1 == nil && t2 == nil {
Russ Cox's avatar
Russ Cox committed
1021
			return true
1022
		}
Russ Cox's avatar
Russ Cox committed
1023
		return false
1024 1025 1026 1027 1028

		// Loop over structs: receiver, in, out.
	case TFUNC:
		t1 = t1.Type
		t2 = t2.Type
1029
		for ; t1 != nil && t2 != nil; t1, t2 = t1.Down, t2.Down {
1030 1031 1032 1033 1034
			if t1.Etype != TSTRUCT || t2.Etype != TSTRUCT {
				Fatal("func missing struct: %v %v", Tconv(t1, 0), Tconv(t2, 0))
			}

			// Loop over fields in structs, ignoring argument names.
1035 1036
			ta := t1.Type
			tb := t2.Type
1037
			for ; ta != nil && tb != nil; ta, tb = ta.Down, tb.Down {
1038 1039 1040
				if ta.Etype != TFIELD || tb.Etype != TFIELD {
					Fatal("func struct missing field: %v %v", Tconv(ta, 0), Tconv(tb, 0))
				}
1041
				if ta.Isddd != tb.Isddd || !eqtype1(ta.Type, tb.Type, &l) {
Russ Cox's avatar
Russ Cox committed
1042
					return false
1043 1044 1045 1046
				}
			}

			if ta != nil || tb != nil {
Russ Cox's avatar
Russ Cox committed
1047
				return false
1048 1049 1050 1051
			}
		}

		if t1 == nil && t2 == nil {
Russ Cox's avatar
Russ Cox committed
1052
			return true
1053
		}
Russ Cox's avatar
Russ Cox committed
1054
		return false
1055 1056 1057

	case TARRAY:
		if t1.Bound != t2.Bound {
Russ Cox's avatar
Russ Cox committed
1058
			return false
1059 1060 1061 1062
		}

	case TCHAN:
		if t1.Chan != t2.Chan {
Russ Cox's avatar
Russ Cox committed
1063
			return false
1064 1065 1066
		}
	}

1067
	if eqtype1(t1.Down, t2.Down, &l) && eqtype1(t1.Type, t2.Type, &l) {
Russ Cox's avatar
Russ Cox committed
1068
		return true
1069
	}
1070
	return false
1071 1072 1073 1074 1075
}

// Are t1 and t2 equal struct types when field names are ignored?
// For deciding whether the result struct from g can be copied
// directly when compiling f(g()).
1076
func eqtypenoname(t1 *Type, t2 *Type) bool {
1077
	if t1 == nil || t2 == nil || t1.Etype != TSTRUCT || t2.Etype != TSTRUCT {
1078
		return false
1079 1080 1081 1082 1083 1084
	}

	t1 = t1.Type
	t2 = t2.Type
	for {
		if !Eqtype(t1, t2) {
1085
			return false
1086 1087
		}
		if t1 == nil {
1088
			return true
1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126
		}
		t1 = t1.Down
		t2 = t2.Down
	}
}

// Is type src assignment compatible to type dst?
// If so, return op code to use in conversion.
// If not, return 0.
func assignop(src *Type, dst *Type, why *string) int {
	if why != nil {
		*why = ""
	}

	// TODO(rsc,lvd): This behaves poorly in the presence of inlining.
	// https://golang.org/issue/2795
	if safemode != 0 && importpkg == nil && src != nil && src.Etype == TUNSAFEPTR {
		Yyerror("cannot use unsafe.Pointer")
		errorexit()
	}

	if src == dst {
		return OCONVNOP
	}
	if src == nil || dst == nil || src.Etype == TFORW || dst.Etype == TFORW || src.Orig == nil || dst.Orig == nil {
		return 0
	}

	// 1. src type is identical to dst.
	if Eqtype(src, dst) {
		return OCONVNOP
	}

	// 2. src and dst have identical underlying types
	// and either src or dst is not a named type or
	// both are empty interface types.
	// For assignable but different non-empty interface types,
	// we want to recompute the itab.
1127
	if Eqtype(src.Orig, dst.Orig) && (src.Sym == nil || dst.Sym == nil || isnilinter(src)) {
1128 1129 1130 1131 1132
		return OCONVNOP
	}

	// 3. dst is an interface type and src implements dst.
	if dst.Etype == TINTER && src.Etype != TNIL {
1133 1134 1135
		var missing *Type
		var ptr int
		var have *Type
1136
		if implements(src, dst, &missing, &have, &ptr) {
1137 1138 1139 1140 1141 1142 1143 1144 1145
			return OCONVIFACE
		}

		// we'll have complained about this method anyway, suppress spurious messages.
		if have != nil && have.Sym == missing.Sym && (have.Type.Broke != 0 || missing.Type.Broke != 0) {
			return OCONVIFACE
		}

		if why != nil {
1146
			if isptrto(src, TINTER) {
1147
				*why = fmt.Sprintf(":\n\t%v is pointer to interface, not interface", Tconv(src, 0))
1148
			} else if have != nil && have.Sym == missing.Sym && have.Nointerface {
1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163
				*why = fmt.Sprintf(":\n\t%v does not implement %v (%v method is marked 'nointerface')", Tconv(src, 0), Tconv(dst, 0), Sconv(missing.Sym, 0))
			} else if have != nil && have.Sym == missing.Sym {
				*why = fmt.Sprintf(":\n\t%v does not implement %v (wrong type for %v method)\n"+"\t\thave %v%v\n\t\twant %v%v", Tconv(src, 0), Tconv(dst, 0), Sconv(missing.Sym, 0), Sconv(have.Sym, 0), Tconv(have.Type, obj.FmtShort|obj.FmtByte), Sconv(missing.Sym, 0), Tconv(missing.Type, obj.FmtShort|obj.FmtByte))
			} else if ptr != 0 {
				*why = fmt.Sprintf(":\n\t%v does not implement %v (%v method has pointer receiver)", Tconv(src, 0), Tconv(dst, 0), Sconv(missing.Sym, 0))
			} else if have != nil {
				*why = fmt.Sprintf(":\n\t%v does not implement %v (missing %v method)\n"+"\t\thave %v%v\n\t\twant %v%v", Tconv(src, 0), Tconv(dst, 0), Sconv(missing.Sym, 0), Sconv(have.Sym, 0), Tconv(have.Type, obj.FmtShort|obj.FmtByte), Sconv(missing.Sym, 0), Tconv(missing.Type, obj.FmtShort|obj.FmtByte))
			} else {
				*why = fmt.Sprintf(":\n\t%v does not implement %v (missing %v method)", Tconv(src, 0), Tconv(dst, 0), Sconv(missing.Sym, 0))
			}
		}

		return 0
	}

1164
	if isptrto(dst, TINTER) {
1165 1166 1167 1168 1169 1170 1171
		if why != nil {
			*why = fmt.Sprintf(":\n\t%v is pointer to interface, not interface", Tconv(dst, 0))
		}
		return 0
	}

	if src.Etype == TINTER && dst.Etype != TBLANK {
1172 1173 1174
		var have *Type
		var ptr int
		var missing *Type
1175
		if why != nil && implements(dst, src, &missing, &have, &ptr) {
1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234
			*why = ": need type assertion"
		}
		return 0
	}

	// 4. src is a bidirectional channel value, dst is a channel type,
	// src and dst have identical element types, and
	// either src or dst is not a named type.
	if src.Etype == TCHAN && src.Chan == Cboth && dst.Etype == TCHAN {
		if Eqtype(src.Type, dst.Type) && (src.Sym == nil || dst.Sym == nil) {
			return OCONVNOP
		}
	}

	// 5. src is the predeclared identifier nil and dst is a nillable type.
	if src.Etype == TNIL {
		switch dst.Etype {
		case TARRAY:
			if dst.Bound != -100 { // not slice
				break
			}
			fallthrough

		case TPTR32,
			TPTR64,
			TFUNC,
			TMAP,
			TCHAN,
			TINTER:
			return OCONVNOP
		}
	}

	// 6. rule about untyped constants - already converted by defaultlit.

	// 7. Any typed value can be assigned to the blank identifier.
	if dst.Etype == TBLANK {
		return OCONVNOP
	}

	return 0
}

// Can we convert a value of type src to a value of type dst?
// If so, return op code to use in conversion (maybe OCONVNOP).
// If not, return 0.
func convertop(src *Type, dst *Type, why *string) int {
	if why != nil {
		*why = ""
	}

	if src == dst {
		return OCONVNOP
	}
	if src == nil || dst == nil {
		return 0
	}

	// 1. src can be assigned to dst.
1235
	op := assignop(src, dst, why)
1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257
	if op != 0 {
		return op
	}

	// The rules for interfaces are no different in conversions
	// than assignments.  If interfaces are involved, stop now
	// with the good message from assignop.
	// Otherwise clear the error.
	if src.Etype == TINTER || dst.Etype == TINTER {
		return 0
	}
	if why != nil {
		*why = ""
	}

	// 2. src and dst have identical underlying types.
	if Eqtype(src.Orig, dst.Orig) {
		return OCONVNOP
	}

	// 3. src and dst are unnamed pointer types
	// and their base types have identical underlying types.
1258
	if Isptr[src.Etype] && Isptr[dst.Etype] && src.Sym == nil && dst.Sym == nil {
1259 1260 1261 1262 1263 1264
		if Eqtype(src.Type.Orig, dst.Type.Orig) {
			return OCONVNOP
		}
	}

	// 4. src and dst are both integer or floating point types.
1265
	if (Isint[src.Etype] || Isfloat[src.Etype]) && (Isint[dst.Etype] || Isfloat[dst.Etype]) {
1266 1267 1268 1269 1270 1271 1272
		if Simtype[src.Etype] == Simtype[dst.Etype] {
			return OCONVNOP
		}
		return OCONV
	}

	// 5. src and dst are both complex types.
1273
	if Iscomplex[src.Etype] && Iscomplex[dst.Etype] {
1274 1275 1276 1277 1278 1279 1280 1281
		if Simtype[src.Etype] == Simtype[dst.Etype] {
			return OCONVNOP
		}
		return OCONV
	}

	// 6. src is an integer or has type []byte or []rune
	// and dst is a string type.
1282
	if Isint[src.Etype] && dst.Etype == TSTRING {
1283 1284 1285
		return ORUNESTR
	}

1286
	if Isslice(src) && dst.Etype == TSTRING {
1287 1288 1289 1290 1291 1292 1293 1294 1295 1296
		if src.Type.Etype == bytetype.Etype {
			return OARRAYBYTESTR
		}
		if src.Type.Etype == runetype.Etype {
			return OARRAYRUNESTR
		}
	}

	// 7. src is a string and dst is []byte or []rune.
	// String to slice.
1297
	if src.Etype == TSTRING && Isslice(dst) {
1298 1299 1300 1301 1302 1303 1304 1305 1306
		if dst.Type.Etype == bytetype.Etype {
			return OSTRARRAYBYTE
		}
		if dst.Type.Etype == runetype.Etype {
			return OSTRARRAYRUNE
		}
	}

	// 8. src is a pointer or uintptr and dst is unsafe.Pointer.
1307
	if (Isptr[src.Etype] || src.Etype == TUINTPTR) && dst.Etype == TUNSAFEPTR {
1308 1309 1310 1311
		return OCONVNOP
	}

	// 9. src is unsafe.Pointer and dst is a pointer or uintptr.
1312
	if src.Etype == TUNSAFEPTR && (Isptr[dst.Etype] || dst.Etype == TUINTPTR) {
1313 1314 1315 1316 1317 1318 1319
		return OCONVNOP
	}

	return 0
}

func assignconv(n *Node, t *Type, context string) *Node {
1320 1321 1322 1323 1324
	return assignconvfn(n, t, func() string { return context })
}

// Convert node n for assignment to type t.
func assignconvfn(n *Node, t *Type, context func() string) *Node {
1325 1326 1327 1328 1329 1330 1331 1332
	if n == nil || n.Type == nil || n.Type.Broke != 0 {
		return n
	}

	if t.Etype == TBLANK && n.Type.Etype == TNIL {
		Yyerror("use of untyped nil")
	}

1333
	old := n
1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344
	old.Diag++ // silence errors about n; we'll issue one below
	defaultlit(&n, t)
	old.Diag--
	if t.Etype == TBLANK {
		return n
	}

	// Convert ideal bool from comparison to plain bool
	// if the next step is non-bool (like interface{}).
	if n.Type == idealbool && t.Etype != TBOOL {
		if n.Op == ONAME || n.Op == OLITERAL {
1345
			r := Nod(OCONVNOP, n, nil)
1346 1347
			r.Type = Types[TBOOL]
			r.Typecheck = 1
1348
			r.Implicit = true
1349 1350 1351 1352 1353 1354 1355 1356
			n = r
		}
	}

	if Eqtype(n.Type, t) {
		return n
	}

1357 1358
	var why string
	op := assignop(n.Type, t, &why)
1359
	if op == 0 {
1360
		Yyerror("cannot use %v as type %v in %s%s", Nconv(n, obj.FmtLong), Tconv(t, 0), context(), why)
1361 1362 1363
		op = OCONV
	}

1364
	r := Nod(op, n, nil)
1365 1366
	r.Type = t
	r.Typecheck = 1
1367
	r.Implicit = true
1368 1369 1370 1371
	r.Orig = n.Orig
	return r
}

1372 1373 1374 1375 1376 1377
// substArgTypes substitutes the given list of types for
// successive occurrences of the "any" placeholder in the
// type syntax expression n.Type.
func substArgTypes(n *Node, types ...*Type) {
	for _, t := range types {
		dowidth(t)
1378
	}
1379 1380 1381
	substAny(&n.Type, &types)
	if len(types) > 0 {
		Fatal("substArgTypes: too many argument types")
1382
	}
1383
}
1384

1385 1386 1387 1388 1389 1390 1391
// substAny walks *tp, replacing instances of "any" with successive
// elements removed from types.
func substAny(tp **Type, types *[]*Type) {
	for {
		t := *tp
		if t == nil {
			return
1392
		}
1393 1394 1395
		if t.Etype == TANY && t.Copyany != 0 {
			if len(*types) == 0 {
				Fatal("substArgTypes: not enough argument types")
1396
			}
1397 1398
			*tp = (*types)[0]
			*types = (*types)[1:]
1399 1400
		}

1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418
		switch t.Etype {
		case TPTR32, TPTR64, TCHAN, TARRAY:
			tp = &t.Type
			continue

		case TMAP:
			substAny(&t.Down, types)
			tp = &t.Type
			continue

		case TFUNC:
			substAny(&t.Type, types)
			substAny(&t.Type.Down.Down, types)
			substAny(&t.Type.Down, types)

		case TSTRUCT:
			for t = t.Type; t != nil; t = t.Down {
				substAny(&t.Type, types)
1419 1420
			}
		}
1421
		return
1422 1423 1424 1425 1426 1427
	}
}

/*
 * Is this a 64-bit type?
 */
1428
func Is64(t *Type) bool {
1429
	if t == nil {
1430
		return false
1431 1432 1433 1434 1435
	}
	switch Simtype[t.Etype] {
	case TINT64,
		TUINT64,
		TPTR64:
1436
		return true
1437 1438
	}

1439
	return false
1440 1441 1442 1443 1444
}

/*
 * Is a conversion between t1 and t2 a no-op?
 */
1445
func Noconv(t1 *Type, t2 *Type) bool {
1446 1447
	e1 := int(Simtype[t1.Etype])
	e2 := int(Simtype[t2.Etype])
1448 1449 1450 1451

	switch e1 {
	case TINT8,
		TUINT8:
1452
		return e2 == TINT8 || e2 == TUINT8
1453 1454 1455

	case TINT16,
		TUINT16:
1456
		return e2 == TINT16 || e2 == TUINT16
1457 1458 1459 1460

	case TINT32,
		TUINT32,
		TPTR32:
1461
		return e2 == TINT32 || e2 == TUINT32 || e2 == TPTR32
1462 1463 1464 1465

	case TINT64,
		TUINT64,
		TPTR64:
1466
		return e2 == TINT64 || e2 == TUINT64 || e2 == TPTR64
1467 1468

	case TFLOAT32:
1469
		return e2 == TFLOAT32
1470 1471

	case TFLOAT64:
1472
		return e2 == TFLOAT64
1473 1474
	}

1475
	return false
1476 1477 1478 1479 1480 1481
}

func shallow(t *Type) *Type {
	if t == nil {
		return nil
	}
1482
	nt := typ(0)
1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494
	*nt = *t
	if t.Orig == t {
		nt.Orig = nt
	}
	return nt
}

func deep(t *Type) *Type {
	if t == nil {
		return nil
	}

1495
	var nt *Type
1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524
	switch t.Etype {
	default:
		nt = t // share from here down

	case TANY:
		nt = shallow(t)
		nt.Copyany = 1

	case TPTR32,
		TPTR64,
		TCHAN,
		TARRAY:
		nt = shallow(t)
		nt.Type = deep(t.Type)

	case TMAP:
		nt = shallow(t)
		nt.Down = deep(t.Down)
		nt.Type = deep(t.Type)

	case TFUNC:
		nt = shallow(t)
		nt.Type = deep(t.Type)
		nt.Type.Down = deep(t.Type.Down)
		nt.Type.Down.Down = deep(t.Type.Down.Down)

	case TSTRUCT:
		nt = shallow(t)
		nt.Type = shallow(t.Type)
1525
		xt := nt.Type
1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537

		for t = t.Type; t != nil; t = t.Down {
			xt.Type = deep(t.Type)
			xt.Down = shallow(t.Down)
			xt = xt.Down
		}
	}

	return nt
}

func syslook(name string, copy int) *Node {
1538
	s := Pkglookup(name, Runtimepkg)
1539 1540 1541 1542
	if s == nil || s.Def == nil {
		Fatal("syslook: can't find runtime.%s", name)
	}

1543
	if copy == 0 {
1544 1545 1546
		return s.Def
	}

1547
	n := Nod(0, nil, nil)
1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572
	*n = *s.Def
	n.Type = deep(s.Def.Type)

	return n
}

/*
 * compute a hash value for type t.
 * if t is a method type, ignore the receiver
 * so that the hash can be used in interface checks.
 * %T already contains
 * all the necessary logic to generate a representation
 * of the type that completely describes it.
 * using smprint here avoids duplicating that code.
 * using md5 here is overkill, but i got tired of
 * accidental collisions making the runtime think
 * two types are equal when they really aren't.
 */
func typehash(t *Type) uint32 {
	var p string

	if t.Thistuple != 0 {
		// hide method receiver from Tpretty
		t.Thistuple = 0

1573
		p = Tconv(t, obj.FmtLeft|obj.FmtUnsigned)
1574 1575
		t.Thistuple = 1
	} else {
1576
		p = Tconv(t, obj.FmtLeft|obj.FmtUnsigned)
1577 1578 1579
	}

	//print("typehash: %s\n", p);
1580 1581
	h := md5.Sum([]byte(p))
	return binary.LittleEndian.Uint32(h[:4])
1582 1583 1584 1585 1586 1587
}

func Ptrto(t *Type) *Type {
	if Tptr == 0 {
		Fatal("ptrto: no tptr")
	}
1588
	t1 := typ(Tptr)
1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607
	t1.Type = t
	t1.Width = int64(Widthptr)
	t1.Align = uint8(Widthptr)
	return t1
}

func frame(context int) {
	var l *NodeList

	if context != 0 {
		fmt.Printf("--- external frame ---\n")
		l = externdcl
	} else if Curfn != nil {
		fmt.Printf("--- %v frame ---\n", Sconv(Curfn.Nname.Sym, 0))
		l = Curfn.Dcl
	} else {
		return
	}

1608 1609
	var n *Node
	var w int64
1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636
	for ; l != nil; l = l.Next {
		n = l.N
		w = -1
		if n.Type != nil {
			w = n.Type.Width
		}
		switch n.Op {
		case ONAME:
			fmt.Printf("%v %v G%d %v width=%d\n", Oconv(int(n.Op), 0), Sconv(n.Sym, 0), n.Vargen, Tconv(n.Type, 0), w)

		case OTYPE:
			fmt.Printf("%v %v width=%d\n", Oconv(int(n.Op), 0), Tconv(n.Type, 0), w)
		}
	}
}

/*
 * calculate sethi/ullman number
 * roughly how many registers needed to
 * compile a node. used to compile the
 * hardest side first to minimize registers.
 */
func ullmancalc(n *Node) {
	if n == nil {
		return
	}

1637 1638
	var ul int
	var ur int
1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692
	if n.Ninit != nil {
		ul = UINF
		goto out
	}

	switch n.Op {
	case OREGISTER,
		OLITERAL,
		ONAME:
		ul = 1
		if n.Class == PPARAMREF || (n.Class&PHEAP != 0) {
			ul++
		}
		goto out

	case OCALL,
		OCALLFUNC,
		OCALLMETH,
		OCALLINTER:
		ul = UINF
		goto out

		// hard with race detector
	case OANDAND,
		OOROR:
		if flag_race != 0 {
			ul = UINF
			goto out
		}
	}

	ul = 1
	if n.Left != nil {
		ul = int(n.Left.Ullman)
	}
	ur = 1
	if n.Right != nil {
		ur = int(n.Right.Ullman)
	}
	if ul == ur {
		ul += 1
	}
	if ur > ul {
		ul = ur
	}

out:
	if ul > 200 {
		ul = 200 // clamp to uchar with room to grow
	}
	n.Ullman = uint8(ul)
}

func badtype(o int, tl *Type, tr *Type) {
1693
	fmt_ := ""
1694 1695 1696 1697 1698 1699 1700 1701
	if tl != nil {
		fmt_ += fmt.Sprintf("\n\t%v", Tconv(tl, 0))
	}
	if tr != nil {
		fmt_ += fmt.Sprintf("\n\t%v", Tconv(tr, 0))
	}

	// common mistake: *struct and *interface.
1702
	if tl != nil && tr != nil && Isptr[tl.Etype] && Isptr[tr.Etype] {
1703
		if tl.Type.Etype == TSTRUCT && tr.Type.Etype == TINTER {
1704
			fmt_ += "\n\t(*struct vs *interface)"
1705
		} else if tl.Type.Etype == TINTER && tr.Type.Etype == TSTRUCT {
1706
			fmt_ += "\n\t(*interface vs *struct)"
1707 1708 1709
		}
	}

1710
	s := fmt_
1711 1712 1713 1714 1715 1716 1717 1718 1719
	Yyerror("illegal types for operand: %v%s", Oconv(int(o), 0), s)
}

/*
 * iterator to walk a structure declaration
 */
func Structfirst(s *Iter, nn **Type) *Type {
	var t *Type

1720
	n := *nn
1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736
	if n == nil {
		goto bad
	}

	switch n.Etype {
	default:
		goto bad

	case TSTRUCT,
		TINTER,
		TFUNC:
		break
	}

	t = n.Type
	if t == nil {
Russ Cox's avatar
Russ Cox committed
1737
		return nil
1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753
	}

	if t.Etype != TFIELD {
		Fatal("structfirst: not field %v", Tconv(t, 0))
	}

	s.T = t
	return t

bad:
	Fatal("structfirst: not struct %v", Tconv(n, 0))

	return nil
}

func structnext(s *Iter) *Type {
1754 1755
	n := s.T
	t := n.Down
1756
	if t == nil {
Russ Cox's avatar
Russ Cox committed
1757
		return nil
1758 1759 1760
	}

	if t.Etype != TFIELD {
Russ Cox's avatar
Russ Cox committed
1761 1762 1763
		Fatal("structnext: not struct %v", Tconv(n, 0))

		return nil
1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799
	}

	s.T = t
	return t
}

/*
 * iterator to this and inargs in a function
 */
func funcfirst(s *Iter, t *Type) *Type {
	var fp *Type

	if t == nil {
		goto bad
	}

	if t.Etype != TFUNC {
		goto bad
	}

	s.Tfunc = t
	s.Done = 0
	fp = Structfirst(s, getthis(t))
	if fp == nil {
		s.Done = 1
		fp = Structfirst(s, getinarg(t))
	}

	return fp

bad:
	Fatal("funcfirst: not func %v", Tconv(t, 0))
	return nil
}

func funcnext(s *Iter) *Type {
1800
	fp := structnext(s)
1801
	if fp == nil && s.Done == 0 {
1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910
		s.Done = 1
		fp = Structfirst(s, getinarg(s.Tfunc))
	}

	return fp
}

func getthis(t *Type) **Type {
	if t.Etype != TFUNC {
		Fatal("getthis: not a func %v", Tconv(t, 0))
	}
	return &t.Type
}

func Getoutarg(t *Type) **Type {
	if t.Etype != TFUNC {
		Fatal("getoutarg: not a func %v", Tconv(t, 0))
	}
	return &t.Type.Down
}

func getinarg(t *Type) **Type {
	if t.Etype != TFUNC {
		Fatal("getinarg: not a func %v", Tconv(t, 0))
	}
	return &t.Type.Down.Down
}

func getthisx(t *Type) *Type {
	return *getthis(t)
}

func getoutargx(t *Type) *Type {
	return *Getoutarg(t)
}

func getinargx(t *Type) *Type {
	return *getinarg(t)
}

/*
 * return !(op)
 * eg == <=> !=
 */
func Brcom(a int) int {
	switch a {
	case OEQ:
		return ONE
	case ONE:
		return OEQ
	case OLT:
		return OGE
	case OGT:
		return OLE
	case OLE:
		return OGT
	case OGE:
		return OLT
	}

	Fatal("brcom: no com for %v\n", Oconv(int(a), 0))
	return a
}

/*
 * return reverse(op)
 * eg a op b <=> b r(op) a
 */
func Brrev(a int) int {
	switch a {
	case OEQ:
		return OEQ
	case ONE:
		return ONE
	case OLT:
		return OGT
	case OGT:
		return OLT
	case OLE:
		return OGE
	case OGE:
		return OLE
	}

	Fatal("brcom: no rev for %v\n", Oconv(int(a), 0))
	return a
}

/*
 * return side effect-free n, appending side effects to init.
 * result is assignable if n is.
 */
func safeexpr(n *Node, init **NodeList) *Node {
	if n == nil {
		return nil
	}

	if n.Ninit != nil {
		walkstmtlist(n.Ninit)
		*init = concat(*init, n.Ninit)
		n.Ninit = nil
	}

	switch n.Op {
	case ONAME,
		OLITERAL:
		return n

	case ODOT:
1911
		l := safeexpr(n.Left, init)
1912 1913 1914
		if l == n.Left {
			return n
		}
1915
		r := Nod(OXXX, nil, nil)
1916 1917 1918 1919 1920 1921 1922 1923
		*r = *n
		r.Left = l
		typecheck(&r, Erv)
		walkexpr(&r, init)
		return r

	case ODOTPTR,
		OIND:
1924
		l := safeexpr(n.Left, init)
1925 1926 1927
		if l == n.Left {
			return n
		}
1928
		a := Nod(OXXX, nil, nil)
1929 1930 1931 1932 1933 1934 1935
		*a = *n
		a.Left = l
		walkexpr(&a, init)
		return a

	case OINDEX,
		OINDEXMAP:
1936 1937
		l := safeexpr(n.Left, init)
		r := safeexpr(n.Right, init)
1938 1939 1940
		if l == n.Left && r == n.Right {
			return n
		}
1941
		a := Nod(OXXX, nil, nil)
1942 1943 1944 1945 1946 1947 1948 1949
		*a = *n
		a.Left = l
		a.Right = r
		walkexpr(&a, init)
		return a
	}

	// make a copy; must not be used as an lvalue
1950
	if islvalue(n) {
1951 1952 1953 1954 1955 1956
		Fatal("missing lvalue case in safeexpr: %v", Nconv(n, 0))
	}
	return cheapexpr(n, init)
}

func copyexpr(n *Node, t *Type, init **NodeList) *Node {
1957 1958
	l := temp(t)
	a := Nod(OAS, l, n)
1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984
	typecheck(&a, Etop)
	walkexpr(&a, init)
	*init = list(*init, a)
	return l
}

/*
 * return side-effect free and cheap n, appending side effects to init.
 * result may not be assignable.
 */
func cheapexpr(n *Node, init **NodeList) *Node {
	switch n.Op {
	case ONAME,
		OLITERAL:
		return n
	}

	return copyexpr(n, n.Type, init)
}

/*
 * return n in a local variable of type t if it is not already.
 * the value is guaranteed not to change except by direct
 * assignment to it.
 */
func localexpr(n *Node, t *Type, init **NodeList) *Node {
1985
	if n.Op == ONAME && (!n.Addrtaken || strings.HasPrefix(n.Sym.Name, "autotmp_")) && (n.Class == PAUTO || n.Class == PPARAM || n.Class == PPARAMOUT) && convertop(n.Type, t, nil) == OCONVNOP {
1986 1987 1988 1989 1990 1991 1992 1993
		return n
	}

	return copyexpr(n, t, init)
}

func Setmaxarg(t *Type, extra int32) {
	dowidth(t)
1994
	w := t.Argwid
1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019
	if w >= Thearch.MAXWIDTH {
		Fatal("bad argwid %v", Tconv(t, 0))
	}
	w += int64(extra)
	if w >= Thearch.MAXWIDTH {
		Fatal("bad argwid %d + %v", extra, Tconv(t, 0))
	}
	if w > Maxarg {
		Maxarg = w
	}
}

/*
 * unicode-aware case-insensitive strcmp
 */

/*
 * code to resolve elided DOTs
 * in embedded types
 */

// search depth 0 --
// return count of fields+methods
// found with a given name
func lookdot0(s *Sym, t *Type, save **Type, ignorecase int) int {
2020
	u := t
2021
	if Isptr[u.Etype] {
2022 2023 2024
		u = u.Type
	}

2025
	c := 0
2026
	if u.Etype == TSTRUCT || u.Etype == TINTER {
2027
		for f := u.Type; f != nil; f = f.Down {
2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038
			if f.Sym == s || (ignorecase != 0 && f.Type.Etype == TFUNC && f.Type.Thistuple > 0 && strings.EqualFold(f.Sym.Name, s.Name)) {
				if save != nil {
					*save = f
				}
				c++
			}
		}
	}

	u = methtype(t, 0)
	if u != nil {
2039
		for f := u.Method; f != nil; f = f.Down {
2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062
			if f.Embedded == 0 && (f.Sym == s || (ignorecase != 0 && strings.EqualFold(f.Sym.Name, s.Name))) {
				if save != nil {
					*save = f
				}
				c++
			}
		}
	}

	return c
}

// search depth d for field/method s --
// return count of fields+methods
// found at search depth.
// answer is in dotlist array and
// count of number of ways is returned.
func adddot1(s *Sym, t *Type, d int, save **Type, ignorecase int) int {
	if t.Trecur != 0 {
		return 0
	}
	t.Trecur = 1

2063 2064 2065
	var c int
	var u *Type
	var a int
2066 2067 2068 2069 2070 2071 2072
	if d == 0 {
		c = lookdot0(s, t, save, ignorecase)
		goto out
	}

	c = 0
	u = t
2073
	if Isptr[u.Etype] {
2074 2075 2076 2077 2078 2079 2080
		u = u.Type
	}
	if u.Etype != TSTRUCT && u.Etype != TINTER {
		goto out
	}

	d--
2081
	for f := u.Type; f != nil; f = f.Down {
2082
		if f.Embedded == 0 {
2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106
			continue
		}
		if f.Sym == nil {
			continue
		}
		a = adddot1(s, f.Type, d, save, ignorecase)
		if a != 0 && c == 0 {
			dotlist[d].field = f
		}
		c += a
	}

out:
	t.Trecur = 0
	return c
}

// in T.field
// find missing fields that
// will give shortest unique addressing.
// modify the tree with missing type names.
func adddot(n *Node) *Node {
	typecheck(&n.Left, Etype|Erv)
	n.Diag |= n.Left.Diag
2107
	t := n.Left.Type
2108
	if t == nil {
Russ Cox's avatar
Russ Cox committed
2109
		return n
2110 2111 2112
	}

	if n.Left.Op == OTYPE {
Russ Cox's avatar
Russ Cox committed
2113
		return n
2114 2115 2116
	}

	if n.Right.Op != ONAME {
Russ Cox's avatar
Russ Cox committed
2117
		return n
2118
	}
Russ Cox's avatar
Russ Cox committed
2119
	s := n.Right.Sym
2120
	if s == nil {
Russ Cox's avatar
Russ Cox committed
2121
		return n
2122 2123
	}

Russ Cox's avatar
Russ Cox committed
2124 2125
	var c int
	for d := 0; d < len(dotlist); d++ {
2126 2127
		c = adddot1(s, t, d, nil, 0)
		if c > 0 {
Russ Cox's avatar
Russ Cox committed
2128 2129 2130 2131 2132
			if c > 1 {
				Yyerror("ambiguous selector %v", Nconv(n, 0))
				n.Left = nil
				return n
			}
2133

Russ Cox's avatar
Russ Cox committed
2134 2135
			// rebuild elided dots
			for c := d - 1; c >= 0; c-- {
2136
				if n.Left.Type != nil && Isptr[n.Left.Type.Etype] {
2137
					n.Left.Implicit = true
Russ Cox's avatar
Russ Cox committed
2138 2139 2140
				}
				n.Left = Nod(ODOT, n.Left, newname(dotlist[c].field.Sym))
			}
2141

Russ Cox's avatar
Russ Cox committed
2142
			return n
2143
		}
2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168
	}

	return n
}

/*
 * code to help generate trampoline
 * functions for methods on embedded
 * subtypes.
 * these are approx the same as
 * the corresponding adddot routines
 * except that they expect to be called
 * with unique tasks and they return
 * the actual methods.
 */
type Symlink struct {
	field     *Type
	good      uint8
	followptr uint8
	link      *Symlink
}

var slist *Symlink

func expand0(t *Type, followptr int) {
2169
	u := t
2170
	if Isptr[u.Etype] {
2171 2172 2173 2174 2175
		followptr = 1
		u = u.Type
	}

	if u.Etype == TINTER {
2176 2177
		var sl *Symlink
		for f := u.Type; f != nil; f = f.Down {
2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193
			if f.Sym.Flags&SymUniq != 0 {
				continue
			}
			f.Sym.Flags |= SymUniq
			sl = new(Symlink)
			sl.field = f
			sl.link = slist
			sl.followptr = uint8(followptr)
			slist = sl
		}

		return
	}

	u = methtype(t, 0)
	if u != nil {
2194 2195
		var sl *Symlink
		for f := u.Method; f != nil; f = f.Down {
2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221
			if f.Sym.Flags&SymUniq != 0 {
				continue
			}
			f.Sym.Flags |= SymUniq
			sl = new(Symlink)
			sl.field = f
			sl.link = slist
			sl.followptr = uint8(followptr)
			slist = sl
		}
	}
}

func expand1(t *Type, d int, followptr int) {
	if t.Trecur != 0 {
		return
	}
	if d == 0 {
		return
	}
	t.Trecur = 1

	if d != len(dotlist)-1 {
		expand0(t, followptr)
	}

2222
	u := t
2223
	if Isptr[u.Etype] {
2224 2225 2226 2227 2228 2229 2230 2231
		followptr = 1
		u = u.Type
	}

	if u.Etype != TSTRUCT && u.Etype != TINTER {
		goto out
	}

2232
	for f := u.Type; f != nil; f = f.Down {
2233
		if f.Embedded == 0 {
2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252
			continue
		}
		if f.Sym == nil {
			continue
		}
		expand1(f.Type, d-1, followptr)
	}

out:
	t.Trecur = 0
}

func expandmeth(t *Type) {
	if t == nil || t.Xmethod != nil {
		return
	}

	// mark top-level method symbols
	// so that expand1 doesn't consider them.
2253
	var f *Type
2254 2255 2256 2257 2258 2259 2260 2261 2262 2263
	for f = t.Method; f != nil; f = f.Down {
		f.Sym.Flags |= SymUniq
	}

	// generate all reachable methods
	slist = nil

	expand1(t, len(dotlist)-1, 0)

	// check each method to be uniquely reachable
2264 2265 2266
	var c int
	var d int
	for sl := slist; sl != nil; sl = sl.link {
2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289
		sl.field.Sym.Flags &^= SymUniq
		for d = 0; d < len(dotlist); d++ {
			c = adddot1(sl.field.Sym, t, d, &f, 0)
			if c == 0 {
				continue
			}
			if c == 1 {
				// addot1 may have dug out arbitrary fields, we only want methods.
				if f.Type.Etype == TFUNC && f.Type.Thistuple > 0 {
					sl.good = 1
					sl.field = f
				}
			}

			break
		}
	}

	for f = t.Method; f != nil; f = f.Down {
		f.Sym.Flags &^= SymUniq
	}

	t.Xmethod = t.Method
2290
	for sl := slist; sl != nil; sl = sl.link {
2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314
		if sl.good != 0 {
			// add it to the base type method list
			f = typ(TFIELD)

			*f = *sl.field
			f.Embedded = 1 // needs a trampoline
			if sl.followptr != 0 {
				f.Embedded = 2
			}
			f.Down = t.Xmethod
			t.Xmethod = f
		}
	}
}

/*
 * Given funarg struct list, return list of ODCLFIELD Node fn args.
 */
func structargs(tl **Type, mustname int) *NodeList {
	var savet Iter
	var a *Node
	var n *Node
	var buf string

Russ Cox's avatar
Russ Cox committed
2315
	var args *NodeList
2316 2317
	gen := 0
	for t := Structfirst(&savet, tl); t != nil; t = structnext(&savet) {
2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381
		n = nil
		if mustname != 0 && (t.Sym == nil || t.Sym.Name == "_") {
			// invent a name so that we can refer to it in the trampoline
			buf = fmt.Sprintf(".anon%d", gen)
			gen++

			n = newname(Lookup(buf))
		} else if t.Sym != nil {
			n = newname(t.Sym)
		}
		a = Nod(ODCLFIELD, n, typenod(t.Type))
		a.Isddd = t.Isddd
		if n != nil {
			n.Isddd = t.Isddd
		}
		args = list(args, a)
	}

	return args
}

/*
 * Generate a wrapper function to convert from
 * a receiver of type T to a receiver of type U.
 * That is,
 *
 *	func (t T) M() {
 *		...
 *	}
 *
 * already exists; this function generates
 *
 *	func (u U) M() {
 *		u.M()
 *	}
 *
 * where the types T and U are such that u.M() is valid
 * and calls the T.M method.
 * The resulting function is for use in method tables.
 *
 *	rcvr - U
 *	method - M func (t T)(), a TFIELD type struct
 *	newnam - the eventual mangled name of this function
 */

var genwrapper_linehistdone int = 0

func genwrapper(rcvr *Type, method *Type, newnam *Sym, iface int) {
	if false && Debug['r'] != 0 {
		fmt.Printf("genwrapper rcvrtype=%v method=%v newnam=%v\n", Tconv(rcvr, 0), Tconv(method, 0), Sconv(newnam, 0))
	}

	lexlineno++
	lineno = lexlineno
	if genwrapper_linehistdone == 0 {
		// All the wrappers can share the same linehist entry.
		linehist("<autogenerated>", 0, 0)

		genwrapper_linehistdone = 1
	}

	dclcontext = PEXTERN
	markdcl()

2382
	this := Nod(ODCLFIELD, newname(Lookup(".this")), typenod(rcvr))
2383
	this.Left.Ntype = this.Right
2384 2385
	in := structargs(getinarg(method.Type), 1)
	out := structargs(Getoutarg(method.Type), 0)
2386

2387 2388
	t := Nod(OTFUNC, nil, nil)
	l := list1(this)
2389 2390 2391 2392 2393 2394
	if iface != 0 && rcvr.Width < Types[Tptr].Width {
		// Building method for interface table and receiver
		// is smaller than the single pointer-sized word
		// that the interface call will pass in.
		// Add a dummy padding argument after the
		// receiver to make up the difference.
2395
		tpad := typ(TARRAY)
2396 2397 2398

		tpad.Type = Types[TUINT8]
		tpad.Bound = Types[Tptr].Width - rcvr.Width
2399
		pad := Nod(ODCLFIELD, newname(Lookup(".pad")), typenod(tpad))
2400 2401 2402 2403 2404 2405
		l = list(l, pad)
	}

	t.List = concat(l, in)
	t.Rlist = out

2406
	fn := Nod(ODCLFUNC, nil, nil)
2407 2408 2409 2410 2411 2412 2413
	fn.Nname = newname(newnam)
	fn.Nname.Defn = fn
	fn.Nname.Ntype = t
	declare(fn.Nname, PFUNC)
	funchdr(fn)

	// arg list
Russ Cox's avatar
Russ Cox committed
2414
	var args *NodeList
2415

2416
	isddd := false
2417
	for l := in; l != nil; l = l.Next {
2418
		args = list(args, l.N.Left)
2419
		isddd = l.N.Left.Isddd
2420 2421
	}

2422
	methodrcvr := getthisx(method.Type).Type.Type
2423 2424

	// generate nil pointer check for better error
2425
	if Isptr[rcvr.Etype] && rcvr.Type == methodrcvr {
2426
		// generating wrapper from *T to T.
2427
		n := Nod(OIF, nil, nil)
2428 2429 2430 2431 2432

		n.Ntest = Nod(OEQ, this.Left, nodnil())

		// these strings are already in the reflect tables,
		// so no space cost to use them here.
Russ Cox's avatar
Russ Cox committed
2433
		var l *NodeList
2434

2435
		var v Val
2436
		v.Ctype = CTSTR
2437
		v.U.Sval = rcvr.Type.Sym.Pkg.Name // package name
2438
		l = list(l, nodlit(v))
2439
		v.U.Sval = rcvr.Type.Sym.Name // type name
2440
		l = list(l, nodlit(v))
2441
		v.U.Sval = method.Sym.Name
2442
		l = list(l, nodlit(v)) // method name
2443
		call := Nod(OCALL, syslook("panicwrap", 0), nil)
2444 2445 2446 2447 2448
		call.List = l
		n.Nbody = list1(call)
		fn.Nbody = list(fn.Nbody, n)
	}

2449
	dot := adddot(Nod(OXDOT, this.Left, newname(method.Sym)))
2450 2451

	// generate call
2452
	if flag_race == 0 && Isptr[rcvr.Etype] && Isptr[methodrcvr.Etype] && method.Embedded != 0 && !isifacemethod(method.Type) {
2453 2454
		// generate tail call: adjust pointer receiver and jump to embedded method.
		dot = dot.Left // skip final .M
2455
		if !Isptr[dotlist[0].field.Type.Etype] {
2456 2457
			dot = Nod(OADDR, dot, nil)
		}
2458
		as := Nod(OAS, this.Left, Nod(OCONVNOP, dot, nil))
2459 2460
		as.Right.Type = rcvr
		fn.Nbody = list(fn.Nbody, as)
2461
		n := Nod(ORETJMP, nil, nil)
2462 2463 2464
		n.Left = newname(methodsym(method.Sym, methodrcvr, 0))
		fn.Nbody = list(fn.Nbody, n)
	} else {
2465
		fn.Wrapper = true // ignore frame for panic+recover matching
2466
		call := Nod(OCALL, dot, nil)
2467
		call.List = args
2468
		call.Isddd = isddd
2469
		if method.Type.Outtuple > 0 {
2470
			n := Nod(ORETURN, nil, nil)
2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485
			n.List = list1(call)
			call = n
		}

		fn.Nbody = list(fn.Nbody, call)
	}

	if false && Debug['r'] != 0 {
		dumplist("genwrapper body", fn.Nbody)
	}

	funcbody(fn)
	Curfn = fn

	// wrappers where T is anonymous (struct or interface) can be duplicated.
2486
	if rcvr.Etype == TSTRUCT || rcvr.Etype == TINTER || Isptr[rcvr.Etype] && rcvr.Type.Etype == TSTRUCT {
2487
		fn.Dupok = true
2488 2489 2490 2491 2492 2493
	}
	typecheck(&fn, Etop)
	typechecklist(fn.Nbody, Etop)

	// Set inl_nonlocal to whether we are calling a method on a
	// type defined in a different package.  Checked in inlvar.
2494
	if !methodrcvr.Local {
2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506
		inl_nonlocal = 1
	}

	inlcalls(fn)

	inl_nonlocal = 0

	Curfn = nil
	funccompile(fn)
}

func hashmem(t *Type) *Node {
2507
	sym := Pkglookup("memhash", Runtimepkg)
2508

2509
	n := newname(sym)
2510
	n.Class = PFUNC
2511
	tfn := Nod(OTFUNC, nil, nil)
2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523
	tfn.List = list(tfn.List, Nod(ODCLFIELD, nil, typenod(Ptrto(t))))
	tfn.List = list(tfn.List, Nod(ODCLFIELD, nil, typenod(Types[TUINTPTR])))
	tfn.List = list(tfn.List, Nod(ODCLFIELD, nil, typenod(Types[TUINTPTR])))
	tfn.Rlist = list(tfn.Rlist, Nod(ODCLFIELD, nil, typenod(Types[TUINTPTR])))
	typecheck(&tfn, Etype)
	n.Type = tfn.Type
	return n
}

func hashfor(t *Type) *Node {
	var sym *Sym

2524
	a := algtype1(t, nil)
2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553
	switch a {
	case AMEM:
		Fatal("hashfor with AMEM type")

	case AINTER:
		sym = Pkglookup("interhash", Runtimepkg)

	case ANILINTER:
		sym = Pkglookup("nilinterhash", Runtimepkg)

	case ASTRING:
		sym = Pkglookup("strhash", Runtimepkg)

	case AFLOAT32:
		sym = Pkglookup("f32hash", Runtimepkg)

	case AFLOAT64:
		sym = Pkglookup("f64hash", Runtimepkg)

	case ACPLX64:
		sym = Pkglookup("c64hash", Runtimepkg)

	case ACPLX128:
		sym = Pkglookup("c128hash", Runtimepkg)

	default:
		sym = typesymprefix(".hash", t)
	}

2554
	n := newname(sym)
2555
	n.Class = PFUNC
2556
	tfn := Nod(OTFUNC, nil, nil)
2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577
	tfn.List = list(tfn.List, Nod(ODCLFIELD, nil, typenod(Ptrto(t))))
	tfn.List = list(tfn.List, Nod(ODCLFIELD, nil, typenod(Types[TUINTPTR])))
	tfn.Rlist = list(tfn.Rlist, Nod(ODCLFIELD, nil, typenod(Types[TUINTPTR])))
	typecheck(&tfn, Etype)
	n.Type = tfn.Type
	return n
}

/*
 * Generate a helper function to compute the hash of a value of type t.
 */
func genhash(sym *Sym, t *Type) {
	if Debug['r'] != 0 {
		fmt.Printf("genhash %v %v\n", Sconv(sym, 0), Tconv(t, 0))
	}

	lineno = 1 // less confusing than end of input
	dclcontext = PEXTERN
	markdcl()

	// func sym(p *T, h uintptr) uintptr
2578
	fn := Nod(ODCLFUNC, nil, nil)
2579 2580 2581

	fn.Nname = newname(sym)
	fn.Nname.Class = PFUNC
2582
	tfn := Nod(OTFUNC, nil, nil)
2583 2584
	fn.Nname.Ntype = tfn

2585
	n := Nod(ODCLFIELD, newname(Lookup("p")), typenod(Ptrto(t)))
2586
	tfn.List = list(tfn.List, n)
2587
	np := n.Left
2588 2589
	n = Nod(ODCLFIELD, newname(Lookup("h")), typenod(Types[TUINTPTR]))
	tfn.List = list(tfn.List, n)
2590
	nh := n.Left
2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604
	n = Nod(ODCLFIELD, nil, typenod(Types[TUINTPTR])) // return value
	tfn.Rlist = list(tfn.Rlist, n)

	funchdr(fn)
	typecheck(&fn.Nname.Ntype, Etype)

	// genhash is only called for types that have equality but
	// cannot be handled by the standard algorithms,
	// so t must be either an array or a struct.
	switch t.Etype {
	default:
		Fatal("genhash %v", Tconv(t, 0))

	case TARRAY:
2605
		if Isslice(t) {
2606 2607 2608 2609 2610 2611
			Fatal("genhash %v", Tconv(t, 0))
		}

		// An array of pure memory would be handled by the
		// standard algorithm, so the element type must not be
		// pure memory.
2612
		hashel := hashfor(t.Type)
2613

2614 2615
		n := Nod(ORANGE, nil, Nod(OIND, np, nil))
		ni := newname(Lookup("i"))
2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628
		ni.Type = Types[TINT]
		n.List = list1(ni)
		n.Colas = 1
		colasdefn(n.List, n)
		ni = n.List.N

		// TODO: with aeshash we don't need these shift/mul parts

		// h = h<<3 | h>>61
		n.Nbody = list(n.Nbody, Nod(OAS, nh, Nod(OOR, Nod(OLSH, nh, Nodintconst(3)), Nod(ORSH, nh, Nodintconst(int64(Widthptr)*8-3)))))

		// h *= mul
		// Same multipliers as in runtime.memhash.
2629
		var mul int64
2630 2631 2632 2633 2634 2635 2636 2637
		if Widthptr == 4 {
			mul = 3267000013
		} else {
			mul = 23344194077549503
		}
		n.Nbody = list(n.Nbody, Nod(OAS, nh, Nod(OMUL, nh, Nodintconst(mul))))

		// h = hashel(&p[i], h)
2638
		call := Nod(OCALL, hashel, nil)
2639

2640
		nx := Nod(OINDEX, np, ni)
2641
		nx.Bounded = true
2642
		na := Nod(OADDR, nx, nil)
2643 2644 2645 2646 2647 2648 2649 2650 2651 2652
		na.Etype = 1 // no escape to heap
		call.List = list(call.List, na)
		call.List = list(call.List, nh)
		n.Nbody = list(n.Nbody, Nod(OAS, nh, call))

		fn.Nbody = list(fn.Nbody, n)

		// Walk the struct using memhash for runs of AMEM
	// and calling specific hash functions for the others.
	case TSTRUCT:
Russ Cox's avatar
Russ Cox committed
2653
		var first *Type
2654 2655 2656 2657 2658 2659 2660 2661

		offend := int64(0)
		var size int64
		var call *Node
		var nx *Node
		var na *Node
		var hashel *Node
		for t1 := t.Type; ; t1 = t1.Down {
2662 2663 2664 2665 2666 2667 2668
			if t1 != nil && algtype1(t1.Type, nil) == AMEM && !isblanksym(t1.Sym) {
				offend = t1.Width + t1.Type.Width
				if first == nil {
					first = t1
				}

				// If it's a memory field but it's padded, stop here.
2669
				if ispaddedfield(t1, t.Width) {
2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731
					t1 = t1.Down
				} else {
					continue
				}
			}

			// Run memhash for fields up to this one.
			if first != nil {
				size = offend - first.Width // first->width is offset
				hashel = hashmem(first.Type)

				// h = hashel(&p.first, size, h)
				call = Nod(OCALL, hashel, nil)

				nx = Nod(OXDOT, np, newname(first.Sym)) // TODO: fields from other packages?
				na = Nod(OADDR, nx, nil)
				na.Etype = 1 // no escape to heap
				call.List = list(call.List, na)
				call.List = list(call.List, nh)
				call.List = list(call.List, Nodintconst(size))
				fn.Nbody = list(fn.Nbody, Nod(OAS, nh, call))

				first = nil
			}

			if t1 == nil {
				break
			}
			if isblanksym(t1.Sym) {
				continue
			}

			// Run hash for this field.
			if algtype1(t1.Type, nil) == AMEM {
				hashel = hashmem(t1.Type)

				// h = memhash(&p.t1, h, size)
				call = Nod(OCALL, hashel, nil)

				nx = Nod(OXDOT, np, newname(t1.Sym)) // TODO: fields from other packages?
				na = Nod(OADDR, nx, nil)
				na.Etype = 1 // no escape to heap
				call.List = list(call.List, na)
				call.List = list(call.List, nh)
				call.List = list(call.List, Nodintconst(t1.Type.Width))
				fn.Nbody = list(fn.Nbody, Nod(OAS, nh, call))
			} else {
				hashel = hashfor(t1.Type)

				// h = hashel(&p.t1, h)
				call = Nod(OCALL, hashel, nil)

				nx = Nod(OXDOT, np, newname(t1.Sym)) // TODO: fields from other packages?
				na = Nod(OADDR, nx, nil)
				na.Etype = 1 // no escape to heap
				call.List = list(call.List, na)
				call.List = list(call.List, nh)
				fn.Nbody = list(fn.Nbody, Nod(OAS, nh, call))
			}
		}
	}

2732
	r := Nod(ORETURN, nil, nil)
2733 2734 2735 2736 2737 2738 2739 2740 2741
	r.List = list(r.List, nh)
	fn.Nbody = list(fn.Nbody, r)

	if Debug['r'] != 0 {
		dumplist("genhash body", fn.Nbody)
	}

	funcbody(fn)
	Curfn = fn
2742
	fn.Dupok = true
2743 2744 2745 2746 2747 2748 2749 2750 2751
	typecheck(&fn, Etop)
	typechecklist(fn.Nbody, Etop)
	Curfn = nil

	// Disable safemode while compiling this code: the code we
	// generate internally can refer to unsafe.Pointer.
	// In this case it can happen if we need to generate an ==
	// for a struct containing a reflect.Value, which itself has
	// an unexported field of type unsafe.Pointer.
2752
	old_safemode := safemode
2753 2754 2755 2756 2757 2758 2759 2760 2761

	safemode = 0
	funccompile(fn)
	safemode = old_safemode
}

// Return node for
//	if p.field != q.field { return false }
func eqfield(p *Node, q *Node, field *Node) *Node {
2762 2763 2764
	nx := Nod(OXDOT, p, field)
	ny := Nod(OXDOT, q, field)
	nif := Nod(OIF, nil, nil)
2765
	nif.Ntest = Nod(ONE, nx, ny)
2766
	r := Nod(ORETURN, nil, nil)
2767
	r.List = list(r.List, Nodbool(false))
2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779
	nif.Nbody = list(nif.Nbody, r)
	return nif
}

func eqmemfunc(size int64, type_ *Type, needsize *int) *Node {
	var fn *Node

	switch size {
	default:
		fn = syslook("memequal", 1)
		*needsize = 1

2780
	case 1, 2, 4, 8, 16:
2781
		buf := fmt.Sprintf("memequal%d", int(size)*8)
2782 2783 2784 2785
		fn = syslook(buf, 1)
		*needsize = 0
	}

2786
	substArgTypes(fn, type_, type_)
2787 2788 2789 2790 2791 2792 2793 2794
	return fn
}

// Return node for
//	if !memequal(&p.field, &q.field [, size]) { return false }
func eqmem(p *Node, q *Node, field *Node, size int64) *Node {
	var needsize int

2795
	nx := Nod(OADDR, Nod(OXDOT, p, field), nil)
2796
	nx.Etype = 1 // does not escape
2797
	ny := Nod(OADDR, Nod(OXDOT, q, field), nil)
2798 2799 2800 2801
	ny.Etype = 1 // does not escape
	typecheck(&nx, Erv)
	typecheck(&ny, Erv)

2802
	call := Nod(OCALL, eqmemfunc(size, nx.Type.Type, &needsize), nil)
2803 2804 2805 2806 2807 2808
	call.List = list(call.List, nx)
	call.List = list(call.List, ny)
	if needsize != 0 {
		call.List = list(call.List, Nodintconst(size))
	}

2809
	nif := Nod(OIF, nil, nil)
2810
	nif.Ntest = Nod(ONOT, call, nil)
2811
	r := Nod(ORETURN, nil, nil)
2812
	r.List = list(r.List, Nodbool(false))
2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829
	nif.Nbody = list(nif.Nbody, r)
	return nif
}

/*
 * Generate a helper function to check equality of two values of type t.
 */
func geneq(sym *Sym, t *Type) {
	if Debug['r'] != 0 {
		fmt.Printf("geneq %v %v\n", Sconv(sym, 0), Tconv(t, 0))
	}

	lineno = 1 // less confusing than end of input
	dclcontext = PEXTERN
	markdcl()

	// func sym(p, q *T) bool
2830
	fn := Nod(ODCLFUNC, nil, nil)
2831 2832 2833

	fn.Nname = newname(sym)
	fn.Nname.Class = PFUNC
2834
	tfn := Nod(OTFUNC, nil, nil)
2835 2836
	fn.Nname.Ntype = tfn

2837
	n := Nod(ODCLFIELD, newname(Lookup("p")), typenod(Ptrto(t)))
2838
	tfn.List = list(tfn.List, n)
2839
	np := n.Left
2840 2841
	n = Nod(ODCLFIELD, newname(Lookup("q")), typenod(Ptrto(t)))
	tfn.List = list(tfn.List, n)
2842
	nq := n.Left
2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855
	n = Nod(ODCLFIELD, nil, typenod(Types[TBOOL]))
	tfn.Rlist = list(tfn.Rlist, n)

	funchdr(fn)

	// geneq is only called for types that have equality but
	// cannot be handled by the standard algorithms,
	// so t must be either an array or a struct.
	switch t.Etype {
	default:
		Fatal("geneq %v", Tconv(t, 0))

	case TARRAY:
2856
		if Isslice(t) {
2857 2858 2859 2860 2861 2862 2863 2864
			Fatal("geneq %v", Tconv(t, 0))
		}

		// An array of pure memory would be handled by the
		// standard memequal, so the element type must not be
		// pure memory.  Even if we unrolled the range loop,
		// each iteration would be a function call, so don't bother
		// unrolling.
2865
		nrange := Nod(ORANGE, nil, Nod(OIND, np, nil))
2866

2867
		ni := newname(Lookup("i"))
2868 2869 2870 2871 2872 2873 2874
		ni.Type = Types[TINT]
		nrange.List = list1(ni)
		nrange.Colas = 1
		colasdefn(nrange.List, nrange)
		ni = nrange.List.N

		// if p[i] != q[i] { return false }
2875
		nx := Nod(OINDEX, np, ni)
2876

2877
		nx.Bounded = true
2878
		ny := Nod(OINDEX, nq, ni)
2879
		ny.Bounded = true
2880

2881
		nif := Nod(OIF, nil, nil)
2882
		nif.Ntest = Nod(ONE, nx, ny)
2883
		r := Nod(ORETURN, nil, nil)
2884
		r.List = list(r.List, Nodbool(false))
2885 2886 2887 2888 2889 2890 2891 2892
		nif.Nbody = list(nif.Nbody, r)
		nrange.Nbody = list(nrange.Nbody, nif)
		fn.Nbody = list(fn.Nbody, nrange)

		// Walk the struct using memequal for runs of AMEM
	// and calling specific equality tests for the others.
	// Skip blank-named fields.
	case TSTRUCT:
Russ Cox's avatar
Russ Cox committed
2893
		var first *Type
2894

2895 2896 2897
		offend := int64(0)
		var size int64
		for t1 := t.Type; ; t1 = t1.Down {
2898 2899 2900 2901 2902 2903 2904
			if t1 != nil && algtype1(t1.Type, nil) == AMEM && !isblanksym(t1.Sym) {
				offend = t1.Width + t1.Type.Width
				if first == nil {
					first = t1
				}

				// If it's a memory field but it's padded, stop here.
2905
				if ispaddedfield(t1, t.Width) {
2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945
					t1 = t1.Down
				} else {
					continue
				}
			}

			// Run memequal for fields up to this one.
			// TODO(rsc): All the calls to newname are wrong for
			// cross-package unexported fields.
			if first != nil {
				if first.Down == t1 {
					fn.Nbody = list(fn.Nbody, eqfield(np, nq, newname(first.Sym)))
				} else if first.Down.Down == t1 {
					fn.Nbody = list(fn.Nbody, eqfield(np, nq, newname(first.Sym)))
					first = first.Down
					if !isblanksym(first.Sym) {
						fn.Nbody = list(fn.Nbody, eqfield(np, nq, newname(first.Sym)))
					}
				} else {
					// More than two fields: use memequal.
					size = offend - first.Width // first->width is offset
					fn.Nbody = list(fn.Nbody, eqmem(np, nq, newname(first.Sym), size))
				}

				first = nil
			}

			if t1 == nil {
				break
			}
			if isblanksym(t1.Sym) {
				continue
			}

			// Check this field, which is not just memory.
			fn.Nbody = list(fn.Nbody, eqfield(np, nq, newname(t1.Sym)))
		}
	}

	// return true
2946
	r := Nod(ORETURN, nil, nil)
2947

2948
	r.List = list(r.List, Nodbool(true))
2949 2950 2951 2952 2953 2954 2955 2956
	fn.Nbody = list(fn.Nbody, r)

	if Debug['r'] != 0 {
		dumplist("geneq body", fn.Nbody)
	}

	funcbody(fn)
	Curfn = fn
2957
	fn.Dupok = true
2958 2959 2960 2961 2962 2963 2964 2965 2966
	typecheck(&fn, Etop)
	typechecklist(fn.Nbody, Etop)
	Curfn = nil

	// Disable safemode while compiling this code: the code we
	// generate internally can refer to unsafe.Pointer.
	// In this case it can happen if we need to generate an ==
	// for a struct containing a reflect.Value, which itself has
	// an unexported field of type unsafe.Pointer.
2967
	old_safemode := safemode
2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980

	safemode = 0
	funccompile(fn)
	safemode = old_safemode
}

func ifacelookdot(s *Sym, t *Type, followptr *int, ignorecase int) *Type {
	*followptr = 0

	if t == nil {
		return nil
	}

2981 2982 2983 2984
	var m *Type
	var i int
	var c int
	for d := 0; d < len(dotlist); d++ {
2985 2986 2987 2988 2989 2990 2991 2992
		c = adddot1(s, t, d, &m, ignorecase)
		if c > 1 {
			Yyerror("%v.%v is ambiguous", Tconv(t, 0), Sconv(s, 0))
			return nil
		}

		if c == 1 {
			for i = 0; i < d; i++ {
2993
				if Isptr[dotlist[i].field.Type.Etype] {
2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010
					*followptr = 1
					break
				}
			}

			if m.Type.Etype != TFUNC || m.Type.Thistuple == 0 {
				Yyerror("%v.%v is a field, not a method", Tconv(t, 0), Sconv(s, 0))
				return nil
			}

			return m
		}
	}

	return nil
}

3011
func implements(t *Type, iface *Type, m **Type, samename **Type, ptr *int) bool {
3012
	t0 := t
3013
	if t == nil {
3014
		return false
3015 3016 3017 3018 3019 3020 3021
	}

	// if this is too slow,
	// could sort these first
	// and then do one loop.

	if t.Etype == TINTER {
3022 3023
		var tm *Type
		for im := iface.Type; im != nil; im = im.Down {
3024 3025 3026 3027 3028 3029 3030 3031
			for tm = t.Type; tm != nil; tm = tm.Down {
				if tm.Sym == im.Sym {
					if Eqtype(tm.Type, im.Type) {
						goto found
					}
					*m = im
					*samename = tm
					*ptr = 0
3032
					return false
3033 3034 3035 3036 3037 3038
				}
			}

			*m = im
			*samename = nil
			*ptr = 0
3039
			return false
3040 3041 3042
		found:
		}

3043
		return true
3044 3045 3046 3047 3048 3049
	}

	t = methtype(t, 0)
	if t != nil {
		expandmeth(t)
	}
3050 3051 3052 3053 3054
	var tm *Type
	var imtype *Type
	var followptr int
	var rcvr *Type
	for im := iface.Type; im != nil; im = im.Down {
3055 3056
		imtype = methodfunc(im.Type, nil)
		tm = ifacelookdot(im.Sym, t, &followptr, 0)
3057
		if tm == nil || tm.Nointerface || !Eqtype(methodfunc(tm.Type, nil), imtype) {
3058 3059 3060 3061 3062 3063
			if tm == nil {
				tm = ifacelookdot(im.Sym, t, &followptr, 1)
			}
			*m = im
			*samename = tm
			*ptr = 0
3064
			return false
3065 3066 3067 3068 3069 3070
		}

		// if pointer receiver in method,
		// the method does not exist for value types.
		rcvr = getthisx(tm.Type).Type.Type

3071
		if Isptr[rcvr.Etype] && !Isptr[t0.Etype] && followptr == 0 && !isifacemethod(tm.Type) {
3072 3073 3074 3075 3076 3077 3078
			if false && Debug['r'] != 0 {
				Yyerror("interface pointer mismatch")
			}

			*m = im
			*samename = nil
			*ptr = 1
3079
			return false
3080 3081 3082
		}
	}

3083
	return true
3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095
}

/*
 * even simpler simtype; get rid of ptr, bool.
 * assuming that the front end has rejected
 * all the invalid conversions (like ptr -> bool)
 */
func Simsimtype(t *Type) int {
	if t == nil {
		return 0
	}

3096
	et := int(Simtype[t.Etype])
3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111
	switch et {
	case TPTR32:
		et = TUINT32

	case TPTR64:
		et = TUINT64

	case TBOOL:
		et = TUINT8
	}

	return et
}

func listtreecopy(l *NodeList) *NodeList {
Russ Cox's avatar
Russ Cox committed
3112
	var out *NodeList
3113 3114 3115 3116 3117 3118 3119
	for ; l != nil; l = l.Next {
		out = list(out, treecopy(l.N))
	}
	return out
}

func liststmt(l *NodeList) *Node {
3120
	n := Nod(OBLOCK, nil, nil)
3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133
	n.List = l
	if l != nil {
		n.Lineno = l.N.Lineno
	}
	return n
}

/*
 * return nelem of list
 */
func structcount(t *Type) int {
	var s Iter

3134
	v := 0
3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147
	for t = Structfirst(&s, &t); t != nil; t = structnext(&s) {
		v++
	}
	return v
}

/*
 * return power of 2 of the constant
 * operand. -1 if it is not a power of 2.
 * 1000+ if it is a -(power of 2)
 */
func powtwo(n *Node) int {
	if n == nil || n.Op != OLITERAL || n.Type == nil {
Russ Cox's avatar
Russ Cox committed
3148
		return -1
3149
	}
3150
	if !Isint[n.Type.Etype] {
Russ Cox's avatar
Russ Cox committed
3151
		return -1
3152 3153
	}

Russ Cox's avatar
Russ Cox committed
3154 3155
	v := uint64(Mpgetfix(n.Val.U.Xval))
	b := uint64(1)
3156
	for i := 0; i < 64; i++ {
3157 3158 3159 3160 3161 3162
		if b == v {
			return i
		}
		b = b << 1
	}

3163
	if !Issigned[n.Type.Etype] {
Russ Cox's avatar
Russ Cox committed
3164
		return -1
3165 3166 3167 3168
	}

	v = -v
	b = 1
3169
	for i := 0; i < 64; i++ {
3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 3194 3195 3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237
		if b == v {
			return i + 1000
		}
		b = b << 1
	}

	return -1
}

/*
 * return the unsigned type for
 * a signed integer type.
 * returns T if input is not a
 * signed integer type.
 */
func tounsigned(t *Type) *Type {
	// this is types[et+1], but not sure
	// that this relation is immutable
	switch t.Etype {
	default:
		fmt.Printf("tounsigned: unknown type %v\n", Tconv(t, 0))
		t = nil

	case TINT:
		t = Types[TUINT]

	case TINT8:
		t = Types[TUINT8]

	case TINT16:
		t = Types[TUINT16]

	case TINT32:
		t = Types[TUINT32]

	case TINT64:
		t = Types[TUINT64]
	}

	return t
}

/*
 * magic number for signed division
 * see hacker's delight chapter 10
 */
func Smagic(m *Magic) {
	var mask uint64

	m.Bad = 0
	switch m.W {
	default:
		m.Bad = 1
		return

	case 8:
		mask = 0xff

	case 16:
		mask = 0xffff

	case 32:
		mask = 0xffffffff

	case 64:
		mask = 0xffffffffffffffff
	}

3238
	two31 := mask ^ (mask >> 1)
3239

3240 3241
	p := m.W - 1
	ad := uint64(m.Sd)
3242 3243 3244 3245 3246 3247 3248 3249 3250 3251
	if m.Sd < 0 {
		ad = -uint64(m.Sd)
	}

	// bad denominators
	if ad == 0 || ad == 1 || ad == two31 {
		m.Bad = 1
		return
	}

3252
	t := two31
3253 3254
	ad &= mask

3255
	anc := t - 1 - t%ad
3256 3257
	anc &= mask

3258 3259
	q1 := two31 / anc
	r1 := two31 - q1*anc
3260 3261 3262
	q1 &= mask
	r1 &= mask

3263 3264
	q2 := two31 / ad
	r2 := two31 - q2*ad
3265 3266 3267
	q2 &= mask
	r2 &= mask

3268
	var delta uint64
3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336
	for {
		p++
		q1 <<= 1
		r1 <<= 1
		q1 &= mask
		r1 &= mask
		if r1 >= anc {
			q1++
			r1 -= anc
			q1 &= mask
			r1 &= mask
		}

		q2 <<= 1
		r2 <<= 1
		q2 &= mask
		r2 &= mask
		if r2 >= ad {
			q2++
			r2 -= ad
			q2 &= mask
			r2 &= mask
		}

		delta = ad - r2
		delta &= mask
		if q1 < delta || (q1 == delta && r1 == 0) {
			continue
		}

		break
	}

	m.Sm = int64(q2 + 1)
	if uint64(m.Sm)&two31 != 0 {
		m.Sm |= ^int64(mask)
	}
	m.S = p - m.W
}

/*
 * magic number for unsigned division
 * see hacker's delight chapter 10
 */
func Umagic(m *Magic) {
	var mask uint64

	m.Bad = 0
	m.Ua = 0

	switch m.W {
	default:
		m.Bad = 1
		return

	case 8:
		mask = 0xff

	case 16:
		mask = 0xffff

	case 32:
		mask = 0xffffffff

	case 64:
		mask = 0xffffffffffffffff
	}

3337
	two31 := mask ^ (mask >> 1)
3338 3339 3340 3341 3342 3343 3344

	m.Ud &= mask
	if m.Ud == 0 || m.Ud == two31 {
		m.Bad = 1
		return
	}

3345 3346
	nc := mask - (-m.Ud&mask)%m.Ud
	p := m.W - 1
3347

3348 3349
	q1 := two31 / nc
	r1 := two31 - q1*nc
3350 3351 3352
	q1 &= mask
	r1 &= mask

3353 3354
	q2 := (two31 - 1) / m.Ud
	r2 := (two31 - 1) - q2*m.Ud
3355 3356 3357
	q2 &= mask
	r2 &= mask

3358
	var delta uint64
3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433
	for {
		p++
		if r1 >= nc-r1 {
			q1 <<= 1
			q1++
			r1 <<= 1
			r1 -= nc
		} else {
			q1 <<= 1
			r1 <<= 1
		}

		q1 &= mask
		r1 &= mask
		if r2+1 >= m.Ud-r2 {
			if q2 >= two31-1 {
				m.Ua = 1
			}

			q2 <<= 1
			q2++
			r2 <<= 1
			r2++
			r2 -= m.Ud
		} else {
			if q2 >= two31 {
				m.Ua = 1
			}

			q2 <<= 1
			r2 <<= 1
			r2++
		}

		q2 &= mask
		r2 &= mask

		delta = m.Ud - 1 - r2
		delta &= mask

		if p < m.W+m.W {
			if q1 < delta || (q1 == delta && r1 == 0) {
				continue
			}
		}

		break
	}

	m.Um = q2 + 1
	m.S = p - m.W
}

func ngotype(n *Node) *Sym {
	if n.Type != nil {
		return typenamesym(n.Type)
	}
	return nil
}

/*
 * Convert raw string to the prefix that will be used in the symbol
 * table.  All control characters, space, '%' and '"', as well as
 * non-7-bit clean bytes turn into %xx.  The period needs escaping
 * only in the last segment of the path, and it makes for happier
 * users if we escape that as little as possible.
 *
 * If you edit this, edit ../ld/lib.c:/^pathtoprefix too.
 * If you edit this, edit ../../debug/goobj/read.go:/importPathToPrefix too.
 */
func pathtoprefix(s string) string {
	slash := strings.LastIndex(s, "/")
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c <= ' ' || i >= slash && c == '.' || c == '%' || c == '"' || c >= 0x7F {
Russ Cox's avatar
Russ Cox committed
3434 3435 3436 3437 3438 3439 3440 3441 3442 3443
			var buf bytes.Buffer
			for i := 0; i < len(s); i++ {
				c := s[i]
				if c <= ' ' || i >= slash && c == '.' || c == '%' || c == '"' || c >= 0x7F {
					fmt.Fprintf(&buf, "%%%02x", c)
					continue
				}
				buf.WriteByte(c)
			}
			return buf.String()
3444 3445 3446 3447 3448
		}
	}
	return s
}

3449 3450 3451
var pkgMap = make(map[string]*Pkg)
var pkgs []*Pkg

3452
func mkpkg(path string) *Pkg {
3453 3454
	if p := pkgMap[path]; p != nil {
		return p
3455 3456
	}

3457
	p := new(Pkg)
3458 3459
	p.Path = path
	p.Prefix = pathtoprefix(path)
3460
	p.Syms = make(map[string]*Sym)
3461 3462
	pkgMap[path] = p
	pkgs = append(pkgs, p)
3463 3464 3465 3466 3467 3468 3469 3470
	return p
}

func addinit(np **Node, init *NodeList) {
	if init == nil {
		return
	}

3471
	n := *np
3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492
	switch n.Op {
	// There may be multiple refs to this node;
	// introduce OCONVNOP to hold init list.
	case ONAME,
		OLITERAL:
		n = Nod(OCONVNOP, n, nil)

		n.Type = n.Left.Type
		n.Typecheck = 1
		*np = n
	}

	n.Ninit = concat(init, n.Ninit)
	n.Ullman = UINF
}

var reservedimports = []string{
	"go",
	"type",
}

3493 3494
func isbadimport(path string) bool {
	if strings.Contains(path, "\x00") {
3495 3496 3497 3498
		Yyerror("import path contains NUL")
		return true
	}

3499
	for i := 0; i < len(reservedimports); i++ {
3500 3501
		if path == reservedimports[i] {
			Yyerror("import path %q is reserved and cannot be used", path)
3502 3503 3504 3505
			return true
		}
	}

3506
	var s string
3507
	_ = s
3508
	var r uint
3509
	_ = r
3510
	for _, r := range path {
3511
		if r == utf8.RuneError {
3512
			Yyerror("import path contains invalid UTF-8 sequence: %q", path)
3513 3514 3515 3516
			return true
		}

		if r < 0x20 || r == 0x7f {
3517
			Yyerror("import path contains control character: %q", path)
3518 3519 3520 3521
			return true
		}

		if r == '\\' {
3522
			Yyerror("import path contains backslash; use slash: %q", path)
3523 3524 3525 3526
			return true
		}

		if unicode.IsSpace(rune(r)) {
3527
			Yyerror("import path contains space character: %q", path)
3528 3529 3530 3531
			return true
		}

		if strings.ContainsRune("!\"#$%&'()*,:;<=>?[]^`{|}", r) {
3532
			Yyerror("import path contains invalid character '%c': %q", r, path)
3533 3534 3535 3536 3537 3538 3539 3540
			return true
		}
	}

	return false
}

func checknil(x *Node, init **NodeList) {
3541
	if Isinter(x.Type) {
3542 3543 3544 3545
		x = Nod(OITAB, x, nil)
		typecheck(&x, Erv)
	}

3546
	n := Nod(OCHECKNIL, x, nil)
3547 3548 3549 3550 3551 3552 3553 3554
	n.Typecheck = 1
	*init = list(*init, n)
}

/*
 * Can this type be stored directly in an interface word?
 * Yes, if the representation is a single pointer.
 */
3555
func isdirectiface(t *Type) bool {
3556 3557 3558 3559 3560 3561 3562
	switch t.Etype {
	case TPTR32,
		TPTR64,
		TCHAN,
		TMAP,
		TFUNC,
		TUNSAFEPTR:
3563
		return true
3564 3565 3566

		// Array of 1 direct iface type can be direct.
	case TARRAY:
3567
		return t.Bound == 1 && isdirectiface(t.Type)
3568 3569 3570

		// Struct with 1 field of direct iface type can be direct.
	case TSTRUCT:
3571
		return t.Type != nil && t.Type.Down == nil && isdirectiface(t.Type.Type)
3572 3573
	}

3574
	return false
3575
}
3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588

// type2IET returns "T" if t is a concrete type,
// "I" if t is an interface type, and "E" if t is an empty interface type.
// It is used to build calls to the conv* and assert* runtime routines.
func type2IET(t *Type) string {
	if isnilinter(t) {
		return "E"
	}
	if Isinter(t) {
		return "I"
	}
	return "T"
}