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

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