dekker.one
this repo has no description
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 getInfo = new ScriptGetInfo<BaseSpace>;
361 so.tracer = new CPProfilerSearchTracer
362 (o.profiler_id(), o.name(), o.profiler_port(), getInfo);
363 }
364#endif
365 l_out << o.name() << endl;
366 Support::Timer t;
367 unsigned long long int s_l =
368 (o.solutions() == 0) ? ULLONG_MAX : o.solutions();
369 unsigned long long int s_n = 0;
370 t.start();
371 if (s == nullptr)
372 s = new Script(o);
373 unsigned int n_p = PropagatorGroup::all.size(*s);
374 unsigned int n_b = BrancherGroup::all.size(*s);
375 so.threads = o.threads();
376 so.c_d = o.c_d();
377 so.a_d = o.a_d();
378 so.d_l = o.d_l();
379 so.assets = o.assets();
380 so.slice = o.slice();
381 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
382 o.interrupt());
383 so.cutoff = createCutoff(o);
384 so.clone = false;
385 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
386 if (o.interrupt())
387 CombinedStop::installCtrlHandler(true);
388 {
389 Meta<Script,Engine> e(s,so);
390 if (o.print_last()) {
391 Script* px = nullptr;
392 do {
393 Script* ex = e.next();
394 if (ex == nullptr) {
395 if (px != nullptr) {
396 px->print(s_out);
397 delete px;
398 }
399 break;
400 } else {
401 s_n++;
402 delete px;
403 px = ex;
404 }
405 } while (s_n < s_l);
406 } else {
407 do {
408 Script* ex = e.next();
409 if (ex == nullptr)
410 break;
411 ex->print(s_out);
412 delete ex;
413 s_n++;
414 } while (s_n < s_l);
415 }
416 if (o.interrupt())
417 CombinedStop::installCtrlHandler(false);
418 Search::Statistics stat = e.statistics();
419 s_out << endl;
420 if (e.stopped()) {
421 l_out << "Search engine stopped..." << endl
422 << "\treason: ";
423 int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
424 if (r & CombinedStop::SR_INT)
425 l_out << "user interrupt " << endl;
426 else {
427 if (r & CombinedStop::SR_NODE)
428 l_out << "node ";
429 if (r & CombinedStop::SR_FAIL)
430 l_out << "fail ";
431 if (r & CombinedStop::SR_TIME)
432 l_out << "time ";
433 l_out << "limit reached" << endl << endl;
434 }
435 }
436 l_out << "Initial" << endl
437 << "\tpropagators: " << n_p << endl
438 << "\tbranchers: " << n_b << endl
439 << endl
440 << "Summary" << endl
441 << "\truntime: ";
442 stop(t, l_out);
443 l_out << endl
444 << "\tsolutions: " << s_n << endl
445 << "\tpropagations: " << stat.propagate << endl
446 << "\tnodes: " << stat.node << endl
447 << "\tfailures: " << stat.fail << endl
448 << "\trestarts: " << stat.restart << endl
449 << "\tno-goods: " << stat.nogood << endl
450 << "\tpeak depth: " << stat.depth << endl
451#ifdef GECODE_PEAKHEAP
452 << "\tpeak memory: "
453 << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
454 << endl
455#endif
456 << endl;
457 }
458 delete so.stop;
459 delete so.tracer;
460 }
461 break;
462 case SM_STAT:
463 {
464 l_out << o.name() << endl;
465 Support::Timer t;
466 unsigned long long int s_l =
467 (o.solutions() == 0) ? ULLONG_MAX : o.solutions();
468 unsigned long long int s_n = 0;
469 t.start();
470 if (s == nullptr)
471 s = new Script(o);
472 unsigned int n_p = PropagatorGroup::all.size(*s);
473 unsigned int n_b = BrancherGroup::all.size(*s);
474
475 so.clone = false;
476 so.threads = o.threads();
477 so.assets = o.assets();
478 so.slice = o.slice();
479 so.c_d = o.c_d();
480 so.a_d = o.a_d();
481 so.d_l = o.d_l();
482 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
483 o.interrupt());
484 so.cutoff = createCutoff(o);
485 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
486 if (o.interrupt())
487 CombinedStop::installCtrlHandler(true);
488 {
489 Meta<Script,Engine> e(s,so);
490 do {
491 Script* ex = e.next();
492 if (ex == nullptr)
493 break;
494 delete ex;
495 s_n++;
496 } while (s_n < s_l);
497 if (o.interrupt())
498 CombinedStop::installCtrlHandler(false);
499 Search::Statistics stat = e.statistics();
500 l_out << endl
501 << "\tpropagators: " << n_p << endl
502 << "\tbranchers: " << n_b << endl
503 << "\truntime: ";
504 stop(t, l_out);
505 l_out << endl
506 << "\tsolutions: " << s_n << endl
507 << "\tpropagations: " << stat.propagate << endl
508 << "\tnodes: " << stat.node << endl
509 << "\tfailures: " << stat.fail << endl
510 << "\trestarts: " << stat.restart << endl
511 << "\tno-goods: " << stat.nogood << endl
512 << "\tpeak depth: " << stat.depth << endl
513#ifdef GECODE_PEAKHEAP
514 << "\tpeak memory: "
515 << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
516 << endl
517#endif
518 << endl;
519 }
520 delete so.stop;
521 }
522 break;
523 case SM_TIME:
524 {
525 l_out << o.name() << endl;
526 Support::Timer t;
527 double* ts = new double[o.samples()];
528 bool stopped = false;
529 for (unsigned int ns = o.samples(); !stopped && ns--; ) {
530 unsigned long long int s_l =
531 (o.solutions() == 0) ? ULLONG_MAX : o.solutions();
532 t.start();
533 for (unsigned int k = o.iterations(); !stopped && k--; ) {
534 unsigned long long int s_n = 0;
535 Script* s1 = new Script(o);
536 Search::Options sok;
537 sok.clone = false;
538 sok.threads = o.threads();
539 sok.assets = o.assets();
540 sok.slice = o.slice();
541 sok.c_d = o.c_d();
542 sok.a_d = o.a_d();
543 sok.d_l = o.d_l();
544 sok.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
545 false);
546 sok.cutoff = createCutoff(o);
547 sok.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
548 {
549 Meta<Script,Engine> e(s1,sok);
550 do {
551 Script* ex = e.next();
552 if (ex == nullptr)
553 break;
554 delete ex;
555 s_n++;
556 } while (s_n < s_l);
557 if (e.stopped())
558 stopped = true;
559 }
560 delete sok.stop;
561 }
562 ts[ns] = t.stop() / o.iterations();
563 }
564 if (stopped) {
565 l_out << "\tSTOPPED" << endl;
566 } else {
567 double m = am(ts,o.samples());
568 double d = dev(ts,o.samples()) * 100.0;
569 l_out << "\truntime: "
570 << setw(20) << right
571 << showpoint << fixed
572 << setprecision(6) << m << "ms"
573 << setprecision(2) << " (" << d << "% deviation)"
574 << endl;
575 }
576 delete [] ts;
577 }
578 break;
579 }
580 } catch (Exception& e) {
581 cerr << "Exception: " << e.what() << "." << endl
582 << "Stopping..." << endl;
583 if (sol_file.is_open())
584 sol_file.close();
585 if (log_file.is_open())
586 log_file.close();
587 exit(EXIT_FAILURE);
588 }
589 if (sol_file.is_open())
590 sol_file.close();
591 if (log_file.is_open())
592 log_file.close();
593 }
594
595}}
596
597// STATISTICS: driver-any