/* $Header: /home/agc/src/ssam-1.9/RCS/ssam.c,v 1.128 1997/10/21 10:06:16 agc Exp agc $ */

/*
 * Copyright © 1996-1997 Alistair G. Crooks.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by Alistair G. Crooks.
 * 4. The name of the author may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
#include <config.h>

#ifdef HAVE_SYS_TYPES_H
#include <sys/types.h>
#endif

#ifdef HAVE_SYS_STAT_H
#include <sys/stat.h>
#endif

#include <stdio.h>
#include <ctype.h>

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif

#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif

#ifdef HAVE_STRING_H
#include <string.h>
#endif

#include <agc.h>

#include "ure.h"
#include "ssam.h"

/* macros to get subscripts in buffer */
#define AFTSUB(fp, n)	((fp)->f_buf[n])
#define BEFSUB(fp, n)	((fp)->f_buf[(fp)->f_size - (n) - 1])

/* forward declarations */
static int rec_address(ssam_t *sp, char *s, int *pos);
static int rec_cmd_or_addr(ssam_t *sp, char *s, int *pos);
static int rec_cmd(ssam_t *sp, char *s, int *pos);
static int rec_block(ssam_t *sp, char *s, int *pos);

static int samcmd(ssam_t *sp, context_t *dot, int *cmdp);

/* Error messages - correspond to Error constants */
static char	*errmsgs[] = {
	"Unknown error",
	"No such command",
	"Nothing to do",
	"No target address specified",
	"No sub-command specified",
	"Invalid address",
	"Bad UTF regular expression",
	"Bad file specification",
	"Bad line number",
	"Change stack corruption - internal error",
	"Can't write to stdout",
	"Too many '}' found",
	"Too many '{' found"
};

/* global parsing error message printing - then die */
static void
Error(ssam_t *sp, int err, char *s, int pos)
{
	char	*msg;

	msg = (err >= 0 && err < LastError) ? errmsgs[err] : "Unknown error";
	(void) fprintf(stderr, "ssam parse error: %s at %.*s\n", msg, pos, s);
	longjmp(sp->s_escape, err);
}

/* global runtime error messaging function */
static void
RunError(ssam_t *sp, int err, cmd_t *cmdp, char *fmt, long arg)
{
	char	*msg;

	msg = (err >= 0 && err < LastError) ? errmsgs[err] : "Unknown error";
	(void) fprintf(stderr, "ssam run-time error: %s at %.*s, ", msg, cmdp->c_pos, cmdp->c_line);
	(void) fprintf(stderr, fmt, arg);
	(void) fputc('\n', stderr);
	longjmp(sp->s_escape, err);
}

/* initial allocation size */
#ifndef CHUNKSIZE
#define CHUNKSIZE	256
#endif

/*
 * We keep a stack of changes, and add to the stack. At the end
 * of the scanning phase, each change is popped off the stack
 * and then the modification is made. This ensures that the
 * scanning phase sees the file in its original form. By stacking
 * changes, we ensure that addresses are correct, as modifications
 * are made from the back of the file towards the front.
 *
 * One side effect of this is that address ranges to the 'm' and
 * 't' commands can overlap their target addresses, as no textual
 * changes take place until after the scanning phase.
 */

#ifndef HAVE_MEMMOVE
/* overlapping-safe memory move function */
static char *
memmove(char *dst, char *src, int nbytes)
{
        char    *ret;
 
        if ((ret = dst) >= src && dst <= &src[nbytes]) {
                for (dst += nbytes, src += nbytes ; nbytes-- > 0 ; ) {
                        *--dst = *--src;
                }
        } else {
                while (nbytes-- > 0) {
                        *dst++ = *src++;
                }
        }
        return ret;
}
#endif

/* save `n' chars of `s' in malloc'd memory */
static char *
strnsave(char *s, int n)
{
	char	*cp;

	NEWARRAY(char, cp, n + 1, exit(1));
	(void) memmove(cp, s, n);
	cp[n] = 0;
	return cp;
}

/* open a file in a buffer gap structure */
static f_t *
f_open(ssam_t *sp, char *f)
{
	struct stat	s;
	FILE		*filep;
	char		*cp;
	long		cc;
	int		i;

	filep = (FILE *) NULL;
	if (f != (char *) NULL && (filep = fopen(f, "r")) == (FILE *) NULL) {
		return (f_t *) NULL;
	}
	for (i = 0 ; i < sp->s_fsize && sp->s_fv[i] ; i++) {
	}
	if (i == sp->s_fsize) {
		if (sp->s_fsize == 0) {
			sp->s_fsize = CHUNKSIZE;
			NEWARRAY(f_t *, sp->s_fv, sp->s_fsize, exit(1));
		} else {
			sp->s_fsize *= 2;
			RENEW(f_t *, sp->s_fv, sp->s_fsize, exit(1));
		}
	}
	NEW(f_t, sp->s_fv[i], exit(1));
	if (f == (char *) NULL) {
		sp->s_fv[i]->f_size = 4096;
		NEWARRAY(char, sp->s_fv[i]->f_buf, sp->s_fv[i]->f_size, exit(1));
	} else {
		(void) fstat(fileno(filep), &s);
		sp->s_fv[i]->f_size = (int) ((s.st_size / 4096) + 1) * 4096;
		NEWARRAY(char, sp->s_fv[i]->f_buf, sp->s_fv[i]->f_size, exit(1));
		cc = fread(&BEFSUB(sp->s_fv[i], s.st_size), sizeof(char),
							s.st_size, filep);
		(void) fclose(filep);
		if (cc != s.st_size) {
			FREE(sp->s_fv[i]->f_buf);
			FREE(sp->s_fv[i]);
			return (f_t *) NULL;
		}
		sp->s_fv[i]->f_name = strnsave(f, utfbytes(f));
		sp->s_fv[i]->f_bbc = s.st_size;
		cp = &BEFSUB(sp->s_fv[i], cc);
		for (;;) {
			if ((cp = utfrune(cp, '\n')) == (char *) NULL) {
				break;
			}
			sp->s_fv[i]->f_blc++;
			cp++;
		}
		sp->s_fv[i]->f_bcc = utfnlen(&BEFSUB(sp->s_fv[i], cc), cc);
	}
	sp->s_fc++;
	return sp->s_fv[i];
}

/* close a buffer gapped file */
static void
f_close(ssam_t *sp, f_t *fp)
{
	int	i;

	for (i = 0 ; i < sp->s_fsize && sp->s_fv[i] != fp ; i++) {
	}
	if (i < sp->s_fsize) {
		sp->s_fv[i] = (f_t *) NULL;
		FREE(fp->f_buf);
		FREE(fp);
	}
}

/* move forwards `n' chars/bytes in a buffer gap */
static int
f_forwards(f_t *fp, int n, int type)
{
	Rune	r;
	int	rlen;

	switch(type) {
	case BGChar:
		if (fp->f_bcc >= n) {
			while (n-- > 0) {
				rlen = chartorune(&r, &BEFSUB(fp, fp->f_bbc));
				if (rlen == 1) {
					AFTSUB(fp, fp->f_abc) = BEFSUB(fp, fp->f_bbc);
				} else {
					(void) memmove(&AFTSUB(fp, fp->f_abc), &BEFSUB(fp, fp->f_bbc), rlen);
				}
				fp->f_acc++;
				fp->f_bcc--;
				fp->f_abc += rlen;
				fp->f_bbc -= rlen;
				if (r == '\n') {
					fp->f_alc++;
					fp->f_blc--;
				}
			}
			return 1;
		}
		break;
	case BGByte:
		if (fp->f_bbc >= n) {
			for ( ; n > 0 ; n -= rlen) {
				rlen = chartorune(&r, &BEFSUB(fp, fp->f_bbc));
				if (rlen == 1) {
					AFTSUB(fp, fp->f_abc) = BEFSUB(fp, fp->f_bbc);
				} else {
					(void) memmove(&AFTSUB(fp, fp->f_abc), &BEFSUB(fp, fp->f_bbc), rlen);
				}
				fp->f_acc++;
				fp->f_bcc--;
				fp->f_abc += rlen;
				fp->f_bbc -= rlen;
				if (r == '\n') {
					fp->f_alc++;
					fp->f_blc--;
				}
			}
			return 1;
		}
	}
	return 0;
}

