// Copyright 2011 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.

// Extract example functions from file ASTs.

package doc

import (
	
	
	
	
	
	
	
	
	
)

// An Example represents an example function found in a test source file.
type Example struct {
	Name        string // name of the item being exemplified (including optional suffix)
	Suffix      string // example suffix, without leading '_' (only populated by NewFromFiles)
	Doc         string // example function doc string
	Code        ast.Node
	Play        *ast.File // a whole program version of the example
	Comments    []*ast.CommentGroup
	Output      string // expected output
	Unordered   bool
	EmptyOutput bool // expect empty output
	Order       int  // original source code order
}

// Examples returns the examples found in testFiles, sorted by Name field.
// The Order fields record the order in which the examples were encountered.
// The Suffix field is not populated when Examples is called directly, it is
// only populated by NewFromFiles for examples it finds in _test.go files.
//
// Playable Examples must be in a package whose name ends in "_test".
// An Example is "playable" (the Play field is non-nil) in either of these
// circumstances:
//   - The example function is self-contained: the function references only
//     identifiers from other packages (or predeclared identifiers, such as
//     "int") and the test file does not include a dot import.
//   - The entire test file is the example: the file contains exactly one
//     example function, zero test or benchmark functions, and at least one
//     top-level function, type, variable, or constant declaration other
//     than the example function.
func ( ...*ast.File) []*Example {
	var  []*Example
	for ,  := range  {
		 := false // file contains tests or benchmarks
		 := 0      // number of non-import declarations in the file
		var  []*Example
		for ,  := range .Decls {
			if ,  := .(*ast.GenDecl);  && .Tok != token.IMPORT {
				++
				continue
			}
			,  := .(*ast.FuncDecl)
			if ! || .Recv != nil {
				continue
			}
			++
			 := .Name.Name
			if isTest(, "Test") || isTest(, "Benchmark") {
				 = true
				continue
			}
			if !isTest(, "Example") {
				continue
			}
			if  := .Type.Params; len(.List) != 0 {
				continue // function has params; not a valid example
			}
			if .Body == nil { // ast.File.Body nil dereference (see issue 28044)
				continue
			}
			var  string
			if .Doc != nil {
				 = .Doc.Text()
			}
			, ,  := exampleOutput(.Body, .Comments)
			 = append(, &Example{
				Name:        [len("Example"):],
				Doc:         ,
				Code:        .Body,
				Play:        playExample(, ),
				Comments:    .Comments,
				Output:      ,
				Unordered:   ,
				EmptyOutput:  == "" && ,
				Order:       len(),
			})
		}
		if ! &&  > 1 && len() == 1 {
			// If this file only has one example function, some
			// other top-level declarations, and no tests or
			// benchmarks, use the whole file as the example.
			[0].Code = 
			[0].Play = playExampleFile()
		}
		 = append(, ...)
	}
	// sort by name
	sort.Slice(, func(,  int) bool {
		return [].Name < [].Name
	})
	return 
}

var outputPrefix = lazyregexp.New(`(?i)^[[:space:]]*(unordered )?output:`)

// Extracts the expected output and whether there was a valid output comment
func exampleOutput( *ast.BlockStmt,  []*ast.CommentGroup) ( string, ,  bool) {
	if ,  := lastComment(, );  != nil {
		// test that it begins with the correct prefix
		 := .Text()
		if  := outputPrefix.FindStringSubmatchIndex();  != nil {
			if [2] != -1 {
				 = true
			}
			 = [[1]:]
			// Strip zero or more spaces followed by \n or a single space.
			 = strings.TrimLeft(, " ")
			if len() > 0 && [0] == '\n' {
				 = [1:]
			}
			return , , true
		}
	}
	return "", false, false // no suitable comment found
}

// isTest tells whether name looks like a test, example, or benchmark.
// It is a Test (say) if there is a character after Test that is not a
// lower-case letter. (We don't want Testiness.)
func isTest(,  string) bool {
	if !strings.HasPrefix(, ) {
		return false
	}
	if len() == len() { // "Test" is ok
		return true
	}
	,  := utf8.DecodeRuneInString([len():])
	return !unicode.IsLower()
}

