Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set

// doxy/ or-tools/ src/ constraint_solver/

or-tools/src/constraint_solver/trace.cc

Go to the documentation of this file.

// Copyright 2010-2012 Google
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include <math.h>
#include <string.h>
#include <algorithm>
#include "base/hash.h"
#include <stack>
#include <string>
#include <utility>

#include "base/commandlineflags.h"
#include "base/integral_types.h"
#include "base/logging.h"
#include "base/scoped_ptr.h"
#include "base/stringprintf.h"
#include "base/map-util.h"
#include "constraint_solver/constraint_solver.h"
#include "constraint_solver/constraint_solveri.h"
#include "util/string_array.h"

namespace operations_research {
namespace {
// ---------- Code Instrumentation ----------
class TraceIntVar : public IntVar {
 public:
  TraceIntVar(Solver* const solver, IntVar* const inner)
      : IntVar(solver), inner_(inner) {
    if (inner->HasName()) {
      set_name(inner->name());
    }
    CHECK_NE(inner->VarType(), TRACE_VAR);
  }

  virtual ~TraceIntVar() {}

  virtual int64 Min() const { return inner_->Min(); }

  virtual void SetMin(int64 m) {
    if (m > inner_->Min()) {
      solver()->GetPropagationMonitor()->SetMin(inner_, m);
      inner_->SetMin(m);
    }
  }

  virtual int64 Max() const { return inner_->Max(); }

  virtual void SetMax(int64 m) {
    if (m < inner_->Max()) {
      solver()->GetPropagationMonitor()->SetMax(inner_, m);
      inner_->SetMax(m);
    }
  }

  virtual void Range(int64* l, int64* u) {
    inner_->Range(l, u);
  }

  virtual void SetRange(int64 l, int64 u) {
    if (l > inner_->Min() || u < inner_->Max()) {
      if (l == u) {
        solver()->GetPropagationMonitor()->SetValue(inner_, l);
        inner_->SetValue(l);
      } else {
        solver()->GetPropagationMonitor()->SetRange(inner_, l, u);
        inner_->SetRange(l, u);
      }
    }
  }

  virtual bool Bound() const {
    return inner_->Bound();
  }

  virtual bool IsVar() const { return true; }

  virtual IntVar* Var() { return this; }

  virtual int64 Value() const {
    return inner_->Value();
  }

  virtual void RemoveValue(int64 v) {
    if (inner_->Contains(v)) {
      solver()->GetPropagationMonitor()->RemoveValue(inner_, v);
      inner_->RemoveValue(v);
    }
  }

  virtual void SetValue(int64 v) {
    solver()->GetPropagationMonitor()->SetValue(inner_, v);
    inner_->SetValue(v);
  }

  virtual void RemoveInterval(int64 l, int64 u) {
    solver()->GetPropagationMonitor()->RemoveInterval(inner_, l, u);
    inner_->RemoveInterval(l, u);
  }

  virtual void RemoveValues(const int64* const values, int size) {
    solver()->GetPropagationMonitor()->RemoveValues(inner_, values, size);
    inner_->RemoveValues(values, size);
  }

  virtual void SetValues(const int64* const values, int size) {
    solver()->GetPropagationMonitor()->SetValues(inner_, values, size);
    inner_->SetValues(values, size);
  }

  virtual void WhenRange(Demon* d) {
    inner_->WhenRange(d);
  }

  virtual void WhenBound(Demon* d) {
    inner_->WhenBound(d);
  }

  virtual void WhenDomain(Demon* d) {
    inner_->WhenDomain(d);
  }

  virtual uint64 Size() const {
    return inner_->Size();
  }

  virtual bool Contains(int64 v) const {
    return inner_->Contains(v);
  }

  virtual IntVarIterator* MakeHoleIterator(bool reversible) const {
    return inner_->MakeHoleIterator(reversible);
  }

  virtual IntVarIterator* MakeDomainIterator(bool reversible) const {
    return inner_->MakeDomainIterator(reversible);
  }

  virtual int64 OldMin() const {
    return inner_->OldMin();
  }

  virtual int64 OldMax() const {
    return inner_->OldMax();
  }

  virtual int VarType() const {
    return TRACE_VAR;
  }

  virtual void Accept(ModelVisitor* const visitor) const {
    inner_->Accept(visitor);
  }

  virtual string DebugString() const {
    return inner_->DebugString();
  }

