1// Copyright 2017 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 android
16
17import (
18	"errors"
19	"fmt"
20	"path/filepath"
21	"sort"
22	"strconv"
23	"strings"
24	"sync"
25
26	"github.com/google/blueprint"
27)
28
29func init() {
30	registerNamespaceBuildComponents(InitRegistrationContext)
31}
32
33func registerNamespaceBuildComponents(ctx RegistrationContext) {
34	ctx.RegisterModuleType("soong_namespace", NamespaceFactory)
35}
36
37// threadsafe sorted list
38type sortedNamespaces struct {
39	lock   sync.Mutex
40	items  []*Namespace
41	sorted bool
42}
43
44func (s *sortedNamespaces) add(namespace *Namespace) {
45	s.lock.Lock()
46	defer s.lock.Unlock()
47	if s.sorted {
48		panic("It is not supported to call sortedNamespaces.add() after sortedNamespaces.sortedItems()")
49	}
50	s.items = append(s.items, namespace)
51}
52
53func (s *sortedNamespaces) sortedItems() []*Namespace {
54	s.lock.Lock()
55	defer s.lock.Unlock()
56	if !s.sorted {
57		less := func(i int, j int) bool {
58			return s.items[i].Path < s.items[j].Path
59		}
60		sort.Slice(s.items, less)
61		s.sorted = true
62	}
63	return s.items
64}
65
66func (s *sortedNamespaces) index(namespace *Namespace) int {
67	for i, candidate := range s.sortedItems() {
68		if namespace == candidate {
69			return i
70		}
71	}
72	return -1
73}
74
75// A NameResolver implements blueprint.NameInterface, and implements the logic to
76// find a module from namespaces based on a query string.
77// A query string can be a module name or can be "//namespace_path:module_path"
78type NameResolver struct {
79	rootNamespace *Namespace
80
81	// id counter for atomic.AddInt32
82	nextNamespaceId int32
83
84	// All namespaces, without duplicates.
85	sortedNamespaces sortedNamespaces
86
87	// Map from dir to namespace. Will have duplicates if two dirs are part of the same namespace.
88	namespacesByDir sync.Map // if generics were supported, this would be sync.Map[string]*Namespace
89
90	// func telling whether to export a namespace to Kati
91	namespaceExportFilter func(*Namespace) bool
92}
93
94// NameResolverConfig provides the subset of the Config interface needed by the
95// NewNameResolver function.
96type NameResolverConfig interface {
97	// ExportedNamespaces is the list of namespaces that Soong must export to
98	// make.
99	ExportedNamespaces() []string
100}
101
102func NewNameResolver(config NameResolverConfig) *NameResolver {
103	namespacePathsToExport := make(map[string]bool)
104
105	for _, namespaceName := range config.ExportedNamespaces() {
106		namespacePathsToExport[namespaceName] = true
107	}
108
109	namespacePathsToExport["."] = true // always export the root namespace
110
111	namespaceExportFilter := func(namespace *Namespace) bool {
112		return namespacePathsToExport[namespace.Path]
113	}
114
115	r := &NameResolver{
116		namespacesByDir:       sync.Map{},
117		namespaceExportFilter: namespaceExportFilter,
118	}
119	r.rootNamespace = r.newNamespace(".")
120	r.rootNamespace.visibleNamespaces = []*Namespace{r.rootNamespace}
121	r.addNamespace(r.rootNamespace)
122
123	return r
124}
125
126func (r *NameResolver) newNamespace(path string) *Namespace {
127	namespace := NewNamespace(path)
128
129	namespace.exportToKati = r.namespaceExportFilter(namespace)
130
131	return namespace
132}
133
134func (r *NameResolver) addNewNamespaceForModule(module *NamespaceModule, path string) error {
135	fileName := filepath.Base(path)
136	if fileName != "Android.bp" {
137		return errors.New("A namespace may only be declared in a file named Android.bp")
138	}
139	dir := filepath.Dir(path)
140
141	namespace := r.newNamespace(dir)
142	module.namespace = namespace
143	module.resolver = r
144	namespace.importedNamespaceNames = module.properties.Imports
145	return r.addNamespace(namespace)
146}
147
148func (r *NameResolver) addNamespace(namespace *Namespace) (err error) {
149	existingNamespace, exists := r.namespaceAt(namespace.Path)
150	if exists {
151		if existingNamespace.Path == namespace.Path {
152			return fmt.Errorf("namespace %v already exists", namespace.Path)
153		} else {
154			// It would probably confuse readers if namespaces were declared anywhere but
155			// the top of the file, so we forbid declaring namespaces after anything else.
156			return fmt.Errorf("a namespace must be the first module in the file")
157		}
158	}
159	r.sortedNamespaces.add(namespace)
160
161	r.namespacesByDir.Store(namespace.Path, namespace)
162	return nil
163}
164
165// non-recursive check for namespace
166func (r *NameResolver) namespaceAt(path string) (namespace *Namespace, found bool) {
167	mapVal, found := r.namespacesByDir.Load(path)
168	if !found {
169		return nil, false
170	}
171	return mapVal.(*Namespace), true
172}
173
174// recursive search upward for a namespace
175func (r *NameResolver) findNamespace(path string) (namespace *Namespace) {
176	namespace, found := r.namespaceAt(path)
177	if found {
178		return namespace
179	}
180	parentDir := filepath.Dir(path)
181	if parentDir == path {
182		return nil
183	}
184	namespace = r.findNamespace(parentDir)
185	r.namespacesByDir.Store(path, namespace)
186	return namespace
187}
188
189// A NamespacelessModule can never be looked up by name.  It must still implement Name(), and the name
190// still has to be unique.
191type NamespacelessModule interface {
192	Namespaceless()
193}
194
195func (r *NameResolver) NewModule(ctx blueprint.NamespaceContext, moduleGroup blueprint.ModuleGroup, module blueprint.Module) (namespace blueprint.Namespace, errs []error) {
196	// if this module is a namespace, then save it to our list of namespaces
197	newNamespace, ok := module.(*NamespaceModule)
198	if ok {
199		err := r.addNewNamespaceForModule(newNamespace, ctx.ModulePath())
200		if err != nil {
201			return nil, []error{err}
202		}
203		return nil, nil
204	}
205
206	if _, ok := module.(NamespacelessModule); ok {
207		return nil, nil
208	}
209
210	// if this module is not a namespace, then save it into the appropriate namespace
211	ns := r.findNamespaceFromCtx(ctx)
212
213	_, errs = ns.moduleContainer.NewModule(ctx, moduleGroup, module)
214	if len(errs) > 0 {
215		return nil, errs
216	}
217
218	amod, ok := module.(Module)
219	if ok {
220		// inform the module whether its namespace is one that we want to export to Make
221		amod.base().commonProperties.NamespaceExportedToMake = ns.exportToKati
222		amod.base().commonProperties.DebugName = module.Name()
223	}
224
225	return ns, nil
226}
227
228func (r *NameResolver) NewSkippedModule(ctx blueprint.NamespaceContext, name string, skipInfo blueprint.SkippedModuleInfo) {
229	r.rootNamespace.moduleContainer.NewSkippedModule(ctx, name, skipInfo)
230}
231
232func (r *NameResolver) AllModules() []blueprint.ModuleGroup {
233	childLists := [][]blueprint.ModuleGroup{}
234	totalCount := 0
235	for _, namespace := range r.sortedNamespaces.sortedItems() {
236		newModules := namespace.moduleContainer.AllModules()
237		totalCount += len(newModules)
238		childLists = append(childLists, newModules)
239	}
240
241	allModules := make([]blueprint.ModuleGroup, 0, totalCount)
242	for _, childList := range childLists {
243		allModules = append(allModules, childList...)
244	}
245	return allModules
246}
247
248func (r *NameResolver) SkippedModuleFromName(moduleName string, namespace blueprint.Namespace) (skipInfos []blueprint.SkippedModuleInfo, skipped bool) {
249	return r.rootNamespace.moduleContainer.SkippedModuleFromName(moduleName, namespace)
250}
251
252// parses a fully-qualified path (like "//namespace_path:module_name") into a namespace name and a
253// module name
254func (r *NameResolver) parseFullyQualifiedName(name string) (namespaceName string, moduleName string, ok bool) {
255	if !strings.HasPrefix(name, "//") {
256		return "", "", false
257	}
258	name = strings.TrimPrefix(name, "//")
259	components := strings.Split(name, ":")
260	if len(components) != 2 {
261		return "", "", false
262	}
263	return components[0], components[1], true
264
265}
266
267func (r *NameResolver) getNamespacesToSearchForModule(sourceNamespace blueprint.Namespace) (searchOrder []*Namespace) {
268	ns, ok := sourceNamespace.(*Namespace)
269	if !ok || ns.visibleNamespaces == nil {
270		// When handling dependencies before namespaceMutator, assume they are non-Soong Blueprint modules and give
271		// access to all namespaces.
272		return r.sortedNamespaces.sortedItems()
273	}
274	return ns.visibleNamespaces
275}
276
277func (r *NameResolver) ModuleFromName(name string, namespace blueprint.Namespace) (group blueprint.ModuleGroup, found bool) {
278	// handle fully qualified references like "//namespace_path:module_name"
279	nsName, moduleName, isAbs := r.parseFullyQualifiedName(name)
280	if isAbs {
281		namespace, found := r.namespaceAt(nsName)
282		if !found {
283			return blueprint.ModuleGroup{}, false
284		}
285		container := namespace.moduleContainer
286		return container.ModuleFromName(moduleName, nil)
287	}
288	for _, candidate := range r.getNamespacesToSearchForModule(namespace) {
289		group, found = candidate.moduleContainer.ModuleFromName(name, nil)
290		if found {
291			return group, true
292		}
293	}
294	return blueprint.ModuleGroup{}, false
295
296}
297
298func (r *NameResolver) Rename(oldName string, newName string, namespace blueprint.Namespace) []error {
299	return namespace.(*Namespace).moduleContainer.Rename(oldName, newName, namespace)
300}
301
302// resolve each element of namespace.importedNamespaceNames and put the result in namespace.visibleNamespaces
303func (r *NameResolver) FindNamespaceImports(namespace *Namespace) (err error) {
304	namespace.visibleNamespaces = make([]*Namespace, 0, 2+len(namespace.importedNamespaceNames))
305	// search itself first
306	namespace.visibleNamespaces = append(namespace.visibleNamespaces, namespace)
307	// search its imports next
308	for _, name := range namespace.importedNamespaceNames {
309		imp, ok := r.namespaceAt(name)
310		if !ok {
311			return fmt.Errorf("namespace %v does not exist; Some necessary modules may have been skipped by Soong. Check if PRODUCT_SOURCE_ROOT_DIRS is pruning necessary Android.bp files.", name)
312		}
313		namespace.visibleNamespaces = append(namespace.visibleNamespaces, imp)
314	}
315	// search the root namespace last
316	namespace.visibleNamespaces = append(namespace.visibleNamespaces, r.rootNamespace)
317	return nil
318}
319
320func (r *NameResolver) chooseId(namespace *Namespace) {
321	id := r.sortedNamespaces.index(namespace)
322	if id < 0 {
323		panic(fmt.Sprintf("Namespace not found: %v\n", namespace.id))
324	}
325	namespace.id = strconv.Itoa(id)
326}
327
328func (r *NameResolver) MissingDependencyError(depender string, dependerNamespace blueprint.Namespace, depName string, guess []string) (err error) {
329	text := fmt.Sprintf("%q depends on undefined module %q.", depender, depName)
330
331	_, _, isAbs := r.parseFullyQualifiedName(depName)
332	if isAbs {
333		// if the user gave a fully-qualified name, we don't need to look for other
334		// modules that they might have been referring to
335		return fmt.Errorf(text)
336	}
337
338	// determine which namespaces the module can be found in
339	foundInNamespaces := []string{}
340	skippedDepErrors := []error{}
341	for _, namespace := range r.sortedNamespaces.sortedItems() {
342		_, found := namespace.moduleContainer.ModuleFromName(depName, nil)
343		if found {
344			foundInNamespaces = append(foundInNamespaces, namespace.Path)
345		}
346		_, skipped := namespace.moduleContainer.SkippedModuleFromName(depName, nil)
347		if skipped {
348			skippedDepErrors = append(skippedDepErrors, namespace.moduleContainer.MissingDependencyError(depender, dependerNamespace, depName, nil))
349		}
350	}
351
352	if len(foundInNamespaces) > 0 {
353		// determine which namespaces are visible to dependerNamespace
354		dependerNs := dependerNamespace.(*Namespace)
355		searched := r.getNamespacesToSearchForModule(dependerNs)
356		importedNames := []string{}
357		for _, ns := range searched {
358			importedNames = append(importedNames, ns.Path)
359		}
360		text += fmt.Sprintf("\nModule %q is defined in namespace %q which can read these %v namespaces: %q", depender, dependerNs.Path, len(importedNames), importedNames)
361		text += fmt.Sprintf("\nModule %q can be found in these namespaces: %q", depName, foundInNamespaces)
362	}
363	for _, err := range skippedDepErrors {
364		text += fmt.Sprintf("\n%s", err.Error())
365	}
366
367	if len(guess) > 0 {
368		text += fmt.Sprintf("\nOr did you mean %q?", guess)
369	}
370
371	return fmt.Errorf(text)
372}
373
374func (r *NameResolver) GetNamespace(ctx blueprint.NamespaceContext) blueprint.Namespace {
375	return r.findNamespaceFromCtx(ctx)
376}
377
378func (r *NameResolver) findNamespaceFromCtx(ctx blueprint.NamespaceContext) *Namespace {
379	return r.findNamespace(filepath.Dir(ctx.ModulePath()))
380}
381
382func (r *NameResolver) UniqueName(ctx blueprint.NamespaceContext, name string) (unique string) {
383	prefix := r.findNamespaceFromCtx(ctx).id
384	if prefix != "" {
385		prefix = prefix + "-"
386	}
387	return prefix + name
388}
389
390var _ blueprint.NameInterface = (*NameResolver)(nil)
391
392type Namespace struct {
393	blueprint.NamespaceMarker
394	Path string
395
396	// names of namespaces listed as imports by this namespace
397	importedNamespaceNames []string
398	// all namespaces that should be searched when a module in this namespace declares a dependency
399	visibleNamespaces []*Namespace
400
401	id string
402
403	exportToKati bool
404
405	moduleContainer blueprint.NameInterface
406}
407
408func NewNamespace(path string) *Namespace {
409	return &Namespace{Path: path, moduleContainer: blueprint.NewSimpleNameInterface()}
410}
411
412var _ blueprint.Namespace = (*Namespace)(nil)
413
414type namespaceProperties struct {
415	// a list of namespaces that contain modules that will be referenced
416	// by modules in this namespace.
417	Imports []string `android:"path"`
418}
419
420type NamespaceModule struct {
421	ModuleBase
422
423	namespace *Namespace
424	resolver  *NameResolver
425
426	properties namespaceProperties
427}
428
429func (n *NamespaceModule) GenerateAndroidBuildActions(ctx ModuleContext) {
430}
431
432func (n *NamespaceModule) GenerateBuildActions(ctx blueprint.ModuleContext) {
433}
434
435func (n *NamespaceModule) Name() (name string) {
436	return *n.nameProperties.Name
437}
438
439// soong_namespace provides a scope to modules in an Android.bp file to prevent
440// module name conflicts with other defined modules in different Android.bp
441// files. Once soong_namespace has been defined in an Android.bp file, the
442// namespacing is applied to all modules that follow the soong_namespace in
443// the current Android.bp file, as well as modules defined in Android.bp files
444// in subdirectories. An Android.bp file in a subdirectory can define its own
445// soong_namespace which is applied to all its modules and as well as modules
446// defined in subdirectories Android.bp files. Modules in a soong_namespace are
447// visible to Make by listing the namespace path in PRODUCT_SOONG_NAMESPACES
448// make variable in a makefile.
449func NamespaceFactory() Module {
450	module := &NamespaceModule{}
451
452	name := "soong_namespace"
453	module.nameProperties.Name = &name
454
455	module.AddProperties(&module.properties)
456	return module
457}
458
459func RegisterNamespaceMutator(ctx RegisterMutatorsContext) {
460	ctx.BottomUp("namespace_deps", namespaceMutator).Parallel()
461}
462
463func namespaceMutator(ctx BottomUpMutatorContext) {
464	module, ok := ctx.Module().(*NamespaceModule)
465	if ok {
466		err := module.resolver.FindNamespaceImports(module.namespace)
467		if err != nil {
468			ctx.ModuleErrorf(err.Error())
469		}
470
471		module.resolver.chooseId(module.namespace)
472	}
473}
474