big_code_analysis_ast/lang_helpers/python.rs
1//! Python: the aliased `block` and `lambda` kind sets, and the shape
2//! of a docstring.
3
4use crate::Python;
5use crate::lang_helpers::doc_comment::node_bytes;
6use crate::node::{AncestorIter, Ancestors, Cursor, FoldLane, Node};
7
8/// Whether `node` is a Python `lambda` expression, under either of the
9/// grammar's two aliased kind_ids: `Lambda` (196, the concrete
10/// production emitted today) and `Lambda2` (197, the currently-unseen
11/// hidden alias). `Lambda3` (73) is the `lambda` *keyword* token, not a
12/// closure node, and is intentionally excluded.
13///
14/// This is the single normalization chokepoint for the lambda-alias set
15/// — mirroring [`python_is_block`] for the block aliases (#419). It
16/// is reused by `PythonCode::is_closure` here, by
17/// [`python_lambdas_below_statement_boundary`] and by the cognitive
18/// boolean-operator gate in `big-code-analysis`, so a future grammar bump
19/// that promotes `Lambda2` to a concrete node is handled in exactly one
20/// place rather than drifting across sites (#422). The
21/// `python_hidden_block_and_lambda_aliases_stay_unseen` drift guard in
22/// `checker.rs` trips on such a bump.
23#[inline]
24#[must_use]
25pub fn python_is_lambda(node: &Node) -> bool {
26 matches!(node.kind_id().into(), Python::Lambda | Python::Lambda2)
27}
28
29/// How many `lambda`s enclose `node` below its nearest statement
30/// boundary — an `expression_list`, `if`, `for` or `while` — the count
31/// `node.count_specific_ancestors::<PythonCode>(ancestors,
32/// python_is_lambda, boundary)` takes.
33///
34/// That climb runs to the root where no boundary is near — a boolean
35/// operator in each level of a nested list — and was quadratic in depth
36/// asked of every such operator (#1767). Under a walk that lent a
37/// `FoldCache` the count is folded down the chain instead, each ancestor
38/// once per walk. The fold's state is a `u8`; past 254 lambdas it
39/// saturates and the exact climb answers, so the count is exact at every
40/// depth and only a lambda nest that deep pays the climb.
41#[must_use]
42pub fn python_lambdas_below_statement_boundary(
43 node: &Node<'_>,
44 ancestors: Ancestors<'_, '_>,
45) -> usize {
46 let climb = || {
47 node.count_specific_ancestors::<crate::langs::PythonCode>(
48 ancestors,
49 python_is_lambda,
50 is_statement_boundary,
51 )
52 };
53 if !ancestors.memoises_folds() {
54 return climb();
55 }
56 let folded = ancestors.fold_down(
57 node,
58 0,
59 FoldLane::LambdaDepth,
60 0,
61 |lambdas, ancestor, _, _| {
62 if is_statement_boundary(ancestor) {
63 0
64 } else if python_is_lambda(ancestor) {
65 lambdas.saturating_add(1)
66 } else {
67 lambdas
68 }
69 },
70 );
71 if folded == u8::MAX {
72 climb()
73 } else {
74 usize::from(folded)
75 }
76}
77
78/// The statement boundary [`python_lambdas_below_statement_boundary`]
79/// stops at. Only `expression_list` can change the count: a lambda body
80/// is a single expression, so no lambda ever sits *above* an `if` /
81/// `for` / `while` statement, and stopping at one is indistinguishable
82/// from running to the module root. The three statement kinds are kept
83/// as an explicit boundary set rather than a claim about coverage
84/// (#1090).
85fn is_statement_boundary(node: &Node) -> bool {
86 matches!(
87 node.kind_id().into(),
88 Python::ExpressionList
89 | Python::IfStatement
90 | Python::ForStatement
91 | Python::WhileStatement
92 )
93}
94
95/// Single normalization point for Python's aliased `block` kind_ids.
96///
97/// tree-sitter-python lists two `kind_id`s that both stringify to
98/// `"block"`: `Block` (135, the hidden `_block` supertype) and
99/// `Block2` (160, the concrete production). Empirically only `Block2`
100/// is ever emitted for real block bodies (function, class, if/for,
101/// while/try/with), so `Block` is dead today — but a future grammar
102/// bump could promote the supertype to a concrete node. Routing every
103/// "is this a block?" check through here means such a bump is handled
104/// at one site instead of silently undercounting at several (issue
105/// #419; lesson 2 / 34 / 56 in docs/development/lessons_learned.md).
106#[inline]
107#[must_use]
108pub fn python_is_block(node: &Node) -> bool {
109 matches!(node.kind_id().into(), Python::Block | Python::Block2)
110}
111
112/// How many parentheses CPython lets one expression nest in: its
113/// tokenizer's `MAXLEVEL` (`Parser/lexer/state.h`). A docstring wrapped
114/// deeper than this is a syntax error, so the climb and the descent
115/// through `parenthesized_expression` stop here, which also keeps each
116/// one constant-time on a file nesting thousands of them. A `u8`, so the
117/// memoised climb ([`bare_string_climb`]) saturates against it.
118const MAX_PARENTHESES: u8 = 200;
119
120/// Whether `node`, past any parentheses around it, is the sole child of
121/// an `expression_statement`: the discarded-value shape a docstring
122/// takes. CPython drops the parentheses, so `("""doc""")` is a docstring
123/// (#1610). `"a", "b"` has two children, so it is a discarded tuple, not
124/// documentation.
125#[inline]
126#[must_use]
127pub fn python_is_bare_statement_value(node: &Node, ancestors: Ancestors<'_, '_>) -> bool {
128 enclosing_statement(node, ancestors)
129 .is_some_and(|((statement, _), _)| is_bare_statement(&statement))
130}
131
132/// Whether `node` is a `parenthesized_expression` around a bare string
133/// statement's string, or one of its `(` and `)`. The parentheses belong
134/// to the docstring they wrap (#1610): neither code rows nor operators.
135///
136/// Decided from the statement down, as the string's own climb is, so a
137/// string nested past CPython's 200-parenthesis cap keeps every one of
138/// its parentheses as code rather than only the outermost. Every
139/// parenthesis of a chain asks, and a climb and a descent per parenthesis
140/// made a statement `d` deep cost `O(d²)`: a walk that lent a `FoldCache`
141/// reads the answer off a memoised fold of the ancestry instead, which
142/// unwraps each statement's value once. Any other caller climbs, which
143/// the cap bounds where a fold without its memo would run from the root.
144#[must_use]
145pub fn python_is_bare_string_parenthesis(node: &Node, ancestors: Ancestors<'_, '_>) -> bool {
146 let token = matches!(node.kind_id().into(), Python::LPAREN | Python::RPAREN);
147 let Some((paren, paren_ancestors)) = (if token {
148 ancestors.iter(node).next()
149 } else {
150 Some((*node, ancestors))
151 }) else {
152 return false;
153 };
154 if paren.kind_id() != Python::ParenthesizedExpression {
155 return false;
156 }
157 if ancestors.memoises_folds() {
158 // A token's fold stops at its parenthesis, whose state it reads.
159 let climb = ancestors.fold_down(
160 node,
161 usize::from(token),
162 FoldLane::BareStringClimb,
163 0,
164 |climb, ancestor, _, _| bare_string_climb(climb, ancestor),
165 );
166 return (1..=MAX_PARENTHESES + 1).contains(&climb);
167 }
168 enclosing_statement(&paren, paren_ancestors)
169 .is_some_and(|((statement, _), _)| statement_string(&statement).is_some())
170}
171
172/// One step of the fold [`python_is_bare_string_parenthesis`] memoises:
173/// the climb from a node through the parentheses above it to the
174/// statement holding them, or 0 when that is no bare string statement. A
175/// parenthesis lengthens the climb, saturating one past the longest climb
176/// [`enclosing_statement`] takes; any other ancestor starts one. A climb
177/// past the cap ends at a statement whose string lies past it too, so the
178/// length decides nothing there, and no recovery the grammar performs
179/// gives a parenthesis holding the string a deeper parenthesis beside it
180/// (searched, #1610): the saturation point is kept for the fold to answer
181/// as the climb does should one appear, and nothing can pin it.
182fn bare_string_climb(climb: u8, ancestor: &Node) -> u8 {
183 if ancestor.kind_id() != Python::ParenthesizedExpression {
184 u8::from(statement_string(ancestor).is_some())
185 } else if climb == 0 {
186 0
187 } else {
188 climb.saturating_add(1).min(MAX_PARENTHESES + 2)
189 }
190}
191
192/// The nearest ancestor of `node` that is not a parenthesis around it,
193/// paired with its ancestry, and the iterator continuing above it.
194fn enclosing_statement<'a, 'c>(
195 node: &Node<'a>,
196 ancestors: Ancestors<'a, 'c>,
197) -> Option<((Node<'a>, Ancestors<'a, 'c>), AncestorIter<'a, 'c>)> {
198 let mut up = ancestors.iter(node);
199 let statement = up
200 .by_ref()
201 .take(usize::from(MAX_PARENTHESES) + 1)
202 .find(|(ancestor, _)| ancestor.kind_id() != Python::ParenthesizedExpression)?;
203 Some((statement, up))
204}
205
206/// `node` with at most [`MAX_PARENTHESES`] parentheses around it removed:
207/// the expression inside, skipping the comments a parenthesized
208/// expression may hold. One cursor serves every layer.
209fn unparenthesized(node: Node) -> Node {
210 let mut cursor = node.cursor();
211 let mut value = node;
212 for _ in 0..MAX_PARENTHESES {
213 let Some(inner) = unparenthesized_once(&value, &mut cursor) else {
214 break;
215 };
216 value = inner;
217 }
218 value
219}
220
221/// The expression one `parenthesized_expression` holds, or `None` when
222/// `node` is not one, read with `cursor`: its first named child that is
223/// no extra, so an `ERROR` the grammar recovered to is still its value.
224fn unparenthesized_once<'a>(node: &Node<'a>, cursor: &mut Cursor<'a>) -> Option<Node<'a>> {
225 if node.kind_id() != Python::ParenthesizedExpression {
226 return None;
227 }
228 node.children_with(cursor).find(not_extra)
229}
230
231/// Whether `node` is one of the grammar's two extras, a `#` comment or
232/// a `\` line continuation: the nodes tree-sitter-python admits between
233/// any two tokens, which spell no part of the construct they sit in.
234#[inline]
235#[must_use]
236pub fn python_is_extra(node: &Node) -> bool {
237 matches!(
238 node.kind_id().into(),
239 Python::Comment | Python::LineContinuation
240 )
241}
242
243/// Whether `node` is a named child that spells an expression or a
244/// statement rather than one of the grammar's two extras. Both extras
245/// are *named* nodes, so `is_named` alone takes the first `\` of
246/// `( \` / `\` / `"""doc"""` as the parenthesis's value and reads the
247/// string as none (#1830); every selector of "the first real child"
248/// skips both.
249fn not_extra(node: &Node) -> bool {
250 node.is_named() && !python_is_extra(node)
251}
252
253/// Whether `statement` is a bare string statement: an
254/// `expression_statement` whose sole value is a `string` or
255/// `concatenated_string`, past any parentheses around it. Asked of a
256/// node alone, with no chain — the LOC walk's `\` finder descends to a
257/// statement that is a sibling's descendant (#1819).
258#[must_use]
259pub fn python_is_bare_string_statement(statement: &Node) -> bool {
260 statement_string(statement).is_some()
261}
262
263/// The string a bare string statement holds, past any parentheses.
264fn statement_string<'a>(statement: &Node<'a>) -> Option<Node<'a>> {
265 if !is_bare_statement(statement) {
266 return None;
267 }
268 statement.child(0).map(unparenthesized).filter(|value| {
269 matches!(
270 value.kind_id().into(),
271 Python::String | Python::ConcatenatedString
272 )
273 })
274}
275
276/// Whether `node` is a bare string statement's `string`: the statement's
277/// sole value itself, or one fragment of an implicitly concatenated
278/// literal (`"""doc""" "more"`) that is — CPython joins the fragments
279/// into one string, and so does the `concatenated_string` node.
280///
281/// The one definition of "a string whose value is discarded" for both
282/// walks that care: the Halstead getter drops its operands (#695) and
283/// the LOC walk bills its rows as comment rows (#415). Whether those rows
284/// are also *documentation* is narrower and positional — see
285/// [`python_documentation_string_run`] (#1597).
286#[inline]
287#[must_use]
288pub fn python_is_bare_string(node: &Node, ancestors: Ancestors<'_, '_>) -> bool {
289 let Some((parent, parent_ancestors)) = ancestors.iter(node).next() else {
290 return false;
291 };
292 if matches!(parent.kind_id().into(), Python::ConcatenatedString) {
293 return python_is_bare_statement_value(&parent, parent_ancestors);
294 }
295 python_is_bare_statement_value(node, ancestors)
296}
297
298/// Whether `value` — a `string` or `concatenated_string` — is a
299/// documentation string by position: a `str` literal that is the sole
300/// value of a bare statement in a docstring, additional-docstring or
301/// attribute-docstring place, per `documentation_run`, which holds the
302/// rules. One fragment of a concatenation answers `false` on its own:
303/// its nearest non-parenthesis ancestor is the `concatenated_string`,
304/// not a statement, so the scan finds no body to read — the mechanism,
305/// not a second test, which is why no `parent` check precedes it. The
306/// `Docstring` row's gate (`roles/python.rs`, #1699): one backward scan
307/// over the statement's siblings, which the run helper shares by asking
308/// this of a run's final member only. A caller asking it of every
309/// member of a run pays one scan per member.
310#[must_use]
311pub(crate) fn python_is_documentation_string(
312 value: &Node,
313 code: &[u8],
314 ancestors: Ancestors<'_, '_>,
315) -> bool {
316 documentation_run(value, code, ancestors).is_some()
317}
318
319// Each backward scan `documentation_run` makes. The scan is one per run
320// — the helper asks at the run's final member only —
321// and `one_scan_per_run` pins it by count, since no probe
322// can tell one scan per run from two (#1699).
323crate::observation::counter!(docstring_runs_scanned);
324
325/// The first statement of the documentation-string run that the bare
326/// string statement holding `value` belongs to, or `None` when that
327/// statement is not documentation — or holds more than one value, a
328/// discarded tuple being no docstring. `value` is a `string` or
329/// `concatenated_string`, per [`python_is_bare_statement_value`], and the
330/// statement documents where Python tooling reads documentation (#1597):
331///
332/// - **a docstring** (PEP 257): the first statement of a module, class or
333/// function body — the string Python stores as `__doc__`, and the one
334/// `help()`, `inspect` and pydoc read. Only a `str` literal is stored:
335/// an f-string, a template string or a bytes literal is no docstring;
336/// - **an additional docstring** (PEP 257): a string statement directly
337/// after another docstring, including an attribute or additional docstring;
338/// - **an attribute docstring** (PEP 257 and 258, read by Sphinx autodoc):
339/// a string statement directly after an assignment to a name at module
340/// or class level, or to an attribute of `self` at the top level of a
341/// class's `__init__`.
342///
343/// "Directly after" skips comments, which are not statements. Any other
344/// bare string — a triple-quoted string wrapping commented-out code in
345/// the middle of a function, a module docstring written after the
346/// imports — is still a comment row (#415) but is not documentation, so
347/// the maintainability index charges it as it charges a `#` comment.
348/// `code` is read for a literal's prefix and for `__init__`'s names.
349///
350/// One backward scan answers both: the string statements before it,
351/// skipping comments, are the run, and the first other statement ends
352/// the run and is the one an attribute docstring is documented by.
353fn documentation_run<'a>(
354 value: &Node<'a>,
355 code: &[u8],
356 ancestors: Ancestors<'a, '_>,
357) -> Option<Node<'a>> {
358 // The literal test is the cheap one; `body_attributes` may read the
359 // enclosing `__init__`'s name and parameters.
360 if !is_str_literal(value, code) {
361 return None;
362 }
363 let ((statement, statement_ancestors), up) = enclosing_statement(value, ancestors)?;
364 // A string of a discarded tuple (`"a", "b"`) is no docstring: the
365 // statement holds two values. Checked here, the one place, so the
366 // row and the run helper cannot differ on it.
367 if !is_bare_statement(&statement) {
368 return None;
369 }
370 docstring_runs_scanned::record();
371 let attributes = body_attributes(up, code)?;
372 let mut first = statement;
373 for sibling in statement_ancestors
374 .siblings_before(&statement)
375 .filter(not_extra)
376 {
377 if !is_string_statement(&sibling, code) {
378 return attributes.documented_by(&sibling, code).then_some(first);
379 }
380 first = sibling;
381 }
382 Some(first)
383}
384
385/// Credits a consecutive run of documentation strings at its last string.
386/// Comments between statements do not break the run. Deciding once keeps
387/// additional-docstring recognition linear in the number of statements.
388pub fn python_documentation_string_run(
389 value: &Node,
390 code: &[u8],
391 ancestors: Ancestors<'_, '_>,
392 mut credit: impl FnMut(usize, usize),
393) {
394 let Some(((statement, outer), _)) = enclosing_statement(value, ancestors) else {
395 return;
396 };
397 if outer
398 .siblings_after(&statement)
399 .find(not_extra)
400 .is_some_and(|next| is_string_statement(&next, code))
401 {
402 return;
403 }
404 // The run's final member. `documentation_run` is the backward scan
405 // the `Docstring` row's gate reads (#1699) and the one this needs for
406 // the run's first member, so it runs once, here: the row's verdict
407 // is `first.is_some()` by construction, the gate being this call.
408 let Some(first) = documentation_run(value, code, ancestors) else {
409 return;
410 };
411 for member in std::iter::once(first)
412 .chain(outer.siblings_after(&first))
413 .take_while(|member| member.start_byte() <= statement.start_byte())
414 .filter(|member| is_string_statement(member, code))
415 {
416 credit_documentation_rows(member, &mut credit);
417 }
418}
419
420/// Credits the rows of a string statement's value and of the `(` and `)`
421/// around it, which are part of the docstring (#1610); a comment inside
422/// the parentheses stays a comment.
423fn credit_documentation_rows(statement: Node, credit: &mut impl FnMut(usize, usize)) {
424 let Some(mut value) = statement.child(0) else {
425 return;
426 };
427 let mut cursor = value.cursor();
428 for _ in 0..MAX_PARENTHESES {
429 let Some(inner) = unparenthesized_once(&value, &mut cursor) else {
430 break;
431 };
432 for paren in value
433 .children_with(&mut cursor)
434 .filter(|child| !child.is_named())
435 {
436 credit(paren.start_row(), paren.end_row());
437 }
438 value = inner;
439 }
440 credit(value.start_row(), value.end_row());
441}
442
443/// The assignments a body reads an attribute docstring after: PEP 258's
444/// rules for the top level of a module, a class or `__init__`, with the
445/// targets Sphinx's `VariableCommentPicker` accepts there. Sphinx also
446/// reads the suites of an `if`, `with`, loop or `try` at those levels;
447/// PEP 257 does not, and neither does this.
448enum Attributes<'code> {
449 /// A module or class body: an assignment to a name, or to a tuple of
450 /// names — not to a subscript or another object's attribute, which
451 /// declares nothing there.
452 Names,
453 /// The top level of a class's `__init__`: an assignment to an
454 /// attribute of its first parameter, whose name this holds (`self`),
455 /// alone or in a tuple of targets.
456 OfSelf(&'code [u8]),
457 /// Any other function body.
458 Nothing,
459}
460
461impl Attributes<'_> {
462 /// Whether `statement`, directly before a string statement, makes that
463 /// string an attribute docstring.
464 fn documented_by(&self, statement: &Node, code: &[u8]) -> bool {
465 // A `type X = …` alias (PEP 695) declares the name it binds, and
466 // Sphinx's `VariableCommentPicker` reads it like an assignment
467 // (`AssignmentLikeType` holds `ast.TypeAlias`): a docstring after
468 // it or a `#:` comment on or above it documents `X`. It never
469 // binds an attribute of `self`.
470 if statement.kind_id() == Python::TypeAliasStatement {
471 return matches!(self, Self::Names);
472 }
473 let Some(target) = assignment_target(statement) else {
474 return false;
475 };
476 match self {
477 Self::Names => binds(&target, |leaf| leaf.kind_id() == Python::Identifier),
478 Self::OfSelf(name) => binds(&target, |leaf| {
479 leaf.kind_id() == Python::Attribute
480 && leaf.child_by_field_name("object").is_some_and(|object| {
481 object.kind_id() == Python::Identifier && node_bytes(&object, code) == *name
482 })
483 }),
484 Self::Nothing => false,
485 }
486 }
487}
488
489/// What a body makes of the assignments in it, from the ancestors above
490/// the statement: `None` when the body holds no documentation at all (an
491/// `if` or loop body).
492fn body_attributes<'code>(
493 mut up: AncestorIter<'_, '_>,
494 code: &'code [u8],
495) -> Option<Attributes<'code>> {
496 let (container, _) = up.next()?;
497 if container.kind_id() == Python::Module {
498 return Some(Attributes::Names);
499 }
500 let (owner, _) = up.next().filter(|_| python_is_block(&container))?;
501 owner_attributes(&owner, up, code)
502}
503
504/// What the body of `owner` — a class or function definition — makes of
505/// the assignments in it; `None` for any other owner. `up` continues
506/// from `owner`'s parent.
507fn owner_attributes<'code>(
508 owner: &Node,
509 up: AncestorIter<'_, '_>,
510 code: &'code [u8],
511) -> Option<Attributes<'code>> {
512 if owner.kind_id() == Python::ClassDefinition {
513 Some(Attributes::Names)
514 } else if owner.kind_id() == Python::FunctionDefinition {
515 let receiver = is_class_init(owner, up, code)
516 .then(|| first_parameter_name(owner, code))
517 .flatten();
518 Some(receiver.map_or(Attributes::Nothing, Attributes::OfSelf))
519 } else {
520 None
521 }
522}
523
524/// Whether `function` is a class's `__init__`, the one method PEP 257
525/// reads attribute docstrings in: named so, with the class the first
526/// ancestor past its decorators and the class body's block. `up`
527/// continues from `function`'s parent.
528///
529/// The search reads three ancestors at most (#1868): a
530/// `decorated_definition` holds its decorators and one definition, never
531/// a block or another `decorated_definition`, and no block's parent is
532/// a block; `the_kinds_between_a_method_and_its_class_nest_two_deep_at_most`
533/// reads that off the pinned grammar.
534fn is_class_init(function: &Node, up: AncestorIter<'_, '_>, code: &[u8]) -> bool {
535 function
536 .child_by_field_name("name")
537 .is_some_and(|name| node_bytes(&name, code) == b"__init__")
538 && up
539 .map(|(node, _)| node)
540 .find(|node| node.kind_id() != Python::DecoratedDefinition && !python_is_block(node))
541 .is_some_and(|class| class.kind_id() == Python::ClassDefinition)
542}
543
544/// The name of `function`'s first parameter, typed or not. The extras
545/// are named, and formatters put a comment right after the `(` of an
546/// exploded signature (`def __init__( # noqa: PLR0913`), a `\` too
547/// (`def __init__( \`), so both are skipped.
548fn first_parameter_name<'code>(function: &Node, code: &'code [u8]) -> Option<&'code [u8]> {
549 let first = function
550 .child_by_field_name("parameters")?
551 .children()
552 .find(not_extra)?;
553 let name = if first.kind_id() == Python::TypedParameter {
554 first.children().find(Node::is_named)?
555 } else {
556 first
557 };
558 (name.kind_id() == Python::Identifier).then(|| node_bytes(&name, code))
559}
560
561/// Whether `value` is a literal Python stores as a docstring: a `str`, not
562/// an f-string, a template string or bytes — a prefix holding `f`, `t` or
563/// `b` in either case makes the statement none, and one fragment of an
564/// implicit concatenation is enough.
565fn is_str_literal(value: &Node, code: &[u8]) -> bool {
566 let is_str = |literal: &Node| {
567 !node_bytes(literal, code)
568 .iter()
569 .take_while(|byte| byte.is_ascii_alphabetic())
570 .any(|byte| matches!(byte.to_ascii_lowercase(), b'f' | b't' | b'b'))
571 };
572 if value.kind_id() == Python::ConcatenatedString {
573 value
574 .children()
575 .filter(|fragment| fragment.kind_id() == Python::String)
576 .all(|fragment| is_str(&fragment))
577 } else {
578 is_str(value)
579 }
580}
581
582/// An `expression_statement` holding one value and nothing else: the
583/// discarded-value shape a docstring takes.
584fn is_bare_statement(statement: &Node) -> bool {
585 statement.kind_id() == Python::ExpressionStatement && statement.child_count() == 1
586}
587
588/// A bare statement whose value is a `str` literal: a docstring, when it
589/// opens its body.
590fn is_string_statement(statement: &Node, code: &[u8]) -> bool {
591 statement_string(statement).is_some_and(|value| is_str_literal(&value, code))
592}
593
594/// Whether an assignment target binds what Sphinx records an attribute
595/// docstring for, as its `get_lvar_names` reads a target: `leaf` decides a
596/// single one — a name, a subscript or an attribute — and a tuple, list or
597/// starred target binds when any element does. Walked with an explicit
598/// stack, so a target nested thousands of brackets deep cannot exhaust the
599/// thread's stack (#1597).
600fn binds(target: &Node, leaf: impl Fn(&Node) -> bool) -> bool {
601 let mut pending = vec![*target];
602 while let Some(node) = pending.pop() {
603 match node.kind_id().into() {
604 Python::Identifier | Python::Subscript | Python::Attribute => {
605 if leaf(&node) {
606 return true;
607 }
608 }
609 _ => pending.extend(node.children().filter(Node::is_named)),
610 }
611 }
612 false
613}
614
615/// The target of the assignment `statement` holds, annotated or not.
616fn assignment_target<'a>(statement: &Node<'a>) -> Option<Node<'a>> {
617 (statement.kind_id() == Python::ExpressionStatement)
618 .then(|| statement.child(0))
619 .flatten()
620 .filter(|value| value.kind_id() == Python::Assignment)
621 .and_then(|assignment| assignment.child_by_field_name("left"))
622}
623
624/// Credits the rows of a Sphinx doc comment that `comment` completes
625/// (#1597). Sphinx autodoc reads a comment starting `#:` as an
626/// attribute's documentation when it sits on the line of an assignment,
627/// after the code, or on the consecutive lines directly above one —
628/// every one of them `#:`; a plain `#` line breaks the block. The
629/// assignment must be one an attribute docstring may follow
630/// (module or class level, or `self.<attr>` at the top of `__init__`).
631///
632/// A block is decided once, at its last `#:` line, which walks back
633/// over the block to credit it: `credit(first_row, last_row)` per line.
634/// The grammar places a comment that precedes a body's first statement
635/// outside that body, as a child of the class or function, so the
636/// statement after it is the body block's first statement.
637pub fn python_sphinx_doc_comment<'a>(
638 comment: &Node<'a>,
639 code: &[u8],
640 ancestors: Ancestors<'a, '_>,
641 mut credit: impl FnMut(usize, usize),
642) {
643 if !is_sphinx_doc_comment(comment, code) {
644 return;
645 }
646 let documents = match ancestors.siblings_before(comment).next() {
647 // The same-line form: `x = 1 #: doc`.
648 Some(statement) if statement.end_row() >= comment.start_row() => {
649 body_attributes(ancestors.iter(comment), code)
650 .is_some_and(|attributes| attributes.documented_by(&statement, code))
651 }
652 _ => ends_block_above_assignment(comment, code, ancestors),
653 };
654 if documents {
655 credit_block(comment, code, ancestors, &mut credit);
656 }
657}
658
659/// Whether `comment` is the last line of a `#:` block that sits directly
660/// above an assignment an attribute docstring may follow. A block whose
661/// next line is another `#:` is decided there instead.
662fn ends_block_above_assignment(comment: &Node, code: &[u8], ancestors: Ancestors<'_, '_>) -> bool {
663 let Some(next) = ancestors.siblings_after(comment).next() else {
664 return false;
665 };
666 let below = comment.end_row().saturating_add(1);
667 if next.start_row() != below || is_sphinx_doc_comment(&next, code) {
668 return false;
669 }
670 if !python_is_block(&next) {
671 return body_attributes(ancestors.iter(comment), code)
672 .is_some_and(|attributes| attributes.documented_by(&next, code));
673 }
674 // The comment precedes a body's first statement, so the grammar made
675 // it the class's or function's child, ahead of the body block.
676 let mut up = ancestors.iter(comment);
677 let Some((owner, _)) = up.next() else {
678 return false;
679 };
680 next.children()
681 .find(Node::is_named)
682 .filter(|first| first.start_row() == below)
683 .is_some_and(|first| {
684 owner_attributes(&owner, up, code)
685 .is_some_and(|attributes| attributes.documented_by(&first, code))
686 })
687}
688
689/// Credits `comment` and the `#:` lines directly above it, each the
690/// first token of its row: one backward pass over one sibling iterator.
691fn credit_block(
692 comment: &Node,
693 code: &[u8],
694 ancestors: Ancestors<'_, '_>,
695 credit: &mut impl FnMut(usize, usize),
696) {
697 credit(comment.start_row(), comment.end_row());
698 let mut member = *comment;
699 let mut before = ancestors.siblings_before(comment).peekable();
700 while let Some(above) = before.next() {
701 let leads_its_row = before
702 .peek()
703 .is_none_or(|prev| prev.end_row() < above.start_row());
704 if !(is_sphinx_doc_comment(&above, code)
705 && above.end_row().saturating_add(1) == member.start_row()
706 && leads_its_row)
707 {
708 break;
709 }
710 credit(above.start_row(), above.end_row());
711 member = above;
712 }
713}
714
715/// A comment whose text opens with Sphinx's doc-comment marker, `#:`.
716fn is_sphinx_doc_comment(node: &Node, code: &[u8]) -> bool {
717 node.kind_id() == Python::Comment && node_bytes(node, code).starts_with(b"#:")
718}
719
720/// The destructuring wrappers an assignment target nests its elements
721/// in: `pattern_list` / `expression_list`, and `tuple_pattern` /
722/// `list_pattern`, which each carry two aliased kind ids — the hidden
723/// supertype (`TuplePattern` / `ListPattern`, never emitted) and the
724/// live node the grammar produces for `(a, b) = …` / `[a, b] = …`
725/// (`TuplePattern2` / `ListPattern2`). Matching only the supertype alias
726/// silently dropped every parenthesised / bracketed unpacking target,
727/// so both are listed per the hidden-alias discipline (#419).
728pub const PYTHON_TARGET_PATTERN_KINDS: &[u16] = &[
729 Python::PatternList as u16,
730 Python::ExpressionList as u16,
731 Python::TuplePattern as u16,
732 Python::TuplePattern2 as u16,
733 Python::ListPattern as u16,
734 Python::ListPattern2 as u16,
735];
736
737/// Conventional receiver names that denote the enclosing object inside
738/// a method body: `self` for instance methods, `cls` for classmethods.
739/// Matched against the receiver bytes rather than by resolving the
740/// enclosing function's first parameter (#412): a non-conventionally
741/// named first parameter is rare enough that under-counting it is
742/// preferable to the over-count of treating every foreign-object write
743/// as an attribute, which the structural-only proxy did.
744const PYTHON_SELF_RECEIVERS: [&[u8]; 2] = [b"self", b"cls"];
745
746/// The attribute name of a `self.<attr>` / `cls.<attr>` `attribute`
747/// node, or `None` when the receiver is not a self / cls alias — the
748/// bytes the `Member` row's gate and the attribute count both read.
749///
750/// The node's first child is the receiver:
751/// self.x → receiver is Identifier "self" → counts
752/// db.x → receiver is Identifier "db" → foreign, skip
753/// self.f.g → receiver is itself an Attribute → skip
754/// The last named child is the attribute identifier. Only a direct
755/// `self.<name>` names an attribute of the class; `self.f.g` writes `g`
756/// on `self.f`, so the nested-attribute receiver is rejected. Borrows
757/// from `code` so the slice is the canonical dedup key.
758#[must_use]
759pub fn python_self_attribute_name<'a>(attr: &Node<'a>, code: &'a [u8]) -> Option<&'a [u8]> {
760 let receiver = python_self_receiver(attr, code)?;
761 // The trailing identifier is the attribute name; the degenerate
762 // single-identifier case has none distinct from the receiver.
763 let id = attr
764 .children()
765 .filter(|c| c.kind_id() == Python::Identifier)
766 .last()
767 .filter(|id| id.start_byte() != receiver.start_byte())?;
768 code.get(id.start_byte()..id.end_byte())
769}
770
771/// The receiver of `attr` when it is a `self` / `cls` identifier: the
772/// first child, read by bytes. The `Member` row's gate asks only this —
773/// the attribute's name is the consumer's dedup key, read once there —
774/// so a row read costs no child scan.
775fn python_self_receiver<'a>(attr: &Node<'a>, code: &[u8]) -> Option<Node<'a>> {
776 let receiver = attr
777 .child(0)
778 .filter(|receiver| receiver.kind_id() == Python::Identifier)?;
779 let receiver_bytes = code.get(receiver.start_byte()..receiver.end_byte())?;
780 PYTHON_SELF_RECEIVERS
781 .contains(&receiver_bytes)
782 .then_some(receiver)
783}
784
785/// Whether an `attribute` node is a `self.x` / `cls.x` being *bound* —
786/// a target of the enclosing `assignment` (`self.x = …`, `self.a,
787/// self.b = …`, `self.a, (self.b, c) = …`), as opposed to a read or an
788/// operand. The target is the assignment's first child; a destructuring
789/// target wraps its elements in [`PYTHON_TARGET_PATTERN_KINDS`], climbed
790/// here until the assignment is met. `ancestors` is the node's chain.
791///
792/// The climb is `O(depth)` in the pattern wrappers above the node, so
793/// asking it of every element of a nested target is quadratic in the
794/// nesting. No production walk asks it: the attribute count walks down
795/// from the assignment's target through those wrappers only, so the
796/// climb would answer yes for every element it reaches, and it reads
797/// the row's kind table and [`python_self_attribute_name`] instead
798/// (#1867). The row tests and the derived suite ask it with real chains.
799#[must_use]
800pub(crate) fn python_is_bound_self_attribute<'a>(
801 node: &Node<'a>,
802 code: &[u8],
803 ancestors: Ancestors<'a, '_>,
804) -> bool {
805 if python_self_receiver(node, code).is_none() {
806 return false;
807 }
808 let mut below = *node;
809 for (ancestor, _) in ancestors.iter(node) {
810 let kind = ancestor.kind_id();
811 if kind == Python::Assignment as u16 {
812 return ancestor
813 .child(0)
814 .is_some_and(|first| first.id() == below.id());
815 }
816 if !PYTHON_TARGET_PATTERN_KINDS.contains(&kind) {
817 return false;
818 }
819 below = ancestor;
820 }
821 false
822}
823
824#[cfg(test)]
825mod tests {
826 use super::*;
827
828 /// `python_lambdas_below_statement_boundary` answers the climb's
829 /// count for every node, folded through a walk's cache or climbed
830 /// without one (#1767).
831 ///
832 /// The fixture puts a boolean operator under each of 300 nested
833 /// lambdas, past the fold's `u8` saturation at 255, so the deepest
834 /// operators can only answer right through the exact fallback; a
835 /// parenthesised `yield` (an `expression_list`) resets the count
836 /// mid-nest, and an `if` and a `for` sit above it all.
837 #[cfg(feature = "python")]
838 #[test]
839 fn lambdas_below_statement_boundary_match_the_climb_past_saturation() {
840 use crate::langs::PythonCode;
841 use crate::node::FoldCache;
842 use crate::test_support::for_each_node_with_chain;
843 let depth = 300;
844 let source = format!(
845 "def g():\n if c:\n for i in r:\n x = {}a and b{}\n y = lambda: (yield (lambda: a or b), 1)\n",
846 "lambda: (a and ".repeat(depth),
847 ")".repeat(depth)
848 );
849 let cache = FoldCache::default();
850 let (mut deepest, mut reset) = (0_usize, false);
851 for_each_node_with_chain::<PythonCode>(source.as_bytes(), |node, chain| {
852 if node.kind_id() != Python::BooleanOperator {
853 return;
854 }
855 let climbed = node.count_specific_ancestors::<PythonCode>(
856 Ancestors::known(chain),
857 python_is_lambda,
858 is_statement_boundary,
859 );
860 let folded = python_lambdas_below_statement_boundary(
861 node,
862 Ancestors::known(chain).with_folds(&cache),
863 );
864 let chained = python_lambdas_below_statement_boundary(node, Ancestors::known(chain));
865 assert_eq!(
866 (folded, chained),
867 (climbed, climbed),
868 "(folded, chained) must both be the climb's count"
869 );
870 deepest = deepest.max(climbed);
871 // `a or b` under the `yield`'s `expression_list`: one lambda
872 // below the boundary, though two enclose it.
873 reset |= node.start_row() == 4 && climbed == 1;
874 });
875 assert_eq!(deepest, depth, "the fixture must reach past saturation");
876 assert!(reset, "the `expression_list` must reset the count");
877 }
878
879 /// Every `parenthesized_expression`, `(` and `)` of `source`, each
880 /// asked through a memoised walk and through its chain alone, which
881 /// takes the climb. A chainless caller climbs the same way, by
882 /// `Node::parent`, at a cost that would make this test quadratic.
883 #[cfg(feature = "python")]
884 fn bare_string_parenthesis_answers(source: &str) -> Vec<[bool; 2]> {
885 use crate::langs::PythonCode;
886 use crate::node::{FoldCache, Tree};
887 let tree = Tree::new::<PythonCode>(source.as_bytes());
888 let cache = FoldCache::default();
889 let mut answers = Vec::new();
890 // Pre-order with the chain the metric walk keeps, so the fold's
891 // per-depth slots are reused as they are there.
892 let mut stack = vec![(tree.get_root(), 0_usize)];
893 let mut chain: Vec<Node> = Vec::new();
894 while let Some((node, depth)) = stack.pop() {
895 chain.truncate(depth);
896 if matches!(
897 node.kind_id().into(),
898 Python::ParenthesizedExpression | Python::LPAREN | Python::RPAREN
899 ) {
900 answers.push([
901 python_is_bare_string_parenthesis(
902 &node,
903 Ancestors::known(&chain).with_folds(&cache),
904 ),
905 python_is_bare_string_parenthesis(&node, Ancestors::known(&chain)),
906 ]);
907 }
908 chain.push(node);
909 let children: Vec<_> = node.children().collect();
910 stack.extend(children.into_iter().rev().map(|child| (child, depth + 1)));
911 }
912 answers
913 }
914
915 /// The memoised fold answers as the climb it replaced does (#1610),
916 /// on both sides of CPython's cap: a bare string under 200
917 /// parentheses keeps all of them as its own, one under 201 none — a
918 /// discarded f-string is a bare string too, if no docstring — and a
919 /// parenthesized value, a tuple and an assignment none.
920 /// The climb's answers are the oracle, so a fold that lost its reset
921 /// (`climb == 0`) fails here before any metric. The saturation point
922 /// and the window's upper edge are not observable: on every tree the
923 /// grammar produces, a parenthesis chain either ends at its string
924 /// within the cap or climbs past it, and both sides agree on each. A
925 /// perturbation of either edge fails nothing (measured), so the
926 /// arithmetic in [`bare_string_climb`] is argued in its doc, not
927 /// pinned here.
928 #[cfg(feature = "python")]
929 #[test]
930 fn memoised_climb_answers_as_the_climb_does() {
931 let nest = |depth: usize, inner: &str| {
932 format!("{}{inner}{}", "(".repeat(depth), ")".repeat(depth))
933 };
934 let cases = [
935 (nest(199, "\"s\""), 199 * 3),
936 (nest(200, "\"s\""), 200 * 3),
937 (nest(201, "\"s\""), 0),
938 (
939 format!("def f():\n {}\n", nest(3, "\"\"\"d\"\"\"")),
940 3 * 3,
941 ),
942 ("( # c\n \"s\"\n)\n".to_owned(), 3),
943 ("(\"a\" \"b\")\n".to_owned(), 3),
944 (nest(3, "x"), 0),
945 ("(\"a\", \"b\")\n".to_owned(), 0),
946 (nest(3, "f\"x\""), 3 * 3),
947 (format!("x = {}\n", nest(1_000, "\"s\"")), 0),
948 (format!("{}\n(\"s\"\n", nest(2, "\"s\"")), 2 * 3),
949 // A `\` run and a comment before the string: both extras are
950 // named, and the value is the string past them (#1830).
951 // Measured 0 before the fix, every one of the four.
952 ("( \\\n\\\n# c\n\"\"\"doc\"\"\" )\n".to_owned(), 3),
953 ("( \\\n\\\n# c\n(\"\"\"doc\"\"\") )\n".to_owned(), 2 * 3),
954 ("( \\\n\\\n(\"\"\"doc\"\"\")\n)\n".to_owned(), 2 * 3),
955 ("( \\\n\\\n# c\n\"\"\"doc\"\"\" \\\n\\\n)\n".to_owned(), 3),
956 // The same prefix before a name and before a tuple: no bare
957 // string, so the extras are skipped to a value that is none.
958 ("( \\\n\\\n# c\nx )\n".to_owned(), 0),
959 ("( \\\n\\\n# c\n\"a\", \"b\" )\n".to_owned(), 0),
960 ];
961 for (source, documenting) in cases {
962 let answers = bare_string_parenthesis_answers(&source);
963 assert!(!answers.is_empty(), "{source:.40}");
964 for [memoised, climbed] in &answers {
965 assert_eq!(memoised, climbed, "{source:.40}");
966 }
967 let found = answers.iter().filter(|[memoised, ..]| *memoised).count();
968 assert_eq!(found, documenting, "{source:.40}");
969 }
970 }
971
972 /// `is_class_init` finds a method's class within three ancestors
973 /// because the kinds it skips do not nest: the one pair the grammar
974 /// allows is a `decorated_definition` in a `block` (#1868). A
975 /// grammar bump that puts a block directly in a block, or a
976 /// decorated definition in another, makes that climb as long as the
977 /// nest and must change this with it.
978 // test-lang-gates: hand-written(python) — reads the grammar crate's
979 // `NODE_TYPES`, which exists only under the `python` feature
980 #[cfg(feature = "python")]
981 #[test]
982 fn the_kinds_between_a_method_and_its_class_nest_two_deep_at_most() {
983 let nesting = crate::test_support::nesting_among(tree_sitter_python::NODE_TYPES, |kind| {
984 matches!(kind, "decorated_definition" | "block")
985 });
986 assert_eq!(
987 nesting,
988 [(
989 "block".to_owned(),
990 ["decorated_definition".to_owned()].into()
991 )]
992 .into()
993 );
994 }
995}