// Copyright 2014 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 trace

import (
	
	
	
	
	
	
	
	
	
	
	
	_ 
)

func goCmd() string {
	var  string
	if runtime.GOOS == "windows" {
		 = ".exe"
	}
	 := filepath.Join(runtime.GOROOT(), "bin", "go"+)
	if ,  := os.Stat();  == nil {
		return 
	}
	return "go"
}

// Event describes one event in the trace.
type Event struct {
	Off   int       // offset in input file (for debugging and error reporting)
	Type  byte      // one of Ev*
	seq   int64     // sequence number
	Ts    int64     // timestamp in nanoseconds
	P     int       // P on which the event happened (can be one of TimerP, NetpollP, SyscallP)
	G     uint64    // G on which the event happened
	StkID uint64    // unique stack ID
	Stk   []*Frame  // stack trace (can be empty)
	Args  [3]uint64 // event-type-specific arguments
	SArgs []string  // event-type-specific string args
	// linked event (can be nil), depends on event type:
	// for GCStart: the GCStop
	// for GCSTWStart: the GCSTWDone
	// for GCSweepStart: the GCSweepDone
	// for GoCreate: first GoStart of the created goroutine
	// for GoStart/GoStartLabel: the associated GoEnd, GoBlock or other blocking event
	// for GoSched/GoPreempt: the next GoStart
	// for GoBlock and other blocking events: the unblock event
	// for GoUnblock: the associated GoStart
	// for blocking GoSysCall: the associated GoSysExit
	// for GoSysExit: the next GoStart
	// for GCMarkAssistStart: the associated GCMarkAssistDone
	// for UserTaskCreate: the UserTaskEnd
	// for UserRegion: if the start region, the corresponding UserRegion end event
	Link *Event
}

// Frame is a frame in stack traces.
type Frame struct {
	PC   uint64
	Fn   string
	File string
	Line int
}

const (
	// Special P identifiers:
	FakeP    = 1000000 + iota
	TimerP   // depicts timer unblocks
	NetpollP // depicts network unblocks
	SyscallP // depicts returns from syscalls
	GCP      // depicts GC state
)

// ParseResult is the result of Parse.
type ParseResult struct {
	// Events is the sorted list of Events in the trace.
	Events []*Event
	// Stacks is the stack traces keyed by stack IDs from the trace.
	Stacks map[uint64][]*Frame
}

// Parse parses, post-processes and verifies the trace.
func ( io.Reader,  string) (ParseResult, error) {
	, ,  := parse(, )
	if  != nil {
		return ParseResult{}, 
	}
	if  < 1007 &&  == "" {
		return ParseResult{}, fmt.Errorf("for traces produced by go 1.6 or below, the binary argument must be provided")
	}
	return , nil
}

// parse parses, post-processes and verifies the trace. It returns the
// trace version and the list of events.
func parse( io.Reader,  string) (int, ParseResult, error) {
	, , ,  := readTrace()
	if  != nil {
		return 0, ParseResult{}, 
	}
	, ,  := parseEvents(, , )
	if  != nil {
		return 0, ParseResult{}, 
	}
	 = removeFutile()
	 = postProcessTrace(, )
	if  != nil {
		return 0, ParseResult{}, 
	}
	// Attach stack traces.
	for ,  := range  {
		if .StkID != 0 {
			.Stk = [.StkID]
		}
	}
	if  < 1007 &&  != "" {
		if  := symbolize(, );  != nil {
			return 0, ParseResult{}, 
		}
	}
	return , ParseResult{Events: , Stacks: }, nil
}

// rawEvent is a helper type used during parsing.
type rawEvent struct {
	off   int
	typ   byte
	args  []uint64
	sargs []string
}

