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

// Summary is the analysis result produced by the summarizer.
type Summary struct {
	Goroutines map[GoID]*GoroutineSummary
	Tasks      map[TaskID]*UserTaskSummary
}

// GoroutineSummary contains statistics and execution details of a single goroutine.
// (For v2 traces.)
type GoroutineSummary struct {
	ID           GoID
	Name         string // A non-unique human-friendly identifier for the goroutine.
	PC           uint64 // The first PC we saw for the entry function of the goroutine
	CreationTime Time   // Timestamp of the first appearance in the trace.
	StartTime    Time   // Timestamp of the first time it started running. 0 if the goroutine never ran.
	EndTime      Time   // Timestamp of when the goroutine exited. 0 if the goroutine never exited.

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

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

	// goroutineSummary is state used just for computing this structure.
	// It's dropped before being returned to the caller.
	//
	// More specifically, if it's nil, it indicates that this summary has
	// already been finalized.
	*goroutineSummary
}

// UserTaskSummary represents a task in the trace.
type UserTaskSummary struct {
	ID       TaskID
	Name     string
	Parent   *UserTaskSummary // nil if the parent is unknown.
	Children []*UserTaskSummary

	// Task begin event. An EventTaskBegin event or nil.
	Start *Event

	// End end event. Normally EventTaskEnd event or nil.
	End *Event

	// Logs is a list of EventLog events associated with the task.
	Logs []*Event

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

	// Goroutines is the set of goroutines associated with this task.
	Goroutines map[GoID]*GoroutineSummary
}

// Complete returns true if we have complete information about the task
// from the trace: both a start and an end.
func ( *UserTaskSummary) () bool {
	return .Start != nil && .End != nil
}

// Descendents returns a slice consisting of itself (always the first task returned),
// and the transitive closure of all of its children.
func ( *UserTaskSummary) () []*UserTaskSummary {
	 := []*UserTaskSummary{}
	for ,  := range .Children {
		 = append(, .()...)
	}
	return 
}

// UserRegionSummary represents a region and goroutine execution stats
// while the region was active. (For v2 traces.)
type UserRegionSummary struct {
	TaskID TaskID
	Name   string

	// Region start event. Normally EventRegionBegin event or nil,
	// but can be a state transition event from NotExist or Undetermined
	// if the region is a synthetic region representing task inheritance
	// from the parent goroutine.
	Start *Event

	// Region end event. Normally EventRegionEnd event or nil,
	// but can be a state transition event to NotExist if the goroutine
	// terminated without explicitly ending the region.
	End *Event

	GoroutineExecStats
}

// GoroutineExecStats contains statistics about a goroutine's execution
// during a period of time.
type GoroutineExecStats struct {
	// These stats are all non-overlapping.
	ExecTime          time.Duration
	SchedWaitTime     time.Duration
	BlockTimeByReason map[string]time.Duration
	SyscallTime       time.Duration
	SyscallBlockTime  time.Duration

	// TotalTime is the duration of the goroutine's presence in the trace.
	// Necessarily overlaps with other stats.
	TotalTime time.Duration

	// Total time the goroutine spent in certain ranges; may overlap
	// with other stats.
	RangeTime map[string]time.Duration
}

func ( GoroutineExecStats) () map[string]time.Duration {
	 := map[string]time.Duration{
		"Execution time":         .ExecTime,
		"Sched wait time":        .SchedWaitTime,
		"Syscall execution time": .SyscallTime,
		"Block time (syscall)":   .SyscallBlockTime,
		"Unknown time":           .UnknownTime(),
	}
	for ,  := range .BlockTimeByReason {
		["Block time ("++")"] += 
	}
	// N.B. Don't include RangeTime or TotalTime; they overlap with these other
	// stats.
	return 
}

// UnknownTime returns whatever isn't accounted for in TotalTime.
func ( GoroutineExecStats) () time.Duration {
	 := .ExecTime + .SchedWaitTime + .SyscallTime +
		.SyscallBlockTime
	for ,  := range .BlockTimeByReason {
		 += 
	}
	// N.B. Don't include range time. Ranges overlap with
	// other stats, whereas these stats are non-overlapping.
	if  < .TotalTime {
		return .TotalTime - 
	}
	return 0
}

