AAPT2: Rename strip phase to optimize

- Allow resource deduping, version collapsing, and sparse resource
  encoding.

Test: manual
Change-Id: Ia4aa892ab5b06ba1d5ea4a6efb51b00bc3a980c4
diff --git a/tools/aapt2/optimize/Optimize.cpp b/tools/aapt2/optimize/Optimize.cpp
new file mode 100644
index 0000000..9615962
--- /dev/null
+++ b/tools/aapt2/optimize/Optimize.cpp
@@ -0,0 +1,201 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+#include <memory>
+#include <vector>
+
+#include "androidfw/StringPiece.h"
+
+#include "Diagnostics.h"
+#include "Flags.h"
+#include "LoadedApk.h"
+#include "SdkConstants.h"
+#include "flatten/TableFlattener.h"
+#include "optimize/ResourceDeduper.h"
+#include "optimize/VersionCollapser.h"
+#include "split/TableSplitter.h"
+
+using android::StringPiece;
+
+namespace aapt {
+
+struct OptimizeOptions {
+  // Path to the output APK.
+  std::string output_path;
+
+  // List of screen density configurations the APK will be optimized for.
+  std::vector<ConfigDescription> target_configs;
+
+  TableFlattenerOptions table_flattener_options;
+};
+
+class OptimizeContext : public IAaptContext {
+ public:
+  IDiagnostics* GetDiagnostics() override { return &diagnostics_; }
+
+  NameMangler* GetNameMangler() override {
+    abort();
+    return nullptr;
+  }
+
+  const std::string& GetCompilationPackage() override {
+    static std::string empty;
+    return empty;
+  }
+
+  uint8_t GetPackageId() override { return 0; }
+
+  SymbolTable* GetExternalSymbols() override {
+    abort();
+    return nullptr;
+  }
+
+  bool IsVerbose() override { return verbose_; }
+
+  void SetVerbose(bool val) { verbose_ = val; }
+
+  void SetMinSdkVersion(int sdk_version) { sdk_version_ = sdk_version; }
+
+  int GetMinSdkVersion() override { return sdk_version_; }
+
+ private:
+  StdErrDiagnostics diagnostics_;
+  bool verbose_ = false;
+  int sdk_version_ = 0;
+};
+
+class OptimizeCommand {
+ public:
+  OptimizeCommand(OptimizeContext* context, const OptimizeOptions& options)
+      : options_(options),
+        context_(context) {}
+
+  int Run(std::unique_ptr<LoadedApk> apk) {
+    if (context_->IsVerbose()) {
+      context_->GetDiagnostics()->Note(DiagMessage() << "Optimizing APK...");
+    }
+
+    VersionCollapser collapser;
+    if (!collapser.Consume(context_, apk->GetResourceTable())) {
+      return 1;
+    }
+
+    ResourceDeduper deduper;
+    if (!deduper.Consume(context_, apk->GetResourceTable())) {
+      context_->GetDiagnostics()->Error(DiagMessage() << "failed deduping resources");
+      return 1;
+    }
+
+    // Stripping the APK using the TableSplitter with no splits and the target
+    // densities as the preferred densities. The resource table is modified in
+    // place in the LoadedApk.
+    TableSplitterOptions splitter_options;
+    for (auto& config : options_.target_configs) {
+      splitter_options.preferred_densities.push_back(config.density);
+    }
+    std::vector<SplitConstraints> splits;
+    TableSplitter splitter(splits, splitter_options);
+    splitter.SplitTable(apk->GetResourceTable());
+
+    std::unique_ptr<IArchiveWriter> writer =
+        CreateZipFileArchiveWriter(context_->GetDiagnostics(), options_.output_path);
+    if (!apk->WriteToArchive(context_, options_.table_flattener_options, writer.get())) {
+      return 1;
+    }
+
+    return 0;
+  }
+
+ private:
+  OptimizeOptions options_;
+  OptimizeContext* context_;
+};
+
+int Optimize(const std::vector<StringPiece>& args) {
+  OptimizeContext context;
+  OptimizeOptions options;
+  Maybe<std::string> target_densities;
+  bool verbose = false;
+  Flags flags =
+      Flags()
+          .RequiredFlag("-o", "Path to the output APK.", &options.output_path)
+          .OptionalFlag(
+              "--target-densities",
+              "Comma separated list of the screen densities that the APK will "
+              "be optimized for. All the resources that would be unused on "
+              "devices of the given densities will be removed from the APK.",
+              &target_densities)
+          .OptionalSwitch("--enable-sparse-encoding",
+                          "Enables encoding sparse entries using a binary search tree.\n"
+                          "This decreases APK size at the cost of resource retrieval performance.",
+                          &options.table_flattener_options.use_sparse_entries)
+          .OptionalSwitch("-v", "Enables verbose logging", &verbose);
+
+  if (!flags.Parse("aapt2 optimize", args, &std::cerr)) {
+    return 1;
+  }
+
+  if (flags.GetArgs().size() != 1u) {
+    std::cerr << "must have one APK as argument.\n\n";
+    flags.Usage("aapt2 optimize", &std::cerr);
+    return 1;
+  }
+
+  std::unique_ptr<LoadedApk> apk =
+      LoadedApk::LoadApkFromPath(&context, flags.GetArgs()[0]);
+  if (!apk) {
+    return 1;
+  }
+
+  if (verbose) {
+    context.SetVerbose(verbose);
+  }
+
+  if (target_densities) {
+    // Parse the target screen densities.
+    for (const StringPiece& config_str : util::Tokenize(target_densities.value(), ',')) {
+      ConfigDescription config;
+      if (!ConfigDescription::Parse(config_str, &config) || config.density == 0) {
+        context.GetDiagnostics()->Error(
+            DiagMessage() << "invalid density '" << config_str
+                          << "' for --target-densities option");
+        return 1;
+      }
+
+      // Clear the version that can be automatically added.
+      config.sdkVersion = 0;
+
+      if (config.diff(ConfigDescription::DefaultConfig()) !=
+          ConfigDescription::CONFIG_DENSITY) {
+        context.GetDiagnostics()->Error(
+            DiagMessage() << "invalid density '" << config_str
+                          << "' for --target-densities option. Must be only a "
+                          << "density value.");
+        return 1;
+      }
+
+      options.target_configs.push_back(config);
+    }
+  }
+
+  // TODO(adamlesinski): Read manfiest and set the proper minSdkVersion.
+  // context.SetMinSdkVersion(SDK_O);
+
+  OptimizeCommand cmd(&context, options);
+  return cmd.Run(std::move(apk));
+}
+
+}  // namespace aapt
diff --git a/tools/aapt2/optimize/ResourceDeduper.cpp b/tools/aapt2/optimize/ResourceDeduper.cpp
new file mode 100644
index 0000000..3aab2e3
--- /dev/null
+++ b/tools/aapt2/optimize/ResourceDeduper.cpp
@@ -0,0 +1,119 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+#include "optimize/ResourceDeduper.h"
+
+#include <algorithm>
+
+#include "DominatorTree.h"
+#include "ResourceTable.h"
+
+namespace aapt {
+
+namespace {
+
+/**
+ * Remove duplicated key-value entries from dominated resources.
+ *
+ * Based on the dominator tree, we can remove a value of an entry if:
+ *
+ * 1. The configuration for the entry's value is dominated by a configuration
+ *    with an equivalent entry value.
+ * 2. All compatible configurations for the entry (those not in conflict and
+ *    unrelated by domination with the configuration for the entry's value) have
+ *    an equivalent entry value.
+ */
+class DominatedKeyValueRemover : public DominatorTree::BottomUpVisitor {
+ public:
+  using Node = DominatorTree::Node;
+
+  explicit DominatedKeyValueRemover(IAaptContext* context, ResourceEntry* entry)
+      : context_(context), entry_(entry) {}
+
+  void VisitConfig(Node* node) {
+    Node* parent = node->parent();
+    if (!parent) {
+      return;
+    }
+    ResourceConfigValue* node_value = node->value();
+    ResourceConfigValue* parent_value = parent->value();
+    if (!node_value || !parent_value) {
+      return;
+    }
+    if (!node_value->value->Equals(parent_value->value.get())) {
+      return;
+    }
+
+    // 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) {
+        // Sibling was already removed.
+        continue;
+      }
+      if (node_configuration.IsCompatibleWith(sibling->config) &&
+          !node_value->value->Equals(sibling->value.get())) {
+        // The configurations are compatible, but the value is
+        // different, so we can't remove this value.
+        return;
+      }
+    }
+    if (context_->IsVerbose()) {
+      context_->GetDiagnostics()->Note(
+          DiagMessage(node_value->value->GetSource())
+          << "removing dominated duplicate resource with name \""
+          << entry_->name << "\"");
+    }
+    node_value->value = {};
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(DominatedKeyValueRemover);
+
+  IAaptContext* context_;
+  ResourceEntry* entry_;
+};
+
+static void DedupeEntry(IAaptContext* context, ResourceEntry* entry) {
+  DominatorTree tree(entry->values);
+  DominatedKeyValueRemover remover(context, entry);
+  tree.Accept(&remover);
+
+  // Erase the values that were removed.
+  entry->values.erase(
+      std::remove_if(
+          entry->values.begin(), entry->values.end(),
+          [](const std::unique_ptr<ResourceConfigValue>& val) -> bool {
+            return val == nullptr || val->value == nullptr;
+          }),
+      entry->values.end());
+}
+
+}  // namespace
+
+bool ResourceDeduper::Consume(IAaptContext* context, ResourceTable* table) {
+  for (auto& package : table->packages) {
+    for (auto& type : package->types) {
+      for (auto& entry : type->entries) {
+        DedupeEntry(context, entry.get());
+      }
+    }
+  }
+  return true;
+}
+
+}  // namespace aapt
diff --git a/tools/aapt2/optimize/ResourceDeduper.h b/tools/aapt2/optimize/ResourceDeduper.h
new file mode 100644
index 0000000..4a669d4
--- /dev/null
+++ b/tools/aapt2/optimize/ResourceDeduper.h
@@ -0,0 +1,41 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+#ifndef AAPT_OPTIMIZE_RESOURCEDEDUPER_H
+#define AAPT_OPTIMIZE_RESOURCEDEDUPER_H
+
+#include "android-base/macros.h"
+
+#include "process/IResourceTableConsumer.h"
+
+namespace aapt {
+
+class ResourceTable;
+
+// Removes duplicated key-value entries from dominated resources.
+class ResourceDeduper : public IResourceTableConsumer {
+ public:
+  ResourceDeduper() = default;
+
+  bool Consume(IAaptContext* context, ResourceTable* table) override;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(ResourceDeduper);
+};
+
+} // namespace aapt
+
+#endif  // AAPT_OPTIMIZE_RESOURCEDEDUPER_H
diff --git a/tools/aapt2/optimize/ResourceDeduper_test.cpp b/tools/aapt2/optimize/ResourceDeduper_test.cpp
new file mode 100644
index 0000000..4d00fa6
--- /dev/null
+++ b/tools/aapt2/optimize/ResourceDeduper_test.cpp
@@ -0,0 +1,87 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+#include "optimize/ResourceDeduper.h"
+
+#include "ResourceTable.h"
+#include "test/Test.h"
+
+namespace aapt {
+
+TEST(ResourceDeduperTest, SameValuesAreDeduped) {
+  std::unique_ptr<IAaptContext> context = test::ContextBuilder().Build();
+  const ConfigDescription default_config = {};
+  const ConfigDescription en_config = test::ParseConfigOrDie("en");
+  const ConfigDescription en_v21_config = test::ParseConfigOrDie("en-v21");
+  // Chosen because this configuration is compatible with en.
+  const ConfigDescription land_config = test::ParseConfigOrDie("land");
+
+  std::unique_ptr<ResourceTable> table =
+      test::ResourceTableBuilder()
+          .AddString("android:string/dedupe", ResourceId{}, default_config,
+                     "dedupe")
+          .AddString("android:string/dedupe", ResourceId{}, en_config, "dedupe")
+          .AddString("android:string/dedupe", ResourceId{}, land_config,
+                     "dedupe")
+          .AddString("android:string/dedupe2", ResourceId{}, default_config,
+                     "dedupe")
+          .AddString("android:string/dedupe2", ResourceId{}, en_config,
+                     "dedupe")
+          .AddString("android:string/dedupe2", ResourceId{}, en_v21_config,
+                     "keep")
+          .AddString("android:string/dedupe2", ResourceId{}, land_config,
+                     "dedupe")
+          .Build();
+
+  ASSERT_TRUE(ResourceDeduper().Consume(context.get(), table.get()));
+  EXPECT_EQ(nullptr, test::GetValueForConfig<String>(
+                         table.get(), "android:string/dedupe", en_config));
+  EXPECT_EQ(nullptr, test::GetValueForConfig<String>(
+                         table.get(), "android:string/dedupe", land_config));
+  EXPECT_EQ(nullptr, test::GetValueForConfig<String>(
+                         table.get(), "android:string/dedupe2", en_config));
+  EXPECT_NE(nullptr, test::GetValueForConfig<String>(
+                         table.get(), "android:string/dedupe2", en_v21_config));
+}
+
+TEST(ResourceDeduperTest, DifferentValuesAreKept) {
+  std::unique_ptr<IAaptContext> context = test::ContextBuilder().Build();
+  const ConfigDescription default_config = {};
+  const ConfigDescription en_config = test::ParseConfigOrDie("en");
+  const ConfigDescription en_v21_config = test::ParseConfigOrDie("en-v21");
+  // Chosen because this configuration is compatible with en.
+  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{}, en_config, "keep")
+          .AddString("android:string/keep", ResourceId{}, en_v21_config,
+                     "keep2")
+          .AddString("android:string/keep", ResourceId{}, land_config, "keep2")
+          .Build();
+
+  ASSERT_TRUE(ResourceDeduper().Consume(context.get(), table.get()));
+  EXPECT_NE(nullptr, test::GetValueForConfig<String>(
+                         table.get(), "android:string/keep", en_config));
+  EXPECT_NE(nullptr, test::GetValueForConfig<String>(
+                         table.get(), "android:string/keep", en_v21_config));
+  EXPECT_NE(nullptr, test::GetValueForConfig<String>(
+                         table.get(), "android:string/keep", land_config));
+}
+
+}  // namespace aapt
diff --git a/tools/aapt2/optimize/VersionCollapser.cpp b/tools/aapt2/optimize/VersionCollapser.cpp
new file mode 100644
index 0000000..d941b48
--- /dev/null
+++ b/tools/aapt2/optimize/VersionCollapser.cpp
@@ -0,0 +1,162 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+#include "optimize/VersionCollapser.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "ResourceTable.h"
+
+namespace aapt {
+
+template <typename Iterator, typename Pred>
+class FilterIterator {
+ public:
+  FilterIterator(Iterator begin, Iterator end, Pred pred = Pred())
+      : current_(begin), end_(end), pred_(pred) {
+    Advance();
+  }
+
+  bool HasNext() { return current_ != end_; }
+
+  Iterator NextIter() {
+    Iterator iter = current_;
+    ++current_;
+    Advance();
+    return iter;
+  }
+
+  typename Iterator::reference Next() { return *NextIter(); }
+
+ private:
+  void Advance() {
+    for (; current_ != end_; ++current_) {
+      if (pred_(*current_)) {
+        return;
+      }
+    }
+  }
+
+  Iterator current_, end_;
+  Pred pred_;
+};
+
+template <typename Iterator, typename Pred>
+FilterIterator<Iterator, Pred> make_filter_iterator(Iterator begin,
+                                                    Iterator end = Iterator(),
+                                                    Pred pred = Pred()) {
+  return FilterIterator<Iterator, Pred>(begin, end, pred);
+}
+
+/**
+ * Every Configuration with an SDK version specified that is less than minSdk
+ * will be removed.
+ * The exception is when there is no exact matching resource for the minSdk. The
+ * next smallest
+ * one will be kept.
+ */
+static void CollapseVersions(int min_sdk, ResourceEntry* entry) {
+  // First look for all sdks less than minSdk.
+  for (auto iter = entry->values.rbegin(); iter != entry->values.rend();
+       ++iter) {
+    // Check if the item was already marked for removal.
+    if (!(*iter)) {
+      continue;
+    }
+
+    const ConfigDescription& config = (*iter)->config;
+    if (config.sdkVersion <= min_sdk) {
+      // This is the first configuration we've found with a smaller or equal SDK
+      // level
+      // to the minimum. We MUST keep this one, but remove all others we find,
+      // which get
+      // overridden by this one.
+
+      ConfigDescription config_without_sdk = config.CopyWithoutSdkVersion();
+      auto pred = [&](const std::unique_ptr<ResourceConfigValue>& val) -> bool {
+        // Check that the value hasn't already been marked for removal.
+        if (!val) {
+          return false;
+        }
+
+        // Only return Configs that differ in SDK version.
+        config_without_sdk.sdkVersion = val->config.sdkVersion;
+        return config_without_sdk == val->config &&
+               val->config.sdkVersion <= min_sdk;
+      };
+
+      // Remove the rest that match.
+      auto filter_iter =
+          make_filter_iterator(iter + 1, entry->values.rend(), pred);
+      while (filter_iter.HasNext()) {
+        filter_iter.Next() = {};
+      }
+    }
+  }
+
+  // Now erase the nullptr values.
+  entry->values.erase(
+      std::remove_if(entry->values.begin(), entry->values.end(),
+                     [](const std::unique_ptr<ResourceConfigValue>& val)
+                         -> bool { return val == nullptr; }),
+      entry->values.end());
+
+  // Strip the version qualifiers for every resource with version <= minSdk.
+  // This will ensure
+  // that the resource entries are all packed together in the same ResTable_type
+  // struct
+  // and take up less space in the resources.arsc table.
+  bool modified = false;
+  for (std::unique_ptr<ResourceConfigValue>& config_value : entry->values) {
+    if (config_value->config.sdkVersion != 0 &&
+        config_value->config.sdkVersion <= min_sdk) {
+      // Override the resource with a Configuration without an SDK.
+      std::unique_ptr<ResourceConfigValue> new_value =
+          util::make_unique<ResourceConfigValue>(
+              config_value->config.CopyWithoutSdkVersion(),
+              config_value->product);
+      new_value->value = std::move(config_value->value);
+      config_value = std::move(new_value);
+
+      modified = true;
+    }
+  }
+
+  if (modified) {
+    // We've modified the keys (ConfigDescription) by changing the sdkVersion to
+    // 0. We MUST re-sort to ensure ordering guarantees hold.
+    std::sort(entry->values.begin(), entry->values.end(),
+              [](const std::unique_ptr<ResourceConfigValue>& a,
+                 const std::unique_ptr<ResourceConfigValue>& b) -> bool {
+                return a->config.compare(b->config) < 0;
+              });
+  }
+}
+
+bool VersionCollapser::Consume(IAaptContext* context, ResourceTable* table) {
+  const int min_sdk = context->GetMinSdkVersion();
+  for (auto& package : table->packages) {
+    for (auto& type : package->types) {
+      for (auto& entry : type->entries) {
+        CollapseVersions(min_sdk, entry.get());
+      }
+    }
+  }
+  return true;
+}
+
+}  // namespace aapt
diff --git a/tools/aapt2/optimize/VersionCollapser.h b/tools/aapt2/optimize/VersionCollapser.h
new file mode 100644
index 0000000..5ab3b25
--- /dev/null
+++ b/tools/aapt2/optimize/VersionCollapser.h
@@ -0,0 +1,40 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+#ifndef AAPT_OPTIMIZE_VERSIONCOLLAPSER_H
+#define AAPT_OPTIMIZE_VERSIONCOLLAPSER_H
+
+#include "android-base/macros.h"
+
+#include "process/IResourceTableConsumer.h"
+
+namespace aapt {
+
+class ResourceTable;
+
+class VersionCollapser : public IResourceTableConsumer {
+ public:
+  VersionCollapser() = default;
+
+  bool Consume(IAaptContext* context, ResourceTable* table) override;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(VersionCollapser);
+};
+
+} // namespace aapt
+
+#endif  // AAPT_OPTIMIZE_VERSIONCOLLAPSER_H
diff --git a/tools/aapt2/optimize/VersionCollapser_test.cpp b/tools/aapt2/optimize/VersionCollapser_test.cpp
new file mode 100644
index 0000000..aa0d0c0
--- /dev/null
+++ b/tools/aapt2/optimize/VersionCollapser_test.cpp
@@ -0,0 +1,119 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+#include "optimize/VersionCollapser.h"
+
+#include "test/Test.h"
+
+using android::StringPiece;
+
+namespace aapt {
+
+static std::unique_ptr<ResourceTable> BuildTableWithConfigs(
+    const StringPiece& name, std::initializer_list<std::string> list) {
+  test::ResourceTableBuilder builder;
+  for (const std::string& item : list) {
+    builder.AddSimple(name, test::ParseConfigOrDie(item));
+  }
+  return builder.Build();
+}
+
+TEST(VersionCollapserTest, CollapseVersions) {
+  std::unique_ptr<IAaptContext> context =
+      test::ContextBuilder().SetMinSdkVersion(7).Build();
+
+  const StringPiece res_name = "@android:string/foo";
+
+  std::unique_ptr<ResourceTable> table = BuildTableWithConfigs(
+      res_name,
+      {"land-v4", "land-v5", "sw600dp", "land-v6", "land-v14", "land-v21"});
+
+  VersionCollapser collapser;
+  ASSERT_TRUE(collapser.Consume(context.get(), table.get()));
+
+  // These should be removed.
+  EXPECT_EQ(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land-v4")));
+  EXPECT_EQ(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land-v5")));
+  // This one should be removed because it was renamed to 'land', with the
+  // version dropped.
+  EXPECT_EQ(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land-v6")));
+
+  // These should remain.
+  EXPECT_NE(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("sw600dp")));
+
+  // 'land' should be present because it was renamed from 'land-v6'.
+  EXPECT_NE(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land")));
+  EXPECT_NE(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land-v14")));
+  EXPECT_NE(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land-v21")));
+}
+
+TEST(VersionCollapserTest, CollapseVersionsWhenMinSdkIsHighest) {
+  std::unique_ptr<IAaptContext> context =
+      test::ContextBuilder().SetMinSdkVersion(21).Build();
+
+  const StringPiece res_name = "@android:string/foo";
+
+  std::unique_ptr<ResourceTable> table = BuildTableWithConfigs(
+      res_name, {"land-v4", "land-v5", "sw600dp", "land-v6", "land-v14",
+                 "land-v21", "land-v22"});
+  VersionCollapser collapser;
+  ASSERT_TRUE(collapser.Consume(context.get(), table.get()));
+
+  // These should all be removed.
+  EXPECT_EQ(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land-v4")));
+  EXPECT_EQ(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land-v5")));
+  EXPECT_EQ(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land-v6")));
+  EXPECT_EQ(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land-v14")));
+
+  // These should remain.
+  EXPECT_NE(nullptr,
+            test::GetValueForConfig<Id>(
+                table.get(), res_name,
+                test::ParseConfigOrDie("sw600dp").CopyWithoutSdkVersion()));
+
+  // land-v21 should have been converted to land.
+  EXPECT_NE(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land")));
+  // land-v22 should remain as-is.
+  EXPECT_NE(nullptr,
+            test::GetValueForConfig<Id>(table.get(), res_name,
+                                        test::ParseConfigOrDie("land-v22")));
+}
+
+}  // namespace aapt