// Package generate provides functionality for generating stacks from stack files.
package generate

import (
	"context"
	"io/fs"
	"os"
	"path/filepath"
	"strings"

	"github.com/gruntwork-io/terragrunt/config"
	"github.com/gruntwork-io/terragrunt/internal/component"
	"github.com/gruntwork-io/terragrunt/internal/discovery"
	"github.com/gruntwork-io/terragrunt/internal/errors"
	"github.com/gruntwork-io/terragrunt/internal/experiment"
	"github.com/gruntwork-io/terragrunt/internal/worker"
	"github.com/gruntwork-io/terragrunt/options"
	"github.com/gruntwork-io/terragrunt/pkg/log"
	"github.com/gruntwork-io/terragrunt/util"
)

const (
	generationMaxPath = 1024
)

// StackNode represents a stack file in the file system.
// The parent is the node that generates the current node,
// and children are the nodes that are generated by the current node.
type StackNode struct {
	Parent   *StackNode
	FilePath string
	Children []*StackNode
	Level    int
}

// NewStackNode creates a new stack node.
func NewStackNode(filePath string) *StackNode {
	return &StackNode{
		FilePath: filePath,
		Level:    -1,
		Children: make([]*StackNode, 0),
	}
}

// GenerateStacks generates the stack files using topological ordering to prevent race conditions.
// Stack files are generated level by level, ensuring parent stacks complete before their children.
func GenerateStacks(ctx context.Context, l log.Logger, opts *options.TerragruntOptions) error {
	foundFiles, err := ListStackFilesMaybeWithDiscovery(ctx, l, opts, opts.WorkingDir)
	if err != nil {
		return errors.Errorf("Failed to list stack files in %s %w", opts.WorkingDir, err)
	}

	if len(foundFiles) == 0 {
		if opts.StackAction == "generate" {
			l.Warnf("No stack files found in %s Nothing to generate.", opts.WorkingDir)
		}

		return nil
	}

	generatedFiles := make(map[string]bool)

	stackTrees := BuildStackTopology(l, foundFiles, opts.WorkingDir)

	const maxLevel = 1024
	for level := range maxLevel {
		if level == maxLevel-1 {
			return errors.Errorf("Cycle detected: maximum level (%d) exceeded", maxLevel)
		}

		levelNodes := getNodesAtLevel(stackTrees, level)
		if len(levelNodes) == 0 {
			break
		}

		if err := generateLevel(ctx, l, opts, level, levelNodes, generatedFiles); err != nil {
			return err
		}

		if err := discoverAndAddNewNodes(ctx, l, opts, stackTrees, generatedFiles, level+1); err != nil {
			return err
		}
	}

	return nil
}

// generateLevel handles the concurrent generation of all stack files at a given level.
func generateLevel(ctx context.Context, l log.Logger, opts *options.TerragruntOptions, level int, levelNodes []*StackNode, generatedFiles map[string]bool) error {
	l.Debugf("Generating stack level %d with %d files", level, len(levelNodes))

	wp := worker.NewWorkerPool(opts.Parallelism)
	defer wp.Stop()

	for _, node := range levelNodes {
		if generatedFiles[node.FilePath] {
			continue
		}

		generatedFiles[node.FilePath] = true

		// Before attempting to generate the stack file, we need to double-check that the file exists.
		// Generation at a higher level might have resulted in this file being removed.
		if !util.FileExists(node.FilePath) {
			continue
		}

		wp.Submit(func() error {
			return config.GenerateStackFile(ctx, l, opts, wp, node.FilePath)
		})
	}

	return wp.Wait()
}

// discoverAndAddNewNodes discovers new stack files and adds them to the dependency graph.
func discoverAndAddNewNodes(ctx context.Context, l log.Logger, opts *options.TerragruntOptions, dependencyGraph map[string]*StackNode, generatedFiles map[string]bool, minLevel int) error {
	newFiles, listErr := ListStackFilesMaybeWithDiscovery(ctx, l, opts, opts.WorkingDir)
	if listErr != nil {
		return errors.Errorf("Failed to list stack files after level %d: %w", minLevel-1, listErr)
	}

	addNewNodesToGraph(l, dependencyGraph, newFiles, generatedFiles, opts.WorkingDir)

	return nil
}

// BuildStackTopology creates a topological tree based on directory hierarchy.
func BuildStackTopology(l log.Logger, stackFiles []string, workingDir string) map[string]*StackNode {
	nodes := make(map[string]*StackNode)

	for _, file := range stackFiles {
		nodes[file] = NewStackNode(file)
	}

	for _, node := range nodes {
		assignNodeLevel(l, node, nodes, workingDir)
	}

	return nodes
}

// assignNodeLevel recursively assigns levels to nodes based on directory depth.
func assignNodeLevel(l log.Logger, node *StackNode, allNodes map[string]*StackNode, workingDir string) int {
	if node.Level != -1 {
		return node.Level
	}

	nodeDir := filepath.Dir(node.FilePath)
	parentPath := findParentStackFile(nodeDir, allNodes, workingDir)

	if parentPath == "" {
		node.Level = 0

		return node.Level
	}

	parent := allNodes[parentPath]
	if parent == nil {
		node.Level = 0

		return node.Level
	}

	parentLevel := assignNodeLevel(l, parent, allNodes, workingDir)
	node.Level = parentLevel + 1
	node.Parent = parent
	parent.Children = append(parent.Children, node)

	l.Debugf("Stack %s (level %d) is child of %s (level %d)", node.FilePath, node.Level, parent.FilePath, parent.Level)

	return node.Level
}

