31c66953a961295706fb0f03b945ec1cc3af420e
[abartlet/samba.git/.git] / source3 / 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, see <http://www.gnu.org/licenses/>.
18 */
19
20 /*
21    This module was originally based on fnmatch.c copyright by the Free
22    Software Foundation. It bears little (if any) resemblence to that
23    code now
24 */
25
26
27 #include "includes.h"
28
29 static int null_match(const smb_ucs2_t *p)
30 {
31         for (;*p;p++) {
32                 if (*p != UCS2_CHAR('*') &&
33                     *p != UCS2_CHAR('<') &&
34                     *p != UCS2_CHAR('"') &&
35                     *p != UCS2_CHAR('>')) return -1;
36         }
37         return 0;
38 }
39
40 /*
41   the max_n structure is purely for efficiency, it doesn't contribute
42   to the matching algorithm except by ensuring that the algorithm does
43   not grow exponentially
44 */
45 struct max_n {
46         const smb_ucs2_t *predot;
47         const smb_ucs2_t *postdot;
48 };
49
50
51 /*
52   p and n are the pattern and string being matched. The max_n array is
53   an optimisation only. The ldot pointer is NULL if the string does
54   not contain a '.', otherwise it points at the last dot in 'n'.
55 */
56 static int ms_fnmatch_core(const smb_ucs2_t *p, const smb_ucs2_t *n,
57                            struct max_n *max_n, const smb_ucs2_t *ldot,
58                            bool is_case_sensitive)
59 {
60         smb_ucs2_t c;
61         int i;
62
63         while ((c = *p++)) {
64                 switch (c) {
65                         /* a '*' matches zero or more characters of any type */
66                 case UCS2_CHAR('*'):
67                         if (max_n->predot && max_n->predot <= n) {
68                                 return null_match(p);
69                         }
70                         for (i=0; n[i]; i++) {
71                                 if (ms_fnmatch_core(p, n+i, max_n+1, ldot, is_case_sensitive) == 0) {
72                                         return 0;
73                                 }
74                         }
75                         if (!max_n->predot || max_n->predot > n) max_n->predot = n;
76                         return null_match(p);
77
78                         /* a '<' matches zero or more characters of
79                            any type, but stops matching at the last
80                            '.' in the string. */
81                 case UCS2_CHAR('<'):
82                         if (max_n->predot && max_n->predot <= n) {
83                                 return null_match(p);
84                         }
85                         if (max_n->postdot && max_n->postdot <= n && n <= ldot) {
86                                 return -1;
87                         }
88                         for (i=0; n[i]; i++) {
89                                 if (ms_fnmatch_core(p, n+i, max_n+1, ldot, is_case_sensitive) == 0) return 0;
90                                 if (n+i == ldot) {
91                                         if (ms_fnmatch_core(p, n+i+1, max_n+1, ldot, is_case_sensitive) == 0) return 0;
92                                         if (!max_n->postdot || max_n->postdot > n) max_n->postdot = n;
93                                         return -1;
94                                 }
95                         }
96                         if (!max_n->predot || max_n->predot > n) max_n->predot = n;
97                         return null_match(p);
98
99                         /* a '?' matches any single character */
100                 case UCS2_CHAR('?'):
101                         if (! *n) {
102                                 return -1;
103                         }
104                         n++;
105                         break;
106
107                         /* a '?' matches any single character */
108                 case UCS2_CHAR('>'):
109                         if (n[0] == UCS2_CHAR('.')) {
110                                 if (! n[1] && null_match(p) == 0) {
111                                         return 0;
112                                 }
113                                 break;
114                         }
115                         if (! *n) return null_match(p);
116                         n++;
117                         break;
118
119                 case UCS2_CHAR('"'):
120                         if (*n == 0 && null_match(p) == 0) {
121                                 return 0;
122                         }
123                         if (*n != UCS2_CHAR('.')) return -1;
124                         n++;
125                         break;
126
127                 default:
128                         if (c != *n) {
129                                 if (is_case_sensitive) {
130                                         return -1;
131                                 }
132                                 if (toupper_m(c) != toupper_m(*n)) {
133                                         return -1;
134                                 }
135                         }
136                         n++;
137                         break;
138                 }
139         }
140
141         if (! *n) {
142                 return 0;
143         }
144
145         return -1;
146 }
147
148 int ms_fnmatch(const char *pattern, const char *string, bool translate_pattern,
149                bool is_case_sensitive)
150 {
151         smb_ucs2_t *p = NULL;
152         smb_ucs2_t *s = NULL;
153         int ret, count, i;
154         struct max_n *max_n = NULL;
155         struct max_n *max_n_free = NULL;
156         struct max_n one_max_n;
157         size_t converted_size;
158
159         if (ISDOTDOT(string)) {
160                 string = ".";
161         }
162
163         if (strpbrk(pattern, "<>*?\"") == NULL) {
164                 /* this is not just an optmisation - it is essential
165                    for LANMAN1 correctness */
166                 if (is_case_sensitive) {
167                         return strcmp(pattern, string);
168                 } else {
169                         return StrCaseCmp(pattern, string);
170                 }
171         }
172
173         if (!push_ucs2_talloc(talloc_tos(), &p, pattern, &converted_size)) {
174                 return -1;
175         }
176
177         if (!push_ucs2_talloc(talloc_tos(), &s, string, &converted_size)) {
178                 TALLOC_FREE(p);
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                 if (count == 1) {
208                         /*
209                          * We're doing this a LOT, so save the effort to allocate
210                          */
211                         ZERO_STRUCT(one_max_n);
212                         max_n = &one_max_n;
213                 }
214                 else {
215                         max_n = SMB_CALLOC_ARRAY(struct max_n, count);
216                         if (!max_n) {
217                                 TALLOC_FREE(p);
218                                 TALLOC_FREE(s);
219                                 return -1;
220                         }
221                         max_n_free = max_n;
222                 }
223         }
224
225         ret = ms_fnmatch_core(p, s, max_n, strrchr_w(s, UCS2_CHAR('.')), is_case_sensitive);
226
227         SAFE_FREE(max_n_free);
228         TALLOC_FREE(p);
229         TALLOC_FREE(s);
230         return ret;
231 }
232
233
234 /* a generic fnmatch function - uses for non-CIFS pattern matching */
235 int gen_fnmatch(const char *pattern, const char *string)
236 {
237         return ms_fnmatch(pattern, string, true, False);
238 }