vc.h

Go to the documentation of this file.

/*****************************************************************************/
/*!
 * \file vc.h
 * \brief Generic API for a validity checker
 * 
 * Author: Clark Barrett
 * 
 * Created: Tue Nov 26 17:45:10 2002
 *
 * <hr>
 * Copyright (C) 2003 by the Board of Trustees of Leland Stanford
 * Junior University and by New York University. 
 *
 * License to use, copy, modify, sell and/or distribute this software
 * and its documentation for any purpose is hereby granted without
 * royalty, subject to the terms and conditions defined in the \ref
 * LICENSE file provided with this distribution.  In particular:
 *
 * - The above copyright notice and this permission notice must appear
 * in all copies of the software and related documentation.
 *
 * - THE SOFTWARE IS PROVIDED "AS-IS", WITHOUT ANY WARRANTIES,
 * EXPRESSED OR IMPLIED.  USE IT AT YOUR OWN RISK.
 * 
 * <hr>
 * 
 */
/*****************************************************************************/

#ifndef _cvcl__include__vc_h_
#define _cvcl__include__vc_h_

#include "expr.h"

/*****************************************************************************/
/*!
 *\defgroup CVCL CVC Lite
 *\brief The top level group which includes all of CVC Lite documentation.
 *@{
 */
/*****************************************************************************/

/*****************************************************************************/
/*!
 *\defgroup BuildingBlocks Building Blocks
 *\brief Code providing basic infrastructure
 */
/*****************************************************************************/

/*****************************************************************************/
/*!
 *\defgroup VC Validity Checker
 *\brief The modules that make up the validity checker
 */
/*****************************************************************************/

/*@}*/ // end of group CVCL

/*****************************************************************************/
/*!
 *\defgroup VC_API Validity Checker API
 * \ingroup VC
 *\brief The library interface of the validity checker (class ValidityChecker)
 */
/*****************************************************************************/

namespace CVCL {

class Context;
class CLFlags;
class Statistics;

/*****************************************************************************/
/*!
 *\class ValidityChecker
 *\brief Generic API for a validity checker
 *\ingroup VC_API
 *\anchor vc
 *
 * Author: Clark Barrett
 *
 * Created: Tue Nov 26 18:24:25 2002
 *
 * All terms and formulas are represented as expressions using the Expr class.
 * The notion of a context is also important.  A context is a "background" set
 * of formulas which are assumed to be true or false.  Formulas can be added to
 * the context explicitly, using assertFormula, or they may be added as part of
 * processing a query command.  At any time, the current set of formulas making
 * up the context can be retrieved using getAssumptions.
 */
/*****************************************************************************/
class ValidityChecker {

public:
  //! Constructor
  ValidityChecker() {}
  //! Destructor
  virtual ~ValidityChecker() {}

  //! Return the set of command-line flags
  /*!  The flags are returned by reference, and if modified, will have an
    immediate effect on the subsequent commands.  Note that not all flags will
    have such an effect; some flags are used only at initialization time (like
    "sat"), and therefore, will not take effect if modified after
    ValidityChecker is created.
  */
  virtual CLFlags& getFlags() const = 0;
  //! Force reprocessing of all flags
  virtual void reprocessFlags() = 0;

  /***************************************************************************/
  /*
   * Static methods
   */
  /***************************************************************************/

  //! Create the set of command line flags with default values; 
  /*!
    \return the set of flags by value
  */
  static CLFlags createFlags();
  //! Create an instance of ValidityChecker
  /*!
    \param flags is the set of command line flags.
  */
  static ValidityChecker* create(const CLFlags& flags);
  //! Create an instance of ValidityChecker using default flag values.
  static ValidityChecker* create();

  /***************************************************************************/
  /*!
   *\name Type-related methods
   * Methods for creating and looking up types
   *\sa class Type
   *@{
   */
  /***************************************************************************/

  // Basic types
  virtual Type boolType() = 0; //!< Create type BOOLEAN

  virtual Type realType() = 0; //!< Create type REAL

