/
balance_pairs.py
105 lines (81 loc) · 3.62 KB
/
balance_pairs.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# For each opening emphasis-like marker find a matching closing one
#
from .state_inline import StateInline
def processDelimiters(state: StateInline, delimiters, *args):
openersBottom = {}
maximum = len(delimiters)
closerIdx = 0
while closerIdx < maximum:
closer = delimiters[closerIdx]
# Length is only used for emphasis-specific "rule of 3",
# if it's not defined (in strikethrough or 3rd party plugins),
# we can default it to 0 to disable those checks.
#
closer.length = closer.length or 0
if not closer.close:
closerIdx += 1
continue
# Previously calculated lower bounds (previous fails)
# for each marker and each delimiter length modulo 3.
if closer.marker not in openersBottom:
openersBottom[closer.marker] = [-1, -1, -1]
minOpenerIdx = openersBottom[closer.marker][closer.length % 3]
newMinOpenerIdx = -1
openerIdx = closerIdx - closer.jump - 1
while openerIdx > minOpenerIdx:
opener = delimiters[openerIdx]
if opener.marker != closer.marker:
openerIdx -= opener.jump + 1
continue
if newMinOpenerIdx == -1:
newMinOpenerIdx = openerIdx
if opener.open and opener.end < 0:
isOddMatch = False
# from spec:
#
# If one of the delimiters can both open and close emphasis, then the
# sum of the lengths of the delimiter runs containing the opening and
# closing delimiters must not be a multiple of 3 unless both lengths
# are multiples of 3.
#
if opener.close or closer.open:
if (opener.length + closer.length) % 3 == 0:
if opener.length % 3 != 0 or closer.length % 3 != 0:
isOddMatch = True
if not isOddMatch:
# If previous delimiter cannot be an opener, we can safely skip
# the entire sequence in future checks. This is required to make
# sure algorithm has linear complexity (see *_*_*_*_*_... case).
#
if openerIdx > 0 and not delimiters[openerIdx - 1].open:
lastJump = delimiters[openerIdx - 1].jump + 1
else:
lastJump = 0
closer.jump = closerIdx - openerIdx + lastJump
closer.open = False
opener.end = closerIdx
opener.jump = lastJump
opener.close = False
newMinOpenerIdx = -1
break
openerIdx -= opener.jump + 1
if newMinOpenerIdx != -1:
# If match for this delimiter run failed, we want to set lower bound for
# future lookups. This is required to make sure algorithm has linear
# complexity.
#
# See details here:
# https:#github.com/commonmark/cmark/issues/178#issuecomment-270417442
#
openersBottom[closer.marker][(closer.length or 0) % 3] = newMinOpenerIdx
closerIdx += 1
def link_pairs(state: StateInline) -> None:
tokens_meta = state.tokens_meta
maximum = len(state.tokens_meta)
processDelimiters(state, state.delimiters)
curr = 0
while curr < maximum:
curr_meta = tokens_meta[curr]
if curr_meta and "delimiters" in curr_meta:
processDelimiters(state, curr_meta["delimiters"])
curr += 1