AAPT2: Add dominator tree analysis and resource removal

Added dominator tree analysis of resource configurations for each
resource entry to allow deduping of resource entries if:

1. The configuration for the resource 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.

Bug: 30051199
Test: make libaapt2_tests && libaapt2_tests
Change-Id: I66468d3014a2d6097a94b039ac1028f9f461c7d3

11 files changed, 726 insertions, 2 deletions

diff --git a/tools/aapt2/Android.mk b/tools/aapt2/Android.mk
index 60114fb6ff99..18a1fbf725b4 100644
--- a/tools/aapt2/Android.mk
+++ b/tools/aapt2/Android.mk
@@ -40,6 +40,7 @@ sources := \
 	link/ProductFilter.cpp \
 	link/PrivateAttributeMover.cpp \
 	link/ReferenceLinker.cpp \
+	link/ResourceDeduper.cpp \
 	link/TableMerger.cpp \
 	link/VersionCollapser.cpp \
 	link/XmlNamespaceRemover.cpp \
@@ -56,6 +57,7 @@ sources := \
 	util/Util.cpp \
 	ConfigDescription.cpp \
 	Debug.cpp \
+	DominatorTree.cpp \
 	Flags.cpp \
 	java/AnnotationProcessor.cpp \
 	java/ClassDefinition.cpp \
@@ -93,6 +95,7 @@ testSources := \
 	link/PrivateAttributeMover_test.cpp \
 	link/ProductFilter_test.cpp \
 	link/ReferenceLinker_test.cpp \
+	link/ResourceDeduper_test.cpp \
 	link/TableMerger_test.cpp \
 	link/VersionCollapser_test.cpp \
 	link/XmlNamespaceRemover_test.cpp \
@@ -106,6 +109,7 @@ testSources := \
 	util/StringPiece_test.cpp \
 	util/Util_test.cpp \
 	ConfigDescription_test.cpp \
+	DominatorTree_test.cpp \
 	java/AnnotationProcessor_test.cpp \
 	java/JavaClassGenerator_test.cpp \
 	java/ManifestClassGenerator_test.cpp \
diff --git a/tools/aapt2/ConfigDescription.cpp b/tools/aapt2/ConfigDescription.cpp
index c1697e794c1e..1812d96a2ea3 100644
--- a/tools/aapt2/ConfigDescription.cpp
+++ b/tools/aapt2/ConfigDescription.cpp
@@ -789,4 +789,96 @@ ConfigDescription ConfigDescription::copyWithoutSdkVersion() const {
     return copy;
 }
 
