Skip to content

Commit 4af4fce

Browse files
committed
html: avoid quadratic complexity when coalescing text nodes
When coalescing adjacent text nodes in addText and fosterParent, appending to an existing TextNode's Data via string concatenation (n.Data += text) reallocated and copied the accumulated string on every token. Inputs containing many short text runs separated by ignored end tags (such as "a</x>") caused O(n^2) allocations and byte copies. Accumulate coalesced text in per-node byte slices during parsing and materialize Data strings once at the end of parse. Thanks to Markus Magnuson for reporting this issue. Fixes CVE-2026-78661 Fixes golang/go#82224 Change-Id: I4cd61a235d0cc14567e8edd3e4ce851999de7731 Reviewed-on: https://go-review.googlesource.com/c/net/+/849365 Reviewed-by: Nicholas Husin <[email protected]> Reviewed-by: Nicholas Husin <[email protected]> LUCI-TryBot-Result: [email protected] <[email protected]>
1 parent 7e56200 commit 4af4fce

2 files changed

Lines changed: 57 additions & 2 deletions

File tree

‎html/parse.go‎

Lines changed: 21 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -51,6 +51,9 @@ type parser struct {
5151
// context is the context element when parsing an HTML fragment
5252
// (section 12.4).
5353
context *Node
54+
// textNodes holds buffers for TextNodes that have had multiple text
55+
// tokens coalesced into them.
56+
textNodes map[*Node][]byte
5457
}
5558

5659
func (p *parser) top() *Node {
@@ -292,7 +295,7 @@ func (p *parser) fosterParent(n *Node) {
292295
prev = parent.LastChild
293296
}
294297
if prev != nil && prev.Type == TextNode && n.Type == TextNode {
295-
prev.Data += n.Data
298+
p.appendText(prev, n.Data)
296299
return
297300
}
298301

@@ -316,7 +319,7 @@ func (p *parser) addText(text string) {
316319

317320
t := p.top()
318321
if n := t.LastChild; n != nil && n.Type == TextNode {
319-
n.Data += text
322+
p.appendText(n, text)
320323
return
321324
}
322325
p.addChild(&Node{
@@ -325,6 +328,18 @@ func (p *parser) addText(text string) {
325328
})
326329
}
327330

331+
func (p *parser) appendText(n *Node, text string) {
332+
if p.textNodes == nil {
333+
p.textNodes = make(map[*Node][]byte)
334+
}
335+
b, ok := p.textNodes[n]
336+
if !ok {
337+
b = []byte(n.Data)
338+
n.Data = ""
339+
}
340+
p.textNodes[n] = append(b, text...)
341+
}
342+
328343
func attrCompare(a, b Attribute) int {
329344
return cmp.Or(
330345
cmp.Compare(a.Namespace, b.Namespace),
@@ -2242,6 +2257,10 @@ func (p *parser) parse() (err error) {
22422257
}
22432258
p.parseCurrentToken()
22442259
}
2260+
for n, b := range p.textNodes {
2261+
n.Data = string(b)
2262+
}
2263+
p.textNodes = nil
22452264
return nil
22462265
}
22472266

‎html/parse_test.go‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -546,3 +546,39 @@ func TestDepthLimit(t *testing.T) {
546546
})
547547
}
548548
}
549+
550+
func TestTextNodeCoalescing(t *testing.T) {
551+
const n = 10000
552+
for _, tc := range []struct {
553+
name string
554+
input string
555+
}{
556+
{"body", strings.Repeat("a</x>", n)},
557+
{"foster", "<table>" + strings.Repeat("a</x>", n)},
558+
} {
559+
t.Run(tc.name, func(t *testing.T) {
560+
var m1, m2 runtime.MemStats
561+
runtime.GC()
562+
runtime.ReadMemStats(&m1)
563+
doc, err := Parse(strings.NewReader(tc.input))
564+
if err != nil {
565+
t.Fatalf("unexpected error: %v", err)
566+
}
567+
runtime.ReadMemStats(&m2)
568+
569+
body := doc.FirstChild.LastChild
570+
text := body.FirstChild
571+
if text == nil || text.Type != TextNode {
572+
t.Fatalf("got first child %v, want TextNode", text)
573+
}
574+
if len(text.Data) != n {
575+
t.Errorf("got text length %d, want %d", len(text.Data), n)
576+
}
577+
578+
// Coalescing n 1-byte text tokens should not require O(n^2) memory.
579+
if alloc := m2.TotalAlloc - m1.TotalAlloc; alloc > 5<<20 {
580+
t.Errorf("Parse allocated %d bytes, want <= %d", alloc, 5<<20)
581+
}
582+
})
583+
}
584+
}

0 commit comments

Comments
 (0)