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