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