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
  27 # include "jam.h"
  28
  29 # define CHECK_BIT( tab, bit ) ( tab[ (bit)/8 ] & (1<<( (bit)%8 )) )
  30 # define BITLISTSIZE 16 /* bytes used for [chars] in compiled expr */
  31
  32 static void globchars( char * s, char * e, char * b );
  33
  34
  35 /*
  36  * glob() - match a string against a simple pattern.
  37  */
  38
  39 int glob( char * c, char * s )
  40 {
  41     char   bitlist[ BITLISTSIZE ];
  42     char * here;
  43
  44     for ( ; ; )
  45     switch ( *c++ )
  46     {
  47     case '\0':
  48         return *s ? -1 : 0;
  49
  50     case '?':
  51         if ( !*s++ )
  52             return 1;
  53         break;
  54
  55     case '[':
  56         /* Scan for matching ]. */
  57
  58         here = c;
  59         do if ( !*c++ ) return 1;
  60         while ( ( here == c ) || ( *c != ']' ) );
  61         ++c;
  62
  63         /* Build character class bitlist. */
  64
  65         globchars( here, c, bitlist );
  66
  67         if ( !CHECK_BIT( bitlist, *(unsigned char *)s ) )
  68             return 1;
  69         ++s;
  70         break;
  71
  72     case '*':
  73         here = s;
  74
  75         while ( *s )
  76             ++s;
  77
  78         /* Try to match the rest of the pattern in a recursive */
  79         /* call.  If the match fails we'll back up chars, retrying. */
  80
  81         while ( s != here )
  82         {
  83             int r;
  84
  85             /* A fast path for the last token in a pattern. */
  86             r = *c ? glob( c, s ) : *s ? -1 : 0;
  87
  88             if ( !r )
  89                 return 0;
  90             if ( r < 0 )
  91                 return 1;
  92             --s;
  93         }
  94         break;
  95
  96     case '\\':
  97         /* Force literal match of next char. */
  98         if ( !*c || ( *s++ != *c++ ) )
  99             return 1;
 100         break;
 101
 102     default:
 103         if ( *s++ != c[ -1 ] )
 104             return 1;
 105         break;
 106     }
 107 }
 108
 109
 110 /*
 111  * globchars() - build a bitlist to check for character group match.
 112  */
 113
 114 static void globchars( char * s,  char * e, char * b )
 115 {
 116     int neg = 0;
 117
 118     memset( b, '\0', BITLISTSIZE  );
 119
 120     if ( *s == '^' )
 121     {
 122         ++neg;
 123         ++s;
 124     }
 125
 126     while ( s < e )
 127     {
 128         int c;
 129
 130         if ( ( s + 2 < e ) && ( s[1] == '-' ) )
 131         {
 132             for ( c = s[0]; c <= s[2]; ++c )
 133                 b[ c/8 ] |= ( 1 << ( c % 8 ) );
 134             s += 3;
 135         }
 136         else
 137         {
 138             c = *s++;
 139             b[ c/8 ] |= ( 1 << ( c % 8 ) );
 140         }
 141     }
 142
 143     if ( neg )
 144     {
 145         int i;
 146         for ( i = 0; i < BITLISTSIZE; ++i )
 147             b[ i ] ^= 0377;
 148     }
 149
 150     /* Do not include \0 in either $[chars] or $[^chars]. */
 151     b[0] &= 0376;
 152 }