// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package doc

import (
	
	
	
	
	
)

// ----------------------------------------------------------------------------
// function/method sets
//
// Internally, we treat functions like methods and collect them in method sets.

// A methodSet describes a set of methods. Entries where Decl == nil are conflict
// entries (more than one method with the same name at the same embedding level).
//
type methodSet map[string]*Func

// recvString returns a string representation of recv of the
// form "T", "*T", or "BADRECV" (if not a proper receiver type).
//
func recvString( ast.Expr) string {
	switch t := .(type) {
	case *ast.Ident:
		return .Name
	case *ast.StarExpr:
		return "*" + (.X)
	}
	return "BADRECV"
}

// set creates the corresponding Func for f and adds it to mset.
// If there are multiple f's with the same name, set keeps the first
// one with documentation; conflicts are ignored. The boolean
// specifies whether to leave the AST untouched.
//
func ( methodSet) ( *ast.FuncDecl,  bool) {
	 := .Name.Name
	if  := [];  != nil && .Doc != "" {
		// A function with the same name has already been registered;
		// since it has documentation, assume f is simply another
		// implementation and ignore it. This does not happen if the
		// caller is using go/build.ScanDir to determine the list of
		// files implementing a package.
		return
	}
	// function doesn't exist or has no documentation; use f
	 := ""
	if .Recv != nil {
		var  ast.Expr
		// be careful in case of incorrect ASTs
		if  := .Recv.List; len() == 1 {
			 = [0].Type
		}
		 = recvString()
	}
	[] = &Func{
		Doc:  .Doc.Text(),
		Name: ,
		Decl: ,
		Recv: ,
		Orig: ,
	}
	if ! {
		.Doc = nil // doc consumed - remove from AST
	}
}

// add adds method m to the method set; m is ignored if the method set
// already contains a method with the same name at the same or a higher
// level than m.
//
func ( methodSet) ( *Func) {
	 := [.Name]
	if  == nil || .Level < .Level {
		[.Name] = 
		return
	}
	if .Level == .Level {
		// conflict - mark it using a method with nil Decl
		[.Name] = &Func{
			Name:  .Name,
			Level: .Level,
		}
	}
}

// ----------------------------------------------------------------------------
// Named types

// baseTypeName returns the name of the base type of x (or "")
// and whether the type is imported or not.
//
func baseTypeName( ast.Expr) ( string,  bool) {
	switch t := .(type) {
	case *ast.Ident:
		return .Name, false
	case *ast.SelectorExpr:
		if ,  := .X.(*ast.Ident);  {
			// only possible for qualified type names;
			// assume type is imported
			return .Sel.Name, true
		}
	case *ast.ParenExpr:
		return (.X)
	case *ast.StarExpr:
		return (.X)
	}
	return
}

// An embeddedSet describes a set of embedded types.
type embeddedSet map[*namedType]bool

// A namedType represents a named unqualified (package local, or possibly
// predeclared) type. The namedType for a type name is always found via
// reader.lookupType.
//
type namedType struct {
	doc  string       // doc comment for type
	name string       // type name
	decl *ast.GenDecl // nil if declaration hasn't been seen yet

	isEmbedded bool        // true if this type is embedded
	isStruct   bool        // true if this type is a struct
	embedded   embeddedSet // true if the embedded type is a pointer

	// associated declarations
	values  []*Value // consts and vars
	funcs   methodSet
	methods methodSet
}

// ----------------------------------------------------------------------------
// AST reader

// reader accumulates documentation for a single package.
// It modifies the AST: Comments (declaration documentation)
// that have been collected by the reader are set to nil
// in the respective AST nodes so that they are not printed
// twice (once when printing the documentation and once when
// printing the corresponding AST node).
//
type reader struct {
	mode Mode

	// package properties
	doc       string // package documentation, if any
	filenames []string
	notes     map[string][]*Note

	// declarations
	imports   map[string]int
	hasDotImp bool     // if set, package contains a dot import
	values    []*Value // consts and vars
	order     int      // sort order of const and var declarations (when we can't use a name)
	types     map[string]*namedType
	funcs     methodSet

	// support for package-local error type declarations
	errorDecl bool                 // if set, type "error" was declared locally
	fixlist   []*ast.InterfaceType // list of interfaces containing anonymous field "error"
}