 private:
  IntVar* const inner_;
};


class TraceIntExpr : public IntExpr {
 public:
  TraceIntExpr(Solver* const solver, IntExpr* const inner)
      : IntExpr(solver), inner_(inner) {
    CHECK(!inner->IsVar());
    if (inner->HasName()) {
      set_name(inner->name());
    }
  }

  virtual ~TraceIntExpr() {}

  virtual int64 Min() const { return inner_->Min(); }

  virtual void SetMin(int64 m) {
    solver()->GetPropagationMonitor()->SetMin(inner_, m);
    inner_->SetMin(m);
  }

  virtual int64 Max() const { return inner_->Max(); }

  virtual void SetMax(int64 m) {
    solver()->GetPropagationMonitor()->SetMax(inner_, m);
    inner_->SetMax(m);
  }

  virtual void Range(int64* l, int64* u) {
    inner_->Range(l, u);
  }

  virtual void SetRange(int64 l, int64 u) {
    if (l > inner_->Min() || u < inner_->Max()) {
      solver()->GetPropagationMonitor()->SetRange(inner_, l, u);
      inner_->SetRange(l, u);
    }
  }

  virtual bool Bound() const {
    return inner_->Bound();
  }

  virtual bool IsVar() const {
    DCHECK(!inner_->IsVar());
    return false;
  }

  virtual IntVar* Var() {
    return solver()->RegisterIntVar(inner_->Var());
  }

  virtual void WhenRange(Demon* d) {
    inner_->WhenRange(d);
  }

  virtual void Accept(ModelVisitor* const visitor) const {
    inner_->Accept(visitor);
  }

  virtual string DebugString() const {
    return inner_->DebugString();
  }

 private:
  IntExpr* const inner_;
};

class TraceIntervalVar : public IntervalVar {
 public:
  TraceIntervalVar(Solver* const solver, IntervalVar* const inner)
      : IntervalVar(solver, ""), inner_(inner) {
    if (inner->HasName()) {
      set_name(inner->name());
    }
  }
  virtual ~TraceIntervalVar() {}

  virtual int64 StartMin() const {
    return inner_->StartMin();
  }

  virtual int64 StartMax() const  {
    return inner_->StartMax();
  }

  virtual void SetStartMin(int64 m) {
    if (m > inner_->StartMin()) {
      solver()->GetPropagationMonitor()->SetStartMin(inner_, m);
      inner_->SetStartMin(m);
    }
  }

  virtual void SetStartMax(int64 m) {
    if (m < inner_->StartMax()) {
      solver()->GetPropagationMonitor()->SetStartMax(inner_, m);
      inner_->SetStartMax(m);
    }
  }

  virtual void SetStartRange(int64 mi, int64 ma) {
    if (mi > inner_->StartMin() || ma < inner_->StartMax()) {
      solver()->GetPropagationMonitor()->SetStartRange(inner_, mi, ma);
      inner_->SetStartRange(mi, ma);
    }
  }

  virtual void WhenStartRange(Demon* const d) {
    inner_->WhenStartRange(d);
  }

  virtual void WhenStartBound(Demon* const d) {
    inner_->WhenStartBound(d);
  }

  virtual int64 EndMin() const {
    return inner_->EndMin();
  }

  virtual int64 EndMax() const  {
    return inner_->EndMax();
  }

  virtual void SetEndMin(int64 m) {
    if (m > inner_->EndMin()) {
      solver()->GetPropagationMonitor()->SetEndMin(inner_, m);
      inner_->SetEndMin(m);
    }
  }

  virtual void SetEndMax(int64 m) {
    if (m < inner_->EndMax()) {
      solver()->GetPropagationMonitor()->SetEndMax(inner_, m);
      inner_->SetEndMax(m);
    }
  }

  virtual void SetEndRange(int64 mi, int64 ma) {
    if (mi > inner_->EndMin() || ma < inner_->EndMax()) {
      solver()->GetPropagationMonitor()->SetEndRange(inner_, mi, ma);
      inner_->SetEndRange(mi, ma);
    }
  }

  virtual void WhenEndRange(Demon* const d) {
    inner_->WhenEndRange(d);
  }

  virtual void WhenEndBound(Demon* const d) {
    inner_->WhenStartBound(d);
  }

  virtual int64 DurationMin() const {
    return inner_->DurationMin();
  }

  virtual int64 DurationMax() const  {
    return inner_->DurationMax();
  }

  virtual void SetDurationMin(int64 m) {
    if (m > inner_->DurationMin()) {
      solver()->GetPropagationMonitor()->SetDurationMin(inner_, m);
      inner_->SetDurationMin(m);
    }
  }

