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

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