parse_tree.cc revision 6e8cce623b6e4fe0c9e4af605d675dd9d0338c38
1// Copyright (c) 2013 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include "tools/gn/parse_tree.h" 6 7#include <string> 8 9#include "base/stl_util.h" 10#include "base/strings/string_number_conversions.h" 11#include "tools/gn/functions.h" 12#include "tools/gn/operators.h" 13#include "tools/gn/scope.h" 14#include "tools/gn/string_utils.h" 15 16namespace { 17 18std::string IndentFor(int value) { 19 std::string ret; 20 for (int i = 0; i < value; i++) 21 ret.append(" "); 22 return ret; 23} 24 25} // namespace 26 27ParseNode::ParseNode() { 28} 29 30ParseNode::~ParseNode() { 31} 32 33const AccessorNode* ParseNode::AsAccessor() const { return NULL; } 34const BinaryOpNode* ParseNode::AsBinaryOp() const { return NULL; } 35const BlockNode* ParseNode::AsBlock() const { return NULL; } 36const ConditionNode* ParseNode::AsConditionNode() const { return NULL; } 37const FunctionCallNode* ParseNode::AsFunctionCall() const { return NULL; } 38const IdentifierNode* ParseNode::AsIdentifier() const { return NULL; } 39const ListNode* ParseNode::AsList() const { return NULL; } 40const LiteralNode* ParseNode::AsLiteral() const { return NULL; } 41const UnaryOpNode* ParseNode::AsUnaryOp() const { return NULL; } 42 43// AccessorNode --------------------------------------------------------------- 44 45AccessorNode::AccessorNode() { 46} 47 48AccessorNode::~AccessorNode() { 49} 50 51const AccessorNode* AccessorNode::AsAccessor() const { 52 return this; 53} 54 55Value AccessorNode::Execute(Scope* scope, Err* err) const { 56 if (index_) 57 return ExecuteArrayAccess(scope, err); 58 else if (member_) 59 return ExecuteScopeAccess(scope, err); 60 NOTREACHED(); 61 return Value(); 62} 63 64LocationRange AccessorNode::GetRange() const { 65 if (index_) 66 return LocationRange(base_.location(), index_->GetRange().end()); 67 else if (member_) 68 return LocationRange(base_.location(), member_->GetRange().end()); 69 NOTREACHED(); 70 return LocationRange(); 71} 72 73Err AccessorNode::MakeErrorDescribing(const std::string& msg, 74 const std::string& help) const { 75 return Err(GetRange(), msg, help); 76} 77 78void AccessorNode::Print(std::ostream& out, int indent) const { 79 out << IndentFor(indent) << "ACCESSOR\n"; 80 out << IndentFor(indent + 1) << base_.value() << "\n"; 81 if (index_) 82 index_->Print(out, indent + 1); 83 else if (member_) 84 member_->Print(out, indent + 1); 85} 86 87Value AccessorNode::ExecuteArrayAccess(Scope* scope, Err* err) const { 88 Value index_value = index_->Execute(scope, err); 89 if (err->has_error()) 90 return Value(); 91 if (!index_value.VerifyTypeIs(Value::INTEGER, err)) 92 return Value(); 93 94 const Value* base_value = scope->GetValue(base_.value(), true); 95 if (!base_value) { 96 *err = MakeErrorDescribing("Undefined identifier."); 97 return Value(); 98 } 99 if (!base_value->VerifyTypeIs(Value::LIST, err)) 100 return Value(); 101 102 int64 index_int = index_value.int_value(); 103 if (index_int < 0) { 104 *err = Err(index_->GetRange(), "Negative array subscript.", 105 "You gave me " + base::Int64ToString(index_int) + "."); 106 return Value(); 107 } 108 size_t index_sizet = static_cast<size_t>(index_int); 109 if (index_sizet >= base_value->list_value().size()) { 110 *err = Err(index_->GetRange(), "Array subscript out of range.", 111 "You gave me " + base::Int64ToString(index_int) + 112 " but I was expecting something from 0 to " + 113 base::Int64ToString( 114 static_cast<int64>(base_value->list_value().size()) - 1) + 115 ", inclusive."); 116 return Value(); 117 } 118 119 // Doing this assumes that there's no way in the language to do anything 120 // between the time the reference is created and the time that the reference 121 // is used. If there is, this will crash! Currently, this is just used for 122 // array accesses where this "shouldn't" happen. 123 return base_value->list_value()[index_sizet]; 124} 125 126Value AccessorNode::ExecuteScopeAccess(Scope* scope, Err* err) const { 127 // We jump through some hoops here since ideally a.b will count "b" as 128 // accessed in the given scope. The value "a" might be in some normal nested 129 // scope and we can modify it, but it might also be inherited from the 130 // readonly root scope and we can't do used variable tracking on it. (It's 131 // not legal to const cast it away since the root scope will be in readonly 132 // mode and being accessed from multiple threads without locking.) So this 133 // code handles both cases. 134 const Value* result = NULL; 135 136 // Look up the value in the scope named by "base_". 137 Value* mutable_base_value = scope->GetMutableValue(base_.value(), true); 138 if (mutable_base_value) { 139 // Common case: base value is mutable so we can track variable accesses 140 // for unused value warnings. 141 if (!mutable_base_value->VerifyTypeIs(Value::SCOPE, err)) 142 return Value(); 143 result = mutable_base_value->scope_value()->GetValue( 144 member_->value().value(), true); 145 } else { 146 // Fall back to see if the value is on a read-only scope. 147 const Value* const_base_value = scope->GetValue(base_.value(), true); 148 if (const_base_value) { 149 // Read only value, don't try to mark the value access as a "used" one. 150 if (!const_base_value->VerifyTypeIs(Value::SCOPE, err)) 151 return Value(); 152 result = 153 const_base_value->scope_value()->GetValue(member_->value().value()); 154 } else { 155 *err = Err(base_, "Undefined identifier."); 156 return Value(); 157 } 158 } 159 160 if (!result) { 161 *err = Err(member_.get(), "No value named \"" + 162 member_->value().value() + "\" in scope \"" + base_.value() + "\""); 163 return Value(); 164 } 165 return *result; 166} 167 168// BinaryOpNode --------------------------------------------------------------- 169 170BinaryOpNode::BinaryOpNode() { 171} 172 173BinaryOpNode::~BinaryOpNode() { 174} 175 176const BinaryOpNode* BinaryOpNode::AsBinaryOp() const { 177 return this; 178} 179 180Value BinaryOpNode::Execute(Scope* scope, Err* err) const { 181 return ExecuteBinaryOperator(scope, this, left_.get(), right_.get(), err); 182} 183 184LocationRange BinaryOpNode::GetRange() const { 185 return left_->GetRange().Union(right_->GetRange()); 186} 187 188Err BinaryOpNode::MakeErrorDescribing(const std::string& msg, 189 const std::string& help) const { 190 return Err(op_, msg, help); 191} 192 193void BinaryOpNode::Print(std::ostream& out, int indent) const { 194 out << IndentFor(indent) << "BINARY(" << op_.value() << ")\n"; 195 left_->Print(out, indent + 1); 196 right_->Print(out, indent + 1); 197} 198 199// BlockNode ------------------------------------------------------------------ 200 201BlockNode::BlockNode(bool has_scope) : has_scope_(has_scope) { 202} 203 204BlockNode::~BlockNode() { 205 STLDeleteContainerPointers(statements_.begin(), statements_.end()); 206} 207 208const BlockNode* BlockNode::AsBlock() const { 209 return this; 210} 211 212Value BlockNode::Execute(Scope* containing_scope, Err* err) const { 213 if (has_scope_) { 214 Scope our_scope(containing_scope); 215 Value ret = ExecuteBlockInScope(&our_scope, err); 216 if (err->has_error()) 217 return Value(); 218 219 // Check for unused vars in the scope. 220 our_scope.CheckForUnusedVars(err); 221 return ret; 222 } 223 return ExecuteBlockInScope(containing_scope, err); 224} 225 226LocationRange BlockNode::GetRange() const { 227 if (begin_token_.type() != Token::INVALID && 228 end_token_.type() != Token::INVALID) { 229 return begin_token_.range().Union(end_token_.range()); 230 } else if (!statements_.empty()) { 231 return statements_[0]->GetRange().Union( 232 statements_[statements_.size() - 1]->GetRange()); 233 } 234 return LocationRange(); 235} 236 237Err BlockNode::MakeErrorDescribing(const std::string& msg, 238 const std::string& help) const { 239 return Err(GetRange(), msg, help); 240} 241 242void BlockNode::Print(std::ostream& out, int indent) const { 243 out << IndentFor(indent) << "BLOCK\n"; 244 for (size_t i = 0; i < statements_.size(); i++) 245 statements_[i]->Print(out, indent + 1); 246} 247 248Value BlockNode::ExecuteBlockInScope(Scope* our_scope, Err* err) const { 249 for (size_t i = 0; i < statements_.size() && !err->has_error(); i++) { 250 // Check for trying to execute things with no side effects in a block. 251 const ParseNode* cur = statements_[i]; 252 if (cur->AsList() || cur->AsLiteral() || cur->AsUnaryOp() || 253 cur->AsIdentifier()) { 254 *err = cur->MakeErrorDescribing( 255 "This statement has no effect.", 256 "Either delete it or do something with the result."); 257 return Value(); 258 } 259 cur->Execute(our_scope, err); 260 } 261 return Value(); 262} 263 264// ConditionNode -------------------------------------------------------------- 265 266ConditionNode::ConditionNode() { 267} 268 269ConditionNode::~ConditionNode() { 270} 271 272const ConditionNode* ConditionNode::AsConditionNode() const { 273 return this; 274} 275 276Value ConditionNode::Execute(Scope* scope, Err* err) const { 277 Value condition_result = condition_->Execute(scope, err); 278 if (err->has_error()) 279 return Value(); 280 if (condition_result.type() != Value::BOOLEAN) { 281 *err = condition_->MakeErrorDescribing( 282 "Condition does not evaluate to a boolean value.", 283 std::string("This is a value of type \"") + 284 Value::DescribeType(condition_result.type()) + 285 "\" instead."); 286 err->AppendRange(if_token_.range()); 287 return Value(); 288 } 289 290 if (condition_result.boolean_value()) { 291 if_true_->ExecuteBlockInScope(scope, err); 292 } else if (if_false_) { 293 // The else block is optional. It's either another condition (for an 294 // "else if" and we can just Execute it and the condition will handle 295 // the scoping) or it's a block indicating an "else" in which ase we 296 // need to be sure it inherits our scope. 297 const BlockNode* if_false_block = if_false_->AsBlock(); 298 if (if_false_block) 299 if_false_block->ExecuteBlockInScope(scope, err); 300 else 301 if_false_->Execute(scope, err); 302 } 303 304 return Value(); 305} 306 307LocationRange ConditionNode::GetRange() const { 308 if (if_false_) 309 return if_token_.range().Union(if_false_->GetRange()); 310 return if_token_.range().Union(if_true_->GetRange()); 311} 312 313Err ConditionNode::MakeErrorDescribing(const std::string& msg, 314 const std::string& help) const { 315 return Err(if_token_, msg, help); 316} 317 318void ConditionNode::Print(std::ostream& out, int indent) const { 319 out << IndentFor(indent) << "CONDITION\n"; 320 condition_->Print(out, indent + 1); 321 if_true_->Print(out, indent + 1); 322 if (if_false_) 323 if_false_->Print(out, indent + 1); 324} 325 326// FunctionCallNode ----------------------------------------------------------- 327 328FunctionCallNode::FunctionCallNode() { 329} 330 331FunctionCallNode::~FunctionCallNode() { 332} 333 334const FunctionCallNode* FunctionCallNode::AsFunctionCall() const { 335 return this; 336} 337 338Value FunctionCallNode::Execute(Scope* scope, Err* err) const { 339 return functions::RunFunction(scope, this, args_.get(), block_.get(), err); 340} 341 342LocationRange FunctionCallNode::GetRange() const { 343 if (block_) 344 return function_.range().Union(block_->GetRange()); 345 return function_.range().Union(args_->GetRange()); 346} 347 348Err FunctionCallNode::MakeErrorDescribing(const std::string& msg, 349 const std::string& help) const { 350 return Err(function_, msg, help); 351} 352 353void FunctionCallNode::Print(std::ostream& out, int indent) const { 354 out << IndentFor(indent) << "FUNCTION(" << function_.value() << ")\n"; 355 args_->Print(out, indent + 1); 356 if (block_) 357 block_->Print(out, indent + 1); 358} 359 360// IdentifierNode -------------------------------------------------------------- 361 362IdentifierNode::IdentifierNode() { 363} 364 365IdentifierNode::IdentifierNode(const Token& token) : value_(token) { 366} 367 368IdentifierNode::~IdentifierNode() { 369} 370 371const IdentifierNode* IdentifierNode::AsIdentifier() const { 372 return this; 373} 374 375Value IdentifierNode::Execute(Scope* scope, Err* err) const { 376 const Value* value = scope->GetValue(value_.value(), true); 377 Value result; 378 if (!value) { 379 *err = MakeErrorDescribing("Undefined identifier"); 380 return result; 381 } 382 383 result = *value; 384 result.set_origin(this); 385 return result; 386} 387 388LocationRange IdentifierNode::GetRange() const { 389 return value_.range(); 390} 391 392Err IdentifierNode::MakeErrorDescribing(const std::string& msg, 393 const std::string& help) const { 394 return Err(value_, msg, help); 395} 396 397void IdentifierNode::Print(std::ostream& out, int indent) const { 398 out << IndentFor(indent) << "IDENTIFIER(" << value_.value() << ")\n"; 399} 400 401// ListNode ------------------------------------------------------------------- 402 403ListNode::ListNode() { 404} 405 406ListNode::~ListNode() { 407 STLDeleteContainerPointers(contents_.begin(), contents_.end()); 408} 409 410const ListNode* ListNode::AsList() const { 411 return this; 412} 413 414Value ListNode::Execute(Scope* scope, Err* err) const { 415 Value result_value(this, Value::LIST); 416 std::vector<Value>& results = result_value.list_value(); 417 results.resize(contents_.size()); 418 419 for (size_t i = 0; i < contents_.size(); i++) { 420 const ParseNode* cur = contents_[i]; 421 results[i] = cur->Execute(scope, err); 422 if (err->has_error()) 423 return Value(); 424 if (results[i].type() == Value::NONE) { 425 *err = cur->MakeErrorDescribing( 426 "This does not evaluate to a value.", 427 "I can't do something with nothing."); 428 return Value(); 429 } 430 } 431 return result_value; 432} 433 434LocationRange ListNode::GetRange() const { 435 return LocationRange(begin_token_.location(), end_token_.location()); 436} 437 438Err ListNode::MakeErrorDescribing(const std::string& msg, 439 const std::string& help) const { 440 return Err(begin_token_, msg, help); 441} 442 443void ListNode::Print(std::ostream& out, int indent) const { 444 out << IndentFor(indent) << "LIST\n"; 445 for (size_t i = 0; i < contents_.size(); i++) 446 contents_[i]->Print(out, indent + 1); 447} 448 449// LiteralNode ----------------------------------------------------------------- 450 451LiteralNode::LiteralNode() { 452} 453 454LiteralNode::LiteralNode(const Token& token) : value_(token) { 455} 456 457LiteralNode::~LiteralNode() { 458} 459 460const LiteralNode* LiteralNode::AsLiteral() const { 461 return this; 462} 463 464Value LiteralNode::Execute(Scope* scope, Err* err) const { 465 switch (value_.type()) { 466 case Token::TRUE_TOKEN: 467 return Value(this, true); 468 case Token::FALSE_TOKEN: 469 return Value(this, false); 470 case Token::INTEGER: { 471 int64 result_int; 472 if (!base::StringToInt64(value_.value(), &result_int)) { 473 *err = MakeErrorDescribing("This does not look like an integer"); 474 return Value(); 475 } 476 return Value(this, result_int); 477 } 478 case Token::STRING: { 479 Value v(this, Value::STRING); 480 ExpandStringLiteral(scope, value_, &v, err); 481 return v; 482 } 483 default: 484 NOTREACHED(); 485 return Value(); 486 } 487} 488 489LocationRange LiteralNode::GetRange() const { 490 return value_.range(); 491} 492 493Err LiteralNode::MakeErrorDescribing(const std::string& msg, 494 const std::string& help) const { 495 return Err(value_, msg, help); 496} 497 498void LiteralNode::Print(std::ostream& out, int indent) const { 499 out << IndentFor(indent) << "LITERAL(" << value_.value() << ")\n"; 500} 501 502// UnaryOpNode ---------------------------------------------------------------- 503 504UnaryOpNode::UnaryOpNode() { 505} 506 507UnaryOpNode::~UnaryOpNode() { 508} 509 510const UnaryOpNode* UnaryOpNode::AsUnaryOp() const { 511 return this; 512} 513 514Value UnaryOpNode::Execute(Scope* scope, Err* err) const { 515 Value operand_value = operand_->Execute(scope, err); 516 if (err->has_error()) 517 return Value(); 518 return ExecuteUnaryOperator(scope, this, operand_value, err); 519} 520 521LocationRange UnaryOpNode::GetRange() const { 522 return op_.range().Union(operand_->GetRange()); 523} 524 525Err UnaryOpNode::MakeErrorDescribing(const std::string& msg, 526 const std::string& help) const { 527 return Err(op_, msg, help); 528} 529 530void UnaryOpNode::Print(std::ostream& out, int indent) const { 531 out << IndentFor(indent) << "UNARY(" << op_.value() << ")\n"; 532 operand_->Print(out, indent + 1); 533} 534