  virtual void SetDurationMax(int64 m) {
    if (m < inner_->DurationMax()) {
      solver()->GetPropagationMonitor()->SetDurationMax(inner_, m);
      inner_->SetDurationMax(m);
    }
  }

  virtual void SetDurationRange(int64 mi, int64 ma) {
    if (mi > inner_->DurationMin() || ma < inner_->DurationMax()) {
      solver()->GetPropagationMonitor()->SetDurationRange(inner_, mi, ma);
      inner_->SetDurationRange(mi, ma);
    }
  }

  virtual void WhenDurationRange(Demon* const d) {
    inner_->WhenDurationRange(d);
  }

  virtual void WhenDurationBound(Demon* const d) {
    inner_->WhenDurationBound(d);
  }

  virtual bool MustBePerformed() const {
    return inner_->MustBePerformed();
  }

  virtual bool MayBePerformed() const {
    return inner_->MayBePerformed();
  }

  virtual void SetPerformed(bool value) {
    if ((value && !inner_->MustBePerformed()) ||
        (!value && inner_->MayBePerformed())) {
      solver()->GetPropagationMonitor()->SetPerformed(inner_, value);
      inner_->SetPerformed(value);
    }
  }

  virtual void WhenPerformedBound(Demon* const d) {
    inner_->WhenPerformedBound(d);
  }

  virtual void Accept(ModelVisitor* const visitor) const {
    inner_->Accept(visitor);
  }

 private:
  IntervalVar* const inner_;
};

// ---------- PrintTrace ----------

class PrintTrace : public PropagationMonitor {
 public:
  struct Info {
    explicit Info(const string& m) : message(m), displayed(false) {}
    string message;
    bool displayed;
  };

  struct Context {
    Context()
        : initial_indent(0),
          indent(0),
          in_demon(false),
          in_constraint(false),
          in_decision_builder(false),
          in_decision(false),
          in_objective(false) {}

    explicit Context(int start_indent)
        : initial_indent(start_indent),
          indent(start_indent),
          in_demon(false),
          in_constraint(false),
          in_decision_builder(false),
          in_decision(false),
          in_objective(false) {}

    bool TopLevel() const {
      return initial_indent == indent;
    }

    void Clear() {
      indent = initial_indent;
      in_demon = false;
      in_constraint = false;
      in_decision_builder = false;
      in_decision = false;
      in_objective = false;
      delayed_info.clear();
    }

    int initial_indent;
    int indent;
    bool in_demon;
    bool in_constraint;
    bool in_decision_builder;
    bool in_decision;
    bool in_objective;
    std::vector<Info> delayed_info;
  };

  explicit PrintTrace(Solver* const s) : PropagationMonitor(s) {
    contexes_.push(Context());
  }

  virtual ~PrintTrace() {}

  // ----- Search events -----

  virtual void BeginInitialPropagation() {
    CheckNoDelayed();
    DisplaySearch("Root Node Propagation");
    IncreaseIndent();
  }
  virtual void EndInitialPropagation() {
    DecreaseIndent();
    DisplaySearch("Starting Tree Search");
  }

  virtual void BeginNextDecision(DecisionBuilder* const b) {
    DisplaySearch(StringPrintf("DecisionBuilder(%s)",
                               b->DebugString().c_str()));
    IncreaseIndent();
    contexes_.top().in_decision_builder = true;
  }

  // After calling DecisionBuilder::Next, along with the returned decision.
  virtual void EndNextDecision(DecisionBuilder* const b, Decision* const d) {
    contexes_.top().in_decision_builder = false;
    DecreaseIndent();
  }

  virtual void BeginFail() {
    contexes_.top().Clear();
    while (!contexes_.top().TopLevel()) {
      DecreaseIndent();
      LOG(INFO) << Indent() << "}";
    }
    DisplaySearch(StringPrintf("Failure at depth %d", solver()->SearchDepth()));
  }

  virtual bool AtSolution() {
    DisplaySearch(StringPrintf("Solution found at depth %d",
                               solver()->SearchDepth()));
    return false;
  }

  virtual void ApplyDecision(Decision* const decision) {
    DisplaySearch(StringPrintf("ApplyDecision(%s)",
                               decision->DebugString().c_str()));
    IncreaseIndent();
    contexes_.top().in_decision = true;
  }

