trace-recorder.hpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2016
 *
 *  Last modified:
 *     $Date: 2017-03-17 23:04:57 +0100 (Fri, 17 Mar 2017) $ by $Author: schulte $
 *     $Revision: 15597 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

namespace Gecode {

  enum TraceEvent {

    TE_INIT  = 1 << 0, 
    TE_PRUNE = 1 << 1, 
    TE_FIX   = 1 << 2, 
    TE_FAIL  = 1 << 3, 
    TE_DONE  = 1 << 4, 


    TE_PROPAGATE = 1 << 5, 
    TE_COMMIT    = 1 << 6  
  };

  template<class View>
  class ViewTraceRecorder : public Propagator {
  public:
    typedef typename TraceTraits<View>::TraceView TraceView;
    typedef typename TraceTraits<View>::TraceDelta TraceDelta;
    typedef typename TraceTraits<View>::SlackValue SlackValue;
    class Slack {
      template<class ViewForTraceRecorder> friend class ViewTraceRecorder;
    protected:
      SlackValue i;
      SlackValue p;
      SlackValue c;
    public:
      SlackValue initial(void) const;
      SlackValue previous(void) const;
      SlackValue current(void) const;
    };
  protected:
    class Idx : public Advisor {
    protected:
      int _idx;
    public:
      Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
      Idx(Space& home, bool share, Idx& a);
      int idx(void) const;
    };
    ViewArray<TraceView> o;
    ViewArray<View> n;
    Council<Idx> c;
    TraceFilter tf;
    int te;
    ViewTracer<View>& t;
    Slack s;
    ViewTraceRecorder(Space& home, bool share, ViewTraceRecorder& p);
  public:
    ViewTraceRecorder(Home home, ViewArray<View>& x,
                      TraceFilter tf, int te, ViewTracer<View>& t);
    virtual Propagator* copy(Space& home, bool share);
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual void reschedule(Space& home);
    virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    virtual size_t dispose(Space& home);
    static ExecStatus post(Home home, ViewArray<View>& x,
                           TraceFilter tf, int te, ViewTracer<View>& t);


    const typename View::VarType operator [](int i) const;
    int size(void) const;
    const Slack& slack(void) const;
  };

  class TraceRecorder : public Propagator {
  public:
    TraceFilter tf;
    int te;
    Tracer& t;
    TraceRecorder(Space& home, bool share, TraceRecorder& p);
  public:
    TraceRecorder(Home home, TraceFilter tf, int te, Tracer& t);
    virtual Propagator* copy(Space& home, bool share);
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual void reschedule(Space& home);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    virtual size_t dispose(Space& home);
    static ExecStatus post(Home home, TraceFilter tf, int te, Tracer& t);


    const TraceFilter& filter(void) const;
    int events(void) const;
    Tracer& tracer(void) const;
  };


  /*
   * Functions for trace support
   *
   */
  template<class View>
  forceinline const typename View::VarType
  ViewTraceRecorder<View>::operator [](int i) const {
    const typename View::VarType x(n[i].varimp());
    return x;
  }
  template<class View>
  forceinline int
  ViewTraceRecorder<View>::size(void) const {
    return n.size();
  }
  template<class View>
  forceinline const typename ViewTraceRecorder<View>::Slack&
  ViewTraceRecorder<View>::slack(void) const {
    return s;
  }


  /*
   * Functions for access to slack
   *
   */
  template<class View>
  forceinline typename ViewTraceRecorder<View>::SlackValue
  ViewTraceRecorder<View>::Slack::initial(void) const {
    return i;
  }
  template<class View>
  forceinline typename ViewTraceRecorder<View>::SlackValue
  ViewTraceRecorder<View>::Slack::previous(void) const {
    return p;
  }
  template<class View>
  forceinline typename ViewTraceRecorder<View>::SlackValue
  ViewTraceRecorder<View>::Slack::current(void) const {
    return c;
  }


  /*
   * Advisor for tracer
   *
   */

  template<class View>
  forceinline
  ViewTraceRecorder<View>::Idx::Idx(Space& home, Propagator& p,
                                    Council<Idx>& c, int i)
    : Advisor(home,p,c), _idx(i) {}
  template<class View>
  forceinline
  ViewTraceRecorder<View>::Idx::Idx(Space& home, bool share, Idx& a)
    : Advisor(home,share,a), _idx(a._idx) {
  }
  template<class View>
  forceinline int
  ViewTraceRecorder<View>::Idx::idx(void) const {
    return _idx;
  }


