Skip to content

Commit 08be507

Browse files
rolandshoemakergopherbot
authored andcommitted
html: improve Noah's Ark clause performance
Instead of iterating over each element in the stack, and checking each attribute against each other attribute in a ~cubic fashion, sort the attributes and just use slices.Equal. Thanks to IPC Labs for reporting this issue. Fixes CVE-2026-25680 Change-Id: Iec3513ba0b5da4f28f1359d24846401b9ab76ee3 Reviewed-on: https://go-review.googlesource.com/c/net/+/781702 TryBot-Bypass: Roland Shoemaker <[email protected]> Reviewed-by: Nicholas Husin <[email protected]> Reviewed-by: Neal Patel <[email protected]> Reviewed-by: Nicholas Husin <[email protected]> Auto-Submit: Gopher Robot <[email protected]>
1 parent a8fb2fe commit 08be507

1 file changed

Lines changed: 20 additions & 14 deletions

File tree

‎html/parse.go‎

Lines changed: 20 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -5,9 +5,11 @@
55
package html
66

77
import (
8+
"cmp"
89
"errors"
910
"fmt"
1011
"io"
12+
"slices"
1113
"strings"
1214

1315
a "golang.org/x/net/html/atom"
@@ -328,6 +330,14 @@ func (p *parser) addText(text string) {
328330
})
329331
}
330332

333+
func attrCompare(a, b Attribute) int {
334+
return cmp.Or(
335+
cmp.Compare(a.Namespace, b.Namespace),
336+
cmp.Compare(a.Key, b.Key),
337+
cmp.Compare(a.Val, b.Val),
338+
)
339+
}
340+
331341
// addElement adds a child element based on the current token.
332342
func (p *parser) addElement() {
333343
p.addChild(&Node{
@@ -343,6 +353,10 @@ func (p *parser) addFormattingElement() {
343353
tagAtom, attr := p.tok.DataAtom, p.tok.Attr
344354
p.addElement()
345355

356+
// In order to optimize the search, we need the attributes to be sorted, so we
357+
// can just use slices.Equal.
358+
slices.SortFunc(attr, attrCompare)
359+
346360
// Implement the Noah's Ark clause, but with three per family instead of two.
347361
identicalElements := 0
348362
findIdenticalElements:
@@ -360,19 +374,7 @@ findIdenticalElements:
360374
if n.DataAtom != tagAtom {
361375
continue
362376
}
363-
if len(n.Attr) != len(attr) {
364-
continue
365-
}
366-
compareAttributes:
367-
for _, t0 := range n.Attr {
368-
for _, t1 := range attr {
369-
if t0.Key == t1.Key && t0.Namespace == t1.Namespace && t0.Val == t1.Val {
370-
// Found a match for this attribute, continue with the next attribute.
371-
continue compareAttributes
372-
}
373-
}
374-
// If we get here, there is no attribute that matches a.
375-
// Therefore the element is not identical to the new one.
377+
if !slices.Equal(n.Attr, attr) {
376378
continue findIdenticalElements
377379
}
378380

@@ -382,7 +384,11 @@ findIdenticalElements:
382384
}
383385
}
384386

385-
p.afe = append(p.afe, p.top())
387+
// Sort the attributes to optimize future identical-element searches.
388+
top := p.top()
389+
slices.SortFunc(top.Attr, attrCompare)
390+
391+
p.afe = append(p.afe, top)
386392
}
387393

388394
// Section 12.2.4.3.

0 commit comments

Comments
 (0)