diff options
Diffstat (limited to 'src/pkg/go/ast')
-rw-r--r-- | src/pkg/go/ast/Makefile | 16 | ||||
-rw-r--r-- | src/pkg/go/ast/ast.go | 914 | ||||
-rw-r--r-- | src/pkg/go/ast/filter.go | 475 | ||||
-rw-r--r-- | src/pkg/go/ast/print.go | 224 | ||||
-rw-r--r-- | src/pkg/go/ast/print_test.go | 77 | ||||
-rw-r--r-- | src/pkg/go/ast/resolve.go | 174 | ||||
-rw-r--r-- | src/pkg/go/ast/scope.go | 156 | ||||
-rw-r--r-- | src/pkg/go/ast/walk.go | 382 |
8 files changed, 2418 insertions, 0 deletions
diff --git a/src/pkg/go/ast/Makefile b/src/pkg/go/ast/Makefile new file mode 100644 index 000000000..40be10208 --- /dev/null +++ b/src/pkg/go/ast/Makefile @@ -0,0 +1,16 @@ +# 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. + +include ../../../Make.inc + +TARG=go/ast +GOFILES=\ + ast.go\ + filter.go\ + print.go\ + resolve.go\ + scope.go\ + walk.go\ + +include ../../../Make.pkg diff --git a/src/pkg/go/ast/ast.go b/src/pkg/go/ast/ast.go new file mode 100644 index 000000000..22bd5ee22 --- /dev/null +++ b/src/pkg/go/ast/ast.go @@ -0,0 +1,914 @@ +// 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 ast declares the types used to represent syntax trees for Go +// packages. +// +package ast + +import ( + "go/token" + "unicode" + "utf8" +) + +// ---------------------------------------------------------------------------- +// Interfaces +// +// There are 3 main classes of nodes: Expressions and type nodes, +// statement nodes, and declaration nodes. The node names usually +// match the corresponding Go spec production names to which they +// correspond. The node fields correspond to the individual parts +// of the respective productions. +// +// All nodes contain position information marking the beginning of +// the corresponding source text segment; it is accessible via the +// Pos accessor method. Nodes may contain additional position info +// for language constructs where comments may be found between parts +// of the construct (typically any larger, parenthesized subpart). +// That position information is needed to properly position comments +// when printing the construct. + +// All node types implement the Node interface. +type Node interface { + Pos() token.Pos // position of first character belonging to the node + End() token.Pos // position of first character immediately after the node +} + +// All expression nodes implement the Expr interface. +type Expr interface { + Node + exprNode() +} + +// All statement nodes implement the Stmt interface. +type Stmt interface { + Node + stmtNode() +} + +// All declaration nodes implement the Decl interface. +type Decl interface { + Node + declNode() +} + +// ---------------------------------------------------------------------------- +// Comments + +// A Comment node represents a single //-style or /*-style comment. +type Comment struct { + Slash token.Pos // position of "/" starting the comment + Text string // comment text (excluding '\n' for //-style comments) +} + +func (c *Comment) Pos() token.Pos { return c.Slash } +func (c *Comment) End() token.Pos { return token.Pos(int(c.Slash) + len(c.Text)) } + +// A CommentGroup represents a sequence of comments +// with no other tokens and no empty lines between. +// +type CommentGroup struct { + List []*Comment // len(List) > 0 +} + +func (g *CommentGroup) Pos() token.Pos { return g.List[0].Pos() } +func (g *CommentGroup) End() token.Pos { return g.List[len(g.List)-1].End() } + +// ---------------------------------------------------------------------------- +// Expressions and types + +// A Field represents a Field declaration list in a struct type, +// a method list in an interface type, or a parameter/result declaration +// in a signature. +// +type Field struct { + Doc *CommentGroup // associated documentation; or nil + Names []*Ident // field/method/parameter names; or nil if anonymous field + Type Expr // field/method/parameter type + Tag *BasicLit // field tag; or nil + Comment *CommentGroup // line comments; or nil +} + +func (f *Field) Pos() token.Pos { + if len(f.Names) > 0 { + return f.Names[0].Pos() + } + return f.Type.Pos() +} + +func (f *Field) End() token.Pos { + if f.Tag != nil { + return f.Tag.End() + } + return f.Type.End() +} + +// A FieldList represents a list of Fields, enclosed by parentheses or braces. +type FieldList struct { + Opening token.Pos // position of opening parenthesis/brace, if any + List []*Field // field list; or nil + Closing token.Pos // position of closing parenthesis/brace, if any +} + +func (f *FieldList) Pos() token.Pos { + if f.Opening.IsValid() { + return f.Opening + } + // the list should not be empty in this case; + // be conservative and guard against bad ASTs + if len(f.List) > 0 { + return f.List[0].Pos() + } + return token.NoPos +} + +func (f *FieldList) End() token.Pos { + if f.Closing.IsValid() { + return f.Closing + 1 + } + // the list should not be empty in this case; + // be conservative and guard against bad ASTs + if n := len(f.List); n > 0 { + return f.List[n-1].End() + } + return token.NoPos +} + +// NumFields returns the number of (named and anonymous fields) in a FieldList. +func (f *FieldList) NumFields() int { + n := 0 + if f != nil { + for _, g := range f.List { + m := len(g.Names) + if m == 0 { + m = 1 // anonymous field + } + n += m + } + } + return n +} + +// An expression is represented by a tree consisting of one +// or more of the following concrete expression nodes. +// +type ( + // A BadExpr node is a placeholder for expressions containing + // syntax errors for which no correct expression nodes can be + // created. + // + BadExpr struct { + From, To token.Pos // position range of bad expression + } + + // An Ident node represents an identifier. + Ident struct { + NamePos token.Pos // identifier position + Name string // identifier name + Obj *Object // denoted object; or nil + } + + // An Ellipsis node stands for the "..." type in a + // parameter list or the "..." length in an array type. + // + Ellipsis struct { + Ellipsis token.Pos // position of "..." + Elt Expr // ellipsis element type (parameter lists only); or nil + } + + // A BasicLit node represents a literal of basic type. + BasicLit struct { + ValuePos token.Pos // literal position + Kind token.Token // token.INT, token.FLOAT, token.IMAG, token.CHAR, or token.STRING + Value string // literal string; e.g. 42, 0x7f, 3.14, 1e-9, 2.4i, 'a', '\x7f', "foo" or `\m\n\o` + } + + // A FuncLit node represents a function literal. + FuncLit struct { + Type *FuncType // function type + Body *BlockStmt // function body + } + + // A CompositeLit node represents a composite literal. + CompositeLit struct { + Type Expr // literal type; or nil + Lbrace token.Pos // position of "{" + Elts []Expr // list of composite elements; or nil + Rbrace token.Pos // position of "}" + } + + // A ParenExpr node represents a parenthesized expression. + ParenExpr struct { + Lparen token.Pos // position of "(" + X Expr // parenthesized expression + Rparen token.Pos // position of ")" + } + + // A SelectorExpr node represents an expression followed by a selector. + SelectorExpr struct { + X Expr // expression + Sel *Ident // field selector + } + + // An IndexExpr node represents an expression followed by an index. + IndexExpr struct { + X Expr // expression + Lbrack token.Pos // position of "[" + Index Expr // index expression + Rbrack token.Pos // position of "]" + } + + // An SliceExpr node represents an expression followed by slice indices. + SliceExpr struct { + X Expr // expression + Lbrack token.Pos // position of "[" + Low Expr // begin of slice range; or nil + High Expr // end of slice range; or nil + Rbrack token.Pos // position of "]" + } + + // A TypeAssertExpr node represents an expression followed by a + // type assertion. + // + TypeAssertExpr struct { + X Expr // expression + Type Expr // asserted type; nil means type switch X.(type) + } + + // A CallExpr node represents an expression followed by an argument list. + CallExpr struct { + Fun Expr // function expression + Lparen token.Pos // position of "(" + Args []Expr // function arguments; or nil + Ellipsis token.Pos // position of "...", if any + Rparen token.Pos // position of ")" + } + + // A StarExpr node represents an expression of the form "*" Expression. + // Semantically it could be a unary "*" expression, or a pointer type. + // + StarExpr struct { + Star token.Pos // position of "*" + X Expr // operand + } + + // A UnaryExpr node represents a unary expression. + // Unary "*" expressions are represented via StarExpr nodes. + // + UnaryExpr struct { + OpPos token.Pos // position of Op + Op token.Token // operator + X Expr // operand + } + + // A BinaryExpr node represents a binary expression. + BinaryExpr struct { + X Expr // left operand + OpPos token.Pos // position of Op + Op token.Token // operator + Y Expr // right operand + } + + // A KeyValueExpr node represents (key : value) pairs + // in composite literals. + // + KeyValueExpr struct { + Key Expr + Colon token.Pos // position of ":" + Value Expr + } +) + +// The direction of a channel type is indicated by one +// of the following constants. +// +type ChanDir int + +const ( + SEND ChanDir = 1 << iota + RECV +) + +// A type is represented by a tree consisting of one +// or more of the following type-specific expression +// nodes. +// +type ( + // An ArrayType node represents an array or slice type. + ArrayType struct { + Lbrack token.Pos // position of "[" + Len Expr // Ellipsis node for [...]T array types, nil for slice types + Elt Expr // element type + } + + // A StructType node represents a struct type. + StructType struct { + Struct token.Pos // position of "struct" keyword + Fields *FieldList // list of field declarations + Incomplete bool // true if (source) fields are missing in the Fields list + } + + // Pointer types are represented via StarExpr nodes. + + // A FuncType node represents a function type. + FuncType struct { + Func token.Pos // position of "func" keyword + Params *FieldList // (incoming) parameters; or nil + Results *FieldList // (outgoing) results; or nil + } + + // An InterfaceType node represents an interface type. + InterfaceType struct { + Interface token.Pos // position of "interface" keyword + Methods *FieldList // list of methods + Incomplete bool // true if (source) methods are missing in the Methods list + } + + // A MapType node represents a map type. + MapType struct { + Map token.Pos // position of "map" keyword + Key Expr + Value Expr + } + + // A ChanType node represents a channel type. + ChanType struct { + Begin token.Pos // position of "chan" keyword or "<-" (whichever comes first) + Dir ChanDir // channel direction + Value Expr // value type + } +) + +// Pos and End implementations for expression/type nodes. +// +func (x *BadExpr) Pos() token.Pos { return x.From } +func (x *Ident) Pos() token.Pos { return x.NamePos } +func (x *Ellipsis) Pos() token.Pos { return x.Ellipsis } +func (x *BasicLit) Pos() token.Pos { return x.ValuePos } +func (x *FuncLit) Pos() token.Pos { return x.Type.Pos() } +func (x *CompositeLit) Pos() token.Pos { + if x.Type != nil { + return x.Type.Pos() + } + return x.Lbrace +} +func (x *ParenExpr) Pos() token.Pos { return x.Lparen } +func (x *SelectorExpr) Pos() token.Pos { return x.X.Pos() } +func (x *IndexExpr) Pos() token.Pos { return x.X.Pos() } +func (x *SliceExpr) Pos() token.Pos { return x.X.Pos() } +func (x *TypeAssertExpr) Pos() token.Pos { return x.X.Pos() } +func (x *CallExpr) Pos() token.Pos { return x.Fun.Pos() } +func (x *StarExpr) Pos() token.Pos { return x.Star } +func (x *UnaryExpr) Pos() token.Pos { return x.OpPos } +func (x *BinaryExpr) Pos() token.Pos { return x.X.Pos() } +func (x *KeyValueExpr) Pos() token.Pos { return x.Key.Pos() } +func (x *ArrayType) Pos() token.Pos { return x.Lbrack } +func (x *StructType) Pos() token.Pos { return x.Struct } +func (x *FuncType) Pos() token.Pos { return x.Func } +func (x *InterfaceType) Pos() token.Pos { return x.Interface } +func (x *MapType) Pos() token.Pos { return x.Map } +func (x *ChanType) Pos() token.Pos { return x.Begin } + +func (x *BadExpr) End() token.Pos { return x.To } +func (x *Ident) End() token.Pos { return token.Pos(int(x.NamePos) + len(x.Name)) } +func (x *Ellipsis) End() token.Pos { + if x.Elt != nil { + return x.Elt.End() + } + return x.Ellipsis + 3 // len("...") +} +func (x *BasicLit) End() token.Pos { return token.Pos(int(x.ValuePos) + len(x.Value)) } +func (x *FuncLit) End() token.Pos { return x.Body.End() } +func (x *CompositeLit) End() token.Pos { return x.Rbrace + 1 } +func (x *ParenExpr) End() token.Pos { return x.Rparen + 1 } +func (x *SelectorExpr) End() token.Pos { return x.Sel.End() } +func (x *IndexExpr) End() token.Pos { return x.Rbrack + 1 } +func (x *SliceExpr) End() token.Pos { return x.Rbrack + 1 } +func (x *TypeAssertExpr) End() token.Pos { + if x.Type != nil { + return x.Type.End() + } + return x.X.End() +} +func (x *CallExpr) End() token.Pos { return x.Rparen + 1 } +func (x *StarExpr) End() token.Pos { return x.X.End() } +func (x *UnaryExpr) End() token.Pos { return x.X.End() } +func (x *BinaryExpr) End() token.Pos { return x.Y.End() } +func (x *KeyValueExpr) End() token.Pos { return x.Value.End() } +func (x *ArrayType) End() token.Pos { return x.Elt.End() } +func (x *StructType) End() token.Pos { return x.Fields.End() } +func (x *FuncType) End() token.Pos { + if x.Results != nil { + return x.Results.End() + } + return x.Params.End() +} +func (x *InterfaceType) End() token.Pos { return x.Methods.End() } +func (x *MapType) End() token.Pos { return x.Value.End() } +func (x *ChanType) End() token.Pos { return x.Value.End() } + +// exprNode() ensures that only expression/type nodes can be +// assigned to an ExprNode. +// +func (x *BadExpr) exprNode() {} +func (x *Ident) exprNode() {} +func (x *Ellipsis) exprNode() {} +func (x *BasicLit) exprNode() {} +func (x *FuncLit) exprNode() {} +func (x *CompositeLit) exprNode() {} +func (x *ParenExpr) exprNode() {} +func (x *SelectorExpr) exprNode() {} +func (x *IndexExpr) exprNode() {} +func (x *SliceExpr) exprNode() {} +func (x *TypeAssertExpr) exprNode() {} +func (x *CallExpr) exprNode() {} +func (x *StarExpr) exprNode() {} +func (x *UnaryExpr) exprNode() {} +func (x *BinaryExpr) exprNode() {} +func (x *KeyValueExpr) exprNode() {} + +func (x *ArrayType) exprNode() {} +func (x *StructType) exprNode() {} +func (x *FuncType) exprNode() {} +func (x *InterfaceType) exprNode() {} +func (x *MapType) exprNode() {} +func (x *ChanType) exprNode() {} + +// ---------------------------------------------------------------------------- +// Convenience functions for Idents + +var noPos token.Pos + +// NewIdent creates a new Ident without position. +// Useful for ASTs generated by code other than the Go parser. +// +func NewIdent(name string) *Ident { return &Ident{noPos, name, nil} } + +// IsExported returns whether name is an exported Go symbol +// (i.e., whether it begins with an uppercase letter). +// +func IsExported(name string) bool { + ch, _ := utf8.DecodeRuneInString(name) + return unicode.IsUpper(ch) +} + +// IsExported returns whether id is an exported Go symbol +// (i.e., whether it begins with an uppercase letter). +// +func (id *Ident) IsExported() bool { return IsExported(id.Name) } + +func (id *Ident) String() string { + if id != nil { + return id.Name + } + return "<nil>" +} + +// ---------------------------------------------------------------------------- +// Statements + +// A statement is represented by a tree consisting of one +// or more of the following concrete statement nodes. +// +type ( + // A BadStmt node is a placeholder for statements containing + // syntax errors for which no correct statement nodes can be + // created. + // + BadStmt struct { + From, To token.Pos // position range of bad statement + } + + // A DeclStmt node represents a declaration in a statement list. + DeclStmt struct { + Decl Decl + } + + // An EmptyStmt node represents an empty statement. + // The "position" of the empty statement is the position + // of the immediately preceding semicolon. + // + EmptyStmt struct { + Semicolon token.Pos // position of preceding ";" + } + + // A LabeledStmt node represents a labeled statement. + LabeledStmt struct { + Label *Ident + Colon token.Pos // position of ":" + Stmt Stmt + } + + // An ExprStmt node represents a (stand-alone) expression + // in a statement list. + // + ExprStmt struct { + X Expr // expression + } + + // A SendStmt node represents a send statement. + SendStmt struct { + Chan Expr + Arrow token.Pos // position of "<-" + Value Expr + } + + // An IncDecStmt node represents an increment or decrement statement. + IncDecStmt struct { + X Expr + TokPos token.Pos // position of Tok + Tok token.Token // INC or DEC + } + + // An AssignStmt node represents an assignment or + // a short variable declaration. + // + AssignStmt struct { + Lhs []Expr + TokPos token.Pos // position of Tok + Tok token.Token // assignment token, DEFINE + Rhs []Expr + } + + // A GoStmt node represents a go statement. + GoStmt struct { + Go token.Pos // position of "go" keyword + Call *CallExpr + } + + // A DeferStmt node represents a defer statement. + DeferStmt struct { + Defer token.Pos // position of "defer" keyword + Call *CallExpr + } + + // A ReturnStmt node represents a return statement. + ReturnStmt struct { + Return token.Pos // position of "return" keyword + Results []Expr // result expressions; or nil + } + + // A BranchStmt node represents a break, continue, goto, + // or fallthrough statement. + // + BranchStmt struct { + TokPos token.Pos // position of Tok + Tok token.Token // keyword token (BREAK, CONTINUE, GOTO, FALLTHROUGH) + Label *Ident // label name; or nil + } + + // A BlockStmt node represents a braced statement list. + BlockStmt struct { + Lbrace token.Pos // position of "{" + List []Stmt + Rbrace token.Pos // position of "}" + } + + // An IfStmt node represents an if statement. + IfStmt struct { + If token.Pos // position of "if" keyword + Init Stmt // initialization statement; or nil + Cond Expr // condition + Body *BlockStmt + Else Stmt // else branch; or nil + } + + // A CaseClause represents a case of an expression or type switch statement. + CaseClause struct { + Case token.Pos // position of "case" or "default" keyword + List []Expr // list of expressions or types; nil means default case + Colon token.Pos // position of ":" + Body []Stmt // statement list; or nil + } + + // A SwitchStmt node represents an expression switch statement. + SwitchStmt struct { + Switch token.Pos // position of "switch" keyword + Init Stmt // initialization statement; or nil + Tag Expr // tag expression; or nil + Body *BlockStmt // CaseClauses only + } + + // An TypeSwitchStmt node represents a type switch statement. + TypeSwitchStmt struct { + Switch token.Pos // position of "switch" keyword + Init Stmt // initialization statement; or nil + Assign Stmt // x := y.(type) or y.(type) + Body *BlockStmt // CaseClauses only + } + + // A CommClause node represents a case of a select statement. + CommClause struct { + Case token.Pos // position of "case" or "default" keyword + Comm Stmt // send or receive statement; nil means default case + Colon token.Pos // position of ":" + Body []Stmt // statement list; or nil + } + + // An SelectStmt node represents a select statement. + SelectStmt struct { + Select token.Pos // position of "select" keyword + Body *BlockStmt // CommClauses only + } + + // A ForStmt represents a for statement. + ForStmt struct { + For token.Pos // position of "for" keyword + Init Stmt // initialization statement; or nil + Cond Expr // condition; or nil + Post Stmt // post iteration statement; or nil + Body *BlockStmt + } + + // A RangeStmt represents a for statement with a range clause. + RangeStmt struct { + For token.Pos // position of "for" keyword + Key, Value Expr // Value may be nil + TokPos token.Pos // position of Tok + Tok token.Token // ASSIGN, DEFINE + X Expr // value to range over + Body *BlockStmt + } +) + +// Pos and End implementations for statement nodes. +// +func (s *BadStmt) Pos() token.Pos { return s.From } +func (s *DeclStmt) Pos() token.Pos { return s.Decl.Pos() } +func (s *EmptyStmt) Pos() token.Pos { return s.Semicolon } +func (s *LabeledStmt) Pos() token.Pos { return s.Label.Pos() } +func (s *ExprStmt) Pos() token.Pos { return s.X.Pos() } +func (s *SendStmt) Pos() token.Pos { return s.Chan.Pos() } +func (s *IncDecStmt) Pos() token.Pos { return s.X.Pos() } +func (s *AssignStmt) Pos() token.Pos { return s.Lhs[0].Pos() } +func (s *GoStmt) Pos() token.Pos { return s.Go } +func (s *DeferStmt) Pos() token.Pos { return s.Defer } +func (s *ReturnStmt) Pos() token.Pos { return s.Return } +func (s *BranchStmt) Pos() token.Pos { return s.TokPos } +func (s *BlockStmt) Pos() token.Pos { return s.Lbrace } +func (s *IfStmt) Pos() token.Pos { return s.If } +func (s *CaseClause) Pos() token.Pos { return s.Case } +func (s *SwitchStmt) Pos() token.Pos { return s.Switch } +func (s *TypeSwitchStmt) Pos() token.Pos { return s.Switch } +func (s *CommClause) Pos() token.Pos { return s.Case } +func (s *SelectStmt) Pos() token.Pos { return s.Select } +func (s *ForStmt) Pos() token.Pos { return s.For } +func (s *RangeStmt) Pos() token.Pos { return s.For } + +func (s *BadStmt) End() token.Pos { return s.To } +func (s *DeclStmt) End() token.Pos { return s.Decl.End() } +func (s *EmptyStmt) End() token.Pos { + return s.Semicolon + 1 /* len(";") */ +} +func (s *LabeledStmt) End() token.Pos { return s.Stmt.End() } +func (s *ExprStmt) End() token.Pos { return s.X.End() } +func (s *SendStmt) End() token.Pos { return s.Value.End() } +func (s *IncDecStmt) End() token.Pos { + return s.TokPos + 2 /* len("++") */ +} +func (s *AssignStmt) End() token.Pos { return s.Rhs[len(s.Rhs)-1].End() } +func (s *GoStmt) End() token.Pos { return s.Call.End() } +func (s *DeferStmt) End() token.Pos { return s.Call.End() } +func (s *ReturnStmt) End() token.Pos { + if n := len(s.Results); n > 0 { + return s.Results[n-1].End() + } + return s.Return + 6 // len("return") +} +func (s *BranchStmt) End() token.Pos { + if s.Label != nil { + return s.Label.End() + } + return token.Pos(int(s.TokPos) + len(s.Tok.String())) +} +func (s *BlockStmt) End() token.Pos { return s.Rbrace + 1 } +func (s *IfStmt) End() token.Pos { + if s.Else != nil { + return s.Else.End() + } + return s.Body.End() +} +func (s *CaseClause) End() token.Pos { + if n := len(s.Body); n > 0 { + return s.Body[n-1].End() + } + return s.Colon + 1 +} +func (s *SwitchStmt) End() token.Pos { return s.Body.End() } +func (s *TypeSwitchStmt) End() token.Pos { return s.Body.End() } +func (s *CommClause) End() token.Pos { + if n := len(s.Body); n > 0 { + return s.Body[n-1].End() + } + return s.Colon + 1 +} +func (s *SelectStmt) End() token.Pos { return s.Body.End() } +func (s *ForStmt) End() token.Pos { return s.Body.End() } +func (s *RangeStmt) End() token.Pos { return s.Body.End() } + +// stmtNode() ensures that only statement nodes can be +// assigned to a StmtNode. +// +func (s *BadStmt) stmtNode() {} +func (s *DeclStmt) stmtNode() {} +func (s *EmptyStmt) stmtNode() {} +func (s *LabeledStmt) stmtNode() {} +func (s *ExprStmt) stmtNode() {} +func (s *SendStmt) stmtNode() {} +func (s *IncDecStmt) stmtNode() {} +func (s *AssignStmt) stmtNode() {} +func (s *GoStmt) stmtNode() {} +func (s *DeferStmt) stmtNode() {} +func (s *ReturnStmt) stmtNode() {} +func (s *BranchStmt) stmtNode() {} +func (s *BlockStmt) stmtNode() {} +func (s *IfStmt) stmtNode() {} +func (s *CaseClause) stmtNode() {} +func (s *SwitchStmt) stmtNode() {} +func (s *TypeSwitchStmt) stmtNode() {} +func (s *CommClause) stmtNode() {} +func (s *SelectStmt) stmtNode() {} +func (s *ForStmt) stmtNode() {} +func (s *RangeStmt) stmtNode() {} + +// ---------------------------------------------------------------------------- +// Declarations + +// A Spec node represents a single (non-parenthesized) import, +// constant, type, or variable declaration. +// +type ( + // The Spec type stands for any of *ImportSpec, *ValueSpec, and *TypeSpec. + Spec interface { + Node + specNode() + } + + // An ImportSpec node represents a single package import. + ImportSpec struct { + Doc *CommentGroup // associated documentation; or nil + Name *Ident // local package name (including "."); or nil + Path *BasicLit // import path + Comment *CommentGroup // line comments; or nil + } + + // A ValueSpec node represents a constant or variable declaration + // (ConstSpec or VarSpec production). + // + ValueSpec struct { + Doc *CommentGroup // associated documentation; or nil + Names []*Ident // value names (len(Names) > 0) + Type Expr // value type; or nil + Values []Expr // initial values; or nil + Comment *CommentGroup // line comments; or nil + } + + // A TypeSpec node represents a type declaration (TypeSpec production). + TypeSpec struct { + Doc *CommentGroup // associated documentation; or nil + Name *Ident // type name + Type Expr // *Ident, *ParenExpr, *SelectorExpr, *StarExpr, or any of the *XxxTypes + Comment *CommentGroup // line comments; or nil + } +) + +// Pos and End implementations for spec nodes. +// +func (s *ImportSpec) Pos() token.Pos { + if s.Name != nil { + return s.Name.Pos() + } + return s.Path.Pos() +} +func (s *ValueSpec) Pos() token.Pos { return s.Names[0].Pos() } +func (s *TypeSpec) Pos() token.Pos { return s.Name.Pos() } + +func (s *ImportSpec) End() token.Pos { return s.Path.End() } +func (s *ValueSpec) End() token.Pos { + if n := len(s.Values); n > 0 { + return s.Values[n-1].End() + } + if s.Type != nil { + return s.Type.End() + } + return s.Names[len(s.Names)-1].End() +} +func (s *TypeSpec) End() token.Pos { return s.Type.End() } + +// specNode() ensures that only spec nodes can be +// assigned to a Spec. +// +func (s *ImportSpec) specNode() {} +func (s *ValueSpec) specNode() {} +func (s *TypeSpec) specNode() {} + +// A declaration is represented by one of the following declaration nodes. +// +type ( + // A BadDecl node is a placeholder for declarations containing + // syntax errors for which no correct declaration nodes can be + // created. + // + BadDecl struct { + From, To token.Pos // position range of bad declaration + } + + // A GenDecl node (generic declaration node) represents an import, + // constant, type or variable declaration. A valid Lparen position + // (Lparen.Line > 0) indicates a parenthesized declaration. + // + // Relationship between Tok value and Specs element type: + // + // token.IMPORT *ImportSpec + // token.CONST *ValueSpec + // token.TYPE *TypeSpec + // token.VAR *ValueSpec + // + GenDecl struct { + Doc *CommentGroup // associated documentation; or nil + TokPos token.Pos // position of Tok + Tok token.Token // IMPORT, CONST, TYPE, VAR + Lparen token.Pos // position of '(', if any + Specs []Spec + Rparen token.Pos // position of ')', if any + } + + // A FuncDecl node represents a function declaration. + FuncDecl struct { + Doc *CommentGroup // associated documentation; or nil + Recv *FieldList // receiver (methods); or nil (functions) + Name *Ident // function/method name + Type *FuncType // position of Func keyword, parameters and results + Body *BlockStmt // function body; or nil (forward declaration) + } +) + +// Pos and End implementations for declaration nodes. +// +func (d *BadDecl) Pos() token.Pos { return d.From } +func (d *GenDecl) Pos() token.Pos { return d.TokPos } +func (d *FuncDecl) Pos() token.Pos { return d.Type.Pos() } + +func (d *BadDecl) End() token.Pos { return d.To } +func (d *GenDecl) End() token.Pos { + if d.Rparen.IsValid() { + return d.Rparen + 1 + } + return d.Specs[0].End() +} +func (d *FuncDecl) End() token.Pos { + if d.Body != nil { + return d.Body.End() + } + return d.Type.End() +} + +// declNode() ensures that only declaration nodes can be +// assigned to a DeclNode. +// +func (d *BadDecl) declNode() {} +func (d *GenDecl) declNode() {} +func (d *FuncDecl) declNode() {} + +// ---------------------------------------------------------------------------- +// Files and packages + +// A File node represents a Go source file. +// +// The Comments list contains all comments in the source file in order of +// appearance, including the comments that are pointed to from other nodes +// via Doc and Comment fields. +// +type File struct { + Doc *CommentGroup // associated documentation; or nil + Package token.Pos // position of "package" keyword + Name *Ident // package name + Decls []Decl // top-level declarations; or nil + Scope *Scope // package scope (this file only) + Imports []*ImportSpec // imports in this file + Unresolved []*Ident // unresolved identifiers in this file + Comments []*CommentGroup // list of all comments in the source file +} + +func (f *File) Pos() token.Pos { return f.Package } +func (f *File) End() token.Pos { + if n := len(f.Decls); n > 0 { + return f.Decls[n-1].End() + } + return f.Name.End() +} + +// A Package node represents a set of source files +// collectively building a Go package. +// +type Package struct { + Name string // package name + Scope *Scope // package scope across all files + Imports map[string]*Object // map of package id -> package object + Files map[string]*File // Go source files by filename +} + +func (p *Package) Pos() token.Pos { return token.NoPos } +func (p *Package) End() token.Pos { return token.NoPos } diff --git a/src/pkg/go/ast/filter.go b/src/pkg/go/ast/filter.go new file mode 100644 index 000000000..26733430d --- /dev/null +++ b/src/pkg/go/ast/filter.go @@ -0,0 +1,475 @@ +// 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 ast + +import "go/token" + +// ---------------------------------------------------------------------------- +// Export filtering + +func identListExports(list []*Ident) []*Ident { + j := 0 + for _, x := range list { + if x.IsExported() { + list[j] = x + j++ + } + } + return list[0:j] +} + +// fieldName assumes that x is the type of an anonymous field and +// returns the corresponding field name. If x is not an acceptable +// anonymous field, the result is nil. +// +func fieldName(x Expr) *Ident { + switch t := x.(type) { + case *Ident: + return t + case *SelectorExpr: + if _, ok := t.X.(*Ident); ok { + return t.Sel + } + case *StarExpr: + return fieldName(t.X) + } + return nil +} + +func fieldListExports(fields *FieldList) (removedFields bool) { + if fields == nil { + return + } + list := fields.List + j := 0 + for _, f := range list { + exported := false + if len(f.Names) == 0 { + // anonymous field + // (Note that a non-exported anonymous field + // may still refer to a type with exported + // fields, so this is not absolutely correct. + // However, this cannot be done w/o complete + // type information.) + name := fieldName(f.Type) + exported = name != nil && name.IsExported() + } else { + n := len(f.Names) + f.Names = identListExports(f.Names) + if len(f.Names) < n { + removedFields = true + } + exported = len(f.Names) > 0 + } + if exported { + typeExports(f.Type) + list[j] = f + j++ + } + } + if j < len(list) { + removedFields = true + } + fields.List = list[0:j] + return +} + +func paramListExports(fields *FieldList) { + if fields == nil { + return + } + for _, f := range fields.List { + typeExports(f.Type) + } +} + +func typeExports(typ Expr) { + switch t := typ.(type) { + case *ArrayType: + typeExports(t.Elt) + case *StructType: + if fieldListExports(t.Fields) { + t.Incomplete = true + } + case *FuncType: + paramListExports(t.Params) + paramListExports(t.Results) + case *InterfaceType: + if fieldListExports(t.Methods) { + t.Incomplete = true + } + case *MapType: + typeExports(t.Key) + typeExports(t.Value) + case *ChanType: + typeExports(t.Value) + } +} + +func specExports(spec Spec) bool { + switch s := spec.(type) { + case *ValueSpec: + s.Names = identListExports(s.Names) + if len(s.Names) > 0 { + typeExports(s.Type) + return true + } + case *TypeSpec: + if s.Name.IsExported() { + typeExports(s.Type) + return true + } + } + return false +} + +func specListExports(list []Spec) []Spec { + j := 0 + for _, s := range list { + if specExports(s) { + list[j] = s + j++ + } + } + return list[0:j] +} + +func declExports(decl Decl) bool { + switch d := decl.(type) { + case *GenDecl: + d.Specs = specListExports(d.Specs) + return len(d.Specs) > 0 + case *FuncDecl: + d.Body = nil // strip body + return d.Name.IsExported() + } + return false +} + +// FileExports trims the AST for a Go source file in place such that only +// exported nodes remain: all top-level identifiers which are not exported +// and their associated information (such as type, initial value, or function +// body) are removed. Non-exported fields and methods of exported types are +// stripped, and the function bodies of exported functions are set to nil. +// The File.comments list is not changed. +// +// FileExports returns true if there is an exported declaration; it returns +// false otherwise. +// +func FileExports(src *File) bool { + j := 0 + for _, d := range src.Decls { + if declExports(d) { + src.Decls[j] = d + j++ + } + } + src.Decls = src.Decls[0:j] + return j > 0 +} + +// PackageExports trims the AST for a Go package in place such that only +// exported nodes remain. The pkg.Files list is not changed, so that file +// names and top-level package comments don't get lost. +// +// PackageExports returns true if there is an exported declaration; it +// returns false otherwise. +// +func PackageExports(pkg *Package) bool { + hasExports := false + for _, f := range pkg.Files { + if FileExports(f) { + hasExports = true + } + } + return hasExports +} + +// ---------------------------------------------------------------------------- +// General filtering + +type Filter func(string) bool + +func filterIdentList(list []*Ident, f Filter) []*Ident { + j := 0 + for _, x := range list { + if f(x.Name) { + list[j] = x + j++ + } + } + return list[0:j] +} + +func filterFieldList(fields *FieldList, filter Filter) (removedFields bool) { + if fields == nil { + return false + } + list := fields.List + j := 0 + for _, f := range list { + keepField := false + if len(f.Names) == 0 { + // anonymous field + name := fieldName(f.Type) + keepField = name != nil && filter(name.Name) + } else { + n := len(f.Names) + f.Names = filterIdentList(f.Names, filter) + if len(f.Names) < n { + removedFields = true + } + keepField = len(f.Names) > 0 + } + if keepField { + list[j] = f + j++ + } + } + if j < len(list) { + removedFields = true + } + fields.List = list[0:j] + return +} + +func filterSpec(spec Spec, f Filter) bool { + switch s := spec.(type) { + case *ValueSpec: + s.Names = filterIdentList(s.Names, f) + return len(s.Names) > 0 + case *TypeSpec: + if f(s.Name.Name) { + return true + } + switch t := s.Type.(type) { + case *StructType: + if filterFieldList(t.Fields, f) { + t.Incomplete = true + } + return len(t.Fields.List) > 0 + case *InterfaceType: + if filterFieldList(t.Methods, f) { + t.Incomplete = true + } + return len(t.Methods.List) > 0 + } + } + return false +} + +func filterSpecList(list []Spec, f Filter) []Spec { + j := 0 + for _, s := range list { + if filterSpec(s, f) { + list[j] = s + j++ + } + } + return list[0:j] +} + +// FilterDecl trims the AST for a Go declaration in place by removing +// all names (including struct field and interface method names, but +// not from parameter lists) that don't pass through the filter f. +// +// FilterDecl returns true if there are any declared names left after +// filtering; it returns false otherwise. +// +func FilterDecl(decl Decl, f Filter) bool { + switch d := decl.(type) { + case *GenDecl: + d.Specs = filterSpecList(d.Specs, f) + return len(d.Specs) > 0 + case *FuncDecl: + return f(d.Name.Name) + } + return false +} + +// FilterFile trims the AST for a Go file in place by removing all +// names from top-level declarations (including struct field and +// interface method names, but not from parameter lists) that don't +// pass through the filter f. If the declaration is empty afterwards, +// the declaration is removed from the AST. +// The File.comments list is not changed. +// +// FilterFile returns true if there are any top-level declarations +// left after filtering; it returns false otherwise. +// +func FilterFile(src *File, f Filter) bool { + j := 0 + for _, d := range src.Decls { + if FilterDecl(d, f) { + src.Decls[j] = d + j++ + } + } + src.Decls = src.Decls[0:j] + return j > 0 +} + +// FilterPackage trims the AST for a Go package in place by removing all +// names from top-level declarations (including struct field and +// interface method names, but not from parameter lists) that don't +// pass through the filter f. If the declaration is empty afterwards, +// the declaration is removed from the AST. +// The pkg.Files list is not changed, so that file names and top-level +// package comments don't get lost. +// +// FilterPackage returns true if there are any top-level declarations +// left after filtering; it returns false otherwise. +// +func FilterPackage(pkg *Package, f Filter) bool { + hasDecls := false + for _, src := range pkg.Files { + if FilterFile(src, f) { + hasDecls = true + } + } + return hasDecls +} + +// ---------------------------------------------------------------------------- +// Merging of package files + +// The MergeMode flags control the behavior of MergePackageFiles. +type MergeMode uint + +const ( + // If set, duplicate function declarations are excluded. + FilterFuncDuplicates MergeMode = 1 << iota + // If set, comments that are not associated with a specific + // AST node (as Doc or Comment) are excluded. + FilterUnassociatedComments +) + +// separator is an empty //-style comment that is interspersed between +// different comment groups when they are concatenated into a single group +// +var separator = &Comment{noPos, "//"} + +// MergePackageFiles creates a file AST by merging the ASTs of the +// files belonging to a package. The mode flags control merging behavior. +// +func MergePackageFiles(pkg *Package, mode MergeMode) *File { + // Count the number of package docs, comments and declarations across + // all package files. + ndocs := 0 + ncomments := 0 + ndecls := 0 + for _, f := range pkg.Files { + if f.Doc != nil { + ndocs += len(f.Doc.List) + 1 // +1 for separator + } + ncomments += len(f.Comments) + ndecls += len(f.Decls) + } + + // Collect package comments from all package files into a single + // CommentGroup - the collected package documentation. The order + // is unspecified. In general there should be only one file with + // a package comment; but it's better to collect extra comments + // than drop them on the floor. + var doc *CommentGroup + var pos token.Pos + if ndocs > 0 { + list := make([]*Comment, ndocs-1) // -1: no separator before first group + i := 0 + for _, f := range pkg.Files { + if f.Doc != nil { + if i > 0 { + // not the first group - add separator + list[i] = separator + i++ + } + for _, c := range f.Doc.List { + list[i] = c + i++ + } + if f.Package > pos { + // Keep the maximum package clause position as + // position for the package clause of the merged + // files. + pos = f.Package + } + } + } + doc = &CommentGroup{list} + } + + // Collect declarations from all package files. + var decls []Decl + if ndecls > 0 { + decls = make([]Decl, ndecls) + funcs := make(map[string]int) // map of global function name -> decls index + i := 0 // current index + n := 0 // number of filtered entries + for _, f := range pkg.Files { + for _, d := range f.Decls { + if mode&FilterFuncDuplicates != 0 { + // A language entity may be declared multiple + // times in different package files; only at + // build time declarations must be unique. + // For now, exclude multiple declarations of + // functions - keep the one with documentation. + // + // TODO(gri): Expand this filtering to other + // entities (const, type, vars) if + // multiple declarations are common. + if f, isFun := d.(*FuncDecl); isFun { + name := f.Name.Name + if j, exists := funcs[name]; exists { + // function declared already + if decls[j] != nil && decls[j].(*FuncDecl).Doc == nil { + // existing declaration has no documentation; + // ignore the existing declaration + decls[j] = nil + } else { + // ignore the new declaration + d = nil + } + n++ // filtered an entry + } else { + funcs[name] = i + } + } + } + decls[i] = d + i++ + } + } + + // Eliminate nil entries from the decls list if entries were + // filtered. We do this using a 2nd pass in order to not disturb + // the original declaration order in the source (otherwise, this + // would also invalidate the monotonically increasing position + // info within a single file). + if n > 0 { + i = 0 + for _, d := range decls { + if d != nil { + decls[i] = d + i++ + } + } + decls = decls[0:i] + } + } + + // Collect comments from all package files. + var comments []*CommentGroup + if mode&FilterUnassociatedComments == 0 { + comments = make([]*CommentGroup, ncomments) + i := 0 + for _, f := range pkg.Files { + i += copy(comments[i:], f.Comments) + } + } + + // TODO(gri) need to compute pkgScope and unresolved identifiers! + // TODO(gri) need to compute imports! + return &File{doc, pos, NewIdent(pkg.Name), decls, nil, nil, nil, comments} +} diff --git a/src/pkg/go/ast/print.go b/src/pkg/go/ast/print.go new file mode 100644 index 000000000..62a30481d --- /dev/null +++ b/src/pkg/go/ast/print.go @@ -0,0 +1,224 @@ +// Copyright 2010 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. + +// This file contains printing suppport for ASTs. + +package ast + +import ( + "fmt" + "go/token" + "io" + "os" + "reflect" +) + +// A FieldFilter may be provided to Fprint to control the output. +type FieldFilter func(name string, value reflect.Value) bool + +// NotNilFilter returns true for field values that are not nil; +// it returns false otherwise. +func NotNilFilter(_ string, v reflect.Value) bool { + switch v.Kind() { + case reflect.Chan, reflect.Func, reflect.Interface, reflect.Map, reflect.Ptr, reflect.Slice: + return !v.IsNil() + } + return true +} + +// Fprint prints the (sub-)tree starting at AST node x to w. +// If fset != nil, position information is interpreted relative +// to that file set. Otherwise positions are printed as integer +// values (file set specific offsets). +// +// A non-nil FieldFilter f may be provided to control the output: +// struct fields for which f(fieldname, fieldvalue) is true are +// are printed; all others are filtered from the output. +// +func Fprint(w io.Writer, fset *token.FileSet, x interface{}, f FieldFilter) (n int, err os.Error) { + // setup printer + p := printer{ + output: w, + fset: fset, + filter: f, + ptrmap: make(map[interface{}]int), + last: '\n', // force printing of line number on first line + } + + // install error handler + defer func() { + n = p.written + if e := recover(); e != nil { + err = e.(localError).err // re-panics if it's not a localError + } + }() + + // print x + if x == nil { + p.printf("nil\n") + return + } + p.print(reflect.ValueOf(x)) + p.printf("\n") + + return +} + +// Print prints x to standard output, skipping nil fields. +// Print(fset, x) is the same as Fprint(os.Stdout, fset, x, NotNilFilter). +func Print(fset *token.FileSet, x interface{}) (int, os.Error) { + return Fprint(os.Stdout, fset, x, NotNilFilter) +} + +type printer struct { + output io.Writer + fset *token.FileSet + filter FieldFilter + ptrmap map[interface{}]int // *T -> line number + written int // number of bytes written to output + indent int // current indentation level + last byte // the last byte processed by Write + line int // current line number +} + +var indent = []byte(". ") + +func (p *printer) Write(data []byte) (n int, err os.Error) { + var m int + for i, b := range data { + // invariant: data[0:n] has been written + if b == '\n' { + m, err = p.output.Write(data[n : i+1]) + n += m + if err != nil { + return + } + p.line++ + } else if p.last == '\n' { + _, err = fmt.Fprintf(p.output, "%6d ", p.line) + if err != nil { + return + } + for j := p.indent; j > 0; j-- { + _, err = p.output.Write(indent) + if err != nil { + return + } + } + } + p.last = b + } + m, err = p.output.Write(data[n:]) + n += m + return +} + +// localError wraps locally caught os.Errors so we can distinguish +// them from genuine panics which we don't want to return as errors. +type localError struct { + err os.Error +} + +// printf is a convenience wrapper that takes care of print errors. +func (p *printer) printf(format string, args ...interface{}) { + n, err := fmt.Fprintf(p, format, args...) + p.written += n + if err != nil { + panic(localError{err}) + } +} + +// Implementation note: Print is written for AST nodes but could be +// used to print arbitrary data structures; such a version should +// probably be in a different package. +// +// Note: This code detects (some) cycles created via pointers but +// not cycles that are created via slices or maps containing the +// same slice or map. Code for general data structures probably +// should catch those as well. + +func (p *printer) print(x reflect.Value) { + if !NotNilFilter("", x) { + p.printf("nil") + return + } + + switch x.Kind() { + case reflect.Interface: + p.print(x.Elem()) + + case reflect.Map: + p.printf("%s (len = %d) {\n", x.Type().String(), x.Len()) + p.indent++ + for _, key := range x.MapKeys() { + p.print(key) + p.printf(": ") + p.print(x.MapIndex(key)) + p.printf("\n") + } + p.indent-- + p.printf("}") + + case reflect.Ptr: + p.printf("*") + // type-checked ASTs may contain cycles - use ptrmap + // to keep track of objects that have been printed + // already and print the respective line number instead + ptr := x.Interface() + if line, exists := p.ptrmap[ptr]; exists { + p.printf("(obj @ %d)", line) + } else { + p.ptrmap[ptr] = p.line + p.print(x.Elem()) + } + + case reflect.Slice: + if s, ok := x.Interface().([]byte); ok { + p.printf("%#q", s) + return + } + p.printf("%s (len = %d) {\n", x.Type().String(), x.Len()) + p.indent++ + for i, n := 0, x.Len(); i < n; i++ { + p.printf("%d: ", i) + p.print(x.Index(i)) + p.printf("\n") + } + p.indent-- + p.printf("}") + + case reflect.Struct: + p.printf("%s {\n", x.Type().String()) + p.indent++ + t := x.Type() + for i, n := 0, t.NumField(); i < n; i++ { + name := t.Field(i).Name + value := x.Field(i) + if p.filter == nil || p.filter(name, value) { + p.printf("%s: ", name) + p.print(value) + p.printf("\n") + } + } + p.indent-- + p.printf("}") + + default: + v := x.Interface() + switch v := v.(type) { + case string: + // print strings in quotes + p.printf("%q", v) + return + case token.Pos: + // position values can be printed nicely if we have a file set + if p.fset != nil { + p.printf("%s", p.fset.Position(v)) + return + } + } + // default + p.printf("%v", v) + } +} diff --git a/src/pkg/go/ast/print_test.go b/src/pkg/go/ast/print_test.go new file mode 100644 index 000000000..f4e8f7a78 --- /dev/null +++ b/src/pkg/go/ast/print_test.go @@ -0,0 +1,77 @@ +// Copyright 2011 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 ast + +import ( + "bytes" + "strings" + "testing" +) + +var tests = []struct { + x interface{} // x is printed as s + s string +}{ + // basic types + {nil, "0 nil"}, + {true, "0 true"}, + {42, "0 42"}, + {3.14, "0 3.14"}, + {1 + 2.718i, "0 (1+2.718i)"}, + {"foobar", "0 \"foobar\""}, + + // maps + {map[string]int{"a": 1, "b": 2}, + `0 map[string] int (len = 2) { + 1 . "a": 1 + 2 . "b": 2 + 3 }`}, + + // pointers + {new(int), "0 *0"}, + + // slices + {[]int{1, 2, 3}, + `0 []int (len = 3) { + 1 . 0: 1 + 2 . 1: 2 + 3 . 2: 3 + 4 }`}, + + // structs + {struct{ x, y int }{42, 991}, + `0 struct { x int; y int } { + 1 . x: 42 + 2 . y: 991 + 3 }`}, +} + +// Split s into lines, trim whitespace from all lines, and return +// the concatenated non-empty lines. +func trim(s string) string { + lines := strings.Split(s, "\n") + i := 0 + for _, line := range lines { + line = strings.TrimSpace(line) + if line != "" { + lines[i] = line + i++ + } + } + return strings.Join(lines[0:i], "\n") +} + +func TestPrint(t *testing.T) { + var buf bytes.Buffer + for _, test := range tests { + buf.Reset() + if _, err := Fprint(&buf, nil, test.x, nil); err != nil { + t.Errorf("Fprint failed: %s", err) + } + if s, ts := trim(buf.String()), trim(test.s); s != ts { + t.Errorf("got:\n%s\nexpected:\n%s\n", s, ts) + } + } +} diff --git a/src/pkg/go/ast/resolve.go b/src/pkg/go/ast/resolve.go new file mode 100644 index 000000000..3927a799e --- /dev/null +++ b/src/pkg/go/ast/resolve.go @@ -0,0 +1,174 @@ +// Copyright 2011 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. + +// This file implements NewPackage. + +package ast + +import ( + "fmt" + "go/scanner" + "go/token" + "os" + "strconv" +) + +type pkgBuilder struct { + scanner.ErrorVector + fset *token.FileSet +} + +func (p *pkgBuilder) error(pos token.Pos, msg string) { + p.Error(p.fset.Position(pos), msg) +} + +func (p *pkgBuilder) errorf(pos token.Pos, format string, args ...interface{}) { + p.error(pos, fmt.Sprintf(format, args...)) +} + +func (p *pkgBuilder) declare(scope, altScope *Scope, obj *Object) { + alt := scope.Insert(obj) + if alt == nil && altScope != nil { + // see if there is a conflicting declaration in altScope + alt = altScope.Lookup(obj.Name) + } + if alt != nil { + prevDecl := "" + if pos := alt.Pos(); pos.IsValid() { + prevDecl = fmt.Sprintf("\n\tprevious declaration at %s", p.fset.Position(pos)) + } + p.error(obj.Pos(), fmt.Sprintf("%s redeclared in this block%s", obj.Name, prevDecl)) + } +} + +func resolve(scope *Scope, ident *Ident) bool { + for ; scope != nil; scope = scope.Outer { + if obj := scope.Lookup(ident.Name); obj != nil { + ident.Obj = obj + return true + } + } + return false +} + +// An Importer resolves import paths to package Objects. +// The imports map records the packages already imported, +// indexed by package id (canonical import path). +// An Importer must determine the canonical import path and +// check the map to see if it is already present in the imports map. +// If so, the Importer can return the map entry. Otherwise, the +// Importer should load the package data for the given path into +// a new *Object (pkg), record pkg in the imports map, and then +// return pkg. +type Importer func(imports map[string]*Object, path string) (pkg *Object, err os.Error) + +// NewPackage creates a new Package node from a set of File nodes. It resolves +// unresolved identifiers across files and updates each file's Unresolved list +// accordingly. If a non-nil importer and universe scope are provided, they are +// used to resolve identifiers not declared in any of the package files. Any +// remaining unresolved identifiers are reported as undeclared. If the files +// belong to different packages, one package name is selected and files with +// different package names are reported and then ignored. +// The result is a package node and a scanner.ErrorList if there were errors. +// +func NewPackage(fset *token.FileSet, files map[string]*File, importer Importer, universe *Scope) (*Package, os.Error) { + var p pkgBuilder + p.fset = fset + + // complete package scope + pkgName := "" + pkgScope := NewScope(universe) + for _, file := range files { + // package names must match + switch name := file.Name.Name; { + case pkgName == "": + pkgName = name + case name != pkgName: + p.errorf(file.Package, "package %s; expected %s", name, pkgName) + continue // ignore this file + } + + // collect top-level file objects in package scope + for _, obj := range file.Scope.Objects { + p.declare(pkgScope, nil, obj) + } + } + + // package global mapping of imported package ids to package objects + imports := make(map[string]*Object) + + // complete file scopes with imports and resolve identifiers + for _, file := range files { + // ignore file if it belongs to a different package + // (error has already been reported) + if file.Name.Name != pkgName { + continue + } + + // build file scope by processing all imports + importErrors := false + fileScope := NewScope(pkgScope) + for _, spec := range file.Imports { + if importer == nil { + importErrors = true + continue + } + path, _ := strconv.Unquote(string(spec.Path.Value)) + pkg, err := importer(imports, path) + if err != nil { + p.errorf(spec.Path.Pos(), "could not import %s (%s)", path, err) + importErrors = true + continue + } + // TODO(gri) If a local package name != "." is provided, + // global identifier resolution could proceed even if the + // import failed. Consider adjusting the logic here a bit. + + // local name overrides imported package name + name := pkg.Name + if spec.Name != nil { + name = spec.Name.Name + } + + // add import to file scope + if name == "." { + // merge imported scope with file scope + for _, obj := range pkg.Data.(*Scope).Objects { + p.declare(fileScope, pkgScope, obj) + } + } else { + // declare imported package object in file scope + // (do not re-use pkg in the file scope but create + // a new object instead; the Decl field is different + // for different files) + obj := NewObj(Pkg, name) + obj.Decl = spec + obj.Data = pkg.Data + p.declare(fileScope, pkgScope, obj) + } + } + + // resolve identifiers + if importErrors { + // don't use the universe scope without correct imports + // (objects in the universe may be shadowed by imports; + // with missing imports, identifiers might get resolved + // incorrectly to universe objects) + pkgScope.Outer = nil + } + i := 0 + for _, ident := range file.Unresolved { + if !resolve(fileScope, ident) { + p.errorf(ident.Pos(), "undeclared name: %s", ident.Name) + file.Unresolved[i] = ident + i++ + } + + } + file.Unresolved = file.Unresolved[0:i] + pkgScope.Outer = universe // reset universe scope + } + + return &Package{pkgName, pkgScope, imports, files}, p.GetError(scanner.Sorted) +} diff --git a/src/pkg/go/ast/scope.go b/src/pkg/go/ast/scope.go new file mode 100644 index 000000000..92e366980 --- /dev/null +++ b/src/pkg/go/ast/scope.go @@ -0,0 +1,156 @@ +// 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. + +// This file implements scopes and the objects they contain. + +package ast + +import ( + "bytes" + "fmt" + "go/token" +) + +// A Scope maintains the set of named language entities declared +// in the scope and a link to the immediately surrounding (outer) +// scope. +// +type Scope struct { + Outer *Scope + Objects map[string]*Object +} + +// NewScope creates a new scope nested in the outer scope. +func NewScope(outer *Scope) *Scope { + const n = 4 // initial scope capacity + return &Scope{outer, make(map[string]*Object, n)} +} + +// Lookup returns the object with the given name if it is +// found in scope s, otherwise it returns nil. Outer scopes +// are ignored. +// +func (s *Scope) Lookup(name string) *Object { + return s.Objects[name] +} + +// Insert attempts to insert a named object obj into the scope s. +// If the scope already contains an object alt with the same name, +// Insert leaves the scope unchanged and returns alt. Otherwise +// it inserts obj and returns nil." +// +func (s *Scope) Insert(obj *Object) (alt *Object) { + if alt = s.Objects[obj.Name]; alt == nil { + s.Objects[obj.Name] = obj + } + return +} + +// Debugging support +func (s *Scope) String() string { + var buf bytes.Buffer + fmt.Fprintf(&buf, "scope %p {", s) + if s != nil && len(s.Objects) > 0 { + fmt.Fprintln(&buf) + for _, obj := range s.Objects { + fmt.Fprintf(&buf, "\t%s %s\n", obj.Kind, obj.Name) + } + } + fmt.Fprintf(&buf, "}\n") + return buf.String() +} + +// ---------------------------------------------------------------------------- +// Objects + +// TODO(gri) Consider replacing the Object struct with an interface +// and a corresponding set of object implementations. + +// An Object describes a named language entity such as a package, +// constant, type, variable, function (incl. methods), or label. +// +// The Data fields contains object-specific data: +// +// Kind Data type Data value +// Pkg *Scope package scope +// Con int iota for the respective declaration +// Con != nil constant value +// +type Object struct { + Kind ObjKind + Name string // declared name + Decl interface{} // corresponding Field, XxxSpec, FuncDecl, or LabeledStmt; or nil + Data interface{} // object-specific data; or nil + Type interface{} // place holder for type information; may be nil +} + +// NewObj creates a new object of a given kind and name. +func NewObj(kind ObjKind, name string) *Object { + return &Object{Kind: kind, Name: name} +} + +// Pos computes the source position of the declaration of an object name. +// The result may be an invalid position if it cannot be computed +// (obj.Decl may be nil or not correct). +func (obj *Object) Pos() token.Pos { + name := obj.Name + switch d := obj.Decl.(type) { + case *Field: + for _, n := range d.Names { + if n.Name == name { + return n.Pos() + } + } + case *ImportSpec: + if d.Name != nil && d.Name.Name == name { + return d.Name.Pos() + } + return d.Path.Pos() + case *ValueSpec: + for _, n := range d.Names { + if n.Name == name { + return n.Pos() + } + } + case *TypeSpec: + if d.Name.Name == name { + return d.Name.Pos() + } + case *FuncDecl: + if d.Name.Name == name { + return d.Name.Pos() + } + case *LabeledStmt: + if d.Label.Name == name { + return d.Label.Pos() + } + } + return token.NoPos +} + +// ObKind describes what an object represents. +type ObjKind int + +// The list of possible Object kinds. +const ( + Bad ObjKind = iota // for error handling + Pkg // package + Con // constant + Typ // type + Var // variable + Fun // function or method + Lbl // label +) + +var objKindStrings = [...]string{ + Bad: "bad", + Pkg: "package", + Con: "const", + Typ: "type", + Var: "var", + Fun: "func", + Lbl: "label", +} + +func (kind ObjKind) String() string { return objKindStrings[kind] } diff --git a/src/pkg/go/ast/walk.go b/src/pkg/go/ast/walk.go new file mode 100644 index 000000000..181cfd149 --- /dev/null +++ b/src/pkg/go/ast/walk.go @@ -0,0 +1,382 @@ +// 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 ast + +import "fmt" + +// A Visitor's Visit method is invoked for each node encountered by Walk. +// If the result visitor w is not nil, Walk visits each of the children +// of node with the visitor w, followed by a call of w.Visit(nil). +type Visitor interface { + Visit(node Node) (w Visitor) +} + +// Helper functions for common node lists. They may be empty. + +func walkIdentList(v Visitor, list []*Ident) { + for _, x := range list { + Walk(v, x) + } +} + +func walkExprList(v Visitor, list []Expr) { + for _, x := range list { + Walk(v, x) + } +} + +func walkStmtList(v Visitor, list []Stmt) { + for _, x := range list { + Walk(v, x) + } +} + +func walkDeclList(v Visitor, list []Decl) { + for _, x := range list { + Walk(v, x) + } +} + +// TODO(gri): Investigate if providing a closure to Walk leads to +// simpler use (and may help eliminate Inspect in turn). + +// Walk traverses an AST in depth-first order: It starts by calling +// v.Visit(node); node must not be nil. If the visitor w returned by +// v.Visit(node) is not nil, Walk is invoked recursively with visitor +// w for each of the non-nil children of node, followed by a call of +// w.Visit(nil). +// +func Walk(v Visitor, node Node) { + if v = v.Visit(node); v == nil { + return + } + + // walk children + // (the order of the cases matches the order + // of the corresponding node types in ast.go) + switch n := node.(type) { + // Comments and fields + case *Comment: + // nothing to do + + case *CommentGroup: + for _, c := range n.List { + Walk(v, c) + } + + case *Field: + if n.Doc != nil { + Walk(v, n.Doc) + } + walkIdentList(v, n.Names) + Walk(v, n.Type) + if n.Tag != nil { + Walk(v, n.Tag) + } + if n.Comment != nil { + Walk(v, n.Comment) + } + + case *FieldList: + for _, f := range n.List { + Walk(v, f) + } + + // Expressions + case *BadExpr, *Ident, *BasicLit: + // nothing to do + + case *Ellipsis: + if n.Elt != nil { + Walk(v, n.Elt) + } + + case *FuncLit: + Walk(v, n.Type) + Walk(v, n.Body) + + case *CompositeLit: + if n.Type != nil { + Walk(v, n.Type) + } + walkExprList(v, n.Elts) + + case *ParenExpr: + Walk(v, n.X) + + case *SelectorExpr: + Walk(v, n.X) + Walk(v, n.Sel) + + case *IndexExpr: + Walk(v, n.X) + Walk(v, n.Index) + + case *SliceExpr: + Walk(v, n.X) + if n.Low != nil { + Walk(v, n.Low) + } + if n.High != nil { + Walk(v, n.High) + } + + case *TypeAssertExpr: + Walk(v, n.X) + if n.Type != nil { + Walk(v, n.Type) + } + + case *CallExpr: + Walk(v, n.Fun) + walkExprList(v, n.Args) + + case *StarExpr: + Walk(v, n.X) + + case *UnaryExpr: + Walk(v, n.X) + + case *BinaryExpr: + Walk(v, n.X) + Walk(v, n.Y) + + case *KeyValueExpr: + Walk(v, n.Key) + Walk(v, n.Value) + + // Types + case *ArrayType: + if n.Len != nil { + Walk(v, n.Len) + } + Walk(v, n.Elt) + + case *StructType: + Walk(v, n.Fields) + + case *FuncType: + Walk(v, n.Params) + if n.Results != nil { + Walk(v, n.Results) + } + + case *InterfaceType: + Walk(v, n.Methods) + + case *MapType: + Walk(v, n.Key) + Walk(v, n.Value) + + case *ChanType: + Walk(v, n.Value) + + // Statements + case *BadStmt: + // nothing to do + + case *DeclStmt: + Walk(v, n.Decl) + + case *EmptyStmt: + // nothing to do + + case *LabeledStmt: + Walk(v, n.Label) + Walk(v, n.Stmt) + + case *ExprStmt: + Walk(v, n.X) + + case *SendStmt: + Walk(v, n.Chan) + Walk(v, n.Value) + + case *IncDecStmt: + Walk(v, n.X) + + case *AssignStmt: + walkExprList(v, n.Lhs) + walkExprList(v, n.Rhs) + + case *GoStmt: + Walk(v, n.Call) + + case *DeferStmt: + Walk(v, n.Call) + + case *ReturnStmt: + walkExprList(v, n.Results) + + case *BranchStmt: + if n.Label != nil { + Walk(v, n.Label) + } + + case *BlockStmt: + walkStmtList(v, n.List) + + case *IfStmt: + if n.Init != nil { + Walk(v, n.Init) + } + Walk(v, n.Cond) + Walk(v, n.Body) + if n.Else != nil { + Walk(v, n.Else) + } + + case *CaseClause: + walkExprList(v, n.List) + walkStmtList(v, n.Body) + + case *SwitchStmt: + if n.Init != nil { + Walk(v, n.Init) + } + if n.Tag != nil { + Walk(v, n.Tag) + } + Walk(v, n.Body) + + case *TypeSwitchStmt: + if n.Init != nil { + Walk(v, n.Init) + } + Walk(v, n.Assign) + Walk(v, n.Body) + + case *CommClause: + if n.Comm != nil { + Walk(v, n.Comm) + } + walkStmtList(v, n.Body) + + case *SelectStmt: + Walk(v, n.Body) + + case *ForStmt: + if n.Init != nil { + Walk(v, n.Init) + } + if n.Cond != nil { + Walk(v, n.Cond) + } + if n.Post != nil { + Walk(v, n.Post) + } + Walk(v, n.Body) + + case *RangeStmt: + Walk(v, n.Key) + if n.Value != nil { + Walk(v, n.Value) + } + Walk(v, n.X) + Walk(v, n.Body) + + // Declarations + case *ImportSpec: + if n.Doc != nil { + Walk(v, n.Doc) + } + if n.Name != nil { + Walk(v, n.Name) + } + Walk(v, n.Path) + if n.Comment != nil { + Walk(v, n.Comment) + } + + case *ValueSpec: + if n.Doc != nil { + Walk(v, n.Doc) + } + walkIdentList(v, n.Names) + if n.Type != nil { + Walk(v, n.Type) + } + walkExprList(v, n.Values) + if n.Comment != nil { + Walk(v, n.Comment) + } + + case *TypeSpec: + if n.Doc != nil { + Walk(v, n.Doc) + } + Walk(v, n.Name) + Walk(v, n.Type) + if n.Comment != nil { + Walk(v, n.Comment) + } + + case *BadDecl: + // nothing to do + + case *GenDecl: + if n.Doc != nil { + Walk(v, n.Doc) + } + for _, s := range n.Specs { + Walk(v, s) + } + + case *FuncDecl: + if n.Doc != nil { + Walk(v, n.Doc) + } + if n.Recv != nil { + Walk(v, n.Recv) + } + Walk(v, n.Name) + Walk(v, n.Type) + if n.Body != nil { + Walk(v, n.Body) + } + + // Files and packages + case *File: + if n.Doc != nil { + Walk(v, n.Doc) + } + Walk(v, n.Name) + walkDeclList(v, n.Decls) + for _, g := range n.Comments { + Walk(v, g) + } + // don't walk n.Comments - they have been + // visited already through the individual + // nodes + + case *Package: + for _, f := range n.Files { + Walk(v, f) + } + + default: + fmt.Printf("ast.Walk: unexpected node type %T", n) + panic("ast.Walk") + } + + v.Visit(nil) +} + +type inspector func(Node) bool + +func (f inspector) Visit(node Node) Visitor { + if f(node) { + return f + } + return nil +} + +// Inspect traverses an AST in depth-first order: It starts by calling +// f(node); node must not be nil. If f returns true, Inspect invokes f +// for all the non-nil children of node, recursively. +// +func Inspect(node Node, f func(Node) bool) { + Walk(inspector(f), node) +} |