>From b051dbb5f4ccb6ea32b14c4d62d95cdbc277922e Mon Sep 17 00:00:00 2001
From: Szabolcs Nagy <nsz@port70.net>
Date: Sun, 27 Sep 2026 15:56:53 +0000
Subject: [PATCH 21/25] regex: use sorted tags in regcomp

merge_dup was O(n*m) for n and m long inputs, now tag lists are kept
sorted so it is O(n+m).

  ((a|)(a|)(a|)(a|)...)*

is a bad case for long tag merges and with long enough input sorted
merge is faster, common patterns have no measurable difference.

insertion sort is used for the empty match tag collection, this relies
on the sort being in decreasing order (so -1 is sorted to the end).
overall there is no asymptotic slowdown compared to just using appends
everywhere, but more work is done which is justified by smaller tnfa
in some edge cases.
---
 src/regex/regcomp.c | 41 +++++++++++++++++++++++++++--------------
 1 file changed, 27 insertions(+), 14 deletions(-)

diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c
index 52119a38..bde02ccf 100644
--- a/src/regex/regcomp.c
+++ b/src/regex/regcomp.c
@@ -2013,16 +2013,24 @@ tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
   return status;
 }
 
-/* merge s1 and s2 with no dups into out with no dups, returns length of out. */
+/* merge sorted nodup s1, s2 into out, returns length of out. */
 static int merge_nodup(int *out, int *s1, int n1, int *s2, int n2)
 {
-	int i=0, j=0, n=n1, v;
-	for (i=0; i<n1; i++) out[i] = s1[i];
-	for (j=0; j<n2; j++) {
-		v = s2[j];
-		for (i=0; i<n1 && v!=out[i]; i++);
-		if (i==n1)
-			out[n++] = v;
+	int i=0, j=0, n=0;
+	for (;;) {
+		if (i==n1) {
+			while (j<n2) out[n++] = s2[j++];
+			break;
+		}
+		if (j==n2) {
+			while (i<n1) out[n++] = s1[i++];
+			break;
+		}
+		if (s1[i]>=s2[j]) {
+			if (s1[i]==s2[j]) j++; /* skip dup */
+			out[n++] = s1[i++];
+		} else
+			out[n++] = s2[j++];
 	}
 	return n;
 }
@@ -2175,13 +2183,18 @@ tre_match_empty(tre_stack_t *stack, tre_ast_node_t *node, int *tags,
 		{
 		  if (tags != NULL)
 		    {
-		      /* Add the tag to `tags'. */
-		      for (i = 0; tags[i] >= 0; i++)
-			if (tags[i] == lit->code_max)
-			  break;
-		      if (tags[i] < 0)
+		      /* simple sorted insert, skip dups. */
+		      int ins = lit->code_max;
+		      for (i = 0; ins < tags[i]; i++);
+		      if (ins != tags[i])
 			{
-			  tags[i] = lit->code_max;
+			  for (; tags[i] >= 0; i++)
+			    {
+			      int t = tags[i];
+			      tags[i] = ins;
+			      ins = t;
+			    }
+			  tags[i] = ins;
 			  tags[i + 1] = -1;
 			}
 		    }
-- 
2.52.0