expr.go 48.1 KB
Newer Older
1 2 3 4 5 6 7
// 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 eval

import (
8 9 10 11 12 13 14
	"bignum"
	"go/ast"
	"go/token"
	"log"
	"strconv"
	"strings"
	"os"
15 16
)

17 18 19
// An expr is the result of compiling an expression.  It stores the
// type of the expression and its evaluator function.
type expr struct {
20 21
	*exprInfo
	t Type
22

23
	// Evaluate this node as the given type.
24
	eval interface{}
25

Austin Clements's avatar
Austin Clements committed
26 27
	// Map index expressions permit special forms of assignment,
	// for which we need to know the Map and key.
28
	evalMapValue func(t *Thread) (Map, interface{})
29

30 31 32
	// Evaluate to the "address of" this value; that is, the
	// settable Value object.  nil for expressions whose address
	// cannot be taken.
33
	evalAddr func(t *Thread) Value
34

35 36
	// Execute this expression as a statement.  Only expressions
	// that are valid expression statements should set this.
37
	exec func(t *Thread)
38

39 40 41
	// If this expression is a type, this is its compiled type.
	// This is only permitted in the function position of a call
	// expression.  In this case, t should be nil.
42
	valType Type
43

44
	// A short string describing this expression for error
45
	// messages.
46
	desc string
47 48
}

49 50 51 52
// exprInfo stores information needed to compile any expression node.
// Each expr also stores its exprInfo so further expressions can be
// compiled from it.
type exprInfo struct {
53 54
	*compiler
	pos token.Position
55 56
}

57
func (a *exprInfo) newExpr(t Type, desc string) *expr {
58
	return &expr{exprInfo: a, t: t, desc: desc}
59 60
}

61
func (a *exprInfo) diag(format string, args ...) {
62
	a.diagAt(&a.pos, format, args)
63 64
}

65
func (a *exprInfo) diagOpType(op token.Token, vt Type) {
66
	a.diag("illegal operand type for '%v' operator\n\t%v", op, vt)
67 68
}

69
func (a *exprInfo) diagOpTypes(op token.Token, lt Type, rt Type) {
70
	a.diag("illegal operand types for '%v' operator\n\t%v\n\t%v", op, lt, rt)
71 72
}

73 74 75 76 77 78 79
/*
 * Common expression manipulations
 */

// a.convertTo(t) converts the value of the analyzed expression a,
// which must be a constant, ideal number, to a new analyzed
// expression with a constant value of type t.
80 81
//
// TODO(austin) Rename to resolveIdeal or something?
82
func (a *expr) convertTo(t Type) *expr {
83
	if !a.t.isIdeal() {
84
		log.Crashf("attempted to convert from %v, expected ideal", a.t)
85 86
	}

87
	var rat *bignum.Rational
88 89 90 91 92 93 94 95 96

	// XXX(Spec)  The spec says "It is erroneous".
	//
	// It is an error to assign a value with a non-zero fractional
	// part to an integer, or if the assignment would overflow or
	// underflow, or in general if the value cannot be represented
	// by the type of the variable.
	switch a.t {
	case IdealFloatType:
97
		rat = a.asIdealFloat()()
98
		if t.isInteger() && !rat.IsInt() {
99 100
			a.diag("constant %v truncated to integer", ratToString(rat))
			return nil
101 102
		}
	case IdealIntType:
103 104
		i := a.asIdealInt()()
		rat = bignum.MakeRat(i, bignum.Nat(1))
105
	default:
106
		log.Crashf("unexpected ideal type %v", a.t)
107 108 109
	}

	// Check bounds
110
	if t, ok := t.lit().(BoundedType); ok {
111
		if rat.Cmp(t.minVal()) < 0 {
112 113
			a.diag("constant %v underflows %v", ratToString(rat), t)
			return nil
114 115
		}
		if rat.Cmp(t.maxVal()) > 0 {
116 117
			a.diag("constant %v overflows %v", ratToString(rat), t)
			return nil
118 119 120 121
		}
	}

	// Convert rat to type t.
122
	res := a.newExpr(t, a.desc)
123
	switch t := t.lit().(type) {
124
	case *uintType:
125 126 127 128
		n, d := rat.Value()
		f := n.Quo(bignum.MakeInt(false, d))
		v := f.Abs().Value()
		res.eval = func(*Thread) uint64 { return v }
129
	case *intType:
130 131 132 133
		n, d := rat.Value()
		f := n.Quo(bignum.MakeInt(false, d))
		v := f.Value()
		res.eval = func(*Thread) int64 { return v }
134
	case *idealIntType:
135 136 137
		n, d := rat.Value()
		f := n.Quo(bignum.MakeInt(false, d))
		res.eval = func() *bignum.Integer { return f }
138
	case *floatType:
139 140 141
		n, d := rat.Value()
		v := float64(n.Value()) / float64(d.Value())
		res.eval = func(*Thread) float64 { return v }
142
	case *idealFloatType:
143
		res.eval = func() *bignum.Rational { return rat }
144
	default:
145
		log.Crashf("cannot convert to type %T", t)
146 147
	}

148
	return res
149 150
}

151 152 153 154 155 156
// convertToInt converts this expression to an integer, if possible,
// or produces an error if not.  This accepts ideal ints, uints, and
// ints.  If max is not -1, produces an error if possible if the value
// exceeds max.  If negErr is not "", produces an error if possible if
// the value is negative.
func (a *expr) convertToInt(max int64, negErr string, errOp string) *expr {
Austin Clements's avatar
Austin Clements committed
157
	switch a.t.lit().(type) {
158
	case *idealIntType:
159
		val := a.asIdealInt()()
160
		if negErr != "" && val.IsNeg() {
161 162
			a.diag("negative %s: %s", negErr, val)
			return nil
163
		}
164
		bound := max
Russ Cox's avatar
Russ Cox committed
165
		if negErr == "slice" {
166
			bound++
Russ Cox's avatar
Russ Cox committed
167 168
		}
		if max != -1 && val.Cmp(bignum.Int(bound)) >= 0 {
169 170
			a.diag("index %s exceeds length %d", val, max)
			return nil
171
		}
172
		return a.convertTo(IntType)
173 174 175

	case *uintType:
		// Convert to int
176 177 178 179
		na := a.newExpr(IntType, a.desc)
		af := a.asUint()
		na.eval = func(t *Thread) int64 { return int64(af(t)) }
		return na
180 181 182

	case *intType:
		// Good as is
183
		return a
184 185
	}

186 187
	a.diag("illegal operand type for %s\n\t%v", errOp, a.t)
	return nil
188 189 190 191 192 193 194
}

// derefArray returns an expression of array type if the given
// expression is a *array type.  Otherwise, returns the given
// expression.
func (a *expr) derefArray() *expr {
	if pt, ok := a.t.lit().(*PtrType); ok {
195
		if _, ok := pt.Elem.lit().(*ArrayType); ok {
196
			deref := a.compileStarExpr(a)
197
			if deref == nil {
198
				log.Crashf("failed to dereference *array")
199
			}
200
			return deref
201 202
		}
	}
203
	return a
204 205
}

206 207 208 209 210 211
/*
 * Assignments
 */

// An assignCompiler compiles assignment operations.  Anything other
// than short declarations should use the compileAssign wrapper.
212
//
213 214 215 216 217 218 219 220 221 222 223
// There are three valid types of assignment:
// 1) T = T
//    Assigning a single expression with single-valued type to a
//    single-valued type.
// 2) MT = T, T, ...
//    Assigning multiple expressions with single-valued types to a
//    multi-valued type.
// 3) MT = MT
//    Assigning a single expression with multi-valued type to a
//    multi-valued type.
type assignCompiler struct {
224 225
	*compiler
	pos token.Position
226 227
	// The RHS expressions.  This may include nil's for
	// expressions that failed to compile.
228
	rs []*expr
229
	// The (possibly unary) MultiType of the RHS.
230
	rmt *MultiType
231
	// Whether this is an unpack assignment (case 3).
232
	isUnpack bool
Austin Clements's avatar
Austin Clements committed
233
	// Whether map special assignment forms are allowed.
234
	allowMap bool
Austin Clements's avatar
Austin Clements committed
235
	// Whether this is a "r, ok = a[x]" assignment.
236
	isMapUnpack bool
237 238
	// The operation name to use in error messages, such as
	// "assignment" or "function call".
239
	errOp string
240 241
	// The name to use for positions in error messages, such as
	// "argument".
242
	errPosName string
243 244 245 246 247 248 249
}

// Type check the RHS of an assignment, returning a new assignCompiler
// and indicating if the type check succeeded.  This always returns an
// assignCompiler with rmt set, but if type checking fails, slots in
// the MultiType may be nil.  If rs contains nil's, type checking will
// fail and these expressions given a nil type.
250
func (a *compiler) checkAssign(pos token.Position, rs []*expr, errOp, errPosName string) (*assignCompiler, bool) {
251 252 253 254 255 256
	c := &assignCompiler{
		compiler: a,
		pos: pos,
		rs: rs,
		errOp: errOp,
		errPosName: errPosName,
257
	}
258 259 260 261

	// Is this an unpack?
	if len(rs) == 1 && rs[0] != nil {
		if rmt, isUnpack := rs[0].t.(*MultiType); isUnpack {
262 263 264
			c.rmt = rmt
			c.isUnpack = true
			return c, true
265
		}
266 267 268 269
	}

	// Create MultiType for RHS and check that all RHS expressions
	// are single-valued.
270 271
	rts := make([]Type, len(rs))
	ok := true
272
	for i, r := range rs {
273
		if r == nil {
274 275
			ok = false
			continue
276 277 278
		}

		if _, isMT := r.t.(*MultiType); isMT {
279 280 281
			r.diag("multi-valued expression not allowed in %s", errOp)
			ok = false
			continue
282 283
		}

284
		rts[i] = r.t
285 286
	}

287 288
	c.rmt = NewMultiType(rts)
	return c, ok
289 290
}

