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	}