1 /*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "optimize/ResourceDeduper.h"
18
19 #include <algorithm>
20
21 #include "DominatorTree.h"
22 #include "ResourceTable.h"
23 #include "trace/TraceBuffer.h"
24
25 using android::ConfigDescription;
26
27 namespace aapt {
28
29 namespace {
30
31 /**
32 * Remove duplicated key-value entries from dominated resources.
33 *
34 * Based on the dominator tree, we can remove a value of an entry if:
35 *
36 * 1. The configuration for the entry's value is dominated by a configuration
37 * with an equivalent entry value.
38 * 2. All compatible configurations for the entry (those not in conflict and
39 * unrelated by domination with the configuration for the entry's value) have
40 * an equivalent entry value.
41 */
42 class DominatedKeyValueRemover : public DominatorTree::BottomUpVisitor {
43 public:
44 using Node = DominatorTree::Node;
45
DominatedKeyValueRemover(IAaptContext * context,ResourceEntry * entry)46 explicit DominatedKeyValueRemover(IAaptContext* context, ResourceEntry* entry)
47 : context_(context), entry_(entry) {}
48
VisitConfig(Node * node)49 void VisitConfig(Node* node) {
50 Node* parent = node->parent();
51 if (!parent) {
52 return;
53 }
54 ResourceConfigValue* node_value = node->value();
55 ResourceConfigValue* parent_value = parent->value();
56 if (!node_value || !parent_value) {
57 return;
58 }
59 if (!node_value->value->Equals(parent_value->value.get())) {
60 return;
61 }
62
63 // Compare compatible configs for this entry and ensure the values are
64 // equivalent.
65 const ConfigDescription& node_configuration = node_value->config;
66 for (const auto& sibling : parent->children()) {
67 ResourceConfigValue* sibling_value = sibling->value();
68 if (!sibling_value->value) {
69 // Sibling was already removed.
70 continue;
71 }
72 if (node_configuration.IsCompatibleWith(sibling_value->config) &&
73 !node_value->value->Equals(sibling_value->value.get())) {
74 // The configurations are compatible, but the value is
75 // different, so we can't remove this value.
76 return;
77 }
78 }
79 if (context_->IsVerbose()) {
80 context_->GetDiagnostics()->Note(
81 DiagMessage(node_value->value->GetSource())
82 << "removing dominated duplicate resource with name \""
83 << entry_->name << "\"");
84 context_->GetDiagnostics()->Note(
85 DiagMessage(parent_value->value->GetSource()) << "dominated here");
86 }
87 node_value->value = {};
88 }
89
90 private:
91 DISALLOW_COPY_AND_ASSIGN(DominatedKeyValueRemover);
92
93 IAaptContext* context_;
94 ResourceEntry* entry_;
95 };
96
DedupeEntry(IAaptContext * context,ResourceEntry * entry)97 static void DedupeEntry(IAaptContext* context, ResourceEntry* entry) {
98 DominatorTree tree(entry->values);
99 DominatedKeyValueRemover remover(context, entry);
100 tree.Accept(&remover);
101
102 // Erase the values that were removed.
103 entry->values.erase(
104 std::remove_if(
105 entry->values.begin(), entry->values.end(),
106 [](const std::unique_ptr<ResourceConfigValue>& val) -> bool {
107 return val == nullptr || val->value == nullptr;
108 }),
109 entry->values.end());
110 }
111
112 } // namespace
113
Consume(IAaptContext * context,ResourceTable * table)114 bool ResourceDeduper::Consume(IAaptContext* context, ResourceTable* table) {
115 TRACE_CALL();
116 for (auto& package : table->packages) {
117 for (auto& type : package->types) {
118 for (auto& entry : type->entries) {
119 DedupeEntry(context, entry.get());
120 }
121 }
122 }
123 return true;
124 }
125
126 } // namespace aapt
127