// 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 (
	"bignum";
	"go/ast";
	"go/token";
	"log";
	"reflect";
	"sort";
	"unsafe";			// For Sizeof
)


// XXX(Spec) The type compatibility section is very confusing because
// it makes it seem like there are three distinct types of
// compatibility: plain compatibility, assignment compatibility, and
// comparison compatibility.  As I understand it, there's really only
// assignment compatibility and comparison and conversion have some
// restrictions and have special meaning in some cases where the types
// are not otherwise assignment compatible.  The comparison
// compatibility section is almost all about the semantics of
// comparison, not the type checking of it, so it would make much more
// sense in the comparison operators section.  The compatibility and
// assignment compatibility sections should be rolled into one.

type Type interface {
	// compat returns whether this type is compatible with another
	// type.  If conv is false, this is normal compatibility,
	// where two named types are compatible only if they are the
	// same named type.  If conv if true, this is conversion
	// compatibility, where two named types are conversion
	// compatible if their definitions are conversion compatible.
	//
	// TODO(austin) Deal with recursive types
	compat(o Type, conv bool) bool;
	// lit returns this type's literal.  If this is a named type,
	// this is the unnamed underlying type.  Otherwise, this is an
	// identity operation.
	lit() Type;
	// isBoolean returns true if this is a boolean type.
	isBoolean() bool;
	// isInteger returns true if this is an integer type.
	isInteger() bool;
	// isFloat returns true if this is a floating type.
	isFloat() bool;
	// isIdeal returns true if this is an ideal int or float.
	isIdeal() bool;
	// Zero returns a new zero value of this type.
	Zero() Value;
	// String returns the string representation of this type.
	String() string;
	// The position where this type was defined, if any.
	Pos() token.Position;
}

type BoundedType interface {
	Type;
	// minVal returns the smallest value of this type.
	minVal() *bignum.Rational;
	// maxVal returns the largest value of this type.
	maxVal() *bignum.Rational;
}

var universePos = token.Position{"<universe>", 0, 0, 0};

/*
 * Type array maps.  These are used to memoize composite types.
 */

type typeArrayMapEntry struct {
	key []Type;
	v interface {};
	next *typeArrayMapEntry;
}

type typeArrayMap map[uintptr] *typeArrayMapEntry

func hashTypeArray(key []Type) uintptr {
	hash := uintptr(0);
	for _, t := range key {
		hash = hash * 33;
		if t == nil {
			continue;
		}
		addr := reflect.NewValue(t).(*reflect.PtrValue).Get();
		hash ^= addr;
	}
	return hash;
}

func newTypeArrayMap() typeArrayMap {
	return make(map[uintptr] *typeArrayMapEntry);
}

func (m typeArrayMap) Get(key []Type) (interface{}) {
	ent, ok := m[hashTypeArray(key)];
	if !ok {
		return nil;
	}

nextEnt:
	for ; ent != nil; ent = ent.next {
		if len(key) != len(ent.key) {
			continue;
		}
		for i := 0; i < len(key); i++ {
			if key[i] != ent.key[i] {
				continue nextEnt;
			}
		}
		// Found it
		return ent.v;
	}

	return nil;
}

func (m typeArrayMap) Put(key []Type, v interface{}) interface{} {
	hash := hashTypeArray(key);
	ent, _ := m[hash];

	new := &typeArrayMapEntry{key, v, ent};
	m[hash] = new;
	return v;
}

/*
 * Common type
 */

type commonType struct {
}

func (commonType) isBoolean() bool {
	return false;
}

func (commonType) isInteger() bool {
	return false;
}

func (commonType) isFloat() bool {
	return false;
}

func (commonType) isIdeal() bool {
	return false;
}

func (commonType) Pos() token.Position {
	return token.Position{};
}

/*
 * Bool
 */

type boolType struct {
	commonType;
}

var BoolType = universe.DefineType("bool", universePos, &boolType{})

func (t *boolType) compat(o Type, conv bool) bool {
	_, ok := o.lit().(*boolType);
	return ok;
}

