1 // Copyright 2011 The Kyua Authors. 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 "utils/format/macros.hpp" 35 #include "utils/fs/exceptions.hpp" 36 #include "utils/logging/macros.hpp" 37 #include "utils/optional.ipp" 38 #include "utils/sanity.hpp" 39 40 namespace fs = utils::fs; 41 42 using utils::none; 43 using utils::optional; 44 45 46 /// Constructs a filter. 47 /// 48 /// \param test_program_ The name of the test program or of the subdirectory to 49 /// match. 50 /// \param test_case_ The name of the test case to match. 51 engine::test_filter::test_filter(const fs::path& test_program_, 52 const std::string& test_case_) : 53 test_program(test_program_), 54 test_case(test_case_) 55 { 56 } 57 58 59 /// Parses a user-provided test filter. 60 /// 61 /// \param str The user-provided string representing a filter for tests. Must 62 /// be of the form <test_program%gt;[:<test_case%gt;]. 63 /// 64 /// \return The parsed filter. 65 /// 66 /// \throw std::runtime_error If the provided filter is invalid. 67 engine::test_filter 68 engine::test_filter::parse(const std::string& str) 69 { 70 if (str.empty()) 71 throw std::runtime_error("Test filter cannot be empty"); 72 73 const std::string::size_type pos = str.find(':'); 74 if (pos == 0) 75 throw std::runtime_error(F("Program name component in '%s' is empty") 76 % str); 77 if (pos == str.length() - 1) 78 throw std::runtime_error(F("Test case component in '%s' is empty") 79 % str); 80 81 try { 82 const fs::path test_program_(str.substr(0, pos)); 83 if (test_program_.is_absolute()) 84 throw std::runtime_error(F("Program name '%s' must be relative " 85 "to the test suite, not absolute") % 86 test_program_.str()); 87 if (pos == std::string::npos) { 88 LD(F("Parsed user filter '%s': test program '%s', no test case") % 89 str % test_program_.str()); 90 return test_filter(test_program_, ""); 91 } else { 92 const std::string test_case_(str.substr(pos + 1)); 93 LD(F("Parsed user filter '%s': test program '%s', test case '%s'") % 94 str % test_program_.str() % test_case_); 95 return test_filter(test_program_, test_case_); 96 } 97 } catch (const fs::error& e) { 98 throw std::runtime_error(F("Invalid path in filter '%s': %s") % str % 99 e.what()); 100 } 101 } 102 103 104 /// Formats a filter for user presentation. 105 /// 106 /// \return A user-friendly string representing the filter. Note that this does 107 /// not necessarily match the string the user provided: in particular, the path 108 /// may have been internally normalized. 109 std::string 110 engine::test_filter::str(void) const 111 { 112 if (!test_case.empty()) 113 return F("%s:%s") % test_program % test_case; 114 else 115 return test_program.str(); 116 } 117 118 119 /// Checks if this filter contains another. 120 /// 121 /// \param other The filter to compare to. 122 /// 123 /// \return True if this filter contains the other filter or if they are equal. 124 bool 125 engine::test_filter::contains(const test_filter& other) const 126 { 127 if (*this == other) 128 return true; 129 else 130 return test_case.empty() && test_program.is_parent_of( 131 other.test_program); 132 } 133 134 135 /// Checks if this filter matches a given test program name or subdirectory. 136 /// 137 /// \param test_program_ The test program to compare to. 138 /// 139 /// \return Whether the filter matches the test program. This is a superset of 140 /// matches_test_case. 141 bool 142 engine::test_filter::matches_test_program(const fs::path& test_program_) const 143 { 144 if (test_program == test_program_) 145 return true; 146 else { 147 // Check if the filter matches a subdirectory of the test program. 148 // The test case must be empty because we don't want foo:bar to match 149 // foo/baz. 150 return (test_case.empty() && test_program.is_parent_of(test_program_)); 151 } 152 } 153 154 155 /// Checks if this filter matches a given test case identifier. 156 /// 157 /// \param test_program_ The test program to compare to. 158 /// \param test_case_ The test case to compare to. 159 /// 160 /// \return Whether the filter matches the test case. 161 bool 162 engine::test_filter::matches_test_case(const fs::path& test_program_, 163 const std::string& test_case_) const 164 { 165 if (matches_test_program(test_program_)) { 166 return test_case.empty() || test_case == test_case_; 167 } else 168 return false; 169 } 170 171 172 /// Less-than comparison for sorting purposes. 173 /// 174 /// \param other The filter to compare to. 175 /// 176 /// \return True if this filter sorts before the other filter. 177 bool 178 engine::test_filter::operator<(const test_filter& other) const 179 { 180 return ( 181 test_program < other.test_program || 182 (test_program == other.test_program && test_case < other.test_case)); 183 } 184 185 186 /// Equality comparison. 187 /// 188 /// \param other The filter to compare to. 189 /// 190 /// \return True if this filter is equal to the other filter. 191 bool 192 engine::test_filter::operator==(const test_filter& other) const 193 { 194 return test_program == other.test_program && test_case == other.test_case; 195 } 196 197 198 /// Non-equality comparison. 199 /// 200 /// \param other The filter to compare to. 201 /// 202 /// \return True if this filter is different than the other filter. 203 bool 204 engine::test_filter::operator!=(const test_filter& other) const 205 { 206 return !(*this == other); 207 } 208 209 210 /// Injects the object into a stream. 211 /// 212 /// \param output The stream into which to inject the object. 213 /// \param object The object to format. 214 /// 215 /// \return The output stream. 216 std::ostream& 217 engine::operator<<(std::ostream& output, const test_filter& object) 218 { 219 if (object.test_case.empty()) { 220 output << F("test_filter{test_program=%s}") % object.test_program; 221 } else { 222 output << F("test_filter{test_program=%s, test_case=%s}") 223 % object.test_program % object.test_case; 224 } 225 return output; 226 } 227 228 229 /// Constructs a new set of filters. 230 /// 231 /// \param filters_ The filters themselves; if empty, no filters are applied. 232 engine::test_filters::test_filters(const std::set< test_filter >& filters_) : 233 _filters(filters_) 234 { 235 } 236 237 238 /// Checks if a given test program matches the set of filters. 239 /// 240 /// This is provided as an optimization only, and the results of this function 241 /// are less specific than those of match_test_case. Checking for the matching 242 /// of a test program should be done before loading the list of test cases from 243 /// a program, so as to avoid the delay in executing the test program, but 244 /// match_test_case must still be called afterwards. 245 /// 246 /// \param name The test program to check against the filters. 247 /// 248 /// \return True if the provided identifier matches any filter. 249 bool 250 engine::test_filters::match_test_program(const fs::path& name) const 251 { 252 if (_filters.empty()) 253 return true; 254 255 bool matches = false; 256 for (std::set< test_filter >::const_iterator iter = _filters.begin(); 257 !matches && iter != _filters.end(); iter++) { 258 matches = (*iter).matches_test_program(name); 259 } 260 return matches; 261 } 262 263 264 /// Checks if a given test case identifier matches the set of filters. 265 /// 266 /// \param test_program The test program to check against the filters. 267 /// \param test_case The test case to check against the filters. 268 /// 269 /// \return A boolean indicating if the test case is matched by any filter and, 270 /// if true, a string containing the filter name. The string is empty when 271 /// there are no filters defined. 272 engine::test_filters::match 273 engine::test_filters::match_test_case(const fs::path& test_program, 274 const std::string& test_case) const 275 { 276 if (_filters.empty()) { 277 INV(match_test_program(test_program)); 278 return match(true, none); 279 } 280 281 optional< test_filter > found = none; 282 for (std::set< test_filter >::const_iterator iter = _filters.begin(); 283 !found && iter != _filters.end(); iter++) { 284 if ((*iter).matches_test_case(test_program, test_case)) 285 found = *iter; 286 } 287 INV(!found || match_test_program(test_program)); 288 return match(static_cast< bool >(found), found); 289 } 290 291 292 /// Calculates the filters that have not matched any tests. 293 /// 294 /// \param matched The filters that did match some tests. This must be a subset 295 /// of the filters held by this object. 296 /// 297 /// \return The set of filters that have not been used. 298 std::set< engine::test_filter > 299 engine::test_filters::difference(const std::set< test_filter >& matched) const 300 { 301 PRE(std::includes(_filters.begin(), _filters.end(), 302 matched.begin(), matched.end())); 303 304 std::set< test_filter > filters; 305 std::set_difference(_filters.begin(), _filters.end(), 306 matched.begin(), matched.end(), 307 std::inserter(filters, filters.begin())); 308 return filters; 309 } 310 311 312 /// Checks if a collection of filters is disjoint. 313 /// 314 /// \param filters The filters to check. 315 /// 316 /// \throw std::runtime_error If the filters are not disjoint. 317 void 318 engine::check_disjoint_filters(const std::set< engine::test_filter >& filters) 319 { 320 // Yes, this is an O(n^2) algorithm. However, we can assume that the number 321 // of test filters (which are provided by the user on the command line) on a 322 // particular run is in the order of tens, and thus this should not cause 323 // any serious performance trouble. 324 for (std::set< test_filter >::const_iterator i1 = filters.begin(); 325 i1 != filters.end(); i1++) { 326 for (std::set< test_filter >::const_iterator i2 = filters.begin(); 327 i2 != filters.end(); i2++) { 328 const test_filter& filter1 = *i1; 329 const test_filter& filter2 = *i2; 330 331 if (i1 != i2 && filter1.contains(filter2)) { 332 throw std::runtime_error( 333 F("Filters '%s' and '%s' are not disjoint") % 334 filter1.str() % filter2.str()); 335 } 336 } 337 } 338 } 339 340 341 /// Constructs a filters_state instance. 342 /// 343 /// \param filters_ The set of filters to track. 344 engine::filters_state::filters_state( 345 const std::set< engine::test_filter >& filters_) : 346 _filters(test_filters(filters_)) 347 { 348 } 349 350 351 /// Checks whether these filters match the given test program. 352 /// 353 /// \param test_program The test program to match against. 354 /// 355 /// \return True if these filters match the given test program name. 356 bool 357 engine::filters_state::match_test_program(const fs::path& test_program) const 358 { 359 return _filters.match_test_program(test_program); 360 } 361 362 363 /// Checks whether these filters match the given test case. 364 /// 365 /// \param test_program The test program to match against. 366 /// \param test_case The test case to match against. 367 /// 368 /// \return True if these filters match the given test case identifier. 369 bool 370 engine::filters_state::match_test_case(const fs::path& test_program, 371 const std::string& test_case) 372 { 373 engine::test_filters::match match = _filters.match_test_case( 374 test_program, test_case); 375 if (match.first && match.second) 376 _used_filters.insert(match.second.get()); 377 return match.first; 378 } 379 380 381 /// Calculates the unused filters in this set. 382 /// 383 /// \return Returns the set of filters that have not matched any tests. This 384 /// information is useful to report usage errors to the user. 385 std::set< engine::test_filter > 386 engine::filters_state::unused(void) const 387 { 388 return _filters.difference(_used_filters); 389 } 390