  virtual void RefuteDecision(Decision* const decision) {
    if (contexes_.top().in_objective) {
      DecreaseIndent();
      contexes_.top().in_objective = false;
    }
    DisplaySearch(StringPrintf("RefuteDecision(%s)",
                               decision->DebugString().c_str()));
    IncreaseIndent();
    contexes_.top().in_decision = true;
  }

  virtual void AfterDecision(Decision* const decision, bool direction) {
    DecreaseIndent();
    contexes_.top().in_decision = false;
  }

  virtual void EnterSearch() {
    if (solver()->SolveDepth() == 0) {
      CHECK_EQ(1, contexes_.size());
      contexes_.top().Clear();
    } else {
      PrintDelayedString();
      PushNestedContext();
    }
    DisplaySearch("Enter Search");
  }

  virtual void ExitSearch() {
    DisplaySearch("Exit Search");
    CHECK(contexes_.top().TopLevel());
    if (solver()->SolveDepth() > 1) {
      contexes_.pop();
    }
  }

  virtual void RestartSearch() {
    CHECK(contexes_.top().TopLevel());
  }

  // ----- Propagation events -----

  virtual void BeginConstraintInitialPropagation(
      const Constraint* const constraint) {
    PushDelayedInfo(StringPrintf("Constraint(%s)",
                                     constraint->DebugString().c_str()));
    contexes_.top().in_constraint= true;
  }

  virtual void EndConstraintInitialPropagation(const Constraint* const) {
    PopDelayedInfo();
    contexes_.top().in_constraint = false;
  }

  virtual void BeginNestedConstraintInitialPropagation(
      const Constraint* const parent,
      const Constraint* const nested) {
    PushDelayedInfo(StringPrintf("Constraint(%s)",
                                     nested->DebugString().c_str()));
    contexes_.top().in_constraint = true;
  }
  virtual void EndNestedConstraintInitialPropagation(const Constraint* const,
                                                     const Constraint* const) {
    PopDelayedInfo();
    contexes_.top().in_constraint = false;
  }

  virtual void RegisterDemon(const Demon* const demon) {}

  virtual void BeginDemonRun(const Demon* const demon) {
    if (demon->priority() != Solver::VAR_PRIORITY) {
      contexes_.top().in_demon = true;
      PushDelayedInfo(StringPrintf("Demon(%s)",
                                       demon->DebugString().c_str()));
    }
  }

  virtual void EndDemonRun(const Demon* const demon) {
    if (demon->priority() != Solver::VAR_PRIORITY) {
      contexes_.top().in_demon = false;
      PopDelayedInfo();
    }
  }

  virtual void PushContext(const string& context) {
    PushDelayedInfo(context);
  }

  virtual void PopContext() {
    PopDelayedInfo();
  }

  // ----- IntExpr modifiers -----

  virtual void SetMin(IntExpr* const expr, int64 new_min) {
    DisplayModification(StringPrintf("SetMin(%s, %lld)",
                                     expr->DebugString().c_str(),
                                     new_min));
  }

  virtual void SetMax(IntExpr* const expr, int64 new_max) {
    DisplayModification(StringPrintf("SetMax(%s, %lld)",
                                     expr->DebugString().c_str(),
                                     new_max));
  }

  virtual void SetRange(IntExpr* const expr, int64 new_min, int64 new_max) {
    DisplayModification(StringPrintf("SetRange(%s, [%lld .. %lld])",
                                     expr->DebugString().c_str(),
                                     new_min,
                                     new_max));
  }

  // ----- IntVar modifiers -----

  virtual void SetMin(IntVar* const var, int64 new_min) {
    DisplayModification(StringPrintf("SetMin(%s, %lld)",
                                     var->DebugString().c_str(),
                                     new_min));
  }

  virtual void SetMax(IntVar* const var, int64 new_max) {
    DisplayModification(StringPrintf("SetMax(%s, %lld)",
                                     var->DebugString().c_str(),
                                     new_max));
  }

  virtual void SetRange(IntVar* const var, int64 new_min, int64 new_max) {
    DisplayModification(StringPrintf("SetRange(%s, [%lld .. %lld])",
                                     var->DebugString().c_str(),
                                     new_min,
                                     new_max));
  }

  virtual void RemoveValue(IntVar* const var, int64 value) {
    DisplayModification(StringPrintf("RemoveValue(%s, %lld)",
                                     var->DebugString().c_str(),
                                     value));
  }