func (t *boolType) lit() Type {
	return t;
}

func (t *boolType) isBoolean() bool {
	return true;
}

func (boolType) String() string {
	// Use angle brackets as a convention for printing the
	// underlying, unnamed type.  This should only show up in
	// debug output.
	return "<bool>";
}

func (t *boolType) Zero() Value {
	res := boolV(false);
	return &res;
}

/*
 * Uint
 */

type uintType struct {
	commonType;

	// 0 for architecture-dependent types
	Bits uint;
	// true for uintptr, false for all others
	Ptr bool;
	name string;
}

var (
	Uint8Type   = universe.DefineType("uint8",   universePos, &uintType{commonType{}, 8,  false, "uint8"});
	Uint16Type  = universe.DefineType("uint16",  universePos, &uintType{commonType{}, 16, false, "uint16"});
	Uint32Type  = universe.DefineType("uint32",  universePos, &uintType{commonType{}, 32, false, "uint32"});
	Uint64Type  = universe.DefineType("uint64",  universePos, &uintType{commonType{}, 64, false, "uint64"});

	UintType    = universe.DefineType("uint",    universePos, &uintType{commonType{}, 0,  false, "uint"});
	UintptrType = universe.DefineType("uintptr", universePos, &uintType{commonType{}, 0,  true,  "uintptr"});
)

func (t *uintType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*uintType);
	return ok && t == t2;;
}

func (t *uintType) lit() Type {
	return t;
}

func (t *uintType) isInteger() bool {
	return true;
}

func (t *uintType) String() string {
	return "<" + t.name + ">";
}

func (t *uintType) Zero() Value {
	switch t.Bits {
	case 0:
		if t.Ptr {
			res := uintptrV(0);
			return &res;
		} else {
			res := uintV(0);
			return &res;
		}
	case 8:
		res := uint8V(0);
		return &res;
	case 16:
		res := uint16V(0);
		return &res;
	case 32:
		res := uint32V(0);
		return &res;
	case 64:
		res := uint64V(0);
		return &res;
	}
	panic("unexpected uint bit count: ", t.Bits);
}

func (t *uintType) minVal() *bignum.Rational {
	return bignum.Rat(0, 1);
}

func (t *uintType) maxVal() *bignum.Rational {
	bits := t.Bits;
	if bits == 0 {
		if t.Ptr {
			bits = uint(8 * unsafe.Sizeof(uintptr(0)));
		} else {
			bits = uint(8 * unsafe.Sizeof(uint(0)));
		}
	}
	return bignum.MakeRat(bignum.Int(1).Shl(bits).Add(bignum.Int(-1)), bignum.Nat(1));
}

/*
 * Int
 */

type intType struct {
	commonType;

	// XXX(Spec) Numeric types: "There is also a set of
	// architecture-independent basic numeric types whose size
	// depends on the architecture."  Should that be
	// architecture-dependent?

	// 0 for architecture-dependent types
	Bits uint;
	name string;
}

var (
	Int8Type  = universe.DefineType("int8",  universePos, &intType{commonType{}, 8,  "int8"});
	Int16Type = universe.DefineType("int16", universePos, &intType{commonType{}, 16, "int16"});
	Int32Type = universe.DefineType("int32", universePos, &intType{commonType{}, 32, "int32"});
	Int64Type = universe.DefineType("int64", universePos, &intType{commonType{}, 64, "int64"});

	IntType   = universe.DefineType("int",   universePos, &intType{commonType{}, 0,  "int"});
)

func (t *intType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*intType);
	return ok && t == t2;
}

func (t *intType) lit() Type {
	return t;
}

func (t *intType) isInteger() bool {
	return true;
}

func (t *intType) String() string {
	return "<" + t.name + ">";
}

func (t *intType) Zero() Value {
	switch t.Bits {
	case 8:
		res := int8V(0);
		return &res;
	case 16:
		res := int16V(0);
		return &res;
	case 32:
		res := int32V(0);
		return &res;
	case 64:
		res := int64V(0);
		return &res;

	case 0:
		res := intV(0);
		return &res;
	}
	panic("unexpected int bit count: ", t.Bits);
}