func ( *reader) ( string) bool {
	return .mode&AllDecls != 0 || token.IsExported()
}

// lookupType returns the base type with the given name.
// If the base type has not been encountered yet, a new
// type with the given name but no associated declaration
// is added to the type map.
//
func ( *reader) ( string) *namedType {
	if  == "" ||  == "_" {
		return nil // no type docs for anonymous types
	}
	if ,  := .types[];  {
		return 
	}
	// type not found - add one without declaration
	 := &namedType{
		name:     ,
		embedded: make(embeddedSet),
		funcs:    make(methodSet),
		methods:  make(methodSet),
	}
	.types[] = 
	return 
}

// recordAnonymousField registers fieldType as the type of an
// anonymous field in the parent type. If the field is imported
// (qualified name) or the parent is nil, the field is ignored.
// The function returns the field name.
//
func ( *reader) ( *namedType,  ast.Expr) ( string) {
	,  := baseTypeName()
	if  == nil ||  {
		return
	}
	if  := .lookupType();  != nil {
		.isEmbedded = true
		,  := .(*ast.StarExpr)
		.embedded[] = 
	}
	return
}

func ( *reader) ( *ast.CommentGroup) {
	// By convention there should be only one package comment
	// but collect all of them if there are more than one.
	 := .Text()
	if .doc == "" {
		.doc = 
		return
	}
	.doc += "\n" + 
}

func ( *reader) ( *ast.InterfaceType) {
	.fixlist = append(.fixlist, )
}

func specNames( []ast.Spec) []string {
	 := make([]string, 0, len()) // reasonable estimate
	for ,  := range  {
		// s guaranteed to be an *ast.ValueSpec by readValue
		for ,  := range .(*ast.ValueSpec).Names {
			 = append(, .Name)
		}
	}
	return 
}

// readValue processes a const or var declaration.
//
func ( *reader) ( *ast.GenDecl) {
	// determine if decl should be associated with a type
	// Heuristic: For each typed entry, determine the type name, if any.
	//            If there is exactly one type name that is sufficiently
	//            frequent, associate the decl with the respective type.
	 := ""
	 := 0
	 := ""
	 := 0
	for ,  := range .Specs {
		,  := .(*ast.ValueSpec)
		if ! {
			continue // should not happen, but be conservative
		}
		 := ""
		switch {
		case .Type != nil:
			// a type is present; determine its name
			if ,  := baseTypeName(.Type); ! {
				 = 
			}
		case .Tok == token.CONST && len(.Values) == 0:
			// no type or value is present but we have a constant declaration;
			// use the previous type name (possibly the empty string)
			 = 
		}
		if  != "" {
			// entry has a named type
			if  != "" &&  !=  {
				// more than one type name - do not associate
				// with any type
				 = ""
				break
			}
			 = 
			++
		}
		 = 
		++
	}

	// nothing to do w/o a legal declaration
	if  == 0 {
		return
	}

	// determine values list with which to associate the Value for this decl
	 := &.values
	const  = 0.75
	if  != "" && .isVisible() &&  >= int(float64(len(.Specs))*) {
		// typed entries are sufficiently frequent
		if  := .lookupType();  != nil {
			 = &.values // associate with that type
		}
	}

	* = append(*, &Value{
		Doc:   .Doc.Text(),
		Names: specNames(.Specs),
		Decl:  ,
		order: .order,
	})
	if .mode&PreserveAST == 0 {
		.Doc = nil // doc consumed - remove from AST
	}
	// Note: It's important that the order used here is global because the cleanupTypes
	// methods may move values associated with types back into the global list. If the
	// order is list-specific, sorting is not deterministic because the same order value
	// may appear multiple times (was bug, found when fixing #16153).
	.order++
}

