tools/gn/parse_tree.cc

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