/* move backwards `n' chars in a buffer gap */
static int
f_backwards(f_t *fp, int n, int type)
{
	Rune	r;
	int	rlen;

	switch(type) {
	case BGChar:
		if (fp->f_acc >= n) {
			while (n-- > 0) {
				rlen = priorrune(&r, &AFTSUB(fp, fp->f_abc));
				fp->f_bcc++;
				fp->f_acc--;
				fp->f_bbc += rlen;
				fp->f_abc -= rlen;
				if (rlen == 1) {
					BEFSUB(fp, fp->f_bbc) = AFTSUB(fp, fp->f_abc);
				} else {
					(void) memmove(&BEFSUB(fp, fp->f_bbc), &AFTSUB(fp, fp->f_abc), rlen);
				}
				if (r == '\n') {
					fp->f_blc++;
					fp->f_alc--;
				}
			}
			return 1;
		}
		break;
	case BGByte:
		if (fp->f_acc >= n) {
			for ( ; n > 0 ; n -= rlen) {
				rlen = priorrune(&r, &AFTSUB(fp, fp->f_abc));
				fp->f_bcc++;
				fp->f_acc--;
				fp->f_bbc += rlen;
				fp->f_abc -= rlen;
				if (rlen == 1) {
					BEFSUB(fp, fp->f_bbc) = AFTSUB(fp, fp->f_abc);
				} else {
					(void) memmove(&BEFSUB(fp, fp->f_bbc), &AFTSUB(fp, fp->f_abc), rlen);
				}
				if (r == '\n') {
					fp->f_blc++;
					fp->f_alc--;
				}
			}
			return 1;
		}
	}
	return 0;
}

/* move within a buffer gap */
static int
f_seek(f_t *fp, long off, int whence, int type)
{
	switch(type) {
	case BGLine:
		switch(whence) {
		case BGFromBOF:
			if (off < 0 || off > fp->f_alc + fp->f_blc) {
				return 0;
			}
			if (off < fp->f_alc) {
				while (off <= fp->f_alc && f_backwards(fp, 1, BGChar)) {
				}
				if (off > 0) {
					(void) f_forwards(fp, 1, BGChar);
				}
			} else if (off > fp->f_alc) {
				while (off > fp->f_alc && f_forwards(fp, 1, BGChar)) {
				}
			}
			return 1;
		case BGFromHere:
			return f_seek(fp, fp->f_alc + off, BGFromBOF, BGLine);
		case BGFromEOF:
			return f_seek(fp, fp->f_alc + fp->f_blc + off, BGFromBOF, BGLine);
		}
		break;
	case BGChar:
		switch(whence) {
		case BGFromBOF:
			if (off < 0 || off > fp->f_acc + fp->f_bcc) {
				return 0;
			}
			if (off < fp->f_acc) {
				return f_backwards(fp, fp->f_acc - off, BGChar);
			} else if (off > fp->f_acc) {
				return f_forwards(fp, off - fp->f_acc, BGChar);
			}
			return 1;
		case BGFromHere:
			return f_seek(fp, fp->f_acc + off, BGFromBOF, BGChar);
		case BGFromEOF:
			return f_seek(fp, fp->f_acc + fp->f_bcc + off, BGFromBOF, BGChar);
		}
		break;
	case BGByte:
		switch(whence) {
		case BGFromBOF:
			if (off < 0 || off > fp->f_abc + fp->f_bbc) {
				return 0;
			}
			if (off < fp->f_abc) {
				return f_backwards(fp, fp->f_abc - off, BGByte);
			} else if (off > fp->f_abc) {
				return f_forwards(fp, off - fp->f_abc, BGByte);
			}
			return 1;
		case BGFromHere:
			return f_seek(fp, fp->f_abc + off, BGFromBOF, BGByte);
		case BGFromEOF:
			return f_seek(fp, fp->f_abc + fp->f_bbc + off, BGFromBOF, BGByte);
		}
		break;
	}
	return 0;
}

/* return a pointer to the text in the buffer gap */
static char *
f_getstr(f_t *fp)
{
	return &BEFSUB(fp, fp->f_bbc);
}

/* return offset in a buffer gap */
static long
f_tell(f_t *fp, int type)
{
	return (type == BGLine) ? fp->f_alc : (type == BGByte) ? fp->f_abc : fp->f_acc;
}

/* return size of buffer gap */
static long
f_size(f_t *fp, int type)
{
	return (type == BGLine) ? fp->f_alc + fp->f_blc : fp->f_acc + fp->f_bcc;
}

/* insert `n' chars of `s' in a buffer gap */
static int
f_insert(f_t *fp, char *s, int n)
{
	Rune	r;
	long	off;
	int	rlen;
	int	i;

	for (i = 0 ; i < n ; i += rlen) {
		if (fp->f_bbc + fp->f_abc == fp->f_size) {
			off = f_tell(fp, BGChar);
			(void) f_seek(fp, 0, BGFromEOF, BGChar);
			fp->f_size *= 2;
			RENEW(char, fp->f_buf, fp->f_size, exit(1));
			(void) f_seek(fp, off, BGFromBOF, BGChar);
		}
		if ((rlen = chartorune(&r, s)) == 1) {
			AFTSUB(fp, fp->f_abc) = *s;
		} else {
			(void) memmove(&AFTSUB(fp, fp->f_abc), s, rlen);
		}
		if (r == '\n') {
			fp->f_alc++;
		}
		fp->f_modified = 1;
		fp->f_abc += rlen;
		fp->f_acc++;
		s += rlen;
	}
	return 1;
}

/* delete `n' bytes from the buffer gap */
static int
f_delete(f_t *fp, int n)
{
	Rune	r;
	int	rlen;
	int	i;

	if (n <= fp->f_bbc) {
		for (i = 0 ; i < n ; i += rlen) {
			rlen = chartorune(&r, &BEFSUB(fp, fp->f_bbc));
			if (r == '\n') {
				fp->f_blc--;
			}
			fp->f_bbc -= rlen;
			fp->f_bcc--;
			fp->f_modified = 1;
		}
		return 1;
	}
	return 0;
}

/* look at a character in a buffer gap `delta' UTF chars away */
static int
f_peek(f_t *fp, long delta)
{
	int	ch;

	if (delta != 0) {
		if (!f_seek(fp, delta, BGFromHere, BGChar)) {
			return -1;
		}
	}
	ch = BEFSUB(fp, fp->f_bbc);
	if (delta != 0) {
		(void) f_seek(fp, -delta, BGFromHere, BGChar);
	}
	return ch;
}

/* return, in malloc'd storage, text from the buffer gap */
static char *
f_gettext(f_t *fp, long from, long to)
{
	char	*text;
	long	off;
	long	n;

	off = f_tell(fp, BGChar);
	NEWARRAY(char, text, (to - from + 1), exit(1));
	(void) f_seek(fp, from, BGFromBOF, BGChar);
	for (n = 0 ; n < to - from ; n++) {
		text[n] = BEFSUB(fp, fp->f_bbc - n);
	}
	text[n] = 0;
	(void) f_seek(fp, off, BGFromBOF, BGChar);
	return text;
}

/* return 1 if we wrote the file correctly */
static int
f_write(f_t *fp, FILE *filep)
{
	if (fwrite(fp->f_buf, sizeof(char), fp->f_abc, filep) != fp->f_abc) {
		return 0;
	}
	if (fwrite(&BEFSUB(fp, fp->f_bbc), sizeof(char), fp->f_bbc, filep) != fp->f_bbc) {
		return 0;
	}
	return 1;
}

/* make a tag line from a buffer gap */
static void
maketag(char *buf, int n, f_t *fp, f_t *fcurr)
{
	/* note use of dirty flag here - it means changes are pending */
	/* f_modified is used by low-level buffer gap routines */
	buf[0] = (fp->f_dirty) ? '\'' : ' ';
	buf[1] = '-';
	buf[2] = (fp == fcurr) ? '.' : ' ';
	buf[3] = ' ';
	(void) utfncpy(&buf[4], (fp->f_name == (char *) NULL) ? "<stdin>" : fp->f_name, n - 5);
	buf[n - 1] = 0;
}