// fields returns a struct's fields or an interface's methods.
//
func fields( ast.Expr) ( []*ast.Field,  bool) {
	var  *ast.FieldList
	switch t := .(type) {
	case *ast.StructType:
		 = .Fields
		 = true
	case *ast.InterfaceType:
		 = .Methods
	}
	if  != nil {
		 = .List
	}
	return
}

// readType processes a type declaration.
//
func ( *reader) ( *ast.GenDecl,  *ast.TypeSpec) {
	 := .lookupType(.Name.Name)
	if  == nil {
		return // no name or blank name - ignore the type
	}

	// A type should be added at most once, so typ.decl
	// should be nil - if it is not, simply overwrite it.
	.decl = 

	// compute documentation
	 := .Doc
	if  == nil {
		// no doc associated with the spec, use the declaration doc, if any
		 = .Doc
	}
	if .mode&PreserveAST == 0 {
		.Doc = nil // doc consumed - remove from AST
		.Doc = nil // doc consumed - remove from AST
	}
	.doc = .Text()

	// record anonymous fields (they may contribute methods)
	// (some fields may have been recorded already when filtering
	// exports, but that's ok)
	var  []*ast.Field
	, .isStruct = fields(.Type)
	for ,  := range  {
		if len(.Names) == 0 {
			.recordAnonymousField(, .Type)
		}
	}
}

// isPredeclared reports whether n denotes a predeclared type.
//
func ( *reader) ( string) bool {
	return predeclaredTypes[] && .types[] == nil
}

// readFunc processes a func or method declaration.
//
func ( *reader) ( *ast.FuncDecl) {
	// strip function body if requested.
	if .mode&PreserveAST == 0 {
		.Body = nil
	}

	// associate methods with the receiver type, if any
	if .Recv != nil {
		// method
		if len(.Recv.List) == 0 {
			// should not happen (incorrect AST); (See issue 17788)
			// don't show this method
			return
		}
		,  := baseTypeName(.Recv.List[0].Type)
		if  {
			// should not happen (incorrect AST);
			// don't show this method
			return
		}
		if  := .lookupType();  != nil {
			.methods.set(, .mode&PreserveAST != 0)
		}
		// otherwise ignore the method
		// TODO(gri): There may be exported methods of non-exported types
		// that can be called because of exported values (consts, vars, or
		// function results) of that type. Could determine if that is the
		// case and then show those methods in an appropriate section.
		return
	}

	// Associate factory functions with the first visible result type, as long as
	// others are predeclared types.
	if .Type.Results.NumFields() >= 1 {
		var  *namedType // type to associate the function with
		 := 0
		for ,  := range .Type.Results.List {
			 := .Type
			if ,  := .(*ast.ArrayType);  {
				// We consider functions that return slices or arrays of type
				// T (or pointers to T) as factory functions of T.
				 = .Elt
			}
			if ,  := baseTypeName(); ! && .isVisible() && !.isPredeclared() {
				if  := .lookupType();  != nil {
					 = 
					++
					if  > 1 {
						break
					}
				}
			}
		}
		// If there is exactly one result type,
		// associate the function with that type.
		if  == 1 {
			.funcs.set(, .mode&PreserveAST != 0)
			return
		}
	}

	// just an ordinary function
	.funcs.set(, .mode&PreserveAST != 0)
}

var (
	noteMarker    = `([A-Z][A-Z]+)\(([^)]+)\):?`                // MARKER(uid), MARKER at least 2 chars, uid at least 1 char
	noteMarkerRx  = lazyregexp.New(`^[ \t]*` + noteMarker)      // MARKER(uid) at text start
	noteCommentRx = lazyregexp.New(`^/[/*][ \t]*` + noteMarker) // MARKER(uid) at comment start
)