Austin Clements's avatar
Austin Clements committed
291
func (a *assignCompiler) allowMapForms(nls int) {
292
	a.allowMap = true
Austin Clements's avatar
Austin Clements committed
293 294

	// Update unpacking info if this is r, ok = a[x]
Russ Cox's avatar
Russ Cox committed
295
	if nls == 2 && len(a.rs) == 1 && a.rs[0] != nil && a.rs[0].evalMapValue != nil {
296 297 298
		a.isUnpack = true
		a.rmt = NewMultiType([]Type{a.rs[0].t, BoolType})
		a.isMapUnpack = true
Austin Clements's avatar
Austin Clements committed
299 300 301
	}
}

302 303 304 305
// compile type checks and compiles an assignment operation, returning
// a function that expects an l-value and the frame in which to
// evaluate the RHS expressions.  The l-value must have exactly the
// type given by lt.  Returns nil if type checking fails.
Russ Cox's avatar
Russ Cox committed
306
func (a *assignCompiler) compile(b *block, lt Type) (func(Value, *Thread)) {
307 308
	lmt, isMT := lt.(*MultiType)
	rmt, isUnpack := a.rmt, a.isUnpack
309 310 311

	// Create unary MultiType for single LHS
	if !isMT {
312
		lmt = NewMultiType([]Type{lt})
313 314 315
	}

	// Check that the assignment count matches
316 317
	lcount := len(lmt.Elems)
	rcount := len(rmt.Elems)
318
	if lcount != rcount {
319 320
		msg := "not enough"
		pos := a.pos
321
		if rcount > lcount {
322
			msg = "too many"
323
			if lcount > 0 {
324
				pos = a.rs[lcount-1].pos
325
			}
326
		}
327 328
		a.diagAt(&pos, "%s %ss for %s\n\t%s\n\t%s", msg, a.errPosName, a.errOp, lt, rmt)
		return nil
329 330
	}

331
	bad := false
332

Austin Clements's avatar
Austin Clements committed
333 334 335 336
	// If this is an unpack, create a temporary to store the
	// multi-value and replace the RHS with expressions to pull
	// out values from the temporary.  Technically, this is only
	// necessary when we need to perform assignment conversions.
337
	var effect func(*Thread)
Austin Clements's avatar
Austin Clements committed
338 339
	if isUnpack {
		// This leaks a slot, but is definitely safe.
340 341
		temp := b.DefineTemp(a.rmt)
		tempIdx := temp.Index
Russ Cox's avatar
Russ Cox committed
342
		if tempIdx < 0 {
343
			panicln("tempidx", tempIdx)
Russ Cox's avatar
Russ Cox committed
344
		}
Austin Clements's avatar
Austin Clements committed
345
		if a.isMapUnpack {
346 347
			rf := a.rs[0].evalMapValue
			vt := a.rmt.Elems[0]
Russ Cox's avatar
Russ Cox committed
348
			effect = func(t *Thread) {
349 350 351
				m, k := rf(t)
				v := m.Elem(t, k)
				found := boolV(true)
Austin Clements's avatar
Austin Clements committed
352
				if v == nil {
353 354
					found = boolV(false)
					v = vt.Zero()
Austin Clements's avatar
Austin Clements committed
355
				}
356 357
				t.f.Vars[tempIdx] = multiV([]Value{v, &found})
			}
Austin Clements's avatar
Austin Clements committed
358
		} else {
359 360
			rf := a.rs[0].asMulti()
			effect = func(t *Thread) { t.f.Vars[tempIdx] = multiV(rf(t)) }
Austin Clements's avatar
Austin Clements committed
361
		}
362 363
		orig := a.rs[0]
		a.rs = make([]*expr, len(a.rmt.Elems))
Austin Clements's avatar
Austin Clements committed
364 365
		for i, t := range a.rmt.Elems {
			if t.isIdeal() {
366
				log.Crashf("Right side of unpack contains ideal: %s", rmt)
Austin Clements's avatar
Austin Clements committed
367
			}
368 369 370
			a.rs[i] = orig.newExpr(t, orig.desc)
			index := i
			a.rs[i].genValue(func(t *Thread) Value { return t.f.Vars[tempIdx].(multiV)[index] })
Austin Clements's avatar
Austin Clements committed
371 372 373 374 375
		}
	}
	// Now len(a.rs) == len(a.rmt) and we've reduced any unpacking
	// to multi-assignment.

Austin Clements's avatar
Austin Clements committed
376
	// TODO(austin) Deal with assignment special cases.
377 378 379 380

	// Values of any type may always be assigned to variables of
	// compatible static type.
	for i, lt := range lmt.Elems {
381
		rt := rmt.Elems[i]
382 383 384 385 386

		// When [an ideal is] (used in an expression) assigned
		// to a variable or typed constant, the destination
		// must be able to represent the assigned value.
		if rt.isIdeal() {
387
			a.rs[i] = a.rs[i].convertTo(lmt.Elems[i])
388
			if a.rs[i] == nil {
389 390
				bad = true
				continue
391
			}
392
			rt = a.rs[i].t
393
		}
394

Austin Clements's avatar
Austin Clements committed
395 396 397 398 399 400 401
		// A pointer p to an array can be assigned to a slice
		// variable v with compatible element type if the type
		// of p or v is unnamed.
		if rpt, ok := rt.lit().(*PtrType); ok {
			if at, ok := rpt.Elem.lit().(*ArrayType); ok {
				if lst, ok := lt.lit().(*SliceType); ok {
					if lst.Elem.compat(at.Elem, false) && (rt.lit() == Type(rt) || lt.lit() == Type(lt)) {
402 403 404 405 406
						rf := a.rs[i].asPtr()
						a.rs[i] = a.rs[i].newExpr(lt, a.rs[i].desc)
						len := at.Len
						a.rs[i].eval = func(t *Thread) Slice { return Slice{rf(t).(ArrayValue), len, len} }
						rt = a.rs[i].t
Austin Clements's avatar
Austin Clements committed
407 408 409 410 411
					}
				}
			}
		}

412
		if !lt.compat(rt, false) {
413
			if len(a.rs) == 1 {
414
				a.rs[0].diag("illegal operand types for %s\n\t%v\n\t%v", a.errOp, lt, rt)
415
			} else {
416
				a.rs[i].diag("illegal operand types in %s %d of %s\n\t%v\n\t%v", a.errPosName, i+1, a.errOp, lt, rt)
417
			}
418
			bad = true
419 420
		}
	}
421
	if bad {
422
		return nil
423
	}
424 425

	// Compile
Austin Clements's avatar
Austin Clements committed
426
	if !isMT {
427
		// Case 1
428
		return genAssign(lt, a.rs[0])
429
	}
Austin Clements's avatar
Austin Clements committed
430
	// Case 2 or 3
431
	as := make([]func(lv Value, t *Thread), len(a.rs))
Austin Clements's avatar
Austin Clements committed
432
	for i, r := range a.rs {
433
		as[i] = genAssign(lmt.Elems[i], r)
Austin Clements's avatar
Austin Clements committed
434
	}
Russ Cox's avatar
Russ Cox committed
435
	return func(lv Value, t *Thread) {
Austin Clements's avatar
Austin Clements committed
436
		if effect != nil {
437
			effect(t)
Austin Clements's avatar
Austin Clements committed
438
		}
439
		lmv := lv.(multiV)
Austin Clements's avatar
Austin Clements committed
440
		for i, a := range as {
441
			a(lmv[i], t)
Austin Clements's avatar
Austin Clements committed
442
		}
443
	}
444 445 446 447 448
}

// compileAssign compiles an assignment operation without the full
// generality of an assignCompiler.  See assignCompiler for a
// description of the arguments.
Russ Cox's avatar
Russ Cox committed
449
func (a *compiler) compileAssign(pos token.Position, b *block, lt Type, rs []*expr, errOp, errPosName string) (func(Value, *Thread)) {
450
	ac, ok := a.checkAssign(pos, rs, errOp, errPosName)
451
	if !ok {
452
		return nil
453
	}
454
	return ac.compile(b, lt)
455 456 457
}

/*
458
 * Expression compiler
459
 */
460

461 462 463 464
// An exprCompiler stores information used throughout the compilation
// of a single expression.  It does not embed funcCompiler because
// expressions can appear at top level.
type exprCompiler struct {
465
	*compiler
466
	// The block this expression is being compiled in.
467
	block *block
468
	// Whether this expression is used in a constant context.
469
	constant bool
470 471
}

