From 632fee7cdfcd234a5c7c53f17777ca18e62d82e3 Mon Sep 17 00:00:00 2001 From: Oliver Kiddle Date: Sat, 30 Oct 2021 23:27:29 +0200 Subject: 49528: allow multiple -D options to compadd --- Src/Zle/comp.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'Src/Zle/comp.h') diff --git a/Src/Zle/comp.h b/Src/Zle/comp.h index 2e3249b52..0c5fbd4f0 100644 --- a/Src/Zle/comp.h +++ b/Src/Zle/comp.h @@ -329,7 +329,7 @@ struct cadata { char *exp; /* explanation (-X) */ char *apar; /* array to store matches in (-A) */ char *opar; /* array to store originals in (-O) */ - char *dpar; /* array to delete non-matches in (-D) */ + char **dpar; /* arrays to delete non-matches in (-D) */ char *disp; /* array with display lists (-d) */ char *mesg; /* message to show unconditionally (-x) */ int dummies; /* add that many dummy matches */ -- cgit v1.2.3 From 48be30e530a6786f1d47a3dd79f4b6eef2967639 Mon Sep 17 00:00:00 2001 From: Mikael Magnusson Date: Fri, 25 Mar 2022 23:57:30 +0100 Subject: 49893: Fix comments for UNIQCON/ALL --- ChangeLog | 5 +++++ Src/Zle/comp.h | 6 +++--- Src/Zle/compcore.c | 8 +++++++- 3 files changed, 15 insertions(+), 4 deletions(-) (limited to 'Src/Zle/comp.h') diff --git a/ChangeLog b/ChangeLog index 27bbdc4a0..96f0dc719 100644 --- a/ChangeLog +++ b/ChangeLog @@ -5,6 +5,11 @@ * 49908: Test/ztst.zsh: reset LC_CTYPE to C during tests. +2022-03-30 Mikael Magnusson + + * 49893: Src/Zle/comp.h, Src/Zle/compcore.c: Fix comments for + UNIQCON/ALL + 2022-03-29 Bart Schaefer * 49918: NEWS, README: Update for 49917 and 49911. diff --git a/Src/Zle/comp.h b/Src/Zle/comp.h index 0c5fbd4f0..a8480c2ba 100644 --- a/Src/Zle/comp.h +++ b/Src/Zle/comp.h @@ -85,8 +85,8 @@ struct cmgroup { #define CGF_NOSORT 1 /* don't sort this group */ #define CGF_LINES 2 /* these are to be printed on different lines */ #define CGF_HASDL 4 /* has display strings printed on separate lines */ -#define CGF_UNIQALL 8 /* remove all duplicates */ -#define CGF_UNIQCON 16 /* remove consecutive duplicates */ +#define CGF_UNIQALL 8 /* remove consecutive duplicates (if neither are set, */ +#define CGF_UNIQCON 16 /* don't deduplicate */ /* remove all dupes) */ #define CGF_PACKED 32 /* LIST_PACKED for this group */ #define CGF_ROWS 64 /* LIST_ROWS_FIRST for this group */ #define CGF_FILES 128 /* contains file names */ @@ -299,7 +299,7 @@ struct menuinfo { #define CAF_NOSORT 2 /* compadd -V: don't sort */ #define CAF_MATCH 4 /* compadd without -U: do matching */ #define CAF_UNIQCON 8 /* compadd -2: don't deduplicate */ -#define CAF_UNIQALL 16 /* compadd -1: deduplicate */ +#define CAF_UNIQALL 16 /* compadd -1: deduplicate consecutive only */ #define CAF_ARRAYS 32 /* compadd -a or -k: array/assoc parameter names */ #define CAF_KEYS 64 /* compadd -k: assoc parameter names */ #define CAF_ALL 128 /* compadd -C: _all_matches */ diff --git a/Src/Zle/compcore.c b/Src/Zle/compcore.c index c6deff756..a9ace5587 100644 --- a/Src/Zle/compcore.c +++ b/Src/Zle/compcore.c @@ -3254,10 +3254,13 @@ makearray(LinkList l, int type, int flags, int *np, int *nlp, int *llp) qsort((void *) rp, n, sizeof(Cmatch), (int (*) _((const void *, const void *)))matchcmp); + /* since the matches are sorted and the default is to remove + * all duplicates, -1 (remove only consecutive dupes) is a no-op, + * so this condition only checks for -2 */ if (!(flags & CGF_UNIQCON)) { int dup; - /* And delete the ones that occur more than once. */ + /* we did not pass -2 so go ahead and remove those dupes */ for (ap = cp = rp; *ap; ap++) { *cp++ = *ap; for (bp = ap; bp[1] && matcheq(*ap, bp[1]); bp++, n--); @@ -3279,7 +3282,9 @@ makearray(LinkList l, int type, int flags, int *np, int *nlp, int *llp) if ((*ap)->flags & (CMF_NOLIST | CMF_MULT)) nl++; } + /* used -O nosort or -V, don't sort */ } else { + /* didn't use -1 or -2, so remove all duplicates (inefficient) */ if (!(flags & CGF_UNIQALL) && !(flags & CGF_UNIQCON)) { int dup; @@ -3303,6 +3308,7 @@ makearray(LinkList l, int type, int flags, int *np, int *nlp, int *llp) (*ap)->flags |= CMF_FMULT; } } + /* passed -1 but not -2, so remove consecutive duplicates (efficient) */ } else if (!(flags & CGF_UNIQCON)) { int dup; -- cgit v1.2.3 From 6a9b3bb290abc1f9427f6574d9b12ec00108f907 Mon Sep 17 00:00:00 2001 From: Mikael Magnusson Date: Sat, 26 Mar 2022 02:34:31 +0100 Subject: 49915: Efficient dedup for unsorted completions --- ChangeLog | 3 +++ Src/Zle/comp.h | 1 + Src/Zle/compcore.c | 54 ++++++++++++++++++++++++++++++++++-------------------- 3 files changed, 38 insertions(+), 20 deletions(-) (limited to 'Src/Zle/comp.h') diff --git a/ChangeLog b/ChangeLog index 96f0dc719..4b02f3bc8 100644 --- a/ChangeLog +++ b/ChangeLog @@ -10,6 +10,9 @@ * 49893: Src/Zle/comp.h, Src/Zle/compcore.c: Fix comments for UNIQCON/ALL + * 49915: Src/Zle/comp.h, Src/Zle/compcore.c: Efficient dedup + for unsorted completions + 2022-03-29 Bart Schaefer * 49918: NEWS, README: Update for 49917 and 49911. 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 v1.2.3