contrib/kyua/engine/filters.cpp

   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 &lt;test_program%gt;[:&lt;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 }