/*

 * pattern.c - pattern matching

 *

 * This file is part of zsh, the Z shell.

 *

 * Copyright (c) 1999 Peter Stephenson

 * All rights reserved.

 *

 * Permission is hereby granted, without written agreement and without

 * license or royalty fees, to use, copy, modify, and distribute this

 * software and to distribute modified versions of this software for any

 * purpose, provided that the above copyright notice and the following

 * two paragraphs appear in all copies of this software.

 *

 * In no event shall Peter Stephenson or the Zsh Development Group be liable

 * to any party for direct, indirect, special, incidental, or consequential

 * damages arising out of the use of this software and its documentation,

 * even if Peter Stephenson and the Zsh Development Group have been advised of

 * the possibility of such damage.

 *

 * Peter Stephenson and the Zsh Development Group specifically disclaim any

 * warranties, including, but not limited to, the implied warranties of

 * merchantability and fitness for a particular purpose.  The software

 * provided hereunder is on an "as is" basis, and Peter Stephenson and the

 * Zsh Development Group have no obligation to provide maintenance,

 * support, updates, enhancements, or modifications.

 *

 * Pattern matching code derived from the regexp library by Henry

 * Spencer, which has the following copyright.

 *

 *	Copyright (c) 1986 by University of Toronto.

 *	Written by Henry Spencer.  Not derived from licensed software.

 *

 *	Permission is granted to anyone to use this software for any

 *	purpose on any computer system, and to redistribute it freely,

 *	subject to the following restrictions:

 *

 *	1. The author is not responsible for the consequences of use of

 *		this software, no matter how awful, even if they arise

 *		from defects in it.

 *

 *	2. The origin of this software must not be misrepresented, either

 *		by explicit claim or by omission.

 *

 *	3. Altered versions must be plainly marked as such, and must not

 *		be misrepresented as being the original software.

 *

 * Eagle-eyed readers will notice this is an altered version.  Incredibly

 * sharp-eyed readers might even find bits that weren't altered.

 *

 *

 *      And I experienced a sense that, like certain regular

 *      expressions, seemed to match the day from beginning to end, so

 *      that I did not need to identify the parenthesised subexpression

 *      that told of dawn, nor the group of characters that indicated

 *      the moment when my grandfather returned home with news of

 *      Swann's departure for Paris; and the whole length of the month

 *      of May, as if matched by a closure, fitted into the buffer of my

 *      life with no sign of overflowing, turning the days, like a

 *      procession of insects that could consist of this or that

 *      species, into a random and unstructured repetition of different

 *      sequences, anchored from the first day of the month to the last

 *      in the same fashion as the weeks when I knew I would not see

 *      Gilberte and would search in vain for any occurrences of the

 *      string in the avenue of hawthorns by Tansonville, without my

 *      having to delimit explicitly the start or finish of the pattern.

 *

 *                                 M. Proust, "In Search of Lost Files",

 *                                 bk I, "The Walk by Bourne's Place".

 */

#include "zsh.mdh"

/*

 * The following union is used mostly for alignment purposes.

 * Normal nodes are longs, while certain nodes take a char * as an argument;

 * here we make sure that they both work out to the same length.

 * The compiled regexp we construct consists of upats stuck together;

 * anything else to be added (strings, numbers) is stuck after and

 * then aligned to a whole number of upat units.

 *

 * Note also that offsets are in terms of the sizes of these things.

 */

union upat {

    long l;

    unsigned char *p;

};

typedef union upat *Upat;

#include "pattern.pro"

/* Number of active parenthesized expressions allowed in backreferencing */

#define NSUBEXP  9

/* definition	number	opnd?	meaning */

#define	P_END	  0x00	/* no	End of program. */

#define P_EXCSYNC 0x01	/* no   Test if following exclude already failed */

#define P_EXCEND  0x02	/* no   Test if exclude matched orig branch */

#define	P_BACK	  0x03	/* no	Match "", "next" ptr points backward. */

