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 40namespace fs = utils::fs; 41 42using utils::none; 43using 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. 51engine::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. 67engine::test_filter 68engine::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. 109std::string 110engine::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. 124bool 125engine::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. 141bool 142engine::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. 161bool 162engine::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. 177bool 178engine::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. 191bool 192engine::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. 203bool 204engine::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. 216std::ostream& 217engine::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. 232engine::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. 249bool 250engine::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. 272engine::test_filters::match 273engine::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. 298std::set< engine::test_filter > 299engine::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. 317void 318engine::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. 344engine::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. 356bool 357engine::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. 369bool 370engine::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. 385std::set< engine::test_filter > 386engine::filters_state::unused(void) const 387{ 388 return _filters.difference(_used_filters); 389} 390