]> 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:

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