20 #include "absl/container/flat_hash_map.h"
21 #include "absl/strings/str_format.h"
22 #include "absl/strings/str_join.h"
31 "Display all trace information, even if the modifiers has no effect");
36 class TraceIntVar :
public IntVar {
38 TraceIntVar(Solver*
const solver, IntVar*
const inner)
39 : IntVar(solver), inner_(inner) {
40 if (inner->HasName()) {
41 set_name(inner->name());
46 ~TraceIntVar()
override {}
48 int64 Min()
const override {
return inner_->Min(); }
50 void SetMin(
int64 m)
override {
51 if (m > inner_->Min()) {
52 solver()->GetPropagationMonitor()->SetMin(inner_, m);
57 int64 Max()
const override {
return inner_->Max(); }
59 void SetMax(
int64 m)
override {
60 if (m < inner_->Max()) {
61 solver()->GetPropagationMonitor()->SetMax(inner_, m);
66 void Range(
int64* l,
int64* u)
override { inner_->Range(l, u); }
69 if (l > inner_->Min() || u < inner_->Max()) {
71 solver()->GetPropagationMonitor()->SetValue(inner_, l);
74 solver()->GetPropagationMonitor()->SetRange(inner_, l, u);
75 inner_->SetRange(l, u);
80 bool Bound()
const override {
return inner_->Bound(); }
82 bool IsVar()
const override {
return true; }
84 IntVar* Var()
override {
return this; }
86 int64 Value()
const override {
return inner_->Value(); }
88 void RemoveValue(
int64 v)
override {
89 if (inner_->Contains(v)) {
90 solver()->GetPropagationMonitor()->RemoveValue(inner_, v);
91 inner_->RemoveValue(v);
95 void SetValue(
int64 v)
override {
96 solver()->GetPropagationMonitor()->SetValue(inner_, v);
100 void RemoveInterval(
int64 l,
int64 u)
override {
101 solver()->GetPropagationMonitor()->RemoveInterval(inner_, l, u);
102 inner_->RemoveInterval(l, u);
105 void RemoveValues(
const std::vector<int64>& values)
override {
106 solver()->GetPropagationMonitor()->RemoveValues(inner_, values);
107 inner_->RemoveValues(values);
110 void SetValues(
const std::vector<int64>& values)
override {
111 solver()->GetPropagationMonitor()->SetValues(inner_, values);
112 inner_->SetValues(values);
115 void WhenRange(Demon* d)
override { inner_->WhenRange(d); }
117 void WhenBound(Demon* d)
override { inner_->WhenBound(d); }
119 void WhenDomain(Demon* d)
override { inner_->WhenDomain(d); }
121 uint64 Size()
const override {
return inner_->Size(); }
123 bool Contains(
int64 v)
const override {
return inner_->Contains(v); }
125 IntVarIterator* MakeHoleIterator(
bool reversible)
const override {
126 return inner_->MakeHoleIterator(reversible);
129 IntVarIterator* MakeDomainIterator(
bool reversible)
const override {
130 return inner_->MakeDomainIterator(reversible);
133 int64 OldMin()
const override {
return inner_->OldMin(); }
135 int64 OldMax()
const override {
return inner_->OldMax(); }
137 int VarType()
const override {
return TRACE_VAR; }
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);
150 std::string DebugString()
const override {
return inner_->DebugString(); }
152 IntVar* IsEqual(
int64 constant)
override {
return inner_->IsEqual(constant); }
154 IntVar* IsDifferent(
int64 constant)
override {
155 return inner_->IsDifferent(constant);
158 IntVar* IsGreaterOrEqual(
int64 constant)
override {
159 return inner_->IsGreaterOrEqual(constant);
162 IntVar* IsLessOrEqual(
int64 constant)
override {
163 return inner_->IsLessOrEqual(constant);
167 IntVar*
const inner_;
170 class TraceIntExpr :
public IntExpr {
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());
180 ~TraceIntExpr()
override {}
182 int64 Min()
const override {
return inner_->Min(); }
184 void SetMin(
int64 m)
override {
185 solver()->GetPropagationMonitor()->SetMin(inner_, m);
189 int64 Max()
const override {
return inner_->Max(); }
191 void SetMax(
int64 m)
override {
192 solver()->GetPropagationMonitor()->SetMax(inner_, m);
196 void Range(
int64* l,
int64* u)
override { inner_->Range(l, u); }
199 if (l > inner_->Min() || u < inner_->Max()) {
200 solver()->GetPropagationMonitor()->SetRange(inner_, l, u);
201 inner_->SetRange(l, u);
205 bool Bound()
const override {
return inner_->Bound(); }
207 bool IsVar()
const override {
212 IntVar* Var()
override {
return solver()->RegisterIntVar(inner_->Var()); }
214 void WhenRange(Demon* d)
override { inner_->WhenRange(d); }
216 void Accept(ModelVisitor*
const visitor)
const override {
223 std::string DebugString()
const override {
return inner_->DebugString(); }
226 IntExpr*
const inner_;
229 class TraceIntervalVar :
public IntervalVar {
231 TraceIntervalVar(Solver*
const solver, IntervalVar*
const inner)
232 : IntervalVar(solver,
""), inner_(inner) {
233 if (inner->HasName()) {
234 set_name(inner->name());
237 ~TraceIntervalVar()
override {}
239 int64 StartMin()
const override {
return inner_->StartMin(); }
241 int64 StartMax()
const override {
return inner_->StartMax(); }
243 void SetStartMin(
int64 m)
override {
244 if (inner_->MayBePerformed() && (m > inner_->StartMin())) {
245 solver()->GetPropagationMonitor()->SetStartMin(inner_, m);
246 inner_->SetStartMin(m);
250 void SetStartMax(
int64 m)
override {
251 if (inner_->MayBePerformed() && (m < inner_->StartMax())) {
252 solver()->GetPropagationMonitor()->SetStartMax(inner_, m);
253 inner_->SetStartMax(m);
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);
265 int64 OldStartMin()
const override {
return inner_->OldStartMin(); }
267 int64 OldStartMax()
const override {
return inner_->OldStartMax(); }
269 void WhenStartRange(Demon*
const d)
override { inner_->WhenStartRange(d); }
271 void WhenStartBound(Demon*
const d)
override { inner_->WhenStartBound(d); }
273 int64 EndMin()
const override {
return inner_->EndMin(); }
275 int64 EndMax()
const override {
return inner_->EndMax(); }
277 void SetEndMin(
int64 m)
override {
278 if (inner_->MayBePerformed() && (m > inner_->EndMin())) {
279 solver()->GetPropagationMonitor()->SetEndMin(inner_, m);
280 inner_->SetEndMin(m);
284 void SetEndMax(
int64 m)
override {
285 if (inner_->MayBePerformed() && (m < inner_->EndMax())) {
286 solver()->GetPropagationMonitor()->SetEndMax(inner_, m);
287 inner_->SetEndMax(m);
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);
299 int64 OldEndMin()
const override {
return inner_->OldEndMin(); }
301 int64 OldEndMax()
const override {
return inner_->OldEndMax(); }
303 void WhenEndRange(Demon*
const d)
override { inner_->WhenEndRange(d); }
305 void WhenEndBound(Demon*
const d)
override { inner_->WhenStartBound(d); }
307 int64 DurationMin()
const override {
return inner_->DurationMin(); }
309 int64 DurationMax()
const override {
return inner_->DurationMax(); }
311 void SetDurationMin(
int64 m)
override {
312 if (inner_->MayBePerformed() && (m > inner_->DurationMin())) {
313 solver()->GetPropagationMonitor()->SetDurationMin(inner_, m);
314 inner_->SetDurationMin(m);
318 void SetDurationMax(
int64 m)
override {
319 if (inner_->MayBePerformed() && (m < inner_->DurationMax())) {
320 solver()->GetPropagationMonitor()->SetDurationMax(inner_, m);
321 inner_->SetDurationMax(m);
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);
333 int64 OldDurationMin()
const override {
return inner_->OldDurationMin(); }
335 int64 OldDurationMax()
const override {
return inner_->OldDurationMax(); }
337 void WhenDurationRange(Demon*
const d)
override {
338 inner_->WhenDurationRange(d);
341 void WhenDurationBound(Demon*
const d)
override {
342 inner_->WhenDurationBound(d);
345 bool MustBePerformed()
const override {
return inner_->MustBePerformed(); }
347 bool MayBePerformed()
const override {
return inner_->MayBePerformed(); }
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);
357 bool WasPerformedBound()
const override {
358 return inner_->WasPerformedBound();
361 void WhenPerformedBound(Demon*
const d)
override {
362 inner_->WhenPerformedBound(d);
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);
372 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
373 return inner_->SafeDurationExpr(unperformed_value);
375 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
376 return inner_->SafeEndExpr(unperformed_value);
379 void Accept(ModelVisitor*
const visitor)
const override {
380 inner_->Accept(visitor);
383 std::string DebugString()
const override {
return inner_->DebugString(); }
386 IntervalVar*
const inner_;
391 class PrintTrace :
public PropagationMonitor {
409 explicit Context(
int start_indent)
440 explicit PrintTrace(Solver*
const s) : PropagationMonitor(s) {
441 contexes_.push(Context());
444 ~PrintTrace()
override {}
448 void BeginInitialPropagation()
override {
450 DisplaySearch(
"Root Node Propagation");
453 void EndInitialPropagation()
override {
455 DisplaySearch(
"Starting Tree Search");
458 void BeginNextDecision(DecisionBuilder*
const b)
override {
459 DisplaySearch(absl::StrFormat(
"DecisionBuilder(%s)",
b->DebugString()));
461 contexes_.top().in_decision_builder =
true;
465 void EndNextDecision(DecisionBuilder*
const b, Decision*
const d)
override {
466 contexes_.top().in_decision_builder =
false;
470 void BeginFail()
override {
471 contexes_.top().Clear();
472 while (!contexes_.top().TopLevel()) {
477 absl::StrFormat(
"Failure at depth %d", solver()->SearchDepth()));
480 bool AtSolution()
override {
482 absl::StrFormat(
"Solution found at depth %d", solver()->SearchDepth()));
486 void ApplyDecision(Decision*
const decision)
override {
488 absl::StrFormat(
"ApplyDecision(%s)", decision->DebugString()));
490 contexes_.top().in_decision =
true;
493 void RefuteDecision(Decision*
const decision)
override {
494 if (contexes_.top().in_objective) {
496 contexes_.top().in_objective =
false;
499 absl::StrFormat(
"RefuteDecision(%s)", decision->DebugString()));
501 contexes_.top().in_decision =
true;
504 void AfterDecision(Decision*
const decision,
bool direction)
override {
506 contexes_.top().in_decision =
false;
509 void EnterSearch()
override {
510 if (solver()->SolveDepth() == 0) {
512 contexes_.top().Clear();
514 PrintDelayedString();
517 DisplaySearch(
"Enter Search");
520 void ExitSearch()
override {
521 DisplaySearch(
"Exit Search");
522 CHECK(contexes_.top().TopLevel());
523 if (solver()->SolveDepth() > 1) {
528 void RestartSearch()
override {
CHECK(contexes_.top().TopLevel()); }
532 void BeginConstraintInitialPropagation(
533 Constraint*
const constraint)
override {
535 absl::StrFormat(
"Constraint(%s)", constraint->DebugString()));
536 contexes_.top().in_constraint =
true;
539 void EndConstraintInitialPropagation(Constraint*
const constraint)
override {
541 contexes_.top().in_constraint =
false;
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;
549 void EndNestedConstraintInitialPropagation(Constraint*
const,
550 Constraint*
const)
override {
552 contexes_.top().in_constraint =
false;
557 void BeginDemonRun(Demon*
const demon)
override {
559 contexes_.top().in_demon =
true;
560 PushDelayedInfo(absl::StrFormat(
"Demon(%s)", demon->DebugString()));
564 void EndDemonRun(Demon*
const demon)
override {
566 contexes_.top().in_demon =
false;
571 void StartProcessingIntegerVariable(IntVar*
const var)
override {
572 PushDelayedInfo(absl::StrFormat(
"StartProcessing(%s)",
var->DebugString()));
575 void EndProcessingIntegerVariable(IntVar*
const var)
override {
579 void PushContext(
const std::string&
context)
override {
583 void PopContext()
override { PopDelayedInfo(); }
587 void SetMin(IntExpr*
const expr,
int64 new_min)
override {
589 absl::StrFormat(
"SetMin(%s, %d)", expr->DebugString(), new_min));
592 void SetMax(IntExpr*
const expr,
int64 new_max)
override {
594 absl::StrFormat(
"SetMax(%s, %d)", expr->DebugString(), new_max));
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));
604 void SetMin(IntVar*
const var,
int64 new_min)
override {
606 absl::StrFormat(
"SetMin(%s, %d)",
var->DebugString(), new_min));
609 void SetMax(IntVar*
const var,
int64 new_max)
override {
611 absl::StrFormat(
"SetMax(%s, %d)",
var->DebugString(), new_max));
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));
621 absl::StrFormat(
"RemoveValue(%s, %d)",
var->DebugString(),
value));
626 absl::StrFormat(
"SetValue(%s, %d)",
var->DebugString(),
value));
629 void RemoveInterval(IntVar*
const var,
int64 imin,
int64 imax)
override {
630 DisplayModification(absl::StrFormat(
"RemoveInterval(%s, [%d .. %d])",
631 var->DebugString(), imin, imax));
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,
", ")));
639 void RemoveValues(IntVar*
const var,
640 const std::vector<int64>& values)
override {
641 DisplayModification(absl::StrFormat(
"RemoveValues(%s, %s)",
643 absl::StrJoin(values,
", ")));
648 void SetStartMin(IntervalVar*
const var,
int64 new_min)
override {
650 absl::StrFormat(
"SetStartMin(%s, %d)",
var->DebugString(), new_min));
653 void SetStartMax(IntervalVar*
const var,
int64 new_max)
override {
655 absl::StrFormat(
"SetStartMax(%s, %d)",
var->DebugString(), new_max));
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));
664 void SetEndMin(IntervalVar*
const var,
int64 new_min)
override {
666 absl::StrFormat(
"SetEndMin(%s, %d)",
var->DebugString(), new_min));
669 void SetEndMax(IntervalVar*
const var,
int64 new_max)
override {
671 absl::StrFormat(
"SetEndMax(%s, %d)",
var->DebugString(), new_max));
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));
680 void SetDurationMin(IntervalVar*
const var,
int64 new_min)
override {
682 absl::StrFormat(
"SetDurationMin(%s, %d)",
var->DebugString(), new_min));
685 void SetDurationMax(IntervalVar*
const var,
int64 new_max)
override {
687 absl::StrFormat(
"SetDurationMax(%s, %d)",
var->DebugString(), new_max));
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));
696 void SetPerformed(IntervalVar*
const var,
bool value)
override {
698 absl::StrFormat(
"SetPerformed(%s, %d)",
var->DebugString(),
value));
701 void RankFirst(SequenceVar*
const var,
int index)
override {
703 absl::StrFormat(
"RankFirst(%s, %d)",
var->DebugString(),
index));
706 void RankNotFirst(SequenceVar*
const var,
int index)
override {
708 absl::StrFormat(
"RankNotFirst(%s, %d)",
var->DebugString(),
index));
711 void RankLast(SequenceVar*
const var,
int index)
override {
713 absl::StrFormat(
"RankLast(%s, %d)",
var->DebugString(),
index));
716 void RankNotLast(SequenceVar*
const var,
int index)
override {
718 absl::StrFormat(
"RankNotLast(%s, %d)",
var->DebugString(),
index));
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,
", ")));
730 void Install()
override {
732 if (solver()->SolveDepth() <= 1) {
733 solver()->AddPropagationMonitor(
this);
737 std::string DebugString()
const override {
return "PrintTrace"; }
740 void PushDelayedInfo(
const std::string& delayed) {
741 if (absl::GetFlag(FLAGS_cp_full_trace)) {
742 LOG(
INFO) << Indent() << delayed <<
" {";
745 contexes_.top().delayed_info.push_back(Info(delayed));
749 void PopDelayedInfo() {
750 if (absl::GetFlag(FLAGS_cp_full_trace)) {
754 CHECK(!contexes_.top().delayed_info.empty());
755 if (contexes_.top().delayed_info.back().displayed &&
756 !contexes_.top().TopLevel()) {
760 contexes_.top().delayed_info.pop_back();
765 void CheckNoDelayed() {
CHECK(contexes_.top().delayed_info.empty()); }
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 <<
" {";
775 contexes_.top().delayed_info[i].displayed =
true;
780 void DisplayModification(
const std::string& to_print) {
781 if (absl::GetFlag(FLAGS_cp_full_trace)) {
782 LOG(
INFO) << Indent() << to_print;
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) {
789 LOG(
INFO) << Indent() << to_print;
800 CHECK(contexes_.top().TopLevel());
801 DisplaySearch(absl::StrFormat(
"Objective -> %s", to_print));
803 contexes_.top().in_objective =
true;
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;
813 LOG(
INFO) << Indent() <<
"######## Nested Search(" << solve_depth - 1
814 <<
"): " << to_print;
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) {
827 void IncreaseIndent() { contexes_.top().indent++; }
829 void DecreaseIndent() {
830 if (contexes_.top().indent > 0) {
831 contexes_.top().indent--;
835 void PushNestedContext() {
840 std::stack<Context> contexes_;
849 return RevAlloc(
new TraceIntExpr(
this, expr));
874 return s->
RevAlloc(
new PrintTrace(s));