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