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

type eventBatch struct {
	events   []*Event
	selected bool
}

type orderEvent struct {
	ev    *Event
	batch int
	g     uint64
	init  gState
	next  gState
}

type gStatus int

type gState struct {
	seq    uint64
	status gStatus
}

const (
	gDead gStatus = iota
	gRunnable
	gRunning
	gWaiting

	unordered = ^uint64(0)
	garbage   = ^uint64(0) - 1
	noseq     = ^uint64(0)
	seqinc    = ^uint64(0) - 1
)

// order1007 merges a set of per-P event batches into a single, consistent stream.
// The high level idea is as follows. Events within an individual batch are in
// correct order, because they are emitted by a single P. So we need to produce
// a correct interleaving of the batches. To do this we take first unmerged event
// from each batch (frontier). Then choose subset that is "ready" to be merged,
// that is, events for which all dependencies are already merged. Then we choose
// event with the lowest timestamp from the subset, merge it and repeat.
// This approach ensures that we form a consistent stream even if timestamps are
// incorrect (condition observed on some machines).
func order1007( map[int][]*Event) ( []*Event,  error) {
	 := 0
	var  []*eventBatch
	for ,  := range  {
		 += len()
		 = append(, &eventBatch{, false})
	}
	 := make(map[uint64]gState)
	var  []orderEvent
	for ;  != 0; -- {
		for ,  := range  {
			if .selected || len(.events) == 0 {
				continue
			}
			 := .events[0]
			, ,  := stateTransition()
			if !transitionReady(, [], ) {
				continue
			}
			 = append(, orderEvent{, , , , })
			.events = .events[1:]
			.selected = true
			// Get rid of "Local" events, they are intended merely for ordering.
			switch .Type {
			case EvGoStartLocal:
				.Type = EvGoStart
			case EvGoUnblockLocal:
				.Type = EvGoUnblock
			case EvGoSysExitLocal:
				.Type = EvGoSysExit
			}
		}
		if len() == 0 {
			return nil, fmt.Errorf("no consistent ordering of events possible")
		}
		sort.Sort(orderEventList())
		 := [0]
		[0] = [len()-1]
		 = [:len()-1]
		 = append(, .ev)
		transition(, .g, .init, .next)
		if ![.batch].selected {
			panic("frontier batch is not selected")
		}
		[.batch].selected = false
	}

	// At this point we have a consistent stream of events.
	// Make sure time stamps respect the ordering.
	// The tests will skip (not fail) the test case if they see this error.
	if !sort.IsSorted(eventList()) {
		return nil, ErrTimeOrder
	}

	// The last part is giving correct timestamps to EvGoSysExit events.
	// The problem with EvGoSysExit is that actual syscall exit timestamp (ev.Args[2])
	// is potentially acquired long before event emission. So far we've used
	// timestamp of event emission (ev.Ts).
	// We could not set ev.Ts = ev.Args[2] earlier, because it would produce
	// seemingly broken timestamps (misplaced event).
	// We also can't simply update the timestamp and resort events, because
	// if timestamps are broken we will misplace the event and later report
	// logically broken trace (instead of reporting broken timestamps).
	 := make(map[uint64]int64)
	for ,  := range  {
		switch .Type {
		case EvGoSysBlock, EvGoInSyscall:
			[.G] = .Ts
		case EvGoSysExit:
			 := int64(.Args[2])
			if  == 0 {
				continue
			}
			 := [.G]
			if  == 0 {
				return nil, fmt.Errorf("stray syscall exit")
			}
			if  <  {
				return nil, ErrTimeOrder
			}
			.Ts = 
		}
	}
	sort.Stable(eventList())

	return
}

// stateTransition returns goroutine state (sequence and status) when the event
// becomes ready for merging (init) and the goroutine state after the event (next).
func stateTransition( *Event) ( uint64, ,  gState) {
	switch .Type {
	case EvGoCreate:
		 = .Args[0]
		 = gState{0, gDead}
		 = gState{1, gRunnable}
	case EvGoWaiting, EvGoInSyscall:
		 = .G
		 = gState{1, gRunnable}
		 = gState{2, gWaiting}
	case EvGoStart, EvGoStartLabel:
		 = .G
		 = gState{.Args[1], gRunnable}
		 = gState{.Args[1] + 1, gRunning}
	case EvGoStartLocal:
		// noseq means that this event is ready for merging as soon as
		// frontier reaches it (EvGoStartLocal is emitted on the same P
		// as the corresponding EvGoCreate/EvGoUnblock, and thus the latter
		// is already merged).
		// seqinc is a stub for cases when event increments g sequence,
		// but since we don't know current seq we also don't know next seq.
		 = .G
		 = gState{noseq, gRunnable}
		 = gState{seqinc, gRunning}
	case EvGoBlock, EvGoBlockSend, EvGoBlockRecv, EvGoBlockSelect,
		EvGoBlockSync, EvGoBlockCond, EvGoBlockNet, EvGoSleep,
		EvGoSysBlock, EvGoBlockGC:
		 = .G
		 = gState{noseq, gRunning}
		 = gState{noseq, gWaiting}
	case EvGoSched, EvGoPreempt:
		 = .G
		 = gState{noseq, gRunning}
		 = gState{noseq, gRunnable}
	case EvGoUnblock, EvGoSysExit:
		 = .Args[0]
		 = gState{.Args[1], gWaiting}
		 = gState{.Args[1] + 1, gRunnable}
	case EvGoUnblockLocal, EvGoSysExitLocal:
		 = .Args[0]
		 = gState{noseq, gWaiting}
		 = gState{seqinc, gRunnable}
	case EvGCStart:
		 = garbage
		 = gState{.Args[0], gDead}
		 = gState{.Args[0] + 1, gDead}
	default:
		// no ordering requirements
		 = unordered
	}
	return
}

func transitionReady( uint64, ,  gState) bool {
	return  == unordered || (.seq == noseq || .seq == .seq) && .status == .status
}

func transition( map[uint64]gState,  uint64, ,  gState) {
	if  == unordered {
		return
	}
	 := []
	if !transitionReady(, , ) {
		panic("event sequences are broken")
	}
	switch .seq {
	case noseq:
		.seq = .seq
	case seqinc:
		.seq = .seq + 1
	}
	[] = 
}

// order1005 merges a set of per-P event batches into a single, consistent stream.
func order1005( map[int][]*Event) ( []*Event,  error) {
	for ,  := range  {
		 = append(, ...)
	}
	for ,  := range  {
		if .Type == EvGoSysExit {
			// EvGoSysExit emission is delayed until the thread has a P.
			// Give it the real sequence number and time stamp.
			.seq = int64(.Args[1])
			if .Args[2] != 0 {
				.Ts = int64(.Args[2])
			}
		}
	}
	sort.Sort(eventSeqList())
	if !sort.IsSorted(eventList()) {
		return nil, ErrTimeOrder
	}
	return
}

type orderEventList []orderEvent

func ( orderEventList) () int {
	return len()
}

func ( orderEventList) (,  int) bool {
	return [].ev.Ts < [].ev.Ts
}

func ( orderEventList) (,  int) {
	[], [] = [], []
}

type eventList []*Event

func ( eventList) () int {
	return len()
}

func ( eventList) (,  int) bool {
	return [].Ts < [].Ts
}

func ( eventList) (,  int) {
	[], [] = [], []
}

type eventSeqList []*Event

func ( eventSeqList) () int {
	return len()
}

func ( eventSeqList) (,  int) bool {
	return [].seq < [].seq
}

func ( eventSeqList) (,  int) {
	[], [] = [], []
}