1// Copyright 2009 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package gc
6
7import (
8	"cmd/compile/internal/types"
9	"cmd/internal/src"
10	"fmt"
11	"math/big"
12	"strings"
13)
14
15// Ctype describes the constant kind of an "ideal" (untyped) constant.
16type Ctype uint8
17
18const (
19	CTxxx Ctype = iota
20
21	CTINT
22	CTRUNE
23	CTFLT
24	CTCPLX
25	CTSTR
26	CTBOOL
27	CTNIL
28)
29
30type Val struct {
31	// U contains one of:
32	// bool     bool when Ctype() == CTBOOL
33	// *Mpint   int when Ctype() == CTINT, rune when Ctype() == CTRUNE
34	// *Mpflt   float when Ctype() == CTFLT
35	// *Mpcplx  pair of floats when Ctype() == CTCPLX
36	// string   string when Ctype() == CTSTR
37	// *Nilval  when Ctype() == CTNIL
38	U interface{}
39}
40
41func (v Val) Ctype() Ctype {
42	switch x := v.U.(type) {
43	default:
44		Fatalf("unexpected Ctype for %T", v.U)
45		panic("unreachable")
46	case nil:
47		return 0
48	case *NilVal:
49		return CTNIL
50	case bool:
51		return CTBOOL
52	case *Mpint:
53		if x.Rune {
54			return CTRUNE
55		}
56		return CTINT
57	case *Mpflt:
58		return CTFLT
59	case *Mpcplx:
60		return CTCPLX
61	case string:
62		return CTSTR
63	}
64}
65
66func eqval(a, b Val) bool {
67	if a.Ctype() != b.Ctype() {
68		return false
69	}
70	switch x := a.U.(type) {
71	default:
72		Fatalf("unexpected Ctype for %T", a.U)
73		panic("unreachable")
74	case *NilVal:
75		return true
76	case bool:
77		y := b.U.(bool)
78		return x == y
79	case *Mpint:
80		y := b.U.(*Mpint)
81		return x.Cmp(y) == 0
82	case *Mpflt:
83		y := b.U.(*Mpflt)
84		return x.Cmp(y) == 0
85	case *Mpcplx:
86		y := b.U.(*Mpcplx)
87		return x.Real.Cmp(&y.Real) == 0 && x.Imag.Cmp(&y.Imag) == 0
88	case string:
89		y := b.U.(string)
90		return x == y
91	}
92}
93
94// Interface returns the constant value stored in v as an interface{}.
95// It returns int64s for ints and runes, float64s for floats,
96// complex128s for complex values, and nil for constant nils.
97func (v Val) Interface() interface{} {
98	switch x := v.U.(type) {
99	default:
100		Fatalf("unexpected Interface for %T", v.U)
101		panic("unreachable")
102	case *NilVal:
103		return nil
104	case bool, string:
105		return x
106	case *Mpint:
107		return x.Int64()
108	case *Mpflt:
109		return x.Float64()
110	case *Mpcplx:
111		return complex(x.Real.Float64(), x.Imag.Float64())
112	}
113}
114
115type NilVal struct{}
116
117// Int64 returns n as an int64.
118// n must be an integer or rune constant.
119func (n *Node) Int64() int64 {
120	if !Isconst(n, CTINT) {
121		Fatalf("Int64(%v)", n)
122	}
123	return n.Val().U.(*Mpint).Int64()
124}
125
126// CanInt64 reports whether it is safe to call Int64() on n.
127func (n *Node) CanInt64() bool {
128	if !Isconst(n, CTINT) {
129		return false
130	}
131
132	// if the value inside n cannot be represented as an int64, the
133	// return value of Int64 is undefined
134	return n.Val().U.(*Mpint).CmpInt64(n.Int64()) == 0
135}
136
137// Bool returns n as a bool.
138// n must be a boolean constant.
139func (n *Node) Bool() bool {
140	if !Isconst(n, CTBOOL) {
141		Fatalf("Bool(%v)", n)
142	}
143	return n.Val().U.(bool)
144}
145
146// truncate float literal fv to 32-bit or 64-bit precision
147// according to type; return truncated value.
148func truncfltlit(oldv *Mpflt, t *types.Type) *Mpflt {
149	if t == nil {
150		return oldv
151	}
152
153	if overflow(Val{oldv}, t) {
154		// If there was overflow, simply continuing would set the
155		// value to Inf which in turn would lead to spurious follow-on
156		// errors. Avoid this by returning the existing value.
157		return oldv
158	}
159
160	fv := newMpflt()
161
162	// convert large precision literal floating
163	// into limited precision (float64 or float32)
164	switch t.Etype {
165	case types.TFLOAT32:
166		fv.SetFloat64(oldv.Float32())
167	case types.TFLOAT64:
168		fv.SetFloat64(oldv.Float64())
169	default:
170		Fatalf("truncfltlit: unexpected Etype %v", t.Etype)
171	}
172
173	return fv
174}
175
176// truncate Real and Imag parts of Mpcplx to 32-bit or 64-bit
177// precision, according to type; return truncated value. In case of
178// overflow, calls yyerror but does not truncate the input value.
179func trunccmplxlit(oldv *Mpcplx, t *types.Type) *Mpcplx {
180	if t == nil {
181		return oldv
182	}
183
184	if overflow(Val{oldv}, t) {
185		// If there was overflow, simply continuing would set the
186		// value to Inf which in turn would lead to spurious follow-on
187		// errors. Avoid this by returning the existing value.
188		return oldv
189	}
190
191	cv := newMpcmplx()
192
193	switch t.Etype {
194	case types.TCOMPLEX64:
195		cv.Real.SetFloat64(oldv.Real.Float32())
196		cv.Imag.SetFloat64(oldv.Imag.Float32())
197	case types.TCOMPLEX128:
198		cv.Real.SetFloat64(oldv.Real.Float64())
199		cv.Imag.SetFloat64(oldv.Imag.Float64())
200	default:
201		Fatalf("trunccplxlit: unexpected Etype %v", t.Etype)
202	}
203
204	return cv
205}
206
207// TODO(mdempsky): Replace these with better APIs.
208func convlit(n *Node, t *types.Type) *Node    { return convlit1(n, t, false, nil) }
209func defaultlit(n *Node, t *types.Type) *Node { return convlit1(n, t, false, nil) }
210
211// convlit1 converts an untyped expression n to type t. If n already
212// has a type, convlit1 has no effect.
213//
214// For explicit conversions, t must be non-nil, and integer-to-string
215// conversions are allowed.
216//
217// For implicit conversions (e.g., assignments), t may be nil; if so,
218// n is converted to its default type.
219//
220// If there's an error converting n to t, context is used in the error
221// message.
222func convlit1(n *Node, t *types.Type, explicit bool, context func() string) *Node {
223	if explicit && t == nil {
224		Fatalf("explicit conversion missing type")
225	}
226	if t != nil && t.IsUntyped() {
227		Fatalf("bad conversion to untyped: %v", t)
228	}
229
230	if n == nil || n.Type == nil {
231		// Allow sloppy callers.
232		return n
233	}
234	if !n.Type.IsUntyped() {
235		// Already typed; nothing to do.
236		return n
237	}
238
239	if n.Op == OLITERAL {
240		// Can't always set n.Type directly on OLITERAL nodes.
241		// See discussion on CL 20813.
242		n = n.rawcopy()
243	}
244
245	// Nil is technically not a constant, so handle it specially.
246	if n.Type.Etype == TNIL {
247		if t == nil {
248			yyerror("use of untyped nil")
249			n.SetDiag(true)
250			n.Type = nil
251			return n
252		}
253
254		if !t.HasNil() {
255			// Leave for caller to handle.
256			return n
257		}
258
259		n.Type = t
260		return n
261	}
262
263	if t == nil || !okforconst[t.Etype] {
264		t = defaultType(idealkind(n))
265	}
266
267	switch n.Op {
268	default:
269		Fatalf("unexpected untyped expression: %v", n)
270
271	case OLITERAL:
272		v := convertVal(n.Val(), t, explicit)
273		if v.U == nil {
274			break
275		}
276		n.SetVal(v)
277		n.Type = t
278		return n
279
280	case OPLUS, ONEG, OBITNOT, ONOT, OREAL, OIMAG:
281		ot := operandType(n.Op, t)
282		if ot == nil {
283			n = defaultlit(n, nil)
284			break
285		}
286
287		n.Left = convlit(n.Left, ot)
288		if n.Left.Type == nil {
289			n.Type = nil
290			return n
291		}
292		n.Type = t
293		return n
294
295	case OADD, OSUB, OMUL, ODIV, OMOD, OOR, OXOR, OAND, OANDNOT, OOROR, OANDAND, OCOMPLEX:
296		ot := operandType(n.Op, t)
297		if ot == nil {
298			n = defaultlit(n, nil)
299			break
300		}
301
302		n.Left = convlit(n.Left, ot)
303		n.Right = convlit(n.Right, ot)
304		if n.Left.Type == nil || n.Right.Type == nil {
305			n.Type = nil
306			return n
307		}
308		if !types.Identical(n.Left.Type, n.Right.Type) {
309			yyerror("invalid operation: %v (mismatched types %v and %v)", n, n.Left.Type, n.Right.Type)
310			n.Type = nil
311			return n
312		}
313
314		n.Type = t
315		return n
316
317	case OEQ, ONE, OLT, OLE, OGT, OGE:
318		if !t.IsBoolean() {
319			break
320		}
321		n.Type = t
322		return n
323
324	case OLSH, ORSH:
325		n.Left = convlit1(n.Left, t, explicit, nil)
326		n.Type = n.Left.Type
327		if n.Type != nil && !n.Type.IsInteger() {
328			yyerror("invalid operation: %v (shift of type %v)", n, n.Type)
329			n.Type = nil
330		}
331		return n
332	}
333
334	if !n.Diag() {
335		if !t.Broke() {
336			if explicit {
337				yyerror("cannot convert %L to type %v", n, t)
338			} else if context != nil {
339				yyerror("cannot use %L as type %v in %s", n, t, context())
340			} else {
341				yyerror("cannot use %L as type %v", n, t)
342			}
343		}
344		n.SetDiag(true)
345	}
346	n.Type = nil
347	return n
348}
349
350func operandType(op Op, t *types.Type) *types.Type {
351	switch op {
352	case OCOMPLEX:
353		if t.IsComplex() {
354			return floatForComplex(t)
355		}
356	case OREAL, OIMAG:
357		if t.IsFloat() {
358			return complexForFloat(t)
359		}
360	default:
361		if okfor[op][t.Etype] {
362			return t
363		}
364	}
365	return nil
366}
367
368// convertVal converts v into a representation appropriate for t. If
369// no such representation exists, it returns Val{} instead.
370//
371// If explicit is true, then conversions from integer to string are
372// also allowed.
373func convertVal(v Val, t *types.Type, explicit bool) Val {
374	switch ct := v.Ctype(); ct {
375	case CTBOOL:
376		if t.IsBoolean() {
377			return v
378		}
379
380	case CTSTR:
381		if t.IsString() {
382			return v
383		}
384
385	case CTINT, CTRUNE:
386		if explicit && t.IsString() {
387			return tostr(v)
388		}
389		fallthrough
390	case CTFLT, CTCPLX:
391		switch {
392		case t.IsInteger():
393			v = toint(v)
394			overflow(v, t)
395			return v
396		case t.IsFloat():
397			v = toflt(v)
398			v = Val{truncfltlit(v.U.(*Mpflt), t)}
399			return v
400		case t.IsComplex():
401			v = tocplx(v)
402			v = Val{trunccmplxlit(v.U.(*Mpcplx), t)}
403			return v
404		}
405	}
406
407	return Val{}
408}
409
410func tocplx(v Val) Val {
411	switch u := v.U.(type) {
412	case *Mpint:
413		c := newMpcmplx()
414		c.Real.SetInt(u)
415		c.Imag.SetFloat64(0.0)
416		v.U = c
417
418	case *Mpflt:
419		c := newMpcmplx()
420		c.Real.Set(u)
421		c.Imag.SetFloat64(0.0)
422		v.U = c
423	}
424
425	return v
426}
427
428func toflt(v Val) Val {
429	switch u := v.U.(type) {
430	case *Mpint:
431		f := newMpflt()
432		f.SetInt(u)
433		v.U = f
434
435	case *Mpcplx:
436		f := newMpflt()
437		f.Set(&u.Real)
438		if u.Imag.CmpFloat64(0) != 0 {
439			yyerror("constant %v truncated to real", u.GoString())
440		}
441		v.U = f
442	}
443
444	return v
445}
446
447func toint(v Val) Val {
448	switch u := v.U.(type) {
449	case *Mpint:
450		if u.Rune {
451			i := new(Mpint)
452			i.Set(u)
453			v.U = i
454		}
455
456	case *Mpflt:
457		i := new(Mpint)
458		if !i.SetFloat(u) {
459			if i.checkOverflow(0) {
460				yyerror("integer too large")
461			} else {
462				// The value of u cannot be represented as an integer;
463				// so we need to print an error message.
464				// Unfortunately some float values cannot be
465				// reasonably formatted for inclusion in an error
466				// message (example: 1 + 1e-100), so first we try to
467				// format the float; if the truncation resulted in
468				// something that looks like an integer we omit the
469				// value from the error message.
470				// (See issue #11371).
471				var t big.Float
472				t.Parse(u.GoString(), 10)
473				if t.IsInt() {
474					yyerror("constant truncated to integer")
475				} else {
476					yyerror("constant %v truncated to integer", u.GoString())
477				}
478			}
479		}
480		v.U = i
481
482	case *Mpcplx:
483		i := new(Mpint)
484		if !i.SetFloat(&u.Real) || u.Imag.CmpFloat64(0) != 0 {
485			yyerror("constant %v truncated to integer", u.GoString())
486		}
487
488		v.U = i
489	}
490
491	return v
492}
493
494func doesoverflow(v Val, t *types.Type) bool {
495	switch u := v.U.(type) {
496	case *Mpint:
497		if !t.IsInteger() {
498			Fatalf("overflow: %v integer constant", t)
499		}
500		return u.Cmp(minintval[t.Etype]) < 0 || u.Cmp(maxintval[t.Etype]) > 0
501
502	case *Mpflt:
503		if !t.IsFloat() {
504			Fatalf("overflow: %v floating-point constant", t)
505		}
506		return u.Cmp(minfltval[t.Etype]) <= 0 || u.Cmp(maxfltval[t.Etype]) >= 0
507
508	case *Mpcplx:
509		if !t.IsComplex() {
510			Fatalf("overflow: %v complex constant", t)
511		}
512		return u.Real.Cmp(minfltval[t.Etype]) <= 0 || u.Real.Cmp(maxfltval[t.Etype]) >= 0 ||
513			u.Imag.Cmp(minfltval[t.Etype]) <= 0 || u.Imag.Cmp(maxfltval[t.Etype]) >= 0
514	}
515
516	return false
517}
518
519func overflow(v Val, t *types.Type) bool {
520	// v has already been converted
521	// to appropriate form for t.
522	if t == nil || t.Etype == TIDEAL {
523		return false
524	}
525
526	// Only uintptrs may be converted to pointers, which cannot overflow.
527	if t.IsPtr() || t.IsUnsafePtr() {
528		return false
529	}
530
531	if doesoverflow(v, t) {
532		yyerror("constant %v overflows %v", v, t)
533		return true
534	}
535
536	return false
537
538}
539
540func tostr(v Val) Val {
541	switch u := v.U.(type) {
542	case *Mpint:
543		var i int64 = 0xFFFD
544		if u.Cmp(minintval[TUINT32]) >= 0 && u.Cmp(maxintval[TUINT32]) <= 0 {
545			i = u.Int64()
546		}
547		v.U = string(i)
548	}
549
550	return v
551}
552
553func consttype(n *Node) Ctype {
554	if n == nil || n.Op != OLITERAL {
555		return CTxxx
556	}
557	return n.Val().Ctype()
558}
559
560func Isconst(n *Node, ct Ctype) bool {
561	t := consttype(n)
562
563	// If the caller is asking for CTINT, allow CTRUNE too.
564	// Makes life easier for back ends.
565	return t == ct || (ct == CTINT && t == CTRUNE)
566}
567
568// evconst rewrites constant expressions into OLITERAL nodes.
569func evconst(n *Node) {
570	nl, nr := n.Left, n.Right
571
572	// Pick off just the opcodes that can be constant evaluated.
573	switch op := n.Op; op {
574	case OPLUS, ONEG, OBITNOT, ONOT:
575		if nl.Op == OLITERAL {
576			setconst(n, unaryOp(op, nl.Val(), n.Type))
577		}
578
579	case OADD, OSUB, OMUL, ODIV, OMOD, OOR, OXOR, OAND, OANDNOT, OOROR, OANDAND:
580		if nl.Op == OLITERAL && nr.Op == OLITERAL {
581			setconst(n, binaryOp(nl.Val(), op, nr.Val()))
582		}
583
584	case OEQ, ONE, OLT, OLE, OGT, OGE:
585		if nl.Op == OLITERAL && nr.Op == OLITERAL {
586			setboolconst(n, compareOp(nl.Val(), op, nr.Val()))
587		}
588
589	case OLSH, ORSH:
590		if nl.Op == OLITERAL && nr.Op == OLITERAL {
591			setconst(n, shiftOp(nl.Val(), op, nr.Val()))
592		}
593
594	case OCONV, ORUNESTR:
595		if okforconst[n.Type.Etype] && nl.Op == OLITERAL {
596			setconst(n, convertVal(nl.Val(), n.Type, true))
597		}
598
599	case OCONVNOP:
600		if okforconst[n.Type.Etype] && nl.Op == OLITERAL {
601			// set so n.Orig gets OCONV instead of OCONVNOP
602			n.Op = OCONV
603			setconst(n, nl.Val())
604		}
605
606	case OADDSTR:
607		// Merge adjacent constants in the argument list.
608		s := n.List.Slice()
609		for i1 := 0; i1 < len(s); i1++ {
610			if Isconst(s[i1], CTSTR) && i1+1 < len(s) && Isconst(s[i1+1], CTSTR) {
611				// merge from i1 up to but not including i2
612				var strs []string
613				i2 := i1
614				for i2 < len(s) && Isconst(s[i2], CTSTR) {
615					strs = append(strs, strlit(s[i2]))
616					i2++
617				}
618
619				nl := *s[i1]
620				nl.Orig = &nl
621				nl.SetVal(Val{strings.Join(strs, "")})
622				s[i1] = &nl
623				s = append(s[:i1+1], s[i2:]...)
624			}
625		}
626
627		if len(s) == 1 && Isconst(s[0], CTSTR) {
628			n.Op = OLITERAL
629			n.SetVal(s[0].Val())
630		} else {
631			n.List.Set(s)
632		}
633
634	case OCAP, OLEN:
635		switch nl.Type.Etype {
636		case TSTRING:
637			if Isconst(nl, CTSTR) {
638				setintconst(n, int64(len(strlit(nl))))
639			}
640		case TARRAY:
641			if !hascallchan(nl) {
642				setintconst(n, nl.Type.NumElem())
643			}
644		}
645
646	case OALIGNOF, OOFFSETOF, OSIZEOF:
647		setintconst(n, evalunsafe(n))
648
649	case OREAL, OIMAG:
650		if nl.Op == OLITERAL {
651			var re, im *Mpflt
652			switch u := nl.Val().U.(type) {
653			case *Mpint:
654				re = newMpflt()
655				re.SetInt(u)
656				// im = 0
657			case *Mpflt:
658				re = u
659				// im = 0
660			case *Mpcplx:
661				re = &u.Real
662				im = &u.Imag
663			default:
664				Fatalf("impossible")
665			}
666			if n.Op == OIMAG {
667				if im == nil {
668					im = newMpflt()
669				}
670				re = im
671			}
672			setconst(n, Val{re})
673		}
674
675	case OCOMPLEX:
676		if nl == nil || nr == nil {
677			// TODO(mdempsky): Remove after early OAS2FUNC rewrite CL lands.
678			break
679		}
680		if nl.Op == OLITERAL && nr.Op == OLITERAL {
681			// make it a complex literal
682			c := newMpcmplx()
683			c.Real.Set(toflt(nl.Val()).U.(*Mpflt))
684			c.Imag.Set(toflt(nr.Val()).U.(*Mpflt))
685			setconst(n, Val{c})
686		}
687	}
688}
689
690func match(x, y Val) (Val, Val) {
691	switch {
692	case x.Ctype() == CTCPLX || y.Ctype() == CTCPLX:
693		return tocplx(x), tocplx(y)
694	case x.Ctype() == CTFLT || y.Ctype() == CTFLT:
695		return toflt(x), toflt(y)
696	}
697
698	// Mixed int/rune are fine.
699	return x, y
700}
701
702func compareOp(x Val, op Op, y Val) bool {
703	x, y = match(x, y)
704
705	switch x.Ctype() {
706	case CTBOOL:
707		x, y := x.U.(bool), y.U.(bool)
708		switch op {
709		case OEQ:
710			return x == y
711		case ONE:
712			return x != y
713		}
714
715	case CTINT, CTRUNE:
716		x, y := x.U.(*Mpint), y.U.(*Mpint)
717		return cmpZero(x.Cmp(y), op)
718
719	case CTFLT:
720		x, y := x.U.(*Mpflt), y.U.(*Mpflt)
721		return cmpZero(x.Cmp(y), op)
722
723	case CTCPLX:
724		x, y := x.U.(*Mpcplx), y.U.(*Mpcplx)
725		eq := x.Real.Cmp(&y.Real) == 0 && x.Imag.Cmp(&y.Imag) == 0
726		switch op {
727		case OEQ:
728			return eq
729		case ONE:
730			return !eq
731		}
732
733	case CTSTR:
734		x, y := x.U.(string), y.U.(string)
735		switch op {
736		case OEQ:
737			return x == y
738		case ONE:
739			return x != y
740		case OLT:
741			return x < y
742		case OLE:
743			return x <= y
744		case OGT:
745			return x > y
746		case OGE:
747			return x >= y
748		}
749	}
750
751	Fatalf("compareOp: bad comparison: %v %v %v", x, op, y)
752	panic("unreachable")
753}
754
755func cmpZero(x int, op Op) bool {
756	switch op {
757	case OEQ:
758		return x == 0
759	case ONE:
760		return x != 0
761	case OLT:
762		return x < 0
763	case OLE:
764		return x <= 0
765	case OGT:
766		return x > 0
767	case OGE:
768		return x >= 0
769	}
770
771	Fatalf("cmpZero: want comparison operator, got %v", op)
772	panic("unreachable")
773}
774
775func binaryOp(x Val, op Op, y Val) Val {
776	x, y = match(x, y)
777
778Outer:
779	switch x.Ctype() {
780	case CTBOOL:
781		x, y := x.U.(bool), y.U.(bool)
782		switch op {
783		case OANDAND:
784			return Val{U: x && y}
785		case OOROR:
786			return Val{U: x || y}
787		}
788
789	case CTINT, CTRUNE:
790		x, y := x.U.(*Mpint), y.U.(*Mpint)
791
792		u := new(Mpint)
793		u.Rune = x.Rune || y.Rune
794		u.Set(x)
795		switch op {
796		case OADD:
797			u.Add(y)
798		case OSUB:
799			u.Sub(y)
800		case OMUL:
801			u.Mul(y)
802		case ODIV:
803			if y.CmpInt64(0) == 0 {
804				yyerror("division by zero")
805				return Val{}
806			}
807			u.Quo(y)
808		case OMOD:
809			if y.CmpInt64(0) == 0 {
810				yyerror("division by zero")
811				return Val{}
812			}
813			u.Rem(y)
814		case OOR:
815			u.Or(y)
816		case OAND:
817			u.And(y)
818		case OANDNOT:
819			u.AndNot(y)
820		case OXOR:
821			u.Xor(y)
822		default:
823			break Outer
824		}
825		return Val{U: u}
826
827	case CTFLT:
828		x, y := x.U.(*Mpflt), y.U.(*Mpflt)
829
830		u := newMpflt()
831		u.Set(x)
832		switch op {
833		case OADD:
834			u.Add(y)
835		case OSUB:
836			u.Sub(y)
837		case OMUL:
838			u.Mul(y)
839		case ODIV:
840			if y.CmpFloat64(0) == 0 {
841				yyerror("division by zero")
842				return Val{}
843			}
844			u.Quo(y)
845		case OMOD, OOR, OAND, OANDNOT, OXOR:
846			// TODO(mdempsky): Move to typecheck; see #31060.
847			yyerror("invalid operation: operator %v not defined on untyped float", op)
848			return Val{}
849		default:
850			break Outer
851		}
852		return Val{U: u}
853
854	case CTCPLX:
855		x, y := x.U.(*Mpcplx), y.U.(*Mpcplx)
856
857		u := newMpcmplx()
858		u.Real.Set(&x.Real)
859		u.Imag.Set(&x.Imag)
860		switch op {
861		case OADD:
862			u.Real.Add(&y.Real)
863			u.Imag.Add(&y.Imag)
864		case OSUB:
865			u.Real.Sub(&y.Real)
866			u.Imag.Sub(&y.Imag)
867		case OMUL:
868			u.Mul(y)
869		case ODIV:
870			if !u.Div(y) {
871				yyerror("complex division by zero")
872				return Val{}
873			}
874		case OMOD, OOR, OAND, OANDNOT, OXOR:
875			// TODO(mdempsky): Move to typecheck; see #31060.
876			yyerror("invalid operation: operator %v not defined on untyped complex", op)
877			return Val{}
878		default:
879			break Outer
880		}
881		return Val{U: u}
882	}
883
884	Fatalf("binaryOp: bad operation: %v %v %v", x, op, y)
885	panic("unreachable")
886}
887
888func unaryOp(op Op, x Val, t *types.Type) Val {
889	switch op {
890	case OPLUS:
891		switch x.Ctype() {
892		case CTINT, CTRUNE, CTFLT, CTCPLX:
893			return x
894		}
895
896	case ONEG:
897		switch x.Ctype() {
898		case CTINT, CTRUNE:
899			x := x.U.(*Mpint)
900			u := new(Mpint)
901			u.Rune = x.Rune
902			u.Set(x)
903			u.Neg()
904			return Val{U: u}
905
906		case CTFLT:
907			x := x.U.(*Mpflt)
908			u := newMpflt()
909			u.Set(x)
910			u.Neg()
911			return Val{U: u}
912
913		case CTCPLX:
914			x := x.U.(*Mpcplx)
915			u := newMpcmplx()
916			u.Real.Set(&x.Real)
917			u.Imag.Set(&x.Imag)
918			u.Real.Neg()
919			u.Imag.Neg()
920			return Val{U: u}
921		}
922
923	case OBITNOT:
924		switch x.Ctype() {
925		case CTINT, CTRUNE:
926			x := x.U.(*Mpint)
927
928			u := new(Mpint)
929			u.Rune = x.Rune
930			if t.IsSigned() || t.IsUntyped() {
931				// Signed values change sign.
932				u.SetInt64(-1)
933			} else {
934				// Unsigned values invert their bits.
935				u.Set(maxintval[t.Etype])
936			}
937			u.Xor(x)
938			return Val{U: u}
939
940		case CTFLT:
941			// TODO(mdempsky): Move to typecheck; see #31060.
942			yyerror("invalid operation: operator %v not defined on untyped float", op)
943			return Val{}
944		case CTCPLX:
945			// TODO(mdempsky): Move to typecheck; see #31060.
946			yyerror("invalid operation: operator %v not defined on untyped complex", op)
947			return Val{}
948		}
949
950	case ONOT:
951		return Val{U: !x.U.(bool)}
952	}
953
954	Fatalf("unaryOp: bad operation: %v %v", op, x)
955	panic("unreachable")
956}
957
958func shiftOp(x Val, op Op, y Val) Val {
959	if x.Ctype() != CTRUNE {
960		x = toint(x)
961	}
962	y = toint(y)
963
964	u := new(Mpint)
965	u.Set(x.U.(*Mpint))
966	u.Rune = x.U.(*Mpint).Rune
967	switch op {
968	case OLSH:
969		u.Lsh(y.U.(*Mpint))
970	case ORSH:
971		u.Rsh(y.U.(*Mpint))
972	default:
973		Fatalf("shiftOp: bad operator: %v", op)
974		panic("unreachable")
975	}
976	return Val{U: u}
977}
978
979// setconst rewrites n as an OLITERAL with value v.
980func setconst(n *Node, v Val) {
981	// If constant folding failed, mark n as broken and give up.
982	if v.U == nil {
983		n.Type = nil
984		return
985	}
986
987	// Ensure n.Orig still points to a semantically-equivalent
988	// expression after we rewrite n into a constant.
989	if n.Orig == n {
990		n.Orig = n.sepcopy()
991	}
992
993	*n = Node{
994		Op:      OLITERAL,
995		Pos:     n.Pos,
996		Orig:    n.Orig,
997		Type:    n.Type,
998		Xoffset: BADWIDTH,
999	}
1000	n.SetVal(v)
1001	if n.Type.IsUntyped() {
1002		// TODO(mdempsky): Make typecheck responsible for setting
1003		// the correct untyped type.
1004		n.Type = idealType(v.Ctype())
1005	}
1006
1007	// Check range.
1008	lno := setlineno(n)
1009	overflow(v, n.Type)
1010	lineno = lno
1011
1012	if !n.Type.IsUntyped() {
1013		switch v.Ctype() {
1014		// Truncate precision for non-ideal float.
1015		case CTFLT:
1016			n.SetVal(Val{truncfltlit(v.U.(*Mpflt), n.Type)})
1017		// Truncate precision for non-ideal complex.
1018		case CTCPLX:
1019			n.SetVal(Val{trunccmplxlit(v.U.(*Mpcplx), n.Type)})
1020		}
1021	}
1022}
1023
1024func setboolconst(n *Node, v bool) {
1025	setconst(n, Val{U: v})
1026}
1027
1028func setintconst(n *Node, v int64) {
1029	u := new(Mpint)
1030	u.SetInt64(v)
1031	setconst(n, Val{u})
1032}
1033
1034// nodlit returns a new untyped constant with value v.
1035func nodlit(v Val) *Node {
1036	n := nod(OLITERAL, nil, nil)
1037	n.SetVal(v)
1038	n.Type = idealType(v.Ctype())
1039	return n
1040}
1041
1042func idealType(ct Ctype) *types.Type {
1043	switch ct {
1044	case CTSTR:
1045		return types.Idealstring
1046	case CTBOOL:
1047		return types.Idealbool
1048	case CTINT:
1049		return types.Idealint
1050	case CTRUNE:
1051		return types.Idealrune
1052	case CTFLT:
1053		return types.Idealfloat
1054	case CTCPLX:
1055		return types.Idealcomplex
1056	case CTNIL:
1057		return types.Types[TNIL]
1058	}
1059	Fatalf("unexpected Ctype: %v", ct)
1060	return nil
1061}
1062
1063// idealkind returns a constant kind like consttype
1064// but for an arbitrary "ideal" (untyped constant) expression.
1065func idealkind(n *Node) Ctype {
1066	if n == nil || !n.Type.IsUntyped() {
1067		return CTxxx
1068	}
1069
1070	switch n.Op {
1071	default:
1072		return CTxxx
1073
1074	case OLITERAL:
1075		return n.Val().Ctype()
1076
1077		// numeric kinds.
1078	case OADD,
1079		OAND,
1080		OANDNOT,
1081		OBITNOT,
1082		ODIV,
1083		ONEG,
1084		OMOD,
1085		OMUL,
1086		OSUB,
1087		OXOR,
1088		OOR,
1089		OPLUS:
1090		k1 := idealkind(n.Left)
1091		k2 := idealkind(n.Right)
1092		if k1 > k2 {
1093			return k1
1094		} else {
1095			return k2
1096		}
1097
1098	case OREAL, OIMAG:
1099		return CTFLT
1100
1101	case OCOMPLEX:
1102		return CTCPLX
1103
1104	case OADDSTR:
1105		return CTSTR
1106
1107	case OANDAND,
1108		OEQ,
1109		OGE,
1110		OGT,
1111		OLE,
1112		OLT,
1113		ONE,
1114		ONOT,
1115		OOROR:
1116		return CTBOOL
1117
1118		// shifts (beware!).
1119	case OLSH, ORSH:
1120		return idealkind(n.Left)
1121	}
1122}
1123
1124// defaultlit on both nodes simultaneously;
1125// if they're both ideal going in they better
1126// get the same type going out.
1127// force means must assign concrete (non-ideal) type.
1128// The results of defaultlit2 MUST be assigned back to l and r, e.g.
1129// 	n.Left, n.Right = defaultlit2(n.Left, n.Right, force)
1130func defaultlit2(l *Node, r *Node, force bool) (*Node, *Node) {
1131	if l.Type == nil || r.Type == nil {
1132		return l, r
1133	}
1134	if !l.Type.IsUntyped() {
1135		r = convlit(r, l.Type)
1136		return l, r
1137	}
1138
1139	if !r.Type.IsUntyped() {
1140		l = convlit(l, r.Type)
1141		return l, r
1142	}
1143
1144	if !force {
1145		return l, r
1146	}
1147
1148	// Can't mix bool with non-bool, string with non-string, or nil with anything (untyped).
1149	if l.Type.IsBoolean() != r.Type.IsBoolean() {
1150		return l, r
1151	}
1152	if l.Type.IsString() != r.Type.IsString() {
1153		return l, r
1154	}
1155	if l.isNil() || r.isNil() {
1156		return l, r
1157	}
1158
1159	k := idealkind(l)
1160	if rk := idealkind(r); rk > k {
1161		k = rk
1162	}
1163	t := defaultType(k)
1164	l = convlit(l, t)
1165	r = convlit(r, t)
1166	return l, r
1167}
1168
1169func defaultType(k Ctype) *types.Type {
1170	switch k {
1171	case CTBOOL:
1172		return types.Types[TBOOL]
1173	case CTSTR:
1174		return types.Types[TSTRING]
1175	case CTINT:
1176		return types.Types[TINT]
1177	case CTRUNE:
1178		return types.Runetype
1179	case CTFLT:
1180		return types.Types[TFLOAT64]
1181	case CTCPLX:
1182		return types.Types[TCOMPLEX128]
1183	}
1184	Fatalf("bad idealkind: %v", k)
1185	return nil
1186}
1187
1188// strlit returns the value of a literal string Node as a string.
1189func strlit(n *Node) string {
1190	return n.Val().U.(string)
1191}
1192
1193// TODO(gri) smallintconst is only used in one place - can we used indexconst?
1194func smallintconst(n *Node) bool {
1195	if n.Op == OLITERAL && Isconst(n, CTINT) && n.Type != nil {
1196		switch simtype[n.Type.Etype] {
1197		case TINT8,
1198			TUINT8,
1199			TINT16,
1200			TUINT16,
1201			TINT32,
1202			TUINT32,
1203			TBOOL:
1204			return true
1205
1206		case TIDEAL, TINT64, TUINT64, TPTR:
1207			v, ok := n.Val().U.(*Mpint)
1208			if ok && v.Cmp(minintval[TINT32]) >= 0 && v.Cmp(maxintval[TINT32]) <= 0 {
1209				return true
1210			}
1211		}
1212	}
1213
1214	return false
1215}
1216
1217// indexconst checks if Node n contains a constant expression
1218// representable as a non-negative int and returns its value.
1219// If n is not a constant expression, not representable as an
1220// integer, or negative, it returns -1. If n is too large, it
1221// returns -2.
1222func indexconst(n *Node) int64 {
1223	if n.Op != OLITERAL {
1224		return -1
1225	}
1226
1227	v := toint(n.Val()) // toint returns argument unchanged if not representable as an *Mpint
1228	vi, ok := v.U.(*Mpint)
1229	if !ok || vi.CmpInt64(0) < 0 {
1230		return -1
1231	}
1232	if vi.Cmp(maxintval[TINT]) > 0 {
1233		return -2
1234	}
1235
1236	return vi.Int64()
1237}
1238
1239// isGoConst reports whether n is a Go language constant (as opposed to a
1240// compile-time constant).
1241//
1242// Expressions derived from nil, like string([]byte(nil)), while they
1243// may be known at compile time, are not Go language constants.
1244func (n *Node) isGoConst() bool {
1245	return n.Op == OLITERAL && n.Val().Ctype() != CTNIL
1246}
1247
1248func hascallchan(n *Node) bool {
1249	if n == nil {
1250		return false
1251	}
1252	switch n.Op {
1253	case OAPPEND,
1254		OCALL,
1255		OCALLFUNC,
1256		OCALLINTER,
1257		OCALLMETH,
1258		OCAP,
1259		OCLOSE,
1260		OCOMPLEX,
1261		OCOPY,
1262		ODELETE,
1263		OIMAG,
1264		OLEN,
1265		OMAKE,
1266		ONEW,
1267		OPANIC,
1268		OPRINT,
1269		OPRINTN,
1270		OREAL,
1271		ORECOVER,
1272		ORECV:
1273		return true
1274	}
1275
1276	if hascallchan(n.Left) || hascallchan(n.Right) {
1277		return true
1278	}
1279	for _, n1 := range n.List.Slice() {
1280		if hascallchan(n1) {
1281			return true
1282		}
1283	}
1284	for _, n2 := range n.Rlist.Slice() {
1285		if hascallchan(n2) {
1286			return true
1287		}
1288	}
1289
1290	return false
1291}
1292
1293// A constSet represents a set of Go constant expressions.
1294type constSet struct {
1295	m map[constSetKey]src.XPos
1296}
1297
1298type constSetKey struct {
1299	typ *types.Type
1300	val interface{}
1301}
1302
1303// add adds constant expression n to s. If a constant expression of
1304// equal value and identical type has already been added, then add
1305// reports an error about the duplicate value.
1306//
1307// pos provides position information for where expression n occurred
1308// (in case n does not have its own position information). what and
1309// where are used in the error message.
1310//
1311// n must not be an untyped constant.
1312func (s *constSet) add(pos src.XPos, n *Node, what, where string) {
1313	if n.Op == OCONVIFACE && n.Implicit() {
1314		n = n.Left
1315	}
1316
1317	if !n.isGoConst() {
1318		return
1319	}
1320	if n.Type.IsUntyped() {
1321		Fatalf("%v is untyped", n)
1322	}
1323
1324	// Consts are only duplicates if they have the same value and
1325	// identical types.
1326	//
1327	// In general, we have to use types.Identical to test type
1328	// identity, because == gives false negatives for anonymous
1329	// types and the byte/uint8 and rune/int32 builtin type
1330	// aliases.  However, this is not a problem here, because
1331	// constant expressions are always untyped or have a named
1332	// type, and we explicitly handle the builtin type aliases
1333	// below.
1334	//
1335	// This approach may need to be revisited though if we fix
1336	// #21866 by treating all type aliases like byte/uint8 and
1337	// rune/int32.
1338
1339	typ := n.Type
1340	switch typ {
1341	case types.Bytetype:
1342		typ = types.Types[TUINT8]
1343	case types.Runetype:
1344		typ = types.Types[TINT32]
1345	}
1346	k := constSetKey{typ, n.Val().Interface()}
1347
1348	if hasUniquePos(n) {
1349		pos = n.Pos
1350	}
1351
1352	if s.m == nil {
1353		s.m = make(map[constSetKey]src.XPos)
1354	}
1355
1356	if prevPos, isDup := s.m[k]; isDup {
1357		yyerrorl(pos, "duplicate %s %s in %s\n\tprevious %s at %v",
1358			what, nodeAndVal(n), where,
1359			what, linestr(prevPos))
1360	} else {
1361		s.m[k] = pos
1362	}
1363}
1364
1365// nodeAndVal reports both an expression and its constant value, if
1366// the latter is non-obvious.
1367//
1368// TODO(mdempsky): This could probably be a fmt.go flag.
1369func nodeAndVal(n *Node) string {
1370	show := n.String()
1371	val := n.Val().Interface()
1372	if s := fmt.Sprintf("%#v", val); show != s {
1373		show += " (value " + s + ")"
1374	}
1375	return show
1376}
1377