package prosediff

import "sort"

// Tuning constants for block alignment. They are deliberately package-level
// and documented rather than hidden in the code, because they are the knobs
// that decide whether a review page reads well.
const (
	// modifyThreshold is the token similarity two blocks need before they
	// are called "the same block, edited" rather than a delete plus an
	// insert. Below it, presenting a word diff would be noise.
	modifyThreshold = 0.40

	// shortBlockTokens is the size below which a block is considered too
	// small to judge by similarity alone.
	shortBlockTokens = 6

	// shortBlockThreshold applies instead of modifyThreshold when either
	// block is short: pairing "yes" with "no" on a 0.4 score helps nobody.
	shortBlockThreshold = 0.60

	// moveMinTokens is the smallest block that may be reported as moved.
	// Below it, identical content is far more likely to be coincidence
	// (a repeated "```", a "- see above") than an actual move.
	moveMinTokens = 5

	// pairBudget caps the similarity matrix inside one changed region. Past
	// it, only pairs within pairWindow of each other are considered; a
	// region with hundreds of blocks on both sides has no readable pairing
	// anyway.
	pairBudget = 4096
	pairWindow = 8
)

// region is one changed stretch of the alignment: blocks deleted from the old
// revision and blocks inserted into the new one, adjacent in the edit script.
type region struct {
	del []int // indices into old
	ins []int // indices into nw
}

// align turns two block sequences into the diff's change list.
//
// Three passes, in this order:
//  1. Myers over block hashes finds the unchanged skeleton.
//  2. Blocks left over from pass 1 that reappear verbatim elsewhere are
//     moves, grown outwards over their neighbours.
//  3. Similar-enough leftovers inside one changed region are modifications.
//
// Anything still unmatched is a plain insert or delete.
func align(old, nw []Block) []BlockChange {
	in := newInterner()
	oldIDs := make([]int, len(old))
	for i, b := range old {
		oldIDs[i] = in.id(b.Hash)
	}
	newIDs := make([]int, len(nw))
	for i, b := range nw {
		newIDs[i] = in.id(b.Hash)
	}
	script := diffInts(oldIDs, newIDs)

	var (
		out     []BlockChange
		regions []region
		// slots[i] is where region i's entries go in the output.
		slots []int
	)

	i, j := 0, 0
	for k := 0; k < len(script); {
		if script[k].op == OpEqual {
			for n := 0; n < script[k].n; n++ {
				o, w := old[i+n], nw[j+n]
				out = append(out, BlockChange{Kind: ChangeEqual, Old: &o, New: &w})
			}
			i += script[k].n
			j += script[k].n
			k++
			continue
		}
		var r region
		for ; k < len(script) && script[k].op != OpEqual; k++ {
			if script[k].op == OpDelete {
				for n := 0; n < script[k].n; n++ {
					r.del = append(r.del, i+n)
				}
				i += script[k].n
			} else {
				for n := 0; n < script[k].n; n++ {
					r.ins = append(r.ins, j+n)
				}
				j += script[k].n
			}
		}
		regions = append(regions, r)
		slots = append(slots, len(out))
		out = append(out, BlockChange{}) // placeholder, expanded below
	}

	moveOf, editedInMove := detectMoves(old, nw, regions)

	// Build each region's entries, then splice them in at their slot.
	expanded := make([][]BlockChange, len(regions))
	for ri, r := range regions {
		expanded[ri] = expandRegion(old, nw, r.del, r.ins, moveOf, editedInMove)
	}
	final := make([]BlockChange, 0, len(out)+len(regions))
	next := 0
	for idx := 0; idx < len(out); idx++ {
		if next < len(slots) && slots[next] == idx {
			final = append(final, expanded[next]...)
			next++
			continue
		}
		final = append(final, out[idx])
	}
	return final
}

// movePair records that old block o and new block n are the same content in a
// different place.
type movePair struct {
	oldIdx int
	newIdx int
}

