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 /*
   8  * glob.c - match a string against a simple pattern
   9  *
  10  * Understands the following patterns:
  11  *
  12  *  * any number of characters
  13  *  ? any single character
  14  *  [a-z] any single character in the range a-z
  15  *  [^a-z]  any single character not in the range a-z
  16  *  \x  match x
  17  *
  18  * External functions:
  19  *
  20  *  glob() - match a string against a simple pattern
  21  *
  22  * Internal functions:
  23  *
  24  *  globchars() - build a bitlist to check for character group match
  25  *
  26  * 11/04/02 (seiwald) - const-ing for string literals
  27  */
  28
  29 # include "jam.h"
  30
  31 # define CHECK_BIT( tab, bit ) ( tab[ (bit)/8 ] & (1<<( (bit)%8 )) )
  32 # define BITLISTSIZE 16 /* bytes used for [chars] in compiled expr */
  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           else 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
 107   if (neg) {
 108     for( c = 0; c < BITLISTSIZE; c++) b[c] ^= 0377;
 109   }
 110
 111   /* Don't include \0 in either $[chars] or $[^chars] */
 112   b[0] &= 0376;
 113 }