// SPDX-License-Identifier: Unlicense OR MIT

// Full port of gioui.org/io/input (router.go, pointer.go, key.go, clipboard.go).
// All sub-packages merged into package gio.

package gio

import (
	"image"
	"io"
	"time"
)

// ---------------------------------------------------------------------------
// Router
// ---------------------------------------------------------------------------

// Router tracks event.Tag identifiers and routes events to widget handlers.
// Source is its interface exposed to widgets.
type Router struct {
	savedTrans []Affine2D
	transStack []Affine2D
	handlers   map[Tag]*routerHandler
	pointer    struct {
		queue     pointerQueue
		collector pointerCollector
	}
	key struct {
		queue         keyQueue
		filter        keyFilterList
		nextFilter    keyFilterList
		scratchFilter keyFilterList
	}
	cqueue  clipboardQueue
	changes []stateChange
	reader  Reader
	// InvalidateCmd summary.
	wakeup     bool
	wakeupTime time.Time
	commands   []InputCommand
	transfers  []io.ReadCloser
	deferring  bool
	// scratchFilters for garbage-free construction.
	scratchFilters []taggedFilter
}

// Source implements the interface between a Router and widget handlers.
// The zero value is disabled.
type Source struct {
	r        *Router
	disabled bool
}

// routerHandler contains per-handler state tracked by a Router.
type routerHandler struct {
	active          bool
	pointer         pointerHandler
	key             keyHandler
	filter          routerFilter
	nextFilter      routerFilter
	processedFilter routerFilter
}

// routerFilter is the union of a set of Filters.
type routerFilter struct {
	pointer   pointerFilter
	focusable bool
}

// taggedFilter is a filter for a particular tag.
type taggedFilter struct {
	tag    Tag
	filter routerFilter
}

// stateChange represents new state and outgoing events resulting from an incoming event.
type stateChange struct {
	event  Event
	state  inputState
	events []taggedEvent
}

// inputState is an immutable snapshot of routing state.
type inputState struct {
	clipboardState
	keyState
	pointerState
}

// taggedEvent represents an event and its target handler.
type taggedEvent struct {
	event Event
	tag   Tag
}

// SystemEvent marks events with platform-specific side-effects.
// SystemEvents are never matched by catch-all filters.
type SystemEvent struct {
	Event Event
}

func (SystemEvent) ImplementsEvent() {}

// Source returns a Source backed by this Router.
func (q *Router) Source() Source { return Source{r: q} }

// Disabled returns a copy of this source that delivers no events.
func (s Source) Disabled() Source { s2 := s; s2.disabled = true; return s2 }

// Enabled reports whether the source is enabled.
func (s Source) Enabled() bool { return s.r != nil && !s.disabled }

// Focused reports whether tag is focused per the last delivered KeyFocusEvent.
func (s Source) Focused(tag Tag) bool {
	if !s.Enabled() {
		return false
	}
	return s.r.state().keyState.focus == tag
}

// Execute queues a command for execution.
func (s Source) Execute(c InputCommand) {
	if !s.Enabled() {
		return
	}
	s.r.execute(c)
}

// Event returns the next event matching at least one of filters.
func (s Source) Event(filters ...Filter) (Event, bool) {
	if !s.Enabled() {
		return nil, false
	}
	return s.r.Event(filters...)
}

func (q *Router) Event(filters ...Filter) (Event, bool) {
	q.scratchFilters = q.scratchFilters[:0]
	q.key.scratchFilter = q.key.scratchFilter[:0]
	for _, f := range filters {
		var t Tag
		switch f := f.(type) {
		case KeyFilter:
			q.key.scratchFilter = append(q.key.scratchFilter, f)
			continue
		case TransferSourceFilter:
			t = f.Target
		case TransferTargetFilter:
			t = f.Target
		case KeyFocusFilter:
			t = f.Target
		case PointerFilter:
			t = f.Target
		}
		if t == nil {
			continue
		}
		var flt *routerFilter
		for i := range q.scratchFilters {
			s := &q.scratchFilters[i]
			if s.tag == t {
				flt = &s.filter
				break
			}
		}
		if flt == nil {
			n := len(q.scratchFilters)
			if n < cap(q.scratchFilters) {
				q.scratchFilters = q.scratchFilters[:n+1]
				tf := &q.scratchFilters[n]
				tf.tag = t
				flt = &tf.filter
				flt.Reset()
			} else {
				q.scratchFilters = append(q.scratchFilters, taggedFilter{tag: t})
				flt = &q.scratchFilters[n].filter
			}
		}
		flt.Add(f)
	}
	for _, tf := range q.scratchFilters {
		h := q.stateFor(tf.tag)
		h.filter.Merge(tf.filter)
		h.nextFilter.Merge(tf.filter)
	}
	q.key.filter = append(q.key.filter, q.key.scratchFilter...)
	q.key.nextFilter = append(q.key.nextFilter, q.key.scratchFilter...)
	// Deliver reset events, if any.
	for _, f := range filters {
		switch f := f.(type) {
		case KeyFocusFilter:
			if f.Target == nil {
				break
			}
			h := q.stateFor(f.Target)
			if reset, ok := h.key.ResetEvent(); ok {
				return reset, true
			}
		case PointerFilter:
			if f.Target == nil {
				break
			}
			h := q.stateFor(f.Target)
			if reset, ok := h.pointer.ResetEvent(); ok && h.filter.pointer.Matches(reset) {
				return reset, true
			}
		}
	}
	for i := range q.changes {
		if q.deferring && i > 0 {
			break
		}
		change := &q.changes[i]
		for j, evt := range change.events {
			match := false
			switch e := evt.event.(type) {
			case KeyEvent:
				match = q.key.scratchFilter.Matches(change.state.keyState.focus, e, false)
			default:
				for _, tf := range q.scratchFilters {
					if evt.tag == tf.tag && tf.filter.Matches(evt.event) {
						match = true
						break
					}
				}
			}
			if match {
				change.events = deleteTaggedEvent(change.events, j, j+1)
				q.collapseState(i)
				return evt.event, true
			}
		}
	}
	for _, tf := range q.scratchFilters {
		h := q.stateFor(tf.tag)
		h.processedFilter.Merge(tf.filter)
	}
	return nil, false
}

func (q *Router) collapseState(idx int) {
	if idx == 0 {
		return
	}
	first := &q.changes[0]
	first.state = q.changes[idx].state
	for _, ch := range q.changes[1 : idx+1] {
		first.events = append(first.events, ch.events...)
	}
	q.changes = append(q.changes[:1], q.changes[idx+1:]...)
}

// Frame completes the current frame, collects handlers from ops, and starts a new frame.
func (q *Router) Frame(frame *OpList) {
	var remaining []Event
	if n := len(q.changes); n > 0 {
		if q.deferring {
			for _, ch := range q.changes[1:] {
				remaining = append(remaining, ch.event)
			}
			q.changes = append(q.changes[:0], stateChange{state: q.changes[0].state})
		} else {
			state := q.changes[n-1].state
			q.changes = append(q.changes[:0], stateChange{state: state})
		}
	}
	for _, rc := range q.transfers {
		if rc != nil {
			rc.Close()
		}
	}
	q.transfers = nil
	q.deferring = false
	for _, h := range q.handlers {
		h.filter, h.nextFilter = h.nextFilter, h.filter
		h.nextFilter.Reset()
		h.processedFilter.Reset()
		h.pointer.Reset()
		h.key.Reset()
	}
	q.key.filter, q.key.nextFilter = q.key.nextFilter, q.key.filter
	q.key.nextFilter = q.key.nextFilter[:0]
	var ops *Ops
	if frame != nil {
		ops = &frame.Internal
	}
	q.reader.ResetReader(ops)
	q.collect()
	for k, h := range q.handlers {
		if !h.active {
			delete(q.handlers, k)
		} else {
			h.active = false
		}
	}
	q.executeCommands()
	q.Queue(remaining...)
	st := q.lastState()
	pst, evts := q.pointer.queue.Frame(q.handlers, st.pointerState)
	st.pointerState = pst
	st.keyState = q.key.queue.Frame(q.handlers, q.lastState().keyState)
	q.changeState(nil, st, evts)
	q.collapseState(len(q.changes) - 1)
}

