package main

// Conflict analysis, deterministic merge, and free-chord suggestion.

import (
	"fmt"
	"sort"
)

// Conflict kinds.
const (
	KindDuplicate = "duplicate-chord"  // one chord, two different actions, same spelling
	KindAlias     = "alias-collision"  // one chord, two different actions, different spellings
	KindPrefix    = "prefix-sequence"  // one binding is a strict prefix of another
	KindDivergent = "divergent-action" // one action, different chords in different sets
	KindReserved  = "reserved-chord"   // collides with an OS-reserved chord
)

// Severities.
const (
	SevError   = "error"
	SevWarning = "warning"
)

// Party is one binding involved in a conflict.
type Party struct {
	Set    string `json:"set"`
	File   string `json:"file"`
	Action string `json:"action"`
	Chord  string `json:"chord"`
	Raw    string `json:"raw"`
	Base   bool   `json:"base,omitempty"`
}

func party(b LoadedBinding) Party {
	return Party{Set: b.Set, File: b.File, Action: b.Action, Chord: b.Canon, Raw: b.Raw, Base: b.IsBase}
}

// Conflict is one finding.
type Conflict struct {
	Kind        string   `json:"kind"`
	Severity    string   `json:"severity"`
	Chord       string   `json:"chord,omitempty"`
	Action      string   `json:"action,omitempty"`
	Detail      string   `json:"detail"`
	OS          string   `json:"os,omitempty"`
	OSDoes      string   `json:"os_does,omitempty"`
	OSSource    string   `json:"os_source,omitempty"`
	Position    int      `json:"chord_position,omitempty"`
	Involved    []Party  `json:"involved"`
	Suggestions []string `json:"suggestions,omitempty"`
}

func sortParties(ps []Party) {
	sort.Slice(ps, func(i, j int) bool {
		if ps[i].Set != ps[j].Set {
			return ps[i].Set < ps[j].Set
		}
		if ps[i].Action != ps[j].Action {
			return ps[i].Action < ps[j].Action
		}
		return ps[i].Chord < ps[j].Chord
	})
}

func sortConflicts(cs []Conflict) {
	sort.SliceStable(cs, func(i, j int) bool {
		a, b := cs[i], cs[j]
		if a.Kind != b.Kind {
			return a.Kind < b.Kind
		}
		if a.Chord != b.Chord {
			return a.Chord < b.Chord
		}
		if a.Action != b.Action {
			return a.Action < b.Action
		}
		if a.OS != b.OS {
			return a.OS < b.OS
		}
		return a.Detail < b.Detail
	})
}

// distinct returns the sorted distinct values of f over bs.
func distinct(bs []LoadedBinding, f func(LoadedBinding) string) []string {
	seen := map[string]bool{}
	var out []string
	for _, b := range bs {
		v := f(b)
		if !seen[v] {
			seen[v] = true
			out = append(out, v)
		}
	}
	sort.Strings(out)
	return out
}

