177788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall/* 277788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * Copyright (C) 2016 The Android Open Source Project 377788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 477788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * Licensed under the Apache License, Version 2.0 (the "License"); 577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * you may not use this file except in compliance with the License. 677788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * You may obtain a copy of the License at 777788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 877788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * http://www.apache.org/licenses/LICENSE-2.0 977788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 1077788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * Unless required by applicable law or agreed to in writing, software 1177788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * distributed under the License is distributed on an "AS IS" BASIS, 1277788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1377788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * See the License for the specific language governing permissions and 1477788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * limitations under the License. 1577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall */ 1677788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 17d48944a745f9ed121e6bde22ef6feb3a44fbec39Adam Lesinski#include "optimize/ResourceDeduper.h" 1877788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 1977788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall#include <algorithm> 2077788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 21ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski#include "DominatorTree.h" 22ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski#include "ResourceTable.h" 23ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski 2477788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwallnamespace aapt { 2577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 2677788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwallnamespace { 2777788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 2877788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall/** 2977788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * Remove duplicated key-value entries from dominated resources. 3077788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 3177788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * Based on the dominator tree, we can remove a value of an entry if: 3277788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 3377788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 1. The configuration for the entry's value is dominated by a configuration 3477788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * with an equivalent entry value. 3577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 2. All compatible configurations for the entry (those not in conflict and 3677788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * unrelated by domination with the configuration for the entry's value) have 3777788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * an equivalent entry value. 3877788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall */ 3977788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwallclass DominatedKeyValueRemover : public DominatorTree::BottomUpVisitor { 40cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski public: 41cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski using Node = DominatorTree::Node; 4277788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 43cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski explicit DominatedKeyValueRemover(IAaptContext* context, ResourceEntry* entry) 44ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski : context_(context), entry_(entry) {} 4577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 46ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski void VisitConfig(Node* node) { 47cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski Node* parent = node->parent(); 48cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski if (!parent) { 49cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return; 50cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 51ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski ResourceConfigValue* node_value = node->value(); 52ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski ResourceConfigValue* parent_value = parent->value(); 53ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski if (!node_value || !parent_value) { 54cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return; 55cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 56ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski if (!node_value->value->Equals(parent_value->value.get())) { 57cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return; 58cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 5977788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 60cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski // Compare compatible configs for this entry and ensure the values are 61cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski // equivalent. 62ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski const ConfigDescription& node_configuration = node_value->config; 63ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski for (const auto& sibling : entry_->values) { 64cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski if (!sibling->value) { 65cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski // Sibling was already removed. 66cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski continue; 67cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 68ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski if (node_configuration.IsCompatibleWith(sibling->config) && 69ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski !node_value->value->Equals(sibling->value.get())) { 70cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski // The configurations are compatible, but the value is 71cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski // different, so we can't remove this value. 72cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return; 73cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 74cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 75ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski if (context_->IsVerbose()) { 76ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski context_->GetDiagnostics()->Note( 77ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski DiagMessage(node_value->value->GetSource()) 78cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski << "removing dominated duplicate resource with name \"" 79ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski << entry_->name << "\""); 808f7c550e20a6edbc9af7bb48675afaf8bcb3783fAdam Lesinski context_->GetDiagnostics()->Note( 818f7c550e20a6edbc9af7bb48675afaf8bcb3783fAdam Lesinski DiagMessage(parent_value->value->GetSource()) << "dominated here"); 8277788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall } 83ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski node_value->value = {}; 84cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 8577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 86cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski private: 87ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski DISALLOW_COPY_AND_ASSIGN(DominatedKeyValueRemover); 88ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski 89ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski IAaptContext* context_; 90ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski ResourceEntry* entry_; 9177788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall}; 9277788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 93ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinskistatic void DedupeEntry(IAaptContext* context, ResourceEntry* entry) { 94cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski DominatorTree tree(entry->values); 95cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski DominatedKeyValueRemover remover(context, entry); 96ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski tree.Accept(&remover); 9777788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 98cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski // Erase the values that were removed. 99cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski entry->values.erase( 100cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski std::remove_if( 101cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski entry->values.begin(), entry->values.end(), 102cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski [](const std::unique_ptr<ResourceConfigValue>& val) -> bool { 103cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return val == nullptr || val->value == nullptr; 104cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski }), 105cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski entry->values.end()); 10677788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall} 10777788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 108cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski} // namespace 10977788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 110ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinskibool ResourceDeduper::Consume(IAaptContext* context, ResourceTable* table) { 111cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski for (auto& package : table->packages) { 112cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski for (auto& type : package->types) { 113cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski for (auto& entry : type->entries) { 114ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski DedupeEntry(context, entry.get()); 115cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 11677788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall } 117cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 118cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return true; 11977788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall} 12077788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 121ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski} // namespace aapt 122