  virtual Type intType() = 0; //!< Create type INT

  //! Create a subrange type [l..r]
  /*! l and r can be Null; l=Null represents minus infinity, r=Null is
   * plus infinity.
   */
  virtual Type subrangeType(const Expr& l, const Expr& r) = 0;

  //! Creates a subtype defined by the given predicate
  /*!
   * \param pred is a predicate taking one argument of type T and returning
   * Boolean.  The resulting type is a subtype of T whose elements x are those
   * satisfying the predicate pred(x).
   */
  virtual Type subtypeType(const Expr& pred) = 0;

  // Tuple types
  //! 2-element tuple
  virtual Type tupleType(const Type& type0, const Type& type1) = 0;

  //! 3-element tuple
  virtual Type tupleType(const Type& type0, const Type& type1,
                         const Type& type2) = 0;
  //! n-element tuple (from a vector of types)
  virtual Type tupleType(const std::vector<Type>& types) = 0;

  // Record types
  //! 1-element record
  virtual Type recordType(const std::string& field, const Type& type) = 0;

  //! 2-element record
  /*! Fields will be sorted automatically */
  virtual Type recordType(const std::string& field0, const Type& type0,
                          const std::string& field1, const Type& type1) = 0;
  //! 3-element record
  /*! Fields will be sorted automatically */
  virtual Type recordType(const std::string& field0, const Type& type0,
                          const std::string& field1, const Type& type1,
                          const std::string& field2, const Type& type2) = 0;
  //! n-element record (fields and types must be of the same length)
  /*! Fields will be sorted automatically */
  virtual Type recordType(const std::vector<std::string>& fields,
                          const std::vector<Type>& types) = 0;

  // Datatypes

  //! Single datatype, single constructor
  /*! The types are either type exressions (obtained from a type with
   *  getExpr()) or string expressions containing the name of (one of) the
   *  dataType(s) being defined. */
  virtual Type dataType(const std::string& name,
                        const std::string& constructor,
                        const std::vector<std::string>& selectors,
                        const std::vector<Expr>& types) = 0;

  //! Single datatype, multiple constructors
  /*! The types are either type exressions (obtained from a type with
   *  getExpr()) or string expressions containing the name of (one of) the
   *  dataType(s) being defined. */
  virtual Type dataType(const std::string& name,
                        const std::vector<std::string>& constructors,
                        const std::vector<std::vector<std::string> >& selectors,
                        const std::vector<std::vector<Expr> >& types) = 0;

  //! Multiple datatypes
  /*! The types are either type exressions (obtained from a type with
   *  getExpr()) or string expressions containing the name of (one of) the
   *  dataType(s) being defined. */
  virtual void dataType(const std::vector<std::string>& names,
                        const std::vector<std::vector<std::string> >& constructors,
                        const std::vector<std::vector<std::vector<std::string> > >& selectors,
                        const std::vector<std::vector<std::vector<Expr> > >& types,
                        std::vector<Type>& returnTypes) = 0;

  //! Create an array type (ARRAY typeIndex OF typeData)
  virtual Type arrayType(const Type& typeIndex, const Type& typeData) = 0;

  //! Create a function type typeDom -> typeRan
  virtual Type funType(const Type& typeDom, const Type& typeRan) = 0;

  //! Create a function type (t1,t2,...,tn) -> typeRan
  virtual Type funType(const std::vector<Type>& typeDom, const Type& typeRan) = 0;

  //! Create named user-defined uninterpreted type
  virtual Type createType(const std::string& typeName) = 0;

  //! Create named user-defined interpreted type (type abbreviation)
  virtual Type createType(const std::string& typeName, const Type& def) = 0;

  //! Lookup a user-defined (uninterpreted) type by name
  virtual Type lookupType(const std::string& typeName) = 0;

  /*@}*/ // End of Type-related methods

  /***************************************************************************/
  /*!
   *\name General Expr methods
   *\sa class Expr
   *\sa class ExprManager
   *@{
   */
  /***************************************************************************/

