libgo/go/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 }