#define	P_EXACTLY 0x04	/* lstr	Match this string. */

#define	P_NOTHING 0x05	/* no	Match empty string. */

#define	P_ONEHASH 0x06	/* node	Match this (simple) thing 0 or more times. */

#define	P_TWOHASH 0x07	/* node	Match this (simple) thing 1 or more times. */

#define P_GFLAGS  0x08	/* long Match nothing and set globbing flags */

#define P_ISSTART 0x09  /* no   Match start of string. */

#define P_ISEND   0x0a  /* no   Match end of string. */

/* numbered so we can test bit 5 for a branch */

#define	P_BRANCH  0x20	/* node	Match this alternative, or the next... */

#define	P_WBRANCH 0x21	/* uc* node P_BRANCH, but match at least 1 char */

/* excludes are also branches, but have bit 4 set, too */

#define P_EXCLUDE 0x30	/* uc* node Exclude this from previous branch */

#define P_EXCLUDP 0x31	/* uc* node Exclude, using full file path so far */

/* numbered so we can test bit 6 so as not to match initial '.' */

#define	P_ANY	  0x40	/* no	Match any one character. */

#define	P_ANYOF	  0x41	/* str  Match any character in this string. */

#define	P_ANYBUT  0x42	/* str  Match any character not in this string. */

#define P_STAR    0x43	/* no   Match any set of characters. */

#define P_NUMRNG  0x44	/* zr, zr Match a numeric range. */

#define P_NUMFROM 0x45	/* zr   Match a number >= X */

#define P_NUMTO   0x46	/* zr   Match a number <= X */

#define P_NUMANY  0x47	/* no   Match any set of decimal digits */

/* spaces left for P_OPEN+n,... for backreferences */

#define	P_OPEN	  0x80	/* no	Mark this point in input as start of n. */

#define	P_CLOSE	  0x90	/* no	Analogous to OPEN. */

/*

 * no    no argument

 * zr    the range type zrange_t:  may be zlong or unsigned long

 * char  a single char

 * uc*   a pointer to unsigned char, used at run time and initialised

 *       to NULL.

 * str   null-terminated, metafied string

 * lstr  length as long then string, not null-terminated, unmetafied.

 */

/*

 * Notes on usage:

 * P_WBRANCH:  This works like a branch and is used in complex closures,

 *    to ensure we don't succeed on a zero-length match of the pattern,

 *    since that would cause an infinite loop.  We do this by recording

 *    the positions where we have already tried to match.   See the

 *    P_WBRANCH test in patmatch().

 *

 *  P_ANY, P_ANYOF:  the operand is a null terminated

 *    string.  Normal characters match as expected.  Characters

 *    in the range Meta+PP_ALPHA..Meta+PP_UNKNWN do the appropriate

 *    Posix range tests.  This relies on imeta returning true for these

 *    characters.  We treat unknown POSIX ranges as never matching.

 *    PP_RANGE means the next two (possibly metafied) characters form

 *    the limits of a range to test; it's too much like hard work to

 *    expand the range.

 *

 *  P_EXCLUDE, P_EXCSYNC, PEXCEND:  P_EXCLUDE appears in the pattern like

 *    P_BRANCH, but applies to the immediately preceding branch.  The code in

 *    the corresponding branch is followed by a P_EXCSYNC, which simply

 *    acts as a marker that a P_EXCLUDE comes next.  The P_EXCLUDE

 *    has a pointer to char embeded in it, which works

 *    like P_WBRANCH:  if we get to the P_EXCSYNC, and we already matched

 *    up to the same position, fail.  Thus we are forced to backtrack

 *    on closures in the P_BRANCH if the first attempt was excluded.

 *    Corresponding to P_EXCSYNC in the original branch, there is a

 *    P_EXCEND in the exclusion.  If we get to this point, and we did

 *    *not* match in the original branch, the exclusion itself fails,

 *    otherwise it succeeds since we know the tail already matches,

 *    so P_EXCEND is the end of the exclusion test.

 *    The whole sorry mess looks like this, where the upper lines

 *    show the linkage of the branches, and the lower shows the linkage

 *    of their pattern arguments.

 *

 *     	        ---------------------      ----------------------

 *              ^      	       	     v    ^      	         v

 *      ( <BRANCH>:apat-><EXCSYNC> <EXCLUDE>:excpat-><EXCEND> ) tail

 *                               	                         ^

 *		       	  |                                      |

 *			   --------------------------------------

 *

 * P_EXCLUDP: this behaves exactly like P_EXCLUDE, with the sole exception

 *   that we prepend the path so far to the exclude pattern.   This is

 *   for top level file globs, e.g. ** / *.c~*foo.c

 *                                    ^ I had to leave this space

 * P_NUM*: zl is a zlong if that is 64-bit, else an unsigned long.

 */

