compiler: fix crash with linked lists in interfaces

This commit fixes the following issue:
https://github.com/tinygo-org/tinygo/issues/309
Also, it prepares for some other reflect-related changes that should
make it easier to add support for named types (etc.) in the future.

6 files changed, 93 insertions, 58 deletions

diff --git a/compiler/func.go b/compiler/func.go
index c4806a09d..d9879d748 100644
--- a/compiler/func.go
+++ b/compiler/func.go
@@ -48,7 +48,7 @@ func (c *Compiler) createFuncValue(funcPtr, context llvm.Value, sig *types.Signa
 		// Closure is: {context, function pointer}
 		funcValueScalar = funcPtr
 	case funcValueSwitch:
-		sigGlobal := c.getFuncSignature(sig)
+		sigGlobal := c.getTypeCode(sig)
 		funcValueWithSignatureGlobalName := funcPtr.Name() + "$withSignature"
 		funcValueWithSignatureGlobal := c.mod.NamedGlobal(funcValueWithSignatureGlobalName)
 		if funcValueWithSignatureGlobal.IsNil() {
@@ -73,22 +73,6 @@ func (c *Compiler) createFuncValue(funcPtr, context llvm.Value, sig *types.Signa
 	return funcValue
 }
 
-// getFuncSignature returns a global for identification of a particular function
-// signature. It is used in runtime.funcValueWithSignature and in calls to
-// getFuncPtr.
-func (c *Compiler) getFuncSignature(sig *types.Signature) llvm.Value {
-	typeCodeName := getTypeCodeName(sig)
-	sigGlobalName := "reflect/types.type:" + typeCodeName
-	sigGlobal := c.mod.NamedGlobal(sigGlobalName)
-	if sigGlobal.IsNil() {
-		sigGlobal = llvm.AddGlobal(c.mod, c.ctx.Int8Type(), sigGlobalName)
-		sigGlobal.SetInitializer(llvm.Undef(c.ctx.Int8Type()))
-		sigGlobal.SetGlobalConstant(true)
-		sigGlobal.SetLinkage(llvm.InternalLinkage)
-	}
-	return sigGlobal
-}
-
 // extractFuncScalar returns some scalar that can be used in comparisons. It is
 // a cheap operation.
 func (c *Compiler) extractFuncScalar(funcValue llvm.Value) llvm.Value {
@@ -110,7 +94,7 @@ func (c *Compiler) decodeFuncValue(funcValue llvm.Value, sig *types.Signature) (
 		funcPtr = c.builder.CreateExtractValue(funcValue, 1, "")
 	case funcValueSwitch:
 		llvmSig := c.getRawFuncType(sig)
-		sigGlobal := c.getFuncSignature(sig)
+		sigGlobal := c.getTypeCode(sig)
 		funcPtr = c.createRuntimeCall("getFuncPtr", []llvm.Value{funcValue, sigGlobal}, "")
 		funcPtr = c.builder.CreateIntToPtr(funcPtr, llvmSig, "")
 	default:
diff --git a/compiler/interface.go b/compiler/interface.go
index d91b8063f..94a60f3dc 100644
--- a/compiler/interface.go
+++ b/compiler/interface.go
@@ -45,10 +45,32 @@ func (c *Compiler) parseMakeInterface(val llvm.Value, typ types.Type, pos token.
 // It returns a pointer to an external global which should be replaced with the
 // real type in the interface lowering pass.
 func (c *Compiler) getTypeCode(typ types.Type) llvm.Value {
-	globalName := "type:" + getTypeCodeName(typ)
+	globalName := "reflect/types.type:" + getTypeCodeName(typ)
 	global := c.mod.NamedGlobal(globalName)
 	if global.IsNil() {
+		// Create a new typecode global.
 		global = llvm.AddGlobal(c.mod, c.getLLVMRuntimeType("typecodeID"), globalName)
+		// Some type classes contain more information for underlying types or
+		// element types. Store it directly in the typecode global to make
+		// reflect lowering simpler.
+		var elementType types.Type
+		switch typ := typ.(type) {
+		case *types.Named:
+			elementType = typ.Underlying()
+		case *types.Chan:
+			elementType = typ.Elem()
+		case *types.Pointer:
+			elementType = typ.Elem()
+		case *types.Slice:
+			elementType = typ.Elem()
+		}
+		if elementType != nil {
+			// Set the 'references' field of the runtime.typecodeID struct.
+			globalValue := c.getZeroValue(global.Type().ElementType())
+			globalValue = llvm.ConstInsertValue(globalValue, c.getTypeCode(elementType), []uint32{0})
+			global.SetInitializer(globalValue)
+			global.SetLinkage(llvm.PrivateLinkage)
+		}
 		global.SetGlobalConstant(true)
 	}
 	return global
@@ -58,14 +80,11 @@ func (c *Compiler) getTypeCode(typ types.Type) llvm.Value {
 // interface lowering pass to assign type codes as expected by the reflect
 // package. See getTypeCodeNum.
 func getTypeCodeName(t types.Type) string {
-	name := ""
-	if named, ok := t.(*types.Named); ok {
-		name = "~" + named.String() + ":"
-		t = t.Underlying()
-	}
 	switch t := t.(type) {
+	case *types.Named:
+		return "named:" + t.String()
 	case *types.Array:
-		return "array:" + name + strconv.FormatInt(t.Len(), 10) + ":" + getTypeCodeName(t.Elem())
+		return "array:" + strconv.FormatInt(t.Len(), 10) + ":" + getTypeCodeName(t.Elem())
 	case *types.Basic:
 		var kind string
 		switch t.Kind() {
@@ -108,21 +127,21 @@ func getTypeCodeName(t types.Type) string {
 		default:
 			panic("unknown basic type: " + t.Name())
 		}
-		return "basic:" + name + kind
+		return "basic:" + kind
 	case *types.Chan:
-		return "chan:" + name + getTypeCodeName(t.Elem())
+		return "chan:" + getTypeCodeName(t.Elem())
 	case *types.Interface:
 		methods := make([]string, t.NumMethods())
 		for i := 0; i < t.NumMethods(); i++ {
 			methods[i] = getTypeCodeName(t.Method(i).Type())
 		}
-		return "interface:" + name + "{" + strings.Join(methods, ",") + "}"
+		return "interface:" + "{" + strings.Join(methods, ",") + "}"
 	case *types.Map:
 		keyType := getTypeCodeName(t.Key())
 		elemType := getTypeCodeName(t.Elem())
-		return "map:" + name + "{" + keyType + "," + elemType + "}"
+		return "map:" + "{" + keyType + "," + elemType + "}"
 	case *types.Pointer:
-		return "pointer:" + name + getTypeCodeName(t.Elem())
+		return "pointer:" + getTypeCodeName(t.Elem())
 	case *types.Signature:
 		params := make([]string, t.Params().Len())
 		for i := 0; i < t.Params().Len(); i++ {
@@ -132,9 +151,9 @@ func getTypeCodeName(t types.Type) string {
 		for i := 0; i < t.Results().Len(); i++ {
 			results[i] = getTypeCodeName(t.Results().At(i).Type())
 		}
-		return "func:" + name + "{" + strings.Join(params, ",") + "}{" + strings.Join(results, ",") + "}"
+		return "func:" + "{" + strings.Join(params, ",") + "}{" + strings.Join(results, ",") + "}"
 	case *types.Slice:
-		return "slice:" + name + getTypeCodeName(t.Elem())
+		return "slice:" + getTypeCodeName(t.Elem())
 	case *types.Struct:
 		elems := make([]string, t.NumFields())
 		if t.NumFields() > 2 && t.Field(0).Name() == "C union" {
@@ -144,7 +163,7 @@ func getTypeCodeName(t types.Type) string {
 		for i := 0; i < t.NumFields(); i++ {
 			elems[i] = getTypeCodeName(t.Field(i).Type())
 		}
-		return "struct:" + name + "{" + strings.Join(elems, ",") + "}"
+		return "struct:" + "{" + strings.Join(elems, ",") + "}"
 	default:
 		panic("unknown type: " + t.String())
 	}
diff --git a/compiler/reflect.go b/compiler/reflect.go
index f449a297d..cc96b6f14 100644
--- a/compiler/reflect.go
+++ b/compiler/reflect.go
@@ -3,6 +3,8 @@ package compiler
 import (
 	"math/big"
 	"strings"
+
+	"tinygo.org/x/go-llvm"
 )
 
 var basicTypes = map[string]int64{
@@ -41,10 +43,7 @@ func (c *Compiler) assignTypeCodes(typeSlice typeInfoSlice) {
 	fallbackIndex := 1
 	namedTypes := make(map[string]int)
 	for _, t := range typeSlice {
-		if t.name[:5] != "type:" {
-			panic("expected type name to start with 'type:'")
-		}
-		num := c.getTypeCodeNum(t.name[5:], &fallbackIndex, namedTypes)
+		num := c.getTypeCodeNum(t.typecode, &fallbackIndex, namedTypes)
 		if num.BitLen() > c.uintptrType.IntTypeWidth() || !num.IsUint64() {
 			// TODO: support this in some way, using a side table for example.
 			// That's less efficient but better than not working at all.
@@ -59,20 +58,14 @@ func (c *Compiler) assignTypeCodes(typeSlice typeInfoSlice) {
 // getTypeCodeNum returns the typecode for a given type as expected by the
 // reflect package. Also see getTypeCodeName, which serializes types to a string
 // based on a types.Type value for this function.
-func (c *Compiler) getTypeCodeNum(id string, fallbackIndex *int, namedTypes map[string]int) *big.Int {
+func (c *Compiler) getTypeCodeNum(typecode llvm.Value, fallbackIndex *int, namedTypes map[string]int) *big.Int {
 	// Note: see src/reflect/type.go for bit allocations.
-	// A type can be named or unnamed. Example of both:
-	//     basic:~foo:uint64
-	//     basic:uint64
-	// Extract the class (basic, slice, pointer, etc.), the name, and the
-	// contents of this type ID string. Allocate bits based on that, as
-	// src/runtime/types.go expects.
-	class := id[:strings.IndexByte(id, ':')]
-	value := id[len(class)+1:]
+	class, value := getClassAndValueFromTypeCode(typecode)
 	name := ""
-	if value[0] == '~' {
-		name = value[1:strings.IndexByte(value, ':')]
-		value = value[len(name)+2:]
+	if class == "named" {
+		name = value
+		typecode = llvm.ConstExtractValue(typecode.Initializer(), []uint32{0})
+		class, value = getClassAndValueFromTypeCode(typecode)
 	}
 	if class == "basic" {
 		// Basic types follow the following bit pattern:
@@ -81,7 +74,7 @@ func (c *Compiler) getTypeCodeNum(id string, fallbackIndex *int, namedTypes map[
 		// upper bits are used to indicate the named type.
 		num, ok := basicTypes[value]
 		if !ok {
-			panic("invalid basic type: " + id)
+			panic("invalid basic type: " + value)
 		}
 		if name != "" {
 			// This type is named, set the upper bits to the name ID.
@@ -100,17 +93,20 @@ func (c *Compiler) getTypeCodeNum(id string, fallbackIndex *int, namedTypes map[
 		var classNumber int64
 		switch class {
 		case "chan":
-			num = c.getTypeCodeNum(value, fallbackIndex, namedTypes)
+			sub := llvm.ConstExtractValue(typecode.Initializer(), []uint32{0})
+			num = c.getTypeCodeNum(sub, fallbackIndex, namedTypes)
 			classNumber = 0
 		case "interface":
 			num = big.NewInt(int64(*fallbackIndex))
 			*fallbackIndex++
 			classNumber = 1
 		case "pointer":
-			num = c.getTypeCodeNum(value, fallbackIndex, namedTypes)
+			sub := llvm.ConstExtractValue(typecode.Initializer(), []uint32{0})
+			num = c.getTypeCodeNum(sub, fallbackIndex, namedTypes)
 			classNumber = 2
 		case "slice":
-			num = c.getTypeCodeNum(value, fallbackIndex, namedTypes)
+			sub := llvm.ConstExtractValue(typecode.Initializer(), []uint32{0})
+			num = c.getTypeCodeNum(sub, fallbackIndex, namedTypes)
 			classNumber = 3
 		case "array":
 			num = big.NewInt(int64(*fallbackIndex))
@@ -129,7 +125,7 @@ func (c *Compiler) getTypeCodeNum(id string, fallbackIndex *int, namedTypes map[
 			*fallbackIndex++
 			classNumber = 7
 		default:
-			panic("unknown type kind: " + id)
+			panic("unknown type kind: " + class)
 		}
 		if name == "" {
 			num.Lsh(num, 5).Or(num, big.NewInt((classNumber<<1)+1))
@@ -142,6 +138,25 @@ func (c *Compiler) getTypeCodeNum(id string, fallbackIndex *int, namedTypes map[
 	}
 }
 
+// getClassAndValueFromTypeCode takes a typecode (a llvm.Value of type
+// runtime.typecodeID), looks at the name, and extracts the typecode class and
+// value from it. For example, for a typecode with the following name:
+//     reflect/types.type:pointer:named:reflect.ValueError
+// It extracts:
+//     class = "pointer"
+//     value = "named:reflect.ValueError"
+func getClassAndValueFromTypeCode(typecode llvm.Value) (class, value string) {
+	typecodeName := typecode.Name()
+	const prefix = "reflect/types.type:"
+	if !strings.HasPrefix(typecodeName, prefix) {
+		panic("unexpected typecode name: " + typecodeName)
+	}
+	id := typecodeName[len(prefix):]
+	class = id[:strings.IndexByte(id, ':')]
+	value = id[len(class)+1:]
+	return
+}
+
 // getNamedTypeNum returns an appropriate (unique) number for the given named
 // type. If the name already has a number that number is returned, else a new
 // number is returned. The number is always non-zero.
diff --git a/src/runtime/func.go b/src/runtime/func.go
index b05c2a271..96a60048b 100644
--- a/src/runtime/func.go
+++ b/src/runtime/func.go
@@ -16,13 +16,13 @@ type funcValue struct {
 
 // funcValueWithSignature is used before the func lowering pass.
 type funcValueWithSignature struct {
-	funcPtr   uintptr // ptrtoint of the actual function pointer
-	signature *uint8  // pointer to identify this signature (the value is undef)
+	funcPtr   uintptr     // ptrtoint of the actual function pointer
+	signature *typecodeID // pointer to identify this signature (the value is undef)
 }
 
 // getFuncPtr is a dummy function that may be used if the func lowering pass is
 // not used. It is generally too slow but may be a useful fallback to debug the
 // func lowering pass.
-func getFuncPtr(val funcValue, signature *uint8) uintptr {
+func getFuncPtr(val funcValue, signature *typecodeID) uintptr {
 	return (*funcValueWithSignature)(unsafe.Pointer(val.id)).funcPtr
 }
diff --git a/src/runtime/interface.go b/src/runtime/interface.go
index 7f940ae6a..daa9d7813 100644
--- a/src/runtime/interface.go
+++ b/src/runtime/interface.go
@@ -43,7 +43,16 @@ type interfaceMethodInfo struct {
 	funcptr   uintptr // bitcast from the actual function pointer
 }
 
-type typecodeID struct{}
+type typecodeID struct {
+	// Depending on the type kind of this typecodeID, this pointer is something
+	// different:
+	// * basic types: null
+	// * named type: the underlying type
+	// * interface: null
+	// * chan/pointer/slice: the element type
+	// * array/func/map/struct: TODO
+	references *typecodeID
+}
 
 // Pseudo type used before interface lowering. By using a struct instead of a
 // function call, this is simpler to reason about during init interpretation
diff --git a/testdata/interface.go b/testdata/interface.go
index 3c6871d85..69c3b32cf 100644
--- a/testdata/interface.go
+++ b/testdata/interface.go
@@ -22,6 +22,10 @@ func main() {
 	println("Stringer.(*Thing).String():", itf.(Stringer).String())
 
 	println("nested switch:", nestedSwitch('v', 3))
+
+	// Try putting a linked list in an interface:
+	// https://github.com/tinygo-org/tinygo/issues/309
+	itf = linkedList{}
 }
 
 func printItf(val interface{}) {
@@ -134,3 +138,7 @@ func (p SmallPair) Print() {
 type Unmatched interface {
 	NeverImplementedMethod()
 }
+
+type linkedList struct {
+	addr *linkedList
+}