1 // Copyright 2011 Google Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * 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 // * Neither the name of Google Inc. nor the names of its contributors
14 // may be used to endorse or promote products derived from this software
15 // without specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29 #include "engine/filters.hpp"
30
31 #include <algorithm>
32 #include <stdexcept>
33
34 #include "engine/test_case.hpp"
35 #include "utils/format/macros.hpp"
36 #include "utils/fs/exceptions.hpp"
37 #include "utils/logging/macros.hpp"
38 #include "utils/optional.ipp"
39 #include "utils/sanity.hpp"
40
41 namespace fs = utils::fs;
42
43 using utils::none;
44 using utils::optional;
45
46
47 /// Constructs a filter.
48 ///
49 /// \param test_program_ The name of the test program or of the subdirectory to
50 /// match.
51 /// \param test_case_ The name of the test case to match.
test_filter(const fs::path & test_program_,const std::string & test_case_)52 engine::test_filter::test_filter(const fs::path& test_program_,
53 const std::string& test_case_) :
54 test_program(test_program_),
55 test_case(test_case_)
56 {
57 }
58
59
60 /// Parses a user-provided test filter.
61 ///
62 /// \param str The user-provided string representing a filter for tests. Must
63 /// be of the form <test_program%gt;[:<test_case%gt;].
64 ///
65 /// \return The parsed filter.
66 ///
67 /// \throw std::runtime_error If the provided filter is invalid.
68 engine::test_filter
parse(const std::string & str)69 engine::test_filter::parse(const std::string& str)
70 {
71 if (str.empty())
72 throw std::runtime_error("Test filter cannot be empty");
73
74 const std::string::size_type pos = str.find(':');
75 if (pos == 0)
76 throw std::runtime_error(F("Program name component in '%s' is empty")
77 % str);
78 if (pos == str.length() - 1)
79 throw std::runtime_error(F("Test case component in '%s' is empty")
80 % str);
81
82 try {
83 const fs::path test_program_(str.substr(0, pos));
84 if (test_program_.is_absolute())
85 throw std::runtime_error(F("Program name '%s' must be relative "
86 "to the test suite, not absolute") %
87 test_program_.str());
88 if (pos == std::string::npos) {
89 LD(F("Parsed user filter '%s': test program '%s', no test case") %
90 str % test_program_.str());
91 return test_filter(test_program_, "");
92 } else {
93 const std::string test_case_(str.substr(pos + 1));
94 LD(F("Parsed user filter '%s': test program '%s', test case '%s'") %
95 str % test_program_.str() % test_case_);
96 return test_filter(test_program_, test_case_);
97 }
98 } catch (const fs::error& e) {
99 throw std::runtime_error(F("Invalid path in filter '%s': %s") % str %
100 e.what());
101 }
102 }
103
104
105 /// Formats a filter for user presentation.
106 ///
107 /// \return A user-friendly string representing the filter. Note that this does
108 /// not necessarily match the string the user provided: in particular, the path
109 /// may have been internally normalized.
110 std::string
str(void) const111 engine::test_filter::str(void) const
112 {
113 if (!test_case.empty())
114 return F("%s:%s") % test_program % test_case;
115 else
116 return test_program.str();
117 }
118
119
120 /// Checks if this filter contains another.
121 ///
122 /// \param other The filter to compare to.
123 ///
124 /// \return True if this filter contains the other filter or if they are equal.
125 bool
contains(const test_filter & other) const126 engine::test_filter::contains(const test_filter& other) const
127 {
128 if (*this == other)
129 return true;
130 else
131 return test_case.empty() && test_program.is_parent_of(
132 other.test_program);
133 }
134
135
136 /// Checks if this filter matches a given test program name or subdirectory.
137 ///
138 /// \param test_program_ The test program to compare to.
139 ///
140 /// \return Whether the filter matches the test program. This is a superset of
141 /// matches_test_case.
142 bool
matches_test_program(const fs::path & test_program_) const143 engine::test_filter::matches_test_program(const fs::path& test_program_) const
144 {
145 if (test_program == test_program_)
146 return true;
147 else {
148 // Check if the filter matches a subdirectory of the test program.
149 // The test case must be empty because we don't want foo:bar to match
150 // foo/baz.
151 return (test_case.empty() && test_program.is_parent_of(test_program_));
152 }
153 }
154
155
156 /// Checks if this filter matches a given test case identifier.
157 ///
158 /// \param test_program_ The test program to compare to.
159 /// \param test_case_ The test case to compare to.
160 ///
161 /// \return Whether the filter matches the test case.
162 bool
matches_test_case(const fs::path & test_program_,const std::string & test_case_) const163 engine::test_filter::matches_test_case(const fs::path& test_program_,
164 const std::string& test_case_) const
165 {
166 if (matches_test_program(test_program_)) {
167 return test_case.empty() || test_case == test_case_;
168 } else
169 return false;
170 }
171
172
173 /// Less-than comparison for sorting purposes.
174 ///
175 /// \param other The filter to compare to.
176 ///
177 /// \return True if this filter sorts before the other filter.
178 bool
operator <(const test_filter & other) const179 engine::test_filter::operator<(const test_filter& other) const
180 {
181 return (
182 test_program < other.test_program ||
183 (test_program == other.test_program && test_case < other.test_case));
184 }
185
186
187 /// Equality comparison.
188 ///
189 /// \param other The filter to compare to.
190 ///
191 /// \return True if this filter is equal to the other filter.
192 bool
operator ==(const test_filter & other) const193 engine::test_filter::operator==(const test_filter& other) const
194 {
195 return test_program == other.test_program && test_case == other.test_case;
196 }
197
198
199 /// Non-equality comparison.
200 ///
201 /// \param other The filter to compare to.
202 ///
203 /// \return True if this filter is different than the other filter.
204 bool
operator !=(const test_filter & other) const205 engine::test_filter::operator!=(const test_filter& other) const
206 {
207 return !(*this == other);
208 }
209
210
211 /// Constructs a new set of filters.
212 ///
213 /// \param filters_ The filters themselves; if empty, no filters are applied.
test_filters(const std::set<test_filter> & filters_)214 engine::test_filters::test_filters(const std::set< test_filter >& filters_) :
215 _filters(filters_)
216 {
217 }
218
219
220 /// Checks if a given test program matches the set of filters.
221 ///
222 /// This is provided as an optimization only, and the results of this function
223 /// are less specific than those of match_test_case. Checking for the matching
224 /// of a test program should be done before loading the list of test cases from
225 /// a program, so as to avoid the delay in executing the test program, but
226 /// match_test_case must still be called afterwards.
227 ///
228 /// \param name The test program to check against the filters.
229 ///
230 /// \return True if the provided identifier matches any filter.
231 bool
match_test_program(const fs::path & name) const232 engine::test_filters::match_test_program(const fs::path& name) const
233 {
234 if (_filters.empty())
235 return true;
236
237 bool matches = false;
238 for (std::set< test_filter >::const_iterator iter = _filters.begin();
239 !matches && iter != _filters.end(); iter++) {
240 matches = (*iter).matches_test_program(name);
241 }
242 return matches;
243 }
244
245
246 /// Checks if a given test case identifier matches the set of filters.
247 ///
248 /// \param test_program The test program to check against the filters.
249 /// \param test_case The test case to check against the filters.
250 ///
251 /// \return A boolean indicating if the test case is matched by any filter and,
252 /// if true, a string containing the filter name. The string is empty when
253 /// there are no filters defined.
254 engine::test_filters::match
match_test_case(const fs::path & test_program,const std::string & test_case) const255 engine::test_filters::match_test_case(const fs::path& test_program,
256 const std::string& test_case) const
257 {
258 if (_filters.empty()) {
259 INV(match_test_program(test_program));
260 return match(true, none);
261 }
262
263 optional< test_filter > found = none;
264 for (std::set< test_filter >::const_iterator iter = _filters.begin();
265 !found && iter != _filters.end(); iter++) {
266 if ((*iter).matches_test_case(test_program, test_case))
267 found = *iter;
268 }
269 INV(!found || match_test_program(test_program));
270 return match(static_cast< bool >(found), found);
271 }
272
273
274 /// Calculates the filters that have not matched any tests.
275 ///
276 /// \param matched The filters that did match some tests. This must be a subset
277 /// of the filters held by this object.
278 ///
279 /// \return The set of filters that have not been used.
280 std::set< engine::test_filter >
difference(const std::set<test_filter> & matched) const281 engine::test_filters::difference(const std::set< test_filter >& matched) const
282 {
283 PRE(std::includes(_filters.begin(), _filters.end(),
284 matched.begin(), matched.end()));
285
286 std::set< test_filter > filters;
287 std::set_difference(_filters.begin(), _filters.end(),
288 matched.begin(), matched.end(),
289 std::inserter(filters, filters.begin()));
290 return filters;
291 }
292
293
294 /// Checks if a collection of filters is disjoint.
295 ///
296 /// \param filters The filters to check.
297 ///
298 /// \throw std::runtime_error If the filters are not disjoint.
299 void
check_disjoint_filters(const std::set<engine::test_filter> & filters)300 engine::check_disjoint_filters(const std::set< engine::test_filter >& filters)
301 {
302 // Yes, this is an O(n^2) algorithm. However, we can assume that the number
303 // of test filters (which are provided by the user on the command line) on a
304 // particular run is in the order of tens, and thus this should not cause
305 // any serious performance trouble.
306 for (std::set< test_filter >::const_iterator i1 = filters.begin();
307 i1 != filters.end(); i1++) {
308 for (std::set< test_filter >::const_iterator i2 = filters.begin();
309 i2 != filters.end(); i2++) {
310 const test_filter& filter1 = *i1;
311 const test_filter& filter2 = *i2;
312
313 if (i1 != i2 && filter1.contains(filter2)) {
314 throw std::runtime_error(
315 F("Filters '%s' and '%s' are not disjoint") %
316 filter1.str() % filter2.str());
317 }
318 }
319 }
320 }
321
322
323 /// Constructs a filters_state instance.
324 ///
325 /// \param filters_ The set of filters to track.
filters_state(const std::set<engine::test_filter> & filters_)326 engine::filters_state::filters_state(
327 const std::set< engine::test_filter >& filters_) :
328 _filters(test_filters(filters_))
329 {
330 }
331
332
333 /// Checks whether these filters match the given test program.
334 ///
335 /// \param test_program The test program to match against.
336 ///
337 /// \return True if these filters match the given test program name.
338 bool
match_test_program(const fs::path & test_program) const339 engine::filters_state::match_test_program(const fs::path& test_program) const
340 {
341 return _filters.match_test_program(test_program);
342 }
343
344
345 /// Checks whether these filters match the given test case.
346 ///
347 /// \param test_program The test program to match against.
348 /// \param test_case The test case to match against.
349 ///
350 /// \return True if these filters match the given test case identifier.
351 bool
match_test_case(const fs::path & test_program,const std::string & test_case)352 engine::filters_state::match_test_case(const fs::path& test_program,
353 const std::string& test_case)
354 {
355 engine::test_filters::match match = _filters.match_test_case(
356 test_program, test_case);
357 if (match.first && match.second)
358 _used_filters.insert(match.second.get());
359 return match.first;
360 }
361
362
363 /// Calculates the unused filters in this set.
364 ///
365 /// \return Returns the set of filters that have not matched any tests. This
366 /// information is useful to report usage errors to the user.
367 std::set< engine::test_filter >
unused(void) const368 engine::filters_state::unused(void) const
369 {
370 return _filters.difference(_used_filters);
371 }
372