  //! Return the ExprManager
  virtual ExprManager* getEM() = 0;

  //! Create a variable with a given name and type 
  /*!
    \param name is the name of the variable
    \param type is its type.  The type cannot be a function type.
    \return an Expr representation of a new variable
   */
  virtual Expr varExpr(const std::string& name, const Type& type) = 0;

  //! Create a variable with a given name, type, and value
  virtual Expr varExpr(const std::string& name, const Type& type,
                       const Expr& def) = 0;

  //! Create a bound variable with a given name, unique ID (uid) and type 
  /*!
    \param name is the name of the variable
    \param uid is the unique ID (a string), which must be unique for
    each variable
    \param type is its type.  The type cannot be a function type.
    \return an Expr representation of a new variable
   */
  virtual Expr boundVarExpr(const std::string& name,
                            const std::string& uid,
                            const Type& type) = 0;

  //! Get the variable associated with a name, and its type 
  /*!
    \param name is the variable name
    \param type is where the type value is returned

    \return a variable by the name. If there is no such Expr, a NULL \
    Expr is returned.
  */
  virtual Expr lookupVar(const std::string& name, Type* type) = 0;

  //! Get the type of the Expr.
  virtual Type getType(const Expr& e) = 0;

  //! Get the largest supertype of the Expr.
  virtual Type getBaseType(const Expr& e) = 0;

  //! Get the largest supertype of the Type.
  virtual Type getBaseType(const Type& t) = 0;

  //! Get the subtype predicate
  virtual Expr getTypePred(const Type&t, const Expr& e) = 0;

  //! Create a string Expr
  virtual Expr stringExpr(const std::string& str) = 0;

  //! Create an ID Expr
  virtual Expr idExpr(const std::string& name) = 0;

  //! Create a list Expr 
  /*! Intermediate representation for DP-specific expressions.
   *  Normally, the first element of the list is a string Expr
   *  representing an operator, and the rest of the list are the
   *  arguments.  For example, 
   *
   *  kids.push_back(vc->stringExpr("PLUS"));
   *  kids.push_back(x); // x and y are previously created Exprs
   *  kids.push_back(y);
   *  Expr lst = vc->listExpr(kids);
   *
   * Or, alternatively (using its overloaded version):
   *
   * Expr lst = vc->listExpr("PLUS", x, y);
   *
   * or
   *
   * vector<Expr> summands;
   * summands.push_back(x); summands.push_back(y); ...
   * Expr lst = vc->listExpr("PLUS", summands);
   */
  virtual Expr listExpr(const std::vector<Expr>& kids) = 0;

  //! Overloaded version of listExpr with one argument
  virtual Expr listExpr(const Expr& e1) = 0;

  //! Overloaded version of listExpr with two arguments
  virtual Expr listExpr(const Expr& e1, const Expr& e2) = 0;

  //! Overloaded version of listExpr with three arguments
  virtual Expr listExpr(const Expr& e1, const Expr& e2, const Expr& e3) = 0;

  //! Overloaded version of listExpr with string operator and many arguments
  virtual Expr listExpr(const std::string& op,
                        const std::vector<Expr>& kids) = 0;

  //! Overloaded version of listExpr with string operator and one argument
  virtual Expr listExpr(const std::string& op, const Expr& e1) = 0;

  //! Overloaded version of listExpr with string operator and two arguments
  virtual Expr listExpr(const std::string& op, const Expr& e1,
                        const Expr& e2) = 0;

  //! Overloaded version of listExpr with string operator and three arguments
  virtual Expr listExpr(const std::string& op, const Expr& e1,
                        const Expr& e2, const Expr& e3) = 0;

  //! Prints e to the standard output
  virtual void printExpr(const Expr& e) = 0;

  //! Prints e to the given ostream
  virtual void printExpr(const Expr& e, std::ostream& os) = 0;

  //! Parse an expression using a Theory-specific parser
  virtual Expr parseExpr(const Expr& e) = 0;

