/*---------------------------------------------------------------------------
 *	     TOOLS.C  the expression parser used by grep 
 *
 *
 *		  Copyright (c)	1984 Allen Holub
 *	Copyright (c) 1984 Software Engineering	Consultants
 *			P.O. Box 5679
 *		     Berkeley, CA.  94705
 *
 *		       All rights reserved.
 *
 *	This program may be copied for personal, non-commmercial use
 *	only, provided that this copyright notice is included in all
 *	copies and that	this program is	not modified in	any way.
 *	Copying	for any	other use without previously obtaining the 
 *	written	permission of the author is prohibited.
 *
 *---------------------------------------------------------------------------
 */


#include <stdio.h>
#include "tools.h"
#include <ctype.h>
#include <malloc.h>
#include <string.h>

/*	This module contains the various routines needed by grep 
 *	to match regular expressions. Routines are ordered alphabeticaly.
 */

int	amatch(lin, pat,boln)
char	*lin, *boln;
TOKEN	*pat;
{
	register  char	*bocl, *rval, *strstart;
	
	if (pat	== 0)	return (0);
	
	strstart = lin;
	
	while (pat)
	{
		if (pat->tok ==	CLOSURE	  &&   pat->next)
		{
			pat = pat->next;
			bocl = lin;
			while (*lin  &&	 omatch(&lin, pat))
				;
			if (pat	= pat->next)
			{ 
				while (bocl <= lin)
				{
					if (rval = amatch(lin, pat, boln))
						return(rval);
					else   
						--lin;
				}
				return (0);
			}
		}
      else if  ( omatch(&lin, pat, boln) )
			pat = pat->next;
      else  
			return(0);
	}
	return ( max(strstart	, --lin) );
}

/* ----------------------------------------------------------------------- */

delete (ch, str)
int	ch;
register char	*str;
{
	ch &= 0xff;
	while (*str && *str != ch)
		str++;
	while (*str)
	{
		*str = *(str+1);
		str++;
	}
}
      
/* ----------------------------------------------------------------------- */

int	dodash(delim, src, map)
int	delim;
char	*src, *map;
{
	register int	first,last;
	char		*start;

	start =	src;

	while (*src  &&	 *src != delim)
	{
		if (*src != '-')
			setbit (esc(&src),map,1);
		else if	(src ==	start || *(src+1) == delim)
			setbit ('-',map,1);
		else
		{	
			src++;
			if (*src < *(src-2))
			{	
				first =	*src;
				last = *(src-2);
			}
			else
			{      
				first =	*(src-2);
				last = *src;
			}
			while (++first <= last)
				setbit(first,map,1);
		}
	src++;
	}
	return (src);
}

/* ------------------------------------------------------------------------ */

int	esc(s)
char	**s;
{
	register int	rval;

	if (**s	!= ESCAPE)
		rval = **s;
	else
	{
		(*s)++;

		switch (toupper(**s))
		{
		case '\000':	rval = ESCAPE;	break;
		case 'S':	rval = ' '   ;	break;
		case 'N':	rval = '\n'  ;	break;
		case 'T':	rval = '\t'  ;	break;
		case 'B':	rval = '\b'  ;	break;
		case 'R':	rval = '\r'  ;	break;
		default:	rval = **s   ;
		}
	}
	return (rval);
}

/* ----------------------------------------------------------------------- */

TOKEN	*getpat(arg)
char	*arg;
{
   return (makepat(arg, '\000',0));
}

/* ----------------------------------------------------------------------- */

insert(ch, str)
int	ch;
register char	*str;
{
	register char	*bp;
	bp = str;
	while (*str)
		str++;
	do
	{
		*(str+1) = *str;
		str--;
	} while	(str >=	bp);
	*bp = ch;
}

/* ----------------------------------------------------------------------- */

char	*in_string(delim,str)
register int	delim;
register char	*str;
{
	delim &= 0x7f;
	while (*str  &&	 *str != delim)	
		str++;
	return (*str ? str : 0);
}

/* ----------------------------------------------------------------------- */

int isalphanum(c)
int	c;
{
	return (('a' <=	c && c <= 'z') ||
		('A' <=	c && c <= 'Z') ||
		('0' <=	c && c <= '9') 
	       );
}

/* ----------------------------------------------------------------------- */ 

