new widget copy-prev-shell-word, like copy-prev-word but uses shell parsing to find word (10685)

4 files changed, 1039 insertions, 430 deletions

diff --git a/Src/Modules/parameter.c b/Src/Modules/parameter.c
index 6bfe43479..bc8918e0f 100644
--- a/Src/Modules/parameter.c
+++ b/Src/Modules/parameter.c
@@ -1093,11 +1093,15 @@ static char **
 histwgetfn(Param pm)
 {
     char **ret, **p, *h, *e, sav;
-    LinkList l = newlinklist();
+    LinkList l = newlinklist(), ll;
     LinkNode n;
     int i = addhistnum(curhist, -1, HIST_FOREIGN), iw;
     Histent he = quietgethistent(i, GETHIST_UPWARD);
 
+    ll = bufferwords(NULL);
+    for (n = firstnode(ll); n; incnode(n))
+	pushnode(l, getdata(n));
+
     while (he) {
 	for (iw = he->nwords - 1; iw >= 0; iw--) {
 	    h = he->text + he->words[iw * 2];
diff --git a/Src/Zle/iwidgets.list b/Src/Zle/iwidgets.list
index 33d36a18c..da5bcc531 100644
--- a/Src/Zle/iwidgets.list
+++ b/Src/Zle/iwidgets.list
@@ -28,6 +28,7 @@
 "clear-screen", clearscreen, ZLE_MENUCMP | ZLE_KEEPSUFFIX | ZLE_LASTCOL | ZLE_NOTCOMMAND
 "complete-word", completeword, ZLE_MENUCMP | ZLE_KEEPSUFFIX | ZLE_ISCOMP
 "copy-prev-word", copyprevword, ZLE_KEEPSUFFIX
+"copy-prev-shell-word", copyprevshellword, ZLE_KEEPSUFFIX
 "copy-region-as-kill", copyregionaskill, ZLE_KEEPSUFFIX
 "delete-char", deletechar, ZLE_KEEPSUFFIX
 "delete-char-or-list", deletecharorlist, ZLE_MENUCMP | ZLE_KEEPSUFFIX | ZLE_ISCOMP
diff --git a/Src/Zle/zle_misc.c b/Src/Zle/zle_misc.c
index 42953852f..a6adcc4fd 100644
--- a/Src/Zle/zle_misc.c
+++ b/Src/Zle/zle_misc.c
@@ -42,7 +42,7 @@ doinsert(char *str)
     int neg = zmult < 0;             /* insert *after* the cursor? */
     int m = neg ? -zmult : zmult;    /* number of copies to insert */
 
-    iremovesuffix(c1);
+    iremovesuffix(c1, 0);
     invalidatelist();
 
     if(insmode)
@@ -57,8 +57,8 @@ doinsert(char *str)
 }
 
 /**/
-void
-selfinsert(void)
+int
+selfinsert(char **args)
 {
     char s[3], *p = s;
 
@@ -69,56 +69,61 @@ selfinsert(void)
     *p++ = c;
     *p = 0;
     doinsert(s);
+    return 0;
 }
 
 /**/
-void
-selfinsertunmeta(void)
+int
+selfinsertunmeta(char **args)
 {
     c &= 0x7f;
     if (c == '\r')
 	c = '\n';
-    selfinsert();
+    return selfinsert(args);
 }
 
 /**/
-void
-deletechar(void)
+int
+deletechar(char **args)
 {
     if (zmult < 0) {
+	int ret;
 	zmult = -zmult;
-	backwarddeletechar();
+	ret = backwarddeletechar(args);
 	zmult = -zmult;
-	return;
+	return ret;
     }
     if (cs + zmult <= ll) {
 	cs += zmult;
 	backdel(zmult);
-    } else
-	feep();
+	return 0;
+    }
+    return 1;
 }
 
 /**/
-void
-backwarddeletechar(void)
+int
+backwarddeletechar(char **args)
 {
     if (zmult < 0) {
+	int ret;
 	zmult = -zmult;
-	deletechar();
+	ret = deletechar(args);
 	zmult = -zmult;
-	return;
+	return ret;
     }
     backdel(zmult > cs ? cs : zmult);
+    return 0;
 }
 
 /**/
-void
-killwholeline(void)
+int
+killwholeline(char **args)
 {
     int i, fg, n = zmult;
 
     if (n < 0)
-	return;
+	return 1;
     while (n--) {
 	if ((fg = (cs && cs == ll)))
 	    cs--;
@@ -127,27 +132,32 @@ killwholeline(void)
 	for (i = cs; i != ll && line[i] != '\n'; i++);
 	forekill(i - cs + (i != ll), fg);
     }
+    clearlist = 1;
+    return 0;
 }
 
 /**/
-void
-killbuffer(void)
+int
+killbuffer(char **args)
 {
     cs = 0;
     forekill(ll, 0);
+    clearlist = 1;
+    return 0;
 }
 
 /**/
-void
-backwardkillline(void)
+int
+backwardkillline(char **args)
 {
     int i = 0, n = zmult;
 
     if (n < 0) {
+	int ret;
 	zmult = -n;
-	killline();
+	ret = killline(args);
 	zmult = n;
-	return;
+	return ret;
     }
     while (n--) {
 	if (cs && line[cs - 1] == '\n')
@@ -157,11 +167,13 @@ backwardkillline(void)
 		cs--, i++;
     }
     forekill(i, 1);
+    clearlist = 1;
+    return 0;
 }
 
 /**/
-void
-gosmacstransposechars(void)
+int
+gosmacstransposechars(char **args)
 {
     int cc;
 
@@ -169,19 +181,19 @@ gosmacstransposechars(void)
 	if (cs == ll || line[cs] == '\n' ||
 	    ((cs + 1 == ll || line[cs + 1] == '\n') &&
 	     (!cs || line[cs - 1] == '\n'))) {
-	    feep();
-	    return;
+	    return 1;
 	}
 	cs += (cs == 0 || line[cs - 1] == '\n') ? 2 : 1;
     }
     cc = line[cs - 2];
     line[cs - 2] = line[cs - 1];
     line[cs - 1] = cc;
+    return 0;
 }
 
 /**/
-void
-transposechars(void)
+int
+transposechars(char **args)
 {
     int cc, ct;
     int n = zmult;
@@ -191,10 +203,8 @@ transposechars(void)
 	n = -n;
     while (n--) {
 	if (!(ct = cs) || line[cs - 1] == '\n') {
-	    if (ll == cs || line[cs] == '\n') {
-		feep();
-		return;
-	    }
+	    if (ll == cs || line[cs] == '\n')
+		return 1;
 	    if (!neg)
 		cs++;
 	    ct++;
@@ -211,29 +221,28 @@ transposechars(void)
 	}
 	if (ct == ll || line[ct] == '\n')
 	    ct--;
-	if (ct < 1 || line[ct - 1] == '\n') {
-	    feep();
-	    return;
-	}
+	if (ct < 1 || line[ct - 1] == '\n')
+	    return 1;
 	cc = line[ct - 1];
 	line[ct - 1] = line[ct];
 	line[ct] = cc;
     }
+    return 0;
 }
 
 /**/
