/* ====================================================================== */

/* 
			AmigaDOS Pattern Matching Demo
				March 20, 1990

				by Dave Haynie

			Released to the Public Domain

	This is the AmigaDOS Pattern Matcher I developed for DiskSalv 
	V1.40.  So far, it seems to work just fine, and certainly works
	better than any public domain code I managed to dig up, most
	of which was limited to the '?' and '#' characters instead of
	full AmigaDOS patterns.
	
	This will compile under Lattice V5.02 with the command:
	
			lc -L pattern.c
			
	The Lattice global optimizer seems to have trouble with it, at
	least with the V5.02 system.

	With the function prototypes removed, I suspect it would be a
	simple port to the Manx V3.6a compiler.
	
	I'd certainly appreciate any feedback on this code, especially 
	if there are any patterns it doesn't correctly match.  
*/

#include <exec/types.h>
#include <string.h>
#include <stdio.h>
#include <setjmp.h>

/* ====================================================================== */

/* These are my allocator routines, slight variations on the C library
   routines.  The pattern matching code was designed to use the DiskSalv
   safe chunky allocator, and rather than re-write the code to use
   something else, I provide some basically equivalent routines below.
   The pattern compiler allocates string memory, and works best with a
   memory allocator that can be cleaned up at program's end (eg, a plain
   AllocMem() here isn't a good idea). */

jmp_buf		lowmem;		/* Don't forget to initialize this! */

/* This is the basic safe allocator; it always returns a valid pointer.
   The pattern matcher counts on the memory returned having been zeroed
   out! */

char *salloc(LONG size) {
   char *ptr;
   
   if (!(ptr = (char *)malloc(size))) longjmp(lowmem,-1);
   setmem(ptr,size,'\0');
   return ptr;	
}

/* This is just for compatibility purposes. */

void sfree(char *ptr) {
   free(ptr);
}

/* ====================================================================== */

/* This is the definition of a pattern element.  The pattern compiler will
   create an array of these elements from a string passed to it. */

typedef struct {
   char *aux;			/* Auxilary data; string or paren-count */
   BYTE type;			/* Corresponding character type */
} pattern;

/* The types, for the "special" array. */

#define pSTRING	0	/* Plain old string */
#define pALT	1	/* The alternation character */
#define pREP	2	/* The repeat character */
#define pANY	3	/* The match-any character */
#define pNULL	4	/* The match-null character */
#define pSUB	5	/* A subpattern */
#define pEND	6	/* End of the pattern. */

/* This is the definition of a pattern matching function, for use in the
   "MatchSub()" coroutine. */

typedef BOOL (*patfunc)(pattern *, char *);

/* ====================================================================== */

/* This section contains the pattern compiler code. */

/* This function takes in a string from which one parenthesis has been
   stripped.  It returns a pointer to the position of the matching
   parenthesis, or NULL if it isn't found. */

static char *FindParen(char *str) {
   short parencnt = 1;
   
   while (*str) {
      switch (*str) {
         case '(' :
            ++parencnt;
            break;
         case ')' :
            if (--parencnt == 0) return str;
            break;
         default :
            break;      	
      }
      ++str;
   }
   return NULL;
}

/* This function creates a pattern for later pattern matching.  It checks
   syntax as well, since we don't want invalid patterns to possibly crash 
   the machine or otherwise cause trouble.  This is a destructive compile,
   in that it trashes the input string. */
        
pattern *CompilePattern(char *str) {
   pattern *pat, *result = NULL;
   short i = 0, j, tlen, plen = strlen(str)+1;
   char  fch, nch, *sub, *tmp;

   if (!str) return NULL;
   
   pat = (pattern *)salloc(sizeof(pattern)*plen);
   while (fch = *str++) {
      nch = *str;
      switch (fch) {
         case '(' :	/* The start of a group */
            if (nch == '|' || nch == ')') goto fail;
            pat[i].type = pSUB;
            if (!(str = FindParen(sub = str))) goto fail;
            *str++ = '\0';
            if (!(pat[i].aux = (char *)CompilePattern(sub))) goto fail;
            break;
         case ')' :	/* We should never see the end of a group */
            goto fail;
         case '|' :	/* Alternation */
            if (nch == '|' || nch == ')') goto fail;
            pat[i].type = pALT;
            break;
         case '#' :	/* Repeatition */
	    if (nch == '#' || nch == '|' || nch == ')' || !nch) goto fail;
	    pat[i].type = pREP;
	    switch (nch) {
	       case '(' :
	       case '%' :
	       case '?' :
	          break;
	       case '\047':
	          nch = *str++;
	       default:
                  pat[++i].type = pSTRING;
                  pat[i].aux = (char *)salloc(2);
                  pat[i].aux[0] = nch;
	          str++;
	          break;
            }
            break;
         case '?' :	/* One of anything */
            pat[i].type = pANY;
            break;
         case '%' :	/* One of nothing */
            pat[i].type = pNULL;
            break;
         default:	/* Normal characters */
            pat[i].type = pSTRING;
            tmp = (char *)salloc((long)(tlen = strlen(str)+2));
            tmp[0] = fch;
            j = 1;
            while (*str && !strchr("()|#?%",*str)) {
               if (*str == '\047') ++str;
               tmp[j++] = *str++;
            }
            tmp[j] = '\0';
            strupr(strcpy(pat[i].aux = salloc(j+1),tmp));
            sfree(tmp);
            break;
      }
      ++i;
   }
   pat[i++].type = pEND;
   result = (pattern *)memcpy(salloc(sizeof(pattern)*i),(char *)pat,sizeof(pattern)*i);

fail:
   sfree((char *)pat);
   return result;
}