TOKEN *makepat(arg, delim, lit)
char	*arg;
int	delim;
int lit ;
{
	TOKEN	*head, *tail;
	TOKEN	*ntok;
	char	buf[CLS_SIZE];
	int	error;

	if (*arg=='\0' || *arg==delim || *arg=='\n' || *arg==CLOSURE)
		return (0);
	error =	0;
	head = 0;
	tail = 0;

	while (*arg && *arg != delim &&	*arg !=	'\n' &&	!error)
	{
		ntok = malloc(TOKSIZE);
		ntok->bitmap = &(ntok->lchar);
		ntok->lchar = '\000';
		ntok->next = 0;

      if (lit) {
			ntok->tok = LITCHAR;
         ntok->lchar = *arg;
      } else switch (*arg)
		{
		case ANY:
			ntok->tok = ANY;
			break;
		case BOL:
			if (head==0)  
				ntok->tok = BOL;
			else  
				error =	1;
			break;
		case EOL:
			if (*(arg+1) ==	delim || *(arg+1) == '\000'
					      || *(arg+1) == '\n')
				ntok->tok = EOL;
			else	
				error =	1;
			break;
		case CCL:
			if (*(arg+1) ==	NEGATE)
			{
				ntok->tok = NCCL;
				arg += 2;
			}
			else
			{
				ntok->tok = CCL;
				arg++;
			}
			if (ntok->bitmap = makebitmap(128))
				arg = dodash(CCLEND,arg,ntok->bitmap);
			else
			{
				fprintf	(stderr,"Not enough memory for pat\n");
				error =	1;
			}
			break;
		case CLOSURE:
			if (head != 0)
			{
				switch (tail->tok)
				{
				case BOL:
				case EOL:
				case CLOSURE:
					return(0);
				default:
					ntok->tok = CLOSURE;
				}
			}
			break;
		default:
			ntok->tok = LITCHAR;
			ntok->lchar = esc(&arg);
		}

		if (error || ntok == 0)
		{
			unmakepat(head);
			return (0);
		}
		else if	(head == 0)
		{
			ntok->next = 0;
			head = tail = ntok;
		}
		else if	(ntok->tok != CLOSURE)
		{
			tail->next = ntok;
			ntok->next = tail;
			tail = ntok;
		}
		else if	(head != tail)
		{
			(tail->next)->next = ntok;
			ntok->next = tail;
		}
		else
		{
			ntok->next = head;
			tail->next = ntok;
			head = ntok;
		}
		arg++;
	}
	tail->next = 0;
	return (head);
}

/* ----------------------------------------------------------------------- */ 

char	*matchs(line,pat,ret_endp)
char	*line;
TOKEN	*pat;
int	ret_endp;
{
	char	*rval, *bptr;
	bptr = line;
	while (*line)
	{
		if ((rval = amatch(line, pat,bptr)) == 0)
			line++;
		else
		{
			rval = ret_endp	? rval : line ;
			break;
		}
	}
	return (rval);
}

/* ----------------------------------------------------------------------- */ 

stoupper(str)
char	*str;
{
	char	*rval;
	rval = str;
	while (*str)
	{
		if ('a' <= *str && *str <= 'z')
			*str -=	('a' - 'A');
		str++;
	}
	return (rval);
}

/* ----------------------------------------------------------------------- */ 

int	max(x,y)
int	x,y;
{
	return ((x>y) ? x : y);
}

/* ----------------------------------------------------------------------- */ 

int	omatch (linp, pat, boln)
char	**linp,	*boln;
TOKEN	*pat;
{
	register int	advance;
	advance	= -1;
	if ( **linp )
	{
		switch (pat->tok)
		{
		case LITCHAR:
         if (**linp == pat->lchar)
				advance	= 1;
			break;
		case BOL:
			if (*linp == boln) 
				advance	= 0;
			break;
		case ANY:
			if (**linp != '\n')   
				advance	= 1;
			break;
		case EOL:
			if (**linp == '\n')  
				advance	= 0;
		case CCL:
			if (testbit (**linp, pat->bitmap))  
				advance	= 1;
			break;
		case NCCL:
			if (!testbit(**linp, pat->bitmap)) 
				advance	= 1;
			break;
		default:
			printf("omatch:	can't happen\n");
		}
	}
	if (advance >= 0)	
		*linp += advance;
	return (++advance);
}

/* ----------------------------------------------------------------------- */ 

pr_line(ln)
register char	*ln;
{
	for (;*ln;ln++)
	{
		if ((' ' <= *ln)  &&  (*ln <= '~'))
			putchar	(*ln);
		else
		{
			printf ("\\0x%02x", *ln);
			if (*ln	== '\n') 
				putchar	('\n');
		}
	}
}

/* ----------------------------------------------------------------------- */ 

pr_tok(head)
TOKEN	*head;
{
	int	i;
	register char	*str;

	for (;head;head=head->next)
	{
	     if	(head->tok == BOL)   
	     	str = "BOL";
	     else
		switch (head->tok)
		{
		case EOL:
			str = "EOL";
			break;
		case ANY:
			str = "ANY";
			break;
		case LITCHAR:
			str = "LITCHAR";
			break;
		case ESCAPE:
			str = "ESCAPE";
			break;
		case CCL:
			str = "CCL";
			break;
		case CCLEND:
			str = "CCLEND";
			break;
		case NEGATE:
			str = "NEGATE";
			break;
		case NCCL:
			str = "NCCL";
			break;
		case CLOSURE:
			str = "CLOSURE";
			break;
		default:
			str = "**** unknown ****";
		}
		printf("%-8s at: 0x%x, ", str, head);
		if (head->tok == CCL ||	head->tok == NCCL)
		{	printf ("string	(at 0x%x) =<",head->bitmap);
			for  (i	= 0;i <	0x7f;i++)
				if (testbit(i,head->bitmap))
					putchar(i);
			printf (">, ");
		}
		else if	(head->tok == LITCHAR)
			printf ("lchar = %c, ",	head->lchar);
		printf ("next =	0x%x\n", head->next);
	}
	putchar	('\n');
}

/* ----------------------------------------------------------------------- */ 

unmakepat(head)
TOKEN	*head;
{
	register TOKEN	*old_head;

	while (head)
	{
		switch (head->tok)
		{
		case CCL:
		case NCCL: 
			free (head->bitmap);
		default:
			old_head = head;
			head = head->next;
			free(old_head);
			break;
		}
	}
}