// Analyse finds every conflict across the loaded bindings. suggestN free-chord
// proposals are attached to each error-severity conflict (0 disables).
func Analyse(in Inputs, suggestN int) []Conflict {
	bs := in.Bindings
	var out []Conflict

	// Index by canonical chord sequence, in sorted key order for determinism.
	byCanon := map[string][]LoadedBinding{}
	for _, b := range bs {
		byCanon[b.Canon] = append(byCanon[b.Canon], b)
	}
	canons := make([]string, 0, len(byCanon))
	for k := range byCanon {
		canons = append(canons, k)
	}
	sort.Strings(canons)

	// 1 + 2. One chord claimed by more than one action.
	for _, canon := range canons {
		group := byCanon[canon]
		actions := distinct(group, func(b LoadedBinding) string { return b.Action })
		if len(actions) < 2 {
			continue
		}
		raws := distinct(group, func(b LoadedBinding) string { return b.Raw })
		kind := KindDuplicate
		detail := fmt.Sprintf("%s is bound to %d different actions (%s)", canon, len(actions), joinQuoted(actions))
		if len(raws) > 1 {
			kind = KindAlias
			detail = fmt.Sprintf("%s is bound to %d different actions (%s); the collision is only visible after normalisation, the files spell it %s",
				canon, len(actions), joinQuoted(actions), joinQuoted(raws))
		}
		c := Conflict{Kind: kind, Severity: SevError, Chord: canon, Detail: detail}
		for _, b := range group {
			c.Involved = append(c.Involved, party(b))
		}
		sortParties(c.Involved)
		out = append(out, c)
	}

	// 3. Prefix conflicts between multi-chord sequences.
	for i := 0; i < len(canons); i++ {
		for j := 0; j < len(canons); j++ {
			if i == j {
				continue
			}
			a, b := byCanon[canons[i]][0].Seq, byCanon[canons[j]][0].Seq
			if !a.StrictPrefixOf(b) {
				continue
			}
			c := Conflict{
				Kind:     KindPrefix,
				Severity: SevError,
				Chord:    canons[i],
				Detail: fmt.Sprintf("%q is a strict prefix of %q - pressing the shorter binding can never resolve without a timeout, and one of the two will not fire",
					canons[i], canons[j]),
			}
			for _, x := range byCanon[canons[i]] {
				c.Involved = append(c.Involved, party(x))
			}
			for _, x := range byCanon[canons[j]] {
				c.Involved = append(c.Involved, party(x))
			}
			sortParties(c.Involved)
			out = append(out, c)
		}
	}

	// 4. One action, different chords in different sets.
	byAction := map[string][]LoadedBinding{}
	for _, b := range bs {
		byAction[b.Action] = append(byAction[b.Action], b)
	}
	actions := make([]string, 0, len(byAction))
	for k := range byAction {
		actions = append(actions, k)
	}
	sort.Strings(actions)
	for _, a := range actions {
		group := byAction[a]
		chords := distinct(group, func(b LoadedBinding) string { return b.Canon })
		if len(chords) < 2 {
			continue
		}
		c := Conflict{
			Kind:     KindDivergent,
			Severity: SevWarning,
			Action:   a,
			Detail: fmt.Sprintf("action %q is bound to %d different chords across the sets (%s) - muscle memory will not transfer between machines",
				a, len(chords), joinQuoted(chords)),
		}
		for _, b := range group {
			c.Involved = append(c.Involved, party(b))
		}
		sortParties(c.Involved)
		out = append(out, c)
	}

	// 5. Collisions with the built-in OS reserved tables.
	for _, canon := range canons {
		group := byCanon[canon]
		for _, hit := range reservedHits(group[0].Seq) {
			where := ""
			if len(group[0].Seq) > 1 {
				where = fmt.Sprintf(" (chord %d of %d in the sequence)", hit.Position, len(group[0].Seq))
			}
			c := Conflict{
				Kind:     KindReserved,
				Severity: SevWarning,
				Chord:    canon,
				OS:       hit.OS,
				OSDoes:   hit.Does,
				OSSource: hit.Source,
				Position: hit.Position,
				Detail: fmt.Sprintf("%s is reserved by %s%s - the OS uses it to %s",
					hit.Chord, osLabel(hit.OS), where, hit.Does),
			}
			for _, b := range group {
				c.Involved = append(c.Involved, party(b))
			}
			sortParties(c.Involved)
			out = append(out, c)
		}
	}

	if suggestN > 0 {
		free := newChordSpace(in.Bindings, nil)
		for i := range out {
			if out[i].Severity != SevError {
				continue
			}
			seq := byCanon[out[i].Chord][0].Seq
			out[i].Suggestions = free.suggest(seq[len(seq)-1], suggestN)
		}
	}

	sortConflicts(out)
	return out
}

func osLabel(os string) string {
	switch os {
	case OSWindows:
		return "Windows"
	case OSMacOS:
		return "macOS"
	default:
		return os
	}
}

func joinQuoted(vs []string) string {
	out := ""
	for i, v := range vs {
		if i > 0 {
			out += ", "
		}
		out += fmt.Sprintf("%q", v)
	}
	return out
}

// ---------------------------------------------------------------------------
// Merge
// ---------------------------------------------------------------------------

// DeckEntry is one binding in the merged deck.
type DeckEntry struct {
	Action   string        `json:"action"`
	Chord    string        `json:"chord"`
	Set      string        `json:"set"`
	File     string        `json:"file"`
	Origin   string        `json:"origin"`
	Override bool          `json:"override,omitempty"`
	Note     string        `json:"note,omitempty"`
	Reserved []ReservedHit `json:"reserved,omitempty"`

	seq Sequence
}

// Resolution records one merge decision, kept or dropped, with its reason.
type Resolution struct {
	Decision    string `json:"decision"` // kept | dropped | duplicate
	Reason      string `json:"reason"`   // machine-readable reason code
	Action      string `json:"action"`
	Chord       string `json:"chord"`
	Set         string `json:"set"`
	File        string `json:"file"`
	Explanation string `json:"explanation"`
}

