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