472 473 474 475 476
// compile compiles an expression AST.  callCtx should be true if this
// AST is in the function position of a function call node; it allows
// the returned expression to be a type or a built-in function (which
// otherwise result in errors).
func (a *exprCompiler) compile(x ast.Expr, callCtx bool) *expr {
477
	ei := &exprInfo{a.compiler, x.Pos()}
478 479 480

	switch x := x.(type) {
	// Literals
481 482 483
	case *ast.BasicLit:
		switch x.Kind {
		case token.INT:
484
			return ei.compileIntLit(string(x.Value))
485
		case token.FLOAT:
486
			return ei.compileFloatLit(string(x.Value))
487
		case token.CHAR:
488
			return ei.compileCharLit(string(x.Value))
489
		case token.STRING:
490
			return ei.compileStringLit(string(x.Value))
491
		default:
492
			log.Crashf("unexpected basic literal type %v", x.Kind)
493
		}
494 495

	case *ast.CompositeLit:
496
		goto notimpl
497 498

	case *ast.FuncLit:
499
		decl := ei.compileFuncType(a.block, x.Type)
500 501 502
		if decl == nil {
			// TODO(austin) Try compiling the body,
			// perhaps with dummy argument definitions
503
			return nil
504
		}
505
		fn := ei.compileFunc(a.block, decl, x.Body)
506
		if fn == nil {
507
			return nil
508 509
		}
		if a.constant {
510 511
			a.diagAt(x, "function literal used in constant expression")
			return nil
512
		}
513
		return ei.compileFuncLit(decl, fn)
514 515 516

	// Types
	case *ast.ArrayType:
517
		// TODO(austin) Use a multi-type case
518
		goto typeexpr
519 520

	case *ast.ChanType:
521
		goto typeexpr
522 523

	case *ast.Ellipsis:
524
		goto typeexpr
525 526

	case *ast.FuncType:
527
		goto typeexpr
528 529

	case *ast.InterfaceType:
530
		goto typeexpr
531 532

	case *ast.MapType:
533
		goto typeexpr
534 535 536 537

	// Remaining expressions
	case *ast.BadExpr:
		// Error already reported by parser
538 539
		a.silentErrors++
		return nil
540 541

	case *ast.BinaryExpr:
542
		l, r := a.compile(x.X, false), a.compile(x.Y, false)
543
		if l == nil || r == nil {
544
			return nil
545
		}
546
		return ei.compileBinaryExpr(x.Op, l, r)
547 548

	case *ast.CallExpr:
549 550 551
		l := a.compile(x.Fun, true)
		args := make([]*expr, len(x.Args))
		bad := false
552
		for i, arg := range x.Args {
Russ Cox's avatar
Russ Cox committed
553
			if i == 0 && l != nil && (l.t == Type(makeType) || l.t == Type(newType)) {
554 555
				argei := &exprInfo{a.compiler, arg.Pos()}
				args[i] = argei.exprFromType(a.compileType(a.block, arg))
556
			} else {
557
				args[i] = a.compile(arg, false)
558
			}
559
			if args[i] == nil {
560
				bad = true
561 562
			}
		}
Russ Cox's avatar
Russ Cox committed
563
		if bad || l == nil {
564
			return nil
565 566
		}
		if a.constant {
567 568
			a.diagAt(x, "function call in constant context")
			return nil
569
		}
570 571

		if l.valType != nil {
572 573
			a.diagAt(x, "type conversions not implemented")
			return nil
574
		} else if ft, ok := l.t.(*FuncType); ok && ft.builtin != "" {
575
			return ei.compileBuiltinCallExpr(a.block, ft, args)
576
		} else {
577
			return ei.compileCallExpr(a.block, l, args)
578
		}
579 580

	case *ast.Ident:
581
		return ei.compileIdent(a.block, a.constant, callCtx, x.Value)
582 583

	case *ast.IndexExpr:
584
		l, r := a.compile(x.X, false), a.compile(x.Index, false)
585
		if l == nil || r == nil {
586
			return nil
587
		}
588
		return ei.compileIndexExpr(l, r)
589

590
	case *ast.SliceExpr:
591
		end := x.End
592 593 594 595
		if end == nil {
			// TODO: set end to len(x.X)
			panic("unimplemented")
		}
596 597 598
		arr := a.compile(x.X, false)
		lo := a.compile(x.Index, false)
		hi := a.compile(end, false)
599 600 601
		if arr == nil || lo == nil || hi == nil {
			return nil
		}
602
		return ei.compileSliceExpr(arr, lo, hi)
603

604
	case *ast.KeyValueExpr:
605
		goto notimpl
606 607

	case *ast.ParenExpr:
608
		return a.compile(x.X, callCtx)
609 610

	case *ast.SelectorExpr:
611
		v := a.compile(x.X, false)
612
		if v == nil {
613
			return nil
614
		}
615
		return ei.compileSelectorExpr(v, x.Sel.Value)
616 617

	case *ast.StarExpr:
618 619
		// We pass down our call context because this could be
		// a pointer type (and thus a type conversion)
620
		v := a.compile(x.X, callCtx)
621
		if v == nil {
622
			return nil
623
		}
624 625
		if v.valType != nil {
			// Turns out this was a pointer type, not a dereference
626
			return ei.exprFromType(NewPtrType(v.valType))
627
		}
628
		return ei.compileStarExpr(v)
629 630

	case *ast.StringList:
631 632
		strings := make([]*expr, len(x.Strings))
		bad := false
633
		for i, s := range x.Strings {
634
			strings[i] = a.compile(s, false)
635
			if strings[i] == nil {
636
				bad = true
637 638 639
			}
		}
		if bad {
640
			return nil
641
		}
642
		return ei.compileStringList(strings)
643 644

	case *ast.StructType:
645
		goto notimpl
646 647

	case *ast.TypeAssertExpr:
648
		goto notimpl
649 650

	case *ast.UnaryExpr:
651
		v := a.compile(x.X, false)
652
		if v == nil {
653
			return nil
654
		}
655
		return ei.compileUnaryExpr(x.Op, v)
656
	}
657 658
	log.Crashf("unexpected ast node type %T", x)
	panic()
659

660 661
typeexpr:
	if !callCtx {
662 663
		a.diagAt(x, "type used as expression")
		return nil
664
	}
665
	return ei.exprFromType(a.compileType(a.block, x))
666

667
notimpl:
668 669
	a.diagAt(x, "%T expression node not implemented", x)
	return nil
670 671
}

672 673
func (a *exprInfo) exprFromType(t Type) *expr {
	if t == nil {
674
		return nil
675
	}
676 677 678
	expr := a.newExpr(nil, "type")
	expr.valType = t
	return expr
679 680 681
}

func (a *exprInfo) compileIdent(b *block, constant bool, callCtx bool, name string) *expr {
682
	bl, level, def := b.Lookup(name)
683
	if def == nil {
684 685
		a.diag("%s: undefined", name)
		return nil
686 687 688
	}
	switch def := def.(type) {
	case *Constant:
689
		expr := a.newExpr(def.Type, "constant")
690 691 692 693
		if ft, ok := def.Type.(*FuncType); ok && ft.builtin != "" {
			// XXX(Spec) I don't think anything says that
			// built-in functions can't be used as values.
			if !callCtx {
694 695
				a.diag("built-in function %s cannot be used as a value", ft.builtin)
				return nil
696 697 698 699
			}
			// Otherwise, we leave the evaluators empty
			// because this is handled specially
		} else {
700
			expr.genConstant(def.Value)
701
		}
702
		return expr
703
	case *Variable:
704
		if constant {
705 706
			a.diag("variable %s used in constant expression", name)
			return nil
707
		}
Russ Cox's avatar
Russ Cox committed
708
		if bl.global {
709
			return a.compileGlobalVariable(def)
Russ Cox's avatar
Russ Cox committed
710
		}
711
		return a.compileVariable(level, def)
712
	case Type:
713
		if callCtx {
714
			return a.exprFromType(def)
715
		}
716 717
		a.diag("type %v used as expression", name)
		return nil
718
	}
719 720
	log.Crashf("name %s has unknown type %T", name, def)
	panic()
721 722 723 724 725
}

func (a *exprInfo) compileVariable(level int, v *Variable) *expr {
	if v.Type == nil {
		// Placeholder definition from an earlier error
726 727
		a.silentErrors++
		return nil
728
	}
729 730 731
	expr := a.newExpr(v.Type, "variable")
	expr.genIdentOp(level, v.Index)
	return expr
732 733
}

Russ Cox's avatar
Russ Cox committed
734 735 736
func (a *exprInfo) compileGlobalVariable(v *Variable) *expr {
	if v.Type == nil {
		// Placeholder definition from an earlier error
737 738
		a.silentErrors++
		return nil
Russ Cox's avatar
Russ Cox committed
739 740
	}
	if v.Init == nil {
741
		v.Init = v.Type.Zero()
Russ Cox's avatar
Russ Cox committed
742
	}
743 744 745 746
	expr := a.newExpr(v.Type, "variable")
	val := v.Init
	expr.genValue(func(t *Thread) Value { return val })
	return expr
Russ Cox's avatar
Russ Cox committed
747 748
}

749
func (a *exprInfo) compileIdealInt(i *bignum.Integer, desc string) *expr {
750 751 752
	expr := a.newExpr(IdealIntType, desc)
	expr.eval = func() *bignum.Integer { return i }
	return expr
753 754
}

