Logo Search packages:      
Sourcecode: maria version File versions

Marking.C

Go to the documentation of this file.
// Marking -*- c++ -*-

#ifdef __GNUC__
# pragma implementation
#endif // __GNUC__
#include "Marking.h"
#include "PlaceMarking.h"
#include "LeafValue.h"
#include "Valuation.h"
#include "Place.h"
#include "Constant.h"
#include "Net.h"
#include "CardType.h"
#include "ExpressionList.h"
#include "IfThenElse.h"
#include "Typecast.h"
#include "VariableDefinition.h"
#include "ExpressionMSet.h"
#include "EmptySet.h"
#include "Printer.h"

/** @file Marking.C
 * Basic multi-set constructor operation
 */

/* Copyright © 1998-2003 Marko Mäkelä (msmakela@tcs.hut.fi).

   This file is part of MARIA, a reachability analyzer and model checker
   for high-level Petri nets.

   MARIA is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   MARIA is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   The GNU General Public License is often shipped with GNU software, and
   is generally kept in a file called COPYING or LICENSE.  If you do not
   have a copy of the license, write to the Free Software Foundation,
   59 Temple Place, Suite 330, Boston, MA 02111 USA. */

/** Calculate the multiplicity of a marking
 * @param valuation     variable substitutions
 * @param expr          the multiplicity expression
 * @param count         multiplicity of the surrounding marking expression
 * @return        multiplicity of the marking expression (count * expr)
 */
inline static card_t
00053 calcMultiplicity (const class Valuation& valuation,
              const class Expression& expr,
              card_t count)
{
  assert (count);
  if (class Value* v = expr.eval (valuation)) {
    assert (v->getKind () == Value::vLeaf);
    card_t c = card_t (static_cast<const class LeafValue&>(*v));
    delete v;
    if (c >= CARD_T_MAX / count) {
      valuation.flag (errCard, expr);
      return 0;
    }
    else
      return count * c;
  }

  assert (!valuation.isOK ());
  return 0;
}

00074 Marking::Marking (const class Place* place, class Marking* child) :
  myChild (child), myParent (0), myNext (0),
  myPlace (place), myMultiplicity (0),
  myToken (0)
{
  if (myPlace)
    Expression::setType (myPlace->getType ());
  else if (myChild)
    Expression::setType (*myChild->getType ());
  assert (!myChild ||
        (myChild->myPlace == myPlace && myChild->getType () == getType ()));
  assert (!myChild || !myChild->myParent);
  for (class Marking* m = myChild; m; m = m->myNext)
    m->myParent = this;
}

00090 Marking::~Marking ()
{
  myChild->destroy ();
  myNext->destroy ();
  myMultiplicity->destroy ();
  myToken->destroy ();
}

void
00099 Marking::setPlace (const class Place* place)
{
  assert (!myPlace || myPlace == place);
  myPlace = place;

  if (myChild)
    myChild->setPlace (place);
  if (myNext)
    myNext->setPlace (place);
}

void
00111 Marking::setMultiplicity (class Expression* multiplicity)
{
  assert (!multiplicity || multiplicity->isBasic ());
  myMultiplicity = multiplicity;
}

void
00118 Marking::setToken (class Expression* token)
{
  assert (!myToken && !myChild); myToken = token;
  if (myToken->getKind () == Expression::eEmptySet) return;
  assert (myToken && myToken->getType ());
  Expression::setType (*myToken->getType ());
}

void
00127 Marking::setType (const class Type& type)
{
  for (class Marking* m = this; m; m = m->myNext) {
    Expression::setType (type);
    if (myToken) {
      myToken->setType (type);
      assert (!myChild);
    }
    else {
      assert (!!myChild);
      myChild->setType (type);
    }
  }
}

/** Inequality null comparison for member components that may be null
 * @param c component name
 * @return  true if one of this.c and other.c is null
 */
00146 #define NULLCMP(c) ((c && !other.c) || (!c && other.c))

bool
00149 Marking::operator== (const class Marking& other) const
{
  if (myPlace != other.myPlace ||
      NULLCMP (myChild) || NULLCMP (myToken) ||
      NULLCMP (myMultiplicity) ||
      NULLCMP (myNext))
    return false;

  if (myChild) {
    assert (!myToken);
    if (!(*myChild == *other.myChild))
      return false;
  }
  else {
    assert (myToken != NULL);
    if (!(*myToken == *other.myToken))
      return false;
  }

  if (myMultiplicity && !(*myMultiplicity == *other.myMultiplicity))
    return false;

  return !myNext || *myNext == *other.myNext;
}
#undef NULLCMP