func (t *intType) minVal() *bignum.Rational {
	bits := t.Bits;
	if bits == 0 {
		bits = uint(8 * unsafe.Sizeof(int(0)));
	}
	return bignum.MakeRat(bignum.Int(-1).Shl(bits - 1), bignum.Nat(1));
}

func (t *intType) maxVal() *bignum.Rational {
	bits := t.Bits;
	if bits == 0 {
		bits = uint(8 * unsafe.Sizeof(int(0)));
	}
	return bignum.MakeRat(bignum.Int(1).Shl(bits - 1).Add(bignum.Int(-1)), bignum.Nat(1));
}

/*
 * Ideal int
 */

type idealIntType struct {
	commonType;
}

var IdealIntType Type = &idealIntType{}

func (t *idealIntType) compat(o Type, conv bool) bool {
	_, ok := o.lit().(*idealIntType);
	return ok;
}

func (t *idealIntType) lit() Type {
	return t;
}

func (t *idealIntType) isInteger() bool {
	return true;
}

func (t *idealIntType) isIdeal() bool {
	return true;
}

func (t *idealIntType) String() string {
	return "ideal integer";
}

func (t *idealIntType) Zero() Value {
	return &idealIntV{bignum.Int(0)};
}

/*
 * Float
 */

type floatType struct {
	commonType;

	// 0 for architecture-dependent type
	Bits uint;

	name string;
}

var (
	Float32Type = universe.DefineType("float32", universePos, &floatType{commonType{}, 32, "float32"});
	Float64Type = universe.DefineType("float64", universePos, &floatType{commonType{}, 64, "float64"});
	FloatType   = universe.DefineType("float",   universePos, &floatType{commonType{}, 0,  "float"});
)

func (t *floatType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*floatType);
	return ok && t == t2;
}

func (t *floatType) lit() Type {
	return t;
}

func (t *floatType) isFloat() bool {
	return true;
}

func (t *floatType) String() string {
	return "<" + t.name + ">";
}

func (t *floatType) Zero() Value {
	switch t.Bits {
	case 32:
		res := float32V(0);
		return &res;
	case 64:
		res := float64V(0);
		return &res;
	case 0:
		res := floatV(0);
		return &res;
	}
	panic("unexpected float bit count: ", t.Bits);
}

var maxFloat32Val = bignum.MakeRat(bignum.Int(0xffffff).Shl(127-23), bignum.Nat(1))
var maxFloat64Val = bignum.MakeRat(bignum.Int(0x1fffffffffffff).Shl(1023-52), bignum.Nat(1))
var minFloat32Val = maxFloat32Val.Neg()
var minFloat64Val = maxFloat64Val.Neg()

func (t *floatType) minVal() *bignum.Rational {
	bits := t.Bits;
	if bits == 0 {
		bits = uint(8 * unsafe.Sizeof(float(0)));
	}
	switch bits {
	case 32:
		return minFloat32Val;
	case 64:
		return minFloat64Val;
	}
	log.Crashf("unexpected floating point bit count: %d", bits);
	panic();
}

func (t *floatType) maxVal() *bignum.Rational {
	bits := t.Bits;
	if bits == 0 {
		bits = uint(8 * unsafe.Sizeof(float(0)));
	}
	switch bits {
	case 32:
		return maxFloat32Val;
	case 64:
		return maxFloat64Val;
	}
	log.Crashf("unexpected floating point bit count: %d", bits);
	panic();
}

/*
 * Ideal float
 */

type idealFloatType struct {
	commonType;
}

var IdealFloatType Type = &idealFloatType{};

func (t *idealFloatType) compat(o Type, conv bool) bool {
	_, ok := o.lit().(*idealFloatType);
	return ok;
}

func (t *idealFloatType) lit() Type {
	return t;
}

func (t *idealFloatType) isFloat() bool {
	return true;
}

func (t *idealFloatType) isIdeal() bool {
	return true;
}

