operators.cc revision 010d83a9304c5a91596085d917d248abff47903a 
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
14namespace {
15
16const 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.
21void 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
56Value 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
75void 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.
120Value 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.
178void 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
251Value 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.
273void 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
314Value 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
334Value 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
345Value 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
358Value 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
368Value 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
379Value 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
390Value 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
400Value 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
410Value 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
420Value 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
432Value 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
462Value 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
495bool IsUnaryOperator(const Token& token) {
496  return token.type() == Token::BANG;
497}
498
499bool 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
515bool IsFunctionCallArgBeginScoper(const Token& token) {
516  return token.type() == Token::LEFT_PAREN;
517}
518
519bool IsFunctionCallArgEndScoper(const Token& token) {
520  return token.type() == Token::RIGHT_PAREN;
521}
522
523bool IsScopeBeginScoper(const Token& token) {
524  return token.type() == Token::LEFT_BRACE;
525}
526
527bool IsScopeEndScoper(const Token& token) {
528  return token.type() == Token::RIGHT_BRACE;
529}
530
531Value 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
547Value 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}
623