  //! Parse a type expression using a Theory-specific parser
  virtual Type parseType(const Expr& e) = 0;

  //! Import the Expr from another instance of ValidityChecker
  /*! When expressions need to be passed among several instances of
   *  ValidityChecker, they need to be explicitly imported into the
   *  corresponding instance using this method.  The return result is
   *  an identical expression that belongs to the current instance of
   *  ValidityChecker, and can be safely used as part of more complex
   *  expressions from the same instance.
   */
  virtual Expr importExpr(const Expr& e) = 0;

  //! Import the Type from another instance of ValidityChecker
  /*! \sa getType() */
  virtual Type importType(const Type& t) = 0;

  /*@}*/ // End of General Expr Methods

  /***************************************************************************/
  /*!
   *\name Core expression methods
   * Methods for manipulating core expressions
   *
   * Except for equality and ite, the children provided as arguments must be of
   * type Boolean.
   *@{
   */
  /***************************************************************************/

  //! Return TRUE Expr
  virtual Expr trueExpr() = 0;

  //! Return FALSE Expr
  virtual Expr falseExpr() = 0;

  //! Create negation
  virtual Expr notExpr(const Expr& child) = 0;

  //! Create 2-element conjunction 
  virtual Expr andExpr(const Expr& left, const Expr& right) = 0;

  //! Create n-element conjunction
  virtual Expr andExpr(const std::vector<Expr>& children) = 0;

  //! Create 2-element disjunction
  virtual Expr orExpr(const Expr& left, const Expr& right) = 0;

  //! Create n-element disjunction
  virtual Expr orExpr(const std::vector<Expr>& children) = 0;

  //! Create Boolean implication
  virtual Expr impliesExpr(const Expr& hyp, const Expr& conc) = 0;

  //! Create left IFF right (boolean equivalence)
  virtual Expr iffExpr(const Expr& left, const Expr& right) = 0;

  //! Create an equality expression.
  /*!
    The two children must have the same type, and cannot be of type
    Boolean.
  */
  virtual Expr eqExpr(const Expr& child0, const Expr& child1) = 0;

  //! Create IF ifpart THEN thenpart ELSE elsepart ENDIF
  /*!
    \param ifpart must be of type Boolean.
    \param thenpart and \param elsepart must have the same type, which will
    also be the type of the ite expression.
  */
  virtual Expr iteExpr(const Expr& ifpart, const Expr& thenpart,
                       const Expr& elsepart) = 0;

  /*@}*/ // End of Core expression methods

  /***************************************************************************/
  /*!
   *\name User-defined (uninterpreted) function methods
   * Methods for manipulating uninterpreted function expressions
   *@{
   */
  /***************************************************************************/

  //! Create a named uninterpreted function with a given type
  /*! 
    \param name is the new function's name (as ID Expr)
    \param type is a function type ( [range -> domain] )
  */
  virtual Op createOp(const std::string& name, const Type& type) = 0;

  //! Create a named user-defined function with a given type
  virtual Op createOp(const std::string& name, const Type& type,
                      const Expr& def) = 0;

  //! Unary function application (op must be of function type)
  virtual Expr funExpr(const Op& op, const Expr& child) = 0;

  //! Binary function application (op must be of function type)
  virtual Expr funExpr(const Op& op, const Expr& left, const Expr& right) = 0;

  //! Ternary function application (op must be of function type)
  virtual Expr funExpr(const Op& op, const Expr& child0,
                       const Expr& child1, const Expr& child2) = 0;

  //! n-ary function application (op must be of function type)
  virtual Expr funExpr(const Op& op, const std::vector<Expr>& children) = 0;

  /*@}*/ // End of User-defined (uninterpreted) function methods

  /***************************************************************************/
  /*!
   *\name Arithmetic expression methods
   * Methods for manipulating arithmetic expressions
   *
   * These functions create arithmetic expressions.  The children provided
   * as arguments must be of type Real.
   *@{
   */
  /***************************************************************************/

