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