755
func (a *exprInfo) compileIntLit(lit string) *expr {
756 757
	i, _, _ := bignum.IntFromString(lit, 0)
	return a.compileIdealInt(i, "integer literal")
758 759
}

760 761
func (a *exprInfo) compileCharLit(lit string) *expr {
	if lit[0] != '\'' {
762
		// Caught by parser
763 764
		a.silentErrors++
		return nil
765
	}
766
	v, _, tail, err := strconv.UnquoteChar(lit[1:], '\'')
767
	if err != nil || tail != "'" {
768
		// Caught by parser
769 770
		a.silentErrors++
		return nil
771
	}
772
	return a.compileIdealInt(bignum.Int(int64(v)), "character literal")
773 774
}

775
func (a *exprInfo) compileFloatLit(lit string) *expr {
776
	f, _, n := bignum.RatFromString(lit, 0)
777
	if n != len(lit) {
778
		log.Crashf("malformed float literal %s at %v passed parser", lit, a.pos)
779
	}
780 781 782
	expr := a.newExpr(IdealFloatType, "float literal")
	expr.eval = func() *bignum.Rational { return f }
	return expr
783 784
}

785
func (a *exprInfo) compileString(s string) *expr {
786 787 788 789
	// Ideal strings don't have a named type but they are
	// compatible with type string.

	// TODO(austin) Use unnamed string type.
790 791 792
	expr := a.newExpr(StringType, "string literal")
	expr.eval = func(*Thread) string { return s }
	return expr
793 794
}

795
func (a *exprInfo) compileStringLit(lit string) *expr {
796
	s, err := strconv.Unquote(lit)
797
	if err != nil {
798 799
		a.diag("illegal string literal, %v", err)
		return nil
800
	}
801
	return a.compileString(s)
802 803
}

804
func (a *exprInfo) compileStringList(list []*expr) *expr {
805
	ss := make([]string, len(list))
806
	for i, s := range list {
807
		ss[i] = s.asString()(nil)
808
	}
809
	return a.compileString(strings.Join(ss, ""))
810 811
}

Russ Cox's avatar
Russ Cox committed
812
func (a *exprInfo) compileFuncLit(decl *FuncDecl, fn func(*Thread) Func) *expr {
813 814 815
	expr := a.newExpr(decl.Type, "function literal")
	expr.eval = fn
	return expr
816 817
}

818
func (a *exprInfo) compileSelectorExpr(v *expr, name string) *expr {
819 820 821
	// mark marks a field that matches the selector name.  It
	// tracks the best depth found so far and whether more than
	// one field has been found at that depth.
822 823 824
	bestDepth := -1
	ambig := false
	amberr := ""
825 826 827
	mark := func(depth int, pathName string) {
		switch {
		case bestDepth == -1 || depth < bestDepth:
828 829 830
			bestDepth = depth
			ambig = false
			amberr = ""
831 832

		case depth == bestDepth:
833
			ambig = true
834 835

		default:
836
			log.Crashf("Marked field at depth %d, but already found one at depth %d", depth, bestDepth)
837
		}
838 839
		amberr += "\n\t" + pathName[1:]
	}
840

841
	visited := make(map[Type]bool)
842 843 844

	// find recursively searches for the named field, starting at
	// type t.  If it finds the named field, it returns a function
845 846 847 848 849 850 851 852
	// which takes an expr that represents a value of type 't' and
	// returns an expr that retrieves the named field.  We delay
	// expr construction to avoid producing lots of useless expr's
	// as we search.
	//
	// TODO(austin) Now that the expression compiler works on
	// semantic values instead of AST's, there should be a much
	// better way of doing this.
853
	var find func(Type, int, string) (func(*expr) *expr)
Robert Griesemer's avatar
Robert Griesemer committed
854
	find = func(t Type, depth int, pathName string) (func(*expr) *expr) {
855 856
		// Don't bother looking if we've found something shallower
		if bestDepth != -1 && bestDepth < depth {
857
			return nil
858 859 860 861
		}

		// Don't check the same type twice and avoid loops
		if _, ok := visited[t]; ok {
862
			return nil
863
		}
864
		visited[t] = true
865 866

		// Implicit dereference
867
		deref := false
868
		if ti, ok := t.(*PtrType); ok {
869 870
			deref = true
			t = ti.Elem
871 872 873 874
		}

		// If it's a named type, look for methods
		if ti, ok := t.(*NamedType); ok {
875
			_, ok := ti.methods[name]
876
			if ok {
877 878
				mark(depth, pathName+"."+name)
				log.Crash("Methods not implemented")
879
			}
880
			t = ti.Def
881 882 883
		}

		// If it's a struct type, check fields and embedded types
884
		var builder func(*expr) *expr
885
		if t, ok := t.(*StructType); ok {
Austin Clements's avatar
Austin Clements committed
886
			for i, f := range t.Elems {
887
				var sub func(*expr) *expr
888 889
				switch {
				case f.Name == name:
890 891
					mark(depth, pathName+"."+name)
					sub = func(e *expr) *expr { return e }
892 893

				case f.Anonymous:
894
					sub = find(f.Type, depth+1, pathName+"."+f.Name)
895
					if sub == nil {
896
						continue
897 898 899
					}

				default:
900
					continue
901 902 903 904
				}

				// We found something.  Create a
				// builder for accessing this field.
905 906
				ft := f.Type
				index := i
907
				builder = func(parent *expr) *expr {
908
					if deref {
909
						parent = a.compileStarExpr(parent)
910
					}
911 912 913 914 915 916
					expr := a.newExpr(ft, "selector expression")
					pf := parent.asStruct()
					evalAddr := func(t *Thread) Value { return pf(t).Field(t, index) }
					expr.genValue(evalAddr)
					return sub(expr)
				}
917 918 919
			}
		}

920 921
		return builder
	}
922

923
	builder := find(v.t, 0, "")
924
	if builder == nil {
925 926
		a.diag("type %v has no field or method %s", v.t, name)
		return nil
927 928
	}
	if ambig {
929 930
		a.diag("field %s is ambiguous in type %v%s", name, v.t, amberr)
		return nil
931 932
	}

933
	return builder(v)
934 935
}

Russ Cox's avatar
Russ Cox committed
936 937
func (a *exprInfo) compileSliceExpr(arr, lo, hi *expr) *expr {
	// Type check object
938
	arr = arr.derefArray()
Russ Cox's avatar
Russ Cox committed
939

940 941
	var at Type
	var maxIndex int64 = -1
Russ Cox's avatar
Russ Cox committed
942 943 944

	switch lt := arr.t.lit().(type) {
	case *ArrayType:
945 946
		at = NewSliceType(lt.Elem)
		maxIndex = lt.Len
Russ Cox's avatar
Russ Cox committed
947 948

	case *SliceType:
949
		at = lt
Russ Cox's avatar
Russ Cox committed
950 951

	case *stringType:
952
		at = lt
Russ Cox's avatar
Russ Cox committed
953 954

	default:
955 956
		a.diag("cannot slice %v", arr.t)
		return nil
Russ Cox's avatar
Russ Cox committed
957 958 959 960 961 962
	}

	// Type check index and convert to int
	// XXX(Spec) It's unclear if ideal floats with no
	// fractional part are allowed here.  6g allows it.  I
	// believe that's wrong.
963 964
	lo = lo.convertToInt(maxIndex, "slice", "slice")
	hi = hi.convertToInt(maxIndex, "slice", "slice")
Russ Cox's avatar
Russ Cox committed
965
	if lo == nil || hi == nil {
966
		return nil
Russ Cox's avatar
Russ Cox committed
967 968
	}

969
	expr := a.newExpr(at, "slice expression")
Russ Cox's avatar
Russ Cox committed
970 971

	// Compile
972 973
	lof := lo.asInt()
	hif := hi.asInt()
Russ Cox's avatar
Russ Cox committed
974 975
	switch lt := arr.t.lit().(type) {
	case *ArrayType:
976 977
		arrf := arr.asArray()
		bound := lt.Len
Russ Cox's avatar
Russ Cox committed
978
		expr.eval = func(t *Thread) Slice {
979
			arr, lo, hi := arrf(t), lof(t), hif(t)
Russ Cox's avatar
Russ Cox committed
980
			if lo > hi || hi > bound || lo < 0 {
981
				t.Abort(SliceError{lo, hi, bound})
Russ Cox's avatar
Russ Cox committed
982
			}
983 984
			return Slice{arr.Sub(lo, bound-lo), hi - lo, bound - lo}
		}
Russ Cox's avatar
Russ Cox committed
985 986

	case *SliceType:
987
		arrf := arr.asSlice()
Russ Cox's avatar
Russ Cox committed
988
		expr.eval = func(t *Thread) Slice {
989
			arr, lo, hi := arrf(t), lof(t), hif(t)
Russ Cox's avatar
Russ Cox committed
990
			if lo > hi || hi > arr.Cap || lo < 0 {
991
				t.Abort(SliceError{lo, hi, arr.Cap})
Russ Cox's avatar
Russ Cox committed
992
			}
993 994
			return Slice{arr.Base.Sub(lo, arr.Cap-lo), hi - lo, arr.Cap - lo}
		}
Russ Cox's avatar
Russ Cox committed
995 996

	case *stringType:
997
		arrf := arr.asString()
Russ Cox's avatar
Russ Cox committed
998 999 1000 1001
		// TODO(austin) This pulls over the whole string in a
		// remote setting, instead of creating a substring backed
		// by remote memory.
		expr.eval = func(t *Thread) string {
1002
			arr, lo, hi := arrf(t), lof(t), hif(t)
Russ Cox's avatar
Russ Cox committed
1003
			if lo > hi || hi > int64(len(arr)) || lo < 0 {
1004
				t.Abort(SliceError{lo, hi, int64(len(arr))})
Russ Cox's avatar
Russ Cox committed
1005
			}
1006 1007
			return arr[lo:hi]
		}
Russ Cox's avatar
Russ Cox committed
1008 1009

	default:
1010
		log.Crashf("unexpected left operand type %T", arr.t.lit())
Russ Cox's avatar
Russ Cox committed
1011 1012
	}

1013
	return expr
Russ Cox's avatar
Russ Cox committed
1014 1015
}

