]> git.madduck.net Git - etc/vim.git/blob - src/black/__init__.py

madduck's git repository

Every one of the projects in this repository is available at the canonical URL git://git.madduck.net/madduck/pub/<projectpath> — see each project's metadata for the exact URL.

All patches and comments are welcome. Please squash your changes to logical commits before using git-format-patch and git-send-email to patches@git.madduck.net. If you'd read over the Git project's submission guidelines and adhered to them, I'd be especially grateful.

SSH access, as well as push access can be individually arranged.

If you use my repositories frequently, consider adding the following snippet to ~/.gitconfig and using the third clone URL listed for each project:

[url "git://git.madduck.net/madduck/"]
  insteadOf = madduck:

a1d16d9bdeb222f9d5d2a811c52f3671323cfe6e
[etc/vim.git] / src / black / __init__.py
1 import ast
2 import asyncio
3 from abc import ABC, abstractmethod
4 from collections import defaultdict
5 from concurrent.futures import Executor, ThreadPoolExecutor, ProcessPoolExecutor
6 from contextlib import contextmanager
7 from datetime import datetime
8 from enum import Enum
9 from functools import lru_cache, partial, wraps
10 import io
11 import itertools
12 import logging
13 from multiprocessing import Manager, freeze_support
14 import os
15 from pathlib import Path
16 import pickle
17 import regex as re
18 import signal
19 import sys
20 import tempfile
21 import tokenize
22 import traceback
23 from typing import (
24     Any,
25     Callable,
26     Collection,
27     Dict,
28     Generator,
29     Generic,
30     Iterable,
31     Iterator,
32     List,
33     Optional,
34     Pattern,
35     Sequence,
36     Set,
37     Sized,
38     Tuple,
39     Type,
40     TypeVar,
41     Union,
42     cast,
43     TYPE_CHECKING,
44 )
45 from mypy_extensions import mypyc_attr
46
47 from appdirs import user_cache_dir
48 from dataclasses import dataclass, field, replace
49 import click
50 import toml
51 from typed_ast import ast3, ast27
52 from pathspec import PathSpec
53
54 # lib2to3 fork
55 from blib2to3.pytree import Node, Leaf, type_repr
56 from blib2to3 import pygram, pytree
57 from blib2to3.pgen2 import driver, token
58 from blib2to3.pgen2.grammar import Grammar
59 from blib2to3.pgen2.parse import ParseError
60
61 from _black_version import version as __version__
62
63 if sys.version_info < (3, 8):
64     from typing_extensions import Final
65 else:
66     from typing import Final
67
68 if TYPE_CHECKING:
69     import colorama  # noqa: F401
70
71 DEFAULT_LINE_LENGTH = 88
72 DEFAULT_EXCLUDES = r"/(\.direnv|\.eggs|\.git|\.hg|\.mypy_cache|\.nox|\.tox|\.venv|\.svn|_build|buck-out|build|dist)/"  # noqa: B950
73 DEFAULT_INCLUDES = r"\.pyi?$"
74 CACHE_DIR = Path(user_cache_dir("black", version=__version__))
75 STDIN_PLACEHOLDER = "__BLACK_STDIN_FILENAME__"
76
77 STRING_PREFIX_CHARS: Final = "furbFURB"  # All possible string prefix characters.
78
79
80 # types
81 FileContent = str
82 Encoding = str
83 NewLine = str
84 Depth = int
85 NodeType = int
86 ParserState = int
87 LeafID = int
88 StringID = int
89 Priority = int
90 Index = int
91 LN = Union[Leaf, Node]
92 Transformer = Callable[["Line", Collection["Feature"]], Iterator["Line"]]
93 Timestamp = float
94 FileSize = int
95 CacheInfo = Tuple[Timestamp, FileSize]
96 Cache = Dict[str, CacheInfo]
97 out = partial(click.secho, bold=True, err=True)
98 err = partial(click.secho, fg="red", err=True)
99
100 pygram.initialize(CACHE_DIR)
101 syms = pygram.python_symbols
102
103
104 class NothingChanged(UserWarning):
105     """Raised when reformatted code is the same as source."""
106
107
108 class CannotTransform(Exception):
109     """Base class for errors raised by Transformers."""
110
111
112 class CannotSplit(CannotTransform):
113     """A readable split that fits the allotted line length is impossible."""
114
115
116 class InvalidInput(ValueError):
117     """Raised when input source code fails all parse attempts."""
118
119
120 class BracketMatchError(KeyError):
121     """Raised when an opening bracket is unable to be matched to a closing bracket."""
122
123
124 T = TypeVar("T")
125 E = TypeVar("E", bound=Exception)
126
127
128 class Ok(Generic[T]):
129     def __init__(self, value: T) -> None:
130         self._value = value
131
132     def ok(self) -> T:
133         return self._value
134
135
136 class Err(Generic[E]):
137     def __init__(self, e: E) -> None:
138         self._e = e
139
140     def err(self) -> E:
141         return self._e
142
143
144 # The 'Result' return type is used to implement an error-handling model heavily
145 # influenced by that used by the Rust programming language
146 # (see https://doc.rust-lang.org/book/ch09-00-error-handling.html).
147 Result = Union[Ok[T], Err[E]]
148 TResult = Result[T, CannotTransform]  # (T)ransform Result
149 TMatchResult = TResult[Index]
150
151
152 class WriteBack(Enum):
153     NO = 0
154     YES = 1
155     DIFF = 2
156     CHECK = 3
157     COLOR_DIFF = 4
158
159     @classmethod
160     def from_configuration(
161         cls, *, check: bool, diff: bool, color: bool = False
162     ) -> "WriteBack":
163         if check and not diff:
164             return cls.CHECK
165
166         if diff and color:
167             return cls.COLOR_DIFF
168
169         return cls.DIFF if diff else cls.YES
170
171
172 class Changed(Enum):
173     NO = 0
174     CACHED = 1
175     YES = 2
176
177
178 class TargetVersion(Enum):
179     PY27 = 2
180     PY33 = 3
181     PY34 = 4
182     PY35 = 5
183     PY36 = 6
184     PY37 = 7
185     PY38 = 8
186     PY39 = 9
187
188     def is_python2(self) -> bool:
189         return self is TargetVersion.PY27
190
191
192 class Feature(Enum):
193     # All string literals are unicode
194     UNICODE_LITERALS = 1
195     F_STRINGS = 2
196     NUMERIC_UNDERSCORES = 3
197     TRAILING_COMMA_IN_CALL = 4
198     TRAILING_COMMA_IN_DEF = 5
199     # The following two feature-flags are mutually exclusive, and exactly one should be
200     # set for every version of python.
201     ASYNC_IDENTIFIERS = 6
202     ASYNC_KEYWORDS = 7
203     ASSIGNMENT_EXPRESSIONS = 8
204     POS_ONLY_ARGUMENTS = 9
205     RELAXED_DECORATORS = 10
206     FORCE_OPTIONAL_PARENTHESES = 50
207
208
209 VERSION_TO_FEATURES: Dict[TargetVersion, Set[Feature]] = {
210     TargetVersion.PY27: {Feature.ASYNC_IDENTIFIERS},
211     TargetVersion.PY33: {Feature.UNICODE_LITERALS, Feature.ASYNC_IDENTIFIERS},
212     TargetVersion.PY34: {Feature.UNICODE_LITERALS, Feature.ASYNC_IDENTIFIERS},
213     TargetVersion.PY35: {
214         Feature.UNICODE_LITERALS,
215         Feature.TRAILING_COMMA_IN_CALL,
216         Feature.ASYNC_IDENTIFIERS,
217     },
218     TargetVersion.PY36: {
219         Feature.UNICODE_LITERALS,
220         Feature.F_STRINGS,
221         Feature.NUMERIC_UNDERSCORES,
222         Feature.TRAILING_COMMA_IN_CALL,
223         Feature.TRAILING_COMMA_IN_DEF,
224         Feature.ASYNC_IDENTIFIERS,
225     },
226     TargetVersion.PY37: {
227         Feature.UNICODE_LITERALS,
228         Feature.F_STRINGS,
229         Feature.NUMERIC_UNDERSCORES,
230         Feature.TRAILING_COMMA_IN_CALL,
231         Feature.TRAILING_COMMA_IN_DEF,
232         Feature.ASYNC_KEYWORDS,
233     },
234     TargetVersion.PY38: {
235         Feature.UNICODE_LITERALS,
236         Feature.F_STRINGS,
237         Feature.NUMERIC_UNDERSCORES,
238         Feature.TRAILING_COMMA_IN_CALL,
239         Feature.TRAILING_COMMA_IN_DEF,
240         Feature.ASYNC_KEYWORDS,
241         Feature.ASSIGNMENT_EXPRESSIONS,
242         Feature.POS_ONLY_ARGUMENTS,
243     },
244     TargetVersion.PY39: {
245         Feature.UNICODE_LITERALS,
246         Feature.F_STRINGS,
247         Feature.NUMERIC_UNDERSCORES,
248         Feature.TRAILING_COMMA_IN_CALL,
249         Feature.TRAILING_COMMA_IN_DEF,
250         Feature.ASYNC_KEYWORDS,
251         Feature.ASSIGNMENT_EXPRESSIONS,
252         Feature.RELAXED_DECORATORS,
253         Feature.POS_ONLY_ARGUMENTS,
254     },
255 }
256
257
258 @dataclass
259 class Mode:
260     target_versions: Set[TargetVersion] = field(default_factory=set)
261     line_length: int = DEFAULT_LINE_LENGTH
262     string_normalization: bool = True
263     magic_trailing_comma: bool = True
264     experimental_string_processing: bool = False
265     is_pyi: bool = False
266
267     def get_cache_key(self) -> str:
268         if self.target_versions:
269             version_str = ",".join(
270                 str(version.value)
271                 for version in sorted(self.target_versions, key=lambda v: v.value)
272             )
273         else:
274             version_str = "-"
275         parts = [
276             version_str,
277             str(self.line_length),
278             str(int(self.string_normalization)),
279             str(int(self.is_pyi)),
280         ]
281         return ".".join(parts)
282
283
284 # Legacy name, left for integrations.
285 FileMode = Mode
286
287
288 def supports_feature(target_versions: Set[TargetVersion], feature: Feature) -> bool:
289     return all(feature in VERSION_TO_FEATURES[version] for version in target_versions)
290
291
292 def find_pyproject_toml(path_search_start: Iterable[str]) -> Optional[str]:
293     """Find the absolute filepath to a pyproject.toml if it exists"""
294     path_project_root = find_project_root(path_search_start)
295     path_pyproject_toml = path_project_root / "pyproject.toml"
296     return str(path_pyproject_toml) if path_pyproject_toml.is_file() else None
297
298
299 def parse_pyproject_toml(path_config: str) -> Dict[str, Any]:
300     """Parse a pyproject toml file, pulling out relevant parts for Black
301
302     If parsing fails, will raise a toml.TomlDecodeError
303     """
304     pyproject_toml = toml.load(path_config)
305     config = pyproject_toml.get("tool", {}).get("black", {})
306     return {k.replace("--", "").replace("-", "_"): v for k, v in config.items()}
307
308
309 def read_pyproject_toml(
310     ctx: click.Context, param: click.Parameter, value: Optional[str]
311 ) -> Optional[str]:
312     """Inject Black configuration from "pyproject.toml" into defaults in `ctx`.
313
314     Returns the path to a successfully found and read configuration file, None
315     otherwise.
316     """
317     if not value:
318         value = find_pyproject_toml(ctx.params.get("src", ()))
319         if value is None:
320             return None
321
322     try:
323         config = parse_pyproject_toml(value)
324     except (toml.TomlDecodeError, OSError) as e:
325         raise click.FileError(
326             filename=value, hint=f"Error reading configuration file: {e}"
327         )
328
329     if not config:
330         return None
331     else:
332         # Sanitize the values to be Click friendly. For more information please see:
333         # https://github.com/psf/black/issues/1458
334         # https://github.com/pallets/click/issues/1567
335         config = {
336             k: str(v) if not isinstance(v, (list, dict)) else v
337             for k, v in config.items()
338         }
339
340     target_version = config.get("target_version")
341     if target_version is not None and not isinstance(target_version, list):
342         raise click.BadOptionUsage(
343             "target-version", "Config key target-version must be a list"
344         )
345
346     default_map: Dict[str, Any] = {}
347     if ctx.default_map:
348         default_map.update(ctx.default_map)
349     default_map.update(config)
350
351     ctx.default_map = default_map
352     return value
353
354
355 def target_version_option_callback(
356     c: click.Context, p: Union[click.Option, click.Parameter], v: Tuple[str, ...]
357 ) -> List[TargetVersion]:
358     """Compute the target versions from a --target-version flag.
359
360     This is its own function because mypy couldn't infer the type correctly
361     when it was a lambda, causing mypyc trouble.
362     """
363     return [TargetVersion[val.upper()] for val in v]
364
365
366 @click.command(context_settings=dict(help_option_names=["-h", "--help"]))
367 @click.option("-c", "--code", type=str, help="Format the code passed in as a string.")
368 @click.option(
369     "-l",
370     "--line-length",
371     type=int,
372     default=DEFAULT_LINE_LENGTH,
373     help="How many characters per line to allow.",
374     show_default=True,
375 )
376 @click.option(
377     "-t",
378     "--target-version",
379     type=click.Choice([v.name.lower() for v in TargetVersion]),
380     callback=target_version_option_callback,
381     multiple=True,
382     help=(
383         "Python versions that should be supported by Black's output. [default: per-file"
384         " auto-detection]"
385     ),
386 )
387 @click.option(
388     "--pyi",
389     is_flag=True,
390     help=(
391         "Format all input files like typing stubs regardless of file extension (useful"
392         " when piping source on standard input)."
393     ),
394 )
395 @click.option(
396     "-S",
397     "--skip-string-normalization",
398     is_flag=True,
399     help="Don't normalize string quotes or prefixes.",
400 )
401 @click.option(
402     "-C",
403     "--skip-magic-trailing-comma",
404     is_flag=True,
405     help="Don't use trailing commas as a reason to split lines.",
406 )
407 @click.option(
408     "--experimental-string-processing",
409     is_flag=True,
410     hidden=True,
411     help=(
412         "Experimental option that performs more normalization on string literals."
413         " Currently disabled because it leads to some crashes."
414     ),
415 )
416 @click.option(
417     "--check",
418     is_flag=True,
419     help=(
420         "Don't write the files back, just return the status.  Return code 0 means"
421         " nothing would change.  Return code 1 means some files would be reformatted."
422         " Return code 123 means there was an internal error."
423     ),
424 )
425 @click.option(
426     "--diff",
427     is_flag=True,
428     help="Don't write the files back, just output a diff for each file on stdout.",
429 )
430 @click.option(
431     "--color/--no-color",
432     is_flag=True,
433     help="Show colored diff. Only applies when `--diff` is given.",
434 )
435 @click.option(
436     "--fast/--safe",
437     is_flag=True,
438     help="If --fast given, skip temporary sanity checks. [default: --safe]",
439 )
440 @click.option(
441     "--include",
442     type=str,
443     default=DEFAULT_INCLUDES,
444     help=(
445         "A regular expression that matches files and directories that should be"
446         " included on recursive searches.  An empty value means all files are included"
447         " regardless of the name.  Use forward slashes for directories on all platforms"
448         " (Windows, too).  Exclusions are calculated first, inclusions later."
449     ),
450     show_default=True,
451 )
452 @click.option(
453     "--exclude",
454     type=str,
455     default=DEFAULT_EXCLUDES,
456     help=(
457         "A regular expression that matches files and directories that should be"
458         " excluded on recursive searches.  An empty value means no paths are excluded."
459         " Use forward slashes for directories on all platforms (Windows, too). "
460         " Exclusions are calculated first, inclusions later."
461     ),
462     show_default=True,
463 )
464 @click.option(
465     "--force-exclude",
466     type=str,
467     help=(
468         "Like --exclude, but files and directories matching this regex will be "
469         "excluded even when they are passed explicitly as arguments."
470     ),
471 )
472 @click.option(
473     "--stdin-filename",
474     type=str,
475     help=(
476         "The name of the file when passing it through stdin. Useful to make "
477         "sure Black will respect --force-exclude option on some "
478         "editors that rely on using stdin."
479     ),
480 )
481 @click.option(
482     "-q",
483     "--quiet",
484     is_flag=True,
485     help=(
486         "Don't emit non-error messages to stderr. Errors are still emitted; silence"
487         " those with 2>/dev/null."
488     ),
489 )
490 @click.option(
491     "-v",
492     "--verbose",
493     is_flag=True,
494     help=(
495         "Also emit messages to stderr about files that were not changed or were ignored"
496         " due to --exclude=."
497     ),
498 )
499 @click.version_option(version=__version__)
500 @click.argument(
501     "src",
502     nargs=-1,
503     type=click.Path(
504         exists=True, file_okay=True, dir_okay=True, readable=True, allow_dash=True
505     ),
506     is_eager=True,
507 )
508 @click.option(
509     "--config",
510     type=click.Path(
511         exists=True,
512         file_okay=True,
513         dir_okay=False,
514         readable=True,
515         allow_dash=False,
516         path_type=str,
517     ),
518     is_eager=True,
519     callback=read_pyproject_toml,
520     help="Read configuration from FILE path.",
521 )
522 @click.pass_context
523 def main(
524     ctx: click.Context,
525     code: Optional[str],
526     line_length: int,
527     target_version: List[TargetVersion],
528     check: bool,
529     diff: bool,
530     color: bool,
531     fast: bool,
532     pyi: bool,
533     skip_string_normalization: bool,
534     skip_magic_trailing_comma: bool,
535     experimental_string_processing: bool,
536     quiet: bool,
537     verbose: bool,
538     include: str,
539     exclude: str,
540     force_exclude: Optional[str],
541     stdin_filename: Optional[str],
542     src: Tuple[str, ...],
543     config: Optional[str],
544 ) -> None:
545     """The uncompromising code formatter."""
546     write_back = WriteBack.from_configuration(check=check, diff=diff, color=color)
547     if target_version:
548         versions = set(target_version)
549     else:
550         # We'll autodetect later.
551         versions = set()
552     mode = Mode(
553         target_versions=versions,
554         line_length=line_length,
555         is_pyi=pyi,
556         string_normalization=not skip_string_normalization,
557         magic_trailing_comma=not skip_magic_trailing_comma,
558         experimental_string_processing=experimental_string_processing,
559     )
560     if config and verbose:
561         out(f"Using configuration from {config}.", bold=False, fg="blue")
562     if code is not None:
563         print(format_str(code, mode=mode))
564         ctx.exit(0)
565     report = Report(check=check, diff=diff, quiet=quiet, verbose=verbose)
566     sources = get_sources(
567         ctx=ctx,
568         src=src,
569         quiet=quiet,
570         verbose=verbose,
571         include=include,
572         exclude=exclude,
573         force_exclude=force_exclude,
574         report=report,
575         stdin_filename=stdin_filename,
576     )
577
578     path_empty(
579         sources,
580         "No Python files are present to be formatted. Nothing to do 😴",
581         quiet,
582         verbose,
583         ctx,
584     )
585
586     if len(sources) == 1:
587         reformat_one(
588             src=sources.pop(),
589             fast=fast,
590             write_back=write_back,
591             mode=mode,
592             report=report,
593         )
594     else:
595         reformat_many(
596             sources=sources, fast=fast, write_back=write_back, mode=mode, report=report
597         )
598
599     if verbose or not quiet:
600         out("Oh no! 💥 💔 💥" if report.return_code else "All done! ✨ 🍰 ✨")
601         click.secho(str(report), err=True)
602     ctx.exit(report.return_code)
603
604
605 def get_sources(
606     *,
607     ctx: click.Context,
608     src: Tuple[str, ...],
609     quiet: bool,
610     verbose: bool,
611     include: str,
612     exclude: str,
613     force_exclude: Optional[str],
614     report: "Report",
615     stdin_filename: Optional[str],
616 ) -> Set[Path]:
617     """Compute the set of files to be formatted."""
618     try:
619         include_regex = re_compile_maybe_verbose(include)
620     except re.error:
621         err(f"Invalid regular expression for include given: {include!r}")
622         ctx.exit(2)
623     try:
624         exclude_regex = re_compile_maybe_verbose(exclude)
625     except re.error:
626         err(f"Invalid regular expression for exclude given: {exclude!r}")
627         ctx.exit(2)
628     try:
629         force_exclude_regex = (
630             re_compile_maybe_verbose(force_exclude) if force_exclude else None
631         )
632     except re.error:
633         err(f"Invalid regular expression for force_exclude given: {force_exclude!r}")
634         ctx.exit(2)
635
636     root = find_project_root(src)
637     sources: Set[Path] = set()
638     path_empty(src, "No Path provided. Nothing to do 😴", quiet, verbose, ctx)
639     gitignore = get_gitignore(root)
640
641     for s in src:
642         if s == "-" and stdin_filename:
643             p = Path(stdin_filename)
644             is_stdin = True
645         else:
646             p = Path(s)
647             is_stdin = False
648
649         if is_stdin or p.is_file():
650             normalized_path = normalize_path_maybe_ignore(p, root, report)
651             if normalized_path is None:
652                 continue
653
654             normalized_path = "/" + normalized_path
655             # Hard-exclude any files that matches the `--force-exclude` regex.
656             if force_exclude_regex:
657                 force_exclude_match = force_exclude_regex.search(normalized_path)
658             else:
659                 force_exclude_match = None
660             if force_exclude_match and force_exclude_match.group(0):
661                 report.path_ignored(p, "matches the --force-exclude regular expression")
662                 continue
663
664             if is_stdin:
665                 p = Path(f"{STDIN_PLACEHOLDER}{str(p)}")
666
667             sources.add(p)
668         elif p.is_dir():
669             sources.update(
670                 gen_python_files(
671                     p.iterdir(),
672                     root,
673                     include_regex,
674                     exclude_regex,
675                     force_exclude_regex,
676                     report,
677                     gitignore,
678                 )
679             )
680         elif s == "-":
681             sources.add(p)
682         else:
683             err(f"invalid path: {s}")
684     return sources
685
686
687 def path_empty(
688     src: Sized, msg: str, quiet: bool, verbose: bool, ctx: click.Context
689 ) -> None:
690     """
691     Exit if there is no `src` provided for formatting
692     """
693     if not src and (verbose or not quiet):
694         out(msg)
695         ctx.exit(0)
696
697
698 def reformat_one(
699     src: Path, fast: bool, write_back: WriteBack, mode: Mode, report: "Report"
700 ) -> None:
701     """Reformat a single file under `src` without spawning child processes.
702
703     `fast`, `write_back`, and `mode` options are passed to
704     :func:`format_file_in_place` or :func:`format_stdin_to_stdout`.
705     """
706     try:
707         changed = Changed.NO
708
709         if str(src) == "-":
710             is_stdin = True
711         elif str(src).startswith(STDIN_PLACEHOLDER):
712             is_stdin = True
713             # Use the original name again in case we want to print something
714             # to the user
715             src = Path(str(src)[len(STDIN_PLACEHOLDER) :])
716         else:
717             is_stdin = False
718
719         if is_stdin:
720             if format_stdin_to_stdout(fast=fast, write_back=write_back, mode=mode):
721                 changed = Changed.YES
722         else:
723             cache: Cache = {}
724             if write_back not in (WriteBack.DIFF, WriteBack.COLOR_DIFF):
725                 cache = read_cache(mode)
726                 res_src = src.resolve()
727                 res_src_s = str(res_src)
728                 if res_src_s in cache and cache[res_src_s] == get_cache_info(res_src):
729                     changed = Changed.CACHED
730             if changed is not Changed.CACHED and format_file_in_place(
731                 src, fast=fast, write_back=write_back, mode=mode
732             ):
733                 changed = Changed.YES
734             if (write_back is WriteBack.YES and changed is not Changed.CACHED) or (
735                 write_back is WriteBack.CHECK and changed is Changed.NO
736             ):
737                 write_cache(cache, [src], mode)
738         report.done(src, changed)
739     except Exception as exc:
740         if report.verbose:
741             traceback.print_exc()
742         report.failed(src, str(exc))
743
744
745 def reformat_many(
746     sources: Set[Path], fast: bool, write_back: WriteBack, mode: Mode, report: "Report"
747 ) -> None:
748     """Reformat multiple files using a ProcessPoolExecutor."""
749     executor: Executor
750     loop = asyncio.get_event_loop()
751     worker_count = os.cpu_count()
752     if sys.platform == "win32":
753         # Work around https://bugs.python.org/issue26903
754         worker_count = min(worker_count, 60)
755     try:
756         executor = ProcessPoolExecutor(max_workers=worker_count)
757     except (ImportError, OSError):
758         # we arrive here if the underlying system does not support multi-processing
759         # like in AWS Lambda or Termux, in which case we gracefully fallback to
760         # a ThreadPollExecutor with just a single worker (more workers would not do us
761         # any good due to the Global Interpreter Lock)
762         executor = ThreadPoolExecutor(max_workers=1)
763
764     try:
765         loop.run_until_complete(
766             schedule_formatting(
767                 sources=sources,
768                 fast=fast,
769                 write_back=write_back,
770                 mode=mode,
771                 report=report,
772                 loop=loop,
773                 executor=executor,
774             )
775         )
776     finally:
777         shutdown(loop)
778         if executor is not None:
779             executor.shutdown()
780
781
782 async def schedule_formatting(
783     sources: Set[Path],
784     fast: bool,
785     write_back: WriteBack,
786     mode: Mode,
787     report: "Report",
788     loop: asyncio.AbstractEventLoop,
789     executor: Executor,
790 ) -> None:
791     """Run formatting of `sources` in parallel using the provided `executor`.
792
793     (Use ProcessPoolExecutors for actual parallelism.)
794
795     `write_back`, `fast`, and `mode` options are passed to
796     :func:`format_file_in_place`.
797     """
798     cache: Cache = {}
799     if write_back not in (WriteBack.DIFF, WriteBack.COLOR_DIFF):
800         cache = read_cache(mode)
801         sources, cached = filter_cached(cache, sources)
802         for src in sorted(cached):
803             report.done(src, Changed.CACHED)
804     if not sources:
805         return
806
807     cancelled = []
808     sources_to_cache = []
809     lock = None
810     if write_back in (WriteBack.DIFF, WriteBack.COLOR_DIFF):
811         # For diff output, we need locks to ensure we don't interleave output
812         # from different processes.
813         manager = Manager()
814         lock = manager.Lock()
815     tasks = {
816         asyncio.ensure_future(
817             loop.run_in_executor(
818                 executor, format_file_in_place, src, fast, mode, write_back, lock
819             )
820         ): src
821         for src in sorted(sources)
822     }
823     pending: Iterable["asyncio.Future[bool]"] = tasks.keys()
824     try:
825         loop.add_signal_handler(signal.SIGINT, cancel, pending)
826         loop.add_signal_handler(signal.SIGTERM, cancel, pending)
827     except NotImplementedError:
828         # There are no good alternatives for these on Windows.
829         pass
830     while pending:
831         done, _ = await asyncio.wait(pending, return_when=asyncio.FIRST_COMPLETED)
832         for task in done:
833             src = tasks.pop(task)
834             if task.cancelled():
835                 cancelled.append(task)
836             elif task.exception():
837                 report.failed(src, str(task.exception()))
838             else:
839                 changed = Changed.YES if task.result() else Changed.NO
840                 # If the file was written back or was successfully checked as
841                 # well-formatted, store this information in the cache.
842                 if write_back is WriteBack.YES or (
843                     write_back is WriteBack.CHECK and changed is Changed.NO
844                 ):
845                     sources_to_cache.append(src)
846                 report.done(src, changed)
847     if cancelled:
848         await asyncio.gather(*cancelled, loop=loop, return_exceptions=True)
849     if sources_to_cache:
850         write_cache(cache, sources_to_cache, mode)
851
852
853 def format_file_in_place(
854     src: Path,
855     fast: bool,
856     mode: Mode,
857     write_back: WriteBack = WriteBack.NO,
858     lock: Any = None,  # multiprocessing.Manager().Lock() is some crazy proxy
859 ) -> bool:
860     """Format file under `src` path. Return True if changed.
861
862     If `write_back` is DIFF, write a diff to stdout. If it is YES, write reformatted
863     code to the file.
864     `mode` and `fast` options are passed to :func:`format_file_contents`.
865     """
866     if src.suffix == ".pyi":
867         mode = replace(mode, is_pyi=True)
868
869     then = datetime.utcfromtimestamp(src.stat().st_mtime)
870     with open(src, "rb") as buf:
871         src_contents, encoding, newline = decode_bytes(buf.read())
872     try:
873         dst_contents = format_file_contents(src_contents, fast=fast, mode=mode)
874     except NothingChanged:
875         return False
876
877     if write_back == WriteBack.YES:
878         with open(src, "w", encoding=encoding, newline=newline) as f:
879             f.write(dst_contents)
880     elif write_back in (WriteBack.DIFF, WriteBack.COLOR_DIFF):
881         now = datetime.utcnow()
882         src_name = f"{src}\t{then} +0000"
883         dst_name = f"{src}\t{now} +0000"
884         diff_contents = diff(src_contents, dst_contents, src_name, dst_name)
885
886         if write_back == WriteBack.COLOR_DIFF:
887             diff_contents = color_diff(diff_contents)
888
889         with lock or nullcontext():
890             f = io.TextIOWrapper(
891                 sys.stdout.buffer,
892                 encoding=encoding,
893                 newline=newline,
894                 write_through=True,
895             )
896             f = wrap_stream_for_windows(f)
897             f.write(diff_contents)
898             f.detach()
899
900     return True
901
902
903 def color_diff(contents: str) -> str:
904     """Inject the ANSI color codes to the diff."""
905     lines = contents.split("\n")
906     for i, line in enumerate(lines):
907         if line.startswith("+++") or line.startswith("---"):
908             line = "\033[1;37m" + line + "\033[0m"  # bold white, reset
909         elif line.startswith("@@"):
910             line = "\033[36m" + line + "\033[0m"  # cyan, reset
911         elif line.startswith("+"):
912             line = "\033[32m" + line + "\033[0m"  # green, reset
913         elif line.startswith("-"):
914             line = "\033[31m" + line + "\033[0m"  # red, reset
915         lines[i] = line
916     return "\n".join(lines)
917
918
919 def wrap_stream_for_windows(
920     f: io.TextIOWrapper,
921 ) -> Union[io.TextIOWrapper, "colorama.AnsiToWin32"]:
922     """
923     Wrap stream with colorama's wrap_stream so colors are shown on Windows.
924
925     If `colorama` is unavailable, the original stream is returned unmodified.
926     Otherwise, the `wrap_stream()` function determines whether the stream needs
927     to be wrapped for a Windows environment and will accordingly either return
928     an `AnsiToWin32` wrapper or the original stream.
929     """
930     try:
931         from colorama.initialise import wrap_stream
932     except ImportError:
933         return f
934     else:
935         # Set `strip=False` to avoid needing to modify test_express_diff_with_color.
936         return wrap_stream(f, convert=None, strip=False, autoreset=False, wrap=True)
937
938
939 def format_stdin_to_stdout(
940     fast: bool, *, write_back: WriteBack = WriteBack.NO, mode: Mode
941 ) -> bool:
942     """Format file on stdin. Return True if changed.
943
944     If `write_back` is YES, write reformatted code back to stdout. If it is DIFF,
945     write a diff to stdout. The `mode` argument is passed to
946     :func:`format_file_contents`.
947     """
948     then = datetime.utcnow()
949     src, encoding, newline = decode_bytes(sys.stdin.buffer.read())
950     dst = src
951     try:
952         dst = format_file_contents(src, fast=fast, mode=mode)
953         return True
954
955     except NothingChanged:
956         return False
957
958     finally:
959         f = io.TextIOWrapper(
960             sys.stdout.buffer, encoding=encoding, newline=newline, write_through=True
961         )
962         if write_back == WriteBack.YES:
963             f.write(dst)
964         elif write_back in (WriteBack.DIFF, WriteBack.COLOR_DIFF):
965             now = datetime.utcnow()
966             src_name = f"STDIN\t{then} +0000"
967             dst_name = f"STDOUT\t{now} +0000"
968             d = diff(src, dst, src_name, dst_name)
969             if write_back == WriteBack.COLOR_DIFF:
970                 d = color_diff(d)
971                 f = wrap_stream_for_windows(f)
972             f.write(d)
973         f.detach()
974
975
976 def format_file_contents(src_contents: str, *, fast: bool, mode: Mode) -> FileContent:
977     """Reformat contents of a file and return new contents.
978
979     If `fast` is False, additionally confirm that the reformatted code is
980     valid by calling :func:`assert_equivalent` and :func:`assert_stable` on it.
981     `mode` is passed to :func:`format_str`.
982     """
983     if not src_contents.strip():
984         raise NothingChanged
985
986     dst_contents = format_str(src_contents, mode=mode)
987     if src_contents == dst_contents:
988         raise NothingChanged
989
990     if not fast:
991         assert_equivalent(src_contents, dst_contents)
992         assert_stable(src_contents, dst_contents, mode=mode)
993     return dst_contents
994
995
996 def format_str(src_contents: str, *, mode: Mode) -> FileContent:
997     """Reformat a string and return new contents.
998
999     `mode` determines formatting options, such as how many characters per line are
1000     allowed.  Example:
1001
1002     >>> import black
1003     >>> print(black.format_str("def f(arg:str='')->None:...", mode=black.Mode()))
1004     def f(arg: str = "") -> None:
1005         ...
1006
1007     A more complex example:
1008
1009     >>> print(
1010     ...   black.format_str(
1011     ...     "def f(arg:str='')->None: hey",
1012     ...     mode=black.Mode(
1013     ...       target_versions={black.TargetVersion.PY36},
1014     ...       line_length=10,
1015     ...       string_normalization=False,
1016     ...       is_pyi=False,
1017     ...     ),
1018     ...   ),
1019     ... )
1020     def f(
1021         arg: str = '',
1022     ) -> None:
1023         hey
1024
1025     """
1026     src_node = lib2to3_parse(src_contents.lstrip(), mode.target_versions)
1027     dst_contents = []
1028     future_imports = get_future_imports(src_node)
1029     if mode.target_versions:
1030         versions = mode.target_versions
1031     else:
1032         versions = detect_target_versions(src_node)
1033     normalize_fmt_off(src_node)
1034     lines = LineGenerator(
1035         mode=mode,
1036         remove_u_prefix="unicode_literals" in future_imports
1037         or supports_feature(versions, Feature.UNICODE_LITERALS),
1038     )
1039     elt = EmptyLineTracker(is_pyi=mode.is_pyi)
1040     empty_line = Line(mode=mode)
1041     after = 0
1042     split_line_features = {
1043         feature
1044         for feature in {Feature.TRAILING_COMMA_IN_CALL, Feature.TRAILING_COMMA_IN_DEF}
1045         if supports_feature(versions, feature)
1046     }
1047     for current_line in lines.visit(src_node):
1048         dst_contents.append(str(empty_line) * after)
1049         before, after = elt.maybe_empty_lines(current_line)
1050         dst_contents.append(str(empty_line) * before)
1051         for line in transform_line(
1052             current_line, mode=mode, features=split_line_features
1053         ):
1054             dst_contents.append(str(line))
1055     return "".join(dst_contents)
1056
1057
1058 def decode_bytes(src: bytes) -> Tuple[FileContent, Encoding, NewLine]:
1059     """Return a tuple of (decoded_contents, encoding, newline).
1060
1061     `newline` is either CRLF or LF but `decoded_contents` is decoded with
1062     universal newlines (i.e. only contains LF).
1063     """
1064     srcbuf = io.BytesIO(src)
1065     encoding, lines = tokenize.detect_encoding(srcbuf.readline)
1066     if not lines:
1067         return "", encoding, "\n"
1068
1069     newline = "\r\n" if b"\r\n" == lines[0][-2:] else "\n"
1070     srcbuf.seek(0)
1071     with io.TextIOWrapper(srcbuf, encoding) as tiow:
1072         return tiow.read(), encoding, newline
1073
1074
1075 def get_grammars(target_versions: Set[TargetVersion]) -> List[Grammar]:
1076     if not target_versions:
1077         # No target_version specified, so try all grammars.
1078         return [
1079             # Python 3.7+
1080             pygram.python_grammar_no_print_statement_no_exec_statement_async_keywords,
1081             # Python 3.0-3.6
1082             pygram.python_grammar_no_print_statement_no_exec_statement,
1083             # Python 2.7 with future print_function import
1084             pygram.python_grammar_no_print_statement,
1085             # Python 2.7
1086             pygram.python_grammar,
1087         ]
1088
1089     if all(version.is_python2() for version in target_versions):
1090         # Python 2-only code, so try Python 2 grammars.
1091         return [
1092             # Python 2.7 with future print_function import
1093             pygram.python_grammar_no_print_statement,
1094             # Python 2.7
1095             pygram.python_grammar,
1096         ]
1097
1098     # Python 3-compatible code, so only try Python 3 grammar.
1099     grammars = []
1100     # If we have to parse both, try to parse async as a keyword first
1101     if not supports_feature(target_versions, Feature.ASYNC_IDENTIFIERS):
1102         # Python 3.7+
1103         grammars.append(
1104             pygram.python_grammar_no_print_statement_no_exec_statement_async_keywords
1105         )
1106     if not supports_feature(target_versions, Feature.ASYNC_KEYWORDS):
1107         # Python 3.0-3.6
1108         grammars.append(pygram.python_grammar_no_print_statement_no_exec_statement)
1109     # At least one of the above branches must have been taken, because every Python
1110     # version has exactly one of the two 'ASYNC_*' flags
1111     return grammars
1112
1113
1114 def lib2to3_parse(src_txt: str, target_versions: Iterable[TargetVersion] = ()) -> Node:
1115     """Given a string with source, return the lib2to3 Node."""
1116     if not src_txt.endswith("\n"):
1117         src_txt += "\n"
1118
1119     for grammar in get_grammars(set(target_versions)):
1120         drv = driver.Driver(grammar, pytree.convert)
1121         try:
1122             result = drv.parse_string(src_txt, True)
1123             break
1124
1125         except ParseError as pe:
1126             lineno, column = pe.context[1]
1127             lines = src_txt.splitlines()
1128             try:
1129                 faulty_line = lines[lineno - 1]
1130             except IndexError:
1131                 faulty_line = "<line number missing in source>"
1132             exc = InvalidInput(f"Cannot parse: {lineno}:{column}: {faulty_line}")
1133     else:
1134         raise exc from None
1135
1136     if isinstance(result, Leaf):
1137         result = Node(syms.file_input, [result])
1138     return result
1139
1140
1141 def lib2to3_unparse(node: Node) -> str:
1142     """Given a lib2to3 node, return its string representation."""
1143     code = str(node)
1144     return code
1145
1146
1147 class Visitor(Generic[T]):
1148     """Basic lib2to3 visitor that yields things of type `T` on `visit()`."""
1149
1150     def visit(self, node: LN) -> Iterator[T]:
1151         """Main method to visit `node` and its children.
1152
1153         It tries to find a `visit_*()` method for the given `node.type`, like
1154         `visit_simple_stmt` for Node objects or `visit_INDENT` for Leaf objects.
1155         If no dedicated `visit_*()` method is found, chooses `visit_default()`
1156         instead.
1157
1158         Then yields objects of type `T` from the selected visitor.
1159         """
1160         if node.type < 256:
1161             name = token.tok_name[node.type]
1162         else:
1163             name = str(type_repr(node.type))
1164         # We explicitly branch on whether a visitor exists (instead of
1165         # using self.visit_default as the default arg to getattr) in order
1166         # to save needing to create a bound method object and so mypyc can
1167         # generate a native call to visit_default.
1168         visitf = getattr(self, f"visit_{name}", None)
1169         if visitf:
1170             yield from visitf(node)
1171         else:
1172             yield from self.visit_default(node)
1173
1174     def visit_default(self, node: LN) -> Iterator[T]:
1175         """Default `visit_*()` implementation. Recurses to children of `node`."""
1176         if isinstance(node, Node):
1177             for child in node.children:
1178                 yield from self.visit(child)
1179
1180
1181 @dataclass
1182 class DebugVisitor(Visitor[T]):
1183     tree_depth: int = 0
1184
1185     def visit_default(self, node: LN) -> Iterator[T]:
1186         indent = " " * (2 * self.tree_depth)
1187         if isinstance(node, Node):
1188             _type = type_repr(node.type)
1189             out(f"{indent}{_type}", fg="yellow")
1190             self.tree_depth += 1
1191             for child in node.children:
1192                 yield from self.visit(child)
1193
1194             self.tree_depth -= 1
1195             out(f"{indent}/{_type}", fg="yellow", bold=False)
1196         else:
1197             _type = token.tok_name.get(node.type, str(node.type))
1198             out(f"{indent}{_type}", fg="blue", nl=False)
1199             if node.prefix:
1200                 # We don't have to handle prefixes for `Node` objects since
1201                 # that delegates to the first child anyway.
1202                 out(f" {node.prefix!r}", fg="green", bold=False, nl=False)
1203             out(f" {node.value!r}", fg="blue", bold=False)
1204
1205     @classmethod
1206     def show(cls, code: Union[str, Leaf, Node]) -> None:
1207         """Pretty-print the lib2to3 AST of a given string of `code`.
1208
1209         Convenience method for debugging.
1210         """
1211         v: DebugVisitor[None] = DebugVisitor()
1212         if isinstance(code, str):
1213             code = lib2to3_parse(code)
1214         list(v.visit(code))
1215
1216
1217 WHITESPACE: Final = {token.DEDENT, token.INDENT, token.NEWLINE}
1218 STATEMENT: Final = {
1219     syms.if_stmt,
1220     syms.while_stmt,
1221     syms.for_stmt,
1222     syms.try_stmt,
1223     syms.except_clause,
1224     syms.with_stmt,
1225     syms.funcdef,
1226     syms.classdef,
1227 }
1228 STANDALONE_COMMENT: Final = 153
1229 token.tok_name[STANDALONE_COMMENT] = "STANDALONE_COMMENT"
1230 LOGIC_OPERATORS: Final = {"and", "or"}
1231 COMPARATORS: Final = {
1232     token.LESS,
1233     token.GREATER,
1234     token.EQEQUAL,
1235     token.NOTEQUAL,
1236     token.LESSEQUAL,
1237     token.GREATEREQUAL,
1238 }
1239 MATH_OPERATORS: Final = {
1240     token.VBAR,
1241     token.CIRCUMFLEX,
1242     token.AMPER,
1243     token.LEFTSHIFT,
1244     token.RIGHTSHIFT,
1245     token.PLUS,
1246     token.MINUS,
1247     token.STAR,
1248     token.SLASH,
1249     token.DOUBLESLASH,
1250     token.PERCENT,
1251     token.AT,
1252     token.TILDE,
1253     token.DOUBLESTAR,
1254 }
1255 STARS: Final = {token.STAR, token.DOUBLESTAR}
1256 VARARGS_SPECIALS: Final = STARS | {token.SLASH}
1257 VARARGS_PARENTS: Final = {
1258     syms.arglist,
1259     syms.argument,  # double star in arglist
1260     syms.trailer,  # single argument to call
1261     syms.typedargslist,
1262     syms.varargslist,  # lambdas
1263 }
1264 UNPACKING_PARENTS: Final = {
1265     syms.atom,  # single element of a list or set literal
1266     syms.dictsetmaker,
1267     syms.listmaker,
1268     syms.testlist_gexp,
1269     syms.testlist_star_expr,
1270 }
1271 TEST_DESCENDANTS: Final = {
1272     syms.test,
1273     syms.lambdef,
1274     syms.or_test,
1275     syms.and_test,
1276     syms.not_test,
1277     syms.comparison,
1278     syms.star_expr,
1279     syms.expr,
1280     syms.xor_expr,
1281     syms.and_expr,
1282     syms.shift_expr,
1283     syms.arith_expr,
1284     syms.trailer,
1285     syms.term,
1286     syms.power,
1287 }
1288 ASSIGNMENTS: Final = {
1289     "=",
1290     "+=",
1291     "-=",
1292     "*=",
1293     "@=",
1294     "/=",
1295     "%=",
1296     "&=",
1297     "|=",
1298     "^=",
1299     "<<=",
1300     ">>=",
1301     "**=",
1302     "//=",
1303 }
1304 COMPREHENSION_PRIORITY: Final = 20
1305 COMMA_PRIORITY: Final = 18
1306 TERNARY_PRIORITY: Final = 16
1307 LOGIC_PRIORITY: Final = 14
1308 STRING_PRIORITY: Final = 12
1309 COMPARATOR_PRIORITY: Final = 10
1310 MATH_PRIORITIES: Final = {
1311     token.VBAR: 9,
1312     token.CIRCUMFLEX: 8,
1313     token.AMPER: 7,
1314     token.LEFTSHIFT: 6,
1315     token.RIGHTSHIFT: 6,
1316     token.PLUS: 5,
1317     token.MINUS: 5,
1318     token.STAR: 4,
1319     token.SLASH: 4,
1320     token.DOUBLESLASH: 4,
1321     token.PERCENT: 4,
1322     token.AT: 4,
1323     token.TILDE: 3,
1324     token.DOUBLESTAR: 2,
1325 }
1326 DOT_PRIORITY: Final = 1
1327
1328
1329 @dataclass
1330 class BracketTracker:
1331     """Keeps track of brackets on a line."""
1332
1333     depth: int = 0
1334     bracket_match: Dict[Tuple[Depth, NodeType], Leaf] = field(default_factory=dict)
1335     delimiters: Dict[LeafID, Priority] = field(default_factory=dict)
1336     previous: Optional[Leaf] = None
1337     _for_loop_depths: List[int] = field(default_factory=list)
1338     _lambda_argument_depths: List[int] = field(default_factory=list)
1339     invisible: List[Leaf] = field(default_factory=list)
1340
1341     def mark(self, leaf: Leaf) -> None:
1342         """Mark `leaf` with bracket-related metadata. Keep track of delimiters.
1343
1344         All leaves receive an int `bracket_depth` field that stores how deep
1345         within brackets a given leaf is. 0 means there are no enclosing brackets
1346         that started on this line.
1347
1348         If a leaf is itself a closing bracket, it receives an `opening_bracket`
1349         field that it forms a pair with. This is a one-directional link to
1350         avoid reference cycles.
1351
1352         If a leaf is a delimiter (a token on which Black can split the line if
1353         needed) and it's on depth 0, its `id()` is stored in the tracker's
1354         `delimiters` field.
1355         """
1356         if leaf.type == token.COMMENT:
1357             return
1358
1359         self.maybe_decrement_after_for_loop_variable(leaf)
1360         self.maybe_decrement_after_lambda_arguments(leaf)
1361         if leaf.type in CLOSING_BRACKETS:
1362             self.depth -= 1
1363             try:
1364                 opening_bracket = self.bracket_match.pop((self.depth, leaf.type))
1365             except KeyError as e:
1366                 raise BracketMatchError(
1367                     "Unable to match a closing bracket to the following opening"
1368                     f" bracket: {leaf}"
1369                 ) from e
1370             leaf.opening_bracket = opening_bracket
1371             if not leaf.value:
1372                 self.invisible.append(leaf)
1373         leaf.bracket_depth = self.depth
1374         if self.depth == 0:
1375             delim = is_split_before_delimiter(leaf, self.previous)
1376             if delim and self.previous is not None:
1377                 self.delimiters[id(self.previous)] = delim
1378             else:
1379                 delim = is_split_after_delimiter(leaf, self.previous)
1380                 if delim:
1381                     self.delimiters[id(leaf)] = delim
1382         if leaf.type in OPENING_BRACKETS:
1383             self.bracket_match[self.depth, BRACKET[leaf.type]] = leaf
1384             self.depth += 1
1385             if not leaf.value:
1386                 self.invisible.append(leaf)
1387         self.previous = leaf
1388         self.maybe_increment_lambda_arguments(leaf)
1389         self.maybe_increment_for_loop_variable(leaf)
1390
1391     def any_open_brackets(self) -> bool:
1392         """Return True if there is an yet unmatched open bracket on the line."""
1393         return bool(self.bracket_match)
1394
1395     def max_delimiter_priority(self, exclude: Iterable[LeafID] = ()) -> Priority:
1396         """Return the highest priority of a delimiter found on the line.
1397
1398         Values are consistent with what `is_split_*_delimiter()` return.
1399         Raises ValueError on no delimiters.
1400         """
1401         return max(v for k, v in self.delimiters.items() if k not in exclude)
1402
1403     def delimiter_count_with_priority(self, priority: Priority = 0) -> int:
1404         """Return the number of delimiters with the given `priority`.
1405
1406         If no `priority` is passed, defaults to max priority on the line.
1407         """
1408         if not self.delimiters:
1409             return 0
1410
1411         priority = priority or self.max_delimiter_priority()
1412         return sum(1 for p in self.delimiters.values() if p == priority)
1413
1414     def maybe_increment_for_loop_variable(self, leaf: Leaf) -> bool:
1415         """In a for loop, or comprehension, the variables are often unpacks.
1416
1417         To avoid splitting on the comma in this situation, increase the depth of
1418         tokens between `for` and `in`.
1419         """
1420         if leaf.type == token.NAME and leaf.value == "for":
1421             self.depth += 1
1422             self._for_loop_depths.append(self.depth)
1423             return True
1424
1425         return False
1426
1427     def maybe_decrement_after_for_loop_variable(self, leaf: Leaf) -> bool:
1428         """See `maybe_increment_for_loop_variable` above for explanation."""
1429         if (
1430             self._for_loop_depths
1431             and self._for_loop_depths[-1] == self.depth
1432             and leaf.type == token.NAME
1433             and leaf.value == "in"
1434         ):
1435             self.depth -= 1
1436             self._for_loop_depths.pop()
1437             return True
1438
1439         return False
1440
1441     def maybe_increment_lambda_arguments(self, leaf: Leaf) -> bool:
1442         """In a lambda expression, there might be more than one argument.
1443
1444         To avoid splitting on the comma in this situation, increase the depth of
1445         tokens between `lambda` and `:`.
1446         """
1447         if leaf.type == token.NAME and leaf.value == "lambda":
1448             self.depth += 1
1449             self._lambda_argument_depths.append(self.depth)
1450             return True
1451
1452         return False
1453
1454     def maybe_decrement_after_lambda_arguments(self, leaf: Leaf) -> bool:
1455         """See `maybe_increment_lambda_arguments` above for explanation."""
1456         if (
1457             self._lambda_argument_depths
1458             and self._lambda_argument_depths[-1] == self.depth
1459             and leaf.type == token.COLON
1460         ):
1461             self.depth -= 1
1462             self._lambda_argument_depths.pop()
1463             return True
1464
1465         return False
1466
1467     def get_open_lsqb(self) -> Optional[Leaf]:
1468         """Return the most recent opening square bracket (if any)."""
1469         return self.bracket_match.get((self.depth - 1, token.RSQB))
1470
1471
1472 @dataclass
1473 class Line:
1474     """Holds leaves and comments. Can be printed with `str(line)`."""
1475
1476     mode: Mode
1477     depth: int = 0
1478     leaves: List[Leaf] = field(default_factory=list)
1479     # keys ordered like `leaves`
1480     comments: Dict[LeafID, List[Leaf]] = field(default_factory=dict)
1481     bracket_tracker: BracketTracker = field(default_factory=BracketTracker)
1482     inside_brackets: bool = False
1483     should_split_rhs: bool = False
1484     magic_trailing_comma: Optional[Leaf] = None
1485
1486     def append(self, leaf: Leaf, preformatted: bool = False) -> None:
1487         """Add a new `leaf` to the end of the line.
1488
1489         Unless `preformatted` is True, the `leaf` will receive a new consistent
1490         whitespace prefix and metadata applied by :class:`BracketTracker`.
1491         Trailing commas are maybe removed, unpacked for loop variables are
1492         demoted from being delimiters.
1493
1494         Inline comments are put aside.
1495         """
1496         has_value = leaf.type in BRACKETS or bool(leaf.value.strip())
1497         if not has_value:
1498             return
1499
1500         if token.COLON == leaf.type and self.is_class_paren_empty:
1501             del self.leaves[-2:]
1502         if self.leaves and not preformatted:
1503             # Note: at this point leaf.prefix should be empty except for
1504             # imports, for which we only preserve newlines.
1505             leaf.prefix += whitespace(
1506                 leaf, complex_subscript=self.is_complex_subscript(leaf)
1507             )
1508         if self.inside_brackets or not preformatted:
1509             self.bracket_tracker.mark(leaf)
1510             if self.mode.magic_trailing_comma:
1511                 if self.has_magic_trailing_comma(leaf):
1512                     self.magic_trailing_comma = leaf
1513             elif self.has_magic_trailing_comma(leaf, ensure_removable=True):
1514                 self.remove_trailing_comma()
1515         if not self.append_comment(leaf):
1516             self.leaves.append(leaf)
1517
1518     def append_safe(self, leaf: Leaf, preformatted: bool = False) -> None:
1519         """Like :func:`append()` but disallow invalid standalone comment structure.
1520
1521         Raises ValueError when any `leaf` is appended after a standalone comment
1522         or when a standalone comment is not the first leaf on the line.
1523         """
1524         if self.bracket_tracker.depth == 0:
1525             if self.is_comment:
1526                 raise ValueError("cannot append to standalone comments")
1527
1528             if self.leaves and leaf.type == STANDALONE_COMMENT:
1529                 raise ValueError(
1530                     "cannot append standalone comments to a populated line"
1531                 )
1532
1533         self.append(leaf, preformatted=preformatted)
1534
1535     @property
1536     def is_comment(self) -> bool:
1537         """Is this line a standalone comment?"""
1538         return len(self.leaves) == 1 and self.leaves[0].type == STANDALONE_COMMENT
1539
1540     @property
1541     def is_decorator(self) -> bool:
1542         """Is this line a decorator?"""
1543         return bool(self) and self.leaves[0].type == token.AT
1544
1545     @property
1546     def is_import(self) -> bool:
1547         """Is this an import line?"""
1548         return bool(self) and is_import(self.leaves[0])
1549
1550     @property
1551     def is_class(self) -> bool:
1552         """Is this line a class definition?"""
1553         return (
1554             bool(self)
1555             and self.leaves[0].type == token.NAME
1556             and self.leaves[0].value == "class"
1557         )
1558
1559     @property
1560     def is_stub_class(self) -> bool:
1561         """Is this line a class definition with a body consisting only of "..."?"""
1562         return self.is_class and self.leaves[-3:] == [
1563             Leaf(token.DOT, ".") for _ in range(3)
1564         ]
1565
1566     @property
1567     def is_def(self) -> bool:
1568         """Is this a function definition? (Also returns True for async defs.)"""
1569         try:
1570             first_leaf = self.leaves[0]
1571         except IndexError:
1572             return False
1573
1574         try:
1575             second_leaf: Optional[Leaf] = self.leaves[1]
1576         except IndexError:
1577             second_leaf = None
1578         return (first_leaf.type == token.NAME and first_leaf.value == "def") or (
1579             first_leaf.type == token.ASYNC
1580             and second_leaf is not None
1581             and second_leaf.type == token.NAME
1582             and second_leaf.value == "def"
1583         )
1584
1585     @property
1586     def is_class_paren_empty(self) -> bool:
1587         """Is this a class with no base classes but using parentheses?
1588
1589         Those are unnecessary and should be removed.
1590         """
1591         return (
1592             bool(self)
1593             and len(self.leaves) == 4
1594             and self.is_class
1595             and self.leaves[2].type == token.LPAR
1596             and self.leaves[2].value == "("
1597             and self.leaves[3].type == token.RPAR
1598             and self.leaves[3].value == ")"
1599         )
1600
1601     @property
1602     def is_triple_quoted_string(self) -> bool:
1603         """Is the line a triple quoted string?"""
1604         return (
1605             bool(self)
1606             and self.leaves[0].type == token.STRING
1607             and self.leaves[0].value.startswith(('"""', "'''"))
1608         )
1609
1610     def contains_standalone_comments(self, depth_limit: int = sys.maxsize) -> bool:
1611         """If so, needs to be split before emitting."""
1612         for leaf in self.leaves:
1613             if leaf.type == STANDALONE_COMMENT and leaf.bracket_depth <= depth_limit:
1614                 return True
1615
1616         return False
1617
1618     def contains_uncollapsable_type_comments(self) -> bool:
1619         ignored_ids = set()
1620         try:
1621             last_leaf = self.leaves[-1]
1622             ignored_ids.add(id(last_leaf))
1623             if last_leaf.type == token.COMMA or (
1624                 last_leaf.type == token.RPAR and not last_leaf.value
1625             ):
1626                 # When trailing commas or optional parens are inserted by Black for
1627                 # consistency, comments after the previous last element are not moved
1628                 # (they don't have to, rendering will still be correct).  So we ignore
1629                 # trailing commas and invisible.
1630                 last_leaf = self.leaves[-2]
1631                 ignored_ids.add(id(last_leaf))
1632         except IndexError:
1633             return False
1634
1635         # A type comment is uncollapsable if it is attached to a leaf
1636         # that isn't at the end of the line (since that could cause it
1637         # to get associated to a different argument) or if there are
1638         # comments before it (since that could cause it to get hidden
1639         # behind a comment.
1640         comment_seen = False
1641         for leaf_id, comments in self.comments.items():
1642             for comment in comments:
1643                 if is_type_comment(comment):
1644                     if comment_seen or (
1645                         not is_type_comment(comment, " ignore")
1646                         and leaf_id not in ignored_ids
1647                     ):
1648                         return True
1649
1650                 comment_seen = True
1651
1652         return False
1653
1654     def contains_unsplittable_type_ignore(self) -> bool:
1655         if not self.leaves:
1656             return False
1657
1658         # If a 'type: ignore' is attached to the end of a line, we
1659         # can't split the line, because we can't know which of the
1660         # subexpressions the ignore was meant to apply to.
1661         #
1662         # We only want this to apply to actual physical lines from the
1663         # original source, though: we don't want the presence of a
1664         # 'type: ignore' at the end of a multiline expression to
1665         # justify pushing it all onto one line. Thus we
1666         # (unfortunately) need to check the actual source lines and
1667         # only report an unsplittable 'type: ignore' if this line was
1668         # one line in the original code.
1669
1670         # Grab the first and last line numbers, skipping generated leaves
1671         first_line = next((leaf.lineno for leaf in self.leaves if leaf.lineno != 0), 0)
1672         last_line = next(
1673             (leaf.lineno for leaf in reversed(self.leaves) if leaf.lineno != 0), 0
1674         )
1675
1676         if first_line == last_line:
1677             # We look at the last two leaves since a comma or an
1678             # invisible paren could have been added at the end of the
1679             # line.
1680             for node in self.leaves[-2:]:
1681                 for comment in self.comments.get(id(node), []):
1682                     if is_type_comment(comment, " ignore"):
1683                         return True
1684
1685         return False
1686
1687     def contains_multiline_strings(self) -> bool:
1688         return any(is_multiline_string(leaf) for leaf in self.leaves)
1689
1690     def has_magic_trailing_comma(
1691         self, closing: Leaf, ensure_removable: bool = False
1692     ) -> bool:
1693         """Return True if we have a magic trailing comma, that is when:
1694         - there's a trailing comma here
1695         - it's not a one-tuple
1696         Additionally, if ensure_removable:
1697         - it's not from square bracket indexing
1698         """
1699         if not (
1700             closing.type in CLOSING_BRACKETS
1701             and self.leaves
1702             and self.leaves[-1].type == token.COMMA
1703         ):
1704             return False
1705
1706         if closing.type == token.RBRACE:
1707             return True
1708
1709         if closing.type == token.RSQB:
1710             if not ensure_removable:
1711                 return True
1712             comma = self.leaves[-1]
1713             return bool(comma.parent and comma.parent.type == syms.listmaker)
1714
1715         if self.is_import:
1716             return True
1717
1718         if not is_one_tuple_between(closing.opening_bracket, closing, self.leaves):
1719             return True
1720
1721         return False
1722
1723     def append_comment(self, comment: Leaf) -> bool:
1724         """Add an inline or standalone comment to the line."""
1725         if (
1726             comment.type == STANDALONE_COMMENT
1727             and self.bracket_tracker.any_open_brackets()
1728         ):
1729             comment.prefix = ""
1730             return False
1731
1732         if comment.type != token.COMMENT:
1733             return False
1734
1735         if not self.leaves:
1736             comment.type = STANDALONE_COMMENT
1737             comment.prefix = ""
1738             return False
1739
1740         last_leaf = self.leaves[-1]
1741         if (
1742             last_leaf.type == token.RPAR
1743             and not last_leaf.value
1744             and last_leaf.parent
1745             and len(list(last_leaf.parent.leaves())) <= 3
1746             and not is_type_comment(comment)
1747         ):
1748             # Comments on an optional parens wrapping a single leaf should belong to
1749             # the wrapped node except if it's a type comment. Pinning the comment like
1750             # this avoids unstable formatting caused by comment migration.
1751             if len(self.leaves) < 2:
1752                 comment.type = STANDALONE_COMMENT
1753                 comment.prefix = ""
1754                 return False
1755
1756             last_leaf = self.leaves[-2]
1757         self.comments.setdefault(id(last_leaf), []).append(comment)
1758         return True
1759
1760     def comments_after(self, leaf: Leaf) -> List[Leaf]:
1761         """Generate comments that should appear directly after `leaf`."""
1762         return self.comments.get(id(leaf), [])
1763
1764     def remove_trailing_comma(self) -> None:
1765         """Remove the trailing comma and moves the comments attached to it."""
1766         trailing_comma = self.leaves.pop()
1767         trailing_comma_comments = self.comments.pop(id(trailing_comma), [])
1768         self.comments.setdefault(id(self.leaves[-1]), []).extend(
1769             trailing_comma_comments
1770         )
1771
1772     def is_complex_subscript(self, leaf: Leaf) -> bool:
1773         """Return True iff `leaf` is part of a slice with non-trivial exprs."""
1774         open_lsqb = self.bracket_tracker.get_open_lsqb()
1775         if open_lsqb is None:
1776             return False
1777
1778         subscript_start = open_lsqb.next_sibling
1779
1780         if isinstance(subscript_start, Node):
1781             if subscript_start.type == syms.listmaker:
1782                 return False
1783
1784             if subscript_start.type == syms.subscriptlist:
1785                 subscript_start = child_towards(subscript_start, leaf)
1786         return subscript_start is not None and any(
1787             n.type in TEST_DESCENDANTS for n in subscript_start.pre_order()
1788         )
1789
1790     def clone(self) -> "Line":
1791         return Line(
1792             mode=self.mode,
1793             depth=self.depth,
1794             inside_brackets=self.inside_brackets,
1795             should_split_rhs=self.should_split_rhs,
1796             magic_trailing_comma=self.magic_trailing_comma,
1797         )
1798
1799     def __str__(self) -> str:
1800         """Render the line."""
1801         if not self:
1802             return "\n"
1803
1804         indent = "    " * self.depth
1805         leaves = iter(self.leaves)
1806         first = next(leaves)
1807         res = f"{first.prefix}{indent}{first.value}"
1808         for leaf in leaves:
1809             res += str(leaf)
1810         for comment in itertools.chain.from_iterable(self.comments.values()):
1811             res += str(comment)
1812
1813         return res + "\n"
1814
1815     def __bool__(self) -> bool:
1816         """Return True if the line has leaves or comments."""
1817         return bool(self.leaves or self.comments)
1818
1819
1820 @dataclass
1821 class EmptyLineTracker:
1822     """Provides a stateful method that returns the number of potential extra
1823     empty lines needed before and after the currently processed line.
1824
1825     Note: this tracker works on lines that haven't been split yet.  It assumes
1826     the prefix of the first leaf consists of optional newlines.  Those newlines
1827     are consumed by `maybe_empty_lines()` and included in the computation.
1828     """
1829
1830     is_pyi: bool = False
1831     previous_line: Optional[Line] = None
1832     previous_after: int = 0
1833     previous_defs: List[int] = field(default_factory=list)
1834
1835     def maybe_empty_lines(self, current_line: Line) -> Tuple[int, int]:
1836         """Return the number of extra empty lines before and after the `current_line`.
1837
1838         This is for separating `def`, `async def` and `class` with extra empty
1839         lines (two on module-level).
1840         """
1841         before, after = self._maybe_empty_lines(current_line)
1842         before = (
1843             # Black should not insert empty lines at the beginning
1844             # of the file
1845             0
1846             if self.previous_line is None
1847             else before - self.previous_after
1848         )
1849         self.previous_after = after
1850         self.previous_line = current_line
1851         return before, after
1852
1853     def _maybe_empty_lines(self, current_line: Line) -> Tuple[int, int]:
1854         max_allowed = 1
1855         if current_line.depth == 0:
1856             max_allowed = 1 if self.is_pyi else 2
1857         if current_line.leaves:
1858             # Consume the first leaf's extra newlines.
1859             first_leaf = current_line.leaves[0]
1860             before = first_leaf.prefix.count("\n")
1861             before = min(before, max_allowed)
1862             first_leaf.prefix = ""
1863         else:
1864             before = 0
1865         depth = current_line.depth
1866         while self.previous_defs and self.previous_defs[-1] >= depth:
1867             self.previous_defs.pop()
1868             if self.is_pyi:
1869                 before = 0 if depth else 1
1870             else:
1871                 before = 1 if depth else 2
1872         if current_line.is_decorator or current_line.is_def or current_line.is_class:
1873             return self._maybe_empty_lines_for_class_or_def(current_line, before)
1874
1875         if (
1876             self.previous_line
1877             and self.previous_line.is_import
1878             and not current_line.is_import
1879             and depth == self.previous_line.depth
1880         ):
1881             return (before or 1), 0
1882
1883         if (
1884             self.previous_line
1885             and self.previous_line.is_class
1886             and current_line.is_triple_quoted_string
1887         ):
1888             return before, 1
1889
1890         return before, 0
1891
1892     def _maybe_empty_lines_for_class_or_def(
1893         self, current_line: Line, before: int
1894     ) -> Tuple[int, int]:
1895         if not current_line.is_decorator:
1896             self.previous_defs.append(current_line.depth)
1897         if self.previous_line is None:
1898             # Don't insert empty lines before the first line in the file.
1899             return 0, 0
1900
1901         if self.previous_line.is_decorator:
1902             if self.is_pyi and current_line.is_stub_class:
1903                 # Insert an empty line after a decorated stub class
1904                 return 0, 1
1905
1906             return 0, 0
1907
1908         if self.previous_line.depth < current_line.depth and (
1909             self.previous_line.is_class or self.previous_line.is_def
1910         ):
1911             return 0, 0
1912
1913         if (
1914             self.previous_line.is_comment
1915             and self.previous_line.depth == current_line.depth
1916             and before == 0
1917         ):
1918             return 0, 0
1919
1920         if self.is_pyi:
1921             if self.previous_line.depth > current_line.depth:
1922                 newlines = 1
1923             elif current_line.is_class or self.previous_line.is_class:
1924                 if current_line.is_stub_class and self.previous_line.is_stub_class:
1925                     # No blank line between classes with an empty body
1926                     newlines = 0
1927                 else:
1928                     newlines = 1
1929             elif (
1930                 current_line.is_def or current_line.is_decorator
1931             ) and not self.previous_line.is_def:
1932                 # Blank line between a block of functions (maybe with preceding
1933                 # decorators) and a block of non-functions
1934                 newlines = 1
1935             else:
1936                 newlines = 0
1937         else:
1938             newlines = 2
1939         if current_line.depth and newlines:
1940             newlines -= 1
1941         return newlines, 0
1942
1943
1944 @dataclass
1945 class LineGenerator(Visitor[Line]):
1946     """Generates reformatted Line objects.  Empty lines are not emitted.
1947
1948     Note: destroys the tree it's visiting by mutating prefixes of its leaves
1949     in ways that will no longer stringify to valid Python code on the tree.
1950     """
1951
1952     mode: Mode
1953     remove_u_prefix: bool = False
1954     current_line: Line = field(init=False)
1955
1956     def line(self, indent: int = 0) -> Iterator[Line]:
1957         """Generate a line.
1958
1959         If the line is empty, only emit if it makes sense.
1960         If the line is too long, split it first and then generate.
1961
1962         If any lines were generated, set up a new current_line.
1963         """
1964         if not self.current_line:
1965             self.current_line.depth += indent
1966             return  # Line is empty, don't emit. Creating a new one unnecessary.
1967
1968         complete_line = self.current_line
1969         self.current_line = Line(mode=self.mode, depth=complete_line.depth + indent)
1970         yield complete_line
1971
1972     def visit_default(self, node: LN) -> Iterator[Line]:
1973         """Default `visit_*()` implementation. Recurses to children of `node`."""
1974         if isinstance(node, Leaf):
1975             any_open_brackets = self.current_line.bracket_tracker.any_open_brackets()
1976             for comment in generate_comments(node):
1977                 if any_open_brackets:
1978                     # any comment within brackets is subject to splitting
1979                     self.current_line.append(comment)
1980                 elif comment.type == token.COMMENT:
1981                     # regular trailing comment
1982                     self.current_line.append(comment)
1983                     yield from self.line()
1984
1985                 else:
1986                     # regular standalone comment
1987                     yield from self.line()
1988
1989                     self.current_line.append(comment)
1990                     yield from self.line()
1991
1992             normalize_prefix(node, inside_brackets=any_open_brackets)
1993             if self.mode.string_normalization and node.type == token.STRING:
1994                 normalize_string_prefix(node, remove_u_prefix=self.remove_u_prefix)
1995                 normalize_string_quotes(node)
1996             if node.type == token.NUMBER:
1997                 normalize_numeric_literal(node)
1998             if node.type not in WHITESPACE:
1999                 self.current_line.append(node)
2000         yield from super().visit_default(node)
2001
2002     def visit_INDENT(self, node: Leaf) -> Iterator[Line]:
2003         """Increase indentation level, maybe yield a line."""
2004         # In blib2to3 INDENT never holds comments.
2005         yield from self.line(+1)
2006         yield from self.visit_default(node)
2007
2008     def visit_DEDENT(self, node: Leaf) -> Iterator[Line]:
2009         """Decrease indentation level, maybe yield a line."""
2010         # The current line might still wait for trailing comments.  At DEDENT time
2011         # there won't be any (they would be prefixes on the preceding NEWLINE).
2012         # Emit the line then.
2013         yield from self.line()
2014
2015         # While DEDENT has no value, its prefix may contain standalone comments
2016         # that belong to the current indentation level.  Get 'em.
2017         yield from self.visit_default(node)
2018
2019         # Finally, emit the dedent.
2020         yield from self.line(-1)
2021
2022     def visit_stmt(
2023         self, node: Node, keywords: Set[str], parens: Set[str]
2024     ) -> Iterator[Line]:
2025         """Visit a statement.
2026
2027         This implementation is shared for `if`, `while`, `for`, `try`, `except`,
2028         `def`, `with`, `class`, `assert` and assignments.
2029
2030         The relevant Python language `keywords` for a given statement will be
2031         NAME leaves within it. This methods puts those on a separate line.
2032
2033         `parens` holds a set of string leaf values immediately after which
2034         invisible parens should be put.
2035         """
2036         normalize_invisible_parens(node, parens_after=parens)
2037         for child in node.children:
2038             if child.type == token.NAME and child.value in keywords:  # type: ignore
2039                 yield from self.line()
2040
2041             yield from self.visit(child)
2042
2043     def visit_suite(self, node: Node) -> Iterator[Line]:
2044         """Visit a suite."""
2045         if self.mode.is_pyi and is_stub_suite(node):
2046             yield from self.visit(node.children[2])
2047         else:
2048             yield from self.visit_default(node)
2049
2050     def visit_simple_stmt(self, node: Node) -> Iterator[Line]:
2051         """Visit a statement without nested statements."""
2052         if first_child_is_arith(node):
2053             wrap_in_parentheses(node, node.children[0], visible=False)
2054         is_suite_like = node.parent and node.parent.type in STATEMENT
2055         if is_suite_like:
2056             if self.mode.is_pyi and is_stub_body(node):
2057                 yield from self.visit_default(node)
2058             else:
2059                 yield from self.line(+1)
2060                 yield from self.visit_default(node)
2061                 yield from self.line(-1)
2062
2063         else:
2064             if (
2065                 not self.mode.is_pyi
2066                 or not node.parent
2067                 or not is_stub_suite(node.parent)
2068             ):
2069                 yield from self.line()
2070             yield from self.visit_default(node)
2071
2072     def visit_async_stmt(self, node: Node) -> Iterator[Line]:
2073         """Visit `async def`, `async for`, `async with`."""
2074         yield from self.line()
2075
2076         children = iter(node.children)
2077         for child in children:
2078             yield from self.visit(child)
2079
2080             if child.type == token.ASYNC:
2081                 break
2082
2083         internal_stmt = next(children)
2084         for child in internal_stmt.children:
2085             yield from self.visit(child)
2086
2087     def visit_decorators(self, node: Node) -> Iterator[Line]:
2088         """Visit decorators."""
2089         for child in node.children:
2090             yield from self.line()
2091             yield from self.visit(child)
2092
2093     def visit_SEMI(self, leaf: Leaf) -> Iterator[Line]:
2094         """Remove a semicolon and put the other statement on a separate line."""
2095         yield from self.line()
2096
2097     def visit_ENDMARKER(self, leaf: Leaf) -> Iterator[Line]:
2098         """End of file. Process outstanding comments and end with a newline."""
2099         yield from self.visit_default(leaf)
2100         yield from self.line()
2101
2102     def visit_STANDALONE_COMMENT(self, leaf: Leaf) -> Iterator[Line]:
2103         if not self.current_line.bracket_tracker.any_open_brackets():
2104             yield from self.line()
2105         yield from self.visit_default(leaf)
2106
2107     def visit_factor(self, node: Node) -> Iterator[Line]:
2108         """Force parentheses between a unary op and a binary power:
2109
2110         -2 ** 8 -> -(2 ** 8)
2111         """
2112         _operator, operand = node.children
2113         if (
2114             operand.type == syms.power
2115             and len(operand.children) == 3
2116             and operand.children[1].type == token.DOUBLESTAR
2117         ):
2118             lpar = Leaf(token.LPAR, "(")
2119             rpar = Leaf(token.RPAR, ")")
2120             index = operand.remove() or 0
2121             node.insert_child(index, Node(syms.atom, [lpar, operand, rpar]))
2122         yield from self.visit_default(node)
2123
2124     def visit_STRING(self, leaf: Leaf) -> Iterator[Line]:
2125         if is_docstring(leaf) and "\\\n" not in leaf.value:
2126             # We're ignoring docstrings with backslash newline escapes because changing
2127             # indentation of those changes the AST representation of the code.
2128             prefix = get_string_prefix(leaf.value)
2129             lead_len = len(prefix) + 3
2130             tail_len = -3
2131             indent = " " * 4 * self.current_line.depth
2132             docstring = fix_docstring(leaf.value[lead_len:tail_len], indent)
2133             if docstring:
2134                 if leaf.value[lead_len - 1] == docstring[0]:
2135                     docstring = " " + docstring
2136                 if leaf.value[tail_len + 1] == docstring[-1]:
2137                     docstring = docstring + " "
2138             leaf.value = leaf.value[0:lead_len] + docstring + leaf.value[tail_len:]
2139
2140         yield from self.visit_default(leaf)
2141
2142     def __post_init__(self) -> None:
2143         """You are in a twisty little maze of passages."""
2144         self.current_line = Line(mode=self.mode)
2145
2146         v = self.visit_stmt
2147         Ø: Set[str] = set()
2148         self.visit_assert_stmt = partial(v, keywords={"assert"}, parens={"assert", ","})
2149         self.visit_if_stmt = partial(
2150             v, keywords={"if", "else", "elif"}, parens={"if", "elif"}
2151         )
2152         self.visit_while_stmt = partial(v, keywords={"while", "else"}, parens={"while"})
2153         self.visit_for_stmt = partial(v, keywords={"for", "else"}, parens={"for", "in"})
2154         self.visit_try_stmt = partial(
2155             v, keywords={"try", "except", "else", "finally"}, parens=Ø
2156         )
2157         self.visit_except_clause = partial(v, keywords={"except"}, parens=Ø)
2158         self.visit_with_stmt = partial(v, keywords={"with"}, parens=Ø)
2159         self.visit_funcdef = partial(v, keywords={"def"}, parens=Ø)
2160         self.visit_classdef = partial(v, keywords={"class"}, parens=Ø)
2161         self.visit_expr_stmt = partial(v, keywords=Ø, parens=ASSIGNMENTS)
2162         self.visit_return_stmt = partial(v, keywords={"return"}, parens={"return"})
2163         self.visit_import_from = partial(v, keywords=Ø, parens={"import"})
2164         self.visit_del_stmt = partial(v, keywords=Ø, parens={"del"})
2165         self.visit_async_funcdef = self.visit_async_stmt
2166         self.visit_decorated = self.visit_decorators
2167
2168
2169 IMPLICIT_TUPLE = {syms.testlist, syms.testlist_star_expr, syms.exprlist}
2170 BRACKET = {token.LPAR: token.RPAR, token.LSQB: token.RSQB, token.LBRACE: token.RBRACE}
2171 OPENING_BRACKETS = set(BRACKET.keys())
2172 CLOSING_BRACKETS = set(BRACKET.values())
2173 BRACKETS = OPENING_BRACKETS | CLOSING_BRACKETS
2174 ALWAYS_NO_SPACE = CLOSING_BRACKETS | {token.COMMA, STANDALONE_COMMENT}
2175
2176
2177 def whitespace(leaf: Leaf, *, complex_subscript: bool) -> str:  # noqa: C901
2178     """Return whitespace prefix if needed for the given `leaf`.
2179
2180     `complex_subscript` signals whether the given leaf is part of a subscription
2181     which has non-trivial arguments, like arithmetic expressions or function calls.
2182     """
2183     NO = ""
2184     SPACE = " "
2185     DOUBLESPACE = "  "
2186     t = leaf.type
2187     p = leaf.parent
2188     v = leaf.value
2189     if t in ALWAYS_NO_SPACE:
2190         return NO
2191
2192     if t == token.COMMENT:
2193         return DOUBLESPACE
2194
2195     assert p is not None, f"INTERNAL ERROR: hand-made leaf without parent: {leaf!r}"
2196     if t == token.COLON and p.type not in {
2197         syms.subscript,
2198         syms.subscriptlist,
2199         syms.sliceop,
2200     }:
2201         return NO
2202
2203     prev = leaf.prev_sibling
2204     if not prev:
2205         prevp = preceding_leaf(p)
2206         if not prevp or prevp.type in OPENING_BRACKETS:
2207             return NO
2208
2209         if t == token.COLON:
2210             if prevp.type == token.COLON:
2211                 return NO
2212
2213             elif prevp.type != token.COMMA and not complex_subscript:
2214                 return NO
2215
2216             return SPACE
2217
2218         if prevp.type == token.EQUAL:
2219             if prevp.parent:
2220                 if prevp.parent.type in {
2221                     syms.arglist,
2222                     syms.argument,
2223                     syms.parameters,
2224                     syms.varargslist,
2225                 }:
2226                     return NO
2227
2228                 elif prevp.parent.type == syms.typedargslist:
2229                     # A bit hacky: if the equal sign has whitespace, it means we
2230                     # previously found it's a typed argument.  So, we're using
2231                     # that, too.
2232                     return prevp.prefix
2233
2234         elif prevp.type in VARARGS_SPECIALS:
2235             if is_vararg(prevp, within=VARARGS_PARENTS | UNPACKING_PARENTS):
2236                 return NO
2237
2238         elif prevp.type == token.COLON:
2239             if prevp.parent and prevp.parent.type in {syms.subscript, syms.sliceop}:
2240                 return SPACE if complex_subscript else NO
2241
2242         elif (
2243             prevp.parent
2244             and prevp.parent.type == syms.factor
2245             and prevp.type in MATH_OPERATORS
2246         ):
2247             return NO
2248
2249         elif (
2250             prevp.type == token.RIGHTSHIFT
2251             and prevp.parent
2252             and prevp.parent.type == syms.shift_expr
2253             and prevp.prev_sibling
2254             and prevp.prev_sibling.type == token.NAME
2255             and prevp.prev_sibling.value == "print"  # type: ignore
2256         ):
2257             # Python 2 print chevron
2258             return NO
2259         elif prevp.type == token.AT and p.parent and p.parent.type == syms.decorator:
2260             # no space in decorators
2261             return NO
2262
2263     elif prev.type in OPENING_BRACKETS:
2264         return NO
2265
2266     if p.type in {syms.parameters, syms.arglist}:
2267         # untyped function signatures or calls
2268         if not prev or prev.type != token.COMMA:
2269             return NO
2270
2271     elif p.type == syms.varargslist:
2272         # lambdas
2273         if prev and prev.type != token.COMMA:
2274             return NO
2275
2276     elif p.type == syms.typedargslist:
2277         # typed function signatures
2278         if not prev:
2279             return NO
2280
2281         if t == token.EQUAL:
2282             if prev.type != syms.tname:
2283                 return NO
2284
2285         elif prev.type == token.EQUAL:
2286             # A bit hacky: if the equal sign has whitespace, it means we
2287             # previously found it's a typed argument.  So, we're using that, too.
2288             return prev.prefix
2289
2290         elif prev.type != token.COMMA:
2291             return NO
2292
2293     elif p.type == syms.tname:
2294         # type names
2295         if not prev:
2296             prevp = preceding_leaf(p)
2297             if not prevp or prevp.type != token.COMMA:
2298                 return NO
2299
2300     elif p.type == syms.trailer:
2301         # attributes and calls
2302         if t == token.LPAR or t == token.RPAR:
2303             return NO
2304
2305         if not prev:
2306             if t == token.DOT:
2307                 prevp = preceding_leaf(p)
2308                 if not prevp or prevp.type != token.NUMBER:
2309                     return NO
2310
2311             elif t == token.LSQB:
2312                 return NO
2313
2314         elif prev.type != token.COMMA:
2315             return NO
2316
2317     elif p.type == syms.argument:
2318         # single argument
2319         if t == token.EQUAL:
2320             return NO
2321
2322         if not prev:
2323             prevp = preceding_leaf(p)
2324             if not prevp or prevp.type == token.LPAR:
2325                 return NO
2326
2327         elif prev.type in {token.EQUAL} | VARARGS_SPECIALS:
2328             return NO
2329
2330     elif p.type == syms.decorator:
2331         # decorators
2332         return NO
2333
2334     elif p.type == syms.dotted_name:
2335         if prev:
2336             return NO
2337
2338         prevp = preceding_leaf(p)
2339         if not prevp or prevp.type == token.AT or prevp.type == token.DOT:
2340             return NO
2341
2342     elif p.type == syms.classdef:
2343         if t == token.LPAR:
2344             return NO
2345
2346         if prev and prev.type == token.LPAR:
2347             return NO
2348
2349     elif p.type in {syms.subscript, syms.sliceop}:
2350         # indexing
2351         if not prev:
2352             assert p.parent is not None, "subscripts are always parented"
2353             if p.parent.type == syms.subscriptlist:
2354                 return SPACE
2355
2356             return NO
2357
2358         elif not complex_subscript:
2359             return NO
2360
2361     elif p.type == syms.atom:
2362         if prev and t == token.DOT:
2363             # dots, but not the first one.
2364             return NO
2365
2366     elif p.type == syms.dictsetmaker:
2367         # dict unpacking
2368         if prev and prev.type == token.DOUBLESTAR:
2369             return NO
2370
2371     elif p.type in {syms.factor, syms.star_expr}:
2372         # unary ops
2373         if not prev:
2374             prevp = preceding_leaf(p)
2375             if not prevp or prevp.type in OPENING_BRACKETS:
2376                 return NO
2377
2378             prevp_parent = prevp.parent
2379             assert prevp_parent is not None
2380             if prevp.type == token.COLON and prevp_parent.type in {
2381                 syms.subscript,
2382                 syms.sliceop,
2383             }:
2384                 return NO
2385
2386             elif prevp.type == token.EQUAL and prevp_parent.type == syms.argument:
2387                 return NO
2388
2389         elif t in {token.NAME, token.NUMBER, token.STRING}:
2390             return NO
2391
2392     elif p.type == syms.import_from:
2393         if t == token.DOT:
2394             if prev and prev.type == token.DOT:
2395                 return NO
2396
2397         elif t == token.NAME:
2398             if v == "import":
2399                 return SPACE
2400
2401             if prev and prev.type == token.DOT:
2402                 return NO
2403
2404     elif p.type == syms.sliceop:
2405         return NO
2406
2407     return SPACE
2408
2409
2410 def preceding_leaf(node: Optional[LN]) -> Optional[Leaf]:
2411     """Return the first leaf that precedes `node`, if any."""
2412     while node:
2413         res = node.prev_sibling
2414         if res:
2415             if isinstance(res, Leaf):
2416                 return res
2417
2418             try:
2419                 return list(res.leaves())[-1]
2420
2421             except IndexError:
2422                 return None
2423
2424         node = node.parent
2425     return None
2426
2427
2428 def prev_siblings_are(node: Optional[LN], tokens: List[Optional[NodeType]]) -> bool:
2429     """Return if the `node` and its previous siblings match types against the provided
2430     list of tokens; the provided `node`has its type matched against the last element in
2431     the list.  `None` can be used as the first element to declare that the start of the
2432     list is anchored at the start of its parent's children."""
2433     if not tokens:
2434         return True
2435     if tokens[-1] is None:
2436         return node is None
2437     if not node:
2438         return False
2439     if node.type != tokens[-1]:
2440         return False
2441     return prev_siblings_are(node.prev_sibling, tokens[:-1])
2442
2443
2444 def child_towards(ancestor: Node, descendant: LN) -> Optional[LN]:
2445     """Return the child of `ancestor` that contains `descendant`."""
2446     node: Optional[LN] = descendant
2447     while node and node.parent != ancestor:
2448         node = node.parent
2449     return node
2450
2451
2452 def container_of(leaf: Leaf) -> LN:
2453     """Return `leaf` or one of its ancestors that is the topmost container of it.
2454
2455     By "container" we mean a node where `leaf` is the very first child.
2456     """
2457     same_prefix = leaf.prefix
2458     container: LN = leaf
2459     while container:
2460         parent = container.parent
2461         if parent is None:
2462             break
2463
2464         if parent.children[0].prefix != same_prefix:
2465             break
2466
2467         if parent.type == syms.file_input:
2468             break
2469
2470         if parent.prev_sibling is not None and parent.prev_sibling.type in BRACKETS:
2471             break
2472
2473         container = parent
2474     return container
2475
2476
2477 def is_split_after_delimiter(leaf: Leaf, previous: Optional[Leaf] = None) -> Priority:
2478     """Return the priority of the `leaf` delimiter, given a line break after it.
2479
2480     The delimiter priorities returned here are from those delimiters that would
2481     cause a line break after themselves.
2482
2483     Higher numbers are higher priority.
2484     """
2485     if leaf.type == token.COMMA:
2486         return COMMA_PRIORITY
2487
2488     return 0
2489
2490
2491 def is_split_before_delimiter(leaf: Leaf, previous: Optional[Leaf] = None) -> Priority:
2492     """Return the priority of the `leaf` delimiter, given a line break before it.
2493
2494     The delimiter priorities returned here are from those delimiters that would
2495     cause a line break before themselves.
2496
2497     Higher numbers are higher priority.
2498     """
2499     if is_vararg(leaf, within=VARARGS_PARENTS | UNPACKING_PARENTS):
2500         # * and ** might also be MATH_OPERATORS but in this case they are not.
2501         # Don't treat them as a delimiter.
2502         return 0
2503
2504     if (
2505         leaf.type == token.DOT
2506         and leaf.parent
2507         and leaf.parent.type not in {syms.import_from, syms.dotted_name}
2508         and (previous is None or previous.type in CLOSING_BRACKETS)
2509     ):
2510         return DOT_PRIORITY
2511
2512     if (
2513         leaf.type in MATH_OPERATORS
2514         and leaf.parent
2515         and leaf.parent.type not in {syms.factor, syms.star_expr}
2516     ):
2517         return MATH_PRIORITIES[leaf.type]
2518
2519     if leaf.type in COMPARATORS:
2520         return COMPARATOR_PRIORITY
2521
2522     if (
2523         leaf.type == token.STRING
2524         and previous is not None
2525         and previous.type == token.STRING
2526     ):
2527         return STRING_PRIORITY
2528
2529     if leaf.type not in {token.NAME, token.ASYNC}:
2530         return 0
2531
2532     if (
2533         leaf.value == "for"
2534         and leaf.parent
2535         and leaf.parent.type in {syms.comp_for, syms.old_comp_for}
2536         or leaf.type == token.ASYNC
2537     ):
2538         if (
2539             not isinstance(leaf.prev_sibling, Leaf)
2540             or leaf.prev_sibling.value != "async"
2541         ):
2542             return COMPREHENSION_PRIORITY
2543
2544     if (
2545         leaf.value == "if"
2546         and leaf.parent
2547         and leaf.parent.type in {syms.comp_if, syms.old_comp_if}
2548     ):
2549         return COMPREHENSION_PRIORITY
2550
2551     if leaf.value in {"if", "else"} and leaf.parent and leaf.parent.type == syms.test:
2552         return TERNARY_PRIORITY
2553
2554     if leaf.value == "is":
2555         return COMPARATOR_PRIORITY
2556
2557     if (
2558         leaf.value == "in"
2559         and leaf.parent
2560         and leaf.parent.type in {syms.comp_op, syms.comparison}
2561         and not (
2562             previous is not None
2563             and previous.type == token.NAME
2564             and previous.value == "not"
2565         )
2566     ):
2567         return COMPARATOR_PRIORITY
2568
2569     if (
2570         leaf.value == "not"
2571         and leaf.parent
2572         and leaf.parent.type == syms.comp_op
2573         and not (
2574             previous is not None
2575             and previous.type == token.NAME
2576             and previous.value == "is"
2577         )
2578     ):
2579         return COMPARATOR_PRIORITY
2580
2581     if leaf.value in LOGIC_OPERATORS and leaf.parent:
2582         return LOGIC_PRIORITY
2583
2584     return 0
2585
2586
2587 FMT_OFF = {"# fmt: off", "# fmt:off", "# yapf: disable"}
2588 FMT_SKIP = {"# fmt: skip", "# fmt:skip"}
2589 FMT_PASS = {*FMT_OFF, *FMT_SKIP}
2590 FMT_ON = {"# fmt: on", "# fmt:on", "# yapf: enable"}
2591
2592
2593 def generate_comments(leaf: LN) -> Iterator[Leaf]:
2594     """Clean the prefix of the `leaf` and generate comments from it, if any.
2595
2596     Comments in lib2to3 are shoved into the whitespace prefix.  This happens
2597     in `pgen2/driver.py:Driver.parse_tokens()`.  This was a brilliant implementation
2598     move because it does away with modifying the grammar to include all the
2599     possible places in which comments can be placed.
2600
2601     The sad consequence for us though is that comments don't "belong" anywhere.
2602     This is why this function generates simple parentless Leaf objects for
2603     comments.  We simply don't know what the correct parent should be.
2604
2605     No matter though, we can live without this.  We really only need to
2606     differentiate between inline and standalone comments.  The latter don't
2607     share the line with any code.
2608
2609     Inline comments are emitted as regular token.COMMENT leaves.  Standalone
2610     are emitted with a fake STANDALONE_COMMENT token identifier.
2611     """
2612     for pc in list_comments(leaf.prefix, is_endmarker=leaf.type == token.ENDMARKER):
2613         yield Leaf(pc.type, pc.value, prefix="\n" * pc.newlines)
2614
2615
2616 @dataclass
2617 class ProtoComment:
2618     """Describes a piece of syntax that is a comment.
2619
2620     It's not a :class:`blib2to3.pytree.Leaf` so that:
2621
2622     * it can be cached (`Leaf` objects should not be reused more than once as
2623       they store their lineno, column, prefix, and parent information);
2624     * `newlines` and `consumed` fields are kept separate from the `value`. This
2625       simplifies handling of special marker comments like ``# fmt: off/on``.
2626     """
2627
2628     type: int  # token.COMMENT or STANDALONE_COMMENT
2629     value: str  # content of the comment
2630     newlines: int  # how many newlines before the comment
2631     consumed: int  # how many characters of the original leaf's prefix did we consume
2632
2633
2634 @lru_cache(maxsize=4096)
2635 def list_comments(prefix: str, *, is_endmarker: bool) -> List[ProtoComment]:
2636     """Return a list of :class:`ProtoComment` objects parsed from the given `prefix`."""
2637     result: List[ProtoComment] = []
2638     if not prefix or "#" not in prefix:
2639         return result
2640
2641     consumed = 0
2642     nlines = 0
2643     ignored_lines = 0
2644     for index, line in enumerate(re.split("\r?\n", prefix)):
2645         consumed += len(line) + 1  # adding the length of the split '\n'
2646         line = line.lstrip()
2647         if not line:
2648             nlines += 1
2649         if not line.startswith("#"):
2650             # Escaped newlines outside of a comment are not really newlines at
2651             # all. We treat a single-line comment following an escaped newline
2652             # as a simple trailing comment.
2653             if line.endswith("\\"):
2654                 ignored_lines += 1
2655             continue
2656
2657         if index == ignored_lines and not is_endmarker:
2658             comment_type = token.COMMENT  # simple trailing comment
2659         else:
2660             comment_type = STANDALONE_COMMENT
2661         comment = make_comment(line)
2662         result.append(
2663             ProtoComment(
2664                 type=comment_type, value=comment, newlines=nlines, consumed=consumed
2665             )
2666         )
2667         nlines = 0
2668     return result
2669
2670
2671 def make_comment(content: str) -> str:
2672     """Return a consistently formatted comment from the given `content` string.
2673
2674     All comments (except for "##", "#!", "#:", '#'", "#%%") should have a single
2675     space between the hash sign and the content.
2676
2677     If `content` didn't start with a hash sign, one is provided.
2678     """
2679     content = content.rstrip()
2680     if not content:
2681         return "#"
2682
2683     if content[0] == "#":
2684         content = content[1:]
2685     if content and content[0] not in " !:#'%":
2686         content = " " + content
2687     return "#" + content
2688
2689
2690 def transform_line(
2691     line: Line, mode: Mode, features: Collection[Feature] = ()
2692 ) -> Iterator[Line]:
2693     """Transform a `line`, potentially splitting it into many lines.
2694
2695     They should fit in the allotted `line_length` but might not be able to.
2696
2697     `features` are syntactical features that may be used in the output.
2698     """
2699     if line.is_comment:
2700         yield line
2701         return
2702
2703     line_str = line_to_string(line)
2704
2705     def init_st(ST: Type[StringTransformer]) -> StringTransformer:
2706         """Initialize StringTransformer"""
2707         return ST(mode.line_length, mode.string_normalization)
2708
2709     string_merge = init_st(StringMerger)
2710     string_paren_strip = init_st(StringParenStripper)
2711     string_split = init_st(StringSplitter)
2712     string_paren_wrap = init_st(StringParenWrapper)
2713
2714     transformers: List[Transformer]
2715     if (
2716         not line.contains_uncollapsable_type_comments()
2717         and not line.should_split_rhs
2718         and not line.magic_trailing_comma
2719         and (
2720             is_line_short_enough(line, line_length=mode.line_length, line_str=line_str)
2721             or line.contains_unsplittable_type_ignore()
2722         )
2723         and not (line.inside_brackets and line.contains_standalone_comments())
2724     ):
2725         # Only apply basic string preprocessing, since lines shouldn't be split here.
2726         if mode.experimental_string_processing:
2727             transformers = [string_merge, string_paren_strip]
2728         else:
2729             transformers = []
2730     elif line.is_def:
2731         transformers = [left_hand_split]
2732     else:
2733
2734         def rhs(line: Line, features: Collection[Feature]) -> Iterator[Line]:
2735             """Wraps calls to `right_hand_split`.
2736
2737             The calls increasingly `omit` right-hand trailers (bracket pairs with
2738             content), meaning the trailers get glued together to split on another
2739             bracket pair instead.
2740             """
2741             for omit in generate_trailers_to_omit(line, mode.line_length):
2742                 lines = list(
2743                     right_hand_split(line, mode.line_length, features, omit=omit)
2744                 )
2745                 # Note: this check is only able to figure out if the first line of the
2746                 # *current* transformation fits in the line length.  This is true only
2747                 # for simple cases.  All others require running more transforms via
2748                 # `transform_line()`.  This check doesn't know if those would succeed.
2749                 if is_line_short_enough(lines[0], line_length=mode.line_length):
2750                     yield from lines
2751                     return
2752
2753             # All splits failed, best effort split with no omits.
2754             # This mostly happens to multiline strings that are by definition
2755             # reported as not fitting a single line, as well as lines that contain
2756             # trailing commas (those have to be exploded).
2757             yield from right_hand_split(
2758                 line, line_length=mode.line_length, features=features
2759             )
2760
2761         if mode.experimental_string_processing:
2762             if line.inside_brackets:
2763                 transformers = [
2764                     string_merge,
2765                     string_paren_strip,
2766                     string_split,
2767                     delimiter_split,
2768                     standalone_comment_split,
2769                     string_paren_wrap,
2770                     rhs,
2771                 ]
2772             else:
2773                 transformers = [
2774                     string_merge,
2775                     string_paren_strip,
2776                     string_split,
2777                     string_paren_wrap,
2778                     rhs,
2779                 ]
2780         else:
2781             if line.inside_brackets:
2782                 transformers = [delimiter_split, standalone_comment_split, rhs]
2783             else:
2784                 transformers = [rhs]
2785
2786     for transform in transformers:
2787         # We are accumulating lines in `result` because we might want to abort
2788         # mission and return the original line in the end, or attempt a different
2789         # split altogether.
2790         try:
2791             result = run_transformer(line, transform, mode, features, line_str=line_str)
2792         except CannotTransform:
2793             continue
2794         else:
2795             yield from result
2796             break
2797
2798     else:
2799         yield line
2800
2801
2802 @dataclass  # type: ignore
2803 class StringTransformer(ABC):
2804     """
2805     An implementation of the Transformer protocol that relies on its
2806     subclasses overriding the template methods `do_match(...)` and
2807     `do_transform(...)`.
2808
2809     This Transformer works exclusively on strings (for example, by merging
2810     or splitting them).
2811
2812     The following sections can be found among the docstrings of each concrete
2813     StringTransformer subclass.
2814
2815     Requirements:
2816         Which requirements must be met of the given Line for this
2817         StringTransformer to be applied?
2818
2819     Transformations:
2820         If the given Line meets all of the above requirements, which string
2821         transformations can you expect to be applied to it by this
2822         StringTransformer?
2823
2824     Collaborations:
2825         What contractual agreements does this StringTransformer have with other
2826         StringTransfomers? Such collaborations should be eliminated/minimized
2827         as much as possible.
2828     """
2829
2830     line_length: int
2831     normalize_strings: bool
2832     __name__ = "StringTransformer"
2833
2834     @abstractmethod
2835     def do_match(self, line: Line) -> TMatchResult:
2836         """
2837         Returns:
2838             * Ok(string_idx) such that `line.leaves[string_idx]` is our target
2839             string, if a match was able to be made.
2840                 OR
2841             * Err(CannotTransform), if a match was not able to be made.
2842         """
2843
2844     @abstractmethod
2845     def do_transform(self, line: Line, string_idx: int) -> Iterator[TResult[Line]]:
2846         """
2847         Yields:
2848             * Ok(new_line) where new_line is the new transformed line.
2849                 OR
2850             * Err(CannotTransform) if the transformation failed for some reason. The
2851             `do_match(...)` template method should usually be used to reject
2852             the form of the given Line, but in some cases it is difficult to
2853             know whether or not a Line meets the StringTransformer's
2854             requirements until the transformation is already midway.
2855
2856         Side Effects:
2857             This method should NOT mutate @line directly, but it MAY mutate the
2858             Line's underlying Node structure. (WARNING: If the underlying Node
2859             structure IS altered, then this method should NOT be allowed to
2860             yield an CannotTransform after that point.)
2861         """
2862
2863     def __call__(self, line: Line, _features: Collection[Feature]) -> Iterator[Line]:
2864         """
2865         StringTransformer instances have a call signature that mirrors that of
2866         the Transformer type.
2867
2868         Raises:
2869             CannotTransform(...) if the concrete StringTransformer class is unable
2870             to transform @line.
2871         """
2872         # Optimization to avoid calling `self.do_match(...)` when the line does
2873         # not contain any string.
2874         if not any(leaf.type == token.STRING for leaf in line.leaves):
2875             raise CannotTransform("There are no strings in this line.")
2876
2877         match_result = self.do_match(line)
2878
2879         if isinstance(match_result, Err):
2880             cant_transform = match_result.err()
2881             raise CannotTransform(
2882                 f"The string transformer {self.__class__.__name__} does not recognize"
2883                 " this line as one that it can transform."
2884             ) from cant_transform
2885
2886         string_idx = match_result.ok()
2887
2888         for line_result in self.do_transform(line, string_idx):
2889             if isinstance(line_result, Err):
2890                 cant_transform = line_result.err()
2891                 raise CannotTransform(
2892                     "StringTransformer failed while attempting to transform string."
2893                 ) from cant_transform
2894             line = line_result.ok()
2895             yield line
2896
2897
2898 @dataclass
2899 class CustomSplit:
2900     """A custom (i.e. manual) string split.
2901
2902     A single CustomSplit instance represents a single substring.
2903
2904     Examples:
2905         Consider the following string:
2906         ```
2907         "Hi there friend."
2908         " This is a custom"
2909         f" string {split}."
2910         ```
2911
2912         This string will correspond to the following three CustomSplit instances:
2913         ```
2914         CustomSplit(False, 16)
2915         CustomSplit(False, 17)
2916         CustomSplit(True, 16)
2917         ```
2918     """
2919
2920     has_prefix: bool
2921     break_idx: int
2922
2923
2924 class CustomSplitMapMixin:
2925     """
2926     This mixin class is used to map merged strings to a sequence of
2927     CustomSplits, which will then be used to re-split the strings iff none of
2928     the resultant substrings go over the configured max line length.
2929     """
2930
2931     _Key = Tuple[StringID, str]
2932     _CUSTOM_SPLIT_MAP: Dict[_Key, Tuple[CustomSplit, ...]] = defaultdict(tuple)
2933
2934     @staticmethod
2935     def _get_key(string: str) -> "CustomSplitMapMixin._Key":
2936         """
2937         Returns:
2938             A unique identifier that is used internally to map @string to a
2939             group of custom splits.
2940         """
2941         return (id(string), string)
2942
2943     def add_custom_splits(
2944         self, string: str, custom_splits: Iterable[CustomSplit]
2945     ) -> None:
2946         """Custom Split Map Setter Method
2947
2948         Side Effects:
2949             Adds a mapping from @string to the custom splits @custom_splits.
2950         """
2951         key = self._get_key(string)
2952         self._CUSTOM_SPLIT_MAP[key] = tuple(custom_splits)
2953
2954     def pop_custom_splits(self, string: str) -> List[CustomSplit]:
2955         """Custom Split Map Getter Method
2956
2957         Returns:
2958             * A list of the custom splits that are mapped to @string, if any
2959             exist.
2960                 OR
2961             * [], otherwise.
2962
2963         Side Effects:
2964             Deletes the mapping between @string and its associated custom
2965             splits (which are returned to the caller).
2966         """
2967         key = self._get_key(string)
2968
2969         custom_splits = self._CUSTOM_SPLIT_MAP[key]
2970         del self._CUSTOM_SPLIT_MAP[key]
2971
2972         return list(custom_splits)
2973
2974     def has_custom_splits(self, string: str) -> bool:
2975         """
2976         Returns:
2977             True iff @string is associated with a set of custom splits.
2978         """
2979         key = self._get_key(string)
2980         return key in self._CUSTOM_SPLIT_MAP
2981
2982
2983 class StringMerger(CustomSplitMapMixin, StringTransformer):
2984     """StringTransformer that merges strings together.
2985
2986     Requirements:
2987         (A) The line contains adjacent strings such that ALL of the validation checks
2988         listed in StringMerger.__validate_msg(...)'s docstring pass.
2989             OR
2990         (B) The line contains a string which uses line continuation backslashes.
2991
2992     Transformations:
2993         Depending on which of the two requirements above where met, either:
2994
2995         (A) The string group associated with the target string is merged.
2996             OR
2997         (B) All line-continuation backslashes are removed from the target string.
2998
2999     Collaborations:
3000         StringMerger provides custom split information to StringSplitter.
3001     """
3002
3003     def do_match(self, line: Line) -> TMatchResult:
3004         LL = line.leaves
3005
3006         is_valid_index = is_valid_index_factory(LL)
3007
3008         for (i, leaf) in enumerate(LL):
3009             if (
3010                 leaf.type == token.STRING
3011                 and is_valid_index(i + 1)
3012                 and LL[i + 1].type == token.STRING
3013             ):
3014                 return Ok(i)
3015
3016             if leaf.type == token.STRING and "\\\n" in leaf.value:
3017                 return Ok(i)
3018
3019         return TErr("This line has no strings that need merging.")
3020
3021     def do_transform(self, line: Line, string_idx: int) -> Iterator[TResult[Line]]:
3022         new_line = line
3023         rblc_result = self.__remove_backslash_line_continuation_chars(
3024             new_line, string_idx
3025         )
3026         if isinstance(rblc_result, Ok):
3027             new_line = rblc_result.ok()
3028
3029         msg_result = self.__merge_string_group(new_line, string_idx)
3030         if isinstance(msg_result, Ok):
3031             new_line = msg_result.ok()
3032
3033         if isinstance(rblc_result, Err) and isinstance(msg_result, Err):
3034             msg_cant_transform = msg_result.err()
3035             rblc_cant_transform = rblc_result.err()
3036             cant_transform = CannotTransform(
3037                 "StringMerger failed to merge any strings in this line."
3038             )
3039
3040             # Chain the errors together using `__cause__`.
3041             msg_cant_transform.__cause__ = rblc_cant_transform
3042             cant_transform.__cause__ = msg_cant_transform
3043
3044             yield Err(cant_transform)
3045         else:
3046             yield Ok(new_line)
3047
3048     @staticmethod
3049     def __remove_backslash_line_continuation_chars(
3050         line: Line, string_idx: int
3051     ) -> TResult[Line]:
3052         """
3053         Merge strings that were split across multiple lines using
3054         line-continuation backslashes.
3055
3056         Returns:
3057             Ok(new_line), if @line contains backslash line-continuation
3058             characters.
3059                 OR
3060             Err(CannotTransform), otherwise.
3061         """
3062         LL = line.leaves
3063
3064         string_leaf = LL[string_idx]
3065         if not (
3066             string_leaf.type == token.STRING
3067             and "\\\n" in string_leaf.value
3068             and not has_triple_quotes(string_leaf.value)
3069         ):
3070             return TErr(
3071                 f"String leaf {string_leaf} does not contain any backslash line"
3072                 " continuation characters."
3073             )
3074
3075         new_line = line.clone()
3076         new_line.comments = line.comments.copy()
3077         append_leaves(new_line, line, LL)
3078
3079         new_string_leaf = new_line.leaves[string_idx]
3080         new_string_leaf.value = new_string_leaf.value.replace("\\\n", "")
3081
3082         return Ok(new_line)
3083
3084     def __merge_string_group(self, line: Line, string_idx: int) -> TResult[Line]:
3085         """
3086         Merges string group (i.e. set of adjacent strings) where the first
3087         string in the group is `line.leaves[string_idx]`.
3088
3089         Returns:
3090             Ok(new_line), if ALL of the validation checks found in
3091             __validate_msg(...) pass.
3092                 OR
3093             Err(CannotTransform), otherwise.
3094         """
3095         LL = line.leaves
3096
3097         is_valid_index = is_valid_index_factory(LL)
3098
3099         vresult = self.__validate_msg(line, string_idx)
3100         if isinstance(vresult, Err):
3101             return vresult
3102
3103         # If the string group is wrapped inside an Atom node, we must make sure
3104         # to later replace that Atom with our new (merged) string leaf.
3105         atom_node = LL[string_idx].parent
3106
3107         # We will place BREAK_MARK in between every two substrings that we
3108         # merge. We will then later go through our final result and use the
3109         # various instances of BREAK_MARK we find to add the right values to
3110         # the custom split map.
3111         BREAK_MARK = "@@@@@ BLACK BREAKPOINT MARKER @@@@@"
3112
3113         QUOTE = LL[string_idx].value[-1]
3114
3115         def make_naked(string: str, string_prefix: str) -> str:
3116             """Strip @string (i.e. make it a "naked" string)
3117
3118             Pre-conditions:
3119                 * assert_is_leaf_string(@string)
3120
3121             Returns:
3122                 A string that is identical to @string except that
3123                 @string_prefix has been stripped, the surrounding QUOTE
3124                 characters have been removed, and any remaining QUOTE
3125                 characters have been escaped.
3126             """
3127             assert_is_leaf_string(string)
3128
3129             RE_EVEN_BACKSLASHES = r"(?:(?<!\\)(?:\\\\)*)"
3130             naked_string = string[len(string_prefix) + 1 : -1]
3131             naked_string = re.sub(
3132                 "(" + RE_EVEN_BACKSLASHES + ")" + QUOTE, r"\1\\" + QUOTE, naked_string
3133             )
3134             return naked_string
3135
3136         # Holds the CustomSplit objects that will later be added to the custom
3137         # split map.
3138         custom_splits = []
3139
3140         # Temporary storage for the 'has_prefix' part of the CustomSplit objects.
3141         prefix_tracker = []
3142
3143         # Sets the 'prefix' variable. This is the prefix that the final merged
3144         # string will have.
3145         next_str_idx = string_idx
3146         prefix = ""
3147         while (
3148             not prefix
3149             and is_valid_index(next_str_idx)
3150             and LL[next_str_idx].type == token.STRING
3151         ):
3152             prefix = get_string_prefix(LL[next_str_idx].value)
3153             next_str_idx += 1
3154
3155         # The next loop merges the string group. The final string will be
3156         # contained in 'S'.
3157         #
3158         # The following convenience variables are used:
3159         #
3160         #   S: string
3161         #   NS: naked string
3162         #   SS: next string
3163         #   NSS: naked next string
3164         S = ""
3165         NS = ""
3166         num_of_strings = 0
3167         next_str_idx = string_idx
3168         while is_valid_index(next_str_idx) and LL[next_str_idx].type == token.STRING:
3169             num_of_strings += 1
3170
3171             SS = LL[next_str_idx].value
3172             next_prefix = get_string_prefix(SS)
3173
3174             # If this is an f-string group but this substring is not prefixed
3175             # with 'f'...
3176             if "f" in prefix and "f" not in next_prefix:
3177                 # Then we must escape any braces contained in this substring.
3178                 SS = re.subf(r"(\{|\})", "{1}{1}", SS)
3179
3180             NSS = make_naked(SS, next_prefix)
3181
3182             has_prefix = bool(next_prefix)
3183             prefix_tracker.append(has_prefix)
3184
3185             S = prefix + QUOTE + NS + NSS + BREAK_MARK + QUOTE
3186             NS = make_naked(S, prefix)
3187
3188             next_str_idx += 1
3189
3190         S_leaf = Leaf(token.STRING, S)
3191         if self.normalize_strings:
3192             normalize_string_quotes(S_leaf)
3193
3194         # Fill the 'custom_splits' list with the appropriate CustomSplit objects.
3195         temp_string = S_leaf.value[len(prefix) + 1 : -1]
3196         for has_prefix in prefix_tracker:
3197             mark_idx = temp_string.find(BREAK_MARK)
3198             assert (
3199                 mark_idx >= 0
3200             ), "Logic error while filling the custom string breakpoint cache."
3201
3202             temp_string = temp_string[mark_idx + len(BREAK_MARK) :]
3203             breakpoint_idx = mark_idx + (len(prefix) if has_prefix else 0) + 1
3204             custom_splits.append(CustomSplit(has_prefix, breakpoint_idx))
3205
3206         string_leaf = Leaf(token.STRING, S_leaf.value.replace(BREAK_MARK, ""))
3207
3208         if atom_node is not None:
3209             replace_child(atom_node, string_leaf)
3210
3211         # Build the final line ('new_line') that this method will later return.
3212         new_line = line.clone()
3213         for (i, leaf) in enumerate(LL):
3214             if i == string_idx:
3215                 new_line.append(string_leaf)
3216
3217             if string_idx <= i < string_idx + num_of_strings:
3218                 for comment_leaf in line.comments_after(LL[i]):
3219                     new_line.append(comment_leaf, preformatted=True)
3220                 continue
3221
3222             append_leaves(new_line, line, [leaf])
3223
3224         self.add_custom_splits(string_leaf.value, custom_splits)
3225         return Ok(new_line)
3226
3227     @staticmethod
3228     def __validate_msg(line: Line, string_idx: int) -> TResult[None]:
3229         """Validate (M)erge (S)tring (G)roup
3230
3231         Transform-time string validation logic for __merge_string_group(...).
3232
3233         Returns:
3234             * Ok(None), if ALL validation checks (listed below) pass.
3235                 OR
3236             * Err(CannotTransform), if any of the following are true:
3237                 - The target string group does not contain ANY stand-alone comments.
3238                 - The target string is not in a string group (i.e. it has no
3239                   adjacent strings).
3240                 - The string group has more than one inline comment.
3241                 - The string group has an inline comment that appears to be a pragma.
3242                 - The set of all string prefixes in the string group is of
3243                   length greater than one and is not equal to {"", "f"}.
3244                 - The string group consists of raw strings.
3245         """
3246         # We first check for "inner" stand-alone comments (i.e. stand-alone
3247         # comments that have a string leaf before them AND after them).
3248         for inc in [1, -1]:
3249             i = string_idx
3250             found_sa_comment = False
3251             is_valid_index = is_valid_index_factory(line.leaves)
3252             while is_valid_index(i) and line.leaves[i].type in [
3253                 token.STRING,
3254                 STANDALONE_COMMENT,
3255             ]:
3256                 if line.leaves[i].type == STANDALONE_COMMENT:
3257                     found_sa_comment = True
3258                 elif found_sa_comment:
3259                     return TErr(
3260                         "StringMerger does NOT merge string groups which contain "
3261                         "stand-alone comments."
3262                     )
3263
3264                 i += inc
3265
3266         num_of_inline_string_comments = 0
3267         set_of_prefixes = set()
3268         num_of_strings = 0
3269         for leaf in line.leaves[string_idx:]:
3270             if leaf.type != token.STRING:
3271                 # If the string group is trailed by a comma, we count the
3272                 # comments trailing the comma to be one of the string group's
3273                 # comments.
3274                 if leaf.type == token.COMMA and id(leaf) in line.comments:
3275                     num_of_inline_string_comments += 1
3276                 break
3277
3278             if has_triple_quotes(leaf.value):
3279                 return TErr("StringMerger does NOT merge multiline strings.")
3280
3281             num_of_strings += 1
3282             prefix = get_string_prefix(leaf.value)
3283             if "r" in prefix:
3284                 return TErr("StringMerger does NOT merge raw strings.")
3285
3286             set_of_prefixes.add(prefix)
3287
3288             if id(leaf) in line.comments:
3289                 num_of_inline_string_comments += 1
3290                 if contains_pragma_comment(line.comments[id(leaf)]):
3291                     return TErr("Cannot merge strings which have pragma comments.")
3292
3293         if num_of_strings < 2:
3294             return TErr(
3295                 f"Not enough strings to merge (num_of_strings={num_of_strings})."
3296             )
3297
3298         if num_of_inline_string_comments > 1:
3299             return TErr(
3300                 f"Too many inline string comments ({num_of_inline_string_comments})."
3301             )
3302
3303         if len(set_of_prefixes) > 1 and set_of_prefixes != {"", "f"}:
3304             return TErr(f"Too many different prefixes ({set_of_prefixes}).")
3305
3306         return Ok(None)
3307
3308
3309 class StringParenStripper(StringTransformer):
3310     """StringTransformer that strips surrounding parentheses from strings.
3311
3312     Requirements:
3313         The line contains a string which is surrounded by parentheses and:
3314             - The target string is NOT the only argument to a function call.
3315             - The target string is NOT a "pointless" string.
3316             - If the target string contains a PERCENT, the brackets are not
3317               preceeded or followed by an operator with higher precedence than
3318               PERCENT.
3319
3320     Transformations:
3321         The parentheses mentioned in the 'Requirements' section are stripped.
3322
3323     Collaborations:
3324         StringParenStripper has its own inherent usefulness, but it is also
3325         relied on to clean up the parentheses created by StringParenWrapper (in
3326         the event that they are no longer needed).
3327     """
3328
3329     def do_match(self, line: Line) -> TMatchResult:
3330         LL = line.leaves
3331
3332         is_valid_index = is_valid_index_factory(LL)
3333
3334         for (idx, leaf) in enumerate(LL):
3335             # Should be a string...
3336             if leaf.type != token.STRING:
3337                 continue
3338
3339             # If this is a "pointless" string...
3340             if (
3341                 leaf.parent
3342                 and leaf.parent.parent
3343                 and leaf.parent.parent.type == syms.simple_stmt
3344             ):
3345                 continue
3346
3347             # Should be preceded by a non-empty LPAR...
3348             if (
3349                 not is_valid_index(idx - 1)
3350                 or LL[idx - 1].type != token.LPAR
3351                 or is_empty_lpar(LL[idx - 1])
3352             ):
3353                 continue
3354
3355             # That LPAR should NOT be preceded by a function name or a closing
3356             # bracket (which could be a function which returns a function or a
3357             # list/dictionary that contains a function)...
3358             if is_valid_index(idx - 2) and (
3359                 LL[idx - 2].type == token.NAME or LL[idx - 2].type in CLOSING_BRACKETS
3360             ):
3361                 continue
3362
3363             string_idx = idx
3364
3365             # Skip the string trailer, if one exists.
3366             string_parser = StringParser()
3367             next_idx = string_parser.parse(LL, string_idx)
3368
3369             # if the leaves in the parsed string include a PERCENT, we need to
3370             # make sure the initial LPAR is NOT preceded by an operator with
3371             # higher or equal precedence to PERCENT
3372             if is_valid_index(idx - 2):
3373                 # mypy can't quite follow unless we name this
3374                 before_lpar = LL[idx - 2]
3375                 if token.PERCENT in {leaf.type for leaf in LL[idx - 1 : next_idx]} and (
3376                     (
3377                         before_lpar.type
3378                         in {
3379                             token.STAR,
3380                             token.AT,
3381                             token.SLASH,
3382                             token.DOUBLESLASH,
3383                             token.PERCENT,
3384                             token.TILDE,
3385                             token.DOUBLESTAR,
3386                             token.AWAIT,
3387                             token.LSQB,
3388                             token.LPAR,
3389                         }
3390                     )
3391                     or (
3392                         # only unary PLUS/MINUS
3393                         before_lpar.parent
3394                         and before_lpar.parent.type == syms.factor
3395                         and (before_lpar.type in {token.PLUS, token.MINUS})
3396                     )
3397                 ):
3398                     continue
3399
3400             # Should be followed by a non-empty RPAR...
3401             if (
3402                 is_valid_index(next_idx)
3403                 and LL[next_idx].type == token.RPAR
3404                 and not is_empty_rpar(LL[next_idx])
3405             ):
3406                 # That RPAR should NOT be followed by anything with higher
3407                 # precedence than PERCENT
3408                 if is_valid_index(next_idx + 1) and LL[next_idx + 1].type in {
3409                     token.DOUBLESTAR,
3410                     token.LSQB,
3411                     token.LPAR,
3412                     token.DOT,
3413                 }:
3414                     continue
3415
3416                 return Ok(string_idx)
3417
3418         return TErr("This line has no strings wrapped in parens.")
3419
3420     def do_transform(self, line: Line, string_idx: int) -> Iterator[TResult[Line]]:
3421         LL = line.leaves
3422
3423         string_parser = StringParser()
3424         rpar_idx = string_parser.parse(LL, string_idx)
3425
3426         for leaf in (LL[string_idx - 1], LL[rpar_idx]):
3427             if line.comments_after(leaf):
3428                 yield TErr(
3429                     "Will not strip parentheses which have comments attached to them."
3430                 )
3431                 return
3432
3433         new_line = line.clone()
3434         new_line.comments = line.comments.copy()
3435         try:
3436             append_leaves(new_line, line, LL[: string_idx - 1])
3437         except BracketMatchError:
3438             # HACK: I believe there is currently a bug somewhere in
3439             # right_hand_split() that is causing brackets to not be tracked
3440             # properly by a shared BracketTracker.
3441             append_leaves(new_line, line, LL[: string_idx - 1], preformatted=True)
3442
3443         string_leaf = Leaf(token.STRING, LL[string_idx].value)
3444         LL[string_idx - 1].remove()
3445         replace_child(LL[string_idx], string_leaf)
3446         new_line.append(string_leaf)
3447
3448         append_leaves(
3449             new_line, line, LL[string_idx + 1 : rpar_idx] + LL[rpar_idx + 1 :]
3450         )
3451
3452         LL[rpar_idx].remove()
3453
3454         yield Ok(new_line)
3455
3456
3457 class BaseStringSplitter(StringTransformer):
3458     """
3459     Abstract class for StringTransformers which transform a Line's strings by splitting
3460     them or placing them on their own lines where necessary to avoid going over
3461     the configured line length.
3462
3463     Requirements:
3464         * The target string value is responsible for the line going over the
3465         line length limit. It follows that after all of black's other line
3466         split methods have been exhausted, this line (or one of the resulting
3467         lines after all line splits are performed) would still be over the
3468         line_length limit unless we split this string.
3469             AND
3470         * The target string is NOT a "pointless" string (i.e. a string that has
3471         no parent or siblings).
3472             AND
3473         * The target string is not followed by an inline comment that appears
3474         to be a pragma.
3475             AND
3476         * The target string is not a multiline (i.e. triple-quote) string.
3477     """
3478
3479     @abstractmethod
3480     def do_splitter_match(self, line: Line) -> TMatchResult:
3481         """
3482         BaseStringSplitter asks its clients to override this method instead of
3483         `StringTransformer.do_match(...)`.
3484
3485         Follows the same protocol as `StringTransformer.do_match(...)`.
3486
3487         Refer to `help(StringTransformer.do_match)` for more information.
3488         """
3489
3490     def do_match(self, line: Line) -> TMatchResult:
3491         match_result = self.do_splitter_match(line)
3492         if isinstance(match_result, Err):
3493             return match_result
3494
3495         string_idx = match_result.ok()
3496         vresult = self.__validate(line, string_idx)
3497         if isinstance(vresult, Err):
3498             return vresult
3499
3500         return match_result
3501
3502     def __validate(self, line: Line, string_idx: int) -> TResult[None]:
3503         """
3504         Checks that @line meets all of the requirements listed in this classes'
3505         docstring. Refer to `help(BaseStringSplitter)` for a detailed
3506         description of those requirements.
3507
3508         Returns:
3509             * Ok(None), if ALL of the requirements are met.
3510                 OR
3511             * Err(CannotTransform), if ANY of the requirements are NOT met.
3512         """
3513         LL = line.leaves
3514
3515         string_leaf = LL[string_idx]
3516
3517         max_string_length = self.__get_max_string_length(line, string_idx)
3518         if len(string_leaf.value) <= max_string_length:
3519             return TErr(
3520                 "The string itself is not what is causing this line to be too long."
3521             )
3522
3523         if not string_leaf.parent or [L.type for L in string_leaf.parent.children] == [
3524             token.STRING,
3525             token.NEWLINE,
3526         ]:
3527             return TErr(
3528                 f"This string ({string_leaf.value}) appears to be pointless (i.e. has"
3529                 " no parent)."
3530             )
3531
3532         if id(line.leaves[string_idx]) in line.comments and contains_pragma_comment(
3533             line.comments[id(line.leaves[string_idx])]
3534         ):
3535             return TErr(
3536                 "Line appears to end with an inline pragma comment. Splitting the line"
3537                 " could modify the pragma's behavior."
3538             )
3539
3540         if has_triple_quotes(string_leaf.value):
3541             return TErr("We cannot split multiline strings.")
3542
3543         return Ok(None)
3544
3545     def __get_max_string_length(self, line: Line, string_idx: int) -> int:
3546         """
3547         Calculates the max string length used when attempting to determine
3548         whether or not the target string is responsible for causing the line to
3549         go over the line length limit.
3550
3551         WARNING: This method is tightly coupled to both StringSplitter and
3552         (especially) StringParenWrapper. There is probably a better way to
3553         accomplish what is being done here.
3554
3555         Returns:
3556             max_string_length: such that `line.leaves[string_idx].value >
3557             max_string_length` implies that the target string IS responsible
3558             for causing this line to exceed the line length limit.
3559         """
3560         LL = line.leaves
3561
3562         is_valid_index = is_valid_index_factory(LL)
3563
3564         # We use the shorthand "WMA4" in comments to abbreviate "We must
3565         # account for". When giving examples, we use STRING to mean some/any
3566         # valid string.
3567         #
3568         # Finally, we use the following convenience variables:
3569         #
3570         #   P:  The leaf that is before the target string leaf.
3571         #   N:  The leaf that is after the target string leaf.
3572         #   NN: The leaf that is after N.
3573
3574         # WMA4 the whitespace at the beginning of the line.
3575         offset = line.depth * 4
3576
3577         if is_valid_index(string_idx - 1):
3578             p_idx = string_idx - 1
3579             if (
3580                 LL[string_idx - 1].type == token.LPAR
3581                 and LL[string_idx - 1].value == ""
3582                 and string_idx >= 2
3583             ):
3584                 # If the previous leaf is an empty LPAR placeholder, we should skip it.
3585                 p_idx -= 1
3586
3587             P = LL[p_idx]
3588             if P.type == token.PLUS:
3589                 # WMA4 a space and a '+' character (e.g. `+ STRING`).
3590                 offset += 2
3591
3592             if P.type == token.COMMA:
3593                 # WMA4 a space, a comma, and a closing bracket [e.g. `), STRING`].
3594                 offset += 3
3595
3596             if P.type in [token.COLON, token.EQUAL, token.NAME]:
3597                 # This conditional branch is meant to handle dictionary keys,
3598                 # variable assignments, 'return STRING' statement lines, and
3599                 # 'else STRING' ternary expression lines.
3600
3601                 # WMA4 a single space.
3602                 offset += 1
3603
3604                 # WMA4 the lengths of any leaves that came before that space,
3605                 # but after any closing bracket before that space.
3606                 for leaf in reversed(LL[: p_idx + 1]):
3607                     offset += len(str(leaf))
3608                     if leaf.type in CLOSING_BRACKETS:
3609                         break
3610
3611         if is_valid_index(string_idx + 1):
3612             N = LL[string_idx + 1]
3613             if N.type == token.RPAR and N.value == "" and len(LL) > string_idx + 2:
3614                 # If the next leaf is an empty RPAR placeholder, we should skip it.
3615                 N = LL[string_idx + 2]
3616
3617             if N.type == token.COMMA:
3618                 # WMA4 a single comma at the end of the string (e.g `STRING,`).
3619                 offset += 1
3620
3621             if is_valid_index(string_idx + 2):
3622                 NN = LL[string_idx + 2]
3623
3624                 if N.type == token.DOT and NN.type == token.NAME:
3625                     # This conditional branch is meant to handle method calls invoked
3626                     # off of a string literal up to and including the LPAR character.
3627
3628                     # WMA4 the '.' character.
3629                     offset += 1
3630
3631                     if (
3632                         is_valid_index(string_idx + 3)
3633                         and LL[string_idx + 3].type == token.LPAR
3634                     ):
3635                         # WMA4 the left parenthesis character.
3636                         offset += 1
3637
3638                     # WMA4 the length of the method's name.
3639                     offset += len(NN.value)
3640
3641         has_comments = False
3642         for comment_leaf in line.comments_after(LL[string_idx]):
3643             if not has_comments:
3644                 has_comments = True
3645                 # WMA4 two spaces before the '#' character.
3646                 offset += 2
3647
3648             # WMA4 the length of the inline comment.
3649             offset += len(comment_leaf.value)
3650
3651         max_string_length = self.line_length - offset
3652         return max_string_length
3653
3654
3655 class StringSplitter(CustomSplitMapMixin, BaseStringSplitter):
3656     """
3657     StringTransformer that splits "atom" strings (i.e. strings which exist on
3658     lines by themselves).
3659
3660     Requirements:
3661         * The line consists ONLY of a single string (with the exception of a
3662         '+' symbol which MAY exist at the start of the line), MAYBE a string
3663         trailer, and MAYBE a trailing comma.
3664             AND
3665         * All of the requirements listed in BaseStringSplitter's docstring.
3666
3667     Transformations:
3668         The string mentioned in the 'Requirements' section is split into as
3669         many substrings as necessary to adhere to the configured line length.
3670
3671         In the final set of substrings, no substring should be smaller than
3672         MIN_SUBSTR_SIZE characters.
3673
3674         The string will ONLY be split on spaces (i.e. each new substring should
3675         start with a space). Note that the string will NOT be split on a space
3676         which is escaped with a backslash.
3677
3678         If the string is an f-string, it will NOT be split in the middle of an
3679         f-expression (e.g. in f"FooBar: {foo() if x else bar()}", {foo() if x
3680         else bar()} is an f-expression).
3681
3682         If the string that is being split has an associated set of custom split
3683         records and those custom splits will NOT result in any line going over
3684         the configured line length, those custom splits are used. Otherwise the
3685         string is split as late as possible (from left-to-right) while still
3686         adhering to the transformation rules listed above.
3687
3688     Collaborations:
3689         StringSplitter relies on StringMerger to construct the appropriate
3690         CustomSplit objects and add them to the custom split map.
3691     """
3692
3693     MIN_SUBSTR_SIZE = 6
3694     # Matches an "f-expression" (e.g. {var}) that might be found in an f-string.
3695     RE_FEXPR = r"""
3696     (?<!\{) (?:\{\{)* \{ (?!\{)
3697         (?:
3698             [^\{\}]
3699             | \{\{
3700             | \}\}
3701             | (?R)
3702         )+?
3703     (?<!\}) \} (?:\}\})* (?!\})
3704     """
3705
3706     def do_splitter_match(self, line: Line) -> TMatchResult:
3707         LL = line.leaves
3708
3709         is_valid_index = is_valid_index_factory(LL)
3710
3711         idx = 0
3712
3713         # The first leaf MAY be a '+' symbol...
3714         if is_valid_index(idx) and LL[idx].type == token.PLUS:
3715             idx += 1
3716
3717         # The next/first leaf MAY be an empty LPAR...
3718         if is_valid_index(idx) and is_empty_lpar(LL[idx]):
3719             idx += 1
3720
3721         # The next/first leaf MUST be a string...
3722         if not is_valid_index(idx) or LL[idx].type != token.STRING:
3723             return TErr("Line does not start with a string.")
3724
3725         string_idx = idx
3726
3727         # Skip the string trailer, if one exists.
3728         string_parser = StringParser()
3729         idx = string_parser.parse(LL, string_idx)
3730
3731         # That string MAY be followed by an empty RPAR...
3732         if is_valid_index(idx) and is_empty_rpar(LL[idx]):
3733             idx += 1
3734
3735         # That string / empty RPAR leaf MAY be followed by a comma...
3736         if is_valid_index(idx) and LL[idx].type == token.COMMA:
3737             idx += 1
3738
3739         # But no more leaves are allowed...
3740         if is_valid_index(idx):
3741             return TErr("This line does not end with a string.")
3742
3743         return Ok(string_idx)
3744
3745     def do_transform(self, line: Line, string_idx: int) -> Iterator[TResult[Line]]:
3746         LL = line.leaves
3747
3748         QUOTE = LL[string_idx].value[-1]
3749
3750         is_valid_index = is_valid_index_factory(LL)
3751         insert_str_child = insert_str_child_factory(LL[string_idx])
3752
3753         prefix = get_string_prefix(LL[string_idx].value)
3754
3755         # We MAY choose to drop the 'f' prefix from substrings that don't
3756         # contain any f-expressions, but ONLY if the original f-string
3757         # contains at least one f-expression. Otherwise, we will alter the AST
3758         # of the program.
3759         drop_pointless_f_prefix = ("f" in prefix) and re.search(
3760             self.RE_FEXPR, LL[string_idx].value, re.VERBOSE
3761         )
3762
3763         first_string_line = True
3764         starts_with_plus = LL[0].type == token.PLUS
3765
3766         def line_needs_plus() -> bool:
3767             return first_string_line and starts_with_plus
3768
3769         def maybe_append_plus(new_line: Line) -> None:
3770             """
3771             Side Effects:
3772                 If @line starts with a plus and this is the first line we are
3773                 constructing, this function appends a PLUS leaf to @new_line
3774                 and replaces the old PLUS leaf in the node structure. Otherwise
3775                 this function does nothing.
3776             """
3777             if line_needs_plus():
3778                 plus_leaf = Leaf(token.PLUS, "+")
3779                 replace_child(LL[0], plus_leaf)
3780                 new_line.append(plus_leaf)
3781
3782         ends_with_comma = (
3783             is_valid_index(string_idx + 1) and LL[string_idx + 1].type == token.COMMA
3784         )
3785
3786         def max_last_string() -> int:
3787             """
3788             Returns:
3789                 The max allowed length of the string value used for the last
3790                 line we will construct.
3791             """
3792             result = self.line_length
3793             result -= line.depth * 4
3794             result -= 1 if ends_with_comma else 0
3795             result -= 2 if line_needs_plus() else 0
3796             return result
3797
3798         # --- Calculate Max Break Index (for string value)
3799         # We start with the line length limit
3800         max_break_idx = self.line_length
3801         # The last index of a string of length N is N-1.
3802         max_break_idx -= 1
3803         # Leading whitespace is not present in the string value (e.g. Leaf.value).
3804         max_break_idx -= line.depth * 4
3805         if max_break_idx < 0:
3806             yield TErr(
3807                 f"Unable to split {LL[string_idx].value} at such high of a line depth:"
3808                 f" {line.depth}"
3809             )
3810             return
3811
3812         # Check if StringMerger registered any custom splits.
3813         custom_splits = self.pop_custom_splits(LL[string_idx].value)
3814         # We use them ONLY if none of them would produce lines that exceed the
3815         # line limit.
3816         use_custom_breakpoints = bool(
3817             custom_splits
3818             and all(csplit.break_idx <= max_break_idx for csplit in custom_splits)
3819         )
3820
3821         # Temporary storage for the remaining chunk of the string line that
3822         # can't fit onto the line currently being constructed.
3823         rest_value = LL[string_idx].value
3824
3825         def more_splits_should_be_made() -> bool:
3826             """
3827             Returns:
3828                 True iff `rest_value` (the remaining string value from the last
3829                 split), should be split again.
3830             """
3831             if use_custom_breakpoints:
3832                 return len(custom_splits) > 1
3833             else:
3834                 return len(rest_value) > max_last_string()
3835
3836         string_line_results: List[Ok[Line]] = []
3837         while more_splits_should_be_made():
3838             if use_custom_breakpoints:
3839                 # Custom User Split (manual)
3840                 csplit = custom_splits.pop(0)
3841                 break_idx = csplit.break_idx
3842             else:
3843                 # Algorithmic Split (automatic)
3844                 max_bidx = max_break_idx - 2 if line_needs_plus() else max_break_idx
3845                 maybe_break_idx = self.__get_break_idx(rest_value, max_bidx)
3846                 if maybe_break_idx is None:
3847                     # If we are unable to algorithmically determine a good split
3848                     # and this string has custom splits registered to it, we
3849                     # fall back to using them--which means we have to start
3850                     # over from the beginning.
3851                     if custom_splits:
3852                         rest_value = LL[string_idx].value
3853                         string_line_results = []
3854                         first_string_line = True
3855                         use_custom_breakpoints = True
3856                         continue
3857
3858                     # Otherwise, we stop splitting here.
3859                     break
3860
3861                 break_idx = maybe_break_idx
3862
3863             # --- Construct `next_value`
3864             next_value = rest_value[:break_idx] + QUOTE
3865             if (
3866                 # Are we allowed to try to drop a pointless 'f' prefix?
3867                 drop_pointless_f_prefix
3868                 # If we are, will we be successful?
3869                 and next_value != self.__normalize_f_string(next_value, prefix)
3870             ):
3871                 # If the current custom split did NOT originally use a prefix,
3872                 # then `csplit.break_idx` will be off by one after removing
3873                 # the 'f' prefix.
3874                 break_idx = (
3875                     break_idx + 1
3876                     if use_custom_breakpoints and not csplit.has_prefix
3877                     else break_idx
3878                 )
3879                 next_value = rest_value[:break_idx] + QUOTE
3880                 next_value = self.__normalize_f_string(next_value, prefix)
3881
3882             # --- Construct `next_leaf`
3883             next_leaf = Leaf(token.STRING, next_value)
3884             insert_str_child(next_leaf)
3885             self.__maybe_normalize_string_quotes(next_leaf)
3886
3887             # --- Construct `next_line`
3888             next_line = line.clone()
3889             maybe_append_plus(next_line)
3890             next_line.append(next_leaf)
3891             string_line_results.append(Ok(next_line))
3892
3893             rest_value = prefix + QUOTE + rest_value[break_idx:]
3894             first_string_line = False
3895
3896         yield from string_line_results
3897
3898         if drop_pointless_f_prefix:
3899             rest_value = self.__normalize_f_string(rest_value, prefix)
3900
3901         rest_leaf = Leaf(token.STRING, rest_value)
3902         insert_str_child(rest_leaf)
3903
3904         # NOTE: I could not find a test case that verifies that the following
3905         # line is actually necessary, but it seems to be. Otherwise we risk
3906         # not normalizing the last substring, right?
3907         self.__maybe_normalize_string_quotes(rest_leaf)
3908
3909         last_line = line.clone()
3910         maybe_append_plus(last_line)
3911
3912         # If there are any leaves to the right of the target string...
3913         if is_valid_index(string_idx + 1):
3914             # We use `temp_value` here to determine how long the last line
3915             # would be if we were to append all the leaves to the right of the
3916             # target string to the last string line.
3917             temp_value = rest_value
3918             for leaf in LL[string_idx + 1 :]:
3919                 temp_value += str(leaf)
3920                 if leaf.type == token.LPAR:
3921                     break
3922
3923             # Try to fit them all on the same line with the last substring...
3924             if (
3925                 len(temp_value) <= max_last_string()
3926                 or LL[string_idx + 1].type == token.COMMA
3927             ):
3928                 last_line.append(rest_leaf)
3929                 append_leaves(last_line, line, LL[string_idx + 1 :])
3930                 yield Ok(last_line)
3931             # Otherwise, place the last substring on one line and everything
3932             # else on a line below that...
3933             else:
3934                 last_line.append(rest_leaf)
3935                 yield Ok(last_line)
3936
3937                 non_string_line = line.clone()
3938                 append_leaves(non_string_line, line, LL[string_idx + 1 :])
3939                 yield Ok(non_string_line)
3940         # Else the target string was the last leaf...
3941         else:
3942             last_line.append(rest_leaf)
3943             last_line.comments = line.comments.copy()
3944             yield Ok(last_line)
3945
3946     def __get_break_idx(self, string: str, max_break_idx: int) -> Optional[int]:
3947         """
3948         This method contains the algorithm that StringSplitter uses to
3949         determine which character to split each string at.
3950
3951         Args:
3952             @string: The substring that we are attempting to split.
3953             @max_break_idx: The ideal break index. We will return this value if it
3954             meets all the necessary conditions. In the likely event that it
3955             doesn't we will try to find the closest index BELOW @max_break_idx
3956             that does. If that fails, we will expand our search by also
3957             considering all valid indices ABOVE @max_break_idx.
3958
3959         Pre-Conditions:
3960             * assert_is_leaf_string(@string)
3961             * 0 <= @max_break_idx < len(@string)
3962
3963         Returns:
3964             break_idx, if an index is able to be found that meets all of the
3965             conditions listed in the 'Transformations' section of this classes'
3966             docstring.
3967                 OR
3968             None, otherwise.
3969         """
3970         is_valid_index = is_valid_index_factory(string)
3971
3972         assert is_valid_index(max_break_idx)
3973         assert_is_leaf_string(string)
3974
3975         _fexpr_slices: Optional[List[Tuple[Index, Index]]] = None
3976
3977         def fexpr_slices() -> Iterator[Tuple[Index, Index]]:
3978             """
3979             Yields:
3980                 All ranges of @string which, if @string were to be split there,
3981                 would result in the splitting of an f-expression (which is NOT
3982                 allowed).
3983             """
3984             nonlocal _fexpr_slices
3985
3986             if _fexpr_slices is None:
3987                 _fexpr_slices = []
3988                 for match in re.finditer(self.RE_FEXPR, string, re.VERBOSE):
3989                     _fexpr_slices.append(match.span())
3990
3991             yield from _fexpr_slices
3992
3993         is_fstring = "f" in get_string_prefix(string)
3994
3995         def breaks_fstring_expression(i: Index) -> bool:
3996             """
3997             Returns:
3998                 True iff returning @i would result in the splitting of an
3999                 f-expression (which is NOT allowed).
4000             """
4001             if not is_fstring:
4002                 return False
4003
4004             for (start, end) in fexpr_slices():
4005                 if start <= i < end:
4006                     return True
4007
4008             return False
4009
4010         def passes_all_checks(i: Index) -> bool:
4011             """
4012             Returns:
4013                 True iff ALL of the conditions listed in the 'Transformations'
4014                 section of this classes' docstring would be be met by returning @i.
4015             """
4016             is_space = string[i] == " "
4017
4018             is_not_escaped = True
4019             j = i - 1
4020             while is_valid_index(j) and string[j] == "\\":
4021                 is_not_escaped = not is_not_escaped
4022                 j -= 1
4023
4024             is_big_enough = (
4025                 len(string[i:]) >= self.MIN_SUBSTR_SIZE
4026                 and len(string[:i]) >= self.MIN_SUBSTR_SIZE
4027             )
4028             return (
4029                 is_space
4030                 and is_not_escaped
4031                 and is_big_enough
4032                 and not breaks_fstring_expression(i)
4033             )
4034
4035         # First, we check all indices BELOW @max_break_idx.
4036         break_idx = max_break_idx
4037         while is_valid_index(break_idx - 1) and not passes_all_checks(break_idx):
4038             break_idx -= 1
4039
4040         if not passes_all_checks(break_idx):
4041             # If that fails, we check all indices ABOVE @max_break_idx.
4042             #
4043             # If we are able to find a valid index here, the next line is going
4044             # to be longer than the specified line length, but it's probably
4045             # better than doing nothing at all.
4046             break_idx = max_break_idx + 1
4047             while is_valid_index(break_idx + 1) and not passes_all_checks(break_idx):
4048                 break_idx += 1
4049
4050             if not is_valid_index(break_idx) or not passes_all_checks(break_idx):
4051                 return None
4052
4053         return break_idx
4054
4055     def __maybe_normalize_string_quotes(self, leaf: Leaf) -> None:
4056         if self.normalize_strings:
4057             normalize_string_quotes(leaf)
4058
4059     def __normalize_f_string(self, string: str, prefix: str) -> str:
4060         """
4061         Pre-Conditions:
4062             * assert_is_leaf_string(@string)
4063
4064         Returns:
4065             * If @string is an f-string that contains no f-expressions, we
4066             return a string identical to @string except that the 'f' prefix
4067             has been stripped and all double braces (i.e. '{{' or '}}') have
4068             been normalized (i.e. turned into '{' or '}').
4069                 OR
4070             * Otherwise, we return @string.
4071         """
4072         assert_is_leaf_string(string)
4073
4074         if "f" in prefix and not re.search(self.RE_FEXPR, string, re.VERBOSE):
4075             new_prefix = prefix.replace("f", "")
4076
4077             temp = string[len(prefix) :]
4078             temp = re.sub(r"\{\{", "{", temp)
4079             temp = re.sub(r"\}\}", "}", temp)
4080             new_string = temp
4081
4082             return f"{new_prefix}{new_string}"
4083         else:
4084             return string
4085
4086
4087 class StringParenWrapper(CustomSplitMapMixin, BaseStringSplitter):
4088     """
4089     StringTransformer that splits non-"atom" strings (i.e. strings that do not
4090     exist on lines by themselves).
4091
4092     Requirements:
4093         All of the requirements listed in BaseStringSplitter's docstring in
4094         addition to the requirements listed below:
4095
4096         * The line is a return/yield statement, which returns/yields a string.
4097             OR
4098         * The line is part of a ternary expression (e.g. `x = y if cond else
4099         z`) such that the line starts with `else <string>`, where <string> is
4100         some string.
4101             OR
4102         * The line is an assert statement, which ends with a string.
4103             OR
4104         * The line is an assignment statement (e.g. `x = <string>` or `x +=
4105         <string>`) such that the variable is being assigned the value of some
4106         string.
4107             OR
4108         * The line is a dictionary key assignment where some valid key is being
4109         assigned the value of some string.
4110
4111     Transformations:
4112         The chosen string is wrapped in parentheses and then split at the LPAR.
4113
4114         We then have one line which ends with an LPAR and another line that
4115         starts with the chosen string. The latter line is then split again at
4116         the RPAR. This results in the RPAR (and possibly a trailing comma)
4117         being placed on its own line.
4118
4119         NOTE: If any leaves exist to the right of the chosen string (except
4120         for a trailing comma, which would be placed after the RPAR), those
4121         leaves are placed inside the parentheses.  In effect, the chosen
4122         string is not necessarily being "wrapped" by parentheses. We can,
4123         however, count on the LPAR being placed directly before the chosen
4124         string.
4125
4126         In other words, StringParenWrapper creates "atom" strings. These
4127         can then be split again by StringSplitter, if necessary.
4128
4129     Collaborations:
4130         In the event that a string line split by StringParenWrapper is
4131         changed such that it no longer needs to be given its own line,
4132         StringParenWrapper relies on StringParenStripper to clean up the
4133         parentheses it created.
4134     """
4135
4136     def do_splitter_match(self, line: Line) -> TMatchResult:
4137         LL = line.leaves
4138
4139         string_idx = (
4140             self._return_match(LL)
4141             or self._else_match(LL)
4142             or self._assert_match(LL)
4143             or self._assign_match(LL)
4144             or self._dict_match(LL)
4145         )
4146
4147         if string_idx is not None:
4148             string_value = line.leaves[string_idx].value
4149             # If the string has no spaces...
4150             if " " not in string_value:
4151                 # And will still violate the line length limit when split...
4152                 max_string_length = self.line_length - ((line.depth + 1) * 4)
4153                 if len(string_value) > max_string_length:
4154                     # And has no associated custom splits...
4155                     if not self.has_custom_splits(string_value):
4156                         # Then we should NOT put this string on its own line.
4157                         return TErr(
4158                             "We do not wrap long strings in parentheses when the"
4159                             " resultant line would still be over the specified line"
4160                             " length and can't be split further by StringSplitter."
4161                         )
4162             return Ok(string_idx)
4163
4164         return TErr("This line does not contain any non-atomic strings.")
4165
4166     @staticmethod
4167     def _return_match(LL: List[Leaf]) -> Optional[int]:
4168         """
4169         Returns:
4170             string_idx such that @LL[string_idx] is equal to our target (i.e.
4171             matched) string, if this line matches the return/yield statement
4172             requirements listed in the 'Requirements' section of this classes'
4173             docstring.
4174                 OR
4175             None, otherwise.
4176         """
4177         # If this line is apart of a return/yield statement and the first leaf
4178         # contains either the "return" or "yield" keywords...
4179         if parent_type(LL[0]) in [syms.return_stmt, syms.yield_expr] and LL[
4180             0
4181         ].value in ["return", "yield"]:
4182             is_valid_index = is_valid_index_factory(LL)
4183
4184             idx = 2 if is_valid_index(1) and is_empty_par(LL[1]) else 1
4185             # The next visible leaf MUST contain a string...
4186             if is_valid_index(idx) and LL[idx].type == token.STRING:
4187                 return idx
4188
4189         return None
4190
4191     @staticmethod
4192     def _else_match(LL: List[Leaf]) -> Optional[int]:
4193         """
4194         Returns:
4195             string_idx such that @LL[string_idx] is equal to our target (i.e.
4196             matched) string, if this line matches the ternary expression
4197             requirements listed in the 'Requirements' section of this classes'
4198             docstring.
4199                 OR
4200             None, otherwise.
4201         """
4202         # If this line is apart of a ternary expression and the first leaf
4203         # contains the "else" keyword...
4204         if (
4205             parent_type(LL[0]) == syms.test
4206             and LL[0].type == token.NAME
4207             and LL[0].value == "else"
4208         ):
4209             is_valid_index = is_valid_index_factory(LL)
4210
4211             idx = 2 if is_valid_index(1) and is_empty_par(LL[1]) else 1
4212             # The next visible leaf MUST contain a string...
4213             if is_valid_index(idx) and LL[idx].type == token.STRING:
4214                 return idx
4215
4216         return None
4217
4218     @staticmethod
4219     def _assert_match(LL: List[Leaf]) -> Optional[int]:
4220         """
4221         Returns:
4222             string_idx such that @LL[string_idx] is equal to our target (i.e.
4223             matched) string, if this line matches the assert statement
4224             requirements listed in the 'Requirements' section of this classes'
4225             docstring.
4226                 OR
4227             None, otherwise.
4228         """
4229         # If this line is apart of an assert statement and the first leaf
4230         # contains the "assert" keyword...
4231         if parent_type(LL[0]) == syms.assert_stmt and LL[0].value == "assert":
4232             is_valid_index = is_valid_index_factory(LL)
4233
4234             for (i, leaf) in enumerate(LL):
4235                 # We MUST find a comma...
4236                 if leaf.type == token.COMMA:
4237                     idx = i + 2 if is_empty_par(LL[i + 1]) else i + 1
4238
4239                     # That comma MUST be followed by a string...
4240                     if is_valid_index(idx) and LL[idx].type == token.STRING:
4241                         string_idx = idx
4242
4243                         # Skip the string trailer, if one exists.
4244                         string_parser = StringParser()
4245                         idx = string_parser.parse(LL, string_idx)
4246
4247                         # But no more leaves are allowed...
4248                         if not is_valid_index(idx):
4249                             return string_idx
4250
4251         return None
4252
4253     @staticmethod
4254     def _assign_match(LL: List[Leaf]) -> Optional[int]:
4255         """
4256         Returns:
4257             string_idx such that @LL[string_idx] is equal to our target (i.e.
4258             matched) string, if this line matches the assignment statement
4259             requirements listed in the 'Requirements' section of this classes'
4260             docstring.
4261                 OR
4262             None, otherwise.
4263         """
4264         # If this line is apart of an expression statement or is a function
4265         # argument AND the first leaf contains a variable name...
4266         if (
4267             parent_type(LL[0]) in [syms.expr_stmt, syms.argument, syms.power]
4268             and LL[0].type == token.NAME
4269         ):
4270             is_valid_index = is_valid_index_factory(LL)
4271
4272             for (i, leaf) in enumerate(LL):
4273                 # We MUST find either an '=' or '+=' symbol...
4274                 if leaf.type in [token.EQUAL, token.PLUSEQUAL]:
4275                     idx = i + 2 if is_empty_par(LL[i + 1]) else i + 1
4276
4277                     # That symbol MUST be followed by a string...
4278                     if is_valid_index(idx) and LL[idx].type == token.STRING:
4279                         string_idx = idx
4280
4281                         # Skip the string trailer, if one exists.
4282                         string_parser = StringParser()
4283                         idx = string_parser.parse(LL, string_idx)
4284
4285                         # The next leaf MAY be a comma iff this line is apart
4286                         # of a function argument...
4287                         if (
4288                             parent_type(LL[0]) == syms.argument
4289                             and is_valid_index(idx)
4290                             and LL[idx].type == token.COMMA
4291                         ):
4292                             idx += 1
4293
4294                         # But no more leaves are allowed...
4295                         if not is_valid_index(idx):
4296                             return string_idx
4297
4298         return None
4299
4300     @staticmethod
4301     def _dict_match(LL: List[Leaf]) -> Optional[int]:
4302         """
4303         Returns:
4304             string_idx such that @LL[string_idx] is equal to our target (i.e.
4305             matched) string, if this line matches the dictionary key assignment
4306             statement requirements listed in the 'Requirements' section of this
4307             classes' docstring.
4308                 OR
4309             None, otherwise.
4310         """
4311         # If this line is apart of a dictionary key assignment...
4312         if syms.dictsetmaker in [parent_type(LL[0]), parent_type(LL[0].parent)]:
4313             is_valid_index = is_valid_index_factory(LL)
4314
4315             for (i, leaf) in enumerate(LL):
4316                 # We MUST find a colon...
4317                 if leaf.type == token.COLON:
4318                     idx = i + 2 if is_empty_par(LL[i + 1]) else i + 1
4319
4320                     # That colon MUST be followed by a string...
4321                     if is_valid_index(idx) and LL[idx].type == token.STRING:
4322                         string_idx = idx
4323
4324                         # Skip the string trailer, if one exists.
4325                         string_parser = StringParser()
4326                         idx = string_parser.parse(LL, string_idx)
4327
4328                         # That string MAY be followed by a comma...
4329                         if is_valid_index(idx) and LL[idx].type == token.COMMA:
4330                             idx += 1
4331
4332                         # But no more leaves are allowed...
4333                         if not is_valid_index(idx):
4334                             return string_idx
4335
4336         return None
4337
4338     def do_transform(self, line: Line, string_idx: int) -> Iterator[TResult[Line]]:
4339         LL = line.leaves
4340
4341         is_valid_index = is_valid_index_factory(LL)
4342         insert_str_child = insert_str_child_factory(LL[string_idx])
4343
4344         comma_idx = -1
4345         ends_with_comma = False
4346         if LL[comma_idx].type == token.COMMA:
4347             ends_with_comma = True
4348
4349         leaves_to_steal_comments_from = [LL[string_idx]]
4350         if ends_with_comma:
4351             leaves_to_steal_comments_from.append(LL[comma_idx])
4352
4353         # --- First Line
4354         first_line = line.clone()
4355         left_leaves = LL[:string_idx]
4356
4357         # We have to remember to account for (possibly invisible) LPAR and RPAR
4358         # leaves that already wrapped the target string. If these leaves do
4359         # exist, we will replace them with our own LPAR and RPAR leaves.
4360         old_parens_exist = False
4361         if left_leaves and left_leaves[-1].type == token.LPAR:
4362             old_parens_exist = True
4363             leaves_to_steal_comments_from.append(left_leaves[-1])
4364             left_leaves.pop()
4365
4366         append_leaves(first_line, line, left_leaves)
4367
4368         lpar_leaf = Leaf(token.LPAR, "(")
4369         if old_parens_exist:
4370             replace_child(LL[string_idx - 1], lpar_leaf)
4371         else:
4372             insert_str_child(lpar_leaf)
4373         first_line.append(lpar_leaf)
4374
4375         # We throw inline comments that were originally to the right of the
4376         # target string to the top line. They will now be shown to the right of
4377         # the LPAR.
4378         for leaf in leaves_to_steal_comments_from:
4379             for comment_leaf in line.comments_after(leaf):
4380                 first_line.append(comment_leaf, preformatted=True)
4381
4382         yield Ok(first_line)
4383
4384         # --- Middle (String) Line
4385         # We only need to yield one (possibly too long) string line, since the
4386         # `StringSplitter` will break it down further if necessary.
4387         string_value = LL[string_idx].value
4388         string_line = Line(
4389             mode=line.mode,
4390             depth=line.depth + 1,
4391             inside_brackets=True,
4392             should_split_rhs=line.should_split_rhs,
4393             magic_trailing_comma=line.magic_trailing_comma,
4394         )
4395         string_leaf = Leaf(token.STRING, string_value)
4396         insert_str_child(string_leaf)
4397         string_line.append(string_leaf)
4398
4399         old_rpar_leaf = None
4400         if is_valid_index(string_idx + 1):
4401             right_leaves = LL[string_idx + 1 :]
4402             if ends_with_comma:
4403                 right_leaves.pop()
4404
4405             if old_parens_exist:
4406                 assert (
4407                     right_leaves and right_leaves[-1].type == token.RPAR
4408                 ), "Apparently, old parentheses do NOT exist?!"
4409                 old_rpar_leaf = right_leaves.pop()
4410
4411             append_leaves(string_line, line, right_leaves)
4412
4413         yield Ok(string_line)
4414
4415         # --- Last Line
4416         last_line = line.clone()
4417         last_line.bracket_tracker = first_line.bracket_tracker
4418
4419         new_rpar_leaf = Leaf(token.RPAR, ")")
4420         if old_rpar_leaf is not None:
4421             replace_child(old_rpar_leaf, new_rpar_leaf)
4422         else:
4423             insert_str_child(new_rpar_leaf)
4424         last_line.append(new_rpar_leaf)
4425
4426         # If the target string ended with a comma, we place this comma to the
4427         # right of the RPAR on the last line.
4428         if ends_with_comma:
4429             comma_leaf = Leaf(token.COMMA, ",")
4430             replace_child(LL[comma_idx], comma_leaf)
4431             last_line.append(comma_leaf)
4432
4433         yield Ok(last_line)
4434
4435
4436 class StringParser:
4437     """
4438     A state machine that aids in parsing a string's "trailer", which can be
4439     either non-existent, an old-style formatting sequence (e.g. `% varX` or `%
4440     (varX, varY)`), or a method-call / attribute access (e.g. `.format(varX,
4441     varY)`).
4442
4443     NOTE: A new StringParser object MUST be instantiated for each string
4444     trailer we need to parse.
4445
4446     Examples:
4447         We shall assume that `line` equals the `Line` object that corresponds
4448         to the following line of python code:
4449         ```
4450         x = "Some {}.".format("String") + some_other_string
4451         ```
4452
4453         Furthermore, we will assume that `string_idx` is some index such that:
4454         ```
4455         assert line.leaves[string_idx].value == "Some {}."
4456         ```
4457
4458         The following code snippet then holds:
4459         ```
4460         string_parser = StringParser()
4461         idx = string_parser.parse(line.leaves, string_idx)
4462         assert line.leaves[idx].type == token.PLUS
4463         ```
4464     """
4465
4466     DEFAULT_TOKEN = -1
4467
4468     # String Parser States
4469     START = 1
4470     DOT = 2
4471     NAME = 3
4472     PERCENT = 4
4473     SINGLE_FMT_ARG = 5
4474     LPAR = 6
4475     RPAR = 7
4476     DONE = 8
4477
4478     # Lookup Table for Next State
4479     _goto: Dict[Tuple[ParserState, NodeType], ParserState] = {
4480         # A string trailer may start with '.' OR '%'.
4481         (START, token.DOT): DOT,
4482         (START, token.PERCENT): PERCENT,
4483         (START, DEFAULT_TOKEN): DONE,
4484         # A '.' MUST be followed by an attribute or method name.
4485         (DOT, token.NAME): NAME,
4486         # A method name MUST be followed by an '(', whereas an attribute name
4487         # is the last symbol in the string trailer.
4488         (NAME, token.LPAR): LPAR,
4489         (NAME, DEFAULT_TOKEN): DONE,
4490         # A '%' symbol can be followed by an '(' or a single argument (e.g. a
4491         # string or variable name).
4492         (PERCENT, token.LPAR): LPAR,
4493         (PERCENT, DEFAULT_TOKEN): SINGLE_FMT_ARG,
4494         # If a '%' symbol is followed by a single argument, that argument is
4495         # the last leaf in the string trailer.
4496         (SINGLE_FMT_ARG, DEFAULT_TOKEN): DONE,
4497         # If present, a ')' symbol is the last symbol in a string trailer.
4498         # (NOTE: LPARS and nested RPARS are not included in this lookup table,
4499         # since they are treated as a special case by the parsing logic in this
4500         # classes' implementation.)
4501         (RPAR, DEFAULT_TOKEN): DONE,
4502     }
4503
4504     def __init__(self) -> None:
4505         self._state = self.START
4506         self._unmatched_lpars = 0
4507
4508     def parse(self, leaves: List[Leaf], string_idx: int) -> int:
4509         """
4510         Pre-conditions:
4511             * @leaves[@string_idx].type == token.STRING
4512
4513         Returns:
4514             The index directly after the last leaf which is apart of the string
4515             trailer, if a "trailer" exists.
4516                 OR
4517             @string_idx + 1, if no string "trailer" exists.
4518         """
4519         assert leaves[string_idx].type == token.STRING
4520
4521         idx = string_idx + 1
4522         while idx < len(leaves) and self._next_state(leaves[idx]):
4523             idx += 1
4524         return idx
4525
4526     def _next_state(self, leaf: Leaf) -> bool:
4527         """
4528         Pre-conditions:
4529             * On the first call to this function, @leaf MUST be the leaf that
4530             was directly after the string leaf in question (e.g. if our target
4531             string is `line.leaves[i]` then the first call to this method must
4532             be `line.leaves[i + 1]`).
4533             * On the next call to this function, the leaf parameter passed in
4534             MUST be the leaf directly following @leaf.
4535
4536         Returns:
4537             True iff @leaf is apart of the string's trailer.
4538         """
4539         # We ignore empty LPAR or RPAR leaves.
4540         if is_empty_par(leaf):
4541             return True
4542
4543         next_token = leaf.type
4544         if next_token == token.LPAR:
4545             self._unmatched_lpars += 1
4546
4547         current_state = self._state
4548
4549         # The LPAR parser state is a special case. We will return True until we
4550         # find the matching RPAR token.
4551         if current_state == self.LPAR:
4552             if next_token == token.RPAR:
4553                 self._unmatched_lpars -= 1
4554                 if self._unmatched_lpars == 0:
4555                     self._state = self.RPAR
4556         # Otherwise, we use a lookup table to determine the next state.
4557         else:
4558             # If the lookup table matches the current state to the next
4559             # token, we use the lookup table.
4560             if (current_state, next_token) in self._goto:
4561                 self._state = self._goto[current_state, next_token]
4562             else:
4563                 # Otherwise, we check if a the current state was assigned a
4564                 # default.
4565                 if (current_state, self.DEFAULT_TOKEN) in self._goto:
4566                     self._state = self._goto[current_state, self.DEFAULT_TOKEN]
4567                 # If no default has been assigned, then this parser has a logic
4568                 # error.
4569                 else:
4570                     raise RuntimeError(f"{self.__class__.__name__} LOGIC ERROR!")
4571
4572             if self._state == self.DONE:
4573                 return False
4574
4575         return True
4576
4577
4578 def TErr(err_msg: str) -> Err[CannotTransform]:
4579     """(T)ransform Err
4580
4581     Convenience function used when working with the TResult type.
4582     """
4583     cant_transform = CannotTransform(err_msg)
4584     return Err(cant_transform)
4585
4586
4587 def contains_pragma_comment(comment_list: List[Leaf]) -> bool:
4588     """
4589     Returns:
4590         True iff one of the comments in @comment_list is a pragma used by one
4591         of the more common static analysis tools for python (e.g. mypy, flake8,
4592         pylint).
4593     """
4594     for comment in comment_list:
4595         if comment.value.startswith(("# type:", "# noqa", "# pylint:")):
4596             return True
4597
4598     return False
4599
4600
4601 def insert_str_child_factory(string_leaf: Leaf) -> Callable[[LN], None]:
4602     """
4603     Factory for a convenience function that is used to orphan @string_leaf
4604     and then insert multiple new leaves into the same part of the node
4605     structure that @string_leaf had originally occupied.
4606
4607     Examples:
4608         Let `string_leaf = Leaf(token.STRING, '"foo"')` and `N =
4609         string_leaf.parent`. Assume the node `N` has the following
4610         original structure:
4611
4612         Node(
4613             expr_stmt, [
4614                 Leaf(NAME, 'x'),
4615                 Leaf(EQUAL, '='),
4616                 Leaf(STRING, '"foo"'),
4617             ]
4618         )
4619
4620         We then run the code snippet shown below.
4621         ```
4622         insert_str_child = insert_str_child_factory(string_leaf)
4623
4624         lpar = Leaf(token.LPAR, '(')
4625         insert_str_child(lpar)
4626
4627         bar = Leaf(token.STRING, '"bar"')
4628         insert_str_child(bar)
4629
4630         rpar = Leaf(token.RPAR, ')')
4631         insert_str_child(rpar)
4632         ```
4633
4634         After which point, it follows that `string_leaf.parent is None` and
4635         the node `N` now has the following structure:
4636
4637         Node(
4638             expr_stmt, [
4639                 Leaf(NAME, 'x'),
4640                 Leaf(EQUAL, '='),
4641                 Leaf(LPAR, '('),
4642                 Leaf(STRING, '"bar"'),
4643                 Leaf(RPAR, ')'),
4644             ]
4645         )
4646     """
4647     string_parent = string_leaf.parent
4648     string_child_idx = string_leaf.remove()
4649
4650     def insert_str_child(child: LN) -> None:
4651         nonlocal string_child_idx
4652
4653         assert string_parent is not None
4654         assert string_child_idx is not None
4655
4656         string_parent.insert_child(string_child_idx, child)
4657         string_child_idx += 1
4658
4659     return insert_str_child
4660
4661
4662 def has_triple_quotes(string: str) -> bool:
4663     """
4664     Returns:
4665         True iff @string starts with three quotation characters.
4666     """
4667     raw_string = string.lstrip(STRING_PREFIX_CHARS)
4668     return raw_string[:3] in {'"""', "'''"}
4669
4670
4671 def parent_type(node: Optional[LN]) -> Optional[NodeType]:
4672     """
4673     Returns:
4674         @node.parent.type, if @node is not None and has a parent.
4675             OR
4676         None, otherwise.
4677     """
4678     if node is None or node.parent is None:
4679         return None
4680
4681     return node.parent.type
4682
4683
4684 def is_empty_par(leaf: Leaf) -> bool:
4685     return is_empty_lpar(leaf) or is_empty_rpar(leaf)
4686
4687
4688 def is_empty_lpar(leaf: Leaf) -> bool:
4689     return leaf.type == token.LPAR and leaf.value == ""
4690
4691
4692 def is_empty_rpar(leaf: Leaf) -> bool:
4693     return leaf.type == token.RPAR and leaf.value == ""
4694
4695
4696 def is_valid_index_factory(seq: Sequence[Any]) -> Callable[[int], bool]:
4697     """
4698     Examples:
4699         ```
4700         my_list = [1, 2, 3]
4701
4702         is_valid_index = is_valid_index_factory(my_list)
4703
4704         assert is_valid_index(0)
4705         assert is_valid_index(2)
4706
4707         assert not is_valid_index(3)
4708         assert not is_valid_index(-1)
4709         ```
4710     """
4711
4712     def is_valid_index(idx: int) -> bool:
4713         """
4714         Returns:
4715             True iff @idx is positive AND seq[@idx] does NOT raise an
4716             IndexError.
4717         """
4718         return 0 <= idx < len(seq)
4719
4720     return is_valid_index
4721
4722
4723 def line_to_string(line: Line) -> str:
4724     """Returns the string representation of @line.
4725
4726     WARNING: This is known to be computationally expensive.
4727     """
4728     return str(line).strip("\n")
4729
4730
4731 def append_leaves(
4732     new_line: Line, old_line: Line, leaves: List[Leaf], preformatted: bool = False
4733 ) -> None:
4734     """
4735     Append leaves (taken from @old_line) to @new_line, making sure to fix the
4736     underlying Node structure where appropriate.
4737
4738     All of the leaves in @leaves are duplicated. The duplicates are then
4739     appended to @new_line and used to replace their originals in the underlying
4740     Node structure. Any comments attached to the old leaves are reattached to
4741     the new leaves.
4742
4743     Pre-conditions:
4744         set(@leaves) is a subset of set(@old_line.leaves).
4745     """
4746     for old_leaf in leaves:
4747         new_leaf = Leaf(old_leaf.type, old_leaf.value)
4748         replace_child(old_leaf, new_leaf)
4749         new_line.append(new_leaf, preformatted=preformatted)
4750
4751         for comment_leaf in old_line.comments_after(old_leaf):
4752             new_line.append(comment_leaf, preformatted=True)
4753
4754
4755 def replace_child(old_child: LN, new_child: LN) -> None:
4756     """
4757     Side Effects:
4758         * If @old_child.parent is set, replace @old_child with @new_child in
4759         @old_child's underlying Node structure.
4760             OR
4761         * Otherwise, this function does nothing.
4762     """
4763     parent = old_child.parent
4764     if not parent:
4765         return
4766
4767     child_idx = old_child.remove()
4768     if child_idx is not None:
4769         parent.insert_child(child_idx, new_child)
4770
4771
4772 def get_string_prefix(string: str) -> str:
4773     """
4774     Pre-conditions:
4775         * assert_is_leaf_string(@string)
4776
4777     Returns:
4778         @string's prefix (e.g. '', 'r', 'f', or 'rf').
4779     """
4780     assert_is_leaf_string(string)
4781
4782     prefix = ""
4783     prefix_idx = 0
4784     while string[prefix_idx] in STRING_PREFIX_CHARS:
4785         prefix += string[prefix_idx].lower()
4786         prefix_idx += 1
4787
4788     return prefix
4789
4790
4791 def assert_is_leaf_string(string: str) -> None:
4792     """
4793     Checks the pre-condition that @string has the format that you would expect
4794     of `leaf.value` where `leaf` is some Leaf such that `leaf.type ==
4795     token.STRING`. A more precise description of the pre-conditions that are
4796     checked are listed below.
4797
4798     Pre-conditions:
4799         * @string starts with either ', ", <prefix>', or <prefix>" where
4800         `set(<prefix>)` is some subset of `set(STRING_PREFIX_CHARS)`.
4801         * @string ends with a quote character (' or ").
4802
4803     Raises:
4804         AssertionError(...) if the pre-conditions listed above are not
4805         satisfied.
4806     """
4807     dquote_idx = string.find('"')
4808     squote_idx = string.find("'")
4809     if -1 in [dquote_idx, squote_idx]:
4810         quote_idx = max(dquote_idx, squote_idx)
4811     else:
4812         quote_idx = min(squote_idx, dquote_idx)
4813
4814     assert (
4815         0 <= quote_idx < len(string) - 1
4816     ), f"{string!r} is missing a starting quote character (' or \")."
4817     assert string[-1] in (
4818         "'",
4819         '"',
4820     ), f"{string!r} is missing an ending quote character (' or \")."
4821     assert set(string[:quote_idx]).issubset(
4822         set(STRING_PREFIX_CHARS)
4823     ), f"{set(string[:quote_idx])} is NOT a subset of {set(STRING_PREFIX_CHARS)}."
4824
4825
4826 def left_hand_split(line: Line, _features: Collection[Feature] = ()) -> Iterator[Line]:
4827     """Split line into many lines, starting with the first matching bracket pair.
4828
4829     Note: this usually looks weird, only use this for function definitions.
4830     Prefer RHS otherwise.  This is why this function is not symmetrical with
4831     :func:`right_hand_split` which also handles optional parentheses.
4832     """
4833     tail_leaves: List[Leaf] = []
4834     body_leaves: List[Leaf] = []
4835     head_leaves: List[Leaf] = []
4836     current_leaves = head_leaves
4837     matching_bracket: Optional[Leaf] = None
4838     for leaf in line.leaves:
4839         if (
4840             current_leaves is body_leaves
4841             and leaf.type in CLOSING_BRACKETS
4842             and leaf.opening_bracket is matching_bracket
4843         ):
4844             current_leaves = tail_leaves if body_leaves else head_leaves
4845         current_leaves.append(leaf)
4846         if current_leaves is head_leaves:
4847             if leaf.type in OPENING_BRACKETS:
4848                 matching_bracket = leaf
4849                 current_leaves = body_leaves
4850     if not matching_bracket:
4851         raise CannotSplit("No brackets found")
4852
4853     head = bracket_split_build_line(head_leaves, line, matching_bracket)
4854     body = bracket_split_build_line(body_leaves, line, matching_bracket, is_body=True)
4855     tail = bracket_split_build_line(tail_leaves, line, matching_bracket)
4856     bracket_split_succeeded_or_raise(head, body, tail)
4857     for result in (head, body, tail):
4858         if result:
4859             yield result
4860
4861
4862 def right_hand_split(
4863     line: Line,
4864     line_length: int,
4865     features: Collection[Feature] = (),
4866     omit: Collection[LeafID] = (),
4867 ) -> Iterator[Line]:
4868     """Split line into many lines, starting with the last matching bracket pair.
4869
4870     If the split was by optional parentheses, attempt splitting without them, too.
4871     `omit` is a collection of closing bracket IDs that shouldn't be considered for
4872     this split.
4873
4874     Note: running this function modifies `bracket_depth` on the leaves of `line`.
4875     """
4876     tail_leaves: List[Leaf] = []
4877     body_leaves: List[Leaf] = []
4878     head_leaves: List[Leaf] = []
4879     current_leaves = tail_leaves
4880     opening_bracket: Optional[Leaf] = None
4881     closing_bracket: Optional[Leaf] = None
4882     for leaf in reversed(line.leaves):
4883         if current_leaves is body_leaves:
4884             if leaf is opening_bracket:
4885                 current_leaves = head_leaves if body_leaves else tail_leaves
4886         current_leaves.append(leaf)
4887         if current_leaves is tail_leaves:
4888             if leaf.type in CLOSING_BRACKETS and id(leaf) not in omit:
4889                 opening_bracket = leaf.opening_bracket
4890                 closing_bracket = leaf
4891                 current_leaves = body_leaves
4892     if not (opening_bracket and closing_bracket and head_leaves):
4893         # If there is no opening or closing_bracket that means the split failed and
4894         # all content is in the tail.  Otherwise, if `head_leaves` are empty, it means
4895         # the matching `opening_bracket` wasn't available on `line` anymore.
4896         raise CannotSplit("No brackets found")
4897
4898     tail_leaves.reverse()
4899     body_leaves.reverse()
4900     head_leaves.reverse()
4901     head = bracket_split_build_line(head_leaves, line, opening_bracket)
4902     body = bracket_split_build_line(body_leaves, line, opening_bracket, is_body=True)
4903     tail = bracket_split_build_line(tail_leaves, line, opening_bracket)
4904     bracket_split_succeeded_or_raise(head, body, tail)
4905     if (
4906         Feature.FORCE_OPTIONAL_PARENTHESES not in features
4907         # the opening bracket is an optional paren
4908         and opening_bracket.type == token.LPAR
4909         and not opening_bracket.value
4910         # the closing bracket is an optional paren
4911         and closing_bracket.type == token.RPAR
4912         and not closing_bracket.value
4913         # it's not an import (optional parens are the only thing we can split on
4914         # in this case; attempting a split without them is a waste of time)
4915         and not line.is_import
4916         # there are no standalone comments in the body
4917         and not body.contains_standalone_comments(0)
4918         # and we can actually remove the parens
4919         and can_omit_invisible_parens(body, line_length, omit_on_explode=omit)
4920     ):
4921         omit = {id(closing_bracket), *omit}
4922         try:
4923             yield from right_hand_split(line, line_length, features=features, omit=omit)
4924             return
4925
4926         except CannotSplit:
4927             if not (
4928                 can_be_split(body)
4929                 or is_line_short_enough(body, line_length=line_length)
4930             ):
4931                 raise CannotSplit(
4932                     "Splitting failed, body is still too long and can't be split."
4933                 )
4934
4935             elif head.contains_multiline_strings() or tail.contains_multiline_strings():
4936                 raise CannotSplit(
4937                     "The current optional pair of parentheses is bound to fail to"
4938                     " satisfy the splitting algorithm because the head or the tail"
4939                     " contains multiline strings which by definition never fit one"
4940                     " line."
4941                 )
4942
4943     ensure_visible(opening_bracket)
4944     ensure_visible(closing_bracket)
4945     for result in (head, body, tail):
4946         if result:
4947             yield result
4948
4949
4950 def bracket_split_succeeded_or_raise(head: Line, body: Line, tail: Line) -> None:
4951     """Raise :exc:`CannotSplit` if the last left- or right-hand split failed.
4952
4953     Do nothing otherwise.
4954
4955     A left- or right-hand split is based on a pair of brackets. Content before
4956     (and including) the opening bracket is left on one line, content inside the
4957     brackets is put on a separate line, and finally content starting with and
4958     following the closing bracket is put on a separate line.
4959
4960     Those are called `head`, `body`, and `tail`, respectively. If the split
4961     produced the same line (all content in `head`) or ended up with an empty `body`
4962     and the `tail` is just the closing bracket, then it's considered failed.
4963     """
4964     tail_len = len(str(tail).strip())
4965     if not body:
4966         if tail_len == 0:
4967             raise CannotSplit("Splitting brackets produced the same line")
4968
4969         elif tail_len < 3:
4970             raise CannotSplit(
4971                 f"Splitting brackets on an empty body to save {tail_len} characters is"
4972                 " not worth it"
4973             )
4974
4975
4976 def bracket_split_build_line(
4977     leaves: List[Leaf], original: Line, opening_bracket: Leaf, *, is_body: bool = False
4978 ) -> Line:
4979     """Return a new line with given `leaves` and respective comments from `original`.
4980
4981     If `is_body` is True, the result line is one-indented inside brackets and as such
4982     has its first leaf's prefix normalized and a trailing comma added when expected.
4983     """
4984     result = Line(mode=original.mode, depth=original.depth)
4985     if is_body:
4986         result.inside_brackets = True
4987         result.depth += 1
4988         if leaves:
4989             # Since body is a new indent level, remove spurious leading whitespace.
4990             normalize_prefix(leaves[0], inside_brackets=True)
4991             # Ensure a trailing comma for imports and standalone function arguments, but
4992             # be careful not to add one after any comments or within type annotations.
4993             no_commas = (
4994                 original.is_def
4995                 and opening_bracket.value == "("
4996                 and not any(leaf.type == token.COMMA for leaf in leaves)
4997             )
4998
4999             if original.is_import or no_commas:
5000                 for i in range(len(leaves) - 1, -1, -1):
5001                     if leaves[i].type == STANDALONE_COMMENT:
5002                         continue
5003
5004                     if leaves[i].type != token.COMMA:
5005                         new_comma = Leaf(token.COMMA, ",")
5006                         leaves.insert(i + 1, new_comma)
5007                     break
5008
5009     # Populate the line
5010     for leaf in leaves:
5011         result.append(leaf, preformatted=True)
5012         for comment_after in original.comments_after(leaf):
5013             result.append(comment_after, preformatted=True)
5014     if is_body and should_split_line(result, opening_bracket):
5015         result.should_split_rhs = True
5016     return result
5017
5018
5019 def dont_increase_indentation(split_func: Transformer) -> Transformer:
5020     """Normalize prefix of the first leaf in every line returned by `split_func`.
5021
5022     This is a decorator over relevant split functions.
5023     """
5024
5025     @wraps(split_func)
5026     def split_wrapper(line: Line, features: Collection[Feature] = ()) -> Iterator[Line]:
5027         for line in split_func(line, features):
5028             normalize_prefix(line.leaves[0], inside_brackets=True)
5029             yield line
5030
5031     return split_wrapper
5032
5033
5034 @dont_increase_indentation
5035 def delimiter_split(line: Line, features: Collection[Feature] = ()) -> Iterator[Line]:
5036     """Split according to delimiters of the highest priority.
5037
5038     If the appropriate Features are given, the split will add trailing commas
5039     also in function signatures and calls that contain `*` and `**`.
5040     """
5041     try:
5042         last_leaf = line.leaves[-1]
5043     except IndexError:
5044         raise CannotSplit("Line empty")
5045
5046     bt = line.bracket_tracker
5047     try:
5048         delimiter_priority = bt.max_delimiter_priority(exclude={id(last_leaf)})
5049     except ValueError:
5050         raise CannotSplit("No delimiters found")
5051
5052     if delimiter_priority == DOT_PRIORITY:
5053         if bt.delimiter_count_with_priority(delimiter_priority) == 1:
5054             raise CannotSplit("Splitting a single attribute from its owner looks wrong")
5055
5056     current_line = Line(
5057         mode=line.mode, depth=line.depth, inside_brackets=line.inside_brackets
5058     )
5059     lowest_depth = sys.maxsize
5060     trailing_comma_safe = True
5061
5062     def append_to_line(leaf: Leaf) -> Iterator[Line]:
5063         """Append `leaf` to current line or to new line if appending impossible."""
5064         nonlocal current_line
5065         try:
5066             current_line.append_safe(leaf, preformatted=True)
5067         except ValueError:
5068             yield current_line
5069
5070             current_line = Line(
5071                 mode=line.mode, depth=line.depth, inside_brackets=line.inside_brackets
5072             )
5073             current_line.append(leaf)
5074
5075     for leaf in line.leaves:
5076         yield from append_to_line(leaf)
5077
5078         for comment_after in line.comments_after(leaf):
5079             yield from append_to_line(comment_after)
5080
5081         lowest_depth = min(lowest_depth, leaf.bracket_depth)
5082         if leaf.bracket_depth == lowest_depth:
5083             if is_vararg(leaf, within={syms.typedargslist}):
5084                 trailing_comma_safe = (
5085                     trailing_comma_safe and Feature.TRAILING_COMMA_IN_DEF in features
5086                 )
5087             elif is_vararg(leaf, within={syms.arglist, syms.argument}):
5088                 trailing_comma_safe = (
5089                     trailing_comma_safe and Feature.TRAILING_COMMA_IN_CALL in features
5090                 )
5091
5092         leaf_priority = bt.delimiters.get(id(leaf))
5093         if leaf_priority == delimiter_priority:
5094             yield current_line
5095
5096             current_line = Line(
5097                 mode=line.mode, depth=line.depth, inside_brackets=line.inside_brackets
5098             )
5099     if current_line:
5100         if (
5101             trailing_comma_safe
5102             and delimiter_priority == COMMA_PRIORITY
5103             and current_line.leaves[-1].type != token.COMMA
5104             and current_line.leaves[-1].type != STANDALONE_COMMENT
5105         ):
5106             new_comma = Leaf(token.COMMA, ",")
5107             current_line.append(new_comma)
5108         yield current_line
5109
5110
5111 @dont_increase_indentation
5112 def standalone_comment_split(
5113     line: Line, features: Collection[Feature] = ()
5114 ) -> Iterator[Line]:
5115     """Split standalone comments from the rest of the line."""
5116     if not line.contains_standalone_comments(0):
5117         raise CannotSplit("Line does not have any standalone comments")
5118
5119     current_line = Line(
5120         mode=line.mode, depth=line.depth, inside_brackets=line.inside_brackets
5121     )
5122
5123     def append_to_line(leaf: Leaf) -> Iterator[Line]:
5124         """Append `leaf` to current line or to new line if appending impossible."""
5125         nonlocal current_line
5126         try:
5127             current_line.append_safe(leaf, preformatted=True)
5128         except ValueError:
5129             yield current_line
5130
5131             current_line = Line(
5132                 line.mode, depth=line.depth, inside_brackets=line.inside_brackets
5133             )
5134             current_line.append(leaf)
5135
5136     for leaf in line.leaves:
5137         yield from append_to_line(leaf)
5138
5139         for comment_after in line.comments_after(leaf):
5140             yield from append_to_line(comment_after)
5141
5142     if current_line:
5143         yield current_line
5144
5145
5146 def is_import(leaf: Leaf) -> bool:
5147     """Return True if the given leaf starts an import statement."""
5148     p = leaf.parent
5149     t = leaf.type
5150     v = leaf.value
5151     return bool(
5152         t == token.NAME
5153         and (
5154             (v == "import" and p and p.type == syms.import_name)
5155             or (v == "from" and p and p.type == syms.import_from)
5156         )
5157     )
5158
5159
5160 def is_type_comment(leaf: Leaf, suffix: str = "") -> bool:
5161     """Return True if the given leaf is a special comment.
5162     Only returns true for type comments for now."""
5163     t = leaf.type
5164     v = leaf.value
5165     return t in {token.COMMENT, STANDALONE_COMMENT} and v.startswith("# type:" + suffix)
5166
5167
5168 def normalize_prefix(leaf: Leaf, *, inside_brackets: bool) -> None:
5169     """Leave existing extra newlines if not `inside_brackets`. Remove everything
5170     else.
5171
5172     Note: don't use backslashes for formatting or you'll lose your voting rights.
5173     """
5174     if not inside_brackets:
5175         spl = leaf.prefix.split("#")
5176         if "\\" not in spl[0]:
5177             nl_count = spl[-1].count("\n")
5178             if len(spl) > 1:
5179                 nl_count -= 1
5180             leaf.prefix = "\n" * nl_count
5181             return
5182
5183     leaf.prefix = ""
5184
5185
5186 def normalize_string_prefix(leaf: Leaf, remove_u_prefix: bool = False) -> None:
5187     """Make all string prefixes lowercase.
5188
5189     If remove_u_prefix is given, also removes any u prefix from the string.
5190
5191     Note: Mutates its argument.
5192     """
5193     match = re.match(r"^([" + STRING_PREFIX_CHARS + r"]*)(.*)$", leaf.value, re.DOTALL)
5194     assert match is not None, f"failed to match string {leaf.value!r}"
5195     orig_prefix = match.group(1)
5196     new_prefix = orig_prefix.replace("F", "f").replace("B", "b").replace("U", "u")
5197     if remove_u_prefix:
5198         new_prefix = new_prefix.replace("u", "")
5199     leaf.value = f"{new_prefix}{match.group(2)}"
5200
5201
5202 def normalize_string_quotes(leaf: Leaf) -> None:
5203     """Prefer double quotes but only if it doesn't cause more escaping.
5204
5205     Adds or removes backslashes as appropriate. Doesn't parse and fix
5206     strings nested in f-strings (yet).
5207
5208     Note: Mutates its argument.
5209     """
5210     value = leaf.value.lstrip(STRING_PREFIX_CHARS)
5211     if value[:3] == '"""':
5212         return
5213
5214     elif value[:3] == "'''":
5215         orig_quote = "'''"
5216         new_quote = '"""'
5217     elif value[0] == '"':
5218         orig_quote = '"'
5219         new_quote = "'"
5220     else:
5221         orig_quote = "'"
5222         new_quote = '"'
5223     first_quote_pos = leaf.value.find(orig_quote)
5224     if first_quote_pos == -1:
5225         return  # There's an internal error
5226
5227     prefix = leaf.value[:first_quote_pos]
5228     unescaped_new_quote = re.compile(rf"(([^\\]|^)(\\\\)*){new_quote}")
5229     escaped_new_quote = re.compile(rf"([^\\]|^)\\((?:\\\\)*){new_quote}")
5230     escaped_orig_quote = re.compile(rf"([^\\]|^)\\((?:\\\\)*){orig_quote}")
5231     body = leaf.value[first_quote_pos + len(orig_quote) : -len(orig_quote)]
5232     if "r" in prefix.casefold():
5233         if unescaped_new_quote.search(body):
5234             # There's at least one unescaped new_quote in this raw string
5235             # so converting is impossible
5236             return
5237
5238         # Do not introduce or remove backslashes in raw strings
5239         new_body = body
5240     else:
5241         # remove unnecessary escapes
5242         new_body = sub_twice(escaped_new_quote, rf"\1\2{new_quote}", body)
5243         if body != new_body:
5244             # Consider the string without unnecessary escapes as the original
5245             body = new_body
5246             leaf.value = f"{prefix}{orig_quote}{body}{orig_quote}"
5247         new_body = sub_twice(escaped_orig_quote, rf"\1\2{orig_quote}", new_body)
5248         new_body = sub_twice(unescaped_new_quote, rf"\1\\{new_quote}", new_body)
5249     if "f" in prefix.casefold():
5250         matches = re.findall(
5251             r"""
5252             (?:[^{]|^)\{  # start of the string or a non-{ followed by a single {
5253                 ([^{].*?)  # contents of the brackets except if begins with {{
5254             \}(?:[^}]|$)  # A } followed by end of the string or a non-}
5255             """,
5256             new_body,
5257             re.VERBOSE,
5258         )
5259         for m in matches:
5260             if "\\" in str(m):
5261                 # Do not introduce backslashes in interpolated expressions
5262                 return
5263
5264     if new_quote == '"""' and new_body[-1:] == '"':
5265         # edge case:
5266         new_body = new_body[:-1] + '\\"'
5267     orig_escape_count = body.count("\\")
5268     new_escape_count = new_body.count("\\")
5269     if new_escape_count > orig_escape_count:
5270         return  # Do not introduce more escaping
5271
5272     if new_escape_count == orig_escape_count and orig_quote == '"':
5273         return  # Prefer double quotes
5274
5275     leaf.value = f"{prefix}{new_quote}{new_body}{new_quote}"
5276
5277
5278 def normalize_numeric_literal(leaf: Leaf) -> None:
5279     """Normalizes numeric (float, int, and complex) literals.
5280
5281     All letters used in the representation are normalized to lowercase (except
5282     in Python 2 long literals).
5283     """
5284     text = leaf.value.lower()
5285     if text.startswith(("0o", "0b")):
5286         # Leave octal and binary literals alone.
5287         pass
5288     elif text.startswith("0x"):
5289         text = format_hex(text)
5290     elif "e" in text:
5291         text = format_scientific_notation(text)
5292     elif text.endswith(("j", "l")):
5293         text = format_long_or_complex_number(text)
5294     else:
5295         text = format_float_or_int_string(text)
5296     leaf.value = text
5297
5298
5299 def format_hex(text: str) -> str:
5300     """
5301     Formats a hexadecimal string like "0x12b3"
5302
5303     Uses lowercase because of similarity between "B" and "8", which
5304     can cause security issues.
5305     see: https://github.com/psf/black/issues/1692
5306     """
5307
5308     before, after = text[:2], text[2:]
5309     return f"{before}{after.lower()}"
5310
5311
5312 def format_scientific_notation(text: str) -> str:
5313     """Formats a numeric string utilizing scentific notation"""
5314     before, after = text.split("e")
5315     sign = ""
5316     if after.startswith("-"):
5317         after = after[1:]
5318         sign = "-"
5319     elif after.startswith("+"):
5320         after = after[1:]
5321     before = format_float_or_int_string(before)
5322     return f"{before}e{sign}{after}"
5323
5324
5325 def format_long_or_complex_number(text: str) -> str:
5326     """Formats a long or complex string like `10L` or `10j`"""
5327     number = text[:-1]
5328     suffix = text[-1]
5329     # Capitalize in "2L" because "l" looks too similar to "1".
5330     if suffix == "l":
5331         suffix = "L"
5332     return f"{format_float_or_int_string(number)}{suffix}"
5333
5334
5335 def format_float_or_int_string(text: str) -> str:
5336     """Formats a float string like "1.0"."""
5337     if "." not in text:
5338         return text
5339
5340     before, after = text.split(".")
5341     return f"{before or 0}.{after or 0}"
5342
5343
5344 def normalize_invisible_parens(node: Node, parens_after: Set[str]) -> None:
5345     """Make existing optional parentheses invisible or create new ones.
5346
5347     `parens_after` is a set of string leaf values immediately after which parens
5348     should be put.
5349
5350     Standardizes on visible parentheses for single-element tuples, and keeps
5351     existing visible parentheses for other tuples and generator expressions.
5352     """
5353     for pc in list_comments(node.prefix, is_endmarker=False):
5354         if pc.value in FMT_OFF:
5355             # This `node` has a prefix with `# fmt: off`, don't mess with parens.
5356             return
5357     check_lpar = False
5358     for index, child in enumerate(list(node.children)):
5359         # Fixes a bug where invisible parens are not properly stripped from
5360         # assignment statements that contain type annotations.
5361         if isinstance(child, Node) and child.type == syms.annassign:
5362             normalize_invisible_parens(child, parens_after=parens_after)
5363
5364         # Add parentheses around long tuple unpacking in assignments.
5365         if (
5366             index == 0
5367             and isinstance(child, Node)
5368             and child.type == syms.testlist_star_expr
5369         ):
5370             check_lpar = True
5371
5372         if check_lpar:
5373             if child.type == syms.atom:
5374                 if maybe_make_parens_invisible_in_atom(child, parent=node):
5375                     wrap_in_parentheses(node, child, visible=False)
5376             elif is_one_tuple(child):
5377                 wrap_in_parentheses(node, child, visible=True)
5378             elif node.type == syms.import_from:
5379                 # "import from" nodes store parentheses directly as part of
5380                 # the statement
5381                 if child.type == token.LPAR:
5382                     # make parentheses invisible
5383                     child.value = ""  # type: ignore
5384                     node.children[-1].value = ""  # type: ignore
5385                 elif child.type != token.STAR:
5386                     # insert invisible parentheses
5387                     node.insert_child(index, Leaf(token.LPAR, ""))
5388                     node.append_child(Leaf(token.RPAR, ""))
5389                 break
5390
5391             elif not (isinstance(child, Leaf) and is_multiline_string(child)):
5392                 wrap_in_parentheses(node, child, visible=False)
5393
5394         check_lpar = isinstance(child, Leaf) and child.value in parens_after
5395
5396
5397 def normalize_fmt_off(node: Node) -> None:
5398     """Convert content between `# fmt: off`/`# fmt: on` into standalone comments."""
5399     try_again = True
5400     while try_again:
5401         try_again = convert_one_fmt_off_pair(node)
5402
5403
5404 def convert_one_fmt_off_pair(node: Node) -> bool:
5405     """Convert content of a single `# fmt: off`/`# fmt: on` into a standalone comment.
5406
5407     Returns True if a pair was converted.
5408     """
5409     for leaf in node.leaves():
5410         previous_consumed = 0
5411         for comment in list_comments(leaf.prefix, is_endmarker=False):
5412             if comment.value not in FMT_PASS:
5413                 previous_consumed = comment.consumed
5414                 continue
5415             # We only want standalone comments. If there's no previous leaf or
5416             # the previous leaf is indentation, it's a standalone comment in
5417             # disguise.
5418             if comment.value in FMT_PASS and comment.type != STANDALONE_COMMENT:
5419                 prev = preceding_leaf(leaf)
5420                 if prev:
5421                     if comment.value in FMT_OFF and prev.type not in WHITESPACE:
5422                         continue
5423                     if comment.value in FMT_SKIP and prev.type in WHITESPACE:
5424                         continue
5425
5426             ignored_nodes = list(generate_ignored_nodes(leaf, comment))
5427             if not ignored_nodes:
5428                 continue
5429
5430             first = ignored_nodes[0]  # Can be a container node with the `leaf`.
5431             parent = first.parent
5432             prefix = first.prefix
5433             first.prefix = prefix[comment.consumed :]
5434             hidden_value = "".join(str(n) for n in ignored_nodes)
5435             if comment.value in FMT_OFF:
5436                 hidden_value = comment.value + "\n" + hidden_value
5437             if comment.value in FMT_SKIP:
5438                 hidden_value += "  " + comment.value
5439             if hidden_value.endswith("\n"):
5440                 # That happens when one of the `ignored_nodes` ended with a NEWLINE
5441                 # leaf (possibly followed by a DEDENT).
5442                 hidden_value = hidden_value[:-1]
5443             first_idx: Optional[int] = None
5444             for ignored in ignored_nodes:
5445                 index = ignored.remove()
5446                 if first_idx is None:
5447                     first_idx = index
5448             assert parent is not None, "INTERNAL ERROR: fmt: on/off handling (1)"
5449             assert first_idx is not None, "INTERNAL ERROR: fmt: on/off handling (2)"
5450             parent.insert_child(
5451                 first_idx,
5452                 Leaf(
5453                     STANDALONE_COMMENT,
5454                     hidden_value,
5455                     prefix=prefix[:previous_consumed] + "\n" * comment.newlines,
5456                 ),
5457             )
5458             return True
5459
5460     return False
5461
5462
5463 def generate_ignored_nodes(leaf: Leaf, comment: ProtoComment) -> Iterator[LN]:
5464     """Starting from the container of `leaf`, generate all leaves until `# fmt: on`.
5465
5466     If comment is skip, returns leaf only.
5467     Stops at the end of the block.
5468     """
5469     container: Optional[LN] = container_of(leaf)
5470     if comment.value in FMT_SKIP:
5471         prev_sibling = leaf.prev_sibling
5472         if comment.value in leaf.prefix and prev_sibling is not None:
5473             leaf.prefix = leaf.prefix.replace(comment.value, "")
5474             siblings = [prev_sibling]
5475             while (
5476                 "\n" not in prev_sibling.prefix
5477                 and prev_sibling.prev_sibling is not None
5478             ):
5479                 prev_sibling = prev_sibling.prev_sibling
5480                 siblings.insert(0, prev_sibling)
5481             for sibling in siblings:
5482                 yield sibling
5483         elif leaf.parent is not None:
5484             yield leaf.parent
5485         return
5486     while container is not None and container.type != token.ENDMARKER:
5487         if is_fmt_on(container):
5488             return
5489
5490         # fix for fmt: on in children
5491         if contains_fmt_on_at_column(container, leaf.column):
5492             for child in container.children:
5493                 if contains_fmt_on_at_column(child, leaf.column):
5494                     return
5495                 yield child
5496         else:
5497             yield container
5498             container = container.next_sibling
5499
5500
5501 def is_fmt_on(container: LN) -> bool:
5502     """Determine whether formatting is switched on within a container.
5503     Determined by whether the last `# fmt:` comment is `on` or `off`.
5504     """
5505     fmt_on = False
5506     for comment in list_comments(container.prefix, is_endmarker=False):
5507         if comment.value in FMT_ON:
5508             fmt_on = True
5509         elif comment.value in FMT_OFF:
5510             fmt_on = False
5511     return fmt_on
5512
5513
5514 def contains_fmt_on_at_column(container: LN, column: int) -> bool:
5515     """Determine if children at a given column have formatting switched on."""
5516     for child in container.children:
5517         if (
5518             isinstance(child, Node)
5519             and first_leaf_column(child) == column
5520             or isinstance(child, Leaf)
5521             and child.column == column
5522         ):
5523             if is_fmt_on(child):
5524                 return True
5525
5526     return False
5527
5528
5529 def first_leaf_column(node: Node) -> Optional[int]:
5530     """Returns the column of the first leaf child of a node."""
5531     for child in node.children:
5532         if isinstance(child, Leaf):
5533             return child.column
5534     return None
5535
5536
5537 def maybe_make_parens_invisible_in_atom(node: LN, parent: LN) -> bool:
5538     """If it's safe, make the parens in the atom `node` invisible, recursively.
5539     Additionally, remove repeated, adjacent invisible parens from the atom `node`
5540     as they are redundant.
5541
5542     Returns whether the node should itself be wrapped in invisible parentheses.
5543
5544     """
5545
5546     if (
5547         node.type != syms.atom
5548         or is_empty_tuple(node)
5549         or is_one_tuple(node)
5550         or (is_yield(node) and parent.type != syms.expr_stmt)
5551         or max_delimiter_priority_in_atom(node) >= COMMA_PRIORITY
5552     ):
5553         return False
5554
5555     if is_walrus_assignment(node):
5556         if parent.type in [syms.annassign, syms.expr_stmt]:
5557             return False
5558
5559     first = node.children[0]
5560     last = node.children[-1]
5561     if first.type == token.LPAR and last.type == token.RPAR:
5562         middle = node.children[1]
5563         # make parentheses invisible
5564         first.value = ""  # type: ignore
5565         last.value = ""  # type: ignore
5566         maybe_make_parens_invisible_in_atom(middle, parent=parent)
5567
5568         if is_atom_with_invisible_parens(middle):
5569             # Strip the invisible parens from `middle` by replacing
5570             # it with the child in-between the invisible parens
5571             middle.replace(middle.children[1])
5572
5573         return False
5574
5575     return True
5576
5577
5578 def is_atom_with_invisible_parens(node: LN) -> bool:
5579     """Given a `LN`, determines whether it's an atom `node` with invisible
5580     parens. Useful in dedupe-ing and normalizing parens.
5581     """
5582     if isinstance(node, Leaf) or node.type != syms.atom:
5583         return False
5584
5585     first, last = node.children[0], node.children[-1]
5586     return (
5587         isinstance(first, Leaf)
5588         and first.type == token.LPAR
5589         and first.value == ""
5590         and isinstance(last, Leaf)
5591         and last.type == token.RPAR
5592         and last.value == ""
5593     )
5594
5595
5596 def is_empty_tuple(node: LN) -> bool:
5597     """Return True if `node` holds an empty tuple."""
5598     return (
5599         node.type == syms.atom
5600         and len(node.children) == 2
5601         and node.children[0].type == token.LPAR
5602         and node.children[1].type == token.RPAR
5603     )
5604
5605
5606 def unwrap_singleton_parenthesis(node: LN) -> Optional[LN]:
5607     """Returns `wrapped` if `node` is of the shape ( wrapped ).
5608
5609     Parenthesis can be optional. Returns None otherwise"""
5610     if len(node.children) != 3:
5611         return None
5612
5613     lpar, wrapped, rpar = node.children
5614     if not (lpar.type == token.LPAR and rpar.type == token.RPAR):
5615         return None
5616
5617     return wrapped
5618
5619
5620 def first_child_is_arith(node: Node) -> bool:
5621     """Whether first child is an arithmetic or a binary arithmetic expression"""
5622     expr_types = {
5623         syms.arith_expr,
5624         syms.shift_expr,
5625         syms.xor_expr,
5626         syms.and_expr,
5627     }
5628     return bool(node.children and node.children[0].type in expr_types)
5629
5630
5631 def wrap_in_parentheses(parent: Node, child: LN, *, visible: bool = True) -> None:
5632     """Wrap `child` in parentheses.
5633
5634     This replaces `child` with an atom holding the parentheses and the old
5635     child.  That requires moving the prefix.
5636
5637     If `visible` is False, the leaves will be valueless (and thus invisible).
5638     """
5639     lpar = Leaf(token.LPAR, "(" if visible else "")
5640     rpar = Leaf(token.RPAR, ")" if visible else "")
5641     prefix = child.prefix
5642     child.prefix = ""
5643     index = child.remove() or 0
5644     new_child = Node(syms.atom, [lpar, child, rpar])
5645     new_child.prefix = prefix
5646     parent.insert_child(index, new_child)
5647
5648
5649 def is_one_tuple(node: LN) -> bool:
5650     """Return True if `node` holds a tuple with one element, with or without parens."""
5651     if node.type == syms.atom:
5652         gexp = unwrap_singleton_parenthesis(node)
5653         if gexp is None or gexp.type != syms.testlist_gexp:
5654             return False
5655
5656         return len(gexp.children) == 2 and gexp.children[1].type == token.COMMA
5657
5658     return (
5659         node.type in IMPLICIT_TUPLE
5660         and len(node.children) == 2
5661         and node.children[1].type == token.COMMA
5662     )
5663
5664
5665 def is_walrus_assignment(node: LN) -> bool:
5666     """Return True iff `node` is of the shape ( test := test )"""
5667     inner = unwrap_singleton_parenthesis(node)
5668     return inner is not None and inner.type == syms.namedexpr_test
5669
5670
5671 def is_simple_decorator_trailer(node: LN, last: bool = False) -> bool:
5672     """Return True iff `node` is a trailer valid in a simple decorator"""
5673     return node.type == syms.trailer and (
5674         (
5675             len(node.children) == 2
5676             and node.children[0].type == token.DOT
5677             and node.children[1].type == token.NAME
5678         )
5679         # last trailer can be arguments
5680         or (
5681             last
5682             and len(node.children) == 3
5683             and node.children[0].type == token.LPAR
5684             # and node.children[1].type == syms.argument
5685             and node.children[2].type == token.RPAR
5686         )
5687     )
5688
5689
5690 def is_simple_decorator_expression(node: LN) -> bool:
5691     """Return True iff `node` could be a 'dotted name' decorator
5692
5693     This function takes the node of the 'namedexpr_test' of the new decorator
5694     grammar and test if it would be valid under the old decorator grammar.
5695
5696     The old grammar was: decorator: @ dotted_name [arguments] NEWLINE
5697     The new grammar is : decorator: @ namedexpr_test NEWLINE
5698     """
5699     if node.type == token.NAME:
5700         return True
5701     if node.type == syms.power:
5702         if node.children:
5703             return (
5704                 node.children[0].type == token.NAME
5705                 and all(map(is_simple_decorator_trailer, node.children[1:-1]))
5706                 and (
5707                     len(node.children) < 2
5708                     or is_simple_decorator_trailer(node.children[-1], last=True)
5709                 )
5710             )
5711     return False
5712
5713
5714 def is_yield(node: LN) -> bool:
5715     """Return True if `node` holds a `yield` or `yield from` expression."""
5716     if node.type == syms.yield_expr:
5717         return True
5718
5719     if node.type == token.NAME and node.value == "yield":  # type: ignore
5720         return True
5721
5722     if node.type != syms.atom:
5723         return False
5724
5725     if len(node.children) != 3:
5726         return False
5727
5728     lpar, expr, rpar = node.children
5729     if lpar.type == token.LPAR and rpar.type == token.RPAR:
5730         return is_yield(expr)
5731
5732     return False
5733
5734
5735 def is_vararg(leaf: Leaf, within: Set[NodeType]) -> bool:
5736     """Return True if `leaf` is a star or double star in a vararg or kwarg.
5737
5738     If `within` includes VARARGS_PARENTS, this applies to function signatures.
5739     If `within` includes UNPACKING_PARENTS, it applies to right hand-side
5740     extended iterable unpacking (PEP 3132) and additional unpacking
5741     generalizations (PEP 448).
5742     """
5743     if leaf.type not in VARARGS_SPECIALS or not leaf.parent:
5744         return False
5745
5746     p = leaf.parent
5747     if p.type == syms.star_expr:
5748         # Star expressions are also used as assignment targets in extended
5749         # iterable unpacking (PEP 3132).  See what its parent is instead.
5750         if not p.parent:
5751             return False
5752
5753         p = p.parent
5754
5755     return p.type in within
5756
5757
5758 def is_multiline_string(leaf: Leaf) -> bool:
5759     """Return True if `leaf` is a multiline string that actually spans many lines."""
5760     return has_triple_quotes(leaf.value) and "\n" in leaf.value
5761
5762
5763 def is_stub_suite(node: Node) -> bool:
5764     """Return True if `node` is a suite with a stub body."""
5765     if (
5766         len(node.children) != 4
5767         or node.children[0].type != token.NEWLINE
5768         or node.children[1].type != token.INDENT
5769         or node.children[3].type != token.DEDENT
5770     ):
5771         return False
5772
5773     return is_stub_body(node.children[2])
5774
5775
5776 def is_stub_body(node: LN) -> bool:
5777     """Return True if `node` is a simple statement containing an ellipsis."""
5778     if not isinstance(node, Node) or node.type != syms.simple_stmt:
5779         return False
5780
5781     if len(node.children) != 2:
5782         return False
5783
5784     child = node.children[0]
5785     return (
5786         child.type == syms.atom
5787         and len(child.children) == 3
5788         and all(leaf == Leaf(token.DOT, ".") for leaf in child.children)
5789     )
5790
5791
5792 def max_delimiter_priority_in_atom(node: LN) -> Priority:
5793     """Return maximum delimiter priority inside `node`.
5794
5795     This is specific to atoms with contents contained in a pair of parentheses.
5796     If `node` isn't an atom or there are no enclosing parentheses, returns 0.
5797     """
5798     if node.type != syms.atom:
5799         return 0
5800
5801     first = node.children[0]
5802     last = node.children[-1]
5803     if not (first.type == token.LPAR and last.type == token.RPAR):
5804         return 0
5805
5806     bt = BracketTracker()
5807     for c in node.children[1:-1]:
5808         if isinstance(c, Leaf):
5809             bt.mark(c)
5810         else:
5811             for leaf in c.leaves():
5812                 bt.mark(leaf)
5813     try:
5814         return bt.max_delimiter_priority()
5815
5816     except ValueError:
5817         return 0
5818
5819
5820 def ensure_visible(leaf: Leaf) -> None:
5821     """Make sure parentheses are visible.
5822
5823     They could be invisible as part of some statements (see
5824     :func:`normalize_invisible_parens` and :func:`visit_import_from`).
5825     """
5826     if leaf.type == token.LPAR:
5827         leaf.value = "("
5828     elif leaf.type == token.RPAR:
5829         leaf.value = ")"
5830
5831
5832 def should_split_line(line: Line, opening_bracket: Leaf) -> bool:
5833     """Should `line` be immediately split with `delimiter_split()` after RHS?"""
5834
5835     if not (opening_bracket.parent and opening_bracket.value in "[{("):
5836         return False
5837
5838     # We're essentially checking if the body is delimited by commas and there's more
5839     # than one of them (we're excluding the trailing comma and if the delimiter priority
5840     # is still commas, that means there's more).
5841     exclude = set()
5842     trailing_comma = False
5843     try:
5844         last_leaf = line.leaves[-1]
5845         if last_leaf.type == token.COMMA:
5846             trailing_comma = True
5847             exclude.add(id(last_leaf))
5848         max_priority = line.bracket_tracker.max_delimiter_priority(exclude=exclude)
5849     except (IndexError, ValueError):
5850         return False
5851
5852     return max_priority == COMMA_PRIORITY and (
5853         (line.mode.magic_trailing_comma and trailing_comma)
5854         # always explode imports
5855         or opening_bracket.parent.type in {syms.atom, syms.import_from}
5856     )
5857
5858
5859 def is_one_tuple_between(opening: Leaf, closing: Leaf, leaves: List[Leaf]) -> bool:
5860     """Return True if content between `opening` and `closing` looks like a one-tuple."""
5861     if opening.type != token.LPAR and closing.type != token.RPAR:
5862         return False
5863
5864     depth = closing.bracket_depth + 1
5865     for _opening_index, leaf in enumerate(leaves):
5866         if leaf is opening:
5867             break
5868
5869     else:
5870         raise LookupError("Opening paren not found in `leaves`")
5871
5872     commas = 0
5873     _opening_index += 1
5874     for leaf in leaves[_opening_index:]:
5875         if leaf is closing:
5876             break
5877
5878         bracket_depth = leaf.bracket_depth
5879         if bracket_depth == depth and leaf.type == token.COMMA:
5880             commas += 1
5881             if leaf.parent and leaf.parent.type in {
5882                 syms.arglist,
5883                 syms.typedargslist,
5884             }:
5885                 commas += 1
5886                 break
5887
5888     return commas < 2
5889
5890
5891 def get_features_used(node: Node) -> Set[Feature]:
5892     """Return a set of (relatively) new Python features used in this file.
5893
5894     Currently looking for:
5895     - f-strings;
5896     - underscores in numeric literals;
5897     - trailing commas after * or ** in function signatures and calls;
5898     - positional only arguments in function signatures and lambdas;
5899     - assignment expression;
5900     - relaxed decorator syntax;
5901     """
5902     features: Set[Feature] = set()
5903     for n in node.pre_order():
5904         if n.type == token.STRING:
5905             value_head = n.value[:2]  # type: ignore
5906             if value_head in {'f"', 'F"', "f'", "F'", "rf", "fr", "RF", "FR"}:
5907                 features.add(Feature.F_STRINGS)
5908
5909         elif n.type == token.NUMBER:
5910             if "_" in n.value:  # type: ignore
5911                 features.add(Feature.NUMERIC_UNDERSCORES)
5912
5913         elif n.type == token.SLASH:
5914             if n.parent and n.parent.type in {syms.typedargslist, syms.arglist}:
5915                 features.add(Feature.POS_ONLY_ARGUMENTS)
5916
5917         elif n.type == token.COLONEQUAL:
5918             features.add(Feature.ASSIGNMENT_EXPRESSIONS)
5919
5920         elif n.type == syms.decorator:
5921             if len(n.children) > 1 and not is_simple_decorator_expression(
5922                 n.children[1]
5923             ):
5924                 features.add(Feature.RELAXED_DECORATORS)
5925
5926         elif (
5927             n.type in {syms.typedargslist, syms.arglist}
5928             and n.children
5929             and n.children[-1].type == token.COMMA
5930         ):
5931             if n.type == syms.typedargslist:
5932                 feature = Feature.TRAILING_COMMA_IN_DEF
5933             else:
5934                 feature = Feature.TRAILING_COMMA_IN_CALL
5935
5936             for ch in n.children:
5937                 if ch.type in STARS:
5938                     features.add(feature)
5939
5940                 if ch.type == syms.argument:
5941                     for argch in ch.children:
5942                         if argch.type in STARS:
5943                             features.add(feature)
5944
5945     return features
5946
5947
5948 def detect_target_versions(node: Node) -> Set[TargetVersion]:
5949     """Detect the version to target based on the nodes used."""
5950     features = get_features_used(node)
5951     return {
5952         version for version in TargetVersion if features <= VERSION_TO_FEATURES[version]
5953     }
5954
5955
5956 def generate_trailers_to_omit(line: Line, line_length: int) -> Iterator[Set[LeafID]]:
5957     """Generate sets of closing bracket IDs that should be omitted in a RHS.
5958
5959     Brackets can be omitted if the entire trailer up to and including
5960     a preceding closing bracket fits in one line.
5961
5962     Yielded sets are cumulative (contain results of previous yields, too).  First
5963     set is empty, unless the line should explode, in which case bracket pairs until
5964     the one that needs to explode are omitted.
5965     """
5966
5967     omit: Set[LeafID] = set()
5968     if not line.magic_trailing_comma:
5969         yield omit
5970
5971     length = 4 * line.depth
5972     opening_bracket: Optional[Leaf] = None
5973     closing_bracket: Optional[Leaf] = None
5974     inner_brackets: Set[LeafID] = set()
5975     for index, leaf, leaf_length in enumerate_with_length(line, reversed=True):
5976         length += leaf_length
5977         if length > line_length:
5978             break
5979
5980         has_inline_comment = leaf_length > len(leaf.value) + len(leaf.prefix)
5981         if leaf.type == STANDALONE_COMMENT or has_inline_comment:
5982             break
5983
5984         if opening_bracket:
5985             if leaf is opening_bracket:
5986                 opening_bracket = None
5987             elif leaf.type in CLOSING_BRACKETS:
5988                 prev = line.leaves[index - 1] if index > 0 else None
5989                 if (
5990                     prev
5991                     and prev.type == token.COMMA
5992                     and not is_one_tuple_between(
5993                         leaf.opening_bracket, leaf, line.leaves
5994                     )
5995                 ):
5996                     # Never omit bracket pairs with trailing commas.
5997                     # We need to explode on those.
5998                     break
5999
6000                 inner_brackets.add(id(leaf))
6001         elif leaf.type in CLOSING_BRACKETS:
6002             prev = line.leaves[index - 1] if index > 0 else None
6003             if prev and prev.type in OPENING_BRACKETS:
6004                 # Empty brackets would fail a split so treat them as "inner"
6005                 # brackets (e.g. only add them to the `omit` set if another
6006                 # pair of brackets was good enough.
6007                 inner_brackets.add(id(leaf))
6008                 continue
6009
6010             if closing_bracket:
6011                 omit.add(id(closing_bracket))
6012                 omit.update(inner_brackets)
6013                 inner_brackets.clear()
6014                 yield omit
6015
6016             if (
6017                 prev
6018                 and prev.type == token.COMMA
6019                 and not is_one_tuple_between(leaf.opening_bracket, leaf, line.leaves)
6020             ):
6021                 # Never omit bracket pairs with trailing commas.
6022                 # We need to explode on those.
6023                 break
6024
6025             if leaf.value:
6026                 opening_bracket = leaf.opening_bracket
6027                 closing_bracket = leaf
6028
6029
6030 def get_future_imports(node: Node) -> Set[str]:
6031     """Return a set of __future__ imports in the file."""
6032     imports: Set[str] = set()
6033
6034     def get_imports_from_children(children: List[LN]) -> Generator[str, None, None]:
6035         for child in children:
6036             if isinstance(child, Leaf):
6037                 if child.type == token.NAME:
6038                     yield child.value
6039
6040             elif child.type == syms.import_as_name:
6041                 orig_name = child.children[0]
6042                 assert isinstance(orig_name, Leaf), "Invalid syntax parsing imports"
6043                 assert orig_name.type == token.NAME, "Invalid syntax parsing imports"
6044                 yield orig_name.value
6045
6046             elif child.type == syms.import_as_names:
6047                 yield from get_imports_from_children(child.children)
6048
6049             else:
6050                 raise AssertionError("Invalid syntax parsing imports")
6051
6052     for child in node.children:
6053         if child.type != syms.simple_stmt:
6054             break
6055
6056         first_child = child.children[0]
6057         if isinstance(first_child, Leaf):
6058             # Continue looking if we see a docstring; otherwise stop.
6059             if (
6060                 len(child.children) == 2
6061                 and first_child.type == token.STRING
6062                 and child.children[1].type == token.NEWLINE
6063             ):
6064                 continue
6065
6066             break
6067
6068         elif first_child.type == syms.import_from:
6069             module_name = first_child.children[1]
6070             if not isinstance(module_name, Leaf) or module_name.value != "__future__":
6071                 break
6072
6073             imports |= set(get_imports_from_children(first_child.children[3:]))
6074         else:
6075             break
6076
6077     return imports
6078
6079
6080 @lru_cache()
6081 def get_gitignore(root: Path) -> PathSpec:
6082     """ Return a PathSpec matching gitignore content if present."""
6083     gitignore = root / ".gitignore"
6084     lines: List[str] = []
6085     if gitignore.is_file():
6086         with gitignore.open() as gf:
6087             lines = gf.readlines()
6088     return PathSpec.from_lines("gitwildmatch", lines)
6089
6090
6091 def normalize_path_maybe_ignore(
6092     path: Path, root: Path, report: "Report"
6093 ) -> Optional[str]:
6094     """Normalize `path`. May return `None` if `path` was ignored.
6095
6096     `report` is where "path ignored" output goes.
6097     """
6098     try:
6099         abspath = path if path.is_absolute() else Path.cwd() / path
6100         normalized_path = abspath.resolve().relative_to(root).as_posix()
6101     except OSError as e:
6102         report.path_ignored(path, f"cannot be read because {e}")
6103         return None
6104
6105     except ValueError:
6106         if path.is_symlink():
6107             report.path_ignored(path, f"is a symbolic link that points outside {root}")
6108             return None
6109
6110         raise
6111
6112     return normalized_path
6113
6114
6115 def gen_python_files(
6116     paths: Iterable[Path],
6117     root: Path,
6118     include: Optional[Pattern[str]],
6119     exclude: Pattern[str],
6120     force_exclude: Optional[Pattern[str]],
6121     report: "Report",
6122     gitignore: PathSpec,
6123 ) -> Iterator[Path]:
6124     """Generate all files under `path` whose paths are not excluded by the
6125     `exclude_regex` or `force_exclude` regexes, but are included by the `include` regex.
6126
6127     Symbolic links pointing outside of the `root` directory are ignored.
6128
6129     `report` is where output about exclusions goes.
6130     """
6131     assert root.is_absolute(), f"INTERNAL ERROR: `root` must be absolute but is {root}"
6132     for child in paths:
6133         normalized_path = normalize_path_maybe_ignore(child, root, report)
6134         if normalized_path is None:
6135             continue
6136
6137         # First ignore files matching .gitignore
6138         if gitignore.match_file(normalized_path):
6139             report.path_ignored(child, "matches the .gitignore file content")
6140             continue
6141
6142         # Then ignore with `--exclude` and `--force-exclude` options.
6143         normalized_path = "/" + normalized_path
6144         if child.is_dir():
6145             normalized_path += "/"
6146
6147         exclude_match = exclude.search(normalized_path) if exclude else None
6148         if exclude_match and exclude_match.group(0):
6149             report.path_ignored(child, "matches the --exclude regular expression")
6150             continue
6151
6152         force_exclude_match = (
6153             force_exclude.search(normalized_path) if force_exclude else None
6154         )
6155         if force_exclude_match and force_exclude_match.group(0):
6156             report.path_ignored(child, "matches the --force-exclude regular expression")
6157             continue
6158
6159         if child.is_dir():
6160             yield from gen_python_files(
6161                 child.iterdir(),
6162                 root,
6163                 include,
6164                 exclude,
6165                 force_exclude,
6166                 report,
6167                 gitignore,
6168             )
6169
6170         elif child.is_file():
6171             include_match = include.search(normalized_path) if include else True
6172             if include_match:
6173                 yield child
6174
6175
6176 @lru_cache()
6177 def find_project_root(srcs: Iterable[str]) -> Path:
6178     """Return a directory containing .git, .hg, or pyproject.toml.
6179
6180     That directory will be a common parent of all files and directories
6181     passed in `srcs`.
6182
6183     If no directory in the tree contains a marker that would specify it's the
6184     project root, the root of the file system is returned.
6185     """
6186     if not srcs:
6187         return Path("/").resolve()
6188
6189     path_srcs = [Path(Path.cwd(), src).resolve() for src in srcs]
6190
6191     # A list of lists of parents for each 'src'. 'src' is included as a
6192     # "parent" of itself if it is a directory
6193     src_parents = [
6194         list(path.parents) + ([path] if path.is_dir() else []) for path in path_srcs
6195     ]
6196
6197     common_base = max(
6198         set.intersection(*(set(parents) for parents in src_parents)),
6199         key=lambda path: path.parts,
6200     )
6201
6202     for directory in (common_base, *common_base.parents):
6203         if (directory / ".git").exists():
6204             return directory
6205
6206         if (directory / ".hg").is_dir():
6207             return directory
6208
6209         if (directory / "pyproject.toml").is_file():
6210             return directory
6211
6212     return directory
6213
6214
6215 @dataclass
6216 class Report:
6217     """Provides a reformatting counter. Can be rendered with `str(report)`."""
6218
6219     check: bool = False
6220     diff: bool = False
6221     quiet: bool = False
6222     verbose: bool = False
6223     change_count: int = 0
6224     same_count: int = 0
6225     failure_count: int = 0
6226
6227     def done(self, src: Path, changed: Changed) -> None:
6228         """Increment the counter for successful reformatting. Write out a message."""
6229         if changed is Changed.YES:
6230             reformatted = "would reformat" if self.check or self.diff else "reformatted"
6231             if self.verbose or not self.quiet:
6232                 out(f"{reformatted} {src}")
6233             self.change_count += 1
6234         else:
6235             if self.verbose:
6236                 if changed is Changed.NO:
6237                     msg = f"{src} already well formatted, good job."
6238                 else:
6239                     msg = f"{src} wasn't modified on disk since last run."
6240                 out(msg, bold=False)
6241             self.same_count += 1
6242
6243     def failed(self, src: Path, message: str) -> None:
6244         """Increment the counter for failed reformatting. Write out a message."""
6245         err(f"error: cannot format {src}: {message}")
6246         self.failure_count += 1
6247
6248     def path_ignored(self, path: Path, message: str) -> None:
6249         if self.verbose:
6250             out(f"{path} ignored: {message}", bold=False)
6251
6252     @property
6253     def return_code(self) -> int:
6254         """Return the exit code that the app should use.
6255
6256         This considers the current state of changed files and failures:
6257         - if there were any failures, return 123;
6258         - if any files were changed and --check is being used, return 1;
6259         - otherwise return 0.
6260         """
6261         # According to http://tldp.org/LDP/abs/html/exitcodes.html starting with
6262         # 126 we have special return codes reserved by the shell.
6263         if self.failure_count:
6264             return 123
6265
6266         elif self.change_count and self.check:
6267             return 1
6268
6269         return 0
6270
6271     def __str__(self) -> str:
6272         """Render a color report of the current state.
6273
6274         Use `click.unstyle` to remove colors.
6275         """
6276         if self.check or self.diff:
6277             reformatted = "would be reformatted"
6278             unchanged = "would be left unchanged"
6279             failed = "would fail to reformat"
6280         else:
6281             reformatted = "reformatted"
6282             unchanged = "left unchanged"
6283             failed = "failed to reformat"
6284         report = []
6285         if self.change_count:
6286             s = "s" if self.change_count > 1 else ""
6287             report.append(
6288                 click.style(f"{self.change_count} file{s} {reformatted}", bold=True)
6289             )
6290         if self.same_count:
6291             s = "s" if self.same_count > 1 else ""
6292             report.append(f"{self.same_count} file{s} {unchanged}")
6293         if self.failure_count:
6294             s = "s" if self.failure_count > 1 else ""
6295             report.append(
6296                 click.style(f"{self.failure_count} file{s} {failed}", fg="red")
6297             )
6298         return ", ".join(report) + "."
6299
6300
6301 def parse_ast(src: str) -> Union[ast.AST, ast3.AST, ast27.AST]:
6302     filename = "<unknown>"
6303     if sys.version_info >= (3, 8):
6304         # TODO: support Python 4+ ;)
6305         for minor_version in range(sys.version_info[1], 4, -1):
6306             try:
6307                 return ast.parse(src, filename, feature_version=(3, minor_version))
6308             except SyntaxError:
6309                 continue
6310     else:
6311         for feature_version in (7, 6):
6312             try:
6313                 return ast3.parse(src, filename, feature_version=feature_version)
6314             except SyntaxError:
6315                 continue
6316
6317     return ast27.parse(src)
6318
6319
6320 def _fixup_ast_constants(
6321     node: Union[ast.AST, ast3.AST, ast27.AST]
6322 ) -> Union[ast.AST, ast3.AST, ast27.AST]:
6323     """Map ast nodes deprecated in 3.8 to Constant."""
6324     if isinstance(node, (ast.Str, ast3.Str, ast27.Str, ast.Bytes, ast3.Bytes)):
6325         return ast.Constant(value=node.s)
6326
6327     if isinstance(node, (ast.Num, ast3.Num, ast27.Num)):
6328         return ast.Constant(value=node.n)
6329
6330     if isinstance(node, (ast.NameConstant, ast3.NameConstant)):
6331         return ast.Constant(value=node.value)
6332
6333     return node
6334
6335
6336 def _stringify_ast(
6337     node: Union[ast.AST, ast3.AST, ast27.AST], depth: int = 0
6338 ) -> Iterator[str]:
6339     """Simple visitor generating strings to compare ASTs by content."""
6340
6341     node = _fixup_ast_constants(node)
6342
6343     yield f"{'  ' * depth}{node.__class__.__name__}("
6344
6345     for field in sorted(node._fields):  # noqa: F402
6346         # TypeIgnore has only one field 'lineno' which breaks this comparison
6347         type_ignore_classes = (ast3.TypeIgnore, ast27.TypeIgnore)
6348         if sys.version_info >= (3, 8):
6349             type_ignore_classes += (ast.TypeIgnore,)
6350         if isinstance(node, type_ignore_classes):
6351             break
6352
6353         try:
6354             value = getattr(node, field)
6355         except AttributeError:
6356             continue
6357
6358         yield f"{'  ' * (depth+1)}{field}="
6359
6360         if isinstance(value, list):
6361             for item in value:
6362                 # Ignore nested tuples within del statements, because we may insert
6363                 # parentheses and they change the AST.
6364                 if (
6365                     field == "targets"
6366                     and isinstance(node, (ast.Delete, ast3.Delete, ast27.Delete))
6367                     and isinstance(item, (ast.Tuple, ast3.Tuple, ast27.Tuple))
6368                 ):
6369                     for item in item.elts:
6370                         yield from _stringify_ast(item, depth + 2)
6371
6372                 elif isinstance(item, (ast.AST, ast3.AST, ast27.AST)):
6373                     yield from _stringify_ast(item, depth + 2)
6374
6375         elif isinstance(value, (ast.AST, ast3.AST, ast27.AST)):
6376             yield from _stringify_ast(value, depth + 2)
6377
6378         else:
6379             # Constant strings may be indented across newlines, if they are
6380             # docstrings; fold spaces after newlines when comparing. Similarly,
6381             # trailing and leading space may be removed.
6382             if (
6383                 isinstance(node, ast.Constant)
6384                 and field == "value"
6385                 and isinstance(value, str)
6386             ):
6387                 normalized = re.sub(r" *\n[ \t]*", "\n", value).strip()
6388             else:
6389                 normalized = value
6390             yield f"{'  ' * (depth+2)}{normalized!r},  # {value.__class__.__name__}"
6391
6392     yield f"{'  ' * depth})  # /{node.__class__.__name__}"
6393
6394
6395 def assert_equivalent(src: str, dst: str) -> None:
6396     """Raise AssertionError if `src` and `dst` aren't equivalent."""
6397     try:
6398         src_ast = parse_ast(src)
6399     except Exception as exc:
6400         raise AssertionError(
6401             "cannot use --safe with this file; failed to parse source file.  AST"
6402             f" error message: {exc}"
6403         )
6404
6405     try:
6406         dst_ast = parse_ast(dst)
6407     except Exception as exc:
6408         log = dump_to_file("".join(traceback.format_tb(exc.__traceback__)), dst)
6409         raise AssertionError(
6410             f"INTERNAL ERROR: Black produced invalid code: {exc}. Please report a bug"
6411             " on https://github.com/psf/black/issues.  This invalid output might be"
6412             f" helpful: {log}"
6413         ) from None
6414
6415     src_ast_str = "\n".join(_stringify_ast(src_ast))
6416     dst_ast_str = "\n".join(_stringify_ast(dst_ast))
6417     if src_ast_str != dst_ast_str:
6418         log = dump_to_file(diff(src_ast_str, dst_ast_str, "src", "dst"))
6419         raise AssertionError(
6420             "INTERNAL ERROR: Black produced code that is not equivalent to the"
6421             " source.  Please report a bug on https://github.com/psf/black/issues. "
6422             f" This diff might be helpful: {log}"
6423         ) from None
6424
6425
6426 def assert_stable(src: str, dst: str, mode: Mode) -> None:
6427     """Raise AssertionError if `dst` reformats differently the second time."""
6428     newdst = format_str(dst, mode=mode)
6429     if dst != newdst:
6430         log = dump_to_file(
6431             str(mode),
6432             diff(src, dst, "source", "first pass"),
6433             diff(dst, newdst, "first pass", "second pass"),
6434         )
6435         raise AssertionError(
6436             "INTERNAL ERROR: Black produced different code on the second pass of the"
6437             " formatter.  Please report a bug on https://github.com/psf/black/issues."
6438             f"  This diff might be helpful: {log}"
6439         ) from None
6440
6441
6442 @mypyc_attr(patchable=True)
6443 def dump_to_file(*output: str, ensure_final_newline: bool = True) -> str:
6444     """Dump `output` to a temporary file. Return path to the file."""
6445     with tempfile.NamedTemporaryFile(
6446         mode="w", prefix="blk_", suffix=".log", delete=False, encoding="utf8"
6447     ) as f:
6448         for lines in output:
6449             f.write(lines)
6450             if ensure_final_newline and lines and lines[-1] != "\n":
6451                 f.write("\n")
6452     return f.name
6453
6454
6455 @contextmanager
6456 def nullcontext() -> Iterator[None]:
6457     """Return an empty context manager.
6458
6459     To be used like `nullcontext` in Python 3.7.
6460     """
6461     yield
6462
6463
6464 def diff(a: str, b: str, a_name: str, b_name: str) -> str:
6465     """Return a unified diff string between strings `a` and `b`."""
6466     import difflib
6467
6468     a_lines = [line for line in a.splitlines(keepends=True)]
6469     b_lines = [line for line in b.splitlines(keepends=True)]
6470     diff_lines = []
6471     for line in difflib.unified_diff(
6472         a_lines, b_lines, fromfile=a_name, tofile=b_name, n=5
6473     ):
6474         # Work around https://bugs.python.org/issue2142
6475         # See https://www.gnu.org/software/diffutils/manual/html_node/Incomplete-Lines.html
6476         if line[-1] == "\n":
6477             diff_lines.append(line)
6478         else:
6479             diff_lines.append(line + "\n")
6480             diff_lines.append("\\ No newline at end of file\n")
6481     return "".join(diff_lines)
6482
6483
6484 def cancel(tasks: Iterable["asyncio.Task[Any]"]) -> None:
6485     """asyncio signal handler that cancels all `tasks` and reports to stderr."""
6486     err("Aborted!")
6487     for task in tasks:
6488         task.cancel()
6489
6490
6491 def shutdown(loop: asyncio.AbstractEventLoop) -> None:
6492     """Cancel all pending tasks on `loop`, wait for them, and close the loop."""
6493     try:
6494         if sys.version_info[:2] >= (3, 7):
6495             all_tasks = asyncio.all_tasks
6496         else:
6497             all_tasks = asyncio.Task.all_tasks
6498         # This part is borrowed from asyncio/runners.py in Python 3.7b2.
6499         to_cancel = [task for task in all_tasks(loop) if not task.done()]
6500         if not to_cancel:
6501             return
6502
6503         for task in to_cancel:
6504             task.cancel()
6505         loop.run_until_complete(
6506             asyncio.gather(*to_cancel, loop=loop, return_exceptions=True)
6507         )
6508     finally:
6509         # `concurrent.futures.Future` objects cannot be cancelled once they
6510         # are already running. There might be some when the `shutdown()` happened.
6511         # Silence their logger's spew about the event loop being closed.
6512         cf_logger = logging.getLogger("concurrent.futures")
6513         cf_logger.setLevel(logging.CRITICAL)
6514         loop.close()
6515
6516
6517 def sub_twice(regex: Pattern[str], replacement: str, original: str) -> str:
6518     """Replace `regex` with `replacement` twice on `original`.
6519
6520     This is used by string normalization to perform replaces on
6521     overlapping matches.
6522     """
6523     return regex.sub(replacement, regex.sub(replacement, original))
6524
6525
6526 def re_compile_maybe_verbose(regex: str) -> Pattern[str]:
6527     """Compile a regular expression string in `regex`.
6528
6529     If it contains newlines, use verbose mode.
6530     """
6531     if "\n" in regex:
6532         regex = "(?x)" + regex
6533     compiled: Pattern[str] = re.compile(regex)
6534     return compiled
6535
6536
6537 def enumerate_reversed(sequence: Sequence[T]) -> Iterator[Tuple[Index, T]]:
6538     """Like `reversed(enumerate(sequence))` if that were possible."""
6539     index = len(sequence) - 1
6540     for element in reversed(sequence):
6541         yield (index, element)
6542         index -= 1
6543
6544
6545 def enumerate_with_length(
6546     line: Line, reversed: bool = False
6547 ) -> Iterator[Tuple[Index, Leaf, int]]:
6548     """Return an enumeration of leaves with their length.
6549
6550     Stops prematurely on multiline strings and standalone comments.
6551     """
6552     op = cast(
6553         Callable[[Sequence[Leaf]], Iterator[Tuple[Index, Leaf]]],
6554         enumerate_reversed if reversed else enumerate,
6555     )
6556     for index, leaf in op(line.leaves):
6557         length = len(leaf.prefix) + len(leaf.value)
6558         if "\n" in leaf.value:
6559             return  # Multiline strings, we can't continue.
6560
6561         for comment in line.comments_after(leaf):
6562             length += len(comment.value)
6563
6564         yield index, leaf, length
6565
6566
6567 def is_line_short_enough(line: Line, *, line_length: int, line_str: str = "") -> bool:
6568     """Return True if `line` is no longer than `line_length`.
6569
6570     Uses the provided `line_str` rendering, if any, otherwise computes a new one.
6571     """
6572     if not line_str:
6573         line_str = line_to_string(line)
6574     return (
6575         len(line_str) <= line_length
6576         and "\n" not in line_str  # multiline strings
6577         and not line.contains_standalone_comments()
6578     )
6579
6580
6581 def can_be_split(line: Line) -> bool:
6582     """Return False if the line cannot be split *for sure*.
6583
6584     This is not an exhaustive search but a cheap heuristic that we can use to
6585     avoid some unfortunate formattings (mostly around wrapping unsplittable code
6586     in unnecessary parentheses).
6587     """
6588     leaves = line.leaves
6589     if len(leaves) < 2:
6590         return False
6591
6592     if leaves[0].type == token.STRING and leaves[1].type == token.DOT:
6593         call_count = 0
6594         dot_count = 0
6595         next = leaves[-1]
6596         for leaf in leaves[-2::-1]:
6597             if leaf.type in OPENING_BRACKETS:
6598                 if next.type not in CLOSING_BRACKETS:
6599                     return False
6600
6601                 call_count += 1
6602             elif leaf.type == token.DOT:
6603                 dot_count += 1
6604             elif leaf.type == token.NAME:
6605                 if not (next.type == token.DOT or next.type in OPENING_BRACKETS):
6606                     return False
6607
6608             elif leaf.type not in CLOSING_BRACKETS:
6609                 return False
6610
6611             if dot_count > 1 and call_count > 1:
6612                 return False
6613
6614     return True
6615
6616
6617 def can_omit_invisible_parens(
6618     line: Line,
6619     line_length: int,
6620     omit_on_explode: Collection[LeafID] = (),
6621 ) -> bool:
6622     """Does `line` have a shape safe to reformat without optional parens around it?
6623
6624     Returns True for only a subset of potentially nice looking formattings but
6625     the point is to not return false positives that end up producing lines that
6626     are too long.
6627     """
6628     bt = line.bracket_tracker
6629     if not bt.delimiters:
6630         # Without delimiters the optional parentheses are useless.
6631         return True
6632
6633     max_priority = bt.max_delimiter_priority()
6634     if bt.delimiter_count_with_priority(max_priority) > 1:
6635         # With more than one delimiter of a kind the optional parentheses read better.
6636         return False
6637
6638     if max_priority == DOT_PRIORITY:
6639         # A single stranded method call doesn't require optional parentheses.
6640         return True
6641
6642     assert len(line.leaves) >= 2, "Stranded delimiter"
6643
6644     # With a single delimiter, omit if the expression starts or ends with
6645     # a bracket.
6646     first = line.leaves[0]
6647     second = line.leaves[1]
6648     if first.type in OPENING_BRACKETS and second.type not in CLOSING_BRACKETS:
6649         if _can_omit_opening_paren(line, first=first, line_length=line_length):
6650             return True
6651
6652         # Note: we are not returning False here because a line might have *both*
6653         # a leading opening bracket and a trailing closing bracket.  If the
6654         # opening bracket doesn't match our rule, maybe the closing will.
6655
6656     penultimate = line.leaves[-2]
6657     last = line.leaves[-1]
6658     if line.magic_trailing_comma:
6659         try:
6660             penultimate, last = last_two_except(line.leaves, omit=omit_on_explode)
6661         except LookupError:
6662             # Turns out we'd omit everything.  We cannot skip the optional parentheses.
6663             return False
6664
6665     if (
6666         last.type == token.RPAR
6667         or last.type == token.RBRACE
6668         or (
6669             # don't use indexing for omitting optional parentheses;
6670             # it looks weird
6671             last.type == token.RSQB
6672             and last.parent
6673             and last.parent.type != syms.trailer
6674         )
6675     ):
6676         if penultimate.type in OPENING_BRACKETS:
6677             # Empty brackets don't help.
6678             return False
6679
6680         if is_multiline_string(first):
6681             # Additional wrapping of a multiline string in this situation is
6682             # unnecessary.
6683             return True
6684
6685         if line.magic_trailing_comma and penultimate.type == token.COMMA:
6686             # The rightmost non-omitted bracket pair is the one we want to explode on.
6687             return True
6688
6689         if _can_omit_closing_paren(line, last=last, line_length=line_length):
6690             return True
6691
6692     return False
6693
6694
6695 def _can_omit_opening_paren(line: Line, *, first: Leaf, line_length: int) -> bool:
6696     """See `can_omit_invisible_parens`."""
6697     remainder = False
6698     length = 4 * line.depth
6699     _index = -1
6700     for _index, leaf, leaf_length in enumerate_with_length(line):
6701         if leaf.type in CLOSING_BRACKETS and leaf.opening_bracket is first:
6702             remainder = True
6703         if remainder:
6704             length += leaf_length
6705             if length > line_length:
6706                 break
6707
6708             if leaf.type in OPENING_BRACKETS:
6709                 # There are brackets we can further split on.
6710                 remainder = False
6711
6712     else:
6713         # checked the entire string and line length wasn't exceeded
6714         if len(line.leaves) == _index + 1:
6715             return True
6716
6717     return False
6718
6719
6720 def _can_omit_closing_paren(line: Line, *, last: Leaf, line_length: int) -> bool:
6721     """See `can_omit_invisible_parens`."""
6722     length = 4 * line.depth
6723     seen_other_brackets = False
6724     for _index, leaf, leaf_length in enumerate_with_length(line):
6725         length += leaf_length
6726         if leaf is last.opening_bracket:
6727             if seen_other_brackets or length <= line_length:
6728                 return True
6729
6730         elif leaf.type in OPENING_BRACKETS:
6731             # There are brackets we can further split on.
6732             seen_other_brackets = True
6733
6734     return False
6735
6736
6737 def last_two_except(leaves: List[Leaf], omit: Collection[LeafID]) -> Tuple[Leaf, Leaf]:
6738     """Return (penultimate, last) leaves skipping brackets in `omit` and contents."""
6739     stop_after = None
6740     last = None
6741     for leaf in reversed(leaves):
6742         if stop_after:
6743             if leaf is stop_after:
6744                 stop_after = None
6745             continue
6746
6747         if last:
6748             return leaf, last
6749
6750         if id(leaf) in omit:
6751             stop_after = leaf.opening_bracket
6752         else:
6753             last = leaf
6754     else:
6755         raise LookupError("Last two leaves were also skipped")
6756
6757
6758 def run_transformer(
6759     line: Line,
6760     transform: Transformer,
6761     mode: Mode,
6762     features: Collection[Feature],
6763     *,
6764     line_str: str = "",
6765 ) -> List[Line]:
6766     if not line_str:
6767         line_str = line_to_string(line)
6768     result: List[Line] = []
6769     for transformed_line in transform(line, features):
6770         if str(transformed_line).strip("\n") == line_str:
6771             raise CannotTransform("Line transformer returned an unchanged result")
6772
6773         result.extend(transform_line(transformed_line, mode=mode, features=features))
6774
6775     if not (
6776         transform.__name__ == "rhs"
6777         and line.bracket_tracker.invisible
6778         and not any(bracket.value for bracket in line.bracket_tracker.invisible)
6779         and not line.contains_multiline_strings()
6780         and not result[0].contains_uncollapsable_type_comments()
6781         and not result[0].contains_unsplittable_type_ignore()
6782         and not is_line_short_enough(result[0], line_length=mode.line_length)
6783     ):
6784         return result
6785
6786     line_copy = line.clone()
6787     append_leaves(line_copy, line, line.leaves)
6788     features_fop = set(features) | {Feature.FORCE_OPTIONAL_PARENTHESES}
6789     second_opinion = run_transformer(
6790         line_copy, transform, mode, features_fop, line_str=line_str
6791     )
6792     if all(
6793         is_line_short_enough(ln, line_length=mode.line_length) for ln in second_opinion
6794     ):
6795         result = second_opinion
6796     return result
6797
6798
6799 def get_cache_file(mode: Mode) -> Path:
6800     return CACHE_DIR / f"cache.{mode.get_cache_key()}.pickle"
6801
6802
6803 def read_cache(mode: Mode) -> Cache:
6804     """Read the cache if it exists and is well formed.
6805
6806     If it is not well formed, the call to write_cache later should resolve the issue.
6807     """
6808     cache_file = get_cache_file(mode)
6809     if not cache_file.exists():
6810         return {}
6811
6812     with cache_file.open("rb") as fobj:
6813         try:
6814             cache: Cache = pickle.load(fobj)
6815         except (pickle.UnpicklingError, ValueError):
6816             return {}
6817
6818     return cache
6819
6820
6821 def get_cache_info(path: Path) -> CacheInfo:
6822     """Return the information used to check if a file is already formatted or not."""
6823     stat = path.stat()
6824     return stat.st_mtime, stat.st_size
6825
6826
6827 def filter_cached(cache: Cache, sources: Iterable[Path]) -> Tuple[Set[Path], Set[Path]]:
6828     """Split an iterable of paths in `sources` into two sets.
6829
6830     The first contains paths of files that modified on disk or are not in the
6831     cache. The other contains paths to non-modified files.
6832     """
6833     todo, done = set(), set()
6834     for src in sources:
6835         res_src = src.resolve()
6836         if cache.get(str(res_src)) != get_cache_info(res_src):
6837             todo.add(src)
6838         else:
6839             done.add(src)
6840     return todo, done
6841
6842
6843 def write_cache(cache: Cache, sources: Iterable[Path], mode: Mode) -> None:
6844     """Update the cache file."""
6845     cache_file = get_cache_file(mode)
6846     try:
6847         CACHE_DIR.mkdir(parents=True, exist_ok=True)
6848         new_cache = {
6849             **cache,
6850             **{str(src.resolve()): get_cache_info(src) for src in sources},
6851         }
6852         with tempfile.NamedTemporaryFile(dir=str(cache_file.parent), delete=False) as f:
6853             pickle.dump(new_cache, f, protocol=4)
6854         os.replace(f.name, cache_file)
6855     except OSError:
6856         pass
6857
6858
6859 def patch_click() -> None:
6860     """Make Click not crash.
6861
6862     On certain misconfigured environments, Python 3 selects the ASCII encoding as the
6863     default which restricts paths that it can access during the lifetime of the
6864     application.  Click refuses to work in this scenario by raising a RuntimeError.
6865
6866     In case of Black the likelihood that non-ASCII characters are going to be used in
6867     file paths is minimal since it's Python source code.  Moreover, this crash was
6868     spurious on Python 3.7 thanks to PEP 538 and PEP 540.
6869     """
6870     try:
6871         from click import core
6872         from click import _unicodefun  # type: ignore
6873     except ModuleNotFoundError:
6874         return
6875
6876     for module in (core, _unicodefun):
6877         if hasattr(module, "_verify_python3_env"):
6878             module._verify_python3_env = lambda: None
6879
6880
6881 def patched_main() -> None:
6882     freeze_support()
6883     patch_click()
6884     main()
6885
6886
6887 def is_docstring(leaf: Leaf) -> bool:
6888     if not is_multiline_string(leaf):
6889         # For the purposes of docstring re-indentation, we don't need to do anything
6890         # with single-line docstrings.
6891         return False
6892
6893     if prev_siblings_are(
6894         leaf.parent, [None, token.NEWLINE, token.INDENT, syms.simple_stmt]
6895     ):
6896         return True
6897
6898     # Multiline docstring on the same line as the `def`.
6899     if prev_siblings_are(leaf.parent, [syms.parameters, token.COLON, syms.simple_stmt]):
6900         # `syms.parameters` is only used in funcdefs and async_funcdefs in the Python
6901         # grammar. We're safe to return True without further checks.
6902         return True
6903
6904     return False
6905
6906
6907 def lines_with_leading_tabs_expanded(s: str) -> List[str]:
6908     """
6909     Splits string into lines and expands only leading tabs (following the normal
6910     Python rules)
6911     """
6912     lines = []
6913     for line in s.splitlines():
6914         # Find the index of the first non-whitespace character after a string of
6915         # whitespace that includes at least one tab
6916         match = re.match(r"\s*\t+\s*(\S)", line)
6917         if match:
6918             first_non_whitespace_idx = match.start(1)
6919
6920             lines.append(
6921                 line[:first_non_whitespace_idx].expandtabs()
6922                 + line[first_non_whitespace_idx:]
6923             )
6924         else:
6925             lines.append(line)
6926     return lines
6927
6928
6929 def fix_docstring(docstring: str, prefix: str) -> str:
6930     # https://www.python.org/dev/peps/pep-0257/#handling-docstring-indentation
6931     if not docstring:
6932         return ""
6933     lines = lines_with_leading_tabs_expanded(docstring)
6934     # Determine minimum indentation (first line doesn't count):
6935     indent = sys.maxsize
6936     for line in lines[1:]:
6937         stripped = line.lstrip()
6938         if stripped:
6939             indent = min(indent, len(line) - len(stripped))
6940     # Remove indentation (first line is special):
6941     trimmed = [lines[0].strip()]
6942     if indent < sys.maxsize:
6943         last_line_idx = len(lines) - 2
6944         for i, line in enumerate(lines[1:]):
6945             stripped_line = line[indent:].rstrip()
6946             if stripped_line or i == last_line_idx:
6947                 trimmed.append(prefix + stripped_line)
6948             else:
6949                 trimmed.append("")
6950     return "\n".join(trimmed)
6951
6952
6953 if __name__ == "__main__":
6954     patched_main()