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
|
