package pijul

import (
	"errors"
	"fmt"
	"io"
	"path"
	"strings"
)

// topologicalSort returns a slice of b and its children, sorted
// topologically.
// It uses the algorithm from
// https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search,
// except that cycles are treated like the end of a branch of the
// graph instead of causing the search to abort.
func topologicalSort(b *Block) []*Block {
	var list []*Block
	visited := make(map[*Block]bool)

	var visit func(*Block)
	visit = func(n *Block) {
		if visited[n] {
			return
		}
		visited[n] = true
		for _, e := range n.Edges {
			visit(e.To)
		}
		list = append(list, n)
	}

	visit(b)

	// Reverse the list.
	for i, j := 0, len(list)-1; i < j; i, j = i+1, j-1 {
		list[i], list[j] = list[j], list[i]
	}

	return list
}

type Conflict struct {
	Start  int
	Center int
	End    int
}

func FindConflicts(inode *Block) ([]*Block, []Conflict) {
	blocks := topologicalSort(inode)
	index := make(map[*Block]int, len(blocks))
	for i, b := range blocks {
		index[b] = i
	}
	var conflicts []Conflict

	// prev is the most recent non-deleted block.
	var prev *Block

	// reachable is the set of blocks that are reachable from prev.
	reachable := map[*Block]bool{
		blocks[0]: true,
	}

	for i, b := range blocks {
		// We only check for conflicts when the current block is not one that
		// has been deleted.
		if len(b.DeletedBy) == 0 {
			if !reachable[b] {
				// If this block is not reachable from the previous block, the order between
				// them is undetermined, and therefore we have a conflict.

				// To find the start of the conflict, we need to look back for the most recent
				// block from which b is reachable.
				var start int
				connected := map[*Block]bool{
					b: true,
				}
				for j := i; j >= 0; j-- {
					if j < i && len(blocks[j].DeletedBy) == 0 && connected[blocks[j]] {
						start = j + 1
						break
					}
					if connected[blocks[j]] {
						for _, e := range blocks[j].ReverseEdges {
							connected[e.From] = true
						}
					}
				}

				// Skip deleted blocks at the start of the conflict.
				for len(blocks[start].DeletedBy) > 0 {
					start++
				}

				// Rather than making a new map of blocks reachable from prev,
				// we can reuse our work from the outer loop.
				// The reachable map will be replaced at the end of the outer loop anyway.

				end := len(blocks)
				for j := i + 1; j < len(blocks); j++ {
					if len(blocks[j].DeletedBy) == 0 && reachable[blocks[j]] {
						end = j
						break
					}
					if reachable[blocks[j]] {
						for _, e := range blocks[j].Edges {
							reachable[e.To] = true
						}
					}
				}

				// skip deleted blocks at the end of the conflict.
				for len(blocks[end-1].DeletedBy) > 0 {
					end--
				}

				conflicts = append(conflicts, Conflict{
					Start:  start,
					Center: i,
					End:    end,
				})
			}

			prev = b
			reachable = map[*Block]bool{
				prev: true,
			}
		}

		if reachable[b] {
			for _, e := range b.Edges {
				reachable[e.To] = true
			}
		}
	}

	return blocks, conflicts
}

func OutputFile(dest io.Writer, inode *Block) error {
	blocks, conflicts := FindConflicts(inode)

	// These maps tell us how many conflicts begin (etc.) directly before the
	// specified index of blocks.
	conflictStart := make(map[int]int)
	conflictCenter := make(map[int]int)
	conflictEnd := make(map[int]int)

	for _, c := range conflicts {
		conflictStart[c.Start]++
		conflictCenter[c.Center]++
		conflictEnd[c.End]++
	}

	for i, b := range blocks {
		for j := 0; j < conflictEnd[i]; j++ {
			fmt.Fprintf(dest, ">>>>>>>\n")
		}
		for j := 0; j < conflictCenter[i]; j++ {
			fmt.Fprintf(dest, "======= %v\n", b.Change)
		}
		for j := 0; j < conflictStart[i]; j++ {
			fmt.Fprintf(dest, "<<<<<<< %v\n", b.Change)
		}

		if len(b.DeletedBy) > 0 {
			continue
		}

		_, err := dest.Write(b.Content)
		if err != nil {
			return err
		}
	}

	for j := 0; j < conflictEnd[len(blocks)]; j++ {
		fmt.Fprintf(dest, ">>>>>>>\n")
	}

	return nil
}

type DirEntry struct {
	IsDirectory bool
	Name        string
	Encoding    string
	Inode       *Block
}

func dirEntry(data []byte) ([]byte, DirEntry, error) {
	if len(data) < 3 {
		return data, DirEntry{}, fmt.Errorf("too short to be a valid directory entry: %d bytes", len(data))
	}

	var d DirEntry

	_, _, err := tuple(
		assign(&d.Name, toString(lengthData(uint64LE))),
		assign(&d.Encoding, mapValue(option(toString(lengthData(uint64LE))), func(p *string) string {
			if p == nil {
				return ""
			}
			return *p
		})),
	)(data[2:])
	if err != nil {
		d.Name = string(data[2:])
		d.IsDirectory = data[0]&2 != 0
	} else {
		// Yes, it really is different endianness depending on which directory entry format
		// it is.
		d.IsDirectory = data[1]&2 != 0
	}
	return nil, d, nil
}

func ReadDir(dirInode *Block) ([]DirEntry, error) {
	var entries []DirEntry
	for _, e := range dirInode.Edges {
		if len(e.To.DeletedBy) > 0 {
			continue
		}
		if e.Flag&EdgeFlagsFolder == 0 {
			return nil, errors.New("ReadDir: found an edge that doesn't have Folder flag set")
		}
		b := e.To
		_, entry, err := dirEntry(b.Content)
		if err != nil {
			continue
		}
		for _, inodeEdge := range b.Edges {
			if len(inodeEdge.To.DeletedBy) > 0 {
				continue
			}
			if inodeEdge.Flag&EdgeFlagsFolder == 0 {
				return nil, fmt.Errorf("directory entry for %s has an edge without Folder flag", entry.Name)
			}
			entry.Inode = inodeEdge.To
			break
		}
		if entry.Inode == nil && len(b.Edges) > 0 {
			// All the potential inodes are deleted.
			// But there has to be one.
			// So we'll just pick the first one.
			entry.Inode = b.Edges[0].To
		}
		if entry.Inode == nil {
			return nil, fmt.Errorf("directory entry for %s has no inode", entry.Name)
		}
		entries = append(entries, entry)
	}
	return entries, nil
}

func FollowPath(g *Graph, p string) (DirEntry, error) {
	p = path.Clean(p)
	names := strings.Split(p, "/")
	dir, err := g.RootDirectory()
	if err != nil {
		return DirEntry{}, err
	}

	for level, name := range names {
		entries, err := ReadDir(dir)
		if err != nil {
			return DirEntry{}, err
		}
		var entry DirEntry
		for _, e := range entries {
			if e.Name == name {
				entry = e
				break
			}
		}
		if entry == (DirEntry{}) {
			return DirEntry{}, fmt.Errorf("not found: %s", path.Join(names[:level+1]...))
		}
		if level == len(names)-1 {
			return entry, nil
		}
		if !entry.IsDirectory {
			return DirEntry{}, fmt.Errorf("not a directory: %s", path.Join(names[:level+1]...))
		}
		dir = entry.Inode
	}
	panic("unreachable")
}