// readNote collects a single note from a sequence of comments.
//
func ( *reader) ( []*ast.Comment) {
	 := (&ast.CommentGroup{List: }).Text()
	if  := noteMarkerRx.FindStringSubmatchIndex();  != nil {
		// The note body starts after the marker.
		// We remove any formatting so that we don't
		// get spurious line breaks/indentation when
		// showing the TODO body.
		 := clean([[1]:], keepNL)
		if  != "" {
			 := [[2]:[3]]
			.notes[] = append(.notes[], &Note{
				Pos:  [0].Pos(),
				End:  [len()-1].End(),
				UID:  [[4]:[5]],
				Body: ,
			})
		}
	}
}

// readNotes extracts notes from comments.
// A note must start at the beginning of a comment with "MARKER(uid):"
// and is followed by the note body (e.g., "// BUG(gri): fix this").
// The note ends at the end of the comment group or at the start of
// another note in the same comment group, whichever comes first.
//
func ( *reader) ( []*ast.CommentGroup) {
	for ,  := range  {
		 := -1 // comment index of most recent note start, valid if >= 0
		 := .List
		for ,  := range  {
			if noteCommentRx.MatchString(.Text) {
				if  >= 0 {
					.readNote([:])
				}
				 = 
			}
		}
		if  >= 0 {
			.readNote([:])
		}
	}
}

// readFile adds the AST for a source file to the reader.
//
func ( *reader) ( *ast.File) {
	// add package documentation
	if .Doc != nil {
		.readDoc(.Doc)
		if .mode&PreserveAST == 0 {
			.Doc = nil // doc consumed - remove from AST
		}
	}

	// add all declarations but for functions which are processed in a separate pass
	for ,  := range .Decls {
		switch d := .(type) {
		case *ast.GenDecl:
			switch .Tok {
			case token.IMPORT:
				// imports are handled individually
				for ,  := range .Specs {
					if ,  := .(*ast.ImportSpec);  {
						if ,  := strconv.Unquote(.Path.Value);  == nil {
							.imports[] = 1
							if .Name != nil && .Name.Name == "." {
								.hasDotImp = true
							}
						}
					}
				}
			case token.CONST, token.VAR:
				// constants and variables are always handled as a group
				.readValue()
			case token.TYPE:
				// types are handled individually
				if len(.Specs) == 1 && !.Lparen.IsValid() {
					// common case: single declaration w/o parentheses
					// (if a single declaration is parenthesized,
					// create a new fake declaration below, so that
					// go/doc type declarations always appear w/o
					// parentheses)
					if ,  := .Specs[0].(*ast.TypeSpec);  {
						.readType(, )
					}
					break
				}
				for ,  := range .Specs {
					if ,  := .(*ast.TypeSpec);  {
						// use an individual (possibly fake) declaration
						// for each type; this also ensures that each type
						// gets to (re-)use the declaration documentation
						// if there's none associated with the spec itself
						 := &ast.GenDecl{
							Doc: .Doc,
							// don't use the existing TokPos because it
							// will lead to the wrong selection range for
							// the fake declaration if there are more
							// than one type in the group (this affects
							// src/cmd/godoc/godoc.go's posLink_urlFunc)
							TokPos: .Pos(),
							Tok:    token.TYPE,
							Specs:  []ast.Spec{},
						}
						.readType(, )
					}
				}
			}
		}
	}

	// collect MARKER(...): annotations
	.readNotes(.Comments)
	if .mode&PreserveAST == 0 {
		.Comments = nil // consumed unassociated comments - remove from AST
	}
}

func ( *reader) ( *ast.Package,  Mode) {
	// initialize reader
	.filenames = make([]string, len(.Files))
	.imports = make(map[string]int)
	.mode = 
	.types = make(map[string]*namedType)
	.funcs = make(methodSet)
	.notes = make(map[string][]*Note)

	// sort package files before reading them so that the
	// result does not depend on map iteration order
	 := 0
	for  := range .Files {
		.filenames[] = 
		++
	}
	sort.Strings(.filenames)

	// process files in sorted order
	for ,  := range .filenames {
		 := .Files[]
		if &AllDecls == 0 {
			.fileExports()
		}
		.readFile()
	}

	// process functions now that we have better type information
	for ,  := range .Files {
		for ,  := range .Decls {
			if ,  := .(*ast.FuncDecl);  {
				.readFunc()
			}
		}
	}
}

