reflect: support slices and indexing of strings and slices

6 files changed, 279 insertions, 52 deletions

diff --git a/compiler/interface.go b/compiler/interface.go
index 1f90b84ae..a849a00ef 100644
--- a/compiler/interface.go
+++ b/compiler/interface.go
@@ -79,11 +79,23 @@ func (c *Compiler) parseMakeInterface(val llvm.Value, typ types.Type, global str
 // 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 {
-	var globalName string
-	switch typ := typ.(type) {
+	globalName := "type:" + getTypeCodeName(typ)
+	global := c.mod.NamedGlobal(globalName)
+	if global.IsNil() {
+		global = llvm.AddGlobal(c.mod, c.ctx.Int8Type(), globalName)
+		global.SetGlobalConstant(true)
+	}
+	return global
+}
+
+// getTypeCodeName returns a name for this type that can be used in the
+// interface lowering pass to assign type codes as expected by the reflect
+// package. See getTypeCodeNum.
+func getTypeCodeName(t types.Type) string {
+	switch t := t.(type) {
 	case *types.Basic:
 		var name string
-		switch typ.Kind() {
+		switch t.Kind() {
 		case types.Bool:
 			name = "bool"
 		case types.Int:
@@ -121,19 +133,15 @@ func (c *Compiler) getTypeCode(typ types.Type) llvm.Value {
 		case types.UnsafePointer:
 			name = "unsafeptr"
 		default:
-			panic("unknown basic type: " + typ.Name())
+			panic("unknown basic type: " + t.Name())
 		}
-		globalName = "type:basic:" + name
+		return "basic:" + name
+	case *types.Slice:
+		return "slice:" + getTypeCodeName(t.Elem())
 	default:
 		// Unknown type, fall back to the .String() method for identification.
-		globalName = "type:other:" + typ.String()
+		return "other:" + t.String()
 	}
-	global := c.mod.NamedGlobal(globalName)
-	if global.IsNil() {
-		global = llvm.AddGlobal(c.mod, c.ctx.Int8Type(), globalName)
-		global.SetGlobalConstant(true)
-	}
-	return global
 }
 
 // getTypeMethodSet returns a reference (GEP) to a global method set. This
diff --git a/compiler/reflect.go b/compiler/reflect.go
index 80ccd795b..cd1ad9ce3 100644
--- a/compiler/reflect.go
+++ b/compiler/reflect.go
@@ -1,10 +1,11 @@
 package compiler
 
 import (
+	"math/big"
 	"strings"
 )
 
-var basicTypes = map[string]uint64{
+var basicTypes = map[string]int64{
 	"bool":       1,
 	"int":        2,
 	"int8":       3,
@@ -39,17 +40,45 @@ func (c *Compiler) assignTypeCodes(typeSlice typeInfoSlice) {
 	// Assign typecodes the way the reflect package expects.
 	fallbackIndex := 1
 	for _, t := range typeSlice {
-		if strings.HasPrefix(t.name, "type:basic:") {
-			// Basic types have a typecode with the lowest bit set to 0.
-			num, ok := basicTypes[t.name[len("type:basic:"):]]
-			if !ok {
-				panic("invalid basic type: " + t.name)
-			}
-			t.num = num<<1 | 0
-		} else {
-			// Fallback types have a typecode with the lowest bit set to 1.
-			t.num = uint64(fallbackIndex<<1 | 1)
+		if t.name[:5] != "type:" {
+			panic("expected type name to start with 'type:'")
+		}
+		num := c.getTypeCodeNum(t.name[5:])
+		if num == nil {
+			// Fallback/unsupported types have a typecode with the lowest bits
+			// set to 11.
+			t.num = uint64(fallbackIndex<<2 | 3)
 			fallbackIndex++
+			continue
+		}
+		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.
+			// Particularly important on systems with 16-bit pointers (e.g.
+			// AVR).
+			panic("compiler: could not store type code number inside interface type code")
+		}
+		t.num = num.Uint64()
+	}
+}
+
+// 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(name string) *big.Int {
+	if strings.HasPrefix(name, "basic:") {
+		// Basic types have a typecode with the lowest bits set to 00.
+		num, ok := basicTypes[name[len("basic:"):]]
+		if !ok {
+			panic("invalid basic type: " + name)
 		}
+		return big.NewInt(num<<2 | 0)
+	} else if strings.HasPrefix(name, "slice:") {
+		// Slices have a typecode with the lowest bits set to 01.
+		num := c.getTypeCodeNum(name[len("slice:"):])
+		num.Lsh(num, 2).Or(num, big.NewInt(1))
+		return num
+	} else {
+		return nil
 	}
 }
diff --git a/src/reflect/type.go b/src/reflect/type.go
index a0fe132d0..fc27a4462 100644
--- a/src/reflect/type.go
+++ b/src/reflect/type.go
@@ -1,5 +1,9 @@
 package reflect
 
+import (
+	"unsafe"
+)
+
 // A Kind is the number that the compiler uses for this type.
 //
 // Not used directly. These types are all replaced with the number the compiler
@@ -76,11 +80,18 @@ func (k Kind) String() string {
 		return "string"
 	case UnsafePointer:
 		return "unsafe.Pointer"
+	case Slice:
+		return "slice"
 	default:
-		return "T"
+		return "invalid"
 	}
 }
 
+// basicType returns a new Type for this kind if Kind is a basic type.
+func (k Kind) basicType() Type {
+	return Type(k << 2 | 0)
+}
+
 // The typecode as used in an interface{}.
 type Type uintptr
 
@@ -93,16 +104,24 @@ func (t Type) String() string {
 }
 
 func (t Type) Kind() Kind {
-	if t & 1 == 0 {
+	if t % 4 == 0 {
 		// Basic type
-		return Kind(t >> 1)
+		return Kind(t >> 2)
+	} else if t % 4 == 1 {
+		// Slice
+		return Slice
 	} else {
 		return Invalid // TODO
 	}
 }
 
 func (t Type) Elem() Type {
-	panic("unimplemented: (reflect.Type).Elem()")
+	switch t.Kind() {
+	case Slice:
+		return t >> 2
+	default: // not implemented: Array, Chan, Map, Ptr
+		panic("unimplemented: (reflect.Type).Elem()")
+	}
 }
 
 func (t Type) Field(i int) StructField {
@@ -122,7 +141,37 @@ func (t Type) NumField() int {
 }
 
 func (t Type) Size() uintptr {
-	panic("unimplemented: (reflect.Type).Size()")
+	switch t.Kind() {
+	case Bool, Int8, Uint8:
+		return 1
+	case Int16, Uint16:
+		return 2
+	case Int32, Uint32:
+		return 4
+	case Int64, Uint64:
+		return 8
+	case Int, Uint:
+		return unsafe.Sizeof(int(0))
+	case Uintptr:
+		return unsafe.Sizeof(uintptr(0))
+	case Float32:
+		return 4
+	case Float64:
+		return 8
+	case Complex64:
+		return 8
+	case Complex128:
+		return 16
+	case String:
+		return unsafe.Sizeof(StringHeader{})
+	case UnsafePointer:
+		return unsafe.Sizeof(uintptr(0))
+	case Slice:
+		return unsafe.Sizeof(SliceHeader{})
+	default:
+		// Size unknown.
+		return 0
+	}
 }
 
 type StructField struct {
diff --git a/src/reflect/value.go b/src/reflect/value.go
index 5747ca70c..d45f0b5c5 100644
--- a/src/reflect/value.go
+++ b/src/reflect/value.go
@@ -18,14 +18,16 @@ func ValueOf(i interface{}) Value {
 	return *(*Value)(unsafe.Pointer(&i))
 }
 
-func (v Value) Interface() interface{}
+func (v Value) Interface() interface{} {
+	return *(*interface{})(unsafe.Pointer(&v))
+}
 
 func (v Value) Type() Type {
 	return v.typecode
 }
 
 func (v Value) Kind() Kind {
-	return Invalid // TODO
+	return v.Type().Kind()
 }
 
 func (v Value) IsNil() bool {
@@ -33,7 +35,7 @@ func (v Value) IsNil() bool {
 }
 
 func (v Value) Pointer() uintptr {
-	switch v.Type().Kind() {
+	switch v.Kind() {
 	case UnsafePointer:
 		return uintptr(v.value)
 	case Chan, Func, Map, Ptr, Slice:
@@ -48,7 +50,8 @@ func (v Value) IsValid() bool {
 }
 
 func (v Value) CanInterface() bool {
-	panic("unimplemented: (reflect.Value).CanInterface()")
+	// No Value types of private data can be constructed at the moment.
+	return true
 }
 
 func (v Value) CanAddr() bool {
@@ -64,7 +67,7 @@ func (v Value) CanSet() bool {
 }
 
 func (v Value) Bool() bool {
-	switch v.Type().Kind() {
+	switch v.Kind() {
 	case Bool:
 		return uintptr(v.value) != 0
 	default:
@@ -73,7 +76,7 @@ func (v Value) Bool() bool {
 }
 
 func (v Value) Int() int64 {
-	switch v.Type().Kind() {
+	switch v.Kind() {
 	case Int:
 		if unsafe.Sizeof(int(0)) <= unsafe.Sizeof(uintptr(0)) {
 			return int64(int(uintptr(v.value)))
@@ -103,7 +106,7 @@ func (v Value) Int() int64 {
 }
 
 func (v Value) Uint() uint64 {
-	switch v.Type().Kind() {
+	switch v.Kind() {
 	case Uintptr, Uint8, Uint16:
 		return uint64(uintptr(v.value))
 	case Uint:
@@ -133,7 +136,7 @@ func (v Value) Uint() uint64 {
 }
 
 func (v Value) Float() float64 {
-	switch v.Type().Kind() {
+	switch v.Kind() {
 	case Float32:
 		if unsafe.Sizeof(float32(0)) <= unsafe.Sizeof(uintptr(0)) {
 			// The float is directly stored in the interface value on systems
@@ -159,7 +162,7 @@ func (v Value) Float() float64 {
 }
 
 func (v Value) Complex() complex128 {
-	switch v.Type().Kind() {
+	switch v.Kind() {
 	case Complex64:
 		if unsafe.Sizeof(complex64(0)) <= unsafe.Sizeof(uintptr(0)) {
 			// The complex number is directly stored in the interface value on
@@ -181,7 +184,7 @@ func (v Value) Complex() complex128 {
 }
 
 func (v Value) String() string {
-	switch v.Type().Kind() {
+	switch v.Kind() {
 	case String:
 		// A string value is always bigger than a pointer as it is made of a
 		// pointer and a length.
@@ -201,7 +204,25 @@ func (v Value) Slice(i, j int) Value {
 }
 
 func (v Value) Len() int {
-	panic("unimplemented: (reflect.Value).Len()")
+	t := v.Type()
+	switch t.Kind() {
+	case Slice:
+		return int((*SliceHeader)(v.value).Len)
+	case String:
+		return int((*StringHeader)(v.value).Len)
+	default: // Array, Chan, Map
+		panic("unimplemented: (reflect.Value).Len()")
+	}
+}
+
+func (v Value) Cap() int {
+	t := v.Type()
+	switch t.Kind() {
+	case Slice:
+		return int((*SliceHeader)(v.value).Cap)
+	default: // Array, Chan
+		panic("unimplemented: (reflect.Value).Cap()")
+	}
 }
 
 func (v Value) NumField() int {
@@ -217,7 +238,48 @@ func (v Value) Field(i int) Value {
 }
 
 func (v Value) Index(i int) Value {
-	panic("unimplemented: (reflect.Value).Index()")
+	switch v.Kind() {
+	case Slice:
+		// Extract an element from the slice.
+		slice := *(*SliceHeader)(v.value)
+		if uint(i) >= uint(slice.Len) {
+			panic("reflect: slice index out of range")
+		}
+		elem := Value{
+			typecode: v.Type().Elem(),
+		}
+		addr := uintptr(slice.Data) + elem.Type().Size() * uintptr(i) // pointer to new value
+		if elem.Type().Size() <= unsafe.Sizeof(uintptr(0)) {
+			// Value fits inside interface value.
+			// Make sure to copy it from the slice to the interface value.
+			var value uintptr
+			for j := elem.Type().Size(); j != 0; j-- {
+				value = (value << 8) | uintptr(*(*uint8)(unsafe.Pointer(addr + j - 1)))
+			}
+			elem.value = unsafe.Pointer(value)
+		} else {
+			// Value doesn't fit in the interface.
+			// Store a pointer to the element in the interface.
+			elem.value = unsafe.Pointer(addr)
+		}
+		return elem
+	case String:
+		// Extract a character from a string.
+		// A string is never stored directly in the interface, but always as a
+		// pointer to the string value.
+		s := *(*StringHeader)(v.value)
+		if uint(i) >= uint(s.Len) {
+			panic("reflect: string index out of range")
+		}
+		return Value{
+			typecode: Uint8.basicType(),
+			value: unsafe.Pointer(uintptr(*(*uint8)(unsafe.Pointer(s.Data + uintptr(i))))),
+		}
+	case Array:
+		panic("unimplemented: (reflect.Value).Index()")
+	default:
+		panic(&ValueError{"Index"})
+	}
 }
 
 func (v Value) MapKeys() []Value {
@@ -260,6 +322,17 @@ func MakeSlice(typ Type, len, cap int) Value {
 	panic("unimplemented: reflect.MakeSlice()")
 }
 
+type SliceHeader struct {
+	Data uintptr
+	Len  uintptr
+	Cap  uintptr
+}
+
+type StringHeader struct {
+	Data uintptr
+	Len  uintptr
+}
+
 type ValueError struct {
 	Method string
 }
diff --git a/testdata/reflect.go b/testdata/reflect.go
index 2d191e2d7..d6c18f2ff 100644
--- a/testdata/reflect.go
+++ b/testdata/reflect.go
@@ -39,34 +39,53 @@ func main() {
 		complex128(1.3 + 0.4i),
 		"foo",
 		unsafe.Pointer(new(int)),
+		[]byte{1, 2, 3},
+		make([]uint8, 2, 5),
+		[]rune{3, 5},
+		[]string{"xyz", "Z"},
 	} {
-		showValue(v)
+		showValue(v, "")
 	}
 }
 
-func showValue(v interface{}) {
+func showValue(v interface{}, indent string) {
 	rv := reflect.ValueOf(v)
 	rt := rv.Type()
 	if reflect.TypeOf(v) != rt {
 		panic("direct TypeOf() is different from ValueOf().Type()")
 	}
-	println("reflect type:", rt.Kind().String())
+	if rt.Kind() != rv.Kind() {
+		panic("type kind is different from value kind")
+	}
+	if reflect.ValueOf(rv.Interface()) != rv {
+		panic("reflect.ValueOf(Value.Interface()) did not return the same value")
+	}
+	println(indent+"reflect type:", rt.Kind().String())
 	switch rt.Kind() {
 	case reflect.Bool:
-		println("  bool:", rv.Bool())
+		println(indent+"  bool:", rv.Bool())
 	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
-		println("  int:", rv.Int())
+		println(indent+"  int:", rv.Int())
 	case reflect.Uint, reflect.Uintptr, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64:
-		println("  uint:", rv.Uint())
+		println(indent+"  uint:", rv.Uint())
 	case reflect.Float32, reflect.Float64:
-		println("  float:", rv.Float())
+		println(indent+"  float:", rv.Float())
 	case reflect.Complex64, reflect.Complex128:
-		println("  complex:", rv.Complex())
+		println(indent+"  complex:", rv.Complex())
 	case reflect.String:
-		println("  string:", rv.String())
+		println(indent+"  string:", rv.String(), rv.Len())
+		for i := 0; i < rv.Len(); i++ {
+			showValue(rv.Index(i).Interface(), indent+"  ")
+		}
 	case reflect.UnsafePointer:
-		println("  pointer:", rv.Pointer() != 0)
+		println(indent+"  pointer:", rv.Pointer() != 0)
+	case reflect.Slice:
+		println(indent+"  slice:", rt.Elem().Kind().String(), rv.Len(), rv.Cap())
+		for i := 0; i < rv.Len(); i++ {
+			println(indent+"  indexing:", i)
+			showValue(rv.Index(i).Interface(), indent+"  ")
+		}
 	default:
-		println("  unknown type kind!")
+		println(indent + "  unknown type kind!")
 	}
 }
diff --git a/testdata/reflect.txt b/testdata/reflect.txt
index 8926e9b48..2badc1393 100644
--- a/testdata/reflect.txt
+++ b/testdata/reflect.txt
@@ -49,6 +49,55 @@ reflect type: complex64
 reflect type: complex128
   complex: (+1.300000e+000+4.000000e-001i)
 reflect type: string
-  string: foo
+  string: foo 3
+  reflect type: uint8
+    uint: 102
+  reflect type: uint8
+    uint: 111
+  reflect type: uint8
+    uint: 111
 reflect type: unsafe.Pointer
   pointer: true
+reflect type: slice
+  slice: uint8 3 3
+  indexing: 0
+  reflect type: uint8
+    uint: 1
+  indexing: 1
+  reflect type: uint8
+    uint: 2
+  indexing: 2
+  reflect type: uint8
+    uint: 3
+reflect type: slice
+  slice: uint8 2 5
+  indexing: 0
+  reflect type: uint8
+    uint: 0
+  indexing: 1
+  reflect type: uint8
+    uint: 0
+reflect type: slice
+  slice: int32 2 2
+  indexing: 0
+  reflect type: int32
+    int: 3
+  indexing: 1
+  reflect type: int32
+    int: 5
+reflect type: slice
+  slice: string 2 2
+  indexing: 0
+  reflect type: string
+    string: xyz 3
+    reflect type: uint8
+      uint: 120
+    reflect type: uint8
+      uint: 121
+    reflect type: uint8
+      uint: 122
+  indexing: 1
+  reflect type: string
+    string: Z 1
+    reflect type: uint8
+      uint: 90