src/glob.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  * glob.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  *  glob() - 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
  29 #define CHECK_BIT(tab, bit)  (tab[(bit)/8]&(1<<((bit)%8)))
  30 /* bytes used for [chars] in compiled expr */
  31 #define BITLISTSIZE  16
  32
  33
  34 static void globchars (const char *s, const char *e, char *b);
  35
  36
  37 /*
  38  * glob() - match a string against a simple pattern
  39  */
  40 int glob (const char *c, const char *s) {
  41   char bitlist[BITLISTSIZE];
  42   const char *here;
  43   //
  44   for (;;) {
  45     switch (*c++) {
  46       case '\0': return *s?-1:0;
  47       case '?': if (!*s++) return 1; break;
  48       case '[':
  49         /* scan for matching ] */
  50         here = c;
  51         /* k8: allow []...] and [^]...] */
  52         if (*c == '^') ++c;
  53         if (*c == ']') ++c;
  54         /* k8 */
  55         do { if (!*c++) return 1; } while (here == c || *c != ']') ;
  56         ++c;
  57         /* build character class bitlist */
  58         globchars(here, c, bitlist);
  59         if (!CHECK_BIT(bitlist, *(unsigned char *)s)) return 1;
  60         ++s;
  61         break;
  62       case '*':
  63         here = s;
  64         while (*s) ++s;
  65         /* try to match the rest of the pattern in a recursive call */
  66         /* if the match fails we'll back up chars, retrying */
  67         while (s != here) {
  68           int r;
  69           /* a fast path for the last token in a pattern */
  70           r = *c?glob(c, s):*s?-1:0;
  71           if (!r) return 0;
  72           if (r < 0) return 1;
  73           --s;
  74         }
  75         break;
  76       case '\\':
  77         /* force literal match of next char */
  78         if (!*c || *s++ != *c++) return 1;
  79         break;
  80       default:
  81         if (*s++ != c[-1]) return 1;
  82         break;
  83     }
  84   }
  85 }
  86
  87
  88 /*
  89  * globchars() - build a bitlist to check for character group match
  90  */
  91 static void globchars (const char *s, const char *e, char *b) {
  92   int neg = 0;
  93   int c;
  94   //
  95   memset(b, '\0', BITLISTSIZE);
  96   if (*s == '^') ++neg, ++s;
  97   while (s < e) {
  98     if (s+2 < e && s[1] == '-') {
  99       for (c = s[0]; c <= s[2]; ++c) b[c/8] |= (1<<(c%8));
 100       s += 3;
 101     } else {
 102       c = *s++;
 103       b[c/8] |= (1<<(c%8));
 104     }
 105   }
 106   if (neg) for (c = 0; c < BITLISTSIZE; ++c) b[c] ^= 0377;
 107   /* don't include \0 in either $[chars] or $[^chars] */
 108   b[0] &= 0376;
 109 }