path: root/src/egrep.y

%{
/*===========================================================================
 Copyright (c) 1998-2000, The Santa Cruz Operation 
 All rights reserved.
 
 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions are met:

 *Redistributions of source code must retain the above copyright notice,
 this list of conditions and the following disclaimer.

 *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.

 *Neither name of The Santa Cruz Operation nor the names of its contributors
 may be used to endorse or promote products derived from this software
 without specific prior written permission. 

 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``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 REGENTS OR CONTRIBUTORS 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. 
 =========================================================================*/

/* $Id: egrep.y,v 1.11 2006/04/21 10:45:48 broeker Exp $ */

/*
 * egrep -- fine lines containing a regular expression
 */
%}

%token CHAR DOT CCL NCCL OR CAT STAR PLUS QUEST
%left OR
%left CHAR DOT CCL NCCL '('
%left CAT
%left STAR PLUS QUEST

%{
#include "global.h"
#include <ctype.h>
#include <stdio.h>

#include <setjmp.h>	/* jmp_buf */

#define nextch()	(*input++)

#define MAXLIN 350
#define MAXPOS 4000
#define NCHARS 256
#define NSTATES 128
#define FINAL -1
static	char gotofn[NSTATES][NCHARS];
static	int state[NSTATES];
static	char out[NSTATES];
static	unsigned int line;
static	int name[MAXLIN];
static	unsigned int left[MAXLIN];
static	unsigned int right[MAXLIN];
static	unsigned int parent[MAXLIN];
static	int foll[MAXLIN];
static	int positions[MAXPOS];
static	char chars[MAXLIN];
static	int nxtpos;
static	int nxtchar;
static	int tmpstat[MAXLIN];
static	int initstat[MAXLIN];
static	int xstate;
static	int count;
static	int icount;
static	char *input;
static	long lnum;
static	int iflag;
static	jmp_buf	env;	/* setjmp/longjmp buffer */
static	char *message;	/* error message */

/* Internal prototypes: */
static	void cfoll(int v);
static	void cgotofn(void);
static	int cstate(int v);
static	int member(int symb, int set, int torf);
static	int notin(int n);
static	void synerror(void);
static	void overflo(void);
static	void add(int *array, int n);
static	void follow(unsigned int v);
static	int unary(int x, int d);
static	int node(int x, int l, int r);
static	unsigned int cclenter(int x);
static	unsigned int enter(int x);

static int yylex(void);
static int yyerror(char *);
%}

%%
s:	t
		{ unary(FINAL, $1);
		  line--;
		}
	;
t:	b r
		{ $$ = node(CAT, $1, $2); }
	| OR b r OR
		{ $$ = node(CAT, $2, $3); }
	| OR b r
		{ $$ = node(CAT, $2, $3); }
	| b r OR
		{ $$ = node(CAT, $1, $2); }
	;
b:
		{ $$ = enter(DOT);
		   $$ = unary(STAR, $$); }
	;
r:	CHAR
		{ $$ = enter($1); }
	| DOT
		{ $$ = enter(DOT); }
	| CCL
		{ $$ = cclenter(CCL); }
	| NCCL
		{ $$ = cclenter(NCCL); }
	;

r:	r OR r
		{ $$ = node(OR, $1, $3); }
	| r r %prec CAT
		{ $$ = node(CAT, $1, $2); }
	| r STAR
		{ $$ = unary(STAR, $1); }
	| r PLUS
		{ $$ = unary(PLUS, $1); }
	| r QUEST
		{ $$ = unary(QUEST, $1); }
	| '(' r ')'
		{ $$ = $2; }
	| error 
	;

%%
static int
yyerror(char *s)
{
	message = s;
	longjmp(env, 1);
	return 1;		/* silence a warning */
}