// playExample synthesizes a new *ast.File based on the provided
// file with the provided function body as the body of main.
func playExample( *ast.File,  *ast.FuncDecl) *ast.File {
	 := .Body

	if !strings.HasSuffix(.Name.Name, "_test") {
		// We don't support examples that are part of the
		// greater package (yet).
		return nil
	}

	// Collect top-level declarations in the file.
	 := make(map[*ast.Object]ast.Decl)
	 := make(map[string][]ast.Decl)

	for ,  := range .Decls {
		switch d := .(type) {
		case *ast.FuncDecl:
			if .Recv == nil {
				[.Name.Obj] = 
			} else {
				if len(.Recv.List) == 1 {
					 := .Recv.List[0].Type
					,  := baseTypeName()
					[] = append([], )
				}
			}
		case *ast.GenDecl:
			for ,  := range .Specs {
				switch s := .(type) {
				case *ast.TypeSpec:
					[.Name.Obj] = 
				case *ast.ValueSpec:
					for ,  := range .Names {
						[.Obj] = 
					}
				}
			}
		}
	}

	// Find unresolved identifiers and uses of top-level declarations.
	 := make(map[string]bool)
	var  []ast.Decl
	 := make(map[ast.Decl]bool)

	var  func(ast.Node) bool
	 = func( ast.Node) bool {
		switch e := .(type) {
		case *ast.Ident:
			if .Obj == nil && .Name != "_" {
				[.Name] = true
			} else if  := [.Obj];  != nil {
				if ![] {
					[] = true
					 = append(, )
				}
			}
			return true
		case *ast.SelectorExpr:
			// For selector expressions, only inspect the left hand side.
			// (For an expression like fmt.Println, only add "fmt" to the
			// set of unresolved names, not "Println".)
			ast.Inspect(.X, )
			return false
		case *ast.KeyValueExpr:
			// For key value expressions, only inspect the value
			// as the key should be resolved by the type of the
			// composite literal.
			ast.Inspect(.Value, )
			return false
		}
		return true
	}
	ast.Inspect(, )
	for  := 0;  < len(); ++ {
		switch d := [].(type) {
		case *ast.FuncDecl:
			// Inspect types of parameters and results. See #28492.
			if .Type.Params != nil {
				for ,  := range .Type.Params.List {
					ast.Inspect(.Type, )
				}
			}
			if .Type.Results != nil {
				for ,  := range .Type.Results.List {
					ast.Inspect(.Type, )
				}
			}

			ast.Inspect(.Body, )
		case *ast.GenDecl:
			for ,  := range .Specs {
				switch s := .(type) {
				case *ast.TypeSpec:
					ast.Inspect(.Type, )

					 = append(, [.Name.Name]...)
				case *ast.ValueSpec:
					if .Type != nil {
						ast.Inspect(.Type, )
					}
					for ,  := range .Values {
						ast.Inspect(, )
					}
				}
			}
		}
	}

	// Remove predeclared identifiers from unresolved list.
	for  := range  {
		if predeclaredTypes[] || predeclaredConstants[] || predeclaredFuncs[] {
			delete(, )
		}
	}

	// Use unresolved identifiers to determine the imports used by this
	// example. The heuristic assumes package names match base import
	// paths for imports w/o renames (should be good enough most of the time).
	 := make(map[string]string) // [name]path
	var  []ast.Spec             // _ imports
	for ,  := range .Imports {
		,  := strconv.Unquote(.Path.Value)
		if  != nil {
			continue
		}
		if  == "syscall/js" {
			// We don't support examples that import syscall/js,
			// because the package syscall/js is not available in the playground.
			return nil
		}
		 := path.Base()
		if .Name != nil {
			 = .Name.Name
			switch  {
			case "_":
				 = append(, )
				continue
			case ".":
				// We can't resolve dot imports (yet).
				return nil
			}
		}
		if [] {
			[] = 
			delete(, )
		}
	}

	// If there are other unresolved identifiers, give up because this
	// synthesized file is not going to build.
	if len() > 0 {
		return nil
	}

	// Include documentation belonging to blank imports.
	var  []*ast.CommentGroup
	for ,  := range  {
		if  := .(*ast.ImportSpec).Doc;  != nil {
			 = append(, )
		}
	}

	// Include comments that are inside the function body.
	for ,  := range .Comments {
		if .Pos() <= .Pos() && .End() <= .End() {
			 = append(, )
		}
	}

	// Strip the "Output:" or "Unordered output:" comment and adjust body
	// end position.
	,  = stripOutputComment(, )

	// Include documentation belonging to dependent declarations.
	for ,  := range  {
		switch d := .(type) {
		case *ast.GenDecl:
			if .Doc != nil {
				 = append(, .Doc)
			}
		case *ast.FuncDecl:
			if .Doc != nil {
				 = append(, .Doc)
			}
		}
	}

	// Synthesize import declaration.
	 := &ast.GenDecl{
		Tok:    token.IMPORT,
		Lparen: 1, // Need non-zero Lparen and Rparen so that printer
		Rparen: 1, // treats this as a factored import.
	}
	for ,  := range  {
		 := &ast.ImportSpec{Path: &ast.BasicLit{Value: strconv.Quote()}}
		if path.Base() !=  {
			.Name = ast.NewIdent()
		}
		.Specs = append(.Specs, )
	}
	.Specs = append(.Specs, ...)

	// Synthesize main function.
	 := &ast.FuncDecl{
		Name: ast.NewIdent("main"),
		Type: .Type,
		Body: ,
	}

	 := make([]ast.Decl, 0, 2+len())
	 = append(, )
	 = append(, ...)
	 = append(, )

	sort.Slice(, func(,  int) bool {
		return [].Pos() < [].Pos()
	})

	sort.Slice(, func(,  int) bool {
		return [].Pos() < [].Pos()
	})

	// Synthesize file.
	return &ast.File{
		Name:     ast.NewIdent("main"),
		Decls:    ,
		Comments: ,
	}
}

