Home | History | Annotate | Download | only in parsing 
      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 #include "src/parsing/token.h"
     11 
     12 namespace v8 {
     13 namespace internal {
     14 
     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(CoverInitializedNameProduction, 8)          \
     26   T(TailCallExpressionProduction, 9)            \
     27   T(AsyncArrowFormalParametersProduction, 10)   \
     28   T(AsyncBindingPatternProduction, 11)
     29 
     30 
     31 template <typename Traits>
     32 class ExpressionClassifier {
     33  public:
     34   enum ErrorKind : unsigned {
     35 #define DEFINE_ERROR_KIND(NAME, CODE) k##NAME = CODE,
     36     ERROR_CODES(DEFINE_ERROR_KIND)
     37 #undef DEFINE_ERROR_KIND
     38     kUnusedError = 15  // Larger than error codes; should fit in 4 bits
     39   };
     40 
     41   struct Error {
     42     V8_INLINE Error()
     43         : location(Scanner::Location::invalid()),
     44           message(MessageTemplate::kNone),
     45           kind(kUnusedError),
     46           type(kSyntaxError),
     47           arg(nullptr) {}
     48     V8_INLINE explicit Error(Scanner::Location loc,
     49                              MessageTemplate::Template msg, ErrorKind k,
     50                              const char* a = nullptr,
     51                              ParseErrorType t = kSyntaxError)
     52         : location(loc), message(msg), kind(k), type(t), arg(a) {}
     53 
     54     Scanner::Location location;
     55     MessageTemplate::Template message : 26;
     56     unsigned kind : 4;
     57     ParseErrorType type : 2;
     58     const char* arg;
     59   };
     60 
     61   enum TargetProduction : unsigned {
     62 #define DEFINE_PRODUCTION(NAME, CODE) NAME = 1 << CODE,
     63     ERROR_CODES(DEFINE_PRODUCTION)
     64 #undef DEFINE_PRODUCTION
     65 
     66     ExpressionProductions =
     67         (ExpressionProduction | FormalParameterInitializerProduction |
     68          TailCallExpressionProduction),
     69     PatternProductions =
     70         (BindingPatternProduction | AssignmentPatternProduction |
     71          LetPatternProduction | AsyncBindingPatternProduction),
     72     FormalParametersProductions = (DistinctFormalParametersProduction |
     73                                    StrictModeFormalParametersProduction),
     74     StandardProductions = ExpressionProductions | PatternProductions,
     75     AllProductions =
     76         (StandardProductions | FormalParametersProductions |
     77          ArrowFormalParametersProduction | CoverInitializedNameProduction |
     78          AsyncArrowFormalParametersProduction | AsyncBindingPatternProduction)
     79   };
     80 
     81   enum FunctionProperties : unsigned {
     82     NonSimpleParameter = 1 << 0
     83   };
     84 
     85   explicit ExpressionClassifier(const Traits* t)
     86       : zone_(t->zone()),
     87         non_patterns_to_rewrite_(t->GetNonPatternList()),
     88         reported_errors_(t->GetReportedErrorList()),
     89         duplicate_finder_(nullptr),
     90         invalid_productions_(0),
     91         function_properties_(0) {
     92     reported_errors_begin_ = reported_errors_end_ = reported_errors_->length();
     93     non_pattern_begin_ = non_patterns_to_rewrite_->length();
     94   }
     95 
     96   ExpressionClassifier(const Traits* t, DuplicateFinder* duplicate_finder)
     97       : zone_(t->zone()),
     98         non_patterns_to_rewrite_(t->GetNonPatternList()),
     99         reported_errors_(t->GetReportedErrorList()),
    100         duplicate_finder_(duplicate_finder),
    101         invalid_productions_(0),
    102         function_properties_(0) {
    103     reported_errors_begin_ = reported_errors_end_ = reported_errors_->length();
    104     non_pattern_begin_ = non_patterns_to_rewrite_->length();
    105   }
    106 
    107   ~ExpressionClassifier() { Discard(); }
    108 
    109   V8_INLINE bool is_valid(unsigned productions) const {
    110     return (invalid_productions_ & productions) == 0;
    111   }
    112 
    113   V8_INLINE DuplicateFinder* duplicate_finder() const {
    114     return duplicate_finder_;
    115   }
    116 
    117   V8_INLINE bool is_valid_expression() const {
    118     return is_valid(ExpressionProduction);
    119   }
    120 
    121   V8_INLINE bool is_valid_formal_parameter_initializer() const {
    122     return is_valid(FormalParameterInitializerProduction);
    123   }
    124 
    125   V8_INLINE bool is_valid_binding_pattern() const {
    126     return is_valid(BindingPatternProduction);
    127   }
    128 
    129   V8_INLINE bool is_valid_assignment_pattern() const {
    130     return is_valid(AssignmentPatternProduction);
    131   }
    132 
    133   V8_INLINE bool is_valid_arrow_formal_parameters() const {
    134     return is_valid(ArrowFormalParametersProduction);
    135   }
    136 
    137   V8_INLINE bool is_valid_formal_parameter_list_without_duplicates() const {
    138     return is_valid(DistinctFormalParametersProduction);
    139   }
    140 
    141   // Note: callers should also check
    142   // is_valid_formal_parameter_list_without_duplicates().
    143   V8_INLINE bool is_valid_strict_mode_formal_parameters() const {
    144     return is_valid(StrictModeFormalParametersProduction);
    145   }
    146 
    147   V8_INLINE bool is_valid_let_pattern() const {
    148     return is_valid(LetPatternProduction);
    149   }
    150 
    151   bool is_valid_async_arrow_formal_parameters() const {
    152     return is_valid(AsyncArrowFormalParametersProduction);
    153   }
    154 
    155   bool is_valid_async_binding_pattern() const {
    156     return is_valid(AsyncBindingPatternProduction);
    157   }
    158 
    159   V8_INLINE const Error& expression_error() const {
    160     return reported_error(kExpressionProduction);
    161   }
    162 
    163   V8_INLINE const Error& formal_parameter_initializer_error() const {
    164     return reported_error(kFormalParameterInitializerProduction);
    165   }
    166 
    167   V8_INLINE const Error& binding_pattern_error() const {
    168     return reported_error(kBindingPatternProduction);
    169   }
    170 
    171   V8_INLINE const Error& assignment_pattern_error() const {
    172     return reported_error(kAssignmentPatternProduction);
    173   }
    174 
    175   V8_INLINE const Error& arrow_formal_parameters_error() const {
    176     return reported_error(kArrowFormalParametersProduction);
    177   }
    178 
    179   V8_INLINE const Error& duplicate_formal_parameter_error() const {
    180     return reported_error(kDistinctFormalParametersProduction);
    181   }
    182 
    183   V8_INLINE const Error& strict_mode_formal_parameter_error() const {
    184     return reported_error(kStrictModeFormalParametersProduction);
    185   }
    186 
    187   V8_INLINE const Error& let_pattern_error() const {
    188     return reported_error(kLetPatternProduction);
    189   }
    190 
    191   V8_INLINE bool has_cover_initialized_name() const {
    192     return !is_valid(CoverInitializedNameProduction);
    193   }
    194 
    195   V8_INLINE const Error& cover_initialized_name_error() const {
    196     return reported_error(kCoverInitializedNameProduction);
    197   }
    198 
    199   V8_INLINE bool has_tail_call_expression() const {
    200     return !is_valid(TailCallExpressionProduction);
    201   }
    202   V8_INLINE const Error& tail_call_expression_error() const {
    203     return reported_error(kTailCallExpressionProduction);
    204   }
    205   V8_INLINE const Error& async_arrow_formal_parameters_error() const {
    206     return reported_error(kAsyncArrowFormalParametersProduction);
    207   }
    208 
    209   V8_INLINE const Error& async_binding_pattern_error() const {
    210     return reported_error(kAsyncBindingPatternProduction);
    211   }
    212 
    213   V8_INLINE bool is_simple_parameter_list() const {
    214     return !(function_properties_ & NonSimpleParameter);
    215   }
    216 
    217   V8_INLINE void RecordNonSimpleParameter() {
    218     function_properties_ |= NonSimpleParameter;
    219   }
    220 
    221   void RecordExpressionError(const Scanner::Location& loc,
    222                              MessageTemplate::Template message,
    223                              const char* arg = nullptr) {
    224     if (!is_valid_expression()) return;
    225     invalid_productions_ |= ExpressionProduction;
    226     Add(Error(loc, message, kExpressionProduction, arg));
    227   }
    228 
    229   void RecordExpressionError(const Scanner::Location& loc,
    230                              MessageTemplate::Template message,
    231                              ParseErrorType type, const char* arg = nullptr) {
    232     if (!is_valid_expression()) return;
    233     invalid_productions_ |= ExpressionProduction;
    234     Add(Error(loc, message, kExpressionProduction, arg, type));
    235   }
    236 
    237   void RecordFormalParameterInitializerError(const Scanner::Location& loc,
    238                                              MessageTemplate::Template message,
    239                                              const char* arg = nullptr) {
    240     if (!is_valid_formal_parameter_initializer()) return;
    241     invalid_productions_ |= FormalParameterInitializerProduction;
    242     Add(Error(loc, message, kFormalParameterInitializerProduction, arg));
    243   }
    244 
    245   void RecordBindingPatternError(const Scanner::Location& loc,
    246                                  MessageTemplate::Template message,
    247                                  const char* arg = nullptr) {
    248     if (!is_valid_binding_pattern()) return;
    249     invalid_productions_ |= BindingPatternProduction;
    250     Add(Error(loc, message, kBindingPatternProduction, arg));
    251   }
    252 
    253   void RecordAssignmentPatternError(const Scanner::Location& loc,
    254                                     MessageTemplate::Template message,
    255                                     const char* arg = nullptr) {
    256     if (!is_valid_assignment_pattern()) return;
    257     invalid_productions_ |= AssignmentPatternProduction;
    258     Add(Error(loc, message, kAssignmentPatternProduction, arg));
    259   }
    260 
    261   void RecordPatternError(const Scanner::Location& loc,
    262                           MessageTemplate::Template message,
    263                           const char* arg = nullptr) {
    264     RecordBindingPatternError(loc, message, arg);
    265     RecordAssignmentPatternError(loc, message, arg);
    266   }
    267 
    268   void RecordArrowFormalParametersError(const Scanner::Location& loc,
    269                                         MessageTemplate::Template message,
    270                                         const char* arg = nullptr) {
    271     if (!is_valid_arrow_formal_parameters()) return;
    272     invalid_productions_ |= ArrowFormalParametersProduction;
    273     Add(Error(loc, message, kArrowFormalParametersProduction, arg));
    274   }
    275 
    276   void RecordAsyncArrowFormalParametersError(const Scanner::Location& loc,
    277                                              MessageTemplate::Template message,
    278                                              const char* arg = nullptr) {
    279     if (!is_valid_async_arrow_formal_parameters()) return;
    280     invalid_productions_ |= AsyncArrowFormalParametersProduction;
    281     Add(Error(loc, message, kAsyncArrowFormalParametersProduction, arg));
    282   }
    283 
    284   void RecordAsyncBindingPatternError(const Scanner::Location& loc,
    285                                       MessageTemplate::Template message,
    286                                       const char* arg = nullptr) {
    287     if (!is_valid_async_binding_pattern()) return;
    288     invalid_productions_ |= AsyncBindingPatternProduction;
    289     Add(Error(loc, message, kAsyncBindingPatternProduction, arg));
    290   }
    291 
    292   void RecordDuplicateFormalParameterError(const Scanner::Location& loc) {
    293     if (!is_valid_formal_parameter_list_without_duplicates()) return;
    294     invalid_productions_ |= DistinctFormalParametersProduction;
    295     Add(Error(loc, MessageTemplate::kParamDupe,
    296               kDistinctFormalParametersProduction));
    297   }
    298 
    299   // Record a binding that would be invalid in strict mode.  Confusingly this
    300   // is not the same as StrictFormalParameterList, which simply forbids
    301   // duplicate bindings.
    302   void RecordStrictModeFormalParameterError(const Scanner::Location& loc,
    303                                             MessageTemplate::Template message,
    304                                             const char* arg = nullptr) {
    305     if (!is_valid_strict_mode_formal_parameters()) return;
    306     invalid_productions_ |= StrictModeFormalParametersProduction;
    307     Add(Error(loc, message, kStrictModeFormalParametersProduction, arg));
    308   }
    309 
    310   void RecordLetPatternError(const Scanner::Location& loc,
    311                              MessageTemplate::Template message,
    312                              const char* arg = nullptr) {
    313     if (!is_valid_let_pattern()) return;
    314     invalid_productions_ |= LetPatternProduction;
    315     Add(Error(loc, message, kLetPatternProduction, arg));
    316   }
    317 
    318   void RecordCoverInitializedNameError(const Scanner::Location& loc,
    319                                        MessageTemplate::Template message,
    320                                        const char* arg = nullptr) {
    321     if (has_cover_initialized_name()) return;
    322     invalid_productions_ |= CoverInitializedNameProduction;
    323     Add(Error(loc, message, kCoverInitializedNameProduction, arg));
    324   }
    325 
    326   void RecordTailCallExpressionError(const Scanner::Location& loc,
    327                                      MessageTemplate::Template message,
    328                                      const char* arg = nullptr) {
    329     if (has_tail_call_expression()) return;
    330     invalid_productions_ |= TailCallExpressionProduction;
    331     Add(Error(loc, message, kTailCallExpressionProduction, arg));
    332   }
    333 
    334   void ForgiveCoverInitializedNameError() {
    335     if (!(invalid_productions_ & CoverInitializedNameProduction)) return;
    336     Error& e = reported_error(kCoverInitializedNameProduction);
    337     e.kind = kUnusedError;
    338     invalid_productions_ &= ~CoverInitializedNameProduction;
    339   }
    340 
    341   void ForgiveAssignmentPatternError() {
    342     if (!(invalid_productions_ & AssignmentPatternProduction)) return;
    343     Error& e = reported_error(kAssignmentPatternProduction);
    344     e.kind = kUnusedError;
    345     invalid_productions_ &= ~AssignmentPatternProduction;
    346   }
    347 
    348   void Accumulate(ExpressionClassifier* inner,
    349                   unsigned productions = StandardProductions,
    350                   bool merge_non_patterns = true) {
    351     DCHECK_EQ(inner->reported_errors_, reported_errors_);
    352     DCHECK_EQ(inner->reported_errors_begin_, reported_errors_end_);
    353     DCHECK_EQ(inner->reported_errors_end_, reported_errors_->length());
    354     if (merge_non_patterns) MergeNonPatterns(inner);
    355     // Propagate errors from inner, but don't overwrite already recorded
    356     // errors.
    357     unsigned non_arrow_inner_invalid_productions =
    358         inner->invalid_productions_ & ~ArrowFormalParametersProduction;
    359     if (non_arrow_inner_invalid_productions) {
    360       unsigned errors = non_arrow_inner_invalid_productions & productions &
    361                         ~invalid_productions_;
    362       // The result will continue to be a valid arrow formal parameters if the
    363       // inner expression is a valid binding pattern.
    364       bool copy_BP_to_AFP = false;
    365       if (productions & ArrowFormalParametersProduction &&
    366           is_valid_arrow_formal_parameters()) {
    367         // Also copy function properties if expecting an arrow function
    368         // parameter.
    369         function_properties_ |= inner->function_properties_;
    370         if (!inner->is_valid_binding_pattern()) {
    371           copy_BP_to_AFP = true;
    372           invalid_productions_ |= ArrowFormalParametersProduction;
    373         }
    374       }
    375       // Traverse the list of errors reported by the inner classifier
    376       // to copy what's necessary.
    377       if (errors != 0 || copy_BP_to_AFP) {
    378         invalid_productions_ |= errors;
    379         int binding_pattern_index = inner->reported_errors_end_;
    380         for (int i = inner->reported_errors_begin_;
    381              i < inner->reported_errors_end_; i++) {
    382           int k = reported_errors_->at(i).kind;
    383           if (errors & (1 << k)) Copy(i);
    384           // Check if it's a BP error that has to be copied to an AFP error.
    385           if (k == kBindingPatternProduction && copy_BP_to_AFP) {
    386             if (reported_errors_end_ <= i) {
    387               // If the BP error itself has not already been copied,
    388               // copy it now and change it to an AFP error.
    389               Copy(i);
    390               reported_errors_->at(reported_errors_end_-1).kind =
    391                   kArrowFormalParametersProduction;
    392             } else {
    393               // Otherwise, if the BP error was already copied, keep its
    394               // position and wait until the end of the traversal.
    395               DCHECK_EQ(reported_errors_end_, i+1);
    396               binding_pattern_index = i;
    397             }
    398           }
    399         }
    400         // Do we still have to copy the BP error to an AFP error?
    401         if (binding_pattern_index < inner->reported_errors_end_) {
    402           // If there's still unused space in the list of the inner
    403           // classifier, copy it there, otherwise add it to the end
    404           // of the list.
    405           if (reported_errors_end_ < inner->reported_errors_end_)
    406             Copy(binding_pattern_index);
    407           else
    408             Add(reported_errors_->at(binding_pattern_index));
    409           reported_errors_->at(reported_errors_end_-1).kind =
    410               kArrowFormalParametersProduction;
    411         }
    412       }
    413     }
    414     reported_errors_->Rewind(reported_errors_end_);
    415     inner->reported_errors_begin_ = inner->reported_errors_end_ =
    416         reported_errors_end_;
    417   }
    418 
    419   V8_INLINE int GetNonPatternBegin() const { return non_pattern_begin_; }
    420 
    421   V8_INLINE void Discard() {
    422     if (reported_errors_end_ == reported_errors_->length()) {
    423       reported_errors_->Rewind(reported_errors_begin_);
    424       reported_errors_end_ = reported_errors_begin_;
    425     }
    426     DCHECK_EQ(reported_errors_begin_, reported_errors_end_);
    427     DCHECK_LE(non_pattern_begin_, non_patterns_to_rewrite_->length());
    428     non_patterns_to_rewrite_->Rewind(non_pattern_begin_);
    429   }
    430 
    431   V8_INLINE void MergeNonPatterns(ExpressionClassifier* inner) {
    432     DCHECK_LE(non_pattern_begin_, inner->non_pattern_begin_);
    433     inner->non_pattern_begin_ = inner->non_patterns_to_rewrite_->length();
    434   }
    435 
    436  private:
    437   V8_INLINE Error& reported_error(ErrorKind kind) const {
    438     if (invalid_productions_ & (1 << kind)) {
    439       for (int i = reported_errors_begin_; i < reported_errors_end_; i++) {
    440         if (reported_errors_->at(i).kind == kind)
    441           return reported_errors_->at(i);
    442       }
    443       UNREACHABLE();
    444     }
    445     // We should only be looking for an error when we know that one has
    446     // been reported.  But we're not...  So this is to make sure we have
    447     // the same behaviour.
    448     static Error none;
    449     return none;
    450   }
    451 
    452   // Adds e to the end of the list of reported errors for this classifier.
    453   // It is expected that this classifier is the last one in the stack.
    454   V8_INLINE void Add(const Error& e) {
    455     DCHECK_EQ(reported_errors_end_, reported_errors_->length());
    456     reported_errors_->Add(e, zone_);
    457     reported_errors_end_++;
    458   }
    459 
    460   // Copies the error at position i of the list of reported errors, so that
    461   // it becomes the last error reported for this classifier.  Position i
    462   // could be either after the existing errors of this classifier (i.e.,
    463   // in an inner classifier) or it could be an existing error (in case a
    464   // copy is needed).
    465   V8_INLINE void Copy(int i) {
    466     DCHECK_LT(i, reported_errors_->length());
    467     if (reported_errors_end_ != i)
    468       reported_errors_->at(reported_errors_end_) = reported_errors_->at(i);
    469     reported_errors_end_++;
    470   }
    471 
    472   Zone* zone_;
    473   ZoneList<typename Traits::Type::Expression>* non_patterns_to_rewrite_;
    474   ZoneList<Error>* reported_errors_;
    475   DuplicateFinder* duplicate_finder_;
    476   // The uint16_t for non_pattern_begin_ will not be enough in the case,
    477   // e.g., of an array literal containing more than 64K inner array
    478   // literals with spreads, as in:
    479   // var N=65536; eval("var x=[];" + "[" + "[...x],".repeat(N) + "].length");
    480   // An implementation limit error in ParserBase::AddNonPatternForRewriting
    481   // will be triggered in this case.
    482   uint16_t non_pattern_begin_;
    483   unsigned invalid_productions_ : 14;
    484   unsigned function_properties_ : 2;
    485   // The uint16_t for reported_errors_begin_ and reported_errors_end_ will
    486   // not be enough in the case of a long series of expressions using nested
    487   // classifiers, e.g., a long sequence of assignments, as in:
    488   // literals with spreads, as in:
    489   // var N=65536; eval("var x;" + "x=".repeat(N) + "42");
    490   // This should not be a problem, as such things currently fail with a
    491   // stack overflow while parsing.
    492   uint16_t reported_errors_begin_;
    493   uint16_t reported_errors_end_;
    494 };
    495 
    496 
    497 #undef ERROR_CODES
    498 
    499 
    500 }  // namespace internal
    501 }  // namespace v8
    502 
    503 #endif  // V8_PARSING_EXPRESSION_CLASSIFIER_H
    504