  //! Create a rational number with numerator n and denominator d.
  /*!
    \param n the numerator
    \param d the denominator, cannot be 0.
  */
  virtual Expr ratExpr(int n, int d = 1) = 0;

  //! Create a rational number with numerator n and denominator d.
  /*!
    Here n and d are given as strings.  They are converted to
    arbitrary-precision integers according to the given base.
  */
  virtual Expr ratExpr(const std::string& n, const std::string& d, int base) = 0;

  //! Create a rational from a single string.  
  /*!  
    \param n can be a string containing an integer, a pair of integers
    "nnn/ddd", or a number in the fixed or floating point format.
    \param base is the base in which to interpret the string.
  */
  virtual Expr ratExpr(const std::string& n, int base = 10) = 0;

  //! Unary minus.
  virtual Expr uminusExpr(const Expr& child) = 0;

  //! Create 2-element sum (left + right)
  virtual Expr plusExpr(const Expr& left, const Expr& right) = 0;

  //! Make a difference (left - right)
  virtual Expr minusExpr(const Expr& left, const Expr& right) = 0;

  //! Create a product (left * right)
  virtual Expr multExpr(const Expr& left, const Expr& right) = 0;

  //! Create a power expression (x ^ n); n must be integer
  virtual Expr powExpr(const Expr& x, const Expr& n) = 0;

  //! Create expression x / y
  virtual Expr divideExpr(const Expr& numerator, const Expr& denominator) = 0;

  //! Create (left < right)
  virtual Expr ltExpr(const Expr& left, const Expr& right) = 0;

  //! Create (left <= right)
  virtual Expr leExpr(const Expr& left, const Expr& right) = 0;

  //! Create (left > right)
  virtual Expr gtExpr(const Expr& left, const Expr& right) = 0;

  //! Create (left >= right)
  virtual Expr geExpr(const Expr& left, const Expr& right) = 0;

  /*@}*/ // End of Arithmetic expression methods

  /***************************************************************************/
  /*!
   *\name Record expression methods
   * Methods for manipulating record expressions
   *@{
   */
  /***************************************************************************/

  //! Create a 1-element record value (# field := expr #)
  /*! Fields will be sorted automatically */
  virtual Expr recordExpr(const std::string& field, const Expr& expr) = 0;

  //! Create a 2-element record value (# field0 := expr0, field1 := expr1 #)
  /*! Fields will be sorted automatically */
  virtual Expr recordExpr(const std::string& field0, const Expr& expr0,
                          const std::string& field1, const Expr& expr1) = 0;

  //! Create a 3-element record value (# field_i := expr_i #)
  /*! Fields will be sorted automatically */
  virtual Expr recordExpr(const std::string& field0, const Expr& expr0,
                          const std::string& field1, const Expr& expr1,
                          const std::string& field2, const Expr& expr2) = 0;

  //! Create an n-element record value (# field_i := expr_i #)
  /*!
   * \param fields
   * \param exprs must be the same length as fields
   *
   * Fields will be sorted automatically
   */
  virtual Expr recordExpr(const std::vector<std::string>& fields,
                          const std::vector<Expr>& exprs) = 0;

  //! Create record.field (field selection)
  /*! Create an expression representing the selection of a field from
    a record. */
  virtual Expr recSelectExpr(const Expr& record, const std::string& field) = 0;

  //! Record update; equivalent to "record WITH .field := newValue"
  /*! Notice the `.' before field in the presentation language (and
    the comment above); this is to distinguish it from datatype
    update.
  */
  virtual Expr recUpdateExpr(const Expr& record, const std::string& field,
                             const Expr& newValue) = 0;

  /*@}*/ // End of Record expression methods

  /***************************************************************************/
  /*!
   *\name Array expression methods
   * Methods for manipulating array expressions
   *@{
   */
  /***************************************************************************/

  //! Create an expression array[index] (array access)
  /*! Create an expression for the value of array at the given index */
  virtual Expr readExpr(const Expr& array, const Expr& index) = 0;

  //! Array update; equivalent to "array WITH index := newValue"
  virtual Expr writeExpr(const Expr& array, const Expr& index,
                         const Expr& newValue) = 0;

