tools/gn/item_tree.cc

   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::GetAllItemNodesLocked(std::vector<const ItemNode*>* 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);
  96 }
  97
  98 void ItemTree::GetAllItemsLocked(std::vector<const Item*>* dest) const {
  99   lock_.AssertAcquired();
 100   dest->reserve(items_.size());
 101   for (StringToNodeHash::const_iterator i = items_.begin();
 102        i != items_.end(); ++i) {
 103     dest->push_back(i->second->item());
 104   }
 105 }
 106
 107 Err ItemTree::CheckForBadItems() const {
 108   base::AutoLock lock(lock_);
 109
 110   // Look for errors where we find a GENERATED node that refers to a REFERENCED
 111   // one. There may be other nodes depending on the GENERATED one, but listing
 112   // all of those isn't helpful, we want to find the broken link.
 113   //
 114   // This finds normal "missing dependency" errors but does not find circular
 115   // dependencies because in this case all items in the cycle will be GENERATED
 116   // but none will be resolved. If this happens, we'll check explicitly for
 117   // that below.
 118   std::vector<const ItemNode*> bad_nodes;
 119   std::string depstring;
 120   for (StringToNodeHash::const_iterator i = items_.begin();
 121        i != items_.end(); ++i) {
 122     const ItemNode* src = i->second;
 123     if (!src->should_generate())
 124       continue;  // Skip ungenerated nodes.
 125
 126     if (src->state() == ItemNode::DEFINED ||
 127         src->state() == ItemNode::PENDING_DEPS) {
 128       bad_nodes.push_back(src);
 129
 130       // Check dependencies.
 131       for (ItemNode::ItemNodeMap::const_iterator dest =
 132                src->unresolved_dependencies().begin();
 133           dest != src->unresolved_dependencies().end();
 134           ++dest) {
 135         const ItemNode* dest_node = dest->first;
 136         if (dest_node->state() == ItemNode::REFERENCED) {
 137           depstring += "\"" + src->item()->label().GetUserVisibleName(false) +
 138               "\" needs " + dest_node->item()->GetItemTypeName() +
 139               " \"" + dest_node->item()->label().GetUserVisibleName(false) +
 140               "\"\n";
 141         }
 142       }
 143     }
 144   }
 145
 146   if (!bad_nodes.empty() && depstring.empty()) {
 147     // Our logic above found a bad node but didn't identify the problem. This
 148     // normally means a circular dependency.
 149     depstring = CheckForCircularDependenciesLocked(bad_nodes);
 150     if (depstring.empty()) {
 151       // Something's very wrong, just dump out the bad nodes.
 152       depstring = "I have no idea what went wrong, but these are unresolved, "
 153           "possible due to an\ninternal error:";
 154       for (size_t i = 0; i < bad_nodes.size(); i++) {
 155         depstring += "\n\"" +
 156             bad_nodes[i]->item()->label().GetUserVisibleName(false) + "\"";
 157       }
 158     }
 159   }
 160
 161   if (depstring.empty())
 162     return Err();
 163   return Err(Location(), "Unresolved dependencies.", depstring);
 164 }
 165
 166 void ItemTree::MarkItemResolvedLocked(ItemNode* node) {
 167   node->SetResolved();
 168   node->item()->OnResolved();
 169
 170   // Now update our waiters, pushing the "resolved" bit.
 171   ItemNode::ItemNodeMap waiting;
 172   node->SwapOutWaitingDependencySet(&waiting);
 173   for (ItemNode::ItemNodeMap::iterator i = waiting.begin();
 174        i != waiting.end(); ++i) {
 175     ItemNode* waiter = i->first;
 176
 177     // Our node should be unresolved in the waiter.
 178     DCHECK(waiter->unresolved_dependencies().find(node) !=
 179            waiter->unresolved_dependencies().end());
 180     waiter->MarkDirectDependencyResolved(node);
 181
 182     // Recursively mark nodes as resolved.
 183     if ((waiter->state() == ItemNode::DEFINED ||
 184          waiter->state() == ItemNode::PENDING_DEPS) &&
 185         waiter->unresolved_dependencies().empty())
 186       MarkItemResolvedLocked(waiter);
 187   }
 188 }
 189
 190 std::string ItemTree::CheckForCircularDependenciesLocked(
 191     const std::vector<const ItemNode*>& bad_nodes) const {
 192   std::vector<const ItemNode*> cycle;
 193   if (!RecursiveFindCycle(bad_nodes[0], bad_nodes[0], &cycle))
 194     return std::string();  // Didn't find a cycle, something else is wrong.
 195
 196   cycle.push_back(bad_nodes[0]);
 197   std::string ret = "There is a dependency cycle:";
 198
 199   // Walk backwards since the dependency arrows point in the reverse direction.
 200   for (int i = static_cast<int>(cycle.size()) - 1; i >= 0; i--) {
 201     ret += "\n  \"" + cycle[i]->item()->label().GetUserVisibleName(false) +
 202         "\"";
 203     if (i != 0)
 204       ret += " ->";
 205   }
 206
 207   return ret;
 208 }