DominatorTree.h revision cacb28f2d60858106e2819cc7d95a65e8bda890b
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 1777788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall#ifndef AAPT_DOMINATOR_TREE_H 1877788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall#define AAPT_DOMINATOR_TREE_H 1977788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 2077788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall#include "ResourceTable.h" 2177788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 2277788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall#include <map> 2377788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall#include <memory> 2477788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall#include <string> 2577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall#include <vector> 2677788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 2777788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwallnamespace aapt { 2877788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 2977788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall/** 3077788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * A dominator tree of configurations as defined by resolution rules for Android 3177788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * resources. 3277788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 3377788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * A node in the tree represents a resource configuration. 3477788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 3577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * The tree has the following property: 3677788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 3777788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * Each child of a given configuration defines a strict superset of qualifiers 3877788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * and has a value that is at least as specific as that of its ancestors. A 3977788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * value is "at least as specific" if it is either identical or it represents a 4077788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * stronger requirement. 4177788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * For example, v21 is more specific than v11, and w1200dp is more specific than 4277788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * w800dp. 4377788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * 4477788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * The dominator tree relies on the underlying configurations passed to it. If 4577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * the configurations passed to the dominator tree go out of scope, the tree 4677788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall * will exhibit undefined behavior. 4777788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall */ 4877788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwallclass DominatorTree { 49cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski public: 50cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski explicit DominatorTree( 51cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski const std::vector<std::unique_ptr<ResourceConfigValue>>& configs); 52cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 53cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski class Node { 54cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski public: 55cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski explicit Node(ResourceConfigValue* value = nullptr, Node* parent = nullptr) 56cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski : mValue(value), mParent(parent) {} 57cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 58cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski inline ResourceConfigValue* value() const { return mValue; } 59cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 60cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski inline Node* parent() const { return mParent; } 61cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 62cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski inline bool isRootNode() const { return !mValue; } 63cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 64cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski inline const std::vector<std::unique_ptr<Node>>& children() const { 65cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return mChildren; 66cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 67cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 68cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski bool tryAddChild(std::unique_ptr<Node> newChild); 69cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 70cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski private: 71cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski bool addChild(std::unique_ptr<Node> newChild); 72cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski bool dominates(const Node* other) const; 73cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 74cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski ResourceConfigValue* mValue; 75cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski Node* mParent; 76cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski std::vector<std::unique_ptr<Node>> mChildren; 77cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 78cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski DISALLOW_COPY_AND_ASSIGN(Node); 79cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski }; 80cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 81cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski struct Visitor { 82cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski virtual ~Visitor() = default; 83cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski virtual void visitTree(const std::string& product, Node* root) = 0; 84cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski }; 85cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 86cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski class BottomUpVisitor : public Visitor { 87cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski public: 88cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski virtual ~BottomUpVisitor() = default; 89cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 90cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski void visitTree(const std::string& product, Node* root) override { 91cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski for (auto& child : root->children()) { 92cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski visitNode(child.get()); 93cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 9477788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall } 9577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 96cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski virtual void visitConfig(Node* node) = 0; 97cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 98cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski private: 99cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski void visitNode(Node* node) { 100cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski for (auto& child : node->children()) { 101cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski visitNode(child.get()); 102cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 103cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski visitConfig(node); 104cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 105cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski }; 106cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 107cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski void accept(Visitor* visitor); 108cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 109cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski inline const std::map<std::string, Node>& getProductRoots() const { 110cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return mProductRoots; 111cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 112cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 113cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski private: 114cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski DISALLOW_COPY_AND_ASSIGN(DominatorTree); 11577788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 116cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski std::map<std::string, Node> mProductRoots; 11777788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall}; 11877788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 119cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski} // namespace aapt 12077788eb4cf0c5dba0f7370192e40364fe853050aAlexandria Cornwall 121cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski#endif // AAPT_DOMINATOR_TREE_H 122