// readTrace does wire-format parsing and verification.
// It does not care about specific event types and argument meaning.
func readTrace( io.Reader) ( int,  []rawEvent,  map[uint64]string,  error) {
	// Read and validate trace header.
	var  [16]byte
	,  := io.ReadFull(, [:])
	if  != nil {
		 = fmt.Errorf("failed to read header: read %v, err %v", , )
		return
	}
	,  = parseHeader([:])
	if  != nil {
		return
	}
	switch  {
	case 1005, 1007, 1008, 1009, 1010, 1011:
		// Note: When adding a new version, add canned traces
		// from the old version to the test suite using mkcanned.bash.
		break
	default:
		 = fmt.Errorf("unsupported trace file version %v.%v (update Go toolchain) %v", /1000, %1000, )
		return
	}

	// Read events.
	 = make(map[uint64]string)
	for {
		// Read event type and number of arguments (1 byte).
		 := 
		var  int
		,  = .Read([:1])
		if  == io.EOF {
			 = nil
			break
		}
		if  != nil ||  != 1 {
			 = fmt.Errorf("failed to read trace at offset 0x%x: n=%v err=%v", , , )
			return
		}
		 += 
		 := [0] << 2 >> 2
		 := [0]>>6 + 1
		 := byte(4)
		if  < 1007 {
			++
			++
		}
		if  == EvNone ||  >= EvCount || EventDescriptions[].minVersion >  {
			 = fmt.Errorf("unknown event type %v at offset 0x%x", , )
			return
		}
		if  == EvString {
			// String dictionary entry [ID, length, string].
			var  uint64
			, ,  = readVal(, )
			if  != nil {
				return
			}
			if  == 0 {
				 = fmt.Errorf("string at offset %d has invalid id 0", )
				return
			}
			if [] != "" {
				 = fmt.Errorf("string at offset %d has duplicate id %v", , )
				return
			}
			var  uint64
			, ,  = readVal(, )
			if  != nil {
				return
			}
			if  == 0 {
				 = fmt.Errorf("string at offset %d has invalid length 0", )
				return
			}
			if  > 1e6 {
				 = fmt.Errorf("string at offset %d has too large length %v", , )
				return
			}
			 := make([]byte, )
			var  int
			,  = io.ReadFull(, )
			if  != nil {
				 = fmt.Errorf("failed to read trace at offset %d: read %v, want %v, error %v", , , , )
				return
			}
			 += 
			[] = string()
			continue
		}
		 := rawEvent{typ: , off: }
		if  <  {
			for  := 0;  < int(); ++ {
				var  uint64
				, ,  = readVal(, )
				if  != nil {
					 = fmt.Errorf("failed to read event %v argument at offset %v (%v)", , , )
					return
				}
				.args = append(.args, )
			}
		} else {
			// More than inlineArgs args, the first value is length of the event in bytes.
			var  uint64
			, ,  = readVal(, )
			if  != nil {
				 = fmt.Errorf("failed to read event %v argument at offset %v (%v)", , , )
				return
			}
			 := 
			 := 
			for  > uint64(-) {
				, ,  = readVal(, )
				if  != nil {
					 = fmt.Errorf("failed to read event %v argument at offset %v (%v)", , , )
					return
				}
				.args = append(.args, )
			}
			if  != uint64(-) {
				 = fmt.Errorf("event has wrong length at offset 0x%x: want %v, got %v", , , -)
				return
			}
		}
		switch .typ {
		case EvUserLog: // EvUserLog records are followed by a value string of length ev.args[len(ev.args)-1]
			var  string
			, ,  = readStr(, )
			.sargs = append(.sargs, )
		}
		 = append(, )
	}
	return
}

func readStr( io.Reader,  int) ( string,  int,  error) {
	var  uint64
	, ,  = readVal(, )
	if  != nil ||  == 0 {
		return "", , 
	}
	if  > 1e6 {
		return "", , fmt.Errorf("string at offset %d is too large (len=%d)", , )
	}
	 := make([]byte, )
	,  := io.ReadFull(, )
	if  != nil ||  != uint64() {
		return "",  + , fmt.Errorf("failed to read trace at offset %d: read %v, want %v, error %v", , , , )
	}
	return string(),  + , nil
}

// parseHeader parses trace header of the form "go 1.7 trace\x00\x00\x00\x00"
// and returns parsed version as 1007.
func parseHeader( []byte) (int, error) {
	if len() != 16 {
		return 0, fmt.Errorf("bad header length")
	}
	if [0] != 'g' || [1] != 'o' || [2] != ' ' ||
		[3] < '1' || [3] > '9' ||
		[4] != '.' ||
		[5] < '1' || [5] > '9' {
		return 0, fmt.Errorf("not a trace file")
	}
	 := int([5] - '0')
	 := 0
	for ; [6+] >= '0' && [6+] <= '9' &&  < 2; ++ {
		 = *10 + int([6+]-'0')
	}
	 += int([3]-'0') * 1000
	if !bytes.Equal([6+:], []byte(" trace\x00\x00\x00\x00")[:10-]) {
		return 0, fmt.Errorf("not a trace file")
	}
	return , nil
}

