diff options
| author | Morgan Deters <mdeters@gmail.com> | 2009-11-12 20:38:10 +0000 |
|---|---|---|
| committer | Morgan Deters <mdeters@gmail.com> | 2009-11-12 20:38:10 +0000 |
| commit | 13a6669a35aee32c03f8d29fe386aca95d2fbd8f (patch) | |
| tree | b126afb6c384dd45db0249e8096cf733a74daa95 | |
| parent | 5b5474281c4cdc880bff8b9e38b84dc84f88e50c (diff) | |
parser, minisat, other things..
40 files changed, 8503 insertions, 55 deletions
@@ -1,8 +1,37 @@ The core authors and designers of CVC4 are: -Clark Barrett <barrett@cs.nyu.edu>, New York University -Christopher Conway <cconway@cs.nyu.edu>, New York University -Morgan Deters <mdeters@cs.nyu.edu>, New York University -Tim King <taking@cs.nyu.edu>, New York University -Dejan Jovanovic <dejan@cs.nyu.edu>, New York University + Clark Barrett <barrett@cs.nyu.edu>, New York University + Christopher Conway <cconway@cs.nyu.edu>, New York University + Morgan Deters <mdeters@cs.nyu.edu>, New York University + Yeting Ge <yeting@cs.nyu.edu>, New York University + Tim King <taking@cs.nyu.edu>, New York University + Mina Jeong <mjeong@cs.nyu.edu>, New York University + Dejan Jovanovic <dejan@cs.nyu.edu>, New York University +The following individuals contributed code to CVC3 that may have been incorporated into CVC4: + + Clark Barrett, New York University + Christopher Conway <cconway@cs.nyu.edu>, New York University + Alexander Fuchs, University of Iowa + Yeting Ge, New York Univeristy + George Hagen, University of Iowa + Dejan Jovanovic <dejan@cs.nyu.edu>, New York University + +The following individuals contributed code to CVC Lite that may have been incorporated in CVC4: + + Clark Barrett, New York University + Sergey Berezin, Stanford University + Cristian Cadar, Stanford University + Jake Donham, New York University + Yeting Ge, New York Univeristy + Vijay Ganesh, Stanford University + Deepak Goyal, Calypto + Ying Hu, New York University + Sean McLaughlin, New York University + Mehul Trivedi, Stanford University + Michael Veksler, Technion, Israel + Daniel Wichs, Stanford University + Mark Zavislak, Stanford University + Jim Zhuang, Stanford University + +CVC4 contains MiniSAT code by Niklas Een and Niklas Sorensson @@ -5,3 +5,28 @@ All rights reserved. This is a prerelease version; distribution is restricted. -- Morgan Deters <mdeters@cs.nyu.edu> Mon, 02 Nov 2009 17:54:27 -0500 + +CVC4 incorporates MiniSat code, excluded from the above copyright. +See src/sat/minisat. + + MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + + 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. + diff --git a/Makefile.am b/Makefile.am index b224de9b0..451ef0e3a 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,4 +1,4 @@ AUTOMAKE_OPTIONS = foreign -ACLOCAL_AMFLAGS = -I m4 +ACLOCAL_AMFLAGS = -I config SUBDIRS = src doc contrib diff --git a/autogen.sh b/autogen.sh index 612c5c204..a250f6b82 100755 --- a/autogen.sh +++ b/autogen.sh @@ -1,11 +1,11 @@ #!/bin/sh -ex cd "$(dirname "$0")" -mkdir -p m4 +mkdir -p config libtoolize --copy -autoheader -I m4 +autoheader -I config touch NEWS README AUTHORS ChangeLog touch stamp-h -aclocal -I m4 -autoconf -I m4 +aclocal -I config +autoconf -I config automake -ac --foreign diff --git a/configure.ac b/configure.ac index 804401a92..53fecffb1 100644 --- a/configure.ac +++ b/configure.ac @@ -3,15 +3,28 @@ AC_PREREQ([2.63]) AC_INIT([src/include/vc.h]) +AC_CONFIG_AUX_DIR([config]) +#AC_CONFIG_LIBOBJ_DIR([lib]) +AC_CONFIG_MACRO_DIR([config]) AM_INIT_AUTOMAKE(cvc4, prerelease) -AC_CONFIG_MACRO_DIR([m4]) AC_CONFIG_HEADERS([config.h]) +AM_MAINTAINER_MODE +LT_INIT + +AC_LIBTOOL_WIN32_DLL # Checks for programs. AC_PROG_CC AC_PROG_CXX AC_PROG_INSTALL AC_PROG_LIBTOOL +AM_PROG_LEX +AC_PROG_YACC + +AC_CHECK_PROG(DOXYGEN, doxygen, doxygen,) +if [ "$DOXYGEN" = '' ]; then + echo 'WARNING: documentation targets require doxygen. Set your PATH appropriately or set DOXYGEN to point to a valid doxygen binary.' +fi # Checks for libraries. AC_CHECK_LIB(gmp, __gmpz_init, , [AC_MSG_ERROR([GNU MP not found, see http://gmplib.org/])]) @@ -23,6 +36,7 @@ AC_HEADER_STDBOOL AC_TYPE_UINT16_T AC_TYPE_UINT32_T AC_TYPE_UINT64_T +AC_TYPE_SIZE_T # Checks for library functions. @@ -31,6 +45,8 @@ AC_CONFIG_FILES([ contrib/Makefile doc/Makefile src/Makefile - src/include/Makefile + src/parser/Makefile + src/sat/Makefile + src/sat/minisat/Makefile ]) AC_OUTPUT diff --git a/src/Makefile.am b/src/Makefile.am index 11fef4d27..f7d0c0103 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -1 +1,25 @@ INCLUDES = -I@srcdir@/include + +SUBDIRS = parser sat + +lib_LTLIBRARIES = libcvc4.la + +libcvc4_la_LIBADD = \ + sat/parser/libparser.a + sat/minisat/libminisat.a + +EXTRA_DIST = \ + include/assert.h \ + include/attr_type.h \ + include/command.h + include/expr_attribute.h \ + include/expr_builder.h \ + include/expr.h \ + include/expr_manager.h \ + include/expr_value.h \ + include/kind.h \ + include/parser.h \ + include/sat.h \ + include/unique_id.h \ + include/vc.h + diff --git a/src/include/Makefile.am b/src/include/Makefile.am deleted file mode 100644 index fa37abd9a..000000000 --- a/src/include/Makefile.am +++ /dev/null @@ -1,14 +0,0 @@ -EXTRA_DIST = \ - assert.h \ - attr_type.h \ - command.h - expr_attribute.h \ - expr_builder.h \ - expr.h \ - expr_manager.h \ - expr_value.h \ - kind.h \ - parser.h \ - sat.h \ - unique_id.h \ - vc.h diff --git a/src/include/exception.h b/src/include/exception.h new file mode 100644 index 000000000..3502fdf0c --- /dev/null +++ b/src/include/exception.h @@ -0,0 +1,47 @@ +/********************* -*- C++ -*- */ +/** exception.h + ** This file is part of the CVC4 prototype. + ** + ** Exception class. + ** + ** The Analysis of Computer Systems Group (ACSys) + ** Courant Institute of Mathematical Sciences + ** New York University + **/ + +#ifndef __CVC4_EXCEPTION_H +#ifndef __CVC4_EXCEPTION_H + +#include <string> +#include <iostream> + +namespace CVC4 { + + class Exception { + protected: + std::string d_msg; + public: + // Constructors + Exception(): d_msg("Unknown exception") { } + Exception(const std::string& msg): d_msg(msg) { } + Exception(const char* msg): d_msg(msg) { } + // Destructor + virtual ~Exception() { } + // NON-VIRTUAL METHODs for setting and printing the error message + void setMessage(const std::string& msg) { d_msg = msg; } + // Printing: feel free to redefine toString(). When inherited, + // it's recommended that this method print the type of exception + // before the actual message. + virtual std::string toString() const { return d_msg; } + // No need to overload operator<< for the inherited classes + friend std::ostream& operator<<(std::ostream& os, const Exception& e); + + }; // end of class Exception + + inline std::ostream& operator<<(std::ostream& os, const Exception& e) { + return os << e.toString(); + } + +}/* CVC4 namespace */ + +#endif /* __CVC4_EXCEPTION_H */ diff --git a/src/include/parser.h b/src/include/parser.h index c5af769e3..63a448b28 100644 --- a/src/include/parser.h +++ b/src/include/parser.h @@ -2,6 +2,8 @@ /** parser.h ** This file is part of the CVC4 prototype. ** + ** Parser abstraction. + ** ** The Analysis of Computer Systems Group (ACSys) ** Courant Institute of Mathematical Sciences ** New York University @@ -10,37 +12,52 @@ #ifndef __CVC4_PARSER_H #define __CVC4_PARSER_H -#include <iostream> -#include "vc.h" -#include "expr.h" +#include "exception.h" +#include "lang.h" namespace CVC4 { -// In terms of abstraction, this is below (and provides services to) -// the main CVC4 binary and above (and requires the services of) -// ValidityChecker. - -class Parser { -private:// maybe protected is better ? - ValidityChecker *d_vc; - -public: - Parser(ValidityChecker* vc); - - /** - * Process a file. Overridden in subclasses to support SMT-LIB - * format, CVC4 presentation language, etc. In subclasses, this - * function should parse terms, build Command objects, and pass them - * to dispatch(). - */ - virtual Expr process(std::istream&) = 0; - - /** - * Dispatch a command. - */ - void dispatch(const Command&); -};/* class Parser */ - -} /* CVC4 namespace */ + class ValidityChecker; + class Expr; + + // Internal parser state and other data + class ParserData; + + class Parser { + private: + ParserData* d_data; + // Internal methods for constructing and destroying the actual parser + void initParser(); + void deleteParser(); + public: + // Constructors + Parser(ValidityChecker* vc, InputLanguage lang, + // The 'interactive' flag is ignored when fileName != "" + bool interactive = true, + const std::string& fileName = ""); + Parser(ValidityChecker* vc, InputLanguage lang, std::istream& is, + bool interactive = false); + // Destructor + ~Parser(); + // Read the next command. + Expr next(); + // Check if we are done (end of input has been reached) + bool done() const; + // The same check can be done by using the class Parser's value as + // a Boolean + operator bool() const { return done(); } + void printLocation(std::ostream & out) const; + // Reset any local data that depends on validity checker + void reset(); + }; // end of class Parser + + // The global pointer to ParserTemp. Each instance of class Parser + // sets this pointer before any calls to the lexer. We do it this + // way because flex and bison use global vars, and we want each + // Parser object to appear independent. + class ParserTemp; + extern ParserTemp* parserTemp; + +}/* CVC4 namespace */ #endif /* __CVC4_PARSER_H */ diff --git a/src/include/parser_exception.h b/src/include/parser_exception.h new file mode 100644 index 000000000..8bad801f4 --- /dev/null +++ b/src/include/parser_exception.h @@ -0,0 +1,36 @@ +/********************* -*- C++ -*- */ +/** exception.h + ** This file is part of the CVC4 prototype. + ** + ** Exception class. + ** + ** The Analysis of Computer Systems Group (ACSys) + ** Courant Institute of Mathematical Sciences + ** New York University + **/ + +#ifndef __CVC4_PARSER_EXCEPTION_H +#define __CVC4_PARSER_EXCEPTION_H + +#include "exception.h" +#include <string> +#include <iostream> + +namespace CVC4 { + + class ParserException: public Exception { + public: + // Constructors + ParserException() { } + ParserException(const std::string& msg): Exception(msg) { } + ParserException(const char* msg): Exception(msg) { } + // Destructor + virtual ~ParserException() { } + virtual std::string toString() const { + return "Parse Error: " + d_msg; + } + }; // end of class ParserException + +}/* CVC4 namespace */ + +#endif /* __CVC4_PARSER_EXCEPTION_H */ diff --git a/src/include/parser_temp.h b/src/include/parser_temp.h new file mode 100644 index 000000000..d64a770e4 --- /dev/null +++ b/src/include/parser_temp.h @@ -0,0 +1,76 @@ +/********************* -*- C++ -*- */ +/** parser_temp.h + ** This file is part of the CVC4 prototype. + ** + ** A temporary holder for data used with the parser. + ** + ** The Analysis of Computer Systems Group (ACSys) + ** Courant Institute of Mathematical Sciences + ** New York University + **/ + +#ifndef __CVC4_PARSER_TEMP_H +#define __CVC4_PARSER_TEMP_H + +#include <iostream> + +#include "expr.h" +#include "exception.h" + +namespace CVC4 { + + class ValidityChecker; + + class ParserTemp { + private: + // Counter for uniqueID of bound variables + int d_uid; + // The main prompt when running interactive + std::string prompt1; + // The interactive prompt in the middle of a multi-line command + std::string prompt2; + // The currently used prompt + std::string prompt; + public: + ValidityChecker* vc; + std::istream* is; + // The current input line + int lineNum; + // File name + std::string fileName; + // The last parsed Expr + Expr expr; + // Whether we are done or not + bool done; + // Whether we are running interactive + bool interactive; + // Whether arrays are enabled for smt-lib format + bool arrFlag; + // Whether bit-vectors are enabled for smt-lib format + bool bvFlag; + // Size of bit-vectors for smt-lib format + int bvSize; + // Did we encounter a formula query (smtlib) + bool queryParsed; + // Default constructor + ParserTemp() : d_uid(0), prompt1("CVC> "), prompt2("- "), + prompt("CVC> "), lineNum(1), done(false), arrFlag(false), queryParsed(false) { } + // Parser error handling (implemented in parser.cpp) + int error(const std::string& s); + // Get the next uniqueID as a string + std::string uniqueID() { + std::ostringstream ss; + ss << d_uid++; + return ss.str(); + } + // Get the current prompt + std::string getPrompt() { return prompt; } + // Set the prompt to the main one + void setPrompt1() { prompt = prompt1; } + // Set the prompt to the secondary one + void setPrompt2() { prompt = prompt2; } + }; + +}/* CVC4 namespace */ + +#endif /* __CVC4_PARSER_TEMP_H */ diff --git a/src/parser/Makefile.am b/src/parser/Makefile.am new file mode 100644 index 000000000..0ebcad8c7 --- /dev/null +++ b/src/parser/Makefile.am @@ -0,0 +1,18 @@ +INCLUDES = -I@srcdir@/../include + +noinst_LIBRARIES = libparser.a + +libparser_a_SOURCES = \ + pl_scanner.lpp \ + pl.ypp \ + smtlib_scanner.lpp \ + smtlib.ypp \ + parser.cpp + +BUILT_SOURCES = \ + pl_scanner.lpp \ + pl.ypp \ + smtlib_scanner.lpp \ + smtlib.ypp + + diff --git a/src/parser/parser.cpp b/src/parser/parser.cpp new file mode 100644 index 000000000..35ca74ecd --- /dev/null +++ b/src/parser/parser.cpp @@ -0,0 +1,21 @@ +/********************* -*- C++ -*- */ +/** parser.cpp + ** This file is part of the CVC4 prototype. + ** + ** Parser implementation. + ** + ** The Analysis of Computer Systems Group (ACSys) + ** Courant Institute of Mathematical Sciences + ** New York University + **/ + +#include "parser.h" +#include "parser_temp.h" +#include "parser_exception.h" + +namespace CVC4 { + +ParserTemp *parserTemp; + +}/* CVC4 namespace */ + diff --git a/src/parser/pl.ypp b/src/parser/pl.ypp new file mode 100644 index 000000000..dfed55dbb --- /dev/null +++ b/src/parser/pl.ypp @@ -0,0 +1,1993 @@ +%{ +/*****************************************************************************/ +/*! + * \file PL.y + * + * Author: Sergey Berezin + * + * Created: Feb 06 03:00:43 GMT 2003 + * + * <hr> + * + * 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. + * + * <hr> + * + */ +/*****************************************************************************/ +/* PL.y + Aaron Stump, 4/14/01 + + This file contains the bison code for the parser that reads in CVC + commands in the presentation language (hence "PL"). +*/ + +#include "vc.h" +#include "parser_exception.h" +#include "parser_temp.h" +#include "rational.h" + +// Exported shared data +namespace CVC4 { + extern ParserTemp* parserTemp; +} +// Define shortcuts for various things +#define TMP CVC4::parserTemp +#define EXPR CVC4::parserTemp->expr +#define VC (CVC4::parserTemp->vc) +#define RAT(args) CVC4::newRational args + +// Suppress the bogus warning suppression in bison (it generates +// compile error) +#undef __GNUC_MINOR__ + +/* stuff that lives in PL.lex */ +extern int PLlex(void); + +int PLerror(const char *s) +{ + std::ostringstream ss; + ss << CVC4::parserTemp->fileName << ":" << CVC4::parserTemp->lineNum + << ": " << s; + return CVC4::parserTemp->error(ss.str()); +} + + +namespace CVC4 { + +// File-static auxiliary funcion to wrap accessors upto the index i +// (not inclusive) around "e". Used to rebuild the UPDATE expressions. +static Expr wrapAccessors(const Expr& e, + const std::vector<Expr>& accessors, + const int i) { + DebugAssert((int)accessors.size() >= i, "wrapAccessors: too few accessors"); + Expr res(e); + for(int j=0; j<i; j++) { + const Expr& acc = accessors[j]; + switch(acc.getKind()) { + case ID: // Datatype: apply the accessor directly to 'res' + res = VC->listExpr(acc, res); + break; + case RAW_LIST: + DebugAssert(acc.arity() == 2 && acc[0].getKind() == ID, + "PL.y: wrong number of arguments in the accessor of WITH: " + +acc.toString()); + res = VC->listExpr(acc[0], res, acc[1]); + break; + default: + DebugAssert(false, "PL.y: Bad accessor in WITH: "+acc.toString()); + } + } + return res; +} + +// Convert a complex WITH statement into a bunch of nested simple UPDATEs + +// Updator "e1 WITH accessors := e2" is represented as +// (e1 (accessor1 accessor2 ... ) e2), where the accessors are: +// (READ idx) +// ID (datatype constructor's argument) +// (RECORD_SELECT ID) +// and (TUPLE_SELECT num). + +// We rebuild this into nested RECORD_UPDATE, WRITE, +// TUPLE_UPDATE, and DATATYPE_UPDATE expressions. For example: +// +// e WITH [idx] car.f := newVal is transformed into +// e WITH [idx] := (e[idx] WITH car := (car(e[idx]) WITH .f := newVal)) +// which is represented as +// (WRITE e idx +// (DATATYPE_UPDATE (READ e idx) car +// (RECORD_UPDATE (car (READ e idx)) f newVal))). +// Here "car" and "f" are identifiers (ID "car") and (ID "f"). + +static Expr PLprocessUpdate(const CVC4::Expr& e, + const CVC4::Expr& update) { + TRACE("parser verbose", "PLprocessUpdate(", e, ") {"); + DebugAssert(update.arity() == 2,"PL.y: Bad WITH statement: " + +update.toString()); + // Rebuild accessors: resolve ID in (READ (ID "name")) and leave + // the rest alone + TRACE("parser verbose", "PLprocessUpdate: update[0] = ", update[0], ""); + std::vector<Expr> acc; + for(Expr::iterator i=update[0].begin(), iend=update[0].end(); i!=iend; ++i) { + TRACE("parser verbose", "*i = ", *i, ""); + acc.push_back(*i); + } + TRACE("parser verbose", "acc.size() = ", acc.size(), ""); + TRACE("parser verbose", "accessors = ", VC->listExpr(acc), ""); + // 'res' serves as the accumulator of updators; initially it is + // newVal (which is update[1]). We run through accessors in reverse + // order, wrapping this accumulator with the corresponding + // updators. + Expr res(update[1]); + // Rebuilding the original expression "e" + // The main loop + for(int i=acc.size()-1; i>=0; i--) { + Expr ac(acc[i]); // The current accessor + TRACE("parser verbose", "ac["+int2string(i)+"] = ", ac, ""); + // "e" with all preceding accessors + Expr tmp(wrapAccessors(e, acc, i)); + TRACE("parser verbose", "tmp = ", tmp, ""); + switch(ac.getKind()) { + case ID: // Datatype update + res = VC->listExpr("_DATATYPE_UPDATE", tmp, ac, res); + break; + case RAW_LIST: { + const std::string& kind = ac[0][0].getString(); + if(kind == "_READ") // Array update + res = VC->listExpr("_WRITE", tmp, ac[1], res); + else if(kind == "_RECORD_SELECT") // Record update + res = VC->listExpr("_RECORD_UPDATE", tmp, ac[1], res); + else if(kind == "_TUPLE_SELECT") // Tuple element + res = VC->listExpr("_TUPLE_UPDATE", tmp, ac[1], res); + else + DebugAssert(false, "PL.y: Bad accessor in WITH: "+ac.toString()); + break; + } + default: + DebugAssert(false, "PL.y: Bad accessor in WITH: "+ac.toString()); + } + } + TRACE("parser verbose", "PLprocessUpdate => ", res, " }"); + return res; +} + + +// Process a vector of simultaneous updates (from a single WITH) +static Expr PLprocessUpdates(const CVC4::Expr& e, + const std::vector<CVC4::Expr>& updates, + size_t idx=0) { + // Processed all the updates + if(idx >= updates.size()) return e; + return PLprocessUpdates(PLprocessUpdate(e, updates[idx]), updates, idx+1); +} + + + +} // end of namespace CVC4 + +#define YYLTYPE_IS_TRIVIAL 1 +#define YYMAXDEPTH 10485760 +/* Prefer YYERROR_VERBOSE over %error-verbose to avoid errors in older bison */ +#define YYERROR_VERBOSE 1 +%} + +%union { + std::string *str; + CVC4::Expr *node; + std::vector<CVC4::Expr> *vec; + int kind; +}; + + +%start cmd + +/* strings are for better error messages. + "_TOK" is so macros don't conflict with kind names */ + +%token DISTINCT_TOK "DISTINCT" +%token AND_TOK "AND" +%token ARRAY_TOK "ARRAY" +%token BOOLEAN_TOK "BOOLEAN" +%token DATATYPE_TOK "DATATYPE" +%token ELSE_TOK "ELSE" +%token ELSIF_TOK "ELSIF" +%token END_TOK "END" +%token ENDIF_TOK "ENDIF" +%token EXISTS_TOK "EXISTS" +%token FALSELIT_TOK "FALSE" +%token FORALL_TOK "FORALL" +%token IN_TOK "IN" +%token IF_TOK "IF" +%token LAMBDA_TOK "LAMBDA" +%token SIMULATE_TOK "SIMULATE" +%token LET_TOK "LET" +%token NOT_TOK "NOT" +%token IS_INTEGER_TOK "IS_INTEGER" +%token OF_TOK "OF" +%token OR_TOK "OR" +%token REAL_TOK "REAL" +%token INT_TOK "INT" +%token SUBTYPE_TOK "SUBTYPE" +%token BITVECTOR_TOK "BITVECTOR" +%token THEN_TOK "THEN" +%token TRUELIT_TOK "TRUE" +%token TYPE_TOK "TYPE" +%token WITH_TOK "WITH" +%token XOR_TOK "XOR" +%token TCC_TOK "TCC" +%token PATTERN_TOK "PATTERN" +%token '_' +%token DONE_TOK + +%token DOTDOT_TOK ".." +%token ASSIGN_TOK ":=" +%token NEQ_TOK "/=" +%token IMPLIES_TOK "=>" +%token IFF_TOK "<=>" +%token PLUS_TOK "+" +%token MINUS_TOK "-" +%token MULT_TOK "*" +%token POW_TOK "^" +%token DIV_TOK "/" +%token MOD_TOK "MOD" +%token INTDIV_TOK "DIV" +%token LT_TOK "<" +%token LE_TOK "<=" +%token GT_TOK ">" +%token GE_TOK ">=" +%token FLOOR_TOK "FLOOR" +%token LEFTSHIFT_TOK "<<" +%token RIGHTSHIFT_TOK ">>" +%token BVPLUS_TOK "BVPLUS" +%token BVSUB_TOK "BVSUB" +%token BVUDIV_TOK "BVUDIV" +%token BVSDIV_TOK "BVSDIV" +%token BVUREM_TOK "BVUREM" +%token BVSREM_TOK "BVSREM" +%token BVSMOD_TOK "BVSMOD" +%token BVSHL_TOK "BVSHL" +%token BVASHR_TOK "BVASHR" +%token BVLSHR_TOK "BVLSHR" +%token BVUMINUS_TOK "BVUMINUS" +%token BVMULT_TOK "BVMULT" +%token SQHASH_TOK "[#" +%token HASHSQ_TOK "#]" +%token PARENHASH_TOK "(#" +%token HASHPAREN_TOK "#)" +%token ARROW_TOK "->" +%token BVNEG_TOK "~" +%token BVAND_TOK "&" +%token MID_TOK "|" +%token BVXOR_TOK "BVXOR" +%token BVNAND_TOK "BVNAND" +%token BVNOR_TOK "BVNOR" +%token BVCOMP_TOK "BVCOMP" +%token BVXNOR_TOK "BVXNOR" +%token CONCAT_TOK "@" +%token BVTOINT_TOK "BVTOINT" +%token INTTOBV_TOK "INTTOBV" +%token BOOLEXTRACT_TOK "BOOLEXTRACT" +%token BVLT_TOK "BVLT" +%token BVGT_TOK "BVGT" +%token BVLE_TOK "BVLE" +%token BVGE_TOK "BVGE" +%token SX_TOK "SX" +%token BVZEROEXTEND_TOK "BVZEROEXTEND" +%token BVREPEAT_TOK "BVREPEAT" +%token BVROTL_TOK "BVROTL" +%token BVROTR_TOK "BVROTR" +%token BVSLT_TOK "BVSLT" +%token BVSGT_TOK "BVSGT" +%token BVSLE_TOK "BVSLE" +%token BVSGE_TOK "BVSGE" + + +/* commands given in prefix syntax */ +%token ARITH_VAR_ORDER_TOK "ARITH_VAR_ORDER" +%token ASSERT_TOK "ASSERT" +%token QUERY_TOK "QUERY" +%token CHECKSAT_TOK "CHECKSAT" +%token CONTINUE_TOK "CONTINUE" +%token RESTART_TOK "RESTART" +%token HELP_TOK "HELP" +%token DBG_TOK "DBG" +%token TRACE_TOK "TRACE" +%token UNTRACE_TOK "UNTRACE" +%token OPTION_TOK "OPTION" +%token TRANSFORM_TOK "TRANSFORM" +%token PRINT_TOK "PRINT" +%token PRINT_TYPE_TOK "PRINT_TYPE" +%token CALL_TOK "CALL" +%token ECHO_TOK "ECHO" +%token INCLUDE_TOK "INCLUDE" +%token DUMP_PROOF_TOK "DUMP_PROOF" +%token DUMP_ASSUMPTIONS_TOK "DUMP_ASSUMPTIONS" +%token DUMP_SIG_TOK "DUMP_SIG" +%token DUMP_TCC_TOK "DUMP_TCC" +%token DUMP_TCC_ASSUMPTIONS_TOK "DUMP_TCC_ASSUMPTIONS" +%token DUMP_TCC_PROOF_TOK "DUMP_TCC_PROOF" +%token DUMP_CLOSURE_TOK "DUMP_CLOSURE" +%token DUMP_CLOSURE_PROOF_TOK "DUMP_CLOSURE_PROOF" +%token WHERE_TOK "WHERE" +%token ASSERTIONS_TOK "ASSERTIONS" +%token ASSUMPTIONS_TOK "ASSUMPTIONS" +%token COUNTEREXAMPLE_TOK "COUNTEREXAMPLE" +%token COUNTERMODEL_TOK "COUNTERMODEL" +%token PUSH_TOK "PUSH" +%token POP_TOK "POP" +%token POPTO_TOK "POPTO" +%token PUSH_SCOPE_TOK "PUSH_SCOPE" +%token POP_SCOPE_TOK "POP_SCOPE" +%token POPTO_SCOPE_TOK "POPTO_SCOPE" +%token RESET_TOK "RESET" +%token CONTEXT_TOK "CONTEXT" +%token FORGET_TOK "FORGET" +%token GET_TYPE_TOK "GET_TYPE" +%token CHECK_TYPE_TOK "CHECK_TYPE" +%token GET_CHILD_TOK "GET_CHILD" +%token GET_OP_TOK "GET_OP" +%token SUBSTITUTE_TOK "SUBSTITUTE" + +%nonassoc ASSIGN_TOK IN_TOK +%nonassoc FORALL_TOK EXISTS_TOK +%left IFF_TOK +%right IMPLIES_TOK +%left OR_TOK XOR_TOK +%left AND_TOK +%left NOT_TOK + +%nonassoc '=' NEQ_TOK +%nonassoc LE_TOK LT_TOK GE_TOK GT_TOK FLOOR_TOK +%left PLUS_TOK MINUS_TOK +%left MULT_TOK INTDIV_TOK DIV_TOK MOD_TOK +%left POW_TOK +%left WITH_TOK +%left UMINUS_TOK +%left CONCAT_TOK +%left MID_TOK +%left BVAND_TOK +%left BVXOR_TOK +%left BVNAND_TOK +%left BVNOR_TOK BVCOMP_TOK +%left BVXNOR_TOK +%left BVNEG_TOK +%left BVUMINUS_TOK BVPLUS_TOK BVSUB_TOK +%left BVUDIV_TOK BVSDIV_TOK BVUREM_TOK BVSREM_TOK BVSMOD_TOK BVSHL_TOK BVASHR_TOK BVLSHR_TOK +%left SX_TOK BVZEROEXTEND_TOK BVREPEAT_TOK BVROTL_TOK BVROTR_TOK +%left LEFTSHIFT_TOK RIGHTSHIFT_TOK +%nonassoc BVLT_TOK BVLE_TOK BVGT_TOK BVGE_TOK +%nonassoc BVSLT_TOK BVSLE_TOK BVSGT_TOK BVSGE_TOK +%right IS_INTEGER_TOK +%left ARROW_TOK + +%nonassoc '[' +%nonassoc '{' '.' '(' +%nonassoc BITVECTOR_TOK + +%type <vec> FieldDecls TypeList IDs reverseIDs SingleDataTypes Constructors +%type <vec> LetDecls TypeLetDecls BoundVarDecls ElseRest VarDecls +%type <vec> Exprs AndExpr OrExpr Pattern Patterns +%type <vec> RecordEntries UpdatePosition Updates + +%type <node> Type /* IndexType */ TypeNotIdentifier TypeDef +%type <node> DataType SingleDataType Constructor +%type <node> FunctionType RecordType Real Int BitvectorType +%type <node> FieldDecl TupleType +%type <node> ArrayType ScalarType SubType BasicType SubrangeType +%type <node> LeftBound RightBound +%type <node> Expr Conditional UpdatePositionNode Update Lambda +%type <node> QuantExpr ArrayLiteral RecordLiteral RecordEntry TupleLiteral +%type <node> LetDecl LetExpr LetDeclsNode +%type <node> TypeLetDecl TypeLetExpr TypeLetDeclsNode +%type <node> BoundVarDecl BoundVarDeclNode VarDecl +%type <node> ConstDecl TypeDecl +%type <node> Identifier StringLiteral Numeral Binary Hex + +%type <node> Assert Query Help Dbg Trace Option +%type <node> Transform Print Call Echo DumpCommand +%type <node> Include Where Push Pop PopTo +%type <node> Context Forget Get_Child Get_Op Get_Type Check_Type Substitute +%type <node> other_cmd +%type <node> Arith_Var_Order + +%token <str> ID_TOK STRINGLIT_TOK NUMERAL_TOK HEX_TOK BINARY_TOK + +%% + +cmd : TypeDecl ';' + { + EXPR = *$1; + delete $1; + YYACCEPT; + } + | ConstDecl ';' + { + EXPR = *$1; + delete $1; + YYACCEPT; + } + | other_cmd ';' { + EXPR = *$1; + delete $1; + YYACCEPT; + } + | ';' + { + EXPR = CVC4::Expr(); + YYACCEPT; + } + | DONE_TOK + { + TMP->done = true; + EXPR = CVC4::Expr(); + YYACCEPT; + } + ; + +other_cmd : Assert { $$ = $1; } + | Query { $$ = $1; } + | Dbg { $$ = $1; } + | Trace { $$ = $1; } + | Option { $$ = $1; } + | Help { $$ = $1; } + | Transform { $$ = $1; } + | Print { $$ = $1; } + | Call { $$ = $1; } + | Echo { $$ = $1; } + | Include { $$ = $1; } + | DumpCommand { $$ = $1; } + | Where { $$ = $1; } + | Push { $$ = $1; } + | Pop { $$ = $1; } + | PopTo { $$ = $1; } + | Context { $$ = $1; } + | Substitute { $$ = $1; } + | Get_Child { $$ = $1; } + | Get_Op { $$ = $1; } + | Get_Type { $$ = $1; } + | Check_Type { $$ = $1; } + | Forget { $$ = $1; } + | Arith_Var_Order { $$ = $1; } + ; + +Arith_Var_Order : ARITH_VAR_ORDER_TOK '(' Exprs ')' + { + $$ = new CVC4::Expr(VC->listExpr("_ARITH_VAR_ORDER", *$3)); + delete $3; + } + ; + +Assert : ASSERT_TOK Expr { + + $$ = new CVC4::Expr(VC->listExpr("_ASSERT", *$2)); + delete $2; + } + ; + +Query : QUERY_TOK Expr { + $$ = new CVC4::Expr(VC->listExpr("_QUERY", *$2)); + delete $2; + } + | CHECKSAT_TOK Expr { + $$ = new CVC4::Expr(VC->listExpr("_CHECKSAT", *$2)); + delete $2; + } + | CHECKSAT_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_CHECKSAT"))); + } + | CONTINUE_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_CONTINUE"))); + } + | RESTART_TOK Expr { + $$ = new CVC4::Expr(VC->listExpr("_RESTART", *$2)); + delete $2; + } + ; +Dbg : DBG_TOK StringLiteral { + $$ = new CVC4::Expr(VC->listExpr("_DBG", *$2)); + delete $2; + } + | DBG_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_DBG"))); + } + ; +Trace : TRACE_TOK StringLiteral { + $$ = new CVC4::Expr(VC->listExpr("_TRACE", *$2)); + delete $2; + } + | UNTRACE_TOK StringLiteral { + $$ = new CVC4::Expr(VC->listExpr("_UNTRACE", *$2)); + delete $2; + } + ; +Option : OPTION_TOK StringLiteral Numeral { + $$ = new CVC4::Expr(VC->listExpr("_OPTION", *$2, *$3)); + delete $2; + delete $3; + } + | OPTION_TOK StringLiteral MINUS_TOK Numeral { + CVC4::Rational value= -$4->getRational(); + CVC4::Expr e = CVC4::Expr(VC->ratExpr(value.toString())); + $$ = new CVC4::Expr(VC->listExpr("_OPTION", *$2, e)); + delete $2; + delete $4; + } + | OPTION_TOK StringLiteral StringLiteral { + $$ = new CVC4::Expr(VC->listExpr("_OPTION", *$2, *$3)); + delete $2; + delete $3; + } + ; +Help : HELP_TOK StringLiteral { + $$ = new CVC4::Expr(VC->listExpr("_HELP", *$2)); + delete $2; + } + | HELP_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_HELP"))); + } + ; + +Transform : TRANSFORM_TOK Expr { + $$ = new CVC4::Expr(VC->listExpr("_TRANSFORM", *$2)); + delete $2; + } + ; + +Print : PRINT_TOK Expr { + $$ = new CVC4::Expr(VC->listExpr("_PRINT", *$2)); + delete $2; + } + | PRINT_TYPE_TOK Type { + $$ = new CVC4::Expr(VC->listExpr("_PRINT", *$2)); + delete $2; + } + ; + +Call : CALL_TOK Identifier Expr { + $$ = new CVC4::Expr(VC->listExpr("_CALL", *$2, *$3)); + delete $2; + delete $3; + } + ; + +Echo : ECHO_TOK StringLiteral { + $$ = new CVC4::Expr(VC->listExpr("_ECHO", *$2)); + delete $2; + } + | ECHO_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_ECHO"))); + } + ; + +Include : INCLUDE_TOK StringLiteral { + $$ = new CVC4::Expr(VC->listExpr("_INCLUDE", *$2)); + delete $2; + } + ; + +DumpCommand : DUMP_PROOF_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_DUMP_PROOF"))); + } + | DUMP_ASSUMPTIONS_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_DUMP_ASSUMPTIONS"))); + } + | DUMP_SIG_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_DUMP_SIG"))); + } + | DUMP_TCC_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_DUMP_TCC"))); + } + | DUMP_TCC_ASSUMPTIONS_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_DUMP_TCC_ASSUMPTIONS"))); + } + | DUMP_TCC_PROOF_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_DUMP_TCC_PROOF"))); + } + | DUMP_CLOSURE_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_DUMP_CLOSURE"))); + } + | DUMP_CLOSURE_PROOF_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_DUMP_CLOSURE_PROOF"))); + } + ; + +Where : WHERE_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_WHERE"))); + } + | ASSERTIONS_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_ASSERTIONS"))); + } + | ASSUMPTIONS_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_ASSUMPTIONS"))); + } + | COUNTEREXAMPLE_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_COUNTEREXAMPLE"))); + } + | COUNTERMODEL_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_COUNTERMODEL"))); + } + ; +Push : PUSH_TOK Numeral { + $$ = new CVC4::Expr(VC->listExpr("_PUSH", *$2)); + delete $2; + } + | PUSH_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_PUSH"))); + } + | PUSH_SCOPE_TOK Numeral { + $$ = new CVC4::Expr(VC->listExpr("_PUSH_SCOPE", *$2)); + delete $2; + } + | PUSH_SCOPE_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_PUSH_SCOPE"))); + } + ; +Pop : POP_TOK Numeral { + $$ = new CVC4::Expr(VC->listExpr("_POP", *$2)); + delete $2; + } + | POP_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_POP"))); + } + | POP_SCOPE_TOK Numeral { + $$ = new CVC4::Expr(VC->listExpr("_POP_SCOPE", *$2)); + delete $2; + } + | POP_SCOPE_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_POP_SCOPE"))); + } + ; +PopTo : POPTO_TOK Numeral { + $$ = new CVC4::Expr(VC->listExpr("_POPTO", *$2)); + delete $2; + } + | POPTO_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_POPTO"))); + } + | POPTO_SCOPE_TOK Numeral { + $$ = new CVC4::Expr(VC->listExpr("_POPTO_SCOPE", *$2)); + delete $2; + } + | POPTO_SCOPE_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_POPTO_SCOPE"))); + } + | RESET_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_RESET"))); + } + ; +Context : CONTEXT_TOK StringLiteral { + $$ = new CVC4::Expr(VC->listExpr("_CONTEXT", *$2)); + delete $2; + } + | CONTEXT_TOK { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_CONTEXT"))); + } + ; +Forget : FORGET_TOK Identifier { + $$ = new CVC4::Expr(VC->listExpr("_FORGET", *$2)); + delete $2; + } + ; +Get_Type : GET_TYPE_TOK Expr { + $$ = new CVC4::Expr(VC->listExpr("_GET_TYPE", *$2)); + delete $2; + } + ; +Check_Type : CHECK_TYPE_TOK Expr ':' Type { + $$ = new CVC4::Expr(VC->listExpr("_CHECK_TYPE",*$2, *$4)); + delete $2; + delete $4; + } + ; +Get_Child : GET_CHILD_TOK Expr Numeral { + $$ = new CVC4::Expr(VC->listExpr("_GET_CHILD", *$2, *$3)); + delete $2; + delete $3; + } + ; +Get_Op : GET_OP_TOK Expr { + $$ = new CVC4::Expr(VC->listExpr("_GET_CHILD", *$2)); + delete $2; + } + ; +Substitute : SUBSTITUTE_TOK Identifier ':' Type '=' Expr '[' Identifier ASSIGN_TOK Expr ']' { + std::vector<CVC4::Expr> tmp; + tmp.push_back(*$2); + tmp.push_back(*$4); + tmp.push_back(*$6); + tmp.push_back(*$8); + tmp.push_back(*$10); + $$ = new CVC4::Expr(VC->listExpr("_SUBSTITUTE", tmp)); + delete $2; + delete $4; + delete $6; + delete $8; + delete $10; + } + ; +Identifier : ID_TOK + { + $$ = new CVC4::Expr(VC->idExpr(*$1)); + delete $1; + } + ; +StringLiteral : STRINGLIT_TOK + { + $$ = new CVC4::Expr(VC->stringExpr(*$1)); + delete $1; + } + ; +Numeral : NUMERAL_TOK + { + $$ = new CVC4::Expr(VC->ratExpr((*$1))); + delete $1; + } + ; + +Binary : BINARY_TOK + { + $$ = new CVC4::Expr + (VC->listExpr("_BVCONST", VC->stringExpr(*$1))); + delete $1; + } + ; + + +Hex : HEX_TOK + { + $$ = new CVC4::Expr + (VC->listExpr("_BVCONST", VC->stringExpr(*$1), VC->ratExpr(16))); + delete $1; + } + ; + + +/* Grammar for Types */ + +Type : Identifier { $$ = $1; } + | TypeNotIdentifier { $$ = $1; } + ; + +TypeNotIdentifier: ArrayType { $$ = $1; } + | FunctionType { $$ = $1; } + | BasicType { $$ = $1; } + | SubrangeType { $$ = $1; } + | TupleType { $$ = $1; } + | RecordType { $$ = $1; } + | TypeLetExpr { $$ = $1; } + | BitvectorType {$$ = $1;} + | SubType { $$ = $1; } + | '(' Type ')' { $$ = $2; } + ; + +TypeDef : Type { $$ = $1; } + | ScalarType { $$ = $1; } + ; + +DataType : DATATYPE_TOK SingleDataTypes END_TOK + { + $$ = new CVC4::Expr( + VC->listExpr("_TYPEDEF", + VC->listExpr("_DATATYPE", *$2))); + delete $2; + } + ; + +SingleDataTypes : SingleDataType + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | SingleDataTypes ',' SingleDataType + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + ; + +SingleDataType : Identifier '=' Constructors + { + $$ = new CVC4::Expr(VC->listExpr(*$1, VC->listExpr(*$3))); + delete $1; + delete $3; + } + ; + +Constructors : Constructor + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | Constructors MID_TOK Constructor + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + ; + +Constructor : Identifier + { + $$ = new CVC4::Expr(VC->listExpr(*$1)); + delete $1; + } + | Identifier '(' VarDecls ')' + { + CVC4::Expr tmp = VC->listExpr(*$3); + $$ = new CVC4::Expr(VC->listExpr(*$1, tmp)); + delete $1; delete $3; + } + ; + +VarDecls : VarDecl + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | VarDecls ',' VarDecl + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + ; + +VarDecl : Identifier ':' Type + { + $$ = new CVC4::Expr(VC->listExpr(*$1, *$3)); + delete $1; + delete $3; + } + ; + +FunctionType : '[' Type ARROW_TOK Type ']' + { + // Old style functions + $$ = new CVC4::Expr(VC->listExpr("_OLD_ARROW", *$2, *$4)); + delete $2; delete $4; + } + | Type ARROW_TOK Type + { + std::vector<CVC4::Expr> temp; + temp.push_back(*$1); + temp.push_back(*$3); + + $$ = new CVC4::Expr(VC->listExpr("_ARROW", temp)); + delete $1; delete $3; + } + | '(' TypeList ')' ARROW_TOK Type + { + $2->push_back(*$5); + $$ = new CVC4::Expr(VC->listExpr("_ARROW", *$2)); + delete $2; delete $5; + } + ; + +RecordType : SQHASH_TOK FieldDecls HASHSQ_TOK + { + $$ = new CVC4::Expr(VC->listExpr(*$2)); + delete $2; + } + ; + +FieldDecls : FieldDecl + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(VC->idExpr("_RECORD_TYPE")); + $$->push_back(*$1); + delete $1; + } + | FieldDecls ',' FieldDecl + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + ; + +FieldDecl : Identifier ':' Type + { + $$ = new CVC4::Expr(VC->listExpr(*$1, *$3)); + delete $1; + delete $3; + } + ; + +TupleType : '[' TypeList ']' + { + $$ = new CVC4::Expr(VC->listExpr("_TUPLE_TYPE", *$2)); + delete $2; + } + ; + +TypeList : Type ',' Type + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + $$->push_back(*$3); + delete $1; + delete $3; + } + | TypeList ',' Type + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + ; + +/* IndexType : SubrangeType { $$ = $1; } */ +/* | Real /\* WART: maybe change to INTEGER when we */ +/* get that working? *\/ */ +/* | Int */ +/* { $$ = $1; } */ +/* | Identifier { $$ = $1; } */ +/* ; */ + +ArrayType : ARRAY_TOK Type OF_TOK Type + { + $$ = new CVC4::Expr(VC->listExpr("_ARRAY", *$2, *$4)); + delete $2; + delete $4; + } + ; + +ScalarType : '{' IDs '}' + { + std::vector<CVC4::Expr>::iterator theIter = $2->begin(); + $2->insert(theIter, VC->idExpr("_SCALARTYPE")); + $$ = new CVC4::Expr(VC->listExpr(*$2)); + delete $2; + } + ; + +SubType : SUBTYPE_TOK '(' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_SUBTYPE", *$3)); + delete $3; + } + | SUBTYPE_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_SUBTYPE", *$3, *$5)); + delete $3; + delete $5; + } + ; + +BasicType : BOOLEAN_TOK + { + $$ = new CVC4::Expr(VC->idExpr("_BOOLEAN")); + } + | Real + | Int + ; + +BitvectorType : BITVECTOR_TOK '(' Numeral ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BITVECTOR", *$3)); + delete $3; + } + ; + +Real : REAL_TOK + { + $$ = new CVC4::Expr(VC->idExpr("_REAL")); + } + ; + +Int : INT_TOK + { + $$ = new CVC4::Expr(VC->idExpr("_INT")); + } + ; +SubrangeType : '[' LeftBound DOTDOT_TOK RightBound ']' + { + $$ = new CVC4::Expr(VC->listExpr("_SUBRANGE", *$2, *$4)); + delete $2; + delete $4; + } + ; + +LeftBound : '_' + { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_NEGINF"))); + } + | Numeral { $$ = $1; } + | MINUS_TOK Numeral { + CVC4::Rational value= -$2->getRational(); + $$ = new CVC4::Expr(VC->ratExpr(value.toString())); + delete $2; + } + ; + +RightBound : '_' + { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_POSINF"))); + } + | Numeral { $$ = $1; } + | MINUS_TOK Numeral { + CVC4::Rational value= -$2->getRational(); + $$ = new CVC4::Expr(VC->ratExpr(value.toString())); + delete $2; + } + ; + +/* right recursive to eliminate a conflict. Reverses order? */ +reverseIDs : Identifier + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | Identifier ',' reverseIDs + { + $3->push_back(*$1); + $$ = $3; + delete $1; + } + ; + +IDs : reverseIDs + { + $$ = new std::vector<CVC4::Expr>($1->rbegin(), + $1->rend()); + delete $1; + } + ; + +/* Grammar for exprs */ + +Expr : Identifier { $$ = $1; } + | Numeral { $$ = $1; } + | Binary { $$ = $1; } + | Hex { $$ = $1; } + | Expr '(' Exprs ')' + { + std::vector<CVC4::Expr> tmp; + tmp.push_back(*$1); + tmp.insert(tmp.end(), $3->begin(), $3->end()); + $$ = new CVC4::Expr(VC->listExpr(tmp)); + delete $1; + delete $3; + } + | SIMULATE_TOK '(' Exprs ')' + { + $$ = new CVC4::Expr(VC->listExpr("_SIMULATE", *$3)); + delete $3; + } + | Expr '[' Expr ']' + { + $$ = new CVC4::Expr(VC->listExpr("_READ", *$1, *$3)); + delete $1; + delete $3; + } + | Expr '.' Identifier + { + $$ = new CVC4::Expr(VC->listExpr("_RECORD_SELECT", *$1, *$3)); + delete $1; + delete $3; + } + | Expr '.' Numeral + { + $$ = new CVC4::Expr(VC->listExpr("_TUPLE_SELECT", *$1, *$3)); + delete $1; + delete $3; + } + | Expr WITH_TOK Updates + { + $$ = new CVC4::Expr(CVC4::PLprocessUpdates(*$1, *$3)); + delete $1; + delete $3; + } + | Lambda { $$ = $1; } + | QuantExpr { $$ = $1; } + | LetExpr { $$ = $1; } + + | ArrayLiteral { $$ = $1; } + + | RecordLiteral { $$ = $1; } + | TupleLiteral { $$ = $1; } + | Conditional { $$ = $1; } + + | TRUELIT_TOK + { + $$ = new CVC4::Expr(VC->idExpr("_TRUE_EXPR")); + } + | FALSELIT_TOK + { + $$ = new CVC4::Expr(VC->idExpr("_FALSE_EXPR")); + } + + | MINUS_TOK Expr %prec UMINUS_TOK + { + if ($2->isRational()) + { + CVC4::Rational value= -$2->getRational(); + $$= new CVC4::Expr(VC->ratExpr(value.toString())); + } + else + $$ = new CVC4::Expr(VC->listExpr("_UMINUS", *$2)); + delete $2; + } + | NOT_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_NOT", *$2)); + delete $2; + } + | IS_INTEGER_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_IS_INTEGER", *$2)); + delete $2; + } + | TCC_TOK '(' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_TCC", *$3)); + delete $3; + } + | Expr '=' Expr + { + $$ = new CVC4::Expr(VC->listExpr("_EQ", *$1, *$3)); + delete $1; + delete $3; + } + | Expr NEQ_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_NEQ", *$1, *$3)); + delete $1; + delete $3; + } + | Expr XOR_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_XOR", *$1, *$3)); + delete $1; + delete $3; + } + | OrExpr %prec OR_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_OR", *$1)); + delete $1; + } + | AndExpr %prec AND_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_AND", *$1)); + delete $1; + } + | Expr IMPLIES_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_IMPLIES", *$1, *$3)); + delete $1; + delete $3; + } + | Expr IFF_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_IFF", *$1, *$3)); + delete $1; + delete $3; + } + | Expr PLUS_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_PLUS", *$1, *$3)); + delete $1; + delete $3; + } + | Expr MINUS_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_MINUS", *$1, *$3)); + delete $1; + delete $3; + } + | Expr MULT_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_TRANS_CLOSURE", + *$1, *$4, *$6)); + delete $1; + delete $4; + delete $6; + } + | Expr MULT_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_MULT", *$1, *$3)); + delete $1; + delete $3; + } + | Expr POW_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_POW", *$3, *$1)); + delete $1; + delete $3; + } + | Expr DIV_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_DIVIDE", *$1, *$3)); + delete $1; + delete $3; + } +// | Expr INTDIV_TOK Expr +// { +// $$ = new CVC4::Expr(VC->listExpr("_INTDIV", *$1, *$3)); +// delete $1; +// delete $3; +// } +// | Expr MOD_TOK Expr +// { +// $$ = new CVC4::Expr(VC->listExpr("_MOD", *$1, *$3)); +// delete $1; +// delete $3; +// } + | Expr GT_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_GT", *$1, *$3)); + delete $1; + delete $3; + } + | Expr GE_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_GE", *$1, *$3)); + delete $1; + delete $3; + } + | FLOOR_TOK '(' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_FLOOR", *$3)); + delete $3; + } + | Expr LT_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_LT", *$1, *$3)); + delete $1; + delete $3; + } + | Expr LE_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_LE", *$1, *$3)); + delete $1; + delete $3; + } + | '(' Expr ')' + { + $$ = $2; + } + | BVNEG_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_BVNEG", *$2)); + delete $2; + } + | Expr '[' NUMERAL_TOK ':' NUMERAL_TOK ']' + { + $$ = new CVC4::Expr + (VC->listExpr("_EXTRACT", VC->ratExpr(*$3), + VC->ratExpr(*$5), *$1)); + delete $1; + delete $3; + delete $5; + } + | Expr BVAND_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_BVAND", *$1, *$3)); + delete $1; + delete $3; + } + | Expr MID_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_BVOR", *$1, *$3)); + delete $1; + delete $3; + } + | Expr LEFTSHIFT_TOK NUMERAL_TOK + { + $$ = new CVC4::Expr + (VC->listExpr("_LEFTSHIFT", *$1, VC->ratExpr(*$3))); + delete $1; + delete $3; + } + | Expr RIGHTSHIFT_TOK NUMERAL_TOK + { + $$ = new CVC4::Expr + (VC->listExpr("_RIGHTSHIFT", *$1, VC->ratExpr(*$3))); + delete $1; + delete $3; + } + | BVXOR_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVXOR", *$3, *$5)); + delete $3; + delete $5; + } + | BVNAND_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVNAND", *$3, *$5)); + delete $3; + delete $5; + } + | BVNOR_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVNOR", *$3, *$5)); + delete $3; + delete $5; + } + | BVCOMP_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVCOMP", *$3, *$5)); + delete $3; + delete $5; + } + | BVXNOR_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVXNOR", *$3, *$5)); + delete $3; + delete $5; + } + | SX_TOK '(' Expr ',' NUMERAL_TOK ')' + { + $$ = new CVC4::Expr(VC->listExpr("_SX",*$3,VC->ratExpr(*$5))); + delete $3; + delete $5; + } + | BVZEROEXTEND_TOK '(' Expr ',' NUMERAL_TOK ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVZEROEXTEND",VC->ratExpr(*$5),*$3)); + delete $3; + delete $5; + } + | BVREPEAT_TOK '(' Expr ',' NUMERAL_TOK ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVREPEAT",VC->ratExpr(*$5),*$3)); + delete $3; + delete $5; + } + | BVROTL_TOK '(' Expr ',' NUMERAL_TOK ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVROTL",VC->ratExpr(*$5),*$3)); + delete $3; + delete $5; + } + | BVROTR_TOK '(' Expr ',' NUMERAL_TOK ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVROTR",VC->ratExpr(*$5),*$3)); + delete $3; + delete $5; + } + | BVLT_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVLT", *$3, *$5)); + delete $3; + delete $5; + } + | BVGT_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVGT", *$3, *$5)); + delete $3; + delete $5; + } + | BVLE_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVLE", *$3, *$5)); + delete $3; + delete $5; + } + | BVGE_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVGE", *$3, *$5)); + delete $3; + delete $5; + } + + | BVSLT_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVSLT", *$3, *$5)); + delete $3; + delete $5; + } + | BVSGT_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVSGT", *$3, *$5)); + delete $3; + delete $5; + } + | BVSLE_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVSLE", *$3, *$5)); + delete $3; + delete $5; + } + | BVSGE_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVSGE", *$3, *$5)); + delete $3; + delete $5; + } + | Expr CONCAT_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_CONCAT", *$1, *$3)); + delete $1; + delete $3; + } + | INTTOBV_TOK '(' Expr ',' NUMERAL_TOK ',' NUMERAL_TOK ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_INTTOBV", *$3, VC->ratExpr(*$5), + VC->ratExpr(*$7))); + delete $3; + delete $5; + delete $7; + } + | BVTOINT_TOK '(' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVTOINT", *$3)); + delete $3; + } + | BOOLEXTRACT_TOK '(' Expr ',' NUMERAL_TOK ')' + { + //FIXME: this function is not to be exposed + //to the user counterexamples containing + //this function can be translated into + //BV-EXTRACT and comparison with 0 or 1 + $$ = new CVC4::Expr(VC->listExpr("_BOOLEXTRACT", *$3, + VC->ratExpr(*$5))); + delete $3; + delete $5; + } + | BVPLUS_TOK '(' NUMERAL_TOK ',' Exprs ')' + { + std::vector<CVC4::Expr> k; + k.push_back(VC->ratExpr(*$3)); + k.insert(k.end(), $5->begin(), $5->end()); + $$ = new CVC4::Expr(VC->listExpr("_BVPLUS", k)); + delete $3; + delete $5; + } + | BVSUB_TOK '(' NUMERAL_TOK ',' Expr ',' Expr ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_BVSUB", VC->ratExpr(*$3), *$5, *$7)); + delete $3; + delete $5; + delete $7; + } + | BVUDIV_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_BVUDIV", *$3, *$5)); + delete $3; + delete $5; + } + | BVSDIV_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_BVSDIV", *$3, *$5)); + delete $3; + delete $5; + } + | BVUREM_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_BVUREM", *$3, *$5)); + delete $3; + delete $5; + } + | BVSREM_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_BVSREM", *$3, *$5)); + delete $3; + delete $5; + } + | BVSMOD_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_BVSMOD", *$3, *$5)); + delete $3; + delete $5; + } + | BVSHL_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_BVSHL", *$3, *$5)); + delete $3; + delete $5; + } + | BVASHR_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_BVASHR", *$3, *$5)); + delete $3; + delete $5; + } + | BVLSHR_TOK '(' Expr ',' Expr ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_BVLSHR", *$3, *$5)); + delete $3; + delete $5; + } + | BVUMINUS_TOK '(' Expr ')' + { + $$ = new CVC4::Expr(VC->listExpr("_BVUMINUS", *$3)); + delete $3; + } + | BVMULT_TOK '(' NUMERAL_TOK ',' Expr ',' Expr ')' + { + $$ = new CVC4::Expr + (VC->listExpr("_BVMULT", VC->ratExpr(*$3), *$5, *$7)); + delete $3; + delete $5; + delete $7; + } + | DISTINCT_TOK '(' Exprs ')' + { + $$ = new CVC4::Expr(VC->listExpr("_DISTINCT", *$3)); + delete $3; + } + ; +AndExpr : AndExpr AND_TOK Expr + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + + | Expr AND_TOK Expr + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + $$->push_back(*$3); + delete $1; + delete $3; + } + ; + + +OrExpr : OrExpr OR_TOK Expr + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + + | Expr OR_TOK Expr + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + $$->push_back(*$3); + delete $1; + delete $3; + } + ; +Conditional : IF_TOK Expr THEN_TOK Expr ElseRest + { + $5->push_back(VC->listExpr(*$2, *$4)); + $5->push_back(VC->idExpr("_COND")); + /* at this point, the list for ElseRest is + in reverse order from what it should be. */ + std::vector<CVC4::Expr> tmp; + tmp.insert(tmp.end(), $5->rbegin(), $5->rend()); + $$ = new CVC4::Expr(VC->listExpr(tmp)); + delete $2; + delete $4; + delete $5; + } + ; + +ElseRest : ELSE_TOK Expr ENDIF_TOK + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(VC->listExpr("_ELSE",*$2)); + delete $2; + } + | ELSIF_TOK Expr THEN_TOK Expr ElseRest + { + /* NOTE that we're getting the list built + up in the reverse order here. We'll fix + things when we produce a Conditional. */ + $5->push_back(VC->listExpr(*$2, *$4)); + $$ = $5; + delete $2; + delete $4; + } + ; + +Exprs : Expr + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | Exprs ',' Expr + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + ; + + +Pattern : PATTERN_TOK '(' Exprs ')' ':' + { + $$ = $3; + } + +Patterns : Pattern + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(VC->listExpr(*$1)); + delete $1; + } + | Patterns Pattern + { + $1->push_back(VC->listExpr(*$2)); + $$ = $1; + delete $2; + } + ; + +Update : UpdatePositionNode ASSIGN_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr(*$1, *$3)); + delete $1; + delete $3; + } + ; + +Updates : Update + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | Updates ',' Update + { + $$->push_back(*$3); + delete $3; + } + ; + +UpdatePositionNode : UpdatePosition + { + $$ = new CVC4::Expr(VC->listExpr(*$1)); + delete $1; + } + ; + +UpdatePosition : '[' Expr ']' + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(VC->listExpr("_READ", *$2)); + delete $2; + } + | Identifier + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | '.' Identifier + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(VC->listExpr("_RECORD_SELECT", *$2)); + delete $2; + } + | '.' Numeral + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(VC->listExpr("_TUPLE_SELECT", *$2)); + delete $2; + } + | UpdatePosition '[' Expr ']' + { + $1->push_back(VC->listExpr("_READ", *$3)); + $$ = $1; + delete $3; + } + | UpdatePosition Identifier + { + $1->push_back(*$2); + $$ = $1; + delete $2; + } + | UpdatePosition '.' Identifier + { + $1->push_back(VC->listExpr("_RECORD_SELECT",*$3)); + $$ = $1; + delete $3; + } + | UpdatePosition '.' Numeral + { + $1->push_back(VC->listExpr("_TUPLE_SELECT", *$3)); + $$ = $1; + delete $3; + } + ; + +Lambda : LAMBDA_TOK '(' BoundVarDecls ')' ':' Expr + %prec ASSIGN_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_LAMBDA", + VC->listExpr(*$3), (*$6))); + delete $3; + delete $6; + } + ; +QuantExpr : FORALL_TOK '(' BoundVarDecls ')' ':' Expr + %prec FORALL_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_FORALL", + VC->listExpr(*$3), *$6)); + delete $3; + delete $6; + } + | FORALL_TOK '(' BoundVarDecls ')' ':' Patterns Expr + %prec FORALL_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_FORALL", + VC->listExpr(*$3), *$7, + VC->listExpr(*$6))); + delete $3; + delete $6; + delete $7; + } + | EXISTS_TOK '(' BoundVarDecls ')' ':' Expr + %prec EXISTS_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_EXISTS", + VC->listExpr(*$3), (*$6))); + delete $3; + delete $6; + } + ; + | EXISTS_TOK '(' BoundVarDecls ')' ':' Patterns Expr + %prec EXISTS_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_EXISTS", + VC->listExpr(*$3), *$7, + VC->listExpr(*$6))); + delete $3; + delete $6; + delete $7; + } + +ArrayLiteral : ARRAY_TOK '(' BoundVarDecl ')' ':' Expr + %prec ASSIGN_TOK + { + $$ = new CVC4::Expr + (VC->listExpr("_ARRAY_LITERAL", *$3, *$6)); + delete $3; + delete $6; + } + ; +RecordLiteral : PARENHASH_TOK RecordEntries HASHPAREN_TOK + { + $2->insert($2->begin(), VC->idExpr("_RECORD")); + $$ = new CVC4::Expr(VC->listExpr(*$2)); + delete $2; + } + ; + +RecordEntries : RecordEntry + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | RecordEntries ',' RecordEntry + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + ; + +RecordEntry : Identifier ASSIGN_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr(*$1, *$3)); + delete $1; + delete $3; + } + ; + +TupleLiteral : '(' Exprs ',' Expr ')' + { + $2->push_back(*$4); + $2->insert($2->begin(),VC->idExpr("_TUPLE")); + $$ = new CVC4::Expr(VC->listExpr(*$2)); + delete $2; + delete $4; + } + ; + +LetDeclsNode : LetDecls + { + $$ = new CVC4::Expr(VC->listExpr(*$1)); + delete $1; + } + ; +LetDecls : LetDecl { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | LetDecls ',' LetDecl + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + ; + +LetDecl : Identifier '=' Expr + { + $$ = new CVC4::Expr(VC->listExpr(*$1,*$3)); + delete $1; + delete $3; + } + | Identifier ':' Type '=' Expr + { + $$ = new CVC4::Expr(VC->listExpr(*$1,*$5)); + delete $1; + delete $3; + delete $5; + } + ; + +LetExpr : LET_TOK LetDeclsNode IN_TOK Expr + { + $$ = new CVC4::Expr(VC->listExpr("_LET", *$2, *$4)); + delete $2; + delete $4; + } + ; + +TypeLetDeclsNode : TypeLetDecls + { + $$ = new CVC4::Expr(VC->listExpr(*$1)); + delete $1; + } + ; +TypeLetDecls : TypeLetDecl { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | TypeLetDecls ',' TypeLetDecl + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + ; + +TypeLetDecl : Identifier '=' Type + { + $$ = new CVC4::Expr(VC->listExpr(*$1, *$3)); + delete $1; + delete $3; + } + | Identifier ':' TYPE_TOK '=' Type + { + $$ = new CVC4::Expr(VC->listExpr(*$1,*$5)); + delete $1; + delete $5; + } + ; + +TypeLetExpr : LET_TOK TypeLetDeclsNode IN_TOK Type + { + $$ = new CVC4::Expr(VC->listExpr("_LET", *$2, *$4)); + delete $2; + delete $4; + } + ; + +BoundVarDecl : IDs ':' Type + { + $1->push_back(*$3); + delete $3; + $$ = new CVC4::Expr(VC->listExpr(*$1)); + delete $1; + + } + ; + +BoundVarDecls : BoundVarDecl + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | BoundVarDecls ',' BoundVarDecl + { + $1->push_back(*$3); + $$ = $1; + delete $3; + } + ; + +BoundVarDeclNode: BoundVarDecls + { + $$ = new CVC4::Expr(VC->listExpr(*$1)); + delete $1; + } + ; + +ConstDecl : Identifier ':' Type '=' Expr + { + $$ = new CVC4::Expr(VC->listExpr("_CONST", + *$1, *$3, *$5)); + delete $1; + delete $3; + delete $5; + } + | Identifier ':' Type + { + $$ =new CVC4::Expr + (VC->listExpr("_CONST", VC->listExpr(*$1), *$3)); + delete $1; + delete $3; + } + | Identifier '(' BoundVarDeclNode ')' ':' Type '=' Expr + { + std::vector<CVC4::Expr> tmp; + tmp.push_back(VC->idExpr("_DEFUN")); + tmp.push_back(*$1); + tmp.push_back(*$3); + tmp.push_back(*$6); + tmp.push_back(*$8); + $$ = new CVC4::Expr(VC->listExpr(tmp)); + delete $1; + delete $3; + delete $6; + delete $8; + } + | Identifier '(' BoundVarDeclNode ')' ':' Type + { + std::vector<CVC4::Expr> tmp; + tmp.push_back(VC->idExpr("_DEFUN")); + tmp.push_back(*$1); + tmp.push_back(*$3); + tmp.push_back(*$6); + $$ = new CVC4::Expr(VC->listExpr(tmp)); + delete $1; + delete $3; + delete $6; + } + | Identifier ',' IDs ':' Type + { + $3->insert($3->begin(), *$1); + $$ = new CVC4::Expr(VC->listExpr("_CONST", VC->listExpr(*$3), *$5)); + delete $1; + delete $3; + delete $5; + } + ; + +TypeDecl : DataType { $$ = $1; } + | Identifier ':' TYPE_TOK '=' TypeDef + { + $$ = new CVC4::Expr(VC->listExpr("_TYPEDEF", *$1, *$5)); + delete $1; + delete $5; + } + | Identifier ':' TYPE_TOK + { + $$ =new CVC4::Expr(VC->listExpr("_TYPE", *$1)); + delete $1; + } + | Identifier ',' IDs ':' TYPE_TOK + { + std::vector<CVC4::Expr> tmp; + tmp.push_back(*$1); + tmp.insert(tmp.end(), $3->begin(), $3->end()); + $$ = new CVC4::Expr(VC->listExpr("_TYPE", tmp)); + delete $1; + delete $3; + } + ; +%% diff --git a/src/parser/pl_scanner.lpp b/src/parser/pl_scanner.lpp new file mode 100644 index 000000000..d203a1e9a --- /dev/null +++ b/src/parser/pl_scanner.lpp @@ -0,0 +1,352 @@ +%{ +/*****************************************************************************/ +/*! + * \file PL.lex + * + * Author: Sergey Berezin + * + * Created: Feb 06 03:00:43 GMT 2003 + * + * <hr> + * + * 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. + * + * <hr> + * + */ +/*****************************************************************************/ + +#include <iostream> +#include "parser_temp.h" +#include "expr_manager.h" /* for the benefit of parsePL_defs.h */ +#include "parsePL_defs.h" +#include "debug.h" + +namespace CVC4 { + extern ParserTemp* parserTemp; +} + +/* prefixing hack from gdb (via automake docs) */ +#define yymaxdepth PL_maxdepth +#define yyparse PL_parse +#define yylex PL_lex +#define yyerror PL_error +#define yylval PL_lval +#define yychar PL_char +#define yydebug PL_debug +#define yypact PL_pact +#define yyr1 PL_r1 +#define yyr2 PL_r2 +#define yydef PL_def +#define yychk PL_chk +#define yypgo PL_pgo +#define yyact PL_act +#define yyexca PL_exca +#define yyerrflag PL_errflag +#define yynerrs PL_nerrs +#define yyps PL_ps +#define yypv PL_pv +#define yys PL_s +#define yy_yys PL_yys +#define yystate PL_state +#define yytmp PL_tmp +#define yyv PL_v +#define yy_yyv PL_yyv +#define yyval PL_val +#define yylloc PL_lloc +#define yyreds PL_reds +#define yytoks PL_toks +#define yylhs PL_yylhs +#define yylen PL_yylen +#define yydefred PL_yydefred +#define yydgoto PL_yydgoto +#define yysindex PL_yysindex +#define yyrindex PL_yyrindex +#define yygindex PL_yygindex +#define yytable PL_yytable +#define yycheck PL_yycheck +#define yyname PL_yyname +#define yyrule PL_yyrule + +extern int PL_inputLine; +extern char *PLtext; + +extern int PLerror (const char *msg); + +static int PLinput(std::istream& is, char* buf, int size) { + int res; + if(is) { + // If interactive, read line by line; otherwise read as much as we + // can gobble + if(CVC4::parserTemp->interactive) { + // Print the current prompt + std::cout << CVC4::parserTemp->getPrompt() << std::flush; + // Set the prompt to "middle of the command" one + CVC4::parserTemp->setPrompt2(); + // Read the line + is.getline(buf, size-1); + } else // Set the terminator char to 0 + is.getline(buf, size-1, 0); + // If failbit is set, but eof is not, it means the line simply + // didn't fit; so we clear the state and keep on reading. + bool partialStr = is.fail() && !is.eof(); + if(partialStr) + is.clear(); + + for(res = 0; res<size && buf[res] != 0; res++); + if(res == size) PLerror("Lexer bug: overfilled the buffer"); + if(!partialStr) { // Insert \n into the buffer + buf[res++] = '\n'; + buf[res] = '\0'; + } + } else { + res = YY_NULL; + } + return res; +} + +// Redefine the input buffer function to read from an istream +#define YY_INPUT(buf,result,max_size) \ + result = PLinput(*CVC4::parserTemp->is, buf, max_size); + +int PL_bufSize() { return YY_BUF_SIZE; } +YY_BUFFER_STATE PL_buf_state() { return YY_CURRENT_BUFFER; } + +/* some wrappers for methods that need to refer to a struct. + These are used by CVC4::Parser. */ +void *PL_createBuffer(int sz) { + return (void *)PL_create_buffer(NULL, sz); +} +void PL_deleteBuffer(void *buf_state) { + PL_delete_buffer((struct yy_buffer_state *)buf_state); +} +void PL_switchToBuffer(void *buf_state) { + PL_switch_to_buffer((struct yy_buffer_state *)buf_state); +} +void *PL_bufState() { + return (void *)PL_buf_state(); +} + +void PL_setInteractive(bool is_interactive) { + yy_set_interactive(is_interactive); +} + +// File-static (local to this file) variables and functions +static std::string _string_lit; + + static char escapeChar(char c) { + switch(c) { + case 'n': return '\n'; + case 't': return '\t'; + default: return c; + } + } + +// for now, we don't have subranges. +// +// ".." { return DOTDOT_TOK; } +/*OPCHAR (['!#?\_$&\|\\@])*/ + +%} + +%option interactive +%option noyywrap +%option nounput +%option noreject +%option noyymore +%option yylineno + +%x COMMENT +%x STRING_LITERAL + +LETTER ([a-zA-Z]) +HEX ([0-9a-fA-F]) +BITS ([0-1]) +DIGIT ([0-9]) +OPCHAR (['?\_$~]) +ANYTHING ({LETTER}|{DIGIT}|{OPCHAR}) + +%% + +[\n] { CVC4::parserTemp->lineNum++; } + +[ \t\r\f] { /* skip whitespace */ } + +0bin{BITS}+ {PLlval.str = new std::string(PLtext+4);return BINARY_TOK; + } +0hex{HEX}+ {PLlval.str = new std::string(PLtext+4);return HEX_TOK; + } +{DIGIT}+ {PLlval.str = new std::string(PLtext);return NUMERAL_TOK; + } + +"%" { BEGIN COMMENT; } +<COMMENT>"\n" { BEGIN INITIAL; /* return to normal mode */ + CVC4::parserTemp->lineNum++; } +<COMMENT>. { /* stay in comment mode */ } + +<INITIAL>"\"" { BEGIN STRING_LITERAL; + _string_lit.erase(_string_lit.begin(), + _string_lit.end()); } +<STRING_LITERAL>"\\". { /* escape characters (like \n or \") */ + _string_lit.insert(_string_lit.end(), + escapeChar(PLtext[1])); } +<STRING_LITERAL>"\"" { BEGIN INITIAL; /* return to normal mode */ + PLlval.str = new std::string(_string_lit); + return STRINGLIT_TOK; } +<STRING_LITERAL>. { _string_lit.insert(_string_lit.end(),*PLtext); } + +[()[\]{},.;:'!#?_=] { return PLtext[0]; } + +".." { return DOTDOT_TOK; } +":=" { return ASSIGN_TOK; } +"/=" { return NEQ_TOK; } +"=>" { return IMPLIES_TOK; } +"<=>" { return IFF_TOK; } +"+" { return PLUS_TOK; } +"-" { return MINUS_TOK; } +"*" { return MULT_TOK; } +"^" { return POW_TOK; } +"/" { return DIV_TOK; } +"MOD" { return MOD_TOK; } +"DIV" { return INTDIV_TOK; } +"<" { return LT_TOK; } +"<=" { return LE_TOK; } +">" { return GT_TOK; } +">=" { return GE_TOK; } +"FLOOR" { return FLOOR_TOK; } + +"[#" { return SQHASH_TOK; } +"#]" { return HASHSQ_TOK; } +"(#" { return PARENHASH_TOK; } +"#)" { return HASHPAREN_TOK; } +"->" { return ARROW_TOK; } +"ARROW" { return ARROW_TOK; } +"@" { return CONCAT_TOK;} +"~" { return BVNEG_TOK;} +"&" { return BVAND_TOK;} +"|" { return MID_TOK;} +"BVXOR" { return BVXOR_TOK;} +"BVNAND" { return BVNAND_TOK;} +"BVNOR" { return BVNOR_TOK;} +"BVCOMP" { return BVCOMP_TOK;} +"BVXNOR" { return BVXNOR_TOK;} +"<<" { return LEFTSHIFT_TOK;} +">>" { return RIGHTSHIFT_TOK;} +"BVSLT" { return BVSLT_TOK;} +"BVSGT" { return BVSGT_TOK;} +"BVSLE" { return BVSLE_TOK;} +"BVSGE" { return BVSGE_TOK;} +"SX" { return SX_TOK;} +"BVZEROEXTEND" { return BVZEROEXTEND_TOK;} +"BVREPEAT" { return BVREPEAT_TOK;} +"BVROTL" { return BVROTL_TOK;} +"BVROTR" { return BVROTR_TOK;} +"BVLT" { return BVLT_TOK;} +"BVGT" { return BVGT_TOK;} +"BVLE" { return BVLE_TOK;} +"BVGE" { return BVGE_TOK;} + +"DISTINCT" { return DISTINCT_TOK; } +"BVTOINT" { return BVTOINT_TOK;} +"INTTOBV" { return INTTOBV_TOK;} +"BOOLEXTRACT" { return BOOLEXTRACT_TOK;} +"BVPLUS" { return BVPLUS_TOK;} +"BVUDIV" { return BVUDIV_TOK;} +"BVSDIV" { return BVSDIV_TOK;} +"BVUREM" { return BVUREM_TOK;} +"BVSREM" { return BVSREM_TOK;} +"BVSMOD" { return BVSMOD_TOK;} +"BVSHL" { return BVSHL_TOK;} +"BVASHR" { return BVASHR_TOK;} +"BVLSHR" { return BVLSHR_TOK;} +"BVSUB" { return BVSUB_TOK;} +"BVUMINUS" { return BVUMINUS_TOK;} +"BVMULT" { return BVMULT_TOK;} +"AND" { return AND_TOK; } +"ARRAY" { return ARRAY_TOK; } +"BOOLEAN" { return BOOLEAN_TOK; } +"DATATYPE" { return DATATYPE_TOK; } +"ELSE" { return ELSE_TOK; } +"ELSIF" { return ELSIF_TOK; } +"END" { return END_TOK; } +"ENDIF" { return ENDIF_TOK; } +"EXISTS" { return EXISTS_TOK; } +"FALSE" { return FALSELIT_TOK; } +"FORALL" { return FORALL_TOK; } +"IF" { return IF_TOK; } +"IN" { return IN_TOK; } +"LAMBDA" { return LAMBDA_TOK; } +"SIMULATE" { return SIMULATE_TOK; } +"LET" { return LET_TOK; } +"NOT" { return NOT_TOK; } +"IS_INTEGER" { return IS_INTEGER_TOK; } +"OF" { return OF_TOK; } +"OR" { return OR_TOK; } +"REAL" { return REAL_TOK; } +"INT" { return INT_TOK;} +"SUBTYPE" { return SUBTYPE_TOK;} +"BITVECTOR" { return BITVECTOR_TOK;} + +"THEN" { return THEN_TOK; } +"TRUE" { return TRUELIT_TOK; } +"TYPE" { return TYPE_TOK; } +"WITH" { return WITH_TOK; } +"XOR" { return XOR_TOK; } +"TCC" { return TCC_TOK; } +"PATTERN" { return PATTERN_TOK; } + +"ARITH_VAR_ORDER" { return ARITH_VAR_ORDER_TOK; } +"ASSERT" { return ASSERT_TOK; } +"QUERY" { return QUERY_TOK; } +"CHECKSAT" { return CHECKSAT_TOK; } +"CONTINUE" { return CONTINUE_TOK; } +"RESTART" { return RESTART_TOK; } +"DBG" { return DBG_TOK; } +"TRACE" { return TRACE_TOK; } +"UNTRACE" { return UNTRACE_TOK; } +"OPTION" { return OPTION_TOK; } +"HELP" { return HELP_TOK; } +"TRANSFORM" { return TRANSFORM_TOK; } +"PRINT" { return PRINT_TOK; } +"PRINT_TYPE" { return PRINT_TYPE_TOK; } +"CALL" { return CALL_TOK; } +"ECHO" { return ECHO_TOK; } +"INCLUDE" { return INCLUDE_TOK; } +"DUMP_ASSUMPTIONS" { return DUMP_ASSUMPTIONS_TOK; } +"DUMP_PROOF" { return DUMP_PROOF_TOK; } +"DUMP_SIG" { return DUMP_SIG_TOK; } +"DUMP_TCC" { return DUMP_TCC_TOK; } +"DUMP_TCC_ASSUMPTIONS" { return DUMP_TCC_ASSUMPTIONS_TOK; } +"DUMP_TCC_PROOF" { return DUMP_TCC_PROOF_TOK; } +"DUMP_CLOSURE" { return DUMP_CLOSURE_TOK; } +"DUMP_CLOSURE_PROOF" { return DUMP_CLOSURE_PROOF_TOK; } +"WHERE" { return WHERE_TOK; } +"ASSERTIONS" { return ASSERTIONS_TOK; } +"ASSUMPTIONS" { return ASSUMPTIONS_TOK; } +"COUNTEREXAMPLE" { return COUNTEREXAMPLE_TOK; } +"COUNTERMODEL" { return COUNTERMODEL_TOK; } +"PUSH" { return PUSH_TOK; } +"POP" { return POP_TOK; } +"POPTO" { return POPTO_TOK; } +"PUSH_SCOPE" { return PUSH_SCOPE_TOK; } +"POP_SCOPE" { return POP_SCOPE_TOK; } +"POPTO_SCOPE" { return POPTO_SCOPE_TOK; } +"RESET" { return RESET_TOK; } +"CONTEXT" { return CONTEXT_TOK; } +"FORGET" { return FORGET_TOK; } +"GET_TYPE" { return GET_TYPE_TOK; } +"CHECK_TYPE" { return CHECK_TYPE_TOK; } +"GET_CHILD" { return GET_CHILD_TOK; } +"GET_OP" { return GET_OP_TOK; } +"SUBSTITUTE" { return SUBSTITUTE_TOK; } + +(({LETTER})|(_)({ANYTHING}))({ANYTHING})* { PLlval.str = new std::string(PLtext); return ID_TOK; } + +<<EOF>> { return DONE_TOK; } + +. { PLerror("Illegal input character."); } +%% + diff --git a/src/parser/smtlib.ypp b/src/parser/smtlib.ypp new file mode 100644 index 000000000..1bc22675a --- /dev/null +++ b/src/parser/smtlib.ypp @@ -0,0 +1,1553 @@ +%{ +/*****************************************************************************/ +/*! + * \file smtlib.y + * + * Author: Clark Barrett + * + * Created: Apr 30 2005 + * + * <hr> + * + * 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. + * + * <hr> + * + */ +/*****************************************************************************/ +/* + This file contains the bison code for the parser that reads in CVC + commands in SMT-LIB language. +*/ + +#include "vc.h" +#include "parser_exception.h" +#include "parser_temp.h" + +// Exported shared data +namespace CVC4 { + extern ParserTemp* parserTemp; +} +// Define shortcuts for various things +#define TMP CVC4::parserTemp +#define EXPR CVC4::parserTemp->expr +#define VC (CVC4::parserTemp->vc) +#define ARRAYSENABLED (CVC4::parserTemp->arrFlag) +#define BVENABLED (CVC4::parserTemp->bvFlag) +#define BVSIZE (CVC4::parserTemp->bvSize) +#define RAT(args) CVC4::newRational args +#define QUERYPARSED CVC4::parserTemp->queryParsed + +// Suppress the bogus warning suppression in bison (it generates +// compile error) +#undef __GNUC_MINOR__ + +/* stuff that lives in smtlib.lex */ +extern int smtliblex(void); + +int smtliberror(const char *s) +{ + std::ostringstream ss; + ss << CVC4::parserTemp->fileName << ":" << CVC4::parserTemp->lineNum + << ": " << s; + return CVC4::parserTemp->error(ss.str()); +} + + + +#define YYLTYPE_IS_TRIVIAL 1 +#define YYMAXDEPTH 10485760 + +%} + +%union { + std::string *str; + std::vector<std::string> *strvec; + CVC4::Expr *node; + std::vector<CVC4::Expr> *vec; + std::pair<std::vector<CVC4::Expr>, std::vector<std::string> > *pat_ann; +}; + + +%start cmd + +/* strings are for better error messages. + "_TOK" is so macros don't conflict with kind names */ + +%type <vec> bench_attributes sort_symbs fun_symb_decls pred_symb_decls +%type <vec> an_exprs an_formulas quant_vars an_terms fun_symb fun_pred_symb +%type <node> pattern +%type <node> benchmark bench_name bench_attribute +%type <node> status fun_symb_decl fun_sig pred_symb_decl pred_sig +%type <node> an_expr an_formula quant_var an_atom prop_atom +%type <node> an_term basic_term sort_symb pred_symb +%type <node> var fvar +%type <str> logic_name quant_symb connective user_value attribute annotation +%type <strvec> annotations +%type <pat_ann> patterns_annotations + +%token <str> NUMERAL_TOK +%token <str> SYM_TOK +%token <str> STRING_TOK +%token <str> AR_SYMB +%token <str> USER_VAL_TOK +%token TRUE_TOK +%token FALSE_TOK +%token ITE_TOK +%token NOT_TOK +%token IMPLIES_TOK +%token IF_THEN_ELSE_TOK +%token AND_TOK +%token OR_TOK +%token XOR_TOK +%token IFF_TOK +%token EXISTS_TOK +%token FORALL_TOK +%token LET_TOK +%token FLET_TOK +%token NOTES_TOK +%token CVC_COMMAND_TOK +%token LOGIC_TOK +%token COLON_TOK +%token LBRACKET_TOK +%token RBRACKET_TOK +%token LCURBRACK_TOK +%token RCURBRACK_TOK +%token LPAREN_TOK +%token RPAREN_TOK +%token SAT_TOK +%token UNSAT_TOK +%token UNKNOWN_TOK +%token ASSUMPTION_TOK +%token FORMULA_TOK +%token STATUS_TOK +%token BENCHMARK_TOK +%token EXTRASORTS_TOK +%token EXTRAFUNS_TOK +%token EXTRAPREDS_TOK +%token DOLLAR_TOK +%token QUESTION_TOK +%token DISTINCT_TOK +%token EOF_TOK +%token PAT_TOK +%% + +cmd: + benchmark + { + EXPR = *$1; + delete $1; + YYACCEPT; + } +; + +benchmark: + LPAREN_TOK BENCHMARK_TOK bench_name bench_attributes RPAREN_TOK + { + if (!QUERYPARSED) + $4->push_back(CVC4::Expr(VC->listExpr("_CHECKSAT", CVC4::Expr(VC->idExpr("_TRUE_EXPR"))))); + $$ = new CVC4::Expr(VC->listExpr("_SEQ",*$4)); + delete $4; + } + | EOF_TOK + { + TMP->done = true; + $$ = new CVC4::Expr(); + } +; + +bench_name: + SYM_TOK + { + $$ = NULL; + delete $1; + } +; + +bench_attributes: + bench_attribute + { + $$ = new std::vector<CVC4::Expr>; + if ($1) { + $$->push_back(*$1); + delete $1; + } + } + | bench_attributes bench_attribute + { + $$ = $1; + if ($2) { + $$->push_back(*$2); + delete $2; + } + } +; + +bench_attribute: + COLON_TOK ASSUMPTION_TOK an_formula + { + $$ = new CVC4::Expr(VC->listExpr("_ASSERT", *$3)); + delete $3; + } + | COLON_TOK FORMULA_TOK an_formula + { + $$ = new CVC4::Expr(VC->listExpr("_CHECKSAT", *$3)); + QUERYPARSED = true; + delete $3; + } + | COLON_TOK STATUS_TOK status + { + $$ = NULL; + } + | COLON_TOK LOGIC_TOK logic_name + { + ARRAYSENABLED = false; + BVENABLED = false; + CVC4::Expr cmd; + if (*$3 == "QF_UF") { + cmd = CVC4::Expr(VC->listExpr("_TYPE", VC->idExpr("U"))); + } + else if (*$3 == "QF_A" || + *$3 == "QF_AX") { + ARRAYSENABLED = true; + std::vector<CVC4::Expr> tmp; + tmp.push_back(VC->listExpr("_TYPE", VC->idExpr("Index"))); + tmp.push_back(VC->listExpr("_TYPE", VC->idExpr("Element"))); + tmp.push_back(VC->listExpr("_TYPEDEF", VC->idExpr("Array"), + VC->listExpr("_ARRAY", + VC->idExpr("Index"), + VC->idExpr("Element")))); + cmd = CVC4::Expr(VC->listExpr("_SEQ", tmp)); + } + else if (*$3 == "QF_AUFLIA" || + *$3 == "AUFLIA") { + ARRAYSENABLED = true; + std::vector<CVC4::Expr> tmp; + tmp.push_back(VC->listExpr("_TYPEDEF", VC->idExpr("Array"), + VC->listExpr("_ARRAY", + VC->idExpr("_INT"), + VC->idExpr("_INT")))); + cmd = CVC4::Expr(VC->listExpr("_SEQ", tmp)); + } + else if (*$3 == "QF_AUFLIRA" || + *$3 == "AUFLIRA" || + *$3 == "QF_AUFNIRA" || + *$3 == "AUFNIRA") { + ARRAYSENABLED = true; + std::vector<CVC4::Expr> tmp; + tmp.push_back(VC->listExpr("_TYPEDEF", VC->idExpr("Array1"), + VC->listExpr("_ARRAY", + VC->idExpr("_INT"), + VC->idExpr("_REAL")))); + tmp.push_back(VC->listExpr("_TYPEDEF", VC->idExpr("Array2"), + VC->listExpr("_ARRAY", + VC->idExpr("_INT"), + VC->idExpr("Array1")))); + cmd = CVC4::Expr(VC->listExpr("_SEQ", tmp)); + } + else if (*$3 == "QF_AUFBV" || + *$3 == "QF_ABV") { + ARRAYSENABLED = true; + BVENABLED = true; +// $$ = new CVC4::Expr(VC->listExpr("_TYPEDEF", VC->idExpr("Array"), +// VC->listExpr("_ARRAY", +// VC->listExpr("_BITVECTOR", VC->ratExpr(32)), +// VC->listExpr("_BITVECTOR", VC->ratExpr(8))))); + } + else if (*$3 == "QF_BV" || + *$3 == "QF_UFBV") { + BVENABLED = true; + } + // This enables the new arith for QF_LRA, but this results in assertion failures in DEBUG mode +// else if (*$3 == "QF_LRA") { +// cmd = CVC4::Expr(VC->listExpr("_OPTION", VC->stringExpr("arith-new"), VC->ratExpr(1))); +// } + + CVC4::Expr cmd2; + if (*$3 == "AUFLIA" || + *$3 == "AUFLIRA" || + *$3 == "AUFNIRA" || + *$3 == "LRA" || + *$3 == "UFNIA") { + cmd2 = CVC4::Expr(VC->listExpr("_OPTION", VC->stringExpr("quant-complete-inst"), VC->ratExpr(1))); + } +// else if (*$3 == "QF_NIA" || +// *$3 == "QF_UFNRA") { +// cmd2 = CVC4::Expr(VC->listExpr("_OPTION", VC->stringExpr("unknown-check-model"), VC->ratExpr(1))); +// } +// else if (*$3 == "QF_LIA" || +// *$3 == "QF_AUFLIA" || +// *$3 == "QF_AX") { +// cmd2 = CVC4::Expr(VC->listExpr("_OPTION", VC->stringExpr("pp-budget"), VC->ratExpr(5000))); +// } + + if (cmd.isNull()) { + if (cmd2.isNull()) { + $$ = NULL; + } + else $$ = new CVC4::Expr(cmd2); + } + else { + if (!cmd2.isNull()) { + cmd = CVC4::Expr(VC->listExpr("_SEQ", cmd, cmd2)); + } + $$ = new CVC4::Expr(cmd); + } + delete $3; + } + | COLON_TOK EXTRASORTS_TOK LPAREN_TOK sort_symbs RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_TYPE", *$4)); + delete $4; + } + | COLON_TOK EXTRAFUNS_TOK LPAREN_TOK fun_symb_decls RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_SEQ", *$4)); + delete $4; + } + | COLON_TOK EXTRAPREDS_TOK LPAREN_TOK pred_symb_decls RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_SEQ", *$4)); + delete $4; + } + | COLON_TOK NOTES_TOK STRING_TOK + { + $$ = NULL; + delete $3; + } + | COLON_TOK CVC_COMMAND_TOK STRING_TOK + { + $$ = new CVC4::Expr(VC->listExpr(VC->idExpr("_"+*$3))); + delete $3; + } + | annotation + { + $$ = NULL; + delete $1; + } +; + +logic_name: + SYM_TOK LBRACKET_TOK NUMERAL_TOK RBRACKET_TOK + { + BVSIZE = atoi($3->c_str()); + delete $3; + $$ = $1; + } + | SYM_TOK + { + $$ = $1; + } +; + +status: + SAT_TOK { $$ = NULL; } + | UNSAT_TOK { $$ = NULL; } + | UNKNOWN_TOK { $$ = NULL; } +; + +sort_symbs: + sort_symb + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | sort_symbs sort_symb + { + $1->push_back(*$2); + $$ = $1; + delete $2; + } +; + +fun_symb_decls: + fun_symb_decl + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | + fun_symb_decls fun_symb_decl + { + $1->push_back(*$2); + $$ = $1; + delete $2; + } +; + +fun_symb_decl: + LPAREN_TOK fun_sig annotations RPAREN_TOK + { + $$ = $2; + delete $3; + } + | LPAREN_TOK fun_sig RPAREN_TOK + { + $$ = $2; + } +; + +fun_sig: + fun_symb sort_symbs + { + if ($2->size() == 1) { + $$ = new CVC4::Expr(VC->listExpr("_CONST", VC->listExpr(*$1), (*$2)[0])); + } + else { + CVC4::Expr tmp(VC->listExpr("_ARROW", *$2)); + $$ = new CVC4::Expr(VC->listExpr("_CONST", VC->listExpr(*$1), tmp)); + } + delete $1; + delete $2; + } +; + +pred_symb_decls: + pred_symb_decl + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | + pred_symb_decls pred_symb_decl + { + $1->push_back(*$2); + $$ = $1; + delete $2; + } +; + +pred_symb_decl: + LPAREN_TOK pred_sig annotations RPAREN_TOK + { + $$ = $2; + delete $3; + } + | LPAREN_TOK pred_sig RPAREN_TOK + { + $$ = $2; + } +; + +pred_sig: + pred_symb sort_symbs + { + std::vector<CVC4::Expr> tmp(*$2); + tmp.push_back(VC->idExpr("_BOOLEAN")); + CVC4::Expr tmp2(VC->listExpr("_ARROW", tmp)); + $$ = new CVC4::Expr(VC->listExpr("_CONST", VC->listExpr(*$1), tmp2)); + delete $1; + delete $2; + } + | pred_symb + { + $$ = new CVC4::Expr(VC->listExpr("_CONST", VC->listExpr(*$1), + VC->idExpr("_BOOLEAN"))); + delete $1; + } +; + +an_formulas: + an_formula + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | + an_formulas an_formula + { + $1->push_back(*$2); + $$ = $1; + delete $2; + } +; + +an_formula: + an_atom + { + $$ = $1; + } + | LPAREN_TOK connective an_formulas annotations RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr(*$2, *$3)); + delete $2; + delete $3; + delete $4; + } + | LPAREN_TOK connective an_formulas RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr(*$2, *$3)); + delete $2; + delete $3; + } + | LPAREN_TOK quant_symb quant_vars an_formula patterns_annotations RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr(*$2, VC->listExpr(*$3), *$4, VC->listExpr((*$5).first))); + delete $2; + delete $3; + delete $4; + delete $5; + } + | LPAREN_TOK quant_symb quant_vars an_formula RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr(*$2, VC->listExpr(*$3), *$4)); + delete $2; + delete $3; + delete $4; + } + | LPAREN_TOK LET_TOK LPAREN_TOK var an_term RPAREN_TOK an_formula annotations RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + delete $8; + } + | LPAREN_TOK LET_TOK LPAREN_TOK var an_term RPAREN_TOK an_formula RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + } + | LPAREN_TOK FLET_TOK LPAREN_TOK fvar an_formula RPAREN_TOK an_formula annotations RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + delete $8; + } + | LPAREN_TOK FLET_TOK LPAREN_TOK fvar an_formula RPAREN_TOK an_formula RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + } +; + +patterns_annotations: + pattern + { + $$ = new std::pair<std::vector<CVC4::Expr>, std::vector<std::string> >; + $$->first.push_back(*$1); + delete $1; + } + | annotation + { + $$ = new std::pair<std::vector<CVC4::Expr>, std::vector<std::string> >; + $$->second.push_back(*$1); + delete $1; + } + | patterns_annotations pattern + { + $1->first.push_back(*$2); + $$ = $1; + delete $2; + } + | patterns_annotations annotation + { + $1->second.push_back(*$2); + $$ = $1; + delete $2; + } + +pattern: + PAT_TOK LCURBRACK_TOK an_exprs RCURBRACK_TOK + { + $$ = new CVC4::Expr(VC->listExpr(*$3)); + delete $3; + } + +quant_vars: + quant_var + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | quant_vars quant_var + { + $1->push_back(*$2); + $$ = $1; + delete $2; + } +; + +quant_var: + LPAREN_TOK var sort_symb RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr(*$2, *$3)); + delete $2; + delete $3; + } +; + +quant_symb: + EXISTS_TOK + { + $$ = new std::string("_EXISTS"); + } + | FORALL_TOK + { + $$ = new std::string("_FORALL"); + } +; + +connective: + NOT_TOK + { + $$ = new std::string("_NOT"); + } + | IMPLIES_TOK + { + $$ = new std::string("_IMPLIES"); + } + | IF_THEN_ELSE_TOK + { + $$ = new std::string("_IF"); + } + | AND_TOK + { + $$ = new std::string("_AND"); + } + | OR_TOK + { + $$ = new std::string("_OR"); + } + | XOR_TOK + { + $$ = new std::string("_XOR"); + } + | IFF_TOK + { + $$ = new std::string("_IFF"); + } +; + +an_atom: + prop_atom + { + $$ = $1; + } + | LPAREN_TOK prop_atom annotations RPAREN_TOK + { + $$ = $2; + delete $3; + } + | LPAREN_TOK pred_symb an_terms annotations RPAREN_TOK + { + if ($4->size() == 1 && (*$4)[0] == "transclose" && + $3->size() == 2) { + $$ = new CVC4::Expr(VC->listExpr("_TRANS_CLOSURE", + *$2, (*$3)[0], (*$3)[1])); + } + else { + std::vector<CVC4::Expr> tmp; + tmp.push_back(*$2); + tmp.insert(tmp.end(), $3->begin(), $3->end()); + $$ = new CVC4::Expr(VC->listExpr(tmp)); + } + delete $2; + delete $3; + delete $4; + } + | LPAREN_TOK pred_symb an_terms RPAREN_TOK + { + std::vector<CVC4::Expr> tmp; + tmp.push_back(*$2); + tmp.insert(tmp.end(), $3->begin(), $3->end()); + $$ = new CVC4::Expr(VC->listExpr(tmp)); + delete $2; + delete $3; + } + | LPAREN_TOK DISTINCT_TOK an_terms annotations RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_DISTINCT", *$3)); + +// std::vector<CVC4::Expr> tmp; +// tmp.push_back(*$2); +// tmp.insert(tmp.end(), $3->begin(), $3->end()); +// $$ = new CVC4::Expr(VC->listExpr(tmp)); +// for (unsigned i = 0; i < (*$3).size(); ++i) { +// tmp.push_back(($3)[i]) +// for (unsigned j = i+1; j < (*$3).size(); ++j) { +// tmp.push_back(VC->listExpr("_NEQ", (*$3)[i], (*$3)[j])); +// } +// } +// $$ = new CVC4::Expr(VC->listExpr("_AND", tmp)); + delete $3; + delete $4; + } + | LPAREN_TOK DISTINCT_TOK an_terms RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_DISTINCT", *$3)); +// std::vector<CVC4::Expr> tmp; +// for (unsigned i = 0; i < (*$3).size(); ++i) { +// for (unsigned j = i+1; j < (*$3).size(); ++j) { +// tmp.push_back(VC->listExpr("_NEQ", (*$3)[i], (*$3)[j])); +// } +// } +// $$ = new CVC4::Expr(VC->listExpr("_AND", tmp)); + delete $3; + } +; + +prop_atom: + TRUE_TOK + { + $$ = new CVC4::Expr(VC->idExpr("_TRUE_EXPR")); + } + | FALSE_TOK + { + $$ = new CVC4::Expr(VC->idExpr("_FALSE_EXPR")); + } + | fvar + { + $$ = $1; + } + | pred_symb + { + $$ = $1; + } +; + +an_terms: + an_term + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | an_terms an_term + { + $1->push_back(*$2); + $$ = $1; + delete $2; + } +; + +an_term: + basic_term + { + $$ = $1; + } + | LPAREN_TOK basic_term annotations RPAREN_TOK + { + $$ = $2; + delete $3; + } + | LPAREN_TOK fun_symb an_terms annotations RPAREN_TOK + { + $2->insert($2->end(), $3->begin(), $3->end()); + $$ = new CVC4::Expr(VC->listExpr(*$2)); + delete $2; + delete $3; + delete $4; + } + | LPAREN_TOK fun_symb an_terms RPAREN_TOK + { + $2->insert($2->end(), $3->begin(), $3->end()); + $$ = new CVC4::Expr(VC->listExpr(*$2)); + delete $2; + delete $3; + } + | LPAREN_TOK ITE_TOK an_formula an_term an_term annotations RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_IF", *$3, *$4, *$5)); + delete $3; + delete $4; + delete $5; + delete $6; + } + | LPAREN_TOK ITE_TOK an_formula an_term an_term RPAREN_TOK + { + $$ = new CVC4::Expr(VC->listExpr("_IF", *$3, *$4, *$5)); + delete $3; + delete $4; + delete $5; + } + | LPAREN_TOK LET_TOK LPAREN_TOK var an_term RPAREN_TOK an_term annotations RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + delete $8; + } + | LPAREN_TOK LET_TOK LPAREN_TOK var an_term RPAREN_TOK an_term RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + } + | LPAREN_TOK FLET_TOK LPAREN_TOK fvar an_formula RPAREN_TOK an_term annotations RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + delete $8; + } + | LPAREN_TOK FLET_TOK LPAREN_TOK fvar an_formula RPAREN_TOK an_term RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + } +; + +basic_term: + var + { + $$ = $1; + } + | fun_symb + { + if ($1->size() == 1) { + $$ = new CVC4::Expr(((*$1)[0])); + } + else { + $$ = new CVC4::Expr(VC->listExpr(*$1)); + } + delete $1; + } +; + +annotations: + annotation + { + $$ = new std::vector<std::string>; + $$->push_back(*$1); + delete $1; + } + | annotations annotation + { + $1->push_back(*$2); + $$ = $1; + delete $2; + } + ; + + +annotation: + attribute + { $$ = $1; } + | attribute user_value + { $$ = $1; } +; + +user_value: + USER_VAL_TOK + { + $$ = NULL; + delete $1; + } +; + + +sort_symb: + SYM_TOK LBRACKET_TOK NUMERAL_TOK RBRACKET_TOK + { + if (BVENABLED && *$1 == "BitVec") { + $$ = new CVC4::Expr(VC->listExpr("_BITVECTOR", VC->ratExpr(*$3))); + } + else { + $$ = new CVC4::Expr(VC->listExpr(*$1, VC->ratExpr(*$3))); + } + delete $1; + delete $3; + } + | SYM_TOK LBRACKET_TOK NUMERAL_TOK COLON_TOK NUMERAL_TOK RBRACKET_TOK + { + if (BVENABLED && ARRAYSENABLED && *$1 == "Array") { + $$ = new CVC4::Expr(VC->listExpr("_ARRAY", + VC->listExpr("_BITVECTOR", VC->ratExpr(*$3)), + VC->listExpr("_BITVECTOR", VC->ratExpr(*$5)))); + } + else { + $$ = new CVC4::Expr(VC->listExpr(*$1, VC->ratExpr(*$3), VC->ratExpr(*$5))); + } + delete $1; + delete $3; + delete $5; + } + | SYM_TOK + { + if (*$1 == "Real") { + $$ = new CVC4::Expr(VC->idExpr("_REAL")); + } else if (*$1 == "Int") { + $$ = new CVC4::Expr(VC->idExpr("_INT")); + } else { + $$ = new CVC4::Expr(VC->idExpr(*$1)); + } + delete $1; + } +; + +pred_symb: + SYM_TOK + { + if (BVENABLED && (*$1 == "bvlt" || *$1 == "bvult")) { + $$ = new CVC4::Expr(VC->idExpr("_BVLT")); + } + else if (BVENABLED && (*$1 == "bvleq" || *$1 == "bvule")) { + $$ = new CVC4::Expr(VC->idExpr("_BVLE")); + } + else if (BVENABLED && (*$1 == "bvgeq" || *$1 == "bvuge")) { + $$ = new CVC4::Expr(VC->idExpr("_BVGE")); + } + else if (BVENABLED && (*$1 == "bvgt" || *$1 == "bvugt")) { + $$ = new CVC4::Expr(VC->idExpr("_BVGT")); + } + else if (BVENABLED && *$1 == "bvslt") { + $$ = new CVC4::Expr(VC->idExpr("_BVSLT")); + } + else if (BVENABLED && (*$1 == "bvsleq" || *$1 == "bvsle")) { + $$ = new CVC4::Expr(VC->idExpr("_BVSLE")); + } + else if (BVENABLED && (*$1 == "bvsgeq" || *$1 == "bvsge")) { + $$ = new CVC4::Expr(VC->idExpr("_BVSGE")); + } + else if (BVENABLED && *$1 == "bvsgt") { + $$ = new CVC4::Expr(VC->idExpr("_BVSGT")); + } + else { + $$ = new CVC4::Expr(VC->idExpr(*$1)); + } + delete $1; + } + | AR_SYMB + { + if ($1->length() == 1) { + switch ((*$1)[0]) { + case '=': $$ = new CVC4::Expr(VC->idExpr("_EQ")); break; + case '<': $$ = new CVC4::Expr(VC->idExpr("_LT")); break; + case '>': $$ = new CVC4::Expr(VC->idExpr("_GT")); break; + default: $$ = new CVC4::Expr(VC->idExpr(*$1)); break; + } + } + else { + if (*$1 == "<=") { + $$ = new CVC4::Expr(VC->idExpr("_LE")); + } else if (*$1 == ">=") { + $$ = new CVC4::Expr(VC->idExpr("_GE")); + } + else $$ = new CVC4::Expr(VC->idExpr(*$1)); + } + delete $1; + } +; + +fun_symb: + SYM_TOK LBRACKET_TOK NUMERAL_TOK RBRACKET_TOK + { + $$ = new std::vector<CVC4::Expr>; + if (BVENABLED && *$1 == "repeat") { + $$->push_back(VC->idExpr("_BVREPEAT")); + } + else if (BVENABLED && *$1 == "zero_extend") { + $$->push_back(VC->idExpr("_BVZEROEXTEND")); + } + else if (BVENABLED && *$1 == "sign_extend") { + $$->push_back(VC->idExpr("_SX")); + $$->push_back(VC->idExpr("_smtlib")); + } + else if (BVENABLED && *$1 == "rotate_left") { + $$->push_back(VC->idExpr("_BVROTL")); + } + else if (BVENABLED && *$1 == "rotate_right") { + $$->push_back(VC->idExpr("_BVROTR")); + } + else if (BVENABLED && + $1->size() > 2 && + (*$1)[0] == 'b' && + (*$1)[1] == 'v') { + int i = 2; + while ((*$1)[i] >= '0' && (*$1)[i] <= '9') ++i; + if ((*$1)[i] == '\0') { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr($1->substr(2), 10)); + } + else $$->push_back(VC->idExpr(*$1)); + } + else $$->push_back(VC->idExpr(*$1)); + $$->push_back(VC->ratExpr(*$3)); + delete $1; + delete $3; + } + | SYM_TOK LBRACKET_TOK NUMERAL_TOK COLON_TOK NUMERAL_TOK RBRACKET_TOK + { + $$ = new std::vector<CVC4::Expr>; + if (BVENABLED && *$1 == "extract") { + $$->push_back(VC->idExpr("_EXTRACT")); + } + else $$->push_back(VC->idExpr(*$1)); + $$->push_back(VC->ratExpr(*$3)); + $$->push_back(VC->ratExpr(*$5)); + delete $1; + delete $3; + delete $5; + } + | SYM_TOK + { + $$ = new std::vector<CVC4::Expr>; + if (ARRAYSENABLED && *$1 == "select") { + $$->push_back(VC->idExpr("_READ")); + } + else if (ARRAYSENABLED && *$1 == "store") { + $$->push_back(VC->idExpr("_WRITE")); + } + else if (BVENABLED && *$1 == "bit0") { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr(0)); + $$->push_back(VC->ratExpr(1)); + } + else if (BVENABLED && *$1 == "bit1") { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr(1)); + $$->push_back(VC->ratExpr(1)); + } + else if (BVENABLED && *$1 == "concat") { + $$->push_back(VC->idExpr("_CONCAT")); + } + else if (BVENABLED && *$1 == "bvnot") { + $$->push_back(VC->idExpr("_BVNEG")); + } + else if (BVENABLED && *$1 == "bvand") { + $$->push_back(VC->idExpr("_BVAND")); + } + else if (BVENABLED && *$1 == "bvor") { + $$->push_back(VC->idExpr("_BVOR")); + } + else if (BVENABLED && *$1 == "bvneg") { + $$->push_back(VC->idExpr("_BVUMINUS")); + } + else if (BVENABLED && *$1 == "bvadd") { + $$->push_back(VC->idExpr("_BVPLUS")); + } + else if (BVENABLED && *$1 == "bvmul") { + $$->push_back(VC->idExpr("_BVMULT")); + } + else if (BVENABLED && *$1 == "bvudiv") { + $$->push_back(VC->idExpr("_BVUDIV")); + } + else if (BVENABLED && *$1 == "bvurem") { + $$->push_back(VC->idExpr("_BVUREM")); + } + else if (BVENABLED && *$1 == "bvshl") { + $$->push_back(VC->idExpr("_BVSHL")); + } + else if (BVENABLED && *$1 == "bvlshr") { + $$->push_back(VC->idExpr("_BVLSHR")); + } + + else if (BVENABLED && *$1 == "bvnand") { + $$->push_back(VC->idExpr("_BVNAND")); + } + else if (BVENABLED && *$1 == "bvnor") { + $$->push_back(VC->idExpr("_BVNOR")); + } + else if (BVENABLED && *$1 == "bvxor") { + $$->push_back(VC->idExpr("_BVXOR")); + } + else if (BVENABLED && *$1 == "bvxnor") { + $$->push_back(VC->idExpr("_BVXNOR")); + } + else if (BVENABLED && *$1 == "bvcomp") { + $$->push_back(VC->idExpr("_BVCOMP")); + } + + else if (BVENABLED && *$1 == "bvsub") { + $$->push_back(VC->idExpr("_BVSUB")); + } + else if (BVENABLED && *$1 == "bvsdiv") { + $$->push_back(VC->idExpr("_BVSDIV")); + } + else if (BVENABLED && *$1 == "bvsrem") { + $$->push_back(VC->idExpr("_BVSREM")); + } + else if (BVENABLED && *$1 == "bvsmod") { + $$->push_back(VC->idExpr("_BVSMOD")); + } + else if (BVENABLED && *$1 == "bvashr") { + $$->push_back(VC->idExpr("_BVASHR")); + } + + // For backwards compatibility: + else if (BVENABLED && *$1 == "shift_left0") { + $$->push_back(VC->idExpr("_CONST_WIDTH_LEFTSHIFT")); + } + else if (BVENABLED && *$1 == "shift_right0") { + $$->push_back(VC->idExpr("_RIGHTSHIFT")); + } + else if (BVENABLED && *$1 == "sign_extend") { + $$->push_back(VC->idExpr("_SX")); + $$->push_back(VC->idExpr("_smtlib")); + } + + // Bitvector constants + else if (BVENABLED && + $1->size() > 2 && + (*$1)[0] == 'b' && + (*$1)[1] == 'v') { + bool done = false; + if ((*$1)[2] >= '0' && (*$1)[2] <= '9') { + int i = 3; + while ((*$1)[i] >= '0' && (*$1)[i] <= '9') ++i; + if ((*$1)[i] == '\0') { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr($1->substr(2), 10)); + $$->push_back(VC->ratExpr(32)); + done = true; + } + } + else if ($1->size() > 5) { + std::string s = $1->substr(0,5); + if (s == "bvbin") { + int i = 5; + while ((*$1)[i] >= '0' && (*$1)[i] <= '1') ++i; + if ((*$1)[i] == '\0') { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr($1->substr(5), 2)); + $$->push_back(VC->ratExpr(i-5)); + done = true; + } + } + else if (s == "bvhex") { + int i = 5; + char c = (*$1)[i]; + while ((c >= '0' && c <= '9') || + (c >= 'a' && c <= 'f') || + (c >= 'A' && c <= 'F')) { + ++i; + c =(*$1)[i]; + } + if ((*$1)[i] == '\0') { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr($1->substr(5), 16)); + $$->push_back(VC->ratExpr(i-5)); + done = true; + } + } + } + if (!done) $$->push_back(VC->idExpr(*$1)); + } + else { + $$->push_back(VC->idExpr(*$1)); + } + delete $1; + } + | AR_SYMB + { + $$ = new std::vector<CVC4::Expr>; + if ($1->length() == 1) { + switch ((*$1)[0]) { + case '+': $$->push_back(VC->idExpr("_PLUS")); break; + case '-': $$->push_back(VC->idExpr("_MINUS")); break; + case '*': $$->push_back(VC->idExpr("_MULT")); break; + case '~': $$->push_back(VC->idExpr("_UMINUS")); break; + case '/': $$->push_back(VC->idExpr("_DIVIDE")); break; + // case '=': $$->push_back(VC->idExpr("_EQ")); break; + // case '<': $$->push_back(VC->idExpr("_LT")); break; + // case '>': $$->push_back(VC->idExpr("_GT")); break; + default: $$->push_back(VC->idExpr(*$1)); + } + } + // else { + // if (*$1 == "<=") { + // $$->push_back(VC->idExpr("_LE")); + // } else if (*$1 == ">=") { + // $$->push_back(VC->idExpr("_GE")); + // } + else $$->push_back(VC->idExpr(*$1)); + // } + delete $1; + } + | NUMERAL_TOK + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(VC->ratExpr(*$1)); + delete $1; + } +; + +attribute: + COLON_TOK SYM_TOK + { + $$ = $2; + } +; + +var: + QUESTION_TOK SYM_TOK + { + $$ = new CVC4::Expr(VC->idExpr("_"+*$2)); + delete $2; + } +; + +fvar: + DOLLAR_TOK SYM_TOK + { + $$ = new CVC4::Expr(VC->idExpr("_"+*$2)); + delete $2; + } +; + +an_exprs: + an_expr + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(*$1); + delete $1; + } + | + an_exprs an_expr + { + $1->push_back(*$2); + $$ = $1; + delete $2; + } +; + +an_expr: + var + { + $$ = $1; + } + | fvar + { + $$ = $1; + } + | LPAREN_TOK fun_pred_symb an_terms annotations RPAREN_TOK + { + $2->insert($2->end(), $3->begin(), $3->end()); + $$ = new CVC4::Expr(VC->listExpr(*$2)); + delete $2; + delete $3; + delete $4; + } + | LPAREN_TOK fun_pred_symb an_terms RPAREN_TOK + { + $2->insert($2->end(), $3->begin(), $3->end()); + $$ = new CVC4::Expr(VC->listExpr(*$2)); + delete $2; + delete $3; + } + | LPAREN_TOK LET_TOK LPAREN_TOK var an_term RPAREN_TOK an_expr annotations RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + delete $8; + } + | LPAREN_TOK LET_TOK LPAREN_TOK var an_term RPAREN_TOK an_expr RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + } + | LPAREN_TOK FLET_TOK LPAREN_TOK fvar an_formula RPAREN_TOK an_expr annotations RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + delete $8; + } + | LPAREN_TOK FLET_TOK LPAREN_TOK fvar an_formula RPAREN_TOK an_expr RPAREN_TOK + { + CVC4::Expr e(VC->listExpr(VC->listExpr(*$4, *$5))); + $$ = new CVC4::Expr(VC->listExpr("_LET", e, *$7)); + delete $4; + delete $5; + delete $7; + } +; + +fun_pred_symb: + SYM_TOK LBRACKET_TOK NUMERAL_TOK RBRACKET_TOK + { + $$ = new std::vector<CVC4::Expr>; + if (BVENABLED && *$1 == "repeat") { + $$->push_back(VC->idExpr("_BVREPEAT")); + } + else if (BVENABLED && *$1 == "zero_extend") { + $$->push_back(VC->idExpr("_BVZEROEXTEND")); + } + else if (BVENABLED && *$1 == "sign_extend") { + $$->push_back(VC->idExpr("_SX")); + $$->push_back(VC->idExpr("_smtlib")); + } + else if (BVENABLED && *$1 == "rotate_left") { + $$->push_back(VC->idExpr("_BVROTL")); + } + else if (BVENABLED && *$1 == "rotate_right") { + $$->push_back(VC->idExpr("_BVROTR")); + } + else if (BVENABLED && + $1->size() > 2 && + (*$1)[0] == 'b' && + (*$1)[1] == 'v') { + int i = 2; + while ((*$1)[i] >= '0' && (*$1)[i] <= '9') ++i; + if ((*$1)[i] == '\0') { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr($1->substr(2), 10)); + } + else $$->push_back(VC->idExpr(*$1)); + } + else $$->push_back(VC->idExpr(*$1)); + $$->push_back(VC->ratExpr(*$3)); + delete $1; + delete $3; + } + | SYM_TOK LBRACKET_TOK NUMERAL_TOK COLON_TOK NUMERAL_TOK RBRACKET_TOK + { + $$ = new std::vector<CVC4::Expr>; + if (BVENABLED && *$1 == "extract") { + $$->push_back(VC->idExpr("_EXTRACT")); + } + else $$->push_back(VC->idExpr(*$1)); + $$->push_back(VC->ratExpr(*$3)); + $$->push_back(VC->ratExpr(*$5)); + delete $1; + delete $3; + delete $5; + } + | SYM_TOK + { + $$ = new std::vector<CVC4::Expr>; + if (ARRAYSENABLED && *$1 == "select") { + $$->push_back(VC->idExpr("_READ")); + } + else if (ARRAYSENABLED && *$1 == "store") { + $$->push_back(VC->idExpr("_WRITE")); + } + else if (BVENABLED && *$1 == "bit0") { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr(0)); + $$->push_back(VC->ratExpr(1)); + } + else if (BVENABLED && *$1 == "bit1") { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr(1)); + $$->push_back(VC->ratExpr(1)); + } + else if (BVENABLED && *$1 == "concat") { + $$->push_back(VC->idExpr("_CONCAT")); + } + else if (BVENABLED && *$1 == "bvnot") { + $$->push_back(VC->idExpr("_BVNEG")); + } + else if (BVENABLED && *$1 == "bvand") { + $$->push_back(VC->idExpr("_BVAND")); + } + else if (BVENABLED && *$1 == "bvor") { + $$->push_back(VC->idExpr("_BVOR")); + } + else if (BVENABLED && *$1 == "bvneg") { + $$->push_back(VC->idExpr("_BVUMINUS")); + } + else if (BVENABLED && *$1 == "bvadd") { + $$->push_back(VC->idExpr("_BVPLUS")); + } + else if (BVENABLED && *$1 == "bvmul") { + $$->push_back(VC->idExpr("_BVMULT")); + } + else if (BVENABLED && *$1 == "bvudiv") { + $$->push_back(VC->idExpr("_BVUDIV")); + } + else if (BVENABLED && *$1 == "bvurem") { + $$->push_back(VC->idExpr("_BVUREM")); + } + else if (BVENABLED && *$1 == "bvshl") { + $$->push_back(VC->idExpr("_BVSHL")); + } + else if (BVENABLED && *$1 == "bvlshr") { + $$->push_back(VC->idExpr("_BVLSHR")); + } + + else if (BVENABLED && *$1 == "bvnand") { + $$->push_back(VC->idExpr("_BVNAND")); + } + else if (BVENABLED && *$1 == "bvnor") { + $$->push_back(VC->idExpr("_BVNOR")); + } + else if (BVENABLED && *$1 == "bvxor") { + $$->push_back(VC->idExpr("_BVXOR")); + } + else if (BVENABLED && *$1 == "bvxnor") { + $$->push_back(VC->idExpr("_BVXNOR")); + } + else if (BVENABLED && *$1 == "bvcomp") { + $$->push_back(VC->idExpr("_BVCOMP")); + } + + else if (BVENABLED && *$1 == "bvsub") { + $$->push_back(VC->idExpr("_BVSUB")); + } + else if (BVENABLED && *$1 == "bvsdiv") { + $$->push_back(VC->idExpr("_BVSDIV")); + } + else if (BVENABLED && *$1 == "bvsrem") { + $$->push_back(VC->idExpr("_BVSREM")); + } + else if (BVENABLED && *$1 == "bvsmod") { + $$->push_back(VC->idExpr("_BVSMOD")); + } + else if (BVENABLED && *$1 == "bvashr") { + $$->push_back(VC->idExpr("_BVASHR")); + } + + // predicates + else if (BVENABLED && (*$1 == "bvlt" || *$1 == "bvult")) { + $$->push_back(VC->idExpr("_BVLT")); + } + else if (BVENABLED && (*$1 == "bvleq" || *$1 == "bvule")) { + $$->push_back(VC->idExpr("_BVLE")); + } + else if (BVENABLED && (*$1 == "bvgeq" || *$1 == "bvuge")) { + $$->push_back(VC->idExpr("_BVGE")); + } + else if (BVENABLED && (*$1 == "bvgt" || *$1 == "bvugt")) { + $$->push_back(VC->idExpr("_BVGT")); + } + else if (BVENABLED && *$1 == "bvslt") { + $$->push_back(VC->idExpr("_BVSLT")); + } + else if (BVENABLED && (*$1 == "bvsleq" || *$1 == "bvsle")) { + $$->push_back(VC->idExpr("_BVSLE")); + } + else if (BVENABLED && (*$1 == "bvsgeq" || *$1 == "bvsge")) { + $$->push_back(VC->idExpr("_BVSGE")); + } + else if (BVENABLED && *$1 == "bvsgt") { + $$->push_back(VC->idExpr("_BVSGT")); + } + + // For backwards compatibility: + else if (BVENABLED && *$1 == "shift_left0") { + $$->push_back(VC->idExpr("_CONST_WIDTH_LEFTSHIFT")); + } + else if (BVENABLED && *$1 == "shift_right0") { + $$->push_back(VC->idExpr("_RIGHTSHIFT")); + } + else if (BVENABLED && *$1 == "sign_extend") { + $$->push_back(VC->idExpr("_SX")); + $$->push_back(VC->idExpr("_smtlib")); + } + + // Bitvector constants + else if (BVENABLED && + $1->size() > 2 && + (*$1)[0] == 'b' && + (*$1)[1] == 'v') { + bool done = false; + if ((*$1)[2] >= '0' && (*$1)[2] <= '9') { + int i = 3; + while ((*$1)[i] >= '0' && (*$1)[i] <= '9') ++i; + if ((*$1)[i] == '\0') { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr($1->substr(2), 10)); + $$->push_back(VC->ratExpr(32)); + done = true; + } + } + else if ($1->size() > 5) { + std::string s = $1->substr(0,5); + if (s == "bvbin") { + int i = 5; + while ((*$1)[i] >= '0' && (*$1)[i] <= '1') ++i; + if ((*$1)[i] == '\0') { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr($1->substr(5), 2)); + $$->push_back(VC->ratExpr(i-5)); + done = true; + } + } + else if (s == "bvhex") { + int i = 5; + char c = (*$1)[i]; + while ((c >= '0' && c <= '9') || + (c >= 'a' && c <= 'f') || + (c >= 'A' && c <= 'F')) { + ++i; + c =(*$1)[i]; + } + if ((*$1)[i] == '\0') { + $$->push_back(VC->idExpr("_BVCONST")); + $$->push_back(VC->ratExpr($1->substr(5), 16)); + $$->push_back(VC->ratExpr(i-5)); + done = true; + } + } + } + if (!done) $$->push_back(VC->idExpr(*$1)); + } + else { + $$->push_back(VC->idExpr(*$1)); + } + delete $1; + } + | AR_SYMB + { + $$ = new std::vector<CVC4::Expr>; + if ($1->length() == 1) { + switch ((*$1)[0]) { + case '+': $$->push_back(VC->idExpr("_PLUS")); break; + case '-': $$->push_back(VC->idExpr("_MINUS")); break; + case '*': $$->push_back(VC->idExpr("_MULT")); break; + case '~': $$->push_back(VC->idExpr("_UMINUS")); break; + case '/': $$->push_back(VC->idExpr("_DIVIDE")); break; + case '=': $$->push_back(VC->idExpr("_EQ")); break; + case '<': $$->push_back(VC->idExpr("_LT")); break; + case '>': $$->push_back(VC->idExpr("_GT")); break; + default: $$->push_back(VC->idExpr(*$1)); + } + } + else { + if (*$1 == "<=") { + $$->push_back(VC->idExpr("_LE")); + } else if (*$1 == ">=") { + $$->push_back(VC->idExpr("_GE")); + } + else $$->push_back(VC->idExpr(*$1)); + } + delete $1; + } + | NUMERAL_TOK + { + $$ = new std::vector<CVC4::Expr>; + $$->push_back(VC->ratExpr(*$1)); + delete $1; + } +; + + + +%% diff --git a/src/parser/smtlib_scanner.lpp b/src/parser/smtlib_scanner.lpp new file mode 100644 index 000000000..d5bdaaf26 --- /dev/null +++ b/src/parser/smtlib_scanner.lpp @@ -0,0 +1,260 @@ +%{ +/*****************************************************************************/ +/*! + * \file smtlib.lex + * + * Author: Clark Barrett + * + * Created: 2005 + * + * <hr> + * + * 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. + * + * <hr> + * + */ +/*****************************************************************************/ + +#include <iostream> +#include "parser_temp.h" +#include "expr_manager.h" /* for the benefit of parsesmtlib_defs.h */ +#include "parsesmtlib_defs.h" +#include "debug.h" + +namespace CVC4 { + extern ParserTemp* parserTemp; +} + +/* prefixing hack from gdb (via automake docs) */ +#define yymaxdepth smtlib_maxdepth +#define yyparse smtlib_parse +#define yylex smtlib_lex +#define yyerror smtlib_error +#define yylval smtlib_lval +#define yychar smtlib_char +#define yydebug smtlib_debug +#define yypact smtlib_pact +#define yyr1 smtlib_r1 +#define yyr2 smtlib_r2 +#define yydef smtlib_def +#define yychk smtlib_chk +#define yypgo smtlib_pgo +#define yyact smtlib_act +#define yyexca smtlib_exca +#define yyerrflag smtlib_errflag +#define yynerrs smtlib_nerrs +#define yyps smtlib_ps +#define yypv smtlib_pv +#define yys smtlib_s +#define yy_yys smtlib_yys +#define yystate smtlib_state +#define yytmp smtlib_tmp +#define yyv smtlib_v +#define yy_yyv smtlib_yyv +#define yyval smtlib_val +#define yylloc smtlib_lloc +#define yyreds smtlib_reds +#define yytoks smtlib_toks +#define yylhs smtlib_yylhs +#define yylen smtlib_yylen +#define yydefred smtlib_yydefred +#define yydgoto smtlib_yydgoto +#define yysindex smtlib_yysindex +#define yyrindex smtlib_yyrindex +#define yygindex smtlib_yygindex +#define yytable smtlib_yytable +#define yycheck smtlib_yycheck +#define yyname smtlib_yyname +#define yyrule smtlib_yyrule + +extern int smtlib_inputLine; +extern char *smtlibtext; + +extern int smtliberror (const char *msg); + +static int smtlibinput(std::istream& is, char* buf, int size) { + int res; + if(is) { + // If interactive, read line by line; otherwise read as much as we + // can gobble + if(CVC4::parserTemp->interactive) { + // Print the current prompt + std::cout << CVC4::parserTemp->getPrompt() << std::flush; + // Set the prompt to "middle of the command" one + CVC4::parserTemp->setPrompt2(); + // Read the line + is.getline(buf, size-1); + } else // Set the terminator char to 0 + is.getline(buf, size-1, 0); + // If failbit is set, but eof is not, it means the line simply + // didn't fit; so we clear the state and keep on reading. + bool partialStr = is.fail() && !is.eof(); + if(partialStr) + is.clear(); + + for(res = 0; res<size && buf[res] != 0; res++); + if(res == size) smtliberror("Lexer bug: overfilled the buffer"); + if(!partialStr) { // Insert \n into the buffer + buf[res++] = '\n'; + buf[res] = '\0'; + } + } else { + res = YY_NULL; + } + return res; +} + +// Redefine the input buffer function to read from an istream +#define YY_INPUT(buf,result,max_size) \ + result = smtlibinput(*CVC4::parserTemp->is, buf, max_size); + +int smtlib_bufSize() { return YY_BUF_SIZE; } +YY_BUFFER_STATE smtlib_buf_state() { return YY_CURRENT_BUFFER; } + +/* some wrappers for methods that need to refer to a struct. + These are used by CVC4::Parser. */ +void *smtlib_createBuffer(int sz) { + return (void *)smtlib_create_buffer(NULL, sz); +} +void smtlib_deleteBuffer(void *buf_state) { + smtlib_delete_buffer((struct yy_buffer_state *)buf_state); +} +void smtlib_switchToBuffer(void *buf_state) { + smtlib_switch_to_buffer((struct yy_buffer_state *)buf_state); +} +void *smtlib_bufState() { + return (void *)smtlib_buf_state(); +} + +void smtlib_setInteractive(bool is_interactive) { + yy_set_interactive(is_interactive); +} + +// File-static (local to this file) variables and functions +static std::string _string_lit; + + static char escapeChar(char c) { + switch(c) { + case 'n': return '\n'; + case 't': return '\t'; + default: return c; + } + } + +// for now, we don't have subranges. +// +// ".." { return DOTDOT_TOK; } +/*OPCHAR (['!#?\_$&\|\\@])*/ + +%} + +%option interactive +%option noyywrap +%option nounput +%option noreject +%option noyymore +%option yylineno + +%x COMMENT +%x STRING_LITERAL +%x USER_VALUE +%s PAT_MODE + +LETTER ([a-zA-Z]) +DIGIT ([0-9]) +OPCHAR (['\.\_]) +IDCHAR ({LETTER}|{DIGIT}|{OPCHAR}) +%% + +[\n] { CVC4::parserTemp->lineNum++; } +[ \t\r\f] { /* skip whitespace */ } + +{DIGIT}+"\."{DIGIT}+ { smtliblval.str = new std::string(smtlibtext); return NUMERAL_TOK; } +{DIGIT}+ { smtliblval.str = new std::string(smtlibtext); return NUMERAL_TOK; + } + +";" { BEGIN COMMENT; } +<COMMENT>"\n" { BEGIN INITIAL; /* return to normal mode */ + CVC4::parserTemp->lineNum++; } +<COMMENT>. { /* stay in comment mode */ } + +<INITIAL>"\"" { BEGIN STRING_LITERAL; + _string_lit.erase(_string_lit.begin(), + _string_lit.end()); } +<STRING_LITERAL>"\\". { /* escape characters (like \n or \") */ + _string_lit.insert(_string_lit.end(), + escapeChar(smtlibtext[1])); } +<STRING_LITERAL>"\"" { BEGIN INITIAL; /* return to normal mode */ + smtliblval.str = new std::string(_string_lit); + return STRING_TOK; } +<STRING_LITERAL>. { _string_lit.insert(_string_lit.end(),*smtlibtext); } + +<INITIAL>":pat" { BEGIN PAT_MODE; + return PAT_TOK;} +<PAT_MODE>"}" { BEGIN INITIAL; + return RCURBRACK_TOK; } +<INITIAL>"{" { BEGIN USER_VALUE; + _string_lit.erase(_string_lit.begin(), + _string_lit.end()); } +<USER_VALUE>"\\"[{}] { /* escape characters */ + _string_lit.insert(_string_lit.end(),smtlibtext[1]); } + +<USER_VALUE>"}" { BEGIN INITIAL; /* return to normal mode */ + smtliblval.str = new std::string(_string_lit); + return USER_VAL_TOK; } + +<USER_VALUE>"\n" { _string_lit.insert(_string_lit.end(),'\n'); + CVC4::parserTemp->lineNum++; } +<USER_VALUE>. { _string_lit.insert(_string_lit.end(),*smtlibtext); } + +"true" { return TRUE_TOK; } +"false" { return FALSE_TOK; } +"ite" { return ITE_TOK; } +"not" { return NOT_TOK; } +"implies" { return IMPLIES_TOK; } +"if_then_else" { return IF_THEN_ELSE_TOK; } +"and" { return AND_TOK; } +"or" { return OR_TOK; } +"xor" { return XOR_TOK; } +"iff" { return IFF_TOK; } +"exists" { return EXISTS_TOK; } +"forall" { return FORALL_TOK; } +"let" { return LET_TOK; } +"flet" { return FLET_TOK; } +"notes" { return NOTES_TOK; } +"cvc_command" { return CVC_COMMAND_TOK; } +"logic" { return LOGIC_TOK; } +"sat" { return SAT_TOK; } +"unsat" { return UNSAT_TOK; } +"unknown" { return UNKNOWN_TOK; } +"assumption" { return ASSUMPTION_TOK; } +"formula" { return FORMULA_TOK; } +"status" { return STATUS_TOK; } +"benchmark" { return BENCHMARK_TOK; } +"extrasorts" { return EXTRASORTS_TOK; } +"extrafuns" { return EXTRAFUNS_TOK; } +"extrapreds" { return EXTRAPREDS_TOK; } +"distinct" { return DISTINCT_TOK; } +":pattern" { return PAT_TOK; } +":" { return COLON_TOK; } +"\[" { return LBRACKET_TOK; } +"\]" { return RBRACKET_TOK; } +"{" { return LCURBRACK_TOK;} +"}" { return RCURBRACK_TOK;} +"(" { return LPAREN_TOK; } +")" { return RPAREN_TOK; } +"$" { return DOLLAR_TOK; } +"?" { return QUESTION_TOK; } + +[=<>&@#+\-*/%|~]+ { smtliblval.str = new std::string(smtlibtext); return AR_SYMB; } +({LETTER})({IDCHAR})* {smtliblval.str = new std::string(smtlibtext); return SYM_TOK; } + +<<EOF>> { return EOF_TOK; } + +. { smtliberror("Illegal input character."); } +%% + diff --git a/src/sat/Makefile.am b/src/sat/Makefile.am new file mode 100644 index 000000000..321507609 --- /dev/null +++ b/src/sat/Makefile.am @@ -0,0 +1,3 @@ +INCLUDES = -I@srcdir@/../include + +SUBDIRS = minisat diff --git a/src/sat/README.minisat b/src/sat/README.minisat new file mode 100644 index 000000000..128581c23 --- /dev/null +++ b/src/sat/README.minisat @@ -0,0 +1,10 @@ +This is MiniSAT 2-070721, downloaded from here: + + http://minisat.se/MiniSat.html + +on 10 November 2009. + +The code has been modified slightly to put everything in the CVC4::MiniSat namespace. +The build process has been modified. + +-- Morgan Deters <mdeters@cs.nyu.edu> Tue, 10 Nov 2009 07:16:14 -0500 diff --git a/src/sat/minisat/LICENSE b/src/sat/minisat/LICENSE new file mode 100644 index 000000000..c87a32731 --- /dev/null +++ b/src/sat/minisat/LICENSE @@ -0,0 +1,20 @@ +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. diff --git a/src/sat/minisat/Makefile.am b/src/sat/minisat/Makefile.am new file mode 100644 index 000000000..74d72d48d --- /dev/null +++ b/src/sat/minisat/Makefile.am @@ -0,0 +1,6 @@ +INCLUDES = -I@srcdir@/mtl -I@srcdir@/core -I@srcdir@/../../include + +noinst_LIBRARIES = libminisat.a +libminisat_a_SOURCES = \ + core/Solver.C \ + simp/SimpSolver.C diff --git a/src/sat/minisat/README b/src/sat/minisat/README new file mode 100644 index 000000000..e1b79329b --- /dev/null +++ b/src/sat/minisat/README @@ -0,0 +1,19 @@ +Directory overview: +================== + +mtl/ Mini Template Library +core/ A core version of the solver +simp/ An extended solver with simplification capabilities +README +LICENSE + +To build (release version: without assertions, statically linked, etc): +====================================================================== + +cd { core | simp } +gmake rs + +Usage: +====== + +TODO diff --git a/src/sat/minisat/core/Main.C b/src/sat/minisat/core/Main.C new file mode 100644 index 000000000..acef32cd5 --- /dev/null +++ b/src/sat/minisat/core/Main.C @@ -0,0 +1,344 @@ +/******************************************************************************************[Main.C] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#include <ctime> +#include <cstring> +#include <stdint.h> +#include <errno.h> + +#include <signal.h> +#include <zlib.h> + +#include "Solver.h" + +/*************************************************************************************/ +#ifdef _MSC_VER +#include <ctime> + +static inline double cpuTime(void) { + return (double)clock() / CLOCKS_PER_SEC; } +#else + +#include <sys/time.h> +#include <sys/resource.h> +#include <unistd.h> + +static inline double cpuTime(void) { + struct rusage ru; + getrusage(RUSAGE_SELF, &ru); + return (double)ru.ru_utime.tv_sec + (double)ru.ru_utime.tv_usec / 1000000; } +#endif + + +#if defined(__linux__) +static inline int memReadStat(int field) +{ + char name[256]; + pid_t pid = getpid(); + sprintf(name, "/proc/%d/statm", pid); + FILE* in = fopen(name, "rb"); + if (in == NULL) return 0; + int value; + for (; field >= 0; field--) + fscanf(in, "%d", &value); + fclose(in); + return value; +} +static inline uint64_t memUsed() { return (uint64_t)memReadStat(0) * (uint64_t)getpagesize(); } + + +#elif defined(__FreeBSD__) +static inline uint64_t memUsed(void) { + struct rusage ru; + getrusage(RUSAGE_SELF, &ru); + return ru.ru_maxrss*1024; } + + +#else +static inline uint64_t memUsed() { return 0; } +#endif + +#if defined(__linux__) +#include <fpu_control.h> +#endif + +//================================================================================================= +// DIMACS Parser: + +#define CHUNK_LIMIT 1048576 + +class StreamBuffer { + gzFile in; + char buf[CHUNK_LIMIT]; + int pos; + int size; + + void assureLookahead() { + if (pos >= size) { + pos = 0; + size = gzread(in, buf, sizeof(buf)); } } + +public: + StreamBuffer(gzFile i) : in(i), pos(0), size(0) { + assureLookahead(); } + + int operator * () { return (pos >= size) ? EOF : buf[pos]; } + void operator ++ () { pos++; assureLookahead(); } +}; + +//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + +template<class B> +static void skipWhitespace(B& in) { + while ((*in >= 9 && *in <= 13) || *in == 32) + ++in; } + +template<class B> +static void skipLine(B& in) { + for (;;){ + if (*in == EOF || *in == '\0') return; + if (*in == '\n') { ++in; return; } + ++in; } } + +template<class B> +static int parseInt(B& in) { + int val = 0; + bool neg = false; + skipWhitespace(in); + if (*in == '-') neg = true, ++in; + else if (*in == '+') ++in; + if (*in < '0' || *in > '9') reportf("PARSE ERROR! Unexpected char: %c\n", *in), exit(3); + while (*in >= '0' && *in <= '9') + val = val*10 + (*in - '0'), + ++in; + return neg ? -val : val; } + +template<class B> +static void readClause(B& in, Solver& S, vec<Lit>& lits) { + int parsed_lit, var; + lits.clear(); + for (;;){ + parsed_lit = parseInt(in); + if (parsed_lit == 0) break; + var = abs(parsed_lit)-1; + while (var >= S.nVars()) S.newVar(); + lits.push( (parsed_lit > 0) ? Lit(var) : ~Lit(var) ); + } +} + +template<class B> +static bool match(B& in, char* str) { + for (; *str != 0; ++str, ++in) + if (*str != *in) + return false; + return true; +} + + +template<class B> +static void parse_DIMACS_main(B& in, Solver& S) { + vec<Lit> lits; + for (;;){ + skipWhitespace(in); + if (*in == EOF) + break; + else if (*in == 'p'){ + if (match(in, "p cnf")){ + int vars = parseInt(in); + int clauses = parseInt(in); + reportf("| Number of variables: %-12d |\n", vars); + reportf("| Number of clauses: %-12d |\n", clauses); + }else{ + reportf("PARSE ERROR! Unexpected char: %c\n", *in), exit(3); + } + } else if (*in == 'c' || *in == 'p') + skipLine(in); + else + readClause(in, S, lits), + S.addClause(lits); + } +} + +// Inserts problem into solver. +// +static void parse_DIMACS(gzFile input_stream, Solver& S) { + StreamBuffer in(input_stream); + parse_DIMACS_main(in, S); } + + +//================================================================================================= + + +void printStats(Solver& solver) +{ + double cpu_time = cpuTime(); + uint64_t mem_used = memUsed(); + reportf("restarts : %lld\n", solver.starts); + reportf("conflicts : %-12lld (%.0f /sec)\n", solver.conflicts , solver.conflicts /cpu_time); + reportf("decisions : %-12lld (%4.2f %% random) (%.0f /sec)\n", solver.decisions, (float)solver.rnd_decisions*100 / (float)solver.decisions, solver.decisions /cpu_time); + reportf("propagations : %-12lld (%.0f /sec)\n", solver.propagations, solver.propagations/cpu_time); + reportf("conflict literals : %-12lld (%4.2f %% deleted)\n", solver.tot_literals, (solver.max_literals - solver.tot_literals)*100 / (double)solver.max_literals); + if (mem_used != 0) reportf("Memory used : %.2f MB\n", mem_used / 1048576.0); + reportf("CPU time : %g s\n", cpu_time); +} + +Solver* solver; +static void SIGINT_handler(int signum) { + reportf("\n"); reportf("*** INTERRUPTED ***\n"); + printStats(*solver); + reportf("\n"); reportf("*** INTERRUPTED ***\n"); + exit(1); } + + +//================================================================================================= +// Main: + +void printUsage(char** argv) +{ + reportf("USAGE: %s [options] <input-file> <result-output-file>\n\n where input may be either in plain or gzipped DIMACS.\n\n", argv[0]); + reportf("OPTIONS:\n\n"); + reportf(" -polarity-mode = {true,false,rnd}\n"); + reportf(" -decay = <num> [ 0 - 1 ]\n"); + reportf(" -rnd-freq = <num> [ 0 - 1 ]\n"); + reportf(" -verbosity = {0,1,2}\n"); + reportf("\n"); +} + + +const char* hasPrefix(const char* str, const char* prefix) +{ + int len = strlen(prefix); + if (strncmp(str, prefix, len) == 0) + return str + len; + else + return NULL; +} + + +int main(int argc, char** argv) +{ + Solver S; + S.verbosity = 1; + + + int i, j; + const char* value; + for (i = j = 0; i < argc; i++){ + if ((value = hasPrefix(argv[i], "-polarity-mode="))){ + if (strcmp(value, "true") == 0) + S.polarity_mode = Solver::polarity_true; + else if (strcmp(value, "false") == 0) + S.polarity_mode = Solver::polarity_false; + else if (strcmp(value, "rnd") == 0) + S.polarity_mode = Solver::polarity_rnd; + else{ + reportf("ERROR! unknown polarity-mode %s\n", value); + exit(0); } + + }else if ((value = hasPrefix(argv[i], "-rnd-freq="))){ + double rnd; + if (sscanf(value, "%lf", &rnd) <= 0 || rnd < 0 || rnd > 1){ + reportf("ERROR! illegal rnd-freq constant %s\n", value); + exit(0); } + S.random_var_freq = rnd; + + }else if ((value = hasPrefix(argv[i], "-decay="))){ + double decay; + if (sscanf(value, "%lf", &decay) <= 0 || decay <= 0 || decay > 1){ + reportf("ERROR! illegal decay constant %s\n", value); + exit(0); } + S.var_decay = 1 / decay; + + }else if ((value = hasPrefix(argv[i], "-verbosity="))){ + int verbosity = (int)strtol(value, NULL, 10); + if (verbosity == 0 && errno == EINVAL){ + reportf("ERROR! illegal verbosity level %s\n", value); + exit(0); } + S.verbosity = verbosity; + + }else if (strcmp(argv[i], "-h") == 0 || strcmp(argv[i], "-help") == 0 || strcmp(argv[i], "--help") == 0){ + printUsage(argv); + exit(0); + + }else if (strncmp(argv[i], "-", 1) == 0){ + reportf("ERROR! unknown flag %s\n", argv[i]); + exit(0); + + }else + argv[j++] = argv[i]; + } + argc = j; + + + reportf("This is MiniSat 2.0 beta\n"); +#if defined(__linux__) + fpu_control_t oldcw, newcw; + _FPU_GETCW(oldcw); newcw = (oldcw & ~_FPU_EXTENDED) | _FPU_DOUBLE; _FPU_SETCW(newcw); + reportf("WARNING: for repeatability, setting FPU to use double precision\n"); +#endif + double cpu_time = cpuTime(); + + solver = &S; + signal(SIGINT,SIGINT_handler); + signal(SIGHUP,SIGINT_handler); + + if (argc == 1) + reportf("Reading from standard input... Use '-h' or '--help' for help.\n"); + + gzFile in = (argc == 1) ? gzdopen(0, "rb") : gzopen(argv[1], "rb"); + if (in == NULL) + reportf("ERROR! Could not open file: %s\n", argc == 1 ? "<stdin>" : argv[1]), exit(1); + + reportf("============================[ Problem Statistics ]=============================\n"); + reportf("| |\n"); + + parse_DIMACS(in, S); + gzclose(in); + FILE* res = (argc >= 3) ? fopen(argv[2], "wb") : NULL; + + double parse_time = cpuTime() - cpu_time; + reportf("| Parsing time: %-12.2f s |\n", parse_time); + + if (!S.simplify()){ + reportf("Solved by unit propagation\n"); + if (res != NULL) fprintf(res, "UNSAT\n"), fclose(res); + printf("UNSATISFIABLE\n"); + exit(20); + } + + bool ret = S.solve(); + printStats(S); + reportf("\n"); + printf(ret ? "SATISFIABLE\n" : "UNSATISFIABLE\n"); + if (res != NULL){ + if (ret){ + fprintf(res, "SAT\n"); + for (int i = 0; i < S.nVars(); i++) + if (S.model[i] != l_Undef) + fprintf(res, "%s%s%d", (i==0)?"":" ", (S.model[i]==l_True)?"":"-", i+1); + fprintf(res, " 0\n"); + }else + fprintf(res, "UNSAT\n"); + fclose(res); + } + +#ifdef NDEBUG + exit(ret ? 10 : 20); // (faster than "return", which will invoke the destructor for 'Solver') +#endif +} diff --git a/src/sat/minisat/core/Makefile b/src/sat/minisat/core/Makefile new file mode 100644 index 000000000..42128c6d6 --- /dev/null +++ b/src/sat/minisat/core/Makefile @@ -0,0 +1,7 @@ +MTL = ../mtl +CHDRS = $(wildcard *.h) $(wildcard $(MTL)/*.h) +EXEC = minisat +CFLAGS = -I$(MTL) -Wall -ffloat-store +LFLAGS = -lz + +include ../mtl/template.mk diff --git a/src/sat/minisat/core/Solver.C b/src/sat/minisat/core/Solver.C new file mode 100644 index 000000000..d7a7bf8e1 --- /dev/null +++ b/src/sat/minisat/core/Solver.C @@ -0,0 +1,746 @@ +/****************************************************************************************[Solver.C] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#include "Solver.h" +#include "Sort.h" +#include <cmath> + +//================================================================================================= +// Constructor/Destructor: + +namespace CVC4 { +namespace MiniSat { + +Solver::Solver() : + + // Parameters: (formerly in 'SearchParams') + var_decay(1 / 0.95), clause_decay(1 / 0.999), random_var_freq(0.02) + , restart_first(100), restart_inc(1.5), learntsize_factor((double)1/(double)3), learntsize_inc(1.1) + + // More parameters: + // + , expensive_ccmin (true) + , polarity_mode (polarity_false) + , verbosity (0) + + // Statistics: (formerly in 'SolverStats') + // + , starts(0), decisions(0), rnd_decisions(0), propagations(0), conflicts(0) + , clauses_literals(0), learnts_literals(0), max_literals(0), tot_literals(0) + + , ok (true) + , cla_inc (1) + , var_inc (1) + , qhead (0) + , simpDB_assigns (-1) + , simpDB_props (0) + , order_heap (VarOrderLt(activity)) + , random_seed (91648253) + , progress_estimate(0) + , remove_satisfied (true) +{} + + +Solver::~Solver() +{ + for (int i = 0; i < learnts.size(); i++) free(learnts[i]); + for (int i = 0; i < clauses.size(); i++) free(clauses[i]); +} + + +//================================================================================================= +// Minor methods: + + +// Creates a new SAT variable in the solver. If 'decision_var' is cleared, variable will not be +// used as a decision variable (NOTE! This has effects on the meaning of a SATISFIABLE result). +// +Var Solver::newVar(bool sign, bool dvar) +{ + int v = nVars(); + watches .push(); // (list for positive literal) + watches .push(); // (list for negative literal) + reason .push(NULL); + assigns .push(toInt(l_Undef)); + level .push(-1); + activity .push(0); + seen .push(0); + + polarity .push((char)sign); + decision_var.push((char)dvar); + + insertVarOrder(v); + return v; +} + + +bool Solver::addClause(vec<Lit>& ps) +{ + assert(decisionLevel() == 0); + + if (!ok) + return false; + else{ + // Check if clause is satisfied and remove false/duplicate literals: + sort(ps); + Lit p; int i, j; + for (i = j = 0, p = lit_Undef; i < ps.size(); i++) + if (value(ps[i]) == l_True || ps[i] == ~p) + return true; + else if (value(ps[i]) != l_False && ps[i] != p) + ps[j++] = p = ps[i]; + ps.shrink(i - j); + } + + if (ps.size() == 0) + return ok = false; + else if (ps.size() == 1){ + assert(value(ps[0]) == l_Undef); + uncheckedEnqueue(ps[0]); + return ok = (propagate() == NULL); + }else{ + Clause* c = Clause_new(ps, false); + clauses.push(c); + attachClause(*c); + } + + return true; +} + + +void Solver::attachClause(Clause& c) { + assert(c.size() > 1); + watches[toInt(~c[0])].push(&c); + watches[toInt(~c[1])].push(&c); + if (c.learnt()) learnts_literals += c.size(); + else clauses_literals += c.size(); } + + +void Solver::detachClause(Clause& c) { + assert(c.size() > 1); + assert(find(watches[toInt(~c[0])], &c)); + assert(find(watches[toInt(~c[1])], &c)); + remove(watches[toInt(~c[0])], &c); + remove(watches[toInt(~c[1])], &c); + if (c.learnt()) learnts_literals -= c.size(); + else clauses_literals -= c.size(); } + + +void Solver::removeClause(Clause& c) { + detachClause(c); + free(&c); } + + +bool Solver::satisfied(const Clause& c) const { + for (int i = 0; i < c.size(); i++) + if (value(c[i]) == l_True) + return true; + return false; } + + +// Revert to the state at given level (keeping all assignment at 'level' but not beyond). +// +void Solver::cancelUntil(int level) { + if (decisionLevel() > level){ + for (int c = trail.size()-1; c >= trail_lim[level]; c--){ + Var x = var(trail[c]); + assigns[x] = toInt(l_Undef); + insertVarOrder(x); } + qhead = trail_lim[level]; + trail.shrink(trail.size() - trail_lim[level]); + trail_lim.shrink(trail_lim.size() - level); + } } + + +//================================================================================================= +// Major methods: + + +Lit Solver::pickBranchLit(int polarity_mode, double random_var_freq) +{ + Var next = var_Undef; + + // Random decision: + if (drand(random_seed) < random_var_freq && !order_heap.empty()){ + next = order_heap[irand(random_seed,order_heap.size())]; + if (toLbool(assigns[next]) == l_Undef && decision_var[next]) + rnd_decisions++; } + + // Activity based decision: + while (next == var_Undef || toLbool(assigns[next]) != l_Undef || !decision_var[next]) + if (order_heap.empty()){ + next = var_Undef; + break; + }else + next = order_heap.removeMin(); + + bool sign = false; + switch (polarity_mode){ + case polarity_true: sign = false; break; + case polarity_false: sign = true; break; + case polarity_user: sign = polarity[next]; break; + case polarity_rnd: sign = irand(random_seed, 2); break; + default: assert(false); } + + return next == var_Undef ? lit_Undef : Lit(next, sign); +} + + +/*_________________________________________________________________________________________________ +| +| analyze : (confl : Clause*) (out_learnt : vec<Lit>&) (out_btlevel : int&) -> [void] +| +| Description: +| Analyze conflict and produce a reason clause. +| +| Pre-conditions: +| * 'out_learnt' is assumed to be cleared. +| * Current decision level must be greater than root level. +| +| Post-conditions: +| * 'out_learnt[0]' is the asserting literal at level 'out_btlevel'. +| +| Effect: +| Will undo part of the trail, upto but not beyond the assumption of the current decision level. +|________________________________________________________________________________________________@*/ +void Solver::analyze(Clause* confl, vec<Lit>& out_learnt, int& out_btlevel) +{ + int pathC = 0; + Lit p = lit_Undef; + + // Generate conflict clause: + // + out_learnt.push(); // (leave room for the asserting literal) + int index = trail.size() - 1; + out_btlevel = 0; + + do{ + assert(confl != NULL); // (otherwise should be UIP) + Clause& c = *confl; + + if (c.learnt()) + claBumpActivity(c); + + for (int j = (p == lit_Undef) ? 0 : 1; j < c.size(); j++){ + Lit q = c[j]; + + if (!seen[var(q)] && level[var(q)] > 0){ + varBumpActivity(var(q)); + seen[var(q)] = 1; + if (level[var(q)] >= decisionLevel()) + pathC++; + else{ + out_learnt.push(q); + if (level[var(q)] > out_btlevel) + out_btlevel = level[var(q)]; + } + } + } + + // Select next clause to look at: + while (!seen[var(trail[index--])]); + p = trail[index+1]; + confl = reason[var(p)]; + seen[var(p)] = 0; + pathC--; + + }while (pathC > 0); + out_learnt[0] = ~p; + + // Simplify conflict clause: + // + int i, j; + if (expensive_ccmin){ + uint32_t abstract_level = 0; + for (i = 1; i < out_learnt.size(); i++) + abstract_level |= abstractLevel(var(out_learnt[i])); // (maintain an abstraction of levels involved in conflict) + + out_learnt.copyTo(analyze_toclear); + for (i = j = 1; i < out_learnt.size(); i++) + if (reason[var(out_learnt[i])] == NULL || !litRedundant(out_learnt[i], abstract_level)) + out_learnt[j++] = out_learnt[i]; + }else{ + out_learnt.copyTo(analyze_toclear); + for (i = j = 1; i < out_learnt.size(); i++){ + Clause& c = *reason[var(out_learnt[i])]; + for (int k = 1; k < c.size(); k++) + if (!seen[var(c[k])] && level[var(c[k])] > 0){ + out_learnt[j++] = out_learnt[i]; + break; } + } + } + max_literals += out_learnt.size(); + out_learnt.shrink(i - j); + tot_literals += out_learnt.size(); + + // Find correct backtrack level: + // + if (out_learnt.size() == 1) + out_btlevel = 0; + else{ + int max_i = 1; + for (int i = 2; i < out_learnt.size(); i++) + if (level[var(out_learnt[i])] > level[var(out_learnt[max_i])]) + max_i = i; + Lit p = out_learnt[max_i]; + out_learnt[max_i] = out_learnt[1]; + out_learnt[1] = p; + out_btlevel = level[var(p)]; + } + + + for (int j = 0; j < analyze_toclear.size(); j++) seen[var(analyze_toclear[j])] = 0; // ('seen[]' is now cleared) +} + + +// Check if 'p' can be removed. 'abstract_levels' is used to abort early if the algorithm is +// visiting literals at levels that cannot be removed later. +bool Solver::litRedundant(Lit p, uint32_t abstract_levels) +{ + analyze_stack.clear(); analyze_stack.push(p); + int top = analyze_toclear.size(); + while (analyze_stack.size() > 0){ + assert(reason[var(analyze_stack.last())] != NULL); + Clause& c = *reason[var(analyze_stack.last())]; analyze_stack.pop(); + + for (int i = 1; i < c.size(); i++){ + Lit p = c[i]; + if (!seen[var(p)] && level[var(p)] > 0){ + if (reason[var(p)] != NULL && (abstractLevel(var(p)) & abstract_levels) != 0){ + seen[var(p)] = 1; + analyze_stack.push(p); + analyze_toclear.push(p); + }else{ + for (int j = top; j < analyze_toclear.size(); j++) + seen[var(analyze_toclear[j])] = 0; + analyze_toclear.shrink(analyze_toclear.size() - top); + return false; + } + } + } + } + + return true; +} + + +/*_________________________________________________________________________________________________ +| +| analyzeFinal : (p : Lit) -> [void] +| +| Description: +| Specialized analysis procedure to express the final conflict in terms of assumptions. +| Calculates the (possibly empty) set of assumptions that led to the assignment of 'p', and +| stores the result in 'out_conflict'. +|________________________________________________________________________________________________@*/ +void Solver::analyzeFinal(Lit p, vec<Lit>& out_conflict) +{ + out_conflict.clear(); + out_conflict.push(p); + + if (decisionLevel() == 0) + return; + + seen[var(p)] = 1; + + for (int i = trail.size()-1; i >= trail_lim[0]; i--){ + Var x = var(trail[i]); + if (seen[x]){ + if (reason[x] == NULL){ + assert(level[x] > 0); + out_conflict.push(~trail[i]); + }else{ + Clause& c = *reason[x]; + for (int j = 1; j < c.size(); j++) + if (level[var(c[j])] > 0) + seen[var(c[j])] = 1; + } + seen[x] = 0; + } + } + + seen[var(p)] = 0; +} + + +void Solver::uncheckedEnqueue(Lit p, Clause* from) +{ + assert(value(p) == l_Undef); + assigns [var(p)] = toInt(lbool(!sign(p))); // <<== abstract but not uttermost effecient + level [var(p)] = decisionLevel(); + reason [var(p)] = from; + trail.push(p); +} + + +/*_________________________________________________________________________________________________ +| +| propagate : [void] -> [Clause*] +| +| Description: +| Propagates all enqueued facts. If a conflict arises, the conflicting clause is returned, +| otherwise NULL. +| +| Post-conditions: +| * the propagation queue is empty, even if there was a conflict. +|________________________________________________________________________________________________@*/ +Clause* Solver::propagate() +{ + Clause* confl = NULL; + int num_props = 0; + + while (qhead < trail.size()){ + Lit p = trail[qhead++]; // 'p' is enqueued fact to propagate. + vec<Clause*>& ws = watches[toInt(p)]; + Clause **i, **j, **end; + num_props++; + + for (i = j = (Clause**)ws, end = i + ws.size(); i != end;){ + Clause& c = **i++; + + // Make sure the false literal is data[1]: + Lit false_lit = ~p; + if (c[0] == false_lit) + c[0] = c[1], c[1] = false_lit; + + assert(c[1] == false_lit); + + // If 0th watch is true, then clause is already satisfied. + Lit first = c[0]; + if (value(first) == l_True){ + *j++ = &c; + }else{ + // Look for new watch: + for (int k = 2; k < c.size(); k++) + if (value(c[k]) != l_False){ + c[1] = c[k]; c[k] = false_lit; + watches[toInt(~c[1])].push(&c); + goto FoundWatch; } + + // Did not find watch -- clause is unit under assignment: + *j++ = &c; + if (value(first) == l_False){ + confl = &c; + qhead = trail.size(); + // Copy the remaining watches: + while (i < end) + *j++ = *i++; + }else + uncheckedEnqueue(first, &c); + } + FoundWatch:; + } + ws.shrink(i - j); + } + propagations += num_props; + simpDB_props -= num_props; + + return confl; +} + +/*_________________________________________________________________________________________________ +| +| reduceDB : () -> [void] +| +| Description: +| Remove half of the learnt clauses, minus the clauses locked by the current assignment. Locked +| clauses are clauses that are reason to some assignment. Binary clauses are never removed. +|________________________________________________________________________________________________@*/ +struct reduceDB_lt { bool operator () (Clause* x, Clause* y) { return x->size() > 2 && (y->size() == 2 || x->activity() < y->activity()); } }; +void Solver::reduceDB() +{ + int i, j; + double extra_lim = cla_inc / learnts.size(); // Remove any clause below this activity + + sort(learnts, reduceDB_lt()); + for (i = j = 0; i < learnts.size() / 2; i++){ + if (learnts[i]->size() > 2 && !locked(*learnts[i])) + removeClause(*learnts[i]); + else + learnts[j++] = learnts[i]; + } + for (; i < learnts.size(); i++){ + if (learnts[i]->size() > 2 && !locked(*learnts[i]) && learnts[i]->activity() < extra_lim) + removeClause(*learnts[i]); + else + learnts[j++] = learnts[i]; + } + learnts.shrink(i - j); +} + + +void Solver::removeSatisfied(vec<Clause*>& cs) +{ + int i,j; + for (i = j = 0; i < cs.size(); i++){ + if (satisfied(*cs[i])) + removeClause(*cs[i]); + else + cs[j++] = cs[i]; + } + cs.shrink(i - j); +} + + +/*_________________________________________________________________________________________________ +| +| simplify : [void] -> [bool] +| +| Description: +| Simplify the clause database according to the current top-level assigment. Currently, the only +| thing done here is the removal of satisfied clauses, but more things can be put here. +|________________________________________________________________________________________________@*/ +bool Solver::simplify() +{ + assert(decisionLevel() == 0); + + if (!ok || propagate() != NULL) + return ok = false; + + if (nAssigns() == simpDB_assigns || (simpDB_props > 0)) + return true; + + // Remove satisfied clauses: + removeSatisfied(learnts); + if (remove_satisfied) // Can be turned off. + removeSatisfied(clauses); + + // Remove fixed variables from the variable heap: + order_heap.filter(VarFilter(*this)); + + simpDB_assigns = nAssigns(); + simpDB_props = clauses_literals + learnts_literals; // (shouldn't depend on stats really, but it will do for now) + + return true; +} + + +/*_________________________________________________________________________________________________ +| +| search : (nof_conflicts : int) (nof_learnts : int) (params : const SearchParams&) -> [lbool] +| +| Description: +| Search for a model the specified number of conflicts, keeping the number of learnt clauses +| below the provided limit. NOTE! Use negative value for 'nof_conflicts' or 'nof_learnts' to +| indicate infinity. +| +| Output: +| 'l_True' if a partial assigment that is consistent with respect to the clauseset is found. If +| all variables are decision variables, this means that the clause set is satisfiable. 'l_False' +| if the clause set is unsatisfiable. 'l_Undef' if the bound on number of conflicts is reached. +|________________________________________________________________________________________________@*/ +lbool Solver::search(int nof_conflicts, int nof_learnts) +{ + assert(ok); + int backtrack_level; + int conflictC = 0; + vec<Lit> learnt_clause; + + starts++; + + bool first = true; + + for (;;){ + Clause* confl = propagate(); + if (confl != NULL){ + // CONFLICT + conflicts++; conflictC++; + if (decisionLevel() == 0) return l_False; + + first = false; + + learnt_clause.clear(); + analyze(confl, learnt_clause, backtrack_level); + cancelUntil(backtrack_level); + assert(value(learnt_clause[0]) == l_Undef); + + if (learnt_clause.size() == 1){ + uncheckedEnqueue(learnt_clause[0]); + }else{ + Clause* c = Clause_new(learnt_clause, true); + learnts.push(c); + attachClause(*c); + claBumpActivity(*c); + uncheckedEnqueue(learnt_clause[0], c); + } + + varDecayActivity(); + claDecayActivity(); + + }else{ + // NO CONFLICT + + if (nof_conflicts >= 0 && conflictC >= nof_conflicts){ + // Reached bound on number of conflicts: + progress_estimate = progressEstimate(); + cancelUntil(0); + return l_Undef; } + + // Simplify the set of problem clauses: + if (decisionLevel() == 0 && !simplify()) + return l_False; + + if (nof_learnts >= 0 && learnts.size()-nAssigns() >= nof_learnts) + // Reduce the set of learnt clauses: + reduceDB(); + + Lit next = lit_Undef; + while (decisionLevel() < assumptions.size()){ + // Perform user provided assumption: + Lit p = assumptions[decisionLevel()]; + if (value(p) == l_True){ + // Dummy decision level: + newDecisionLevel(); + }else if (value(p) == l_False){ + analyzeFinal(~p, conflict); + return l_False; + }else{ + next = p; + break; + } + } + + if (next == lit_Undef){ + // New variable decision: + decisions++; + next = pickBranchLit(polarity_mode, random_var_freq); + + if (next == lit_Undef) + // Model found: + return l_True; + } + + // Increase decision level and enqueue 'next' + assert(value(next) == l_Undef); + newDecisionLevel(); + uncheckedEnqueue(next); + } + } +} + + +double Solver::progressEstimate() const +{ + double progress = 0; + double F = 1.0 / nVars(); + + for (int i = 0; i <= decisionLevel(); i++){ + int beg = i == 0 ? 0 : trail_lim[i - 1]; + int end = i == decisionLevel() ? trail.size() : trail_lim[i]; + progress += pow(F, i) * (end - beg); + } + + return progress / nVars(); +} + + +bool Solver::solve(const vec<Lit>& assumps) +{ + model.clear(); + conflict.clear(); + + if (!ok) return false; + + assumps.copyTo(assumptions); + + double nof_conflicts = restart_first; + double nof_learnts = nClauses() * learntsize_factor; + lbool status = l_Undef; + + if (verbosity >= 1){ + reportf("============================[ Search Statistics ]==============================\n"); + reportf("| Conflicts | ORIGINAL | LEARNT | Progress |\n"); + reportf("| | Vars Clauses Literals | Limit Clauses Lit/Cl | |\n"); + reportf("===============================================================================\n"); + } + + // Search: + while (status == l_Undef){ + if (verbosity >= 1) + reportf("| %9d | %7d %8d %8d | %8d %8d %6.0f | %6.3f %% |\n", (int)conflicts, order_heap.size(), nClauses(), (int)clauses_literals, (int)nof_learnts, nLearnts(), (double)learnts_literals/nLearnts(), progress_estimate*100), fflush(stdout); + status = search((int)nof_conflicts, (int)nof_learnts); + nof_conflicts *= restart_inc; + nof_learnts *= learntsize_inc; + } + + if (verbosity >= 1) + reportf("===============================================================================\n"); + + + if (status == l_True){ + // Extend & copy model: + model.growTo(nVars()); + for (int i = 0; i < nVars(); i++) model[i] = value(i); +#ifndef NDEBUG + verifyModel(); +#endif + }else{ + assert(status == l_False); + if (conflict.size() == 0) + ok = false; + } + + cancelUntil(0); + return status == l_True; +} + +//================================================================================================= +// Debug methods: + + +void Solver::verifyModel() +{ + bool failed = false; + for (int i = 0; i < clauses.size(); i++){ + assert(clauses[i]->mark() == 0); + Clause& c = *clauses[i]; + for (int j = 0; j < c.size(); j++) + if (modelValue(c[j]) == l_True) + goto next; + + reportf("unsatisfied clause: "); + printClause(*clauses[i]); + reportf("\n"); + failed = true; + next:; + } + + assert(!failed); + + reportf("Verified %d original clauses.\n", clauses.size()); +} + + +void Solver::checkLiteralCount() +{ + // Check that sizes are calculated correctly: + int cnt = 0; + for (int i = 0; i < clauses.size(); i++) + if (clauses[i]->mark() == 0) + cnt += clauses[i]->size(); + + if ((int)clauses_literals != cnt){ + fprintf(stderr, "literal count: %d, real value = %d\n", (int)clauses_literals, cnt); + assert((int)clauses_literals == cnt); + } +} + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + diff --git a/src/sat/minisat/core/Solver.h b/src/sat/minisat/core/Solver.h new file mode 100644 index 000000000..e53cefc24 --- /dev/null +++ b/src/sat/minisat/core/Solver.h @@ -0,0 +1,306 @@ +/****************************************************************************************[Solver.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_Solver_h +#define CVC4_MiniSat_Solver_h + +#include <cstdio> + +#include "Vec.h" +#include "Heap.h" +#include "Alg.h" + +#include "SolverTypes.h" + + +//================================================================================================= +// Solver -- the main class: + +namespace CVC4 { +namespace MiniSat { + +class Solver { +public: + + // Constructor/Destructor: + // + Solver(); + ~Solver(); + + // Problem specification: + // + Var newVar (bool polarity = true, bool dvar = true); // Add a new variable with parameters specifying variable mode. + bool addClause (vec<Lit>& ps); // Add a clause to the solver. NOTE! 'ps' may be shrunk by this method! + + // Solving: + // + bool simplify (); // Removes already satisfied clauses. + bool solve (const vec<Lit>& assumps); // Search for a model that respects a given set of assumptions. + bool solve (); // Search without assumptions. + bool okay () const; // FALSE means solver is in a conflicting state + + // Variable mode: + // + void setPolarity (Var v, bool b); // Declare which polarity the decision heuristic should use for a variable. Requires mode 'polarity_user'. + void setDecisionVar (Var v, bool b); // Declare if a variable should be eligible for selection in the decision heuristic. + + // Read state: + // + lbool value (Var x) const; // The current value of a variable. + lbool value (Lit p) const; // The current value of a literal. + lbool modelValue (Lit p) const; // The value of a literal in the last model. The last call to solve must have been satisfiable. + int nAssigns () const; // The current number of assigned literals. + int nClauses () const; // The current number of original clauses. + int nLearnts () const; // The current number of learnt clauses. + int nVars () const; // The current number of variables. + + // Extra results: (read-only member variable) + // + vec<lbool> model; // If problem is satisfiable, this vector contains the model (if any). + vec<Lit> conflict; // If problem is unsatisfiable (possibly under assumptions), + // this vector represent the final conflict clause expressed in the assumptions. + + // Mode of operation: + // + double var_decay; // Inverse of the variable activity decay factor. (default 1 / 0.95) + double clause_decay; // Inverse of the clause activity decay factor. (1 / 0.999) + double random_var_freq; // The frequency with which the decision heuristic tries to choose a random variable. (default 0.02) + int restart_first; // The initial restart limit. (default 100) + double restart_inc; // The factor with which the restart limit is multiplied in each restart. (default 1.5) + double learntsize_factor; // The intitial limit for learnt clauses is a factor of the original clauses. (default 1 / 3) + double learntsize_inc; // The limit for learnt clauses is multiplied with this factor each restart. (default 1.1) + bool expensive_ccmin; // Controls conflict clause minimization. (default TRUE) + int polarity_mode; // Controls which polarity the decision heuristic chooses. See enum below for allowed modes. (default polarity_false) + int verbosity; // Verbosity level. 0=silent, 1=some progress report (default 0) + + enum { polarity_true = 0, polarity_false = 1, polarity_user = 2, polarity_rnd = 3 }; + + // Statistics: (read-only member variable) + // + uint64_t starts, decisions, rnd_decisions, propagations, conflicts; + uint64_t clauses_literals, learnts_literals, max_literals, tot_literals; + +protected: + + // Helper structures: + // + struct VarOrderLt { + const vec<double>& activity; + bool operator () (Var x, Var y) const { return activity[x] > activity[y]; } + VarOrderLt(const vec<double>& act) : activity(act) { } + }; + + friend class VarFilter; + struct VarFilter { + const Solver& s; + VarFilter(const Solver& _s) : s(_s) {} + bool operator()(Var v) const { return toLbool(s.assigns[v]) == l_Undef && s.decision_var[v]; } + }; + + // Solver state: + // + bool ok; // If FALSE, the constraints are already unsatisfiable. No part of the solver state may be used! + vec<Clause*> clauses; // List of problem clauses. + vec<Clause*> learnts; // List of learnt clauses. + double cla_inc; // Amount to bump next clause with. + vec<double> activity; // A heuristic measurement of the activity of a variable. + double var_inc; // Amount to bump next variable with. + vec<vec<Clause*> > watches; // 'watches[lit]' is a list of constraints watching 'lit' (will go there if literal becomes true). + vec<char> assigns; // The current assignments (lbool:s stored as char:s). + vec<char> polarity; // The preferred polarity of each variable. + vec<char> decision_var; // Declares if a variable is eligible for selection in the decision heuristic. + vec<Lit> trail; // Assignment stack; stores all assigments made in the order they were made. + vec<int> trail_lim; // Separator indices for different decision levels in 'trail'. + vec<Clause*> reason; // 'reason[var]' is the clause that implied the variables current value, or 'NULL' if none. + vec<int> level; // 'level[var]' contains the level at which the assignment was made. + int qhead; // Head of queue (as index into the trail -- no more explicit propagation queue in MiniSat). + int simpDB_assigns; // Number of top-level assignments since last execution of 'simplify()'. + int64_t simpDB_props; // Remaining number of propagations that must be made before next execution of 'simplify()'. + vec<Lit> assumptions; // Current set of assumptions provided to solve by the user. + Heap<VarOrderLt> order_heap; // A priority queue of variables ordered with respect to the variable activity. + double random_seed; // Used by the random variable selection. + double progress_estimate;// Set by 'search()'. + bool remove_satisfied; // Indicates whether possibly inefficient linear scan for satisfied clauses should be performed in 'simplify'. + + // Temporaries (to reduce allocation overhead). Each variable is prefixed by the method in which it is + // used, exept 'seen' wich is used in several places. + // + vec<char> seen; + vec<Lit> analyze_stack; + vec<Lit> analyze_toclear; + vec<Lit> add_tmp; + + // Main internal methods: + // + void insertVarOrder (Var x); // Insert a variable in the decision order priority queue. + Lit pickBranchLit (int polarity_mode, double random_var_freq); // Return the next decision variable. + void newDecisionLevel (); // Begins a new decision level. + void uncheckedEnqueue (Lit p, Clause* from = NULL); // Enqueue a literal. Assumes value of literal is undefined. + bool enqueue (Lit p, Clause* from = NULL); // Test if fact 'p' contradicts current state, enqueue otherwise. + Clause* propagate (); // Perform unit propagation. Returns possibly conflicting clause. + void cancelUntil (int level); // Backtrack until a certain level. + void analyze (Clause* confl, vec<Lit>& out_learnt, int& out_btlevel); // (bt = backtrack) + void analyzeFinal (Lit p, vec<Lit>& out_conflict); // COULD THIS BE IMPLEMENTED BY THE ORDINARIY "analyze" BY SOME REASONABLE GENERALIZATION? + bool litRedundant (Lit p, uint32_t abstract_levels); // (helper method for 'analyze()') + lbool search (int nof_conflicts, int nof_learnts); // Search for a given number of conflicts. + void reduceDB (); // Reduce the set of learnt clauses. + void removeSatisfied (vec<Clause*>& cs); // Shrink 'cs' to contain only non-satisfied clauses. + + // Maintaining Variable/Clause activity: + // + void varDecayActivity (); // Decay all variables with the specified factor. Implemented by increasing the 'bump' value instead. + void varBumpActivity (Var v); // Increase a variable with the current 'bump' value. + void claDecayActivity (); // Decay all clauses with the specified factor. Implemented by increasing the 'bump' value instead. + void claBumpActivity (Clause& c); // Increase a clause with the current 'bump' value. + + // Operations on clauses: + // + void attachClause (Clause& c); // Attach a clause to watcher lists. + void detachClause (Clause& c); // Detach a clause to watcher lists. + void removeClause (Clause& c); // Detach and free a clause. + bool locked (const Clause& c) const; // Returns TRUE if a clause is a reason for some implication in the current state. + bool satisfied (const Clause& c) const; // Returns TRUE if a clause is satisfied in the current state. + + // Misc: + // + int decisionLevel () const; // Gives the current decisionlevel. + uint32_t abstractLevel (Var x) const; // Used to represent an abstraction of sets of decision levels. + double progressEstimate () const; // DELETE THIS ?? IT'S NOT VERY USEFUL ... + + // Debug: + void printLit (Lit l); + template<class C> + void printClause (const C& c); + void verifyModel (); + void checkLiteralCount(); + + // Static helpers: + // + + // Returns a random float 0 <= x < 1. Seed must never be 0. + static inline double drand(double& seed) { + seed *= 1389796; + int q = (int)(seed / 2147483647); + seed -= (double)q * 2147483647; + return seed / 2147483647; } + + // Returns a random integer 0 <= x < size. Seed must never be 0. + static inline int irand(double& seed, int size) { + return (int)(drand(seed) * size); } +}; + + +//================================================================================================= +// Implementation of inline methods: + + +inline void Solver::insertVarOrder(Var x) { + if (!order_heap.inHeap(x) && decision_var[x]) order_heap.insert(x); } + +inline void Solver::varDecayActivity() { var_inc *= var_decay; } +inline void Solver::varBumpActivity(Var v) { + if ( (activity[v] += var_inc) > 1e100 ) { + // Rescale: + for (int i = 0; i < nVars(); i++) + activity[i] *= 1e-100; + var_inc *= 1e-100; } + + // Update order_heap with respect to new activity: + if (order_heap.inHeap(v)) + order_heap.decrease(v); } + +inline void Solver::claDecayActivity() { cla_inc *= clause_decay; } +inline void Solver::claBumpActivity (Clause& c) { + if ( (c.activity() += cla_inc) > 1e20 ) { + // Rescale: + for (int i = 0; i < learnts.size(); i++) + learnts[i]->activity() *= 1e-20; + cla_inc *= 1e-20; } } + +inline bool Solver::enqueue (Lit p, Clause* from) { return value(p) != l_Undef ? value(p) != l_False : (uncheckedEnqueue(p, from), true); } +inline bool Solver::locked (const Clause& c) const { return reason[var(c[0])] == &c && value(c[0]) == l_True; } +inline void Solver::newDecisionLevel() { trail_lim.push(trail.size()); } + +inline int Solver::decisionLevel () const { return trail_lim.size(); } +inline uint32_t Solver::abstractLevel (Var x) const { return 1 << (level[x] & 31); } +inline lbool Solver::value (Var x) const { return toLbool(assigns[x]); } +inline lbool Solver::value (Lit p) const { return toLbool(assigns[var(p)]) ^ sign(p); } +inline lbool Solver::modelValue (Lit p) const { return model[var(p)] ^ sign(p); } +inline int Solver::nAssigns () const { return trail.size(); } +inline int Solver::nClauses () const { return clauses.size(); } +inline int Solver::nLearnts () const { return learnts.size(); } +inline int Solver::nVars () const { return assigns.size(); } +inline void Solver::setPolarity (Var v, bool b) { polarity [v] = (char)b; } +inline void Solver::setDecisionVar(Var v, bool b) { decision_var[v] = (char)b; if (b) { insertVarOrder(v); } } +inline bool Solver::solve () { vec<Lit> tmp; return solve(tmp); } +inline bool Solver::okay () const { return ok; } + + + +//================================================================================================= +// Debug + etc: + + +#define reportf(format, args...) ( fflush(stdout), fprintf(stderr, format, ## args), fflush(stderr) ) + +static inline void logLit(FILE* f, Lit l) +{ + fprintf(f, "%sx%d", sign(l) ? "~" : "", var(l)+1); +} + +static inline void logLits(FILE* f, const vec<Lit>& ls) +{ + fprintf(f, "[ "); + if (ls.size() > 0){ + logLit(f, ls[0]); + for (int i = 1; i < ls.size(); i++){ + fprintf(f, ", "); + logLit(f, ls[i]); + } + } + fprintf(f, "] "); +} + +static inline const char* showBool(bool b) { return b ? "true" : "false"; } + + +// Just like 'assert()' but expression will be evaluated in the release version as well. +static inline void check(bool expr) { assert(expr); } + + +inline void Solver::printLit(Lit l) +{ + reportf("%s%d:%c", sign(l) ? "-" : "", var(l)+1, value(l) == l_True ? '1' : (value(l) == l_False ? '0' : 'X')); +} + + +template<class C> +inline void Solver::printClause(const C& c) +{ + for (int i = 0; i < c.size(); i++){ + printLit(c[i]); + fprintf(stderr, " "); + } +} + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +//================================================================================================= +#endif /* CVC4_MiniSat_Solver_h */ diff --git a/src/sat/minisat/core/SolverTypes.h b/src/sat/minisat/core/SolverTypes.h new file mode 100644 index 000000000..55e6d75fd --- /dev/null +++ b/src/sat/minisat/core/SolverTypes.h @@ -0,0 +1,202 @@ +/***********************************************************************************[SolverTypes.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_SolverTypes_h +#define CVC4_MiniSat_SolverTypes_h + +#include <cassert> +#include <stdint.h> + +namespace CVC4 { +namespace MiniSat { + +//================================================================================================= +// Variables, literals, lifted booleans, clauses: + + +// NOTE! Variables are just integers. No abstraction here. They should be chosen from 0..N, +// so that they can be used as array indices. + +typedef int Var; +#define var_Undef (-1) + + +class Lit { + int x; + public: + Lit() : x(2*var_Undef) { } // (lit_Undef) + explicit Lit(Var var, bool sign = false) : x((var+var) + (int)sign) { } + + // Don't use these for constructing/deconstructing literals. Use the normal constructors instead. + friend int toInt (Lit p); // Guarantees small, positive integers suitable for array indexing. + friend Lit toLit (int i); // Inverse of 'toInt()' + friend Lit operator ~(Lit p); + friend bool sign (Lit p); + friend int var (Lit p); + friend Lit unsign (Lit p); + friend Lit id (Lit p, bool sgn); + + bool operator == (Lit p) const { return x == p.x; } + bool operator != (Lit p) const { return x != p.x; } + bool operator < (Lit p) const { return x < p.x; } // '<' guarantees that p, ~p are adjacent in the ordering. +}; + +inline int toInt (Lit p) { return p.x; } +inline Lit toLit (int i) { Lit p; p.x = i; return p; } +inline Lit operator ~(Lit p) { Lit q; q.x = p.x ^ 1; return q; } +inline bool sign (Lit p) { return p.x & 1; } +inline int var (Lit p) { return p.x >> 1; } +inline Lit unsign (Lit p) { Lit q; q.x = p.x & ~1; return q; } +inline Lit id (Lit p, bool sgn) { Lit q; q.x = p.x ^ (int)sgn; return q; } + +const Lit lit_Undef(var_Undef, false); // }- Useful special constants. +const Lit lit_Error(var_Undef, true ); // } + + +//================================================================================================= +// Lifted booleans: + + +class lbool { + char value; + explicit lbool(int v) : value(v) { } + +public: + lbool() : value(0) { } + lbool(bool x) : value((int)x*2-1) { } + int toInt(void) const { return value; } + + bool operator == (lbool b) const { return value == b.value; } + bool operator != (lbool b) const { return value != b.value; } + lbool operator ^ (bool b) const { return b ? lbool(-value) : lbool(value); } + + friend int toInt (lbool l); + friend lbool toLbool(int v); +}; +inline int toInt (lbool l) { return l.toInt(); } +inline lbool toLbool(int v) { return lbool(v); } + +const lbool l_True = toLbool( 1); +const lbool l_False = toLbool(-1); +const lbool l_Undef = toLbool( 0); + +//================================================================================================= +// Clause -- a simple class for representing a clause: + + +class Clause { + uint32_t size_etc; + union { float act; uint32_t abst; } extra; + Lit data[0]; + +public: + void calcAbstraction() { + uint32_t abstraction = 0; + for (int i = 0; i < size(); i++) + abstraction |= 1 << (var(data[i]) & 31); + extra.abst = abstraction; } + + // NOTE: This constructor cannot be used directly (doesn't allocate enough memory). + template<class V> + Clause(const V& ps, bool learnt) { + size_etc = (ps.size() << 3) | (uint32_t)learnt; + for (int i = 0; i < ps.size(); i++) data[i] = ps[i]; + if (learnt) extra.act = 0; else calcAbstraction(); } + + // -- use this function instead: + template<class V> + friend Clause* Clause_new(const V& ps, bool learnt = false) { + assert(sizeof(Lit) == sizeof(uint32_t)); + assert(sizeof(float) == sizeof(uint32_t)); + void* mem = malloc(sizeof(Clause) + sizeof(uint32_t)*(ps.size())); + return new (mem) Clause(ps, learnt); } + + int size () const { return size_etc >> 3; } + void shrink (int i) { assert(i <= size()); size_etc = (((size_etc >> 3) - i) << 3) | (size_etc & 7); } + void pop () { shrink(1); } + bool learnt () const { return size_etc & 1; } + uint32_t mark () const { return (size_etc >> 1) & 3; } + void mark (uint32_t m) { size_etc = (size_etc & ~6) | ((m & 3) << 1); } + const Lit& last () const { return data[size()-1]; } + + // NOTE: somewhat unsafe to change the clause in-place! Must manually call 'calcAbstraction' afterwards for + // subsumption operations to behave correctly. + Lit& operator [] (int i) { return data[i]; } + Lit operator [] (int i) const { return data[i]; } + operator const Lit* (void) const { return data; } + + float& activity () { return extra.act; } + uint32_t abstraction () const { return extra.abst; } + + Lit subsumes (const Clause& other) const; + void strengthen (Lit p); +}; + + +/*_________________________________________________________________________________________________ +| +| subsumes : (other : const Clause&) -> Lit +| +| Description: +| Checks if clause subsumes 'other', and at the same time, if it can be used to simplify 'other' +| by subsumption resolution. +| +| Result: +| lit_Error - No subsumption or simplification +| lit_Undef - Clause subsumes 'other' +| p - The literal p can be deleted from 'other' +|________________________________________________________________________________________________@*/ +inline Lit Clause::subsumes(const Clause& other) const +{ + if (other.size() < size() || (extra.abst & ~other.extra.abst) != 0) + return lit_Error; + + Lit ret = lit_Undef; + const Lit* c = (const Lit*)(*this); + const Lit* d = (const Lit*)other; + + for (int i = 0; i < size(); i++) { + // search for c[i] or ~c[i] + for (int j = 0; j < other.size(); j++) + if (c[i] == d[j]) + goto ok; + else if (ret == lit_Undef && c[i] == ~d[j]){ + ret = c[i]; + goto ok; + } + + // did not find it + return lit_Error; + ok:; + } + + return ret; +} + + +inline void Clause::strengthen(Lit p) +{ + remove(*this, p); + calcAbstraction(); +} + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +#endif /* CVC4_MiniSat_SolverTypes_h */ diff --git a/src/sat/minisat/mtl/Alg.h b/src/sat/minisat/mtl/Alg.h new file mode 100644 index 000000000..a4ca4403b --- /dev/null +++ b/src/sat/minisat/mtl/Alg.h @@ -0,0 +1,63 @@ +/*******************************************************************************************[Alg.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_Alg_h +#define CVC4_MiniSat_Alg_h + +namespace CVC4 { +namespace MiniSat { + +//================================================================================================= +// Useful functions on vectors + + +#if 1 +template<class V, class T> +static inline void remove(V& ts, const T& t) +{ + int j = 0; + for (; j < ts.size() && ts[j] != t; j++); + assert(j < ts.size()); + for (; j < ts.size()-1; j++) ts[j] = ts[j+1]; + ts.pop(); +} +#else +template<class V, class T> +static inline void remove(V& ts, const T& t) +{ + int j = 0; + for (; j < ts.size() && ts[j] != t; j++); + assert(j < ts.size()); + ts[j] = ts.last(); + ts.pop(); +} +#endif + +template<class V, class T> +static inline bool find(V& ts, const T& t) +{ + int j = 0; + for (; j < ts.size() && ts[j] != t; j++); + return j < ts.size(); +} + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +#endif /* CVC4_MiniSat_Alg_h */ diff --git a/src/sat/minisat/mtl/BasicHeap.h b/src/sat/minisat/mtl/BasicHeap.h new file mode 100644 index 000000000..b22a35ada --- /dev/null +++ b/src/sat/minisat/mtl/BasicHeap.h @@ -0,0 +1,105 @@ +/******************************************************************************************[Heap.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_BasicHeap_h +#define CVC4_MiniSat_BasicHeap_h + +#include "Vec.h" + +namespace CVC4 { +namespace MiniSat { + +//================================================================================================= +// A heap implementation with support for decrease/increase key. + + +template<class Comp> +class BasicHeap { + Comp lt; + vec<int> heap; // heap of ints + + // Index "traversal" functions + static inline int left (int i) { return i*2+1; } + static inline int right (int i) { return (i+1)*2; } + static inline int parent(int i) { return (i-1) >> 1; } + + inline void percolateUp(int i) + { + int x = heap[i]; + while (i != 0 && lt(x, heap[parent(i)])){ + heap[i] = heap[parent(i)]; + i = parent(i); + } + heap [i] = x; + } + + + inline void percolateDown(int i) + { + int x = heap[i]; + while (left(i) < heap.size()){ + int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i); + if (!lt(heap[child], x)) break; + heap[i] = heap[child]; + i = child; + } + heap[i] = x; + } + + + bool heapProperty(int i) { + return i >= heap.size() + || ((i == 0 || !lt(heap[i], heap[parent(i)])) && heapProperty(left(i)) && heapProperty(right(i))); } + + + public: + BasicHeap(const C& c) : comp(c) { } + + int size () const { return heap.size(); } + bool empty () const { return heap.size() == 0; } + int operator[](int index) const { return heap[index+1]; } + void clear (bool dealloc = false) { heap.clear(dealloc); } + void insert (int n) { heap.push(n); percolateUp(heap.size()-1); } + + + int removeMin() { + int r = heap[0]; + heap[0] = heap.last(); + heap.pop(); + if (heap.size() > 1) percolateDown(0); + return r; + } + + + // DEBUG: consistency checking + bool heapProperty() { + return heapProperty(1); } + + + // COMPAT: should be removed + int getmin () { return removeMin(); } +}; + + +//================================================================================================= + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +#endif /* CVC4_MiniSat_BasicHeap_h */ diff --git a/src/sat/minisat/mtl/BoxedVec.h b/src/sat/minisat/mtl/BoxedVec.h new file mode 100644 index 000000000..7c5b10e4c --- /dev/null +++ b/src/sat/minisat/mtl/BoxedVec.h @@ -0,0 +1,152 @@ +/*******************************************************************************************[Vec.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_BoxedVec_h +#define CVC4_MiniSat_BoxedVec_h + +#include <cstdlib> +#include <cassert> +#include <new> + +namespace CVC4 { +namespace MiniSat { + +//================================================================================================= +// Automatically resizable arrays +// +// NOTE! Don't use this vector on datatypes that cannot be re-located in memory (with realloc) + +template<class T> +class bvec { + + static inline int imin(int x, int y) { + int mask = (x-y) >> (sizeof(int)*8-1); + return (x&mask) + (y&(~mask)); } + + static inline int imax(int x, int y) { + int mask = (y-x) >> (sizeof(int)*8-1); + return (x&mask) + (y&(~mask)); } + + struct Vec_t { + int sz; + int cap; + T data[0]; + + static Vec_t* alloc(Vec_t* x, int size){ + x = (Vec_t*)realloc((void*)x, sizeof(Vec_t) + sizeof(T)*size); + x->cap = size; + return x; + } + + }; + + Vec_t* ref; + + static const int init_size = 2; + static int nextSize (int current) { return (current * 3 + 1) >> 1; } + static int fitSize (int needed) { int x; for (x = init_size; needed > x; x = nextSize(x)); return x; } + + void fill (int size) { + assert(ref != NULL); + for (T* i = ref->data; i < ref->data + size; i++) + new (i) T(); + } + + void fill (int size, const T& pad) { + assert(ref != NULL); + for (T* i = ref->data; i < ref->data + size; i++) + new (i) T(pad); + } + + // Don't allow copying (error prone): + altvec<T>& operator = (altvec<T>& other) { assert(0); } + altvec (altvec<T>& other) { assert(0); } + +public: + void clear (bool dealloc = false) { + if (ref != NULL){ + for (int i = 0; i < ref->sz; i++) + (*ref).data[i].~T(); + + if (dealloc) { + free(ref); ref = NULL; + }else + ref->sz = 0; + } + } + + // Constructors: + altvec(void) : ref (NULL) { } + altvec(int size) : ref (Vec_t::alloc(NULL, fitSize(size))) { fill(size); ref->sz = size; } + altvec(int size, const T& pad) : ref (Vec_t::alloc(NULL, fitSize(size))) { fill(size, pad); ref->sz = size; } + ~altvec(void) { clear(true); } + + // Ownership of underlying array: + operator T* (void) { return ref->data; } // (unsafe but convenient) + operator const T* (void) const { return ref->data; } + + // Size operations: + int size (void) const { return ref != NULL ? ref->sz : 0; } + + void pop (void) { assert(ref != NULL && ref->sz > 0); int last = --ref->sz; ref->data[last].~T(); } + void push (const T& elem) { + int size = ref != NULL ? ref->sz : 0; + int cap = ref != NULL ? ref->cap : 0; + if (size == cap){ + cap = cap != 0 ? nextSize(cap) : init_size; + ref = Vec_t::alloc(ref, cap); + } + //new (&ref->data[size]) T(elem); + ref->data[size] = elem; + ref->sz = size+1; + } + + void push () { + int size = ref != NULL ? ref->sz : 0; + int cap = ref != NULL ? ref->cap : 0; + if (size == cap){ + cap = cap != 0 ? nextSize(cap) : init_size; + ref = Vec_t::alloc(ref, cap); + } + new (&ref->data[size]) T(); + ref->sz = size+1; + } + + void shrink (int nelems) { for (int i = 0; i < nelems; i++) pop(); } + void shrink_(int nelems) { for (int i = 0; i < nelems; i++) pop(); } + void growTo (int size) { while (this->size() < size) push(); } + void growTo (int size, const T& pad) { while (this->size() < size) push(pad); } + void capacity (int size) { growTo(size); } + + const T& last (void) const { return ref->data[ref->sz-1]; } + T& last (void) { return ref->data[ref->sz-1]; } + + // Vector interface: + const T& operator [] (int index) const { return ref->data[index]; } + T& operator [] (int index) { return ref->data[index]; } + + void copyTo(altvec<T>& copy) const { copy.clear(); for (int i = 0; i < size(); i++) copy.push(ref->data[i]); } + void moveTo(altvec<T>& dest) { dest.clear(true); dest.ref = ref; ref = NULL; } + +}; + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +#endif /* CVC4_MiniSat_BoxedVec_h */ diff --git a/src/sat/minisat/mtl/Heap.h b/src/sat/minisat/mtl/Heap.h new file mode 100644 index 000000000..84234705c --- /dev/null +++ b/src/sat/minisat/mtl/Heap.h @@ -0,0 +1,174 @@ +/******************************************************************************************[Heap.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_Heap_h +#define CVC4_MiniSat_Heap_h + +#include "Vec.h" + +namespace CVC4 { +namespace MiniSat { + +//================================================================================================= +// A heap implementation with support for decrease/increase key. + + +template<class Comp> +class Heap { + Comp lt; + vec<int> heap; // heap of ints + vec<int> indices; // int -> index in heap + + // Index "traversal" functions + static inline int left (int i) { return i*2+1; } + static inline int right (int i) { return (i+1)*2; } + static inline int parent(int i) { return (i-1) >> 1; } + + + inline void percolateUp(int i) + { + int x = heap[i]; + while (i != 0 && lt(x, heap[parent(i)])){ + heap[i] = heap[parent(i)]; + indices[heap[i]] = i; + i = parent(i); + } + heap [i] = x; + indices[x] = i; + } + + + inline void percolateDown(int i) + { + int x = heap[i]; + while (left(i) < heap.size()){ + int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i); + if (!lt(heap[child], x)) break; + heap[i] = heap[child]; + indices[heap[i]] = i; + i = child; + } + heap [i] = x; + indices[x] = i; + } + + + bool heapProperty (int i) const { + return i >= heap.size() + || ((i == 0 || !lt(heap[i], heap[parent(i)])) && heapProperty(left(i)) && heapProperty(right(i))); } + + + public: + Heap(const Comp& c) : lt(c) { } + + int size () const { return heap.size(); } + bool empty () const { return heap.size() == 0; } + bool inHeap (int n) const { return n < indices.size() && indices[n] >= 0; } + int operator[](int index) const { assert(index < heap.size()); return heap[index]; } + + void decrease (int n) { assert(inHeap(n)); percolateUp(indices[n]); } + + // RENAME WHEN THE DEPRECATED INCREASE IS REMOVED. + void increase_ (int n) { assert(inHeap(n)); percolateDown(indices[n]); } + + + void insert(int n) + { + indices.growTo(n+1, -1); + assert(!inHeap(n)); + + indices[n] = heap.size(); + heap.push(n); + percolateUp(indices[n]); + } + + + int removeMin() + { + int x = heap[0]; + heap[0] = heap.last(); + indices[heap[0]] = 0; + indices[x] = -1; + heap.pop(); + if (heap.size() > 1) percolateDown(0); + return x; + } + + + void clear(bool dealloc = false) + { + for (int i = 0; i < heap.size(); i++) + indices[heap[i]] = -1; +#ifdef NDEBUG + for (int i = 0; i < indices.size(); i++) + assert(indices[i] == -1); +#endif + heap.clear(dealloc); + } + + + // Fool proof variant of insert/decrease/increase + void update (int n) + { + if (!inHeap(n)) + insert(n); + else { + percolateUp(indices[n]); + percolateDown(indices[n]); + } + } + + + // Delete elements from the heap using a given filter function (-object). + // *** this could probaly be replaced with a more general "buildHeap(vec<int>&)" method *** + template <class F> + void filter(const F& filt) { + int i,j; + for (i = j = 0; i < heap.size(); i++) + if (filt(heap[i])){ + heap[j] = heap[i]; + indices[heap[i]] = j++; + }else + indices[heap[i]] = -1; + + heap.shrink(i - j); + for (int i = heap.size() / 2 - 1; i >= 0; i--) + percolateDown(i); + + assert(heapProperty()); + } + + + // DEBUG: consistency checking + bool heapProperty() const { + return heapProperty(1); } + + + // COMPAT: should be removed + void setBounds (int n) { } + void increase (int n) { decrease(n); } + int getmin () { return removeMin(); } + +}; + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +//================================================================================================= +#endif /* CVC4_MiniSat_Heap_h */ diff --git a/src/sat/minisat/mtl/Map.h b/src/sat/minisat/mtl/Map.h new file mode 100644 index 000000000..f69fca6d5 --- /dev/null +++ b/src/sat/minisat/mtl/Map.h @@ -0,0 +1,124 @@ +/*******************************************************************************************[Map.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_Map_h +#define CVC4_MiniSat_Map_h + +#include <stdint.h> + +#include "Vec.h" + +namespace CVC4 { +namespace MiniSat { + +//================================================================================================= +// Default hash/equals functions +// + +template<class K> struct Hash { uint32_t operator()(const K& k) const { return hash(k); } }; +template<class K> struct Equal { bool operator()(const K& k1, const K& k2) const { return k1 == k2; } }; + +template<class K> struct DeepHash { uint32_t operator()(const K* k) const { return hash(*k); } }; +template<class K> struct DeepEqual { bool operator()(const K* k1, const K* k2) const { return *k1 == *k2; } }; + +//================================================================================================= +// Some primes +// + +static const int nprimes = 25; +static const int primes [nprimes] = { 31, 73, 151, 313, 643, 1291, 2593, 5233, 10501, 21013, 42073, 84181, 168451, 337219, 674701, 1349473, 2699299, 5398891, 10798093, 21596719, 43193641, 86387383, 172775299, 345550609, 691101253 }; + +//================================================================================================= +// Hash table implementation of Maps +// + +template<class K, class D, class H = Hash<K>, class E = Equal<K> > +class Map { + struct Pair { K key; D data; }; + + H hash; + E equals; + + vec<Pair>* table; + int cap; + int size; + + // Don't allow copying (error prone): + Map<K,D,H,E>& operator = (Map<K,D,H,E>& other) { assert(0); } + Map (Map<K,D,H,E>& other) { assert(0); } + + int32_t index (const K& k) const { return hash(k) % cap; } + void _insert (const K& k, const D& d) { table[index(k)].push(); table[index(k)].last().key = k; table[index(k)].last().data = d; } + void rehash () { + const vec<Pair>* old = table; + + int newsize = primes[0]; + for (int i = 1; newsize <= cap && i < nprimes; i++) + newsize = primes[i]; + + table = new vec<Pair>[newsize]; + + for (int i = 0; i < cap; i++){ + for (int j = 0; j < old[i].size(); j++){ + _insert(old[i][j].key, old[i][j].data); }} + + delete [] old; + + cap = newsize; + } + + + public: + + Map () : table(NULL), cap(0), size(0) {} + Map (const H& h, const E& e) : Map(), hash(h), equals(e) {} + ~Map () { delete [] table; } + + void insert (const K& k, const D& d) { if (size+1 > cap / 2) rehash(); _insert(k, d); size++; } + bool peek (const K& k, D& d) { + if (size == 0) return false; + const vec<Pair>& ps = table[index(k)]; + for (int i = 0; i < ps.size(); i++) + if (equals(ps[i].key, k)){ + d = ps[i].data; + return true; } + return false; + } + + void remove (const K& k) { + assert(table != NULL); + vec<Pair>& ps = table[index(k)]; + int j = 0; + for (; j < ps.size() && !equals(ps[j].key, k); j++); + assert(j < ps.size()); + ps[j] = ps.last(); + ps.pop(); + } + + void clear () { + cap = size = 0; + delete [] table; + table = NULL; + } +}; + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +#endif /* CVC4_MiniSat_Map_h */ diff --git a/src/sat/minisat/mtl/Queue.h b/src/sat/minisat/mtl/Queue.h new file mode 100644 index 000000000..e4e7e2159 --- /dev/null +++ b/src/sat/minisat/mtl/Queue.h @@ -0,0 +1,89 @@ +/*****************************************************************************************[Queue.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_Queue_h +#define CVC4_MiniSat_Queue_h + +#include "Vec.h" + +namespace CVC4 { +namespace MiniSat { + +//================================================================================================= + + +template <class T> +class Queue { + vec<T> elems; + int first; + +public: + Queue(void) : first(0) { } + + void insert(T x) { elems.push(x); } + T peek () const { return elems[first]; } + void pop () { first++; } + + void clear(bool dealloc = false) { elems.clear(dealloc); first = 0; } + int size(void) { return elems.size() - first; } + + //bool has(T x) { for (int i = first; i < elems.size(); i++) if (elems[i] == x) return true; return false; } + + const T& operator [] (int index) const { return elems[first + index]; } + +}; + +//template<class T> +//class Queue { +// vec<T> buf; +// int first; +// int end; +// +//public: +// typedef T Key; +// +// Queue() : buf(1), first(0), end(0) {} +// +// void clear () { buf.shrinkTo(1); first = end = 0; } +// int size () { return (end >= first) ? end - first : end - first + buf.size(); } +// +// T peek () { assert(first != end); return buf[first]; } +// void pop () { assert(first != end); first++; if (first == buf.size()) first = 0; } +// void insert(T elem) { // INVARIANT: buf[end] is always unused +// buf[end++] = elem; +// if (end == buf.size()) end = 0; +// if (first == end){ // Resize: +// vec<T> tmp((buf.size()*3 + 1) >> 1); +// //**/printf("queue alloc: %d elems (%.1f MB)\n", tmp.size(), tmp.size() * sizeof(T) / 1000000.0); +// int i = 0; +// for (int j = first; j < buf.size(); j++) tmp[i++] = buf[j]; +// for (int j = 0 ; j < end ; j++) tmp[i++] = buf[j]; +// first = 0; +// end = buf.size(); +// tmp.moveTo(buf); +// } +// } +//}; + +//================================================================================================= + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +#endif /* CVC4_MiniSat_Queue_h */ diff --git a/src/sat/minisat/mtl/Sort.h b/src/sat/minisat/mtl/Sort.h new file mode 100644 index 000000000..df5261a06 --- /dev/null +++ b/src/sat/minisat/mtl/Sort.h @@ -0,0 +1,100 @@ +/******************************************************************************************[Sort.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_Sort_h +#define CVC4_MiniSat_Sort_h + +#include "Vec.h" + +namespace CVC4 { +namespace MiniSat { + +//================================================================================================= +// Some sorting algorithms for vec's + + +template<class T> +struct LessThan_default { + bool operator () (T x, T y) { return x < y; } +}; + + +template <class T, class LessThan> +void selectionSort(T* array, int size, LessThan lt) +{ + int i, j, best_i; + T tmp; + + for (i = 0; i < size-1; i++){ + best_i = i; + for (j = i+1; j < size; j++){ + if (lt(array[j], array[best_i])) + best_i = j; + } + tmp = array[i]; array[i] = array[best_i]; array[best_i] = tmp; + } +} +template <class T> static inline void selectionSort(T* array, int size) { + selectionSort(array, size, LessThan_default<T>()); } + +template <class T, class LessThan> +void sort(T* array, int size, LessThan lt) +{ + if (size <= 15) + selectionSort(array, size, lt); + + else{ + T pivot = array[size / 2]; + T tmp; + int i = -1; + int j = size; + + for(;;){ + do i++; while(lt(array[i], pivot)); + do j--; while(lt(pivot, array[j])); + + if (i >= j) break; + + tmp = array[i]; array[i] = array[j]; array[j] = tmp; + } + + sort(array , i , lt); + sort(&array[i], size-i, lt); + } +} +template <class T> static inline void sort(T* array, int size) { + sort(array, size, LessThan_default<T>()); } + + +//================================================================================================= +// For 'vec's: + + +template <class T, class LessThan> void sort(vec<T>& v, LessThan lt) { + sort((T*)v, v.size(), lt); } +template <class T> void sort(vec<T>& v) { + sort(v, LessThan_default<T>()); } + + +//================================================================================================= + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +#endif /* CVC4_MiniSat_Sort_h */ diff --git a/src/sat/minisat/mtl/Vec.h b/src/sat/minisat/mtl/Vec.h new file mode 100644 index 000000000..1a07cc334 --- /dev/null +++ b/src/sat/minisat/mtl/Vec.h @@ -0,0 +1,138 @@ +/*******************************************************************************************[Vec.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_Vec_h +#define CVC4_MiniSat_Vec_h + +#include <cstdlib> +#include <cassert> +#include <new> + +namespace CVC4 { +namespace MiniSat { + +//================================================================================================= +// Automatically resizable arrays +// +// NOTE! Don't use this vector on datatypes that cannot be re-located in memory (with realloc) + +template<class T> +class vec { + T* data; + int sz; + int cap; + + void init(int size, const T& pad); + void grow(int min_cap); + + // Don't allow copying (error prone): + vec<T>& operator = (vec<T>& other) { assert(0); return *this; } + vec (vec<T>& other) { assert(0); } + + static inline int imin(int x, int y) { + int mask = (x-y) >> (sizeof(int)*8-1); + return (x&mask) + (y&(~mask)); } + + static inline int imax(int x, int y) { + int mask = (y-x) >> (sizeof(int)*8-1); + return (x&mask) + (y&(~mask)); } + +public: + // Types: + typedef int Key; + typedef T Datum; + + // Constructors: + vec(void) : data(NULL) , sz(0) , cap(0) { } + vec(int size) : data(NULL) , sz(0) , cap(0) { growTo(size); } + vec(int size, const T& pad) : data(NULL) , sz(0) , cap(0) { growTo(size, pad); } + vec(T* array, int size) : data(array), sz(size), cap(size) { } // (takes ownership of array -- will be deallocated with 'free()') + ~vec(void) { clear(true); } + + // Ownership of underlying array: + T* release (void) { T* ret = data; data = NULL; sz = 0; cap = 0; return ret; } + operator T* (void) { return data; } // (unsafe but convenient) + operator const T* (void) const { return data; } + + // Size operations: + int size (void) const { return sz; } + void shrink (int nelems) { assert(nelems <= sz); for (int i = 0; i < nelems; i++) sz--, data[sz].~T(); } + void shrink_(int nelems) { assert(nelems <= sz); sz -= nelems; } + void pop (void) { sz--, data[sz].~T(); } + void growTo (int size); + void growTo (int size, const T& pad); + void clear (bool dealloc = false); + void capacity (int size) { grow(size); } + + // Stack interface: +#if 1 + void push (void) { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } new (&data[sz]) T(); sz++; } + //void push (const T& elem) { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } new (&data[sz]) T(elem); sz++; } + void push (const T& elem) { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } data[sz++] = elem; } + void push_ (const T& elem) { assert(sz < cap); data[sz++] = elem; } +#else + void push (void) { if (sz == cap) grow(sz+1); new (&data[sz]) T() ; sz++; } + void push (const T& elem) { if (sz == cap) grow(sz+1); new (&data[sz]) T(elem); sz++; } +#endif + + const T& last (void) const { return data[sz-1]; } + T& last (void) { return data[sz-1]; } + + // Vector interface: + const T& operator [] (int index) const { return data[index]; } + T& operator [] (int index) { return data[index]; } + + + // Duplicatation (preferred instead): + void copyTo(vec<T>& copy) const { copy.clear(); copy.growTo(sz); for (int i = 0; i < sz; i++) new (©[i]) T(data[i]); } + void moveTo(vec<T>& dest) { dest.clear(true); dest.data = data; dest.sz = sz; dest.cap = cap; data = NULL; sz = 0; cap = 0; } +}; + +template<class T> +void vec<T>::grow(int min_cap) { + if (min_cap <= cap) return; + if (cap == 0) cap = (min_cap >= 2) ? min_cap : 2; + else do cap = (cap*3+1) >> 1; while (cap < min_cap); + data = (T*)realloc(data, cap * sizeof(T)); } + +template<class T> +void vec<T>::growTo(int size, const T& pad) { + if (sz >= size) return; + grow(size); + for (int i = sz; i < size; i++) new (&data[i]) T(pad); + sz = size; } + +template<class T> +void vec<T>::growTo(int size) { + if (sz >= size) return; + grow(size); + for (int i = sz; i < size; i++) new (&data[i]) T(); + sz = size; } + +template<class T> +void vec<T>::clear(bool dealloc) { + if (data != NULL){ + for (int i = 0; i < sz; i++) data[i].~T(); + sz = 0; + if (dealloc) free(data), data = NULL, cap = 0; } } + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +#endif /* CVC4_MiniSat_Vec_h */ diff --git a/src/sat/minisat/mtl/template.mk b/src/sat/minisat/mtl/template.mk new file mode 100644 index 000000000..15f023fb3 --- /dev/null +++ b/src/sat/minisat/mtl/template.mk @@ -0,0 +1,90 @@ +## +## Template makefile for Standard, Profile, Debug, Release, and Release-static versions +## +## eg: "make rs" for a statically linked release version. +## "make d" for a debug version (no optimizations). +## "make" for the standard version (optimized, but with debug information and assertions active) + +CSRCS ?= $(wildcard *.C) +CHDRS ?= $(wildcard *.h) +COBJS ?= $(addsuffix .o, $(basename $(CSRCS))) + +PCOBJS = $(addsuffix p, $(COBJS)) +DCOBJS = $(addsuffix d, $(COBJS)) +RCOBJS = $(addsuffix r, $(COBJS)) + +EXEC ?= $(notdir $(shell pwd)) +LIB ?= $(EXEC) + +CXX ?= g++ +CFLAGS ?= -Wall +LFLAGS ?= -Wall + +COPTIMIZE ?= -O3 + +.PHONY : s p d r rs lib libd clean + +s: $(EXEC) +p: $(EXEC)_profile +d: $(EXEC)_debug +r: $(EXEC)_release +rs: $(EXEC)_static +lib: lib$(LIB).a +libd: lib$(LIB)d.a + +## Compile options +%.o: CFLAGS +=$(COPTIMIZE) -ggdb -D DEBUG +%.op: CFLAGS +=$(COPTIMIZE) -pg -ggdb -D NDEBUG +%.od: CFLAGS +=-O0 -ggdb -D DEBUG # -D INVARIANTS +%.or: CFLAGS +=$(COPTIMIZE) -D NDEBUG + +## Link options +$(EXEC): LFLAGS := -ggdb $(LFLAGS) +$(EXEC)_profile: LFLAGS := -ggdb -pg $(LFLAGS) +$(EXEC)_debug: LFLAGS := -ggdb $(LFLAGS) +$(EXEC)_release: LFLAGS := $(LFLAGS) +$(EXEC)_static: LFLAGS := --static $(LFLAGS) + +## Dependencies +$(EXEC): $(COBJS) +$(EXEC)_profile: $(PCOBJS) +$(EXEC)_debug: $(DCOBJS) +$(EXEC)_release: $(RCOBJS) +$(EXEC)_static: $(RCOBJS) + +lib$(LIB).a: $(filter-out Main.or, $(RCOBJS)) +lib$(LIB)d.a: $(filter-out Main.od, $(DCOBJS)) + + +## Build rule +%.o %.op %.od %.or: %.C + @echo Compiling: "$@ ( $< )" + @$(CXX) $(CFLAGS) -c -o $@ $< + +## Linking rules (standard/profile/debug/release) +$(EXEC) $(EXEC)_profile $(EXEC)_debug $(EXEC)_release $(EXEC)_static: + @echo Linking: "$@ ( $^ )" + @$(CXX) $^ $(LFLAGS) -o $@ + +## Library rule +lib$(LIB).a lib$(LIB)d.a: + @echo Library: "$@ ( $^ )" + @rm -f $@ + @ar cq $@ $^ + +## Clean rule +clean: + @rm -f $(EXEC) $(EXEC)_profile $(EXEC)_debug $(EXEC)_release $(EXEC)_static \ + $(COBJS) $(PCOBJS) $(DCOBJS) $(RCOBJS) *.core depend.mak lib$(LIB).a lib$(LIB)d.a + +## Make dependencies +depend.mk: $(CSRCS) $(CHDRS) + @echo Making dependencies ... + @$(CXX) $(CFLAGS) -MM $(CSRCS) > depend.mk + @cp depend.mk /tmp/depend.mk.tmp + @sed "s/o:/op:/" /tmp/depend.mk.tmp >> depend.mk + @sed "s/o:/od:/" /tmp/depend.mk.tmp >> depend.mk + @sed "s/o:/or:/" /tmp/depend.mk.tmp >> depend.mk + @rm /tmp/depend.mk.tmp + +-include depend.mk diff --git a/src/sat/minisat/simp/Main.C b/src/sat/minisat/simp/Main.C new file mode 100644 index 000000000..b6d194631 --- /dev/null +++ b/src/sat/minisat/simp/Main.C @@ -0,0 +1,415 @@ +/******************************************************************************************[Main.C] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#include <ctime> +#include <cstring> +#include <stdint.h> +#include <errno.h> + +#include <signal.h> +#include <zlib.h> + +#include "SimpSolver.h" + +/*************************************************************************************/ +#ifdef _MSC_VER +#include <ctime> + +static inline double cpuTime(void) { + return (double)clock() / CLOCKS_PER_SEC; } +#else + +#include <sys/time.h> +#include <sys/resource.h> +#include <unistd.h> + +static inline double cpuTime(void) { + struct rusage ru; + getrusage(RUSAGE_SELF, &ru); + return (double)ru.ru_utime.tv_sec + (double)ru.ru_utime.tv_usec / 1000000; } +#endif + + +#if defined(__linux__) +static inline int memReadStat(int field) +{ + char name[256]; + pid_t pid = getpid(); + sprintf(name, "/proc/%d/statm", pid); + FILE* in = fopen(name, "rb"); + if (in == NULL) return 0; + int value; + for (; field >= 0; field--) + fscanf(in, "%d", &value); + fclose(in); + return value; +} +static inline uint64_t memUsed() { return (uint64_t)memReadStat(0) * (uint64_t)getpagesize(); } + + +#elif defined(__FreeBSD__) +static inline uint64_t memUsed(void) { + struct rusage ru; + getrusage(RUSAGE_SELF, &ru); + return ru.ru_maxrss*1024; } + + +#else +static inline uint64_t memUsed() { return 0; } +#endif + +#if defined(__linux__) +#include <fpu_control.h> +#endif + + +//================================================================================================= +// DIMACS Parser: + +#define CHUNK_LIMIT 1048576 + +class StreamBuffer { + gzFile in; + char buf[CHUNK_LIMIT]; + int pos; + int size; + + void assureLookahead() { + if (pos >= size) { + pos = 0; + size = gzread(in, buf, sizeof(buf)); } } + +public: + StreamBuffer(gzFile i) : in(i), pos(0), size(0) { + assureLookahead(); } + + int operator * () { return (pos >= size) ? EOF : buf[pos]; } + void operator ++ () { pos++; assureLookahead(); } +}; + +//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + +template<class B> +static void skipWhitespace(B& in) { + while ((*in >= 9 && *in <= 13) || *in == 32) + ++in; } + +template<class B> +static void skipLine(B& in) { + for (;;){ + if (*in == EOF || *in == '\0') return; + if (*in == '\n') { ++in; return; } + ++in; } } + +template<class B> +static int parseInt(B& in) { + int val = 0; + bool neg = false; + skipWhitespace(in); + if (*in == '-') neg = true, ++in; + else if (*in == '+') ++in; + if (*in < '0' || *in > '9') reportf("PARSE ERROR! Unexpected char: %c\n", *in), exit(3); + while (*in >= '0' && *in <= '9') + val = val*10 + (*in - '0'), + ++in; + return neg ? -val : val; } + +template<class B> +static void readClause(B& in, SimpSolver& S, vec<Lit>& lits) { + int parsed_lit, var; + lits.clear(); + for (;;){ + parsed_lit = parseInt(in); + if (parsed_lit == 0) break; + var = abs(parsed_lit)-1; + while (var >= S.nVars()) S.newVar(); + lits.push( (parsed_lit > 0) ? Lit(var) : ~Lit(var) ); + } +} + +template<class B> +static bool match(B& in, char* str) { + for (; *str != 0; ++str, ++in) + if (*str != *in) + return false; + return true; +} + + +template<class B> +static void parse_DIMACS_main(B& in, SimpSolver& S) { + vec<Lit> lits; + for (;;){ + skipWhitespace(in); + if (*in == EOF) break; + else if (*in == 'p'){ + if (match(in, "p cnf")){ + int vars = parseInt(in); + int clauses = parseInt(in); + reportf("| Number of variables: %-12d |\n", vars); + reportf("| Number of clauses: %-12d |\n", clauses); + + // SATRACE'06 hack + if (clauses > 4000000) + S.eliminate(true); + }else{ + reportf("PARSE ERROR! Unexpected char: %c\n", *in), exit(3); + } + } else if (*in == 'c' || *in == 'p') + skipLine(in); + else{ + readClause(in, S, lits); + S.addClause(lits); } + } +} + +// Inserts problem into solver. +// +static void parse_DIMACS(gzFile input_stream, SimpSolver& S) { + StreamBuffer in(input_stream); + parse_DIMACS_main(in, S); } + + +//================================================================================================= + + +void printStats(Solver& S) +{ + double cpu_time = cpuTime(); + uint64_t mem_used = memUsed(); + reportf("restarts : %lld\n", S.starts); + reportf("conflicts : %-12lld (%.0f /sec)\n", S.conflicts , S.conflicts /cpu_time); + reportf("decisions : %-12lld (%4.2f %% random) (%.0f /sec)\n", S.decisions, (float)S.rnd_decisions*100 / (float)S.decisions, S.decisions /cpu_time); + reportf("propagations : %-12lld (%.0f /sec)\n", S.propagations, S.propagations/cpu_time); + reportf("conflict literals : %-12lld (%4.2f %% deleted)\n", S.tot_literals, (S.max_literals - S.tot_literals)*100 / (double)S.max_literals); + if (mem_used != 0) reportf("Memory used : %.2f MB\n", mem_used / 1048576.0); + reportf("CPU time : %g s\n", cpu_time); +} + +SimpSolver* solver; +static void SIGINT_handler(int signum) { + reportf("\n"); reportf("*** INTERRUPTED ***\n"); + printStats(*solver); + reportf("\n"); reportf("*** INTERRUPTED ***\n"); + exit(1); } + + +//================================================================================================= +// Main: + +void printUsage(char** argv) +{ + reportf("USAGE: %s [options] <input-file> <result-output-file>\n\n where input may be either in plain or gzipped DIMACS.\n\n", argv[0]); + reportf("OPTIONS:\n\n"); + reportf(" -pre = {none,once}\n"); + reportf(" -asymm\n"); + reportf(" -rcheck\n"); + reportf(" -grow = <num> [ >0 ]\n"); + reportf(" -polarity-mode = {true,false,rnd}\n"); + reportf(" -decay = <num> [ 0 - 1 ]\n"); + reportf(" -rnd-freq = <num> [ 0 - 1 ]\n"); + reportf(" -dimacs = <output-file>\n"); + reportf(" -verbosity = {0,1,2}\n"); + reportf("\n"); +} + +typedef enum { pre_none, pre_once, pre_repeat } preprocessMode; + +const char* hasPrefix(const char* str, const char* prefix) +{ + int len = strlen(prefix); + if (strncmp(str, prefix, len) == 0) + return str + len; + else + return NULL; +} + + +int main(int argc, char** argv) +{ + reportf("This is MiniSat 2.0 beta\n"); +#if defined(__linux__) + fpu_control_t oldcw, newcw; + _FPU_GETCW(oldcw); newcw = (oldcw & ~_FPU_EXTENDED) | _FPU_DOUBLE; _FPU_SETCW(newcw); + reportf("WARNING: for repeatability, setting FPU to use double precision\n"); +#endif + preprocessMode pre = pre_once; + const char* dimacs = NULL; + const char* freeze = NULL; + SimpSolver S; + S.verbosity = 1; + + // This just grew and grew, and I didn't have time to do sensible argument parsing yet :) + // + int i, j; + const char* value; + for (i = j = 0; i < argc; i++){ + if ((value = hasPrefix(argv[i], "-polarity-mode="))){ + if (strcmp(value, "true") == 0) + S.polarity_mode = Solver::polarity_true; + else if (strcmp(value, "false") == 0) + S.polarity_mode = Solver::polarity_false; + else if (strcmp(value, "rnd") == 0) + S.polarity_mode = Solver::polarity_rnd; + else{ + reportf("ERROR! unknown polarity-mode %s\n", value); + exit(0); } + + }else if ((value = hasPrefix(argv[i], "-rnd-freq="))){ + double rnd; + if (sscanf(value, "%lf", &rnd) <= 0 || rnd < 0 || rnd > 1){ + reportf("ERROR! illegal rnd-freq constant %s\n", value); + exit(0); } + S.random_var_freq = rnd; + + }else if ((value = hasPrefix(argv[i], "-decay="))){ + double decay; + if (sscanf(value, "%lf", &decay) <= 0 || decay <= 0 || decay > 1){ + reportf("ERROR! illegal decay constant %s\n", value); + exit(0); } + S.var_decay = 1 / decay; + + }else if ((value = hasPrefix(argv[i], "-verbosity="))){ + int verbosity = (int)strtol(value, NULL, 10); + if (verbosity == 0 && errno == EINVAL){ + reportf("ERROR! illegal verbosity level %s\n", value); + exit(0); } + S.verbosity = verbosity; + + }else if ((value = hasPrefix(argv[i], "-pre="))){ + if (strcmp(value, "none") == 0) + pre = pre_none; + else if (strcmp(value, "once") == 0) + pre = pre_once; + else if (strcmp(value, "repeat") == 0){ + pre = pre_repeat; + reportf("ERROR! preprocessing mode \"repeat\" is not supported at the moment.\n"); + exit(0); + }else{ + reportf("ERROR! unknown preprocessing mode %s\n", value); + exit(0); } + }else if (strcmp(argv[i], "-asymm") == 0){ + S.asymm_mode = true; + }else if (strcmp(argv[i], "-rcheck") == 0){ + S.redundancy_check = true; + }else if ((value = hasPrefix(argv[i], "-grow="))){ + int grow = (int)strtol(value, NULL, 10); + if (grow == 0 && errno == EINVAL){ + reportf("ERROR! illegal grow constant %s\n", &argv[i][6]); + exit(0); } + S.grow = grow; + }else if ((value = hasPrefix(argv[i], "-dimacs="))){ + dimacs = value; + }else if ((value = hasPrefix(argv[i], "-freeze="))){ + freeze = value; + }else if (strcmp(argv[i], "-h") == 0 || strcmp(argv[i], "-help") == 0){ + printUsage(argv); + exit(0); + }else if (strncmp(argv[i], "-", 1) == 0){ + reportf("ERROR! unknown flag %s\n", argv[i]); + exit(0); + }else + argv[j++] = argv[i]; + } + argc = j; + + double cpu_time = cpuTime(); + + if (pre == pre_none) + S.eliminate(true); + + solver = &S; + signal(SIGINT,SIGINT_handler); + signal(SIGHUP,SIGINT_handler); + + if (argc == 1) + reportf("Reading from standard input... Use '-h' or '--help' for help.\n"); + + gzFile in = (argc == 1) ? gzdopen(0, "rb") : gzopen(argv[1], "rb"); + if (in == NULL) + reportf("ERROR! Could not open file: %s\n", argc == 1 ? "<stdin>" : argv[1]), exit(1); + + reportf("============================[ Problem Statistics ]=============================\n"); + reportf("| |\n"); + + parse_DIMACS(in, S); + gzclose(in); + FILE* res = (argc >= 3) ? fopen(argv[2], "wb") : NULL; + + + double parse_time = cpuTime() - cpu_time; + reportf("| Parsing time: %-12.2f s |\n", parse_time); + + /*HACK: Freeze variables*/ + if (freeze != NULL && pre != pre_none){ + int count = 0; + FILE* in = fopen(freeze, "rb"); + for(;;){ + Var x; + fscanf(in, "%d", &x); + if (x == 0) break; + x--; + + /**/assert(S.n_occ[toInt(Lit(x))] + S.n_occ[toInt(~Lit(x))] != 0); + /**/assert(S.value(x) == l_Undef); + S.setFrozen(x, true); + count++; + } + fclose(in); + reportf("| Frozen vars : %-12.0f |\n", (double)count); + } + /*END*/ + + if (!S.simplify()){ + reportf("Solved by unit propagation\n"); + if (res != NULL) fprintf(res, "UNSAT\n"), fclose(res); + printf("UNSATISFIABLE\n"); + exit(20); + } + + if (dimacs){ + if (pre != pre_none) + S.eliminate(true); + reportf("==============================[ Writing DIMACS ]===============================\n"); + S.toDimacs(dimacs); + printStats(S); + exit(0); + }else{ + bool ret = S.solve(true, true); + printStats(S); + reportf("\n"); + + printf(ret ? "SATISFIABLE\n" : "UNSATISFIABLE\n"); + if (res != NULL){ + if (ret){ + fprintf(res, "SAT\n"); + for (int i = 0; i < S.nVars(); i++) + if (S.model[i] != l_Undef) + fprintf(res, "%s%s%d", (i==0)?"":" ", (S.model[i]==l_True)?"":"-", i+1); + fprintf(res, " 0\n"); + }else + fprintf(res, "UNSAT\n"); + fclose(res); + } +#ifdef NDEBUG + exit(ret ? 10 : 20); // (faster than "return", which will invoke the destructor for 'Solver') +#endif + } + +} diff --git a/src/sat/minisat/simp/Makefile b/src/sat/minisat/simp/Makefile new file mode 100644 index 000000000..a1db4951b --- /dev/null +++ b/src/sat/minisat/simp/Makefile @@ -0,0 +1,11 @@ +MTL = ../mtl +CORE = ../core +CHDRS = $(wildcard *.h) $(wildcard $(MTL)/*.h) +EXEC = minisat +CFLAGS = -I$(MTL) -I$(CORE) -Wall -ffloat-store +LFLAGS = -lz + +CSRCS = $(wildcard *.C) +COBJS = $(addsuffix .o, $(basename $(CSRCS))) $(CORE)/Solver.o + +include ../mtl/template.mk diff --git a/src/sat/minisat/simp/SimpSolver.C b/src/sat/minisat/simp/SimpSolver.C new file mode 100644 index 000000000..14b64b555 --- /dev/null +++ b/src/sat/minisat/simp/SimpSolver.C @@ -0,0 +1,705 @@ +/************************************************************************************[SimpSolver.C] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#include "Sort.h" +#include "SimpSolver.h" + + +//================================================================================================= +// Constructor/Destructor: + +namespace CVC4 { +namespace MiniSat { + +SimpSolver::SimpSolver() : + grow (0) + , asymm_mode (false) + , redundancy_check (false) + , merges (0) + , asymm_lits (0) + , remembered_clauses (0) + , elimorder (1) + , use_simplification (true) + , elim_heap (ElimLt(n_occ)) + , bwdsub_assigns (0) +{ + vec<Lit> dummy(1,lit_Undef); + bwdsub_tmpunit = Clause_new(dummy); + remove_satisfied = false; +} + + +SimpSolver::~SimpSolver() +{ + free(bwdsub_tmpunit); + + // NOTE: elimtable.size() might be lower than nVars() at the moment + for (int i = 0; i < elimtable.size(); i++) + for (int j = 0; j < elimtable[i].eliminated.size(); j++) + free(elimtable[i].eliminated[j]); +} + + +Var SimpSolver::newVar(bool sign, bool dvar) { + Var v = Solver::newVar(sign, dvar); + + if (use_simplification){ + n_occ .push(0); + n_occ .push(0); + occurs .push(); + frozen .push((char)false); + touched .push(0); + elim_heap.insert(v); + elimtable.push(); + } + return v; } + + + +bool SimpSolver::solve(const vec<Lit>& assumps, bool do_simp, bool turn_off_simp) { + vec<Var> extra_frozen; + bool result = true; + + do_simp &= use_simplification; + + if (do_simp){ + // Assumptions must be temporarily frozen to run variable elimination: + for (int i = 0; i < assumps.size(); i++){ + Var v = var(assumps[i]); + + // If an assumption has been eliminated, remember it. + if (isEliminated(v)) + remember(v); + + if (!frozen[v]){ + // Freeze and store. + setFrozen(v, true); + extra_frozen.push(v); + } } + + result = eliminate(turn_off_simp); + } + + if (result) + result = Solver::solve(assumps); + + if (result) { + extendModel(); +#ifndef NDEBUG + verifyModel(); +#endif + } + + if (do_simp) + // Unfreeze the assumptions that were frozen: + for (int i = 0; i < extra_frozen.size(); i++) + setFrozen(extra_frozen[i], false); + + return result; +} + + + +bool SimpSolver::addClause(vec<Lit>& ps) +{ + for (int i = 0; i < ps.size(); i++) + if (isEliminated(var(ps[i]))) + remember(var(ps[i])); + + int nclauses = clauses.size(); + + if (redundancy_check && implied(ps)) + return true; + + if (!Solver::addClause(ps)) + return false; + + if (use_simplification && clauses.size() == nclauses + 1){ + Clause& c = *clauses.last(); + + subsumption_queue.insert(&c); + + for (int i = 0; i < c.size(); i++){ + assert(occurs.size() > var(c[i])); + assert(!find(occurs[var(c[i])], &c)); + + occurs[var(c[i])].push(&c); + n_occ[toInt(c[i])]++; + touched[var(c[i])] = 1; + assert(elimtable[var(c[i])].order == 0); + if (elim_heap.inHeap(var(c[i]))) + elim_heap.increase_(var(c[i])); + } + } + + return true; +} + + +void SimpSolver::removeClause(Clause& c) +{ + assert(!c.learnt()); + + if (use_simplification) + for (int i = 0; i < c.size(); i++){ + n_occ[toInt(c[i])]--; + updateElimHeap(var(c[i])); + } + + detachClause(c); + c.mark(1); +} + + +bool SimpSolver::strengthenClause(Clause& c, Lit l) +{ + assert(decisionLevel() == 0); + assert(c.mark() == 0); + assert(!c.learnt()); + assert(find(watches[toInt(~c[0])], &c)); + assert(find(watches[toInt(~c[1])], &c)); + + // FIX: this is too inefficient but would be nice to have (properly implemented) + // if (!find(subsumption_queue, &c)) + subsumption_queue.insert(&c); + + // If l is watched, delete it from watcher list and watch a new literal + if (c[0] == l || c[1] == l){ + Lit other = c[0] == l ? c[1] : c[0]; + if (c.size() == 2){ + removeClause(c); + c.strengthen(l); + }else{ + c.strengthen(l); + remove(watches[toInt(~l)], &c); + + // Add a watch for the correct literal + watches[toInt(~(c[1] == other ? c[0] : c[1]))].push(&c); + + // !! this version assumes that remove does not change the order !! + //watches[toInt(~c[1])].push(&c); + clauses_literals -= 1; + } + } + else{ + c.strengthen(l); + clauses_literals -= 1; + } + + // if subsumption-indexing is active perform the necessary updates + if (use_simplification){ + remove(occurs[var(l)], &c); + n_occ[toInt(l)]--; + updateElimHeap(var(l)); + } + + return c.size() == 1 ? enqueue(c[0]) && propagate() == NULL : true; +} + + +// Returns FALSE if clause is always satisfied ('out_clause' should not be used). +bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v, vec<Lit>& out_clause) +{ + merges++; + out_clause.clear(); + + bool ps_smallest = _ps.size() < _qs.size(); + const Clause& ps = ps_smallest ? _qs : _ps; + const Clause& qs = ps_smallest ? _ps : _qs; + + for (int i = 0; i < qs.size(); i++){ + if (var(qs[i]) != v){ + for (int j = 0; j < ps.size(); j++) + if (var(ps[j]) == var(qs[i])) + if (ps[j] == ~qs[i]) + return false; + else + goto next; + out_clause.push(qs[i]); + } + next:; + } + + for (int i = 0; i < ps.size(); i++) + if (var(ps[i]) != v) + out_clause.push(ps[i]); + + return true; +} + + +// Returns FALSE if clause is always satisfied. +bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v) +{ + merges++; + + bool ps_smallest = _ps.size() < _qs.size(); + const Clause& ps = ps_smallest ? _qs : _ps; + const Clause& qs = ps_smallest ? _ps : _qs; + const Lit* __ps = (const Lit*)ps; + const Lit* __qs = (const Lit*)qs; + + for (int i = 0; i < qs.size(); i++){ + if (var(__qs[i]) != v){ + for (int j = 0; j < ps.size(); j++) + if (var(__ps[j]) == var(__qs[i])) + if (__ps[j] == ~__qs[i]) + return false; + else + goto next; + } + next:; + } + + return true; +} + + +void SimpSolver::gatherTouchedClauses() +{ + //fprintf(stderr, "Gathering clauses for backwards subsumption\n"); + int ntouched = 0; + for (int i = 0; i < touched.size(); i++) + if (touched[i]){ + const vec<Clause*>& cs = getOccurs(i); + ntouched++; + for (int j = 0; j < cs.size(); j++) + if (cs[j]->mark() == 0){ + subsumption_queue.insert(cs[j]); + cs[j]->mark(2); + } + touched[i] = 0; + } + + //fprintf(stderr, "Touched variables %d of %d yields %d clauses to check\n", ntouched, touched.size(), clauses.size()); + for (int i = 0; i < subsumption_queue.size(); i++) + subsumption_queue[i]->mark(0); +} + + +bool SimpSolver::implied(const vec<Lit>& c) +{ + assert(decisionLevel() == 0); + + trail_lim.push(trail.size()); + for (int i = 0; i < c.size(); i++) + if (value(c[i]) == l_True){ + cancelUntil(0); + return false; + }else if (value(c[i]) != l_False){ + assert(value(c[i]) == l_Undef); + uncheckedEnqueue(~c[i]); + } + + bool result = propagate() != NULL; + cancelUntil(0); + return result; +} + + +// Backward subsumption + backward subsumption resolution +bool SimpSolver::backwardSubsumptionCheck(bool verbose) +{ + int cnt = 0; + int subsumed = 0; + int deleted_literals = 0; + assert(decisionLevel() == 0); + + while (subsumption_queue.size() > 0 || bwdsub_assigns < trail.size()){ + + // Check top-level assignments by creating a dummy clause and placing it in the queue: + if (subsumption_queue.size() == 0 && bwdsub_assigns < trail.size()){ + Lit l = trail[bwdsub_assigns++]; + (*bwdsub_tmpunit)[0] = l; + bwdsub_tmpunit->calcAbstraction(); + assert(bwdsub_tmpunit->mark() == 0); + subsumption_queue.insert(bwdsub_tmpunit); } + + Clause& c = *subsumption_queue.peek(); subsumption_queue.pop(); + + if (c.mark()) continue; + + if (verbose && verbosity >= 2 && cnt++ % 1000 == 0) + reportf("subsumption left: %10d (%10d subsumed, %10d deleted literals)\r", subsumption_queue.size(), subsumed, deleted_literals); + + assert(c.size() > 1 || value(c[0]) == l_True); // Unit-clauses should have been propagated before this point. + + // Find best variable to scan: + Var best = var(c[0]); + for (int i = 1; i < c.size(); i++) + if (occurs[var(c[i])].size() < occurs[best].size()) + best = var(c[i]); + + // Search all candidates: + vec<Clause*>& _cs = getOccurs(best); + Clause** cs = (Clause**)_cs; + + for (int j = 0; j < _cs.size(); j++) + if (c.mark()) + break; + else if (!cs[j]->mark() && cs[j] != &c){ + Lit l = c.subsumes(*cs[j]); + + if (l == lit_Undef) + subsumed++, removeClause(*cs[j]); + else if (l != lit_Error){ + deleted_literals++; + + if (!strengthenClause(*cs[j], ~l)) + return false; + + // Did current candidate get deleted from cs? Then check candidate at index j again: + if (var(l) == best) + j--; + } + } + } + + return true; +} + + +bool SimpSolver::asymm(Var v, Clause& c) +{ + assert(decisionLevel() == 0); + + if (c.mark() || satisfied(c)) return true; + + trail_lim.push(trail.size()); + Lit l = lit_Undef; + for (int i = 0; i < c.size(); i++) + if (var(c[i]) != v && value(c[i]) != l_False) + uncheckedEnqueue(~c[i]); + else + l = c[i]; + + if (propagate() != NULL){ + cancelUntil(0); + asymm_lits++; + if (!strengthenClause(c, l)) + return false; + }else + cancelUntil(0); + + return true; +} + + +bool SimpSolver::asymmVar(Var v) +{ + assert(!frozen[v]); + assert(use_simplification); + + vec<Clause*> pos, neg; + const vec<Clause*>& cls = getOccurs(v); + + if (value(v) != l_Undef || cls.size() == 0) + return true; + + for (int i = 0; i < cls.size(); i++) + if (!asymm(v, *cls[i])) + return false; + + return backwardSubsumptionCheck(); +} + + +void SimpSolver::verifyModel() +{ + bool failed = false; + int cnt = 0; + // NOTE: elimtable.size() might be lower than nVars() at the moment + for (int i = 0; i < elimtable.size(); i++) + if (elimtable[i].order > 0) + for (int j = 0; j < elimtable[i].eliminated.size(); j++){ + cnt++; + Clause& c = *elimtable[i].eliminated[j]; + for (int k = 0; k < c.size(); k++) + if (modelValue(c[k]) == l_True) + goto next; + + reportf("unsatisfied clause: "); + printClause(*elimtable[i].eliminated[j]); + reportf("\n"); + failed = true; + next:; + } + + assert(!failed); + reportf("Verified %d eliminated clauses.\n", cnt); +} + + +bool SimpSolver::eliminateVar(Var v, bool fail) +{ + if (!fail && asymm_mode && !asymmVar(v)) return false; + + const vec<Clause*>& cls = getOccurs(v); + +// if (value(v) != l_Undef || cls.size() == 0) return true; + if (value(v) != l_Undef) return true; + + // Split the occurrences into positive and negative: + vec<Clause*> pos, neg; + for (int i = 0; i < cls.size(); i++) + (find(*cls[i], Lit(v)) ? pos : neg).push(cls[i]); + + // Check if number of clauses decreases: + int cnt = 0; + for (int i = 0; i < pos.size(); i++) + for (int j = 0; j < neg.size(); j++) + if (merge(*pos[i], *neg[j], v) && ++cnt > cls.size() + grow) + return true; + + // Delete and store old clauses: + setDecisionVar(v, false); + elimtable[v].order = elimorder++; + assert(elimtable[v].eliminated.size() == 0); + for (int i = 0; i < cls.size(); i++){ + elimtable[v].eliminated.push(Clause_new(*cls[i])); + removeClause(*cls[i]); } + + // Produce clauses in cross product: + int top = clauses.size(); + vec<Lit> resolvent; + for (int i = 0; i < pos.size(); i++) + for (int j = 0; j < neg.size(); j++) + if (merge(*pos[i], *neg[j], v, resolvent) && !addClause(resolvent)) + return false; + + // DEBUG: For checking that a clause set is saturated with respect to variable elimination. + // If the clause set is expected to be saturated at this point, this constitutes an + // error. + if (fail){ + reportf("eliminated var %d, %d <= %d\n", v+1, cnt, cls.size()); + reportf("previous clauses:\n"); + for (int i = 0; i < cls.size(); i++){ + printClause(*cls[i]); reportf("\n"); } + reportf("new clauses:\n"); + for (int i = top; i < clauses.size(); i++){ + printClause(*clauses[i]); reportf("\n"); } + assert(0); } + + return backwardSubsumptionCheck(); +} + + +void SimpSolver::remember(Var v) +{ + assert(decisionLevel() == 0); + assert(isEliminated(v)); + + vec<Lit> clause; + + // Re-activate variable: + elimtable[v].order = 0; + setDecisionVar(v, true); // Not good if the variable wasn't a decision variable before. Not sure how to fix this right now. + + if (use_simplification) + updateElimHeap(v); + + // Reintroduce all old clauses which may implicitly remember other clauses: + for (int i = 0; i < elimtable[v].eliminated.size(); i++){ + Clause& c = *elimtable[v].eliminated[i]; + clause.clear(); + for (int j = 0; j < c.size(); j++) + clause.push(c[j]); + + remembered_clauses++; + check(addClause(clause)); + free(&c); + } + + elimtable[v].eliminated.clear(); +} + + +void SimpSolver::extendModel() +{ + vec<Var> vs; + + // NOTE: elimtable.size() might be lower than nVars() at the moment + for (int v = 0; v < elimtable.size(); v++) + if (elimtable[v].order > 0) + vs.push(v); + + sort(vs, ElimOrderLt(elimtable)); + + for (int i = 0; i < vs.size(); i++){ + Var v = vs[i]; + Lit l = lit_Undef; + + for (int j = 0; j < elimtable[v].eliminated.size(); j++){ + Clause& c = *elimtable[v].eliminated[j]; + + for (int k = 0; k < c.size(); k++) + if (var(c[k]) == v) + l = c[k]; + else if (modelValue(c[k]) != l_False) + goto next; + + assert(l != lit_Undef); + model[v] = lbool(!sign(l)); + break; + + next:; + } + + if (model[v] == l_Undef) + model[v] = l_True; + } +} + + +bool SimpSolver::eliminate(bool turn_off_elim) +{ + if (!ok || !use_simplification) + return ok; + + // Main simplification loop: + //assert(subsumption_queue.size() == 0); + //gatherTouchedClauses(); + while (subsumption_queue.size() > 0 || elim_heap.size() > 0){ + + //fprintf(stderr, "subsumption phase: (%d)\n", subsumption_queue.size()); + if (!backwardSubsumptionCheck(true)) + return false; + + //fprintf(stderr, "elimination phase:\n (%d)", elim_heap.size()); + for (int cnt = 0; !elim_heap.empty(); cnt++){ + Var elim = elim_heap.removeMin(); + + if (verbosity >= 2 && cnt % 100 == 0) + reportf("elimination left: %10d\r", elim_heap.size()); + + if (!frozen[elim] && !eliminateVar(elim)) + return false; + } + + assert(subsumption_queue.size() == 0); + gatherTouchedClauses(); + } + + // Cleanup: + cleanUpClauses(); + order_heap.filter(VarFilter(*this)); + +#ifdef INVARIANTS + // Check that no more subsumption is possible: + reportf("Checking that no more subsumption is possible\n"); + for (int i = 0; i < clauses.size(); i++){ + if (i % 1000 == 0) + reportf("left %10d\r", clauses.size() - i); + + assert(clauses[i]->mark() == 0); + for (int j = 0; j < i; j++) + assert(clauses[i]->subsumes(*clauses[j]) == lit_Error); + } + reportf("done.\n"); + + // Check that no more elimination is possible: + reportf("Checking that no more elimination is possible\n"); + for (int i = 0; i < nVars(); i++) + if (!frozen[i]) eliminateVar(i, true); + reportf("done.\n"); + checkLiteralCount(); +#endif + + // If no more simplification is needed, free all simplification-related data structures: + if (turn_off_elim){ + use_simplification = false; + touched.clear(true); + occurs.clear(true); + n_occ.clear(true); + subsumption_queue.clear(true); + elim_heap.clear(true); + remove_satisfied = true; + } + + + return true; +} + + +void SimpSolver::cleanUpClauses() +{ + int i , j; + vec<Var> dirty; + for (i = 0; i < clauses.size(); i++) + if (clauses[i]->mark() == 1){ + Clause& c = *clauses[i]; + for (int k = 0; k < c.size(); k++) + if (!seen[var(c[k])]){ + seen[var(c[k])] = 1; + dirty.push(var(c[k])); + } } + + for (i = 0; i < dirty.size(); i++){ + cleanOcc(dirty[i]); + seen[dirty[i]] = 0; } + + for (i = j = 0; i < clauses.size(); i++) + if (clauses[i]->mark() == 1) + free(clauses[i]); + else + clauses[j++] = clauses[i]; + clauses.shrink(i - j); +} + + +//================================================================================================= +// Convert to DIMACS: + + +void SimpSolver::toDimacs(FILE* f, Clause& c) +{ + if (satisfied(c)) return; + + for (int i = 0; i < c.size(); i++) + if (value(c[i]) != l_False) + fprintf(f, "%s%d ", sign(c[i]) ? "-" : "", var(c[i])+1); + fprintf(f, "0\n"); +} + + +void SimpSolver::toDimacs(const char* file) +{ + assert(decisionLevel() == 0); + FILE* f = fopen(file, "wr"); + if (f != NULL){ + + // Cannot use removeClauses here because it is not safe + // to deallocate them at this point. Could be improved. + int cnt = 0; + for (int i = 0; i < clauses.size(); i++) + if (!satisfied(*clauses[i])) + cnt++; + + fprintf(f, "p cnf %d %d\n", nVars(), cnt); + + for (int i = 0; i < clauses.size(); i++) + toDimacs(f, *clauses[i]); + + fprintf(stderr, "Wrote %d clauses...\n", clauses.size()); + }else + fprintf(stderr, "could not open file %s\n", file); +} + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ diff --git a/src/sat/minisat/simp/SimpSolver.h b/src/sat/minisat/simp/SimpSolver.h new file mode 100644 index 000000000..221b4c6e2 --- /dev/null +++ b/src/sat/minisat/simp/SimpSolver.h @@ -0,0 +1,166 @@ +/************************************************************************************[SimpSolver.h] +MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson + +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. +**************************************************************************************************/ + +#ifndef CVC4_MiniSat_SimpSolver_h +#define CVC4_MiniSat_SimpSolver_h + +#include <cstdio> + +#include "Queue.h" +#include "Solver.h" + +namespace CVC4 { +namespace MiniSat { + +class SimpSolver : public Solver { + public: + // Constructor/Destructor: + // + SimpSolver(); + ~SimpSolver(); + + // Problem specification: + // + Var newVar (bool polarity = true, bool dvar = true); + bool addClause (vec<Lit>& ps); + + // Variable mode: + // + void setFrozen (Var v, bool b); // If a variable is frozen it will not be eliminated. + + // Solving: + // + bool solve (const vec<Lit>& assumps, bool do_simp = true, bool turn_off_simp = false); + bool solve (bool do_simp = true, bool turn_off_simp = false); + bool eliminate (bool turn_off_elim = false); // Perform variable elimination based simplification. + + // Generate a (possibly simplified) DIMACS file: + // + void toDimacs (const char* file); + + // Mode of operation: + // + int grow; // Allow a variable elimination step to grow by a number of clauses (default to zero). + bool asymm_mode; // Shrink clauses by asymmetric branching. + bool redundancy_check; // Check if a clause is already implied. Prett costly, and subsumes subsumptions :) + + // Statistics: + // + int merges; + int asymm_lits; + int remembered_clauses; + +// protected: + public: + + // Helper structures: + // + struct ElimData { + int order; // 0 means not eliminated, >0 gives an index in the elimination order + vec<Clause*> eliminated; + ElimData() : order(0) {} }; + + struct ElimOrderLt { + const vec<ElimData>& elimtable; + ElimOrderLt(const vec<ElimData>& et) : elimtable(et) {} + bool operator()(Var x, Var y) { return elimtable[x].order > elimtable[y].order; } }; + + struct ElimLt { + const vec<int>& n_occ; + ElimLt(const vec<int>& no) : n_occ(no) {} + int cost (Var x) const { return n_occ[toInt(Lit(x))] * n_occ[toInt(~Lit(x))]; } + bool operator()(Var x, Var y) const { return cost(x) < cost(y); } }; + + + // Solver state: + // + int elimorder; + bool use_simplification; + vec<ElimData> elimtable; + vec<char> touched; + vec<vec<Clause*> > occurs; + vec<int> n_occ; + Heap<ElimLt> elim_heap; + Queue<Clause*> subsumption_queue; + vec<char> frozen; + int bwdsub_assigns; + + // Temporaries: + // + Clause* bwdsub_tmpunit; + + // Main internal methods: + // + bool asymm (Var v, Clause& c); + bool asymmVar (Var v); + void updateElimHeap (Var v); + void cleanOcc (Var v); + vec<Clause*>& getOccurs (Var x); + void gatherTouchedClauses (); + bool merge (const Clause& _ps, const Clause& _qs, Var v, vec<Lit>& out_clause); + bool merge (const Clause& _ps, const Clause& _qs, Var v); + bool backwardSubsumptionCheck (bool verbose = false); + bool eliminateVar (Var v, bool fail = false); + void remember (Var v); + void extendModel (); + void verifyModel (); + + void removeClause (Clause& c); + bool strengthenClause (Clause& c, Lit l); + void cleanUpClauses (); + bool implied (const vec<Lit>& c); + void toDimacs (FILE* f, Clause& c); + bool isEliminated (Var v) const; + +}; + + +//================================================================================================= +// Implementation of inline methods: + +inline void SimpSolver::updateElimHeap(Var v) { + if (elimtable[v].order == 0) + elim_heap.update(v); } + +inline void SimpSolver::cleanOcc(Var v) { + assert(use_simplification); + Clause **begin = (Clause**)occurs[v]; + Clause **end = begin + occurs[v].size(); + Clause **i, **j; + for (i = begin, j = end; i < j; i++) + if ((*i)->mark() == 1){ + *i = *(--j); + i--; + } + //occurs[v].shrink_(end - j); // This seems slower. Why?! + occurs[v].shrink(end - j); +} + +inline vec<Clause*>& SimpSolver::getOccurs(Var x) { + cleanOcc(x); return occurs[x]; } + +inline bool SimpSolver::isEliminated (Var v) const { return v < elimtable.size() && elimtable[v].order != 0; } +inline void SimpSolver::setFrozen (Var v, bool b) { frozen[v] = (char)b; if (b) { updateElimHeap(v); } } +inline bool SimpSolver::solve (bool do_simp, bool turn_off_simp) { vec<Lit> tmp; return solve(tmp, do_simp, turn_off_simp); } + +}/* CVC4::MiniSat namespace */ +}/* CVC4 namespace */ + +//================================================================================================= +#endif /* CVC4_MiniSat_SimpSolver_h */ |