static int
yylex(void)
{
    int cclcnt, x;
    char c, d;

    switch(c = nextch()) {
    case '|':
	return (OR);
    case '*':
	return (STAR);
    case '+':
	return (PLUS);
    case '?':
	return (QUEST);
    case '(':
	return (c);
    case ')':
	return (c);
    case '.':
	return (DOT);
    case '\0':
	return (0);
    case '\n':
	return (OR);
    case '[': 
	x = CCL;
	cclcnt = 0;
	count = nxtchar++;
	if ((c = nextch()) == '^') {
	    x = NCCL;
	    c = nextch();
	}
	do {
	    if (c == '\0')
		synerror();
	    if (c == '-'
		&& cclcnt > 0
		&& chars[nxtchar-1] != 0) {
		if ((d = nextch()) != 0) {
		    c = chars[nxtchar-1];
		    while ((unsigned int)c < (unsigned int)d) {
			if (nxtchar >= MAXLIN)
			    overflo();
			chars[nxtchar++] = ++c;
			cclcnt++;
		    }
		    continue;
		} /* if() */
	    } /* if() */
	    if (nxtchar >= MAXLIN)
		overflo();
	    chars[nxtchar++] = c;
	    cclcnt++;
	} while ((c = nextch()) != ']');
	chars[count] = cclcnt;
	return (x);
    case '\\':
	if ((c = nextch()) == '\0')
	    synerror();
	/* not reached */
    case '$':
    case '^':
	c = '\n';
	/* fall through */
    default:
	yylval = c;
	return (CHAR);
    }
}

static void
synerror(void)
{
    yyerror("Syntax error");
}

static unsigned int
enter(int x)
{
    if(line >= MAXLIN)
	overflo();
    name[line] = x;
    left[line] = 0;
    right[line] = 0;
    return(line++);
}

static unsigned int
cclenter(int x)
{
    unsigned int linno;

    linno = enter(x);
    right[linno] = count;
    return (linno);
}

static int
node(int x, int l, int r)
{
    if(line >= MAXLIN)
	overflo();
    name[line] = x;
    left[line] = l;
    right[line] = r;
    parent[l] = line;
    parent[r] = line;
    return(line++);
}

static int
unary(int x, int d)
{
    if(line >= MAXLIN)
	overflo();
    name[line] = x;
    left[line] = d;
    right[line] = 0;
    parent[d] = line;
    return(line++);
}

static void
overflo(void)
{
    yyerror("internal table overflow");
}

static void
cfoll(int v)
{
    unsigned int i;

    if (left[v] == 0) {
	count = 0;
	for (i = 1; i <= line; i++) 
	    tmpstat[i] = 0;
	follow(v);
	add(foll, v);
    } else if (right[v] == 0)
	cfoll(left[v]); 
    else {
	cfoll(left[v]);
	cfoll(right[v]);
    }
}

static void
cgotofn(void)
{
    unsigned int i, n, s;
    int c, k;
    char symbol[NCHARS];
    unsigned int j, l, pc, pos;
    unsigned int nc;
    int curpos;
    unsigned int num, number, newpos;

    count = 0;
    for (n=3; n<=line; n++)
	tmpstat[n] = 0;
    if (cstate(line-1)==0) {
	tmpstat[line] = 1;
	count++;
	out[0] = 1;
    }
    for (n=3; n<=line; n++)
	initstat[n] = tmpstat[n];
    count--;		/*leave out position 1 */
    icount = count;
    tmpstat[1] = 0;
    add(state, 0);
    n = 0;
    for (s = 0; s <= n; s++)  {
	if (out[s] == 1)
	    continue;
	for (i = 0; i < NCHARS; i++)
	    symbol[i] = 0;
	num = positions[state[s]];
	count = icount;
	for (i = 3; i <= line; i++)
	    tmpstat[i] = initstat[i];
	pos = state[s] + 1;
	for (i = 0; i < num; i++) {
	    curpos = positions[pos];
	    if ((c = name[curpos]) >= 0) {
		if (c < NCHARS) {
		    symbol[c] = 1;
		} else if (c == DOT) {
		    for (k = 0; k < NCHARS; k++)
			if (k != '\n')
			    symbol[k] = 1;
		} else if (c == CCL) {
		    nc = chars[right[curpos]];
		    pc = right[curpos] + 1;
		    for (j = 0; j < nc; j++)
			symbol[(unsigned char)(chars[pc++])] = 1;
		} else if (c == NCCL) {
		    nc = chars[right[curpos]];
		    for (j = 0; j < NCHARS; j++) {
			pc = right[curpos] + 1;
			for (l = 0; l < nc; l++)
			    if (j==(unsigned char)(chars[pc++]))
				goto cont;
			if (j != '\n')
			    symbol[j] = 1;
		    cont:
			;
		    }
		}
	    }
	    pos++;
	} /* for (i) */
	for (c=0; c<NCHARS; c++) {
	    if (symbol[c] == 1) {
		/* nextstate(s,c) */
		count = icount;
		for (i=3; i <= line; i++)
		    tmpstat[i] = initstat[i];
		pos = state[s] + 1;
		for (i=0; i<num; i++) {
		    curpos = positions[pos];
		    if ((k = name[curpos]) >= 0)
			if ((k == c)
			    || (k == DOT)
			    || (k == CCL && member(c, right[curpos], 1))
			    || (k == NCCL && member(c, right[curpos], 0))
			    ) {
			    number = positions[foll[curpos]];
			    newpos = foll[curpos] + 1;
			    for (j = 0; j < number; j++) {
				if (tmpstat[positions[newpos]] != 1) {
				    tmpstat[positions[newpos]] = 1;
				    count++;
				}
				newpos++;
			    }
			}
		    pos++;
		} /* end nextstate */
		if (notin(n)) {
		    if (n >= NSTATES)
			overflo();
		    add(state, ++n);
		    if (tmpstat[line] == 1)
			out[n] = 1;
		    gotofn[s][c] = n;
		} else {
		    gotofn[s][c] = xstate;
		}
	    } /* if (symbol) */
	} /* for(c) */
    } /* for(s) */
}

