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

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