LCOV - code coverage report
Current view: top level - src/parsing - expression-classifier.h (source / functions) Hit Total Coverage
Test: app.info Lines: 90 95 94.7 %
Date: 2017-04-26 Functions: 26 26 100.0 %

          Line data    Source code
       1             : // Copyright 2015 the V8 project 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             : #ifndef V8_PARSING_EXPRESSION_CLASSIFIER_H
       6             : #define V8_PARSING_EXPRESSION_CLASSIFIER_H
       7             : 
       8             : #include "src/messages.h"
       9             : #include "src/parsing/scanner.h"
      10             : 
      11             : namespace v8 {
      12             : namespace internal {
      13             : 
      14             : class DuplicateFinder;
      15             : 
      16             : #define ERROR_CODES(T)                       \
      17             :   T(ExpressionProduction, 0)                 \
      18             :   T(FormalParameterInitializerProduction, 1) \
      19             :   T(BindingPatternProduction, 2)             \
      20             :   T(AssignmentPatternProduction, 3)          \
      21             :   T(DistinctFormalParametersProduction, 4)   \
      22             :   T(StrictModeFormalParametersProduction, 5) \
      23             :   T(ArrowFormalParametersProduction, 6)      \
      24             :   T(LetPatternProduction, 7)                 \
      25             :   T(AsyncArrowFormalParametersProduction, 8)
      26             : 
      27             : // Expression classifiers serve two purposes:
      28             : //
      29             : // 1) They keep track of error messages that are pending (and other
      30             : //    related information), waiting for the parser to decide whether
      31             : //    the parsed expression is a pattern or not.
      32             : // 2) They keep track of expressions that may need to be rewritten, if
      33             : //    the parser decides that they are not patterns.  (A different
      34             : //    mechanism implements the rewriting of patterns.)
      35             : //
      36             : // Expression classifiers are used by the parser in a stack fashion.
      37             : // Each new classifier is pushed on top of the stack.  This happens
      38             : // automatically by the class's constructor.  While on top of the
      39             : // stack, the classifier records pending error messages and tracks the
      40             : // pending non-patterns of the expression that is being parsed.
      41             : //
      42             : // At the end of its life, a classifier is either "accumulated" to the
      43             : // one that is below it on the stack, or is "discarded".  The former
      44             : // is achieved by calling the method Accumulate.  The latter is
      45             : // achieved automatically by the destructor, but it can happen earlier
      46             : // by calling the method Discard.  Both actions result in removing the
      47             : // classifier from the parser's stack.
      48             : 
      49             : template <typename Types>
      50             : class ExpressionClassifier {
      51             :  public:
      52             :   enum ErrorKind : unsigned {
      53             : #define DEFINE_ERROR_KIND(NAME, CODE) k##NAME = CODE,
      54             :     ERROR_CODES(DEFINE_ERROR_KIND)
      55             : #undef DEFINE_ERROR_KIND
      56             :     kUnusedError = 15  // Larger than error codes; should fit in 4 bits
      57             :   };
      58             : 
      59             :   struct Error {
      60             :     V8_INLINE Error()
      61             :         : location(Scanner::Location::invalid()),
      62             :           message(MessageTemplate::kNone),
      63             :           kind(kUnusedError),
      64             :           type(kSyntaxError),
      65             :           arg(nullptr) {}
      66             :     V8_INLINE explicit Error(Scanner::Location loc,
      67             :                              MessageTemplate::Template msg, ErrorKind k,
      68             :                              const char* a = nullptr,
      69             :                              ParseErrorType t = kSyntaxError)
      70   243665219 :         : location(loc), message(msg), kind(k), type(t), arg(a) {}
      71             : 
      72             :     Scanner::Location location;
      73             :     MessageTemplate::Template message : 26;
      74             :     unsigned kind : 4;
      75             :     ParseErrorType type : 2;
      76             :     const char* arg;
      77             :   };
      78             : 
      79             :   // clang-format off
      80             :   enum TargetProduction : unsigned {
      81             : #define DEFINE_PRODUCTION(NAME, CODE) NAME = 1 << CODE,
      82             :     ERROR_CODES(DEFINE_PRODUCTION)
      83             : #undef DEFINE_PRODUCTION
      84             : 
      85             : #define DEFINE_ALL_PRODUCTIONS(NAME, CODE) NAME |
      86             :     AllProductions = ERROR_CODES(DEFINE_ALL_PRODUCTIONS) /* | */ 0
      87             : #undef DEFINE_ALL_PRODUCTIONS
      88             :   };
      89             :   // clang-format on
      90             : 
      91             :   enum FunctionProperties : unsigned {
      92             :     NonSimpleParameter = 1 << 0
      93             :   };
      94             : 
      95   304421433 :   explicit ExpressionClassifier(typename Types::Base* base,
      96             :                                 DuplicateFinder* duplicate_finder = nullptr)
      97             :       : base_(base),
      98             :         previous_(base->classifier_),
      99             :         zone_(base->impl()->zone()),
     100             :         non_patterns_to_rewrite_(base->impl()->GetNonPatternList()),
     101             :         reported_errors_(base->impl()->GetReportedErrorList()),
     102             :         duplicate_finder_(duplicate_finder),
     103             :         invalid_productions_(0),
     104   913264554 :         function_properties_(0) {
     105   304421580 :     base->classifier_ = this;
     106   304421580 :     reported_errors_begin_ = reported_errors_end_ = reported_errors_->length();
     107   304421580 :     non_pattern_begin_ = non_patterns_to_rewrite_->length();
     108   304421580 :   }
     109             : 
     110             :   V8_INLINE ~ExpressionClassifier() {
     111             :     Discard();
     112   304423261 :     if (base_->classifier_ == this) base_->classifier_ = previous_;
     113             :   }
     114             : 
     115             :   V8_INLINE bool is_valid(unsigned productions) const {
     116   729537307 :     return (invalid_productions_ & productions) == 0;
     117             :   }
     118             : 
     119             :   V8_INLINE DuplicateFinder* duplicate_finder() const {
     120             :     return duplicate_finder_;
     121             :   }
     122             : 
     123             :   V8_INLINE bool is_valid_expression() const {
     124             :     return is_valid(ExpressionProduction);
     125             :   }
     126             : 
     127             :   V8_INLINE bool is_valid_formal_parameter_initializer() const {
     128             :     return is_valid(FormalParameterInitializerProduction);
     129             :   }
     130             : 
     131             :   V8_INLINE bool is_valid_binding_pattern() const {
     132             :     return is_valid(BindingPatternProduction);
     133             :   }
     134             : 
     135             :   V8_INLINE bool is_valid_assignment_pattern() const {
     136             :     return is_valid(AssignmentPatternProduction);
     137             :   }
     138             : 
     139             :   V8_INLINE bool is_valid_arrow_formal_parameters() const {
     140             :     return is_valid(ArrowFormalParametersProduction);
     141             :   }
     142             : 
     143             :   V8_INLINE bool is_valid_formal_parameter_list_without_duplicates() const {
     144             :     return is_valid(DistinctFormalParametersProduction);
     145             :   }
     146             : 
     147             :   // Note: callers should also check
     148             :   // is_valid_formal_parameter_list_without_duplicates().
     149             :   V8_INLINE bool is_valid_strict_mode_formal_parameters() const {
     150             :     return is_valid(StrictModeFormalParametersProduction);
     151             :   }
     152             : 
     153             :   V8_INLINE bool is_valid_let_pattern() const {
     154             :     return is_valid(LetPatternProduction);
     155             :   }
     156             : 
     157             :   bool is_valid_async_arrow_formal_parameters() const {
     158             :     return is_valid(AsyncArrowFormalParametersProduction);
     159             :   }
     160             : 
     161             :   V8_INLINE const Error& expression_error() const {
     162             :     return reported_error(kExpressionProduction);
     163             :   }
     164             : 
     165             :   V8_INLINE const Error& formal_parameter_initializer_error() const {
     166             :     return reported_error(kFormalParameterInitializerProduction);
     167             :   }
     168             : 
     169             :   V8_INLINE const Error& binding_pattern_error() const {
     170             :     return reported_error(kBindingPatternProduction);
     171             :   }
     172             : 
     173             :   V8_INLINE const Error& assignment_pattern_error() const {
     174             :     return reported_error(kAssignmentPatternProduction);
     175             :   }
     176             : 
     177             :   V8_INLINE const Error& arrow_formal_parameters_error() const {
     178             :     return reported_error(kArrowFormalParametersProduction);
     179             :   }
     180             : 
     181             :   V8_INLINE const Error& duplicate_formal_parameter_error() const {
     182             :     return reported_error(kDistinctFormalParametersProduction);
     183             :   }
     184             : 
     185             :   V8_INLINE const Error& strict_mode_formal_parameter_error() const {
     186             :     return reported_error(kStrictModeFormalParametersProduction);
     187             :   }
     188             : 
     189             :   V8_INLINE const Error& let_pattern_error() const {
     190             :     return reported_error(kLetPatternProduction);
     191             :   }
     192             : 
     193             :   V8_INLINE const Error& async_arrow_formal_parameters_error() const {
     194             :     return reported_error(kAsyncArrowFormalParametersProduction);
     195             :   }
     196             : 
     197             :   V8_INLINE bool is_simple_parameter_list() const {
     198     8902001 :     return !(function_properties_ & NonSimpleParameter);
     199             :   }
     200             : 
     201             :   V8_INLINE void RecordNonSimpleParameter() {
     202    48276568 :     function_properties_ |= NonSimpleParameter;
     203             :   }
     204             : 
     205      422493 :   void RecordExpressionError(const Scanner::Location& loc,
     206             :                              MessageTemplate::Template message,
     207             :                              const char* arg = nullptr) {
     208      844986 :     if (!is_valid_expression()) return;
     209      417245 :     invalid_productions_ |= ExpressionProduction;
     210      417245 :     Add(Error(loc, message, kExpressionProduction, arg));
     211             :   }
     212             : 
     213             :   void RecordExpressionError(const Scanner::Location& loc,
     214             :                              MessageTemplate::Template message,
     215             :                              ParseErrorType type, const char* arg = nullptr) {
     216             :     if (!is_valid_expression()) return;
     217             :     invalid_productions_ |= ExpressionProduction;
     218             :     Add(Error(loc, message, kExpressionProduction, arg, type));
     219             :   }
     220             : 
     221       95731 :   void RecordFormalParameterInitializerError(const Scanner::Location& loc,
     222             :                                              MessageTemplate::Template message,
     223             :                                              const char* arg = nullptr) {
     224      191462 :     if (!is_valid_formal_parameter_initializer()) return;
     225       94664 :     invalid_productions_ |= FormalParameterInitializerProduction;
     226       94664 :     Add(Error(loc, message, kFormalParameterInitializerProduction, arg));
     227             :   }
     228             : 
     229   147660378 :   void RecordBindingPatternError(const Scanner::Location& loc,
     230             :                                  MessageTemplate::Template message,
     231             :                                  const char* arg = nullptr) {
     232   295320767 :     if (!is_valid_binding_pattern()) return;
     233   100225309 :     invalid_productions_ |= BindingPatternProduction;
     234   100225320 :     Add(Error(loc, message, kBindingPatternProduction, arg));
     235             :   }
     236             : 
     237    23128600 :   void RecordAssignmentPatternError(const Scanner::Location& loc,
     238             :                                     MessageTemplate::Template message,
     239             :                                     const char* arg = nullptr) {
     240    46257204 :     if (!is_valid_assignment_pattern()) return;
     241     8532041 :     invalid_productions_ |= AssignmentPatternProduction;
     242     8532045 :     Add(Error(loc, message, kAssignmentPatternProduction, arg));
     243             :   }
     244             : 
     245     8066531 :   void RecordPatternError(const Scanner::Location& loc,
     246             :                           MessageTemplate::Template message,
     247             :                           const char* arg = nullptr) {
     248     8066531 :     RecordBindingPatternError(loc, message, arg);
     249     8066533 :     RecordAssignmentPatternError(loc, message, arg);
     250     8066538 :   }
     251             : 
     252   212008490 :   void RecordArrowFormalParametersError(const Scanner::Location& loc,
     253             :                                         MessageTemplate::Template message,
     254             :                                         const char* arg = nullptr) {
     255   424016999 :     if (!is_valid_arrow_formal_parameters()) return;
     256   133721155 :     invalid_productions_ |= ArrowFormalParametersProduction;
     257   133721174 :     Add(Error(loc, message, kArrowFormalParametersProduction, arg));
     258             :   }
     259             : 
     260       21216 :   void RecordAsyncArrowFormalParametersError(const Scanner::Location& loc,
     261             :                                              MessageTemplate::Template message,
     262             :                                              const char* arg = nullptr) {
     263       42432 :     if (!is_valid_async_arrow_formal_parameters()) return;
     264       21216 :     invalid_productions_ |= AsyncArrowFormalParametersProduction;
     265       21216 :     Add(Error(loc, message, kAsyncArrowFormalParametersProduction, arg));
     266             :   }
     267             : 
     268       22171 :   void RecordDuplicateFormalParameterError(const Scanner::Location& loc) {
     269       44342 :     if (!is_valid_formal_parameter_list_without_duplicates()) return;
     270        7833 :     invalid_productions_ |= DistinctFormalParametersProduction;
     271             :     Add(Error(loc, MessageTemplate::kParamDupe,
     272        7833 :               kDistinctFormalParametersProduction));
     273             :   }
     274             : 
     275             :   // Record a binding that would be invalid in strict mode.  Confusingly this
     276             :   // is not the same as StrictFormalParameterList, which simply forbids
     277             :   // duplicate bindings.
     278      633532 :   void RecordStrictModeFormalParameterError(const Scanner::Location& loc,
     279             :                                             MessageTemplate::Template message,
     280             :                                             const char* arg = nullptr) {
     281     1267064 :     if (!is_valid_strict_mode_formal_parameters()) return;
     282      631954 :     invalid_productions_ |= StrictModeFormalParametersProduction;
     283      631954 :     Add(Error(loc, message, kStrictModeFormalParametersProduction, arg));
     284             :   }
     285             : 
     286       13979 :   void RecordLetPatternError(const Scanner::Location& loc,
     287             :                              MessageTemplate::Template message,
     288             :                              const char* arg = nullptr) {
     289       27958 :     if (!is_valid_let_pattern()) return;
     290       13802 :     invalid_productions_ |= LetPatternProduction;
     291       13802 :     Add(Error(loc, message, kLetPatternProduction, arg));
     292             :   }
     293             : 
     294   210843530 :   void Accumulate(ExpressionClassifier* inner, unsigned productions,
     295             :                   bool merge_non_patterns = true) {
     296             :     DCHECK_EQ(inner->reported_errors_, reported_errors_);
     297             :     DCHECK_EQ(inner->reported_errors_begin_, reported_errors_end_);
     298             :     DCHECK_EQ(inner->reported_errors_end_, reported_errors_->length());
     299             :     DCHECK_EQ(inner->non_patterns_to_rewrite_, non_patterns_to_rewrite_);
     300             :     DCHECK_LE(non_pattern_begin_, inner->non_pattern_begin_);
     301             :     DCHECK_LE(inner->non_pattern_begin_, non_patterns_to_rewrite_->length());
     302             :     // Merge non-patterns from the inner classifier, or discard them.
     303   210843530 :     if (merge_non_patterns)
     304   196285016 :       inner->non_pattern_begin_ = non_patterns_to_rewrite_->length();
     305             :     else
     306    14558514 :       non_patterns_to_rewrite_->Rewind(inner->non_pattern_begin_);
     307             :     // Propagate errors from inner, but don't overwrite already recorded
     308             :     // errors.
     309             :     unsigned non_arrow_inner_invalid_productions =
     310   210843530 :         inner->invalid_productions_ & ~ArrowFormalParametersProduction;
     311   210843530 :     if (non_arrow_inner_invalid_productions) {
     312             :       unsigned errors = non_arrow_inner_invalid_productions & productions &
     313   153348603 :                         ~invalid_productions_;
     314             :       // The result will continue to be a valid arrow formal parameters if the
     315             :       // inner expression is a valid binding pattern.
     316             :       bool copy_BP_to_AFP = false;
     317   198214113 :       if (productions & ArrowFormalParametersProduction &&
     318             :           is_valid_arrow_formal_parameters()) {
     319             :         // Also copy function properties if expecting an arrow function
     320             :         // parameter.
     321    40899323 :         function_properties_ |= inner->function_properties_;
     322    40899323 :         if (!inner->is_valid_binding_pattern()) {
     323             :           copy_BP_to_AFP = true;
     324    40844674 :           invalid_productions_ |= ArrowFormalParametersProduction;
     325             :         }
     326             :       }
     327             :       // Traverse the list of errors reported by the inner classifier
     328             :       // to copy what's necessary.
     329   153348603 :       if (errors != 0 || copy_BP_to_AFP) {
     330   113071727 :         invalid_productions_ |= errors;
     331   113071727 :         int binding_pattern_index = inner->reported_errors_end_;
     332   312290223 :         for (int i = inner->reported_errors_begin_;
     333             :              i < inner->reported_errors_end_; i++) {
     334   398436824 :           int k = reported_errors_->at(i).kind;
     335   199218412 :           if (errors & (1 << k)) Copy(i);
     336             :           // Check if it's a BP error that has to be copied to an AFP error.
     337   199218496 :           if (k == kBindingPatternProduction && copy_BP_to_AFP) {
     338    40844713 :             if (reported_errors_end_ <= i) {
     339             :               // If the BP error itself has not already been copied,
     340             :               // copy it now and change it to an AFP error.
     341             :               Copy(i);
     342    81689426 :               reported_errors_->at(reported_errors_end_-1).kind =
     343             :                   kArrowFormalParametersProduction;
     344             :             } else {
     345             :               // Otherwise, if the BP error was already copied, keep its
     346             :               // position and wait until the end of the traversal.
     347             :               DCHECK_EQ(reported_errors_end_, i+1);
     348             :               binding_pattern_index = i;
     349             :             }
     350             :           }
     351             :         }
     352             :         // Do we still have to copy the BP error to an AFP error?
     353   113071811 :         if (binding_pattern_index < inner->reported_errors_end_) {
     354             :           // If there's still unused space in the list of the inner
     355             :           // classifier, copy it there, otherwise add it to the end
     356             :           // of the list.
     357           0 :           if (reported_errors_end_ < inner->reported_errors_end_)
     358             :             Copy(binding_pattern_index);
     359             :           else
     360           0 :             Add(reported_errors_->at(binding_pattern_index));
     361           0 :           reported_errors_->at(reported_errors_end_-1).kind =
     362             :               kArrowFormalParametersProduction;
     363             :         }
     364             :       }
     365             :     }
     366   210843614 :     reported_errors_->Rewind(reported_errors_end_);
     367   210843614 :     inner->reported_errors_begin_ = inner->reported_errors_end_ =
     368             :         reported_errors_end_;
     369   210843614 :   }
     370             : 
     371   152863472 :   V8_INLINE int GetNonPatternBegin() const { return non_pattern_begin_; }
     372             : 
     373             :   V8_INLINE void Discard() {
     374   305123566 :     if (reported_errors_end_ == reported_errors_->length()) {
     375   303931054 :       reported_errors_->Rewind(reported_errors_begin_);
     376   303931054 :       reported_errors_end_ = reported_errors_begin_;
     377             :     }
     378             :     DCHECK_EQ(reported_errors_begin_, reported_errors_end_);
     379             :     DCHECK_LE(non_pattern_begin_, non_patterns_to_rewrite_->length());
     380   305123566 :     non_patterns_to_rewrite_->Rewind(non_pattern_begin_);
     381             :   }
     382             : 
     383   211543531 :   ExpressionClassifier* previous() const { return previous_; }
     384             : 
     385             :  private:
     386             :   V8_INLINE const Error& reported_error(ErrorKind kind) const {
     387      122388 :     if (invalid_productions_ & (1 << kind)) {
     388      254947 :       for (int i = reported_errors_begin_; i < reported_errors_end_; i++) {
     389      254947 :         if (reported_errors_->at(i).kind == kind)
     390      122388 :           return reported_errors_->at(i);
     391             :       }
     392           0 :       UNREACHABLE();
     393             :     }
     394             :     // We should only be looking for an error when we know that one has
     395             :     // been reported.  But we're not...  So this is to make sure we have
     396             :     // the same behaviour.
     397           0 :     UNREACHABLE();
     398             : 
     399             :     // Make MSVC happy by returning an error from this inaccessible path.
     400             :     static Error none;
     401             :     return none;
     402             :   }
     403             : 
     404             :   // Adds e to the end of the list of reported errors for this classifier.
     405             :   // It is expected that this classifier is the last one in the stack.
     406             :   V8_INLINE void Add(const Error& e) {
     407             :     DCHECK_EQ(reported_errors_end_, reported_errors_->length());
     408   243665219 :     reported_errors_->Add(e, zone_);
     409   243665253 :     reported_errors_end_++;
     410             :   }
     411             : 
     412             :   // Copies the error at position i of the list of reported errors, so that
     413             :   // it becomes the last error reported for this classifier.  Position i
     414             :   // could be either after the existing errors of this classifier (i.e.,
     415             :   // in an inner classifier) or it could be an existing error (in case a
     416             :   // copy is needed).
     417             :   V8_INLINE void Copy(int i) {
     418             :     DCHECK_LT(i, reported_errors_->length());
     419   125441740 :     if (reported_errors_end_ != i)
     420    72677378 :       reported_errors_->at(reported_errors_end_) = reported_errors_->at(i);
     421   125441824 :     reported_errors_end_++;
     422             :   }
     423             : 
     424             :   typename Types::Base* base_;
     425             :   ExpressionClassifier* previous_;
     426             :   Zone* zone_;
     427             :   ZoneList<typename Types::Expression>* non_patterns_to_rewrite_;
     428             :   ZoneList<Error>* reported_errors_;
     429             :   DuplicateFinder* duplicate_finder_;
     430             :   // The uint16_t for non_pattern_begin_ will not be enough in the case,
     431             :   // e.g., of an array literal containing more than 64K inner array
     432             :   // literals with spreads, as in:
     433             :   // var N=65536; eval("var x=[];" + "[" + "[...x],".repeat(N) + "].length");
     434             :   // An implementation limit error in ParserBase::AddNonPatternForRewriting
     435             :   // will be triggered in this case.
     436             :   uint16_t non_pattern_begin_;
     437             :   unsigned invalid_productions_ : 14;
     438             :   unsigned function_properties_ : 2;
     439             :   // The uint16_t for reported_errors_begin_ and reported_errors_end_ will
     440             :   // not be enough in the case of a long series of expressions using nested
     441             :   // classifiers, e.g., a long sequence of assignments, as in:
     442             :   // literals with spreads, as in:
     443             :   // var N=65536; eval("var x;" + "x=".repeat(N) + "42");
     444             :   // This should not be a problem, as such things currently fail with a
     445             :   // stack overflow while parsing.
     446             :   uint16_t reported_errors_begin_;
     447             :   uint16_t reported_errors_end_;
     448             : 
     449             :   DISALLOW_COPY_AND_ASSIGN(ExpressionClassifier);
     450             : };
     451             : 
     452             : 
     453             : #undef ERROR_CODES
     454             : 
     455             : 
     456             : }  // namespace internal
     457             : }  // namespace v8
     458             : 
     459             : #endif  // V8_PARSING_EXPRESSION_CLASSIFIER_H

Generated by: LCOV version 1.10