#define PP_ALPHA  1

#define PP_ALNUM  2

#define PP_ASCII  3

#define PP_BLANK  4

#define PP_CNTRL  5

#define PP_DIGIT  6

#define PP_GRAPH  7

#define PP_LOWER  8

#define PP_PRINT  9

#define PP_PUNCT  10

#define PP_SPACE  11

#define PP_UPPER  12

#define PP_XDIGIT 13

#define PP_UNKWN  14

#define PP_RANGE  15

#define	P_OP(p)		((p)->l & 0xff)

#define	P_NEXT(p)	((p)->l >> 8)

#define	P_OPERAND(p)	((p) + 1)

#define P_ISBRANCH(p)   ((p)->l & 0x20)

#define P_ISEXCLUDE(p)	(((p)->l & 0x30) == 0x30)

#define P_NOTDOT(p)	((p)->l & 0x40)

/* Specific to lstr type, i.e. P_EXACTLY. */

#define P_LS_LEN(p)	((p)[1].l) /* can be used as lvalue */

#define P_LS_STR(p)	((char *)((p) + 2))

/* Flags needed when pattern is executed */

#define P_SIMPLE        0x01	/* Simple enough to be #/## operand. */

#define P_HSTART        0x02	/* Starts with # or ##'d pattern. */

#define P_PURESTR	0x04	/* Can be matched with a strcmp */

/*

 * Increment pointer which may be on a Meta (x is a pointer variable),

 * returning the incremented value (i.e. like pre-increment).

 *

 * In future the following will need to refer to metafied multibyte

 * characters.  References to invidual characters are not turned

 * into a macro when the characters is metafied (c.f. CHARREF()

 * below then the character is not metafied) and will need tracking

 * down.

 */

#define METAINC(x)	((x) += (*(x) == Meta) ? 2 : 1)

/*

 * Return unmetafied char from string (x is any char *)

 */

#define UNMETA(x)	(*(x) == Meta ? (x)[1] ^ 32 : *(x))

#if defined(ZSH_64_BIT_TYPE) || defined(LONG_IS_64_BIT)

typedef zlong zrange_t;

#define ZRANGE_T_IS_SIGNED	(1)

#else

typedef unsigned long zrange_t;

#endif

/*

 * Characters which terminate a pattern segment.  We actually use

 * a pointer patendseg which skips the first character if we are not

 * parsing a file pattern.

 * Note that the size of this and the next array are hard-wired

 * via the definitions.

 */

static char endseg[] = {

    '/',			/* file only */

    '\0', Bar, Outpar,		/* all patterns */

    Tilde			/* extended glob only */

};

#define PATENDSEGLEN_NORM 4

#define PATENDSEGLEN_EXT  5

/* Characters which terminate a simple string */

static char endstr[] = {

    '/',			/* file only */

    '\0', Bar, Outpar, Quest, Star, Inbrack, Inpar, Inang,

				/* all patterns */

    Tilde, Hat, Pound		/* extended glob only */

};

#define PATENDSTRLEN_NORM 9

#define PATENDSTRLEN_EXT  12

