Home | History | Annotate | Download | only in aapt2 
      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 #include "DominatorTree.h"
     18 
     19 #include <algorithm>
     20 
     21 #include "android-base/logging.h"
     22 
     23 #include "ConfigDescription.h"
     24 
     25 namespace aapt {
     26 
     27 DominatorTree::DominatorTree(
     28     const std::vector<std::unique_ptr<ResourceConfigValue>>& configs) {
     29   for (const auto& config : configs) {
     30     product_roots_[config->product].TryAddChild(
     31         util::make_unique<Node>(config.get(), nullptr));
     32   }
     33 }
     34 
     35 void DominatorTree::Accept(Visitor* visitor) {
     36   for (auto& entry : product_roots_) {
     37     visitor->VisitTree(entry.first, &entry.second);
     38   }
     39 }
     40 
     41 bool DominatorTree::Node::TryAddChild(std::unique_ptr<Node> new_child) {
     42   CHECK(new_child->value_) << "cannot add a root or empty node as a child";
     43   if (value_ && !Dominates(new_child.get())) {
     44     // This is not the root and the child dominates us.
     45     return false;
     46   }
     47   return AddChild(std::move(new_child));
     48 }
     49 
     50 bool DominatorTree::Node::AddChild(std::unique_ptr<Node> new_child) {
     51   bool has_dominated_children = false;
     52   // Demote children dominated by the new config.
     53   for (auto& child : children_) {
     54     if (new_child->Dominates(child.get())) {
     55       child->parent_ = new_child.get();
     56       new_child->children_.push_back(std::move(child));
     57       child = {};
     58       has_dominated_children = true;
     59     }
     60   }
     61   // Remove dominated children.
     62   if (has_dominated_children) {
     63     children_.erase(
     64         std::remove_if(children_.begin(), children_.end(),
     65                        [](const std::unique_ptr<Node>& child) -> bool {
     66                          return child == nullptr;
     67                        }),
     68         children_.end());
     69   }
     70   // Add the new config to a child if a child dominates the new config.
     71   for (auto& child : children_) {
     72     if (child->Dominates(new_child.get())) {
     73       child->AddChild(std::move(new_child));
     74       return true;
     75     }
     76   }
     77   // The new config is not dominated by a child, so add it here.
     78   new_child->parent_ = this;
     79   children_.push_back(std::move(new_child));
     80   return true;
     81 }
     82 
     83 bool DominatorTree::Node::Dominates(const Node* other) const {
     84   // Check root node dominations.
     85   if (other->is_root_node()) {
     86     return is_root_node();
     87   } else if (is_root_node()) {
     88     return true;
     89   }
     90   // Neither node is a root node; compare the configurations.
     91   return value_->config.Dominates(other->value_->config);
     92 }
     93 
     94 }  // namespace aapt
     95