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

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