static int
cstate(int v)
{
	int b;
	if (left[v] == 0) {
		if (tmpstat[v] != 1) {
			tmpstat[v] = 1;
			count++;
		}
		return(1);
	}
	else if (right[v] == 0) {
		if (cstate(left[v]) == 0) return (0);
		else if (name[v] == PLUS) return (1);
		else return (0);
	}
	else if (name[v] == CAT) {
		if (cstate(left[v]) == 0 && cstate(right[v]) == 0) return (0);
		else return (1);
	}
	else { /* name[v] == OR */
		b = cstate(right[v]);
		if (cstate(left[v]) == 0 || b == 0) return (0);
		else return (1);
	}
}

static int
member(int symb, int set, int torf)
{
    unsigned int i, num, pos;

    num = chars[set];
    pos = set + 1;
    for (i = 0; i < num; i++)
	if (symb == (unsigned char)(chars[pos++]))
	    return (torf);
    return (!torf);
}

static int
notin(int n)
{
	int i, j, pos;
	for (i=0; i<=n; i++) {
		if (positions[state[i]] == count) {
			pos = state[i] + 1;
			for (j=0; j < count; j++)
				if (tmpstat[positions[pos++]] != 1) goto nxt;
			xstate = i;
			return (0);
		}
		nxt: ;
	}
	return (1);
}

static void
add(int *array, int n)
{
    unsigned int i;

    if (nxtpos + count > MAXPOS)
	overflo();
    array[n] = nxtpos;
    positions[nxtpos++] = count;
    for (i=3; i <= line; i++) {
	if (tmpstat[i] == 1) {
	    positions[nxtpos++] = i;
	}
    }
}

static void
follow(unsigned int v)
{
    unsigned int p;

    if (v == line) 
	return;
    p = parent[v];
    switch(name[p]) {
    case STAR:
    case PLUS:	cstate(v);
	follow(p);
	return;

    case OR:
    case QUEST:	follow(p);
	return;

    case CAT:
	if (v == left[p]) {
	    if (cstate(right[p]) == 0) {
		follow(p);
		return;
	    }
	} else 
	    follow(p);
	return;
    case FINAL:
	if (tmpstat[line] != 1) {
	    tmpstat[line] = 1;
	    count++;
	}
	return;
    }
}