bool
00176 Marking::operator< (const class Marking& other) const
{
  // the shorter chain of markings is smaller
  for (const class Marking *l = this, *r = &other; l && r; ) {
    l = l->myNext, r = r->myNext;
    if (!l && r) return true;
    if (!r && l) return false;
  }
  // the chains are of the same length => compare other things

  // place referred to by the first marking
  if (myPlace < other.myPlace) return true;
  if (other.myPlace < myPlace) return false;
  // presence of child marking
  if (!myChild && other.myChild) return true;
  if (!other.myChild && myChild) return false;

  if (myChild) {
    // ordering of child markings
    assert (!myToken);
    if (*myChild < *other.myChild) return true;
    if (*other.myChild < *myChild) return false;
  }

  // presence of token expression
  if (!myToken && other.myToken) return true;
  if (!other.myToken && myToken) return false;

  if (myToken) {
    // ordering of token expressions
    assert (!myChild);
    if (*myToken < *other.myToken) return true;
    if (*other.myToken < *myToken) return false;
  }
  else
    assert (!!myChild);

  // presence of multiplicity expression
  if (!myMultiplicity && other.myMultiplicity) return true;
  if (!other.myMultiplicity && myMultiplicity) return false;

  // ordering of multiplicity expressions
  if (myMultiplicity) {
    if (*myMultiplicity < *other.myMultiplicity) return true;
    if (*other.myMultiplicity < *myMultiplicity) return false;
  }

  // the next marking in the chain
  return myNext && *myNext < *other.myNext;
}

class Expression*
00228 Marking::ground (const class Valuation& valuation,
             class Transition* transition,
             bool declare)
{
  valuation.clearErrors ();
  class ExpressionMSet result;
  if (ground (valuation, transition, declare, result, 1)) {
    assert (valuation.isOK ());
    return result.toMarking (myPlace);
  }
  else {
    assert (!valuation.isOKorVar ());
    return NULL;
  }
}

bool
00245 Marking::ground (const class Valuation& valuation,
             class Transition* transition,
             bool declare,
             class ExpressionMSet& result,
             card_t count)
{
  assert (count > 0);
  for (class Marking* m = this; m; m = m->myNext) {
    assert (m->myPlace == myPlace);
    assert (valuation.isOK ());
    valuation.clearErrors ();

    class Expression* multiplicity = m->myMultiplicity
      ? m->myMultiplicity->ground (valuation, transition, declare)
      : NULL;

    if (m->myMultiplicity && !multiplicity)
      return false;

    if (!multiplicity || multiplicity->getKind () == Expression::eConstant) {
      card_t c;
      if (multiplicity) {
      const class Value& mv =
        static_cast<class Constant*>(multiplicity)->getValue ();
      assert (mv.getKind () == Value::vLeaf);
      c = card_t (static_cast<const class LeafValue&>(mv));
      multiplicity->destroy ();
      if (!c)
        continue;
      else if (c >= CARD_T_MAX / count) {
        valuation.flag (errCard, *m);
        return false;
      }
      }
      else
      c = 1;
      if (m->myChild) {
      assert (!m->myToken);
      if (!m->myChild->ground (valuation, transition, declare,
                         result, c * count))
        return false;
      }
      else {
      assert (m->myToken && m->myToken->getKind () != Expression::eMarking);
      class Expression* token =
        m->myToken->ground (valuation, transition, declare);
      if (!token)
        return false;
      assert (valuation.isOK ());
      if (!result.insert (*token, c * count)) {
        token->destroy ();
        valuation.flag (errCard, *m);
        return false;
      }
      token->destroy ();
      }
    }
    else { // variable multiplicity
      assert (m->myChild ? !m->myToken : !!m->myToken);
      class Expression* expr = m->myChild
      ? m->myChild->ground (valuation, transition, declare)
      : m->myToken->ground (valuation, transition, declare);
      if (!expr) {
      assert (!valuation.isOKorVar ());
      multiplicity->destroy ();
      expr->destroy ();
      return false;
      }
      assert (valuation.isOK ());
      class Marking* mm;
      if (m->myChild) {
      assert (expr && expr->getKind () == Expression::eMarking);
      mm = static_cast<class Marking*>(expr);
      if (mm->myMultiplicity)
        mm = new class Marking (myPlace, mm);
      }
      else {
      mm = new class Marking (myPlace);
      mm->setToken (expr);
      }
      assert (!mm->myMultiplicity && multiplicity);
      mm->setMultiplicity (multiplicity);
      mm = static_cast<class Marking*>(mm->cse ());
      if (!result.insert (*mm, count)) {
      mm->destroy ();
      valuation.flag (errCard, *mm);
      return false;
      }
      mm->destroy ();
    }
  }

  return true;
}