// Reason codes.
const (
	ReasonAccepted    = "accepted"
	ReasonChordTaken  = "chord-already-bound"
	ReasonActionTaken = "action-already-bound"
	ReasonPrefix      = "prefix-of-kept-binding"
	ReasonIdentical   = "identical-binding"
)

// Deck is the merged result. It contains no timestamps or input ordering, so
// two merges of the same sets in any order compare byte-for-byte equal.
type Deck struct {
	Base        string       `json:"base,omitempty"`
	Sets        []string     `json:"sets"`
	Bindings    []DeckEntry  `json:"bindings"`
	Resolutions []Resolution `json:"resolutions"`
	Warnings    []string     `json:"warnings"`
	Suggestions []Suggestion `json:"suggestions"`
}

// Suggestion offers replacement chords for a binding the merge had to drop.
type Suggestion struct {
	Set    string   `json:"set"`
	Action string   `json:"action"`
	Chord  string   `json:"chord"`
	Free   []string `json:"free_chords"`
}

// mergeSortKey orders the candidate bindings. It is built ONLY from intrinsic
// properties - priority, set name, action, chord - never from the order the
// files were given on the command line. That is what makes merge
// order-independent.
func mergeSortKey(a, b LoadedBinding) bool {
	if a.priority() != b.priority() {
		return a.priority() < b.priority()
	}
	if a.Set != b.Set {
		return a.Set < b.Set
	}
	if a.Action != b.Action {
		return a.Action < b.Action
	}
	return a.Canon < b.Canon
}