// Parse events transforms raw events into events.
// It does analyze and verify per-event-type arguments.
func parseEvents( int,  []rawEvent,  map[uint64]string) ( []*Event,  map[uint64][]*Frame,  error) {
	var , ,  int64
	var  uint64
	var  int
	 := make(map[uint64]bool)
	 := make(map[int]uint64) // last goroutine running on P
	 = make(map[uint64][]*Frame)
	 := make(map[int][]*Event) // events by P
	for ,  := range  {
		 := EventDescriptions[.typ]
		if .Name == "" {
			 = fmt.Errorf("missing description for event type %v", .typ)
			return
		}
		 := argNum(, )
		if len(.args) !=  {
			 = fmt.Errorf("%v has wrong number of arguments at offset 0x%x: want %v, got %v",
				.Name, .off, , len(.args))
			return
		}
		switch .typ {
		case EvBatch:
			[] = 
			 = int(.args[0])
			 = []
			if  < 1007 {
				 = int64(.args[1])
				 = int64(.args[2])
			} else {
				 = int64(.args[1])
			}
		case EvFrequency:
			 = int64(.args[0])
			if  <= 0 {
				// The most likely cause for this is tick skew on different CPUs.
				// For example, solaris/amd64 seems to have wildly different
				// ticks on different CPUs.
				 = ErrTimeOrder
				return
			}
		case EvTimerGoroutine:
			[.args[0]] = true
		case EvStack:
			if len(.args) < 2 {
				 = fmt.Errorf("EvStack has wrong number of arguments at offset 0x%x: want at least 2, got %v",
					.off, len(.args))
				return
			}
			 := .args[1]
			if  > 1000 {
				 = fmt.Errorf("EvStack has bad number of frames at offset 0x%x: %v",
					.off, )
				return
			}
			 := 2 + 4*
			if  < 1007 {
				 = 2 + 
			}
			if uint64(len(.args)) !=  {
				 = fmt.Errorf("EvStack has wrong number of arguments at offset 0x%x: want %v, got %v",
					.off, , len(.args))
				return
			}
			 := .args[0]
			if  != 0 &&  > 0 {
				 := make([]*Frame, )
				for  := 0;  < int(); ++ {
					if  < 1007 {
						[] = &Frame{PC: .args[2+]}
					} else {
						 := .args[2+*4+0]
						 := .args[2+*4+1]
						 := .args[2+*4+2]
						 := .args[2+*4+3]
						[] = &Frame{PC: , Fn: [], File: [], Line: int()}
					}
				}
				[] = 
			}
		default:
			 := &Event{Off: .off, Type: .typ, P: , G: }
			var  int
			if  < 1007 {
				.seq =  + int64(.args[0])
				.Ts =  + int64(.args[1])
				 = .seq
				 = 2
			} else {
				.Ts =  + int64(.args[0])
				 = 1
			}
			 = .Ts
			for  := ;  < ; ++ {
				if  == -1 && .Stack {
					.StkID = .args[]
				} else {
					.Args[-] = .args[]
				}
			}
			switch .typ {
			case EvGoStart, EvGoStartLocal, EvGoStartLabel:
				 = .Args[0]
				.G = 
				if .typ == EvGoStartLabel {
					.SArgs = []string{[.Args[2]]}
				}
			case EvGCSTWStart:
				.G = 0
				switch .Args[0] {
				case 0:
					.SArgs = []string{"mark termination"}
				case 1:
					.SArgs = []string{"sweep termination"}
				default:
					 = fmt.Errorf("unknown STW kind %d", .Args[0])
					return
				}
			case EvGCStart, EvGCDone, EvGCSTWDone:
				.G = 0
			case EvGoEnd, EvGoStop, EvGoSched, EvGoPreempt,
				EvGoSleep, EvGoBlock, EvGoBlockSend, EvGoBlockRecv,
				EvGoBlockSelect, EvGoBlockSync, EvGoBlockCond, EvGoBlockNet,
				EvGoSysBlock, EvGoBlockGC:
				 = 0
			case EvGoSysExit, EvGoWaiting, EvGoInSyscall:
				.G = .Args[0]
			case EvUserTaskCreate:
				// e.Args 0: taskID, 1:parentID, 2:nameID
				.SArgs = []string{[.Args[2]]}
			case EvUserRegion:
				// e.Args 0: taskID, 1: mode, 2:nameID
				.SArgs = []string{[.Args[2]]}
			case EvUserLog:
				// e.Args 0: taskID, 1:keyID, 2: stackID
				.SArgs = []string{[.Args[1]], .sargs[0]}
			}
			[] = append([], )
		}
	}
	if len() == 0 {
		 = fmt.Errorf("trace is empty")
		return
	}
	if  == 0 {
		 = fmt.Errorf("no EvFrequency event")
		return
	}
	if BreakTimestampsForTesting {
		var  [][]*Event
		for ,  := range  {
			 = append(, )
		}
		for  := 0;  < 5; ++ {
			 := [rand.Intn(len())]
			[rand.Intn(len())].Ts += int64(rand.Intn(2000) - 1000)
		}
	}
	if  < 1007 {
		,  = order1005()
	} else {
		,  = order1007()
	}
	if  != nil {
		return
	}

	// Translate cpu ticks to real time.
	 := [0].Ts
	// Use floating point to avoid integer overflows.
	 := 1e9 / float64()
	for ,  := range  {
		.Ts = int64(float64(.Ts-) * )
		// Move timers and syscalls to separate fake Ps.
		if [.G] && .Type == EvGoUnblock {
			.P = TimerP
		}
		if .Type == EvGoSysExit {
			.P = SyscallP
		}
	}

	return
}

