AAPT2: Sort artifacts based on the Play Store rules.

Sort output artifacts so that the updated versionCode manifest entry
will allow correct handling of updates from Play Store. The most
important dimension is Android SDK version. It is important that a split
based on min SDK version will allow a user to get a new APK if they
upgrade the OS on their device to support a new split.

ABI splits need to also be taken into consideration as it is possible
for a device to run in ARM emulation mode and installing an ARM APK over
a x86 APK could cause performance regressions.

The XML file format was updated to give each of the configuration groups
have their own section of the XML file. This allows the sort order to be
determined by a groups ordering. Artifacts can now be added to the
configuration file in an arbitrary order. Since this will be the common
case for developers, it will help reduce errors from inserting a new
artifact in the wrong spot.

The implementation follows the rules outlined at:
https://developer.android.com/google/play/publishing/multiple-apks.html

Test: Unit tests
Test: Manual process XML configuration

Change-Id: I0face862c6d6b9d3cd2d99088afe5b9491be0120
diff --git a/tools/aapt2/configuration/ConfigurationParser.internal.h b/tools/aapt2/configuration/ConfigurationParser.internal.h
index 7657ebd..a583057 100644
--- a/tools/aapt2/configuration/ConfigurationParser.internal.h
+++ b/tools/aapt2/configuration/ConfigurationParser.internal.h
@@ -17,35 +17,105 @@
 #ifndef AAPT2_CONFIGURATIONPARSER_INTERNAL_H
 #define AAPT2_CONFIGURATIONPARSER_INTERNAL_H
 