/* Default size for pattern buffer */

#define P_DEF_ALLOC 256

/* Flags used in compilation */

static char *patstart, *patparse;	/* input pointers */

static int patnpar;		/* () count */

static char *patcode;		/* point of code emission */

static long patsize;		/* size of code */

static char *patout;		/* start of code emission string */

static long patalloc;		/* size allocated for same */

static char *patendseg;		/* characters ending segment */

static int patendseglen;	/* length of same */

static char *patendstr;		/* characters ending plain string */

static int patendstrlen;	/* length of sameo */

/* Flags used in both compilation and execution */

static int patflags;		    /* flags passed down to patcompile */

static int patglobflags;  /* globbing flags & approx */

/* Add n more characters, ensuring there is enough space. */

enum {

    PA_NOALIGN = 1,

    PA_UNMETA  = 2

};

/**/

static void

patadd(char *add, int ch, long n, int paflags)

{

    /* Make sure everything gets aligned unless we get PA_NOALIGN. */

    long newpatsize = patsize + n;

    if (!(paflags & PA_NOALIGN))

	newpatsize = (newpatsize + sizeof(union upat) - 1) &

		      ~(sizeof(union upat) - 1);

    if (patalloc < newpatsize) {

	long newpatalloc =

	    2*(newpatsize > patalloc ? newpatsize : patalloc);

	patout = (char *)zrealloc((char *)patout, newpatalloc);

	patcode = patout + patsize;

	patalloc = newpatalloc;

    }

    patsize = newpatsize;

    if (add) {

	if (paflags & PA_UNMETA) {

	    /*

	     * Unmetafy and untokenize the string as we go.

	     * The Meta characters in add aren't counted in n.

	     */

	    while (n--) {

		if (itok(*add))

		    *patcode++ = ztokens[*add++ - Pound];

		else if (*add == Meta) {

		    add++;

		    *patcode++ = *add++ ^ 32;

		} else {

		    *patcode++ = *add++;

		}

	    }

	} else {

	    while (n--)

		*patcode++ = *add++;

	}

    } else

	*patcode++ = ch;

    patcode = patout + patsize;

}

static long rn_offs;

/* operates on pointers to union upat, returns a pointer */

#define PATNEXT(p) ((rn_offs = P_NEXT(p)) ? \

		    (P_OP(p) == P_BACK) ? \

		    ((p)-rn_offs) : ((p)+rn_offs) : NULL)

/* Called before parsing a set of file matchs to initialize flags */

/**/

void

patcompstart(void)

{

    if (isset(CASEGLOB))

	patglobflags = 0;

    else

	patglobflags = GF_IGNCASE;

}

/*

 * Top level pattern compilation subroutine

 * exp is a null-terminated, metafied string.

 * inflags is an or of some PAT_* flags.

 * endexp, if non-null, is set to a pointer to the end of the

 *   part of exp which was compiled.  This is used when

 *   compiling patterns for directories which must be

 *   matched recursively.

 */

/**/

mod_export Patprog

patcompile(char *exp, int inflags, char **endexp)

