expect/exp_glob.c

   1 /* exp_glob.c - expect functions for doing glob
   2
   3 Based on Tcl's glob functions but modified to support anchors and to
   4 return information about the possibility of future matches
   5
   6 Modifications by: Don Libes, NIST, 2/6/90
   7
   8 Design and implementation of this program was paid for by U.S. tax
   9 dollars.  Therefore it is public domain.  However, the author and NIST
  10 would appreciate credit if this program or parts of it are used.
  11
  12 */
  13
  14 #include "expect_cf.h"
  15 #include "tcl.h"
  16 #include "exp_int.h"
  17
  18 #if 0
  19 /* The following functions implement expect's glob-style string matching */
  20 /* Exp_StringMatch allow's implements the unanchored front (or conversely */
  21 /* the '^') feature.  Exp_StringMatch2 does the rest of the work. */
  22 int     /* returns # of chars that matched */
  23 Exp_StringMatch(string, pattern,offset)
  24 char *string;
  25 char *pattern;
  26 int *offset;    /* offset from beginning of string where pattern matches */
  27 {
  28         char *s;
  29         int sm; /* count of chars matched or -1 */
  30         int caret = FALSE;
  31
  32         *offset = 0;
  33
  34         if (pattern[0] == '^') {
  35                 caret = TRUE;
  36                 pattern++;
  37         }
  38
  39         sm = Exp_StringMatch2(string,pattern);
  40         if (sm >= 0) return(sm);
  41
  42         if (caret) return(-1);
  43
  44         if (pattern[0] == '*') return(-1);
  45
  46         for (s = string;*s;s++) {
  47                 sm = Exp_StringMatch2(s,pattern);
  48                 if (sm != -1) {
  49                         *offset = s-string;
  50                         return(sm);
  51                 }
  52         }
  53         return(-1);
  54 }
  55 #endif
  56
  57 /* The following functions implement expect's glob-style string matching */
  58 /* Exp_StringMatch allow's implements the unanchored front (or conversely */
  59 /* the '^') feature.  Exp_StringMatch2 does the rest of the work. */
  60 int     /* returns # of chars that matched */
  61 Exp_StringMatch(string, pattern,offset)
  62 char *string;
  63 char *pattern;
  64 int *offset;    /* offset from beginning of string where pattern matches */
  65 {
  66         char *s;
  67         int sm; /* count of chars matched or -1 */
  68         int caret = FALSE;
  69         int star = FALSE;
  70
  71         *offset = 0;
  72
  73         if (pattern[0] == '^') {
  74                 caret = TRUE;
  75                 pattern++;
  76         } else if (pattern[0] == '*') {
  77                 star = TRUE;
  78         }
  79
  80         /*
  81          * test if pattern matches in initial position.
  82          * This handles front-anchor and 1st iteration of non-front-anchor.
  83          * Note that 1st iteration must be tried even if string is empty.
  84          */
  85
  86         sm = Exp_StringMatch2(string,pattern);
  87         if (sm >= 0) return(sm);
  88
  89         if (caret) return -1;
  90         if (star) return -1;
  91
  92         if (*string == '\0') return -1;
  93
  94         for (s = string+1;*s;s++) {
  95                 sm = Exp_StringMatch2(s,pattern);
  96                 if (sm != -1) {
  97                         *offset = s-string;
  98                         return(sm);
  99                 }
 100         }
 101         return -1;
 102 }
 103
 104 /* Exp_StringMatch2 --
 105
 106 Like Tcl_StringMatch except that
 107 1) returns number of characters matched, -1 if failed.
 108         (Can return 0 on patterns like "" or "$")
 109 2) does not require pattern to match to end of string
 110 3) much of code is stolen from Tcl_StringMatch
 111 4) front-anchor is assumed (Tcl_StringMatch retries for non-front-anchor)
 112 */
 113
 114 int Exp_StringMatch2(string,pattern)
 115     register char *string;      /* String. */
 116     register char *pattern;     /* Pattern, which may contain
 117                                  * special characters. */
 118 {
 119     char c2;
 120     int match = 0;      /* # of chars matched */
 121
 122     while (1) {
 123         /* If at end of pattern, success! */
 124         if (*pattern == 0) {
 125                 return match;
 126         }
 127
 128         /* If last pattern character is '$', verify that entire
 129          * string has been matched.
 130          */
 131         if ((*pattern == '$') && (pattern[1] == 0)) {
 132                 if (*string == 0) return(match);
 133                 else return(-1);
 134         }
 135
 136         /* Check for a "*" as the next pattern character.  It matches
 137          * any substring.  We handle this by calling ourselves
 138          * recursively for each postfix of string, until either we
 139          * match or we reach the end of the string.
 140          */
 141
 142         if (*pattern == '*') {
 143 #if 1
 144             int head_len;
 145             char *tail;
 146 #endif
 147             pattern += 1;
 148             if (*pattern == 0) {
 149                 return(strlen(string)+match); /* DEL */
 150             }
 151 #if 1
 152             /* find longest match - switched to this on 12/31/93 */
 153             head_len = strlen(string);  /* length before tail */
 154             tail = string + head_len;
 155             while (head_len >= 0) {
 156                 int rc;
 157
 158                 if (-1 != (rc = Exp_StringMatch2(tail, pattern))) {
 159                     return rc + match + head_len;       /* DEL */
 160                 }
 161                 tail--;
 162                 head_len--;
 163             }
 164 #else
 165             /* find shortest match */
 166             while (*string != 0) {
 167                 int rc;                                 /* DEL */
 168
 169                 if (-1 != (rc = Exp_StringMatch2(string, pattern))) {
 170                     return rc+match;            /* DEL */
 171                 }
 172                 string += 1;
 173                 match++;                                /* DEL */
 174             }
 175             if (*pattern == '$') return 0;      /* handle *$ */
 176 #endif
 177             return -1;                                  /* DEL */
 178         }
 179
 180         /*
 181          * after this point, all patterns must match at least one
 182          * character, so check this
 183          */
 184
 185         if (*string == 0) return -1;
 186
 187         /* Check for a "?" as the next pattern character.  It matches
 188          * any single character.
 189          */
 190
 191         if (*pattern == '?') {
 192             goto thisCharOK;
 193         }
 194
 195         /* Check for a "[" as the next pattern character.  It is followed
 196          * by a list of characters that are acceptable, or by a range
 197          * (two characters separated by "-").
 198          */
 199
 200         if (*pattern == '[') {
 201             pattern += 1;
 202             while (1) {
 203                 if ((*pattern == ']') || (*pattern == 0)) {
 204                     return -1;                  /* was 0; DEL */
 205                 }
 206                 if (*pattern == *string) {
 207                     break;
 208                 }
 209                 if (pattern[1] == '-') {
 210                     c2 = pattern[2];
 211                     if (c2 == 0) {
 212                         return -1;              /* DEL */
 213                     }
 214                     if ((*pattern <= *string) && (c2 >= *string)) {
 215                         break;
 216                     }
 217                     if ((*pattern >= *string) && (c2 <= *string)) {
 218                         break;
 219                     }
 220                     pattern += 2;
 221                 }
 222                 pattern += 1;
 223             }
 224
 225 /* OOPS! Found a bug in vanilla Tcl - have sent back to Ousterhout */
 226 /* but he hasn't integrated it yet. - DEL */
 227
 228 #if 0
 229             while ((*pattern != ']') && (*pattern != 0)) {
 230 #else
 231             while (*pattern != ']') {
 232                 if (*pattern == 0) {
 233                     pattern--;
 234                     break;
 235                 }
 236 #endif
 237                 pattern += 1;
 238             }
 239             goto thisCharOK;
 240         }
 241
 242         /* If the next pattern character is backslash, strip it off
 243          * so we do exact matching on the character that follows.
 244          */
 245
 246         if (*pattern == '\\') {
 247             pattern += 1;
 248             if (*pattern == 0) {
 249                 return -1;
 250             }
 251         }
 252
 253         /* There's no special character.  Just make sure that the next
 254          * characters of each string match.
 255          */
 256
 257         if (*pattern != *string) {
 258             return -1;
 259         }
 260
 261         thisCharOK: pattern += 1;
 262         string += 1;
 263         match++;
 264     }
 265 }
 266