+#include "configuration/ConfigurationParser.h"
+
+#include <algorithm>
+#include <limits>
+
 namespace aapt {
+
+// Forward declaration of classes used in the API.
+namespace xml {
+class Element;
+}
+
 namespace configuration {
 
+template <typename T>
+struct OrderedEntry {
+  size_t order;
+  std::vector<T> entry;
+};
+
 /** A mapping of group labels to group of configuration items. */
 template <class T>
-using Group = std::unordered_map<std::string, std::vector<T>>;
+using Group = std::unordered_map<std::string, OrderedEntry<T>>;
 
 /** A mapping of group label to a single configuration item. */
 template <class T>
 using Entry = std::unordered_map<std::string, T>;
 
+/** Retrieves an entry from the provided Group, creating a new instance if one does not exist. */
+template <typename T>
+std::vector<T>& GetOrCreateGroup(std::string label, Group<T>* group) {
+  OrderedEntry<T>& entry = (*group)[label];
+  // If this is a new entry, set the order.
+  if (entry.order == 0) {
+    entry.order = group->size();
+  }
+  return entry.entry;
+}
+
+/**
+ * A ComparisonChain is a grouping of comparisons to perform when sorting groups that have a well
+ * defined order of precedence. Comparisons are only made if none of the previous comparisons had a
+ * definite result. A comparison has a result if at least one of the items has an entry for that
+ * value and that they are not equal.
+ */
+class ComparisonChain {
+ public:
+  /**
+   * Adds a new comparison of items in a group to the chain. The new comparison is only used if we
+   * have not been able to determine the sort order with the previous comparisons.
+   */
+  template <typename T>
+  ComparisonChain& Add(const Group<T>& groups, const Maybe<std::string>& lhs,
+                       const Maybe<std::string>& rhs) {
+    return Add(GetGroupOrder(groups, lhs), GetGroupOrder(groups, rhs));
+  }
+
+  /**
+   * Adds a new comparison to the chain. The new comparison is only used if we have not been able to
+   * determine the sort order with the previous comparisons.
+   */
+  ComparisonChain& Add(int lhs, int rhs) {
+    if (!has_result_) {
+      has_result_ = (lhs != rhs);
+      result_ = (lhs < rhs);
+    }
+    return *this;
+  }
+
+  /** Returns true if the left hand side should come before the right hand side. */
+  bool Compare() {
+    return result_;
+  }
+
+ private:
+  template <typename T>
+  inline size_t GetGroupOrder(const Group<T>& groups, const Maybe<std::string>& label) {
+    if (!label) {
+      return std::numeric_limits<size_t>::max();
+    }
+    return groups.at(label.value()).order;
+  }
+
+  bool has_result_ = false;
+  bool result_ = false;
+};
+
 /** Output artifact configuration options. */
 struct ConfiguredArtifact {
   /** Name to use for output of processing foo.apk -> foo.<name>.apk. */
   Maybe<std::string> name;
-  /**
-   * Value to add to the base Android manifest versionCode. If it is not present in the
-   * configuration file, it is set to the previous artifact + 1. If the first artifact does not have
-   * a value, artifacts are a 1 based index.
-   */
-  int version;
   /** If present, uses the ABI group with this name. */
   Maybe<std::string> abi_group;
   /** If present, uses the screen density group with this name. */
   Maybe<std::string> screen_density_group;
   /** If present, uses the locale group with this name. */
   Maybe<std::string> locale_group;
-  /** If present, uses the Android SDK group with this name. */
-  Maybe<std::string> android_sdk_group;
+  /** If present, uses the Android SDK with this name. */
+  Maybe<std::string> android_sdk;
   /** If present, uses the device feature group with this name. */
   Maybe<std::string> device_feature_group;
   /** If present, uses the OpenGL texture group with this name. */
@@ -57,31 +127,71 @@
 
   /** Convert an artifact name template into a name string based on configuration contents. */
   Maybe<std::string> Name(const android::StringPiece& apk_name, IDiagnostics* diag) const;
-
-  bool operator<(const ConfiguredArtifact& rhs) const {
-    // TODO(safarmer): Order by play store multi-APK requirements.
-    return version < rhs.version;
-  }
-
-  bool operator==(const ConfiguredArtifact& rhs) const {
-    return version == rhs.version;
-  }
 };
 
 /** AAPT2 XML configuration file binary representation. */
 struct PostProcessingConfiguration {
-  // TODO: Support named artifacts?
   std::vector<ConfiguredArtifact> artifacts;
   Maybe<std::string> artifact_format;
 
   Group<Abi> abi_groups;
   Group<ConfigDescription> screen_density_groups;
   Group<ConfigDescription> locale_groups;
-  Entry<AndroidSdk> android_sdk_groups;
   Group<DeviceFeature> device_feature_groups;
   Group<GlTexture> gl_texture_groups;
+  Entry<AndroidSdk> android_sdks;
+
+  /**
+   * Sorts the configured artifacts based on the ordering of the groups in the configuration file.
+   * The only exception to this rule is Android SDK versions. Larger SDK versions will have a larger
+   * versionCode to ensure users get the correct APK when they upgrade their OS.
+   */
+  void SortArtifacts() {
+    std::sort(artifacts.begin(), artifacts.end(), *this);
+  }
+
+  /** Comparator that ensures artifacts are in the preferred order for versionCode rewriting. */
+  bool operator()(const ConfiguredArtifact& lhs, const ConfiguredArtifact& rhs) {
+    // Split dimensions are added in the order of precedence. Items higher in the list result in
+    // higher version codes.
+    return ComparisonChain()
+        // All splits with a minSdkVersion specified must be last to ensure the application will be
+        // updated if a user upgrades the version of Android on their device.
+        .Add(GetMinSdk(lhs), GetMinSdk(rhs))
+        // ABI version is important, especially on x86 phones where they may begin to run in ARM
+        // emulation mode on newer Android versions. This allows us to ensure that the x86 version
+        // is installed on these devices rather than ARM.
+        .Add(abi_groups, lhs.abi_group, rhs.abi_group)
+        // The rest are in arbitrary order based on estimated usage.
+        .Add(screen_density_groups, lhs.screen_density_group, rhs.screen_density_group)
+        .Add(locale_groups, lhs.locale_group, rhs.locale_group)
+        .Add(gl_texture_groups, lhs.gl_texture_group, rhs.gl_texture_group)
+        .Add(device_feature_groups, lhs.device_feature_group, rhs.device_feature_group)
+        .Compare();
+  }
+
+ private:
+  /**
+   * Returns the min_sdk_version from the provided artifact or 0 if none is present. This allows
+   * artifacts that have an Android SDK version to have a higher versionCode than those that do not.
+   */
+  inline int GetMinSdk(const ConfiguredArtifact& artifact) {
+    if (!artifact.android_sdk) {
+      return 0;
+    }
+    const auto& entry = android_sdks.find(artifact.android_sdk.value());
+    if (entry == android_sdks.end()) {
+      return 0;
+    }
+    return entry->second.min_sdk_version;
+  }
 };
 
+/** Parses the provided XML document returning the post processing configuration. */
+Maybe<PostProcessingConfiguration> ExtractConfiguration(const std::string& contents,
+                                                        const std::string& config_path,
+                                                        IDiagnostics* diag);
+
 namespace handler {
 
 /** Handler for <artifact> tags. */
@@ -104,9 +214,9 @@
 bool LocaleGroupTagHandler(configuration::PostProcessingConfiguration* config,
                            xml::Element* element, IDiagnostics* diag);
 
-/** Handler for <android-sdk-group> tags. */
-bool AndroidSdkGroupTagHandler(configuration::PostProcessingConfiguration* config,
-                               xml::Element* element, IDiagnostics* diag);
+/** Handler for <android-sdk> tags. */
+bool AndroidSdkTagHandler(configuration::PostProcessingConfiguration* config, xml::Element* element,
+                          IDiagnostics* diag);
 
 /** Handler for <gl-texture-group> tags. */
 bool GlTextureGroupTagHandler(configuration::PostProcessingConfiguration* config,