-void
-poundinsert(void)
+int
+poundinsert(char **args)
 {
     cs = 0;
-    vifirstnonblank();
+    vifirstnonblank(zlenoargs);
     if (line[cs] != '#') {
 	spaceinline(1);
 	line[cs] = '#';
 	cs = findeol();
 	while(cs != ll) {
 	    cs++;
-	    vifirstnonblank();
+	    vifirstnonblank(zlenoargs);
 	    spaceinline(1);
 	    line[cs] = '#';
 	    cs = findeol();
@@ -243,42 +252,46 @@ poundinsert(void)
 	cs = findeol();
 	while(cs != ll) {
 	    cs++;
-	    vifirstnonblank();
+	    vifirstnonblank(zlenoargs);
 	    if(line[cs] == '#')
 		foredel(1);
 	    cs = findeol();
 	}
     }
     done = 1;
+    return 0;
 }
 
 /**/
-void
-acceptline(void)
+int
+acceptline(char **args)
 {
     done = 1;
+    return 0;
 }
 
 /**/
-void
-acceptandhold(void)
+int
+acceptandhold(char **args)
 {
-    pushnode(bufstack, metafy((char *)line, ll, META_DUP));
+    zpushnode(bufstack, metafy((char *)line, ll, META_DUP));
     stackcs = cs;
     done = 1;
+    return 0;
 }
 
 /**/
-void
-killline(void)
+int
+killline(char **args)
 {
     int i = 0, n = zmult;
 
     if (n < 0) {
+	int ret;
 	zmult = -n;
-	backwardkillline();
+	ret = backwardkillline(args);
 	zmult = n;
-	return;
+	return ret;
     }
     while (n--) {
 	if (line[cs] == '\n')
@@ -288,11 +301,13 @@ killline(void)
 		cs++, i++;
     }
     backkill(i, 0);
+    clearlist = 1;
+    return 0;
 }
 
 /**/
-void
-killregion(void)
+int
+killregion(char **args)
 {
     if (mark > ll)
 	mark = ll;
@@ -300,11 +315,12 @@ killregion(void)
 	forekill(mark - cs, 0);
     else
 	backkill(cs - mark, 1);
+    return 0;
 }
 
 /**/
-void
-copyregionaskill(void)
+int
+copyregionaskill(char **args)
 {
     if (mark > ll)
 	mark = ll;
@@ -312,25 +328,24 @@ copyregionaskill(void)
 	cut(cs, mark - cs, 0);
     else
 	cut(mark, cs - mark, 1);
+    return 0;
 }
 
 static int kct, yankb, yanke;
 
 /**/
-void
-yank(void)
+int
+yank(char **args)
 {
     Cutbuffer buf = &cutbuf;
     int n = zmult;
 
     if (n < 0)
-	return;
+	return 1;
     if (zmod.flags & MOD_VIBUF)
 	buf = &vibuf[zmod.vibuf];
-    if (!buf->buf) {
-	feep();
-	return;
-    }
+    if (!buf->buf)
+	return 1;
     mark = cs;
     yankb = cs;
     while (n--) {
@@ -340,18 +355,17 @@ yank(void)
 	cs += buf->len;
 	yanke = cs;
     }
+    return 0;
 }
 
 /**/
-void
-yankpop(void)
+int
+yankpop(char **args)
 {
     int cc;
 
-    if (!(lastcmd & ZLE_YANK) || !kring[kct].buf) {
-	feep();
-	return;
-    }
+    if (!(lastcmd & ZLE_YANK) || !kring[kct].buf)
+	return 1;
     cs = yankb;
     foredel(yanke - yankb);
     cc = kring[kct].len;
@@ -360,17 +374,20 @@ yankpop(void)
     cs += cc;
     yanke = cs;
     kct = (kct + KRINGCT - 1) % KRINGCT;
+    return 0;
 }
 
 /**/
-void
-overwritemode(void)
+int
+overwritemode(char **args)
 {
     insmode ^= 1;
+    return 0;
 }
+
 /**/
-void
-whatcursorposition(void)
+int
+whatcursorposition(char **args)
 {
     char msg[100];
     char *s = msg;
@@ -404,18 +421,19 @@ whatcursorposition(void)
     sprintf(s, "  point %d of %d(%d%%)  column %d", cs+1, ll+1,
 	    ll ? 100 * cs / ll : 0, cs - bol);
     showmsg(msg);
+    return 0;
 }
 
 /**/
-void
-undefinedkey(void)
+int
+undefinedkey(char **args)
 {
-    feep();
+    return 1;
 }
 
 /**/
-void
-quotedinsert(void)
+int
+quotedinsert(char **args)
 {
 #ifndef HAS_TIO
     struct sgttyb sob;
@@ -426,20 +444,24 @@ quotedinsert(void)
 #endif
     c = getkey(0);
 #ifndef HAS_TIO
-    setterm();
+    zsetterm();
 #endif
     if (c < 0)
-	feep();
+	return 1;
     else
-	selfinsert();
+	return selfinsert(args);
 }
 
 /**/
-void
-digitargument(void)
+int
+digitargument(char **args)
 {
     int sign = (zmult < 0) ? -1 : 1;
 
+    /* allow metafied as well as ordinary digits */
+    if ((c & 0x7f) < '0' || (c & 0x7f) > '9')
+	return 1;
+
     if (!(zmod.flags & MOD_TMULT))
 	zmod.tmult = 0;
     if (zmod.flags & MOD_NEG) {
@@ -451,26 +473,31 @@ digitargument(void)
 	zmod.tmult = zmod.tmult * 10 + sign * (c & 0xf);
     zmod.flags |= MOD_TMULT;
     prefixflag = 1;
+    return 0;
 }
 
 /**/
-void
-negargument(void)
+int
+negargument(char **args)
 {
-    if(zmod.flags & MOD_TMULT) {
-	feep();
-	return;
-    }
+    if (zmod.flags & MOD_TMULT)
+	return 1;
     zmod.tmult = -1;
     zmod.flags |= MOD_TMULT|MOD_NEG;
     prefixflag = 1;
+    return 0;
 }
 
 /**/
-void
-universalargument(void)
+int
+universalargument(char **args)
 {
     int digcnt = 0, pref = 0, minus = 1, gotk;
+    if (*args) {
+	zmod.mult = atoi(*args);
+	zmod.flags |= MOD_MULT;
+	return 0;
+    }
     while ((gotk = getkey(0)) != EOF) {
 	if (gotk == '-' && !digcnt) {
 	    minus = -1;
@@ -489,11 +516,12 @@ universalargument(void)
 	zmod.tmult *= 4;
     zmod.flags |= MOD_TMULT;
     prefixflag = 1;
+    return 0;
 }
 
 /**/
-void
-copyprevword(void)
+int
+copyprevword(char **args)
 {
     int len, t0;
 
@@ -509,18 +537,46 @@ copyprevword(void)
     spaceinline(len);
     memcpy((char *)&line[cs], (char *)&line[t0], len);
     cs += len;
+    return 0;
 }
 
 /**/
-void
-sendbreak(void)
+int
+copyprevshellword(char **args)
+{
+    LinkList l;
+    LinkNode n;
+    int i;
+    char *p = NULL;
+
+    l = bufferwords(&i);
+
+    for (n = firstnode(l); n; incnode(n))
+	if (!i--) {
+	    p = getdata(n);
+	    break;
+	}
+    if (p) {
+	int len = strlen(p);
+
+	spaceinline(len);
+	memcpy(line + cs, p, len);
+	cs += len;
+    }
+    return 0;
+}
+
+/**/
+int
+sendbreak(char **args)
 {
     errflag = 1;
+    return 1;
 }
 
 /**/
-void
-quoteregion(void)
+int
+quoteregion(char **args)
 {
     char *str;
     size_t len;
@@ -540,11 +596,12 @@ quoteregion(void)
     memcpy((char *)&line[cs], str, len);
     mark = cs;
     cs += len;
+    return 0;
 }
 
 /**/
-void
-quoteline(void)
+int
+quoteline(char **args)
 {
     char *str;
     size_t len = ll;
@@ -553,6 +610,7 @@ quoteline(void)
     sizeline(len);
     memcpy(line, str, len);
     cs = ll = len;
+    return 0;
 }
 
 /**/
@@ -567,7 +625,7 @@ makequote(char *str, size_t *len)
 	if (*l == '\'')
 	    qtct++;
     *len += 2 + qtct*3;
-    l = ol = (char *)halloc(*len);
+    l = ol = (char *)zhalloc(*len);
     *l++ = '\'';
     for (; str < end; str++)
 	if (*str == '\'') {
@@ -608,11 +666,13 @@ Thingy
 executenamedcommand(char *prmt)
 {
     Thingy cmd;
-    int len, l = strlen(prmt);
+    int len, l = strlen(prmt), feep = 0, listed = 0, curlist = 0;
+    int ols = (listshown && validlist), olll = lastlistlen;
     char *ptr;
     char *okeymap = curkeymapname;
 
-    cmdbuf = halloc(l + NAMLEN + 2);
+    clearlist = 1;
+    cmdbuf = zhalloc(l + NAMLEN + 2);
     strcpy(cmdbuf, prmt);
     statusline = cmdbuf;
     selectkeymap("main", 1);
@@ -621,40 +681,67 @@ executenamedcommand(char *prmt)
     for (;;) {
 	*ptr = '_';
 	statusll = l + len + 1;
-	refresh();
+	zrefresh();
 	if (!(cmd = getkeycmd()) || cmd == Th(z_sendbreak)) {
 	    statusline = NULL;
 	    selectkeymap(okeymap, 1);
+	    if ((listshown = ols)) {
+		showinglist = -2;
+		lastlistlen = olll;
+	    } else if (listed)
+		clearlist = listshown = 1;
+
 	    return NULL;
 	}
 	if(cmd == Th(z_clearscreen)) {
-	    clearscreen();
+	    clearscreen(zlenoargs);
+	    if (curlist) {
+		int zmultsav = zmult;
+
+		zmult = 1;
+		listlist(cmdll);
+		showinglist = 0;
+		zmult = zmultsav;
+	    }
 	} else if(cmd == Th(z_redisplay)) {
-	    redisplay();
+	    redisplay(zlenoargs);
+	    if (curlist) {
+		int zmultsav = zmult;
+
+		zmult = 1;
+		listlist(cmdll);
+		showinglist = 0;
+		zmult = zmultsav;
+	    }
 	} else if(cmd == Th(z_viquotedinsert)) {
 	    *ptr = '^';
-	    refresh();
+	    zrefresh();
 	    c = getkey(0);
 	    if(c == EOF || !c || len == NAMLEN)
-		feep();
+		feep = 1;
 	    else
-		*ptr++ = c, len++;
+		*ptr++ = c, len++, curlist = 0;
 	} else if(cmd == Th(z_quotedinsert)) {
 	    if((c = getkey(0)) == EOF || !c || len == NAMLEN)
-		feep();
+		feep = 1;
 	    else
-		*ptr++ = c, len++;
+		*ptr++ = c, len++, curlist = 0;
 	} else if(cmd == Th(z_backwarddeletechar) ||
 	    	cmd == Th(z_vibackwarddeletechar)) {
 	    if (len)
-		len--, ptr--;
+		len--, ptr--, curlist = 0;
 	} else if(cmd == Th(z_killregion) || cmd == Th(z_backwardkillword) ||
-	    	cmd == Th(z_vibackwardkillword)) {
+		  cmd == Th(z_vibackwardkillword)) {
+	    if (len)
+		curlist = 0;
 	    while (len && (len--, *--ptr != '-'));
 	} else if(cmd == Th(z_killwholeline) || cmd == Th(z_vikillline) ||
 	    	cmd == Th(z_backwardkillline)) {
 	    len = 0;
 	    ptr = cmdbuf;
+	    if (listed)
+		clearlist = listshown = 1;
+	    curlist = 0;
 	} else {
 	    if(cmd == Th(z_acceptline) || cmd == Th(z_vicmdmode)) {
 		Thingy r;
@@ -665,6 +752,11 @@ executenamedcommand(char *prmt)
 		    unrefthingy(r);
 		    statusline = NULL;
 		    selectkeymap(okeymap, 1);
+		    if ((listshown = ols)) {
+			showinglist = -2;
+			lastlistlen = olll;
+		    } else if (listed)
+			clearlist = listshown = 1;
 		    return r;
 		}
 		unrefthingy(r);
@@ -681,21 +773,25 @@ executenamedcommand(char *prmt)
 		cmd == Th(z_acceptline) || c == ' ' || c == '\t') {
 		cmdambig = 100;
 
-		HEAPALLOC {
-		    cmdll = newlinklist();
-		    *ptr = 0;
+		cmdll = newlinklist();
+		*ptr = 0;
+
+		scanhashtable(thingytab, 1, 0, DISABLED, scancompcmd, 0);
 
-		    scanhashtable(thingytab, 1, 0, DISABLED, scancompcmd, 0);
-		} LASTALLOC;
-		if (empty(cmdll))
-		    feep();
-		else if (cmd == Th(z_listchoices) ||
+		if (empty(cmdll)) {
+		    feep = 1;
+		    if (listed)
+			clearlist = listshown = 1;
+		    curlist = 0;
+		} else if (cmd == Th(z_listchoices) ||
 		    cmd == Th(z_deletecharorlist)) {
 		    int zmultsav = zmult;
 		    *ptr = '_';
 		    statusll = l + len + 1;
 		    zmult = 1;
 		    listlist(cmdll);
+		    listed = curlist = 1;
+		    showinglist = 0;
 		    zmult = zmultsav;
 		} else if (!nextnode(firstnode(cmdll))) {
 		    strcpy(ptr = cmdbuf, peekfirst(cmdll));
@@ -710,22 +806,26 @@ executenamedcommand(char *prmt)
 			!(isset(LISTAMBIGUOUS) && cmdambig > len)) {
 			int zmultsav = zmult;
 			if (isset(LISTBEEP))
-			    feep();
+			    feep = 1;
 			statusll = l + cmdambig + 1;
 			zmult = 1;
 			listlist(cmdll);
+			listed = curlist = 1;
+			showinglist = 0;
 			zmult = zmultsav;
 		    }
 		    len = cmdambig;
 		}
 	    } else {
 		if (len == NAMLEN || icntrl(c) || cmd != Th(z_selfinsert))
-		    feep();
+		    feep = 1;
 		else
-		    *ptr++ = c, len++;
+		    *ptr++ = c, len++, curlist = 0;
 	    }
 	}
-	handlefeep();
+	if (feep)
+	    handlefeep(zlenoargs);
+	feep = 0;
     }
 }
 
@@ -761,16 +861,22 @@ executenamedcommand(char *prmt)
  * suffixlen[256] is the length to remove for non-insertion editing actions. */
 
 /**/
-int suffixlen[257];
+mod_export int suffixlen[257];
+
+/* Shell function to call to remove the suffix. */
+
+/**/
+static char *suffixfunc;
 
 /* Set up suffix: the last n characters are a suffix that should be *
  * removed in the usual word end conditions.                        */
 
 /**/
-void
+mod_export void
 makesuffix(int n)
 {
-    suffixlen[256] = suffixlen[' '] = suffixlen['\t'] = suffixlen['\n'] = n;
+    suffixlen[256] = suffixlen[' '] = suffixlen['\t'] = suffixlen['\n'] = 
+	suffixlen[';'] = suffixlen['&'] = suffixlen['|'] = n;
 }
 
 /* Set up suffix for parameter names: the last n characters are a suffix *
@@ -780,7 +886,7 @@ makesuffix(int n)
  * characters that can only be used in braces are included.              */
 
 /**/
-void
+mod_export void
 makeparamsuffix(int br, int n)
 {
     if(br || unset(KSHARRAYS))
@@ -788,20 +894,91 @@ makeparamsuffix(int br, int n)
     if(br) {
 	suffixlen['#'] = suffixlen['%'] = suffixlen['?'] = n;
 	suffixlen['-'] = suffixlen['+'] = suffixlen['='] = n;
-	/*{*/ suffixlen['}'] = n;
+	/*{*/ suffixlen['}'] = suffixlen['/'] = n;
     }
 }
 
+/* Set up suffix given a string containing the characters on which to   *
+ * remove the suffix. */
+
+/**/
+mod_export void
+makesuffixstr(char *f, char *s, int n)
+{
+    if (f) {
+	zsfree(suffixfunc);
+	suffixfunc = ztrdup(f);
+	suffixlen[0] = n;
+    } else if (s) {
+	int inv, i, v, z = 0;
+
+	if (*s == '^' || *s == '!') {
+	    inv = 1;
+	    s++;
+	} else
+	    inv = 0;
+	s = getkeystring(s, &i, 5, &z);
+	s = metafy(s, i, META_USEHEAP);
+
+	if (inv) {
+	    v = 0;
+	    for (i = 0; i < 257; i++)
+		 suffixlen[i] = n;
+	} else
+	    v = n;
+
+	if (z)
+	    suffixlen[256] = v;
+
+	while (*s) {
+	    if (s[1] == '-' && s[2]) {
+		int b = (int) *s, e = (int) s[2];
+
+		while (b <= e)
+		    suffixlen[b++] = v;
+		s += 2;
+	    } else
+		suffixlen[STOUC(*s)] = v;
+	    s++;
+	}
+    } else
+	makesuffix(n);
+}
+
 /* Remove suffix, if there is one, when inserting character c. */
 
 /**/
-void
-iremovesuffix(int c)
+mod_export void
+iremovesuffix(int c, int keep)
 {
-    int sl = suffixlen[c];
-    if(sl) {
-	backdel(sl);
-	invalidatelist();
+    if (suffixfunc) {
+	Eprog prog = getshfunc(suffixfunc);
+
+	if (prog != &dummy_eprog) {
+	    LinkList args = newlinklist();
+	    char buf[20];
+	    int osc = sfcontext;
+
+	    sprintf(buf, "%d", suffixlen[0]);
+	    addlinknode(args, suffixfunc);
+	    addlinknode(args, buf);
+
+	    startparamscope();
+	    makezleparams(0);
+	    sfcontext = SFC_COMPLETE;
+	    doshfunc(suffixfunc, prog, args, 0, 1);
+	    sfcontext = osc;
+	    endparamscope();
+	}
+	zsfree(suffixfunc);
+	suffixfunc = NULL;
+    } else {
+	int sl = suffixlen[c];
+	if(sl) {
+	    backdel(sl);
+	    if (!keep)
+		invalidatelist();
+	}
     }
     fixsuffix();
 }
@@ -809,7 +986,7 @@ iremovesuffix(int c)
 /* Fix the suffix in place, if there is one, making it non-removable. */
 
 /**/
-void
+mod_export void
 fixsuffix(void)
 {
     memset(suffixlen, 0, sizeof(suffixlen));
diff --git a/Src/hist.c b/Src/hist.c
index a4c5735c1..530b6e05c 100644
--- a/Src/hist.c
+++ b/Src/hist.c
@@ -30,10 +30,31 @@
 #include "zsh.mdh"
 #include "hist.pro"
 
+/* Functions to call for getting/ungetting a character and for history
+ * word control. */
+
+/**/
+mod_export int (*hgetc) _((void));
+
+/**/
+void (*hungetc) _((int));
+
+/**/
+void (*hwaddc) _((int));
+
+/**/
+void (*hwbegin) _((int));
+
+/**/
+void (*hwend) _((void));
+
+/**/
+void (*addtoline) _((int));
+
 /* != 0 means history substitution is turned off */
  
 /**/
-int stophist;
+mod_export int stophist;
  
 /* this line began with a space, so junk it if HISTIGNORESPACE is on */
  
@@ -43,12 +64,12 @@ int spaceflag;
 /* if != 0, we are expanding the current line */
 
 /**/
-int expanding;
+mod_export int expanding;
 
 /* these are used to modify the cursor position during expansion */
 
 /**/
-int excs, exlast;
+mod_export int excs, exlast;
 
 /*
  * Current history event number
@@ -56,23 +77,29 @@ int excs, exlast;
  * Note on curhist: with history inactive, this points to the
  * last line actually added to the history list.  With history active,
  * the line does not get added to the list until hend(), if at all.
- * However, curhist is incremented to reflect the current line anyway.
- * Thus if the line is not added to the list, curhist must be
- * decremented in hend().
+ * However, curhist is incremented to reflect the current line anyway
+ * and a temporary history entry is inserted while the user is editing.
+ * If the resulting line was not added to the list, a flag is set so
+ * that curhist will be decremented in hbegin().
  */
  
 /**/
-int curhist;
+mod_export int curhist;
 
-/* number of history entries */
- 
 /**/
-int histentct;
- 
-/* array of history entries */
- 
+struct histent curline;
+
+/* current line count of allocated history entries */
+
+/**/
+int histlinect;
+
+/* The history lines are kept in a hash, and also doubly-linked in a ring */
+
+/**/
+HashTable histtab;
 /**/
-Histent histentarr;
+mod_export Histent hist_ring;
  
 /* capacity of history lists */
  
@@ -90,6 +117,17 @@ int histdone;
 /**/
 int histactive;
 
+/* Current setting of the associated option, but sometimes also includes
+ * the setting of the HIST_SAVE_NO_DUPS option. */
+
+/**/
+int hist_ignore_all_dups;
+
+/* What flags (if any) we should skip when moving through the history */
+
+/**/
+mod_export int hist_skip_flags;
+
 /* Bits of histactive variable */
 #define HA_ACTIVE	(1<<0)	/* History mechanism is active */
 #define HA_NOSTORE	(1<<1)	/* Don't store the line when finished */
@@ -121,12 +159,12 @@ char *hsubr;
 /* pointer into the history line */
  
 /**/
-char *hptr;
+mod_export char *hptr;
  
 /* the current history line */
  
 /**/
-char *chline;
+mod_export char *chline;
 
 /* true if the last character returned by hgetc was an escaped bangchar *
  * if it is set and NOBANGHIST is unset hwaddc escapes bangchars        */
@@ -142,12 +180,11 @@ int hlinesz;
 /* default event (usually curhist-1, that is, "!!") */
  
 static int defev;
- 
+
 /* add a character to the current history word */
 
-/**/
-void
-hwaddc(int c)
+static void
+ihwaddc(int c)
 {
     /* Only if history line exists and lexing has not finished. */
     if (chline && !(errflag || lexstop)) {
@@ -165,7 +202,7 @@ hwaddc(int c)
 	if (hptr - chline >= hlinesz) {
 	    int oldsiz = hlinesz;
 
-	    chline = realloc(chline, hlinesz = oldsiz + 16);
+	    chline = realloc(chline, hlinesz = oldsiz + 64);
 	    hptr = chline + oldsiz;
 	}
     }
@@ -175,12 +212,12 @@ hwaddc(int c)
  * zsh expands history (see doexpandhist() in zle_tricky.c). It also     *
  * calculates the new cursor position after the expansion. It is called  *
  * from hgetc() and from gettok() in lex.c for characters in comments.   */
- 
+
 /**/
 void
-addtoline(int c)
+iaddtoline(int c)
 {
-    if (! expanding || lexstop)
+    if (!expanding || lexstop)
 	return;
     if (qbang && c == bangchar && stophist < 2) {
 	exlast--;
@@ -199,9 +236,8 @@ addtoline(int c)
     line[cs++] = itok(c) ? ztokens[c - Pound] : c;
 }
 
-/**/
-int
-hgetc(void)
+static int
+ihgetc(void)
 {
     int c = ingetc();
 
@@ -217,7 +253,7 @@ hgetc(void)
     }
     if ((inbufflags & INP_HIST) && !stophist) {
 	/* the current character c came from a history expansion          *
-	 * (inbufflags && INP_HIST) and history is not disabled           *
+	 * (inbufflags & INP_HIST) and history is not disabled            *
 	 * (e.g. we are not inside single quotes). In that case, \!       *
 	 * should be treated as ! (since this \! came from a previous     *
 	 * history line where \ was used to escape the bang). So if       *
@@ -255,7 +291,7 @@ safeinungetc(int c)
 void
 herrflush(void)
 {
-    while (!lexstop && inbufct)
+    while (!lexstop && inbufct && !strin)
 	hwaddc(ingetc());
 }
 
@@ -392,10 +428,10 @@ histsubchar(int c)
 		c = ingetc();
 	    }
 	    *ptr = 0;
-	    if (!*buf)
+	    if (!*buf) {
 		if (c != '%') {
 		    if (isset(CSHJUNKIEHISTORY))
-			ev = curhist - 1;
+			ev = addhistnum(curhist,-1,HIST_FOREIGN);
 		    else
 			ev = defev;
 		    if (c == ':' && evset == -1)
@@ -408,11 +444,12 @@ histsubchar(int c)
 		    else
 			ev = defev;
 		    evset = 0;
+		}
 	    } else if ((t0 = atoi(buf))) {
-		ev = (t0 < 0) ? curhist + t0 : t0;
+		ev = (t0 < 0) ? addhistnum(curhist,t0,HIST_FOREIGN) : t0;
 		evset = 1;
 	    } else if ((unsigned)*buf == bangchar) {
-		ev = curhist - 1;
+		ev = addhistnum(curhist,-1,HIST_FOREIGN);
 		evset = 1;
 	    } else if (*buf == '#') {
 		ev = curhist;
@@ -540,6 +577,18 @@ histsubchar(int c)
 	    case 'q':
 		quote(&sline);
 		break;
+	    case 'Q':
+		{
+		    int one = noerrs, oef = errflag;
+
+		    noerrs = 1;
+		    parse_subst_string(sline);
+		    noerrs = one;
+		    errflag = oef;
+		    remnulargs(sline);
+		    untokenize(sline);
+		}
+		break;
 	    case 'x':
 		quotebreak(&sline);
 		break;
@@ -588,13 +637,12 @@ histsubchar(int c)
 /* unget a char and remove it from chline. It can only be used *
  * to unget a character returned by hgetc.                     */
 
-/**/
-void
-hungetc(int c)
+static void
+ihungetc(int c)
 {
     int doit = 1;
 
-    while (!lexstop) {
+    while (!lexstop && !errflag) {
 	if (hptr[-1] != (char) c && stophist < 4 &&
 	    hptr > chline + 1 && hptr[-1] == '\n' && hptr[-2] == '\\')
 	    hungetc('\n'), hungetc('\\');
@@ -622,18 +670,18 @@ hungetc(int c)
 /* begin reading a string */
 
 /**/
-void
-strinbeg(void)
+mod_export void
+strinbeg(int dohist)
 {
     strin++;
-    hbegin();
+    hbegin(dohist);
     lexinit();
 }
 
 /* done reading a string */
 
 /**/
-void
+mod_export void
 strinend(void)
 {
     hend();
@@ -643,60 +691,72 @@ strinend(void)
     histdone = 0;
 }
 
+/* dummy functions to use instead of hwaddc(), hwbegin(), and hwend() when
+ * they aren't needed */
+
+static void
+nohw(int c)
+{
+}
+
+static void
+nohwe(void)
+{
+}
+
 /* initialize the history mechanism */
 
 /**/
-void
-hbegin(void)
+mod_export void
+hbegin(int dohist)
 {
-    Histent curhistent;
-
     isfirstln = isfirstch = 1;
     errflag = histdone = spaceflag = 0;
-    stophist = (!interact || unset(BANGHIST) || unset(SHINSTDIN)) << 1;
-    chline = hptr = zcalloc(hlinesz = 16);
-    chwords = zalloc((chwordlen = 16)*sizeof(short));
+    stophist = (!dohist || !interact || unset(SHINSTDIN)) ? 2 : 0;
+    if (stophist == 2 || (inbufflags & INP_ALIAS)) {
+	chline = hptr = NULL;
+	hlinesz = 0;
+	chwords = NULL;
+	chwordlen = 0;
+	hgetc = ingetc;
+	hungetc = inungetc;
+	hwaddc = nohw;
+	hwbegin = nohw;
+	hwend = nohwe;
+	addtoline = nohw;
+    } else {
+	chline = hptr = zcalloc(hlinesz = 64);
+	chwords = zalloc((chwordlen = 64) * sizeof(short));
+	hgetc = ihgetc;
+	hungetc = ihungetc;
+	hwaddc = ihwaddc;
+	hwbegin = ihwbegin;
+	hwend = ihwend;
+	addtoline = iaddtoline;
+	if (!isset(BANGHIST))
+	    stophist = 4;
+    }
     chwordpos = 0;
 
     if (histactive & HA_JUNKED)
 	curhist--;
-    curhistent = gethistent(curhist);
-    if (!curhistent->ftim)
-	curhistent->ftim = time(NULL);
-    histactive = HA_ACTIVE;
+    if (hist_ring && !hist_ring->ftim)
+	hist_ring->ftim = time(NULL);
     if (interact && isset(SHINSTDIN) && !strin) {
+	histactive = HA_ACTIVE;
 	attachtty(mypgrp);
-	defev = curhist;
-	curhist++;
+	if (!hist_ring)
+	    hist_ring = curline.up = curline.down = &curline;
+	else {
+	    curline.up = hist_ring;
+	    curline.down = hist_ring->down;
+	    hist_ring->down = hist_ring->down->up = &curline;
+	    hist_ring = &curline;
+	}
+	curline.histnum = ++curhist;
+	defev = addhistnum(curhist, -1, HIST_FOREIGN);
     } else
-	histactive |= HA_NOINC;
-}
-
-/* compare current line with history entry using only text in words */
-
-/**/
-static int
-histcmp(Histent he)
-{
-    int kword, lword;
-    int nwords = chwordpos/2;
-
-    /* If the history entry came from a file, the words were not
-     * divided by the lexer so we have to resort to strcmp.
-     */
-    if (he->flags & HIST_READ)
-	return strcmp(he->text, chline);
-
-    if (nwords != he->nwords)
-	return 1;
-
-    for (kword = 0; kword < 2*nwords; kword += 2)
-	if ((lword = chwords[kword+1]-chwords[kword])
-	    != he->words[kword+1]-he->words[kword] ||
-	    memcmp(he->text+he->words[kword], chline+chwords[kword], lword))
-	    return 1;
-
-    return 0;
+	histactive = HA_ACTIVE | HA_NOINC;
 }
 
 /**/
@@ -725,35 +785,194 @@ histreduceblanks(void)
     chline[pos] = '\0';
 }
 
+/**/
+void
+histremovedups(void)
+{
+    Histent he, next;
+    for (he = hist_ring; he; he = next) {
+	next = up_histent(he);
+	if (he->flags & HIST_DUP)
+	    freehistnode((HashNode)he);
+    }
+}
+
+/**/
+mod_export int
+addhistnum(int hl, int n, int xflags)
+{
+    int dir = n < 0? -1 : n > 0? 1 : 0;
+    Histent he = gethistent(hl, dir);
+			     
+    if (!he)
+	return 0;
+    if (he->histnum != hl)
+	n -= dir;
+    if (n)
+	he = movehistent(he, n, xflags);
+    if (!he)
+	return dir < 0? firsthist() : curhist;
+    return he->histnum;
+}
+
+/**/
+mod_export Histent
+movehistent(Histent he, int n, int xflags)
+{
+    while (n < 0) {
+	if (!(he = up_histent(he)))
+	    return NULL;
+	if (!(he->flags & xflags))
+	    n++;
+    }
+    while (n > 0) {
+	if (!(he = down_histent(he)))
+	    return NULL;
+	if (!(he->flags & xflags))
+	    n--;
+    }
+    return he;
+}
+
+/**/
+mod_export Histent
+up_histent(Histent he)
+{
+    return he->up == hist_ring? NULL : he->up;
+}
+
+/**/
+mod_export Histent
+down_histent(Histent he)
+{
+    return he == hist_ring? NULL : he->down;
+}
+
+/**/
+Histent
+gethistent(int ev, int nearmatch)
+{
+    Histent he;
+
+    if (!hist_ring)
+	return NULL;
+
+    if (ev - hist_ring->down->histnum < hist_ring->histnum - ev) {
+	for (he = hist_ring->down; he->histnum <= ev; he = he->down) {
+	    if (he->histnum == ev)
+		return he;
+	}
+	if (nearmatch < 0)
+	    return up_histent(he);
+	if (nearmatch > 0)
+	    return he;
+    }
+    else {
+	for (he = hist_ring; he->histnum >= ev; he = he->up) {
+	    if (he->histnum == ev)
+		return he;
+	}
+	if (nearmatch < 0)
+	    return he;
+	if (nearmatch > 0)
+	    return down_histent(he);
+    }
+
+    return NULL;
+}
+
+/**/
+Histent
+prepnexthistent(int histnum)
+{
+    Histent he;
+
+    if (histlinect < histsiz) {
+	he = (Histent)zcalloc(sizeof *he);
+	if (!hist_ring)
+	    hist_ring = he->up = he->down = he;
+	else {
+	    he->up = hist_ring;
+	    he->down = hist_ring->down;
+	    hist_ring->down = he->down->up = he;
+	    hist_ring = he;
+	}
+	histlinect++;
+    }
+    else {
+	he = hist_ring->down;
+	if (isset(HISTEXPIREDUPSFIRST) && !(he->flags & HIST_DUP)) {
+	    int max_unique_ct = getiparam("SAVEHIST");
+	    do {
+		if (max_unique_ct-- <= 0) {
+		    he = hist_ring->down;
+		    break;
+		}
+		he = he->down;
+	    } while (he != hist_ring->down && !(he->flags & HIST_DUP));
+	    if (he != hist_ring->down) {
+		he->up->down = he->down;
+		he->down->up = he->up;
+		he->up = hist_ring;
+		he->down = hist_ring->down;
+		hist_ring->down = he->down->up = he;
+	    }
+	}
+	freehistdata(hist_ring = he, 0);
+    }
+    hist_ring->histnum = histnum;
+    return hist_ring;
+}
+
 /* say we're done using the history mechanism */
 
 /**/
-int
+mod_export int
 hend(void)
 {
     int flag, save = 1;
-
-    DPUTS(!chline, "BUG: chline is NULL in hend()");
+    char *hf = getsparam("HISTFILE");
+
+    DPUTS(stophist != 2 && !(inbufflags & INP_ALIAS) && !chline,
+	  "BUG: chline is NULL in hend()");
+    if (histdone & HISTFLAG_SETTY)
+	settyinfo(&shttyinfo);
+    if (!(histactive & HA_NOINC)) {
+	curline.up->down = curline.down;
+	curline.down->up = curline.up;
+	if (hist_ring == &curline) {
+	    if (!histlinect)
+		hist_ring = NULL;
+	    else
+		hist_ring = curline.up;
+	}
+	curhist--;
+    }
     if (histactive & (HA_NOSTORE|HA_NOINC)) {
 	zfree(chline, hlinesz);
 	zfree(chwords, chwordlen*sizeof(short));
 	chline = NULL;
-	if (!(histactive & HA_NOINC))
-	    curhist--;
 	histactive = 0;
 	return 1;
     }
+    if (hist_ignore_all_dups != isset(HISTIGNOREALLDUPS)
+     && (hist_ignore_all_dups = isset(HISTIGNOREALLDUPS)) != 0)
+	histremovedups();
+    /* For history sharing, lock history file once for both read and write */
+    if (isset(SHAREHISTORY) && lockhistfile(hf, 0))
+	readhistfile(hf, 0, HFILE_USE_OPTIONS | HFILE_FAST);
     flag = histdone;
     histdone = 0;
     if (hptr < chline + 1)
 	save = 0;
     else {
 	*hptr = '\0';
-	if (hptr[-1] == '\n')
+	if (hptr[-1] == '\n') {
 	    if (chline[1]) {
 		*--hptr = '\0';
 	    } else
 		save = 0;
+	}
 	if (!*chline || !strcmp(chline, "\n") ||
 	    (isset(HISTIGNORESPACE) && spaceflag))
 	    save = 0;
@@ -768,17 +987,18 @@ hend(void)
 	    fflush(shout);
 	}
 	if (flag & HISTFLAG_RECALL) {
-	    PERMALLOC {
-		pushnode(bufstack, ptr);
-	    } LASTALLOC;
+	    zpushnode(bufstack, ptr);
+
 	    save = 0;
 	} else
 	    zsfree(ptr);
     }
     if (save) {
 	Histent he;
-	int keepflags = 0;
+	int keepflags;
 
+	for (he = hist_ring; he && he->flags & hist_skip_flags;
+	     he = up_histent(he)) ;
 #ifdef DEBUG
 	/* debugging only */
 	if (chwordpos%2) {
@@ -787,28 +1007,26 @@ hend(void)
 	}
 #endif
 	/* get rid of pesky \n which we've already nulled out */
-	if (!chline[chwords[chwordpos-2]])
+	if (chwordpos > 1 && !chline[chwords[chwordpos-2]])
 	    chwordpos -= 2;
 	/* strip superfluous blanks, if desired */
 	if (isset(HISTREDUCEBLANKS))
 	    histreduceblanks();
-
-	if (isset(HISTIGNOREDUPS) && (he = gethistent(curhist - 1))
-	 && he->text && !histcmp(he)) {
+	if ((isset(HISTIGNOREDUPS) || isset(HISTIGNOREALLDUPS)) && he
+	 && histstrcmp(chline, he->text) == 0) {
 	    /* This history entry compares the same as the previous.
 	     * In case minor changes were made, we overwrite the
-	     * previous one with the current one.  This also gets
-	     * the timestamp right.  However, keep the old flags.
+	     * previous one with the current one.  This also gets the
+	     * timestamp right.  Perhaps, preserve the HIST_OLD flag.
 	     */
-	    keepflags = he->flags;
-	    curhist--;
+	    keepflags = he->flags & HIST_OLD; /* Avoid re-saving */
+	    freehistdata(he, 0);
+	} else {
+	    keepflags = 0;
+	    he = prepnexthistent(++curhist);
 	}
 
-	he =  gethistent(curhist);
-	zsfree(he->text);
 	he->text = ztrdup(chline);
-	if (he->nwords)
-	    zfree(he->words, he->nwords*2*sizeof(short));
 	he->stim = time(NULL);
 	he->ftim = 0L;
 	he->flags = keepflags;
@@ -817,12 +1035,15 @@ hend(void)
 	    he->words = (short *)zalloc(chwordpos * sizeof(short));
 	    memcpy(he->words, chwords, chwordpos * sizeof(short));
 	}
-    } else
-	curhist--;
+	addhistnode(histtab, he->text, he);
+    }
     zfree(chline, hlinesz);
     zfree(chwords, chwordlen*sizeof(short));
     chline = NULL;
     histactive = 0;
+    if (isset(SHAREHISTORY) || isset(INCAPPENDHISTORY))
+	savehistfile(hf, 0, HFILE_USE_OPTIONS | HFILE_FAST);
+    unlockhistfile(hf); /* It's OK to call this even if we aren't locked */
     return !(flag & HISTFLAG_NOEXEC || errflag);
 }
 
@@ -832,12 +1053,11 @@ hend(void)
 void
 remhist(void)
 {
+    if (hist_ring == &curline)
+	return;
     if (!(histactive & HA_ACTIVE)) {
 	if (!(histactive & HA_JUNKED)) {
-	    /* make sure this doesn't show up when we do firsthist() */
-	    Histent he = gethistent(curhist);
-	    zsfree(he->text);
-	    he->text = NULL;
+	    freehistnode((HashNode)hist_ring);
 	    histactive |= HA_JUNKED;
 	    /* curhist-- is delayed until the next hbegin() */
 	}
@@ -854,8 +1074,10 @@ int hwgetword = -1;
 
 /**/
 void
-hwbegin(int offset)
+ihwbegin(int offset)
 {
+    if (stophist == 2)
+	return;
     if (chwordpos%2)
 	chwordpos--;	/* make sure we're on a word start, not end */
     /* If we're expanding an alias, we should overwrite the expansion
@@ -872,15 +1094,18 @@ hwbegin(int offset)
 
 /**/
 void
-hwend(void)
+ihwend(void)
 {
+    if (stophist == 2)
+	return;
     if (chwordpos%2 && chline) {
 	/* end of word reached and we've already begun a word */
 	if (hptr > chline + chwords[chwordpos-1]) {
 	    chwords[chwordpos++] = hptr - chline;
 	    if (chwordpos >= chwordlen) {
 		chwords = (short *) realloc(chwords,
-					    (chwordlen += 16)*sizeof(short));
+					    (chwordlen += 32) * 
+					    sizeof(short));
 	    }
 	    if (hwgetword > -1) {
 		/* We want to reuse the current word position */
@@ -956,7 +1181,7 @@ hwrep(char *rep)
 /* Get the entire current line, deleting it in the history. */
 
 /**/
-char *
+mod_export char *
 hgetline(void)
 {
     /* Currently only used by pushlineoredit().
@@ -1022,18 +1247,21 @@ getargspec(int argc, int marg, int evset)
 static int
 hconsearch(char *str, int *marg)
 {
-    int t0, t1 = 0;
+    int t1 = 0;
     char *s;
     Histent he;
 
-    for (t0 = curhist - 1; (he = quietgethist(t0)); t0--)
+    for (he = up_histent(hist_ring); he; he = up_histent(he)) {
+	if (he->flags & HIST_FOREIGN)
+	    continue;
 	if ((s = strstr(he->text, str))) {
 	    int pos = s - he->text;
 	    while (t1 < he->nwords && he->words[2*t1] <= pos)
 		t1++;
 	    *marg = t1 - 1;
-	    return t0;
+	    return he->histnum;
 	}
+    }
     return -1;
 }
 
@@ -1043,12 +1271,15 @@ hconsearch(char *str, int *marg)
 int
 hcomsearch(char *str)
 {
-    int t0;
-    char *hs;
+    Histent he;
+    int len = strlen(str);
 
-    for (t0 = curhist - 1; (hs = quietgetevent(t0)); t0--)
-	if (!strncmp(hs, str, strlen(str)))
-	    return t0;
+    for (he = up_histent(hist_ring); he; he = up_histent(he)) {
+	if (he->flags & HIST_FOREIGN)
+	    continue;
+	if (strncmp(he->text, str, len) == 0)
+	    return he->histnum;
+    }
     return -1;
 }
 
@@ -1097,7 +1328,7 @@ rembutext(char **junkptr)
 }
 
 /**/
-int
+mod_export int
 remlpaths(char **junkptr)
 {
     char *str = *junkptr, *remcut;
@@ -1188,7 +1419,7 @@ convamps(char *out, char *in, int inlen)
 	    slen += inlen - 1, sdup = 1;
     if (!sdup)
 	return out;
-    ret = pp = (char *)alloc(slen + 1);
+    ret = pp = (char *) zhalloc(slen + 1);
     for (ptr = out; *ptr; ptr++)
 	if (*ptr == '\\')
 	    *pp++ = *++ptr;
@@ -1202,33 +1433,22 @@ convamps(char *out, char *in, int inlen)
 }
 
 /**/
-struct histent *
-quietgethist(int ev)
+mod_export Histent
+quietgethistent(int ev, int nearmatch)
 {
-    static struct histent storehist;
-
-    if (ev < firsthist() || ev > curhist)
-	return NULL;
     if (ev == curhist && (histactive & HA_ACTIVE)) {
-	/* The current history line has not been stored.  Build it up
-	 * from other variables.
-	 */
-	storehist.text = chline;
-	storehist.nwords = chwordpos/2;
-	storehist.words = chwords;
-
-	return &storehist;
-    } else
-	return gethistent(ev);
+	curline.text = chline;
+	curline.nwords = chwordpos/2;
+	curline.words = chwords;
+    }
+    return gethistent(ev, nearmatch);
 }
 
 /**/
-char *
-quietgetevent(int ev)
+mod_export Histent
+quietgethist(int ev)
 {
-    Histent ent = quietgethist(ev);
-
-    return ent ? ent->text : NULL;
+    return quietgethistent(ev, GETHIST_EXACT);
 }
 
 /**/
@@ -1301,7 +1521,7 @@ quote(char **tr)
 	} else if (inblank(*ptr) && !inquotes && ptr[-1] != '\\')
 	    len += 2;
     ptr = *str;
-    *str = rptr = (char *)alloc(len);
+    *str = rptr = (char *) zhalloc(len);
     *rptr++ = '\'';
     for (; *ptr; ptr++)
 	if (*ptr == '\'') {
@@ -1338,7 +1558,7 @@ quotebreak(char **tr)
 	else if (inblank(*ptr))
 	    len += 2;
     ptr = *str;
-    *str = rptr = (char *)alloc(len);
+    *str = rptr = (char *) zhalloc(len);
     *rptr++ = '\'';
     for (; *ptr;)
 	if (*ptr == '\'') {
@@ -1358,10 +1578,9 @@ quotebreak(char **tr)
     return 0;
 }
 
-#if 0
 /* read an arbitrary amount of data into a buffer until stop is found */
 
-/**/
+#if 0 /**/
 char *
 hdynread(int stop)
 {
@@ -1420,61 +1639,80 @@ hdynread2(int stop)
 void
 inithist(void)
 {
-    histentct = histsiz;
-    histentarr = (Histent) zcalloc(histentct * sizeof *histentarr);
+    createhisttable();
 }
 
 /**/
 void
 resizehistents(void)
 {
-    int newentct, t0, t1, firstlex;
-    Histent newarr;
-
-    newentct = histsiz;
-    newarr = (Histent) zcalloc(newentct * sizeof *newarr);
-    firstlex = curhist - histsiz + 1;
-    t0 = firsthist();
-    if (t0 < curhist - newentct)
-	t0 = curhist - newentct;
-    t1 = t0 % newentct;
-    for (; t0 <= curhist; t0++) {
-	newarr[t1] = *gethistent(t0);
-	if (t0 < firstlex) {
-	    zsfree(newarr[t1].text);
-	    newarr[t1].text = NULL;
-	}
-	t1++;
-	if (t1 == newentct)
-	    t1 = 0;
-    }
-    free(histentarr);
-    histentarr = newarr;
-    histentct = newentct;
+    while (histlinect > histsiz)
+	freehistnode((HashNode)hist_ring->down);
 }
 
+/* Remember the last line in the history file so we can find it again. */
+static struct {
+    char *text;
+    time_t stim, mtim;
+    off_t fpos, fsiz;
+    int next_write_ev;
+} lasthist;
+
+static int histfile_linect;
+
 /**/
 void
-readhistfile(char *s, int err)
+readhistfile(char *fn, int err, int readflags)
 {
-    char *buf;
+    char *buf, *start = NULL;
     FILE *in;
-    Histent ent;
-    time_t tim = time(NULL);
+    Histent he;
+    time_t stim, ftim, tim = time(NULL);
+    off_t fpos;
     short *wordlist;
+    struct stat sb;
     int nwordpos, nwordlist, bufsiz;
+    int searching, newflags;
 
-    if (!s)
+    if (!fn && !(fn = getsparam("HISTFILE")))
+	return;
+    if (readflags & HFILE_FAST) {
+	if (stat(fn, &sb) < 0
+	 || (lasthist.fsiz == sb.st_size && lasthist.mtim == sb.st_mtime)
+	 || !lockhistfile(fn, 0))
+	    return;
+	lasthist.fsiz = sb.st_size;
+	lasthist.mtim = sb.st_mtime;
+    }
+    else if (!lockhistfile(fn, 1))
 	return;
-    if ((in = fopen(unmeta(s), "r"))) {
-	nwordlist = 16;
+    if ((in = fopen(unmeta(fn), "r"))) {
+	nwordlist = 64;
 	wordlist = (short *)zalloc(nwordlist*sizeof(short));
 	bufsiz = 1024;
 	buf = zalloc(bufsiz);
 
-	while (fgets(buf, bufsiz, in)) {
+	if (readflags & HFILE_FAST && lasthist.text) {
+	    if (lasthist.fpos < lasthist.fsiz) {
+		fseek(in, lasthist.fpos, 0);
+		searching = 1;
+	    }
+	    else {
+		histfile_linect = 0;
+		searching = -1;
+	    }
+	} else
+	    searching = 0;
+
+	newflags = HIST_OLD | HIST_READ;
+	if (readflags & HFILE_FAST)
+	    newflags |= HIST_FOREIGN;
+	if (readflags & HFILE_SKIPOLD
+	 || (hist_ignore_all_dups && newflags & hist_skip_flags))
+	    newflags |= HIST_MAKEUNIQUE;
+	while (fpos = ftell(in), fgets(buf, bufsiz, in)) {
 	    int l = strlen(buf);
-	    char *pt, *start;
+	    char *pt;
 
 	    while (l) {
 		while (buf[l - 1] != '\n') {
@@ -1484,114 +1722,184 @@ readhistfile(char *s, int err)
 			l++;
 			break;
 		    }
-		    l = strlen(buf);
+		    l += strlen(buf+l);
 		}
 		buf[l - 1] = '\0';
 		if (l > 1 && buf[l - 2] == '\\') {
-		    buf[l - 2] = '\n';
-		    fgets(buf + l - 1, bufsiz - (l - 1), in);
-		    l = strlen(buf);
+		    buf[--l - 1] = '\n';
+		    fgets(buf + l, bufsiz - l, in);
+		    l += strlen(buf+l);
 		} else
 		    break;
 	    }
 
-	    ent = gethistent(++curhist);
 	    pt = buf;
 	    if (*pt == ':') {
 		pt++;
-		ent->stim = zstrtol(pt, NULL, 0);
+		stim = zstrtol(pt, NULL, 0);
 		for (; *pt != ':' && *pt; pt++);
 		if (*pt) {
 		    pt++;
-		    ent->ftim = zstrtol(pt, NULL, 0);
+		    ftim = zstrtol(pt, NULL, 0);
 		    for (; *pt != ';' && *pt; pt++);
 		    if (*pt)
 			pt++;
-		} else {
-		    ent->ftim = tim;
-		}
-		if (ent->stim == 0)
-		    ent->stim = tim;
-		if (ent->ftim == 0)
-		    ent->ftim = tim;
+		} else
+		    ftim = stim;
 	    } else {
-		ent->ftim = ent->stim = tim;
+		if (*pt == '\\' && pt[1] == ':')
+		    pt++;
+		stim = ftim = 0;
 	    }
 
-	    zsfree(ent->text);
-	    ent->text = ztrdup(pt);
-	    ent->flags = HIST_OLD|HIST_READ;
-	    if (ent->nwords)
-		zfree(ent->words, ent->nwords*2*sizeof(short));
+	    if (searching) {
+		if (searching > 0) {
+		    if (stim == lasthist.stim
+		     && histstrcmp(pt, lasthist.text) == 0)
+			searching = 0;
+		    else {
+			fseek(in, 0, 0);
+			histfile_linect = 0;
+			searching = -1;
+		    }
+		    continue;
+		}
+		else if (stim < lasthist.stim) {
+		    histfile_linect++;
+		    continue;
+		}
+		searching = 0;
+	    }
+
+	    if (readflags & HFILE_USE_OPTIONS) {
+		histfile_linect++;
+		lasthist.fpos = fpos;
+		lasthist.stim = stim;
+	    }
+
+	    he = prepnexthistent(++curhist);
+	    he->text = ztrdup(pt);
+	    he->flags = newflags;
+	    if ((he->stim = stim) == 0)
+		he->stim = he->ftim = tim;
+	    else if (ftim < stim)
+		he->ftim = stim + ftim;
+	    else
+		he->ftim = ftim;
 
 	    /* Divide up the words.  We don't know how it lexes,
-	       so just look for spaces.
+	       so just look for white-space.
 	       */
 	    nwordpos = 0;
 	    start = pt;
 	    do {
-		while (*pt == ' ')
+		while (inblank(*pt))
 		    pt++;
 		if (*pt) {
 		    if (nwordpos >= nwordlist)
 			wordlist = (short *) realloc(wordlist,
-					(nwordlist += 16)*sizeof(short));
+					(nwordlist += 64)*sizeof(short));
 		    wordlist[nwordpos++] = pt - start;
-		    while (*pt && *pt != ' ')
+		    while (*pt && !inblank(*pt))
 			pt++;
 		    wordlist[nwordpos++] = pt - start;
 		}
 	    } while (*pt);
 
-	    ent->nwords = nwordpos/2;
-	    if (ent->nwords) {
-		ent->words = (short *)zalloc(nwordpos*sizeof(short));
-		memcpy(ent->words, wordlist, nwordpos*sizeof(short));
+	    he->nwords = nwordpos/2;
+	    if (he->nwords) {
+		he->words = (short *)zalloc(nwordpos*sizeof(short));
+		memcpy(he->words, wordlist, nwordpos*sizeof(short));
 	    } else
-		ent->words = (short *)NULL;
+		he->words = (short *)NULL;
+	    addhistnode(histtab, he->text, he);
+	    if (hist_ring != he)
+		curhist--; /* We discarded a foreign duplicate */
+	}
+	if (start && readflags & HFILE_USE_OPTIONS) {
+	    zsfree(lasthist.text);
+	    lasthist.text = ztrdup(start);
 	}
-	fclose(in);
-
 	zfree(wordlist, nwordlist*sizeof(short));
 	zfree(buf, bufsiz);
+
+	fclose(in);
     } else if (err)
-	zerr("can't read history file", s, 0);
+	zerr("can't read history file", fn, 0);
+
+    unlockhistfile(fn);
 }
 
 /**/
 void
-savehistfile(char *s, int err, int app)
+savehistfile(char *fn, int err, int writeflags)
 {
-    char *t;
+    char *t, *start = NULL;
     FILE *out;
-    int ev;
-    Histent ent;
+    Histent he;
+    int xcurhist = curhist - !!(histactive & HA_ACTIVE);
     int savehist = getiparam("SAVEHIST");
+    int extended_history = isset(EXTENDEDHISTORY);
 
-    if (!s || !interact || savehist <= 0)
+    if (!interact || savehist <= 0 || !hist_ring
+     || (!fn && !(fn = getsparam("HISTFILE"))))
 	return;
-    ev = curhist - savehist + 1;
-    if (ev < firsthist())
-	ev = firsthist();
-    if (app & 1)
-	out = fdopen(open(unmeta(s),
-		     O_CREAT | O_WRONLY | O_APPEND | O_NOCTTY, 0600), "a");
-    else
-	out = fdopen(open(unmeta(s),
-		     O_CREAT | O_WRONLY | O_TRUNC | O_NOCTTY, 0600), "w");
+    if (writeflags & HFILE_FAST) {
+	he = gethistent(lasthist.next_write_ev, GETHIST_DOWNWARD);
+	while (he && he->flags & HIST_OLD) {
+	    lasthist.next_write_ev = he->histnum + 1;
+	    he = down_histent(he);
+	}
+	if (!he || !lockhistfile(fn, 0))
+	    return;
+	if (histfile_linect > savehist + savehist / 5)
+	    writeflags &= ~HFILE_FAST;
+    }
+    else {
+	if (!lockhistfile(fn, 1))
+	    return;
+	he = hist_ring->down;
+    }
+    if (writeflags & HFILE_USE_OPTIONS) {
+	if (isset(APPENDHISTORY) || isset(INCAPPENDHISTORY)
+	 || isset(SHAREHISTORY))
+	    writeflags |= HFILE_APPEND | HFILE_SKIPOLD;
+	else
+	    histfile_linect = 0;
+	if (isset(HISTSAVENODUPS))
+	    writeflags |= HFILE_SKIPDUPS;
+	if (isset(SHAREHISTORY))
+	    extended_history = 1;
+    }
+    if (writeflags & HFILE_APPEND) {
+	out = fdopen(open(unmeta(fn),
+			O_CREAT | O_WRONLY | O_APPEND | O_NOCTTY, 0600), "a");
+    }
+    else {
+	out = fdopen(open(unmeta(fn),
+			 O_CREAT | O_WRONLY | O_TRUNC | O_NOCTTY, 0600), "w");
+    }
     if (out) {
-	for (; ev <= curhist - !!(histactive & HA_ACTIVE); ev++) {
-	    ent = gethistent(ev);
-	    if (app & 2) {
-		if (ent->flags & HIST_OLD)
+	for (; he && he->histnum <= xcurhist; he = down_histent(he)) {
+	    if ((writeflags & HFILE_SKIPDUPS && he->flags & HIST_DUP)
+	     || (writeflags & HFILE_SKIPFOREIGN && he->flags & HIST_FOREIGN))
+		continue;
+	    if (writeflags & HFILE_SKIPOLD) {
+		if (he->flags & HIST_OLD)
 		    continue;
-		ent->flags |= HIST_OLD;
+		he->flags |= HIST_OLD;
+		if (writeflags & HFILE_USE_OPTIONS)
+		    lasthist.next_write_ev = he->histnum + 1;
 	    }
-	    t = ent->text;
-	    if (isset(EXTENDEDHISTORY)) {
-		fprintf(out, ": %ld:%ld;",
-			(long)ent->stim,
-			(long)ent->ftim);
+	    if (writeflags & HFILE_USE_OPTIONS) {
+		lasthist.fpos = ftell(out);
+		lasthist.stim = he->stim;
+		histfile_linect++;
+	    }
+	    t = start = he->text;
+	    if (extended_history) {
+		fprintf(out, ": %ld:%ld;", (long)he->stim,
+			he->ftim? (long)(he->ftim - he->stim) : 0L);
 	    } else if (*t == ':')
 		fputc('\\', out);
 
@@ -1602,69 +1910,188 @@ savehistfile(char *s, int err, int app)
 	    }
 	    fputc('\n', out);
 	}
+	if (start && writeflags & HFILE_USE_OPTIONS) {
+	    struct stat sb;
+	    fflush(out);
+	    if (fstat(fileno(out), &sb) == 0) {
+		lasthist.fsiz = sb.st_size;
+		lasthist.mtim = sb.st_mtime;
+	    }
+	    zsfree(lasthist.text);
+	    lasthist.text = ztrdup(start);
+	}
 	fclose(out);
 
-	if (app & 2 && (out = fopen(unmeta(s), "r"))) {
-	    char **store, buf[1024], **ptr;
-	    int i, l, histnum = 0;
-
-	    store = (char **)zcalloc((savehist + 1) * sizeof *store);
-	    while (fgets(buf, sizeof(buf), out)) {
-		char *t;
-
-		if (store[i = histnum % savehist])
-		    free(store[i]);
-		store[i] = ztrdup(buf);
-		l = strlen(buf);
-		if (l > 1) {
-		    t = store[i] + l;
-		    while ((t[-1] != '\n' ||
-			    (t[-1] == '\n' && t[-2] == '\\')) &&
-			   fgets(buf, sizeof(buf), out)) {
-			l += strlen(buf);
-			store[i] = zrealloc(store[i], l + 1);
-			t = store[i] + l;
-			strcat(store[i], buf);
-		    }
-		}
-		histnum++;
-	    }
-	    fclose(out);
-	    if ((out = fdopen(open(unmeta(s),
-			    O_WRONLY | O_TRUNC | O_NOCTTY, 0600), "w"))) {
-		if (histnum < savehist)
-		    for (i = 0; i < histnum; i++)
-			fprintf(out, "%s", store[i]);
-		else
-		    for (i = histnum; i < histnum + savehist; i++)
-			fprintf(out, "%s", store[i % savehist]);
-		fclose(out);
-	    }
-	    for (ptr = store; *ptr; ptr++)
-		zsfree(*ptr);
-	    free(store);
+	if ((writeflags & (HFILE_SKIPOLD | HFILE_FAST)) == HFILE_SKIPOLD) {
+	    HashTable remember_histtab = histtab;
+	    Histent remember_hist_ring = hist_ring;
+	    int remember_histlinect = histlinect;
+	    int remember_curhist = curhist;
+
+	    hist_ring = NULL;
+	    curhist = histlinect = 0;
+	    histsiz = savehist;
+	    createhisttable(); /* sets histtab */
+
+	    hist_ignore_all_dups |= isset(HISTSAVENODUPS);
+	    readhistfile(fn, err, 0);
+	    hist_ignore_all_dups = isset(HISTIGNOREALLDUPS);
+	    savehistfile(fn, err, 0);
+	    deletehashtable(histtab);
+
+	    curhist = remember_curhist;
+	    histlinect = remember_histlinect;
+	    hist_ring = remember_hist_ring;
+	    histtab = remember_histtab;
 	}
     } else if (err)
-	zerr("can't write history file %s", s, 0);
+	zerr("can't write history file %s", fn, 0);
+
+    unlockhistfile(fn);
 }
 
+static int lockhistct;
+
 /**/
 int
-firsthist(void)
+lockhistfile(char *fn, int keep_trying)
 {
-    int ev;
-    Histent ent;
+    int ct = lockhistct;
 
-    ev = curhist - histentct + 1;
-    if (ev < 1)
-	ev = 1;
-    do {
-	ent = gethistent(ev);
-	if (ent->text)
-	    break;
-	ev++;
+    if (!fn && !(fn = getsparam("HISTFILE")))
+	return 0;
+    if (!lockhistct++) {
+	struct stat sb;
+	int fd, len = strlen(fn);
+	char *tmpfile, *lockfile;
+
+#ifdef HAVE_LINK
+	tmpfile = zalloc(len + 10 + 1);
+	sprintf(tmpfile, "%s.%ld", fn, (long)mypid);
+	if ((fd = open(tmpfile, O_RDWR|O_CREAT|O_EXCL, 0644)) >= 0) {
+	    write(fd, "0\n", 2);
+	    close(fd);
+	    lockfile = zalloc(len + 5 + 1);
+	    sprintf(lockfile, "%s.LOCK", fn);
+	    while (link(tmpfile, lockfile) < 0) {
+		if (stat(lockfile, &sb) < 0) {
+		    if (errno == ENOENT)
+			continue;
+		}
+		else if (keep_trying) {
+		    if (time(NULL) - sb.st_mtime < 10)
+			sleep(1);
+		    else
+			unlink(lockfile);
+		    continue;
+		}
+		lockhistct--;
+		break;
+	    }
+	    free(lockfile);
+	}
+	unlink(tmpfile);
+	free(tmpfile);
+#else /* not HAVE_LINK */
+	lockfile = zalloc(len + 5 + 1);
+	sprintf(lockfile, "%s.LOCK", fn);
+	while ((fd = open(lockfile, O_CREAT|O_EXCL, 0644)) < 0) {
+		if (errno == EEXIST) continue;
+		else if (keep_trying) {
+		    if (time(NULL) - sb.st_mtime < 10)
+			sleep(1);
+		    continue;
+		}
+		lockhistct--;
+		break;
+	}
+	free(lockfile);
+#endif /* HAVE_LINK */
+    }
+    return ct != lockhistct;
+}
+
+/* Unlock the history file if this corresponds to the last nested lock
+ * request.  If we don't have the file locked, just return.
+ */
+
+/**/
+void
+unlockhistfile(char *fn)
+{
+    if (!fn && !(fn = getsparam("HISTFILE")))
+	return;
+    if (--lockhistct) {
+	if (lockhistct < 0)
+	    lockhistct = 0;
+    }
+    else {
+	char *lockfile = zalloc(strlen(fn) + 5 + 1);
+	sprintf(lockfile, "%s.LOCK", fn);
+	unlink(lockfile);
+	free(lockfile);
     }
-    while (ev < curhist);
-    return ev;
 }
 
+/* Get the words in the current buffer. Using the lexer. */
+
+/**/
+mod_export LinkList
+bufferwords(int *index)
+{
+    LinkList list = newlinklist();
+    int num = 0, cur = -1, got = 0, ne = noerrs, ocs = cs;
+    char *p;
+
+    zleparse = 1;
+    addedx = 0;
+    noerrs = 1;
+    lexsave();
+    if (!isfirstln && chline) {
+	p = (char *) zhalloc(hptr - chline + ll + 2);
+	memcpy(p, chline, hptr - chline);
+	memcpy(p + (hptr - chline), line, ll);
+	p[(hptr - chline) + ll] = ' ';
+	p[(hptr - chline) + ll + 1] = '\0';
+	inpush(p, 0, NULL);
+	cs += hptr - chline;
+    } else {
+	p = (char *) zhalloc(ll + 2);
+	memcpy(p, line, ll);
+	p[ll] = ' ';
+	p[ll + 1] = '\0';
+	inpush(p, 0, NULL);
+    }
+    if (cs)
+	cs--;
+    strinbeg(0);
+    noaliases = 1;
+    do {
+	ctxtlex();
+	if (tok == ENDINPUT || tok == LEXERR)
+	    break;
+	if (tokstr && *tokstr) {
+	    untokenize((p = dupstring(tokstr)));
+	    addlinknode(list, p);
+	    num++;
+	}
+	if (!got && !zleparse) {
+	    got = 1;
+	    cur = num - 1;
+	}
+    } while (tok != ENDINPUT && tok != LEXERR);
+    if (cur < 0 && num)
+	cur = num - 1;
+    noaliases = 0;
+    strinend();
+    inpop();
+    errflag = zleparse = 0;
+    noerrs = ne;
+    lexrestore();
+    cs = ocs;
+
+    if (index)
+	*index = cur;
+
+    return list;
+}