// Queue events to be routed.
func (q *Router) Queue(events ...Event) {
	for _, e := range events {
		se, system := e.(SystemEvent)
		if system {
			e = se.Event
		}
		q.processEvent(e, system)
	}
}

// QueuePointer translates and queues AppPointerEvents.
func (q *Router) QueuePointer(events []AppPointerEvent) {
	for _, e := range events {
		q.Queue(appPointerToPointerEvent(e))
	}
}

// QueueKey translates and queues AppKeyEvents.
func (q *Router) QueueKey(events []AppKeyEvent) {
	for _, e := range events {
		if ke, ok := appKeyToKeyEvent(e); ok {
			q.Queue(ke)
		}
	}
}

func (f *routerFilter) Add(flt Filter) {
	switch flt := flt.(type) {
	case KeyFocusFilter:
		f.focusable = true
	case PointerFilter:
		f.pointer.Add(flt)
	case TransferSourceFilter, TransferTargetFilter:
		f.pointer.AddTransfer(flt)
	}
}

func (f *routerFilter) Merge(f2 routerFilter) {
	f.focusable = f.focusable || f2.focusable
	f.pointer.Merge(f2.pointer)
}

func (f *routerFilter) Matches(e Event) bool {
	switch e.(type) {
	case KeyFocusEvent, SnippetEvent, KeyEditEvent, SelectionEvent:
		return f.focusable
	default:
		return f.pointer.Matches(e)
	}
}

func (f *routerFilter) Reset() {
	*f = routerFilter{
		pointer: pointerFilter{
			sourceMimes: f.pointer.sourceMimes[:0],
			targetMimes: f.pointer.targetMimes[:0],
		},
	}
}

func (q *Router) processEvent(e Event, system bool) {
	state := q.lastState()
	switch e := e.(type) {
	case PointerEvent:
		pstate, evts := q.pointer.queue.Push(q.handlers, state.pointerState, e)
		state.pointerState = pstate
		q.changeState(e, state, evts)
	case KeyEvent:
		var evts []taggedEvent
		if q.key.filter.Matches(state.keyState.focus, e, system) {
			evts = append(evts, taggedEvent{event: e})
		}
		q.changeState(e, state, evts)
	case SnippetEvent:
		if r := state.content.Snippet.KeyRange; rangeOverlaps(r, KeyRange(e)) {
			if e.Start > r.Start {
				e.Start = r.Start
			}
			if e.End < r.End {
				e.End = r.End
			}
		}
		var evts []taggedEvent
		if f := state.focus; f != nil {
			evts = append(evts, taggedEvent{tag: f, event: e})
		}
		q.changeState(e, state, evts)
	case KeyEditEvent, KeyFocusEvent, SelectionEvent:
		var evts []taggedEvent
		if f := state.focus; f != nil {
			evts = append(evts, taggedEvent{tag: f, event: e})
		}
		q.changeState(e, state, evts)
	case TransferDataEvent:
		cstate, evts := q.cqueue.Push(state.clipboardState, e)
		state.clipboardState = cstate
		q.changeState(e, state, evts)
	default:
		// Unknown event type - ignore rather than panic for robustness.
	}
}

func (q *Router) execute(c InputCommand) {
	if !q.deferring {
		ch := q.executeCommand(c)
		immediate := true
		for _, e := range ch.events {
			h, ok := q.handlers[e.tag]
			immediate = immediate && (!ok || !h.processedFilter.Matches(e.event))
		}
		if immediate {
			var evts []Event
			for _, ch := range q.changes {
				if ch.event != nil {
					evts = append(evts, ch.event)
				}
			}
			if len(q.changes) > 1 {
				q.changes = q.changes[:1]
			}
			q.changeState(nil, ch.state, ch.events)
			q.Queue(evts...)
			return
		}
	}
	q.deferring = true
	q.commands = append(q.commands, c)
}

func (q *Router) state() inputState {
	if len(q.changes) > 0 {
		return q.changes[0].state
	}
	return inputState{}
}

func (q *Router) lastState() inputState {
	if n := len(q.changes); n > 0 {
		return q.changes[n-1].state
	}
	return inputState{}
}

func (q *Router) executeCommands() {
	for _, c := range q.commands {
		ch := q.executeCommand(c)
		q.changeState(nil, ch.state, ch.events)
	}
	q.commands = nil
}

func (q *Router) executeCommand(c InputCommand) stateChange {
	state := q.state()
	var evts []taggedEvent
	switch req := c.(type) {
	case SelectionCmd:
		state.keyState = q.key.queue.setSelection(state.keyState, req)
	case FocusCmd:
		state.keyState, evts = q.key.queue.Focus(q.handlers, state.keyState, req.Tag)
	case SoftKeyboardCmd:
		state.keyState = state.keyState.softKeyboard(req.Show)
	case SnippetCmd:
		state.keyState = q.key.queue.setSnippet(state.keyState, req)
	case TransferOfferCmd:
		state.pointerState, evts = q.pointer.queue.offerData(q.handlers, state.pointerState, req)
	case ClipboardWriteCmd:
		q.cqueue.ProcessWriteClipboard(req)
	case ClipboardReadCmd:
		state.clipboardState = q.cqueue.ProcessReadClipboard(state.clipboardState, req.Tag)
	case GrabCmd:
		state.pointerState, evts = q.pointer.queue.grab(state.pointerState, req)
	case InvalidateCmd:
		if !q.wakeup || req.At.Before(q.wakeupTime) {
			q.wakeup = true
			q.wakeupTime = req.At
		}
	}
	return stateChange{state: state, events: evts}
}

func (q *Router) changeState(e Event, state inputState, evts []taggedEvent) {
	for i := range evts {
		ev := &evts[i]
		if de, ok := ev.event.(TransferDataEvent); ok {
			transferIdx := len(q.transfers)
			data := de.Open()
			q.transfers = append(q.transfers, data)
			de.Open = func() io.ReadCloser {
				q.transfers[transferIdx] = nil
				return data
			}
			ev.event = de
		}
	}
	if len(q.changes) == 0 {
		q.changes = append(q.changes, stateChange{})
	}
	if e != nil && len(evts) > 0 {
		q.changes = append(q.changes, stateChange{event: e, state: state, events: evts})
	} else {
		prev := &q.changes[len(q.changes)-1]
		prev.state = state
		prev.events = append(prev.events, evts...)
	}
}

func rangeOverlaps(r1, r2 KeyRange) bool {
	r1 = rangeNorm(r1)
	r2 = rangeNorm(r2)
	return r1.Start <= r2.Start && r2.Start < r1.End ||
		r1.Start <= r2.End && r2.End < r1.End
}

func rangeNorm(r KeyRange) KeyRange {
	if r.End < r.Start {
		r.End, r.Start = r.Start, r.End
	}
	return r
}

// MoveFocus attempts to move the focus in direction dir.
func (q *Router) MoveFocus(dir FocusDirection) {
	state := q.lastState()
	kstate, evts := q.key.queue.MoveFocus(q.handlers, state.keyState, dir)
	state.keyState = kstate
	q.changeState(nil, state, evts)
}

// RevealFocus scrolls the current focus into viewport.
func (q *Router) RevealFocus(viewport image.Rectangle) {
	state := q.lastState()
	focus := state.focus
	if focus == nil {
		return
	}
	kh := &q.handlers[focus].key
	bounds := q.key.queue.BoundsFor(kh)
	area := q.key.queue.AreaFor(kh)
	viewport = q.pointer.queue.ClipFor(area, viewport)
	topleft := bounds.Min.Sub(viewport.Min)
	topleft = maxImgPt(topleft, bounds.Max.Sub(viewport.Max))
	topleft = minImgPt(image.Pt(0, 0), topleft)
	bottomright := bounds.Max.Sub(viewport.Max)
	bottomright = minImgPt(bottomright, bounds.Min.Sub(viewport.Min))
	bottomright = maxImgPt(image.Pt(0, 0), bottomright)
	s := topleft
	if s.X == 0 {
		s.X = bottomright.X
	}
	if s.Y == 0 {
		s.Y = bottomright.Y
	}
	q.ScrollFocus(s)
}

// ScrollFocus scrolls the focused widget by dist.
func (q *Router) ScrollFocus(dist image.Point) {
	state := q.lastState()
	focus := state.focus
	if focus == nil {
		return
	}
	kh := &q.handlers[focus].key
	area := q.key.queue.AreaFor(kh)
	q.changeState(nil, q.lastState(), q.pointer.queue.Deliver(q.handlers, area, PointerEvent{
		Kind:   PointerScroll,
		Source: Touch,
		Scroll: FPt(dist),
	}))
}

