Logo Search packages:      
Sourcecode: maria version File versions

BooleanBinop.C

Go to the documentation of this file.
// Maria boolean binary operator expression class -*- c++ -*-

#ifdef __GNUC__
# pragma implementation
#endif // __GNUC__
#include "BooleanBinop.h"
#include "BoolType.h"
#include "LeafValue.h"
#include "Net.h"
#include "Constant.h"
#include "NotExpression.h"
#include "VariableDefinition.h"
#include "Property.h"
#include "Printer.h"

/** @file BooleanBinop.C
 * Binary operators in Boolean arithmetic
 */

/* Copyright © 1998-2002 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. */

00040 BooleanBinop::BooleanBinop (bool conj,
                      class Expression& left,
                      class Expression& right) :
  Expression (),
  myConj (conj), myLeft (&left), myRight (&right)
{
  assert (myLeft->getKind () == Expression::eUndefined ||
        myLeft->getType ()->getKind () == Type::tBool);
  assert (myRight->getKind () == Expression::eUndefined ||
        myRight->getType ()->getKind () == Type::tBool);
  setType (Net::getBoolType ());
}

00053 BooleanBinop::~BooleanBinop ()
{
  myLeft->destroy ();
  myRight->destroy ();
}

bool
00060 BooleanBinop::isBasic () const
{
  return
    (!myLeft || myLeft->isBasic ()) &&
    (!myRight || myRight->isBasic ());
}

bool
00068 BooleanBinop::isTemporal () const
{
  return
    (myLeft && myLeft->isTemporal ()) ||
    (myRight && myRight->isTemporal ());
}

class Expression*
00076 BooleanBinop::construct (bool conj,
                   class Expression& left,
                   class Expression& right)
{
  if (left == right) {
    right.destroy ();
    return &left;
  }
  else if (left.getKind () == Expression::eNot &&
         right.getKind () == Expression::eNot)
    return NotExpression::construct
      (*construct (!conj,
               *NotExpression::construct (left),
               *NotExpression::construct (right)));
  else if (left.getKind () == Expression::eConstant) {
    const class Value& v = static_cast<class Constant&>(left).getValue ();
    assert (v.getKind () == Value::vLeaf);
    if (conj == bool (static_cast<const class LeafValue&>(v))) {
      left.destroy ();
      return &right;
    }
    else {
      right.destroy ();
      return &left;
    }
  }
  else if (right.getKind () == Expression::eConstant) {
    const class Value& v = static_cast<class Constant&>(right).getValue ();
    assert (v.getKind () == Value::vLeaf);
    if (conj == bool (static_cast<const class LeafValue&>(v))) {
      right.destroy ();
      return &left;
    }
    // optimising "left" away could break short-circuit evaluation
  }

  return (new class BooleanBinop (conj, left, right))->cse ();
}

class Value*
00116 BooleanBinop::do_eval (const class Valuation& valuation) const
{
  class Value* v = myLeft->eval (valuation);
  if (!v)
    return NULL;
  assert (v->getType ().getKind () == Type::tBool);
  assert (v->getKind () == Value::vLeaf);

  if (myConj == bool (static_cast<class LeafValue&>(*v))) {
    delete v;
    if (!(v = myRight->eval (valuation)))
      return 0;
    assert (v->getType ().getKind () == Type::tBool);
    assert (v->getKind () == Value::vLeaf);
  }

  return constrain (valuation, v);
}

class Expression*
00136 BooleanBinop::ground (const class Valuation& valuation,
                  class Transition* transition,
                  bool declare)
{
  class Expression* left = myLeft->ground (valuation, transition, declare);

  if (!left)
    return NULL;
  // short-circuit evaluation
  if (left->getKind () == Expression::eConstant) {
    const class Value& v = static_cast<class Constant*>(left)->getValue ();
    assert (v.getKind () == Value::vLeaf);
    if (myConj != bool (static_cast<const class LeafValue&>(v)))
      return left;
    left->destroy ();
    return myRight->ground (valuation, transition, declare);
  }

  class Expression* right = myRight->ground (valuation, transition, declare);

  if (!right) {
    left->destroy ();
    return NULL;
  }

  assert (valuation.isOK ());

  if (left == myLeft && right == myRight) {
    left->destroy ();
    right->destroy ();
    return copy ();
  }
  else
    return construct (myConj, *left, *right)->ground (valuation);
}

class Expression*
00173 BooleanBinop::substitute (class Substitution& substitution)
{
  class Expression* left = myLeft->substitute (substitution);
  class Expression* right = myRight->substitute (substitution);

  if (left == myLeft && right == myRight) {
    left->destroy ();
    right->destroy ();
    return copy ();
  }
  else {
    class Expression* expr = construct (myConj, *left, *right);
    expr->setType (*getType ());
    return expr;
  }
}

bool
00191 BooleanBinop::depends (const class VariableSet& vars,
                   bool complement) const
{
  return
    myLeft->depends (vars, complement) ||
    myRight->depends (vars, complement);
}

bool
00200 BooleanBinop::forVariables (bool (*operation)
                      (const class Expression&,void*),
                      void* data) const
{
  return
    myLeft->forVariables (operation, data) &&
    myRight->forVariables (operation, data);
}

