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 #ifndef AAPT_DOMINATOR_TREE_H 18 #define AAPT_DOMINATOR_TREE_H 19 20 #include <map> 21 #include <memory> 22 #include <string> 23 #include <vector> 24 25 #include "ResourceTable.h" 26 27 namespace aapt { 28 29 /** 30 * A dominator tree of configurations as defined by resolution rules for Android 31 * resources. 32 * 33 * A node in the tree represents a resource configuration. 34 * 35 * The tree has the following property: 36 * 37 * Each child of a given configuration defines a strict superset of qualifiers 38 * and has a value that is at least as specific as that of its ancestors. A 39 * value is "at least as specific" if it is either identical or it represents a 40 * stronger requirement. 41 * For example, v21 is more specific than v11, and w1200dp is more specific than 42 * w800dp. 43 * 44 * The dominator tree relies on the underlying configurations passed to it. If 45 * the configurations passed to the dominator tree go out of scope, the tree 46 * will exhibit undefined behavior. 47 */ 48 class DominatorTree { 49 public: 50 explicit DominatorTree( 51 const std::vector<std::unique_ptr<ResourceConfigValue>>& configs); 52 53 class Node { 54 public: 55 explicit Node(ResourceConfigValue* value = nullptr, Node* parent = nullptr) value_(value)56 : value_(value), parent_(parent) {} 57 value()58 inline ResourceConfigValue* value() const { return value_; } 59 parent()60 inline Node* parent() const { return parent_; } 61 is_root_node()62 inline bool is_root_node() const { return !value_; } 63 children()64 inline const std::vector<std::unique_ptr<Node>>& children() const { 65 return children_; 66 } 67 68 bool TryAddChild(std::unique_ptr<Node> new_child); 69 70 private: 71 bool AddChild(std::unique_ptr<Node> new_child); 72 bool Dominates(const Node* other) const; 73 74 ResourceConfigValue* value_; 75 Node* parent_; 76 std::vector<std::unique_ptr<Node>> children_; 77 78 DISALLOW_COPY_AND_ASSIGN(Node); 79 }; 80 81 struct Visitor { 82 virtual ~Visitor() = default; 83 virtual void VisitTree(const std::string& product, Node* root) = 0; 84 }; 85 86 class BottomUpVisitor : public Visitor { 87 public: 88 virtual ~BottomUpVisitor() = default; 89 VisitTree(const std::string & product,Node * root)90 void VisitTree(const std::string& product, Node* root) override { 91 for (auto& child : root->children()) { 92 VisitNode(child.get()); 93 } 94 } 95 96 virtual void VisitConfig(Node* node) = 0; 97 98 private: VisitNode(Node * node)99 void VisitNode(Node* node) { 100 for (auto& child : node->children()) { 101 VisitNode(child.get()); 102 } 103 VisitConfig(node); 104 } 105 }; 106 107 void Accept(Visitor* visitor); 108 product_roots()109 inline const std::map<std::string, Node>& product_roots() const { 110 return product_roots_; 111 } 112 113 private: 114 DISALLOW_COPY_AND_ASSIGN(DominatorTree); 115 116 std::map<std::string, Node> product_roots_; 117 }; 118 119 } // namespace aapt 120 121 #endif // AAPT_DOMINATOR_TREE_H 122