src/matchglob.c

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