func getSortedKeys(modules map[string]*TerraformModule) []string {
	keys := []string{}
	for key, _ := range modules {
		keys = append(keys, key)
	}
	sort.Strings(keys)
	return keys
}
Return the keys for the given map in sorted order. This is used to ensure we always iterate over maps of modules
in a consistent order (Go does not guarantee iteration order for maps, and usually makes it random)
package configstack
import (
	"fmt"
	"path/filepath"
	"sort"
	"strings"
	"github.com/gruntwork-io/terragrunt/config"
	"github.com/gruntwork-io/terragrunt/errors"
	"github.com/gruntwork-io/terragrunt/options"
	"github.com/gruntwork-io/terragrunt/shell"
	"github.com/gruntwork-io/terragrunt/util"
	zglob "github.com/mattn/go-zglob"
)
const maxLevelsOfRecursion = 20
type TerraformModule struct {
	Path                 string
	Dependencies         []*TerraformModule
	Config               config.TerragruntConfig
	TerragruntOptions    *options.TerragruntOptions
	AssumeAlreadyApplied bool
	FlagExcluded         bool
}
func (module *TerraformModule) String() string {
	dependencies := []string{}
	for _, dependency := range module.Dependencies {
		dependencies = append(dependencies, dependency.Path)
	}
	return fmt.Sprintf(
		"Module %s (excluded: %v, assume applied: %v, dependencies: [%s])",
		module.Path, module.FlagExcluded, module.AssumeAlreadyApplied, strings.Join(dependencies, ", "),
	)
}
func ResolveTerraformModules(terragruntConfigPaths []string, terragruntOptions *options.TerragruntOptions, howThesePathsWereFound string) ([]*TerraformModule, error) {
	canonicalTerragruntConfigPaths, err := util.CanonicalPaths(terragruntConfigPaths, ".")
	if err != nil {
		return []*TerraformModule{}, err
	}
	modules, err := resolveModules(canonicalTerragruntConfigPaths, terragruntOptions, howThesePathsWereFound)
	if err != nil {
		return []*TerraformModule{}, err
	}
	externalDependencies, err := resolveExternalDependenciesForModules(modules, map[string]*TerraformModule{}, 0, terragruntOptions)
	if err != nil {
		return []*TerraformModule{}, err
	}
	crossLinkedModules, err := crosslinkDependencies(mergeMaps(modules, externalDependencies), canonicalTerragruntConfigPaths)
	if err != nil {
		return []*TerraformModule{}, err
	}
	includedModules, err := flagIncludedDirs(crossLinkedModules, terragruntOptions)
	if err != nil {
		return []*TerraformModule{}, err
	}
	finalModules, err := flagExcludedDirs(includedModules, terragruntOptions)
	if err != nil {
		return []*TerraformModule{}, err
	}
	return finalModules, nil
}
func flagExcludedDirs(modules []*TerraformModule, terragruntOptions *options.TerragruntOptions) ([]*TerraformModule, error) {
	if len(terragruntOptions.ExcludeDirs) == 0 {
		return modules, nil
	}
	canonicalWorkingDir, err := util.CanonicalPath("", terragruntOptions.WorkingDir)
	if err != nil {
		return nil, err
	}
	excludeGlobMatches := []string{}
	for _, dir := range terragruntOptions.ExcludeDirs {
		absoluteDir := ""
		if filepath.IsAbs(dir) {
			absoluteDir = dir
		} else {
			absoluteDir = filepath.Join(canonicalWorkingDir, dir)
		}
		matches, err := zglob.Glob(absoluteDir)
		if err == nil {
			excludeGlobMatches = append(excludeGlobMatches, matches...)
		}
	}
	canonicalExcludeDirs := []string{}
	for _, module := range excludeGlobMatches {
		canonicalPath, err := util.CanonicalPath(module, terragruntOptions.WorkingDir)
		if err != nil {
			return nil, err
		}
		canonicalExcludeDirs = append(canonicalExcludeDirs, canonicalPath)
	}
	for _, module := range modules {
		if findModuleinPath(module, canonicalExcludeDirs) {
			module.FlagExcluded = true
		}
		for _, dependency := range module.Dependencies {
			if findModuleinPath(dependency, canonicalExcludeDirs) {
				dependency.FlagExcluded = true
			}
		}
	}
	return modules, nil
}
func flagIncludedDirs(modules []*TerraformModule, terragruntOptions *options.TerragruntOptions) ([]*TerraformModule, error) {
	if len(terragruntOptions.IncludeDirs) == 0 {
		if terragruntOptions.StrictInclude {
			return []*TerraformModule{}, nil
		}
		return modules, nil
	}
	canonicalWorkingDir, err := util.CanonicalPath("", terragruntOptions.WorkingDir)
	if err != nil {
		return nil, err
	}
	includeGlobMatches := []string{}
	for _, dir := range terragruntOptions.IncludeDirs {
		absoluteDir := dir
		if !filepath.IsAbs(dir) {
			absoluteDir = filepath.Join(canonicalWorkingDir, dir)
		}
		matches, err := zglob.Glob(absoluteDir)
		if err == nil {
			includeGlobMatches = append(includeGlobMatches, matches...)
		}
	}
	canonicalIncludeDirs := []string{}
	for _, module := range includeGlobMatches {
		canonicalPath, err := util.CanonicalPath(module, terragruntOptions.WorkingDir)
		if err != nil {
			return nil, err
		}
		canonicalIncludeDirs = append(canonicalIncludeDirs, canonicalPath)
	}
	for _, module := range modules {
		if findModuleinPath(module, canonicalIncludeDirs) {
			module.FlagExcluded = false
		} else {
			module.FlagExcluded = true
		}
	}
	if !terragruntOptions.StrictInclude {
		for _, module := range modules {
			if !module.FlagExcluded {
				for _, dependency := range module.Dependencies {
					dependency.FlagExcluded = false
				}
			}
		}
	}
	return modules, nil
}
func findModuleinPath(module *TerraformModule, targetDirs []string) bool {
	for _, targetDir := range targetDirs {
		if module.Path == targetDir {
			return true
		}
	}
	return false
}
func resolveModules(canonicalTerragruntConfigPaths []string, terragruntOptions *options.TerragruntOptions, howTheseModulesWereFound string) (map[string]*TerraformModule, error) {
	moduleMap := map[string]*TerraformModule{}
	for _, terragruntConfigPath := range canonicalTerragruntConfigPaths {
		module, err := resolveTerraformModule(terragruntConfigPath, terragruntOptions, howTheseModulesWereFound)
		if err != nil {
			return moduleMap, err
		}
		if module != nil {
			moduleMap[module.Path] = module
		}
	}
	return moduleMap, nil
}
func resolveTerraformModule(terragruntConfigPath string, terragruntOptions *options.TerragruntOptions, howThisModuleWasFound string) (*TerraformModule, error) {
	modulePath, err := util.CanonicalPath(filepath.Dir(terragruntConfigPath), ".")
	if err != nil {
		return nil, err
	}
	opts := terragruntOptions.Clone(terragruntConfigPath)
	opts.OriginalTerragruntConfigPath = terragruntConfigPath
	terragruntConfig, err := config.PartialParseConfigFile(
		terragruntConfigPath,
		opts,
		nil,
		[]config.PartialDecodeSectionType{
			config.TerraformSource,
			config.DependenciesBlock,
			config.DependencyBlock,
		},
	)
	if err != nil {
		return nil, errors.WithStackTrace(ErrorProcessingModule{UnderlyingError: err, HowThisModuleWasFound: howThisModuleWasFound, ModulePath: terragruntConfigPath})
	}
	terragruntSource, err := config.GetTerragruntSourceForModule(terragruntOptions.Source, modulePath, terragruntConfig)
	if err != nil {
		return nil, err
	}
	opts.Source = terragruntSource
	_, defaultDownloadDir, err := options.DefaultWorkingAndDownloadDirs(terragruntOptions.TerragruntConfigPath)
	if err != nil {
		return nil, err
	}
	if terragruntOptions.DownloadDir == defaultDownloadDir {
		_, downloadDir, err := options.DefaultWorkingAndDownloadDirs(terragruntConfigPath)
		if err != nil {
			return nil, err
		}
		terragruntOptions.Logger.Debugf("Setting download directory for module %s to %s", modulePath, downloadDir)
		opts.DownloadDir = downloadDir
	}
	matches, err := filepath.Glob(filepath.Join(filepath.Dir(terragruntConfigPath), "*.tf"))
	if err != nil {
		return nil, err
	}
	if (terragruntConfig.Terraform == nil || terragruntConfig.Terraform.Source == nil || *terragruntConfig.Terraform.Source == "") && matches == nil {
		terragruntOptions.Logger.Debugf("Module %s does not have an associated terraform configuration and will be skipped.", filepath.Dir(terragruntConfigPath))
		return nil, nil
	}
	return &TerraformModule{Path: modulePath, Config: *terragruntConfig, TerragruntOptions: opts}, nil
}
func resolveExternalDependenciesForModules(moduleMap map[string]*TerraformModule, modulesAlreadyProcessed map[string]*TerraformModule, recursionLevel int, terragruntOptions *options.TerragruntOptions) (map[string]*TerraformModule, error) {
	allExternalDependencies := map[string]*TerraformModule{}
	modulesToSkip := mergeMaps(moduleMap, modulesAlreadyProcessed)
	if recursionLevel > maxLevelsOfRecursion {
		return allExternalDependencies, errors.WithStackTrace(InfiniteRecursion{RecursionLevel: maxLevelsOfRecursion, Modules: modulesToSkip})
	}
	sortedKeys := getSortedKeys(moduleMap)
	for _, key := range sortedKeys {
		module := moduleMap[key]
		externalDependencies, err := resolveExternalDependenciesForModule(module, modulesToSkip, terragruntOptions)
		if err != nil {
			return externalDependencies, err
		}
		for _, externalDependency := range externalDependencies {
			if _, alreadyFound := modulesToSkip[externalDependency.Path]; alreadyFound {
				continue
			}
			shouldApply := false
			if !terragruntOptions.IgnoreExternalDependencies {
				shouldApply, err = confirmShouldApplyExternalDependency(module, externalDependency, terragruntOptions)
				if err != nil {
					return externalDependencies, err
				}
			}
			externalDependency.AssumeAlreadyApplied = !shouldApply
			allExternalDependencies[externalDependency.Path] = externalDependency
		}
	}
	if len(allExternalDependencies) > 0 {
		recursiveDependencies, err := resolveExternalDependenciesForModules(allExternalDependencies, moduleMap, recursionLevel+1, terragruntOptions)
		if err != nil {
			return allExternalDependencies, err
		}
		return mergeMaps(allExternalDependencies, recursiveDependencies), nil
	}
	return allExternalDependencies, nil
}
func resolveExternalDependenciesForModule(module *TerraformModule, moduleMap map[string]*TerraformModule, terragruntOptions *options.TerragruntOptions) (map[string]*TerraformModule, error) {
	if module.Config.Dependencies == nil || len(module.Config.Dependencies.Paths) == 0 {
		return map[string]*TerraformModule{}, nil
	}
	externalTerragruntConfigPaths := []string{}
	for _, dependency := range module.Config.Dependencies.Paths {
		dependencyPath, err := util.CanonicalPath(dependency, module.Path)
		if err != nil {
			return map[string]*TerraformModule{}, err
		}
		terragruntConfigPath := config.GetDefaultConfigPath(dependencyPath)
		if _, alreadyContainsModule := moduleMap[dependencyPath]; !alreadyContainsModule {
			externalTerragruntConfigPaths = append(externalTerragruntConfigPaths, terragruntConfigPath)
		}
	}
	howThesePathsWereFound := fmt.Sprintf("dependency of module at '%s'", module.Path)
	return resolveModules(externalTerragruntConfigPaths, terragruntOptions, howThesePathsWereFound)
}
func confirmShouldApplyExternalDependency(module *TerraformModule, dependency *TerraformModule, terragruntOptions *options.TerragruntOptions) (bool, error) {
	if terragruntOptions.IncludeExternalDependencies {
		terragruntOptions.Logger.Debugf("The --terragrunt-include-external-dependencies flag is set, so automatically including all external dependencies, and will run this command against module %s, which is a dependency of module %s.", dependency.Path, module.Path)
		return true, nil
	}
	if terragruntOptions.NonInteractive {
		terragruntOptions.Logger.Debugf("The --non-interactive flag is set. To avoid accidentally affecting external dependencies with a run-all command, will not run this command against module %s, which is a dependency of module %s.", dependency.Path, module.Path)
		return false, nil
	}
	stackCmd := terragruntOptions.TerraformCommand
	if stackCmd == "destroy" {
		terragruntOptions.Logger.Debugf("run-all command called with destroy. To avoid accidentally having destructive effects on external dependencies with run-all command, will not run this command against module %s, which is a dependency of module %s.", dependency.Path, module.Path)
		return false, nil
	}
	prompt := fmt.Sprintf("Module %s depends on module %s, which is an external dependency outside of the current working directory. Should Terragrunt run this external dependency? Warning, if you say 'yes', Terragrunt will make changes in %s as well!", module.Path, dependency.Path, dependency.Path)
	return shell.PromptUserForYesNo(prompt, terragruntOptions)
}
func mergeMaps(modules map[string]*TerraformModule, externalDependencies map[string]*TerraformModule) map[string]*TerraformModule {
	out := map[string]*TerraformModule{}
	for key, value := range externalDependencies {
		out[key] = value
	}
	for key, value := range modules {
		out[key] = value
	}
	return out
}
func crosslinkDependencies(moduleMap map[string]*TerraformModule, canonicalTerragruntConfigPaths []string) ([]*TerraformModule, error) {
	modules := []*TerraformModule{}
	keys := getSortedKeys(moduleMap)
	for _, key := range keys {
		module := moduleMap[key]
		dependencies, err := getDependenciesForModule(module, moduleMap, canonicalTerragruntConfigPaths)
		if err != nil {
			return modules, err
		}
		module.Dependencies = dependencies
		modules = append(modules, module)
	}
	return modules, nil
}
func getDependenciesForModule(module *TerraformModule, moduleMap map[string]*TerraformModule, terragruntConfigPaths []string) ([]*TerraformModule, error) {
	dependencies := []*TerraformModule{}
	if module.Config.Dependencies == nil || len(module.Config.Dependencies.Paths) == 0 {
		return dependencies, nil
	}
	for _, dependencyPath := range module.Config.Dependencies.Paths {
		dependencyModulePath, err := util.CanonicalPath(dependencyPath, module.Path)
		if err != nil {
			return dependencies, nil
		}
		dependencyModule, foundModule := moduleMap[dependencyModulePath]
		if !foundModule {
			err := UnrecognizedDependency{
				ModulePath:            module.Path,
				DependencyPath:        dependencyPath,
				TerragruntConfigPaths: terragruntConfigPaths,
			}
			return dependencies, errors.WithStackTrace(err)
		}
		dependencies = append(dependencies, dependencyModule)
	}
	return dependencies, nil
}