Resolve variant includes with the correct ordering

Summary:
Refactored variant include resolution to correctly order the hierarchy
of includes while still protecting against infinite recursion. The
function was renamed, refactored for clarity, and exported so as to be
better tested and documented with examples.

Test Plan:
Run `go test ./...`.

Check the rendered `config.ResolveIncludes` `godoc` for sanity.

Reviewers: thcipriani, mmodell, hashar, Jrbranaa, zeljkofilipin, demon, #release-engineering-team

Reviewed By: thcipriani, #release-engineering-team

Tags: #release-engineering-team

Differential Revision: https://phabricator.wikimedia.org/D959

3 files changed, 128 insertions, 46 deletions

diff --git a/config/reader.go b/config/reader.go
index 1496575..bb28603 100644
--- a/config/reader.go
+++ b/config/reader.go
@@ -8,29 +8,50 @@ import (
 	"gopkg.in/yaml.v2"
 )
 
-func expandIncludes(config *Config, name string, included map[string]bool) ([]string, error) {
-	variant, found := config.Variants[name]
+// ResolveIncludes iterates over and recurses through a given variant's
+// includes to build a flat slice of variant names in the correct order by
+// which they should be expanded/merged. It checks for both the existence of
+// included variants and maintains a recursion stack to protect against
+// infinite loops.
+//
+// Variant names found at a greater depth of recursion are first and siblings
+// last, the order in which config should be merged.
+//
+func ResolveIncludes(config *Config, name string) ([]string, error) {
+	stack := map[string]bool{}
+	includes := []string{}
 
-	if !found {
-		return nil, fmt.Errorf("variant '%s' does not exist", name)
-	}
+	var resolve func(string) error
 
-	if included[name] == true {
-		return nil, errors.New("variant expansion detected loop")
-	}
+	resolve = func(name string) error {
+		if instack, found := stack[name]; found && instack {
+			return errors.New("variant expansion detected loop")
+		}
 
-	for _, include := range variant.Includes {
-		included[name] = true
-		inc, err := expandIncludes(config, include, included)
+		stack[name] = true
+		defer func() { stack[name] = false }()
 
-		if err != nil {
-			return nil, err
+		variant, found := config.Variants[name]
+
+		if !found {
+			return fmt.Errorf("variant '%s' does not exist", name)
+		}
+
+		for _, include := range variant.Includes {
+			if err := resolve(include); err != nil {
+				return err
+			}
 		}
 
-		return append(inc, include), nil
+		// Appending _after_ recursion ensures the correct ordering
+		includes = append(includes, name)
+
+		return nil
 	}
 
-	return []string{}, nil
+	err := resolve(name)
+
+	return includes, err
 }
 
 // ExpandVariant merges a named variant with a config. It also attempts to
@@ -40,8 +61,7 @@ func ExpandVariant(config *Config, name string) (*VariantConfig, error) {
 	expanded := new(VariantConfig)
 	expanded.CommonConfig.Merge(config.CommonConfig)
 
-	includes, err := expandIncludes(config, name, map[string]bool{})
-	includes = append(includes, name)
+	includes, err := ResolveIncludes(config, name)
 
 	if err != nil {
 		return nil, err
diff --git a/config/reader_test.go b/config/reader_test.go
new file mode 100644
index 0000000..e11e7af
--- /dev/null
+++ b/config/reader_test.go
@@ -0,0 +1,91 @@
+package config_test
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+
+	"phabricator.wikimedia.org/source/blubber/config"
+)
+
+func ExampleResolveIncludes() {
+	cfg, _ := config.ReadConfig([]byte(`---
+    variants:
+      varA: { includes: [varB, varC] }
+      varB: { includes: [varD, varE] }
+      varC: {}
+      varD: { includes: [varF] }
+      varE: {}
+      varF: {}`))
+
+	includes, _ := config.ResolveIncludes(cfg, "varA")
+
+	fmt.Printf("%v\n", includes)
+
+	// Output: [varF varD varE varB varC varA]
+}
+
+func TestResolveIncludesPreventsInfiniteRecursion(t *testing.T) {
+	cfg, err := config.ReadConfig([]byte(`---
+    variants:
+      varA: { includes: [varB] }
+      varB: { includes: [varA] }`))
+
+	assert.NoError(t, err)
+
+	_, err2 := config.ResolveIncludes(cfg, "varA")
+
+	assert.EqualError(t, err2, "variant expansion detected loop")
+}
+
+func TestMultiLevelIncludes(t *testing.T) {
+	cfg, err := config.ReadConfig([]byte(`---
+    base: nodejs-slim
+    variants:
+      build:
+        base: nodejs-devel
+        node: {env: build}
+      development:
+        includes: [build]
+        node: {env: development}
+        entrypoint: [npm, start]
+      test:
+        includes: [development]
+        node: {dependencies: true}
+        entrypoint: [npm, test]`))
+
+	assert.NoError(t, err)
+
+	variant, _ := config.ExpandVariant(cfg, "test")
+
+	assert.Equal(t, "nodejs-devel", variant.Base)
+	assert.Equal(t, "development", variant.Node.Env)
+
+	devVariant, _ := config.ExpandVariant(cfg, "development")
+
+	assert.True(t, variant.Node.Dependencies.True)
+	assert.False(t, devVariant.Node.Dependencies.True)
+}
+
+func TestMultiIncludes(t *testing.T) {
+	cfg, err := config.ReadConfig([]byte(`---
+    variants:
+      mammal:
+        base: neutral
+      human:
+        base: moral
+        includes: [mammal]
+      lizard:
+        base: immoral
+      lizardman:
+        includes: [human, lizard]`))
+
+	if assert.NoError(t, err) {
+		variant, err := config.ExpandVariant(cfg, "lizardman")
+
+		if assert.NoError(t, err) {
+			assert.Equal(t, "immoral", variant.Base)
+		}
+	}
+}
diff --git a/config/variant_test.go b/config/variant_test.go
index 89a1e28..3f58c39 100644
--- a/config/variant_test.go
+++ b/config/variant_test.go
@@ -65,35 +65,6 @@ func TestVariantLoops(t *testing.T) {
 	assert.Nil(t, errTwo)
 }
 
-func TestMultiLevelIncludes(t *testing.T) {
-	cfg, err := config.ReadConfig([]byte(`---
-    base: nodejs-slim
-    variants:
-      build:
-        base: nodejs-devel
-        node: {env: build}
-      development:
-        includes: [build]
-        node: {env: development}
-        entrypoint: [npm, start]
-      test:
-        includes: [development]
-        node: {dependencies: true}
-        entrypoint: [npm, test]`))
-
-	assert.Nil(t, err)
-
-	variant, _ := config.ExpandVariant(cfg, "test")
-
-	assert.Equal(t, "nodejs-devel", variant.Base)
-	assert.Equal(t, "development", variant.Node.Env)
-
-	devVariant, _ := config.ExpandVariant(cfg, "development")
-
-	assert.True(t, variant.Node.Dependencies.True)
-	assert.False(t, devVariant.Node.Dependencies.True)
-}
-
 func TestVariantConfigInstructions(t *testing.T) {
 	t.Run("PhaseInstall", func(t *testing.T) {
 		t.Run("copies", func(t *testing.T) {