// Copyright © 2016 Asteris, LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package load

import (
	"fmt"
	"io/ioutil"
	"sort"
	"sync"
	"text/template"

	"github.com/Sirupsen/logrus"
	"github.com/asteris-llc/converge/graph"
	"github.com/asteris-llc/converge/graph/node"
	"github.com/asteris-llc/converge/helpers/logging"
	"github.com/asteris-llc/converge/parse"
	"github.com/asteris-llc/converge/render/extensions"
	"github.com/asteris-llc/converge/render/preprocessor"
	"github.com/pkg/errors"
	"golang.org/x/net/context"
)

type dependencyGenerator func(g *graph.Graph, id string, node *parse.Node) ([]string, error)

// ResolveDependencies examines the strings and depdendencies at each vertex of
// the graph and creates edges to fit them
func ResolveDependencies(ctx context.Context, g *graph.Graph) (*graph.Graph, error) {
	logger := logging.GetLogger(ctx).WithField("function", "ResolveDependencies")
	logger.Debug("resolving dependencies")

	groupLock := new(sync.Mutex)
	groupMap := make(map[string]struct{})
	g, err := g.Transform(ctx, func(meta *node.Node, out *graph.Graph) error {
		if graph.IsRoot(meta.ID) { // skip root
			return nil
		}

		node, ok := meta.Value().(*parse.Node)
		if !ok {
			return fmt.Errorf("ResolveDependencies can only be used on Graphs of *parse.Node. I got %T", meta.Value())
		}

		depGenerators := []dependencyGenerator{getDepends, getParams, getXrefs}

		// we have dependencies from various sources, but they're always IDs, so we
		// can connect them pretty easily
		for _, source := range depGenerators {
			deps, err := source(g, meta.ID, node)
			if err != nil {
				return err
			}
			for _, dep := range deps {
				if err := out.SafeConnect(meta.ID, dep); err != nil {
					logger.Error(err)
					return err
				}
			}
		}

		// collect group information
		if meta.Group != "" {
			groupLock.Lock()
			groupMap[meta.Group] = struct{}{}
			groupLock.Unlock()
		}

		return nil
	})

	for group := range groupMap {
		if depG, grpErr := groupDeps(ctx, g, group); grpErr != nil {
			return depG, grpErr
		}
	}
	return g, err
}

func getDepends(g *graph.Graph, id string, node *parse.Node) ([]string, error) {
	deps, err := node.GetStringSlice("depends")
	switch err {
	case parse.ErrNotFound:
		return []string{}, nil
	case nil:
		for idx, dep := range deps {
			if ancestor, ok := getNearestAncestor(g, id, dep); ok {
				deps[idx] = ancestor
			} else {
				return nil, fmt.Errorf("nonexistent vertices in edges: %s", dep)
			}
		}
		return deps, nil
	default:
		return nil, err
	}
}

func getParams(g *graph.Graph, id string, node *parse.Node) (out []string, err error) {
	var nodeStrings []string
	nodeStrings, err = node.GetStrings()
	if err != nil {
		return nil, err
	}

	meta, found := g.Get(id)
	if !found {
		return nil, errors.New("error: node is not in the provided graph")
	}

	if metaIface, ok := meta.LookupMetadata("conditional-predicate-raw"); ok {
		if str, ok := metaIface.(string); ok {
			nodeStrings = append(nodeStrings, str)
		}
	}

	type stub struct{}
	language := extensions.MinimalLanguage()
	language.On("param", extensions.RememberCalls(&out, ""))
	language.On("paramList", extensions.RememberCalls(&out, []interface{}(nil)))
	language.On("paramMap", extensions.RememberCalls(&out, map[string]interface{}(nil)))

	for _, s := range nodeStrings {
		useless := stub{}
		tmpl, tmplErr := template.New("DependencyTemplate").Funcs(language.Funcs).Parse(s)
		if tmplErr != nil {
			return out, tmplErr
		}
		tmpl.Execute(ioutil.Discard, &useless)
	}
	for idx, val := range out {
		ancestor, found := getNearestAncestor(g, id, "param."+val)
		if !found {
			return out, fmt.Errorf("unknown parameter: param.%s", val)
		}
		out[idx] = ancestor
	}
	return out, err
}

