Rework class loader context implementation.

The old representation consisted of a list of libraries (UsesLibraries),
a list of optional libraries (OptionalUsesLibraries) and a mapping from
library name to its build/install paths (LibraryPaths). The separation
into lists and map was necessary because of special handling of
compatibility libraries, which is now unified with normal libraries.

The new representation is a mapping from target SDK version to a tree
structure ClassLoaderContext. Each node of the tree represents a library
and contains library name, build/install paths and a slice of
subcontexts for dependencies. The same library may occur in the tree
multiple times in case it is a dependency of multiple libraries. The
order in which libraries are added matters (the resulting tree shape may
be different).

Test results have to be updated, as the resulting <uses-library> list is
reodered (previously it was a sorted list of map keys, and now it is
formed by a depth-first preorder traversal of the class loader tree).

Test: lunch aosp_cf_x86_phone-userdebug && m
Bug: 132357300
Bug: 168686456
Change-Id: I11be8cd2967f004fd58753d7c5fb99fed179cd63
diff --git a/java/aar.go b/java/aar.go
index 157d677..c8faed0 100644
--- a/java/aar.go
+++ b/java/aar.go
@@ -109,7 +109,7 @@
 	useEmbeddedNativeLibs   bool
 	useEmbeddedDex          bool
 	usesNonSdkApis          bool
-	sdkLibraries            dexpreopt.LibraryPaths
+	sdkLibraries            dexpreopt.ClassLoaderContextMap
 	hasNoCode               bool
 	LoggingParent           string
 	resourceFiles           android.Paths
@@ -392,7 +392,7 @@
 
 // aaptLibs collects libraries from dependencies and sdk_version and converts them into paths
 func aaptLibs(ctx android.ModuleContext, sdkContext sdkContext) (transitiveStaticLibs, transitiveStaticLibManifests android.Paths,
-	staticRRODirs []rroDir, assets, deps android.Paths, flags []string, sdkLibraries dexpreopt.LibraryPaths) {
+	staticRRODirs []rroDir, assets, deps android.Paths, flags []string, sdkLibraries dexpreopt.ClassLoaderContextMap) {
 
 	var sharedLibs android.Paths
 
@@ -401,7 +401,7 @@
 		sharedLibs = append(sharedLibs, sdkDep.jars...)
 	}
 