class Expression*
00341 Marking::substitute (class Substitution& substitution)
{
  class Marking* child = myChild
    ? static_cast<class Marking*>(myChild->substitute (substitution))
    : NULL;
  class Marking* n = myNext
    ? static_cast<class Marking*>(myNext->substitute (substitution))
    : NULL;
  class Expression* token = myToken
    ? myToken->substitute (substitution)
    : NULL;
  class Expression* multiplicity = myMultiplicity
    ? myMultiplicity->substitute (substitution)
    : NULL;
  if (child == myChild && n == myNext &&
      token == myToken && multiplicity == myMultiplicity) {
    child->destroy ();
    n->destroy ();
    token->destroy ();
    multiplicity->destroy ();

    return copy ();
  }
  else {
    class Marking* m = new class Marking (myPlace, child);
    m->myMultiplicity = multiplicity;
    m->myNext = n;
    m->myToken = token;
    static_cast<class Expression*>(m)->setType (*getType ());
    return m->cse ();
  }
}

bool
00375 Marking::depends (const class VariableSet& vars,
              bool complement) const
{
  return
    (myChild && myChild->depends (vars, complement)) ||
    (myNext && myNext->depends (vars, complement)) ||
    (myMultiplicity && myMultiplicity->depends (vars, complement)) ||
    (myToken && myToken->depends (vars, complement));
}

bool
00386 Marking::forVariables (bool (*operation)
                   (const class Expression&,void*),
                   void* data) const
{
  return
    (!myChild || myChild->forVariables (operation, data)) &&
    (!myNext || myNext->forVariables (operation, data)) &&
    (!myMultiplicity || myMultiplicity->forVariables (operation, data)) &&
    (!myToken || myToken->forVariables (operation, data));
}

bool
00398 Marking::eval (class PlaceMarking* const source,
             class PlaceMarking* const target,
             const card_t count,
             const class Valuation& valuation) const
{
  assert (count > 0);
  assert (valuation.isOK ());

  for (const class Marking* m = this; m; m = m->myNext) {
    assert (valuation.isOK ());
    card_t tokencount;

    if (m->myMultiplicity) {
      tokencount = calcMultiplicity (valuation, *m->myMultiplicity, count);
      if (!valuation.isOK ())
      return false;
    }
    else
      tokencount = count;

    if (const class Expression* const expr = m->myToken) {
      assert (!m->myChild);
      if (tokencount) {
      if (expr->isSet ()) {
        if (class PlaceMarking* p = expr->meval (valuation)) {
          assert (!source && target);
          bool ok = target->add (*p, tokencount);
          delete p;
          if (!ok) {
            valuation.flag (errCard, *m);
            return false;
          }
        }
        else
          return false;
      }
      else if (class Value* token = expr->eval (valuation)) {
        if (source)
          source->remove (*token, tokencount);
        if (target) {
          if (!target->add (*token, tokencount)) {
            valuation.flag (errCard, *m);
            return false;
          }
        }
        else
          delete token;
      }
      else
        return false;
      }
    }
    else {
      assert (!!m->myChild);
      if (tokencount &&
        !m->myChild->eval (source, target, tokencount, valuation))
      return false;
    }
  }

  return true;
}

class PlaceMarking*
00462 Marking::meval (const class Valuation& valuation) const
{
  class PlaceMarking* const p = new class PlaceMarking;
#ifndef NDEBUG
  p->setType (getType ());
#endif
  if (add (*p, 1, valuation))
    return p;
  delete p;
  return NULL;
}

card_t
00475 Marking::getMultiplicity (const class Valuation& valuation) const
{
  card_t mult = myParent ? myParent->getMultiplicity (valuation) : 1;
  return mult && myMultiplicity
    ? calcMultiplicity (valuation, *myMultiplicity, mult)
    : mult;
}

