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/parse_tree.h"
6
7#include <string>
8
9#include "base/stl_util.h"
10#include "base/strings/string_number_conversions.h"
11#include "tools/gn/functions.h"
12#include "tools/gn/operators.h"
13#include "tools/gn/scope.h"
14#include "tools/gn/string_utils.h"
15
16namespace {
17
18std::string IndentFor(int value) {
19  return std::string(value, ' ');
20}
21
22}  // namespace
23
24Comments::Comments() {
25}
26
27Comments::~Comments() {
28}
29
30void Comments::ReverseSuffix() {
31  for (int i = 0, j = static_cast<int>(suffix_.size() - 1); i < j; ++i, --j)
32    std::swap(suffix_[i], suffix_[j]);
33}
34
35ParseNode::ParseNode() {
36}
37
38ParseNode::~ParseNode() {
39}
40
41const AccessorNode* ParseNode::AsAccessor() const { return NULL; }
42const BinaryOpNode* ParseNode::AsBinaryOp() const { return NULL; }
43const BlockNode* ParseNode::AsBlock() const { return NULL; }
44const ConditionNode* ParseNode::AsConditionNode() const { return NULL; }
45const FunctionCallNode* ParseNode::AsFunctionCall() const { return NULL; }
46const IdentifierNode* ParseNode::AsIdentifier() const { return NULL; }
47const ListNode* ParseNode::AsList() const { return NULL; }
48const LiteralNode* ParseNode::AsLiteral() const { return NULL; }
49const UnaryOpNode* ParseNode::AsUnaryOp() const { return NULL; }
50const BlockCommentNode* ParseNode::AsBlockComment() const { return NULL; }
51
52Comments* ParseNode::comments_mutable() {
53  if (!comments_)
54    comments_.reset(new Comments);
55  return comments_.get();
56}
57
58void ParseNode::PrintComments(std::ostream& out, int indent) const {
59  if (comments_) {
60    std::string ind = IndentFor(indent + 1);
61    for (std::vector<Token>::const_iterator i(comments_->before().begin());
62         i != comments_->before().end();
63         ++i) {
64      out << ind << "+BEFORE_COMMENT(\"" << i->value() << "\")\n";
65    }
66    for (std::vector<Token>::const_iterator i(comments_->suffix().begin());
67         i != comments_->suffix().end();
68         ++i) {
69      out << ind << "+SUFFIX_COMMENT(\"" << i->value() << "\")\n";
70    }
71    for (std::vector<Token>::const_iterator i(comments_->after().begin());
72         i != comments_->after().end();
73         ++i) {
74      out << ind << "+AFTER_COMMENT(\"" << i->value() << "\")\n";
75    }
76  }
77}
78
79// AccessorNode ---------------------------------------------------------------
80
81AccessorNode::AccessorNode() {
82}
83
84AccessorNode::~AccessorNode() {
85}
86
87const AccessorNode* AccessorNode::AsAccessor() const {
88  return this;
89}
90
91Value AccessorNode::Execute(Scope* scope, Err* err) const {
92  if (index_)
93    return ExecuteArrayAccess(scope, err);
94  else if (member_)
95    return ExecuteScopeAccess(scope, err);
96  NOTREACHED();
97  return Value();
98}
99
100LocationRange AccessorNode::GetRange() const {
101  if (index_)
102    return LocationRange(base_.location(), index_->GetRange().end());
103  else if (member_)
104    return LocationRange(base_.location(), member_->GetRange().end());
105  NOTREACHED();
106  return LocationRange();
107}
108
109Err AccessorNode::MakeErrorDescribing(const std::string& msg,
110                                      const std::string& help) const {
111  return Err(GetRange(), msg, help);
112}
113
114void AccessorNode::Print(std::ostream& out, int indent) const {
115  out << IndentFor(indent) << "ACCESSOR\n";
116  PrintComments(out, indent);
117  out << IndentFor(indent + 1) << base_.value() << "\n";
118  if (index_)
119    index_->Print(out, indent + 1);
120  else if (member_)
121    member_->Print(out, indent + 1);
122}
123
124Value AccessorNode::ExecuteArrayAccess(Scope* scope, Err* err) const {
125  Value index_value = index_->Execute(scope, err);
126  if (err->has_error())
127    return Value();
128  if (!index_value.VerifyTypeIs(Value::INTEGER, err))
129    return Value();
130
131  const Value* base_value = scope->GetValue(base_.value(), true);
132  if (!base_value) {
133    *err = MakeErrorDescribing("Undefined identifier.");
134    return Value();
135  }
136  if (!base_value->VerifyTypeIs(Value::LIST, err))
137    return Value();
138
139  int64 index_int = index_value.int_value();
140  if (index_int < 0) {
141    *err = Err(index_->GetRange(), "Negative array subscript.",
142        "You gave me " + base::Int64ToString(index_int) + ".");
143    return Value();
144  }
145  size_t index_sizet = static_cast<size_t>(index_int);
146  if (index_sizet >= base_value->list_value().size()) {
147    *err = Err(index_->GetRange(), "Array subscript out of range.",
148        "You gave me " + base::Int64ToString(index_int) +
149        " but I was expecting something from 0 to " +
150        base::Int64ToString(
151            static_cast<int64>(base_value->list_value().size()) - 1) +
152        ", inclusive.");
153    return Value();
154  }
155
156  // Doing this assumes that there's no way in the language to do anything
157  // between the time the reference is created and the time that the reference
158  // is used. If there is, this will crash! Currently, this is just used for
159  // array accesses where this "shouldn't" happen.
160  return base_value->list_value()[index_sizet];
161}
162
163Value AccessorNode::ExecuteScopeAccess(Scope* scope, Err* err) const {
164  // We jump through some hoops here since ideally a.b will count "b" as
165  // accessed in the given scope. The value "a" might be in some normal nested
166  // scope and we can modify it, but it might also be inherited from the
167  // readonly root scope and we can't do used variable tracking on it. (It's
168  // not legal to const cast it away since the root scope will be in readonly
169  // mode and being accessed from multiple threads without locking.) So this
170  // code handles both cases.
171  const Value* result = NULL;
172
173  // Look up the value in the scope named by "base_".
174  Value* mutable_base_value = scope->GetMutableValue(base_.value(), true);
175  if (mutable_base_value) {
176    // Common case: base value is mutable so we can track variable accesses
177    // for unused value warnings.
178    if (!mutable_base_value->VerifyTypeIs(Value::SCOPE, err))
179      return Value();
180    result = mutable_base_value->scope_value()->GetValue(
181        member_->value().value(), true);
182  } else {
183    // Fall back to see if the value is on a read-only scope.
184    const Value* const_base_value = scope->GetValue(base_.value(), true);
185    if (const_base_value) {
186      // Read only value, don't try to mark the value access as a "used" one.
187      if (!const_base_value->VerifyTypeIs(Value::SCOPE, err))
188        return Value();
189      result =
190          const_base_value->scope_value()->GetValue(member_->value().value());
191    } else {
192      *err = Err(base_, "Undefined identifier.");
193      return Value();
194    }
195  }
196
197  if (!result) {
198    *err = Err(member_.get(), "No value named \"" +
199        member_->value().value() + "\" in scope \"" + base_.value() + "\"");
200    return Value();
201  }
202  return *result;
203}
204
205// BinaryOpNode ---------------------------------------------------------------
206
207BinaryOpNode::BinaryOpNode() {
208}
209
210BinaryOpNode::~BinaryOpNode() {
211}
212
213const BinaryOpNode* BinaryOpNode::AsBinaryOp() const {
214  return this;
215}
216
217Value BinaryOpNode::Execute(Scope* scope, Err* err) const {
218  return ExecuteBinaryOperator(scope, this, left_.get(), right_.get(), err);
219}
220
221LocationRange BinaryOpNode::GetRange() const {
222  return left_->GetRange().Union(right_->GetRange());
223}
224
225Err BinaryOpNode::MakeErrorDescribing(const std::string& msg,
226                                      const std::string& help) const {
227  return Err(op_, msg, help);
228}
229
230void BinaryOpNode::Print(std::ostream& out, int indent) const {
231  out << IndentFor(indent) << "BINARY(" << op_.value() << ")\n";
232  PrintComments(out, indent);
233  left_->Print(out, indent + 1);
234  right_->Print(out, indent + 1);
235}
236
237// BlockNode ------------------------------------------------------------------
238
239BlockNode::BlockNode(bool has_scope) : has_scope_(has_scope) {
240}
241
242BlockNode::~BlockNode() {
243  STLDeleteContainerPointers(statements_.begin(), statements_.end());
244}
245
246const BlockNode* BlockNode::AsBlock() const {
247  return this;
248}
249
250Value BlockNode::Execute(Scope* containing_scope, Err* err) const {
251  if (has_scope_) {
252    Scope our_scope(containing_scope);
253    Value ret = ExecuteBlockInScope(&our_scope, err);
254    if (err->has_error())
255      return Value();
256
257    // Check for unused vars in the scope.
258    our_scope.CheckForUnusedVars(err);
259    return ret;
260  }
261  return ExecuteBlockInScope(containing_scope, err);
262}
263
264LocationRange BlockNode::GetRange() const {
265  if (begin_token_.type() != Token::INVALID &&
266      end_token_.type() != Token::INVALID) {
267    return begin_token_.range().Union(end_token_.range());
268  } else if (!statements_.empty()) {
269    return statements_[0]->GetRange().Union(
270        statements_[statements_.size() - 1]->GetRange());
271  }
272  return LocationRange();
273}
274
275Err BlockNode::MakeErrorDescribing(const std::string& msg,
276                                   const std::string& help) const {
277  return Err(GetRange(), msg, help);
278}
279
280void BlockNode::Print(std::ostream& out, int indent) const {
281  out << IndentFor(indent) << "BLOCK\n";
282  PrintComments(out, indent);
283  for (size_t i = 0; i < statements_.size(); i++)
284    statements_[i]->Print(out, indent + 1);
285}
286
287Value BlockNode::ExecuteBlockInScope(Scope* our_scope, Err* err) const {
288  for (size_t i = 0; i < statements_.size() && !err->has_error(); i++) {
289    // Check for trying to execute things with no side effects in a block.
290    const ParseNode* cur = statements_[i];
291    if (cur->AsList() || cur->AsLiteral() || cur->AsUnaryOp() ||
292        cur->AsIdentifier()) {
293      *err = cur->MakeErrorDescribing(
294          "This statement has no effect.",
295          "Either delete it or do something with the result.");
296      return Value();
297    }
298    cur->Execute(our_scope, err);
299  }
300  return Value();
301}
302
303// ConditionNode --------------------------------------------------------------
304
305ConditionNode::ConditionNode() {
306}
307
308ConditionNode::~ConditionNode() {
309}
310
311const ConditionNode* ConditionNode::AsConditionNode() const {
312  return this;
313}
314
315Value ConditionNode::Execute(Scope* scope, Err* err) const {
316  Value condition_result = condition_->Execute(scope, err);
317  if (err->has_error())
318    return Value();
319  if (condition_result.type() != Value::BOOLEAN) {
320    *err = condition_->MakeErrorDescribing(
321        "Condition does not evaluate to a boolean value.",
322        std::string("This is a value of type \"") +
323            Value::DescribeType(condition_result.type()) +
324            "\" instead.");
325    err->AppendRange(if_token_.range());
326    return Value();
327  }
328
329  if (condition_result.boolean_value()) {
330    if_true_->ExecuteBlockInScope(scope, err);
331  } else if (if_false_) {
332    // The else block is optional. It's either another condition (for an
333    // "else if" and we can just Execute it and the condition will handle
334    // the scoping) or it's a block indicating an "else" in which ase we
335    // need to be sure it inherits our scope.
336    const BlockNode* if_false_block = if_false_->AsBlock();
337    if (if_false_block)
338      if_false_block->ExecuteBlockInScope(scope, err);
339    else
340      if_false_->Execute(scope, err);
341  }
342
343  return Value();
344}
345
346LocationRange ConditionNode::GetRange() const {
347  if (if_false_)
348    return if_token_.range().Union(if_false_->GetRange());
349  return if_token_.range().Union(if_true_->GetRange());
350}
351
352Err ConditionNode::MakeErrorDescribing(const std::string& msg,
353                                       const std::string& help) const {
354  return Err(if_token_, msg, help);
355}
356
357void ConditionNode::Print(std::ostream& out, int indent) const {
358  out << IndentFor(indent) << "CONDITION\n";
359  PrintComments(out, indent);
360  condition_->Print(out, indent + 1);
361  if_true_->Print(out, indent + 1);
362  if (if_false_)
363    if_false_->Print(out, indent + 1);
364}
365
366// FunctionCallNode -----------------------------------------------------------
367
368FunctionCallNode::FunctionCallNode() {
369}
370
371FunctionCallNode::~FunctionCallNode() {
372}
373
374const FunctionCallNode* FunctionCallNode::AsFunctionCall() const {
375  return this;
376}
377
378Value FunctionCallNode::Execute(Scope* scope, Err* err) const {
379  return functions::RunFunction(scope, this, args_.get(), block_.get(), err);
380}
381
382LocationRange FunctionCallNode::GetRange() const {
383  if (function_.type() == Token::INVALID)
384    return LocationRange();  // This will be null in some tests.
385  if (block_)
386    return function_.range().Union(block_->GetRange());
387  return function_.range().Union(args_->GetRange());
388}
389
390Err FunctionCallNode::MakeErrorDescribing(const std::string& msg,
391                                          const std::string& help) const {
392  return Err(function_, msg, help);
393}
394
395void FunctionCallNode::Print(std::ostream& out, int indent) const {
396  out << IndentFor(indent) << "FUNCTION(" << function_.value() << ")\n";
397  PrintComments(out, indent);
398  args_->Print(out, indent + 1);
399  if (block_)
400    block_->Print(out, indent + 1);
401}
402
403// IdentifierNode --------------------------------------------------------------
404
405IdentifierNode::IdentifierNode() {
406}
407
408IdentifierNode::IdentifierNode(const Token& token) : value_(token) {
409}
410
411IdentifierNode::~IdentifierNode() {
412}
413
414const IdentifierNode* IdentifierNode::AsIdentifier() const {
415  return this;
416}
417
418Value IdentifierNode::Execute(Scope* scope, Err* err) const {
419  const Value* value = scope->GetValue(value_.value(), true);
420  Value result;
421  if (!value) {
422    *err = MakeErrorDescribing("Undefined identifier");
423    return result;
424  }
425
426  result = *value;
427  result.set_origin(this);
428  return result;
429}
430
431LocationRange IdentifierNode::GetRange() const {
432  return value_.range();
433}
434
435Err IdentifierNode::MakeErrorDescribing(const std::string& msg,
436                                        const std::string& help) const {
437  return Err(value_, msg, help);
438}
439
440void IdentifierNode::Print(std::ostream& out, int indent) const {
441  out << IndentFor(indent) << "IDENTIFIER(" << value_.value() << ")\n";
442  PrintComments(out, indent);
443}
444
445// ListNode -------------------------------------------------------------------
446
447ListNode::ListNode() {
448}
449
450ListNode::~ListNode() {
451  STLDeleteContainerPointers(contents_.begin(), contents_.end());
452}
453
454const ListNode* ListNode::AsList() const {
455  return this;
456}
457
458Value ListNode::Execute(Scope* scope, Err* err) const {
459  Value result_value(this, Value::LIST);
460  std::vector<Value>& results = result_value.list_value();
461  results.reserve(contents_.size());
462
463  for (size_t i = 0; i < contents_.size(); i++) {
464    const ParseNode* cur = contents_[i];
465    if (cur->AsBlockComment())
466      continue;
467    results.push_back(cur->Execute(scope, err));
468    if (err->has_error())
469      return Value();
470    if (results.back().type() == Value::NONE) {
471      *err = cur->MakeErrorDescribing(
472          "This does not evaluate to a value.",
473          "I can't do something with nothing.");
474      return Value();
475    }
476  }
477  return result_value;
478}
479
480LocationRange ListNode::GetRange() const {
481  return LocationRange(begin_token_.location(), end_token_.location());
482}
483
484Err ListNode::MakeErrorDescribing(const std::string& msg,
485                                  const std::string& help) const {
486  return Err(begin_token_, msg, help);
487}
488
489void ListNode::Print(std::ostream& out, int indent) const {
490  out << IndentFor(indent) << "LIST\n";
491  PrintComments(out, indent);
492  for (size_t i = 0; i < contents_.size(); i++)
493    contents_[i]->Print(out, indent + 1);
494}
495
496// LiteralNode -----------------------------------------------------------------
497
498LiteralNode::LiteralNode() {
499}
500
501LiteralNode::LiteralNode(const Token& token) : value_(token) {
502}
503
504LiteralNode::~LiteralNode() {
505}
506
507const LiteralNode* LiteralNode::AsLiteral() const {
508  return this;
509}
510
511Value LiteralNode::Execute(Scope* scope, Err* err) const {
512  switch (value_.type()) {
513    case Token::TRUE_TOKEN:
514      return Value(this, true);
515    case Token::FALSE_TOKEN:
516      return Value(this, false);
517    case Token::INTEGER: {
518      int64 result_int;
519      if (!base::StringToInt64(value_.value(), &result_int)) {
520        *err = MakeErrorDescribing("This does not look like an integer");
521        return Value();
522      }
523      return Value(this, result_int);
524    }
525    case Token::STRING: {
526      Value v(this, Value::STRING);
527      ExpandStringLiteral(scope, value_, &v, err);
528      return v;
529    }
530    default:
531      NOTREACHED();
532      return Value();
533  }
534}
535
536LocationRange LiteralNode::GetRange() const {
537  return value_.range();
538}
539
540Err LiteralNode::MakeErrorDescribing(const std::string& msg,
541                                     const std::string& help) const {
542  return Err(value_, msg, help);
543}
544
545void LiteralNode::Print(std::ostream& out, int indent) const {
546  out << IndentFor(indent) << "LITERAL(" << value_.value() << ")\n";
547  PrintComments(out, indent);
548}
549
550// UnaryOpNode ----------------------------------------------------------------
551
552UnaryOpNode::UnaryOpNode() {
553}
554
555UnaryOpNode::~UnaryOpNode() {
556}
557
558const UnaryOpNode* UnaryOpNode::AsUnaryOp() const {
559  return this;
560}
561
562Value UnaryOpNode::Execute(Scope* scope, Err* err) const {
563  Value operand_value = operand_->Execute(scope, err);
564  if (err->has_error())
565    return Value();
566  return ExecuteUnaryOperator(scope, this, operand_value, err);
567}
568
569LocationRange UnaryOpNode::GetRange() const {
570  return op_.range().Union(operand_->GetRange());
571}
572
573Err UnaryOpNode::MakeErrorDescribing(const std::string& msg,
574                                     const std::string& help) const {
575  return Err(op_, msg, help);
576}
577
578void UnaryOpNode::Print(std::ostream& out, int indent) const {
579  out << IndentFor(indent) << "UNARY(" << op_.value() << ")\n";
580  PrintComments(out, indent);
581  operand_->Print(out, indent + 1);
582}
583
584// BlockCommentNode ------------------------------------------------------------
585
586BlockCommentNode::BlockCommentNode() {
587}
588
589BlockCommentNode::~BlockCommentNode() {
590}
591
592const BlockCommentNode* BlockCommentNode::AsBlockComment() const {
593  return this;
594}
595
596Value BlockCommentNode::Execute(Scope* scope, Err* err) const {
597  return Value();
598}
599
600LocationRange BlockCommentNode::GetRange() const {
601  return comment_.range();
602}
603
604Err BlockCommentNode::MakeErrorDescribing(const std::string& msg,
605                                          const std::string& help) const {
606  return Err(comment_, msg, help);
607}
608
609void BlockCommentNode::Print(std::ostream& out, int indent) const {
610  out << IndentFor(indent) << "BLOCK_COMMENT(" << comment_.value() << ")\n";
611  PrintComments(out, indent);
612}
613