func (t *idealFloatType) String() string {
	return "ideal float";
}

func (t *idealFloatType) Zero() Value {
	return &idealFloatV{bignum.Rat(1, 0)};
}

/*
 * String
 */

type stringType struct {
	commonType;
}

var StringType = universe.DefineType("string", universePos, &stringType{})

func (t *stringType) compat(o Type, conv bool) bool {
	_, ok := o.lit().(*stringType);
	return ok;
}

func (t *stringType) lit() Type {
	return t;
}

func (t *stringType) String() string {
	return "<string>";
}

func (t *stringType) Zero() Value {
	res := stringV("");
	return &res;
}

/*
 * Array
 */

type ArrayType struct {
	commonType;
	Len int64;
	Elem Type;
}

var arrayTypes = make(map[int64] map[Type] *ArrayType)

// Two array types are identical if they have identical element types
// and the same array length.

func NewArrayType(len int64, elem Type) *ArrayType {
	ts, ok := arrayTypes[len];
	if !ok {
		ts = make(map[Type] *ArrayType);
		arrayTypes[len] = ts;
	}
	t, ok := ts[elem];
	if !ok {
		t = &ArrayType{commonType{}, len, elem};
		ts[elem] = t;
	}
	return t;
}

func (t *ArrayType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*ArrayType);
	if !ok {
		return false;
	}
	return t.Len == t2.Len && t.Elem.compat(t2.Elem, conv);
}

func (t *ArrayType) lit() Type {
	return t;
}

func (t *ArrayType) String() string {
	return "[]" + t.Elem.String();
}

func (t *ArrayType) Zero() Value {
	res := arrayV(make([]Value, t.Len));
	// TODO(austin) It's unfortunate that each element is
	// separately heap allocated.  We could add ZeroArray to
	// everything, though that doesn't help with multidimensional
	// arrays.  Or we could do something unsafe.  We'll have this
	// same problem with structs.
	for i := int64(0); i < t.Len; i++ {
		res[i] = t.Elem.Zero();
	}
	return &res;
}

/*
 * Struct
 */

type StructField struct {
	Name string;
	Type Type;
	Anonymous bool;
}

type StructType struct {
	commonType;
	Elems []StructField;
}

var structTypes = newTypeArrayMap()

// Two struct types are identical if they have the same sequence of
// fields, and if corresponding fields have the same names and
// identical types. Two anonymous fields are considered to have the
// same name.

func NewStructType(fields []StructField) *StructType {
	// Start by looking up just the types
	fts := make([]Type, len(fields));
	for i, f := range fields {
		fts[i] = f.Type;
	}
	tMapI := structTypes.Get(fts);
	if tMapI == nil {
		tMapI = structTypes.Put(fts, make(map[string] *StructType));
	}
	tMap := tMapI.(map[string] *StructType);

	// Construct key for field names
	key := "";
	for _, f := range fields {
		// XXX(Spec) It's not clear if struct { T } and struct
		// { T T } are either identical or compatible.  The
		// "Struct Types" section says that the name of that
		// field is "T", which suggests that they are
		// identical, but it really means that it's the name
		// for the purpose of selector expressions and nothing
		// else.  We decided that they should be neither
		// identical or compatible.
		if f.Anonymous {
			key += "!";
		}
		key += f.Name + " ";
	}

	// XXX(Spec) Do the tags also have to be identical for the
	// types to be identical?  I certainly hope so, because
	// otherwise, this is the only case where two distinct type
	// objects can represent identical types.

	t, ok := tMap[key];
	if !ok {
		// Create new struct type
		t = &StructType{commonType{}, fields};
		tMap[key] = t;
	}
	return t;
}

func (t *StructType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*StructType);
	if !ok {
		return false;
	}
	if len(t.Elems) != len(t2.Elems) {
		return false;
	}
	for i, e := range t.Elems {
		e2 := t2.Elems[i];
		// XXX(Spec) An anonymous and a non-anonymous field
		// are neither identical nor compatible.
		if (e.Anonymous != e2.Anonymous ||
		    (!e.Anonymous && e.Name != e2.Name) ||
		    !e.Type.compat(e2.Type, conv)) {
			return false;
		}
	}
	return true;
}