// removeFutile removes all constituents of futile wakeups (block, unblock, start).
// For example, a goroutine was unblocked on a mutex, but another goroutine got
// ahead and acquired the mutex before the first goroutine is scheduled,
// so the first goroutine has to block again. Such wakeups happen on buffered
// channels and sync.Mutex, but are generally not interesting for end user.
func removeFutile( []*Event) []*Event {
	// Two non-trivial aspects:
	// 1. A goroutine can be preempted during a futile wakeup and migrate to another P.
	//	We want to remove all of that.
	// 2. Tracing can start in the middle of a futile wakeup.
	//	That is, we can see a futile wakeup event w/o the actual wakeup before it.
	// postProcessTrace runs after us and ensures that we leave the trace in a consistent state.

	// Phase 1: determine futile wakeup sequences.
	type  struct {
		 bool
		 []*Event // wakeup sequence (subject for removal)
	}
	 := make(map[uint64])
	 := make(map[*Event]bool)
	for ,  := range  {
		switch .Type {
		case EvGoUnblock:
			 := [.Args[0]]
			. = []*Event{}
			[.Args[0]] = 
		case EvGoStart, EvGoPreempt, EvFutileWakeup:
			 := [.G]
			. = append(., )
			if .Type == EvFutileWakeup {
				. = true
			}
			[.G] = 
		case EvGoBlock, EvGoBlockSend, EvGoBlockRecv, EvGoBlockSelect, EvGoBlockSync, EvGoBlockCond:
			 := [.G]
			if . {
				[] = true
				for ,  := range . {
					[] = true
				}
			}
			delete(, .G)
		}
	}

	// Phase 2: remove futile wakeup sequences.
	 := [:0] // overwrite the original slice
	for ,  := range  {
		if ![] {
			 = append(, )
		}
	}
	return 
}

// ErrTimeOrder is returned by Parse when the trace contains
// time stamps that do not respect actual event ordering.
var ErrTimeOrder = fmt.Errorf("time stamps out of order")

