/************************************************************************
 *	Custom regular expression library, *fully* egrep compatible	*
 *									*
 *	Seems to be relatively bug free.				*
 *									*
 *	Copyright (c) 1991-1992, S.R. van den Berg, The Netherlands	*
 *	The sources can be freely copied for non-commercial use.	*
 *	#include "README"						*
 *									*
 ************************************************************************/
#ifdef RCS
static char rcsid[]="$Id: regexp.c,v 2.12 1992/01/21 17:27:04 berg Rel $";
#endif
#include "config.h"
#include "procmail.h"
#include "shell.h"

#define R_BEG_GROUP	'('
#define R_OR		'|'
#define R_END_GROUP	')'
#define R_0_OR_MORE	'*'
#define R_0_OR_1	'?'
#define R_1_OR_MORE	'+'
#define R_DOT		'.'
#define R_SOL		'^'
#define R_EOL		'$'
#define R_BEG_CLASS	'['
#define R_NOT_CLASS	'^'
#define R_RANGE		'-'
#define R_END_CLASS	']'
#define R_ESCAPE	'\\'

#define BITS_P_CHAR		8
#define OPB			(1<<BITS_P_CHAR)
#define OPC_EPS			OPB
#define OPC_CLASS		(OPB+1)
#define OPC_DOT			(OPB+2)
#define OPC_FIN			(OPB+3)

#define bit_type		unsigned
#define bit_bits		(sizeof(bit_type)*8)
#define bit_index(which)	((unsigned)(which)/bit_bits)
#define bit_mask(which)		((unsigned)1<<(unsigned)(which)%bit_bits)
#define bit_toggle(name,which)	(name[bit_index(which)]^=bit_mask(which))
#define bit_test(name,which)	(!!(name[bit_index(which)]&bit_mask(which)))
#define bit_set(name,which,value)	\
 (value?(name[bit_index(which)]|=bit_mask(which)):\
 (name[bit_index(which)]&=~bit_mask(which)))
#define bit_field(name,size)	bit_type name[((size)+bit_bits-1)/bit_bits]

#define SZ(x)		(sizeof(struct x))
#define Ceps		(struct eps*)
#define epso(to,add)	(Ceps((char*)(to)+(add)))
#define ii		(aleps.topc)
#define jj		(aleps.ua.jjua)
#define jjp		(aleps.ua.tnext)

/* the spawn and stack members are reused in the normal opcodes as pc fields */
static struct eps{unsigned opc;struct eps*stack,*spawn,*next;}*r;
static struct{unsigned topc;union{struct eps*tnext;int jjua;}ua;}aleps;
static uchar*p;
static ignore_case;

struct chclass {unsigned opc_;struct eps*stack_,*spawn_,*next_;
 bit_field(c,OPB);};

static puteps(spot,to,aswell)struct eps*const spot;    /* epsilon transition */
 const struct eps*const to,*const aswell;
{ spot->opc=OPC_EPS;spot->next=to!=spot?Ceps to:Ceps aswell;
  spot->spawn=aswell!=spot?Ceps aswell:Ceps to;spot->stack=0;
}

static putneps(spot,to)struct eps*const spot;const struct eps*const to;
{ puteps(spot,to,spot+1);
}

#define rAc	(((struct chclass*)r)->c)

static bseti(i,j)unsigned i;const int j;
{ bit_set(rAc,i,j);			   /* mark 'i' as being in the class */
  if(ignore_case)				  /* mark the other case too */
   { if(i-'A'<26)						/* uppercase */
	i+='a'-'A';
     else if(i-'a'<26)						/* lowercase */
	i-='a'-'A';
     else return;						  /* no case */
     bit_set(rAc,i,j);
   }
}

static por();