func (t *StructType) lit() Type {
	return t;
}

func (t *StructType) String() string {
	s := "struct {";
	for i, f := range t.Elems {
		if i > 0 {
			s += "; ";
		}
		if !f.Anonymous {
			s += f.Name + " ";
		}
		s += f.Type.String();
	}
	return s + "}";
}

func (t *StructType) Zero() Value {
	res := structV(make([]Value, len(t.Elems)));
	for i, f := range t.Elems {
		res[i] = f.Type.Zero();
	}
	return &res;
}

/*
 * Pointer
 */

type PtrType struct {
	commonType;
	Elem Type;
}

var ptrTypes = make(map[Type] *PtrType)

// Two pointer types are identical if they have identical base types.

func NewPtrType(elem Type) *PtrType {
	t, ok := ptrTypes[elem];
	if !ok {
		t = &PtrType{commonType{}, elem};
		ptrTypes[elem] = t;
	}
	return t;
}

func (t *PtrType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*PtrType);
	if !ok {
		return false;
	}
	return t.Elem.compat(t2.Elem, conv);
}

func (t *PtrType) lit() Type {
	return t;
}

func (t *PtrType) String() string {
	return "*" + t.Elem.String();
}

func (t *PtrType) Zero() Value {
	return &ptrV{nil};
}

/*
 * Function
 */

type FuncType struct {
	commonType;
	// TODO(austin) Separate receiver Type for methods?
	In []Type;
	Variadic bool;
	Out []Type;
	builtin string;
}

var funcTypes = newTypeArrayMap()
var variadicFuncTypes = newTypeArrayMap()

// Create singleton function types for magic built-in functions
var (
	capType     = &FuncType{builtin: "cap"};
	closeType   = &FuncType{builtin: "close"};
	closedType  = &FuncType{builtin: "closed"};
	lenType     = &FuncType{builtin: "len"};
	makeType    = &FuncType{builtin: "make"};
	newType     = &FuncType{builtin: "new"};
	panicType   = &FuncType{builtin: "panic"};
	paniclnType = &FuncType{builtin: "panicln"};
	printType   = &FuncType{builtin: "print"};
	printlnType = &FuncType{builtin: "println"};
)

// Two function types are identical if they have the same number of
// parameters and result values and if corresponding parameter and
// result types are identical. All "..." parameters have identical
// type. Parameter and result names are not required to match.

func NewFuncType(in []Type, variadic bool, out []Type) *FuncType {
	inMap := funcTypes;
	if variadic {
		inMap = variadicFuncTypes;
	}

	outMapI := inMap.Get(in);
	if outMapI == nil {
		outMapI = inMap.Put(in, newTypeArrayMap());
	}
	outMap := outMapI.(typeArrayMap);

	tI := outMap.Get(out);
	if tI != nil {
		return tI.(*FuncType);
	}

	t := &FuncType{commonType{}, in, variadic, out, ""};
	outMap.Put(out, t);
	return t;
}

func (t *FuncType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*FuncType);
	if !ok {
		return false;
	}
	if len(t.In) != len(t2.In) || t.Variadic != t2.Variadic || len(t.Out) != len(t2.Out) {
		return false;
	}
	for i := range t.In {
		if !t.In[i].compat(t2.In[i], conv) {
			return false;
		}
	}
	for i := range t.Out {
		if !t.Out[i].compat(t2.Out[i], conv) {
			return false;
		}
	}
	return true;
}

func (t *FuncType) lit() Type {
	return t;
}

func typeListString(ts []Type, ns []*ast.Ident) string {
	s := "";
	for i, t := range ts {
		if i > 0 {
			s += ", ";
		}
		if ns != nil && ns[i] != nil {
			s += ns[i].Value + " ";
		}
		if t == nil {
			// Some places use nil types to represent errors
			s += "<none>";
		} else {
			s += t.String();
		}
	}
	return s;
}