// Merge resolves every conflict and returns a deck plus a full audit of the
// decisions. suggestN free chords are proposed for each dropped binding.
func Merge(in Inputs, suggestN int) Deck {
	cands := make([]LoadedBinding, len(in.Bindings))
	copy(cands, in.Bindings)
	sort.SliceStable(cands, func(i, j int) bool { return mergeSortKey(cands[i], cands[j]) })

	deck := Deck{Base: in.BaseSet, Sets: in.setNames()}
	var kept []DeckEntry
	keptByChord := map[string]DeckEntry{}
	keptByAction := map[string]DeckEntry{}
	var dropped []LoadedBinding

	for _, b := range cands {
		if e, taken := keptByChord[b.Canon]; taken {
			if e.Action == b.Action {
				deck.Resolutions = append(deck.Resolutions, Resolution{
					Decision: "duplicate", Reason: ReasonIdentical,
					Action: b.Action, Chord: b.Canon, Set: b.Set, File: b.File,
					Explanation: fmt.Sprintf("kept %s -> %s from %s (%s); %s declares exactly the same binding, so nothing changed",
						e.Action, e.Chord, e.Set, e.Origin, b.Set),
				})
				continue
			}
			deck.Resolutions = append(deck.Resolutions, Resolution{
				Decision: "dropped", Reason: ReasonChordTaken,
				Action: b.Action, Chord: b.Canon, Set: b.Set, File: b.File,
				Explanation: fmt.Sprintf("kept %s -> %s from %s (%s), dropped %s -> %s from %s because the chord is already bound to a different action",
					e.Action, e.Chord, e.Set, e.Origin, b.Action, b.Canon, b.File),
			})
			dropped = append(dropped, b)
			continue
		}
		if e, taken := keptByAction[b.Action]; taken {
			deck.Resolutions = append(deck.Resolutions, Resolution{
				Decision: "dropped", Reason: ReasonActionTaken,
				Action: b.Action, Chord: b.Canon, Set: b.Set, File: b.File,
				Explanation: fmt.Sprintf("kept %s -> %s from %s (%s), dropped the alternate chord %s for the same action from %s because one action gets one chord",
					e.Action, e.Chord, e.Set, e.Origin, b.Canon, b.File),
			})
			dropped = append(dropped, b)
			continue
		}
		if e, clash := prefixClash(kept, b.Seq); clash {
			deck.Resolutions = append(deck.Resolutions, Resolution{
				Decision: "dropped", Reason: ReasonPrefix,
				Action: b.Action, Chord: b.Canon, Set: b.Set, File: b.File,
				Explanation: fmt.Sprintf("kept %s -> %s from %s (%s), dropped %s -> %s from %s because one sequence is a strict prefix of the other and only one of them could ever fire",
					e.Action, e.Chord, e.Set, e.Origin, b.Action, b.Canon, b.File),
			})
			dropped = append(dropped, b)
			continue
		}
		e := DeckEntry{
			Action: b.Action, Chord: b.Canon, Set: b.Set, File: b.File,
			Origin: b.origin(), Override: b.Override, Note: b.Note,
			Reserved: reservedHits(b.Seq), seq: b.Seq,
		}
		kept = append(kept, e)
		keptByChord[e.Chord] = e
		keptByAction[e.Action] = e
		deck.Resolutions = append(deck.Resolutions, Resolution{
			Decision: "kept", Reason: ReasonAccepted,
			Action: e.Action, Chord: e.Chord, Set: e.Set, File: e.File,
			Explanation: fmt.Sprintf("kept %s -> %s from %s (%s); nothing else claimed the chord at equal or higher precedence",
				e.Action, e.Chord, e.Set, e.Origin),
		})
	}

	// Warnings: everything that survived but still collides with an OS.
	for _, e := range kept {
		for _, h := range e.Reserved {
			deck.Warnings = append(deck.Warnings, fmt.Sprintf("%s -> %s (from %s) is reserved by %s, which uses it to %s [%s]",
				e.Action, e.Chord, e.Set, osLabel(h.OS), h.Does, h.Source))
		}
	}
	sort.Strings(deck.Warnings)

	// Suggestions for everything that had to be dropped.
	if suggestN > 0 && len(dropped) > 0 {
		space := newChordSpace(in.Bindings, kept)
		for _, b := range dropped {
			deck.Suggestions = append(deck.Suggestions, Suggestion{
				Set: b.Set, Action: b.Action, Chord: b.Canon,
				Free: space.suggest(b.Seq[len(b.Seq)-1], suggestN),
			})
		}
	}
	sort.SliceStable(deck.Suggestions, func(i, j int) bool {
		if deck.Suggestions[i].Action != deck.Suggestions[j].Action {
			return deck.Suggestions[i].Action < deck.Suggestions[j].Action
		}
		if deck.Suggestions[i].Set != deck.Suggestions[j].Set {
			return deck.Suggestions[i].Set < deck.Suggestions[j].Set
		}
		return deck.Suggestions[i].Chord < deck.Suggestions[j].Chord
	})

	sort.SliceStable(kept, func(i, j int) bool {
		if kept[i].Action != kept[j].Action {
			return kept[i].Action < kept[j].Action
		}
		return kept[i].Chord < kept[j].Chord
	})
	deck.Bindings = kept

	sort.SliceStable(deck.Resolutions, func(i, j int) bool {
		a, b := deck.Resolutions[i], deck.Resolutions[j]
		if a.Decision != b.Decision {
			return a.Decision < b.Decision
		}
		if a.Action != b.Action {
			return a.Action < b.Action
		}
		if a.Chord != b.Chord {
			return a.Chord < b.Chord
		}
		return a.Set < b.Set
	})

	if deck.Warnings == nil {
		deck.Warnings = []string{}
	}
	if deck.Suggestions == nil {
		deck.Suggestions = []Suggestion{}
	}
	return deck
}

// prefixClash reports the first kept entry whose sequence is a strict prefix of
// seq, or of which seq is a strict prefix.
func prefixClash(kept []DeckEntry, seq Sequence) (DeckEntry, bool) {
	for _, e := range kept {
		if e.seq.StrictPrefixOf(seq) || seq.StrictPrefixOf(e.seq) {
			return e, true
		}
	}
	return DeckEntry{}, false
}

// ---------------------------------------------------------------------------
// Suggestion of genuinely free chords
// ---------------------------------------------------------------------------

// suggestMods is the ordered search space of modifier combinations. Bare and
// single-modifier chords come last because they are the most likely to be
// wanted by the application itself.
var suggestMods = []Mod{
	ModCtrl | ModShift,
	ModCtrl | ModAlt,
	ModAlt | ModShift,
	ModCtrl | ModAlt | ModShift,
	ModMeta | ModShift,
	ModMeta | ModAlt,
	ModCtrl | ModMeta,
	ModCtrl | ModMeta | ModShift,
	ModMeta | ModAlt | ModShift,
	ModCtrl | ModAlt | ModMeta,
	ModCtrl | ModAlt | ModShift | ModMeta,
}

// suggestKeys is the ordered search space of keys.
var suggestKeys = buildSuggestKeys()

