Skip to main content

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}