1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
15 // ----------------------------------------------------------------------------
16 // function/method sets
18 // Internally, we treat functions like methods and collect them in method sets.
20 // A methodSet describes a set of methods. Entries where Decl == nil are conflict
21 // entries (more than one method with the same name at the same embedding level).
23 type methodSet
map[string]*Func
25 // recvString returns a string representation of recv of the
26 // form "T", "*T", or "BADRECV" (if not a proper receiver type).
28 func recvString(recv ast
.Expr
) string {
29 switch t
:= recv
.(type) {
33 return "*" + recvString(t
.X
)
38 // set creates the corresponding Func for f and adds it to mset.
39 // If there are multiple f's with the same name, set keeps the first
40 // one with documentation; conflicts are ignored.
42 func (mset methodSet
) set(f
*ast
.FuncDecl
) {
44 if g
:= mset
[name
]; g
!= nil && g
.Doc
!= "" {
45 // A function with the same name has already been registered;
46 // since it has documentation, assume f is simply another
47 // implementation and ignore it. This does not happen if the
48 // caller is using go/build.ScanDir to determine the list of
49 // files implementing a package.
52 // function doesn't exist or has no documentation; use f
56 // be careful in case of incorrect ASTs
57 if list
:= f
.Recv
.List
; len(list
) == 1 {
60 recv
= recvString(typ
)
69 f
.Doc
= nil // doc consumed - remove from AST
72 // add adds method m to the method set; m is ignored if the method set
73 // already contains a method with the same name at the same or a higher
76 func (mset methodSet
) add(m
*Func
) {
78 if old
== nil || m
.Level
< old
.Level
{
82 if old
!= nil && m
.Level
== old
.Level
{
83 // conflict - mark it using a method with nil Decl
91 // ----------------------------------------------------------------------------
94 // baseTypeName returns the name of the base type of x (or "")
95 // and whether the type is imported or not.
97 func baseTypeName(x ast
.Expr
) (name
string, imported
bool) {
98 switch t
:= x
.(type) {
101 case *ast
.SelectorExpr
:
102 if _
, ok
:= t
.X
.(*ast
.Ident
); ok
{
103 // only possible for qualified type names;
104 // assume type is imported
105 return t
.Sel
.Name
, true
108 return baseTypeName(t
.X
)
110 return baseTypeName(t
.X
)
115 // An embeddedSet describes a set of embedded types.
116 type embeddedSet
map[*namedType
]bool
118 // A namedType represents a named unqualified (package local, or possibly
119 // predeclared) type. The namedType for a type name is always found via
120 // reader.lookupType.
122 type namedType
struct {
123 doc
string // doc comment for type
124 name
string // type name
125 decl
*ast
.GenDecl
// nil if declaration hasn't been seen yet
127 isEmbedded
bool // true if this type is embedded
128 isStruct
bool // true if this type is a struct
129 embedded embeddedSet
// true if the embedded type is a pointer
131 // associated declarations
132 values
[]*Value
// consts and vars
137 // ----------------------------------------------------------------------------
140 // reader accumulates documentation for a single package.
141 // It modifies the AST: Comments (declaration documentation)
142 // that have been collected by the reader are set to nil
143 // in the respective AST nodes so that they are not printed
144 // twice (once when printing the documentation and once when
145 // printing the corresponding AST node).
150 // package properties
151 doc
string // package documentation, if any
153 notes
map[string][]*Note
156 imports
map[string]int
157 hasDotImp
bool // if set, package contains a dot import
158 values
[]*Value
// consts and vars
159 order
int // sort order of const and var declarations (when we can't use a name)
160 types
map[string]*namedType
163 // support for package-local error type declarations
164 errorDecl
bool // if set, type "error" was declared locally
165 fixlist
[]*ast
.InterfaceType
// list of interfaces containing anonymous field "error"
168 func (r
*reader
) isVisible(name
string) bool {
169 return r
.mode
&AllDecls
!= 0 || ast
.IsExported(name
)
172 // lookupType returns the base type with the given name.
173 // If the base type has not been encountered yet, a new
174 // type with the given name but no associated declaration
175 // is added to the type map.
177 func (r
*reader
) lookupType(name
string) *namedType
{
178 if name
== "" || name
== "_" {
179 return nil // no type docs for anonymous types
181 if typ
, found
:= r
.types
[name
]; found
{
184 // type not found - add one without declaration
187 embedded
: make(embeddedSet
),
188 funcs
: make(methodSet
),
189 methods
: make(methodSet
),
195 // recordAnonymousField registers fieldType as the type of an
196 // anonymous field in the parent type. If the field is imported
197 // (qualified name) or the parent is nil, the field is ignored.
198 // The function returns the field name.
200 func (r
*reader
) recordAnonymousField(parent
*namedType
, fieldType ast
.Expr
) (fname
string) {
201 fname
, imp
:= baseTypeName(fieldType
)
202 if parent
== nil || imp
{
205 if ftype
:= r
.lookupType(fname
); ftype
!= nil {
206 ftype
.isEmbedded
= true
207 _
, ptr
:= fieldType
.(*ast
.StarExpr
)
208 parent
.embedded
[ftype
] = ptr
213 func (r
*reader
) readDoc(comment
*ast
.CommentGroup
) {
214 // By convention there should be only one package comment
215 // but collect all of them if there are more than one.
216 text
:= comment
.Text()
224 func (r
*reader
) remember(typ
*ast
.InterfaceType
) {
225 r
.fixlist
= append(r
.fixlist
, typ
)
228 func specNames(specs
[]ast
.Spec
) []string {
229 names
:= make([]string, 0, len(specs
)) // reasonable estimate
230 for _
, s
:= range specs
{
231 // s guaranteed to be an *ast.ValueSpec by readValue
232 for _
, ident
:= range s
.(*ast
.ValueSpec
).Names
{
233 names
= append(names
, ident
.Name
)
239 // readValue processes a const or var declaration.
241 func (r
*reader
) readValue(decl
*ast
.GenDecl
) {
242 // determine if decl should be associated with a type
243 // Heuristic: For each typed entry, determine the type name, if any.
244 // If there is exactly one type name that is sufficiently
245 // frequent, associate the decl with the respective type.
250 for _
, spec
:= range decl
.Specs
{
251 s
, ok
:= spec
.(*ast
.ValueSpec
)
253 continue // should not happen, but be conservative
258 // a type is present; determine its name
259 if n
, imp
:= baseTypeName(s
.Type
); !imp
{
262 case decl
.Tok
== token
.CONST
&& len(s
.Values
) == 0:
263 // no type or value is present but we have a constant declaration;
264 // use the previous type name (possibly the empty string)
268 // entry has a named type
269 if domName
!= "" && domName
!= name
{
270 // more than one type name - do not associate
282 // nothing to do w/o a legal declaration
287 // determine values list with which to associate the Value for this decl
289 const threshold
= 0.75
290 if domName
!= "" && r
.isVisible(domName
) && domFreq
>= int(float64(len(decl
.Specs
))*threshold
) {
291 // typed entries are sufficiently frequent
292 if typ
:= r
.lookupType(domName
); typ
!= nil {
293 values
= &typ
.values
// associate with that type
297 *values
= append(*values
, &Value
{
298 Doc
: decl
.Doc
.Text(),
299 Names
: specNames(decl
.Specs
),
303 decl
.Doc
= nil // doc consumed - remove from AST
305 // Note: It's important that the order used here is global because the cleanupTypes
306 // methods may move values associated with types back into the global list. If the
307 // order is list-specific, sorting is not deterministic because the same order value
308 // may appear multiple times (was bug, found when fixing #16153).
312 // fields returns a struct's fields or an interface's methods.
314 func fields(typ ast
.Expr
) (list
[]*ast
.Field
, isStruct
bool) {
315 var fields
*ast
.FieldList
316 switch t
:= typ
.(type) {
317 case *ast
.StructType
:
320 case *ast
.InterfaceType
:
329 // readType processes a type declaration.
331 func (r
*reader
) readType(decl
*ast
.GenDecl
, spec
*ast
.TypeSpec
) {
332 typ
:= r
.lookupType(spec
.Name
.Name
)
334 return // no name or blank name - ignore the type
337 // A type should be added at most once, so typ.decl
338 // should be nil - if it is not, simply overwrite it.
341 // compute documentation
343 spec
.Doc
= nil // doc consumed - remove from AST
345 // no doc associated with the spec, use the declaration doc, if any
348 decl
.Doc
= nil // doc consumed - remove from AST
351 // record anonymous fields (they may contribute methods)
352 // (some fields may have been recorded already when filtering
353 // exports, but that's ok)
354 var list
[]*ast
.Field
355 list
, typ
.isStruct
= fields(spec
.Type
)
356 for _
, field
:= range list
{
357 if len(field
.Names
) == 0 {
358 r
.recordAnonymousField(typ
, field
.Type
)
363 // readFunc processes a func or method declaration.
365 func (r
*reader
) readFunc(fun
*ast
.FuncDecl
) {
366 // strip function body
369 // associate methods with the receiver type, if any
372 if len(fun
.Recv
.List
) == 0 {
373 // should not happen (incorrect AST); (See issue 17788)
374 // don't show this method
377 recvTypeName
, imp
:= baseTypeName(fun
.Recv
.List
[0].Type
)
379 // should not happen (incorrect AST);
380 // don't show this method
383 if typ
:= r
.lookupType(recvTypeName
); typ
!= nil {
386 // otherwise ignore the method
387 // TODO(gri): There may be exported methods of non-exported types
388 // that can be called because of exported values (consts, vars, or
389 // function results) of that type. Could determine if that is the
390 // case and then show those methods in an appropriate section.
394 // Associate factory functions with the first visible result type, if that
395 // is the only type returned.
396 if fun
.Type
.Results
.NumFields() >= 1 {
397 var typ
*namedType
// type to associate the function with
399 for _
, res
:= range fun
.Type
.Results
.List
{
400 // exactly one (named or anonymous) result associated
401 // with the first type in result signature (there may
402 // be more than one result)
403 factoryType
:= res
.Type
404 if t
, ok
:= factoryType
.(*ast
.ArrayType
); ok
{
405 // We consider functions that return slices or arrays of type
406 // T (or pointers to T) as factory functions of T.
409 if n
, imp
:= baseTypeName(factoryType
); !imp
&& r
.isVisible(n
) {
410 if t
:= r
.lookupType(n
); t
!= nil {
416 // If there is exactly one result type, associate the function with that type.
417 if numResultTypes
== 1 {
423 // just an ordinary function
428 noteMarker
= `([A-Z][A-Z]+)\(([^)]+)\):?` // MARKER(uid), MARKER at least 2 chars, uid at least 1 char
429 noteMarkerRx
= regexp
.MustCompile(`^[ \t]*` + noteMarker
) // MARKER(uid) at text start
430 noteCommentRx
= regexp
.MustCompile(`^/[/*][ \t]*` + noteMarker
) // MARKER(uid) at comment start
433 // readNote collects a single note from a sequence of comments.
435 func (r
*reader
) readNote(list
[]*ast
.Comment
) {
436 text
:= (&ast
.CommentGroup
{List
: list
}).Text()
437 if m
:= noteMarkerRx
.FindStringSubmatchIndex(text
); m
!= nil {
438 // The note body starts after the marker.
439 // We remove any formatting so that we don't
440 // get spurious line breaks/indentation when
441 // showing the TODO body.
442 body
:= clean(text
[m
[1]:], keepNL
)
444 marker
:= text
[m
[2]:m
[3]]
445 r
.notes
[marker
] = append(r
.notes
[marker
], &Note
{
447 End
: list
[len(list
)-1].End(),
448 UID
: text
[m
[4]:m
[5]],
455 // readNotes extracts notes from comments.
456 // A note must start at the beginning of a comment with "MARKER(uid):"
457 // and is followed by the note body (e.g., "// BUG(gri): fix this").
458 // The note ends at the end of the comment group or at the start of
459 // another note in the same comment group, whichever comes first.
461 func (r
*reader
) readNotes(comments
[]*ast
.CommentGroup
) {
462 for _
, group
:= range comments
{
463 i
:= -1 // comment index of most recent note start, valid if >= 0
465 for j
, c
:= range list
{
466 if noteCommentRx
.MatchString(c
.Text
) {
468 r
.readNote(list
[i
:j
])
479 // readFile adds the AST for a source file to the reader.
481 func (r
*reader
) readFile(src
*ast
.File
) {
482 // add package documentation
485 src
.Doc
= nil // doc consumed - remove from AST
488 // add all declarations
489 for _
, decl
:= range src
.Decls
{
490 switch d
:= decl
.(type) {
494 // imports are handled individually
495 for _
, spec
:= range d
.Specs
{
496 if s
, ok
:= spec
.(*ast
.ImportSpec
); ok
{
497 if import_
, err
:= strconv
.Unquote(s
.Path
.Value
); err
== nil {
498 r
.imports
[import_
] = 1
499 if s
.Name
!= nil && s
.Name
.Name
== "." {
505 case token
.CONST
, token
.VAR
:
506 // constants and variables are always handled as a group
509 // types are handled individually
510 if len(d
.Specs
) == 1 && !d
.Lparen
.IsValid() {
511 // common case: single declaration w/o parentheses
512 // (if a single declaration is parenthesized,
513 // create a new fake declaration below, so that
514 // go/doc type declarations always appear w/o
516 if s
, ok
:= d
.Specs
[0].(*ast
.TypeSpec
); ok
{
521 for _
, spec
:= range d
.Specs
{
522 if s
, ok
:= spec
.(*ast
.TypeSpec
); ok
{
523 // use an individual (possibly fake) declaration
524 // for each type; this also ensures that each type
525 // gets to (re-)use the declaration documentation
526 // if there's none associated with the spec itself
527 fake
:= &ast
.GenDecl
{
529 // don't use the existing TokPos because it
530 // will lead to the wrong selection range for
531 // the fake declaration if there are more
532 // than one type in the group (this affects
533 // src/cmd/godoc/godoc.go's posLink_urlFunc)
536 Specs
: []ast
.Spec
{s
},
547 // collect MARKER(...): annotations
548 r
.readNotes(src
.Comments
)
549 src
.Comments
= nil // consumed unassociated comments - remove from AST
552 func (r
*reader
) readPackage(pkg
*ast
.Package
, mode Mode
) {
554 r
.filenames
= make([]string, len(pkg
.Files
))
555 r
.imports
= make(map[string]int)
557 r
.types
= make(map[string]*namedType
)
558 r
.funcs
= make(methodSet
)
559 r
.notes
= make(map[string][]*Note
)
561 // sort package files before reading them so that the
562 // result does not depend on map iteration order
564 for filename
:= range pkg
.Files
{
565 r
.filenames
[i
] = filename
568 sort
.Strings(r
.filenames
)
570 // process files in sorted order
571 for _
, filename
:= range r
.filenames
{
572 f
:= pkg
.Files
[filename
]
573 if mode
&AllDecls
== 0 {
580 // ----------------------------------------------------------------------------
583 func customizeRecv(f
*Func
, recvTypeName
string, embeddedIsPtr
bool, level
int) *Func
{
584 if f
== nil || f
.Decl
== nil || f
.Decl
.Recv
== nil ||
len(f
.Decl
.Recv
.List
) != 1 {
585 return f
// shouldn't happen, but be safe
588 // copy existing receiver field and set new type
589 newField
:= *f
.Decl
.Recv
.List
[0]
590 origPos
:= newField
.Type
.Pos()
591 _
, origRecvIsPtr
:= newField
.Type
.(*ast
.StarExpr
)
592 newIdent
:= &ast
.Ident
{NamePos
: origPos
, Name
: recvTypeName
}
593 var typ ast
.Expr
= newIdent
594 if !embeddedIsPtr
&& origRecvIsPtr
{
595 newIdent
.NamePos
++ // '*' is one character
596 typ
= &ast
.StarExpr
{Star
: origPos
, X
: newIdent
}
600 // copy existing receiver field list and set new receiver field
601 newFieldList
:= *f
.Decl
.Recv
602 newFieldList
.List
= []*ast
.Field
{&newField
}
604 // copy existing function declaration and set new receiver field list
605 newFuncDecl
:= *f
.Decl
606 newFuncDecl
.Recv
= &newFieldList
608 // copy existing function documentation and set new declaration
610 newF
.Decl
= &newFuncDecl
611 newF
.Recv
= recvString(typ
)
612 // the Orig field never changes
618 // collectEmbeddedMethods collects the embedded methods of typ in mset.
620 func (r
*reader
) collectEmbeddedMethods(mset methodSet
, typ
*namedType
, recvTypeName
string, embeddedIsPtr
bool, level
int, visited embeddedSet
) {
622 for embedded
, isPtr
:= range typ
.embedded
{
623 // Once an embedded type is embedded as a pointer type
624 // all embedded types in those types are treated like
625 // pointer types for the purpose of the receiver type
626 // computation; i.e., embeddedIsPtr is sticky for this
627 // embedding hierarchy.
628 thisEmbeddedIsPtr
:= embeddedIsPtr || isPtr
629 for _
, m
:= range embedded
.methods
{
630 // only top-level methods are embedded
632 mset
.add(customizeRecv(m
, recvTypeName
, thisEmbeddedIsPtr
, level
))
635 if !visited
[embedded
] {
636 r
.collectEmbeddedMethods(mset
, embedded
, recvTypeName
, thisEmbeddedIsPtr
, level
+1, visited
)
642 // computeMethodSets determines the actual method sets for each type encountered.
644 func (r
*reader
) computeMethodSets() {
645 for _
, t
:= range r
.types
{
646 // collect embedded methods for t
649 r
.collectEmbeddedMethods(t
.methods
, t
, t
.name
, false, 1, make(embeddedSet
))
652 // TODO(gri) fix this
656 // if error was declared locally, don't treat it as exported field anymore
658 for _
, ityp
:= range r
.fixlist
{
659 removeErrorField(ityp
)
664 // cleanupTypes removes the association of functions and methods with
665 // types that have no declaration. Instead, these functions and methods
666 // are shown at the package level. It also removes types with missing
667 // declarations or which are not visible.
669 func (r
*reader
) cleanupTypes() {
670 for _
, t
:= range r
.types
{
671 visible
:= r
.isVisible(t
.name
)
672 predeclared
:= predeclaredTypes
[t
.name
]
674 if t
.decl
== nil && (predeclared || visible
&& (t
.isEmbedded || r
.hasDotImp
)) {
675 // t.name is a predeclared type (and was not redeclared in this package),
676 // or it was embedded somewhere but its declaration is missing (because
677 // the AST is incomplete), or we have a dot-import (and all bets are off):
678 // move any associated values, funcs, and methods back to the top-level so
679 // that they are not lost.
681 r
.values
= append(r
.values
, t
.values
...)
682 // 2) move factory functions
683 for name
, f
:= range t
.funcs
{
684 // in a correct AST, package-level function names
685 // are all different - no need to check for conflicts
690 for name
, m
:= range t
.methods
{
691 // don't overwrite functions with the same name - drop them
692 if _
, found
:= r
.funcs
[name
]; !found
{
698 // remove types w/o declaration or which are not visible
699 if t
.decl
== nil ||
!visible
{
700 delete(r
.types
, t
.name
)
705 // ----------------------------------------------------------------------------
711 less
func(i
, j
int) bool
714 func (d
*data
) Len() int { return d
.n
}
715 func (d
*data
) Swap(i
, j
int) { d
.swap(i
, j
) }
716 func (d
*data
) Less(i
, j
int) bool { return d
.less(i
, j
) }
718 // sortBy is a helper function for sorting
719 func sortBy(less
func(i
, j
int) bool, swap
func(i
, j
int), n
int) {
720 sort
.Sort(&data
{n
, swap
, less
})
723 func sortedKeys(m
map[string]int) []string {
724 list
:= make([]string, len(m
))
734 // sortingName returns the name to use when sorting d into place.
736 func sortingName(d
*ast
.GenDecl
) string {
737 if len(d
.Specs
) == 1 {
738 if s
, ok
:= d
.Specs
[0].(*ast
.ValueSpec
); ok
{
739 return s
.Names
[0].Name
745 func sortedValues(m
[]*Value
, tok token
.Token
) []*Value
{
746 list
:= make([]*Value
, len(m
)) // big enough in any case
748 for _
, val
:= range m
{
749 if val
.Decl
.Tok
== tok
{
757 func(i
, j
int) bool {
758 if ni
, nj
:= sortingName(list
[i
].Decl
), sortingName(list
[j
].Decl
); ni
!= nj
{
761 return list
[i
].order
< list
[j
].order
763 func(i
, j
int) { list
[i
], list
[j
] = list
[j
], list
[i
] },
770 func sortedTypes(m
map[string]*namedType
, allMethods
bool) []*Type
{
771 list
:= make([]*Type
, len(m
))
773 for _
, t
:= range m
{
778 Consts
: sortedValues(t
.values
, token
.CONST
),
779 Vars
: sortedValues(t
.values
, token
.VAR
),
780 Funcs
: sortedFuncs(t
.funcs
, true),
781 Methods
: sortedFuncs(t
.methods
, allMethods
),
787 func(i
, j
int) bool { return list
[i
].Name
< list
[j
].Name
},
788 func(i
, j
int) { list
[i
], list
[j
] = list
[j
], list
[i
] },
795 func removeStar(s
string) string {
796 if len(s
) > 0 && s
[0] == '*' {
802 func sortedFuncs(m methodSet
, allMethods
bool) []*Func
{
803 list
:= make([]*Func
, len(m
))
805 for _
, m
:= range m
{
806 // determine which methods to include
809 // exclude conflict entry
810 case allMethods
, m
.Level
== 0, !ast
.IsExported(removeStar(m
.Orig
)):
811 // forced inclusion, method not embedded, or method
812 // embedded but original receiver type not exported
819 func(i
, j
int) bool { return list
[i
].Name
< list
[j
].Name
},
820 func(i
, j
int) { list
[i
], list
[j
] = list
[j
], list
[i
] },
826 // noteBodies returns a list of note body strings given a list of notes.
827 // This is only used to populate the deprecated Package.Bugs field.
829 func noteBodies(notes
[]*Note
) []string {
831 for _
, n
:= range notes
{
832 list
= append(list
, n
.Body
)
837 // ----------------------------------------------------------------------------
838 // Predeclared identifiers
840 // IsPredeclared reports whether s is a predeclared identifier.
841 func IsPredeclared(s
string) bool {
842 return predeclaredTypes
[s
] || predeclaredFuncs
[s
] || predeclaredConstants
[s
]
845 var predeclaredTypes
= map[string]bool{
868 var predeclaredFuncs
= map[string]bool{
886 var predeclaredConstants
= map[string]bool{