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