// ActionAt returns the action at pos, if any.
func (q *Router) ActionAt(p Point) (SystemAction, bool) {
	return q.pointer.queue.ActionAt(p)
}

// ClickFocus synthesizes a click on the focused widget.
func (q *Router) ClickFocus() {
	focus := q.lastState().focus
	if focus == nil {
		return
	}
	kh := &q.handlers[focus].key
	bounds := q.key.queue.BoundsFor(kh)
	center := bounds.Max.Add(bounds.Min).Div(2)
	e := PointerEvent{
		Position: Pt(float32(center.X), float32(center.Y)),
		Source:   Touch,
	}
	area := q.key.queue.AreaFor(kh)
	e.Kind = PointerPress
	state := q.lastState()
	q.changeState(nil, state, q.pointer.queue.Deliver(q.handlers, area, e))
	e.Kind = PointerRelease
	q.changeState(nil, state, q.pointer.queue.Deliver(q.handlers, area, e))
}

// TextInputState returns the current text input state.
func (q *Router) TextInputState() TextInputState {
	state := q.state()
	kstate, s := state.InputState()
	state.keyState = kstate
	q.changeState(nil, state, nil)
	return s
}

// TextInputHint returns the current key input hint.
func (q *Router) TextInputHint() (InputHint, bool) {
	return q.key.queue.InputHint(q.handlers, q.state().keyState)
}

// WriteClipboard returns the most recent content to copy to clipboard.
func (q *Router) WriteClipboard() (mime string, content []byte, ok bool) {
	return q.cqueue.WriteClipboard()
}

// ClipboardRequested reports if any handler is waiting for clipboard contents.
func (q *Router) ClipboardRequested() bool {
	return q.cqueue.ClipboardRequested(q.lastState().clipboardState)
}

// Cursor returns the last cursor set.
func (q *Router) Cursor() Cursor {
	return q.state().cursor
}

// WakeupTime returns the most recent requested wakeup time.
func (q *Router) WakeupTime() (time.Time, bool) {
	t, w := q.wakeupTime, q.wakeup
	q.wakeup = false
	if len(q.changes) > 1 || len(q.changes) == 1 && len(q.changes[0].events) > 0 {
		t, w = time.Time{}, true
	}
	return t, w
}

func (q *Router) stateFor(tag Tag) *routerHandler {
	if tag == nil {
		panic("internal error: nil tag")
	}
	s, ok := q.handlers[tag]
	if !ok {
		s = &routerHandler{}
		if q.handlers == nil {
			q.handlers = map[Tag]*routerHandler{}
		}
		q.handlers[tag] = s
	}
	s.active = true
	return s
}

func (q *Router) collect() {
	q.transStack = q.transStack[:0]
	pc := &q.pointer.collector
	pc.q = &q.pointer.queue
	pc.Reset()
	kq := &q.key.queue
	q.key.queue.Reset()
	t := AffineId()
	for encOp, ok := q.reader.Decode(); ok; encOp, ok = q.reader.Decode() {
		switch OpType(encOp.Data[0]) {
		case TypeSave:
			id := DecodeSave(encOp.Data)
			for extra := id - len(q.savedTrans) + 1; extra > 0; extra-- {
				q.savedTrans = append(q.savedTrans, AffineId())
			}
			q.savedTrans[id] = t
		case TypeLoad:
			id := DecodeLoad(encOp.Data)
			t = q.savedTrans[id]
			pc.resetState()
			pc.setTrans(t)
		case TypeClip:
			var op DecodedClipOp
			op.Decode(encOp.Data)
			pc.clip(op)
		case TypePopClip:
			pc.popArea()
		case TypeTransform:
			t2, push := DecodeTransform(encOp.Data)
			if push {
				q.transStack = append(q.transStack, t)
			}
			t = t.Mul(t2)
			pc.setTrans(t)
		case TypePopTransform:
			n := len(q.transStack)
			t = q.transStack[n-1]
			q.transStack = q.transStack[:n-1]
			pc.setTrans(t)
		case TypeInput:
			tag := encOp.Refs[0].(Tag)
			s := q.stateFor(tag)
			pc.inputOp(tag, &s.pointer)
			a := pc.currentArea()
			b := pc.currentAreaBounds()
			if s.filter.focusable {
				kq.inputOp(tag, &s.key, t, a, b)
			}
		case TypePass:
			pc.pass()
		case TypePopPass:
			pc.popPass()
		case TypeCursor:
			name := Cursor(encOp.Data[1])
			pc.cursor(name)
		case TypeActionInput:
			act := SystemAction(encOp.Data[1])
			pc.actionInputOp(act)
		case TypeKeyInputHint:
			op := KeyInputHintOp{
				Tag:  encOp.Refs[0].(Tag),
				Hint: InputHint(encOp.Data[1]),
			}
			s := q.stateFor(op.Tag)
			s.key.inputHint(op.Hint)
		case TypeSemanticLabel:
			lbl := *encOp.Refs[0].(*string)
			pc.semanticLabel(lbl)
		case TypeSemanticDesc:
			desc := *encOp.Refs[0].(*string)
			pc.semanticDesc(desc)
		case TypeSemanticClass:
			class := SemanticClassOp(encOp.Data[1])
			pc.semanticClass(class)
		case TypeSemanticSelected:
			pc.semanticSelected(encOp.Data[1] != 0)
		case TypeSemanticEnabled:
			pc.semanticEnabled(encOp.Data[1] != 0)
		}
	}
}

// SemanticID uniquely identifies a SemanticDesc.
type SemanticID uint

// SemanticGestures is a bit-set of supported gestures.
type SemanticGestures int

const (
	ClickGesture  SemanticGestures = 1 << iota
	ScrollGesture
)

// SemanticNode represents a node in the semantic tree.
type SemanticNode struct {
	ID       SemanticID
	ParentID SemanticID
	Children []SemanticNode
	Desc     SemanticDesc
	areaIdx  int
}

// SemanticDesc provides a semantic description of a UI component.
type SemanticDesc struct {
	Class       SemanticClassOp
	Description string
	Label       string
	Selected    bool
	Disabled    bool
	Gestures    SemanticGestures
	Bounds      image.Rectangle
}

// SemanticAt returns the first semantic description under pos, if any.
func (q *Router) SemanticAt(pos Point) (SemanticID, bool) {
	return q.pointer.queue.SemanticAt(pos)
}

// AppendSemantics appends the semantic tree to nodes and returns the result.
func (q *Router) AppendSemantics(nodes []SemanticNode) []SemanticNode {
	q.pointer.collector.q = &q.pointer.queue
	q.pointer.collector.ensureRoot()
	return q.pointer.queue.AppendSemantics(nodes)
}

// EditorState returns the editor state for the focused handler.
func (q *Router) EditorState() EditorState {
	return q.key.queue.editorState(q.handlers, q.state().keyState)
}

// EditorState represents the state of an editor.
type EditorState struct {
	Selection struct {
		Transform Affine2D
		KeyRange
		Caret
	}
	Snippet Snippet
}

// TextInputState represents the text input open/close state.
type TextInputState uint8

const (
	TextInputKeep  TextInputState = iota
	TextInputClose
	TextInputOpen
)

func maxImgPt(p1, p2 image.Point) image.Point {
	if p2.X > p1.X {
		p1.X = p2.X
	}
	if p2.Y > p1.Y {
		p1.Y = p2.Y
	}
	return p1
}

func minImgPt(p1, p2 image.Point) image.Point {
	if p2.X < p1.X {
		p1.X = p2.X
	}
	if p2.Y < p1.Y {
		p1.Y = p2.Y
	}
	return p1
}

// ---------------------------------------------------------------------------
// Pointer queue (ported from pointer.go)
// ---------------------------------------------------------------------------

type pointerQueue struct {
	hitTree []hitNode
	areas   []areaNode

	semantic struct {
		idsAssigned bool
		lastID      SemanticID
		contentIDs  map[semanticContent][]semanticID
	}
}

type hitNode struct {
	next int
	area int
	tag  Tag
	pass bool
}

type pointerState struct {
	cursor   Cursor
	pointers []pointerInfo
}

