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 | |
28 | namespace { |
29 | |
30 | /// ImplicitDepLoader variant that stores dep nodes into the given output |
31 | /// without updating graph deps like the base loader does. |
32 | struct 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 | |
50 | bool 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 | |
64 | MissingDependencyScannerDelegate::~MissingDependencyScannerDelegate() {} |
65 | |
66 | void 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 | |
72 | MissingDependencyScanner::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 | |
78 | void 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 | |
109 | void 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 | |
154 | void 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 | |
172 | bool 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 | |