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

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

// GoroutineSummary contains statistics and execution details of a single goroutine.
// (For v2 traces.)
type GoroutineSummary struct {
	ID           tracev2.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 tracev2.Time // Timestamp of the first appearance in the trace.
	StartTime    tracev2.Time // Timestamp of the first time it started running. 0 if the goroutine never ran.
	EndTime      tracev2.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       tracev2.TaskID
	Name     string
	Parent   *UserTaskSummary // nil if the parent is unknown.
	Children []*UserTaskSummary

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

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

	// Logs is a list of tracev2.EventLog events associated with the task.
	Logs []*tracev2.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[tracev2.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 tracev2.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 *tracev2.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 *tracev2.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) ( tracev2.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) ( tracev2.Time,  *tracev2.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        tracev2.Time
	lastRunnableTime     tracev2.Time
	lastBlockTime        tracev2.Time
	lastBlockReason      string
	lastSyscallTime      tracev2.Time
	lastSyscallBlockTime tracev2.Time
	lastRangeTime        map[string]tracev2.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[tracev2.GoID]*GoroutineSummary

	// tasks contains the map of task summaries we're building up to return to the caller.
	tasks map[tracev2.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[tracev2.ProcID]tracev2.GoID
	syscallingG map[tracev2.GoID]tracev2.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]tracev2.GoID

	lastTs tracev2.Time // timestamp of the last event processed.
	syncTs tracev2.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[tracev2.GoID]*GoroutineSummary),
		tasks:       make(map[tracev2.TaskID]*UserTaskSummary),
		syscallingP: make(map[tracev2.ProcID]tracev2.GoID),
		syscallingG: make(map[tracev2.GoID]tracev2.ProcID),
		rangesP:     make(map[rangeP]tracev2.GoID),
	}
}

type rangeP struct {
	id   tracev2.ProcID
	name string
}

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

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

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

			// Handle transition out.
			 := .gs[]
			switch  {
			case tracev2.GoUndetermined, tracev2.GoNotExist:
				 = &GoroutineSummary{ID: , goroutineSummary: &goroutineSummary{}}
				// If we're coming out of GoUndetermined, then the creation time is the
				// time of the last sync.
				if  == tracev2.GoUndetermined {
					.CreationTime = .syncTs
				} else {
					.CreationTime = .Time()
				}
				// The goroutine is being created, or it's being named for the first time.
				.lastRangeTime = make(map[string]tracev2.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 tracev2.GoRunning:
				// Record execution time as we transition out of running
				.ExecTime += .Time().Sub(.lastStartTime)
				.lastStartTime = 0
			case tracev2.GoWaiting:
				// Record block time as we transition out of waiting.
				if .lastBlockTime != 0 {
					.BlockTimeByReason[.lastBlockReason] += .Time().Sub(.lastBlockTime)
					.lastBlockTime = 0
				}
			case tracev2.GoRunnable:
				// Record sched latency time as we transition out of runnable.
				if .lastRunnableTime != 0 {
					.SchedWaitTime += .Time().Sub(.lastRunnableTime)
					.lastRunnableTime = 0
				}
			case tracev2.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 == "" {
				 := .Stack
				if  != tracev2.NoStack {
					var  tracev2.StackFrame
					var  bool
					.Frames(func( tracev2.StackFrame) bool {
						 = 
						 = true
						return true
					})
					if  {
						// 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 tracev2.GoRunning:
				// We started running. Record it.
				.lastStartTime = .Time()
				if .StartTime == 0 {
					.StartTime = .Time()
				}
			case tracev2.GoRunnable:
				.lastRunnableTime = .Time()
			case tracev2.GoWaiting:
				if .Reason != "forever" {
					.lastBlockTime = .Time()
					.lastBlockReason = .Reason
					break
				}
				// "Forever" is like goroutine death.
				fallthrough
			case tracev2.GoNotExist:
				.finalize(.Time(), )
			case tracev2.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 tracev2.ResourceProc:
			 := .Resource.Proc()
			,  := .Proc()
			if  !=  &&  == tracev2.ProcIdle {
				if ,  := .syscallingP[];  {
					 := .gs[]
					.lastSyscallBlockTime = .Time()
					delete(.syscallingP, )
				}
			}
		}

	// Handle ranges of all kinds.
	case tracev2.EventRangeBegin, tracev2.EventRangeActive:
		 := .Range()
		var  *GoroutineSummary
		switch .Scope.Kind {
		case tracev2.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 tracev2.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() == tracev2.EventRangeActive {
			if  := .lastRangeTime[.Name];  != 0 {
				.RangeTime[.Name] += .syncTs.Sub()
			}
			.lastRangeTime[.Name] = .syncTs
		} else {
			.lastRangeTime[.Name] = .Time()
		}
	case tracev2.EventRangeEnd:
		 := .Range()
		var  *GoroutineSummary
		switch .Scope.Kind {
		case tracev2.ResourceGoroutine:
			 = .gs[.Scope.Goroutine()]
		case tracev2.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 tracev2.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 tracev2.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 tracev2.EventTaskBegin, tracev2.EventTaskEnd:
		// Initialize the task.
		 := .Task()
		 := .getOrAddTask(.ID)
		.Name = .Type
		.Goroutines[.Goroutine()] = .gs[.Goroutine()]
		if .Kind() == tracev2.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 != tracev2.NoTask && .Parent == nil {
			 := .getOrAddTask(.Parent)
			.Parent = 
			.Children = append(.Children, )
		}
	case tracev2.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) ( tracev2.TaskID) *UserTaskSummary {
	 := .tasks[]
	if  == nil {
		 = &UserTaskSummary{ID: , Goroutines: make(map[tracev2.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.
		sort.Slice(.Regions, func(,  int) bool {
			 := .Regions[].Start
			 := .Regions[].Start
			if  == nil {
				return true
			}
			if  == nil {
				return false
			}
			return .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 ( []tracev2.Event,  tracev2.GoID) map[tracev2.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 {
		 tracev2.GoID
		  tracev2.GoID
	}
	var  []
	for ,  := range  {
		if .Goroutine() == tracev2.NoGoroutine {
			continue
		}
		if .Kind() != tracev2.EventStateTransition {
			continue
		}
		 := .StateTransition()
		if .Resource.Kind != tracev2.ResourceGoroutine {
			continue
		}
		 := .Resource.Goroutine()
		,  := .Goroutine()
		if  ==  ||  != tracev2.GoWaiting {
			continue
		}
		 = append(, {
			: .Goroutine(),
			:  ,
		})
	}
	// Compute the transitive closure of depth 2 of goroutines that have unblocked each other
	// (starting from goid).
	 := make(map[tracev2.GoID]struct{})
	[] = struct{}{}
	for  := 0;  < 2; ++ {
		// Copy the map.
		 := make(map[tracev2.GoID]struct{})
		for  := range  {
			[] = struct{}{}
		}
		for ,  := range  {
			if ,  := [.];  {
				[.] = struct{}{}
			}
		}
		 = 
	}
	return 
}