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

c6b018ffd050431a4592ab5b15820cb610c986f3
[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 maybe_remove_trailing_comma(self, closing: Leaf) -> bool:
1098         """Remove trailing comma if there is one and it's safe."""
1099         if not (
1100             self.leaves
1101             and self.leaves[-1].type == token.COMMA
1102             and closing.type in CLOSING_BRACKETS
1103         ):
1104             return False
1105
1106         if closing.type == token.RBRACE:
1107             self.remove_trailing_comma()
1108             return True
1109
1110         if closing.type == token.RSQB:
1111             comma = self.leaves[-1]
1112             if comma.parent and comma.parent.type == syms.listmaker:
1113                 self.remove_trailing_comma()
1114                 return True
1115
1116         # For parens let's check if it's safe to remove the comma.
1117         # Imports are always safe.
1118         if self.is_import:
1119             self.remove_trailing_comma()
1120             return True
1121
1122         # Otheriwsse, if the trailing one is the only one, we might mistakenly
1123         # change a tuple into a different type by removing the comma.
1124         depth = closing.bracket_depth + 1
1125         commas = 0
1126         opening = closing.opening_bracket
1127         for _opening_index, leaf in enumerate(self.leaves):
1128             if leaf is opening:
1129                 break
1130
1131         else:
1132             return False
1133
1134         for leaf in self.leaves[_opening_index + 1 :]:
1135             if leaf is closing:
1136                 break
1137
1138             bracket_depth = leaf.bracket_depth
1139             if bracket_depth == depth and leaf.type == token.COMMA:
1140                 commas += 1
1141                 if leaf.parent and leaf.parent.type == syms.arglist:
1142                     commas += 1
1143                     break
1144
1145         if commas > 1:
1146             self.remove_trailing_comma()
1147             return True
1148
1149         return False
1150
1151     def append_comment(self, comment: Leaf) -> bool:
1152         """Add an inline or standalone comment to the line."""
1153         if (
1154             comment.type == STANDALONE_COMMENT
1155             and self.bracket_tracker.any_open_brackets()
1156         ):
1157             comment.prefix = ""
1158             return False
1159
1160         if comment.type != token.COMMENT:
1161             return False
1162
1163         after = len(self.leaves) - 1
1164         if after == -1:
1165             comment.type = STANDALONE_COMMENT
1166             comment.prefix = ""
1167             return False
1168
1169         else:
1170             self.comments.append((after, comment))
1171             return True
1172
1173     def comments_after(self, leaf: Leaf, _index: int = -1) -> Iterator[Leaf]:
1174         """Generate comments that should appear directly after `leaf`.
1175
1176         Provide a non-negative leaf `_index` to speed up the function.
1177         """
1178         if _index == -1:
1179             for _index, _leaf in enumerate(self.leaves):
1180                 if leaf is _leaf:
1181                     break
1182
1183             else:
1184                 return
1185
1186         for index, comment_after in self.comments:
1187             if _index == index:
1188                 yield comment_after
1189
1190     def remove_trailing_comma(self) -> None:
1191         """Remove the trailing comma and moves the comments attached to it."""
1192         comma_index = len(self.leaves) - 1
1193         for i in range(len(self.comments)):
1194             comment_index, comment = self.comments[i]
1195             if comment_index == comma_index:
1196                 self.comments[i] = (comma_index - 1, comment)
1197         self.leaves.pop()
1198
1199     def is_complex_subscript(self, leaf: Leaf) -> bool:
1200         """Return True iff `leaf` is part of a slice with non-trivial exprs."""
1201         open_lsqb = (
1202             leaf if leaf.type == token.LSQB else self.bracket_tracker.get_open_lsqb()
1203         )
1204         if open_lsqb is None:
1205             return False
1206
1207         subscript_start = open_lsqb.next_sibling
1208         if (
1209             isinstance(subscript_start, Node)
1210             and subscript_start.type == syms.subscriptlist
1211         ):
1212             subscript_start = child_towards(subscript_start, leaf)
1213         return subscript_start is not None and any(
1214             n.type in TEST_DESCENDANTS for n in subscript_start.pre_order()
1215         )
1216
1217     def __str__(self) -> str:
1218         """Render the line."""
1219         if not self:
1220             return "\n"
1221
1222         indent = "    " * self.depth
1223         leaves = iter(self.leaves)
1224         first = next(leaves)
1225         res = f"{first.prefix}{indent}{first.value}"
1226         for leaf in leaves:
1227             res += str(leaf)
1228         for _, comment in self.comments:
1229             res += str(comment)
1230         return res + "\n"
1231
1232     def __bool__(self) -> bool:
1233         """Return True if the line has leaves or comments."""
1234         return bool(self.leaves or self.comments)
1235
1236
1237 class UnformattedLines(Line):
1238     """Just like :class:`Line` but stores lines which aren't reformatted."""
1239
1240     def append(self, leaf: Leaf, preformatted: bool = True) -> None:
1241         """Just add a new `leaf` to the end of the lines.
1242
1243         The `preformatted` argument is ignored.
1244
1245         Keeps track of indentation `depth`, which is useful when the user
1246         says `# fmt: on`. Otherwise, doesn't do anything with the `leaf`.
1247         """
1248         try:
1249             list(generate_comments(leaf))
1250         except FormatOn as f_on:
1251             self.leaves.append(f_on.leaf_from_consumed(leaf))
1252             raise
1253
1254         self.leaves.append(leaf)
1255         if leaf.type == token.INDENT:
1256             self.depth += 1
1257         elif leaf.type == token.DEDENT:
1258             self.depth -= 1
1259
1260     def __str__(self) -> str:
1261         """Render unformatted lines from leaves which were added with `append()`.
1262
1263         `depth` is not used for indentation in this case.
1264         """
1265         if not self:
1266             return "\n"
1267
1268         res = ""
1269         for leaf in self.leaves:
1270             res += str(leaf)
1271         return res
1272
1273     def append_comment(self, comment: Leaf) -> bool:
1274         """Not implemented in this class. Raises `NotImplementedError`."""
1275         raise NotImplementedError("Unformatted lines don't store comments separately.")
1276
1277     def maybe_remove_trailing_comma(self, closing: Leaf) -> bool:
1278         """Does nothing and returns False."""
1279         return False
1280
1281     def maybe_increment_for_loop_variable(self, leaf: Leaf) -> bool:
1282         """Does nothing and returns False."""
1283         return False
1284
1285
1286 @dataclass
1287 class EmptyLineTracker:
1288     """Provides a stateful method that returns the number of potential extra
1289     empty lines needed before and after the currently processed line.
1290
1291     Note: this tracker works on lines that haven't been split yet.  It assumes
1292     the prefix of the first leaf consists of optional newlines.  Those newlines
1293     are consumed by `maybe_empty_lines()` and included in the computation.
1294     """
1295
1296     is_pyi: bool = False
1297     previous_line: Optional[Line] = None
1298     previous_after: int = 0
1299     previous_defs: List[int] = Factory(list)
1300
1301     def maybe_empty_lines(self, current_line: Line) -> Tuple[int, int]:
1302         """Return the number of extra empty lines before and after the `current_line`.
1303
1304         This is for separating `def`, `async def` and `class` with extra empty
1305         lines (two on module-level).
1306         """
1307         if isinstance(current_line, UnformattedLines):
1308             return 0, 0
1309
1310         before, after = self._maybe_empty_lines(current_line)
1311         before -= self.previous_after
1312         self.previous_after = after
1313         self.previous_line = current_line
1314         return before, after
1315
1316     def _maybe_empty_lines(self, current_line: Line) -> Tuple[int, int]:
1317         max_allowed = 1
1318         if current_line.depth == 0:
1319             max_allowed = 1 if self.is_pyi else 2
1320         if current_line.leaves:
1321             # Consume the first leaf's extra newlines.
1322             first_leaf = current_line.leaves[0]
1323             before = first_leaf.prefix.count("\n")
1324             before = min(before, max_allowed)
1325             first_leaf.prefix = ""
1326         else:
1327             before = 0
1328         depth = current_line.depth
1329         while self.previous_defs and self.previous_defs[-1] >= depth:
1330             self.previous_defs.pop()
1331             if self.is_pyi:
1332                 before = 0 if depth else 1
1333             else:
1334                 before = 1 if depth else 2
1335         is_decorator = current_line.is_decorator
1336         if is_decorator or current_line.is_def or current_line.is_class:
1337             if not is_decorator:
1338                 self.previous_defs.append(depth)
1339             if self.previous_line is None:
1340                 # Don't insert empty lines before the first line in the file.
1341                 return 0, 0
1342
1343             if self.previous_line.is_decorator:
1344                 return 0, 0
1345
1346             if self.previous_line.depth < current_line.depth and (
1347                 self.previous_line.is_class or self.previous_line.is_def
1348             ):
1349                 return 0, 0
1350
1351             if (
1352                 self.previous_line.is_comment
1353                 and self.previous_line.depth == current_line.depth
1354                 and before == 0
1355             ):
1356                 return 0, 0
1357
1358             if self.is_pyi:
1359                 if self.previous_line.depth > current_line.depth:
1360                     newlines = 1
1361                 elif current_line.is_class or self.previous_line.is_class:
1362                     if current_line.is_stub_class and self.previous_line.is_stub_class:
1363                         newlines = 0
1364                     else:
1365                         newlines = 1
1366                 else:
1367                     newlines = 0
1368             else:
1369                 newlines = 2
1370             if current_line.depth and newlines:
1371                 newlines -= 1
1372             return newlines, 0
1373
1374         if (
1375             self.previous_line
1376             and self.previous_line.is_import
1377             and not current_line.is_import
1378             and depth == self.previous_line.depth
1379         ):
1380             return (before or 1), 0
1381
1382         if (
1383             self.previous_line
1384             and self.previous_line.is_class
1385             and current_line.is_triple_quoted_string
1386         ):
1387             return before, 1
1388
1389         return before, 0
1390
1391
1392 @dataclass
1393 class LineGenerator(Visitor[Line]):
1394     """Generates reformatted Line objects.  Empty lines are not emitted.
1395
1396     Note: destroys the tree it's visiting by mutating prefixes of its leaves
1397     in ways that will no longer stringify to valid Python code on the tree.
1398     """
1399
1400     is_pyi: bool = False
1401     normalize_strings: bool = True
1402     current_line: Line = Factory(Line)
1403     remove_u_prefix: bool = False
1404
1405     def line(self, indent: int = 0, type: Type[Line] = Line) -> Iterator[Line]:
1406         """Generate a line.
1407
1408         If the line is empty, only emit if it makes sense.
1409         If the line is too long, split it first and then generate.
1410
1411         If any lines were generated, set up a new current_line.
1412         """
1413         if not self.current_line:
1414             if self.current_line.__class__ == type:
1415                 self.current_line.depth += indent
1416             else:
1417                 self.current_line = type(depth=self.current_line.depth + indent)
1418             return  # Line is empty, don't emit. Creating a new one unnecessary.
1419
1420         complete_line = self.current_line
1421         self.current_line = type(depth=complete_line.depth + indent)
1422         yield complete_line
1423
1424     def visit(self, node: LN) -> Iterator[Line]:
1425         """Main method to visit `node` and its children.
1426
1427         Yields :class:`Line` objects.
1428         """
1429         if isinstance(self.current_line, UnformattedLines):
1430             # File contained `# fmt: off`
1431             yield from self.visit_unformatted(node)
1432
1433         else:
1434             yield from super().visit(node)
1435
1436     def visit_default(self, node: LN) -> Iterator[Line]:
1437         """Default `visit_*()` implementation. Recurses to children of `node`."""
1438         if isinstance(node, Leaf):
1439             any_open_brackets = self.current_line.bracket_tracker.any_open_brackets()
1440             try:
1441                 for comment in generate_comments(node):
1442                     if any_open_brackets:
1443                         # any comment within brackets is subject to splitting
1444                         self.current_line.append(comment)
1445                     elif comment.type == token.COMMENT:
1446                         # regular trailing comment
1447                         self.current_line.append(comment)
1448                         yield from self.line()
1449
1450                     else:
1451                         # regular standalone comment
1452                         yield from self.line()
1453
1454                         self.current_line.append(comment)
1455                         yield from self.line()
1456
1457             except FormatOff as f_off:
1458                 f_off.trim_prefix(node)
1459                 yield from self.line(type=UnformattedLines)
1460                 yield from self.visit(node)
1461
1462             except FormatOn as f_on:
1463                 # This only happens here if somebody says "fmt: on" multiple
1464                 # times in a row.
1465                 f_on.trim_prefix(node)
1466                 yield from self.visit_default(node)
1467
1468             else:
1469                 normalize_prefix(node, inside_brackets=any_open_brackets)
1470                 if self.normalize_strings and node.type == token.STRING:
1471                     normalize_string_prefix(node, remove_u_prefix=self.remove_u_prefix)
1472                     normalize_string_quotes(node)
1473                 if node.type not in WHITESPACE:
1474                     self.current_line.append(node)
1475         yield from super().visit_default(node)
1476
1477     def visit_INDENT(self, node: Node) -> Iterator[Line]:
1478         """Increase indentation level, maybe yield a line."""
1479         # In blib2to3 INDENT never holds comments.
1480         yield from self.line(+1)
1481         yield from self.visit_default(node)
1482
1483     def visit_DEDENT(self, node: Node) -> Iterator[Line]:
1484         """Decrease indentation level, maybe yield a line."""
1485         # The current line might still wait for trailing comments.  At DEDENT time
1486         # there won't be any (they would be prefixes on the preceding NEWLINE).
1487         # Emit the line then.
1488         yield from self.line()
1489
1490         # While DEDENT has no value, its prefix may contain standalone comments
1491         # that belong to the current indentation level.  Get 'em.
1492         yield from self.visit_default(node)
1493
1494         # Finally, emit the dedent.
1495         yield from self.line(-1)
1496
1497     def visit_stmt(
1498         self, node: Node, keywords: Set[str], parens: Set[str]
1499     ) -> Iterator[Line]:
1500         """Visit a statement.
1501
1502         This implementation is shared for `if`, `while`, `for`, `try`, `except`,
1503         `def`, `with`, `class`, `assert` and assignments.
1504
1505         The relevant Python language `keywords` for a given statement will be
1506         NAME leaves within it. This methods puts those on a separate line.
1507
1508         `parens` holds a set of string leaf values immediately after which
1509         invisible parens should be put.
1510         """
1511         normalize_invisible_parens(node, parens_after=parens)
1512         for child in node.children:
1513             if child.type == token.NAME and child.value in keywords:  # type: ignore
1514                 yield from self.line()
1515
1516             yield from self.visit(child)
1517
1518     def visit_suite(self, node: Node) -> Iterator[Line]:
1519         """Visit a suite."""
1520         if self.is_pyi and is_stub_suite(node):
1521             yield from self.visit(node.children[2])
1522         else:
1523             yield from self.visit_default(node)
1524
1525     def visit_simple_stmt(self, node: Node) -> Iterator[Line]:
1526         """Visit a statement without nested statements."""
1527         is_suite_like = node.parent and node.parent.type in STATEMENT
1528         if is_suite_like:
1529             if self.is_pyi and is_stub_body(node):
1530                 yield from self.visit_default(node)
1531             else:
1532                 yield from self.line(+1)
1533                 yield from self.visit_default(node)
1534                 yield from self.line(-1)
1535
1536         else:
1537             if not self.is_pyi or not node.parent or not is_stub_suite(node.parent):
1538                 yield from self.line()
1539             yield from self.visit_default(node)
1540
1541     def visit_async_stmt(self, node: Node) -> Iterator[Line]:
1542         """Visit `async def`, `async for`, `async with`."""
1543         yield from self.line()
1544
1545         children = iter(node.children)
1546         for child in children:
1547             yield from self.visit(child)
1548
1549             if child.type == token.ASYNC:
1550                 break
1551
1552         internal_stmt = next(children)
1553         for child in internal_stmt.children:
1554             yield from self.visit(child)
1555
1556     def visit_decorators(self, node: Node) -> Iterator[Line]:
1557         """Visit decorators."""
1558         for child in node.children:
1559             yield from self.line()
1560             yield from self.visit(child)
1561
1562     def visit_SEMI(self, leaf: Leaf) -> Iterator[Line]:
1563         """Remove a semicolon and put the other statement on a separate line."""
1564         yield from self.line()
1565
1566     def visit_ENDMARKER(self, leaf: Leaf) -> Iterator[Line]:
1567         """End of file. Process outstanding comments and end with a newline."""
1568         yield from self.visit_default(leaf)
1569         yield from self.line()
1570
1571     def visit_unformatted(self, node: LN) -> Iterator[Line]:
1572         """Used when file contained a `# fmt: off`."""
1573         if isinstance(node, Node):
1574             for child in node.children:
1575                 yield from self.visit(child)
1576
1577         else:
1578             try:
1579                 self.current_line.append(node)
1580             except FormatOn as f_on:
1581                 f_on.trim_prefix(node)
1582                 yield from self.line()
1583                 yield from self.visit(node)
1584
1585             if node.type == token.ENDMARKER:
1586                 # somebody decided not to put a final `# fmt: on`
1587                 yield from self.line()
1588
1589     def __attrs_post_init__(self) -> None:
1590         """You are in a twisty little maze of passages."""
1591         v = self.visit_stmt
1592         Ø: Set[str] = set()
1593         self.visit_assert_stmt = partial(v, keywords={"assert"}, parens={"assert", ","})
1594         self.visit_if_stmt = partial(
1595             v, keywords={"if", "else", "elif"}, parens={"if", "elif"}
1596         )
1597         self.visit_while_stmt = partial(v, keywords={"while", "else"}, parens={"while"})
1598         self.visit_for_stmt = partial(v, keywords={"for", "else"}, parens={"for", "in"})
1599         self.visit_try_stmt = partial(
1600             v, keywords={"try", "except", "else", "finally"}, parens=Ø
1601         )
1602         self.visit_except_clause = partial(v, keywords={"except"}, parens=Ø)
1603         self.visit_with_stmt = partial(v, keywords={"with"}, parens=Ø)
1604         self.visit_funcdef = partial(v, keywords={"def"}, parens=Ø)
1605         self.visit_classdef = partial(v, keywords={"class"}, parens=Ø)
1606         self.visit_expr_stmt = partial(v, keywords=Ø, parens=ASSIGNMENTS)
1607         self.visit_return_stmt = partial(v, keywords={"return"}, parens={"return"})
1608         self.visit_import_from = partial(v, keywords=Ø, parens={"import"})
1609         self.visit_async_funcdef = self.visit_async_stmt
1610         self.visit_decorated = self.visit_decorators
1611
1612
1613 IMPLICIT_TUPLE = {syms.testlist, syms.testlist_star_expr, syms.exprlist}
1614 BRACKET = {token.LPAR: token.RPAR, token.LSQB: token.RSQB, token.LBRACE: token.RBRACE}
1615 OPENING_BRACKETS = set(BRACKET.keys())
1616 CLOSING_BRACKETS = set(BRACKET.values())
1617 BRACKETS = OPENING_BRACKETS | CLOSING_BRACKETS
1618 ALWAYS_NO_SPACE = CLOSING_BRACKETS | {token.COMMA, STANDALONE_COMMENT}
1619
1620
1621 def whitespace(leaf: Leaf, *, complex_subscript: bool) -> str:  # noqa C901
1622     """Return whitespace prefix if needed for the given `leaf`.
1623
1624     `complex_subscript` signals whether the given leaf is part of a subscription
1625     which has non-trivial arguments, like arithmetic expressions or function calls.
1626     """
1627     NO = ""
1628     SPACE = " "
1629     DOUBLESPACE = "  "
1630     t = leaf.type
1631     p = leaf.parent
1632     v = leaf.value
1633     if t in ALWAYS_NO_SPACE:
1634         return NO
1635
1636     if t == token.COMMENT:
1637         return DOUBLESPACE
1638
1639     assert p is not None, f"INTERNAL ERROR: hand-made leaf without parent: {leaf!r}"
1640     if t == token.COLON and p.type not in {
1641         syms.subscript,
1642         syms.subscriptlist,
1643         syms.sliceop,
1644     }:
1645         return NO
1646
1647     prev = leaf.prev_sibling
1648     if not prev:
1649         prevp = preceding_leaf(p)
1650         if not prevp or prevp.type in OPENING_BRACKETS:
1651             return NO
1652
1653         if t == token.COLON:
1654             if prevp.type == token.COLON:
1655                 return NO
1656
1657             elif prevp.type != token.COMMA and not complex_subscript:
1658                 return NO
1659
1660             return SPACE
1661
1662         if prevp.type == token.EQUAL:
1663             if prevp.parent:
1664                 if prevp.parent.type in {
1665                     syms.arglist,
1666                     syms.argument,
1667                     syms.parameters,
1668                     syms.varargslist,
1669                 }:
1670                     return NO
1671
1672                 elif prevp.parent.type == syms.typedargslist:
1673                     # A bit hacky: if the equal sign has whitespace, it means we
1674                     # previously found it's a typed argument.  So, we're using
1675                     # that, too.
1676                     return prevp.prefix
1677
1678         elif prevp.type in STARS:
1679             if is_vararg(prevp, within=VARARGS_PARENTS | UNPACKING_PARENTS):
1680                 return NO
1681
1682         elif prevp.type == token.COLON:
1683             if prevp.parent and prevp.parent.type in {syms.subscript, syms.sliceop}:
1684                 return SPACE if complex_subscript else NO
1685
1686         elif (
1687             prevp.parent
1688             and prevp.parent.type == syms.factor
1689             and prevp.type in MATH_OPERATORS
1690         ):
1691             return NO
1692
1693         elif (
1694             prevp.type == token.RIGHTSHIFT
1695             and prevp.parent
1696             and prevp.parent.type == syms.shift_expr
1697             and prevp.prev_sibling
1698             and prevp.prev_sibling.type == token.NAME
1699             and prevp.prev_sibling.value == "print"  # type: ignore
1700         ):
1701             # Python 2 print chevron
1702             return NO
1703
1704     elif prev.type in OPENING_BRACKETS:
1705         return NO
1706
1707     if p.type in {syms.parameters, syms.arglist}:
1708         # untyped function signatures or calls
1709         if not prev or prev.type != token.COMMA:
1710             return NO
1711
1712     elif p.type == syms.varargslist:
1713         # lambdas
1714         if prev and prev.type != token.COMMA:
1715             return NO
1716
1717     elif p.type == syms.typedargslist:
1718         # typed function signatures
1719         if not prev:
1720             return NO
1721
1722         if t == token.EQUAL:
1723             if prev.type != syms.tname:
1724                 return NO
1725
1726         elif prev.type == token.EQUAL:
1727             # A bit hacky: if the equal sign has whitespace, it means we
1728             # previously found it's a typed argument.  So, we're using that, too.
1729             return prev.prefix
1730
1731         elif prev.type != token.COMMA:
1732             return NO
1733
1734     elif p.type == syms.tname:
1735         # type names
1736         if not prev:
1737             prevp = preceding_leaf(p)
1738             if not prevp or prevp.type != token.COMMA:
1739                 return NO
1740
1741     elif p.type == syms.trailer:
1742         # attributes and calls
1743         if t == token.LPAR or t == token.RPAR:
1744             return NO
1745
1746         if not prev:
1747             if t == token.DOT:
1748                 prevp = preceding_leaf(p)
1749                 if not prevp or prevp.type != token.NUMBER:
1750                     return NO
1751
1752             elif t == token.LSQB:
1753                 return NO
1754
1755         elif prev.type != token.COMMA:
1756             return NO
1757
1758     elif p.type == syms.argument:
1759         # single argument
1760         if t == token.EQUAL:
1761             return NO
1762
1763         if not prev:
1764             prevp = preceding_leaf(p)
1765             if not prevp or prevp.type == token.LPAR:
1766                 return NO
1767
1768         elif prev.type in {token.EQUAL} | STARS:
1769             return NO
1770
1771     elif p.type == syms.decorator:
1772         # decorators
1773         return NO
1774
1775     elif p.type == syms.dotted_name:
1776         if prev:
1777             return NO
1778
1779         prevp = preceding_leaf(p)
1780         if not prevp or prevp.type == token.AT or prevp.type == token.DOT:
1781             return NO
1782
1783     elif p.type == syms.classdef:
1784         if t == token.LPAR:
1785             return NO
1786
1787         if prev and prev.type == token.LPAR:
1788             return NO
1789
1790     elif p.type in {syms.subscript, syms.sliceop}:
1791         # indexing
1792         if not prev:
1793             assert p.parent is not None, "subscripts are always parented"
1794             if p.parent.type == syms.subscriptlist:
1795                 return SPACE
1796
1797             return NO
1798
1799         elif not complex_subscript:
1800             return NO
1801
1802     elif p.type == syms.atom:
1803         if prev and t == token.DOT:
1804             # dots, but not the first one.
1805             return NO
1806
1807     elif p.type == syms.dictsetmaker:
1808         # dict unpacking
1809         if prev and prev.type == token.DOUBLESTAR:
1810             return NO
1811
1812     elif p.type in {syms.factor, syms.star_expr}:
1813         # unary ops
1814         if not prev:
1815             prevp = preceding_leaf(p)
1816             if not prevp or prevp.type in OPENING_BRACKETS:
1817                 return NO
1818
1819             prevp_parent = prevp.parent
1820             assert prevp_parent is not None
1821             if prevp.type == token.COLON and prevp_parent.type in {
1822                 syms.subscript,
1823                 syms.sliceop,
1824             }:
1825                 return NO
1826
1827             elif prevp.type == token.EQUAL and prevp_parent.type == syms.argument:
1828                 return NO
1829
1830         elif t == token.NAME or t == token.NUMBER:
1831             return NO
1832
1833     elif p.type == syms.import_from:
1834         if t == token.DOT:
1835             if prev and prev.type == token.DOT:
1836                 return NO
1837
1838         elif t == token.NAME:
1839             if v == "import":
1840                 return SPACE
1841
1842             if prev and prev.type == token.DOT:
1843                 return NO
1844
1845     elif p.type == syms.sliceop:
1846         return NO
1847
1848     return SPACE
1849
1850
1851 def preceding_leaf(node: Optional[LN]) -> Optional[Leaf]:
1852     """Return the first leaf that precedes `node`, if any."""
1853     while node:
1854         res = node.prev_sibling
1855         if res:
1856             if isinstance(res, Leaf):
1857                 return res
1858
1859             try:
1860                 return list(res.leaves())[-1]
1861
1862             except IndexError:
1863                 return None
1864
1865         node = node.parent
1866     return None
1867
1868
1869 def child_towards(ancestor: Node, descendant: LN) -> Optional[LN]:
1870     """Return the child of `ancestor` that contains `descendant`."""
1871     node: Optional[LN] = descendant
1872     while node and node.parent != ancestor:
1873         node = node.parent
1874     return node
1875
1876
1877 def is_split_after_delimiter(leaf: Leaf, previous: Leaf = None) -> int:
1878     """Return the priority of the `leaf` delimiter, given a line break after it.
1879
1880     The delimiter priorities returned here are from those delimiters that would
1881     cause a line break after themselves.
1882
1883     Higher numbers are higher priority.
1884     """
1885     if leaf.type == token.COMMA:
1886         return COMMA_PRIORITY
1887
1888     return 0
1889
1890
1891 def is_split_before_delimiter(leaf: Leaf, previous: Leaf = None) -> int:
1892     """Return the priority of the `leaf` delimiter, given a line before after it.
1893
1894     The delimiter priorities returned here are from those delimiters that would
1895     cause a line break before themselves.
1896
1897     Higher numbers are higher priority.
1898     """
1899     if is_vararg(leaf, within=VARARGS_PARENTS | UNPACKING_PARENTS):
1900         # * and ** might also be MATH_OPERATORS but in this case they are not.
1901         # Don't treat them as a delimiter.
1902         return 0
1903
1904     if (
1905         leaf.type == token.DOT
1906         and leaf.parent
1907         and leaf.parent.type not in {syms.import_from, syms.dotted_name}
1908         and (previous is None or previous.type in CLOSING_BRACKETS)
1909     ):
1910         return DOT_PRIORITY
1911
1912     if (
1913         leaf.type in MATH_OPERATORS
1914         and leaf.parent
1915         and leaf.parent.type not in {syms.factor, syms.star_expr}
1916     ):
1917         return MATH_PRIORITIES[leaf.type]
1918
1919     if leaf.type in COMPARATORS:
1920         return COMPARATOR_PRIORITY
1921
1922     if (
1923         leaf.type == token.STRING
1924         and previous is not None
1925         and previous.type == token.STRING
1926     ):
1927         return STRING_PRIORITY
1928
1929     if leaf.type != token.NAME:
1930         return 0
1931
1932     if (
1933         leaf.value == "for"
1934         and leaf.parent
1935         and leaf.parent.type in {syms.comp_for, syms.old_comp_for}
1936     ):
1937         return COMPREHENSION_PRIORITY
1938
1939     if (
1940         leaf.value == "if"
1941         and leaf.parent
1942         and leaf.parent.type in {syms.comp_if, syms.old_comp_if}
1943     ):
1944         return COMPREHENSION_PRIORITY
1945
1946     if leaf.value in {"if", "else"} and leaf.parent and leaf.parent.type == syms.test:
1947         return TERNARY_PRIORITY
1948
1949     if leaf.value == "is":
1950         return COMPARATOR_PRIORITY
1951
1952     if (
1953         leaf.value == "in"
1954         and leaf.parent
1955         and leaf.parent.type in {syms.comp_op, syms.comparison}
1956         and not (
1957             previous is not None
1958             and previous.type == token.NAME
1959             and previous.value == "not"
1960         )
1961     ):
1962         return COMPARATOR_PRIORITY
1963
1964     if (
1965         leaf.value == "not"
1966         and leaf.parent
1967         and leaf.parent.type == syms.comp_op
1968         and not (
1969             previous is not None
1970             and previous.type == token.NAME
1971             and previous.value == "is"
1972         )
1973     ):
1974         return COMPARATOR_PRIORITY
1975
1976     if leaf.value in LOGIC_OPERATORS and leaf.parent:
1977         return LOGIC_PRIORITY
1978
1979     return 0
1980
1981
1982 def generate_comments(leaf: LN) -> Iterator[Leaf]:
1983     """Clean the prefix of the `leaf` and generate comments from it, if any.
1984
1985     Comments in lib2to3 are shoved into the whitespace prefix.  This happens
1986     in `pgen2/driver.py:Driver.parse_tokens()`.  This was a brilliant implementation
1987     move because it does away with modifying the grammar to include all the
1988     possible places in which comments can be placed.
1989
1990     The sad consequence for us though is that comments don't "belong" anywhere.
1991     This is why this function generates simple parentless Leaf objects for
1992     comments.  We simply don't know what the correct parent should be.
1993
1994     No matter though, we can live without this.  We really only need to
1995     differentiate between inline and standalone comments.  The latter don't
1996     share the line with any code.
1997
1998     Inline comments are emitted as regular token.COMMENT leaves.  Standalone
1999     are emitted with a fake STANDALONE_COMMENT token identifier.
2000     """
2001     p = leaf.prefix
2002     if not p:
2003         return
2004
2005     if "#" not in p:
2006         return
2007
2008     consumed = 0
2009     nlines = 0
2010     for index, line in enumerate(p.split("\n")):
2011         consumed += len(line) + 1  # adding the length of the split '\n'
2012         line = line.lstrip()
2013         if not line:
2014             nlines += 1
2015         if not line.startswith("#"):
2016             continue
2017
2018         if index == 0 and leaf.type != token.ENDMARKER:
2019             comment_type = token.COMMENT  # simple trailing comment
2020         else:
2021             comment_type = STANDALONE_COMMENT
2022         comment = make_comment(line)
2023         yield Leaf(comment_type, comment, prefix="\n" * nlines)
2024
2025         if comment in {"# fmt: on", "# yapf: enable"}:
2026             raise FormatOn(consumed)
2027
2028         if comment in {"# fmt: off", "# yapf: disable"}:
2029             if comment_type == STANDALONE_COMMENT:
2030                 raise FormatOff(consumed)
2031
2032             prev = preceding_leaf(leaf)
2033             if not prev or prev.type in WHITESPACE:  # standalone comment in disguise
2034                 raise FormatOff(consumed)
2035
2036         nlines = 0
2037
2038
2039 def make_comment(content: str) -> str:
2040     """Return a consistently formatted comment from the given `content` string.
2041
2042     All comments (except for "##", "#!", "#:") should have a single space between
2043     the hash sign and the content.
2044
2045     If `content` didn't start with a hash sign, one is provided.
2046     """
2047     content = content.rstrip()
2048     if not content:
2049         return "#"
2050
2051     if content[0] == "#":
2052         content = content[1:]
2053     if content and content[0] not in " !:#":
2054         content = " " + content
2055     return "#" + content
2056
2057
2058 def split_line(
2059     line: Line, line_length: int, inner: bool = False, py36: bool = False
2060 ) -> Iterator[Line]:
2061     """Split a `line` into potentially many lines.
2062
2063     They should fit in the allotted `line_length` but might not be able to.
2064     `inner` signifies that there were a pair of brackets somewhere around the
2065     current `line`, possibly transitively. This means we can fallback to splitting
2066     by delimiters if the LHS/RHS don't yield any results.
2067
2068     If `py36` is True, splitting may generate syntax that is only compatible
2069     with Python 3.6 and later.
2070     """
2071     if isinstance(line, UnformattedLines) or line.is_comment:
2072         yield line
2073         return
2074
2075     line_str = str(line).strip("\n")
2076     if not line.should_explode and is_line_short_enough(
2077         line, line_length=line_length, line_str=line_str
2078     ):
2079         yield line
2080         return
2081
2082     split_funcs: List[SplitFunc]
2083     if line.is_def:
2084         split_funcs = [left_hand_split]
2085     else:
2086
2087         def rhs(line: Line, py36: bool = False) -> Iterator[Line]:
2088             for omit in generate_trailers_to_omit(line, line_length):
2089                 lines = list(right_hand_split(line, line_length, py36, omit=omit))
2090                 if is_line_short_enough(lines[0], line_length=line_length):
2091                     yield from lines
2092                     return
2093
2094             # All splits failed, best effort split with no omits.
2095             # This mostly happens to multiline strings that are by definition
2096             # reported as not fitting a single line.
2097             yield from right_hand_split(line, py36)
2098
2099         if line.inside_brackets:
2100             split_funcs = [delimiter_split, standalone_comment_split, rhs]
2101         else:
2102             split_funcs = [rhs]
2103     for split_func in split_funcs:
2104         # We are accumulating lines in `result` because we might want to abort
2105         # mission and return the original line in the end, or attempt a different
2106         # split altogether.
2107         result: List[Line] = []
2108         try:
2109             for l in split_func(line, py36):
2110                 if str(l).strip("\n") == line_str:
2111                     raise CannotSplit("Split function returned an unchanged result")
2112
2113                 result.extend(
2114                     split_line(l, line_length=line_length, inner=True, py36=py36)
2115                 )
2116         except CannotSplit as cs:
2117             continue
2118
2119         else:
2120             yield from result
2121             break
2122
2123     else:
2124         yield line
2125
2126
2127 def left_hand_split(line: Line, py36: bool = False) -> Iterator[Line]:
2128     """Split line into many lines, starting with the first matching bracket pair.
2129
2130     Note: this usually looks weird, only use this for function definitions.
2131     Prefer RHS otherwise.  This is why this function is not symmetrical with
2132     :func:`right_hand_split` which also handles optional parentheses.
2133     """
2134     head = Line(depth=line.depth)
2135     body = Line(depth=line.depth + 1, inside_brackets=True)
2136     tail = Line(depth=line.depth)
2137     tail_leaves: List[Leaf] = []
2138     body_leaves: List[Leaf] = []
2139     head_leaves: List[Leaf] = []
2140     current_leaves = head_leaves
2141     matching_bracket = None
2142     for leaf in line.leaves:
2143         if (
2144             current_leaves is body_leaves
2145             and leaf.type in CLOSING_BRACKETS
2146             and leaf.opening_bracket is matching_bracket
2147         ):
2148             current_leaves = tail_leaves if body_leaves else head_leaves
2149         current_leaves.append(leaf)
2150         if current_leaves is head_leaves:
2151             if leaf.type in OPENING_BRACKETS:
2152                 matching_bracket = leaf
2153                 current_leaves = body_leaves
2154     # Since body is a new indent level, remove spurious leading whitespace.
2155     if body_leaves:
2156         normalize_prefix(body_leaves[0], inside_brackets=True)
2157     # Build the new lines.
2158     for result, leaves in (head, head_leaves), (body, body_leaves), (tail, tail_leaves):
2159         for leaf in leaves:
2160             result.append(leaf, preformatted=True)
2161             for comment_after in line.comments_after(leaf):
2162                 result.append(comment_after, preformatted=True)
2163     bracket_split_succeeded_or_raise(head, body, tail)
2164     for result in (head, body, tail):
2165         if result:
2166             yield result
2167
2168
2169 def right_hand_split(
2170     line: Line, line_length: int, py36: bool = False, omit: Collection[LeafID] = ()
2171 ) -> Iterator[Line]:
2172     """Split line into many lines, starting with the last matching bracket pair.
2173
2174     If the split was by optional parentheses, attempt splitting without them, too.
2175     `omit` is a collection of closing bracket IDs that shouldn't be considered for
2176     this split.
2177
2178     Note: running this function modifies `bracket_depth` on the leaves of `line`.
2179     """
2180     head = Line(depth=line.depth)
2181     body = Line(depth=line.depth + 1, inside_brackets=True)
2182     tail = Line(depth=line.depth)
2183     tail_leaves: List[Leaf] = []
2184     body_leaves: List[Leaf] = []
2185     head_leaves: List[Leaf] = []
2186     current_leaves = tail_leaves
2187     opening_bracket = None
2188     closing_bracket = None
2189     for leaf in reversed(line.leaves):
2190         if current_leaves is body_leaves:
2191             if leaf is opening_bracket:
2192                 current_leaves = head_leaves if body_leaves else tail_leaves
2193         current_leaves.append(leaf)
2194         if current_leaves is tail_leaves:
2195             if leaf.type in CLOSING_BRACKETS and id(leaf) not in omit:
2196                 opening_bracket = leaf.opening_bracket
2197                 closing_bracket = leaf
2198                 current_leaves = body_leaves
2199     tail_leaves.reverse()
2200     body_leaves.reverse()
2201     head_leaves.reverse()
2202     # Since body is a new indent level, remove spurious leading whitespace.
2203     if body_leaves:
2204         normalize_prefix(body_leaves[0], inside_brackets=True)
2205     if not head_leaves:
2206         # No `head` means the split failed. Either `tail` has all content or
2207         # the matching `opening_bracket` wasn't available on `line` anymore.
2208         raise CannotSplit("No brackets found")
2209
2210     # Build the new lines.
2211     for result, leaves in (head, head_leaves), (body, body_leaves), (tail, tail_leaves):
2212         for leaf in leaves:
2213             result.append(leaf, preformatted=True)
2214             for comment_after in line.comments_after(leaf):
2215                 result.append(comment_after, preformatted=True)
2216     bracket_split_succeeded_or_raise(head, body, tail)
2217     assert opening_bracket and closing_bracket
2218     if (
2219         # the opening bracket is an optional paren
2220         opening_bracket.type == token.LPAR
2221         and not opening_bracket.value
2222         # the closing bracket is an optional paren
2223         and closing_bracket.type == token.RPAR
2224         and not closing_bracket.value
2225         # there are no standalone comments in the body
2226         and not line.contains_standalone_comments(0)
2227         # and it's not an import (optional parens are the only thing we can split
2228         # on in this case; attempting a split without them is a waste of time)
2229         and not line.is_import
2230     ):
2231         omit = {id(closing_bracket), *omit}
2232         if can_omit_invisible_parens(body, line_length):
2233             try:
2234                 yield from right_hand_split(line, line_length, py36=py36, omit=omit)
2235                 return
2236             except CannotSplit:
2237                 pass
2238
2239     ensure_visible(opening_bracket)
2240     ensure_visible(closing_bracket)
2241     body.should_explode = should_explode(body, opening_bracket)
2242     for result in (head, body, tail):
2243         if result:
2244             yield result
2245
2246
2247 def bracket_split_succeeded_or_raise(head: Line, body: Line, tail: Line) -> None:
2248     """Raise :exc:`CannotSplit` if the last left- or right-hand split failed.
2249
2250     Do nothing otherwise.
2251
2252     A left- or right-hand split is based on a pair of brackets. Content before
2253     (and including) the opening bracket is left on one line, content inside the
2254     brackets is put on a separate line, and finally content starting with and
2255     following the closing bracket is put on a separate line.
2256
2257     Those are called `head`, `body`, and `tail`, respectively. If the split
2258     produced the same line (all content in `head`) or ended up with an empty `body`
2259     and the `tail` is just the closing bracket, then it's considered failed.
2260     """
2261     tail_len = len(str(tail).strip())
2262     if not body:
2263         if tail_len == 0:
2264             raise CannotSplit("Splitting brackets produced the same line")
2265
2266         elif tail_len < 3:
2267             raise CannotSplit(
2268                 f"Splitting brackets on an empty body to save "
2269                 f"{tail_len} characters is not worth it"
2270             )
2271
2272
2273 def dont_increase_indentation(split_func: SplitFunc) -> SplitFunc:
2274     """Normalize prefix of the first leaf in every line returned by `split_func`.
2275
2276     This is a decorator over relevant split functions.
2277     """
2278
2279     @wraps(split_func)
2280     def split_wrapper(line: Line, py36: bool = False) -> Iterator[Line]:
2281         for l in split_func(line, py36):
2282             normalize_prefix(l.leaves[0], inside_brackets=True)
2283             yield l
2284
2285     return split_wrapper
2286
2287
2288 @dont_increase_indentation
2289 def delimiter_split(line: Line, py36: bool = False) -> Iterator[Line]:
2290     """Split according to delimiters of the highest priority.
2291
2292     If `py36` is True, the split will add trailing commas also in function
2293     signatures that contain `*` and `**`.
2294     """
2295     try:
2296         last_leaf = line.leaves[-1]
2297     except IndexError:
2298         raise CannotSplit("Line empty")
2299
2300     bt = line.bracket_tracker
2301     try:
2302         delimiter_priority = bt.max_delimiter_priority(exclude={id(last_leaf)})
2303     except ValueError:
2304         raise CannotSplit("No delimiters found")
2305
2306     if delimiter_priority == DOT_PRIORITY:
2307         if bt.delimiter_count_with_priority(delimiter_priority) == 1:
2308             raise CannotSplit("Splitting a single attribute from its owner looks wrong")
2309
2310     current_line = Line(depth=line.depth, inside_brackets=line.inside_brackets)
2311     lowest_depth = sys.maxsize
2312     trailing_comma_safe = True
2313
2314     def append_to_line(leaf: Leaf) -> Iterator[Line]:
2315         """Append `leaf` to current line or to new line if appending impossible."""
2316         nonlocal current_line
2317         try:
2318             current_line.append_safe(leaf, preformatted=True)
2319         except ValueError as ve:
2320             yield current_line
2321
2322             current_line = Line(depth=line.depth, inside_brackets=line.inside_brackets)
2323             current_line.append(leaf)
2324
2325     for index, leaf in enumerate(line.leaves):
2326         yield from append_to_line(leaf)
2327
2328         for comment_after in line.comments_after(leaf, index):
2329             yield from append_to_line(comment_after)
2330
2331         lowest_depth = min(lowest_depth, leaf.bracket_depth)
2332         if leaf.bracket_depth == lowest_depth and is_vararg(
2333             leaf, within=VARARGS_PARENTS
2334         ):
2335             trailing_comma_safe = trailing_comma_safe and py36
2336         leaf_priority = bt.delimiters.get(id(leaf))
2337         if leaf_priority == delimiter_priority:
2338             yield current_line
2339
2340             current_line = Line(depth=line.depth, inside_brackets=line.inside_brackets)
2341     if current_line:
2342         if (
2343             trailing_comma_safe
2344             and delimiter_priority == COMMA_PRIORITY
2345             and current_line.leaves[-1].type != token.COMMA
2346             and current_line.leaves[-1].type != STANDALONE_COMMENT
2347         ):
2348             current_line.append(Leaf(token.COMMA, ","))
2349         yield current_line
2350
2351
2352 @dont_increase_indentation
2353 def standalone_comment_split(line: Line, py36: bool = False) -> Iterator[Line]:
2354     """Split standalone comments from the rest of the line."""
2355     if not line.contains_standalone_comments(0):
2356         raise CannotSplit("Line does not have any standalone comments")
2357
2358     current_line = Line(depth=line.depth, inside_brackets=line.inside_brackets)
2359
2360     def append_to_line(leaf: Leaf) -> Iterator[Line]:
2361         """Append `leaf` to current line or to new line if appending impossible."""
2362         nonlocal current_line
2363         try:
2364             current_line.append_safe(leaf, preformatted=True)
2365         except ValueError as ve:
2366             yield current_line
2367
2368             current_line = Line(depth=line.depth, inside_brackets=line.inside_brackets)
2369             current_line.append(leaf)
2370
2371     for index, leaf in enumerate(line.leaves):
2372         yield from append_to_line(leaf)
2373
2374         for comment_after in line.comments_after(leaf, index):
2375             yield from append_to_line(comment_after)
2376
2377     if current_line:
2378         yield current_line
2379
2380
2381 def is_import(leaf: Leaf) -> bool:
2382     """Return True if the given leaf starts an import statement."""
2383     p = leaf.parent
2384     t = leaf.type
2385     v = leaf.value
2386     return bool(
2387         t == token.NAME
2388         and (
2389             (v == "import" and p and p.type == syms.import_name)
2390             or (v == "from" and p and p.type == syms.import_from)
2391         )
2392     )
2393
2394
2395 def normalize_prefix(leaf: Leaf, *, inside_brackets: bool) -> None:
2396     """Leave existing extra newlines if not `inside_brackets`. Remove everything
2397     else.
2398
2399     Note: don't use backslashes for formatting or you'll lose your voting rights.
2400     """
2401     if not inside_brackets:
2402         spl = leaf.prefix.split("#")
2403         if "\\" not in spl[0]:
2404             nl_count = spl[-1].count("\n")
2405             if len(spl) > 1:
2406                 nl_count -= 1
2407             leaf.prefix = "\n" * nl_count
2408             return
2409
2410     leaf.prefix = ""
2411
2412
2413 def normalize_string_prefix(leaf: Leaf, remove_u_prefix: bool = False) -> None:
2414     """Make all string prefixes lowercase.
2415
2416     If remove_u_prefix is given, also removes any u prefix from the string.
2417
2418     Note: Mutates its argument.
2419     """
2420     match = re.match(r"^([furbFURB]*)(.*)$", leaf.value, re.DOTALL)
2421     assert match is not None, f"failed to match string {leaf.value!r}"
2422     orig_prefix = match.group(1)
2423     new_prefix = orig_prefix.lower()
2424     if remove_u_prefix:
2425         new_prefix = new_prefix.replace("u", "")
2426     leaf.value = f"{new_prefix}{match.group(2)}"
2427
2428
2429 def normalize_string_quotes(leaf: Leaf) -> None:
2430     """Prefer double quotes but only if it doesn't cause more escaping.
2431
2432     Adds or removes backslashes as appropriate. Doesn't parse and fix
2433     strings nested in f-strings (yet).
2434
2435     Note: Mutates its argument.
2436     """
2437     value = leaf.value.lstrip("furbFURB")
2438     if value[:3] == '"""':
2439         return
2440
2441     elif value[:3] == "'''":
2442         orig_quote = "'''"
2443         new_quote = '"""'
2444     elif value[0] == '"':
2445         orig_quote = '"'
2446         new_quote = "'"
2447     else:
2448         orig_quote = "'"
2449         new_quote = '"'
2450     first_quote_pos = leaf.value.find(orig_quote)
2451     if first_quote_pos == -1:
2452         return  # There's an internal error
2453
2454     prefix = leaf.value[:first_quote_pos]
2455     unescaped_new_quote = re.compile(rf"(([^\\]|^)(\\\\)*){new_quote}")
2456     escaped_new_quote = re.compile(rf"([^\\]|^)\\(\\\\)*{new_quote}")
2457     escaped_orig_quote = re.compile(rf"([^\\]|^)\\(\\\\)*{orig_quote}")
2458     body = leaf.value[first_quote_pos + len(orig_quote) : -len(orig_quote)]
2459     if "r" in prefix.casefold():
2460         if unescaped_new_quote.search(body):
2461             # There's at least one unescaped new_quote in this raw string
2462             # so converting is impossible
2463             return
2464
2465         # Do not introduce or remove backslashes in raw strings
2466         new_body = body
2467     else:
2468         # remove unnecessary quotes
2469         new_body = sub_twice(escaped_new_quote, rf"\1\2{new_quote}", body)
2470         if body != new_body:
2471             # Consider the string without unnecessary quotes as the original
2472             body = new_body
2473             leaf.value = f"{prefix}{orig_quote}{body}{orig_quote}"
2474         new_body = sub_twice(escaped_orig_quote, rf"\1\2{orig_quote}", new_body)
2475         new_body = sub_twice(unescaped_new_quote, rf"\1\\{new_quote}", new_body)
2476     if new_quote == '"""' and new_body[-1] == '"':
2477         # edge case:
2478         new_body = new_body[:-1] + '\\"'
2479     orig_escape_count = body.count("\\")
2480     new_escape_count = new_body.count("\\")
2481     if new_escape_count > orig_escape_count:
2482         return  # Do not introduce more escaping
2483
2484     if new_escape_count == orig_escape_count and orig_quote == '"':
2485         return  # Prefer double quotes
2486
2487     leaf.value = f"{prefix}{new_quote}{new_body}{new_quote}"
2488
2489
2490 def normalize_invisible_parens(node: Node, parens_after: Set[str]) -> None:
2491     """Make existing optional parentheses invisible or create new ones.
2492
2493     `parens_after` is a set of string leaf values immeditely after which parens
2494     should be put.
2495
2496     Standardizes on visible parentheses for single-element tuples, and keeps
2497     existing visible parentheses for other tuples and generator expressions.
2498     """
2499     try:
2500         list(generate_comments(node))
2501     except FormatOff:
2502         return  # This `node` has a prefix with `# fmt: off`, don't mess with parens.
2503
2504     check_lpar = False
2505     for index, child in enumerate(list(node.children)):
2506         if check_lpar:
2507             if child.type == syms.atom:
2508                 maybe_make_parens_invisible_in_atom(child)
2509             elif is_one_tuple(child):
2510                 # wrap child in visible parentheses
2511                 lpar = Leaf(token.LPAR, "(")
2512                 rpar = Leaf(token.RPAR, ")")
2513                 child.remove()
2514                 node.insert_child(index, Node(syms.atom, [lpar, child, rpar]))
2515             elif node.type == syms.import_from:
2516                 # "import from" nodes store parentheses directly as part of
2517                 # the statement
2518                 if child.type == token.LPAR:
2519                     # make parentheses invisible
2520                     child.value = ""  # type: ignore
2521                     node.children[-1].value = ""  # type: ignore
2522                 elif child.type != token.STAR:
2523                     # insert invisible parentheses
2524                     node.insert_child(index, Leaf(token.LPAR, ""))
2525                     node.append_child(Leaf(token.RPAR, ""))
2526                 break
2527
2528             elif not (isinstance(child, Leaf) and is_multiline_string(child)):
2529                 # wrap child in invisible parentheses
2530                 lpar = Leaf(token.LPAR, "")
2531                 rpar = Leaf(token.RPAR, "")
2532                 index = child.remove() or 0
2533                 node.insert_child(index, Node(syms.atom, [lpar, child, rpar]))
2534
2535         check_lpar = isinstance(child, Leaf) and child.value in parens_after
2536
2537
2538 def maybe_make_parens_invisible_in_atom(node: LN) -> bool:
2539     """If it's safe, make the parens in the atom `node` invisible, recusively."""
2540     if (
2541         node.type != syms.atom
2542         or is_empty_tuple(node)
2543         or is_one_tuple(node)
2544         or is_yield(node)
2545         or max_delimiter_priority_in_atom(node) >= COMMA_PRIORITY
2546     ):
2547         return False
2548
2549     first = node.children[0]
2550     last = node.children[-1]
2551     if first.type == token.LPAR and last.type == token.RPAR:
2552         # make parentheses invisible
2553         first.value = ""  # type: ignore
2554         last.value = ""  # type: ignore
2555         if len(node.children) > 1:
2556             maybe_make_parens_invisible_in_atom(node.children[1])
2557         return True
2558
2559     return False
2560
2561
2562 def is_empty_tuple(node: LN) -> bool:
2563     """Return True if `node` holds an empty tuple."""
2564     return (
2565         node.type == syms.atom
2566         and len(node.children) == 2
2567         and node.children[0].type == token.LPAR
2568         and node.children[1].type == token.RPAR
2569     )
2570
2571
2572 def is_one_tuple(node: LN) -> bool:
2573     """Return True if `node` holds a tuple with one element, with or without parens."""
2574     if node.type == syms.atom:
2575         if len(node.children) != 3:
2576             return False
2577
2578         lpar, gexp, rpar = node.children
2579         if not (
2580             lpar.type == token.LPAR
2581             and gexp.type == syms.testlist_gexp
2582             and rpar.type == token.RPAR
2583         ):
2584             return False
2585
2586         return len(gexp.children) == 2 and gexp.children[1].type == token.COMMA
2587
2588     return (
2589         node.type in IMPLICIT_TUPLE
2590         and len(node.children) == 2
2591         and node.children[1].type == token.COMMA
2592     )
2593
2594
2595 def is_yield(node: LN) -> bool:
2596     """Return True if `node` holds a `yield` or `yield from` expression."""
2597     if node.type == syms.yield_expr:
2598         return True
2599
2600     if node.type == token.NAME and node.value == "yield":  # type: ignore
2601         return True
2602
2603     if node.type != syms.atom:
2604         return False
2605
2606     if len(node.children) != 3:
2607         return False
2608
2609     lpar, expr, rpar = node.children
2610     if lpar.type == token.LPAR and rpar.type == token.RPAR:
2611         return is_yield(expr)
2612
2613     return False
2614
2615
2616 def is_vararg(leaf: Leaf, within: Set[NodeType]) -> bool:
2617     """Return True if `leaf` is a star or double star in a vararg or kwarg.
2618
2619     If `within` includes VARARGS_PARENTS, this applies to function signatures.
2620     If `within` includes UNPACKING_PARENTS, it applies to right hand-side
2621     extended iterable unpacking (PEP 3132) and additional unpacking
2622     generalizations (PEP 448).
2623     """
2624     if leaf.type not in STARS or not leaf.parent:
2625         return False
2626
2627     p = leaf.parent
2628     if p.type == syms.star_expr:
2629         # Star expressions are also used as assignment targets in extended
2630         # iterable unpacking (PEP 3132).  See what its parent is instead.
2631         if not p.parent:
2632             return False
2633
2634         p = p.parent
2635
2636     return p.type in within
2637
2638
2639 def is_multiline_string(leaf: Leaf) -> bool:
2640     """Return True if `leaf` is a multiline string that actually spans many lines."""
2641     value = leaf.value.lstrip("furbFURB")
2642     return value[:3] in {'"""', "'''"} and "\n" in value
2643
2644
2645 def is_stub_suite(node: Node) -> bool:
2646     """Return True if `node` is a suite with a stub body."""
2647     if (
2648         len(node.children) != 4
2649         or node.children[0].type != token.NEWLINE
2650         or node.children[1].type != token.INDENT
2651         or node.children[3].type != token.DEDENT
2652     ):
2653         return False
2654
2655     return is_stub_body(node.children[2])
2656
2657
2658 def is_stub_body(node: LN) -> bool:
2659     """Return True if `node` is a simple statement containing an ellipsis."""
2660     if not isinstance(node, Node) or node.type != syms.simple_stmt:
2661         return False
2662
2663     if len(node.children) != 2:
2664         return False
2665
2666     child = node.children[0]
2667     return (
2668         child.type == syms.atom
2669         and len(child.children) == 3
2670         and all(leaf == Leaf(token.DOT, ".") for leaf in child.children)
2671     )
2672
2673
2674 def max_delimiter_priority_in_atom(node: LN) -> int:
2675     """Return maximum delimiter priority inside `node`.
2676
2677     This is specific to atoms with contents contained in a pair of parentheses.
2678     If `node` isn't an atom or there are no enclosing parentheses, returns 0.
2679     """
2680     if node.type != syms.atom:
2681         return 0
2682
2683     first = node.children[0]
2684     last = node.children[-1]
2685     if not (first.type == token.LPAR and last.type == token.RPAR):
2686         return 0
2687
2688     bt = BracketTracker()
2689     for c in node.children[1:-1]:
2690         if isinstance(c, Leaf):
2691             bt.mark(c)
2692         else:
2693             for leaf in c.leaves():
2694                 bt.mark(leaf)
2695     try:
2696         return bt.max_delimiter_priority()
2697
2698     except ValueError:
2699         return 0
2700
2701
2702 def ensure_visible(leaf: Leaf) -> None:
2703     """Make sure parentheses are visible.
2704
2705     They could be invisible as part of some statements (see
2706     :func:`normalize_invible_parens` and :func:`visit_import_from`).
2707     """
2708     if leaf.type == token.LPAR:
2709         leaf.value = "("
2710     elif leaf.type == token.RPAR:
2711         leaf.value = ")"
2712
2713
2714 def should_explode(line: Line, opening_bracket: Leaf) -> bool:
2715     """Should `line` immediately be split with `delimiter_split()` after RHS?"""
2716     if not (
2717         opening_bracket.parent
2718         and opening_bracket.parent.type in {syms.atom, syms.import_from}
2719         and opening_bracket.value in "[{("
2720     ):
2721         return False
2722
2723     try:
2724         last_leaf = line.leaves[-1]
2725         exclude = {id(last_leaf)} if last_leaf.type == token.COMMA else set()
2726         max_priority = line.bracket_tracker.max_delimiter_priority(exclude=exclude)
2727     except (IndexError, ValueError):
2728         return False
2729
2730     return max_priority == COMMA_PRIORITY
2731
2732
2733 def is_python36(node: Node) -> bool:
2734     """Return True if the current file is using Python 3.6+ features.
2735
2736     Currently looking for:
2737     - f-strings; and
2738     - trailing commas after * or ** in function signatures and calls.
2739     """
2740     for n in node.pre_order():
2741         if n.type == token.STRING:
2742             value_head = n.value[:2]  # type: ignore
2743             if value_head in {'f"', 'F"', "f'", "F'", "rf", "fr", "RF", "FR"}:
2744                 return True
2745
2746         elif (
2747             n.type in {syms.typedargslist, syms.arglist}
2748             and n.children
2749             and n.children[-1].type == token.COMMA
2750         ):
2751             for ch in n.children:
2752                 if ch.type in STARS:
2753                     return True
2754
2755                 if ch.type == syms.argument:
2756                     for argch in ch.children:
2757                         if argch.type in STARS:
2758                             return True
2759
2760     return False
2761
2762
2763 def generate_trailers_to_omit(line: Line, line_length: int) -> Iterator[Set[LeafID]]:
2764     """Generate sets of closing bracket IDs that should be omitted in a RHS.
2765
2766     Brackets can be omitted if the entire trailer up to and including
2767     a preceding closing bracket fits in one line.
2768
2769     Yielded sets are cumulative (contain results of previous yields, too).  First
2770     set is empty.
2771     """
2772
2773     omit: Set[LeafID] = set()
2774     yield omit
2775
2776     length = 4 * line.depth
2777     opening_bracket = None
2778     closing_bracket = None
2779     optional_brackets: Set[LeafID] = set()
2780     inner_brackets: Set[LeafID] = set()
2781     for index, leaf, leaf_length in enumerate_with_length(line, reversed=True):
2782         length += leaf_length
2783         if length > line_length:
2784             break
2785
2786         has_inline_comment = leaf_length > len(leaf.value) + len(leaf.prefix)
2787         if leaf.type == STANDALONE_COMMENT or has_inline_comment:
2788             break
2789
2790         optional_brackets.discard(id(leaf))
2791         if opening_bracket:
2792             if leaf is opening_bracket:
2793                 opening_bracket = None
2794             elif leaf.type in CLOSING_BRACKETS:
2795                 inner_brackets.add(id(leaf))
2796         elif leaf.type in CLOSING_BRACKETS:
2797             if not leaf.value:
2798                 optional_brackets.add(id(opening_bracket))
2799                 continue
2800
2801             if index > 0 and line.leaves[index - 1].type in OPENING_BRACKETS:
2802                 # Empty brackets would fail a split so treat them as "inner"
2803                 # brackets (e.g. only add them to the `omit` set if another
2804                 # pair of brackets was good enough.
2805                 inner_brackets.add(id(leaf))
2806                 continue
2807
2808             opening_bracket = leaf.opening_bracket
2809             if closing_bracket:
2810                 omit.add(id(closing_bracket))
2811                 omit.update(inner_brackets)
2812                 inner_brackets.clear()
2813                 yield omit
2814             closing_bracket = leaf
2815
2816
2817 def get_future_imports(node: Node) -> Set[str]:
2818     """Return a set of __future__ imports in the file."""
2819     imports = set()
2820     for child in node.children:
2821         if child.type != syms.simple_stmt:
2822             break
2823         first_child = child.children[0]
2824         if isinstance(first_child, Leaf):
2825             # Continue looking if we see a docstring; otherwise stop.
2826             if (
2827                 len(child.children) == 2
2828                 and first_child.type == token.STRING
2829                 and child.children[1].type == token.NEWLINE
2830             ):
2831                 continue
2832             else:
2833                 break
2834         elif first_child.type == syms.import_from:
2835             module_name = first_child.children[1]
2836             if not isinstance(module_name, Leaf) or module_name.value != "__future__":
2837                 break
2838             for import_from_child in first_child.children[3:]:
2839                 if isinstance(import_from_child, Leaf):
2840                     if import_from_child.type == token.NAME:
2841                         imports.add(import_from_child.value)
2842                 else:
2843                     assert import_from_child.type == syms.import_as_names
2844                     for leaf in import_from_child.children:
2845                         if isinstance(leaf, Leaf) and leaf.type == token.NAME:
2846                             imports.add(leaf.value)
2847         else:
2848             break
2849     return imports
2850
2851
2852 def gen_python_files_in_dir(
2853     path: Path,
2854     root: Path,
2855     include: Pattern[str],
2856     exclude: Pattern[str],
2857     report: "Report",
2858 ) -> Iterator[Path]:
2859     """Generate all files under `path` whose paths are not excluded by the
2860     `exclude` regex, but are included by the `include` regex.
2861
2862     `report` is where output about exclusions goes.
2863     """
2864     assert root.is_absolute(), f"INTERNAL ERROR: `root` must be absolute but is {root}"
2865     for child in path.iterdir():
2866         normalized_path = "/" + child.resolve().relative_to(root).as_posix()
2867         if child.is_dir():
2868             normalized_path += "/"
2869         exclude_match = exclude.search(normalized_path)
2870         if exclude_match and exclude_match.group(0):
2871             report.path_ignored(child, f"matches --exclude={exclude.pattern}")
2872             continue
2873
2874         if child.is_dir():
2875             yield from gen_python_files_in_dir(child, root, include, exclude, report)
2876
2877         elif child.is_file():
2878             include_match = include.search(normalized_path)
2879             if include_match:
2880                 yield child
2881
2882
2883 def find_project_root(srcs: List[str]) -> Path:
2884     """Return a directory containing .git, .hg, or pyproject.toml.
2885
2886     That directory can be one of the directories passed in `srcs` or their
2887     common parent.
2888
2889     If no directory in the tree contains a marker that would specify it's the
2890     project root, the root of the file system is returned.
2891     """
2892     if not srcs:
2893         return Path("/").resolve()
2894
2895     common_base = min(Path(src).resolve() for src in srcs)
2896     if common_base.is_dir():
2897         # Append a fake file so `parents` below returns `common_base_dir`, too.
2898         common_base /= "fake-file"
2899     for directory in common_base.parents:
2900         if (directory / ".git").is_dir():
2901             return directory
2902
2903         if (directory / ".hg").is_dir():
2904             return directory
2905
2906         if (directory / "pyproject.toml").is_file():
2907             return directory
2908
2909     return directory
2910
2911
2912 @dataclass
2913 class Report:
2914     """Provides a reformatting counter. Can be rendered with `str(report)`."""
2915
2916     check: bool = False
2917     quiet: bool = False
2918     verbose: bool = False
2919     change_count: int = 0
2920     same_count: int = 0
2921     failure_count: int = 0
2922
2923     def done(self, src: Path, changed: Changed) -> None:
2924         """Increment the counter for successful reformatting. Write out a message."""
2925         if changed is Changed.YES:
2926             reformatted = "would reformat" if self.check else "reformatted"
2927             if self.verbose or not self.quiet:
2928                 out(f"{reformatted} {src}")
2929             self.change_count += 1
2930         else:
2931             if self.verbose:
2932                 if changed is Changed.NO:
2933                     msg = f"{src} already well formatted, good job."
2934                 else:
2935                     msg = f"{src} wasn't modified on disk since last run."
2936                 out(msg, bold=False)
2937             self.same_count += 1
2938
2939     def failed(self, src: Path, message: str) -> None:
2940         """Increment the counter for failed reformatting. Write out a message."""
2941         err(f"error: cannot format {src}: {message}")
2942         self.failure_count += 1
2943
2944     def path_ignored(self, path: Path, message: str) -> None:
2945         if self.verbose:
2946             out(f"{path} ignored: {message}", bold=False)
2947
2948     @property
2949     def return_code(self) -> int:
2950         """Return the exit code that the app should use.
2951
2952         This considers the current state of changed files and failures:
2953         - if there were any failures, return 123;
2954         - if any files were changed and --check is being used, return 1;
2955         - otherwise return 0.
2956         """
2957         # According to http://tldp.org/LDP/abs/html/exitcodes.html starting with
2958         # 126 we have special returncodes reserved by the shell.
2959         if self.failure_count:
2960             return 123
2961
2962         elif self.change_count and self.check:
2963             return 1
2964
2965         return 0
2966
2967     def __str__(self) -> str:
2968         """Render a color report of the current state.
2969
2970         Use `click.unstyle` to remove colors.
2971         """
2972         if self.check:
2973             reformatted = "would be reformatted"
2974             unchanged = "would be left unchanged"
2975             failed = "would fail to reformat"
2976         else:
2977             reformatted = "reformatted"
2978             unchanged = "left unchanged"
2979             failed = "failed to reformat"
2980         report = []
2981         if self.change_count:
2982             s = "s" if self.change_count > 1 else ""
2983             report.append(
2984                 click.style(f"{self.change_count} file{s} {reformatted}", bold=True)
2985             )
2986         if self.same_count:
2987             s = "s" if self.same_count > 1 else ""
2988             report.append(f"{self.same_count} file{s} {unchanged}")
2989         if self.failure_count:
2990             s = "s" if self.failure_count > 1 else ""
2991             report.append(
2992                 click.style(f"{self.failure_count} file{s} {failed}", fg="red")
2993             )
2994         return ", ".join(report) + "."
2995
2996
2997 def assert_equivalent(src: str, dst: str) -> None:
2998     """Raise AssertionError if `src` and `dst` aren't equivalent."""
2999
3000     import ast
3001     import traceback
3002
3003     def _v(node: ast.AST, depth: int = 0) -> Iterator[str]:
3004         """Simple visitor generating strings to compare ASTs by content."""
3005         yield f"{'  ' * depth}{node.__class__.__name__}("
3006
3007         for field in sorted(node._fields):
3008             try:
3009                 value = getattr(node, field)
3010             except AttributeError:
3011                 continue
3012
3013             yield f"{'  ' * (depth+1)}{field}="
3014
3015             if isinstance(value, list):
3016                 for item in value:
3017                     if isinstance(item, ast.AST):
3018                         yield from _v(item, depth + 2)
3019
3020             elif isinstance(value, ast.AST):
3021                 yield from _v(value, depth + 2)
3022
3023             else:
3024                 yield f"{'  ' * (depth+2)}{value!r},  # {value.__class__.__name__}"
3025
3026         yield f"{'  ' * depth})  # /{node.__class__.__name__}"
3027
3028     try:
3029         src_ast = ast.parse(src)
3030     except Exception as exc:
3031         major, minor = sys.version_info[:2]
3032         raise AssertionError(
3033             f"cannot use --safe with this file; failed to parse source file "
3034             f"with Python {major}.{minor}'s builtin AST. Re-run with --fast "
3035             f"or stop using deprecated Python 2 syntax. AST error message: {exc}"
3036         )
3037
3038     try:
3039         dst_ast = ast.parse(dst)
3040     except Exception as exc:
3041         log = dump_to_file("".join(traceback.format_tb(exc.__traceback__)), dst)
3042         raise AssertionError(
3043             f"INTERNAL ERROR: Black produced invalid code: {exc}. "
3044             f"Please report a bug on https://github.com/ambv/black/issues.  "
3045             f"This invalid output might be helpful: {log}"
3046         ) from None
3047
3048     src_ast_str = "\n".join(_v(src_ast))
3049     dst_ast_str = "\n".join(_v(dst_ast))
3050     if src_ast_str != dst_ast_str:
3051         log = dump_to_file(diff(src_ast_str, dst_ast_str, "src", "dst"))
3052         raise AssertionError(
3053             f"INTERNAL ERROR: Black produced code that is not equivalent to "
3054             f"the source.  "
3055             f"Please report a bug on https://github.com/ambv/black/issues.  "
3056             f"This diff might be helpful: {log}"
3057         ) from None
3058
3059
3060 def assert_stable(
3061     src: str, dst: str, line_length: int, mode: FileMode = FileMode.AUTO_DETECT
3062 ) -> None:
3063     """Raise AssertionError if `dst` reformats differently the second time."""
3064     newdst = format_str(dst, line_length=line_length, mode=mode)
3065     if dst != newdst:
3066         log = dump_to_file(
3067             diff(src, dst, "source", "first pass"),
3068             diff(dst, newdst, "first pass", "second pass"),
3069         )
3070         raise AssertionError(
3071             f"INTERNAL ERROR: Black produced different code on the second pass "
3072             f"of the formatter.  "
3073             f"Please report a bug on https://github.com/ambv/black/issues.  "
3074             f"This diff might be helpful: {log}"
3075         ) from None
3076
3077
3078 def dump_to_file(*output: str) -> str:
3079     """Dump `output` to a temporary file. Return path to the file."""
3080     import tempfile
3081
3082     with tempfile.NamedTemporaryFile(
3083         mode="w", prefix="blk_", suffix=".log", delete=False, encoding="utf8"
3084     ) as f:
3085         for lines in output:
3086             f.write(lines)
3087             if lines and lines[-1] != "\n":
3088                 f.write("\n")
3089     return f.name
3090
3091
3092 def diff(a: str, b: str, a_name: str, b_name: str) -> str:
3093     """Return a unified diff string between strings `a` and `b`."""
3094     import difflib
3095
3096     a_lines = [line + "\n" for line in a.split("\n")]
3097     b_lines = [line + "\n" for line in b.split("\n")]
3098     return "".join(
3099         difflib.unified_diff(a_lines, b_lines, fromfile=a_name, tofile=b_name, n=5)
3100     )
3101
3102
3103 def cancel(tasks: Iterable[asyncio.Task]) -> None:
3104     """asyncio signal handler that cancels all `tasks` and reports to stderr."""
3105     err("Aborted!")
3106     for task in tasks:
3107         task.cancel()
3108
3109
3110 def shutdown(loop: BaseEventLoop) -> None:
3111     """Cancel all pending tasks on `loop`, wait for them, and close the loop."""
3112     try:
3113         # This part is borrowed from asyncio/runners.py in Python 3.7b2.
3114         to_cancel = [task for task in asyncio.Task.all_tasks(loop) if not task.done()]
3115         if not to_cancel:
3116             return
3117
3118         for task in to_cancel:
3119             task.cancel()
3120         loop.run_until_complete(
3121             asyncio.gather(*to_cancel, loop=loop, return_exceptions=True)
3122         )
3123     finally:
3124         # `concurrent.futures.Future` objects cannot be cancelled once they
3125         # are already running. There might be some when the `shutdown()` happened.
3126         # Silence their logger's spew about the event loop being closed.
3127         cf_logger = logging.getLogger("concurrent.futures")
3128         cf_logger.setLevel(logging.CRITICAL)
3129         loop.close()
3130
3131
3132 def sub_twice(regex: Pattern[str], replacement: str, original: str) -> str:
3133     """Replace `regex` with `replacement` twice on `original`.
3134
3135     This is used by string normalization to perform replaces on
3136     overlapping matches.
3137     """
3138     return regex.sub(replacement, regex.sub(replacement, original))
3139
3140
3141 def enumerate_reversed(sequence: Sequence[T]) -> Iterator[Tuple[Index, T]]:
3142     """Like `reversed(enumerate(sequence))` if that were possible."""
3143     index = len(sequence) - 1
3144     for element in reversed(sequence):
3145         yield (index, element)
3146         index -= 1
3147
3148
3149 def enumerate_with_length(
3150     line: Line, reversed: bool = False
3151 ) -> Iterator[Tuple[Index, Leaf, int]]:
3152     """Return an enumeration of leaves with their length.
3153
3154     Stops prematurely on multiline strings and standalone comments.
3155     """
3156     op = cast(
3157         Callable[[Sequence[Leaf]], Iterator[Tuple[Index, Leaf]]],
3158         enumerate_reversed if reversed else enumerate,
3159     )
3160     for index, leaf in op(line.leaves):
3161         length = len(leaf.prefix) + len(leaf.value)
3162         if "\n" in leaf.value:
3163             return  # Multiline strings, we can't continue.
3164
3165         comment: Optional[Leaf]
3166         for comment in line.comments_after(leaf, index):
3167             length += len(comment.value)
3168
3169         yield index, leaf, length
3170
3171
3172 def is_line_short_enough(line: Line, *, line_length: int, line_str: str = "") -> bool:
3173     """Return True if `line` is no longer than `line_length`.
3174
3175     Uses the provided `line_str` rendering, if any, otherwise computes a new one.
3176     """
3177     if not line_str:
3178         line_str = str(line).strip("\n")
3179     return (
3180         len(line_str) <= line_length
3181         and "\n" not in line_str  # multiline strings
3182         and not line.contains_standalone_comments()
3183     )
3184
3185
3186 def can_omit_invisible_parens(line: Line, line_length: int) -> bool:
3187     """Does `line` have a shape safe to reformat without optional parens around it?
3188
3189     Returns True for only a subset of potentially nice looking formattings but
3190     the point is to not return false positives that end up producing lines that
3191     are too long.
3192     """
3193     bt = line.bracket_tracker
3194     if not bt.delimiters:
3195         # Without delimiters the optional parentheses are useless.
3196         return True
3197
3198     max_priority = bt.max_delimiter_priority()
3199     if bt.delimiter_count_with_priority(max_priority) > 1:
3200         # With more than one delimiter of a kind the optional parentheses read better.
3201         return False
3202
3203     if max_priority == DOT_PRIORITY:
3204         # A single stranded method call doesn't require optional parentheses.
3205         return True
3206
3207     assert len(line.leaves) >= 2, "Stranded delimiter"
3208
3209     first = line.leaves[0]
3210     second = line.leaves[1]
3211     penultimate = line.leaves[-2]
3212     last = line.leaves[-1]
3213
3214     # With a single delimiter, omit if the expression starts or ends with
3215     # a bracket.
3216     if first.type in OPENING_BRACKETS and second.type not in CLOSING_BRACKETS:
3217         remainder = False
3218         length = 4 * line.depth
3219         for _index, leaf, leaf_length in enumerate_with_length(line):
3220             if leaf.type in CLOSING_BRACKETS and leaf.opening_bracket is first:
3221                 remainder = True
3222             if remainder:
3223                 length += leaf_length
3224                 if length > line_length:
3225                     break
3226
3227                 if leaf.type in OPENING_BRACKETS:
3228                     # There are brackets we can further split on.
3229                     remainder = False
3230
3231         else:
3232             # checked the entire string and line length wasn't exceeded
3233             if len(line.leaves) == _index + 1:
3234                 return True
3235
3236         # Note: we are not returning False here because a line might have *both*
3237         # a leading opening bracket and a trailing closing bracket.  If the
3238         # opening bracket doesn't match our rule, maybe the closing will.
3239
3240     if (
3241         last.type == token.RPAR
3242         or last.type == token.RBRACE
3243         or (
3244             # don't use indexing for omitting optional parentheses;
3245             # it looks weird
3246             last.type == token.RSQB
3247             and last.parent
3248             and last.parent.type != syms.trailer
3249         )
3250     ):
3251         if penultimate.type in OPENING_BRACKETS:
3252             # Empty brackets don't help.
3253             return False
3254
3255         if is_multiline_string(first):
3256             # Additional wrapping of a multiline string in this situation is
3257             # unnecessary.
3258             return True
3259
3260         length = 4 * line.depth
3261         seen_other_brackets = False
3262         for _index, leaf, leaf_length in enumerate_with_length(line):
3263             length += leaf_length
3264             if leaf is last.opening_bracket:
3265                 if seen_other_brackets or length <= line_length:
3266                     return True
3267
3268             elif leaf.type in OPENING_BRACKETS:
3269                 # There are brackets we can further split on.
3270                 seen_other_brackets = True
3271
3272     return False
3273
3274
3275 def get_cache_file(line_length: int, mode: FileMode) -> Path:
3276     pyi = bool(mode & FileMode.PYI)
3277     py36 = bool(mode & FileMode.PYTHON36)
3278     return (
3279         CACHE_DIR
3280         / f"cache.{line_length}{'.pyi' if pyi else ''}{'.py36' if py36 else ''}.pickle"
3281     )
3282
3283
3284 def read_cache(line_length: int, mode: FileMode) -> Cache:
3285     """Read the cache if it exists and is well formed.
3286
3287     If it is not well formed, the call to write_cache later should resolve the issue.
3288     """
3289     cache_file = get_cache_file(line_length, mode)
3290     if not cache_file.exists():
3291         return {}
3292
3293     with cache_file.open("rb") as fobj:
3294         try:
3295             cache: Cache = pickle.load(fobj)
3296         except pickle.UnpicklingError:
3297             return {}
3298
3299     return cache
3300
3301
3302 def get_cache_info(path: Path) -> CacheInfo:
3303     """Return the information used to check if a file is already formatted or not."""
3304     stat = path.stat()
3305     return stat.st_mtime, stat.st_size
3306
3307
3308 def filter_cached(cache: Cache, sources: Iterable[Path]) -> Tuple[Set[Path], Set[Path]]:
3309     """Split an iterable of paths in `sources` into two sets.
3310
3311     The first contains paths of files that modified on disk or are not in the
3312     cache. The other contains paths to non-modified files.
3313     """
3314     todo, done = set(), set()
3315     for src in sources:
3316         src = src.resolve()
3317         if cache.get(src) != get_cache_info(src):
3318             todo.add(src)
3319         else:
3320             done.add(src)
3321     return todo, done
3322
3323
3324 def write_cache(
3325     cache: Cache, sources: Iterable[Path], line_length: int, mode: FileMode
3326 ) -> None:
3327     """Update the cache file."""
3328     cache_file = get_cache_file(line_length, mode)
3329     try:
3330         if not CACHE_DIR.exists():
3331             CACHE_DIR.mkdir(parents=True)
3332         new_cache = {**cache, **{src.resolve(): get_cache_info(src) for src in sources}}
3333         with cache_file.open("wb") as fobj:
3334             pickle.dump(new_cache, fobj, protocol=pickle.HIGHEST_PROTOCOL)
3335     except OSError:
3336         pass
3337
3338
3339 if __name__ == "__main__":
3340     main()