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`.
223fn unparenthesized_once<'a>(node: &Node<'a>, cursor: &mut Cursor<'a>) -> Option<Node<'a>> {
224    if node.kind_id() != Python::ParenthesizedExpression {
225        return None;
226    }
227    node.children_with(cursor)
228        .find(|child| child.is_named() && child.kind_id() != Python::Comment)
229}
230
231/// The string a bare string statement holds, past any parentheses.
232fn statement_string<'a>(statement: &Node<'a>) -> Option<Node<'a>> {
233    if !is_bare_statement(statement) {
234        return None;
235    }
236    statement.child(0).map(unparenthesized).filter(|value| {
237        matches!(
238            value.kind_id().into(),
239            Python::String | Python::ConcatenatedString
240        )
241    })
242}
243
244/// Whether `node` is a bare string statement's `string`: the statement's
245/// sole value itself, or one fragment of an implicitly concatenated
246/// literal (`"""doc""" "more"`) that is — CPython joins the fragments
247/// into one string, and so does the `concatenated_string` node.
248///
249/// The one definition of "a string whose value is discarded" for both
250/// walks that care: the Halstead getter drops its operands (#695) and
251/// the LOC walk bills its rows as comment rows (#415). Whether those rows
252/// are also *documentation* is narrower and positional — see
253/// [`python_documentation_string_run`] (#1597).
254#[inline]
255#[must_use]
256pub fn python_is_bare_string(node: &Node, ancestors: Ancestors<'_, '_>) -> bool {
257    let Some((parent, parent_ancestors)) = ancestors.iter(node).next() else {
258        return false;
259    };
260    if matches!(parent.kind_id().into(), Python::ConcatenatedString) {
261        return python_is_bare_statement_value(&parent, parent_ancestors);
262    }
263    python_is_bare_statement_value(node, ancestors)
264}
265
266/// Whether `value` — a `string` or `concatenated_string` — is a
267/// documentation string by position: a `str` literal that is the sole
268/// value of a bare statement in a docstring, additional-docstring or
269/// attribute-docstring place, per `documentation_run`, which holds the
270/// rules. One fragment of a concatenation answers `false` on its own:
271/// its nearest non-parenthesis ancestor is the `concatenated_string`,
272/// not a statement, so the scan finds no body to read — the mechanism,
273/// not a second test, which is why no `parent` check precedes it. The
274/// `Docstring` row's gate (`roles/python.rs`, #1699): one backward scan
275/// over the statement's siblings, which the run helper shares by asking
276/// this of a run's final member only. A caller asking it of every
277/// member of a run pays one scan per member.
278#[must_use]
279pub(crate) fn python_is_documentation_string(
280    value: &Node,
281    code: &[u8],
282    ancestors: Ancestors<'_, '_>,
283) -> bool {
284    documentation_run(value, code, ancestors).is_some()
285}
286
287// Each backward scan `documentation_run` makes. The scan is one per run
288// — the helper asks at the run's final member only —
289// and `one_scan_per_run` pins it by count, since no probe
290// can tell one scan per run from two (#1699).
291crate::observation::counter!(docstring_runs_scanned);
292
293/// The first statement of the documentation-string run that the bare
294/// string statement holding `value` belongs to, or `None` when that
295/// statement is not documentation — or holds more than one value, a
296/// discarded tuple being no docstring. `value` is a `string` or
297/// `concatenated_string`, per [`python_is_bare_statement_value`], and the
298/// statement documents where Python tooling reads documentation (#1597):
299///
300/// - **a docstring** (PEP 257): the first statement of a module, class or
301///   function body — the string Python stores as `__doc__`, and the one
302///   `help()`, `inspect` and pydoc read. Only a `str` literal is stored:
303///   an f-string, a template string or a bytes literal is no docstring;
304/// - **an additional docstring** (PEP 257): a string statement directly
305///   after another docstring, including an attribute or additional docstring;
306/// - **an attribute docstring** (PEP 257 and 258, read by Sphinx autodoc):
307///   a string statement directly after an assignment to a name at module
308///   or class level, or to an attribute of `self` at the top level of a
309///   class's `__init__`.
310///
311/// "Directly after" skips comments, which are not statements. Any other
312/// bare string — a triple-quoted string wrapping commented-out code in
313/// the middle of a function, a module docstring written after the
314/// imports — is still a comment row (#415) but is not documentation, so
315/// the maintainability index charges it as it charges a `#` comment.
316/// `code` is read for a literal's prefix and for `__init__`'s names.
317///
318/// One backward scan answers both: the string statements before it,
319/// skipping comments, are the run, and the first other statement ends
320/// the run and is the one an attribute docstring is documented by.
321fn documentation_run<'a>(
322    value: &Node<'a>,
323    code: &[u8],
324    ancestors: Ancestors<'a, '_>,
325) -> Option<Node<'a>> {
326    // The literal test is the cheap one; `body_attributes` may read the
327    // enclosing `__init__`'s name and parameters.
328    if !is_str_literal(value, code) {
329        return None;
330    }
331    let ((statement, statement_ancestors), up) = enclosing_statement(value, ancestors)?;
332    // A string of a discarded tuple (`"a", "b"`) is no docstring: the
333    // statement holds two values. Checked here, the one place, so the
334    // row and the run helper cannot differ on it.
335    if !is_bare_statement(&statement) {
336        return None;
337    }
338    docstring_runs_scanned::record();
339    let attributes = body_attributes(up, code)?;
340    let mut first = statement;
341    for sibling in statement_ancestors
342        .siblings_before(&statement)
343        .filter(|sibling| sibling.is_named() && sibling.kind_id() != Python::Comment)
344    {
345        if !is_string_statement(&sibling, code) {
346            return attributes.documented_by(&sibling, code).then_some(first);
347        }
348        first = sibling;
349    }
350    Some(first)
351}
352
353/// Credits a consecutive run of documentation strings at its last string.
354/// Comments between statements do not break the run. Deciding once keeps
355/// additional-docstring recognition linear in the number of statements.
356pub fn python_documentation_string_run(
357    value: &Node,
358    code: &[u8],
359    ancestors: Ancestors<'_, '_>,
360    mut credit: impl FnMut(usize, usize),
361) {
362    let Some(((statement, outer), _)) = enclosing_statement(value, ancestors) else {
363        return;
364    };
365    if outer
366        .siblings_after(&statement)
367        .find(|sibling| sibling.is_named() && sibling.kind_id() != Python::Comment)
368        .is_some_and(|next| is_string_statement(&next, code))
369    {
370        return;
371    }
372    // The run's final member. `documentation_run` is the backward scan
373    // the `Docstring` row's gate reads (#1699) and the one this needs for
374    // the run's first member, so it runs once, here: the row's verdict
375    // is `first.is_some()` by construction, the gate being this call.
376    let Some(first) = documentation_run(value, code, ancestors) else {
377        return;
378    };
379    for member in std::iter::once(first)
380        .chain(outer.siblings_after(&first))
381        .take_while(|member| member.start_byte() <= statement.start_byte())
382        .filter(|member| is_string_statement(member, code))
383    {
384        credit_documentation_rows(member, &mut credit);
385    }
386}
387
388/// Credits the rows of a string statement's value and of the `(` and `)`
389/// around it, which are part of the docstring (#1610); a comment inside
390/// the parentheses stays a comment.
391fn credit_documentation_rows(statement: Node, credit: &mut impl FnMut(usize, usize)) {
392    let Some(mut value) = statement.child(0) else {
393        return;
394    };
395    let mut cursor = value.cursor();
396    for _ in 0..MAX_PARENTHESES {
397        let Some(inner) = unparenthesized_once(&value, &mut cursor) else {
398            break;
399        };
400        for paren in value
401            .children_with(&mut cursor)
402            .filter(|child| !child.is_named())
403        {
404            credit(paren.start_row(), paren.end_row());
405        }
406        value = inner;
407    }
408    credit(value.start_row(), value.end_row());
409}
410
411/// The assignments a body reads an attribute docstring after: PEP 258's
412/// rules for the top level of a module, a class or `__init__`, with the
413/// targets Sphinx's `VariableCommentPicker` accepts there. Sphinx also
414/// reads the suites of an `if`, `with`, loop or `try` at those levels;
415/// PEP 257 does not, and neither does this.
416enum Attributes<'code> {
417    /// A module or class body: an assignment to a name, or to a tuple of
418    /// names — not to a subscript or another object's attribute, which
419    /// declares nothing there.
420    Names,
421    /// The top level of a class's `__init__`: an assignment to an
422    /// attribute of its first parameter, whose name this holds (`self`),
423    /// alone or in a tuple of targets.
424    OfSelf(&'code [u8]),
425    /// Any other function body.
426    Nothing,
427}
428
429impl Attributes<'_> {
430    /// Whether `statement`, directly before a string statement, makes that
431    /// string an attribute docstring.
432    fn documented_by(&self, statement: &Node, code: &[u8]) -> bool {
433        // A `type X = …` alias (PEP 695) declares the name it binds, and
434        // Sphinx's `VariableCommentPicker` reads it like an assignment
435        // (`AssignmentLikeType` holds `ast.TypeAlias`): a docstring after
436        // it or a `#:` comment on or above it documents `X`. It never
437        // binds an attribute of `self`.
438        if statement.kind_id() == Python::TypeAliasStatement {
439            return matches!(self, Self::Names);
440        }
441        let Some(target) = assignment_target(statement) else {
442            return false;
443        };
444        match self {
445            Self::Names => binds(&target, |leaf| leaf.kind_id() == Python::Identifier),
446            Self::OfSelf(name) => binds(&target, |leaf| {
447                leaf.kind_id() == Python::Attribute
448                    && leaf.child_by_field_name("object").is_some_and(|object| {
449                        object.kind_id() == Python::Identifier && node_bytes(&object, code) == *name
450                    })
451            }),
452            Self::Nothing => false,
453        }
454    }
455}
456
457/// What a body makes of the assignments in it, from the ancestors above
458/// the statement: `None` when the body holds no documentation at all (an
459/// `if` or loop body).
460fn body_attributes<'code>(
461    mut up: AncestorIter<'_, '_>,
462    code: &'code [u8],
463) -> Option<Attributes<'code>> {
464    let (container, _) = up.next()?;
465    if container.kind_id() == Python::Module {
466        return Some(Attributes::Names);
467    }
468    let (owner, _) = up.next().filter(|_| python_is_block(&container))?;
469    owner_attributes(&owner, up, code)
470}
471
472/// What the body of `owner` — a class or function definition — makes of
473/// the assignments in it; `None` for any other owner. `up` continues
474/// from `owner`'s parent.
475fn owner_attributes<'code>(
476    owner: &Node,
477    up: AncestorIter<'_, '_>,
478    code: &'code [u8],
479) -> Option<Attributes<'code>> {
480    if owner.kind_id() == Python::ClassDefinition {
481        Some(Attributes::Names)
482    } else if owner.kind_id() == Python::FunctionDefinition {
483        let receiver = is_class_init(owner, up, code)
484            .then(|| first_parameter_name(owner, code))
485            .flatten();
486        Some(receiver.map_or(Attributes::Nothing, Attributes::OfSelf))
487    } else {
488        None
489    }
490}
491
492/// Whether `function` is a class's `__init__`, the one method PEP 257
493/// reads attribute docstrings in: named so, with the class the first
494/// ancestor past its decorators and the class body's block. `up`
495/// continues from `function`'s parent.
496fn is_class_init(function: &Node, up: AncestorIter<'_, '_>, code: &[u8]) -> bool {
497    function
498        .child_by_field_name("name")
499        .is_some_and(|name| node_bytes(&name, code) == b"__init__")
500        && up
501            .map(|(node, _)| node)
502            .find(|node| node.kind_id() != Python::DecoratedDefinition && !python_is_block(node))
503            .is_some_and(|class| class.kind_id() == Python::ClassDefinition)
504}
505
506/// The name of `function`'s first parameter, typed or not. A comment is a
507/// named extra, and formatters put one right after the `(` of an exploded
508/// signature (`def __init__(  # noqa: PLR0913`), so it is skipped.
509fn first_parameter_name<'code>(function: &Node, code: &'code [u8]) -> Option<&'code [u8]> {
510    let first = function
511        .child_by_field_name("parameters")?
512        .children()
513        .find(|child| child.is_named() && child.kind_id() != Python::Comment)?;
514    let name = if first.kind_id() == Python::TypedParameter {
515        first.children().find(Node::is_named)?
516    } else {
517        first
518    };
519    (name.kind_id() == Python::Identifier).then(|| node_bytes(&name, code))
520}
521
522/// Whether `value` is a literal Python stores as a docstring: a `str`, not
523/// an f-string, a template string or bytes — a prefix holding `f`, `t` or
524/// `b` in either case makes the statement none, and one fragment of an
525/// implicit concatenation is enough.
526fn is_str_literal(value: &Node, code: &[u8]) -> bool {
527    let is_str = |literal: &Node| {
528        !node_bytes(literal, code)
529            .iter()
530            .take_while(|byte| byte.is_ascii_alphabetic())
531            .any(|byte| matches!(byte.to_ascii_lowercase(), b'f' | b't' | b'b'))
532    };
533    if value.kind_id() == Python::ConcatenatedString {
534        value
535            .children()
536            .filter(|fragment| fragment.kind_id() == Python::String)
537            .all(|fragment| is_str(&fragment))
538    } else {
539        is_str(value)
540    }
541}
542
543/// An `expression_statement` holding one value and nothing else: the
544/// discarded-value shape a docstring takes.
545fn is_bare_statement(statement: &Node) -> bool {
546    statement.kind_id() == Python::ExpressionStatement && statement.child_count() == 1
547}
548
549/// A bare statement whose value is a `str` literal: a docstring, when it
550/// opens its body.
551fn is_string_statement(statement: &Node, code: &[u8]) -> bool {
552    statement_string(statement).is_some_and(|value| is_str_literal(&value, code))
553}
554
555/// Whether an assignment target binds what Sphinx records an attribute
556/// docstring for, as its `get_lvar_names` reads a target: `leaf` decides a
557/// single one — a name, a subscript or an attribute — and a tuple, list or
558/// starred target binds when any element does. Walked with an explicit
559/// stack, so a target nested thousands of brackets deep cannot exhaust the
560/// thread's stack (#1597).
561fn binds(target: &Node, leaf: impl Fn(&Node) -> bool) -> bool {
562    let mut pending = vec![*target];
563    while let Some(node) = pending.pop() {
564        match node.kind_id().into() {
565            Python::Identifier | Python::Subscript | Python::Attribute => {
566                if leaf(&node) {
567                    return true;
568                }
569            }
570            _ => pending.extend(node.children().filter(Node::is_named)),
571        }
572    }
573    false
574}
575
576/// The target of the assignment `statement` holds, annotated or not.
577fn assignment_target<'a>(statement: &Node<'a>) -> Option<Node<'a>> {
578    (statement.kind_id() == Python::ExpressionStatement)
579        .then(|| statement.child(0))
580        .flatten()
581        .filter(|value| value.kind_id() == Python::Assignment)
582        .and_then(|assignment| assignment.child_by_field_name("left"))
583}
584
585/// Credits the rows of a Sphinx doc comment that `comment` completes
586/// (#1597). Sphinx autodoc reads a comment starting `#:` as an
587/// attribute's documentation when it sits on the line of an assignment,
588/// after the code, or on the consecutive lines directly above one —
589/// every one of them `#:`; a plain `#` line breaks the block. The
590/// assignment must be one an attribute docstring may follow
591/// (module or class level, or `self.<attr>` at the top of `__init__`).
592///
593/// A block is decided once, at its last `#:` line, which walks back
594/// over the block to credit it: `credit(first_row, last_row)` per line.
595/// The grammar places a comment that precedes a body's first statement
596/// outside that body, as a child of the class or function, so the
597/// statement after it is the body block's first statement.
598pub fn python_sphinx_doc_comment<'a>(
599    comment: &Node<'a>,
600    code: &[u8],
601    ancestors: Ancestors<'a, '_>,
602    mut credit: impl FnMut(usize, usize),
603) {
604    if !is_sphinx_doc_comment(comment, code) {
605        return;
606    }
607    let documents = match ancestors.siblings_before(comment).next() {
608        // The same-line form: `x = 1  #: doc`.
609        Some(statement) if statement.end_row() >= comment.start_row() => {
610            body_attributes(ancestors.iter(comment), code)
611                .is_some_and(|attributes| attributes.documented_by(&statement, code))
612        }
613        _ => ends_block_above_assignment(comment, code, ancestors),
614    };
615    if documents {
616        credit_block(comment, code, ancestors, &mut credit);
617    }
618}
619
620/// Whether `comment` is the last line of a `#:` block that sits directly
621/// above an assignment an attribute docstring may follow. A block whose
622/// next line is another `#:` is decided there instead.
623fn ends_block_above_assignment(comment: &Node, code: &[u8], ancestors: Ancestors<'_, '_>) -> bool {
624    let Some(next) = ancestors.siblings_after(comment).next() else {
625        return false;
626    };
627    let below = comment.end_row().saturating_add(1);
628    if next.start_row() != below || is_sphinx_doc_comment(&next, code) {
629        return false;
630    }
631    if !python_is_block(&next) {
632        return body_attributes(ancestors.iter(comment), code)
633            .is_some_and(|attributes| attributes.documented_by(&next, code));
634    }
635    // The comment precedes a body's first statement, so the grammar made
636    // it the class's or function's child, ahead of the body block.
637    let mut up = ancestors.iter(comment);
638    let Some((owner, _)) = up.next() else {
639        return false;
640    };
641    next.children()
642        .find(Node::is_named)
643        .filter(|first| first.start_row() == below)
644        .is_some_and(|first| {
645            owner_attributes(&owner, up, code)
646                .is_some_and(|attributes| attributes.documented_by(&first, code))
647        })
648}
649
650/// Credits `comment` and the `#:` lines directly above it, each the
651/// first token of its row: one backward pass over one sibling iterator.
652fn credit_block(
653    comment: &Node,
654    code: &[u8],
655    ancestors: Ancestors<'_, '_>,
656    credit: &mut impl FnMut(usize, usize),
657) {
658    credit(comment.start_row(), comment.end_row());
659    let mut member = *comment;
660    let mut before = ancestors.siblings_before(comment).peekable();
661    while let Some(above) = before.next() {
662        let leads_its_row = before
663            .peek()
664            .is_none_or(|prev| prev.end_row() < above.start_row());
665        if !(is_sphinx_doc_comment(&above, code)
666            && above.end_row().saturating_add(1) == member.start_row()
667            && leads_its_row)
668        {
669            break;
670        }
671        credit(above.start_row(), above.end_row());
672        member = above;
673    }
674}
675
676/// A comment whose text opens with Sphinx's doc-comment marker, `#:`.
677fn is_sphinx_doc_comment(node: &Node, code: &[u8]) -> bool {
678    node.kind_id() == Python::Comment && node_bytes(node, code).starts_with(b"#:")
679}
680
681/// The destructuring wrappers an assignment target nests its elements
682/// in: `pattern_list` / `expression_list`, and `tuple_pattern` /
683/// `list_pattern`, which each carry two aliased kind ids — the hidden
684/// supertype (`TuplePattern` / `ListPattern`, never emitted) and the
685/// live node the grammar produces for `(a, b) = …` / `[a, b] = …`
686/// (`TuplePattern2` / `ListPattern2`). Matching only the supertype alias
687/// silently dropped every parenthesised / bracketed unpacking target,
688/// so both are listed per the hidden-alias discipline (#419).
689pub const PYTHON_TARGET_PATTERN_KINDS: &[u16] = &[
690    Python::PatternList as u16,
691    Python::ExpressionList as u16,
692    Python::TuplePattern as u16,
693    Python::TuplePattern2 as u16,
694    Python::ListPattern as u16,
695    Python::ListPattern2 as u16,
696];
697
698/// Conventional receiver names that denote the enclosing object inside
699/// a method body: `self` for instance methods, `cls` for classmethods.
700/// Matched against the receiver bytes rather than by resolving the
701/// enclosing function's first parameter (#412): a non-conventionally
702/// named first parameter is rare enough that under-counting it is
703/// preferable to the over-count of treating every foreign-object write
704/// as an attribute, which the structural-only proxy did.
705const PYTHON_SELF_RECEIVERS: [&[u8]; 2] = [b"self", b"cls"];
706
707/// The attribute name of a `self.<attr>` / `cls.<attr>` `attribute`
708/// node, or `None` when the receiver is not a self / cls alias — the
709/// bytes the `Member` row's gate and the attribute count both read.
710///
711/// The node's first child is the receiver:
712///   self.x       → receiver is Identifier "self"      → counts
713///   db.x         → receiver is Identifier "db"        → foreign, skip
714///   self.f.g     → receiver is itself an Attribute    → skip
715/// The last named child is the attribute identifier. Only a direct
716/// `self.<name>` names an attribute of the class; `self.f.g` writes `g`
717/// on `self.f`, so the nested-attribute receiver is rejected. Borrows
718/// from `code` so the slice is the canonical dedup key.
719#[must_use]
720pub fn python_self_attribute_name<'a>(attr: &Node<'a>, code: &'a [u8]) -> Option<&'a [u8]> {
721    let receiver = python_self_receiver(attr, code)?;
722    // The trailing identifier is the attribute name; the degenerate
723    // single-identifier case has none distinct from the receiver.
724    let id = attr
725        .children()
726        .filter(|c| c.kind_id() == Python::Identifier)
727        .last()
728        .filter(|id| id.start_byte() != receiver.start_byte())?;
729    code.get(id.start_byte()..id.end_byte())
730}
731
732/// The receiver of `attr` when it is a `self` / `cls` identifier: the
733/// first child, read by bytes. The `Member` row's gate asks only this —
734/// the attribute's name is the consumer's dedup key, read once there —
735/// so a row read costs no child scan.
736fn python_self_receiver<'a>(attr: &Node<'a>, code: &[u8]) -> Option<Node<'a>> {
737    let receiver = attr
738        .child(0)
739        .filter(|receiver| receiver.kind_id() == Python::Identifier)?;
740    let receiver_bytes = code.get(receiver.start_byte()..receiver.end_byte())?;
741    PYTHON_SELF_RECEIVERS
742        .contains(&receiver_bytes)
743        .then_some(receiver)
744}
745
746/// Whether an `attribute` node is a `self.x` / `cls.x` being *bound* —
747/// a target of the enclosing `assignment` (`self.x = …`, `self.a,
748/// self.b = …`, `self.a, (self.b, c) = …`), as opposed to a read or an
749/// operand. The target is the assignment's first child; a destructuring
750/// target wraps its elements in [`PYTHON_TARGET_PATTERN_KINDS`], climbed
751/// here until the assignment is met. `ancestors` is the node's chain.
752#[must_use]
753pub(crate) fn python_is_bound_self_attribute<'a>(
754    node: &Node<'a>,
755    code: &[u8],
756    ancestors: Ancestors<'a, '_>,
757) -> bool {
758    if python_self_receiver(node, code).is_none() {
759        return false;
760    }
761    let mut below = *node;
762    for (ancestor, _) in ancestors.iter(node) {
763        let kind = ancestor.kind_id();
764        if kind == Python::Assignment as u16 {
765            return ancestor
766                .child(0)
767                .is_some_and(|first| first.id() == below.id());
768        }
769        if !PYTHON_TARGET_PATTERN_KINDS.contains(&kind) {
770            return false;
771        }
772        below = ancestor;
773    }
774    false
775}
776
777#[cfg(test)]
778mod tests {
779    use super::*;
780
781    /// `python_lambdas_below_statement_boundary` answers the climb's
782    /// count for every node, folded through a walk's cache or climbed
783    /// without one (#1767).
784    ///
785    /// The fixture puts a boolean operator under each of 300 nested
786    /// lambdas, past the fold's `u8` saturation at 255, so the deepest
787    /// operators can only answer right through the exact fallback; a
788    /// parenthesised `yield` (an `expression_list`) resets the count
789    /// mid-nest, and an `if` and a `for` sit above it all.
790    #[cfg(feature = "python")]
791    #[test]
792    fn lambdas_below_statement_boundary_match_the_climb_past_saturation() {
793        use crate::langs::PythonCode;
794        use crate::node::FoldCache;
795        use crate::test_support::for_each_node_with_chain;
796        let depth = 300;
797        let source = format!(
798            "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",
799            "lambda: (a and ".repeat(depth),
800            ")".repeat(depth)
801        );
802        let cache = FoldCache::default();
803        let (mut deepest, mut reset) = (0_usize, false);
804        for_each_node_with_chain::<PythonCode>(source.as_bytes(), |node, chain| {
805            if node.kind_id() != Python::BooleanOperator {
806                return;
807            }
808            let climbed = node.count_specific_ancestors::<PythonCode>(
809                Ancestors::known(chain),
810                python_is_lambda,
811                is_statement_boundary,
812            );
813            let folded = python_lambdas_below_statement_boundary(
814                node,
815                Ancestors::known(chain).with_folds(&cache),
816            );
817            let chained = python_lambdas_below_statement_boundary(node, Ancestors::known(chain));
818            assert_eq!(
819                (folded, chained),
820                (climbed, climbed),
821                "(folded, chained) must both be the climb's count"
822            );
823            deepest = deepest.max(climbed);
824            // `a or b` under the `yield`'s `expression_list`: one lambda
825            // below the boundary, though two enclose it.
826            reset |= node.start_row() == 4 && climbed == 1;
827        });
828        assert_eq!(deepest, depth, "the fixture must reach past saturation");
829        assert!(reset, "the `expression_list` must reset the count");
830    }
831
832    /// Every `parenthesized_expression`, `(` and `)` of `source`, each
833    /// asked through a memoised walk and through its chain alone, which
834    /// takes the climb. A chainless caller climbs the same way, by
835    /// `Node::parent`, at a cost that would make this test quadratic.
836    #[cfg(feature = "python")]
837    fn bare_string_parenthesis_answers(source: &str) -> Vec<[bool; 2]> {
838        use crate::langs::PythonCode;
839        use crate::node::{FoldCache, Tree};
840        let tree = Tree::new::<PythonCode>(source.as_bytes());
841        let cache = FoldCache::default();
842        let mut answers = Vec::new();
843        // Pre-order with the chain the metric walk keeps, so the fold's
844        // per-depth slots are reused as they are there.
845        let mut stack = vec![(tree.get_root(), 0_usize)];
846        let mut chain: Vec<Node> = Vec::new();
847        while let Some((node, depth)) = stack.pop() {
848            chain.truncate(depth);
849            if matches!(
850                node.kind_id().into(),
851                Python::ParenthesizedExpression | Python::LPAREN | Python::RPAREN
852            ) {
853                answers.push([
854                    python_is_bare_string_parenthesis(
855                        &node,
856                        Ancestors::known(&chain).with_folds(&cache),
857                    ),
858                    python_is_bare_string_parenthesis(&node, Ancestors::known(&chain)),
859                ]);
860            }
861            chain.push(node);
862            let children: Vec<_> = node.children().collect();
863            stack.extend(children.into_iter().rev().map(|child| (child, depth + 1)));
864        }
865        answers
866    }
867
868    /// The memoised fold answers as the climb it replaced does (#1610),
869    /// on both sides of CPython's cap: a bare string under 200
870    /// parentheses keeps all of them as its own, one under 201 none — a
871    /// discarded f-string is a bare string too, if no docstring — and a
872    /// parenthesized value, a tuple and an assignment none.
873    /// The climb's answers are the oracle, so a fold that lost its reset
874    /// (`climb == 0`) fails here before any metric. The saturation point
875    /// and the window's upper edge are not observable: on every tree the
876    /// grammar produces, a parenthesis chain either ends at its string
877    /// within the cap or climbs past it, and both sides agree on each. A
878    /// perturbation of either edge fails nothing (measured), so the
879    /// arithmetic in [`bare_string_climb`] is argued in its doc, not
880    /// pinned here.
881    #[cfg(feature = "python")]
882    #[test]
883    fn memoised_climb_answers_as_the_climb_does() {
884        let nest = |depth: usize, inner: &str| {
885            format!("{}{inner}{}", "(".repeat(depth), ")".repeat(depth))
886        };
887        let cases = [
888            (nest(199, "\"s\""), 199 * 3),
889            (nest(200, "\"s\""), 200 * 3),
890            (nest(201, "\"s\""), 0),
891            (
892                format!("def f():\n    {}\n", nest(3, "\"\"\"d\"\"\"")),
893                3 * 3,
894            ),
895            ("(  # c\n    \"s\"\n)\n".to_owned(), 3),
896            ("(\"a\" \"b\")\n".to_owned(), 3),
897            (nest(3, "x"), 0),
898            ("(\"a\", \"b\")\n".to_owned(), 0),
899            (nest(3, "f\"x\""), 3 * 3),
900            (format!("x = {}\n", nest(1_000, "\"s\"")), 0),
901            (format!("{}\n(\"s\"\n", nest(2, "\"s\"")), 2 * 3),
902        ];
903        for (source, documenting) in cases {
904            let answers = bare_string_parenthesis_answers(&source);
905            assert!(!answers.is_empty(), "{source:.40}");
906            for [memoised, climbed] in &answers {
907                assert_eq!(memoised, climbed, "{source:.40}");
908            }
909            let found = answers.iter().filter(|[memoised, ..]| *memoised).count();
910            assert_eq!(found, documenting, "{source:.40}");
911        }
912    }
913}