blob: 0a30e661fda1b63e9a3d4da687a0c1f76abfe194 [file] [log] [blame]
// 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
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// See the License for the specific language governing permissions and
// limitations under the License.
#include "eval_env.h"
#include <assert.h>
#include "graph.h"
#include "state.h"
Rule::Rule(const HashedStrView& name) : name_(name) {
pos_.base = new BasePosition {{ &State::kBuiltinScope, 0 }}; // leaked
bool Rule::IsReservedBinding(StringPiece var) {
// Cycle detection for rule variable evaluation uses a fixed recursion depth
// that's guaranteed to be larger than the number of reserved binding names
// listed below.
static_assert(EdgeEval::kEvalRecursionLimit == 16,
"Unexpected rule variable evaluation recursion limit");
return var == "command" ||
var == "depfile" ||
var == "dyndep" ||
var == "description" ||
var == "deps" ||
var == "generator" ||
var == "pool" ||
var == "restat" ||
var == "rspfile" ||
var == "rspfile_content" ||
var == "phony_output" ||
var == "symlink_outputs" ||
var == "msvc_deps_prefix";
void Binding::Evaluate(std::string* out_append) {
if (is_evaluated_.load()) {
std::string str;
EvaluateBindingInScope(&str, parsed_value_, pos_.scope_pos());
// Try to store the result so we can use it again later. If we can't acquire
// the lock, then another thread has already acquired it and will set the
// final binding value.
std::unique_lock<std::mutex> lock(mutex_, std::try_to_lock);
if (!lock.owns_lock())
// Check the flag again. Another thread could have set it before this thread
// acquired the lock, and if it had, then other threads could already be using
// this binding's saved value.
if (is_evaluated_.load())
final_value_ = std::move(str);;
template <typename K, typename V>
static void ExpandTable(std::unordered_map<K, V>& table, size_t extra_size) {
size_t needed_buckets = table.size() + extra_size + 1;
if (table.bucket_count() >= needed_buckets)
table.rehash(needed_buckets * 2);
void Scope::ReserveTableSpace(size_t new_bindings, size_t new_rules) {
ExpandTable(bindings_, new_bindings);
ExpandTable(rules_, new_rules);
std::map<std::string, const Rule*> Scope::GetRules() const {
std::map<std::string, const Rule*> result;
for (std::pair<HashedStrView, Rule*> pair : rules_) {
Rule* rule = pair.second;
result[rule->name()] = rule;
return result;
Binding* Scope::LookupBindingAtPos(const HashedStrView& var, ScopePosition pos) {
Scope* scope = pos.scope;
if (scope == nullptr) return nullptr;
auto it = scope->bindings_.find(var);
if (it == scope->bindings_.end())
return LookupBindingAtPos(var, scope->parent_);
struct BindingCmp {
bool operator()(Binding* x, DeclIndex y) const {
return x->pos_.scope_index() < y;
// A binding "Foo = $Foo" is valid; the "$Foo" is not a self-reference but
// a reference to the previous binding of Foo. The evaluation of "$Foo"
// happens with the same DeclIndex as the "Foo = $Foo" binding, so we want
// to find a binding whose ScopePosition is strictly less than the one we're
// searching for, not equal to it.
std::vector<Binding*>& decls = it->second;
auto it2 = std::lower_bound(
decls.begin(), decls.end(),
pos.index, BindingCmp());
if (it2 == decls.begin())
return LookupBindingAtPos(var, scope->parent_);
return *(it2 - 1);
Binding* Scope::LookupBinding(const HashedStrView& var, Scope* scope) {
if (scope == nullptr) return nullptr;
auto it = scope->bindings_.find(var);
if (it == scope->bindings_.end()) {
// When we delegate to the parent scope, we match bindings at the end of the
// parent's scope, even if they weren't in scope when the subninja scope was
// parsed. The behavior matters after parsing is complete and we're
// evaluating edge bindings that involve rule variable expansions.
return LookupBinding(var, scope->parent_.scope);
std::vector<Binding*>& decls = it->second;
// Evaluate the binding.
return decls.back();
void Scope::EvaluateVariableAtPos(std::string* out_append,
const HashedStrView& var, ScopePosition pos) {
if (Binding* binding = LookupBindingAtPos(var, pos))
void Scope::EvaluateVariable(std::string* out_append, const HashedStrView& var,
Scope* scope) {
if (Binding* binding = LookupBinding(var, scope))
std::string Scope::LookupVariable(const HashedStrView& var) {
std::string result;
EvaluateVariable(&result, var, this);
return result;
Rule* Scope::LookupRuleAtPos(const HashedStrView& rule_name,
ScopePosition pos) {
Scope* scope = pos.scope;
if (scope == nullptr) return nullptr;
auto it = scope->rules_.find(rule_name);
if (it != scope->rules_.end()) {
Rule* rule = it->second;
if (rule->pos_.scope_index() < pos.index)
return rule;
return LookupRuleAtPos(rule_name, scope->parent_);