src/matchglob.c

   1 /*
   2  * Copyright 1994 Christopher Seiwald.  All rights reserved.
   3  *
   4  * This file is part of Jam - see jam.c for Copyright information.
   5  */
   6 /*
   7  * matchglob.c - match a string against a simple pattern
   8  *
   9  * Understands the following patterns:
  10  *
  11  *  * any number of characters
  12  *  ? any single character
  13  *  [a-z] any single character in the range a-z
  14  *  [^a-z]  any single character not in the range a-z
  15  *  \x  match x
  16  *
  17  * External functions:
  18  *
  19  *  matchglob() - match a string against a simple pattern
  20  *
  21  * Internal functions:
  22  *
  23  *  globchars() - build a bitlist to check for character group match
  24  *
  25  * 11/04/02 (seiwald) - const-ing for string literals
  26  */
  27 #include "jam.h"
  28 #include "matchglob.h"
  29
  30
  31 #define CHECK_BIT(tab, bit)  (tab[(bit)/8]&(1<<((bit)%8)))
  32 #define SET_BIT(tab, bit)    (tab[(bit)/8] |= (1<<((bit)%8)))
  33
  34 /* bytes used for [chars] in compiled expr */
  35 #define BITLISTSIZE  (32)
  36
  37
  38 static inline int casechar (char ch) {
  39   return
  40     (ch >= 'a' && ch <= 'z') ? ch-32 :
  41     (ch >= 'A' && ch <= 'Z') ? ch+32 :
  42     ch;
  43 }
  44
  45
  46 static inline int lower (char ch) {
  47   return (ch >= 'A' && ch <= 'Z') ? ch+32 : ch;
  48 }
  49
  50
  51 static inline int samechars (char c0, char c1, int casesens) {
  52   return casesens ? c0==c1 : lower(c0)==lower(c1);
  53 }
  54
  55
  56 /*
  57  * globchars() - build a bitlist to check for character group match
  58  */
  59 static void globchars (const char *s, const char *e, unsigned char *b, int casesens) {
  60   int neg = 0, c;
  61   //
  62   memset(b, 0, BITLISTSIZE);
  63   if (*s == '^') ++neg, ++s;
  64   //
  65   while (s < e) {
  66     if (s+2 < e && s[1] == '-') {
  67       for (c = (unsigned char)s[0]; c <= (unsigned char)s[2]; ++c) {
  68         SET_BIT(b, c);
  69         if (!casesens) SET_BIT(b, casechar(c));
  70       }
  71       s += 3;
  72     } else {
  73       c = (unsigned char)(*s++);
  74       SET_BIT(b, c);
  75       if (!casesens) SET_BIT(b, casechar(c));
  76     }
  77   }
  78   if (neg) for (c = 0; c < BITLISTSIZE; ++c) b[c] ^= 0xff;
  79   /* don't include \0 in either $[chars] or $[^chars] */
  80   b[0] &= 0xfe;
  81 }
  82
  83
  84 int matchglob (const char *pat, const char *str) {
  85   return matchglobex(pat, str, 1);
  86 }
  87
  88
  89 /*
  90  * matchglobex() - match a string against a simple pattern
  91  */
  92 int matchglobex (const char *pat, const char *str, int casesens) {
  93   unsigned char bitlist[BITLISTSIZE];
  94   const char *here;
  95   //
  96   for (;;) {
  97     switch (*pat++) {
  98       case '\0': return *str?-1:0;
  99       case '?': if (!*str++) return 1; break;
 100       case '[':
 101         /* scan for matching ] */
 102         here = pat;
 103         /* k8: allow []...] and [^]...] */
 104         if (*pat == '^') ++pat;
 105         if (*pat == ']') ++pat;
 106         /* k8 */
 107         do { if (!*pat++) return 1; } while (here == pat || *pat != ']') ;
 108         ++pat;
 109         /* build character class bitlist */
 110         globchars(here, pat, bitlist, casesens);
 111         if (!CHECK_BIT(bitlist, *(unsigned char *)str)) return 1;
 112         ++str;
 113         break;
 114       case '*':
 115         here = str;
 116         while (*str) ++str;
 117         /* try to match the rest of the pattern in a recursive call */
 118         /* if the match fails we'll back up chars, retrying */
 119         while (str != here) {
 120           int r;
 121           /* a fast path for the last token in a pattern */
 122           r = *pat?matchglobex(pat, str, casesens):*str?-1:0;
 123           if (!r) return 0;
 124           if (r < 0) return 1;
 125           --str;
 126         }
 127         break;
 128       case '\\':
 129         /* force literal match of next char */
 130         if (!*pat || !samechars(*str++, *pat++, casesens)) return 1;
 131         break;
 132       default:
 133         if (!samechars(*str++, pat[-1], casesens)) return 1;
 134         break;
 135     }
 136   }
 137 }