  virtual void SetValue(IntVar* const var, int64 value) {
    DisplayModification(StringPrintf("SetValue(%s, %lld)",
                                     var->DebugString().c_str(),
                                     value));
  }

  virtual void RemoveInterval(IntVar* const var, int64 imin, int64 imax) {
    DisplayModification(StringPrintf("RemoveInterval(%s, [%lld .. %lld])",
                                     var->DebugString().c_str(),
                                     imin,
                                     imax));
  }

  virtual void SetValues(IntVar* const var,
                         const int64* const values,
                         int size) {
    DisplayModification(
        StringPrintf("SetValues(%s, %s)",
                     var->DebugString().c_str(),
                     Int64ArrayToString(values, size, ", ").c_str()));
  }

  virtual void RemoveValues(IntVar* const var,
                            const int64* const values,
                            int size) {
    DisplayModification(
        StringPrintf("RemoveValues(%s, %s)",
                     var->DebugString().c_str(),
                     Int64ArrayToString(values, size, ", ").c_str()));
  }

  // ----- IntervalVar modifiers -----

  virtual void SetStartMin(IntervalVar* const var, int64 new_min) {
    DisplayModification(StringPrintf("SetStartMin(%s, %lld)",
                                     var->DebugString().c_str(),
                                     new_min));
  }

  virtual void SetStartMax(IntervalVar* const var, int64 new_max) {
    DisplayModification(StringPrintf("SetStartMax(%s, %lld)",
                                     var->DebugString().c_str(),
                                     new_max));
  }

  virtual void SetStartRange(IntervalVar* const var,
                             int64 new_min,
                             int64 new_max) {
    DisplayModification(StringPrintf("SetStartRange(%s, [%lld .. %lld])",
                                     var->DebugString().c_str(),
                                     new_min,
                                     new_max));
  }

  virtual void SetEndMin(IntervalVar* const var, int64 new_min) {
    DisplayModification(StringPrintf("SetEndMin(%s, %lld)",
                                     var->DebugString().c_str(),
                                     new_min));
  }

  virtual void SetEndMax(IntervalVar* const var, int64 new_max) {
    DisplayModification(StringPrintf("SetEndMax(%s, %lld)",
                                     var->DebugString().c_str(),
                                     new_max));
  }

  virtual void SetEndRange(IntervalVar* const var,
                           int64 new_min,
                           int64 new_max) {
    DisplayModification(StringPrintf("SetEndRange(%s, [%lld .. %lld])",
                                     var->DebugString().c_str(),
                                     new_min,
                                     new_max));
  }

  virtual void SetDurationMin(IntervalVar* const var, int64 new_min) {
    DisplayModification(StringPrintf("SetDurationMin(%s, %lld)",
                                     var->DebugString().c_str(),
                                     new_min));
  }

  virtual void SetDurationMax(IntervalVar* const var, int64 new_max) {
    DisplayModification(StringPrintf("SetDurationMax(%s, %lld)",
                                     var->DebugString().c_str(),
                                     new_max));
  }

  virtual void SetDurationRange(IntervalVar* const var,
                                int64 new_min,
                                int64 new_max) {
    DisplayModification(StringPrintf("SetDurationRange(%s, [%lld .. %lld])",
                                     var->DebugString().c_str(),
                                     new_min,
                                     new_max));
  }

  virtual void SetPerformed(IntervalVar* const var, bool value) {
    DisplayModification(StringPrintf("SetPerformed(%s, %d)",
                                     var->DebugString().c_str(),
                                     value));
  }

  virtual void RankFirst(SequenceVar* const var, int index) {
    DisplayModification(StringPrintf("RankFirst(%s, %d)",
                                     var->DebugString().c_str(),
                                     index));
  }

  virtual void RankNotFirst(SequenceVar* const var, int index) {
    DisplayModification(StringPrintf("RankNotFirst(%s, %d)",
                                     var->DebugString().c_str(),
                                     index));
  }

  virtual void RankLast(SequenceVar* const var, int index) {
    DisplayModification(StringPrintf("RankLast(%s, %d)",
                                     var->DebugString().c_str(),
                                     index));
  }

  virtual void RankNotLast(SequenceVar* const var, int index) {
    DisplayModification(StringPrintf("RankNotLast(%s, %d)",
                                     var->DebugString().c_str(),
                                     index));
  }