-	sdkLibraries = make(dexpreopt.LibraryPaths)
+	sdkLibraries = make(dexpreopt.ClassLoaderContextMap)
 
 	ctx.VisitDirectDeps(func(module android.Module) {
 		var exportPackage android.Path
@@ -411,7 +411,7 @@
 		}
 
 		if dep, ok := module.(Dependency); ok {
-			sdkLibraries.AddLibraryPaths(dep.ExportedSdkLibs())
+			sdkLibraries.AddContextMap(dep.ExportedSdkLibs())
 		}
 
 		switch ctx.OtherModuleDependencyTag(module) {
@@ -426,7 +426,7 @@
 			// (including the java_sdk_library) itself then append any implicit sdk library
 			// names to the list of sdk libraries to be added to the manifest.
 			if component, ok := module.(SdkLibraryComponentDependency); ok {
-				sdkLibraries.MaybeAddLibraryPath(ctx, component.OptionalImplicitSdkLibrary(),
+				sdkLibraries.MaybeAddContext(ctx, component.OptionalImplicitSdkLibrary(),
 					component.DexJarBuildPath(), component.DexJarInstallPath())
 			}
 
@@ -439,7 +439,7 @@
 				transitiveStaticLibs = append(transitiveStaticLibs, aarDep.ExportedStaticPackages()...)
 				transitiveStaticLibs = append(transitiveStaticLibs, exportPackage)
 				transitiveStaticLibManifests = append(transitiveStaticLibManifests, aarDep.ExportedManifests()...)
-				sdkLibraries.AddLibraryPaths(aarDep.ExportedSdkLibs())
+				sdkLibraries.AddContextMap(aarDep.ExportedSdkLibs())
 				if aarDep.ExportedAssets().Valid() {
 					assets = append(assets, aarDep.ExportedAssets().Path())
 				}
@@ -827,7 +827,7 @@
 	return nil
 }
 
-func (a *AARImport) ExportedSdkLibs() dexpreopt.LibraryPaths {
+func (a *AARImport) ExportedSdkLibs() dexpreopt.ClassLoaderContextMap {
 	return nil
 }
 
diff --git a/java/android_manifest.go b/java/android_manifest.go
index 62cd112..6b39c35 100644
--- a/java/android_manifest.go
+++ b/java/android_manifest.go
@@ -43,8 +43,9 @@
 	"args", "libs")
 
 // Uses manifest_fixer.py to inject minSdkVersion, etc. into an AndroidManifest.xml
-func manifestFixer(ctx android.ModuleContext, manifest android.Path, sdkContext sdkContext, sdkLibraries dexpreopt.LibraryPaths,
-	isLibrary, useEmbeddedNativeLibs, usesNonSdkApis, useEmbeddedDex, hasNoCode bool, loggingParent string) android.Path {
+func manifestFixer(ctx android.ModuleContext, manifest android.Path, sdkContext sdkContext,
+	sdkLibraries dexpreopt.ClassLoaderContextMap, isLibrary, useEmbeddedNativeLibs, usesNonSdkApis,
+	useEmbeddedDex, hasNoCode bool, loggingParent string) android.Path {
 
 	var args []string
 	if isLibrary {
@@ -70,7 +71,7 @@
 		args = append(args, "--use-embedded-dex")
 	}
 
-	for _, usesLib := range android.SortedStringKeys(sdkLibraries) {
+	for _, usesLib := range sdkLibraries.UsesLibs() {
 		if inList(usesLib, dexpreopt.OptionalCompatUsesLibs) {
 			args = append(args, "--optional-uses-library", usesLib)
 		} else {
diff --git a/java/androidmk.go b/java/androidmk.go
index e1a661f..c606245 100644
--- a/java/androidmk.go
+++ b/java/androidmk.go
@@ -115,7 +115,7 @@
 						entries.SetPath("LOCAL_SOONG_JACOCO_REPORT_CLASSES_JAR", library.jacocoReportClassesFile)
 					}
 
-					entries.AddStrings("LOCAL_EXPORT_SDK_LIBRARIES", android.SortedStringKeys(library.exportedSdkLibs)...)
+					entries.AddStrings("LOCAL_EXPORT_SDK_LIBRARIES", library.exportedSdkLibs.UsesLibs()...)
 
 					if len(library.additionalCheckedModules) != 0 {
 						entries.AddStrings("LOCAL_ADDITIONAL_CHECKED_MODULE", library.additionalCheckedModules.Strings()...)
diff --git a/java/app.go b/java/app.go
index c24e0c5..4848fae 100755
--- a/java/app.go
+++ b/java/app.go
@@ -601,7 +601,7 @@
 	return android.PathForModuleInstall(ctx, installDir, a.installApkName+".apk")
 }
 
-func (a *AndroidApp) dexBuildActions(ctx android.ModuleContext, sdkLibs dexpreopt.LibraryPaths) android.Path {
+func (a *AndroidApp) dexBuildActions(ctx android.ModuleContext, sdkLibs dexpreopt.ClassLoaderContextMap) android.Path {
 	a.dexpreopter.installPath = a.installPath(ctx)
 	if a.dexProperties.Uncompress_dex == nil {
 		// If the value was not force-set by the user, use reasonable default based on the module.
@@ -609,12 +609,10 @@
 	}
 	a.dexpreopter.uncompressedDex = *a.dexProperties.Uncompress_dex
 	a.dexpreopter.enforceUsesLibs = a.usesLibrary.enforceUsesLibraries()
-	a.dexpreopter.usesLibs = a.usesLibrary.usesLibraryProperties.Uses_libs
-	a.dexpreopter.optionalUsesLibs = a.usesLibrary.presentOptionalUsesLibs(ctx)
-	a.dexpreopter.libraryPaths = a.usesLibrary.usesLibraryPaths(ctx)
-	a.dexpreopter.libraryPaths.AddLibraryPaths(sdkLibs)
+	a.dexpreopter.classLoaderContexts = a.usesLibrary.classLoaderContextForUsesLibDeps(ctx)
+	a.dexpreopter.classLoaderContexts.AddContextMap(sdkLibs)
 	a.dexpreopter.manifestFile = a.mergedManifestFile
-	a.exportedSdkLibs = make(dexpreopt.LibraryPaths)
+	a.exportedSdkLibs = make(dexpreopt.ClassLoaderContextMap)
 
 	if ctx.ModuleName() != "framework-res" {
 		a.Module.compile(ctx, a.aaptSrcJar)
@@ -791,7 +789,7 @@
 	a.usesLibrary.freezeEnforceUsesLibraries()
 
 	// Add implicit SDK libraries to <uses-library> list.
-	for _, usesLib := range android.SortedStringKeys(a.aapt.sdkLibraries) {
+	for _, usesLib := range a.aapt.sdkLibraries.UsesLibs() {
 		a.usesLibrary.addLib(usesLib, inList(usesLib, dexpreopt.OptionalCompatUsesLibs))
 	}
 
@@ -1540,9 +1538,7 @@
 	a.dexpreopter.uncompressedDex = a.shouldUncompressDex(ctx)
 
 	a.dexpreopter.enforceUsesLibs = a.usesLibrary.enforceUsesLibraries()
-	a.dexpreopter.usesLibs = a.usesLibrary.usesLibraryProperties.Uses_libs
-	a.dexpreopter.optionalUsesLibs = a.usesLibrary.presentOptionalUsesLibs(ctx)
-	a.dexpreopter.libraryPaths = a.usesLibrary.usesLibraryPaths(ctx)
+	a.dexpreopter.classLoaderContexts = a.usesLibrary.classLoaderContextForUsesLibDeps(ctx)
 
 	dexOutput := a.dexpreopter.dexpreopt(ctx, jnisUncompressed)
 	if a.dexpreopter.uncompressedDex {
@@ -1976,17 +1972,18 @@
 	return optionalUsesLibs
 }
 
-// usesLibraryPaths returns a map of module names of shared library dependencies to the paths
+// Returns a map of module names of shared library dependencies to the paths
 // to their dex jars on host and on device.
-func (u *usesLibrary) usesLibraryPaths(ctx android.ModuleContext) dexpreopt.LibraryPaths {
-	usesLibPaths := make(dexpreopt.LibraryPaths)
+func (u *usesLibrary) classLoaderContextForUsesLibDeps(ctx android.ModuleContext) dexpreopt.ClassLoaderContextMap {
+	clcMap := make(dexpreopt.ClassLoaderContextMap)
 
 	if !ctx.Config().UnbundledBuild() {
 		ctx.VisitDirectDeps(func(m android.Module) {
-			if _, ok := ctx.OtherModuleDependencyTag(m).(usesLibraryDependencyTag); ok {
+			if tag, ok := ctx.OtherModuleDependencyTag(m).(usesLibraryDependencyTag); ok {
 				dep := ctx.OtherModuleName(m)
 				if lib, ok := m.(Dependency); ok {
-					usesLibPaths.AddLibraryPath(ctx, dep, lib.DexJarBuildPath(), lib.DexJarInstallPath())
+					clcMap.AddContextForSdk(ctx, tag.sdkVersion, dep,
+						lib.DexJarBuildPath(), lib.DexJarInstallPath(), lib.ExportedSdkLibs())
 				} else if ctx.Config().AllowMissingDependencies() {
 					ctx.AddMissingDependencies([]string{dep})
 				} else {
@@ -1996,7 +1993,7 @@
 		})
 	}
 
-	return usesLibPaths
+	return clcMap
 }
 
 // enforceUsesLibraries returns true of <uses-library> tags should be checked against uses_libs and optional_uses_libs
diff --git a/java/app_test.go b/java/app_test.go
index 82577e3..d9e4d3a 100644
--- a/java/app_test.go
+++ b/java/app_test.go
@@ -2815,11 +2815,11 @@
 	// Test that all present libraries are preopted, including implicit SDK dependencies, possibly stubs
 	cmd = app.Rule("dexpreopt").RuleParams.Command
 	w := `--target-context-for-sdk any ` +
-		`PCL[/system/framework/foo.jar]#` +
-		`PCL[/system/framework/quuz.jar]#` +
 		`PCL[/system/framework/qux.jar]#` +
-		`PCL[/system/framework/runtime-library.jar]#` +
-		`PCL[/system/framework/bar.jar]`
+		`PCL[/system/framework/quuz.jar]#` +
+		`PCL[/system/framework/foo.jar]#` +
+		`PCL[/system/framework/bar.jar]#` +
+		`PCL[/system/framework/runtime-library.jar]`
 	if !strings.Contains(cmd, w) {
 		t.Errorf("wanted %q in %q", w, cmd)
 	}
diff --git a/java/device_host_converter.go b/java/device_host_converter.go
index 40a2280..d8b617e 100644
--- a/java/device_host_converter.go
+++ b/java/device_host_converter.go
@@ -163,7 +163,7 @@
 	return nil
 }
 
-func (d *DeviceHostConverter) ExportedSdkLibs() dexpreopt.LibraryPaths {
+func (d *DeviceHostConverter) ExportedSdkLibs() dexpreopt.ClassLoaderContextMap {
 	return nil
 }
 
diff --git a/java/dexpreopt.go b/java/dexpreopt.go
index 20dbc66..a21fb76 100644
--- a/java/dexpreopt.go
+++ b/java/dexpreopt.go
@@ -33,11 +33,9 @@
 	isTest              bool
 	isPresignedPrebuilt bool
 
-	manifestFile     android.Path
-	usesLibs         []string
-	optionalUsesLibs []string
-	enforceUsesLibs  bool
-	libraryPaths     dexpreopt.LibraryPaths
+	manifestFile        android.Path
+	enforceUsesLibs     bool
+	classLoaderContexts dexpreopt.ClassLoaderContextMap
 
 	builtInstalled string
 }
@@ -193,10 +191,8 @@
 		ProfileIsTextListing: profileIsTextListing,
 		ProfileBootListing:   profileBootListing,
 
-		EnforceUsesLibraries:  d.enforceUsesLibs,
-		OptionalUsesLibraries: d.optionalUsesLibs,
-		UsesLibraries:         d.usesLibs,
-		LibraryPaths:          d.libraryPaths,
+		EnforceUsesLibraries: d.enforceUsesLibs,
+		ClassLoaderContexts:  d.classLoaderContexts,
 
 		Archs:                   archs,
 		DexPreoptImages:         images,
diff --git a/java/java.go b/java/java.go
index 9f09051..31466b0 100644
--- a/java/java.go
+++ b/java/java.go
@@ -416,8 +416,8 @@
 	// manifest file to use instead of properties.Manifest
 	overrideManifest android.OptionalPath
 
-	// map of SDK libs exported by this java module to their build and install paths
-	exportedSdkLibs dexpreopt.LibraryPaths
+	// map of SDK version to class loader context
+	exportedSdkLibs dexpreopt.ClassLoaderContextMap
 
 	// list of plugins that this java module is exporting
 	exportedPluginJars android.Paths
@@ -509,7 +509,7 @@
 	ImplementationJars() android.Paths
 	ResourceJars() android.Paths
 	AidlIncludeDirs() android.Paths
-	ExportedSdkLibs() dexpreopt.LibraryPaths
+	ExportedSdkLibs() dexpreopt.ClassLoaderContextMap
 	ExportedPlugins() (android.Paths, []string)
 	SrcJarArgs() ([]string, android.Paths)
 	BaseModuleName() string
@@ -1027,7 +1027,8 @@
 			case libTag:
 				deps.classpath = append(deps.classpath, dep.SdkHeaderJars(ctx, j.sdkVersion())...)
 				// names of sdk libs that are directly depended are exported
-				j.exportedSdkLibs.MaybeAddLibraryPath(ctx, dep.OptionalImplicitSdkLibrary(), dep.DexJarBuildPath(), dep.DexJarInstallPath())
+				j.exportedSdkLibs.MaybeAddContext(ctx, dep.OptionalImplicitSdkLibrary(),
+					dep.DexJarBuildPath(), dep.DexJarInstallPath())
 			case staticLibTag:
 				ctx.ModuleErrorf("dependency on java_sdk_library %q can only be in libs", otherName)
 			}
@@ -1038,7 +1039,7 @@
 			case libTag, instrumentationForTag:
 				deps.classpath = append(deps.classpath, dep.HeaderJars()...)
 				// sdk lib names from dependencies are re-exported
-				j.exportedSdkLibs.AddLibraryPaths(dep.ExportedSdkLibs())
+				j.exportedSdkLibs.AddContextMap(dep.ExportedSdkLibs())
 				deps.aidlIncludeDirs = append(deps.aidlIncludeDirs, dep.AidlIncludeDirs()...)
 				pluginJars, pluginClasses := dep.ExportedPlugins()
 				addPlugins(&deps, pluginJars, pluginClasses...)
@@ -1050,7 +1051,7 @@
 				deps.staticHeaderJars = append(deps.staticHeaderJars, dep.HeaderJars()...)
 				deps.staticResourceJars = append(deps.staticResourceJars, dep.ResourceJars()...)
 				// sdk lib names from dependencies are re-exported
-				j.exportedSdkLibs.AddLibraryPaths(dep.ExportedSdkLibs())
+				j.exportedSdkLibs.AddContextMap(dep.ExportedSdkLibs())
 				deps.aidlIncludeDirs = append(deps.aidlIncludeDirs, dep.AidlIncludeDirs()...)
 				pluginJars, pluginClasses := dep.ExportedPlugins()
 				addPlugins(&deps, pluginJars, pluginClasses...)
@@ -1902,7 +1903,7 @@
 	return j.exportAidlIncludeDirs
 }
 
-func (j *Module) ExportedSdkLibs() dexpreopt.LibraryPaths {
+func (j *Module) ExportedSdkLibs() dexpreopt.ClassLoaderContextMap {
 	return j.exportedSdkLibs
 }
 
@@ -2041,7 +2042,7 @@
 		j.dexProperties.Uncompress_dex = proptools.BoolPtr(shouldUncompressDex(ctx, &j.dexpreopter))
 	}
 	j.dexpreopter.uncompressedDex = *j.dexProperties.Uncompress_dex
-	j.exportedSdkLibs = make(dexpreopt.LibraryPaths)
+	j.exportedSdkLibs = make(dexpreopt.ClassLoaderContextMap)
 	j.compile(ctx, nil)
 
 	// Collect the module directory for IDE info in java/jdeps.go.
@@ -2061,11 +2062,12 @@
 	// add the name of that java_sdk_library to the exported sdk libs to make sure
 	// that, if necessary, a <uses-library> element for that java_sdk_library is
 	// added to the Android manifest.
-	j.exportedSdkLibs.MaybeAddLibraryPath(ctx, j.OptionalImplicitSdkLibrary(), j.DexJarBuildPath(), j.DexJarInstallPath())
+	j.exportedSdkLibs.MaybeAddContext(ctx, j.OptionalImplicitSdkLibrary(),
+		j.DexJarBuildPath(), j.DexJarInstallPath())
 
 	// A non-SDK library may provide a <uses-library> (the name may be different from the module name).
 	if lib := proptools.String(j.usesLibraryProperties.Provides_uses_lib); lib != "" {
-		j.exportedSdkLibs.AddLibraryPath(ctx, lib, j.DexJarBuildPath(), j.DexJarInstallPath())
+		j.exportedSdkLibs.AddContext(ctx, lib, j.DexJarBuildPath(), j.DexJarInstallPath())
 	}
 
 	j.distFiles = j.GenerateTaggedDistFiles(ctx)
@@ -2644,7 +2646,7 @@
 	dexJarFile android.Path
 
 	combinedClasspathFile android.Path
-	exportedSdkLibs       dexpreopt.LibraryPaths
+	exportedSdkLibs       dexpreopt.ClassLoaderContextMap
 	exportAidlIncludeDirs android.Paths
 
 	hideApexVariantFromMake bool
@@ -2719,7 +2721,7 @@
 		TransformJetifier(ctx, outputFile, inputFile)
 	}
 	j.combinedClasspathFile = outputFile
-	j.exportedSdkLibs = make(dexpreopt.LibraryPaths)
+	j.exportedSdkLibs = make(dexpreopt.ClassLoaderContextMap)
 
 	var flags javaBuilderFlags
 
@@ -2733,7 +2735,7 @@
 			case libTag, staticLibTag:
 				flags.classpath = append(flags.classpath, dep.HeaderJars()...)
 				// sdk lib names from dependencies are re-exported
-				j.exportedSdkLibs.AddLibraryPaths(dep.ExportedSdkLibs())
+				j.exportedSdkLibs.AddContextMap(dep.ExportedSdkLibs())
 			case bootClasspathTag:
 				flags.bootClasspath = append(flags.bootClasspath, dep.HeaderJars()...)
 			}
@@ -2742,7 +2744,8 @@
 			case libTag:
 				flags.classpath = append(flags.classpath, dep.SdkHeaderJars(ctx, j.sdkVersion())...)
 				// names of sdk libs that are directly depended are exported
-				j.exportedSdkLibs.AddLibraryPath(ctx, otherName, dep.DexJarBuildPath(), dep.DexJarInstallPath())
+				j.exportedSdkLibs.AddContext(ctx, otherName,
+					dep.DexJarBuildPath(), dep.DexJarInstallPath())
 			}
 		}
 	})
@@ -2757,7 +2760,8 @@
 	// add the name of that java_sdk_library to the exported sdk libs to make sure
 	// that, if necessary, a <uses-library> element for that java_sdk_library is
 	// added to the Android manifest.
-	j.exportedSdkLibs.MaybeAddLibraryPath(ctx, j.OptionalImplicitSdkLibrary(), outputFile, installFile)
+	j.exportedSdkLibs.MaybeAddContext(ctx, j.OptionalImplicitSdkLibrary(),
+		outputFile, installFile)
 
 	j.exportAidlIncludeDirs = android.PathsForModuleSrc(ctx, j.properties.Aidl.Export_include_dirs)
 
@@ -2839,7 +2843,7 @@
 	return j.exportAidlIncludeDirs
 }
 
-func (j *Import) ExportedSdkLibs() dexpreopt.LibraryPaths {
+func (j *Import) ExportedSdkLibs() dexpreopt.ClassLoaderContextMap {
 	return j.exportedSdkLibs
 }
 
diff --git a/java/java_test.go b/java/java_test.go
index 6c0a908..81c4f22 100644
--- a/java/java_test.go
+++ b/java/java_test.go
@@ -1593,8 +1593,8 @@
 	// test if baz has exported SDK lib names foo and bar to qux
 	qux := ctx.ModuleForTests("qux", "android_common")
 	if quxLib, ok := qux.Module().(*Library); ok {
-		sdkLibs := android.SortedStringKeys(quxLib.ExportedSdkLibs())
-		if w := []string{"bar", "foo", "fred", "quuz"}; !reflect.DeepEqual(w, sdkLibs) {
+		sdkLibs := quxLib.ExportedSdkLibs().UsesLibs()
+		if w := []string{"foo", "bar", "fred", "quuz"}; !reflect.DeepEqual(w, sdkLibs) {
 			t.Errorf("qux should export %q but exports %q", w, sdkLibs)
 		}
 	}