diff options
Diffstat (limited to 'src')
79 files changed, 2028 insertions, 672 deletions
diff --git a/src/compat/cvc3_compat.cpp b/src/compat/cvc3_compat.cpp index 02d76d351..2a8673451 100644 --- a/src/compat/cvc3_compat.cpp +++ b/src/compat/cvc3_compat.cpp @@ -1107,23 +1107,38 @@ Type ValidityChecker::tupleType(const std::vector<Type>& types) { } Type ValidityChecker::recordType(const std::string& field, const Type& type) { - Unimplemented("Records not supported by CVC4 yet (sorry!)"); + std::vector< std::pair<std::string, CVC4::Type> > fields; + fields.push_back(std::make_pair(field, (const CVC4::Type&) type)); + return d_em->mkRecordType(CVC4::Record(fields)); } Type ValidityChecker::recordType(const std::string& field0, const Type& type0, const std::string& field1, const Type& type1) { - Unimplemented("Records not supported by CVC4 yet (sorry!)"); + std::vector< std::pair<std::string, CVC4::Type> > fields; + fields.push_back(std::make_pair(field0, (const CVC4::Type&) type0)); + fields.push_back(std::make_pair(field1, (const CVC4::Type&) type1)); + return d_em->mkRecordType(CVC4::Record(fields)); } Type ValidityChecker::recordType(const std::string& field0, const Type& type0, const std::string& field1, const Type& type1, const std::string& field2, const Type& type2) { - Unimplemented("Records not supported by CVC4 yet (sorry!)"); + std::vector< std::pair<std::string, CVC4::Type> > fields; + fields.push_back(std::make_pair(field0, (const CVC4::Type&) type0)); + fields.push_back(std::make_pair(field1, (const CVC4::Type&) type1)); + fields.push_back(std::make_pair(field2, (const CVC4::Type&) type2)); + return d_em->mkRecordType(CVC4::Record(fields)); } Type ValidityChecker::recordType(const std::vector<std::string>& fields, const std::vector<Type>& types) { - Unimplemented("Records not supported by CVC4 yet (sorry!)"); + CVC4::CheckArgument(fields.size() == types.size() && fields.size() > 0, + "invalid vector length(s) in recordType()"); + std::vector< std::pair<std::string, CVC4::Type> > fieldSpecs; + for(unsigned i = 0; i < fields.size(); ++i) { + fieldSpecs.push_back(std::make_pair(fields[i], (const CVC4::Type&) types[i])); + } + return d_em->mkRecordType(CVC4::Record(fieldSpecs)); } Type ValidityChecker::dataType(const std::string& name, @@ -1559,32 +1574,43 @@ Expr ValidityChecker::geExpr(const Expr& left, const Expr& right) { } Expr ValidityChecker::recordExpr(const std::string& field, const Expr& expr) { - Unimplemented("Records not supported by CVC4 yet (sorry!)"); + CVC4::Type t = recordType(field, expr.getType()); + return d_em->mkExpr(CVC4::kind::RECORD, d_em->mkConst(CVC4::RecordType(t).getRecord()), expr); } Expr ValidityChecker::recordExpr(const std::string& field0, const Expr& expr0, const std::string& field1, const Expr& expr1) { - Unimplemented("Records not supported by CVC4 yet (sorry!)"); + CVC4::Type t = recordType(field0, expr0.getType(), + field1, expr1.getType()); + return d_em->mkExpr(CVC4::kind::RECORD, d_em->mkConst(CVC4::RecordType(t).getRecord()), expr0, expr1); } Expr ValidityChecker::recordExpr(const std::string& field0, const Expr& expr0, const std::string& field1, const Expr& expr1, const std::string& field2, const Expr& expr2) { - Unimplemented("Records not supported by CVC4 yet (sorry!)"); + CVC4::Type t = recordType(field0, expr0.getType(), + field1, expr1.getType(), + field2, expr2.getType()); + return d_em->mkExpr(CVC4::kind::RECORD, d_em->mkConst(CVC4::RecordType(t).getRecord()), expr0, expr1, expr2); } Expr ValidityChecker::recordExpr(const std::vector<std::string>& fields, const std::vector<Expr>& exprs) { - Unimplemented("Records not supported by CVC4 yet (sorry!)"); + std::vector<Type> types; + for(unsigned i = 0; i < exprs.size(); ++i) { + types.push_back(exprs[i].getType()); + } + CVC4::Type t = recordType(fields, types); + return d_em->mkExpr(d_em->mkConst(CVC4::RecordType(t).getRecord()), *reinterpret_cast<const vector<CVC4::Expr>*>(&exprs)); } Expr ValidityChecker::recSelectExpr(const Expr& record, const std::string& field) { - Unimplemented("Records not supported by CVC4 yet (sorry!)"); + return d_em->mkExpr(d_em->mkConst(CVC4::RecordSelect(field)), record); } Expr ValidityChecker::recUpdateExpr(const Expr& record, const std::string& field, const Expr& newValue) { - Unimplemented("Records not supported by CVC4 yet (sorry!)"); + return d_em->mkExpr(d_em->mkConst(CVC4::RecordUpdate(field)), record, newValue); } Expr ValidityChecker::readExpr(const Expr& array, const Expr& index) { @@ -1935,12 +1961,16 @@ Expr ValidityChecker::tupleExpr(const std::vector<Expr>& exprs) { } Expr ValidityChecker::tupleSelectExpr(const Expr& tuple, int index) { - Unimplemented("Tuples not supported by CVC4 yet (sorry!)"); + CVC4::CheckArgument(index >= 0 && index < tuple.getNumChildren(), + "invalid index in tuple select"); + return d_em->mkExpr(d_em->mkConst(CVC4::TupleSelect(index)), tuple); } Expr ValidityChecker::tupleUpdateExpr(const Expr& tuple, int index, const Expr& newValue) { - Unimplemented("Tuples not supported by CVC4 yet (sorry!)"); + CVC4::CheckArgument(index >= 0 && index < tuple.getNumChildren(), + "invalid index in tuple update"); + return d_em->mkExpr(d_em->mkConst(CVC4::TupleUpdate(index)), tuple, newValue); } Expr ValidityChecker::datatypeConsExpr(const std::string& constructor, const std::vector<Expr>& args) { diff --git a/src/context/Makefile.am b/src/context/Makefile.am index e7f1dc68b..a63c990cc 100644 --- a/src/context/Makefile.am +++ b/src/context/Makefile.am @@ -16,6 +16,10 @@ libcontext_la_SOURCES = \ cdlist_forward.h \ cdqueue.h \ cdtrail_queue.h \ + cdtrail_hashmap.h \ + cdtrail_hashmap_forward.h \ + cdinsert_hashmap.h \ + cdinsert_hashmap_forward.h \ cdhashmap.h \ cdhashmap_forward.h \ cdhashset.h \ diff --git a/src/context/cdhashmap.h b/src/context/cdhashmap.h index a37fd2f23..e2ede0603 100644 --- a/src/context/cdhashmap.h +++ b/src/context/cdhashmap.h @@ -17,14 +17,19 @@ ** and operator== for the key class. For key types that don't have a ** __gnu_cxx::hash<>, you should provide an explicit HashFcn. ** + ** See also: + ** CDInsertHashMap : An "insert-once" CD hash map. + ** CDTrailHashMap : A lightweight CD hash map with poor iteration + ** characteristics and some quirks in usage. + ** ** Internal documentation: ** - ** CDMap<> is something of a work in progress at present (26 May + ** CDHashMap<> is something of a work in progress at present (26 May ** 2010), due to some recent discoveries of problems with its ** internal state. Here are some notes on the internal use of ** CDOhash_maps that may be useful in figuring out this mess: ** - ** So you have a CDMap<>. + ** So you have a CDHashMap<>. ** ** You insert some (key,value) pairs. Each allocates a CDOhash_map<> ** and goes on a doubly-linked list headed by map.d_first and @@ -36,7 +41,7 @@ ** map pointer at level 0, and a non-NULL map pointer in the ** current context level. (Remember that for later.) ** - ** When a key is associated to a new value in a CDMap, its + ** When a key is associated to a new value in a CDHashMap, its ** associated CDOhash_map calls makeCurrent(), then sets the new ** value. The save object is also a CDOhash_map (allocated in context ** memory). @@ -62,21 +67,21 @@ ** obliterate() removes it from the map and frees the CDOhash_map's ** memory. ** - ** Fourth, you might delete the cdhashmap(calling CDMap::~CDMap()). + ** Fourth, you might delete the cdhashmap(calling CDHashMap::~CDHashMap()). ** This first calls destroy(), as per ContextObj contract, but ** cdhashmapdoesn't save/restore itself, so that does nothing at the - ** CDMap-level. Then it empties the trash. Then, for each + ** CDHashMap-level. Then it empties the trash. Then, for each ** element in the map, it marks it as being "part of a complete ** map destruction", which essentially short-circuits ** CDOhash_map::restore() (see CDOhash_map::restore()), then deallocates ** it. Finally it asserts that the trash is empty (which it ** should be, since restore() was short-circuited). ** - ** Fifth, you might clear() the CDMap. This does exactly the - ** same as CDMap::~CDMap(), except that it doesn't call destroy() + ** Fifth, you might clear() the CDHashMap. This does exactly the + ** same as CDHashMap::~CDHashMap(), except that it doesn't call destroy() ** on itself. ** - ** CDMap::emptyTrash() simply goes through and calls + ** CDHashMap::emptyTrash() simply goes through and calls ** ->deleteSelf() on all elements in the trash. ** ContextObj::deleteSelf() calls the CDOhash_map destructor, then ** frees the memory associated to the CDOhash_map. CDOhash_map::~CDOhash_map() @@ -87,8 +92,8 @@ #include "cvc4_private.h" -#ifndef __CVC4__CONTEXT__CDMAP_H -#define __CVC4__CONTEXT__CDMAP_H +#ifndef __CVC4__CONTEXT__CDHASHMAP_H +#define __CVC4__CONTEXT__CDHASHMAP_H #include <vector> #include <iterator> @@ -148,9 +153,9 @@ class CDOhash_map : public ContextObj { d_next->d_prev = d_prev; d_prev->d_next = d_next; if(d_noTrash) { - Debug("gc") << "CDMap<> no-trash " << this << std::endl; + Debug("gc") << "CDHashMap<> no-trash " << this << std::endl; } else { - Debug("gc") << "CDMap<> trash push_back " << this << std::endl; + Debug("gc") << "CDHashMap<> trash push_back " << this << std::endl; //this->deleteSelf(); d_map->d_trash.push_back(this); } @@ -190,7 +195,7 @@ public: // "Initializing" map insertion: this entry will never be // removed from the map, it's inserted at level 0 as an // "initializing" element. See - // CDMap<>::insertAtContextLevelZero(). + // CDHashMap<>::insertAtContextLevelZero(). d_data = data; } else { // Normal map insertion: first makeCurrent(), then set the data @@ -417,7 +422,7 @@ public: } /** - * Version of insert() for CDMap<> that inserts data value d at + * Version of insert() for CDHashMap<> that inserts data value d at * context level zero. This is a special escape hatch for inserting * "initializing" data into the map. Imagine something happens at a * deep context level L that causes insertion into a map, such that @@ -538,7 +543,7 @@ public: const std::pair<const Key, Data>& operator*() const { return *d_pair; } - };/* class CDMap<>::iterator::Proxy */ + };/* class CDHashMap<>::iterator::Proxy */ // Actual postfix increment: returns Proxy with the old value. // Now, an expression like *i++ will return the current *i, and @@ -549,7 +554,7 @@ public: ++(*this); return e; } - };/* class CDMap<>::iterator */ + };/* class CDHashMap<>::iterator */ typedef iterator const_iterator; @@ -576,9 +581,9 @@ public: return const_cast<const CDHashMap*>(this)->find(k); } -};/* class CDMap<> */ +};/* class CDHashMap<> */ }/* CVC4::context namespace */ }/* CVC4 namespace */ -#endif /* __CVC4__CONTEXT__CDMAP_H */ +#endif /* __CVC4__CONTEXT__CDHashMAP_H */ diff --git a/src/context/cdhashmap_forward.h b/src/context/cdhashmap_forward.h index d81f5345d..60291af07 100644 --- a/src/context/cdhashmap_forward.h +++ b/src/context/cdhashmap_forward.h @@ -9,22 +9,22 @@ ** See the file COPYING in the top-level source directory for licensing ** information.\endverbatim ** - ** \brief This is a forward declaration header to declare the CDMap<> + ** \brief This is a forward declaration header to declare the CDHashMap<> ** template ** - ** This is a forward declaration header to declare the CDMap<> - ** template. It's useful if you want to forward-declare CDMap<> - ** without including the full cdmap.h header, for example, in a + ** This is a forward declaration header to declare the CDHashMap<> + ** template. It's useful if you want to forward-declare CDHashMap<> + ** without including the full cdhashmap.h header, for example, in a ** public header context. ** - ** For CDMap<> in particular, it's difficult to forward-declare it + ** For CDHashMap<> in particular, it's difficult to forward-declare it ** yourself, because it has a default template argument. **/ #include "cvc4_public.h" -#ifndef __CVC4__CONTEXT__CDMAP_FORWARD_H -#define __CVC4__CONTEXT__CDMAP_FORWARD_H +#ifndef __CVC4__CONTEXT__CDHASHMAP_FORWARD_H +#define __CVC4__CONTEXT__CDHASHMAP_FORWARD_H /// \cond internals @@ -41,4 +41,4 @@ namespace CVC4 { /// \endcond -#endif /* __CVC4__CONTEXT__CDMAP_FORWARD_H */ +#endif /* __CVC4__CONTEXT__CDHASHMAP_FORWARD_H */ diff --git a/src/context/cdhashset.h b/src/context/cdhashset.h index e885b7729..d7957cf3f 100644 --- a/src/context/cdhashset.h +++ b/src/context/cdhashset.h @@ -20,16 +20,15 @@ #define __CVC4__CONTEXT__CDSET_H #include "context/context.h" -#include "context/cdhashset_forward.h" -#include "context/cdhashmap.h" +#include "context/cdinsert_hashmap.h" #include "util/cvc4_assert.h" namespace CVC4 { namespace context { template <class V, class HashFcn> -class CDHashSet : protected CDHashMap<V, V, HashFcn> { - typedef CDHashMap<V, V, HashFcn> super; +class CDHashSet : protected CDInsertHashMap<V, bool, HashFcn> { + typedef CDInsertHashMap<V, bool, HashFcn> super; public: @@ -58,40 +57,30 @@ public: return super::size(); } - size_t count(const V& v) const { - return super::count(v); - } - bool insert(const V& v) { - return super::insert(v, v); - } - - void insertAtContextLevelZero(const V& v) { - return super::insertAtContextLevelZero(v, v); + return super::insert_safe(v, true); } bool contains(const V& v) { - return find(v) != end(); + return super::contains(v); } - // FIXME: no erase(), too much hassle to implement efficiently... - - class iterator { - typename super::iterator d_it; + class const_iterator { + typename super::const_iterator d_it; public: - iterator(const typename super::iterator& it) : d_it(it) {} - iterator(const iterator& it) : d_it(it.d_it) {} + const_iterator(const typename super::const_iterator& it) : d_it(it) {} + const_iterator(const const_iterator& it) : d_it(it.d_it) {} // Default constructor - iterator() {} + const_iterator() {} // (Dis)equality - bool operator==(const iterator& i) const { + bool operator==(const const_iterator& i) const { return d_it == i.d_it; } - bool operator!=(const iterator& i) const { + bool operator!=(const const_iterator& i) const { return d_it != i.d_it; } @@ -101,7 +90,7 @@ public: } // Prefix increment - iterator& operator++() { + const_iterator& operator++() { ++d_it; return *this; } @@ -131,18 +120,28 @@ public: } };/* class CDSet<>::iterator */ - typedef iterator const_iterator; - const_iterator begin() const { - return iterator(super::begin()); + return const_iterator(super::begin()); } const_iterator end() const { - return iterator(super::end()); + return const_iterator(super::end()); } const_iterator find(const V& v) const { - return iterator(super::find(v)); + return const_iterator(super::find(v)); + } + + typedef typename super::key_iterator key_iterator; + key_iterator key_begin() const { + return super::key_begin(); + } + key_iterator key_end() const { + return super::key_end(); + } + + void insertAtContextLevelZero(const V& v) { + return super::insertAtContextLevelZero(v, true); } };/* class CDSet */ diff --git a/src/context/cdinsert_hashmap.h b/src/context/cdinsert_hashmap.h new file mode 100644 index 000000000..0c84eda80 --- /dev/null +++ b/src/context/cdinsert_hashmap.h @@ -0,0 +1,402 @@ +/********************* */ +/*! \file cdinsert_hashmap.h + ** \verbatim + ** Original author: taking + ** Major contributors: none + ** Minor contributors (to current version): none + ** This file is part of the CVC4 prototype. + ** Copyright (c) 2009-2012 New York University and The University of Iowa + ** See the file COPYING in the top-level source directory for licensing + ** information.\endverbatim + ** + ** \brief Context-dependent insert only hashmap built using trail of edits + ** + ** Context-dependent hashmap that only allows for one insertion per element. + ** This can be viewed as a highly restricted version of CDHashMap. + ** It is significantly lighter in memory usage than CDHashMap. + ** + ** See also: + ** CDTrailHashMap : A lightweight CD hash map with poor iteration + ** characteristics and some quirks in usage. + ** CDHashMap : A fully featured CD hash map. (The closest to <ext/hash_map>) + ** + ** Notes: + ** - To iterate efficiently over the elements use the key_iterators. + ** - operator[] is only supported as a const derefence (must succeed). + ** - insert(k) must always work. + ** - Use insert_safe if you want to check if the element has been inserted + ** and only insert if it has not yet been. + ** - Does not accept TNodes as keys. + ** - Supports insertAtContextLevelZero() if the element is not in the map. + **/ + + +#include "cvc4_private.h" + +#include "context/context.h" +#include "context/cdinsert_hashmap_forward.h" +#include <utility> +#include <ext/hash_map> +#include <deque> +#include "util/cvc4_assert.h" +#include "util/output.h" + +#include "expr/node.h" +#include <boost/static_assert.hpp> + +#pragma once + +namespace CVC4 { +namespace context { + + +template <class Key, class Data, class HashFcn = __gnu_cxx::hash<Key> > +class InsertHashMap { +private: + typedef std::deque<Key> KeyVec; + /** A list of the keys in the map maintained as a stack. */ + KeyVec d_keys; + + typedef __gnu_cxx::hash_map<Key, Data, HashFcn> HashMap; + /** The hash_map used for element lookup. */ + HashMap d_hashMap; + +public: + /** + * An iterator over a list of keys. + * Use this to efficiently iterate over the elements. + * (See std::deque<>::iterator). + */ + typedef typename KeyVec::const_iterator key_iterator; + + /**An iterator over the elements in the hash_map. */ + typedef typename HashMap::const_iterator const_iterator; + + + /** + * Returns an iterator to the begining of the HashMap. + * Acts like a hash_map::const_iterator. + */ + const_iterator begin() const{ + return d_hashMap.begin(); + } + /** + * Returns an iterator to the end of the HashMap. + * Acts like a hash_map::const_iterator. + */ + const_iterator end() const{ + return d_hashMap.end(); + } + + /** + * Returns an iterator to the Key k of the map. + * See hash_map::find() + */ + const_iterator find(const Key& k) const{ + return d_hashMap.find(k); + } + + /** Returns an iterator to the start of the set of keys. */ + key_iterator key_begin() const{ + return d_keys.begin(); + } + /** Returns an iterator to the end of the set of keys. */ + key_iterator key_end() const{ + return d_keys.end(); + } + + /** Returns true if the map is empty. */ + bool empty() const { return d_keys.empty(); } + /** Returns the number of elements in the map. */ + size_t size() const { return d_keys.size(); } + + /** Returns true if k is a mapped key. */ + bool contains(const Key& k) const { + return find(k) != end(); + } + + /** + * Returns a reference the data mapped by k. + * This must succeed. + */ + const Data& operator[](const Key& k) const { + const_iterator ci = find(k); + Assert(ci != end()); + return (*ci).second; + } + + /** + * Inserts an element into the map, and pushes its key to the front + * of the stack. The key inserted must be not be currently mapped. + */ + void push_front(const Key& k, const Data& d){ + Assert(!contains(k)); + d_hashMap.insert(std::make_pair(k, d)); + d_keys.push_front(k); + } + + /** + * Inserts an element into the map, and pushes its key onto the + * back on the stack. The key inserted must be not be currently mapped. + */ + void push_back(const Key& k, const Data& d){ + Assert(!contains(k)); + d_hashMap.insert(std::make_pair(k, d)); + d_keys.push_back(k); + } + + /** + * Pops the key at the front of the list off and removes its key from the map. + */ + void pop_front(){ + Assert(!empty()); + const Key& front = d_keys.front(); + d_hashMap.erase(front); + + Debug("TrailHashMap") <<"TrailHashMap pop_front " << size() << std::endl; + d_keys.pop_front(); + } + + /** + * Pops the key at the back of the stack off and removes its key from the map. + */ + void pop_back(){ + Assert(!empty()); + const Key& back = d_keys.back(); + d_hashMap.erase(back); + + Debug("TrailHashMap") <<"TrailHashMap pop_back " << size() << std::endl; + d_keys.pop_back(); + } + + /** + * Pops the back of the stack until the size is below s. + */ + void pop_to_size(size_t s){ + while(size() > s){ + pop_back(); + } + } +};/* class TrailHashMap<> */ + +template <class Key, class Data, class HashFcn > +class CDInsertHashMap : public ContextObj { +private: + typedef InsertHashMap<Key, Data, HashFcn> IHM; + + /** An InsertHashMap that backs all of the data. */ + IHM* d_insertMap; + + /** For restores, we need to keep track of the previous size. */ + size_t d_size; + + /** + * To support insertAtContextLevelZero() and restores, + * we have called d_insertMap->d_pushFront(). + */ + size_t d_pushFronts; + + /** + * Private copy constructor used only by save(). d_insertMap is + * not copied: only the base class information and + * d_size and d_pushFronts are needed in restore. + */ + CDInsertHashMap(const CDInsertHashMap<Key, Data, HashFcn>& l) : + ContextObj(l), + d_insertMap(NULL), + d_size(l.d_size), + d_pushFronts(l.d_pushFronts) + { + Debug("CDInsertHashMap") << "copy ctor: " << this + << " from " << &l + << " size " << d_size << std::endl; + } + + /** + * Implementation of mandatory ContextObj method save: simply copies + * the current size information to a copy using the copy constructor (the + * pointer and the allocated size are *not* copied as they are not + * restored on a pop). The saved information is allocated using the + * ContextMemoryManager. + */ + ContextObj* save(ContextMemoryManager* pCMM) { + ContextObj* data = new(pCMM) CDInsertHashMap<Key, Data, HashFcn>(*this); + Debug("CDInsertHashMap") << "save " << this + << " at level " << this->getContext()->getLevel() + << " size at " << this->d_size + << " d_list is " << this->d_insertMap + << " data:" << data << std::endl; + return data; + } +protected: + /** + * Implementation of mandatory ContextObj method restore: + * restore to the previous size taking into account the number + * of new pushFront calls have happened since saving. + * The d_insertMap is untouched and d_pushFronts is also kept. + */ + void restore(ContextObj* data) { + Debug("CDInsertHashMap") << "restore " << this + << " level " << this->getContext()->getLevel() + << " data == " << data + << " d_insertMap == " << this->d_insertMap << std::endl; + size_t oldSize = ((CDInsertHashMap<Key, Data, HashFcn>*)data)->d_size; + size_t oldPushFronts = ((CDInsertHashMap<Key, Data, HashFcn>*)data)->d_pushFronts; + Assert(oldPushFronts <= d_pushFronts); + + // The size to restore to. + size_t restoreSize = oldSize + (d_pushFronts - oldPushFronts); + d_insertMap->pop_to_size(restoreSize); + d_size = restoreSize; + Assert(d_insertMap->size() == d_size); + Debug("CDInsertHashMap") << "restore " << this + << " level " << this->getContext()->getLevel() + << " size back to " << this->d_size << std::endl; + } +public: + + /** + * Main constructor: d_insertMap starts as an empty map, with the size is 0 + */ + CDInsertHashMap(Context* context) : + ContextObj(context), + d_insertMap(new IHM()), + d_size(0), + d_pushFronts(0){ + Assert(d_insertMap->size() == d_size); + } + + /** + * Destructor: delete the d_insertMap + */ + ~CDInsertHashMap() throw(AssertionException) { + this->destroy(); + delete d_insertMap; + } + + /** An iterator over the elements in the hash_map. */ + typedef typename IHM::const_iterator const_iterator; + + /** + * An iterator over a list of keys. + * Use this to efficiently iterate over the elements. + * (See std::deque<>::iterator). + */ + typedef typename IHM::key_iterator key_iterator; + + /** Returns true if the map is empty in the current context. */ + bool empty() const{ + return d_size == 0; + } + + /** Returns true the size of the map in the current context. */ + size_t size() const { + return d_size; + } + + /** + * Inserts an element into the map. + * The key inserted must be not be currently mapped. + * This is implemented using d_insertMap.push_back(). + */ + void insert(const Key& k, const Data& d){ + makeCurrent(); + ++d_size; + d_insertMap->push_back(k, d); + Assert(d_insertMap->size() == d_size); + } + + /** + * Checks if the key k is mapped already. + * If it is, this returns false. + * Otherwise it is inserted and this returns true. + */ + bool insert_safe(const Key& k, const Data& d){ + if(contains(k)){ + return false; + }else{ + insert(k,d); + return true; + } + } + + /** + * Version of insert() for CDMap<> that inserts data value d at + * context level zero. + * + * It is an error to insertAtContextLevelZero() + * a key that already is in the map. + */ + void insertAtContextLevelZero(const Key& k, const Data& d){ + makeCurrent(); + ++d_size; + ++d_pushFronts; + d_insertMap->push_front(k, d); + } + + /** Returns true if k is a mapped key in the context. */ + bool contains(const Key& k) const { + return d_insertMap->contains(k); + } + + /** + * Returns a reference the data mapped by k. + * k must be in the map in this context. + */ + const Data& operator[](const Key& k) const { + return (*d_insertMap)[k]; + } + + /** + * Returns a const_iterator to the value_type if k is a mapped key in + * the context. + */ + const_iterator find(const Key& k) const { + return d_insertMap->find(k); + } + + /** + * Returns an iterator to the begining of the map. + * Acts like a hash_map::const_iterator. + */ + const_iterator begin() const{ + return d_insertMap->begin(); + } + + /** + * Returns an iterator to the end of the map. + * Acts like a hash_map::const_iterator. + */ + const_iterator end() const{ + return d_insertMap->end(); + } + + /** Returns an iterator to the start of the set of keys. */ + key_iterator key_begin() const{ + return d_insertMap->key_begin(); + } + /** Returns an iterator to the end of the set of keys. */ + key_iterator key_end() const{ + return d_insertMap->key_end(); + } +};/* class CDInsertHashMap<> */ + + +template <class Data, class HashFcn> +class CDInsertHashMap <TNode, Data, HashFcn > : public ContextObj { + /* CDInsertHashMap is challenging to get working with TNode. + * Consider using CDHashMap<TNode,...> instead. + * + * Explanation: + * CDInsertHashMap uses keys for deallocation. + * If the key is a TNode and the backing (the hard node reference) + * for the key in another data structure removes the key at the same context + * the ref count could drop to 0. The key would then not be eligible to be + * hashed. Getting the order right with a guarentee is to hard. + */ + + BOOST_STATIC_ASSERT(sizeof(Data) == 0); +}; + +}/* CVC4::context namespace */ +}/* CVC4 namespace */ diff --git a/src/context/cdinsert_hashmap_forward.h b/src/context/cdinsert_hashmap_forward.h new file mode 100644 index 000000000..638607840 --- /dev/null +++ b/src/context/cdinsert_hashmap_forward.h @@ -0,0 +1,38 @@ +/********************* */ +/*! \file cdinsert_hashmap_forward.h + ** \verbatim + ** Original author: taking + ** Major contributors: none + ** Minor contributors (to current version): none + ** This file is part of the CVC4 prototype. + ** Copyright (c) 2009-2012 New York University and The University of Iowa + ** See the file COPYING in the top-level source directory for licensing + ** information.\endverbatim + ** + ** \brief This is a forward declaration header to declare the CDInsertHashMap<> + ** template + ** + ** This is a forward declaration header to declare the CDInsertHashMap<> + ** template. It's useful if you want to forward-declare CDInsertHashMap<> + ** without including the full cdinsert_hashmap.h header, for example, in a + ** public header context. + ** + ** For CDInsertHashMap<> in particular, it's difficult to forward-declare it + ** yourself, because it has a default template argument. + **/ + +#include "cvc4_public.h" + +#pragma once + +namespace __gnu_cxx { + template <class Key> struct hash; +}/* __gnu_cxx namespace */ + +namespace CVC4 { + namespace context { + template <class Key, class Data, class HashFcn = __gnu_cxx::hash<Key> > + class CDInsertHashMap; + }/* CVC4::context namespace */ +}/* CVC4 namespace */ + diff --git a/src/context/cdtrail_hashmap.h b/src/context/cdtrail_hashmap.h new file mode 100644 index 000000000..5f090341d --- /dev/null +++ b/src/context/cdtrail_hashmap.h @@ -0,0 +1,571 @@ +/********************* */ +/*! \file cdtrail_hashmap.h + ** \verbatim + ** Original author: taking + ** Major contributors: none + ** Minor contributors (to current version): none + ** This file is part of the CVC4 prototype. + ** Copyright (c) 2009-2012 New York University and The University of Iowa + ** See the file COPYING in the top-level source directory for licensing + ** information.\endverbatim + ** + ** \brief Context-dependent hashmap built using trail of elements + ** + ** Context-dependent hashmap that explicitly keeps track of its edit history. + ** This is similar in functionality to CDHashMap with fewer capabilites and + ** slight changes in the interface. It has the advantage of being lighter in + ** memory usage. + ** + ** See also: + ** CDInsertHashMap : An "insert-once" CD hash map. + ** CDHashMap : A fully featured CD hash map. (The closest to <ext/hash_map>) + ** + ** Notes: + ** - To iterate efficiently over the elements use the key_iterators. + ** - operator[] is only supported as a const derefence (must succeed). + ** - Insertions to the map are done with respect to a context. + ** - Insertions can be done in two manors either with insert() or + ** insert_no_overwrite(). + ** - insert(k,d) inserts the key data pair into the hashtable and returns a + ** false if it overwrote the previous value. + ** - insert_no_overwrite(k,d) inserts key data pair into the hashtable only + ** if the value is not already there. It returns true, if an element was + ** added. This conditionally extends the trail length if it returns true. + ** - inserts are compacting. If there is another insert to the same key + ** at the same context, the memory is reused. + ** - Iterating over const_iterators has amortized time proportional to + ** O(trail length). (If this needs to be improved, please bug Tim.) + ** - contains() and operator[] are slightly faster than using stl style + ** iterator comparisons: find(), end(), etc. + **/ + + +#include "cvc4_private.h" + +#pragma once + +#include "context/context.h" +#include "context/cdtrail_hashmap_forward.h" +#include <utility> +#include <ext/hash_map> +#include <deque> +#include "util/cvc4_assert.h" +#include "util/output.h" + +#include "expr/node.h" +#include <boost/static_assert.hpp> + + +namespace CVC4 { +namespace context { + + +template <class Key, class Data, class HashFcn = __gnu_cxx::hash<Key> > +class TrailHashMap { +public: + /** A pair of Key and Data that mirrors hash_map::value_type. */ + typedef std::pair<Key, Data> value_type; + +private: + + /** The trail information from an insert. */ + struct KDT { + /** The Key Data pair. */ + value_type d_kd; + + /** + * The previous trail entry with the same key. + * On a pop, this is the element to revert to. + * This value is a self loop if there is no previous entry. + */ + size_t d_prevKey; + + /** The whether the trail element is current. */ + bool d_current; + + KDT(const Key& key, const Data& data, size_t prev, bool cur = true): + d_kd(std::make_pair(key, data)), d_prevKey(prev), d_current(cur){ } + KDT(){} + }; + + typedef std::deque<KDT> KDTVec; + typedef typename KDTVec::const_iterator KDTVec_const_iterator; + /** The trail of elements. */ + KDTVec d_kdts; + + + typedef __gnu_cxx::hash_map<Key, size_t, HashFcn> PositionMap; + typedef typename PositionMap::iterator PM_iterator; + typedef typename PositionMap::const_iterator PM_const_iterator; + + /** A map of keys to their positions in the trail. */ + PositionMap d_posMap; + + + /** The number of unique keys in the map. */ + size_t d_uniqueKeys; + + /** Internal utility class. NonConstant find on the position map.*/ + inline PM_iterator ncfind(const Key& k) { + return d_posMap.find(k); + } + + /** Internal utility class. Position Map Find.*/ + inline PM_const_iterator pmfind(const Key& k) const{ + return d_posMap.find(k); + } + /** Internal utility class. Position Map End.*/ + inline PM_const_iterator pmend() const{ + return d_posMap.end(); + } + + /** This is true if the previous entry in the trail points at itself.*/ + inline bool selfLoop(size_t pos, const KDT& kdt) const { + return pos == kdt.d_prevKey; + } + +public: + /** + * Constant iterator for TrailHashMap. + * Only supports forward iteration. + * This always points at the end or a current element in the trail. + * This is done by iterating over the trail. + */ + class const_iterator { + private: + /** A vector iterator. */ + KDTVec_const_iterator d_it; + + /** A pointer to the end of the vector.*/ + KDTVec_const_iterator d_end; + + /** Move the iterator to the end or the next current element.*/ + void findCurrent(){ + while(d_it != d_end && !(*d_it).d_current){ + ++d_it; + } + } + + public: + + /** Constructs an iterator for a TrailHashMap. */ + const_iterator(KDTVec_const_iterator it, KDTVec_const_iterator end) : + d_it(it), + d_end(end){ + findCurrent(); + } + + /** Copy constructor for an iterator for a TrailHashMap. */ + const_iterator(const const_iterator& other) : + d_it(other.d_it), d_end(other.d_end){ + // Do not need to findCurrent() + } + + /** Returns true if the iterators are the same. */ + inline bool operator==(const const_iterator& other) const { + return d_it == other.d_it; + } + + /** Returns true if the iterators are the same. */ + inline bool operator!=(const const_iterator& other) const { + return d_it != other.d_it; + } + + /** Returns a pair<Key,Data>. */ + inline const value_type& operator*() const { + return (*d_it).d_kd; + } + + /** Prefix increment */ + const_iterator& operator++() { + ++d_it; + findCurrent(); + return *this; + } + }; + + /** Returns a beginning iterator.*/ + inline const_iterator begin() const{ + return const_iterator(d_kdts.begin(), d_kdts.end()); + } + + /** Returns an end iterator.*/ + inline const_iterator end() const{ + return const_iterator(d_kdts.end(), d_kdts.end()); + } + + /** Returns true if the trail is empty.*/ + inline bool empty() const { return d_kdts.empty(); } + + /** Returns the size of the trail.*/ + inline size_t trailSize() const { return d_kdts.size(); } + + /** Returns the number of unique keys in the map.*/ + inline size_t uniqueKeys() const { return d_uniqueKeys; } + + /** Returns true if the key is in the map.*/ + inline bool contains(const Key& k) const { + return pmfind(k) != pmend(); + } + + /** + * Returns a NON const reference to an element in the Map. + * k must be a key in the Map. + * DO NOT USE THIS UNLESS YOU ARE CONFIDENT THE CHANGES MAKE SENSE. + */ + Data& lookup(const Key& k){ + Assert(contains(k)); + PM_iterator ci = ncfind(k); + KDT& kdt = d_kdts[(*ci).second]; + return kdt.d_kd.second; + } + + /** + * Returns a const reference to an element mapped by a Key k. + * k must be a key in the Map. + */ + const Data& operator[](const Key& k) const { + PM_const_iterator pci = pmfind(k); + Assert(pci != pmend()); + return d_kdts[(*pci).second].d_kd.second; + } + + /** + * If the key k is in the map, this returns a const_iterator pointing at this + * element. Otherwise, this returns end(). + */ + const_iterator find(const Key& k) const { + PM_const_iterator pci = pmfind(k); + if(pci == pmend()){ + return end(); + }else{ + size_t pos = (*pci).second; + return const_iterator(d_kdts.begin() + pos, d_kdts.end()); + } + } + + /** + * Similar to contains, but includes a notion of trail position. + * Returns <true, true> if contains(k) and the current position of k + * in the map is greater than or equal to pos. + * Returns <true, false> if it contains(k) but not the previous condition. + * Returns <false, false> if it does not contains(k). + */ + std::pair<bool, bool> hasAfter(const Key& k, size_t pos) { + PM_iterator it = ncfind(k); + if(it != d_posMap.end()){ + return std::make_pair(true, (*it).second >= pos ); + } + return std::make_pair(false, false); + } + + /** + * Inserts an element unconditionally. + * Always increases the trail size. + * Returns true if the key count increased. + */ + bool push_back(const Key& k, const Data& d){ + std::pair<bool, bool> res = compacting_push_back(k, d, trailSize()); + return res.first; + } + + /** + * This inserts an element into the trail. + * This insert can reuse the same trail element if the postion of the element + * is >= threshold. + * + * Return values: + * If pair<bool, bool> res = compacting_push_back(..), + * then res.first is true if this is a new unique key, and + * res.second is true if the trail length increased. + * + */ + std::pair<bool, bool> compacting_push_back(const Key& k, const Data& d, size_t threshold){ + size_t backPos = d_kdts.size(); + std::pair<PM_iterator, bool> res = d_posMap.insert(std::make_pair(k, backPos)); + if(!res.second){ + size_t& prevPosInPM = (*res.first).second; + + Assert(d_kdts[prevPosInPM].d_current); + + if(prevPosInPM < threshold){ + d_kdts.push_back(KDT(k,d, prevPosInPM)); + d_kdts[prevPosInPM].d_current = false; + prevPosInPM = backPos; + + return std::make_pair(false, true); + }else{ + d_kdts[prevPosInPM].d_kd.second = d; + return std::make_pair(false, false); + } + }else{ + d_kdts.push_back(KDT(k,d, backPos)); + ++d_uniqueKeys; + return std::make_pair(true, true); + } + } + + /** + * Inserts an element if the key is not already in the map. + * Returns true if the element was inserted. + */ + bool insert_no_overwrite(const Key& k, const Data& d){ + size_t backPos = d_kdts.size(); + std::pair<PM_iterator, bool> res = d_posMap.insert(std::make_pair(k, backPos)); + if(res.second){ + d_kdts.push_back(KDT(k,d, backPos)); + ++d_uniqueKeys; + } + Debug("TrailHashMap") <<"TrailHashMap insert" << k << " d " << d << " " << backPos << std::endl; + return res.second; + } + + /** Pops the element at the back of the trail. */ + void pop_back(){ + Assert(!empty()); + const KDT& back = d_kdts.back(); + const Key& k = back.d_kd.first; + if(selfLoop(trailSize()-1, back)){ + d_posMap.erase(k); + --d_uniqueKeys; + Debug("TrailHashMap") <<"TrailHashMap pop_back erase " << trailSize() <<" " << std::endl; + + }else{ + Debug("TrailHashMap") <<"TrailHashMap reset " << trailSize() <<" " << " " << back.d_prevKey << std::endl; + d_posMap[k] = back.d_prevKey; + d_kdts[back.d_prevKey].d_current = true; + } + d_kdts.pop_back(); + } + + /** Pops the element at the back of the trail until the trailSize is <= s. */ + void pop_to_size(size_t s){ + while(trailSize() > s){ + pop_back(); + } + } +};/* class TrailHashMap<> */ + +template <class Key, class Data, class HashFcn > +class CDTrailHashMap : public ContextObj { +private: + /** A short name for the templatized TrailMap that backs the CDTrailMap. */ + typedef TrailHashMap<Key, Data, HashFcn> THM; + + /** The trail map that backs the CDTrailMap. */ + THM* d_trailMap; +public: + /** Iterator for the CDTrailHashMap. */ + typedef typename THM::const_iterator const_iterator; + + /** Return value of operator* on a const_iterator (pair<Key,Data>).*/ + typedef typename THM::value_type value_type; + +private: + /** + * The length of the trail in the current context. + * This is used to support reverting. + */ + size_t d_trailSize; + + /** + * The length of the trail immediately after the previous makeCurrent(). + * This is used to support compacting inserts. + */ + size_t d_prevTrailSize; + + /** + * Private copy constructor used only by save(). d_trailMap is not copied: + * only the base class information, d_trailSize, and d_prevTrailSize + * are needed in restore. + */ + CDTrailHashMap(const CDTrailHashMap<Key, Data, HashFcn>& l) : + ContextObj(l), + d_trailMap(NULL), + d_trailSize(l.d_trailSize), + d_prevTrailSize(l.d_prevTrailSize){ + Debug("CDTrailHashMap") << "copy ctor: " << this + << " from " << &l + << " size " << d_trailSize << std::endl; + } + + /** + * Implementation of mandatory ContextObj method save: simply copies + * the current sizes to a copy using the copy constructor, + * The saved information is allocated using the ContextMemoryManager. + */ + ContextObj* save(ContextMemoryManager* pCMM) { + ContextObj* data = new(pCMM) CDTrailHashMap<Key, Data, HashFcn>(*this); + Debug("CDTrailHashMap") << "save " << this + << " at level " << this->getContext()->getLevel() + << " size at " << this->d_trailSize + << " d_list is " << this->d_trailMap + << " data:" << data << std::endl; + return data; + } +protected: + /** + * Implementation of mandatory ContextObj method restore: simply + * restores the previous size. Note that the list pointer and the + * allocated size are not changed. + */ + void restore(ContextObj* data) { + Debug("CDTrailHashMap") << "restore " << this + << " level " << this->getContext()->getLevel() + << " data == " << data + << " d_trailMap == " << this->d_trailMap << std::endl; + size_t oldSize = ((CDTrailHashMap<Key, Data, HashFcn>*)data)->d_trailSize; + d_trailMap->pop_to_size(oldSize); + d_trailSize = oldSize; + Assert(d_trailMap->trailSize() == d_trailSize); + + d_prevTrailSize = ((CDTrailHashMap<Key, Data, HashFcn>*)data)->d_prevTrailSize; + Debug("CDTrailHashMap") << "restore " << this + << " level " << this->getContext()->getLevel() + << " size back to " << this->d_trailSize << std::endl; + } + + /** + * We need to save the d_trailSize immediately after a successful makeCurrent. + * So this version needs to be used everywhere instead of maekCurrent() + * internally. + */ + void internalMakeCurrent () { + if(!isCurrent()){ + makeCurrent(); + d_prevTrailSize = d_trailSize; + } + } + +public: + + /** + * Main constructor: d_trailMap starts as an empty map, with the sizes are 0 + */ + CDTrailHashMap(Context* context) : + ContextObj(context), + d_trailMap(new THM()), + d_trailSize(0), + d_prevTrailSize(0){ + Assert(d_trailMap->trailSize() == d_trailSize); + } + + /** + * Destructor: delete the map + */ + ~CDTrailHashMap() throw(AssertionException) { + this->destroy(); + delete d_trailMap; + } + + /** Returns true if the map is empty in the current context. */ + bool empty() const{ + return d_trailSize == 0; + } + + /** Returns true the size of the map in the current context. */ + size_t size() const { + return d_trailMap->uniqueKeys(); + } + + /** + * Inserts an element into the map. + * This always succeeds. + * Returns true if the key is new. + */ + bool insert(const Key& k, const Data& d){ + internalMakeCurrent(); + std::pair<bool, bool> res = d_trailMap->compacting_push_back(k, d, d_prevTrailSize); + if(res.second){ + ++d_trailSize; + } + Assert(d_trailMap->trailSize() == d_trailSize); + return res.first; + } + + /** + * Inserts an element into the map if the key is not already there. + * This has no side effects if the insert does not happen. + * Returns true if the element was inserted. + */ + bool insert_no_overwrite(const Key& k, const Data& d){ + bool res = d_trailMap->insert_no_overwrite(k, d); + if(res){ + internalMakeCurrent(); + ++d_trailSize; + } + Assert(d_trailMap->trailSize() == d_trailSize); + return res; + } + + /** Returns true if k is a mapped key in the context. */ + bool contains(const Key& k) const { + return d_trailMap->contains(k); + } + + /** + * Returns a reference the data mapped by k. + * k must be in the map in this context. + */ + const Data& operator[](const Key& k) const { + return (*d_trailMap)[k]; + } + /* +// While the following code "works", I wonder if it is not better to disable it? +// Non-const operator[] has strange semantics for a context-dependent +// data structure. + Data& operator[](const Key& k) { + internalMakeCurrent(); + std::pair<bool, bool> res = d_trailMap->hasAfter(k, d_prevTrailSize); + if(!res.first){ + std::pair<bool, bool> res = d_trailMap->compacting_push_back(k, Data(), d_prevTrailSize); + if(res.second){ + ++d_trailSize; + } + }else if(!res.second){ + std::pair<bool, bool> res = d_trailMap->compacting_push_back(k, (*d_trailMap)[k], d_prevTrailSize); + if(res.second){ + ++d_trailSize; + } + } + return d_trailMap->lookup(k); + } + */ + + /** + * Returns a const_iterator to the value_type if k is a mapped key in + * the context. + */ + const_iterator find(const Key& k) const { + return d_trailMap->find(k); + } + + /** Returns an iterator to the begining of the map. */ + const_iterator begin() const{ + return d_trailMap->begin(); + } + /** Returns an iterator to the end of the map. */ + const_iterator end() const{ + return d_trailMap->end(); + } + +};/* class CDTrailHashMap<> */ + +template <class Data, class HashFcn> +class CDTrailHashMap <TNode, Data, HashFcn > : public ContextObj { + /* CDTrailHashMap is challenging to get working with TNode. + * Consider using CDHashMap<TNode,...> instead. + * + * Explanation: + * CDTrailHashMap uses keys during deallocation. + * If the key is a TNode and the backing (the hard node reference) + * for the key in another data structure removes the key at the same context + * the ref count could drop to 0. The key would then not be eligible to be + * hashed. Getting the order right with a guarentee is to hard. + */ + + BOOST_STATIC_ASSERT(sizeof(Data) == 0); +}; + +}/* CVC4::context namespace */ +}/* CVC4 namespace */ diff --git a/src/context/cdtrail_hashmap_forward.h b/src/context/cdtrail_hashmap_forward.h new file mode 100644 index 000000000..549ecd738 --- /dev/null +++ b/src/context/cdtrail_hashmap_forward.h @@ -0,0 +1,38 @@ +/********************* */ +/*! \file cdtrail_hashmap_forward.h + ** \verbatim + ** Original author: taking + ** Major contributors: none + ** Minor contributors (to current version): none + ** This file is part of the CVC4 prototype. + ** Copyright (c) 2009-2012 New York University and The University of Iowa + ** See the file COPYING in the top-level source directory for licensing + ** information.\endverbatim + ** + ** \brief This is a forward declaration header to declare the + ** CDTrailHashMap<> template + ** + ** This is a forward declaration header to declare the CDTrailHashMap<> + ** template. It's useful if you want to forward-declare CDTrailHashMap<> + ** without including the full cdtrail_hash_map.h header, for example, in a + ** public header context. + ** + ** For CDTrailHashMap<> in particular, it's difficult to forward-declare it + ** yourself, because it has a default template argument. + **/ + +#include "cvc4_public.h" + +#pragma once + +namespace __gnu_cxx { + template <class Key> struct hash; +}/* __gnu_cxx namespace */ + +namespace CVC4 { + namespace context { + template <class Key, class Data, class HashFcn = __gnu_cxx::hash<Key> > + class CDTrailHashMap; + }/* CVC4::context namespace */ +}/* CVC4 namespace */ + diff --git a/src/decision/decision_engine.cpp b/src/decision/decision_engine.cpp index 22c70eb6d..9e8add752 100644 --- a/src/decision/decision_engine.cpp +++ b/src/decision/decision_engine.cpp @@ -33,7 +33,7 @@ DecisionEngine::DecisionEngine(context::Context *sc, d_enabledStrategies(), d_needIteSkolemMap(), d_relevancyStrategy(NULL), - d_assertions(), + d_assertions(uc), d_cnfStream(NULL), d_satSolver(NULL), d_satContext(sc), @@ -50,18 +50,6 @@ void DecisionEngine::init() d_engineState = 1; Trace("decision-init") << "DecisionEngine::init()" << std::endl; - if(options::incrementalSolving()) { - if(options::decisionMode() != decision::DECISION_STRATEGY_INTERNAL) { - if(options::decisionMode.wasSetByUser()) { - Warning() << "Ignorning decision option since using incremental mode (currently not supported together)" - << std::endl; - } else { - Notice() << "Using internal decision heuristic since using incremental mode (not supported currently)" - << std::endl; - } - } - return; - } Trace("decision-init") << " * options->decisionMode: " << options::decisionMode() << std:: endl; Trace("decision-init") << " * options->decisionStopOnly: " @@ -70,11 +58,16 @@ void DecisionEngine::init() if(options::decisionMode() == decision::DECISION_STRATEGY_INTERNAL) { } if(options::decisionMode() == decision::DECISION_STRATEGY_JUSTIFICATION) { ITEDecisionStrategy* ds = - new decision::JustificationHeuristic(this, d_satContext); + new decision::JustificationHeuristic(this, d_userContext, d_satContext); enableStrategy(ds); d_needIteSkolemMap.push_back(ds); } if(options::decisionMode() == decision::DECISION_STRATEGY_RELEVANCY) { + if(options::incrementalSolving()) { + Warning() << "Relevancy decision heuristic and incremental not supported together" + << std::endl; + return; // Currently not supported with incremental + } RelevancyStrategy* ds = new decision::Relevancy(this, d_satContext); enableStrategy(ds); @@ -137,7 +130,7 @@ void DecisionEngine::addAssertions(const vector<Node> &assertions, // new assertions, reset whatever result we knew d_result = SAT_VALUE_UNKNOWN; - d_assertions.reserve(assertions.size()); + // d_assertions.reserve(assertions.size()); for(unsigned i = 0; i < assertions.size(); ++i) d_assertions.push_back(assertions[i]); diff --git a/src/decision/decision_engine.h b/src/decision/decision_engine.h index 4d354af2a..ea16cec16 100644 --- a/src/decision/decision_engine.h +++ b/src/decision/decision_engine.h @@ -42,7 +42,8 @@ class DecisionEngine { vector <ITEDecisionStrategy* > d_needIteSkolemMap; RelevancyStrategy* d_relevancyStrategy; - vector <Node> d_assertions; + typedef context::CDList<Node> AssertionsList; + AssertionsList d_assertions; // PropEngine* d_propEngine; CnfStream* d_cnfStream; @@ -55,7 +56,7 @@ class DecisionEngine { context::CDO<SatValue> d_result; // Disable creating decision engine without required parameters - DecisionEngine() : d_result(NULL) {} + DecisionEngine(); // init/shutdown state unsigned d_engineState; // 0=pre-init; 1=init,pre-shutdown; 2=shutdown @@ -68,8 +69,6 @@ public: /** Destructor, currently does nothing */ ~DecisionEngine() { Trace("decision") << "Destroying decision engine" << std::endl; - for(unsigned i = 0; i < d_enabledStrategies.size(); ++i) - delete d_enabledStrategies[i]; } // void setPropEngine(PropEngine* pe) { @@ -99,14 +98,15 @@ public: /** * This is called by SmtEngine, at shutdown time, just before * destruction. It is important because there are destruction - * ordering issues between some parts of the system. For now, - * there's nothing to do here in the DecisionEngine. + * ordering issues between some parts of the system. */ void shutdown() { Assert(d_engineState == 1); d_engineState = 2; Trace("decision") << "Shutting down decision engine" << std::endl; + for(unsigned i = 0; i < d_enabledStrategies.size(); ++i) + delete d_enabledStrategies[i]; } // Interface for External World to use our services @@ -191,7 +191,7 @@ public: /** * Get the assertions. Strategies are notified when these are available. */ - const vector<Node>& getAssertions() { + AssertionsList& getAssertions() { return d_assertions; } diff --git a/src/decision/justification_heuristic.cpp b/src/decision/justification_heuristic.cpp index 4ec4588f3..46ec6f09f 100644 --- a/src/decision/justification_heuristic.cpp +++ b/src/decision/justification_heuristic.cpp @@ -74,7 +74,7 @@ void JustificationHeuristic::computeITEs(TNode n, IteList &l) for(unsigned i=0; i<n.getNumChildren(); ++i) { SkolemMap::iterator it2 = d_iteAssertions.find(n[i]); if(it2 != d_iteAssertions.end()) { - l.push_back(make_pair(n[i], it2->second)); + l.push_back(make_pair(n[i], (*it2).second)); Assert(n[i].getNumChildren() == 0); } if(d_visitedComputeITE.find(n[i]) == @@ -103,6 +103,15 @@ bool JustificationHeuristic::findSplitterRec(TNode node, SatValue desiredVal, SatLiteral* litDecision) { + /** + * Main idea + * + * Given a boolean formula "node", the goal is to try to make it + * evaluate to "desiredVal" (true/false). for instance if "node" is a AND + * formula we want to make it evaluate to true, we'd like one of the + * children to be true. this is done recursively. + */ + Trace("jh-findSplitterRec") << "findSplitterRec(" << node << ", " << desiredVal << ", .. )" << std::endl; diff --git a/src/decision/justification_heuristic.h b/src/decision/justification_heuristic.h index de6bf5095..ea67fee29 100644 --- a/src/decision/justification_heuristic.h +++ b/src/decision/justification_heuristic.h @@ -27,6 +27,8 @@ #include "decision_strategy.h" #include "context/cdhashset.h" +#include "context/cdlist.h" +#include "context/cdhashmap.h" #include "expr/node.h" #include "prop/sat_solver_types.h" @@ -44,10 +46,10 @@ public: class JustificationHeuristic : public ITEDecisionStrategy { typedef std::vector<pair<TNode,TNode> > IteList; typedef hash_map<TNode,IteList,TNodeHashFunction> IteCache; - typedef hash_map<TNode,TNode,TNodeHashFunction> SkolemMap; + typedef context::CDHashMap<TNode,TNode,TNodeHashFunction> SkolemMap; // being 'justified' is monotonic with respect to decisions - typedef context::CDHashSet<TNode,TNodeHashFunction> JustifiedSet; + typedef context::CDHashSet<Node,NodeHashFunction> JustifiedSet; JustifiedSet d_justified; context::CDO<unsigned> d_prvsIndex; @@ -59,7 +61,7 @@ class JustificationHeuristic : public ITEDecisionStrategy { * A copy of the assertions that need to be justified * directly. Doesn't have ones introduced during during ITE-removal. */ - std::vector<TNode> d_assertions; + context::CDList<TNode> d_assertions; //TNode is fine since decisionEngine has them too /** map from ite-rewrite skolem to a boolean-ite assertion */ @@ -83,13 +85,17 @@ class JustificationHeuristic : public ITEDecisionStrategy { */ hash_set<TNode,TNodeHashFunction> d_visitedComputeITE; public: - JustificationHeuristic(CVC4::DecisionEngine* de, context::Context *c): + JustificationHeuristic(CVC4::DecisionEngine* de, + context::Context *uc, + context::Context *c): ITEDecisionStrategy(de, c), d_justified(c), d_prvsIndex(c, 0), d_helfulness("decision::jh::helpfulness", 0), d_giveup("decision::jh::giveup", 0), - d_timestat("decision::jh::time") { + d_timestat("decision::jh::time"), + d_assertions(uc), + d_iteAssertions(uc) { StatisticsRegistry::registerStat(&d_helfulness); StatisticsRegistry::registerStat(&d_giveup); StatisticsRegistry::registerStat(&d_timestat); @@ -97,6 +103,7 @@ public: } ~JustificationHeuristic() { StatisticsRegistry::unregisterStat(&d_helfulness); + StatisticsRegistry::unregisterStat(&d_giveup); StatisticsRegistry::unregisterStat(&d_timestat); } prop::SatLiteral getNext(bool &stopSearch) { @@ -106,8 +113,8 @@ public: d_visited.clear(); if(Trace.isOn("justified")) { - for(JustifiedSet::iterator i = d_justified.begin(); - i != d_justified.end(); ++i) { + for(JustifiedSet::key_iterator i = d_justified.key_begin(); + i != d_justified.key_end(); ++i) { TNode n = *i; SatLiteral l = d_decisionEngine->hasSatLiteral(n) ? d_decisionEngine->getSatLiteral(n) : -1; diff --git a/src/decision/relevancy.h b/src/decision/relevancy.h index 8a6eb54ef..bfd30ddde 100644 --- a/src/decision/relevancy.h +++ b/src/decision/relevancy.h @@ -60,7 +60,7 @@ class Relevancy : public RelevancyStrategy { typedef hash_map<TNode,SatValue,TNodeHashFunction> PolarityCache; // being 'justified' is monotonic with respect to decisions - context::CDHashSet<TNode,TNodeHashFunction> d_justified; + context::CDHashSet<Node, NodeHashFunction> d_justified; context::CDO<unsigned> d_prvsIndex; IntStat d_helfulness; diff --git a/src/expr/attribute_internals.h b/src/expr/attribute_internals.h index a085161bc..9a14caec5 100644 --- a/src/expr/attribute_internals.h +++ b/src/expr/attribute_internals.h @@ -752,7 +752,7 @@ public: table_value_type table_value_type; typedef attr::AttributeTraits<table_value_type, context_dep> traits; uint64_t id = attr::LastAttributeId<table_value_type, context_dep>::s_id++; - Assert(traits::cleanup.size() == id);// sanity check + //Assert(traits::cleanup.size() == id);// sanity check traits::cleanup.push_back(attr::getCleanupStrategy<value_t, CleanupStrategy>::fn); return id; diff --git a/src/expr/expr_manager_template.h b/src/expr/expr_manager_template.h index b9cae9431..09018cbfd 100644 --- a/src/expr/expr_manager_template.h +++ b/src/expr/expr_manager_template.h @@ -43,7 +43,7 @@ class SmtEngine; class NodeManager; class Options; class IntStat; -class ExprManagerMapCollection; +struct ExprManagerMapCollection; class StatisticsRegistry; namespace expr { diff --git a/src/expr/expr_template.h b/src/expr/expr_template.h index 442d29ac9..b353ec5dc 100644 --- a/src/expr/expr_template.h +++ b/src/expr/expr_template.h @@ -67,7 +67,7 @@ namespace prop { class TheoryProxy; }/* CVC4::prop namespace */ -class ExprManagerMapCollection; +struct ExprManagerMapCollection; struct ExprHashFunction; diff --git a/src/expr/kind_template.h b/src/expr/kind_template.h index 47504b0e4..0cab4e628 100644 --- a/src/expr/kind_template.h +++ b/src/expr/kind_template.h @@ -27,7 +27,7 @@ namespace CVC4 { namespace kind { -enum Kind_t { +enum CVC4_PUBLIC Kind_t { UNDEFINED_KIND = -1, /**< undefined */ NULL_EXPR, /**< Null kind */ ${kind_decls} diff --git a/src/expr/type.cpp b/src/expr/type.cpp index cc52b11b9..4e95c0fe2 100644 --- a/src/expr/type.cpp +++ b/src/expr/type.cpp @@ -204,111 +204,48 @@ bool Type::isBoolean() const { return d_typeNode->isBoolean(); } -/** Cast to a Boolean type */ -Type::operator BooleanType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isBoolean(), this); - return BooleanType(*this); -} - /** Is this the integer type? */ bool Type::isInteger() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isInteger(); } -/** Cast to a integer type */ -Type::operator IntegerType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isInteger(), this); - return IntegerType(*this); -} - /** Is this the real type? */ bool Type::isReal() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isReal(); } -/** Cast to a real type */ -Type::operator RealType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isReal(), this); - return RealType(*this); -} - /** Is this the string type? */ bool Type::isString() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isString(); } -/** Cast to a string type */ -Type::operator StringType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isString(), this); - return StringType(*this); -} - /** Is this the bit-vector type? */ bool Type::isBitVector() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isBitVector(); } -/** Cast to a bit-vector type */ -Type::operator BitVectorType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isBitVector(), this); - return BitVectorType(*this); -} - -/** Cast to a Constructor type */ -Type::operator DatatypeType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isDatatype(), this); - return DatatypeType(*this); -} - /** Is this a datatype type? */ bool Type::isDatatype() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isDatatype() || d_typeNode->isParametricDatatype(); } -/** Cast to a Constructor type */ -Type::operator ConstructorType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isConstructor(), this); - return ConstructorType(*this); -} - /** Is this the Constructor type? */ bool Type::isConstructor() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isConstructor(); } -/** Cast to a Selector type */ -Type::operator SelectorType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isSelector(), this); - return SelectorType(*this); -} - /** Is this the Selector type? */ bool Type::isSelector() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isSelector(); } -/** Cast to a Tester type */ -Type::operator TesterType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isTester(), this); - return TesterType(*this); -} - /** Is this the Tester type? */ bool Type::isTester() const { NodeManagerScope nms(d_nodeManager); @@ -330,64 +267,30 @@ bool Type::isPredicate() const { return d_typeNode->isPredicate(); } -/** Cast to a function type */ -Type::operator FunctionType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isFunction(), this); - return FunctionType(*this); -} - /** Is this a tuple type? */ bool Type::isTuple() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isTuple(); } -/** Cast to a tuple type */ -Type::operator TupleType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isTuple(), this); - return TupleType(*this); -} - /** Is this a record type? */ bool Type::isRecord() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isRecord(); } -/** Cast to a record type */ -Type::operator RecordType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isRecord(), this); - return RecordType(*this); -} - /** Is this a symbolic expression type? */ bool Type::isSExpr() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isSExpr(); } -/** Cast to a symbolic expression type */ -Type::operator SExprType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isSExpr(), this); - return SExprType(*this); -} - /** Is this an array type? */ bool Type::isArray() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isArray(); } -/** Cast to an array type */ -Type::operator ArrayType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - return ArrayType(*this); -} - /** Is this a sort kind */ bool Type::isSort() const { NodeManagerScope nms(d_nodeManager); @@ -395,25 +298,11 @@ bool Type::isSort() const { } /** Cast to a sort type */ -Type::operator SortType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isSort(), this); - return SortType(*this); -} - -/** Is this a sort constructor kind */ bool Type::isSortConstructor() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isSortConstructor(); } -/** Cast to a sort constructor type */ -Type::operator SortConstructorType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isSortConstructor(), this); - return SortConstructorType(*this); -} - /** Is this a predicate subtype */ /* - not in release 1.0 bool Type::isPredicateSubtype() const { @@ -422,28 +311,12 @@ bool Type::isPredicateSubtype() const { } */ -/** Cast to a predicate subtype */ -/* - not in release 1.0 -Type::operator PredicateSubtype() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isPredicateSubtype(), this); - return PredicateSubtype(*this); -} -*/ - /** Is this an integer subrange */ bool Type::isSubrange() const { NodeManagerScope nms(d_nodeManager); return d_typeNode->isSubrange(); } -/** Cast to a predicate subtype */ -Type::operator SubrangeType() const throw(IllegalArgumentException) { - NodeManagerScope nms(d_nodeManager); - CheckArgument(isNull() || isSubrange(), this); - return SubrangeType(*this); -} - vector<Type> FunctionType::getArgTypes() const { NodeManagerScope nms(d_nodeManager); vector<Type> args; diff --git a/src/expr/type.h b/src/expr/type.h index 4223d71ab..ce6291cd8 100644 --- a/src/expr/type.h +++ b/src/expr/type.h @@ -30,15 +30,15 @@ namespace CVC4 { class NodeManager; -class ExprManager; -class Expr; +class CVC4_PUBLIC ExprManager; +class CVC4_PUBLIC Expr; class TypeNode; -class ExprManagerMapCollection; +struct CVC4_PUBLIC ExprManagerMapCollection; -class SmtEngine; +class CVC4_PUBLIC SmtEngine; -class Datatype; -class Record; +class CVC4_PUBLIC Datatype; +class CVC4_PUBLIC Record; template <bool ref_count> class NodeTemplate; @@ -240,60 +240,30 @@ public: bool isBoolean() const; /** - * Cast this type to a Boolean type - * @return the BooleanType - */ - operator BooleanType() const throw(IllegalArgumentException); - - /** * Is this the integer type? * @return true if the type is a integer type */ bool isInteger() const; /** - * Cast this type to a integer type - * @return the IntegerType - */ - operator IntegerType() const throw(IllegalArgumentException); - - /** * Is this the real type? * @return true if the type is a real type */ bool isReal() const; /** - * Cast this type to a real type - * @return the RealType - */ - operator RealType() const throw(IllegalArgumentException); - - /** * Is this the string type? * @return true if the type is the string type */ bool isString() const; /** - * Cast this type to a string type - * @return the StringType - */ - operator StringType() const throw(IllegalArgumentException); - - /** * Is this the bit-vector type? * @return true if the type is a bit-vector type */ bool isBitVector() const; /** - * Cast this type to a bit-vector type - * @return the BitVectorType - */ - operator BitVectorType() const throw(IllegalArgumentException); - - /** * Is this a function type? * @return true if the type is a function type */ @@ -307,132 +277,66 @@ public: bool isPredicate() const; /** - * Cast this type to a function type - * @return the FunctionType - */ - operator FunctionType() const throw(IllegalArgumentException); - - /** * Is this a tuple type? * @return true if the type is a tuple type */ bool isTuple() const; /** - * Cast this type to a tuple type - * @return the TupleType - */ - operator TupleType() const throw(IllegalArgumentException); - - /** * Is this a record type? * @return true if the type is a record type */ bool isRecord() const; /** - * Cast this type to a record type - * @return the RecordType - */ - operator RecordType() const throw(IllegalArgumentException); - - /** * Is this a symbolic expression type? * @return true if the type is a symbolic expression type */ bool isSExpr() const; /** - * Cast this type to a symbolic expression type - * @return the SExprType - */ - operator SExprType() const throw(IllegalArgumentException); - - /** * Is this an array type? * @return true if the type is a array type */ bool isArray() const; /** - * Cast this type to an array type - * @return the ArrayType - */ - operator ArrayType() const throw(IllegalArgumentException); - - /** * Is this a datatype type? * @return true if the type is a datatype type */ bool isDatatype() const; /** - * Cast this type to a datatype type - * @return the DatatypeType - */ - operator DatatypeType() const throw(IllegalArgumentException); - - /** * Is this a constructor type? * @return true if the type is a constructor type */ bool isConstructor() const; /** - * Cast this type to a constructor type - * @return the ConstructorType - */ - operator ConstructorType() const throw(IllegalArgumentException); - - /** * Is this a selector type? * @return true if the type is a selector type */ bool isSelector() const; /** - * Cast this type to a selector type - * @return the SelectorType - */ - operator SelectorType() const throw(IllegalArgumentException); - - /** * Is this a tester type? * @return true if the type is a tester type */ bool isTester() const; /** - * Cast this type to a tester type - * @return the TesterType - */ - operator TesterType() const throw(IllegalArgumentException); - - /** * Is this a sort kind? * @return true if this is a sort kind */ bool isSort() const; /** - * Cast this type to a sort type - * @return the sort type - */ - operator SortType() const throw(IllegalArgumentException); - - /** * Is this a sort constructor kind? * @return true if this is a sort constructor kind */ bool isSortConstructor() const; /** - * Cast this type to a sort constructor type - * @return the sort constructor type - */ - operator SortConstructorType() const throw(IllegalArgumentException); - - /** * Is this a predicate subtype? * @return true if this is a predicate subtype */ @@ -440,25 +344,12 @@ public: //bool isPredicateSubtype() const; /** - * Cast this type to a predicate subtype - * @return the predicate subtype - */ - // not in release 1.0 - //operator PredicateSubtype() const throw(IllegalArgumentException); - - /** * Is this an integer subrange type? * @return true if this is an integer subrange type */ bool isSubrange() const; /** - * Cast this type to an integer subrange type - * @return the integer subrange type - */ - operator SubrangeType() const throw(IllegalArgumentException); - - /** * Outputs a string representation of this type to the stream. * @param out the stream to output to */ diff --git a/src/include/cvc4_public.h b/src/include/cvc4_public.h index 6c546a147..9993e5f18 100644 --- a/src/include/cvc4_public.h +++ b/src/include/cvc4_public.h @@ -22,19 +22,7 @@ #include <stdint.h> #if defined _WIN32 || defined __CYGWIN__ -# ifdef BUILDING_DLL -# ifdef __GNUC__ -# define CVC4_PUBLIC __attribute__((__dllexport__)) -# else /* ! __GNUC__ */ -# define CVC4_PUBLIC __declspec(dllexport) -# endif /* __GNUC__ */ -# else /* BUILDING_DLL */ -# ifdef __GNUC__ -# define CVC4_PUBLIC __attribute__((__dllimport__)) -# else /* ! __GNUC__ */ -# define CVC4_PUBLIC __declspec(dllimport) -# endif /* __GNUC__ */ -# endif /* BUILDING_DLL */ +# define CVC4_PUBLIC #else /* !( defined _WIN32 || defined __CYGWIN__ ) */ # if __GNUC__ >= 4 # define CVC4_PUBLIC __attribute__ ((__visibility__("default"))) diff --git a/src/lib/Makefile.am b/src/lib/Makefile.am index a6ea59e95..61f9e2d70 100644 --- a/src/lib/Makefile.am +++ b/src/lib/Makefile.am @@ -15,5 +15,8 @@ libreplacements_la_LIBADD = \ EXTRA_DIST = \ replacements.h \ clock_gettime.c \ - clock_gettime.h - + clock_gettime.h \ + strtok_r.c \ + strtok_r.h \ + ffs.c \ + ffs.h diff --git a/src/lib/clock_gettime.c b/src/lib/clock_gettime.c index 77409c71a..e9d347438 100644 --- a/src/lib/clock_gettime.c +++ b/src/lib/clock_gettime.c @@ -18,20 +18,20 @@ #include "cvc4_private.h" -#include <stdio.h> -#include <errno.h> -#include <time.h> - #include "lib/clock_gettime.h" #ifdef __cplusplus extern "C" { #endif /* __cplusplus */ -#ifndef __APPLE__ -# warning This code assumes you're on Mac OS X, and you don't seem to be. You'll likely have problems. -#endif /* __APPLE__ */ +#if !(defined(__APPLE__) || defined(__WIN32__)) +# warning "This code assumes you're on Mac OS X or Win32, and you don't seem to be. You'll likely have problems." +#endif /* !(__APPLE__ || __WIN32__) */ +#ifdef __APPLE__ + +#include <stdio.h> +#include <errno.h> #include <mach/mach_time.h> static double s_clockconv = 0.0; @@ -64,6 +64,15 @@ long clock_gettime(clockid_t which_clock, struct timespec *tp) { return 0; } +#else /* else we're __WIN32__ */ + +long clock_gettime(clockid_t which_clock, struct timespec *tp) { + // unsupported on Windows + return 0; +} + +#endif /* __APPLE__ / __WIN32__ */ + #ifdef __cplusplus }/* extern "C" */ #endif /* __cplusplus */ diff --git a/src/lib/clock_gettime.h b/src/lib/clock_gettime.h index ac4ca1f85..ea14f885c 100644 --- a/src/lib/clock_gettime.h +++ b/src/lib/clock_gettime.h @@ -30,13 +30,19 @@ /* otherwise, we have to define it */ +#ifndef __WIN32__ + /* get timespec from <time.h> */ #include <time.h> +#endif /* ! __WIN32__ */ + #ifdef __cplusplus extern "C" { #endif /* __cplusplus */ +struct timespec; + typedef enum { CLOCK_REALTIME, CLOCK_MONOTONIC, diff --git a/src/lib/ffs.c b/src/lib/ffs.c new file mode 100644 index 000000000..5c25211ce --- /dev/null +++ b/src/lib/ffs.c @@ -0,0 +1,40 @@ +/********************* */ +/*! \file ffs.c + ** \verbatim + ** Original author: mdeters + ** Major contributors: none + ** Minor contributors (to current version): none + ** This file is part of CVC4. + ** Copyright (c) 2009-2013 New York University and The University of Iowa + ** See the file COPYING in the top-level source directory for licensing + ** information.\endverbatim + ** + ** \brief Replacement for ffs() for systems without it (like Win32) + ** + ** Replacement for ffs() for systems without it (like Win32). + **/ + +#include "cvc4_private.h" + +#include "lib/ffs.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +int ffs(int i) { + long mask = 0x1; + int pos = 1; + while(pos <= sizeof(int) * 8) { + if((mask & i) != 0) { + return pos; + } + ++pos; + mask <<= 1; + } + return 0; +} + +#ifdef __cplusplus +}/* extern "C" */ +#endif /* __cplusplus */ diff --git a/src/lib/ffs.h b/src/lib/ffs.h new file mode 100644 index 000000000..9b038d429 --- /dev/null +++ b/src/lib/ffs.h @@ -0,0 +1,42 @@ +/********************* */ +/*! \file ffs.h + ** \verbatim + ** Original author: mdeters + ** Major contributors: none + ** Minor contributors (to current version): none + ** This file is part of CVC4. + ** Copyright (c) 2009-2013 New York University and The University of Iowa + ** See the file COPYING in the top-level source directory for licensing + ** information.\endverbatim + ** + ** \brief Replacement for ffs() for systems without it (like Win32) + ** + ** Replacement for ffs() for systems without it (like Win32). + **/ + +#include "cvc4_public.h" + +#ifndef __CVC4__LIB__FFS_H +#define __CVC4__LIB__FFS_H + +#ifdef HAVE_FFS + +// available in strings.h +#include <strings.h> + +#else /* ! HAVE_FFS */ + +#include "lib/replacements.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +int ffs(int i); + +#ifdef __cplusplus +}/* extern "C" */ +#endif /* __cplusplus */ + +#endif /* HAVE_FFS */ +#endif /* __CVC4__LIB__FFS_H */ diff --git a/src/lib/strtok_r.c b/src/lib/strtok_r.c new file mode 100644 index 000000000..b8df95359 --- /dev/null +++ b/src/lib/strtok_r.c @@ -0,0 +1,41 @@ +/********************* */ +/*! \file strtok_r.c + ** \verbatim + ** Original author: mdeters + ** Major contributors: none + ** Minor contributors (to current version): none + ** This file is part of CVC4. + ** Copyright (c) 2009-2013 New York University and The University of Iowa + ** See the file COPYING in the top-level source directory for licensing + ** information.\endverbatim + ** + ** \brief Replacement for strtok_r() for systems without it (like Win32) + ** + ** Replacement for strtok_r() for systems without it (like Win32). + **/ + +#include "cvc4_private.h" + +#include "lib/strtok_r.h" +#include <stdio.h> +#include <string.h> + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +char* strtok_r(char *str, const char *delim, char **saveptr) { + if(str == NULL) { + char* retval = strtok(*saveptr, delim); + *saveptr = retval + strlen(retval) + 1; + return retval; + } else { + char* retval = strtok(str, delim); + *saveptr = retval + strlen(retval) + 1; + return retval; + } +} + +#ifdef __cplusplus +}/* extern "C" */ +#endif /* __cplusplus */ diff --git a/src/lib/strtok_r.h b/src/lib/strtok_r.h new file mode 100644 index 000000000..6b3387e6b --- /dev/null +++ b/src/lib/strtok_r.h @@ -0,0 +1,42 @@ +/********************* */ +/*! \file strtok_r.h + ** \verbatim + ** Original author: mdeters + ** Major contributors: none + ** Minor contributors (to current version): none + ** This file is part of CVC4. + ** Copyright (c) 2009-2013 New York University and The University of Iowa + ** See the file COPYING in the top-level source directory for licensing + ** information.\endverbatim + ** + ** \brief Replacement for strtok_r() for systems without it (like Win32) + ** + ** Replacement for strtok_r() for systems without it (like Win32). + **/ + +#include "cvc4_public.h" + +#ifndef __CVC4__LIB__STRTOK_R_H +#define __CVC4__LIB__STRTOK_R_H + +#ifdef HAVE_STRTOK_R + +// available in string.h +#include <string.h> + +#else /* ! HAVE_STRTOK_R */ + +#include "lib/replacements.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +char* strtok_r(char *str, const char *delim, char **saveptr); + +#ifdef __cplusplus +}/* extern "C" */ +#endif /* __cplusplus */ + +#endif /* HAVE_STRTOK_R */ +#endif /* __CVC4__LIB__STRTOK_R_H */ diff --git a/src/main/Makefile.am b/src/main/Makefile.am index 952951655..64a43eb02 100644 --- a/src/main/Makefile.am +++ b/src/main/Makefile.am @@ -41,9 +41,9 @@ pcvc4_LDADD += $(BOOST_THREAD_LIBS) -lpthread pcvc4_LDADD += $(BOOST_THREAD_LDFLAGS) if STATIC_BINARY -pcvc4_LINK = $(CXXLINK) -all-static +pcvc4_LINK = $(CXXLINK) -all-static $(pcvc4_LDFLAGS) else -pcvc4_LINK = $(CXXLINK) +pcvc4_LINK = $(CXXLINK) $(pcvc4_LDFLAGS) endif endif @@ -87,8 +87,8 @@ clean-local: rm -f $(BUILT_SOURCES) if STATIC_BINARY -cvc4_LINK = $(CXXLINK) -all-static +cvc4_LINK = $(CXXLINK) -all-static $(cvc4_LDFLAGS) else -cvc4_LINK = $(CXXLINK) +cvc4_LINK = $(CXXLINK) $(cvc4_LDFLAGS) endif diff --git a/src/main/util.cpp b/src/main/util.cpp index 5e7436580..9ade23630 100644 --- a/src/main/util.cpp +++ b/src/main/util.cpp @@ -19,10 +19,15 @@ #include <cerrno> #include <exception> #include <string.h> + +#ifndef __WIN32__ + #include <signal.h> #include <sys/resource.h> #include <unistd.h> +#endif /* __WIN32__ */ + #include "util/exception.h" #include "options/options.h" #include "util/statistics.h" @@ -44,9 +49,6 @@ namespace CVC4 { namespace main { -size_t cvc4StackSize; -void* cvc4StackBase; - /** * If true, will not spin on segfault even when CVC4_DEBUG is on. * Useful for nightly regressions, noninteractive performance runs @@ -54,6 +56,11 @@ void* cvc4StackBase; */ bool segvNoSpin = false; +#ifndef __WIN32__ + +size_t cvc4StackSize; +void* cvc4StackBase; + /** Handler for SIGXCPU, i.e., timeout. */ void timeout_handler(int sig, siginfo_t* info, void*) { fprintf(stderr, "CVC4 interrupted by timeout.\n"); @@ -144,10 +151,12 @@ void ill_handler(int sig, siginfo_t* info, void*) { #endif /* CVC4_DEBUG */ } +#endif /* __WIN32__ */ + static terminate_handler default_terminator; void cvc4unexpected() { -#ifdef CVC4_DEBUG +#if defined(CVC4_DEBUG) && !defined(__WIN32__) fprintf(stderr, "\n" "CVC4 threw an \"unexpected\" exception (one that wasn't properly " "specified\nin the throws() specifier for the throwing function)." @@ -204,6 +213,7 @@ void cvc4terminate() { /** Initialize the driver. Sets signal handlers for SIGINT and SIGSEGV. */ void cvc4_init() throw(Exception) { +#ifndef __WIN32__ stack_t ss; ss.ss_sp = malloc(SIGSTKSZ); if(ss.ss_sp == NULL) { @@ -262,6 +272,8 @@ void cvc4_init() throw(Exception) { throw Exception(string("sigaction(SIGILL) failure: ") + strerror(errno)); } +#endif /* __WIN32__ */ + set_unexpected(cvc4unexpected); default_terminator = set_terminate(cvc4terminate); } diff --git a/src/options/options.h b/src/options/options.h index 2d49765f3..5f17f5a5c 100644 --- a/src/options/options.h +++ b/src/options/options.h @@ -31,7 +31,7 @@ namespace CVC4 { namespace options { - class OptionsHolder; + struct OptionsHolder; }/* CVC4::options namespace */ class ExprStream; diff --git a/src/parser/memory_mapped_input_buffer.cpp b/src/parser/memory_mapped_input_buffer.cpp index 9f72ac51c..f110b1145 100644 --- a/src/parser/memory_mapped_input_buffer.cpp +++ b/src/parser/memory_mapped_input_buffer.cpp @@ -18,10 +18,15 @@ #include <stdio.h> #include <stdint.h> +#include <antlr3input.h> + +#ifndef _WIN32 + #include <cerrno> #include <sys/mman.h> #include <sys/stat.h> -#include <antlr3input.h> + +#endif /* _WIN32 */ #include "parser/memory_mapped_input_buffer.h" #include "util/exception.h" @@ -31,6 +36,14 @@ namespace parser { extern "C" { +#ifdef _WIN32 + +pANTLR3_INPUT_STREAM MemoryMappedInputBufferNew(const std::string& filename) { + return 0; +} + +#else /* ! _WIN32 */ + static ANTLR3_UINT32 MemoryMapFile(pANTLR3_INPUT_STREAM input, const std::string& filename); @@ -112,6 +125,8 @@ void UnmapFile(pANTLR3_INPUT_STREAM input) { input->close(input); } +#endif /* _WIN32 */ + }/* extern "C" */ }/* CVC4::parser namespace */ diff --git a/src/parser/smt1/Smt1.g b/src/parser/smt1/Smt1.g index 6dade9530..0f76baace 100644 --- a/src/parser/smt1/Smt1.g +++ b/src/parser/smt1/Smt1.g @@ -1,4 +1,3 @@ -/* ******************* */ /*! \file Smt1.g ** \verbatim ** Original author: cconway @@ -235,10 +234,10 @@ annotatedFormula[CVC4::Expr& expr] Expr op; /* Operator expression FIXME: move away kill it */ } : /* a built-in operator application */ - LPAREN_TOK builtinOp[kind] annotatedFormulas[args,expr] RPAREN_TOK + LPAREN_TOK builtinOp[kind] annotatedFormulas[args,expr] { if((kind == CVC4::kind::AND || kind == CVC4::kind::OR) && args.size() == 1) { /* Unary AND/OR can be replaced with the argument. - It just so happens expr should already by the only argument. */ + * It just so happens expr should already be the only argument. */ assert( expr == args[0] ); } else if( CVC4::kind::isAssociative(kind) && args.size() > EXPR_MANAGER->maxArity(kind) ) { @@ -253,6 +252,7 @@ annotatedFormula[CVC4::Expr& expr] expr = MK_EXPR(kind, args); } } + termAnnotation[expr]* RPAREN_TOK | /* A quantifier */ LPAREN_TOK @@ -261,12 +261,13 @@ annotatedFormula[CVC4::Expr& expr] ( LPAREN_TOK let_identifier[name,CHECK_NONE] t=sortSymbol RPAREN_TOK { args.push_back(PARSER_STATE->mkBoundVar(name, t)); } )+ - annotatedFormula[expr] RPAREN_TOK + annotatedFormula[expr] { args2.push_back( MK_EXPR( kind::BOUND_VAR_LIST, args ) ); args2.push_back(expr); expr = MK_EXPR(kind, args2); - PARSER_STATE->popScope(); } + termAnnotation[expr]* RPAREN_TOK + { PARSER_STATE->popScope(); } | /* A non-built-in function application */ @@ -275,9 +276,10 @@ annotatedFormula[CVC4::Expr& expr] // { isFunction(LT(2)->getText()) }? LPAREN_TOK parameterizedOperator[op] - annotatedFormulas[args,expr] RPAREN_TOK + annotatedFormulas[args,expr] // TODO: check arity { expr = MK_EXPR(op,args); } + termAnnotation[expr]* RPAREN_TOK | /* An ite expression */ LPAREN_TOK ITE_TOK @@ -286,9 +288,9 @@ annotatedFormula[CVC4::Expr& expr] annotatedFormula[expr] { args.push_back(expr); } annotatedFormula[expr] - { args.push_back(expr); } - RPAREN_TOK - { expr = MK_EXPR(CVC4::kind::ITE, args); } + { args.push_back(expr); + expr = MK_EXPR(CVC4::kind::ITE, args); } + termAnnotation[expr]* RPAREN_TOK | /* a let/flet binding */ LPAREN_TOK @@ -298,7 +300,7 @@ annotatedFormula[CVC4::Expr& expr] { PARSER_STATE->pushScope(); PARSER_STATE->defineVar(name,expr); } annotatedFormula[expr] - RPAREN_TOK + termAnnotation[expr]* RPAREN_TOK { PARSER_STATE->popScope(); } /* constants */ @@ -310,7 +312,7 @@ annotatedFormula[CVC4::Expr& expr] { // FIXME: This doesn't work because an SMT rational is not a // valid GMP rational string expr = MK_CONST( AntlrInput::tokenToRational($RATIONAL_TOK) ); } - | n = BITVECTOR_BV_CONST '[' size = NUMERAL_TOK ']' + | n = BITVECTOR_BV_CONST '[' size = NUMERAL_TOK ']' { expr = MK_CONST( AntlrInput::tokenToBitvector($n, $size) ); } // NOTE: Theory constants go here /* TODO: quantifiers, arithmetic constants */ @@ -320,7 +322,6 @@ annotatedFormula[CVC4::Expr& expr] | let_identifier[name,CHECK_DECLARED] | flet_identifier[name,CHECK_DECLARED] ) { expr = PARSER_STATE->getVariable(name); } - ; /** @@ -458,7 +459,7 @@ functionSymbol[CVC4::Expr& fun] * Matches an attribute name from the input (:attribute_name). */ attribute[std::string& s] - : ATTR_IDENTIFIER + : ATTR_IDENTIFIER { s = AntlrInput::tokenText($ATTR_IDENTIFIER); } ; @@ -555,28 +556,56 @@ status[ CVC4::BenchmarkStatus& status ] /** * Matches an annotation, which is an attribute name, with an optional user + * value. */ annotation[CVC4::Command*& smt_command] @init { - std::string key; + std::string key, value; smt_command = NULL; + std::vector<Expr> pats; + Expr pat; } - : attribute[key] - ( USER_VALUE - { std::string value = AntlrInput::tokenText($USER_VALUE); - assert(*value.begin() == '{'); - assert(*value.rbegin() == '}'); - // trim whitespace - value.erase(value.begin(), value.begin() + 1); - value.erase(value.begin(), std::find_if(value.begin(), value.end(), std::not1(std::ptr_fun<int, int>(std::isspace)))); - value.erase(value.end() - 1); - value.erase(std::find_if(value.rbegin(), value.rend(), std::not1(std::ptr_fun<int, int>(std::isspace))).base(), value.end()); - smt_command = new SetInfoCommand(key.c_str() + 1, value); } - )? - { if(smt_command == NULL) { - smt_command = new EmptyCommand(std::string("annotation: ") + key); + : PATTERN_ANNOTATION_BEGIN + { PARSER_STATE->warning(":pat not supported here; ignored"); } + annotatedFormulas[pats,pat] '}' + | attribute[key] + ( userValue[value] + { smt_command = new SetInfoCommand(key.c_str() + 1, value); } + | { smt_command = new EmptyCommand(std::string("annotation: ") + key); } + ) + ; + +/** + * Matches an annotation, which is an attribute name, with an optional user + * value. + */ +termAnnotation[CVC4::Expr& expr] +@init { + std::string key, value; + std::vector<Expr> pats; + Expr pat; +} + : PATTERN_ANNOTATION_BEGIN annotatedFormulas[pats,pat] '}' + { if(expr.getKind() == kind::FORALL || expr.getKind() == kind::EXISTS) { + pat = MK_EXPR(kind::INST_PATTERN, pats); + if(expr.getNumChildren() == 3) { + // we have other user patterns attached to the quantifier + // already; add this one to the existing list + pats = expr[2].getChildren(); + pats.push_back(pat); + expr = MK_EXPR(expr.getKind(), expr[0], expr[1], MK_EXPR(kind::INST_PATTERN_LIST, pats)); + } else { + // this is the only user pattern for the quantifier + expr = MK_EXPR(expr.getKind(), expr[0], expr[1], MK_EXPR(kind::INST_PATTERN_LIST, pat)); + } + } else { + PARSER_STATE->warning(":pat only supported on quantifiers"); } } + | ':pat' + { PARSER_STATE->warning("expected an instantiation pattern after :pat"); } + | attribute[key] userValue[value]? + { PARSER_STATE->attributeNotSupported(key); } ; /** @@ -752,6 +781,15 @@ FLET_IDENTIFIER * only constraint imposed on a user-defined value is that it start * with an open brace and end with closed brace. */ +userValue[std::string& s] + : USER_VALUE + { s = AntlrInput::tokenText($USER_VALUE); } + ; + +PATTERN_ANNOTATION_BEGIN + : ':pat' (' ' | '\t' | '\f' | '\r' | '\n')* '{' + ; + USER_VALUE : '{' ('\\{' | '\\}' | ~('{' | '}'))* '}' ; diff --git a/src/printer/smt2/smt2_printer.cpp b/src/printer/smt2/smt2_printer.cpp index 5821fbc77..000fd2fbf 100644 --- a/src/printer/smt2/smt2_printer.cpp +++ b/src/printer/smt2/smt2_printer.cpp @@ -541,6 +541,13 @@ void Smt2Printer::toStream(std::ostream& out, const CommandStatus* s) const thro }/* Smt2Printer::toStream(CommandStatus*) */ +void Smt2Printer::toStream(std::ostream& out, Model& m) const throw() { + out << "(model" << std::endl; + this->Printer::toStream(out, m); + out << ")" << std::endl; +} + + void Smt2Printer::toStream(std::ostream& out, Model& m, const Command* c) const throw() { theory::TheoryModel& tm = (theory::TheoryModel&) m; if(dynamic_cast<const DeclareTypeCommand*>(c) != NULL) { diff --git a/src/printer/smt2/smt2_printer.h b/src/printer/smt2/smt2_printer.h index c6d932457..32a0c94ba 100644 --- a/src/printer/smt2/smt2_printer.h +++ b/src/printer/smt2/smt2_printer.h @@ -30,6 +30,7 @@ namespace smt2 { class Smt2Printer : public CVC4::Printer { void toStream(std::ostream& out, TNode n, int toDepth, bool types) const throw(); void toStream(std::ostream& out, Model& m, const Command* c) const throw(); + void toStream(std::ostream& out, Model& m) const throw(); public: void toStream(std::ostream& out, TNode n, int toDepth, bool types, size_t dag) const throw(); void toStream(std::ostream& out, const Command* c, int toDepth, bool types, size_t dag) const throw(); diff --git a/src/proof/proof_manager.cpp b/src/proof/proof_manager.cpp index d05fe24a7..c1351c6a2 100644 --- a/src/proof/proof_manager.cpp +++ b/src/proof/proof_manager.cpp @@ -26,7 +26,7 @@ namespace CVC4 { bool ProofManager::isInitialized = false; ProofManager* ProofManager::proofManager = NULL; -ProofManager::ProofManager(ProofFormat format = LFSC): +ProofManager::ProofManager(ProofFormat format): d_satProof(NULL), d_cnfProof(NULL), d_format(format) diff --git a/src/proof/proof_manager.h b/src/proof/proof_manager.h index 3bfff1456..91eb2ed99 100644 --- a/src/proof/proof_manager.h +++ b/src/proof/proof_manager.h @@ -52,7 +52,7 @@ class ProofManager { static ProofManager* proofManager; static bool isInitialized; - ProofManager(ProofFormat format); + ProofManager(ProofFormat format = LFSC); public: static ProofManager* currentPM(); diff --git a/src/prop/bvminisat/core/Solver.cc b/src/prop/bvminisat/core/Solver.cc index 978ac8d7b..68969c78b 100644 --- a/src/prop/bvminisat/core/Solver.cc +++ b/src/prop/bvminisat/core/Solver.cc @@ -32,7 +32,7 @@ OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWA #include "theory/interrupted.h" using namespace BVMinisat; -namespace CVC4 { +namespace BVMinisat { #define OUTPUT_TAG "bvminisat: [a=" << assumptions.size() << ",l=" << decisionLevel() << "] " diff --git a/src/prop/cnf_stream.cpp b/src/prop/cnf_stream.cpp index 9f2138e9d..89cd731e9 100644 --- a/src/prop/cnf_stream.cpp +++ b/src/prop/cnf_stream.cpp @@ -108,11 +108,10 @@ void TseitinCnfStream::ensureLiteral(TNode n) { Debug("cnf") << "ensureLiteral(" << n << ")" << endl; if(hasLiteral(n)) { SatLiteral lit = getLiteral(n); - LiteralToNodeMap::iterator i = d_literalToNodeMap.find(lit); - if(i == d_literalToNodeMap.end()) { + if(!d_literalToNodeMap.contains(lit)){ // Store backward-mappings - d_literalToNodeMap[lit] = n; - d_literalToNodeMap[~lit] = n.notNode(); + d_literalToNodeMap.insert(lit, n); + d_literalToNodeMap.insert(~lit, n.notNode()); } return; } @@ -140,8 +139,9 @@ void TseitinCnfStream::ensureLiteral(TNode n) { lit = toCNF(n, false); // Store backward-mappings - d_literalToNodeMap[lit] = n; - d_literalToNodeMap[~lit] = n.notNode(); + // These may already exist + d_literalToNodeMap.insert_safe(lit, n); + d_literalToNodeMap.insert_safe(~lit, n.notNode()); } else { // We have a theory atom or variable. lit = convertAtom(n); @@ -168,8 +168,8 @@ SatLiteral CnfStream::newLiteral(TNode node, bool theoryLiteral) { } else { lit = SatLiteral(d_satSolver->newVar(theoryLiteral)); } - d_nodeToLiteralMap[node] = lit; - d_nodeToLiteralMap[node.notNode()] = ~lit; + d_nodeToLiteralMap.insert(node, lit); + d_nodeToLiteralMap.insert(node.notNode(), ~lit); } else { lit = getLiteral(node); } @@ -178,8 +178,9 @@ SatLiteral CnfStream::newLiteral(TNode node, bool theoryLiteral) { if ( theoryLiteral || d_fullLitToNodeMap || ( CVC4_USE_REPLAY && options::replayLog() != NULL ) || (Dump.isOn("clauses")) ) { - d_literalToNodeMap[lit] = node; - d_literalToNodeMap[~lit] = node.notNode(); + + d_literalToNodeMap.insert_safe(lit, node); + d_literalToNodeMap.insert_safe(~lit, node.notNode()); } // If a theory literal, we pre-register it @@ -197,11 +198,8 @@ SatLiteral CnfStream::newLiteral(TNode node, bool theoryLiteral) { TNode CnfStream::getNode(const SatLiteral& literal) { Debug("cnf") << "getNode(" << literal << ")" << endl; - LiteralToNodeMap::iterator find = d_literalToNodeMap.find(literal); - Assert(find != d_literalToNodeMap.end()); - Assert(d_nodeToLiteralMap.find((*find).second) != d_nodeToLiteralMap.end()); - Debug("cnf") << "getNode(" << literal << ") => " << (*find).second << endl; - return (*find).second; + Debug("cnf") << "getNode(" << literal << ") => " << d_literalToNodeMap[literal] << endl; + return d_literalToNodeMap[literal]; } void CnfStream::getBooleanVariables(std::vector<TNode>& outputVariables) const { @@ -229,10 +227,9 @@ SatLiteral CnfStream::convertAtom(TNode node) { } SatLiteral CnfStream::getLiteral(TNode node) { - NodeToLiteralMap::iterator find = d_nodeToLiteralMap.find(node); Assert(!node.isNull(), "CnfStream: can't getLiteral() of null node"); - Assert(find != d_nodeToLiteralMap.end(), "Literal not in the CNF Cache: %s\n", node.toString().c_str()); - SatLiteral literal = (*find).second; + Assert(d_nodeToLiteralMap.contains(node), "Literal not in the CNF Cache: %s\n", node.toString().c_str()); + SatLiteral literal = d_nodeToLiteralMap[node]; Debug("cnf") << "CnfStream::getLiteral(" << node << ") => " << literal << std::endl; return literal; } diff --git a/src/prop/cnf_stream.h b/src/prop/cnf_stream.h index 6ab639712..042cccd56 100644 --- a/src/prop/cnf_stream.h +++ b/src/prop/cnf_stream.h @@ -29,6 +29,7 @@ #include "prop/theory_proxy.h" #include "prop/registrar.h" #include "context/cdlist.h" +#include "context/cdinsert_hashmap.h" #include <ext/hash_map> @@ -47,10 +48,10 @@ class CnfStream { public: /** Cache of what nodes have been registered to a literal. */ - typedef context::CDHashMap<SatLiteral, TNode, SatLiteralHashFunction> LiteralToNodeMap; + typedef context::CDInsertHashMap<SatLiteral, TNode, SatLiteralHashFunction> LiteralToNodeMap; /** Cache of what literals have been registered to a node. */ - typedef context::CDHashMap<Node, SatLiteral, NodeHashFunction> NodeToLiteralMap; + typedef context::CDInsertHashMap<Node, SatLiteral, NodeHashFunction> NodeToLiteralMap; protected: diff --git a/src/prop/sat_solver.h b/src/prop/sat_solver.h index e5d876b48..b4807b021 100644 --- a/src/prop/sat_solver.h +++ b/src/prop/sat_solver.h @@ -130,8 +130,6 @@ public: };/* class DPLLSatSolverInterface */ -}/* CVC4::prop namespace */ - inline std::ostream& operator <<(std::ostream& out, prop::SatLiteral lit) { out << lit.toString(); return out; @@ -167,6 +165,7 @@ inline std::ostream& operator <<(std::ostream& out, prop::SatValue val) { return out; } +}/* CVC4::prop namespace */ }/* CVC4 namespace */ #endif /* __CVC4__PROP__SAT_MODULE_H */ diff --git a/src/smt/options_handlers.h b/src/smt/options_handlers.h index a3065f29b..a0a6429a8 100644 --- a/src/smt/options_handlers.h +++ b/src/smt/options_handlers.h @@ -23,6 +23,7 @@ #include "util/dump.h" #include "smt/modal_exception.h" #include "smt/smt_engine.h" +#include "lib/strtok_r.h" #include <cerrno> #include <cstring> diff --git a/src/smt/smt_engine.h b/src/smt/smt_engine.h index 3edcd6872..cdae68d96 100644 --- a/src/smt/smt_engine.h +++ b/src/smt/smt_engine.h @@ -47,7 +47,7 @@ namespace CVC4 { template <bool ref_count> class NodeTemplate; typedef NodeTemplate<true> Node; typedef NodeTemplate<false> TNode; -class NodeHashFunction; +struct NodeHashFunction; class Command; class GetModelCommand; @@ -77,7 +77,7 @@ namespace smt { */ class DefinedFunction; - class SmtEngineStatistics; + struct SmtEngineStatistics; class SmtEnginePrivate; class SmtScope; class BooleanTermConverter; diff --git a/src/theory/arith/Makefile.am b/src/theory/arith/Makefile.am index b2d1b9f09..76d8d9083 100644 --- a/src/theory/arith/Makefile.am +++ b/src/theory/arith/Makefile.am @@ -9,6 +9,7 @@ libarith_la_SOURCES = \ theory_arith_type_rules.h \ type_enumerator.h \ arithvar.h \ + arithvar.cpp \ arith_rewriter.h \ arith_rewriter.cpp \ arith_static_learner.h \ diff --git a/src/theory/arith/arith_static_learner.cpp b/src/theory/arith/arith_static_learner.cpp index 5b8d3befc..4ee176cf1 100644 --- a/src/theory/arith/arith_static_learner.cpp +++ b/src/theory/arith/arith_static_learner.cpp @@ -19,6 +19,7 @@ #include "theory/arith/arith_utilities.h" #include "theory/arith/arith_static_learner.h" +#include "theory/arith/options.h" #include "util/propositional_query.h" @@ -61,6 +62,13 @@ ArithStaticLearner::Statistics::~Statistics(){ StatisticsRegistry::unregisterStat(&d_avgNumMiplibtrickValues); } +void ArithStaticLearner::miplibTrickInsert(Node key, Node value){ + if(options::arithMLTrick()){ + d_miplibTrick.insert(key, value); + } +} + + void ArithStaticLearner::staticLearning(TNode n, NodeBuilder<>& learned){ vector<TNode> workList; @@ -138,15 +146,16 @@ void ArithStaticLearner::process(TNode n, NodeBuilder<>& learned, const TNodeSet TNode var = n[1][0]; Node current = (d_miplibTrick.find(var) == d_miplibTrick.end()) ? mkBoolNode(false) : d_miplibTrick[var]; - d_miplibTrick.insert(var, n.orNode(current)); + + miplibTrickInsert(var, n.orNode(current)); Debug("arith::miplib") << "insert " << var << " const " << n << endl; } } break; case CONST_RATIONAL: // Mark constants as minmax - d_minMap[n] = n.getConst<Rational>(); - d_maxMap[n] = n.getConst<Rational>(); + d_minMap.insert(n, n.getConst<Rational>()); + d_maxMap.insert(n, n.getConst<Rational>()); break; case OR: { // Look for things like "x = 0 OR x = 1" (that are defTrue) and @@ -248,7 +257,7 @@ void ArithStaticLearner::iteConstant(TNode n, NodeBuilder<>& learned){ DeltaRational min = std::min(first, second); CDNodeToMinMaxMap::const_iterator minFind = d_minMap.find(n); if (minFind == d_minMap.end() || (*minFind).second < min) { - d_minMap[n] = min; + d_minMap.insert(n, min); Node nGeqMin; if (min.getInfinitesimalPart() == 0) { nGeqMin = NodeBuilder<2>(kind::GEQ) << n << mkRationalNode(min.getNoninfinitesimalPart()); @@ -267,7 +276,7 @@ void ArithStaticLearner::iteConstant(TNode n, NodeBuilder<>& learned){ DeltaRational max = std::max(first, second); CDNodeToMinMaxMap::const_iterator maxFind = d_maxMap.find(n); if (maxFind == d_maxMap.end() || (*maxFind).second > max) { - d_maxMap[n] = max; + d_maxMap.insert(n, max); Node nLeqMax; if (max.getInfinitesimalPart() == 0) { nLeqMax = NodeBuilder<2>(kind::LEQ) << n << mkRationalNode(max.getNoninfinitesimalPart()); @@ -338,7 +347,7 @@ void ArithStaticLearner::postProcess(NodeBuilder<>& learned){ Result isTaut = PropositionalQuery::isTautology(possibleTaut); if(isTaut == Result(Result::VALID)){ miplibTrick(var, values, learned); - d_miplibTrick.insert(var, mkBoolNode(false)); + miplibTrickInsert(var, mkBoolNode(false)); } ++keyIter; } @@ -398,7 +407,7 @@ void ArithStaticLearner::addBound(TNode n) { /* fall through */ case kind::LEQ: if (maxFind == d_maxMap.end() || (*maxFind).second > bound) { - d_maxMap[n[0]] = bound; + d_maxMap.insert(n[0], bound); Debug("arith::static") << "adding bound " << n << endl; } break; @@ -407,7 +416,7 @@ void ArithStaticLearner::addBound(TNode n) { /* fall through */ case kind::GEQ: if (minFind == d_minMap.end() || (*minFind).second < bound) { - d_minMap[n[0]] = bound; + d_minMap.insert(n[0], bound); Debug("arith::static") << "adding bound " << n << endl; } break; diff --git a/src/theory/arith/arith_static_learner.h b/src/theory/arith/arith_static_learner.h index b047018e8..041ae6339 100644 --- a/src/theory/arith/arith_static_learner.h +++ b/src/theory/arith/arith_static_learner.h @@ -27,7 +27,7 @@ #include "context/context.h" #include "context/cdlist.h" -#include "context/cdhashmap.h" +#include "context/cdtrail_hashmap.h" #include <set> namespace CVC4 { @@ -41,17 +41,16 @@ private: * (=> _ (= x c)) * where c is a constant. */ - //typedef __gnu_cxx::hash_map<Node, std::set<Node>, NodeHashFunction> VarToNodeSetMap; - typedef context::CDHashMap<Node, Node, NodeHashFunction> CDNodeToNodeListMap; + typedef context::CDTrailHashMap<Node, Node, NodeHashFunction> CDNodeToNodeListMap; // The domain is an implicit list OR(x, OR(y, ..., FALSE )) // or FALSE CDNodeToNodeListMap d_miplibTrick; + void miplibTrickInsert(Node key, Node value); /** * Map from a node to it's minimum and maximum. */ - //typedef __gnu_cxx::hash_map<Node, DeltaRational, NodeHashFunction> NodeToMinMaxMap; - typedef context::CDHashMap<Node, DeltaRational, NodeHashFunction> CDNodeToMinMaxMap; + typedef context::CDTrailHashMap<Node, DeltaRational, NodeHashFunction> CDNodeToMinMaxMap; CDNodeToMinMaxMap d_minMap; CDNodeToMinMaxMap d_maxMap; diff --git a/src/theory/arith/arith_utilities.h b/src/theory/arith/arith_utilities.h index c7f511a98..76210fc7c 100644 --- a/src/theory/arith/arith_utilities.h +++ b/src/theory/arith/arith_utilities.h @@ -168,59 +168,6 @@ inline int deltaCoeff(Kind k){ } } - -// template <bool selectLeft> -// inline TNode getSide(TNode assertion, Kind simpleKind){ -// switch(simpleKind){ -// case kind::LT: -// case kind::GT: -// case kind::DISTINCT: -// return selectLeft ? (assertion[0])[0] : (assertion[0])[1]; -// case kind::LEQ: -// case kind::GEQ: -// case kind::EQUAL: -// return selectLeft ? assertion[0] : assertion[1]; -// default: -// Unreachable(); -// return TNode::null(); -// } -// } - -// inline DeltaRational determineRightConstant(TNode assertion, Kind simpleKind){ -// TNode right = getSide<false>(assertion, simpleKind); - -// Assert(right.getKind() == kind::CONST_RATIONAL); -// const Rational& noninf = right.getConst<Rational>(); - -// Rational inf = Rational(Integer(deltaCoeff(simpleKind))); -// return DeltaRational(noninf, inf); -// } - -// inline DeltaRational asDeltaRational(TNode n){ -// Kind simp = simplifiedKind(n); -// return determineRightConstant(n, simp); -// } - -// /** -// * Takes two nodes with exactly 2 children, -// * the second child of both are of kind CONST_RATIONAL, -// * and compares value of the two children. -// * This is for comparing inequality nodes. -// * RightHandRationalLT((<= x 50), (< x 75)) == true -// */ -// struct RightHandRationalLT -// { -// bool operator()(TNode s1, TNode s2) const -// { -// TNode rh1 = s1[1]; -// TNode rh2 = s2[1]; -// const Rational& c1 = rh1.getConst<Rational>(); -// const Rational& c2 = rh2.getConst<Rational>(); -// int cmpRes = c1.cmp(c2); -// return cmpRes < 0; -// } -// }; - inline Node negateConjunctionAsClause(TNode conjunction){ Assert(conjunction.getKind() == kind::AND); NodeBuilder<> orBuilder(kind::OR); diff --git a/src/theory/arith/arithvar.cpp b/src/theory/arith/arithvar.cpp new file mode 100644 index 000000000..76b143fff --- /dev/null +++ b/src/theory/arith/arithvar.cpp @@ -0,0 +1,13 @@ + +#include "theory/arith/arithvar.h" +#include <limits> + +namespace CVC4 { +namespace theory { +namespace arith { + +const ArithVar ARITHVAR_SENTINEL = std::numeric_limits<ArithVar>::max(); + +}/* CVC4::theory::arith namespace */ +}/* CVC4::theory namespace */ +}/* CVC4 namespace */ diff --git a/src/theory/arith/arithvar.h b/src/theory/arith/arithvar.h index 7cb6c6e99..95614a011 100644 --- a/src/theory/arith/arithvar.h +++ b/src/theory/arith/arithvar.h @@ -22,24 +22,23 @@ #ifndef __CVC4__THEORY__ARITH__ARITHVAR_H #define __CVC4__THEORY__ARITH__ARITHVAR_H -#include <limits> #include <ext/hash_map> #include "expr/node.h" #include "context/cdhashset.h" -#include "context/cdhashset.h" #include "util/index.h" +#include "util/dense_map.h" namespace CVC4 { namespace theory { namespace arith { typedef Index ArithVar; -const ArithVar ARITHVAR_SENTINEL = std::numeric_limits<ArithVar>::max(); +extern const ArithVar ARITHVAR_SENTINEL; //Maps from Nodes -> ArithVars, and vice versa typedef __gnu_cxx::hash_map<Node, ArithVar, NodeHashFunction> NodeToArithVarMap; -typedef __gnu_cxx::hash_map<ArithVar, Node> ArithVarToNodeMap; +typedef DenseMap<Node> ArithVarToNodeMap; /** * ArithVarCallBack provides a mechanism for agreeing on callbacks while @@ -50,6 +49,16 @@ public: virtual void operator()(ArithVar x) = 0; }; +/** + * Requests arithmetic variables for internal use, + * and releases arithmetic variables that are no longer being used. + */ +class ArithVarMalloc { +public: + virtual ArithVar request() = 0; + virtual void release(ArithVar v) = 0; +}; + class TNodeCallBack { public: virtual void operator()(TNode n) = 0; diff --git a/src/theory/arith/arithvar_node_map.h b/src/theory/arith/arithvar_node_map.h index 3a2cff236..e0e589e57 100644 --- a/src/theory/arith/arithvar_node_map.h +++ b/src/theory/arith/arithvar_node_map.h @@ -40,31 +40,50 @@ private: ArithVarToNodeMap d_arithVarToNodeMap; public: + + typedef ArithVarToNodeMap::const_iterator var_iterator; + ArithVarNodeMap() {} inline bool hasArithVar(TNode x) const { return d_nodeToArithVarMap.find(x) != d_nodeToArithVarMap.end(); } + inline bool hasNode(ArithVar a) const { + return d_arithVarToNodeMap.isKey(a); + } + inline ArithVar asArithVar(TNode x) const{ Assert(hasArithVar(x)); Assert((d_nodeToArithVarMap.find(x))->second <= ARITHVAR_SENTINEL); return (d_nodeToArithVarMap.find(x))->second; } + inline Node asNode(ArithVar a) const{ - Assert(d_arithVarToNodeMap.find(a) != d_arithVarToNodeMap.end()); - return (d_arithVarToNodeMap.find(a))->second; + Assert(hasNode(a)); + return d_arithVarToNodeMap[a]; } inline void setArithVar(TNode x, ArithVar a){ Assert(!hasArithVar(x)); - Assert(d_arithVarToNodeMap.find(a) == d_arithVarToNodeMap.end()); - d_arithVarToNodeMap[a] = x; + Assert(!d_arithVarToNodeMap.isKey(a)); + d_arithVarToNodeMap.set(a, x); d_nodeToArithVarMap[x] = a; } - const ArithVarToNodeMap& getArithVarToNodeMap() const { - return d_arithVarToNodeMap; + inline void remove(ArithVar x){ + Assert(hasNode(x)); + Node node = asNode(x); + + d_nodeToArithVarMap.erase(d_nodeToArithVarMap.find(node)); + d_arithVarToNodeMap.remove(x); + } + + var_iterator var_begin() const { + return d_arithVarToNodeMap.begin(); + } + var_iterator var_end() const { + return d_arithVarToNodeMap.end(); } };/* class ArithVarNodeMap */ diff --git a/src/theory/arith/congruence_manager.cpp b/src/theory/arith/congruence_manager.cpp index 5ee250c09..de4c7eac3 100644 --- a/src/theory/arith/congruence_manager.cpp +++ b/src/theory/arith/congruence_manager.cpp @@ -272,7 +272,7 @@ void ArithCongruenceManager::addWatchedPair(ArithVar s, TNode x, TNode y){ d_watchedVariables.add(s); Node eq = x.eqNode(y); - d_watchedEqualities[s] = eq; + d_watchedEqualities.set(s, eq); } void ArithCongruenceManager::assertionToEqualityEngine(bool isEquality, ArithVar s, TNode reason){ diff --git a/src/theory/arith/constraint.cpp b/src/theory/arith/constraint.cpp index 392d04f6c..cf3aeafee 100644 --- a/src/theory/arith/constraint.cpp +++ b/src/theory/arith/constraint.cpp @@ -371,6 +371,10 @@ void ConstraintValue::setAssertedToTheTheory(TNode witness) { d_database->pushAssertionOrderWatch(this, witness); } +// bool ConstraintValue::isPsuedoConstraint() const { +// return d_proof == d_database->d_psuedoConstraintProof; +// } + bool ConstraintValue::isSelfExplaining() const { return d_proof == d_database->d_selfExplainingProof; } @@ -481,6 +485,9 @@ ConstraintDatabase::ConstraintDatabase(context::Context* satContext, context::Co d_equalityEngineProof = d_proofs.size(); d_proofs.push_back(NullConstraint); + + // d_psuedoConstraintProof = d_proofs.size(); + // d_proofs.push_back(NullConstraint); } Constraint ConstraintDatabase::getConstraint(ArithVar v, ConstraintType t, const DeltaRational& r){ @@ -566,8 +573,32 @@ ConstraintDatabase::Statistics::~Statistics(){ } void ConstraintDatabase::addVariable(ArithVar v){ - Assert(v == d_varDatabases.size()); - d_varDatabases.push_back(new PerVariableDatabase(v)); + if(d_reclaimable.isMember(v)){ + SortedConstraintMap& scm = getVariableSCM(v); + + std::vector<Constraint> constraintList; + + for(SortedConstraintMapIterator i = scm.begin(), end = scm.end(); i != end; ++i){ + (i->second).push_into(constraintList); + } + while(!constraintList.empty()){ + Constraint c = constraintList.back(); + constraintList.pop_back(); + Assert(c->safeToGarbageCollect()); + delete c; + } + Assert(scm.empty()); + + d_reclaimable.remove(v); + }else{ + Assert(v == d_varDatabases.size()); + d_varDatabases.push_back(new PerVariableDatabase(v)); + } +} + +void ConstraintDatabase::removeVariable(ArithVar v){ + Assert(!d_reclaimable.isMember(v)); + d_reclaimable.add(v); } bool ConstraintValue::safeToGarbageCollect() const{ @@ -802,6 +833,13 @@ void ConstraintValue::impliedBy(const std::vector<Constraint>& b){ } } +// void ConstraintValue::setPsuedoConstraint(){ +// Assert(truthIsUnknown()); +// Assert(!hasLiteral()); + +// d_database->pushProofWatch(this, d_database->d_psuedoConstraintProof); +// } + void ConstraintValue::setEqualityEngineProof(){ Assert(truthIsUnknown()); Assert(hasLiteral()); @@ -818,6 +856,7 @@ void ConstraintValue::markAsTrue(){ void ConstraintValue::markAsTrue(Constraint imp){ Assert(truthIsUnknown()); Assert(imp->hasProof()); + //Assert(!imp->isPsuedoConstraint()); d_database->d_proofs.push_back(NullConstraint); d_database->d_proofs.push_back(imp); @@ -829,6 +868,8 @@ void ConstraintValue::markAsTrue(Constraint impA, Constraint impB){ Assert(truthIsUnknown()); Assert(impA->hasProof()); Assert(impB->hasProof()); + //Assert(!impA->isPsuedoConstraint()); + //Assert(!impB->isPsuedoConstraint()); d_database->d_proofs.push_back(NullConstraint); d_database->d_proofs.push_back(impA); @@ -845,6 +886,7 @@ void ConstraintValue::markAsTrue(const vector<Constraint>& a){ for(vector<Constraint>::const_iterator i = a.begin(), end = a.end(); i != end; ++i){ Constraint c_i = *i; Assert(c_i->hasProof()); + //Assert(!c_i->isPsuedoConstraint()); d_database->d_proofs.push_back(c_i); } @@ -861,6 +903,7 @@ SortedConstraintMap& ConstraintValue::constraintSet() const{ bool ConstraintValue::proofIsEmpty() const{ Assert(hasProof()); bool result = d_database->d_proofs[d_proof] == NullConstraint; + //Assert((!result) || isSelfExplaining() || hasEqualityEngineProof() || isPsuedoConstraint()); Assert((!result) || isSelfExplaining() || hasEqualityEngineProof()); return result; } @@ -869,6 +912,7 @@ void ConstraintValue::explainBefore(NodeBuilder<>& nb, AssertionOrder order) con Assert(hasProof()); Assert(!isSelfExplaining() || assertedToTheTheory()); + if(assertedBefore(order)){ nb << getWitness(); }else if(hasEqualityEngineProof()){ diff --git a/src/theory/arith/constraint.h b/src/theory/arith/constraint.h index 331fd2bcb..52aa5a5ce 100644 --- a/src/theory/arith/constraint.h +++ b/src/theory/arith/constraint.h @@ -485,6 +485,15 @@ public: void setEqualityEngineProof(); bool hasEqualityEngineProof() const; + + /** + * There cannot be a literal associated with this constraint. + * The explanation is the constant true. + * explainInto() does nothing. + */ + //void setPsuedoConstraint(); + //bool isPsuedoConstraint() const; + /** * Returns a explanation of the constraint that is appropriate for conflicts. * @@ -694,6 +703,14 @@ private: */ ProofId d_equalityEngineProof; + /** + * Marks a node as being true always. + * This is only okay for purely internal things. + * + * This is a special proof that is always a member of the list. + */ + //ProofId d_psuedoConstraintProof; + typedef context::CDList<Constraint, ConstraintValue::ProofCleanup> ProofCleanupList; typedef context::CDList<Constraint, ConstraintValue::CanBePropagatedCleanup> CBPList; typedef context::CDList<Constraint, ConstraintValue::AssertionOrderCleanup> AOList; @@ -817,6 +834,7 @@ public: void addVariable(ArithVar v); bool variableDatabaseIsSetup(ArithVar v) const; + void removeVariable(ArithVar v); Node eeExplain(ConstConstraint c) const; void eeExplain(ConstConstraint c, NodeBuilder<>& nb) const; @@ -881,6 +899,8 @@ public: private: void raiseUnateConflict(Constraint ant, Constraint cons); + DenseSet d_reclaimable; + class Statistics { public: IntStat d_unatePropagateCalls; diff --git a/src/theory/arith/linear_equality.cpp b/src/theory/arith/linear_equality.cpp index 360e45289..5063a05c7 100644 --- a/src/theory/arith/linear_equality.cpp +++ b/src/theory/arith/linear_equality.cpp @@ -80,7 +80,7 @@ void LinearEqualityModule::update(ArithVar x_i, const DeltaRational& v){ if(Debug.isOn("paranoid:check_tableau")){ debugCheckTableau(); } } -void LinearEqualityModule::pivotAndUpdate(ArithVar x_i, ArithVar x_j, DeltaRational& v){ +void LinearEqualityModule::pivotAndUpdate(ArithVar x_i, ArithVar x_j, const DeltaRational& v){ Assert(x_i != x_j); TimerStat::CodeTimer codeTimer(d_statistics.d_pivotTime); @@ -188,6 +188,23 @@ void LinearEqualityModule::debugCheckTableau(){ Assert(sum == shouldBe); } } +bool LinearEqualityModule::debugEntireLinEqIsConsistent(const string& s){ + bool result = true; + for(ArithVar var = 0, end = d_tableau.getNumColumns(); var != end; ++var){ + // for(VarIter i = d_variables.begin(), end = d_variables.end(); i != end; ++i){ + //ArithVar var = d_arithvarNodeMap.asArithVar(*i); + if(!d_partialModel.assignmentIsConsistent(var)){ + d_partialModel.printModel(var); + Warning() << s << ":" << "Assignment is not consistent for " << var ; + if(d_tableau.isBasic(var)){ + Warning() << " (basic)"; + } + Warning() << endl; + result = false; + } + } + return result; +} DeltaRational LinearEqualityModule::computeBound(ArithVar basic, bool upperBound){ DeltaRational sum(0,0); diff --git a/src/theory/arith/linear_equality.h b/src/theory/arith/linear_equality.h index f337ef0db..7df5ee9c3 100644 --- a/src/theory/arith/linear_equality.h +++ b/src/theory/arith/linear_equality.h @@ -79,7 +79,7 @@ public: * and then pivots x_i with the nonbasic variable in its row x_j. * Updates the assignment of the other basic variables accordingly. */ - void pivotAndUpdate(ArithVar x_i, ArithVar x_j, DeltaRational& v); + void pivotAndUpdate(ArithVar x_i, ArithVar x_j, const DeltaRational& v); ArithPartialModel& getPartialModel() const{ return d_partialModel; } @@ -141,6 +141,11 @@ public: /** Debugging information for a pivot. */ void debugPivot(ArithVar x_i, ArithVar x_j); + /** + * + */ + bool debugEntireLinEqIsConsistent(const std::string& s); + private: /** These fields are designed to be accessible to TheoryArith methods. */ diff --git a/src/theory/arith/matrix.cpp b/src/theory/arith/matrix.cpp index 8e7fe7894..cd7a8a9aa 100644 --- a/src/theory/arith/matrix.cpp +++ b/src/theory/arith/matrix.cpp @@ -247,7 +247,7 @@ void Tableau::rowPivot(ArithVar basicOld, ArithVar basicNew){ d_basic2RowIndex.remove(basicOld); d_basic2RowIndex.set(basicNew, rid); - d_rowIndex2basic[rid] = basicNew; + d_rowIndex2basic.set(rid, basicNew); } // void Tableau::addEntry(ArithVar row, ArithVar col, const Rational& coeff){ @@ -397,10 +397,11 @@ void Tableau::addRow(ArithVar basic, RowIndex newRow = Matrix<Rational>::addRow(coefficients, variables); addEntry(newRow, basic, Rational(-1)); - Assert(d_rowIndex2basic.size() == newRow); + Assert(!d_basic2RowIndex.isKey(basic)); + Assert(!d_rowIndex2basic.isKey(newRow)); d_basic2RowIndex.set(basic, newRow); - d_rowIndex2basic.push_back(basic); + d_rowIndex2basic.set(newRow, basic); if(Debug.isOn("matrix")){ printMatrix(); } @@ -558,6 +559,15 @@ void ReducedRowVector::enqueueNonBasicVariablesAndCoefficients(std::vector< Arit // return newId; // } +void Tableau::removeBasicRow(ArithVar basic){ + RowIndex rid = basicToRowIndex(basic); + + removeRow(rid); + d_basic2RowIndex.remove(basic); + d_rowIndex2basic.remove(rid); + +} + }/* CVC4::theory::arith namespace */ }/* CVC4::theory namespace */ diff --git a/src/theory/arith/matrix.h b/src/theory/arith/matrix.h index ea6c389b9..027397b6a 100644 --- a/src/theory/arith/matrix.h +++ b/src/theory/arith/matrix.h @@ -25,6 +25,7 @@ #include "util/dense_map.h" #include "theory/arith/arithvar.h" +#include "theory/arith/arithvar_node_map.h" #include "theory/arith/normal_form.h" #include <queue> @@ -377,6 +378,8 @@ protected: uint32_t d_entriesInUse; MatrixEntryVector<T> d_entries; + std::vector<RowIndex> d_pool; + T d_zero; public: @@ -446,6 +449,23 @@ protected: d_entries.freeEntry(id); } + private: + RowIndex requestRowIndex(){ + if(d_pool.empty()){ + RowIndex ridx = d_rows.size(); + d_rows.push_back(RowVectorT(&d_entries)); + return ridx; + }else{ + RowIndex rid = d_pool.back(); + d_pool.pop_back(); + return rid; + } + } + + void releaseRowIndex(RowIndex rid){ + d_pool.push_back(rid); + } + public: size_t getNumRows() const { @@ -485,8 +505,11 @@ public: */ RowIndex addRow(const std::vector<T>& coeffs, const std::vector<ArithVar>& variables){ - RowIndex ridx = d_rows.size(); - d_rows.push_back(RowVectorT(&d_entries)); + + RowIndex ridx = requestRowIndex(); + + //RowIndex ridx = d_rows.size(); + //d_rows.push_back(RowVectorT(&d_entries)); std::vector<Rational>::const_iterator coeffIter = coeffs.begin(); std::vector<ArithVar>::const_iterator varsIter = variables.begin(); @@ -701,36 +724,7 @@ public: EntryID id = i.getID(); removeEntry(id); } - } - - - Node rowAsEquality(RowIndex rid, const ArithVarToNodeMap& map){ - using namespace CVC4::kind; - - Assert(getRowLength(rid) >= 2); - - std::vector<Node> pairs; - for(RowIterator i = getRow(rid); !i.atEnd(); ++i){ - const Entry& entry = *i; - ArithVar colVar = entry.getColVar(); - - Node var = (map.find(colVar))->second; - Node coeff = mkRationalNode(entry.getCoefficient()); - - Node mult = NodeBuilder<2>(MULT) << coeff << var; - pairs.push_back(mult); - } - - Node sum = Node::null(); - if(pairs.size() == 1 ){ - sum = pairs.front(); - }else{ - Assert(pairs.size() >= 2); - NodeBuilder<> sumBuilder(PLUS); - sumBuilder.append(pairs); - sum = sumBuilder; - } - return NodeBuilder<2>(EQUAL) << sum << mkRationalNode(d_zero); + releaseRowIndex(rid); } double densityMeasure() const{ @@ -754,6 +748,15 @@ public: } } + void loadSignQueries(RowIndex rid, DenseMap<int>& target) const{ + + RowIterator i = getRow(rid).begin(), i_end = getRow(rid).end(); + for(; i != i_end; ++i){ + const MatrixEntry<T>& entry = *i; + target.set(entry.getColVar(), entry.getCoefficient().sgn()); + } + } + protected: uint32_t numNonZeroEntries() const { return size(); } @@ -833,8 +836,10 @@ private: // Set of all of the basic variables in the tableau. // ArithVarMap<RowIndex> : ArithVar |-> RowIndex BasicToRowMap d_basic2RowIndex; + // RowIndex |-> Basic Variable - std::vector<ArithVar> d_rowIndex2basic; + typedef DenseMap<ArithVar> RowIndexToBasicMap; + RowIndexToBasicMap d_rowIndex2basic; public: @@ -882,10 +887,6 @@ public: return getRow(basicToRowIndex(basic)).begin(); } - // RowIterator rowIterator(RowIndex r) const { - // return getRow(r).begin(); - // } - /** * Adds a row to the tableau. * The new row is equivalent to: @@ -911,7 +912,6 @@ public: void removeBasicRow(ArithVar basic); - private: /* Changes the basic variable on the row for basicOld to basicNew. */ void rowPivot(ArithVar basicOld, ArithVar basicNew); diff --git a/src/theory/arith/options b/src/theory/arith/options index 38cf07251..ab377c8a1 100644 --- a/src/theory/arith/options +++ b/src/theory/arith/options @@ -51,4 +51,8 @@ option arithRewriteEq --enable-arith-rewrite-equalities/--disable-arith-rewrite- turns on the preprocessing rewrite turning equalities into a conjunction of inequalities /turns off the preprocessing rewrite turning equalities into a conjunction of inequalities +option arithMLTrick --enable-miplib-trick/--disable-miplib-trick bool :default false :read-write + turns on the preprocessing step of attempting to infer bounds on miplib problems +/turns off the preprocessing step of attempting to infer bounds on miplib problems + endmodule diff --git a/src/theory/arith/partial_model.cpp b/src/theory/arith/partial_model.cpp index 0ffe67763..5dccd8747 100644 --- a/src/theory/arith/partial_model.cpp +++ b/src/theory/arith/partial_model.cpp @@ -72,7 +72,9 @@ void ArithPartialModel::setAssignment(ArithVar x, const DeltaRational& safe, con Debug("partial_model") << "pm: updating the assignment to" << x << " now " << r <<endl; if(safe == r){ - d_hasSafeAssignment[x] = false; + if(d_hasSafeAssignment[x]){ + d_safeAssignment[x] = safe; + } }else{ d_safeAssignment[x] = safe; @@ -177,6 +179,25 @@ void ArithPartialModel::setUpperBoundConstraint(Constraint c){ d_ubc.set(x, c); } +void ArithPartialModel::forceRelaxLowerBound(ArithVar v){ + AssertArgument(inMaps(v), "Calling forceRelaxLowerBound on a variable that is not properly setup."); + AssertArgument(hasLowerBound(v), "Calling forceRelaxLowerBound on a variable without a lowerbound."); + + Debug("partial_model") << "forceRelaxLowerBound(" << v << ") dropping :" << getLowerBoundConstraint(v) << endl; + + d_lbc.set(v, NullConstraint); +} + + +void ArithPartialModel::forceRelaxUpperBound(ArithVar v){ + AssertArgument(inMaps(v), "Calling forceRelaxUpperBound on a variable that is not properly setup."); + AssertArgument(hasUpperBound(v), "Calling forceRelaxUpperBound on a variable without an upper bound."); + + Debug("partial_model") << "forceRelaxUpperBound(" << v << ") dropping :" << getUpperBoundConstraint(v) << endl; + + d_ubc.set(v, NullConstraint); +} + int ArithPartialModel::cmpToLowerBound(ArithVar x, const DeltaRational& c) const{ if(!hasLowerBound(x)){ // l = -\intfy diff --git a/src/theory/arith/partial_model.h b/src/theory/arith/partial_model.h index 49cfd44a1..fdb4a8ffa 100644 --- a/src/theory/arith/partial_model.h +++ b/src/theory/arith/partial_model.h @@ -68,16 +68,40 @@ public: ArithPartialModel(context::Context* c, RationalCallBack& deltaComputation); + /** + * This sets the lower bound for a variable in the current context. + * This must be stronger the previous constraint. + */ void setLowerBoundConstraint(Constraint lb); + + /** + * This sets the upper bound for a variable in the current context. + * This must be stronger the previous constraint. + */ void setUpperBoundConstraint(Constraint ub); + /** Returns the constraint for the upper bound of a variable. */ inline Constraint getUpperBoundConstraint(ArithVar x) const{ return d_ubc[x]; } + /** Returns the constraint for the lower bound of a variable. */ inline Constraint getLowerBoundConstraint(ArithVar x) const{ return d_lbc[x]; } + /** + * This forces the lower bound for a variable to be relaxed in the current context. + * This is done by forcing the lower bound to be NullConstraint. + * This is an expert only operation! (See primal simplex for an example.) + */ + void forceRelaxLowerBound(ArithVar x); + + /** + * This forces the upper bound for a variable to be relaxed in the current context. + * This is done by forcing the upper bound to be NullConstraint. + * This is an expert only operation! (See primal simplex for an example.) + */ + void forceRelaxUpperBound(ArithVar x); /* Initializes a variable to a safe value.*/ void initialize(ArithVar x, const DeltaRational& r); @@ -190,7 +214,6 @@ public: d_deltaIsSafe = true; } - private: /** @@ -202,7 +225,7 @@ private: bool equalSizes(); bool inMaps(ArithVar x) const{ - return 0 <= x && x < d_mapSize; + return x < d_mapSize; } };/* class ArithPartialModel */ diff --git a/src/theory/arith/theory_arith.cpp b/src/theory/arith/theory_arith.cpp index c2c005767..39ded7991 100644 --- a/src/theory/arith/theory_arith.cpp +++ b/src/theory/arith/theory_arith.cpp @@ -62,6 +62,8 @@ TheoryArith::TheoryArith(context::Context* c, context::UserContext* u, OutputCha d_unknownsInARow(0), d_hasDoneWorkSinceCut(false), d_learner(u), + d_numberOfVariables(0), + d_pool(), d_setupLiteralCallback(this), d_assertionsThatDoNotMatchTheirLiterals(c), d_nextIntegerCheckVar(0), @@ -79,6 +81,7 @@ TheoryArith::TheoryArith(context::Context* c, context::UserContext* u, OutputCha d_tableauResetPeriod(10), d_conflicts(c), d_raiseConflict(d_conflicts), + d_tempVarMalloc(*this), d_congruenceManager(c, d_constraintDatabase, d_setupLiteralCallback, d_arithvarNodeMap, d_raiseConflict), d_simplex(d_linEq, d_raiseConflict), d_constraintDatabase(c, u, d_arithvarNodeMap, d_congruenceManager, d_raiseConflict), @@ -749,8 +752,8 @@ Theory::PPAssertStatus TheoryArith::ppAssert(TNode in, SubstitutionMap& outSubst Assert(elim == Rewriter::rewrite(elim)); - static const unsigned MAX_SUB_SIZE = 20; - if(false && right.size() > MAX_SUB_SIZE){ + static const unsigned MAX_SUB_SIZE = 2; + if(right.size() > MAX_SUB_SIZE){ Debug("simplify") << "TheoryArith::solve(): did not substitute due to the right hand side containing too many terms: " << minVar << ":" << elim << endl; Debug("simplify") << right.size() << endl; }else if(elim.hasSubterm(minVar)){ @@ -822,8 +825,9 @@ void TheoryArith::setupVariable(const Variable& x){ Assert(!isSetup(n)); ++(d_statistics.d_statUserVariables); - ArithVar varN = requestArithVar(n,false); - setupInitialValue(varN); + requestArithVar(n,false); + //ArithVar varN = requestArithVar(n,false); + //setupInitialValue(varN); markSetup(n); @@ -860,8 +864,9 @@ void TheoryArith::setupVariableList(const VarList& vl){ d_nlIncomplete = true; ++(d_statistics.d_statUserVariables); - ArithVar av = requestArithVar(vlNode, false); - setupInitialValue(av); + requestArithVar(vlNode, false); + //ArithVar av = requestArithVar(vlNode, false); + //setupInitialValue(av); markSetup(vlNode); } @@ -1054,7 +1059,7 @@ void TheoryArith::setupPolynomial(const Polynomial& poly) { ArithVar varSlack = requestArithVar(polyNode, true); d_tableau.addRow(varSlack, coefficients, variables); - setupInitialValue(varSlack); + setupBasicValue(varSlack); //Add differences to the difference manager Polynomial::iterator i = poly.begin(), end = poly.end(); @@ -1125,6 +1130,14 @@ void TheoryArith::preRegisterTerm(TNode n) { Debug("arith::preregister") << "end arith::preRegisterTerm("<< n <<")" << endl; } +void TheoryArith::releaseArithVar(ArithVar v){ + Assert(d_arithvarNodeMap.hasNode(v)); + + d_constraintDatabase.removeVariable(v); + d_arithvarNodeMap.remove(v); + + d_pool.push_back(v); +} ArithVar TheoryArith::requestArithVar(TNode x, bool slack){ //TODO : The VarList trick is good enough? @@ -1135,32 +1148,73 @@ ArithVar TheoryArith::requestArithVar(TNode x, bool slack){ Assert(!d_arithvarNodeMap.hasArithVar(x)); Assert(x.getType().isReal());// real or integer - ArithVar varX = d_variables.size(); - d_variables.push_back(Node(x)); - Debug("integers") << "isInteger[[" << x << "]]: " << x.getType().isInteger() << endl; + // ArithVar varX = d_variables.size(); + // d_variables.push_back(Node(x)); + + bool reclaim = !d_pool.empty(); + ArithVar varX; + + if(reclaim){ + varX = d_pool.back(); + d_pool.pop_back(); + + d_partialModel.setAssignment(varX, d_DELTA_ZERO, d_DELTA_ZERO); + }else{ + varX = d_numberOfVariables; + ++d_numberOfVariables; + + d_slackVars.push_back(true); + d_variableTypes.push_back(ATReal); + d_simplex.increaseMax(); + + d_tableau.increaseSize(); + d_tableauSizeHasBeenModified = true; + + d_partialModel.initialize(varX, d_DELTA_ZERO); + } + + ArithType type; if(slack){ //The type computation is not quite accurate for Rationals that are integral. //We'll use the isIntegral check from the polynomial package instead. Polynomial p = Polynomial::parsePolynomial(x); - d_variableTypes.push_back(p.isIntegral() ? ATInteger : ATReal); + type = p.isIntegral() ? ATInteger : ATReal; }else{ - d_variableTypes.push_back(nodeToArithType(x)); + type = nodeToArithType(x); } + d_variableTypes[varX] = type; + d_slackVars[varX] = slack; - d_slackVars.push_back(slack); - - d_simplex.increaseMax(); + d_constraintDatabase.addVariable(varX); d_arithvarNodeMap.setArithVar(x,varX); - d_tableau.increaseSize(); - d_tableauSizeHasBeenModified = true; + // Debug("integers") << "isInteger[[" << x << "]]: " << x.getType().isInteger() << endl; - d_constraintDatabase.addVariable(varX); + // if(slack){ + // //The type computation is not quite accurate for Rationals that are integral. + // //We'll use the isIntegral check from the polynomial package instead. + // Polynomial p = Polynomial::parsePolynomial(x); + // d_variableTypes.push_back(p.isIntegral() ? ATInteger : ATReal); + // }else{ + // d_variableTypes.push_back(nodeToArithType(x)); + // } + + // d_slackVars.push_back(slack); + + // d_simplex.increaseMax(); + + // d_tableau.increaseSize(); + // d_tableauSizeHasBeenModified = true; + + // d_constraintDatabase.addVariable(varX); Debug("arith::arithvar") << x << " |-> " << varX << endl; + Assert(!d_partialModel.hasUpperBound(varX)); + Assert(!d_partialModel.hasLowerBound(varX)); + return varX; } @@ -1179,18 +1233,7 @@ void TheoryArith::asVectors(const Polynomial& p, std::vector<Rational>& coeffs, Assert(theoryOf(n) != THEORY_ARITH || d_arithvarNodeMap.hasArithVar(n)); Assert(d_arithvarNodeMap.hasArithVar(n)); - ArithVar av; - // The first if is likely dead is likely dead code: - // if (theoryOf(n) != THEORY_ARITH && !d_arithvarNodeMap.hasArithVar(n)) { - // // The only way not to get it through pre-register is if it's a foreign term - // ++(d_statistics.d_statUserVariables); - // av = requestArithVar(n,false); - // setupInitialValue(av); - // } else { - // // Otherwise, we already have it's variable - // av = d_arithvarNodeMap.asArithVar(n); - // } - av = d_arithvarNodeMap.asArithVar(n); + ArithVar av = d_arithvarNodeMap.asArithVar(n); coeffs.push_back(constant.getValue()); variables.push_back(av); @@ -1200,11 +1243,12 @@ void TheoryArith::asVectors(const Polynomial& p, std::vector<Rational>& coeffs, /* Requirements: * For basic variables the row must have been added to the tableau. */ -void TheoryArith::setupInitialValue(ArithVar x){ +void TheoryArith::setupBasicValue(ArithVar x){ + Assert(d_tableau.isBasic(x)); - if(!d_tableau.isBasic(x)){ - d_partialModel.initialize(x, d_DELTA_ZERO); - }else{ + // if(!d_tableau.isBasic(x)){ + // d_partialModel.setAssignment(x, d_DELTA_ZERO, d_DELTA_ZERO); + // }else{ //If the variable is basic, assertions may have already happened and updates //may have occured before setting this variable up. @@ -1212,9 +1256,11 @@ void TheoryArith::setupInitialValue(ArithVar x){ //time instead of register DeltaRational safeAssignment = d_linEq.computeRowValue(x, true); DeltaRational assignment = d_linEq.computeRowValue(x, false); - d_partialModel.initialize(x,safeAssignment); - d_partialModel.setAssignment(x,assignment); - } + //d_partialModel.initialize(x,safeAssignment); + //d_partialModel.setAssignment(x,assignment); + d_partialModel.setAssignment(x,safeAssignment,assignment); + + // } Debug("arith") << "setupVariable("<<x<<")"<<std::endl; } @@ -1254,8 +1300,8 @@ Node TheoryArith::dioCutting(){ context::Context::ScopedPush speculativePush(getSatContext()); //DO NOT TOUCH THE OUTPUTSTREAM - //TODO: Improve this - for(ArithVar v = 0, end = d_variables.size(); v != end; ++v){ + for(var_iterator vi = var_begin(), vend = var_end(); vi != vend; ++vi){ + ArithVar v = *vi; if(isInteger(v)){ const DeltaRational& dr = d_partialModel.getAssignment(v); if(d_partialModel.equalsUpperBound(v, dr) || d_partialModel.equalsLowerBound(v, dr)){ @@ -1369,7 +1415,7 @@ Constraint TheoryArith::constraintFromFactQueue(){ if(assertion != reAssertion){ Debug("arith::nf") << "getting non-nf assertion " << assertion << " |-> " << reAssertion << endl; Assert(constraint != NullConstraint); - d_assertionsThatDoNotMatchTheirLiterals[assertion] = constraint; + d_assertionsThatDoNotMatchTheirLiterals.insert(assertion, constraint); } } @@ -1485,7 +1531,8 @@ bool TheoryArith::assertionCases(Constraint constraint){ * If this returns true, all integer variables have an integer assignment. */ bool TheoryArith::hasIntegerModel(){ - if(d_variables.size() > 0){ + //if(d_variables.size() > 0){ + if(getNumberOfVariables()){ const ArithVar rrEnd = d_nextIntegerCheckVar; do { //Do not include slack variables @@ -1495,7 +1542,7 @@ bool TheoryArith::hasIntegerModel(){ return false; } } - } while((d_nextIntegerCheckVar = (1 + d_nextIntegerCheckVar == d_variables.size() ? 0 : 1 + d_nextIntegerCheckVar)) != rrEnd); + } while((d_nextIntegerCheckVar = (1 + d_nextIntegerCheckVar == getNumberOfVariables() ? 0 : 1 + d_nextIntegerCheckVar)) != rrEnd); } return true; } @@ -1576,6 +1623,7 @@ void TheoryArith::check(Effort effortLevel){ Assert(d_conflicts.empty()); d_qflraStatus = d_simplex.findModel(fullEffort(effortLevel)); + switch(d_qflraStatus){ case Result::SAT: if(newFacts){ @@ -1822,7 +1870,8 @@ bool TheoryArith::splitDisequalities(){ */ void TheoryArith::debugPrintAssertions() { Debug("arith::print_assertions") << "Assertions:" << endl; - for (ArithVar i = 0; i < d_variables.size(); ++ i) { + for (var_iterator vi = var_begin(), vend = var_end(); vi != vend; ++vi){ + ArithVar i = *vi; if (d_partialModel.hasLowerBound(i)) { Constraint lConstr = d_partialModel.getLowerBoundConstraint(i); Debug("arith::print_assertions") << lConstr << endl; @@ -1842,13 +1891,15 @@ void TheoryArith::debugPrintAssertions() { void TheoryArith::debugPrintModel(){ Debug("arith::print_model") << "Model:" << endl; - - for (ArithVar i = 0; i < d_variables.size(); ++ i) { - Debug("arith::print_model") << d_variables[i] << " : " << - d_partialModel.getAssignment(i); - if(d_tableau.isBasic(i)) - Debug("arith::print_model") << " (basic)"; - Debug("arith::print_model") << endl; + for (var_iterator vi = var_begin(), vend = var_end(); vi != vend; ++vi){ + ArithVar i = *vi; + if(d_arithvarNodeMap.hasNode(i)){ + Debug("arith::print_model") << d_arithvarNodeMap.asNode(i) << " : " << + d_partialModel.getAssignment(i); + if(d_tableau.isBasic(i)) + Debug("arith::print_model") << " (basic)"; + Debug("arith::print_model") << endl; + } } } @@ -2057,7 +2108,8 @@ Rational TheoryArith::deltaValueForTotalOrder() const{ relevantDeltaValues.insert(val); } - for(ArithVar v = 0; v < d_variables.size(); ++v){ + for(var_iterator vi = var_begin(), vend = var_end(); vi != vend; ++vi){ + ArithVar v = *vi; const DeltaRational& value = d_partialModel.getAssignment(v); relevantDeltaValues.insert(value); if( d_partialModel.hasLowerBound(v)){ @@ -2108,7 +2160,8 @@ void TheoryArith::collectModelInfo( TheoryModel* m, bool fullModel ){ // TODO: // This is not very good for user push/pop.... // Revisit when implementing push/pop - for(ArithVar v = 0; v < d_variables.size(); ++v){ + for(var_iterator vi = var_begin(), vend = var_end(); vi != vend; ++vi){ + ArithVar v = *vi; if(!isSlackVariable(v)){ Node term = d_arithvarNodeMap.asNode(v); @@ -2187,13 +2240,13 @@ void TheoryArith::notifyRestart(){ } bool TheoryArith::entireStateIsConsistent(const string& s){ - typedef std::vector<Node>::const_iterator VarIter; bool result = true; - for(VarIter i = d_variables.begin(), end = d_variables.end(); i != end; ++i){ - ArithVar var = d_arithvarNodeMap.asArithVar(*i); + for(var_iterator vi = var_begin(), vend = var_end(); vi != vend; ++vi){ + ArithVar var = *vi; + //ArithVar var = d_arithvarNodeMap.asArithVar(*i); if(!d_partialModel.assignmentIsConsistent(var)){ d_partialModel.printModel(var); - Warning() << s << ":" << "Assignment is not consistent for " << var << *i; + Warning() << s << ":" << "Assignment is not consistent for " << var << d_arithvarNodeMap.asNode(var); if(d_tableau.isBasic(var)){ Warning() << " (basic)"; } @@ -2205,15 +2258,14 @@ bool TheoryArith::entireStateIsConsistent(const string& s){ } bool TheoryArith::unenqueuedVariablesAreConsistent(){ - typedef std::vector<Node>::const_iterator VarIter; bool result = true; - for(VarIter i = d_variables.begin(), end = d_variables.end(); i != end; ++i){ - ArithVar var = d_arithvarNodeMap.asArithVar(*i); + for(var_iterator vi = var_begin(), vend = var_end(); vi != vend; ++vi){ + ArithVar var = *vi; if(!d_partialModel.assignmentIsConsistent(var)){ if(!d_simplex.debugIsInCollectionQueue(var)){ d_partialModel.printModel(var); - Warning() << "Unenqueued var is not consistent for " << var << *i; + Warning() << "Unenqueued var is not consistent for " << var << d_arithvarNodeMap.asNode(var); if(d_tableau.isBasic(var)){ Warning() << " (basic)"; } @@ -2221,7 +2273,7 @@ bool TheoryArith::unenqueuedVariablesAreConsistent(){ result = false; } else if(Debug.isOn("arith::consistency::initial")){ d_partialModel.printModel(var); - Warning() << "Initial var is not consistent for " << var << *i; + Warning() << "Initial var is not consistent for " << var << d_arithvarNodeMap.asNode(var); if(d_tableau.isBasic(var)){ Warning() << " (basic)"; } diff --git a/src/theory/arith/theory_arith.h b/src/theory/arith/theory_arith.h index 6a83c501b..7d1150fb1 100644 --- a/src/theory/arith/theory_arith.h +++ b/src/theory/arith/theory_arith.h @@ -22,6 +22,7 @@ #include "context/context.h" #include "context/cdlist.h" #include "context/cdhashset.h" +#include "context/cdinsert_hashmap.h" #include "context/cdqueue.h" #include "expr/node.h" @@ -88,17 +89,20 @@ private: /** Static learner. */ ArithStaticLearner d_learner; - /** - * List of the variables in the system. - * This is needed to keep a positive ref count on slack variables. - */ - std::vector<Node> d_variables; + + ArithVar d_numberOfVariables; + inline ArithVar getNumberOfVariables() const { return d_numberOfVariables; } + std::vector<ArithVar> d_pool; + void releaseArithVar(ArithVar v); /** * The map between arith variables to nodes. */ ArithVarNodeMap d_arithvarNodeMap; + typedef ArithVarNodeMap::var_iterator var_iterator; + var_iterator var_begin() const { return d_arithvarNodeMap.var_begin(); } + var_iterator var_end() const { return d_arithvarNodeMap.var_end(); } NodeSet d_setupNodes; bool isSetup(Node n) const { @@ -135,7 +139,7 @@ private: * A superset of all of the assertions that currently are not the literal for * their constraint do not match constraint literals. Not just the witnesses. */ - context::CDHashMap<TNode, Constraint, TNodeHashFunction> d_assertionsThatDoNotMatchTheirLiterals; + context::CDInsertHashMap<Node, Constraint, NodeHashFunction> d_assertionsThatDoNotMatchTheirLiterals; /** * (For the moment) the type hierarchy goes as: @@ -272,6 +276,18 @@ private: void outputConflicts(); + class TempVarMalloc : public ArithVarMalloc { + private: + TheoryArith& d_ta; + public: + TempVarMalloc(TheoryArith& ta) : d_ta(ta) {} + ArithVar request(){ + Node skolem = mkRealSkolem("tmpVar"); + return d_ta.requestArithVar(skolem, false); + } + void release(ArithVar v){ d_ta.releaseArithVar(v); } + } d_tempVarMalloc; + /** * A copy of the tableau. * This is equivalent to the original tableau if d_tableauSizeHasBeenModified @@ -432,7 +448,7 @@ private: ArithVar requestArithVar(TNode x, bool slack); /** Initial (not context dependent) sets up for a variable.*/ - void setupInitialValue(ArithVar x); + void setupBasicValue(ArithVar x); /** Initial (not context dependent) sets up for a new slack variable.*/ void setupSlack(TNode left); diff --git a/src/theory/arrays/theory_arrays.cpp b/src/theory/arrays/theory_arrays.cpp index a05d30517..aabd3a62d 100644 --- a/src/theory/arrays/theory_arrays.cpp +++ b/src/theory/arrays/theory_arrays.cpp @@ -537,7 +537,7 @@ EqualityStatus TheoryArrays::getEqualityStatus(TNode a, TNode b) { void TheoryArrays::computeCareGraph() { if (d_sharedArrays.size() > 0) { - context::CDHashSet<TNode, TNodeHashFunction>::iterator it1 = d_sharedArrays.begin(), it2, iend = d_sharedArrays.end(); + CDNodeSet::key_iterator it1 = d_sharedArrays.key_begin(), it2, iend = d_sharedArrays.key_end(); for (; it1 != iend; ++it1) { for (it2 = it1, ++it2; it2 != iend; ++it2) { if ((*it1).getType() != (*it2).getType()) { @@ -1261,7 +1261,7 @@ void TheoryArrays::checkRowLemmas(TNode a, TNode b) void TheoryArrays::queueRowLemma(RowLemmaType lem) { - if (d_conflict || d_RowAlreadyAdded.count(lem) != 0) { + if (d_conflict || d_RowAlreadyAdded.contains(lem)) { return; } TNode a = lem.first; @@ -1407,7 +1407,7 @@ void TheoryArrays::dischargeLemmas() for (unsigned count = 0; count < sz; ++count) { RowLemmaType l = d_RowQueue.front(); d_RowQueue.pop(); - if (d_RowAlreadyAdded.count(l) != 0) { + if (d_RowAlreadyAdded.contains(l)) { continue; } diff --git a/src/theory/arrays/theory_arrays.h b/src/theory/arrays/theory_arrays.h index 240cfad9a..172482e71 100644 --- a/src/theory/arrays/theory_arrays.h +++ b/src/theory/arrays/theory_arrays.h @@ -333,8 +333,10 @@ class TheoryArrays : public Theory { context::CDQueue<RowLemmaType> d_RowQueue; context::CDHashSet<RowLemmaType, RowLemmaTypeHashFunction > d_RowAlreadyAdded; - context::CDHashSet<TNode, TNodeHashFunction> d_sharedArrays; - context::CDHashSet<TNode, TNodeHashFunction> d_sharedOther; + typedef context::CDHashSet<Node, NodeHashFunction> CDNodeSet; + + CDNodeSet d_sharedArrays; + CDNodeSet d_sharedOther; context::CDO<bool> d_sharedTerms; context::CDList<TNode> d_reads; std::hash_map<TNode, Node, TNodeHashFunction> d_diseqCache; diff --git a/src/theory/booleans/circuit_propagator.h b/src/theory/booleans/circuit_propagator.h index e62f9b7a1..aec0cff58 100644 --- a/src/theory/booleans/circuit_propagator.h +++ b/src/theory/booleans/circuit_propagator.h @@ -118,7 +118,7 @@ private: /** Nodes that have been attached already (computed forward edges for) */ // All the nodes we've visited so far - context::CDHashSet<TNode, TNodeHashFunction> d_seen; + context::CDHashSet<Node, NodeHashFunction> d_seen; /** * Assignment status of each node. diff --git a/src/theory/bv/theory_bv.h b/src/theory/bv/theory_bv.h index 0c8df3fca..e38f3568c 100644 --- a/src/theory/bv/theory_bv.h +++ b/src/theory/bv/theory_bv.h @@ -40,8 +40,8 @@ class TheoryBV : public Theory { context::Context* d_context; /** Context dependent set of atoms we already propagated */ - context::CDHashSet<TNode, TNodeHashFunction> d_alreadyPropagatedSet; - context::CDHashSet<TNode, TNodeHashFunction> d_sharedTermsSet; + context::CDHashSet<Node, NodeHashFunction> d_alreadyPropagatedSet; + context::CDHashSet<Node, NodeHashFunction> d_sharedTermsSet; BitblastSolver d_bitblastSolver; EqualitySolver d_equalitySolver; diff --git a/src/theory/bv/theory_bv_rewrite_rules_simplification.h b/src/theory/bv/theory_bv_rewrite_rules_simplification.h index 23cd8381d..8bcc64414 100644 --- a/src/theory/bv/theory_bv_rewrite_rules_simplification.h +++ b/src/theory/bv/theory_bv_rewrite_rules_simplification.h @@ -430,10 +430,6 @@ Node RewriteRule<BitwiseNotOr>::apply(TNode node) { template<> inline bool RewriteRule<XorNot>::applies(TNode node) { Unreachable(); - if (node.getKind() == kind::BITVECTOR_XOR && - node.getNumChildren() == 2 && - node[0].getKind() == kind::BITVECTOR_NOT && - node[1].getKind() == kind::BITVECTOR_NOT); } template<> inline diff --git a/src/theory/quantifiers/first_order_model.cpp b/src/theory/quantifiers/first_order_model.cpp index 3d98674a8..8272ce168 100644 --- a/src/theory/quantifiers/first_order_model.cpp +++ b/src/theory/quantifiers/first_order_model.cpp @@ -42,10 +42,6 @@ void FirstOrderModel::reset(){ TheoryModel::reset(); } -void FirstOrderModel::addTerm( Node n ){ - TheoryModel::addTerm( n ); -} - void FirstOrderModel::initialize( bool considerAxioms ){ //rebuild models d_uf_model_tree.clear(); diff --git a/src/theory/quantifiers/first_order_model.h b/src/theory/quantifiers/first_order_model.h index 3779579fd..50a941968 100644 --- a/src/theory/quantifiers/first_order_model.h +++ b/src/theory/quantifiers/first_order_model.h @@ -33,8 +33,6 @@ class TermDb; class FirstOrderModel : public TheoryModel { private: - //add term function - void addTerm( Node n ); //for initialize model void initializeModelForTerm( Node n ); /** whether an axiom is asserted */ diff --git a/src/theory/quantifiers/inst_strategy_cbqi.cpp b/src/theory/quantifiers/inst_strategy_cbqi.cpp index d79ddee31..ddf763b73 100755 --- a/src/theory/quantifiers/inst_strategy_cbqi.cpp +++ b/src/theory/quantifiers/inst_strategy_cbqi.cpp @@ -46,11 +46,12 @@ void InstStrategySimplex::processResetInstantiationRound( Theory::Effort effort d_tableaux.clear();
d_ceTableaux.clear();
//search for instantiation rows in simplex tableaux
- ArithVarToNodeMap avtnm = d_th->d_arithvarNodeMap.getArithVarToNodeMap();
- for( ArithVarToNodeMap::iterator it = avtnm.begin(); it != avtnm.end(); ++it ){
- ArithVar x = (*it).first;
+ ArithVarNodeMap& avnm = d_th->d_arithvarNodeMap;
+ ArithVarNodeMap::var_iterator vi, vend;
+ for(vi = avnm.var_begin(), vend = avnm.var_end(); vi != vend; ++vi ){
+ ArithVar x = *vi;
if( d_th->d_partialModel.hasEitherBound( x ) ){
- Node n = (*it).second;
+ Node n = avnm.asNode(x);
Node f;
NodeBuilder<> t(kind::PLUS);
if( n.getKind()==PLUS ){
@@ -167,10 +168,11 @@ void InstStrategySimplex::addTermToRow( ArithVar x, Node n, Node& f, NodeBuilder }
void InstStrategySimplex::debugPrint( const char* c ){
- ArithVarToNodeMap avtnm = d_th->d_arithvarNodeMap.getArithVarToNodeMap();
- for( ArithVarToNodeMap::iterator it = avtnm.begin(); it != avtnm.end(); ++it ){
- ArithVar x = (*it).first;
- Node n = (*it).second;
+ const ArithVarNodeMap& avnm = d_th->d_arithvarNodeMap;
+ ArithVarNodeMap::var_iterator vi, vend;
+ for(vi = avnm.var_begin(), vend = avnm.var_end(); vi != vend; ++vi ){
+ ArithVar x = *vi;
+ Node n = avnm.asNode(x);
//if( ((TheoryArith*)getTheory())->d_partialModel.hasEitherBound( x ) ){
Debug(c) << x << " : " << n << ", bounds = ";
if( d_th->d_partialModel.hasLowerBound( x ) ){
diff --git a/src/theory/rewriterules/theory_rewriterules.cpp b/src/theory/rewriterules/theory_rewriterules.cpp index c6fd9611c..a82b94f73 100644 --- a/src/theory/rewriterules/theory_rewriterules.cpp +++ b/src/theory/rewriterules/theory_rewriterules.cpp @@ -276,7 +276,7 @@ void TheoryRewriteRules::check(Effort level) { if(glast.inst == RULEINST_TRUE||glast.inst == RULEINST_FALSE) continue; // If it has a value it should already has been notified - bool value; value = value; // avoiding the warning in non debug mode + bool value CVC4_UNUSED; Assert(!getValuation().hasSatValue(g,value)); Debug("rewriterules::check") << "RewriteRules::Check Narrowing on:" << g << std::endl; /** Can split on already rewritten instrule... but... */ diff --git a/src/theory/shared_terms_database.h b/src/theory/shared_terms_database.h index 655918986..c7036a9ad 100644 --- a/src/theory/shared_terms_database.h +++ b/src/theory/shared_terms_database.h @@ -66,7 +66,7 @@ private: AlreadyNotifiedMap d_alreadyNotifiedMap; /** The registered equalities for propagation */ - typedef context::CDHashSet<TNode, TNodeHashFunction> RegisteredEqualitiesSet; + typedef context::CDHashSet<Node, NodeHashFunction> RegisteredEqualitiesSet; RegisteredEqualitiesSet d_registeredEqualities; private: diff --git a/src/theory/theory.h b/src/theory/theory.h index f317d4b92..5b2032430 100644 --- a/src/theory/theory.h +++ b/src/theory/theory.h @@ -33,6 +33,7 @@ #include "options/options.h" #include "util/statistics_registry.h" #include "util/dump.h" +#include "lib/ffs.h" #include <string> #include <iostream> @@ -49,13 +50,13 @@ namespace theory { class QuantifiersEngine; class TheoryModel; -namespace rrinst{ -class CandidateGenerator; -} +namespace rrinst { + class CandidateGenerator; +}/* CVC4::theory::rrinst namespace */ namespace eq { -class EqualityEngine; -} + class EqualityEngine; +}/* CVC4::theory::eq namespace */ /** * Information about an assertion for the theories. @@ -786,14 +787,10 @@ public: std::hash_set<TNode, TNodeHashFunction> currentlySharedTerms() const; };/* class Theory */ -std::ostream& operator<<(std::ostream& os, Theory::Effort level); - -namespace eq{ - class EqualityEngine; -} - +std::ostream& operator<<(std::ostream& os, theory::Theory::Effort level); +inline std::ostream& operator<<(std::ostream& out, const theory::Assertion& a); -inline Assertion Theory::get() { +inline theory::Assertion Theory::get() { Assert( !done(), "Theory::get() called with assertion queue empty!" ); // Get the assertion @@ -809,7 +806,9 @@ inline Assertion Theory::get() { return fact; } -}/* CVC4::theory namespace */ +inline std::ostream& operator<<(std::ostream& out, const theory::Assertion& a) { + return out << a.assertion; +} inline std::ostream& operator<<(std::ostream& out, const CVC4::theory::Theory& theory) { @@ -830,6 +829,7 @@ inline std::ostream& operator << (std::ostream& out, theory::Theory::PPAssertSta return out; } +}/* CVC4::theory namespace */ }/* CVC4 namespace */ #endif /* __CVC4__THEORY__THEORY_H */ diff --git a/src/theory/theory_engine.h b/src/theory/theory_engine.h index 063943056..27371eac3 100644 --- a/src/theory/theory_engine.h +++ b/src/theory/theory_engine.h @@ -190,7 +190,7 @@ class TheoryEngine { * context-dependent set of those theory-propagable literals that * have been propagated. */ - context::CDHashSet<TNode, TNodeHashFunction> d_hasPropagated; + context::CDHashSet<Node, NodeHashFunction> d_hasPropagated; /** * Statistics for a particular theory. diff --git a/src/util/dense_map.h b/src/util/dense_map.h index fa78e6787..222a761c3 100644 --- a/src/util/dense_map.h +++ b/src/util/dense_map.h @@ -151,6 +151,7 @@ public: pop_back(); } + /** Returns the key at the back of a non-empty list.*/ Key back() const { return d_list.back(); } @@ -164,6 +165,27 @@ public: d_list.pop_back(); } + + /** Adds at least a constant fraction of the elements in the current map to another map. */ + void splitInto(DenseMap<T>& target){ + uint32_t targetSize = size()/2; + while(size() > targetSize){ + Key key = back(); + target.set(key, get(key)); + pop_back(); + } + } + + /** Adds the current target map to the current map.*/ + void addAll(const DenseMap<T>& target){ + for(const_iterator i = target.begin(), e = target.end(); i != e; ++i){ + Key k = *i; + set(k, target[k]); + } + } + + + private: size_t allocated() const { diff --git a/src/util/node_visitor.h b/src/util/node_visitor.h index e444ba6e2..4c8e646bd 100644 --- a/src/util/node_visitor.h +++ b/src/util/node_visitor.h @@ -36,10 +36,11 @@ class NodeVisitor { /** * Guard against NodeVisitor<> being re-entrant. */ + template <class T> class GuardReentry { - bool& d_guard; + T& d_guard; public: - GuardReentry(bool& guard) + GuardReentry(T& guard) : d_guard(guard) { Assert(!d_guard); d_guard = true; @@ -71,7 +72,7 @@ public: */ static typename Visitor::return_type run(Visitor& visitor, TNode node) { - GuardReentry guard(bool(s_inRun)); + GuardReentry<CVC4_THREADLOCAL_TYPE(bool)> guard(s_inRun); // Notify of a start visitor.start(node); diff --git a/src/util/record.h b/src/util/record.h index 2c15d30e0..27b090e1d 100644 --- a/src/util/record.h +++ b/src/util/record.h @@ -29,7 +29,7 @@ namespace CVC4 { -class Record; +class CVC4_PUBLIC Record; // operators for record select and update diff --git a/src/util/statistics_registry.cpp b/src/util/statistics_registry.cpp index b86b557e2..8f9f05031 100644 --- a/src/util/statistics_registry.cpp +++ b/src/util/statistics_registry.cpp @@ -17,7 +17,9 @@ #include "util/statistics_registry.h" #include "expr/expr_manager.h" -#include "lib/clock_gettime.h" +#ifndef __WIN32__ +# include "lib/clock_gettime.h" +#endif /* ! __WIN32__ */ #include "smt/smt_engine.h" #ifndef __BUILDING_STATISTICS_FOR_EXPORT @@ -102,14 +104,17 @@ void StatisticsRegistry::flushInformation(std::ostream &out) const { } void TimerStat::start() { +#ifndef __WIN32__ if(__CVC4_USE_STATISTICS) { CheckArgument(!d_running, *this, "timer already running"); clock_gettime(CLOCK_MONOTONIC, &d_start); d_running = true; } +#endif /* ! __WIN32__ */ }/* TimerStat::start() */ void TimerStat::stop() { +#ifndef __WIN32__ if(__CVC4_USE_STATISTICS) { CheckArgument(d_running, *this, "timer not running"); ::timespec end; @@ -117,6 +122,7 @@ void TimerStat::stop() { d_data += end - d_start; d_running = false; } +#endif /* ! __WIN32__ */ }/* TimerStat::stop() */ RegisterStatistic::RegisterStatistic(ExprManager& em, Stat* stat) : diff --git a/src/util/statistics_registry.h b/src/util/statistics_registry.h index 3bf990dbb..32aa33bed 100644 --- a/src/util/statistics_registry.h +++ b/src/util/statistics_registry.h @@ -612,10 +612,14 @@ public: };/* class StatisticsRegistry */ +#ifndef __WIN32__ + /****************************************************************************/ /* Some utility functions for timespec */ /****************************************************************************/ +inline std::ostream& operator<<(std::ostream& os, const timespec& t); + /** Compute the sum of two timespecs. */ inline timespec& operator+=(timespec& a, const timespec& b) { // assumes a.tv_nsec and b.tv_nsec are in range @@ -765,6 +769,25 @@ public: };/* class TimerStat */ +#else /* __WIN32__ */ + +class CodeTimer; + +class TimerStat : public IntStat { +public: + + typedef CVC4::CodeTimer CodeTimer; + + TimerStat(const std::string& name) : + IntStat(name, 0) { + } + + void start(); + void stop(); + +};/* class TimerStat */ + +#endif /* __WIN32__ */ /** * Utility class to make it easier to call stop() at the end of a @@ -788,7 +811,6 @@ public: } };/* class CodeTimer */ - /** * To use a statistic, you need to declare it, initialize it in your * constructor, register it in your constructor, and deregister it in |