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

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