func buildSuggestKeys() []string {
	var ks []string
	for c := 'A'; c <= 'Z'; c++ {
		ks = append(ks, string(c))
	}
	for d := '0'; d <= '9'; d++ {
		ks = append(ks, string(d))
	}
	for i := 13; i <= 24; i++ {
		ks = append(ks, fmt.Sprintf("F%d", i))
	}
	return ks
}

// chordSpace knows which chords are unavailable.
type chordSpace struct {
	taken map[string]bool // canonical single chords that are used or led into
}

// newChordSpace marks as taken every chord any input binding uses, plus the
// first chord of every sequence (a single chord equal to it would be a prefix
// conflict), plus everything already in the deck.
func newChordSpace(all []LoadedBinding, deck []DeckEntry) *chordSpace {
	cs := &chordSpace{taken: map[string]bool{}}
	mark := func(seq Sequence) {
		for _, c := range seq {
			cs.taken[c.String()] = true
		}
	}
	for _, b := range all {
		mark(b.Seq)
	}
	for _, e := range deck {
		mark(e.seq)
	}
	return cs
}

// free reports whether c may be proposed: unused by every set and unreserved on
// BOTH Windows and macOS.
func (cs *chordSpace) free(c Chord) bool {
	if c.Mods == 0 {
		return false
	}
	if cs.taken[c.String()] {
		return false
	}
	return !isReservedAnywhere(c)
}

// suggest proposes up to n free chords, preferring chords that keep the key the
// author originally wanted, then chords that keep the modifiers.
func (cs *chordSpace) suggest(want Chord, n int) []string {
	if n <= 0 {
		return nil
	}
	var out []string
	seen := map[string]bool{}
	emit := func(c Chord) bool {
		s := c.String()
		if seen[s] || !cs.free(c) {
			return false
		}
		seen[s] = true
		out = append(out, s)
		return len(out) >= n
	}
	// Tier 1: same key, different modifiers.
	for _, m := range suggestMods {
		if m == want.Mods {
			continue
		}
		if emit(Chord{Mods: m, Key: want.Key}) {
			return out
		}
	}
	// Tier 2: same modifiers, different key.
	if want.Mods != 0 {
		for _, k := range suggestKeys {
			if k == want.Key {
				continue
			}
			if emit(Chord{Mods: want.Mods, Key: k}) {
				return out
			}
		}
	}
	// Tier 3: the rest of the space, in a fixed order.
	for _, m := range suggestMods {
		for _, k := range suggestKeys {
			if emit(Chord{Mods: m, Key: k}) {
				return out
			}
		}
	}
	return out
}

// ---------------------------------------------------------------------------
// explain
// ---------------------------------------------------------------------------

// Explanation is the answer to "who binds this chord?".
type Explanation struct {
	Query      string        `json:"query"`
	Chord      string        `json:"chord"`
	BoundBy    []Party       `json:"bound_by"`
	Reserved   []ReservedHit `json:"reserved"`
	PrefixOf   []Party       `json:"prefix_of"`
	PrefixedBy []Party       `json:"prefixed_by"`
	InDeck     *DeckEntry    `json:"in_merged_deck,omitempty"`
}

// Explain reports everything known about one chord or chord sequence.
func Explain(in Inputs, query string, seq Sequence, deck *Deck) Explanation {
	ex := Explanation{Query: query, Chord: seq.String(), Reserved: reservedHits(seq)}
	for _, b := range in.Bindings {
		switch {
		case b.Canon == ex.Chord:
			ex.BoundBy = append(ex.BoundBy, party(b))
		case seq.StrictPrefixOf(b.Seq):
			ex.PrefixOf = append(ex.PrefixOf, party(b))
		case b.Seq.StrictPrefixOf(seq):
			ex.PrefixedBy = append(ex.PrefixedBy, party(b))
		}
	}
	sortParties(ex.BoundBy)
	sortParties(ex.PrefixOf)
	sortParties(ex.PrefixedBy)
	if ex.BoundBy == nil {
		ex.BoundBy = []Party{}
	}
	if ex.PrefixOf == nil {
		ex.PrefixOf = []Party{}
	}
	if ex.PrefixedBy == nil {
		ex.PrefixedBy = []Party{}
	}
	if ex.Reserved == nil {
		ex.Reserved = []ReservedHit{}
	}
	if deck != nil {
		for i := range deck.Bindings {
			if deck.Bindings[i].Chord == ex.Chord {
				e := deck.Bindings[i]
				ex.InDeck = &e
				break
			}
		}
	}
	return ex
}