func rootedIn(root string, parts []string) string {
	for i := 1; i < len(parts); i++ {
		suffix := filepath.Join(parts[i:]...)
		if isFile(filepath.Join(root, suffix)) {
			return filepath.Join(parts[:i]...)
		}
	}
	return ""
}
isRootIn returns a root if the file split in parts is rooted in root.
package stack
import (
	"bufio"
	"bytes"
	"errors"
	"fmt"
	"io"
	"log"
	"math"
	"net/url"
	"os"
	"os/user"
	"path/filepath"
	"regexp"
	"runtime"
	"sort"
	"strconv"
	"strings"
	"unicode"
	"unicode/utf8"
)
const lockedToThread = "locked to thread"
var (
	reRoutineHeader = regexp.MustCompile("^goroutine (\\d+) \\[([^\\]]+)\\]\\:\r?\n$")
	reMinutes       = regexp.MustCompile("^(\\d+) minutes$")
	reUnavail       = regexp.MustCompile("^(?:\t| +)goroutine running on other thread; stack unavailable")
	reFile = regexp.MustCompile("^(?:\t| +)(\\?\\?|\\<autogenerated\\>|.+\\.(?:c|go|s))\\:(\\d+)(?:| \\+0x[0-9a-f]+)(?:| fp=0x[0-9a-f]+ sp=0x[0-9a-f]+)\r?\n$")
	reCreated = regexp.MustCompile("^created by (.+)\r?\n$")
	reFunc    = regexp.MustCompile("^(.+)\\((.*)\\)\r?\n$")
	reElided  = regexp.MustCompile("^\\.\\.\\.additional frames elided\\.\\.\\.\r?\n$")
	goroot string
	gopaths map[string]string
	localgoroot  = runtime.GOROOT()
	localgopaths = getGOPATHs()
)
type Function struct {
	Raw string
}
func (f Function) String() string {
	s, _ := url.QueryUnescape(f.Raw)
	return s
}
func (f Function) Name() string {
	parts := strings.SplitN(filepath.Base(f.Raw), ".", 2)
	if len(parts) == 1 {
		return parts[0]
	}
	return parts[1]
}
func (f Function) PkgName() string {
	parts := strings.SplitN(filepath.Base(f.Raw), ".", 2)
	if len(parts) == 1 {
		return ""
	}
	s, _ := url.QueryUnescape(parts[0])
	return s
}
func (f Function) PkgDotName() string {
	parts := strings.SplitN(filepath.Base(f.Raw), ".", 2)
	s, _ := url.QueryUnescape(parts[0])
	if len(parts) == 1 {
		return parts[0]
	}
	if s != "" || parts[1] != "" {
		return s + "." + parts[1]
	}
	return ""
}
func (f Function) IsExported() bool {
	name := f.Name()
	parts := strings.Split(name, ".")
	r, _ := utf8.DecodeRuneInString(parts[len(parts)-1])
	if unicode.ToUpper(r) == r {
		return true
	}
	return f.PkgName() == "main" && name == "main"
}
type Arg struct {
	Value uint64  
	Name  string  
}
func (a *Arg) IsPtr() bool {
	return a.Value > 16*1024*1024 && a.Value < math.MaxInt64
}
func (a Arg) String() string {
	if a.Name != "" {
		return a.Name
	}
	if a.Value == 0 {
		return "0"
	}
	return fmt.Sprintf("0x%x", a.Value)
}
type Args struct {
	Values    []Arg     
	Processed []string  
	Elided    bool      
}
func (a Args) String() string {
	var v []string
	if len(a.Processed) != 0 {
		v = make([]string, 0, len(a.Processed))
		for _, item := range a.Processed {
			v = append(v, item)
		}
	} else {
		v = make([]string, 0, len(a.Values))
		for _, item := range a.Values {
			v = append(v, item.String())
		}
	}
	if a.Elided {
		v = append(v, "...")
	}
	return strings.Join(v, ", ")
}
func (a *Args) Equal(r *Args) bool {
	if a.Elided != r.Elided || len(a.Values) != len(r.Values) {
		return false
	}
	for i, l := range a.Values {
		if l != r.Values[i] {
			return false
		}
	}
	return true
}
func (a *Args) Similar(r *Args, similar Similarity) bool {
	if a.Elided != r.Elided || len(a.Values) != len(r.Values) {
		return false
	}
	if similar == AnyValue {
		return true
	}
	for i, l := range a.Values {
		switch similar {
		case ExactFlags, ExactLines:
			if l != r.Values[i] {
				return false
			}
		default:
			if l.IsPtr() != r.Values[i].IsPtr() || (!l.IsPtr() && l != r.Values[i]) {
				return false
			}
		}
	}
	return true
}
func (a *Args) Merge(r *Args) Args {
	out := Args{
		Values: make([]Arg, len(a.Values)),
		Elided: a.Elided,
	}
	for i, l := range a.Values {
		if l != r.Values[i] {
			out.Values[i].Name = "*"
			out.Values[i].Value = l.Value
		} else {
			out.Values[i] = l
		}
	}
	return out
}
type Call struct {
	SourcePath string    
	Line       int       
	Func       Function  
	Args       Args      
}
func (c *Call) Equal(r *Call) bool {
	return c.SourcePath == r.SourcePath && c.Line == r.Line && c.Func == r.Func && c.Args.Equal(&r.Args)
}
func (c *Call) Similar(r *Call, similar Similarity) bool {
	return c.SourcePath == r.SourcePath && c.Line == r.Line && c.Func == r.Func && c.Args.Similar(&r.Args, similar)
}
func (c *Call) Merge(r *Call) Call {
	return Call{
		SourcePath: c.SourcePath,
		Line:       c.Line,
		Func:       c.Func,
		Args:       c.Args.Merge(&r.Args),
	}
}
func (c *Call) SourceName() string {
	return filepath.Base(c.SourcePath)
}
func (c *Call) SourceLine() string {
	return fmt.Sprintf("%s:%d", c.SourceName(), c.Line)
}
func (c *Call) LocalSourcePath() string {
	if strings.HasPrefix(c.SourcePath, goroot) {
		return filepath.Join(localgoroot, c.SourcePath[len(goroot):])
	}
	for prefix, dest := range gopaths {
		if strings.HasPrefix(c.SourcePath, prefix) {
			return filepath.Join(dest, c.SourcePath[len(prefix):])
		}
	}
	return c.SourcePath
}
func (c *Call) FullSourceLine() string {
	return fmt.Sprintf("%s:%d", c.SourcePath, c.Line)
}
func (c *Call) PkgSource() string {
	return filepath.Join(filepath.Base(filepath.Dir(c.SourcePath)), c.SourceName())
}
const testMainSource = "_test" + string(os.PathSeparator) + "_testmain.go"
func (c *Call) IsStdlib() bool {
	return (goroot != "" && strings.HasPrefix(c.SourcePath, goroot)) || c.PkgSource() == testMainSource
}
func (c *Call) IsPkgMain() bool {
	return c.Func.PkgName() == "main"
}
type Stack struct {
	Calls  []Call  
	Elided bool    
}
func (s *Stack) Equal(r *Stack) bool {
	if len(s.Calls) != len(r.Calls) || s.Elided != r.Elided {
		return false
	}
	for i := range s.Calls {
		if !s.Calls[i].Equal(&r.Calls[i]) {
			return false
		}
	}
	return true
}
func (s *Stack) Similar(r *Stack, similar Similarity) bool {
	if len(s.Calls) != len(r.Calls) || s.Elided != r.Elided {
		return false
	}
	for i := range s.Calls {
		if !s.Calls[i].Similar(&r.Calls[i], similar) {
			return false
		}
	}
	return true
}
func (s *Stack) Merge(r *Stack) *Stack {
	out := &Stack{
		Calls:  make([]Call, len(s.Calls)),
		Elided: s.Elided,
	}
	for i := range s.Calls {
		out.Calls[i] = s.Calls[i].Merge(&r.Calls[i])
	}
	return out
}
func (s *Stack) Less(r *Stack) bool {
	lStdlib := 0
	lPrivate := 0
	for _, c := range s.Calls {
		if c.IsStdlib() {
			lStdlib++
		} else {
			lPrivate++
		}
	}
	rStdlib := 0
	rPrivate := 0
	for _, s := range r.Calls {
		if s.IsStdlib() {
			rStdlib++
		} else {
			rPrivate++
		}
	}
	if lPrivate > rPrivate {
		return true
	}
	if lPrivate < rPrivate {
		return false
	}
	if lStdlib > rStdlib {
		return false
	}
	if lStdlib < rStdlib {
		return true
	}
	for x := range s.Calls {
		if s.Calls[x].Func.Raw < r.Calls[x].Func.Raw {
			return true
		}
		if s.Calls[x].Func.Raw > r.Calls[x].Func.Raw {
			return true
		}
		if s.Calls[x].PkgSource() < r.Calls[x].PkgSource() {
			return true
		}
		if s.Calls[x].PkgSource() > r.Calls[x].PkgSource() {
			return true
		}
		if s.Calls[x].Line < r.Calls[x].Line {
			return true
		}
		if s.Calls[x].Line > r.Calls[x].Line {
			return true
		}
	}
	return false
}
type Signature struct {
	State     string
	CreatedBy Call  
	SleepMin  int   
	SleepMax  int   
	Stack     Stack
	Locked    bool  
}
func (s *Signature) Equal(r *Signature) bool {
	if s.State != r.State || !s.CreatedBy.Equal(&r.CreatedBy) || s.Locked != r.Locked || s.SleepMin != r.SleepMin || s.SleepMax != r.SleepMax {
		return false
	}
	return s.Stack.Equal(&r.Stack)
}
func (s *Signature) Similar(r *Signature, similar Similarity) bool {
	if s.State != r.State || !s.CreatedBy.Similar(&r.CreatedBy, similar) {
		return false
	}
	if similar == ExactFlags && s.Locked != r.Locked {
		return false
	}
	return s.Stack.Similar(&r.Stack, similar)
}
func (s *Signature) Merge(r *Signature) *Signature {
	min := s.SleepMin
	if r.SleepMin < min {
		min = r.SleepMin
	}
	max := s.SleepMax
	if r.SleepMax > max {
		max = r.SleepMax
	}
	return &Signature{
		State:     s.State,      
		CreatedBy: s.CreatedBy,  
		SleepMin:  min,
		SleepMax:  max,
		Stack:     *s.Stack.Merge(&r.Stack),
		Locked:    s.Locked || r.Locked,  
	}
}
func (s *Signature) Less(r *Signature) bool {
	if s.Stack.Less(&r.Stack) {
		return true
	}
	if r.Stack.Less(&s.Stack) {
		return false
	}
	if s.Locked && !r.Locked {
		return true
	}
	if r.Locked && !s.Locked {
		return false
	}
	if s.State < r.State {
		return true
	}
	if s.State > r.State {
		return false
	}
	return false
}
type Goroutine struct {
	Signature       
	ID        int   
	First     bool  
}
func scanLines(data []byte, atEOF bool) (advance int, token []byte, err error) {
	if atEOF && len(data) == 0 {
		return 0, nil, nil
	}
	if i := bytes.IndexByte(data, '\n'); i >= 0 {
		return i + 1, data[0 : i+1], nil
	}
	if atEOF {
		return len(data), data, nil
	}
	if len(data) >= bufio.MaxScanTokenSize {
		return len(data), data, nil
	}
	return 0, nil, nil
}
func ParseDump(r io.Reader, out io.Writer) ([]Goroutine, error) {
	goroutines := make([]Goroutine, 0, 16)
	var goroutine *Goroutine
	scanner := bufio.NewScanner(r)
	scanner.Split(scanLines)
	created := false
	firstLine := false
	for scanner.Scan() {
		line := scanner.Text()
		if line == "\n" || line == "\r\n" {
			if goroutine != nil {
				goroutine = nil
				continue
			}
		} else if line[len(line)-1] == '\n' {
			if goroutine == nil {
				if match := reRoutineHeader.FindStringSubmatch(line); match != nil {
					if id, err := strconv.Atoi(match[1]); err == nil {
						items := strings.Split(match[2], ", ")
						sleep := 0
						locked := false
						for i := 1; i < len(items); i++ {
							if items[i] == lockedToThread {
								locked = true
								continue
							}
							if match2 := reMinutes.FindStringSubmatch(items[i]); match2 != nil {
								sleep, _ = strconv.Atoi(match2[1])
							}
						}
						goroutines = append(goroutines, Goroutine{
							Signature: Signature{
								State:    items[0],
								SleepMin: sleep,
								SleepMax: sleep,
								Locked:   locked,
							},
							ID:    id,
							First: len(goroutines) == 0,
						})
						goroutine = &goroutines[len(goroutines)-1]
						firstLine = true
						continue
					}
				}
			} else {
				if firstLine {
					firstLine = false
					if match := reUnavail.FindStringSubmatch(line); match != nil {
						goroutine.Stack.Calls = []Call{{SourcePath: "<unavailable>"}}
						continue
					}
				}
				if match := reFile.FindStringSubmatch(line); match != nil {
					num, err := strconv.Atoi(match[2])
					if err != nil {
						return goroutines, fmt.Errorf("failed to parse int on line: \"%s\"", line)
					}
					if created {
						created = false
						goroutine.CreatedBy.SourcePath = match[1]
						goroutine.CreatedBy.Line = num
					} else {
						i := len(goroutine.Stack.Calls) - 1
						if i < 0 {
							return goroutines, errors.New("unexpected order")
						}
						goroutine.Stack.Calls[i].SourcePath = match[1]
						goroutine.Stack.Calls[i].Line = num
					}
					continue
				}
				if match := reCreated.FindStringSubmatch(line); match != nil {
					created = true
					goroutine.CreatedBy.Func.Raw = match[1]
					continue
				}
				if match := reFunc.FindStringSubmatch(line); match != nil {
					args := Args{}
					for _, a := range strings.Split(match[2], ", ") {
						if a == "..." {
							args.Elided = true
							continue
						}
						if a == "" {
							break
						}
						v, err := strconv.ParseUint(a, 0, 64)
						if err != nil {
							return goroutines, fmt.Errorf("failed to parse int on line: \"%s\"", line)
						}
						args.Values = append(args.Values, Arg{Value: v})
					}
					goroutine.Stack.Calls = append(goroutine.Stack.Calls, Call{Func: Function{match[1]}, Args: args})
					continue
				}
				if match := reElided.FindStringSubmatch(line); match != nil {
					goroutine.Stack.Elided = true
					continue
				}
			}
		}
		_, _ = io.WriteString(out, line)
		goroutine = nil
	}
	nameArguments(goroutines)
	if goroot == "" {
		findRoots(goroutines)
	}
	return goroutines, scanner.Err()
}
func NoRebase() {
	goroot = runtime.GOROOT()
	gopaths = map[string]string{}
	for _, p := range getGOPATHs() {
		gopaths[p] = p
	}
}
func nameArguments(goroutines []Goroutine) {
	type object struct {
		args      []*Arg
		inPrimary bool
		id        int
	}
	objects := map[uint64]object{}
	for i := range goroutines {
		for j := range goroutines[i].Stack.Calls {
			for k := range goroutines[i].Stack.Calls[j].Args.Values {
				arg := goroutines[i].Stack.Calls[j].Args.Values[k]
				if arg.IsPtr() {
					objects[arg.Value] = object{
						args:      append(objects[arg.Value].args, &goroutines[i].Stack.Calls[j].Args.Values[k]),
						inPrimary: objects[arg.Value].inPrimary || i == 0,
					}
				}
			}
		}
	}
	order := make(uint64Slice, 0, len(objects)/2)
	for k, obj := range objects {
		if len(obj.args) > 1 && obj.inPrimary {
			order = append(order, k)
		}
	}
	sort.Sort(order)
	nextID := 1
	for _, k := range order {
		for _, arg := range objects[k].args {
			arg.Name = fmt.Sprintf("#%d", nextID)
		}
		nextID++
	}
	order = make(uint64Slice, 0, len(objects))
	for k := range objects {
		order = append(order, k)
	}
	sort.Sort(order)
	for _, k := range order {
		if objects[k].inPrimary {
			continue
		}
		for _, arg := range objects[k].args {
			arg.Name = fmt.Sprintf("#%d", nextID)
		}
		nextID++
	}
}
func hasPathPrefix(p string, s map[string]string) bool {
	for prefix := range s {
		if strings.HasPrefix(p, prefix+"/") {
			return true
		}
	}
	return false
}
func getFiles(goroutines []Goroutine) []string {
	files := map[string]struct{}{}
	for _, g := range goroutines {
		for _, c := range g.Stack.Calls {
			files[c.SourcePath] = struct{}{}
		}
	}
	out := make([]string, 0, len(files))
	for f := range files {
		out = append(out, f)
	}
	sort.Strings(out)
	return out
}
func splitPath(p string) []string {
	if p == "" {
		return nil
	}
	var out []string
	s := ""
	for _, c := range p {
		if c != '/' || (len(out) == 0 && strings.Count(s, "/") == len(s)) {
			s += string(c)
		} else if s != "" {
			out = append(out, s)
			s = ""
		}
	}
	if s != "" {
		out = append(out, s)
	}
	return out
}
func isFile(p string) bool {
	i, err := os.Stat(p)
	return err == nil && !i.IsDir()
}