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   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 }