Revert "Revert "Soong support for namespaces""

This mostly reverts commit 178d5fefc0cea9d0f031c0bdee125b9d960f32c3
and mostly reapplies change I6d3e52ef62c4cabe85b9a135a54de0e1a6aab29c .

Bug: 65683273
Test: build/soong/scripts/diff_build_graphs.sh \
      --products=aosp_arm \
      'build/blueprint:work^ build/soong:work^' \
      'build/blueprint:work build/soong:work'
      # and see that the only changes were:
      # 1. adding some new files
      # 2. changing some line numbers
Test: m -j nothing # which runs unit tests

Change-Id: I32baae00277a547fdcdd1c2219fe6625ee0e45d7
diff --git a/android/namespace_test.go b/android/namespace_test.go
new file mode 100644
index 0000000..b10b528
--- /dev/null
+++ b/android/namespace_test.go
@@ -0,0 +1,652 @@
+// Copyright 2017 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package android
+
+import (
+	"errors"
+	"io/ioutil"
+	"os"
+	"path/filepath"
+	"testing"
+
+	"github.com/google/blueprint"
+)
+
+func TestDependingOnModuleInSameNamespace(t *testing.T) {
+	ctx := setupTest(t,
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+			}
+			test_module {
+				name: "b",
+				deps: ["a"],
+			}
+			`,
+		},
+	)
+
+	a := getModule(ctx, "a")
+	b := getModule(ctx, "b")
+	if !dependsOn(ctx, b, a) {
+		t.Errorf("module b does not depend on module a in the same namespace")
+	}
+}
+
+func TestDependingOnModuleInRootNamespace(t *testing.T) {
+	ctx := setupTest(t,
+		map[string]string{
+			".": `
+			test_module {
+				name: "b",
+				deps: ["a"],
+			}
+			test_module {
+				name: "a",
+			}
+			`,
+		},
+	)
+
+	a := getModule(ctx, "a")
+	b := getModule(ctx, "b")
+	if !dependsOn(ctx, b, a) {
+		t.Errorf("module b in root namespace does not depend on module a in the root namespace")
+	}
+}
+
+func TestImplicitlyImportRootNamespace(t *testing.T) {
+	_ = setupTest(t,
+		map[string]string{
+			".": `
+			test_module {
+				name: "a",
+			}
+			`,
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "b",
+				deps: ["a"],
+			}
+			`,
+		},
+	)
+
+	// setupTest will report any errors
+}
+
+func TestDependingOnModuleInImportedNamespace(t *testing.T) {
+	ctx := setupTest(t,
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+			}
+			`,
+			"dir2": `
+			soong_namespace {
+				imports: ["dir1"],
+			}
+			test_module {
+				name: "b",
+				deps: ["a"],
+			}
+			`,
+		},
+	)
+
+	a := getModule(ctx, "a")
+	b := getModule(ctx, "b")
+	if !dependsOn(ctx, b, a) {
+		t.Errorf("module b does not depend on module a in the same namespace")
+	}
+}
+
+func TestDependingOnModuleInNonImportedNamespace(t *testing.T) {
+	_, errs := setupTestExpectErrs(
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+			}
+			`,
+			"dir2": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+			}
+			`,
+			"dir3": `
+			soong_namespace {
+			}
+			test_module {
+				name: "b",
+				deps: ["a"],
+			}
+			`,
+		},
+	)
+
+	expectedErrors := []error{
+		errors.New(
+			`dir3/Blueprints:4:4: "b" depends on undefined module "a"
+Module "b" is defined in namespace "dir3" which can read these 2 namespaces: ["dir3" "."]
+Module "a" can be found in these namespaces: ["dir1" "dir2"]`),
+	}
+
+	if len(errs) != 1 || errs[0].Error() != expectedErrors[0].Error() {
+		t.Errorf("Incorrect errors. Expected:\n%v\n, got:\n%v\n", expectedErrors, errs)
+	}
+}
+
+func TestDependingOnModuleByFullyQualifiedReference(t *testing.T) {
+	ctx := setupTest(t,
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+			}
+			`,
+			"dir2": `
+			soong_namespace {
+			}
+			test_module {
+				name: "b",
+				deps: ["//dir1:a"],
+			}
+			`,
+		},
+	)
+	a := getModule(ctx, "a")
+	b := getModule(ctx, "b")
+	if !dependsOn(ctx, b, a) {
+		t.Errorf("module b does not depend on module a")
+	}
+}
+
+func TestSameNameInTwoNamespaces(t *testing.T) {
+	ctx := setupTest(t,
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+				id: "1",
+			}
+			test_module {
+				name: "b",
+				deps: ["a"],
+				id: "2",
+			}
+			`,
+			"dir2": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+				id:"3",
+			}
+			test_module {
+				name: "b",
+				deps: ["a"],
+				id:"4",
+			}
+			`,
+		},
+	)
+
+	one := findModuleById(ctx, "1")
+	two := findModuleById(ctx, "2")
+	three := findModuleById(ctx, "3")
+	four := findModuleById(ctx, "4")
+	if !dependsOn(ctx, two, one) {
+		t.Fatalf("Module 2 does not depend on module 1 in its namespace")
+	}
+	if dependsOn(ctx, two, three) {
+		t.Fatalf("Module 2 depends on module 3 in another namespace")
+	}
+	if !dependsOn(ctx, four, three) {
+		t.Fatalf("Module 4 does not depend on module 3 in its namespace")
+	}
+	if dependsOn(ctx, four, one) {
+		t.Fatalf("Module 4 depends on module 1 in another namespace")
+	}
+}
+
+func TestSearchOrder(t *testing.T) {
+	ctx := setupTest(t,
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+				id: "1",
+			}
+			`,
+			"dir2": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+				id:"2",
+			}
+			test_module {
+				name: "b",
+				id:"3",
+			}
+			`,
+			"dir3": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+				id:"4",
+			}
+			test_module {
+				name: "b",
+				id:"5",
+			}
+			test_module {
+				name: "c",
+				id:"6",
+			}
+			`,
+			".": `
+			test_module {
+				name: "a",
+				id: "7",
+			}
+			test_module {
+				name: "b",
+				id: "8",
+			}
+			test_module {
+				name: "c",
+				id: "9",
+			}
+			test_module {
+				name: "d",
+				id: "10",
+			}
+			`,
+			"dir4": `
+			soong_namespace {
+				imports: ["dir1", "dir2", "dir3"]
+			}
+			test_module {
+				name: "test_me",
+				id:"0",
+				deps: ["a", "b", "c", "d"],
+			}
+			`,
+		},
+	)
+
+	testMe := findModuleById(ctx, "0")
+	if !dependsOn(ctx, testMe, findModuleById(ctx, "1")) {
+		t.Errorf("test_me doesn't depend on id 1")
+	}
+	if !dependsOn(ctx, testMe, findModuleById(ctx, "3")) {
+		t.Errorf("test_me doesn't depend on id 3")
+	}
+	if !dependsOn(ctx, testMe, findModuleById(ctx, "6")) {
+		t.Errorf("test_me doesn't depend on id 6")
+	}
+	if !dependsOn(ctx, testMe, findModuleById(ctx, "10")) {
+		t.Errorf("test_me doesn't depend on id 10")
+	}
+	if numDeps(ctx, testMe) != 4 {
+		t.Errorf("num dependencies of test_me = %v, not 4\n", numDeps(ctx, testMe))
+	}
+}
+
+func TestTwoNamespacesCanImportEachOther(t *testing.T) {
+	_ = setupTest(t,
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+				imports: ["dir2"]
+			}
+			test_module {
+				name: "a",
+			}
+			test_module {
+				name: "c",
+				deps: ["b"],
+			}
+			`,
+			"dir2": `
+			soong_namespace {
+				imports: ["dir1"],
+			}
+			test_module {
+				name: "b",
+				deps: ["a"],
+			}
+			`,
+		},
+	)
+
+	// setupTest will report any errors
+}
+
+func TestImportingNonexistentNamespace(t *testing.T) {
+	_, errs := setupTestExpectErrs(
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+				imports: ["a_nonexistent_namespace"]
+			}
+			test_module {
+				name: "a",
+				deps: ["a_nonexistent_module"]
+			}
+			`,
+		},
+	)
+
+	// should complain about the missing namespace and not complain about the unresolvable dependency
+	expectedErrors := []error{
+		errors.New(`dir1/Blueprints:2:4: module "soong_namespace": namespace a_nonexistent_namespace does not exist`),
+	}
+	if len(errs) != 1 || errs[0].Error() != expectedErrors[0].Error() {
+		t.Errorf("Incorrect errors. Expected:\n%v\n, got:\n%v\n", expectedErrors, errs)
+	}
+}
+
+func TestNamespacesDontInheritParentNamespaces(t *testing.T) {
+	_, errs := setupTestExpectErrs(
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+			}
+			`,
+			"dir1/subdir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "b",
+				deps: ["a"],
+			}
+			`,
+		},
+	)
+
+	expectedErrors := []error{
+		errors.New(`dir1/subdir1/Blueprints:4:4: "b" depends on undefined module "a"
+Module "b" is defined in namespace "dir1/subdir1" which can read these 2 namespaces: ["dir1/subdir1" "."]
+Module "a" can be found in these namespaces: ["dir1"]`),
+	}
+	if len(errs) != 1 || errs[0].Error() != expectedErrors[0].Error() {
+		t.Errorf("Incorrect errors. Expected:\n%v\n, got:\n%v\n", expectedErrors, errs)
+	}
+}
+
+func TestModulesDoReceiveParentNamespace(t *testing.T) {
+	_ = setupTest(t,
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+			}
+			`,
+			"dir1/subdir": `
+			test_module {
+				name: "b",
+				deps: ["a"],
+			}
+			`,
+		},
+	)
+
+	// setupTest will report any errors
+}
+
+func TestNamespaceImportsNotTransitive(t *testing.T) {
+	_, errs := setupTestExpectErrs(
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a",
+			}
+			`,
+			"dir2": `
+			soong_namespace {
+				imports: ["dir1"],
+			}
+			test_module {
+				name: "b",
+				deps: ["a"],
+			}
+			`,
+			"dir3": `
+			soong_namespace {
+				imports: ["dir2"],
+			}
+			test_module {
+				name: "c",
+				deps: ["a"],
+			}
+			`,
+		},
+	)
+
+	expectedErrors := []error{
+		errors.New(`dir3/Blueprints:5:4: "c" depends on undefined module "a"
+Module "c" is defined in namespace "dir3" which can read these 3 namespaces: ["dir3" "dir2" "."]
+Module "a" can be found in these namespaces: ["dir1"]`),
+	}
+	if len(errs) != 1 || errs[0].Error() != expectedErrors[0].Error() {
+		t.Errorf("Incorrect errors. Expected:\n%v\n, got:\n%v\n", expectedErrors, errs)
+	}
+}
+
+func TestTwoNamepacesInSameDir(t *testing.T) {
+	_, errs := setupTestExpectErrs(
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			soong_namespace {
+			}
+			`,
+		},
+	)
+
+	expectedErrors := []error{
+		errors.New(`dir1/Blueprints:4:4: namespace dir1 already exists`),
+	}
+	if len(errs) != 1 || errs[0].Error() != expectedErrors[0].Error() {
+		t.Errorf("Incorrect errors. Expected:\n%v\n, got:\n%v\n", expectedErrors, errs)
+	}
+}
+
+func TestNamespaceNotAtTopOfFile(t *testing.T) {
+	_, errs := setupTestExpectErrs(
+		map[string]string{
+			"dir1": `
+			test_module {
+				name: "a"
+			}
+			soong_namespace {
+			}
+			`,
+		},
+	)
+
+	expectedErrors := []error{
+		errors.New(`dir1/Blueprints:5:4: a namespace must be the first module in the file`),
+	}
+	if len(errs) != 1 || errs[0].Error() != expectedErrors[0].Error() {
+		t.Errorf("Incorrect errors. Expected:\n%v\n, got:\n%v\n", expectedErrors, errs)
+	}
+}
+
+func TestTwoModulesWithSameNameInSameNamespace(t *testing.T) {
+	_, errs := setupTestExpectErrs(
+		map[string]string{
+			"dir1": `
+			soong_namespace {
+			}
+			test_module {
+				name: "a"
+			}
+			test_module {
+				name: "a"
+			}
+			`,
+		},
+	)
+
+	expectedErrors := []error{
+		errors.New(`dir1/Blueprints:7:4: module "a" already defined
+       dir1/Blueprints:4:4 <-- previous definition here`),
+	}
+	if len(errs) != 1 || errs[0].Error() != expectedErrors[0].Error() {
+		t.Errorf("Incorrect errors. Expected:\n%v\n, got:\n%v\n", expectedErrors, errs)
+	}
+}
+
+// some utils to support the tests
+
+func mockFiles(bps map[string]string) (files map[string][]byte) {
+	files = make(map[string][]byte, len(bps))
+	files["Blueprints"] = []byte("")
+	for dir, text := range bps {
+		files[filepath.Join(dir, "Blueprints")] = []byte(text)
+	}
+	return files
+}
+
+func setupTestExpectErrs(bps map[string]string) (ctx *TestContext, errs []error) {
+	buildDir, err := ioutil.TempDir("", "soong_namespace_test")
+	if err != nil {
+		return nil, []error{err}
+	}
+	defer os.RemoveAll(buildDir)
+
+	config := TestConfig(buildDir, nil)
+
+	ctx = NewTestContext()
+	ctx.MockFileSystem(mockFiles(bps))
+	ctx.RegisterModuleType("test_module", ModuleFactoryAdaptor(newTestModule))
+	ctx.RegisterModuleType("soong_namespace", ModuleFactoryAdaptor(NamespaceFactory))
+	ctx.PreDepsMutators(RegisterNamespaceMutator)
+	ctx.Register()
+
+	_, errs = ctx.ParseBlueprintsFiles("Blueprints")
+	if len(errs) > 0 {
+		return ctx, errs
+	}
+	_, errs = ctx.PrepareBuildActions(config)
+	return ctx, errs
+}
+
+func setupTest(t *testing.T, bps map[string]string) (ctx *TestContext) {
+	ctx, errs := setupTestExpectErrs(bps)
+	failIfErrored(t, errs)
+	return ctx
+}
+
+func dependsOn(ctx *TestContext, module TestingModule, possibleDependency TestingModule) bool {
+	depends := false
+	visit := func(dependency blueprint.Module) {
+		if dependency == possibleDependency.module {
+			depends = true
+		}
+	}
+	ctx.VisitDirectDeps(module.module, visit)
+	return depends
+}
+
+func numDeps(ctx *TestContext, module TestingModule) int {
+	count := 0
+	visit := func(dependency blueprint.Module) {
+		count++
+	}
+	ctx.VisitDirectDeps(module.module, visit)
+	return count
+}
+
+func getModule(ctx *TestContext, moduleName string) TestingModule {
+	return ctx.ModuleForTests(moduleName, "")
+}
+
+func findModuleById(ctx *TestContext, id string) (module TestingModule) {
+	visit := func(candidate blueprint.Module) {
+		testModule, ok := candidate.(*testModule)
+		if ok {
+			if testModule.properties.Id == id {
+				module = TestingModule{testModule}
+			}
+		}
+	}
+	ctx.VisitAllModules(visit)
+	return module
+}
+
+type testModule struct {
+	ModuleBase
+	properties struct {
+		Deps []string
+		Id   string
+	}
+}
+
+func (m *testModule) DepsMutator(ctx BottomUpMutatorContext) {
+	for _, d := range m.properties.Deps {
+		ctx.AddDependency(ctx.Module(), nil, d)
+	}
+}
+
+func (m *testModule) GenerateAndroidBuildActions(ModuleContext) {
+}
+
+func newTestModule() Module {
+	m := &testModule{}
+	m.AddProperties(&m.properties)
+	InitAndroidModule(m)
+	return m
+}
+
+func failIfErrored(t *testing.T, errs []error) {
+	if len(errs) > 0 {
+		for _, err := range errs {
+			t.Error(err)
+		}
+		t.FailNow()
+	}
+}