// 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.

// This file contains data types that all implementations of the trace format
// parser need to provide to the rest of the package.

package trace

import (
	
	
	

	
	
	
)

// maxArgs is the maximum number of arguments for "plain" events,
// i.e. anything that could reasonably be represented as a Base.
const maxArgs = 5

// baseEvent is the basic unprocessed event. This serves as a common
// fundamental data structure across.
type baseEvent struct {
	typ  event.Type
	time Time
	args [maxArgs - 1]uint64
}

// extra returns a slice representing extra available space in args
// that the parser can use to pass data up into Event.
func ( *baseEvent) ( version.Version) []uint64 {
	switch  {
	case version.Go122:
		return .args[len(go122.Specs()[.typ].Args)-1:]
	}
	panic(fmt.Sprintf("unsupported version: go 1.%d", ))
}

// evTable contains the per-generation data necessary to
// interpret an individual event.
type evTable struct {
	freq    frequency
	strings dataTable[stringID, string]
	stacks  dataTable[stackID, stack]

	// extraStrings are strings that get generated during
	// parsing but haven't come directly from the trace, so
	// they don't appear in strings.
	extraStrings   []string
	extraStringIDs map[string]extraStringID
	nextExtra      extraStringID
}

// addExtraString adds an extra string to the evTable and returns
// a unique ID for the string in the table.
func ( *evTable) ( string) extraStringID {
	if  == "" {
		return 0
	}
	if .extraStringIDs == nil {
		.extraStringIDs = make(map[string]extraStringID)
	}
	if ,  := .extraStringIDs[];  {
		return 
	}
	.nextExtra++
	 := .nextExtra
	.extraStrings = append(.extraStrings, )
	.extraStringIDs[] = 
	return 
}

// getExtraString returns the extra string for the provided ID.
// The ID must have been produced by addExtraString for this evTable.
func ( *evTable) ( extraStringID) string {
	if  == 0 {
		return ""
	}
	return .extraStrings[-1]
}

// dataTable is a mapping from EIs to Es.
type dataTable[ ~uint64,  any] struct {
	present []uint8
	dense   []
	sparse  map[]
}

// insert tries to add a mapping from id to s.
//
// Returns an error if a mapping for id already exists, regardless
// of whether or not s is the same in content. This should be used
// for validation during parsing.
func ( *dataTable[, ]) ( ,  ) error {
	if .sparse == nil {
		.sparse = make(map[])
	}
	if ,  := .get();  {
		return fmt.Errorf("multiple %Ts with the same ID: id=%d, new=%v, existing=%v", , , , )
	}
	.sparse[] = 
	return nil
}

// compactify attempts to compact sparse into dense.
//
// This is intended to be called only once after insertions are done.
func ( *dataTable[, ]) () {
	if .sparse == nil || len(.dense) != 0 {
		// Already compactified.
		return
	}
	// Find the range of IDs.
	 := (0)
	 := ^(0)
	for  := range .sparse {
		if  >  {
			 = 
		}
		if  <  {
			 = 
		}
	}
	if  >= math.MaxInt {
		// We can't create a slice big enough to hold maxID elements
		return
	}
	// We're willing to waste at most 2x memory.
	if int(-) > max(len(.sparse), 2*len(.sparse)) {
		return
	}
	if int() > len(.sparse) {
		return
	}
	 := int() + 1
	.present = make([]uint8, (+7)/8)
	.dense = make([], )
	for ,  := range .sparse {
		.dense[] = 
		.present[/8] |= uint8(1) << ( % 8)
	}
	.sparse = nil
}

// get returns the E for id or false if it doesn't
// exist. This should be used for validation during parsing.
func ( *dataTable[, ]) ( ) (, bool) {
	if  == 0 {
		return *new(), true
	}
	if uint64() < uint64(len(.dense)) {
		if .present[/8]&(uint8(1)<<(%8)) != 0 {
			return .dense[], true
		}
	} else if .sparse != nil {
		if ,  := .sparse[];  {
			return , true
		}
	}
	return *new(), false
}

// forEach iterates over all ID/value pairs in the data table.
func ( *dataTable[, ]) ( func(, ) bool) bool {
	for ,  := range .dense {
		if .present[/8]&(uint8(1)<<(%8)) == 0 {
			continue
		}
		if !((), ) {
			return false
		}
	}
	if .sparse == nil {
		return true
	}
	for ,  := range .sparse {
		if !(, ) {
			return false
		}
	}
	return true
}

// mustGet returns the E for id or panics if it fails.
//
// This should only be used if id has already been validated.
func ( *dataTable[, ]) ( )  {
	,  := .get()
	if ! {
		panic(fmt.Sprintf("expected id %d in %T table", , ))
	}
	return 
}

// frequency is nanoseconds per timestamp unit.
type frequency float64

// mul multiplies an unprocessed to produce a time in nanoseconds.
func ( frequency) ( timestamp) Time {
	return Time(float64() * float64())
}

// stringID is an index into the string table for a generation.
type stringID uint64

// extraStringID is an index into the extra string table for a generation.
type extraStringID uint64

// stackID is an index into the stack table for a generation.
type stackID uint64

// cpuSample represents a CPU profiling sample captured by the trace.
type cpuSample struct {
	schedCtx
	time  Time
	stack stackID
}

// asEvent produces a complete Event from a cpuSample. It needs
// the evTable from the generation that created it.
//
// We don't just store it as an Event in generation to minimize
// the amount of pointer data floating around.
func ( cpuSample) ( *evTable) Event {
	// TODO(mknyszek): This is go122-specific, but shouldn't be.
	// Generalize this in the future.
	 := Event{
		table: ,
		ctx:   .schedCtx,
		base: baseEvent{
			typ:  go122.EvCPUSample,
			time: .time,
		},
	}
	.base.args[0] = uint64(.stack)
	return 
}

// stack represents a goroutine stack sample.
type stack struct {
	frames []frame
}

func ( stack) () string {
	var  strings.Builder
	for ,  := range .frames {
		fmt.Fprintf(&, "\t%#v\n", )
	}
	return .String()
}

// frame represents a single stack frame.
type frame struct {
	pc     uint64
	funcID stringID
	fileID stringID
	line   uint64
}