+bool ConfigDescription::dominates(const ConfigDescription& o) const {
+    if (*this == defaultConfig() || *this == o) {
+        return true;
+    }
+    return matchWithDensity(o)
+            && !o.matchWithDensity(*this)
+            && !isMoreSpecificThan(o)
+            && !o.hasHigherPrecedenceThan(*this);
+}
+
+bool ConfigDescription::hasHigherPrecedenceThan(const ConfigDescription& o) const {
+    // The order of the following tests defines the importance of one
+    // configuration parameter over another. Those tests first are more
+    // important, trumping any values in those following them.
+    // The ordering should be the same as ResTable_config#isBetterThan.
+    if (mcc || o.mcc) return (!o.mcc);
+    if (mnc || o.mnc) return (!o.mnc);
+    if (language[0] || o.language[0]) return (!o.language[0]);
+    if (country[0] || o.country[0]) return (!o.country[0]);
+    // Script and variant require either a language or country, both of which
+    // have higher precedence.
+    if ((screenLayout | o.screenLayout) & MASK_LAYOUTDIR) {
+        return !(o.screenLayout & MASK_LAYOUTDIR);
+    }
+    if (smallestScreenWidthDp || o.smallestScreenWidthDp) return (!o.smallestScreenWidthDp);
+    if (screenWidthDp || o.screenWidthDp) return (!o.screenWidthDp);
+    if (screenHeightDp || o.screenHeightDp) return (!o.screenHeightDp);
+    if ((screenLayout | o.screenLayout) & MASK_SCREENSIZE) {
+        return !(o.screenLayout & MASK_SCREENSIZE);
+    }
+    if ((screenLayout | o.screenLayout) & MASK_SCREENLONG) {
+        return !(o.screenLayout & MASK_SCREENLONG);
+    }
+    if ((screenLayout2 | o.screenLayout2) & MASK_SCREENROUND) {
+        return !(o.screenLayout2 & MASK_SCREENROUND);
+    }
+    if (orientation || o.orientation) return (!o.orientation);
+    if ((uiMode | o.uiMode) & MASK_UI_MODE_TYPE) {
+        return !(o.uiMode & MASK_UI_MODE_TYPE);
+    }
+    if ((uiMode | o.uiMode) & MASK_UI_MODE_NIGHT) {
+        return !(o.uiMode & MASK_UI_MODE_NIGHT);
+    }
+    if (density || o.density) return (!o.density);
+    if (touchscreen || o.touchscreen) return (!o.touchscreen);
+    if ((inputFlags | o.inputFlags) & MASK_KEYSHIDDEN) {
+        return !(o.inputFlags & MASK_KEYSHIDDEN);
+    }
+    if ((inputFlags | o.inputFlags) & MASK_NAVHIDDEN) {
+        return !(o.inputFlags & MASK_NAVHIDDEN);
+    }
+    if (keyboard || o.keyboard) return (!o.keyboard);
+    if (navigation || o.navigation) return (!o.navigation);
+    if (screenWidth || o.screenWidth) return (!o.screenWidth);
+    if (screenHeight || o.screenHeight) return (!o.screenHeight);
+    if (sdkVersion || o.sdkVersion) return (!o.sdkVersion);
+    if (minorVersion || o.minorVersion) return (!o.minorVersion);
+    // Both configurations have nothing defined except some possible future
+    // value. Returning the comparison of the two configurations is a
+    // "best effort" at this point to protect against incorrect dominations.
+    return *this != o;
+}
+
+bool ConfigDescription::conflictsWith(const ConfigDescription& o) const {
+    // This method should be updated as new configuration parameters are
+    // introduced (e.g. screenConfig2).
+    auto pred = [](const uint32_t a, const uint32_t b) -> bool {
+        return a == 0 || b == 0 || a == b;
+    };
+    // The values here can be found in ResTable_config#match. Density and range
+    // values can't lead to conflicts, and are ignored.
+    return !pred(mcc, o.mcc)
+            || !pred(mnc, o.mnc)
+            || !pred(locale, o.locale)
+            || !pred(screenLayout & MASK_LAYOUTDIR, o.screenLayout & MASK_LAYOUTDIR)
+            || !pred(screenLayout & MASK_SCREENLONG, o.screenLayout & MASK_SCREENLONG)
+            || !pred(screenLayout & MASK_UI_MODE_TYPE, o.screenLayout & MASK_UI_MODE_TYPE)
+            || !pred(uiMode & MASK_UI_MODE_TYPE, o.uiMode & MASK_UI_MODE_TYPE)
+            || !pred(uiMode & MASK_UI_MODE_NIGHT, o.uiMode & MASK_UI_MODE_NIGHT)
+            || !pred(screenLayout2 & MASK_SCREENROUND, o.screenLayout2 & MASK_SCREENROUND)
+            || !pred(orientation, o.orientation)
+            || !pred(touchscreen, o.touchscreen)
+            || !pred(inputFlags & MASK_KEYSHIDDEN, o.inputFlags & MASK_KEYSHIDDEN)
+            || !pred(inputFlags & MASK_NAVHIDDEN, o.inputFlags & MASK_NAVHIDDEN)
+            || !pred(keyboard, o.keyboard)
+            || !pred(navigation, o.navigation);
+}
+
+bool ConfigDescription::isCompatibleWith(const ConfigDescription& o) const {
+    return !conflictsWith(o) && !dominates(o) && !o.dominates(*this);
+}
+
 } // namespace aapt
