• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// Copyright 2014 Google Inc. All rights reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package blueprint
16
17import (
18	"bytes"
19	"context"
20	"encoding/json"
21	"errors"
22	"fmt"
23	"io"
24	"io/ioutil"
25	"os"
26	"path/filepath"
27	"reflect"
28	"runtime"
29	"runtime/pprof"
30	"sort"
31	"strings"
32	"sync"
33	"sync/atomic"
34	"text/scanner"
35	"text/template"
36
37	"github.com/google/blueprint/metrics"
38	"github.com/google/blueprint/parser"
39	"github.com/google/blueprint/pathtools"
40	"github.com/google/blueprint/proptools"
41)
42
43var ErrBuildActionsNotReady = errors.New("build actions are not ready")
44
45const maxErrors = 10
46const MockModuleListFile = "bplist"
47
48// A Context contains all the state needed to parse a set of Blueprints files
49// and generate a Ninja file.  The process of generating a Ninja file proceeds
50// through a series of four phases.  Each phase corresponds with a some methods
51// on the Context object
52//
53//         Phase                            Methods
54//      ------------      -------------------------------------------
55//   1. Registration         RegisterModuleType, RegisterSingletonType
56//
57//   2. Parse                    ParseBlueprintsFiles, Parse
58//
59//   3. Generate            ResolveDependencies, PrepareBuildActions
60//
61//   4. Write                           WriteBuildFile
62//
63// The registration phase prepares the context to process Blueprints files
64// containing various types of modules.  The parse phase reads in one or more
65// Blueprints files and validates their contents against the module types that
66// have been registered.  The generate phase then analyzes the parsed Blueprints
67// contents to create an internal representation for the build actions that must
68// be performed.  This phase also performs validation of the module dependencies
69// and property values defined in the parsed Blueprints files.  Finally, the
70// write phase generates the Ninja manifest text based on the generated build
71// actions.
72type Context struct {
73	context.Context
74
75	// Used for metrics-related event logging.
76	EventHandler *metrics.EventHandler
77
78	moduleFactories     map[string]ModuleFactory
79	nameInterface       NameInterface
80	moduleGroups        []*moduleGroup
81	moduleInfo          map[Module]*moduleInfo
82	modulesSorted       []*moduleInfo
83	preSingletonInfo    []*singletonInfo
84	singletonInfo       []*singletonInfo
85	mutatorInfo         []*mutatorInfo
86	variantMutatorNames []string
87
88	depsModified uint32 // positive if a mutator modified the dependencies
89
90	dependenciesReady bool // set to true on a successful ResolveDependencies
91	buildActionsReady bool // set to true on a successful PrepareBuildActions
92
93	// set by SetIgnoreUnknownModuleTypes
94	ignoreUnknownModuleTypes bool
95
96	// set by SetAllowMissingDependencies
97	allowMissingDependencies bool
98
99	// set during PrepareBuildActions
100	pkgNames        map[*packageContext]string
101	liveGlobals     *liveTracker
102	globalVariables map[Variable]ninjaString
103	globalPools     map[Pool]*poolDef
104	globalRules     map[Rule]*ruleDef
105
106	// set during PrepareBuildActions
107	outDir             ninjaString // The builddir special Ninja variable
108	requiredNinjaMajor int         // For the ninja_required_version variable
109	requiredNinjaMinor int         // For the ninja_required_version variable
110	requiredNinjaMicro int         // For the ninja_required_version variable
111
112	subninjas []string
113
114	// set lazily by sortedModuleGroups
115	cachedSortedModuleGroups []*moduleGroup
116	// cache deps modified to determine whether cachedSortedModuleGroups needs to be recalculated
117	cachedDepsModified bool
118
119	globs    map[globKey]pathtools.GlobResult
120	globLock sync.Mutex
121
122	srcDir         string
123	fs             pathtools.FileSystem
124	moduleListFile string
125
126	// Mutators indexed by the ID of the provider associated with them.  Not all mutators will
127	// have providers, and not all providers will have a mutator, or if they do the mutator may
128	// not be registered in this Context.
129	providerMutators []*mutatorInfo
130
131	// The currently running mutator
132	startedMutator *mutatorInfo
133	// True for any mutators that have already run over all modules
134	finishedMutators map[*mutatorInfo]bool
135
136	// Can be set by tests to avoid invalidating Module values after mutators.
137	skipCloneModulesAfterMutators bool
138
139	// String values that can be used to gate build graph traversal
140	includeTags *IncludeTags
141}
142
143// A container for String keys. The keys can be used to gate build graph traversal
144type IncludeTags map[string]bool
145
146func (tags *IncludeTags) Add(names ...string) {
147	for _, name := range names {
148		(*tags)[name] = true
149	}
150}
151
152func (tags *IncludeTags) Contains(tag string) bool {
153	_, exists := (*tags)[tag]
154	return exists
155}
156
157func (c *Context) AddIncludeTags(names ...string) {
158	c.includeTags.Add(names...)
159}
160
161func (c *Context) ContainsIncludeTag(name string) bool {
162	return c.includeTags.Contains(name)
163}
164
165// An Error describes a problem that was encountered that is related to a
166// particular location in a Blueprints file.
167type BlueprintError struct {
168	Err error            // the error that occurred
169	Pos scanner.Position // the relevant Blueprints file location
170}
171
172// A ModuleError describes a problem that was encountered that is related to a
173// particular module in a Blueprints file
174type ModuleError struct {
175	BlueprintError
176	module *moduleInfo
177}
178
179// A PropertyError describes a problem that was encountered that is related to a
180// particular property in a Blueprints file
181type PropertyError struct {
182	ModuleError
183	property string
184}
185
186func (e *BlueprintError) Error() string {
187	return fmt.Sprintf("%s: %s", e.Pos, e.Err)
188}
189
190func (e *ModuleError) Error() string {
191	return fmt.Sprintf("%s: %s: %s", e.Pos, e.module, e.Err)
192}
193
194func (e *PropertyError) Error() string {
195	return fmt.Sprintf("%s: %s: %s: %s", e.Pos, e.module, e.property, e.Err)
196}
197
198type localBuildActions struct {
199	variables []*localVariable
200	rules     []*localRule
201	buildDefs []*buildDef
202}
203
204type moduleAlias struct {
205	variant variant
206	target  *moduleInfo
207}
208
209func (m *moduleAlias) alias() *moduleAlias              { return m }
210func (m *moduleAlias) module() *moduleInfo              { return nil }
211func (m *moduleAlias) moduleOrAliasTarget() *moduleInfo { return m.target }
212func (m *moduleAlias) moduleOrAliasVariant() variant    { return m.variant }
213
214func (m *moduleInfo) alias() *moduleAlias              { return nil }
215func (m *moduleInfo) module() *moduleInfo              { return m }
216func (m *moduleInfo) moduleOrAliasTarget() *moduleInfo { return m }
217func (m *moduleInfo) moduleOrAliasVariant() variant    { return m.variant }
218
219type moduleOrAlias interface {
220	alias() *moduleAlias
221	module() *moduleInfo
222	moduleOrAliasTarget() *moduleInfo
223	moduleOrAliasVariant() variant
224}
225
226type modulesOrAliases []moduleOrAlias
227
228func (l modulesOrAliases) firstModule() *moduleInfo {
229	for _, moduleOrAlias := range l {
230		if m := moduleOrAlias.module(); m != nil {
231			return m
232		}
233	}
234	panic(fmt.Errorf("no first module!"))
235}
236
237func (l modulesOrAliases) lastModule() *moduleInfo {
238	for i := range l {
239		if m := l[len(l)-1-i].module(); m != nil {
240			return m
241		}
242	}
243	panic(fmt.Errorf("no last module!"))
244}
245
246type moduleGroup struct {
247	name      string
248	ninjaName string
249
250	modules modulesOrAliases
251
252	namespace Namespace
253}
254
255func (group *moduleGroup) moduleOrAliasByVariantName(name string) moduleOrAlias {
256	for _, module := range group.modules {
257		if module.moduleOrAliasVariant().name == name {
258			return module
259		}
260	}
261	return nil
262}
263
264func (group *moduleGroup) moduleByVariantName(name string) *moduleInfo {
265	return group.moduleOrAliasByVariantName(name).module()
266}
267
268type moduleInfo struct {
269	// set during Parse
270	typeName          string
271	factory           ModuleFactory
272	relBlueprintsFile string
273	pos               scanner.Position
274	propertyPos       map[string]scanner.Position
275	createdBy         *moduleInfo
276
277	variant variant
278
279	logicModule Module
280	group       *moduleGroup
281	properties  []interface{}
282
283	// set during ResolveDependencies
284	missingDeps   []string
285	newDirectDeps []depInfo
286
287	// set during updateDependencies
288	reverseDeps []*moduleInfo
289	forwardDeps []*moduleInfo
290	directDeps  []depInfo
291
292	// used by parallelVisit
293	waitingCount int
294
295	// set during each runMutator
296	splitModules modulesOrAliases
297
298	// set during PrepareBuildActions
299	actionDefs localBuildActions
300
301	providers []interface{}
302
303	startedMutator  *mutatorInfo
304	finishedMutator *mutatorInfo
305
306	startedGenerateBuildActions  bool
307	finishedGenerateBuildActions bool
308}
309
310type variant struct {
311	name                 string
312	variations           variationMap
313	dependencyVariations variationMap
314}
315
316type depInfo struct {
317	module *moduleInfo
318	tag    DependencyTag
319}
320
321func (module *moduleInfo) Name() string {
322	// If this is called from a LoadHook (which is run before the module has been registered)
323	// then group will not be set and so the name is retrieved from logicModule.Name().
324	// Usually, using that method is not safe as it does not track renames (group.name does).
325	// However, when called from LoadHook it is safe as there is no way to rename a module
326	// until after the LoadHook has run and the module has been registered.
327	if module.group != nil {
328		return module.group.name
329	} else {
330		return module.logicModule.Name()
331	}
332}
333
334func (module *moduleInfo) String() string {
335	s := fmt.Sprintf("module %q", module.Name())
336	if module.variant.name != "" {
337		s += fmt.Sprintf(" variant %q", module.variant.name)
338	}
339	if module.createdBy != nil {
340		s += fmt.Sprintf(" (created by %s)", module.createdBy)
341	}
342
343	return s
344}
345
346func (module *moduleInfo) namespace() Namespace {
347	return module.group.namespace
348}
349
350// A Variation is a way that a variant of a module differs from other variants of the same module.
351// For example, two variants of the same module might have Variation{"arch","arm"} and
352// Variation{"arch","arm64"}
353type Variation struct {
354	// Mutator is the axis on which this variation applies, i.e. "arch" or "link"
355	Mutator string
356	// Variation is the name of the variation on the axis, i.e. "arm" or "arm64" for arch, or
357	// "shared" or "static" for link.
358	Variation string
359}
360
361// A variationMap stores a map of Mutator to Variation to specify a variant of a module.
362type variationMap map[string]string
363
364func (vm variationMap) clone() variationMap {
365	if vm == nil {
366		return nil
367	}
368	newVm := make(variationMap)
369	for k, v := range vm {
370		newVm[k] = v
371	}
372
373	return newVm
374}
375
376// Compare this variationMap to another one.  Returns true if the every entry in this map
377// exists and has the same value in the other map.
378func (vm variationMap) subsetOf(other variationMap) bool {
379	for k, v1 := range vm {
380		if v2, ok := other[k]; !ok || v1 != v2 {
381			return false
382		}
383	}
384	return true
385}
386
387func (vm variationMap) equal(other variationMap) bool {
388	return reflect.DeepEqual(vm, other)
389}
390
391type singletonInfo struct {
392	// set during RegisterSingletonType
393	factory   SingletonFactory
394	singleton Singleton
395	name      string
396
397	// set during PrepareBuildActions
398	actionDefs localBuildActions
399}
400
401type mutatorInfo struct {
402	// set during RegisterMutator
403	topDownMutator  TopDownMutator
404	bottomUpMutator BottomUpMutator
405	name            string
406	parallel        bool
407}
408
409func newContext() *Context {
410	eventHandler := metrics.EventHandler{}
411	return &Context{
412		Context:            context.Background(),
413		EventHandler:       &eventHandler,
414		moduleFactories:    make(map[string]ModuleFactory),
415		nameInterface:      NewSimpleNameInterface(),
416		moduleInfo:         make(map[Module]*moduleInfo),
417		globs:              make(map[globKey]pathtools.GlobResult),
418		fs:                 pathtools.OsFs,
419		finishedMutators:   make(map[*mutatorInfo]bool),
420		includeTags: &IncludeTags{},
421		outDir:             nil,
422		requiredNinjaMajor: 1,
423		requiredNinjaMinor: 7,
424		requiredNinjaMicro: 0,
425	}
426}
427
428// NewContext creates a new Context object.  The created context initially has
429// no module or singleton factories registered, so the RegisterModuleFactory and
430// RegisterSingletonFactory methods must be called before it can do anything
431// useful.
432func NewContext() *Context {
433	ctx := newContext()
434
435	ctx.RegisterBottomUpMutator("blueprint_deps", blueprintDepsMutator)
436
437	return ctx
438}
439
440// A ModuleFactory function creates a new Module object.  See the
441// Context.RegisterModuleType method for details about how a registered
442// ModuleFactory is used by a Context.
443type ModuleFactory func() (m Module, propertyStructs []interface{})
444
445// RegisterModuleType associates a module type name (which can appear in a
446// Blueprints file) with a Module factory function.  When the given module type
447// name is encountered in a Blueprints file during parsing, the Module factory
448// is invoked to instantiate a new Module object to handle the build action
449// generation for the module.  If a Mutator splits a module into multiple variants,
450// the factory is invoked again to create a new Module for each variant.
451//
452// The module type names given here must be unique for the context.  The factory
453// function should be a named function so that its package and name can be
454// included in the generated Ninja file for debugging purposes.
455//
456// The factory function returns two values.  The first is the newly created
457// Module object.  The second is a slice of pointers to that Module object's
458// properties structs.  Each properties struct is examined when parsing a module
459// definition of this type in a Blueprints file.  Exported fields of the
460// properties structs are automatically set to the property values specified in
461// the Blueprints file.  The properties struct field names determine the name of
462// the Blueprints file properties that are used - the Blueprints property name
463// matches that of the properties struct field name with the first letter
464// converted to lower-case.
465//
466// The fields of the properties struct must be either []string, a string, or
467// bool. The Context will panic if a Module gets instantiated with a properties
468// struct containing a field that is not one these supported types.
469//
470// Any properties that appear in the Blueprints files that are not built-in
471// module properties (such as "name" and "deps") and do not have a corresponding
472// field in the returned module properties struct result in an error during the
473// Context's parse phase.
474//
475// As an example, the follow code:
476//
477//   type myModule struct {
478//       properties struct {
479//           Foo string
480//           Bar []string
481//       }
482//   }
483//
484//   func NewMyModule() (blueprint.Module, []interface{}) {
485//       module := new(myModule)
486//       properties := &module.properties
487//       return module, []interface{}{properties}
488//   }
489//
490//   func main() {
491//       ctx := blueprint.NewContext()
492//       ctx.RegisterModuleType("my_module", NewMyModule)
493//       // ...
494//   }
495//
496// would support parsing a module defined in a Blueprints file as follows:
497//
498//   my_module {
499//       name: "myName",
500//       foo:  "my foo string",
501//       bar:  ["my", "bar", "strings"],
502//   }
503//
504// The factory function may be called from multiple goroutines.  Any accesses
505// to global variables must be synchronized.
506func (c *Context) RegisterModuleType(name string, factory ModuleFactory) {
507	if _, present := c.moduleFactories[name]; present {
508		panic(errors.New("module type name is already registered"))
509	}
510	c.moduleFactories[name] = factory
511}
512
513// A SingletonFactory function creates a new Singleton object.  See the
514// Context.RegisterSingletonType method for details about how a registered
515// SingletonFactory is used by a Context.
516type SingletonFactory func() Singleton
517
518// RegisterSingletonType registers a singleton type that will be invoked to
519// generate build actions.  Each registered singleton type is instantiated
520// and invoked exactly once as part of the generate phase.  Each registered
521// singleton is invoked in registration order.
522//
523// The singleton type names given here must be unique for the context.  The
524// factory function should be a named function so that its package and name can
525// be included in the generated Ninja file for debugging purposes.
526func (c *Context) RegisterSingletonType(name string, factory SingletonFactory) {
527	for _, s := range c.singletonInfo {
528		if s.name == name {
529			panic(errors.New("singleton name is already registered"))
530		}
531	}
532
533	c.singletonInfo = append(c.singletonInfo, &singletonInfo{
534		factory:   factory,
535		singleton: factory(),
536		name:      name,
537	})
538}
539
540// RegisterPreSingletonType registers a presingleton type that will be invoked to
541// generate build actions before any Blueprint files have been read.  Each registered
542// presingleton type is instantiated and invoked exactly once at the beginning of the
543// parse phase.  Each registered presingleton is invoked in registration order.
544//
545// The presingleton type names given here must be unique for the context.  The
546// factory function should be a named function so that its package and name can
547// be included in the generated Ninja file for debugging purposes.
548func (c *Context) RegisterPreSingletonType(name string, factory SingletonFactory) {
549	for _, s := range c.preSingletonInfo {
550		if s.name == name {
551			panic(errors.New("presingleton name is already registered"))
552		}
553	}
554
555	c.preSingletonInfo = append(c.preSingletonInfo, &singletonInfo{
556		factory:   factory,
557		singleton: factory(),
558		name:      name,
559	})
560}
561
562func (c *Context) SetNameInterface(i NameInterface) {
563	c.nameInterface = i
564}
565
566func (c *Context) SetSrcDir(path string) {
567	c.srcDir = path
568	c.fs = pathtools.NewOsFs(path)
569}
570
571func (c *Context) SrcDir() string {
572	return c.srcDir
573}
574
575func singletonPkgPath(singleton Singleton) string {
576	typ := reflect.TypeOf(singleton)
577	for typ.Kind() == reflect.Ptr {
578		typ = typ.Elem()
579	}
580	return typ.PkgPath()
581}
582
583func singletonTypeName(singleton Singleton) string {
584	typ := reflect.TypeOf(singleton)
585	for typ.Kind() == reflect.Ptr {
586		typ = typ.Elem()
587	}
588	return typ.PkgPath() + "." + typ.Name()
589}
590
591// RegisterTopDownMutator registers a mutator that will be invoked to propagate dependency info
592// top-down between Modules.  Each registered mutator is invoked in registration order (mixing
593// TopDownMutators and BottomUpMutators) once per Module, and the invocation on any module will
594// have returned before it is in invoked on any of its dependencies.
595//
596// The mutator type names given here must be unique to all top down mutators in
597// the Context.
598//
599// Returns a MutatorHandle, on which Parallel can be called to set the mutator to visit modules in
600// parallel while maintaining ordering.
601func (c *Context) RegisterTopDownMutator(name string, mutator TopDownMutator) MutatorHandle {
602	for _, m := range c.mutatorInfo {
603		if m.name == name && m.topDownMutator != nil {
604			panic(fmt.Errorf("mutator name %s is already registered", name))
605		}
606	}
607
608	info := &mutatorInfo{
609		topDownMutator: mutator,
610		name:           name,
611	}
612
613	c.mutatorInfo = append(c.mutatorInfo, info)
614
615	return info
616}
617
618// RegisterBottomUpMutator registers a mutator that will be invoked to split Modules into variants.
619// Each registered mutator is invoked in registration order (mixing TopDownMutators and
620// BottomUpMutators) once per Module, will not be invoked on a module until the invocations on all
621// of the modules dependencies have returned.
622//
623// The mutator type names given here must be unique to all bottom up or early
624// mutators in the Context.
625//
626// Returns a MutatorHandle, on which Parallel can be called to set the mutator to visit modules in
627// parallel while maintaining ordering.
628func (c *Context) RegisterBottomUpMutator(name string, mutator BottomUpMutator) MutatorHandle {
629	for _, m := range c.variantMutatorNames {
630		if m == name {
631			panic(fmt.Errorf("mutator name %s is already registered", name))
632		}
633	}
634
635	info := &mutatorInfo{
636		bottomUpMutator: mutator,
637		name:            name,
638	}
639	c.mutatorInfo = append(c.mutatorInfo, info)
640
641	c.variantMutatorNames = append(c.variantMutatorNames, name)
642
643	return info
644}
645
646type MutatorHandle interface {
647	// Set the mutator to visit modules in parallel while maintaining ordering.  Calling any
648	// method on the mutator context is thread-safe, but the mutator must handle synchronization
649	// for any modifications to global state or any modules outside the one it was invoked on.
650	Parallel() MutatorHandle
651}
652
653func (mutator *mutatorInfo) Parallel() MutatorHandle {
654	mutator.parallel = true
655	return mutator
656}
657
658// SetIgnoreUnknownModuleTypes sets the behavior of the context in the case
659// where it encounters an unknown module type while parsing Blueprints files. By
660// default, the context will report unknown module types as an error.  If this
661// method is called with ignoreUnknownModuleTypes set to true then the context
662// will silently ignore unknown module types.
663//
664// This method should generally not be used.  It exists to facilitate the
665// bootstrapping process.
666func (c *Context) SetIgnoreUnknownModuleTypes(ignoreUnknownModuleTypes bool) {
667	c.ignoreUnknownModuleTypes = ignoreUnknownModuleTypes
668}
669
670// SetAllowMissingDependencies changes the behavior of Blueprint to ignore
671// unresolved dependencies.  If the module's GenerateBuildActions calls
672// ModuleContext.GetMissingDependencies Blueprint will not emit any errors
673// for missing dependencies.
674func (c *Context) SetAllowMissingDependencies(allowMissingDependencies bool) {
675	c.allowMissingDependencies = allowMissingDependencies
676}
677
678func (c *Context) SetModuleListFile(listFile string) {
679	c.moduleListFile = listFile
680}
681
682func (c *Context) ListModulePaths(baseDir string) (paths []string, err error) {
683	reader, err := c.fs.Open(c.moduleListFile)
684	if err != nil {
685		return nil, err
686	}
687	defer reader.Close()
688	bytes, err := ioutil.ReadAll(reader)
689	if err != nil {
690		return nil, err
691	}
692	text := string(bytes)
693
694	text = strings.Trim(text, "\n")
695	lines := strings.Split(text, "\n")
696	for i := range lines {
697		lines[i] = filepath.Join(baseDir, lines[i])
698	}
699
700	return lines, nil
701}
702
703// a fileParseContext tells the status of parsing a particular file
704type fileParseContext struct {
705	// name of file
706	fileName string
707
708	// scope to use when resolving variables
709	Scope *parser.Scope
710
711	// pointer to the one in the parent directory
712	parent *fileParseContext
713
714	// is closed once FileHandler has completed for this file
715	doneVisiting chan struct{}
716}
717
718// ParseBlueprintsFiles parses a set of Blueprints files starting with the file
719// at rootFile.  When it encounters a Blueprints file with a set of subdirs
720// listed it recursively parses any Blueprints files found in those
721// subdirectories.
722//
723// If no errors are encountered while parsing the files, the list of paths on
724// which the future output will depend is returned.  This list will include both
725// Blueprints file paths as well as directory paths for cases where wildcard
726// subdirs are found.
727func (c *Context) ParseBlueprintsFiles(rootFile string,
728	config interface{}) (deps []string, errs []error) {
729
730	baseDir := filepath.Dir(rootFile)
731	pathsToParse, err := c.ListModulePaths(baseDir)
732	if err != nil {
733		return nil, []error{err}
734	}
735	return c.ParseFileList(baseDir, pathsToParse, config)
736}
737
738// Returns a boolean for whether this file should be analyzed
739// Evaluates to true if the file either
740// 1. does not contain a blueprint_package_includes
741// 2. contains a blueprint_package_includes and all requested tags are set
742// This should be processed before adding any modules to the build graph
743func shouldVisitFile(c *Context, file *parser.File) (bool, []error) {
744	for _, def := range file.Defs {
745		switch def := def.(type) {
746		case *parser.Module:
747			if def.Type != "blueprint_package_includes" {
748				continue
749			}
750			module, errs := processModuleDef(def, file.Name, c.moduleFactories, nil, c.ignoreUnknownModuleTypes)
751			if len(errs) > 0 {
752				// This file contains errors in blueprint_package_includes
753				// Visit anyways so that we can report errors on other modules in the file
754				return true, errs
755			}
756			logicModule, _ := c.cloneLogicModule(module)
757			pi := logicModule.(*PackageIncludes)
758			return pi.MatchesIncludeTags(c), []error{}
759		}
760	}
761	return true, []error{}
762}
763
764
765func (c *Context) ParseFileList(rootDir string, filePaths []string,
766	config interface{}) (deps []string, errs []error) {
767
768	if len(filePaths) < 1 {
769		return nil, []error{fmt.Errorf("no paths provided to parse")}
770	}
771
772	c.dependenciesReady = false
773
774	type newModuleInfo struct {
775		*moduleInfo
776		deps  []string
777		added chan<- struct{}
778	}
779
780	moduleCh := make(chan newModuleInfo)
781	errsCh := make(chan []error)
782	doneCh := make(chan struct{})
783	var numErrs uint32
784	var numGoroutines int32
785
786	// handler must be reentrant
787	handleOneFile := func(file *parser.File) {
788		if atomic.LoadUint32(&numErrs) > maxErrors {
789			return
790		}
791
792		addedCh := make(chan struct{})
793
794		var scopedModuleFactories map[string]ModuleFactory
795
796		var addModule func(module *moduleInfo) []error
797		addModule = func(module *moduleInfo) []error {
798			// Run any load hooks immediately before it is sent to the moduleCh and is
799			// registered by name. This allows load hooks to set and/or modify any aspect
800			// of the module (including names) using information that is not available when
801			// the module factory is called.
802			newModules, newDeps, errs := runAndRemoveLoadHooks(c, config, module, &scopedModuleFactories)
803			if len(errs) > 0 {
804				return errs
805			}
806
807			moduleCh <- newModuleInfo{module, newDeps, addedCh}
808			<-addedCh
809			for _, n := range newModules {
810				errs = addModule(n)
811				if len(errs) > 0 {
812					return errs
813				}
814			}
815			return nil
816		}
817		shouldVisit, errs := shouldVisitFile(c, file)
818		if len(errs) > 0 {
819			atomic.AddUint32(&numErrs, uint32(len(errs)))
820			errsCh <- errs
821		}
822		if !shouldVisit {
823			// TODO: Write a file that lists the skipped bp files
824			return
825		}
826
827		for _, def := range file.Defs {
828			switch def := def.(type) {
829			case *parser.Module:
830				module, errs := processModuleDef(def, file.Name, c.moduleFactories, scopedModuleFactories, c.ignoreUnknownModuleTypes)
831				if len(errs) == 0 && module != nil {
832					errs = addModule(module)
833				}
834
835				if len(errs) > 0 {
836					atomic.AddUint32(&numErrs, uint32(len(errs)))
837					errsCh <- errs
838				}
839
840			case *parser.Assignment:
841				// Already handled via Scope object
842			default:
843				panic("unknown definition type")
844			}
845
846		}
847	}
848
849	atomic.AddInt32(&numGoroutines, 1)
850	go func() {
851		var errs []error
852		deps, errs = c.WalkBlueprintsFiles(rootDir, filePaths, handleOneFile)
853		if len(errs) > 0 {
854			errsCh <- errs
855		}
856		doneCh <- struct{}{}
857	}()
858
859	var hookDeps []string
860loop:
861	for {
862		select {
863		case newErrs := <-errsCh:
864			errs = append(errs, newErrs...)
865		case module := <-moduleCh:
866			newErrs := c.addModule(module.moduleInfo)
867			hookDeps = append(hookDeps, module.deps...)
868			if module.added != nil {
869				module.added <- struct{}{}
870			}
871			if len(newErrs) > 0 {
872				errs = append(errs, newErrs...)
873			}
874		case <-doneCh:
875			n := atomic.AddInt32(&numGoroutines, -1)
876			if n == 0 {
877				break loop
878			}
879		}
880	}
881
882	deps = append(deps, hookDeps...)
883	return deps, errs
884}
885
886type FileHandler func(*parser.File)
887
888// WalkBlueprintsFiles walks a set of Blueprints files starting with the given filepaths,
889// calling the given file handler on each
890//
891// When WalkBlueprintsFiles encounters a Blueprints file with a set of subdirs listed,
892// it recursively parses any Blueprints files found in those subdirectories.
893//
894// If any of the file paths is an ancestor directory of any other of file path, the ancestor
895// will be parsed and visited first.
896//
897// the file handler will be called from a goroutine, so it must be reentrant.
898//
899// If no errors are encountered while parsing the files, the list of paths on
900// which the future output will depend is returned.  This list will include both
901// Blueprints file paths as well as directory paths for cases where wildcard
902// subdirs are found.
903//
904// visitor will be called asynchronously, and will only be called once visitor for each
905// ancestor directory has completed.
906//
907// WalkBlueprintsFiles will not return until all calls to visitor have returned.
908func (c *Context) WalkBlueprintsFiles(rootDir string, filePaths []string,
909	visitor FileHandler) (deps []string, errs []error) {
910
911	// make a mapping from ancestors to their descendants to facilitate parsing ancestors first
912	descendantsMap, err := findBlueprintDescendants(filePaths)
913	if err != nil {
914		panic(err.Error())
915	}
916	blueprintsSet := make(map[string]bool)
917
918	// Channels to receive data back from openAndParse goroutines
919	blueprintsCh := make(chan fileParseContext)
920	errsCh := make(chan []error)
921	depsCh := make(chan string)
922
923	// Channel to notify main loop that a openAndParse goroutine has finished
924	doneParsingCh := make(chan fileParseContext)
925
926	// Number of outstanding goroutines to wait for
927	activeCount := 0
928	var pending []fileParseContext
929	tooManyErrors := false
930
931	// Limit concurrent calls to parseBlueprintFiles to 200
932	// Darwin has a default limit of 256 open files
933	maxActiveCount := 200
934
935	// count the number of pending calls to visitor()
936	visitorWaitGroup := sync.WaitGroup{}
937
938	startParseBlueprintsFile := func(blueprint fileParseContext) {
939		if blueprintsSet[blueprint.fileName] {
940			return
941		}
942		blueprintsSet[blueprint.fileName] = true
943		activeCount++
944		deps = append(deps, blueprint.fileName)
945		visitorWaitGroup.Add(1)
946		go func() {
947			file, blueprints, deps, errs := c.openAndParse(blueprint.fileName, blueprint.Scope, rootDir,
948				&blueprint)
949			if len(errs) > 0 {
950				errsCh <- errs
951			}
952			for _, blueprint := range blueprints {
953				blueprintsCh <- blueprint
954			}
955			for _, dep := range deps {
956				depsCh <- dep
957			}
958			doneParsingCh <- blueprint
959
960			if blueprint.parent != nil && blueprint.parent.doneVisiting != nil {
961				// wait for visitor() of parent to complete
962				<-blueprint.parent.doneVisiting
963			}
964
965			if len(errs) == 0 {
966				// process this file
967				visitor(file)
968			}
969			if blueprint.doneVisiting != nil {
970				close(blueprint.doneVisiting)
971			}
972			visitorWaitGroup.Done()
973		}()
974	}
975
976	foundParseableBlueprint := func(blueprint fileParseContext) {
977		if activeCount >= maxActiveCount {
978			pending = append(pending, blueprint)
979		} else {
980			startParseBlueprintsFile(blueprint)
981		}
982	}
983
984	startParseDescendants := func(blueprint fileParseContext) {
985		descendants, hasDescendants := descendantsMap[blueprint.fileName]
986		if hasDescendants {
987			for _, descendant := range descendants {
988				foundParseableBlueprint(fileParseContext{descendant, parser.NewScope(blueprint.Scope), &blueprint, make(chan struct{})})
989			}
990		}
991	}
992
993	// begin parsing any files that have no ancestors
994	startParseDescendants(fileParseContext{"", parser.NewScope(nil), nil, nil})
995
996loop:
997	for {
998		if len(errs) > maxErrors {
999			tooManyErrors = true
1000		}
1001
1002		select {
1003		case newErrs := <-errsCh:
1004			errs = append(errs, newErrs...)
1005		case dep := <-depsCh:
1006			deps = append(deps, dep)
1007		case blueprint := <-blueprintsCh:
1008			if tooManyErrors {
1009				continue
1010			}
1011			foundParseableBlueprint(blueprint)
1012		case blueprint := <-doneParsingCh:
1013			activeCount--
1014			if !tooManyErrors {
1015				startParseDescendants(blueprint)
1016			}
1017			if activeCount < maxActiveCount && len(pending) > 0 {
1018				// start to process the next one from the queue
1019				next := pending[len(pending)-1]
1020				pending = pending[:len(pending)-1]
1021				startParseBlueprintsFile(next)
1022			}
1023			if activeCount == 0 {
1024				break loop
1025			}
1026		}
1027	}
1028
1029	sort.Strings(deps)
1030
1031	// wait for every visitor() to complete
1032	visitorWaitGroup.Wait()
1033
1034	return
1035}
1036
1037// MockFileSystem causes the Context to replace all reads with accesses to the provided map of
1038// filenames to contents stored as a byte slice.
1039func (c *Context) MockFileSystem(files map[string][]byte) {
1040	// look for a module list file
1041	_, ok := files[MockModuleListFile]
1042	if !ok {
1043		// no module list file specified; find every file named Blueprints
1044		pathsToParse := []string{}
1045		for candidate := range files {
1046			if filepath.Base(candidate) == "Android.bp" {
1047				pathsToParse = append(pathsToParse, candidate)
1048			}
1049		}
1050		if len(pathsToParse) < 1 {
1051			panic(fmt.Sprintf("No Blueprints files found in mock filesystem: %v\n", files))
1052		}
1053		// put the list of Blueprints files into a list file
1054		files[MockModuleListFile] = []byte(strings.Join(pathsToParse, "\n"))
1055	}
1056	c.SetModuleListFile(MockModuleListFile)
1057
1058	// mock the filesystem
1059	c.fs = pathtools.MockFs(files)
1060}
1061
1062func (c *Context) SetFs(fs pathtools.FileSystem) {
1063	c.fs = fs
1064}
1065
1066// openAndParse opens and parses a single Blueprints file, and returns the results
1067func (c *Context) openAndParse(filename string, scope *parser.Scope, rootDir string,
1068	parent *fileParseContext) (file *parser.File,
1069	subBlueprints []fileParseContext, deps []string, errs []error) {
1070
1071	f, err := c.fs.Open(filename)
1072	if err != nil {
1073		// couldn't open the file; see if we can provide a clearer error than "could not open file"
1074		stats, statErr := c.fs.Lstat(filename)
1075		if statErr == nil {
1076			isSymlink := stats.Mode()&os.ModeSymlink != 0
1077			if isSymlink {
1078				err = fmt.Errorf("could not open symlink %v : %v", filename, err)
1079				target, readlinkErr := os.Readlink(filename)
1080				if readlinkErr == nil {
1081					_, targetStatsErr := c.fs.Lstat(target)
1082					if targetStatsErr != nil {
1083						err = fmt.Errorf("could not open symlink %v; its target (%v) cannot be opened", filename, target)
1084					}
1085				}
1086			} else {
1087				err = fmt.Errorf("%v exists but could not be opened: %v", filename, err)
1088			}
1089		}
1090		return nil, nil, nil, []error{err}
1091	}
1092
1093	func() {
1094		defer func() {
1095			err = f.Close()
1096			if err != nil {
1097				errs = append(errs, err)
1098			}
1099		}()
1100		file, subBlueprints, errs = c.parseOne(rootDir, filename, f, scope, parent)
1101	}()
1102
1103	if len(errs) > 0 {
1104		return nil, nil, nil, errs
1105	}
1106
1107	for _, b := range subBlueprints {
1108		deps = append(deps, b.fileName)
1109	}
1110
1111	return file, subBlueprints, deps, nil
1112}
1113
1114// parseOne parses a single Blueprints file from the given reader, creating Module
1115// objects for each of the module definitions encountered.  If the Blueprints
1116// file contains an assignment to the "subdirs" variable, then the
1117// subdirectories listed are searched for Blueprints files returned in the
1118// subBlueprints return value.  If the Blueprints file contains an assignment
1119// to the "build" variable, then the file listed are returned in the
1120// subBlueprints return value.
1121//
1122// rootDir specifies the path to the root directory of the source tree, while
1123// filename specifies the path to the Blueprints file.  These paths are used for
1124// error reporting and for determining the module's directory.
1125func (c *Context) parseOne(rootDir, filename string, reader io.Reader,
1126	scope *parser.Scope, parent *fileParseContext) (file *parser.File, subBlueprints []fileParseContext, errs []error) {
1127
1128	relBlueprintsFile, err := filepath.Rel(rootDir, filename)
1129	if err != nil {
1130		return nil, nil, []error{err}
1131	}
1132
1133	scope.Remove("subdirs")
1134	scope.Remove("optional_subdirs")
1135	scope.Remove("build")
1136	file, errs = parser.ParseAndEval(filename, reader, scope)
1137	if len(errs) > 0 {
1138		for i, err := range errs {
1139			if parseErr, ok := err.(*parser.ParseError); ok {
1140				err = &BlueprintError{
1141					Err: parseErr.Err,
1142					Pos: parseErr.Pos,
1143				}
1144				errs[i] = err
1145			}
1146		}
1147
1148		// If there were any parse errors don't bother trying to interpret the
1149		// result.
1150		return nil, nil, errs
1151	}
1152	file.Name = relBlueprintsFile
1153
1154	build, buildPos, err := getLocalStringListFromScope(scope, "build")
1155	if err != nil {
1156		errs = append(errs, err)
1157	}
1158	for _, buildEntry := range build {
1159		if strings.Contains(buildEntry, "/") {
1160			errs = append(errs, &BlueprintError{
1161				Err: fmt.Errorf("illegal value %v. The '/' character is not permitted", buildEntry),
1162				Pos: buildPos,
1163			})
1164		}
1165	}
1166
1167	if err != nil {
1168		errs = append(errs, err)
1169	}
1170
1171	var blueprints []string
1172
1173	newBlueprints, newErrs := c.findBuildBlueprints(filepath.Dir(filename), build, buildPos)
1174	blueprints = append(blueprints, newBlueprints...)
1175	errs = append(errs, newErrs...)
1176
1177	subBlueprintsAndScope := make([]fileParseContext, len(blueprints))
1178	for i, b := range blueprints {
1179		subBlueprintsAndScope[i] = fileParseContext{b, parser.NewScope(scope), parent, make(chan struct{})}
1180	}
1181	return file, subBlueprintsAndScope, errs
1182}
1183
1184func (c *Context) findBuildBlueprints(dir string, build []string,
1185	buildPos scanner.Position) ([]string, []error) {
1186
1187	var blueprints []string
1188	var errs []error
1189
1190	for _, file := range build {
1191		pattern := filepath.Join(dir, file)
1192		var matches []string
1193		var err error
1194
1195		matches, err = c.glob(pattern, nil)
1196
1197		if err != nil {
1198			errs = append(errs, &BlueprintError{
1199				Err: fmt.Errorf("%q: %s", pattern, err.Error()),
1200				Pos: buildPos,
1201			})
1202			continue
1203		}
1204
1205		if len(matches) == 0 {
1206			errs = append(errs, &BlueprintError{
1207				Err: fmt.Errorf("%q: not found", pattern),
1208				Pos: buildPos,
1209			})
1210		}
1211
1212		for _, foundBlueprints := range matches {
1213			if strings.HasSuffix(foundBlueprints, "/") {
1214				errs = append(errs, &BlueprintError{
1215					Err: fmt.Errorf("%q: is a directory", foundBlueprints),
1216					Pos: buildPos,
1217				})
1218			}
1219			blueprints = append(blueprints, foundBlueprints)
1220		}
1221	}
1222
1223	return blueprints, errs
1224}
1225
1226func (c *Context) findSubdirBlueprints(dir string, subdirs []string, subdirsPos scanner.Position,
1227	subBlueprintsName string, optional bool) ([]string, []error) {
1228
1229	var blueprints []string
1230	var errs []error
1231
1232	for _, subdir := range subdirs {
1233		pattern := filepath.Join(dir, subdir, subBlueprintsName)
1234		var matches []string
1235		var err error
1236
1237		matches, err = c.glob(pattern, nil)
1238
1239		if err != nil {
1240			errs = append(errs, &BlueprintError{
1241				Err: fmt.Errorf("%q: %s", pattern, err.Error()),
1242				Pos: subdirsPos,
1243			})
1244			continue
1245		}
1246
1247		if len(matches) == 0 && !optional {
1248			errs = append(errs, &BlueprintError{
1249				Err: fmt.Errorf("%q: not found", pattern),
1250				Pos: subdirsPos,
1251			})
1252		}
1253
1254		for _, subBlueprints := range matches {
1255			if strings.HasSuffix(subBlueprints, "/") {
1256				errs = append(errs, &BlueprintError{
1257					Err: fmt.Errorf("%q: is a directory", subBlueprints),
1258					Pos: subdirsPos,
1259				})
1260			}
1261			blueprints = append(blueprints, subBlueprints)
1262		}
1263	}
1264
1265	return blueprints, errs
1266}
1267
1268func getLocalStringListFromScope(scope *parser.Scope, v string) ([]string, scanner.Position, error) {
1269	if assignment, local := scope.Get(v); assignment == nil || !local {
1270		return nil, scanner.Position{}, nil
1271	} else {
1272		switch value := assignment.Value.Eval().(type) {
1273		case *parser.List:
1274			ret := make([]string, 0, len(value.Values))
1275
1276			for _, listValue := range value.Values {
1277				s, ok := listValue.(*parser.String)
1278				if !ok {
1279					// The parser should not produce this.
1280					panic("non-string value found in list")
1281				}
1282
1283				ret = append(ret, s.Value)
1284			}
1285
1286			return ret, assignment.EqualsPos, nil
1287		case *parser.Bool, *parser.String:
1288			return nil, scanner.Position{}, &BlueprintError{
1289				Err: fmt.Errorf("%q must be a list of strings", v),
1290				Pos: assignment.EqualsPos,
1291			}
1292		default:
1293			panic(fmt.Errorf("unknown value type: %d", assignment.Value.Type()))
1294		}
1295	}
1296}
1297
1298func getStringFromScope(scope *parser.Scope, v string) (string, scanner.Position, error) {
1299	if assignment, _ := scope.Get(v); assignment == nil {
1300		return "", scanner.Position{}, nil
1301	} else {
1302		switch value := assignment.Value.Eval().(type) {
1303		case *parser.String:
1304			return value.Value, assignment.EqualsPos, nil
1305		case *parser.Bool, *parser.List:
1306			return "", scanner.Position{}, &BlueprintError{
1307				Err: fmt.Errorf("%q must be a string", v),
1308				Pos: assignment.EqualsPos,
1309			}
1310		default:
1311			panic(fmt.Errorf("unknown value type: %d", assignment.Value.Type()))
1312		}
1313	}
1314}
1315
1316// Clones a build logic module by calling the factory method for its module type, and then cloning
1317// property values.  Any values stored in the module object that are not stored in properties
1318// structs will be lost.
1319func (c *Context) cloneLogicModule(origModule *moduleInfo) (Module, []interface{}) {
1320	newLogicModule, newProperties := origModule.factory()
1321
1322	if len(newProperties) != len(origModule.properties) {
1323		panic("mismatched properties array length in " + origModule.Name())
1324	}
1325
1326	for i := range newProperties {
1327		dst := reflect.ValueOf(newProperties[i])
1328		src := reflect.ValueOf(origModule.properties[i])
1329
1330		proptools.CopyProperties(dst, src)
1331	}
1332
1333	return newLogicModule, newProperties
1334}
1335
1336func newVariant(module *moduleInfo, mutatorName string, variationName string,
1337	local bool) variant {
1338
1339	newVariantName := module.variant.name
1340	if variationName != "" {
1341		if newVariantName == "" {
1342			newVariantName = variationName
1343		} else {
1344			newVariantName += "_" + variationName
1345		}
1346	}
1347
1348	newVariations := module.variant.variations.clone()
1349	if newVariations == nil {
1350		newVariations = make(variationMap)
1351	}
1352	newVariations[mutatorName] = variationName
1353
1354	newDependencyVariations := module.variant.dependencyVariations.clone()
1355	if !local {
1356		if newDependencyVariations == nil {
1357			newDependencyVariations = make(variationMap)
1358		}
1359		newDependencyVariations[mutatorName] = variationName
1360	}
1361
1362	return variant{newVariantName, newVariations, newDependencyVariations}
1363}
1364
1365func (c *Context) createVariations(origModule *moduleInfo, mutatorName string,
1366	defaultVariationName *string, variationNames []string, local bool) (modulesOrAliases, []error) {
1367
1368	if len(variationNames) == 0 {
1369		panic(fmt.Errorf("mutator %q passed zero-length variation list for module %q",
1370			mutatorName, origModule.Name()))
1371	}
1372
1373	var newModules modulesOrAliases
1374
1375	var errs []error
1376
1377	for i, variationName := range variationNames {
1378		var newLogicModule Module
1379		var newProperties []interface{}
1380
1381		if i == 0 {
1382			// Reuse the existing module for the first new variant
1383			// This both saves creating a new module, and causes the insertion in c.moduleInfo below
1384			// with logicModule as the key to replace the original entry in c.moduleInfo
1385			newLogicModule, newProperties = origModule.logicModule, origModule.properties
1386		} else {
1387			newLogicModule, newProperties = c.cloneLogicModule(origModule)
1388		}
1389
1390		m := *origModule
1391		newModule := &m
1392		newModule.directDeps = append([]depInfo(nil), origModule.directDeps...)
1393		newModule.reverseDeps = nil
1394		newModule.forwardDeps = nil
1395		newModule.logicModule = newLogicModule
1396		newModule.variant = newVariant(origModule, mutatorName, variationName, local)
1397		newModule.properties = newProperties
1398		newModule.providers = append([]interface{}(nil), origModule.providers...)
1399
1400		newModules = append(newModules, newModule)
1401
1402		newErrs := c.convertDepsToVariation(newModule, mutatorName, variationName, defaultVariationName)
1403		if len(newErrs) > 0 {
1404			errs = append(errs, newErrs...)
1405		}
1406	}
1407
1408	// Mark original variant as invalid.  Modules that depend on this module will still
1409	// depend on origModule, but we'll fix it when the mutator is called on them.
1410	origModule.logicModule = nil
1411	origModule.splitModules = newModules
1412
1413	atomic.AddUint32(&c.depsModified, 1)
1414
1415	return newModules, errs
1416}
1417
1418func (c *Context) convertDepsToVariation(module *moduleInfo,
1419	mutatorName, variationName string, defaultVariationName *string) (errs []error) {
1420
1421	for i, dep := range module.directDeps {
1422		if dep.module.logicModule == nil {
1423			var newDep *moduleInfo
1424			for _, m := range dep.module.splitModules {
1425				if m.moduleOrAliasVariant().variations[mutatorName] == variationName {
1426					newDep = m.moduleOrAliasTarget()
1427					break
1428				}
1429			}
1430			if newDep == nil && defaultVariationName != nil {
1431				// give it a second chance; match with defaultVariationName
1432				for _, m := range dep.module.splitModules {
1433					if m.moduleOrAliasVariant().variations[mutatorName] == *defaultVariationName {
1434						newDep = m.moduleOrAliasTarget()
1435						break
1436					}
1437				}
1438			}
1439			if newDep == nil {
1440				errs = append(errs, &BlueprintError{
1441					Err: fmt.Errorf("failed to find variation %q for module %q needed by %q",
1442						variationName, dep.module.Name(), module.Name()),
1443					Pos: module.pos,
1444				})
1445				continue
1446			}
1447			module.directDeps[i].module = newDep
1448		}
1449	}
1450
1451	return errs
1452}
1453
1454func (c *Context) prettyPrintVariant(variations variationMap) string {
1455	names := make([]string, 0, len(variations))
1456	for _, m := range c.variantMutatorNames {
1457		if v, ok := variations[m]; ok {
1458			names = append(names, m+":"+v)
1459		}
1460	}
1461
1462	return strings.Join(names, ",")
1463}
1464
1465func (c *Context) prettyPrintGroupVariants(group *moduleGroup) string {
1466	var variants []string
1467	for _, moduleOrAlias := range group.modules {
1468		if mod := moduleOrAlias.module(); mod != nil {
1469			variants = append(variants, c.prettyPrintVariant(mod.variant.variations))
1470		} else if alias := moduleOrAlias.alias(); alias != nil {
1471			variants = append(variants, c.prettyPrintVariant(alias.variant.variations)+
1472				" (alias to "+c.prettyPrintVariant(alias.target.variant.variations)+")")
1473		}
1474	}
1475	return strings.Join(variants, "\n  ")
1476}
1477
1478func newModule(factory ModuleFactory) *moduleInfo {
1479	logicModule, properties := factory()
1480
1481	return &moduleInfo{
1482		logicModule: logicModule,
1483		factory:     factory,
1484		properties:  properties,
1485	}
1486}
1487
1488func processModuleDef(moduleDef *parser.Module,
1489	relBlueprintsFile string, moduleFactories, scopedModuleFactories map[string]ModuleFactory, ignoreUnknownModuleTypes bool) (*moduleInfo, []error) {
1490
1491	factory, ok := moduleFactories[moduleDef.Type]
1492	if !ok && scopedModuleFactories != nil {
1493		factory, ok = scopedModuleFactories[moduleDef.Type]
1494	}
1495	if !ok {
1496		if ignoreUnknownModuleTypes {
1497			return nil, nil
1498		}
1499
1500		return nil, []error{
1501			&BlueprintError{
1502				Err: fmt.Errorf("unrecognized module type %q", moduleDef.Type),
1503				Pos: moduleDef.TypePos,
1504			},
1505		}
1506	}
1507
1508	module := newModule(factory)
1509	module.typeName = moduleDef.Type
1510
1511	module.relBlueprintsFile = relBlueprintsFile
1512
1513	propertyMap, errs := proptools.UnpackProperties(moduleDef.Properties, module.properties...)
1514	if len(errs) > 0 {
1515		for i, err := range errs {
1516			if unpackErr, ok := err.(*proptools.UnpackError); ok {
1517				err = &BlueprintError{
1518					Err: unpackErr.Err,
1519					Pos: unpackErr.Pos,
1520				}
1521				errs[i] = err
1522			}
1523		}
1524		return nil, errs
1525	}
1526
1527	module.pos = moduleDef.TypePos
1528	module.propertyPos = make(map[string]scanner.Position)
1529	for name, propertyDef := range propertyMap {
1530		module.propertyPos[name] = propertyDef.ColonPos
1531	}
1532
1533	return module, nil
1534}
1535
1536func (c *Context) addModule(module *moduleInfo) []error {
1537	name := module.logicModule.Name()
1538	if name == "" {
1539		return []error{
1540			&BlueprintError{
1541				Err: fmt.Errorf("property 'name' is missing from a module"),
1542				Pos: module.pos,
1543			},
1544		}
1545	}
1546	c.moduleInfo[module.logicModule] = module
1547
1548	group := &moduleGroup{
1549		name:    name,
1550		modules: modulesOrAliases{module},
1551	}
1552	module.group = group
1553	namespace, errs := c.nameInterface.NewModule(
1554		newNamespaceContext(module),
1555		ModuleGroup{moduleGroup: group},
1556		module.logicModule)
1557	if len(errs) > 0 {
1558		for i := range errs {
1559			errs[i] = &BlueprintError{Err: errs[i], Pos: module.pos}
1560		}
1561		return errs
1562	}
1563	group.namespace = namespace
1564
1565	c.moduleGroups = append(c.moduleGroups, group)
1566
1567	return nil
1568}
1569
1570// ResolveDependencies checks that the dependencies specified by all of the
1571// modules defined in the parsed Blueprints files are valid.  This means that
1572// the modules depended upon are defined and that no circular dependencies
1573// exist.
1574func (c *Context) ResolveDependencies(config interface{}) (deps []string, errs []error) {
1575	c.BeginEvent("resolve_deps")
1576	defer c.EndEvent("resolve_deps")
1577	return c.resolveDependencies(c.Context, config)
1578}
1579
1580func (c *Context) resolveDependencies(ctx context.Context, config interface{}) (deps []string, errs []error) {
1581	pprof.Do(ctx, pprof.Labels("blueprint", "ResolveDependencies"), func(ctx context.Context) {
1582		c.initProviders()
1583
1584		c.liveGlobals = newLiveTracker(config)
1585
1586		deps, errs = c.generateSingletonBuildActions(config, c.preSingletonInfo, c.liveGlobals)
1587		if len(errs) > 0 {
1588			return
1589		}
1590
1591		errs = c.updateDependencies()
1592		if len(errs) > 0 {
1593			return
1594		}
1595
1596		var mutatorDeps []string
1597		mutatorDeps, errs = c.runMutators(ctx, config)
1598		if len(errs) > 0 {
1599			return
1600		}
1601		deps = append(deps, mutatorDeps...)
1602
1603		if !c.skipCloneModulesAfterMutators {
1604			c.cloneModules()
1605		}
1606
1607		c.dependenciesReady = true
1608	})
1609
1610	if len(errs) > 0 {
1611		return nil, errs
1612	}
1613
1614	return deps, nil
1615}
1616
1617// Default dependencies handling.  If the module implements the (deprecated)
1618// DynamicDependerModule interface then this set consists of the union of those
1619// module names returned by its DynamicDependencies method and those added by calling
1620// AddDependencies or AddVariationDependencies on DynamicDependencyModuleContext.
1621func blueprintDepsMutator(ctx BottomUpMutatorContext) {
1622	if dynamicDepender, ok := ctx.Module().(DynamicDependerModule); ok {
1623		func() {
1624			defer func() {
1625				if r := recover(); r != nil {
1626					ctx.error(newPanicErrorf(r, "DynamicDependencies for %s", ctx.moduleInfo()))
1627				}
1628			}()
1629			dynamicDeps := dynamicDepender.DynamicDependencies(ctx)
1630
1631			if ctx.Failed() {
1632				return
1633			}
1634
1635			ctx.AddDependency(ctx.Module(), nil, dynamicDeps...)
1636		}()
1637	}
1638}
1639
1640// findExactVariantOrSingle searches the moduleGroup for a module with the same variant as module,
1641// and returns the matching module, or nil if one is not found.  A group with exactly one module
1642// is always considered matching.
1643func findExactVariantOrSingle(module *moduleInfo, possible *moduleGroup, reverse bool) *moduleInfo {
1644	found, _ := findVariant(module, possible, nil, false, reverse)
1645	if found == nil {
1646		for _, moduleOrAlias := range possible.modules {
1647			if m := moduleOrAlias.module(); m != nil {
1648				if found != nil {
1649					// more than one possible match, give up
1650					return nil
1651				}
1652				found = m
1653			}
1654		}
1655	}
1656	return found
1657}
1658
1659func (c *Context) addDependency(module *moduleInfo, tag DependencyTag, depName string) (*moduleInfo, []error) {
1660	if _, ok := tag.(BaseDependencyTag); ok {
1661		panic("BaseDependencyTag is not allowed to be used directly!")
1662	}
1663
1664	if depName == module.Name() {
1665		return nil, []error{&BlueprintError{
1666			Err: fmt.Errorf("%q depends on itself", depName),
1667			Pos: module.pos,
1668		}}
1669	}
1670
1671	possibleDeps := c.moduleGroupFromName(depName, module.namespace())
1672	if possibleDeps == nil {
1673		return nil, c.discoveredMissingDependencies(module, depName, nil)
1674	}
1675
1676	if m := findExactVariantOrSingle(module, possibleDeps, false); m != nil {
1677		module.newDirectDeps = append(module.newDirectDeps, depInfo{m, tag})
1678		atomic.AddUint32(&c.depsModified, 1)
1679		return m, nil
1680	}
1681
1682	if c.allowMissingDependencies {
1683		// Allow missing variants.
1684		return nil, c.discoveredMissingDependencies(module, depName, module.variant.dependencyVariations)
1685	}
1686
1687	return nil, []error{&BlueprintError{
1688		Err: fmt.Errorf("dependency %q of %q missing variant:\n  %s\navailable variants:\n  %s",
1689			depName, module.Name(),
1690			c.prettyPrintVariant(module.variant.dependencyVariations),
1691			c.prettyPrintGroupVariants(possibleDeps)),
1692		Pos: module.pos,
1693	}}
1694}
1695
1696func (c *Context) findReverseDependency(module *moduleInfo, destName string) (*moduleInfo, []error) {
1697	if destName == module.Name() {
1698		return nil, []error{&BlueprintError{
1699			Err: fmt.Errorf("%q depends on itself", destName),
1700			Pos: module.pos,
1701		}}
1702	}
1703
1704	possibleDeps := c.moduleGroupFromName(destName, module.namespace())
1705	if possibleDeps == nil {
1706		return nil, []error{&BlueprintError{
1707			Err: fmt.Errorf("%q has a reverse dependency on undefined module %q",
1708				module.Name(), destName),
1709			Pos: module.pos,
1710		}}
1711	}
1712
1713	if m := findExactVariantOrSingle(module, possibleDeps, true); m != nil {
1714		return m, nil
1715	}
1716
1717	if c.allowMissingDependencies {
1718		// Allow missing variants.
1719		return module, c.discoveredMissingDependencies(module, destName, module.variant.dependencyVariations)
1720	}
1721
1722	return nil, []error{&BlueprintError{
1723		Err: fmt.Errorf("reverse dependency %q of %q missing variant:\n  %s\navailable variants:\n  %s",
1724			destName, module.Name(),
1725			c.prettyPrintVariant(module.variant.dependencyVariations),
1726			c.prettyPrintGroupVariants(possibleDeps)),
1727		Pos: module.pos,
1728	}}
1729}
1730
1731func findVariant(module *moduleInfo, possibleDeps *moduleGroup, variations []Variation, far bool, reverse bool) (*moduleInfo, variationMap) {
1732	// We can't just append variant.Variant to module.dependencyVariant.variantName and
1733	// compare the strings because the result won't be in mutator registration order.
1734	// Create a new map instead, and then deep compare the maps.
1735	var newVariant variationMap
1736	if !far {
1737		if !reverse {
1738			// For forward dependency, ignore local variants by matching against
1739			// dependencyVariant which doesn't have the local variants
1740			newVariant = module.variant.dependencyVariations.clone()
1741		} else {
1742			// For reverse dependency, use all the variants
1743			newVariant = module.variant.variations.clone()
1744		}
1745	}
1746	for _, v := range variations {
1747		if newVariant == nil {
1748			newVariant = make(variationMap)
1749		}
1750		newVariant[v.Mutator] = v.Variation
1751	}
1752
1753	check := func(variant variationMap) bool {
1754		if far {
1755			return newVariant.subsetOf(variant)
1756		} else {
1757			return variant.equal(newVariant)
1758		}
1759	}
1760
1761	var foundDep *moduleInfo
1762	for _, m := range possibleDeps.modules {
1763		if check(m.moduleOrAliasVariant().variations) {
1764			foundDep = m.moduleOrAliasTarget()
1765			break
1766		}
1767	}
1768
1769	return foundDep, newVariant
1770}
1771
1772func (c *Context) addVariationDependency(module *moduleInfo, variations []Variation,
1773	tag DependencyTag, depName string, far bool) (*moduleInfo, []error) {
1774	if _, ok := tag.(BaseDependencyTag); ok {
1775		panic("BaseDependencyTag is not allowed to be used directly!")
1776	}
1777
1778	possibleDeps := c.moduleGroupFromName(depName, module.namespace())
1779	if possibleDeps == nil {
1780		return nil, c.discoveredMissingDependencies(module, depName, nil)
1781	}
1782
1783	foundDep, newVariant := findVariant(module, possibleDeps, variations, far, false)
1784
1785	if foundDep == nil {
1786		if c.allowMissingDependencies {
1787			// Allow missing variants.
1788			return nil, c.discoveredMissingDependencies(module, depName, newVariant)
1789		}
1790		return nil, []error{&BlueprintError{
1791			Err: fmt.Errorf("dependency %q of %q missing variant:\n  %s\navailable variants:\n  %s",
1792				depName, module.Name(),
1793				c.prettyPrintVariant(newVariant),
1794				c.prettyPrintGroupVariants(possibleDeps)),
1795			Pos: module.pos,
1796		}}
1797	}
1798
1799	if module == foundDep {
1800		return nil, []error{&BlueprintError{
1801			Err: fmt.Errorf("%q depends on itself", depName),
1802			Pos: module.pos,
1803		}}
1804	}
1805	// AddVariationDependency allows adding a dependency on itself, but only if
1806	// that module is earlier in the module list than this one, since we always
1807	// run GenerateBuildActions in order for the variants of a module
1808	if foundDep.group == module.group && beforeInModuleList(module, foundDep, module.group.modules) {
1809		return nil, []error{&BlueprintError{
1810			Err: fmt.Errorf("%q depends on later version of itself", depName),
1811			Pos: module.pos,
1812		}}
1813	}
1814	module.newDirectDeps = append(module.newDirectDeps, depInfo{foundDep, tag})
1815	atomic.AddUint32(&c.depsModified, 1)
1816	return foundDep, nil
1817}
1818
1819func (c *Context) addInterVariantDependency(origModule *moduleInfo, tag DependencyTag,
1820	from, to Module) *moduleInfo {
1821	if _, ok := tag.(BaseDependencyTag); ok {
1822		panic("BaseDependencyTag is not allowed to be used directly!")
1823	}
1824
1825	var fromInfo, toInfo *moduleInfo
1826	for _, moduleOrAlias := range origModule.splitModules {
1827		if m := moduleOrAlias.module(); m != nil {
1828			if m.logicModule == from {
1829				fromInfo = m
1830			}
1831			if m.logicModule == to {
1832				toInfo = m
1833				if fromInfo != nil {
1834					panic(fmt.Errorf("%q depends on later version of itself", origModule.Name()))
1835				}
1836			}
1837		}
1838	}
1839
1840	if fromInfo == nil || toInfo == nil {
1841		panic(fmt.Errorf("AddInterVariantDependency called for module %q on invalid variant",
1842			origModule.Name()))
1843	}
1844
1845	fromInfo.newDirectDeps = append(fromInfo.newDirectDeps, depInfo{toInfo, tag})
1846	atomic.AddUint32(&c.depsModified, 1)
1847	return toInfo
1848}
1849
1850// findBlueprintDescendants returns a map linking parent Blueprint files to child Blueprints files
1851// For example, if paths = []string{"a/b/c/Android.bp", "a/Android.bp"},
1852// then descendants = {"":[]string{"a/Android.bp"}, "a/Android.bp":[]string{"a/b/c/Android.bp"}}
1853func findBlueprintDescendants(paths []string) (descendants map[string][]string, err error) {
1854	// make mapping from dir path to file path
1855	filesByDir := make(map[string]string, len(paths))
1856	for _, path := range paths {
1857		dir := filepath.Dir(path)
1858		_, alreadyFound := filesByDir[dir]
1859		if alreadyFound {
1860			return nil, fmt.Errorf("Found two Blueprint files in directory %v : %v and %v", dir, filesByDir[dir], path)
1861		}
1862		filesByDir[dir] = path
1863	}
1864
1865	findAncestor := func(childFile string) (ancestor string) {
1866		prevAncestorDir := filepath.Dir(childFile)
1867		for {
1868			ancestorDir := filepath.Dir(prevAncestorDir)
1869			if ancestorDir == prevAncestorDir {
1870				// reached the root dir without any matches; assign this as a descendant of ""
1871				return ""
1872			}
1873
1874			ancestorFile, ancestorExists := filesByDir[ancestorDir]
1875			if ancestorExists {
1876				return ancestorFile
1877			}
1878			prevAncestorDir = ancestorDir
1879		}
1880	}
1881	// generate the descendants map
1882	descendants = make(map[string][]string, len(filesByDir))
1883	for _, childFile := range filesByDir {
1884		ancestorFile := findAncestor(childFile)
1885		descendants[ancestorFile] = append(descendants[ancestorFile], childFile)
1886	}
1887	return descendants, nil
1888}
1889
1890type visitOrderer interface {
1891	// returns the number of modules that this module needs to wait for
1892	waitCount(module *moduleInfo) int
1893	// returns the list of modules that are waiting for this module
1894	propagate(module *moduleInfo) []*moduleInfo
1895	// visit modules in order
1896	visit(modules []*moduleInfo, visit func(*moduleInfo, chan<- pauseSpec) bool)
1897}
1898
1899type unorderedVisitorImpl struct{}
1900
1901func (unorderedVisitorImpl) waitCount(module *moduleInfo) int {
1902	return 0
1903}
1904
1905func (unorderedVisitorImpl) propagate(module *moduleInfo) []*moduleInfo {
1906	return nil
1907}
1908
1909func (unorderedVisitorImpl) visit(modules []*moduleInfo, visit func(*moduleInfo, chan<- pauseSpec) bool) {
1910	for _, module := range modules {
1911		if visit(module, nil) {
1912			return
1913		}
1914	}
1915}
1916
1917type bottomUpVisitorImpl struct{}
1918
1919func (bottomUpVisitorImpl) waitCount(module *moduleInfo) int {
1920	return len(module.forwardDeps)
1921}
1922
1923func (bottomUpVisitorImpl) propagate(module *moduleInfo) []*moduleInfo {
1924	return module.reverseDeps
1925}
1926
1927func (bottomUpVisitorImpl) visit(modules []*moduleInfo, visit func(*moduleInfo, chan<- pauseSpec) bool) {
1928	for _, module := range modules {
1929		if visit(module, nil) {
1930			return
1931		}
1932	}
1933}
1934
1935type topDownVisitorImpl struct{}
1936
1937func (topDownVisitorImpl) waitCount(module *moduleInfo) int {
1938	return len(module.reverseDeps)
1939}
1940
1941func (topDownVisitorImpl) propagate(module *moduleInfo) []*moduleInfo {
1942	return module.forwardDeps
1943}
1944
1945func (topDownVisitorImpl) visit(modules []*moduleInfo, visit func(*moduleInfo, chan<- pauseSpec) bool) {
1946	for i := 0; i < len(modules); i++ {
1947		module := modules[len(modules)-1-i]
1948		if visit(module, nil) {
1949			return
1950		}
1951	}
1952}
1953
1954var (
1955	bottomUpVisitor bottomUpVisitorImpl
1956	topDownVisitor  topDownVisitorImpl
1957)
1958
1959// pauseSpec describes a pause that a module needs to occur until another module has been visited,
1960// at which point the unpause channel will be closed.
1961type pauseSpec struct {
1962	paused  *moduleInfo
1963	until   *moduleInfo
1964	unpause unpause
1965}
1966
1967type unpause chan struct{}
1968
1969const parallelVisitLimit = 1000
1970
1971// Calls visit on each module, guaranteeing that visit is not called on a module until visit on all
1972// of its dependencies has finished.  A visit function can write a pauseSpec to the pause channel
1973// to wait for another dependency to be visited.  If a visit function returns true to cancel
1974// while another visitor is paused, the paused visitor will never be resumed and its goroutine
1975// will stay paused forever.
1976func parallelVisit(modules []*moduleInfo, order visitOrderer, limit int,
1977	visit func(module *moduleInfo, pause chan<- pauseSpec) bool) []error {
1978
1979	doneCh := make(chan *moduleInfo)
1980	cancelCh := make(chan bool)
1981	pauseCh := make(chan pauseSpec)
1982	cancel := false
1983
1984	var backlog []*moduleInfo      // Visitors that are ready to start but backlogged due to limit.
1985	var unpauseBacklog []pauseSpec // Visitors that are ready to unpause but backlogged due to limit.
1986
1987	active := 0  // Number of visitors running, not counting paused visitors.
1988	visited := 0 // Number of finished visitors.
1989
1990	pauseMap := make(map[*moduleInfo][]pauseSpec)
1991
1992	for _, module := range modules {
1993		module.waitingCount = order.waitCount(module)
1994	}
1995
1996	// Call the visitor on a module if there are fewer active visitors than the parallelism
1997	// limit, otherwise add it to the backlog.
1998	startOrBacklog := func(module *moduleInfo) {
1999		if active < limit {
2000			active++
2001			go func() {
2002				ret := visit(module, pauseCh)
2003				if ret {
2004					cancelCh <- true
2005				}
2006				doneCh <- module
2007			}()
2008		} else {
2009			backlog = append(backlog, module)
2010		}
2011	}
2012
2013	// Unpause the already-started but paused  visitor on a module if there are fewer active
2014	// visitors than the parallelism limit, otherwise add it to the backlog.
2015	unpauseOrBacklog := func(pauseSpec pauseSpec) {
2016		if active < limit {
2017			active++
2018			close(pauseSpec.unpause)
2019		} else {
2020			unpauseBacklog = append(unpauseBacklog, pauseSpec)
2021		}
2022	}
2023
2024	// Start any modules in the backlog up to the parallelism limit.  Unpause paused modules first
2025	// since they may already be holding resources.
2026	unpauseOrStartFromBacklog := func() {
2027		for active < limit && len(unpauseBacklog) > 0 {
2028			unpause := unpauseBacklog[0]
2029			unpauseBacklog = unpauseBacklog[1:]
2030			unpauseOrBacklog(unpause)
2031		}
2032		for active < limit && len(backlog) > 0 {
2033			toVisit := backlog[0]
2034			backlog = backlog[1:]
2035			startOrBacklog(toVisit)
2036		}
2037	}
2038
2039	toVisit := len(modules)
2040
2041	// Start or backlog any modules that are not waiting for any other modules.
2042	for _, module := range modules {
2043		if module.waitingCount == 0 {
2044			startOrBacklog(module)
2045		}
2046	}
2047
2048	for active > 0 {
2049		select {
2050		case <-cancelCh:
2051			cancel = true
2052			backlog = nil
2053		case doneModule := <-doneCh:
2054			active--
2055			if !cancel {
2056				// Mark this module as done.
2057				doneModule.waitingCount = -1
2058				visited++
2059
2060				// Unpause or backlog any modules that were waiting for this one.
2061				if unpauses, ok := pauseMap[doneModule]; ok {
2062					delete(pauseMap, doneModule)
2063					for _, unpause := range unpauses {
2064						unpauseOrBacklog(unpause)
2065					}
2066				}
2067
2068				// Start any backlogged modules up to limit.
2069				unpauseOrStartFromBacklog()
2070
2071				// Decrement waitingCount on the next modules in the tree based
2072				// on propagation order, and start or backlog them if they are
2073				// ready to start.
2074				for _, module := range order.propagate(doneModule) {
2075					module.waitingCount--
2076					if module.waitingCount == 0 {
2077						startOrBacklog(module)
2078					}
2079				}
2080			}
2081		case pauseSpec := <-pauseCh:
2082			if pauseSpec.until.waitingCount == -1 {
2083				// Module being paused for is already finished, resume immediately.
2084				close(pauseSpec.unpause)
2085			} else {
2086				// Register for unpausing.
2087				pauseMap[pauseSpec.until] = append(pauseMap[pauseSpec.until], pauseSpec)
2088
2089				// Don't count paused visitors as active so that this can't deadlock
2090				// if 1000 visitors are paused simultaneously.
2091				active--
2092				unpauseOrStartFromBacklog()
2093			}
2094		}
2095	}
2096
2097	if !cancel {
2098		// Invariant check: no backlogged modules, these weren't waiting on anything except
2099		// the parallelism limit so they should have run.
2100		if len(backlog) > 0 {
2101			panic(fmt.Errorf("parallelVisit finished with %d backlogged visitors", len(backlog)))
2102		}
2103
2104		// Invariant check: no backlogged paused modules, these weren't waiting on anything
2105		// except the parallelism limit so they should have run.
2106		if len(unpauseBacklog) > 0 {
2107			panic(fmt.Errorf("parallelVisit finished with %d backlogged unpaused visitors", len(unpauseBacklog)))
2108		}
2109
2110		if len(pauseMap) > 0 {
2111			// Probably a deadlock due to a newly added dependency cycle. Start from each module in
2112			// the order of the input modules list and perform a depth-first search for the module
2113			// it is paused on, ignoring modules that are marked as done.  Note this traverses from
2114			// modules to the modules that would have been unblocked when that module finished, i.e
2115			// the reverse of the visitOrderer.
2116
2117			// In order to reduce duplicated work, once a module has been checked and determined
2118			// not to be part of a cycle add it and everything that depends on it to the checked
2119			// map.
2120			checked := make(map[*moduleInfo]struct{})
2121
2122			var check func(module, end *moduleInfo) []*moduleInfo
2123			check = func(module, end *moduleInfo) []*moduleInfo {
2124				if module.waitingCount == -1 {
2125					// This module was finished, it can't be part of a loop.
2126					return nil
2127				}
2128				if module == end {
2129					// This module is the end of the loop, start rolling up the cycle.
2130					return []*moduleInfo{module}
2131				}
2132
2133				if _, alreadyChecked := checked[module]; alreadyChecked {
2134					return nil
2135				}
2136
2137				for _, dep := range order.propagate(module) {
2138					cycle := check(dep, end)
2139					if cycle != nil {
2140						return append([]*moduleInfo{module}, cycle...)
2141					}
2142				}
2143				for _, depPauseSpec := range pauseMap[module] {
2144					cycle := check(depPauseSpec.paused, end)
2145					if cycle != nil {
2146						return append([]*moduleInfo{module}, cycle...)
2147					}
2148				}
2149
2150				checked[module] = struct{}{}
2151				return nil
2152			}
2153
2154			// Iterate over the modules list instead of pauseMap to provide deterministic ordering.
2155			for _, module := range modules {
2156				for _, pauseSpec := range pauseMap[module] {
2157					cycle := check(pauseSpec.paused, pauseSpec.until)
2158					if len(cycle) > 0 {
2159						return cycleError(cycle)
2160					}
2161				}
2162			}
2163		}
2164
2165		// Invariant check: if there was no deadlock and no cancellation every module
2166		// should have been visited.
2167		if visited != toVisit {
2168			panic(fmt.Errorf("parallelVisit ran %d visitors, expected %d", visited, toVisit))
2169		}
2170
2171		// Invariant check: if there was no deadlock and no cancellation  every module
2172		// should have been visited, so there is nothing left to be paused on.
2173		if len(pauseMap) > 0 {
2174			panic(fmt.Errorf("parallelVisit finished with %d paused visitors", len(pauseMap)))
2175		}
2176	}
2177
2178	return nil
2179}
2180
2181func cycleError(cycle []*moduleInfo) (errs []error) {
2182	// The cycle list is in reverse order because all the 'check' calls append
2183	// their own module to the list.
2184	errs = append(errs, &BlueprintError{
2185		Err: fmt.Errorf("encountered dependency cycle:"),
2186		Pos: cycle[len(cycle)-1].pos,
2187	})
2188
2189	// Iterate backwards through the cycle list.
2190	curModule := cycle[0]
2191	for i := len(cycle) - 1; i >= 0; i-- {
2192		nextModule := cycle[i]
2193		errs = append(errs, &BlueprintError{
2194			Err: fmt.Errorf("    %s depends on %s",
2195				curModule, nextModule),
2196			Pos: curModule.pos,
2197		})
2198		curModule = nextModule
2199	}
2200
2201	return errs
2202}
2203
2204// updateDependencies recursively walks the module dependency graph and updates
2205// additional fields based on the dependencies.  It builds a sorted list of modules
2206// such that dependencies of a module always appear first, and populates reverse
2207// dependency links and counts of total dependencies.  It also reports errors when
2208// it encounters dependency cycles.  This should be called after resolveDependencies,
2209// as well as after any mutator pass has called addDependency
2210func (c *Context) updateDependencies() (errs []error) {
2211	c.cachedDepsModified = true
2212	visited := make(map[*moduleInfo]bool)  // modules that were already checked
2213	checking := make(map[*moduleInfo]bool) // modules actively being checked
2214
2215	sorted := make([]*moduleInfo, 0, len(c.moduleInfo))
2216
2217	var check func(group *moduleInfo) []*moduleInfo
2218
2219	check = func(module *moduleInfo) []*moduleInfo {
2220		visited[module] = true
2221		checking[module] = true
2222		defer delete(checking, module)
2223
2224		// Reset the forward and reverse deps without reducing their capacity to avoid reallocation.
2225		module.reverseDeps = module.reverseDeps[:0]
2226		module.forwardDeps = module.forwardDeps[:0]
2227
2228		// Add an implicit dependency ordering on all earlier modules in the same module group
2229		for _, dep := range module.group.modules {
2230			if dep == module {
2231				break
2232			}
2233			if depModule := dep.module(); depModule != nil {
2234				module.forwardDeps = append(module.forwardDeps, depModule)
2235			}
2236		}
2237
2238	outer:
2239		for _, dep := range module.directDeps {
2240			// use a loop to check for duplicates, average number of directDeps measured to be 9.5.
2241			for _, exists := range module.forwardDeps {
2242				if dep.module == exists {
2243					continue outer
2244				}
2245			}
2246			module.forwardDeps = append(module.forwardDeps, dep.module)
2247		}
2248
2249		for _, dep := range module.forwardDeps {
2250			if checking[dep] {
2251				// This is a cycle.
2252				return []*moduleInfo{dep, module}
2253			}
2254
2255			if !visited[dep] {
2256				cycle := check(dep)
2257				if cycle != nil {
2258					if cycle[0] == module {
2259						// We are the "start" of the cycle, so we're responsible
2260						// for generating the errors.
2261						errs = append(errs, cycleError(cycle)...)
2262
2263						// We can continue processing this module's children to
2264						// find more cycles.  Since all the modules that were
2265						// part of the found cycle were marked as visited we
2266						// won't run into that cycle again.
2267					} else {
2268						// We're not the "start" of the cycle, so we just append
2269						// our module to the list and return it.
2270						return append(cycle, module)
2271					}
2272				}
2273			}
2274
2275			dep.reverseDeps = append(dep.reverseDeps, module)
2276		}
2277
2278		sorted = append(sorted, module)
2279
2280		return nil
2281	}
2282
2283	for _, module := range c.moduleInfo {
2284		if !visited[module] {
2285			cycle := check(module)
2286			if cycle != nil {
2287				if cycle[len(cycle)-1] != module {
2288					panic("inconceivable!")
2289				}
2290				errs = append(errs, cycleError(cycle)...)
2291			}
2292		}
2293	}
2294
2295	c.modulesSorted = sorted
2296
2297	return
2298}
2299
2300type jsonVariationMap []Variation
2301
2302type jsonModuleName struct {
2303	Name                 string
2304	Variations           jsonVariationMap
2305	DependencyVariations jsonVariationMap
2306}
2307
2308type jsonDep struct {
2309	jsonModuleName
2310	Tag string
2311}
2312
2313type JsonModule struct {
2314	jsonModuleName
2315	Deps      []jsonDep
2316	Type      string
2317	Blueprint string
2318	Module    map[string]interface{}
2319}
2320
2321func toJsonVariationMap(vm variationMap) jsonVariationMap {
2322	m := make(jsonVariationMap, 0, len(vm))
2323	for k, v := range vm {
2324		m = append(m, Variation{k, v})
2325	}
2326	sort.Slice(m, func(i, j int) bool {
2327		if m[i].Mutator != m[j].Mutator {
2328			return m[i].Mutator < m[j].Mutator
2329		}
2330		return m[i].Variation < m[j].Variation
2331	})
2332	return m
2333}
2334
2335func jsonModuleNameFromModuleInfo(m *moduleInfo) *jsonModuleName {
2336	return &jsonModuleName{
2337		Name:                 m.Name(),
2338		Variations:           toJsonVariationMap(m.variant.variations),
2339		DependencyVariations: toJsonVariationMap(m.variant.dependencyVariations),
2340	}
2341}
2342
2343type JSONDataSupplier interface {
2344	AddJSONData(d *map[string]interface{})
2345}
2346
2347func jsonModuleFromModuleInfo(m *moduleInfo) *JsonModule {
2348	result := &JsonModule{
2349		jsonModuleName: *jsonModuleNameFromModuleInfo(m),
2350		Deps:           make([]jsonDep, 0),
2351		Type:           m.typeName,
2352		Blueprint:      m.relBlueprintsFile,
2353		Module:         make(map[string]interface{}),
2354	}
2355	if j, ok := m.logicModule.(JSONDataSupplier); ok {
2356		j.AddJSONData(&result.Module)
2357	}
2358	for _, p := range m.providers {
2359		if j, ok := p.(JSONDataSupplier); ok {
2360			j.AddJSONData(&result.Module)
2361		}
2362	}
2363	return result
2364}
2365
2366func jsonModuleWithActionsFromModuleInfo(m *moduleInfo) *JsonModule {
2367	result := &JsonModule{
2368		jsonModuleName: jsonModuleName{
2369			Name: m.Name(),
2370		},
2371		Deps:      make([]jsonDep, 0),
2372		Type:      m.typeName,
2373		Blueprint: m.relBlueprintsFile,
2374		Module:    make(map[string]interface{}),
2375	}
2376	var actions []map[string]interface{}
2377	for _, bDef := range m.actionDefs.buildDefs {
2378		actions = append(actions, map[string]interface{}{
2379			"Inputs": append(
2380				getNinjaStringsWithNilPkgNames(bDef.Inputs),
2381				getNinjaStringsWithNilPkgNames(bDef.Implicits)...),
2382			"Outputs": append(
2383				getNinjaStringsWithNilPkgNames(bDef.Outputs),
2384				getNinjaStringsWithNilPkgNames(bDef.ImplicitOutputs)...),
2385		})
2386	}
2387	result.Module["Actions"] = actions
2388	return result
2389}
2390
2391// Gets a list of strings from the given list of ninjaStrings by invoking ninjaString.Value with
2392// nil pkgNames on each of the input ninjaStrings.
2393func getNinjaStringsWithNilPkgNames(nStrs []ninjaString) []string {
2394	var strs []string
2395	for _, nstr := range nStrs {
2396		strs = append(strs, nstr.Value(nil))
2397	}
2398	return strs
2399}
2400
2401// PrintJSONGraph prints info of modules in a JSON file.
2402func (c *Context) PrintJSONGraphAndActions(wGraph io.Writer, wActions io.Writer) {
2403	modulesToGraph := make([]*JsonModule, 0)
2404	modulesToActions := make([]*JsonModule, 0)
2405	for _, m := range c.modulesSorted {
2406		jm := jsonModuleFromModuleInfo(m)
2407		jmWithActions := jsonModuleWithActionsFromModuleInfo(m)
2408		for _, d := range m.directDeps {
2409			jm.Deps = append(jm.Deps, jsonDep{
2410				jsonModuleName: *jsonModuleNameFromModuleInfo(d.module),
2411				Tag:            fmt.Sprintf("%T %+v", d.tag, d.tag),
2412			})
2413			jmWithActions.Deps = append(jmWithActions.Deps, jsonDep{
2414				jsonModuleName: jsonModuleName{
2415					Name: d.module.Name(),
2416				},
2417			})
2418
2419		}
2420		modulesToGraph = append(modulesToGraph, jm)
2421		modulesToActions = append(modulesToActions, jmWithActions)
2422	}
2423	writeJson(wGraph, modulesToGraph)
2424	writeJson(wActions, modulesToActions)
2425}
2426
2427func writeJson(w io.Writer, modules []*JsonModule) {
2428	e := json.NewEncoder(w)
2429	e.SetIndent("", "\t")
2430	e.Encode(modules)
2431}
2432
2433// PrepareBuildActions generates an internal representation of all the build
2434// actions that need to be performed.  This process involves invoking the
2435// GenerateBuildActions method on each of the Module objects created during the
2436// parse phase and then on each of the registered Singleton objects.
2437//
2438// If the ResolveDependencies method has not already been called it is called
2439// automatically by this method.
2440//
2441// The config argument is made available to all of the Module and Singleton
2442// objects via the Config method on the ModuleContext and SingletonContext
2443// objects passed to GenerateBuildActions.  It is also passed to the functions
2444// specified via PoolFunc, RuleFunc, and VariableFunc so that they can compute
2445// config-specific values.
2446//
2447// The returned deps is a list of the ninja files dependencies that were added
2448// by the modules and singletons via the ModuleContext.AddNinjaFileDeps(),
2449// SingletonContext.AddNinjaFileDeps(), and PackageContext.AddNinjaFileDeps()
2450// methods.
2451
2452func (c *Context) PrepareBuildActions(config interface{}) (deps []string, errs []error) {
2453	c.BeginEvent("prepare_build_actions")
2454	defer c.EndEvent("prepare_build_actions")
2455	pprof.Do(c.Context, pprof.Labels("blueprint", "PrepareBuildActions"), func(ctx context.Context) {
2456		c.buildActionsReady = false
2457
2458		if !c.dependenciesReady {
2459			var extraDeps []string
2460			extraDeps, errs = c.resolveDependencies(ctx, config)
2461			if len(errs) > 0 {
2462				return
2463			}
2464			deps = append(deps, extraDeps...)
2465		}
2466
2467		var depsModules []string
2468		depsModules, errs = c.generateModuleBuildActions(config, c.liveGlobals)
2469		if len(errs) > 0 {
2470			return
2471		}
2472
2473		var depsSingletons []string
2474		depsSingletons, errs = c.generateSingletonBuildActions(config, c.singletonInfo, c.liveGlobals)
2475		if len(errs) > 0 {
2476			return
2477		}
2478
2479		deps = append(deps, depsModules...)
2480		deps = append(deps, depsSingletons...)
2481
2482		if c.outDir != nil {
2483			err := c.liveGlobals.addNinjaStringDeps(c.outDir)
2484			if err != nil {
2485				errs = []error{err}
2486				return
2487			}
2488		}
2489
2490		pkgNames, depsPackages := c.makeUniquePackageNames(c.liveGlobals)
2491
2492		deps = append(deps, depsPackages...)
2493
2494		c.memoizeFullNames(c.liveGlobals, pkgNames)
2495
2496		// This will panic if it finds a problem since it's a programming error.
2497		c.checkForVariableReferenceCycles(c.liveGlobals.variables, pkgNames)
2498
2499		c.pkgNames = pkgNames
2500		c.globalVariables = c.liveGlobals.variables
2501		c.globalPools = c.liveGlobals.pools
2502		c.globalRules = c.liveGlobals.rules
2503
2504		c.buildActionsReady = true
2505	})
2506
2507	if len(errs) > 0 {
2508		return nil, errs
2509	}
2510
2511	return deps, nil
2512}
2513
2514func (c *Context) runMutators(ctx context.Context, config interface{}) (deps []string, errs []error) {
2515	pprof.Do(ctx, pprof.Labels("blueprint", "runMutators"), func(ctx context.Context) {
2516		for _, mutator := range c.mutatorInfo {
2517			pprof.Do(ctx, pprof.Labels("mutator", mutator.name), func(context.Context) {
2518				var newDeps []string
2519				if mutator.topDownMutator != nil {
2520					newDeps, errs = c.runMutator(config, mutator, topDownMutator)
2521				} else if mutator.bottomUpMutator != nil {
2522					newDeps, errs = c.runMutator(config, mutator, bottomUpMutator)
2523				} else {
2524					panic("no mutator set on " + mutator.name)
2525				}
2526				if len(errs) > 0 {
2527					return
2528				}
2529				deps = append(deps, newDeps...)
2530			})
2531			if len(errs) > 0 {
2532				return
2533			}
2534		}
2535	})
2536
2537	if len(errs) > 0 {
2538		return nil, errs
2539	}
2540
2541	return deps, nil
2542}
2543
2544type mutatorDirection interface {
2545	run(mutator *mutatorInfo, ctx *mutatorContext)
2546	orderer() visitOrderer
2547	fmt.Stringer
2548}
2549
2550type bottomUpMutatorImpl struct{}
2551
2552func (bottomUpMutatorImpl) run(mutator *mutatorInfo, ctx *mutatorContext) {
2553	mutator.bottomUpMutator(ctx)
2554}
2555
2556func (bottomUpMutatorImpl) orderer() visitOrderer {
2557	return bottomUpVisitor
2558}
2559
2560func (bottomUpMutatorImpl) String() string {
2561	return "bottom up mutator"
2562}
2563
2564type topDownMutatorImpl struct{}
2565
2566func (topDownMutatorImpl) run(mutator *mutatorInfo, ctx *mutatorContext) {
2567	mutator.topDownMutator(ctx)
2568}
2569
2570func (topDownMutatorImpl) orderer() visitOrderer {
2571	return topDownVisitor
2572}
2573
2574func (topDownMutatorImpl) String() string {
2575	return "top down mutator"
2576}
2577
2578var (
2579	topDownMutator  topDownMutatorImpl
2580	bottomUpMutator bottomUpMutatorImpl
2581)
2582
2583type reverseDep struct {
2584	module *moduleInfo
2585	dep    depInfo
2586}
2587
2588func (c *Context) runMutator(config interface{}, mutator *mutatorInfo,
2589	direction mutatorDirection) (deps []string, errs []error) {
2590
2591	newModuleInfo := make(map[Module]*moduleInfo)
2592	for k, v := range c.moduleInfo {
2593		newModuleInfo[k] = v
2594	}
2595
2596	type globalStateChange struct {
2597		reverse    []reverseDep
2598		rename     []rename
2599		replace    []replace
2600		newModules []*moduleInfo
2601		deps       []string
2602	}
2603
2604	reverseDeps := make(map[*moduleInfo][]depInfo)
2605	var rename []rename
2606	var replace []replace
2607	var newModules []*moduleInfo
2608
2609	errsCh := make(chan []error)
2610	globalStateCh := make(chan globalStateChange)
2611	newVariationsCh := make(chan modulesOrAliases)
2612	done := make(chan bool)
2613
2614	c.depsModified = 0
2615
2616	visit := func(module *moduleInfo, pause chan<- pauseSpec) bool {
2617		if module.splitModules != nil {
2618			panic("split module found in sorted module list")
2619		}
2620
2621		mctx := &mutatorContext{
2622			baseModuleContext: baseModuleContext{
2623				context: c,
2624				config:  config,
2625				module:  module,
2626			},
2627			name:    mutator.name,
2628			pauseCh: pause,
2629		}
2630
2631		module.startedMutator = mutator
2632
2633		func() {
2634			defer func() {
2635				if r := recover(); r != nil {
2636					in := fmt.Sprintf("%s %q for %s", direction, mutator.name, module)
2637					if err, ok := r.(panicError); ok {
2638						err.addIn(in)
2639						mctx.error(err)
2640					} else {
2641						mctx.error(newPanicErrorf(r, in))
2642					}
2643				}
2644			}()
2645			direction.run(mutator, mctx)
2646		}()
2647
2648		module.finishedMutator = mutator
2649
2650		if len(mctx.errs) > 0 {
2651			errsCh <- mctx.errs
2652			return true
2653		}
2654
2655		if len(mctx.newVariations) > 0 {
2656			newVariationsCh <- mctx.newVariations
2657		}
2658
2659		if len(mctx.reverseDeps) > 0 || len(mctx.replace) > 0 || len(mctx.rename) > 0 || len(mctx.newModules) > 0 || len(mctx.ninjaFileDeps) > 0 {
2660			globalStateCh <- globalStateChange{
2661				reverse:    mctx.reverseDeps,
2662				replace:    mctx.replace,
2663				rename:     mctx.rename,
2664				newModules: mctx.newModules,
2665				deps:       mctx.ninjaFileDeps,
2666			}
2667		}
2668
2669		return false
2670	}
2671
2672	// Process errs and reverseDeps in a single goroutine
2673	go func() {
2674		for {
2675			select {
2676			case newErrs := <-errsCh:
2677				errs = append(errs, newErrs...)
2678			case globalStateChange := <-globalStateCh:
2679				for _, r := range globalStateChange.reverse {
2680					reverseDeps[r.module] = append(reverseDeps[r.module], r.dep)
2681				}
2682				replace = append(replace, globalStateChange.replace...)
2683				rename = append(rename, globalStateChange.rename...)
2684				newModules = append(newModules, globalStateChange.newModules...)
2685				deps = append(deps, globalStateChange.deps...)
2686			case newVariations := <-newVariationsCh:
2687				for _, moduleOrAlias := range newVariations {
2688					if m := moduleOrAlias.module(); m != nil {
2689						newModuleInfo[m.logicModule] = m
2690					}
2691				}
2692			case <-done:
2693				return
2694			}
2695		}
2696	}()
2697
2698	c.startedMutator = mutator
2699
2700	var visitErrs []error
2701	if mutator.parallel {
2702		visitErrs = parallelVisit(c.modulesSorted, direction.orderer(), parallelVisitLimit, visit)
2703	} else {
2704		direction.orderer().visit(c.modulesSorted, visit)
2705	}
2706
2707	if len(visitErrs) > 0 {
2708		return nil, visitErrs
2709	}
2710
2711	c.finishedMutators[mutator] = true
2712
2713	done <- true
2714
2715	if len(errs) > 0 {
2716		return nil, errs
2717	}
2718
2719	c.moduleInfo = newModuleInfo
2720
2721	for _, group := range c.moduleGroups {
2722		for i := 0; i < len(group.modules); i++ {
2723			module := group.modules[i].module()
2724			if module == nil {
2725				// Existing alias, skip it
2726				continue
2727			}
2728
2729			// Update module group to contain newly split variants
2730			if module.splitModules != nil {
2731				group.modules, i = spliceModules(group.modules, i, module.splitModules)
2732			}
2733
2734			// Fix up any remaining dependencies on modules that were split into variants
2735			// by replacing them with the first variant
2736			for j, dep := range module.directDeps {
2737				if dep.module.logicModule == nil {
2738					module.directDeps[j].module = dep.module.splitModules.firstModule()
2739				}
2740			}
2741
2742			if module.createdBy != nil && module.createdBy.logicModule == nil {
2743				module.createdBy = module.createdBy.splitModules.firstModule()
2744			}
2745
2746			// Add in any new direct dependencies that were added by the mutator
2747			module.directDeps = append(module.directDeps, module.newDirectDeps...)
2748			module.newDirectDeps = nil
2749		}
2750
2751		findAliasTarget := func(variant variant) *moduleInfo {
2752			for _, moduleOrAlias := range group.modules {
2753				if alias := moduleOrAlias.alias(); alias != nil {
2754					if alias.variant.variations.equal(variant.variations) {
2755						return alias.target
2756					}
2757				}
2758			}
2759			return nil
2760		}
2761
2762		// Forward or delete any dangling aliases.
2763		// Use a manual loop instead of range because len(group.modules) can
2764		// change inside the loop
2765		for i := 0; i < len(group.modules); i++ {
2766			if alias := group.modules[i].alias(); alias != nil {
2767				if alias.target.logicModule == nil {
2768					newTarget := findAliasTarget(alias.target.variant)
2769					if newTarget != nil {
2770						alias.target = newTarget
2771					} else {
2772						// The alias was left dangling, remove it.
2773						group.modules = append(group.modules[:i], group.modules[i+1:]...)
2774						i--
2775					}
2776				}
2777			}
2778		}
2779	}
2780
2781	// Add in any new reverse dependencies that were added by the mutator
2782	for module, deps := range reverseDeps {
2783		sort.Sort(depSorter(deps))
2784		module.directDeps = append(module.directDeps, deps...)
2785		c.depsModified++
2786	}
2787
2788	for _, module := range newModules {
2789		errs = c.addModule(module)
2790		if len(errs) > 0 {
2791			return nil, errs
2792		}
2793		atomic.AddUint32(&c.depsModified, 1)
2794	}
2795
2796	errs = c.handleRenames(rename)
2797	if len(errs) > 0 {
2798		return nil, errs
2799	}
2800
2801	errs = c.handleReplacements(replace)
2802	if len(errs) > 0 {
2803		return nil, errs
2804	}
2805
2806	if c.depsModified > 0 {
2807		errs = c.updateDependencies()
2808		if len(errs) > 0 {
2809			return nil, errs
2810		}
2811	}
2812
2813	return deps, errs
2814}
2815
2816// Replaces every build logic module with a clone of itself.  Prevents introducing problems where
2817// a mutator sets a non-property member variable on a module, which works until a later mutator
2818// creates variants of that module.
2819func (c *Context) cloneModules() {
2820	type update struct {
2821		orig  Module
2822		clone *moduleInfo
2823	}
2824	ch := make(chan update)
2825	doneCh := make(chan bool)
2826	go func() {
2827		errs := parallelVisit(c.modulesSorted, unorderedVisitorImpl{}, parallelVisitLimit,
2828			func(m *moduleInfo, pause chan<- pauseSpec) bool {
2829				origLogicModule := m.logicModule
2830				m.logicModule, m.properties = c.cloneLogicModule(m)
2831				ch <- update{origLogicModule, m}
2832				return false
2833			})
2834		if len(errs) > 0 {
2835			panic(errs)
2836		}
2837		doneCh <- true
2838	}()
2839
2840	done := false
2841	for !done {
2842		select {
2843		case <-doneCh:
2844			done = true
2845		case update := <-ch:
2846			delete(c.moduleInfo, update.orig)
2847			c.moduleInfo[update.clone.logicModule] = update.clone
2848		}
2849	}
2850}
2851
2852// Removes modules[i] from the list and inserts newModules... where it was located, returning
2853// the new slice and the index of the last inserted element
2854func spliceModules(modules modulesOrAliases, i int, newModules modulesOrAliases) (modulesOrAliases, int) {
2855	spliceSize := len(newModules)
2856	newLen := len(modules) + spliceSize - 1
2857	var dest modulesOrAliases
2858	if cap(modules) >= len(modules)-1+len(newModules) {
2859		// We can fit the splice in the existing capacity, do everything in place
2860		dest = modules[:newLen]
2861	} else {
2862		dest = make(modulesOrAliases, newLen)
2863		copy(dest, modules[:i])
2864	}
2865
2866	// Move the end of the slice over by spliceSize-1
2867	copy(dest[i+spliceSize:], modules[i+1:])
2868
2869	// Copy the new modules into the slice
2870	copy(dest[i:], newModules)
2871
2872	return dest, i + spliceSize - 1
2873}
2874
2875func (c *Context) generateModuleBuildActions(config interface{},
2876	liveGlobals *liveTracker) ([]string, []error) {
2877
2878	var deps []string
2879	var errs []error
2880
2881	cancelCh := make(chan struct{})
2882	errsCh := make(chan []error)
2883	depsCh := make(chan []string)
2884
2885	go func() {
2886		for {
2887			select {
2888			case <-cancelCh:
2889				close(cancelCh)
2890				return
2891			case newErrs := <-errsCh:
2892				errs = append(errs, newErrs...)
2893			case newDeps := <-depsCh:
2894				deps = append(deps, newDeps...)
2895
2896			}
2897		}
2898	}()
2899
2900	visitErrs := parallelVisit(c.modulesSorted, bottomUpVisitor, parallelVisitLimit,
2901		func(module *moduleInfo, pause chan<- pauseSpec) bool {
2902			uniqueName := c.nameInterface.UniqueName(newNamespaceContext(module), module.group.name)
2903			sanitizedName := toNinjaName(uniqueName)
2904			sanitizedVariant := toNinjaName(module.variant.name)
2905
2906			prefix := moduleNamespacePrefix(sanitizedName + "_" + sanitizedVariant)
2907
2908			// The parent scope of the moduleContext's local scope gets overridden to be that of the
2909			// calling Go package on a per-call basis.  Since the initial parent scope doesn't matter we
2910			// just set it to nil.
2911			scope := newLocalScope(nil, prefix)
2912
2913			mctx := &moduleContext{
2914				baseModuleContext: baseModuleContext{
2915					context: c,
2916					config:  config,
2917					module:  module,
2918				},
2919				scope:              scope,
2920				handledMissingDeps: module.missingDeps == nil,
2921			}
2922
2923			mctx.module.startedGenerateBuildActions = true
2924
2925			func() {
2926				defer func() {
2927					if r := recover(); r != nil {
2928						in := fmt.Sprintf("GenerateBuildActions for %s", module)
2929						if err, ok := r.(panicError); ok {
2930							err.addIn(in)
2931							mctx.error(err)
2932						} else {
2933							mctx.error(newPanicErrorf(r, in))
2934						}
2935					}
2936				}()
2937				mctx.module.logicModule.GenerateBuildActions(mctx)
2938			}()
2939
2940			mctx.module.finishedGenerateBuildActions = true
2941
2942			if len(mctx.errs) > 0 {
2943				errsCh <- mctx.errs
2944				return true
2945			}
2946
2947			if module.missingDeps != nil && !mctx.handledMissingDeps {
2948				var errs []error
2949				for _, depName := range module.missingDeps {
2950					errs = append(errs, c.missingDependencyError(module, depName))
2951				}
2952				errsCh <- errs
2953				return true
2954			}
2955
2956			depsCh <- mctx.ninjaFileDeps
2957
2958			newErrs := c.processLocalBuildActions(&module.actionDefs,
2959				&mctx.actionDefs, liveGlobals)
2960			if len(newErrs) > 0 {
2961				errsCh <- newErrs
2962				return true
2963			}
2964			return false
2965		})
2966
2967	cancelCh <- struct{}{}
2968	<-cancelCh
2969
2970	errs = append(errs, visitErrs...)
2971
2972	return deps, errs
2973}
2974
2975func (c *Context) generateSingletonBuildActions(config interface{},
2976	singletons []*singletonInfo, liveGlobals *liveTracker) ([]string, []error) {
2977
2978	var deps []string
2979	var errs []error
2980
2981	for _, info := range singletons {
2982		// The parent scope of the singletonContext's local scope gets overridden to be that of the
2983		// calling Go package on a per-call basis.  Since the initial parent scope doesn't matter we
2984		// just set it to nil.
2985		scope := newLocalScope(nil, singletonNamespacePrefix(info.name))
2986
2987		sctx := &singletonContext{
2988			name:    info.name,
2989			context: c,
2990			config:  config,
2991			scope:   scope,
2992			globals: liveGlobals,
2993		}
2994
2995		func() {
2996			defer func() {
2997				if r := recover(); r != nil {
2998					in := fmt.Sprintf("GenerateBuildActions for singleton %s", info.name)
2999					if err, ok := r.(panicError); ok {
3000						err.addIn(in)
3001						sctx.error(err)
3002					} else {
3003						sctx.error(newPanicErrorf(r, in))
3004					}
3005				}
3006			}()
3007			info.singleton.GenerateBuildActions(sctx)
3008		}()
3009
3010		if len(sctx.errs) > 0 {
3011			errs = append(errs, sctx.errs...)
3012			if len(errs) > maxErrors {
3013				break
3014			}
3015			continue
3016		}
3017
3018		deps = append(deps, sctx.ninjaFileDeps...)
3019
3020		newErrs := c.processLocalBuildActions(&info.actionDefs,
3021			&sctx.actionDefs, liveGlobals)
3022		errs = append(errs, newErrs...)
3023		if len(errs) > maxErrors {
3024			break
3025		}
3026	}
3027
3028	return deps, errs
3029}
3030
3031func (c *Context) processLocalBuildActions(out, in *localBuildActions,
3032	liveGlobals *liveTracker) []error {
3033
3034	var errs []error
3035
3036	// First we go through and add everything referenced by the module's
3037	// buildDefs to the live globals set.  This will end up adding the live
3038	// locals to the set as well, but we'll take them out after.
3039	for _, def := range in.buildDefs {
3040		err := liveGlobals.AddBuildDefDeps(def)
3041		if err != nil {
3042			errs = append(errs, err)
3043		}
3044	}
3045
3046	if len(errs) > 0 {
3047		return errs
3048	}
3049
3050	out.buildDefs = append(out.buildDefs, in.buildDefs...)
3051
3052	// We use the now-incorrect set of live "globals" to determine which local
3053	// definitions are live.  As we go through copying those live locals to the
3054	// moduleGroup we remove them from the live globals set.
3055	for _, v := range in.variables {
3056		isLive := liveGlobals.RemoveVariableIfLive(v)
3057		if isLive {
3058			out.variables = append(out.variables, v)
3059		}
3060	}
3061
3062	for _, r := range in.rules {
3063		isLive := liveGlobals.RemoveRuleIfLive(r)
3064		if isLive {
3065			out.rules = append(out.rules, r)
3066		}
3067	}
3068
3069	return nil
3070}
3071
3072func (c *Context) walkDeps(topModule *moduleInfo, allowDuplicates bool,
3073	visitDown func(depInfo, *moduleInfo) bool, visitUp func(depInfo, *moduleInfo)) {
3074
3075	visited := make(map[*moduleInfo]bool)
3076	var visiting *moduleInfo
3077
3078	defer func() {
3079		if r := recover(); r != nil {
3080			panic(newPanicErrorf(r, "WalkDeps(%s, %s, %s) for dependency %s",
3081				topModule, funcName(visitDown), funcName(visitUp), visiting))
3082		}
3083	}()
3084
3085	var walk func(module *moduleInfo)
3086	walk = func(module *moduleInfo) {
3087		for _, dep := range module.directDeps {
3088			if allowDuplicates || !visited[dep.module] {
3089				visiting = dep.module
3090				recurse := true
3091				if visitDown != nil {
3092					recurse = visitDown(dep, module)
3093				}
3094				if recurse && !visited[dep.module] {
3095					walk(dep.module)
3096					visited[dep.module] = true
3097				}
3098				if visitUp != nil {
3099					visitUp(dep, module)
3100				}
3101			}
3102		}
3103	}
3104
3105	walk(topModule)
3106}
3107
3108type replace struct {
3109	from, to  *moduleInfo
3110	predicate ReplaceDependencyPredicate
3111}
3112
3113type rename struct {
3114	group *moduleGroup
3115	name  string
3116}
3117
3118func (c *Context) moduleMatchingVariant(module *moduleInfo, name string) *moduleInfo {
3119	group := c.moduleGroupFromName(name, module.namespace())
3120
3121	if group == nil {
3122		return nil
3123	}
3124
3125	for _, m := range group.modules {
3126		if module.variant.name == m.moduleOrAliasVariant().name {
3127			return m.moduleOrAliasTarget()
3128		}
3129	}
3130
3131	return nil
3132}
3133
3134func (c *Context) handleRenames(renames []rename) []error {
3135	var errs []error
3136	for _, rename := range renames {
3137		group, name := rename.group, rename.name
3138		if name == group.name || len(group.modules) < 1 {
3139			continue
3140		}
3141
3142		errs = append(errs, c.nameInterface.Rename(group.name, rename.name, group.namespace)...)
3143	}
3144
3145	return errs
3146}
3147
3148func (c *Context) handleReplacements(replacements []replace) []error {
3149	var errs []error
3150	changedDeps := false
3151	for _, replace := range replacements {
3152		for _, m := range replace.from.reverseDeps {
3153			for i, d := range m.directDeps {
3154				if d.module == replace.from {
3155					// If the replacement has a predicate then check it.
3156					if replace.predicate == nil || replace.predicate(m.logicModule, d.tag, d.module.logicModule) {
3157						m.directDeps[i].module = replace.to
3158						changedDeps = true
3159					}
3160				}
3161			}
3162		}
3163
3164	}
3165
3166	if changedDeps {
3167		atomic.AddUint32(&c.depsModified, 1)
3168	}
3169	return errs
3170}
3171
3172func (c *Context) discoveredMissingDependencies(module *moduleInfo, depName string, depVariations variationMap) (errs []error) {
3173	if depVariations != nil {
3174		depName = depName + "{" + c.prettyPrintVariant(depVariations) + "}"
3175	}
3176	if c.allowMissingDependencies {
3177		module.missingDeps = append(module.missingDeps, depName)
3178		return nil
3179	}
3180	return []error{c.missingDependencyError(module, depName)}
3181}
3182
3183func (c *Context) missingDependencyError(module *moduleInfo, depName string) (errs error) {
3184	err := c.nameInterface.MissingDependencyError(module.Name(), module.namespace(), depName)
3185
3186	return &BlueprintError{
3187		Err: err,
3188		Pos: module.pos,
3189	}
3190}
3191
3192func (c *Context) moduleGroupFromName(name string, namespace Namespace) *moduleGroup {
3193	group, exists := c.nameInterface.ModuleFromName(name, namespace)
3194	if exists {
3195		return group.moduleGroup
3196	}
3197	return nil
3198}
3199
3200func (c *Context) sortedModuleGroups() []*moduleGroup {
3201	if c.cachedSortedModuleGroups == nil || c.cachedDepsModified {
3202		unwrap := func(wrappers []ModuleGroup) []*moduleGroup {
3203			result := make([]*moduleGroup, 0, len(wrappers))
3204			for _, group := range wrappers {
3205				result = append(result, group.moduleGroup)
3206			}
3207			return result
3208		}
3209
3210		c.cachedSortedModuleGroups = unwrap(c.nameInterface.AllModules())
3211		c.cachedDepsModified = false
3212	}
3213
3214	return c.cachedSortedModuleGroups
3215}
3216
3217func (c *Context) visitAllModules(visit func(Module)) {
3218	var module *moduleInfo
3219
3220	defer func() {
3221		if r := recover(); r != nil {
3222			panic(newPanicErrorf(r, "VisitAllModules(%s) for %s",
3223				funcName(visit), module))
3224		}
3225	}()
3226
3227	for _, moduleGroup := range c.sortedModuleGroups() {
3228		for _, moduleOrAlias := range moduleGroup.modules {
3229			if module = moduleOrAlias.module(); module != nil {
3230				visit(module.logicModule)
3231			}
3232		}
3233	}
3234}
3235
3236func (c *Context) visitAllModulesIf(pred func(Module) bool,
3237	visit func(Module)) {
3238
3239	var module *moduleInfo
3240
3241	defer func() {
3242		if r := recover(); r != nil {
3243			panic(newPanicErrorf(r, "VisitAllModulesIf(%s, %s) for %s",
3244				funcName(pred), funcName(visit), module))
3245		}
3246	}()
3247
3248	for _, moduleGroup := range c.sortedModuleGroups() {
3249		for _, moduleOrAlias := range moduleGroup.modules {
3250			if module = moduleOrAlias.module(); module != nil {
3251				if pred(module.logicModule) {
3252					visit(module.logicModule)
3253				}
3254			}
3255		}
3256	}
3257}
3258
3259func (c *Context) visitAllModuleVariants(module *moduleInfo,
3260	visit func(Module)) {
3261
3262	var variant *moduleInfo
3263
3264	defer func() {
3265		if r := recover(); r != nil {
3266			panic(newPanicErrorf(r, "VisitAllModuleVariants(%s, %s) for %s",
3267				module, funcName(visit), variant))
3268		}
3269	}()
3270
3271	for _, moduleOrAlias := range module.group.modules {
3272		if variant = moduleOrAlias.module(); variant != nil {
3273			visit(variant.logicModule)
3274		}
3275	}
3276}
3277
3278func (c *Context) requireNinjaVersion(major, minor, micro int) {
3279	if major != 1 {
3280		panic("ninja version with major version != 1 not supported")
3281	}
3282	if c.requiredNinjaMinor < minor {
3283		c.requiredNinjaMinor = minor
3284		c.requiredNinjaMicro = micro
3285	}
3286	if c.requiredNinjaMinor == minor && c.requiredNinjaMicro < micro {
3287		c.requiredNinjaMicro = micro
3288	}
3289}
3290
3291func (c *Context) setOutDir(value ninjaString) {
3292	if c.outDir == nil {
3293		c.outDir = value
3294	}
3295}
3296
3297func (c *Context) makeUniquePackageNames(
3298	liveGlobals *liveTracker) (map[*packageContext]string, []string) {
3299
3300	pkgs := make(map[string]*packageContext)
3301	pkgNames := make(map[*packageContext]string)
3302	longPkgNames := make(map[*packageContext]bool)
3303
3304	processPackage := func(pctx *packageContext) {
3305		if pctx == nil {
3306			// This is a built-in rule and has no package.
3307			return
3308		}
3309		if _, ok := pkgNames[pctx]; ok {
3310			// We've already processed this package.
3311			return
3312		}
3313
3314		otherPkg, present := pkgs[pctx.shortName]
3315		if present {
3316			// Short name collision.  Both this package and the one that's
3317			// already there need to use their full names.  We leave the short
3318			// name in pkgNames for now so future collisions still get caught.
3319			longPkgNames[pctx] = true
3320			longPkgNames[otherPkg] = true
3321		} else {
3322			// No collision so far.  Tentatively set the package's name to be
3323			// its short name.
3324			pkgNames[pctx] = pctx.shortName
3325			pkgs[pctx.shortName] = pctx
3326		}
3327	}
3328
3329	// We try to give all packages their short name, but when we get collisions
3330	// we need to use the full unique package name.
3331	for v, _ := range liveGlobals.variables {
3332		processPackage(v.packageContext())
3333	}
3334	for p, _ := range liveGlobals.pools {
3335		processPackage(p.packageContext())
3336	}
3337	for r, _ := range liveGlobals.rules {
3338		processPackage(r.packageContext())
3339	}
3340
3341	// Add the packages that had collisions using their full unique names.  This
3342	// will overwrite any short names that were added in the previous step.
3343	for pctx := range longPkgNames {
3344		pkgNames[pctx] = pctx.fullName
3345	}
3346
3347	// Create deps list from calls to PackageContext.AddNinjaFileDeps
3348	deps := []string{}
3349	for _, pkg := range pkgs {
3350		deps = append(deps, pkg.ninjaFileDeps...)
3351	}
3352
3353	return pkgNames, deps
3354}
3355
3356// memoizeFullNames stores the full name of each live global variable, rule and pool since each is
3357// guaranteed to be used at least twice, once in the definition and once for each usage, and many
3358// are used much more than once.
3359func (c *Context) memoizeFullNames(liveGlobals *liveTracker, pkgNames map[*packageContext]string) {
3360	for v := range liveGlobals.variables {
3361		v.memoizeFullName(pkgNames)
3362	}
3363	for r := range liveGlobals.rules {
3364		r.memoizeFullName(pkgNames)
3365	}
3366	for p := range liveGlobals.pools {
3367		p.memoizeFullName(pkgNames)
3368	}
3369}
3370
3371func (c *Context) checkForVariableReferenceCycles(
3372	variables map[Variable]ninjaString, pkgNames map[*packageContext]string) {
3373
3374	visited := make(map[Variable]bool)  // variables that were already checked
3375	checking := make(map[Variable]bool) // variables actively being checked
3376
3377	var check func(v Variable) []Variable
3378
3379	check = func(v Variable) []Variable {
3380		visited[v] = true
3381		checking[v] = true
3382		defer delete(checking, v)
3383
3384		value := variables[v]
3385		for _, dep := range value.Variables() {
3386			if checking[dep] {
3387				// This is a cycle.
3388				return []Variable{dep, v}
3389			}
3390
3391			if !visited[dep] {
3392				cycle := check(dep)
3393				if cycle != nil {
3394					if cycle[0] == v {
3395						// We are the "start" of the cycle, so we're responsible
3396						// for generating the errors.  The cycle list is in
3397						// reverse order because all the 'check' calls append
3398						// their own module to the list.
3399						msgs := []string{"detected variable reference cycle:"}
3400
3401						// Iterate backwards through the cycle list.
3402						curName := v.fullName(pkgNames)
3403						curValue := value.Value(pkgNames)
3404						for i := len(cycle) - 1; i >= 0; i-- {
3405							next := cycle[i]
3406							nextName := next.fullName(pkgNames)
3407							nextValue := variables[next].Value(pkgNames)
3408
3409							msgs = append(msgs, fmt.Sprintf(
3410								"    %q depends on %q", curName, nextName))
3411							msgs = append(msgs, fmt.Sprintf(
3412								"    [%s = %s]", curName, curValue))
3413
3414							curName = nextName
3415							curValue = nextValue
3416						}
3417
3418						// Variable reference cycles are a programming error,
3419						// not the fault of the Blueprint file authors.
3420						panic(strings.Join(msgs, "\n"))
3421					} else {
3422						// We're not the "start" of the cycle, so we just append
3423						// our module to the list and return it.
3424						return append(cycle, v)
3425					}
3426				}
3427			}
3428		}
3429
3430		return nil
3431	}
3432
3433	for v := range variables {
3434		if !visited[v] {
3435			cycle := check(v)
3436			if cycle != nil {
3437				panic("inconceivable!")
3438			}
3439		}
3440	}
3441}
3442
3443// AllTargets returns a map all the build target names to the rule used to build
3444// them.  This is the same information that is output by running 'ninja -t
3445// targets all'.  If this is called before PrepareBuildActions successfully
3446// completes then ErrbuildActionsNotReady is returned.
3447func (c *Context) AllTargets() (map[string]string, error) {
3448	if !c.buildActionsReady {
3449		return nil, ErrBuildActionsNotReady
3450	}
3451
3452	targets := map[string]string{}
3453
3454	// Collect all the module build targets.
3455	for _, module := range c.moduleInfo {
3456		for _, buildDef := range module.actionDefs.buildDefs {
3457			ruleName := buildDef.Rule.fullName(c.pkgNames)
3458			for _, output := range append(buildDef.Outputs, buildDef.ImplicitOutputs...) {
3459				outputValue, err := output.Eval(c.globalVariables)
3460				if err != nil {
3461					return nil, err
3462				}
3463				targets[outputValue] = ruleName
3464			}
3465		}
3466	}
3467
3468	// Collect all the singleton build targets.
3469	for _, info := range c.singletonInfo {
3470		for _, buildDef := range info.actionDefs.buildDefs {
3471			ruleName := buildDef.Rule.fullName(c.pkgNames)
3472			for _, output := range append(buildDef.Outputs, buildDef.ImplicitOutputs...) {
3473				outputValue, err := output.Eval(c.globalVariables)
3474				if err != nil {
3475					return nil, err
3476				}
3477				targets[outputValue] = ruleName
3478			}
3479		}
3480	}
3481
3482	return targets, nil
3483}
3484
3485func (c *Context) OutDir() (string, error) {
3486	if c.outDir != nil {
3487		return c.outDir.Eval(c.globalVariables)
3488	} else {
3489		return "", nil
3490	}
3491}
3492
3493// ModuleTypePropertyStructs returns a mapping from module type name to a list of pointers to
3494// property structs returned by the factory for that module type.
3495func (c *Context) ModuleTypePropertyStructs() map[string][]interface{} {
3496	ret := make(map[string][]interface{})
3497	for moduleType, factory := range c.moduleFactories {
3498		_, ret[moduleType] = factory()
3499	}
3500
3501	return ret
3502}
3503
3504func (c *Context) ModuleTypeFactories() map[string]ModuleFactory {
3505	ret := make(map[string]ModuleFactory)
3506	for k, v := range c.moduleFactories {
3507		ret[k] = v
3508	}
3509	return ret
3510}
3511
3512func (c *Context) ModuleName(logicModule Module) string {
3513	module := c.moduleInfo[logicModule]
3514	return module.Name()
3515}
3516
3517func (c *Context) ModuleDir(logicModule Module) string {
3518	return filepath.Dir(c.BlueprintFile(logicModule))
3519}
3520
3521func (c *Context) ModuleSubDir(logicModule Module) string {
3522	module := c.moduleInfo[logicModule]
3523	return module.variant.name
3524}
3525
3526func (c *Context) ModuleType(logicModule Module) string {
3527	module := c.moduleInfo[logicModule]
3528	return module.typeName
3529}
3530
3531// ModuleProvider returns the value, if any, for the provider for a module.  If the value for the
3532// provider was not set it returns the zero value of the type of the provider, which means the
3533// return value can always be type-asserted to the type of the provider.  The return value should
3534// always be considered read-only.  It panics if called before the appropriate mutator or
3535// GenerateBuildActions pass for the provider on the module.  The value returned may be a deep
3536// copy of the value originally passed to SetProvider.
3537func (c *Context) ModuleProvider(logicModule Module, provider ProviderKey) interface{} {
3538	module := c.moduleInfo[logicModule]
3539	value, _ := c.provider(module, provider)
3540	return value
3541}
3542
3543// ModuleHasProvider returns true if the provider for the given module has been set.
3544func (c *Context) ModuleHasProvider(logicModule Module, provider ProviderKey) bool {
3545	module := c.moduleInfo[logicModule]
3546	_, ok := c.provider(module, provider)
3547	return ok
3548}
3549
3550func (c *Context) BlueprintFile(logicModule Module) string {
3551	module := c.moduleInfo[logicModule]
3552	return module.relBlueprintsFile
3553}
3554
3555func (c *Context) ModuleErrorf(logicModule Module, format string,
3556	args ...interface{}) error {
3557
3558	module := c.moduleInfo[logicModule]
3559	return &BlueprintError{
3560		Err: fmt.Errorf(format, args...),
3561		Pos: module.pos,
3562	}
3563}
3564
3565func (c *Context) VisitAllModules(visit func(Module)) {
3566	c.visitAllModules(visit)
3567}
3568
3569func (c *Context) VisitAllModulesIf(pred func(Module) bool,
3570	visit func(Module)) {
3571
3572	c.visitAllModulesIf(pred, visit)
3573}
3574
3575func (c *Context) VisitDirectDeps(module Module, visit func(Module)) {
3576	topModule := c.moduleInfo[module]
3577
3578	var visiting *moduleInfo
3579
3580	defer func() {
3581		if r := recover(); r != nil {
3582			panic(newPanicErrorf(r, "VisitDirectDeps(%s, %s) for dependency %s",
3583				topModule, funcName(visit), visiting))
3584		}
3585	}()
3586
3587	for _, dep := range topModule.directDeps {
3588		visiting = dep.module
3589		visit(dep.module.logicModule)
3590	}
3591}
3592
3593func (c *Context) VisitDirectDepsIf(module Module, pred func(Module) bool, visit func(Module)) {
3594	topModule := c.moduleInfo[module]
3595
3596	var visiting *moduleInfo
3597
3598	defer func() {
3599		if r := recover(); r != nil {
3600			panic(newPanicErrorf(r, "VisitDirectDepsIf(%s, %s, %s) for dependency %s",
3601				topModule, funcName(pred), funcName(visit), visiting))
3602		}
3603	}()
3604
3605	for _, dep := range topModule.directDeps {
3606		visiting = dep.module
3607		if pred(dep.module.logicModule) {
3608			visit(dep.module.logicModule)
3609		}
3610	}
3611}
3612
3613func (c *Context) VisitDepsDepthFirst(module Module, visit func(Module)) {
3614	topModule := c.moduleInfo[module]
3615
3616	var visiting *moduleInfo
3617
3618	defer func() {
3619		if r := recover(); r != nil {
3620			panic(newPanicErrorf(r, "VisitDepsDepthFirst(%s, %s) for dependency %s",
3621				topModule, funcName(visit), visiting))
3622		}
3623	}()
3624
3625	c.walkDeps(topModule, false, nil, func(dep depInfo, parent *moduleInfo) {
3626		visiting = dep.module
3627		visit(dep.module.logicModule)
3628	})
3629}
3630
3631func (c *Context) VisitDepsDepthFirstIf(module Module, pred func(Module) bool, visit func(Module)) {
3632	topModule := c.moduleInfo[module]
3633
3634	var visiting *moduleInfo
3635
3636	defer func() {
3637		if r := recover(); r != nil {
3638			panic(newPanicErrorf(r, "VisitDepsDepthFirstIf(%s, %s, %s) for dependency %s",
3639				topModule, funcName(pred), funcName(visit), visiting))
3640		}
3641	}()
3642
3643	c.walkDeps(topModule, false, nil, func(dep depInfo, parent *moduleInfo) {
3644		if pred(dep.module.logicModule) {
3645			visiting = dep.module
3646			visit(dep.module.logicModule)
3647		}
3648	})
3649}
3650
3651func (c *Context) PrimaryModule(module Module) Module {
3652	return c.moduleInfo[module].group.modules.firstModule().logicModule
3653}
3654
3655func (c *Context) FinalModule(module Module) Module {
3656	return c.moduleInfo[module].group.modules.lastModule().logicModule
3657}
3658
3659func (c *Context) VisitAllModuleVariants(module Module,
3660	visit func(Module)) {
3661
3662	c.visitAllModuleVariants(c.moduleInfo[module], visit)
3663}
3664
3665// Singletons returns a list of all registered Singletons.
3666func (c *Context) Singletons() []Singleton {
3667	var ret []Singleton
3668	for _, s := range c.singletonInfo {
3669		ret = append(ret, s.singleton)
3670	}
3671	return ret
3672}
3673
3674// SingletonName returns the name that the given singleton was registered with.
3675func (c *Context) SingletonName(singleton Singleton) string {
3676	for _, s := range c.singletonInfo {
3677		if s.singleton == singleton {
3678			return s.name
3679		}
3680	}
3681	return ""
3682}
3683
3684// WriteBuildFile writes the Ninja manifeset text for the generated build
3685// actions to w.  If this is called before PrepareBuildActions successfully
3686// completes then ErrBuildActionsNotReady is returned.
3687func (c *Context) WriteBuildFile(w io.StringWriter) error {
3688	var err error
3689	pprof.Do(c.Context, pprof.Labels("blueprint", "WriteBuildFile"), func(ctx context.Context) {
3690		if !c.buildActionsReady {
3691			err = ErrBuildActionsNotReady
3692			return
3693		}
3694
3695		nw := newNinjaWriter(w)
3696
3697		err = c.writeBuildFileHeader(nw)
3698		if err != nil {
3699			return
3700		}
3701
3702		err = c.writeNinjaRequiredVersion(nw)
3703		if err != nil {
3704			return
3705		}
3706
3707		err = c.writeSubninjas(nw)
3708		if err != nil {
3709			return
3710		}
3711
3712		// TODO: Group the globals by package.
3713
3714		err = c.writeGlobalVariables(nw)
3715		if err != nil {
3716			return
3717		}
3718
3719		err = c.writeGlobalPools(nw)
3720		if err != nil {
3721			return
3722		}
3723
3724		err = c.writeBuildDir(nw)
3725		if err != nil {
3726			return
3727		}
3728
3729		err = c.writeGlobalRules(nw)
3730		if err != nil {
3731			return
3732		}
3733
3734		err = c.writeAllModuleActions(nw)
3735		if err != nil {
3736			return
3737		}
3738
3739		err = c.writeAllSingletonActions(nw)
3740		if err != nil {
3741			return
3742		}
3743	})
3744
3745	if err != nil {
3746		return err
3747	}
3748
3749	return nil
3750}
3751
3752type pkgAssociation struct {
3753	PkgName string
3754	PkgPath string
3755}
3756
3757type pkgAssociationSorter struct {
3758	pkgs []pkgAssociation
3759}
3760
3761func (s *pkgAssociationSorter) Len() int {
3762	return len(s.pkgs)
3763}
3764
3765func (s *pkgAssociationSorter) Less(i, j int) bool {
3766	iName := s.pkgs[i].PkgName
3767	jName := s.pkgs[j].PkgName
3768	return iName < jName
3769}
3770
3771func (s *pkgAssociationSorter) Swap(i, j int) {
3772	s.pkgs[i], s.pkgs[j] = s.pkgs[j], s.pkgs[i]
3773}
3774
3775func (c *Context) writeBuildFileHeader(nw *ninjaWriter) error {
3776	headerTemplate := template.New("fileHeader")
3777	_, err := headerTemplate.Parse(fileHeaderTemplate)
3778	if err != nil {
3779		// This is a programming error.
3780		panic(err)
3781	}
3782
3783	var pkgs []pkgAssociation
3784	maxNameLen := 0
3785	for pkg, name := range c.pkgNames {
3786		pkgs = append(pkgs, pkgAssociation{
3787			PkgName: name,
3788			PkgPath: pkg.pkgPath,
3789		})
3790		if len(name) > maxNameLen {
3791			maxNameLen = len(name)
3792		}
3793	}
3794
3795	for i := range pkgs {
3796		pkgs[i].PkgName += strings.Repeat(" ", maxNameLen-len(pkgs[i].PkgName))
3797	}
3798
3799	sort.Sort(&pkgAssociationSorter{pkgs})
3800
3801	params := map[string]interface{}{
3802		"Pkgs": pkgs,
3803	}
3804
3805	buf := bytes.NewBuffer(nil)
3806	err = headerTemplate.Execute(buf, params)
3807	if err != nil {
3808		return err
3809	}
3810
3811	return nw.Comment(buf.String())
3812}
3813
3814func (c *Context) writeNinjaRequiredVersion(nw *ninjaWriter) error {
3815	value := fmt.Sprintf("%d.%d.%d", c.requiredNinjaMajor, c.requiredNinjaMinor,
3816		c.requiredNinjaMicro)
3817
3818	err := nw.Assign("ninja_required_version", value)
3819	if err != nil {
3820		return err
3821	}
3822
3823	return nw.BlankLine()
3824}
3825
3826func (c *Context) writeSubninjas(nw *ninjaWriter) error {
3827	for _, subninja := range c.subninjas {
3828		err := nw.Subninja(subninja)
3829		if err != nil {
3830			return err
3831		}
3832	}
3833	return nw.BlankLine()
3834}
3835
3836func (c *Context) writeBuildDir(nw *ninjaWriter) error {
3837	if c.outDir != nil {
3838		err := nw.Assign("builddir", c.outDir.Value(c.pkgNames))
3839		if err != nil {
3840			return err
3841		}
3842
3843		err = nw.BlankLine()
3844		if err != nil {
3845			return err
3846		}
3847	}
3848	return nil
3849}
3850
3851type globalEntity interface {
3852	fullName(pkgNames map[*packageContext]string) string
3853}
3854
3855type globalEntitySorter struct {
3856	pkgNames map[*packageContext]string
3857	entities []globalEntity
3858}
3859
3860func (s *globalEntitySorter) Len() int {
3861	return len(s.entities)
3862}
3863
3864func (s *globalEntitySorter) Less(i, j int) bool {
3865	iName := s.entities[i].fullName(s.pkgNames)
3866	jName := s.entities[j].fullName(s.pkgNames)
3867	return iName < jName
3868}
3869
3870func (s *globalEntitySorter) Swap(i, j int) {
3871	s.entities[i], s.entities[j] = s.entities[j], s.entities[i]
3872}
3873
3874func (c *Context) writeGlobalVariables(nw *ninjaWriter) error {
3875	visited := make(map[Variable]bool)
3876
3877	var walk func(v Variable) error
3878	walk = func(v Variable) error {
3879		visited[v] = true
3880
3881		// First visit variables on which this variable depends.
3882		value := c.globalVariables[v]
3883		for _, dep := range value.Variables() {
3884			if !visited[dep] {
3885				err := walk(dep)
3886				if err != nil {
3887					return err
3888				}
3889			}
3890		}
3891
3892		err := nw.Assign(v.fullName(c.pkgNames), value.Value(c.pkgNames))
3893		if err != nil {
3894			return err
3895		}
3896
3897		err = nw.BlankLine()
3898		if err != nil {
3899			return err
3900		}
3901
3902		return nil
3903	}
3904
3905	globalVariables := make([]globalEntity, 0, len(c.globalVariables))
3906	for variable := range c.globalVariables {
3907		globalVariables = append(globalVariables, variable)
3908	}
3909
3910	sort.Sort(&globalEntitySorter{c.pkgNames, globalVariables})
3911
3912	for _, entity := range globalVariables {
3913		v := entity.(Variable)
3914		if !visited[v] {
3915			err := walk(v)
3916			if err != nil {
3917				return nil
3918			}
3919		}
3920	}
3921
3922	return nil
3923}
3924
3925func (c *Context) writeGlobalPools(nw *ninjaWriter) error {
3926	globalPools := make([]globalEntity, 0, len(c.globalPools))
3927	for pool := range c.globalPools {
3928		globalPools = append(globalPools, pool)
3929	}
3930
3931	sort.Sort(&globalEntitySorter{c.pkgNames, globalPools})
3932
3933	for _, entity := range globalPools {
3934		pool := entity.(Pool)
3935		name := pool.fullName(c.pkgNames)
3936		def := c.globalPools[pool]
3937		err := def.WriteTo(nw, name)
3938		if err != nil {
3939			return err
3940		}
3941
3942		err = nw.BlankLine()
3943		if err != nil {
3944			return err
3945		}
3946	}
3947
3948	return nil
3949}
3950
3951func (c *Context) writeGlobalRules(nw *ninjaWriter) error {
3952	globalRules := make([]globalEntity, 0, len(c.globalRules))
3953	for rule := range c.globalRules {
3954		globalRules = append(globalRules, rule)
3955	}
3956
3957	sort.Sort(&globalEntitySorter{c.pkgNames, globalRules})
3958
3959	for _, entity := range globalRules {
3960		rule := entity.(Rule)
3961		name := rule.fullName(c.pkgNames)
3962		def := c.globalRules[rule]
3963		err := def.WriteTo(nw, name, c.pkgNames)
3964		if err != nil {
3965			return err
3966		}
3967
3968		err = nw.BlankLine()
3969		if err != nil {
3970			return err
3971		}
3972	}
3973
3974	return nil
3975}
3976
3977type depSorter []depInfo
3978
3979func (s depSorter) Len() int {
3980	return len(s)
3981}
3982
3983func (s depSorter) Less(i, j int) bool {
3984	iName := s[i].module.Name()
3985	jName := s[j].module.Name()
3986	if iName == jName {
3987		iName = s[i].module.variant.name
3988		jName = s[j].module.variant.name
3989	}
3990	return iName < jName
3991}
3992
3993func (s depSorter) Swap(i, j int) {
3994	s[i], s[j] = s[j], s[i]
3995}
3996
3997type moduleSorter struct {
3998	modules       []*moduleInfo
3999	nameInterface NameInterface
4000}
4001
4002func (s moduleSorter) Len() int {
4003	return len(s.modules)
4004}
4005
4006func (s moduleSorter) Less(i, j int) bool {
4007	iMod := s.modules[i]
4008	jMod := s.modules[j]
4009	iName := s.nameInterface.UniqueName(newNamespaceContext(iMod), iMod.group.name)
4010	jName := s.nameInterface.UniqueName(newNamespaceContext(jMod), jMod.group.name)
4011	if iName == jName {
4012		iVariantName := s.modules[i].variant.name
4013		jVariantName := s.modules[j].variant.name
4014		if iVariantName == jVariantName {
4015			panic(fmt.Sprintf("duplicate module name: %s %s: %#v and %#v\n",
4016				iName, iVariantName, iMod.variant.variations, jMod.variant.variations))
4017		} else {
4018			return iVariantName < jVariantName
4019		}
4020	} else {
4021		return iName < jName
4022	}
4023}
4024
4025func (s moduleSorter) Swap(i, j int) {
4026	s.modules[i], s.modules[j] = s.modules[j], s.modules[i]
4027}
4028
4029func (c *Context) writeAllModuleActions(nw *ninjaWriter) error {
4030	headerTemplate := template.New("moduleHeader")
4031	_, err := headerTemplate.Parse(moduleHeaderTemplate)
4032	if err != nil {
4033		// This is a programming error.
4034		panic(err)
4035	}
4036
4037	modules := make([]*moduleInfo, 0, len(c.moduleInfo))
4038	for _, module := range c.moduleInfo {
4039		modules = append(modules, module)
4040	}
4041	sort.Sort(moduleSorter{modules, c.nameInterface})
4042
4043	buf := bytes.NewBuffer(nil)
4044
4045	for _, module := range modules {
4046		if len(module.actionDefs.variables)+len(module.actionDefs.rules)+len(module.actionDefs.buildDefs) == 0 {
4047			continue
4048		}
4049
4050		buf.Reset()
4051
4052		// In order to make the bootstrap build manifest independent of the
4053		// build dir we need to output the Blueprints file locations in the
4054		// comments as paths relative to the source directory.
4055		relPos := module.pos
4056		relPos.Filename = module.relBlueprintsFile
4057
4058		// Get the name and location of the factory function for the module.
4059		factoryFunc := runtime.FuncForPC(reflect.ValueOf(module.factory).Pointer())
4060		factoryName := factoryFunc.Name()
4061
4062		infoMap := map[string]interface{}{
4063			"name":      module.Name(),
4064			"typeName":  module.typeName,
4065			"goFactory": factoryName,
4066			"pos":       relPos,
4067			"variant":   module.variant.name,
4068		}
4069		err = headerTemplate.Execute(buf, infoMap)
4070		if err != nil {
4071			return err
4072		}
4073
4074		err = nw.Comment(buf.String())
4075		if err != nil {
4076			return err
4077		}
4078
4079		err = nw.BlankLine()
4080		if err != nil {
4081			return err
4082		}
4083
4084		err = c.writeLocalBuildActions(nw, &module.actionDefs)
4085		if err != nil {
4086			return err
4087		}
4088
4089		err = nw.BlankLine()
4090		if err != nil {
4091			return err
4092		}
4093	}
4094
4095	return nil
4096}
4097
4098func (c *Context) writeAllSingletonActions(nw *ninjaWriter) error {
4099	headerTemplate := template.New("singletonHeader")
4100	_, err := headerTemplate.Parse(singletonHeaderTemplate)
4101	if err != nil {
4102		// This is a programming error.
4103		panic(err)
4104	}
4105
4106	buf := bytes.NewBuffer(nil)
4107
4108	for _, info := range c.singletonInfo {
4109		if len(info.actionDefs.variables)+len(info.actionDefs.rules)+len(info.actionDefs.buildDefs) == 0 {
4110			continue
4111		}
4112
4113		// Get the name of the factory function for the module.
4114		factory := info.factory
4115		factoryFunc := runtime.FuncForPC(reflect.ValueOf(factory).Pointer())
4116		factoryName := factoryFunc.Name()
4117
4118		buf.Reset()
4119		infoMap := map[string]interface{}{
4120			"name":      info.name,
4121			"goFactory": factoryName,
4122		}
4123		err = headerTemplate.Execute(buf, infoMap)
4124		if err != nil {
4125			return err
4126		}
4127
4128		err = nw.Comment(buf.String())
4129		if err != nil {
4130			return err
4131		}
4132
4133		err = nw.BlankLine()
4134		if err != nil {
4135			return err
4136		}
4137
4138		err = c.writeLocalBuildActions(nw, &info.actionDefs)
4139		if err != nil {
4140			return err
4141		}
4142
4143		err = nw.BlankLine()
4144		if err != nil {
4145			return err
4146		}
4147	}
4148
4149	return nil
4150}
4151
4152func (c *Context) BeginEvent(name string) {
4153	c.EventHandler.Begin(name)
4154}
4155
4156func (c *Context) EndEvent(name string) {
4157	c.EventHandler.End(name)
4158}
4159
4160func (c *Context) writeLocalBuildActions(nw *ninjaWriter,
4161	defs *localBuildActions) error {
4162
4163	// Write the local variable assignments.
4164	for _, v := range defs.variables {
4165		// A localVariable doesn't need the package names or config to
4166		// determine its name or value.
4167		name := v.fullName(nil)
4168		value, err := v.value(nil)
4169		if err != nil {
4170			panic(err)
4171		}
4172		err = nw.Assign(name, value.Value(c.pkgNames))
4173		if err != nil {
4174			return err
4175		}
4176	}
4177
4178	if len(defs.variables) > 0 {
4179		err := nw.BlankLine()
4180		if err != nil {
4181			return err
4182		}
4183	}
4184
4185	// Write the local rules.
4186	for _, r := range defs.rules {
4187		// A localRule doesn't need the package names or config to determine
4188		// its name or definition.
4189		name := r.fullName(nil)
4190		def, err := r.def(nil)
4191		if err != nil {
4192			panic(err)
4193		}
4194
4195		err = def.WriteTo(nw, name, c.pkgNames)
4196		if err != nil {
4197			return err
4198		}
4199
4200		err = nw.BlankLine()
4201		if err != nil {
4202			return err
4203		}
4204	}
4205
4206	// Write the build definitions.
4207	for _, buildDef := range defs.buildDefs {
4208		err := buildDef.WriteTo(nw, c.pkgNames)
4209		if err != nil {
4210			return err
4211		}
4212
4213		if len(buildDef.Args) > 0 {
4214			err = nw.BlankLine()
4215			if err != nil {
4216				return err
4217			}
4218		}
4219	}
4220
4221	return nil
4222}
4223
4224func beforeInModuleList(a, b *moduleInfo, list modulesOrAliases) bool {
4225	found := false
4226	if a == b {
4227		return false
4228	}
4229	for _, l := range list {
4230		if l.module() == a {
4231			found = true
4232		} else if l.module() == b {
4233			return found
4234		}
4235	}
4236
4237	missing := a
4238	if found {
4239		missing = b
4240	}
4241	panic(fmt.Errorf("element %v not found in list %v", missing, list))
4242}
4243
4244type panicError struct {
4245	panic interface{}
4246	stack []byte
4247	in    string
4248}
4249
4250func newPanicErrorf(panic interface{}, in string, a ...interface{}) error {
4251	buf := make([]byte, 4096)
4252	count := runtime.Stack(buf, false)
4253	return panicError{
4254		panic: panic,
4255		in:    fmt.Sprintf(in, a...),
4256		stack: buf[:count],
4257	}
4258}
4259
4260func (p panicError) Error() string {
4261	return fmt.Sprintf("panic in %s\n%s\n%s\n", p.in, p.panic, p.stack)
4262}
4263
4264func (p *panicError) addIn(in string) {
4265	p.in += " in " + in
4266}
4267
4268func funcName(f interface{}) string {
4269	return runtime.FuncForPC(reflect.ValueOf(f).Pointer()).Name()
4270}
4271
4272var fileHeaderTemplate = `******************************************************************************
4273***            This file is generated and should not be edited             ***
4274******************************************************************************
4275{{if .Pkgs}}
4276This file contains variables, rules, and pools with name prefixes indicating
4277they were generated by the following Go packages:
4278{{range .Pkgs}}
4279    {{.PkgName}} [from Go package {{.PkgPath}}]{{end}}{{end}}
4280
4281`
4282
4283var moduleHeaderTemplate = `# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
4284Module:  {{.name}}
4285Variant: {{.variant}}
4286Type:    {{.typeName}}
4287Factory: {{.goFactory}}
4288Defined: {{.pos}}
4289`
4290
4291var singletonHeaderTemplate = `# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
4292Singleton: {{.name}}
4293Factory:   {{.goFactory}}
4294`
4295
4296// Blueprint module type that can be used to gate blueprint files beneath this directory
4297type PackageIncludes struct {
4298	properties struct {
4299		// Package will be included if all include tags in this list are set
4300		Match_all []string
4301	}
4302	name *string `blueprint:"mutated"`
4303}
4304
4305func (pi *PackageIncludes) Name() string {
4306	return proptools.String(pi.name)
4307}
4308
4309// This module type does not have any build actions
4310func (pi *PackageIncludes) GenerateBuildActions(ctx ModuleContext) {
4311}
4312
4313func newPackageIncludesFactory() (Module, []interface{}) {
4314	module := &PackageIncludes{}
4315	AddLoadHook(module, func(ctx LoadHookContext) {
4316		module.name = proptools.StringPtr(ctx.ModuleDir() + "_includes") // Generate a synthetic name
4317	})
4318	return module, []interface{}{&module.properties}
4319}
4320
4321func RegisterPackageIncludesModuleType(ctx *Context) {
4322	ctx.RegisterModuleType("blueprint_package_includes", newPackageIncludesFactory)
4323}
4324
4325func (pi *PackageIncludes) MatchAll() []string {
4326	return pi.properties.Match_all
4327}
4328
4329// Returns true if all requested include tags are set in the Context object
4330func (pi *PackageIncludes) MatchesIncludeTags(ctx *Context) bool {
4331	if len(pi.MatchAll()) == 0 {
4332		ctx.ModuleErrorf(pi, "Match_all must be a non-empty list")
4333	}
4334	for _, includeTag := range pi.MatchAll() {
4335		if !ctx.ContainsIncludeTag(includeTag) {
4336			return false
4337		}
4338	}
4339	return true
4340}
4341