Quadratic formatting time for chains of subscripts (7s for one 160-subscript line; attribute/call chains stay linear)

[LuShadowX]

Describe the bug

A single line consisting of a chain of subscripts takes quadratic time to format. 160 subscripts on one line takes ~7 s; 300 takes ~23 s. The equivalent chain of attributes or calls, same length, takes ~0.02–0.07 s.

The cause is that a run of subscript trailers has no delimiter for delimiter_split to use, so the line is taken apart one bracket at a time by recursive right-hand splits, and each level rebuilds lines holding all the remaining leaves.

To Reproduce

# gen.py
n = 160
print("x = a" + "".join(f"[{i}]" for i in range(n)))

$ python gen.py > file.py
$ time black file.py

Measured with black.format_str on main (c7801d9e2), default mode:

n	a[0][1]…	a["k0"]["k1"]…	a.b0.b1…	a.m0().m1()…	a.b0[0].b1[1]…
40	0.033 s	0.188 s	0.007 s	0.015 s	0.021 s
80	1.142 s	0.993 s	0.013 s	0.032 s	0.044 s
160	7.098 s	4.213 s	0.024 s	0.068 s	0.079 s

Only consecutive subscripts are affected — interleaving an attribute (a.b0[0].b1[1]…) brings it back to linear.

Expected behavior

Roughly linear, like every other trailer chain of the same length.

Why it is the split search, not the parser

With --line-length 100000, so the line never needs splitting, n=160 drops from 7.098 s to 0.020 s.

Where the time goes

Instrumented call counts for n=60:

shape	right_hand_split	_first_right_hand_split	bracket_split_build_line	delimiter_split
a[0][1]…	734	780	2340	0
a.m0().m1()…	2	2	6	2
a.b0.b1…	4	6	6	2

Attribute and call chains carry DOT_PRIORITY delimiters, so delimiter_split takes the whole chain apart in one pass. A pure subscript chain has no delimiter at all, so rhs recurses: each level peels one […] off the tail and calls bracket_split_build_line three times, each of which appends every remaining leaf to a fresh Line (Line.append → BracketTracker.mark). That is O(n) levels × O(n) leaves.

cProfile at n=100 (7.3 s total, 12.8 M calls) agrees:

   ncalls  tottime  cumtime  function
   491702    1.261    2.189  brackets.py:71(mark)
   587522    1.062    3.680  lines.py:59(Line.append)
     7860    0.615    5.739  linegen.py:1294(bracket_split_build_line)
     2620    0.438    0.737  brackets.py:394(get_leaves_inside_matching_brackets)
     2620    0.189    6.150  linegen.py:981(_first_right_hand_split)

Line.append calls grow 47.9 K → 587.5 K → 2.35 M for n = 50 → 100 → 200.

Not the same as #3627

#3627 is long nested dicts. This is flat subscript chaining, it reproduces from a one-line generator, and the attribute/call contrast localises it to the missing delimiter. They may share the recursive-RHS cost, but this one has a much smaller repro.

Environment

• Black main at c7801d9e2, source install, macOS, CPython 3.13.6.
• Times are black.format_str(src, mode=black.Mode()), single run each, no cache involved.

I have not proposed a patch: making rhs stop rebuilding whole lines per level, or giving consecutive subscript trailers a delimiter priority so delimiter_split handles them, both look like they could move the stable style, and I would rather hear which direction you want before touching it.

[DresdenGman]

Thanks for the detailed reproduction and profiling. The distinction from #3627 and the attribute/call comparison make the quadratic split path very clear. Before preparing a patch, is there a maintainer preference between (1) preserving the existing split behavior while avoiding repeated RHS line reconstruction, and (2) adding a subscript-trailer delimiter so delimiter_split can handle a consecutive chain? I would keep the change narrowly scoped and add targeted correctness plus performance regression coverage.

[JelleZijlstra]

I'd prefer maintaining existing formatting; otherwise we would have to put the change in the preview style.