static psimp(e)struct eps const*const e;
{ switch(*p)
   { case R_BEG_GROUP:++p;por(e);return;	  /* not so simple after all */
     case R_BEG_CLASS:					   /* a simple class */
	jj=R_NOT_CLASS==*++p;
	if(e)
	 { r->opc=OPC_CLASS;r->next=Ceps e;r->spawn=r->stack=0;
	   ii=maxindex(rAc);
	   do rAc[ii]=jj?~0:0;			     /* preset the bit field */
	   while(ii--);
	 }
	if(jj)					  /* skip the 'not' modifier */
	 { ++p;
	   if(e)
	      bit_toggle(rAc,'\n');
	 }
	if(*p==R_END_CLASS)	  /* right at the start, cannot mean the end */
	 { ++p;
	   if(e)
	    { ii=R_END_CLASS;bit_toggle(rAc,R_END_CLASS);
	    }
	 }
	else if(*p==R_RANGE)				/* take it literally */
	 { ++p;
	   if(e)
	    { ii=R_RANGE;bit_toggle(rAc,R_RANGE);
	    }
	 }
	for(;;++p)
	 { switch(*p)
	    { case R_END_CLASS:++p;
	      case '\0':r=epso(r,SZ(chclass));return;
	      case R_RANGE:
		 switch(*++p)
		  { default:
		       if(e)
			  while(++ii<*p)	    /* mark all in the range */
			     bseti(ii,!jj);
		       break;
		    case '\0':case R_END_CLASS:--p;		/* literally */
		  }
	    }
	   if(e)
	      bseti(ii= *p,!jj);	      /* a normal character, mark it */
	 }
     case '\0':return;
     case R_DOT:			 /* matches everything but a newline */
	if(e)
	 { r->opc=OPC_DOT;goto fine;
	 }
	goto fine2;
     case R_EOL:case R_SOL:		      /* match a newline (in effect) */
	if(e)
	 { r->opc='\n';goto fine;
	 }
	goto fine2;
     case R_ESCAPE:					  /* quote something */
	if(!*++p)					 /* nothing to quote */
	   --p;
   }
  if(e)						      /* a regular character */
   { r->opc=ignore_case&&(unsigned)*p-'A'<26?*p+'a'-'A':*p;
fine:
     r->next=Ceps e;r->spawn=r->stack=0;
   }
fine2:
  ++p;++r;
}

#define EOS(x)	(jjp?jjp:(x))

static pnorm(e)struct eps const*const e;
{ void*pold;struct eps*rold;
  for(;;)
   { pold=p;rold=r;psimp(Ceps 0);ii= *p;		    /* skip it first */
     jjp=p[1]==R_OR||p[1]==R_END_GROUP||!p[1]?Ceps e:Ceps 0;
     if(e)
      { p=pold;pold=r;
      }
     switch(ii)			   /* check for any of the postfix operators */
      { case R_0_OR_MORE:++r;
	   if(e)			  /* first an epsilon, then the rest */
	    { putneps(rold,EOS(r));r=rold+1;psimp(rold);
	    }
	   goto incagoon;
	case R_1_OR_MORE:				   /* first the rest */
	   if(e)				      /* and then an epsilon */
	    { puteps(r,rold,EOS(r+1));r=rold;psimp(Ceps pold);
	    }
	   ++r;goto incagoon;
	case R_0_OR_1:++r;
	   if(e)			  /* first an epsilon, then the rest */
	    { putneps(rold,r=EOS(r));pold=r;r=rold+1;psimp(Ceps pold);
	    }
incagoon:  switch(*++p)			/* at the end of this group already? */
	    { case R_OR:case R_END_GROUP:case '\0':return;
	    }
	   continue;				 /* regular end of the group */
	case R_OR:case R_END_GROUP:case '\0':
	   if(e)
	    { r=rold;psimp(e);
	    }
	   return;
      }
     if(e)			/* no fancy postfix operators, plain vanilla */
      { r=rold;psimp(Ceps pold);
      }
   }
}

static por(e)struct eps const*const e;
{ uchar*pold;struct eps*rold;
  for(;;)
     for(pold=p;;)
      { rold=r;
	switch(*p)
	 { default:pnorm(Ceps 0);r=rold;continue;     /* still in this group */
	   case '\0':case R_END_GROUP:	       /* found the end of the group */
	      if(p==pold)				 /* empty 'or' group */
	       { if(e)
		    puteps(r,e,e);	       /* misused epsilon as branch, */
		 ++r;		/* let the optimiser (fillout()) take it out */
	       }
	      else
	       { p=pold;pnorm(e);			/* normal last group */
	       }
	      if(*p)
		 ++p;
	      return;
	   case R_OR:++r;
	      if(p==pold)				 /* empty 'or' group */
	       { if(e)
		    putneps(rold,e);			  /* special epsilon */
	       }
	      else
	       { p=pold;pnorm(e);	      /* normal 'or' group, first an */
		 if(e)				   /* epsilon, then the rest */
		    putneps(rold,r);
	       }
	      ++p;
	 }
	break;
      }
}

static findandrep(old,new)register struct eps**const old;
 struct eps*const new;
{ register struct eps*i,*t= *old;			   /* save the value */
  for(i=r;;)			     /* change all pointers from *old to new */
   { if(i->next==t)
	i->next=new;
     if(i->spawn==t)
	i->spawn=new;
     switch(i->opc)
      { case OPC_FIN:*old=t;return;	   /* last one, restore value, ready */
	case OPC_CLASS:i=epso(i,SZ(chclass));break;
	default:++i;
      }
   }
}

