OR-Tools  8.2
trace.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#include <algorithm>
15#include <cmath>
16#include <stack>
17#include <string>
18#include <utility>
19
20#include "absl/container/flat_hash_map.h"
21#include "absl/strings/str_format.h"
22#include "absl/strings/str_join.h"
29
30ABSL_FLAG(bool, cp_full_trace, false,
31 "Display all trace information, even if the modifiers has no effect");
32
33namespace operations_research {
34namespace {
35// ---------- Code Instrumentation ----------
36class TraceIntVar : public IntVar {
37 public:
38 TraceIntVar(Solver* const solver, IntVar* const inner)
39 : IntVar(solver), inner_(inner) {
40 if (inner->HasName()) {
41 set_name(inner->name());
42 }
43 CHECK_NE(inner->VarType(), TRACE_VAR);
44 }
45
46 ~TraceIntVar() override {}
47
48 int64 Min() const override { return inner_->Min(); }
49
50 void SetMin(int64 m) override {
51 if (m > inner_->Min()) {
52 solver()->GetPropagationMonitor()->SetMin(inner_, m);
53 inner_->SetMin(m);
54 }
55 }
56
57 int64 Max() const override { return inner_->Max(); }
58
59 void SetMax(int64 m) override {
60 if (m < inner_->Max()) {
61 solver()->GetPropagationMonitor()->SetMax(inner_, m);
62 inner_->SetMax(m);
63 }
64 }
65
66 void Range(int64* l, int64* u) override { inner_->Range(l, u); }
67
68 void SetRange(int64 l, int64 u) override {
69 if (l > inner_->Min() || u < inner_->Max()) {
70 if (l == u) {
71 solver()->GetPropagationMonitor()->SetValue(inner_, l);
72 inner_->SetValue(l);
73 } else {
74 solver()->GetPropagationMonitor()->SetRange(inner_, l, u);
75 inner_->SetRange(l, u);
76 }
77 }
78 }
79
80 bool Bound() const override { return inner_->Bound(); }
81
82 bool IsVar() const override { return true; }
83
84 IntVar* Var() override { return this; }
85
86 int64 Value() const override { return inner_->Value(); }
87
88 void RemoveValue(int64 v) override {
89 if (inner_->Contains(v)) {
90 solver()->GetPropagationMonitor()->RemoveValue(inner_, v);
91 inner_->RemoveValue(v);
92 }
93 }
94
95 void SetValue(int64 v) override {
96 solver()->GetPropagationMonitor()->SetValue(inner_, v);
97 inner_->SetValue(v);
98 }
99
100 void RemoveInterval(int64 l, int64 u) override {
101 solver()->GetPropagationMonitor()->RemoveInterval(inner_, l, u);
102 inner_->RemoveInterval(l, u);
103 }
104
105 void RemoveValues(const std::vector<int64>& values) override {
106 solver()->GetPropagationMonitor()->RemoveValues(inner_, values);
107 inner_->RemoveValues(values);
108 }
109
110 void SetValues(const std::vector<int64>& values) override {
111 solver()->GetPropagationMonitor()->SetValues(inner_, values);
112 inner_->SetValues(values);
113 }
114
115 void WhenRange(Demon* d) override { inner_->WhenRange(d); }
116
117 void WhenBound(Demon* d) override { inner_->WhenBound(d); }
118
119 void WhenDomain(Demon* d) override { inner_->WhenDomain(d); }
120
121 uint64 Size() const override { return inner_->Size(); }
122
123 bool Contains(int64 v) const override { return inner_->Contains(v); }
124
125 IntVarIterator* MakeHoleIterator(bool reversible) const override {
126 return inner_->MakeHoleIterator(reversible);
127 }
128
129 IntVarIterator* MakeDomainIterator(bool reversible) const override {
130 return inner_->MakeDomainIterator(reversible);
131 }
132
133 int64 OldMin() const override { return inner_->OldMin(); }
134
135 int64 OldMax() const override { return inner_->OldMax(); }
136
137 int VarType() const override { return TRACE_VAR; }
138
139 void Accept(ModelVisitor* const visitor) const override {
140 IntExpr* const cast_expr =
141 solver()->CastExpression(const_cast<TraceIntVar*>(this));
142 if (cast_expr != nullptr) {
143 visitor->VisitIntegerVariable(this, cast_expr);
144 } else {
145 visitor->VisitIntegerVariable(this, ModelVisitor::kTraceOperation, 0,
146 inner_);
147 }
148 }
149
150 std::string DebugString() const override { return inner_->DebugString(); }
151
152 IntVar* IsEqual(int64 constant) override { return inner_->IsEqual(constant); }
153
154 IntVar* IsDifferent(int64 constant) override {
155 return inner_->IsDifferent(constant);
156 }
157
158 IntVar* IsGreaterOrEqual(int64 constant) override {
159 return inner_->IsGreaterOrEqual(constant);
160 }
161
162 IntVar* IsLessOrEqual(int64 constant) override {
163 return inner_->IsLessOrEqual(constant);
164 }
165
166 private:
167 IntVar* const inner_;
168};
169
170class TraceIntExpr : public IntExpr {
171 public:
172 TraceIntExpr(Solver* const solver, IntExpr* const inner)
173 : IntExpr(solver), inner_(inner) {
174 CHECK(!inner->IsVar());
175 if (inner->HasName()) {
176 set_name(inner->name());
177 }
178 }
179
180 ~TraceIntExpr() override {}
181
182 int64 Min() const override { return inner_->Min(); }
183
184 void SetMin(int64 m) override {
185 solver()->GetPropagationMonitor()->SetMin(inner_, m);
186 inner_->SetMin(m);
187 }
188
189 int64 Max() const override { return inner_->Max(); }
190
191 void SetMax(int64 m) override {
192 solver()->GetPropagationMonitor()->SetMax(inner_, m);
193 inner_->SetMax(m);
194 }
195
196 void Range(int64* l, int64* u) override { inner_->Range(l, u); }
197
198 void SetRange(int64 l, int64 u) override {
199 if (l > inner_->Min() || u < inner_->Max()) {
200 solver()->GetPropagationMonitor()->SetRange(inner_, l, u);
201 inner_->SetRange(l, u);
202 }
203 }
204
205 bool Bound() const override { return inner_->Bound(); }
206
207 bool IsVar() const override {
208 DCHECK(!inner_->IsVar());
209 return false;
210 }
211
212 IntVar* Var() override { return solver()->RegisterIntVar(inner_->Var()); }
213
214 void WhenRange(Demon* d) override { inner_->WhenRange(d); }
215
216 void Accept(ModelVisitor* const visitor) const override {
217 visitor->BeginVisitIntegerExpression(ModelVisitor::kTrace, this);
218 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
219 inner_);
220 visitor->EndVisitIntegerExpression(ModelVisitor::kTrace, this);
221 }
222
223 std::string DebugString() const override { return inner_->DebugString(); }
224
225 private:
226 IntExpr* const inner_;
227};
228
229class TraceIntervalVar : public IntervalVar {
230 public:
231 TraceIntervalVar(Solver* const solver, IntervalVar* const inner)
232 : IntervalVar(solver, ""), inner_(inner) {
233 if (inner->HasName()) {
234 set_name(inner->name());
235 }
236 }
237 ~TraceIntervalVar() override {}
238
239 int64 StartMin() const override { return inner_->StartMin(); }
240
241 int64 StartMax() const override { return inner_->StartMax(); }
242
243 void SetStartMin(int64 m) override {
244 if (inner_->MayBePerformed() && (m > inner_->StartMin())) {
245 solver()->GetPropagationMonitor()->SetStartMin(inner_, m);
246 inner_->SetStartMin(m);
247 }
248 }
249
250 void SetStartMax(int64 m) override {
251 if (inner_->MayBePerformed() && (m < inner_->StartMax())) {
252 solver()->GetPropagationMonitor()->SetStartMax(inner_, m);
253 inner_->SetStartMax(m);
254 }
255 }
256
257 void SetStartRange(int64 mi, int64 ma) override {
258 if (inner_->MayBePerformed() &&
259 (mi > inner_->StartMin() || ma < inner_->StartMax())) {
260 solver()->GetPropagationMonitor()->SetStartRange(inner_, mi, ma);
261 inner_->SetStartRange(mi, ma);
262 }
263 }
264
265 int64 OldStartMin() const override { return inner_->OldStartMin(); }
266
267 int64 OldStartMax() const override { return inner_->OldStartMax(); }
268
269 void WhenStartRange(Demon* const d) override { inner_->WhenStartRange(d); }
270
271 void WhenStartBound(Demon* const d) override { inner_->WhenStartBound(d); }
272
273 int64 EndMin() const override { return inner_->EndMin(); }
274
275 int64 EndMax() const override { return inner_->EndMax(); }
276
277 void SetEndMin(int64 m) override {
278 if (inner_->MayBePerformed() && (m > inner_->EndMin())) {
279 solver()->GetPropagationMonitor()->SetEndMin(inner_, m);
280 inner_->SetEndMin(m);
281 }
282 }
283
284 void SetEndMax(int64 m) override {
285 if (inner_->MayBePerformed() && (m < inner_->EndMax())) {
286 solver()->GetPropagationMonitor()->SetEndMax(inner_, m);
287 inner_->SetEndMax(m);
288 }
289 }
290
291 void SetEndRange(int64 mi, int64 ma) override {
292 if (inner_->MayBePerformed() &&
293 (mi > inner_->EndMin() || ma < inner_->EndMax())) {
294 solver()->GetPropagationMonitor()->SetEndRange(inner_, mi, ma);
295 inner_->SetEndRange(mi, ma);
296 }
297 }
298
299 int64 OldEndMin() const override { return inner_->OldEndMin(); }
300
301 int64 OldEndMax() const override { return inner_->OldEndMax(); }
302
303 void WhenEndRange(Demon* const d) override { inner_->WhenEndRange(d); }
304
305 void WhenEndBound(Demon* const d) override { inner_->WhenStartBound(d); }
306
307 int64 DurationMin() const override { return inner_->DurationMin(); }
308
309 int64 DurationMax() const override { return inner_->DurationMax(); }
310
311 void SetDurationMin(int64 m) override {
312 if (inner_->MayBePerformed() && (m > inner_->DurationMin())) {
313 solver()->GetPropagationMonitor()->SetDurationMin(inner_, m);
314 inner_->SetDurationMin(m);
315 }
316 }
317
318 void SetDurationMax(int64 m) override {
319 if (inner_->MayBePerformed() && (m < inner_->DurationMax())) {
320 solver()->GetPropagationMonitor()->SetDurationMax(inner_, m);
321 inner_->SetDurationMax(m);
322 }
323 }
324
325 void SetDurationRange(int64 mi, int64 ma) override {
326 if (inner_->MayBePerformed() &&
327 (mi > inner_->DurationMin() || ma < inner_->DurationMax())) {
328 solver()->GetPropagationMonitor()->SetDurationRange(inner_, mi, ma);
329 inner_->SetDurationRange(mi, ma);
330 }
331 }
332
333 int64 OldDurationMin() const override { return inner_->OldDurationMin(); }
334
335 int64 OldDurationMax() const override { return inner_->OldDurationMax(); }
336
337 void WhenDurationRange(Demon* const d) override {
338 inner_->WhenDurationRange(d);
339 }
340
341 void WhenDurationBound(Demon* const d) override {
342 inner_->WhenDurationBound(d);
343 }
344
345 bool MustBePerformed() const override { return inner_->MustBePerformed(); }
346
347 bool MayBePerformed() const override { return inner_->MayBePerformed(); }
348
349 void SetPerformed(bool value) override {
350 if ((value && !inner_->MustBePerformed()) ||
351 (!value && inner_->MayBePerformed())) {
352 solver()->GetPropagationMonitor()->SetPerformed(inner_, value);
353 inner_->SetPerformed(value);
354 }
355 }
356
357 bool WasPerformedBound() const override {
358 return inner_->WasPerformedBound();
359 }
360
361 void WhenPerformedBound(Demon* const d) override {
362 inner_->WhenPerformedBound(d);
363 }
364
365 IntExpr* StartExpr() override { return inner_->StartExpr(); }
366 IntExpr* DurationExpr() override { return inner_->DurationExpr(); }
367 IntExpr* EndExpr() override { return inner_->EndExpr(); }
368 IntExpr* PerformedExpr() override { return inner_->PerformedExpr(); }
369 IntExpr* SafeStartExpr(int64 unperformed_value) override {
370 return inner_->SafeStartExpr(unperformed_value);
371 }
372 IntExpr* SafeDurationExpr(int64 unperformed_value) override {
373 return inner_->SafeDurationExpr(unperformed_value);
374 }
375 IntExpr* SafeEndExpr(int64 unperformed_value) override {
376 return inner_->SafeEndExpr(unperformed_value);
377 }
378
379 void Accept(ModelVisitor* const visitor) const override {
380 inner_->Accept(visitor);
381 }
382
383 std::string DebugString() const override { return inner_->DebugString(); }
384
385 private:
386 IntervalVar* const inner_;
387};
388
389// ---------- PrintTrace ----------
390
391class PrintTrace : public PropagationMonitor {
392 public:
393 struct Info {
394 explicit Info(const std::string& m) : message(m), displayed(false) {}
395 std::string message;
397 };
398
399 struct Context {
400 Context()
401 : initial_indent(0),
402 indent(0),
403 in_demon(false),
404 in_constraint(false),
405 in_decision_builder(false),
406 in_decision(false),
407 in_objective(false) {}
408
409 explicit Context(int start_indent)
410 : initial_indent(start_indent),
411 indent(start_indent),
412 in_demon(false),
413 in_constraint(false),
414 in_decision_builder(false),
415 in_decision(false),
416 in_objective(false) {}
417
418 bool TopLevel() const { return initial_indent == indent; }
419
420 void Clear() {
422 in_demon = false;
423 in_constraint = false;
424 in_decision_builder = false;
425 in_decision = false;
426 in_objective = false;
427 delayed_info.clear();
428 }
429
437 std::vector<Info> delayed_info;
438 };
439
440 explicit PrintTrace(Solver* const s) : PropagationMonitor(s) {
441 contexes_.push(Context());
442 }
443
444 ~PrintTrace() override {}
445
446 // ----- Search events -----
447
448 void BeginInitialPropagation() override {
449 CheckNoDelayed();
450 DisplaySearch("Root Node Propagation");
451 IncreaseIndent();
452 }
453 void EndInitialPropagation() override {
454 DecreaseIndent();
455 DisplaySearch("Starting Tree Search");
456 }
457
458 void BeginNextDecision(DecisionBuilder* const b) override {
459 DisplaySearch(absl::StrFormat("DecisionBuilder(%s)", b->DebugString()));
460 IncreaseIndent();
461 contexes_.top().in_decision_builder = true;
462 }
463
464 // After calling DecisionBuilder::Next, along with the returned decision.
465 void EndNextDecision(DecisionBuilder* const b, Decision* const d) override {
466 contexes_.top().in_decision_builder = false;
467 DecreaseIndent();
468 }
469
470 void BeginFail() override {
471 contexes_.top().Clear();
472 while (!contexes_.top().TopLevel()) {
473 DecreaseIndent();
474 LOG(INFO) << Indent() << "}";
475 }
476 DisplaySearch(
477 absl::StrFormat("Failure at depth %d", solver()->SearchDepth()));
478 }
479
480 bool AtSolution() override {
481 DisplaySearch(
482 absl::StrFormat("Solution found at depth %d", solver()->SearchDepth()));
483 return false;
484 }
485
486 void ApplyDecision(Decision* const decision) override {
487 DisplaySearch(
488 absl::StrFormat("ApplyDecision(%s)", decision->DebugString()));
489 IncreaseIndent();
490 contexes_.top().in_decision = true;
491 }
492
493 void RefuteDecision(Decision* const decision) override {
494 if (contexes_.top().in_objective) {
495 DecreaseIndent();
496 contexes_.top().in_objective = false;
497 }
498 DisplaySearch(
499 absl::StrFormat("RefuteDecision(%s)", decision->DebugString()));
500 IncreaseIndent();
501 contexes_.top().in_decision = true;
502 }
503
504 void AfterDecision(Decision* const decision, bool direction) override {
505 DecreaseIndent();
506 contexes_.top().in_decision = false;
507 }
508
509 void EnterSearch() override {
510 if (solver()->SolveDepth() == 0) {
511 CHECK_EQ(1, contexes_.size());
512 contexes_.top().Clear();
513 } else {
514 PrintDelayedString();
515 PushNestedContext();
516 }
517 DisplaySearch("Enter Search");
518 }
519
520 void ExitSearch() override {
521 DisplaySearch("Exit Search");
522 CHECK(contexes_.top().TopLevel());
523 if (solver()->SolveDepth() > 1) {
524 contexes_.pop();
525 }
526 }
527
528 void RestartSearch() override { CHECK(contexes_.top().TopLevel()); }
529
530 // ----- Propagation events -----
531
532 void BeginConstraintInitialPropagation(
533 Constraint* const constraint) override {
534 PushDelayedInfo(
535 absl::StrFormat("Constraint(%s)", constraint->DebugString()));
536 contexes_.top().in_constraint = true;
537 }
538
539 void EndConstraintInitialPropagation(Constraint* const constraint) override {
540 PopDelayedInfo();
541 contexes_.top().in_constraint = false;
542 }
543
544 void BeginNestedConstraintInitialPropagation(
545 Constraint* const parent, Constraint* const nested) override {
546 PushDelayedInfo(absl::StrFormat("Constraint(%s)", nested->DebugString()));
547 contexes_.top().in_constraint = true;
548 }
549 void EndNestedConstraintInitialPropagation(Constraint* const,
550 Constraint* const) override {
551 PopDelayedInfo();
552 contexes_.top().in_constraint = false;
553 }
554
555 void RegisterDemon(Demon* const demon) override {}
556
557 void BeginDemonRun(Demon* const demon) override {
558 if (demon->priority() != Solver::VAR_PRIORITY) {
559 contexes_.top().in_demon = true;
560 PushDelayedInfo(absl::StrFormat("Demon(%s)", demon->DebugString()));
561 }
562 }
563
564 void EndDemonRun(Demon* const demon) override {
565 if (demon->priority() != Solver::VAR_PRIORITY) {
566 contexes_.top().in_demon = false;
567 PopDelayedInfo();
568 }
569 }
570
571 void StartProcessingIntegerVariable(IntVar* const var) override {
572 PushDelayedInfo(absl::StrFormat("StartProcessing(%s)", var->DebugString()));
573 }
574
575 void EndProcessingIntegerVariable(IntVar* const var) override {
576 PopDelayedInfo();
577 }
578
579 void PushContext(const std::string& context) override {
580 PushDelayedInfo(context);
581 }
582
583 void PopContext() override { PopDelayedInfo(); }
584
585 // ----- IntExpr modifiers -----
586
587 void SetMin(IntExpr* const expr, int64 new_min) override {
588 DisplayModification(
589 absl::StrFormat("SetMin(%s, %d)", expr->DebugString(), new_min));
590 }
591
592 void SetMax(IntExpr* const expr, int64 new_max) override {
593 DisplayModification(
594 absl::StrFormat("SetMax(%s, %d)", expr->DebugString(), new_max));
595 }
596
597 void SetRange(IntExpr* const expr, int64 new_min, int64 new_max) override {
598 DisplayModification(absl::StrFormat("SetRange(%s, [%d .. %d])",
599 expr->DebugString(), new_min, new_max));
600 }
601
602 // ----- IntVar modifiers -----
603
604 void SetMin(IntVar* const var, int64 new_min) override {
605 DisplayModification(
606 absl::StrFormat("SetMin(%s, %d)", var->DebugString(), new_min));
607 }
608
609 void SetMax(IntVar* const var, int64 new_max) override {
610 DisplayModification(
611 absl::StrFormat("SetMax(%s, %d)", var->DebugString(), new_max));
612 }
613
614 void SetRange(IntVar* const var, int64 new_min, int64 new_max) override {
615 DisplayModification(absl::StrFormat("SetRange(%s, [%d .. %d])",
616 var->DebugString(), new_min, new_max));
617 }
618
619 void RemoveValue(IntVar* const var, int64 value) override {
620 DisplayModification(
621 absl::StrFormat("RemoveValue(%s, %d)", var->DebugString(), value));
622 }
623
624 void SetValue(IntVar* const var, int64 value) override {
625 DisplayModification(
626 absl::StrFormat("SetValue(%s, %d)", var->DebugString(), value));
627 }
628
629 void RemoveInterval(IntVar* const var, int64 imin, int64 imax) override {
630 DisplayModification(absl::StrFormat("RemoveInterval(%s, [%d .. %d])",
631 var->DebugString(), imin, imax));
632 }
633
634 void SetValues(IntVar* const var, const std::vector<int64>& values) override {
635 DisplayModification(absl::StrFormat("SetValues(%s, %s)", var->DebugString(),
636 absl::StrJoin(values, ", ")));
637 }
638
639 void RemoveValues(IntVar* const var,
640 const std::vector<int64>& values) override {
641 DisplayModification(absl::StrFormat("RemoveValues(%s, %s)",
642 var->DebugString(),
643 absl::StrJoin(values, ", ")));
644 }
645
646 // ----- IntervalVar modifiers -----
647
648 void SetStartMin(IntervalVar* const var, int64 new_min) override {
649 DisplayModification(
650 absl::StrFormat("SetStartMin(%s, %d)", var->DebugString(), new_min));
651 }
652
653 void SetStartMax(IntervalVar* const var, int64 new_max) override {
654 DisplayModification(
655 absl::StrFormat("SetStartMax(%s, %d)", var->DebugString(), new_max));
656 }
657
658 void SetStartRange(IntervalVar* const var, int64 new_min,
659 int64 new_max) override {
660 DisplayModification(absl::StrFormat("SetStartRange(%s, [%d .. %d])",
661 var->DebugString(), new_min, new_max));
662 }
663
664 void SetEndMin(IntervalVar* const var, int64 new_min) override {
665 DisplayModification(
666 absl::StrFormat("SetEndMin(%s, %d)", var->DebugString(), new_min));
667 }
668
669 void SetEndMax(IntervalVar* const var, int64 new_max) override {
670 DisplayModification(
671 absl::StrFormat("SetEndMax(%s, %d)", var->DebugString(), new_max));
672 }
673
674 void SetEndRange(IntervalVar* const var, int64 new_min,
675 int64 new_max) override {
676 DisplayModification(absl::StrFormat("SetEndRange(%s, [%d .. %d])",
677 var->DebugString(), new_min, new_max));
678 }
679
680 void SetDurationMin(IntervalVar* const var, int64 new_min) override {
681 DisplayModification(
682 absl::StrFormat("SetDurationMin(%s, %d)", var->DebugString(), new_min));
683 }
684
685 void SetDurationMax(IntervalVar* const var, int64 new_max) override {
686 DisplayModification(
687 absl::StrFormat("SetDurationMax(%s, %d)", var->DebugString(), new_max));
688 }
689
690 void SetDurationRange(IntervalVar* const var, int64 new_min,
691 int64 new_max) override {
692 DisplayModification(absl::StrFormat("SetDurationRange(%s, [%d .. %d])",
693 var->DebugString(), new_min, new_max));
694 }
695
696 void SetPerformed(IntervalVar* const var, bool value) override {
697 DisplayModification(
698 absl::StrFormat("SetPerformed(%s, %d)", var->DebugString(), value));
699 }
700
701 void RankFirst(SequenceVar* const var, int index) override {
702 DisplayModification(
703 absl::StrFormat("RankFirst(%s, %d)", var->DebugString(), index));
704 }
705
706 void RankNotFirst(SequenceVar* const var, int index) override {
707 DisplayModification(
708 absl::StrFormat("RankNotFirst(%s, %d)", var->DebugString(), index));
709 }
710
711 void RankLast(SequenceVar* const var, int index) override {
712 DisplayModification(
713 absl::StrFormat("RankLast(%s, %d)", var->DebugString(), index));
714 }
715
716 void RankNotLast(SequenceVar* const var, int index) override {
717 DisplayModification(
718 absl::StrFormat("RankNotLast(%s, %d)", var->DebugString(), index));
719 }
720
721 void RankSequence(SequenceVar* const var, const std::vector<int>& rank_first,
722 const std::vector<int>& rank_last,
723 const std::vector<int>& unperformed) override {
724 DisplayModification(absl::StrFormat(
725 "RankSequence(%s, forward [%s], backward[%s], unperformed[%s])",
726 var->DebugString(), absl::StrJoin(rank_first, ", "),
727 absl::StrJoin(rank_last, ", "), absl::StrJoin(unperformed, ", ")));
728 }
729
730 void Install() override {
732 if (solver()->SolveDepth() <= 1) {
733 solver()->AddPropagationMonitor(this);
734 }
735 }
736
737 std::string DebugString() const override { return "PrintTrace"; }
738
739 private:
740 void PushDelayedInfo(const std::string& delayed) {
741 if (absl::GetFlag(FLAGS_cp_full_trace)) {
742 LOG(INFO) << Indent() << delayed << " {";
743 IncreaseIndent();
744 } else {
745 contexes_.top().delayed_info.push_back(Info(delayed));
746 }
747 }
748
749 void PopDelayedInfo() {
750 if (absl::GetFlag(FLAGS_cp_full_trace)) {
751 DecreaseIndent();
752 LOG(INFO) << Indent() << "}";
753 } else {
754 CHECK(!contexes_.top().delayed_info.empty());
755 if (contexes_.top().delayed_info.back().displayed &&
756 !contexes_.top().TopLevel()) {
757 DecreaseIndent();
758 LOG(INFO) << Indent() << "}";
759 } else {
760 contexes_.top().delayed_info.pop_back();
761 }
762 }
763 }
764
765 void CheckNoDelayed() { CHECK(contexes_.top().delayed_info.empty()); }
766
767 void PrintDelayedString() {
768 const std::vector<Info>& infos = contexes_.top().delayed_info;
769 for (int i = 0; i < infos.size(); ++i) {
770 const Info& info = infos[i];
771 if (!info.displayed) {
772 LOG(INFO) << Indent() << info.message << " {";
773 IncreaseIndent();
774 // Marks it as displayed.
775 contexes_.top().delayed_info[i].displayed = true;
776 }
777 }
778 }
779
780 void DisplayModification(const std::string& to_print) {
781 if (absl::GetFlag(FLAGS_cp_full_trace)) {
782 LOG(INFO) << Indent() << to_print;
783 } else {
784 PrintDelayedString();
785 if (contexes_.top().in_demon || contexes_.top().in_constraint ||
786 contexes_.top().in_decision_builder || contexes_.top().in_decision ||
787 contexes_.top().in_objective) {
788 // Inside a demon, constraint, decision builder -> normal print.
789 LOG(INFO) << Indent() << to_print;
790 } else {
791 // Top level, modification pushed by the objective. This is a
792 // hack. The SetMax or SetMin done by the objective happens in
793 // the RefuteDecision callback of search monitors. We cannot
794 // easily differentiate that from the actual modifications done
795 // by the Refute() call itself. To distinguish that, we force
796 // the print trace to be last in the list of monitors. Thus
797 // modifications that happens at the top level before the
798 // RefuteDecision() callbacks must be from the objective.
799 // In that case, we push the in_objective context.
800 CHECK(contexes_.top().TopLevel());
801 DisplaySearch(absl::StrFormat("Objective -> %s", to_print));
802 IncreaseIndent();
803 contexes_.top().in_objective = true;
804 }
805 }
806 }
807
808 void DisplaySearch(const std::string& to_print) {
809 const int solve_depth = solver()->SolveDepth();
810 if (solve_depth <= 1) {
811 LOG(INFO) << Indent() << "######## Top Level Search: " << to_print;
812 } else {
813 LOG(INFO) << Indent() << "######## Nested Search(" << solve_depth - 1
814 << "): " << to_print;
815 }
816 }
817
818 std::string Indent() {
819 CHECK_GE(contexes_.top().indent, 0);
820 std::string output = " @ ";
821 for (int i = 0; i < contexes_.top().indent; ++i) {
822 output.append(" ");
823 }
824 return output;
825 }
826
827 void IncreaseIndent() { contexes_.top().indent++; }
828
829 void DecreaseIndent() {
830 if (contexes_.top().indent > 0) {
831 contexes_.top().indent--;
832 }
833 }
834
835 void PushNestedContext() {
836 const int initial_indent = contexes_.top().indent;
837 contexes_.push(Context(initial_indent));
838 }
839
840 std::stack<Context> contexes_;
841};
842} // namespace
843
845 if (InstrumentsVariables()) {
846 if (expr->IsVar()) {
847 return RegisterIntVar(expr->Var());
848 } else {
849 return RevAlloc(new TraceIntExpr(this, expr));
850 }
851 } else {
852 return expr;
853 }
854}
855
857 if (InstrumentsVariables() && var->VarType() != TRACE_VAR) { // Not already a
858 // trace var.
859 return RevAlloc(new TraceIntVar(this, var));
860 } else {
861 return var;
862 }
863}
864
866 if (InstrumentsVariables()) {
867 return RevAlloc(new TraceIntervalVar(this, var));
868 } else {
869 return var;
870 }
871}
872
874 return s->RevAlloc(new PrintTrace(s));
875}
876} // namespace operations_research
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
The class IntExpr is the base of all integer expressions in constraint programming.
virtual bool IsVar() const
Returns true if the expression is indeed a variable.
virtual IntVar * Var()=0
Creates a variable from the expression.
The class IntVar is a subset of IntExpr.
Interval variables are often used in scheduling.
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
IntExpr * RegisterIntExpr(IntExpr *const expr)
Registers a new IntExpr and wraps it inside a TraceIntExpr if necessary.
Definition: trace.cc:844
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
IntVar * RegisterIntVar(IntVar *const var)
Registers a new IntVar and wraps it inside a TraceIntVar if necessary.
Definition: trace.cc:856
bool InstrumentsVariables() const
Returns whether we are tracing variables.
T * RevAlloc(T *object)
Registers the given object as being reversible.
IntervalVar * RegisterIntervalVar(IntervalVar *const var)
Registers a new IntervalVar and wraps it inside a TraceIntervalVar if necessary.
Definition: trace.cc:865
int64 value
IntVar * var
Definition: expr_array.cc:1858
GurobiMPCallbackContext * context
int64_t int64
uint64_t uint64
const int INFO
Definition: log_severity.h:31
std::function< int64(const Model &)> Value(IntegerVariable v)
Definition: integer.h:1487
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
PropagationMonitor * BuildPrintTrace(Solver *const s)
Definition: trace.cc:873
void RegisterDemon(Solver *const solver, Demon *const demon, DemonProfiler *const monitor)
int index
Definition: pack.cc:508
bool in_decision_builder
Definition: trace.cc:434
bool in_decision
Definition: trace.cc:435
bool displayed
Definition: trace.cc:396
std::string message
Definition: trace.cc:395
int initial_indent
Definition: trace.cc:430
int indent
Definition: trace.cc:431
std::vector< Info > delayed_info
Definition: trace.cc:437
bool in_demon
Definition: trace.cc:432
bool in_objective
Definition: trace.cc:436
bool in_constraint
Definition: trace.cc:433
ABSL_FLAG(bool, cp_full_trace, false, "Display all trace information, even if the modifiers has no effect")