source/lib/util/ms_fnmatch.c

   1 /*
   2    Unix SMB/CIFS implementation.
   3    filename matching routine
   4    Copyright (C) Andrew Tridgell 1992-2004
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software
  18    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19 */
  20
  21 /*
  22    This module was originally based on fnmatch.c copyright by the Free
  23    Software Foundation. It bears little (if any) resemblence to that
  24    code now
  25 */
  26
  27 /**
  28  * @file
  29  * @brief MS-style Filename matching
  30  */
  31
  32 #include "includes.h"
  33
  34 static int null_match(const char *p)
  35 {
  36         for (;*p;p++) {
  37                 if (*p != '*' &&
  38                     *p != '<' &&
  39                     *p != '"' &&
  40                     *p != '>') return -1;
  41         }
  42         return 0;
  43 }
  44
  45 /*
  46   the max_n structure is purely for efficiency, it doesn't contribute
  47   to the matching algorithm except by ensuring that the algorithm does
  48   not grow exponentially
  49 */
  50 struct max_n {
  51         const char *predot;
  52         const char *postdot;
  53 };
  54
  55
  56 /*
  57   p and n are the pattern and string being matched. The max_n array is
  58   an optimisation only. The ldot pointer is NULL if the string does
  59   not contain a '.', otherwise it points at the last dot in 'n'.
  60 */
  61 static int ms_fnmatch_core(const char *p, const char *n,
  62                            struct max_n *max_n, const char *ldot)
  63 {
  64         codepoint_t c, c2;
  65         int i;
  66         size_t size, size_n;
  67
  68         while ((c = next_codepoint(p, &size))) {
  69                 p += size;
  70
  71                 switch (c) {
  72                 case '*':
  73                         /* a '*' matches zero or more characters of any type */
  74                         if (max_n->predot && max_n->predot <= n) {
  75                                 return null_match(p);
  76                         }
  77                         for (i=0; n[i]; i += size_n) {
  78                                 next_codepoint(n+i, &size_n);
  79                                 if (ms_fnmatch_core(p, n+i, max_n+1, ldot) == 0) {
  80                                         return 0;
  81                                 }
  82                         }
  83                         if (!max_n->predot || max_n->predot > n) max_n->predot = n;
  84                         return null_match(p);
  85
  86                 case '<':
  87                         /* a '<' matches zero or more characters of
  88                            any type, but stops matching at the last
  89                            '.' in the string. */
  90                         if (max_n->predot && max_n->predot <= n) {
  91                                 return null_match(p);
  92                         }
  93                         if (max_n->postdot && max_n->postdot <= n && n <= ldot) {
  94                                 return -1;
  95                         }
  96                         for (i=0; n[i]; i += size_n) {
  97                                 next_codepoint(n+i, &size_n);
  98                                 if (ms_fnmatch_core(p, n+i, max_n+1, ldot) == 0) return 0;
  99                                 if (n+i == ldot) {
 100                                         if (ms_fnmatch_core(p, n+i+size_n, max_n+1, ldot) == 0) return 0;
 101                                         if (!max_n->postdot || max_n->postdot > n) max_n->postdot = n;
 102                                         return -1;
 103                                 }
 104                         }
 105                         if (!max_n->predot || max_n->predot > n) max_n->predot = n;
 106                         return null_match(p);
 107
 108                 case '?':
 109                         /* a '?' matches any single character */
 110                         if (! *n) {
 111                                 return -1;
 112                         }
 113                         next_codepoint(n, &size_n);
 114                         n += size_n;
 115                         break;
 116
 117                 case '>':
 118                         /* a '?' matches any single character, but
 119                            treats '.' specially */
 120                         if (n[0] == '.') {
 121                                 if (! n[1] && null_match(p) == 0) {
 122                                         return 0;
 123                                 }
 124                                 break;
 125                         }
 126                         if (! *n) return null_match(p);
 127                         next_codepoint(n, &size_n);
 128                         n += size_n;
 129                         break;
 130
 131                 case '"':
 132                         /* a bit like a soft '.' */
 133                         if (*n == 0 && null_match(p) == 0) {
 134                                 return 0;
 135                         }
 136                         if (*n != '.') return -1;
 137                         next_codepoint(n, &size_n);
 138                         n += size_n;
 139                         break;
 140
 141                 default:
 142                         c2 = next_codepoint(n, &size_n);
 143                         if (c != c2 && codepoint_cmpi(c, c2) != 0) {
 144                                 return -1;
 145                         }
 146                         n += size_n;
 147                         break;
 148                 }
 149         }
 150
 151         if (! *n) {
 152                 return 0;
 153         }
 154
 155         return -1;
 156 }
 157
 158 int ms_fnmatch(const char *pattern, const char *string, enum protocol_types protocol)
 159 {
 160         int ret, count, i;
 161         struct max_n *max_n = NULL;
 162
 163         if (strcmp(string, "..") == 0) {
 164                 string = ".";
 165         }
 166
 167         if (strpbrk(pattern, "<>*?\"") == NULL) {
 168                 /* this is not just an optimisation - it is essential
 169                    for LANMAN1 correctness */
 170                 return strcasecmp_m(pattern, string);
 171         }
 172
 173         if (protocol <= PROTOCOL_LANMAN2) {
 174                 char *p = talloc_strdup(NULL, pattern);
 175                 if (p == NULL) {
 176                         return -1;
 177                 }
 178                 /*
 179                   for older negotiated protocols it is possible to
 180                   translate the pattern to produce a "new style"
 181                   pattern that exactly matches w2k behaviour
 182                 */
 183                 for (i=0;p[i];i++) {
 184                         if (p[i] == '?') {
 185                                 p[i] = '>';
 186                         } else if (p[i] == '.' &&
 187                                    (p[i+1] == '?' ||
 188                                     p[i+1] == '*' ||
 189                                     p[i+1] == 0)) {
 190                                 p[i] = '"';
 191                         } else if (p[i] == '*' &&
 192                                    p[i+1] == '.') {
 193                                 p[i] = '<';
 194                         }
 195                 }
 196                 ret = ms_fnmatch(p, string, PROTOCOL_NT1);
 197                 talloc_free(p);
 198                 return ret;
 199         }
 200
 201         for (count=i=0;pattern[i];i++) {
 202                 if (pattern[i] == '*' || pattern[i] == '<') count++;
 203         }
 204
 205         max_n = talloc_array(NULL, struct max_n, count);
 206         if (!max_n) {
 207                 return -1;
 208         }
 209         memset(max_n, 0, sizeof(struct max_n) * count);
 210
 211         ret = ms_fnmatch_core(pattern, string, max_n, strrchr(string, '.'));
 212
 213         talloc_free(max_n);
 214
 215         return ret;
 216 }
 217
 218
 219 /** a generic fnmatch function - uses for non-CIFS pattern matching */
 220 int gen_fnmatch(const char *pattern, const char *string)
 221 {
 222         return ms_fnmatch(pattern, string, PROTOCOL_NT1);
 223 }