// Copyright (c) 2017-2023 Uber Technologies, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

package stack

import (
	
	
	
	
	
	
	
)

const _defaultBufferSize = 64 * 1024 // 64 KiB

// Stack represents a single Goroutine's stack.
type Stack struct {
	id    int
	state string // e.g. 'running', 'chan receive'

	// The first function on the stack.
	firstFunction string

	// A set of all functions in the stack,
	allFunctions map[string]struct{}

	// Full, raw stack trace.
	fullStack string
}

// ID returns the goroutine ID.
func ( Stack) () int {
	return .id
}

// State returns the Goroutine's state.
func ( Stack) () string {
	return .state
}

// Full returns the full stack trace for this goroutine.
func ( Stack) () string {
	return .fullStack
}

// FirstFunction returns the name of the first function on the stack.
func ( Stack) () string {
	return .firstFunction
}

// HasFunction reports whether the stack has the given function
// anywhere in it.
func ( Stack) ( string) bool {
	,  := .allFunctions[]
	return 
}

func ( Stack) () string {
	return fmt.Sprintf(
		"Goroutine %v in state %v, with %v on top of the stack:\n%s",
		.id, .state, .firstFunction, .Full())
}

func ( bool) []Stack {
	 := getStackBuffer()
	,  := newStackParser(bytes.NewReader()).Parse()
	if  != nil {
		// Well-formed stack traces should never fail to parse.
		// If they do, it's a bug in this package.
		// Panic so we can fix it.
		panic(fmt.Sprintf("Failed to parse stack trace: %v\n%s", , ))
	}
	return 
}

type stackParser struct {
	scan   *scanner
	stacks []Stack
	errors []error
}

func ( io.Reader) *stackParser {
	return &stackParser{
		scan: newScanner(),
	}
}

func ( *stackParser) () ([]Stack, error) {
	for .scan.Scan() {
		 := .scan.Text()

		// If we see the goroutine header, start a new stack.
		if strings.HasPrefix(, "goroutine ") {
			,  := .parseStack()
			if  != nil {
				.errors = append(.errors, )
				continue
			}
			.stacks = append(.stacks, )
		}
	}

	.errors = append(.errors, .scan.Err())
	return .stacks, errors.Join(.errors...)
}

// parseStack parses a single stack trace from the given scanner.
// line is the first line of the stack trace, which should look like:
//
//	goroutine 123 [runnable]:
func ( *stackParser) ( string) (Stack, error) {
	, ,  := parseGoStackHeader()
	if  != nil {
		return Stack{}, fmt.Errorf("parse header: %w", )
	}

	// Read the rest of the stack trace.
	var (
		 string
		     bytes.Buffer
	)
	 := make(map[string]struct{})
	for .scan.Scan() {
		 := .scan.Text()
		if strings.HasPrefix(, "goroutine ") {
			// If we see the goroutine header,
			// it's the end of this stack.
			// Unscan so the next Scan sees the same line.
			.scan.Unscan()
			break
		}

		.WriteString()
		.WriteByte('\n') // scanner trims the newline

		if len() == 0 {
			// Empty line usually marks the end of the stack
			// but we don't want to have to rely on that.
			// Just skip it.
			continue
		}

		, ,  := parseFuncName()
		if  != nil {
			return Stack{}, fmt.Errorf("parse function: %w", )
		}
		if ! {
			// A function is part of a goroutine's stack
			// only if it's not a "created by" function.
			//
			// The creator function is part of a different stack.
			// We don't care about it right now.
			[] = struct{}{}
			if  == "" {
				 = 
			}

		}

		// The function name followed by a line in the form:
		//
		//	<tab>example.com/path/to/package/file.go:123 +0x123
		//
		// We don't care about the position so we can skip this line.
		if .scan.Scan() {
			// Be defensive:
			// Skip the line only if it starts with a tab.
			 := .scan.Bytes()
			if len() > 0 && [0] == '\t' {
				.Write()
				.WriteByte('\n')
			} else {
				// Put it back and let the next iteration handle it
				// if it doesn't start with a tab.
				.scan.Unscan()
			}
		}

		if  {
			// The "created by" line is the last line of the stack.
			// We can stop parsing now.
			//
			// Note that if tracebackancestors=N is set,
			// there may be more a traceback of the creator function
			// following the "created by" line,
			// but it should not be considered part of this stack.
			// e.g.,
			//
			// created by testing.(*T).Run in goroutine 1
			//         /usr/lib/go/src/testing/testing.go:1648 +0x3ad
			// [originating from goroutine 1]:
			// testing.(*T).Run(...)
			//         /usr/lib/go/src/testing/testing.go:1649 +0x3ad
			//
			break
		}
	}

	return Stack{
		id:            ,
		state:         ,
		firstFunction: ,
		allFunctions:  ,
		fullStack:     .String(),
	}, nil
}

// All returns the stacks for all running goroutines.
func () []Stack {
	return getStacks(true)
}

// Current returns the stack for the current goroutine.
func () Stack {
	return getStacks(false)[0]
}

func ( bool) []byte {
	for  := _defaultBufferSize; ;  *= 2 {
		 := make([]byte, )
		if  := runtime.Stack(, );  <  {
			return [:]
		}
	}
}

// Parses a single function from the given line.
// The line is in one of these formats:
//
//	example.com/path/to/package.funcName(args...)
//	example.com/path/to/package.(*typeName).funcName(args...)
//	created by example.com/path/to/package.funcName
//	created by example.com/path/to/package.funcName in goroutine [...]
//
// Also reports whether the line was a "created by" line.
func ( string) ( string,  bool,  error) {
	if ,  := strings.CutPrefix(, "created by ");  {
		// The function name is the part after "created by "
		// and before " in goroutine [...]".
		 := strings.Index(, " in goroutine")
		if  >= 0 {
			 = [:]
		}
		 = 
		 = true
	} else if  := strings.LastIndexByte(, '(');  >= 0 {
		// The function name is the part before the last '('.
		 = [:]
	}

	if  == "" {
		return "", false, fmt.Errorf("no function found: %q", )
	}

	return , , nil
}

// parseGoStackHeader parses a stack header that looks like:
// goroutine 643 [runnable]:\n
// And returns the goroutine ID, and the state.
func ( string) ( int,  string,  error) {
	// The scanner will have already trimmed the "\n",
	// but we'll guard against it just in case.
	//
	// Trimming them separately makes them both optional.
	 = strings.TrimSuffix(strings.TrimSuffix(, ":"), "\n")
	 := strings.SplitN(, " ", 3)
	if len() != 3 {
		return 0, "", fmt.Errorf("unexpected format: %q", )
	}

	,  := strconv.Atoi([1])
	if  != nil {
		return 0, "", fmt.Errorf("bad goroutine ID %q in line %q", [1], )
	}

	 = strings.TrimSuffix(strings.TrimPrefix([2], "["), "]")
	return , , nil
}