src/tools/gn/operators.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/operators.h"
   6
   7 #include "base/strings/string_number_conversions.h"
   8 #include "tools/gn/err.h"
   9 #include "tools/gn/parse_tree.h"
  10 #include "tools/gn/scope.h"
  11 #include "tools/gn/token.h"
  12 #include "tools/gn/value.h"
  13
  14 namespace {
  15
  16 const char kSourcesName[] = "sources";
  17
  18 // Applies the sources assignment filter from the given scope to each element
  19 // of source (can be a list or a string), appending it to dest if it doesn't
  20 // match.
  21 void AppendFilteredSourcesToValue(const Scope* scope,
  22                                   const Value& source,
  23                                   Value* dest) {
  24   const PatternList* filter = scope->GetSourcesAssignmentFilter();
  25
  26   if (source.type() == Value::STRING) {
  27     if (!filter || filter->is_empty() ||
  28         !filter->MatchesValue(source))
  29       dest->list_value().push_back(source);
  30     return;
  31   }
  32   if (source.type() != Value::LIST) {
  33     // Any non-list and non-string being added to a list can just get appended,
  34     // we're not going to filter it.
  35     dest->list_value().push_back(source);
  36     return;
  37   }
  38
  39   if (!filter || filter->is_empty()) {
  40     // No filter, append everything.
  41     for (const auto& source_entry : source.list_value())
  42       dest->list_value().push_back(source_entry);
  43     return;
  44   }
  45
  46   // Note: don't reserve() the dest vector here since that actually hurts
  47   // the allocation pattern when the build script is doing multiple small
  48   // additions.
  49   for (const auto& source_entry : source.list_value()) {
  50     if (!filter->MatchesValue(source_entry))
  51       dest->list_value().push_back(source_entry);
  52   }
  53 }
  54
  55 Value GetValueOrFillError(const BinaryOpNode* op_node,
  56                           const ParseNode* node,
  57                           const char* name,
  58                           Scope* scope,
  59                           Err* err) {
  60   Value value = node->Execute(scope, err);
  61   if (err->has_error())
  62     return Value();
  63   if (value.type() == Value::NONE) {
  64     *err = Err(op_node->op(),
  65                "Operator requires a value.",
  66                "This thing on the " + std::string(name) +
  67                    " does not evaluate to a value.");
  68     err->AppendRange(node->GetRange());
  69     return Value();
  70   }
  71   return value;
  72 }
  73
  74 void RemoveMatchesFromList(const BinaryOpNode* op_node,
  75                            Value* list,
  76                            const Value& to_remove,
  77                            Err* err) {
  78   std::vector<Value>& v = list->list_value();
  79   switch (to_remove.type()) {
  80     case Value::BOOLEAN:
  81     case Value::INTEGER:  // Filter out the individual int/string.
  82     case Value::STRING: {
  83       bool found_match = false;
  84       for (size_t i = 0; i < v.size(); /* nothing */) {
  85         if (v[i] == to_remove) {
  86           found_match = true;
  87           v.erase(v.begin() + i);
  88         } else {
  89           i++;
  90         }
  91       }
  92       if (!found_match) {
  93         *err = Err(to_remove.origin()->GetRange(), "Item not found",
  94             "You were trying to remove " + to_remove.ToString(true) +
  95             "\nfrom the list but it wasn't there.");
  96       }
  97       break;
  98     }
  99
 100     case Value::LIST:  // Filter out each individual thing.
 101       for (size_t i = 0; i < to_remove.list_value().size(); i++) {
 102         // TODO(brettw) if the nested item is a list, we may want to search
 103         // for the literal list rather than remote the items in it.
 104         RemoveMatchesFromList(op_node, list, to_remove.list_value()[i], err);
 105         if (err->has_error())
 106           return;
 107       }
 108       break;
 109
 110     default:
 111       break;
 112   }
 113 }
 114
 115 // Assignment -----------------------------------------------------------------
 116
 117 // We return a null value from this rather than the result of doing the append.
 118 // See ValuePlusEquals for rationale.
 119 Value ExecuteEquals(Scope* scope,
 120                     const BinaryOpNode* op_node,
 121                     const Token& left,
 122                     const Value& right,
 123                     Err* err) {
 124   const Value* old_value = scope->GetValue(left.value(), false);
 125   if (old_value) {
 126     // Throw an error when overwriting a nonempty list with another nonempty
 127     // list item. This is to detect the case where you write
 128     //   defines = ["FOO"]
 129     // and you overwrote inherited ones, when instead you mean to append:
 130     //   defines += ["FOO"]
 131     if (old_value->type() == Value::LIST &&
 132         !old_value->list_value().empty() &&
 133         right.type() == Value::LIST &&
 134         !right.list_value().empty()) {
 135       *err = Err(op_node->left()->GetRange(), "Replacing nonempty list.",
 136           std::string("This overwrites a previously-defined nonempty list ") +
 137           "(length " +
 138           base::IntToString(static_cast<int>(old_value->list_value().size()))
 139           + ").");
 140       err->AppendSubErr(Err(*old_value, "for previous definition",
 141           "with another one (length " +
 142           base::IntToString(static_cast<int>(right.list_value().size())) +
 143           "). Did you mean " +
 144           "\"+=\" to append instead? If you\nreally want to do this, do\n  " +
 145           left.value().as_string() + " = []\nbefore reassigning."));
 146       return Value();
 147     }
 148   }
 149   if (err->has_error())
 150     return Value();
 151
 152   if (right.type() == Value::LIST && left.value() == kSourcesName) {
 153     // Assigning to sources, filter the list. Here we do the filtering and
 154     // copying in one step to save an extra list copy (the lists may be
 155     // long).
 156     Value* set_value = scope->SetValue(left.value(),
 157                                        Value(op_node, Value::LIST), op_node);
 158     set_value->list_value().reserve(right.list_value().size());
 159     AppendFilteredSourcesToValue(scope, right, set_value);
 160   } else {
 161     // Normal value set, just copy it.
 162     scope->SetValue(left.value(), right, op_node->right());
 163   }
 164   return Value();
 165 }
 166
 167 // allow_type_conversion indicates if we're allowed to change the type of the
 168 // left value. This is set to true when doing +, and false when doing +=.
 169 //
 170 // Note that we return Value() from here, which is different than C++. This
 171 // means you can't do clever things like foo = [ bar += baz ] to simultaneously
 172 // append to and use a value. This is basically never needed in out build
 173 // scripts and is just as likely an error as the intended behavior, and it also
 174 // involves a copy of the value when it's returned. Many times we're appending
 175 // to large lists, and copying the value to discard it for the next statement
 176 // is very wasteful.
 177 void ValuePlusEquals(const Scope* scope,
 178                      const BinaryOpNode* op_node,
 179                      const Token& left_token,
 180                      Value* left,
 181                      const Value& right,
 182                      bool allow_type_conversion,
 183                      Err* err) {
 184   switch (left->type()) {
 185     // Left-hand-side int.
 186     case Value::INTEGER:
 187       switch (right.type()) {
 188         case Value::INTEGER:  // int + int -> addition.
 189           left->int_value() += right.int_value();
 190           return;
 191
 192         case Value::STRING:  // int + string -> string concat.
 193           if (allow_type_conversion) {
 194             *left = Value(op_node,
 195                 base::Int64ToString(left->int_value()) + right.string_value());
 196             return;
 197           }
 198           break;
 199
 200         default:
 201           break;
 202       }
 203       break;
 204
 205     // Left-hand-side string.
 206     case Value::STRING:
 207       switch (right.type()) {
 208         case Value::INTEGER:  // string + int -> string concat.
 209           left->string_value().append(base::Int64ToString(right.int_value()));
 210           return;
 211
 212         case Value::STRING:  // string + string -> string contat.
 213           left->string_value().append(right.string_value());
 214           return;
 215
 216         default:
 217           break;
 218       }
 219       break;
 220
 221     // Left-hand-side list.
 222     case Value::LIST:
 223       switch (right.type()) {
 224         case Value::LIST:  // list + list -> list concat.
 225           if (left_token.value() == kSourcesName) {
 226             // Filter additions through the assignment filter.
 227             AppendFilteredSourcesToValue(scope, right, left);
 228           } else {
 229             // Normal list concat.
 230             for (const auto& value : right.list_value())
 231               left->list_value().push_back(value);
 232           }
 233           return;
 234
 235         default:
 236           *err = Err(op_node->op(), "Incompatible types to add.",
 237               "To append a single item to a list do \"foo += [ bar ]\".");
 238           return;
 239       }
 240
 241     default:
 242       break;
 243   }
 244
 245   *err = Err(op_node->op(), "Incompatible types to add.",
 246       std::string("I see a ") + Value::DescribeType(left->type()) + " and a " +
 247       Value::DescribeType(right.type()) + ".");
 248 }
 249
 250 Value ExecutePlusEquals(Scope* scope,
 251                         const BinaryOpNode* op_node,
 252                         const Token& left,
 253                         const Value& right,
 254                         Err* err) {
 255   // We modify in-place rather than doing read-modify-write to avoid
 256   // copying large lists.
 257   Value* left_value =
 258       scope->GetValueForcedToCurrentScope(left.value(), op_node);
 259   if (!left_value) {
 260     *err = Err(left, "Undefined variable for +=.",
 261         "I don't have something with this name in scope now.");
 262     return Value();
 263   }
 264   ValuePlusEquals(scope, op_node, left, left_value, right, false, err);
 265   left_value->set_origin(op_node);
 266   scope->MarkUnused(left.value());
 267   return Value();
 268 }
 269
 270 // We return a null value from this rather than the result of doing the append.
 271 // See ValuePlusEquals for rationale.
 272 void ValueMinusEquals(const BinaryOpNode* op_node,
 273                       Value* left,
 274                       const Value& right,
 275                       bool allow_type_conversion,
 276                       Err* err) {
 277   switch (left->type()) {
 278     // Left-hand-side int.
 279     case Value::INTEGER:
 280       switch (right.type()) {
 281         case Value::INTEGER:  // int - int -> subtraction.
 282           left->int_value() -= right.int_value();
 283           return;
 284
 285         default:
 286           break;
 287       }
 288       break;
 289
 290     // Left-hand-side string.
 291     case Value::STRING:
 292       break;  // All are errors.
 293
 294     // Left-hand-side list.
 295     case Value::LIST:
 296       if (right.type() != Value::LIST) {
 297         *err = Err(op_node->op(), "Incompatible types to subtract.",
 298             "To remove a single item from a list do \"foo -= [ bar ]\".");
 299       } else {
 300         RemoveMatchesFromList(op_node, left, right, err);
 301       }
 302       return;
 303
 304     default:
 305       break;
 306   }
 307
 308   *err = Err(op_node->op(), "Incompatible types to subtract.",
 309       std::string("I see a ") + Value::DescribeType(left->type()) + " and a " +
 310       Value::DescribeType(right.type()) + ".");
 311 }
 312
 313 Value ExecuteMinusEquals(Scope* scope,
 314                          const BinaryOpNode* op_node,
 315                          const Token& left,
 316                          const Value& right,
 317                          Err* err) {
 318   Value* left_value =
 319       scope->GetValueForcedToCurrentScope(left.value(), op_node);
 320   if (!left_value) {
 321     *err = Err(left, "Undefined variable for -=.",
 322         "I don't have something with this name in scope now.");
 323     return Value();
 324   }
 325   ValueMinusEquals(op_node, left_value, right, false, err);
 326   left_value->set_origin(op_node);
 327   scope->MarkUnused(left.value());
 328   return Value();
 329 }
 330
 331 // Plus/Minus -----------------------------------------------------------------
 332
 333 Value ExecutePlus(Scope* scope,
 334                   const BinaryOpNode* op_node,
 335                   const Value& left,
 336                   const Value& right,
 337                   Err* err) {
 338   Value ret = left;
 339   ValuePlusEquals(scope, op_node, Token(), &ret, right, true, err);
 340   ret.set_origin(op_node);
 341   return ret;
 342 }
 343
 344 Value ExecuteMinus(Scope* scope,
 345                    const BinaryOpNode* op_node,
 346                    const Value& left,
 347                    const Value& right,
 348                    Err* err) {
 349   Value ret = left;
 350   ValueMinusEquals(op_node, &ret, right, true, err);
 351   ret.set_origin(op_node);
 352   return ret;
 353 }
 354
 355 // Comparison -----------------------------------------------------------------
 356
 357 Value ExecuteEqualsEquals(Scope* scope,
 358                           const BinaryOpNode* op_node,
 359                           const Value& left,
 360                           const Value& right,
 361                           Err* err) {
 362   if (left == right)
 363     return Value(op_node, true);
 364   return Value(op_node, false);
 365 }
 366
 367 Value ExecuteNotEquals(Scope* scope,
 368                        const BinaryOpNode* op_node,
 369                        const Value& left,
 370                        const Value& right,
 371                        Err* err) {
 372   // Evaluate in terms of ==.
 373   Value result = ExecuteEqualsEquals(scope, op_node, left, right, err);
 374   result.boolean_value() = !result.boolean_value();
 375   return result;
 376 }
 377
 378 Value FillNeedsTwoIntegersError(const BinaryOpNode* op_node,
 379                                 const Value& left,
 380                                 const Value& right,
 381                                 Err* err) {
 382   *err = Err(op_node, "Comparison requires two integers.",
 383              "This operator can only compare two integers.");
 384   err->AppendRange(left.origin()->GetRange());
 385   err->AppendRange(right.origin()->GetRange());
 386   return Value();
 387 }
 388
 389 Value ExecuteLessEquals(Scope* scope,
 390                         const BinaryOpNode* op_node,
 391                         const Value& left,
 392                         const Value& right,
 393                         Err* err) {
 394   if (left.type() != Value::INTEGER || right.type() != Value::INTEGER)
 395     return FillNeedsTwoIntegersError(op_node, left, right, err);
 396   return Value(op_node, left.int_value() <= right.int_value());
 397 }
 398
 399 Value ExecuteGreaterEquals(Scope* scope,
 400                            const BinaryOpNode* op_node,
 401                            const Value& left,
 402                            const Value& right,
 403                            Err* err) {
 404   if (left.type() != Value::INTEGER || right.type() != Value::INTEGER)
 405     return FillNeedsTwoIntegersError(op_node, left, right, err);
 406   return Value(op_node, left.int_value() >= right.int_value());
 407 }
 408
 409 Value ExecuteGreater(Scope* scope,
 410                      const BinaryOpNode* op_node,
 411                      const Value& left,
 412                      const Value& right,
 413                      Err* err) {
 414   if (left.type() != Value::INTEGER || right.type() != Value::INTEGER)
 415     return FillNeedsTwoIntegersError(op_node, left, right, err);
 416   return Value(op_node, left.int_value() > right.int_value());
 417 }
 418
 419 Value ExecuteLess(Scope* scope,
 420                   const BinaryOpNode* op_node,
 421                   const Value& left,
 422                   const Value& right,
 423                   Err* err) {
 424   if (left.type() != Value::INTEGER || right.type() != Value::INTEGER)
 425     return FillNeedsTwoIntegersError(op_node, left, right, err);
 426   return Value(op_node, left.int_value() < right.int_value());
 427 }
 428
 429 // Binary ----------------------------------------------------------------------
 430
 431 Value ExecuteOr(Scope* scope,
 432                 const BinaryOpNode* op_node,
 433                 const ParseNode* left_node,
 434                 const ParseNode* right_node,
 435                 Err* err) {
 436   Value left = GetValueOrFillError(op_node, left_node, "left", scope, err);
 437   if (err->has_error())
 438     return Value();
 439   if (left.type() != Value::BOOLEAN) {
 440     *err = Err(op_node->left(), "Left side of || operator is not a boolean.",
 441         "Type is \"" + std::string(Value::DescribeType(left.type())) +
 442         "\" instead.");
 443     return Value();
 444   }
 445   if (left.boolean_value())
 446     return Value(op_node, left.boolean_value());
 447
 448   Value right = GetValueOrFillError(op_node, right_node, "right", scope, err);
 449   if (err->has_error())
 450     return Value();
 451   if (right.type() != Value::BOOLEAN) {
 452     *err = Err(op_node->right(), "Right side of || operator is not a boolean.",
 453         "Type is \"" + std::string(Value::DescribeType(right.type())) +
 454         "\" instead.");
 455     return Value();
 456   }
 457
 458   return Value(op_node, left.boolean_value() || right.boolean_value());
 459 }
 460
 461 Value ExecuteAnd(Scope* scope,
 462                  const BinaryOpNode* op_node,
 463                  const ParseNode* left_node,
 464                  const ParseNode* right_node,
 465                  Err* err) {
 466   Value left = GetValueOrFillError(op_node, left_node, "left", scope, err);
 467   if (err->has_error())
 468     return Value();
 469   if (left.type() != Value::BOOLEAN) {
 470     *err = Err(op_node->left(), "Left side of && operator is not a boolean.",
 471         "Type is \"" + std::string(Value::DescribeType(left.type())) +
 472         "\" instead.");
 473     return Value();
 474   }
 475   if (!left.boolean_value())
 476     return Value(op_node, left.boolean_value());
 477
 478   Value right = GetValueOrFillError(op_node, right_node, "right", scope, err);
 479   if (err->has_error())
 480     return Value();
 481   if (right.type() != Value::BOOLEAN) {
 482     *err = Err(op_node->right(), "Right side of && operator is not a boolean.",
 483         "Type is \"" + std::string(Value::DescribeType(right.type())) +
 484         "\" instead.");
 485     return Value();
 486   }
 487   return Value(op_node, left.boolean_value() && right.boolean_value());
 488 }
 489
 490 }  // namespace
 491
 492 // ----------------------------------------------------------------------------
 493
 494 bool IsUnaryOperator(const Token& token) {
 495   return token.type() == Token::BANG;
 496 }
 497
 498 bool IsBinaryOperator(const Token& token) {
 499   return token.type() == Token::EQUAL ||
 500          token.type() == Token::PLUS ||
 501          token.type() == Token::MINUS ||
 502          token.type() == Token::PLUS_EQUALS ||
 503          token.type() == Token::MINUS_EQUALS ||
 504          token.type() == Token::EQUAL_EQUAL ||
 505          token.type() == Token::NOT_EQUAL ||
 506          token.type() == Token::LESS_EQUAL ||
 507          token.type() == Token::GREATER_EQUAL ||
 508          token.type() == Token::LESS_THAN ||
 509          token.type() == Token::GREATER_THAN ||
 510          token.type() == Token::BOOLEAN_AND ||
 511          token.type() == Token::BOOLEAN_OR;
 512 }
 513
 514 bool IsFunctionCallArgBeginScoper(const Token& token) {
 515   return token.type() == Token::LEFT_PAREN;
 516 }
 517
 518 bool IsFunctionCallArgEndScoper(const Token& token) {
 519   return token.type() == Token::RIGHT_PAREN;
 520 }
 521
 522 bool IsScopeBeginScoper(const Token& token) {
 523   return token.type() == Token::LEFT_BRACE;
 524 }
 525
 526 bool IsScopeEndScoper(const Token& token) {
 527   return token.type() == Token::RIGHT_BRACE;
 528 }
 529
 530 Value ExecuteUnaryOperator(Scope* scope,
 531                            const UnaryOpNode* op_node,
 532                            const Value& expr,
 533                            Err* err) {
 534   DCHECK(op_node->op().type() == Token::BANG);
 535
 536   if (expr.type() != Value::BOOLEAN) {
 537     *err = Err(op_node, "Operand of ! operator is not a boolean.",
 538         "Type is \"" + std::string(Value::DescribeType(expr.type())) +
 539         "\" instead.");
 540     return Value();
 541   }
 542   // TODO(scottmg): Why no unary minus?
 543   return Value(op_node, !expr.boolean_value());
 544 }
 545
 546 Value ExecuteBinaryOperator(Scope* scope,
 547                             const BinaryOpNode* op_node,
 548                             const ParseNode* left,
 549                             const ParseNode* right,
 550                             Err* err) {
 551   const Token& op = op_node->op();
 552
 553   // First handle the ones that take an lvalue.
 554   if (op.type() == Token::EQUAL ||
 555       op.type() == Token::PLUS_EQUALS ||
 556       op.type() == Token::MINUS_EQUALS) {
 557     const IdentifierNode* left_id = left->AsIdentifier();
 558     if (!left_id) {
 559       *err = Err(op, "Operator requires a lvalue.",
 560                  "This thing on the left is not an identifier.");
 561       err->AppendRange(left->GetRange());
 562       return Value();
 563     }
 564     const Token& dest = left_id->value();
 565
 566     Value right_value = right->Execute(scope, err);
 567     if (err->has_error())
 568       return Value();
 569     if (right_value.type() == Value::NONE) {
 570       *err = Err(op, "Operator requires a rvalue.",
 571                  "This thing on the right does not evaluate to a value.");
 572       err->AppendRange(right->GetRange());
 573       return Value();
 574     }
 575
 576     if (op.type() == Token::EQUAL)
 577       return ExecuteEquals(scope, op_node, dest, right_value, err);
 578     if (op.type() == Token::PLUS_EQUALS)
 579       return ExecutePlusEquals(scope, op_node, dest, right_value, err);
 580     if (op.type() == Token::MINUS_EQUALS)
 581       return ExecuteMinusEquals(scope, op_node, dest, right_value, err);
 582     NOTREACHED();
 583     return Value();
 584   }
 585
 586   // ||, &&. Passed the node instead of the value so that they can avoid
 587   // evaluating the RHS on early-out.
 588   if (op.type() == Token::BOOLEAN_OR)
 589     return ExecuteOr(scope, op_node, left, right, err);
 590   if (op.type() == Token::BOOLEAN_AND)
 591     return ExecuteAnd(scope, op_node, left, right, err);
 592
 593   Value left_value = GetValueOrFillError(op_node, left, "left", scope, err);
 594   if (err->has_error())
 595     return Value();
 596   Value right_value = GetValueOrFillError(op_node, right, "right", scope, err);
 597   if (err->has_error())
 598     return Value();
 599
 600   // +, -.
 601   if (op.type() == Token::MINUS)
 602     return ExecuteMinus(scope, op_node, left_value, right_value, err);
 603   if (op.type() == Token::PLUS)
 604     return ExecutePlus(scope, op_node, left_value, right_value, err);
 605
 606   // Comparisons.
 607   if (op.type() == Token::EQUAL_EQUAL)
 608     return ExecuteEqualsEquals(scope, op_node, left_value, right_value, err);
 609   if (op.type() == Token::NOT_EQUAL)
 610     return ExecuteNotEquals(scope, op_node, left_value, right_value, err);
 611   if (op.type() == Token::GREATER_EQUAL)
 612     return ExecuteGreaterEquals(scope, op_node, left_value, right_value, err);
 613   if (op.type() == Token::LESS_EQUAL)
 614     return ExecuteLessEquals(scope, op_node, left_value, right_value, err);
 615   if (op.type() == Token::GREATER_THAN)
 616     return ExecuteGreater(scope, op_node, left_value, right_value, err);
 617   if (op.type() == Token::LESS_THAN)
 618     return ExecuteLess(scope, op_node, left_value, right_value, err);
 619
 620   return Value();
 621 }