package pijul

import (
	"errors"
	"fmt"
	"sort"
)

// A Block is a vertex in the graph representing the repository,
// with its associated content.
type Block struct {
	Change       Hash
	Start        ChangePosition
	End          ChangePosition
	Content      []byte
	Edges        []*Edge
	ReverseEdges []*Edge
	DeletedBy    []Hash
}

// An Edge is a link between two blocks.
type Edge struct {
	Change Hash
	Flag   EdgeFlags
	From   *Block
	To     *Block
}

// A graph represents the current content of the repository.
type Graph struct {
	Root *Block

	// For each change that has been applied to the graph, the index has a
	// slice of the blocks added by that change, sorted by starting position.
	Index map[Hash][]*Block
}

func NewGraph() *Graph {
	g := &Graph{}
	g.Root = &Block{}
	g.Index = map[Hash][]*Block{
		Hash{}: []*Block{g.Root},
	}
	return g
}

// blockStarting returns the block starting at the specified location,
// or nil if it is not found.
func (g *Graph) blockStarting(change Hash, pos ChangePosition) *Block {
	blocks := g.Index[change]
	if len(blocks) == 0 {
		return nil
	}

	i := sort.Search(len(blocks), func(i int) bool {
		return blocks[i].Start == pos || blocks[i].End > pos
	})
	if i == len(blocks) {
		return nil
	}
	if blocks[i].Start == pos {
		return blocks[i]
	}
	if blocks[i].Start > pos {
		return nil
	}
	return g.splitBlock(blocks[i], pos)
}

// blockEnding returns the block ending at the specified location, or nil if
// it is not found.
func (g *Graph) blockEnding(change Hash, pos ChangePosition) *Block {
	if change == (Hash{}) {
		return g.Root
	}
	blocks := g.Index[change]
	if len(blocks) == 0 {
		return nil
	}

	i := sort.Search(len(blocks), func(i int) bool {
		return blocks[i].End >= pos
	})
	if i == len(blocks) {
		return nil
	}
	if blocks[i].End == pos {
		return blocks[i]
	}
	if blocks[i].Start >= pos {
		return nil
	}

	g.splitBlock(blocks[i], pos)

	return blocks[i]
}

func (g *Graph) splitBlock(oldBlock *Block, pos ChangePosition) (newBlock *Block) {
	change := oldBlock.Change
	newBlock = &Block{
		Change:  change,
		Start:   pos,
		End:     oldBlock.End,
		Content: oldBlock.Content[pos-oldBlock.Start:],
		Edges:   oldBlock.Edges,
	}
	for _, e := range newBlock.Edges {
		e.From = newBlock
	}
	oldBlock.End = pos
	oldBlock.Content = oldBlock.Content[:pos-oldBlock.Start]
	oldBlock.Edges = nil

	if len(oldBlock.DeletedBy) > 0 {
		newBlock.DeletedBy = make([]Hash, len(oldBlock.DeletedBy))
		copy(newBlock.DeletedBy, oldBlock.DeletedBy)
	}

	makeEdge(change, 0, oldBlock, newBlock)

	blocks := append(g.Index[change], newBlock)
	sort.Sort(blockList(blocks))
	g.Index[change] = blocks

	return newBlock
}

type blockList []*Block

func (b blockList) Len() int           { return len(b) }
func (b blockList) Less(i, j int) bool { return b[i].Start < b[j].Start }
func (b blockList) Swap(i, j int)      { b[i], b[j] = b[j], b[i] }