func getXrefs(g *graph.Graph, id string, node *parse.Node) (out []string, err error) {
	var nodeStrings []string
	var calls []string
	nodeRefs := make(map[string]struct{})
	nodeStrings, err = node.GetStrings()
	if err != nil {
		return nil, err
	}

	meta, found := g.Get(id)
	if !found {
		return nil, errors.New("error: node is not in the provided graph")
	}

	if metaIface, ok := meta.LookupMetadata("conditional-predicate-raw"); ok {
		if str, ok := metaIface.(string); ok {
			nodeStrings = append(nodeStrings, str)
		}
	}

	language := extensions.MinimalLanguage()
	language.On(extensions.RefFuncName, extensions.RememberCalls(&calls, 0))
	for _, s := range nodeStrings {
		tmpl, tmplErr := template.New("DependencyTemplate").Funcs(language.Funcs).Parse(s)
		if tmplErr != nil {
			return out, tmplErr
		}
		tmpl.Execute(ioutil.Discard, &struct{}{})
	}
	for _, call := range calls {
		vertex, _, found := preprocessor.VertexSplitTraverse(g, call, id, preprocessor.TraverseUntilModule, make(map[string]struct{}))
		if !found {
			return []string{}, fmt.Errorf("dependency generator: unresolvable call to %s", call)
		}
		if _, ok := nodeRefs[vertex]; !ok {
			nodeRefs[vertex] = struct{}{}
			out = append(out, vertex)
			if peerVertex, ok := getPeerVertex(g, id, vertex); ok {
				out = append(out, peerVertex)
			}
		}
	}
	return out, err
}

func getPeerVertex(g *graph.Graph, src, dst string) (string, bool) {
	if dst == "." || graph.IsRoot(dst) {
		return "", false
	}
	if g.AreSiblings(src, dst) {
		return dst, true
	}
	return getPeerVertex(g, src, graph.ParentID(dst))
}

func getNearestAncestor(g *graph.Graph, id, node string) (string, bool) {
	if graph.IsRoot(id) || id == "" || id == "." {
		return "", false
	}

	siblingID := graph.SiblingID(id, node)

	valMeta, ok := g.Get(siblingID)
	if !ok {
		return getNearestAncestor(g, graph.ParentID(id), node)
	}
	_, ok = valMeta.Value().(*parse.Node)
	if !ok {
		return "", false
	}
	return siblingID, true
}

func withoutRoot(in []string) (out []string) {
	for _, id := range in {
		if !graph.IsRoot(id) {
			out = append(out, id)
		}
	}
	return out
}

func withoutModule(g *graph.Graph, in []string) (out []string) {
	for _, id := range in {
		if meta, ok := g.Get(id); ok {
			if node, ok := meta.Value().(*parse.Node); ok {
				if !node.IsModule() {
					out = append(out, id)
				}
			}
		}
	}
	return out
}

func withoutSelf(self string, in []string) (out []string) {
	for _, id := range in {
		if id != self {
			out = append(out, id)
		}
	}
	return out
}

func highestGroupEdge(g *graph.Graph, id, group string) string {
	edges := g.UpEdgesInGroup(id, group)
	for _, edge := range edges {
		if !graph.IsRoot(edge) && edge != id {
			return highestGroupEdge(g, edge, group)
		}
	}
	return id
}

func moduleEdge(g *graph.Graph, id string) string {
	edges := graph.Sources(g.UpEdges(id))
	for _, edge := range edges {
		if graph.IsRoot(edge) {
			return edge
		}

		if meta, ok := g.Get(edge); ok {
			if node, ok := meta.Value().(*parse.Node); ok {
				if node.IsModule() {
					return meta.ID
				}
				return moduleEdge(g, meta.ID)
			}
		}
	}
	return id
}

type byDependencyCount struct {
	g     *graph.Graph
	nodes []*node.Node
}

func (b byDependencyCount) Len() int      { return len(b.nodes) }
func (b byDependencyCount) Swap(i, j int) { b.nodes[i], b.nodes[j] = b.nodes[j], b.nodes[i] }
func (b byDependencyCount) Less(i, j int) bool {
	return len(b.g.Dependencies(b.nodes[i].ID)) > len(b.g.Dependencies(b.nodes[j].ID))
}

