Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Balance paired characters (*, _, etc) in inline tokens."""
3from __future__ import annotations
5from .state_inline import Delimiter, StateInline
8def processDelimiters(state: StateInline, delimiters: list[Delimiter]) -> None:
9 """For each opening emphasis-like marker find a matching closing one."""
10 if not delimiters:
11 return
13 openersBottom = {}
14 maximum = len(delimiters)
16 # headerIdx is the first delimiter of the current (where closer is) delimiter run
17 headerIdx = 0
18 lastTokenIdx = -2 # needs any value lower than -1
19 jumps: list[int] = []
20 closerIdx = 0
21 while closerIdx < maximum:
22 closer = delimiters[closerIdx]
24 jumps.append(0)
26 # markers belong to same delimiter run if:
27 # - they have adjacent tokens
28 # - AND markers are the same
29 #
30 if (
31 delimiters[headerIdx].marker != closer.marker
32 or lastTokenIdx != closer.token - 1
33 ):
34 headerIdx = closerIdx
35 lastTokenIdx = closer.token
37 # Length is only used for emphasis-specific "rule of 3",
38 # if it's not defined (in strikethrough or 3rd party plugins),
39 # we can default it to 0 to disable those checks.
40 #
41 closer.length = closer.length or 0
43 if not closer.close:
44 closerIdx += 1
45 continue
47 # Previously calculated lower bounds (previous fails)
48 # for each marker, each delimiter length modulo 3,
49 # and for whether this closer can be an opener;
50 # https://github.com/commonmark/cmark/commit/34250e12ccebdc6372b8b49c44fab57c72443460
51 if closer.marker not in openersBottom:
52 openersBottom[closer.marker] = [-1, -1, -1, -1, -1, -1]
54 minOpenerIdx = openersBottom[closer.marker][
55 (3 if closer.open else 0) + (closer.length % 3)
56 ]
58 openerIdx = headerIdx - jumps[headerIdx] - 1
60 newMinOpenerIdx = openerIdx
62 while openerIdx > minOpenerIdx:
63 opener = delimiters[openerIdx]
65 if opener.marker != closer.marker:
66 openerIdx -= jumps[openerIdx] + 1
67 continue
69 if opener.open and opener.end < 0:
70 isOddMatch = False
72 # from spec:
73 #
74 # If one of the delimiters can both open and close emphasis, then the
75 # sum of the lengths of the delimiter runs containing the opening and
76 # closing delimiters must not be a multiple of 3 unless both lengths
77 # are multiples of 3.
78 #
79 if (
80 (opener.close or closer.open)
81 and ((opener.length + closer.length) % 3 == 0)
82 and (opener.length % 3 != 0 or closer.length % 3 != 0)
83 ):
84 isOddMatch = True
86 if not isOddMatch:
87 # If previous delimiter cannot be an opener, we can safely skip
88 # the entire sequence in future checks. This is required to make
89 # sure algorithm has linear complexity (see *_*_*_*_*_... case).
90 #
91 if openerIdx > 0 and not delimiters[openerIdx - 1].open:
92 lastJump = jumps[openerIdx - 1] + 1
93 else:
94 lastJump = 0
96 jumps[closerIdx] = closerIdx - openerIdx + lastJump
97 jumps[openerIdx] = lastJump
99 closer.open = False
100 opener.end = closerIdx
101 opener.close = False
102 newMinOpenerIdx = -1
104 # treat next token as start of run,
105 # it optimizes skips in **<...>**a**<...>** pathological case
106 lastTokenIdx = -2
108 break
110 openerIdx -= jumps[openerIdx] + 1
112 if newMinOpenerIdx != -1:
113 # If match for this delimiter run failed, we want to set lower bound for
114 # future lookups. This is required to make sure algorithm has linear
115 # complexity.
116 #
117 # See details here:
118 # https:#github.com/commonmark/cmark/issues/178#issuecomment-270417442
119 #
120 openersBottom[closer.marker][
121 (3 if closer.open else 0) + ((closer.length or 0) % 3)
122 ] = newMinOpenerIdx
124 closerIdx += 1
127def link_pairs(state: StateInline) -> None:
128 tokens_meta = state.tokens_meta
129 maximum = len(state.tokens_meta)
131 processDelimiters(state, state.delimiters)
133 curr = 0
134 while curr < maximum:
135 curr_meta = tokens_meta[curr]
136 if curr_meta and "delimiters" in curr_meta:
137 processDelimiters(state, curr_meta["delimiters"])
138 curr += 1