diff -r 000000000000 -r 2e3d3ce01487 openenvutils/commandshell/shell/src/pattern.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/openenvutils/commandshell/shell/src/pattern.c Tue Feb 02 10:12:00 2010 +0200 @@ -0,0 +1,3049 @@ +// +// © Portions Copyright (c) Symbian Software Ltd 2007. All rights reserved. +// +/* + * 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 + * ( :apat-> :excpat-> ) 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. + */ + p = (Patprog)patout; + opnd = patout + (opnd - oldpatout); + dst = patout + startoff; + } + + while (oplen--) { + if (imeta(*opnd)) { + *dst++ = Meta; + *dst++ = *opnd ^ 32; + } else { + *dst++ = *opnd++; + } + } + } + } + p->size = dst - patout; + /* patmlen is really strlen. We don't need a null. */ + p->patmlen = p->size - startoff; + } else { + /* starting point info */ + if (P_OP(pscan) == P_EXACTLY && !p->globflags && + P_LS_LEN(pscan)) + p->patstartch = *P_LS_STR(pscan); + /* + * Find the longest literal string in something expensive. + * This is itself not all that cheap if we have + * case-insensitive matching or approximation, so don't. + */ + if ((flags & P_HSTART) && !p->globflags) { + lng = NULL; + len = 0; + for (; pscan; pscan = PATNEXT(pscan)) + if (P_OP(pscan) == P_EXACTLY && + P_LS_LEN(pscan) >= len) { + lng = P_LS_STR(pscan); + len = P_LS_LEN(pscan); + } + if (lng) { + p->mustoff = lng - patout; + p->patmlen = len; + } + } + } + } + } + + /* + * The pattern was compiled in a fixed buffer: unless told otherwise, + * we stick the compiled pattern on the heap. This is necessary + * for files where we will often be compiling multiple segments at once. + * But if we get the ZDUP flag we always put it in zalloc()ed memory. + */ + if (patflags & PAT_ZDUP) { + Patprog newp = (Patprog)zalloc(patsize); + memcpy((char *)newp, (char *)p, patsize); + p = newp; + } else if (!(patflags & PAT_STATIC)) { + Patprog newp = (Patprog)zhalloc(patsize); + memcpy((char *)newp, (char *)p, patsize); + p = newp; + } + + if (endexp) + *endexp = patparse; + return p; +} + +/* + * Main body or parenthesized subexpression in pattern + * Parenthesis (and any ksh_glob gubbins) will have been removed. + */ + +/**/ +static long +patcompswitch(int paren, int *flagp) +{ + long starter, br, ender, excsync = 0; + int parno = 0; + int flags, gfchanged = 0, savglobflags = patglobflags; + Upat ptr; + + *flagp = 0; + + if (paren && (patglobflags & GF_BACKREF) && patnpar <= NSUBEXP) { + /* + * parenthesized: make an open node. + * We can only refer to the first nine parentheses. + * For any others, we just use P_OPEN on its own; there's + * no gain in arbitrarily limiting the number of parentheses. + */ + parno = patnpar++; + starter = patnode(P_OPEN + parno); + } else + starter = 0; + + br = patnode(P_BRANCH); + if (!patcompbranch(&flags)) + return 0; + if (patglobflags != savglobflags) + gfchanged++; + if (starter) + pattail(starter, br); + else + starter = br; + + *flagp |= flags & (P_HSTART|P_PURESTR); + + while (*patparse == Bar || + (isset(EXTENDEDGLOB) && *patparse == Tilde && + (patparse[1] == '/' || + !memchr(patendseg, patparse[1], patendseglen)))) { + int tilde = *patparse++ == Tilde; + long gfnode = 0, newbr; + + *flagp &= ~P_PURESTR; + + if (tilde) { + union upat up; + /* excsync remembers the P_EXCSYNC node before a chain of + * exclusions: all point back to this. only the + * original (non-excluded) branch gets a trailing P_EXCSYNC. + */ + if (!excsync) { + excsync = patnode(P_EXCSYNC); + patoptail(br, excsync); + } + /* + * By default, approximations are turned off in exclusions: + * we need to do this here as otherwise the code compiling + * the exclusion doesn't know if the flags have really + * changed if the error count gets restored. + */ + patglobflags &= ~0xff; + if (!(patflags & PAT_FILET) || paren) { + br = patnode(P_EXCLUDE); + } else { + /* + * At top level (paren == 0) in a file glob !(patflags + * &PAT_FILET) do the exclusion prepending the file path + * so far. We need to flag this to avoid unnecessarily + * copying the path. + */ + br = patnode(P_EXCLUDP); + patflags |= PAT_HAS_EXCLUDP; + } + up.p = NULL; + patadd((char *)&up, 0, sizeof(up), 0); + /* / is not treated as special if we are at top level */ + if (!paren && *patendseg == '/') { + tilde++; + patendseg++; + patendseglen--; + patendstr++; + patendstrlen--; + } + } else { + excsync = 0; + br = patnode(P_BRANCH); + /* + * The position of the following statements means globflags + * set in the main branch carry over to the exclusion. + */ + if (!paren) { + patglobflags = 0; + if (((Patprog)patout)->globflags) { + /* + * If at top level, we need to reinitialize flags to zero, + * since (#i)foo|bar only applies to foo and we stuck + * the #i into the global flags. + * We could have done it so that they only got set in the + * first branch, but it's quite convenient having any + * global flags set in the header and not buried in the + * pattern. (Or maybe it isn't and we should + * forget this bit and always stick in an explicit GFLAGS + * statement instead of using the header.) + * Also, this can't happen for file globs where there are + * no top-level |'s. + * + * No gfchanged, as nothing to follow branch at top + * level. + */ + union upat up; + gfnode = patnode(P_GFLAGS); + up.l = patglobflags; + patadd((char *)&up, 0, sizeof(union upat), 0); + } + } else { + patglobflags = savglobflags; + } + } + newbr = patcompbranch(&flags); + if (tilde == 2) { + /* restore special treatment of / */ + patendseg--; + patendseglen++; + patendstr--; + patendstrlen++; + } + if (!newbr) + return 0; + if (gfnode) + pattail(gfnode, newbr); + if (!tilde && patglobflags != savglobflags) + gfchanged++; + pattail(starter, br); + if (excsync) + patoptail(br, patnode(P_EXCEND)); + *flagp |= flags & P_HSTART; + } + + /* + * Make a closing node, hooking it to the end. + * Note that we can't optimize P_NOTHING out here, since another + * branch at that point would indicate the current choices continue, + * which they don't. + */ + ender = patnode(paren ? parno ? P_CLOSE+parno : P_NOTHING : P_END); + pattail(starter, ender); + + /* + * Hook the tails of the branches to the closing node, + * except for exclusions which terminate where they are. + */ + for (ptr = (Upat)patout + starter; ptr; ptr = PATNEXT(ptr)) + if (!P_ISEXCLUDE(ptr)) + patoptail(ptr-(Upat)patout, ender); + + /* check for proper termination */ + if ((paren && *patparse++ != Outpar) || + (!paren && *patparse && + !((patflags & PAT_FILE) && *patparse == '/'))) + return 0; + + if (paren && gfchanged) { + /* + * Restore old values of flags when leaving parentheses. + * gfchanged detects a change in any branch (except exclusions + * which are separate), since we need to emit this even if + * a later branch happened to put the flags back. + */ + pattail(ender, patnode(P_GFLAGS)); + patglobflags = savglobflags; + patadd((char *)&savglobflags, 0, sizeof(long), 0); + } + + return starter; +} + +/* + * Compile something ended by Bar, Outpar, Tilde, or end of string. + * Note the BRANCH or EXCLUDE tag must already have been omitted: + * this returns the position of the operand of that. + */ + +/**/ +static long +patcompbranch(int *flagp) +{ + long chain, latest = 0, starter; + int flags = 0; + + *flagp = P_PURESTR; + + starter = chain = 0; + while (!memchr(patendseg, *patparse, patendseglen) || + (*patparse == Tilde && patparse[1] != '/' && + memchr(patendseg, patparse[1], patendseglen))) { + if (isset(EXTENDEDGLOB) && + ((!isset(SHGLOB) && + (*patparse == Inpar && patparse[1] == Pound)) || + (isset(KSHGLOB) && *patparse == '@' && patparse[1] == Inpar && + patparse[2] == Pound))) { + /* Globbing flags. */ + char *pp1 = patparse; + int oldglobflags = patglobflags, ignore; + long assert; + patparse += (*patparse == '@') ? 3 : 2; + if (!patgetglobflags(&patparse, &assert, &ignore)) + return 0; + if (!ignore) { + if (assert) { + /* + * Start/end assertion looking like flags, but + * actually handled as a normal node + */ + latest = patnode(assert); + flags = 0; + } else { + if (pp1 == patstart) { + /* Right at start of pattern, the simplest case. + * Put them into the flags and don't emit anything. + */ + ((Patprog)patout)->globflags = patglobflags; + continue; + } else if (!*patparse) { + /* Right at the end, so just leave the flags for + * the next Patprog in the chain to pick up. + */ + break; + } + /* + * Otherwise, we have to stick them in as a pattern + * matching nothing. + */ + if (oldglobflags != patglobflags) { + /* Flags changed */ + union upat up; + latest = patnode(P_GFLAGS); + up.l = patglobflags; + patadd((char *)&up, 0, sizeof(union upat), 0); + } else { + /* No effect. */ + continue; + } + } + } else if (!*patparse) + break; + else + continue; + } else if (isset(EXTENDEDGLOB) && *patparse == Hat) { + /* + * ^pat: anything but pat. For proper backtracking, + * etc., we turn this into (*~pat), except without the + * parentheses. + */ + patparse++; + latest = patcompnot(0, &flags); + } else + latest = patcomppiece(&flags); + if (!latest) + return 0; + if (!starter) + starter = latest; + if (!(flags & P_PURESTR)) + *flagp &= ~P_PURESTR; + if (!chain) + *flagp |= flags & P_HSTART; + else + pattail(chain, latest); + chain = latest; + } + /* check if there was nothing in the loop, i.e. () */ + if (!chain) + starter = patnode(P_NOTHING); + + return starter; +} + +/* get glob flags, return 1 for success, 0 for failure */ + +/**/ +int +patgetglobflags(char **strp, long *assertp, int *ignore) +{ + char *nptr, *ptr = *strp; + zlong ret; + + *assertp = 0; + *ignore = 1; + /* (#X): assumes we are still positioned on the first X */ + for (; *ptr && *ptr != Outpar; ptr++) { + if (*ptr == 'q') { + /* Glob qualifiers, ignored in pattern code */ + while (*ptr && *ptr != Outpar) + ptr++; + break; + } else { + *ignore = 0; + switch (*ptr) { + case 'a': + /* Approximate matching, max no. of errors follows */ + ret = zstrtol(++ptr, &nptr, 10); + /* + * We can't have more than 254, because we need 255 to + * mark 254 errors in wbranch and exclude sync strings + * (hypothetically --- hope no-one tries it). + */ + if (ret < 0 || ret > 254 || ptr == nptr) + return 0; + patglobflags = (patglobflags & ~0xff) | (ret & 0xff); + ptr = nptr-1; + break; + + case 'l': + /* Lowercase in pattern matches lower or upper in target */ + patglobflags = (patglobflags & ~GF_IGNCASE) | GF_LCMATCHUC; + break; + + case 'i': + /* Fully case insensitive */ + patglobflags = (patglobflags & ~GF_LCMATCHUC) | GF_IGNCASE; + break; + + case 'I': + /* Restore case sensitivity */ + patglobflags &= ~(GF_LCMATCHUC|GF_IGNCASE); + break; + + case 'b': + /* Make backreferences */ + patglobflags |= GF_BACKREF; + break; + + case 'B': + /* Don't make backreferences */ + patglobflags &= ~GF_BACKREF; + break; + + case 'm': + /* Make references to complete match */ + patglobflags |= GF_MATCHREF; + break; + + case 'M': + /* Don't */ + patglobflags &= ~GF_MATCHREF; + break; + + case 's': + *assertp = P_ISSTART; + break; + + case 'e': + *assertp = P_ISEND; + break; + + default: + return 0; + } + } + } + if (*ptr != Outpar) + return 0; + /* Start/end assertions must appear on their own. */ + if (*assertp && (*strp)[1] != Outpar) + return 0; + *strp = ptr + 1; + return 1; +} + +/* + * compile a chunk such as a literal string or a [...] followed + * by a possible hash operator + */ + +/**/ +static long +patcomppiece(int *flagp) +{ + long starter = 0, next, pound, op; + int flags, flags2, kshchar, len, ch, patch, nmeta; + union upat up; + char *nptr, *str0, *ptr, cbuf[2]; + zrange_t from, to; + + flags = 0; + str0 = patparse; + for (;;) { + /* + * Check if we have a string. First, we need to make sure + * the string doesn't introduce a ksh-like parenthesized expression. + */ + kshchar = '\0'; + if (isset(KSHGLOB) && *patparse && patparse[1] == Inpar) { + if (strchr("?*+!@", *patparse)) + kshchar = STOUC(*patparse); + else if (*patparse == Star || *patparse == Quest) + kshchar = STOUC(ztokens[*patparse - Pound]); + } + + /* + * End of string (or no string at all) if ksh-type parentheses, + * or special character, unless that character is a tilde and + * the character following is an end-of-segment character. Thus + * tildes are not special if there is nothing following to + * be excluded. + */ + if (kshchar || (memchr(patendstr, *patparse, patendstrlen) && + (*patparse != Tilde || + patparse[1] == '/' || + !memchr(patendseg, patparse[1], patendseglen)))) + break; + + METAINC(patparse); + } + + if (patparse > str0) { + long slen = patparse - str0; + int morelen; + + /* Ordinary string: cancel kshchar lookahead */ + kshchar = '\0'; + /* + * Assume it matches a simple string until we find otherwise. + */ + flags |= P_PURESTR; + DPUTS(patparse == str0, "BUG: matched nothing in patcomppiece."); + /* more than one character matched? */ + morelen = str0 + (*str0 == Meta ? 2 : 1) < patparse; + /* + * If we have more than one character, a following hash only + * applies to the last, so decrement. + */ + if (isset(EXTENDEDGLOB) && *patparse == Pound && morelen) + patparse -= (patparse > str0 + 1 && patparse[-2] == Meta) ? 2 : 1; + /* + * If len is 1, we can't have an active # following, so doesn't + * matter that we don't make X in `XX#' simple. + */ + if (!morelen) + flags |= P_SIMPLE; + starter = patnode(P_EXACTLY); + + /* Get length of string without metafication. */ + nmeta = 0; + /* inherited from domatch, but why, exactly? */ + if (*str0 == Nularg) + str0++; + for (ptr = str0; ptr < patparse; ptr++) { + if (*ptr == Meta) { + nmeta++; + ptr++; + } + } + slen = (patparse - str0) - nmeta; + /* First add length, which is a long */ + patadd((char *)&slen, 0, sizeof(long), 0); + /* + * Then the string, not null terminated. + * Unmetafy and untokenize; pass the final length, + * which is what we need to allocate, i.e. not including + * a count for each Meta in the string. + */ + patadd(str0, 0, slen, PA_UNMETA); + nptr = P_LS_STR((Upat)patout + starter); + /* + * It's much simpler to turn off pure string mode for + * any case-insensitive or approximate matching; usually, + * that is correct, or they wouldn't have been turned on. + * However, we need to make sure we match a "." or ".." + * in a file name as a pure string. There's a minor bug + * that this will also apply to something like + * ..(#a1).. (i.e. the (#a1) has no effect), but if you're + * going to write funny patterns, you get no sympathy from me. + */ + if (patglobflags) { + if (!(patflags & PAT_FILE)) + flags &= ~P_PURESTR; + else if (!(nptr[0] == '.' && + (slen == 1 || (nptr[1] == '.' && slen == 2)))) + flags &= ~P_PURESTR; + } + } else { + if (kshchar) + patparse++; + + patch = *patparse; + METAINC(patparse); + switch(patch) { + case Quest: + flags |= P_SIMPLE; + starter = patnode(P_ANY); + break; + case Star: + /* kshchar is used as a sign that we can't have #'s. */ + kshchar = -1; + starter = patnode(P_STAR); + break; + case Inbrack: + flags |= P_SIMPLE; + if (*patparse == Hat || *patparse == '^' || *patparse == '!') { + patparse++; + starter = patnode(P_ANYBUT); + } else + starter = patnode(P_ANYOF); + if (*patparse == Outbrack) { + patparse++; + patadd(NULL, ']', 1, PA_NOALIGN); + } + while (*patparse && *patparse != Outbrack) { + /* Meta is not a token */ + if (*patparse == Inbrack && patparse[1] == ':' && + (nptr = strchr(patparse+2, ':')) && + nptr[1] == Outbrack) { + /* Posix range. */ + patparse += 2; + len = nptr - patparse; + if (!strncmp(patparse, "alpha", len)) + ch = PP_ALPHA; + else if (!strncmp(patparse, "alnum", len)) + ch = PP_ALNUM; + else if (!strncmp(patparse, "ascii", len)) + ch = PP_ASCII; + else if (!strncmp(patparse, "blank", len)) + ch = PP_BLANK; + else if (!strncmp(patparse, "cntrl", len)) + ch = PP_CNTRL; + else if (!strncmp(patparse, "digit", len)) + ch = PP_DIGIT; + else if (!strncmp(patparse, "graph", len)) + ch = PP_GRAPH; + else if (!strncmp(patparse, "lower", len)) + ch = PP_LOWER; + else if (!strncmp(patparse, "print", len)) + ch = PP_PRINT; + else if (!strncmp(patparse, "punct", len)) + ch = PP_PUNCT; + else if (!strncmp(patparse, "space", len)) + ch = PP_SPACE; + else if (!strncmp(patparse, "upper", len)) + ch = PP_UPPER; + else if (!strncmp(patparse, "xdigit", len)) + ch = PP_XDIGIT; + else + ch = PP_UNKWN; + patparse = nptr + 2; + if (ch != PP_UNKWN) + patadd(NULL, STOUC(Meta+ch), 1, PA_NOALIGN); + continue; + } + if (itok(*patparse)) { + cbuf[0] = ztokens[*patparse - Pound]; + } else if (*patparse == Meta) { + cbuf[0] = Meta; + cbuf[1] = *++patparse; + } else + cbuf[0] = *patparse; + patparse++; + + if (*patparse == '-' && patparse[1] != Outbrack) { + patadd(NULL, STOUC(Meta+PP_RANGE), 1, PA_NOALIGN); + patadd(cbuf, 0, (cbuf[0] == Meta) ? 2 : 1, PA_NOALIGN); + if (itok(*++patparse)) { + patadd(0, STOUC(ztokens[*patparse - Pound]), 1, + PA_NOALIGN); + } else + patadd(patparse, 0, (*patparse == Meta) ? 2 : 1, + PA_NOALIGN); + METAINC(patparse); + } else + patadd(cbuf, 0, (cbuf[0] == Meta) ? 2 : 1, PA_NOALIGN); + } + if (*patparse != Outbrack) + return 0; + patparse++; + /* terminate null string and fix alignment */ + patadd(NULL, 0, 1, 0); + break; + case Inpar: + /* is this how to treat parentheses in SHGLOB? */ + if (isset(SHGLOB) && !kshchar) + return 0; + if (kshchar == '!') { + /* This is nasty, we should really either handle all + * kshglobbing below or here. But most of the + * others look like non-ksh patterns, while this one + * doesn't, so we handle it here and leave the rest. + * We treat it like an extendedglob ^, except that + * it goes into parentheses. + * + * If we did do kshglob here, we could support + * the old behaviour that things like !(foo)## + * work, but it makes the code more complicated at + * the expense of allowing the user to do things + * they shouldn't. + */ + if (!(starter = patcompnot(1, &flags2))) + return 0; + } else if (!(starter = patcompswitch(1, &flags2))) + return 0; + flags |= flags2 & P_HSTART; + break; + case Inang: + /* Numeric glob */ + len = 0; /* beginning present 1, end present 2 */ + if (idigit(*patparse)) { + from = (zrange_t) zstrtol((char *)patparse, + (char **)&nptr, 10); + patparse = nptr; + len |= 1; + } + DPUTS(*patparse != '-', "BUG: - missing from numeric glob"); + patparse++; + if (idigit(*patparse)) { + to = (zrange_t) zstrtol((char *)patparse, + (char **)&nptr, 10); + patparse = nptr; + len |= 2; + } + if (*patparse != Outang) + return 0; + patparse++; + switch(len) { + case 3: + starter = patnode(P_NUMRNG); + patadd((char *)&from, 0, sizeof(from), 0); + patadd((char *)&to, 0, sizeof(to), 0); + break; + case 2: + starter = patnode(P_NUMTO); + patadd((char *)&to, 0, sizeof(to), 0); + break; + case 1: + starter = patnode(P_NUMFROM); + patadd((char *)&from, 0, sizeof(from), 0); + break; + case 0: + starter = patnode(P_NUMANY); + break; + } + /* This can't be simple, because it isn't. + * Mention in manual that matching digits with [...] + * is more efficient. + */ + break; + case Pound: + DPUTS(!isset(EXTENDEDGLOB), "BUG: # not treated as string"); + /* + * A hash here is an error; it should follow something + * repeatable. + */ + return 0; + break; +#ifdef DEBUG + default: + dputs("BUG: character not handled in patcomppiece"); + return 0; + break; +#endif + } + } + + if (!(pound = (*patparse == Pound && isset(EXTENDEDGLOB))) && + (kshchar <= 0 || kshchar == '@' || kshchar == '!')) { + *flagp = flags; + return starter; + } + + /* too much at once doesn't currently work */ + if (kshchar && pound) + return 0; + + if (kshchar == '*') { + op = P_ONEHASH; + *flagp = P_HSTART; + } else if (kshchar == '+') { + op = P_TWOHASH; + *flagp = P_HSTART; + } else if (kshchar == '?') { + op = 0; + *flagp = 0; + } else if (*++patparse == Pound) { + op = P_TWOHASH; + patparse++; + *flagp = P_HSTART; + } else { + op = P_ONEHASH; + *flagp = P_HSTART; + } + + /* + * Note optimizations with pointers into P_NOTHING branches: some + * should logically point to next node after current piece. + * + * Backtracking is also encoded in a slightly obscure way: the + * code emitted ensures we test the non-empty branch of complex + * patterns before the empty branch on each repetition. Hence + * each time we fail on a non-empty branch, we try the empty branch, + * which is equivalent to backtracking. + */ + if ((flags & P_SIMPLE) && (op == P_ONEHASH || op == P_TWOHASH) && + P_OP((Upat)patout+starter) == P_ANY) { + /* Optimize ?# to *. Silly thing to do, since who would use + * use ?# ? But it makes the later code shorter. + */ + Upat uptr = (Upat)patout + starter; + if (op == P_TWOHASH) { + /* ?## becomes ?* */ + uptr->l = (uptr->l & ~0xff) | P_ANY; + pattail(starter, patnode(P_STAR)); + } else { + uptr->l = (uptr->l & ~0xff) | P_STAR; + } + } else if ((flags & P_SIMPLE) && op && !(patglobflags & 0xff)) { + /* Don't simplify if we need to look for approximations. */ + patinsert(op, starter, NULL, 0); + } else if (op == P_ONEHASH) { + /* Emit x# as (x&|), where & means "self". */ + up.p = NULL; + patinsert(P_WBRANCH, starter, (char *)&up, sizeof(up)); + /* Either x */ + patoptail(starter, patnode(P_BACK)); /* and loop */ + patoptail(starter, starter); /* back */ + pattail(starter, patnode(P_BRANCH)); /* or */ + pattail(starter, patnode(P_NOTHING)); /* null. */ + } else if (op == P_TWOHASH) { + /* Emit x## as x(&|) where & means "self". */ + next = patnode(P_WBRANCH); /* Either */ + up.p = NULL; + patadd((char *)&up, 0, sizeof(up), 0); + pattail(starter, next); + pattail(patnode(P_BACK), starter); /* loop back */ + pattail(next, patnode(P_BRANCH)); /* or */ + pattail(starter, patnode(P_NOTHING)); /* null. */ + } else if (kshchar == '?') { + /* Emit ?(x) as (x|) */ + patinsert(P_BRANCH, starter, NULL, 0); /* Either x */ + pattail(starter, patnode(P_BRANCH)); /* or */ + next = patnode(P_NOTHING); /* null */ + pattail(starter, next); + patoptail(starter, next); + } + if (*patparse == Pound) + return 0; + + return starter; +} + +/* + * Turn a ^foo (paren = 0) or !(foo) (paren = 1) into *~foo with + * parentheses if necessary. As you see, that's really quite easy. + */ + +/**/ +static long +patcompnot(int paren, int *flagsp) +{ + union upat up; + long excsync, br, excl, n, starter; + int dummy; + + /* Here, we're matching a star at the start. */ + *flagsp = P_HSTART; + + starter = patnode(P_BRANCH); + br = patnode(P_STAR); + excsync = patnode(P_EXCSYNC); + pattail(br, excsync); + pattail(starter, excl = patnode(P_EXCLUDE)); + up.p = NULL; + patadd((char *)&up, 0, sizeof(up), 0); + if (!(br = (paren ? patcompswitch(1, &dummy) : patcompbranch(&dummy)))) + return 0; + pattail(br, patnode(P_EXCEND)); + n = patnode(P_NOTHING); /* just so much easier */ + pattail(excsync, n); + pattail(excl, n); + + return starter; +} + +/* Emit a node */ + +/**/ +static long +patnode(long op) +{ + long starter = (Upat)patcode - (Upat)patout; + union upat up; + + up.l = op; + patadd((char *)&up, 0, sizeof(union upat), 0); + return starter; +} + +/* + * insert an operator in front of an already emitted operand: + * we relocate the operand. there had better be nothing else after. + */ + +/**/ +static void +patinsert(long op, int opnd, char *xtra, int sz) +{ + char *src, *dst, *opdst; + union upat buf, *lptr; + + buf.l = 0; + patadd((char *)&buf, 0, sizeof(buf), 0); + if (sz) + patadd(xtra, 0, sz, 0); + src = patcode - sizeof(union upat) - sz; + dst = patcode; + opdst = patout + opnd * sizeof(union upat); + while (src > opdst) + *--dst = *--src; + + /* A cast can't be an lvalue */ + lptr = (Upat)opdst; + lptr->l = op; + opdst += sizeof(union upat); + while (sz--) + *opdst++ = *xtra++; +} + +/* set the 'next' pointer at the end of a node chain */ + +/**/ +static void +pattail(long p, long val) +{ + Upat scan, temp; + long offset; + + scan = (Upat)patout + p; + for (;;) { + if (!(temp = PATNEXT(scan))) + break; + scan = temp; + } + + offset = (P_OP(scan) == P_BACK) + ? (scan - (Upat)patout) - val : val - (scan - (Upat)patout); + + scan->l |= offset << 8; +} + +/* do pattail, but on operand of first argument; nop if operandless */ + +/**/ +static void patoptail(long p, long val) +{ + Upat ptr = (Upat)patout + p; + int op = P_OP(ptr); + if (!p || !P_ISBRANCH(ptr)) + return; + if (op == P_BRANCH) + pattail(P_OPERAND(p), val); + else + pattail(P_OPERAND(p) + 1, val); +} + + +/* + * Run a pattern. + */ +static char *patinstart; /* Start of input string */ +static char *patinend; /* End of input string */ +static char *patinput; /* String input pointer */ +static char *patinpath; /* Full path for use with ~ exclusions */ +static int patinlen; /* Length of last successful match. + * Includes count of Meta characters. + */ + +static char *patbeginp[NSUBEXP]; /* Pointer to backref beginnings */ +static char *patendp[NSUBEXP]; /* Pointer to backref ends */ +static int parsfound; /* parentheses (with backrefs) found */ + +static int globdots; /* Glob initial dots? */ + +/* + * Macros which are currently trivial but are likely to be less + * so when we handle multibyte characters. They operate on + * umetafied strings. + */ + +/* Get a character from the start point in a string */ +#define CHARREF(x) (STOUC(*x)) +/* Get a pointer to the next character */ +#define CHARNEXT(x) (x+1) +/* Increment a pointer past the current character. */ +#define CHARINC(x) (x++) +/* Counter the number of characters between two pointers, largest first */ +#define CHARSUB(x,y) (x-y) + +/* + * The following need to be accessed in the globbing scanner for + * a multi-component file path. See horror story in glob.c. + */ +/**/ +int errsfound; /* Total error count so far */ + +/**/ +int forceerrs; /* Forced maximum error count */ + +/**/ +void +pattrystart(void) +{ + forceerrs = -1; + errsfound = 0; +} + +/* + * Test prog against null-terminated, metafied string. + */ + +/**/ +mod_export int +pattry(Patprog prog, char *string) +{ + return pattryrefs(prog, string, -1, -1, 0, NULL, NULL, NULL); +} + +/* + * Test prog against string of given length, no null termination + * but still metafied at this point. offset gives an offset + * to include in reported match indices + */ + +/**/ +mod_export int +pattrylen(Patprog prog, char *string, int len, int unmetalen, int offset) +{ + return pattryrefs(prog, string, len, unmetalen, offset, NULL, NULL, NULL); +} + +/* + * Test prog against string with given lengths. The input + * string is metafied; stringlen is the raw string length, and + * unmetalen the number of characters in the original string (some + * of which may now be metafied). Either value may be -1 + * to indicate a null-terminated string which will be counted. Note + * there may be a severe penalty for this if a lot of matching is done + * on one string. + * + * offset is the position in the original string (not seen by + * the pattern module) at which we are trying to match. + * This is added in to the positions recorded in patbeginp and patendp + * when we are looking for substrings. Currently this only happens + * in the parameter substitution code. + * + * Note this is a character offset, i.e. a metafied character + * counts as 1. + * + * The last three arguments are used to report the positions for the + * backreferences. On entry, *nump should contain the maximum number + * of positions to report. In this case the match, mbegin, mend + * arrays are not altered. + */ + +/**/ +mod_export int +pattryrefs(Patprog prog, char *string, int stringlen, int unmetalen, + int patoffset, + int *nump, int *begp, int *endp) +{ + int i, maxnpos = 0, ret, needfullpath, unmetalenp; + int origlen; + char **sp, **ep, *tryalloced, *ptr; + char *progstr = (char *)prog + prog->startoff; + + if (nump) { + maxnpos = *nump; + *nump = 0; + } + /* inherited from domatch, but why, exactly? */ + if (*string == Nularg) { + string++; + unmetalen--; + } + + if (stringlen < 0) + stringlen = strlen(string); + origlen = stringlen; + + patflags = prog->flags; + /* + * For a top-level ~-exclusion, we will need the full + * path to exclude, so copy the path so far and append the + * current test string. + */ + needfullpath = (patflags & PAT_HAS_EXCLUDP) && pathpos; + + /* Get the length of the full string when unmetafied. */ + if (unmetalen < 0) + unmetalen = ztrsub(string + stringlen, string); + if (needfullpath) + unmetalenp = ztrsub(pathbuf + pathpos, pathbuf); + else + unmetalenp = 0; + + DPUTS(needfullpath && (patflags & (PAT_PURES|PAT_ANY)), + "rum sort of file exclusion"); + /* + * Partly for efficiency, and partly for the convenience of + * globbing, we don't unmetafy pure string patterns, and + * there's no reason to if the pattern is just a *. + */ + if (!(patflags & (PAT_PURES|PAT_ANY)) + && (needfullpath || unmetalen != stringlen)) { + /* + * We need to copy if we need to prepend the path so far + * (in which case we copy both chunks), or if we have + * Meta characters. + */ + char *dst; + int icopy, ncopy; + + dst = tryalloced = zalloc(unmetalen + unmetalenp); + + if (needfullpath) { + /* loop twice, copy path buffer first time */ + ptr = pathbuf; + ncopy = unmetalenp; + } else { + /* just loop once, copy string with unmetafication */ + ptr = string; + ncopy = unmetalen; + } + for (icopy = 0; icopy < 2; icopy++) { + for (i = 0; i < ncopy; i++) { + if (*ptr == Meta) { + ptr++; + *dst++ = *ptr++ ^ 32; + } else { + *dst++ = *ptr++; + } + } + if (!needfullpath) + break; + /* next time append test string to path so far */ + ptr = string; + ncopy = unmetalen; + } + + if (needfullpath) { + patinstart = tryalloced + unmetalenp; + patinpath = tryalloced; + } else { + patinstart = tryalloced; + patinpath = NULL; + } + stringlen = unmetalen; + } else { + patinstart = string; + tryalloced = patinpath = NULL; + } + + patinend = patinstart + stringlen; + /* + * From now on we do not require NULL termination of + * the test string. There should also be no more references + * to the variable string. + */ + + if (prog->flags & (PAT_PURES|PAT_ANY)) { + /* + * Either we are testing against a pure string, + * or we can match anything at all. + */ + int ret; + if (prog->flags & PAT_ANY) { + /* + * Optimisation for a single "*": always matches + * (except for no_glob_dots, see below). + */ + ret = 1; + } else { + /* + * Testing a pure string. See if initial + * components match. + */ + int lendiff = stringlen - prog->patmlen; + if (lendiff < 0) { + /* No, the pattern string is too long. */ + ret = 0; + } else if (!memcmp(progstr, patinstart, prog->patmlen)) { + /* + * Initial component matches. Matches either + * if lengths are the same or we are not anchored + * to the end of the string. + */ + ret = !lendiff || (prog->flags & PAT_NOANCH); + } else { + /* No match. */ + ret = 0; + } + } + if (ret) { + /* + * For files, we won't match initial "."s unless + * glob_dots is set. + */ + if ((prog->flags & PAT_NOGLD) && *patinstart == '.') { + ret = 0; + } else { + /* + * Remember the length in case used for ${..#..} etc. + * In this case, we didn't unmetafy the string. + */ + patinlen = (int)prog->patmlen; + /* if matching files, must update globbing flags */ + patglobflags = prog->globend; + } + } + + if (tryalloced) + zfree(tryalloced, unmetalen + unmetalenp); + + return ret; + } else { + /* + * Test for a `must match' string, unless we're scanning for a match + * in which case we don't need to do this each time. + */ + ret = 1; + if (!(prog->flags & PAT_SCAN) && prog->mustoff) + { + char *testptr; /* start pointer into test string */ + char *teststop; /* last point from which we can match */ + char *patptr = (char *)prog + prog->mustoff; + int patlen = prog->patmlen; + int found = 0; + + if (patlen > stringlen) { + /* Too long, can't match. */ + ret = 0; + } else { + teststop = patinend - patlen; + + for (testptr = patinstart; testptr <= teststop; testptr++) + { + if (!memcmp(testptr, patptr, patlen)) { + found = 1; + break; + } + } + + if (!found) + ret = 0; + } + } + if (!ret) { + if (tryalloced) + zfree(tryalloced, unmetalen + unmetalenp); + return 0; + } + + patglobflags = prog->globflags; + if (!(patflags & PAT_FILE)) { + forceerrs = -1; + errsfound = 0; + } + globdots = !(patflags & PAT_NOGLD); + parsfound = 0; + + patinput = patinstart; + + if (patmatch((Upat)progstr)) { + /* + * we were lazy and didn't save the globflags if an exclusion + * failed, so set it now + */ + patglobflags = prog->globend; + + /* + * Record length of successful match, including Meta + * characters. Do it here so that patmatchlen() can return + * it even if we delete the pattern strings. + */ + patinlen = patinput - patinstart; + /* + * Optimization: if we didn't find any Meta characters + * to begin with, we don't need to look for them now. + */ + if (unmetalen != origlen) { + for (ptr = patinstart; ptr < patinput; ptr++) + if (imeta(*ptr)) + patinlen++; + } + + /* + * Should we clear backreferences and matches on a failed + * match? + */ + if ((patglobflags & GF_MATCHREF) && !(patflags & PAT_FILE)) { + /* + * m flag: for global match. This carries no overhead + * in the pattern matching part. + * + * Remember the test pattern is already unmetafied. + */ + char *str; + int mlen = CHARSUB(patinput, patinstart); + + str = metafy(patinstart, patinput - patinstart, META_DUP); + setsparam("MATCH", str); + setiparam("MBEGIN", (zlong)(patoffset + !isset(KSHARRAYS))); + setiparam("MEND", + (zlong)(mlen + patoffset + + !isset(KSHARRAYS) - 1)); + } + if (prog->patnpar && nump) { + /* + * b flag: for backreferences using parentheses. Reported + * directly. + */ + *nump = prog->patnpar; + + sp = patbeginp; + ep = patendp; + + for (i = 0; i < prog->patnpar && i < maxnpos; i++) { + if (parsfound & (1 << i)) { + if (begp) + *begp++ = CHARSUB(*sp, patinstart) + patoffset; + if (endp) + *endp++ = CHARSUB(*ep, patinstart) + patoffset + - 1; + } else { + if (begp) + *begp++ = -1; + if (endp) + *endp++ = -1; + } + + sp++; + ep++; + } + } else if (prog->patnpar && !(patflags & PAT_FILE)) { + /* + * b flag: for backreferences using parentheses. + */ + int palen = prog->patnpar+1; + char **matcharr, **mbeginarr, **mendarr; + char numbuf[DIGBUFSIZE]; + + matcharr = zshcalloc(palen*sizeof(char *)); + mbeginarr = zshcalloc(palen*sizeof(char *)); + mendarr = zshcalloc(palen*sizeof(char *)); + + sp = patbeginp; + ep = patendp; + + for (i = 0; i < prog->patnpar; i++) { + if (parsfound & (1 << i)) { + matcharr[i] = metafy(*sp, *ep - *sp, META_DUP); + /* + * mbegin and mend give indexes into the string + * in the standard notation, i.e. respecting + * KSHARRAYS, and with the end index giving + * the last character, not one beyond. + * For example, foo=foo; [[ $foo = (f)oo ]] gives + * (without KSHARRAYS) indexes 1 and 1, which + * corresponds to indexing as ${foo[1,1]}. + */ + sprintf(numbuf, "%ld", + (long)(CHARSUB(*sp, patinstart) + + patoffset + + !isset(KSHARRAYS))); + mbeginarr[i] = ztrdup(numbuf); + sprintf(numbuf, "%ld", + (long)(CHARSUB(*ep, patinstart) + + patoffset + + !isset(KSHARRAYS) - 1)); + mendarr[i] = ztrdup(numbuf); + } else { + /* Pattern wasn't set: either it was in an + * unmatched branch, or a hashed parenthesis + * that didn't match at all. + */ + matcharr[i] = ztrdup(""); + mbeginarr[i] = ztrdup("-1"); + mendarr[i] = ztrdup("-1"); + } + sp++; + ep++; + } + setaparam("match", matcharr); + setaparam("mbegin", mbeginarr); + setaparam("mend", mendarr); + } + + ret = 1; + } else + ret = 0; + + if (tryalloced) + zfree(tryalloced, unmetalen + unmetalenp); + + return ret; + } +} + +/* + * Return length of previous succesful match. This is + * in metafied bytes, i.e. includes a count of Meta characters. + * Unusual and futile attempt at modular encapsulation. + */ + +/**/ +int +patmatchlen(void) +{ + return patinlen; +} + +/* + * Match literal characters with case insensitivity test: the first + * comes from the input string, the second the current pattern. + */ +#define CHARMATCH(chin, chpa) (chin == chpa || \ + ((patglobflags & GF_IGNCASE) ? \ + ((isupper(chin) ? tolower(chin) : chin) == \ + (isupper(chpa) ? tolower(chpa) : chpa)) : \ + (patglobflags & GF_LCMATCHUC) ? \ + (islower(chpa) && toupper(chpa) == chin) : 0)) +/* + * The same but caching an expression from the first argument, + * Requires local charmatch_cache definition. + */ +#define CHARMATCH_EXPR(expr, chpa) \ + (charmatch_cache = (expr), CHARMATCH(charmatch_cache, chpa)) + +/* + * exactpos is used to remember how far down an exact string we have + * matched, if we are doing approximation and can therefore redo from + * the same point; we never need to otherwise. + * + * exactend is a pointer to the end of the string, which isn't + * null-terminated. + */ +static char *exactpos, *exactend; + +/* + * Main matching routine. + * + * Testing the tail end of a match is usually done by recursion, but + * we try to eliminate that in favour of looping for simple cases. + */ + +/**/ +static int +patmatch(Upat prog) +{ + /* Current and next nodes */ + Upat scan = prog, next, opnd; + char *start, *save, *chrop, *chrend, *compend; + int savglobflags, op, no, min, nextch, fail = 0, saverrsfound; + zrange_t from, to, comp; + + while (scan) { + next = PATNEXT(scan); + + if (!globdots && P_NOTDOT(scan) && patinput == patinstart && + patinput < patinend && *patinput == '.') + return 0; + + switch (P_OP(scan)) { + case P_ANY: + if (patinput == patinend) + fail = 1; + else + CHARINC(patinput); + break; + case P_EXACTLY: + /* + * acts as nothing if *chrop is null: this is used by + * approx code. + */ + if (exactpos) { + chrop = exactpos; + chrend = exactend; + } else { + chrop = P_LS_STR(scan); + chrend = chrop + P_LS_LEN(scan); + } + exactpos = NULL; + while (chrop < chrend && patinput < patinend) { + int chin = CHARREF(patinput); + int chpa = CHARREF(chrop); + if (!CHARMATCH(chin, chpa)) { + fail = 1; + break; + } + CHARINC(chrop); + CHARINC(patinput); + } + if (chrop < chrend) { + exactpos = chrop; + exactend = chrend; + fail = 1; + } + break; + case P_ANYOF: + if (patinput == patinend || + !patmatchrange((char *)P_OPERAND(scan), + CHARREF(patinput))) + fail = 1; + else + CHARINC(patinput); + break; + case P_ANYBUT: + if (patinput == patinend || + patmatchrange((char *)P_OPERAND(scan), + CHARREF(patinput))) + fail = 1; + else + CHARINC(patinput); + break; + case P_NUMRNG: + case P_NUMFROM: + case P_NUMTO: + /* + * To do this properly, we really have to treat numbers as + * closures: that's so things like <1-1000>33 will + * match 633 (they didn't up to 3.1.6). To avoid making this + * too inefficient, we see if there's an exact match next: + * if there is, and it's not a digit, we return 1 after + * the first attempt. + */ + op = P_OP(scan); + start = (char *)P_OPERAND(scan); + from = to = 0; + if (op != P_NUMTO) { +#ifdef ZSH_64_BIT_TYPE + /* We can't rely on pointer alignment being good enough. */ + memcpy((char *)&from, start, sizeof(zrange_t)); +#else + from = *((zrange_t *) start); +#endif + start += sizeof(zrange_t); + } + if (op != P_NUMFROM) { +#ifdef ZSH_64_BIT_TYPE + memcpy((char *)&to, start, sizeof(zrange_t)); +#else + to = *((zrange_t *) start); +#endif + } + start = compend = patinput; + comp = 0; + while (patinput < patinend && idigit(*patinput)) { + if (comp) + comp *= 10; + comp += *patinput - '0'; + patinput++; + compend++; + + if (comp & ((zrange_t)1 << (sizeof(comp)*8 - +#ifdef ZRANGE_T_IS_SIGNED + 2 +#else + 1 +#endif + ))) { + /* + * Out of range (allowing for signedness, which + * we need if we are using zlongs). + * This is as far as we can go. + * If we're doing a range "from", skip all the + * remaining numbers. Otherwise, we can't + * match beyond the previous point anyway. + * Leave the pointer to the last calculated + * position (compend) where it was before. + */ + if (op == P_NUMFROM) { + while (patinput < patinend && idigit(*patinput)) + patinput++; + } + } + } + save = patinput; + no = 0; + while (patinput > start) { + /* if already too small, no power on earth can save it */ + if (comp < from && patinput <= compend) + break; + if ((op == P_NUMFROM || comp <= to) && patmatch(next)) { + return 1; + } + if (!no && P_OP(next) == P_EXACTLY && + (!P_LS_LEN(next) || + !idigit(STOUC(*P_LS_STR(next)))) && + !(patglobflags & 0xff)) + return 0; + patinput = --save; + no++; + /* + * With a range start and an unrepresentable test + * number, we just back down the test string without + * changing the number until we get to a representable + * one. + */ + if (patinput < compend) + comp /= 10; + } + patinput = start; + fail = 1; + break; + case P_NUMANY: + /* This is <->: any old set of digits, don't bother comparing */ + start = patinput; + while (patinput < patinend && idigit(CHARREF(patinput))) + patinput++; + save = patinput; + no = 0; + while (patinput > start) { + if (patmatch(next)) + return 1; + if (!no && P_OP(next) == P_EXACTLY && + (!P_LS_LEN(next) || + !idigit(CHARREF(P_LS_STR(next)))) && + !(patglobflags & 0xff)) + return 0; + patinput = --save; + no++; + } + patinput = start; + fail = 1; + break; + case P_NOTHING: + break; + case P_BACK: + break; + case P_GFLAGS: + patglobflags = P_OPERAND(scan)->l; + break; + case P_OPEN: + case P_OPEN+1: + case P_OPEN+2: + case P_OPEN+3: + case P_OPEN+4: + case P_OPEN+5: + case P_OPEN+6: + case P_OPEN+7: + case P_OPEN+8: + case P_OPEN+9: + no = P_OP(scan) - P_OPEN; + save = patinput; + + if (patmatch(next)) { + /* + * Don't set patbeginp if some later invocation of + * the same parentheses already has. + */ + if (no && !(parsfound & (1 << (no - 1)))) { + patbeginp[no-1] = save; + parsfound |= 1 << (no - 1); + } + return 1; + } else + return 0; + break; + case P_CLOSE: + case P_CLOSE+1: + case P_CLOSE+2: + case P_CLOSE+3: + case P_CLOSE+4: + case P_CLOSE+5: + case P_CLOSE+6: + case P_CLOSE+7: + case P_CLOSE+8: + case P_CLOSE+9: + no = P_OP(scan) - P_CLOSE; + save = patinput; + + if (patmatch(next)) { + DPUTS(!patendp, "patendp not set for backreferencing"); + if (no && !(parsfound & (1 << (no + 15)))) { + patendp[no-1] = save; + parsfound |= 1 << (no + 15); + } + return 1; + } else + return 0; + break; + case P_EXCSYNC: + /* See the P_EXCLUDE code below for where syncptr comes from */ + { + unsigned char *syncptr; + Upat after; + after = P_OPERAND(scan); + DPUTS(!P_ISEXCLUDE(after), + "BUG: EXCSYNC not followed by EXCLUDE."); + DPUTS(!P_OPERAND(after)->p, + "BUG: EXCSYNC not handled by EXCLUDE"); + syncptr = P_OPERAND(after)->p + (patinput - patinstart); + /* + * If we already matched from here, this time we fail. + * See WBRANCH code for story about error count. + */ + if (*syncptr && errsfound + 1 >= *syncptr) + return 0; + /* + * Else record that we (possibly) matched this time. + * No harm if we don't: then the previous test will just + * short cut the attempted match that is bound to fail. + * We never try to exclude something that has already + * failed anyway. + */ + *syncptr = errsfound + 1; + } + break; + case P_EXCEND: + /* + * This is followed by a P_EXCSYNC, but only in the P_EXCLUDE + * branch. Actually, we don't bother following it: all we + * need to know is that we successfully matched so far up + * to the end of the asserted pattern; the endpoint + * in the target string is nulled out. + */ + if (!(fail = (patinput < patinend))) + return 1; + break; + case P_BRANCH: + case P_WBRANCH: + /* P_EXCLUDE shouldn't occur without a P_BRANCH */ + if (!P_ISBRANCH(next)) { + /* no choice, avoid recursion */ + DPUTS(P_OP(scan) == P_WBRANCH, + "BUG: WBRANCH with no alternative."); + next = P_OPERAND(scan); + } else { + do { + save = patinput; + savglobflags = patglobflags; + saverrsfound = errsfound; + if (P_ISEXCLUDE(next)) { + /* + * The strategy is to test the asserted pattern, + * recording via P_EXCSYNC how far the part to + * be excluded matched. We then set the + * length of the test string to that + * point and see if the exclusion as far as + * P_EXCEND also matches that string. + * We need to keep testing the asserted pattern + * by backtracking, since the first attempt + * may be excluded while a later attempt may not. + * For this we keep a pointer just after + * the P_EXCLUDE which is tested by the P_EXCSYNC + * to see if we matched there last time, in which + * case we fail. If there is nothing to backtrack + * over, that doesn't matter: we should fail anyway. + * The pointer also tells us where the asserted + * pattern matched for use by the exclusion. + * + * It's hard to allocate space for this + * beforehand since we may need to do it + * recursively. + * + * P.S. in case you were wondering, this code + * is horrible. + */ + Upat syncstrp; + char *origpatinend; + unsigned char *oldsyncstr; + char *matchpt = NULL; + int ret, savglobdots, matchederrs = 0; + int savparsfound = parsfound; + DPUTS(P_OP(scan) == P_WBRANCH, + "BUG: excluded WBRANCH"); + syncstrp = P_OPERAND(next); + /* + * Unlike WBRANCH, each test at the same exclude + * sync point (due to an external loop) is separate, + * i.e testing (foo~bar)# is no different from + * (foo~bar)(foo~bar)... from the exclusion point + * of view, so we use a different sync string. + */ + oldsyncstr = syncstrp->p; + syncstrp->p = (unsigned char *) + zshcalloc((patinend - patinstart) + 1); + origpatinend = patinend; + while ((ret = patmatch(P_OPERAND(scan)))) { + unsigned char *syncpt; + char *savpatinstart; + int savforce = forceerrs; + int savpatflags = patflags, synclen; + forceerrs = -1; + savglobdots = globdots; + matchederrs = errsfound; + matchpt = patinput; /* may not be end */ + globdots = 1; /* OK to match . first */ + /* Find the point where the scan + * matched the part to be excluded: because + * of backtracking, the one + * most recently matched will be the first. + * (Luckily, backtracking is done after all + * possibilities for approximation have been + * checked.) + */ + for (syncpt = syncstrp->p; !*syncpt; syncpt++) + ; + synclen = syncpt - syncstrp->p; + if (patinstart + synclen != patinend) { + /* + * Temporarily mark the string as + * ending at this point. + */ + DPUTS(patinstart + synclen > matchpt, + "BUG: EXCSYNC failed"); + + patinend = patinstart + synclen; + /* + * If this isn't really the end of the string, + * remember this for the (#e) assertion. + */ + patflags |= PAT_NOTEND; + } + savpatinstart = patinstart; + next = PATNEXT(scan); + while (next && P_ISEXCLUDE(next)) { + patinput = save; + /* + * turn off approximations in exclusions: + * note we keep remaining patglobflags + * set by asserted branch (or previous + * excluded branches, for consistency). + */ + patglobflags &= ~0xff; + errsfound = 0; + opnd = P_OPERAND(next) + 1; + if (P_OP(next) == P_EXCLUDP && patinpath) { + /* + * Top level exclusion with a file, + * applies to whole path so add the + * segments already matched. + * We copied these in front of the + * test pattern, so patinend doesn't + * need moving. + */ + DPUTS(patinput != patinstart, + "BUG: not at start excluding path"); + patinput = patinstart = patinpath; + } + if (patmatch(opnd)) { + ret = 0; + /* + * Another subtlety: if we exclude the + * match, any parentheses just found + * become invalidated. + */ + parsfound = savparsfound; + } + if (patinpath) { + patinput = savpatinstart + + (patinput - patinstart); + patinstart = savpatinstart; + } + if (!ret) + break; + next = PATNEXT(next); + } + /* + * Restore original end position. + */ + patinend = origpatinend; + patflags = savpatflags; + globdots = savglobdots; + forceerrs = savforce; + if (ret) + break; + patinput = save; + patglobflags = savglobflags; + errsfound = saverrsfound; + } + zfree((char *)syncstrp->p, + (patinend - patinstart) + 1); + syncstrp->p = oldsyncstr; + if (ret) { + patinput = matchpt; + errsfound = matchederrs; + return 1; + } + while ((scan = PATNEXT(scan)) && + P_ISEXCLUDE(scan)) + ; + } else { + int ret = 1, pfree = 0; + Upat ptrp = NULL; + unsigned char *ptr; + if (P_OP(scan) == P_WBRANCH) { + /* + * This is where we make sure that we are not + * repeatedly matching zero-length strings in + * a closure, which would cause an infinite loop, + * and also remove exponential behaviour in + * backtracking nested closures. + * The P_WBRANCH operator leaves a space for a + * uchar *, initialized to NULL, which is + * turned into a string the same length as the + * target string. Every time we match from a + * particular point in the target string, we + * stick a 1 at the corresponding point here. + * If we come round to the same branch again, and + * there is already a 1, then the test fails. + */ + opnd = P_OPERAND(scan); + ptrp = opnd++; + if (!ptrp->p) { + ptrp->p = (unsigned char *) + zshcalloc((patinend - patinstart) + 1); + pfree = 1; + } + ptr = ptrp->p + (patinput - patinstart); + + /* + * Without approximation, this is just a + * single bit test. With approximation, we + * need to know how many errors there were + * last time we made the test. If errsfound + * is now smaller than it was, hence we can + * make more approximations in the remaining + * code, we continue with the test. + * (This is why the max number of errors is + * 254, not 255.) + */ + if (*ptr && errsfound + 1 >= *ptr) + ret = 0; + *ptr = errsfound + 1; + } else + opnd = P_OPERAND(scan); + if (ret) + ret = patmatch(opnd); + if (pfree) { + zfree((char *)ptrp->p, + (patinend - patinstart) + 1); + ptrp->p = NULL; + } + if (ret) + return 1; + scan = PATNEXT(scan); + } + patinput = save; + patglobflags = savglobflags; + errsfound = saverrsfound; + DPUTS(P_OP(scan) == P_WBRANCH, + "BUG: WBRANCH not first choice."); + next = PATNEXT(scan); + } while (scan && P_ISBRANCH(scan)); + return 0; + } + break; + case P_STAR: + /* Handle specially for speed, although really P_ONEHASH+P_ANY */ + case P_ONEHASH: + case P_TWOHASH: + /* + * This is just simple cases, matching one character. + * With approximations, we still handle * this way, since + * no approximation is ever necessary, but other closures + * are handled by the more complicated branching method + */ + op = P_OP(scan); + /* Note that no counts possibly metafied characters */ + start = patinput; + if (op == P_STAR) { + for (no = 0; patinput < patinend; CHARINC(patinput)) + no++; + /* simple optimization for reasonably common case */ + if (P_OP(next) == P_END) + return 1; + } else { + DPUTS(patglobflags & 0xff, + "BUG: wrong backtracking with approximation."); + if (!globdots && P_NOTDOT(P_OPERAND(scan)) && + patinput == patinstart && patinput < patinend && + CHARREF(patinput) == '.') + return 0; + no = patrepeat(P_OPERAND(scan)); + } + min = (op == P_TWOHASH) ? 1 : 0; + /* + * Lookahead to avoid useless matches. This is not possible + * with approximation. + */ + if (P_OP(next) == P_EXACTLY && P_LS_LEN(next) && + !(patglobflags & 0xff)) { + char *nextop = P_LS_STR(next); + /* + * If that P_EXACTLY is last (common in simple patterns, + * such as *.c), then it can be only be matched at one + * point in the test string, so record that. + */ + Upat ptemp= PATNEXT(next); + if ( P_OP(ptemp)== P_END && + !(patflags & PAT_NOANCH)) { + int ptlen = patinend - patinput; + int lenmatch = patinend - (min ? CHARNEXT(start) : start); + /* Are we in the right range? */ + if (P_LS_LEN(next) > lenmatch || P_LS_LEN(next) < ptlen) + return 0; + /* Yes, just position appropriately and test. */ + patinput += ptlen - P_LS_LEN(next); + /* + * Here we will need to be careful that patinput is not + * in the middle of a multibyte character. + */ + /* Continue loop with P_EXACTLY test. */ + break; + } + nextch = CHARREF(nextop); + } else + nextch = -1; + save = patinput; + savglobflags = patglobflags; + saverrsfound = errsfound; + while (no >= min) { + int charmatch_cache; + if (nextch < 0 || + (patinput < patinend && + CHARMATCH_EXPR(CHARREF(patinput), nextch))) { + if (patmatch(next)) + return 1; + } + no--; + save--; + /* + * Here we will need to make sure save is + * decremented properly to the start of + * the preceeding multibyte character. + */ + patinput = save; + patglobflags = savglobflags; + errsfound = saverrsfound; + } + /* + * As with branches, the patmatch(next) stuff for * + * handles approximation, so we don't need to try + * anything here. + */ + return 0; + case P_ISSTART: + if (patinput != patinstart || (patflags & PAT_NOTSTART)) + fail = 1; + break; + case P_ISEND: + if (patinput < patinend || (patflags & PAT_NOTEND)) + fail = 1; + break; + case P_END: + if (!(fail = (patinput < patinend && !(patflags & PAT_NOANCH)))) + return 1; + break; +#ifdef DEBUG + default: + dputs("BUG: bad operand in patmatch."); + return 0; + break; +#endif + } + + if (fail) { + if (errsfound < (patglobflags & 0xff) && + (forceerrs == -1 || errsfound < forceerrs)) { + /* + * Approximation code. There are four possibilities + * + * 1. omit character from input string + * 2. transpose characters in input and pattern strings + * 3. omit character in both input and pattern strings + * 4. omit character from pattern string. + * + * which we try in that order. + * + * Of these, 2, 3 and 4 require an exact match string + * (P_EXACTLY) while 1, 2 and 3 require that we not + * have reached the end of the input string. + * + * Note in each case after making the approximation we + * need to retry the *same* pattern; this is what + * requires exactpos, a slightly doleful way of + * communicating with the exact character matcher. + */ + char *savexact = exactpos; + save = patinput; + savglobflags = patglobflags; + saverrsfound = ++errsfound; + fail = 0; + + DPUTS(P_OP(scan) != P_EXACTLY && exactpos, + "BUG: non-exact match has set exactpos"); + + /* Try omitting a character from the input string */ + if (patinput < patinend) { + CHARINC(patinput); + /* If we are not on an exact match, then this is + * our last gasp effort, so we can optimize out + * the recursive call. + */ + if (P_OP(scan) != P_EXACTLY) + continue; + if (patmatch(scan)) + return 1; + } + + if (P_OP(scan) == P_EXACTLY) { + char *nextexact = savexact; + DPUTS(!savexact, + "BUG: exact match has not set exactpos"); + CHARINC(nextexact); + + if (save < patinend) { + char *nextin = save; + CHARINC(nextin); + patglobflags = savglobflags; + errsfound = saverrsfound; + exactpos = savexact; + + /* + * Try swapping two characters in patinput and + * exactpos + */ + if (save < patinend && nextin < patinend && + nextexact < exactend) { + int cin0 = CHARREF(save); + int cpa0 = CHARREF(exactpos); + int cin1 = CHARREF(nextin); + int cpa1 = CHARREF(nextexact); + + if (CHARMATCH(cin0, cpa1) && + CHARMATCH(cin1, cpa0)) { + patinput = nextin; + CHARINC(patinput); + exactpos = nextexact; + CHARINC(exactpos); + if (patmatch(scan)) + return 1; + + patglobflags = savglobflags; + errsfound = saverrsfound; + } + } + + /* + * Try moving up both strings. + */ + patinput = nextin; + exactpos = nextexact; + if (patmatch(scan)) + return 1; + + patinput = save; + patglobflags = savglobflags; + errsfound = saverrsfound; + exactpos = savexact; + } + + DPUTS(exactpos == exactend, "approximating too far"); + /* + * Try moving up the exact match pattern. + * This must be the last attempt, so just loop + * instead of calling recursively. + */ + CHARINC(exactpos); + continue; + } + } + exactpos = NULL; + return 0; + } + + scan = next; + } + + return 0; +} + +/**/ +static int +patmatchrange(char *range, int ch) +{ + int r1, r2; + + /* + * Careful here: unlike other strings, range is a NULL-terminated, + * metafied string, because we need to treat the Posix and hyphenated + * ranges specially. + */ + for (; *range; range++) { + if (imeta(STOUC(*range))) { + switch (STOUC(*range)-STOUC(Meta)) { + case 0: + if (STOUC(*++range ^ 32) == ch) + return 1; + break; + case PP_ALPHA: + if (isalpha(ch)) + return 1; + break; + case PP_ALNUM: + if (isalnum(ch)) + return 1; + break; + case PP_ASCII: + if ((ch & ~0x7f) == 0) + return 1; + break; + case PP_BLANK: + if (ch == ' ' || ch == '\t') + return 1; + break; + case PP_CNTRL: + if (iscntrl(ch)) + return 1; + break; + case PP_DIGIT: + if (isdigit(ch)) + return 1; + break; + case PP_GRAPH: + if (isgraph(ch)) + return 1; + break; + case PP_LOWER: + if (islower(ch)) + return 1; + break; + case PP_PRINT: + if (isprint(ch)) + return 1; + break; + case PP_PUNCT: + if (ispunct(ch)) + return 1; + break; + case PP_SPACE: + if (isspace(ch)) + return 1; + break; + case PP_UPPER: + if (isupper(ch)) + return 1; + break; + case PP_XDIGIT: + if (isxdigit(ch)) + return 1; + break; + case PP_RANGE: + range++; + r1 = STOUC(UNMETA(range)); + METAINC(range); + r2 = STOUC(UNMETA(range)); + if (*range == Meta) + range++; + if (r1 <= ch && ch <= r2) + return 1; + break; + case PP_UNKWN: + DPUTS(1, "BUG: unknown posix range passed through.\n"); + break; + default: + DPUTS(1, "BUG: unknown metacharacter in range."); + break; + } + } else if (STOUC(*range) == ch) + return 1; + } + return 0; +} + +/* repeatedly match something simple and say how many times */ + +/**/ +static int patrepeat(Upat p) +{ + int count = 0, tch, charmatch_cache; + char *scan, *opnd; + + scan = patinput; + opnd = (char *)P_OPERAND(p); + + switch(P_OP(p)) { +#ifdef DEBUG + case P_ANY: + dputs("BUG: ?# did not get optimized to *"); + return 0; + break; +#endif + case P_EXACTLY: + DPUTS(P_LS_LEN(p) != 1, "closure following more than one character"); + tch = CHARREF(P_LS_STR(p)); + while (scan < patinend && + CHARMATCH_EXPR(CHARREF(scan), tch)) { + count++; + CHARINC(scan); + } + break; + case P_ANYOF: + while (scan < patinend && patmatchrange(opnd, CHARREF(scan))) { + count++; + CHARINC(scan); + } + break; + case P_ANYBUT: + while (scan < patinend && !patmatchrange(opnd, CHARREF(scan))) { + count++; + CHARINC(scan); + } + break; +#ifdef DEBUG + default: + dputs("BUG: something very strange is happening in patrepeat"); + return 0; + break; +#endif + } + + patinput = scan; + return count; +} + +/* Free a patprog. */ + +/**/ +mod_export void +freepatprog(Patprog prog) +{ + if (prog && prog != dummy_patprog1 && prog != dummy_patprog2) + zfree(prog, prog->size); +} + +/**/ +#ifdef ZSH_PAT_DEBUG + +/* Debugging stuff: print and test a regular expression */ + +/* Dump a regexp onto stdout in vaguely comprehensible form */ + +/**/ +static void +patdump(Patprog r) +{ + char *s, *base, op = P_EXACTLY; + Upat up, codestart, next; + + base = (char *)r; + s = base + r->startoff; + + if (r->flags & PAT_PURES) { + printf("STRING:%s\n", (char *)s); + } else { + codestart = (Upat)s; + while (op != P_END) { + up = (Upat)s; + op = P_OP(up); + printf("%2d%s", up-codestart, patprop(up)); + next = PATNEXT(up); + printf("(%d)", next ? next-codestart : 0); + s += sizeof(union upat); + if (op == P_EXACTLY) { + long llen = *(long *)s; + s += sizeof(long); + while (llen--) { + putchar(CHARREF(s)); + CHARINC(s); + } + } else if (op == P_ANYOF || op == P_ANYBUT) { + while (*s != '\0') { + if (itok(*s)) { + if (*s == Meta + PP_RANGE) { + s++; + printf("", UNMETA(s)); + } else { + printf("", *s - Meta); + s++; + continue; + } + } else + putchar(UNMETA(s)); + METAINC(s); + } + } else if (op == P_NUMRNG || op == P_NUMFROM || op == P_NUMTO) { + printf("%lu", (unsigned long)*(zrange_t *)s); + s += sizeof(zrange_t); + if (op == P_NUMRNG) { + printf("-%lu", (unsigned long)*(zrange_t *)s); + s += sizeof(zrange_t); + } + } else if (op == P_GFLAGS) { + printf("%ld, %ld", (++up)->l & ~0xff, (++up)->l & 0xff); + s += sizeof(union upat); + } else if (op == P_WBRANCH || op == P_EXCLUDE || + op == P_EXCLUDP) { + s += sizeof(union upat); + } + putchar('\n'); + s = base + (((s - base) + sizeof(union upat) - 1) & + ~(sizeof(union upat) - 1)); + } + } + + printf("Total size = %ld\n", r->size); + if (r->patstartch) + printf("start `%c' ", r->patstartch); + if (!(r->flags & PAT_NOANCH)) + printf("EOL-anchor "); + if (r->patnpar) + printf("%d active backreferences ", r->patnpar); + if (r->mustoff) + printf("must have \"%s\"", (char *)r + r->mustoff); + printf("\n"); + if (r->globflags) { + printf("Globbing flags: "); + if (r->globflags & GF_LCMATCHUC) + printf("LC matches UC "); + if (r->globflags & GF_IGNCASE) + printf("Ignore case"); + printf("\n"); + if (r->globflags & 0xff) + printf("Max errors = %d\n", r->globflags & 0xff); + } +} + +/**/ +static char * +patprop(Upat op) +{ + char *p = NULL; + static char buf[50]; + + strcpy(buf, ":"); + + switch(P_OP(op)) { + case P_ANY: + p = "ANY"; + break; + case P_ANYOF: + p = "ANYOF"; + break; + case P_ANYBUT: + p = "ANYBUT"; + break; + case P_BRANCH: + p = "BRANCH"; + break; + case P_WBRANCH: + p = "WBRANCH"; + break; + case P_EXCLUDE: + p = "EXCLUDE"; + break; + case P_EXCLUDP: + p = "EXCLUDP"; + break; + case P_EXCSYNC: + p = "EXCSYNC"; + break; + case P_EXCEND: + p = "EXCEND"; + break; + case P_EXACTLY: + p = "EXACTLY"; + break; + case P_GFLAGS: + p = "GFLAGS"; + break; + case P_ISSTART: + p = "ISSTART"; + break; + case P_ISEND: + p = "ISEND"; + break; + case P_NOTHING: + p = "NOTHING"; + break; + case P_BACK: + p = "BACK"; + break; + case P_END: + p = "END"; + break; + case P_OPEN: + case P_OPEN+1: + case P_OPEN+2: + case P_OPEN+3: + case P_OPEN+4: + case P_OPEN+5: + case P_OPEN+6: + case P_OPEN+7: + case P_OPEN+8: + case P_OPEN+9: + sprintf(buf+strlen(buf), "OPEN%ld", P_OP(op)-P_OPEN); + p = NULL; + break; + case P_CLOSE: + case P_CLOSE+1: + case P_CLOSE+2: + case P_CLOSE+3: + case P_CLOSE+4: + case P_CLOSE+5: + case P_CLOSE+6: + case P_CLOSE+7: + case P_CLOSE+8: + case P_CLOSE+9: + sprintf(buf+strlen(buf), "CLOSE%ld", P_OP(op)-P_CLOSE); + p = NULL; + break; + case P_STAR: + p = "STAR"; + break; + case P_ONEHASH: + p = "ONEHASH"; + break; + case P_TWOHASH: + p = "TWOHASH"; + break; + case P_NUMRNG: + p = "NUMRNG"; + break; + case P_NUMFROM: + p = "NUMFROM"; + break; + case P_NUMTO: + p = "NUMTO"; + break; + case P_NUMANY: + p = "NUMANY"; + break; + default: + fprintf(stderr, "Bad opcode\n"); + p = NULL; + break; + } + if (p) + strcat(buf, p); + return buf; +} +#ifndef __SYMBIAN32__ +/**/ +int +bin_patdebug(char *name, char **args, char *ops, int func) +{ + Patprog prog; + int ret = 0; + + tokenize(*args); + + if (!(prog = patcompile((char *)*args, 0, 0))) + return 1; + if (ops['p'] || !args[1]) { + patdump(prog); + } + + while (*++args) { + if (!pattry(prog, (char *)*args)) + ret++; + } + return ret; +} +#endif //#ifndef __SYMBIAN32__ +/**/ +#endif /* ZSH_PAT_DEBUG */