// ----------------------------------------------------------------------------
// Types

func customizeRecv( *Func,  string,  bool,  int) *Func {
	if  == nil || .Decl == nil || .Decl.Recv == nil || len(.Decl.Recv.List) != 1 {
		return  // shouldn't happen, but be safe
	}

	// copy existing receiver field and set new type
	 := *.Decl.Recv.List[0]
	 := .Type.Pos()
	,  := .Type.(*ast.StarExpr)
	 := &ast.Ident{NamePos: , Name: }
	var  ast.Expr = 
	if ! &&  {
		.NamePos++ // '*' is one character
		 = &ast.StarExpr{Star: , X: }
	}
	.Type = 

	// copy existing receiver field list and set new receiver field
	 := *.Decl.Recv
	.List = []*ast.Field{&}

	// copy existing function declaration and set new receiver field list
	 := *.Decl
	.Recv = &

	// copy existing function documentation and set new declaration
	 := *
	.Decl = &
	.Recv = recvString()
	// the Orig field never changes
	.Level = 

	return &
}

// collectEmbeddedMethods collects the embedded methods of typ in mset.
//
func ( *reader) ( methodSet,  *namedType,  string,  bool,  int,  embeddedSet) {
	[] = true
	for ,  := range .embedded {
		// Once an embedded type is embedded as a pointer type
		// all embedded types in those types are treated like
		// pointer types for the purpose of the receiver type
		// computation; i.e., embeddedIsPtr is sticky for this
		// embedding hierarchy.
		 :=  || 
		for ,  := range .methods {
			// only top-level methods are embedded
			if .Level == 0 {
				.add(customizeRecv(, , , ))
			}
		}
		if ![] {
			.(, , , , +1, )
		}
	}
	delete(, )
}

// computeMethodSets determines the actual method sets for each type encountered.
//
func ( *reader) () {
	for ,  := range .types {
		// collect embedded methods for t
		if .isStruct {
			// struct
			.collectEmbeddedMethods(.methods, , .name, false, 1, make(embeddedSet))
		} else {
			// interface
			// TODO(gri) fix this
		}
	}

	// if error was declared locally, don't treat it as exported field anymore
	if .errorDecl {
		for ,  := range .fixlist {
			removeErrorField()
		}
	}
}

// cleanupTypes removes the association of functions and methods with
// types that have no declaration. Instead, these functions and methods
// are shown at the package level. It also removes types with missing
// declarations or which are not visible.
//
func ( *reader) () {
	for ,  := range .types {
		 := .isVisible(.name)
		 := predeclaredTypes[.name]

		if .decl == nil && ( ||  && (.isEmbedded || .hasDotImp)) {
			// t.name is a predeclared type (and was not redeclared in this package),
			// or it was embedded somewhere but its declaration is missing (because
			// the AST is incomplete), or we have a dot-import (and all bets are off):
			// move any associated values, funcs, and methods back to the top-level so
			// that they are not lost.
			// 1) move values
			.values = append(.values, .values...)
			// 2) move factory functions
			for ,  := range .funcs {
				// in a correct AST, package-level function names
				// are all different - no need to check for conflicts
				.funcs[] = 
			}
			// 3) move methods
			if ! {
				for ,  := range .methods {
					// don't overwrite functions with the same name - drop them
					if ,  := .funcs[]; ! {
						.funcs[] = 
					}
				}
			}
		}
		// remove types w/o declaration or which are not visible
		if .decl == nil || ! {
			delete(.types, .name)
		}
	}
}

// ----------------------------------------------------------------------------
// Sorting

type data struct {
	n    int
	swap func(i, j int)
	less func(i, j int) bool
}

func ( *data) () int           { return .n }
func ( *data) (,  int)      { .swap(, ) }
func ( *data) (,  int) bool { return .less(, ) }