func (t *FuncType) String() string {
	if t.builtin != "" {
		return "built-in function " + t.builtin;
	}
	args := typeListString(t.In, nil);
	if t.Variadic {
		if len(args) > 0 {
			args += ", ";
		}
		args += "...";
	}
	s := "func(" + args + ")";
	if len(t.Out) > 0 {
		s += " (" + typeListString(t.Out, nil) + ")";
	}
	return s;
}

func (t *FuncType) Zero() Value {
	return &funcV{nil};
}

type FuncDecl struct {
	Type *FuncType;
	Name *ast.Ident;		// nil for function literals
	// InNames will be one longer than Type.In if this function is
	// variadic.
	InNames []*ast.Ident;
	OutNames []*ast.Ident;
}

func (t *FuncDecl) String() string {
	s := "func";
	if t.Name != nil {
		s += " " + t.Name.Value;
	}
	s += funcTypeString(t.Type, t.InNames, t.OutNames);
	return s;
}

func funcTypeString(ft *FuncType, ins []*ast.Ident, outs []*ast.Ident) string {
	s := "(";
	s += typeListString(ft.In, ins);
	if ft.Variadic {
		if len(ft.In) > 0 {
			s += ", ";
		}
		s += "...";
	}
	s += ")";
	if len(ft.Out) > 0 {
		s += " (" + typeListString(ft.Out, outs) + ")";
	}
	return s;
}

/*
 * Interface
 */

// TODO(austin) Interface values, types, and type compilation are
// implemented, but none of the type checking or semantics of
// interfaces are.

type InterfaceType struct {
	commonType;
	// TODO(austin) This should be a map from names to
	// *FuncType's.  We only need the sorted list for generating
	// the type map key.  It's detrimental for everything else.
	methods []IMethod;
}

type IMethod struct {
	Name string;
	Type *FuncType;
}

var interfaceTypes = newTypeArrayMap()

func NewInterfaceType(methods []IMethod, embeds []*InterfaceType) *InterfaceType {
	// Count methods of embedded interfaces
	nMethods := len(methods);
	for _, e := range embeds {
		nMethods += len(e.methods);
	}

	// Combine methods
	allMethods := make([]IMethod, nMethods);
	for i, m := range methods {
		allMethods[i] = m;
	}
	n := len(methods);
	for _, e := range embeds {
		for _, m := range e.methods {
			allMethods[n] = m;
			n++;
		}
	}

	// Sort methods
	sort.Sort(iMethodSorter(allMethods));

	mts := make([]Type, len(allMethods));
	for i, m := range methods {
		mts[i] = m.Type;
	}
	tMapI := interfaceTypes.Get(mts);
	if tMapI == nil {
		tMapI = interfaceTypes.Put(mts, make(map[string] *InterfaceType));
	}
	tMap := tMapI.(map[string] *InterfaceType);

	key := "";
	for _, m := range allMethods {
		key += m.Name + " ";
	}

	t, ok := tMap[key];
	if !ok {
		t = &InterfaceType{commonType{}, allMethods};
		tMap[key] = t;
	}
	return t;
}

type iMethodSorter []IMethod

func (s iMethodSorter) Less(a, b int) bool {
	return s[a].Name < s[b].Name;
}

func (s iMethodSorter) Swap(a, b int) {
	s[a], s[b] = s[b], s[a];
}

func (s iMethodSorter) Len() int {
	return len(s);
}

func (t *InterfaceType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*InterfaceType);
	if !ok {
		return false;
	}
	if len(t.methods) != len(t2.methods) {
		return false;
	}
	for i, e := range t.methods {
		e2 := t2.methods[i];
		if e.Name != e2.Name || !e.Type.compat(e2.Type, conv) {
			return false;
		}
	}
	return true;
}

func (t *InterfaceType) lit() Type {
	return t;
}