type pointerInfo struct {
	id       PointerID
	pressed  bool
	handlers []Tag
	last     PointerEvent
	entered  []Tag
	dataSource Tag
	dataTarget Tag
}

type pointerHandler struct {
	areaPlusOne int
	setup       bool
}

type pointerFilter struct {
	kinds       PointerKind
	scrollX     ScrollRange
	scrollY     ScrollRange
	sourceMimes []string
	targetMimes []string
}

type areaOp struct {
	kind areaKind
	rect image.Rectangle
}

type areaNode struct {
	trans      Affine2D
	area       areaOp
	cursor     Cursor
	parent     int
	firstChild int
	lastChild  int
	sibling    int
	semantic struct {
		valid   bool
		id      SemanticID
		content semanticContent
	}
	action SystemAction
}

type areaKind uint8

const (
	areaRect    areaKind = iota
	areaEllipse
)

type collectState struct {
	t           Affine2D
	nodePlusOne int
	pass        int
}

type pointerCollector struct {
	q         *pointerQueue
	state     collectState
	nodeStack []int
}

type semanticContent struct {
	tag      Tag
	label    string
	desc     string
	class    SemanticClassOp
	gestures SemanticGestures
	selected bool
	disabled bool
}

type semanticID struct {
	id   SemanticID
	used bool
}

func (c *pointerCollector) resetState() {
	c.state = collectState{t: AffineId()}
	c.nodeStack = c.nodeStack[:0]
	if len(c.q.hitTree) > 0 {
		c.state.nodePlusOne = 0 + 1
	}
}

func (c *pointerCollector) setTrans(t Affine2D) { c.state.t = t }

func (c *pointerCollector) clip(op DecodedClipOp) {
	kind := areaRect
	if op.Shape == ShapeEllipse {
		kind = areaEllipse
	}
	c.pushArea(kind, op.Bounds)
}

func (c *pointerCollector) pushArea(kind areaKind, bounds image.Rectangle) {
	parentID := c.currentArea()
	areaID := len(c.q.areas)
	if parentID != -1 {
		parent := &c.q.areas[parentID]
		if parent.firstChild == -1 {
			parent.firstChild = areaID
		}
		if siblingID := parent.lastChild; siblingID != -1 {
			c.q.areas[siblingID].sibling = areaID
		}
		parent.lastChild = areaID
	}
	an := areaNode{
		trans:      c.state.t,
		area:       areaOp{kind: kind, rect: bounds},
		parent:     parentID,
		sibling:    -1,
		firstChild: -1,
		lastChild:  -1,
	}
	c.q.areas = append(c.q.areas, an)
	c.nodeStack = append(c.nodeStack, c.state.nodePlusOne-1)
	c.addHitNode(hitNode{area: areaID, pass: true})
}

func (c *pointerCollector) popArea() {
	n := len(c.nodeStack)
	c.state.nodePlusOne = c.nodeStack[n-1] + 1
	c.nodeStack = c.nodeStack[:n-1]
}

func (c *pointerCollector) pass()    { c.state.pass++ }
func (c *pointerCollector) popPass() { c.state.pass-- }

func (c *pointerCollector) currentArea() int {
	if i := c.state.nodePlusOne - 1; i != -1 {
		return c.q.hitTree[i].area
	}
	return -1
}

func (c *pointerCollector) currentAreaBounds() image.Rectangle {
	a := c.currentArea()
	if a == -1 {
		panic("no root area")
	}
	return c.q.areas[a].bounds()
}

func (c *pointerCollector) addHitNode(n hitNode) {
	n.next = c.state.nodePlusOne - 1
	c.q.hitTree = append(c.q.hitTree, n)
	c.state.nodePlusOne = len(c.q.hitTree) - 1 + 1
}

func (c *pointerCollector) newHandler(tag Tag, state *pointerHandler) {
	areaID := c.currentArea()
	c.addHitNode(hitNode{area: areaID, tag: tag, pass: c.state.pass > 0})
	state.areaPlusOne = areaID + 1
}

func (s *pointerHandler) Reset()    { s.areaPlusOne = 0 }
func (s *pointerHandler) ResetEvent() (Event, bool) {
	if s.setup {
		return nil, false
	}
	s.setup = true
	return PointerEvent{Kind: PointerCancel}, true
}

func (c *pointerCollector) actionInputOp(act SystemAction) {
	areaID := c.currentArea()
	c.q.areas[areaID].action = act
}

func (c *pointerCollector) inputOp(tag Tag, state *pointerHandler) {
	areaID := c.currentArea()
	c.q.areas[areaID].semantic.content.tag = tag
	c.newHandler(tag, state)
}

func (c *pointerCollector) cursor(cur Cursor) {
	areaID := c.currentArea()
	c.q.areas[areaID].cursor = cur
}

func (c *pointerCollector) semanticLabel(lbl string) {
	areaID := c.currentArea()
	a := &c.q.areas[areaID]
	a.semantic.valid = true
	a.semantic.content.label = lbl
}

func (c *pointerCollector) semanticDesc(desc string) {
	areaID := c.currentArea()
	a := &c.q.areas[areaID]
	a.semantic.valid = true
	a.semantic.content.desc = desc
}

func (c *pointerCollector) semanticClass(class SemanticClassOp) {
	areaID := c.currentArea()
	a := &c.q.areas[areaID]
	a.semantic.valid = true
	a.semantic.content.class = class
}

func (c *pointerCollector) semanticSelected(selected bool) {
	areaID := c.currentArea()
	a := &c.q.areas[areaID]
	a.semantic.valid = true
	a.semantic.content.selected = selected
}

func (c *pointerCollector) semanticEnabled(enabled bool) {
	areaID := c.currentArea()
	a := &c.q.areas[areaID]
	a.semantic.valid = true
	a.semantic.content.disabled = !enabled
}

func (c *pointerCollector) Reset() {
	c.q.reset()
	c.resetState()
	c.ensureRoot()
}

func (c *pointerCollector) ensureRoot() {
	if len(c.q.areas) > 0 {
		return
	}
	c.pushArea(areaRect, image.Rect(-1e6, -1e6, 1e6, 1e6))
	c.q.areas[0].semantic.valid = true
}

func (q *pointerQueue) reset() {
	q.hitTree = q.hitTree[:0]
	q.areas = q.areas[:0]
	q.semantic.idsAssigned = false
	for k, ids := range q.semantic.contentIDs {
		for i := len(ids) - 1; i >= 0; i-- {
			if !ids[i].used {
				ids = deleteSemanticID(ids, i, i+1)
			} else {
				ids[i].used = false
			}
		}
		if len(ids) > 0 {
			q.semantic.contentIDs[k] = ids
		} else {
			delete(q.semantic.contentIDs, k)
		}
	}
}

func (q *pointerQueue) assignSemIDs() {
	if q.semantic.idsAssigned {
		return
	}
	q.semantic.idsAssigned = true
	for i, a := range q.areas {
		if a.semantic.valid {
			q.areas[i].semantic.id = q.semanticIDFor(a.semantic.content)
		}
	}
}

func (q *pointerQueue) AppendSemantics(nodes []SemanticNode) []SemanticNode {
	q.assignSemIDs()
	nodes = q.appendSemanticChildren(nodes, 0)
	nodes = q.appendSemanticArea(nodes, 0, 0)
	return nodes
}

func (q *pointerQueue) appendSemanticArea(nodes []SemanticNode, parentID SemanticID, nodeIdx int) []SemanticNode {
	areaIdx := nodes[nodeIdx].areaIdx
	a := q.areas[areaIdx]
	childStart := len(nodes)
	nodes = q.appendSemanticChildren(nodes, a.firstChild)
	childEnd := len(nodes)
	for i := childStart; i < childEnd; i++ {
		nodes = q.appendSemanticArea(nodes, a.semantic.id, i)
	}
	n := &nodes[nodeIdx]
	n.ParentID = parentID
	n.Children = nodes[childStart:childEnd]
	return nodes
}

