Merge from vendor branch CVS:
[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.7 2004/07/24 22:13:44 kientzle Exp $");
29
30 #include <errno.h>
31 #include <fnmatch.h>
32 #include <stdlib.h>
33 #include <string.h>
34
35 #include "bsdtar.h"
36
37 struct match {
38         struct match     *next;
39         int               matches;
40         char              pattern[1];
41 };
42
43 struct matching {
44         struct match     *exclusions;
45         int               exclusions_count;
46         struct match     *inclusions;
47         int               inclusions_count;
48         int               inclusions_unmatched_count;
49 };
50
51
52 static void     add_pattern(struct bsdtar *, struct match **list,
53                     const char *pattern);
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  * XXX TODO: fnmatch isn't the most portable thing around, and even
187  * worse, FNM_LEADING_DIR is a non-POSIX extension.  <sigh> Thus, the
188  * following two functions need to eventually be replaced with code
189  * that does not rely on fnmatch().
190  */
191 int
192 match_exclusion(struct match *match, const char *pathname)
193 {
194         const char *p;
195
196         if (*match->pattern == '*' || *match->pattern == '/')
197                 return (fnmatch(match->pattern, pathname, FNM_LEADING_DIR) == 0);
198
199         for (p = pathname; p != NULL; p = strchr(p, '/')) {
200                 if (*p == '/')
201                         p++;
202                 if (fnmatch(match->pattern, p, FNM_LEADING_DIR) == 0)
203                         return (1);
204         }
205         return (0);
206 }
207
208 /*
209  * Again, mimic gtar:  inclusions are always anchored (have to match
210  * the beginning of the path) even though exclusions are not anchored.
211  */
212 int
213 match_inclusion(struct match *match, const char *pathname)
214 {
215         return (fnmatch(match->pattern, pathname, FNM_LEADING_DIR) == 0);
216 }
217
218 void
219 cleanup_exclusions(struct bsdtar *bsdtar)
220 {
221         struct match *p, *q;
222
223         if (bsdtar->matching) {
224                 p = bsdtar->matching->inclusions;
225                 while (p != NULL) {
226                         q = p;
227                         p = p->next;
228                         free(q);
229                 }
230                 p = bsdtar->matching->exclusions;
231                 while (p != NULL) {
232                         q = p;
233                         p = p->next;
234                         free(q);
235                 }
236                 free(bsdtar->matching);
237         }
238 }
239
240 static void
241 initialize_matching(struct bsdtar *bsdtar)
242 {
243         bsdtar->matching = malloc(sizeof(*bsdtar->matching));
244         if (bsdtar->matching == NULL)
245                 bsdtar_errc(bsdtar, 1, errno, "No memory");
246         memset(bsdtar->matching, 0, sizeof(*bsdtar->matching));
247 }
248
249 int
250 unmatched_inclusions(struct bsdtar *bsdtar)
251 {
252         struct matching *matching;
253
254         matching = bsdtar->matching;
255         if (matching == NULL)
256                 return (0);
257         return (matching->inclusions_unmatched_count);
258 }