// postProcessTrace does inter-event verification and information restoration.
// The resulting trace is guaranteed to be consistent
// (for example, a P does not run two Gs at the same time, or a G is indeed
// blocked before an unblock event).
func postProcessTrace( int,  []*Event) error {
	const (
		 = iota
		
		
		
	)
	type  struct {
		        int
		           *Event
		      *Event
		     *Event
		 *Event
	}
	type  struct {
		 bool
		       uint64
		   *Event
		 *Event
	}

	 := make(map[uint64])
	 := make(map[int])
	 := make(map[uint64]*Event)           // task id to task creation events
	 := make(map[uint64][]*Event) // goroutine id to stack of regions
	[0] = {: }
	var ,  *Event

	 := func( ,  ,  *Event,  bool) error {
		 := EventDescriptions[.Type].Name
		if . !=  {
			return fmt.Errorf("g %v is not running while %v (offset %v, time %v)", .G, , .Off, .Ts)
		}
		if . != .G {
			return fmt.Errorf("p %v is not running g %v while %v (offset %v, time %v)", .P, .G, , .Off, .Ts)
		}
		if ! && .G == 0 {
			return fmt.Errorf("g 0 did %v (offset %v, time %v)", EventDescriptions[.Type].Name, .Off, .Ts)
		}
		return nil
	}

	for ,  := range  {
		 := [.G]
		 := [.P]

		switch .Type {
		case EvProcStart:
			if . {
				return fmt.Errorf("p %v is running before start (offset %v, time %v)", .P, .Off, .Ts)
			}
			. = true
		case EvProcStop:
			if !. {
				return fmt.Errorf("p %v is not running before stop (offset %v, time %v)", .P, .Off, .Ts)
			}
			if . != 0 {
				return fmt.Errorf("p %v is running a goroutine %v during stop (offset %v, time %v)", .P, ., .Off, .Ts)
			}
			. = false
		case EvGCStart:
			if  != nil {
				return fmt.Errorf("previous GC is not ended before a new one (offset %v, time %v)", .Off, .Ts)
			}
			 = 
			// Attribute this to the global GC state.
			.P = GCP
		case EvGCDone:
			if  == nil {
				return fmt.Errorf("bogus GC end (offset %v, time %v)", .Off, .Ts)
			}
			.Link = 
			 = nil
		case EvGCSTWStart:
			 := &
			if  < 1010 {
				// Before 1.10, EvGCSTWStart was per-P.
				 = &.
			}
			if * != nil {
				return fmt.Errorf("previous STW is not ended before a new one (offset %v, time %v)", .Off, .Ts)
			}
			* = 
		case EvGCSTWDone:
			 := &
			if  < 1010 {
				// Before 1.10, EvGCSTWDone was per-P.
				 = &.
			}
			if * == nil {
				return fmt.Errorf("bogus STW end (offset %v, time %v)", .Off, .Ts)
			}
			(*).Link = 
			* = nil
		case EvGCSweepStart:
			if . != nil {
				return fmt.Errorf("previous sweeping is not ended before a new one (offset %v, time %v)", .Off, .Ts)
			}
			. = 
		case EvGCMarkAssistStart:
			if . != nil {
				return fmt.Errorf("previous mark assist is not ended before a new one (offset %v, time %v)", .Off, .Ts)
			}
			. = 
		case EvGCMarkAssistDone:
			// Unlike most events, mark assists can be in progress when a
			// goroutine starts tracing, so we can't report an error here.
			if . != nil {
				..Link = 
				. = nil
			}
		case EvGCSweepDone:
			if . == nil {
				return fmt.Errorf("bogus sweeping end (offset %v, time %v)", .Off, .Ts)
			}
			..Link = 
			. = nil
		case EvGoWaiting:
			if . !=  {
				return fmt.Errorf("g %v is not runnable before EvGoWaiting (offset %v, time %v)", .G, .Off, .Ts)
			}
			. = 
			. = 
		case EvGoInSyscall:
			if . !=  {
				return fmt.Errorf("g %v is not runnable before EvGoInSyscall (offset %v, time %v)", .G, .Off, .Ts)
			}
			. = 
			. = 
		case EvGoCreate:
			if  := (, , , true);  != nil {
				return 
			}
			if ,  := [.Args[0]];  {
				return fmt.Errorf("g %v already exists (offset %v, time %v)", .Args[0], .Off, .Ts)
			}
			[.Args[0]] = {: , : , : }
		case EvGoStart, EvGoStartLabel:
			if . !=  {
				return fmt.Errorf("g %v is not runnable before start (offset %v, time %v)", .G, .Off, .Ts)
			}
			if . != 0 {
				return fmt.Errorf("p %v is already running g %v while start g %v (offset %v, time %v)", .P, ., .G, .Off, .Ts)
			}
			. = 
			. = 
			. = .G
			if . != nil {
				if  < 1007 {
					// +1 because symbolizer expects return pc.
					.Stk = []*Frame{{PC: ..Args[1] + 1}}
				} else {
					.StkID = ..Args[1]
				}
				. = nil
			}

			if . != nil {
				..Link = 
				. = nil
			}
		case EvGoEnd, EvGoStop:
			if  := (, , , false);  != nil {
				return 
			}
			..Link = 
			. = nil
			. = 
			. = 0

			if .Type == EvGoEnd { // flush all active regions
				 := [.G]
				for ,  := range  {
					.Link = 
				}
				delete(, .G)
			}

		case EvGoSched, EvGoPreempt:
			if  := (, , , false);  != nil {
				return 
			}
			. = 
			..Link = 
			. = nil
			. = 0
			. = 
		case EvGoUnblock:
			if . !=  {
				return fmt.Errorf("g %v is not running while unpark (offset %v, time %v)", .G, .Off, .Ts)
			}
			if .P != TimerP && . != .G {
				return fmt.Errorf("p %v is not running g %v while unpark (offset %v, time %v)", .P, .G, .Off, .Ts)
			}
			 := [.Args[0]]
			if . !=  {
				return fmt.Errorf("g %v is not waiting before unpark (offset %v, time %v)", .Args[0], .Off, .Ts)
			}
			if . != nil && ..Type == EvGoBlockNet && .P != TimerP {
				.P = NetpollP
			}
			if . != nil {
				..Link = 
			}
			. = 
			. = 
			[.Args[0]] = 
		case EvGoSysCall:
			if  := (, , , false);  != nil {
				return 
			}
			. = 
		case EvGoSysBlock:
			if  := (, , , false);  != nil {
				return 
			}
			. = 
			..Link = 
			. = nil
			. = 0
		case EvGoSysExit:
			if . !=  {
				return fmt.Errorf("g %v is not waiting during syscall exit (offset %v, time %v)", .G, .Off, .Ts)
			}
			if . != nil && ..Type == EvGoSysCall {
				..Link = 
			}
			. = 
			. = 
		case EvGoSleep, EvGoBlock, EvGoBlockSend, EvGoBlockRecv,
			EvGoBlockSelect, EvGoBlockSync, EvGoBlockCond, EvGoBlockNet, EvGoBlockGC:
			if  := (, , , false);  != nil {
				return 
			}
			. = 
			. = 
			..Link = 
			. = nil
			. = 0
		case EvUserTaskCreate:
			 := .Args[0]
			if ,  := [];  {
				return fmt.Errorf("task id conflicts (id:%d), %q vs %q", , , )
			}
			[.Args[0]] = 
		case EvUserTaskEnd:
			 := .Args[0]
			if ,  := [];  {
				.Link = 
				delete(, )
			}
		case EvUserRegion:
			 := .Args[1]
			 := [.G]
			if  == 0 { // region start
				[.G] = append(, ) // push
			} else if  == 1 { // region end
				 := len()
				if  > 0 { // matching region start event is in the trace.
					 := [-1]
					if .Args[0] != .Args[0] || .SArgs[0] != .SArgs[0] { // task id, region name mismatch
						return fmt.Errorf("misuse of region in goroutine %d: span end %q when the inner-most active span start event is %q", .G, , )
					}
					// Link region start event with span end event
					.Link = 

					if  > 1 {
						[.G] = [:-1]
					} else {
						delete(, .G)
					}
				}
			} else {
				return fmt.Errorf("invalid user region mode: %q", )
			}
		}

		[.G] = 
		[.P] = 
	}

	// TODO(dvyukov): restore stacks for EvGoStart events.
	// TODO(dvyukov): test that all EvGoStart events has non-nil Link.

	return nil
}