#define drs(m)	(*(struct eps**)((char*)*stack+(ioffsetof(struct eps,m)^ofs)))

static cstack(stack,ofs)struct eps**const stack;
{ if(drs(next)->stack==Ceps p)
   { findandrep(*stack,drs(next));*stack=drs(spawn);return 1;
   }
  return 0;
}
    /* break up any closed epsilon circles, otherwise they can't be executed */
static fillout(stack)struct eps**const stack;
{ if((*stack)->opc!=OPC_EPS||(*stack)->stack)
     return 0;
  (*stack)->stack=Ceps p;			    /* mark this one as used */
#define RECURS(nxt)	\
  do\
     if(cstack(stack,ioffsetof(struct eps,nxt)^ioffsetof(struct eps,next)))\
	return 1;\
  while(fillout(&(*stack)->nxt))
  RECURS(next);RECURS(spawn);return 0;				  /* recurse */
}

void*bregcomp(a,ign_case)char const*a;
{ struct eps*st;size_t i;      /* first a trial run, determine memory needed */
  p=(uchar*)a;ignore_case=ign_case;r=Ceps&aleps+1;por(Ceps 0);
  st=malloc((i=(char*)r-(char*)&aleps)+ioffsetof(struct eps,stack)+sizeof r);
  putneps(st,r=st+1);p=(uchar*)a;por(Ceps((char*)st+i));   /* really compile */
  r->opc=OPC_FIN;r->stack=0;				  /* tack on the end */
  for(r=st;;)				 /* simplify the compiled code (i.e. */
     switch(st->opc)		      /* take out cyclic epsilon references) */
      { case OPC_FIN:return r;					 /* finished */
	case OPC_CLASS:st=epso(st,SZ(chclass));break;		     /* skip */
	case OPC_EPS:p=(uchar*)st;fillout(&st);		       /* check tree */
	default:++st;						 /* skip too */
      }
}

#define XOR1		\
 (ioffsetof(struct eps,spawn)^ioffsetof(struct eps,stack))
#define PC(this,t)	(*(struct eps**)((char*)(this)+(t)))

char*bregexec(code,text,len,ign_case)struct eps*code;const uchar*text;
 size_t len;
{ register struct eps*reg,*t,*stack,*other,*this;unsigned i,th1,ot1;
  if(code[1].opc==OPC_EPS)
     ++code;		   /* two epsilons at the start would be superfluous */
  (this=code)->stack=0;th1=ioffsetof(struct eps,spawn);
  ot1=ioffsetof(struct eps,stack);--text;++len;
  i='\n';goto setups;	      /* make sure any beginning-of-line-hooks catch */
  do
   { i= *++text;			 /* get the next real-text character */
lastrun:				     /* switch this & other pc-stack */
     th1^=XOR1;ot1^=XOR1;this=other;
setups:
     reg=(other=stack=code)->next;goto nostack;
     do					 /* pop next entry off this pc-stack */
      { reg=(t=this)->next;this=PC(t,th1);PC(t,th1)=0;goto nostack;
	do				/* pop next entry off the work-stack */
	 { stack=(t=stack)->stack;t->stack=0;reg=t->spawn;
nostack:   switch(reg->opc-OPB)	    /* push spawned branch on the work-stack */
	    { default:
		 if(ign_case&&i-'A'<26)
		    i+='a'-'A';		     /* transmogrify it to lowercase */
		 if(i==reg->opc)		  /* regular character match */
		    goto yep;
		 break;
	      case OPC_EPS-OPB:reg->stack=stack;reg=(stack=reg)->next;
		 goto nostack;
	      case OPC_FIN-OPB:		   /* hurray!  complete regexp match */
		 return(char*)text;		/* return one past the match */
	      case OPC_CLASS-OPB:
		 if(bit_test(((struct chclass*)reg)->c,i))
		    goto yep;			       /* character in class */
		 break;
	      case OPC_DOT-OPB:				     /* dot-wildcard */
		 if(i!='\n')
yep:		    if(!PC(reg,ot1))		     /* state not yet pushed */
		     { PC(reg,ot1)=other;other=reg;    /* push location onto */
		     }					   /* other pc-stack */
	    }
	 }
	while(stack);			      /* the work-stack is not empty */
      }
     while(this!=code);			       /* this pc-stack is not empty */
   }
  while(--len);					     /* still text to search */
  if(ign_case!=2)					      /* out of text */
   { ign_case=2;len=1;++text;goto lastrun;	 /* check if we just matched */
   }
  return 0;							 /* no match */
}