1016
func (a *exprInfo) compileIndexExpr(l, r *expr) *expr {
1017
	// Type check object
1018
	l = l.derefArray()
1019

1020 1021 1022
	var at Type
	intIndex := false
	var maxIndex int64 = -1
1023

1024
	switch lt := l.t.lit().(type) {
1025
	case *ArrayType:
1026 1027 1028
		at = lt.Elem
		intIndex = true
		maxIndex = lt.Len
1029

Austin Clements's avatar
Austin Clements committed
1030
	case *SliceType:
1031 1032
		at = lt.Elem
		intIndex = true
1033 1034

	case *stringType:
1035 1036
		at = Uint8Type
		intIndex = true
1037

Austin Clements's avatar
Austin Clements committed
1038
	case *MapType:
1039
		at = lt.Elem
Austin Clements's avatar
Austin Clements committed
1040
		if r.t.isIdeal() {
1041
			r = r.convertTo(lt.Key)
Austin Clements's avatar
Austin Clements committed
1042
			if r == nil {
1043
				return nil
Austin Clements's avatar
Austin Clements committed
1044 1045 1046
			}
		}
		if !lt.Key.compat(r.t, false) {
1047 1048
			a.diag("cannot use %s as index into %s", r.t, lt)
			return nil
Austin Clements's avatar
Austin Clements committed
1049
		}
1050 1051

	default:
1052 1053
		a.diag("cannot index into %v", l.t)
		return nil
1054 1055 1056 1057 1058 1059 1060
	}

	// Type check index and convert to int if necessary
	if intIndex {
		// XXX(Spec) It's unclear if ideal floats with no
		// fractional part are allowed here.  6g allows it.  I
		// believe that's wrong.
1061
		r = r.convertToInt(maxIndex, "index", "index")
1062
		if r == nil {
1063
			return nil
1064 1065 1066
		}
	}

1067
	expr := a.newExpr(at, "index expression")
1068 1069

	// Compile
1070
	switch lt := l.t.lit().(type) {
1071
	case *ArrayType:
1072 1073 1074
		lf := l.asArray()
		rf := r.asInt()
		bound := lt.Len
Russ Cox's avatar
Russ Cox committed
1075
		expr.genValue(func(t *Thread) Value {
1076
			l, r := lf(t), rf(t)
1077
			if r < 0 || r >= bound {
1078
				t.Abort(IndexError{r, bound})
1079
			}
1080 1081
			return l.Elem(t, r)
		})
1082

Austin Clements's avatar
Austin Clements committed
1083
	case *SliceType:
1084 1085
		lf := l.asSlice()
		rf := r.asInt()
Russ Cox's avatar
Russ Cox committed
1086
		expr.genValue(func(t *Thread) Value {
1087
			l, r := lf(t), rf(t)
1088
			if l.Base == nil {
1089
				t.Abort(NilPointerError{})
1090 1091
			}
			if r < 0 || r >= l.Len {
1092
				t.Abort(IndexError{r, l.Len})
1093
			}
1094 1095
			return l.Base.Elem(t, r)
		})
Austin Clements's avatar
Austin Clements committed
1096

1097
	case *stringType:
1098 1099
		lf := l.asString()
		rf := r.asInt()
1100 1101
		// TODO(austin) This pulls over the whole string in a
		// remote setting, instead of just the one character.
Russ Cox's avatar
Russ Cox committed
1102
		expr.eval = func(t *Thread) uint64 {
1103
			l, r := lf(t), rf(t)
1104
			if r < 0 || r >= int64(len(l)) {
1105
				t.Abort(IndexError{r, int64(len(l))})
1106
			}
1107 1108
			return uint64(l[r])
		}
1109

Austin Clements's avatar
Austin Clements committed
1110
	case *MapType:
1111 1112
		lf := l.asMap()
		rf := r.asInterface()
Russ Cox's avatar
Russ Cox committed
1113
		expr.genValue(func(t *Thread) Value {
1114 1115
			m := lf(t)
			k := rf(t)
1116
			if m == nil {
1117
				t.Abort(NilPointerError{})
1118
			}
1119
			e := m.Elem(t, k)
Austin Clements's avatar
Austin Clements committed
1120
			if e == nil {
1121
				t.Abort(KeyError{k})
Austin Clements's avatar
Austin Clements committed
1122
			}
1123 1124
			return e
		})
Austin Clements's avatar
Austin Clements committed
1125 1126
		// genValue makes things addressable, but map values
		// aren't addressable.
1127
		expr.evalAddr = nil
Russ Cox's avatar
Russ Cox committed
1128
		expr.evalMapValue = func(t *Thread) (Map, interface{}) {
1129
			// TODO(austin) Key check?  nil check?
1130
			return lf(t), rf(t)
1131
		}
Austin Clements's avatar
Austin Clements committed
1132

1133
	default:
1134
		log.Crashf("unexpected left operand type %T", l.t.lit())
1135
	}
1136

1137
	return expr
1138 1139
}

1140
func (a *exprInfo) compileCallExpr(b *block, l *expr, as []*expr) *expr {
1141 1142 1143 1144 1145 1146 1147 1148 1149 1150
	// TODO(austin) Variadic functions.

	// Type check

	// XXX(Spec) Calling a named function type is okay.  I really
	// think there needs to be a general discussion of named
	// types.  A named type creates a new, distinct type, but the
	// type of that type is still whatever it's defined to.  Thus,
	// in "type Foo int", Foo is still an integer type and in
	// "type Foo func()", Foo is a function type.
1151
	lt, ok := l.t.lit().(*FuncType)
1152
	if !ok {
1153 1154
		a.diag("cannot call non-function type %v", l.t)
		return nil
1155 1156 1157 1158
	}

	// The arguments must be single-valued expressions assignment
	// compatible with the parameters of F.
1159 1160 1161
	//
	// XXX(Spec) The spec is wrong.  It can also be a single
	// multi-valued expression.
1162 1163
	nin := len(lt.In)
	assign := a.compileAssign(a.pos, b, NewMultiType(lt.In), as, "function call", "argument")
1164
	if assign == nil {
1165
		return nil
1166 1167
	}

1168 1169
	var t Type
	nout := len(lt.Out)
1170 1171
	switch nout {
	case 0:
1172
		t = EmptyType
1173
	case 1:
1174
		t = lt.Out[0]
1175
	default:
1176
		t = NewMultiType(lt.Out)
1177
	}
1178
	expr := a.newExpr(t, "function call")
1179

1180
	// Gather argument and out types to initialize frame variables
1181
	vts := make([]Type, nin+nout)
1182
	for i, t := range lt.In {
1183
		vts[i] = t
1184 1185
	}
	for i, t := range lt.Out {
1186
		vts[i+nin] = t
1187 1188
	}

1189
	// Compile
1190
	lf := l.asFunc()
Russ Cox's avatar
Russ Cox committed
1191
	call := func(t *Thread) []Value {
1192 1193
		fun := lf(t)
		fr := fun.NewFrame()
1194
		for i, t := range vts {
1195
			fr.Vars[i] = t.Zero()
1196
		}
1197 1198 1199 1200 1201 1202 1203 1204
		assign(multiV(fr.Vars[0:nin]), t)
		oldf := t.f
		t.f = fr
		fun.Call(t)
		t.f = oldf
		return fr.Vars[nin : nin+nout]
	}
	expr.genFuncCall(call)
1205

1206
	return expr
1207
}
1208