func groupDeps(ctx context.Context, g *graph.Graph, group string) (*graph.Graph, error) {
	logger := logging.GetLogger(ctx).WithField("function", "groupDeps").WithField("group", group)

	nodes := g.GroupNodes(group)
	sort.Sort(byDependencyCount{g, nodes})

	for _, meta := range nodes {
		l := logger.WithField("id", meta.ID)
		// align all up edges in a single branch
		alignG, err := alignEdgesInGroup(ctx, g, meta.ID, group)
		if err != nil {
			l.Error(err)
			return alignG, errors.Wrap(err, "failed to align edges in branch")
		}
	}

	g, err := connectIsolatedGroupNodes(ctx, g, nodes, group)
	if err != nil {
		logger.Error(err)
		return g, errors.Wrap(err, "failed to connect group nodes")
	}

	g, err = connectIsolatedGroupBranches(ctx, g, nodes, group)
	if err != nil {
		logger.Error(err)
		return g, errors.Wrap(err, "failed to connect group branches")
	}

	return g, nil
}

func alignEdgesInGroup(ctx context.Context, g *graph.Graph, id, group string) (*graph.Graph, error) {
	upEdges := withoutRoot(g.UpEdgesInGroup(id, group))
	for i, upEdge := range upEdges {
		if i > 0 {
			dest := highestGroupEdge(g, upEdges[i-1], group)
			if err := g.SafeDisconnect(upEdge, id); err != nil {
				return g, err
			}

			if !willCycle(g, upEdge, dest) {
				if err := g.SafeConnect(upEdge, dest); err != nil {
					return g, err
				}
			}
		}

		// if the node has more than one down edge we want to keep the one with
		// the most dependencies
		downEdges := g.DownEdgesInGroup(upEdge, group)
		if len(downEdges) > 1 {
			var downNodes []*node.Node
			for _, downEdge := range downEdges {
				if meta, ok := g.Get(downEdge); ok {
					downNodes = append(downNodes, meta)
				}
			}
			sort.Sort(byDependencyCount{g, downNodes})
			for i := 1; i < len(downNodes); i++ {
				if err := g.SafeDisconnect(upEdge, downNodes[i].ID); err != nil {
					return g, err
				}
			}
		}
	}
	return g, nil
}

func connectIsolatedGroupNodes(ctx context.Context, g *graph.Graph, nodes []*node.Node, group string) (*graph.Graph, error) {
	// collect remaining group nodes that have no edges
	var unconnected []*node.Node
	for _, meta := range nodes {
		downEdges := withoutSelf(meta.ID, g.DownEdgesInGroup(meta.ID, group))
		upEdges := withoutModule(g, withoutRoot(g.UpEdgesInGroup(meta.ID, group)))
		if len(downEdges) == 0 && len(upEdges) == 0 {
			unconnected = append(unconnected, meta)
		}
	}

	groupDep := func(id string) string {
		pid := graph.ParentID(id)
		if !graph.IsRoot(pid) {
			id = pid
		}
		return id
	}

	// connect unconnected in single branch
	for i, meta := range unconnected {
		if i > 0 {
			from := meta.ID
			to := unconnected[i-1].ID
			if !g.AreSiblings(from, to) {
				from = groupDep(from)
				to = groupDep(to)
			}
			logging.GetLogger(ctx).WithFields(logrus.Fields{
				"from": from,
				"to":   to,
			}).Debug("connecting isolated group nodes")
			if err := g.SafeConnect(from, to); err != nil {
				return g, err
			}
		}
	}
	return g, nil
}

func connectIsolatedGroupBranches(ctx context.Context, g *graph.Graph, nodes []*node.Node, group string) (*graph.Graph, error) {
	// collect all unconnected group branches
	var groupBranches []*node.Node
	for _, meta := range nodes {
		downEdges := g.DownEdgesInGroup(meta.ID, group)
		if len(downEdges) == 0 {
			groupBranches = append(groupBranches, meta)
		}
	}

	// connect branches into a single branch (if in the same module)
	for i, treeRoot := range groupBranches {
		if i > 0 {
			from := treeRoot.ID
			dest := highestGroupEdge(g, groupBranches[i-1].ID, group)

			if moduleEdge(g, from) == moduleEdge(g, dest) {
				if !willCycle(g, from, dest) {
					if err := g.SafeConnect(from, dest); err != nil {
						return g, err
					}
				}
			}
		}
	}
	return g, nil
}

func willCycle(g *graph.Graph, from, to string) bool {
	var willCycle bool
	for _, dep := range g.Dependencies(to) {
		if dep == from {
			willCycle = true
			break
		}
	}
	return willCycle
}