{

    int flags = 0;

    long len = 0;

    long startoff;

    Upat pscan;

    Upat ptemp;

    char *lng, *strp = NULL;

    Patprog p;

    startoff = sizeof(struct patprog);

    /* Ensure alignment of start of program string */

    startoff = (startoff + sizeof(union upat) - 1) & ~(sizeof(union upat) - 1);

    /* Allocate reasonable sized chunk if none, reduce size if too big */

    if (patalloc != P_DEF_ALLOC)

	patout = (char *)zrealloc(patout, patalloc = P_DEF_ALLOC);

    patcode = patout + startoff;

    patsize = patcode - patout;

    patstart = patparse = exp;

    /*

     * Note global patnpar numbers parentheses 1..9, while patnpar

     * in struct is actual count of parentheses.

     */

    patnpar = 1;

    patflags = inflags & ~(PAT_PURES|PAT_HAS_EXCLUDP);

    patendseg = endseg;

    patendseglen = isset(EXTENDEDGLOB) ? PATENDSEGLEN_EXT : PATENDSEGLEN_NORM;

    patendstr = endstr;

    patendstrlen = isset(EXTENDEDGLOB) ? PATENDSTRLEN_EXT : PATENDSTRLEN_NORM;

    if (!(patflags & PAT_FILE)) {

	patendseg++;

	patendstr++;

	patendseglen--;

	patendstrlen--;

	remnulargs(patparse);

	patglobflags = 0;

    }

    /*

     * Have to be set now, since they get updated during compilation.

     */

    ((Patprog)patout)->globflags = patglobflags;

    if (!(patflags & PAT_ANY)) {

	/* Look for a really pure string, with no tokens at all. */

	if (!patglobflags

#ifdef __CYGWIN__

	    /*

	     * If the OS treats files case-insensitively and we

	     * are looking at files, we don't need to use pattern

	     * matching to find the file.

	     */

	    || (!(patglobflags & ~GF_IGNCASE) && (patflags & PAT_FILE))

#endif

	    )

	{

	    /*

	     * Waah!  I wish I understood this.

	     * Empty metafied strings have an initial Nularg.

	     * This never corresponds to a real character in

	     * a glob pattern or string, so skip it.

	     */

	    if (*exp == Nularg)

		exp++;

	    for (strp = exp; *strp &&

		     (!(patflags & PAT_FILE) || *strp != '/') && !itok(*strp);

		 strp++)

		;

	}

	if (!strp || (*strp && *strp != '/')) {

	    /* No, do normal compilation. */

	    strp = NULL;

	    if (patcompswitch(0, &flags) == 0)

		return NULL;

	} else {

	    /*

	     * Yes, copy the string, and skip compilation altogether.

	     * Null terminate for the benefit of globbing.

	     * Leave metafied both for globbing and for our own

	     * efficiency.

	     */

	    patparse = strp;

	    len = strp - exp;

	    patadd(exp, 0, len + 1, 0);

	    patout[startoff + len] = '\0';

	    patflags |= PAT_PURES;

	}

    }

    /* end of compilation: safe to use pointers */

    p = (Patprog)patout;

    p->startoff = startoff;

    p->patstartch = '\0';

    p->globend = patglobflags;

    p->flags = patflags;

    p->mustoff = 0;

    p->size = patsize;

    p->patmlen = len;

    p->patnpar = patnpar-1;

    if (!strp) {

	pscan = (Upat)(patout + startoff);

	ptemp=PATNEXT(pscan);	

	if (!(patflags & PAT_ANY) && (P_OP(ptemp) == P_END)) {

	    /* only one top level choice */

	    pscan = P_OPERAND(pscan);

	    if (flags & P_PURESTR) {

		/*

		 * The pattern can be matched with a simple strncmp/strcmp.

		 * Careful in case we've overwritten the node for the next ptr.

		 */

		char *dst = patout + startoff;

		Upat next;

		p->flags |= PAT_PURES;

		for (; pscan; pscan = next) {

		    next = PATNEXT(pscan);

		    if (P_OP(pscan) == P_EXACTLY) {

			char *opnd = P_LS_STR(pscan), *mtest;

			long oplen = P_LS_LEN(pscan), ilen;

			int nmeta = 0;

			/*

			 * Unfortunately we unmetafied the string

			 * and we need to put any metacharacters

			 * back now we know it's a pure string.

			 * This shouldn't happen too often, it's

			 * just that there are some cases such

			 * as . and .. in files where we really

			 * need a pure string even if there are

			 * pattern characters flying around.

			 */

			for (mtest = opnd, ilen = oplen; ilen;

			     mtest++, ilen--)

			    if (imeta(*mtest))

				nmeta++;

			if (nmeta) {

			    char *oldpatout = patout;

			    patadd(NULL, 0, nmeta, 0);

			    /*

			     * Yuk.

			     */