operators.cc revision c5cede9ae108bb15f6b7a8aea21c7e1fefa2834c 
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
56void 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.
101Value 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.
159void 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
232Value 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.
254void 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
295Value 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
315Value 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
326Value 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
339Value 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
349Value 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
360Value 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
371Value 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
381Value 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
391Value 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
401Value 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
413Value 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(op_node->left(), "Left side of || operator is not a boolean.",
420        "Type is \"" + std::string(Value::DescribeType(left.type())) +
421        "\" instead.");
422    return Value();
423  } else if (right.type() != Value::BOOLEAN) {
424    *err = Err(op_node->right(), "Right side of || operator is not a boolean.",
425        "Type is \"" + std::string(Value::DescribeType(right.type())) +
426        "\" instead.");
427    return Value();
428  }
429  return Value(op_node, left.boolean_value() || right.boolean_value());
430}
431
432Value ExecuteAnd(Scope* scope,
433                 const BinaryOpNode* op_node,
434                 const Value& left,
435                 const Value& right,
436                 Err* err) {
437  if (left.type() != Value::BOOLEAN) {
438    *err = Err(op_node->left(), "Left side of && operator is not a boolean.",
439        "Type is \"" + std::string(Value::DescribeType(left.type())) +
440        "\" instead.");
441    return Value();
442  } else if (right.type() != Value::BOOLEAN) {
443    *err = Err(op_node->right(), "Right side of && operator is not a boolean.",
444        "Type is \"" + std::string(Value::DescribeType(right.type())) +
445        "\" instead.");
446    return Value();
447  }
448  return Value(op_node, left.boolean_value() && right.boolean_value());
449}
450
451}  // namespace
452
453// ----------------------------------------------------------------------------
454
455bool IsUnaryOperator(const Token& token) {
456  return token.type() == Token::BANG;
457}
458
459bool IsBinaryOperator(const Token& token) {
460  return token.type() == Token::EQUAL ||
461         token.type() == Token::PLUS ||
462         token.type() == Token::MINUS ||
463         token.type() == Token::PLUS_EQUALS ||
464         token.type() == Token::MINUS_EQUALS ||
465         token.type() == Token::EQUAL_EQUAL ||
466         token.type() == Token::NOT_EQUAL ||
467         token.type() == Token::LESS_EQUAL ||
468         token.type() == Token::GREATER_EQUAL ||
469         token.type() == Token::LESS_THAN ||
470         token.type() == Token::GREATER_THAN ||
471         token.type() == Token::BOOLEAN_AND ||
472         token.type() == Token::BOOLEAN_OR;
473}
474
475bool IsFunctionCallArgBeginScoper(const Token& token) {
476  return token.type() == Token::LEFT_PAREN;
477}
478
479bool IsFunctionCallArgEndScoper(const Token& token) {
480  return token.type() == Token::RIGHT_PAREN;
481}
482
483bool IsScopeBeginScoper(const Token& token) {
484  return token.type() == Token::LEFT_BRACE;
485}
486
487bool IsScopeEndScoper(const Token& token) {
488  return token.type() == Token::RIGHT_BRACE;
489}
490
491Value ExecuteUnaryOperator(Scope* scope,
492                           const UnaryOpNode* op_node,
493                           const Value& expr,
494                           Err* err) {
495  DCHECK(op_node->op().type() == Token::BANG);
496
497  if (expr.type() != Value::BOOLEAN) {
498    *err = Err(op_node, "Operand of ! operator is not a boolean.",
499        "Type is \"" + std::string(Value::DescribeType(expr.type())) +
500        "\" instead.");
501    return Value();
502  }
503  // TODO(scottmg): Why no unary minus?
504  return Value(op_node, !expr.boolean_value());
505}
506
507Value ExecuteBinaryOperator(Scope* scope,
508                            const BinaryOpNode* op_node,
509                            const ParseNode* left,
510                            const ParseNode* right,
511                            Err* err) {
512  const Token& op = op_node->op();
513
514  // First handle the ones that take an lvalue.
515  if (op.type() == Token::EQUAL ||
516      op.type() == Token::PLUS_EQUALS ||
517      op.type() == Token::MINUS_EQUALS) {
518    const IdentifierNode* left_id = left->AsIdentifier();
519    if (!left_id) {
520      *err = Err(op, "Operator requires a lvalue.",
521                 "This thing on the left is not an identifier.");
522      err->AppendRange(left->GetRange());
523      return Value();
524    }
525    const Token& dest = left_id->value();
526
527    Value right_value = right->Execute(scope, err);
528    if (err->has_error())
529      return Value();
530    if (right_value.type() == Value::NONE) {
531      *err = Err(op, "Operator requires a rvalue.",
532                 "This thing on the right does not evaluate to a value.");
533      err->AppendRange(right->GetRange());
534      return Value();
535    }
536
537    if (op.type() == Token::EQUAL)
538      return ExecuteEquals(scope, op_node, dest, right_value, err);
539    if (op.type() == Token::PLUS_EQUALS)
540      return ExecutePlusEquals(scope, op_node, dest, right_value, err);
541    if (op.type() == Token::MINUS_EQUALS)
542      return ExecuteMinusEquals(scope, op_node, dest, right_value, err);
543    NOTREACHED();
544    return Value();
545  }
546
547  // Left value.
548  Value left_value = left->Execute(scope, err);
549  if (err->has_error())
550    return Value();
551  if (left_value.type() == Value::NONE) {
552    *err = Err(op, "Operator requires a value.",
553               "This thing on the left does not evaluate to a value.");
554    err->AppendRange(left->GetRange());
555    return Value();
556  }
557
558  // Right value. Note: don't move this above to share code with the lvalue
559  // version since in this case we want to execute the left side first.
560  Value right_value = right->Execute(scope, err);
561  if (err->has_error())
562    return Value();
563  if (right_value.type() == Value::NONE) {
564    *err = Err(op, "Operator requires a value.",
565               "This thing on the right does not evaluate to a value.");
566    err->AppendRange(right->GetRange());
567    return Value();
568  }
569
570  // +, -.
571  if (op.type() == Token::MINUS)
572    return ExecuteMinus(scope, op_node, left_value, right_value, err);
573  if (op.type() == Token::PLUS)
574    return ExecutePlus(scope, op_node, left_value, right_value, err);
575
576  // Comparisons.
577  if (op.type() == Token::EQUAL_EQUAL)
578    return ExecuteEqualsEquals(scope, op_node, left_value, right_value, err);
579  if (op.type() == Token::NOT_EQUAL)
580    return ExecuteNotEquals(scope, op_node, left_value, right_value, err);
581  if (op.type() == Token::GREATER_EQUAL)
582    return ExecuteGreaterEquals(scope, op_node, left_value, right_value, err);
583  if (op.type() == Token::LESS_EQUAL)
584    return ExecuteLessEquals(scope, op_node, left_value, right_value, err);
585  if (op.type() == Token::GREATER_THAN)
586    return ExecuteGreater(scope, op_node, left_value, right_value, err);
587  if (op.type() == Token::LESS_THAN)
588    return ExecuteLess(scope, op_node, left_value, right_value, err);
589
590  // ||, &&.
591  if (op.type() == Token::BOOLEAN_OR)
592    return ExecuteOr(scope, op_node, left_value, right_value, err);
593  if (op.type() == Token::BOOLEAN_AND)
594    return ExecuteAnd(scope, op_node, left_value, right_value, err);
595
596  return Value();
597}
598