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

1 files changed, 719 insertions, 292 deletions

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;
+}