/* set a context structure */
static void
setcontext(context_t *dot, f_t *fp, long from, long to, int type)
{
	dot->c_fp = fp;
	switch(type) {
	case BGChar:
		dot->c_r.r_from = from;
		dot->c_r.r_to = to;
		break;
	case BGByte:
		(void) f_seek(dot->c_fp, from, BGFromBOF, BGByte);
		dot->c_r.r_from = f_tell(dot->c_fp, BGChar);
		(void) f_seek(dot->c_fp, to, BGFromBOF, BGByte);
		dot->c_r.r_to = f_tell(dot->c_fp, BGChar);
		break;
	}
}

/* push a change onto the change stack */
static void
pushchange(ssam_t *sp, f_t *fp, long from, long to, char type, int cc, char *s)
{
	if (sp->s_chgsize == 0) {
		sp->s_chgsize = CHUNKSIZE;
		NEWARRAY(change_t, sp->s_chgv, sp->s_chgsize, exit(1));
	} else if (sp->s_chgc == sp->s_chgsize) {
		sp->s_chgsize *= 2;
		RENEW(change_t, sp->s_chgv, sp->s_chgsize, exit(1));
	}
	fp->f_dirty = 1;
	sp->s_chgv[sp->s_chgc].ch_type = type;
	sp->s_chgv[sp->s_chgc].ch_r.r_from = from;
	sp->s_chgv[sp->s_chgc].ch_r.r_to = to;
	if ((sp->s_chgv[sp->s_chgc].ch_c = cc) > 0) {
		sp->s_chgv[sp->s_chgc].ch_v = strnsave(s, cc);
	}
	sp->s_chgv[sp->s_chgc++].ch_fp = fp;
}

/* generic change_t comparison function */
static int
chgcmp(const void *vp1, const void *vp2)
{
	change_t	*cp1 = (change_t *) vp1;
	change_t	*cp2 = (change_t *) vp2;
	int		i;

	if (cp1->ch_fp != cp2->ch_fp) {
		return (int)(cp1->ch_fp - cp2->ch_fp);
	}
	if ((i = cp1->ch_r.r_from - cp2->ch_r.r_from) == 0) {
		/* Order the insertion `before' the deletion in the array */
		/* Remember that this is stacked, so del really happens first */
		i = (cp1->ch_type == 'i') ? -1 : 1;
	}
	return i;
}

/* sort the changes so that ordering in file is consistent */
static void
sortchanges(ssam_t *sp)
{
	qsort(sp->s_chgv, sp->s_chgc, sizeof(change_t), chgcmp);
}

/* pop the changes from the change stack, and perform those changes */
static int
popchanges(ssam_t *sp)
{
	change_t	*cp;
	int		i;

	sortchanges(sp);
	for (i = sp->s_chgc - 1, cp = &sp->s_chgv[i] ; i >= 0 ; --i, --cp) {
		if (!f_seek(cp->ch_fp, cp->ch_r.r_from, BGFromBOF, BGChar)) {
			return 0;
		}
		switch(cp->ch_type) {
		case 'd':
			if (!f_delete(cp->ch_fp,
					cp->ch_r.r_to - cp->ch_r.r_from)) {
				return 0;
			}
			break;
		case 'i':
			if (!f_insert(cp->ch_fp, cp->ch_v, cp->ch_c)) {
				return 0;
			}
		}
	}
	return 1;
}

/* return 1 if any changes have been made */
static int
changed(ssam_t *sp)
{
	return sp->s_chgc > 0;
}

/* substitute text */
static void
subst(ssam_t *sp, context_t *dot, cmd_t *cmdp, urematch_t *mv)
{
	char	*repl;
	char	*text;
	char	*s2;
	char	*s;
	long	off;
	int	replsize;
	int	replc;
	int	n;
	int	i;

	replsize = CHUNKSIZE;
	NEWARRAY(char, repl, replsize, exit(1));
	replc = 0;
	for (off = dot->c_r.r_from, s = cmdp->c_argv[1] ; s < &cmdp->c_argv[1][cmdp->c_iargv[1]] ; off++) {
		if (replc == replsize) {
			replsize *= 2;
			RENEW(char, repl, replsize, exit(1));
		}
		if (*s == '\\' && isdigit(*(s + 1))) {
			for (n = 0, s++ ; s < &cmdp->c_argv[1][cmdp->c_iargv[1]] && isdigit(*s) ; s++) {
				n = (n * 10) + (*s - '0');
			}
			if (mv[n].rm_so != (ureoff_t) -1) {
				s2 = text = f_gettext(dot->c_fp, mv[n].rm_so,
								mv[n].rm_eo);
				for (i = mv[n].rm_so ; i < mv[n].rm_eo ; i++) {
					if (replc == replsize) {
						replsize *= 2;
						RENEW(char, repl, replsize, exit(1));
					}
					repl[replc++] = *s2++;
				}
				FREE(text);
			}
		} else {
			repl[replc++] = *s++;
		}
	}
	pushchange(sp, dot->c_fp, mv[0].rm_so, mv[0].rm_eo, 'i', replc, repl);
	FREE(repl);
}

/* check there's enough space for match offsets */
/* return the subscript of base of matches */
static int
pushmatch(ssam_t *sp, ure_t *up)
{
	int	ret;

	if (sp->s_matchsize == 0) {
		sp->s_matchsize = CHUNKSIZE;
		NEWARRAY(urematch_t, sp->s_matchv, sp->s_matchsize, exit(1));
	} else if (sp->s_matchc + up->u_subc >= sp->s_matchsize) {
		sp->s_matchsize *= 2;
		RENEW(urematch_t, sp->s_matchv, sp->s_matchsize, exit(1));
	}
	ret = sp->s_matchc;
	sp->s_matchc += up->u_subc;
	return ret;
}

/* pop the match structures we've just used */
static void
popmatch(ssam_t *sp, ure_t *up)
{
	sp->s_matchc -= up->u_subc;
}

/* find file */
static void
findfile(ssam_t *sp, context_t *ndot, int cmd)
{
	ure_t		*up;
	int		base;
	char		buf[BUFSIZ];
	int		i;

	base = pushmatch(sp, up = &sp->s_progv[cmd].c_u);
	for (i = 0 ; i < sp->s_fsize ; i++) {
		if (sp->s_fv[i] != (f_t *) NULL) {
			maketag(buf, sizeof(buf), sp->s_fv[i], sp->s_fcurr);
			if (ureexec(up, buf,
					up->u_subc, &sp->s_matchv[base], 0, sp->s_collseq) == URE_SUCCESS) {
				break;
			}
		}
	}
	popmatch(sp, up);
	if (i == sp->s_fsize) {
		RunError(sp, ErrBadFilespec, &sp->s_progv[cmd], "No such file", 0);
	}
	setcontext(ndot, sp->s_fv[i], sp->s_fv[i]->f_r.r_from, sp->s_fv[i]->f_r.r_to, BGChar);
}

/* reverse search */
static int
revsearch(ssam_t *sp, ure_t *up, context_t *dot, int mc, urematch_t *mv)
{
	Rune	prior;
	Rune	r;
	int	rlen;
	char	*cp;
	char	*s;
	int	matched;
	int	eflag;
	int	m;

	(void) f_seek(dot->c_fp, 0, BGFromBOF, BGChar);
	s = f_getstr(dot->c_fp);
	cp = &s[utfbytes(s) - 1];
	matched = 0;
	for (;;) {
		if (cp == s) {
			return matched;
		}
		(void) priorrune(&prior, cp);
		eflag = (cp == s || prior == '\n') ? 0 : URE_NOTBOL;
		m = ureexec(up, cp, mc, mv, eflag, sp->s_collseq);
		if (matched && (m == URE_NOMATCH || mv[0].rm_so > 0)) {
			mv[0].rm_so += (cp - s);
			mv[0].rm_eo += (cp - s);
			return 1;
		}
		if (!matched && m == URE_SUCCESS) {
			matched = 1;
		}
		rlen = priorrune(&r, cp);
		cp -= rlen;
	}
}

