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 : 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 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 function_properties_(0) { 105 base->classifier_ = this; 106 reported_errors_begin_ = reported_errors_end_ = reported_errors_->length(); 107 non_pattern_begin_ = non_patterns_to_rewrite_->length(); 108 } 109 110 V8_INLINE ~ExpressionClassifier() { 111 Discard(); 112 if (base_->classifier_ == this) base_->classifier_ = previous_; 113 } 114 115 V8_INLINE bool is_valid(unsigned productions) const { 116 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 return !(function_properties_ & NonSimpleParameter); 199 } 200 201 V8_INLINE void RecordNonSimpleParameter() { 202 function_properties_ |= NonSimpleParameter; 203 } 204 205 void RecordExpressionError(const Scanner::Location& loc, 206 MessageTemplate::Template message, 207 const char* arg = nullptr) { 208 if (!is_valid_expression()) return; 209 invalid_productions_ |= ExpressionProduction; 210 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 void RecordFormalParameterInitializerError(const Scanner::Location& loc, 222 MessageTemplate::Template message, 223 const char* arg = nullptr) { 224 if (!is_valid_formal_parameter_initializer()) return; 225 invalid_productions_ |= FormalParameterInitializerProduction; 226 Add(Error(loc, message, kFormalParameterInitializerProduction, arg)); 227 } 228 229 void RecordBindingPatternError(const Scanner::Location& loc, 230 MessageTemplate::Template message, 231 const char* arg = nullptr) { 232 if (!is_valid_binding_pattern()) return; 233 invalid_productions_ |= BindingPatternProduction; 234 Add(Error(loc, message, kBindingPatternProduction, arg)); 235 } 236 237 void RecordAssignmentPatternError(const Scanner::Location& loc, 238 MessageTemplate::Template message, 239 const char* arg = nullptr) { 240 if (!is_valid_assignment_pattern()) return; 241 invalid_productions_ |= AssignmentPatternProduction; 242 Add(Error(loc, message, kAssignmentPatternProduction, arg)); 243 } 244 245 void RecordPatternError(const Scanner::Location& loc, 246 MessageTemplate::Template message, 247 const char* arg = nullptr) { 248 RecordBindingPatternError(loc, message, arg); 249 RecordAssignmentPatternError(loc, message, arg); 250 } 251 252 void RecordArrowFormalParametersError(const Scanner::Location& loc, 253 MessageTemplate::Template message, 254 const char* arg = nullptr) { 255 if (!is_valid_arrow_formal_parameters()) return; 256 invalid_productions_ |= ArrowFormalParametersProduction; 257 Add(Error(loc, message, kArrowFormalParametersProduction, arg)); 258 } 259 260 void RecordAsyncArrowFormalParametersError(const Scanner::Location& loc, 261 MessageTemplate::Template message, 262 const char* arg = nullptr) { 263 if (!is_valid_async_arrow_formal_parameters()) return; 264 invalid_productions_ |= AsyncArrowFormalParametersProduction; 265 Add(Error(loc, message, kAsyncArrowFormalParametersProduction, arg)); 266 } 267 268 void RecordDuplicateFormalParameterError(const Scanner::Location& loc) { 269 if (!is_valid_formal_parameter_list_without_duplicates()) return; 270 invalid_productions_ |= DistinctFormalParametersProduction; 271 Add(Error(loc, MessageTemplate::kParamDupe, 272 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 void RecordStrictModeFormalParameterError(const Scanner::Location& loc, 279 MessageTemplate::Template message, 280 const char* arg = nullptr) { 281 if (!is_valid_strict_mode_formal_parameters()) return; 282 invalid_productions_ |= StrictModeFormalParametersProduction; 283 Add(Error(loc, message, kStrictModeFormalParametersProduction, arg)); 284 } 285 286 void RecordLetPatternError(const Scanner::Location& loc, 287 MessageTemplate::Template message, 288 const char* arg = nullptr) { 289 if (!is_valid_let_pattern()) return; 290 invalid_productions_ |= LetPatternProduction; 291 Add(Error(loc, message, kLetPatternProduction, arg)); 292 } 293 294 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 if (merge_non_patterns) 304 inner->non_pattern_begin_ = non_patterns_to_rewrite_->length(); 305 else 306 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 inner->invalid_productions_ & ~ArrowFormalParametersProduction; 311 if (non_arrow_inner_invalid_productions) { 312 unsigned errors = non_arrow_inner_invalid_productions & productions & 313 ~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 if (productions & ArrowFormalParametersProduction && 318 is_valid_arrow_formal_parameters()) { 319 // Also copy function properties if expecting an arrow function 320 // parameter. 321 function_properties_ |= inner->function_properties_; 322 if (!inner->is_valid_binding_pattern()) { 323 copy_BP_to_AFP = true; 324 invalid_productions_ |= ArrowFormalParametersProduction; 325 } 326 } 327 // Traverse the list of errors reported by the inner classifier 328 // to copy what's necessary. 329 if (errors != 0 || copy_BP_to_AFP) { 330 invalid_productions_ |= errors; 331 int binding_pattern_index = inner->reported_errors_end_; 332 for (int i = inner->reported_errors_begin_; 333 i < inner->reported_errors_end_; i++) { 334 int k = reported_errors_->at(i).kind; 335 if (errors & (1 << k)) Copy(i); 336 // Check if it's a BP error that has to be copied to an AFP error. 337 if (k == kBindingPatternProduction && copy_BP_to_AFP) { 338 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 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 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 if (reported_errors_end_ < inner->reported_errors_end_) 358 Copy(binding_pattern_index); 359 else 360 Add(reported_errors_->at(binding_pattern_index)); 361 reported_errors_->at(reported_errors_end_-1).kind = 362 kArrowFormalParametersProduction; 363 } 364 } 365 } 366 reported_errors_->Rewind(reported_errors_end_); 367 inner->reported_errors_begin_ = inner->reported_errors_end_ = 368 reported_errors_end_; 369 } 370 371 V8_INLINE int GetNonPatternBegin() const { return non_pattern_begin_; } 372 373 V8_INLINE void Discard() { 374 if (reported_errors_end_ == reported_errors_->length()) { 375 reported_errors_->Rewind(reported_errors_begin_); 376 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 non_patterns_to_rewrite_->Rewind(non_pattern_begin_); 381 } 382 383 ExpressionClassifier* previous() const { return previous_; } 384 385 private: 386 V8_INLINE const Error& reported_error(ErrorKind kind) const { 387 if (invalid_productions_ & (1 << kind)) { 388 for (int i = reported_errors_begin_; i < reported_errors_end_; i++) { 389 if (reported_errors_->at(i).kind == kind) 390 return reported_errors_->at(i); 391 } 392 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 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 reported_errors_->Add(e, zone_); 409 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 if (reported_errors_end_ != i) 420 reported_errors_->at(reported_errors_end_) = reported_errors_->at(i); 421 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 460
