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 16 namespace { 17 18 std::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 27 ParseNode::ParseNode() { 28 } 29 30 ParseNode::~ParseNode() { 31 } 32 33 const AccessorNode* ParseNode::AsAccessor() const { return NULL; } 34 const BinaryOpNode* ParseNode::AsBinaryOp() const { return NULL; } 35 const BlockNode* ParseNode::AsBlock() const { return NULL; } 36 const ConditionNode* ParseNode::AsConditionNode() const { return NULL; } 37 const FunctionCallNode* ParseNode::AsFunctionCall() const { return NULL; } 38 const IdentifierNode* ParseNode::AsIdentifier() const { return NULL; } 39 const ListNode* ParseNode::AsList() const { return NULL; } 40 const LiteralNode* ParseNode::AsLiteral() const { return NULL; } 41 const UnaryOpNode* ParseNode::AsUnaryOp() const { return NULL; } 42 43 // AccessorNode --------------------------------------------------------------- 44 45 AccessorNode::AccessorNode() { 46 } 47 48 AccessorNode::~AccessorNode() { 49 } 50 51 const AccessorNode* AccessorNode::AsAccessor() const { 52 return this; 53 } 54 55 Value 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 64 LocationRange 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 73 Err AccessorNode::MakeErrorDescribing(const std::string& msg, 74 const std::string& help) const { 75 return Err(GetRange(), msg, help); 76 } 77 78 void 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 87 Value 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 126 Value 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 170 BinaryOpNode::BinaryOpNode() { 171 } 172 173 BinaryOpNode::~BinaryOpNode() { 174 } 175 176 const BinaryOpNode* BinaryOpNode::AsBinaryOp() const { 177 return this; 178 } 179 180 Value BinaryOpNode::Execute(Scope* scope, Err* err) const { 181 return ExecuteBinaryOperator(scope, this, left_.get(), right_.get(), err); 182 } 183 184 LocationRange BinaryOpNode::GetRange() const { 185 return left_->GetRange().Union(right_->GetRange()); 186 } 187 188 Err BinaryOpNode::MakeErrorDescribing(const std::string& msg, 189 const std::string& help) const { 190 return Err(op_, msg, help); 191 } 192 193 void 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 201 BlockNode::BlockNode(bool has_scope) : has_scope_(has_scope) { 202 } 203 204 BlockNode::~BlockNode() { 205 STLDeleteContainerPointers(statements_.begin(), statements_.end()); 206 } 207 208 const BlockNode* BlockNode::AsBlock() const { 209 return this; 210 } 211 212 Value 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 226 LocationRange 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 237 Err BlockNode::MakeErrorDescribing(const std::string& msg, 238 const std::string& help) const { 239 return Err(GetRange(), msg, help); 240 } 241 242 void 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 248 Value 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 266 ConditionNode::ConditionNode() { 267 } 268 269 ConditionNode::~ConditionNode() { 270 } 271 272 const ConditionNode* ConditionNode::AsConditionNode() const { 273 return this; 274 } 275 276 Value 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 307 LocationRange 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 313 Err ConditionNode::MakeErrorDescribing(const std::string& msg, 314 const std::string& help) const { 315 return Err(if_token_, msg, help); 316 } 317 318 void 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 328 FunctionCallNode::FunctionCallNode() { 329 } 330 331 FunctionCallNode::~FunctionCallNode() { 332 } 333 334 const FunctionCallNode* FunctionCallNode::AsFunctionCall() const { 335 return this; 336 } 337 338 Value FunctionCallNode::Execute(Scope* scope, Err* err) const { 339 return functions::RunFunction(scope, this, args_.get(), block_.get(), err); 340 } 341 342 LocationRange FunctionCallNode::GetRange() const { 343 if (block_) 344 return function_.range().Union(block_->GetRange()); 345 return function_.range().Union(args_->GetRange()); 346 } 347 348 Err FunctionCallNode::MakeErrorDescribing(const std::string& msg, 349 const std::string& help) const { 350 return Err(function_, msg, help); 351 } 352 353 void 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 362 IdentifierNode::IdentifierNode() { 363 } 364 365 IdentifierNode::IdentifierNode(const Token& token) : value_(token) { 366 } 367 368 IdentifierNode::~IdentifierNode() { 369 } 370 371 const IdentifierNode* IdentifierNode::AsIdentifier() const { 372 return this; 373 } 374 375 Value IdentifierNode::Execute(Scope* scope, Err* err) const { 376 const Value* result = scope->GetValue(value_.value(), true); 377 if (!result) { 378 *err = MakeErrorDescribing("Undefined identifier"); 379 return Value(); 380 } 381 return *result; 382 } 383 384 LocationRange IdentifierNode::GetRange() const { 385 return value_.range(); 386 } 387 388 Err IdentifierNode::MakeErrorDescribing(const std::string& msg, 389 const std::string& help) const { 390 return Err(value_, msg, help); 391 } 392 393 void IdentifierNode::Print(std::ostream& out, int indent) const { 394 out << IndentFor(indent) << "IDENTIFIER(" << value_.value() << ")\n"; 395 } 396 397 // ListNode ------------------------------------------------------------------- 398 399 ListNode::ListNode() { 400 } 401 402 ListNode::~ListNode() { 403 STLDeleteContainerPointers(contents_.begin(), contents_.end()); 404 } 405 406 const ListNode* ListNode::AsList() const { 407 return this; 408 } 409 410 Value ListNode::Execute(Scope* scope, Err* err) const { 411 Value result_value(this, Value::LIST); 412 std::vector<Value>& results = result_value.list_value(); 413 results.resize(contents_.size()); 414 415 for (size_t i = 0; i < contents_.size(); i++) { 416 const ParseNode* cur = contents_[i]; 417 results[i] = cur->Execute(scope, err); 418 if (err->has_error()) 419 return Value(); 420 if (results[i].type() == Value::NONE) { 421 *err = cur->MakeErrorDescribing( 422 "This does not evaluate to a value.", 423 "I can't do something with nothing."); 424 return Value(); 425 } 426 } 427 return result_value; 428 } 429 430 LocationRange ListNode::GetRange() const { 431 return LocationRange(begin_token_.location(), end_token_.location()); 432 } 433 434 Err ListNode::MakeErrorDescribing(const std::string& msg, 435 const std::string& help) const { 436 return Err(begin_token_, msg, help); 437 } 438 439 void ListNode::Print(std::ostream& out, int indent) const { 440 out << IndentFor(indent) << "LIST\n"; 441 for (size_t i = 0; i < contents_.size(); i++) 442 contents_[i]->Print(out, indent + 1); 443 } 444 445 // LiteralNode ----------------------------------------------------------------- 446 447 LiteralNode::LiteralNode() { 448 } 449 450 LiteralNode::LiteralNode(const Token& token) : value_(token) { 451 } 452 453 LiteralNode::~LiteralNode() { 454 } 455 456 const LiteralNode* LiteralNode::AsLiteral() const { 457 return this; 458 } 459 460 Value LiteralNode::Execute(Scope* scope, Err* err) const { 461 switch (value_.type()) { 462 case Token::TRUE_TOKEN: 463 return Value(this, true); 464 case Token::FALSE_TOKEN: 465 return Value(this, false); 466 case Token::INTEGER: { 467 int64 result_int; 468 if (!base::StringToInt64(value_.value(), &result_int)) { 469 *err = MakeErrorDescribing("This does not look like an integer"); 470 return Value(); 471 } 472 return Value(this, result_int); 473 } 474 case Token::STRING: { 475 Value v(this, Value::STRING); 476 ExpandStringLiteral(scope, value_, &v, err); 477 return v; 478 } 479 default: 480 NOTREACHED(); 481 return Value(); 482 } 483 } 484 485 LocationRange LiteralNode::GetRange() const { 486 return value_.range(); 487 } 488 489 Err LiteralNode::MakeErrorDescribing(const std::string& msg, 490 const std::string& help) const { 491 return Err(value_, msg, help); 492 } 493 494 void LiteralNode::Print(std::ostream& out, int indent) const { 495 out << IndentFor(indent) << "LITERAL(" << value_.value() << ")\n"; 496 } 497 498 // UnaryOpNode ---------------------------------------------------------------- 499 500 UnaryOpNode::UnaryOpNode() { 501 } 502 503 UnaryOpNode::~UnaryOpNode() { 504 } 505 506 const UnaryOpNode* UnaryOpNode::AsUnaryOp() const { 507 return this; 508 } 509 510 Value UnaryOpNode::Execute(Scope* scope, Err* err) const { 511 Value operand_value = operand_->Execute(scope, err); 512 if (err->has_error()) 513 return Value(); 514 return ExecuteUnaryOperator(scope, this, operand_value, err); 515 } 516 517 LocationRange UnaryOpNode::GetRange() const { 518 return op_.range().Union(operand_->GetRange()); 519 } 520 521 Err UnaryOpNode::MakeErrorDescribing(const std::string& msg, 522 const std::string& help) const { 523 return Err(op_, msg, help); 524 } 525 526 void UnaryOpNode::Print(std::ostream& out, int indent) const { 527 out << IndentFor(indent) << "UNARY(" << op_.value() << ")\n"; 528 operand_->Print(out, indent + 1); 529 } 530