// playExampleFile takes a whole file example and synthesizes a new *ast.File
// such that the example is function main in package main.
func playExampleFile( *ast.File) *ast.File {
	// Strip copyright comment if present.
	 := .Comments
	if len() > 0 && strings.HasPrefix([0].Text(), "Copyright") {
		 = [1:]
	}

	// Copy declaration slice, rewriting the ExampleX function to main.
	var  []ast.Decl
	for ,  := range .Decls {
		if ,  := .(*ast.FuncDecl);  && isTest(.Name.Name, "Example") {
			// Copy the FuncDecl, as it may be used elsewhere.
			 := *
			.Name = ast.NewIdent("main")
			.Body,  = stripOutputComment(.Body, )
			 = &
		}
		 = append(, )
	}

	// Copy the File, as it may be used elsewhere.
	 := *
	.Name = ast.NewIdent("main")
	.Decls = 
	.Comments = 
	return &
}

// stripOutputComment finds and removes the "Output:" or "Unordered output:"
// comment from body and comments, and adjusts the body block's end position.
func stripOutputComment( *ast.BlockStmt,  []*ast.CommentGroup) (*ast.BlockStmt, []*ast.CommentGroup) {
	// Do nothing if there is no "Output:" or "Unordered output:" comment.
	,  := lastComment(, )
	if  == nil || !outputPrefix.MatchString(.Text()) {
		return , 
	}

	// Copy body and comments, as the originals may be used elsewhere.
	 := &ast.BlockStmt{
		Lbrace: .Lbrace,
		List:   .List,
		Rbrace: .Pos(),
	}
	 := make([]*ast.CommentGroup, len()-1)
	copy(, [:])
	copy([:], [+1:])
	return , 
}

// lastComment returns the last comment inside the provided block.
func lastComment( *ast.BlockStmt,  []*ast.CommentGroup) ( int,  *ast.CommentGroup) {
	if  == nil {
		return
	}
	,  := .Pos(), .End()
	for ,  := range  {
		if .Pos() <  {
			continue
		}
		if .End() >  {
			break
		}
		,  = , 
	}
	return
}

// classifyExamples classifies examples and assigns them to the Examples field
// of the relevant Func, Type, or Package that the example is associated with.
//
// The classification process is ambiguous in some cases:
//
// 	- ExampleFoo_Bar matches a type named Foo_Bar
// 	  or a method named Foo.Bar.
// 	- ExampleFoo_bar matches a type named Foo_bar
// 	  or Foo (with a "bar" suffix).
//
// Examples with malformed names are not associated with anything.
//
func classifyExamples( *Package,  []*Example) {
	if len() == 0 {
		return
	}

	// Mapping of names for funcs, types, and methods to the example listing.
	 := make(map[string]*[]*Example)
	[""] = &.Examples // package-level examples have an empty name
	for ,  := range .Funcs {
		if !token.IsExported(.Name) {
			continue
		}
		[.Name] = &.Examples
	}
	for ,  := range .Types {
		if !token.IsExported(.Name) {
			continue
		}
		[.Name] = &.Examples
		for ,  := range .Funcs {
			if !token.IsExported(.Name) {
				continue
			}
			[.Name] = &.Examples
		}
		for ,  := range .Methods {
			if !token.IsExported(.Name) {
				continue
			}
			[strings.TrimPrefix(.Recv, "*")+"_"+.Name] = &.Examples
		}
	}

	// Group each example with the associated func, type, or method.
	for ,  := range  {
		// Consider all possible split points for the suffix
		// by starting at the end of string (no suffix case),
		// then trying all positions that contain a '_' character.
		//
		// An association is made on the first successful match.
		// Examples with malformed names that match nothing are skipped.
		for  := len(.Name);  >= 0;  = strings.LastIndexByte(.Name[:], '_') {
			, ,  := splitExampleName(.Name, )
			if ! {
				continue
			}
			,  := []
			if ! {
				continue
			}
			.Suffix = 
			* = append(*, )
			break
		}
	}

	// Sort list of example according to the user-specified suffix name.
	for ,  := range  {
		sort.Slice((*), func(,  int) bool {
			return (*)[].Suffix < (*)[].Suffix
		})
	}
}

// splitExampleName attempts to split example name s at index i,
// and reports if that produces a valid split. The suffix may be
// absent. Otherwise, it must start with a lower-case letter and
// be preceded by '_'.
//
// One of i == len(s) or s[i] == '_' must be true.
func splitExampleName( string,  int) (,  string,  bool) {
	if  == len() {
		return , "", true
	}
	if  == len()-1 {
		return "", "", false
	}
	,  = [:], [+1:]
	return , , isExampleSuffix()
}

func isExampleSuffix( string) bool {
	,  := utf8.DecodeRuneInString()
	return  > 0 && unicode.IsLower()
}