// sub returns the stats v-s.
func ( GoroutineExecStats) ( GoroutineExecStats) ( GoroutineExecStats) {
	 = .clone()
	.ExecTime -= .ExecTime
	.SchedWaitTime -= .SchedWaitTime
	for  := range .BlockTimeByReason {
		.BlockTimeByReason[] -= .BlockTimeByReason[]
	}
	.SyscallTime -= .SyscallTime
	.SyscallBlockTime -= .SyscallBlockTime
	.TotalTime -= .TotalTime
	for  := range .RangeTime {
		.RangeTime[] -= .RangeTime[]
	}
	return 
}

func ( GoroutineExecStats) () ( GoroutineExecStats) {
	 = 
	.BlockTimeByReason = make(map[string]time.Duration)
	for ,  := range .BlockTimeByReason {
		.BlockTimeByReason[] = 
	}
	.RangeTime = make(map[string]time.Duration)
	for ,  := range .RangeTime {
		.RangeTime[] = 
	}
	return 
}

// snapshotStat returns the snapshot of the goroutine execution statistics.
// This is called as we process the ordered trace event stream. lastTs is used
// to process pending statistics if this is called before any goroutine end event.
func ( *GoroutineSummary) ( Time) ( GoroutineExecStats) {
	 = .GoroutineExecStats.clone()

	if .goroutineSummary == nil {
		return  // Already finalized; no pending state.
	}

	// Set the total time if necessary.
	if .TotalTime == 0 {
		.TotalTime = .Sub(.CreationTime)
	}

	// Add in time since lastTs.
	if .lastStartTime != 0 {
		.ExecTime += .Sub(.lastStartTime)
	}
	if .lastRunnableTime != 0 {
		.SchedWaitTime += .Sub(.lastRunnableTime)
	}
	if .lastBlockTime != 0 {
		.BlockTimeByReason[.lastBlockReason] += .Sub(.lastBlockTime)
	}
	if .lastSyscallTime != 0 {
		.SyscallTime += .Sub(.lastSyscallTime)
	}
	if .lastSyscallBlockTime != 0 {
		.SchedWaitTime += .Sub(.lastSyscallBlockTime)
	}
	for ,  := range .lastRangeTime {
		.RangeTime[] += .Sub()
	}
	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 ( *GoroutineSummary) ( Time,  *Event) {
	if  != nil {
		.EndTime = .Time()
	}
	 := .snapshotStat()

	.GoroutineExecStats = 

	// 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 = 
			.GoroutineExecStats = .sub(.GoroutineExecStats)
			.Regions = append(.Regions, )
		}
	}
	*(.goroutineSummary) = goroutineSummary{}
}

// goroutineSummary is a private part of GoroutineSummary that is required only during analysis.
type goroutineSummary struct {
	lastStartTime        Time
	lastRunnableTime     Time
	lastBlockTime        Time
	lastBlockReason      string
	lastSyscallTime      Time
	lastSyscallBlockTime Time
	lastRangeTime        map[string]Time
	activeRegions        []*UserRegionSummary // stack of active regions
}

// Summarizer constructs per-goroutine time statistics for v2 traces.
type Summarizer struct {
	// gs contains the map of goroutine summaries we're building up to return to the caller.
	gs map[GoID]*GoroutineSummary

	// tasks contains the map of task summaries we're building up to return to the caller.
	tasks map[TaskID]*UserTaskSummary

	// syscallingP and syscallingG represent a binding between a P and G in a syscall.
	// Used to correctly identify and clean up after syscalls (blocking or otherwise).
	syscallingP map[ProcID]GoID
	syscallingG map[GoID]ProcID

	// rangesP is used for optimistic tracking of P-based ranges for goroutines.
	//
	// It's a best-effort mapping of an active range on a P to the goroutine we think
	// is associated with it.
	rangesP map[rangeP]GoID

	lastTs Time // timestamp of the last event processed.
	syncTs Time // timestamp of the last sync event processed (or the first timestamp in the trace).
}