// detectMoves matches leftover blocks across regions, seeding on exact hash
// equality and then growing each seed over its neighbours.
//
// Deliberate limitation: every move must be anchored by at least one block
// whose content is byte-identical after normalization. A block that moved and
// was edited is recognised only when it sits *between* two such anchors; a
// section that moved and was rewritten throughout falls through as a delete
// plus an insert. Matching moves by similarity alone would claim
// relationships between blocks that merely share boilerplate, and a wrong
// "moved from" costs a reviewer more than an honest add+remove.
func detectMoves(old, nw []Block, regions []region) (moves, edited map[int]movePair) {
	freeOld := map[int]bool{}
	freeNew := map[int]bool{}
	byHash := map[string][]int{}
	for _, r := range regions {
		for _, oi := range r.del {
			freeOld[oi] = true
			if len(Tokenize(old[oi].Text)) >= moveMinTokens {
				byHash[old[oi].Hash] = append(byHash[old[oi].Hash], oi)
			}
		}
		for _, ni := range r.ins {
			freeNew[ni] = true
		}
	}

	out := map[int]movePair{}
	edited = map[int]movePair{}
	pair := func(oi, ni int) {
		p := movePair{oldIdx: oi, newIdx: ni}
		out[oldKey(oi)] = p
		out[newKey(ni)] = p
		delete(freeOld, oi)
		delete(freeNew, ni)
	}

	// Seed: blocks big enough that identical content cannot be coincidence.
	var seeds []movePair
	for _, r := range regions {
		for _, ni := range r.ins {
			if len(Tokenize(nw[ni].Text)) < moveMinTokens {
				continue
			}
			for _, oi := range byHash[nw[ni].Hash] {
				if !freeOld[oi] || !freeNew[ni] {
					continue
				}
				pair(oi, ni)
				seeds = append(seeds, movePair{oi, ni})
				break
			}
		}
	}

	// Grow each seed outwards while the neighbouring blocks are also
	// unmatched and identical. This is what keeps a moved section's heading
	// and its short trailing blocks attached to the move, instead of
	// stranding them as a delete plus an insert either side of it.
	//
	// Growth also bridges a single edited block, but only when the block
	// *past* it matches exactly — "a section was moved and one paragraph in
	// it was touched" is common, while a lone similar block at the edge of a
	// move is just as likely to be coincidence.
	for _, s := range seeds {
		for step := -1; step <= 1; step += 2 {
			oi, ni := s.oldIdx+step, s.newIdx+step
			for freeOld[oi] && freeNew[ni] {
				if old[oi].Hash == nw[ni].Hash {
					pair(oi, ni)
					oi += step
					ni += step
					continue
				}
				if !bridgeable(old, nw, oi, ni, step, freeOld, freeNew, out) {
					break
				}
				pair(oi, ni)
				edited[oldKey(oi)] = movePair{oi, ni}
				edited[newKey(ni)] = movePair{oi, ni}
				oi += step
				ni += step
			}
		}
	}
	return out, edited
}

// bridgeable reports whether old[oi] and nw[ni] are an edited version of one
// another sitting inside a run of moved blocks. The anchor past the gap may
// be either still unclaimed or already paired to its counterpart by an
// earlier seed — both mean "the move continues on the far side".
func bridgeable(old, nw []Block, oi, ni, step int, freeOld, freeNew map[int]bool, moves map[int]movePair) bool {
	if old[oi].Kind != nw[ni].Kind {
		return false
	}
	no, nn := oi+step, ni+step
	if no < 0 || no >= len(old) || nn < 0 || nn >= len(nw) {
		return false
	}
	if old[no].Hash != nw[nn].Hash {
		return false
	}
	anchored := freeOld[no] && freeNew[nn]
	if p, ok := moves[oldKey(no)]; ok && p.newIdx == nn {
		anchored = true
	}
	if !anchored {
		return false
	}
	return blockSimilarity(old[oi], nw[ni]) >= thresholdFor(old[oi], nw[ni])
}

// Move bookkeeping keys old and new indices into one map without colliding.
func oldKey(i int) int { return i * 2 }
func newKey(i int) int { return i*2 + 1 }