  /*@}*/ // End of Array expression methods

  /***************************************************************************/
  /*!
   *\name Other expression methods
   * Methods for manipulating other kinds of expressions
   *@{
   */
  /***************************************************************************/

  //! Tuple expression
  virtual Expr tupleExpr(const std::vector<Expr>& exprs) = 0;

  //! Tuple select; equivalent to "tuple.n", where n is an numeral (e.g. tup.5)
  virtual Expr tupleSelectExpr(const Expr& tuple, int index) = 0;

  //! Tuple update; equivalent to "tuple WITH index := newValue"
  virtual Expr tupleUpdateExpr(const Expr& tuple, int index,
                               const Expr& newValue) = 0;

  //! Datatype constructor expression
  virtual Expr datatypeConsExpr(const std::string& constructor, const std::vector<Expr>& args) = 0;

  //! Datatype selector expression
  virtual Expr datatypeSelExpr(const std::string& selector, const Expr& arg) = 0;

  //! Datatype tester expression
  virtual Expr datatypeTestExpr(const std::string& constructor, const Expr& arg) = 0;

  //! Universal quantifier
  virtual Expr forallExpr(const std::vector<Expr>& vars, const Expr& body) = 0;

  //! Existential quantifier
  virtual Expr existsExpr(const std::vector<Expr>& vars, const Expr& body) = 0;

  //! Lambda-expression
  virtual Op lambdaExpr(const std::vector<Expr>& vars, const Expr& body) = 0;

  //! Symbolic simulation expression
  /*!
   * \param f is the next state function (LAMBDA-expression)
   * \param s0 is the initial state
   * \param inputs is the vector of LAMBDA-expressions representing
   * the sequences of inputs to f
   * \param n is a constant, the number of cycles to run the simulation.
   */
  virtual Expr simulateExpr(const Expr& f, const Expr& s0,
                            const std::vector<Expr>& inputs,
                            const Expr& n) = 0;

  /*@}*/ // End of Other expression methods

  /***************************************************************************/
  /*!
   *\name Validity checking methods
   * Methods related to validity checking
   *
   * This group includes methods for asserting formulas, checking
   * validity in the given logical context, manipulating the scope
   * level of the context, etc.
   *@{
   */
  /***************************************************************************/

  //! Set the resource limit (0==unlimited, 1==exhausted).
  /*! Currently, the limit is the total number of processed facts. */
  virtual void setResourceLimit(unsigned limit) = 0;

  //! Assert a new formula in the current context.
  /*! This creates the assumption e |- e.  The formula must have Boolean type.
  */
  virtual void assertFormula(const Expr& e) = 0;

  //! Register an atomic formula of interest.
  /*! Registered atoms are tracked by the decision procedures.  If one of them
      is deduced to be true or false, it is added to a list of implied literals.
      Implied literals can be retrieved with the getImpliedLiteral function */
  virtual void registerAtom(const Expr& e) = 0;

  //! Return next literal implied by last assertion.  Null Expr if none.
  /*! Returned literals are either registered atomic formulas or their negation
   */
  virtual Expr getImpliedLiteral() = 0;

  //! Simplify e with respect to the current context
  virtual Expr simplify(const Expr& e) = 0;

  //! Simplify e into e', and return the Theorem3 object for e = e'
  /*! This function must be called only when +tcc flag is set.  
   * 
   * The resulting Theorem3 (a 3-valued theorem object) can be used to
   * extract the simplified expression and the proof of its
   * equivalence to the origital expression: thm.getExpr() [to get
   * e=e'], thm.getRHS() [to get just e'], and thm.getProof() [to get
   * a Proof object].
   */
  virtual Theorem3 simplifyThm(const Expr& e) = 0;

  //! Simpfy e, ignoring TCCs (assumes total interpretation)
  virtual Theorem simplifyThm2(const Expr& e) = 0;
  
  //! Dump all variables in e
  virtual void printV(const Expr& e) = 0;
  
