operators.cc revision 5d1f7b1de12d16ceb2c938c56701a3e8bfa558f7 
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(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
428Value 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
447bool IsUnaryOperator(const Token& token) {
448  return token.type() == Token::BANG;
449}
450
451bool 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
467bool IsFunctionCallArgBeginScoper(const Token& token) {
468  return token.type() == Token::LEFT_PAREN;
469}
470
471bool IsFunctionCallArgEndScoper(const Token& token) {
472  return token.type() == Token::RIGHT_PAREN;
473}
474
475bool IsScopeBeginScoper(const Token& token) {
476  return token.type() == Token::LEFT_BRACE;
477}
478
479bool IsScopeEndScoper(const Token& token) {
480  return token.type() == Token::RIGHT_BRACE;
481}
482
483Value 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
498Value 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}
589