// NewSummarizer creates a new struct to build goroutine stats from a trace.
func () *Summarizer {
	return &Summarizer{
		gs:          make(map[GoID]*GoroutineSummary),
		tasks:       make(map[TaskID]*UserTaskSummary),
		syscallingP: make(map[ProcID]GoID),
		syscallingG: make(map[GoID]ProcID),
		rangesP:     make(map[rangeP]GoID),
	}
}

type rangeP struct {
	id   ProcID
	name string
}

// Event feeds a single event into the stats summarizer.
func ( *Summarizer) ( *Event) {
	if .syncTs == 0 {
		.syncTs = .Time()
	}
	.lastTs = .Time()

	switch .Kind() {
	// Record sync time for the RangeActive events.
	case EventSync:
		.syncTs = .Time()

	// Handle state transitions.
	case EventStateTransition:
		 := .StateTransition()
		switch .Resource.Kind {
		// Handle goroutine transitions, which are the meat of this computation.
		case ResourceGoroutine:
			 := .Resource.Goroutine()
			,  := .Goroutine()
			if  ==  {
				// Skip these events; they're not telling us anything new.
				break
			}

			// Handle transition out.
			 := .gs[]
			switch  {
			case GoUndetermined, GoNotExist:
				 = &GoroutineSummary{ID: , goroutineSummary: &goroutineSummary{}}
				// If we're coming out of GoUndetermined, then the creation time is the
				// time of the last sync.
				if  == GoUndetermined {
					.CreationTime = .syncTs
				} else {
					.CreationTime = .Time()
				}
				// The goroutine is being created, or it's being named for the first time.
				.lastRangeTime = make(map[string]Time)
				.BlockTimeByReason = make(map[string]time.Duration)
				.RangeTime = make(map[string]time.Duration)

				// 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.
				//
				// N.B. ev.Goroutine() will always be NoGoroutine for the
				// Undetermined case, so this is will simply not fire.
				if  := .gs[.Goroutine()];  != nil && len(.activeRegions) > 0 {
					 := .activeRegions
					 := [len()-1]
					.activeRegions = []*UserRegionSummary{{TaskID: .TaskID, Start: }}
				}
				.gs[.ID] = 
			case GoRunning:
				// Record execution time as we transition out of running
				.ExecTime += .Time().Sub(.lastStartTime)
				.lastStartTime = 0
			case GoWaiting:
				// Record block time as we transition out of waiting.
				if .lastBlockTime != 0 {
					.BlockTimeByReason[.lastBlockReason] += .Time().Sub(.lastBlockTime)
					.lastBlockTime = 0
				}
			case GoRunnable:
				// Record sched latency time as we transition out of runnable.
				if .lastRunnableTime != 0 {
					.SchedWaitTime += .Time().Sub(.lastRunnableTime)
					.lastRunnableTime = 0
				}
			case GoSyscall:
				// Record syscall execution time and syscall block time as we transition out of syscall.
				if .lastSyscallTime != 0 {
					if .lastSyscallBlockTime != 0 {
						.SyscallBlockTime += .Time().Sub(.lastSyscallBlockTime)
						.SyscallTime += .lastSyscallBlockTime.Sub(.lastSyscallTime)
					} else {
						.SyscallTime += .Time().Sub(.lastSyscallTime)
					}
					.lastSyscallTime = 0
					.lastSyscallBlockTime = 0

					// Clear the syscall map.
					delete(.syscallingP, .syscallingG[])
					delete(.syscallingG, )
				}
			}

			// The goroutine hasn't been identified yet. Take the transition stack
			// and identify the goroutine by the root frame of that stack.
			// This root frame will be identical for all transitions on this
			// goroutine, because it represents its immutable start point.
			if .Name == "" {
				for  := range .Stack.Frames() {
					// NB: this PC won't actually be consistent for
					// goroutines which existed at the start of the
					// trace. The UI doesn't use it directly; this
					// mainly serves as an indication that we
					// actually saw a call stack for the goroutine
					.PC = .PC
					.Name = .Func
				}
			}

			// Handle transition in.
			switch  {
			case GoRunning:
				// We started running. Record it.
				.lastStartTime = .Time()
				if .StartTime == 0 {
					.StartTime = .Time()
				}
			case GoRunnable:
				.lastRunnableTime = .Time()
			case GoWaiting:
				if .Reason != "forever" {
					.lastBlockTime = .Time()
					.lastBlockReason = .Reason
					break
				}
				// "Forever" is like goroutine death.
				fallthrough
			case GoNotExist:
				.finalize(.Time(), )
			case GoSyscall:
				.syscallingP[.Proc()] = 
				.syscallingG[] = .Proc()
				.lastSyscallTime = .Time()
			}

		// Handle procs to detect syscall blocking, which si identifiable as a
		// proc going idle while the goroutine it was attached to is in a syscall.
		case ResourceProc:
			 := .Resource.Proc()
			,  := .Proc()
			if  !=  &&  == ProcIdle {
				if ,  := .syscallingP[];  {
					 := .gs[]
					.lastSyscallBlockTime = .Time()
					delete(.syscallingP, )
				}
			}
		}

	// Handle ranges of all kinds.
	case EventRangeBegin, EventRangeActive:
		 := .Range()
		var  *GoroutineSummary
		switch .Scope.Kind {
		case ResourceGoroutine:
			// Simple goroutine range. We attribute the entire range regardless of
			// goroutine stats. Lots of situations are still identifiable, e.g. a
			// goroutine blocked often in mark assist will have both high mark assist
			// and high block times. Those interested in a deeper view can look at the
			// trace viewer.
			 = .gs[.Scope.Goroutine()]
		case ResourceProc:
			// N.B. These ranges are not actually bound to the goroutine, they're
			// bound to the P. But if we happen to be on the P the whole time, let's
			// try to attribute it to the goroutine. (e.g. GC sweeps are here.)
			 = .gs[.Goroutine()]
			if  != nil {
				.rangesP[rangeP{id: .Scope.Proc(), name: .Name}] = .Goroutine()
			}
		}
		if  == nil {
			break
		}
		if .Kind() == EventRangeActive {
			if  := .lastRangeTime[.Name];  != 0 {
				.RangeTime[.Name] += .syncTs.Sub()
			}
			.lastRangeTime[.Name] = .syncTs
		} else {
			.lastRangeTime[.Name] = .Time()
		}
	case EventRangeEnd:
		 := .Range()
		var  *GoroutineSummary
		switch .Scope.Kind {
		case ResourceGoroutine:
			 = .gs[.Scope.Goroutine()]
		case ResourceProc:
			 := rangeP{id: .Scope.Proc(), name: .Name}
			if ,  := .rangesP[];  {
				if  == .Goroutine() {
					// As the comment in the RangeBegin case states, this is only OK
					// if we finish on the same goroutine we started on.
					 = .gs[]
				}
				delete(.rangesP, )
			}
		}
		if  == nil {
			break
		}
		 := .lastRangeTime[.Name]
		if  == 0 {
			break
		}
		.RangeTime[.Name] += .Time().Sub()
		delete(.lastRangeTime, .Name)

	// Handle user-defined regions.
	case EventRegionBegin:
		 := .gs[.Goroutine()]
		 := .Region()
		 := &UserRegionSummary{
			Name:               .Type,
			TaskID:             .Task,
			Start:              ,
			GoroutineExecStats: .snapshotStat(.Time()),
		}
		.activeRegions = append(.activeRegions, )
		// Associate the region and current goroutine to the task.
		 := .getOrAddTask(.Task)
		.Regions = append(.Regions, )
		.Goroutines[.ID] = 
	case EventRegionEnd:
		 := .gs[.Goroutine()]
		 := .Region()
		var  *UserRegionSummary
		if  := .activeRegions; len() > 0 {
			// Pop the top region from the stack since that's what must have ended.
			 := len()
			 = [-1]
			 = [:-1]
			.activeRegions = 
			// N.B. No need to add the region to a task; the EventRegionBegin already handled it.
		} else {
			// This is an "end" without a start. Just fabricate the region now.
			 = &UserRegionSummary{Name: .Type, TaskID: .Task}
			// Associate the region and current goroutine to the task.
			 := .getOrAddTask(.Task)
			.Goroutines[.ID] = 
			.Regions = append(.Regions, )
		}
		.GoroutineExecStats = .snapshotStat(.Time()).sub(.GoroutineExecStats)
		.End = 
		.Regions = append(.Regions, )

	// Handle tasks and logs.
	case EventTaskBegin, EventTaskEnd:
		// Initialize the task.
		 := .Task()
		 := .getOrAddTask(.ID)
		.Name = .Type
		.Goroutines[.Goroutine()] = .gs[.Goroutine()]
		if .Kind() == EventTaskBegin {
			.Start = 
		} else {
			.End = 
		}
		// Initialize the parent, if one exists and it hasn't been done yet.
		// We need to avoid doing it twice, otherwise we could appear twice
		// in the parent's Children list.
		if .Parent != NoTask && .Parent == nil {
			 := .getOrAddTask(.Parent)
			.Parent = 
			.Children = append(.Children, )
		}
	case EventLog:
		 := .Log()
		// Just add the log to the task. We'll create the task if it
		// doesn't exist (it's just been mentioned now).
		 := .getOrAddTask(.Task)
		.Goroutines[.Goroutine()] = .gs[.Goroutine()]
		.Logs = append(.Logs, )
	}
}

