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