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
24namespace aapt {
25
26namespace {
27
28/**
29 * Remove duplicated key-value entries from dominated resources.
30 *
31 * Based on the dominator tree, we can remove a value of an entry if:
32 *
33 * 1. The configuration for the entry's value is dominated by a configuration
34 *    with an equivalent entry value.
35 * 2. All compatible configurations for the entry (those not in conflict and
36 *    unrelated by domination with the configuration for the entry's value) have
37 *    an equivalent entry value.
38 */
39class DominatedKeyValueRemover : public DominatorTree::BottomUpVisitor {
40 public:
41  using Node = DominatorTree::Node;
42
43  explicit DominatedKeyValueRemover(IAaptContext* context, ResourceEntry* entry)
44      : context_(context), entry_(entry) {}
45
46  void VisitConfig(Node* node) {
47    Node* parent = node->parent();
48    if (!parent) {
49      return;
50    }
51    ResourceConfigValue* node_value = node->value();
52    ResourceConfigValue* parent_value = parent->value();
53    if (!node_value || !parent_value) {
54      return;
55    }
56    if (!node_value->value->Equals(parent_value->value.get())) {
57      return;
58    }
59
60    // Compare compatible configs for this entry and ensure the values are
61    // equivalent.
62    const ConfigDescription& node_configuration = node_value->config;
63    for (const auto& sibling : entry_->values) {
64      if (!sibling->value) {
65        // Sibling was already removed.
66        continue;
67      }
68      if (node_configuration.IsCompatibleWith(sibling->config) &&
69          !node_value->value->Equals(sibling->value.get())) {
70        // The configurations are compatible, but the value is
71        // different, so we can't remove this value.
72        return;
73      }
74    }
75    if (context_->IsVerbose()) {
76      context_->GetDiagnostics()->Note(
77          DiagMessage(node_value->value->GetSource())
78          << "removing dominated duplicate resource with name \""
79          << entry_->name << "\"");
80      context_->GetDiagnostics()->Note(
81          DiagMessage(parent_value->value->GetSource()) << "dominated here");
82    }
83    node_value->value = {};
84  }
85
86 private:
87  DISALLOW_COPY_AND_ASSIGN(DominatedKeyValueRemover);
88
89  IAaptContext* context_;
90  ResourceEntry* entry_;
91};
92
93static void DedupeEntry(IAaptContext* context, ResourceEntry* entry) {
94  DominatorTree tree(entry->values);
95  DominatedKeyValueRemover remover(context, entry);
96  tree.Accept(&remover);
97
98  // Erase the values that were removed.
99  entry->values.erase(
100      std::remove_if(
101          entry->values.begin(), entry->values.end(),
102          [](const std::unique_ptr<ResourceConfigValue>& val) -> bool {
103            return val == nullptr || val->value == nullptr;
104          }),
105      entry->values.end());
106}
107
108}  // namespace
109
110bool ResourceDeduper::Consume(IAaptContext* context, ResourceTable* table) {
111  for (auto& package : table->packages) {
112    for (auto& type : package->types) {
113      for (auto& entry : type->entries) {
114        DedupeEntry(context, entry.get());
115      }
116    }
117  }
118  return true;
119}
120
121}  // namespace aapt
122