5 files changed, 177 insertions, 15 deletions

diff --git a/tools/aapt2/optimize/MultiApkGenerator.cpp b/tools/aapt2/optimize/MultiApkGenerator.cpp
index 8c9c43409569..c686a10a3fa9 100644
--- a/tools/aapt2/optimize/MultiApkGenerator.cpp
+++ b/tools/aapt2/optimize/MultiApkGenerator.cpp
@@ -101,6 +101,10 @@ class ContextWrapper : public IAaptContext {
         util::make_unique<SourcePathDiagnostics>(Source{source}, context_->GetDiagnostics());
   }
 
+  const std::set<std::string>& GetSplitNameDependencies() override {
+    return context_->GetSplitNameDependencies();
+  }
+
  private:
   IAaptContext* context_;
   std::unique_ptr<SourcePathDiagnostics> source_diag_;
diff --git a/tools/aapt2/optimize/ResourceDeduper.cpp b/tools/aapt2/optimize/ResourceDeduper.cpp
index 78ebcb97b811..0278b439cfae 100644
--- a/tools/aapt2/optimize/ResourceDeduper.cpp
+++ b/tools/aapt2/optimize/ResourceDeduper.cpp
@@ -63,13 +63,14 @@ class DominatedKeyValueRemover : public DominatorTree::BottomUpVisitor {
     // Compare compatible configs for this entry and ensure the values are
     // equivalent.
     const ConfigDescription& node_configuration = node_value->config;
-    for (const auto& sibling : entry_->values) {
-      if (!sibling->value) {
+    for (const auto& sibling : parent->children()) {
+      ResourceConfigValue* sibling_value = sibling->value();
+      if (!sibling_value->value) {
         // Sibling was already removed.
         continue;
       }
-      if (node_configuration.IsCompatibleWith(sibling->config) &&
-          !node_value->value->Equals(sibling->value.get())) {
+      if (node_configuration.IsCompatibleWith(sibling_value->config) &&
+          !node_value->value->Equals(sibling_value->value.get())) {
         // The configurations are compatible, but the value is
         // different, so we can't remove this value.
         return;
diff --git a/tools/aapt2/optimize/ResourceDeduper_test.cpp b/tools/aapt2/optimize/ResourceDeduper_test.cpp
index 2e098aec4f8d..048e318d2802 100644
--- a/tools/aapt2/optimize/ResourceDeduper_test.cpp
+++ b/tools/aapt2/optimize/ResourceDeduper_test.cpp
@@ -80,11 +80,58 @@ TEST(ResourceDeduperTest, DifferentValuesAreKept) {
           .Build();
 
   ASSERT_TRUE(ResourceDeduper().Consume(context.get(), table.get()));
+  EXPECT_THAT(table, HasValue("android:string/keep", default_config));
   EXPECT_THAT(table, HasValue("android:string/keep", ldrtl_config));
   EXPECT_THAT(table, HasValue("android:string/keep", ldrtl_v21_config));
   EXPECT_THAT(table, HasValue("android:string/keep", land_config));
 }
 
+TEST(ResourceDeduperTest, SameValuesAreDedupedIncompatibleSiblings) {
+  std::unique_ptr<IAaptContext> context = test::ContextBuilder().Build();
+  const ConfigDescription default_config = {};
+  const ConfigDescription ldrtl_config = test::ParseConfigOrDie("ldrtl");
+  const ConfigDescription ldrtl_night_config = test::ParseConfigOrDie("ldrtl-night");
+  // Chosen because this configuration is not compatible with ldrtl-night.
+  const ConfigDescription ldrtl_notnight_config = test::ParseConfigOrDie("ldrtl-notnight");
+
+  std::unique_ptr<ResourceTable> table =
+      test::ResourceTableBuilder()
+          .AddString("android:string/keep", ResourceId{}, default_config, "keep")
+          .AddString("android:string/keep", ResourceId{}, ldrtl_config, "dedupe")
+          .AddString("android:string/keep", ResourceId{}, ldrtl_night_config, "dedupe")
+          .AddString("android:string/keep", ResourceId{}, ldrtl_notnight_config, "keep2")
+          .Build();
+
+  ASSERT_TRUE(ResourceDeduper().Consume(context.get(), table.get()));
+  EXPECT_THAT(table, HasValue("android:string/keep", default_config));
+  EXPECT_THAT(table, HasValue("android:string/keep", ldrtl_config));
+  EXPECT_THAT(table, Not(HasValue("android:string/keep", ldrtl_night_config)));
+  EXPECT_THAT(table, HasValue("android:string/keep", ldrtl_notnight_config));
+}
+
+TEST(ResourceDeduperTest, SameValuesAreDedupedCompatibleNonSiblings) {
+  std::unique_ptr<IAaptContext> context = test::ContextBuilder().Build();
+  const ConfigDescription default_config = {};
+  const ConfigDescription ldrtl_config = test::ParseConfigOrDie("ldrtl");
+  const ConfigDescription ldrtl_night_config = test::ParseConfigOrDie("ldrtl-night");
+  // Chosen because this configuration is compatible with ldrtl.
+  const ConfigDescription land_config = test::ParseConfigOrDie("land");
+
+  std::unique_ptr<ResourceTable> table =
+      test::ResourceTableBuilder()
+          .AddString("android:string/keep", ResourceId{}, default_config, "keep")
+          .AddString("android:string/keep", ResourceId{}, ldrtl_config, "dedupe")
+          .AddString("android:string/keep", ResourceId{}, ldrtl_night_config, "dedupe")
+          .AddString("android:string/keep", ResourceId{}, land_config, "keep2")
+          .Build();
+
+  ASSERT_TRUE(ResourceDeduper().Consume(context.get(), table.get()));
+  EXPECT_THAT(table, HasValue("android:string/keep", default_config));
+  EXPECT_THAT(table, HasValue("android:string/keep", ldrtl_config));
+  EXPECT_THAT(table, Not(HasValue("android:string/keep", ldrtl_night_config)));
+  EXPECT_THAT(table, HasValue("android:string/keep", land_config));
+}
+
 TEST(ResourceDeduperTest, LocalesValuesAreKept) {
   std::unique_ptr<IAaptContext> context = test::ContextBuilder().Build();
   const ConfigDescription default_config = {};
diff --git a/tools/aapt2/optimize/ResourcePathShortener.cpp b/tools/aapt2/optimize/ResourcePathShortener.cpp
index c5df3dd00db9..7ff9bf5aa8df 100644
--- a/tools/aapt2/optimize/ResourcePathShortener.cpp
+++ b/tools/aapt2/optimize/ResourcePathShortener.cpp
@@ -16,13 +16,14 @@
 
 #include "optimize/ResourcePathShortener.h"
 
-#include <math.h>
+#include <set>
 #include <unordered_set>
 
 #include "androidfw/StringPiece.h"
 
 #include "ResourceTable.h"
 #include "ValueVisitor.h"
+#include "util/Util.h"
 
 
 static const std::string base64_chars =
@@ -50,18 +51,15 @@ std::string ShortenFileName(const android::StringPiece& file_path, int output_le
 }
 
 
-// Calculate the optimal hash length such that an average of 10% of resources
-// collide in their shortened path.
+// Return the optimal hash length such that at most 10% of resources collide in
+// their shortened path.
 // Reference: http://matt.might.net/articles/counting-hash-collisions/
 int OptimalShortenedLength(int num_resources) {
-  int num_chars = 2;
-  double N = 64*64; // hash space when hash is 2 chars long
-  double max_collisions = num_resources * 0.1;
-  while (num_resources - N + N * pow((N - 1) / N, num_resources) > max_collisions) {
-    N *= 64;
-    num_chars++;
+  if (num_resources > 4000) {
+    return 3;
+  } else {
+    return 2;
   }
-  return num_chars;
 }
 
 std::string GetShortenedPath(const android::StringPiece& shortened_filename,
@@ -74,10 +72,19 @@ std::string GetShortenedPath(const android::StringPiece& shortened_filename,
   return shortened_path;
 }
 
+// implement custom comparator of FileReference pointers so as to use the
+// underlying filepath as key rather than the integer address. This is to ensure
+// determinism of output for colliding files.
+struct PathComparator {
+    bool operator() (const FileReference* lhs, const FileReference* rhs) const {
+        return lhs->path->compare(*rhs->path);
+    }
+};
+
 bool ResourcePathShortener::Consume(IAaptContext* context, ResourceTable* table) {
   // used to detect collisions
   std::unordered_set<std::string> shortened_paths;
-  std::unordered_set<FileReference*> file_refs;
+  std::set<FileReference*, PathComparator> file_refs;
   for (auto& package : table->packages) {
     for (auto& type : package->types) {
       for (auto& entry : type->entries) {
@@ -95,6 +102,10 @@ bool ResourcePathShortener::Consume(IAaptContext* context, ResourceTable* table)
     android::StringPiece res_subdir, actual_filename, extension;
     util::ExtractResFilePathParts(*file_ref->path, &res_subdir, &actual_filename, &extension);
 
+    // Android detects ColorStateLists via pathname, skip res/color*
+    if (util::StartsWith(res_subdir, "res/color"))
+      continue;
+
     std::string shortened_filename = ShortenFileName(*file_ref->path, num_chars);
     int collision_count = 0;
     std::string shortened_path = GetShortenedPath(shortened_filename, extension, collision_count);
diff --git a/tools/aapt2/optimize/ResourcePathShortener_test.cpp b/tools/aapt2/optimize/ResourcePathShortener_test.cpp
index 88cadc76c336..f5a02be0ea5e 100644
--- a/tools/aapt2/optimize/ResourcePathShortener_test.cpp
+++ b/tools/aapt2/optimize/ResourcePathShortener_test.cpp
@@ -24,6 +24,19 @@ using ::testing::Not;
 using ::testing::NotNull;
 using ::testing::Eq;
 
+android::StringPiece GetExtension(android::StringPiece path) {
+  auto iter = std::find(path.begin(), path.end(), '.');
+  return android::StringPiece(iter, path.end() - iter);
+}
+
+void FillTable(aapt::test::ResourceTableBuilder& builder, int start, int end) {
+  for (int i=start; i<end; i++) {
+    builder.AddFileReference(
+        "android:drawable/xmlfile" + std::to_string(i),
+        "res/drawable/xmlfile" + std::to_string(i) + ".xml");
+  }
+}
+
 namespace aapt {
 
 TEST(ResourcePathShortenerTest, FileRefPathsChangedInResourceTable) {
@@ -64,4 +77,90 @@ TEST(ResourcePathShortenerTest, FileRefPathsChangedInResourceTable) {
   EXPECT_THAT(path_map.find("res/should/still/be/the/same.png"), Eq(path_map.end()));
 }
 
+TEST(ResourcePathShortenerTest, SkipColorFileRefPaths) {
+  std::unique_ptr<IAaptContext> context = test::ContextBuilder().Build();
+
+  std::unique_ptr<ResourceTable> table =
+      test::ResourceTableBuilder()
+          .AddFileReference("android:color/colorlist", "res/color/colorlist.xml")
+          .AddFileReference("android:color/colorlist",
+                            "res/color-mdp-v21/colorlist.xml",
+                            test::ParseConfigOrDie("mdp-v21"))
+          .Build();
+
+  std::map<std::string, std::string> path_map;
+  ASSERT_TRUE(ResourcePathShortener(path_map).Consume(context.get(), table.get()));
+
+  // Expect that the path map to not contain the ColorStateList
+  ASSERT_THAT(path_map.find("res/color/colorlist.xml"), Eq(path_map.end()));
+  ASSERT_THAT(path_map.find("res/color-mdp-v21/colorlist.xml"), Eq(path_map.end()));
+}
+
+TEST(ResourcePathShortenerTest, KeepExtensions) {
+  std::unique_ptr<IAaptContext> context = test::ContextBuilder().Build();
+
+  std::string original_xml_path = "res/drawable/xmlfile.xml";
+  std::string original_png_path = "res/drawable/pngfile.png";
+
+  std::unique_ptr<ResourceTable> table =
+      test::ResourceTableBuilder()
+          .AddFileReference("android:color/xmlfile", original_xml_path)
+          .AddFileReference("android:color/pngfile", original_png_path)
+          .Build();
+
+  std::map<std::string, std::string> path_map;
+  ASSERT_TRUE(ResourcePathShortener(path_map).Consume(context.get(), table.get()));
+
+  // Expect that the path map is populated
+  ASSERT_THAT(path_map.find("res/drawable/xmlfile.xml"), Not(Eq(path_map.end())));
+  ASSERT_THAT(path_map.find("res/drawable/pngfile.png"), Not(Eq(path_map.end())));
+
+  auto shortend_xml_path = path_map[original_xml_path];
+  auto shortend_png_path = path_map[original_png_path];
+
+  EXPECT_THAT(GetExtension(path_map[original_xml_path]), Eq(android::StringPiece(".xml")));
+  EXPECT_THAT(GetExtension(path_map[original_png_path]), Eq(android::StringPiece(".png")));
+}
+
+TEST(ResourcePathShortenerTest, DeterministicallyHandleCollisions) {
+  std::unique_ptr<IAaptContext> context = test::ContextBuilder().Build();
+
+  // 4000 resources is the limit at which the hash space is expanded to 3
+  // letters to reduce collisions, we want as many collisions as possible thus
+  // N-1.
+  const auto kNumResources = 3999;
+  const auto kNumTries = 5;
+
+  test::ResourceTableBuilder builder1;
+  FillTable(builder1, 0, kNumResources);
+  std::unique_ptr<ResourceTable> table1 = builder1.Build();
+  std::map<std::string, std::string> expected_mapping;
+  ASSERT_TRUE(ResourcePathShortener(expected_mapping).Consume(context.get(), table1.get()));
+
+  // We are trying to ensure lack of non-determinism, it is not simple to prove
+  // a negative, thus we must try the test a few times so that the test itself
+  // is non-flaky. Basically create the pathmap 5 times from the same set of
+  // resources but a different order of addition and then ensure they are always
+  // mapped to the same short path.
+  for (int i=0; i<kNumTries; i++) {
+    test::ResourceTableBuilder builder2;
+    // This loop adds resources to the resource table in the range of
+    // [0:kNumResources).  Adding the file references in different order makes
+    // non-determinism more likely to surface. Thus we add resources
+    // [start_index:kNumResources) first then [0:start_index). We also use a
+    // different start_index each run.
+    int start_index = (kNumResources/kNumTries)*i;
+    FillTable(builder2, start_index, kNumResources);
+    FillTable(builder2, 0, start_index);
+    std::unique_ptr<ResourceTable> table2 = builder2.Build();
+
+    std::map<std::string, std::string> actual_mapping;
+    ASSERT_TRUE(ResourcePathShortener(actual_mapping).Consume(context.get(), table2.get()));
+
+    for (auto& item : actual_mapping) {
+      ASSERT_THAT(expected_mapping[item.first], Eq(item.second));
+    }
+  }
+}
+
 }   // namespace aapt