this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Mikael Lagerkvist <lagerkvist@gecode.org>
6 *
7 * Copyright:
8 * Christian Schulte, 2004
9 * Mikael Lagerkvist, 2005
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#include "test/test.hh"
37
38#ifdef GECODE_HAS_MTRACE
39#include <mcheck.h>
40#endif
41
42#include <iostream>
43
44#include <cstdlib>
45#include <cstring>
46#include <ctime>
47#include <utility>
48#include <vector>
49#include <utility>
50
51namespace Test {
52
53 // Log stream
54 std::ostringstream olog;
55
56 /*
57 * Base class for tests
58 *
59 */
60 Base::Base(std::string s)
61 : _name(std::move(s)), _next(_tests), _rand(Gecode::Support::RandomGenerator()) {
62 _tests = this; _n_tests++;
63 }
64
65 Base* Base::_tests = nullptr;
66 unsigned int Base::_n_tests = 0;
67
68 /// Sort tests by name
69 class SortByName {
70 public:
71 forceinline bool
72 operator()(Base* x, Base* y) {
73 return x->name() > y->name();
74 }
75 };
76
77 void
78 Base::sort() {
79 Base** b = Gecode::heap.alloc<Base*>(_n_tests);
80 unsigned int i=0;
81 for (Base* t = _tests; t != nullptr; t = t->next())
82 b[i++] = t;
83 SortByName sbn;
84 Gecode::Support::quicksort(b, _n_tests,sbn);
85 i=0;
86 _tests = nullptr;
87 for ( ; i < _n_tests; i++) {
88 b[i]->next(_tests); _tests = b[i];
89 }
90 Gecode::heap.free(b,_n_tests);
91 }
92
93 Base::~Base() = default;
94
95 Options opt;
96
97 void report_error(const std::string& name, unsigned int seed, Options& options, std::ostream& ostream) {
98 ostream << "Options: -seed " << seed;
99 if (options.fixprob != Test::Options::deffixprob)
100 ostream << " -fixprob " << options.fixprob;
101 ostream << " -test " << name << std::endl;
102 if (options.log)
103 ostream << olog.str();
104 }
105
106 void
107 Options::parse(int argc, char* argv[]) {
108 int i = 1;
109 while (i < argc) {
110 if (!strcmp(argv[i],"-help") || !strcmp(argv[i],"--help")) {
111 std::cerr << "Options for testing:" << std::endl
112 << "\t-threads (unsigned int) default: " << threads << std::endl
113 << "\t\tnumber of threads to use. If 0, as many threads as there are cores are used."
114 << "\t\tThreaded execution and logging can not be used at the same time."
115 << std::endl
116 << "\t-seed (unsigned int or \"time\") default: "
117 << seed << std::endl
118 << "\t\tseed for random number generator (unsigned int),"
119 << std::endl
120 << "\t\tor \"time\" for a random seed based on "
121 << "current time" << std::endl
122 << "\t-fixprob (unsigned int) default: "
123 << fixprob << std::endl
124 << "\t\t1/fixprob is the probability of computing a fixpoint"
125 << std::endl
126 << "\t-iter (unsigned int) default: " <<iter<< std::endl
127 << "\t\tthe number of iterations" << std::endl
128 << "\t-test (string) default: (none)" << std::endl
129 << "\t\tsimple pattern for the tests to run" << std::endl
130 << "\t\tprefixing with \"-\" negates the pattern" << std::endl
131 << "\t\tprefixing with \"^\" requires a match at the beginning" << std::endl
132 << "\t\tmultiple pattern-options may be given"
133 << std::endl
134 << "\t-start (string) default: (none)" << std::endl
135 << "\t\tsimple pattern for the first test to run" << std::endl
136 << "\t-log"
137 << std::endl
138 << "\t\tlog execution of tests"
139 << std::endl
140 << "\t\tthe optional argument determines the style of the log"
141 << std::endl
142 << "\t\twith text as the default style"
143 << std::endl
144 << "\t-stop (boolean) default: "
145 << (stop ? "true" : "false") << std::endl
146 << "\t\tstop on first error or continue" << std::endl
147 << "\t-list" << std::endl
148 << "\t\toutput list of all test cases and exit" << std::endl
149 ;
150 exit(EXIT_SUCCESS);
151 } else if (!strcmp(argv[i],"-threads")) {
152 if (++i == argc) goto missing;
153 unsigned int argument = static_cast<unsigned int>(atoi(argv[i]));
154 if (argument == 0) {
155 threads = Gecode::Support::Thread::npu();
156 } else {
157 threads = argument;
158 }
159 } else if (!strcmp(argv[i],"-seed")) {
160 if (++i == argc) goto missing;
161 if (!strcmp(argv[i],"time")) {
162 seed = static_cast<unsigned int>(time(nullptr));
163 } else {
164 seed = static_cast<unsigned int>(atoi(argv[i]));
165 }
166 } else if (!strcmp(argv[i],"-iter")) {
167 if (++i == argc) goto missing;
168 iter = static_cast<unsigned int>(atoi(argv[i]));
169 } else if (!strcmp(argv[i],"-fixprob")) {
170 if (++i == argc) goto missing;
171 fixprob = static_cast<unsigned int>(atoi(argv[i]));
172 } else if (!strcmp(argv[i],"-test")) {
173 if (++i == argc) goto missing;
174 if (argv[i][0] == '^')
175 testpat.emplace_back(MT_FIRST, argv[i] + 1);
176 else if (argv[i][0] == '-')
177 testpat.emplace_back(MT_NOT, argv[i] + 1);
178 else
179 testpat.emplace_back(MT_ANY, argv[i]);
180 } else if (!strcmp(argv[i],"-start")) {
181 if (++i == argc) goto missing;
182 start_from = argv[i];
183 } else if (!strcmp(argv[i],"-log")) {
184 log = true;
185 } else if (!strcmp(argv[i],"-stop")) {
186 if (++i == argc) goto missing;
187 if(argv[i][0] == 't') {
188 stop = true;
189 } else if (argv[i][0] == 'f') {
190 stop = false;
191 }
192 } else if (!strcmp(argv[i],"-list")) {
193 list = true;
194 }
195 i++;
196 }
197
198 if (threads > 1 && log) {
199 std::cerr << "Logging and multi threading can not be used jointly." << std::endl;
200 exit(EXIT_FAILURE);
201 }
202
203 return;
204 missing:
205 std::cerr << "Erroneous argument (" << argv[i-1] << ")" << std::endl
206 << " missing parameter" << std::endl;
207 exit(EXIT_FAILURE);
208 }
209
210 bool Options::is_test_name_matching(const std::string& test_name) {
211 if (!testpat.empty()) {
212 bool positive_patterns = false;
213 bool match_found = false;
214 for (const auto& type_pattern: testpat) {
215 const auto& type = type_pattern.first;
216 const auto& pattern = type_pattern.second;
217 if (type == MT_NOT) { // Negative pattern
218 if (test_name.find(pattern) != std::string::npos) {
219 // Test matches a negative pattern, should not run
220 return false;
221 }
222 } else {
223 // Positive pattern
224 positive_patterns = true;
225 if (!match_found) {
226 // No match found yet, test with current pattern
227 if (((type == MT_ANY) && (test_name.find(pattern) != std::string::npos)) ||
228 ((type == MT_FIRST) && (test_name.find(pattern) == 0)))
229 match_found = true;
230 }
231 }
232 }
233
234 if (positive_patterns && match_found) {
235 // Some positive pattern matched the test name
236 return true;
237 } else if (positive_patterns && !match_found) {
238 // No positive pattern matched the test name
239 return false;
240 } else {
241 // No positive patterns, but no negative pattern ruled the test name out
242 return true;
243 }
244 } else {
245 // With no test-patterns, all tests should run.
246 return true;
247 }
248 }
249
250 /// Run a single test, returning true iff the test succeeded
251 bool run_test(Base* test, unsigned int test_seed, const Options& options, std::ostream& ostream) {
252 try {
253 ostream << test->name() << " ";
254 ostream.flush();
255 test->_rand.seed(test_seed);
256 for (unsigned int i = options.iter; i--;) {
257 unsigned int seed = test->_rand.seed();
258 if (test->run()) {
259 ostream << '+';
260 ostream.flush();
261 } else {
262 ostream << "-" << std::endl;
263 report_error(test->name(), seed, opt, ostream);
264 return false;
265 }
266 }
267 ostream << std::endl;
268 return true;
269 } catch (Gecode::Exception& e) {
270 ostream << "Exception in \"Gecode::" << e.what()
271 << "." << std::endl
272 << "Stopping..." << std::endl;
273 report_error(test->name(), options.seed, opt, ostream);
274 return false;
275 }
276 }
277
278 /// Run all the tests with the supplied options.
279 int run_tests(const std::vector<Base*>& tests, const Options& options) {
280 Gecode::Support::RandomGenerator seed_sequence(options.seed);
281 int result = EXIT_SUCCESS;
282 for (auto test : tests) {
283 unsigned int test_seed = seed_sequence.next();
284 if (!run_test(test, test_seed, options, std::cout)) {
285 if (opt.stop) {
286 return EXIT_FAILURE;
287 } else {
288 result = EXIT_FAILURE;
289 }
290 }
291 }
292 return result;
293 }
294
295 class TestExecutor;
296
297 /**
298 * Class that manages the state and control for running tests.
299 */
300 class TestExecutionControl {
301 /// All the tests to run
302 const std::vector<Base*>& tests;
303 /// The options to use when running tests
304 const Options& options;
305 /// Mutex controlling output from the threads
306 Gecode::Support::Mutex output_mutex;
307 /// The next starting index among the tests.
308 std::atomic<size_t> next_tests;
309 /// The result
310 std::atomic<int> result;
311 /// The number of test runners that are to be set up.
312 std::atomic<int> running_threads;
313 /// Flag indicating some thread is waiting on the execution to be done.
314 std::atomic<bool> execution_done_wait_started;
315 /// Event for signalling that execution is done.
316 Gecode::Support::Event execution_done_event;
317
318 friend class TestExecutor;
319
320 /// Choose a batch size based on the number of tests to divide
321 static size_t choose_batch_size(size_t test_count, int thread_count) {
322 const int batches_per_thread = 5;
323 std::vector<size_t> batch_sizes = {25, 10, 5, 2};
324 for (auto batch_size : batch_sizes) {
325 if (test_count > batch_size * thread_count * batches_per_thread) {
326 return batch_size;
327 }
328 }
329 return 1;
330 }
331
332 public:
333 TestExecutionControl(const std::vector<Base*>& tests0, const Options& options0, int thread_count)
334 : tests(tests0), options(options0), output_mutex(),
335 next_tests(0), result(EXIT_SUCCESS), running_threads(thread_count),
336 execution_done_wait_started(false), execution_done_event() {}
337
338 /// Get the current result (either \a EXIT_SUCCESS or \a EXIT_FAILURE). Requires all threads to be done first.
339 int get_result() {
340 assert(running_threads.load() == 0);
341 return result.load();
342 }
343
344 /** Wait for test-runners to be completed.
345 *
346 * Important: may only be called once by a single thread!
347 */
348 void await_test_runners_completed() {
349#ifndef NDEBUG
350 bool some_waiting =
351#endif
352 execution_done_wait_started.exchange(true);
353 assert(some_waiting == false && "Only one thread is allowed to await the result");
354 execution_done_event.wait();
355 }
356 private:
357 /// Set flag that failure has occurred.
358 void set_failure() {
359 result.store(EXIT_FAILURE);
360 }
361
362 /// Indicate that a thread is done executing.
363 void thread_done() {
364 if (running_threads.fetch_sub(1) == 1) {
365 execution_done_event.signal();
366 }
367 }
368
369 /// Get the start of the next batch and the batch size.
370 /// Important, may be a number larger than available number of tests
371 std::pair<size_t, size_t> next_batch() {
372 const size_t current_start = next_tests.load();
373 const size_t batch_size = choose_batch_size(tests.size() - current_start, running_threads);
374 const size_t next_start = next_tests.fetch_add(batch_size);
375 return std::make_pair(next_start, batch_size);
376 }
377
378 /// True iff the runners should continue running tests
379 bool continue_testing() {
380 // Note: implementation should be cheap to call form multiple threads often
381 return !options.stop || result.load() == EXIT_SUCCESS;
382 }
383
384 /// Write a string to standard output, synchronized across all test runners
385 void write_output(std::string output) {
386 Gecode::Support::Lock lock(output_mutex);
387 std::cout << output;
388 std::cout.flush();
389 }
390 };
391
392 /**
393 * Class that is responsible for running tests.
394 */
395 class TestExecutor : public Gecode::Support::Runnable {
396 /// The common controller for running tests
397 TestExecutionControl& tec;
398 /// The initial seed to start with
399 const int initial_seed;
400 public:
401
402 TestExecutor(TestExecutionControl& tec, const int initialSeed)
403 : tec(tec), initial_seed(initialSeed) {}
404
405 void run(void) override {
406 // Set up a local source of randomness seeds based on the initial seed supplied.
407 Gecode::Support::RandomGenerator seed_sequence(initial_seed);
408
409 // Loop runs tests continuously in batches from the test execution control
410 while (true) {
411 // Get next batch
412 const std::pair<size_t, size_t>& start_and_size = tec.next_batch();
413 const size_t batch_start = start_and_size.first;
414 const size_t batch_size = start_and_size.second;
415 if (batch_start >= tec.tests.size()) {
416 // No more tests to run
417 break;
418 }
419 // Run each test in the batch, handling output and failures
420 for (size_t i = batch_start; i < batch_start + batch_size && i < tec.tests.size(); ++i) {
421 if (!tec.continue_testing()) {
422 break;
423 }
424 auto test = tec.tests[i];
425 unsigned int test_seed = seed_sequence.next();
426 std::ostringstream test_output;
427 if (!run_test(test, test_seed, tec.options, test_output)) {
428 tec.set_failure();
429 }
430 tec.write_output(test_output.str());
431 }
432 if (!tec.continue_testing()) {
433 break;
434 }
435 }
436
437 // Signal that this thread is done. Last one signals the waiting main thread.
438 tec.thread_done();
439 }
440 };
441
442 /// Run all the tests with the supplied options i parallel.
443 int run_tests_parallel(const std::vector<Base*>& tests, const Options& options) {
444 using namespace Gecode::Support;
445 RandomGenerator seed_sequence(options.seed);
446
447 TestExecutionControl tec(tests, options, opt.threads);
448
449 for (unsigned int i = 0; i < opt.threads; ++i) {
450 Thread::run(new TestExecutor(tec, seed_sequence.next()));
451 }
452 tec.await_test_runners_completed();
453
454 return tec.get_result();
455 }
456}
457
458
459int
460main(int argc, char* argv[]) {
461 using namespace Test;
462#ifdef GECODE_HAS_MTRACE
463 mtrace();
464#endif
465
466 opt.parse(argc, argv);
467
468 Base::sort();
469
470 if (opt.list) {
471 for (Base* t = Base::tests() ; t != nullptr; t = t->next() ) {
472 std::cout << t->name() << std::endl;
473 }
474 exit(EXIT_SUCCESS);
475 }
476
477 std::vector<Base*> tests;
478 bool started = opt.start_from == nullptr ? true : false;
479 for (Base* t = Base::tests() ; t != nullptr; t = t->next() ) {
480 if (!started) {
481 if (t->name().find(opt.start_from) != std::string::npos) {
482 started = true;
483 } else {
484 continue;
485 }
486 }
487 if (opt.is_test_name_matching(t->name())) {
488 tests.emplace_back(t);
489 }
490 }
491
492 if (opt.threads > 1) {
493 return run_tests_parallel(tests, opt);
494 } else {
495 return run_tests(tests, opt);
496 }
497}
498
499std::ostream&
500operator<<(std::ostream& os, const Test::ind& i) {
501 for (int j=i.l; j--; )
502 os << " ";
503 return os;
504}
505
506// STATISTICS: test-core