  /*
   * Posting of tracer propagator
   *
   */
  template<class View>
  forceinline
  ViewTraceRecorder<View>::ViewTraceRecorder(Home home, ViewArray<View>& x,
                                             TraceFilter tf0, int te0,
                                             ViewTracer<View>& t0)
    : Propagator(home), o(home,x.size()), n(x), c(home),
      tf(tf0), te(te0), t(t0) {
    home.notice(*this, AP_VIEW_TRACE);
    home.notice(*this, AP_DISPOSE);
    for (int i=n.size(); i--; ) {
      o[i] = TraceView(home,n[i]);
      if (!n[i].assigned())
        n[i].subscribe(home,*new (home) Idx(home,*this,c,i));
    }
    View::schedule(home,*this,ME_GEN_ASSIGNED);
    s.i = TraceView::slack(n[n.size()-1]);
    for (int i=n.size()-1; i--; )
      s.i += TraceView::slack(n[i]);
    s.p = s.i;
    if ((te & TE_INIT) != 0)
      t._init(home,*this);
  }


  template<class View>
  forceinline ExecStatus
  ViewTraceRecorder<View>::post(Home home, ViewArray<View>& x,
                                TraceFilter tf, int te, ViewTracer<View>& t) {
    if ((x.size() > 0) &&
        (te & (TE_INIT | TE_PRUNE | TE_FIX | TE_FAIL | TE_DONE)))
      (void) new (home) ViewTraceRecorder(home,x,tf,te,t);
    return ES_OK;
  }


  /*
   * Propagation for trace recorder
   *
   */
  template<class View>
  forceinline
  ViewTraceRecorder<View>::ViewTraceRecorder(Space& home, bool share,
                                             ViewTraceRecorder& p)
    : Propagator(home,share,p), te(p.te), t(p.t), s(p.s) {
    o.update(home, share, p.o);
    n.update(home, share, p.n);
    c.update(home, share, p.c);
    tf.update(home, share, p.tf);
  }

  template<class View>
  Propagator*
  ViewTraceRecorder<View>::copy(Space& home, bool share) {
    return new (home) ViewTraceRecorder(home, share, *this);
  }

  template<class View>
  inline size_t
  ViewTraceRecorder<View>::dispose(Space& home) {
    home.ignore(*this, AP_VIEW_TRACE);
    home.ignore(*this, AP_DISPOSE);
    tf.~TraceFilter();
    // Cancel remaining advisors
    for (Advisors<Idx> as(c); as(); ++as)
      n[as.advisor().idx()].cancel(home,as.advisor());
    c.dispose(home);
    (void) Propagator::dispose(home);
    return sizeof(*this);
  }

  template<class View>
  PropCost
  ViewTraceRecorder<View>::cost(const Space&, const ModEventDelta&) const {
    return PropCost::record();
  }

  template<class View>
  void
  ViewTraceRecorder<View>::reschedule(Space& home) {
    View::schedule(home,*this,ME_GEN_ASSIGNED);
  }

  template<class View>
  ExecStatus
  ViewTraceRecorder<View>::advise(Space& home, Advisor& _a, const Delta& d) {
    Idx& a = static_cast<Idx&>(_a);
    int i = a.idx();
    if (((te & TE_PRUNE) != 0) && !disabled() && tf(a(home)) ) {
      TraceDelta td(o[i],n[i],d);
      t._prune(home,*this,a(home),i,td);
    }
    o[i].prune(home,n[i],d);
    if (n[a.idx()].assigned())
      a.dispose(home,c);
    return ES_NOFIX;
  }

  template<class View>
  ExecStatus
  ViewTraceRecorder<View>::propagate(Space& home, const ModEventDelta&) {
    s.c = TraceView::slack(n[n.size()-1]);
    for (int i=n.size()-1; i--; )
      s.c += TraceView::slack(n[i]);
    if (home.failed() && ((te & TE_FAIL) != 0) && !disabled()) {
      t._fail(home,*this);
      return ES_FIX;
    }
    if ((te & TE_FIX) != 0)
      t._fix(home,*this);
    s.p = s.c;
    if (c.empty()) {
      if ((te & TE_DONE) != 0)
        t._done(home,*this);
      return home.ES_SUBSUMED(*this);
    }
    return ES_FIX;
  }



  /*
   * Functions for trace support
   *
   */
  forceinline const TraceFilter&
  TraceRecorder::filter(void) const {
    return tf;
  }
  forceinline int
  TraceRecorder::events(void) const {
    return te;
  }
  forceinline Tracer&
  TraceRecorder::tracer(void) const {
    return t;
  }


  /*
   * Trace recorder propagator
   *
   */
  forceinline
  TraceRecorder::TraceRecorder(Home home, TraceFilter tf0, int te0,
                               Tracer& t0)
    : Propagator(home), tf(tf0), te(te0), t(t0) {
    home.notice(*this, AP_DISPOSE);
    home.notice(*this, AP_TRACE);
  }

  forceinline ExecStatus
  TraceRecorder::post(Home home, TraceFilter tf, int te, Tracer& t) {
    if (te & (TE_PROPAGATE | TE_COMMIT))
      (void) new (home) TraceRecorder(home,tf,te,t);
    return ES_OK;
  }

  forceinline
  TraceRecorder::TraceRecorder(Space& home, bool share,
                               TraceRecorder& p)
    : Propagator(home,share,p), te(p.te), t(p.t) {
    tf.update(home, share, p.tf);
  }

}

// STATISTICS: kernel-trace