  virtual void RankSequence(SequenceVar* const var,
                            const std::vector<int>& rank_first,
                            const std::vector<int>& rank_last,
                            const std::vector<int>& unperformed) {
    DisplayModification(
        StringPrintf(
            "RankSequence(%s, forward [%s], backward[%s], unperformed[%s])",
            var->DebugString().c_str(),
            IntVectorToString(rank_first, ", ").c_str(),
            IntVectorToString(rank_last, ", ").c_str(),
            IntVectorToString(unperformed, ", ").c_str()));
  }

  virtual void Install() {
    SearchMonitor::Install();
    if (solver()->SolveDepth() <= 1) {
      solver()->AddPropagationMonitor(this);
    }
  }

 private:
  void PushDelayedInfo(const string& delayed) {
    contexes_.top().delayed_info.push_back(Info(delayed));
  }

  void PopDelayedInfo() {
    CHECK(!contexes_.top().delayed_info.empty());
    if (contexes_.top().delayed_info.back().displayed &&
        !contexes_.top().TopLevel()) {
      DecreaseIndent();
      LOG(INFO) << Indent() << "}";
    } else {
      contexes_.top().delayed_info.pop_back();
    }
  }

  void CheckNoDelayed() {
    CHECK(contexes_.top().delayed_info.empty());
  }

  void PrintDelayedString() {
    const std::vector<Info>& infos = contexes_.top().delayed_info;
    for (int i = 0; i < infos.size(); ++i) {
      const Info& info = infos[i];
      if (!info.displayed) {
        LOG(INFO) << Indent() << info.message << " {";
        IncreaseIndent();
        // Marks it as displayed.
        contexes_.top().delayed_info[i].displayed = true;
      }
    }
  }

  void DisplayModification(const string& to_print) {
    PrintDelayedString();
    if (contexes_.top().in_demon ||
        contexes_.top().in_constraint ||
        contexes_.top().in_decision_builder ||
        contexes_.top().in_decision ||
        contexes_.top().in_objective) {
      // Inside a demon, constraint, decision builder -> normal print.
      LOG(INFO) << Indent() << to_print;
    } else {
      // Top level, modification pushed by the objective.  This is a
      // hack. The SetMax or SetMin done by the objective happens in
      // the RefuteDecision callback of search monitors.  We cannot
      // easily differentiate that from the actual modifications done
      // by the Refute() call itself.  To distinguish that, we force
      // the print trace to be last in the list of monitors. Thus
      // modifications that happens at the top level before the
      // RefuteDecision() callbacks must be from the objective.
      // In that case, we push the in_objective context.
      CHECK(contexes_.top().TopLevel());
      DisplaySearch(StringPrintf("Objective -> %s", to_print.c_str()));
      IncreaseIndent();
      contexes_.top().in_objective = true;
    }
  }

  void DisplaySearch(const string& to_print) {
    const int solve_depth = solver()->SolveDepth();
    if (solve_depth <= 1) {
      LOG(INFO) << Indent() << "######## Top Level Search: " << to_print;
    } else {
      LOG(INFO) << Indent() << "######## Nested Search(" << solve_depth - 1
                << "): " << to_print;
    }
  }

  string Indent() {
    string output = " @ ";
    for (int i = 0; i < contexes_.top().indent; ++i) {
      output.append("    ");
    }
    return output;
  }

  void IncreaseIndent() {
    contexes_.top().indent++;
  }

  void DecreaseIndent() {
    contexes_.top().indent--;
  }

  void PushNestedContext() {
    const int initial_indent = contexes_.top().indent;
    contexes_.push(Context(initial_indent));
  }

  std::stack<Context> contexes_;
};
}  // namespace

IntExpr* Solver::RegisterIntExpr(IntExpr* const expr) {
  if (InstrumentsVariables()) {
    if (expr->IsVar()) {
      return RegisterIntVar(expr->Var());
    } else {
      return RevAlloc(new TraceIntExpr(this, expr));
    }
  } else {
    return expr;
  }
}

IntVar* Solver::RegisterIntVar(IntVar* const var) {
  if (InstrumentsVariables() &&
      var->VarType() != TRACE_VAR) {  // Not already a trace var.
    return RevAlloc(new TraceIntVar(this, var));
  } else {
    return var;
  }
}

IntervalVar* Solver::RegisterIntervalVar(IntervalVar* const var) {
  if (InstrumentsVariables()) {
    return RevAlloc(new TraceIntervalVar(this, var));
  } else {
    return var;
  }
}

PropagationMonitor* BuildPrintTrace(Solver* const s) {
  return s->RevAlloc(new PrintTrace(s));
}
}  // namespace operations_research