// symbolize attaches func/file/line info to stack traces.
func symbolize( []*Event,  string) error {
	// First, collect and dedup all pcs.
	 := make(map[uint64]*Frame)
	for ,  := range  {
		for ,  := range .Stk {
			[.PC] = nil
		}
	}

	// Start addr2line.
	 := exec.Command(goCmd(), "tool", "addr2line", )
	,  := .StdinPipe()
	if  != nil {
		return fmt.Errorf("failed to pipe addr2line stdin: %v", )
	}
	.Stderr = os.Stderr
	,  := .StdoutPipe()
	if  != nil {
		return fmt.Errorf("failed to pipe addr2line stdout: %v", )
	}
	 = .Start()
	if  != nil {
		return fmt.Errorf("failed to start addr2line: %v", )
	}
	 := bufio.NewReader()

	// Write all pcs to addr2line.
	// Need to copy pcs to an array, because map iteration order is non-deterministic.
	var  []uint64
	for  := range  {
		 = append(, )
		,  := fmt.Fprintf(, "0x%x\n", -1)
		if  != nil {
			return fmt.Errorf("failed to write to addr2line: %v", )
		}
	}
	.Close()

	// Read in answers.
	for ,  := range  {
		,  := .ReadString('\n')
		if  != nil {
			return fmt.Errorf("failed to read from addr2line: %v", )
		}
		,  := .ReadString('\n')
		if  != nil {
			return fmt.Errorf("failed to read from addr2line: %v", )
		}
		 := &Frame{PC: }
		.Fn = [:len()-1]
		.File = [:len()-1]
		if  := strings.LastIndex(.File, ":");  != -1 {
			,  := strconv.Atoi(.File[+1:])
			if  == nil {
				.File = .File[:]
				.Line = 
			}
		}
		[] = 
	}
	.Wait()

	// Replace frames in events array.
	for ,  := range  {
		for ,  := range .Stk {
			.Stk[] = [.PC]
		}
	}

	return nil
}

// readVal reads unsigned base-128 value from r.
func readVal( io.Reader,  int) ( uint64,  int,  error) {
	 = 
	for  := 0;  < 10; ++ {
		var  [1]byte
		var  int
		,  = .Read([:])
		if  != nil ||  != 1 {
			return 0, 0, fmt.Errorf("failed to read trace at offset %d: read %v, error %v", , , )
		}
		++
		 |= uint64([0]&0x7f) << (uint() * 7)
		if [0]&0x80 == 0 {
			return
		}
	}
	return 0, 0, fmt.Errorf("bad value at offset 0x%x", )
}

// Print dumps events to stdout. For debugging.
func ( []*Event) {
	for ,  := range  {
		PrintEvent()
	}
}

// PrintEvent dumps the event to stdout. For debugging.
func ( *Event) {
	fmt.Printf("%s\n", )
}

func ( *Event) () string {
	 := EventDescriptions[.Type]
	 := new(bytes.Buffer)
	fmt.Fprintf(, "%v %v p=%v g=%v off=%v", .Ts, .Name, .P, .G, .Off)
	for ,  := range .Args {
		fmt.Fprintf(, " %v=%v", , .Args[])
	}
	for ,  := range .SArgs {
		fmt.Fprintf(, " %v=%v", , .SArgs[])
	}
	return .String()
}

// argNum returns total number of args for the event accounting for timestamps,
// sequence numbers and differences between trace format versions.
func argNum( rawEvent,  int) int {
	 := EventDescriptions[.typ]
	if .typ == EvStack {
		return len(.args)
	}
	 := len(.Args)
	if .Stack {
		++
	}
	switch .typ {
	case EvBatch, EvFrequency, EvTimerGoroutine:
		if  < 1007 {
			++ // there was an unused arg before 1.7
		}
		return 
	}
	++ // timestamp
	if  < 1007 {
		++ // sequence
	}
	switch .typ {
	case EvGCSweepDone:
		if  < 1009 {
			 -= 2 // 1.9 added two arguments
		}
	case EvGCStart, EvGoStart, EvGoUnblock:
		if  < 1007 {
			-- // 1.7 added an additional seq arg
		}
	case EvGCSTWStart:
		if  < 1010 {
			-- // 1.10 added an argument
		}
	}
	return 
}

// BreakTimestampsForTesting causes the parser to randomly alter timestamps (for testing of broken cputicks).
var BreakTimestampsForTesting bool

