From b86359073e8268093dbff1c5d5a8ed600218c816 Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Tue, 16 Dec 2008 18:02:22 -0800 Subject: [PATCH] Snapshot. Preparations to track identifiers and declarations so that we can generate good html links as pretty printer output: - brought over old code and adjusted it - initial hookups, nothing really running yet R=r OCL=21383 CL=21383 --- usr/gri/pretty/Makefile | 12 +- usr/gri/pretty/compilation.go | 6 + usr/gri/pretty/globals.go | 240 ++++++++++++++++++++++++++++++++++ usr/gri/pretty/object.go | 36 +++++ usr/gri/pretty/type.go | 207 +++++++++++++++++++++++++++++ usr/gri/pretty/universe.go | 125 ++++++++++++++++++ 6 files changed, 624 insertions(+), 2 deletions(-) create mode 100644 usr/gri/pretty/globals.go create mode 100755 usr/gri/pretty/object.go create mode 100644 usr/gri/pretty/type.go create mode 100755 usr/gri/pretty/universe.go diff --git a/usr/gri/pretty/Makefile b/usr/gri/pretty/Makefile index 50585fe102..cfc2bb132c 100644 --- a/usr/gri/pretty/Makefile +++ b/usr/gri/pretty/Makefile @@ -23,11 +23,11 @@ install: pretty cp pretty $(HOME)/bin/pretty clean: - rm -f pretty *.6 *~ + rm -f pretty *.6 *.a *~ pretty.6: platform.6 printer.6 compilation.6 -compilation.6: platform.6 scanner.6 parser.6 ast.6 +compilation.6: platform.6 scanner.6 parser.6 ast.6 typechecker.6 ast.6: scanner.6 @@ -39,5 +39,13 @@ platform.6: utils.6 printer.6: scanner.6 ast.6 +typechecker.6: ast.6 universe.6 globals.6 type.6 + +universe.6: globals.6 object.6 type.6 + +object.6: globals.6 + +type.6: globals.6 object.6 + %.6: %.go $(G) $(F) $< diff --git a/usr/gri/pretty/compilation.go b/usr/gri/pretty/compilation.go index 9df221436a..82b6618da3 100644 --- a/usr/gri/pretty/compilation.go +++ b/usr/gri/pretty/compilation.go @@ -10,6 +10,7 @@ import Platform "platform" import Scanner "scanner" import Parser "parser" import AST "ast" +import TypeChecker "typechecker" func assert(b bool) { @@ -133,6 +134,11 @@ export func Compile(src_file string, flags *Flags) (*AST.Program, int) { parser.Open(flags.verbose, flags.sixg, flags.deps, &scanner, tstream); prog := parser.ParseProgram(); + + if err.nerrors == 0 { + TypeChecker.CheckProgram(prog); + } + return prog, err.nerrors; } diff --git a/usr/gri/pretty/globals.go b/usr/gri/pretty/globals.go new file mode 100644 index 0000000000..d1dc47cb0b --- /dev/null +++ b/usr/gri/pretty/globals.go @@ -0,0 +1,240 @@ +// 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 Globals + + +// The following types should really be in their respective files +// (object.go, type.go, scope.go, package.go, compilation.go, etc.) but +// they refer to each other and we don't know how to handle forward +// declared pointers across packages yet. + + +// ---------------------------------------------------------------------------- + +type Type struct +type Scope struct +type Elem struct +type OldCompilation struct + +// Object represents a language object, such as a constant, variable, type, +// etc. (kind). An objects is (pre-)declared at a particular position in the +// source code (pos), has a name (ident), a type (typ), and a package number +// or nesting level (pnolev). + +export type Object struct { + exported bool; + pos int; // source position (< 0 if unknown position) + kind int; + ident string; + typ *Type; // nil for packages + pnolev int; // >= 0: package no., <= 0: function nesting level, 0: global level +} + + +export type Type struct { + ref int; // for exporting only: >= 0 means already exported + form int; + size int; // in bytes + len int; // array length, no. of function/method parameters (w/o recv) + aux int; // channel info + obj *Object; // primary type object or NULL + key *Type; // alias base type or map key + elt *Type; // aliased type, array, map, channel or pointer element type, function result type, tuple function type + scope *Scope; // forwards, structs, interfaces, functions +} + + +export type Package struct { + ref int; // for exporting only: >= 0 means already exported + file_name string; + key string; + obj *Object; + scope *Scope; // holds the (global) objects in this package +} + + +export type Scope struct { + parent *Scope; + entries *map[string] *Object; +} + + +export type Environment struct { + Error *(comp *OldCompilation, pos int, msg string); + Import *(comp *OldCompilation, pkg_file string) *Package; + Export *(comp *OldCompilation, pkg_file string); + Compile *(comp *OldCompilation, src_file string); +} + + +export type OldCompilation struct { + // environment + env *Environment; + + // TODO rethink the need for this here + src_file string; + src string; + + // Error handling + nerrors int; // number of errors reported + errpos int; // last error position + + // TODO use open arrays eventually + pkg_list [256] *Package; // pkg_list[0] is the current package + pkg_ref int; +} + + +export type Expr interface { + op() int; // node operation + pos() int; // source position + typ() *Type; + // ... more to come here +} + + +export type Stat interface { + // ... more to come here +} + + +// TODO This is hideous! We need to have a decent way to do lists. +// Ideally open arrays that allow '+'. + +export type Elem struct { + next *Elem; + val int; + str string; + obj *Object; + typ *Type; + expr Expr +} + + +// ---------------------------------------------------------------------------- +// Creation + +export var Universe_void_typ *Type // initialized by Universe to Universe.void_typ + +export func NewObject(pos, kind int, ident string) *Object { + obj := new(Object); + obj.exported = false; + obj.pos = pos; + obj.kind = kind; + obj.ident = ident; + obj.typ = Universe_void_typ; + obj.pnolev = 0; + return obj; +} + + +export func NewType(form int) *Type { + typ := new(Type); + typ.ref = -1; // not yet exported + typ.form = form; + return typ; +} + + +export func NewPackage(file_name string, obj *Object, scope *Scope) *Package { + pkg := new(Package); + pkg.ref = -1; // not yet exported + pkg.file_name = file_name; + pkg.key = ""; // empty key means package forward declaration + pkg.obj = obj; + pkg.scope = scope; + return pkg; +} + + +export func NewScope(parent *Scope) *Scope { + scope := new(Scope); + scope.parent = parent; + scope.entries = new(map[string]*Object, 8); + return scope; +} + + +// ---------------------------------------------------------------------------- +// Object methods + +func (obj *Object) Copy() *Object { + copy := new(Object); + copy.exported = obj.exported; + copy.pos = obj.pos; + copy.kind = obj.kind; + copy.ident = obj.ident; + copy.typ = obj.typ; + copy.pnolev = obj.pnolev; + return copy; +} + + +// ---------------------------------------------------------------------------- +// Scope methods + +func (scope *Scope) Lookup(ident string) *Object { + obj, found := scope.entries[ident]; + if found { + return obj; + } + return nil; +} + + +func (scope *Scope) Add(obj* Object) { + scope.entries[obj.ident] = obj; +} + + +func (scope *Scope) Insert(obj *Object) { + if scope.Lookup(obj.ident) != nil { + panic("obj already inserted"); + } + scope.Add(obj); +} + + +func (scope *Scope) InsertImport(obj *Object) *Object { + p := scope.Lookup(obj.ident); + if p == nil { + scope.Add(obj); + p = obj; + } + return p; +} + + +func (scope *Scope) Print() { + print("scope {"); + for key := range scope.entries { + print("\n ", key); + } + print("\n}\n"); +} + + +// ---------------------------------------------------------------------------- +// Compilation methods + +func (C *OldCompilation) Lookup(file_name string) *Package { + for i := 0; i < C.pkg_ref; i++ { + pkg := C.pkg_list[i]; + if pkg.file_name == file_name { + return pkg; + } + } + return nil; +} + + +func (C *OldCompilation) Insert(pkg *Package) { + if C.Lookup(pkg.file_name) != nil { + panic("package already inserted"); + } + pkg.obj.pnolev = C.pkg_ref; + C.pkg_list[C.pkg_ref] = pkg; + C.pkg_ref++; +} diff --git a/usr/gri/pretty/object.go b/usr/gri/pretty/object.go new file mode 100755 index 0000000000..220f4c8d8b --- /dev/null +++ b/usr/gri/pretty/object.go @@ -0,0 +1,36 @@ +// 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 Object + +import Globals "globals" + + +export const /* kind */ ( + BAD = iota; // error handling + CONST; TYPE; VAR; FIELD; FUNC; BUILTIN; PACKAGE; LABEL; + END; // end of scope (import/export only) +) + + +// The 'Object' declaration should be here as well, but 6g cannot handle +// this due to cross-package circular references. For now it's all in +// globals.go. + + +export func KindStr(kind int) string { + switch kind { + case BAD: return "BAD"; + case CONST: return "CONST"; + case TYPE: return "TYPE"; + case VAR: return "VAR"; + case FIELD: return "FIELD"; + case FUNC: return "FUNC"; + case BUILTIN: return "BUILTIN"; + case PACKAGE: return "PACKAGE"; + case LABEL: return "LABEL"; + case END: return "END"; + } + return ""; +} diff --git a/usr/gri/pretty/type.go b/usr/gri/pretty/type.go new file mode 100644 index 0000000000..507357e65d --- /dev/null +++ b/usr/gri/pretty/type.go @@ -0,0 +1,207 @@ +// 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 Type + +import Globals "globals" +import Object "object" + + +export const /* form */ ( + // internal types + // We should never see one of these. + UNDEF = iota; + + // VOID types are used when we don't have a type. Never exported. + // (exported type forms must be > 0) + VOID; + + // BAD types are compatible with any type and don't cause further errors. + // They are introduced only as a result of an error in the source code. A + // correct program cannot have BAD types. + BAD; + + // FORWARD types are forward-declared (incomplete) types. They can only + // be used as element types of pointer types and must be resolved before + // their internals are accessible. + FORWARD; + + // TUPLE types represent multi-valued result types of functions and + // methods. + TUPLE; + + // The type of nil. + NIL; + + // basic types + BOOL; UINT; INT; FLOAT; STRING; INTEGER; + + // 'any' type // TODO this should go away eventually + ANY; + + // composite types + ALIAS; ARRAY; STRUCT; INTERFACE; MAP; CHANNEL; FUNCTION; METHOD; POINTER; +) + + +export const /* Type.aux */ ( + SEND = 1; // chan> + RECV = 2; // chan< +) + + +// The 'Type' declaration should be here as well, but 6g cannot handle +// this due to cross-package circular references. For now it's all in +// globals.go. + + +export func FormStr(form int) string { + switch form { + case VOID: return "VOID"; + case BAD: return "BAD"; + case FORWARD: return "FORWARD"; + case TUPLE: return "TUPLE"; + case NIL: return "NIL"; + case BOOL: return "BOOL"; + case UINT: return "UINT"; + case INT: return "INT"; + case FLOAT: return "FLOAT"; + case STRING: return "STRING"; + case ANY: return "ANY"; + case ALIAS: return "ALIAS"; + case ARRAY: return "ARRAY"; + case STRUCT: return "STRUCT"; + case INTERFACE: return "INTERFACE"; + case MAP: return "MAP"; + case CHANNEL: return "CHANNEL"; + case FUNCTION: return "FUNCTION"; + case METHOD: return "METHOD"; + case POINTER: return "POINTER"; + } + return ""; +} + + +export func Equal(x, y *Globals.Type) bool; + +func Equal0(x, y *Globals.Type) bool { + if x == y { + return true; // identical types are equal + } + + if x.form == BAD || y.form == BAD { + return true; // bad types are always equal (avoid excess error messages) + } + + // TODO where to check for *T == nil ? + if x.form != y.form { + return false; // types of different forms are not equal + } + + switch x.form { + case FORWARD, BAD: + break; + + case NIL, BOOL, STRING, ANY: + return true; + + case UINT, INT, FLOAT: + return x.size == y.size; + + case ARRAY: + return + x.len == y.len && + Equal(x.elt, y.elt); + + case MAP: + return + Equal(x.key, y.key) && + Equal(x.elt, y.elt); + + case CHANNEL: + return + x.aux == y.aux && + Equal(x.elt, y.elt); + + case FUNCTION, METHOD: + { panic(); + /* + xp := x.scope.entries; + yp := x.scope.entries; + if x.len != y.len && // number of parameters + xp.len != yp.len // recv + parameters + results + { + return false; + } + for p, q := xp.first, yp.first; p != nil; p, q = p.next, q.next { + xf := p.obj; + yf := q.obj; + if xf.kind != Object.VAR || yf.kind != Object.VAR { + panic("parameters must be vars"); + } + if !Equal(xf.typ, yf.typ) { + return false; + } + } + */ + } + return true; + + case STRUCT: + /* + { ObjList* xl = &x.scope.list; + ObjList* yl = &y.scope.list; + if xl.len() != yl.len() { + return false; // scopes of different sizes are not equal + } + for int i = xl.len(); i-- > 0; { + Object* xf = (*xl)[i]; + Object* yf = (*yl)[i]; + ASSERT(xf.kind == Object.VAR && yf.kind == Object.VAR); + if xf.name != yf.name) || ! EqualTypes(xf.type(), yf.type() { + return false; + } + } + } + return true; + */ + // Scopes must be identical for them to be equal. + // If we reach here, they weren't. + return false; + + case INTERFACE: + panic("UNIMPLEMENTED"); + return false; + + case POINTER: + return Equal(x.elt, y.elt); + + case TUPLE: + panic("UNIMPLEMENTED"); + return false; + } + + panic("UNREACHABLE"); + return false; +} + + +export func Equal(x, y *Globals.Type) bool { + res := Equal0(x, y); + // TODO should do the check below only in debug mode + if Equal0(y, x) != res { + panic("type equality must be symmetric"); + } + return res; +} + + +export func Assigneable(from, to *Globals.Type) bool { + if Equal(from, to) { + return true; + } + + panic("UNIMPLEMENTED"); + return false; +} diff --git a/usr/gri/pretty/universe.go b/usr/gri/pretty/universe.go new file mode 100755 index 0000000000..fb199ec353 --- /dev/null +++ b/usr/gri/pretty/universe.go @@ -0,0 +1,125 @@ +// 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 Universe + +import ( + "array" + Globals "globals"; + Object "object"; + Type "type"; +) + + +export var ( + scope *Globals.Scope; + types array.Array; + + // internal types + void_typ, + bad_typ, + nil_typ, + + // basic types + bool_typ, + uint8_typ, + uint16_typ, + uint32_typ, + uint64_typ, + int8_typ, + int16_typ, + int32_typ, + int64_typ, + float32_typ, + float64_typ, + float80_typ, + string_typ, + integer_typ, + + // convenience types + byte_typ, + uint_typ, + int_typ, + float_typ, + uintptr_typ *Globals.Type; + + true_obj, + false_obj, + iota_obj, + nil_obj *Globals.Object; +) + + +func DeclObj(kind int, ident string, typ *Globals.Type) *Globals.Object { + obj := Globals.NewObject(-1 /* no source pos */, kind, ident); + obj.typ = typ; + if kind == Object.TYPE && typ.obj == nil { + typ.obj = obj; // set primary type object + } + scope.Insert(obj); + return obj +} + + +func DeclType(form int, ident string, size int) *Globals.Type { + typ := Globals.NewType(form); + typ.size = size; + return DeclObj(Object.TYPE, ident, typ).typ; +} + + +func Register(typ *Globals.Type) *Globals.Type { + typ.ref = types.Len(); + types.Push(typ); + return typ; +} + + +func init() { + scope = Globals.NewScope(nil); // universe has no parent + types.Init(32); + + // Interal types + void_typ = Globals.NewType(Type.VOID); + Globals.Universe_void_typ = void_typ; + bad_typ = Globals.NewType(Type.BAD); + nil_typ = Globals.NewType(Type.NIL); + + // Basic types + bool_typ = Register(DeclType(Type.BOOL, "bool", 1)); + uint8_typ = Register(DeclType(Type.UINT, "uint8", 1)); + uint16_typ = Register(DeclType(Type.UINT, "uint16", 2)); + uint32_typ = Register(DeclType(Type.UINT, "uint32", 4)); + uint64_typ = Register(DeclType(Type.UINT, "uint64", 8)); + int8_typ = Register(DeclType(Type.INT, "int8", 1)); + int16_typ = Register(DeclType(Type.INT, "int16", 2)); + int32_typ = Register(DeclType(Type.INT, "int32", 4)); + int64_typ = Register(DeclType(Type.INT, "int64", 8)); + float32_typ = Register(DeclType(Type.FLOAT, "float32", 4)); + float64_typ = Register(DeclType(Type.FLOAT, "float64", 8)); + float80_typ = Register(DeclType(Type.FLOAT, "float80", 10)); + string_typ = Register(DeclType(Type.STRING, "string", 8)); + integer_typ = Register(DeclType(Type.INTEGER, "integer", 8)); + + // All but 'byte' should be platform-dependent, eventually. + byte_typ = Register(DeclType(Type.UINT, "byte", 1)); + uint_typ = Register(DeclType(Type.UINT, "uint", 4)); + int_typ = Register(DeclType(Type.INT, "int", 4)); + float_typ = Register(DeclType(Type.FLOAT, "float", 4)); + uintptr_typ = Register(DeclType(Type.UINT, "uintptr", 8)); + + // Predeclared constants + true_obj = DeclObj(Object.CONST, "true", bool_typ); + false_obj = DeclObj(Object.CONST, "false", bool_typ); + iota_obj = DeclObj(Object.CONST, "iota", int_typ); + nil_obj = DeclObj(Object.CONST, "nil", nil_typ); + + // Builtin functions + DeclObj(Object.BUILTIN, "len", void_typ); + DeclObj(Object.BUILTIN, "new", void_typ); + DeclObj(Object.BUILTIN, "panic", void_typ); + DeclObj(Object.BUILTIN, "print", void_typ); + + // scope.Print(); +} -- 2.48.1