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 <roland@golang.org>
Reviewed-by: Nicholas Husin <nsh@golang.org>
Reviewed-by: Neal Patel <nealpatel@google.com>
Reviewed-by: Nicholas Husin <husin@google.com>
Auto-Submit: Gopher Robot <gobot@golang.org>

html/parse.go

diff --git a/html/parse.go b/html/parse.go
index 70a6335..b3d2a25 100644
--- a/html/parse.go
+++ b/html/parse.go
@@ -5,9 +5,11 @@
 package html
 
 import (
+	"cmp"
 	"errors"
 	"fmt"
 	"io"
+	"slices"
 	"strings"
 
 	a "golang.org/x/net/html/atom"
@@ -328,6 +330,14 @@
 	})
 }
 
+func attrCompare(a, b Attribute) int {
+	return cmp.Or(
+		cmp.Compare(a.Namespace, b.Namespace),
+		cmp.Compare(a.Key, b.Key),
+		cmp.Compare(a.Val, b.Val),
+	)
+}
+
 // addElement adds a child element based on the current token.
 func (p *parser) addElement() {
 	p.addChild(&Node{
@@ -343,6 +353,10 @@
 	tagAtom, attr := p.tok.DataAtom, p.tok.Attr
 	p.addElement()
 
+	// In order to optimize the search, we need the attributes to be sorted, so we
+	// can just use slices.Equal.
+	slices.SortFunc(attr, attrCompare)
+
 	// Implement the Noah's Ark clause, but with three per family instead of two.
 	identicalElements := 0
 findIdenticalElements:
@@ -360,19 +374,7 @@
 		if n.DataAtom != tagAtom {
 			continue
 		}
-		if len(n.Attr) != len(attr) {
-			continue
-		}
-	compareAttributes:
-		for _, t0 := range n.Attr {
-			for _, t1 := range attr {
-				if t0.Key == t1.Key && t0.Namespace == t1.Namespace && t0.Val == t1.Val {
-					// Found a match for this attribute, continue with the next attribute.
-					continue compareAttributes
-				}
-			}
-			// If we get here, there is no attribute that matches a.
-			// Therefore the element is not identical to the new one.
+		if !slices.Equal(n.Attr, attr) {
 			continue findIdenticalElements
 		}
 
@@ -382,7 +384,11 @@
 		}
 	}
 
-	p.afe = append(p.afe, p.top())
+	// Sort the attributes to optimize future identical-element searches.
+	top := p.top()
+	slices.SortFunc(top.Attr, attrCompare)
+
+	p.afe = append(p.afe, top)
 }
 
 // Section 12.2.4.3.