package datastore

import (
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"sort"
	"strings"

	"github.com/mem9-ai/drive9/pkg/pathutil"
)

func sortOverlayCommitCreates(creates []FSLayerEntry) {
	if len(creates) < 2 {
		return
	}
	renameDestBySource := make(map[string]string)
	renameDestSet := make(map[string]struct{})
	for i := range creates {
		if creates[i].Op == FSLayerEntryOpRename && creates[i].Path != "" && creates[i].ContentText != "" {
			renameDestBySource[creates[i].Path] = creates[i].ContentText
			renameDestSet[creates[i].ContentText] = struct{}{}
		}
	}
	topo := overlayRenameTopoOrder(creates)
	sort.SliceStable(creates, func(i, j int) bool {
		si, sj := overlayDraftCreateSortPath(creates[i], renameDestBySource, renameDestSet), overlayDraftCreateSortPath(creates[j], renameDestBySource, renameDestSet)
		di, dj := pathDepth(si), pathDepth(sj)
		if di != dj {
			return di < dj
		}
		if creates[i].Op == FSLayerEntryOpRename && creates[j].Op == FSLayerEntryOpRename {
			ti, tj := topo[creates[i].Path], topo[creates[j].Path]
			if ti != tj {
				return ti < tj
			}
		}
		if si != sj {
			return si < sj
		}
		ri, rj := overlayDraftCreateRank(creates[i], renameDestBySource), overlayDraftCreateRank(creates[j], renameDestBySource)
		if ri != rj {
			return ri < rj
		}
		return creates[i].Path < creates[j].Path
	})
}

func sortOverlayCommitDeletes(deletes []FSLayerEntry) {
	sort.Slice(deletes, func(i, j int) bool {
		di, dj := pathDepth(deletes[i].Path), pathDepth(deletes[j].Path)
		if di != dj {
			return di > dj
		}
		return deletes[i].Path > deletes[j].Path
	})
}

// OverlayBreakRenameCycles turns crossing dest drafts (a→b + b→a) into a
// linear apply set with a hidden temp hop so preflight and RenameNoReplace
// can run without "target exists".
func OverlayBreakRenameCycles(entries []FSLayerEntry) []FSLayerEntry {
	srcToDest := make(map[string]string)
	var renameIdx []int
	for i := range entries {
		if entries[i].Op == FSLayerEntryOpRename && entries[i].Path != "" && entries[i].ContentText != "" {
			srcToDest[entries[i].Path] = entries[i].ContentText
			renameIdx = append(renameIdx, i)
		}
	}
	if len(renameIdx) < 2 {
		return entries
	}
	type mark int
	const (
		markNone mark = iota
		markWalk
		markDone
	)
	seen := make(map[string]mark, len(srcToDest))
	var cycles [][]string
	var walk func(src string, stack []string)
	walk = func(src string, stack []string) {
		switch seen[src] {
		case markDone:
			return
		case markWalk:
			for i, p := range stack {
				if p == src {
					cycles = append(cycles, append([]string(nil), stack[i:]...))
					return
				}
			}
			return
		}
		dest, ok := srcToDest[src]
		if !ok {
			seen[src] = markDone
			return
		}
		seen[src] = markWalk
		walk(dest, append(stack, src))
		seen[src] = markDone
	}
	srcs := make([]string, 0, len(srcToDest))
	for src := range srcToDest {
		srcs = append(srcs, src)
	}
	sort.Strings(srcs)
	for _, src := range srcs {
		if seen[src] == markNone {
			walk(src, nil)
		}
	}
	if len(cycles) == 0 {
		return overlayOrderCommitDrafts(entries)
	}
	used := make(map[string]struct{}, len(entries)+len(cycles))
	for i := range entries {
		used[entries[i].Path] = struct{}{}
		if entries[i].ContentText != "" {
			used[entries[i].ContentText] = struct{}{}
		}
	}
	rewrites := make(map[string]string, len(cycles))
	var extra []FSLayerEntry
	for _, cyc := range cycles {
		if len(cyc) < 2 {
			continue
		}
		breakAt := 0
		for i := 1; i < len(cyc); i++ {
			if cyc[i] < cyc[breakAt] {
				breakAt = i
			}
		}
		src := cyc[breakAt]
		if _, ok := rewrites[src]; ok {
			continue
		}
		dest := srcToDest[src]
		tmp := overlaySwapTempPath(src, dest, used)
		used[tmp] = struct{}{}
		rewrites[src] = tmp
		var proto FSLayerEntry
		for _, i := range renameIdx {
			if entries[i].Path == src {
				proto = entries[i]
				break
			}
		}
		hop := proto
		hop.Path = tmp
		hop.ContentText = dest
		hop.BaseInodeID = ""
		hop.BaseRevision = 0
		extra = append(extra, hop)
	}
	out := make([]FSLayerEntry, 0, len(entries)+len(extra))
	for i := range entries {
		e := entries[i]
		if e.Op == FSLayerEntryOpRename {
			if tmp, ok := rewrites[e.Path]; ok {
				e.ContentText = tmp
			}
		}
		out = append(out, e)
	}
	out = append(out, extra...)
	return overlayOrderCommitDrafts(out)
}

