parsing of type strings. still missing: func, struct, interface, chan

R=rsc
DELTA=366  (337 added, 7 deleted, 22 changed)
OCL=17321
CL=17324

3 files changed, 353 insertions, 29 deletions

diff --git a/usr/r/reflect/main.go b/usr/r/reflect/main.go
index 127bcb49b..9e8897ad3 100644
--- a/usr/r/reflect/main.go
+++ b/usr/r/reflect/main.go
@@ -11,23 +11,45 @@ import (
 func main() {
 	var s string;
 
-	s = reflect.ToString(reflect.Int8); print(s, "\n");
-	s = reflect.ToString(reflect.Int16); print(s, "\n");
-	s = reflect.ToString(reflect.Int32); print(s, "\n");
-	s = reflect.ToString(reflect.Int64); print(s, "\n");
-	s = reflect.ToString(reflect.Uint8); print(s, "\n");
-	s = reflect.ToString(reflect.Uint16); print(s, "\n");
-	s = reflect.ToString(reflect.Uint32); print(s, "\n");
-	s = reflect.ToString(reflect.Uint64); print(s, "\n");
-	s = reflect.ToString(reflect.Float32); print(s, "\n");
-	s = reflect.ToString(reflect.Float64); print(s, "\n");
-	s = reflect.ToString(reflect.Float80); print(s, "\n");
-	s = reflect.ToString(reflect.String); print(s, "\n");
-
-	s = reflect.ToString(reflect.PtrInt8); print(s, "\n");
-	s = reflect.ToString(reflect.ArrayFloat32); print(s, "\n");
-	s = reflect.ToString(reflect.MapStringInt16); print(s, "\n");
-	s = reflect.ToString(reflect.ChanArray); print(s, "\n");
-	s = reflect.ToString(reflect.Structure); print(s, "\n");
-	s = reflect.ToString(reflect.Function); print(s, "\n");
+	if false {
+		s = reflect.ToString(reflect.Int8); print(s, "\n");
+		s = reflect.ToString(reflect.Int16); print(s, "\n");
+		s = reflect.ToString(reflect.Int32); print(s, "\n");
+		s = reflect.ToString(reflect.Int64); print(s, "\n");
+		s = reflect.ToString(reflect.Uint8); print(s, "\n");
+		s = reflect.ToString(reflect.Uint16); print(s, "\n");
+		s = reflect.ToString(reflect.Uint32); print(s, "\n");
+		s = reflect.ToString(reflect.Uint64); print(s, "\n");
+		s = reflect.ToString(reflect.Float32); print(s, "\n");
+		s = reflect.ToString(reflect.Float64); print(s, "\n");
+		s = reflect.ToString(reflect.Float80); print(s, "\n");
+		s = reflect.ToString(reflect.String); print(s, "\n");
+
+		s = reflect.ToString(reflect.PtrInt8); print(s, "\n");
+		s = reflect.ToString(reflect.PtrPtrInt8); print(s, "\n");
+		s = reflect.ToString(reflect.ArrayFloat32); print(s, "\n");
+		s = reflect.ToString(reflect.MapStringInt16); print(s, "\n");
+		s = reflect.ToString(reflect.ChanArray); print(s, "\n");
+		s = reflect.ToString(reflect.Structure); print(s, "\n");
+		s = reflect.ToString(reflect.Function); print(s, "\n");
+	}
+	var t reflect.Type;
+
+	t = reflect.ParseTypeString("int8");
+	s = reflect.ToString(t); print(s, "\n");
+
+	t = reflect.ParseTypeString("**int8");
+	s = reflect.ToString(t); print(s, "\n");
+
+	t = reflect.ParseTypeString("**P.integer");
+	s = reflect.ToString(t); print(s, "\n");
+
+	t = reflect.ParseTypeString("[32]int32");
+	s = reflect.ToString(t); print(s, "\n");
+
+	t = reflect.ParseTypeString("[]int8");
+	s = reflect.ToString(t); print(s, "\n");
+
+	t = reflect.ParseTypeString("map[string]int32");
+	s = reflect.ToString(t); print(s, "\n");
 }
diff --git a/usr/r/reflect/tostring.go b/usr/r/reflect/tostring.go
index b3cd8568e..60fb9f6f8 100644
--- a/usr/r/reflect/tostring.go
+++ b/usr/r/reflect/tostring.go
@@ -2,6 +2,9 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
+// Reflection library.
+// Formatting of types for debugging.
+
 package reflect
 
 import (
@@ -28,6 +31,8 @@ func FieldsToString(t Type) string {
 func ToString(typ Type) string {
 	var str string;
 	switch(typ.Kind()) {
+	case MissingKind:
+		return "missing";
 	case Int8Kind:
 		return "int8";
 	case Int16Kind:
diff --git a/usr/r/reflect/type.go b/usr/r/reflect/type.go
index 6d3f1440c..abec5c11e 100644
--- a/usr/r/reflect/type.go
+++ b/usr/r/reflect/type.go
@@ -2,22 +2,20 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
+// Reflection library.
+// Types and parsing of type strings.
+
 package reflect
 
 export type Type interface
-export type Value interface{}	// TODO: define this
 
-export func LookupTypeName(name string) Type
+export func ExpandType(name string) Type
 
 //export var GlobalTypeStrings = sys.typestrings;
 
-// Cache of types keyed by type name
-var types = new(map[string] *Type)	// BUG TODO: should be Type not *Type
-// Cache of type strings keyed by type name
-var strings = new(map[string] string)
-
 export const (
-	ArrayKind = iota;
+	MissingKind = iota;
+	ArrayKind;
 	ChanKind;
 	Float32Kind;
 	Float64Kind;
@@ -37,6 +35,8 @@ export const (
 	Uint8Kind;
 )
 
+var MissingString = "missing"	// syntactic name for undefined type names
+
 type Type interface {
 	Kind()	int;
 }
@@ -57,6 +57,7 @@ func NewBasicType(k int) Type {
 
 // Basic types
 export var (
+	Missing = NewBasicType(MissingKind);
 	Int8 = NewBasicType(Int8Kind);
 	Int16 = NewBasicType(Int16Kind);
 	Int32 = NewBasicType(Int32Kind);
@@ -71,6 +72,8 @@ export var (
 	String = NewBasicType(StringKind);
 )
 
+// Stub types allow us to defer evaluating type names until needed.
+// If the name is empty, the type must be non-nil.
 type StubType struct {
 	name	string;
 	typ		Type;
@@ -78,11 +81,23 @@ type StubType struct {
 
 func (t *StubType) Get() Type {
 	if t.typ == nil {
-		t.typ = LookupTypeName(t.name)
+		t.typ = ExpandType(t.name)
 	}
 	return t.typ
 }
 
+func NewStubType(t Type) *StubType {
+	s := new(StubType);
+	s.typ = t;
+	return s;
+}
+
+func NewNamedStubType(n string) *StubType {
+	s := new(StubType);
+	s.name = n;
+	return s;
+}
+
 export type PtrType interface {
 	Sub()	Type
 }
@@ -274,8 +289,8 @@ func NewFuncTypeStruct(receiver, in, out *StructTypeStruct) *FuncTypeStruct {
 	return t;
 }
 
+////////////////////////
 //helpers for early bootstrap and debugging
-export func LookupTypeName(name string) Type { return Int8 }
 func Stub(n string, t Type) *StubType {
 	s := new(StubType);
 	s.name = n;
@@ -283,6 +298,7 @@ func Stub(n string, t Type) *StubType {
 	return s;
 }
 export var PtrInt8 Type = NewPtrTypeStruct(Stub("i", Int8));
+export var PtrPtrInt8 Type = NewPtrTypeStruct(Stub("i", PtrInt8));
 export var ArrayFloat32 Type = NewArrayTypeStruct(100, Stub("f", Float32));
 export var MapStringInt16 Type = NewMapTypeStruct(Stub("s", String), Stub("i", Int16));
 export var ChanArray Type = NewChanTypeStruct(RecvDir, Stub("a", ArrayFloat32));
@@ -290,3 +306,284 @@ var F1 = Field{"i", Stub("i", Int64)};
 var Fields = []Field{F1};
 export var Structure = NewStructTypeStruct(&Fields);
 export var Function Type = NewFuncTypeStruct(Structure, Structure, Structure);
+////////////////////////
+
+// Cache of expanded types keyed by type name.
+var types *map[string] *Type	// BUG TODO: should be Type not *Type
+// List of typename, typestring pairs
+var typestrings *map[string] string
+// Map of basic types to prebuilt StubTypes
+var basicstubs *map[string] *StubType
+
+var MissingStub *StubType;
+
+func init() {
+	types = new(map[string] *Type);
+	typestrings = new(map[string] string);
+	basicstubs = new(map[string] *StubType);
+
+	// Basics go into types table
+	types["missing"] = &Missing;
+	types["int8"] = &Int8;
+	types["int16"] = &Int16;
+	types["int32"] = &Int32;
+	types["int64"] = &Int64;
+	types["uint8"] = &Uint8;
+	types["uint16"] = &Uint16;
+	types["uint32"] = &Uint32;
+	types["uint64"] = &Uint64;
+	types["float32"] = &Float32;
+	types["float64"] = &Float64;
+	types["float80"] = &Float80;
+	types["string"] = &String;
+
+	// Basics get prebuilt stubs
+	MissingStub = NewStubType(Missing);
+	basicstubs["missing"] = MissingStub;
+	basicstubs["int8"] = NewStubType(Int8);
+	basicstubs["int16"] = NewStubType(Int16);
+	basicstubs["int32"] = NewStubType(Int32);
+	basicstubs["int64"] = NewStubType(Int64);
+	basicstubs["uint8"] = NewStubType(Uint8);
+	basicstubs["uint16"] = NewStubType(Uint16);
+	basicstubs["uint32"] = NewStubType(Uint32);
+	basicstubs["uint64"] = NewStubType(Uint64);
+	basicstubs["float32"] = NewStubType(Float32);
+	basicstubs["float64"] = NewStubType(Float64);
+	basicstubs["float80"] = NewStubType(Float80);
+	basicstubs["string"] = NewStubType(String);
+
+	typestrings["P.integer"] = "int32";
+	return;
+	typestrings["P.S"] =  "struct {t *P.T}";
+	typestrings["P.T"] = "struct {c *(? *chan P.S, *int)}";
+}
+
+/*
+	Grammar
+
+	stubtype =	- represent as StubType when possible
+		type
+	identifier =
+		name
+		'?'
+	type =
+		basictypename	- int8, string, etc.
+		typename
+		arraytype
+		structtype
+		interfacetype
+		chantype
+		maptype
+		pointertype
+		functiontype
+	typename =
+		name '.' name
+	fieldlist =
+		[ field { ',' field } ]
+	field =
+		identifier stubtype
+	arraytype =
+		'[' [ number ] ']' stubtype
+	structtype =
+		'struct' '{' fieldlist '}'
+	interfacetype =
+		'interface' '{' fieldlist '}'
+	chantype =
+		'<-' chan stubtype
+		chan '<-' stubtype
+		chan stubtype
+	maptype =
+		'map' '[' stubtype ']' stubtype
+	pointertype =
+		'*' stubtype
+	functiontype =
+		'(' fieldlist ')'
+
+*/
+
+func isdigit(c uint8) bool {
+	return '0' <= c && c <= '9'
+}
+
+func special(c uint8) bool {
+	s := "*[](){}<";	// Note: '.' is not in this list.  "P.T" is an identifer, as is "?".
+	for i := 0; i < len(s); i++ {
+		if c == s[i] {
+			return true
+		}
+	}
+	return false;
+}
+
+type Parser struct {
+	str	string;
+	index	int;
+	token	string;
+}
+
+func (p *Parser) Next() {
+	token := "";
+	for ; p.index < len(p.str) && p.str[p.index] == ' '; p.index++ {
+	}
+	if p.index >= len(p.str) {
+		p.token = "";
+		return;
+	}
+	start := p.index;
+	c, w := sys.stringtorune(p.str, p.index);
+	p.index += w;
+	switch {
+	case c == '*':
+		p.token = "*";
+		return;
+	case c == '[':
+		p.token = "[";
+		return;
+	case c == ']':
+		p.token = "]";
+		return;
+	case c == '(':
+		p.token = "(";
+		return;
+	case c == ')':
+		p.token = ")";
+		return;
+	case c == '<':
+		if p.index < len(p.str) && p.str[p.index+1] == '-' {
+			p.index++;
+			p.token = "<-";
+			return;
+		}
+		p.token = "<";	// shouldn't happen but let the parser figure it out
+		return;
+	case isdigit(uint8(c)):
+		for p.index < len(p.str) && isdigit(p.str[p.index]) {
+			p.index++
+		}
+		p.token = p.str[start : p.index];
+		return;
+	}
+	for p.index < len(p.str) && !special(p.str[p.index]) {
+		p.index++
+	}
+	p.token = p.str[start : p.index];
+}
+
+func (p *Parser) Type() *StubType
+
+func (p *Parser) Array() *StubType {
+	size := -1;
+	if p.token != "]" {
+		if len(p.token) == 0 || !isdigit(p.token[0]) {
+			return MissingStub
+		}
+		// write our own (trivial and simpleminded) atoi to avoid dependency
+		size = 0;
+		for i := 0; i < len(p.token); i++ {
+			size = size * 10 + int(p.token[i]) - '0'
+		}
+		p.Next();
+	}
+	if p.token != "]" {
+		return MissingStub
+	}
+	p.Next();
+	elemtype := p.Type();
+	return NewStubType(NewArrayTypeStruct(size, elemtype));
+}
+
+func (p *Parser) Map() *StubType {
+	if p.token != "[" {
+		return MissingStub
+	}
+	p.Next();
+	keytype := p.Type();
+	if p.token != "]" {
+		return MissingStub
+	}
+	p.Next();
+	elemtype := p.Type();
+	return NewStubType(NewMapTypeStruct(keytype, elemtype));
+}
+
+func (p *Parser) Simple() *StubType {
+	switch {
+	case p.token == "":
+		return nil;
+	case p.token == "*":
+		p.Next();
+		return NewStubType(NewPtrTypeStruct(p.Simple()));
+	case p.token == "[":
+		p.Next();
+		return p.Array();
+	case p.token == "map":
+		p.Next();
+		return p.Map();
+	case isdigit(p.token[0]):
+		p.Next();
+		print("reflect.Simple: number encountered\n");	// TODO: remove
+		return MissingStub;
+	case special(p.token[0]):
+		// TODO: get chans right
+		p.Next();
+		print("reflect.Simple: special character encountered\n");	// TODO: remove
+		return MissingStub;
+	}
+	// must be an identifier. is it basic? if so, we have a stub
+	if s, ok := basicstubs[p.token]; ok {
+		p.Next();
+		return s
+	}
+	// not a basic - must be of the form "P.T"
+	ndot := 0;
+	for i := 0; i < len(p.token); i++ {
+		if p.token[i] == '.' {
+			ndot++
+		}
+	}
+	if ndot != 1 {
+		print("reflect.Simple: illegal identifier ", p.token, "\n");	// TODO: remove
+		p.Next();
+		return MissingStub;
+	}
+	s := new(StubType);
+	s.name = p.token;
+	p.Next();
+	return s;
+}
+
+func (p *Parser) Type() *StubType {
+	return p.Simple();
+}
+
+export func ParseTypeString(str string) Type {
+	p := new(Parser);
+	p.str = str;
+	p.Next();
+	return p.Type().Get();
+}
+
+// Look up type string associated with name.
+func TypeNameToTypeString(name string) string {
+	s, ok := typestrings[name];
+	if !ok {
+		s = MissingString;
+		typestrings[name] = s;
+	}
+	return s
+}
+
+// Type is known by name.  Find (and create if necessary) its real type.
+func ExpandType(name string) Type {
+	t, ok := types[name];
+	if ok {
+		return *t
+	}
+	types[name] = &Missing;	// prevent recursion; will overwrite
+	t1 := ParseTypeString(TypeNameToTypeString(name));
+	p := new(Type);
+	*p = t1;
+	types[name] = p;
+	return t1;
+}