func expandRegion(old, nw []Block, del, ins []int, moveOf, editedInMove map[int]movePair) []BlockChange {
	pairs := pairModified(old, nw, del, ins, moveOf)
	pairedOld := map[int]int{} // old index -> new index
	pairedNew := map[int]bool{}
	for _, p := range pairs {
		pairedOld[p.oldIdx] = p.newIdx
		pairedNew[p.newIdx] = true
	}

	var out []BlockChange
	for _, oi := range del {
		o := old[oi]
		if mp, ok := moveOf[oldKey(oi)]; ok {
			// A block that moved and was edited is announced here and
			// shown in full at its new position, where the reviewer
			// reads the section it now belongs to.
			n := nw[mp.newIdx]
			out = append(out, BlockChange{Kind: ChangeMoveOut, Old: &o, New: &n})
			continue
		}
		if ni, ok := pairedOld[oi]; ok {
			n := nw[ni]
			out = append(out, modifyChange(o, n))
			continue
		}
		out = append(out, BlockChange{Kind: ChangeDelete, Old: &o})
	}
	for _, ni := range ins {
		n := nw[ni]
		if mp, ok := editedInMove[newKey(ni)]; ok {
			c := modifyChange(old[mp.oldIdx], n)
			c.Moved = true
			out = append(out, c)
			continue
		}
		if mp, ok := moveOf[newKey(ni)]; ok {
			o := old[mp.oldIdx]
			out = append(out, BlockChange{Kind: ChangeMoveIn, Old: &o, New: &n})
			continue
		}
		if pairedNew[ni] {
			continue // already emitted as a modification
		}
		out = append(out, BlockChange{Kind: ChangeInsert, New: &n})
	}
	return out
}

func modifyChange(o, n Block) BlockChange {
	c := BlockChange{Kind: ChangeModify, Old: &o, New: &n}
	if o.Kind.Prose() {
		c.Words = DiffWords(o.Text, n.Text)
		c.StructureOnly = !hasChange(c.Words)
	} else {
		c.Lines = DiffLines(o.Lines, n.Lines)
		c.StructureOnly = !hasChange(c.Lines)
	}
	c.Similarity = blockSimilarity(o, n)
	return c
}

func hasChange(spans []Span) bool {
	for _, s := range spans {
		if s.Op != OpEqual {
			return true
		}
	}
	return false
}

// pairModified greedily matches the most similar delete/insert pairs left in
// one changed region, best first.
func pairModified(old, nw []Block, del, ins []int, moveOf map[int]movePair) []movePair {
	var cand []int
	for _, oi := range del {
		if _, moved := moveOf[oldKey(oi)]; !moved {
			cand = append(cand, oi)
		}
	}
	var cins []int
	for _, ni := range ins {
		if _, moved := moveOf[newKey(ni)]; !moved {
			cins = append(cins, ni)
		}
	}
	if len(cand) == 0 || len(cins) == 0 {
		return nil
	}
	windowed := len(cand)*len(cins) > pairBudget

	type scored struct {
		p movePair
		s float64
	}
	var all []scored
	for a, oi := range cand {
		for b, ni := range cins {
			if windowed && abs(a-b) > pairWindow {
				continue
			}
			o, n := old[oi], nw[ni]
			if o.Kind != n.Kind {
				continue
			}
			s := blockSimilarity(o, n)
			if s < thresholdFor(o, n) {
				continue
			}
			all = append(all, scored{movePair{oi, ni}, s})
		}
	}
	sort.SliceStable(all, func(i, j int) bool {
		if all[i].s != all[j].s {
			return all[i].s > all[j].s
		}
		return all[i].p.oldIdx < all[j].p.oldIdx
	})

	usedOld := map[int]bool{}
	usedNew := map[int]bool{}
	var out []movePair
	for _, c := range all {
		if usedOld[c.p.oldIdx] || usedNew[c.p.newIdx] {
			continue
		}
		usedOld[c.p.oldIdx] = true
		usedNew[c.p.newIdx] = true
		out = append(out, c.p)
	}
	return out
}

func thresholdFor(a, b Block) float64 {
	if len(Tokenize(a.Text)) < shortBlockTokens || len(Tokenize(b.Text)) < shortBlockTokens {
		return shortBlockThreshold
	}
	return modifyThreshold
}

// blockSimilarity is token similarity for prose and line similarity for code.
func blockSimilarity(a, b Block) float64 {
	in := newInterner()
	if a.Kind.Prose() {
		return ratio(in.all(TokenTexts(Tokenize(a.Text))), in.all(TokenTexts(Tokenize(b.Text))))
	}
	return ratio(in.all(a.Lines), in.all(b.Lines))
}

func abs(i int) int {
	if i < 0 {
		return -i
	}
	return i
}