238d793b73409d1812a965c4f0a89fa687c32364
[tprouty/samba.git] / source / lib / 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 3 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 #include "includes.h"
29
30 static int null_match(const smb_ucs2_t *p)
31 {
32         for (;*p;p++) {
33                 if (*p != UCS2_CHAR('*') &&
34                     *p != UCS2_CHAR('<') &&
35                     *p != UCS2_CHAR('"') &&
36                     *p != UCS2_CHAR('>')) return -1;
37         }
38         return 0;
39 }
40
41 /*
42   the max_n structure is purely for efficiency, it doesn't contribute
43   to the matching algorithm except by ensuring that the algorithm does
44   not grow exponentially
45 */
46 struct max_n {
47         const smb_ucs2_t *predot;
48         const smb_ucs2_t *postdot;
49 };
50
51
52 /*
53   p and n are the pattern and string being matched. The max_n array is
54   an optimisation only. The ldot pointer is NULL if the string does
55   not contain a '.', otherwise it points at the last dot in 'n'.
56 */
57 static int ms_fnmatch_core(const smb_ucs2_t *p, const smb_ucs2_t *n, 
58                            struct max_n *max_n, const smb_ucs2_t *ldot,
59                            BOOL is_case_sensitive)
60 {
61         smb_ucs2_t c;
62         int i;
63
64         while ((c = *p++)) {
65                 switch (c) {
66                         /* a '*' matches zero or more characters of any type */
67                 case UCS2_CHAR('*'):
68                         if (max_n->predot && max_n->predot <= n) {
69                                 return null_match(p);
70                         }
71                         for (i=0; n[i]; i++) {
72                                 if (ms_fnmatch_core(p, n+i, max_n+1, ldot, is_case_sensitive) == 0) {
73                                         return 0;
74                                 }
75                         }
76                         if (!max_n->predot || max_n->predot > n) max_n->predot = n;
77                         return null_match(p);
78
79                         /* a '<' matches zero or more characters of
80                            any type, but stops matching at the last
81                            '.' in the string. */
82                 case UCS2_CHAR('<'):
83                         if (max_n->predot && max_n->predot <= n) {
84                                 return null_match(p);
85                         }
86                         if (max_n->postdot && max_n->postdot <= n && n <= ldot) {
87                                 return -1;
88                         }
89                         for (i=0; n[i]; i++) {
90                                 if (ms_fnmatch_core(p, n+i, max_n+1, ldot, is_case_sensitive) == 0) return 0;
91                                 if (n+i == ldot) {
92                                         if (ms_fnmatch_core(p, n+i+1, max_n+1, ldot, is_case_sensitive) == 0) return 0;
93                                         if (!max_n->postdot || max_n->postdot > n) max_n->postdot = n;
94                                         return -1;
95                                 }
96                         }
97                         if (!max_n->predot || max_n->predot > n) max_n->predot = n;
98                         return null_match(p);
99
100                         /* a '?' matches any single character */
101                 case UCS2_CHAR('?'):
102                         if (! *n) {
103                                 return -1;
104                         }
105                         n++;
106                         break;
107
108                         /* a '?' matches any single character */
109                 case UCS2_CHAR('>'):
110                         if (n[0] == UCS2_CHAR('.')) {
111                                 if (! n[1] && null_match(p) == 0) {
112                                         return 0;
113                                 }
114                                 break;
115                         }
116                         if (! *n) return null_match(p);
117                         n++;
118                         break;
119
120                 case UCS2_CHAR('"'):
121                         if (*n == 0 && null_match(p) == 0) {
122                                 return 0;
123                         }
124                         if (*n != UCS2_CHAR('.')) return -1;
125                         n++;
126                         break;
127
128                 default:
129                         if (c != *n) {
130                                 if (is_case_sensitive) {
131                                         return -1;
132                                 }
133                                 if (toupper_w(c) != toupper_w(*n)) {
134                                         return -1;
135                                 }
136                         }
137                         n++;
138                         break;
139                 }
140         }
141         
142         if (! *n) {
143                 return 0;
144         }
145         
146         return -1;
147 }
148
149 int ms_fnmatch(const char *pattern, const char *string, BOOL translate_pattern,
150                BOOL is_case_sensitive)
151 {
152         wpstring p, s;
153         int ret, count, i;
154         struct max_n *max_n = NULL;
155
156         if (strcmp(string, "..") == 0) {
157                 string = ".";
158         }
159
160         if (strpbrk(pattern, "<>*?\"") == NULL) {
161                 /* this is not just an optmisation - it is essential
162                    for LANMAN1 correctness */
163                 if (is_case_sensitive) {
164                         return strcmp(pattern, string);
165                 } else {
166                         return StrCaseCmp(pattern, string);
167                 }
168         }
169
170         if (push_ucs2(NULL, p, pattern, sizeof(p), STR_TERMINATE) == (size_t)-1) {
171                 /* Not quite the right answer, but finding the right one
172                   under this failure case is expensive, and it's pretty close */
173                 return -1;
174         }
175
176         if (push_ucs2(NULL, s, string, sizeof(s), STR_TERMINATE) == (size_t)-1) {
177                 /* Not quite the right answer, but finding the right one
178                    under this failure case is expensive, and it's pretty close */
179                 return -1;
180         }
181
182         if (translate_pattern) {
183                 /*
184                   for older negotiated protocols it is possible to
185                   translate the pattern to produce a "new style"
186                   pattern that exactly matches w2k behaviour
187                 */
188                 for (i=0;p[i];i++) {
189                         if (p[i] == UCS2_CHAR('?')) {
190                                 p[i] = UCS2_CHAR('>');
191                         } else if (p[i] == UCS2_CHAR('.') && 
192                                    (p[i+1] == UCS2_CHAR('?') || 
193                                     p[i+1] == UCS2_CHAR('*') ||
194                                     p[i+1] == 0)) {
195                                 p[i] = UCS2_CHAR('"');
196                         } else if (p[i] == UCS2_CHAR('*') && p[i+1] == UCS2_CHAR('.')) {
197                                 p[i] = UCS2_CHAR('<');
198                         }
199                 }
200         }
201
202         for (count=i=0;p[i];i++) {
203                 if (p[i] == UCS2_CHAR('*') || p[i] == UCS2_CHAR('<')) count++;
204         }
205
206         if (count != 0) {
207                 max_n = SMB_CALLOC_ARRAY(struct max_n, count);
208                 if (!max_n) {
209                         return -1;
210                 }
211         }
212
213         ret = ms_fnmatch_core(p, s, max_n, strrchr_w(s, UCS2_CHAR('.')), is_case_sensitive);
214
215         if (max_n) {
216                 free(max_n);
217         }
218
219         return ret;
220 }
221
222
223 /* a generic fnmatch function - uses for non-CIFS pattern matching */
224 int gen_fnmatch(const char *pattern, const char *string)
225 {
226         return ms_fnmatch(pattern, string, PROTOCOL_NT1, False);
227 }