diff --git a/tools/aapt2/ConfigDescription.h b/tools/aapt2/ConfigDescription.h
index 6858c624fc80..d8016210d4a7 100644
--- a/tools/aapt2/ConfigDescription.h
+++ b/tools/aapt2/ConfigDescription.h
@@ -59,14 +59,50 @@ struct ConfigDescription : public android::ResTable_config {
     ConfigDescription& operator=(const ConfigDescription& o);
     ConfigDescription& operator=(ConfigDescription&& o);
 
+    ConfigDescription copyWithoutSdkVersion() const;
+
+    /**
+     * A configuration X dominates another configuration Y, if X has at least the
+     * precedence of Y and X is strictly more general than Y: for any type defined
+     * by X, the same type is defined by Y with a value equal to or, in the case
+     * of ranges, more specific than that of X.
+     *
+     * For example, the configuration 'en-w800dp' dominates 'en-rGB-w1024dp'. It
+     * does not dominate 'fr', 'en-w720dp', or 'mcc001-en-w800dp'.
+     */
+    bool dominates(const ConfigDescription& o) const;
+
+    /**
+     * Returns true if this configuration defines a more important configuration
+     * parameter than o. For example, "en" has higher precedence than "v23",
+     * whereas "en" has the same precedence as "en-v23".
+     */
+    bool hasHigherPrecedenceThan(const ConfigDescription& o) const;
+
+    /**
+     * A configuration conflicts with another configuration if both
+     * configurations define an incompatible configuration parameter. An
+     * incompatible configuration parameter is a non-range, non-density parameter
+     * that is defined in both configurations as a different, non-default value.
+     */
+    bool conflictsWith(const ConfigDescription& o) const;
+
+    /**
+     * A configuration is compatible with another configuration if both
+     * configurations can match a common concrete device configuration and are
+     * unrelated by domination. For example, land-v11 conflicts with port-v21
+     * but is compatible with v21 (both land-v11 and v21 would match en-land-v23).
+     */
+    bool isCompatibleWith(const ConfigDescription& o) const;
+
+    bool matchWithDensity(const ConfigDescription& o) const;
+
     bool operator<(const ConfigDescription& o) const;
     bool operator<=(const ConfigDescription& o) const;
     bool operator==(const ConfigDescription& o) const;
     bool operator!=(const ConfigDescription& o) const;
     bool operator>=(const ConfigDescription& o) const;
     bool operator>(const ConfigDescription& o) const;
-
-    ConfigDescription copyWithoutSdkVersion() const;
 };
 
 inline ConfigDescription::ConfigDescription() {
@@ -103,6 +139,10 @@ inline ConfigDescription& ConfigDescription::operator=(ConfigDescription&& o) {
     return *this;
 }
 
+inline bool ConfigDescription::matchWithDensity(const ConfigDescription& o) const {
+    return match(o) && (density == 0 || density == o.density);
+}
+
 inline bool ConfigDescription::operator<(const ConfigDescription& o) const {
     return compare(o) < 0;
 }
diff --git a/tools/aapt2/DominatorTree.cpp b/tools/aapt2/DominatorTree.cpp
new file mode 100644
index 000000000000..29587a8b39a7
--- /dev/null
+++ b/tools/aapt2/DominatorTree.cpp
@@ -0,0 +1,89 @@
+/*
+ * 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 "ConfigDescription.h"
+#include "DominatorTree.h"
+
+#include <algorithm>
+
+namespace aapt {
+
+DominatorTree::DominatorTree(
+        const std::vector<std::unique_ptr<ResourceConfigValue>>& configs) {
+    for (const auto& config : configs) {
+        mProductRoots[config->product].tryAddChild(
+                util::make_unique<Node>(config.get(), nullptr));
+    }
+}
+
+void DominatorTree::accept(Visitor* visitor) {
+    for (auto& entry : mProductRoots) {
+        visitor->visitTree(entry.first, &entry.second);
+    }
+}
+
+bool DominatorTree::Node::tryAddChild(std::unique_ptr<Node> newChild) {
+    assert(newChild->mValue && "cannot add a root or empty node as a child");
+    if (mValue && !dominates(newChild.get())) {
+        // This is not the root and the child dominates us.
+        return false;
+    }
+    return addChild(std::move(newChild));
+}
+
+bool DominatorTree::Node::addChild(std::unique_ptr<Node> newChild) {
+    bool hasDominatedChildren = false;
+    // Demote children dominated by the new config.
+    for (auto& child : mChildren) {
+        if (newChild->dominates(child.get())) {
+            child->mParent = newChild.get();
+            newChild->mChildren.push_back(std::move(child));
+            child = {};
+            hasDominatedChildren = true;
+        }
+    }
+    // Remove dominated children.
+    if (hasDominatedChildren) {
+        mChildren.erase(std::remove_if(mChildren.begin(), mChildren.end(),
+                [](const std::unique_ptr<Node>& child) -> bool {
+            return child == nullptr;
+        }), mChildren.end());
+    }
+    // Add the new config to a child if a child dominates the new config.
+    for (auto& child : mChildren) {
+        if (child->dominates(newChild.get())) {
+            child->addChild(std::move(newChild));
+            return true;
+        }
+    }
+    // The new config is not dominated by a child, so add it here.
+    newChild->mParent = this;
+    mChildren.push_back(std::move(newChild));
+    return true;
+}
+
+bool DominatorTree::Node::dominates(const Node* other) const {
+    // Check root node dominations.
+    if (other->isRootNode()) {
+        return isRootNode();
+    } else if (isRootNode()) {
+        return true;
+    }
+    // Neither node is a root node; compare the configurations.
+    return mValue->config.dominates(other->mValue->config);
+}
+
+} // namespace aapt
diff --git a/tools/aapt2/DominatorTree.h b/tools/aapt2/DominatorTree.h
new file mode 100644
index 000000000000..ad2df0e4fd66
--- /dev/null
+++ b/tools/aapt2/DominatorTree.h
@@ -0,0 +1,127 @@
+/*
+ * 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.
+ */
+
+#ifndef AAPT_DOMINATOR_TREE_H
+#define AAPT_DOMINATOR_TREE_H
+
+#include "ResourceTable.h"
+
+#include <map>
+#include <memory>
+#include <string>
+#include <vector>
+
+namespace aapt {
+
+/**
+ * A dominator tree of configurations as defined by resolution rules for Android
+ * resources.
+ *
+ * A node in the tree represents a resource configuration.
+ *
+ * The tree has the following property:
+ *
+ * Each child of a given configuration defines a strict superset of qualifiers
+ * and has a value that is at least as specific as that of its ancestors. A
+ * value is "at least as specific" if it is either identical or it represents a
+ * stronger requirement.
+ * For example, v21 is more specific than v11, and w1200dp is more specific than
+ * w800dp.
+ *
+ * The dominator tree relies on the underlying configurations passed to it. If
+ * the configurations passed to the dominator tree go out of scope, the tree
+ * will exhibit undefined behavior.
+ */
+class DominatorTree {
+public:
+    explicit DominatorTree(const std::vector<std::unique_ptr<ResourceConfigValue>>& configs);
+
+    class Node {
+    public:
+        explicit Node(ResourceConfigValue* value = nullptr, Node* parent = nullptr) :
+                mValue(value), mParent(parent) {
+        }
+
+        inline ResourceConfigValue* value() const {
+            return mValue;
+        }
+
+        inline Node* parent() const {
+            return mParent;
+        }
+
+        inline bool isRootNode() const {
+            return !mValue;
+        }
+
+        inline const std::vector<std::unique_ptr<Node>>& children() const {
+            return mChildren;
+        }
+
+        bool tryAddChild(std::unique_ptr<Node> newChild);
+
+    private:
+        bool addChild(std::unique_ptr<Node> newChild);
+        bool dominates(const Node* other) const;
+
+        ResourceConfigValue* mValue;
+        Node* mParent;
+        std::vector<std::unique_ptr<Node>> mChildren;
+
+        DISALLOW_COPY_AND_ASSIGN(Node);
+    };
+
+    struct Visitor {
+        virtual ~Visitor() = default;
+        virtual void visitTree(const std::string& product, Node* root) = 0;
+    };
+
+    class BottomUpVisitor : public Visitor {
+    public:
+        virtual ~BottomUpVisitor() = default;
+
+        void visitTree(const std::string& product, Node* root) override {
+            for (auto& child : root->children()) {
+                visitNode(child.get());
+            }
+        }
+
+        virtual void visitConfig(Node* node) = 0;
+
+    private:
+        void visitNode(Node* node) {
+            for (auto& child : node->children()) {
+                visitNode(child.get());
+            }
+            visitConfig(node);
+        }
+    };
+
+    void accept(Visitor* visitor);
+
+    inline const std::map<std::string, Node>& getProductRoots() const {
+        return mProductRoots;
+    }
+
+private:
+    DISALLOW_COPY_AND_ASSIGN(DominatorTree);
+
+    std::map<std::string, Node> mProductRoots;
+};
+
+} // namespace aapt
+
+#endif // AAPT_DOMINATOR_TREE_H
diff --git a/tools/aapt2/DominatorTree_test.cpp b/tools/aapt2/DominatorTree_test.cpp
new file mode 100644
index 000000000000..fb850e4dae61
--- /dev/null
+++ b/tools/aapt2/DominatorTree_test.cpp
@@ -0,0 +1,151 @@
+/*
+ * 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 "DominatorTree.h"
+#include "test/Test.h"
+#include "util/Util.h"
+
+#include <sstream>
+#include <string>
+#include <vector>
+
+namespace aapt {
+
+namespace {
+
+class PrettyPrinter : public DominatorTree::Visitor {
+public:
+    explicit PrettyPrinter(const int indent = 2) : mIndent(indent) {
+    }
+
+    void visitTree(const std::string& product, DominatorTree::Node* root) override {
+        for (auto& child : root->children()) {
+            visitNode(child.get(), 0);
+        }
+    }
+
+    std::string toString(DominatorTree* tree) {
+        mBuffer.str("");
+        mBuffer.clear();
+        tree->accept(this);
+        return mBuffer.str();
+    }
+
+private:
+    void visitConfig(const DominatorTree::Node* node, const int indent) {
+        auto configString = node->value()->config.toString();
+        mBuffer << std::string(indent, ' ')
+                << (configString.isEmpty() ? "<default>" : configString)
+                << std::endl;
+    }
+
+    void visitNode(const DominatorTree::Node* node, const int indent) {
+        visitConfig(node, indent);
+        for (const auto& child : node->children()) {
+            visitNode(child.get(), indent + mIndent);
+        }
+    }
+
+    std::stringstream mBuffer;
+    const int mIndent = 2;
+};
+
+} // namespace
+
+TEST(DominatorTreeTest, DefaultDominatesEverything) {
+    const ConfigDescription defaultConfig = {};
+    const ConfigDescription landConfig = test::parseConfigOrDie("land");
+    const ConfigDescription sw600dpLandConfig = test::parseConfigOrDie("sw600dp-land-v13");
+
+    std::vector<std::unique_ptr<ResourceConfigValue>> configs;
+    configs.push_back(util::make_unique<ResourceConfigValue>(defaultConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(landConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(sw600dpLandConfig, ""));
+
+    DominatorTree tree(configs);
+    PrettyPrinter printer;
+
+    std::string expected =
+            "<default>\n"
+            "  land\n"
+            "  sw600dp-land-v13\n";
+    EXPECT_EQ(expected, printer.toString(&tree));
+}
+
+TEST(DominatorTreeTest, ProductsAreDominatedSeparately) {
+    const ConfigDescription defaultConfig = {};
+    const ConfigDescription landConfig = test::parseConfigOrDie("land");
+    const ConfigDescription sw600dpLandConfig = test::parseConfigOrDie("sw600dp-land-v13");
+
+    std::vector<std::unique_ptr<ResourceConfigValue>> configs;
+    configs.push_back(util::make_unique<ResourceConfigValue>(defaultConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(landConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(defaultConfig, "phablet"));
+    configs.push_back(util::make_unique<ResourceConfigValue>(sw600dpLandConfig, "phablet"));
+
+    DominatorTree tree(configs);
+    PrettyPrinter printer;
+
+    std::string expected =
+            "<default>\n"
+            "  land\n"
+            "<default>\n"
+            "  sw600dp-land-v13\n";
+    EXPECT_EQ(expected, printer.toString(&tree));
+}
+
+TEST(DominatorTreeTest, MoreSpecificConfigurationsAreDominated) {
+    const ConfigDescription defaultConfig = {};
+    const ConfigDescription enConfig = test::parseConfigOrDie("en");
+    const ConfigDescription enV21Config = test::parseConfigOrDie("en-v21");
+    const ConfigDescription ldrtlConfig = test::parseConfigOrDie("ldrtl-v4");
+    const ConfigDescription ldrtlXhdpiConfig = test::parseConfigOrDie("ldrtl-xhdpi-v4");
+    const ConfigDescription sw300dpConfig = test::parseConfigOrDie("sw300dp-v13");
+    const ConfigDescription sw540dpConfig = test::parseConfigOrDie("sw540dp-v14");
+    const ConfigDescription sw600dpConfig = test::parseConfigOrDie("sw600dp-v14");
+    const ConfigDescription sw720dpConfig = test::parseConfigOrDie("sw720dp-v13");
+    const ConfigDescription v20Config = test::parseConfigOrDie("v20");
+
+    std::vector<std::unique_ptr<ResourceConfigValue>> configs;
+    configs.push_back(util::make_unique<ResourceConfigValue>(defaultConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(enConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(enV21Config, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(ldrtlConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(ldrtlXhdpiConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(sw300dpConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(sw540dpConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(sw600dpConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(sw720dpConfig, ""));
+    configs.push_back(util::make_unique<ResourceConfigValue>(v20Config, ""));
+
+    DominatorTree tree(configs);
+    PrettyPrinter printer;
+
+    std::string expected =
+            "<default>\n"
+            "  en\n"
+            "    en-v21\n"
+            "  ldrtl-v4\n"
+            "    ldrtl-xhdpi-v4\n"
+            "  sw300dp-v13\n"
+            "    sw540dp-v14\n"
+            "      sw600dp-v14\n"
+            "    sw720dp-v13\n"
+            "  v20\n";
+    EXPECT_EQ(expected, printer.toString(&tree));
+}
+
+} // namespace aapt
diff --git a/tools/aapt2/link/Link.cpp b/tools/aapt2/link/Link.cpp
index c2363943b535..b6b4b4732669 100644
--- a/tools/aapt2/link/Link.cpp
+++ b/tools/aapt2/link/Link.cpp
@@ -72,6 +72,7 @@ struct LinkOptions {
 
     bool noAutoVersion = false;
     bool noVersionVectors = false;
+    bool noResourceDeduping = false;
     bool staticLib = false;
     bool noStaticLibPackages = false;
     bool generateNonFinalIds = false;
@@ -1505,6 +1506,14 @@ public:
             }
         }
 
+        if (!mOptions.noResourceDeduping) {
+            ResourceDeduper deduper;
+            if (!deduper.consume(mContext, &mFinalTable)) {
+                mContext->getDiagnostics()->error(DiagMessage() << "failed deduping resources");
+                return 1;
+            }
+        }
+
         proguard::KeepSet proguardKeepSet;
         proguard::KeepSet proguardMainDexKeepSet;
 
@@ -1743,6 +1752,9 @@ int link(const std::vector<StringPiece>& args) {
                             "Disables automatic versioning of vector drawables. Use this only\n"
                             "when building with vector drawable support library",
                             &options.noVersionVectors)
+            .optionalSwitch("--no-resource-deduping", "Disables automatic deduping of resources with\n"
+                            "identical values across compatible configurations.",
+                            &options.noResourceDeduping)
             .optionalSwitch("-x", "Legacy flag that specifies to use the package identifier 0x01",
                             &legacyXFlag)
             .optionalSwitch("-z", "Require localization of strings marked 'suggested'",
diff --git a/tools/aapt2/link/Linkers.h b/tools/aapt2/link/Linkers.h
index 82e28682f78e..ce455da9b58b 100644
--- a/tools/aapt2/link/Linkers.h
+++ b/tools/aapt2/link/Linkers.h
@@ -60,6 +60,14 @@ public:
 };
 
 /**
+ * Removes duplicated key-value entries from dominated resources.
+ */
+class ResourceDeduper : public IResourceTableConsumer {
+public:
+    bool consume(IAaptContext* context, ResourceTable* table) override;
+};
+
+/**
  * If any attribute resource values are defined as public, this consumer will move all private
  * attribute resource values to a private ^private-attr type, avoiding backwards compatibility
  * issues with new apps running on old platforms.
diff --git a/tools/aapt2/link/ResourceDeduper.cpp b/tools/aapt2/link/ResourceDeduper.cpp
new file mode 100644
index 000000000000..027626152a6c
--- /dev/null
+++ b/tools/aapt2/link/ResourceDeduper.cpp
@@ -0,0 +1,114 @@
+/*
+ * 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 "DominatorTree.h"
+#include "ResourceTable.h"
+#include "link/Linkers.h"
+
+#include <algorithm>
+
+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) :
+            mContext(context), mEntry(entry) {
+    }
+
+    void visitConfig(Node* node) {
+        Node* parent = node->parent();
+        if (!parent) {
+            return;
+        }
+        ResourceConfigValue* nodeValue = node->value();
+        ResourceConfigValue* parentValue = parent->value();
+        if (!nodeValue || !parentValue) {
+            return;
+        }
+        if (!nodeValue->value->equals(parentValue->value.get())) {
+            return;
+        }
+
+        // Compare compatible configs for this entry and ensure the values are
+        // equivalent.
+        const ConfigDescription& nodeConfiguration = nodeValue->config;
+        for (const auto& sibling : mEntry->values) {
+            if (!sibling->value) {
+                // Sibling was already removed.
+                continue;
+            }
+            if (nodeConfiguration.isCompatibleWith(sibling->config)
+                    && !nodeValue->value->equals(sibling->value.get())) {
+                // The configurations are compatible, but the value is
+                // different, so we can't remove this value.
+                return;
+            }
+        }
+        if (mContext->verbose()) {
+            mContext->getDiagnostics()->note(
+                    DiagMessage(nodeValue->value->getSource())
+                            << "removing dominated duplicate resource with name \""
+                            << mEntry->name << "\"");
+        }
+        nodeValue->value = {};
+    }
+
+private:
+    IAaptContext* mContext;
+    ResourceEntry* mEntry;
+};
+
+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;
+}
+
+} // aapt
diff --git a/tools/aapt2/link/ResourceDeduper_test.cpp b/tools/aapt2/link/ResourceDeduper_test.cpp
new file mode 100644
index 000000000000..47071a51bb73
--- /dev/null
+++ b/tools/aapt2/link/ResourceDeduper_test.cpp
@@ -0,0 +1,83 @@
+/*
+ * 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 "ResourceTable.h"
+#include "link/Linkers.h"
+#include "test/Test.h"
+
+namespace aapt {
+
+TEST(ResourceDeduperTest, SameValuesAreDeduped) {
+    std::unique_ptr<IAaptContext> context = test::ContextBuilder().build();
+    const ConfigDescription defaultConfig = {};
+    const ConfigDescription enConfig = test::parseConfigOrDie("en");
+    const ConfigDescription enV21Config = test::parseConfigOrDie("en-v21");
+    // Chosen because this configuration is compatible with en.
+    const ConfigDescription landConfig = test::parseConfigOrDie("land");
+
+    std::unique_ptr<ResourceTable> table = test::ResourceTableBuilder()
+            .addString("android:string/dedupe", ResourceId{}, defaultConfig, "dedupe")
+            .addString("android:string/dedupe", ResourceId{}, enConfig, "dedupe")
+            .addString("android:string/dedupe", ResourceId{}, landConfig, "dedupe")
+            .addString("android:string/dedupe2", ResourceId{}, defaultConfig, "dedupe")
+            .addString("android:string/dedupe2", ResourceId{}, enConfig, "dedupe")
+            .addString("android:string/dedupe2", ResourceId{}, enV21Config, "keep")
+            .addString("android:string/dedupe2", ResourceId{}, landConfig, "dedupe")
+            .build();
+
+    ASSERT_TRUE(ResourceDeduper().consume(context.get(), table.get()));
+    EXPECT_EQ(
+            nullptr,
+            test::getValueForConfig<String>(table.get(), "android:string/dedupe", enConfig));
+    EXPECT_EQ(
+            nullptr,
+            test::getValueForConfig<String>(table.get(), "android:string/dedupe", landConfig));
+    EXPECT_EQ(
+            nullptr,
+            test::getValueForConfig<String>(table.get(), "android:string/dedupe2", enConfig));
+    EXPECT_NE(
+            nullptr,
+            test::getValueForConfig<String>(table.get(), "android:string/dedupe2", enV21Config));
+}
+
+TEST(ResourceDeduperTest, DifferentValuesAreKept) {
+    std::unique_ptr<IAaptContext> context = test::ContextBuilder().build();
+    const ConfigDescription defaultConfig = {};
+    const ConfigDescription enConfig = test::parseConfigOrDie("en");
+    const ConfigDescription enV21Config = test::parseConfigOrDie("en-v21");
+    // Chosen because this configuration is compatible with en.
+    const ConfigDescription landConfig = test::parseConfigOrDie("land");
+
+    std::unique_ptr<ResourceTable> table = test::ResourceTableBuilder()
+            .addString("android:string/keep", ResourceId{}, defaultConfig, "keep")
+            .addString("android:string/keep", ResourceId{}, enConfig, "keep")
+            .addString("android:string/keep", ResourceId{}, enV21Config, "keep2")
+            .addString("android:string/keep", ResourceId{}, landConfig, "keep2")
+            .build();
+
+    ASSERT_TRUE(ResourceDeduper().consume(context.get(), table.get()));
+    EXPECT_NE(
+            nullptr,
+            test::getValueForConfig<String>(table.get(), "android:string/keep", enConfig));
+    EXPECT_NE(
+            nullptr,
+            test::getValueForConfig<String>(table.get(), "android:string/keep", enV21Config));
+    EXPECT_NE(
+            nullptr,
+            test::getValueForConfig<String>(table.get(), "android:string/keep", landConfig));
+}
+
+}  // namespace aapt
diff --git a/tools/aapt2/readme.md b/tools/aapt2/readme.md
index 267200dea444..93c790d80c4c 100644
--- a/tools/aapt2/readme.md
+++ b/tools/aapt2/readme.md
@@ -4,6 +4,10 @@
 ### `aapt2 compile ...`
 - Added support for inline complex XML resources. See
   https://developer.android.com/guide/topics/resources/complex-xml-resources.html
+### `aapt link ...`
+- Duplicate resource filtering: removes duplicate resources in dominated configurations
+  that are always identical when selected at runtime. This can be disabled with
+  `--no-resource-deduping`.
 
 ## Version 2.1
 ### `aapt2 link ...`