1 /*
2 * This file exposes PyAST_Validate interface to check the integrity
3 * of the given abstract syntax tree (potentially constructed manually).
4 */
5 #include "Python.h"
6 #include "pycore_ast.h" // asdl_stmt_seq
7 #include "pycore_pystate.h" // _PyThreadState_GET()
8
9 #include <assert.h>
10 #include <stdbool.h>
11
12 struct validator {
13 int recursion_depth; /* current recursion depth */
14 int recursion_limit; /* recursion limit */
15 };
16
17 static int validate_stmts(struct validator *, asdl_stmt_seq *);
18 static int validate_exprs(struct validator *, asdl_expr_seq *, expr_context_ty, int);
19 static int validate_patterns(struct validator *, asdl_pattern_seq *, int);
20 static int _validate_nonempty_seq(asdl_seq *, const char *, const char *);
21 static int validate_stmt(struct validator *, stmt_ty);
22 static int validate_expr(struct validator *, expr_ty, expr_context_ty);
23 static int validate_pattern(struct validator *, pattern_ty, int);
24
25 #define VALIDATE_POSITIONS(node) \
26 if (node->lineno > node->end_lineno) { \
27 PyErr_Format(PyExc_ValueError, \
28 "AST node line range (%d, %d) is not valid", \
29 node->lineno, node->end_lineno); \
30 return 0; \
31 } \
32 if ((node->lineno < 0 && node->end_lineno != node->lineno) || \
33 (node->col_offset < 0 && node->col_offset != node->end_col_offset)) { \
34 PyErr_Format(PyExc_ValueError, \
35 "AST node column range (%d, %d) for line range (%d, %d) is not valid", \
36 node->col_offset, node->end_col_offset, node->lineno, node->end_lineno); \
37 return 0; \
38 } \
39 if (node->lineno == node->end_lineno && node->col_offset > node->end_col_offset) { \
40 PyErr_Format(PyExc_ValueError, \
41 "line %d, column %d-%d is not a valid range", \
42 node->lineno, node->col_offset, node->end_col_offset); \
43 return 0; \
44 }
45
46 static int
47 validate_name(PyObject *name)
48 {
49 assert(!PyErr_Occurred());
50 assert(PyUnicode_Check(name));
51 static const char * const forbidden[] = {
52 "None",
53 "True",
54 "False",
55 NULL
56 };
57 for (int i = 0; forbidden[i] != NULL; i++) {
58 if (_PyUnicode_EqualToASCIIString(name, forbidden[i])) {
59 PyErr_Format(PyExc_ValueError, "identifier field can't represent '%s' constant", forbidden[i]);
60 return 0;
61 }
62 }
63 return 1;
64 }
65
66 static int
67 validate_comprehension(struct validator *state, asdl_comprehension_seq *gens)
68 {
69 assert(!PyErr_Occurred());
70 if (!asdl_seq_LEN(gens)) {
71 PyErr_SetString(PyExc_ValueError, "comprehension with no generators");
72 return 0;
73 }
74 for (Py_ssize_t i = 0; i < asdl_seq_LEN(gens); i++) {
75 comprehension_ty comp = asdl_seq_GET(gens, i);
76 if (!validate_expr(state, comp->target, Store) ||
77 !validate_expr(state, comp->iter, Load) ||
78 !validate_exprs(state, comp->ifs, Load, 0))
79 return 0;
80 }
81 return 1;
82 }
83
84 static int
85 validate_keywords(struct validator *state, asdl_keyword_seq *keywords)
86 {
87 assert(!PyErr_Occurred());
88 for (Py_ssize_t i = 0; i < asdl_seq_LEN(keywords); i++)
89 if (!validate_expr(state, (asdl_seq_GET(keywords, i))->value, Load))
90 return 0;
91 return 1;
92 }
93
94 static int
95 validate_args(struct validator *state, asdl_arg_seq *args)
96 {
97 assert(!PyErr_Occurred());
98 for (Py_ssize_t i = 0; i < asdl_seq_LEN(args); i++) {
99 arg_ty arg = asdl_seq_GET(args, i);
100 VALIDATE_POSITIONS(arg);
101 if (arg->annotation && !validate_expr(state, arg->annotation, Load))
102 return 0;
103 }
104 return 1;
105 }
106
107 static const char *
108 expr_context_name(expr_context_ty ctx)
109 {
110 switch (ctx) {
111 case Load:
112 return "Load";
113 case Store:
114 return "Store";
115 case Del:
116 return "Del";
117 // No default case so compiler emits warning for unhandled cases
118 }
119 Py_UNREACHABLE();
120 }
121
122 static int
123 validate_arguments(struct validator *state, arguments_ty args)
124 {
125 assert(!PyErr_Occurred());
126 if (!validate_args(state, args->posonlyargs) || !validate_args(state, args->args)) {
127 return 0;
128 }
129 if (args->vararg && args->vararg->annotation
130 && !validate_expr(state, args->vararg->annotation, Load)) {
131 return 0;
132 }
133 if (!validate_args(state, args->kwonlyargs))
134 return 0;
135 if (args->kwarg && args->kwarg->annotation
136 && !validate_expr(state, args->kwarg->annotation, Load)) {
137 return 0;
138 }
139 if (asdl_seq_LEN(args->defaults) > asdl_seq_LEN(args->posonlyargs) + asdl_seq_LEN(args->args)) {
140 PyErr_SetString(PyExc_ValueError, "more positional defaults than args on arguments");
141 return 0;
142 }
143 if (asdl_seq_LEN(args->kw_defaults) != asdl_seq_LEN(args->kwonlyargs)) {
144 PyErr_SetString(PyExc_ValueError, "length of kwonlyargs is not the same as "
145 "kw_defaults on arguments");
146 return 0;
147 }
148 return validate_exprs(state, args->defaults, Load, 0) && validate_exprs(state, args->kw_defaults, Load, 1);
149 }
150
151 static int
152 validate_constant(struct validator *state, PyObject *value)
153 {
154 assert(!PyErr_Occurred());
155 if (value == Py_None || value == Py_Ellipsis)
156 return 1;
157
158 if (PyLong_CheckExact(value)
159 || PyFloat_CheckExact(value)
160 || PyComplex_CheckExact(value)
161 || PyBool_Check(value)
162 || PyUnicode_CheckExact(value)
163 || PyBytes_CheckExact(value))
164 return 1;
165
166 if (PyTuple_CheckExact(value) || PyFrozenSet_CheckExact(value)) {
167 if (++state->recursion_depth > state->recursion_limit) {
168 PyErr_SetString(PyExc_RecursionError,
169 "maximum recursion depth exceeded during compilation");
170 return 0;
171 }
172
173 PyObject *it = PyObject_GetIter(value);
174 if (it == NULL)
175 return 0;
176
177 while (1) {
178 PyObject *item = PyIter_Next(it);
179 if (item == NULL) {
180 if (PyErr_Occurred()) {
181 Py_DECREF(it);
182 return 0;
183 }
184 break;
185 }
186
187 if (!validate_constant(state, item)) {
188 Py_DECREF(it);
189 Py_DECREF(item);
190 return 0;
191 }
192 Py_DECREF(item);
193 }
194
195 Py_DECREF(it);
196 --state->recursion_depth;
197 return 1;
198 }
199
200 if (!PyErr_Occurred()) {
201 PyErr_Format(PyExc_TypeError,
202 "got an invalid type in Constant: %s",
203 _PyType_Name(Py_TYPE(value)));
204 }
205 return 0;
206 }
207
208 static int
209 validate_expr(struct validator *state, expr_ty exp, expr_context_ty ctx)
210 {
211 assert(!PyErr_Occurred());
212 VALIDATE_POSITIONS(exp);
213 int ret = -1;
214 if (++state->recursion_depth > state->recursion_limit) {
215 PyErr_SetString(PyExc_RecursionError,
216 "maximum recursion depth exceeded during compilation");
217 return 0;
218 }
219 int check_ctx = 1;
220 expr_context_ty actual_ctx;
221
222 /* First check expression context. */
223 switch (exp->kind) {
224 case Attribute_kind:
225 actual_ctx = exp->v.Attribute.ctx;
226 break;
227 case Subscript_kind:
228 actual_ctx = exp->v.Subscript.ctx;
229 break;
230 case Starred_kind:
231 actual_ctx = exp->v.Starred.ctx;
232 break;
233 case Name_kind:
234 if (!validate_name(exp->v.Name.id)) {
235 return 0;
236 }
237 actual_ctx = exp->v.Name.ctx;
238 break;
239 case List_kind:
240 actual_ctx = exp->v.List.ctx;
241 break;
242 case Tuple_kind:
243 actual_ctx = exp->v.Tuple.ctx;
244 break;
245 default:
246 if (ctx != Load) {
247 PyErr_Format(PyExc_ValueError, "expression which can't be "
248 "assigned to in %s context", expr_context_name(ctx));
249 return 0;
250 }
251 check_ctx = 0;
252 /* set actual_ctx to prevent gcc warning */
253 actual_ctx = 0;
254 }
255 if (check_ctx && actual_ctx != ctx) {
256 PyErr_Format(PyExc_ValueError, "expression must have %s context but has %s instead",
257 expr_context_name(ctx), expr_context_name(actual_ctx));
258 return 0;
259 }
260
261 /* Now validate expression. */
262 switch (exp->kind) {
263 case BoolOp_kind:
264 if (asdl_seq_LEN(exp->v.BoolOp.values) < 2) {
265 PyErr_SetString(PyExc_ValueError, "BoolOp with less than 2 values");
266 return 0;
267 }
268 ret = validate_exprs(state, exp->v.BoolOp.values, Load, 0);
269 break;
270 case BinOp_kind:
271 ret = validate_expr(state, exp->v.BinOp.left, Load) &&
272 validate_expr(state, exp->v.BinOp.right, Load);
273 break;
274 case UnaryOp_kind:
275 ret = validate_expr(state, exp->v.UnaryOp.operand, Load);
276 break;
277 case Lambda_kind:
278 ret = validate_arguments(state, exp->v.Lambda.args) &&
279 validate_expr(state, exp->v.Lambda.body, Load);
280 break;
281 case IfExp_kind:
282 ret = validate_expr(state, exp->v.IfExp.test, Load) &&
283 validate_expr(state, exp->v.IfExp.body, Load) &&
284 validate_expr(state, exp->v.IfExp.orelse, Load);
285 break;
286 case Dict_kind:
287 if (asdl_seq_LEN(exp->v.Dict.keys) != asdl_seq_LEN(exp->v.Dict.values)) {
288 PyErr_SetString(PyExc_ValueError,
289 "Dict doesn't have the same number of keys as values");
290 return 0;
291 }
292 /* null_ok=1 for keys expressions to allow dict unpacking to work in
293 dict literals, i.e. ``{**{a:b}}`` */
294 ret = validate_exprs(state, exp->v.Dict.keys, Load, /*null_ok=*/ 1) &&
295 validate_exprs(state, exp->v.Dict.values, Load, /*null_ok=*/ 0);
296 break;
297 case Set_kind:
298 ret = validate_exprs(state, exp->v.Set.elts, Load, 0);
299 break;
300 #define COMP(NAME) \
301 case NAME ## _kind: \
302 ret = validate_comprehension(state, exp->v.NAME.generators) && \
303 validate_expr(state, exp->v.NAME.elt, Load); \
304 break;
305 COMP(ListComp)
306 COMP(SetComp)
307 COMP(GeneratorExp)
308 #undef COMP
309 case DictComp_kind:
310 ret = validate_comprehension(state, exp->v.DictComp.generators) &&
311 validate_expr(state, exp->v.DictComp.key, Load) &&
312 validate_expr(state, exp->v.DictComp.value, Load);
313 break;
314 case Yield_kind:
315 ret = !exp->v.Yield.value || validate_expr(state, exp->v.Yield.value, Load);
316 break;
317 case YieldFrom_kind:
318 ret = validate_expr(state, exp->v.YieldFrom.value, Load);
319 break;
320 case Await_kind:
321 ret = validate_expr(state, exp->v.Await.value, Load);
322 break;
323 case Compare_kind:
324 if (!asdl_seq_LEN(exp->v.Compare.comparators)) {
325 PyErr_SetString(PyExc_ValueError, "Compare with no comparators");
326 return 0;
327 }
328 if (asdl_seq_LEN(exp->v.Compare.comparators) !=
329 asdl_seq_LEN(exp->v.Compare.ops)) {
330 PyErr_SetString(PyExc_ValueError, "Compare has a different number "
331 "of comparators and operands");
332 return 0;
333 }
334 ret = validate_exprs(state, exp->v.Compare.comparators, Load, 0) &&
335 validate_expr(state, exp->v.Compare.left, Load);
336 break;
337 case Call_kind:
338 ret = validate_expr(state, exp->v.Call.func, Load) &&
339 validate_exprs(state, exp->v.Call.args, Load, 0) &&
340 validate_keywords(state, exp->v.Call.keywords);
341 break;
342 case Constant_kind:
343 if (!validate_constant(state, exp->v.Constant.value)) {
344 return 0;
345 }
346 ret = 1;
347 break;
348 case JoinedStr_kind:
349 ret = validate_exprs(state, exp->v.JoinedStr.values, Load, 0);
350 break;
351 case FormattedValue_kind:
352 if (validate_expr(state, exp->v.FormattedValue.value, Load) == 0)
353 return 0;
354 if (exp->v.FormattedValue.format_spec) {
355 ret = validate_expr(state, exp->v.FormattedValue.format_spec, Load);
356 break;
357 }
358 ret = 1;
359 break;
360 case Attribute_kind:
361 ret = validate_expr(state, exp->v.Attribute.value, Load);
362 break;
363 case Subscript_kind:
364 ret = validate_expr(state, exp->v.Subscript.slice, Load) &&
365 validate_expr(state, exp->v.Subscript.value, Load);
366 break;
367 case Starred_kind:
368 ret = validate_expr(state, exp->v.Starred.value, ctx);
369 break;
370 case Slice_kind:
371 ret = (!exp->v.Slice.lower || validate_expr(state, exp->v.Slice.lower, Load)) &&
372 (!exp->v.Slice.upper || validate_expr(state, exp->v.Slice.upper, Load)) &&
373 (!exp->v.Slice.step || validate_expr(state, exp->v.Slice.step, Load));
374 break;
375 case List_kind:
376 ret = validate_exprs(state, exp->v.List.elts, ctx, 0);
377 break;
378 case Tuple_kind:
379 ret = validate_exprs(state, exp->v.Tuple.elts, ctx, 0);
380 break;
381 case NamedExpr_kind:
382 if (exp->v.NamedExpr.target->kind != Name_kind) {
383 PyErr_SetString(PyExc_TypeError,
384 "NamedExpr target must be a Name");
385 return 0;
386 }
387 ret = validate_expr(state, exp->v.NamedExpr.value, Load);
388 break;
389 /* This last case doesn't have any checking. */
390 case Name_kind:
391 ret = 1;
392 break;
393 // No default case so compiler emits warning for unhandled cases
394 }
395 if (ret < 0) {
396 PyErr_SetString(PyExc_SystemError, "unexpected expression");
397 ret = 0;
398 }
399 state->recursion_depth--;
400 return ret;
401 }
402
403
404 // Note: the ensure_literal_* functions are only used to validate a restricted
405 // set of non-recursive literals that have already been checked with
406 // validate_expr, so they don't accept the validator state
407 static int
408 ensure_literal_number(expr_ty exp, bool allow_real, bool allow_imaginary)
409 {
410 assert(exp->kind == Constant_kind);
411 PyObject *value = exp->v.Constant.value;
412 return (allow_real && PyFloat_CheckExact(value)) ||
413 (allow_real && PyLong_CheckExact(value)) ||
414 (allow_imaginary && PyComplex_CheckExact(value));
415 }
416
417 static int
418 ensure_literal_negative(expr_ty exp, bool allow_real, bool allow_imaginary)
419 {
420 assert(exp->kind == UnaryOp_kind);
421 // Must be negation ...
422 if (exp->v.UnaryOp.op != USub) {
423 return 0;
424 }
425 // ... of a constant ...
426 expr_ty operand = exp->v.UnaryOp.operand;
427 if (operand->kind != Constant_kind) {
428 return 0;
429 }
430 // ... number
431 return ensure_literal_number(operand, allow_real, allow_imaginary);
432 }
433
434 static int
435 ensure_literal_complex(expr_ty exp)
436 {
437 assert(exp->kind == BinOp_kind);
438 expr_ty left = exp->v.BinOp.left;
439 expr_ty right = exp->v.BinOp.right;
440 // Ensure op is addition or subtraction
441 if (exp->v.BinOp.op != Add && exp->v.BinOp.op != Sub) {
442 return 0;
443 }
444 // Check LHS is a real number (potentially signed)
445 switch (left->kind)
446 {
447 case Constant_kind:
448 if (!ensure_literal_number(left, /*real=*/true, /*imaginary=*/false)) {
449 return 0;
450 }
451 break;
452 case UnaryOp_kind:
453 if (!ensure_literal_negative(left, /*real=*/true, /*imaginary=*/false)) {
454 return 0;
455 }
456 break;
457 default:
458 return 0;
459 }
460 // Check RHS is an imaginary number (no separate sign allowed)
461 switch (right->kind)
462 {
463 case Constant_kind:
464 if (!ensure_literal_number(right, /*real=*/false, /*imaginary=*/true)) {
465 return 0;
466 }
467 break;
468 default:
469 return 0;
470 }
471 return 1;
472 }
473
474 static int
475 validate_pattern_match_value(struct validator *state, expr_ty exp)
476 {
477 assert(!PyErr_Occurred());
478 if (!validate_expr(state, exp, Load)) {
479 return 0;
480 }
481
482 switch (exp->kind)
483 {
484 case Constant_kind:
485 /* Ellipsis and immutable sequences are not allowed.
486 For True, False and None, MatchSingleton() should
487 be used */
488 if (!validate_expr(state, exp, Load)) {
489 return 0;
490 }
491 PyObject *literal = exp->v.Constant.value;
492 if (PyLong_CheckExact(literal) || PyFloat_CheckExact(literal) ||
493 PyBytes_CheckExact(literal) || PyComplex_CheckExact(literal) ||
494 PyUnicode_CheckExact(literal)) {
495 return 1;
496 }
497 PyErr_SetString(PyExc_ValueError,
498 "unexpected constant inside of a literal pattern");
499 return 0;
500 case Attribute_kind:
501 // Constants and attribute lookups are always permitted
502 return 1;
503 case UnaryOp_kind:
504 // Negated numbers are permitted (whether real or imaginary)
505 // Compiler will complain if AST folding doesn't create a constant
506 if (ensure_literal_negative(exp, /*real=*/true, /*imaginary=*/true)) {
507 return 1;
508 }
509 break;
510 case BinOp_kind:
511 // Complex literals are permitted
512 // Compiler will complain if AST folding doesn't create a constant
513 if (ensure_literal_complex(exp)) {
514 return 1;
515 }
516 break;
517 case JoinedStr_kind:
518 // Handled in the later stages
519 return 1;
520 default:
521 break;
522 }
523 PyErr_SetString(PyExc_ValueError,
524 "patterns may only match literals and attribute lookups");
525 return 0;
526 }
527
528 static int
529 validate_capture(PyObject *name)
530 {
531 assert(!PyErr_Occurred());
532 if (_PyUnicode_EqualToASCIIString(name, "_")) {
533 PyErr_Format(PyExc_ValueError, "can't capture name '_' in patterns");
534 return 0;
535 }
536 return validate_name(name);
537 }
538
539 static int
540 validate_pattern(struct validator *state, pattern_ty p, int star_ok)
541 {
542 assert(!PyErr_Occurred());
543 VALIDATE_POSITIONS(p);
544 int ret = -1;
545 if (++state->recursion_depth > state->recursion_limit) {
546 PyErr_SetString(PyExc_RecursionError,
547 "maximum recursion depth exceeded during compilation");
548 return 0;
549 }
550 switch (p->kind) {
551 case MatchValue_kind:
552 ret = validate_pattern_match_value(state, p->v.MatchValue.value);
553 break;
554 case MatchSingleton_kind:
555 ret = p->v.MatchSingleton.value == Py_None || PyBool_Check(p->v.MatchSingleton.value);
556 if (!ret) {
557 PyErr_SetString(PyExc_ValueError,
558 "MatchSingleton can only contain True, False and None");
559 }
560 break;
561 case MatchSequence_kind:
562 ret = validate_patterns(state, p->v.MatchSequence.patterns, /*star_ok=*/1);
563 break;
564 case MatchMapping_kind:
565 if (asdl_seq_LEN(p->v.MatchMapping.keys) != asdl_seq_LEN(p->v.MatchMapping.patterns)) {
566 PyErr_SetString(PyExc_ValueError,
567 "MatchMapping doesn't have the same number of keys as patterns");
568 ret = 0;
569 break;
570 }
571
572 if (p->v.MatchMapping.rest && !validate_capture(p->v.MatchMapping.rest)) {
573 ret = 0;
574 break;
575 }
576
577 asdl_expr_seq *keys = p->v.MatchMapping.keys;
578 for (Py_ssize_t i = 0; i < asdl_seq_LEN(keys); i++) {
579 expr_ty key = asdl_seq_GET(keys, i);
580 if (key->kind == Constant_kind) {
581 PyObject *literal = key->v.Constant.value;
582 if (literal == Py_None || PyBool_Check(literal)) {
583 /* validate_pattern_match_value will ensure the key
584 doesn't contain True, False and None but it is
585 syntactically valid, so we will pass those on in
586 a special case. */
587 continue;
588 }
589 }
590 if (!validate_pattern_match_value(state, key)) {
591 ret = 0;
592 break;
593 }
594 }
595 if (ret == 0) {
596 break;
597 }
598 ret = validate_patterns(state, p->v.MatchMapping.patterns, /*star_ok=*/0);
599 break;
600 case MatchClass_kind:
601 if (asdl_seq_LEN(p->v.MatchClass.kwd_attrs) != asdl_seq_LEN(p->v.MatchClass.kwd_patterns)) {
602 PyErr_SetString(PyExc_ValueError,
603 "MatchClass doesn't have the same number of keyword attributes as patterns");
604 ret = 0;
605 break;
606 }
607 if (!validate_expr(state, p->v.MatchClass.cls, Load)) {
608 ret = 0;
609 break;
610 }
611
612 expr_ty cls = p->v.MatchClass.cls;
613 while (1) {
614 if (cls->kind == Name_kind) {
615 break;
616 }
617 else if (cls->kind == Attribute_kind) {
618 cls = cls->v.Attribute.value;
619 continue;
620 }
621 else {
622 PyErr_SetString(PyExc_ValueError,
623 "MatchClass cls field can only contain Name or Attribute nodes.");
624 ret = 0;
625 break;
626 }
627 }
628 if (ret == 0) {
629 break;
630 }
631
632 for (Py_ssize_t i = 0; i < asdl_seq_LEN(p->v.MatchClass.kwd_attrs); i++) {
633 PyObject *identifier = asdl_seq_GET(p->v.MatchClass.kwd_attrs, i);
634 if (!validate_name(identifier)) {
635 ret = 0;
636 break;
637 }
638 }
639 if (ret == 0) {
640 break;
641 }
642
643 if (!validate_patterns(state, p->v.MatchClass.patterns, /*star_ok=*/0)) {
644 ret = 0;
645 break;
646 }
647
648 ret = validate_patterns(state, p->v.MatchClass.kwd_patterns, /*star_ok=*/0);
649 break;
650 case MatchStar_kind:
651 if (!star_ok) {
652 PyErr_SetString(PyExc_ValueError, "can't use MatchStar here");
653 ret = 0;
654 break;
655 }
656 ret = p->v.MatchStar.name == NULL || validate_capture(p->v.MatchStar.name);
657 break;
658 case MatchAs_kind:
659 if (p->v.MatchAs.name && !validate_capture(p->v.MatchAs.name)) {
660 ret = 0;
661 break;
662 }
663 if (p->v.MatchAs.pattern == NULL) {
664 ret = 1;
665 }
666 else if (p->v.MatchAs.name == NULL) {
667 PyErr_SetString(PyExc_ValueError,
668 "MatchAs must specify a target name if a pattern is given");
669 ret = 0;
670 }
671 else {
672 ret = validate_pattern(state, p->v.MatchAs.pattern, /*star_ok=*/0);
673 }
674 break;
675 case MatchOr_kind:
676 if (asdl_seq_LEN(p->v.MatchOr.patterns) < 2) {
677 PyErr_SetString(PyExc_ValueError,
678 "MatchOr requires at least 2 patterns");
679 ret = 0;
680 break;
681 }
682 ret = validate_patterns(state, p->v.MatchOr.patterns, /*star_ok=*/0);
683 break;
684 // No default case, so the compiler will emit a warning if new pattern
685 // kinds are added without being handled here
686 }
687 if (ret < 0) {
688 PyErr_SetString(PyExc_SystemError, "unexpected pattern");
689 ret = 0;
690 }
691 state->recursion_depth--;
692 return ret;
693 }
694
695 static int
696 _validate_nonempty_seq(asdl_seq *seq, const char *what, const char *owner)
697 {
698 if (asdl_seq_LEN(seq))
699 return 1;
700 PyErr_Format(PyExc_ValueError, "empty %s on %s", what, owner);
701 return 0;
702 }
703 #define validate_nonempty_seq(seq, what, owner) _validate_nonempty_seq((asdl_seq*)seq, what, owner)
704
705 static int
706 validate_assignlist(struct validator *state, asdl_expr_seq *targets, expr_context_ty ctx)
707 {
708 assert(!PyErr_Occurred());
709 return validate_nonempty_seq(targets, "targets", ctx == Del ? "Delete" : "Assign") &&
710 validate_exprs(state, targets, ctx, 0);
711 }
712
713 static int
714 validate_body(struct validator *state, asdl_stmt_seq *body, const char *owner)
715 {
716 assert(!PyErr_Occurred());
717 return validate_nonempty_seq(body, "body", owner) && validate_stmts(state, body);
718 }
719
720 static int
721 validate_stmt(struct validator *state, stmt_ty stmt)
722 {
723 assert(!PyErr_Occurred());
724 VALIDATE_POSITIONS(stmt);
725 int ret = -1;
726 if (++state->recursion_depth > state->recursion_limit) {
727 PyErr_SetString(PyExc_RecursionError,
728 "maximum recursion depth exceeded during compilation");
729 return 0;
730 }
731 switch (stmt->kind) {
732 case FunctionDef_kind:
733 ret = validate_body(state, stmt->v.FunctionDef.body, "FunctionDef") &&
734 validate_arguments(state, stmt->v.FunctionDef.args) &&
735 validate_exprs(state, stmt->v.FunctionDef.decorator_list, Load, 0) &&
736 (!stmt->v.FunctionDef.returns ||
737 validate_expr(state, stmt->v.FunctionDef.returns, Load));
738 break;
739 case ClassDef_kind:
740 ret = validate_body(state, stmt->v.ClassDef.body, "ClassDef") &&
741 validate_exprs(state, stmt->v.ClassDef.bases, Load, 0) &&
742 validate_keywords(state, stmt->v.ClassDef.keywords) &&
743 validate_exprs(state, stmt->v.ClassDef.decorator_list, Load, 0);
744 break;
745 case Return_kind:
746 ret = !stmt->v.Return.value || validate_expr(state, stmt->v.Return.value, Load);
747 break;
748 case Delete_kind:
749 ret = validate_assignlist(state, stmt->v.Delete.targets, Del);
750 break;
751 case Assign_kind:
752 ret = validate_assignlist(state, stmt->v.Assign.targets, Store) &&
753 validate_expr(state, stmt->v.Assign.value, Load);
754 break;
755 case AugAssign_kind:
756 ret = validate_expr(state, stmt->v.AugAssign.target, Store) &&
757 validate_expr(state, stmt->v.AugAssign.value, Load);
758 break;
759 case AnnAssign_kind:
760 if (stmt->v.AnnAssign.target->kind != Name_kind &&
761 stmt->v.AnnAssign.simple) {
762 PyErr_SetString(PyExc_TypeError,
763 "AnnAssign with simple non-Name target");
764 return 0;
765 }
766 ret = validate_expr(state, stmt->v.AnnAssign.target, Store) &&
767 (!stmt->v.AnnAssign.value ||
768 validate_expr(state, stmt->v.AnnAssign.value, Load)) &&
769 validate_expr(state, stmt->v.AnnAssign.annotation, Load);
770 break;
771 case For_kind:
772 ret = validate_expr(state, stmt->v.For.target, Store) &&
773 validate_expr(state, stmt->v.For.iter, Load) &&
774 validate_body(state, stmt->v.For.body, "For") &&
775 validate_stmts(state, stmt->v.For.orelse);
776 break;
777 case AsyncFor_kind:
778 ret = validate_expr(state, stmt->v.AsyncFor.target, Store) &&
779 validate_expr(state, stmt->v.AsyncFor.iter, Load) &&
780 validate_body(state, stmt->v.AsyncFor.body, "AsyncFor") &&
781 validate_stmts(state, stmt->v.AsyncFor.orelse);
782 break;
783 case While_kind:
784 ret = validate_expr(state, stmt->v.While.test, Load) &&
785 validate_body(state, stmt->v.While.body, "While") &&
786 validate_stmts(state, stmt->v.While.orelse);
787 break;
788 case If_kind:
789 ret = validate_expr(state, stmt->v.If.test, Load) &&
790 validate_body(state, stmt->v.If.body, "If") &&
791 validate_stmts(state, stmt->v.If.orelse);
792 break;
793 case With_kind:
794 if (!validate_nonempty_seq(stmt->v.With.items, "items", "With"))
795 return 0;
796 for (Py_ssize_t i = 0; i < asdl_seq_LEN(stmt->v.With.items); i++) {
797 withitem_ty item = asdl_seq_GET(stmt->v.With.items, i);
798 if (!validate_expr(state, item->context_expr, Load) ||
799 (item->optional_vars && !validate_expr(state, item->optional_vars, Store)))
800 return 0;
801 }
802 ret = validate_body(state, stmt->v.With.body, "With");
803 break;
804 case AsyncWith_kind:
805 if (!validate_nonempty_seq(stmt->v.AsyncWith.items, "items", "AsyncWith"))
806 return 0;
807 for (Py_ssize_t i = 0; i < asdl_seq_LEN(stmt->v.AsyncWith.items); i++) {
808 withitem_ty item = asdl_seq_GET(stmt->v.AsyncWith.items, i);
809 if (!validate_expr(state, item->context_expr, Load) ||
810 (item->optional_vars && !validate_expr(state, item->optional_vars, Store)))
811 return 0;
812 }
813 ret = validate_body(state, stmt->v.AsyncWith.body, "AsyncWith");
814 break;
815 case Match_kind:
816 if (!validate_expr(state, stmt->v.Match.subject, Load)
817 || !validate_nonempty_seq(stmt->v.Match.cases, "cases", "Match")) {
818 return 0;
819 }
820 for (Py_ssize_t i = 0; i < asdl_seq_LEN(stmt->v.Match.cases); i++) {
821 match_case_ty m = asdl_seq_GET(stmt->v.Match.cases, i);
822 if (!validate_pattern(state, m->pattern, /*star_ok=*/0)
823 || (m->guard && !validate_expr(state, m->guard, Load))
824 || !validate_body(state, m->body, "match_case")) {
825 return 0;
826 }
827 }
828 ret = 1;
829 break;
830 case Raise_kind:
831 if (stmt->v.Raise.exc) {
832 ret = validate_expr(state, stmt->v.Raise.exc, Load) &&
833 (!stmt->v.Raise.cause || validate_expr(state, stmt->v.Raise.cause, Load));
834 break;
835 }
836 if (stmt->v.Raise.cause) {
837 PyErr_SetString(PyExc_ValueError, "Raise with cause but no exception");
838 return 0;
839 }
840 ret = 1;
841 break;
842 case Try_kind:
843 if (!validate_body(state, stmt->v.Try.body, "Try"))
844 return 0;
845 if (!asdl_seq_LEN(stmt->v.Try.handlers) &&
846 !asdl_seq_LEN(stmt->v.Try.finalbody)) {
847 PyErr_SetString(PyExc_ValueError, "Try has neither except handlers nor finalbody");
848 return 0;
849 }
850 if (!asdl_seq_LEN(stmt->v.Try.handlers) &&
851 asdl_seq_LEN(stmt->v.Try.orelse)) {
852 PyErr_SetString(PyExc_ValueError, "Try has orelse but no except handlers");
853 return 0;
854 }
855 for (Py_ssize_t i = 0; i < asdl_seq_LEN(stmt->v.Try.handlers); i++) {
856 excepthandler_ty handler = asdl_seq_GET(stmt->v.Try.handlers, i);
857 VALIDATE_POSITIONS(handler);
858 if ((handler->v.ExceptHandler.type &&
859 !validate_expr(state, handler->v.ExceptHandler.type, Load)) ||
860 !validate_body(state, handler->v.ExceptHandler.body, "ExceptHandler"))
861 return 0;
862 }
863 ret = (!asdl_seq_LEN(stmt->v.Try.finalbody) ||
864 validate_stmts(state, stmt->v.Try.finalbody)) &&
865 (!asdl_seq_LEN(stmt->v.Try.orelse) ||
866 validate_stmts(state, stmt->v.Try.orelse));
867 break;
868 case TryStar_kind:
869 if (!validate_body(state, stmt->v.TryStar.body, "TryStar"))
870 return 0;
871 if (!asdl_seq_LEN(stmt->v.TryStar.handlers) &&
872 !asdl_seq_LEN(stmt->v.TryStar.finalbody)) {
873 PyErr_SetString(PyExc_ValueError, "TryStar has neither except handlers nor finalbody");
874 return 0;
875 }
876 if (!asdl_seq_LEN(stmt->v.TryStar.handlers) &&
877 asdl_seq_LEN(stmt->v.TryStar.orelse)) {
878 PyErr_SetString(PyExc_ValueError, "TryStar has orelse but no except handlers");
879 return 0;
880 }
881 for (Py_ssize_t i = 0; i < asdl_seq_LEN(stmt->v.TryStar.handlers); i++) {
882 excepthandler_ty handler = asdl_seq_GET(stmt->v.TryStar.handlers, i);
883 if ((handler->v.ExceptHandler.type &&
884 !validate_expr(state, handler->v.ExceptHandler.type, Load)) ||
885 !validate_body(state, handler->v.ExceptHandler.body, "ExceptHandler"))
886 return 0;
887 }
888 ret = (!asdl_seq_LEN(stmt->v.TryStar.finalbody) ||
889 validate_stmts(state, stmt->v.TryStar.finalbody)) &&
890 (!asdl_seq_LEN(stmt->v.TryStar.orelse) ||
891 validate_stmts(state, stmt->v.TryStar.orelse));
892 break;
893 case Assert_kind:
894 ret = validate_expr(state, stmt->v.Assert.test, Load) &&
895 (!stmt->v.Assert.msg || validate_expr(state, stmt->v.Assert.msg, Load));
896 break;
897 case Import_kind:
898 ret = validate_nonempty_seq(stmt->v.Import.names, "names", "Import");
899 break;
900 case ImportFrom_kind:
901 if (stmt->v.ImportFrom.level < 0) {
902 PyErr_SetString(PyExc_ValueError, "Negative ImportFrom level");
903 return 0;
904 }
905 ret = validate_nonempty_seq(stmt->v.ImportFrom.names, "names", "ImportFrom");
906 break;
907 case Global_kind:
908 ret = validate_nonempty_seq(stmt->v.Global.names, "names", "Global");
909 break;
910 case Nonlocal_kind:
911 ret = validate_nonempty_seq(stmt->v.Nonlocal.names, "names", "Nonlocal");
912 break;
913 case Expr_kind:
914 ret = validate_expr(state, stmt->v.Expr.value, Load);
915 break;
916 case AsyncFunctionDef_kind:
917 ret = validate_body(state, stmt->v.AsyncFunctionDef.body, "AsyncFunctionDef") &&
918 validate_arguments(state, stmt->v.AsyncFunctionDef.args) &&
919 validate_exprs(state, stmt->v.AsyncFunctionDef.decorator_list, Load, 0) &&
920 (!stmt->v.AsyncFunctionDef.returns ||
921 validate_expr(state, stmt->v.AsyncFunctionDef.returns, Load));
922 break;
923 case Pass_kind:
924 case Break_kind:
925 case Continue_kind:
926 ret = 1;
927 break;
928 // No default case so compiler emits warning for unhandled cases
929 }
930 if (ret < 0) {
931 PyErr_SetString(PyExc_SystemError, "unexpected statement");
932 ret = 0;
933 }
934 state->recursion_depth--;
935 return ret;
936 }
937
938 static int
939 validate_stmts(struct validator *state, asdl_stmt_seq *seq)
940 {
941 assert(!PyErr_Occurred());
942 for (Py_ssize_t i = 0; i < asdl_seq_LEN(seq); i++) {
943 stmt_ty stmt = asdl_seq_GET(seq, i);
944 if (stmt) {
945 if (!validate_stmt(state, stmt))
946 return 0;
947 }
948 else {
949 PyErr_SetString(PyExc_ValueError,
950 "None disallowed in statement list");
951 return 0;
952 }
953 }
954 return 1;
955 }
956
957 static int
958 validate_exprs(struct validator *state, asdl_expr_seq *exprs, expr_context_ty ctx, int null_ok)
959 {
960 assert(!PyErr_Occurred());
961 for (Py_ssize_t i = 0; i < asdl_seq_LEN(exprs); i++) {
962 expr_ty expr = asdl_seq_GET(exprs, i);
963 if (expr) {
964 if (!validate_expr(state, expr, ctx))
965 return 0;
966 }
967 else if (!null_ok) {
968 PyErr_SetString(PyExc_ValueError,
969 "None disallowed in expression list");
970 return 0;
971 }
972
973 }
974 return 1;
975 }
976
977 static int
978 validate_patterns(struct validator *state, asdl_pattern_seq *patterns, int star_ok)
979 {
980 assert(!PyErr_Occurred());
981 for (Py_ssize_t i = 0; i < asdl_seq_LEN(patterns); i++) {
982 pattern_ty pattern = asdl_seq_GET(patterns, i);
983 if (!validate_pattern(state, pattern, star_ok)) {
984 return 0;
985 }
986 }
987 return 1;
988 }
989
990
991 /* See comments in symtable.c. */
992 #define COMPILER_STACK_FRAME_SCALE 3
993
994 int
995 _PyAST_Validate(mod_ty mod)
996 {
997 assert(!PyErr_Occurred());
998 int res = -1;
999 struct validator state;
1000 PyThreadState *tstate;
1001 int recursion_limit = Py_GetRecursionLimit();
1002 int starting_recursion_depth;
1003
1004 /* Setup recursion depth check counters */
1005 tstate = _PyThreadState_GET();
1006 if (!tstate) {
1007 return 0;
1008 }
1009 /* Be careful here to prevent overflow. */
1010 int recursion_depth = tstate->recursion_limit - tstate->recursion_remaining;
1011 starting_recursion_depth = (recursion_depth< INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
1012 recursion_depth * COMPILER_STACK_FRAME_SCALE : recursion_depth;
1013 state.recursion_depth = starting_recursion_depth;
1014 state.recursion_limit = (recursion_limit < INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
1015 recursion_limit * COMPILER_STACK_FRAME_SCALE : recursion_limit;
1016
1017 switch (mod->kind) {
1018 case Module_kind:
1019 res = validate_stmts(&state, mod->v.Module.body);
1020 break;
1021 case Interactive_kind:
1022 res = validate_stmts(&state, mod->v.Interactive.body);
1023 break;
1024 case Expression_kind:
1025 res = validate_expr(&state, mod->v.Expression.body, Load);
1026 break;
1027 case FunctionType_kind:
1028 res = validate_exprs(&state, mod->v.FunctionType.argtypes, Load, /*null_ok=*/0) &&
1029 validate_expr(&state, mod->v.FunctionType.returns, Load);
1030 break;
1031 // No default case so compiler emits warning for unhandled cases
1032 }
1033
1034 if (res < 0) {
1035 PyErr_SetString(PyExc_SystemError, "impossible module node");
1036 return 0;
1037 }
1038
1039 /* Check that the recursion depth counting balanced correctly */
1040 if (res && state.recursion_depth != starting_recursion_depth) {
1041 PyErr_Format(PyExc_SystemError,
1042 "AST validator recursion depth mismatch (before=%d, after=%d)",
1043 starting_recursion_depth, state.recursion_depth);
1044 return 0;
1045 }
1046 return res;
1047 }
1048
1049 PyObject *
1050 _PyAST_GetDocString(asdl_stmt_seq *body)
1051 {
1052 if (!asdl_seq_LEN(body)) {
1053 return NULL;
1054 }
1055 stmt_ty st = asdl_seq_GET(body, 0);
1056 if (st->kind != Expr_kind) {
1057 return NULL;
1058 }
1059 expr_ty e = st->v.Expr.value;
1060 if (e->kind == Constant_kind && PyUnicode_CheckExact(e->v.Constant.value)) {
1061 return e->v.Constant.value;
1062 }
1063 return NULL;
1064 }