func ( *Summarizer) ( TaskID) *UserTaskSummary {
	 := .tasks[]
	if  == nil {
		 = &UserTaskSummary{ID: , Goroutines: make(map[GoID]*GoroutineSummary)}
		.tasks[] = 
	}
	return 
}

// Finalize indicates to the summarizer that we're done processing the trace.
// It cleans up any remaining state and returns the full summary.
func ( *Summarizer) () *Summary {
	for ,  := range .gs {
		.finalize(.lastTs, nil)

		// Sort based on region start time.
		slices.SortFunc(.Regions, func(,  *UserRegionSummary) int {
			 := .Start
			 := .Start
			if  == nil {
				if  == nil {
					return 0
				}
				return -1
			}
			if  == nil {
				return +1
			}
			return cmp.Compare(.Time(), .Time())
		})
		.goroutineSummary = nil
	}
	return &Summary{
		Goroutines: .gs,
		Tasks:      .tasks,
	}
}

// RelatedGoroutinesV2 finds a set of goroutines related to goroutine goid for v2 traces.
// The association is based on whether they have synchronized with each other in the Go
// scheduler (one has unblocked another).
func ( []Event,  GoID) map[GoID]struct{} {
	// Process all the events, looking for transitions of goroutines
	// out of GoWaiting. If there was an active goroutine when this
	// happened, then we know that active goroutine unblocked another.
	// Scribble all these down so we can process them.
	type  struct {
		 GoID
		  GoID
	}
	var  []
	for ,  := range  {
		if .Goroutine() == NoGoroutine {
			continue
		}
		if .Kind() != EventStateTransition {
			continue
		}
		 := .StateTransition()
		if .Resource.Kind != ResourceGoroutine {
			continue
		}
		 := .Resource.Goroutine()
		,  := .Goroutine()
		if  ==  ||  != GoWaiting {
			continue
		}
		 = append(, {
			: .Goroutine(),
			:  ,
		})
	}
	// Compute the transitive closure of depth 2 of goroutines that have unblocked each other
	// (starting from goid).
	 := make(map[GoID]struct{})
	[] = struct{}{}
	for  := 0;  < 2; ++ {
		// Copy the map.
		 := make(map[GoID]struct{})
		for  := range  {
			[] = struct{}{}
		}
		for ,  := range  {
			if ,  := [.];  {
				[.] = struct{}{}
			}
		}
		 = 
	}
	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.")
}