#include "varorderingopt.h"
#include <time.h>
#include <stdarg.h>
-#include "alloyenc.h"
+#include "alloyinterpreter.h"
+#include "smtinterpreter.h"
+#include "mathsatinterpreter.h"
+#include "smtratinterpreter.h"
CSolver::CSolver() :
boolTrue(BooleanEdge(new BooleanConst(true))),
boolFalse(boolTrue.negate()),
unsat(false),
booleanVarUsed(false),
+ incrementalMode(false),
+ optimizationsOff(false),
tuner(NULL),
elapsedTime(0),
satsolverTimeout(NOTIMEOUT),
- alloyEncoder(NULL)
+ interpreter(NULL)
{
satEncoder = new SATEncoder(this);
}
delete allFunctions.get(i);
}
+ if (interpreter != NULL) {
+ delete interpreter;
+ }
+
delete boolTrue.getBoolean();
delete satEncoder;
}
allOrders.clear();
allFunctions.clear();
constraints.reset();
+ encodedConstraints.reset();
activeOrders.reset();
boolMap.reset();
elemMap.reset();
return copy;
}
-CSolver *CSolver::deserialize(const char *file, bool alloy) {
+CSolver *CSolver::deserialize(const char *file, InterpreterType itype) {
model_print("deserializing %s ...\n", file);
- Deserializer deserializer(file, alloy);
+ Deserializer deserializer(file, itype);
return deserializer.deserialize();
}
element->anyValue = true;
}
+void CSolver::freezeElementsVariables() {
+
+ for (uint i = 0; i < allElements.getSize(); i++) {
+ Element *e = allElements.get(i);
+ if (e->frozen) {
+ satEncoder->freezeElementVariables(&e->encoding);
+ }
+ }
+}
+
+
Set *CSolver::getElementRange (Element *element) {
return element->getRange();
}
Element *CSolver::applyFunction(Function *function, Element **array, uint numArrays, BooleanEdge overflowstatus) {
- ASSERT(numArrays == 2);
Element *element = new ElementFunction(function,array,numArrays,overflowstatus);
Element *e = elemMap.get(element);
if (e == NULL) {
BooleanEdge CSolver::getBooleanVar(VarType type) {
Boolean *boolean = new BooleanVar(type);
allBooleans.push(boolean);
- if(!booleanVarUsed)
+ if (!booleanVarUsed)
booleanVarUsed = true;
return BooleanEdge(boolean);
}
return applyLogicalOperation(op, newarray, asize);
}
+BooleanEdge CSolver::applyExactlyOneConstraint (BooleanEdge *array, uint asize) {
+ BooleanEdge newarray[asize + 1];
+
+ newarray[asize] = applyLogicalOperation(SATC_OR, array, asize);
+ for (uint i = 0; i < asize; i++) {
+ BooleanEdge oprand1 = array[i];
+ BooleanEdge carray [asize - 1];
+ uint index = 0;
+ for ( uint j = 0; j < asize; j++) {
+ if (i != j) {
+ BooleanEdge oprand2 = applyLogicalOperation(SATC_NOT, array[j]);
+ carray[index++] = applyLogicalOperation(SATC_IMPLIES, oprand1, oprand2);
+ }
+ }
+ ASSERT(index == asize - 1);
+ newarray[i] = applyLogicalOperation(SATC_AND, carray, asize - 1);
+ }
+ return applyLogicalOperation(SATC_AND, newarray, asize + 1);
+}
+
BooleanEdge CSolver::applyLogicalOperation(LogicOp op, BooleanEdge *array, uint asize) {
- if(!useAlloyCompiler()){
+ if (!useInterpreter()) {
BooleanEdge newarray[asize];
switch (op) {
case SATC_NOT: {
return applyLogicalOperation(SATC_OR, applyLogicalOperation(SATC_NOT, array[0]), array[1]);
}
}
-
+
ASSERT(asize != 0);
Boolean *boolean = new BooleanLogic(this, op, array, asize);
Boolean *b = boolMap.get(boolean);
Boolean *boolean = new BooleanLogic(this, op, array, asize);
allBooleans.push(boolean);
return BooleanEdge(boolean);
-
+
}
}
}
}
Boolean *constraint = new BooleanOrder(order, first, second);
- if (!useAlloyCompiler() ){
+ if (!useInterpreter() ) {
Boolean *b = boolMap.get(constraint);
if (b == NULL) {
}
void CSolver::addConstraint(BooleanEdge constraint) {
- if(!useAlloyCompiler()){
+ if (!useInterpreter() && !optimizationsOff) {
if (isTrue(constraint))
return;
else if (isFalse(constraint)) {
replaceBooleanWithTrueNoRemove(constraint);
constraint->parents.clear();
}
- } else{
+ } else {
constraints.add(constraint);
constraint->parents.clear();
}
}
}
+int CSolver::solveIncremental() {
+ if (isUnSAT()) {
+ return IS_UNSAT;
+ }
+
+
+ long long startTime = getTimeNano();
+ bool deleteTuner = false;
+ if (tuner == NULL) {
+ tuner = new DefaultTuner();
+ deleteTuner = true;
+ }
+ int result = IS_INDETER;
+ ASSERT (!useInterpreter());
+ if(!optimizationsOff){
+ computePolarities(this);
+ }
+// long long time1 = getTimeNano();
+// model_print("Polarity time: %f\n", (time1 - startTime) / NANOSEC);
+// Preprocess pp(this);
+// pp.doTransform();
+// long long time2 = getTimeNano();
+// model_print("Preprocess time: %f\n", (time2 - time1) / NANOSEC);
+
+// DecomposeOrderTransform dot(this);
+// dot.doTransform();
+// time1 = getTimeNano();
+// model_print("Decompose Order: %f\n", (time1 - time2) / NANOSEC);
+
+// IntegerEncodingTransform iet(this);
+// iet.doTransform();
+
+ //Doing element optimization on new constraints
+// ElementOpt eop(this);
+// eop.doTransform();
+
+ //Since no new element is added, we assuming adding new constraint
+ //has no impact on previous encoding decisions
+// EncodingGraph eg(this);
+// eg.encode();
+
+ naiveEncodingDecision(this);
+ // eg.validate();
+ //Order of sat solver variables don't change!
+// VarOrderingOpt bor(this, satEncoder);
+// bor.doTransform();
+
+ long long time2 = getTimeNano();
+ //Encoding newly added constraints
+ satEncoder->encodeAllSATEncoder(this);
+ long long time1 = getTimeNano();
+
+ model_print("Elapse Encode time: %f\n", (time1 - startTime) / NANOSEC);
+
+ model_print("Is problem UNSAT after encoding: %d\n", unsat);
+
+ result = unsat ? IS_UNSAT : satEncoder->solve(satsolverTimeout);
+ model_print("Result Computed in SAT solver:\t%s\n", result == IS_SAT ? "SAT" : result == IS_INDETER ? "INDETERMINATE" : " UNSAT");
+ time2 = getTimeNano();
+ elapsedTime = time2 - startTime;
+ model_print("CSOLVER solve time: %f\n", elapsedTime / NANOSEC);
+
+ if (deleteTuner) {
+ delete tuner;
+ tuner = NULL;
+ }
+ return result;
+}
+
int CSolver::solve() {
+ if (isUnSAT()) {
+ return IS_UNSAT;
+ }
long long startTime = getTimeNano();
bool deleteTuner = false;
if (tuner == NULL) {
deleteTuner = true;
}
int result = IS_INDETER;
- if(useAlloyCompiler()){
- alloyEncoder->encode();
- model_print("Problem encoded in Alloy\n");
- result = alloyEncoder->solve();
- model_print("Problem solved by Alloy\n");
- } else{
+ if (useInterpreter()) {
+ interpreter->encode();
+ model_print("Problem encoded in Interpreter\n");
+ result = interpreter->solve();
+ model_print("Problem solved by Interpreter\n");
+ } else {
{
SetIteratorOrder *orderit = activeOrders.iterator();
}
delete orderit;
}
+ long long time1, time2;
+
computePolarities(this);
- long long time1 = getTimeNano();
- model_print("Polarity time: %f\n", (time1 - startTime) / NANOSEC);
- Preprocess pp(this);
- pp.doTransform();
- long long time2 = getTimeNano();
- model_print("Preprocess time: %f\n", (time2 - time1) / NANOSEC);
-
- DecomposeOrderTransform dot(this);
- dot.doTransform();
time1 = getTimeNano();
- model_print("Decompose Order: %f\n", (time1 - time2) / NANOSEC);
+ model_print("Polarity time: %f\n", (time1 - startTime) / NANOSEC);
+ if(!optimizationsOff){
+ Preprocess pp(this);
+ pp.doTransform();
+ time2 = getTimeNano();
+ model_print("Preprocess time: %f\n", (time2 - time1) / NANOSEC);
- IntegerEncodingTransform iet(this);
- iet.doTransform();
+ DecomposeOrderTransform dot(this);
+ dot.doTransform();
+ time1 = getTimeNano();
+ model_print("Decompose Order: %f\n", (time1 - time2) / NANOSEC);
- ElementOpt eop(this);
- eop.doTransform();
+ IntegerEncodingTransform iet(this);
+ iet.doTransform();
- EncodingGraph eg(this);
- eg.encode();
+ ElementOpt eop(this);
+ eop.doTransform();
+ EncodingGraph eg(this);
+ eg.encode();
+ }
naiveEncodingDecision(this);
- // eg.validate();
-
- VarOrderingOpt bor(this, satEncoder);
- bor.doTransform();
-
- time2 = getTimeNano();
- model_print("Encoding Graph Time: %f\n", (time2 - time1) / NANOSEC);
+ // eg.validate();
+ if(!optimizationsOff){
+ VarOrderingOpt bor(this, satEncoder);
+ bor.doTransform();
+ time2 = getTimeNano();
+ model_print("Encoding Graph Time: %f\n", (time2 - time1) / NANOSEC);
+ }
satEncoder->encodeAllSATEncoder(this);
time1 = getTimeNano();
model_print("Elapse Encode time: %f\n", (time1 - startTime) / NANOSEC);
model_print("Is problem UNSAT after encoding: %d\n", unsat);
-
+
result = unsat ? IS_UNSAT : satEncoder->solve(satsolverTimeout);
model_print("Result Computed in SAT solver:\t%s\n", result == IS_SAT ? "SAT" : result == IS_INDETER ? "INDETERMINATE" : " UNSAT");
return result;
}
-void CSolver::setAlloyEncoder(){
- if(alloyEncoder == NULL){
- alloyEncoder = new AlloyEnc(this);
+void CSolver::setInterpreter(InterpreterType type) {
+ if (interpreter == NULL) {
+ switch (type) {
+ case SATUNE:
+ break;
+ case ALLOY: {
+ interpreter = new AlloyInterpreter(this);
+ break;
+ } case Z3: {
+ interpreter = new SMTInterpreter(this);
+ break;
+ }
+ case MATHSAT: {
+ interpreter = new MathSATInterpreter(this);
+ break;
+ }
+ case SMTRAT: {
+ interpreter = new SMTRatInterpreter(this);
+ break;
+ }
+ default:
+ ASSERT(0);
+ }
}
}
case ELEMSET:
case ELEMCONST:
case ELEMFUNCRETURN:
- return useAlloyCompiler()? alloyEncoder->getValue(element):
- getElementValueSATTranslator(this, element);
+ return useInterpreter() ? interpreter->getValue(element) :
+ getElementValueSATTranslator(this, element);
default:
ASSERT(0);
}
exit(-1);
}
+void CSolver::freezeElement(Element *e) {
+ e->freezeElement();
+ if (!incrementalMode) {
+ incrementalMode = true;
+ }
+}
+
bool CSolver::getBooleanValue(BooleanEdge bedge) {
Boolean *boolean = bedge.getBoolean();
switch (boolean->type) {
case BOOLEANVAR:
- return useAlloyCompiler()? alloyEncoder->getBooleanValue(boolean):
- getBooleanVariableValueSATTranslator(this, boolean);
+ return useInterpreter() ? interpreter->getBooleanValue(boolean) :
+ getBooleanVariableValueSATTranslator(this, boolean);
default:
ASSERT(0);
}