| // Copyright 2011 Google Inc. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include "graph.h" |
| |
| #include <deque> |
| #include <unordered_set> |
| #include <assert.h> |
| #include <stdio.h> |
| |
| #include "build_log.h" |
| #include "debug_flags.h" |
| #include "depfile_parser.h" |
| #include "deps_log.h" |
| #include "disk_interface.h" |
| #include "metrics.h" |
| #include "parallel_map.h" |
| #include "state.h" |
| #include "util.h" |
| |
| bool Node::PrecomputeStat(DiskInterface* disk_interface, std::string* err) { |
| if (in_edge() != nullptr) { |
| if (in_edge()->IsPhonyOutput()) { |
| return true; |
| } |
| return (precomputed_mtime_ = disk_interface->LStat(globalPath().h.data(), nullptr, nullptr, err)) != -1; |
| } else { |
| return (precomputed_mtime_ = disk_interface->Stat(globalPath().h.data(), err)) != -1; |
| } |
| } |
| |
| bool Node::Stat(DiskInterface* disk_interface, string* err) { |
| if (in_edge() != nullptr) { |
| assert(!in_edge()->IsPhonyOutput()); |
| return (mtime_ = disk_interface->LStat(globalPath().h.data(), nullptr, nullptr, err)) != -1; |
| } else { |
| return (mtime_ = disk_interface->Stat(globalPath().h.data(), err)) != -1; |
| } |
| } |
| |
| void Node::UpdatePhonyMtime(TimeStamp mtime) { |
| if (!exists()) { |
| mtime_ = std::max(mtime_, mtime); |
| } |
| } |
| |
| bool Node::LStat( |
| DiskInterface* disk_interface, bool* is_dir, bool* is_symlink, string* err) { |
| assert(in_edge() != nullptr); |
| assert(!in_edge()->IsPhonyOutput()); |
| return (mtime_ = disk_interface->LStat(globalPath().h.data(), is_dir, is_symlink, err)) != -1; |
| } |
| |
| bool DependencyScan::RecomputeNodesDirty(const std::vector<Node*>& initial_nodes, |
| std::vector<Node*>* validation_nodes, |
| std::string* err) { |
| METRIC_RECORD("dep scan"); |
| std::vector<Node*> all_nodes; |
| std::vector<Edge*> all_edges; |
| std::unique_ptr<ThreadPool> thread_pool = CreateThreadPool(); |
| |
| { |
| METRIC_RECORD("dep scan : collect nodes+edges"); |
| for (Node* node : initial_nodes) |
| CollectPrecomputeLists(node, &all_nodes, &all_edges); |
| } |
| |
| bool success = true; |
| if (!PrecomputeNodesDirty(all_nodes, all_edges, thread_pool.get(), err)) |
| success = false; |
| |
| |
| std::deque<Node*> nodes(initial_nodes.begin(), initial_nodes.end()); |
| |
| if (success) { |
| METRIC_RECORD("dep scan : main pass"); |
| std::vector<Node*> stack; |
| std::vector<Node*> new_validation_nodes; |
| while (!nodes.empty()) { |
| Node* node = nodes.front(); |
| nodes.pop_front(); |
| |
| stack.clear(); |
| new_validation_nodes.clear(); |
| if (!RecomputeNodeDirty(node, &stack, &new_validation_nodes, err)) { |
| success = false; |
| break; |
| } |
| nodes.insert(nodes.end(), new_validation_nodes.begin(), |
| new_validation_nodes.end()); |
| if (!new_validation_nodes.empty()) { |
| assert(validation_nodes && |
| "validations require RecomputeDirty to be called with validation_nodes"); |
| validation_nodes->insert(validation_nodes->end(), |
| new_validation_nodes.begin(), |
| new_validation_nodes.end()); |
| } |
| } |
| } |
| |
| { |
| // Ensure that the precomputed mtime information can't be used after this |
| // dependency scan finishes. |
| METRIC_RECORD("dep scan : clear pre-stat"); |
| ParallelMap(thread_pool.get(), all_nodes, [](Node* node) { |
| node->ClearPrecomputedStat(); |
| }); |
| } |
| |
| return success; |
| } |
| |
| void DependencyScan::CollectPrecomputeLists(Node* node, |
| std::vector<Node*>* nodes, |
| std::vector<Edge*>* edges) { |
| if (node->precomputed_dirtiness()) |
| return; |
| node->set_precomputed_dirtiness(true); |
| nodes->push_back(node); |
| |
| Edge* edge = node->in_edge(); |
| if (edge && !edge->precomputed_dirtiness_) { |
| edge->precomputed_dirtiness_ = true; |
| edges->push_back(edge); |
| |
| for (Node* node : edge->inputs_) { |
| // Duplicate the dirtiness check here to avoid an unnecessary function |
| // call. (The precomputed_dirtiness() will be inlined, but the recursive |
| // call can't be.) |
| if (!node->precomputed_dirtiness()) |
| CollectPrecomputeLists(node, nodes, edges); |
| } |
| |
| if (!edge->validations_.empty()) { |
| for (Node* node : edge->validations_) { |
| // Duplicate the dirtiness check here to avoid an unnecessary function |
| // call. (The precomputed_dirtiness() will be inlined, but the recursive |
| // call can't be.) |
| if (!node->precomputed_dirtiness()) |
| CollectPrecomputeLists(node, nodes, edges); |
| } |
| } |
| } |
| |
| // Collect dependencies from the deps log. This pass could also examine |
| // depfiles, but it would be a more intrusive design change, because we don't |
| // want to parse a depfile twice. |
| if (DepsLog::Deps* deps = deps_log()->GetDeps(node)) { |
| for (int i = 0; i < deps->node_count; ++i) { |
| Node* node = deps->nodes[i]; |
| // Duplicate the dirtiness check here to avoid an unnecessary function |
| // call. |
| if (!node->precomputed_dirtiness()) { |
| CollectPrecomputeLists(node, nodes, edges); |
| } |
| } |
| } |
| } |
| |
| bool DependencyScan::PrecomputeNodesDirty(const std::vector<Node*>& nodes, |
| const std::vector<Edge*>& edges, |
| ThreadPool* thread_pool, |
| std::string* err) { |
| // Optimize the "null build" case by calling Stat in parallel on every node in |
| // the transitive closure. |
| // |
| // The Windows RealDiskInterface::Stat uses a directory-based cache that isn't |
| // thread-safe. Various tests also uses a non-thread-safe Stat, so disable the |
| // parallelized stat'ing for them as well. |
| if (disk_interface_->IsStatThreadSafe() && |
| GetOptimalThreadPoolJobCount() > 1) { |
| METRIC_RECORD("dep scan : pre-stat nodes"); |
| if (!PropagateError(err, ParallelMap(thread_pool, nodes, |
| [this](Node* node) { |
| // Each node is guaranteed to appear at most once in the collected list |
| // of nodes, so it's safe to modify the nodes from worker threads. |
| std::string err; |
| node->PrecomputeStat(disk_interface_, &err); |
| return err; |
| }))) { |
| return false; |
| } |
| } |
| |
| { |
| METRIC_RECORD("dep scan : precompute edge info"); |
| if (!PropagateError(err, ParallelMap(thread_pool, edges, [](Edge* edge) { |
| // As with the node list, each edge appears at most once in the |
| // collected list, so it's safe to modify the edges from worker threads. |
| std::string err; |
| edge->PrecomputeDepScanInfo(&err); |
| return err; |
| }))) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| bool DependencyScan::RecomputeNodeDirty(Node* node, std::vector<Node*>* stack, |
| std::vector<Node*>* validation_nodes, |
| std::string* err) { |
| Edge* edge = node->in_edge(); |
| if (!edge) { |
| // If we already visited this leaf node then we are done. |
| if (node->status_known()) |
| return true; |
| // This node has no in-edge; it is dirty if it is missing. |
| if (!node->StatIfNecessary(disk_interface_, err)) |
| return false; |
| if (!node->exists()) |
| EXPLAIN("%s has no in-edge and is missing", node->globalPath().h.data()); |
| node->set_dirty(!node->exists()); |
| return true; |
| } |
| |
| // If we already finished this edge then we are done. |
| if (edge->mark_ == Edge::VisitDone) |
| return true; |
| |
| // If we encountered this edge earlier in the call stack we have a cycle. |
| if (!VerifyDAG(node, stack, err)) |
| return false; |
| |
| // Mark the edge temporarily while in the call stack. |
| edge->mark_ = Edge::VisitInStack; |
| stack->push_back(node); |
| |
| bool dirty = false; |
| bool phony_output = edge->IsPhonyOutput(); |
| edge->outputs_ready_ = true; |
| edge->deps_missing_ = false; |
| |
| if (phony_output) { |
| EXPLAIN("edge with output %s is a phony output, so is always dirty", |
| node->globalPath().h.data()); |
| dirty = true; |
| |
| if (edge->UsesDepsLog() || edge->UsesDepfile()) { |
| *err = "phony output " + node->globalPath().h.str_view().AsString() + |
| " has deps, which does not make sense."; |
| return false; |
| } |
| } else { |
| if (!edge->deps_loaded_) { |
| // This is our first encounter with this edge. |
| // If there is a pending dyndep file, visit it now: |
| // * If the dyndep file is ready then load it now to get any |
| // additional inputs and outputs for this and other edges. |
| // Once the dyndep file is loaded it will no longer be pending |
| // if any other edges encounter it, but they will already have |
| // been updated. |
| // * If the dyndep file is not ready then since is known to be an |
| // input to this edge, the edge will not be considered ready below. |
| // Later during the build the dyndep file will become ready and be |
| // loaded to update this edge before it can possibly be scheduled. |
| if (edge->dyndep_ && edge->dyndep_->dyndep_pending()) { |
| if (!RecomputeDirty(edge->dyndep_, stack, err)) |
| return false; |
| |
| if (!edge->dyndep_->in_edge() || |
| edge->dyndep_->in_edge()->outputs_ready()) { |
| // The dyndep file is ready, so load it now. |
| if (!LoadDyndeps(edge->dyndep_, err)) |
| return false; |
| } |
| } |
| } |
| |
| // Load output mtimes so we can compare them to the most recent input below. |
| for (vector<Node*>::iterator o = edge->outputs_.begin(); |
| o != edge->outputs_.end(); ++o) { |
| if (!(*o)->StatIfNecessary(disk_interface_, err)) |
| return false; |
| } |
| |
| if (!edge->deps_loaded_) { |
| // This is our first encounter with this edge. Load discovered deps. |
| edge->deps_loaded_ = true; |
| if (!dep_loader_.LoadDeps(edge, err)) { |
| if (!err->empty()) |
| return false; |
| // Failed to load dependency info: rebuild to regenerate it. |
| // LoadDeps() did EXPLAIN() already, no need to do it here. |
| dirty = edge->deps_missing_ = true; |
| } |
| } |
| } |
| |
| // Store any validation nodes from the edge for adding to the initial |
| // nodes. Don't recurse into them, that would trigger the dependency |
| // cycle detector if the validation node depends on this node. |
| // RecomputeNodesDirty will add the validation nodes to the initial nodes |
| // and recurse into them. |
| validation_nodes->insert(validation_nodes->end(), |
| edge->validations_.begin(), edge->validations_.end()); |
| |
| // Visit all inputs; we're dirty if any of the inputs are dirty. |
| Node* most_recent_input = NULL; |
| for (vector<Node*>::iterator i = edge->inputs_.begin(); |
| i != edge->inputs_.end(); ++i) { |
| // Visit this input. |
| if (!RecomputeNodeDirty(*i, stack, validation_nodes, err)) |
| return false; |
| |
| // If an input is not ready, neither are our outputs. |
| Edge* in_edge = (*i)->in_edge(); |
| if (in_edge != nullptr) { |
| if (!in_edge->outputs_ready_) |
| edge->outputs_ready_ = false; |
| } |
| |
| if (!phony_output && !edge->is_order_only(i - edge->inputs_.begin())) { |
| if (in_edge != nullptr && in_edge->IsPhonyOutput()) { |
| *err = "real file '" + node->globalPath().h.str_view().AsString() + |
| "' depends on phony output '" + (*i)->globalPath().h.str_view().AsString() + "'\n"; |
| return false; |
| } |
| |
| // If a regular input is dirty (or missing), we're dirty. |
| // Otherwise consider mtime. |
| if ((*i)->dirty()) { |
| EXPLAIN("%s is dirty", (*i)->globalPath().h.data()); |
| dirty = true; |
| } else { |
| if (!most_recent_input || (*i)->mtime() > most_recent_input->mtime()) { |
| most_recent_input = *i; |
| } |
| } |
| } |
| } |
| |
| // We may also be dirty due to output state: missing outputs, out of |
| // date outputs, etc. Visit all outputs and determine whether they're dirty. |
| if (!dirty) |
| if (!RecomputeOutputsDirty(edge, most_recent_input, &dirty, err)) |
| return false; |
| |
| // Finally, visit each output and update their dirty state if necessary. |
| for (vector<Node*>::iterator o = edge->outputs_.begin(); |
| o != edge->outputs_.end(); ++o) { |
| if (dirty) |
| (*o)->MarkDirty(); |
| } |
| |
| // If an edge is dirty, its outputs are normally not ready. (It's |
| // possible to be clean but still not be ready in the presence of |
| // order-only inputs.) |
| // But phony edges with no inputs have nothing to do, so are always |
| // ready. |
| if (dirty && !(edge->is_phony() && edge->inputs_.empty())) |
| edge->outputs_ready_ = false; |
| |
| // Mark the edge as finished during this walk now that it will no longer |
| // be in the call stack. |
| edge->mark_ = Edge::VisitDone; |
| assert(stack->back() == node); |
| stack->pop_back(); |
| |
| return true; |
| } |
| |
| bool DependencyScan::VerifyDAG(Node* node, vector<Node*>* stack, string* err) { |
| Edge* edge = node->in_edge(); |
| assert(edge != NULL); |
| |
| // If we have no temporary mark on the edge then we do not yet have a cycle. |
| if (edge->mark_ != Edge::VisitInStack) |
| return true; |
| |
| // We have this edge earlier in the call stack. Find it. |
| vector<Node*>::iterator start = stack->begin(); |
| while (start != stack->end() && (*start)->in_edge() != edge) |
| ++start; |
| assert(start != stack->end()); |
| |
| // Make the cycle clear by reporting its start as the node at its end |
| // instead of some other output of the starting edge. For example, |
| // running 'ninja b' on |
| // build a b: cat c |
| // build c: cat a |
| // should report a -> c -> a instead of b -> c -> a. |
| *start = node; |
| |
| // Construct the error message rejecting the cycle. |
| *err = "dependency cycle: "; |
| for (vector<Node*>::const_iterator i = start; i != stack->end(); ++i) { |
| err->append((*i)->globalPath().h.data()); |
| err->append(" -> "); |
| } |
| err->append((*start)->globalPath().h.data()); |
| |
| if ((start + 1) == stack->end() && edge->maybe_phonycycle_diagnostic()) { |
| // The manifest parser would have filtered out the self-referencing |
| // input if it were not configured to allow the error. |
| err->append(" [-w phonycycle=err]"); |
| } |
| |
| return false; |
| } |
| |
| bool DependencyScan::RecomputeOutputsDirty(Edge* edge, Node* most_recent_input, |
| bool* outputs_dirty, string* err) { |
| assert(!edge->IsPhonyOutput()); |
| |
| uint64_t command_hash = edge->GetCommandHash(); |
| for (vector<Node*>::iterator o = edge->outputs_.begin(); |
| o != edge->outputs_.end(); ++o) { |
| if (edge->is_phony()) { |
| // Phony edges don't write any output. Outputs are only dirty if |
| // there are no inputs and we're missing the output. |
| if (edge->inputs_.empty() && !(*o)->exists()) { |
| // For phony targets defined in the ninja file, error when using dirty phony edges. |
| // The phony edges automatically created from depfiles still need the old behavior. |
| if (missing_phony_is_err_ && !edge->phony_from_depfile_) { |
| *err = "output " + (*o)->globalPath().h.str_view().AsString() + |
| " of phony edge doesn't exist. Missing 'phony_output = true'?"; |
| return false; |
| } else { |
| EXPLAIN("output %s of phony edge with no inputs doesn't exist", |
| (*o)->globalPath().h.data()); |
| *outputs_dirty = true; |
| return true; |
| } |
| } |
| |
| // Update the mtime with the newest input. Dependents can thus call mtime() |
| // on the fake node and get the latest mtime of the dependencies |
| if (most_recent_input) { |
| (*o)->UpdatePhonyMtime(most_recent_input->mtime()); |
| } |
| continue; |
| } |
| if (RecomputeOutputDirty(edge, most_recent_input, command_hash, *o)) { |
| *outputs_dirty = true; |
| return true; |
| } |
| } |
| return true; |
| } |
| |
| bool DependencyScan::RecomputeOutputDirty(Edge* edge, |
| Node* most_recent_input, |
| uint64_t command_hash, |
| Node* output) { |
| assert(!edge->is_phony()); |
| |
| BuildLog::LogEntry* entry = 0; |
| |
| // Dirty if we're missing the output. |
| if (!output->exists()) { |
| EXPLAIN("output %s doesn't exist", output->globalPath().h.data()); |
| return true; |
| } |
| |
| // Dirty if the output is older than the input. |
| if (most_recent_input && output->mtime() < most_recent_input->mtime()) { |
| TimeStamp output_mtime = output->mtime(); |
| |
| // If this is a restat rule, we may have cleaned the output with a restat |
| // rule in a previous run and stored the most recent input mtime in the |
| // build log. Use that mtime instead, so that the file will only be |
| // considered dirty if an input was modified since the previous run. |
| bool used_restat = false; |
| if (edge->IsRestat() && build_log() && |
| (entry = build_log()->LookupByOutput(output->globalPath()))) { |
| output_mtime = entry->mtime; |
| used_restat = true; |
| output->set_restat_mtime(output_mtime); |
| } |
| |
| if (output_mtime < most_recent_input->mtime()) { |
| EXPLAIN("%soutput %s older than most recent input %s " |
| "(%" PRId64 " vs %" PRId64 ")", |
| used_restat ? "restat of " : "", output->globalPath().h.data(), |
| most_recent_input->globalPath().h.data(), |
| output_mtime, most_recent_input->mtime()); |
| return true; |
| } |
| } |
| |
| if (build_log()) { |
| bool generator = edge->IsGenerator(); |
| if (entry || (entry = build_log()->LookupByOutput(output->globalPath()))) { |
| if (!generator && |
| command_hash != entry->command_hash) { |
| // May also be dirty due to the command changing since the last build. |
| // But if this is a generator rule, the command changing does not make us |
| // dirty. |
| EXPLAIN("command line changed for %s", output->globalPath().h.data()); |
| return true; |
| } |
| if (most_recent_input && entry->mtime < most_recent_input->mtime()) { |
| // May also be dirty due to the mtime in the log being older than the |
| // mtime of the most recent input. This can occur even when the mtime |
| // on disk is newer if a previous run wrote to the output file but |
| // exited with an error or was interrupted. |
| EXPLAIN("recorded mtime of %s older than most recent input %s (%" PRId64 " vs %" PRId64 ")", |
| output->globalPath().h.data(), most_recent_input->globalPath().h.data(), |
| entry->mtime, most_recent_input->mtime()); |
| return true; |
| } |
| } |
| if (!entry && !generator) { |
| EXPLAIN("command line not found in log for %s", output->globalPath().h.data()); |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| bool DependencyScan::LoadDyndeps(Node* node, string* err) const { |
| return dyndep_loader_.LoadDyndeps(node, err); |
| } |
| |
| bool DependencyScan::LoadDyndeps(Node* node, DyndepFile* ddf, |
| string* err) const { |
| return dyndep_loader_.LoadDyndeps(node, ddf, err); |
| } |
| |
| bool Edge::AllInputsReady() const { |
| for (vector<Node*>::const_iterator i = inputs_.begin(); |
| i != inputs_.end(); ++i) { |
| if ((*i)->in_edge() && !(*i)->in_edge()->outputs_ready()) |
| return false; |
| } |
| return true; |
| } |
| |
| static const HashedStrView kIn { "in" }; |
| static const HashedStrView kInNewline { "in_newline" }; |
| static const HashedStrView kOut { "out" }; |
| |
| bool EdgeEval::EvaluateVariable(std::string* out_append, |
| const HashedStrView& var, |
| Scope* target, |
| std::string* err) { |
| if (var == kIn || var == kInNewline) { |
| int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ - |
| edge_->order_only_deps_; |
| AppendPathList(out_append, |
| edge_->inputs_.begin(), |
| edge_->inputs_.begin() + explicit_deps_count, |
| var == kIn ? ' ' : '\n', target); |
| return true; |
| } else if (var == kOut) { |
| int explicit_outs_count = edge_->outputs_.size() - edge_->implicit_outs_; |
| AppendPathList(out_append, |
| edge_->outputs_.begin(), |
| edge_->outputs_.begin() + explicit_outs_count, |
| ' ', target); |
| return true; |
| } |
| |
| if (edge_->EvaluateVariableSelfOnly(out_append, var)) |
| return true; |
| |
| // Search for a matching rule binding. |
| if (const std::string* binding_pattern = edge_->rule().GetBinding(var)) { |
| // Detect recursive rule variable usage. |
| if (recursion_count_ == kEvalRecursionLimit) { |
| std::string cycle = recursion_vars_[0].AsString(); |
| for (int i = 1; i < kEvalRecursionLimit; ++i) { |
| cycle += " -> " + recursion_vars_[i].AsString(); |
| if (recursion_vars_[i] == recursion_vars_[0]) |
| break; |
| } |
| *err = "cycle in rule variables: " + cycle; |
| return false; |
| } |
| recursion_vars_[recursion_count_++] = var.str_view(); |
| |
| return EvaluateBindingOnRule(out_append, *binding_pattern, this, target, err); |
| } |
| |
| // Fall back to the edge's enclosing scope. |
| if (eval_phase_ == EdgeEval::kParseTime) { |
| Scope::EvaluateVariableAtPos(out_append, var, edge_->pos_.scope_pos()); |
| } else { |
| Scope::EvaluateVariable(out_append, var, edge_->pos_.scope()); |
| } |
| return true; |
| } |
| |
| void EdgeEval::AppendPathList(std::string* out_append, |
| std::vector<Node*>::iterator begin, |
| std::vector<Node*>::iterator end, |
| char sep, Scope* target) { |
| for (auto it = begin; it != end; ++it) { |
| if (it != begin) |
| out_append->push_back(sep); |
| |
| string path = (*it)->PathDecanonicalized(target); |
| if (escape_in_out_ == kShellEscape) { |
| #if _WIN32 |
| GetWin32EscapedString(path, out_append); |
| #else |
| GetShellEscapedString(path, out_append); |
| #endif |
| } else { |
| out_append->append(path); |
| } |
| } |
| } |
| |
| static const HashedStrView kCommand { "command" }; |
| static const HashedStrView kDepfile { "depfile" }; |
| static const HashedStrView kDyndep { "dyndep" }; |
| static const HashedStrView kRspfile { "rspfile" }; |
| static const HashedStrView kRspFileContent { "rspfile_content" }; |
| |
| bool Edge::EvaluateCommand(std::string* out_append, bool incl_rsp_file, |
| std::string* err) { |
| METRIC_RECORD("eval command"); |
| auto len_pre_chdir = out_append->size(); |
| if (!pos_.scope()->chdir().empty()) { |
| #ifdef _WIN32 |
| out_append->append(NINJA_WIN32_CD_DELIM); |
| out_append->append(pos_.scope()->chdir()); |
| out_append->append(NINJA_WIN32_CD_DELIM); |
| #else |
| out_append->append("cd \""); |
| out_append->append(pos_.scope()->chdir()); |
| out_append->append("\" && "); |
| #endif |
| } |
| auto len_post_chdir = out_append->size(); |
| if (!EvaluateVariable(out_append, kCommand, pos_.scope(), err)) |
| return false; |
| // out_append has the chdir in it, waiting, but the correct output |
| // is the empty string if EvaluateVariable() produced the empty string. |
| // In other words, clean up chdir if it's the only thing in out_append. |
| if (!pos_.scope()->chdir().empty() && out_append->size() == len_post_chdir) { |
| out_append->resize(len_pre_chdir); |
| } |
| |
| if (incl_rsp_file) { |
| std::string rspfile_content; |
| if (!EvaluateVariable(&rspfile_content, kRspFileContent, pos_.scope(), err)) |
| return false; |
| if (!rspfile_content.empty()) { |
| out_append->append(";rspfile="); |
| out_append->append(rspfile_content); |
| } |
| } |
| return true; |
| } |
| |
| void Edge::EvaluateCommand(EdgeCommand* out, bool incl_rsp_file) { |
| std::string err; |
| if (!EvaluateCommand(&out->command, incl_rsp_file, &err)) |
| Fatal("%s", err.c_str()); |
| out->use_console = use_console(); |
| out->env = cmdEnviron; |
| } |
| |
| static const HashedStrView kRestat { "restat" }; |
| static const HashedStrView kGenerator { "generator" }; |
| static const HashedStrView kDeps { "deps" }; |
| static const HashedStrView kPhonyOutput { "phony_output" }; |
| |
| bool Edge::PrecomputeDepScanInfo(std::string* err) { |
| if (dep_scan_info_.valid) |
| return true; |
| |
| // Precompute boolean flags. |
| auto get_bool_var = [this, err](const HashedStrView& var, |
| EdgeEval::EscapeKind escape, bool* out) { |
| std::string value; |
| if (!EvaluateVariable(&value, var, pos_.scope(), err, EdgeEval::kFinalScope, escape)) |
| return false; |
| *out = !value.empty(); |
| return true; |
| }; |
| if (!get_bool_var(kRestat, EdgeEval::kShellEscape, &dep_scan_info_.restat)) return false; |
| if (!get_bool_var(kGenerator, EdgeEval::kShellEscape, &dep_scan_info_.generator)) return false; |
| if (!get_bool_var(kDeps, EdgeEval::kShellEscape, &dep_scan_info_.deps)) return false; |
| if (!get_bool_var(kDepfile, EdgeEval::kDoNotEscape, &dep_scan_info_.depfile)) return false; |
| if (!get_bool_var(kPhonyOutput, EdgeEval::kShellEscape, &dep_scan_info_.phony_output)) return false; |
| |
| // Precompute the command hash. |
| std::string command; |
| if (!EvaluateCommand(&command, /*incl_rsp_file=*/true, err)) |
| return false; |
| dep_scan_info_.command_hash = BuildLog::LogEntry::HashCommand(command); |
| |
| dep_scan_info_.valid = true; |
| return true; |
| } |
| |
| /// Returns dependency-scanning info or exits with a fatal error. |
| const Edge::DepScanInfo& Edge::ComputeDepScanInfo() { |
| std::string err; |
| if (!PrecomputeDepScanInfo(&err)) |
| Fatal("%s", err.c_str()); |
| return dep_scan_info_; |
| } |
| |
| void Edge::SetRestat() { |
| std::string err; |
| if (!PrecomputeDepScanInfo(&err)) |
| Fatal("%s", err.c_str()); |
| dep_scan_info_.restat = true; |
| } |
| |
| bool Edge::EvaluateVariable(std::string* out_append, const HashedStrView& key, |
| Scope* target, std::string* err, |
| EdgeEval::EvalPhase phase, |
| EdgeEval::EscapeKind escape) { |
| EdgeEval eval(this, phase, escape); |
| return eval.EvaluateVariable(out_append, key, target, err); |
| } |
| |
| std::string Edge::GetBindingImpl(const HashedStrView& key, |
| EdgeEval::EvalPhase phase, |
| EdgeEval::EscapeKind escape) { |
| std::string result; |
| std::string err; |
| if (!EvaluateVariable(&result, key, pos_.scope(), &err, phase, escape)) |
| Fatal("%s", err.c_str()); |
| return result; |
| } |
| |
| std::string Edge::GetBinding(const HashedStrView& key) { |
| return GetBindingImpl(key, EdgeEval::kFinalScope, EdgeEval::kShellEscape); |
| } |
| |
| std::string Edge::GetUnescapedDepfile() { |
| return GetBindingImpl(kDepfile, EdgeEval::kFinalScope, EdgeEval::kDoNotEscape); |
| } |
| |
| std::string Edge::GetUnescapedDyndep() { |
| return GetBindingImpl(kDyndep, EdgeEval::kFinalScope, EdgeEval::kDoNotEscape); |
| } |
| |
| std::string Edge::GetUnescapedRspfile() { |
| return GetBindingImpl(kRspfile, EdgeEval::kFinalScope, EdgeEval::kDoNotEscape); |
| } |
| |
| void Edge::Dump(const char* prefix) const { |
| printf("%s[ ", prefix); |
| for (vector<Node*>::const_iterator i = inputs_.begin(); |
| i != inputs_.end() && *i != NULL; ++i) { |
| printf("%s ", (*i)->path().c_str()); |
| } |
| printf("--%s-> ", rule_->name().c_str()); |
| for (vector<Node*>::const_iterator i = outputs_.begin(); |
| i != outputs_.end() && *i != NULL; ++i) { |
| printf("%s ", (*i)->path().c_str()); |
| } |
| if (!validations_.empty()) { |
| printf(" validations "); |
| for (vector<Node*>::const_iterator i = validations_.begin(); |
| i != validations_.end() && *i != NULL; ++i) { |
| printf("%s ", (*i)->path().c_str()); |
| } |
| } |
| if (pool_) { |
| if (!pool_->name().empty()) { |
| printf("(in pool '%s')", pool_->name().c_str()); |
| } |
| } else { |
| printf("(null pool?)"); |
| } |
| printf("] 0x%p\n", this); |
| } |
| |
| bool Edge::is_phony() const { |
| return rule_ == &State::kPhonyRule; |
| } |
| |
| bool Edge::use_console() const { |
| return pool() == &State::kConsolePool; |
| } |
| |
| bool Edge::maybe_phonycycle_diagnostic() const { |
| // CMake 2.8.12.x and 3.0.x produced self-referencing phony rules |
| // of the form "build a: phony ... a ...". Restrict our |
| // "phonycycle" diagnostic option to the form it used. |
| return is_phony() && outputs_.size() == 1 && implicit_outs_ == 0 && |
| implicit_deps_ == 0 && order_only_deps_ == 0; |
| } |
| |
| bool Edge::EvaluateVariableSelfOnly(std::string* out_append, |
| const HashedStrView& var) const { |
| // ninja allows declaring the same binding repeatedly on an edge. Use the |
| // last matching binding. |
| const auto it_end = unevaled_bindings_.rend(); |
| for (auto it = unevaled_bindings_.rbegin(); it != it_end; ++it) { |
| if (var == it->first) { |
| EvaluateBindingInScope(out_append, it->second, pos_.scope_pos()); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // static |
| string Node::PathDecanonicalized(const string& path, uint64_t slash_bits) { |
| string result = path; |
| #ifdef _WIN32 |
| uint64_t mask = 1; |
| for (char* c = &result[0]; (c = strchr(c, '/')) != NULL;) { |
| if (slash_bits & mask) |
| *c = '\\'; |
| c++; |
| mask <<= 1; |
| } |
| #endif |
| return result; |
| } |
| |
| Node::~Node() { |
| EdgeList* node = out_edges_.load(); |
| while (node != nullptr) { |
| EdgeList* next = node->next; |
| delete node; |
| node = next; |
| } |
| } |
| |
| // Does the node have at least one out edge? |
| bool Node::has_out_edge() const { |
| return out_edges_.load() != nullptr; |
| } |
| |
| std::vector<Edge*> Node::GetOutEdges() const { |
| // Include out-edges from the manifest. |
| std::vector<Edge*> result; |
| for (EdgeList* node = out_edges_.load(); node != nullptr; node = node->next) { |
| result.push_back(node->edge); |
| } |
| std::sort(result.begin(), result.end(), EdgeCmp()); |
| |
| // Add extra out-edges from depfiles and the deps log. Preserve the order |
| // of these extra edges; don't sort them. |
| std::copy(dep_scan_out_edges_.begin(), dep_scan_out_edges_.end(), |
| std::back_inserter(result)); |
| |
| return result; |
| } |
| |
| std::vector<Edge*> Node::GetValidationOutEdges() const { |
| std::vector<Edge*> result; |
| for (EdgeList* node = validation_out_edges_.load(); node != nullptr; node = node->next) { |
| result.push_back(node->edge); |
| } |
| std::sort(result.begin(), result.end(), EdgeCmp()); |
| |
| return result; |
| } |
| |
| std::vector<Edge*> Node::GetAllOutEdges() const { |
| std::vector<Edge*> result = this->GetOutEdges(); |
| std::vector<Edge*> extra = this->GetValidationOutEdges(); |
| if (!extra.empty()) { |
| result.insert(result.end(), extra.begin(), extra.end()); |
| } |
| return result; |
| } |
| |
| void Node::AddOutEdge(Edge* edge) { |
| EdgeList* new_node = new EdgeList { edge }; |
| while (true) { |
| EdgeList* cur_head = out_edges_.load(); |
| new_node->next = cur_head; |
| if (out_edges_.compare_exchange_weak(cur_head, new_node)) |
| break; |
| } |
| } |
| |
| void Node::AddValidationOutEdge(Edge* edge) { |
| EdgeList* new_node = new EdgeList { edge }; |
| while (true) { |
| EdgeList* cur_head = validation_out_edges_.load(); |
| new_node->next = cur_head; |
| if (validation_out_edges_.compare_exchange_weak(cur_head, new_node)) |
| break; |
| } |
| } |
| |
| void Node::Dump(const char* prefix) const { |
| printf("%s <%s 0x%p> mtime: %" PRId64 "%s, (:%s), ", |
| prefix, path().c_str(), this, |
| mtime(), mtime() ? "" : " (:missing)", |
| dirty() ? " dirty" : " clean"); |
| if (in_edge()) { |
| in_edge()->Dump("in-edge: "); |
| } else { |
| printf("no in-edge\n"); |
| } |
| printf(" out edges:\n"); |
| const std::vector<Edge*> out_edges = GetOutEdges(); |
| for (vector<Edge*>::const_iterator e = out_edges.begin(); |
| e != out_edges.end() && *e != NULL; ++e) { |
| (*e)->Dump(" +- "); |
| } |
| const std::vector<Edge*> validation_out_edges = GetValidationOutEdges(); |
| if (!validation_out_edges.empty()) { |
| printf(" validation out edges:\n"); |
| for (vector<Edge*>::const_iterator e = validation_out_edges.begin(); |
| e != validation_out_edges.end() && *e != NULL; ++e) { |
| (*e)->Dump(" +- "); |
| } |
| } |
| } |
| |
| GlobalPathStr Node::globalPath() { |
| return scope_->GlobalPath(path_); |
| } |
| |
| static void GetDependencyPathsDfs(Node* node, Node* out, |
| DepPath& path_till_here, |
| std::unordered_set<Node*>& dead_ends, |
| std::vector<DepPath>& output) { |
| if (node == out) { |
| path_till_here.push_back(node); |
| output.push_back(path_till_here); |
| path_till_here.pop_back(); |
| return; |
| } |
| |
| if (dead_ends.find(node) != dead_ends.end()) |
| return; |
| const size_t result_count = output.size(); |
| |
| path_till_here.push_back(node); |
| node->set_dirty(true); |
| for (Edge* edge : node->GetAllOutEdges()) { |
| for (Node* next : edge->outputs_) { |
| if (!next->dirty()) { |
| GetDependencyPathsDfs(next, out, path_till_here, dead_ends, output); |
| } |
| } |
| } |
| node->set_dirty(false); |
| path_till_here.pop_back(); |
| |
| if (output.size() == result_count) { |
| // There are no paths from `node` to `out`, so skip `node` for the rest of |
| // the search. |
| dead_ends.insert(node); |
| } |
| } |
| |
| std::vector<DepPath> GetDependencyPaths(Node* in, Node* out) { |
| assert(in != nullptr && out != nullptr); |
| std::unordered_set<Node*> dead_ends; |
| std::vector<DepPath> result; |
| DepPath path_till_here; |
| GetDependencyPathsDfs(in, out, path_till_here, dead_ends, result); |
| return result; |
| } |
| |
| bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) { |
| if (edge->UsesDepsLog()) |
| return LoadDepsFromLog(edge, err); |
| |
| if (edge->UsesDepfile()) { |
| std::string depfile = edge->GetUnescapedDepfile(); |
| assert(!depfile.empty() && |
| "UsesDepfile was set, so the depfile should be non-empty"); |
| return LoadDepFile(edge, depfile, err); |
| } |
| |
| // No deps to load. |
| return true; |
| } |
| |
| bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path, |
| string* err) { |
| METRIC_RECORD("depfile load"); |
| // Read depfile content. Treat a missing depfile as empty. |
| string content; |
| switch (disk_interface_->ReadFile(path, &content, err)) { |
| case DiskInterface::Okay: |
| break; |
| case DiskInterface::NotFound: |
| err->clear(); |
| break; |
| case DiskInterface::OtherError: |
| *err = "loading '" + path + "': " + *err; |
| return false; |
| } |
| // On a missing depfile: return false and empty *err. |
| if (content.empty()) { |
| EXPLAIN("depfile '%s' is missing", path.c_str()); |
| return false; |
| } |
| |
| DepfileParser depfile(depfile_parser_options_ |
| ? *depfile_parser_options_ |
| : DepfileParserOptions()); |
| string depfile_err; |
| string depfile_warn; |
| if (!depfile.Parse(&content, &depfile_warn, &depfile_err)) { |
| *err = path + ": " + depfile_err; |
| return false; |
| } |
| |
| if (!depfile_warn.empty()) { |
| Warning("%s: %s", path.c_str(), depfile_warn.c_str()); |
| } |
| |
| uint64_t unused; |
| if (!CanonicalizePath(const_cast<char*>(depfile.out_.str_), |
| &depfile.out_.len_, &unused, err)) { |
| *err = path + ": " + *err; |
| return false; |
| } |
| |
| // Check that this depfile matches the edge's output, if not return false to |
| // mark the edge as dirty. |
| Node* first_output = edge->outputs_[0]; |
| if (first_output->path() != depfile.out_) { |
| EXPLAIN("expected depfile '%s' to mention '%s', got '%s'", path.c_str(), |
| first_output->path().c_str(), depfile.out_.AsString().c_str()); |
| return false; |
| } |
| |
| // Preallocate space in edge->inputs_ to be filled in below. |
| vector<Node*>::iterator implicit_dep = |
| PreallocateSpace(edge, depfile.ins_.size()); |
| |
| // Add all its in-edges. |
| for (vector<StringPiece>::iterator i = depfile.ins_.begin(); |
| i != depfile.ins_.end(); ++i, ++implicit_dep) { |
| uint64_t slash_bits; |
| if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits, |
| err)) |
| return false; |
| |
| Node* node = state_->GetNode(edge->pos_.scope()->GlobalPath(*i), |
| slash_bits); |
| *implicit_dep = node; |
| node->AddOutEdgeDepScan(edge); |
| CreatePhonyInEdge(node); |
| } |
| |
| return true; |
| } |
| |
| bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, string* err) { |
| // NOTE: deps are only supported for single-target edges. |
| Node* output = edge->outputs_[0]; |
| DepsLog::Deps* deps = deps_log_->GetDeps(output); |
| if (!deps) { |
| EXPLAIN("deps for '%s' are missing", output->path().c_str()); |
| return false; |
| } |
| |
| // Deps are invalid if the output is newer than the deps. |
| if (output->mtime() > deps->mtime) { |
| EXPLAIN("stored deps info out of date for '%s' (%" PRId64 " vs %" PRId64 ")", |
| output->path().c_str(), deps->mtime, output->mtime()); |
| return false; |
| } |
| |
| vector<Node*>::iterator implicit_dep = |
| PreallocateSpace(edge, deps->node_count); |
| for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) { |
| Node* node = deps->nodes[i]; |
| *implicit_dep = node; |
| node->AddOutEdgeDepScan(edge); |
| CreatePhonyInEdge(node); |
| } |
| return true; |
| } |
| |
| vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge, |
| int count) { |
| edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_, |
| (size_t)count, 0); |
| edge->implicit_deps_ += count; |
| return edge->inputs_.end() - edge->order_only_deps_ - count; |
| } |
| |
| void ImplicitDepLoader::CreatePhonyInEdge(Node* node) { |
| if (node->in_edge()) |
| return; |
| |
| Edge* phony_edge = state_->AddEdge(&State::kPhonyRule); |
| node->set_in_edge(phony_edge); |
| phony_edge->outputs_.push_back(node); |
| ++phony_edge->explicit_outs_; |
| |
| // RecomputeDirty might not be called for phony_edge if a previous call |
| // to RecomputeDirty had caused the file to be stat'ed. Because previous |
| // invocations of RecomputeDirty would have seen this node without an |
| // input edge (and therefore ready), we have to set outputs_ready_ to true |
| // to avoid a potential stuck build. If we do call RecomputeDirty for |
| // this node, it will simply set outputs_ready_ to the correct value. |
| phony_edge->outputs_ready_ = true; |
| |
| phony_edge->phony_from_depfile_ = true; |
| } |
