// 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 (
	
	
)

// GDesc contains statistics and execution details of a single goroutine.
type GDesc struct {
	ID           uint64
	Name         string
	PC           uint64
	CreationTime int64
	StartTime    int64
	EndTime      int64

	// List of regions in the goroutine, sorted based on the start time.
	Regions []*UserRegionDesc

	// Statistics of execution time during the goroutine execution.
	GExecutionStat

	*gdesc // private part.
}

// UserRegionDesc represents a region and goroutine execution stats
// while the region was active.
type UserRegionDesc struct {
	TaskID uint64
	Name   string

	// Region start event. Normally EvUserRegion start event or nil,
	// but can be EvGoCreate event if the region is a synthetic
	// region representing task inheritance from the parent goroutine.
	Start *Event

	// Region end event. Normally EvUserRegion end event or nil,
	// but can be EvGoStop or EvGoEnd event if the goroutine
	// terminated without explicitly ending the region.
	End *Event

	GExecutionStat
}

// GExecutionStat contains statistics about a goroutine's execution
// during a period of time.
type GExecutionStat struct {
	ExecTime      int64
	SchedWaitTime int64
	IOTime        int64
	BlockTime     int64
	SyscallTime   int64
	GCTime        int64
	SweepTime     int64
	TotalTime     int64
}

// sub returns the stats v-s.
func ( GExecutionStat) ( GExecutionStat) ( GExecutionStat) {
	 = 
	.ExecTime -= .ExecTime
	.SchedWaitTime -= .SchedWaitTime
	.IOTime -= .IOTime
	.BlockTime -= .BlockTime
	.SyscallTime -= .SyscallTime
	.GCTime -= .GCTime
	.SweepTime -= .SweepTime
	.TotalTime -= .TotalTime
	return 
}

// snapshotStat returns the snapshot of the goroutine execution statistics.
// This is called as we process the ordered trace event stream. lastTs and
// activeGCStartTime are used to process pending statistics if this is called
// before any goroutine end event.
func ( *GDesc) (,  int64) ( GExecutionStat) {
	 = .GExecutionStat

	if .gdesc == nil {
		return  // finalized GDesc. No pending state.
	}

	if  != 0 { // terminating while GC is active
		if .CreationTime <  {
			.GCTime +=  - 
		} else {
			// The goroutine's lifetime completely overlaps
			// with a GC.
			.GCTime +=  - .CreationTime
		}
	}

	if .TotalTime == 0 {
		.TotalTime =  - .CreationTime
	}

	if .lastStartTime != 0 {
		.ExecTime +=  - .lastStartTime
	}
	if .blockNetTime != 0 {
		.IOTime +=  - .blockNetTime
	}
	if .blockSyncTime != 0 {
		.BlockTime +=  - .blockSyncTime
	}
	if .blockSyscallTime != 0 {
		.SyscallTime +=  - .blockSyscallTime
	}
	if .blockSchedTime != 0 {
		.SchedWaitTime +=  - .blockSchedTime
	}
	if .blockSweepTime != 0 {
		.SweepTime +=  - .blockSweepTime
	}
	return 
}

// finalize is called when processing a goroutine end event or at
// the end of trace processing. This finalizes the execution stat
// and any active regions in the goroutine, in which case trigger is nil.
func ( *GDesc) (,  int64,  *Event) {
	if  != nil {
		.EndTime = .Ts
	}
	 := .snapshotStat(, )

	.GExecutionStat = 

	// System goroutines are never part of regions, even though they
	// "inherit" a task due to creation (EvGoCreate) from within a region.
	// This may happen e.g. if the first GC is triggered within a region,
	// starting the GC worker goroutines.
	if !IsSystemGoroutine(.Name) {
		for ,  := range .activeRegions {
			.End = 
			.GExecutionStat = .sub(.GExecutionStat)
			.Regions = append(.Regions, )
		}
	}
	*(.gdesc) = gdesc{}
}

// gdesc is a private part of GDesc that is required only during analysis.
type gdesc struct {
	lastStartTime    int64
	blockNetTime     int64
	blockSyncTime    int64
	blockSyscallTime int64
	blockSweepTime   int64
	blockGCTime      int64
	blockSchedTime   int64

	activeRegions []*UserRegionDesc // stack of active regions
}