  //! Check validity of e in the current context.
  /*! If the result is true, then the resulting context is the same as
    the starting context.  If the result is false, then the resulting
    context is a context in which e is false.  e must have Boolean
    type.
    
    \param e is the queried formula
    
    \param tcc is a flag indicating that the formula is a TCC, which
    is assumed to be always defined (so, its TCC is not computed)
  */
  virtual bool query(const Expr& e, bool tcc = false) = 0;

  //! Check satisfiability of the expr in the current context.
  /*! Returns false if the context is satisfiable and true if it is
    unsatisfiable.  Note that this is equivalent to QUERY !e */
  virtual bool checkUnsat(const Expr& e) = 0;

  //! Get the next model
  /*! This method should only be called after a query which returns
    false.  Returns false if another counterexample is found, true
    otherwise. */
  virtual bool checkContinue() = 0;

  //! Restart the most recent query with e as an additional assertion.
  /*! This method should only be called after a query which returns false.
    Returns true if the resulting query is valid and false otherwise. */
  virtual bool restart(const Expr& e) = 0;

  //! Returns to context immediately before last invalid query.
  /*! This method should only be called after a query which returns false.
   */
  virtual void returnFromCheck() = 0;

  //! Get assumptions made by the user in this and all previous contexts.
  /*! User assumptions are created either by calls to assertFormula or by a
   * call to query.  In the latter case, the negated query is added as an
   * assumption.
   * \param assumptions should be empty on entry.
  */
  virtual void getUserAssumptions(std::vector<Expr>& assumptions) = 0;

  //! Get assumptions made internally in this and all previous contexts.
  /*! Internal assumptions are literals assumed by the sat solver.
   * \param assumptions should be empty on entry.
  */
  virtual void getInternalAssumptions(std::vector<Expr>& assumptions) = 0;

  //! Get all assumptions made in this and all previous contexts.
  /*! \param assumptions should be empty on entry.
  */
  virtual void getAssumptions(std::vector<Expr>& assumptions) = 0;

  //! Returns the set of assumptions used in the proof of queried formula.
  /*! It returns a subset of getAssumptions().  If the last query was false
   *  or there has not yet been a query, it does nothing.
   *  \param assumptions should be empty on entry.
  */
  virtual void getAssumptionsUsed(std::vector<Expr>& assumptions) = 0;

  //! Return the internal assumptions that make the queried formula false.
  /*! This method should only be called after a query which returns
    false.  It will try to return the simplest possible subset of
    the internal assumptions sufficient to make the queried expression
    false.
    \param assumptions should be empty on entry.
    \param inOrder if true, returns the assumptions in the order they
    were made.  This is slightly more expensive than inOrder = false.
  */
  virtual void getCounterExample(std::vector<Expr>& assumptions,
                                 bool inOrder=true) = 0;

  //! Will assign concrete values to all user created variables
  /*! This function should only be called after a query which return false.
  */  
  virtual void getConcreteModel(ExprMap<Expr> & m) = 0;

  //! Returns true if the current context is inconsistent.
  /*! Also returns a minimal set of assertions used to determine the
   inconsistency.  
   \param assumptions should be empty on entry.
  */
  virtual bool inconsistent(std::vector<Expr>& assumptions) = 0;

  //! Returns true if the invalid result from last query() is imprecise
  /*!
   * Some decision procedures in CVC Lite are incomplete (quantifier
   * elimination, non-linear arithmetic, etc.).  If any incomplete
   * features were used during the last query(), and the result is
   * "invalid" (query() returns false), then this result is
   * inconclusive.  It means that the system gave up the search for
   * contradiction at some point.
   */
  virtual bool incomplete() = 0;

  //! Returns true if the invalid result from last query() is imprecise
  /*!
   * \sa incomplete()
   *
   * The argument is filled with the reasons for incompleteness (they
   * are intended to be shown to the end user).
   */
  virtual bool incomplete(std::vector<std::string>& reasons) = 0;

