From 6a9b3bb290abc1f9427f6574d9b12ec00108f907 Mon Sep 17 00:00:00 2001
From: Mikael Magnusson <mikachu@gmail.com>
Date: Sat, 26 Mar 2022 02:34:31 +0100
Subject: 49915: Efficient dedup for unsorted completions

---
 Src/Zle/comp.h     |  1 +
 Src/Zle/compcore.c | 54 ++++++++++++++++++++++++++++++++++--------------------
 2 files changed, 35 insertions(+), 20 deletions(-)

(limited to 'Src/Zle')

diff --git a/Src/Zle/comp.h b/Src/Zle/comp.h
index a8480c2ba..2ca779fe5 100644
--- a/Src/Zle/comp.h
+++ b/Src/Zle/comp.h
@@ -140,6 +140,7 @@ struct cmatch {
 #define CMF_ALL      (1<<13)	/* a match representing all other matches */
 #define CMF_DUMMY    (1<<14)	/* unselectable dummy match */
 #define CMF_MORDER   (1<<15)    /* order by matches, not display strings */
+#define CMF_DELETE   (1<<16)    /* used for deduplication of unsorted matches, don't set */
 
 /* Stuff for completion matcher control. */
 
diff --git a/Src/Zle/compcore.c b/Src/Zle/compcore.c
index a9ace5587..0b5b22a30 100644
--- a/Src/Zle/compcore.c
+++ b/Src/Zle/compcore.c
@@ -3284,30 +3284,44 @@ makearray(LinkList l, int type, int flags, int *np, int *nlp, int *llp)
 	    }
 	/* used -O nosort or -V, don't sort */
 	} else {
-	    /* didn't use -1 or -2, so remove all duplicates (inefficient) */
+	    /* didn't use -1 or -2, so remove all duplicates (efficient) */
 	    if (!(flags & CGF_UNIQALL) && !(flags & CGF_UNIQCON)) {
-                int dup;
-
-		for (ap = rp; *ap; ap++) {
-		    for (bp = cp = ap + 1; *bp; bp++) {
-			if (!matcheq(*ap, *bp))
-			    *cp++ = *bp;
-			else
+                int dup, i, del = 0;
+
+		/* To avoid O(n^2) here, sort a copy of the list, then remove marked elements */
+		matchorder = flags;
+		Cmatch *sp, *asp;
+		sp = (Cmatch *) zhalloc((n + 1) * sizeof(Cmatch));
+		memcpy(sp, rp, (n + 1) * sizeof(Cmatch));
+		qsort((void *) sp, n, sizeof(Cmatch),
+		      (int (*) _((const void *, const void *)))matchcmp);
+		for (asp = sp + 1; *asp; asp++) {
+		    Cmatch *ap = asp - 1, *bp = asp;
+		    if (matcheq(*ap, *bp)) {
+			bp[0]->flags = CMF_DELETE;
+			del = 1;
+		    } else if (!ap[0]->disp) {
+			/* Mark those, that would show the same string in the list. */
+			for (dup = 0; bp[0] && !(bp[0])->disp &&
+				 !strcmp((*ap)->str, (bp[0])->str); bp = ++sp) {
+			    (bp[0])->flags |= CMF_MULT;
+			    dup = 1;
+			}
+			if (dup)
+			    (*ap)->flags |= CMF_FMULT;
+		    }
+		}
+		if (del) {
+		    int n_orig = n;
+		    for (bp = rp, ap = rp; bp < rp + n_orig; ap++, bp++) {
+			while (bp[0]->flags & CMF_DELETE) {
+			    bp++;
 			    n--;
+			}
+			*ap = *bp;
 		    }
-		    *cp = NULL;
-                    if (!(*ap)->disp) {
-                        for (dup = 0, bp = ap + 1; *bp; bp++)
-                            if (!(*bp)->disp &&
-                                !((*bp)->flags & CMF_MULT) &&
-                                !strcmp((*ap)->str, (*bp)->str)) {
-                                (*bp)->flags |= CMF_MULT;
-                                dup = 1;
-                            }
-                        if (dup)
-                            (*ap)->flags |= CMF_FMULT;
-                    }
 		}
+		*ap = NULL;
 	    /* passed -1 but not -2, so remove consecutive duplicates (efficient) */
 	    } else if (!(flags & CGF_UNIQCON)) {
 		int dup;
-- 
cgit 1.4.1