char *
egrepinit(char *egreppat)
{
    /* initialize the global data */
    memset(gotofn, 0, sizeof(gotofn));
    memset(state, 0, sizeof(state));
    memset(out, 0, sizeof(out));
    line = 1;
    memset(name, 0, sizeof(name));
    memset(left, 0, sizeof(left));
    memset(right, 0, sizeof(right));
    memset(parent, 0, sizeof(parent));
    memset(foll, 0, sizeof(foll));
    memset(positions, 0, sizeof(positions));
    memset(chars, 0, sizeof(chars));
    nxtpos = 0;
    nxtchar = 0;
    memset(tmpstat, 0, sizeof(tmpstat));
    memset(initstat, 0, sizeof(initstat));
    xstate = 0;
    count = 0;
    icount = 0;
    input = egreppat;
    message = NULL;
    if (setjmp(env) == 0) {
	yyparse();
	cfoll(line-1);
	cgotofn();
    }
    return(message);
}

int
egrep(char *file, FILE *output, char *format)
{
    char *p;
    unsigned int cstat;
    int ccount;
    char buf[2*BUFSIZ];
    char *nlp;
    unsigned int istat;
    int in_line;
    FILE *fptr;

    if ((fptr = myfopen(file, "r")) == NULL) 
	return(-1);

    ccount = 0;
    lnum = 1;
    in_line = 0;
    p = buf;
    nlp = p;
    if ((ccount = fread(p, sizeof(char), BUFSIZ, fptr)) <= 0)
	goto done;
    in_line = 1;
    istat = cstat = (unsigned int) gotofn[0]['\n'];
    if (out[cstat])
	goto found;
    for (;;) {
	if (!iflag)
	    cstat = (unsigned int) gotofn[cstat][(unsigned int)*p&0377];
	/* all input chars made positive */
	else
	    cstat = (unsigned int) gotofn[cstat][tolower((int)*p&0377)];
	/* for -i option*/
	if (out[cstat]) {
	found:
	    for(;;) {
		if (*p++ == '\n') {
		    in_line = 0;
		succeed:
		    fprintf(output, format, file, lnum);
		    if (p <= nlp) {
			while (nlp < &buf[2*BUFSIZ])
			    putc(*nlp++, output);
			nlp = buf;
		    }
		    while (nlp < p)
			putc(*nlp++, output);
		    lnum++;
		    nlp = p;
		    if ((out[(cstat=istat)]) == 0)
			goto brk2;
		} /* if (p++ == \n) */
	    cfound:
		if (--ccount <= 0) {
		    if (p <= &buf[BUFSIZ]) {
			ccount = fread(p, sizeof(char), BUFSIZ, fptr);
		    } else if (p == &buf[2*BUFSIZ]) {
			p = buf;
			ccount = fread(p, sizeof(char), BUFSIZ, fptr);
		    } else {
			ccount = fread(p, sizeof(char), &buf[2*BUFSIZ] - p,
				       fptr);
		    }
		    if (ccount <= 0) {
			if (in_line) {
			    in_line = 0;
			    goto succeed;
			}
			goto done;
		    }
		} /* if(ccount <= 0) */
		in_line = 1;
	    } /* for(ever) */
	} /* if(out[cstat]) */

	if (*p++ == '\n') {
	    in_line = 0;
	    lnum++;
	    nlp = p;
	    if (out[(cstat=istat)])
		goto cfound;
	}
    brk2:
	if (--ccount <= 0) {
	    if (p <= &buf[BUFSIZ]) {
		ccount = fread(p, sizeof(char), BUFSIZ, fptr);
	    } else if (p == &buf[2*BUFSIZ]) {
		p = buf;
		ccount = fread(p, sizeof(char), BUFSIZ, fptr);
	    } else {
		ccount = fread(p, sizeof(char), &buf[2*BUFSIZ] - p, fptr);
	    }
	    if (ccount <= 0) 
		break;
	}
	in_line = 1;
    }
done:
    fclose(fptr);
    return(0);
}

/* FIXME HBB: should export this to a separate file and use
 * AC_REPLACE_FUNCS() */
#if !STDC_HEADERS && !defined(HAVE_MEMSET) && !defined(HAVE_MEMORY_H)
/*LINTLIBRARY*/
/*
 * Set an array of n chars starting at sp to the character c.
 * Return sp.
 */
char *
memset(char *sp, char c, int n)
{
	char *sp0 = sp;

	while (--n >= 0)
		*sp++ = c;
	return (sp0);
}
#endif

void
egrepcaseless(int i)
{
	iflag = i;	/* simulate "egrep -i" */
}