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
27namespace 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 */
48class 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)
56        : value_(value), parent_(parent) {}
57
58    inline ResourceConfigValue* value() const { return value_; }
59
60    inline Node* parent() const { return parent_; }
61
62    inline bool is_root_node() const { return !value_; }
63
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
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:
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
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