diff --git a/Blueprints b/Blueprints
index ecc0792..25c22ab 100644
--- a/Blueprints
+++ b/Blueprints
@@ -17,6 +17,7 @@
         "ninja_strings.go",
         "ninja_writer.go",
         "package_ctx.go",
+        "provider.go",
         "scope.go",
         "singleton_ctx.go",
     ],
@@ -26,6 +27,7 @@
         "module_ctx_test.go",
         "ninja_strings_test.go",
         "ninja_writer_test.go",
+        "provider_test.go",
         "splice_modules_test.go",
         "visit_test.go",
     ],
diff --git a/bootstrap.bash b/bootstrap.bash
index 08b85b5..b08bf1e 100755
--- a/bootstrap.bash
+++ b/bootstrap.bash
@@ -67,12 +67,14 @@
     echo "  -h: print a help message and exit"
     echo "  -b <builddir>: set the build directory"
     echo "  -t: run tests"
+    echo "  -n: use validations to depend on tests"
 }
 
 # Parse the command line flags.
-while getopts ":b:ht" opt; do
+while getopts ":b:hnt" opt; do
     case $opt in
         b) BUILDDIR="$OPTARG";;
+        n) USE_VALIDATIONS=true;;
         t) RUN_TESTS=true;;
         h)
             usage
@@ -93,6 +95,9 @@
 # If RUN_TESTS is set, behave like -t was passed in as an option.
 [ ! -z "$RUN_TESTS" ] && EXTRA_ARGS="${EXTRA_ARGS} -t"
 
+# If $USE_VALIDATIONS is set, pass --use-validations.
+[ ! -z "$USE_VALIDATIONS" ] && EXTRA_ARGS="${EXTRA_ARGS} --use-validations"
+
 # If EMPTY_NINJA_FILE is set, have the primary build write out a 0-byte ninja
 # file instead of a full length one. Useful if you don't plan on executing the
 # build, but want to verify the primary builder execution.
diff --git a/bootstrap/bootstrap.go b/bootstrap/bootstrap.go
index bb85e7d..64fa8e5 100644
--- a/bootstrap/bootstrap.go
+++ b/bootstrap/bootstrap.go
@@ -180,8 +180,10 @@
 
 func pluginDeps(ctx blueprint.BottomUpMutatorContext) {
 	if pkg, ok := ctx.Module().(*goPackage); ok {
-		for _, plugin := range pkg.properties.PluginFor {
-			ctx.AddReverseDependency(ctx.Module(), nil, plugin)
+		if ctx.PrimaryModule() == ctx.Module() {
+			for _, plugin := range pkg.properties.PluginFor {
+				ctx.AddReverseDependency(ctx.Module(), nil, plugin)
+			}
 		}
 	}
 }
@@ -211,7 +213,7 @@
 	}
 }
 
-func isBootstrapModule(module blueprint.Module) bool {
+func IsBootstrapModule(module blueprint.Module) bool {
 	_, isPackage := module.(*goPackage)
 	_, isBinary := module.(*goBinary)
 	return isPackage || isBinary
@@ -268,6 +270,9 @@
 }
 
 func (g *goPackage) DynamicDependencies(ctx blueprint.DynamicDependerModuleContext) []string {
+	if ctx.Module() != ctx.PrimaryModule() {
+		return nil
+	}
 	return g.properties.Deps
 }
 
@@ -297,6 +302,16 @@
 }
 
 func (g *goPackage) GenerateBuildActions(ctx blueprint.ModuleContext) {
+	// Allow the primary builder to create multiple variants.  Any variants after the first
+	// will copy outputs from the first.
+	if ctx.Module() != ctx.PrimaryModule() {
+		primary := ctx.PrimaryModule().(*goPackage)
+		g.pkgRoot = primary.pkgRoot
+		g.archiveFile = primary.archiveFile
+		g.testResultFile = primary.testResultFile
+		return
+	}
+
 	var (
 		name       = ctx.ModuleName()
 		hasPlugins = false
@@ -338,7 +353,7 @@
 			filepath.FromSlash(g.properties.PkgPath)+".a")
 		g.testResultFile = buildGoTest(ctx, testRoot(ctx, g.config), testArchiveFile,
 			g.properties.PkgPath, srcs, genSrcs,
-			testSrcs)
+			testSrcs, g.config.useValidations)
 	}
 
 	buildGoPackage(ctx, g.pkgRoot, g.properties.PkgPath, g.archiveFile,
@@ -386,6 +401,9 @@
 }
 
 func (g *goBinary) DynamicDependencies(ctx blueprint.DynamicDependerModuleContext) []string {
+	if ctx.Module() != ctx.PrimaryModule() {
+		return nil
+	}
 	return g.properties.Deps
 }
 
@@ -395,6 +413,14 @@
 }
 
 func (g *goBinary) GenerateBuildActions(ctx blueprint.ModuleContext) {
+	// Allow the primary builder to create multiple variants.  Any variants after the first
+	// will copy outputs from the first.
+	if ctx.Module() != ctx.PrimaryModule() {
+		primary := ctx.PrimaryModule().(*goBinary)
+		g.installPath = primary.installPath
+		return
+	}
+
 	var (
 		name            = ctx.ModuleName()
 		objDir          = moduleObjDir(ctx, g.config)
@@ -421,7 +447,7 @@
 		genSrcs = append(genSrcs, pluginSrc)
 	}
 
-	var deps []string
+	var testDeps []string
 
 	if hasPlugins && !buildGoPluginLoader(ctx, "main", pluginSrc) {
 		return
@@ -437,8 +463,8 @@
 	}
 
 	if g.config.runGoTests {
-		deps = buildGoTest(ctx, testRoot(ctx, g.config), testArchiveFile,
-			name, srcs, genSrcs, testSrcs)
+		testDeps = buildGoTest(ctx, testRoot(ctx, g.config), testArchiveFile,
+			name, srcs, genSrcs, testSrcs, g.config.useValidations)
 	}
 
 	buildGoPackage(ctx, objDir, "main", archiveFile, srcs, genSrcs)
@@ -451,7 +477,7 @@
 			linkDeps = append(linkDeps, dep.GoPackageTarget())
 			libDir := dep.GoPkgRoot()
 			libDirFlags = append(libDirFlags, "-L "+libDir)
-			deps = append(deps, dep.GoTestTargets()...)
+			testDeps = append(testDeps, dep.GoTestTargets()...)
 		})
 
 	linkArgs := map[string]string{}
@@ -468,12 +494,20 @@
 		Optional:  true,
 	})
 
+	var orderOnlyDeps, validationDeps []string
+	if g.config.useValidations {
+		validationDeps = testDeps
+	} else {
+		orderOnlyDeps = testDeps
+	}
+
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      cp,
-		Outputs:   []string{g.installPath},
-		Inputs:    []string{aoutFile},
-		OrderOnly: deps,
-		Optional:  !g.properties.Default,
+		Rule:        cp,
+		Outputs:     []string{g.installPath},
+		Inputs:      []string{aoutFile},
+		OrderOnly:   orderOnlyDeps,
+		Validations: validationDeps,
+		Optional:    !g.properties.Default,
 	})
 }
 
@@ -538,7 +572,7 @@
 }
 
 func buildGoTest(ctx blueprint.ModuleContext, testRoot, testPkgArchive,
-	pkgPath string, srcs, genSrcs, testSrcs []string) []string {
+	pkgPath string, srcs, genSrcs, testSrcs []string, useValidations bool) []string {
 
 	if len(testSrcs) == 0 {
 		return nil
@@ -600,11 +634,19 @@
 		Optional: true,
 	})
 
+	var orderOnlyDeps, validationDeps []string
+	if useValidations {
+		validationDeps = testDeps
+	} else {
+		orderOnlyDeps = testDeps
+	}
+
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      test,
-		Outputs:   []string{testPassed},
-		Inputs:    []string{testFile},
-		OrderOnly: testDeps,
+		Rule:        test,
+		Outputs:     []string{testPassed},
+		Inputs:      []string{testFile},
+		OrderOnly:   orderOnlyDeps,
+		Validations: validationDeps,
 		Args: map[string]string{
 			"pkg":       pkgPath,
 			"pkgSrcDir": filepath.Dir(testFiles[0]),
@@ -637,13 +679,15 @@
 	var blueprintTools []string
 	ctx.VisitAllModulesIf(isBootstrapBinaryModule,
 		func(module blueprint.Module) {
-			binaryModule := module.(*goBinary)
+			if ctx.PrimaryModule(module) == module {
+				binaryModule := module.(*goBinary)
 
-			if binaryModule.properties.Tool_dir {
-				blueprintTools = append(blueprintTools, binaryModule.InstallPath())
-			}
-			if binaryModule.properties.PrimaryBuilder {
-				primaryBuilders = append(primaryBuilders, binaryModule)
+				if binaryModule.properties.Tool_dir {
+					blueprintTools = append(blueprintTools, binaryModule.InstallPath())
+				}
+				if binaryModule.properties.PrimaryBuilder {
+					primaryBuilders = append(primaryBuilders, binaryModule)
+				}
 			}
 		})
 
diff --git a/bootstrap/bpdoc/bpdoc_test.go b/bootstrap/bpdoc/bpdoc_test.go
index 687d97b..3856933 100644
--- a/bootstrap/bpdoc/bpdoc_test.go
+++ b/bootstrap/bpdoc/bpdoc_test.go
@@ -1,6 +1,7 @@
 package bpdoc
 
 import (
+	"fmt"
 	"reflect"
 	"testing"
 )
@@ -44,3 +45,37 @@
 		}
 	}
 }
+
+func TestAllPackages(t *testing.T) {
+	packages, err := AllPackages(pkgFiles, moduleTypeNameFactories, moduleTypeNamePropertyStructs)
+	if err != nil {
+		t.Errorf("expected nil error for AllPackages(%v, %v, %v), got %s", pkgFiles, moduleTypeNameFactories, moduleTypeNamePropertyStructs, err)
+	}
+
+	if numPackages := len(packages); numPackages != 1 {
+		t.Errorf("Expected %d package, got %d packages %v instead", len(pkgFiles), numPackages, packages)
+	}
+
+	pkg := packages[0]
+
+	for _, m := range pkg.ModuleTypes {
+		for _, p := range m.PropertyStructs {
+			for _, err := range noMutatedProperties(p.Properties) {
+				t.Errorf("%s", err)
+			}
+		}
+	}
+}
+
+func noMutatedProperties(properties []Property) []error {
+	errs := []error{}
+	for _, p := range properties {
+		if hasTag(p.Tag, "blueprint", "mutated") {
+			err := fmt.Errorf("Property %s has `blueprint:\"mutated\" tag but should have been excluded.", p)
+			errs = append(errs, err)
+		}
+
+		errs = append(errs, noMutatedProperties(p.Properties)...)
+	}
+	return errs
+}
diff --git a/bootstrap/bpdoc/properties.go b/bootstrap/bpdoc/properties.go
index 9256d8e..dcbb80e 100644
--- a/bootstrap/bpdoc/properties.go
+++ b/bootstrap/bpdoc/properties.go
@@ -251,6 +251,7 @@
 	filtered := (*props)[:0]
 	for _, x := range *props {
 		if hasTag(x.Tag, key, value) == !exclude {
+			filterPropsByTag(&x.Properties, key, value, exclude)
 			filtered = append(filtered, x)
 		}
 	}
diff --git a/bootstrap/bpdoc/properties_test.go b/bootstrap/bpdoc/properties_test.go
index 4045cb1..085bcdf 100644
--- a/bootstrap/bpdoc/properties_test.go
+++ b/bootstrap/bpdoc/properties_test.go
@@ -28,11 +28,8 @@
 
 	ps.ExcludeByTag("tag1", "a")
 
-	expected := []string{"c"}
-	actual := []string{}
-	for _, p := range ps.Properties {
-		actual = append(actual, p.Name)
-	}
+	expected := []string{"c", "d", "g"}
+	actual := actualProperties(t, ps.Properties)
 	if !reflect.DeepEqual(expected, actual) {
 		t.Errorf("unexpected ExcludeByTag result, expected: %q, actual: %q", expected, actual)
 	}
@@ -47,12 +44,20 @@
 
 	ps.IncludeByTag("tag1", "c")
 
-	expected := []string{"b", "c"}
-	actual := []string{}
-	for _, p := range ps.Properties {
-		actual = append(actual, p.Name)
-	}
+	expected := []string{"b", "c", "d", "f", "g"}
+	actual := actualProperties(t, ps.Properties)
 	if !reflect.DeepEqual(expected, actual) {
 		t.Errorf("unexpected IncludeByTag result, expected: %q, actual: %q", expected, actual)
 	}
 }
+
+func actualProperties(t *testing.T, props []Property) []string {
+	t.Helper()
+
+	actual := []string{}
+	for _, p := range props {
+		actual = append(actual, p.Name)
+		actual = append(actual, actualProperties(t, p.Properties)...)
+	}
+	return actual
+}
diff --git a/bootstrap/bpdoc/reader_test.go b/bootstrap/bpdoc/reader_test.go
index 0d608b3..8493e14 100644
--- a/bootstrap/bpdoc/reader_test.go
+++ b/bootstrap/bpdoc/reader_test.go
@@ -16,6 +16,7 @@
 package bpdoc
 
 import (
+	"html/template"
 	"reflect"
 	"runtime"
 	"testing"
@@ -23,11 +24,29 @@
 	"github.com/google/blueprint"
 )
 
+type factoryFn func() (blueprint.Module, []interface{})
+
 // foo docs.
 func fooFactory() (blueprint.Module, []interface{}) {
 	return nil, []interface{}{&props{}}
 }
 
+// bar docs.
+func barFactory() (blueprint.Module, []interface{}) {
+	return nil, []interface{}{&complexProps{}}
+}
+
+// for bpdoc_test.go
+type complexProps struct {
+	A         string
+	B_mutated string `blueprint:"mutated"`
+
+	Nested struct {
+		C         string
+		D_mutated string `blueprint:"mutated"`
+	}
+}
+
 // props docs.
 type props struct {
 	// A docs.
@@ -39,10 +58,18 @@
 	A string `tag1:"a,b" tag2:"c"`
 	B string `tag1:"a,c"`
 	C string `tag1:"b,c"`
+
+	D struct {
+		E string `tag1:"a,b" tag2:"c"`
+		F string `tag1:"a,c"`
+		G string `tag1:"b,c"`
+	} `tag1:"b,c"`
 }
 
 var pkgPath string
 var pkgFiles map[string][]string
+var moduleTypeNameFactories map[string]reflect.Value
+var moduleTypeNamePropertyStructs map[string][]interface{}
 
 func init() {
 	pc, filename, _, _ := runtime.Caller(0)
@@ -57,21 +84,34 @@
 	pkgFiles = map[string][]string{
 		pkgPath: {filename},
 	}
+
+	factories := map[string]factoryFn{"foo": fooFactory, "bar": barFactory}
+
+	moduleTypeNameFactories = make(map[string]reflect.Value, len(factories))
+	moduleTypeNamePropertyStructs = make(map[string][]interface{}, len(factories))
+	for name, factory := range factories {
+		moduleTypeNameFactories[name] = reflect.ValueOf(factory)
+		_, structs := factory()
+		moduleTypeNamePropertyStructs[name] = structs
+	}
 }
 
 func TestModuleTypeDocs(t *testing.T) {
 	r := NewReader(pkgFiles)
-	mt, err := r.ModuleType("foo_module", reflect.ValueOf(fooFactory))
-	if err != nil {
-		t.Fatal(err)
-	}
+	for m := range moduleTypeNameFactories {
+		mt, err := r.ModuleType(m+"_module", moduleTypeNameFactories[m])
+		if err != nil {
+			t.Fatal(err)
+		}
 
-	if mt.Text != "foo docs.\n\n" {
-		t.Errorf("unexpected docs %q", mt.Text)
-	}
+		expectedText := template.HTML(m + " docs.\n\n")
+		if mt.Text != expectedText {
+			t.Errorf("unexpected docs %q", mt.Text)
+		}
 
-	if mt.PkgPath != pkgPath {
-		t.Errorf("expected pkgpath %q, got %q", pkgPath, mt.PkgPath)
+		if mt.PkgPath != pkgPath {
+			t.Errorf("expected pkgpath %q, got %q", pkgPath, mt.PkgPath)
+		}
 	}
 }
 
diff --git a/bootstrap/command.go b/bootstrap/command.go
index 1f73ce3..dc655e8 100644
--- a/bootstrap/command.go
+++ b/bootstrap/command.go
@@ -40,6 +40,7 @@
 	memprofile     string
 	traceFile      string
 	runGoTests     bool
+	useValidations bool
 	noGC           bool
 	emptyNinjaFile bool
 	BuildDir       string
@@ -61,6 +62,7 @@
 	flag.StringVar(&memprofile, "memprofile", "", "write memory profile to file")
 	flag.BoolVar(&noGC, "nogc", false, "turn off GC for debugging")
 	flag.BoolVar(&runGoTests, "t", false, "build and run go tests during bootstrap")
+	flag.BoolVar(&useValidations, "use-validations", false, "use validations to depend on go tests")
 	flag.StringVar(&ModuleListFile, "l", "", "file that lists filepaths to parse")
 	flag.BoolVar(&emptyNinjaFile, "empty-ninja-file", false, "write out a 0-byte ninja file")
 }
@@ -131,6 +133,7 @@
 		topLevelBlueprintsFile: flag.Arg(0),
 		emptyNinjaFile:         emptyNinjaFile,
 		runGoTests:             runGoTests,
+		useValidations:         useValidations,
 		moduleListFile:         ModuleListFile,
 	}
 
diff --git a/bootstrap/config.go b/bootstrap/config.go
index 9499aeb..ace0ae6 100644
--- a/bootstrap/config.go
+++ b/bootstrap/config.go
@@ -107,5 +107,6 @@
 
 	emptyNinjaFile bool
 	runGoTests     bool
+	useValidations bool
 	moduleListFile string
 }
