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

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