// findParentStackFile finds the parent stack file for a given directory.
func findParentStackFile(childDir string, allNodes map[string]*StackNode, workingDir string) string {
	currentDir := childDir

	for {
		parentDir := filepath.Dir(currentDir)
		if parentDir == currentDir {
			break
		}

		if parentDir == workingDir {
			potentialParent := filepath.Join(workingDir, config.DefaultStackFile)
			if _, exists := allNodes[potentialParent]; exists {
				return potentialParent
			}

			break
		}

		potentialParent := filepath.Join(parentDir, config.DefaultStackFile)
		if _, exists := allNodes[potentialParent]; exists {
			return potentialParent
		}

		currentDir = parentDir
	}

	return ""
}

// getNodesAtLevel returns all nodes at a specific level.
func getNodesAtLevel(nodes map[string]*StackNode, level int) []*StackNode {
	var levelNodes []*StackNode

	for _, node := range nodes {
		if node.Level == level {
			levelNodes = append(levelNodes, node)
		}
	}

	return levelNodes
}

// addNewNodesToGraph adds newly discovered stack files to the dependency graph.
func addNewNodesToGraph(
	l log.Logger,
	existingNodes map[string]*StackNode,
	allFiles []string,
	generatedFiles map[string]bool,
	workingDir string,
) {
	newFiles := make([]string, 0)

	for _, file := range allFiles {
		if _, exists := existingNodes[file]; !exists && !generatedFiles[file] {
			newFiles = append(newFiles, file)
		}
	}

	if len(newFiles) == 0 {
		return
	}

	l.Debugf("Adding %d new stack files to topology graph", len(newFiles))

	for _, file := range newFiles {
		existingNodes[file] = NewStackNode(file)
	}

	for _, file := range newFiles {
		node := existingNodes[file]
		assignNodeLevel(l, node, existingNodes, workingDir)
	}
}

// ListStackFilesMaybeWithDiscovery searches for stack files in the specified directory using the discovery package.
//
// We only want to use the discovery package when the filter flag experiment is enabled, as we need to filter discovery
// results to ensure that we get the right files back for generation.
func ListStackFilesMaybeWithDiscovery(
	ctx context.Context,
	l log.Logger,
	opts *options.TerragruntOptions,
	dir string,
) ([]string, error) {
	if !opts.Experiments.Evaluate(experiment.FilterFlag) {
		return listStackFiles(l, opts, dir)
	}

	discovery, err := discovery.NewForStackGenerate(discovery.StackGenerateOptions{
		WorkingDir:    opts.WorkingDir,
		FilterQueries: opts.FilterQueries,
		Experiments:   opts.Experiments,
	})
	if err != nil {
		return nil, errors.Errorf("Failed to create discovery for stack generate: %w", err)
	}

	components, err := discovery.Discover(ctx, l, opts)
	if err != nil {
		return nil, errors.Errorf("Failed to discover stack files: %w", err)
	}

	foundFiles := make([]string, 0, len(components))
	for _, c := range components {
		if _, ok := c.(*component.Stack); !ok {
			continue
		}

		foundFiles = append(foundFiles, filepath.Join(c.Path(), config.DefaultStackFile))
	}

	return foundFiles, nil
}

// listStackFiles searches for stack files in the specified directory.
//
// The function walks through the given directory to find files that match the
// default stack file name. It optionally follows symbolic links based on the
// provided Terragrunt options.
func listStackFiles(l log.Logger, opts *options.TerragruntOptions, dir string) ([]string, error) {
	walkWithSymlinks := opts.Experiments.Evaluate(experiment.Symlinks)

	walkFunc := filepath.WalkDir
	if walkWithSymlinks {
		walkFunc = util.WalkDirWithSymlinks
	}

	l.Debugf("Searching for stack files in %s", dir)

	var stackFiles []string

	// find all defaultStackFile files
	if err := walkFunc(dir, func(path string, d fs.DirEntry, err error) error {
		if err != nil {
			l.Warnf("Error accessing path %s: %w", path, err)
			return nil
		}

		if d.IsDir() {
			return nil
		}

		// skip files in Terragrunt cache directory
		if strings.Contains(path, string(os.PathSeparator)+util.TerragruntCacheDir+string(os.PathSeparator)) ||
			filepath.Base(path) == util.TerragruntCacheDir {
			return filepath.SkipDir
		}

		if len(path) >= generationMaxPath {
			return errors.Errorf("Cycle detected: maximum path length (%d) exceeded at %s", generationMaxPath, path)
		}

		if strings.HasSuffix(path, config.DefaultStackFile) {
			l.Debugf("Found stack file %s", path)
			stackFiles = append(stackFiles, path)
		}
		return nil
	}); err != nil {
		return nil, err
	}

	return stackFiles, nil
}
