diff options
Diffstat (limited to 'src/go/ast')
| -rw-r--r-- | src/go/ast/ast.go | 1063 | ||||
| -rw-r--r-- | src/go/ast/ast_test.go | 79 | ||||
| -rw-r--r-- | src/go/ast/commentmap.go | 332 | ||||
| -rw-r--r-- | src/go/ast/commentmap_test.go | 170 | ||||
| -rw-r--r-- | src/go/ast/example_test.go | 206 | ||||
| -rw-r--r-- | src/go/ast/filter.go | 497 | ||||
| -rw-r--r-- | src/go/ast/filter_test.go | 86 | ||||
| -rw-r--r-- | src/go/ast/import.go | 230 | ||||
| -rw-r--r-- | src/go/ast/issues_test.go | 42 | ||||
| -rw-r--r-- | src/go/ast/print.go | 254 | ||||
| -rw-r--r-- | src/go/ast/print_test.go | 97 | ||||
| -rw-r--r-- | src/go/ast/resolve.go | 174 | ||||
| -rw-r--r-- | src/go/ast/scope.go | 160 | ||||
| -rw-r--r-- | src/go/ast/walk.go | 386 |
14 files changed, 3776 insertions, 0 deletions
diff --git a/src/go/ast/ast.go b/src/go/ast/ast.go new file mode 100644 index 0000000..300966a --- /dev/null +++ b/src/go/ast/ast.go @@ -0,0 +1,1063 @@ +// 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" + "strings" +) + +// ---------------------------------------------------------------------------- +// 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. +// +// The Text field contains the comment text without carriage returns (\r) that +// may have been present in the source. Because a comment's end position is +// computed using len(Text), the position reported by End() does not match the +// true source end position for comments containing carriage returns. +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() } + +func isWhitespace(ch byte) bool { return ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r' } + +func stripTrailingWhitespace(s string) string { + i := len(s) + for i > 0 && isWhitespace(s[i-1]) { + i-- + } + return s[0:i] +} + +// Text returns the text of the comment. +// Comment markers (//, /*, and */), the first space of a line comment, and +// leading and trailing empty lines are removed. +// Comment directives like "//line" and "//go:noinline" are also removed. +// Multiple empty lines are reduced to one, and trailing space on lines is trimmed. +// Unless the result is empty, it is newline-terminated. +func (g *CommentGroup) Text() string { + if g == nil { + return "" + } + comments := make([]string, len(g.List)) + for i, c := range g.List { + comments[i] = c.Text + } + + lines := make([]string, 0, 10) // most comments are less than 10 lines + for _, c := range comments { + // Remove comment markers. + // The parser has given us exactly the comment text. + switch c[1] { + case '/': + //-style comment (no newline at the end) + c = c[2:] + if len(c) == 0 { + // empty line + break + } + if c[0] == ' ' { + // strip first space - required for Example tests + c = c[1:] + break + } + if isDirective(c) { + // Ignore //go:noinline, //line, and so on. + continue + } + case '*': + /*-style comment */ + c = c[2 : len(c)-2] + } + + // Split on newlines. + cl := strings.Split(c, "\n") + + // Walk lines, stripping trailing white space and adding to list. + for _, l := range cl { + lines = append(lines, stripTrailingWhitespace(l)) + } + } + + // Remove leading blank lines; convert runs of + // interior blank lines to a single blank line. + n := 0 + for _, line := range lines { + if line != "" || n > 0 && lines[n-1] != "" { + lines[n] = line + n++ + } + } + lines = lines[0:n] + + // Add final "" entry to get trailing newline from Join. + if n > 0 && lines[n-1] != "" { + lines = append(lines, "") + } + + return strings.Join(lines, "\n") +} + +// isDirective reports whether c is a comment directive. +func isDirective(c string) bool { + // "//line " is a line directive. + // (The // has been removed.) + if strings.HasPrefix(c, "line ") { + return true + } + + // "//[a-z0-9]+:[a-z0-9]" + // (The // has been removed.) + colon := strings.Index(c, ":") + if colon <= 0 || colon+1 >= len(c) { + return false + } + for i := 0; i <= colon+1; i++ { + if i == colon { + continue + } + b := c[i] + if !('a' <= b && b <= 'z' || '0' <= b && b <= '9') { + return false + } + } + return true +} + +// ---------------------------------------------------------------------------- +// 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. +// Field.Names is nil for unnamed parameters (parameter lists which only contain types) +// and embedded struct fields. In the latter case, the field name is the type name. +// +type Field struct { + Doc *CommentGroup // associated documentation; or nil + Names []*Ident // field/method/parameter names; or nil + 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 parameters or struct fields represented by 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 + } + 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 an expression containing + // syntax errors for which a correct expression node cannot 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. + // + // Note that for the CHAR and STRING kinds, the literal is stored + // with its quotes. For example, for a double-quoted STRING, the + // first and the last rune in the Value field will be ". The + // Unquote and UnquoteChar functions in the strconv package can be + // used to unquote STRING and CHAR values, respectively. + 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 "}" + Incomplete bool // true if (source) expressions are missing in the Elts list + } + + // 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 "]" + } + + // A 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 + Max Expr // maximum capacity of slice; or nil + Slice3 bool // true if 3-index slice (2 colons present) + Rbrack token.Pos // position of "]" + } + + // A TypeAssertExpr node represents an expression followed by a + // type assertion. + // + TypeAssertExpr struct { + X Expr // expression + Lparen token.Pos // position of "(" + Type Expr // asserted type; nil means type switch X.(type) + Rparen token.Pos // position of ")" + } + + // 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 "..." (token.NoPos if there is no "...") + 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 a bit +// mask including one or both 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 (token.NoPos if there is no "func") + Params *FieldList // (incoming) parameters; non-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) + Arrow token.Pos // position of "<-" (token.NoPos if there is no "<-") + 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 { + if x.Func.IsValid() || x.Params == nil { // see issue 3870 + return x.Func + } + return x.Params.Pos() // interface method declarations have no "func" keyword +} +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 { return x.Rparen + 1 } +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 Expr. +// +func (*BadExpr) exprNode() {} +func (*Ident) exprNode() {} +func (*Ellipsis) exprNode() {} +func (*BasicLit) exprNode() {} +func (*FuncLit) exprNode() {} +func (*CompositeLit) exprNode() {} +func (*ParenExpr) exprNode() {} +func (*SelectorExpr) exprNode() {} +func (*IndexExpr) exprNode() {} +func (*SliceExpr) exprNode() {} +func (*TypeAssertExpr) exprNode() {} +func (*CallExpr) exprNode() {} +func (*StarExpr) exprNode() {} +func (*UnaryExpr) exprNode() {} +func (*BinaryExpr) exprNode() {} +func (*KeyValueExpr) exprNode() {} + +func (*ArrayType) exprNode() {} +func (*StructType) exprNode() {} +func (*FuncType) exprNode() {} +func (*InterfaceType) exprNode() {} +func (*MapType) exprNode() {} +func (*ChanType) exprNode() {} + +// ---------------------------------------------------------------------------- +// Convenience functions for Idents + +// 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{token.NoPos, name, nil} } + +// IsExported reports whether name starts with an upper-case letter. +// +func IsExported(name string) bool { return token.IsExported(name) } + +// IsExported reports whether id starts with an upper-case letter. +// +func (id *Ident) IsExported() bool { return token.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 // *GenDecl with CONST, TYPE, or VAR token + } + + // An EmptyStmt node represents an empty statement. + // The "position" of the empty statement is the position + // of the immediately following (explicit or implicit) semicolon. + // + EmptyStmt struct { + Semicolon token.Pos // position of following ";" + Implicit bool // if set, ";" was omitted in the source + } + + // 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 "}", if any (may be absent due to syntax error) + } + + // 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 + } + + // A 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 + } + + // A 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 // Key, Value may be nil + TokPos token.Pos // position of Tok; invalid if Key == nil + Tok token.Token // ILLEGAL if Key == nil, 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 { + if s.Implicit { + return s.Semicolon + } + 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 { + if s.Rbrace.IsValid() { + return s.Rbrace + 1 + } + if n := len(s.List); n > 0 { + return s.List[n-1].End() + } + return s.Lbrace + 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 Stmt. +// +func (*BadStmt) stmtNode() {} +func (*DeclStmt) stmtNode() {} +func (*EmptyStmt) stmtNode() {} +func (*LabeledStmt) stmtNode() {} +func (*ExprStmt) stmtNode() {} +func (*SendStmt) stmtNode() {} +func (*IncDecStmt) stmtNode() {} +func (*AssignStmt) stmtNode() {} +func (*GoStmt) stmtNode() {} +func (*DeferStmt) stmtNode() {} +func (*ReturnStmt) stmtNode() {} +func (*BranchStmt) stmtNode() {} +func (*BlockStmt) stmtNode() {} +func (*IfStmt) stmtNode() {} +func (*CaseClause) stmtNode() {} +func (*SwitchStmt) stmtNode() {} +func (*TypeSwitchStmt) stmtNode() {} +func (*CommClause) stmtNode() {} +func (*SelectStmt) stmtNode() {} +func (*ForStmt) stmtNode() {} +func (*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 + EndPos token.Pos // end of spec (overrides Path.Pos if nonzero) + } + + // 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 + Assign token.Pos // position of '=', if any + 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 { + if s.EndPos != 0 { + return s.EndPos + } + 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 (*ImportSpec) specNode() {} +func (*ValueSpec) specNode() {} +func (*TypeSpec) specNode() {} + +// A declaration is represented by one of the following declaration nodes. +// +type ( + // A BadDecl node is a placeholder for a declaration containing + // syntax errors for which a correct declaration node cannot 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.IsValid()) 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 // function signature: parameters, results, and position of "func" keyword + Body *BlockStmt // function body; or nil for external (non-Go) function + } +) + +// 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 Decl. +// +func (*BadDecl) declNode() {} +func (*GenDecl) declNode() {} +func (*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. +// +// For correct printing of source code containing comments (using packages +// go/format and go/printer), special care must be taken to update comments +// when a File's syntax tree is modified: For printing, comments are interspersed +// between tokens based on their position. If syntax tree nodes are +// removed or moved, relevant comments in their vicinity must also be removed +// (from the File.Comments list) or moved accordingly (by updating their +// positions). A CommentMap may be used to facilitate some of these operations. +// +// Whether and how a comment is associated with a node depends on the +// interpretation of the syntax tree by the manipulating program: Except for Doc +// and Comment comments directly associated with nodes, the remaining comments +// are "free-floating" (see also issues #18593, #20744). +// +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/go/ast/ast_test.go b/src/go/ast/ast_test.go new file mode 100644 index 0000000..71b2d6c --- /dev/null +++ b/src/go/ast/ast_test.go @@ -0,0 +1,79 @@ +// Copyright 2012 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 ( + "testing" +) + +var comments = []struct { + list []string + text string +}{ + {[]string{"//"}, ""}, + {[]string{"// "}, ""}, + {[]string{"//", "//", "// "}, ""}, + {[]string{"// foo "}, "foo\n"}, + {[]string{"//", "//", "// foo"}, "foo\n"}, + {[]string{"// foo bar "}, "foo bar\n"}, + {[]string{"// foo", "// bar"}, "foo\nbar\n"}, + {[]string{"// foo", "//", "//", "//", "// bar"}, "foo\n\nbar\n"}, + {[]string{"// foo", "/* bar */"}, "foo\n bar\n"}, + {[]string{"//", "//", "//", "// foo", "//", "//", "//"}, "foo\n"}, + + {[]string{"/**/"}, ""}, + {[]string{"/* */"}, ""}, + {[]string{"/**/", "/**/", "/* */"}, ""}, + {[]string{"/* Foo */"}, " Foo\n"}, + {[]string{"/* Foo Bar */"}, " Foo Bar\n"}, + {[]string{"/* Foo*/", "/* Bar*/"}, " Foo\n Bar\n"}, + {[]string{"/* Foo*/", "/**/", "/**/", "/**/", "// Bar"}, " Foo\n\nBar\n"}, + {[]string{"/* Foo*/", "/*\n*/", "//", "/*\n*/", "// Bar"}, " Foo\n\nBar\n"}, + {[]string{"/* Foo*/", "// Bar"}, " Foo\nBar\n"}, + {[]string{"/* Foo\n Bar*/"}, " Foo\n Bar\n"}, + + {[]string{"// foo", "//go:noinline", "// bar", "//:baz"}, "foo\nbar\n:baz\n"}, + {[]string{"// foo", "//lint123:ignore", "// bar"}, "foo\nbar\n"}, +} + +func TestCommentText(t *testing.T) { + for i, c := range comments { + list := make([]*Comment, len(c.list)) + for i, s := range c.list { + list[i] = &Comment{Text: s} + } + + text := (&CommentGroup{list}).Text() + if text != c.text { + t.Errorf("case %d: got %q; expected %q", i, text, c.text) + } + } +} + +var isDirectiveTests = []struct { + in string + ok bool +}{ + {"abc", false}, + {"go:inline", true}, + {"Go:inline", false}, + {"go:Inline", false}, + {":inline", false}, + {"lint:ignore", true}, + {"lint:1234", true}, + {"1234:lint", true}, + {"go: inline", false}, + {"go:", false}, + {"go:*", false}, + {"go:x*", true}, +} + +func TestIsDirective(t *testing.T) { + for _, tt := range isDirectiveTests { + if ok := isDirective(tt.in); ok != tt.ok { + t.Errorf("isDirective(%q) = %v, want %v", tt.in, ok, tt.ok) + } + } +} diff --git a/src/go/ast/commentmap.go b/src/go/ast/commentmap.go new file mode 100644 index 0000000..2a653a6 --- /dev/null +++ b/src/go/ast/commentmap.go @@ -0,0 +1,332 @@ +// Copyright 2012 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" + "fmt" + "go/token" + "sort" +) + +type byPos []*CommentGroup + +func (a byPos) Len() int { return len(a) } +func (a byPos) Less(i, j int) bool { return a[i].Pos() < a[j].Pos() } +func (a byPos) Swap(i, j int) { a[i], a[j] = a[j], a[i] } + +// sortComments sorts the list of comment groups in source order. +// +func sortComments(list []*CommentGroup) { + // TODO(gri): Does it make sense to check for sorted-ness + // first (because we know that sorted-ness is + // very likely)? + if orderedList := byPos(list); !sort.IsSorted(orderedList) { + sort.Sort(orderedList) + } +} + +// A CommentMap maps an AST node to a list of comment groups +// associated with it. See NewCommentMap for a description of +// the association. +// +type CommentMap map[Node][]*CommentGroup + +func (cmap CommentMap) addComment(n Node, c *CommentGroup) { + list := cmap[n] + if len(list) == 0 { + list = []*CommentGroup{c} + } else { + list = append(list, c) + } + cmap[n] = list +} + +type byInterval []Node + +func (a byInterval) Len() int { return len(a) } +func (a byInterval) Less(i, j int) bool { + pi, pj := a[i].Pos(), a[j].Pos() + return pi < pj || pi == pj && a[i].End() > a[j].End() +} +func (a byInterval) Swap(i, j int) { a[i], a[j] = a[j], a[i] } + +// nodeList returns the list of nodes of the AST n in source order. +// +func nodeList(n Node) []Node { + var list []Node + Inspect(n, func(n Node) bool { + // don't collect comments + switch n.(type) { + case nil, *CommentGroup, *Comment: + return false + } + list = append(list, n) + return true + }) + // Note: The current implementation assumes that Inspect traverses the + // AST in depth-first and thus _source_ order. If AST traversal + // does not follow source order, the sorting call below will be + // required. + // sort.Sort(byInterval(list)) + return list +} + +// A commentListReader helps iterating through a list of comment groups. +// +type commentListReader struct { + fset *token.FileSet + list []*CommentGroup + index int + comment *CommentGroup // comment group at current index + pos, end token.Position // source interval of comment group at current index +} + +func (r *commentListReader) eol() bool { + return r.index >= len(r.list) +} + +func (r *commentListReader) next() { + if !r.eol() { + r.comment = r.list[r.index] + r.pos = r.fset.Position(r.comment.Pos()) + r.end = r.fset.Position(r.comment.End()) + r.index++ + } +} + +// A nodeStack keeps track of nested nodes. +// A node lower on the stack lexically contains the nodes higher on the stack. +// +type nodeStack []Node + +// push pops all nodes that appear lexically before n +// and then pushes n on the stack. +// +func (s *nodeStack) push(n Node) { + s.pop(n.Pos()) + *s = append((*s), n) +} + +// pop pops all nodes that appear lexically before pos +// (i.e., whose lexical extent has ended before or at pos). +// It returns the last node popped. +// +func (s *nodeStack) pop(pos token.Pos) (top Node) { + i := len(*s) + for i > 0 && (*s)[i-1].End() <= pos { + top = (*s)[i-1] + i-- + } + *s = (*s)[0:i] + return top +} + +// NewCommentMap creates a new comment map by associating comment groups +// of the comments list with the nodes of the AST specified by node. +// +// A comment group g is associated with a node n if: +// +// - g starts on the same line as n ends +// - g starts on the line immediately following n, and there is +// at least one empty line after g and before the next node +// - g starts before n and is not associated to the node before n +// via the previous rules +// +// NewCommentMap tries to associate a comment group to the "largest" +// node possible: For instance, if the comment is a line comment +// trailing an assignment, the comment is associated with the entire +// assignment rather than just the last operand in the assignment. +// +func NewCommentMap(fset *token.FileSet, node Node, comments []*CommentGroup) CommentMap { + if len(comments) == 0 { + return nil // no comments to map + } + + cmap := make(CommentMap) + + // set up comment reader r + tmp := make([]*CommentGroup, len(comments)) + copy(tmp, comments) // don't change incoming comments + sortComments(tmp) + r := commentListReader{fset: fset, list: tmp} // !r.eol() because len(comments) > 0 + r.next() + + // create node list in lexical order + nodes := nodeList(node) + nodes = append(nodes, nil) // append sentinel + + // set up iteration variables + var ( + p Node // previous node + pend token.Position // end of p + pg Node // previous node group (enclosing nodes of "importance") + pgend token.Position // end of pg + stack nodeStack // stack of node groups + ) + + for _, q := range nodes { + var qpos token.Position + if q != nil { + qpos = fset.Position(q.Pos()) // current node position + } else { + // set fake sentinel position to infinity so that + // all comments get processed before the sentinel + const infinity = 1 << 30 + qpos.Offset = infinity + qpos.Line = infinity + } + + // process comments before current node + for r.end.Offset <= qpos.Offset { + // determine recent node group + if top := stack.pop(r.comment.Pos()); top != nil { + pg = top + pgend = fset.Position(pg.End()) + } + // Try to associate a comment first with a node group + // (i.e., a node of "importance" such as a declaration); + // if that fails, try to associate it with the most recent + // node. + // TODO(gri) try to simplify the logic below + var assoc Node + switch { + case pg != nil && + (pgend.Line == r.pos.Line || + pgend.Line+1 == r.pos.Line && r.end.Line+1 < qpos.Line): + // 1) comment starts on same line as previous node group ends, or + // 2) comment starts on the line immediately after the + // previous node group and there is an empty line before + // the current node + // => associate comment with previous node group + assoc = pg + case p != nil && + (pend.Line == r.pos.Line || + pend.Line+1 == r.pos.Line && r.end.Line+1 < qpos.Line || + q == nil): + // same rules apply as above for p rather than pg, + // but also associate with p if we are at the end (q == nil) + assoc = p + default: + // otherwise, associate comment with current node + if q == nil { + // we can only reach here if there was no p + // which would imply that there were no nodes + panic("internal error: no comments should be associated with sentinel") + } + assoc = q + } + cmap.addComment(assoc, r.comment) + if r.eol() { + return cmap + } + r.next() + } + + // update previous node + p = q + pend = fset.Position(p.End()) + + // update previous node group if we see an "important" node + switch q.(type) { + case *File, *Field, Decl, Spec, Stmt: + stack.push(q) + } + } + + return cmap +} + +// Update replaces an old node in the comment map with the new node +// and returns the new node. Comments that were associated with the +// old node are associated with the new node. +// +func (cmap CommentMap) Update(old, new Node) Node { + if list := cmap[old]; len(list) > 0 { + delete(cmap, old) + cmap[new] = append(cmap[new], list...) + } + return new +} + +// Filter returns a new comment map consisting of only those +// entries of cmap for which a corresponding node exists in +// the AST specified by node. +// +func (cmap CommentMap) Filter(node Node) CommentMap { + umap := make(CommentMap) + Inspect(node, func(n Node) bool { + if g := cmap[n]; len(g) > 0 { + umap[n] = g + } + return true + }) + return umap +} + +// Comments returns the list of comment groups in the comment map. +// The result is sorted in source order. +// +func (cmap CommentMap) Comments() []*CommentGroup { + list := make([]*CommentGroup, 0, len(cmap)) + for _, e := range cmap { + list = append(list, e...) + } + sortComments(list) + return list +} + +func summary(list []*CommentGroup) string { + const maxLen = 40 + var buf bytes.Buffer + + // collect comments text +loop: + for _, group := range list { + // Note: CommentGroup.Text() does too much work for what we + // need and would only replace this innermost loop. + // Just do it explicitly. + for _, comment := range group.List { + if buf.Len() >= maxLen { + break loop + } + buf.WriteString(comment.Text) + } + } + + // truncate if too long + if buf.Len() > maxLen { + buf.Truncate(maxLen - 3) + buf.WriteString("...") + } + + // replace any invisibles with blanks + bytes := buf.Bytes() + for i, b := range bytes { + switch b { + case '\t', '\n', '\r': + bytes[i] = ' ' + } + } + + return string(bytes) +} + +func (cmap CommentMap) String() string { + var buf bytes.Buffer + fmt.Fprintln(&buf, "CommentMap {") + for node, comment := range cmap { + // print name of identifiers; print node type for other nodes + var s string + if ident, ok := node.(*Ident); ok { + s = ident.Name + } else { + s = fmt.Sprintf("%T", node) + } + fmt.Fprintf(&buf, "\t%p %20s: %s\n", node, s, summary(comment)) + } + fmt.Fprintln(&buf, "}") + return buf.String() +} diff --git a/src/go/ast/commentmap_test.go b/src/go/ast/commentmap_test.go new file mode 100644 index 0000000..38c62b0 --- /dev/null +++ b/src/go/ast/commentmap_test.go @@ -0,0 +1,170 @@ +// Copyright 2012 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. + +// To avoid a cyclic dependency with go/parser, this file is in a separate package. + +package ast_test + +import ( + "bytes" + "fmt" + . "go/ast" + "go/parser" + "go/token" + "sort" + "testing" +) + +const src = ` +// the very first comment + +// package p +package p /* the name is p */ + +// imports +import ( + "bytes" // bytes + "fmt" // fmt + "go/ast" + "go/parser" +) + +// T +type T struct { + a, b, c int // associated with a, b, c + // associated with x, y + x, y float64 // float values + z complex128 // complex value +} +// also associated with T + +// x +var x = 0 // x = 0 +// also associated with x + +// f1 +func f1() { + /* associated with s1 */ + s1() + // also associated with s1 + + // associated with s2 + + // also associated with s2 + s2() // line comment for s2 +} +// associated with f1 +// also associated with f1 + +// associated with f2 + +// f2 +func f2() { +} + +func f3() { + i := 1 /* 1 */ + 2 // addition + _ = i +} + +// the very last comment +` + +// res maps a key of the form "line number: node type" +// to the associated comments' text. +// +var res = map[string]string{ + " 5: *ast.File": "the very first comment\npackage p\n", + " 5: *ast.Ident": " the name is p\n", + " 8: *ast.GenDecl": "imports\n", + " 9: *ast.ImportSpec": "bytes\n", + "10: *ast.ImportSpec": "fmt\n", + "16: *ast.GenDecl": "T\nalso associated with T\n", + "17: *ast.Field": "associated with a, b, c\n", + "19: *ast.Field": "associated with x, y\nfloat values\n", + "20: *ast.Field": "complex value\n", + "25: *ast.GenDecl": "x\nx = 0\nalso associated with x\n", + "29: *ast.FuncDecl": "f1\nassociated with f1\nalso associated with f1\n", + "31: *ast.ExprStmt": " associated with s1\nalso associated with s1\n", + "37: *ast.ExprStmt": "associated with s2\nalso associated with s2\nline comment for s2\n", + "45: *ast.FuncDecl": "associated with f2\nf2\n", + "49: *ast.AssignStmt": "addition\n", + "49: *ast.BasicLit": " 1\n", + "50: *ast.Ident": "the very last comment\n", +} + +func ctext(list []*CommentGroup) string { + var buf bytes.Buffer + for _, g := range list { + buf.WriteString(g.Text()) + } + return buf.String() +} + +func TestCommentMap(t *testing.T) { + fset := token.NewFileSet() + f, err := parser.ParseFile(fset, "", src, parser.ParseComments) + if err != nil { + t.Fatal(err) + } + cmap := NewCommentMap(fset, f, f.Comments) + + // very correct association of comments + for n, list := range cmap { + key := fmt.Sprintf("%2d: %T", fset.Position(n.Pos()).Line, n) + got := ctext(list) + want := res[key] + if got != want { + t.Errorf("%s: got %q; want %q", key, got, want) + } + } + + // verify that no comments got lost + if n := len(cmap.Comments()); n != len(f.Comments) { + t.Errorf("got %d comment groups in map; want %d", n, len(f.Comments)) + } + + // support code to update test: + // set genMap to true to generate res map + const genMap = false + if genMap { + out := make([]string, 0, len(cmap)) + for n, list := range cmap { + out = append(out, fmt.Sprintf("\t\"%2d: %T\":\t%q,", fset.Position(n.Pos()).Line, n, ctext(list))) + } + sort.Strings(out) + for _, s := range out { + fmt.Println(s) + } + } +} + +func TestFilter(t *testing.T) { + fset := token.NewFileSet() + f, err := parser.ParseFile(fset, "", src, parser.ParseComments) + if err != nil { + t.Fatal(err) + } + cmap := NewCommentMap(fset, f, f.Comments) + + // delete variable declaration + for i, decl := range f.Decls { + if gen, ok := decl.(*GenDecl); ok && gen.Tok == token.VAR { + copy(f.Decls[i:], f.Decls[i+1:]) + f.Decls = f.Decls[:len(f.Decls)-1] + break + } + } + + // check if comments are filtered correctly + cc := cmap.Filter(f) + for n, list := range cc { + key := fmt.Sprintf("%2d: %T", fset.Position(n.Pos()).Line, n) + got := ctext(list) + want := res[key] + if key == "25: *ast.GenDecl" || got != want { + t.Errorf("%s: got %q; want %q", key, got, want) + } + } +} diff --git a/src/go/ast/example_test.go b/src/go/ast/example_test.go new file mode 100644 index 0000000..e3013f6 --- /dev/null +++ b/src/go/ast/example_test.go @@ -0,0 +1,206 @@ +// Copyright 2012 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_test + +import ( + "bytes" + "fmt" + "go/ast" + "go/format" + "go/parser" + "go/token" +) + +// This example demonstrates how to inspect the AST of a Go program. +func ExampleInspect() { + // src is the input for which we want to inspect the AST. + src := ` +package p +const c = 1.0 +var X = f(3.14)*2 + c +` + + // Create the AST by parsing src. + fset := token.NewFileSet() // positions are relative to fset + f, err := parser.ParseFile(fset, "src.go", src, 0) + if err != nil { + panic(err) + } + + // Inspect the AST and print all identifiers and literals. + ast.Inspect(f, func(n ast.Node) bool { + var s string + switch x := n.(type) { + case *ast.BasicLit: + s = x.Value + case *ast.Ident: + s = x.Name + } + if s != "" { + fmt.Printf("%s:\t%s\n", fset.Position(n.Pos()), s) + } + return true + }) + + // Output: + // src.go:2:9: p + // src.go:3:7: c + // src.go:3:11: 1.0 + // src.go:4:5: X + // src.go:4:9: f + // src.go:4:11: 3.14 + // src.go:4:17: 2 + // src.go:4:21: c +} + +// This example shows what an AST looks like when printed for debugging. +func ExamplePrint() { + // src is the input for which we want to print the AST. + src := ` +package main +func main() { + println("Hello, World!") +} +` + + // Create the AST by parsing src. + fset := token.NewFileSet() // positions are relative to fset + f, err := parser.ParseFile(fset, "", src, 0) + if err != nil { + panic(err) + } + + // Print the AST. + ast.Print(fset, f) + + // Output: + // 0 *ast.File { + // 1 . Package: 2:1 + // 2 . Name: *ast.Ident { + // 3 . . NamePos: 2:9 + // 4 . . Name: "main" + // 5 . } + // 6 . Decls: []ast.Decl (len = 1) { + // 7 . . 0: *ast.FuncDecl { + // 8 . . . Name: *ast.Ident { + // 9 . . . . NamePos: 3:6 + // 10 . . . . Name: "main" + // 11 . . . . Obj: *ast.Object { + // 12 . . . . . Kind: func + // 13 . . . . . Name: "main" + // 14 . . . . . Decl: *(obj @ 7) + // 15 . . . . } + // 16 . . . } + // 17 . . . Type: *ast.FuncType { + // 18 . . . . Func: 3:1 + // 19 . . . . Params: *ast.FieldList { + // 20 . . . . . Opening: 3:10 + // 21 . . . . . Closing: 3:11 + // 22 . . . . } + // 23 . . . } + // 24 . . . Body: *ast.BlockStmt { + // 25 . . . . Lbrace: 3:13 + // 26 . . . . List: []ast.Stmt (len = 1) { + // 27 . . . . . 0: *ast.ExprStmt { + // 28 . . . . . . X: *ast.CallExpr { + // 29 . . . . . . . Fun: *ast.Ident { + // 30 . . . . . . . . NamePos: 4:2 + // 31 . . . . . . . . Name: "println" + // 32 . . . . . . . } + // 33 . . . . . . . Lparen: 4:9 + // 34 . . . . . . . Args: []ast.Expr (len = 1) { + // 35 . . . . . . . . 0: *ast.BasicLit { + // 36 . . . . . . . . . ValuePos: 4:10 + // 37 . . . . . . . . . Kind: STRING + // 38 . . . . . . . . . Value: "\"Hello, World!\"" + // 39 . . . . . . . . } + // 40 . . . . . . . } + // 41 . . . . . . . Ellipsis: - + // 42 . . . . . . . Rparen: 4:25 + // 43 . . . . . . } + // 44 . . . . . } + // 45 . . . . } + // 46 . . . . Rbrace: 5:1 + // 47 . . . } + // 48 . . } + // 49 . } + // 50 . Scope: *ast.Scope { + // 51 . . Objects: map[string]*ast.Object (len = 1) { + // 52 . . . "main": *(obj @ 11) + // 53 . . } + // 54 . } + // 55 . Unresolved: []*ast.Ident (len = 1) { + // 56 . . 0: *(obj @ 29) + // 57 . } + // 58 } +} + +// This example illustrates how to remove a variable declaration +// in a Go program while maintaining correct comment association +// using an ast.CommentMap. +func ExampleCommentMap() { + // src is the input for which we create the AST that we + // are going to manipulate. + src := ` +// This is the package comment. +package main + +// This comment is associated with the hello constant. +const hello = "Hello, World!" // line comment 1 + +// This comment is associated with the foo variable. +var foo = hello // line comment 2 + +// This comment is associated with the main function. +func main() { + fmt.Println(hello) // line comment 3 +} +` + + // Create the AST by parsing src. + fset := token.NewFileSet() // positions are relative to fset + f, err := parser.ParseFile(fset, "src.go", src, parser.ParseComments) + if err != nil { + panic(err) + } + + // Create an ast.CommentMap from the ast.File's comments. + // This helps keeping the association between comments + // and AST nodes. + cmap := ast.NewCommentMap(fset, f, f.Comments) + + // Remove the first variable declaration from the list of declarations. + for i, decl := range f.Decls { + if gen, ok := decl.(*ast.GenDecl); ok && gen.Tok == token.VAR { + copy(f.Decls[i:], f.Decls[i+1:]) + f.Decls = f.Decls[:len(f.Decls)-1] + break + } + } + + // Use the comment map to filter comments that don't belong anymore + // (the comments associated with the variable declaration), and create + // the new comments list. + f.Comments = cmap.Filter(f).Comments() + + // Print the modified AST. + var buf bytes.Buffer + if err := format.Node(&buf, fset, f); err != nil { + panic(err) + } + fmt.Printf("%s", buf.Bytes()) + + // Output: + // // This is the package comment. + // package main + // + // // This comment is associated with the hello constant. + // const hello = "Hello, World!" // line comment 1 + // + // // This comment is associated with the main function. + // func main() { + // fmt.Println(hello) // line comment 3 + // } +} diff --git a/src/go/ast/filter.go b/src/go/ast/filter.go new file mode 100644 index 0000000..c398e6e --- /dev/null +++ b/src/go/ast/filter.go @@ -0,0 +1,497 @@ +// 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" + "sort" +) + +// ---------------------------------------------------------------------------- +// Export filtering + +// exportFilter is a special filter function to extract exported nodes. +func exportFilter(name string) bool { + return IsExported(name) +} + +// 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. The File.Comments list is not changed. +// +// FileExports reports whether there are exported declarations. +// +func FileExports(src *File) bool { + return filterFile(src, exportFilter, true) +} + +// 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 reports whether there are exported declarations; +// it returns false otherwise. +// +func PackageExports(pkg *Package) bool { + return filterPackage(pkg, exportFilter, true) +} + +// ---------------------------------------------------------------------------- +// 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] +} + +// 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 filterFieldList(fields *FieldList, filter Filter, export bool) (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 { + if export { + filterType(f.Type, filter, export) + } + list[j] = f + j++ + } + } + if j < len(list) { + removedFields = true + } + fields.List = list[0:j] + return +} + +func filterCompositeLit(lit *CompositeLit, filter Filter, export bool) { + n := len(lit.Elts) + lit.Elts = filterExprList(lit.Elts, filter, export) + if len(lit.Elts) < n { + lit.Incomplete = true + } +} + +func filterExprList(list []Expr, filter Filter, export bool) []Expr { + j := 0 + for _, exp := range list { + switch x := exp.(type) { + case *CompositeLit: + filterCompositeLit(x, filter, export) + case *KeyValueExpr: + if x, ok := x.Key.(*Ident); ok && !filter(x.Name) { + continue + } + if x, ok := x.Value.(*CompositeLit); ok { + filterCompositeLit(x, filter, export) + } + } + list[j] = exp + j++ + } + return list[0:j] +} + +func filterParamList(fields *FieldList, filter Filter, export bool) bool { + if fields == nil { + return false + } + var b bool + for _, f := range fields.List { + if filterType(f.Type, filter, export) { + b = true + } + } + return b +} + +func filterType(typ Expr, f Filter, export bool) bool { + switch t := typ.(type) { + case *Ident: + return f(t.Name) + case *ParenExpr: + return filterType(t.X, f, export) + case *ArrayType: + return filterType(t.Elt, f, export) + case *StructType: + if filterFieldList(t.Fields, f, export) { + t.Incomplete = true + } + return len(t.Fields.List) > 0 + case *FuncType: + b1 := filterParamList(t.Params, f, export) + b2 := filterParamList(t.Results, f, export) + return b1 || b2 + case *InterfaceType: + if filterFieldList(t.Methods, f, export) { + t.Incomplete = true + } + return len(t.Methods.List) > 0 + case *MapType: + b1 := filterType(t.Key, f, export) + b2 := filterType(t.Value, f, export) + return b1 || b2 + case *ChanType: + return filterType(t.Value, f, export) + } + return false +} + +func filterSpec(spec Spec, f Filter, export bool) bool { + switch s := spec.(type) { + case *ValueSpec: + s.Names = filterIdentList(s.Names, f) + s.Values = filterExprList(s.Values, f, export) + if len(s.Names) > 0 { + if export { + filterType(s.Type, f, export) + } + return true + } + case *TypeSpec: + if f(s.Name.Name) { + if export { + filterType(s.Type, f, export) + } + return true + } + if !export { + // For general filtering (not just exports), + // filter type even if name is not filtered + // out. + // If the type contains filtered elements, + // keep the declaration. + return filterType(s.Type, f, export) + } + } + return false +} + +func filterSpecList(list []Spec, f Filter, export bool) []Spec { + j := 0 + for _, s := range list { + if filterSpec(s, f, export) { + 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 reports whether there are any declared names left after +// filtering. +// +func FilterDecl(decl Decl, f Filter) bool { + return filterDecl(decl, f, false) +} + +func filterDecl(decl Decl, f Filter, export bool) bool { + switch d := decl.(type) { + case *GenDecl: + d.Specs = filterSpecList(d.Specs, f, export) + 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. Import declarations are +// always removed. The File.Comments list is not changed. +// +// FilterFile reports whether there are any top-level declarations +// left after filtering. +// +func FilterFile(src *File, f Filter) bool { + return filterFile(src, f, false) +} + +func filterFile(src *File, f Filter, export bool) bool { + j := 0 + for _, d := range src.Decls { + if filterDecl(d, f, export) { + 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 reports whether there are any top-level declarations +// left after filtering. +// +func FilterPackage(pkg *Package, f Filter) bool { + return filterPackage(pkg, f, false) +} + +func filterPackage(pkg *Package, f Filter, export bool) bool { + hasDecls := false + for _, src := range pkg.Files { + if filterFile(src, f, export) { + 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 + // If set, duplicate import declarations are excluded. + FilterImportDuplicates +) + +// nameOf returns the function (foo) or method name (foo.bar) for +// the given function declaration. If the AST is incorrect for the +// receiver, it assumes a function instead. +// +func nameOf(f *FuncDecl) string { + if r := f.Recv; r != nil && len(r.List) == 1 { + // looks like a correct receiver declaration + t := r.List[0].Type + // dereference pointer receiver types + if p, _ := t.(*StarExpr); p != nil { + t = p.X + } + // the receiver type must be a type name + if p, _ := t.(*Ident); p != nil { + return p.Name + "." + f.Name.Name + } + // otherwise assume a function instead + } + return f.Name.Name +} + +// separator is an empty //-style comment that is interspersed between +// different comment groups when they are concatenated into a single group +// +var separator = &Comment{token.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. Also, compute sorted list of filenames, so that + // subsequent iterations can always iterate in the same order. + ndocs := 0 + ncomments := 0 + ndecls := 0 + filenames := make([]string, len(pkg.Files)) + i := 0 + for filename, f := range pkg.Files { + filenames[i] = filename + i++ + if f.Doc != nil { + ndocs += len(f.Doc.List) + 1 // +1 for separator + } + ncomments += len(f.Comments) + ndecls += len(f.Decls) + } + sort.Strings(filenames) + + // Collect package comments from all package files into a single + // CommentGroup - the collected package documentation. 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 _, filename := range filenames { + f := pkg.Files[filename] + 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 func name -> decls index + i := 0 // current index + n := 0 // number of filtered entries + for _, filename := range filenames { + f := pkg.Files[filename] + 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 := nameOf(f) + 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 import specs from all package files. + var imports []*ImportSpec + if mode&FilterImportDuplicates != 0 { + seen := make(map[string]bool) + for _, filename := range filenames { + f := pkg.Files[filename] + for _, imp := range f.Imports { + if path := imp.Path.Value; !seen[path] { + // TODO: consider handling cases where: + // - 2 imports exist with the same import path but + // have different local names (one should probably + // keep both of them) + // - 2 imports exist but only one has a comment + // - 2 imports exist and they both have (possibly + // different) comments + imports = append(imports, imp) + seen[path] = true + } + } + } + } else { + // Iterate over filenames for deterministic order. + for _, filename := range filenames { + f := pkg.Files[filename] + imports = append(imports, f.Imports...) + } + } + + // Collect comments from all package files. + var comments []*CommentGroup + if mode&FilterUnassociatedComments == 0 { + comments = make([]*CommentGroup, ncomments) + i := 0 + for _, filename := range filenames { + f := pkg.Files[filename] + i += copy(comments[i:], f.Comments) + } + } + + // TODO(gri) need to compute unresolved identifiers! + return &File{doc, pos, NewIdent(pkg.Name), decls, pkg.Scope, imports, nil, comments} +} diff --git a/src/go/ast/filter_test.go b/src/go/ast/filter_test.go new file mode 100644 index 0000000..9fd86cb --- /dev/null +++ b/src/go/ast/filter_test.go @@ -0,0 +1,86 @@ +// Copyright 2013 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. + +// To avoid a cyclic dependency with go/parser, this file is in a separate package. + +package ast_test + +import ( + "bytes" + "go/ast" + "go/format" + "go/parser" + "go/token" + "testing" +) + +const input = `package p + +type t1 struct{} +type t2 struct{} + +func f1() {} +func f1() {} +func f2() {} + +func (*t1) f1() {} +func (t1) f1() {} +func (t1) f2() {} + +func (t2) f1() {} +func (t2) f2() {} +func (x *t2) f2() {} +` + +// Calling ast.MergePackageFiles with ast.FilterFuncDuplicates +// keeps a duplicate entry with attached documentation in favor +// of one without, and it favors duplicate entries appearing +// later in the source over ones appearing earlier. This is why +// (*t2).f2 is kept and t2.f2 is eliminated in this test case. +// +const golden = `package p + +type t1 struct{} +type t2 struct{} + +func f1() {} +func f2() {} + +func (t1) f1() {} +func (t1) f2() {} + +func (t2) f1() {} + +func (x *t2) f2() {} +` + +func TestFilterDuplicates(t *testing.T) { + // parse input + fset := token.NewFileSet() + file, err := parser.ParseFile(fset, "", input, 0) + if err != nil { + t.Fatal(err) + } + + // create package + files := map[string]*ast.File{"": file} + pkg, err := ast.NewPackage(fset, files, nil, nil) + if err != nil { + t.Fatal(err) + } + + // filter + merged := ast.MergePackageFiles(pkg, ast.FilterFuncDuplicates) + + // pretty-print + var buf bytes.Buffer + if err := format.Node(&buf, fset, merged); err != nil { + t.Fatal(err) + } + output := buf.String() + + if output != golden { + t.Errorf("incorrect output:\n%s", output) + } +} diff --git a/src/go/ast/import.go b/src/go/ast/import.go new file mode 100644 index 0000000..7fdf137 --- /dev/null +++ b/src/go/ast/import.go @@ -0,0 +1,230 @@ +// 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 ( + "go/token" + "sort" + "strconv" +) + +// SortImports sorts runs of consecutive import lines in import blocks in f. +// It also removes duplicate imports when it is possible to do so without data loss. +func SortImports(fset *token.FileSet, f *File) { + for _, d := range f.Decls { + d, ok := d.(*GenDecl) + if !ok || d.Tok != token.IMPORT { + // Not an import declaration, so we're done. + // Imports are always first. + break + } + + if !d.Lparen.IsValid() { + // Not a block: sorted by default. + continue + } + + // Identify and sort runs of specs on successive lines. + i := 0 + specs := d.Specs[:0] + for j, s := range d.Specs { + if j > i && lineAt(fset, s.Pos()) > 1+lineAt(fset, d.Specs[j-1].End()) { + // j begins a new run. End this one. + specs = append(specs, sortSpecs(fset, f, d.Specs[i:j])...) + i = j + } + } + specs = append(specs, sortSpecs(fset, f, d.Specs[i:])...) + d.Specs = specs + + // Deduping can leave a blank line before the rparen; clean that up. + if len(d.Specs) > 0 { + lastSpec := d.Specs[len(d.Specs)-1] + lastLine := lineAt(fset, lastSpec.Pos()) + rParenLine := lineAt(fset, d.Rparen) + for rParenLine > lastLine+1 { + rParenLine-- + fset.File(d.Rparen).MergeLine(rParenLine) + } + } + } +} + +func lineAt(fset *token.FileSet, pos token.Pos) int { + return fset.PositionFor(pos, false).Line +} + +func importPath(s Spec) string { + t, err := strconv.Unquote(s.(*ImportSpec).Path.Value) + if err == nil { + return t + } + return "" +} + +func importName(s Spec) string { + n := s.(*ImportSpec).Name + if n == nil { + return "" + } + return n.Name +} + +func importComment(s Spec) string { + c := s.(*ImportSpec).Comment + if c == nil { + return "" + } + return c.Text() +} + +// collapse indicates whether prev may be removed, leaving only next. +func collapse(prev, next Spec) bool { + if importPath(next) != importPath(prev) || importName(next) != importName(prev) { + return false + } + return prev.(*ImportSpec).Comment == nil +} + +type posSpan struct { + Start token.Pos + End token.Pos +} + +type cgPos struct { + left bool // true if comment is to the left of the spec, false otherwise. + cg *CommentGroup +} + +func sortSpecs(fset *token.FileSet, f *File, specs []Spec) []Spec { + // Can't short-circuit here even if specs are already sorted, + // since they might yet need deduplication. + // A lone import, however, may be safely ignored. + if len(specs) <= 1 { + return specs + } + + // Record positions for specs. + pos := make([]posSpan, len(specs)) + for i, s := range specs { + pos[i] = posSpan{s.Pos(), s.End()} + } + + // Identify comments in this range. + begSpecs := pos[0].Start + endSpecs := pos[len(pos)-1].End + beg := fset.File(begSpecs).LineStart(lineAt(fset, begSpecs)) + endLine := lineAt(fset, endSpecs) + endFile := fset.File(endSpecs) + var end token.Pos + if endLine == endFile.LineCount() { + end = endSpecs + } else { + end = endFile.LineStart(endLine + 1) // beginning of next line + } + first := len(f.Comments) + last := -1 + for i, g := range f.Comments { + if g.End() >= end { + break + } + // g.End() < end + if beg <= g.Pos() { + // comment is within the range [beg, end[ of import declarations + if i < first { + first = i + } + if i > last { + last = i + } + } + } + + var comments []*CommentGroup + if last >= 0 { + comments = f.Comments[first : last+1] + } + + // Assign each comment to the import spec on the same line. + importComments := map[*ImportSpec][]cgPos{} + specIndex := 0 + for _, g := range comments { + for specIndex+1 < len(specs) && pos[specIndex+1].Start <= g.Pos() { + specIndex++ + } + var left bool + // A block comment can appear before the first import spec. + if specIndex == 0 && pos[specIndex].Start > g.Pos() { + left = true + } else if specIndex+1 < len(specs) && // Or it can appear on the left of an import spec. + lineAt(fset, pos[specIndex].Start)+1 == lineAt(fset, g.Pos()) { + specIndex++ + left = true + } + s := specs[specIndex].(*ImportSpec) + importComments[s] = append(importComments[s], cgPos{left: left, cg: g}) + } + + // Sort the import specs by import path. + // Remove duplicates, when possible without data loss. + // Reassign the import paths to have the same position sequence. + // Reassign each comment to the spec on the same line. + // Sort the comments by new position. + sort.Slice(specs, func(i, j int) bool { + ipath := importPath(specs[i]) + jpath := importPath(specs[j]) + if ipath != jpath { + return ipath < jpath + } + iname := importName(specs[i]) + jname := importName(specs[j]) + if iname != jname { + return iname < jname + } + return importComment(specs[i]) < importComment(specs[j]) + }) + + // Dedup. Thanks to our sorting, we can just consider + // adjacent pairs of imports. + deduped := specs[:0] + for i, s := range specs { + if i == len(specs)-1 || !collapse(s, specs[i+1]) { + deduped = append(deduped, s) + } else { + p := s.Pos() + fset.File(p).MergeLine(lineAt(fset, p)) + } + } + specs = deduped + + // Fix up comment positions + for i, s := range specs { + s := s.(*ImportSpec) + if s.Name != nil { + s.Name.NamePos = pos[i].Start + } + s.Path.ValuePos = pos[i].Start + s.EndPos = pos[i].End + for _, g := range importComments[s] { + for _, c := range g.cg.List { + if g.left { + c.Slash = pos[i].Start - 1 + } else { + // An import spec can have both block comment and a line comment + // to its right. In that case, both of them will have the same pos. + // But while formatting the AST, the line comment gets moved to + // after the block comment. + c.Slash = pos[i].End + } + } + } + } + + sort.Slice(comments, func(i, j int) bool { + return comments[i].Pos() < comments[j].Pos() + }) + + return specs +} diff --git a/src/go/ast/issues_test.go b/src/go/ast/issues_test.go new file mode 100644 index 0000000..788c557 --- /dev/null +++ b/src/go/ast/issues_test.go @@ -0,0 +1,42 @@ +// Copyright 2019 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_test + +import ( + "go/ast" + "go/parser" + "go/token" + "testing" +) + +func TestIssue33649(t *testing.T) { + for _, src := range []string{ + `package p; func _()`, + `package p; func _() {`, + `package p; func _() { _ = 0`, + `package p; func _() { _ = 0 }`, + } { + fset := token.NewFileSet() + f, _ := parser.ParseFile(fset, "", src, parser.AllErrors) + if f == nil { + panic("invalid test setup: parser didn't return an AST") + } + + // find corresponding token.File + var tf *token.File + fset.Iterate(func(f *token.File) bool { + tf = f + return true + }) + tfEnd := tf.Base() + tf.Size() + + fd := f.Decls[len(f.Decls)-1].(*ast.FuncDecl) + fdEnd := int(fd.End()) + + if fdEnd != tfEnd { + t.Errorf("%q: got fdEnd = %d; want %d (base = %d, size = %d)", src, fdEnd, tfEnd, tf.Base(), tf.Size()) + } + } +} diff --git a/src/go/ast/print.go b/src/go/ast/print.go new file mode 100644 index 0000000..d86d9ba --- /dev/null +++ b/src/go/ast/print.go @@ -0,0 +1,254 @@ +// 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 support 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 +// printed; all others are filtered from the output. Unexported +// struct fields are never printed. +func Fprint(w io.Writer, fset *token.FileSet, x interface{}, f FieldFilter) error { + return fprint(w, fset, x, f) +} + +func fprint(w io.Writer, fset *token.FileSet, x interface{}, f FieldFilter) (err 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() { + 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{}) 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 + 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 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 + } + if len(data) > n { + m, err = p.output.Write(data[n:]) + n += m + } + return +} + +// localError wraps locally caught errors so we can distinguish +// them from genuine panics which we don't want to return as errors. +type localError struct { + err error +} + +// printf is a convenience wrapper that takes care of print errors. +func (p *printer) printf(format string, args ...interface{}) { + if _, err := fmt.Fprintf(p, format, args...); 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) {", x.Type(), x.Len()) + if x.Len() > 0 { + p.indent++ + p.printf("\n") + 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.Array: + p.printf("%s {", x.Type()) + if x.Len() > 0 { + p.indent++ + p.printf("\n") + 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.Slice: + if s, ok := x.Interface().([]byte); ok { + p.printf("%#q", s) + return + } + p.printf("%s (len = %d) {", x.Type(), x.Len()) + if x.Len() > 0 { + p.indent++ + p.printf("\n") + 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: + t := x.Type() + p.printf("%s {", t) + p.indent++ + first := true + for i, n := 0, t.NumField(); i < n; i++ { + // exclude non-exported fields because their + // values cannot be accessed via reflection + if name := t.Field(i).Name; IsExported(name) { + value := x.Field(i) + if p.filter == nil || p.filter(name, value) { + if first { + p.printf("\n") + first = false + } + 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/go/ast/print_test.go b/src/go/ast/print_test.go new file mode 100644 index 0000000..210f164 --- /dev/null +++ b/src/go/ast/print_test.go @@ -0,0 +1,97 @@ +// 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[Expr]string{}, `0 map[ast.Expr]string (len = 0) {}`}, + {map[string]int{"a": 1}, + `0 map[string]int (len = 1) { + 1 . "a": 1 + 2 }`}, + + // pointers + {new(int), "0 *0"}, + + // arrays + {[0]int{}, `0 [0]int {}`}, + {[3]int{1, 2, 3}, + `0 [3]int { + 1 . 0: 1 + 2 . 1: 2 + 3 . 2: 3 + 4 }`}, + {[...]int{42}, + `0 [1]int { + 1 . 0: 42 + 2 }`}, + + // slices + {[]int{}, `0 []int (len = 0) {}`}, + {[]int{1, 2, 3}, + `0 []int (len = 3) { + 1 . 0: 1 + 2 . 1: 2 + 3 . 2: 3 + 4 }`}, + + // structs + {struct{}{}, `0 struct {} {}`}, + {struct{ x int }{007}, `0 struct { x int } {}`}, + {struct{ X, y int }{42, 991}, + `0 struct { X int; y int } { + 1 . X: 42 + 2 }`}, + {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/go/ast/resolve.go b/src/go/ast/resolve.go new file mode 100644 index 0000000..c1830b5 --- /dev/null +++ b/src/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" + "strconv" +) + +type pkgBuilder struct { + fset *token.FileSet + errors scanner.ErrorList +} + +func (p *pkgBuilder) error(pos token.Pos, msg string) { + p.errors.Add(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 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, 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(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 if name != "_" { + // 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 + } + + p.errors.Sort() + return &Package{pkgName, pkgScope, imports, files}, p.errors.Err() +} diff --git a/src/go/ast/scope.go b/src/go/ast/scope.go new file mode 100644 index 0000000..a400c71 --- /dev/null +++ b/src/go/ast/scope.go @@ -0,0 +1,160 @@ +// 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 + +// 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 +// +type Object struct { + Kind ObjKind + Name string // declared name + Decl interface{} // corresponding Field, XxxSpec, FuncDecl, LabeledStmt, AssignStmt, Scope; or nil + Data interface{} // object-specific data; or nil + Type interface{} // placeholder 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() + } + case *AssignStmt: + for _, x := range d.Lhs { + if ident, isIdent := x.(*Ident); isIdent && ident.Name == name { + return ident.Pos() + } + } + case *Scope: + // predeclared object - nothing to do for now + } + return token.NoPos +} + +// ObjKind 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/go/ast/walk.go b/src/go/ast/walk.go new file mode 100644 index 0000000..8ca2195 --- /dev/null +++ b/src/go/ast/walk.go @@ -0,0 +1,386 @@ +// 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) + } + if n.Max != nil { + Walk(v, n.Max) + } + + 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: + if n.Params != nil { + 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: + if n.Key != nil { + 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) + // 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: + panic(fmt.Sprintf("ast.Walk: unexpected node type %T", n)) + } + + 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 +// recursively for each of the non-nil children of node, followed by a +// call of f(nil). +// +func Inspect(node Node, f func(Node) bool) { + Walk(inspector(f), node) +} |