class Expression*
00210 BooleanBinop::disqualify (const class Transition& transition)
{
  class Expression* left = myLeft->disqualify (transition);
  class Expression* right = myRight->disqualify (transition);


  if (!left || !right) {
    if (!myConj) {
      if (left) return left;
      if (right) return right;
    }
    left->destroy (), right->destroy ();
    return 0;
  }

  if (left == myLeft && right == myRight) {
    left->destroy (), right->destroy ();
    return copy ();
  }

  class Expression* expr = construct (myConj, *left, *right);
  class Valuation valuation;
  if (class Value* v = expr->eval (valuation)) {
    expr->destroy ();
    return (new class Constant (*v))->cse ();
  }
  else
    return expr;
}

class Ltl*
00241 BooleanBinop::toFormula (class Property& property)
{
  return (myLeft->isTemporal () || myRight->isTemporal ())
    ? property.addBinop (myConj ? Property::opAnd : Property::opOr,
                   *myLeft, *myRight)
    : Expression::toFormula (property);
}

class Expression*
00250 BooleanBinop::quantify (bool conj,
                  class Expression& expr,
                  class Valuation& valuation,
                  class Transition* transition,
                  class VariableDefinition& variable,
                  class Expression* condition,
                  bool declare)
{
  assert (valuation.isOK ());
  assert (expr.getType ()->getKind () == Type::tBool);
  assert (!condition || condition->getType ()->getKind () == Type::tBool);

  class Expression* q = expr.copy ();
  if (condition)
    q = conj
      ? construct (false, *NotExpression::construct (*condition), *q)
      : construct (true, *condition, *q);
  valuation.setValue (variable, variable.getType ().getFirstValue ());
  class Expression* result = NULL;
  /** the outcome in case it is constant */
  bool outcome = conj;

  do {
    if (class Expression* e = q->ground (valuation, transition, declare)) {
      assert (valuation.isOKorVar ());
      valuation.clearErrors ();
      if (e->getKind () == Expression::eConstant) {
      const class Value& v = static_cast<class Constant*>(e)->getValue ();
      assert (v.getKind () == Value::vLeaf);
      if (conj != bool (static_cast<const class LeafValue&>(v))) {
        result->destroy (), result = 0;
        outcome = !conj;
        break;
      }
      }
      else
      result = result ? construct (conj, *result, *e) : e;
    }
    else {
      result->destroy (), q->destroy ();
      return NULL;
    }
  }
  while (valuation.increment (variable));

  q->destroy ();

  if (!result)
    result = (new class Constant (*new class LeafValue
                          (Net::getBoolType (), outcome)))->cse ();
  return result;
}

#ifdef EXPR_COMPILE
# include "CExpression.h"

void
BooleanBinop::compile (class CExpression& cexpr,
                   unsigned indent,
                   const char* lvalue,
                   const class VariableSet* vars) const
{
  class StringBuffer& out = cexpr.getOut ();
  myLeft->compile (cexpr, indent, lvalue, vars);
  out.indent (indent);
  out.append ("if (");
  if (!myConj)
    out.append ("!");
  out.append (lvalue);
  out.append (") {\n");
  bool* checkpoint;
  unsigned checkpointSize = cexpr.getCheckpoint (checkpoint);
  myRight->compile (cexpr, indent + 2, lvalue, vars);
  cexpr.setCheckpoint (indent + 2, checkpoint, checkpointSize);
  delete[] checkpoint;
  out.indent (indent);
  out.append ("}\n");
  compileConstraint (cexpr, indent, lvalue);
}

#endif // EXPR_COMPILE

/** Determine whether an expression needs to be enclosed in parentheses
 * @param kind    kind of the expression
 * @return  whether parentheses are necessary
 */
inline static bool
00337 needParentheses (enum Expression::Kind kind)
{
  switch (kind) {
  case Expression::eVariable:
  case Expression::eConstant:
  case Expression::eUndefined:
  case Expression::eStructComponent:
  case Expression::eUnionComponent:
  case Expression::eUnionType:
  case Expression::eVectorIndex:
  case Expression::eTypecast:
  case Expression::eCardinality:
  case Expression::eRelop:
  case Expression::eNot:
  case Expression::eSet:
    return false;
  case Expression::eBinop:
  case Expression::eStruct:
  case Expression::eUnion:
  case Expression::eVector:
  case Expression::eUnop:
  case Expression::eBuffer:
  case Expression::eBufferRemove:
  case Expression::eBufferUnop:
  case Expression::eBufferWrite:
  case Expression::eBufferIndex:
  case Expression::eMarking:
  case Expression::ePlaceContents:
  case Expression::eSubmarking:
  case Expression::eMapping:
  case Expression::eEmptySet:
  case Expression::eStructAssign:
  case Expression::eVectorAssign:
  case Expression::eVectorShift:
    assert (false);
  case Expression::eTransitionQualifier:
  case Expression::eBooleanBinop:
  case Expression::eIfThenElse:
  case Expression::eTemporalBinop:
  case Expression::eTemporalUnop:
    break;
  }

  return true;
}

void
00384 BooleanBinop::display (const class Printer& printer) const
{
  if (isAtomic ()) {
    printer.printRaw ("atom");
    printer.delimiter ('(')++;
  }

  if (::needParentheses (myLeft->getKind ())) {
    printer.delimiter ('(')++;
    myLeft->display (printer);
    --printer.delimiter (')');
  }
  else
    myLeft->display (printer);

  printer.printRaw (myConj ? "&&" : "||");

  if (::needParentheses (myRight->getKind ())) {
    printer.delimiter ('(')++;
    myRight->display (printer);
    --printer.delimiter (')');
  }
  else
    myRight->display (printer);

  if (isAtomic ())
    --printer.delimiter (')');
}

Generated by  Doxygen 1.6.0   Back to index