// Event types in the trace.
// Verbatim copy from src/runtime/trace.go with the "trace" prefix removed.
const (
	EvNone              = 0  // unused
	EvBatch             = 1  // start of per-P batch of events [pid, timestamp]
	EvFrequency         = 2  // contains tracer timer frequency [frequency (ticks per second)]
	EvStack             = 3  // stack [stack id, number of PCs, array of {PC, func string ID, file string ID, line}]
	EvGomaxprocs        = 4  // current value of GOMAXPROCS [timestamp, GOMAXPROCS, stack id]
	EvProcStart         = 5  // start of P [timestamp, thread id]
	EvProcStop          = 6  // stop of P [timestamp]
	EvGCStart           = 7  // GC start [timestamp, seq, stack id]
	EvGCDone            = 8  // GC done [timestamp]
	EvGCSTWStart        = 9  // GC mark termination start [timestamp, kind]
	EvGCSTWDone         = 10 // GC mark termination done [timestamp]
	EvGCSweepStart      = 11 // GC sweep start [timestamp, stack id]
	EvGCSweepDone       = 12 // GC sweep done [timestamp, swept, reclaimed]
	EvGoCreate          = 13 // goroutine creation [timestamp, new goroutine id, new stack id, stack id]
	EvGoStart           = 14 // goroutine starts running [timestamp, goroutine id, seq]
	EvGoEnd             = 15 // goroutine ends [timestamp]
	EvGoStop            = 16 // goroutine stops (like in select{}) [timestamp, stack]
	EvGoSched           = 17 // goroutine calls Gosched [timestamp, stack]
	EvGoPreempt         = 18 // goroutine is preempted [timestamp, stack]
	EvGoSleep           = 19 // goroutine calls Sleep [timestamp, stack]
	EvGoBlock           = 20 // goroutine blocks [timestamp, stack]
	EvGoUnblock         = 21 // goroutine is unblocked [timestamp, goroutine id, seq, stack]
	EvGoBlockSend       = 22 // goroutine blocks on chan send [timestamp, stack]
	EvGoBlockRecv       = 23 // goroutine blocks on chan recv [timestamp, stack]
	EvGoBlockSelect     = 24 // goroutine blocks on select [timestamp, stack]
	EvGoBlockSync       = 25 // goroutine blocks on Mutex/RWMutex [timestamp, stack]
	EvGoBlockCond       = 26 // goroutine blocks on Cond [timestamp, stack]
	EvGoBlockNet        = 27 // goroutine blocks on network [timestamp, stack]
	EvGoSysCall         = 28 // syscall enter [timestamp, stack]
	EvGoSysExit         = 29 // syscall exit [timestamp, goroutine id, seq, real timestamp]
	EvGoSysBlock        = 30 // syscall blocks [timestamp]
	EvGoWaiting         = 31 // denotes that goroutine is blocked when tracing starts [timestamp, goroutine id]
	EvGoInSyscall       = 32 // denotes that goroutine is in syscall when tracing starts [timestamp, goroutine id]
	EvHeapAlloc         = 33 // memstats.heap_live change [timestamp, heap_alloc]
	EvNextGC            = 34 // memstats.next_gc change [timestamp, next_gc]
	EvTimerGoroutine    = 35 // denotes timer goroutine [timer goroutine id]
	EvFutileWakeup      = 36 // denotes that the previous wakeup of this goroutine was futile [timestamp]
	EvString            = 37 // string dictionary entry [ID, length, string]
	EvGoStartLocal      = 38 // goroutine starts running on the same P as the last event [timestamp, goroutine id]
	EvGoUnblockLocal    = 39 // goroutine is unblocked on the same P as the last event [timestamp, goroutine id, stack]
	EvGoSysExitLocal    = 40 // syscall exit on the same P as the last event [timestamp, goroutine id, real timestamp]
	EvGoStartLabel      = 41 // goroutine starts running with label [timestamp, goroutine id, seq, label string id]
	EvGoBlockGC         = 42 // goroutine blocks on GC assist [timestamp, stack]
	EvGCMarkAssistStart = 43 // GC mark assist start [timestamp, stack]
	EvGCMarkAssistDone  = 44 // GC mark assist done [timestamp]
	EvUserTaskCreate    = 45 // trace.NewContext [timestamp, internal task id, internal parent id, stack, name string]
	EvUserTaskEnd       = 46 // end of task [timestamp, internal task id, stack]
	EvUserRegion        = 47 // trace.WithRegion [timestamp, internal task id, mode(0:start, 1:end), stack, name string]
	EvUserLog           = 48 // trace.Log [timestamp, internal id, key string id, stack, value string]
	EvCount             = 49
)