// sortBy is a helper function for sorting
func sortBy( func(,  int) bool,  func(,  int),  int) {
	sort.Sort(&data{, , })
}

func sortedKeys( map[string]int) []string {
	 := make([]string, len())
	 := 0
	for  := range  {
		[] = 
		++
	}
	sort.Strings()
	return 
}

// sortingName returns the name to use when sorting d into place.
//
func sortingName( *ast.GenDecl) string {
	if len(.Specs) == 1 {
		if ,  := .Specs[0].(*ast.ValueSpec);  {
			return .Names[0].Name
		}
	}
	return ""
}

func sortedValues( []*Value,  token.Token) []*Value {
	 := make([]*Value, len()) // big enough in any case
	 := 0
	for ,  := range  {
		if .Decl.Tok ==  {
			[] = 
			++
		}
	}
	 = [0:]

	sortBy(
		func(,  int) bool {
			if ,  := sortingName([].Decl), sortingName([].Decl);  !=  {
				return  < 
			}
			return [].order < [].order
		},
		func(,  int) { [], [] = [], [] },
		len(),
	)

	return 
}

func sortedTypes( map[string]*namedType,  bool) []*Type {
	 := make([]*Type, len())
	 := 0
	for ,  := range  {
		[] = &Type{
			Doc:     .doc,
			Name:    .name,
			Decl:    .decl,
			Consts:  sortedValues(.values, token.CONST),
			Vars:    sortedValues(.values, token.VAR),
			Funcs:   sortedFuncs(.funcs, true),
			Methods: sortedFuncs(.methods, ),
		}
		++
	}

	sortBy(
		func(,  int) bool { return [].Name < [].Name },
		func(,  int) { [], [] = [], [] },
		len(),
	)

	return 
}

func removeStar( string) string {
	if len() > 0 && [0] == '*' {
		return [1:]
	}
	return 
}

func sortedFuncs( methodSet,  bool) []*Func {
	 := make([]*Func, len())
	 := 0
	for ,  := range  {
		// determine which methods to include
		switch {
		case .Decl == nil:
			// exclude conflict entry
		case , .Level == 0, !token.IsExported(removeStar(.Orig)):
			// forced inclusion, method not embedded, or method
			// embedded but original receiver type not exported
			[] = 
			++
		}
	}
	 = [0:]
	sortBy(
		func(,  int) bool { return [].Name < [].Name },
		func(,  int) { [], [] = [], [] },
		len(),
	)
	return 
}

// noteBodies returns a list of note body strings given a list of notes.
// This is only used to populate the deprecated Package.Bugs field.
//
func noteBodies( []*Note) []string {
	var  []string
	for ,  := range  {
		 = append(, .Body)
	}
	return 
}

// ----------------------------------------------------------------------------
// Predeclared identifiers

// IsPredeclared reports whether s is a predeclared identifier.
func ( string) bool {
	return predeclaredTypes[] || predeclaredFuncs[] || predeclaredConstants[]
}

var predeclaredTypes = map[string]bool{
	"bool":       true,
	"byte":       true,
	"complex64":  true,
	"complex128": true,
	"error":      true,
	"float32":    true,
	"float64":    true,
	"int":        true,
	"int8":       true,
	"int16":      true,
	"int32":      true,
	"int64":      true,
	"rune":       true,
	"string":     true,
	"uint":       true,
	"uint8":      true,
	"uint16":     true,
	"uint32":     true,
	"uint64":     true,
	"uintptr":    true,
}

var predeclaredFuncs = map[string]bool{
	"append":  true,
	"cap":     true,
	"close":   true,
	"complex": true,
	"copy":    true,
	"delete":  true,
	"imag":    true,
	"len":     true,
	"make":    true,
	"new":     true,
	"panic":   true,
	"print":   true,
	"println": true,
	"real":    true,
	"recover": true,
}

var predeclaredConstants = map[string]bool{
	"false": true,
	"iota":  true,
	"nil":   true,
	"true":  true,
}