class Expression*
00484 Marking::quantify (const class Valuation& valuation,
               class Transition* transition,
               class VariableDefinition& variable,
               class Expression* condition,
               bool declare)
{
  class Valuation v (valuation);
  class ExpressionMSet result;
  assert (valuation.isOK ());

  if (condition) {
    for (class Marking* m = this; m; m = m->myNext)
      if (m->myMultiplicity) {
      class ExpressionList* l = new class ExpressionList;
      l->append (*(new class Constant (*new class LeafValue
                               (Net::getCardType (), 0)))->cse ());
      l->append (*m->myMultiplicity);
      m->myMultiplicity =
        (new class IfThenElse (*condition->copy (), *l))->cse ();
      }
      else
      m->myMultiplicity =
        (new class Typecast (Net::getCardType (),
                         *condition->copy ()))->cse ();
  }

  v.setValue (variable, variable.getType ().getFirstValue ());

  do {
    if (!ground (v, transition, declare, result, 1)) {
      valuation.copyErrors (v);
      return NULL;
    }
  } while (v.increment (variable));

  if (class Marking* m = result.toMarking (myPlace))
    return m;
  else
    return (new class EmptySet)->cse ();
}

bool
00526 Marking::hasVariableMultiplicity () const
{
  for (const class Marking* m = this; m; m = m->myParent)
    if (m->myMultiplicity &&
      m->myMultiplicity->getKind () != Expression::eConstant)
      return true;
  return false;
}

#ifdef EXPR_COMPILE
# include "CExpression.h"

bool
Marking::hasMultiplicity () const
{
  for (const class Marking* m = this; m; m = m->myParent)
    if (m->myMultiplicity)
      return true;
  return false;
}

void
Marking::compileScalarMset (class CExpression& cexpr,
                      unsigned indent,
                      const char* result,
                      const class VariableSet* vars,
                      bool check) const
{
  if (myMultiplicity || myChild || myNext)
    Expression::compileScalarMset (cexpr, indent, result, vars, check);
  else if (myToken->isSet ())
    myToken->compileScalarMset (cexpr, indent, result, vars, check);
  else {
    class StringBuffer& out = cexpr.getOut ();
    char* tmp;

    if (check) {
      out.indent (indent);
      out.append ("if (");
      out.append (result);
      out.append (")\n");
      cexpr.compileError (indent + 2, errConst);
    }

    if (myToken->getKind () == Expression::eConstant
      ? cexpr.getVariable (*static_cast<const class Constant*>(myToken),
                       tmp)
      : cexpr.getVariable (*myToken, tmp));
      myToken->compile (cexpr, indent, tmp, vars);
    out.indent (indent);
    out.append (result);
    out.append (" = &");
    out.append (tmp);
    out.append (";\n");
    delete[] tmp;
  }
}

void
Marking::compileMset (class CExpression& cexpr,
                  unsigned indent,
                  const char* resulttype,
                  const char* result,
                  const class VariableSet* vars) const
{
  const class Constant* oldtoken = 0;
  char* token;
  for (const class Marking* m = first (); m; m = m->next ()) {
    assert (m->getType () == getType () && m->myToken);
    class StringBuffer& out = cexpr.getOut ();
    char* mult = 0;
    bool* checkpoint = 0;
    unsigned checkpointSize = 0;
    if (m->myToken->getKind () == Expression::eEmptySet)
      continue;
    if (m->hasMultiplicity ()) {
      mult = cexpr.getLabel ();
      out.indent (indent);
      out.append ("{\n");
      out.indent (indent += 2);
      out.append ("card_t ");
      out.append (mult);
      out.append (";\n");
      m->compileMultiplicity (cexpr, indent, mult, vars);
      checkpointSize = cexpr.getCheckpoint (checkpoint);
      out.indent (indent);
      out.append ("if ("), out.append (mult), out.append (") {\n");
      indent += 2;
    }
    if (m->myToken->isSet ()) {
      if (cexpr.getVariable (*m->myToken, token))
      m->myToken->compileMset (cexpr, indent, 0, token, vars);
      out.indent (indent);
      out.append (result);
      out.append (mult ? "=copyc" : "=copy");
      getType ()->appendIndex (out);
      out.append (" (");
      if (resulttype)
      out.append (resulttype);
      out.append (result);
      out.append (", ");
      out.append (token);
      if (mult) out.append (", "), out.append (mult);
      out.append (");\n");
      delete[] token;
    }
    else {
      if (oldtoken)
      cexpr.recycle (*oldtoken, *m->myToken);
      if (m->myToken->getKind () == Expression::eConstant) {
      oldtoken = static_cast<const class Constant*>(m->myToken);
      if (cexpr.getVariable (*oldtoken, token))
        oldtoken->compile (cexpr, indent, token, vars);
      }
      else if (oldtoken = 0, cexpr.getVariable (*m->myToken, token))
      m->myToken->compile (cexpr, indent, token, vars);
      out.indent (indent);
      out.append (result);
      out.append ("=insert");
      getType ()->appendIndex (out);
      out.append (" (");
      if (resulttype)
      out.append (resulttype);
      out.append (result);
      out.append (", &");
      out.append (token);
      out.append (", ");
      out.append (mult ? mult : "1");
      out.append (");\n");
      delete[] token;
    }
    if (mult) {
      cexpr.setCheckpoint (indent, checkpoint, checkpointSize);
      delete[] checkpoint;
      delete[] mult;
      out.indent (indent -= 2), out.append ("}\n");
      out.indent (indent -= 2), out.append ("}\n");
    }
  }
}

