1/* $XConsortium: wildmat.c,v 1.2 94/04/13 18:40:59 rws Exp $ */ 2/* 3** 4** Do shell-style pattern matching for ?, \, [], and * characters. 5** Might not be robust in face of malformed patterns; e.g., "foo[a-" 6** could cause a segmentation violation. It is 8bit clean. 7** 8** Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986. 9** Rich $alz is now <rsalz@bbn.com>. 10** April, 1991: Replaced mutually-recursive calls with in-line code 11** for the star character. 12** 13** Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code. 14** This can greatly speed up failing wildcard patterns. For example: 15** pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-* 16** text 1: -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1 17** text 2: -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1 18** Text 1 matches with 51 calls, while text 2 fails with 54 calls. Without 19** the ABORT, then it takes 22310 calls to fail. Ugh. The following 20** explanation is from Lars: 21** The precondition that must be fulfilled is that DoMatch will consume 22** at least one character in text. This is true if *p is neither '*' nor 23** '\0'.) The last return has ABORT instead of false to avoid quadratic 24** behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx". With 25** false, each star-loop has to run to the end of the text; with ABORT 26** only the last one does. 27** 28** Once the control of one instance of DoMatch enters the star-loop, that 29** instance will return either true or ABORT, and any calling instance 30** will therefore return immediately after (without calling recursively 31** again). In effect, only one star-loop is ever active. It would be 32** possible to modify the code to maintain this context explicitly, 33** eliminating all recursive calls at the cost of some complication and 34** loss of clarity (and the ABORT stuff seems to be unclear enough by 35** itself). I think it would be unwise to try to get this into a 36** released version unless you have a good test data base to try it out 37** on. 38*/ 39 40#include "transmission.h" 41#include "utils.h" 42 43#define ABORT -1 44 45 /* What character marks an inverted character class? */ 46#define NEGATE_CLASS '^' 47 /* Is "*" a common pattern? */ 48#define OPTIMIZE_JUST_STAR 49 /* Do tar(1) matching rules, which ignore a trailing slash? */ 50#undef MATCH_TAR_PATTERN 51 52 53/* 54** Match text and p, return true, false, or ABORT. 55*/ 56static int 57DoMatch( const char * text, const char * p ) 58{ 59 register int last; 60 register int matched; 61 register int reverse; 62 63 for ( ; *p; text++, p++) { 64 if (*text == '\0' && *p != '*') 65 return ABORT; 66 switch (*p) { 67 case '\\': 68 /* Literal match with following character. */ 69 p++; 70 /* FALLTHROUGH */ 71 default: 72 if (*text != *p) 73 return false; 74 continue; 75 case '?': 76 /* Match anything. */ 77 continue; 78 case '*': 79 while (*++p == '*') 80 /* Consecutive stars act just like one. */ 81 continue; 82 if (*p == '\0') 83 /* Trailing star matches everything. */ 84 return true; 85 while (*text) 86 if ((matched = DoMatch(text++, p)) != false) 87 return matched; 88 return ABORT; 89 case '[': 90 reverse = p[1] == NEGATE_CLASS ? true : false; 91 if (reverse) 92 /* Inverted character class. */ 93 p++; 94 for (last = 0400, matched = false; *++p && *p != ']'; last = *p) 95 /* This next line requires a good C compiler. */ 96 if (*p == '-' ? *text <= *++p && *text >= last : *text == *p) 97 matched = true; 98 if (matched == reverse) 99 return false; 100 continue; 101 } 102 } 103 104#ifdef MATCH_TAR_PATTERN 105 if (*text == '/') 106 return true; 107#endif /* MATCH_TAR_ATTERN */ 108 return *text == '\0'; 109} 110 111 112/* User-level routine. returns whether or not 'text' and 'p' matched */ 113bool 114tr_wildmat(const char * text, const char * p ) 115{ 116 if (p[0] == '*' && p[1] == '\0') 117 return true; 118 119 return DoMatch(text, p) == true; 120} 121