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