  //! Returns the proof term for the last proven query
  /*! If there has not been a successful query, it should return a NULL proof
  */
  virtual Proof getProof() = 0;

  //! Returns the TCC of the last assumption or query
  /*! Returns Null if no assumptions or queries were performed. */
  virtual const Expr& getTCC() = 0;

  //! Return the set of assumptions used in the proof of the last TCC
  virtual void getAssumptionsTCC(std::vector<Expr>& assumptions) = 0;

  //! Returns the proof of TCC of the last assumption or query
  /*! Returns Null if no assumptions or queries were performed. */
  virtual const Proof& getProofTCC() = 0;

  //! After successful query, return its closure |- Gamma => phi
  /*! Turn a valid query Gamma |- phi into an implication
   * |- Gamma => phi.
   *
   * Returns Null if last query was invalid.
   */
  virtual const Expr& getClosure() = 0;

  //! Construct a proof of the query closure |- Gamma => phi
  /*! Returns Null if last query was Invalid. */
  virtual const Proof& getProofClosure() = 0;

  /*@}*/ // End of Validity checking methods

  /***************************************************************************/
  /*!
   *\name Context methods
   * Methods for manipulating contexts
   *
   * Contexts support stack-based push and pop.  There are two
   * separate notions of the current context stack.  stackLevel(), push(),
   * pop(), and popto() work with the user-level notion of the stack.
   *
   * scopeLevel(), pushScope(), popScope(), and poptoScope() work with
   * the internal stack which is more fine-grained than the user
   * stack.
   *
   * Do not use the scope methods unless you know what you are doing.
   * *@{
   */
  /***************************************************************************/

  //! Returns the current stack level.  Initial level is 0.
  virtual int stackLevel() = 0;

  //! Checkpoint the current context and increase the scope level
  virtual void push() = 0;

  //! Restore the current context to its state at the last checkpoint
  virtual void pop() = 0;

  //! Restore the current context to the given stackLevel.
  /*!
    \param stackLevel should be greater than or equal to 0 and less
    than or equal to the current scope level.
  */
  virtual void popto(int stackLevel) = 0;

  //! Returns the current scope level.  Initially, the scope level is 1.
  virtual int scopeLevel() = 0;

  /*! @brief Checkpoint the current context and increase the
   * <strong>internal</strong> scope level.  Do not use unless you
   * know what you're doing!
   */
  virtual void pushScope() = 0;

  /*! @brief Restore the current context to its state at the last
   * <strong>internal</strong> checkpoint.  Do not use unless you know
   * what you're doing!
   */
  virtual void popScope() = 0;

  //! Restore the current context to the given scopeLevel.
  /*!
    \param scopeLevel should be less than or equal to the current scope level.

    If scopeLevel is less than 1, then the current context is reset
    and the scope level is set to 1.
  */
  virtual void poptoScope(int scopeLevel) = 0;

  //! Get the current context
  virtual Context* getCurrentContext() = 0;

  /*@}*/ // End of Context methods

  /***************************************************************************/
  /*!
   *\name Reading files
   * Methods for reading external files
   *@{
   */
  /***************************************************************************/
  
  //! Read and execute the commands from a file given by name ("" means stdin)
  virtual void loadFile(const std::string& fileName,
                        InputLanguage lang = PRESENTATION_LANG,
                        bool interactive = false) = 0;

  //! Read and execute the commands from a stream
  virtual void loadFile(std::istream& is,
                        InputLanguage lang = PRESENTATION_LANG,
                        bool interactive = false) = 0;

  /*@}*/ // End of methods for reading files

  /***************************************************************************/
  /*!
   *\name Reporting Statistics
   * Methods for collecting and reporting run-time statistics
   *@{
   */
  /***************************************************************************/
  
  //! Get statistics object
  virtual Statistics& getStatistics() = 0;

  //! Print collected statistics to stdout
  virtual void printStatistics() = 0;

  /*@}*/ // End of Statistics Methods


}; // End of class ValidityChecker

} // End of namespace CVCL

#endif

---