func (t *InterfaceType) String() string {
	// TODO(austin) Instead of showing embedded interfaces, this
	// shows their methods.
	s := "interface {";
	for i, m := range t.methods {
		if i > 0 {
			s += "; ";
		}
		s += m.Name + funcTypeString(m.Type, nil, nil);
	}
	return s + "}";
}

// implementedBy tests if o implements t, returning nil, true if it does.
// Otherwise, it returns a method of t that o is missing and false.
func (t *InterfaceType) implementedBy(o Type) (*IMethod, bool) {
	if len(t.methods) == 0 {
		return nil, true;
	}

	// The methods of a named interface types are those of the
	// underlying type.
	if it, ok := o.lit().(*InterfaceType); ok {
		o = it;
	}

	// XXX(Spec) Interface types: "A type implements any interface
	// comprising any subset of its methods" It's unclear if
	// methods must have identical or compatible types.  6g
	// requires identical types.

	switch o := o.(type) {
	case *NamedType:
		for _, tm := range t.methods {
			sm, ok := o.methods[tm.Name];
			if !ok || sm.decl.Type != tm.Type {
				return &tm, false;
			}
		}
		return nil, true;

	case *InterfaceType:
		var ti, oi int;
		for ti < len(t.methods) && oi < len(o.methods) {
			tm, om := &t.methods[ti], &o.methods[oi];
			switch {
			case tm.Name == om.Name:
				if tm.Type != om.Type {
					return tm, false;
				}
				ti++;
				oi++;
			case tm.Name > om.Name:
				oi++;
			default:
				return tm, false;
			}
		}
		if ti < len(t.methods) {
			return &t.methods[ti], false;
		}
		return nil, true;
	}

	return &t.methods[0], false;
}

func (t *InterfaceType) Zero() Value {
	return &interfaceV{};
}

/*
 * Slice
 */

type SliceType struct {
	commonType;
	Elem Type;
}

var sliceTypes = make(map[Type] *SliceType)

// Two slice types are identical if they have identical element types.

func NewSliceType(elem Type) *SliceType {
	t, ok := sliceTypes[elem];
	if !ok {
		t = &SliceType{commonType{}, elem};
		sliceTypes[elem] = t;
	}
	return t;
}

func (t *SliceType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*SliceType);
	if !ok {
		return false;
	}
	return t.Elem.compat(t2.Elem, conv);
}

func (t *SliceType) lit() Type {
	return t;
}

func (t *SliceType) String() string {
	return "[]" + t.Elem.String();
}

func (t *SliceType) Zero() Value {
	// The value of an uninitialized slice is nil. The length and
	// capacity of a nil slice are 0.
	return &sliceV{Slice{nil, 0, 0}};
}

/*
 * Map type
 */

type MapType struct {
	commonType;
	Key Type;
	Elem Type;
}

var mapTypes = make(map[Type] map[Type] *MapType)

func NewMapType(key Type, elem Type) *MapType {
	ts, ok := mapTypes[key];
	if !ok {
		ts = make(map[Type] *MapType);
		mapTypes[key] = ts;
	}
	t, ok := ts[elem];
	if !ok {
		t = &MapType{commonType{}, key, elem};
		ts[elem] = t;
	}
	return t;
}

func (t *MapType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*MapType);
	if !ok {
		return false;
	}
	return t.Elem.compat(t2.Elem, conv) && t.Key.compat(t2.Key, conv);
}

func (t *MapType) lit() Type {
	return t;
}

func (t *MapType) String() string {
	return "map[" + t.Key.String() + "] " + t.Elem.String();
}

func (t *MapType) Zero() Value {
	// The value of an uninitialized map is nil.
	return &mapV{nil};
}

/*
type ChanType struct {
	// TODO(austin)
}
*/

/*
 * Named types
 */

type Method struct {
	decl *FuncDecl;
	fn Func;
}

type NamedType struct {
	token.Position;
	Name string;
	// Underlying type.  If incomplete is true, this will be nil.
	// If incomplete is false and this is still nil, then this is
	// a placeholder type representing an error.
	Def Type;
	// True while this type is being defined.
	incomplete bool;
	methods map[string] Method;
}