diff --git a/bpmodify/bpmodify.go b/bpmodify/bpmodify.go
index 29e97d1..0190f19 100644
--- a/bpmodify/bpmodify.go
+++ b/bpmodify/bpmodify.go
@@ -22,18 +22,20 @@
 
 var (
 	// main operation modes
-	list            = flag.Bool("l", false, "list files that would be modified by bpmodify")
-	write           = flag.Bool("w", false, "write result to (source) file instead of stdout")
-	doDiff          = flag.Bool("d", false, "display diffs instead of rewriting files")
-	sortLists       = flag.Bool("s", false, "sort touched lists, even if they were unsorted")
-	parameter       = flag.String("parameter", "deps", "name of parameter to modify on each module")
-	targetedModules = new(identSet)
-	addIdents       = new(identSet)
-	removeIdents    = new(identSet)
+	list             = flag.Bool("l", false, "list files that would be modified by bpmodify")
+	write            = flag.Bool("w", false, "write result to (source) file instead of stdout")
+	doDiff           = flag.Bool("d", false, "display diffs instead of rewriting files")
+	sortLists        = flag.Bool("s", false, "sort touched lists, even if they were unsorted")
+	targetedModules  = new(identSet)
+	targetedProperty = new(qualifiedProperty)
+	addIdents        = new(identSet)
+	removeIdents     = new(identSet)
 )
 
 func init() {
 	flag.Var(targetedModules, "m", "comma or whitespace separated list of modules on which to operate")
+	flag.Var(targetedProperty, "parameter", "alias to -property=`name`")
+	flag.Var(targetedProperty, "property", "fully qualified `name` of property to modify (default \"deps\")")
 	flag.Var(addIdents, "a", "comma or whitespace separated list of identifiers to add")
 	flag.Var(removeIdents, "r", "comma or whitespace separated list of identifiers to remove")
 	flag.Usage = usage
@@ -140,24 +142,74 @@
 
 func processModule(module *parser.Module, moduleName string,
 	file *parser.File) (modified bool, errs []error) {
-
-	for _, prop := range module.Properties {
-		if prop.Name == *parameter {
-			modified, errs = processParameter(prop.Value, *parameter, moduleName, file)
-			return
+	prop, err := getRecursiveProperty(module, targetedProperty.name(), targetedProperty.prefixes())
+	if err != nil {
+		return false, []error{err}
+	}
+	if prop == nil {
+		if len(addIdents.idents) == 0 {
+			// We cannot find an existing prop, and we aren't adding anything to the prop,
+			// which means we must be removing something from a non-existing prop,
+			// which means this is a noop.
+			return false, nil
+		}
+		// Else we are adding something to a non-existing prop, so we need to create it first.
+		prop, modified, err = createRecursiveProperty(module, targetedProperty.name(), targetedProperty.prefixes())
+		if err != nil {
+			// Here should be unreachable, but still handle it for completeness.
+			return false, []error{err}
 		}
 	}
-
-	prop := parser.Property{Name: *parameter, Value: &parser.List{}}
-	modified, errs = processParameter(prop.Value, *parameter, moduleName, file)
-
-	if modified {
-		module.Properties = append(module.Properties, &prop)
-	}
-
+	m, errs := processParameter(prop.Value, targetedProperty.String(), moduleName, file)
+	modified = modified || m
 	return modified, errs
 }
 
+func getRecursiveProperty(module *parser.Module, name string, prefixes []string) (prop *parser.Property, err error) {
+	prop, _, err = getOrCreateRecursiveProperty(module, name, prefixes, false)
+	return prop, err
+}
+
+func createRecursiveProperty(module *parser.Module, name string, prefixes []string) (prop *parser.Property, modified bool, err error) {
+	return getOrCreateRecursiveProperty(module, name, prefixes, true)
+}
+
+func getOrCreateRecursiveProperty(module *parser.Module, name string, prefixes []string,
+	createIfNotFound bool) (prop *parser.Property, modified bool, err error) {
+	m := &module.Map
+	for i, prefix := range prefixes {
+		if prop, found := m.GetProperty(prefix); found {
+			if mm, ok := prop.Value.Eval().(*parser.Map); ok {
+				m = mm
+			} else {
+				// We've found a property in the AST and such property is not of type
+				// *parser.Map, which must mean we didn't modify the AST.
+				return nil, false, fmt.Errorf("Expected property %q to be a map, found %s",
+					strings.Join(prefixes[:i+1], "."), prop.Value.Type())
+			}
+		} else if createIfNotFound {
+			mm := &parser.Map{}
+			m.Properties = append(m.Properties, &parser.Property{Name: prefix, Value: mm})
+			m = mm
+			// We've created a new node in the AST. This means the m.GetProperty(name)
+			// check after this for loop must fail, because the node we inserted is an
+			// empty parser.Map, thus this function will return |modified| is true.
+		} else {
+			return nil, false, nil
+		}
+	}
+	if prop, found := m.GetProperty(name); found {
+		// We've found a property in the AST, which must mean we didn't modify the AST.
+		return prop, false, nil
+	} else if createIfNotFound {
+		prop = &parser.Property{Name: name, Value: &parser.List{}}
+		m.Properties = append(m.Properties, prop)
+		return prop, true, nil
+	} else {
+		return nil, false, nil
+	}
+}
+
 func processParameter(value parser.Expression, paramName, moduleName string,
 	file *parser.File) (modified bool, errs []error) {
 	if _, ok := value.(*parser.Variable); ok {
@@ -232,6 +284,10 @@
 
 	flag.Parse()
 
+	if len(targetedProperty.parts) == 0 {
+		targetedProperty.Set("deps")
+	}
+
 	if flag.NArg() == 0 {
 		if *write {
 			report(fmt.Errorf("error: cannot use -w with standard input"))
@@ -318,3 +374,38 @@
 func (m *identSet) Get() interface{} {
 	return m.idents
 }
+
+type qualifiedProperty struct {
+	parts []string
+}
+
+var _ flag.Getter = (*qualifiedProperty)(nil)
+
+func (p *qualifiedProperty) name() string {
+	return p.parts[len(p.parts)-1]
+}
+
+func (p *qualifiedProperty) prefixes() []string {
+	return p.parts[:len(p.parts)-1]
+}
+
+func (p *qualifiedProperty) String() string {
+	return strings.Join(p.parts, ".")
+}
+
+func (p *qualifiedProperty) Set(s string) error {
+	p.parts = strings.Split(s, ".")
+	if len(p.parts) == 0 {
+		return fmt.Errorf("%q is not a valid property name", s)
+	}
+	for _, part := range p.parts {
+		if part == "" {
+			return fmt.Errorf("%q is not a valid property name", s)
+		}
+	}
+	return nil
+}
+
+func (p *qualifiedProperty) Get() interface{} {
+	return p.parts
+}
diff --git a/bpmodify/bpmodify_test.go b/bpmodify/bpmodify_test.go
new file mode 100644
index 0000000..a498a14
--- /dev/null
+++ b/bpmodify/bpmodify_test.go
@@ -0,0 +1,259 @@
+// Copyright 2020 Google Inc. All rights reserved.
+//
+// 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 main
+
+import (
+	"strings"
+	"testing"
+
+	"github.com/google/blueprint/parser"
+)
+
+var testCases = []struct {
+	input     string
+	output    string
+	property  string
+	addSet    string
+	removeSet string
+}{
+	{
+		`
+		cc_foo {
+			name: "foo",
+		}
+		`,
+		`
+		cc_foo {
+			name: "foo",
+			deps: ["bar"],
+		}
+		`,
+		"deps",
+		"bar",
+		"",
+	},
+	{
+		`
+		cc_foo {
+			name: "foo",
+			deps: ["bar"],
+		}
+		`,
+		`
+		cc_foo {
+			name: "foo",
+			deps: [],
+		}
+		`,
+		"deps",
+		"",
+		"bar",
+	},
+	{
+		`
+		cc_foo {
+			name: "foo",
+		}
+		`,
+		`
+		cc_foo {
+			name: "foo",
+			arch: {
+				arm: {
+					deps: [
+						"dep2",
+						"nested_dep",],
+				},
+			},
+		}
+		`,
+		"arch.arm.deps",
+		"nested_dep,dep2",
+		"",
+	},
+	{
+		`
+		cc_foo {
+			name: "foo",
+			arch: {
+				arm: {
+					deps: [
+						"dep2",
+						"nested_dep",
+					],
+				},
+			},
+		}
+		`,
+		`
+		cc_foo {
+			name: "foo",
+			arch: {
+				arm: {
+					deps: [
+					],
+				},
+			},
+		}
+		`,
+		"arch.arm.deps",
+		"",
+		"nested_dep,dep2",
+	},
+	{
+		`
+		cc_foo {
+			name: "foo",
+			arch: {
+				arm: {
+					deps: [
+						"nested_dep",
+						"dep2",
+					],
+				},
+			},
+		}
+		`,
+		`
+		cc_foo {
+			name: "foo",
+			arch: {
+				arm: {
+					deps: [
+						"nested_dep",
+						"dep2",
+					],
+				},
+			},
+		}
+		`,
+		"arch.arm.deps",
+		"dep2,dep2",
+		"",
+	},
+	{
+		`
+		cc_foo {
+			name: "foo",
+			arch: {
+				arm: {
+					deps: [
+						"nested_dep",
+						"dep2",
+					],
+				},
+			},
+		}
+		`,
+		`
+		cc_foo {
+			name: "foo",
+			arch: {
+				arm: {
+					deps: [
+						"nested_dep",
+						"dep2",
+					],
+				},
+			},
+		}
+		`,
+		"arch.arm.deps",
+		"",
+		"dep3,dep4",
+	},
+	{
+		`
+		cc_foo {
+			name: "foo",
+		}
+		`,
+		`
+		cc_foo {
+			name: "foo",
+		}
+		`,
+		"deps",
+		"",
+		"bar",
+	},
+	{
+		`
+		cc_foo {
+			name: "foo",
+			arch: {},
+		}
+		`,
+		`
+		cc_foo {
+			name: "foo",
+			arch: {},
+		}
+		`,
+		"arch.arm.deps",
+		"",
+		"dep3,dep4",
+	},
+}
+
+func simplifyModuleDefinition(def string) string {
+	var result string
+	for _, line := range strings.Split(def, "\n") {
+		result += strings.TrimSpace(line)
+	}
+	return result
+}
+
+func TestProcessModule(t *testing.T) {
+	for i, testCase := range testCases {
+		targetedProperty.Set(testCase.property)
+		addIdents.Set(testCase.addSet)
+		removeIdents.Set(testCase.removeSet)
+
+		inAst, errs := parser.ParseAndEval("", strings.NewReader(testCase.input), parser.NewScope(nil))
+		if len(errs) > 0 {
+			t.Errorf("test case %d:", i)
+			for _, err := range errs {
+				t.Errorf("  %s", err)
+			}
+			t.Errorf("failed to parse:")
+			t.Errorf("%+v", testCase)
+			continue
+		}
+
+		if inModule, ok := inAst.Defs[0].(*parser.Module); !ok {
+			t.Errorf("test case %d:", i)
+			t.Errorf("  input must only contain a single module definition: %s", testCase.input)
+			continue
+		} else {
+			_, errs := processModule(inModule, "", inAst)
+			if len(errs) > 0 {
+				t.Errorf("test case %d:", i)
+				for _, err := range errs {
+					t.Errorf("  %s", err)
+				}
+			}
+			inModuleText, _ := parser.Print(inAst)
+			inModuleString := string(inModuleText)
+			if simplifyModuleDefinition(inModuleString) != simplifyModuleDefinition(testCase.output) {
+				t.Errorf("test case %d:", i)
+				t.Errorf("expected module definition:")
+				t.Errorf("  %s", testCase.output)
+				t.Errorf("actual module definition:")
+				t.Errorf("  %s", inModuleString)
+			}
+		}
+	}
+}
diff --git a/context.go b/context.go
index adcda9b..f12856f 100644
--- a/context.go
+++ b/context.go
@@ -117,6 +117,19 @@
 	srcDir         string
 	fs             pathtools.FileSystem
 	moduleListFile string
+
+	// Mutators indexed by the ID of the provider associated with them.  Not all mutators will
+	// have providers, and not all providers will have a mutator, or if they do the mutator may
+	// not be registered in this Context.
+	providerMutators []*mutatorInfo
+
+	// The currently running mutator
+	startedMutator *mutatorInfo
+	// True for any mutators that have already run over all modules
+	finishedMutators map[*mutatorInfo]bool
+
+	// Can be set by tests to avoid invalidating Module values after mutators.
+	skipCloneModulesAfterMutators bool
 }
 
 // An Error describes a problem that was encountered that is related to a
@@ -159,22 +172,69 @@
 }
 
 type moduleAlias struct {
-	variantName       string
-	variant           variationMap
-	dependencyVariant variationMap
-	target            *moduleInfo
+	variant variant
+	target  *moduleInfo
+}
+
+func (m *moduleAlias) alias() *moduleAlias              { return m }
+func (m *moduleAlias) module() *moduleInfo              { return nil }
+func (m *moduleAlias) moduleOrAliasTarget() *moduleInfo { return m.target }
+func (m *moduleAlias) moduleOrAliasVariant() variant    { return m.variant }
+
+func (m *moduleInfo) alias() *moduleAlias              { return nil }
+func (m *moduleInfo) module() *moduleInfo              { return m }
+func (m *moduleInfo) moduleOrAliasTarget() *moduleInfo { return m }
+func (m *moduleInfo) moduleOrAliasVariant() variant    { return m.variant }
+
+type moduleOrAlias interface {
+	alias() *moduleAlias
+	module() *moduleInfo
+	moduleOrAliasTarget() *moduleInfo
+	moduleOrAliasVariant() variant
+}
+
+type modulesOrAliases []moduleOrAlias
+
+func (l modulesOrAliases) firstModule() *moduleInfo {
+	for _, moduleOrAlias := range l {
+		if m := moduleOrAlias.module(); m != nil {
+			return m
+		}
+	}
+	panic(fmt.Errorf("no first module!"))
+}
+
+func (l modulesOrAliases) lastModule() *moduleInfo {
+	for i := range l {
+		if m := l[len(l)-1-i].module(); m != nil {
+			return m
+		}
+	}
+	panic(fmt.Errorf("no last module!"))
 }
 
 type moduleGroup struct {
 	name      string
 	ninjaName string
 
-	modules []*moduleInfo
-	aliases []*moduleAlias
+	modules modulesOrAliases
 
 	namespace Namespace
 }
 
+func (group *moduleGroup) moduleOrAliasByVariantName(name string) moduleOrAlias {
+	for _, module := range group.modules {
+		if module.moduleOrAliasVariant().name == name {
+			return module
+		}
+	}
+	return nil
+}
+
+func (group *moduleGroup) moduleByVariantName(name string) *moduleInfo {
+	return group.moduleOrAliasByVariantName(name).module()
+}
+
 type moduleInfo struct {
 	// set during Parse
 	typeName          string
@@ -184,9 +244,7 @@
 	propertyPos       map[string]scanner.Position
 	createdBy         *moduleInfo
 
-	variantName       string
-	variant           variationMap
-	dependencyVariant variationMap
+	variant variant
 
 	logicModule Module
 	group       *moduleGroup
@@ -201,15 +259,28 @@
 	forwardDeps []*moduleInfo
 	directDeps  []depInfo
 
-	// used by parallelVisitAllBottomUp
+	// used by parallelVisit
 	waitingCount int
 
 	// set during each runMutator
-	splitModules []*moduleInfo
-	aliasTarget  *moduleInfo
+	splitModules modulesOrAliases
 
 	// set during PrepareBuildActions
 	actionDefs localBuildActions
+
+	providers []interface{}
+
+	startedMutator  *mutatorInfo
+	finishedMutator *mutatorInfo
+
+	startedGenerateBuildActions  bool
+	finishedGenerateBuildActions bool
+}
+
+type variant struct {
+	name                 string
+	variations           variationMap
+	dependencyVariations variationMap
 }
 
 type depInfo struct {
@@ -232,8 +303,8 @@
 
 func (module *moduleInfo) String() string {
 	s := fmt.Sprintf("module %q", module.Name())
-	if module.variantName != "" {
-		s += fmt.Sprintf(" variant %q", module.variantName)
+	if module.variant.name != "" {
+		s += fmt.Sprintf(" variant %q", module.variant.name)
 	}
 	if module.createdBy != nil {
 		s += fmt.Sprintf(" (created by %s)", module.createdBy)
@@ -273,10 +344,10 @@
 }
 
 // Compare this variationMap to another one.  Returns true if the every entry in this map
-// is either the same in the other map or doesn't exist in the other map.
-func (vm variationMap) subset(other variationMap) bool {
+// exists and has the same value in the other map.
+func (vm variationMap) subsetOf(other variationMap) bool {
 	for k, v1 := range vm {
-		if v2, ok := other[k]; ok && v1 != v2 {
+		if v2, ok := other[k]; !ok || v1 != v2 {
 			return false
 		}
 	}
@@ -313,6 +384,7 @@
 		moduleInfo:         make(map[Module]*moduleInfo),
 		globs:              make(map[string]GlobPath),
 		fs:                 pathtools.OsFs,
+		finishedMutators:   make(map[*mutatorInfo]bool),
 		ninjaBuildDir:      nil,
 		requiredNinjaMajor: 1,
 		requiredNinjaMinor: 7,
@@ -1224,15 +1296,44 @@
 	return newLogicModule, newProperties
 }
 
+func newVariant(module *moduleInfo, mutatorName string, variationName string,
+	local bool) variant {
+
+	newVariantName := module.variant.name
+	if variationName != "" {
+		if newVariantName == "" {
+			newVariantName = variationName
+		} else {
+			newVariantName += "_" + variationName
+		}
+	}
+
+	newVariations := module.variant.variations.clone()
+	if newVariations == nil {
+		newVariations = make(variationMap)
+	}
+	newVariations[mutatorName] = variationName
+
+	newDependencyVariations := module.variant.dependencyVariations.clone()
+	if !local {
+		if newDependencyVariations == nil {
+			newDependencyVariations = make(variationMap)
+		}
+		newDependencyVariations[mutatorName] = variationName
+	}
+
+	return variant{newVariantName, newVariations, newDependencyVariations}
+}
+
 func (c *Context) createVariations(origModule *moduleInfo, mutatorName string,
-	defaultVariationName *string, variationNames []string) ([]*moduleInfo, []error) {
+	defaultVariationName *string, variationNames []string, local bool) (modulesOrAliases, []error) {
 
 	if len(variationNames) == 0 {
 		panic(fmt.Errorf("mutator %q passed zero-length variation list for module %q",
 			mutatorName, origModule.Name()))
 	}
 
-	newModules := []*moduleInfo{}
+	var newModules modulesOrAliases
 
 	var errs []error
 
@@ -1249,27 +1350,13 @@
 			newLogicModule, newProperties = c.cloneLogicModule(origModule)
 		}
 
-		newVariant := origModule.variant.clone()
-		if newVariant == nil {
-			newVariant = make(variationMap)
-		}
-		newVariant[mutatorName] = variationName
-
 		m := *origModule
 		newModule := &m
-		newModule.directDeps = append([]depInfo{}, origModule.directDeps...)
+		newModule.directDeps = append([]depInfo(nil), origModule.directDeps...)
 		newModule.logicModule = newLogicModule
-		newModule.variant = newVariant
-		newModule.dependencyVariant = origModule.dependencyVariant.clone()
+		newModule.variant = newVariant(origModule, mutatorName, variationName, local)
 		newModule.properties = newProperties
-
-		if variationName != "" {
-			if newModule.variantName == "" {
-				newModule.variantName = variationName
-			} else {
-				newModule.variantName += "_" + variationName
-			}
-		}
+		newModule.providers = append([]interface{}(nil), origModule.providers...)
 
 		newModules = append(newModules, newModule)
 
@@ -1296,16 +1383,16 @@
 		if dep.module.logicModule == nil {
 			var newDep *moduleInfo
 			for _, m := range dep.module.splitModules {
-				if m.variant[mutatorName] == variationName {
-					newDep = m
+				if m.moduleOrAliasVariant().variations[mutatorName] == variationName {
+					newDep = m.moduleOrAliasTarget()
 					break
 				}
 			}
 			if newDep == nil && defaultVariationName != nil {
 				// give it a second chance; match with defaultVariationName
 				for _, m := range dep.module.splitModules {
-					if m.variant[mutatorName] == *defaultVariationName {
-						newDep = m
+					if m.moduleOrAliasVariant().variations[mutatorName] == *defaultVariationName {
+						newDep = m.moduleOrAliasTarget()
 						break
 					}
 				}
@@ -1325,10 +1412,10 @@
 	return errs
 }
 
-func (c *Context) prettyPrintVariant(variant variationMap) string {
-	names := make([]string, 0, len(variant))
+func (c *Context) prettyPrintVariant(variations variationMap) string {
+	names := make([]string, 0, len(variations))
 	for _, m := range c.variantMutatorNames {
-		if v, ok := variant[m]; ok {
+		if v, ok := variations[m]; ok {
 			names = append(names, m+":"+v)
 		}
 	}
@@ -1338,14 +1425,14 @@
 
 func (c *Context) prettyPrintGroupVariants(group *moduleGroup) string {
 	var variants []string
-	for _, mod := range group.modules {
-		variants = append(variants, c.prettyPrintVariant(mod.variant))
+	for _, moduleOrAlias := range group.modules {
+		if mod := moduleOrAlias.module(); mod != nil {
+			variants = append(variants, c.prettyPrintVariant(mod.variant.variations))
+		} else if alias := moduleOrAlias.alias(); alias != nil {
+			variants = append(variants, c.prettyPrintVariant(alias.variant.variations)+
+				"(alias to "+c.prettyPrintVariant(alias.target.variant.variations)+")")
+		}
 	}
-	for _, mod := range group.aliases {
-		variants = append(variants, c.prettyPrintVariant(mod.variant)+
-			"(alias to "+c.prettyPrintVariant(mod.target.variant)+")")
-	}
-	sort.Strings(variants)
 	return strings.Join(variants, "\n  ")
 }
 
@@ -1424,7 +1511,7 @@
 
 	group := &moduleGroup{
 		name:    name,
-		modules: []*moduleInfo{module},
+		modules: modulesOrAliases{module},
 	}
 	module.group = group
 	namespace, errs := c.nameInterface.NewModule(
@@ -1454,6 +1541,8 @@
 
 func (c *Context) resolveDependencies(ctx context.Context, config interface{}) (deps []string, errs []error) {
 	pprof.Do(ctx, pprof.Labels("blueprint", "ResolveDependencies"), func(ctx context.Context) {
+		c.initProviders()
+
 		c.liveGlobals = newLiveTracker(config)
 
 		deps, errs = c.generateSingletonBuildActions(config, c.preSingletonInfo, c.liveGlobals)
@@ -1473,7 +1562,9 @@
 		}
 		deps = append(deps, mutatorDeps...)
 
-		c.cloneModules()
+		if !c.skipCloneModulesAfterMutators {
+			c.cloneModules()
+		}
 
 		c.dependenciesReady = true
 	})
@@ -1508,43 +1599,32 @@
 	}
 }
 
-// findMatchingVariant searches the moduleGroup for a module with the same variant as module,
-// and returns the matching module, or nil if one is not found.
-func (c *Context) findMatchingVariant(module *moduleInfo, possible *moduleGroup, reverse bool) *moduleInfo {
-	if len(possible.modules) == 1 {
-		return possible.modules[0]
-	} else {
-		var variantToMatch variationMap
-		if !reverse {
-			// For forward dependency, ignore local variants by matching against
-			// dependencyVariant which doesn't have the local variants
-			variantToMatch = module.dependencyVariant
-		} else {
-			// For reverse dependency, use all the variants
-			variantToMatch = module.variant
-		}
-		for _, m := range possible.modules {
-			if m.variant.equal(variantToMatch) {
-				return m
-			}
-		}
-		for _, m := range possible.aliases {
-			if m.variant.equal(variantToMatch) {
-				return m.target
+// findExactVariantOrSingle searches the moduleGroup for a module with the same variant as module,
+// and returns the matching module, or nil if one is not found.  A group with exactly one module
+// is always considered matching.
+func findExactVariantOrSingle(module *moduleInfo, possible *moduleGroup, reverse bool) *moduleInfo {
+	found, _ := findVariant(module, possible, nil, false, reverse)
+	if found == nil {
+		for _, moduleOrAlias := range possible.modules {
+			if m := moduleOrAlias.module(); m != nil {
+				if found != nil {
+					// more than one possible match, give up
+					return nil
+				}
+				found = m
 			}
 		}
 	}
-
-	return nil
+	return found
 }
 
-func (c *Context) addDependency(module *moduleInfo, tag DependencyTag, depName string) []error {
+func (c *Context) addDependency(module *moduleInfo, tag DependencyTag, depName string) (*moduleInfo, []error) {
 	if _, ok := tag.(BaseDependencyTag); ok {
 		panic("BaseDependencyTag is not allowed to be used directly!")
 	}
 
 	if depName == module.Name() {
-		return []error{&BlueprintError{
+		return nil, []error{&BlueprintError{
 			Err: fmt.Errorf("%q depends on itself", depName),
 			Pos: module.pos,
 		}}
@@ -1552,24 +1632,24 @@
 
 	possibleDeps := c.moduleGroupFromName(depName, module.namespace())
 	if possibleDeps == nil {
-		return c.discoveredMissingDependencies(module, depName)
+		return nil, c.discoveredMissingDependencies(module, depName)
 	}
 
-	if m := c.findMatchingVariant(module, possibleDeps, false); m != nil {
+	if m := findExactVariantOrSingle(module, possibleDeps, false); m != nil {
 		module.newDirectDeps = append(module.newDirectDeps, depInfo{m, tag})
 		atomic.AddUint32(&c.depsModified, 1)
-		return nil
+		return m, nil
 	}
 
 	if c.allowMissingDependencies {
 		// Allow missing variants.
-		return c.discoveredMissingDependencies(module, depName+c.prettyPrintVariant(module.dependencyVariant))
+		return nil, c.discoveredMissingDependencies(module, depName+c.prettyPrintVariant(module.variant.dependencyVariations))
 	}
 
-	return []error{&BlueprintError{
+	return nil, []error{&BlueprintError{
 		Err: fmt.Errorf("dependency %q of %q missing variant:\n  %s\navailable variants:\n  %s",
 			depName, module.Name(),
-			c.prettyPrintVariant(module.dependencyVariant),
+			c.prettyPrintVariant(module.variant.dependencyVariations),
 			c.prettyPrintGroupVariants(possibleDeps)),
 		Pos: module.pos,
 	}}
@@ -1592,26 +1672,26 @@
 		}}
 	}
 
-	if m := c.findMatchingVariant(module, possibleDeps, true); m != nil {
+	if m := findExactVariantOrSingle(module, possibleDeps, true); m != nil {
 		return m, nil
 	}
 
 	if c.allowMissingDependencies {
 		// Allow missing variants.
-		return module, c.discoveredMissingDependencies(module, destName+c.prettyPrintVariant(module.dependencyVariant))
+		return module, c.discoveredMissingDependencies(module, destName+c.prettyPrintVariant(module.variant.dependencyVariations))
 	}
 
 	return nil, []error{&BlueprintError{
 		Err: fmt.Errorf("reverse dependency %q of %q missing variant:\n  %s\navailable variants:\n  %s",
 			destName, module.Name(),
-			c.prettyPrintVariant(module.dependencyVariant),
+			c.prettyPrintVariant(module.variant.dependencyVariations),
 			c.prettyPrintGroupVariants(possibleDeps)),
 		Pos: module.pos,
 	}}
 }
 
-func (c *Context) findVariant(module *moduleInfo, possibleDeps *moduleGroup, variations []Variation, far bool, reverse bool) (*moduleInfo, variationMap) {
-	// We can't just append variant.Variant to module.dependencyVariants.variantName and
+func findVariant(module *moduleInfo, possibleDeps *moduleGroup, variations []Variation, far bool, reverse bool) (*moduleInfo, variationMap) {
+	// We can't just append variant.Variant to module.dependencyVariant.variantName and
 	// compare the strings because the result won't be in mutator registration order.
 	// Create a new map instead, and then deep compare the maps.
 	var newVariant variationMap
@@ -1619,10 +1699,10 @@
 		if !reverse {
 			// For forward dependency, ignore local variants by matching against
 			// dependencyVariant which doesn't have the local variants
-			newVariant = module.dependencyVariant.clone()
+			newVariant = module.variant.dependencyVariations.clone()
 		} else {
 			// For reverse dependency, use all the variants
-			newVariant = module.variant.clone()
+			newVariant = module.variant.variations.clone()
 		}
 	}
 	for _, v := range variations {
@@ -1634,7 +1714,7 @@
 
 	check := func(variant variationMap) bool {
 		if far {
-			return variant.subset(newVariant)
+			return newVariant.subsetOf(variant)
 		} else {
 			return variant.equal(newVariant)
 		}
@@ -1642,43 +1722,34 @@
 
 	var foundDep *moduleInfo
 	for _, m := range possibleDeps.modules {
-		if check(m.variant) {
-			foundDep = m
+		if check(m.moduleOrAliasVariant().variations) {
+			foundDep = m.moduleOrAliasTarget()
 			break
 		}
 	}
 
-	if foundDep == nil {
-		for _, m := range possibleDeps.aliases {
-			if check(m.variant) {
-				foundDep = m.target
-				break
-			}
-		}
-	}
-
 	return foundDep, newVariant
 }
 
 func (c *Context) addVariationDependency(module *moduleInfo, variations []Variation,
-	tag DependencyTag, depName string, far bool) []error {
+	tag DependencyTag, depName string, far bool) (*moduleInfo, []error) {
 	if _, ok := tag.(BaseDependencyTag); ok {
 		panic("BaseDependencyTag is not allowed to be used directly!")
 	}
 
 	possibleDeps := c.moduleGroupFromName(depName, module.namespace())
 	if possibleDeps == nil {
-		return c.discoveredMissingDependencies(module, depName)
+		return nil, c.discoveredMissingDependencies(module, depName)
 	}
 
-	foundDep, newVariant := c.findVariant(module, possibleDeps, variations, far, false)
+	foundDep, newVariant := findVariant(module, possibleDeps, variations, far, false)
 
 	if foundDep == nil {
 		if c.allowMissingDependencies {
 			// Allow missing variants.
-			return c.discoveredMissingDependencies(module, depName+c.prettyPrintVariant(newVariant))
+			return nil, c.discoveredMissingDependencies(module, depName+c.prettyPrintVariant(newVariant))
 		}
-		return []error{&BlueprintError{
+		return nil, []error{&BlueprintError{
 			Err: fmt.Errorf("dependency %q of %q missing variant:\n  %s\navailable variants:\n  %s",
 				depName, module.Name(),
 				c.prettyPrintVariant(newVariant),
@@ -1688,7 +1759,7 @@
 	}
 
 	if module == foundDep {
-		return []error{&BlueprintError{
+		return nil, []error{&BlueprintError{
 			Err: fmt.Errorf("%q depends on itself", depName),
 			Pos: module.pos,
 		}}
@@ -1697,31 +1768,33 @@
 	// that module is earlier in the module list than this one, since we always
 	// run GenerateBuildActions in order for the variants of a module
 	if foundDep.group == module.group && beforeInModuleList(module, foundDep, module.group.modules) {
-		return []error{&BlueprintError{
+		return nil, []error{&BlueprintError{
 			Err: fmt.Errorf("%q depends on later version of itself", depName),
 			Pos: module.pos,
 		}}
 	}
 	module.newDirectDeps = append(module.newDirectDeps, depInfo{foundDep, tag})
 	atomic.AddUint32(&c.depsModified, 1)
-	return nil
+	return foundDep, nil
 }
 
 func (c *Context) addInterVariantDependency(origModule *moduleInfo, tag DependencyTag,
-	from, to Module) {
+	from, to Module) *moduleInfo {
 	if _, ok := tag.(BaseDependencyTag); ok {
 		panic("BaseDependencyTag is not allowed to be used directly!")
 	}
 
 	var fromInfo, toInfo *moduleInfo
-	for _, m := range origModule.splitModules {
-		if m.logicModule == from {
-			fromInfo = m
-		}
-		if m.logicModule == to {
-			toInfo = m
-			if fromInfo != nil {
-				panic(fmt.Errorf("%q depends on later version of itself", origModule.Name()))
+	for _, moduleOrAlias := range origModule.splitModules {
+		if m := moduleOrAlias.module(); m != nil {
+			if m.logicModule == from {
+				fromInfo = m
+			}
+			if m.logicModule == to {
+				toInfo = m
+				if fromInfo != nil {
+					panic(fmt.Errorf("%q depends on later version of itself", origModule.Name()))
+				}
 			}
 		}
 	}
@@ -1733,6 +1806,7 @@
 
 	fromInfo.newDirectDeps = append(fromInfo.newDirectDeps, depInfo{toInfo, tag})
 	atomic.AddUint32(&c.depsModified, 1)
+	return toInfo
 }
 
 // findBlueprintDescendants returns a map linking parent Blueprints files to child Blueprints files
@@ -1781,7 +1855,7 @@
 	// returns the list of modules that are waiting for this module
 	propagate(module *moduleInfo) []*moduleInfo
 	// visit modules in order
-	visit(modules []*moduleInfo, visit func(*moduleInfo) bool)
+	visit(modules []*moduleInfo, visit func(*moduleInfo, chan<- pauseSpec) bool)
 }
 
 type unorderedVisitorImpl struct{}
@@ -1794,9 +1868,9 @@
 	return nil
 }
 
-func (unorderedVisitorImpl) visit(modules []*moduleInfo, visit func(*moduleInfo) bool) {
+func (unorderedVisitorImpl) visit(modules []*moduleInfo, visit func(*moduleInfo, chan<- pauseSpec) bool) {
 	for _, module := range modules {
-		if visit(module) {
+		if visit(module, nil) {
 			return
 		}
 	}
@@ -1812,9 +1886,9 @@
 	return module.reverseDeps
 }
 
-func (bottomUpVisitorImpl) visit(modules []*moduleInfo, visit func(*moduleInfo) bool) {
+func (bottomUpVisitorImpl) visit(modules []*moduleInfo, visit func(*moduleInfo, chan<- pauseSpec) bool) {
 	for _, module := range modules {
-		if visit(module) {
+		if visit(module, nil) {
 			return
 		}
 	}
@@ -1830,10 +1904,10 @@
 	return module.forwardDeps
 }
 
-func (topDownVisitorImpl) visit(modules []*moduleInfo, visit func(*moduleInfo) bool) {
+func (topDownVisitorImpl) visit(modules []*moduleInfo, visit func(*moduleInfo, chan<- pauseSpec) bool) {
 	for i := 0; i < len(modules); i++ {
 		module := modules[len(modules)-1-i]
-		if visit(module) {
+		if visit(module, nil) {
 			return
 		}
 	}
@@ -1844,25 +1918,50 @@
 	topDownVisitor  topDownVisitorImpl
 )
 
+// pauseSpec describes a pause that a module needs to occur until another module has been visited,
+// at which point the unpause channel will be closed.
+type pauseSpec struct {
+	paused  *moduleInfo
+	until   *moduleInfo
+	unpause unpause
+}
+
+type unpause chan struct{}
+
+const parallelVisitLimit = 1000
+
 // Calls visit on each module, guaranteeing that visit is not called on a module until visit on all
-// of its dependencies has finished.
-func (c *Context) parallelVisit(order visitOrderer, visit func(group *moduleInfo) bool) {
+// of its dependencies has finished.  A visit function can write a pauseSpec to the pause channel
+// to wait for another dependency to be visited.  If a visit function returns true to cancel
+// while another visitor is paused, the paused visitor will never be resumed and its goroutine
+// will stay paused forever.
+func parallelVisit(modules []*moduleInfo, order visitOrderer, limit int,
+	visit func(module *moduleInfo, pause chan<- pauseSpec) bool) []error {
+
 	doneCh := make(chan *moduleInfo)
 	cancelCh := make(chan bool)
-	count := 0
+	pauseCh := make(chan pauseSpec)
 	cancel := false
-	var backlog []*moduleInfo
-	const limit = 1000
 
-	for _, module := range c.modulesSorted {
+	var backlog []*moduleInfo      // Visitors that are ready to start but backlogged due to limit.
+	var unpauseBacklog []pauseSpec // Visitors that are ready to unpause but backlogged due to limit.
+
+	active := 0  // Number of visitors running, not counting paused visitors.
+	visited := 0 // Number of finished visitors.
+
+	pauseMap := make(map[*moduleInfo][]pauseSpec)
+
+	for _, module := range modules {
 		module.waitingCount = order.waitCount(module)
 	}
 
-	visitOne := func(module *moduleInfo) {
-		if count < limit {
-			count++
+	// Call the visitor on a module if there are fewer active visitors than the parallelism
+	// limit, otherwise add it to the backlog.
+	startOrBacklog := func(module *moduleInfo) {
+		if active < limit {
+			active++
 			go func() {
-				ret := visit(module)
+				ret := visit(module, pauseCh)
 				if ret {
 					cancelCh <- true
 				}
@@ -1873,34 +1972,190 @@
 		}
 	}
 
-	for _, module := range c.modulesSorted {
-		if module.waitingCount == 0 {
-			visitOne(module)
+	// Unpause the already-started but paused  visitor on a module if there are fewer active
+	// visitors than the parallelism limit, otherwise add it to the backlog.
+	unpauseOrBacklog := func(pauseSpec pauseSpec) {
+		if active < limit {
+			active++
+			close(pauseSpec.unpause)
+		} else {
+			unpauseBacklog = append(unpauseBacklog, pauseSpec)
 		}
 	}
 
-	for count > 0 || len(backlog) > 0 {
+	// Start any modules in the backlog up to the parallelism limit.  Unpause paused modules first
+	// since they may already be holding resources.
+	unpauseOrStartFromBacklog := func() {
+		for active < limit && len(unpauseBacklog) > 0 {
+			unpause := unpauseBacklog[0]
+			unpauseBacklog = unpauseBacklog[1:]
+			unpauseOrBacklog(unpause)
+		}
+		for active < limit && len(backlog) > 0 {
+			toVisit := backlog[0]
+			backlog = backlog[1:]
+			startOrBacklog(toVisit)
+		}
+	}
+
+	toVisit := len(modules)
+
+	// Start or backlog any modules that are not waiting for any other modules.
+	for _, module := range modules {
+		if module.waitingCount == 0 {
+			startOrBacklog(module)
+		}
+	}
+
+	for active > 0 {
 		select {
 		case <-cancelCh:
 			cancel = true
 			backlog = nil
 		case doneModule := <-doneCh:
-			count--
+			active--
 			if !cancel {
-				for count < limit && len(backlog) > 0 {
-					toVisit := backlog[0]
-					backlog = backlog[1:]
-					visitOne(toVisit)
+				// Mark this module as done.
+				doneModule.waitingCount = -1
+				visited++
+
+				// Unpause or backlog any modules that were waiting for this one.
+				if unpauses, ok := pauseMap[doneModule]; ok {
+					delete(pauseMap, doneModule)
+					for _, unpause := range unpauses {
+						unpauseOrBacklog(unpause)
+					}
 				}
+
+				// Start any backlogged modules up to limit.
+				unpauseOrStartFromBacklog()
+
+				// Decrement waitingCount on the next modules in the tree based
+				// on propagation order, and start or backlog them if they are
+				// ready to start.
 				for _, module := range order.propagate(doneModule) {
 					module.waitingCount--
 					if module.waitingCount == 0 {
-						visitOne(module)
+						startOrBacklog(module)
 					}
 				}
 			}
+		case pauseSpec := <-pauseCh:
+			if pauseSpec.until.waitingCount == -1 {
+				// Module being paused for is already finished, resume immediately.
+				close(pauseSpec.unpause)
+			} else {
+				// Register for unpausing.
+				pauseMap[pauseSpec.until] = append(pauseMap[pauseSpec.until], pauseSpec)
+
+				// Don't count paused visitors as active so that this can't deadlock
+				// if 1000 visitors are paused simultaneously.
+				active--
+				unpauseOrStartFromBacklog()
+			}
 		}
 	}
+
+	if !cancel {
+		// Invariant check: no backlogged modules, these weren't waiting on anything except
+		// the parallelism limit so they should have run.
+		if len(backlog) > 0 {
+			panic(fmt.Errorf("parallelVisit finished with %d backlogged visitors", len(backlog)))
+		}
+
+		// Invariant check: no backlogged paused modules, these weren't waiting on anything
+		// except the parallelism limit so they should have run.
+		if len(unpauseBacklog) > 0 {
+			panic(fmt.Errorf("parallelVisit finished with %d backlogged unpaused visitors", len(unpauseBacklog)))
+		}
+
+		if len(pauseMap) > 0 {
+			// Probably a deadlock due to a newly added dependency cycle.
+			// Start from a semi-random module being paused for and perform a depth-first
+			// search for the module it is paused on, ignoring modules that are marked as
+			// done.  Note this traverses from modules to the modules that would have been
+			// unblocked when that module finished.
+			var start, end *moduleInfo
+			for _, pauseSpecs := range pauseMap {
+				for _, pauseSpec := range pauseSpecs {
+					if start == nil || start.String() > pauseSpec.paused.String() {
+						start = pauseSpec.paused
+						end = pauseSpec.until
+					}
+				}
+			}
+
+			var check func(group *moduleInfo) []*moduleInfo
+			check = func(module *moduleInfo) []*moduleInfo {
+				if module.waitingCount == -1 {
+					// This module was finished, it can't be part of a loop.
+					return nil
+				}
+				if module == end {
+					// This module is the end of the loop, start rolling up the cycle.
+					return []*moduleInfo{module}
+				}
+
+				for _, dep := range order.propagate(module) {
+					cycle := check(dep)
+					if cycle != nil {
+						return append([]*moduleInfo{module}, cycle...)
+					}
+				}
+				for _, depPauseSpec := range pauseMap[module] {
+					cycle := check(depPauseSpec.paused)
+					if cycle != nil {
+						return append([]*moduleInfo{module}, cycle...)
+					}
+				}
+
+				return nil
+			}
+
+			cycle := check(start)
+			if cycle != nil {
+				return cycleError(cycle)
+			}
+		}
+
+		// Invariant check: if there was no deadlock and no cancellation every module
+		// should have been visited.
+		if visited != toVisit {
+			panic(fmt.Errorf("parallelVisit ran %d visitors, expected %d", visited, toVisit))
+		}
+
+		// Invariant check: if there was no deadlock and no cancellation  every module
+		// should have been visited, so there is nothing left to be paused on.
+		if len(pauseMap) > 0 {
+			panic(fmt.Errorf("parallelVisit finished with %d paused visitors", len(pauseMap)))
+		}
+	}
+
+	return nil
+}
+
+func cycleError(cycle []*moduleInfo) (errs []error) {
+	// The cycle list is in reverse order because all the 'check' calls append
+	// their own module to the list.
+	errs = append(errs, &BlueprintError{
+		Err: fmt.Errorf("encountered dependency cycle:"),
+		Pos: cycle[len(cycle)-1].pos,
+	})
+
+	// Iterate backwards through the cycle list.
+	curModule := cycle[0]
+	for i := len(cycle) - 1; i >= 0; i-- {
+		nextModule := cycle[i]
+		errs = append(errs, &BlueprintError{
+			Err: fmt.Errorf("    %q depends on %q",
+				curModule.Name(),
+				nextModule.Name()),
+			Pos: curModule.pos,
+		})
+		curModule = nextModule
+	}
+
+	return errs
 }
 
 // updateDependencies recursively walks the module dependency graph and updates
@@ -1917,30 +2172,6 @@
 
 	var check func(group *moduleInfo) []*moduleInfo
 
-	cycleError := func(cycle []*moduleInfo) {
-		// We are the "start" of the cycle, so we're responsible
-		// for generating the errors.  The cycle list is in
-		// reverse order because all the 'check' calls append
-		// their own module to the list.
-		errs = append(errs, &BlueprintError{
-			Err: fmt.Errorf("encountered dependency cycle:"),
-			Pos: cycle[len(cycle)-1].pos,
-		})
-
-		// Iterate backwards through the cycle list.
-		curModule := cycle[0]
-		for i := len(cycle) - 1; i >= 0; i-- {
-			nextModule := cycle[i]
-			errs = append(errs, &BlueprintError{
-				Err: fmt.Errorf("    %q depends on %q",
-					curModule.Name(),
-					nextModule.Name()),
-				Pos: curModule.pos,
-			})
-			curModule = nextModule
-		}
-	}
-
 	check = func(module *moduleInfo) []*moduleInfo {
 		visited[module] = true
 		checking[module] = true
@@ -1953,7 +2184,9 @@
 			if dep == module {
 				break
 			}
-			deps[dep] = true
+			if depModule := dep.module(); depModule != nil {
+				deps[depModule] = true
+			}
 		}
 
 		for _, dep := range module.directDeps {
@@ -1974,10 +2207,8 @@
 				if cycle != nil {
 					if cycle[0] == module {
 						// We are the "start" of the cycle, so we're responsible
-						// for generating the errors.  The cycle list is in
-						// reverse order because all the 'check' calls append
-						// their own module to the list.
-						cycleError(cycle)
+						// for generating the errors.
+						errs = append(errs, cycleError(cycle)...)
 
 						// We can continue processing this module's children to
 						// find more cycles.  Since all the modules that were
@@ -2007,7 +2238,7 @@
 				if cycle[len(cycle)-1] != module {
 					panic("inconceivable!")
 				}
-				cycleError(cycle)
+				errs = append(errs, cycleError(cycle)...)
 			}
 		}
 	}
@@ -2195,12 +2426,12 @@
 
 	errsCh := make(chan []error)
 	globalStateCh := make(chan globalStateChange)
-	newVariationsCh := make(chan []*moduleInfo)
+	newVariationsCh := make(chan modulesOrAliases)
 	done := make(chan bool)
 
 	c.depsModified = 0
 
-	visit := func(module *moduleInfo) bool {
+	visit := func(module *moduleInfo, pause chan<- pauseSpec) bool {
 		if module.splitModules != nil {
 			panic("split module found in sorted module list")
 		}
@@ -2211,9 +2442,12 @@
 				config:  config,
 				module:  module,
 			},
-			name: mutator.name,
+			name:    mutator.name,
+			pauseCh: pause,
 		}
 
+		module.startedMutator = mutator
+
 		func() {
 			defer func() {
 				if r := recover(); r != nil {
@@ -2229,6 +2463,8 @@
 			direction.run(mutator, mctx)
 		}()
 
+		module.finishedMutator = mutator
+
 		if len(mctx.errs) > 0 {
 			errsCh <- mctx.errs
 			return true
@@ -2266,8 +2502,10 @@
 				newModules = append(newModules, globalStateChange.newModules...)
 				deps = append(deps, globalStateChange.deps...)
 			case newVariations := <-newVariationsCh:
-				for _, m := range newVariations {
-					newModuleInfo[m.logicModule] = m
+				for _, moduleOrAlias := range newVariations {
+					if m := moduleOrAlias.module(); m != nil {
+						newModuleInfo[m.logicModule] = m
+					}
 				}
 			case <-done:
 				return
@@ -2275,12 +2513,21 @@
 		}
 	}()
 
+	c.startedMutator = mutator
+
+	var visitErrs []error
 	if mutator.parallel {
-		c.parallelVisit(direction.orderer(), visit)
+		visitErrs = parallelVisit(c.modulesSorted, direction.orderer(), parallelVisitLimit, visit)
 	} else {
 		direction.orderer().visit(c.modulesSorted, visit)
 	}
 
+	if len(visitErrs) > 0 {
+		return nil, visitErrs
+	}
+
+	c.finishedMutators[mutator] = true
+
 	done <- true
 
 	if len(errs) > 0 {
@@ -2291,33 +2538,27 @@
 
 	for _, group := range c.moduleGroups {
 		for i := 0; i < len(group.modules); i++ {
-			module := group.modules[i]
+			module := group.modules[i].module()
+			if module == nil {
+				// Existing alias, skip it
+				continue
+			}
 
 			// Update module group to contain newly split variants
 			if module.splitModules != nil {
 				group.modules, i = spliceModules(group.modules, i, module.splitModules)
 			}
 
-			// Create any new aliases.
-			if module.aliasTarget != nil {
-				group.aliases = append(group.aliases, &moduleAlias{
-					variantName:       module.variantName,
-					variant:           module.variant,
-					dependencyVariant: module.dependencyVariant,
-					target:            module.aliasTarget,
-				})
-			}
-
 			// Fix up any remaining dependencies on modules that were split into variants
 			// by replacing them with the first variant
 			for j, dep := range module.directDeps {
 				if dep.module.logicModule == nil {
-					module.directDeps[j].module = dep.module.splitModules[0]
+					module.directDeps[j].module = dep.module.splitModules.firstModule()
 				}
 			}
 
 			if module.createdBy != nil && module.createdBy.logicModule == nil {
-				module.createdBy = module.createdBy.splitModules[0]
+				module.createdBy = module.createdBy.splitModules.firstModule()
 			}
 
 			// Add in any new direct dependencies that were added by the mutator
@@ -2325,17 +2566,31 @@
 			module.newDirectDeps = nil
 		}
 
-		// Forward or delete any dangling aliases.
-		for i := 0; i < len(group.aliases); i++ {
-			alias := group.aliases[i]
+		findAliasTarget := func(variant variant) *moduleInfo {
+			for _, moduleOrAlias := range group.modules {
+				if alias := moduleOrAlias.alias(); alias != nil {
+					if alias.variant.variations.equal(variant.variations) {
+						return alias.target
+					}
+				}
+			}
+			return nil
+		}
 
-			if alias.target.logicModule == nil {
-				if alias.target.aliasTarget != nil {
-					alias.target = alias.target.aliasTarget
-				} else {
-					// The alias was left dangling, remove it.
-					group.aliases = append(group.aliases[:i], group.aliases[i+1:]...)
-					i--
+		// Forward or delete any dangling aliases.
+		// Use a manual loop instead of range because len(group.modules) can
+		// change inside the loop
+		for i := 0; i < len(group.modules); i++ {
+			if alias := group.modules[i].alias(); alias != nil {
+				if alias.target.logicModule == nil {
+					newTarget := findAliasTarget(alias.target.variant)
+					if newTarget != nil {
+						alias.target = newTarget
+					} else {
+						// The alias was left dangling, remove it.
+						group.modules = append(group.modules[:i], group.modules[i+1:]...)
+						i--
+					}
 				}
 			}
 		}
@@ -2387,12 +2642,16 @@
 	ch := make(chan update)
 	doneCh := make(chan bool)
 	go func() {
-		c.parallelVisit(unorderedVisitorImpl{}, func(m *moduleInfo) bool {
-			origLogicModule := m.logicModule
-			m.logicModule, m.properties = c.cloneLogicModule(m)
-			ch <- update{origLogicModule, m}
-			return false
-		})
+		errs := parallelVisit(c.modulesSorted, unorderedVisitorImpl{}, parallelVisitLimit,
+			func(m *moduleInfo, pause chan<- pauseSpec) bool {
+				origLogicModule := m.logicModule
+				m.logicModule, m.properties = c.cloneLogicModule(m)
+				ch <- update{origLogicModule, m}
+				return false
+			})
+		if len(errs) > 0 {
+			panic(errs)
+		}
 		doneCh <- true
 	}()
 
@@ -2410,15 +2669,15 @@
 
 // Removes modules[i] from the list and inserts newModules... where it was located, returning
 // the new slice and the index of the last inserted element
-func spliceModules(modules []*moduleInfo, i int, newModules []*moduleInfo) ([]*moduleInfo, int) {
+func spliceModules(modules modulesOrAliases, i int, newModules modulesOrAliases) (modulesOrAliases, int) {
 	spliceSize := len(newModules)
 	newLen := len(modules) + spliceSize - 1
-	var dest []*moduleInfo
+	var dest modulesOrAliases
 	if cap(modules) >= len(modules)-1+len(newModules) {
 		// We can fit the splice in the existing capacity, do everything in place
 		dest = modules[:newLen]
 	} else {
-		dest = make([]*moduleInfo, newLen)
+		dest = make(modulesOrAliases, newLen)
 		copy(dest, modules[:i])
 	}
 
@@ -2456,71 +2715,77 @@
 		}
 	}()
 
-	c.parallelVisit(bottomUpVisitor, func(module *moduleInfo) bool {
+	visitErrs := parallelVisit(c.modulesSorted, bottomUpVisitor, parallelVisitLimit,
+		func(module *moduleInfo, pause chan<- pauseSpec) bool {
+			uniqueName := c.nameInterface.UniqueName(newNamespaceContext(module), module.group.name)
+			sanitizedName := toNinjaName(uniqueName)
 
-		uniqueName := c.nameInterface.UniqueName(newNamespaceContext(module), module.group.name)
-		sanitizedName := toNinjaName(uniqueName)
+			prefix := moduleNamespacePrefix(sanitizedName + "_" + module.variant.name)
 
-		prefix := moduleNamespacePrefix(sanitizedName + "_" + module.variantName)
+			// The parent scope of the moduleContext's local scope gets overridden to be that of the
+			// calling Go package on a per-call basis.  Since the initial parent scope doesn't matter we
+			// just set it to nil.
+			scope := newLocalScope(nil, prefix)
 
-		// The parent scope of the moduleContext's local scope gets overridden to be that of the
-		// calling Go package on a per-call basis.  Since the initial parent scope doesn't matter we
-		// just set it to nil.
-		scope := newLocalScope(nil, prefix)
-
-		mctx := &moduleContext{
-			baseModuleContext: baseModuleContext{
-				context: c,
-				config:  config,
-				module:  module,
-			},
-			scope:              scope,
-			handledMissingDeps: module.missingDeps == nil,
-		}
-
-		func() {
-			defer func() {
-				if r := recover(); r != nil {
-					in := fmt.Sprintf("GenerateBuildActions for %s", module)
-					if err, ok := r.(panicError); ok {
-						err.addIn(in)
-						mctx.error(err)
-					} else {
-						mctx.error(newPanicErrorf(r, in))
-					}
-				}
-			}()
-			mctx.module.logicModule.GenerateBuildActions(mctx)
-		}()
-
-		if len(mctx.errs) > 0 {
-			errsCh <- mctx.errs
-			return true
-		}
-
-		if module.missingDeps != nil && !mctx.handledMissingDeps {
-			var errs []error
-			for _, depName := range module.missingDeps {
-				errs = append(errs, c.missingDependencyError(module, depName))
+			mctx := &moduleContext{
+				baseModuleContext: baseModuleContext{
+					context: c,
+					config:  config,
+					module:  module,
+				},
+				scope:              scope,
+				handledMissingDeps: module.missingDeps == nil,
 			}
-			errsCh <- errs
-			return true
-		}
 
-		depsCh <- mctx.ninjaFileDeps
+			mctx.module.startedGenerateBuildActions = true
 
-		newErrs := c.processLocalBuildActions(&module.actionDefs,
-			&mctx.actionDefs, liveGlobals)
-		if len(newErrs) > 0 {
-			errsCh <- newErrs
-			return true
-		}
-		return false
-	})
+			func() {
+				defer func() {
+					if r := recover(); r != nil {
+						in := fmt.Sprintf("GenerateBuildActions for %s", module)
+						if err, ok := r.(panicError); ok {
+							err.addIn(in)
+							mctx.error(err)
+						} else {
+							mctx.error(newPanicErrorf(r, in))
+						}
+					}
+				}()
+				mctx.module.logicModule.GenerateBuildActions(mctx)
+			}()
+
+			mctx.module.finishedGenerateBuildActions = true
+
+			if len(mctx.errs) > 0 {
+				errsCh <- mctx.errs
+				return true
+			}
+
+			if module.missingDeps != nil && !mctx.handledMissingDeps {
+				var errs []error
+				for _, depName := range module.missingDeps {
+					errs = append(errs, c.missingDependencyError(module, depName))
+				}
+				errsCh <- errs
+				return true
+			}
+
+			depsCh <- mctx.ninjaFileDeps
+
+			newErrs := c.processLocalBuildActions(&module.actionDefs,
+				&mctx.actionDefs, liveGlobals)
+			if len(newErrs) > 0 {
+				errsCh <- newErrs
+				return true
+			}
+			return false
+		})
 
 	cancelCh <- struct{}{}
 	<-cancelCh
 
+	errs = append(errs, visitErrs...)
+
 	return deps, errs
 }
 
@@ -2675,14 +2940,8 @@
 	}
 
 	for _, m := range group.modules {
-		if module.variantName == m.variantName {
-			return m
-		}
-	}
-
-	for _, m := range group.aliases {
-		if module.variantName == m.variantName {
-			return m.target
+		if module.variant.name == m.moduleOrAliasVariant().name {
+			return m.moduleOrAliasTarget()
 		}
 	}
 
@@ -2779,8 +3038,10 @@
 	}()
 
 	for _, moduleGroup := range c.sortedModuleGroups() {
-		for _, module = range moduleGroup.modules {
-			visit(module.logicModule)
+		for _, moduleOrAlias := range moduleGroup.modules {
+			if module = moduleOrAlias.module(); module != nil {
+				visit(module.logicModule)
+			}
 		}
 	}
 }
@@ -2798,9 +3059,11 @@
 	}()
 
 	for _, moduleGroup := range c.sortedModuleGroups() {
-		for _, module := range moduleGroup.modules {
-			if pred(module.logicModule) {
-				visit(module.logicModule)
+		for _, moduleOrAlias := range moduleGroup.modules {
+			if module = moduleOrAlias.module(); module != nil {
+				if pred(module.logicModule) {
+					visit(module.logicModule)
+				}
 			}
 		}
 	}
@@ -2818,8 +3081,10 @@
 		}
 	}()
 
-	for _, variant = range module.group.modules {
-		visit(variant.logicModule)
+	for _, moduleOrAlias := range module.group.modules {
+		if variant = moduleOrAlias.module(); variant != nil {
+			visit(variant.logicModule)
+		}
 	}
 }
 
@@ -3047,18 +3312,13 @@
 	return module.Name()
 }
 
-func (c *Context) ModulePath(logicModule Module) string {
-	module := c.moduleInfo[logicModule]
-	return module.relBlueprintsFile
-}
-
 func (c *Context) ModuleDir(logicModule Module) string {
-	return filepath.Dir(c.ModulePath(logicModule))
+	return filepath.Dir(c.BlueprintFile(logicModule))
 }
 
 func (c *Context) ModuleSubDir(logicModule Module) string {
 	module := c.moduleInfo[logicModule]
-	return module.variantName
+	return module.variant.name
 }
 
 func (c *Context) ModuleType(logicModule Module) string {
@@ -3066,6 +3326,25 @@
 	return module.typeName
 }
 
+// ModuleProvider returns the value, if any, for the provider for a module.  If the value for the
+// provider was not set it returns the zero value of the type of the provider, which means the
+// return value can always be type-asserted to the type of the provider.  The return value should
+// always be considered read-only.  It panics if called before the appropriate mutator or
+// GenerateBuildActions pass for the provider on the module.  The value returned may be a deep
+// copy of the value originally passed to SetProvider.
+func (c *Context) ModuleProvider(logicModule Module, provider ProviderKey) interface{} {
+	module := c.moduleInfo[logicModule]
+	value, _ := c.provider(module, provider)
+	return value
+}
+
+// ModuleHasProvider returns true if the provider for the given module has been set.
+func (c *Context) ModuleHasProvider(logicModule Module, provider ProviderKey) bool {
+	module := c.moduleInfo[logicModule]
+	_, ok := c.provider(module, provider)
+	return ok
+}
+
 func (c *Context) BlueprintFile(logicModule Module) string {
 	module := c.moduleInfo[logicModule]
 	return module.relBlueprintsFile
@@ -3168,12 +3447,11 @@
 }
 
 func (c *Context) PrimaryModule(module Module) Module {
-	return c.moduleInfo[module].group.modules[0].logicModule
+	return c.moduleInfo[module].group.modules.firstModule().logicModule
 }
 
 func (c *Context) FinalModule(module Module) Module {
-	modules := c.moduleInfo[module].group.modules
-	return modules[len(modules)-1].logicModule
+	return c.moduleInfo[module].group.modules.lastModule().logicModule
 }
 
 func (c *Context) VisitAllModuleVariants(module Module,
@@ -3504,8 +3782,8 @@
 	iName := s[i].module.Name()
 	jName := s[j].module.Name()
 	if iName == jName {
-		iName = s[i].module.variantName
-		jName = s[j].module.variantName
+		iName = s[i].module.variant.name
+		jName = s[j].module.variant.name
 	}
 	return iName < jName
 }
@@ -3529,14 +3807,17 @@
 	iName := s.nameInterface.UniqueName(newNamespaceContext(iMod), iMod.group.name)
 	jName := s.nameInterface.UniqueName(newNamespaceContext(jMod), jMod.group.name)
 	if iName == jName {
-		iName = s.modules[i].variantName
-		jName = s.modules[j].variantName
+		iVariantName := s.modules[i].variant.name
+		jVariantName := s.modules[j].variant.name
+		if iVariantName == jVariantName {
+			panic(fmt.Sprintf("duplicate module name: %s %s: %#v and %#v\n",
+				iName, iVariantName, iMod.variant.variations, jMod.variant.variations))
+		} else {
+			return iVariantName < jVariantName
+		}
+	} else {
+		return iName < jName
 	}
-
-	if iName == jName {
-		panic(fmt.Sprintf("duplicate module name: %s: %#v and %#v\n", iName, iMod, jMod))
-	}
-	return iName < jName
 }
 
 func (s moduleSorter) Swap(i, j int) {
@@ -3581,7 +3862,7 @@
 			"typeName":  module.typeName,
 			"goFactory": factoryName,
 			"pos":       relPos,
-			"variant":   module.variantName,
+			"variant":   module.variant.name,
 		}
 		err = headerTemplate.Execute(buf, infoMap)
 		if err != nil {
@@ -3730,15 +4011,15 @@
 	return nil
 }
 
-func beforeInModuleList(a, b *moduleInfo, list []*moduleInfo) bool {
+func beforeInModuleList(a, b *moduleInfo, list modulesOrAliases) bool {
 	found := false
 	if a == b {
 		return false
 	}
 	for _, l := range list {
-		if l == a {
+		if l.module() == a {
 			found = true
-		} else if l == b {
+		} else if l.module() == b {
 			return found
 		}
 	}
diff --git a/context_test.go b/context_test.go
index 0541c06..dd5ec38 100644
--- a/context_test.go
+++ b/context_test.go
@@ -238,7 +238,7 @@
 		t.FailNow()
 	}
 
-	topModule := ctx.moduleGroupFromName("A", nil).modules[0]
+	topModule := ctx.moduleGroupFromName("A", nil).modules.firstModule()
 	outputDown, outputUp := walkDependencyGraph(ctx, topModule, false)
 	if outputDown != "BCEFG" {
 		t.Errorf("unexpected walkDeps behaviour: %s\ndown should be: BCEFG", outputDown)
@@ -319,7 +319,7 @@
 		t.FailNow()
 	}
 
-	topModule := ctx.moduleGroupFromName("A", nil).modules[0]
+	topModule := ctx.moduleGroupFromName("A", nil).modules.firstModule()
 	outputDown, outputUp := walkDependencyGraph(ctx, topModule, true)
 	if outputDown != "BCEGHFGG" {
 		t.Errorf("unexpected walkDeps behaviour: %s\ndown should be: BCEGHFGG", outputDown)
@@ -386,7 +386,7 @@
 		t.FailNow()
 	}
 
-	topModule := ctx.moduleGroupFromName("A", nil).modules[0]
+	topModule := ctx.moduleGroupFromName("A", nil).modules.firstModule()
 	outputDown, outputUp := walkDependencyGraph(ctx, topModule, true)
 	expectedDown := "BDCDE"
 	if outputDown != expectedDown {
@@ -432,10 +432,10 @@
 		t.FailNow()
 	}
 
-	a := ctx.moduleGroupFromName("A", nil).modules[0].logicModule.(*fooModule)
-	b := ctx.moduleGroupFromName("B", nil).modules[0].logicModule.(*barModule)
-	c := ctx.moduleGroupFromName("C", nil).modules[0].logicModule.(*barModule)
-	d := ctx.moduleGroupFromName("D", nil).modules[0].logicModule.(*fooModule)
+	a := ctx.moduleGroupFromName("A", nil).modules.firstModule().logicModule.(*fooModule)
+	b := ctx.moduleGroupFromName("B", nil).modules.firstModule().logicModule.(*barModule)
+	c := ctx.moduleGroupFromName("C", nil).modules.firstModule().logicModule.(*barModule)
+	d := ctx.moduleGroupFromName("D", nil).modules.firstModule().logicModule.(*fooModule)
 
 	checkDeps := func(m Module, expected string) {
 		var deps []string
@@ -606,3 +606,451 @@
 		t.Errorf("Incorrect errors; expected:\n%s\ngot:\n%s", expectedErrs, errs)
 	}
 }
+
+func Test_findVariant(t *testing.T) {
+	module := &moduleInfo{
+		variant: variant{
+			name: "normal_local",
+			variations: variationMap{
+				"normal": "normal",
+				"local":  "local",
+			},
+			dependencyVariations: variationMap{
+				"normal": "normal",
+			},
+		},
+	}
+
+	type alias struct {
+		variant variant
+		target  int
+	}
+
+	makeDependencyGroup := func(in ...interface{}) *moduleGroup {
+		group := &moduleGroup{
+			name: "dep",
+		}
+		for _, x := range in {
+			switch m := x.(type) {
+			case *moduleInfo:
+				m.group = group
+				group.modules = append(group.modules, m)
+			case alias:
+				// aliases may need to target modules that haven't been processed
+				// yet, put an empty alias in for now.
+				group.modules = append(group.modules, nil)
+			default:
+				t.Fatalf("unexpected type %T", x)
+			}
+		}
+
+		for i, x := range in {
+			switch m := x.(type) {
+			case *moduleInfo:
+				// already added in the first pass
+			case alias:
+				group.modules[i] = &moduleAlias{
+					variant: m.variant,
+					target:  group.modules[m.target].moduleOrAliasTarget(),
+				}
+			default:
+				t.Fatalf("unexpected type %T", x)
+			}
+		}
+
+		return group
+	}
+
+	tests := []struct {
+		name         string
+		possibleDeps *moduleGroup
+		variations   []Variation
+		far          bool
+		reverse      bool
+		want         string
+	}{
+		{
+			name: "AddVariationDependencies(nil)",
+			// A dependency that matches the non-local variations of the module
+			possibleDeps: makeDependencyGroup(
+				&moduleInfo{
+					variant: variant{
+						name: "normal",
+						variations: variationMap{
+							"normal": "normal",
+						},
+					},
+				},
+			),
+			variations: nil,
+			far:        false,
+			reverse:    false,
+			want:       "normal",
+		},
+		{
+			name: "AddVariationDependencies(nil) to alias",
+			// A dependency with an alias that matches the non-local variations of the module
+			possibleDeps: makeDependencyGroup(
+				alias{
+					variant: variant{
+						name: "normal",
+						variations: variationMap{
+							"normal": "normal",
+						},
+					},
+					target: 1,
+				},
+				&moduleInfo{
+					variant: variant{
+						name: "normal_a",
+						variations: variationMap{
+							"normal": "normal",
+							"a":      "a",
+						},
+					},
+				},
+			),
+			variations: nil,
+			far:        false,
+			reverse:    false,
+			want:       "normal_a",
+		},
+		{
+			name: "AddVariationDependencies(a)",
+			// A dependency with local variations
+			possibleDeps: makeDependencyGroup(
+				&moduleInfo{
+					variant: variant{
+						name: "normal_a",
+						variations: variationMap{
+							"normal": "normal",
+							"a":      "a",
+						},
+					},
+				},
+			),
+			variations: []Variation{{"a", "a"}},
+			far:        false,
+			reverse:    false,
+			want:       "normal_a",
+		},
+		{
+			name: "AddFarVariationDependencies(far)",
+			// A dependency with far variations
+			possibleDeps: makeDependencyGroup(
+				&moduleInfo{
+					variant: variant{
+						name:       "",
+						variations: nil,
+					},
+				},
+				&moduleInfo{
+					variant: variant{
+						name: "far",
+						variations: variationMap{
+							"far": "far",
+						},
+					},
+				},
+			),
+			variations: []Variation{{"far", "far"}},
+			far:        true,
+			reverse:    false,
+			want:       "far",
+		},
+		{
+			name: "AddFarVariationDependencies(far) to alias",
+			// A dependency with far variations and aliases
+			possibleDeps: makeDependencyGroup(
+				alias{
+					variant: variant{
+						name: "far",
+						variations: variationMap{
+							"far": "far",
+						},
+					},
+					target: 2,
+				},
+				&moduleInfo{
+					variant: variant{
+						name: "far_a",
+						variations: variationMap{
+							"far": "far",
+							"a":   "a",
+						},
+					},
+				},
+				&moduleInfo{
+					variant: variant{
+						name: "far_b",
+						variations: variationMap{
+							"far": "far",
+							"b":   "b",
+						},
+					},
+				},
+			),
+			variations: []Variation{{"far", "far"}},
+			far:        true,
+			reverse:    false,
+			want:       "far_b",
+		},
+		{
+			name: "AddFarVariationDependencies(far, b) to missing",
+			// A dependency with far variations and aliases
+			possibleDeps: makeDependencyGroup(
+				alias{
+					variant: variant{
+						name: "far",
+						variations: variationMap{
+							"far": "far",
+						},
+					},
+					target: 1,
+				},
+				&moduleInfo{
+					variant: variant{
+						name: "far_a",
+						variations: variationMap{
+							"far": "far",
+							"a":   "a",
+						},
+					},
+				},
+			),
+			variations: []Variation{{"far", "far"}, {"a", "b"}},
+			far:        true,
+			reverse:    false,
+			want:       "nil",
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			got, _ := findVariant(module, tt.possibleDeps, tt.variations, tt.far, tt.reverse)
+			if g, w := got == nil, tt.want == "nil"; g != w {
+				t.Fatalf("findVariant() got = %v, want %v", got, tt.want)
+			}
+			if got != nil {
+				if g, w := got.String(), fmt.Sprintf("module %q variant %q", "dep", tt.want); g != w {
+					t.Errorf("findVariant() got = %v, want %v", g, w)
+				}
+			}
+		})
+	}
+}
+
+func Test_parallelVisit(t *testing.T) {
+	moduleA := &moduleInfo{
+		group: &moduleGroup{
+			name: "A",
+		},
+	}
+	moduleB := &moduleInfo{
+		group: &moduleGroup{
+			name: "B",
+		},
+	}
+	moduleC := &moduleInfo{
+		group: &moduleGroup{
+			name: "C",
+		},
+	}
+	moduleD := &moduleInfo{
+		group: &moduleGroup{
+			name: "D",
+		},
+	}
+	moduleA.group.modules = modulesOrAliases{moduleA}
+	moduleB.group.modules = modulesOrAliases{moduleB}
+	moduleC.group.modules = modulesOrAliases{moduleC}
+	moduleD.group.modules = modulesOrAliases{moduleD}
+
+	addDep := func(from, to *moduleInfo) {
+		from.directDeps = append(from.directDeps, depInfo{to, nil})
+		from.forwardDeps = append(from.forwardDeps, to)
+		to.reverseDeps = append(to.reverseDeps, from)
+	}
+
+	// A depends on B, B depends on C.  Nothing depends on D, and D doesn't depend on anything.
+	addDep(moduleA, moduleB)
+	addDep(moduleB, moduleC)
+
+	t.Run("no modules", func(t *testing.T) {
+		errs := parallelVisit(nil, bottomUpVisitorImpl{}, 1,
+			func(module *moduleInfo, pause chan<- pauseSpec) bool {
+				panic("unexpected call to visitor")
+			})
+		if errs != nil {
+			t.Errorf("expected no errors, got %q", errs)
+		}
+	})
+	t.Run("bottom up", func(t *testing.T) {
+		order := ""
+		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 1,
+			func(module *moduleInfo, pause chan<- pauseSpec) bool {
+				order += module.group.name
+				return false
+			})
+		if errs != nil {
+			t.Errorf("expected no errors, got %q", errs)
+		}
+		if g, w := order, "CBA"; g != w {
+			t.Errorf("expected order %q, got %q", w, g)
+		}
+	})
+	t.Run("pause", func(t *testing.T) {
+		order := ""
+		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC, moduleD}, bottomUpVisitorImpl{}, 1,
+			func(module *moduleInfo, pause chan<- pauseSpec) bool {
+				if module == moduleC {
+					// Pause module C on module D
+					unpause := make(chan struct{})
+					pause <- pauseSpec{moduleC, moduleD, unpause}
+					<-unpause
+				}
+				order += module.group.name
+				return false
+			})
+		if errs != nil {
+			t.Errorf("expected no errors, got %q", errs)
+		}
+		if g, w := order, "DCBA"; g != w {
+			t.Errorf("expected order %q, got %q", w, g)
+		}
+	})
+	t.Run("cancel", func(t *testing.T) {
+		order := ""
+		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 1,
+			func(module *moduleInfo, pause chan<- pauseSpec) bool {
+				order += module.group.name
+				// Cancel in module B
+				return module == moduleB
+			})
+		if errs != nil {
+			t.Errorf("expected no errors, got %q", errs)
+		}
+		if g, w := order, "CB"; g != w {
+			t.Errorf("expected order %q, got %q", w, g)
+		}
+	})
+	t.Run("pause and cancel", func(t *testing.T) {
+		order := ""
+		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC, moduleD}, bottomUpVisitorImpl{}, 1,
+			func(module *moduleInfo, pause chan<- pauseSpec) bool {
+				if module == moduleC {
+					// Pause module C on module D
+					unpause := make(chan struct{})
+					pause <- pauseSpec{moduleC, moduleD, unpause}
+					<-unpause
+				}
+				order += module.group.name
+				// Cancel in module D
+				return module == moduleD
+			})
+		if errs != nil {
+			t.Errorf("expected no errors, got %q", errs)
+		}
+		if g, w := order, "D"; g != w {
+			t.Errorf("expected order %q, got %q", w, g)
+		}
+	})
+	t.Run("parallel", func(t *testing.T) {
+		order := ""
+		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 3,
+			func(module *moduleInfo, pause chan<- pauseSpec) bool {
+				order += module.group.name
+				return false
+			})
+		if errs != nil {
+			t.Errorf("expected no errors, got %q", errs)
+		}
+		if g, w := order, "CBA"; g != w {
+			t.Errorf("expected order %q, got %q", w, g)
+		}
+	})
+	t.Run("pause existing", func(t *testing.T) {
+		order := ""
+		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 3,
+			func(module *moduleInfo, pause chan<- pauseSpec) bool {
+				if module == moduleA {
+					// Pause module A on module B (an existing dependency)
+					unpause := make(chan struct{})
+					pause <- pauseSpec{moduleA, moduleB, unpause}
+					<-unpause
+				}
+				order += module.group.name
+				return false
+			})
+		if errs != nil {
+			t.Errorf("expected no errors, got %q", errs)
+		}
+		if g, w := order, "CBA"; g != w {
+			t.Errorf("expected order %q, got %q", w, g)
+		}
+	})
+	t.Run("cycle", func(t *testing.T) {
+		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 3,
+			func(module *moduleInfo, pause chan<- pauseSpec) bool {
+				if module == moduleC {
+					// Pause module C on module A (a dependency cycle)
+					unpause := make(chan struct{})
+					pause <- pauseSpec{moduleC, moduleA, unpause}
+					<-unpause
+				}
+				return false
+			})
+		want := []string{
+			`encountered dependency cycle`,
+			`"C" depends on "A"`,
+			`"A" depends on "B"`,
+			`"B" depends on "C"`,
+		}
+		for i := range want {
+			if len(errs) <= i {
+				t.Errorf("missing error %s", want[i])
+			} else if !strings.Contains(errs[i].Error(), want[i]) {
+				t.Errorf("expected error %s, got %s", want[i], errs[i])
+			}
+		}
+		if len(errs) > len(want) {
+			for _, err := range errs[len(want):] {
+				t.Errorf("unexpected error %s", err.Error())
+			}
+		}
+	})
+	t.Run("pause cycle", func(t *testing.T) {
+		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC, moduleD}, bottomUpVisitorImpl{}, 3,
+			func(module *moduleInfo, pause chan<- pauseSpec) bool {
+				if module == moduleC {
+					// Pause module C on module D
+					unpause := make(chan struct{})
+					pause <- pauseSpec{moduleC, moduleD, unpause}
+					<-unpause
+				}
+				if module == moduleD {
+					// Pause module D on module C (a pause cycle)
+					unpause := make(chan struct{})
+					pause <- pauseSpec{moduleD, moduleC, unpause}
+					<-unpause
+				}
+				return false
+			})
+		want := []string{
+			`encountered dependency cycle`,
+			`"C" depends on "D"`,
+			`"D" depends on "C"`,
+		}
+		for i := range want {
+			if len(errs) <= i {
+				t.Errorf("missing error %s", want[i])
+			} else if !strings.Contains(errs[i].Error(), want[i]) {
+				t.Errorf("expected error %s, got %s", want[i], errs[i])
+			}
+		}
+		if len(errs) > len(want) {
+			for _, err := range errs[len(want):] {
+				t.Errorf("unexpected error %s", err.Error())
+			}
+		}
+	})
+}
diff --git a/live_tracker.go b/live_tracker.go
index 40e1930..1d48e58 100644
--- a/live_tracker.go
+++ b/live_tracker.go
@@ -68,6 +68,11 @@
 		return err
 	}
 
+	err = l.addNinjaStringListDeps(def.Validations)
+	if err != nil {
+		return err
+	}
+
 	for _, value := range def.Variables {
 		err = l.addNinjaStringDeps(value)
 		if err != nil {
diff --git a/module_ctx.go b/module_ctx.go
index 9de2676..d0f8c39 100644
--- a/module_ctx.go
+++ b/module_ctx.go
@@ -246,6 +246,24 @@
 	// invalidated by future mutators.
 	WalkDeps(visit func(Module, Module) bool)
 
+	// PrimaryModule returns the first variant of the current module.  Variants of a module are always visited in
+	// order by mutators and GenerateBuildActions, so the data created by the current mutator can be read from the
+	// Module returned by PrimaryModule without data races.  This can be used to perform singleton actions that are
+	// only done once for all variants of a module.
+	PrimaryModule() Module
+
+	// FinalModule returns the last variant of the current module.  Variants of a module are always visited in
+	// order by mutators and GenerateBuildActions, so the data created by the current mutator can be read from all
+	// variants using VisitAllModuleVariants if the current module == FinalModule().  This can be used to perform
+	// singleton actions that are only done once for all variants of a module.
+	FinalModule() Module
+
+	// VisitAllModuleVariants calls visit for each variant of the current module.  Variants of a module are always
+	// visited in order by mutators and GenerateBuildActions, so the data created by the current mutator can be read
+	// from all variants if the current module == FinalModule().  Otherwise, care must be taken to not access any
+	// data modified by the current mutator.
+	VisitAllModuleVariants(visit func(Module))
+
 	// OtherModuleName returns the name of another Module.  See BaseModuleContext.ModuleName for more information.
 	// It is intended for use inside the visit functions of Visit* and WalkDeps.
 	OtherModuleName(m Module) string
@@ -288,6 +306,31 @@
 	// other words, it checks for the module AddReverseDependency would add a
 	// dependency on with the same argument.
 	OtherModuleReverseDependencyVariantExists(name string) bool
+
+	// OtherModuleProvider returns the value for a provider for the given module.  If the value is
+	// not set it returns the zero value of the type of the provider, so the return value can always
+	// be type asserted to the type of the provider.  The value returned may be a deep copy of the
+	// value originally passed to SetProvider.
+	OtherModuleProvider(m Module, provider ProviderKey) interface{}
+
+	// OtherModuleHasProvider returns true if the provider for the given module has been set.
+	OtherModuleHasProvider(m Module, provider ProviderKey) bool
+
+	// Provider returns the value for a provider for the current module.  If the value is
+	// not set it returns the zero value of the type of the provider, so the return value can always
+	// be type asserted to the type of the provider.  It panics if called before the appropriate
+	// mutator or GenerateBuildActions pass for the provider.  The value returned may be a deep
+	// copy of the value originally passed to SetProvider.
+	Provider(provider ProviderKey) interface{}
+
+	// HasProvider returns true if the provider for the current module has been set.
+	HasProvider(provider ProviderKey) bool
+
+	// SetProvider sets the value for a provider for the current module.  It panics if not called
+	// during the appropriate mutator or GenerateBuildActions pass for the provider, if the value
+	// is not of the appropriate type, or if the value has already been set.  The value should not
+	// be modified after being passed to SetProvider.
+	SetProvider(provider ProviderKey, value interface{})
 }
 
 type DynamicDependerModuleContext BottomUpMutatorContext
@@ -309,24 +352,6 @@
 	// Build creates a new ninja build statement.
 	Build(pctx PackageContext, params BuildParams)
 
-	// PrimaryModule returns the first variant of the current module.  Variants of a module are always visited in
-	// order by mutators and GenerateBuildActions, so the data created by the current mutator can be read from the
-	// Module returned by PrimaryModule without data races.  This can be used to perform singleton actions that are
-	// only done once for all variants of a module.
-	PrimaryModule() Module
-
-	// FinalModule returns the last variant of the current module.  Variants of a module are always visited in
-	// order by mutators and GenerateBuildActions, so the data created by the current mutator can be read from all
-	// variants using VisitAllModuleVariants if the current module == FinalModule().  This can be used to perform
-	// singleton actions that are only done once for all variants of a module.
-	FinalModule() Module
-
-	// VisitAllModuleVariants calls visit for each variant of the current module.  Variants of a module are always
-	// visited in order by mutators and GenerateBuildActions, so the data created by the current mutator can be read
-	// from all variants if the current module == FinalModule().  Otherwise, care must be taken to not access any
-	// data modified by the current mutator.
-	VisitAllModuleVariants(visit func(Module))
-
 	// GetMissingDependencies returns the list of dependencies that were passed to AddDependencies or related methods,
 	// but do not exist.  It can be used with Context.SetAllowMissingDependencies to allow the primary builder to
 	// handle missing dependencies on its own instead of having Blueprint treat them as an error.
@@ -464,7 +489,7 @@
 
 func (m *baseModuleContext) OtherModuleSubDir(logicModule Module) string {
 	module := m.context.moduleInfo[logicModule]
-	return module.variantName
+	return module.variant.name
 }
 
 func (m *baseModuleContext) OtherModuleType(logicModule Module) string {
@@ -510,7 +535,7 @@
 	if possibleDeps == nil {
 		return false
 	}
-	found, _ := m.context.findVariant(m.module, possibleDeps, variations, false, false)
+	found, _ := findVariant(m.module, possibleDeps, variations, false, false)
 	return found != nil
 }
 
@@ -519,10 +544,36 @@
 	if possibleDeps == nil {
 		return false
 	}
-	found, _ := m.context.findVariant(m.module, possibleDeps, nil, false, true)
+	found, _ := findVariant(m.module, possibleDeps, nil, false, true)
 	return found != nil
 }
 
+func (m *baseModuleContext) OtherModuleProvider(logicModule Module, provider ProviderKey) interface{} {
+	module := m.context.moduleInfo[logicModule]
+	value, _ := m.context.provider(module, provider)
+	return value
+}
+
+func (m *baseModuleContext) OtherModuleHasProvider(logicModule Module, provider ProviderKey) bool {
+	module := m.context.moduleInfo[logicModule]
+	_, ok := m.context.provider(module, provider)
+	return ok
+}
+
+func (m *baseModuleContext) Provider(provider ProviderKey) interface{} {
+	value, _ := m.context.provider(m.module, provider)
+	return value
+}
+
+func (m *baseModuleContext) HasProvider(provider ProviderKey) bool {
+	_, ok := m.context.provider(m.module, provider)
+	return ok
+}
+
+func (m *baseModuleContext) SetProvider(provider ProviderKey, value interface{}) {
+	m.context.setProvider(m.module, provider, value)
+}
+
 func (m *baseModuleContext) GetDirectDep(name string) (Module, DependencyTag) {
 	for _, dep := range m.module.directDeps {
 		if dep.module.Name() == name {
@@ -642,6 +693,18 @@
 	m.visitingDep = depInfo{}
 }
 
+func (m *baseModuleContext) PrimaryModule() Module {
+	return m.module.group.modules.firstModule().logicModule
+}
+
+func (m *baseModuleContext) FinalModule() Module {
+	return m.module.group.modules.lastModule().logicModule
+}
+
+func (m *baseModuleContext) VisitAllModuleVariants(visit func(Module)) {
+	m.context.visitAllModuleVariants(m.module, visit)
+}
+
 func (m *baseModuleContext) AddNinjaFileDeps(deps ...string) {
 	m.ninjaFileDeps = append(m.ninjaFileDeps, deps...)
 }
@@ -655,7 +718,7 @@
 }
 
 func (m *moduleContext) ModuleSubDir() string {
-	return m.module.variantName
+	return m.module.variant.name
 }
 
 func (m *moduleContext) Variable(pctx PackageContext, name, value string) {
@@ -695,18 +758,6 @@
 	m.actionDefs.buildDefs = append(m.actionDefs.buildDefs, def)
 }
 
-func (m *moduleContext) PrimaryModule() Module {
-	return m.module.group.modules[0].logicModule
-}
-
-func (m *moduleContext) FinalModule() Module {
-	return m.module.group.modules[len(m.module.group.modules)-1].logicModule
-}
-
-func (m *moduleContext) VisitAllModuleVariants(visit func(Module)) {
-	m.context.visitAllModuleVariants(m.module, visit)
-}
-
 func (m *moduleContext) GetMissingDependencies() []string {
 	m.handledMissingDeps = true
 	return m.module.missingDeps
@@ -722,9 +773,10 @@
 	reverseDeps      []reverseDep
 	rename           []rename
 	replace          []replace
-	newVariations    []*moduleInfo // new variants of existing modules
-	newModules       []*moduleInfo // brand new modules
+	newVariations    modulesOrAliases // new variants of existing modules
+	newModules       []*moduleInfo    // brand new modules
 	defaultVariation *string
+	pauseCh          chan<- pauseSpec
 }
 
 type BaseMutatorContext interface {
@@ -775,10 +827,15 @@
 type BottomUpMutatorContext interface {
 	BaseMutatorContext
 
-	// AddDependency adds a dependency to the given module.
-	// Does not affect the ordering of the current mutator pass, but will be ordered
-	// correctly for all future mutator passes.
-	AddDependency(module Module, tag DependencyTag, name ...string)
+	// AddDependency adds a dependency to the given module.  It returns a slice of modules for each
+	// dependency (some entries may be nil).  Does not affect the ordering of the current mutator
+	// pass, but will be ordered correctly for all future mutator passes.
+	//
+	// If the mutator is parallel (see MutatorHandle.Parallel), this method will pause until the
+	// new dependencies have had the current mutator called on them.  If the mutator is not
+	// parallel this method does not affect the ordering of the current mutator pass, but will
+	// be ordered correctly for all future mutator passes.
+	AddDependency(module Module, tag DependencyTag, name ...string) []Module
 
 	// AddReverseDependency adds a dependency from the destination to the given module.
 	// Does not affect the ordering of the current mutator pass, but will be ordered
@@ -818,19 +875,30 @@
 	SetDefaultDependencyVariation(*string)
 
 	// AddVariationDependencies adds deps as dependencies of the current module, but uses the variations
-	// argument to select which variant of the dependency to use.  A variant of the dependency must
-	// exist that matches the all of the non-local variations of the current module, plus the variations
-	// argument.
-	AddVariationDependencies([]Variation, DependencyTag, ...string)
+	// argument to select which variant of the dependency to use.  It returns a slice of modules for
+	// each dependency (some entries may be nil).  A variant of the dependency must exist that matches
+	// the all of the non-local variations of the current module, plus the variations argument.
+	//
+	// If the mutator is parallel (see MutatorHandle.Parallel), this method will pause until the
+	// new dependencies have had the current mutator called on them.  If the mutator is not
+	// parallel this method does not affect the ordering of the current mutator pass, but will
+	// be ordered correctly for all future mutator passes.
+	AddVariationDependencies([]Variation, DependencyTag, ...string) []Module
 
 	// AddFarVariationDependencies adds deps as dependencies of the current module, but uses the
-	// variations argument to select which variant of the dependency to use.  A variant of the
-	// dependency must exist that matches the variations argument, but may also have other variations.
+	// variations argument to select which variant of the dependency to use.  It returns a slice of
+	// modules for each dependency (some entries may be nil).  A variant of the dependency must
+	// exist that matches the variations argument, but may also have other variations.
 	// For any unspecified variation the first variant will be used.
 	//
 	// Unlike AddVariationDependencies, the variations of the current module are ignored - the
 	// dependency only needs to match the supplied variations.
-	AddFarVariationDependencies([]Variation, DependencyTag, ...string)
+	//
+	// If the mutator is parallel (see MutatorHandle.Parallel), this method will pause until the
+	// new dependencies have had the current mutator called on them.  If the mutator is not
+	// parallel this method does not affect the ordering of the current mutator pass, but will
+	// be ordered correctly for all future mutator passes.
+	AddFarVariationDependencies([]Variation, DependencyTag, ...string) []Module
 
 	// AddInterVariantDependency adds a dependency between two variants of the same module.  Variants are always
 	// ordered in the same orderas they were listed in CreateVariations, and AddInterVariantDependency does not change
@@ -850,12 +918,29 @@
 	// Replacements don't take effect until after the mutator pass is finished.
 	ReplaceDependenciesIf(string, ReplaceDependencyPredicate)
 
-	// AliasVariation takes a variationName that was passed to CreateVariations for this module, and creates an
-	// alias from the current variant to the new variant.  The alias will be valid until the next time a mutator
-	// calls CreateVariations or CreateLocalVariations on this module without also calling AliasVariation.  The
-	// alias can be used to add dependencies on the newly created variant using the variant map from before
-	// CreateVariations was run.
+	// AliasVariation takes a variationName that was passed to CreateVariations for this module,
+	// and creates an alias from the current variant (before the mutator has run) to the new
+	// variant.  The alias will be valid until the next time a mutator calls CreateVariations or
+	// CreateLocalVariations on this module without also calling AliasVariation.  The alias can
+	// be used to add dependencies on the newly created variant using the variant map from
+	// before CreateVariations was run.
 	AliasVariation(variationName string)
+
+	// CreateAliasVariation takes a toVariationName that was passed to CreateVariations for this
+	// module, and creates an alias from a new fromVariationName variant the toVariationName
+	// variant.  The alias will be valid until the next time a mutator calls CreateVariations or
+	// CreateLocalVariations on this module without also calling AliasVariation.  The alias can
+	// be used to add dependencies on the toVariationName variant using the fromVariationName
+	// variant.
+	CreateAliasVariation(fromVariationName, toVariationName string)
+
+	// SetVariationProvider sets the value for a provider for the given newly created variant of
+	// the current module, i.e. one of the Modules returned by CreateVariations..  It panics if
+	// not called during the appropriate mutator or GenerateBuildActions pass for the provider,
+	// if the value is not of the appropriate type, or if the module is not a newly created
+	// variant of the current module.  The value should not be modified after being passed to
+	// SetVariationProvider.
+	SetVariationProvider(module Module, provider ProviderKey, value interface{})
 }
 
 // A Mutator function is called for each Module, and can use
@@ -899,21 +984,30 @@
 	return mctx.createVariations(variationNames, true)
 }
 
+func (mctx *mutatorContext) SetVariationProvider(module Module, provider ProviderKey, value interface{}) {
+	for _, variant := range mctx.newVariations {
+		if m := variant.module(); m != nil && m.logicModule == module {
+			mctx.context.setProvider(m, provider, value)
+			return
+		}
+	}
+	panic(fmt.Errorf("module %q is not a newly created variant of %q", module, mctx.module))
+}
+
+type pendingAlias struct {
+	fromVariant variant
+	target      *moduleInfo
+}
+
 func (mctx *mutatorContext) createVariations(variationNames []string, local bool) []Module {
 	ret := []Module{}
-	modules, errs := mctx.context.createVariations(mctx.module, mctx.name, mctx.defaultVariation, variationNames)
+	modules, errs := mctx.context.createVariations(mctx.module, mctx.name, mctx.defaultVariation, variationNames, local)
 	if len(errs) > 0 {
 		mctx.errs = append(mctx.errs, errs...)
 	}
 
-	for i, module := range modules {
-		ret = append(ret, module.logicModule)
-		if !local {
-			if module.dependencyVariant == nil {
-				module.dependencyVariant = make(variationMap)
-			}
-			module.dependencyVariant[mctx.name] = variationNames[i]
-		}
+	for _, module := range modules {
+		ret = append(ret, module.module().logicModule)
 	}
 
 	if mctx.newVariations != nil {
@@ -929,24 +1023,65 @@
 }
 
 func (mctx *mutatorContext) AliasVariation(variationName string) {
-	if mctx.module.aliasTarget != nil {
-		panic(fmt.Errorf("AliasVariation already called"))
+	for _, moduleOrAlias := range mctx.module.splitModules {
+		if alias := moduleOrAlias.alias(); alias != nil {
+			if alias.variant.variations.equal(mctx.module.variant.variations) {
+				panic(fmt.Errorf("AliasVariation already called"))
+			}
+		}
 	}
 
 	for _, variant := range mctx.newVariations {
-		if variant.variant[mctx.name] == variationName {
-			mctx.module.aliasTarget = variant
+		if variant.moduleOrAliasVariant().variations[mctx.name] == variationName {
+			alias := &moduleAlias{
+				variant: mctx.module.variant,
+				target:  variant.moduleOrAliasTarget(),
+			}
+			// Prepend the alias so that AddFarVariationDependencies subset match matches
+			// the alias before matching the first variation.
+			mctx.module.splitModules = append(modulesOrAliases{alias}, mctx.module.splitModules...)
 			return
 		}
 	}
 
 	var foundVariations []string
 	for _, variant := range mctx.newVariations {
-		foundVariations = append(foundVariations, variant.variant[mctx.name])
+		foundVariations = append(foundVariations, variant.moduleOrAliasVariant().variations[mctx.name])
 	}
 	panic(fmt.Errorf("no %q variation in module variations %q", variationName, foundVariations))
 }
 
+func (mctx *mutatorContext) CreateAliasVariation(aliasVariationName, targetVariationName string) {
+	newVariant := newVariant(mctx.module, mctx.name, aliasVariationName, false)
+
+	for _, moduleOrAlias := range mctx.module.splitModules {
+		if moduleOrAlias.moduleOrAliasVariant().variations.equal(newVariant.variations) {
+			if alias := moduleOrAlias.alias(); alias != nil {
+				panic(fmt.Errorf("can't alias %q to %q, already aliased to %q", aliasVariationName, targetVariationName, alias.target.variant.name))
+			} else {
+				panic(fmt.Errorf("can't alias %q to %q, there is already a variant with that name", aliasVariationName, targetVariationName))
+			}
+		}
+	}
+
+	for _, variant := range mctx.newVariations {
+		if variant.moduleOrAliasVariant().variations[mctx.name] == targetVariationName {
+			// Append the alias here so that it comes after any aliases created by AliasVariation.
+			mctx.module.splitModules = append(mctx.module.splitModules, &moduleAlias{
+				variant: newVariant,
+				target:  variant.moduleOrAliasTarget(),
+			})
+			return
+		}
+	}
+
+	var foundVariations []string
+	for _, variant := range mctx.newVariations {
+		foundVariations = append(foundVariations, variant.moduleOrAliasVariant().variations[mctx.name])
+	}
+	panic(fmt.Errorf("no %q variation in module variations %q", targetVariationName, foundVariations))
+}
+
 func (mctx *mutatorContext) SetDependencyVariation(variationName string) {
 	mctx.context.convertDepsToVariation(mctx.module, mctx.name, variationName, nil)
 }
@@ -959,14 +1094,17 @@
 	return mctx.module.logicModule
 }
 
-func (mctx *mutatorContext) AddDependency(module Module, tag DependencyTag, deps ...string) {
+func (mctx *mutatorContext) AddDependency(module Module, tag DependencyTag, deps ...string) []Module {
+	depInfos := make([]Module, 0, len(deps))
 	for _, dep := range deps {
 		modInfo := mctx.context.moduleInfo[module]
-		errs := mctx.context.addDependency(modInfo, tag, dep)
+		depInfo, errs := mctx.context.addDependency(modInfo, tag, dep)
 		if len(errs) > 0 {
 			mctx.errs = append(mctx.errs, errs...)
 		}
+		depInfos = append(depInfos, maybeLogicModule(depInfo))
 	}
+	return depInfos
 }
 
 func (mctx *mutatorContext) AddReverseDependency(module Module, tag DependencyTag, destName string) {
@@ -987,25 +1125,31 @@
 }
 
 func (mctx *mutatorContext) AddVariationDependencies(variations []Variation, tag DependencyTag,
-	deps ...string) {
+	deps ...string) []Module {
 
+	depInfos := make([]Module, 0, len(deps))
 	for _, dep := range deps {
-		errs := mctx.context.addVariationDependency(mctx.module, variations, tag, dep, false)
+		depInfo, errs := mctx.context.addVariationDependency(mctx.module, variations, tag, dep, false)
 		if len(errs) > 0 {
 			mctx.errs = append(mctx.errs, errs...)
 		}
+		depInfos = append(depInfos, maybeLogicModule(depInfo))
 	}
+	return depInfos
 }
 
 func (mctx *mutatorContext) AddFarVariationDependencies(variations []Variation, tag DependencyTag,
-	deps ...string) {
+	deps ...string) []Module {
 
+	depInfos := make([]Module, 0, len(deps))
 	for _, dep := range deps {
-		errs := mctx.context.addVariationDependency(mctx.module, variations, tag, dep, true)
+		depInfo, errs := mctx.context.addVariationDependency(mctx.module, variations, tag, dep, true)
 		if len(errs) > 0 {
 			mctx.errs = append(mctx.errs, errs...)
 		}
+		depInfos = append(depInfos, maybeLogicModule(depInfo))
 	}
+	return depInfos
 }
 
 func (mctx *mutatorContext) AddInterVariantDependency(tag DependencyTag, from, to Module) {
@@ -1023,7 +1167,7 @@
 
 	if target == nil {
 		panic(fmt.Errorf("ReplaceDependencies could not find identical variant %q for module %q",
-			mctx.module.variantName, name))
+			mctx.module.variant.name, name))
 	}
 
 	mctx.replace = append(mctx.replace, replace{target, mctx.module, predicate})
@@ -1053,6 +1197,23 @@
 	return module.logicModule
 }
 
+// pause waits until the given dependency has been visited by the mutator's parallelVisit call.
+// It returns true if the pause was supported, false if the pause was not supported and did not
+// occur, which will happen when the mutator is not parallelizable.
+func (mctx *mutatorContext) pause(dep *moduleInfo) bool {
+	if mctx.pauseCh != nil {
+		unpause := make(unpause)
+		mctx.pauseCh <- pauseSpec{
+			paused:  mctx.module,
+			until:   dep,
+			unpause: unpause,
+		}
+		<-unpause
+		return true
+	}
+	return false
+}
+
 // SimpleName is an embeddable object to implement the ModuleContext.Name method using a property
 // called "name".  Modules that embed it must also add SimpleName.Properties to their property
 // structure list.
@@ -1172,9 +1333,8 @@
 
 // Check the syntax of a generated blueprint file.
 //
-// This is intended to perform a quick sanity check for generated blueprint
-// code to ensure that it is syntactically correct, where syntactically correct
-// means:
+// This is intended to perform a quick syntactic check for generated blueprint
+// code, where syntactically correct means:
 // * No variable definitions.
 // * Valid module types.
 // * Valid property names.
@@ -1210,3 +1370,11 @@
 
 	return errs
 }
+
+func maybeLogicModule(module *moduleInfo) Module {
+	if module != nil {
+		return module.logicModule
+	} else {
+		return nil
+	}
+}
diff --git a/module_ctx_test.go b/module_ctx_test.go
index e98ae82..62a89c1 100644
--- a/module_ctx_test.go
+++ b/module_ctx_test.go
@@ -32,7 +32,7 @@
 func (f *moduleCtxTestModule) GenerateBuildActions(ModuleContext) {
 }
 
-func noCreateAliasMutator(name string) func(ctx BottomUpMutatorContext) {
+func noAliasMutator(name string) func(ctx BottomUpMutatorContext) {
 	return func(ctx BottomUpMutatorContext) {
 		if ctx.ModuleName() == name {
 			ctx.CreateVariations("a", "b")
@@ -40,11 +40,22 @@
 	}
 }
 
+func aliasMutator(name string) func(ctx BottomUpMutatorContext) {
+	return func(ctx BottomUpMutatorContext) {
+		if ctx.ModuleName() == name {
+			ctx.CreateVariations("a", "b")
+			ctx.AliasVariation("b")
+		}
+	}
+}
+
 func createAliasMutator(name string) func(ctx BottomUpMutatorContext) {
 	return func(ctx BottomUpMutatorContext) {
 		if ctx.ModuleName() == name {
 			ctx.CreateVariations("a", "b")
-			ctx.AliasVariation("b")
+			ctx.CreateAliasVariation("c", "a")
+			ctx.CreateAliasVariation("d", "b")
+			ctx.CreateAliasVariation("e", "a")
 		}
 	}
 }
@@ -57,7 +68,7 @@
 	}
 }
 
-func TestAliases(t *testing.T) {
+func TestAliasVariation(t *testing.T) {
 	runWithFailures := func(ctx *Context, expectedErr string) {
 		t.Helper()
 		bp := `
@@ -115,17 +126,13 @@
 		// Tests a dependency from "foo" to "bar" variant "b" through alias "".
 		ctx := NewContext()
 		ctx.RegisterModuleType("test", newModuleCtxTestModule)
-		ctx.RegisterBottomUpMutator("1", createAliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("1", aliasMutator("bar"))
 		ctx.RegisterBottomUpMutator("2", addVariantDepsMutator(nil, nil, "foo", "bar"))
 
 		run(ctx)
 
-		foo := ctx.moduleGroupFromName("foo", nil).modules[0]
-		barB := ctx.moduleGroupFromName("bar", nil).modules[1]
-
-		if g, w := barB.variantName, "b"; g != w {
-			t.Fatalf("expected bar.modules[1] variant to be %q, got %q", w, g)
-		}
+		foo := ctx.moduleGroupFromName("foo", nil).moduleByVariantName("")
+		barB := ctx.moduleGroupFromName("bar", nil).moduleByVariantName("b")
 
 		if g, w := foo.forwardDeps, []*moduleInfo{barB}; !reflect.DeepEqual(g, w) {
 			t.Fatalf("expected foo deps to be %q, got %q", w, g)
@@ -138,18 +145,14 @@
 		// Tests a dependency from "foo" to "bar" variant "b_b" through alias "".
 		ctx := NewContext()
 		ctx.RegisterModuleType("test", newModuleCtxTestModule)
-		ctx.RegisterBottomUpMutator("1", createAliasMutator("bar"))
-		ctx.RegisterBottomUpMutator("2", createAliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("1", aliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("2", aliasMutator("bar"))
 		ctx.RegisterBottomUpMutator("3", addVariantDepsMutator(nil, nil, "foo", "bar"))
 
 		run(ctx)
 
-		foo := ctx.moduleGroupFromName("foo", nil).modules[0]
-		barBB := ctx.moduleGroupFromName("bar", nil).modules[3]
-
-		if g, w := barBB.variantName, "b_b"; g != w {
-			t.Fatalf("expected bar.modules[3] variant to be %q, got %q", w, g)
-		}
+		foo := ctx.moduleGroupFromName("foo", nil).moduleByVariantName("")
+		barBB := ctx.moduleGroupFromName("bar", nil).moduleByVariantName("b_b")
 
 		if g, w := foo.forwardDeps, []*moduleInfo{barBB}; !reflect.DeepEqual(g, w) {
 			t.Fatalf("expected foo deps to be %q, got %q", w, g)
@@ -162,18 +165,14 @@
 		// Tests a dependency from "foo" to "bar" variant "a_b" through alias "a".
 		ctx := NewContext()
 		ctx.RegisterModuleType("test", newModuleCtxTestModule)
-		ctx.RegisterBottomUpMutator("1", createAliasMutator("bar"))
-		ctx.RegisterBottomUpMutator("2", createAliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("1", aliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("2", aliasMutator("bar"))
 		ctx.RegisterBottomUpMutator("3", addVariantDepsMutator([]Variation{{"1", "a"}}, nil, "foo", "bar"))
 
 		run(ctx)
 
-		foo := ctx.moduleGroupFromName("foo", nil).modules[0]
-		barAB := ctx.moduleGroupFromName("bar", nil).modules[1]
-
-		if g, w := barAB.variantName, "a_b"; g != w {
-			t.Fatalf("expected bar.modules[1] variant to be %q, got %q", w, g)
-		}
+		foo := ctx.moduleGroupFromName("foo", nil).moduleByVariantName("")
+		barAB := ctx.moduleGroupFromName("bar", nil).moduleByVariantName("a_b")
 
 		if g, w := foo.forwardDeps, []*moduleInfo{barAB}; !reflect.DeepEqual(g, w) {
 			t.Fatalf("expected foo deps to be %q, got %q", w, g)
@@ -186,8 +185,8 @@
 		// Tests a dependency from "foo" to removed "bar" alias "" fails.
 		ctx := NewContext()
 		ctx.RegisterModuleType("test", newModuleCtxTestModule)
-		ctx.RegisterBottomUpMutator("1", createAliasMutator("bar"))
-		ctx.RegisterBottomUpMutator("2", noCreateAliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("1", aliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("2", noAliasMutator("bar"))
 		ctx.RegisterBottomUpMutator("3", addVariantDepsMutator(nil, nil, "foo", "bar"))
 
 		runWithFailures(ctx, `dependency "bar" of "foo" missing variant:`+"\n  \n"+
@@ -196,6 +195,113 @@
 	})
 }
 
+func TestCreateAliasVariations(t *testing.T) {
+	runWithFailures := func(ctx *Context, expectedErr string) {
+		t.Helper()
+		bp := `
+			test {
+				name: "foo",
+			}
+
+			test {
+				name: "bar",
+			}
+		`
+
+		mockFS := map[string][]byte{
+			"Blueprints": []byte(bp),
+		}
+
+		ctx.MockFileSystem(mockFS)
+
+		_, errs := ctx.ParseFileList(".", []string{"Blueprints"}, nil)
+		if len(errs) > 0 {
+			t.Errorf("unexpected parse errors:")
+			for _, err := range errs {
+				t.Errorf("  %s", err)
+			}
+		}
+
+		_, errs = ctx.ResolveDependencies(nil)
+		if len(errs) > 0 {
+			if expectedErr == "" {
+				t.Errorf("unexpected dep errors:")
+				for _, err := range errs {
+					t.Errorf("  %s", err)
+				}
+			} else {
+				for _, err := range errs {
+					if strings.Contains(err.Error(), expectedErr) {
+						continue
+					} else {
+						t.Errorf("unexpected dep error: %s", err)
+					}
+				}
+			}
+		} else if expectedErr != "" {
+			t.Errorf("missing dep error: %s", expectedErr)
+		}
+	}
+
+	run := func(ctx *Context) {
+		t.Helper()
+		runWithFailures(ctx, "")
+	}
+
+	t.Run("simple", func(t *testing.T) {
+		// Creates a module "bar" with variants "a" and "b" and alias "c" -> "a", "d" -> "b", and "e" -> "a".
+		// Tests a dependency from "foo" to "bar" variant "b" through alias "d".
+		ctx := NewContext()
+		ctx.RegisterModuleType("test", newModuleCtxTestModule)
+		ctx.RegisterBottomUpMutator("1", createAliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("2", addVariantDepsMutator([]Variation{{"1", "d"}}, nil, "foo", "bar"))
+
+		run(ctx)
+
+		foo := ctx.moduleGroupFromName("foo", nil).moduleByVariantName("")
+		barB := ctx.moduleGroupFromName("bar", nil).moduleByVariantName("b")
+
+		if g, w := foo.forwardDeps, []*moduleInfo{barB}; !reflect.DeepEqual(g, w) {
+			t.Fatalf("expected foo deps to be %q, got %q", w, g)
+		}
+	})
+
+	t.Run("chained", func(t *testing.T) {
+		// Creates a module "bar" with variants "a_a", "a_b", "b_a" and "b_b" and aliases "c" -> "a_b",
+		// "d" -> "b_b", and "d" -> "a_b".
+		// Tests a dependency from "foo" to "bar" variant "b_b" through alias "d".
+		ctx := NewContext()
+		ctx.RegisterModuleType("test", newModuleCtxTestModule)
+		ctx.RegisterBottomUpMutator("1", createAliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("2", aliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("3", addVariantDepsMutator([]Variation{{"1", "d"}}, nil, "foo", "bar"))
+
+		run(ctx)
+
+		foo := ctx.moduleGroupFromName("foo", nil).moduleByVariantName("")
+		barBB := ctx.moduleGroupFromName("bar", nil).moduleByVariantName("b_b")
+
+		if g, w := foo.forwardDeps, []*moduleInfo{barBB}; !reflect.DeepEqual(g, w) {
+			t.Fatalf("expected foo deps to be %q, got %q", w, g)
+		}
+	})
+
+	t.Run("removed dangling alias", func(t *testing.T) {
+		// Creates a module "bar" with variants "a" and "b" and alias "c" -> "a", "d" -> "b", and "e" -> "a",
+		// then splits the variants into "a_a", "a_b", "b_a" and "b_b" without creating new aliases.
+		// Tests a dependency from "foo" to removed "bar" alias "d" fails.
+		ctx := NewContext()
+		ctx.RegisterModuleType("test", newModuleCtxTestModule)
+		ctx.RegisterBottomUpMutator("1", createAliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("2", noAliasMutator("bar"))
+		ctx.RegisterBottomUpMutator("3", addVariantDepsMutator([]Variation{{"1", "d"}}, nil, "foo", "bar"))
+
+		runWithFailures(ctx, `dependency "bar" of "foo" missing variant:`+"\n  1:d\n"+
+			"available variants:"+
+			"\n  1:a, 2:a\n  1:a, 2:b\n  1:b, 2:a\n  1:b, 2:b")
+	})
+}
+
 func expectedErrors(t *testing.T, errs []error, expectedMessages ...string) {
 	t.Helper()
 	if len(errs) != len(expectedMessages) {
diff --git a/name_interface.go b/name_interface.go
index 1849e9d..5e7e16e 100644
--- a/name_interface.go
+++ b/name_interface.go
@@ -109,7 +109,7 @@
 		return nil, []error{
 			// seven characters at the start of the second line to align with the string "error: "
 			fmt.Errorf("module %q already defined\n"+
-				"       %s <-- previous definition here", name, group.modules[0].pos),
+				"       %s <-- previous definition here", name, group.modules.firstModule().pos),
 		}
 	}
 
@@ -130,7 +130,7 @@
 			// seven characters at the start of the second line to align with the string "error: "
 			fmt.Errorf("renaming module %q to %q conflicts with existing module\n"+
 				"       %s <-- existing module defined here",
-				oldName, newName, existingGroup.modules[0].pos),
+				oldName, newName, existingGroup.modules.firstModule().pos),
 		}
 	}
 
diff --git a/ninja_defs.go b/ninja_defs.go
index c5d0e4b..8c5db57 100644
--- a/ninja_defs.go
+++ b/ninja_defs.go
@@ -87,6 +87,7 @@
 	Inputs          []string          // The list of explicit input dependencies.
 	Implicits       []string          // The list of implicit input dependencies.
 	OrderOnly       []string          // The list of order-only dependencies.
+	Validations     []string          // The list of validations to run when this rule runs.
 	Args            map[string]string // The variable/value pairs to set.
 	Optional        bool              // Skip outputting a default statement
 }
@@ -257,6 +258,7 @@
 	Inputs          []ninjaString
 	Implicits       []ninjaString
 	OrderOnly       []ninjaString
+	Validations     []ninjaString
 	Args            map[Variable]ninjaString
 	Variables       map[string]ninjaString
 	Optional        bool
@@ -314,6 +316,11 @@
 		return nil, fmt.Errorf("error parsing OrderOnly param: %s", err)
 	}
 
+	b.Validations, err = parseNinjaStrings(scope, params.Validations)
+	if err != nil {
+		return nil, fmt.Errorf("error parsing Validations param: %s", err)
+	}
+
 	b.Optional = params.Optional
 
 	if params.Depfile != "" {
@@ -373,6 +380,7 @@
 		explicitDeps  = valueList(b.Inputs, pkgNames, inputEscaper)
 		implicitDeps  = valueList(b.Implicits, pkgNames, inputEscaper)
 		orderOnlyDeps = valueList(b.OrderOnly, pkgNames, inputEscaper)
+		validations   = valueList(b.Validations, pkgNames, inputEscaper)
 	)
 
 	if b.RuleDef != nil {
@@ -380,7 +388,7 @@
 		orderOnlyDeps = append(valueList(b.RuleDef.CommandOrderOnly, pkgNames, inputEscaper), orderOnlyDeps...)
 	}
 
-	err := nw.Build(comment, rule, outputs, implicitOuts, explicitDeps, implicitDeps, orderOnlyDeps)
+	err := nw.Build(comment, rule, outputs, implicitOuts, explicitDeps, implicitDeps, orderOnlyDeps, validations)
 	if err != nil {
 		return err
 	}
diff --git a/ninja_writer.go b/ninja_writer.go
index 5366f3f..5e69c08 100644
--- a/ninja_writer.go
+++ b/ninja_writer.go
@@ -104,7 +104,7 @@
 }
 
 func (n *ninjaWriter) Build(comment string, rule string, outputs, implicitOuts,
-	explicitDeps, implicitDeps, orderOnlyDeps []string) error {
+	explicitDeps, implicitDeps, orderOnlyDeps, validations []string) error {
 
 	n.justDidBlankLine = false
 
@@ -161,6 +161,14 @@
 		}
 	}
 
+	if len(validations) > 0 {
+		wrapper.WriteStringWithSpace("|@")
+
+		for _, dep := range validations {
+			wrapper.WriteStringWithSpace(dep)
+		}
+	}
+
 	return wrapper.Flush()
 }
 
diff --git a/ninja_writer_test.go b/ninja_writer_test.go
index cc880e5..48ecb7c 100644
--- a/ninja_writer_test.go
+++ b/ninja_writer_test.go
@@ -50,9 +50,9 @@
 	{
 		input: func(w *ninjaWriter) {
 			ck(w.Build("foo comment", "foo", []string{"o1", "o2"}, []string{"io1", "io2"},
-				[]string{"e1", "e2"}, []string{"i1", "i2"}, []string{"oo1", "oo2"}))
+				[]string{"e1", "e2"}, []string{"i1", "i2"}, []string{"oo1", "oo2"}, []string{"v1", "v2"}))
 		},
-		output: "# foo comment\nbuild o1 o2 | io1 io2: foo e1 e2 | i1 i2 || oo1 oo2\n",
+		output: "# foo comment\nbuild o1 o2 | io1 io2: foo e1 e2 | i1 i2 || oo1 oo2 |@ v1 v2\n",
 	},
 	{
 		input: func(w *ninjaWriter) {
@@ -94,7 +94,7 @@
 			ck(w.ScopedAssign("command", "echo out: $out in: $in _arg: $_arg"))
 			ck(w.ScopedAssign("pool", "p"))
 			ck(w.BlankLine())
-			ck(w.Build("r comment", "r", []string{"foo.o"}, nil, []string{"foo.in"}, nil, nil))
+			ck(w.Build("r comment", "r", []string{"foo.o"}, nil, []string{"foo.in"}, nil, nil, nil))
 			ck(w.ScopedAssign("_arg", "arg value"))
 		},
 		output: `pool p
diff --git a/provider.go b/provider.go
new file mode 100644
index 0000000..b83e1d4
--- /dev/null
+++ b/provider.go
@@ -0,0 +1,216 @@
+// Copyright 2020 Google Inc. All rights reserved.
+//
+// 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 blueprint
+
+import (
+	"fmt"
+	"reflect"
+)
+
+// This file implements Providers, modelled after Bazel
+// (https://docs.bazel.build/versions/master/skylark/rules.html#providers).
+// Each provider can be associated with a mutator, in which case the value for the provider for a
+// module can only be set during the mutator call for the module, and the value can only be
+// retrieved after the mutator call for the module. For providers not associated with a mutator, the
+// value can for the provider for a module can only be set during GenerateBuildActions for the
+// module, and the value can only be retrieved after GenerateBuildActions for the module.
+//
+// Providers are globally registered during init() and given a unique ID.  The value of a provider
+// for a module is stored in an []interface{} indexed by the ID.  If the value of a provider has
+// not been set, the value in the []interface{} will be nil.
+//
+// If the storage used by the provider value arrays becomes too large:
+//  sizeof([]interface) * number of providers * number of modules that have a provider value set
+// then the storage can be replaced with something like a bitwise trie.
+//
+// The purpose of providers is to provide a serializable checkpoint between modules to enable
+// Blueprint to skip parts of the analysis phase when inputs haven't changed.  To that end,
+// values passed to providers should be treated as immutable by callers to both the getters and
+// setters.  Go doesn't provide any way to enforce immutability on arbitrary types, so it may be
+// necessary for the getters and setters to make deep copies of the values, likely extending
+// proptools.CloneProperties to do so.
+
+type provider struct {
+	id      int
+	typ     reflect.Type
+	zero    interface{}
+	mutator string
+}
+
+type ProviderKey *provider
+
+var providerRegistry []ProviderKey
+
+// NewProvider returns a ProviderKey for the type of the given example value.  The example value
+// is otherwise unused.
+//
+// The returned ProviderKey can be used to set a value of the ProviderKey's type for a module
+// inside GenerateBuildActions for the module, and to get the value from GenerateBuildActions from
+// any module later in the build graph.
+//
+// Once Go has generics the exampleValue parameter will not be necessary:
+// NewProvider(type T)() ProviderKey(T)
+func NewProvider(exampleValue interface{}) ProviderKey {
+	return NewMutatorProvider(exampleValue, "")
+}
+
+// NewMutatorProvider returns a ProviderKey for the type of the given example value.  The example
+// value is otherwise unused.
+//
+// The returned ProviderKey can be used to set a value of the ProviderKey's type for a module inside
+// the given mutator for the module, and to get the value from GenerateBuildActions from any
+// module later in the build graph in the same mutator, or any module in a later mutator or during
+// GenerateBuildActions.
+//
+// Once Go has generics the exampleValue parameter will not be necessary:
+// NewMutatorProvider(type T)(mutator string) ProviderKey(T)
+func NewMutatorProvider(exampleValue interface{}, mutator string) ProviderKey {
+	checkCalledFromInit()
+
+	typ := reflect.TypeOf(exampleValue)
+	zero := reflect.Zero(typ).Interface()
+
+	provider := &provider{
+		id:      len(providerRegistry),
+		typ:     typ,
+		zero:    zero,
+		mutator: mutator,
+	}
+
+	providerRegistry = append(providerRegistry, provider)
+
+	return provider
+}
+
+// initProviders fills c.providerMutators with the *mutatorInfo associated with each provider ID,
+// if any.
+func (c *Context) initProviders() {
+	c.providerMutators = make([]*mutatorInfo, len(providerRegistry))
+	for _, provider := range providerRegistry {
+		for _, mutator := range c.mutatorInfo {
+			if mutator.name == provider.mutator {
+				c.providerMutators[provider.id] = mutator
+			}
+		}
+	}
+}
+
+// setProvider sets the value for a provider on a moduleInfo.  Verifies that it is called during the
+// appropriate mutator or GenerateBuildActions pass for the provider, and that the value is of the
+// appropriate type.  The value should not be modified after being passed to setProvider.
+//
+// Once Go has generics the value parameter can be typed:
+// setProvider(type T)(m *moduleInfo, provider ProviderKey(T), value T)
+func (c *Context) setProvider(m *moduleInfo, provider ProviderKey, value interface{}) {
+	if provider.mutator == "" {
+		if !m.startedGenerateBuildActions {
+			panic(fmt.Sprintf("Can't set value of provider %s before GenerateBuildActions started",
+				provider.typ))
+		} else if m.finishedGenerateBuildActions {
+			panic(fmt.Sprintf("Can't set value of provider %s after GenerateBuildActions finished",
+				provider.typ))
+		}
+	} else {
+		expectedMutator := c.providerMutators[provider.id]
+		if expectedMutator == nil {
+			panic(fmt.Sprintf("Can't set value of provider %s associated with unregistered mutator %s",
+				provider.typ, provider.mutator))
+		} else if c.mutatorFinishedForModule(expectedMutator, m) {
+			panic(fmt.Sprintf("Can't set value of provider %s after mutator %s finished",
+				provider.typ, provider.mutator))
+		} else if !c.mutatorStartedForModule(expectedMutator, m) {
+			panic(fmt.Sprintf("Can't set value of provider %s before mutator %s started",
+				provider.typ, provider.mutator))
+		}
+	}
+
+	if typ := reflect.TypeOf(value); typ != provider.typ {
+		panic(fmt.Sprintf("Value for provider has incorrect type, wanted %s, got %s",
+			provider.typ, typ))
+	}
+
+	if m.providers == nil {
+		m.providers = make([]interface{}, len(providerRegistry))
+	}
+
+	if m.providers[provider.id] != nil {
+		panic(fmt.Sprintf("Value of provider %s is already set", provider.typ))
+	}
+
+	m.providers[provider.id] = value
+}
+
+// provider returns the value, if any, for a given provider for a module.  Verifies that it is
+// called after the appropriate mutator or GenerateBuildActions pass for the provider on the module.
+// If the value for the provider was not set it returns the zero value of the type of the provider,
+// which means the return value can always be type-asserted to the type of the provider.  The return
+// value should always be considered read-only.
+//
+// Once Go has generics the return value can be typed and the type assert by callers can be dropped:
+// provider(type T)(m *moduleInfo, provider ProviderKey(T)) T
+func (c *Context) provider(m *moduleInfo, provider ProviderKey) (interface{}, bool) {
+	if provider.mutator == "" {
+		if !m.finishedGenerateBuildActions {
+			panic(fmt.Sprintf("Can't get value of provider %s before GenerateBuildActions finished",
+				provider.typ))
+		}
+	} else {
+		expectedMutator := c.providerMutators[provider.id]
+		if expectedMutator != nil && !c.mutatorFinishedForModule(expectedMutator, m) {
+			panic(fmt.Sprintf("Can't get value of provider %s before mutator %s finished",
+				provider.typ, provider.mutator))
+		}
+	}
+
+	if len(m.providers) > provider.id {
+		if p := m.providers[provider.id]; p != nil {
+			return p, true
+		}
+	}
+
+	return provider.zero, false
+}
+
+func (c *Context) mutatorFinishedForModule(mutator *mutatorInfo, m *moduleInfo) bool {
+	if c.finishedMutators[mutator] {
+		// mutator pass finished for all modules
+		return true
+	}
+
+	if c.startedMutator == mutator {
+		// mutator pass started, check if it is finished for this module
+		return m.finishedMutator == mutator
+	}
+
+	// mutator pass hasn't started
+	return false
+}
+
+func (c *Context) mutatorStartedForModule(mutator *mutatorInfo, m *moduleInfo) bool {
+	if c.finishedMutators[mutator] {
+		// mutator pass finished for all modules
+		return true
+	}
+
+	if c.startedMutator == mutator {
+		// mutator pass is currently running
+		if m.startedMutator == mutator {
+			// mutator has started for this module
+			return true
+		}
+	}
+
+	return false
+}
diff --git a/provider_test.go b/provider_test.go
new file mode 100644
index 0000000..8f8def4
--- /dev/null
+++ b/provider_test.go
@@ -0,0 +1,420 @@
+// Copyright 2020 Google Inc. All rights reserved.
+//
+// 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 blueprint
+
+import (
+	"fmt"
+	"reflect"
+	"strings"
+	"testing"
+)
+
+type providerTestModule struct {
+	SimpleName
+	properties struct {
+		Deps []string
+	}
+
+	mutatorProviderValues              []string
+	generateBuildActionsProviderValues []string
+}
+
+func newProviderTestModule() (Module, []interface{}) {
+	m := &providerTestModule{}
+	return m, []interface{}{&m.properties, &m.SimpleName.Properties}
+}
+
+type providerTestMutatorInfo struct {
+	Values []string
+}
+
+type providerTestGenerateBuildActionsInfo struct {
+	Value string
+}
+
+type providerTestUnsetInfo string
+
+var providerTestMutatorInfoProvider = NewMutatorProvider(&providerTestMutatorInfo{}, "provider_mutator")
+var providerTestGenerateBuildActionsInfoProvider = NewProvider(&providerTestGenerateBuildActionsInfo{})
+var providerTestUnsetInfoProvider = NewMutatorProvider((providerTestUnsetInfo)(""), "provider_mutator")
+var providerTestUnusedMutatorProvider = NewMutatorProvider(&struct{ unused string }{}, "nonexistent_mutator")
+
+func (p *providerTestModule) GenerateBuildActions(ctx ModuleContext) {
+	unset := ctx.Provider(providerTestUnsetInfoProvider).(providerTestUnsetInfo)
+	if unset != "" {
+		panic(fmt.Sprintf("expected zero value for providerTestGenerateBuildActionsInfoProvider before it was set, got %q",
+			unset))
+	}
+
+	_ = ctx.Provider(providerTestUnusedMutatorProvider)
+
+	ctx.SetProvider(providerTestGenerateBuildActionsInfoProvider, &providerTestGenerateBuildActionsInfo{
+		Value: ctx.ModuleName(),
+	})
+
+	mp := ctx.Provider(providerTestMutatorInfoProvider).(*providerTestMutatorInfo)
+	if mp != nil {
+		p.mutatorProviderValues = mp.Values
+	}
+
+	ctx.VisitDirectDeps(func(module Module) {
+		gbap := ctx.OtherModuleProvider(module, providerTestGenerateBuildActionsInfoProvider).(*providerTestGenerateBuildActionsInfo)
+		if gbap != nil {
+			p.generateBuildActionsProviderValues = append(p.generateBuildActionsProviderValues, gbap.Value)
+		}
+	})
+}
+
+func providerTestDepsMutator(ctx BottomUpMutatorContext) {
+	if p, ok := ctx.Module().(*providerTestModule); ok {
+		ctx.AddDependency(ctx.Module(), nil, p.properties.Deps...)
+	}
+}
+
+func providerTestMutator(ctx BottomUpMutatorContext) {
+	values := []string{strings.ToLower(ctx.ModuleName())}
+
+	ctx.VisitDirectDeps(func(module Module) {
+		mp := ctx.OtherModuleProvider(module, providerTestMutatorInfoProvider).(*providerTestMutatorInfo)
+		if mp != nil {
+			values = append(values, mp.Values...)
+		}
+	})
+
+	ctx.SetProvider(providerTestMutatorInfoProvider, &providerTestMutatorInfo{
+		Values: values,
+	})
+}
+
+func providerTestAfterMutator(ctx BottomUpMutatorContext) {
+	_ = ctx.Provider(providerTestMutatorInfoProvider)
+}
+
+func TestProviders(t *testing.T) {
+	ctx := NewContext()
+	ctx.RegisterModuleType("provider_module", newProviderTestModule)
+	ctx.RegisterBottomUpMutator("provider_deps_mutator", providerTestDepsMutator)
+	ctx.RegisterBottomUpMutator("provider_mutator", providerTestMutator)
+	ctx.RegisterBottomUpMutator("provider_after_mutator", providerTestAfterMutator)
+
+	ctx.MockFileSystem(map[string][]byte{
+		"Blueprints": []byte(`
+			provider_module {
+				name: "A",
+				deps: ["B"],
+			}
+	
+			provider_module {
+				name: "B",
+				deps: ["C", "D"],
+			}
+	
+			provider_module {
+				name: "C",
+				deps: ["D"],
+			}
+	
+			provider_module {
+				name: "D",
+			}
+		`),
+	})
+
+	_, errs := ctx.ParseBlueprintsFiles("Blueprints", nil)
+	if len(errs) == 0 {
+		_, errs = ctx.ResolveDependencies(nil)
+	}
+	if len(errs) == 0 {
+		_, errs = ctx.PrepareBuildActions(nil)
+	}
+	if len(errs) > 0 {
+		t.Errorf("unexpected errors:")
+		for _, err := range errs {
+			t.Errorf("  %s", err)
+		}
+		t.FailNow()
+	}
+
+	aModule := ctx.moduleGroupFromName("A", nil).moduleByVariantName("").logicModule.(*providerTestModule)
+	if g, w := aModule.generateBuildActionsProviderValues, []string{"B"}; !reflect.DeepEqual(g, w) {
+		t.Errorf("expected A.generateBuildActionsProviderValues %q, got %q", w, g)
+	}
+	if g, w := aModule.mutatorProviderValues, []string{"a", "b", "c", "d", "d"}; !reflect.DeepEqual(g, w) {
+		t.Errorf("expected A.mutatorProviderValues %q, got %q", w, g)
+	}
+
+	bModule := ctx.moduleGroupFromName("B", nil).moduleByVariantName("").logicModule.(*providerTestModule)
+	if g, w := bModule.generateBuildActionsProviderValues, []string{"C", "D"}; !reflect.DeepEqual(g, w) {
+		t.Errorf("expected B.generateBuildActionsProviderValues %q, got %q", w, g)
+	}
+	if g, w := bModule.mutatorProviderValues, []string{"b", "c", "d", "d"}; !reflect.DeepEqual(g, w) {
+		t.Errorf("expected B.mutatorProviderValues %q, got %q", w, g)
+	}
+}
+
+type invalidProviderUsageMutatorInfo string
+type invalidProviderUsageGenerateBuildActionsInfo string
+
+var invalidProviderUsageMutatorInfoProvider = NewMutatorProvider(invalidProviderUsageMutatorInfo(""), "mutator_under_test")
+var invalidProviderUsageGenerateBuildActionsInfoProvider = NewProvider(invalidProviderUsageGenerateBuildActionsInfo(""))
+
+type invalidProviderUsageTestModule struct {
+	parent *invalidProviderUsageTestModule
+
+	SimpleName
+	properties struct {
+		Deps []string
+
+		Early_mutator_set_of_mutator_provider       bool
+		Late_mutator_set_of_mutator_provider        bool
+		Late_build_actions_set_of_mutator_provider  bool
+		Early_mutator_set_of_build_actions_provider bool
+
+		Early_mutator_get_of_mutator_provider       bool
+		Early_module_get_of_mutator_provider        bool
+		Early_mutator_get_of_build_actions_provider bool
+		Early_module_get_of_build_actions_provider  bool
+
+		Duplicate_set bool
+	}
+}
+
+func invalidProviderUsageDepsMutator(ctx BottomUpMutatorContext) {
+	if i, ok := ctx.Module().(*invalidProviderUsageTestModule); ok {
+		ctx.AddDependency(ctx.Module(), nil, i.properties.Deps...)
+	}
+}
+
+func invalidProviderUsageParentMutator(ctx TopDownMutatorContext) {
+	if i, ok := ctx.Module().(*invalidProviderUsageTestModule); ok {
+		ctx.VisitDirectDeps(func(module Module) {
+			module.(*invalidProviderUsageTestModule).parent = i
+		})
+	}
+}
+
+func invalidProviderUsageBeforeMutator(ctx BottomUpMutatorContext) {
+	if i, ok := ctx.Module().(*invalidProviderUsageTestModule); ok {
+		if i.properties.Early_mutator_set_of_mutator_provider {
+			// A mutator attempting to set the value of a provider associated with a later mutator.
+			ctx.SetProvider(invalidProviderUsageMutatorInfoProvider, invalidProviderUsageMutatorInfo(""))
+		}
+		if i.properties.Early_mutator_get_of_mutator_provider {
+			// A mutator attempting to get the value of a provider associated with a later mutator.
+			_ = ctx.Provider(invalidProviderUsageMutatorInfoProvider)
+		}
+	}
+}
+
+func invalidProviderUsageMutatorUnderTest(ctx TopDownMutatorContext) {
+	if i, ok := ctx.Module().(*invalidProviderUsageTestModule); ok {
+		if i.properties.Early_mutator_set_of_build_actions_provider {
+			// A mutator attempting to set the value of a non-mutator provider.
+			ctx.SetProvider(invalidProviderUsageGenerateBuildActionsInfoProvider, invalidProviderUsageGenerateBuildActionsInfo(""))
+		}
+		if i.properties.Early_mutator_get_of_build_actions_provider {
+			// A mutator attempting to get the value of a non-mutator provider.
+			_ = ctx.Provider(invalidProviderUsageGenerateBuildActionsInfoProvider)
+		}
+		if i.properties.Early_module_get_of_mutator_provider {
+			// A mutator attempting to get the value of a provider associated with this mutator on
+			// a module for which this mutator hasn't run.  This is a top down mutator so
+			// dependencies haven't run yet.
+			ctx.VisitDirectDeps(func(module Module) {
+				_ = ctx.OtherModuleProvider(module, invalidProviderUsageMutatorInfoProvider)
+			})
+		}
+	}
+}
+
+func invalidProviderUsageAfterMutator(ctx BottomUpMutatorContext) {
+	if i, ok := ctx.Module().(*invalidProviderUsageTestModule); ok {
+		if i.properties.Late_mutator_set_of_mutator_provider {
+			// A mutator trying to set the value of a provider associated with an earlier mutator.
+			ctx.SetProvider(invalidProviderUsageMutatorInfoProvider, invalidProviderUsageMutatorInfo(""))
+		}
+		if i.properties.Late_mutator_set_of_mutator_provider {
+			// A mutator trying to set the value of a provider associated with an earlier mutator.
+			ctx.SetProvider(invalidProviderUsageMutatorInfoProvider, invalidProviderUsageMutatorInfo(""))
+		}
+	}
+}
+
+func (i *invalidProviderUsageTestModule) GenerateBuildActions(ctx ModuleContext) {
+	if i.properties.Late_build_actions_set_of_mutator_provider {
+		// A GenerateBuildActions trying to set the value of a provider associated with a mutator.
+		ctx.SetProvider(invalidProviderUsageMutatorInfoProvider, invalidProviderUsageMutatorInfo(""))
+	}
+	if i.properties.Early_module_get_of_build_actions_provider {
+		// A GenerateBuildActions trying to get the value of a provider on a module for which
+		// GenerateBuildActions hasn't run.
+		_ = ctx.OtherModuleProvider(i.parent, invalidProviderUsageGenerateBuildActionsInfoProvider)
+	}
+	if i.properties.Duplicate_set {
+		ctx.SetProvider(invalidProviderUsageGenerateBuildActionsInfoProvider, invalidProviderUsageGenerateBuildActionsInfo(""))
+		ctx.SetProvider(invalidProviderUsageGenerateBuildActionsInfoProvider, invalidProviderUsageGenerateBuildActionsInfo(""))
+	}
+}
+
+func TestInvalidProvidersUsage(t *testing.T) {
+	run := func(t *testing.T, module string, prop string, panicMsg string) {
+		t.Helper()
+		ctx := NewContext()
+		ctx.RegisterModuleType("invalid_provider_usage_test_module", func() (Module, []interface{}) {
+			m := &invalidProviderUsageTestModule{}
+			return m, []interface{}{&m.properties, &m.SimpleName.Properties}
+		})
+		ctx.RegisterBottomUpMutator("deps", invalidProviderUsageDepsMutator)
+		ctx.RegisterBottomUpMutator("before", invalidProviderUsageBeforeMutator)
+		ctx.RegisterTopDownMutator("mutator_under_test", invalidProviderUsageMutatorUnderTest)
+		ctx.RegisterBottomUpMutator("after", invalidProviderUsageAfterMutator)
+		ctx.RegisterTopDownMutator("parent", invalidProviderUsageParentMutator)
+
+		// Don't invalidate the parent pointer and before GenerateBuildActions.
+		ctx.skipCloneModulesAfterMutators = true
+
+		var parentBP, moduleUnderTestBP, childBP string
+
+		prop += ": true,"
+
+		switch module {
+		case "parent":
+			parentBP = prop
+		case "module_under_test":
+			moduleUnderTestBP = prop
+		case "child":
+			childBP = prop
+		}
+
+		bp := fmt.Sprintf(`
+			invalid_provider_usage_test_module {
+				name: "parent",
+				deps: ["module_under_test"],
+				%s
+			}
+	
+			invalid_provider_usage_test_module {
+				name: "module_under_test",
+				deps: ["child"],
+				%s
+			}
+	
+			invalid_provider_usage_test_module {
+				name: "child",
+				%s
+			}
+
+		`,
+			parentBP,
+			moduleUnderTestBP,
+			childBP)
+
+		ctx.MockFileSystem(map[string][]byte{
+			"Blueprints": []byte(bp),
+		})
+
+		_, errs := ctx.ParseBlueprintsFiles("Blueprints", nil)
+
+		if len(errs) == 0 {
+			_, errs = ctx.ResolveDependencies(nil)
+		}
+
+		if len(errs) == 0 {
+			_, errs = ctx.PrepareBuildActions(nil)
+		}
+
+		if len(errs) == 0 {
+			t.Fatal("expected an error")
+		}
+
+		if len(errs) > 1 {
+			t.Errorf("expected a single error, got %d:", len(errs))
+			for i, err := range errs {
+				t.Errorf("%d:  %s", i, err)
+			}
+			t.FailNow()
+		}
+
+		if panicErr, ok := errs[0].(panicError); ok {
+			if panicErr.panic != panicMsg {
+				t.Fatalf("expected panic %q, got %q", panicMsg, panicErr.panic)
+			}
+		} else {
+			t.Fatalf("expected a panicError, got %T: %s", errs[0], errs[0].Error())
+		}
+
+	}
+
+	tests := []struct {
+		prop   string
+		module string
+
+		panicMsg string
+		skip     string
+	}{
+		{
+			prop:     "early_mutator_set_of_mutator_provider",
+			module:   "module_under_test",
+			panicMsg: "Can't set value of provider blueprint.invalidProviderUsageMutatorInfo before mutator mutator_under_test started",
+		},
+		{
+			prop:     "late_mutator_set_of_mutator_provider",
+			module:   "module_under_test",
+			panicMsg: "Can't set value of provider blueprint.invalidProviderUsageMutatorInfo after mutator mutator_under_test finished",
+		},
+		{
+			prop:     "late_build_actions_set_of_mutator_provider",
+			module:   "module_under_test",
+			panicMsg: "Can't set value of provider blueprint.invalidProviderUsageMutatorInfo after mutator mutator_under_test finished",
+		},
+		{
+			prop:     "early_mutator_set_of_build_actions_provider",
+			module:   "module_under_test",
+			panicMsg: "Can't set value of provider blueprint.invalidProviderUsageGenerateBuildActionsInfo before GenerateBuildActions started",
+		},
+
+		{
+			prop:     "early_mutator_get_of_mutator_provider",
+			module:   "module_under_test",
+			panicMsg: "Can't get value of provider blueprint.invalidProviderUsageMutatorInfo before mutator mutator_under_test finished",
+		},
+		{
+			prop:     "early_module_get_of_mutator_provider",
+			module:   "module_under_test",
+			panicMsg: "Can't get value of provider blueprint.invalidProviderUsageMutatorInfo before mutator mutator_under_test finished",
+		},
+		{
+			prop:     "early_mutator_get_of_build_actions_provider",
+			module:   "module_under_test",
+			panicMsg: "Can't get value of provider blueprint.invalidProviderUsageGenerateBuildActionsInfo before GenerateBuildActions finished",
+		},
+		{
+			prop:     "early_module_get_of_build_actions_provider",
+			module:   "module_under_test",
+			panicMsg: "Can't get value of provider blueprint.invalidProviderUsageGenerateBuildActionsInfo before GenerateBuildActions finished",
+		},
+		{
+			prop:     "duplicate_set",
+			module:   "module_under_test",
+			panicMsg: "Value of provider blueprint.invalidProviderUsageGenerateBuildActionsInfo is already set",
+		},
+	}
+
+	for _, tt := range tests {
+		t.Run(tt.prop, func(t *testing.T) {
+			run(t, tt.module, tt.prop, tt.panicMsg)
+		})
+	}
+}
diff --git a/singleton_ctx.go b/singleton_ctx.go
index 3c0a24c..a4e7153 100644
--- a/singleton_ctx.go
+++ b/singleton_ctx.go
@@ -47,6 +47,16 @@
 	// BlueprintFile returns the path of the Blueprint file that defined the given module.
 	BlueprintFile(module Module) string
 
+	// ModuleProvider returns the value, if any, for the provider for a module.  If the value for the
+	// provider was not set it returns the zero value of the type of the provider, which means the
+	// return value can always be type-asserted to the type of the provider.  The return value should
+	// always be considered read-only.  It panics if called before the appropriate mutator or
+	// GenerateBuildActions pass for the provider on the module.
+	ModuleProvider(module Module, provider ProviderKey) interface{}
+
+	// ModuleHasProvider returns true if the provider for the given module has been set.
+	ModuleHasProvider(m Module, provider ProviderKey) bool
+
 	// ModuleErrorf reports an error at the line number of the module type in the module definition.
 	ModuleErrorf(module Module, format string, args ...interface{})
 
@@ -188,6 +198,15 @@
 	return s.context.ModuleType(logicModule)
 }
 
+func (s *singletonContext) ModuleProvider(logicModule Module, provider ProviderKey) interface{} {
+	return s.context.ModuleProvider(logicModule, provider)
+}
+
+// ModuleHasProvider returns true if the provider for the given module has been set.
+func (s *singletonContext) ModuleHasProvider(logicModule Module, provider ProviderKey) bool {
+	return s.context.ModuleHasProvider(logicModule, provider)
+}
+
 func (s *singletonContext) BlueprintFile(logicModule Module) string {
 	return s.context.BlueprintFile(logicModule)
 }
diff --git a/splice_modules_test.go b/splice_modules_test.go
index a67aeb1..473999a 100644
--- a/splice_modules_test.go
+++ b/splice_modules_test.go
@@ -20,91 +20,91 @@
 )
 
 var (
-	testModuleA = &moduleInfo{variantName: "testModuleA"}
-	testModuleB = &moduleInfo{variantName: "testModuleB"}
-	testModuleC = &moduleInfo{variantName: "testModuleC"}
-	testModuleD = &moduleInfo{variantName: "testModuleD"}
-	testModuleE = &moduleInfo{variantName: "testModuleE"}
-	testModuleF = &moduleInfo{variantName: "testModuleF"}
+	testModuleA = &moduleInfo{variant: variant{name: "testModuleA"}}
+	testModuleB = &moduleInfo{variant: variant{name: "testModuleB"}}
+	testModuleC = &moduleInfo{variant: variant{name: "testModuleC"}}
+	testModuleD = &moduleInfo{variant: variant{name: "testModuleD"}}
+	testModuleE = &moduleInfo{variant: variant{name: "testModuleE"}}
+	testModuleF = &moduleInfo{variant: variant{name: "testModuleF"}}
 )
 
 var spliceModulesTestCases = []struct {
-	in         []*moduleInfo
+	in         modulesOrAliases
 	at         int
-	with       []*moduleInfo
-	out        []*moduleInfo
+	with       modulesOrAliases
+	out        modulesOrAliases
 	outAt      int
 	reallocate bool
 }{
 	{
 		// Insert at the beginning
-		in:         []*moduleInfo{testModuleA, testModuleB, testModuleC},
+		in:         modulesOrAliases{testModuleA, testModuleB, testModuleC},
 		at:         0,
-		with:       []*moduleInfo{testModuleD, testModuleE},
-		out:        []*moduleInfo{testModuleD, testModuleE, testModuleB, testModuleC},
+		with:       modulesOrAliases{testModuleD, testModuleE},
+		out:        modulesOrAliases{testModuleD, testModuleE, testModuleB, testModuleC},
 		outAt:      1,
 		reallocate: true,
 	},
 	{
 		// Insert in the middle
-		in:         []*moduleInfo{testModuleA, testModuleB, testModuleC},
+		in:         modulesOrAliases{testModuleA, testModuleB, testModuleC},
 		at:         1,
-		with:       []*moduleInfo{testModuleD, testModuleE},
-		out:        []*moduleInfo{testModuleA, testModuleD, testModuleE, testModuleC},
+		with:       modulesOrAliases{testModuleD, testModuleE},
+		out:        modulesOrAliases{testModuleA, testModuleD, testModuleE, testModuleC},
 		outAt:      2,
 		reallocate: true,
 	},
 	{
 		// Insert at the end
-		in:         []*moduleInfo{testModuleA, testModuleB, testModuleC},
+		in:         modulesOrAliases{testModuleA, testModuleB, testModuleC},
 		at:         2,
-		with:       []*moduleInfo{testModuleD, testModuleE},
-		out:        []*moduleInfo{testModuleA, testModuleB, testModuleD, testModuleE},
+		with:       modulesOrAliases{testModuleD, testModuleE},
+		out:        modulesOrAliases{testModuleA, testModuleB, testModuleD, testModuleE},
 		outAt:      3,
 		reallocate: true,
 	},
 	{
 		// Insert over a single element
-		in:         []*moduleInfo{testModuleA},
+		in:         modulesOrAliases{testModuleA},
 		at:         0,
-		with:       []*moduleInfo{testModuleD, testModuleE},
-		out:        []*moduleInfo{testModuleD, testModuleE},
+		with:       modulesOrAliases{testModuleD, testModuleE},
+		out:        modulesOrAliases{testModuleD, testModuleE},
 		outAt:      1,
 		reallocate: true,
 	},
 	{
 		// Insert at the beginning without reallocating
-		in:         []*moduleInfo{testModuleA, testModuleB, testModuleC, nil}[0:3],
+		in:         modulesOrAliases{testModuleA, testModuleB, testModuleC, nil}[0:3],
 		at:         0,
-		with:       []*moduleInfo{testModuleD, testModuleE},
-		out:        []*moduleInfo{testModuleD, testModuleE, testModuleB, testModuleC},
+		with:       modulesOrAliases{testModuleD, testModuleE},
+		out:        modulesOrAliases{testModuleD, testModuleE, testModuleB, testModuleC},
 		outAt:      1,
 		reallocate: false,
 	},
 	{
 		// Insert in the middle without reallocating
-		in:         []*moduleInfo{testModuleA, testModuleB, testModuleC, nil}[0:3],
+		in:         modulesOrAliases{testModuleA, testModuleB, testModuleC, nil}[0:3],
 		at:         1,
-		with:       []*moduleInfo{testModuleD, testModuleE},
-		out:        []*moduleInfo{testModuleA, testModuleD, testModuleE, testModuleC},
+		with:       modulesOrAliases{testModuleD, testModuleE},
+		out:        modulesOrAliases{testModuleA, testModuleD, testModuleE, testModuleC},
 		outAt:      2,
 		reallocate: false,
 	},
 	{
 		// Insert at the end without reallocating
-		in:         []*moduleInfo{testModuleA, testModuleB, testModuleC, nil}[0:3],
+		in:         modulesOrAliases{testModuleA, testModuleB, testModuleC, nil}[0:3],
 		at:         2,
-		with:       []*moduleInfo{testModuleD, testModuleE},
-		out:        []*moduleInfo{testModuleA, testModuleB, testModuleD, testModuleE},
+		with:       modulesOrAliases{testModuleD, testModuleE},
+		out:        modulesOrAliases{testModuleA, testModuleB, testModuleD, testModuleE},
 		outAt:      3,
 		reallocate: false,
 	},
 	{
 		// Insert over a single element without reallocating
-		in:         []*moduleInfo{testModuleA, nil}[0:1],
+		in:         modulesOrAliases{testModuleA, nil}[0:1],
 		at:         0,
-		with:       []*moduleInfo{testModuleD, testModuleE},
-		out:        []*moduleInfo{testModuleD, testModuleE},
+		with:       modulesOrAliases{testModuleD, testModuleE},
+		out:        modulesOrAliases{testModuleD, testModuleE},
 		outAt:      1,
 		reallocate: false,
 	},
@@ -112,7 +112,7 @@
 
 func TestSpliceModules(t *testing.T) {
 	for _, testCase := range spliceModulesTestCases {
-		in := make([]*moduleInfo, len(testCase.in), cap(testCase.in))
+		in := make(modulesOrAliases, len(testCase.in), cap(testCase.in))
 		copy(in, testCase.in)
 		origIn := in
 		got, gotAt := spliceModules(in, testCase.at, testCase.with)
@@ -139,6 +139,6 @@
 	}
 }
 
-func sameArray(a, b []*moduleInfo) bool {
+func sameArray(a, b modulesOrAliases) bool {
 	return &a[0:cap(a)][cap(a)-1] == &b[0:cap(b)][cap(b)-1]
 }
diff --git a/visit_test.go b/visit_test.go
index efaadba..1c74b93 100644
--- a/visit_test.go
+++ b/visit_test.go
@@ -149,13 +149,13 @@
 func TestVisit(t *testing.T) {
 	ctx := setupVisitTest(t)
 
-	topModule := ctx.moduleGroupFromName("A", nil).modules[0].logicModule.(*visitModule)
+	topModule := ctx.moduleGroupFromName("A", nil).modules.firstModule().logicModule.(*visitModule)
 	assertString(t, topModule.properties.VisitDepsDepthFirst, "FEDCB")
 	assertString(t, topModule.properties.VisitDepsDepthFirstIf, "FEDC")
 	assertString(t, topModule.properties.VisitDirectDeps, "B")
 	assertString(t, topModule.properties.VisitDirectDepsIf, "")
 
-	eModule := ctx.moduleGroupFromName("E", nil).modules[0].logicModule.(*visitModule)
+	eModule := ctx.moduleGroupFromName("E", nil).modules.firstModule().logicModule.(*visitModule)
 	assertString(t, eModule.properties.VisitDepsDepthFirst, "F")
 	assertString(t, eModule.properties.VisitDepsDepthFirstIf, "F")
 	assertString(t, eModule.properties.VisitDirectDeps, "FF")