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

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