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
14namespace {
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).
25bool 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
49ItemTree::ItemTree() {
50}
51
52ItemTree::~ItemTree() {
53  STLDeleteContainerPairSecondPointers(items_.begin(), items_.end());
54}
55
56ItemNode* 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
64void ItemTree::AddNodeLocked(ItemNode* node) {
65  lock_.AssertAcquired();
66  DCHECK(items_.find(node->item()->label()) == items_.end());
67  items_[node->item()->label()] = node;
68}
69
70bool 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
90void 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
99Err 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
158void 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
182std::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