Source file src/pkg/go/doc/reader.go
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. 4 5 package doc 6 7 import ( 8 "go/ast" 9 "go/token" 10 "regexp" 11 "sort" 12 "strconv" 13 ) 14 15 // ---------------------------------------------------------------------------- 16 // function/method sets 17 // 18 // Internally, we treat functions like methods and collect them in method sets. 19 20 // A methodSet describes a set of methods. Entries where Decl == nil are conflict 21 // entries (more then one method with the same name at the same embedding level). 22 // 23 type methodSet map[string]*Func 24 25 // recvString returns a string representation of recv of the 26 // form "T", "*T", or "BADRECV" (if not a proper receiver type). 27 // 28 func recvString(recv ast.Expr) string { 29 switch t := recv.(type) { 30 case *ast.Ident: 31 return t.Name 32 case *ast.StarExpr: 33 return "*" + recvString(t.X) 34 } 35 return "BADRECV" 36 } 37 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. 41 // 42 func (mset methodSet) set(f *ast.FuncDecl) { 43 name := f.Name.Name 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. 50 return 51 } 52 // function doesn't exist or has no documentation; use f 53 recv := "" 54 if f.Recv != nil { 55 var typ ast.Expr 56 // be careful in case of incorrect ASTs 57 if list := f.Recv.List; len(list) == 1 { 58 typ = list[0].Type 59 } 60 recv = recvString(typ) 61 } 62 mset[name] = &Func{ 63 Doc: f.Doc.Text(), 64 Name: name, 65 Decl: f, 66 Recv: recv, 67 Orig: recv, 68 } 69 f.Doc = nil // doc consumed - remove from AST 70 } 71 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 74 // level then m. 75 // 76 func (mset methodSet) add(m *Func) { 77 old := mset[m.Name] 78 if old == nil || m.Level < old.Level { 79 mset[m.Name] = m 80 return 81 } 82 if old != nil && m.Level == old.Level { 83 // conflict - mark it using a method with nil Decl 84 mset[m.Name] = &Func{ 85 Name: m.Name, 86 Level: m.Level, 87 } 88 } 89 } 90 91 // ---------------------------------------------------------------------------- 92 // Named types 93 94 // baseTypeName returns the name of the base type of x (or "") 95 // and whether the type is imported or not. 96 // 97 func baseTypeName(x ast.Expr) (name string, imported bool) { 98 switch t := x.(type) { 99 case *ast.Ident: 100 return t.Name, false 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 106 } 107 case *ast.StarExpr: 108 return baseTypeName(t.X) 109 } 110 return 111 } 112 113 // An embeddedSet describes a set of embedded types. 114 type embeddedSet map[*namedType]bool 115 116 // A namedType represents a named unqualified (package local, or possibly 117 // predeclared) type. The namedType for a type name is always found via 118 // reader.lookupType. 119 // 120 type namedType struct { 121 doc string // doc comment for type 122 name string // type name 123 decl *ast.GenDecl // nil if declaration hasn't been seen yet 124 125 isEmbedded bool // true if this type is embedded 126 isStruct bool // true if this type is a struct 127 embedded embeddedSet // true if the embedded type is a pointer 128 129 // associated declarations 130 values []*Value // consts and vars 131 funcs methodSet 132 methods methodSet 133 } 134 135 // ---------------------------------------------------------------------------- 136 // AST reader 137 138 // reader accumulates documentation for a single package. 139 // It modifies the AST: Comments (declaration documentation) 140 // that have been collected by the reader are set to nil 141 // in the respective AST nodes so that they are not printed 142 // twice (once when printing the documentation and once when 143 // printing the corresponding AST node). 144 // 145 type reader struct { 146 mode Mode 147 148 // package properties 149 doc string // package documentation, if any 150 filenames []string 151 bugs []string 152 153 // declarations 154 imports map[string]int 155 values []*Value // consts and vars 156 types map[string]*namedType 157 funcs methodSet 158 159 // support for package-local error type declarations 160 errorDecl bool // if set, type "error" was declared locally 161 fixlist []*ast.InterfaceType // list of interfaces containing anonymous field "error" 162 } 163 164 func (r *reader) isVisible(name string) bool { 165 return r.mode&AllDecls != 0 || ast.IsExported(name) 166 } 167 168 // lookupType returns the base type with the given name. 169 // If the base type has not been encountered yet, a new 170 // type with the given name but no associated declaration 171 // is added to the type map. 172 // 173 func (r *reader) lookupType(name string) *namedType { 174 if name == "" || name == "_" { 175 return nil // no type docs for anonymous types 176 } 177 if typ, found := r.types[name]; found { 178 return typ 179 } 180 // type not found - add one without declaration 181 typ := &namedType{ 182 name: name, 183 embedded: make(embeddedSet), 184 funcs: make(methodSet), 185 methods: make(methodSet), 186 } 187 r.types[name] = typ 188 return typ 189 } 190 191 // recordAnonymousField registers fieldType as the type of an 192 // anonymous field in the parent type. If the field is imported 193 // (qualified name) or the parent is nil, the field is ignored. 194 // The function returns the field name. 195 // 196 func (r *reader) recordAnonymousField(parent *namedType, fieldType ast.Expr) (fname string) { 197 fname, imp := baseTypeName(fieldType) 198 if parent == nil || imp { 199 return 200 } 201 if ftype := r.lookupType(fname); ftype != nil { 202 ftype.isEmbedded = true 203 _, ptr := fieldType.(*ast.StarExpr) 204 parent.embedded[ftype] = ptr 205 } 206 return 207 } 208 209 func (r *reader) readDoc(comment *ast.CommentGroup) { 210 // By convention there should be only one package comment 211 // but collect all of them if there are more then one. 212 text := comment.Text() 213 if r.doc == "" { 214 r.doc = text 215 return 216 } 217 r.doc += "\n" + text 218 } 219 220 func (r *reader) remember(typ *ast.InterfaceType) { 221 r.fixlist = append(r.fixlist, typ) 222 } 223 224 func specNames(specs []ast.Spec) []string { 225 names := make([]string, 0, len(specs)) // reasonable estimate 226 for _, s := range specs { 227 // s guaranteed to be an *ast.ValueSpec by readValue 228 for _, ident := range s.(*ast.ValueSpec).Names { 229 names = append(names, ident.Name) 230 } 231 } 232 return names 233 } 234 235 // readValue processes a const or var declaration. 236 // 237 func (r *reader) readValue(decl *ast.GenDecl) { 238 // determine if decl should be associated with a type 239 // Heuristic: For each typed entry, determine the type name, if any. 240 // If there is exactly one type name that is sufficiently 241 // frequent, associate the decl with the respective type. 242 domName := "" 243 domFreq := 0 244 prev := "" 245 n := 0 246 for _, spec := range decl.Specs { 247 s, ok := spec.(*ast.ValueSpec) 248 if !ok { 249 continue // should not happen, but be conservative 250 } 251 name := "" 252 switch { 253 case s.Type != nil: 254 // a type is present; determine its name 255 if n, imp := baseTypeName(s.Type); !imp { 256 name = n 257 } 258 case decl.Tok == token.CONST: 259 // no type is present but we have a constant declaration; 260 // use the previous type name (w/o more type information 261 // we cannot handle the case of unnamed variables with 262 // initializer expressions except for some trivial cases) 263 name = prev 264 } 265 if name != "" { 266 // entry has a named type 267 if domName != "" && domName != name { 268 // more than one type name - do not associate 269 // with any type 270 domName = "" 271 break 272 } 273 domName = name 274 domFreq++ 275 } 276 prev = name 277 n++ 278 } 279 280 // nothing to do w/o a legal declaration 281 if n == 0 { 282 return 283 } 284 285 // determine values list with which to associate the Value for this decl 286 values := &r.values 287 const threshold = 0.75 288 if domName != "" && r.isVisible(domName) && domFreq >= int(float64(len(decl.Specs))*threshold) { 289 // typed entries are sufficiently frequent 290 if typ := r.lookupType(domName); typ != nil { 291 values = &typ.values // associate with that type 292 } 293 } 294 295 *values = append(*values, &Value{ 296 Doc: decl.Doc.Text(), 297 Names: specNames(decl.Specs), 298 Decl: decl, 299 order: len(*values), 300 }) 301 decl.Doc = nil // doc consumed - remove from AST 302 } 303 304 // fields returns a struct's fields or an interface's methods. 305 // 306 func fields(typ ast.Expr) (list []*ast.Field, isStruct bool) { 307 var fields *ast.FieldList 308 switch t := typ.(type) { 309 case *ast.StructType: 310 fields = t.Fields 311 isStruct = true 312 case *ast.InterfaceType: 313 fields = t.Methods 314 } 315 if fields != nil { 316 list = fields.List 317 } 318 return 319 } 320 321 // readType processes a type declaration. 322 // 323 func (r *reader) readType(decl *ast.GenDecl, spec *ast.TypeSpec) { 324 typ := r.lookupType(spec.Name.Name) 325 if typ == nil { 326 return // no name or blank name - ignore the type 327 } 328 329 // A type should be added at most once, so typ.decl 330 // should be nil - if it is not, simply overwrite it. 331 typ.decl = decl 332 333 // compute documentation 334 doc := spec.Doc 335 spec.Doc = nil // doc consumed - remove from AST 336 if doc == nil { 337 // no doc associated with the spec, use the declaration doc, if any 338 doc = decl.Doc 339 } 340 decl.Doc = nil // doc consumed - remove from AST 341 typ.doc = doc.Text() 342 343 // record anonymous fields (they may contribute methods) 344 // (some fields may have been recorded already when filtering 345 // exports, but that's ok) 346 var list []*ast.Field 347 list, typ.isStruct = fields(spec.Type) 348 for _, field := range list { 349 if len(field.Names) == 0 { 350 r.recordAnonymousField(typ, field.Type) 351 } 352 } 353 } 354 355 // readFunc processes a func or method declaration. 356 // 357 func (r *reader) readFunc(fun *ast.FuncDecl) { 358 // strip function body 359 fun.Body = nil 360 361 // associate methods with the receiver type, if any 362 if fun.Recv != nil { 363 // method 364 recvTypeName, imp := baseTypeName(fun.Recv.List[0].Type) 365 if imp { 366 // should not happen (incorrect AST); 367 // don't show this method 368 return 369 } 370 if typ := r.lookupType(recvTypeName); typ != nil { 371 typ.methods.set(fun) 372 } 373 // otherwise ignore the method 374 // TODO(gri): There may be exported methods of non-exported types 375 // that can be called because of exported values (consts, vars, or 376 // function results) of that type. Could determine if that is the 377 // case and then show those methods in an appropriate section. 378 return 379 } 380 381 // associate factory functions with the first visible result type, if any 382 if fun.Type.Results.NumFields() >= 1 { 383 res := fun.Type.Results.List[0] 384 if len(res.Names) <= 1 { 385 // exactly one (named or anonymous) result associated 386 // with the first type in result signature (there may 387 // be more than one result) 388 if n, imp := baseTypeName(res.Type); !imp && r.isVisible(n) { 389 if typ := r.lookupType(n); typ != nil { 390 // associate function with typ 391 typ.funcs.set(fun) 392 return 393 } 394 } 395 } 396 } 397 398 // just an ordinary function 399 r.funcs.set(fun) 400 } 401 402 var ( 403 bug_markers = regexp.MustCompile("^/[/*][ \t]*BUG\\(.*\\):[ \t]*") // BUG(uid): 404 bug_content = regexp.MustCompile("[^ \n\r\t]+") // at least one non-whitespace char 405 ) 406 407 // readFile adds the AST for a source file to the reader. 408 // 409 func (r *reader) readFile(src *ast.File) { 410 // add package documentation 411 if src.Doc != nil { 412 r.readDoc(src.Doc) 413 src.Doc = nil // doc consumed - remove from AST 414 } 415 416 // add all declarations 417 for _, decl := range src.Decls { 418 switch d := decl.(type) { 419 case *ast.GenDecl: 420 switch d.Tok { 421 case token.IMPORT: 422 // imports are handled individually 423 for _, spec := range d.Specs { 424 if s, ok := spec.(*ast.ImportSpec); ok { 425 if import_, err := strconv.Unquote(s.Path.Value); err == nil { 426 r.imports[import_] = 1 427 } 428 } 429 } 430 case token.CONST, token.VAR: 431 // constants and variables are always handled as a group 432 r.readValue(d) 433 case token.TYPE: 434 // types are handled individually 435 if len(d.Specs) == 1 && !d.Lparen.IsValid() { 436 // common case: single declaration w/o parentheses 437 // (if a single declaration is parenthesized, 438 // create a new fake declaration below, so that 439 // go/doc type declarations always appear w/o 440 // parentheses) 441 if s, ok := d.Specs[0].(*ast.TypeSpec); ok { 442 r.readType(d, s) 443 } 444 break 445 } 446 for _, spec := range d.Specs { 447 if s, ok := spec.(*ast.TypeSpec); ok { 448 // use an individual (possibly fake) declaration 449 // for each type; this also ensures that each type 450 // gets to (re-)use the declaration documentation 451 // if there's none associated with the spec itself 452 fake := &ast.GenDecl{ 453 Doc: d.Doc, 454 // don't use the existing TokPos because it 455 // will lead to the wrong selection range for 456 // the fake declaration if there are more 457 // than one type in the group (this affects 458 // src/cmd/godoc/godoc.go's posLink_urlFunc) 459 TokPos: s.Pos(), 460 Tok: token.TYPE, 461 Specs: []ast.Spec{s}, 462 } 463 r.readType(fake, s) 464 } 465 } 466 } 467 case *ast.FuncDecl: 468 r.readFunc(d) 469 } 470 } 471 472 // collect BUG(...) comments 473 for _, c := range src.Comments { 474 text := c.List[0].Text 475 if m := bug_markers.FindStringIndex(text); m != nil { 476 // found a BUG comment; maybe empty 477 if btxt := text[m[1]:]; bug_content.MatchString(btxt) { 478 // non-empty BUG comment; collect comment without BUG prefix 479 list := append([]*ast.Comment(nil), c.List...) // make a copy 480 list[0].Text = text[m[1]:] 481 r.bugs = append(r.bugs, (&ast.CommentGroup{List: list}).Text()) 482 } 483 } 484 } 485 src.Comments = nil // consumed unassociated comments - remove from AST 486 } 487 488 func (r *reader) readPackage(pkg *ast.Package, mode Mode) { 489 // initialize reader 490 r.filenames = make([]string, len(pkg.Files)) 491 r.imports = make(map[string]int) 492 r.mode = mode 493 r.types = make(map[string]*namedType) 494 r.funcs = make(methodSet) 495 496 // sort package files before reading them so that the 497 // result result does not depend on map iteration order 498 i := 0 499 for filename := range pkg.Files { 500 r.filenames[i] = filename 501 i++ 502 } 503 sort.Strings(r.filenames) 504 505 // process files in sorted order 506 for _, filename := range r.filenames { 507 f := pkg.Files[filename] 508 if mode&AllDecls == 0 { 509 r.fileExports(f) 510 } 511 r.readFile(f) 512 } 513 } 514 515 // ---------------------------------------------------------------------------- 516 // Types 517 518 var predeclaredTypes = map[string]bool{ 519 "bool": true, 520 "byte": true, 521 "complex64": true, 522 "complex128": true, 523 "error": true, 524 "float32": true, 525 "float64": true, 526 "int": true, 527 "int8": true, 528 "int16": true, 529 "int32": true, 530 "int64": true, 531 "rune": true, 532 "string": true, 533 "uint": true, 534 "uint8": true, 535 "uint16": true, 536 "uint32": true, 537 "uint64": true, 538 "uintptr": true, 539 } 540 541 func customizeRecv(f *Func, recvTypeName string, embeddedIsPtr bool, level int) *Func { 542 if f == nil || f.Decl == nil || f.Decl.Recv == nil || len(f.Decl.Recv.List) != 1 { 543 return f // shouldn't happen, but be safe 544 } 545 546 // copy existing receiver field and set new type 547 newField := *f.Decl.Recv.List[0] 548 _, origRecvIsPtr := newField.Type.(*ast.StarExpr) 549 var typ ast.Expr = ast.NewIdent(recvTypeName) 550 if !embeddedIsPtr && origRecvIsPtr { 551 typ = &ast.StarExpr{X: typ} 552 } 553 newField.Type = typ 554 555 // copy existing receiver field list and set new receiver field 556 newFieldList := *f.Decl.Recv 557 newFieldList.List = []*ast.Field{&newField} 558 559 // copy existing function declaration and set new receiver field list 560 newFuncDecl := *f.Decl 561 newFuncDecl.Recv = &newFieldList 562 563 // copy existing function documentation and set new declaration 564 newF := *f 565 newF.Decl = &newFuncDecl 566 newF.Recv = recvString(typ) 567 // the Orig field never changes 568 newF.Level = level 569 570 return &newF 571 } 572 573 // collectEmbeddedMethods collects the embedded methods of typ in mset. 574 // 575 func (r *reader) collectEmbeddedMethods(mset methodSet, typ *namedType, recvTypeName string, embeddedIsPtr bool, level int, visited embeddedSet) { 576 visited[typ] = true 577 for embedded, isPtr := range typ.embedded { 578 // Once an embedded type is embedded as a pointer type 579 // all embedded types in those types are treated like 580 // pointer types for the purpose of the receiver type 581 // computation; i.e., embeddedIsPtr is sticky for this 582 // embedding hierarchy. 583 thisEmbeddedIsPtr := embeddedIsPtr || isPtr 584 for _, m := range embedded.methods { 585 // only top-level methods are embedded 586 if m.Level == 0 { 587 mset.add(customizeRecv(m, recvTypeName, thisEmbeddedIsPtr, level)) 588 } 589 } 590 if !visited[embedded] { 591 r.collectEmbeddedMethods(mset, embedded, recvTypeName, thisEmbeddedIsPtr, level+1, visited) 592 } 593 } 594 delete(visited, typ) 595 } 596 597 // computeMethodSets determines the actual method sets for each type encountered. 598 // 599 func (r *reader) computeMethodSets() { 600 for _, t := range r.types { 601 // collect embedded methods for t 602 if t.isStruct { 603 // struct 604 r.collectEmbeddedMethods(t.methods, t, t.name, false, 1, make(embeddedSet)) 605 } else { 606 // interface 607 // TODO(gri) fix this 608 } 609 } 610 611 // if error was declared locally, don't treat it as exported field anymore 612 if r.errorDecl { 613 for _, ityp := range r.fixlist { 614 removeErrorField(ityp) 615 } 616 } 617 } 618 619 // cleanupTypes removes the association of functions and methods with 620 // types that have no declaration. Instead, these functions and methods 621 // are shown at the package level. It also removes types with missing 622 // declarations or which are not visible. 623 // 624 func (r *reader) cleanupTypes() { 625 for _, t := range r.types { 626 visible := r.isVisible(t.name) 627 if t.decl == nil && (predeclaredTypes[t.name] || t.isEmbedded && visible) { 628 // t.name is a predeclared type (and was not redeclared in this package), 629 // or it was embedded somewhere but its declaration is missing (because 630 // the AST is incomplete): move any associated values, funcs, and methods 631 // back to the top-level so that they are not lost. 632 // 1) move values 633 r.values = append(r.values, t.values...) 634 // 2) move factory functions 635 for name, f := range t.funcs { 636 // in a correct AST, package-level function names 637 // are all different - no need to check for conflicts 638 r.funcs[name] = f 639 } 640 // 3) move methods 641 for name, m := range t.methods { 642 // don't overwrite functions with the same name - drop them 643 if _, found := r.funcs[name]; !found { 644 r.funcs[name] = m 645 } 646 } 647 } 648 // remove types w/o declaration or which are not visible 649 if t.decl == nil || !visible { 650 delete(r.types, t.name) 651 } 652 } 653 } 654 655 // ---------------------------------------------------------------------------- 656 // Sorting 657 658 type data struct { 659 n int 660 swap func(i, j int) 661 less func(i, j int) bool 662 } 663 664 func (d *data) Len() int { return d.n } 665 func (d *data) Swap(i, j int) { d.swap(i, j) } 666 func (d *data) Less(i, j int) bool { return d.less(i, j) } 667 668 // sortBy is a helper function for sorting 669 func sortBy(less func(i, j int) bool, swap func(i, j int), n int) { 670 sort.Sort(&data{n, swap, less}) 671 } 672 673 func sortedKeys(m map[string]int) []string { 674 list := make([]string, len(m)) 675 i := 0 676 for key := range m { 677 list[i] = key 678 i++ 679 } 680 sort.Strings(list) 681 return list 682 } 683 684 // sortingName returns the name to use when sorting d into place. 685 // 686 func sortingName(d *ast.GenDecl) string { 687 if len(d.Specs) == 1 { 688 if s, ok := d.Specs[0].(*ast.ValueSpec); ok { 689 return s.Names[0].Name 690 } 691 } 692 return "" 693 } 694 695 func sortedValues(m []*Value, tok token.Token) []*Value { 696 list := make([]*Value, len(m)) // big enough in any case 697 i := 0 698 for _, val := range m { 699 if val.Decl.Tok == tok { 700 list[i] = val 701 i++ 702 } 703 } 704 list = list[0:i] 705 706 sortBy( 707 func(i, j int) bool { 708 if ni, nj := sortingName(list[i].Decl), sortingName(list[j].Decl); ni != nj { 709 return ni < nj 710 } 711 return list[i].order < list[j].order 712 }, 713 func(i, j int) { list[i], list[j] = list[j], list[i] }, 714 len(list), 715 ) 716 717 return list 718 } 719 720 func sortedTypes(m map[string]*namedType, allMethods bool) []*Type { 721 list := make([]*Type, len(m)) 722 i := 0 723 for _, t := range m { 724 list[i] = &Type{ 725 Doc: t.doc, 726 Name: t.name, 727 Decl: t.decl, 728 Consts: sortedValues(t.values, token.CONST), 729 Vars: sortedValues(t.values, token.VAR), 730 Funcs: sortedFuncs(t.funcs, true), 731 Methods: sortedFuncs(t.methods, allMethods), 732 } 733 i++ 734 } 735 736 sortBy( 737 func(i, j int) bool { return list[i].Name < list[j].Name }, 738 func(i, j int) { list[i], list[j] = list[j], list[i] }, 739 len(list), 740 ) 741 742 return list 743 } 744 745 func removeStar(s string) string { 746 if len(s) > 0 && s[0] == '*' { 747 return s[1:] 748 } 749 return s 750 } 751 752 func sortedFuncs(m methodSet, allMethods bool) []*Func { 753 list := make([]*Func, len(m)) 754 i := 0 755 for _, m := range m { 756 // determine which methods to include 757 switch { 758 case m.Decl == nil: 759 // exclude conflict entry 760 case allMethods, m.Level == 0, !ast.IsExported(removeStar(m.Orig)): 761 // forced inclusion, method not embedded, or method 762 // embedded but original receiver type not exported 763 list[i] = m 764 i++ 765 } 766 } 767 list = list[0:i] 768 sortBy( 769 func(i, j int) bool { return list[i].Name < list[j].Name }, 770 func(i, j int) { list[i], list[j] = list[j], list[i] }, 771 len(list), 772 ) 773 return list 774 }