Skip to content

Commit ddec203

Browse files
committed
perf: cache search results, limit length
1 parent b4539c4 commit ddec203

5 files changed

Lines changed: 61 additions & 16 deletions

File tree

‎extension/footnote.go‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,9 @@ import (
1818
var footnoteListKey = parser.NewContextKey()
1919
var footnoteLinkListKey = parser.NewContextKey()
2020

21+
// footnoteLabelLimit is the max length of footnote labels. This is the same limit as CommonMark link labels.
22+
const footnoteLabelLimit = 999
23+
2124
type footnoteBlockParser struct {
2225
}
2326

@@ -45,7 +48,7 @@ func (b *footnoteBlockParser) Open(parent gast.Node, reader text.Reader, pc pars
4548
}
4649
open := pos + 1
4750
var closes int
48-
closure := util.FindClosure(line[pos+1:], '[', ']', false, false) //nolint:staticcheck
51+
closure := util.FindClosure(line[pos+1:min(len(line), pos+1+footnoteLabelLimit)], '[', ']', false, false) //nolint:staticcheck
4952
closes = pos + 1 + closure
5053
next := closes + 1
5154
if closure > -1 {
@@ -136,7 +139,7 @@ func (s *footnoteParser) Parse(parent gast.Node, block text.Reader, pc parser.Co
136139
return nil
137140
}
138141
open := pos
139-
closure := util.FindClosure(line[pos:], '[', ']', false, false) //nolint:staticcheck
142+
closure := util.FindClosure(line[pos:min(len(line), pos+footnoteLabelLimit)], '[', ']', false, false) //nolint:staticcheck
140143
if closure < 0 {
141144
return nil
142145
}

‎parser/list.go‎

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@ const (
1717
)
1818

1919
var skipListParserKey = NewContextKey()
20+
var tbCacheKey = NewContextKey()
2021
var emptyListItemWithBlankLines = NewContextKey()
2122
var listItemFlagValue any = true
2223

@@ -156,7 +157,7 @@ func (b *listParser) Open(parent ast.Node, reader text.Reader, pc Context) (ast.
156157

157158
func (b *listParser) Continue(node ast.Node, reader text.Reader, pc Context) State {
158159
list := node.(*ast.List)
159-
line, _ := reader.PeekLine()
160+
line, seg := reader.PeekLine()
160161
if util.IsBlank(line) {
161162
if node.LastChild().ChildCount() == 0 {
162163
pc.Set(emptyListItemWithBlankLines, listItemFlagValue)
@@ -197,7 +198,15 @@ func (b *listParser) Continue(node ast.Node, reader text.Reader, pc Context) Sta
197198
return Close
198199
}
199200
// Thematic Breaks take precedence over lists
200-
if isThematicBreak(line[match[3]-1:], 0) {
201+
tb := pc.ComputeIfAbsent(tbCacheKey, func() any {
202+
return &posCache{}
203+
}).(*posCache)
204+
isTb := false
205+
if seg.Stop > tb.pos {
206+
isTb = isThematicBreak(line[match[3]-1:], 0)
207+
tb.pos = seg.Stop
208+
}
209+
if isTb {
201210
isHeading := false
202211
last := pc.LastOpenedBlock().Node
203212
if ast.IsParagraph(last) {

‎parser/parser.go‎

Lines changed: 13 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -88,11 +88,14 @@ type IDs interface {
8888

8989
type ids struct {
9090
values map[string]bool
91+
// n caches the last suffix number used for each base id.
92+
n map[string]int
9193
}
9294

9395
func newIDs() IDs {
9496
return &ids{
9597
values: map[string]bool{},
98+
n: map[string]int{},
9699
}
97100
}
98101

@@ -123,24 +126,30 @@ func (s *ids) Generate(value []byte, kind ast.NodeKind) []byte {
123126
result = []byte("id")
124127
}
125128
}
126-
if _, ok := s.values[util.BytesToReadOnlyString(result)]; !ok {
127-
s.values[util.BytesToReadOnlyString(result)] = true
129+
key := util.BytesToReadOnlyString(result)
130+
if _, ok := s.values[key]; !ok {
131+
s.values[key] = true
128132
return result
129133
}
130-
for i := 1; ; i++ {
134+
for i := s.n[key] + 1; ; i++ {
131135
newResult := fmt.Sprintf("%s-%d", result, i)
132136
if _, ok := s.values[newResult]; !ok {
133137
s.values[newResult] = true
138+
s.n[key] = i
134139
return []byte(newResult)
135140
}
136-
137141
}
138142
}
139143

140144
func (s *ids) Put(value []byte) {
141145
s.values[util.BytesToReadOnlyString(value)] = true
142146
}
143147

148+
// posCache caches a position at which a search has already failed.
149+
type posCache struct {
150+
pos int
151+
}
152+
144153
// ContextKey is a key that is used to set arbitrary values to the context.
145154
type ContextKey int
146155

‎parser/raw_html.go‎

Lines changed: 27 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -36,17 +36,22 @@ func (s *rawHTMLParser) Parse(parent ast.Node, block text.Reader, pc Context) as
3636
return s.parseComment(block, pc)
3737
}
3838
if bytes.HasPrefix(line, openProcessingInstruction) {
39-
return s.parseUntil(block, closeProcessingInstruction, pc)
39+
return s.parseUntil(block, closeProcessingInstruction, closeProcessingInstructionCacheKey, pc)
4040
}
4141
if len(line) > 2 && line[1] == '!' && line[2] >= 'A' && line[2] <= 'Z' {
42-
return s.parseUntil(block, closeDecl, pc)
42+
return s.parseUntil(block, closeDecl, closeDeclCacheKey, pc)
4343
}
4444
if bytes.HasPrefix(line, openCDATA) {
45-
return s.parseUntil(block, closeCDATA, pc)
45+
return s.parseUntil(block, closeCDATA, closeCDATACacheKey, pc)
4646
}
4747
return nil
4848
}
4949

50+
var closeProcessingInstructionCacheKey = NewContextKey()
51+
var closeDeclCacheKey = NewContextKey()
52+
var closeCDATACacheKey = NewContextKey()
53+
var closeCommentCacheKey = NewContextKey()
54+
5055
var tagnamePattern = `([A-Za-z][A-Za-z0-9-]*)`
5156
var spaceOrOneNewline = `(?:[ \t]|(?:\r\n|\n){0,1})`
5257
var attributePattern = `(?:[\r\n \t]+[a-zA-Z_:][a-zA-Z0-9:._-]*(?:[\r\n \t]*=[\r\n \t]*(?:[^\"'=<>` + "`" + `\x00-\x20]+|'[^']*'|"[^"]*"))?)` //nolint:golint,lll
@@ -63,7 +68,7 @@ var emptyComment2 = []byte("<!--->")
6368
var openComment = []byte("<!--")
6469
var closeComment = []byte("-->")
6570

66-
func (s *rawHTMLParser) parseComment(block text.Reader, _ Context) ast.Node {
71+
func (s *rawHTMLParser) parseComment(block text.Reader, pc Context) ast.Node {
6772
savedLine, savedSegment := block.Position()
6873
node := ast.NewRawHTML()
6974
line, segment := block.PeekLine()
@@ -77,8 +82,14 @@ func (s *rawHTMLParser) parseComment(block text.Reader, _ Context) ast.Node {
7782
block.Advance(len(emptyComment2))
7883
return node
7984
}
85+
// A previous search failed up to cache.pos, so there is no closer before it.
86+
cache := pc.ComputeIfAbsent(closeCommentCacheKey, func() any { return &posCache{} }).(*posCache)
87+
if segment.Start < cache.pos {
88+
return nil
89+
}
8090
offset := len(openComment)
8191
line = line[offset:]
92+
lastStop := segment.Stop
8293
for {
8394
index := bytes.Index(line, closeComment)
8495
if index > -1 {
@@ -88,33 +99,44 @@ func (s *rawHTMLParser) parseComment(block text.Reader, _ Context) ast.Node {
8899
}
89100
offset = 0
90101
node.Segments.Append(segment)
102+
lastStop = segment.Stop
91103
block.AdvanceLine()
92104
line, segment = block.PeekLine()
93105
if line == nil {
94106
break
95107
}
96108
}
109+
cache.pos = lastStop
97110
block.SetPosition(savedLine, savedSegment)
98111
return nil
99112
}
100113

101-
func (s *rawHTMLParser) parseUntil(block text.Reader, closer []byte, _ Context) ast.Node {
114+
func (s *rawHTMLParser) parseUntil(block text.Reader, closer []byte, ck ContextKey, pc Context) ast.Node {
102115
savedLine, savedSegment := block.Position()
103116
node := ast.NewRawHTML()
117+
// A previous search failed up to cache.pos, so there is no closer before it.
118+
cache := pc.ComputeIfAbsent(ck, func() any { return &posCache{} }).(*posCache)
119+
lastStop := 0
104120
for {
105121
line, segment := block.PeekLine()
106122
if line == nil {
107123
break
108124
}
125+
if segment.Start < cache.pos {
126+
block.SetPosition(savedLine, savedSegment)
127+
return nil
128+
}
109129
index := bytes.Index(line, closer)
110130
if index > -1 {
111131
node.Segments.Append(segment.WithStop(segment.Start + index + len(closer)))
112132
block.Advance(index + len(closer))
113133
return node
114134
}
115135
node.Segments.Append(segment)
136+
lastStop = segment.Stop
116137
block.AdvanceLine()
117138
}
139+
cache.pos = lastStop
118140
block.SetPosition(savedLine, savedSegment)
119141
return nil
120142
}

‎util/util.go‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -764,7 +764,8 @@ var emailDomainRegexp = regexp.MustCompile(`^[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-
764764
func FindEmailIndex(b []byte) int {
765765
// TODO: eliminate regexps
766766
i := 0
767-
for ; i < len(b); i++ {
767+
lim := min(len(b), 64)
768+
for ; i < lim; i++ {
768769
c := b[i]
769770
if emailTable[c]&1 != 1 {
770771
break
@@ -780,8 +781,9 @@ func FindEmailIndex(b []byte) int {
780781
if i >= len(b) {
781782
return -1
782783
}
783-
match := emailDomainRegexp.FindSubmatchIndex(b[i:])
784-
if match == nil {
784+
// domain names are at most 255 bytes long
785+
match := emailDomainRegexp.FindSubmatchIndex(b[i:min(len(b), i+256)])
786+
if match == nil || match[1] > 255 {
785787
return -1
786788
}
787789
return i + match[1]

0 commit comments

Comments
 (0)