chiark - git - mdw - anag/blob - wildcard.c

   1 /* -*-c-*-
   2  *
   3  * Matches wildcard patterns
   4  *
   5  * (c) 2001 Mark Wooding
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Anag: a simple wordgame helper.
  11  *
  12  * Anag is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License as published by
  14  * the Free Software Foundation; either version 2 of the License, or
  15  * (at your option) any later version.
  16  *
  17  * Anag is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with Anag; if not, write to the Free Software Foundation,
  24  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  25  */
  26
  27 /*----- Header files ------------------------------------------------------*/
  28
  29 #include "anag.h"
  30
  31 /*----- Data structures ---------------------------------------------------*/
  32
  33 typedef struct node_wild {
  34   node n;
  35   const char *p;
  36 } node_wild;
  37
  38 /*----- Main code ---------------------------------------------------------*/
  39
  40 /* --- @match@ --- *
  41  *
  42  * Arguments:   @const char *p@ = pointer to pattern string
  43  *              @const char *s@ = string to compare with
  44  *
  45  * Returns:     Nonzero if the pattern matches the string.
  46  *
  47  * Use:         Does simple wildcard matching.  This is quite nasty and more
  48  *              than a little slow.  Supports metacharacters `*', `?' and
  49  *              '['.
  50  */
  51
  52 static int match(const char *p, const char *s)
  53 {
  54   char pch, pche, sch;
  55   int sense;
  56
  57   for (;;) {
  58     pch = *p++;
  59     switch (pch) {
  60
  61       case '?':
  62         /* If there's no character left, then we fail; otherwise consume
  63          * anything and move on.
  64          */
  65
  66         if (!*s++) return (0);
  67         break;
  68
  69       case '*':
  70         /* If there's no more pattern then we win. */
  71         if (!*p) return (1);
  72
  73         /* Try skipping any number of characters from the pattern looking for
  74          * a match.
  75          */
  76         do {
  77           if (match(p, s)) return (1);
  78           s++;
  79         } while (*s);
  80         return (0);
  81
  82       case '[':
  83         /* Character sets.  This is the hard part. */
  84
  85         /* If there is no character left, then we fail. */
  86         if (!*s) return (0);
  87
  88         /* Fetch the string character, and start munching through the
  89          * pattern.
  90          */
  91         sch = *s++;
  92         pch = *p++; sense = 1;
  93
  94         /* Maybe we need to negate. */
  95         if (pch == '^' || pch == '!') { sense = !sense; pch = *p++; }
  96
  97         /* A close bracket here is literal.  Watch for ranges. */
  98         if (pch == ']') {
  99           if (*p == '-' && p[1] && p[1] != ']') {
 100             pche = p[1]; p += 2;
 101             if (pch <= sch && sch <= pche) goto class_match;
 102           } else if (pch == sch) goto class_match;
 103           pch = *p++;
 104         }
 105
 106         /* Work through the other characters and ranges in the set. */
 107         for (;; pch = *p++) {
 108           if (!pch || pch == ']') goto class_nomatch;
 109           if (*p == '-' && p[1] && p[1] != ']') {
 110             pche = p[1]; p += 2;
 111             if (pch <= sch && sch <= pche) goto class_match;
 112           } else if (pch == sch) goto class_match;
 113         }
 114
 115       class_match:
 116         /* Found a match.  Chew through the rest of the pattern. */
 117         if (!sense) return (0);
 118         for (;;) {
 119           pch = *p++; if (!pch) return (0);
 120           if (pch == ']') break;
 121           if (*p == '-' && p[1] && p[1] != ']') p += 2;
 122         }
 123         break;
 124
 125       class_nomatch:
 126         /* Found the end of the set, so it's a mismatch. */
 127         if (sense) return (0);
 128         break;
 129
 130       case '\\':
 131         /* Treat the next thing literally. */
 132         pch = *p++;
 133         /* fall through... */
 134
 135       default:
 136         /* A plain character match.
 137          *
 138          * Trick: If this is the end of the pattern, we expect the end of
 139          * the string.
 140          */
 141
 142         if (pch != *s++) return (0);
 143         if (!pch) return (1);
 144         break;
 145     }
 146   }
 147 }
 148
 149 /* --- Node matcher --- */
 150
 151 static int n_wild(node *nn, const char *p, size_t sz)
 152 {
 153   node_wild *n = (node_wild *)nn;
 154   return (match(n->p, p));
 155 }
 156
 157 /* --- Node creation --- */
 158
 159 node *wildcard(const char *const *av)
 160 {
 161   node_wild *n = xmalloc(sizeof(*n));
 162   n->n.func = n_wild;
 163   n->p = av[0];
 164   return (&n->n);
 165 }
 166
 167 /*----- That's all, folks -------------------------------------------------*/