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

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