/* find a pattern */
static void
findpat(ssam_t *sp, context_t *ndot, context_t *dot, cmd_t *cmdp, int dir)
{
	context_t	tmp;
	long		boff;
	long		off;
	int		base;

	base = pushmatch(sp, &cmdp->c_u);
	setcontext(&tmp, dot->c_fp, dot->c_r.r_from, dot->c_r.r_to, BGChar);
	if (!f_seek(tmp.c_fp, off = tmp.c_r.r_from, BGFromBOF, BGChar)) {
		RunError(sp, ErrInvalidAddr, cmdp, "(%ld)", off);
	}
	if (dir == 1) {
		boff = f_tell(tmp.c_fp, BGByte);
		if (ureexec(&cmdp->c_u, f_getstr(tmp.c_fp), cmdp->c_u.u_subc,
			    &sp->s_matchv[base], 0, sp->s_collseq) == URE_NOMATCH) {
			RunError(sp, ErrBadURE, cmdp, "Not found", 0);
		}
		setcontext(ndot, tmp.c_fp, boff + sp->s_matchv[base].rm_so, boff + sp->s_matchv[base].rm_eo, BGByte);
	} else {
		if (!revsearch(sp, &cmdp->c_u, &tmp, cmdp->c_u.u_subc, &sp->s_matchv[base])) {
			RunError(sp, ErrBadURE, cmdp, "Not found", 0);
		}
		setcontext(ndot, tmp.c_fp, sp->s_matchv[base].rm_so, sp->s_matchv[base].rm_eo, BGByte);
	}
	popmatch(sp, &cmdp->c_u);
}

/* set the address in ndot */
static void
setaddress(ssam_t *sp, context_t *ndot, context_t *dot, int cmd)
{
	context_t	lhs;
	long		n;
	int		sign;
	int		rhs;

	sign = 0;
	switch(sp->s_progv[cmd].c_gcp->gc_ch) {
	case '#':
		setcontext(ndot, dot->c_fp, sp->s_progv[cmd].c_iargv[0], sp->s_progv[cmd].c_iargv[0], BGChar);
		return;
	case '$':
		n = f_size(dot->c_fp, BGChar);
		setcontext(ndot, dot->c_fp, n, n, BGChar);
		return;
	case '.':
		setcontext(ndot, dot->c_fp, dot->c_r.r_from, dot->c_r.r_to, BGChar);
		return;
	case '\'':
		setcontext(ndot, sp->s_mark.c_fp, sp->s_mark.c_r.r_from, sp->s_mark.c_r.r_to, BGChar);
		return;
	case '"':
		findfile(sp, ndot, cmd);
		return;
	case '1':
		if (!f_seek(dot->c_fp, sp->s_progv[cmd].c_iargv[0], BGFromBOF, BGLine)) {
			RunError(sp, ErrBadLineNumber, &sp->s_progv[cmd], "Bad line number", 0);
		}
		n = f_tell(dot->c_fp, BGChar);
		setcontext(ndot, dot->c_fp, n, (f_seek(dot->c_fp, 1, BGFromHere, BGLine)) ?
						f_tell(dot->c_fp, BGChar) :
						f_size(dot->c_fp, BGChar), BGChar);
		return;
	case '/':
		/* if we get here, then it's a forwards search */
		findpat(sp, ndot, dot, &sp->s_progv[cmd], 1);
		return;
	case '+':
		setaddress(sp, &lhs, dot, sp->s_progv[cmd].c_lhs);
		sign = 1;
		break;
	case '-':
		setaddress(sp, &lhs, dot, sp->s_progv[cmd].c_lhs);
		sign = -1;
		break;
	}
	setcontext(ndot, lhs.c_fp, lhs.c_r.r_from, lhs.c_r.r_to, BGChar);
	rhs = sp->s_progv[cmd].c_rhs;
	switch(sp->s_progv[rhs].c_gcp->gc_ch) {
	case '/':
		findpat(sp, ndot, dot, &sp->s_progv[rhs], sign);
		break;
	case '#':
		n = ((sign == 1) ? ndot->c_r.r_to : ndot->c_r.r_from) + (sign * sp->s_progv[rhs].c_iargv[0]);
		if (!f_seek(ndot->c_fp, n, BGFromBOF, BGChar)) {
			RunError(sp, ErrInvalidAddr, &sp->s_progv[rhs], "(%ld)", n);
		}
		setcontext(ndot, ndot->c_fp, n, n, BGChar);
		break;
	case '1':
		n = (sign == 1) ? ndot->c_r.r_to : ndot->c_r.r_from;
		if (!f_seek(ndot->c_fp, n, BGFromBOF, BGChar)) {
			RunError(sp, ErrInvalidAddr, &sp->s_progv[rhs], "(%ld)", n);
		}
		n = sign * sp->s_progv[rhs].c_iargv[0];
		if (!f_seek(ndot->c_fp, n, BGFromHere, BGLine)) {
			setcontext(ndot, ndot->c_fp, 0, 0, BGChar);
		} else {
			n = f_tell(ndot->c_fp, BGChar);
			setcontext(ndot, ndot->c_fp, n, (f_seek(ndot->c_fp, 1, BGFromHere, BGLine)) ?
						f_tell(ndot->c_fp, BGChar) :
						f_size(ndot->c_fp, BGChar), BGChar);
		}
	}
}

/* do a semicolon address command */
static int
do_semicolon(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	context_t	lhs;

	setaddress(sp, &lhs, dot, sp->s_progv[*cmdp].c_lhs);
	setaddress(sp, &ndot, &lhs, sp->s_progv[*cmdp].c_rhs);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, &ndot, cmdp);
}

/* do a comma address command */
static int
do_comma(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	context_t	lhs;
	context_t	rhs;

	setaddress(sp, &lhs, dot, sp->s_progv[*cmdp].c_lhs);
	setaddress(sp, &rhs, dot, sp->s_progv[*cmdp].c_rhs);
	setcontext(&ndot, lhs.c_fp, lhs.c_r.r_from, rhs.c_r.r_to, BGChar);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, &ndot, cmdp);
}

/* do an address command */
static int
do_addr(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;

	setaddress(sp, &ndot, dot, *cmdp);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, &ndot, cmdp);
}