// TODO(austin) This is temporarily needed by the debugger's remote
// type parser.  This should only be possible with block.DefineType.
func NewNamedType(name string) *NamedType {
	return &NamedType{token.Position{}, name, nil, true, make(map[string] Method)};
}

func (t *NamedType) Complete(def Type) {
	if !t.incomplete {
		log.Crashf("cannot complete already completed NamedType %+v", *t);
	}
	// We strip the name from def because multiple levels of
	// naming are useless.
	if ndef, ok := def.(*NamedType); ok {
		def = ndef.Def;
	}
	t.Def = def;
	t.incomplete = false;
}

func (t *NamedType) compat(o Type, conv bool) bool {
	t2, ok := o.(*NamedType);
	if ok {
		if conv {
			// Two named types are conversion compatible
			// if their literals are conversion
			// compatible.
			return t.Def.compat(t2.Def, conv);
		} else {
			// Two named types are compatible if their
			// type names originate in the same type
			// declaration.
			return t == t2;
		}
	}
	// A named and an unnamed type are compatible if the
	// respective type literals are compatible.
	return o.compat(t.Def, conv);
}

func (t *NamedType) lit() Type {
	return t.Def.lit();
}

func (t *NamedType) isBoolean() bool {
	return t.Def.isBoolean();
}

func (t *NamedType) isInteger() bool {
	return t.Def.isInteger();
}

func (t *NamedType) isFloat() bool {
	return t.Def.isFloat();
}

func (t *NamedType) isIdeal() bool {
	return false;
}

func (t *NamedType) String() string {
	return t.Name;
}

func (t *NamedType) Zero() Value {
	return t.Def.Zero();
}

/*
 * Multi-valued type
 */

// MultiType is a special type used for multi-valued expressions, akin
// to a tuple type.  It's not generally accessible within the
// language.
type MultiType struct {
	commonType;
	Elems []Type;
}

var multiTypes = newTypeArrayMap()

func NewMultiType(elems []Type) *MultiType {
	if t := multiTypes.Get(elems); t != nil {
		return t.(*MultiType);
	}

	t := &MultiType{commonType{}, elems};
	multiTypes.Put(elems, t);
	return t;
}

func (t *MultiType) compat(o Type, conv bool) bool {
	t2, ok := o.lit().(*MultiType);
	if !ok {
		return false;
	}
	if len(t.Elems) != len(t2.Elems) {
		return false;
	}
	for i := range t.Elems {
		if !t.Elems[i].compat(t2.Elems[i], conv) {
			return false;
		}
	}
	return true;
}

var EmptyType Type = NewMultiType([]Type{})

func (t *MultiType) lit() Type {
	return t;
}

func (t *MultiType) String() string {
	if len(t.Elems) == 0 {
		return "<none>";
	}
	return typeListString(t.Elems, nil);
}

func (t *MultiType) Zero() Value {
	res := make([]Value, len(t.Elems));
	for i, t := range t.Elems {
		res[i] = t.Zero();
	}
	return multiV(res);
}

/*
 * Initialize the universe
 */

func init() {
	// To avoid portability issues all numeric types are distinct
	// except byte, which is an alias for uint8.

	// Make byte an alias for the named type uint8.  Type aliases
	// are otherwise impossible in Go, so just hack it here.
	universe.defs["byte"] = universe.defs["uint8"];

	// Built-in functions
	universe.DefineConst("cap", universePos, capType, nil);
	universe.DefineConst("close", universePos, closeType, nil);
	universe.DefineConst("closed", universePos, closedType, nil);
	universe.DefineConst("len", universePos, lenType, nil);
	universe.DefineConst("make", universePos, makeType, nil);
	universe.DefineConst("new", universePos, newType, nil);
	universe.DefineConst("panic", universePos, panicType, nil);
	universe.DefineConst("panicln", universePos, paniclnType, nil);
	universe.DefineConst("print", universePos, printType, nil);
	universe.DefineConst("println", universePos, printlnType, nil);
}