1209 1210 1211
func (a *exprInfo) compileBuiltinCallExpr(b *block, ft *FuncType, as []*expr) *expr {
	checkCount := func(min, max int) bool {
		if len(as) < min {
1212 1213
			a.diag("not enough arguments to %s", ft.builtin)
			return false
1214
		} else if len(as) > max {
1215 1216
			a.diag("too many arguments to %s", ft.builtin)
			return false
1217
		}
1218 1219
		return true
	}
1220 1221 1222 1223

	switch ft {
	case capType:
		if !checkCount(1, 1) {
1224
			return nil
1225
		}
1226 1227
		arg := as[0].derefArray()
		expr := a.newExpr(IntType, "function call")
1228 1229 1230 1231
		switch t := arg.t.lit().(type) {
		case *ArrayType:
			// TODO(austin) It would be nice if this could
			// be a constant int.
1232 1233
			v := t.Len
			expr.eval = func(t *Thread) int64 { return v }
1234 1235

		case *SliceType:
1236 1237
			vf := arg.asSlice()
			expr.eval = func(t *Thread) int64 { return vf(t).Cap }
1238 1239 1240 1241

		//case *ChanType:

		default:
1242 1243
			a.diag("illegal argument type for cap function\n\t%v", arg.t)
			return nil
1244
		}
1245
		return expr
1246 1247 1248

	case lenType:
		if !checkCount(1, 1) {
1249
			return nil
1250
		}
1251 1252
		arg := as[0].derefArray()
		expr := a.newExpr(IntType, "function call")
1253 1254
		switch t := arg.t.lit().(type) {
		case *stringType:
1255 1256
			vf := arg.asString()
			expr.eval = func(t *Thread) int64 { return int64(len(vf(t))) }
1257 1258 1259 1260

		case *ArrayType:
			// TODO(austin) It would be nice if this could
			// be a constant int.
1261 1262
			v := t.Len
			expr.eval = func(t *Thread) int64 { return v }
1263 1264

		case *SliceType:
1265 1266
			vf := arg.asSlice()
			expr.eval = func(t *Thread) int64 { return vf(t).Len }
1267 1268

		case *MapType:
1269
			vf := arg.asMap()
Russ Cox's avatar
Russ Cox committed
1270
			expr.eval = func(t *Thread) int64 {
1271 1272
				// XXX(Spec) What's the len of an
				// uninitialized map?
1273
				m := vf(t)
1274
				if m == nil {
1275
					return 0
1276
				}
1277 1278
				return m.Len(t)
			}
1279 1280 1281 1282

		//case *ChanType:

		default:
1283 1284
			a.diag("illegal argument type for len function\n\t%v", arg.t)
			return nil
1285
		}
1286
		return expr
1287 1288 1289

	case makeType:
		if !checkCount(1, 3) {
1290
			return nil
1291 1292 1293 1294
		}
		// XXX(Spec) What are the types of the
		// arguments?  Do they have to be ints?  6g
		// accepts any integral type.
1295 1296
		var lenexpr, capexpr *expr
		var lenf, capf func(*Thread) int64
1297
		if len(as) > 1 {
1298
			lenexpr = as[1].convertToInt(-1, "length", "make function")
1299
			if lenexpr == nil {
1300
				return nil
1301
			}
1302
			lenf = lenexpr.asInt()
1303 1304
		}
		if len(as) > 2 {
1305
			capexpr = as[2].convertToInt(-1, "capacity", "make function")
1306
			if capexpr == nil {
1307
				return nil
1308
			}
1309
			capf = capexpr.asInt()
1310 1311 1312 1313 1314 1315 1316 1317 1318 1319
		}

		switch t := as[0].valType.lit().(type) {
		case *SliceType:
			// A new, initialized slice value for a given
			// element type T is made using the built-in
			// function make, which takes a slice type and
			// parameters specifying the length and
			// optionally the capacity.
			if !checkCount(2, 3) {
1320
				return nil
1321
			}
1322 1323
			et := t.Elem
			expr := a.newExpr(t, "function call")
Russ Cox's avatar
Russ Cox committed
1324
			expr.eval = func(t *Thread) Slice {
1325
				l := lenf(t)
1326 1327 1328
				// XXX(Spec) What if len or cap is
				// negative?  The runtime panics.
				if l < 0 {
1329
					t.Abort(NegativeLengthError{l})
1330
				}
1331
				c := l
1332
				if capf != nil {
1333
					c = capf(t)
1334
					if c < 0 {
1335
						t.Abort(NegativeCapacityError{c})
1336 1337 1338 1339 1340
					}
					// XXX(Spec) What happens if
					// len > cap?  The runtime
					// sets cap to len.
					if l > c {
1341
						c = l
1342 1343
					}
				}
1344
				base := arrayV(make([]Value, c))
1345
				for i := int64(0); i < c; i++ {
1346
					base[i] = et.Zero()
1347
				}
1348 1349 1350
				return Slice{&base, l, c}
			}
			return expr
1351 1352 1353 1354 1355 1356 1357

		case *MapType:
			// A new, empty map value is made using the
			// built-in function make, which takes the map
			// type and an optional capacity hint as
			// arguments.
			if !checkCount(1, 2) {
1358
				return nil
1359
			}
1360
			expr := a.newExpr(t, "function call")
Russ Cox's avatar
Russ Cox committed
1361
			expr.eval = func(t *Thread) Map {
1362
				if lenf == nil {
1363
					return make(evalMap)
1364
				}
1365 1366 1367 1368
				l := lenf(t)
				return make(evalMap, l)
			}
			return expr
1369 1370 1371 1372

		//case *ChanType:

		default:
1373 1374
			a.diag("illegal argument type for make function\n\t%v", as[0].valType)
			return nil
1375 1376
		}

Russ Cox's avatar
Russ Cox committed
1377
	case closeType, closedType:
1378 1379
		a.diag("built-in function %s not implemented", ft.builtin)
		return nil
Russ Cox's avatar
Russ Cox committed
1380 1381 1382

	case newType:
		if !checkCount(1, 1) {
1383
			return nil
Russ Cox's avatar
Russ Cox committed
1384 1385
		}

1386 1387 1388 1389
		t := as[0].valType
		expr := a.newExpr(NewPtrType(t), "new")
		expr.eval = func(*Thread) Value { return t.Zero() }
		return expr
Russ Cox's avatar
Russ Cox committed
1390 1391

	case panicType, paniclnType, printType, printlnType:
1392
		evals := make([]func(*Thread) interface{}, len(as))
Russ Cox's avatar
Russ Cox committed
1393
		for i, x := range as {
1394
			evals[i] = x.asInterface()
Russ Cox's avatar
Russ Cox committed
1395
		}
1396 1397
		spaces := ft == paniclnType || ft == printlnType
		newline := ft != printType
Russ Cox's avatar
Russ Cox committed
1398 1399 1400
		printer := func(t *Thread) {
			for i, eval := range evals {
				if i > 0 && spaces {
1401
					print(" ")
Russ Cox's avatar
Russ Cox committed
1402
				}
1403
				v := eval(t)
Robert Griesemer's avatar
Robert Griesemer committed
1404
				type stringer interface {
1405
					String() string
Robert Griesemer's avatar
Robert Griesemer committed
1406
				}
Russ Cox's avatar
Russ Cox committed
1407 1408
				switch v1 := v.(type) {
				case bool:
1409
					print(v1)
Russ Cox's avatar
Russ Cox committed
1410
				case uint64:
1411
					print(v1)
Russ Cox's avatar
Russ Cox committed
1412
				case int64:
1413
					print(v1)
Russ Cox's avatar
Russ Cox committed
1414
				case float64:
1415
					print(v1)
Russ Cox's avatar
Russ Cox committed
1416
				case string:
1417
					print(v1)
Russ Cox's avatar
Russ Cox committed
1418
				case stringer:
1419
					print(v1.String())
Russ Cox's avatar
Russ Cox committed
1420
				default:
1421
					print("???")
Russ Cox's avatar
Russ Cox committed
1422 1423 1424
				}
			}
			if newline {
1425
				print("\n")
Russ Cox's avatar
Russ Cox committed
1426
			}
1427 1428 1429
		}
		expr := a.newExpr(EmptyType, "print")
		expr.exec = printer
Russ Cox's avatar
Russ Cox committed
1430 1431
		if ft == panicType || ft == paniclnType {
			expr.exec = func(t *Thread) {
1432 1433
				printer(t)
				t.Abort(os.NewError("panic"))
1434
			}
Russ Cox's avatar
Russ Cox committed
1435
		}
1436
		return expr
1437 1438
	}

1439 1440
	log.Crashf("unexpected built-in function '%s'", ft.builtin)
	panic()
1441 1442
}

1443
func (a *exprInfo) compileStarExpr(v *expr) *expr {
1444
	switch vt := v.t.lit().(type) {
1445
	case *PtrType:
1446 1447
		expr := a.newExpr(vt.Elem, "indirect expression")
		vf := v.asPtr()
Russ Cox's avatar
Russ Cox committed
1448
		expr.genValue(func(t *Thread) Value {
1449
			v := vf(t)
1450
			if v == nil {
1451
				t.Abort(NilPointerError{})
1452
			}
1453 1454 1455
			return v
		})
		return expr
1456 1457
	}

1458 1459
	a.diagOpType(token.MUL, v.t)
	return nil
1460 1461
}

Robert Griesemer's avatar
Robert Griesemer committed
1462
var unaryOpDescs = make(map[token.Token]string)
1463

