1// Copyright 2019 Google Inc. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include "missing_deps.h"
16
17#include <string.h>
18
19#include <iostream>
20
21#include "depfile_parser.h"
22#include "deps_log.h"
23#include "disk_interface.h"
24#include "graph.h"
25#include "state.h"
26#include "util.h"
27
28namespace {
29
30/// ImplicitDepLoader variant that stores dep nodes into the given output
31/// without updating graph deps like the base loader does.
32struct NodeStoringImplicitDepLoader : public ImplicitDepLoader {
33 NodeStoringImplicitDepLoader(
34 State* state, DepsLog* deps_log, DiskInterface* disk_interface,
35 DepfileParserOptions const* depfile_parser_options,
36 std::vector<Node*>* dep_nodes_output)
37 : ImplicitDepLoader(state, deps_log, disk_interface,
38 depfile_parser_options),
39 dep_nodes_output_(dep_nodes_output) {}
40
41 protected:
42 virtual bool ProcessDepfileDeps(Edge* edge,
43 std::vector<StringPiece>* depfile_ins,
44 std::string* err);
45
46 private:
47 std::vector<Node*>* dep_nodes_output_;
48};
49
50bool NodeStoringImplicitDepLoader::ProcessDepfileDeps(
51 Edge* edge, std::vector<StringPiece>* depfile_ins, std::string* err) {
52 for (std::vector<StringPiece>::iterator i = depfile_ins->begin();
53 i != depfile_ins->end(); ++i) {
54 uint64_t slash_bits;
55 CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits);
56 Node* node = state_->GetNode(*i, slash_bits);
57 dep_nodes_output_->push_back(node);
58 }
59 return true;
60}
61
62} // namespace
63
64MissingDependencyScannerDelegate::~MissingDependencyScannerDelegate() {}
65
66void MissingDependencyPrinter::OnMissingDep(Node* node, const std::string& path,
67 const Rule& generator) {
68 std::cout << "Missing dep: " << node->path() << " uses " << path
69 << " (generated by " << generator.name() << ")\n";
70}
71
72MissingDependencyScanner::MissingDependencyScanner(
73 MissingDependencyScannerDelegate* delegate, DepsLog* deps_log, State* state,
74 DiskInterface* disk_interface)
75 : delegate_(delegate), deps_log_(deps_log), state_(state),
76 disk_interface_(disk_interface), missing_dep_path_count_(0) {}
77
78void MissingDependencyScanner::ProcessNode(Node* node) {
79 if (!node)
80 return;
81 Edge* edge = node->in_edge();
82 if (!edge)
83 return;
84 if (!seen_.insert(node).second)
85 return;
86
87 for (std::vector<Node*>::iterator in = edge->inputs_.begin();
88 in != edge->inputs_.end(); ++in) {
89 ProcessNode(*in);
90 }
91
92 std::string deps_type = edge->GetBinding("deps");
93 if (!deps_type.empty()) {
94 DepsLog::Deps* deps = deps_log_->GetDeps(node);
95 if (deps)
96 ProcessNodeDeps(node, deps->nodes, deps->node_count);
97 } else {
98 DepfileParserOptions parser_opts;
99 std::vector<Node*> depfile_deps;
100 NodeStoringImplicitDepLoader dep_loader(state_, deps_log_, disk_interface_,
101 &parser_opts, &depfile_deps);
102 std::string err;
103 dep_loader.LoadDeps(edge, &err);
104 if (!depfile_deps.empty())
105 ProcessNodeDeps(node, &depfile_deps[0], depfile_deps.size());
106 }
107}
108
109void MissingDependencyScanner::ProcessNodeDeps(Node* node, Node** dep_nodes,
110 int dep_nodes_count) {
111 Edge* edge = node->in_edge();
112 std::set<Edge*> deplog_edges;
113 for (int i = 0; i < dep_nodes_count; ++i) {
114 Node* deplog_node = dep_nodes[i];
115 // Special exception: A dep on build.ninja can be used to mean "always
116 // rebuild this target when the build is reconfigured", but build.ninja is
117 // often generated by a configuration tool like cmake or gn. The rest of
118 // the build "implicitly" depends on the entire build being reconfigured,
119 // so a missing dep path to build.ninja is not an actual missing dependency
120 // problem.
121 if (deplog_node->path() == "build.ninja")
122 return;
123 Edge* deplog_edge = deplog_node->in_edge();
124 if (deplog_edge) {
125 deplog_edges.insert(deplog_edge);
126 }
127 }
128 std::vector<Edge*> missing_deps;
129 for (std::set<Edge*>::iterator de = deplog_edges.begin();
130 de != deplog_edges.end(); ++de) {
131 if (!PathExistsBetween(*de, edge)) {
132 missing_deps.push_back(*de);
133 }
134 }
135
136 if (!missing_deps.empty()) {
137 std::set<std::string> missing_deps_rule_names;
138 for (std::vector<Edge*>::iterator ne = missing_deps.begin();
139 ne != missing_deps.end(); ++ne) {
140 for (int i = 0; i < dep_nodes_count; ++i) {
141 if (dep_nodes[i]->in_edge() == *ne) {
142 generated_nodes_.insert(dep_nodes[i]);
143 generator_rules_.insert(&(*ne)->rule());
144 missing_deps_rule_names.insert((*ne)->rule().name());
145 delegate_->OnMissingDep(node, dep_nodes[i]->path(), (*ne)->rule());
146 }
147 }
148 }
149 missing_dep_path_count_ += missing_deps_rule_names.size();
150 nodes_missing_deps_.insert(node);
151 }
152}
153
154void MissingDependencyScanner::PrintStats() {
155 std::cout << "Processed " << seen_.size() << " nodes.\n";
156 if (HadMissingDeps()) {
157 std::cout << "Error: There are " << missing_dep_path_count_
158 << " missing dependency paths.\n";
159 std::cout << nodes_missing_deps_.size()
160 << " targets had depfile dependencies on "
161 << generated_nodes_.size() << " distinct generated inputs "
162 << "(from " << generator_rules_.size() << " rules) "
163 << " without a non-depfile dep path to the generator.\n";
164 std::cout << "There might be build flakiness if any of the targets listed "
165 "above are built alone, or not late enough, in a clean output "
166 "directory.\n";
167 } else {
168 std::cout << "No missing dependencies on generated files found.\n";
169 }
170}
171
172bool MissingDependencyScanner::PathExistsBetween(Edge* from, Edge* to) {
173 AdjacencyMap::iterator it = adjacency_map_.find(from);
174 if (it != adjacency_map_.end()) {
175 InnerAdjacencyMap::iterator inner_it = it->second.find(to);
176 if (inner_it != it->second.end()) {
177 return inner_it->second;
178 }
179 } else {
180 it = adjacency_map_.insert(std::make_pair(from, InnerAdjacencyMap())).first;
181 }
182 bool found = false;
183 for (size_t i = 0; i < to->inputs_.size(); ++i) {
184 Edge* e = to->inputs_[i]->in_edge();
185 if (e && (e == from || PathExistsBetween(from, e))) {
186 found = true;
187 break;
188 }
189 }
190 it->second.insert(std::make_pair(to, found));
191 return found;
192}
193