/* do an equals command */
static int
do_eq(ssam_t *sp, context_t *dot, int *cmdp)
{
	long	toline;
	long	tobytes;

	if (!f_seek(dot->c_fp, dot->c_r.r_to, BGFromBOF, BGChar)) {
		RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", dot->c_r.r_to);
	}
	toline = f_tell(dot->c_fp, BGLine);
	tobytes = f_tell(dot->c_fp, BGByte);
	if (!f_seek(dot->c_fp, dot->c_r.r_from, BGFromBOF, BGChar)) {
		RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", dot->c_r.r_from);
	}
	printf("%ld,%ld #%ld,#%ld\n", f_tell(dot->c_fp, BGLine), toline,
		(sp->s_outbytes) ? f_tell(dot->c_fp, BGByte) : dot->c_r.r_from,
		(sp->s_outbytes) ? tobytes : dot->c_r.r_to);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do an X command */
static int
do_X(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	ure_t		*up;
	char		buf[BUFSIZ];
	int		base;
	int		i;
	int		j;

	base = pushmatch(sp, up = &sp->s_progv[*cmdp].c_u);
	for (i = 0 ; i < sp->s_fsize ; i++) {
		if (sp->s_fv[i] != (f_t *) NULL) {
			maketag(buf, sizeof(buf), sp->s_fv[i], sp->s_fcurr);
			if (ureexec(up, buf, up->u_subc, &sp->s_matchv[base], 0, sp->s_collseq) == URE_SUCCESS) {
				setcontext(&ndot, sp->s_fv[i], sp->s_fv[i]->f_r.r_from,
							sp->s_fv[i]->f_r.r_to, BGChar);
				j = sp->s_progv[*cmdp].c_sub;
				if (!samcmd(sp, &ndot, &j)) {
					popmatch(sp, up);
					return 0;
				}
			}
		}
	}
	popmatch(sp, up);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do a Y command */
static int
do_Y(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	ure_t		*up;
	char		buf[BUFSIZ];
	int		base;
	int		i;
	int		j;

	base = pushmatch(sp, up = &sp->s_progv[*cmdp].c_u);
	for (i = 0 ; i < sp->s_fsize ; i++) {
		if (sp->s_fv[i] != (f_t *) NULL) {
			maketag(buf, sizeof(buf), sp->s_fv[i], sp->s_fcurr);
			if (ureexec(up, buf, up->u_subc, &sp->s_matchv[base], 0, sp->s_collseq) == URE_NOMATCH) {
				setcontext(&ndot, sp->s_fv[i], sp->s_fv[i]->f_r.r_from,
							sp->s_fv[i]->f_r.r_to, BGChar);
				j = sp->s_progv[*cmdp].c_sub;
				if (!samcmd(sp, &ndot, &j)) {
					popmatch(sp, up);
					return 0;
				}
			}
		}
	}
	popmatch(sp, up);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do an a command */
static int
do_a(ssam_t *sp, context_t *dot, int *cmdp)
{
	pushchange(sp, dot->c_fp, dot->c_r.r_to, dot->c_r.r_to,
					'i', sp->s_progv[*cmdp].c_iargv[0], sp->s_progv[*cmdp].c_argv[0]);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do a c command */
static int
do_c(ssam_t *sp, context_t *dot, int *cmdp)
{
	pushchange(sp, dot->c_fp, dot->c_r.r_from, dot->c_r.r_to,
					'i', sp->s_progv[*cmdp].c_iargv[0], sp->s_progv[*cmdp].c_argv[0]);
	pushchange(sp, dot->c_fp, dot->c_r.r_from, dot->c_r.r_to, 'd', 0, NULL);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do a d command */
static int
do_d(ssam_t *sp, context_t *dot, int *cmdp)
{
	pushchange(sp, dot->c_fp, dot->c_r.r_from, dot->c_r.r_to, 'd', 0, NULL);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do an f command */
static int
do_f(ssam_t *sp, context_t *dot, int *cmdp)
{
	char	buf[BUFSIZ];

	maketag(buf, sizeof(buf), sp->s_fcurr, sp->s_fcurr);
	printf("%s\n", buf);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do a g command */
static int
do_g(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	ure_t		*up;
	int		base;
	int		j;

	base = pushmatch(sp, up = &sp->s_progv[*cmdp].c_u);
	if (!f_seek(dot->c_fp, dot->c_r.r_from, BGFromBOF, BGChar)) {
		RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", dot->c_r.r_from);
	}
	if (ureexec(up, f_getstr(dot->c_fp), up->u_subc, &sp->s_matchv[base], 0, sp->s_collseq) == URE_NOMATCH ||
	    sp->s_matchv[base].rm_so > dot->c_r.r_to) {
		return 1;
	}
	popmatch(sp, up);
	j = sp->s_progv[*cmdp].c_sub;
	if (!samcmd(sp, &ndot, &j)) {
		return 0;
	}
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do an i command */
static int
do_i(ssam_t *sp, context_t *dot, int *cmdp)
{
	pushchange(sp, dot->c_fp, dot->c_r.r_from, dot->c_r.r_to,
					'i', sp->s_progv[*cmdp].c_iargv[0], sp->s_progv[*cmdp].c_argv[0]);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do a k command */
static int
do_k(ssam_t *sp, context_t *dot, int *cmdp)
{
	sp->s_mark.c_fp = dot->c_fp;
	sp->s_mark.c_r.r_from = dot->c_r.r_from;
	sp->s_mark.c_r.r_to = dot->c_r.r_to;
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do an m command */
static int
do_m(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	char		*text;

	setaddress(sp, &ndot, dot, sp->s_progv[*cmdp].c_tgt);
	text = f_gettext(dot->c_fp, dot->c_r.r_from, dot->c_r.r_to);
	pushchange(sp, dot->c_fp, ndot.c_r.r_to, ndot.c_r.r_to, 'i',
				dot->c_r.r_to - dot->c_r.r_from, text);
	FREE(text);
	pushchange(sp, dot->c_fp, dot->c_r.r_from, dot->c_r.r_to, 'd', 0, NULL);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do an n command */
static int
do_n(ssam_t *sp, context_t *dot, int *cmdp)
{
	char	buf[BUFSIZ];
	int	i;

	for (i = 0 ; i < sp->s_fsize ; i++) {
		if (sp->s_fv[i] != (f_t *) NULL) {
			maketag(buf, sizeof(buf), sp->s_fv[i], sp->s_fcurr);
			printf("%s\n", buf);
		}
	}
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do a p command */
static int
do_p(ssam_t *sp, context_t *dot, int *cmdp)
{
	long	n;

	if (!f_seek(dot->c_fp, dot->c_r.r_to, BGFromBOF, BGChar)) {
		RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", dot->c_r.r_to);
	}
	n = f_tell(dot->c_fp, BGByte);
	if (!f_seek(dot->c_fp, dot->c_r.r_from, BGFromBOF, BGChar)) {
		RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", dot->c_r.r_from);
	}
	n -= f_tell(dot->c_fp, BGByte);
	if (fwrite(f_getstr(dot->c_fp), sizeof(char), n, stdout) != n) {
		RunError(sp, ErrCantWrite, &sp->s_progv[*cmdp], "(%ld)", n);
	}
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do an s command */
static int
do_s(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	ure_t		*up;
	long		off;
	int		base;

	base = pushmatch(sp, up = &sp->s_progv[*cmdp].c_u);
	if (!f_seek(dot->c_fp, off = dot->c_r.r_from, BGFromBOF, BGChar)) {
		RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", dot->c_r.r_from);
	}
	if (ureexec(up, f_getstr(dot->c_fp), up->u_subc, &sp->s_matchv[base], 0, sp->s_collseq) == URE_NOMATCH ||
	    sp->s_matchv[base].rm_so + off > dot->c_r.r_to) {
		return 1;
	}
	sp->s_matchv[base].rm_so += off;
	sp->s_matchv[base].rm_eo += off;
	subst(sp, dot, &sp->s_progv[*cmdp], &sp->s_matchv[base]);
	pushchange(sp, dot->c_fp, sp->s_matchv[base].rm_so, sp->s_matchv[base].rm_eo, 'd', 0, NULL);
	popmatch(sp, up);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, &ndot, cmdp);
}

/* do a t command */
static int
do_t(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	char		*text;

	setaddress(sp, &ndot, dot, sp->s_progv[*cmdp].c_tgt);
	text = f_gettext(dot->c_fp, dot->c_r.r_from, dot->c_r.r_to);
	pushchange(sp, dot->c_fp, ndot.c_r.r_to, ndot.c_r.r_to, 'i',
				dot->c_r.r_to - dot->c_r.r_from, text);
	FREE(text);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do a v command */
static int
do_v(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	ure_t		*up;
	int		base;
	int		j;

	base = pushmatch(sp, up = &sp->s_progv[*cmdp].c_u);
	if (!f_seek(dot->c_fp, dot->c_r.r_from, BGFromBOF, BGChar)) {
		RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", dot->c_r.r_from);
	}
	if (ureexec(up, f_getstr(dot->c_fp), up->u_subc, &sp->s_matchv[base], 0, sp->s_collseq) == URE_NOMATCH ||
	    sp->s_matchv[base].rm_so > dot->c_r.r_to) {
		j = sp->s_progv[*cmdp].c_sub;
		if (!samcmd(sp, &ndot, &j)) {
			popmatch(sp, up);
			return 0;
		}
	}
	popmatch(sp, up);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do a w command */
static int
do_w(ssam_t *sp, context_t *dot, int *cmdp)
{
	int	i;

	for (i = 0 ; i < sp->s_fc ; i++) {
		sp->s_fv[i]->f_writeme = 1;
	}
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do an x command */
static int
do_x(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	ure_t		*up;
	long		boff;
	long		off;
	int		eflag;
	int		base;
	int		j;

	base = pushmatch(sp, up = &sp->s_progv[*cmdp].c_u);
	if (!f_seek(dot->c_fp, off = dot->c_r.r_from, BGFromBOF, BGChar)) {
		RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", off);
	}
	while (off < dot->c_r.r_to) {
		boff = f_tell(dot->c_fp, BGByte);
		eflag = (off == 0 || f_peek(dot->c_fp, -1) == '\n') ? 0 : URE_NOTBOL;
		if (ureexec(up, f_getstr(dot->c_fp),
			    up->u_subc, &sp->s_matchv[base], eflag, sp->s_collseq) == URE_NOMATCH) {
			break;
		}
		setcontext(&ndot, dot->c_fp, boff + sp->s_matchv[base].rm_so, boff + sp->s_matchv[base].rm_eo, BGByte);
		if (ndot.c_r.r_to > dot->c_r.r_to) {
			break;
		}
		j = sp->s_progv[*cmdp].c_sub;
		if (!samcmd(sp, &ndot, &j)) {
			popmatch(sp, up);
			return 0;
		}
		if (!f_seek(dot->c_fp, sp->s_matchv[base].rm_eo + boff, BGFromBOF, BGByte)) {
			RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", boff + sp->s_matchv[base].rm_eo);
		}
		if (sp->s_matchv[base].rm_eo == sp->s_matchv[base].rm_so) {
			if (!f_seek(dot->c_fp, 1, BGFromHere, BGChar)) {
				RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", sp->s_matchv[base].rm_eo);
			}
		}
		off = f_tell(dot->c_fp, BGChar);
	}
	popmatch(sp, up);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do a y command */
static int
do_y(ssam_t *sp, context_t *dot, int *cmdp)
{
	context_t	ndot;
	ure_t		*up;
	long		from;
	long		off;
	int		eflag;
	int		base;
	int		j;

	base = pushmatch(sp, up = &sp->s_progv[*cmdp].c_u);
	if (!f_seek(dot->c_fp, off = dot->c_r.r_from, BGFromBOF, BGChar)) {
		RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", off);
	}
	while (off < dot->c_r.r_to) {
		from = f_tell(dot->c_fp, BGByte);
		eflag = (off == 0 || f_peek(dot->c_fp, -1) == '\n') ? 0 : URE_NOTBOL;
		if (ureexec(up, f_getstr(dot->c_fp),
			    up->u_subc, &sp->s_matchv[base], eflag, sp->s_collseq) == URE_NOMATCH) {
			break;
		}
		/* got a match - now do cmd from `from' to here */
		setcontext(&ndot, dot->c_fp, from, from + sp->s_matchv[base].rm_so, BGByte);
		if (ndot.c_r.r_to > dot->c_r.r_to) {
			break;
		}
		j = sp->s_progv[*cmdp].c_sub;
		if (!samcmd(sp, &ndot, &j)) {
			popmatch(sp, up);
			return 0;
		}
		(void) f_seek(dot->c_fp, from + sp->s_matchv[base].rm_eo, BGFromBOF, BGByte);
		if (sp->s_matchv[base].rm_eo == sp->s_matchv[base].rm_so) {
			if (!f_seek(dot->c_fp, 1, BGFromHere, BGChar)) {
				RunError(sp, ErrInvalidAddr, &sp->s_progv[*cmdp], "(%ld)", sp->s_matchv[base].rm_eo);
			}
		}
		off = f_tell(dot->c_fp, BGChar);
	}
	if (from < dot->c_r.r_to) {
		(void) f_seek(dot->c_fp, dot->c_r.r_to, BGFromBOF, BGChar);
		setcontext(&ndot, dot->c_fp, from, f_tell(dot->c_fp, BGByte), BGByte);
		j = sp->s_progv[*cmdp].c_sub;
		if (!samcmd(sp, &ndot, &j)) {
			popmatch(sp, up);
			return 0;
		}
	}
	popmatch(sp, up);
	*cmdp = sp->s_progv[*cmdp].c_next;
	return samcmd(sp, dot, cmdp);
}

/* do a { command */
static int
do_lb(ssam_t *sp, context_t *dot, int *cmdp)
{
	int	cmd;

	for (cmd = sp->s_progv[*cmdp].c_sub ; cmd >= 0 ; ) {
		if (!samcmd(sp, dot, &cmd)) {
			return 0;
		}
		if (cmd >= 0) {
			cmd = sp->s_progv[cmd].c_next;
		}
	}
	return 1;
}

/* do a } command */
static int
do_rb(ssam_t *sp, context_t *dot, int *cmdp)
{
	return 1;
}

/* do a sam command */
static int
samcmd(ssam_t *sp, context_t *dot, int *cmdp)
{
	return (*cmdp == -1) ? 1 : (*sp->s_progv[*cmdp].c_gcp->gc_func)(sp, dot, cmdp);
}

/* transform a Rune escape sequence */
static int
transformesc(Rune r, Rune *rp)
{
	static Rune	from[] = { 'n', 'r', 't', 0 };
	static Rune	to[] = { '\n', '\r', '\t', 0 };
	Rune		*runep;

	for (runep = from ; *runep && *runep != r ; runep++) {
	}
	if (*runep == 0) {
		return 0;
	}
	*rp = to[runep - from];
	return 1;
}

/* search for `ch', ignoring any occurrences where it's escaped */
static char *
utfescrune(char *s, int *pos, Rune ch, int intesc)
{
	char	*out;
	char	*cp;
	Rune	outr;
	Rune	r;
	int	rlen;

	rlen = utfbytes(&s[*pos]);
	NEWARRAY(char, cp, rlen + 1, exit(1));
	out = cp;
	for (;;) {
		rlen = chartorune(&r, &s[*pos]);
		if (r == '\\') {
			*pos += rlen;
			rlen = chartorune(&r, &s[*pos]);
			if (intesc && transformesc(r, &outr)) {
				*pos += rlen;
				out += runetochar(out, &outr);
				continue;
			}
			if (r != ch) {
				outr = '\\';
				out += runetochar(out, &outr);
			}
		} else {
			if (r == ch) {
				*pos += rlen;
				*out = 0;
				return cp;
			}
			if (r == 0) {
				*out = 0;
				return cp;
			}
		}
		out += runetochar(out, &r);
		*pos += rlen;
	}
}

/* skip whitespace */
static void
skipspace(char *s, int *pos)
{
	Rune	r;
	int	rlen;

	for (;;) {
		rlen = chartorune(&r, &s[*pos]);
		if (r == 0 || !UNICODE_isspace(r)) {
			return;
		}
		*pos += rlen;
	}
}

/* get `argc' arguments, placing them in `argv', and their lengths in `iargv' */
static void
getarg(ssam_t *sp, char *s, int *pos, int argc, char **argv, int *iargv, int intesc)
{
	Rune	sep;
	char	*cp;
	int	rlen;
	int	i;

	skipspace(s, pos);
	rlen = chartorune(&sep, &s[*pos]);
	*pos += rlen;
	for (i = 0 ; i < argc ; i++) {
		rlen = *pos;
		cp = utfescrune(s, pos, sep, intesc);
		iargv[i] = utfbytes(argv[i] = cp);
	}
}

/* get an integer */
static int
getinteger(char *s, int *pos)
{
	Rune	r;
	int	rlen;
	int	ret;

	rlen = chartorune(&r, s + *pos);
	for (ret = 0 ; UNICODE_isdigit(r) ; ) {
		ret = (ret * 10) + (r - '0');
		*pos += rlen;
		rlen = chartorune(&r, s + *pos);
	}
	return ret;
}

/* make a new command, contents depend on the generic command */
static int
newcmd(ssam_t *sp, char *s, int *pos, gcmd_t *gcp)
{
	cmd_t	*cmdp;
	Rune	r;
	int	rlen;
	int	j;

	if (sp->s_progsize == 0) {
		sp->s_progsize = CHUNKSIZE;
		NEWARRAY(cmd_t, sp->s_progv, sp->s_progsize, exit(1));
	} else if (sp->s_progc == sp->s_progsize) {
		sp->s_progsize *= 2;
		RENEW(cmd_t, sp->s_progv, sp->s_progsize, exit(1));
	}
	j = sp->s_progc;
	cmdp = &sp->s_progv[sp->s_progc++];
	cmdp->c_gcp = gcp;
	cmdp->c_pos = *pos;
	cmdp->c_line = s;
	cmdp->c_tgt = cmdp->c_next = cmdp->c_sub = cmdp->c_lhs = cmdp->c_rhs = -1;
	if (gcp->gc_advance) {
		rlen = chartorune(&r, s + *pos);
		*pos += rlen;
	}
	if (gcp->gc_argc > 0) {
		getarg(sp, s, pos, gcp->gc_argc, cmdp->c_argv, cmdp->c_iargv, gcp->gc_intesc);
	}
	if (gcp->gc_tgt) {
		if ((cmdp->c_tgt = rec_address(sp, s, pos)) < 0) {
			Error(sp, ErrNoTarget, s, *pos);
		}
	}
	if (gcp->gc_subcmd) {
		if ((cmdp->c_sub = rec_cmd_or_addr(sp, s, pos)) < 0) {
			Error(sp, ErrNoSubcommand, s, *pos);
		}
	}
	if (gcp->gc_compile) {
		if (urecomp(&cmdp->c_u, cmdp->c_argv[0], 0) != URE_SUCCESS) {
			Error(sp, ErrBadURE, s, *pos);
		}
	}
	if (gcp->gc_getint) {
		cmdp->c_iargv[0] = getinteger(s, pos);
	}
	if (gcp->gc_recblock) {
		cmdp->c_sub = rec_block(sp, s, pos);
	}
	return j;
}

/* some constants to show what's happening in parse tables */
enum {
	HasTarget = 1,
	HasSubCmd,
	UreArg,
	Advance,
	IntArg,
	RecBlock,
	InterpEscs
};

/* parse table for simple addresses */
static gcmd_t	simpaddrv[] = {
	{ '#', do_addr, 0, 0, 0, 0, Advance, IntArg, 0, SimpleAddr, NULL, NULL, 0, 0 },
	{ '.', do_addr, 0, 0, 0, 0, Advance, 0, 0, SimpleAddr, NULL, NULL, 0, 0 },
	{ '$', do_addr, 0, 0, 0, 0, Advance, 0, 0, SimpleAddr, NULL, NULL, 0, 0 },
	{ '\'', do_addr, 0, 0, 0, 0, Advance, 0, 0, SimpleAddr, NULL, NULL, 0, 0 },
	{ '/', do_addr, 1, 0, 0, UreArg, 0, 0, 0, SimpleAddr, NULL, NULL, 0, 0 },
	{ '"', do_addr, 1, 0, 0, UreArg, 0, 0, 0, SimpleAddr, NULL, NULL, 0, 0 },
	{ 0 }
};

/* special case of line number */
static gcmd_t	gc_line = { '1', do_addr, 0, 0, 0, 0, 0, IntArg, 0, SimpleAddr, NULL, NULL, 0, 0 };

/* parse table for compound addresses */
static gcmd_t	compaddrv[] = {
	{ '+', do_addr, 0, 0, 0, 0, Advance, 0, 0, CompoundAddr, ".", "1", 0, 0 },
	{ '-', do_addr, 0, 0, 0, 0, Advance, 0, 0, CompoundAddr, ".", "1", 0, 0 },
	{ ',', do_comma, 0, 0, 0, 0, Advance, 0, 0, CompoundAddr, "0", "$", 0, 0 },
	{ ';', do_semicolon, 0, 0, 0, 0, Advance, 0, 0, CompoundAddr, "0", "$", 0, 0 },
	{ 0 }
};

/* parse table for commands */
static gcmd_t	cmdv[] = {
	{ '=', do_eq, 0, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'X', do_X, 1, 0, HasSubCmd, UreArg, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'Y', do_Y, 1, 0, HasSubCmd, UreArg, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'a', do_a, 1, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, InterpEscs },
	{ 'c', do_c, 1, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, InterpEscs },
	{ 'd', do_d, 0, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'f', do_f, 0, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'g', do_g, 1, 0, HasSubCmd, UreArg, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'i', do_i, 1, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, InterpEscs },
	{ 'k', do_k, 0, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'm', do_m, 0, HasTarget, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'n', do_n, 0, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'p', do_p, 0, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 's', do_s, 2, 0, 0, UreArg, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 't', do_t, 0, HasTarget, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'v', do_v, 1, 0, HasSubCmd, UreArg, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'w', do_w, 0, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'x', do_x, 1, 0, HasSubCmd, UreArg, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ 'y', do_y, 1, 0, HasSubCmd, UreArg, Advance, 0, 0, Cmd, NULL, NULL, 0, 0 },
	{ '{', do_lb, 0, 0, 0, 0, Advance, 0, RecBlock, Cmd, NULL, NULL, 1, 0 },
	{ '}', do_rb, 0, 0, 0, 0, Advance, 0, 0, Cmd, NULL, NULL, -1, 0 },
	{ 0 }
};

/* find a generic command in a command table */
static gcmd_t *
findcmd(Rune r, gcmd_t *tab)
{
	gcmd_t	*gp;

	for (gp = tab ; gp->gc_ch != 0 && gp->gc_ch != r ; gp++) {
	}
	return (gp->gc_ch == 0) ? (gcmd_t *) NULL : gp;
}

/* recognise a simple address */
static int
rec_simple(ssam_t *sp, char *s, int *pos)
{
	gcmd_t	*gp;
	Rune	r;

	skipspace(s, pos);
	(void) chartorune(&r, &s[*pos]);
	if ((gp = findcmd(r, simpaddrv)) == (gcmd_t *) NULL && UNICODE_isdigit(r)) {
		gp = &gc_line;
	}
	return (gp) ? newcmd(sp, s, pos, gp) : -1;
}

/* recognise a compound address */
static int
rec_address(ssam_t *sp, char *s, int *pos)
{
	gcmd_t	*gp;
	Rune	r;
	int	cmd;
	int	lhs;
	int	j;

	lhs = rec_simple(sp, s, pos);
	(void) chartorune(&r, &s[*pos]);
	while ((gp = findcmd(r, compaddrv)) != (gcmd_t *) NULL) {
		if (lhs == -1) {
			j = 0;
			lhs = rec_simple(sp, gp->gc_lhs, &j);
		}
		cmd = newcmd(sp, s, pos, gp);
		sp->s_progv[cmd].c_lhs = lhs;
		if ((sp->s_progv[cmd].c_rhs = rec_simple(sp, s, pos)) == -1) {
			j = 0;
			sp->s_progv[cmd].c_rhs = rec_simple(sp, gp->gc_rhs, &j);
		}
		lhs = cmd;
		(void) chartorune(&r, &s[*pos]);
	}
	return lhs;
}

/* recognise a command or address */
static int
rec_cmd_or_addr(ssam_t *sp, char *s, int *pos)
{
	gcmd_t	*gp;
	Rune	r;
	int	ret;

	skipspace(s, pos);
	(void) chartorune(&r, &s[*pos]);
	if ((gp = findcmd(r, cmdv)) == (gcmd_t *) NULL) {
		if (r == 0) {
			return -1;
		}
		if ((ret = rec_address(sp, s, pos)) == -1) {
			Error(sp, ErrNoCmd, s, *pos);
		}
		return ret;
	}
	if ((sp->s_blockc += gp->gc_blockc) < 0) {
		Error(sp, ErrBlockUnderflow, s, *pos);
	}
	return newcmd(sp, s, pos, gp);
}

/* add a default `p' command if the last thing is an address */
static void
defaultp(ssam_t *sp, int cmd)
{
	int	next;
	int	tail;
	int	j;

	if (cmd >= 0) {
		for (tail = cmd ; (next = sp->s_progv[tail].c_next) != -1 ; tail = next) {
			if (sp->s_progv[next].c_gcp->gc_ch == '}') {
				break;
			}
		}
		if (sp->s_progv[tail].c_sub != -1) {
			tail = sp->s_progv[tail].c_sub;
		}
		if (ISADDRESS(sp->s_progv[tail].c_gcp)) {
/* (void) fprintf(stderr, "1. Got a default `p' here\n"); */
			j = 0;
			sp->s_progv[tail].c_next = rec_cmd_or_addr(sp, "p", &j);
		}
	}
}

/* recognise a command - keep going until we get one */
static int
rec_cmd(ssam_t *sp, char *s, int *pos)
{
	gcmd_t	*gp;
	Rune	r;
	int	head;
	int	tail;
	int	cmd;

	head = tail = -1;
	do {
		skipspace(s, pos);
		(void) chartorune(&r, &s[*pos]);
		if ((gp = findcmd(r, cmdv)) == (gcmd_t *) NULL) {
			if (r == 0 || (cmd = rec_address(sp, s, pos)) == -1) {
				break;
			}
		} else {
			if ((sp->s_blockc += gp->gc_blockc) < 0) {
				Error(sp, ErrBlockUnderflow, s, *pos);
			}
			cmd = newcmd(sp, s, pos, gp);
		}
		if (head < 0) {
			head = cmd;
		} else {
			sp->s_progv[tail].c_next = cmd;
		}
		if (sp->s_progv[cmd].c_gcp->gc_ch == '}') {
			break;
		}
		tail = cmd;
	} while (gp == (gcmd_t *) NULL);
	defaultp(sp, tail);
	return head;
}

/* parse a block of commands */
static int
rec_block(ssam_t *sp, char *s, int *pos)
{
	int	head;
	int	tail;
	int	cmd;

	head = tail = -1;
	for (;;) {
		if ((cmd = rec_cmd_or_addr(sp, s, pos)) < 0) {
			break;
		}
		if (head < 0) {
			head = cmd;
		} else {
			sp->s_progv[tail].c_next = cmd;
		}
		if (sp->s_progv[cmd].c_gcp->gc_ch == '}') {
			break;
		}
		tail = cmd;
	}
	defaultp(sp, tail);
	return head;
}

/* print the command, and its descendants */
static void
print(ssam_t *sp, int node, int level)
{
	cmd_t	*cmdp;
	int	i;

	if (node >= 0) {
		cmdp = &sp->s_progv[node];
		print(sp, cmdp->c_lhs, level);
		if (cmdp->c_gcp->gc_ch == '}') {
			level--;
		}
		for (i = 0 ; i < level - 1 ; i++) {
			printf("   ");
		}
		switch(cmdp->c_gcp->gc_ch) {
		case '1':
			printf("[Line %d]", cmdp->c_iargv[0]);
			break;
		case '#':
			printf("[UTF Offset %d]", cmdp->c_iargv[0]);
			break;
		default:
			printf("%c ", cmdp->c_gcp->gc_ch);
		}
		for (i = 0 ; i < cmdp->c_gcp->gc_argc ; i++) {
			printf("`%.*s' ", cmdp->c_iargv[i], cmdp->c_argv[i]);
		}
		printf("\n");
		print(sp, cmdp->c_rhs, level);
		print(sp, cmdp->c_sub, level + 1);
		print(sp, cmdp->c_next, level);
	}
}

/* read stdin into a buffer gap */
static void
readinput(ssam_t *sp)
{
	char	buf[BUFSIZ];
	f_t	*fp;
	int	cc;

	fp = f_open(sp, (char *) NULL);
	while ((cc = fread(buf, sizeof(char), sizeof(buf), stdin)) > 0) {
		f_insert(fp, buf, cc);
	}
	fp->f_modified = 0;
}

/* read files into buffer gaps */
static void
readfiles(ssam_t *sp, int argc, char **argv)
{
	int	i;

	for (i = 0 ; i < argc ; i++) {
		if (f_open(sp, argv[i]) == (f_t *) NULL) {
			(void) fprintf(stderr, "can't open `%s'\n", argv[i]);
		}
	}
}

/* write any files with the write bit set */
static int
writefiles(ssam_t *sp)
{
	FILE	*filep;
	int	alldone;
	int	i;

	for (i = 0, alldone = 1 ; i < sp->s_fc ; i++) {
		if (!sp->s_fv[i]->f_writeme || !sp->s_fv[i]->f_modified) {
			continue;
		}
		if ((filep = fopen(sp->s_fv[i]->f_name, "w")) == (FILE *) NULL) {
			alldone = 0;
		}
		if (!f_write(sp->s_fv[i], filep)) {
			(void) fprintf(stderr, "Error writing to %s\n",
				sp->s_fv[i]->f_name);
			alldone = 0;
		}
		(void) fclose(filep);
	}
	return alldone;
}

/* this routine sets up the files in buffer gap structures */
int
ssamfiles(ssam_t *sp, int argc, char **argv)
{
	if (argc > 0) {
		readfiles(sp, argc, argv);
	} else {
		readinput(sp);
	}
	if (sp->s_fv == (f_t **) NULL || (sp->s_fcurr = sp->s_fv[0]) == (f_t *) NULL) {
		(void) fprintf(stderr, "No input\n");
		return 0;
	}
	return 1;
}

/* this routine frees memory if necessary. If it is, you need a new OS */
void
ssamfree(ssam_t *sp, int flags)
{
	int	i;
	int	j;

	for (i = 0 ; (flags & FreeCommands) && i < sp->s_progc ; i++) {
		if (sp->s_progv[i].c_gcp->gc_compile) {
			urefree(&sp->s_progv[i].c_u);
		}
		for (j = 0 ; j < sp->s_progv[i].c_gcp->gc_argc ; j++) {
			FREE(sp->s_progv[i].c_argv[j]);
		}
	}
	if ((flags & FreeCommands) && sp->s_progsize > 0) {
		FREE(sp->s_progv);
	}
	if ((flags & FreeChanges) && sp->s_chgsize > 0) {
		FREE(sp->s_chgv);
	}
	if ((flags & FreeMatches) && sp->s_chgsize > 0) {
		FREE(sp->s_matchv);
	}
	for (i = 0 ; (flags & CloseFiles) && i < sp->s_fc ; i++) {
		f_close(sp, sp->s_fv[i]);
	}
	if ((flags & FreeFiles) && sp->s_fv != (f_t **) NULL) {
		FREE(sp->s_fv);
	}
}

/* this routine does most of the work */
int
ssam(ssam_t *sp, char *command, int argc, int flags, char *collseq)
{
	int	pos;
	int	cmd;

	pos = sp->s_blockc = 0;
	sp->s_collseq = collseq;
	sp->s_outbytes = (flags & ByteOffsets);
	if (setjmp(sp->s_escape) != 0) {
		return 0;
	}
	if ((cmd = rec_block(sp, command, &pos)) < 0) {
		Error(sp, ErrNothingToDo, command, pos);
	}
	if (sp->s_blockc > 0) {
		Error(sp, ErrBlockOverflow, command, pos);
	}
	if (flags & Explain) {
		print(sp, cmd, 0);
	} else {
		(void) f_seek(sp->s_fcurr, 0, BGFromBOF, BGChar);
		setcontext(&sp->s_dot, sp->s_fcurr, sp->s_fcurr->f_r.r_from, sp->s_fcurr->f_r.r_to, BGChar);
		(void) samcmd(sp, &sp->s_dot, &cmd);
		if (!popchanges(sp)) {
			RunError(sp, ErrChangeStack, &sp->s_progv[0], "Corrupted change stack", 0);
		}
	}
	return 1;
}

/* commit changes, if any made */
int
ssamcommit(ssam_t *sp, int argc, int flags)
{
	if (argc > 0) {
		if (changed(sp) && !(flags & Writeable)) {
			(void) fprintf(stderr, "To make updates to files, use -w flag to ssam\n");
			return 0;
		}
		if (!writefiles(sp)) {
			return 0;
		}
	} else if (!(flags & NoEcho)) {
		if (!f_write(sp->s_fcurr, stdout)) {
			return 0;
		}
	}
	return 1;
}