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

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