1464
func (a *exprInfo) compileUnaryExpr(op token.Token, v *expr) *expr {
1465
	// Type check
1466
	var t Type
1467
	switch op {
1468 1469
	case token.ADD, token.SUB:
		if !v.t.isInteger() && !v.t.isFloat() {
1470 1471
			a.diagOpType(op, v.t)
			return nil
1472
		}
1473
		t = v.t
1474

1475 1476
	case token.NOT:
		if !v.t.isBoolean() {
1477 1478
			a.diagOpType(op, v.t)
			return nil
1479
		}
1480
		t = BoolType
1481

1482 1483
	case token.XOR:
		if !v.t.isInteger() {
1484 1485
			a.diagOpType(op, v.t)
			return nil
1486
		}
1487
		t = v.t
1488

1489
	case token.AND:
1490 1491 1492 1493
		// The unary prefix address-of operator & generates
		// the address of its operand, which must be a
		// variable, pointer indirection, field selector, or
		// array or slice indexing operation.
1494
		if v.evalAddr == nil {
1495 1496
			a.diag("cannot take the address of %s", v.desc)
			return nil
1497 1498 1499 1500 1501 1502
		}

		// TODO(austin) Implement "It is illegal to take the
		// address of a function result variable" once I have
		// function result variables.

1503
		t = NewPtrType(v.t)
1504 1505

	case token.ARROW:
1506
		log.Crashf("Unary op %v not implemented", op)
1507

1508
	default:
1509
		log.Crashf("unknown unary operator %v", op)
1510 1511
	}

1512
	desc, ok := unaryOpDescs[op]
Robert Griesemer's avatar
Robert Griesemer committed
1513
	if !ok {
1514 1515
		desc = "unary " + op.String() + " expression"
		unaryOpDescs[op] = desc
1516 1517 1518
	}

	// Compile
1519
	expr := a.newExpr(t, desc)
1520
	switch op {
1521 1522
	case token.ADD:
		// Just compile it out
1523 1524
		expr = v
		expr.desc = desc
1525 1526

	case token.SUB:
1527
		expr.genUnaryOpNeg(v)
1528 1529

	case token.NOT:
1530
		expr.genUnaryOpNot(v)
1531 1532

	case token.XOR:
1533
		expr.genUnaryOpXor(v)
1534 1535

	case token.AND:
1536 1537
		vf := v.evalAddr
		expr.eval = func(t *Thread) Value { return vf(t) }
1538 1539

	default:
1540
		log.Crashf("Compilation of unary op %v not implemented", op)
1541
	}
1542

1543
	return expr
1544 1545
}

Robert Griesemer's avatar
Robert Griesemer committed
1546
var binOpDescs = make(map[token.Token]string)
1547

1548
func (a *exprInfo) compileBinaryExpr(op token.Token, l, r *expr) *expr {
1549
	// Save the original types of l.t and r.t for error messages.
1550 1551
	origlt := l.t
	origrt := r.t
1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565

	// XXX(Spec) What is the exact definition of a "named type"?

	// XXX(Spec) Arithmetic operators: "Integer types" apparently
	// means all types compatible with basic integer types, though
	// this is never explained.  Likewise for float types, etc.
	// This relates to the missing explanation of named types.

	// XXX(Spec) Operators: "If both operands are ideal numbers,
	// the conversion is to ideal floats if one of the operands is
	// an ideal float (relevant for / and %)."  How is that
	// relevant only for / and %?  If I add an ideal int and an
	// ideal float, I get an ideal float.

1566
	if op != token.SHL && op != token.SHR {
1567 1568 1569 1570
		// Except in shift expressions, if one operand has
		// numeric type and the other operand is an ideal
		// number, the ideal number is converted to match the
		// type of the other operand.
1571
		if (l.t.isInteger() || l.t.isFloat()) && !l.t.isIdeal() && r.t.isIdeal() {
1572
			r = r.convertTo(l.t)
1573
		} else if (r.t.isInteger() || r.t.isFloat()) && !r.t.isIdeal() && l.t.isIdeal() {
1574
			l = l.convertTo(r.t)
1575 1576
		}
		if l == nil || r == nil {
1577
			return nil
1578 1579 1580 1581 1582 1583 1584
		}

		// Except in shift expressions, if both operands are
		// ideal numbers and one is an ideal float, the other
		// is converted to ideal float.
		if l.t.isIdeal() && r.t.isIdeal() {
			if l.t.isInteger() && r.t.isFloat() {
1585
				l = l.convertTo(r.t)
1586
			} else if l.t.isFloat() && r.t.isInteger() {
1587
				r = r.convertTo(l.t)
1588 1589
			}
			if l == nil || r == nil {
1590
				return nil
1591 1592 1593 1594 1595
			}
		}
	}

	// Useful type predicates
Austin Clements's avatar
Austin Clements committed
1596
	// TODO(austin) CL 33668 mandates identical types except for comparisons.
1597 1598 1599
	compat := func() bool { return l.t.compat(r.t, false) }
	integers := func() bool { return l.t.isInteger() && r.t.isInteger() }
	floats := func() bool { return l.t.isFloat() && r.t.isFloat() }
1600 1601
	strings := func() bool {
		// TODO(austin) Deal with named types
1602
		return l.t == StringType && r.t == StringType
1603 1604
	}
	booleans := func() bool { return l.t.isBoolean() && r.t.isBoolean() }
1605 1606

	// Type check
1607
	var t Type
1608
	switch op {
1609
	case token.ADD:
1610
		if !compat() || (!integers() && !floats() && !strings()) {
1611 1612
			a.diagOpTypes(op, origlt, origrt)
			return nil
1613
		}
1614
		t = l.t
1615 1616

	case token.SUB, token.MUL, token.QUO:
1617
		if !compat() || (!integers() && !floats()) {
1618 1619
			a.diagOpTypes(op, origlt, origrt)
			return nil
1620
		}
1621
		t = l.t
1622 1623

	case token.REM, token.AND, token.OR, token.XOR, token.AND_NOT:
1624
		if !compat() || !integers() {
1625 1626
			a.diagOpTypes(op, origlt, origrt)
			return nil
1627
		}
1628
		t = l.t
1629 1630

	case token.SHL, token.SHR:
1631 1632 1633 1634 1635
		// XXX(Spec) Is it okay for the right operand to be an
		// ideal float with no fractional part?  "The right
		// operand in a shift operation must be always be of
		// unsigned integer type or an ideal number that can
		// be safely converted into an unsigned integer type
1636
		// (§Arithmetic operators)" suggests so and 6g agrees.
1637 1638

		if !l.t.isInteger() || !(r.t.isInteger() || r.t.isIdeal()) {
1639 1640
			a.diagOpTypes(op, origlt, origrt)
			return nil
1641 1642
		}

1643 1644 1645 1646 1647
		// The right operand in a shift operation must be
		// always be of unsigned integer type or an ideal
		// number that can be safely converted into an
		// unsigned integer type.
		if r.t.isIdeal() {
1648
			r2 := r.convertTo(UintType)
1649
			if r2 == nil {
1650
				return nil
1651
			}
1652 1653 1654

			// If the left operand is not ideal, convert
			// the right to not ideal.
1655
			if !l.t.isIdeal() {
1656
				r = r2
1657 1658 1659 1660 1661
			}

			// If both are ideal, but the right side isn't
			// an ideal int, convert it to simplify things.
			if l.t.isIdeal() && !r.t.isInteger() {
1662
				r = r.convertTo(IdealIntType)
1663
				if r == nil {
1664
					log.Crashf("conversion to uintType succeeded, but conversion to idealIntType failed")
1665 1666
				}
			}
1667
		} else if _, ok := r.t.lit().(*uintType); !ok {
1668 1669
			a.diag("right operand of shift must be unsigned")
			return nil
1670
		}
1671 1672 1673 1674 1675 1676

		if l.t.isIdeal() && !r.t.isIdeal() {
			// XXX(Spec) What is the meaning of "ideal >>
			// non-ideal"?  Russ says the ideal should be
			// converted to an int.  6g propagates the
			// type down from assignments as a hint.
1677

1678
			l = l.convertTo(IntType)
1679
			if l == nil {
1680
				return nil
1681 1682 1683 1684 1685 1686 1687 1688
			}
		}

		// At this point, we should have one of three cases:
		// 1) uint SHIFT uint
		// 2) int SHIFT uint
		// 3) ideal int SHIFT ideal int

1689
		t = l.t
1690 1691 1692

	case token.LOR, token.LAND:
		if !booleans() {
1693
			return nil
1694 1695 1696 1697 1698 1699 1700
		}
		// XXX(Spec) There's no mention of *which* boolean
		// type the logical operators return.  From poking at
		// 6g, it appears to be the named boolean type, NOT
		// the type of the left operand, and NOT an unnamed
		// boolean type.

1701
		t = BoolType
1702 1703 1704 1705 1706

	case token.ARROW:
		// The operands in channel sends differ in type: one
		// is always a channel and the other is a variable or
		// value of the channel's element type.
1707 1708
		log.Crash("Binary op <- not implemented")
		t = BoolType
1709 1710

	case token.LSS, token.GTR, token.LEQ, token.GEQ:
1711 1712 1713 1714 1715 1716 1717
		// XXX(Spec) It's really unclear what types which
		// comparison operators apply to.  I feel like the
		// text is trying to paint a Venn diagram for me,
		// which it's really pretty simple: <, <=, >, >= apply
		// only to numeric types and strings.  == and != apply
		// to everything except arrays and structs, and there
		// are some restrictions on when it applies to slices.
1718

1719
		if !compat() || (!integers() && !floats() && !strings()) {
1720 1721
			a.diagOpTypes(op, origlt, origrt)
			return nil
1722
		}
1723
		t = BoolType
1724 1725

	case token.EQL, token.NEQ:
1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741
		// XXX(Spec) The rules for type checking comparison
		// operators are spread across three places that all
		// partially overlap with each other: the Comparison
		// Compatibility section, the Operators section, and
		// the Comparison Operators section.  The Operators
		// section should just say that operators require
		// identical types (as it does currently) except that
		// there a few special cases for comparison, which are
		// described in section X.  Currently it includes just
		// one of the four special cases.  The Comparison
		// Compatibility section and the Comparison Operators
		// section should either be merged, or at least the
		// Comparison Compatibility section should be
		// exclusively about type checking and the Comparison
		// Operators section should be exclusively about
		// semantics.
1742 1743

		// XXX(Spec) Comparison operators: "All comparison
1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761
		// operators apply to basic types except bools."  This
		// is very difficult to parse.  It's explained much
		// better in the Comparison Compatibility section.

		// XXX(Spec) Comparison compatibility: "Function
		// values are equal if they refer to the same
		// function." is rather vague.  It should probably be
		// similar to the way the rule for map values is
		// written: Function values are equal if they were
		// created by the same execution of a function literal
		// or refer to the same function declaration.  This is
		// *almost* but not quite waht 6g implements.  If a
		// function literals does not capture any variables,
		// then multiple executions of it will result in the
		// same closure.  Russ says he'll change that.

		// TODO(austin) Deal with remaining special cases

1762
		if !compat() {
1763 1764
			a.diagOpTypes(op, origlt, origrt)
			return nil
1765 1766
		}
		// Arrays and structs may not be compared to anything.
1767 1768
		switch l.t.(type) {
		case *ArrayType, *StructType:
1769 1770
			a.diagOpTypes(op, origlt, origrt)
			return nil
1771
		}
1772
		t = BoolType
1773 1774

	default:
1775
		log.Crashf("unknown binary operator %v", op)
1776 1777
	}

1778
	desc, ok := binOpDescs[op]
1779
	if !ok {
1780 1781
		desc = op.String() + " expression"
		binOpDescs[op] = desc
1782 1783
	}

1784 1785 1786 1787 1788 1789
	// Check for ideal divide by zero
	switch op {
	case token.QUO, token.REM:
		if r.t.isIdeal() {
			if (r.t.isInteger() && r.asIdealInt()().IsZero()) ||
				(r.t.isFloat() && r.asIdealFloat()().IsZero()) {
1790 1791
				a.diag("divide by zero")
				return nil
1792 1793 1794 1795
			}
		}
	}

1796
	// Compile
1797
	expr := a.newExpr(t, desc)
1798
	switch op {
1799
	case token.ADD:
1800
		expr.genBinOpAdd(l, r)
1801 1802

	case token.SUB:
1803
		expr.genBinOpSub(l, r)
1804

1805
	case token.MUL:
1806
		expr.genBinOpMul(l, r)
1807

1808
	case token.QUO:
1809
		expr.genBinOpQuo(l, r)
1810

1811
	case token.REM:
1812
		expr.genBinOpRem(l, r)
1813 1814

	case token.AND:
1815
		expr.genBinOpAnd(l, r)
1816 1817

	case token.OR:
1818
		expr.genBinOpOr(l, r)
1819 1820

	case token.XOR:
1821
		expr.genBinOpXor(l, r)
1822 1823

	case token.AND_NOT:
1824
		expr.genBinOpAndNot(l, r)
1825 1826

	case token.SHL:
1827
		if l.t.isIdeal() {
1828 1829 1830
			lv := l.asIdealInt()()
			rv := r.asIdealInt()()
			const maxShift = 99999
1831
			if rv.Cmp(bignum.Int(maxShift)) > 0 {
1832 1833 1834
				a.diag("left shift by %v; exceeds implementation limit of %v", rv, maxShift)
				expr.t = nil
				return nil
1835
			}
1836 1837
			val := lv.Shl(uint(rv.Value()))
			expr.eval = func() *bignum.Integer { return val }
1838
		} else {
1839
			expr.genBinOpShl(l, r)
1840 1841 1842
		}

	case token.SHR:
1843
		if l.t.isIdeal() {
1844 1845 1846 1847
			lv := l.asIdealInt()()
			rv := r.asIdealInt()()
			val := lv.Shr(uint(rv.Value()))
			expr.eval = func() *bignum.Integer { return val }
1848
		} else {
1849
			expr.genBinOpShr(l, r)
1850 1851
		}

1852
	case token.LSS:
1853
		expr.genBinOpLss(l, r)
1854 1855

	case token.GTR:
1856
		expr.genBinOpGtr(l, r)
1857 1858

	case token.LEQ:
1859
		expr.genBinOpLeq(l, r)
1860 1861

	case token.GEQ:
1862
		expr.genBinOpGeq(l, r)
1863 1864

	case token.EQL:
1865
		expr.genBinOpEql(l, r)
1866 1867

	case token.NEQ:
1868
		expr.genBinOpNeq(l, r)
1869

Russ Cox's avatar
Russ Cox committed
1870
	case token.LAND:
1871
		expr.genBinOpLogAnd(l, r)
Russ Cox's avatar
Russ Cox committed
1872 1873

	case token.LOR:
1874
		expr.genBinOpLogOr(l, r)
Russ Cox's avatar
Russ Cox committed
1875

1876
	default:
1877
		log.Crashf("Compilation of binary op %v not implemented", op)
1878 1879
	}

1880
	return expr
1881 1882
}