func (g *Graph) ApplyChange(h Hash, c Change) error {
	if _, ok := g.Index[h]; ok {
		return fmt.Errorf("already applied change %v", h)
	}
	for _, dep := range c.Dependencies {
		if _, ok := g.Index[dep]; !ok {
			return fmt.Errorf("missing dependency: %v", dep)
		}
	}

	var blocks []*Block
	g.Index[h] = blocks

	for _, hunk := range c.Changes {
		for _, atom := range hunk.atoms() {
			switch a := atom.(type) {
			case NewVertex:
				b := &Block{
					Change:  h,
					Start:   a.Start,
					End:     a.End,
					Content: c.Contents[a.Start:a.End],
				}
				for _, pos := range a.UpContext {
					parent := g.blockEnding(coalesceHash(pos.Change, h), pos.Pos)
					if parent == nil {
						return fmt.Errorf("not found: block ending at %v:%d", coalesceHash(pos.Change, h), pos.Pos)
					}
					makeEdge(h, a.Flag, parent, b)
				}
				for _, pos := range a.DownContext {
					child := g.blockStarting(coalesceHash(pos.Change, h), pos.Pos)
					if child == nil {
						return fmt.Errorf("not found: block starting at %v:%d", coalesceHash(pos.Change, h), pos.Pos)
					}
					makeEdge(h, a.Flag, b, child)
				}
				blocks = append(blocks, b)
				if len(blocks) >= 2 && blocks[len(blocks)-2].Start > blocks[len(blocks)-1].Start {
					sort.Sort(blockList(blocks))
				}
				g.Index[h] = blocks

			case EdgeMap:
				for _, e := range a.Edges {
					err := g.putNewEdge(h, e)
					if err != nil {
						return err
					}
				}
			}
		}
	}

	return nil
}

func (g *Graph) putNewEdge(change Hash, ne NewEdge) error {
	target := g.blockStarting(coalesceHash(ne.To.Change, change), ne.To.Start)
	if target == nil {
		return fmt.Errorf("not found: block starting at %v:%d", coalesceHash(ne.To.Change, change), ne.To.Start)
	}

	introducedBy := coalesceHash(ne.IntroducedBy, change)

	for {
		if target.End > ne.To.End {
			g.splitBlock(target, ne.To.End)
		}

		if ne.Flag&EdgeFlagsDeleted != 0 {
			// This is a deletion, so we'll add this change to the DeletedBy list if it
			// isn't there already.
			found := false
			for _, h := range target.DeletedBy {
				if h == change {
					found = true
					break
				}
			}
			if !found {
				target.DeletedBy = append(target.DeletedBy, change)
			}
		} else {
			// This is an undeletion, so we'll remove the change that did the deletion
			// from the DeletedBy list.
			for i, h := range target.DeletedBy {
				if h == introducedBy {
					target.DeletedBy = append(target.DeletedBy[:i], target.DeletedBy[i+1:]...)
					break
				}
			}
		}

		if target.End == ne.To.End {
			break
		}

		newTarget := g.blockStarting(target.Change, target.End)
		if newTarget == nil {
			return fmt.Errorf("not found: block to follow %v:%d:%d", target.Change, target.Start, target.End)
		}
		target = newTarget
	}

	return nil
}

func coalesceHash(o OptionalHash, h Hash) Hash {
	if o.Valid {
		return o.Hash
	}
	return h
}

func makeEdge(change Hash, flag EdgeFlags, from *Block, to *Block) {
	e := &Edge{
		Change: change,
		Flag:   flag,
		From:   from,
		To:     to,
	}
	from.Edges = append(from.Edges, e)
	to.ReverseEdges = append(to.ReverseEdges, e)
}

// RootDirectory returns the "inode" block corresponding to the root directory
// of the repository.
func (g *Graph) RootDirectory() (*Block, error) {
	// There are two possible configurations for the directory structure:
	// The old setup had directory entries as direct children of the root.
	// The new setup has a special root inode, which is a child of an intermediate
	// vertex, which is a child of the root.
	//
	// So we need to try both possibilities.
	var possibleRoots []*Block
	var directFiles []*Block
	for _, e := range g.Root.Edges {
		if len(e.To.DeletedBy) > 0 {
			continue
		}
		if e.Flag&EdgeFlagsFolder == 0 {
			return nil, errors.New("non-folder edge found while looking for root directory")
		}
		b := e.To
		if len(b.Content) > 0 {
			directFiles = append(directFiles, b)
			continue
		}
		for _, f := range b.Edges {
			if len(f.To.DeletedBy) > 0 {
				continue
			}
			if f.Flag&EdgeFlagsFolder == 0 {
				return nil, errors.New("non-folder edge found while looking for root directory")
			}
			if len(f.To.Content) > 0 {
				continue
			}
			possibleRoots = append(possibleRoots, f.To)
		}
	}

	if len(directFiles) > 0 || len(possibleRoots) == 0 {
		return g.Root, nil
	}
	if len(possibleRoots) > 1 {
		return nil, fmt.Errorf("found %d possible root directories", len(possibleRoots))
	}
	return possibleRoots[0], nil
}