Home | History | Annotate | Download | only in gn 
      1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "tools/gn/item_tree.h"
      6 
      7 #include <algorithm>
      8 
      9 #include "base/stl_util.h"
     10 #include "tools/gn/err.h"
     11 #include "tools/gn/item.h"
     12 #include "tools/gn/item_node.h"
     13 
     14 namespace {
     15 
     16 // Recursively looks in the tree for a given node, returning true if it
     17 // was found in the dependecy graph. This is used to see if a given node
     18 // participates in a cycle.
     19 //
     20 // Note that "look_for" and "search_in" will be the same node when starting the
     21 // search, so we don't want to return true in that case.
     22 //
     23 // If a cycle is found, the return value will be true and the cycle vector will
     24 // be filled with the path (in reverse order).
     25 bool RecursiveFindCycle(const ItemNode* look_for,
     26                         const ItemNode* search_in,
     27                         std::vector<const ItemNode*>* cycle) {
     28   const ItemNode::ItemNodeMap& unresolved =
     29       search_in->unresolved_dependencies();
     30   for (ItemNode::ItemNodeMap::const_iterator i = unresolved.begin();
     31        i != unresolved.end(); ++i) {
     32     ItemNode* cur = i->first;
     33     if (cur == look_for) {
     34       cycle->push_back(cur);
     35       return true;
     36     }
     37 
     38     if (RecursiveFindCycle(look_for, cur, cycle)) {
     39       // Found a cycle inside this one, record our path and return.
     40       cycle->push_back(cur);
     41       return true;
     42     }
     43   }
     44   return false;
     45 }
     46 
     47 }  // namespace
     48 
     49 ItemTree::ItemTree() {
     50 }
     51 
     52 ItemTree::~ItemTree() {
     53   STLDeleteContainerPairSecondPointers(items_.begin(), items_.end());
     54 }
     55 
     56 ItemNode* ItemTree::GetExistingNodeLocked(const Label& label) {
     57   lock_.AssertAcquired();
     58   StringToNodeHash::iterator found = items_.find(label);
     59   if (found == items_.end())
     60     return NULL;
     61   return found->second;
     62 }
     63 
     64 void ItemTree::AddNodeLocked(ItemNode* node) {
     65   lock_.AssertAcquired();
     66   DCHECK(items_.find(node->item()->label()) == items_.end());
     67   items_[node->item()->label()] = node;
     68 }
     69 
     70 bool ItemTree::MarkItemDefinedLocked(const BuildSettings* build_settings,
     71                                      const Label& label,
     72                                      Err* err) {
     73   lock_.AssertAcquired();
     74   DCHECK(items_.find(label) != items_.end());
     75 
     76   ItemNode* node = items_[label];
     77 
     78   if (!node->unresolved_dependencies().empty()) {
     79     // Still some pending dependencies, wait for those to be resolved.
     80     if (!node->SetDefined(build_settings, err))
     81       return false;
     82     return true;
     83   }
     84 
     85   // No more pending deps.
     86   MarkItemResolvedLocked(node);
     87   return true;
     88 }
     89 
     90 void ItemTree::GetAllItemsLocked(std::vector<const Item*>* dest) const {
     91   lock_.AssertAcquired();
     92   dest->reserve(items_.size());
     93   for (StringToNodeHash::const_iterator i = items_.begin();
     94        i != items_.end(); ++i) {
     95     dest->push_back(i->second->item());
     96   }
     97 }
     98 
     99 Err ItemTree::CheckForBadItems() const {
    100   base::AutoLock lock(lock_);
    101 
    102   // Look for errors where we find a GENERATED node that refers to a REFERENCED
    103   // one. There may be other nodes depending on the GENERATED one, but listing
    104   // all of those isn't helpful, we want to find the broken link.
    105   //
    106   // This finds normal "missing dependency" errors but does not find circular
    107   // dependencies because in this case all items in the cycle will be GENERATED
    108   // but none will be resolved. If this happens, we'll check explicitly for
    109   // that below.
    110   std::vector<const ItemNode*> bad_nodes;
    111   std::string depstring;
    112   for (StringToNodeHash::const_iterator i = items_.begin();
    113        i != items_.end(); ++i) {
    114     const ItemNode* src = i->second;
    115     if (!src->should_generate())
    116       continue;  // Skip ungenerated nodes.
    117 
    118     if (src->state() == ItemNode::DEFINED ||
    119         src->state() == ItemNode::PENDING_DEPS) {
    120       bad_nodes.push_back(src);
    121 
    122       // Check dependencies.
    123       for (ItemNode::ItemNodeMap::const_iterator dest =
    124                src->unresolved_dependencies().begin();
    125           dest != src->unresolved_dependencies().end();
    126           ++dest) {
    127         const ItemNode* dest_node = dest->first;
    128         if (dest_node->state() == ItemNode::REFERENCED) {
    129           depstring += "\"" + src->item()->label().GetUserVisibleName(false) +
    130               "\" needs " + dest_node->item()->GetItemTypeName() +
    131               " \"" + dest_node->item()->label().GetUserVisibleName(false) +
    132               "\"\n";
    133         }
    134       }
    135     }
    136   }
    137 
    138   if (!bad_nodes.empty() && depstring.empty()) {
    139     // Our logic above found a bad node but didn't identify the problem. This
    140     // normally means a circular dependency.
    141     depstring = CheckForCircularDependenciesLocked(bad_nodes);
    142     if (depstring.empty()) {
    143       // Something's very wrong, just dump out the bad nodes.
    144       depstring = "I have no idea what went wrong, but these are unresolved, "
    145           "possible due to an\ninternal error:";
    146       for (size_t i = 0; i < bad_nodes.size(); i++) {
    147         depstring += "\n\"" +
    148             bad_nodes[i]->item()->label().GetUserVisibleName(false) + "\"";
    149       }
    150     }
    151   }
    152 
    153   if (depstring.empty())
    154     return Err();
    155   return Err(Location(), "Unresolved dependencies.", depstring);
    156 }
    157 
    158 void ItemTree::MarkItemResolvedLocked(ItemNode* node) {
    159   node->SetResolved();
    160   node->item()->OnResolved();
    161 
    162   // Now update our waiters, pushing the "resolved" bit.
    163   ItemNode::ItemNodeMap waiting;
    164   node->SwapOutWaitingDependencySet(&waiting);
    165   for (ItemNode::ItemNodeMap::iterator i = waiting.begin();
    166        i != waiting.end(); ++i) {
    167     ItemNode* waiter = i->first;
    168 
    169     // Our node should be unresolved in the waiter.
    170     DCHECK(waiter->unresolved_dependencies().find(node) !=
    171            waiter->unresolved_dependencies().end());
    172     waiter->MarkDirectDependencyResolved(node);
    173 
    174     // Recursively mark nodes as resolved.
    175     if ((waiter->state() == ItemNode::DEFINED ||
    176          waiter->state() == ItemNode::PENDING_DEPS) &&
    177         waiter->unresolved_dependencies().empty())
    178       MarkItemResolvedLocked(waiter);
    179   }
    180 }
    181 
    182 std::string ItemTree::CheckForCircularDependenciesLocked(
    183     const std::vector<const ItemNode*>& bad_nodes) const {
    184   std::vector<const ItemNode*> cycle;
    185   if (!RecursiveFindCycle(bad_nodes[0], bad_nodes[0], &cycle))
    186     return std::string();  // Didn't find a cycle, something else is wrong.
    187 
    188   cycle.push_back(bad_nodes[0]);
    189   std::string ret = "There is a dependency cycle:";
    190 
    191   // Walk backwards since the dependency arrows point in the reverse direction.
    192   for (int i = static_cast<int>(cycle.size()) - 1; i >= 0; i--) {
    193     ret += "\n  \"" + cycle[i]->item()->label().GetUserVisibleName(false) +
    194         "\"";
    195     if (i != 0)
    196       ret += " ->";
    197   }
    198 
    199   return ret;
    200 }
    201