func overlaySwapTempPath(src, dest string, used map[string]struct{}) string {
	parent := pathutil.ParentPath(src)
	if parent == "" {
		parent = "/"
	}
	if !strings.HasSuffix(parent, "/") {
		parent += "/"
	}
	dir := strings.HasSuffix(src, "/") || strings.HasSuffix(dest, "/")
	sum := sha256.Sum256([]byte(src + "\x00" + dest))
	for n := 8; n <= len(sum); n += 4 {
		p := parent + ".fs-layer-swap-" + hex.EncodeToString(sum[:n])
		if dir {
			p += "/"
		}
		if _, ok := used[p]; !ok {
			return p
		}
	}
	for i := 0; ; i++ {
		p := parent + fmt.Sprintf(".fs-layer-swap-%s-%d", hex.EncodeToString(sum[:8]), i)
		if dir {
			p += "/"
		}
		if _, ok := used[p]; !ok {
			return p
		}
	}
}

func overlayOrderCommitDrafts(entries []FSLayerEntry) []FSLayerEntry {
	var creates, deletes []FSLayerEntry
	for i := range entries {
		if entries[i].Op == FSLayerEntryOpWhiteout {
			deletes = append(deletes, entries[i])
			continue
		}
		creates = append(creates, entries[i])
	}
	sortOverlayCommitCreates(creates)
	sortOverlayCommitDeletes(deletes)
	return append(creates, deletes...)
}

func overlaySwapTempPathName(p string) bool {
	base := pathutil.BaseName(p)
	return strings.HasPrefix(base, ".fs-layer-swap-")
}

func overlayRenameTopoOrder(creates []FSLayerEntry) map[string]int {
	var renames []FSLayerEntry
	for i := range creates {
		if creates[i].Op == FSLayerEntryOpRename && creates[i].Path != "" {
			renames = append(renames, creates[i])
		}
	}
	order := make(map[string]int, len(renames))
	if len(renames) == 0 {
		return order
	}
	vacates := make(map[string][]int, len(renames))
	createsDest := make(map[string][]int, len(renames))
	for i := range renames {
		vacates[renames[i].Path] = append(vacates[renames[i].Path], i)
		createsDest[renames[i].ContentText] = append(createsDest[renames[i].ContentText], i)
	}
	deps := make([]int, len(renames))
	dependents := make([][]int, len(renames))
	addDep := func(child, parent int) {
		if child == parent {
			return
		}
		deps[child]++
		dependents[parent] = append(dependents[parent], child)
	}
	for i := range renames {
		src, dest := renames[i].Path, renames[i].ContentText
		if overlaySwapTempPathName(src) {
			for _, j := range createsDest[src] {
				addDep(i, j)
			}
		}
		if overlaySwapTempPathName(dest) {
			continue
		}
		for _, j := range vacates[dest] {
			addDep(i, j)
		}
	}
	var ready []int
	for i := range renames {
		if deps[i] == 0 {
			ready = append(ready, i)
		}
	}
	sort.Slice(ready, func(a, b int) bool {
		return renames[ready[a]].Path < renames[ready[b]].Path
	})
	next := 0
	for len(ready) > 0 {
		i := ready[0]
		ready = ready[1:]
		order[renames[i].Path] = next
		next++
		var unlocked []int
		for _, j := range dependents[i] {
			deps[j]--
			if deps[j] == 0 {
				unlocked = append(unlocked, j)
			}
		}
		sort.Slice(unlocked, func(a, b int) bool {
			return renames[unlocked[a]].Path < renames[unlocked[b]].Path
		})
		ready = append(ready, unlocked...)
	}
	for i := range renames {
		if _, ok := order[renames[i].Path]; !ok {
			order[renames[i].Path] = next
			next++
		}
	}
	return order
}

func overlayDraftCreateSortPath(e FSLayerEntry, renameDestBySource map[string]string, renameDestSet map[string]struct{}) string {
	if e.Op == FSLayerEntryOpRename {
		return e.ContentText
	}
	if e.Op == FSLayerEntryOpChmod {
		if _, ok := renameDestSet[e.Path]; ok {
			// Dest chmod after rename: stay with dest, even if this path
			// is also a swap source (mv a tmp; mv b a; mv tmp b).
			return e.Path
		}
	}
	// Recreate of a rename source (mv a b; echo > a) must sort with the dest
	// so dest-parent mkdir stays first and the rename still precedes the upsert.
	if dest := renameDestBySource[e.Path]; dest != "" {
		return dest
	}
	return e.Path
}

func overlayDraftCreateRank(e FSLayerEntry, renameDestBySource map[string]string) int {
	// Recreate of a rename source (mv dir new; mkdir dir) must follow the
	// rename even if the recreate is a mkdir (default rank 0).
	if e.Op != FSLayerEntryOpRename && renameDestBySource[e.Path] != "" {
		return 4
	}
	switch e.Op {
	case FSLayerEntryOpMkdir:
		return 0
	case FSLayerEntryOpRename:
		return 1
	case FSLayerEntryOpChmod:
		return 3
	default:
		return 2
	}
}

func pathDepth(p string) int {
	n := 0
	for _, c := range p {
		if c == '/' {
			n++
		}
	}
	return n
}