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

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