func (q *pointerQueue) appendSemanticChildren(nodes []SemanticNode, areaIdx int) []SemanticNode {
	if areaIdx == -1 {
		return nodes
	}
	a := q.areas[areaIdx]
	if semID := a.semantic.id; semID != 0 {
		cnt := a.semantic.content
		nodes = append(nodes, SemanticNode{
			ID: semID,
			Desc: SemanticDesc{
				Bounds:      a.bounds(),
				Label:       cnt.label,
				Description: cnt.desc,
				Class:       cnt.class,
				Gestures:    cnt.gestures,
				Selected:    cnt.selected,
				Disabled:    cnt.disabled,
			},
			areaIdx: areaIdx,
		})
	} else {
		nodes = q.appendSemanticChildren(nodes, a.firstChild)
	}
	return q.appendSemanticChildren(nodes, a.sibling)
}

func (q *pointerQueue) semanticIDFor(content semanticContent) SemanticID {
	ids := q.semantic.contentIDs[content]
	for i, id := range ids {
		if !id.used {
			ids[i].used = true
			return id.id
		}
	}
	q.semantic.lastID++
	id := semanticID{id: q.semantic.lastID, used: true}
	if q.semantic.contentIDs == nil {
		q.semantic.contentIDs = map[semanticContent][]semanticID{}
	}
	q.semantic.contentIDs[content] = append(q.semantic.contentIDs[content], id)
	return id.id
}

func (q *pointerQueue) ActionAt(pos Point) (action SystemAction, hasAction bool) {
	q.hitTest(pos, func(n *hitNode) bool {
		area := q.areas[n.area]
		if area.action != 0 {
			action = area.action
			hasAction = true
			return false
		}
		return true
	})
	return action, hasAction
}

func (q *pointerQueue) SemanticAt(pos Point) (semID SemanticID, hasSemID bool) {
	q.assignSemIDs()
	q.hitTest(pos, func(n *hitNode) bool {
		area := q.areas[n.area]
		if area.semantic.id != 0 {
			semID = area.semantic.id
			hasSemID = true
			return false
		}
		return true
	})
	return semID, hasSemID
}

func (q *pointerQueue) hitTest(pos Point, onNode func(*hitNode) bool) Cursor {
	pass := true
	idx := len(q.hitTree) - 1
	cursor := CursorDefault
	for idx >= 0 {
		n := &q.hitTree[idx]
		hit, c := q.hit(n.area, pos)
		if !hit {
			idx--
			continue
		}
		if cursor == CursorDefault {
			cursor = c
		}
		pass = pass && n.pass
		if pass {
			idx--
		} else {
			idx = n.next
		}
		if !onNode(n) {
			break
		}
	}
	return cursor
}

func (q *pointerQueue) invTransform(areaIdx int, p Point) Point {
	if areaIdx == -1 {
		return p
	}
	return q.areas[areaIdx].trans.Invert().Transform(p)
}

func (q *pointerQueue) hit(areaIdx int, p Point) (bool, Cursor) {
	c := CursorDefault
	for areaIdx != -1 {
		a := &q.areas[areaIdx]
		if c == CursorDefault {
			c = a.cursor
		}
		tp := a.trans.Invert().Transform(p)
		if !a.area.Hit(tp) {
			return false, c
		}
		areaIdx = a.parent
	}
	return true, c
}

func (q *pointerQueue) grab(state pointerState, req GrabCmd) (pointerState, []taggedEvent) {
	var evts []taggedEvent
	for _, p := range state.pointers {
		if !p.pressed || p.id != req.ID {
			continue
		}
		found := containsTag(p.handlers, req.Tag)
		if !found {
			continue
		}
		for i := len(p.handlers) - 1; i >= 0; i-- {
			if tag := p.handlers[i]; tag != req.Tag {
				evts = append(evts, taggedEvent{
					tag:   tag,
					event: PointerEvent{Kind: PointerCancel},
				})
				state = dropHandler(state, tag)
			}
		}
		break
	}
	return state, evts
}

func (q *pointerQueue) offerData(handlers map[Tag]*routerHandler, state pointerState, req TransferOfferCmd) (pointerState, []taggedEvent) {
	var evts []taggedEvent
	for i, p := range state.pointers {
		if p.dataSource != req.Tag {
			continue
		}
		if p.dataTarget != nil {
			evts = append(evts, taggedEvent{tag: p.dataTarget, event: TransferDataEvent{
				Type: req.Type,
				Open: func() io.ReadCloser { return req.Data },
			}})
		}
		state.pointers = clonePointers(state.pointers)
		state.pointers[i], evts = q.deliverTransferCancelEvent(handlers, p, evts)
		break
	}
	return state, evts
}

func (q *pointerQueue) Frame(handlers map[Tag]*routerHandler, state pointerState) (pointerState, []taggedEvent) {
	for _, h := range handlers {
		if h.pointer.areaPlusOne != 0 {
			area := &q.areas[h.pointer.areaPlusOne-1]
			if h.filter.pointer.kinds&(PointerPress|PointerRelease) != 0 {
				area.semantic.content.gestures |= ClickGesture
			}
			if h.filter.pointer.kinds&PointerScroll != 0 {
				area.semantic.content.gestures |= ScrollGesture
			}
			area.semantic.valid = area.semantic.content.gestures != 0
		}
	}
	var evts []taggedEvent
	for i, p := range state.pointers {
		changed := false
		p, evts, state.cursor, changed = q.deliverEnterLeaveEvents(handlers, state.cursor, p, evts, p.last)
		if changed {
			state.pointers = clonePointers(state.pointers)
			state.pointers[i] = p
		}
	}
	return state, evts
}

func dropHandler(state pointerState, tag Tag) pointerState {
	pointers := state.pointers
	state.pointers = nil
	for _, p := range pointers {
		handlers := p.handlers
		p.handlers = nil
		for _, h := range handlers {
			if h != tag {
				p.handlers = append(p.handlers, h)
			}
		}
		entered := p.entered
		p.entered = nil
		for _, h := range entered {
			if h != tag {
				p.entered = append(p.entered, h)
			}
		}
		state.pointers = append(state.pointers, p)
	}
	return state
}

func (s pointerState) pointerOf(e PointerEvent) (pointerState, int) {
	for i, p := range s.pointers {
		if p.id == e.PointerID {
			return s, i
		}
	}
	n := len(s.pointers)
	s.pointers = append(s.pointers[:n:n], pointerInfo{id: e.PointerID})
	return s, len(s.pointers) - 1
}

func (q *pointerQueue) Deliver(handlers map[Tag]*routerHandler, areaIdx int, e PointerEvent) []taggedEvent {
	scroll := e.Scroll
	idx := len(q.hitTree) - 1
	for idx != -1 {
		n := &q.hitTree[idx]
		if n.area == areaIdx {
			break
		}
		idx--
	}
	var evts []taggedEvent
	for idx != -1 {
		n := &q.hitTree[idx]
		idx = n.next
		h, ok := handlers[n.tag]
		if !ok || !h.filter.pointer.Matches(e) {
			continue
		}
		e := e
		if e.Kind == PointerScroll {
			if scroll == (Point{}) {
				break
			}
			scroll, e.Scroll = h.filter.pointer.clampScroll(scroll)
		}
		e.Position = q.invTransform(h.pointer.areaPlusOne-1, e.Position)
		evts = append(evts, taggedEvent{tag: n.tag, event: e})
		if e.Kind != PointerScroll {
			break
		}
	}
	return evts
}

func (q *pointerQueue) ClipFor(area int, r image.Rectangle) image.Rectangle {
	a := &q.areas[area]
	parent := a.parent
	for parent != -1 {
		a := &q.areas[parent]
		r = r.Intersect(a.bounds())
		parent = a.parent
	}
	return r
}

