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, 2016
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34namespace Gecode {
35
36 /**
37 * \brief Which events to trace
38 * \ingroup TaskTrace
39 */
40 enum TraceEvent {
41 /// \name Events for view tracers
42 //@{
43 TE_INIT = 1 << 0, ///< Trace init events
44 TE_PRUNE = 1 << 1, ///< Trace prune events
45 TE_FIX = 1 << 2, ///< Trace fixpoint events
46 TE_FAIL = 1 << 3, ///< Trace fail events
47 TE_DONE = 1 << 4, ///< Trace done events
48 //@}
49 /// \name Events for general tracers
50 TE_PROPAGATE = 1 << 5, ///< Trace propagator executions
51 TE_COMMIT = 1 << 6, ///< Trace commit operations by branchers
52 TE_POST = 1 << 7 ///< Trace propagator posting
53 };
54
55 /**
56 * \brief Propagator for recording view trace information
57 * \ingroup TaskTrace
58 */
59 template<class View>
60 class ViewTraceRecorder : public Propagator {
61 public:
62 /// The corresponding duplicate view type
63 typedef typename TraceTraits<View>::TraceView TraceView;
64 /// The corresponding trace delta type
65 typedef typename TraceTraits<View>::TraceDelta TraceDelta;
66 /// The corresponding slack value type
67 typedef typename TraceTraits<View>::SlackValue SlackValue;
68 /// Collection of slack values
69 class Slack {
70 template<class ViewForTraceRecorder> friend class ViewTraceRecorder;
71 protected:
72 /// The initial slack value
73 SlackValue i;
74 /// Slack value at previous event (fixpoint or init)
75 SlackValue p;
76 /// Current slack value
77 SlackValue c;
78 public:
79 /// Return initial slack value
80 SlackValue initial(void) const;
81 /// Return previous slack value
82 SlackValue previous(void) const;
83 /// Return current slack value
84 SlackValue current(void) const;
85 };
86 protected:
87 /// Advisor with index information
88 class Idx : public Advisor {
89 protected:
90 /// Index information
91 int _idx;
92 public:
93 /// Constructor for creation
94 Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
95 /// Constructor for cloning \a a
96 Idx(Space& home, Idx& a);
97 /// Get index of view
98 int idx(void) const;
99 };
100 /// Duplicate views (old information)
101 ViewArray<TraceView> o;
102 /// Original views (new information)
103 ViewArray<View> n;
104 /// The advisor council
105 Council<Idx> c;
106 /// The trace filter
107 TraceFilter tf;
108 /// Which events to trace
109 int te;
110 /// The actual tracer
111 ViewTracer<View>& t;
112 /// Slack information
113 Slack s;
114 /// Constructor for cloning \a p
115 ViewTraceRecorder(Space& home, ViewTraceRecorder& p);
116 public:
117 /// Constructor for creation
118 ViewTraceRecorder(Home home, ViewArray<View>& x,
119 TraceFilter tf, int te, ViewTracer<View>& t);
120 /// Copy propagator during cloning
121 virtual Propagator* copy(Space& home);
122 /// Cost function (record so that propagator runs last)
123 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
124 /// Schedule function
125 virtual void reschedule(Space& home);
126 /// Give advice to propagator
127 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
128 /// Perform propagation
129 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
130 /// Delete propagator and return its size
131 virtual size_t dispose(Space& home);
132 /// Post recorder propagator
133 static ExecStatus post(Home home, ViewArray<View>& x,
134 TraceFilter tf, int te, ViewTracer<View>& t);
135 /// \name Trace information
136 //@{
137 /// Return variable being traced at position \a i
138 const typename View::VarType operator [](int i) const;
139 /// Return number of variables being traced
140 int size(void) const;
141 /// Provide access to slack information
142 const Slack& slack(void) const;
143 //@}
144 };
145
146 /**
147 * \brief Propagator for recording trace information
148 *
149 * This propagator is actually never run. It only provides access
150 * to information needed for tracing.
151 *
152 * \ingroup TaskTrace
153 */
154 class TraceRecorder : public Propagator {
155 public:
156 /// The trace filter
157 TraceFilter tf;
158 /// Which events to trace
159 int te;
160 /// The actual tracer
161 Tracer& t;
162 /// Constructor for cloning \a p
163 TraceRecorder(Space& home, TraceRecorder& p);
164 public:
165 /// Constructor for creation
166 TraceRecorder(Home home, TraceFilter tf, int te, Tracer& t);
167 /// Copy propagator during cloning
168 virtual Propagator* copy(Space& home);
169 /// Cost function (record so that propagator runs last)
170 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
171 /// Schedule function
172 virtual void reschedule(Space& home);
173 /// Perform propagation
174 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
175 /// Delete propagator and return its size
176 virtual size_t dispose(Space& home);
177 /// Post propagator
178 static ExecStatus post(Home home, TraceFilter tf, int te, Tracer& t);
179 /// \name Trace information
180 //@{
181 /// Return trace filter
182 const TraceFilter& filter(void) const;
183 /// Which events to trace
184 int events(void) const;
185 /// Return tracer
186 Tracer& tracer(void) const;
187 //@}
188 };
189
190
191 /*
192 * Functions for trace support
193 *
194 */
195 template<class View>
196 forceinline const typename View::VarType
197 ViewTraceRecorder<View>::operator [](int i) const {
198 const typename View::VarType x(n[i].varimp());
199 return x;
200 }
201 template<class View>
202 forceinline int
203 ViewTraceRecorder<View>::size(void) const {
204 return n.size();
205 }
206 template<class View>
207 forceinline const typename ViewTraceRecorder<View>::Slack&
208 ViewTraceRecorder<View>::slack(void) const {
209 return s;
210 }
211
212
213 /*
214 * Functions for access to slack
215 *
216 */
217 template<class View>
218 forceinline typename ViewTraceRecorder<View>::SlackValue
219 ViewTraceRecorder<View>::Slack::initial(void) const {
220 return i;
221 }
222 template<class View>
223 forceinline typename ViewTraceRecorder<View>::SlackValue
224 ViewTraceRecorder<View>::Slack::previous(void) const {
225 return p;
226 }
227 template<class View>
228 forceinline typename ViewTraceRecorder<View>::SlackValue
229 ViewTraceRecorder<View>::Slack::current(void) const {
230 return c;
231 }
232
233
234 /*
235 * Advisor for tracer
236 *
237 */
238
239 template<class View>
240 forceinline
241 ViewTraceRecorder<View>::Idx::Idx(Space& home, Propagator& p,
242 Council<Idx>& c, int i)
243 : Advisor(home,p,c), _idx(i) {}
244 template<class View>
245 forceinline
246 ViewTraceRecorder<View>::Idx::Idx(Space& home, Idx& a)
247 : Advisor(home,a), _idx(a._idx) {
248 }
249 template<class View>
250 forceinline int
251 ViewTraceRecorder<View>::Idx::idx(void) const {
252 return _idx;
253 }
254
255
256 /*
257 * Posting of tracer propagator
258 *
259 */
260 template<class View>
261 forceinline
262 ViewTraceRecorder<View>::ViewTraceRecorder(Home home, ViewArray<View>& x,
263 TraceFilter tf0, int te0,
264 ViewTracer<View>& t0)
265 : Propagator(home), o(home,x.size()), n(x), c(home),
266 tf(tf0), te(te0), t(t0) {
267 home.notice(*this, AP_VIEW_TRACE);
268 home.notice(*this, AP_DISPOSE);
269 for (int i=0; i<n.size(); i++) {
270 o[i] = TraceView(home,n[i]);
271 if (!n[i].assigned())
272 n[i].subscribe(home,*new (home) Idx(home,*this,c,i));
273 }
274 View::schedule(home,*this,ME_GEN_ASSIGNED);
275 s.i = TraceView::slack(n[0]);
276 for (int i=1; i<n.size(); i++)
277 s.i += TraceView::slack(n[i]);
278 s.p = s.i;
279 if ((te & TE_INIT) != 0)
280 t._init(home,*this);
281 }
282
283
284 template<class View>
285 forceinline ExecStatus
286 ViewTraceRecorder<View>::post(Home home, ViewArray<View>& x,
287 TraceFilter tf, int te, ViewTracer<View>& t) {
288 if ((x.size() > 0) &&
289 (te & (TE_INIT | TE_PRUNE | TE_FIX | TE_FAIL | TE_DONE)))
290 (void) new (home) ViewTraceRecorder(home,x,tf,te,t);
291 return ES_OK;
292 }
293
294
295 /*
296 * Propagation for trace recorder
297 *
298 */
299 template<class View>
300 forceinline
301 ViewTraceRecorder<View>::ViewTraceRecorder(Space& home, ViewTraceRecorder& p)
302 : Propagator(home,p), tf(p.tf), te(p.te), t(p.t), s(p.s) {
303 o.update(home, p.o);
304 n.update(home, p.n);
305 c.update(home, p.c);
306 }
307
308 template<class View>
309 Propagator*
310 ViewTraceRecorder<View>::copy(Space& home) {
311 return new (home) ViewTraceRecorder(home, *this);
312 }
313
314 template<class View>
315 inline size_t
316 ViewTraceRecorder<View>::dispose(Space& home) {
317 home.ignore(*this, AP_VIEW_TRACE);
318 home.ignore(*this, AP_DISPOSE);
319 tf.~TraceFilter();
320 // Cancel remaining advisors
321 for (Advisors<Idx> as(c); as(); ++as)
322 n[as.advisor().idx()].cancel(home,as.advisor());
323 c.dispose(home);
324 (void) Propagator::dispose(home);
325 return sizeof(*this);
326 }
327
328 template<class View>
329 PropCost
330 ViewTraceRecorder<View>::cost(const Space&, const ModEventDelta&) const {
331 return PropCost::record();
332 }
333
334 template<class View>
335 void
336 ViewTraceRecorder<View>::reschedule(Space& home) {
337 View::schedule(home,*this,ME_GEN_ASSIGNED);
338 }
339
340 template<class View>
341 ExecStatus
342 ViewTraceRecorder<View>::advise(Space& home, Advisor& _a, const Delta& d) {
343 Idx& a = static_cast<Idx&>(_a);
344 int i = a.idx();
345 if (((te & TE_PRUNE) != 0) && !disabled() && tf(a(home)) ) {
346 TraceDelta td(o[i],n[i],d);
347 t._prune(home,*this,a(home),i,td);
348 }
349 o[i].prune(home,n[i],d);
350 if (n[a.idx()].assigned())
351 a.dispose(home,c);
352 return ES_NOFIX;
353 }
354
355 template<class View>
356 ExecStatus
357 ViewTraceRecorder<View>::propagate(Space& home, const ModEventDelta&) {
358 s.c = TraceView::slack(n[0]);
359 for (int i=1; i<n.size(); i++)
360 s.c += TraceView::slack(n[i]);
361 if (home.failed() && ((te & TE_FAIL) != 0) && !disabled()) {
362 t._fail(home,*this);
363 return ES_FIX;
364 }
365 if ((te & TE_FIX) != 0)
366 t._fix(home,*this);
367 s.p = s.c;
368 if (c.empty()) {
369 if ((te & TE_DONE) != 0)
370 t._done(home,*this);
371 return home.ES_SUBSUMED(*this);
372 }
373 return ES_FIX;
374 }
375
376
377
378 /*
379 * Functions for trace support
380 *
381 */
382 forceinline const TraceFilter&
383 TraceRecorder::filter(void) const {
384 return tf;
385 }
386 forceinline int
387 TraceRecorder::events(void) const {
388 return te;
389 }
390 forceinline Tracer&
391 TraceRecorder::tracer(void) const {
392 return t;
393 }
394
395
396 /*
397 * Trace recorder propagator
398 *
399 */
400 forceinline
401 TraceRecorder::TraceRecorder(Home home, TraceFilter tf0, int te0,
402 Tracer& t0)
403 : Propagator(home), tf(tf0), te(te0), t(t0) {
404 home.notice(*this, AP_DISPOSE);
405 home.notice(*this, AP_TRACE);
406 }
407
408 forceinline ExecStatus
409 TraceRecorder::post(Home home, TraceFilter tf, int te, Tracer& t) {
410 if (te & (TE_PROPAGATE | TE_COMMIT | TE_POST))
411 (void) new (home) TraceRecorder(home,tf,te,t);
412 return ES_OK;
413 }
414
415 forceinline
416 TraceRecorder::TraceRecorder(Space& home, TraceRecorder& p)
417 : Propagator(home,p), tf(p.tf), te(p.te), t(p.t) {
418 }
419
420}
421
422// STATISTICS: kernel-trace