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