func (q *pointerQueue) Push(handlers map[Tag]*routerHandler, state pointerState, e PointerEvent) (pointerState, []taggedEvent) {
	var evts []taggedEvent
	if e.Kind == PointerCancel {
		for k := range handlers {
			evts = append(evts, taggedEvent{
				event: PointerEvent{Kind: PointerCancel},
				tag:   k,
			})
		}
		state.pointers = nil
		return state, evts
	}
	state, pidx := state.pointerOf(e)
	p := state.pointers[pidx]

	switch e.Kind {
	case PointerPress:
		p, evts, state.cursor, _ = q.deliverEnterLeaveEvents(handlers, state.cursor, p, evts, e)
		p.pressed = true
		evts = q.deliverEvent(handlers, p, evts, e)
	case PointerMove:
		if p.pressed {
			e.Kind = PointerDrag
		}
		p, evts, state.cursor, _ = q.deliverEnterLeaveEvents(handlers, state.cursor, p, evts, e)
		evts = q.deliverEvent(handlers, p, evts, e)
		if p.pressed {
			p, evts = q.deliverDragEvent(handlers, p, evts)
		}
	case PointerRelease:
		evts = q.deliverEvent(handlers, p, evts, e)
		p.pressed = false
		p, evts, state.cursor, _ = q.deliverEnterLeaveEvents(handlers, state.cursor, p, evts, e)
		p, evts = q.deliverDropEvent(handlers, p, evts)
	case PointerScroll:
		p, evts, state.cursor, _ = q.deliverEnterLeaveEvents(handlers, state.cursor, p, evts, e)
		evts = q.deliverEvent(handlers, p, evts, e)
	}

	p.last = e
	if !p.pressed && len(p.entered) == 0 {
		// concat equivalent: remove pidx
		state.pointers = concatPointers(state.pointers[:pidx:pidx], state.pointers[pidx+1:])
	} else {
		state.pointers = clonePointers(state.pointers)
		state.pointers[pidx] = p
	}
	return state, evts
}

func (q *pointerQueue) deliverEvent(handlers map[Tag]*routerHandler, p pointerInfo, evts []taggedEvent, e PointerEvent) []taggedEvent {
	if p.pressed && len(p.handlers) == 1 {
		e.Priority = Grabbed
	}
	scroll := e.Scroll
	for _, k := range p.handlers {
		h, ok := handlers[k]
		if !ok {
			continue
		}
		f := h.filter.pointer
		if !f.Matches(e) {
			continue
		}
		if e.Kind == PointerScroll {
			if scroll == (Point{}) {
				return evts
			}
			scroll, e.Scroll = f.clampScroll(scroll)
		}
		ev := e
		ev.Position = q.invTransform(h.pointer.areaPlusOne-1, e.Position)
		evts = append(evts, taggedEvent{event: ev, tag: k})
	}
	return evts
}

func (q *pointerQueue) deliverEnterLeaveEvents(handlers map[Tag]*routerHandler, cursor Cursor, p pointerInfo, evts []taggedEvent, e PointerEvent) (pointerInfo, []taggedEvent, Cursor, bool) {
	changed := false
	var hits []Tag
	if e.Source != Mouse && !p.pressed && e.Kind != PointerPress {
		// Non-mouse pointers leave when released.
	} else {
		var transSrc *pointerFilter
		if p.dataSource != nil {
			transSrc = &handlers[p.dataSource].filter.pointer
		}
		cursor = q.hitTest(e.Position, func(n *hitNode) bool {
			h, ok := handlers[n.tag]
			if !ok {
				return true
			}
			add := true
			if p.pressed {
				add = false
				if _, found := searchTag(p.handlers, n.tag); found {
					add = true
				}
				if transSrc != nil {
					if _, ok := firstMimeMatch(transSrc, &h.filter.pointer); ok {
						add = true
					}
				}
			}
			if add {
				hits = addTagToList(hits, n.tag)
			}
			return true
		})
		if !p.pressed {
			changed = true
			p.handlers = hits
		}
	}
	// Deliver Leave events.
	for _, k := range p.entered {
		if _, found := searchTag(hits, k); found {
			continue
		}
		h, ok := handlers[k]
		if !ok {
			continue
		}
		changed = true
		ev := e
		ev.Kind = PointerLeave
		if h.filter.pointer.Matches(ev) {
			ev.Position = q.invTransform(h.pointer.areaPlusOne-1, ev.Position)
			evts = append(evts, taggedEvent{tag: k, event: ev})
		}
	}
	// Deliver Enter events.
	for _, k := range hits {
		if _, found := searchTag(p.entered, k); found {
			continue
		}
		h, ok := handlers[k]
		if !ok {
			continue
		}
		changed = true
		ev := e
		ev.Kind = PointerEnter
		if h.filter.pointer.Matches(ev) {
			ev.Position = q.invTransform(h.pointer.areaPlusOne-1, ev.Position)
			evts = append(evts, taggedEvent{tag: k, event: ev})
		}
	}
	p.entered = hits
	return p, evts, cursor, changed
}

func (q *pointerQueue) deliverDragEvent(handlers map[Tag]*routerHandler, p pointerInfo, evts []taggedEvent) (pointerInfo, []taggedEvent) {
	if p.dataSource != nil {
		return p, evts
	}
	for _, k := range p.entered {
		src := &handlers[k].filter.pointer
		if len(src.sourceMimes) == 0 {
			continue
		}
		p.dataSource = k
		for k, tgt := range handlers {
			if _, ok := firstMimeMatch(src, &tgt.filter.pointer); ok {
				evts = append(evts, taggedEvent{tag: k, event: TransferInitiateEvent{}})
			}
		}
		break
	}
	return p, evts
}

func (q *pointerQueue) deliverDropEvent(handlers map[Tag]*routerHandler, p pointerInfo, evts []taggedEvent) (pointerInfo, []taggedEvent) {
	if p.dataSource == nil {
		return p, evts
	}
	src := &handlers[p.dataSource].filter.pointer
	for _, k := range p.entered {
		h := handlers[k]
		if m, ok := firstMimeMatch(src, &h.filter.pointer); ok {
			p.dataTarget = k
			evts = append(evts, taggedEvent{tag: p.dataSource, event: TransferRequestEvent{Type: m}})
			return p, evts
		}
	}
	return q.deliverTransferCancelEvent(handlers, p, evts)
}

func (q *pointerQueue) deliverTransferCancelEvent(handlers map[Tag]*routerHandler, p pointerInfo, evts []taggedEvent) (pointerInfo, []taggedEvent) {
	evts = append(evts, taggedEvent{tag: p.dataSource, event: TransferCancelEvent{}})
	src := &handlers[p.dataSource].filter.pointer
	for k, h := range handlers {
		if _, ok := firstMimeMatch(src, &h.filter.pointer); ok {
			evts = append(evts, taggedEvent{tag: k, event: TransferCancelEvent{}})
		}
	}
	p.dataSource = nil
	p.dataTarget = nil
	return p, evts
}

func (p *pointerFilter) Add(f Filter) {
	switch f := f.(type) {
	case PointerFilter:
		p.kinds = p.kinds | f.Kinds
		p.scrollX = p.scrollX.Union(f.ScrollX)
		p.scrollY = p.scrollY.Union(f.ScrollY)
	}
}

func (p *pointerFilter) AddTransfer(f Filter) {
	switch f := f.(type) {
	case TransferSourceFilter:
		if !containsStr(p.sourceMimes, f.Type) {
			p.sourceMimes = append(p.sourceMimes, f.Type)
		}
	case TransferTargetFilter:
		if !containsStr(p.targetMimes, f.Type) {
			p.targetMimes = append(p.targetMimes, f.Type)
		}
	}
}

func (p *pointerFilter) Matches(e Event) bool {
	switch e := e.(type) {
	case PointerEvent:
		return e.Kind&p.kinds == e.Kind
	case TransferCancelEvent, TransferInitiateEvent:
		return len(p.sourceMimes) > 0 || len(p.targetMimes) > 0
	case TransferRequestEvent:
		return containsStr(p.sourceMimes, e.Type)
	case TransferDataEvent:
		return containsStr(p.targetMimes, e.Type)
	}
	return false
}

func (p *pointerFilter) Merge(p2 pointerFilter) {
	p.kinds = p.kinds | p2.kinds
	p.scrollX = p.scrollX.Union(p2.scrollX)
	p.scrollY = p.scrollY.Union(p2.scrollY)
	p.sourceMimes = append(p.sourceMimes, p2.sourceMimes...)
	p.targetMimes = append(p.targetMimes, p2.targetMimes...)
}

func (p *pointerFilter) clampScroll(scroll Point) (left, scrolled Point) {
	left.X, scrolled.X = clampSplit(scroll.X, p.scrollX.Min, p.scrollX.Max)
	left.Y, scrolled.Y = clampSplit(scroll.Y, p.scrollY.Min, p.scrollY.Max)
	return
}

func clampSplit(v float32, min, max int) (float32, float32) {
	if m := float32(max); v > m {
		return v - m, m
	}
	if m := float32(min); v < m {
		return v - m, m
	}
	return 0, v
}

