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

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