| // Copyright 2018 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 "manifest_parser.h" |
| |
| #include <assert.h> |
| |
| #include <unordered_map> |
| #include <vector> |
| |
| #include "disk_interface.h" |
| #include "eval_env.h" |
| #include "lexer.h" |
| #include "metrics.h" |
| #include "parallel_map.h" |
| #include "state.h" |
| #include "util.h" |
| #include "version.h" |
| #include "manifest_chunk_parser.h" |
| |
| using manifest_chunk::Clump; |
| using manifest_chunk::DefaultTarget; |
| using manifest_chunk::Include; |
| using manifest_chunk::ParserItem; |
| using manifest_chunk::RequiredVersion; |
| |
| namespace { |
| |
| static bool DecorateError(const LoadedFile& file, size_t file_offset, |
| const std::string& message, std::string* err) { |
| assert(file_offset <= file.content().size()); |
| return DecorateErrorWithLocation(file.filename(), file.content().data(), |
| file_offset, message, err); |
| } |
| |
| /// Split a single manifest file into chunks, parse the chunks in parallel, and |
| /// return the resulting parser output. |
| static std::vector<ParserItem> ParseManifestChunks(const LoadedFile& file, |
| ThreadPool* thread_pool) { |
| std::vector<ParserItem> result; |
| const std::vector<StringPiece> chunk_views = |
| manifest_chunk::SplitManifestIntoChunks(file.content_with_nul()); |
| |
| METRIC_RECORD(".ninja load : parse chunks"); |
| |
| for (std::vector<ParserItem>& chunk_items : |
| ParallelMap(thread_pool, chunk_views, [&file](StringPiece view) { |
| std::vector<ParserItem> chunk_items; |
| manifest_chunk::ParseChunk(file, view, &chunk_items); |
| return chunk_items; |
| })) { |
| std::move(chunk_items.begin(), chunk_items.end(), |
| std::back_inserter(result)); |
| } |
| return result; |
| } |
| |
| static void ReserveSpaceInScopeTables(Scope* scope, |
| const std::vector<ParserItem>& items) { |
| // Reserve extra space in the scope's bindings/rules hash tables. |
| METRIC_RECORD(".ninja load : alloc scope tables"); |
| size_t new_bindings = 0; |
| size_t new_rules = 0; |
| for (const auto& item : items) { |
| if (item.kind == ParserItem::kClump) { |
| Clump* clump = item.u.clump; |
| new_bindings += clump->bindings_.size(); |
| new_rules += clump->rules_.size(); |
| } |
| } |
| scope->ReserveTableSpace(new_bindings, new_rules); |
| } |
| |
| struct ManifestFileSet { |
| ManifestFileSet(FileReader* file_reader) : file_reader_(file_reader) {} |
| |
| bool LoadFile(const std::string& filename, const LoadedFile** result, |
| std::string* err); |
| |
| ~ManifestFileSet() { |
| // It can take a surprising long time to unmap all the manifest files |
| // (e.g. ~70 ms for Android, 25 ms for Chromium). |
| METRIC_RECORD(".ninja load : unload files"); |
| loaded_files_.clear(); |
| } |
| |
| private: |
| FileReader *file_reader_ = nullptr; |
| |
| /// Keep all the manifests in memory until all the manifest parsing work is |
| /// complete, because intermediate parsing results (i.e. StringPiece) may |
| /// point into the loaded files. |
| std::vector<std::unique_ptr<LoadedFile>> loaded_files_; |
| }; |
| |
| bool ManifestFileSet::LoadFile(const std::string& filename, |
| const LoadedFile** result, |
| std::string* err) { |
| std::unique_ptr<LoadedFile> loaded_file; |
| if (file_reader_->LoadFile(filename, &loaded_file, err) != FileReader::Okay) { |
| *err = "loading '" + filename + "': " + *err; |
| return false; |
| } |
| loaded_files_.push_back(std::move(loaded_file)); |
| *result = loaded_files_.back().get(); |
| return true; |
| } |
| |
| struct DfsParser { |
| DfsParser(ManifestFileSet* file_set, State* state, ThreadPool* thread_pool) |
| : file_set_(file_set), state_(state), thread_pool_(thread_pool) {} |
| |
| private: |
| void HandleRequiredVersion(const RequiredVersion& item, Scope* scope); |
| bool HandleInclude(const Include& item, const LoadedFile& file, Scope* scope, |
| const LoadedFile** child_file, Scope** child_scope, |
| std::string* err); |
| bool HandlePool(Pool* pool, const LoadedFile& file, std::string* err); |
| bool HandleClump(Clump* clump, const LoadedFile& file, Scope* scope, |
| std::string* err); |
| |
| public: |
| /// Load the tree of manifest files and do initial parsing of all the chunks. |
| /// This function always runs on the main thread. |
| bool LoadManifestTree(const LoadedFile& file, Scope* scope, |
| std::vector<Clump*>* out_clumps, std::string* err); |
| |
| private: |
| ManifestFileSet* file_set_; |
| State* state_; |
| ThreadPool* thread_pool_; |
| }; |
| |
| void DfsParser::HandleRequiredVersion(const RequiredVersion& item, |
| Scope* scope) { |
| std::string version; |
| EvaluateBindingInScope(&version, item.version_, |
| scope->GetCurrentEndOfScope()); |
| CheckNinjaVersion(version); |
| } |
| |
| bool DfsParser::HandleInclude(const Include& include, const LoadedFile& file, |
| Scope* scope, const LoadedFile** child_file, |
| Scope** child_scope, std::string* err) { |
| std::string path; |
| EvaluatePathInScope(&path, include.path_, scope->GetCurrentEndOfScope()); |
| if (!file_set_->LoadFile(path, child_file, err)) { |
| return DecorateError(file, include.diag_pos_, std::string(*err), err); |
| } |
| if (include.new_scope_) { |
| *child_scope = new Scope(scope->GetCurrentEndOfScope()); |
| } else { |
| *child_scope = scope; |
| } |
| return true; |
| } |
| |
| bool DfsParser::HandlePool(Pool* pool, const LoadedFile& file, |
| std::string* err) { |
| std::string depth_string; |
| EvaluateBindingInScope(&depth_string, pool->parse_state_.depth, |
| pool->pos_.scope_pos()); |
| pool->depth_ = atol(depth_string.c_str()); |
| if (pool->depth_ < 0) { |
| return DecorateError(file, pool->parse_state_.depth_diag_pos, |
| "invalid pool depth", err); |
| } |
| if (!state_->AddPool(pool)) { |
| return DecorateError(file, pool->parse_state_.pool_name_diag_pos, |
| "duplicate pool '" + pool->name() + "'", err); |
| } |
| return true; |
| } |
| |
| bool DfsParser::HandleClump(Clump* clump, const LoadedFile& file, Scope* scope, |
| std::string* err) { |
| METRIC_RECORD(".ninja load : scope setup"); |
| // Allocate DFS and scope positions for the clump. |
| clump->pos_.scope = scope->AllocDecls(clump->decl_count()); |
| clump->pos_.dfs_location = state_->AllocDfsLocation(clump->decl_count()); |
| { |
| METRIC_RECORD(".ninja load : scope setup : bindings"); |
| for (Binding* binding : clump->bindings_) { |
| scope->AddBinding(binding); |
| } |
| } |
| { |
| METRIC_RECORD(".ninja load : scope setup : rules"); |
| for (Rule* rule : clump->rules_) { |
| if (!scope->AddRule(rule)) { |
| return DecorateError(file, rule->parse_state_.rule_name_diag_pos, |
| "duplicate rule '" + rule->name() + "'", err); |
| } |
| } |
| } |
| for (Pool* pool : clump->pools_) { |
| if (!HandlePool(pool, file, err)) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| bool DfsParser::LoadManifestTree(const LoadedFile& file, Scope* scope, |
| std::vector<Clump*>* out_clumps, |
| std::string* err) { |
| std::vector<ParserItem> items = ParseManifestChunks(file, thread_pool_); |
| ReserveSpaceInScopeTables(scope, items); |
| |
| // With the chunks parsed, do a depth-first parse of the ninja manifest using |
| // the results of the parallel parse. |
| for (const auto& item : items) { |
| switch (item.kind) { |
| case ParserItem::kError: |
| *err = item.u.error->msg_; |
| return false; |
| |
| case ParserItem::kRequiredVersion: |
| HandleRequiredVersion(*item.u.required_version, scope); |
| break; |
| |
| case ParserItem::kInclude: { |
| const Include& include = *item.u.include; |
| const LoadedFile* child_file = nullptr; |
| Scope* child_scope = nullptr; |
| if (!HandleInclude(include, file, scope, &child_file, &child_scope, err)) |
| return false; |
| if (!LoadManifestTree(*child_file, child_scope, out_clumps, err)) |
| return false; |
| break; |
| } |
| |
| case ParserItem::kClump: |
| if (!HandleClump(item.u.clump, file, scope, err)) |
| return false; |
| out_clumps->push_back(item.u.clump); |
| break; |
| |
| default: |
| assert(false && "unrecognized kind of ParserItem"); |
| abort(); |
| } |
| } |
| |
| return true; |
| } |
| |
| /// Parse an edge's path and add it to a vector on the Edge object. |
| static inline bool AddPathToEdge(State* state, const Edge& edge, |
| std::vector<Node*>* out_vec, |
| const LoadedFile& file, Lexer& lexer, |
| std::string* err) { |
| HashedStrView key; |
| uint64_t slash_bits = 0; |
| |
| StringPiece canon_path = lexer.PeekCanonicalPath(); |
| if (!canon_path.empty()) { |
| key = canon_path; |
| } else { |
| LexedPath path; |
| if (!lexer.ReadPath(&path, err) || path.str_.empty()) { |
| assert(false && "manifest file apparently changed during parsing"); |
| abort(); |
| } |
| |
| thread_local std::string tls_work_buf; |
| std::string& work_buf = tls_work_buf; |
| work_buf.clear(); |
| EvaluatePathOnEdge(&work_buf, path, edge); |
| |
| std::string path_err; |
| if (!CanonicalizePath(&work_buf, &slash_bits, &path_err)) { |
| return DecorateError(file, edge.parse_state_.final_diag_pos, path_err, |
| err); |
| } |
| key = work_buf; |
| } |
| |
| Node* node = state->GetNode(key, 0); |
| node->UpdateFirstReference(edge.dfs_location(), slash_bits); |
| out_vec->push_back(node); |
| return true; |
| } |
| |
| static const HashedStrView kPool { "pool" }; |
| static const HashedStrView kDeps { "deps" }; |
| static const HashedStrView kDyndep { "dyndep" }; |
| |
| struct ManifestLoader { |
| private: |
| State* const state_ = nullptr; |
| ThreadPool* const thread_pool_ = nullptr; |
| const ManifestParserOptions options_; |
| const bool quiet_ = false; |
| |
| bool AddEdgeToGraph(Edge* edge, const LoadedFile& file, std::string* err); |
| |
| /// This function runs on a worker thread and adds a clump's declarations to |
| /// the build graph. |
| bool FinishAddingClumpToGraph(Clump* clump, std::string* err); |
| |
| bool FinishLoading(const std::vector<Clump*>& clumps, std::string* err); |
| |
| public: |
| ManifestLoader(State* state, ThreadPool* thread_pool, |
| ManifestParserOptions options, bool quiet) |
| : state_(state), thread_pool_(thread_pool), options_(options), |
| quiet_(quiet) {} |
| |
| bool Load(ManifestFileSet* file_set, const LoadedFile& root_manifest, |
| std::string* err); |
| }; |
| |
| bool ManifestLoader::AddEdgeToGraph(Edge* edge, const LoadedFile& file, |
| std::string* err) { |
| |
| const ScopePosition edge_pos = edge->pos_.scope_pos(); |
| |
| // Look up the edge's rule. |
| edge->rule_ = Scope::LookupRuleAtPos(edge->parse_state_.rule_name, edge_pos); |
| if (edge->rule_ == nullptr) { |
| std::string msg = "unknown build rule '" + |
| edge->parse_state_.rule_name.AsString() + "'"; |
| return DecorateError(file, edge->parse_state_.rule_name_diag_pos, msg, err); |
| } |
| |
| // Now that the edge's bindings are available, check whether the edge has a |
| // pool. This check requires the full edge+rule evaluation system. |
| std::string pool_name; |
| if (!edge->EvaluateVariable(&pool_name, kPool, err, EdgeEval::kParseTime)) |
| return false; |
| if (pool_name.empty()) { |
| edge->pool_ = &State::kDefaultPool; |
| } else { |
| edge->pool_ = state_->LookupPoolAtPos(pool_name, edge->pos_.dfs_location()); |
| if (edge->pool_ == nullptr) { |
| return DecorateError(file, edge->parse_state_.final_diag_pos, |
| "unknown pool name '" + pool_name + "'", err); |
| } |
| } |
| |
| edge->outputs_.reserve(edge->explicit_outs_ + edge->implicit_outs_); |
| edge->inputs_.reserve(edge->explicit_deps_ + edge->implicit_deps_ + |
| edge->order_only_deps_); |
| edge->validations_.reserve(edge->validation_deps_); |
| |
| // Add the input and output nodes. We already lexed them in the first pass, |
| // but we couldn't add them because scope bindings weren't available. To save |
| // memory, the first pass only recorded the lexer position of each category |
| // of input/output nodes, rather than each path's location. |
| Lexer lexer(file.filename(), file.content(), file.content().data()); |
| for (const Edge::DeferredPathList& path_list : |
| edge->parse_state_.deferred_path_lists) { |
| std::vector<Node*>* vec = |
| path_list.type == Edge::DeferredPathList::INPUT ? &edge->inputs_ : |
| path_list.type == Edge::DeferredPathList::OUTPUT ? &edge->outputs_ : |
| &edge->validations_; |
| lexer.ResetPos(path_list.lexer_pos); |
| for (int i = 0; i < path_list.count; ++i) { |
| if (!AddPathToEdge(state_, *edge, vec, file, lexer, err)) |
| return false; |
| } |
| // Verify that there are no more paths to parse. |
| LexedPath path; |
| if (!lexer.ReadPath(&path, err) || !path.str_.empty()) { |
| assert(false && "manifest file apparently changed during parsing"); |
| abort(); |
| } |
| } |
| |
| // This compatibility mode filters nodes from the edge->inputs_ list; do it |
| // before linking the edge inputs and nodes. |
| if (options_.phony_cycle_action_ == kPhonyCycleActionWarn && |
| edge->maybe_phonycycle_diagnostic()) { |
| // CMake 2.8.12.x and 3.0.x incorrectly write phony build statements that |
| // reference themselves. Ninja used to tolerate these in the build graph |
| // but that has since been fixed. Filter them out to support users of those |
| // old CMake versions. |
| Node* out = edge->outputs_[0]; |
| std::vector<Node*>::iterator new_end = |
| std::remove(edge->inputs_.begin(), edge->inputs_.end(), out); |
| if (new_end != edge->inputs_.end()) { |
| edge->inputs_.erase(new_end, edge->inputs_.end()); |
| --edge->explicit_deps_; |
| if (!quiet_) { |
| Warning("phony target '%s' names itself as an input; ignoring " |
| "[-w phonycycle=warn]", out->path().c_str()); |
| } |
| } |
| } |
| |
| // Multiple outputs aren't (yet?) supported with depslog. |
| std::string deps_type; |
| if (!edge->EvaluateVariable(&deps_type, kDeps, err, EdgeEval::kParseTime)) |
| return false; |
| if (!deps_type.empty() && edge->outputs_.size() - edge->implicit_outs_ > 1) { |
| return DecorateError(file, edge->parse_state_.final_diag_pos, |
| "multiple outputs aren't (yet?) supported by depslog; " |
| "bring this up on the mailing list if it affects you", |
| err); |
| } |
| |
| // Lookup, validate, and save any dyndep binding. It will be used later |
| // to load generated dependency information dynamically, but it must |
| // be one of our manifest-specified inputs. |
| std::string dyndep; |
| if (!edge->EvaluateVariable(&dyndep, kDyndep, err, EdgeEval::kParseTime)) |
| return false; |
| if (!dyndep.empty()) { |
| uint64_t slash_bits; |
| if (!CanonicalizePath(&dyndep, &slash_bits, err)) |
| return false; |
| edge->dyndep_ = state_->GetNode(dyndep, 0); |
| edge->dyndep_->set_dyndep_pending(true); |
| vector<Node*>::iterator dgi = |
| std::find(edge->inputs_.begin(), edge->inputs_.end(), edge->dyndep_); |
| if (dgi == edge->inputs_.end()) { |
| return DecorateError(file, edge->parse_state_.final_diag_pos, |
| "dyndep '" + dyndep + "' is not an input", err); |
| } |
| } |
| |
| return true; |
| } |
| |
| bool ManifestLoader::FinishAddingClumpToGraph(Clump* clump, std::string* err) { |
| std::string work_buf; |
| |
| // Precompute all binding values. Discard each evaluated string -- we just |
| // need to make sure each binding's value isn't coming from the mmap'ed |
| // manifest anymore. |
| for (Binding* binding : clump->bindings_) { |
| work_buf.clear(); |
| binding->Evaluate(&work_buf); |
| } |
| |
| for (Edge* edge : clump->edges_) { |
| if (!AddEdgeToGraph(edge, clump->file_, err)) |
| return false; |
| } |
| |
| return true; |
| } |
| |
| bool ManifestLoader::FinishLoading(const std::vector<Clump*>& clumps, |
| std::string* err) { |
| { |
| // Most of this pass's time is spent adding the edges. (i.e. The time spent |
| // evaluating the bindings is negligible.) |
| METRIC_RECORD(".ninja load : edge setup"); |
| |
| size_t output_count = 0; |
| for (Clump* clump : clumps) |
| output_count += clump->edge_output_count_; |
| |
| // Construct the initial graph of input/output nodes. Select an initial size |
| // that's likely to keep the number of collisions low. The number of edges' |
| // non-implicit outputs is a decent enough proxy for the final number of |
| // nodes. (I see acceptable performance even with a much lower number of |
| // buckets, e.g. 100 times fewer.) |
| state_->paths_.reserve(state_->paths_.size() + output_count * 3); |
| |
| if (!PropagateError(err, ParallelMap(thread_pool_, clumps, |
| [this](Clump* clump) { |
| std::string err; |
| FinishAddingClumpToGraph(clump, &err); |
| return err; |
| }))) { |
| return false; |
| } |
| } |
| { |
| // Record the in-edge for each node that's built by an edge. Detect |
| // duplicate edges. |
| // |
| // With dupbuild=warn (the default until 1.9.0), when two edges generate the |
| // same node, remove the duplicate node from the output list of the later |
| // edge. If all of an edge's outputs are removed, remove the edge from the |
| // graph. |
| METRIC_RECORD(".ninja load : link edge outputs"); |
| for (Clump* clump : clumps) { |
| for (size_t edge_idx = 0; edge_idx < clump->edges_.size(); ) { |
| // Scan all Edge outputs and link them to the Node objects. |
| Edge* edge = clump->edges_[edge_idx]; |
| for (size_t i = 0; i < edge->outputs_.size(); ) { |
| Node* output = edge->outputs_[i]; |
| if (output->in_edge() == nullptr) { |
| output->set_in_edge(edge); |
| ++i; |
| continue; |
| } |
| // Two edges produce the same output node. |
| if (options_.dupe_edge_action_ == kDupeEdgeActionError) { |
| return DecorateError(clump->file_, |
| edge->parse_state_.final_diag_pos, |
| "multiple rules generate " + output->path() + |
| " [-w dupbuild=err]", err); |
| } else { |
| if (!quiet_) { |
| Warning("multiple rules generate %s. " |
| "builds involving this target will not be correct; " |
| "continuing anyway [-w dupbuild=warn]", |
| output->path().c_str()); |
| } |
| if (edge->is_implicit_out(i)) |
| --edge->implicit_outs_; |
| else |
| --edge->explicit_outs_; |
| edge->outputs_.erase(edge->outputs_.begin() + i); |
| } |
| } |
| if (edge->outputs_.empty()) { |
| // All outputs of the edge are already created by other edges. Remove |
| // this edge from the graph. This removal happens before the edge's |
| // inputs are linked to nodes. |
| clump->edges_.erase(clump->edges_.begin() + edge_idx); |
| continue; |
| } |
| ++edge_idx; |
| } |
| } |
| } |
| { |
| // Now that all invalid edges are removed from the graph, record an out-edge |
| // on each node that's needed by an edge. |
| METRIC_RECORD(".ninja load : link edge inputs"); |
| ParallelMap(thread_pool_, clumps, [](Clump* clump) { |
| for (Edge* edge : clump->edges_) { |
| for (Node* input : edge->inputs_) { |
| input->AddOutEdge(edge); |
| } |
| for (Node* validation : edge->validations_) { |
| validation->AddValidationOutEdge(edge); |
| } |
| } |
| }); |
| } |
| { |
| METRIC_RECORD(".ninja load : default targets"); |
| |
| for (Clump* clump : clumps) { |
| for (DefaultTarget* target : clump->default_targets_) { |
| std::string path; |
| EvaluatePathInScope(&path, target->parsed_path_, |
| target->pos_.scope_pos()); |
| uint64_t slash_bits; // Unused because this only does lookup. |
| std::string path_err; |
| if (!CanonicalizePath(&path, &slash_bits, &path_err)) |
| return DecorateError(clump->file_, target->diag_pos_, path_err, err); |
| |
| Node* node = state_->LookupNodeAtPos(path, target->pos_.dfs_location()); |
| if (node == nullptr) { |
| return DecorateError(clump->file_, target->diag_pos_, |
| "unknown target '" + path + "'", err); |
| } |
| state_->AddDefault(node); |
| } |
| } |
| } |
| { |
| // Add the clump edges into the global edge vector, and assign edge IDs. |
| // Edge IDs are used for custom protobuf-based Ninja frontends. An edge's ID |
| // is equal to its index in the global edge vector, so delay the assignment |
| // of edge IDs until we've removed duplicate edges above (dupbuild=warn). |
| |
| METRIC_RECORD(".ninja load : build edge table"); |
| |
| // Copy edges to the global edge table. |
| size_t old_size = state_->edges_.size(); |
| size_t new_size = old_size; |
| for (Clump* clump : clumps) { |
| new_size += clump->edges_.size(); |
| } |
| state_->edges_.reserve(new_size); |
| for (Clump* clump : clumps) { |
| std::copy(clump->edges_.begin(), clump->edges_.end(), |
| std::back_inserter(state_->edges_)); |
| } |
| // Assign edge IDs. |
| ParallelMap(thread_pool_, IntegralRange<size_t>(old_size, new_size), |
| [this](size_t idx) { |
| state_->edges_[idx]->id_ = idx; |
| }); |
| } |
| |
| return true; |
| } |
| |
| bool ManifestLoader::Load(ManifestFileSet* file_set, |
| const LoadedFile& root_manifest, std::string* err) { |
| DfsParser dfs_parser(file_set, state_, thread_pool_); |
| std::vector<Clump*> clumps; |
| if (!dfs_parser.LoadManifestTree(root_manifest, &state_->root_scope_, &clumps, |
| err)) { |
| return false; |
| } |
| return FinishLoading(clumps, err); |
| } |
| |
| } // anonymous namespace |
| |
| bool ManifestParser::Load(const string& filename, string* err) { |
| METRIC_RECORD(".ninja load"); |
| |
| ManifestFileSet file_set(file_reader_); |
| const LoadedFile* file = nullptr; |
| if (!file_set.LoadFile(filename, &file, err)) |
| return false; |
| |
| std::unique_ptr<ThreadPool> thread_pool = CreateThreadPool(); |
| ManifestLoader loader(state_, thread_pool.get(), options_, false); |
| return loader.Load(&file_set, *file, err); |
| } |
| |
| bool ManifestParser::ParseTest(const string& input, string* err) { |
| ManifestFileSet file_set(file_reader_); |
| std::unique_ptr<ThreadPool> thread_pool = CreateThreadPool(); |
| ManifestLoader loader(state_, thread_pool.get(), options_, true); |
| return loader.Load(&file_set, HeapLoadedFile("input", input), err); |
| } |