func (op *areaOp) Hit(pos Point) bool {
	pos = pos.Sub(FPt(op.rect.Min))
	size := FPt(op.rect.Size())
	switch op.kind {
	case areaRect:
		return 0 <= pos.X && pos.X < size.X &&
			0 <= pos.Y && pos.Y < size.Y
	case areaEllipse:
		rx := size.X / 2
		ry := size.Y / 2
		xh := pos.X - rx
		yk := pos.Y - ry
		return (xh*xh)/(rx*rx)+(yk*yk)/(ry*ry) <= 1
	default:
		panic("invalid area kind")
	}
}

func (a *areaNode) bounds() image.Rectangle {
	return Rectangle{
		Min: a.trans.Transform(FPt(a.area.rect.Min)),
		Max: a.trans.Transform(FPt(a.area.rect.Max)),
	}.Round()
}

// ---------------------------------------------------------------------------
// Key queue (ported from key.go)
// ---------------------------------------------------------------------------

type keyQueue struct {
	order    []Tag
	dirOrder []dirFocusEntry
	hint     InputHint
}

type keyState struct {
	focus   Tag
	state   TextInputState
	content EditorState
}

type keyHandler struct {
	visible      bool
	reset        bool
	hint         InputHint
	orderPlusOne int
	dirOrder     int
	trans        Affine2D
}

type keyFilterList []KeyFilter

type dirFocusEntry struct {
	tag    Tag
	row    int
	area   int
	bounds image.Rectangle
}

func (k *keyHandler) inputHint(hint InputHint) { k.hint = hint }

func (s keyState) InputState() (keyState, TextInputState) {
	state := s.state
	s.state = TextInputKeep
	return s, state
}

func (q *keyQueue) InputHint(handlers map[Tag]*routerHandler, state keyState) (InputHint, bool) {
	focused, ok := handlers[state.focus]
	if !ok {
		return q.hint, false
	}
	old := q.hint
	q.hint = focused.key.hint
	return q.hint, old != q.hint
}

func (k *keyHandler) Reset() {
	k.visible = false
	k.orderPlusOne = 0
	k.hint = HintAny
}

func (q *keyQueue) Reset() {
	q.order = q.order[:0]
	q.dirOrder = q.dirOrder[:0]
}

func (k *keyHandler) ResetEvent() (Event, bool) {
	if k.reset {
		return nil, false
	}
	k.reset = true
	return KeyFocusEvent{Focus: false}, true
}

func (q *keyQueue) Frame(handlers map[Tag]*routerHandler, state keyState) keyState {
	if state.focus != nil {
		if h, ok := handlers[state.focus]; !ok || !h.filter.focusable || !h.key.visible {
			state.focus = nil
			state.state = TextInputClose
		}
	}
	q.updateFocusLayout(handlers)
	return state
}

func (q *keyQueue) updateFocusLayout(handlers map[Tag]*routerHandler) {
	order := q.dirOrder
	// Sort by ascending Y - insertion sort (stable).
	for i := 1; i < len(order); i++ {
		for j := i; j > 0 && order[j].bounds.Min.Y < order[j-1].bounds.Min.Y; j-- {
			order[j], order[j-1] = order[j-1], order[j]
		}
	}
	row := 0
	i := 0
	for i < len(order) {
		h := &order[i]
		h.row = row
		bottom := h.bounds.Max.Y
		end := i + 1
		for end < len(order) {
			h2 := &order[end]
			center := (h2.bounds.Min.Y + h2.bounds.Max.Y) / 2
			if center > bottom {
				break
			}
			h2.row = row
			end++
		}
		// Sort row by ascending X.
		for a := i + 1; a < end; a++ {
			for b := a; b > i && order[b].bounds.Min.X < order[b-1].bounds.Min.X; b-- {
				order[b], order[b-1] = order[b-1], order[b]
			}
		}
		i = end
		row++
	}
	for i, o := range q.dirOrder {
		handlers[o.tag].key.dirOrder = i
	}
}

func (q *keyQueue) MoveFocus(handlers map[Tag]*routerHandler, state keyState, dir FocusDirection) (keyState, []taggedEvent) {
	if len(q.dirOrder) == 0 {
		return state, nil
	}
	order := 0
	if state.focus != nil {
		order = handlers[state.focus].key.dirOrder
	}
	focus := q.dirOrder[order]
	switch dir {
	case FocusForward, FocusBackward:
		if len(q.order) == 0 {
			break
		}
		ord := 0
		if dir == FocusBackward {
			ord = -1
		}
		if state.focus != nil {
			ord = handlers[state.focus].key.orderPlusOne - 1
			if dir == FocusForward {
				ord++
			} else {
				ord--
			}
		}
		ord = (ord + len(q.order)) % len(q.order)
		return q.Focus(handlers, state, q.order[ord])
	case FocusRight, FocusLeft:
		next := order
		if state.focus != nil {
			next = order + 1
			if dir == FocusLeft {
				next = order - 1
			}
		}
		if 0 <= next && next < len(q.dirOrder) {
			newFocus := q.dirOrder[next]
			if newFocus.row == focus.row {
				return q.Focus(handlers, state, newFocus.tag)
			}
		}
	case FocusUp, FocusDown:
		delta := +1
		if dir == FocusUp {
			delta = -1
		}
		nextRow := 0
		if state.focus != nil {
			nextRow = focus.row + delta
		}
		var closest Tag
		dist := 1 << 30
		center := (focus.bounds.Min.X + focus.bounds.Max.X) / 2
		ord := order
	focusLoop:
		for 0 <= ord && ord < len(q.dirOrder) {
			next := q.dirOrder[ord]
			switch next.row {
			case nextRow:
				nextCenter := (next.bounds.Min.X + next.bounds.Max.X) / 2
				d := center - nextCenter
				if d < 0 {
					d = -d
				}
				if d > dist {
					break focusLoop
				}
				dist = d
				closest = next.tag
			case nextRow + delta:
				break focusLoop
			}
			ord += delta
		}
		if closest != nil {
			return q.Focus(handlers, state, closest)
		}
	}
	return state, nil
}

func (q *keyQueue) BoundsFor(k *keyHandler) image.Rectangle {
	return q.dirOrder[k.dirOrder].bounds
}

func (q *keyQueue) AreaFor(k *keyHandler) int {
	return q.dirOrder[k.dirOrder].area
}

func (k *keyFilterList) Matches(focus Tag, e KeyEvent, system bool) bool {
	for _, f := range *k {
		if keyFilterMatch(focus, f, e, system) {
			return true
		}
	}
	return false
}

func keyFilterMatch(focus Tag, f KeyFilter, e KeyEvent, system bool) bool {
	if f.Focus != nil && f.Focus != focus {
		return false
	}
	if (f.Name != "" || system) && f.Name != e.Name {
		return false
	}
	if e.Modifiers&f.Required != f.Required {
		return false
	}
	if e.Modifiers&^(f.Required|f.Optional) != 0 {
		return false
	}
	return true
}

func (q *keyQueue) Focus(handlers map[Tag]*routerHandler, state keyState, focus Tag) (keyState, []taggedEvent) {
	if focus == state.focus {
		return state, nil
	}
	state.content = EditorState{}
	state.content.Selection.Transform = AffineId()
	var evts []taggedEvent
	if state.focus != nil {
		evts = append(evts, taggedEvent{tag: state.focus, event: KeyFocusEvent{Focus: false}})
	}
	state.focus = focus
	if state.focus != nil {
		evts = append(evts, taggedEvent{tag: state.focus, event: KeyFocusEvent{Focus: true}})
	}
	if state.focus == nil || state.state == TextInputKeep {
		state.state = TextInputClose
	}
	return state, evts
}

func (s keyState) softKeyboard(show bool) keyState {
	if show {
		s.state = TextInputOpen
	} else {
		s.state = TextInputClose
	}
	return s
}

func (k *keyFilterList) Add(f KeyFilter) {
	for _, existing := range *k {
		if existing == f {
			return
		}
	}
	*k = append(*k, f)
}

func (k *keyFilterList) Merge(k2 keyFilterList) {
	*k = append(*k, k2...)
}

func (q *keyQueue) inputOp(tag Tag, state *keyHandler, t Affine2D, area int, bounds image.Rectangle) {
	state.visible = true
	if state.orderPlusOne == 0 {
		state.orderPlusOne = len(q.order) + 1
		q.order = append(q.order, tag)
		q.dirOrder = append(q.dirOrder, dirFocusEntry{tag: tag, area: area, bounds: bounds})
	}
	state.trans = t
}