1883 1884
// TODO(austin) This is a hack to eliminate a circular dependency
// between type.go and expr.go
1885
func (a *compiler) compileArrayLen(b *block, expr ast.Expr) (int64, bool) {
1886
	lenExpr := a.compileExpr(b, true, expr)
1887
	if lenExpr == nil {
1888
		return 0, false
1889 1890
	}

1891
	// XXX(Spec) Are ideal floats with no fractional part okay?
1892
	if lenExpr.t.isIdeal() {
1893
		lenExpr = lenExpr.convertTo(IntType)
1894
		if lenExpr == nil {
1895
			return 0, false
1896 1897 1898
		}
	}

1899
	if !lenExpr.t.isInteger() {
1900 1901
		a.diagAt(expr, "array size must be an integer")
		return 0, false
1902 1903
	}

Austin Clements's avatar
Austin Clements committed
1904
	switch lenExpr.t.lit().(type) {
1905
	case *intType:
1906
		return lenExpr.asInt()(nil), true
1907
	case *uintType:
1908
		return int64(lenExpr.asUint()(nil)), true
1909
	}
1910 1911
	log.Crashf("unexpected integer type %T", lenExpr.t)
	return 0, false
1912 1913
}

1914
func (a *compiler) compileExpr(b *block, constant bool, expr ast.Expr) *expr {
1915 1916 1917
	ec := &exprCompiler{a, b, constant}
	nerr := a.numError()
	e := ec.compile(expr, false)
1918
	if e == nil && nerr == a.numError() {
1919
		log.Crashf("expression compilation failed without reporting errors")
1920
	}
1921
	return e
1922 1923
}

1924 1925 1926
// extractEffect separates out any effects that the expression may
// have, returning a function that will perform those effects and a
// new exprCompiler that is guaranteed to be side-effect free.  These
1927 1928 1929 1930 1931
// are the moral equivalents of "temp := expr" and "temp" (or "temp :=
// &expr" and "*temp" for addressable exprs).  Because this creates a
// temporary variable, the caller should create a temporary block for
// the compilation of this expression and the evaluation of the
// results.
Russ Cox's avatar
Russ Cox committed
1932
func (a *expr) extractEffect(b *block, errOp string) (func(*Thread), *expr) {
1933
	// Create "&a" if a is addressable
1934
	rhs := a
1935
	if a.evalAddr != nil {
1936
		rhs = a.compileUnaryExpr(token.AND, rhs)
1937 1938 1939
	}

	// Create temp
1940
	ac, ok := a.checkAssign(a.pos, []*expr{rhs}, errOp, "")
1941
	if !ok {
1942
		return nil, nil
1943 1944
	}
	if len(ac.rmt.Elems) != 1 {
1945 1946
		a.diag("multi-valued expression not allowed in %s", errOp)
		return nil, nil
1947
	}
1948
	tempType := ac.rmt.Elems[0]
1949 1950 1951 1952
	if tempType.isIdeal() {
		// It's too bad we have to duplicate this rule.
		switch {
		case tempType.isInteger():
1953
			tempType = IntType
1954
		case tempType.isFloat():
1955
			tempType = FloatType
1956
		default:
1957
			log.Crashf("unexpected ideal type %v", tempType)
1958 1959
		}
	}
1960 1961
	temp := b.DefineTemp(tempType)
	tempIdx := temp.Index
1962

1963
	// Create "temp := rhs"
1964
	assign := ac.compile(b, tempType)
1965
	if assign == nil {
1966
		log.Crashf("compileAssign type check failed")
1967 1968
	}

Russ Cox's avatar
Russ Cox committed
1969
	effect := func(t *Thread) {
1970 1971 1972 1973
		tempVal := tempType.Zero()
		t.f.Vars[tempIdx] = tempVal
		assign(tempVal, t)
	}
1974

1975
	// Generate "temp" or "*temp"
1976
	getTemp := a.compileVariable(0, temp)
1977
	if a.evalAddr == nil {
1978
		return effect, getTemp
1979
	}
1980

1981
	deref := a.compileStarExpr(getTemp)
1982
	if deref == nil {
1983
		return nil, nil
1984
	}
1985
	return effect, deref
1986
}