core/java/com/android/internal/content/om/OverlayConfig.java - platform/frameworks/base - Git at Google

 /*
  * Copyright (C) 2020 The Android Open Source Project
  *
  * 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 com.android.internal.content.om;

 import android.annotation.NonNull;
 import android.annotation.Nullable;
 import android.content.pm.PackagePartitions;
 import android.os.Build;
 import android.os.Trace;
 import android.util.ArrayMap;
 import android.util.IndentingPrintWriter;
 import android.util.Log;

 import com.android.apex.ApexInfo;
 import com.android.apex.XmlParser;
 import com.android.internal.annotations.VisibleForTesting;
 import com.android.internal.content.om.OverlayConfigParser.OverlayPartition;
 import com.android.internal.content.om.OverlayConfigParser.ParsedConfiguration;
 import com.android.internal.content.om.OverlayScanner.ParsedOverlayInfo;
 import com.android.internal.util.Preconditions;
 import com.android.internal.util.function.TriConsumer;

 import org.w3c.dom.Document;
 import org.w3c.dom.Element;
 import org.w3c.dom.Node;
 import org.w3c.dom.NodeList;
 import org.xml.sax.SAXException;

 import java.io.File;
 import java.io.FileInputStream;
 import java.io.IOException;
 import java.io.PrintWriter;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.function.Supplier;

 import javax.xml.parsers.DocumentBuilder;
 import javax.xml.parsers.DocumentBuilderFactory;
 import javax.xml.parsers.ParserConfigurationException;

 /**
  * Responsible for reading overlay configuration files and handling queries of overlay mutability,
  * default-enabled state, and priority.
  *
  * @see OverlayConfigParser
  */
 @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
 public class OverlayConfig {
     static final String TAG = "OverlayConfig";

     // The default priority of an overlay that has not been configured. Overlays with default
     // priority have a higher precedence than configured overlays.
     @VisibleForTesting
     public static final int DEFAULT_PRIORITY = Integer.MAX_VALUE;

     public static final String PARTITION_ORDER_FILE_PATH = "/product/overlay/partition_order.xml";

     @VisibleForTesting
     public static final class Configuration {
         @Nullable
         public final ParsedConfiguration parsedConfig;

         public final int configIndex;

         public Configuration(@Nullable ParsedConfiguration parsedConfig, int configIndex) {
             this.parsedConfig = parsedConfig;
             this.configIndex = configIndex;
         }
     }

     /**
      * Interface for providing information on scanned packages.
      * TODO(147840005): Remove this when android:isStatic and android:priority are fully deprecated
      */
     public interface PackageProvider {

         /** Performs the given action for each package. */
         void forEachPackage(TriConsumer<Package, Boolean, File> p);

         interface Package {

             String getBaseApkPath();

             int getOverlayPriority();

             String getOverlayTarget();

             String getPackageName();

             int getTargetSdkVersion();

             boolean isOverlayIsStatic();
         }
     }

     private static final Comparator<ParsedConfiguration> sStaticOverlayComparator = (c1, c2) -> {
         final ParsedOverlayInfo o1 = c1.parsedInfo;
         final ParsedOverlayInfo o2 = c2.parsedInfo;
         Preconditions.checkArgument(o1.isStatic && o2.isStatic,
                 "attempted to sort non-static overlay");

         if (!o1.targetPackageName.equals(o2.targetPackageName)) {
             return o1.targetPackageName.compareTo(o2.targetPackageName);
         }

         final int comparedPriority = o1.priority - o2.priority;
         return comparedPriority == 0 ? o1.path.compareTo(o2.path) : comparedPriority;
     };

     // Map of overlay package name to configured overlay settings
     private final ArrayMap<String, Configuration> mConfigurations = new ArrayMap<>();

     // Singleton instance only assigned in system server
     private static OverlayConfig sInstance;

     private final String mPartitionOrder;

     private final boolean mIsDefaultPartitionOrder;

     @VisibleForTesting
     public OverlayConfig(@Nullable File rootDirectory,
             @Nullable Supplier<OverlayScanner> scannerFactory,
             @Nullable PackageProvider packageProvider) {
         Preconditions.checkArgument((scannerFactory == null) != (packageProvider == null),
                 "scannerFactory and packageProvider cannot be both null or both non-null");

         final ArrayList<OverlayPartition> partitions;
         if (rootDirectory == null) {
             partitions = new ArrayList<>(
                     PackagePartitions.getOrderedPartitions(OverlayPartition::new));
         } else {
             // Rebase the system partitions and settings file on the specified root directory.
             partitions = new ArrayList<>(PackagePartitions.getOrderedPartitions(
                     p -> new OverlayPartition(
                             new File(rootDirectory, p.getNonConicalFolder().getPath()),
                             p)));
         }
         mIsDefaultPartitionOrder = !sortPartitions(PARTITION_ORDER_FILE_PATH, partitions);
         mPartitionOrder = generatePartitionOrderString(partitions);

         ArrayMap<Integer, List<String>> activeApexesPerPartition = getActiveApexes(partitions);

         final Map<String, ParsedOverlayInfo> packageManagerOverlayInfos =
                 packageProvider == null ? null : getOverlayPackageInfos(packageProvider);

         final ArrayList<ParsedConfiguration> overlays = new ArrayList<>();
         for (int i = 0, n = partitions.size(); i < n; i++) {
             final OverlayPartition partition = partitions.get(i);
             final OverlayScanner scanner = (scannerFactory == null) ? null : scannerFactory.get();
             final ArrayList<ParsedConfiguration> partitionOverlays =
                     OverlayConfigParser.getConfigurations(partition, scanner,
                             packageManagerOverlayInfos,
                             activeApexesPerPartition.getOrDefault(partition.type,
                                     Collections.emptyList()));
             if (partitionOverlays != null) {
                 overlays.addAll(partitionOverlays);
                 continue;
             }

             // If the configuration file is not present, then use android:isStatic and
             // android:priority to configure the overlays in the partition.
             // TODO(147840005): Remove converting static overlays to immutable, default-enabled
             //  overlays when android:siStatic and android:priority are fully deprecated.
             final ArrayList<ParsedOverlayInfo> partitionOverlayInfos;
             if (scannerFactory != null) {
                 partitionOverlayInfos = new ArrayList<>(scanner.getAllParsedInfos());
             } else {
                 // Filter out overlays not present in the partition.
                 partitionOverlayInfos = new ArrayList<>(packageManagerOverlayInfos.values());
                 for (int j = partitionOverlayInfos.size() - 1; j >= 0; j--) {
                     if (!partition.containsFile(partitionOverlayInfos.get(j)
                             .getOriginalPartitionPath())) {
                         partitionOverlayInfos.remove(j);
                     }
                 }
             }

             // Static overlays are configured as immutable, default-enabled overlays.
             final ArrayList<ParsedConfiguration> partitionConfigs = new ArrayList<>();
             for (int j = 0, m = partitionOverlayInfos.size(); j < m; j++) {
                 final ParsedOverlayInfo p = partitionOverlayInfos.get(j);
                 if (p.isStatic) {
                     partitionConfigs.add(new ParsedConfiguration(p.packageName,
                             true /* enabled */, false /* mutable */, partition.policy, p, null));
                 }
             }

             partitionConfigs.sort(sStaticOverlayComparator);
             overlays.addAll(partitionConfigs);
         }

         for (int i = 0, n = overlays.size(); i < n; i++) {
             // Add the configurations to a map so definitions of an overlay in an earlier
             // partition can be replaced by an overlay with the same package name in a later
             // partition.
             final ParsedConfiguration config = overlays.get(i);
             mConfigurations.put(config.packageName, new Configuration(config, i));
         }
     }

     private static String generatePartitionOrderString(List<OverlayPartition> partitions) {
         if (partitions == null || partitions.size() == 0) {
             return "";
         }
         StringBuilder partitionOrder = new StringBuilder();
         partitionOrder.append(partitions.get(0).getName());
         for (int i = 1; i < partitions.size(); i++) {
             partitionOrder.append(", ").append(partitions.get(i).getName());
         }
         return partitionOrder.toString();
     }

     private static boolean parseAndValidatePartitionsOrderXml(String partitionOrderFilePath,
             Map<String, Integer> orderMap, List<OverlayPartition> partitions) {
         try {
             File file = new File(partitionOrderFilePath);
             if (!file.exists()) {
                 Log.w(TAG, "partition_order.xml does not exist.");
                 return false;
             }
             var dbFactory = DocumentBuilderFactory.newInstance();
             DocumentBuilder dBuilder = dbFactory.newDocumentBuilder();
             Document doc = dBuilder.parse(file);
             doc.getDocumentElement().normalize();

             Element root = doc.getDocumentElement();
             if (!root.getNodeName().equals("partition-order")) {
                 Log.w(TAG, "Invalid partition_order.xml, "
                         + "xml root element is not partition-order");
                 return false;
             }

             NodeList partitionList = doc.getElementsByTagName("partition");
             for (int order = 0; order < partitionList.getLength(); order++) {
                 Node partitionNode = partitionList.item(order);
                 if (partitionNode.getNodeType() == Node.ELEMENT_NODE) {
                     Element partitionElement = (Element) partitionNode;
                     String partitionName = partitionElement.getAttribute("name");
                     if (orderMap.containsKey(partitionName)) {
                         Log.w(TAG, "Invalid partition_order.xml, "
                                 + "it has duplicate partition: " + partitionName);
                         return false;
                     }
                     orderMap.put(partitionName, order);
                 }
             }

             if (orderMap.keySet().size() != partitions.size()) {
                 Log.w(TAG, "Invalid partition_order.xml, partition_order.xml has "
                         + orderMap.keySet().size() + " partitions, "
                         + "which is different from SYSTEM_PARTITIONS");
                 return false;
             }
             for (int i = 0; i < partitions.size(); i++) {
                 if (!orderMap.keySet().contains(partitions.get(i).getName())) {
                     Log.w(TAG, "Invalid Parsing partition_order.xml, "
                             + "partition_order.xml does not have partition: "
                             + partitions.get(i).getName());
                     return false;
                 }
             }
         } catch (ParserConfigurationException | SAXException | IOException e) {
             Log.w(TAG, "Parsing or validating partition_order.xml failed, "
                     + "exception thrown: " + e.getMessage());
             return false;
         }
         Log.i(TAG, "Sorting partitions in the specified order from partitions_order.xml");
         return true;
     }

     /**
      * Sort partitions by order in partition_order.xml if the file exists.
      *
      * @hide
      */
     @VisibleForTesting
     public static boolean sortPartitions(String partitionOrderFilePath,
             List<OverlayPartition> partitions) {
         Map<String, Integer> orderMap = new HashMap<>();
         if (!parseAndValidatePartitionsOrderXml(partitionOrderFilePath, orderMap, partitions)) {
             return false;
         }

         Comparator<OverlayPartition> partitionComparator = Comparator.comparingInt(
                 o -> orderMap.get(o.getName()));
         Collections.sort(partitions, partitionComparator);

         return true;
     }

     /**
      * Creates an instance of OverlayConfig for use in the zygote process.
      * This instance will not include information of static overlays existing outside of a partition
      * overlay directory.
      */
     @NonNull
     public static OverlayConfig getZygoteInstance() {
         Trace.traceBegin(Trace.TRACE_TAG_RRO, "OverlayConfig#getZygoteInstance");
         try {
             return new OverlayConfig(null /* rootDirectory */, OverlayScanner::new,
                     null /* packageProvider */);
         } finally {
             Trace.traceEnd(Trace.TRACE_TAG_RRO);
         }
     }

     /**
      * Initializes a singleton instance for use in the system process.
      * Can only be called once. This instance is cached so future invocations of
      * {@link #getSystemInstance()} will return the initialized instance.
      */
     @NonNull
     public static OverlayConfig initializeSystemInstance(PackageProvider packageProvider) {
         Trace.traceBegin(Trace.TRACE_TAG_RRO, "OverlayConfig#initializeSystemInstance");
         try {
             sInstance = new OverlayConfig(null, null, packageProvider);
         } finally {
             Trace.traceEnd(Trace.TRACE_TAG_RRO);
         }
         return sInstance;
     }

     /**
      * Retrieves the singleton instance initialized by
      * {@link #initializeSystemInstance(PackageProvider)}.
      */
     @NonNull
     public static OverlayConfig getSystemInstance() {
         if (sInstance == null) {
             throw new IllegalStateException("System instance not initialized");
         }

         return sInstance;
     }

     @VisibleForTesting
     @Nullable
     public Configuration getConfiguration(@NonNull String packageName) {
         return mConfigurations.get(packageName);
     }

     /**
      * Returns whether the overlay is enabled by default.
      * Overlays that are not configured are disabled by default.
      *
      * If an immutable overlay has its enabled state change, the new enabled state is applied to the
      * overlay.
      *
      * When a mutable is first seen by the OverlayManagerService, the default-enabled state will be
      * applied to the overlay. If the configured default-enabled state changes in a subsequent boot,
      * the default-enabled state will not be applied to the overlay.
      *
      * The configured enabled state will only be applied when:
      * <ul>
      * <li> The device is factory reset
      * <li> The overlay is removed from the device and added back to the device in a future OTA
      * <li> The overlay changes its package name
      * <li> The overlay changes its target package name or target overlayable name
      * <li> An immutable overlay becomes mutable
      * </ul>
      */
     public boolean isEnabled(String packageName) {
         final Configuration config = mConfigurations.get(packageName);
         return config == null? OverlayConfigParser.DEFAULT_ENABLED_STATE
                 : config.parsedConfig.enabled;
     }

     /**
      * Returns whether the overlay is mutable and can have its enabled state changed dynamically.
      * Overlays that are not configured are mutable.
      */
     public boolean isMutable(String packageName) {
         final Configuration config = mConfigurations.get(packageName);
         return config == null ? OverlayConfigParser.DEFAULT_MUTABILITY
                 : config.parsedConfig.mutable;
     }

     /**
      * Returns an integer corresponding to the priority of the overlay.
      * When multiple overlays override the same resource, the overlay with the highest priority will
      * will have its value chosen. Overlays that are not configured have a priority of
      * {@link Integer#MAX_VALUE}.
      */
     public int getPriority(String packageName) {
         final Configuration config = mConfigurations.get(packageName);
         return config == null ? DEFAULT_PRIORITY : config.configIndex;
     }

     @NonNull
     private ArrayList<Configuration> getSortedOverlays() {
         final ArrayList<Configuration> sortedOverlays = new ArrayList<>();
         for (int i = 0, n = mConfigurations.size(); i < n; i++) {
             sortedOverlays.add(mConfigurations.valueAt(i));
         }
         sortedOverlays.sort(Comparator.comparingInt(o -> o.configIndex));
         return sortedOverlays;
     }

     @NonNull
     private static Map<String, ParsedOverlayInfo> getOverlayPackageInfos(
             @NonNull PackageProvider packageManager) {
         final HashMap<String, ParsedOverlayInfo> overlays = new HashMap<>();
         packageManager.forEachPackage((PackageProvider.Package p, Boolean isSystem,
                 @Nullable File preInstalledApexPath) -> {
             if (p.getOverlayTarget() != null && isSystem) {
                 overlays.put(p.getPackageName(), new ParsedOverlayInfo(p.getPackageName(),
                         p.getOverlayTarget(), p.getTargetSdkVersion(), p.isOverlayIsStatic(),
                         p.getOverlayPriority(), new File(p.getBaseApkPath()),
                         preInstalledApexPath));
             }
         });
         return overlays;
     }

     /** Returns a map of PartitionType to List of active APEX module names. */
     @NonNull
     private static ArrayMap<Integer, List<String>> getActiveApexes(
             @NonNull List<OverlayPartition> partitions) {
         // An Overlay in an APEX, which is an update of an APEX in a given partition,
         // is considered as belonging to that partition.
         ArrayMap<Integer, List<String>> result = new ArrayMap<>();
         for (OverlayPartition partition : partitions) {
             result.put(partition.type, new ArrayList<String>());
         }
         // Read from apex-info-list because ApexManager is not accessible to zygote.
         File apexInfoList = new File("/apex/apex-info-list.xml");
         if (apexInfoList.exists() && apexInfoList.canRead()) {
             try (FileInputStream stream = new FileInputStream(apexInfoList)) {
                 List<ApexInfo> apexInfos = XmlParser.readApexInfoList(stream).getApexInfo();
                 for (ApexInfo info : apexInfos) {
                     if (info.getIsActive()) {
                         for (OverlayPartition partition : partitions) {
                             if (partition.containsPath(info.getPreinstalledModulePath())) {
                                 result.get(partition.type).add(info.getModuleName());
                                 break;
                             }
                         }
                     }
                 }
             } catch (Exception e) {
                 Log.w(TAG, "Error reading apex-info-list: " + e);
             }
         }
         return result;
     }

     /** Represents a single call to idmap create-multiple. */
     @VisibleForTesting
     public static class IdmapInvocation {
         public final boolean enforceOverlayable;
         public final String policy;
         public final ArrayList<String> overlayPaths = new ArrayList<>();

         IdmapInvocation(boolean enforceOverlayable, @NonNull String policy) {
             this.enforceOverlayable = enforceOverlayable;
             this.policy = policy;
         }

         @Override
         public String toString() {
             return getClass().getSimpleName() + String.format("{enforceOverlayable=%s, policy=%s"
                             + ", overlayPaths=[%s]}", enforceOverlayable, policy,
                     String.join(", ", overlayPaths));
         }
     }

     /**
      * Retrieves a list of immutable framework overlays in order of least precedence to greatest
      * precedence.
      */
     @VisibleForTesting
     public ArrayList<IdmapInvocation> getImmutableFrameworkOverlayIdmapInvocations() {
         final ArrayList<IdmapInvocation> idmapInvocations = new ArrayList<>();
         final ArrayList<Configuration> sortedConfigs = getSortedOverlays();
         for (int i = 0, n = sortedConfigs.size(); i < n; i++) {
             final Configuration overlay = sortedConfigs.get(i);
             if (overlay.parsedConfig.mutable || !overlay.parsedConfig.enabled
                     || !"android".equals(overlay.parsedConfig.parsedInfo.targetPackageName)) {
                 continue;
             }

             // Only enforce that overlays targeting packages with overlayable declarations abide by
             // those declarations if the target sdk of the overlay is at least Q (when overlayable
             // was introduced).
             final boolean enforceOverlayable = overlay.parsedConfig.parsedInfo.targetSdkVersion
                     >= Build.VERSION_CODES.Q;

             // Determine if the idmap for the current overlay can be generated in the last idmap
             // create-multiple invocation.
             IdmapInvocation invocation = null;
             if (!idmapInvocations.isEmpty()) {
                 final IdmapInvocation last = idmapInvocations.get(idmapInvocations.size() - 1);
                 if (last.enforceOverlayable == enforceOverlayable
                         && last.policy.equals(overlay.parsedConfig.policy)) {
                     invocation = last;
                 }
             }

             if (invocation == null) {
                 invocation = new IdmapInvocation(enforceOverlayable, overlay.parsedConfig.policy);
                 idmapInvocations.add(invocation);
             }

             invocation.overlayPaths.add(overlay.parsedConfig.parsedInfo.path.getAbsolutePath());
         }
         return idmapInvocations;
     }

     /**
      * Creates idmap files for immutable overlays targeting the framework packages. Currently the
      * android package is the only preloaded system package. Only the zygote can invoke this method.
      *
      * @return the paths of the created idmap files
      */
     @NonNull
     public String[] createImmutableFrameworkIdmapsInZygote() {
         final String targetPath = "/system/framework/framework-res.apk";
         final ArrayList<String> idmapPaths = new ArrayList<>();
         final ArrayList<IdmapInvocation> idmapInvocations =
                 getImmutableFrameworkOverlayIdmapInvocations();

         for (int i = 0, n = idmapInvocations.size(); i < n; i++) {
             final IdmapInvocation invocation = idmapInvocations.get(i);
             final String[] idmaps = createIdmap(targetPath,
                     invocation.overlayPaths.toArray(new String[0]),
                     new String[]{OverlayConfigParser.OverlayPartition.POLICY_PUBLIC,
                             invocation.policy},
                     invocation.enforceOverlayable);

             if (idmaps == null) {
                 Log.w(TAG, "'idmap2 create-multiple' failed: no mutable=\"false\" overlays"
                         + " targeting \"android\" will be loaded");
                 return new String[0];
             }

             idmapPaths.addAll(Arrays.asList(idmaps));
         }

         return idmapPaths.toArray(new String[0]);
     }

     /** Dump all overlay configurations to the Printer. */
     public void dump(@NonNull PrintWriter writer) {
         final IndentingPrintWriter ipw = new IndentingPrintWriter(writer);
         ipw.println("Overlay configurations:");
         ipw.increaseIndent();

         final ArrayList<Configuration> configurations = new ArrayList<>(mConfigurations.values());
         configurations.sort(Comparator.comparingInt(o -> o.configIndex));
         for (int i = 0; i < configurations.size(); i++) {
             final Configuration configuration = configurations.get(i);
             ipw.print(configuration.configIndex);
             ipw.print(", ");
             ipw.print(configuration.parsedConfig);
             ipw.println();
         }
         ipw.decreaseIndent();
         ipw.println();
     }

     /**
      * For each overlay APK, this creates the idmap file that allows the overlay to override the
      * target package.
      *
      * @return the paths of the created idmap
      */
     private static native String[] createIdmap(@NonNull String targetPath,
             @NonNull String[] overlayPath, @NonNull String[] policies, boolean enforceOverlayable);

     /**
      * @hide
      */
     public boolean isDefaultPartitionOrder() {
         return mIsDefaultPartitionOrder;
     }

     /**
      * @hide
      */
     public String getPartitionOrder() {
         return mPartitionOrder;
     }

 }
	/*
	* Copyright (C) 2020 The Android Open Source Project
	*
	* 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 com.android.internal.content.om;

	import android.annotation.NonNull;
	import android.annotation.Nullable;
	import android.content.pm.PackagePartitions;
	import android.os.Build;
	import android.os.Trace;
	import android.util.ArrayMap;
	import android.util.IndentingPrintWriter;
	import android.util.Log;

	import com.android.apex.ApexInfo;
	import com.android.apex.XmlParser;
	import com.android.internal.annotations.VisibleForTesting;
	import com.android.internal.content.om.OverlayConfigParser.OverlayPartition;
	import com.android.internal.content.om.OverlayConfigParser.ParsedConfiguration;
	import com.android.internal.content.om.OverlayScanner.ParsedOverlayInfo;
	import com.android.internal.util.Preconditions;
	import com.android.internal.util.function.TriConsumer;

	import org.w3c.dom.Document;
	import org.w3c.dom.Element;
	import org.w3c.dom.Node;
	import org.w3c.dom.NodeList;
	import org.xml.sax.SAXException;

	import java.io.File;
	import java.io.FileInputStream;
	import java.io.IOException;
	import java.io.PrintWriter;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.List;
	import java.util.Map;
	import java.util.function.Supplier;

	import javax.xml.parsers.DocumentBuilder;
	import javax.xml.parsers.DocumentBuilderFactory;
	import javax.xml.parsers.ParserConfigurationException;

	/**
	* Responsible for reading overlay configuration files and handling queries of overlay mutability,
	* default-enabled state, and priority.
	*
	* @see OverlayConfigParser
	*/
	@VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
	public class OverlayConfig {
	static final String TAG = "OverlayConfig";

	// The default priority of an overlay that has not been configured. Overlays with default
	// priority have a higher precedence than configured overlays.
	@VisibleForTesting
	public static final int DEFAULT_PRIORITY = Integer.MAX_VALUE;

	public static final String PARTITION_ORDER_FILE_PATH = "/product/overlay/partition_order.xml";

	@VisibleForTesting
	public static final class Configuration {
	@Nullable
	public final ParsedConfiguration parsedConfig;

	public final int configIndex;

	public Configuration(@Nullable ParsedConfiguration parsedConfig, int configIndex) {
	this.parsedConfig = parsedConfig;
	this.configIndex = configIndex;
	}
	}

	/**
	* Interface for providing information on scanned packages.
	* TODO(147840005): Remove this when android:isStatic and android:priority are fully deprecated
	*/
	public interface PackageProvider {

	/** Performs the given action for each package. */
	void forEachPackage(TriConsumer<Package, Boolean, File> p);

	interface Package {

	String getBaseApkPath();

	int getOverlayPriority();

	String getOverlayTarget();

	String getPackageName();

	int getTargetSdkVersion();

	boolean isOverlayIsStatic();
	}
	}

	private static final Comparator<ParsedConfiguration> sStaticOverlayComparator = (c1, c2) -> {
	final ParsedOverlayInfo o1 = c1.parsedInfo;
	final ParsedOverlayInfo o2 = c2.parsedInfo;
	Preconditions.checkArgument(o1.isStatic && o2.isStatic,
	"attempted to sort non-static overlay");

	if (!o1.targetPackageName.equals(o2.targetPackageName)) {
	return o1.targetPackageName.compareTo(o2.targetPackageName);
	}

	final int comparedPriority = o1.priority - o2.priority;
	return comparedPriority == 0 ? o1.path.compareTo(o2.path) : comparedPriority;
	};

	// Map of overlay package name to configured overlay settings
	private final ArrayMap<String, Configuration> mConfigurations = new ArrayMap<>();

	// Singleton instance only assigned in system server
	private static OverlayConfig sInstance;

	private final String mPartitionOrder;

	private final boolean mIsDefaultPartitionOrder;

	@VisibleForTesting
	public OverlayConfig(@Nullable File rootDirectory,
	@Nullable Supplier<OverlayScanner> scannerFactory,
	@Nullable PackageProvider packageProvider) {
	Preconditions.checkArgument((scannerFactory == null) != (packageProvider == null),
	"scannerFactory and packageProvider cannot be both null or both non-null");

	final ArrayList<OverlayPartition> partitions;
	if (rootDirectory == null) {
	partitions = new ArrayList<>(
	PackagePartitions.getOrderedPartitions(OverlayPartition::new));
	} else {
	// Rebase the system partitions and settings file on the specified root directory.
	partitions = new ArrayList<>(PackagePartitions.getOrderedPartitions(
	p -> new OverlayPartition(
	new File(rootDirectory, p.getNonConicalFolder().getPath()),
	p)));
	}
	mIsDefaultPartitionOrder = !sortPartitions(PARTITION_ORDER_FILE_PATH, partitions);
	mPartitionOrder = generatePartitionOrderString(partitions);

	ArrayMap<Integer, List<String>> activeApexesPerPartition = getActiveApexes(partitions);

	final Map<String, ParsedOverlayInfo> packageManagerOverlayInfos =
	packageProvider == null ? null : getOverlayPackageInfos(packageProvider);

	final ArrayList<ParsedConfiguration> overlays = new ArrayList<>();
	for (int i = 0, n = partitions.size(); i < n; i++) {
	final OverlayPartition partition = partitions.get(i);
	final OverlayScanner scanner = (scannerFactory == null) ? null : scannerFactory.get();
	final ArrayList<ParsedConfiguration> partitionOverlays =
	OverlayConfigParser.getConfigurations(partition, scanner,
	packageManagerOverlayInfos,
	activeApexesPerPartition.getOrDefault(partition.type,
	Collections.emptyList()));
	if (partitionOverlays != null) {
	overlays.addAll(partitionOverlays);
	continue;
	}

	// If the configuration file is not present, then use android:isStatic and
	// android:priority to configure the overlays in the partition.
	// TODO(147840005): Remove converting static overlays to immutable, default-enabled
	// overlays when android:siStatic and android:priority are fully deprecated.
	final ArrayList<ParsedOverlayInfo> partitionOverlayInfos;
	if (scannerFactory != null) {
	partitionOverlayInfos = new ArrayList<>(scanner.getAllParsedInfos());
	} else {
	// Filter out overlays not present in the partition.
	partitionOverlayInfos = new ArrayList<>(packageManagerOverlayInfos.values());
	for (int j = partitionOverlayInfos.size() - 1; j >= 0; j--) {
	if (!partition.containsFile(partitionOverlayInfos.get(j)
	.getOriginalPartitionPath())) {
	partitionOverlayInfos.remove(j);
	}
	}
	}

	// Static overlays are configured as immutable, default-enabled overlays.
	final ArrayList<ParsedConfiguration> partitionConfigs = new ArrayList<>();
	for (int j = 0, m = partitionOverlayInfos.size(); j < m; j++) {
	final ParsedOverlayInfo p = partitionOverlayInfos.get(j);
	if (p.isStatic) {
	partitionConfigs.add(new ParsedConfiguration(p.packageName,
	true /* enabled /, false / mutable */, partition.policy, p, null));
	}
	}

	partitionConfigs.sort(sStaticOverlayComparator);
	overlays.addAll(partitionConfigs);
	}

	for (int i = 0, n = overlays.size(); i < n; i++) {
	// Add the configurations to a map so definitions of an overlay in an earlier
	// partition can be replaced by an overlay with the same package name in a later
	// partition.
	final ParsedConfiguration config = overlays.get(i);
	mConfigurations.put(config.packageName, new Configuration(config, i));
	}
	}

	private static String generatePartitionOrderString(List<OverlayPartition> partitions) {
	if (partitions == null \|\| partitions.size() == 0) {
	return "";
	}
	StringBuilder partitionOrder = new StringBuilder();
	partitionOrder.append(partitions.get(0).getName());
	for (int i = 1; i < partitions.size(); i++) {
	partitionOrder.append(", ").append(partitions.get(i).getName());
	}
	return partitionOrder.toString();
	}

	private static boolean parseAndValidatePartitionsOrderXml(String partitionOrderFilePath,
	Map<String, Integer> orderMap, List<OverlayPartition> partitions) {
	try {
	File file = new File(partitionOrderFilePath);
	if (!file.exists()) {
	Log.w(TAG, "partition_order.xml does not exist.");
	return false;
	}
	var dbFactory = DocumentBuilderFactory.newInstance();
	DocumentBuilder dBuilder = dbFactory.newDocumentBuilder();
	Document doc = dBuilder.parse(file);
	doc.getDocumentElement().normalize();

	Element root = doc.getDocumentElement();
	if (!root.getNodeName().equals("partition-order")) {
	Log.w(TAG, "Invalid partition_order.xml, "
	+ "xml root element is not partition-order");
	return false;
	}

	NodeList partitionList = doc.getElementsByTagName("partition");
	for (int order = 0; order < partitionList.getLength(); order++) {
	Node partitionNode = partitionList.item(order);
	if (partitionNode.getNodeType() == Node.ELEMENT_NODE) {
	Element partitionElement = (Element) partitionNode;
	String partitionName = partitionElement.getAttribute("name");
	if (orderMap.containsKey(partitionName)) {
	Log.w(TAG, "Invalid partition_order.xml, "
	+ "it has duplicate partition: " + partitionName);
	return false;
	}
	orderMap.put(partitionName, order);
	}
	}

	if (orderMap.keySet().size() != partitions.size()) {
	Log.w(TAG, "Invalid partition_order.xml, partition_order.xml has "
	+ orderMap.keySet().size() + " partitions, "
	+ "which is different from SYSTEM_PARTITIONS");
	return false;
	}
	for (int i = 0; i < partitions.size(); i++) {
	if (!orderMap.keySet().contains(partitions.get(i).getName())) {
	Log.w(TAG, "Invalid Parsing partition_order.xml, "
	+ "partition_order.xml does not have partition: "
	+ partitions.get(i).getName());
	return false;
	}
	}
	} catch (ParserConfigurationException \| SAXException \| IOException e) {
	Log.w(TAG, "Parsing or validating partition_order.xml failed, "
	+ "exception thrown: " + e.getMessage());
	return false;
	}
	Log.i(TAG, "Sorting partitions in the specified order from partitions_order.xml");
	return true;
	}

	/**
	* Sort partitions by order in partition_order.xml if the file exists.
	*
	* @hide
	*/
	@VisibleForTesting
	public static boolean sortPartitions(String partitionOrderFilePath,
	List<OverlayPartition> partitions) {
	Map<String, Integer> orderMap = new HashMap<>();
	if (!parseAndValidatePartitionsOrderXml(partitionOrderFilePath, orderMap, partitions)) {
	return false;
	}

	Comparator<OverlayPartition> partitionComparator = Comparator.comparingInt(
	o -> orderMap.get(o.getName()));
	Collections.sort(partitions, partitionComparator);

	return true;
	}

	/**
	* Creates an instance of OverlayConfig for use in the zygote process.
	* This instance will not include information of static overlays existing outside of a partition
	* overlay directory.
	*/
	@NonNull
	public static OverlayConfig getZygoteInstance() {
	Trace.traceBegin(Trace.TRACE_TAG_RRO, "OverlayConfig#getZygoteInstance");
	try {
	return new OverlayConfig(null /* rootDirectory */, OverlayScanner::new,
	null /* packageProvider */);
	} finally {
	Trace.traceEnd(Trace.TRACE_TAG_RRO);
	}
	}

	/**
	* Initializes a singleton instance for use in the system process.
	* Can only be called once. This instance is cached so future invocations of
	* {@link #getSystemInstance()} will return the initialized instance.
	*/
	@NonNull
	public static OverlayConfig initializeSystemInstance(PackageProvider packageProvider) {
	Trace.traceBegin(Trace.TRACE_TAG_RRO, "OverlayConfig#initializeSystemInstance");
	try {
	sInstance = new OverlayConfig(null, null, packageProvider);
	} finally {
	Trace.traceEnd(Trace.TRACE_TAG_RRO);
	}
	return sInstance;
	}

	/**
	* Retrieves the singleton instance initialized by
	* {@link #initializeSystemInstance(PackageProvider)}.
	*/
	@NonNull
	public static OverlayConfig getSystemInstance() {
	if (sInstance == null) {
	throw new IllegalStateException("System instance not initialized");
	}

	return sInstance;
	}

	@VisibleForTesting
	@Nullable
	public Configuration getConfiguration(@NonNull String packageName) {
	return mConfigurations.get(packageName);
	}

	/**
	* Returns whether the overlay is enabled by default.
	* Overlays that are not configured are disabled by default.
	*
	* If an immutable overlay has its enabled state change, the new enabled state is applied to the
	* overlay.
	*
	* When a mutable is first seen by the OverlayManagerService, the default-enabled state will be
	* applied to the overlay. If the configured default-enabled state changes in a subsequent boot,
	* the default-enabled state will not be applied to the overlay.
	*
	* The configured enabled state will only be applied when:
	* <ul>
	* <li> The device is factory reset
	* <li> The overlay is removed from the device and added back to the device in a future OTA
	* <li> The overlay changes its package name
	* <li> The overlay changes its target package name or target overlayable name
	* <li> An immutable overlay becomes mutable
	* </ul>
	*/
	public boolean isEnabled(String packageName) {
	final Configuration config = mConfigurations.get(packageName);
	return config == null? OverlayConfigParser.DEFAULT_ENABLED_STATE
	: config.parsedConfig.enabled;
	}

	/**
	* Returns whether the overlay is mutable and can have its enabled state changed dynamically.
	* Overlays that are not configured are mutable.
	*/
	public boolean isMutable(String packageName) {
	final Configuration config = mConfigurations.get(packageName);
	return config == null ? OverlayConfigParser.DEFAULT_MUTABILITY
	: config.parsedConfig.mutable;
	}

	/**
	* Returns an integer corresponding to the priority of the overlay.
	* When multiple overlays override the same resource, the overlay with the highest priority will
	* will have its value chosen. Overlays that are not configured have a priority of
	* {@link Integer#MAX_VALUE}.
	*/
	public int getPriority(String packageName) {
	final Configuration config = mConfigurations.get(packageName);
	return config == null ? DEFAULT_PRIORITY : config.configIndex;
	}

	@NonNull
	private ArrayList<Configuration> getSortedOverlays() {
	final ArrayList<Configuration> sortedOverlays = new ArrayList<>();
	for (int i = 0, n = mConfigurations.size(); i < n; i++) {
	sortedOverlays.add(mConfigurations.valueAt(i));
	}
	sortedOverlays.sort(Comparator.comparingInt(o -> o.configIndex));
	return sortedOverlays;
	}

	@NonNull
	private static Map<String, ParsedOverlayInfo> getOverlayPackageInfos(
	@NonNull PackageProvider packageManager) {
	final HashMap<String, ParsedOverlayInfo> overlays = new HashMap<>();
	packageManager.forEachPackage((PackageProvider.Package p, Boolean isSystem,
	@Nullable File preInstalledApexPath) -> {
	if (p.getOverlayTarget() != null && isSystem) {
	overlays.put(p.getPackageName(), new ParsedOverlayInfo(p.getPackageName(),
	p.getOverlayTarget(), p.getTargetSdkVersion(), p.isOverlayIsStatic(),
	p.getOverlayPriority(), new File(p.getBaseApkPath()),
	preInstalledApexPath));
	}
	});
	return overlays;
	}

	/** Returns a map of PartitionType to List of active APEX module names. */
	@NonNull
	private static ArrayMap<Integer, List<String>> getActiveApexes(
	@NonNull List<OverlayPartition> partitions) {
	// An Overlay in an APEX, which is an update of an APEX in a given partition,
	// is considered as belonging to that partition.
	ArrayMap<Integer, List<String>> result = new ArrayMap<>();
	for (OverlayPartition partition : partitions) {
	result.put(partition.type, new ArrayList<String>());
	}
	// Read from apex-info-list because ApexManager is not accessible to zygote.
	File apexInfoList = new File("/apex/apex-info-list.xml");
	if (apexInfoList.exists() && apexInfoList.canRead()) {
	try (FileInputStream stream = new FileInputStream(apexInfoList)) {
	List<ApexInfo> apexInfos = XmlParser.readApexInfoList(stream).getApexInfo();
	for (ApexInfo info : apexInfos) {
	if (info.getIsActive()) {
	for (OverlayPartition partition : partitions) {
	if (partition.containsPath(info.getPreinstalledModulePath())) {
	result.get(partition.type).add(info.getModuleName());
	break;
	}
	}
	}
	}
	} catch (Exception e) {
	Log.w(TAG, "Error reading apex-info-list: " + e);
	}
	}
	return result;
	}

	/** Represents a single call to idmap create-multiple. */
	@VisibleForTesting
	public static class IdmapInvocation {
	public final boolean enforceOverlayable;
	public final String policy;
	public final ArrayList<String> overlayPaths = new ArrayList<>();

	IdmapInvocation(boolean enforceOverlayable, @NonNull String policy) {
	this.enforceOverlayable = enforceOverlayable;
	this.policy = policy;
	}

	@Override
	public String toString() {
	return getClass().getSimpleName() + String.format("{enforceOverlayable=%s, policy=%s"
	+ ", overlayPaths=[%s]}", enforceOverlayable, policy,
	String.join(", ", overlayPaths));
	}
	}

	/**
	* Retrieves a list of immutable framework overlays in order of least precedence to greatest
	* precedence.
	*/
	@VisibleForTesting
	public ArrayList<IdmapInvocation> getImmutableFrameworkOverlayIdmapInvocations() {
	final ArrayList<IdmapInvocation> idmapInvocations = new ArrayList<>();
	final ArrayList<Configuration> sortedConfigs = getSortedOverlays();
	for (int i = 0, n = sortedConfigs.size(); i < n; i++) {
	final Configuration overlay = sortedConfigs.get(i);
	if (overlay.parsedConfig.mutable \|\| !overlay.parsedConfig.enabled
	\|\| !"android".equals(overlay.parsedConfig.parsedInfo.targetPackageName)) {
	continue;
	}

	// Only enforce that overlays targeting packages with overlayable declarations abide by
	// those declarations if the target sdk of the overlay is at least Q (when overlayable
	// was introduced).
	final boolean enforceOverlayable = overlay.parsedConfig.parsedInfo.targetSdkVersion
	>= Build.VERSION_CODES.Q;

	// Determine if the idmap for the current overlay can be generated in the last idmap
	// create-multiple invocation.
	IdmapInvocation invocation = null;
	if (!idmapInvocations.isEmpty()) {
	final IdmapInvocation last = idmapInvocations.get(idmapInvocations.size() - 1);
	if (last.enforceOverlayable == enforceOverlayable
	&& last.policy.equals(overlay.parsedConfig.policy)) {
	invocation = last;
	}
	}

	if (invocation == null) {
	invocation = new IdmapInvocation(enforceOverlayable, overlay.parsedConfig.policy);
	idmapInvocations.add(invocation);
	}

	invocation.overlayPaths.add(overlay.parsedConfig.parsedInfo.path.getAbsolutePath());
	}
	return idmapInvocations;
	}

	/**
	* Creates idmap files for immutable overlays targeting the framework packages. Currently the
	* android package is the only preloaded system package. Only the zygote can invoke this method.
	*
	* @return the paths of the created idmap files
	*/
	@NonNull
	public String[] createImmutableFrameworkIdmapsInZygote() {
	final String targetPath = "/system/framework/framework-res.apk";
	final ArrayList<String> idmapPaths = new ArrayList<>();
	final ArrayList<IdmapInvocation> idmapInvocations =
	getImmutableFrameworkOverlayIdmapInvocations();

	for (int i = 0, n = idmapInvocations.size(); i < n; i++) {
	final IdmapInvocation invocation = idmapInvocations.get(i);
	final String[] idmaps = createIdmap(targetPath,
	invocation.overlayPaths.toArray(new String[0]),
	new String[]{OverlayConfigParser.OverlayPartition.POLICY_PUBLIC,
	invocation.policy},
	invocation.enforceOverlayable);

	if (idmaps == null) {
	Log.w(TAG, "'idmap2 create-multiple' failed: no mutable=\"false\" overlays"
	+ " targeting \"android\" will be loaded");
	return new String[0];
	}

	idmapPaths.addAll(Arrays.asList(idmaps));
	}

	return idmapPaths.toArray(new String[0]);
	}

	/** Dump all overlay configurations to the Printer. */
	public void dump(@NonNull PrintWriter writer) {
	final IndentingPrintWriter ipw = new IndentingPrintWriter(writer);
	ipw.println("Overlay configurations:");
	ipw.increaseIndent();

	final ArrayList<Configuration> configurations = new ArrayList<>(mConfigurations.values());
	configurations.sort(Comparator.comparingInt(o -> o.configIndex));
	for (int i = 0; i < configurations.size(); i++) {
	final Configuration configuration = configurations.get(i);
	ipw.print(configuration.configIndex);
	ipw.print(", ");
	ipw.print(configuration.parsedConfig);
	ipw.println();
	}
	ipw.decreaseIndent();
	ipw.println();
	}

	/**
	* For each overlay APK, this creates the idmap file that allows the overlay to override the
	* target package.
	*
	* @return the paths of the created idmap
	*/
	private static native String[] createIdmap(@NonNull String targetPath,
	@NonNull String[] overlayPath, @NonNull String[] policies, boolean enforceOverlayable);

	/**
	* @hide
	*/
	public boolean isDefaultPartitionOrder() {
	return mIsDefaultPartitionOrder;
	}

	/**
	* @hide
	*/
	public String getPartitionOrder() {
	return mPartitionOrder;
	}

	}