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 *
6 * Copyright:
7 * Christian Schulte, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 *
14 * Permission is hereby granted, free of charge, to any person obtaining
15 * a copy of this software and associated documentation files (the
16 * "Software"), to deal in the Software without restriction, including
17 * without limitation the rights to use, copy, modify, merge, publish,
18 * distribute, sublicense, and/or sell copies of the Software, and to
19 * permit persons to whom the Software is furnished to do so, subject to
20 * the following conditions:
21 *
22 * The above copyright notice and this permission notice shall be
23 * included in all copies or substantial portions of the Software.
24 *
25 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
26 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
27 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
28 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
29 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
30 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
31 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
32 *
33 */
34
35#include <iostream>
36#include <iomanip>
37#include <fstream>
38#include <cstring>
39
40#ifndef GECODE_THREADS_WINDOWS
41#include <csignal>
42#endif
43
44namespace Gecode { namespace Driver {
45
46 /**
47 * \brief Stop object based on nodes, failures, and time
48 *
49 */
50 class CombinedStop : public Search::Stop {
51 private:
52 Search::NodeStop* ns; ///< Used node stop object
53 Search::FailStop* fs; ///< Used fail stop object
54 Search::TimeStop* ts; ///< Used time stop object
55 GECODE_DRIVER_EXPORT
56 static bool sigint; ///< Whether search was interrupted using Ctrl-C
57 /// Initialize stop object
58 CombinedStop(unsigned long long int node,
59 unsigned long long int fail,
60 double time)
61 : ns((node > 0ULL) ? new Search::NodeStop(node) : nullptr),
62 fs((fail > 0ULL) ? new Search::FailStop(fail) : nullptr),
63 ts((time > 0.0) ? new Search::TimeStop(time) : nullptr) {
64 sigint = false;
65 }
66 public:
67 /// Reason why search has been stopped
68 enum {
69 SR_NODE = 1 << 0, ///< Node limit reached
70 SR_FAIL = 1 << 1, ///< Fail limit reached
71 SR_TIME = 1 << 2, ///< Time limit reached
72 SR_INT = 1 << 3 ///< Interrupted by user
73 };
74 /// Test whether search must be stopped
75 virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
76 return
77 sigint ||
78 ((ns != nullptr) && ns->stop(s,o)) ||
79 ((fs != nullptr) && fs->stop(s,o)) ||
80 ((ts != nullptr) && ts->stop(s,o));
81 }
82 /// Report reason why search has been stopped
83 int reason(const Search::Statistics& s, const Search::Options& o) {
84 return
85 (((ns != nullptr) && ns->stop(s,o)) ? SR_NODE : 0) |
86 (((fs != nullptr) && fs->stop(s,o)) ? SR_FAIL : 0) |
87 (((ts != nullptr) && ts->stop(s,o)) ? SR_TIME : 0) |
88 (sigint ? SR_INT : 0);
89 }
90 /// Create appropriate stop-object
91 static Search::Stop*
92 create(unsigned long long int node,
93 unsigned long long int fail,
94 double time,
95 bool intr) {
96 if (!intr && (node == 0ULL) && (fail == 0ULL) && (time == 0.0))
97 return nullptr;
98 else
99 return new CombinedStop(node,fail,time);
100 }
101#ifdef GECODE_THREADS_WINDOWS
102 /// Handler for catching Ctrl-C
103 static BOOL interrupt(DWORD t) noexcept {
104 if (t == CTRL_C_EVENT) {
105 sigint = true;
106 installCtrlHandler(false,true);
107 return true;
108 }
109 return false;
110 }
111#else
112 /// Handler for catching Ctrl-C
113 static void
114 interrupt(int) {
115 sigint = true;
116 installCtrlHandler(false,true);
117 }
118#endif
119 /// Install handler for catching Ctrl-C
120 static void installCtrlHandler(bool install, bool force=false) {
121 if (force || !sigint) {
122#ifdef GECODE_THREADS_WINDOWS
123 SetConsoleCtrlHandler( (PHANDLER_ROUTINE) interrupt, install);
124#else
125 std::signal(SIGINT, install ? interrupt : SIG_DFL);
126#endif
127 }
128 }
129 /// Destructor
130 ~CombinedStop(void) {
131 delete ns; delete fs; delete ts;
132 }
133 };
134
135 /**
136 * \brief Get time since start of timer and print user friendly time
137 * information.
138 */
139 GECODE_DRIVER_EXPORT void
140 stop(Support::Timer& t, std::ostream& os);
141
142 /**
143 * \brief Compute arithmetic mean of \a n elements in \a t
144 */
145 GECODE_DRIVER_EXPORT double
146 am(double t[], unsigned int n);
147
148 /**
149 * \brief Compute deviation of \a n elements in \a t
150 */
151 GECODE_DRIVER_EXPORT double
152 dev(double t[], unsigned int n);
153
154 /// Create cutoff object from options
155 template<class Options>
156 inline Search::Cutoff*
157 createCutoff(const Options& o) {
158 switch (o.restart()) {
159 case RM_NONE:
160 return nullptr;
161 case RM_CONSTANT:
162 return Search::Cutoff::constant(o.restart_scale());
163 case RM_LINEAR:
164 return Search::Cutoff::linear(o.restart_scale());
165 case RM_LUBY:
166 return Search::Cutoff::luby(o.restart_scale());
167 case RM_GEOMETRIC:
168 return Search::Cutoff::geometric(o.restart_scale(),o.restart_base());
169 default: GECODE_NEVER;
170 }
171 return nullptr;
172 }
173
174
175#ifdef GECODE_HAS_GIST
176
177 /**
178 * \brief Traits class for search engines
179 */
180 template<class Engine>
181 class GistEngine {
182 public:
183 static void explore(Space* root, const Gist::Options& opt) {
184 (void) Gist::dfs(root, opt);
185 }
186 };
187
188 /// Specialization for DFS
189 template<typename S>
190 class GistEngine<DFS<S> > {
191 public:
192 static void explore(S* root, const Gist::Options& opt) {
193 (void) Gist::dfs(root, opt);
194 }
195 };
196
197 /// Specialization for LDS
198 template<typename S>
199 class GistEngine<LDS<S> > {
200 public:
201 static void explore(S* root, const Gist::Options& opt) {
202 (void) Gist::dfs(root, opt);
203 }
204 };
205
206 /// Specialization for BAB
207 template<typename S>
208 class GistEngine<BAB<S> > {
209 public:
210 static void explore(S* root, const Gist::Options& opt) {
211 (void) Gist::bab(root, opt);
212 }
213 };
214
215#endif
216
217#ifdef GECODE_HAS_CPPROFILER
218
219 /// Class to send solution information to CPProfiler for a script
220 template<class BaseSpace>
221 class ScriptGetInfo : public CPProfilerSearchTracer::GetInfo {
222 public:
223 /// Initialize
224 ScriptGetInfo(void);
225 /// Return info for a space (which must be a script)
226 virtual std::string getInfo(const Space& home) const;
227 };
228
229#endif
230
231 template<class BaseSpace>
232 forceinline
233 ScriptBase<BaseSpace>::ScriptBase(const Options& opt)
234 : BaseSpace(opt) {}
235
236 template<class BaseSpace>
237 forceinline
238 ScriptBase<BaseSpace>::ScriptBase(ScriptBase& e)
239 : BaseSpace(e) {}
240
241 template<class BaseSpace>
242 void
243 ScriptBase<BaseSpace>::print(std::ostream&) const {}
244
245 template<class BaseSpace>
246 void
247 ScriptBase<BaseSpace>::compare(const Space&, std::ostream&) const {}
248
249 template<class BaseSpace>
250 std::ostream&
251 ScriptBase<BaseSpace>::select_ostream(const char* sn, std::ofstream& ofs) {
252 if (strcmp(sn, "stdout") == 0) {
253 return std::cout;
254 } else if (strcmp(sn, "stdlog") == 0) {
255 return std::clog;
256 } else if (strcmp(sn, "stderr") == 0) {
257 return std::cerr;
258 } else {
259 ofs.open(sn);
260 return ofs;
261 }
262 }
263
264#ifdef GECODE_HAS_CPPROFILER
265
266 template<class BaseSpace>
267 ScriptGetInfo<BaseSpace>::ScriptGetInfo(void) {}
268
269 template<class BaseSpace>
270 std::string
271 ScriptGetInfo<BaseSpace>::getInfo(const Space& home) const {
272 std::stringstream ss;
273 if (const ScriptBase<BaseSpace>* sb
274 = dynamic_cast<const ScriptBase<BaseSpace>*>(&home))
275 sb->print(ss);
276 return ss.str();
277 }
278
279#endif
280
281
282 /**
283 * \brief Wrapper class to add engine template argument
284 */
285 template<class T, template<class> class E>
286 class EngineToMeta : public E<T> {
287 public:
288 EngineToMeta(T* s, const Search::Options& o) : E<T>(s,o) {}
289 };
290
291 template<class BaseSpace>
292 template<class Script, template<class> class Engine, class Options>
293 void
294 ScriptBase<BaseSpace>::run(const Options& o, Script* s) {
295 if ((o.restart() != RM_NONE) && (o.assets() > 0)) {
296 std::cerr << "Cannot use restarts and portfolio..." << std::endl;
297 exit(EXIT_FAILURE);
298 }
299 if (o.restart() != RM_NONE) {
300 runMeta<Script,Engine,Options,RBS>(o,s);
301 } else if (o.assets() > 0) {
302 runMeta<Script,Engine,Options,PBS>(o,s);
303 } else {
304 runMeta<Script,Engine,Options,EngineToMeta>(o,s);
305 }
306 }
307
308 template<class BaseSpace>
309 template<class Script, template<class> class Engine, class Options,
310 template<class, template<class> class> class Meta>
311 void
312 ScriptBase<BaseSpace>::runMeta(const Options& o, Script* s) {
313 using namespace std;
314
315 ofstream sol_file, log_file;
316
317 ostream& s_out = select_ostream(o.out_file(), sol_file);
318 ostream& l_out = select_ostream(o.log_file(), log_file);
319
320 Search::Options so;
321
322 try {
323 switch (o.mode()) {
324 case SM_GIST:
325#ifdef GECODE_HAS_GIST
326 {
327 Gist::Print<Script> pi(o.name());
328 Gist::VarComparator<Script> vc(o.name());
329 Gist::Options opt;
330 opt.inspect.click(&pi);
331 opt.inspect.compare(&vc);
332 opt.clone = false;
333 opt.c_d = o.c_d();
334 opt.a_d = o.a_d();
335 for (unsigned int i=0; o.inspect.click(i) != nullptr; i++)
336 opt.inspect.click(o.inspect.click(i));
337 for (unsigned int i=0; o.inspect.solution(i) != nullptr; i++)
338 opt.inspect.solution(o.inspect.solution(i));
339 for (unsigned int i=0; o.inspect.move(i) != nullptr; i++)
340 opt.inspect.move(o.inspect.move(i));
341 for (unsigned int i=0; o.inspect.compare(i) != nullptr; i++)
342 opt.inspect.compare(o.inspect.compare(i));
343 if (s == nullptr)
344 s = new Script(o);
345 (void) GistEngine<Engine<Script> >::explore(s, opt);
346 }
347 break;
348 // If Gist is not available, goto solution
349#else
350 goto solution;
351#endif
352 case SM_SOLUTION:
353#ifndef GECODE_HAS_GIST
354 solution:
355#endif
356 {
357#ifdef GECODE_HAS_CPPROFILER
358 if (o.profiler_port()) {
359 CPProfilerSearchTracer::GetInfo* getInfo = nullptr;
360 if (o.profiler_info())
361 getInfo = new ScriptGetInfo<BaseSpace>;
362 so.tracer = new CPProfilerSearchTracer
363 (o.profiler_id(), o.name(), o.profiler_port(), getInfo);
364 }
365#endif
366 l_out << o.name() << endl;
367 Support::Timer t;
368 unsigned long long int s_l =
369 (o.solutions() == 0) ? ULLONG_MAX : o.solutions();
370 unsigned long long int s_n = 0;
371 t.start();
372 if (s == nullptr)
373 s = new Script(o);
374 unsigned int n_p = PropagatorGroup::all.size(*s);
375 unsigned int n_b = BrancherGroup::all.size(*s);
376 so.threads = o.threads();
377 so.c_d = o.c_d();
378 so.a_d = o.a_d();
379 so.d_l = o.d_l();
380 so.assets = o.assets();
381 so.slice = o.slice();
382 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
383 o.interrupt());
384 so.cutoff = createCutoff(o);
385 so.clone = false;
386 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
387 if (o.interrupt())
388 CombinedStop::installCtrlHandler(true);
389 {
390 Meta<Script,Engine> e(s,so);
391 if (o.print_last()) {
392 Script* px = nullptr;
393 do {
394 Script* ex = e.next();
395 if (ex == nullptr) {
396 if (px != nullptr) {
397 px->print(s_out);
398 delete px;
399 }
400 break;
401 } else {
402 s_n++;
403 delete px;
404 px = ex;
405 }
406 } while (s_n < s_l);
407 } else {
408 do {
409 Script* ex = e.next();
410 if (ex == nullptr)
411 break;
412 ex->print(s_out);
413 delete ex;
414 s_n++;
415 } while (s_n < s_l);
416 }
417 if (o.interrupt())
418 CombinedStop::installCtrlHandler(false);
419 Search::Statistics stat = e.statistics();
420 s_out << endl;
421 if (e.stopped()) {
422 l_out << "Search engine stopped..." << endl
423 << "\treason: ";
424 int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
425 if (r & CombinedStop::SR_INT)
426 l_out << "user interrupt " << endl;
427 else {
428 if (r & CombinedStop::SR_NODE)
429 l_out << "node ";
430 if (r & CombinedStop::SR_FAIL)
431 l_out << "fail ";
432 if (r & CombinedStop::SR_TIME)
433 l_out << "time ";
434 l_out << "limit reached" << endl << endl;
435 }
436 }
437 l_out << "Initial" << endl
438 << "\tpropagators: " << n_p << endl
439 << "\tbranchers: " << n_b << endl
440 << endl
441 << "Summary" << endl
442 << "\truntime: ";
443 stop(t, l_out);
444 l_out << endl
445 << "\tsolutions: " << s_n << endl
446 << "\tpropagations: " << stat.propagate << endl
447 << "\tnodes: " << stat.node << endl
448 << "\tfailures: " << stat.fail << endl
449 << "\trestarts: " << stat.restart << endl
450 << "\tno-goods: " << stat.nogood << endl
451 << "\tpeak depth: " << stat.depth << endl
452#ifdef GECODE_PEAKHEAP
453 << "\tpeak memory: "
454 << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
455 << endl
456#endif
457 << endl;
458 }
459 delete so.stop;
460 delete so.tracer;
461 }
462 break;
463 case SM_STAT:
464 {
465 l_out << o.name() << endl;
466 Support::Timer t;
467 unsigned long long int s_l =
468 (o.solutions() == 0) ? ULLONG_MAX : o.solutions();
469 unsigned long long int s_n = 0;
470 t.start();
471 if (s == nullptr)
472 s = new Script(o);
473 unsigned int n_p = PropagatorGroup::all.size(*s);
474 unsigned int n_b = BrancherGroup::all.size(*s);
475
476 so.clone = false;
477 so.threads = o.threads();
478 so.assets = o.assets();
479 so.slice = o.slice();
480 so.c_d = o.c_d();
481 so.a_d = o.a_d();
482 so.d_l = o.d_l();
483 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
484 o.interrupt());
485 so.cutoff = createCutoff(o);
486 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
487 if (o.interrupt())
488 CombinedStop::installCtrlHandler(true);
489 {
490 Meta<Script,Engine> e(s,so);
491 do {
492 Script* ex = e.next();
493 if (ex == nullptr)
494 break;
495 delete ex;
496 s_n++;
497 } while (s_n < s_l);
498 if (o.interrupt())
499 CombinedStop::installCtrlHandler(false);
500 Search::Statistics stat = e.statistics();
501 l_out << endl
502 << "\tpropagators: " << n_p << endl
503 << "\tbranchers: " << n_b << endl
504 << "\truntime: ";
505 stop(t, l_out);
506 l_out << endl
507 << "\tsolutions: " << s_n << endl
508 << "\tpropagations: " << stat.propagate << endl
509 << "\tnodes: " << stat.node << endl
510 << "\tfailures: " << stat.fail << endl
511 << "\trestarts: " << stat.restart << endl
512 << "\tno-goods: " << stat.nogood << endl
513 << "\tpeak depth: " << stat.depth << endl
514#ifdef GECODE_PEAKHEAP
515 << "\tpeak memory: "
516 << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
517 << endl
518#endif
519 << endl;
520 }
521 delete so.stop;
522 }
523 break;
524 case SM_TIME:
525 {
526 l_out << o.name() << endl;
527 Support::Timer t;
528 double* ts = new double[o.samples()];
529 bool stopped = false;
530 for (unsigned int ns = o.samples(); !stopped && ns--; ) {
531 unsigned long long int s_l =
532 (o.solutions() == 0) ? ULLONG_MAX : o.solutions();
533 t.start();
534 for (unsigned int k = o.iterations(); !stopped && k--; ) {
535 unsigned long long int s_n = 0;
536 Script* s1 = new Script(o);
537 Search::Options sok;
538 sok.clone = false;
539 sok.threads = o.threads();
540 sok.assets = o.assets();
541 sok.slice = o.slice();
542 sok.c_d = o.c_d();
543 sok.a_d = o.a_d();
544 sok.d_l = o.d_l();
545 sok.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
546 false);
547 sok.cutoff = createCutoff(o);
548 sok.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
549 {
550 Meta<Script,Engine> e(s1,sok);
551 do {
552 Script* ex = e.next();
553 if (ex == nullptr)
554 break;
555 delete ex;
556 s_n++;
557 } while (s_n < s_l);
558 if (e.stopped())
559 stopped = true;
560 }
561 delete sok.stop;
562 }
563 ts[ns] = t.stop() / o.iterations();
564 }
565 if (stopped) {
566 l_out << "\tSTOPPED" << endl;
567 } else {
568 double m = am(ts,o.samples());
569 double d = dev(ts,o.samples()) * 100.0;
570 l_out << "\truntime: "
571 << setw(20) << right
572 << showpoint << fixed
573 << setprecision(6) << m << "ms"
574 << setprecision(2) << " (" << d << "% deviation)"
575 << endl;
576 }
577 delete [] ts;
578 }
579 break;
580 }
581 } catch (Exception& e) {
582 cerr << "Exception: " << e.what() << "." << endl
583 << "Stopping..." << endl;
584 if (sol_file.is_open())
585 sol_file.close();
586 if (log_file.is_open())
587 log_file.close();
588 exit(EXIT_FAILURE);
589 }
590 if (sol_file.is_open())
591 sol_file.close();
592 if (log_file.is_open())
593 log_file.close();
594 }
595
596}}
597
598// STATISTICS: driver-any