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         do { if (!*c++) return 1; } while (here == c || *c != ']') ;
  52         c++;
  53         /* build character class bitlist */
  54         globchars(here, c, bitlist);
  55         if (!CHECK_BIT(bitlist, *(unsigned char *)s)) return 1;
  56         s++;
  57         break;
  58       case '*':
  59         here = s;
  60         while (*s) s++;
  61         /* Try to match the rest of the pattern in a recursive call.
  62            If the match fails we'll back up chars, retrying. */
  63         while (s != here) {
  64           int r;
  65           /* A fast path for the last token in a pattern */
  66           r = *c?glob(c, s):*s?-1:0;
  67           if (!r) return 0;
  68           else if (r < 0) return 1;
  69           --s;
  70         }
  71         break;
  72       case '\\':
  73         /* Force literal match of next char. */
  74         if (!*c || *s++ != *c++) return 1;
  75         break;
  76       default:
  77         if (*s++ != c[-1]) return 1;
  78         break;
  79     }
  80   }
  81 }
  82
  83
  84 /*
  85  * globchars() - build a bitlist to check for character group match
  86  */
  87 static void globchars (const char *s, const char *e, char *b) {
  88   int neg = 0;
  89   int c;
  90
  91   memset(b, '\0', BITLISTSIZE);
  92   if (*s == '^') neg++, s++;
  93   while (s < e) {
  94     if (s+2 < e && s[1] == '-') {
  95       for (c = s[0]; c <= s[2]; c++) b[c/8] |= (1<<(c%8));
  96       s += 3;
  97     } else {
  98       c = *s++;
  99       b[c/8] |= (1<<(c%8));
 100     }
 101   }
 102
 103   if (neg) {
 104     for( c = 0; c < BITLISTSIZE; c++) b[c] ^= 0377;
 105   }
 106
 107   /* Don't include \0 in either $[chars] or $[^chars] */
 108   b[0] &= 0376;
 109 }