/* ====================================================================== */

/* This is the actual pattern matching code.  This code hasn't been really
   optimized or anything; it's highly recursive, but it's designed to be
   as nice to your stack as possible.  There are four coroutines in my 
   pattern matcher.  The top-level routine "MatchPattern()" takes in a 
   pattern and a string, and knows only how to subdivide an alternated 
   pattern and pass that on the the single pattern matcher, "MatchOne()".  
   That routine knows how to match strings, NULLs, and ANYs.  It calls 
   "MatchRepeat()" to handle the repeat pattern, and "MatchSub()" to handle
   a sub-pattern.  Similarly, the "MatchRepeat()" routine knows how to match
   repeated strings, NULLs, and ANYs.  It also calls the "MatchSub()" routine
   to handle repeated subpatterns.  The "MatchSub()" splits the input string
   into strings for the subpattern and parent pattern to match, and works 
   through these until a match is found or we've tried all possibilities.  
   It calls "MatchPattern()" on a simple subpattern, or "MatchRepeat()" on a 
   repeated subpattern. */

/* Forward Declarations */

static BOOL MatchOne(pattern *, char *);
static BOOL MatchSub(pattern *, pattern *, char *, patfunc);
static BOOL MatchRepeat(pattern *, char *);
       BOOL MatchPattern(pattern *, char *);

/* This function matches a subpattern, where "sub" is the subpattern,
   "pat" is the rest of the pattern at the current level, and "str"
   is the usual string.  The string splitting uses dynamic allocation
   to avoid stack overflows as much as possible, the "subob" function
   is the particular pattern matching function to use on the subpattern. */

static BOOL MatchSub(pattern *sub, pattern *pat, char *str, patfunc subop) {
   short pos, len = strlen(str)+1;
   char *copy = salloc(strlen(str)+1);

   for (pos = 0; pos < len; pos++) {
      if ((*subop)(sub,copy) && MatchOne(pat,str)) {
         sfree(copy);
         return TRUE;
      }
      copy[pos] = *str++;
   }
   sfree(copy);
   return FALSE;
}

/* This function matches a repeat pattern.  It returns the part of the
   string not matched, or NULL if the whole string was matched. */

static BOOL MatchRepeat(pattern *pat, char *str) {
   pattern *local = pat++;

   switch (local->type) {
      case pSTRING	:
         while (TRUE) {
            if (MatchPattern(pat,str)) return TRUE;
            if (strnicmp(str,local->aux,strlen(local->aux))) break;
            str += strlen(local->aux);
         }
         break;
      case pANY	:
         do {
            if (MatchPattern(pat,str)) return TRUE;
         } while (*++str);
         if (pat[0].type == pEND || pat[0].type == pALT) return TRUE;
         break;
      case pNULL	:
         break;
      case pSUB	:
         if (MatchPattern(pat,str)) return TRUE;
         return MatchSub((pattern *)local->aux,pat,str,MatchRepeat);
      case pEND	:
         break;
   }
   return MatchOne(pat,str);
}

/* This function tries to match a single pattern against the given 
   string.  It is up to the calling function to worry about alternation. */

static BOOL MatchOne(pattern *pat, char *str) {
   if (!str) return FALSE;

   while (pat->type != pEND && pat->type != pALT) {
      switch (pat->type) {
         case pSTRING:
            if (strnicmp(str,pat->aux,strlen(pat->aux))) return FALSE;
            str += strlen(pat->aux);
            break;
         case pREP	:
            return MatchRepeat(++pat,str);
         case pANY	:         
            if (!*str++) return FALSE;
            break;
         case pNULL	:
            break;
         case pSUB	:
            return MatchSub((pattern *)pat->aux,pat+1,str,MatchPattern);
      }
      ++pat;
   }
   if (!*str) return TRUE;
   return FALSE;
}

/* This function matches a given string against a precompiled pattern.  The
   main function here doesn't do any actual matching; it just subdivides
   a pattern into individual items based on any alternation used. */

BOOL MatchPattern(pattern *pat, char *str) {
   if (!str) return FALSE;

   while (pat && pat->type != pEND) {
      if (MatchOne(pat,str)) return TRUE;

      while (pat->type != pALT && pat->type != pEND) ++pat;
      if (pat->type == pALT) ++pat;
   } 
   return FALSE;
}

/* ====================================================================== */