| // Copyright 2015 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef V8_PARSING_EXPRESSION_CLASSIFIER_H_ |
| #define V8_PARSING_EXPRESSION_CLASSIFIER_H_ |
| |
| #include "src/messages.h" |
| #include "src/parsing/scanner.h" |
| #include "src/zone/zone-containers.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| class DuplicateFinder; |
| |
| #define ERROR_CODES(T) \ |
| T(ExpressionProduction, 0) \ |
| T(FormalParameterInitializerProduction, 1) \ |
| T(BindingPatternProduction, 2) \ |
| T(AssignmentPatternProduction, 3) \ |
| T(DistinctFormalParametersProduction, 4) \ |
| T(StrictModeFormalParametersProduction, 5) \ |
| T(ArrowFormalParametersProduction, 6) \ |
| T(LetPatternProduction, 7) \ |
| T(AsyncArrowFormalParametersProduction, 8) |
| |
| // Expression classifiers serve two purposes: |
| // |
| // 1) They keep track of error messages that are pending (and other |
| // related information), waiting for the parser to decide whether |
| // the parsed expression is a pattern or not. |
| // 2) They keep track of expressions that may need to be rewritten, if |
| // the parser decides that they are not patterns. (A different |
| // mechanism implements the rewriting of patterns.) |
| // |
| // Expression classifiers are used by the parser in a stack fashion. |
| // Each new classifier is pushed on top of the stack. This happens |
| // automatically by the class's constructor. While on top of the |
| // stack, the classifier records pending error messages and tracks the |
| // pending non-patterns of the expression that is being parsed. |
| // |
| // At the end of its life, a classifier is either "accumulated" to the |
| // one that is below it on the stack, or is "discarded". The former |
| // is achieved by calling the method Accumulate. The latter is |
| // achieved automatically by the destructor, but it can happen earlier |
| // by calling the method Discard. Both actions result in removing the |
| // classifier from the parser's stack. |
| |
| template <typename Types> |
| class ExpressionClassifier { |
| public: |
| enum ErrorKind : unsigned { |
| #define DEFINE_ERROR_KIND(NAME, CODE) k##NAME = CODE, |
| ERROR_CODES(DEFINE_ERROR_KIND) |
| #undef DEFINE_ERROR_KIND |
| kUnusedError = 15 // Larger than error codes; should fit in 4 bits |
| }; |
| |
| struct Error { |
| V8_INLINE Error() |
| : location(Scanner::Location::invalid()), |
| message(MessageTemplate::kNone), |
| kind(kUnusedError), |
| arg(nullptr) {} |
| V8_INLINE explicit Error(Scanner::Location loc, |
| MessageTemplate::Template msg, ErrorKind k, |
| const char* a = nullptr) |
| : location(loc), message(msg), kind(k), arg(a) {} |
| |
| Scanner::Location location; |
| MessageTemplate::Template message : 28; |
| unsigned kind : 4; |
| const char* arg; |
| }; |
| |
| // clang-format off |
| enum TargetProduction : unsigned { |
| #define DEFINE_PRODUCTION(NAME, CODE) NAME = 1 << CODE, |
| ERROR_CODES(DEFINE_PRODUCTION) |
| #undef DEFINE_PRODUCTION |
| |
| #define DEFINE_ALL_PRODUCTIONS(NAME, CODE) NAME | |
| AllProductions = ERROR_CODES(DEFINE_ALL_PRODUCTIONS) /* | */ 0 |
| #undef DEFINE_ALL_PRODUCTIONS |
| }; |
| // clang-format on |
| |
| explicit ExpressionClassifier(typename Types::Base* base, |
| DuplicateFinder* duplicate_finder = nullptr) |
| : base_(base), |
| previous_(base->classifier_), |
| zone_(base->impl()->zone()), |
| reported_errors_(base->impl()->GetReportedErrorList()), |
| duplicate_finder_(duplicate_finder), |
| invalid_productions_(0), |
| is_non_simple_parameter_list_(0) { |
| base->classifier_ = this; |
| reported_errors_begin_ = reported_errors_end_ = reported_errors_->size(); |
| } |
| |
| V8_INLINE ~ExpressionClassifier() { |
| Discard(); |
| if (base_->classifier_ == this) base_->classifier_ = previous_; |
| } |
| |
| V8_INLINE bool is_valid(unsigned productions) const { |
| return (invalid_productions_ & productions) == 0; |
| } |
| |
| V8_INLINE DuplicateFinder* duplicate_finder() const { |
| return duplicate_finder_; |
| } |
| |
| V8_INLINE bool is_valid_expression() const { |
| return is_valid(ExpressionProduction); |
| } |
| |
| V8_INLINE bool is_valid_formal_parameter_initializer() const { |
| return is_valid(FormalParameterInitializerProduction); |
| } |
| |
| V8_INLINE bool is_valid_binding_pattern() const { |
| return is_valid(BindingPatternProduction); |
| } |
| |
| V8_INLINE bool is_valid_assignment_pattern() const { |
| return is_valid(AssignmentPatternProduction); |
| } |
| |
| V8_INLINE bool is_valid_arrow_formal_parameters() const { |
| return is_valid(ArrowFormalParametersProduction); |
| } |
| |
| V8_INLINE bool is_valid_formal_parameter_list_without_duplicates() const { |
| return is_valid(DistinctFormalParametersProduction); |
| } |
| |
| // Note: callers should also check |
| // is_valid_formal_parameter_list_without_duplicates(). |
| V8_INLINE bool is_valid_strict_mode_formal_parameters() const { |
| return is_valid(StrictModeFormalParametersProduction); |
| } |
| |
| V8_INLINE bool is_valid_let_pattern() const { |
| return is_valid(LetPatternProduction); |
| } |
| |
| bool is_valid_async_arrow_formal_parameters() const { |
| return is_valid(AsyncArrowFormalParametersProduction); |
| } |
| |
| V8_INLINE const Error& expression_error() const { |
| return reported_error(kExpressionProduction); |
| } |
| |
| V8_INLINE const Error& formal_parameter_initializer_error() const { |
| return reported_error(kFormalParameterInitializerProduction); |
| } |
| |
| V8_INLINE const Error& binding_pattern_error() const { |
| return reported_error(kBindingPatternProduction); |
| } |
| |
| V8_INLINE const Error& assignment_pattern_error() const { |
| return reported_error(kAssignmentPatternProduction); |
| } |
| |
| V8_INLINE const Error& arrow_formal_parameters_error() const { |
| return reported_error(kArrowFormalParametersProduction); |
| } |
| |
| V8_INLINE const Error& duplicate_formal_parameter_error() const { |
| return reported_error(kDistinctFormalParametersProduction); |
| } |
| |
| V8_INLINE const Error& strict_mode_formal_parameter_error() const { |
| return reported_error(kStrictModeFormalParametersProduction); |
| } |
| |
| V8_INLINE const Error& let_pattern_error() const { |
| return reported_error(kLetPatternProduction); |
| } |
| |
| V8_INLINE const Error& async_arrow_formal_parameters_error() const { |
| return reported_error(kAsyncArrowFormalParametersProduction); |
| } |
| |
| V8_INLINE bool is_simple_parameter_list() const { |
| return !is_non_simple_parameter_list_; |
| } |
| |
| V8_INLINE void RecordNonSimpleParameter() { |
| is_non_simple_parameter_list_ = 1; |
| } |
| |
| void RecordExpressionError(const Scanner::Location& loc, |
| MessageTemplate::Template message, |
| const char* arg = nullptr) { |
| if (!is_valid_expression()) return; |
| invalid_productions_ |= ExpressionProduction; |
| Add(Error(loc, message, kExpressionProduction, arg)); |
| } |
| |
| void RecordFormalParameterInitializerError(const Scanner::Location& loc, |
| MessageTemplate::Template message, |
| const char* arg = nullptr) { |
| if (!is_valid_formal_parameter_initializer()) return; |
| invalid_productions_ |= FormalParameterInitializerProduction; |
| Add(Error(loc, message, kFormalParameterInitializerProduction, arg)); |
| } |
| |
| void RecordBindingPatternError(const Scanner::Location& loc, |
| MessageTemplate::Template message, |
| const char* arg = nullptr) { |
| if (!is_valid_binding_pattern()) return; |
| invalid_productions_ |= BindingPatternProduction; |
| Add(Error(loc, message, kBindingPatternProduction, arg)); |
| } |
| |
| void RecordAssignmentPatternError(const Scanner::Location& loc, |
| MessageTemplate::Template message, |
| const char* arg = nullptr) { |
| if (!is_valid_assignment_pattern()) return; |
| invalid_productions_ |= AssignmentPatternProduction; |
| Add(Error(loc, message, kAssignmentPatternProduction, arg)); |
| } |
| |
| void RecordPatternError(const Scanner::Location& loc, |
| MessageTemplate::Template message, |
| const char* arg = nullptr) { |
| RecordBindingPatternError(loc, message, arg); |
| RecordAssignmentPatternError(loc, message, arg); |
| } |
| |
| void RecordArrowFormalParametersError(const Scanner::Location& loc, |
| MessageTemplate::Template message, |
| const char* arg = nullptr) { |
| if (!is_valid_arrow_formal_parameters()) return; |
| invalid_productions_ |= ArrowFormalParametersProduction; |
| Add(Error(loc, message, kArrowFormalParametersProduction, arg)); |
| } |
| |
| void RecordAsyncArrowFormalParametersError(const Scanner::Location& loc, |
| MessageTemplate::Template message, |
| const char* arg = nullptr) { |
| if (!is_valid_async_arrow_formal_parameters()) return; |
| invalid_productions_ |= AsyncArrowFormalParametersProduction; |
| Add(Error(loc, message, kAsyncArrowFormalParametersProduction, arg)); |
| } |
| |
| void RecordDuplicateFormalParameterError(const Scanner::Location& loc) { |
| if (!is_valid_formal_parameter_list_without_duplicates()) return; |
| invalid_productions_ |= DistinctFormalParametersProduction; |
| Add(Error(loc, MessageTemplate::kParamDupe, |
| kDistinctFormalParametersProduction)); |
| } |
| |
| // Record a binding that would be invalid in strict mode. Confusingly this |
| // is not the same as StrictFormalParameterList, which simply forbids |
| // duplicate bindings. |
| void RecordStrictModeFormalParameterError(const Scanner::Location& loc, |
| MessageTemplate::Template message, |
| const char* arg = nullptr) { |
| if (!is_valid_strict_mode_formal_parameters()) return; |
| invalid_productions_ |= StrictModeFormalParametersProduction; |
| Add(Error(loc, message, kStrictModeFormalParametersProduction, arg)); |
| } |
| |
| void RecordLetPatternError(const Scanner::Location& loc, |
| MessageTemplate::Template message, |
| const char* arg = nullptr) { |
| if (!is_valid_let_pattern()) return; |
| invalid_productions_ |= LetPatternProduction; |
| Add(Error(loc, message, kLetPatternProduction, arg)); |
| } |
| |
| void Accumulate(ExpressionClassifier* inner, unsigned productions) { |
| DCHECK_EQ(inner->reported_errors_, reported_errors_); |
| DCHECK_EQ(inner->reported_errors_begin_, reported_errors_end_); |
| DCHECK_EQ(inner->reported_errors_end_, reported_errors_->size()); |
| // Propagate errors from inner, but don't overwrite already recorded |
| // errors. |
| unsigned non_arrow_inner_invalid_productions = |
| inner->invalid_productions_ & ~ArrowFormalParametersProduction; |
| if (non_arrow_inner_invalid_productions) { |
| unsigned errors = non_arrow_inner_invalid_productions & productions & |
| ~invalid_productions_; |
| // The result will continue to be a valid arrow formal parameters if the |
| // inner expression is a valid binding pattern. |
| bool copy_BP_to_AFP = false; |
| if (productions & ArrowFormalParametersProduction && |
| is_valid_arrow_formal_parameters()) { |
| // Also whether we've seen any non-simple parameters |
| // if expecting an arrow function parameter. |
| is_non_simple_parameter_list_ |= inner->is_non_simple_parameter_list_; |
| if (!inner->is_valid_binding_pattern()) { |
| copy_BP_to_AFP = true; |
| invalid_productions_ |= ArrowFormalParametersProduction; |
| } |
| } |
| // Traverse the list of errors reported by the inner classifier |
| // to copy what's necessary. |
| if (errors != 0 || copy_BP_to_AFP) { |
| invalid_productions_ |= errors; |
| int binding_pattern_index = inner->reported_errors_end_; |
| for (int i = inner->reported_errors_begin_; |
| i < inner->reported_errors_end_; i++) { |
| int k = reported_errors_->at(i).kind; |
| if (errors & (1 << k)) Copy(i); |
| // Check if it's a BP error that has to be copied to an AFP error. |
| if (k == kBindingPatternProduction && copy_BP_to_AFP) { |
| if (reported_errors_end_ <= i) { |
| // If the BP error itself has not already been copied, |
| // copy it now and change it to an AFP error. |
| Copy(i); |
| reported_errors_->at(reported_errors_end_-1).kind = |
| kArrowFormalParametersProduction; |
| } else { |
| // Otherwise, if the BP error was already copied, keep its |
| // position and wait until the end of the traversal. |
| DCHECK_EQ(reported_errors_end_, i+1); |
| binding_pattern_index = i; |
| } |
| } |
| } |
| // Do we still have to copy the BP error to an AFP error? |
| if (binding_pattern_index < inner->reported_errors_end_) { |
| // If there's still unused space in the list of the inner |
| // classifier, copy it there, otherwise add it to the end |
| // of the list. |
| if (reported_errors_end_ < inner->reported_errors_end_) |
| Copy(binding_pattern_index); |
| else |
| Add(reported_errors_->at(binding_pattern_index)); |
| reported_errors_->at(reported_errors_end_-1).kind = |
| kArrowFormalParametersProduction; |
| } |
| } |
| } |
| reported_errors_->resize(reported_errors_end_); |
| inner->reported_errors_begin_ = inner->reported_errors_end_ = |
| reported_errors_end_; |
| } |
| |
| V8_INLINE void Discard() { |
| if (reported_errors_end_ == reported_errors_->size()) { |
| reported_errors_->resize(reported_errors_begin_); |
| reported_errors_end_ = reported_errors_begin_; |
| } |
| DCHECK_EQ(reported_errors_begin_, reported_errors_end_); |
| } |
| |
| ExpressionClassifier* previous() const { return previous_; } |
| |
| private: |
| V8_INLINE const Error& reported_error(ErrorKind kind) const { |
| if (invalid_productions_ & (1 << kind)) { |
| for (int i = reported_errors_begin_; i < reported_errors_end_; i++) { |
| if (reported_errors_->at(i).kind == kind) |
| return reported_errors_->at(i); |
| } |
| UNREACHABLE(); |
| } |
| // We should only be looking for an error when we know that one has |
| // been reported. But we're not... So this is to make sure we have |
| // the same behaviour. |
| UNREACHABLE(); |
| |
| // Make MSVC happy by returning an error from this inaccessible path. |
| static Error none; |
| return none; |
| } |
| |
| // Adds e to the end of the list of reported errors for this classifier. |
| // It is expected that this classifier is the last one in the stack. |
| V8_INLINE void Add(const Error& e) { |
| DCHECK_EQ(reported_errors_end_, reported_errors_->size()); |
| reported_errors_->push_back(e); |
| reported_errors_end_++; |
| } |
| |
| // Copies the error at position i of the list of reported errors, so that |
| // it becomes the last error reported for this classifier. Position i |
| // could be either after the existing errors of this classifier (i.e., |
| // in an inner classifier) or it could be an existing error (in case a |
| // copy is needed). |
| V8_INLINE void Copy(int i) { |
| DCHECK_LT(i, reported_errors_->size()); |
| if (reported_errors_end_ != i) |
| reported_errors_->at(reported_errors_end_) = reported_errors_->at(i); |
| reported_errors_end_++; |
| } |
| |
| typename Types::Base* base_; |
| ExpressionClassifier* previous_; |
| Zone* zone_; |
| ZoneVector<Error>* reported_errors_; |
| DuplicateFinder* duplicate_finder_; |
| unsigned invalid_productions_ : 15; |
| unsigned is_non_simple_parameter_list_ : 1; |
| // The uint16_t for reported_errors_begin_ and reported_errors_end_ will |
| // not be enough in the case of a long series of expressions using nested |
| // classifiers, e.g., a long sequence of assignments, as in: |
| // literals with spreads, as in: |
| // var N=65536; eval("var x;" + "x=".repeat(N) + "42"); |
| // This should not be a problem, as such things currently fail with a |
| // stack overflow while parsing. |
| uint16_t reported_errors_begin_; |
| uint16_t reported_errors_end_; |
| |
| DISALLOW_COPY_AND_ASSIGN(ExpressionClassifier); |
| }; |
| |
| |
| #undef ERROR_CODES |
| |
| |
| } // namespace internal |
| } // namespace v8 |
| |
| #endif // V8_PARSING_EXPRESSION_CLASSIFIER_H_ |