]> git.madduck.net Git - etc/vim.git/blob - black.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:

71f42ef307194f3febbd336c2c70597b25eafe5c
[etc/vim.git] / black.py
1 import ast
2 import asyncio
3 from concurrent.futures import Executor, ProcessPoolExecutor
4 from contextlib import contextmanager
5 from datetime import datetime
6 from enum import Enum
7 from functools import lru_cache, partial, wraps
8 import io
9 import itertools
10 import logging
11 from multiprocessing import Manager, freeze_support
12 import os
13 from pathlib import Path
14 import pickle
15 import re
16 import signal
17 import sys
18 import tempfile
19 import tokenize
20 import traceback
21 from typing import (
22     Any,
23     Callable,
24     Collection,
25     Dict,
26     Generator,
27     Generic,
28     Iterable,
29     Iterator,
30     List,
31     Optional,
32     Pattern,
33     Sequence,
34     Set,
35     Tuple,
36     TypeVar,
37     Union,
38     cast,
39 )
40
41 from appdirs import user_cache_dir
42 from attr import dataclass, evolve, Factory
43 import click
44 import toml
45 from typed_ast import ast3, ast27
46
47 # lib2to3 fork
48 from blib2to3.pytree import Node, Leaf, type_repr
49 from blib2to3 import pygram, pytree
50 from blib2to3.pgen2 import driver, token
51 from blib2to3.pgen2.grammar import Grammar
52 from blib2to3.pgen2.parse import ParseError
53
54 from _version import get_versions
55
56 v = get_versions()
57 __version__ = v.get("closest-tag", v["version"])
58 __git_version__ = v.get("full-revisionid")
59
60 DEFAULT_LINE_LENGTH = 88
61 DEFAULT_EXCLUDES = (
62     r"/(\.eggs|\.git|\.hg|\.mypy_cache|\.nox|\.tox|\.venv|_build|buck-out|build|dist)/"
63 )
64 DEFAULT_INCLUDES = r"\.pyi?$"
65 CACHE_DIR = Path(user_cache_dir("black", version=__git_version__))
66
67
68 # types
69 FileContent = str
70 Encoding = str
71 NewLine = str
72 Depth = int
73 NodeType = int
74 LeafID = int
75 Priority = int
76 Index = int
77 LN = Union[Leaf, Node]
78 SplitFunc = Callable[["Line", Collection["Feature"]], Iterator["Line"]]
79 Timestamp = float
80 FileSize = int
81 CacheInfo = Tuple[Timestamp, FileSize]
82 Cache = Dict[Path, CacheInfo]
83 out = partial(click.secho, bold=True, err=True)
84 err = partial(click.secho, fg="red", err=True)
85
86 pygram.initialize(CACHE_DIR)
87 syms = pygram.python_symbols
88
89
90 class NothingChanged(UserWarning):
91     """Raised when reformatted code is the same as source."""
92
93
94 class CannotSplit(Exception):
95     """A readable split that fits the allotted line length is impossible."""
96
97
98 class InvalidInput(ValueError):
99     """Raised when input source code fails all parse attempts."""
100
101
102 class WriteBack(Enum):
103     NO = 0
104     YES = 1
105     DIFF = 2
106     CHECK = 3
107
108     @classmethod
109     def from_configuration(cls, *, check: bool, diff: bool) -> "WriteBack":
110         if check and not diff:
111             return cls.CHECK
112
113         return cls.DIFF if diff else cls.YES
114
115
116 class Changed(Enum):
117     NO = 0
118     CACHED = 1
119     YES = 2
120
121
122 class TargetVersion(Enum):
123     PY27 = 2
124     PY33 = 3
125     PY34 = 4
126     PY35 = 5
127     PY36 = 6
128     PY37 = 7
129     PY38 = 8
130
131     def is_python2(self) -> bool:
132         return self is TargetVersion.PY27
133
134
135 PY36_VERSIONS = {TargetVersion.PY36, TargetVersion.PY37, TargetVersion.PY38}
136
137
138 class Feature(Enum):
139     # All string literals are unicode
140     UNICODE_LITERALS = 1
141     F_STRINGS = 2
142     NUMERIC_UNDERSCORES = 3
143     TRAILING_COMMA_IN_CALL = 4
144     TRAILING_COMMA_IN_DEF = 5
145     # The following two feature-flags are mutually exclusive, and exactly one should be
146     # set for every version of python.
147     ASYNC_IDENTIFIERS = 6
148     ASYNC_KEYWORDS = 7
149     ASSIGNMENT_EXPRESSIONS = 8
150     POS_ONLY_ARGUMENTS = 9
151
152
153 VERSION_TO_FEATURES: Dict[TargetVersion, Set[Feature]] = {
154     TargetVersion.PY27: {Feature.ASYNC_IDENTIFIERS},
155     TargetVersion.PY33: {Feature.UNICODE_LITERALS, Feature.ASYNC_IDENTIFIERS},
156     TargetVersion.PY34: {Feature.UNICODE_LITERALS, Feature.ASYNC_IDENTIFIERS},
157     TargetVersion.PY35: {
158         Feature.UNICODE_LITERALS,
159         Feature.TRAILING_COMMA_IN_CALL,
160         Feature.ASYNC_IDENTIFIERS,
161     },
162     TargetVersion.PY36: {
163         Feature.UNICODE_LITERALS,
164         Feature.F_STRINGS,
165         Feature.NUMERIC_UNDERSCORES,
166         Feature.TRAILING_COMMA_IN_CALL,
167         Feature.TRAILING_COMMA_IN_DEF,
168         Feature.ASYNC_IDENTIFIERS,
169     },
170     TargetVersion.PY37: {
171         Feature.UNICODE_LITERALS,
172         Feature.F_STRINGS,
173         Feature.NUMERIC_UNDERSCORES,
174         Feature.TRAILING_COMMA_IN_CALL,
175         Feature.TRAILING_COMMA_IN_DEF,
176         Feature.ASYNC_KEYWORDS,
177     },
178     TargetVersion.PY38: {
179         Feature.UNICODE_LITERALS,
180         Feature.F_STRINGS,
181         Feature.NUMERIC_UNDERSCORES,
182         Feature.TRAILING_COMMA_IN_CALL,
183         Feature.TRAILING_COMMA_IN_DEF,
184         Feature.ASYNC_KEYWORDS,
185         Feature.ASSIGNMENT_EXPRESSIONS,
186         Feature.POS_ONLY_ARGUMENTS,
187     },
188 }
189
190
191 @dataclass
192 class FileMode:
193     target_versions: Set[TargetVersion] = Factory(set)
194     line_length: int = DEFAULT_LINE_LENGTH
195     string_normalization: bool = True
196     is_pyi: bool = False
197
198     def get_cache_key(self) -> str:
199         if self.target_versions:
200             version_str = ",".join(
201                 str(version.value)
202                 for version in sorted(self.target_versions, key=lambda v: v.value)
203             )
204         else:
205             version_str = "-"
206         parts = [
207             version_str,
208             str(self.line_length),
209             str(int(self.string_normalization)),
210             str(int(self.is_pyi)),
211         ]
212         return ".".join(parts)
213
214
215 def supports_feature(target_versions: Set[TargetVersion], feature: Feature) -> bool:
216     return all(feature in VERSION_TO_FEATURES[version] for version in target_versions)
217
218
219 def read_pyproject_toml(
220     ctx: click.Context, param: click.Parameter, value: Union[str, int, bool, None]
221 ) -> Optional[str]:
222     """Inject Black configuration from "pyproject.toml" into defaults in `ctx`.
223
224     Returns the path to a successfully found and read configuration file, None
225     otherwise.
226     """
227     assert not isinstance(value, (int, bool)), "Invalid parameter type passed"
228     if not value:
229         root = find_project_root(ctx.params.get("src", ()))
230         path = root / "pyproject.toml"
231         if path.is_file():
232             value = str(path)
233         else:
234             return None
235
236     try:
237         pyproject_toml = toml.load(value)
238         config = pyproject_toml.get("tool", {}).get("black", {})
239     except (toml.TomlDecodeError, OSError) as e:
240         raise click.FileError(
241             filename=value, hint=f"Error reading configuration file: {e}"
242         )
243
244     if not config:
245         return None
246
247     if ctx.default_map is None:
248         ctx.default_map = {}
249     ctx.default_map.update(  # type: ignore  # bad types in .pyi
250         {k.replace("--", "").replace("-", "_"): v for k, v in config.items()}
251     )
252     return value
253
254
255 @click.command(context_settings=dict(help_option_names=["-h", "--help"]))
256 @click.option("-c", "--code", type=str, help="Format the code passed in as a string.")
257 @click.option(
258     "-l",
259     "--line-length",
260     type=int,
261     default=DEFAULT_LINE_LENGTH,
262     help="How many characters per line to allow.",
263     show_default=True,
264 )
265 @click.option(
266     "-t",
267     "--target-version",
268     type=click.Choice([v.name.lower() for v in TargetVersion]),
269     callback=lambda c, p, v: [TargetVersion[val.upper()] for val in v],
270     multiple=True,
271     help=(
272         "Python versions that should be supported by Black's output. [default: "
273         "per-file auto-detection]"
274     ),
275 )
276 @click.option(
277     "--py36",
278     is_flag=True,
279     help=(
280         "Allow using Python 3.6-only syntax on all input files.  This will put "
281         "trailing commas in function signatures and calls also after *args and "
282         "**kwargs. Deprecated; use --target-version instead. "
283         "[default: per-file auto-detection]"
284     ),
285 )
286 @click.option(
287     "--pyi",
288     is_flag=True,
289     help=(
290         "Format all input files like typing stubs regardless of file extension "
291         "(useful when piping source on standard input)."
292     ),
293 )
294 @click.option(
295     "-S",
296     "--skip-string-normalization",
297     is_flag=True,
298     help="Don't normalize string quotes or prefixes.",
299 )
300 @click.option(
301     "--check",
302     is_flag=True,
303     help=(
304         "Don't write the files back, just return the status.  Return code 0 "
305         "means nothing would change.  Return code 1 means some files would be "
306         "reformatted.  Return code 123 means there was an internal error."
307     ),
308 )
309 @click.option(
310     "--diff",
311     is_flag=True,
312     help="Don't write the files back, just output a diff for each file on stdout.",
313 )
314 @click.option(
315     "--fast/--safe",
316     is_flag=True,
317     help="If --fast given, skip temporary sanity checks. [default: --safe]",
318 )
319 @click.option(
320     "--include",
321     type=str,
322     default=DEFAULT_INCLUDES,
323     help=(
324         "A regular expression that matches files and directories that should be "
325         "included on recursive searches.  An empty value means all files are "
326         "included regardless of the name.  Use forward slashes for directories on "
327         "all platforms (Windows, too).  Exclusions are calculated first, inclusions "
328         "later."
329     ),
330     show_default=True,
331 )
332 @click.option(
333     "--exclude",
334     type=str,
335     default=DEFAULT_EXCLUDES,
336     help=(
337         "A regular expression that matches files and directories that should be "
338         "excluded on recursive searches.  An empty value means no paths are excluded. "
339         "Use forward slashes for directories on all platforms (Windows, too).  "
340         "Exclusions are calculated first, inclusions later."
341     ),
342     show_default=True,
343 )
344 @click.option(
345     "-q",
346     "--quiet",
347     is_flag=True,
348     help=(
349         "Don't emit non-error messages to stderr. Errors are still emitted; "
350         "silence those with 2>/dev/null."
351     ),
352 )
353 @click.option(
354     "-v",
355     "--verbose",
356     is_flag=True,
357     help=(
358         "Also emit messages to stderr about files that were not changed or were "
359         "ignored due to --exclude=."
360     ),
361 )
362 @click.version_option(version=__version__)
363 @click.argument(
364     "src",
365     nargs=-1,
366     type=click.Path(
367         exists=True, file_okay=True, dir_okay=True, readable=True, allow_dash=True
368     ),
369     is_eager=True,
370 )
371 @click.option(
372     "--config",
373     type=click.Path(
374         exists=False, file_okay=True, dir_okay=False, readable=True, allow_dash=False
375     ),
376     is_eager=True,
377     callback=read_pyproject_toml,
378     help="Read configuration from PATH.",
379 )
380 @click.pass_context
381 def main(
382     ctx: click.Context,
383     code: Optional[str],
384     line_length: int,
385     target_version: List[TargetVersion],
386     check: bool,
387     diff: bool,
388     fast: bool,
389     pyi: bool,
390     py36: bool,
391     skip_string_normalization: bool,
392     quiet: bool,
393     verbose: bool,
394     include: str,
395     exclude: str,
396     src: Tuple[str],
397     config: Optional[str],
398 ) -> None:
399     """The uncompromising code formatter."""
400     write_back = WriteBack.from_configuration(check=check, diff=diff)
401     if target_version:
402         if py36:
403             err(f"Cannot use both --target-version and --py36")
404             ctx.exit(2)
405         else:
406             versions = set(target_version)
407     elif py36:
408         err(
409             "--py36 is deprecated and will be removed in a future version. "
410             "Use --target-version py36 instead."
411         )
412         versions = PY36_VERSIONS
413     else:
414         # We'll autodetect later.
415         versions = set()
416     mode = FileMode(
417         target_versions=versions,
418         line_length=line_length,
419         is_pyi=pyi,
420         string_normalization=not skip_string_normalization,
421     )
422     if config and verbose:
423         out(f"Using configuration from {config}.", bold=False, fg="blue")
424     if code is not None:
425         print(format_str(code, mode=mode))
426         ctx.exit(0)
427     try:
428         include_regex = re_compile_maybe_verbose(include)
429     except re.error:
430         err(f"Invalid regular expression for include given: {include!r}")
431         ctx.exit(2)
432     try:
433         exclude_regex = re_compile_maybe_verbose(exclude)
434     except re.error:
435         err(f"Invalid regular expression for exclude given: {exclude!r}")
436         ctx.exit(2)
437     report = Report(check=check, quiet=quiet, verbose=verbose)
438     root = find_project_root(src)
439     sources: Set[Path] = set()
440     path_empty(src, quiet, verbose, ctx)
441     for s in src:
442         p = Path(s)
443         if p.is_dir():
444             sources.update(
445                 gen_python_files_in_dir(p, root, include_regex, exclude_regex, report)
446             )
447         elif p.is_file() or s == "-":
448             # if a file was explicitly given, we don't care about its extension
449             sources.add(p)
450         else:
451             err(f"invalid path: {s}")
452     if len(sources) == 0:
453         if verbose or not quiet:
454             out("No Python files are present to be formatted. Nothing to do 😴")
455         ctx.exit(0)
456
457     if len(sources) == 1:
458         reformat_one(
459             src=sources.pop(),
460             fast=fast,
461             write_back=write_back,
462             mode=mode,
463             report=report,
464         )
465     else:
466         reformat_many(
467             sources=sources, fast=fast, write_back=write_back, mode=mode, report=report
468         )
469
470     if verbose or not quiet:
471         out("Oh no! 💥 💔 💥" if report.return_code else "All done! ✨ 🍰 ✨")
472         click.secho(str(report), err=True)
473     ctx.exit(report.return_code)
474
475
476 def path_empty(src: Tuple[str], quiet: bool, verbose: bool, ctx: click.Context) -> None:
477     """
478     Exit if there is no `src` provided for formatting
479     """
480     if not src:
481         if verbose or not quiet:
482             out("No Path provided. Nothing to do 😴")
483             ctx.exit(0)
484
485
486 def reformat_one(
487     src: Path, fast: bool, write_back: WriteBack, mode: FileMode, report: "Report"
488 ) -> None:
489     """Reformat a single file under `src` without spawning child processes.
490
491     `fast`, `write_back`, and `mode` options are passed to
492     :func:`format_file_in_place` or :func:`format_stdin_to_stdout`.
493     """
494     try:
495         changed = Changed.NO
496         if not src.is_file() and str(src) == "-":
497             if format_stdin_to_stdout(fast=fast, write_back=write_back, mode=mode):
498                 changed = Changed.YES
499         else:
500             cache: Cache = {}
501             if write_back != WriteBack.DIFF:
502                 cache = read_cache(mode)
503                 res_src = src.resolve()
504                 if res_src in cache and cache[res_src] == get_cache_info(res_src):
505                     changed = Changed.CACHED
506             if changed is not Changed.CACHED and format_file_in_place(
507                 src, fast=fast, write_back=write_back, mode=mode
508             ):
509                 changed = Changed.YES
510             if (write_back is WriteBack.YES and changed is not Changed.CACHED) or (
511                 write_back is WriteBack.CHECK and changed is Changed.NO
512             ):
513                 write_cache(cache, [src], mode)
514         report.done(src, changed)
515     except Exception as exc:
516         report.failed(src, str(exc))
517
518
519 def reformat_many(
520     sources: Set[Path],
521     fast: bool,
522     write_back: WriteBack,
523     mode: FileMode,
524     report: "Report",
525 ) -> None:
526     """Reformat multiple files using a ProcessPoolExecutor."""
527     loop = asyncio.get_event_loop()
528     worker_count = os.cpu_count()
529     if sys.platform == "win32":
530         # Work around https://bugs.python.org/issue26903
531         worker_count = min(worker_count, 61)
532     executor = ProcessPoolExecutor(max_workers=worker_count)
533     try:
534         loop.run_until_complete(
535             schedule_formatting(
536                 sources=sources,
537                 fast=fast,
538                 write_back=write_back,
539                 mode=mode,
540                 report=report,
541                 loop=loop,
542                 executor=executor,
543             )
544         )
545     finally:
546         shutdown(loop)
547         executor.shutdown()
548
549
550 async def schedule_formatting(
551     sources: Set[Path],
552     fast: bool,
553     write_back: WriteBack,
554     mode: FileMode,
555     report: "Report",
556     loop: asyncio.AbstractEventLoop,
557     executor: Executor,
558 ) -> None:
559     """Run formatting of `sources` in parallel using the provided `executor`.
560
561     (Use ProcessPoolExecutors for actual parallelism.)
562
563     `write_back`, `fast`, and `mode` options are passed to
564     :func:`format_file_in_place`.
565     """
566     cache: Cache = {}
567     if write_back != WriteBack.DIFF:
568         cache = read_cache(mode)
569         sources, cached = filter_cached(cache, sources)
570         for src in sorted(cached):
571             report.done(src, Changed.CACHED)
572     if not sources:
573         return
574
575     cancelled = []
576     sources_to_cache = []
577     lock = None
578     if write_back == WriteBack.DIFF:
579         # For diff output, we need locks to ensure we don't interleave output
580         # from different processes.
581         manager = Manager()
582         lock = manager.Lock()
583     tasks = {
584         asyncio.ensure_future(
585             loop.run_in_executor(
586                 executor, format_file_in_place, src, fast, mode, write_back, lock
587             )
588         ): src
589         for src in sorted(sources)
590     }
591     pending: Iterable[asyncio.Future] = tasks.keys()
592     try:
593         loop.add_signal_handler(signal.SIGINT, cancel, pending)
594         loop.add_signal_handler(signal.SIGTERM, cancel, pending)
595     except NotImplementedError:
596         # There are no good alternatives for these on Windows.
597         pass
598     while pending:
599         done, _ = await asyncio.wait(pending, return_when=asyncio.FIRST_COMPLETED)
600         for task in done:
601             src = tasks.pop(task)
602             if task.cancelled():
603                 cancelled.append(task)
604             elif task.exception():
605                 report.failed(src, str(task.exception()))
606             else:
607                 changed = Changed.YES if task.result() else Changed.NO
608                 # If the file was written back or was successfully checked as
609                 # well-formatted, store this information in the cache.
610                 if write_back is WriteBack.YES or (
611                     write_back is WriteBack.CHECK and changed is Changed.NO
612                 ):
613                     sources_to_cache.append(src)
614                 report.done(src, changed)
615     if cancelled:
616         await asyncio.gather(*cancelled, loop=loop, return_exceptions=True)
617     if sources_to_cache:
618         write_cache(cache, sources_to_cache, mode)
619
620
621 def format_file_in_place(
622     src: Path,
623     fast: bool,
624     mode: FileMode,
625     write_back: WriteBack = WriteBack.NO,
626     lock: Any = None,  # multiprocessing.Manager().Lock() is some crazy proxy
627 ) -> bool:
628     """Format file under `src` path. Return True if changed.
629
630     If `write_back` is DIFF, write a diff to stdout. If it is YES, write reformatted
631     code to the file.
632     `mode` and `fast` options are passed to :func:`format_file_contents`.
633     """
634     if src.suffix == ".pyi":
635         mode = evolve(mode, is_pyi=True)
636
637     then = datetime.utcfromtimestamp(src.stat().st_mtime)
638     with open(src, "rb") as buf:
639         src_contents, encoding, newline = decode_bytes(buf.read())
640     try:
641         dst_contents = format_file_contents(src_contents, fast=fast, mode=mode)
642     except NothingChanged:
643         return False
644
645     if write_back == write_back.YES:
646         with open(src, "w", encoding=encoding, newline=newline) as f:
647             f.write(dst_contents)
648     elif write_back == write_back.DIFF:
649         now = datetime.utcnow()
650         src_name = f"{src}\t{then} +0000"
651         dst_name = f"{src}\t{now} +0000"
652         diff_contents = diff(src_contents, dst_contents, src_name, dst_name)
653
654         with lock or nullcontext():
655             f = io.TextIOWrapper(
656                 sys.stdout.buffer,
657                 encoding=encoding,
658                 newline=newline,
659                 write_through=True,
660             )
661             f.write(diff_contents)
662             f.detach()
663
664     return True
665
666
667 def format_stdin_to_stdout(
668     fast: bool, *, write_back: WriteBack = WriteBack.NO, mode: FileMode
669 ) -> bool:
670     """Format file on stdin. Return True if changed.
671
672     If `write_back` is YES, write reformatted code back to stdout. If it is DIFF,
673     write a diff to stdout. The `mode` argument is passed to
674     :func:`format_file_contents`.
675     """
676     then = datetime.utcnow()
677     src, encoding, newline = decode_bytes(sys.stdin.buffer.read())
678     dst = src
679     try:
680         dst = format_file_contents(src, fast=fast, mode=mode)
681         return True
682
683     except NothingChanged:
684         return False
685
686     finally:
687         f = io.TextIOWrapper(
688             sys.stdout.buffer, encoding=encoding, newline=newline, write_through=True
689         )
690         if write_back == WriteBack.YES:
691             f.write(dst)
692         elif write_back == WriteBack.DIFF:
693             now = datetime.utcnow()
694             src_name = f"STDIN\t{then} +0000"
695             dst_name = f"STDOUT\t{now} +0000"
696             f.write(diff(src, dst, src_name, dst_name))
697         f.detach()
698
699
700 def format_file_contents(
701     src_contents: str, *, fast: bool, mode: FileMode
702 ) -> FileContent:
703     """Reformat contents a file and return new contents.
704
705     If `fast` is False, additionally confirm that the reformatted code is
706     valid by calling :func:`assert_equivalent` and :func:`assert_stable` on it.
707     `mode` is passed to :func:`format_str`.
708     """
709     if src_contents.strip() == "":
710         raise NothingChanged
711
712     dst_contents = format_str(src_contents, mode=mode)
713     if src_contents == dst_contents:
714         raise NothingChanged
715
716     if not fast:
717         assert_equivalent(src_contents, dst_contents)
718         assert_stable(src_contents, dst_contents, mode=mode)
719     return dst_contents
720
721
722 def format_str(src_contents: str, *, mode: FileMode) -> FileContent:
723     """Reformat a string and return new contents.
724
725     `mode` determines formatting options, such as how many characters per line are
726     allowed.
727     """
728     src_node = lib2to3_parse(src_contents.lstrip(), mode.target_versions)
729     dst_contents = []
730     future_imports = get_future_imports(src_node)
731     if mode.target_versions:
732         versions = mode.target_versions
733     else:
734         versions = detect_target_versions(src_node)
735     normalize_fmt_off(src_node)
736     lines = LineGenerator(
737         remove_u_prefix="unicode_literals" in future_imports
738         or supports_feature(versions, Feature.UNICODE_LITERALS),
739         is_pyi=mode.is_pyi,
740         normalize_strings=mode.string_normalization,
741     )
742     elt = EmptyLineTracker(is_pyi=mode.is_pyi)
743     empty_line = Line()
744     after = 0
745     split_line_features = {
746         feature
747         for feature in {Feature.TRAILING_COMMA_IN_CALL, Feature.TRAILING_COMMA_IN_DEF}
748         if supports_feature(versions, feature)
749     }
750     for current_line in lines.visit(src_node):
751         for _ in range(after):
752             dst_contents.append(str(empty_line))
753         before, after = elt.maybe_empty_lines(current_line)
754         for _ in range(before):
755             dst_contents.append(str(empty_line))
756         for line in split_line(
757             current_line, line_length=mode.line_length, features=split_line_features
758         ):
759             dst_contents.append(str(line))
760     return "".join(dst_contents)
761
762
763 def decode_bytes(src: bytes) -> Tuple[FileContent, Encoding, NewLine]:
764     """Return a tuple of (decoded_contents, encoding, newline).
765
766     `newline` is either CRLF or LF but `decoded_contents` is decoded with
767     universal newlines (i.e. only contains LF).
768     """
769     srcbuf = io.BytesIO(src)
770     encoding, lines = tokenize.detect_encoding(srcbuf.readline)
771     if not lines:
772         return "", encoding, "\n"
773
774     newline = "\r\n" if b"\r\n" == lines[0][-2:] else "\n"
775     srcbuf.seek(0)
776     with io.TextIOWrapper(srcbuf, encoding) as tiow:
777         return tiow.read(), encoding, newline
778
779
780 def get_grammars(target_versions: Set[TargetVersion]) -> List[Grammar]:
781     if not target_versions:
782         # No target_version specified, so try all grammars.
783         return [
784             # Python 3.7+
785             pygram.python_grammar_no_print_statement_no_exec_statement_async_keywords,
786             # Python 3.0-3.6
787             pygram.python_grammar_no_print_statement_no_exec_statement,
788             # Python 2.7 with future print_function import
789             pygram.python_grammar_no_print_statement,
790             # Python 2.7
791             pygram.python_grammar,
792         ]
793     elif all(version.is_python2() for version in target_versions):
794         # Python 2-only code, so try Python 2 grammars.
795         return [
796             # Python 2.7 with future print_function import
797             pygram.python_grammar_no_print_statement,
798             # Python 2.7
799             pygram.python_grammar,
800         ]
801     else:
802         # Python 3-compatible code, so only try Python 3 grammar.
803         grammars = []
804         # If we have to parse both, try to parse async as a keyword first
805         if not supports_feature(target_versions, Feature.ASYNC_IDENTIFIERS):
806             # Python 3.7+
807             grammars.append(
808                 pygram.python_grammar_no_print_statement_no_exec_statement_async_keywords  # noqa: B950
809             )
810         if not supports_feature(target_versions, Feature.ASYNC_KEYWORDS):
811             # Python 3.0-3.6
812             grammars.append(pygram.python_grammar_no_print_statement_no_exec_statement)
813         # At least one of the above branches must have been taken, because every Python
814         # version has exactly one of the two 'ASYNC_*' flags
815         return grammars
816
817
818 def lib2to3_parse(src_txt: str, target_versions: Iterable[TargetVersion] = ()) -> Node:
819     """Given a string with source, return the lib2to3 Node."""
820     if src_txt[-1:] != "\n":
821         src_txt += "\n"
822
823     for grammar in get_grammars(set(target_versions)):
824         drv = driver.Driver(grammar, pytree.convert)
825         try:
826             result = drv.parse_string(src_txt, True)
827             break
828
829         except ParseError as pe:
830             lineno, column = pe.context[1]
831             lines = src_txt.splitlines()
832             try:
833                 faulty_line = lines[lineno - 1]
834             except IndexError:
835                 faulty_line = "<line number missing in source>"
836             exc = InvalidInput(f"Cannot parse: {lineno}:{column}: {faulty_line}")
837     else:
838         raise exc from None
839
840     if isinstance(result, Leaf):
841         result = Node(syms.file_input, [result])
842     return result
843
844
845 def lib2to3_unparse(node: Node) -> str:
846     """Given a lib2to3 node, return its string representation."""
847     code = str(node)
848     return code
849
850
851 T = TypeVar("T")
852
853
854 class Visitor(Generic[T]):
855     """Basic lib2to3 visitor that yields things of type `T` on `visit()`."""
856
857     def visit(self, node: LN) -> Iterator[T]:
858         """Main method to visit `node` and its children.
859
860         It tries to find a `visit_*()` method for the given `node.type`, like
861         `visit_simple_stmt` for Node objects or `visit_INDENT` for Leaf objects.
862         If no dedicated `visit_*()` method is found, chooses `visit_default()`
863         instead.
864
865         Then yields objects of type `T` from the selected visitor.
866         """
867         if node.type < 256:
868             name = token.tok_name[node.type]
869         else:
870             name = type_repr(node.type)
871         yield from getattr(self, f"visit_{name}", self.visit_default)(node)
872
873     def visit_default(self, node: LN) -> Iterator[T]:
874         """Default `visit_*()` implementation. Recurses to children of `node`."""
875         if isinstance(node, Node):
876             for child in node.children:
877                 yield from self.visit(child)
878
879
880 @dataclass
881 class DebugVisitor(Visitor[T]):
882     tree_depth: int = 0
883
884     def visit_default(self, node: LN) -> Iterator[T]:
885         indent = " " * (2 * self.tree_depth)
886         if isinstance(node, Node):
887             _type = type_repr(node.type)
888             out(f"{indent}{_type}", fg="yellow")
889             self.tree_depth += 1
890             for child in node.children:
891                 yield from self.visit(child)
892
893             self.tree_depth -= 1
894             out(f"{indent}/{_type}", fg="yellow", bold=False)
895         else:
896             _type = token.tok_name.get(node.type, str(node.type))
897             out(f"{indent}{_type}", fg="blue", nl=False)
898             if node.prefix:
899                 # We don't have to handle prefixes for `Node` objects since
900                 # that delegates to the first child anyway.
901                 out(f" {node.prefix!r}", fg="green", bold=False, nl=False)
902             out(f" {node.value!r}", fg="blue", bold=False)
903
904     @classmethod
905     def show(cls, code: Union[str, Leaf, Node]) -> None:
906         """Pretty-print the lib2to3 AST of a given string of `code`.
907
908         Convenience method for debugging.
909         """
910         v: DebugVisitor[None] = DebugVisitor()
911         if isinstance(code, str):
912             code = lib2to3_parse(code)
913         list(v.visit(code))
914
915
916 WHITESPACE = {token.DEDENT, token.INDENT, token.NEWLINE}
917 STATEMENT = {
918     syms.if_stmt,
919     syms.while_stmt,
920     syms.for_stmt,
921     syms.try_stmt,
922     syms.except_clause,
923     syms.with_stmt,
924     syms.funcdef,
925     syms.classdef,
926 }
927 STANDALONE_COMMENT = 153
928 token.tok_name[STANDALONE_COMMENT] = "STANDALONE_COMMENT"
929 LOGIC_OPERATORS = {"and", "or"}
930 COMPARATORS = {
931     token.LESS,
932     token.GREATER,
933     token.EQEQUAL,
934     token.NOTEQUAL,
935     token.LESSEQUAL,
936     token.GREATEREQUAL,
937 }
938 MATH_OPERATORS = {
939     token.VBAR,
940     token.CIRCUMFLEX,
941     token.AMPER,
942     token.LEFTSHIFT,
943     token.RIGHTSHIFT,
944     token.PLUS,
945     token.MINUS,
946     token.STAR,
947     token.SLASH,
948     token.DOUBLESLASH,
949     token.PERCENT,
950     token.AT,
951     token.TILDE,
952     token.DOUBLESTAR,
953 }
954 STARS = {token.STAR, token.DOUBLESTAR}
955 VARARGS_SPECIALS = STARS | {token.SLASH}
956 VARARGS_PARENTS = {
957     syms.arglist,
958     syms.argument,  # double star in arglist
959     syms.trailer,  # single argument to call
960     syms.typedargslist,
961     syms.varargslist,  # lambdas
962 }
963 UNPACKING_PARENTS = {
964     syms.atom,  # single element of a list or set literal
965     syms.dictsetmaker,
966     syms.listmaker,
967     syms.testlist_gexp,
968     syms.testlist_star_expr,
969 }
970 TEST_DESCENDANTS = {
971     syms.test,
972     syms.lambdef,
973     syms.or_test,
974     syms.and_test,
975     syms.not_test,
976     syms.comparison,
977     syms.star_expr,
978     syms.expr,
979     syms.xor_expr,
980     syms.and_expr,
981     syms.shift_expr,
982     syms.arith_expr,
983     syms.trailer,
984     syms.term,
985     syms.power,
986 }
987 ASSIGNMENTS = {
988     "=",
989     "+=",
990     "-=",
991     "*=",
992     "@=",
993     "/=",
994     "%=",
995     "&=",
996     "|=",
997     "^=",
998     "<<=",
999     ">>=",
1000     "**=",
1001     "//=",
1002 }
1003 COMPREHENSION_PRIORITY = 20
1004 COMMA_PRIORITY = 18
1005 TERNARY_PRIORITY = 16
1006 LOGIC_PRIORITY = 14
1007 STRING_PRIORITY = 12
1008 COMPARATOR_PRIORITY = 10
1009 MATH_PRIORITIES = {
1010     token.VBAR: 9,
1011     token.CIRCUMFLEX: 8,
1012     token.AMPER: 7,
1013     token.LEFTSHIFT: 6,
1014     token.RIGHTSHIFT: 6,
1015     token.PLUS: 5,
1016     token.MINUS: 5,
1017     token.STAR: 4,
1018     token.SLASH: 4,
1019     token.DOUBLESLASH: 4,
1020     token.PERCENT: 4,
1021     token.AT: 4,
1022     token.TILDE: 3,
1023     token.DOUBLESTAR: 2,
1024 }
1025 DOT_PRIORITY = 1
1026
1027
1028 @dataclass
1029 class BracketTracker:
1030     """Keeps track of brackets on a line."""
1031
1032     depth: int = 0
1033     bracket_match: Dict[Tuple[Depth, NodeType], Leaf] = Factory(dict)
1034     delimiters: Dict[LeafID, Priority] = Factory(dict)
1035     previous: Optional[Leaf] = None
1036     _for_loop_depths: List[int] = Factory(list)
1037     _lambda_argument_depths: List[int] = Factory(list)
1038
1039     def mark(self, leaf: Leaf) -> None:
1040         """Mark `leaf` with bracket-related metadata. Keep track of delimiters.
1041
1042         All leaves receive an int `bracket_depth` field that stores how deep
1043         within brackets a given leaf is. 0 means there are no enclosing brackets
1044         that started on this line.
1045
1046         If a leaf is itself a closing bracket, it receives an `opening_bracket`
1047         field that it forms a pair with. This is a one-directional link to
1048         avoid reference cycles.
1049
1050         If a leaf is a delimiter (a token on which Black can split the line if
1051         needed) and it's on depth 0, its `id()` is stored in the tracker's
1052         `delimiters` field.
1053         """
1054         if leaf.type == token.COMMENT:
1055             return
1056
1057         self.maybe_decrement_after_for_loop_variable(leaf)
1058         self.maybe_decrement_after_lambda_arguments(leaf)
1059         if leaf.type in CLOSING_BRACKETS:
1060             self.depth -= 1
1061             opening_bracket = self.bracket_match.pop((self.depth, leaf.type))
1062             leaf.opening_bracket = opening_bracket
1063         leaf.bracket_depth = self.depth
1064         if self.depth == 0:
1065             delim = is_split_before_delimiter(leaf, self.previous)
1066             if delim and self.previous is not None:
1067                 self.delimiters[id(self.previous)] = delim
1068             else:
1069                 delim = is_split_after_delimiter(leaf, self.previous)
1070                 if delim:
1071                     self.delimiters[id(leaf)] = delim
1072         if leaf.type in OPENING_BRACKETS:
1073             self.bracket_match[self.depth, BRACKET[leaf.type]] = leaf
1074             self.depth += 1
1075         self.previous = leaf
1076         self.maybe_increment_lambda_arguments(leaf)
1077         self.maybe_increment_for_loop_variable(leaf)
1078
1079     def any_open_brackets(self) -> bool:
1080         """Return True if there is an yet unmatched open bracket on the line."""
1081         return bool(self.bracket_match)
1082
1083     def max_delimiter_priority(self, exclude: Iterable[LeafID] = ()) -> Priority:
1084         """Return the highest priority of a delimiter found on the line.
1085
1086         Values are consistent with what `is_split_*_delimiter()` return.
1087         Raises ValueError on no delimiters.
1088         """
1089         return max(v for k, v in self.delimiters.items() if k not in exclude)
1090
1091     def delimiter_count_with_priority(self, priority: Priority = 0) -> int:
1092         """Return the number of delimiters with the given `priority`.
1093
1094         If no `priority` is passed, defaults to max priority on the line.
1095         """
1096         if not self.delimiters:
1097             return 0
1098
1099         priority = priority or self.max_delimiter_priority()
1100         return sum(1 for p in self.delimiters.values() if p == priority)
1101
1102     def maybe_increment_for_loop_variable(self, leaf: Leaf) -> bool:
1103         """In a for loop, or comprehension, the variables are often unpacks.
1104
1105         To avoid splitting on the comma in this situation, increase the depth of
1106         tokens between `for` and `in`.
1107         """
1108         if leaf.type == token.NAME and leaf.value == "for":
1109             self.depth += 1
1110             self._for_loop_depths.append(self.depth)
1111             return True
1112
1113         return False
1114
1115     def maybe_decrement_after_for_loop_variable(self, leaf: Leaf) -> bool:
1116         """See `maybe_increment_for_loop_variable` above for explanation."""
1117         if (
1118             self._for_loop_depths
1119             and self._for_loop_depths[-1] == self.depth
1120             and leaf.type == token.NAME
1121             and leaf.value == "in"
1122         ):
1123             self.depth -= 1
1124             self._for_loop_depths.pop()
1125             return True
1126
1127         return False
1128
1129     def maybe_increment_lambda_arguments(self, leaf: Leaf) -> bool:
1130         """In a lambda expression, there might be more than one argument.
1131
1132         To avoid splitting on the comma in this situation, increase the depth of
1133         tokens between `lambda` and `:`.
1134         """
1135         if leaf.type == token.NAME and leaf.value == "lambda":
1136             self.depth += 1
1137             self._lambda_argument_depths.append(self.depth)
1138             return True
1139
1140         return False
1141
1142     def maybe_decrement_after_lambda_arguments(self, leaf: Leaf) -> bool:
1143         """See `maybe_increment_lambda_arguments` above for explanation."""
1144         if (
1145             self._lambda_argument_depths
1146             and self._lambda_argument_depths[-1] == self.depth
1147             and leaf.type == token.COLON
1148         ):
1149             self.depth -= 1
1150             self._lambda_argument_depths.pop()
1151             return True
1152
1153         return False
1154
1155     def get_open_lsqb(self) -> Optional[Leaf]:
1156         """Return the most recent opening square bracket (if any)."""
1157         return self.bracket_match.get((self.depth - 1, token.RSQB))
1158
1159
1160 @dataclass
1161 class Line:
1162     """Holds leaves and comments. Can be printed with `str(line)`."""
1163
1164     depth: int = 0
1165     leaves: List[Leaf] = Factory(list)
1166     comments: Dict[LeafID, List[Leaf]] = Factory(dict)  # keys ordered like `leaves`
1167     bracket_tracker: BracketTracker = Factory(BracketTracker)
1168     inside_brackets: bool = False
1169     should_explode: bool = False
1170
1171     def append(self, leaf: Leaf, preformatted: bool = False) -> None:
1172         """Add a new `leaf` to the end of the line.
1173
1174         Unless `preformatted` is True, the `leaf` will receive a new consistent
1175         whitespace prefix and metadata applied by :class:`BracketTracker`.
1176         Trailing commas are maybe removed, unpacked for loop variables are
1177         demoted from being delimiters.
1178
1179         Inline comments are put aside.
1180         """
1181         has_value = leaf.type in BRACKETS or bool(leaf.value.strip())
1182         if not has_value:
1183             return
1184
1185         if token.COLON == leaf.type and self.is_class_paren_empty:
1186             del self.leaves[-2:]
1187         if self.leaves and not preformatted:
1188             # Note: at this point leaf.prefix should be empty except for
1189             # imports, for which we only preserve newlines.
1190             leaf.prefix += whitespace(
1191                 leaf, complex_subscript=self.is_complex_subscript(leaf)
1192             )
1193         if self.inside_brackets or not preformatted:
1194             self.bracket_tracker.mark(leaf)
1195             self.maybe_remove_trailing_comma(leaf)
1196         if not self.append_comment(leaf):
1197             self.leaves.append(leaf)
1198
1199     def append_safe(self, leaf: Leaf, preformatted: bool = False) -> None:
1200         """Like :func:`append()` but disallow invalid standalone comment structure.
1201
1202         Raises ValueError when any `leaf` is appended after a standalone comment
1203         or when a standalone comment is not the first leaf on the line.
1204         """
1205         if self.bracket_tracker.depth == 0:
1206             if self.is_comment:
1207                 raise ValueError("cannot append to standalone comments")
1208
1209             if self.leaves and leaf.type == STANDALONE_COMMENT:
1210                 raise ValueError(
1211                     "cannot append standalone comments to a populated line"
1212                 )
1213
1214         self.append(leaf, preformatted=preformatted)
1215
1216     @property
1217     def is_comment(self) -> bool:
1218         """Is this line a standalone comment?"""
1219         return len(self.leaves) == 1 and self.leaves[0].type == STANDALONE_COMMENT
1220
1221     @property
1222     def is_decorator(self) -> bool:
1223         """Is this line a decorator?"""
1224         return bool(self) and self.leaves[0].type == token.AT
1225
1226     @property
1227     def is_import(self) -> bool:
1228         """Is this an import line?"""
1229         return bool(self) and is_import(self.leaves[0])
1230
1231     @property
1232     def is_class(self) -> bool:
1233         """Is this line a class definition?"""
1234         return (
1235             bool(self)
1236             and self.leaves[0].type == token.NAME
1237             and self.leaves[0].value == "class"
1238         )
1239
1240     @property
1241     def is_stub_class(self) -> bool:
1242         """Is this line a class definition with a body consisting only of "..."?"""
1243         return self.is_class and self.leaves[-3:] == [
1244             Leaf(token.DOT, ".") for _ in range(3)
1245         ]
1246
1247     @property
1248     def is_def(self) -> bool:
1249         """Is this a function definition? (Also returns True for async defs.)"""
1250         try:
1251             first_leaf = self.leaves[0]
1252         except IndexError:
1253             return False
1254
1255         try:
1256             second_leaf: Optional[Leaf] = self.leaves[1]
1257         except IndexError:
1258             second_leaf = None
1259         return (first_leaf.type == token.NAME and first_leaf.value == "def") or (
1260             first_leaf.type == token.ASYNC
1261             and second_leaf is not None
1262             and second_leaf.type == token.NAME
1263             and second_leaf.value == "def"
1264         )
1265
1266     @property
1267     def is_class_paren_empty(self) -> bool:
1268         """Is this a class with no base classes but using parentheses?
1269
1270         Those are unnecessary and should be removed.
1271         """
1272         return (
1273             bool(self)
1274             and len(self.leaves) == 4
1275             and self.is_class
1276             and self.leaves[2].type == token.LPAR
1277             and self.leaves[2].value == "("
1278             and self.leaves[3].type == token.RPAR
1279             and self.leaves[3].value == ")"
1280         )
1281
1282     @property
1283     def is_triple_quoted_string(self) -> bool:
1284         """Is the line a triple quoted string?"""
1285         return (
1286             bool(self)
1287             and self.leaves[0].type == token.STRING
1288             and self.leaves[0].value.startswith(('"""', "'''"))
1289         )
1290
1291     def contains_standalone_comments(self, depth_limit: int = sys.maxsize) -> bool:
1292         """If so, needs to be split before emitting."""
1293         for leaf in self.leaves:
1294             if leaf.type == STANDALONE_COMMENT:
1295                 if leaf.bracket_depth <= depth_limit:
1296                     return True
1297         return False
1298
1299     def contains_inner_type_comments(self) -> bool:
1300         ignored_ids = set()
1301         try:
1302             last_leaf = self.leaves[-1]
1303             ignored_ids.add(id(last_leaf))
1304             if last_leaf.type == token.COMMA or (
1305                 last_leaf.type == token.RPAR and not last_leaf.value
1306             ):
1307                 # When trailing commas or optional parens are inserted by Black for
1308                 # consistency, comments after the previous last element are not moved
1309                 # (they don't have to, rendering will still be correct).  So we ignore
1310                 # trailing commas and invisible.
1311                 last_leaf = self.leaves[-2]
1312                 ignored_ids.add(id(last_leaf))
1313         except IndexError:
1314             return False
1315
1316         for leaf_id, comments in self.comments.items():
1317             if leaf_id in ignored_ids:
1318                 continue
1319
1320             for comment in comments:
1321                 if is_type_comment(comment):
1322                     return True
1323
1324         return False
1325
1326     def contains_multiline_strings(self) -> bool:
1327         for leaf in self.leaves:
1328             if is_multiline_string(leaf):
1329                 return True
1330
1331         return False
1332
1333     def maybe_remove_trailing_comma(self, closing: Leaf) -> bool:
1334         """Remove trailing comma if there is one and it's safe."""
1335         if not (
1336             self.leaves
1337             and self.leaves[-1].type == token.COMMA
1338             and closing.type in CLOSING_BRACKETS
1339         ):
1340             return False
1341
1342         if closing.type == token.RBRACE:
1343             self.remove_trailing_comma()
1344             return True
1345
1346         if closing.type == token.RSQB:
1347             comma = self.leaves[-1]
1348             if comma.parent and comma.parent.type == syms.listmaker:
1349                 self.remove_trailing_comma()
1350                 return True
1351
1352         # For parens let's check if it's safe to remove the comma.
1353         # Imports are always safe.
1354         if self.is_import:
1355             self.remove_trailing_comma()
1356             return True
1357
1358         # Otherwise, if the trailing one is the only one, we might mistakenly
1359         # change a tuple into a different type by removing the comma.
1360         depth = closing.bracket_depth + 1
1361         commas = 0
1362         opening = closing.opening_bracket
1363         for _opening_index, leaf in enumerate(self.leaves):
1364             if leaf is opening:
1365                 break
1366
1367         else:
1368             return False
1369
1370         for leaf in self.leaves[_opening_index + 1 :]:
1371             if leaf is closing:
1372                 break
1373
1374             bracket_depth = leaf.bracket_depth
1375             if bracket_depth == depth and leaf.type == token.COMMA:
1376                 commas += 1
1377                 if leaf.parent and leaf.parent.type in {
1378                     syms.arglist,
1379                     syms.typedargslist,
1380                 }:
1381                     commas += 1
1382                     break
1383
1384         if commas > 1:
1385             self.remove_trailing_comma()
1386             return True
1387
1388         return False
1389
1390     def append_comment(self, comment: Leaf) -> bool:
1391         """Add an inline or standalone comment to the line."""
1392         if (
1393             comment.type == STANDALONE_COMMENT
1394             and self.bracket_tracker.any_open_brackets()
1395         ):
1396             comment.prefix = ""
1397             return False
1398
1399         if comment.type != token.COMMENT:
1400             return False
1401
1402         if not self.leaves:
1403             comment.type = STANDALONE_COMMENT
1404             comment.prefix = ""
1405             return False
1406
1407         last_leaf = self.leaves[-1]
1408         if (
1409             last_leaf.type == token.RPAR
1410             and not last_leaf.value
1411             and last_leaf.parent
1412             and len(list(last_leaf.parent.leaves())) <= 3
1413             and not is_type_comment(comment)
1414         ):
1415             # Comments on an optional parens wrapping a single leaf should belong to
1416             # the wrapped node except if it's a type comment. Pinning the comment like
1417             # this avoids unstable formatting caused by comment migration.
1418             if len(self.leaves) < 2:
1419                 comment.type = STANDALONE_COMMENT
1420                 comment.prefix = ""
1421                 return False
1422             last_leaf = self.leaves[-2]
1423         self.comments.setdefault(id(last_leaf), []).append(comment)
1424         return True
1425
1426     def comments_after(self, leaf: Leaf) -> List[Leaf]:
1427         """Generate comments that should appear directly after `leaf`."""
1428         return self.comments.get(id(leaf), [])
1429
1430     def remove_trailing_comma(self) -> None:
1431         """Remove the trailing comma and moves the comments attached to it."""
1432         trailing_comma = self.leaves.pop()
1433         trailing_comma_comments = self.comments.pop(id(trailing_comma), [])
1434         self.comments.setdefault(id(self.leaves[-1]), []).extend(
1435             trailing_comma_comments
1436         )
1437
1438     def is_complex_subscript(self, leaf: Leaf) -> bool:
1439         """Return True iff `leaf` is part of a slice with non-trivial exprs."""
1440         open_lsqb = self.bracket_tracker.get_open_lsqb()
1441         if open_lsqb is None:
1442             return False
1443
1444         subscript_start = open_lsqb.next_sibling
1445
1446         if isinstance(subscript_start, Node):
1447             if subscript_start.type == syms.listmaker:
1448                 return False
1449
1450             if subscript_start.type == syms.subscriptlist:
1451                 subscript_start = child_towards(subscript_start, leaf)
1452         return subscript_start is not None and any(
1453             n.type in TEST_DESCENDANTS for n in subscript_start.pre_order()
1454         )
1455
1456     def __str__(self) -> str:
1457         """Render the line."""
1458         if not self:
1459             return "\n"
1460
1461         indent = "    " * self.depth
1462         leaves = iter(self.leaves)
1463         first = next(leaves)
1464         res = f"{first.prefix}{indent}{first.value}"
1465         for leaf in leaves:
1466             res += str(leaf)
1467         for comment in itertools.chain.from_iterable(self.comments.values()):
1468             res += str(comment)
1469         return res + "\n"
1470
1471     def __bool__(self) -> bool:
1472         """Return True if the line has leaves or comments."""
1473         return bool(self.leaves or self.comments)
1474
1475
1476 @dataclass
1477 class EmptyLineTracker:
1478     """Provides a stateful method that returns the number of potential extra
1479     empty lines needed before and after the currently processed line.
1480
1481     Note: this tracker works on lines that haven't been split yet.  It assumes
1482     the prefix of the first leaf consists of optional newlines.  Those newlines
1483     are consumed by `maybe_empty_lines()` and included in the computation.
1484     """
1485
1486     is_pyi: bool = False
1487     previous_line: Optional[Line] = None
1488     previous_after: int = 0
1489     previous_defs: List[int] = Factory(list)
1490
1491     def maybe_empty_lines(self, current_line: Line) -> Tuple[int, int]:
1492         """Return the number of extra empty lines before and after the `current_line`.
1493
1494         This is for separating `def`, `async def` and `class` with extra empty
1495         lines (two on module-level).
1496         """
1497         before, after = self._maybe_empty_lines(current_line)
1498         before = (
1499             # Black should not insert empty lines at the beginning
1500             # of the file
1501             0
1502             if self.previous_line is None
1503             else before - self.previous_after
1504         )
1505         self.previous_after = after
1506         self.previous_line = current_line
1507         return before, after
1508
1509     def _maybe_empty_lines(self, current_line: Line) -> Tuple[int, int]:
1510         max_allowed = 1
1511         if current_line.depth == 0:
1512             max_allowed = 1 if self.is_pyi else 2
1513         if current_line.leaves:
1514             # Consume the first leaf's extra newlines.
1515             first_leaf = current_line.leaves[0]
1516             before = first_leaf.prefix.count("\n")
1517             before = min(before, max_allowed)
1518             first_leaf.prefix = ""
1519         else:
1520             before = 0
1521         depth = current_line.depth
1522         while self.previous_defs and self.previous_defs[-1] >= depth:
1523             self.previous_defs.pop()
1524             if self.is_pyi:
1525                 before = 0 if depth else 1
1526             else:
1527                 before = 1 if depth else 2
1528         if current_line.is_decorator or current_line.is_def or current_line.is_class:
1529             return self._maybe_empty_lines_for_class_or_def(current_line, before)
1530
1531         if (
1532             self.previous_line
1533             and self.previous_line.is_import
1534             and not current_line.is_import
1535             and depth == self.previous_line.depth
1536         ):
1537             return (before or 1), 0
1538
1539         if (
1540             self.previous_line
1541             and self.previous_line.is_class
1542             and current_line.is_triple_quoted_string
1543         ):
1544             return before, 1
1545
1546         return before, 0
1547
1548     def _maybe_empty_lines_for_class_or_def(
1549         self, current_line: Line, before: int
1550     ) -> Tuple[int, int]:
1551         if not current_line.is_decorator:
1552             self.previous_defs.append(current_line.depth)
1553         if self.previous_line is None:
1554             # Don't insert empty lines before the first line in the file.
1555             return 0, 0
1556
1557         if self.previous_line.is_decorator:
1558             return 0, 0
1559
1560         if self.previous_line.depth < current_line.depth and (
1561             self.previous_line.is_class or self.previous_line.is_def
1562         ):
1563             return 0, 0
1564
1565         if (
1566             self.previous_line.is_comment
1567             and self.previous_line.depth == current_line.depth
1568             and before == 0
1569         ):
1570             return 0, 0
1571
1572         if self.is_pyi:
1573             if self.previous_line.depth > current_line.depth:
1574                 newlines = 1
1575             elif current_line.is_class or self.previous_line.is_class:
1576                 if current_line.is_stub_class and self.previous_line.is_stub_class:
1577                     # No blank line between classes with an empty body
1578                     newlines = 0
1579                 else:
1580                     newlines = 1
1581             elif current_line.is_def and not self.previous_line.is_def:
1582                 # Blank line between a block of functions and a block of non-functions
1583                 newlines = 1
1584             else:
1585                 newlines = 0
1586         else:
1587             newlines = 2
1588         if current_line.depth and newlines:
1589             newlines -= 1
1590         return newlines, 0
1591
1592
1593 @dataclass
1594 class LineGenerator(Visitor[Line]):
1595     """Generates reformatted Line objects.  Empty lines are not emitted.
1596
1597     Note: destroys the tree it's visiting by mutating prefixes of its leaves
1598     in ways that will no longer stringify to valid Python code on the tree.
1599     """
1600
1601     is_pyi: bool = False
1602     normalize_strings: bool = True
1603     current_line: Line = Factory(Line)
1604     remove_u_prefix: bool = False
1605
1606     def line(self, indent: int = 0) -> Iterator[Line]:
1607         """Generate a line.
1608
1609         If the line is empty, only emit if it makes sense.
1610         If the line is too long, split it first and then generate.
1611
1612         If any lines were generated, set up a new current_line.
1613         """
1614         if not self.current_line:
1615             self.current_line.depth += indent
1616             return  # Line is empty, don't emit. Creating a new one unnecessary.
1617
1618         complete_line = self.current_line
1619         self.current_line = Line(depth=complete_line.depth + indent)
1620         yield complete_line
1621
1622     def visit_default(self, node: LN) -> Iterator[Line]:
1623         """Default `visit_*()` implementation. Recurses to children of `node`."""
1624         if isinstance(node, Leaf):
1625             any_open_brackets = self.current_line.bracket_tracker.any_open_brackets()
1626             for comment in generate_comments(node):
1627                 if any_open_brackets:
1628                     # any comment within brackets is subject to splitting
1629                     self.current_line.append(comment)
1630                 elif comment.type == token.COMMENT:
1631                     # regular trailing comment
1632                     self.current_line.append(comment)
1633                     yield from self.line()
1634
1635                 else:
1636                     # regular standalone comment
1637                     yield from self.line()
1638
1639                     self.current_line.append(comment)
1640                     yield from self.line()
1641
1642             normalize_prefix(node, inside_brackets=any_open_brackets)
1643             if self.normalize_strings and node.type == token.STRING:
1644                 normalize_string_prefix(node, remove_u_prefix=self.remove_u_prefix)
1645                 normalize_string_quotes(node)
1646             if node.type == token.NUMBER:
1647                 normalize_numeric_literal(node)
1648             if node.type not in WHITESPACE:
1649                 self.current_line.append(node)
1650         yield from super().visit_default(node)
1651
1652     def visit_atom(self, node: Node) -> Iterator[Line]:
1653         # Always make parentheses invisible around a single node, because it should
1654         # not be needed (except in the case of yield, where removing the parentheses
1655         # produces a SyntaxError).
1656         if (
1657             len(node.children) == 3
1658             and isinstance(node.children[0], Leaf)
1659             and node.children[0].type == token.LPAR
1660             and isinstance(node.children[2], Leaf)
1661             and node.children[2].type == token.RPAR
1662             and isinstance(node.children[1], Leaf)
1663             and not (
1664                 node.children[1].type == token.NAME
1665                 and node.children[1].value == "yield"
1666             )
1667         ):
1668             node.children[0].value = ""
1669             node.children[2].value = ""
1670         yield from super().visit_default(node)
1671
1672     def visit_factor(self, node: Node) -> Iterator[Line]:
1673         """Force parentheses between a unary op and a binary power:
1674
1675         -2 ** 8 -> -(2 ** 8)
1676         """
1677         child = node.children[1]
1678         if child.type == syms.power and len(child.children) == 3:
1679             lpar = Leaf(token.LPAR, "(")
1680             rpar = Leaf(token.RPAR, ")")
1681             index = child.remove() or 0
1682             node.insert_child(index, Node(syms.atom, [lpar, child, rpar]))
1683         yield from self.visit_default(node)
1684
1685     def visit_INDENT(self, node: Node) -> Iterator[Line]:
1686         """Increase indentation level, maybe yield a line."""
1687         # In blib2to3 INDENT never holds comments.
1688         yield from self.line(+1)
1689         yield from self.visit_default(node)
1690
1691     def visit_DEDENT(self, node: Node) -> Iterator[Line]:
1692         """Decrease indentation level, maybe yield a line."""
1693         # The current line might still wait for trailing comments.  At DEDENT time
1694         # there won't be any (they would be prefixes on the preceding NEWLINE).
1695         # Emit the line then.
1696         yield from self.line()
1697
1698         # While DEDENT has no value, its prefix may contain standalone comments
1699         # that belong to the current indentation level.  Get 'em.
1700         yield from self.visit_default(node)
1701
1702         # Finally, emit the dedent.
1703         yield from self.line(-1)
1704
1705     def visit_stmt(
1706         self, node: Node, keywords: Set[str], parens: Set[str]
1707     ) -> Iterator[Line]:
1708         """Visit a statement.
1709
1710         This implementation is shared for `if`, `while`, `for`, `try`, `except`,
1711         `def`, `with`, `class`, `assert` and assignments.
1712
1713         The relevant Python language `keywords` for a given statement will be
1714         NAME leaves within it. This methods puts those on a separate line.
1715
1716         `parens` holds a set of string leaf values immediately after which
1717         invisible parens should be put.
1718         """
1719         normalize_invisible_parens(node, parens_after=parens)
1720         for child in node.children:
1721             if child.type == token.NAME and child.value in keywords:  # type: ignore
1722                 yield from self.line()
1723
1724             yield from self.visit(child)
1725
1726     def visit_suite(self, node: Node) -> Iterator[Line]:
1727         """Visit a suite."""
1728         if self.is_pyi and is_stub_suite(node):
1729             yield from self.visit(node.children[2])
1730         else:
1731             yield from self.visit_default(node)
1732
1733     def visit_simple_stmt(self, node: Node) -> Iterator[Line]:
1734         """Visit a statement without nested statements."""
1735         is_suite_like = node.parent and node.parent.type in STATEMENT
1736         if is_suite_like:
1737             if self.is_pyi and is_stub_body(node):
1738                 yield from self.visit_default(node)
1739             else:
1740                 yield from self.line(+1)
1741                 yield from self.visit_default(node)
1742                 yield from self.line(-1)
1743
1744         else:
1745             if not self.is_pyi or not node.parent or not is_stub_suite(node.parent):
1746                 yield from self.line()
1747             yield from self.visit_default(node)
1748
1749     def visit_async_stmt(self, node: Node) -> Iterator[Line]:
1750         """Visit `async def`, `async for`, `async with`."""
1751         yield from self.line()
1752
1753         children = iter(node.children)
1754         for child in children:
1755             yield from self.visit(child)
1756
1757             if child.type == token.ASYNC:
1758                 break
1759
1760         internal_stmt = next(children)
1761         for child in internal_stmt.children:
1762             yield from self.visit(child)
1763
1764     def visit_decorators(self, node: Node) -> Iterator[Line]:
1765         """Visit decorators."""
1766         for child in node.children:
1767             yield from self.line()
1768             yield from self.visit(child)
1769
1770     def visit_SEMI(self, leaf: Leaf) -> Iterator[Line]:
1771         """Remove a semicolon and put the other statement on a separate line."""
1772         yield from self.line()
1773
1774     def visit_ENDMARKER(self, leaf: Leaf) -> Iterator[Line]:
1775         """End of file. Process outstanding comments and end with a newline."""
1776         yield from self.visit_default(leaf)
1777         yield from self.line()
1778
1779     def visit_STANDALONE_COMMENT(self, leaf: Leaf) -> Iterator[Line]:
1780         if not self.current_line.bracket_tracker.any_open_brackets():
1781             yield from self.line()
1782         yield from self.visit_default(leaf)
1783
1784     def __attrs_post_init__(self) -> None:
1785         """You are in a twisty little maze of passages."""
1786         v = self.visit_stmt
1787         Ø: Set[str] = set()
1788         self.visit_assert_stmt = partial(v, keywords={"assert"}, parens={"assert", ","})
1789         self.visit_if_stmt = partial(
1790             v, keywords={"if", "else", "elif"}, parens={"if", "elif"}
1791         )
1792         self.visit_while_stmt = partial(v, keywords={"while", "else"}, parens={"while"})
1793         self.visit_for_stmt = partial(v, keywords={"for", "else"}, parens={"for", "in"})
1794         self.visit_try_stmt = partial(
1795             v, keywords={"try", "except", "else", "finally"}, parens=Ø
1796         )
1797         self.visit_except_clause = partial(v, keywords={"except"}, parens=Ø)
1798         self.visit_with_stmt = partial(v, keywords={"with"}, parens=Ø)
1799         self.visit_funcdef = partial(v, keywords={"def"}, parens=Ø)
1800         self.visit_classdef = partial(v, keywords={"class"}, parens=Ø)
1801         self.visit_expr_stmt = partial(v, keywords=Ø, parens=ASSIGNMENTS)
1802         self.visit_return_stmt = partial(v, keywords={"return"}, parens={"return"})
1803         self.visit_import_from = partial(v, keywords=Ø, parens={"import"})
1804         self.visit_del_stmt = partial(v, keywords=Ø, parens={"del"})
1805         self.visit_async_funcdef = self.visit_async_stmt
1806         self.visit_decorated = self.visit_decorators
1807
1808
1809 IMPLICIT_TUPLE = {syms.testlist, syms.testlist_star_expr, syms.exprlist}
1810 BRACKET = {token.LPAR: token.RPAR, token.LSQB: token.RSQB, token.LBRACE: token.RBRACE}
1811 OPENING_BRACKETS = set(BRACKET.keys())
1812 CLOSING_BRACKETS = set(BRACKET.values())
1813 BRACKETS = OPENING_BRACKETS | CLOSING_BRACKETS
1814 ALWAYS_NO_SPACE = CLOSING_BRACKETS | {token.COMMA, STANDALONE_COMMENT}
1815
1816
1817 def whitespace(leaf: Leaf, *, complex_subscript: bool) -> str:  # noqa: C901
1818     """Return whitespace prefix if needed for the given `leaf`.
1819
1820     `complex_subscript` signals whether the given leaf is part of a subscription
1821     which has non-trivial arguments, like arithmetic expressions or function calls.
1822     """
1823     NO = ""
1824     SPACE = " "
1825     DOUBLESPACE = "  "
1826     t = leaf.type
1827     p = leaf.parent
1828     v = leaf.value
1829     if t in ALWAYS_NO_SPACE:
1830         return NO
1831
1832     if t == token.COMMENT:
1833         return DOUBLESPACE
1834
1835     assert p is not None, f"INTERNAL ERROR: hand-made leaf without parent: {leaf!r}"
1836     if t == token.COLON and p.type not in {
1837         syms.subscript,
1838         syms.subscriptlist,
1839         syms.sliceop,
1840     }:
1841         return NO
1842
1843     prev = leaf.prev_sibling
1844     if not prev:
1845         prevp = preceding_leaf(p)
1846         if not prevp or prevp.type in OPENING_BRACKETS:
1847             return NO
1848
1849         if t == token.COLON:
1850             if prevp.type == token.COLON:
1851                 return NO
1852
1853             elif prevp.type != token.COMMA and not complex_subscript:
1854                 return NO
1855
1856             return SPACE
1857
1858         if prevp.type == token.EQUAL:
1859             if prevp.parent:
1860                 if prevp.parent.type in {
1861                     syms.arglist,
1862                     syms.argument,
1863                     syms.parameters,
1864                     syms.varargslist,
1865                 }:
1866                     return NO
1867
1868                 elif prevp.parent.type == syms.typedargslist:
1869                     # A bit hacky: if the equal sign has whitespace, it means we
1870                     # previously found it's a typed argument.  So, we're using
1871                     # that, too.
1872                     return prevp.prefix
1873
1874         elif prevp.type in VARARGS_SPECIALS:
1875             if is_vararg(prevp, within=VARARGS_PARENTS | UNPACKING_PARENTS):
1876                 return NO
1877
1878         elif prevp.type == token.COLON:
1879             if prevp.parent and prevp.parent.type in {syms.subscript, syms.sliceop}:
1880                 return SPACE if complex_subscript else NO
1881
1882         elif (
1883             prevp.parent
1884             and prevp.parent.type == syms.factor
1885             and prevp.type in MATH_OPERATORS
1886         ):
1887             return NO
1888
1889         elif (
1890             prevp.type == token.RIGHTSHIFT
1891             and prevp.parent
1892             and prevp.parent.type == syms.shift_expr
1893             and prevp.prev_sibling
1894             and prevp.prev_sibling.type == token.NAME
1895             and prevp.prev_sibling.value == "print"  # type: ignore
1896         ):
1897             # Python 2 print chevron
1898             return NO
1899
1900     elif prev.type in OPENING_BRACKETS:
1901         return NO
1902
1903     if p.type in {syms.parameters, syms.arglist}:
1904         # untyped function signatures or calls
1905         if not prev or prev.type != token.COMMA:
1906             return NO
1907
1908     elif p.type == syms.varargslist:
1909         # lambdas
1910         if prev and prev.type != token.COMMA:
1911             return NO
1912
1913     elif p.type == syms.typedargslist:
1914         # typed function signatures
1915         if not prev:
1916             return NO
1917
1918         if t == token.EQUAL:
1919             if prev.type != syms.tname:
1920                 return NO
1921
1922         elif prev.type == token.EQUAL:
1923             # A bit hacky: if the equal sign has whitespace, it means we
1924             # previously found it's a typed argument.  So, we're using that, too.
1925             return prev.prefix
1926
1927         elif prev.type != token.COMMA:
1928             return NO
1929
1930     elif p.type == syms.tname:
1931         # type names
1932         if not prev:
1933             prevp = preceding_leaf(p)
1934             if not prevp or prevp.type != token.COMMA:
1935                 return NO
1936
1937     elif p.type == syms.trailer:
1938         # attributes and calls
1939         if t == token.LPAR or t == token.RPAR:
1940             return NO
1941
1942         if not prev:
1943             if t == token.DOT:
1944                 prevp = preceding_leaf(p)
1945                 if not prevp or prevp.type != token.NUMBER:
1946                     return NO
1947
1948             elif t == token.LSQB:
1949                 return NO
1950
1951         elif prev.type != token.COMMA:
1952             return NO
1953
1954     elif p.type == syms.argument:
1955         # single argument
1956         if t == token.EQUAL:
1957             return NO
1958
1959         if not prev:
1960             prevp = preceding_leaf(p)
1961             if not prevp or prevp.type == token.LPAR:
1962                 return NO
1963
1964         elif prev.type in {token.EQUAL} | VARARGS_SPECIALS:
1965             return NO
1966
1967     elif p.type == syms.decorator:
1968         # decorators
1969         return NO
1970
1971     elif p.type == syms.dotted_name:
1972         if prev:
1973             return NO
1974
1975         prevp = preceding_leaf(p)
1976         if not prevp or prevp.type == token.AT or prevp.type == token.DOT:
1977             return NO
1978
1979     elif p.type == syms.classdef:
1980         if t == token.LPAR:
1981             return NO
1982
1983         if prev and prev.type == token.LPAR:
1984             return NO
1985
1986     elif p.type in {syms.subscript, syms.sliceop}:
1987         # indexing
1988         if not prev:
1989             assert p.parent is not None, "subscripts are always parented"
1990             if p.parent.type == syms.subscriptlist:
1991                 return SPACE
1992
1993             return NO
1994
1995         elif not complex_subscript:
1996             return NO
1997
1998     elif p.type == syms.atom:
1999         if prev and t == token.DOT:
2000             # dots, but not the first one.
2001             return NO
2002
2003     elif p.type == syms.dictsetmaker:
2004         # dict unpacking
2005         if prev and prev.type == token.DOUBLESTAR:
2006             return NO
2007
2008     elif p.type in {syms.factor, syms.star_expr}:
2009         # unary ops
2010         if not prev:
2011             prevp = preceding_leaf(p)
2012             if not prevp or prevp.type in OPENING_BRACKETS:
2013                 return NO
2014
2015             prevp_parent = prevp.parent
2016             assert prevp_parent is not None
2017             if prevp.type == token.COLON and prevp_parent.type in {
2018                 syms.subscript,
2019                 syms.sliceop,
2020             }:
2021                 return NO
2022
2023             elif prevp.type == token.EQUAL and prevp_parent.type == syms.argument:
2024                 return NO
2025
2026         elif t in {token.NAME, token.NUMBER, token.STRING}:
2027             return NO
2028
2029     elif p.type == syms.import_from:
2030         if t == token.DOT:
2031             if prev and prev.type == token.DOT:
2032                 return NO
2033
2034         elif t == token.NAME:
2035             if v == "import":
2036                 return SPACE
2037
2038             if prev and prev.type == token.DOT:
2039                 return NO
2040
2041     elif p.type == syms.sliceop:
2042         return NO
2043
2044     return SPACE
2045
2046
2047 def preceding_leaf(node: Optional[LN]) -> Optional[Leaf]:
2048     """Return the first leaf that precedes `node`, if any."""
2049     while node:
2050         res = node.prev_sibling
2051         if res:
2052             if isinstance(res, Leaf):
2053                 return res
2054
2055             try:
2056                 return list(res.leaves())[-1]
2057
2058             except IndexError:
2059                 return None
2060
2061         node = node.parent
2062     return None
2063
2064
2065 def child_towards(ancestor: Node, descendant: LN) -> Optional[LN]:
2066     """Return the child of `ancestor` that contains `descendant`."""
2067     node: Optional[LN] = descendant
2068     while node and node.parent != ancestor:
2069         node = node.parent
2070     return node
2071
2072
2073 def container_of(leaf: Leaf) -> LN:
2074     """Return `leaf` or one of its ancestors that is the topmost container of it.
2075
2076     By "container" we mean a node where `leaf` is the very first child.
2077     """
2078     same_prefix = leaf.prefix
2079     container: LN = leaf
2080     while container:
2081         parent = container.parent
2082         if parent is None:
2083             break
2084
2085         if parent.children[0].prefix != same_prefix:
2086             break
2087
2088         if parent.type == syms.file_input:
2089             break
2090
2091         if parent.prev_sibling is not None and parent.prev_sibling.type in BRACKETS:
2092             break
2093
2094         container = parent
2095     return container
2096
2097
2098 def is_split_after_delimiter(leaf: Leaf, previous: Optional[Leaf] = None) -> Priority:
2099     """Return the priority of the `leaf` delimiter, given a line break after it.
2100
2101     The delimiter priorities returned here are from those delimiters that would
2102     cause a line break after themselves.
2103
2104     Higher numbers are higher priority.
2105     """
2106     if leaf.type == token.COMMA:
2107         return COMMA_PRIORITY
2108
2109     return 0
2110
2111
2112 def is_split_before_delimiter(leaf: Leaf, previous: Optional[Leaf] = None) -> Priority:
2113     """Return the priority of the `leaf` delimiter, given a line break before it.
2114
2115     The delimiter priorities returned here are from those delimiters that would
2116     cause a line break before themselves.
2117
2118     Higher numbers are higher priority.
2119     """
2120     if is_vararg(leaf, within=VARARGS_PARENTS | UNPACKING_PARENTS):
2121         # * and ** might also be MATH_OPERATORS but in this case they are not.
2122         # Don't treat them as a delimiter.
2123         return 0
2124
2125     if (
2126         leaf.type == token.DOT
2127         and leaf.parent
2128         and leaf.parent.type not in {syms.import_from, syms.dotted_name}
2129         and (previous is None or previous.type in CLOSING_BRACKETS)
2130     ):
2131         return DOT_PRIORITY
2132
2133     if (
2134         leaf.type in MATH_OPERATORS
2135         and leaf.parent
2136         and leaf.parent.type not in {syms.factor, syms.star_expr}
2137     ):
2138         return MATH_PRIORITIES[leaf.type]
2139
2140     if leaf.type in COMPARATORS:
2141         return COMPARATOR_PRIORITY
2142
2143     if (
2144         leaf.type == token.STRING
2145         and previous is not None
2146         and previous.type == token.STRING
2147     ):
2148         return STRING_PRIORITY
2149
2150     if leaf.type not in {token.NAME, token.ASYNC}:
2151         return 0
2152
2153     if (
2154         leaf.value == "for"
2155         and leaf.parent
2156         and leaf.parent.type in {syms.comp_for, syms.old_comp_for}
2157         or leaf.type == token.ASYNC
2158     ):
2159         if (
2160             not isinstance(leaf.prev_sibling, Leaf)
2161             or leaf.prev_sibling.value != "async"
2162         ):
2163             return COMPREHENSION_PRIORITY
2164
2165     if (
2166         leaf.value == "if"
2167         and leaf.parent
2168         and leaf.parent.type in {syms.comp_if, syms.old_comp_if}
2169     ):
2170         return COMPREHENSION_PRIORITY
2171
2172     if leaf.value in {"if", "else"} and leaf.parent and leaf.parent.type == syms.test:
2173         return TERNARY_PRIORITY
2174
2175     if leaf.value == "is":
2176         return COMPARATOR_PRIORITY
2177
2178     if (
2179         leaf.value == "in"
2180         and leaf.parent
2181         and leaf.parent.type in {syms.comp_op, syms.comparison}
2182         and not (
2183             previous is not None
2184             and previous.type == token.NAME
2185             and previous.value == "not"
2186         )
2187     ):
2188         return COMPARATOR_PRIORITY
2189
2190     if (
2191         leaf.value == "not"
2192         and leaf.parent
2193         and leaf.parent.type == syms.comp_op
2194         and not (
2195             previous is not None
2196             and previous.type == token.NAME
2197             and previous.value == "is"
2198         )
2199     ):
2200         return COMPARATOR_PRIORITY
2201
2202     if leaf.value in LOGIC_OPERATORS and leaf.parent:
2203         return LOGIC_PRIORITY
2204
2205     return 0
2206
2207
2208 FMT_OFF = {"# fmt: off", "# fmt:off", "# yapf: disable"}
2209 FMT_ON = {"# fmt: on", "# fmt:on", "# yapf: enable"}
2210
2211
2212 def generate_comments(leaf: LN) -> Iterator[Leaf]:
2213     """Clean the prefix of the `leaf` and generate comments from it, if any.
2214
2215     Comments in lib2to3 are shoved into the whitespace prefix.  This happens
2216     in `pgen2/driver.py:Driver.parse_tokens()`.  This was a brilliant implementation
2217     move because it does away with modifying the grammar to include all the
2218     possible places in which comments can be placed.
2219
2220     The sad consequence for us though is that comments don't "belong" anywhere.
2221     This is why this function generates simple parentless Leaf objects for
2222     comments.  We simply don't know what the correct parent should be.
2223
2224     No matter though, we can live without this.  We really only need to
2225     differentiate between inline and standalone comments.  The latter don't
2226     share the line with any code.
2227
2228     Inline comments are emitted as regular token.COMMENT leaves.  Standalone
2229     are emitted with a fake STANDALONE_COMMENT token identifier.
2230     """
2231     for pc in list_comments(leaf.prefix, is_endmarker=leaf.type == token.ENDMARKER):
2232         yield Leaf(pc.type, pc.value, prefix="\n" * pc.newlines)
2233
2234
2235 @dataclass
2236 class ProtoComment:
2237     """Describes a piece of syntax that is a comment.
2238
2239     It's not a :class:`blib2to3.pytree.Leaf` so that:
2240
2241     * it can be cached (`Leaf` objects should not be reused more than once as
2242       they store their lineno, column, prefix, and parent information);
2243     * `newlines` and `consumed` fields are kept separate from the `value`. This
2244       simplifies handling of special marker comments like ``# fmt: off/on``.
2245     """
2246
2247     type: int  # token.COMMENT or STANDALONE_COMMENT
2248     value: str  # content of the comment
2249     newlines: int  # how many newlines before the comment
2250     consumed: int  # how many characters of the original leaf's prefix did we consume
2251
2252
2253 @lru_cache(maxsize=4096)
2254 def list_comments(prefix: str, *, is_endmarker: bool) -> List[ProtoComment]:
2255     """Return a list of :class:`ProtoComment` objects parsed from the given `prefix`."""
2256     result: List[ProtoComment] = []
2257     if not prefix or "#" not in prefix:
2258         return result
2259
2260     consumed = 0
2261     nlines = 0
2262     ignored_lines = 0
2263     for index, line in enumerate(prefix.split("\n")):
2264         consumed += len(line) + 1  # adding the length of the split '\n'
2265         line = line.lstrip()
2266         if not line:
2267             nlines += 1
2268         if not line.startswith("#"):
2269             # Escaped newlines outside of a comment are not really newlines at
2270             # all. We treat a single-line comment following an escaped newline
2271             # as a simple trailing comment.
2272             if line.endswith("\\"):
2273                 ignored_lines += 1
2274             continue
2275
2276         if index == ignored_lines and not is_endmarker:
2277             comment_type = token.COMMENT  # simple trailing comment
2278         else:
2279             comment_type = STANDALONE_COMMENT
2280         comment = make_comment(line)
2281         result.append(
2282             ProtoComment(
2283                 type=comment_type, value=comment, newlines=nlines, consumed=consumed
2284             )
2285         )
2286         nlines = 0
2287     return result
2288
2289
2290 def make_comment(content: str) -> str:
2291     """Return a consistently formatted comment from the given `content` string.
2292
2293     All comments (except for "##", "#!", "#:", '#'", "#%%") should have a single
2294     space between the hash sign and the content.
2295
2296     If `content` didn't start with a hash sign, one is provided.
2297     """
2298     content = content.rstrip()
2299     if not content:
2300         return "#"
2301
2302     if content[0] == "#":
2303         content = content[1:]
2304     if content and content[0] not in " !:#'%":
2305         content = " " + content
2306     return "#" + content
2307
2308
2309 def split_line(
2310     line: Line,
2311     line_length: int,
2312     inner: bool = False,
2313     features: Collection[Feature] = (),
2314 ) -> Iterator[Line]:
2315     """Split a `line` into potentially many lines.
2316
2317     They should fit in the allotted `line_length` but might not be able to.
2318     `inner` signifies that there were a pair of brackets somewhere around the
2319     current `line`, possibly transitively. This means we can fallback to splitting
2320     by delimiters if the LHS/RHS don't yield any results.
2321
2322     `features` are syntactical features that may be used in the output.
2323     """
2324     if line.is_comment:
2325         yield line
2326         return
2327
2328     line_str = str(line).strip("\n")
2329
2330     if (
2331         not line.contains_inner_type_comments()
2332         and not line.should_explode
2333         and is_line_short_enough(line, line_length=line_length, line_str=line_str)
2334     ):
2335         yield line
2336         return
2337
2338     split_funcs: List[SplitFunc]
2339     if line.is_def:
2340         split_funcs = [left_hand_split]
2341     else:
2342
2343         def rhs(line: Line, features: Collection[Feature]) -> Iterator[Line]:
2344             for omit in generate_trailers_to_omit(line, line_length):
2345                 lines = list(right_hand_split(line, line_length, features, omit=omit))
2346                 if is_line_short_enough(lines[0], line_length=line_length):
2347                     yield from lines
2348                     return
2349
2350             # All splits failed, best effort split with no omits.
2351             # This mostly happens to multiline strings that are by definition
2352             # reported as not fitting a single line.
2353             yield from right_hand_split(line, line_length, features=features)
2354
2355         if line.inside_brackets:
2356             split_funcs = [delimiter_split, standalone_comment_split, rhs]
2357         else:
2358             split_funcs = [rhs]
2359     for split_func in split_funcs:
2360         # We are accumulating lines in `result` because we might want to abort
2361         # mission and return the original line in the end, or attempt a different
2362         # split altogether.
2363         result: List[Line] = []
2364         try:
2365             for l in split_func(line, features):
2366                 if str(l).strip("\n") == line_str:
2367                     raise CannotSplit("Split function returned an unchanged result")
2368
2369                 result.extend(
2370                     split_line(
2371                         l, line_length=line_length, inner=True, features=features
2372                     )
2373                 )
2374         except CannotSplit:
2375             continue
2376
2377         else:
2378             yield from result
2379             break
2380
2381     else:
2382         yield line
2383
2384
2385 def left_hand_split(line: Line, features: Collection[Feature] = ()) -> Iterator[Line]:
2386     """Split line into many lines, starting with the first matching bracket pair.
2387
2388     Note: this usually looks weird, only use this for function definitions.
2389     Prefer RHS otherwise.  This is why this function is not symmetrical with
2390     :func:`right_hand_split` which also handles optional parentheses.
2391     """
2392     tail_leaves: List[Leaf] = []
2393     body_leaves: List[Leaf] = []
2394     head_leaves: List[Leaf] = []
2395     current_leaves = head_leaves
2396     matching_bracket = None
2397     for leaf in line.leaves:
2398         if (
2399             current_leaves is body_leaves
2400             and leaf.type in CLOSING_BRACKETS
2401             and leaf.opening_bracket is matching_bracket
2402         ):
2403             current_leaves = tail_leaves if body_leaves else head_leaves
2404         current_leaves.append(leaf)
2405         if current_leaves is head_leaves:
2406             if leaf.type in OPENING_BRACKETS:
2407                 matching_bracket = leaf
2408                 current_leaves = body_leaves
2409     if not matching_bracket:
2410         raise CannotSplit("No brackets found")
2411
2412     head = bracket_split_build_line(head_leaves, line, matching_bracket)
2413     body = bracket_split_build_line(body_leaves, line, matching_bracket, is_body=True)
2414     tail = bracket_split_build_line(tail_leaves, line, matching_bracket)
2415     bracket_split_succeeded_or_raise(head, body, tail)
2416     for result in (head, body, tail):
2417         if result:
2418             yield result
2419
2420
2421 def right_hand_split(
2422     line: Line,
2423     line_length: int,
2424     features: Collection[Feature] = (),
2425     omit: Collection[LeafID] = (),
2426 ) -> Iterator[Line]:
2427     """Split line into many lines, starting with the last matching bracket pair.
2428
2429     If the split was by optional parentheses, attempt splitting without them, too.
2430     `omit` is a collection of closing bracket IDs that shouldn't be considered for
2431     this split.
2432
2433     Note: running this function modifies `bracket_depth` on the leaves of `line`.
2434     """
2435     tail_leaves: List[Leaf] = []
2436     body_leaves: List[Leaf] = []
2437     head_leaves: List[Leaf] = []
2438     current_leaves = tail_leaves
2439     opening_bracket = None
2440     closing_bracket = None
2441     for leaf in reversed(line.leaves):
2442         if current_leaves is body_leaves:
2443             if leaf is opening_bracket:
2444                 current_leaves = head_leaves if body_leaves else tail_leaves
2445         current_leaves.append(leaf)
2446         if current_leaves is tail_leaves:
2447             if leaf.type in CLOSING_BRACKETS and id(leaf) not in omit:
2448                 opening_bracket = leaf.opening_bracket
2449                 closing_bracket = leaf
2450                 current_leaves = body_leaves
2451     if not (opening_bracket and closing_bracket and head_leaves):
2452         # If there is no opening or closing_bracket that means the split failed and
2453         # all content is in the tail.  Otherwise, if `head_leaves` are empty, it means
2454         # the matching `opening_bracket` wasn't available on `line` anymore.
2455         raise CannotSplit("No brackets found")
2456
2457     tail_leaves.reverse()
2458     body_leaves.reverse()
2459     head_leaves.reverse()
2460     head = bracket_split_build_line(head_leaves, line, opening_bracket)
2461     body = bracket_split_build_line(body_leaves, line, opening_bracket, is_body=True)
2462     tail = bracket_split_build_line(tail_leaves, line, opening_bracket)
2463     bracket_split_succeeded_or_raise(head, body, tail)
2464     if (
2465         # the body shouldn't be exploded
2466         not body.should_explode
2467         # the opening bracket is an optional paren
2468         and opening_bracket.type == token.LPAR
2469         and not opening_bracket.value
2470         # the closing bracket is an optional paren
2471         and closing_bracket.type == token.RPAR
2472         and not closing_bracket.value
2473         # it's not an import (optional parens are the only thing we can split on
2474         # in this case; attempting a split without them is a waste of time)
2475         and not line.is_import
2476         # there are no standalone comments in the body
2477         and not body.contains_standalone_comments(0)
2478         # and we can actually remove the parens
2479         and can_omit_invisible_parens(body, line_length)
2480     ):
2481         omit = {id(closing_bracket), *omit}
2482         try:
2483             yield from right_hand_split(line, line_length, features=features, omit=omit)
2484             return
2485
2486         except CannotSplit:
2487             if not (
2488                 can_be_split(body)
2489                 or is_line_short_enough(body, line_length=line_length)
2490             ):
2491                 raise CannotSplit(
2492                     "Splitting failed, body is still too long and can't be split."
2493                 )
2494
2495             elif head.contains_multiline_strings() or tail.contains_multiline_strings():
2496                 raise CannotSplit(
2497                     "The current optional pair of parentheses is bound to fail to "
2498                     "satisfy the splitting algorithm because the head or the tail "
2499                     "contains multiline strings which by definition never fit one "
2500                     "line."
2501                 )
2502
2503     ensure_visible(opening_bracket)
2504     ensure_visible(closing_bracket)
2505     for result in (head, body, tail):
2506         if result:
2507             yield result
2508
2509
2510 def bracket_split_succeeded_or_raise(head: Line, body: Line, tail: Line) -> None:
2511     """Raise :exc:`CannotSplit` if the last left- or right-hand split failed.
2512
2513     Do nothing otherwise.
2514
2515     A left- or right-hand split is based on a pair of brackets. Content before
2516     (and including) the opening bracket is left on one line, content inside the
2517     brackets is put on a separate line, and finally content starting with and
2518     following the closing bracket is put on a separate line.
2519
2520     Those are called `head`, `body`, and `tail`, respectively. If the split
2521     produced the same line (all content in `head`) or ended up with an empty `body`
2522     and the `tail` is just the closing bracket, then it's considered failed.
2523     """
2524     tail_len = len(str(tail).strip())
2525     if not body:
2526         if tail_len == 0:
2527             raise CannotSplit("Splitting brackets produced the same line")
2528
2529         elif tail_len < 3:
2530             raise CannotSplit(
2531                 f"Splitting brackets on an empty body to save "
2532                 f"{tail_len} characters is not worth it"
2533             )
2534
2535
2536 def bracket_split_build_line(
2537     leaves: List[Leaf], original: Line, opening_bracket: Leaf, *, is_body: bool = False
2538 ) -> Line:
2539     """Return a new line with given `leaves` and respective comments from `original`.
2540
2541     If `is_body` is True, the result line is one-indented inside brackets and as such
2542     has its first leaf's prefix normalized and a trailing comma added when expected.
2543     """
2544     result = Line(depth=original.depth)
2545     if is_body:
2546         result.inside_brackets = True
2547         result.depth += 1
2548         if leaves:
2549             # Since body is a new indent level, remove spurious leading whitespace.
2550             normalize_prefix(leaves[0], inside_brackets=True)
2551             # Ensure a trailing comma for imports and standalone function arguments, but
2552             # be careful not to add one after any comments.
2553             no_commas = original.is_def and not any(
2554                 l.type == token.COMMA for l in leaves
2555             )
2556
2557             if original.is_import or no_commas:
2558                 for i in range(len(leaves) - 1, -1, -1):
2559                     if leaves[i].type == STANDALONE_COMMENT:
2560                         continue
2561                     elif leaves[i].type == token.COMMA:
2562                         break
2563                     else:
2564                         leaves.insert(i + 1, Leaf(token.COMMA, ","))
2565                         break
2566     # Populate the line
2567     for leaf in leaves:
2568         result.append(leaf, preformatted=True)
2569         for comment_after in original.comments_after(leaf):
2570             result.append(comment_after, preformatted=True)
2571     if is_body:
2572         result.should_explode = should_explode(result, opening_bracket)
2573     return result
2574
2575
2576 def dont_increase_indentation(split_func: SplitFunc) -> SplitFunc:
2577     """Normalize prefix of the first leaf in every line returned by `split_func`.
2578
2579     This is a decorator over relevant split functions.
2580     """
2581
2582     @wraps(split_func)
2583     def split_wrapper(line: Line, features: Collection[Feature] = ()) -> Iterator[Line]:
2584         for l in split_func(line, features):
2585             normalize_prefix(l.leaves[0], inside_brackets=True)
2586             yield l
2587
2588     return split_wrapper
2589
2590
2591 @dont_increase_indentation
2592 def delimiter_split(line: Line, features: Collection[Feature] = ()) -> Iterator[Line]:
2593     """Split according to delimiters of the highest priority.
2594
2595     If the appropriate Features are given, the split will add trailing commas
2596     also in function signatures and calls that contain `*` and `**`.
2597     """
2598     try:
2599         last_leaf = line.leaves[-1]
2600     except IndexError:
2601         raise CannotSplit("Line empty")
2602
2603     bt = line.bracket_tracker
2604     try:
2605         delimiter_priority = bt.max_delimiter_priority(exclude={id(last_leaf)})
2606     except ValueError:
2607         raise CannotSplit("No delimiters found")
2608
2609     if delimiter_priority == DOT_PRIORITY:
2610         if bt.delimiter_count_with_priority(delimiter_priority) == 1:
2611             raise CannotSplit("Splitting a single attribute from its owner looks wrong")
2612
2613     current_line = Line(depth=line.depth, inside_brackets=line.inside_brackets)
2614     lowest_depth = sys.maxsize
2615     trailing_comma_safe = True
2616
2617     def append_to_line(leaf: Leaf) -> Iterator[Line]:
2618         """Append `leaf` to current line or to new line if appending impossible."""
2619         nonlocal current_line
2620         try:
2621             current_line.append_safe(leaf, preformatted=True)
2622         except ValueError:
2623             yield current_line
2624
2625             current_line = Line(depth=line.depth, inside_brackets=line.inside_brackets)
2626             current_line.append(leaf)
2627
2628     for leaf in line.leaves:
2629         yield from append_to_line(leaf)
2630
2631         for comment_after in line.comments_after(leaf):
2632             yield from append_to_line(comment_after)
2633
2634         lowest_depth = min(lowest_depth, leaf.bracket_depth)
2635         if leaf.bracket_depth == lowest_depth:
2636             if is_vararg(leaf, within={syms.typedargslist}):
2637                 trailing_comma_safe = (
2638                     trailing_comma_safe and Feature.TRAILING_COMMA_IN_DEF in features
2639                 )
2640             elif is_vararg(leaf, within={syms.arglist, syms.argument}):
2641                 trailing_comma_safe = (
2642                     trailing_comma_safe and Feature.TRAILING_COMMA_IN_CALL in features
2643                 )
2644
2645         leaf_priority = bt.delimiters.get(id(leaf))
2646         if leaf_priority == delimiter_priority:
2647             yield current_line
2648
2649             current_line = Line(depth=line.depth, inside_brackets=line.inside_brackets)
2650     if current_line:
2651         if (
2652             trailing_comma_safe
2653             and delimiter_priority == COMMA_PRIORITY
2654             and current_line.leaves[-1].type != token.COMMA
2655             and current_line.leaves[-1].type != STANDALONE_COMMENT
2656         ):
2657             current_line.append(Leaf(token.COMMA, ","))
2658         yield current_line
2659
2660
2661 @dont_increase_indentation
2662 def standalone_comment_split(
2663     line: Line, features: Collection[Feature] = ()
2664 ) -> Iterator[Line]:
2665     """Split standalone comments from the rest of the line."""
2666     if not line.contains_standalone_comments(0):
2667         raise CannotSplit("Line does not have any standalone comments")
2668
2669     current_line = Line(depth=line.depth, inside_brackets=line.inside_brackets)
2670
2671     def append_to_line(leaf: Leaf) -> Iterator[Line]:
2672         """Append `leaf` to current line or to new line if appending impossible."""
2673         nonlocal current_line
2674         try:
2675             current_line.append_safe(leaf, preformatted=True)
2676         except ValueError:
2677             yield current_line
2678
2679             current_line = Line(depth=line.depth, inside_brackets=line.inside_brackets)
2680             current_line.append(leaf)
2681
2682     for leaf in line.leaves:
2683         yield from append_to_line(leaf)
2684
2685         for comment_after in line.comments_after(leaf):
2686             yield from append_to_line(comment_after)
2687
2688     if current_line:
2689         yield current_line
2690
2691
2692 def is_import(leaf: Leaf) -> bool:
2693     """Return True if the given leaf starts an import statement."""
2694     p = leaf.parent
2695     t = leaf.type
2696     v = leaf.value
2697     return bool(
2698         t == token.NAME
2699         and (
2700             (v == "import" and p and p.type == syms.import_name)
2701             or (v == "from" and p and p.type == syms.import_from)
2702         )
2703     )
2704
2705
2706 def is_type_comment(leaf: Leaf) -> bool:
2707     """Return True if the given leaf is a special comment.
2708     Only returns true for type comments for now."""
2709     t = leaf.type
2710     v = leaf.value
2711     return t in {token.COMMENT, t == STANDALONE_COMMENT} and v.startswith("# type:")
2712
2713
2714 def normalize_prefix(leaf: Leaf, *, inside_brackets: bool) -> None:
2715     """Leave existing extra newlines if not `inside_brackets`. Remove everything
2716     else.
2717
2718     Note: don't use backslashes for formatting or you'll lose your voting rights.
2719     """
2720     if not inside_brackets:
2721         spl = leaf.prefix.split("#")
2722         if "\\" not in spl[0]:
2723             nl_count = spl[-1].count("\n")
2724             if len(spl) > 1:
2725                 nl_count -= 1
2726             leaf.prefix = "\n" * nl_count
2727             return
2728
2729     leaf.prefix = ""
2730
2731
2732 def normalize_string_prefix(leaf: Leaf, remove_u_prefix: bool = False) -> None:
2733     """Make all string prefixes lowercase.
2734
2735     If remove_u_prefix is given, also removes any u prefix from the string.
2736
2737     Note: Mutates its argument.
2738     """
2739     match = re.match(r"^([furbFURB]*)(.*)$", leaf.value, re.DOTALL)
2740     assert match is not None, f"failed to match string {leaf.value!r}"
2741     orig_prefix = match.group(1)
2742     new_prefix = orig_prefix.lower()
2743     if remove_u_prefix:
2744         new_prefix = new_prefix.replace("u", "")
2745     leaf.value = f"{new_prefix}{match.group(2)}"
2746
2747
2748 def normalize_string_quotes(leaf: Leaf) -> None:
2749     """Prefer double quotes but only if it doesn't cause more escaping.
2750
2751     Adds or removes backslashes as appropriate. Doesn't parse and fix
2752     strings nested in f-strings (yet).
2753
2754     Note: Mutates its argument.
2755     """
2756     value = leaf.value.lstrip("furbFURB")
2757     if value[:3] == '"""':
2758         return
2759
2760     elif value[:3] == "'''":
2761         orig_quote = "'''"
2762         new_quote = '"""'
2763     elif value[0] == '"':
2764         orig_quote = '"'
2765         new_quote = "'"
2766     else:
2767         orig_quote = "'"
2768         new_quote = '"'
2769     first_quote_pos = leaf.value.find(orig_quote)
2770     if first_quote_pos == -1:
2771         return  # There's an internal error
2772
2773     prefix = leaf.value[:first_quote_pos]
2774     unescaped_new_quote = re.compile(rf"(([^\\]|^)(\\\\)*){new_quote}")
2775     escaped_new_quote = re.compile(rf"([^\\]|^)\\((?:\\\\)*){new_quote}")
2776     escaped_orig_quote = re.compile(rf"([^\\]|^)\\((?:\\\\)*){orig_quote}")
2777     body = leaf.value[first_quote_pos + len(orig_quote) : -len(orig_quote)]
2778     if "r" in prefix.casefold():
2779         if unescaped_new_quote.search(body):
2780             # There's at least one unescaped new_quote in this raw string
2781             # so converting is impossible
2782             return
2783
2784         # Do not introduce or remove backslashes in raw strings
2785         new_body = body
2786     else:
2787         # remove unnecessary escapes
2788         new_body = sub_twice(escaped_new_quote, rf"\1\2{new_quote}", body)
2789         if body != new_body:
2790             # Consider the string without unnecessary escapes as the original
2791             body = new_body
2792             leaf.value = f"{prefix}{orig_quote}{body}{orig_quote}"
2793         new_body = sub_twice(escaped_orig_quote, rf"\1\2{orig_quote}", new_body)
2794         new_body = sub_twice(unescaped_new_quote, rf"\1\\{new_quote}", new_body)
2795     if "f" in prefix.casefold():
2796         matches = re.findall(
2797             r"""
2798             (?:[^{]|^)\{  # start of the string or a non-{ followed by a single {
2799                 ([^{].*?)  # contents of the brackets except if begins with {{
2800             \}(?:[^}]|$)  # A } followed by end of the string or a non-}
2801             """,
2802             new_body,
2803             re.VERBOSE,
2804         )
2805         for m in matches:
2806             if "\\" in str(m):
2807                 # Do not introduce backslashes in interpolated expressions
2808                 return
2809     if new_quote == '"""' and new_body[-1:] == '"':
2810         # edge case:
2811         new_body = new_body[:-1] + '\\"'
2812     orig_escape_count = body.count("\\")
2813     new_escape_count = new_body.count("\\")
2814     if new_escape_count > orig_escape_count:
2815         return  # Do not introduce more escaping
2816
2817     if new_escape_count == orig_escape_count and orig_quote == '"':
2818         return  # Prefer double quotes
2819
2820     leaf.value = f"{prefix}{new_quote}{new_body}{new_quote}"
2821
2822
2823 def normalize_numeric_literal(leaf: Leaf) -> None:
2824     """Normalizes numeric (float, int, and complex) literals.
2825
2826     All letters used in the representation are normalized to lowercase (except
2827     in Python 2 long literals).
2828     """
2829     text = leaf.value.lower()
2830     if text.startswith(("0o", "0b")):
2831         # Leave octal and binary literals alone.
2832         pass
2833     elif text.startswith("0x"):
2834         # Change hex literals to upper case.
2835         before, after = text[:2], text[2:]
2836         text = f"{before}{after.upper()}"
2837     elif "e" in text:
2838         before, after = text.split("e")
2839         sign = ""
2840         if after.startswith("-"):
2841             after = after[1:]
2842             sign = "-"
2843         elif after.startswith("+"):
2844             after = after[1:]
2845         before = format_float_or_int_string(before)
2846         text = f"{before}e{sign}{after}"
2847     elif text.endswith(("j", "l")):
2848         number = text[:-1]
2849         suffix = text[-1]
2850         # Capitalize in "2L" because "l" looks too similar to "1".
2851         if suffix == "l":
2852             suffix = "L"
2853         text = f"{format_float_or_int_string(number)}{suffix}"
2854     else:
2855         text = format_float_or_int_string(text)
2856     leaf.value = text
2857
2858
2859 def format_float_or_int_string(text: str) -> str:
2860     """Formats a float string like "1.0"."""
2861     if "." not in text:
2862         return text
2863
2864     before, after = text.split(".")
2865     return f"{before or 0}.{after or 0}"
2866
2867
2868 def normalize_invisible_parens(node: Node, parens_after: Set[str]) -> None:
2869     """Make existing optional parentheses invisible or create new ones.
2870
2871     `parens_after` is a set of string leaf values immediately after which parens
2872     should be put.
2873
2874     Standardizes on visible parentheses for single-element tuples, and keeps
2875     existing visible parentheses for other tuples and generator expressions.
2876     """
2877     for pc in list_comments(node.prefix, is_endmarker=False):
2878         if pc.value in FMT_OFF:
2879             # This `node` has a prefix with `# fmt: off`, don't mess with parens.
2880             return
2881
2882     check_lpar = False
2883     for index, child in enumerate(list(node.children)):
2884         # Add parentheses around long tuple unpacking in assignments.
2885         if (
2886             index == 0
2887             and isinstance(child, Node)
2888             and child.type == syms.testlist_star_expr
2889         ):
2890             check_lpar = True
2891
2892         if check_lpar:
2893             if is_walrus_assignment(child):
2894                 continue
2895             if child.type == syms.atom:
2896                 # Determines if the underlying atom should be surrounded with
2897                 # invisible params - also makes parens invisible recursively
2898                 # within the atom and removes repeated invisible parens within
2899                 # the atom
2900                 should_surround_with_parens = maybe_make_parens_invisible_in_atom(
2901                     child, parent=node
2902                 )
2903
2904                 if should_surround_with_parens:
2905                     lpar = Leaf(token.LPAR, "")
2906                     rpar = Leaf(token.RPAR, "")
2907                     index = child.remove() or 0
2908                     node.insert_child(index, Node(syms.atom, [lpar, child, rpar]))
2909             elif is_one_tuple(child):
2910                 # wrap child in visible parentheses
2911                 lpar = Leaf(token.LPAR, "(")
2912                 rpar = Leaf(token.RPAR, ")")
2913                 child.remove()
2914                 node.insert_child(index, Node(syms.atom, [lpar, child, rpar]))
2915             elif node.type == syms.import_from:
2916                 # "import from" nodes store parentheses directly as part of
2917                 # the statement
2918                 if child.type == token.LPAR:
2919                     # make parentheses invisible
2920                     child.value = ""  # type: ignore
2921                     node.children[-1].value = ""  # type: ignore
2922                 elif child.type != token.STAR:
2923                     # insert invisible parentheses
2924                     node.insert_child(index, Leaf(token.LPAR, ""))
2925                     node.append_child(Leaf(token.RPAR, ""))
2926                 break
2927
2928             elif not (isinstance(child, Leaf) and is_multiline_string(child)):
2929                 # wrap child in invisible parentheses
2930                 lpar = Leaf(token.LPAR, "")
2931                 rpar = Leaf(token.RPAR, "")
2932                 index = child.remove() or 0
2933                 prefix = child.prefix
2934                 child.prefix = ""
2935                 new_child = Node(syms.atom, [lpar, child, rpar])
2936                 new_child.prefix = prefix
2937                 node.insert_child(index, new_child)
2938
2939         check_lpar = isinstance(child, Leaf) and child.value in parens_after
2940
2941
2942 def normalize_fmt_off(node: Node) -> None:
2943     """Convert content between `# fmt: off`/`# fmt: on` into standalone comments."""
2944     try_again = True
2945     while try_again:
2946         try_again = convert_one_fmt_off_pair(node)
2947
2948
2949 def convert_one_fmt_off_pair(node: Node) -> bool:
2950     """Convert content of a single `# fmt: off`/`# fmt: on` into a standalone comment.
2951
2952     Returns True if a pair was converted.
2953     """
2954     for leaf in node.leaves():
2955         previous_consumed = 0
2956         for comment in list_comments(leaf.prefix, is_endmarker=False):
2957             if comment.value in FMT_OFF:
2958                 # We only want standalone comments. If there's no previous leaf or
2959                 # the previous leaf is indentation, it's a standalone comment in
2960                 # disguise.
2961                 if comment.type != STANDALONE_COMMENT:
2962                     prev = preceding_leaf(leaf)
2963                     if prev and prev.type not in WHITESPACE:
2964                         continue
2965
2966                 ignored_nodes = list(generate_ignored_nodes(leaf))
2967                 if not ignored_nodes:
2968                     continue
2969
2970                 first = ignored_nodes[0]  # Can be a container node with the `leaf`.
2971                 parent = first.parent
2972                 prefix = first.prefix
2973                 first.prefix = prefix[comment.consumed :]
2974                 hidden_value = (
2975                     comment.value + "\n" + "".join(str(n) for n in ignored_nodes)
2976                 )
2977                 if hidden_value.endswith("\n"):
2978                     # That happens when one of the `ignored_nodes` ended with a NEWLINE
2979                     # leaf (possibly followed by a DEDENT).
2980                     hidden_value = hidden_value[:-1]
2981                 first_idx = None
2982                 for ignored in ignored_nodes:
2983                     index = ignored.remove()
2984                     if first_idx is None:
2985                         first_idx = index
2986                 assert parent is not None, "INTERNAL ERROR: fmt: on/off handling (1)"
2987                 assert first_idx is not None, "INTERNAL ERROR: fmt: on/off handling (2)"
2988                 parent.insert_child(
2989                     first_idx,
2990                     Leaf(
2991                         STANDALONE_COMMENT,
2992                         hidden_value,
2993                         prefix=prefix[:previous_consumed] + "\n" * comment.newlines,
2994                     ),
2995                 )
2996                 return True
2997
2998             previous_consumed = comment.consumed
2999
3000     return False
3001
3002
3003 def generate_ignored_nodes(leaf: Leaf) -> Iterator[LN]:
3004     """Starting from the container of `leaf`, generate all leaves until `# fmt: on`.
3005
3006     Stops at the end of the block.
3007     """
3008     container: Optional[LN] = container_of(leaf)
3009     while container is not None and container.type != token.ENDMARKER:
3010         for comment in list_comments(container.prefix, is_endmarker=False):
3011             if comment.value in FMT_ON:
3012                 return
3013
3014         yield container
3015
3016         container = container.next_sibling
3017
3018
3019 def maybe_make_parens_invisible_in_atom(node: LN, parent: LN) -> bool:
3020     """If it's safe, make the parens in the atom `node` invisible, recursively.
3021     Additionally, remove repeated, adjacent invisible parens from the atom `node`
3022     as they are redundant.
3023
3024     Returns whether the node should itself be wrapped in invisible parentheses.
3025
3026     """
3027     if (
3028         node.type != syms.atom
3029         or is_empty_tuple(node)
3030         or is_one_tuple(node)
3031         or (is_yield(node) and parent.type != syms.expr_stmt)
3032         or max_delimiter_priority_in_atom(node) >= COMMA_PRIORITY
3033     ):
3034         return False
3035
3036     first = node.children[0]
3037     last = node.children[-1]
3038     if first.type == token.LPAR and last.type == token.RPAR:
3039         middle = node.children[1]
3040         # make parentheses invisible
3041         first.value = ""  # type: ignore
3042         last.value = ""  # type: ignore
3043         maybe_make_parens_invisible_in_atom(middle, parent=parent)
3044
3045         if is_atom_with_invisible_parens(middle):
3046             # Strip the invisible parens from `middle` by replacing
3047             # it with the child in-between the invisible parens
3048             middle.replace(middle.children[1])
3049
3050         return False
3051
3052     return True
3053
3054
3055 def is_atom_with_invisible_parens(node: LN) -> bool:
3056     """Given a `LN`, determines whether it's an atom `node` with invisible
3057     parens. Useful in dedupe-ing and normalizing parens.
3058     """
3059     if isinstance(node, Leaf) or node.type != syms.atom:
3060         return False
3061
3062     first, last = node.children[0], node.children[-1]
3063     return (
3064         isinstance(first, Leaf)
3065         and first.type == token.LPAR
3066         and first.value == ""
3067         and isinstance(last, Leaf)
3068         and last.type == token.RPAR
3069         and last.value == ""
3070     )
3071
3072
3073 def is_empty_tuple(node: LN) -> bool:
3074     """Return True if `node` holds an empty tuple."""
3075     return (
3076         node.type == syms.atom
3077         and len(node.children) == 2
3078         and node.children[0].type == token.LPAR
3079         and node.children[1].type == token.RPAR
3080     )
3081
3082
3083 def unwrap_singleton_parenthesis(node: LN) -> Optional[LN]:
3084     """Returns `wrapped` if `node` is of the shape ( wrapped ).
3085
3086     Parenthesis can be optional. Returns None otherwise"""
3087     if len(node.children) != 3:
3088         return None
3089     lpar, wrapped, rpar = node.children
3090     if not (lpar.type == token.LPAR and rpar.type == token.RPAR):
3091         return None
3092
3093     return wrapped
3094
3095
3096 def is_one_tuple(node: LN) -> bool:
3097     """Return True if `node` holds a tuple with one element, with or without parens."""
3098     if node.type == syms.atom:
3099         gexp = unwrap_singleton_parenthesis(node)
3100         if gexp is None or gexp.type != syms.testlist_gexp:
3101             return False
3102
3103         return len(gexp.children) == 2 and gexp.children[1].type == token.COMMA
3104
3105     return (
3106         node.type in IMPLICIT_TUPLE
3107         and len(node.children) == 2
3108         and node.children[1].type == token.COMMA
3109     )
3110
3111
3112 def is_walrus_assignment(node: LN) -> bool:
3113     """Return True iff `node` is of the shape ( test := test )"""
3114     inner = unwrap_singleton_parenthesis(node)
3115     return inner is not None and inner.type == syms.namedexpr_test
3116
3117
3118 def is_yield(node: LN) -> bool:
3119     """Return True if `node` holds a `yield` or `yield from` expression."""
3120     if node.type == syms.yield_expr:
3121         return True
3122
3123     if node.type == token.NAME and node.value == "yield":  # type: ignore
3124         return True
3125
3126     if node.type != syms.atom:
3127         return False
3128
3129     if len(node.children) != 3:
3130         return False
3131
3132     lpar, expr, rpar = node.children
3133     if lpar.type == token.LPAR and rpar.type == token.RPAR:
3134         return is_yield(expr)
3135
3136     return False
3137
3138
3139 def is_vararg(leaf: Leaf, within: Set[NodeType]) -> bool:
3140     """Return True if `leaf` is a star or double star in a vararg or kwarg.
3141
3142     If `within` includes VARARGS_PARENTS, this applies to function signatures.
3143     If `within` includes UNPACKING_PARENTS, it applies to right hand-side
3144     extended iterable unpacking (PEP 3132) and additional unpacking
3145     generalizations (PEP 448).
3146     """
3147     if leaf.type not in VARARGS_SPECIALS or not leaf.parent:
3148         return False
3149
3150     p = leaf.parent
3151     if p.type == syms.star_expr:
3152         # Star expressions are also used as assignment targets in extended
3153         # iterable unpacking (PEP 3132).  See what its parent is instead.
3154         if not p.parent:
3155             return False
3156
3157         p = p.parent
3158
3159     return p.type in within
3160
3161
3162 def is_multiline_string(leaf: Leaf) -> bool:
3163     """Return True if `leaf` is a multiline string that actually spans many lines."""
3164     value = leaf.value.lstrip("furbFURB")
3165     return value[:3] in {'"""', "'''"} and "\n" in value
3166
3167
3168 def is_stub_suite(node: Node) -> bool:
3169     """Return True if `node` is a suite with a stub body."""
3170     if (
3171         len(node.children) != 4
3172         or node.children[0].type != token.NEWLINE
3173         or node.children[1].type != token.INDENT
3174         or node.children[3].type != token.DEDENT
3175     ):
3176         return False
3177
3178     return is_stub_body(node.children[2])
3179
3180
3181 def is_stub_body(node: LN) -> bool:
3182     """Return True if `node` is a simple statement containing an ellipsis."""
3183     if not isinstance(node, Node) or node.type != syms.simple_stmt:
3184         return False
3185
3186     if len(node.children) != 2:
3187         return False
3188
3189     child = node.children[0]
3190     return (
3191         child.type == syms.atom
3192         and len(child.children) == 3
3193         and all(leaf == Leaf(token.DOT, ".") for leaf in child.children)
3194     )
3195
3196
3197 def max_delimiter_priority_in_atom(node: LN) -> Priority:
3198     """Return maximum delimiter priority inside `node`.
3199
3200     This is specific to atoms with contents contained in a pair of parentheses.
3201     If `node` isn't an atom or there are no enclosing parentheses, returns 0.
3202     """
3203     if node.type != syms.atom:
3204         return 0
3205
3206     first = node.children[0]
3207     last = node.children[-1]
3208     if not (first.type == token.LPAR and last.type == token.RPAR):
3209         return 0
3210
3211     bt = BracketTracker()
3212     for c in node.children[1:-1]:
3213         if isinstance(c, Leaf):
3214             bt.mark(c)
3215         else:
3216             for leaf in c.leaves():
3217                 bt.mark(leaf)
3218     try:
3219         return bt.max_delimiter_priority()
3220
3221     except ValueError:
3222         return 0
3223
3224
3225 def ensure_visible(leaf: Leaf) -> None:
3226     """Make sure parentheses are visible.
3227
3228     They could be invisible as part of some statements (see
3229     :func:`normalize_invisible_parens` and :func:`visit_import_from`).
3230     """
3231     if leaf.type == token.LPAR:
3232         leaf.value = "("
3233     elif leaf.type == token.RPAR:
3234         leaf.value = ")"
3235
3236
3237 def should_explode(line: Line, opening_bracket: Leaf) -> bool:
3238     """Should `line` immediately be split with `delimiter_split()` after RHS?"""
3239
3240     if not (
3241         opening_bracket.parent
3242         and opening_bracket.parent.type in {syms.atom, syms.import_from}
3243         and opening_bracket.value in "[{("
3244     ):
3245         return False
3246
3247     try:
3248         last_leaf = line.leaves[-1]
3249         exclude = {id(last_leaf)} if last_leaf.type == token.COMMA else set()
3250         max_priority = line.bracket_tracker.max_delimiter_priority(exclude=exclude)
3251     except (IndexError, ValueError):
3252         return False
3253
3254     return max_priority == COMMA_PRIORITY
3255
3256
3257 def get_features_used(node: Node) -> Set[Feature]:
3258     """Return a set of (relatively) new Python features used in this file.
3259
3260     Currently looking for:
3261     - f-strings;
3262     - underscores in numeric literals;
3263     - trailing commas after * or ** in function signatures and calls;
3264     - positional only arguments in function signatures and lambdas;
3265     """
3266     features: Set[Feature] = set()
3267     for n in node.pre_order():
3268         if n.type == token.STRING:
3269             value_head = n.value[:2]  # type: ignore
3270             if value_head in {'f"', 'F"', "f'", "F'", "rf", "fr", "RF", "FR"}:
3271                 features.add(Feature.F_STRINGS)
3272
3273         elif n.type == token.NUMBER:
3274             if "_" in n.value:  # type: ignore
3275                 features.add(Feature.NUMERIC_UNDERSCORES)
3276
3277         elif n.type == token.SLASH:
3278             if n.parent and n.parent.type in {syms.typedargslist, syms.arglist}:
3279                 features.add(Feature.POS_ONLY_ARGUMENTS)
3280
3281         elif n.type == token.COLONEQUAL:
3282             features.add(Feature.ASSIGNMENT_EXPRESSIONS)
3283
3284         elif (
3285             n.type in {syms.typedargslist, syms.arglist}
3286             and n.children
3287             and n.children[-1].type == token.COMMA
3288         ):
3289             if n.type == syms.typedargslist:
3290                 feature = Feature.TRAILING_COMMA_IN_DEF
3291             else:
3292                 feature = Feature.TRAILING_COMMA_IN_CALL
3293
3294             for ch in n.children:
3295                 if ch.type in STARS:
3296                     features.add(feature)
3297
3298                 if ch.type == syms.argument:
3299                     for argch in ch.children:
3300                         if argch.type in STARS:
3301                             features.add(feature)
3302
3303     return features
3304
3305
3306 def detect_target_versions(node: Node) -> Set[TargetVersion]:
3307     """Detect the version to target based on the nodes used."""
3308     features = get_features_used(node)
3309     return {
3310         version for version in TargetVersion if features <= VERSION_TO_FEATURES[version]
3311     }
3312
3313
3314 def generate_trailers_to_omit(line: Line, line_length: int) -> Iterator[Set[LeafID]]:
3315     """Generate sets of closing bracket IDs that should be omitted in a RHS.
3316
3317     Brackets can be omitted if the entire trailer up to and including
3318     a preceding closing bracket fits in one line.
3319
3320     Yielded sets are cumulative (contain results of previous yields, too).  First
3321     set is empty.
3322     """
3323
3324     omit: Set[LeafID] = set()
3325     yield omit
3326
3327     length = 4 * line.depth
3328     opening_bracket = None
3329     closing_bracket = None
3330     inner_brackets: Set[LeafID] = set()
3331     for index, leaf, leaf_length in enumerate_with_length(line, reversed=True):
3332         length += leaf_length
3333         if length > line_length:
3334             break
3335
3336         has_inline_comment = leaf_length > len(leaf.value) + len(leaf.prefix)
3337         if leaf.type == STANDALONE_COMMENT or has_inline_comment:
3338             break
3339
3340         if opening_bracket:
3341             if leaf is opening_bracket:
3342                 opening_bracket = None
3343             elif leaf.type in CLOSING_BRACKETS:
3344                 inner_brackets.add(id(leaf))
3345         elif leaf.type in CLOSING_BRACKETS:
3346             if index > 0 and line.leaves[index - 1].type in OPENING_BRACKETS:
3347                 # Empty brackets would fail a split so treat them as "inner"
3348                 # brackets (e.g. only add them to the `omit` set if another
3349                 # pair of brackets was good enough.
3350                 inner_brackets.add(id(leaf))
3351                 continue
3352
3353             if closing_bracket:
3354                 omit.add(id(closing_bracket))
3355                 omit.update(inner_brackets)
3356                 inner_brackets.clear()
3357                 yield omit
3358
3359             if leaf.value:
3360                 opening_bracket = leaf.opening_bracket
3361                 closing_bracket = leaf
3362
3363
3364 def get_future_imports(node: Node) -> Set[str]:
3365     """Return a set of __future__ imports in the file."""
3366     imports: Set[str] = set()
3367
3368     def get_imports_from_children(children: List[LN]) -> Generator[str, None, None]:
3369         for child in children:
3370             if isinstance(child, Leaf):
3371                 if child.type == token.NAME:
3372                     yield child.value
3373             elif child.type == syms.import_as_name:
3374                 orig_name = child.children[0]
3375                 assert isinstance(orig_name, Leaf), "Invalid syntax parsing imports"
3376                 assert orig_name.type == token.NAME, "Invalid syntax parsing imports"
3377                 yield orig_name.value
3378             elif child.type == syms.import_as_names:
3379                 yield from get_imports_from_children(child.children)
3380             else:
3381                 raise AssertionError("Invalid syntax parsing imports")
3382
3383     for child in node.children:
3384         if child.type != syms.simple_stmt:
3385             break
3386         first_child = child.children[0]
3387         if isinstance(first_child, Leaf):
3388             # Continue looking if we see a docstring; otherwise stop.
3389             if (
3390                 len(child.children) == 2
3391                 and first_child.type == token.STRING
3392                 and child.children[1].type == token.NEWLINE
3393             ):
3394                 continue
3395             else:
3396                 break
3397         elif first_child.type == syms.import_from:
3398             module_name = first_child.children[1]
3399             if not isinstance(module_name, Leaf) or module_name.value != "__future__":
3400                 break
3401             imports |= set(get_imports_from_children(first_child.children[3:]))
3402         else:
3403             break
3404     return imports
3405
3406
3407 def gen_python_files_in_dir(
3408     path: Path,
3409     root: Path,
3410     include: Pattern[str],
3411     exclude: Pattern[str],
3412     report: "Report",
3413 ) -> Iterator[Path]:
3414     """Generate all files under `path` whose paths are not excluded by the
3415     `exclude` regex, but are included by the `include` regex.
3416
3417     Symbolic links pointing outside of the `root` directory are ignored.
3418
3419     `report` is where output about exclusions goes.
3420     """
3421     assert root.is_absolute(), f"INTERNAL ERROR: `root` must be absolute but is {root}"
3422     for child in path.iterdir():
3423         try:
3424             normalized_path = "/" + child.resolve().relative_to(root).as_posix()
3425         except ValueError:
3426             if child.is_symlink():
3427                 report.path_ignored(
3428                     child, f"is a symbolic link that points outside {root}"
3429                 )
3430                 continue
3431
3432             raise
3433
3434         if child.is_dir():
3435             normalized_path += "/"
3436         exclude_match = exclude.search(normalized_path)
3437         if exclude_match and exclude_match.group(0):
3438             report.path_ignored(child, f"matches the --exclude regular expression")
3439             continue
3440
3441         if child.is_dir():
3442             yield from gen_python_files_in_dir(child, root, include, exclude, report)
3443
3444         elif child.is_file():
3445             include_match = include.search(normalized_path)
3446             if include_match:
3447                 yield child
3448
3449
3450 @lru_cache()
3451 def find_project_root(srcs: Iterable[str]) -> Path:
3452     """Return a directory containing .git, .hg, or pyproject.toml.
3453
3454     That directory can be one of the directories passed in `srcs` or their
3455     common parent.
3456
3457     If no directory in the tree contains a marker that would specify it's the
3458     project root, the root of the file system is returned.
3459     """
3460     if not srcs:
3461         return Path("/").resolve()
3462
3463     common_base = min(Path(src).resolve() for src in srcs)
3464     if common_base.is_dir():
3465         # Append a fake file so `parents` below returns `common_base_dir`, too.
3466         common_base /= "fake-file"
3467     for directory in common_base.parents:
3468         if (directory / ".git").is_dir():
3469             return directory
3470
3471         if (directory / ".hg").is_dir():
3472             return directory
3473
3474         if (directory / "pyproject.toml").is_file():
3475             return directory
3476
3477     return directory
3478
3479
3480 @dataclass
3481 class Report:
3482     """Provides a reformatting counter. Can be rendered with `str(report)`."""
3483
3484     check: bool = False
3485     quiet: bool = False
3486     verbose: bool = False
3487     change_count: int = 0
3488     same_count: int = 0
3489     failure_count: int = 0
3490
3491     def done(self, src: Path, changed: Changed) -> None:
3492         """Increment the counter for successful reformatting. Write out a message."""
3493         if changed is Changed.YES:
3494             reformatted = "would reformat" if self.check else "reformatted"
3495             if self.verbose or not self.quiet:
3496                 out(f"{reformatted} {src}")
3497             self.change_count += 1
3498         else:
3499             if self.verbose:
3500                 if changed is Changed.NO:
3501                     msg = f"{src} already well formatted, good job."
3502                 else:
3503                     msg = f"{src} wasn't modified on disk since last run."
3504                 out(msg, bold=False)
3505             self.same_count += 1
3506
3507     def failed(self, src: Path, message: str) -> None:
3508         """Increment the counter for failed reformatting. Write out a message."""
3509         err(f"error: cannot format {src}: {message}")
3510         self.failure_count += 1
3511
3512     def path_ignored(self, path: Path, message: str) -> None:
3513         if self.verbose:
3514             out(f"{path} ignored: {message}", bold=False)
3515
3516     @property
3517     def return_code(self) -> int:
3518         """Return the exit code that the app should use.
3519
3520         This considers the current state of changed files and failures:
3521         - if there were any failures, return 123;
3522         - if any files were changed and --check is being used, return 1;
3523         - otherwise return 0.
3524         """
3525         # According to http://tldp.org/LDP/abs/html/exitcodes.html starting with
3526         # 126 we have special return codes reserved by the shell.
3527         if self.failure_count:
3528             return 123
3529
3530         elif self.change_count and self.check:
3531             return 1
3532
3533         return 0
3534
3535     def __str__(self) -> str:
3536         """Render a color report of the current state.
3537
3538         Use `click.unstyle` to remove colors.
3539         """
3540         if self.check:
3541             reformatted = "would be reformatted"
3542             unchanged = "would be left unchanged"
3543             failed = "would fail to reformat"
3544         else:
3545             reformatted = "reformatted"
3546             unchanged = "left unchanged"
3547             failed = "failed to reformat"
3548         report = []
3549         if self.change_count:
3550             s = "s" if self.change_count > 1 else ""
3551             report.append(
3552                 click.style(f"{self.change_count} file{s} {reformatted}", bold=True)
3553             )
3554         if self.same_count:
3555             s = "s" if self.same_count > 1 else ""
3556             report.append(f"{self.same_count} file{s} {unchanged}")
3557         if self.failure_count:
3558             s = "s" if self.failure_count > 1 else ""
3559             report.append(
3560                 click.style(f"{self.failure_count} file{s} {failed}", fg="red")
3561             )
3562         return ", ".join(report) + "."
3563
3564
3565 def parse_ast(src: str) -> Union[ast.AST, ast3.AST, ast27.AST]:
3566     filename = "<unknown>"
3567     if sys.version_info >= (3, 8):
3568         # TODO: support Python 4+ ;)
3569         for minor_version in range(sys.version_info[1], 4, -1):
3570             try:
3571                 return ast.parse(src, filename, feature_version=(3, minor_version))
3572             except SyntaxError:
3573                 continue
3574     else:
3575         for feature_version in (7, 6):
3576             try:
3577                 return ast3.parse(src, filename, feature_version=feature_version)
3578             except SyntaxError:
3579                 continue
3580
3581     return ast27.parse(src)
3582
3583
3584 def _fixup_ast_constants(
3585     node: Union[ast.AST, ast3.AST, ast27.AST]
3586 ) -> Union[ast.AST, ast3.AST, ast27.AST]:
3587     """Map ast nodes deprecated in 3.8 to Constant."""
3588     # casts are required until this is released:
3589     # https://github.com/python/typeshed/pull/3142
3590     if isinstance(node, (ast.Str, ast3.Str, ast27.Str, ast.Bytes, ast3.Bytes)):
3591         return cast(ast.AST, ast.Constant(value=node.s))
3592     elif isinstance(node, (ast.Num, ast3.Num, ast27.Num)):
3593         return cast(ast.AST, ast.Constant(value=node.n))
3594     elif isinstance(node, (ast.NameConstant, ast3.NameConstant)):
3595         return cast(ast.AST, ast.Constant(value=node.value))
3596     return node
3597
3598
3599 def assert_equivalent(src: str, dst: str) -> None:
3600     """Raise AssertionError if `src` and `dst` aren't equivalent."""
3601
3602     def _v(node: Union[ast.AST, ast3.AST, ast27.AST], depth: int = 0) -> Iterator[str]:
3603         """Simple visitor generating strings to compare ASTs by content."""
3604
3605         node = _fixup_ast_constants(node)
3606
3607         yield f"{'  ' * depth}{node.__class__.__name__}("
3608
3609         for field in sorted(node._fields):
3610             # TypeIgnore has only one field 'lineno' which breaks this comparison
3611             type_ignore_classes = (ast3.TypeIgnore, ast27.TypeIgnore)
3612             if sys.version_info >= (3, 8):
3613                 type_ignore_classes += (ast.TypeIgnore,)
3614             if isinstance(node, type_ignore_classes):
3615                 break
3616
3617             try:
3618                 value = getattr(node, field)
3619             except AttributeError:
3620                 continue
3621
3622             yield f"{'  ' * (depth+1)}{field}="
3623
3624             if isinstance(value, list):
3625                 for item in value:
3626                     # Ignore nested tuples within del statements, because we may insert
3627                     # parentheses and they change the AST.
3628                     if (
3629                         field == "targets"
3630                         and isinstance(node, (ast.Delete, ast3.Delete, ast27.Delete))
3631                         and isinstance(item, (ast.Tuple, ast3.Tuple, ast27.Tuple))
3632                     ):
3633                         for item in item.elts:
3634                             yield from _v(item, depth + 2)
3635                     elif isinstance(item, (ast.AST, ast3.AST, ast27.AST)):
3636                         yield from _v(item, depth + 2)
3637
3638             elif isinstance(value, (ast.AST, ast3.AST, ast27.AST)):
3639                 yield from _v(value, depth + 2)
3640
3641             else:
3642                 yield f"{'  ' * (depth+2)}{value!r},  # {value.__class__.__name__}"
3643
3644         yield f"{'  ' * depth})  # /{node.__class__.__name__}"
3645
3646     try:
3647         src_ast = parse_ast(src)
3648     except Exception as exc:
3649         raise AssertionError(
3650             f"cannot use --safe with this file; failed to parse source file.  "
3651             f"AST error message: {exc}"
3652         )
3653
3654     try:
3655         dst_ast = parse_ast(dst)
3656     except Exception as exc:
3657         log = dump_to_file("".join(traceback.format_tb(exc.__traceback__)), dst)
3658         raise AssertionError(
3659             f"INTERNAL ERROR: Black produced invalid code: {exc}. "
3660             f"Please report a bug on https://github.com/psf/black/issues.  "
3661             f"This invalid output might be helpful: {log}"
3662         ) from None
3663
3664     src_ast_str = "\n".join(_v(src_ast))
3665     dst_ast_str = "\n".join(_v(dst_ast))
3666     if src_ast_str != dst_ast_str:
3667         log = dump_to_file(diff(src_ast_str, dst_ast_str, "src", "dst"))
3668         raise AssertionError(
3669             f"INTERNAL ERROR: Black produced code that is not equivalent to "
3670             f"the source.  "
3671             f"Please report a bug on https://github.com/psf/black/issues.  "
3672             f"This diff might be helpful: {log}"
3673         ) from None
3674
3675
3676 def assert_stable(src: str, dst: str, mode: FileMode) -> None:
3677     """Raise AssertionError if `dst` reformats differently the second time."""
3678     newdst = format_str(dst, mode=mode)
3679     if dst != newdst:
3680         log = dump_to_file(
3681             diff(src, dst, "source", "first pass"),
3682             diff(dst, newdst, "first pass", "second pass"),
3683         )
3684         raise AssertionError(
3685             f"INTERNAL ERROR: Black produced different code on the second pass "
3686             f"of the formatter.  "
3687             f"Please report a bug on https://github.com/psf/black/issues.  "
3688             f"This diff might be helpful: {log}"
3689         ) from None
3690
3691
3692 def dump_to_file(*output: str) -> str:
3693     """Dump `output` to a temporary file. Return path to the file."""
3694     with tempfile.NamedTemporaryFile(
3695         mode="w", prefix="blk_", suffix=".log", delete=False, encoding="utf8"
3696     ) as f:
3697         for lines in output:
3698             f.write(lines)
3699             if lines and lines[-1] != "\n":
3700                 f.write("\n")
3701     return f.name
3702
3703
3704 @contextmanager
3705 def nullcontext() -> Iterator[None]:
3706     """Return context manager that does nothing.
3707     Similar to `nullcontext` from python 3.7"""
3708     yield
3709
3710
3711 def diff(a: str, b: str, a_name: str, b_name: str) -> str:
3712     """Return a unified diff string between strings `a` and `b`."""
3713     import difflib
3714
3715     a_lines = [line + "\n" for line in a.split("\n")]
3716     b_lines = [line + "\n" for line in b.split("\n")]
3717     return "".join(
3718         difflib.unified_diff(a_lines, b_lines, fromfile=a_name, tofile=b_name, n=5)
3719     )
3720
3721
3722 def cancel(tasks: Iterable[asyncio.Task]) -> None:
3723     """asyncio signal handler that cancels all `tasks` and reports to stderr."""
3724     err("Aborted!")
3725     for task in tasks:
3726         task.cancel()
3727
3728
3729 def shutdown(loop: asyncio.AbstractEventLoop) -> None:
3730     """Cancel all pending tasks on `loop`, wait for them, and close the loop."""
3731     try:
3732         if sys.version_info[:2] >= (3, 7):
3733             all_tasks = asyncio.all_tasks
3734         else:
3735             all_tasks = asyncio.Task.all_tasks
3736         # This part is borrowed from asyncio/runners.py in Python 3.7b2.
3737         to_cancel = [task for task in all_tasks(loop) if not task.done()]
3738         if not to_cancel:
3739             return
3740
3741         for task in to_cancel:
3742             task.cancel()
3743         loop.run_until_complete(
3744             asyncio.gather(*to_cancel, loop=loop, return_exceptions=True)
3745         )
3746     finally:
3747         # `concurrent.futures.Future` objects cannot be cancelled once they
3748         # are already running. There might be some when the `shutdown()` happened.
3749         # Silence their logger's spew about the event loop being closed.
3750         cf_logger = logging.getLogger("concurrent.futures")
3751         cf_logger.setLevel(logging.CRITICAL)
3752         loop.close()
3753
3754
3755 def sub_twice(regex: Pattern[str], replacement: str, original: str) -> str:
3756     """Replace `regex` with `replacement` twice on `original`.
3757
3758     This is used by string normalization to perform replaces on
3759     overlapping matches.
3760     """
3761     return regex.sub(replacement, regex.sub(replacement, original))
3762
3763
3764 def re_compile_maybe_verbose(regex: str) -> Pattern[str]:
3765     """Compile a regular expression string in `regex`.
3766
3767     If it contains newlines, use verbose mode.
3768     """
3769     if "\n" in regex:
3770         regex = "(?x)" + regex
3771     return re.compile(regex)
3772
3773
3774 def enumerate_reversed(sequence: Sequence[T]) -> Iterator[Tuple[Index, T]]:
3775     """Like `reversed(enumerate(sequence))` if that were possible."""
3776     index = len(sequence) - 1
3777     for element in reversed(sequence):
3778         yield (index, element)
3779         index -= 1
3780
3781
3782 def enumerate_with_length(
3783     line: Line, reversed: bool = False
3784 ) -> Iterator[Tuple[Index, Leaf, int]]:
3785     """Return an enumeration of leaves with their length.
3786
3787     Stops prematurely on multiline strings and standalone comments.
3788     """
3789     op = cast(
3790         Callable[[Sequence[Leaf]], Iterator[Tuple[Index, Leaf]]],
3791         enumerate_reversed if reversed else enumerate,
3792     )
3793     for index, leaf in op(line.leaves):
3794         length = len(leaf.prefix) + len(leaf.value)
3795         if "\n" in leaf.value:
3796             return  # Multiline strings, we can't continue.
3797
3798         for comment in line.comments_after(leaf):
3799             length += len(comment.value)
3800
3801         yield index, leaf, length
3802
3803
3804 def is_line_short_enough(line: Line, *, line_length: int, line_str: str = "") -> bool:
3805     """Return True if `line` is no longer than `line_length`.
3806
3807     Uses the provided `line_str` rendering, if any, otherwise computes a new one.
3808     """
3809     if not line_str:
3810         line_str = str(line).strip("\n")
3811     return (
3812         len(line_str) <= line_length
3813         and "\n" not in line_str  # multiline strings
3814         and not line.contains_standalone_comments()
3815     )
3816
3817
3818 def can_be_split(line: Line) -> bool:
3819     """Return False if the line cannot be split *for sure*.
3820
3821     This is not an exhaustive search but a cheap heuristic that we can use to
3822     avoid some unfortunate formattings (mostly around wrapping unsplittable code
3823     in unnecessary parentheses).
3824     """
3825     leaves = line.leaves
3826     if len(leaves) < 2:
3827         return False
3828
3829     if leaves[0].type == token.STRING and leaves[1].type == token.DOT:
3830         call_count = 0
3831         dot_count = 0
3832         next = leaves[-1]
3833         for leaf in leaves[-2::-1]:
3834             if leaf.type in OPENING_BRACKETS:
3835                 if next.type not in CLOSING_BRACKETS:
3836                     return False
3837
3838                 call_count += 1
3839             elif leaf.type == token.DOT:
3840                 dot_count += 1
3841             elif leaf.type == token.NAME:
3842                 if not (next.type == token.DOT or next.type in OPENING_BRACKETS):
3843                     return False
3844
3845             elif leaf.type not in CLOSING_BRACKETS:
3846                 return False
3847
3848             if dot_count > 1 and call_count > 1:
3849                 return False
3850
3851     return True
3852
3853
3854 def can_omit_invisible_parens(line: Line, line_length: int) -> bool:
3855     """Does `line` have a shape safe to reformat without optional parens around it?
3856
3857     Returns True for only a subset of potentially nice looking formattings but
3858     the point is to not return false positives that end up producing lines that
3859     are too long.
3860     """
3861     bt = line.bracket_tracker
3862     if not bt.delimiters:
3863         # Without delimiters the optional parentheses are useless.
3864         return True
3865
3866     max_priority = bt.max_delimiter_priority()
3867     if bt.delimiter_count_with_priority(max_priority) > 1:
3868         # With more than one delimiter of a kind the optional parentheses read better.
3869         return False
3870
3871     if max_priority == DOT_PRIORITY:
3872         # A single stranded method call doesn't require optional parentheses.
3873         return True
3874
3875     assert len(line.leaves) >= 2, "Stranded delimiter"
3876
3877     first = line.leaves[0]
3878     second = line.leaves[1]
3879     penultimate = line.leaves[-2]
3880     last = line.leaves[-1]
3881
3882     # With a single delimiter, omit if the expression starts or ends with
3883     # a bracket.
3884     if first.type in OPENING_BRACKETS and second.type not in CLOSING_BRACKETS:
3885         remainder = False
3886         length = 4 * line.depth
3887         for _index, leaf, leaf_length in enumerate_with_length(line):
3888             if leaf.type in CLOSING_BRACKETS and leaf.opening_bracket is first:
3889                 remainder = True
3890             if remainder:
3891                 length += leaf_length
3892                 if length > line_length:
3893                     break
3894
3895                 if leaf.type in OPENING_BRACKETS:
3896                     # There are brackets we can further split on.
3897                     remainder = False
3898
3899         else:
3900             # checked the entire string and line length wasn't exceeded
3901             if len(line.leaves) == _index + 1:
3902                 return True
3903
3904         # Note: we are not returning False here because a line might have *both*
3905         # a leading opening bracket and a trailing closing bracket.  If the
3906         # opening bracket doesn't match our rule, maybe the closing will.
3907
3908     if (
3909         last.type == token.RPAR
3910         or last.type == token.RBRACE
3911         or (
3912             # don't use indexing for omitting optional parentheses;
3913             # it looks weird
3914             last.type == token.RSQB
3915             and last.parent
3916             and last.parent.type != syms.trailer
3917         )
3918     ):
3919         if penultimate.type in OPENING_BRACKETS:
3920             # Empty brackets don't help.
3921             return False
3922
3923         if is_multiline_string(first):
3924             # Additional wrapping of a multiline string in this situation is
3925             # unnecessary.
3926             return True
3927
3928         length = 4 * line.depth
3929         seen_other_brackets = False
3930         for _index, leaf, leaf_length in enumerate_with_length(line):
3931             length += leaf_length
3932             if leaf is last.opening_bracket:
3933                 if seen_other_brackets or length <= line_length:
3934                     return True
3935
3936             elif leaf.type in OPENING_BRACKETS:
3937                 # There are brackets we can further split on.
3938                 seen_other_brackets = True
3939
3940     return False
3941
3942
3943 def get_cache_file(mode: FileMode) -> Path:
3944     return CACHE_DIR / f"cache.{mode.get_cache_key()}.pickle"
3945
3946
3947 def read_cache(mode: FileMode) -> Cache:
3948     """Read the cache if it exists and is well formed.
3949
3950     If it is not well formed, the call to write_cache later should resolve the issue.
3951     """
3952     cache_file = get_cache_file(mode)
3953     if not cache_file.exists():
3954         return {}
3955
3956     with cache_file.open("rb") as fobj:
3957         try:
3958             cache: Cache = pickle.load(fobj)
3959         except pickle.UnpicklingError:
3960             return {}
3961
3962     return cache
3963
3964
3965 def get_cache_info(path: Path) -> CacheInfo:
3966     """Return the information used to check if a file is already formatted or not."""
3967     stat = path.stat()
3968     return stat.st_mtime, stat.st_size
3969
3970
3971 def filter_cached(cache: Cache, sources: Iterable[Path]) -> Tuple[Set[Path], Set[Path]]:
3972     """Split an iterable of paths in `sources` into two sets.
3973
3974     The first contains paths of files that modified on disk or are not in the
3975     cache. The other contains paths to non-modified files.
3976     """
3977     todo, done = set(), set()
3978     for src in sources:
3979         src = src.resolve()
3980         if cache.get(src) != get_cache_info(src):
3981             todo.add(src)
3982         else:
3983             done.add(src)
3984     return todo, done
3985
3986
3987 def write_cache(cache: Cache, sources: Iterable[Path], mode: FileMode) -> None:
3988     """Update the cache file."""
3989     cache_file = get_cache_file(mode)
3990     try:
3991         CACHE_DIR.mkdir(parents=True, exist_ok=True)
3992         new_cache = {**cache, **{src.resolve(): get_cache_info(src) for src in sources}}
3993         with tempfile.NamedTemporaryFile(dir=str(cache_file.parent), delete=False) as f:
3994             pickle.dump(new_cache, f, protocol=pickle.HIGHEST_PROTOCOL)
3995         os.replace(f.name, cache_file)
3996     except OSError:
3997         pass
3998
3999
4000 def patch_click() -> None:
4001     """Make Click not crash.
4002
4003     On certain misconfigured environments, Python 3 selects the ASCII encoding as the
4004     default which restricts paths that it can access during the lifetime of the
4005     application.  Click refuses to work in this scenario by raising a RuntimeError.
4006
4007     In case of Black the likelihood that non-ASCII characters are going to be used in
4008     file paths is minimal since it's Python source code.  Moreover, this crash was
4009     spurious on Python 3.7 thanks to PEP 538 and PEP 540.
4010     """
4011     try:
4012         from click import core
4013         from click import _unicodefun  # type: ignore
4014     except ModuleNotFoundError:
4015         return
4016
4017     for module in (core, _unicodefun):
4018         if hasattr(module, "_verify_python3_env"):
4019             module._verify_python3_env = lambda: None
4020
4021
4022 def patched_main() -> None:
4023     freeze_support()
4024     patch_click()
4025     main()
4026
4027
4028 if __name__ == "__main__":
4029     patched_main()