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

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