Sync with FreeBSD. This adds read-only support for zip and ISO9660.
[dragonfly.git] / contrib / bsdtar / matching.c
1 /*-
2  * Copyright (c) 2003-2004 Tim Kientzle
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer
10  *    in this position and unchanged.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18  * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "bsdtar_platform.h"
28 __FBSDID("$FreeBSD: src/usr.bin/tar/matching.c,v 1.9 2005/03/14 00:30:35 kientzle Exp $");
29
30 #include <errno.h>
31 #include <stdlib.h>
32 #include <string.h>
33
34 #include "bsdtar.h"
35
36 struct match {
37         struct match     *next;
38         int               matches;
39         char              pattern[1];
40 };
41
42 struct matching {
43         struct match     *exclusions;
44         int               exclusions_count;
45         struct match     *inclusions;
46         int               inclusions_count;
47         int               inclusions_unmatched_count;
48 };
49
50
51 static void     add_pattern(struct bsdtar *, struct match **list,
52                     const char *pattern);
53 static int      bsdtar_fnmatch(const char *p, const char *s);
54 static void     initialize_matching(struct bsdtar *);
55 static int      match_exclusion(struct match *, const char *pathname);
56 static int      match_inclusion(struct match *, const char *pathname);
57
58 /*
59  * The matching logic here needs to be re-thought.  I started out to
60  * try to mimic gtar's matching logic, but it's not entirely
61  * consistent.  In particular 'tar -t' and 'tar -x' interpret patterns
62  * on the command line as anchored, but --exclude doesn't.
63  */
64
65 /*
66  * Utility functions to manage exclusion/inclusion patterns
67  */
68
69 int
70 exclude(struct bsdtar *bsdtar, const char *pattern)
71 {
72         struct matching *matching;
73
74         if (bsdtar->matching == NULL)
75                 initialize_matching(bsdtar);
76         matching = bsdtar->matching;
77         add_pattern(bsdtar, &(matching->exclusions), pattern);
78         matching->exclusions_count++;
79         return (0);
80 }
81
82 int
83 exclude_from_file(struct bsdtar *bsdtar, const char *pathname)
84 {
85         return (process_lines(bsdtar, pathname, &exclude));
86 }
87
88 int
89 include(struct bsdtar *bsdtar, const char *pattern)
90 {
91         struct matching *matching;
92
93         if (bsdtar->matching == NULL)
94                 initialize_matching(bsdtar);
95         matching = bsdtar->matching;
96         add_pattern(bsdtar, &(matching->inclusions), pattern);
97         matching->inclusions_count++;
98         matching->inclusions_unmatched_count++;
99         return (0);
100 }
101
102 int
103 include_from_file(struct bsdtar *bsdtar, const char *pathname)
104 {
105         return (process_lines(bsdtar, pathname, &include));
106 }
107
108 static void
109 add_pattern(struct bsdtar *bsdtar, struct match **list, const char *pattern)
110 {
111         struct match *match;
112
113         match = malloc(sizeof(*match) + strlen(pattern) + 1);
114         if (match == NULL)
115                 bsdtar_errc(bsdtar, 1, errno, "Out of memory");
116         if (pattern[0] == '/')
117                 pattern++;
118         strcpy(match->pattern, pattern);
119         /* Both "foo/" and "foo" should match "foo/bar". */
120         if (match->pattern[strlen(match->pattern)-1] == '/')
121                 match->pattern[strlen(match->pattern)-1] = '\0';
122         match->next = *list;
123         *list = match;
124         match->matches = 0;
125 }
126
127
128 int
129 excluded(struct bsdtar *bsdtar, const char *pathname)
130 {
131         struct matching *matching;
132         struct match *match;
133         struct match *matched;
134
135         matching = bsdtar->matching;
136         if (matching == NULL)
137                 return (0);
138
139         /* Exclusions take priority */
140         for (match = matching->exclusions; match != NULL; match = match->next){
141                 if (match_exclusion(match, pathname))
142                         return (1);
143         }
144
145         /* Then check for inclusions */
146         matched = NULL;
147         for (match = matching->inclusions; match != NULL; match = match->next){
148                 if (match_inclusion(match, pathname)) {
149                         /*
150                          * If this pattern has never been matched,
151                          * then we're done.
152                          */
153                         if (match->matches == 0) {
154                                 match->matches++;
155                                 matching->inclusions_unmatched_count++;
156                                 return (0);
157                         }
158                         /*
159                          * Otherwise, remember the match but keep checking
160                          * in case we can tick off an unmatched pattern.
161                          */
162                         matched = match;
163                 }
164         }
165         /*
166          * We didn't find a pattern that had never been matched, but
167          * we did find a match, so count it and exit.
168          */
169         if (matched != NULL) {
170                 matched->matches++;
171                 return (0);
172         }
173
174         /* If there were inclusions, default is to exclude. */
175         if (matching->inclusions != NULL)
176             return (1);
177
178         /* No explicit inclusions, default is to match. */
179         return (0);
180 }
181
182 /*
183  * This is a little odd, but it matches the default behavior of
184  * gtar.  In particular, 'a*b' will match 'foo/a1111/222b/bar'
185  *
186  */
187 int
188 match_exclusion(struct match *match, const char *pathname)
189 {
190         const char *p;
191
192         if (*match->pattern == '*' || *match->pattern == '/')
193                 return (bsdtar_fnmatch(match->pattern, pathname) == 0);
194
195         for (p = pathname; p != NULL; p = strchr(p, '/')) {
196                 if (*p == '/')
197                         p++;
198                 if (bsdtar_fnmatch(match->pattern, p) == 0)
199                         return (1);
200         }
201         return (0);
202 }
203
204 /*
205  * Again, mimic gtar:  inclusions are always anchored (have to match
206  * the beginning of the path) even though exclusions are not anchored.
207  */
208 int
209 match_inclusion(struct match *match, const char *pathname)
210 {
211         return (bsdtar_fnmatch(match->pattern, pathname) == 0);
212 }
213
214 void
215 cleanup_exclusions(struct bsdtar *bsdtar)
216 {
217         struct match *p, *q;
218
219         if (bsdtar->matching) {
220                 p = bsdtar->matching->inclusions;
221                 while (p != NULL) {
222                         q = p;
223                         p = p->next;
224                         free(q);
225                 }
226                 p = bsdtar->matching->exclusions;
227                 while (p != NULL) {
228                         q = p;
229                         p = p->next;
230                         free(q);
231                 }
232                 free(bsdtar->matching);
233         }
234 }
235
236 static void
237 initialize_matching(struct bsdtar *bsdtar)
238 {
239         bsdtar->matching = malloc(sizeof(*bsdtar->matching));
240         if (bsdtar->matching == NULL)
241                 bsdtar_errc(bsdtar, 1, errno, "No memory");
242         memset(bsdtar->matching, 0, sizeof(*bsdtar->matching));
243 }
244
245 int
246 unmatched_inclusions(struct bsdtar *bsdtar)
247 {
248         struct matching *matching;
249
250         matching = bsdtar->matching;
251         if (matching == NULL)
252                 return (0);
253         return (matching->inclusions_unmatched_count);
254 }
255
256
257
258 #if defined(HAVE_FNMATCH) && defined(HAVE_FNM_LEADING_DIR)
259
260 /* Use system fnmatch() if it suits our needs. */
261 /* On Linux, _GNU_SOURCE must be defined to get FNM_LEADING_DIR. */
262 #define _GNU_SOURCE
263 #include <fnmatch.h>
264 static int
265 bsdtar_fnmatch(const char *pattern, const char *string)
266 {
267         return (fnmatch(pattern, string, FNM_LEADING_DIR));
268 }
269
270 #else
271 /*
272  * The following was hacked from BSD C library
273  * code:  src/lib/libc/gen/fnmatch.c,v 1.15 2002/02/01
274  *
275  * In particular, most of the flags were ripped out: this always
276  * behaves like FNM_LEADING_DIR is set and other flags specified
277  * by POSIX are unset.
278  *
279  * Normally, I would not conditionally compile something like this: If
280  * I have to support it anyway, everyone may as well use it. ;-)
281  * However, the full POSIX spec for fnmatch() includes a lot of
282  * advanced character handling that I'm not ready to put in here, so
283  * it's probably best if people use a local version when it's available.
284  */
285
286 /*
287  * Copyright (c) 1989, 1993, 1994
288  *      The Regents of the University of California.  All rights reserved.
289  *
290  * This code is derived from software contributed to Berkeley by
291  * Guido van Rossum.
292  *
293  * Redistribution and use in source and binary forms, with or without
294  * modification, are permitted provided that the following conditions
295  * are met:
296  * 1. Redistributions of source code must retain the above copyright
297  *    notice, this list of conditions and the following disclaimer.
298  * 2. Redistributions in binary form must reproduce the above copyright
299  *    notice, this list of conditions and the following disclaimer in the
300  *    documentation and/or other materials provided with the distribution.
301  * 4. Neither the name of the University nor the names of its contributors
302  *    may be used to endorse or promote products derived from this software
303  *    without specific prior written permission.
304  *
305  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
306  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
307  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
308  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
309  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
310  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
311  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
312  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
313  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
314  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
315  * SUCH DAMAGE.
316  */
317
318 static int
319 bsdtar_fnmatch(const char *pattern, const char *string)
320 {
321         const char *saved_pattern;
322         int negate, matched;
323         char c;
324
325         for (;;) {
326                 switch (c = *pattern++) {
327                 case '\0':
328                         if (*string == '/' || *string == '\0')
329                                 return (0);
330                         return (1);
331                 case '?':
332                         if (*string == '\0')
333                                 return (1);
334                         ++string;
335                         break;
336                 case '*':
337                         c = *pattern;
338                         /* Collapse multiple stars. */
339                         while (c == '*')
340                                 c = *++pattern;
341
342                         /* Optimize for pattern with * at end. */
343                         if (c == '\0')
344                                 return (0);
345
346                         /* General case, use recursion. */
347                         while (*string != '\0') {
348                                 if (!bsdtar_fnmatch(pattern, string))
349                                         return (0);
350                                 ++string;
351                         }
352                         return (1);
353                 case '[':
354                         if (*string == '\0')
355                                 return (1);
356                         saved_pattern = pattern;
357                         if (*pattern == '!' || *pattern == '^') {
358                                 negate = 1;
359                                 ++pattern;
360                         } else
361                                 negate = 0;
362                         matched = 0;
363                         c = *pattern++;
364                         do {
365                                 if (c == '\\')
366                                         c = *pattern++;
367                                 if (c == '\0') {
368                                         pattern = saved_pattern;
369                                         c = '[';
370                                         goto norm;
371                                 }
372                                 if (*pattern == '-') {
373                                         char c2 = *(pattern + 1);
374                                         if (c2 == '\0') {
375                                                 pattern = saved_pattern;
376                                                 c = '[';
377                                                 goto norm;
378                                         }
379                                         if (c2 == ']') {
380                                                 /* [a-] is not a range. */
381                                                 if (c == *string
382                                                     || '-' == *string)
383                                                         matched = 1;
384                                                 pattern ++;
385                                         } else {
386                                                 if (c <= *string
387                                                     && *string <= c2)
388                                                         matched = 1;
389                                                 pattern += 2;
390                                         }
391                                 } else if (c == *string)
392                                         matched = 1;
393                                 c = *pattern++;
394                         } while (c != ']');
395                         if (matched == negate)
396                                 return (1);
397                         ++string;
398                         break;
399                 case '\\':
400                         if ((c = *pattern++) == '\0') {
401                                 c = '\\';
402                                 --pattern;
403                         }
404                         /* FALLTHROUGH */
405                 default:
406                 norm:
407                         if (c != *string)
408                                 return (1);
409                         string++;
410                         break;
411                 }
412         }
413         /* NOTREACHED */
414 }
415
416 #endif