var EventDescriptions = [EvCount]struct {
	Name       string
	minVersion int
	Stack      bool
	Args       []string
	SArgs      []string // string arguments
}{
	EvNone:              {"None", 1005, false, []string{}, nil},
	EvBatch:             {"Batch", 1005, false, []string{"p", "ticks"}, nil}, // in 1.5 format it was {"p", "seq", "ticks"}
	EvFrequency:         {"Frequency", 1005, false, []string{"freq"}, nil},   // in 1.5 format it was {"freq", "unused"}
	EvStack:             {"Stack", 1005, false, []string{"id", "siz"}, nil},
	EvGomaxprocs:        {"Gomaxprocs", 1005, true, []string{"procs"}, nil},
	EvProcStart:         {"ProcStart", 1005, false, []string{"thread"}, nil},
	EvProcStop:          {"ProcStop", 1005, false, []string{}, nil},
	EvGCStart:           {"GCStart", 1005, true, []string{"seq"}, nil}, // in 1.5 format it was {}
	EvGCDone:            {"GCDone", 1005, false, []string{}, nil},
	EvGCSTWStart:        {"GCSTWStart", 1005, false, []string{"kindid"}, []string{"kind"}}, // <= 1.9, args was {} (implicitly {0})
	EvGCSTWDone:         {"GCSTWDone", 1005, false, []string{}, nil},
	EvGCSweepStart:      {"GCSweepStart", 1005, true, []string{}, nil},
	EvGCSweepDone:       {"GCSweepDone", 1005, false, []string{"swept", "reclaimed"}, nil}, // before 1.9, format was {}
	EvGoCreate:          {"GoCreate", 1005, true, []string{"g", "stack"}, nil},
	EvGoStart:           {"GoStart", 1005, false, []string{"g", "seq"}, nil}, // in 1.5 format it was {"g"}
	EvGoEnd:             {"GoEnd", 1005, false, []string{}, nil},
	EvGoStop:            {"GoStop", 1005, true, []string{}, nil},
	EvGoSched:           {"GoSched", 1005, true, []string{}, nil},
	EvGoPreempt:         {"GoPreempt", 1005, true, []string{}, nil},
	EvGoSleep:           {"GoSleep", 1005, true, []string{}, nil},
	EvGoBlock:           {"GoBlock", 1005, true, []string{}, nil},
	EvGoUnblock:         {"GoUnblock", 1005, true, []string{"g", "seq"}, nil}, // in 1.5 format it was {"g"}
	EvGoBlockSend:       {"GoBlockSend", 1005, true, []string{}, nil},
	EvGoBlockRecv:       {"GoBlockRecv", 1005, true, []string{}, nil},
	EvGoBlockSelect:     {"GoBlockSelect", 1005, true, []string{}, nil},
	EvGoBlockSync:       {"GoBlockSync", 1005, true, []string{}, nil},
	EvGoBlockCond:       {"GoBlockCond", 1005, true, []string{}, nil},
	EvGoBlockNet:        {"GoBlockNet", 1005, true, []string{}, nil},
	EvGoSysCall:         {"GoSysCall", 1005, true, []string{}, nil},
	EvGoSysExit:         {"GoSysExit", 1005, false, []string{"g", "seq", "ts"}, nil},
	EvGoSysBlock:        {"GoSysBlock", 1005, false, []string{}, nil},
	EvGoWaiting:         {"GoWaiting", 1005, false, []string{"g"}, nil},
	EvGoInSyscall:       {"GoInSyscall", 1005, false, []string{"g"}, nil},
	EvHeapAlloc:         {"HeapAlloc", 1005, false, []string{"mem"}, nil},
	EvNextGC:            {"NextGC", 1005, false, []string{"mem"}, nil},
	EvTimerGoroutine:    {"TimerGoroutine", 1005, false, []string{"g"}, nil}, // in 1.5 format it was {"g", "unused"}
	EvFutileWakeup:      {"FutileWakeup", 1005, false, []string{}, nil},
	EvString:            {"String", 1007, false, []string{}, nil},
	EvGoStartLocal:      {"GoStartLocal", 1007, false, []string{"g"}, nil},
	EvGoUnblockLocal:    {"GoUnblockLocal", 1007, true, []string{"g"}, nil},
	EvGoSysExitLocal:    {"GoSysExitLocal", 1007, false, []string{"g", "ts"}, nil},
	EvGoStartLabel:      {"GoStartLabel", 1008, false, []string{"g", "seq", "labelid"}, []string{"label"}},
	EvGoBlockGC:         {"GoBlockGC", 1008, true, []string{}, nil},
	EvGCMarkAssistStart: {"GCMarkAssistStart", 1009, true, []string{}, nil},
	EvGCMarkAssistDone:  {"GCMarkAssistDone", 1009, false, []string{}, nil},
	EvUserTaskCreate:    {"UserTaskCreate", 1011, true, []string{"taskid", "pid", "typeid"}, []string{"name"}},
	EvUserTaskEnd:       {"UserTaskEnd", 1011, true, []string{"taskid"}, nil},
	EvUserRegion:        {"UserRegion", 1011, true, []string{"taskid", "mode", "typeid"}, []string{"name"}},
	EvUserLog:           {"UserLog", 1011, true, []string{"id", "keyid"}, []string{"category", "message"}},
}