// GoroutineStats generates statistics for all goroutines in the trace.
func ( []*Event) map[uint64]*GDesc {
	 := make(map[uint64]*GDesc)
	var  int64
	var  int64 // gcStartTime == 0 indicates gc is inactive.
	for ,  := range  {
		 = .Ts
		switch .Type {
		case EvGoCreate:
			 := &GDesc{ID: .Args[0], CreationTime: .Ts, gdesc: new(gdesc)}
			.blockSchedTime = .Ts
			// When a goroutine is newly created, inherit the task
			// of the active region. For ease handling of this
			// case, we create a fake region description with the
			// task id. This isn't strictly necessary as this
			// goroutine may not be associated with the task, but
			// it can be convenient to see all children created
			// during a region.
			if  := [.G];  != nil && len(.gdesc.activeRegions) > 0 {
				 := .gdesc.activeRegions
				 := [len()-1]
				if .TaskID != 0 {
					.gdesc.activeRegions = []*UserRegionDesc{
						{TaskID: .TaskID, Start: },
					}
				}
			}
			[.ID] = 
		case EvGoStart, EvGoStartLabel:
			 := [.G]
			if .PC == 0 && len(.Stk) > 0 {
				.PC = .Stk[0].PC
				.Name = .Stk[0].Fn
			}
			.lastStartTime = .Ts
			if .StartTime == 0 {
				.StartTime = .Ts
			}
			if .blockSchedTime != 0 {
				.SchedWaitTime += .Ts - .blockSchedTime
				.blockSchedTime = 0
			}
		case EvGoEnd, EvGoStop:
			 := [.G]
			.finalize(.Ts, , )
		case EvGoBlockSend, EvGoBlockRecv, EvGoBlockSelect,
			EvGoBlockSync, EvGoBlockCond:
			 := [.G]
			.ExecTime += .Ts - .lastStartTime
			.lastStartTime = 0
			.blockSyncTime = .Ts
		case EvGoSched, EvGoPreempt:
			 := [.G]
			.ExecTime += .Ts - .lastStartTime
			.lastStartTime = 0
			.blockSchedTime = .Ts
		case EvGoSleep, EvGoBlock:
			 := [.G]
			.ExecTime += .Ts - .lastStartTime
			.lastStartTime = 0
		case EvGoBlockNet:
			 := [.G]
			.ExecTime += .Ts - .lastStartTime
			.lastStartTime = 0
			.blockNetTime = .Ts
		case EvGoBlockGC:
			 := [.G]
			.ExecTime += .Ts - .lastStartTime
			.lastStartTime = 0
			.blockGCTime = .Ts
		case EvGoUnblock:
			 := [.Args[0]]
			if .blockNetTime != 0 {
				.IOTime += .Ts - .blockNetTime
				.blockNetTime = 0
			}
			if .blockSyncTime != 0 {
				.BlockTime += .Ts - .blockSyncTime
				.blockSyncTime = 0
			}
			.blockSchedTime = .Ts
		case EvGoSysBlock:
			 := [.G]
			.ExecTime += .Ts - .lastStartTime
			.lastStartTime = 0
			.blockSyscallTime = .Ts
		case EvGoSysExit:
			 := [.G]
			if .blockSyscallTime != 0 {
				.SyscallTime += .Ts - .blockSyscallTime
				.blockSyscallTime = 0
			}
			.blockSchedTime = .Ts
		case EvGCSweepStart:
			 := [.G]
			if  != nil {
				// Sweep can happen during GC on system goroutine.
				.blockSweepTime = .Ts
			}
		case EvGCSweepDone:
			 := [.G]
			if  != nil && .blockSweepTime != 0 {
				.SweepTime += .Ts - .blockSweepTime
				.blockSweepTime = 0
			}
		case EvGCStart:
			 = .Ts
		case EvGCDone:
			for ,  := range  {
				if .EndTime != 0 {
					continue
				}
				if  < .CreationTime {
					.GCTime += .Ts - .CreationTime
				} else {
					.GCTime += .Ts - 
				}
			}
			 = 0 // indicates gc is inactive.
		case EvUserRegion:
			 := [.G]
			switch  := .Args[1];  {
			case 0: // region start
				.activeRegions = append(.activeRegions, &UserRegionDesc{
					Name:           .SArgs[0],
					TaskID:         .Args[0],
					Start:          ,
					GExecutionStat: .snapshotStat(, ),
				})
			case 1: // region end
				var  *UserRegionDesc
				if  := .activeRegions; len() > 0 {
					 := len()
					 = [-1]
					 = [:-1] // pop
					.activeRegions = 
				} else {
					 = &UserRegionDesc{
						Name:   .SArgs[0],
						TaskID: .Args[0],
					}
				}
				.GExecutionStat = .snapshotStat(, ).sub(.GExecutionStat)
				.End = 
				.Regions = append(.Regions, )
			}
		}
	}

	for ,  := range  {
		.finalize(, , nil)

		// sort based on region start time
		sort.Slice(.Regions, func(,  int) bool {
			 := .Regions[].Start
			 := .Regions[].Start
			if  == nil {
				return true
			}
			if  == nil {
				return false
			}
			return .Ts < .Ts
		})

		.gdesc = nil
	}

	return 
}

// RelatedGoroutines finds a set of goroutines related to goroutine goid.
func ( []*Event,  uint64) map[uint64]bool {
	// BFS of depth 2 over "unblock" edges
	// (what goroutines unblock goroutine goid?).
	 := make(map[uint64]bool)
	[] = true
	for  := 0;  < 2; ++ {
		 := make(map[uint64]bool)
		for  := range  {
			[] = true
		}
		for ,  := range  {
			if .Type == EvGoUnblock && [.Args[0]] {
				[.G] = true
			}
		}
		 = 
	}
	[0] = true // for GC events
	return 
}

func ( string) bool {
	// This mimics runtime.isSystemGoroutine as closely as
	// possible.
	// Also, locked g in extra M (with empty entryFn) is system goroutine.
	return  == "" ||  != "runtime.main" && strings.HasPrefix(, "runtime.")
}