void
Marking::compileMultiplicity (class CExpression& cexpr,
                        unsigned indent,
                        const char* result,
                        const class VariableSet* vars) const
{
  class StringBuffer& out = cexpr.getOut ();
  /** number of multiplicity expressions */
  unsigned p, parents = 0;
  const class Marking* m;
  for (m = this; m; m = m->myParent)
    if (m->myMultiplicity)
      parents++;

  if (!parents) {
    out.indent (indent);
    out.append (result);
    out.append ("=1;\n");
    return;
  }

  for (m = this; !m->myMultiplicity; m = m->myParent);
  for (p = parents; --p; )
    while (!(m = m->myParent)->myMultiplicity);
  m->myMultiplicity->compile (cexpr, indent, result, vars);

  while (--parents) {
    for (m = this; !m->myMultiplicity; m = m->myParent);
    for (p = parents; --p; )
      while (!(m = m->myParent)->myMultiplicity);
    bool* checkpoint = 0;
    unsigned checkpointSize = cexpr.getCheckpoint (checkpoint);
    out.indent (indent);
    out.append ("if (");
    out.append (result);
    out.append (") {\n");
    const char* work = cexpr.getVarTmpCount ();
    m->myMultiplicity->compile (cexpr, indent + 2, work, vars);
    out.indent (indent + 2);
    out.append ("if (");
    out.append (work);
    out.append (">=CARD_T_MAX/");
    out.append (result);
    out.append (")\n");
    cexpr.compileError (indent + 4, errCard);
    out.indent (indent + 2);
    out.append (result);
    out.append ("*=");
    out.append (work);
    out.append (";\n");
    cexpr.setCheckpoint (indent + 2, checkpoint, checkpointSize);
    delete[] checkpoint;
    out.indent (indent);
    out.append ("}\n");
  }
}

#endif // EXPR_COMPILE

void
00727 Marking::display (const class Printer& printer) const
{
  for (const class Marking* m = this;; ) {
    if (m->myMultiplicity) {
      switch (m->myMultiplicity->getKind ()) {
      case eCardinality:
      case eUnop:
      case eConstant:
      case eVariable:
      m->myMultiplicity->display (printer);
      break;
      default:
      printer.delimiter ('(')++;
      m->myMultiplicity->display (printer);
      --printer.delimiter (')');
      break;
      }
      printer.delimiter ('#');
    }
    if (m->myToken)
      m->myToken->display (printer), assert (!m->myChild);
    else {
      assert (!!m->myChild);
      printer.delimiter ('(')++;
      m->myChild->display (printer);
      --printer.delimiter (')');
    }

    if ((m = m->myNext))
      printer.delimiter (',');
    else
      break;
  }
}

/** Display the multiplicity of a marking
 * @param printer the printer object
 * @param m       the marking
 */
inline static void
00767 displayMultiplicity (const class Printer& printer,
                 const class Marking& m)
{
  if (m.getParent ())
    displayMultiplicity (printer, *m.getParent ());
  if (const class Expression* mult = m.getMultiplicity ())
    mult->display (printer), printer.delimiter ('#');
}

void
00777 Marking::displayToken (const class Printer& printer) const
{
  const class Marking* m;
  for (m = this; m->myChild; m = m->myChild);
  assert (m && m->myToken);
  displayMultiplicity (printer, *m);
  m->myToken->display (printer);
}

Generated by  Doxygen 1.6.0   Back to index