func (q *keyQueue) setSelection(state keyState, req SelectionCmd) keyState {
	if req.Tag != state.focus {
		return state
	}
	state.content.Selection.KeyRange = req.KeyRange
	state.content.Selection.Caret = req.Caret
	return state
}

func (q *keyQueue) editorState(handlers map[Tag]*routerHandler, state keyState) EditorState {
	s := state.content
	if f := state.focus; f != nil {
		s.Selection.Transform = handlers[f].key.trans
	}
	return s
}

func (q *keyQueue) setSnippet(state keyState, req SnippetCmd) keyState {
	if req.Tag == state.focus {
		state.content.Snippet = req.Snippet
	}
	return state
}

// ---------------------------------------------------------------------------
// Clipboard queue (ported from clipboard.go)
// ---------------------------------------------------------------------------

type clipboardState struct {
	receivers []Tag
}

type clipboardQueue struct {
	requested bool
	mime      string
	text      []byte
}

func (q *clipboardQueue) WriteClipboard() (mime string, content []byte, ok bool) {
	if q.text == nil {
		return "", nil, false
	}
	content = q.text
	q.text = nil
	return q.mime, content, true
}

func (q *clipboardQueue) ClipboardRequested(state clipboardState) bool {
	req := len(state.receivers) > 0 && q.requested
	q.requested = false
	return req
}

func (q *clipboardQueue) Push(state clipboardState, e Event) (clipboardState, []taggedEvent) {
	var evts []taggedEvent
	for _, r := range state.receivers {
		evts = append(evts, taggedEvent{tag: r, event: e})
	}
	state.receivers = nil
	return state, evts
}

func (q *clipboardQueue) ProcessWriteClipboard(req ClipboardWriteCmd) {
	if req.Data != nil {
		content, err := io.ReadAll(req.Data)
		req.Data.Close()
		if err != nil {
			return
		}
		q.mime = req.Type
		q.text = content
	}
}

func (q *clipboardQueue) ProcessReadClipboard(state clipboardState, tag Tag) clipboardState {
	if containsTag(state.receivers, tag) {
		return state
	}
	n := len(state.receivers)
	state.receivers = append(state.receivers[:n:n], tag)
	q.requested = true
	return state
}

// ---------------------------------------------------------------------------
// Translation: AppPointerEvent → PointerEvent, AppKeyEvent → KeyEvent
// ---------------------------------------------------------------------------

func appPointerToPointerEvent(e AppPointerEvent) PointerEvent {
	var kind PointerKind
	switch e.Kind {
	case WinPointerMove:
		kind = PointerMove
	case WinPointerPress:
		kind = PointerPress
	case WinPointerRelease:
		kind = PointerRelease
	case WinPointerScroll:
		kind = PointerScroll
	case WinPointerCancel:
		kind = PointerCancel
	}
	src := Mouse
	touchID := PointerID(e.Buttons >> 8 & 0xff)
	if touchID != 0 {
		src = Touch
	}
	btns := PointerButtons(e.Buttons & 0xff)
	var mods Modifiers
	if e.Mods&ModAltBit != 0 {
		mods |= ModAlt
	}
	if e.Mods&ModCtrlBit != 0 {
		mods |= ModCtrl
	}
	if e.Mods&ModShiftBit != 0 {
		mods |= ModShift
	}
	if e.Mods&ModMetaBit != 0 {
		mods |= ModCommand
	}
	return PointerEvent{
		Kind:      kind,
		Source:    src,
		PointerID: touchID,
		Position:  Pt(e.X, e.Y),
		Scroll:    Pt(e.Dx, e.Dy),
		Buttons:   btns,
		Modifiers: mods,
	}
}

func appKeyToKeyEvent(e AppKeyEvent) (KeyEvent, bool) {
	name := keyCodeToKeyName(e.Code, e.Mods)
	if name == "" {
		return KeyEvent{}, false
	}
	var mods Modifiers
	if e.Mods&ModAltBit != 0 {
		mods |= ModAlt
	}
	if e.Mods&ModCtrlBit != 0 {
		mods |= ModCtrl
	}
	if e.Mods&ModShiftBit != 0 {
		mods |= ModShift
	}
	if e.Mods&ModMetaBit != 0 {
		mods |= ModCommand
	}
	state := KeyRelease
	if e.Press {
		state = KeyPress
	}
	return KeyEvent{Name: name, Modifiers: mods, State: state}, true
}

// keyCodeToKeyName maps AppKeyEvent.Code to a KeyName.
func keyCodeToKeyName(code, mods int32) KeyName {
	switch code {
	case KeyArrowUp:
		return KeyNameUpArrow
	case KeyArrowDown:
		return KeyNameDownArrow
	case KeyArrowLeft:
		return KeyNameLeftArrow
	case KeyArrowRight:
		return KeyNameRightArrow
	case KeyEscape:
		return KeyNameEscape
	case KeyEnter:
		return KeyNameReturn
	case KeyBackspace:
		return KeyNameDeleteBackward
	case KeyDelete:
		return KeyNameDeleteForward
	case KeyHome:
		return KeyNameHome
	case KeyEnd:
		return KeyNameEnd
	case KeyPageUp:
		return KeyNamePageUp
	case KeyPageDown:
		return KeyNamePageDown
	case KeyTab:
		return KeyNameTab
	case KeySpace:
		return KeyNameSpace
	case KeyF1:
		return KeyNameF1
	case KeyF1 + 1:
		return KeyNameF2
	case KeyF1 + 2:
		return KeyNameF3
	case KeyF1 + 3:
		return KeyNameF4
	case KeyF1 + 4:
		return KeyNameF5
	case KeyF1 + 5:
		return KeyNameF6
	case KeyF1 + 6:
		return KeyNameF7
	case KeyF1 + 7:
		return KeyNameF8
	case KeyF1 + 8:
		return KeyNameF9
	case KeyF1 + 9:
		return KeyNameF10
	case KeyF1 + 10:
		return KeyNameF11
	case KeyF12:
		return KeyNameF12
	case KeyCtrl:
		return KeyNameCtrl
	case KeyShift:
		return KeyNameShift
	case KeyAlt:
		return KeyNameAlt
	case KeySuper:
		return KeyNameSuper
	case KeyCommand:
		return KeyNameCommand
	}
	// Printable ASCII: code is uppercase codepoint.
	if code >= 0x20 && code <= 0x7e {
		// Apply shift for lowercase vs uppercase.
		if mods&ModShiftBit == 0 && code >= 'A' && code <= 'Z' {
			// return lowercase
			return KeyName(string(rune(code + 32)))
		}
		return KeyName(string(rune(code)))
	}
	return ""
}

// ---------------------------------------------------------------------------
// Slice helpers (replaces slices package)
// ---------------------------------------------------------------------------

func containsTag(tags []Tag, tag Tag) bool {
	for _, t := range tags {
		if t == tag {
			return true
		}
	}
	return false
}

func containsStr(ss []string, s string) bool {
	for _, v := range ss {
		if v == s {
			return true
		}
	}
	return false
}

func searchTag(tags []Tag, tag Tag) (int, bool) {
	for i, t := range tags {
		if t == tag {
			return i, true
		}
	}
	return 0, false
}

func addTagToList(tags []Tag, tag Tag) []Tag {
	if containsTag(tags, tag) {
		return tags
	}
	return append(tags, tag)
}

func firstMimeMatch(src, tgt *pointerFilter) (first string, matched bool) {
	for _, m1 := range tgt.targetMimes {
		if containsStr(src.sourceMimes, m1) {
			return m1, true
		}
	}
	return "", false
}

func clonePointers(s []pointerInfo) []pointerInfo {
	c := []pointerInfo{:len(s):len(s)}
	copy(c, s)
	return c
}

func concatPointers(a, b []pointerInfo) []pointerInfo {
	r := []pointerInfo{:len(a)+len(b):len(a)+len(b)}
	copy(r, a)
	copy(r[len(a):], b)
	return r
}

func deleteTaggedEvent(s []taggedEvent, i, j int) []taggedEvent {
	copy(s[i:], s[j:])
	return s[:len(s)-(j-i)]
}

func deleteSemanticID(s []semanticID, i, j int) []semanticID {
	copy(s[i:], s[j:])
	return s[:len(s)-(j-i)]
}