]> git.madduck.net Git - etc/vim.git/blob - src/black/trans.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:

Add IntelliJ docs on external tools and file watcher (#3365)
[etc/vim.git] / src / black / trans.py
1 """
2 String transformers that can split and merge strings.
3 """
4 import re
5 import sys
6 from abc import ABC, abstractmethod
7 from collections import defaultdict
8 from dataclasses import dataclass
9 from typing import (
10     Any,
11     Callable,
12     ClassVar,
13     Collection,
14     Dict,
15     Iterable,
16     Iterator,
17     List,
18     Optional,
19     Sequence,
20     Set,
21     Tuple,
22     TypeVar,
23     Union,
24 )
25
26 if sys.version_info < (3, 8):
27     from typing_extensions import Final, Literal
28 else:
29     from typing import Literal, Final
30
31 from mypy_extensions import trait
32
33 from black.comments import contains_pragma_comment
34 from black.lines import Line, append_leaves
35 from black.mode import Feature
36 from black.nodes import (
37     CLOSING_BRACKETS,
38     OPENING_BRACKETS,
39     STANDALONE_COMMENT,
40     is_empty_lpar,
41     is_empty_par,
42     is_empty_rpar,
43     is_part_of_annotation,
44     parent_type,
45     replace_child,
46     syms,
47 )
48 from black.rusty import Err, Ok, Result
49 from black.strings import (
50     assert_is_leaf_string,
51     get_string_prefix,
52     has_triple_quotes,
53     normalize_string_quotes,
54 )
55 from blib2to3.pgen2 import token
56 from blib2to3.pytree import Leaf, Node
57
58
59 class CannotTransform(Exception):
60     """Base class for errors raised by Transformers."""
61
62
63 # types
64 T = TypeVar("T")
65 LN = Union[Leaf, Node]
66 Transformer = Callable[[Line, Collection[Feature]], Iterator[Line]]
67 Index = int
68 NodeType = int
69 ParserState = int
70 StringID = int
71 TResult = Result[T, CannotTransform]  # (T)ransform Result
72 TMatchResult = TResult[List[Index]]
73
74
75 def TErr(err_msg: str) -> Err[CannotTransform]:
76     """(T)ransform Err
77
78     Convenience function used when working with the TResult type.
79     """
80     cant_transform = CannotTransform(err_msg)
81     return Err(cant_transform)
82
83
84 def hug_power_op(line: Line, features: Collection[Feature]) -> Iterator[Line]:
85     """A transformer which normalizes spacing around power operators."""
86
87     # Performance optimization to avoid unnecessary Leaf clones and other ops.
88     for leaf in line.leaves:
89         if leaf.type == token.DOUBLESTAR:
90             break
91     else:
92         raise CannotTransform("No doublestar token was found in the line.")
93
94     def is_simple_lookup(index: int, step: Literal[1, -1]) -> bool:
95         # Brackets and parentheses indicate calls, subscripts, etc. ...
96         # basically stuff that doesn't count as "simple". Only a NAME lookup
97         # or dotted lookup (eg. NAME.NAME) is OK.
98         if step == -1:
99             disallowed = {token.RPAR, token.RSQB}
100         else:
101             disallowed = {token.LPAR, token.LSQB}
102
103         while 0 <= index < len(line.leaves):
104             current = line.leaves[index]
105             if current.type in disallowed:
106                 return False
107             if current.type not in {token.NAME, token.DOT} or current.value == "for":
108                 # If the current token isn't disallowed, we'll assume this is simple as
109                 # only the disallowed tokens are semantically attached to this lookup
110                 # expression we're checking. Also, stop early if we hit the 'for' bit
111                 # of a comprehension.
112                 return True
113
114             index += step
115
116         return True
117
118     def is_simple_operand(index: int, kind: Literal["base", "exponent"]) -> bool:
119         # An operand is considered "simple" if's a NAME, a numeric CONSTANT, a simple
120         # lookup (see above), with or without a preceding unary operator.
121         start = line.leaves[index]
122         if start.type in {token.NAME, token.NUMBER}:
123             return is_simple_lookup(index, step=(1 if kind == "exponent" else -1))
124
125         if start.type in {token.PLUS, token.MINUS, token.TILDE}:
126             if line.leaves[index + 1].type in {token.NAME, token.NUMBER}:
127                 # step is always one as bases with a preceding unary op will be checked
128                 # for simplicity starting from the next token (so it'll hit the check
129                 # above).
130                 return is_simple_lookup(index + 1, step=1)
131
132         return False
133
134     new_line = line.clone()
135     should_hug = False
136     for idx, leaf in enumerate(line.leaves):
137         new_leaf = leaf.clone()
138         if should_hug:
139             new_leaf.prefix = ""
140             should_hug = False
141
142         should_hug = (
143             (0 < idx < len(line.leaves) - 1)
144             and leaf.type == token.DOUBLESTAR
145             and is_simple_operand(idx - 1, kind="base")
146             and line.leaves[idx - 1].value != "lambda"
147             and is_simple_operand(idx + 1, kind="exponent")
148         )
149         if should_hug:
150             new_leaf.prefix = ""
151
152         # We have to be careful to make a new line properly:
153         # - bracket related metadata must be maintained (handled by Line.append)
154         # - comments need to copied over, updating the leaf IDs they're attached to
155         new_line.append(new_leaf, preformatted=True)
156         for comment_leaf in line.comments_after(leaf):
157             new_line.append(comment_leaf, preformatted=True)
158
159     yield new_line
160
161
162 class StringTransformer(ABC):
163     """
164     An implementation of the Transformer protocol that relies on its
165     subclasses overriding the template methods `do_match(...)` and
166     `do_transform(...)`.
167
168     This Transformer works exclusively on strings (for example, by merging
169     or splitting them).
170
171     The following sections can be found among the docstrings of each concrete
172     StringTransformer subclass.
173
174     Requirements:
175         Which requirements must be met of the given Line for this
176         StringTransformer to be applied?
177
178     Transformations:
179         If the given Line meets all of the above requirements, which string
180         transformations can you expect to be applied to it by this
181         StringTransformer?
182
183     Collaborations:
184         What contractual agreements does this StringTransformer have with other
185         StringTransfomers? Such collaborations should be eliminated/minimized
186         as much as possible.
187     """
188
189     __name__: Final = "StringTransformer"
190
191     # Ideally this would be a dataclass, but unfortunately mypyc breaks when used with
192     # `abc.ABC`.
193     def __init__(self, line_length: int, normalize_strings: bool) -> None:
194         self.line_length = line_length
195         self.normalize_strings = normalize_strings
196
197     @abstractmethod
198     def do_match(self, line: Line) -> TMatchResult:
199         """
200         Returns:
201             * Ok(string_indices) such that for each index, `line.leaves[index]`
202             is our target string if a match was able to be made. For
203             transformers that don't result in more lines (e.g. StringMerger,
204             StringParenStripper), multiple matches and transforms are done at
205             once to reduce the complexity.
206                 OR
207             * Err(CannotTransform), if no match could be made.
208         """
209
210     @abstractmethod
211     def do_transform(
212         self, line: Line, string_indices: List[int]
213     ) -> Iterator[TResult[Line]]:
214         """
215         Yields:
216             * Ok(new_line) where new_line is the new transformed line.
217                 OR
218             * Err(CannotTransform) if the transformation failed for some reason. The
219             `do_match(...)` template method should usually be used to reject
220             the form of the given Line, but in some cases it is difficult to
221             know whether or not a Line meets the StringTransformer's
222             requirements until the transformation is already midway.
223
224         Side Effects:
225             This method should NOT mutate @line directly, but it MAY mutate the
226             Line's underlying Node structure. (WARNING: If the underlying Node
227             structure IS altered, then this method should NOT be allowed to
228             yield an CannotTransform after that point.)
229         """
230
231     def __call__(self, line: Line, _features: Collection[Feature]) -> Iterator[Line]:
232         """
233         StringTransformer instances have a call signature that mirrors that of
234         the Transformer type.
235
236         Raises:
237             CannotTransform(...) if the concrete StringTransformer class is unable
238             to transform @line.
239         """
240         # Optimization to avoid calling `self.do_match(...)` when the line does
241         # not contain any string.
242         if not any(leaf.type == token.STRING for leaf in line.leaves):
243             raise CannotTransform("There are no strings in this line.")
244
245         match_result = self.do_match(line)
246
247         if isinstance(match_result, Err):
248             cant_transform = match_result.err()
249             raise CannotTransform(
250                 f"The string transformer {self.__class__.__name__} does not recognize"
251                 " this line as one that it can transform."
252             ) from cant_transform
253
254         string_indices = match_result.ok()
255
256         for line_result in self.do_transform(line, string_indices):
257             if isinstance(line_result, Err):
258                 cant_transform = line_result.err()
259                 raise CannotTransform(
260                     "StringTransformer failed while attempting to transform string."
261                 ) from cant_transform
262             line = line_result.ok()
263             yield line
264
265
266 @dataclass
267 class CustomSplit:
268     """A custom (i.e. manual) string split.
269
270     A single CustomSplit instance represents a single substring.
271
272     Examples:
273         Consider the following string:
274         ```
275         "Hi there friend."
276         " This is a custom"
277         f" string {split}."
278         ```
279
280         This string will correspond to the following three CustomSplit instances:
281         ```
282         CustomSplit(False, 16)
283         CustomSplit(False, 17)
284         CustomSplit(True, 16)
285         ```
286     """
287
288     has_prefix: bool
289     break_idx: int
290
291
292 @trait
293 class CustomSplitMapMixin:
294     """
295     This mixin class is used to map merged strings to a sequence of
296     CustomSplits, which will then be used to re-split the strings iff none of
297     the resultant substrings go over the configured max line length.
298     """
299
300     _Key: ClassVar = Tuple[StringID, str]
301     _CUSTOM_SPLIT_MAP: ClassVar[Dict[_Key, Tuple[CustomSplit, ...]]] = defaultdict(
302         tuple
303     )
304
305     @staticmethod
306     def _get_key(string: str) -> "CustomSplitMapMixin._Key":
307         """
308         Returns:
309             A unique identifier that is used internally to map @string to a
310             group of custom splits.
311         """
312         return (id(string), string)
313
314     def add_custom_splits(
315         self, string: str, custom_splits: Iterable[CustomSplit]
316     ) -> None:
317         """Custom Split Map Setter Method
318
319         Side Effects:
320             Adds a mapping from @string to the custom splits @custom_splits.
321         """
322         key = self._get_key(string)
323         self._CUSTOM_SPLIT_MAP[key] = tuple(custom_splits)
324
325     def pop_custom_splits(self, string: str) -> List[CustomSplit]:
326         """Custom Split Map Getter Method
327
328         Returns:
329             * A list of the custom splits that are mapped to @string, if any
330             exist.
331                 OR
332             * [], otherwise.
333
334         Side Effects:
335             Deletes the mapping between @string and its associated custom
336             splits (which are returned to the caller).
337         """
338         key = self._get_key(string)
339
340         custom_splits = self._CUSTOM_SPLIT_MAP[key]
341         del self._CUSTOM_SPLIT_MAP[key]
342
343         return list(custom_splits)
344
345     def has_custom_splits(self, string: str) -> bool:
346         """
347         Returns:
348             True iff @string is associated with a set of custom splits.
349         """
350         key = self._get_key(string)
351         return key in self._CUSTOM_SPLIT_MAP
352
353
354 class StringMerger(StringTransformer, CustomSplitMapMixin):
355     """StringTransformer that merges strings together.
356
357     Requirements:
358         (A) The line contains adjacent strings such that ALL of the validation checks
359         listed in StringMerger._validate_msg(...)'s docstring pass.
360             OR
361         (B) The line contains a string which uses line continuation backslashes.
362
363     Transformations:
364         Depending on which of the two requirements above where met, either:
365
366         (A) The string group associated with the target string is merged.
367             OR
368         (B) All line-continuation backslashes are removed from the target string.
369
370     Collaborations:
371         StringMerger provides custom split information to StringSplitter.
372     """
373
374     def do_match(self, line: Line) -> TMatchResult:
375         LL = line.leaves
376
377         is_valid_index = is_valid_index_factory(LL)
378
379         string_indices = []
380         idx = 0
381         while is_valid_index(idx):
382             leaf = LL[idx]
383             if (
384                 leaf.type == token.STRING
385                 and is_valid_index(idx + 1)
386                 and LL[idx + 1].type == token.STRING
387             ):
388                 if not is_part_of_annotation(leaf):
389                     string_indices.append(idx)
390
391                 # Advance to the next non-STRING leaf.
392                 idx += 2
393                 while is_valid_index(idx) and LL[idx].type == token.STRING:
394                     idx += 1
395
396             elif leaf.type == token.STRING and "\\\n" in leaf.value:
397                 string_indices.append(idx)
398                 # Advance to the next non-STRING leaf.
399                 idx += 1
400                 while is_valid_index(idx) and LL[idx].type == token.STRING:
401                     idx += 1
402
403             else:
404                 idx += 1
405
406         if string_indices:
407             return Ok(string_indices)
408         else:
409             return TErr("This line has no strings that need merging.")
410
411     def do_transform(
412         self, line: Line, string_indices: List[int]
413     ) -> Iterator[TResult[Line]]:
414         new_line = line
415
416         rblc_result = self._remove_backslash_line_continuation_chars(
417             new_line, string_indices
418         )
419         if isinstance(rblc_result, Ok):
420             new_line = rblc_result.ok()
421
422         msg_result = self._merge_string_group(new_line, string_indices)
423         if isinstance(msg_result, Ok):
424             new_line = msg_result.ok()
425
426         if isinstance(rblc_result, Err) and isinstance(msg_result, Err):
427             msg_cant_transform = msg_result.err()
428             rblc_cant_transform = rblc_result.err()
429             cant_transform = CannotTransform(
430                 "StringMerger failed to merge any strings in this line."
431             )
432
433             # Chain the errors together using `__cause__`.
434             msg_cant_transform.__cause__ = rblc_cant_transform
435             cant_transform.__cause__ = msg_cant_transform
436
437             yield Err(cant_transform)
438         else:
439             yield Ok(new_line)
440
441     @staticmethod
442     def _remove_backslash_line_continuation_chars(
443         line: Line, string_indices: List[int]
444     ) -> TResult[Line]:
445         """
446         Merge strings that were split across multiple lines using
447         line-continuation backslashes.
448
449         Returns:
450             Ok(new_line), if @line contains backslash line-continuation
451             characters.
452                 OR
453             Err(CannotTransform), otherwise.
454         """
455         LL = line.leaves
456
457         indices_to_transform = []
458         for string_idx in string_indices:
459             string_leaf = LL[string_idx]
460             if (
461                 string_leaf.type == token.STRING
462                 and "\\\n" in string_leaf.value
463                 and not has_triple_quotes(string_leaf.value)
464             ):
465                 indices_to_transform.append(string_idx)
466
467         if not indices_to_transform:
468             return TErr(
469                 "Found no string leaves that contain backslash line continuation"
470                 " characters."
471             )
472
473         new_line = line.clone()
474         new_line.comments = line.comments.copy()
475         append_leaves(new_line, line, LL)
476
477         for string_idx in indices_to_transform:
478             new_string_leaf = new_line.leaves[string_idx]
479             new_string_leaf.value = new_string_leaf.value.replace("\\\n", "")
480
481         return Ok(new_line)
482
483     def _merge_string_group(
484         self, line: Line, string_indices: List[int]
485     ) -> TResult[Line]:
486         """
487         Merges string groups (i.e. set of adjacent strings).
488
489         Each index from `string_indices` designates one string group's first
490         leaf in `line.leaves`.
491
492         Returns:
493             Ok(new_line), if ALL of the validation checks found in
494             _validate_msg(...) pass.
495                 OR
496             Err(CannotTransform), otherwise.
497         """
498         LL = line.leaves
499
500         is_valid_index = is_valid_index_factory(LL)
501
502         # A dict of {string_idx: tuple[num_of_strings, string_leaf]}.
503         merged_string_idx_dict: Dict[int, Tuple[int, Leaf]] = {}
504         for string_idx in string_indices:
505             vresult = self._validate_msg(line, string_idx)
506             if isinstance(vresult, Err):
507                 continue
508             merged_string_idx_dict[string_idx] = self._merge_one_string_group(
509                 LL, string_idx, is_valid_index
510             )
511
512         if not merged_string_idx_dict:
513             return TErr("No string group is merged")
514
515         # Build the final line ('new_line') that this method will later return.
516         new_line = line.clone()
517         previous_merged_string_idx = -1
518         previous_merged_num_of_strings = -1
519         for i, leaf in enumerate(LL):
520             if i in merged_string_idx_dict:
521                 previous_merged_string_idx = i
522                 previous_merged_num_of_strings, string_leaf = merged_string_idx_dict[i]
523                 new_line.append(string_leaf)
524
525             if (
526                 previous_merged_string_idx
527                 <= i
528                 < previous_merged_string_idx + previous_merged_num_of_strings
529             ):
530                 for comment_leaf in line.comments_after(LL[i]):
531                     new_line.append(comment_leaf, preformatted=True)
532                 continue
533
534             append_leaves(new_line, line, [leaf])
535
536         return Ok(new_line)
537
538     def _merge_one_string_group(
539         self, LL: List[Leaf], string_idx: int, is_valid_index: Callable[[int], bool]
540     ) -> Tuple[int, Leaf]:
541         """
542         Merges one string group where the first string in the group is
543         `LL[string_idx]`.
544
545         Returns:
546             A tuple of `(num_of_strings, leaf)` where `num_of_strings` is the
547             number of strings merged and `leaf` is the newly merged string
548             to be replaced in the new line.
549         """
550         # If the string group is wrapped inside an Atom node, we must make sure
551         # to later replace that Atom with our new (merged) string leaf.
552         atom_node = LL[string_idx].parent
553
554         # We will place BREAK_MARK in between every two substrings that we
555         # merge. We will then later go through our final result and use the
556         # various instances of BREAK_MARK we find to add the right values to
557         # the custom split map.
558         BREAK_MARK = "@@@@@ BLACK BREAKPOINT MARKER @@@@@"
559
560         QUOTE = LL[string_idx].value[-1]
561
562         def make_naked(string: str, string_prefix: str) -> str:
563             """Strip @string (i.e. make it a "naked" string)
564
565             Pre-conditions:
566                 * assert_is_leaf_string(@string)
567
568             Returns:
569                 A string that is identical to @string except that
570                 @string_prefix has been stripped, the surrounding QUOTE
571                 characters have been removed, and any remaining QUOTE
572                 characters have been escaped.
573             """
574             assert_is_leaf_string(string)
575
576             RE_EVEN_BACKSLASHES = r"(?:(?<!\\)(?:\\\\)*)"
577             naked_string = string[len(string_prefix) + 1 : -1]
578             naked_string = re.sub(
579                 "(" + RE_EVEN_BACKSLASHES + ")" + QUOTE, r"\1\\" + QUOTE, naked_string
580             )
581             return naked_string
582
583         # Holds the CustomSplit objects that will later be added to the custom
584         # split map.
585         custom_splits = []
586
587         # Temporary storage for the 'has_prefix' part of the CustomSplit objects.
588         prefix_tracker = []
589
590         # Sets the 'prefix' variable. This is the prefix that the final merged
591         # string will have.
592         next_str_idx = string_idx
593         prefix = ""
594         while (
595             not prefix
596             and is_valid_index(next_str_idx)
597             and LL[next_str_idx].type == token.STRING
598         ):
599             prefix = get_string_prefix(LL[next_str_idx].value).lower()
600             next_str_idx += 1
601
602         # The next loop merges the string group. The final string will be
603         # contained in 'S'.
604         #
605         # The following convenience variables are used:
606         #
607         #   S: string
608         #   NS: naked string
609         #   SS: next string
610         #   NSS: naked next string
611         S = ""
612         NS = ""
613         num_of_strings = 0
614         next_str_idx = string_idx
615         while is_valid_index(next_str_idx) and LL[next_str_idx].type == token.STRING:
616             num_of_strings += 1
617
618             SS = LL[next_str_idx].value
619             next_prefix = get_string_prefix(SS).lower()
620
621             # If this is an f-string group but this substring is not prefixed
622             # with 'f'...
623             if "f" in prefix and "f" not in next_prefix:
624                 # Then we must escape any braces contained in this substring.
625                 SS = re.sub(r"(\{|\})", r"\1\1", SS)
626
627             NSS = make_naked(SS, next_prefix)
628
629             has_prefix = bool(next_prefix)
630             prefix_tracker.append(has_prefix)
631
632             S = prefix + QUOTE + NS + NSS + BREAK_MARK + QUOTE
633             NS = make_naked(S, prefix)
634
635             next_str_idx += 1
636
637         # Take a note on the index of the non-STRING leaf.
638         non_string_idx = next_str_idx
639
640         S_leaf = Leaf(token.STRING, S)
641         if self.normalize_strings:
642             S_leaf.value = normalize_string_quotes(S_leaf.value)
643
644         # Fill the 'custom_splits' list with the appropriate CustomSplit objects.
645         temp_string = S_leaf.value[len(prefix) + 1 : -1]
646         for has_prefix in prefix_tracker:
647             mark_idx = temp_string.find(BREAK_MARK)
648             assert (
649                 mark_idx >= 0
650             ), "Logic error while filling the custom string breakpoint cache."
651
652             temp_string = temp_string[mark_idx + len(BREAK_MARK) :]
653             breakpoint_idx = mark_idx + (len(prefix) if has_prefix else 0) + 1
654             custom_splits.append(CustomSplit(has_prefix, breakpoint_idx))
655
656         string_leaf = Leaf(token.STRING, S_leaf.value.replace(BREAK_MARK, ""))
657
658         if atom_node is not None:
659             # If not all children of the atom node are merged (this can happen
660             # when there is a standalone comment in the middle) ...
661             if non_string_idx - string_idx < len(atom_node.children):
662                 # We need to replace the old STRING leaves with the new string leaf.
663                 first_child_idx = LL[string_idx].remove()
664                 for idx in range(string_idx + 1, non_string_idx):
665                     LL[idx].remove()
666                 if first_child_idx is not None:
667                     atom_node.insert_child(first_child_idx, string_leaf)
668             else:
669                 # Else replace the atom node with the new string leaf.
670                 replace_child(atom_node, string_leaf)
671
672         self.add_custom_splits(string_leaf.value, custom_splits)
673         return num_of_strings, string_leaf
674
675     @staticmethod
676     def _validate_msg(line: Line, string_idx: int) -> TResult[None]:
677         """Validate (M)erge (S)tring (G)roup
678
679         Transform-time string validation logic for _merge_string_group(...).
680
681         Returns:
682             * Ok(None), if ALL validation checks (listed below) pass.
683                 OR
684             * Err(CannotTransform), if any of the following are true:
685                 - The target string group does not contain ANY stand-alone comments.
686                 - The target string is not in a string group (i.e. it has no
687                   adjacent strings).
688                 - The string group has more than one inline comment.
689                 - The string group has an inline comment that appears to be a pragma.
690                 - The set of all string prefixes in the string group is of
691                   length greater than one and is not equal to {"", "f"}.
692                 - The string group consists of raw strings.
693                 - The string group is stringified type annotations. We don't want to
694                   process stringified type annotations since pyright doesn't support
695                   them spanning multiple string values. (NOTE: mypy, pytype, pyre do
696                   support them, so we can change if pyright also gains support in the
697                   future. See https://github.com/microsoft/pyright/issues/4359.)
698         """
699         # We first check for "inner" stand-alone comments (i.e. stand-alone
700         # comments that have a string leaf before them AND after them).
701         for inc in [1, -1]:
702             i = string_idx
703             found_sa_comment = False
704             is_valid_index = is_valid_index_factory(line.leaves)
705             while is_valid_index(i) and line.leaves[i].type in [
706                 token.STRING,
707                 STANDALONE_COMMENT,
708             ]:
709                 if line.leaves[i].type == STANDALONE_COMMENT:
710                     found_sa_comment = True
711                 elif found_sa_comment:
712                     return TErr(
713                         "StringMerger does NOT merge string groups which contain "
714                         "stand-alone comments."
715                     )
716
717                 i += inc
718
719         num_of_inline_string_comments = 0
720         set_of_prefixes = set()
721         num_of_strings = 0
722         for leaf in line.leaves[string_idx:]:
723             if leaf.type != token.STRING:
724                 # If the string group is trailed by a comma, we count the
725                 # comments trailing the comma to be one of the string group's
726                 # comments.
727                 if leaf.type == token.COMMA and id(leaf) in line.comments:
728                     num_of_inline_string_comments += 1
729                 break
730
731             if has_triple_quotes(leaf.value):
732                 return TErr("StringMerger does NOT merge multiline strings.")
733
734             num_of_strings += 1
735             prefix = get_string_prefix(leaf.value).lower()
736             if "r" in prefix:
737                 return TErr("StringMerger does NOT merge raw strings.")
738
739             set_of_prefixes.add(prefix)
740
741             if id(leaf) in line.comments:
742                 num_of_inline_string_comments += 1
743                 if contains_pragma_comment(line.comments[id(leaf)]):
744                     return TErr("Cannot merge strings which have pragma comments.")
745
746         if num_of_strings < 2:
747             return TErr(
748                 f"Not enough strings to merge (num_of_strings={num_of_strings})."
749             )
750
751         if num_of_inline_string_comments > 1:
752             return TErr(
753                 f"Too many inline string comments ({num_of_inline_string_comments})."
754             )
755
756         if len(set_of_prefixes) > 1 and set_of_prefixes != {"", "f"}:
757             return TErr(f"Too many different prefixes ({set_of_prefixes}).")
758
759         return Ok(None)
760
761
762 class StringParenStripper(StringTransformer):
763     """StringTransformer that strips surrounding parentheses from strings.
764
765     Requirements:
766         The line contains a string which is surrounded by parentheses and:
767             - The target string is NOT the only argument to a function call.
768             - The target string is NOT a "pointless" string.
769             - If the target string contains a PERCENT, the brackets are not
770               preceded or followed by an operator with higher precedence than
771               PERCENT.
772
773     Transformations:
774         The parentheses mentioned in the 'Requirements' section are stripped.
775
776     Collaborations:
777         StringParenStripper has its own inherent usefulness, but it is also
778         relied on to clean up the parentheses created by StringParenWrapper (in
779         the event that they are no longer needed).
780     """
781
782     def do_match(self, line: Line) -> TMatchResult:
783         LL = line.leaves
784
785         is_valid_index = is_valid_index_factory(LL)
786
787         string_indices = []
788
789         idx = -1
790         while True:
791             idx += 1
792             if idx >= len(LL):
793                 break
794             leaf = LL[idx]
795
796             # Should be a string...
797             if leaf.type != token.STRING:
798                 continue
799
800             # If this is a "pointless" string...
801             if (
802                 leaf.parent
803                 and leaf.parent.parent
804                 and leaf.parent.parent.type == syms.simple_stmt
805             ):
806                 continue
807
808             # Should be preceded by a non-empty LPAR...
809             if (
810                 not is_valid_index(idx - 1)
811                 or LL[idx - 1].type != token.LPAR
812                 or is_empty_lpar(LL[idx - 1])
813             ):
814                 continue
815
816             # That LPAR should NOT be preceded by a function name or a closing
817             # bracket (which could be a function which returns a function or a
818             # list/dictionary that contains a function)...
819             if is_valid_index(idx - 2) and (
820                 LL[idx - 2].type == token.NAME or LL[idx - 2].type in CLOSING_BRACKETS
821             ):
822                 continue
823
824             string_idx = idx
825
826             # Skip the string trailer, if one exists.
827             string_parser = StringParser()
828             next_idx = string_parser.parse(LL, string_idx)
829
830             # if the leaves in the parsed string include a PERCENT, we need to
831             # make sure the initial LPAR is NOT preceded by an operator with
832             # higher or equal precedence to PERCENT
833             if is_valid_index(idx - 2):
834                 # mypy can't quite follow unless we name this
835                 before_lpar = LL[idx - 2]
836                 if token.PERCENT in {leaf.type for leaf in LL[idx - 1 : next_idx]} and (
837                     (
838                         before_lpar.type
839                         in {
840                             token.STAR,
841                             token.AT,
842                             token.SLASH,
843                             token.DOUBLESLASH,
844                             token.PERCENT,
845                             token.TILDE,
846                             token.DOUBLESTAR,
847                             token.AWAIT,
848                             token.LSQB,
849                             token.LPAR,
850                         }
851                     )
852                     or (
853                         # only unary PLUS/MINUS
854                         before_lpar.parent
855                         and before_lpar.parent.type == syms.factor
856                         and (before_lpar.type in {token.PLUS, token.MINUS})
857                     )
858                 ):
859                     continue
860
861             # Should be followed by a non-empty RPAR...
862             if (
863                 is_valid_index(next_idx)
864                 and LL[next_idx].type == token.RPAR
865                 and not is_empty_rpar(LL[next_idx])
866             ):
867                 # That RPAR should NOT be followed by anything with higher
868                 # precedence than PERCENT
869                 if is_valid_index(next_idx + 1) and LL[next_idx + 1].type in {
870                     token.DOUBLESTAR,
871                     token.LSQB,
872                     token.LPAR,
873                     token.DOT,
874                 }:
875                     continue
876
877                 string_indices.append(string_idx)
878                 idx = string_idx
879                 while idx < len(LL) - 1 and LL[idx + 1].type == token.STRING:
880                     idx += 1
881
882         if string_indices:
883             return Ok(string_indices)
884         return TErr("This line has no strings wrapped in parens.")
885
886     def do_transform(
887         self, line: Line, string_indices: List[int]
888     ) -> Iterator[TResult[Line]]:
889         LL = line.leaves
890
891         string_and_rpar_indices: List[int] = []
892         for string_idx in string_indices:
893             string_parser = StringParser()
894             rpar_idx = string_parser.parse(LL, string_idx)
895
896             should_transform = True
897             for leaf in (LL[string_idx - 1], LL[rpar_idx]):
898                 if line.comments_after(leaf):
899                     # Should not strip parentheses which have comments attached
900                     # to them.
901                     should_transform = False
902                     break
903             if should_transform:
904                 string_and_rpar_indices.extend((string_idx, rpar_idx))
905
906         if string_and_rpar_indices:
907             yield Ok(self._transform_to_new_line(line, string_and_rpar_indices))
908         else:
909             yield Err(
910                 CannotTransform("All string groups have comments attached to them.")
911             )
912
913     def _transform_to_new_line(
914         self, line: Line, string_and_rpar_indices: List[int]
915     ) -> Line:
916         LL = line.leaves
917
918         new_line = line.clone()
919         new_line.comments = line.comments.copy()
920
921         previous_idx = -1
922         # We need to sort the indices, since string_idx and its matching
923         # rpar_idx may not come in order, e.g. in
924         # `("outer" % ("inner".join(items)))`, the "inner" string's
925         # string_idx is smaller than "outer" string's rpar_idx.
926         for idx in sorted(string_and_rpar_indices):
927             leaf = LL[idx]
928             lpar_or_rpar_idx = idx - 1 if leaf.type == token.STRING else idx
929             append_leaves(new_line, line, LL[previous_idx + 1 : lpar_or_rpar_idx])
930             if leaf.type == token.STRING:
931                 string_leaf = Leaf(token.STRING, LL[idx].value)
932                 LL[lpar_or_rpar_idx].remove()  # Remove lpar.
933                 replace_child(LL[idx], string_leaf)
934                 new_line.append(string_leaf)
935             else:
936                 LL[lpar_or_rpar_idx].remove()  # This is a rpar.
937
938             previous_idx = idx
939
940         # Append the leaves after the last idx:
941         append_leaves(new_line, line, LL[idx + 1 :])
942
943         return new_line
944
945
946 class BaseStringSplitter(StringTransformer):
947     """
948     Abstract class for StringTransformers which transform a Line's strings by splitting
949     them or placing them on their own lines where necessary to avoid going over
950     the configured line length.
951
952     Requirements:
953         * The target string value is responsible for the line going over the
954         line length limit. It follows that after all of black's other line
955         split methods have been exhausted, this line (or one of the resulting
956         lines after all line splits are performed) would still be over the
957         line_length limit unless we split this string.
958             AND
959         * The target string is NOT a "pointless" string (i.e. a string that has
960         no parent or siblings).
961             AND
962         * The target string is not followed by an inline comment that appears
963         to be a pragma.
964             AND
965         * The target string is not a multiline (i.e. triple-quote) string.
966     """
967
968     STRING_OPERATORS: Final = [
969         token.EQEQUAL,
970         token.GREATER,
971         token.GREATEREQUAL,
972         token.LESS,
973         token.LESSEQUAL,
974         token.NOTEQUAL,
975         token.PERCENT,
976         token.PLUS,
977         token.STAR,
978     ]
979
980     @abstractmethod
981     def do_splitter_match(self, line: Line) -> TMatchResult:
982         """
983         BaseStringSplitter asks its clients to override this method instead of
984         `StringTransformer.do_match(...)`.
985
986         Follows the same protocol as `StringTransformer.do_match(...)`.
987
988         Refer to `help(StringTransformer.do_match)` for more information.
989         """
990
991     def do_match(self, line: Line) -> TMatchResult:
992         match_result = self.do_splitter_match(line)
993         if isinstance(match_result, Err):
994             return match_result
995
996         string_indices = match_result.ok()
997         assert len(string_indices) == 1, (
998             f"{self.__class__.__name__} should only find one match at a time, found"
999             f" {len(string_indices)}"
1000         )
1001         string_idx = string_indices[0]
1002         vresult = self._validate(line, string_idx)
1003         if isinstance(vresult, Err):
1004             return vresult
1005
1006         return match_result
1007
1008     def _validate(self, line: Line, string_idx: int) -> TResult[None]:
1009         """
1010         Checks that @line meets all of the requirements listed in this classes'
1011         docstring. Refer to `help(BaseStringSplitter)` for a detailed
1012         description of those requirements.
1013
1014         Returns:
1015             * Ok(None), if ALL of the requirements are met.
1016                 OR
1017             * Err(CannotTransform), if ANY of the requirements are NOT met.
1018         """
1019         LL = line.leaves
1020
1021         string_leaf = LL[string_idx]
1022
1023         max_string_length = self._get_max_string_length(line, string_idx)
1024         if len(string_leaf.value) <= max_string_length:
1025             return TErr(
1026                 "The string itself is not what is causing this line to be too long."
1027             )
1028
1029         if not string_leaf.parent or [L.type for L in string_leaf.parent.children] == [
1030             token.STRING,
1031             token.NEWLINE,
1032         ]:
1033             return TErr(
1034                 f"This string ({string_leaf.value}) appears to be pointless (i.e. has"
1035                 " no parent)."
1036             )
1037
1038         if id(line.leaves[string_idx]) in line.comments and contains_pragma_comment(
1039             line.comments[id(line.leaves[string_idx])]
1040         ):
1041             return TErr(
1042                 "Line appears to end with an inline pragma comment. Splitting the line"
1043                 " could modify the pragma's behavior."
1044             )
1045
1046         if has_triple_quotes(string_leaf.value):
1047             return TErr("We cannot split multiline strings.")
1048
1049         return Ok(None)
1050
1051     def _get_max_string_length(self, line: Line, string_idx: int) -> int:
1052         """
1053         Calculates the max string length used when attempting to determine
1054         whether or not the target string is responsible for causing the line to
1055         go over the line length limit.
1056
1057         WARNING: This method is tightly coupled to both StringSplitter and
1058         (especially) StringParenWrapper. There is probably a better way to
1059         accomplish what is being done here.
1060
1061         Returns:
1062             max_string_length: such that `line.leaves[string_idx].value >
1063             max_string_length` implies that the target string IS responsible
1064             for causing this line to exceed the line length limit.
1065         """
1066         LL = line.leaves
1067
1068         is_valid_index = is_valid_index_factory(LL)
1069
1070         # We use the shorthand "WMA4" in comments to abbreviate "We must
1071         # account for". When giving examples, we use STRING to mean some/any
1072         # valid string.
1073         #
1074         # Finally, we use the following convenience variables:
1075         #
1076         #   P:  The leaf that is before the target string leaf.
1077         #   N:  The leaf that is after the target string leaf.
1078         #   NN: The leaf that is after N.
1079
1080         # WMA4 the whitespace at the beginning of the line.
1081         offset = line.depth * 4
1082
1083         if is_valid_index(string_idx - 1):
1084             p_idx = string_idx - 1
1085             if (
1086                 LL[string_idx - 1].type == token.LPAR
1087                 and LL[string_idx - 1].value == ""
1088                 and string_idx >= 2
1089             ):
1090                 # If the previous leaf is an empty LPAR placeholder, we should skip it.
1091                 p_idx -= 1
1092
1093             P = LL[p_idx]
1094             if P.type in self.STRING_OPERATORS:
1095                 # WMA4 a space and a string operator (e.g. `+ STRING` or `== STRING`).
1096                 offset += len(str(P)) + 1
1097
1098             if P.type == token.COMMA:
1099                 # WMA4 a space, a comma, and a closing bracket [e.g. `), STRING`].
1100                 offset += 3
1101
1102             if P.type in [token.COLON, token.EQUAL, token.PLUSEQUAL, token.NAME]:
1103                 # This conditional branch is meant to handle dictionary keys,
1104                 # variable assignments, 'return STRING' statement lines, and
1105                 # 'else STRING' ternary expression lines.
1106
1107                 # WMA4 a single space.
1108                 offset += 1
1109
1110                 # WMA4 the lengths of any leaves that came before that space,
1111                 # but after any closing bracket before that space.
1112                 for leaf in reversed(LL[: p_idx + 1]):
1113                     offset += len(str(leaf))
1114                     if leaf.type in CLOSING_BRACKETS:
1115                         break
1116
1117         if is_valid_index(string_idx + 1):
1118             N = LL[string_idx + 1]
1119             if N.type == token.RPAR and N.value == "" and len(LL) > string_idx + 2:
1120                 # If the next leaf is an empty RPAR placeholder, we should skip it.
1121                 N = LL[string_idx + 2]
1122
1123             if N.type == token.COMMA:
1124                 # WMA4 a single comma at the end of the string (e.g `STRING,`).
1125                 offset += 1
1126
1127             if is_valid_index(string_idx + 2):
1128                 NN = LL[string_idx + 2]
1129
1130                 if N.type == token.DOT and NN.type == token.NAME:
1131                     # This conditional branch is meant to handle method calls invoked
1132                     # off of a string literal up to and including the LPAR character.
1133
1134                     # WMA4 the '.' character.
1135                     offset += 1
1136
1137                     if (
1138                         is_valid_index(string_idx + 3)
1139                         and LL[string_idx + 3].type == token.LPAR
1140                     ):
1141                         # WMA4 the left parenthesis character.
1142                         offset += 1
1143
1144                     # WMA4 the length of the method's name.
1145                     offset += len(NN.value)
1146
1147         has_comments = False
1148         for comment_leaf in line.comments_after(LL[string_idx]):
1149             if not has_comments:
1150                 has_comments = True
1151                 # WMA4 two spaces before the '#' character.
1152                 offset += 2
1153
1154             # WMA4 the length of the inline comment.
1155             offset += len(comment_leaf.value)
1156
1157         max_string_length = self.line_length - offset
1158         return max_string_length
1159
1160     @staticmethod
1161     def _prefer_paren_wrap_match(LL: List[Leaf]) -> Optional[int]:
1162         """
1163         Returns:
1164             string_idx such that @LL[string_idx] is equal to our target (i.e.
1165             matched) string, if this line matches the "prefer paren wrap" statement
1166             requirements listed in the 'Requirements' section of the StringParenWrapper
1167             class's docstring.
1168                 OR
1169             None, otherwise.
1170         """
1171         # The line must start with a string.
1172         if LL[0].type != token.STRING:
1173             return None
1174
1175         # If the string is surrounded by commas (or is the first/last child)...
1176         prev_sibling = LL[0].prev_sibling
1177         next_sibling = LL[0].next_sibling
1178         if not prev_sibling and not next_sibling and parent_type(LL[0]) == syms.atom:
1179             # If it's an atom string, we need to check the parent atom's siblings.
1180             parent = LL[0].parent
1181             assert parent is not None  # For type checkers.
1182             prev_sibling = parent.prev_sibling
1183             next_sibling = parent.next_sibling
1184         if (not prev_sibling or prev_sibling.type == token.COMMA) and (
1185             not next_sibling or next_sibling.type == token.COMMA
1186         ):
1187             return 0
1188
1189         return None
1190
1191
1192 def iter_fexpr_spans(s: str) -> Iterator[Tuple[int, int]]:
1193     """
1194     Yields spans corresponding to expressions in a given f-string.
1195     Spans are half-open ranges (left inclusive, right exclusive).
1196     Assumes the input string is a valid f-string, but will not crash if the input
1197     string is invalid.
1198     """
1199     stack: List[int] = []  # our curly paren stack
1200     i = 0
1201     while i < len(s):
1202         if s[i] == "{":
1203             # if we're in a string part of the f-string, ignore escaped curly braces
1204             if not stack and i + 1 < len(s) and s[i + 1] == "{":
1205                 i += 2
1206                 continue
1207             stack.append(i)
1208             i += 1
1209             continue
1210
1211         if s[i] == "}":
1212             if not stack:
1213                 i += 1
1214                 continue
1215             j = stack.pop()
1216             # we've made it back out of the expression! yield the span
1217             if not stack:
1218                 yield (j, i + 1)
1219             i += 1
1220             continue
1221
1222         # if we're in an expression part of the f-string, fast forward through strings
1223         # note that backslashes are not legal in the expression portion of f-strings
1224         if stack:
1225             delim = None
1226             if s[i : i + 3] in ("'''", '"""'):
1227                 delim = s[i : i + 3]
1228             elif s[i] in ("'", '"'):
1229                 delim = s[i]
1230             if delim:
1231                 i += len(delim)
1232                 while i < len(s) and s[i : i + len(delim)] != delim:
1233                     i += 1
1234                 i += len(delim)
1235                 continue
1236         i += 1
1237
1238
1239 def fstring_contains_expr(s: str) -> bool:
1240     return any(iter_fexpr_spans(s))
1241
1242
1243 class StringSplitter(BaseStringSplitter, CustomSplitMapMixin):
1244     """
1245     StringTransformer that splits "atom" strings (i.e. strings which exist on
1246     lines by themselves).
1247
1248     Requirements:
1249         * The line consists ONLY of a single string (possibly prefixed by a
1250         string operator [e.g. '+' or '==']), MAYBE a string trailer, and MAYBE
1251         a trailing comma.
1252             AND
1253         * All of the requirements listed in BaseStringSplitter's docstring.
1254
1255     Transformations:
1256         The string mentioned in the 'Requirements' section is split into as
1257         many substrings as necessary to adhere to the configured line length.
1258
1259         In the final set of substrings, no substring should be smaller than
1260         MIN_SUBSTR_SIZE characters.
1261
1262         The string will ONLY be split on spaces (i.e. each new substring should
1263         start with a space). Note that the string will NOT be split on a space
1264         which is escaped with a backslash.
1265
1266         If the string is an f-string, it will NOT be split in the middle of an
1267         f-expression (e.g. in f"FooBar: {foo() if x else bar()}", {foo() if x
1268         else bar()} is an f-expression).
1269
1270         If the string that is being split has an associated set of custom split
1271         records and those custom splits will NOT result in any line going over
1272         the configured line length, those custom splits are used. Otherwise the
1273         string is split as late as possible (from left-to-right) while still
1274         adhering to the transformation rules listed above.
1275
1276     Collaborations:
1277         StringSplitter relies on StringMerger to construct the appropriate
1278         CustomSplit objects and add them to the custom split map.
1279     """
1280
1281     MIN_SUBSTR_SIZE: Final = 6
1282
1283     def do_splitter_match(self, line: Line) -> TMatchResult:
1284         LL = line.leaves
1285
1286         if self._prefer_paren_wrap_match(LL) is not None:
1287             return TErr("Line needs to be wrapped in parens first.")
1288
1289         is_valid_index = is_valid_index_factory(LL)
1290
1291         idx = 0
1292
1293         # The first two leaves MAY be the 'not in' keywords...
1294         if (
1295             is_valid_index(idx)
1296             and is_valid_index(idx + 1)
1297             and [LL[idx].type, LL[idx + 1].type] == [token.NAME, token.NAME]
1298             and str(LL[idx]) + str(LL[idx + 1]) == "not in"
1299         ):
1300             idx += 2
1301         # Else the first leaf MAY be a string operator symbol or the 'in' keyword...
1302         elif is_valid_index(idx) and (
1303             LL[idx].type in self.STRING_OPERATORS
1304             or LL[idx].type == token.NAME
1305             and str(LL[idx]) == "in"
1306         ):
1307             idx += 1
1308
1309         # The next/first leaf MAY be an empty LPAR...
1310         if is_valid_index(idx) and is_empty_lpar(LL[idx]):
1311             idx += 1
1312
1313         # The next/first leaf MUST be a string...
1314         if not is_valid_index(idx) or LL[idx].type != token.STRING:
1315             return TErr("Line does not start with a string.")
1316
1317         string_idx = idx
1318
1319         # Skip the string trailer, if one exists.
1320         string_parser = StringParser()
1321         idx = string_parser.parse(LL, string_idx)
1322
1323         # That string MAY be followed by an empty RPAR...
1324         if is_valid_index(idx) and is_empty_rpar(LL[idx]):
1325             idx += 1
1326
1327         # That string / empty RPAR leaf MAY be followed by a comma...
1328         if is_valid_index(idx) and LL[idx].type == token.COMMA:
1329             idx += 1
1330
1331         # But no more leaves are allowed...
1332         if is_valid_index(idx):
1333             return TErr("This line does not end with a string.")
1334
1335         return Ok([string_idx])
1336
1337     def do_transform(
1338         self, line: Line, string_indices: List[int]
1339     ) -> Iterator[TResult[Line]]:
1340         LL = line.leaves
1341         assert len(string_indices) == 1, (
1342             f"{self.__class__.__name__} should only find one match at a time, found"
1343             f" {len(string_indices)}"
1344         )
1345         string_idx = string_indices[0]
1346
1347         QUOTE = LL[string_idx].value[-1]
1348
1349         is_valid_index = is_valid_index_factory(LL)
1350         insert_str_child = insert_str_child_factory(LL[string_idx])
1351
1352         prefix = get_string_prefix(LL[string_idx].value).lower()
1353
1354         # We MAY choose to drop the 'f' prefix from substrings that don't
1355         # contain any f-expressions, but ONLY if the original f-string
1356         # contains at least one f-expression. Otherwise, we will alter the AST
1357         # of the program.
1358         drop_pointless_f_prefix = ("f" in prefix) and fstring_contains_expr(
1359             LL[string_idx].value
1360         )
1361
1362         first_string_line = True
1363
1364         string_op_leaves = self._get_string_operator_leaves(LL)
1365         string_op_leaves_length = (
1366             sum(len(str(prefix_leaf)) for prefix_leaf in string_op_leaves) + 1
1367             if string_op_leaves
1368             else 0
1369         )
1370
1371         def maybe_append_string_operators(new_line: Line) -> None:
1372             """
1373             Side Effects:
1374                 If @line starts with a string operator and this is the first
1375                 line we are constructing, this function appends the string
1376                 operator to @new_line and replaces the old string operator leaf
1377                 in the node structure. Otherwise this function does nothing.
1378             """
1379             maybe_prefix_leaves = string_op_leaves if first_string_line else []
1380             for i, prefix_leaf in enumerate(maybe_prefix_leaves):
1381                 replace_child(LL[i], prefix_leaf)
1382                 new_line.append(prefix_leaf)
1383
1384         ends_with_comma = (
1385             is_valid_index(string_idx + 1) and LL[string_idx + 1].type == token.COMMA
1386         )
1387
1388         def max_last_string() -> int:
1389             """
1390             Returns:
1391                 The max allowed length of the string value used for the last
1392                 line we will construct.
1393             """
1394             result = self.line_length
1395             result -= line.depth * 4
1396             result -= 1 if ends_with_comma else 0
1397             result -= string_op_leaves_length
1398             return result
1399
1400         # --- Calculate Max Break Index (for string value)
1401         # We start with the line length limit
1402         max_break_idx = self.line_length
1403         # The last index of a string of length N is N-1.
1404         max_break_idx -= 1
1405         # Leading whitespace is not present in the string value (e.g. Leaf.value).
1406         max_break_idx -= line.depth * 4
1407         if max_break_idx < 0:
1408             yield TErr(
1409                 f"Unable to split {LL[string_idx].value} at such high of a line depth:"
1410                 f" {line.depth}"
1411             )
1412             return
1413
1414         # Check if StringMerger registered any custom splits.
1415         custom_splits = self.pop_custom_splits(LL[string_idx].value)
1416         # We use them ONLY if none of them would produce lines that exceed the
1417         # line limit.
1418         use_custom_breakpoints = bool(
1419             custom_splits
1420             and all(csplit.break_idx <= max_break_idx for csplit in custom_splits)
1421         )
1422
1423         # Temporary storage for the remaining chunk of the string line that
1424         # can't fit onto the line currently being constructed.
1425         rest_value = LL[string_idx].value
1426
1427         def more_splits_should_be_made() -> bool:
1428             """
1429             Returns:
1430                 True iff `rest_value` (the remaining string value from the last
1431                 split), should be split again.
1432             """
1433             if use_custom_breakpoints:
1434                 return len(custom_splits) > 1
1435             else:
1436                 return len(rest_value) > max_last_string()
1437
1438         string_line_results: List[Ok[Line]] = []
1439         while more_splits_should_be_made():
1440             if use_custom_breakpoints:
1441                 # Custom User Split (manual)
1442                 csplit = custom_splits.pop(0)
1443                 break_idx = csplit.break_idx
1444             else:
1445                 # Algorithmic Split (automatic)
1446                 max_bidx = max_break_idx - string_op_leaves_length
1447                 maybe_break_idx = self._get_break_idx(rest_value, max_bidx)
1448                 if maybe_break_idx is None:
1449                     # If we are unable to algorithmically determine a good split
1450                     # and this string has custom splits registered to it, we
1451                     # fall back to using them--which means we have to start
1452                     # over from the beginning.
1453                     if custom_splits:
1454                         rest_value = LL[string_idx].value
1455                         string_line_results = []
1456                         first_string_line = True
1457                         use_custom_breakpoints = True
1458                         continue
1459
1460                     # Otherwise, we stop splitting here.
1461                     break
1462
1463                 break_idx = maybe_break_idx
1464
1465             # --- Construct `next_value`
1466             next_value = rest_value[:break_idx] + QUOTE
1467
1468             # HACK: The following 'if' statement is a hack to fix the custom
1469             # breakpoint index in the case of either: (a) substrings that were
1470             # f-strings but will have the 'f' prefix removed OR (b) substrings
1471             # that were not f-strings but will now become f-strings because of
1472             # redundant use of the 'f' prefix (i.e. none of the substrings
1473             # contain f-expressions but one or more of them had the 'f' prefix
1474             # anyway; in which case, we will prepend 'f' to _all_ substrings).
1475             #
1476             # There is probably a better way to accomplish what is being done
1477             # here...
1478             #
1479             # If this substring is an f-string, we _could_ remove the 'f'
1480             # prefix, and the current custom split did NOT originally use a
1481             # prefix...
1482             if (
1483                 use_custom_breakpoints
1484                 and not csplit.has_prefix
1485                 and (
1486                     # `next_value == prefix + QUOTE` happens when the custom
1487                     # split is an empty string.
1488                     next_value == prefix + QUOTE
1489                     or next_value != self._normalize_f_string(next_value, prefix)
1490                 )
1491             ):
1492                 # Then `csplit.break_idx` will be off by one after removing
1493                 # the 'f' prefix.
1494                 break_idx += 1
1495                 next_value = rest_value[:break_idx] + QUOTE
1496
1497             if drop_pointless_f_prefix:
1498                 next_value = self._normalize_f_string(next_value, prefix)
1499
1500             # --- Construct `next_leaf`
1501             next_leaf = Leaf(token.STRING, next_value)
1502             insert_str_child(next_leaf)
1503             self._maybe_normalize_string_quotes(next_leaf)
1504
1505             # --- Construct `next_line`
1506             next_line = line.clone()
1507             maybe_append_string_operators(next_line)
1508             next_line.append(next_leaf)
1509             string_line_results.append(Ok(next_line))
1510
1511             rest_value = prefix + QUOTE + rest_value[break_idx:]
1512             first_string_line = False
1513
1514         yield from string_line_results
1515
1516         if drop_pointless_f_prefix:
1517             rest_value = self._normalize_f_string(rest_value, prefix)
1518
1519         rest_leaf = Leaf(token.STRING, rest_value)
1520         insert_str_child(rest_leaf)
1521
1522         # NOTE: I could not find a test case that verifies that the following
1523         # line is actually necessary, but it seems to be. Otherwise we risk
1524         # not normalizing the last substring, right?
1525         self._maybe_normalize_string_quotes(rest_leaf)
1526
1527         last_line = line.clone()
1528         maybe_append_string_operators(last_line)
1529
1530         # If there are any leaves to the right of the target string...
1531         if is_valid_index(string_idx + 1):
1532             # We use `temp_value` here to determine how long the last line
1533             # would be if we were to append all the leaves to the right of the
1534             # target string to the last string line.
1535             temp_value = rest_value
1536             for leaf in LL[string_idx + 1 :]:
1537                 temp_value += str(leaf)
1538                 if leaf.type == token.LPAR:
1539                     break
1540
1541             # Try to fit them all on the same line with the last substring...
1542             if (
1543                 len(temp_value) <= max_last_string()
1544                 or LL[string_idx + 1].type == token.COMMA
1545             ):
1546                 last_line.append(rest_leaf)
1547                 append_leaves(last_line, line, LL[string_idx + 1 :])
1548                 yield Ok(last_line)
1549             # Otherwise, place the last substring on one line and everything
1550             # else on a line below that...
1551             else:
1552                 last_line.append(rest_leaf)
1553                 yield Ok(last_line)
1554
1555                 non_string_line = line.clone()
1556                 append_leaves(non_string_line, line, LL[string_idx + 1 :])
1557                 yield Ok(non_string_line)
1558         # Else the target string was the last leaf...
1559         else:
1560             last_line.append(rest_leaf)
1561             last_line.comments = line.comments.copy()
1562             yield Ok(last_line)
1563
1564     def _iter_nameescape_slices(self, string: str) -> Iterator[Tuple[Index, Index]]:
1565         """
1566         Yields:
1567             All ranges of @string which, if @string were to be split there,
1568             would result in the splitting of an \\N{...} expression (which is NOT
1569             allowed).
1570         """
1571         # True - the previous backslash was unescaped
1572         # False - the previous backslash was escaped *or* there was no backslash
1573         previous_was_unescaped_backslash = False
1574         it = iter(enumerate(string))
1575         for idx, c in it:
1576             if c == "\\":
1577                 previous_was_unescaped_backslash = not previous_was_unescaped_backslash
1578                 continue
1579             if not previous_was_unescaped_backslash or c != "N":
1580                 previous_was_unescaped_backslash = False
1581                 continue
1582             previous_was_unescaped_backslash = False
1583
1584             begin = idx - 1  # the position of backslash before \N{...}
1585             for idx, c in it:
1586                 if c == "}":
1587                     end = idx
1588                     break
1589             else:
1590                 # malformed nameescape expression?
1591                 # should have been detected by AST parsing earlier...
1592                 raise RuntimeError(f"{self.__class__.__name__} LOGIC ERROR!")
1593             yield begin, end
1594
1595     def _iter_fexpr_slices(self, string: str) -> Iterator[Tuple[Index, Index]]:
1596         """
1597         Yields:
1598             All ranges of @string which, if @string were to be split there,
1599             would result in the splitting of an f-expression (which is NOT
1600             allowed).
1601         """
1602         if "f" not in get_string_prefix(string).lower():
1603             return
1604         yield from iter_fexpr_spans(string)
1605
1606     def _get_illegal_split_indices(self, string: str) -> Set[Index]:
1607         illegal_indices: Set[Index] = set()
1608         iterators = [
1609             self._iter_fexpr_slices(string),
1610             self._iter_nameescape_slices(string),
1611         ]
1612         for it in iterators:
1613             for begin, end in it:
1614                 illegal_indices.update(range(begin, end + 1))
1615         return illegal_indices
1616
1617     def _get_break_idx(self, string: str, max_break_idx: int) -> Optional[int]:
1618         """
1619         This method contains the algorithm that StringSplitter uses to
1620         determine which character to split each string at.
1621
1622         Args:
1623             @string: The substring that we are attempting to split.
1624             @max_break_idx: The ideal break index. We will return this value if it
1625             meets all the necessary conditions. In the likely event that it
1626             doesn't we will try to find the closest index BELOW @max_break_idx
1627             that does. If that fails, we will expand our search by also
1628             considering all valid indices ABOVE @max_break_idx.
1629
1630         Pre-Conditions:
1631             * assert_is_leaf_string(@string)
1632             * 0 <= @max_break_idx < len(@string)
1633
1634         Returns:
1635             break_idx, if an index is able to be found that meets all of the
1636             conditions listed in the 'Transformations' section of this classes'
1637             docstring.
1638                 OR
1639             None, otherwise.
1640         """
1641         is_valid_index = is_valid_index_factory(string)
1642
1643         assert is_valid_index(max_break_idx)
1644         assert_is_leaf_string(string)
1645
1646         _illegal_split_indices = self._get_illegal_split_indices(string)
1647
1648         def breaks_unsplittable_expression(i: Index) -> bool:
1649             """
1650             Returns:
1651                 True iff returning @i would result in the splitting of an
1652                 unsplittable expression (which is NOT allowed).
1653             """
1654             return i in _illegal_split_indices
1655
1656         def passes_all_checks(i: Index) -> bool:
1657             """
1658             Returns:
1659                 True iff ALL of the conditions listed in the 'Transformations'
1660                 section of this classes' docstring would be be met by returning @i.
1661             """
1662             is_space = string[i] == " "
1663
1664             is_not_escaped = True
1665             j = i - 1
1666             while is_valid_index(j) and string[j] == "\\":
1667                 is_not_escaped = not is_not_escaped
1668                 j -= 1
1669
1670             is_big_enough = (
1671                 len(string[i:]) >= self.MIN_SUBSTR_SIZE
1672                 and len(string[:i]) >= self.MIN_SUBSTR_SIZE
1673             )
1674             return (
1675                 is_space
1676                 and is_not_escaped
1677                 and is_big_enough
1678                 and not breaks_unsplittable_expression(i)
1679             )
1680
1681         # First, we check all indices BELOW @max_break_idx.
1682         break_idx = max_break_idx
1683         while is_valid_index(break_idx - 1) and not passes_all_checks(break_idx):
1684             break_idx -= 1
1685
1686         if not passes_all_checks(break_idx):
1687             # If that fails, we check all indices ABOVE @max_break_idx.
1688             #
1689             # If we are able to find a valid index here, the next line is going
1690             # to be longer than the specified line length, but it's probably
1691             # better than doing nothing at all.
1692             break_idx = max_break_idx + 1
1693             while is_valid_index(break_idx + 1) and not passes_all_checks(break_idx):
1694                 break_idx += 1
1695
1696             if not is_valid_index(break_idx) or not passes_all_checks(break_idx):
1697                 return None
1698
1699         return break_idx
1700
1701     def _maybe_normalize_string_quotes(self, leaf: Leaf) -> None:
1702         if self.normalize_strings:
1703             leaf.value = normalize_string_quotes(leaf.value)
1704
1705     def _normalize_f_string(self, string: str, prefix: str) -> str:
1706         """
1707         Pre-Conditions:
1708             * assert_is_leaf_string(@string)
1709
1710         Returns:
1711             * If @string is an f-string that contains no f-expressions, we
1712             return a string identical to @string except that the 'f' prefix
1713             has been stripped and all double braces (i.e. '{{' or '}}') have
1714             been normalized (i.e. turned into '{' or '}').
1715                 OR
1716             * Otherwise, we return @string.
1717         """
1718         assert_is_leaf_string(string)
1719
1720         if "f" in prefix and not fstring_contains_expr(string):
1721             new_prefix = prefix.replace("f", "")
1722
1723             temp = string[len(prefix) :]
1724             temp = re.sub(r"\{\{", "{", temp)
1725             temp = re.sub(r"\}\}", "}", temp)
1726             new_string = temp
1727
1728             return f"{new_prefix}{new_string}"
1729         else:
1730             return string
1731
1732     def _get_string_operator_leaves(self, leaves: Iterable[Leaf]) -> List[Leaf]:
1733         LL = list(leaves)
1734
1735         string_op_leaves = []
1736         i = 0
1737         while LL[i].type in self.STRING_OPERATORS + [token.NAME]:
1738             prefix_leaf = Leaf(LL[i].type, str(LL[i]).strip())
1739             string_op_leaves.append(prefix_leaf)
1740             i += 1
1741         return string_op_leaves
1742
1743
1744 class StringParenWrapper(BaseStringSplitter, CustomSplitMapMixin):
1745     """
1746     StringTransformer that wraps strings in parens and then splits at the LPAR.
1747
1748     Requirements:
1749         All of the requirements listed in BaseStringSplitter's docstring in
1750         addition to the requirements listed below:
1751
1752         * The line is a return/yield statement, which returns/yields a string.
1753             OR
1754         * The line is part of a ternary expression (e.g. `x = y if cond else
1755         z`) such that the line starts with `else <string>`, where <string> is
1756         some string.
1757             OR
1758         * The line is an assert statement, which ends with a string.
1759             OR
1760         * The line is an assignment statement (e.g. `x = <string>` or `x +=
1761         <string>`) such that the variable is being assigned the value of some
1762         string.
1763             OR
1764         * The line is a dictionary key assignment where some valid key is being
1765         assigned the value of some string.
1766             OR
1767         * The line is an lambda expression and the value is a string.
1768             OR
1769         * The line starts with an "atom" string that prefers to be wrapped in
1770         parens. It's preferred to be wrapped when the string is surrounded by
1771         commas (or is the first/last child).
1772
1773     Transformations:
1774         The chosen string is wrapped in parentheses and then split at the LPAR.
1775
1776         We then have one line which ends with an LPAR and another line that
1777         starts with the chosen string. The latter line is then split again at
1778         the RPAR. This results in the RPAR (and possibly a trailing comma)
1779         being placed on its own line.
1780
1781         NOTE: If any leaves exist to the right of the chosen string (except
1782         for a trailing comma, which would be placed after the RPAR), those
1783         leaves are placed inside the parentheses.  In effect, the chosen
1784         string is not necessarily being "wrapped" by parentheses. We can,
1785         however, count on the LPAR being placed directly before the chosen
1786         string.
1787
1788         In other words, StringParenWrapper creates "atom" strings. These
1789         can then be split again by StringSplitter, if necessary.
1790
1791     Collaborations:
1792         In the event that a string line split by StringParenWrapper is
1793         changed such that it no longer needs to be given its own line,
1794         StringParenWrapper relies on StringParenStripper to clean up the
1795         parentheses it created.
1796
1797         For "atom" strings that prefers to be wrapped in parens, it requires
1798         StringSplitter to hold the split until the string is wrapped in parens.
1799     """
1800
1801     def do_splitter_match(self, line: Line) -> TMatchResult:
1802         LL = line.leaves
1803
1804         if line.leaves[-1].type in OPENING_BRACKETS:
1805             return TErr(
1806                 "Cannot wrap parens around a line that ends in an opening bracket."
1807             )
1808
1809         string_idx = (
1810             self._return_match(LL)
1811             or self._else_match(LL)
1812             or self._assert_match(LL)
1813             or self._assign_match(LL)
1814             or self._dict_or_lambda_match(LL)
1815             or self._prefer_paren_wrap_match(LL)
1816         )
1817
1818         if string_idx is not None:
1819             string_value = line.leaves[string_idx].value
1820             # If the string has no spaces...
1821             if " " not in string_value:
1822                 # And will still violate the line length limit when split...
1823                 max_string_length = self.line_length - ((line.depth + 1) * 4)
1824                 if len(string_value) > max_string_length:
1825                     # And has no associated custom splits...
1826                     if not self.has_custom_splits(string_value):
1827                         # Then we should NOT put this string on its own line.
1828                         return TErr(
1829                             "We do not wrap long strings in parentheses when the"
1830                             " resultant line would still be over the specified line"
1831                             " length and can't be split further by StringSplitter."
1832                         )
1833             return Ok([string_idx])
1834
1835         return TErr("This line does not contain any non-atomic strings.")
1836
1837     @staticmethod
1838     def _return_match(LL: List[Leaf]) -> Optional[int]:
1839         """
1840         Returns:
1841             string_idx such that @LL[string_idx] is equal to our target (i.e.
1842             matched) string, if this line matches the return/yield statement
1843             requirements listed in the 'Requirements' section of this classes'
1844             docstring.
1845                 OR
1846             None, otherwise.
1847         """
1848         # If this line is apart of a return/yield statement and the first leaf
1849         # contains either the "return" or "yield" keywords...
1850         if parent_type(LL[0]) in [syms.return_stmt, syms.yield_expr] and LL[
1851             0
1852         ].value in ["return", "yield"]:
1853             is_valid_index = is_valid_index_factory(LL)
1854
1855             idx = 2 if is_valid_index(1) and is_empty_par(LL[1]) else 1
1856             # The next visible leaf MUST contain a string...
1857             if is_valid_index(idx) and LL[idx].type == token.STRING:
1858                 return idx
1859
1860         return None
1861
1862     @staticmethod
1863     def _else_match(LL: List[Leaf]) -> Optional[int]:
1864         """
1865         Returns:
1866             string_idx such that @LL[string_idx] is equal to our target (i.e.
1867             matched) string, if this line matches the ternary expression
1868             requirements listed in the 'Requirements' section of this classes'
1869             docstring.
1870                 OR
1871             None, otherwise.
1872         """
1873         # If this line is apart of a ternary expression and the first leaf
1874         # contains the "else" keyword...
1875         if (
1876             parent_type(LL[0]) == syms.test
1877             and LL[0].type == token.NAME
1878             and LL[0].value == "else"
1879         ):
1880             is_valid_index = is_valid_index_factory(LL)
1881
1882             idx = 2 if is_valid_index(1) and is_empty_par(LL[1]) else 1
1883             # The next visible leaf MUST contain a string...
1884             if is_valid_index(idx) and LL[idx].type == token.STRING:
1885                 return idx
1886
1887         return None
1888
1889     @staticmethod
1890     def _assert_match(LL: List[Leaf]) -> Optional[int]:
1891         """
1892         Returns:
1893             string_idx such that @LL[string_idx] is equal to our target (i.e.
1894             matched) string, if this line matches the assert statement
1895             requirements listed in the 'Requirements' section of this classes'
1896             docstring.
1897                 OR
1898             None, otherwise.
1899         """
1900         # If this line is apart of an assert statement and the first leaf
1901         # contains the "assert" keyword...
1902         if parent_type(LL[0]) == syms.assert_stmt and LL[0].value == "assert":
1903             is_valid_index = is_valid_index_factory(LL)
1904
1905             for i, leaf in enumerate(LL):
1906                 # We MUST find a comma...
1907                 if leaf.type == token.COMMA:
1908                     idx = i + 2 if is_empty_par(LL[i + 1]) else i + 1
1909
1910                     # That comma MUST be followed by a string...
1911                     if is_valid_index(idx) and LL[idx].type == token.STRING:
1912                         string_idx = idx
1913
1914                         # Skip the string trailer, if one exists.
1915                         string_parser = StringParser()
1916                         idx = string_parser.parse(LL, string_idx)
1917
1918                         # But no more leaves are allowed...
1919                         if not is_valid_index(idx):
1920                             return string_idx
1921
1922         return None
1923
1924     @staticmethod
1925     def _assign_match(LL: List[Leaf]) -> Optional[int]:
1926         """
1927         Returns:
1928             string_idx such that @LL[string_idx] is equal to our target (i.e.
1929             matched) string, if this line matches the assignment statement
1930             requirements listed in the 'Requirements' section of this classes'
1931             docstring.
1932                 OR
1933             None, otherwise.
1934         """
1935         # If this line is apart of an expression statement or is a function
1936         # argument AND the first leaf contains a variable name...
1937         if (
1938             parent_type(LL[0]) in [syms.expr_stmt, syms.argument, syms.power]
1939             and LL[0].type == token.NAME
1940         ):
1941             is_valid_index = is_valid_index_factory(LL)
1942
1943             for i, leaf in enumerate(LL):
1944                 # We MUST find either an '=' or '+=' symbol...
1945                 if leaf.type in [token.EQUAL, token.PLUSEQUAL]:
1946                     idx = i + 2 if is_empty_par(LL[i + 1]) else i + 1
1947
1948                     # That symbol MUST be followed by a string...
1949                     if is_valid_index(idx) and LL[idx].type == token.STRING:
1950                         string_idx = idx
1951
1952                         # Skip the string trailer, if one exists.
1953                         string_parser = StringParser()
1954                         idx = string_parser.parse(LL, string_idx)
1955
1956                         # The next leaf MAY be a comma iff this line is apart
1957                         # of a function argument...
1958                         if (
1959                             parent_type(LL[0]) == syms.argument
1960                             and is_valid_index(idx)
1961                             and LL[idx].type == token.COMMA
1962                         ):
1963                             idx += 1
1964
1965                         # But no more leaves are allowed...
1966                         if not is_valid_index(idx):
1967                             return string_idx
1968
1969         return None
1970
1971     @staticmethod
1972     def _dict_or_lambda_match(LL: List[Leaf]) -> Optional[int]:
1973         """
1974         Returns:
1975             string_idx such that @LL[string_idx] is equal to our target (i.e.
1976             matched) string, if this line matches the dictionary key assignment
1977             statement or lambda expression requirements listed in the
1978             'Requirements' section of this classes' docstring.
1979                 OR
1980             None, otherwise.
1981         """
1982         # If this line is a part of a dictionary key assignment or lambda expression...
1983         parent_types = [parent_type(LL[0]), parent_type(LL[0].parent)]
1984         if syms.dictsetmaker in parent_types or syms.lambdef in parent_types:
1985             is_valid_index = is_valid_index_factory(LL)
1986
1987             for i, leaf in enumerate(LL):
1988                 # We MUST find a colon, it can either be dict's or lambda's colon...
1989                 if leaf.type == token.COLON and i < len(LL) - 1:
1990                     idx = i + 2 if is_empty_par(LL[i + 1]) else i + 1
1991
1992                     # That colon MUST be followed by a string...
1993                     if is_valid_index(idx) and LL[idx].type == token.STRING:
1994                         string_idx = idx
1995
1996                         # Skip the string trailer, if one exists.
1997                         string_parser = StringParser()
1998                         idx = string_parser.parse(LL, string_idx)
1999
2000                         # That string MAY be followed by a comma...
2001                         if is_valid_index(idx) and LL[idx].type == token.COMMA:
2002                             idx += 1
2003
2004                         # But no more leaves are allowed...
2005                         if not is_valid_index(idx):
2006                             return string_idx
2007
2008         return None
2009
2010     def do_transform(
2011         self, line: Line, string_indices: List[int]
2012     ) -> Iterator[TResult[Line]]:
2013         LL = line.leaves
2014         assert len(string_indices) == 1, (
2015             f"{self.__class__.__name__} should only find one match at a time, found"
2016             f" {len(string_indices)}"
2017         )
2018         string_idx = string_indices[0]
2019
2020         is_valid_index = is_valid_index_factory(LL)
2021         insert_str_child = insert_str_child_factory(LL[string_idx])
2022
2023         comma_idx = -1
2024         ends_with_comma = False
2025         if LL[comma_idx].type == token.COMMA:
2026             ends_with_comma = True
2027
2028         leaves_to_steal_comments_from = [LL[string_idx]]
2029         if ends_with_comma:
2030             leaves_to_steal_comments_from.append(LL[comma_idx])
2031
2032         # --- First Line
2033         first_line = line.clone()
2034         left_leaves = LL[:string_idx]
2035
2036         # We have to remember to account for (possibly invisible) LPAR and RPAR
2037         # leaves that already wrapped the target string. If these leaves do
2038         # exist, we will replace them with our own LPAR and RPAR leaves.
2039         old_parens_exist = False
2040         if left_leaves and left_leaves[-1].type == token.LPAR:
2041             old_parens_exist = True
2042             leaves_to_steal_comments_from.append(left_leaves[-1])
2043             left_leaves.pop()
2044
2045         append_leaves(first_line, line, left_leaves)
2046
2047         lpar_leaf = Leaf(token.LPAR, "(")
2048         if old_parens_exist:
2049             replace_child(LL[string_idx - 1], lpar_leaf)
2050         else:
2051             insert_str_child(lpar_leaf)
2052         first_line.append(lpar_leaf)
2053
2054         # We throw inline comments that were originally to the right of the
2055         # target string to the top line. They will now be shown to the right of
2056         # the LPAR.
2057         for leaf in leaves_to_steal_comments_from:
2058             for comment_leaf in line.comments_after(leaf):
2059                 first_line.append(comment_leaf, preformatted=True)
2060
2061         yield Ok(first_line)
2062
2063         # --- Middle (String) Line
2064         # We only need to yield one (possibly too long) string line, since the
2065         # `StringSplitter` will break it down further if necessary.
2066         string_value = LL[string_idx].value
2067         string_line = Line(
2068             mode=line.mode,
2069             depth=line.depth + 1,
2070             inside_brackets=True,
2071             should_split_rhs=line.should_split_rhs,
2072             magic_trailing_comma=line.magic_trailing_comma,
2073         )
2074         string_leaf = Leaf(token.STRING, string_value)
2075         insert_str_child(string_leaf)
2076         string_line.append(string_leaf)
2077
2078         old_rpar_leaf = None
2079         if is_valid_index(string_idx + 1):
2080             right_leaves = LL[string_idx + 1 :]
2081             if ends_with_comma:
2082                 right_leaves.pop()
2083
2084             if old_parens_exist:
2085                 assert right_leaves and right_leaves[-1].type == token.RPAR, (
2086                     "Apparently, old parentheses do NOT exist?!"
2087                     f" (left_leaves={left_leaves}, right_leaves={right_leaves})"
2088                 )
2089                 old_rpar_leaf = right_leaves.pop()
2090             elif right_leaves and right_leaves[-1].type == token.RPAR:
2091                 # Special case for lambda expressions as dict's value, e.g.:
2092                 #     my_dict = {
2093                 #        "key": lambda x: f"formatted: {x},
2094                 #     }
2095                 # After wrapping the dict's value with parentheses, the string is
2096                 # followed by a RPAR but its opening bracket is lambda's, not
2097                 # the string's:
2098                 #        "key": (lambda x: f"formatted: {x}),
2099                 opening_bracket = right_leaves[-1].opening_bracket
2100                 if opening_bracket is not None and opening_bracket in left_leaves:
2101                     index = left_leaves.index(opening_bracket)
2102                     if (
2103                         index > 0
2104                         and index < len(left_leaves) - 1
2105                         and left_leaves[index - 1].type == token.COLON
2106                         and left_leaves[index + 1].value == "lambda"
2107                     ):
2108                         right_leaves.pop()
2109
2110             append_leaves(string_line, line, right_leaves)
2111
2112         yield Ok(string_line)
2113
2114         # --- Last Line
2115         last_line = line.clone()
2116         last_line.bracket_tracker = first_line.bracket_tracker
2117
2118         new_rpar_leaf = Leaf(token.RPAR, ")")
2119         if old_rpar_leaf is not None:
2120             replace_child(old_rpar_leaf, new_rpar_leaf)
2121         else:
2122             insert_str_child(new_rpar_leaf)
2123         last_line.append(new_rpar_leaf)
2124
2125         # If the target string ended with a comma, we place this comma to the
2126         # right of the RPAR on the last line.
2127         if ends_with_comma:
2128             comma_leaf = Leaf(token.COMMA, ",")
2129             replace_child(LL[comma_idx], comma_leaf)
2130             last_line.append(comma_leaf)
2131
2132         yield Ok(last_line)
2133
2134
2135 class StringParser:
2136     """
2137     A state machine that aids in parsing a string's "trailer", which can be
2138     either non-existent, an old-style formatting sequence (e.g. `% varX` or `%
2139     (varX, varY)`), or a method-call / attribute access (e.g. `.format(varX,
2140     varY)`).
2141
2142     NOTE: A new StringParser object MUST be instantiated for each string
2143     trailer we need to parse.
2144
2145     Examples:
2146         We shall assume that `line` equals the `Line` object that corresponds
2147         to the following line of python code:
2148         ```
2149         x = "Some {}.".format("String") + some_other_string
2150         ```
2151
2152         Furthermore, we will assume that `string_idx` is some index such that:
2153         ```
2154         assert line.leaves[string_idx].value == "Some {}."
2155         ```
2156
2157         The following code snippet then holds:
2158         ```
2159         string_parser = StringParser()
2160         idx = string_parser.parse(line.leaves, string_idx)
2161         assert line.leaves[idx].type == token.PLUS
2162         ```
2163     """
2164
2165     DEFAULT_TOKEN: Final = 20210605
2166
2167     # String Parser States
2168     START: Final = 1
2169     DOT: Final = 2
2170     NAME: Final = 3
2171     PERCENT: Final = 4
2172     SINGLE_FMT_ARG: Final = 5
2173     LPAR: Final = 6
2174     RPAR: Final = 7
2175     DONE: Final = 8
2176
2177     # Lookup Table for Next State
2178     _goto: Final[Dict[Tuple[ParserState, NodeType], ParserState]] = {
2179         # A string trailer may start with '.' OR '%'.
2180         (START, token.DOT): DOT,
2181         (START, token.PERCENT): PERCENT,
2182         (START, DEFAULT_TOKEN): DONE,
2183         # A '.' MUST be followed by an attribute or method name.
2184         (DOT, token.NAME): NAME,
2185         # A method name MUST be followed by an '(', whereas an attribute name
2186         # is the last symbol in the string trailer.
2187         (NAME, token.LPAR): LPAR,
2188         (NAME, DEFAULT_TOKEN): DONE,
2189         # A '%' symbol can be followed by an '(' or a single argument (e.g. a
2190         # string or variable name).
2191         (PERCENT, token.LPAR): LPAR,
2192         (PERCENT, DEFAULT_TOKEN): SINGLE_FMT_ARG,
2193         # If a '%' symbol is followed by a single argument, that argument is
2194         # the last leaf in the string trailer.
2195         (SINGLE_FMT_ARG, DEFAULT_TOKEN): DONE,
2196         # If present, a ')' symbol is the last symbol in a string trailer.
2197         # (NOTE: LPARS and nested RPARS are not included in this lookup table,
2198         # since they are treated as a special case by the parsing logic in this
2199         # classes' implementation.)
2200         (RPAR, DEFAULT_TOKEN): DONE,
2201     }
2202
2203     def __init__(self) -> None:
2204         self._state = self.START
2205         self._unmatched_lpars = 0
2206
2207     def parse(self, leaves: List[Leaf], string_idx: int) -> int:
2208         """
2209         Pre-conditions:
2210             * @leaves[@string_idx].type == token.STRING
2211
2212         Returns:
2213             The index directly after the last leaf which is apart of the string
2214             trailer, if a "trailer" exists.
2215                 OR
2216             @string_idx + 1, if no string "trailer" exists.
2217         """
2218         assert leaves[string_idx].type == token.STRING
2219
2220         idx = string_idx + 1
2221         while idx < len(leaves) and self._next_state(leaves[idx]):
2222             idx += 1
2223         return idx
2224
2225     def _next_state(self, leaf: Leaf) -> bool:
2226         """
2227         Pre-conditions:
2228             * On the first call to this function, @leaf MUST be the leaf that
2229             was directly after the string leaf in question (e.g. if our target
2230             string is `line.leaves[i]` then the first call to this method must
2231             be `line.leaves[i + 1]`).
2232             * On the next call to this function, the leaf parameter passed in
2233             MUST be the leaf directly following @leaf.
2234
2235         Returns:
2236             True iff @leaf is apart of the string's trailer.
2237         """
2238         # We ignore empty LPAR or RPAR leaves.
2239         if is_empty_par(leaf):
2240             return True
2241
2242         next_token = leaf.type
2243         if next_token == token.LPAR:
2244             self._unmatched_lpars += 1
2245
2246         current_state = self._state
2247
2248         # The LPAR parser state is a special case. We will return True until we
2249         # find the matching RPAR token.
2250         if current_state == self.LPAR:
2251             if next_token == token.RPAR:
2252                 self._unmatched_lpars -= 1
2253                 if self._unmatched_lpars == 0:
2254                     self._state = self.RPAR
2255         # Otherwise, we use a lookup table to determine the next state.
2256         else:
2257             # If the lookup table matches the current state to the next
2258             # token, we use the lookup table.
2259             if (current_state, next_token) in self._goto:
2260                 self._state = self._goto[current_state, next_token]
2261             else:
2262                 # Otherwise, we check if a the current state was assigned a
2263                 # default.
2264                 if (current_state, self.DEFAULT_TOKEN) in self._goto:
2265                     self._state = self._goto[current_state, self.DEFAULT_TOKEN]
2266                 # If no default has been assigned, then this parser has a logic
2267                 # error.
2268                 else:
2269                     raise RuntimeError(f"{self.__class__.__name__} LOGIC ERROR!")
2270
2271             if self._state == self.DONE:
2272                 return False
2273
2274         return True
2275
2276
2277 def insert_str_child_factory(string_leaf: Leaf) -> Callable[[LN], None]:
2278     """
2279     Factory for a convenience function that is used to orphan @string_leaf
2280     and then insert multiple new leaves into the same part of the node
2281     structure that @string_leaf had originally occupied.
2282
2283     Examples:
2284         Let `string_leaf = Leaf(token.STRING, '"foo"')` and `N =
2285         string_leaf.parent`. Assume the node `N` has the following
2286         original structure:
2287
2288         Node(
2289             expr_stmt, [
2290                 Leaf(NAME, 'x'),
2291                 Leaf(EQUAL, '='),
2292                 Leaf(STRING, '"foo"'),
2293             ]
2294         )
2295
2296         We then run the code snippet shown below.
2297         ```
2298         insert_str_child = insert_str_child_factory(string_leaf)
2299
2300         lpar = Leaf(token.LPAR, '(')
2301         insert_str_child(lpar)
2302
2303         bar = Leaf(token.STRING, '"bar"')
2304         insert_str_child(bar)
2305
2306         rpar = Leaf(token.RPAR, ')')
2307         insert_str_child(rpar)
2308         ```
2309
2310         After which point, it follows that `string_leaf.parent is None` and
2311         the node `N` now has the following structure:
2312
2313         Node(
2314             expr_stmt, [
2315                 Leaf(NAME, 'x'),
2316                 Leaf(EQUAL, '='),
2317                 Leaf(LPAR, '('),
2318                 Leaf(STRING, '"bar"'),
2319                 Leaf(RPAR, ')'),
2320             ]
2321         )
2322     """
2323     string_parent = string_leaf.parent
2324     string_child_idx = string_leaf.remove()
2325
2326     def insert_str_child(child: LN) -> None:
2327         nonlocal string_child_idx
2328
2329         assert string_parent is not None
2330         assert string_child_idx is not None
2331
2332         string_parent.insert_child(string_child_idx, child)
2333         string_child_idx += 1
2334
2335     return insert_str_child
2336
2337
2338 def is_valid_index_factory(seq: Sequence[Any]) -> Callable[[int], bool]:
2339     """
2340     Examples:
2341         ```
2342         my_list = [1, 2, 3]
2343
2344         is_valid_index = is_valid_index_factory(my_list)
2345
2346         assert is_valid_index(0)
2347         assert is_valid_index(2)
2348
2349         assert not is_valid_index(3)
2350         assert not is_valid_index(-1)
2351         ```
2352     """
2353
2354     def is_valid_index(idx: int) -> bool:
2355         """
2356         Returns:
2357             True iff @idx is positive AND seq[@idx] does NOT raise an
2358             IndexError.
2359         """
2360         return 0 <= idx < len(seq)
2361
2362     return is_valid_index