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

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