/**CFile*********************************************************************** FileName [smtDebug.c] PackageName [smt] Synopsis [Routines for smt function.] Author [Hyondeuk Kim] Copyright [Copyright (c) 1995-2004, Regents of the University of Colorado All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of the University of Colorado nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.] ******************************************************************************/ #ifdef HAVE_LIBGMP #include "smt.h" void smt_print_atom_variable(smtManager_t * sm) { satManager_t * cm = sm->cm; smtAvar_t * avar; int value = 2; int i; for(i = 0; i < sm->avarArr->size; i++) { avar = (smtAvar_t *) sm->avarArr->space[i]; if (cm) value = cm->values[SATVar(avar->id)]; fprintf(stdout, "%d:%s:%d\n", avar->id, avar->name, value); } } void smt_print_atom_variable_in_array(smtManager_t * sm, satArray_t * avarArr) { satManager_t * cm = sm->cm; smtAvar_t * avar; int value = 2; int i; for(i = 0; i < avarArr->size; i++) { avar = (smtAvar_t *) avarArr->space[i]; if (cm) value = cm->values[SATVar(avar->id)]; fprintf(stdout, "%d:%s:%d\n", avar->id, avar->name, value); } } void smt_print_numerical_variable(smtManager_t * sm) { smtNvar_t * nvar; int i; for(i = 0; i < sm->nvarArr->size; i++) { nvar = (smtNvar_t *) sm->nvarArr->space[i]; fprintf(stdout, "%d:%s\n", nvar->id, nvar->name); } } void smt_print_numerical_variable_in_array( satArray_t * nvarArr) { smtNvar_t * nvar; int i; for(i = 0; i < nvarArr->size; i++) { nvar = (smtNvar_t *) nvarArr->space[i]; fprintf(stdout, "%d:%s\n", nvar->id, nvar->name); } } void smt_print_nvar_with_value(smtManager_t * sm) { smtNvar_t *nvar; int i; for(i = 0; i < sm->nvarArr->size; i++) { nvar = (smtNvar_t *) sm->nvarArr->space[i]; if (sm->flag & IDL_MASK) fprintf(stdout, "%s=%d\n", nvar->name, sm->ivalues[nvar->id]); else if (sm->flag & RDL_MASK) fprintf(stdout, "%s=%g\n", nvar->name, sm->rvalues[nvar->id]); } return; } void smt_print_nvar_value_in_tableau(smtManager_t * sm) { smtNvar_t * nvar; double value; int i; for(i = 0; i < sm->tab_nvars->size; i++) { nvar = (smtNvar_t *) sm->tab_nvars->space[i]; value = sm->rvalues[nvar->id]; fprintf(stdout, "%s:%g\n", nvar->name, value); } } void smt_check_nvar_value_with_tableau(smtManager_t * sm) { double * tab = sm->tab; smtNvar_t * nvar; double coeff, sum; int col, num_col, index; int i, j; num_col = sm->tab_nvars->size; for(i = 0; i < sm->basics->size; i++) { for(j = 0, sum = 0; j < sm->tab_nvars->size; j++) { nvar = (smtNvar_t *) sm->tab_nvars->space[j]; col = nvar->id; index = i * num_col + col; coeff = tab[index]; if (coeff <= 0 && coeff >= 0) continue; sum = sum + coeff * sm->rvalues[nvar->id]; } assert(sum==0); } } void smt_print_nvar_bound_in_tableau(smtManager_t * sm) { smtNvar_t * nvar; smtBound_t * bound; int i; for(i = 0; i < sm->tab_nvars->size; i++) { nvar = (smtNvar_t *) sm->tab_nvars->space[i]; bound = &(sm->bounds[nvar->id]); fprintf(stdout, "%g <= %s <= %g\n", bound->lb, nvar->name, bound->ub); } } void smt_print_atom_for_slack(smtManager_t * sm) { smtAvar_t * avar; smtNvar_t * slack, * nvar; double coeff; int i, j; for(i = 0; i < sm->slacks->size; i++) { slack = (smtNvar_t *) sm->slacks->space[i]; avar = (smtAvar_t *) slack->avarArr->space[0]; fprintf(stdout, "%s:", slack->name); for(j = 0; j < avar->nvars->size; j++) { coeff = array_fetch(double, avar->coeffs, j); nvar = (smtNvar_t *) avar->nvars->space[j]; if (avar->flag & SIGNED_MASK) coeff = -coeff; fprintf(stdout, "%g*%s ", coeff, nvar->name); } fprintf(stdout, "\n"); } } void smt_print_boolean_variable(smtManager_t * sm) { satManager_t * cm = sm->cm; smtBvar_t * bvar; int value = 2; int i; for(i = 0; i < sm->bvarArr->size; i++) { bvar = (smtBvar_t *) sm->bvarArr->space[i]; if (cm) value = cm->values[SATVar(bvar->id)]; fprintf(stdout, "%d:%s:%d\n", bvar->id, bvar->name, value); } } void smt_print_flet_pair(smtManager_t * sm) { smtFlet_t * flet; int i; char * fvar_str, * fml_str; for(i = 0; i < sm->fletArr->size; i++) { flet = (smtFlet_t *) sm->fletArr->space[i]; fvar_str = smt_convert_fml_to_string(flet->fvar_fml); fml_str = smt_convert_fml_to_string(flet->fml); fprintf(stdout, "%s <-> %s\n", fvar_str, fml_str); free(fvar_str); free(fml_str); } } void smt_print_cnf_to_smt_file(smtManager_t * sm) { FILE * fp; smtCls_t * cls; smtAvar_t * avar; smtBvar_t * bvar; smtNvar_t * nvar; satArray_t * clsArr = sm->clsArr; char * filename; int id, lit, i, j; if (sm->clsArr->size == 0) return; if (sm->filename) filename = util_strcat3(sm->filename, ".cnf.smt", ""); else return; fp = fopen(filename, "w"); fprintf(fp, "(benchmark %s\n", filename); fprintf(fp, ":source {\n"); fprintf(fp, "SMT Formula is translated by Hyondeuk Kim in CNF SMT-LIB format benchmark\n"); fprintf(fp, "}\n"); fprintf(fp, ":status unknown\n"); if (sm->flag & LIA_MASK) fprintf(fp, ":logic QF_LIA\n"); else if (sm->flag & LRA_MASK) fprintf(fp, ":logic QF_LRA\n"); else if (sm->flag & IDL_MASK) fprintf(fp, ":logic QF_IDL\n"); else if (sm->flag & RDL_MASK) fprintf(fp, ":logic QF_RDL\n"); for(i = 0; i < sm->bvarArr->size; i++) { bvar = (smtBvar_t *) sm->bvarArr->space[i]; fprintf(fp, " :extrapreds ((%s))\n", bvar->name); } for(i = 0; i < sm->nvarArr->size; i++) { nvar = (smtNvar_t *) sm->nvarArr->space[i]; if (sm->flag & LIA_MASK || sm->flag & IDL_MASK) fprintf(fp, " :extrafuns ((%s Int))\n", nvar->name); else if (sm->flag & LRA_MASK || sm->flag & RDL_MASK) fprintf(fp, " :extrafuns ((%s Real))\n", nvar->name); } fprintf(fp, ":formula\n"); fprintf(fp, "( and\n"); for(i = 0; i < clsArr->size; i++) { fprintf(fp, "( or "); cls = (smtCls_t *) clsArr->space[i]; for(j = 0; j < cls->litArr->size; j++) { lit = cls->litArr->space[j]; if (lit > 0) { id = lit; if (id > sm->avarArr->size) { bvar = (smtBvar_t *) sm->id2var->space[id]; fprintf(fp, "%s ", bvar->name); } else { avar = (smtAvar_t *) sm->id2var->space[id]; fprintf(fp, "%s ", avar->name); } } else { id = -lit; if (id > sm->avarArr->size) { bvar = (smtBvar_t *) sm->id2var->space[id]; fprintf(fp, "(not %s) ", bvar->name); } else { avar = (smtAvar_t *) sm->id2var->space[id]; fprintf(fp, "(not %s) ", avar->name); } } } fprintf(fp, " )\n"); } fprintf(fp, "))"); fclose(fp); free(filename); } void smt_print_cnf_to_smt_file_with_avar(smtManager_t * sm) { FILE * fp; smtCls_t * cls; smtAvar_t * avar; smtBvar_t * bvar; smtNvar_t * nvar; satArray_t * clsArr = sm->clsArr; char * filename; char * str_a, * str_b, * str_c, * str_d, * str_e; double coeff, tcoeff, constant, tconstant; int id, lit; int i, j, k; if (sm->clsArr->size == 0) return; if (sm->filename) filename = util_strcat3(sm->filename, ".cnf.smt", ""); else return; fp = fopen(filename, "w"); fprintf(fp, "(benchmark %s\n", filename); fprintf(fp, ":source {\n"); fprintf(fp, "SMT Formula is translated by Hyondeuk Kim in CNF SMT-LIB format benchmark\n"); fprintf(fp, "}\n"); fprintf(fp, ":status unknown\n"); if (sm->flag & LIA_MASK) fprintf(fp, ":logic QF_LIA\n"); else if (sm->flag & LRA_MASK) fprintf(fp, ":logic QF_LRA\n"); else if (sm->flag & IDL_MASK) fprintf(fp, ":logic QF_IDL\n"); else if (sm->flag & RDL_MASK) fprintf(fp, ":logic QF_RDL\n"); for(i = 0; i < sm->bvarArr->size; i++) { bvar = (smtBvar_t *) sm->bvarArr->space[i]; fprintf(fp, " :extrapreds ((%s))\n", bvar->name); } for(i = 0; i < sm->nvarArr->size; i++) { nvar = (smtNvar_t *) sm->nvarArr->space[i]; if (sm->flag & LIA_MASK || sm->flag & IDL_MASK) fprintf(fp, " :extrafuns ((%s Int))\n", nvar->name); else if (sm->flag & LRA_MASK || sm->flag & RDL_MASK) fprintf(fp, " :extrafuns ((%s Real))\n", nvar->name); } fprintf(fp, ":formula\n"); fprintf(fp, "( and\n"); str_b = (char *) malloc(sizeof(char) * 10); for(i = 0; i < clsArr->size; i++) { fprintf(fp, "( or "); cls = (smtCls_t *) clsArr->space[i]; for(j = 0; j < cls->litArr->size; j++) { lit = cls->litArr->space[j]; if (lit > 0) { id = lit; if (id > sm->avarArr->size) { bvar = (smtBvar_t *) sm->id2var->space[id]; fprintf(fp, "%s ", bvar->name); } else { avar = (smtAvar_t *) sm->id2var->space[id]; str_a = util_strsav("(<= (+ "); for(k = 0; k < avar->nvars->size; k++) { coeff = array_fetch(double, avar->coeffs, k); tcoeff = (coeff > 0) ? coeff : -coeff; sprintf(str_b, "%d", (int) tcoeff); nvar = (smtNvar_t *) avar->nvars->space[k]; if (coeff > 0) { str_c = util_strcat3("(* ", str_b, " "); str_d = util_strcat3(str_c, nvar->name, ") "); } else { str_c = util_strcat3("(* (~ ", str_b, ") "); str_d = util_strcat3(str_c, nvar->name, ") "); } str_e = str_a; str_a = util_strcat3(str_a, str_d, ""); free(str_c); free(str_d); free(str_e); } constant = avar->constant; tconstant = (constant >= 0) ? constant : -constant; if (constant >= 0) { sprintf(str_b, "%d", (int) tconstant); str_e = util_strsav(str_b); } else { sprintf(str_b, "%d", (int) tconstant); str_e = util_strcat3("(~ ", str_b, ") "); } str_c = util_strcat3(str_a, ") ", str_e); str_d = util_strcat3(str_c, " ) ", ""); fprintf(fp, "%s ", str_d); /* fprintf(stdout, "%s\n", str_d); */ free(str_a); free(str_c); free(str_d); free(str_e); } } else { id = -lit; if (id > sm->avarArr->size) { bvar = (smtBvar_t *) sm->id2var->space[id]; fprintf(fp, "(not %s) ", bvar->name); } else { avar = (smtAvar_t *) sm->id2var->space[id]; str_a = util_strsav("(<= (+ "); for(k = 0; k < avar->nvars->size; k++) { coeff = array_fetch(double, avar->coeffs, k); tcoeff = (coeff > 0) ? coeff : -coeff; sprintf(str_b, "%d", (int) tcoeff); nvar = (smtNvar_t *) avar->nvars->space[k]; if (coeff > 0) { str_c = util_strcat3("(* ", str_b, " "); str_d = util_strcat3(str_c, nvar->name, ") "); } else { str_c = util_strcat3("(* (~ ", str_b, ") "); str_d = util_strcat3(str_c, nvar->name, ") "); } str_e = str_a; str_a = util_strcat3(str_a, str_d, ""); free(str_c); free(str_d); free(str_e); } constant = avar->constant; tconstant = (constant >= 0) ? constant : -constant; if (constant >= 0) { sprintf(str_b, "%d", (int) tconstant); str_e = util_strsav(str_b); } else { sprintf(str_b, "%d", (int) tconstant); str_e = util_strcat3("(~ ", str_b, ") "); } str_c = util_strcat3(str_a, ") ", str_e); str_d = util_strcat3(str_c, " ) ", ""); fprintf(fp, "(not %s) ", str_d); free(str_a); free(str_c); free(str_d); free(str_e); } } } fprintf(fp, " )\n"); } fprintf(fp, "))"); fclose(fp); free(filename); free(str_b); } void smt_print_dimacs_to_smt_file(smtManager_t * sm) { FILE * fp; satManager_t * cm = sm->cm; satClause_t * c; smtAvar_t * avar; smtBvar_t * bvar; smtNvar_t * nvar; satArray_t * arr = cm->clauses; char * filename, * str_a, * str_b; int * vflags; long lit, v; int id, i, j, csize, value; if (arr->size == 0) return; if (sm->filename) filename = util_strcat3(sm->filename, ".dimacs.cnf.smt", ""); else return; vflags = (int *) malloc(sizeof(int) * sm->id2var->size); memset(vflags, 0, sizeof(int) * sm->id2var->size); for(i = 0; i < arr->size; i++) { c = (satClause_t *)arr->space[i]; csize = SATSizeClause(c); for(j = 0; j < csize; j++) { lit = c->lits[j]; v = lit >> 1; v = lit&1 ? -v : v; if (v > 0) id = (int) v; else id = (int) -v; vflags[id] = 1; } } fp = fopen(filename, "w"); fprintf(fp, "(benchmark %s\n", filename); fprintf(fp, ":source {\n"); fprintf(fp, "SMT Formula is translated by Hyondeuk Kim in CNF SMT-LIB format benchmark\n"); fprintf(fp, "}\n"); fprintf(fp, ":status unknown\n"); if (sm->flag & LIA_MASK) fprintf(fp, ":logic QF_LIA\n"); else if (sm->flag & LRA_MASK) fprintf(fp, ":logic QF_LRA\n"); else if (sm->flag & IDL_MASK) fprintf(fp, ":logic QF_IDL\n"); else if (sm->flag & RDL_MASK) fprintf(fp, ":logic QF_RDL\n"); for(i = 0; i < sm->bvarArr->size; i++) { bvar = (smtBvar_t *) sm->bvarArr->space[i]; if (vflags[bvar->id] && !(bvar->flag & BTRUE_MASK) && !(bvar->flag & BFALSE_MASK) ) fprintf(fp, " :extrapreds ((%s))\n", bvar->name); } for(i = 0; i < sm->nvarArr->size; i++) { nvar = (smtNvar_t *) sm->nvarArr->space[i]; if (sm->flag & LIA_MASK || sm->flag & IDL_MASK) fprintf(fp, " :extrafuns ((%s Int))\n", nvar->name); else if (sm->flag & LRA_MASK || sm->flag & RDL_MASK) fprintf(fp, " :extrafuns ((%s Real))\n", nvar->name); } fprintf(fp, ":formula\n"); fprintf(fp, "( and\n"); for(i = 0; i < arr->size; i++) { c = (satClause_t *)arr->space[i]; csize = SATSizeClause(c); for(j = 0, str_a = 0; j < csize; j++) { lit = c->lits[j]; v = lit >> 1; #if 1 if((cm->values[v] ^ (lit&1)) == 1) { if (str_a) { /* satisfied clause */ free(str_a); str_a = 0; } break; } /* cm->values[v] can be somehow 64, 85, ... */ else if (cm->values[v] == 1 || cm->values[v] == 0) { continue; /* unsat lit in clause : remove lit in clause */ } #endif v = lit&1 ? -v : v; if (v > 0) { id = (int) v; if (id > sm->avarArr->size) { bvar = (smtBvar_t *) sm->id2var->space[id]; str_b = str_a; if (str_a) str_a = util_strcat3(str_a, bvar->name, " "); else str_a = util_strcat3("", bvar->name, " "); if (str_b) free(str_b); } else { avar = (smtAvar_t *) sm->id2var->space[id]; str_b = str_a; if (str_a) str_a = util_strcat3(str_a, avar->name, " "); else str_a = util_strcat3("", avar->name, " "); if (str_b) free(str_b); } } else { id = (int) -v; if (id > sm->avarArr->size) { bvar = (smtBvar_t *) sm->id2var->space[id]; str_b = str_a; if (str_a) str_a = util_strcat3(str_a, "(not ", bvar->name); else str_a = util_strcat3("", "(not ", bvar->name); if (str_b) free(str_b); str_b = str_a; str_a = util_strcat3(str_a, ") ", ""); if (str_b) free(str_b); } else { avar = (smtAvar_t *) sm->id2var->space[id]; str_b = str_a; if (str_a) str_a = util_strcat3(str_a, "(not ", avar->name); else str_a = util_strcat3("", "(not ", avar->name); if (str_b) free(str_b); str_b = str_a; str_a = util_strcat3(str_a, ") ", ""); if (str_b) free(str_b); } } } if (str_a) { str_b = util_strcat3("( or ", str_a, " )\n"); fprintf(fp, "%s", str_b); free(str_a); free(str_b); } } /* require assigned predicates */ for(i = 0; i < sm->avarArr->size; i++) { avar = (smtAvar_t *) sm->avarArr->space[i]; id = avar->id; value = cm->values[id]; if (value == 1) fprintf(fp, "%s\n", avar->name); else if (value == 0) fprintf(fp, "(not %s)\n", avar->name); } #if 0 for(i = 0; i < sm->bvarArr->size; i++) { bvar = (smtBvar_t *) sm->bvarArr->space[i]; id = bvar->id; value = cm->values[id]; if (value == 1) fprintf(fp, "%s\n", bvar->name); else if (value == 0) fprintf(fp, "(not %s)\n", bvar->name); } #endif fprintf(fp, "))"); fclose(fp); free(filename); free(vflags); } void smt_print_cnf_to_dimcas_file(smtManager_t * sm) { FILE * fp; smtCls_t * cls; smtAvar_t * avar; smtBvar_t * bvar; satArray_t * clsArr = sm->clsArr; char * filename; int id, lit, i, j; if (sm->clsArr->size == 0) return; if (sm->filename) filename = util_strcat3(sm->filename, ".cnf", ""); else return; fp = fopen(filename, "w"); fprintf(fp, "p cnf %ld %ld\n", sm->id2var->size, sm->clsArr->size); for(i = 0; i < sm->bvarArr->size; i++) { bvar = (smtBvar_t *) sm->bvarArr->space[i]; fprintf(fp, "c %d:((%s))\n", bvar->id, bvar->name); } for(i = 0; i < sm->avarArr->size; i++) { avar = (smtAvar_t *) sm->avarArr->space[i]; fprintf(fp, "c %d:((%s))\n", avar->id, avar->name); } for(i = 0; i < clsArr->size; i++) { cls = (smtCls_t *) clsArr->space[i]; for(j = 0; j < cls->litArr->size; j++) { lit = cls->litArr->space[j]; if (lit > 0) { id = lit; if (id > sm->avarArr->size) { bvar = (smtBvar_t *) sm->id2var->space[id]; fprintf(fp, "%d ", bvar->id); } else { avar = (smtAvar_t *) sm->id2var->space[id]; fprintf(fp, "%d ", avar->id); } } else { id = -lit; if (id > sm->avarArr->size) { bvar = (smtBvar_t *) sm->id2var->space[id]; fprintf(fp, "%d ", -bvar->id); } else { avar = (smtAvar_t *) sm->id2var->space[id]; fprintf(fp, "%d ", -avar->id); } } } fprintf(fp, "0\n"); } fclose(fp); free(filename); } void smt_print_fml_to_smt_file(smtManager_t * sm, smtFml_t * fml, int index) { FILE * fp; smtBvar_t * bvar; smtNvar_t * nvar; satArray_t * bvarArr; char * filename, * num, * str; int i; if (sm->filename) { num = (char *) malloc(sizeof(char) * 10); memset(num, 0, sizeof(char) * 10); sprintf(num, ".%d", index); filename = util_strcat3(sm->filename, num, ".sub_fml.smt"); free(num); } else return; fp = fopen(filename, "w"); fprintf(fp, "(benchmark %s\n", filename); fprintf(fp, ":source {\n"); fprintf(fp, "SMT Formula is translated by Hyondeuk Kim in CNF SMT-LIB format benchmark\n"); fprintf(fp, "}\n"); fprintf(fp, ":status unknown\n"); if (sm->flag & LIA_MASK) fprintf(fp, ":logic QF_LIA\n"); else if (sm->flag & LRA_MASK) fprintf(fp, ":logic QF_LRA\n"); else if (sm->flag & IDL_MASK) fprintf(fp, ":logic QF_IDL\n"); else if (sm->flag & RDL_MASK) fprintf(fp, ":logic QF_RDL\n"); bvarArr = smt_gather_bvar_in_fml(sm, fml); for(i = 0; i < bvarArr->size; i++) { bvar = (smtBvar_t *) bvarArr->space[i]; fprintf(fp, " :extrapreds ((%s))\n", bvar->name); } for(i = 0; i < sm->nvarArr->size; i++) { nvar = (smtNvar_t *) sm->nvarArr->space[i]; if (sm->flag & LIA_MASK || sm->flag & IDL_MASK) fprintf(fp, " :extrafuns ((%s Int))\n", nvar->name); else if (sm->flag & LRA_MASK || sm->flag & RDL_MASK) fprintf(fp, " :extrafuns ((%s Real))\n", nvar->name); } fprintf(fp, ":formula\n"); str = smt_convert_fml_to_string(fml); fprintf(fp, "%s\n", str); fprintf(fp, ")"); fclose(fp); free(filename); free(bvarArr); free(str); return; } void smt_print_fml_to_file(smtManager_t * sm, smtFml_t * fml) { FILE * fp; smtBvar_t * bvar; smtNvar_t * nvar; satArray_t * bvarArr = 0; char * filename; int i; if (sm->filename) filename = util_strcat3(sm->filename, ".sub_fml.smt", ""); else return; fp = fopen(filename, "w"); fprintf(fp, "(benchmark %s\n", filename); fprintf(fp, ":source {\n"); fprintf(fp, "SMT Formula is translated by Hyondeuk Kim in CNF SMT-LIB format benchmark\n"); fprintf(fp, "}\n"); fprintf(fp, ":status unknown\n"); if (sm->flag & LIA_MASK) fprintf(fp, ":logic QF_LIA\n"); else if (sm->flag & LRA_MASK) fprintf(fp, ":logic QF_LRA\n"); else if (sm->flag & IDL_MASK) fprintf(fp, ":logic QF_IDL\n"); else if (sm->flag & RDL_MASK) fprintf(fp, ":logic QF_RDL\n"); for(i = 0; i < bvarArr->size; i++) { bvar = (smtBvar_t *) bvarArr->space[i]; fprintf(fp, " :extrapreds ((%s))\n", bvar->name); } for(i = 0; i < sm->nvarArr->size; i++) { nvar = (smtNvar_t *) sm->nvarArr->space[i]; if (sm->flag & LIA_MASK || sm->flag & IDL_MASK) fprintf(fp, " :extrafuns ((%s Int))\n", nvar->name); else if (sm->flag & LRA_MASK || sm->flag & RDL_MASK) fprintf(fp, " :extrafuns ((%s Real))\n", nvar->name); } fprintf(fp, ":formula\n"); fprintf(fp, "%s\n", smt_convert_fml_to_string(fml)); fprintf(fp, ")"); fclose(fp); free(filename); } void smt_print_aig_to_dot_file(Aig_Manager_t * bm) { FILE *fp; fp = fopen("aig.dot", "w"); Aig_PrintDot(fp, bm); fclose(fp); } void smt_print_lit_in_array(smtManager_t * sm, satArray_t * litArr) { satManager_t * cm = sm->cm; smtAvar_t * avar; int lit, id; int i; for(i = 0; i < litArr->size; i++) { lit = litArr->space[i]; id = (lit > 0) ? lit : -lit; avar = (smtAvar_t *) sm->id2var->space[id]; if (avar) { if (lit>0) fprintf(stdout, "%d:%s:flag:%d:level:%ld\n", avar->id, avar->name, avar->flag, cm->levels[id]); else if(lit<0) fprintf(stdout, "%d:!%s:flag:%d:level:%ld\n", avar->id, avar->name, avar->flag, cm->levels[id]); else fprintf(stdout, "ERROR: %d:?%s:flag:%d:level:%ld\n", avar->id, avar->name, avar->flag, cm->levels[id]); } } } void smt_print_lit_in_array_hor(smtManager_t * sm, satArray_t * litArr) { satManager_t * cm = sm->cm; smtAvar_t * avar; int lit, id; int i; for(i = 0; i < litArr->size; i++) { lit = litArr->space[i]; id = (lit > 0) ? lit : -lit; avar = (smtAvar_t *) sm->id2var->space[id]; if (avar) { if (lit>0) fprintf(stdout, "%d ", avar->id); else if(lit<0) fprintf(stdout, "%d ", avar->id); else fprintf(stdout, "ERROR: %d:?%s:flag:%d:level:%ld\n", avar->id, avar->name, avar->flag, cm->levels[id]); } } if (litArr->size) fprintf(stdout, "\n"); } void smt_print_sat_lit_in_array(smtManager_t * sm, satArray_t * litArr) { satManager_t * cm = sm->cm; smtAvar_t * avar; int lit, id; int i; for(i = 0; i < litArr->size; i++) { lit = litArr->space[i]; id = lit >> 1; avar = (smtAvar_t *) sm->id2var->space[id]; if (avar) { if (lit % 2 == 1) fprintf(stdout, "%d:%s:flag:%d:level:%ld\n", avar->id, avar->name, avar->flag, cm->levels[id]); else if(lit % 2 == 0) fprintf(stdout, "%d:!%s:flag:%d:level:%ld\n", avar->id, avar->name, avar->flag, cm->levels[id]); else fprintf(stdout, "ERROR: %d:?%s:flag:%d:level:%ld\n", avar->id, avar->name, avar->flag, cm->levels[id]); } } } void smt_print_idl_digraph_to_dot_file(smtGraph_t * G, char * filename) { FILE * fp; smtVertex_t * src, * dest; smtEdge_t * e; smtNvar_t * rnvar, * lnvar; int i; fp = fopen(filename, "w"); fprintf(fp, "digraph \"G\" {\n"); fprintf(fp, " rotate=90;\n"); fprintf(fp, " margin=0.5;\n"); fprintf(fp, " label=\"G\";\n"); fprintf(fp, " size=\"10, 7, 5\";\n"); for(i = 0; i < G->esize; i++) { e = &(G->eHead[i]); src = e->src; dest = e->dest; rnvar = (smtNvar_t *) G->nvarArr->space[src->index]; lnvar = (smtNvar_t *) G->nvarArr->space[dest->index]; if(G->paths[dest->index] == src) fprintf(fp, " \"%d.%s:%d\" -> \"%d.%s:%d\" [color = red, label=\"%g\"];\n", src->index, rnvar->name, G->idists[src->index], dest->index, lnvar->name, G->idists[dest->index], e->weight); else fprintf(fp, " \"%d.%s:%d\" -> \"%d.%s:%d\" [color = black, label=\"%g\"];\n", src->index, rnvar->name, G->idists[src->index], dest->index, lnvar->name, G->idists[dest->index], e->weight); } fprintf(fp, "}\n"); fclose(fp); } void smt_print_rdl_digraph_to_dot_file(smtGraph_t * G, char * filename) { FILE * fp; smtVertex_t * src, * dest; smtEdge_t * e; smtNvar_t * rnvar, * lnvar; int i; fp = fopen(filename, "w"); fprintf(fp, "digraph \"G\" {\n"); fprintf(fp, " rotate=90;\n"); fprintf(fp, " margin=0.5;\n"); fprintf(fp, " label=\"G\";\n"); fprintf(fp, " size=\"10, 7, 5\";\n"); for(i = 0; i < G->esize; i++) { e = &(G->eHead[i]); src = e->src; dest = e->dest; rnvar = (smtNvar_t *) G->nvarArr->space[src->index]; lnvar = (smtNvar_t *) G->nvarArr->space[dest->index]; if(G->paths[dest->index] == src) fprintf(fp, " \"%d.%s:%g\" -> \"%d.%s:%g\" [color = red, label=\"%g\"];\n", src->index, rnvar->name, G->rdists[src->index], dest->index, lnvar->name, G->rdists[dest->index], e->weight); else fprintf(fp, " \"%d.%s:%g\" -> \"%d.%s:%g\" [color = black, label=\"%g\"];\n", src->index, rnvar->name, G->rdists[src->index], dest->index, lnvar->name, G->rdists[dest->index], e->weight); } fprintf(fp, "}\n"); fclose(fp); } void smt_print_variable_to_smt_file(smtManager_t * sm, FILE * fp) { smtBvar_t * bvar; smtNvar_t * nvar; int i; for(i = 0; i < sm->bvarArr->size; i++) { bvar = (smtBvar_t *) sm->bvarArr->space[i]; if (! strcmp(bvar->name, "true") || ! strcmp(bvar->name, "false")) continue; fprintf(fp, ":extrapreds ((%s))\n", bvar->name); } for(i = 0; i < sm->nvarArr->size; i++) { nvar = (smtNvar_t *) sm->nvarArr->space[i]; if (sm->flag & RDL_MASK) fprintf(fp, ":extrafuns ((%s Real))\n", nvar->name); else if (sm->flag & IDL_MASK || sm->flag & LIA_MASK) fprintf(fp, ":extrafuns ((%s Int))\n", nvar->name); } } void smt_print_equation_in_tableau(smtManager_t * sm) { double * tab = sm->tab; smtNvar_t * nvar; double coeff; int col, num_col, index; int i, j; num_col = sm->tab_nvars->size; for(i = 0; i < sm->basics->size; i++) { fprintf(stdout, "row_%d:", i+1); for(j = 0; j < sm->tab_nvars->size; j++) { nvar = (smtNvar_t *) sm->tab_nvars->space[j]; col = nvar->id; index = i * num_col + col; coeff = tab[index]; if (coeff <= 0 && coeff >= 0) continue; if (nvar->flag & BASIC_MASK) fprintf(stdout, "(%g*%s)(%d) ", coeff, nvar->name, col); else fprintf(stdout, "%g*%s(%d) ", coeff, nvar->name, col); } fprintf(stdout, "\n"); } return; } void smt_report_result(smtManager_t * sm, int is_model) { satManager_t * cm = sm->cm; if (sm->flag & IDL_MASK || sm->flag & RDL_MASK) { smt_dl_report_result(sm); /* print solution */ if (cm->status == 1 && is_model) { if (sm->flag & MP_CONST_MASK) smt_mp_print_solution(sm); else smt_print_solution(sm); } } } void smt_dl_report_intermediate_result(smtManager_t * sm) { fprintf(stdout, "rate of bellman-ford conflict : %10g/%g\n", sm->stats->num_bf_conf, sm->stats->num_bf_call); fprintf(stdout, "rate of simple theory propagation : %10g/%g\n", sm->stats->num_simp_tprop, sm->stats->num_simp_tprop_call); fprintf(stdout, "rate of theory propagation : %10g/%g\n", sm->stats->num_tprop, sm->stats->num_tprop_call); fprintf(stdout, "\n"); return; } void smt_dl_report_result(smtManager_t * sm) { satManager_t * cm = sm->cm; if (cm) { if(cm->status == 0) fprintf(stdout, "unsat\n"); else if(cm->status == 1) fprintf(stdout, "sat\n"); else fprintf(stdout, "unknown\n"); } else { /*fprintf(stdout, "unknown\n");*/ if (sm->obj == Aig_One) fprintf(stdout, "sat\n"); else if (sm->obj == Aig_Zero) fprintf(stdout, "unsat\n"); } fprintf(stdout, "# of clauses : %10ld\n", sm->clsArr->size - (long) sm->stats->num_static_cls); fprintf(stdout, "# of bool vars : %10ld\n", sm->bvarArr->size + (long) sm->stats->num_inter_bvar); fprintf(stdout, "# of atoms : %10ld\n", sm->avarArr->size - (long) sm->stats->num_static_pred); fprintf(stdout, "rate of bellman-ford conflict : %10g/%g\n", sm->stats->num_bf_conf, sm->stats->num_bf_call); fprintf(stdout, "rate of simple theory propagation : %10g/%g\n", sm->stats->num_simp_tprop, sm->stats->num_simp_tprop_call); fprintf(stdout, "rate of theory propagation : %10g/%g\n", sm->stats->num_tprop, sm->stats->num_tprop_call); fprintf(stdout, "total solve time : %10g\n", sm->stats->solve_time); /*if (cm->status == 1) smt_print_solution(sm);*/ return; } void smt_check_result(smtManager_t * sm) { satManager_t * cm = sm->cm; int status = 2; if (gvar->status == 2) return; if (cm) { if (cm->status == 1) status = 1; else if (cm->status == 0) status = 0; else status = 2; } else if ( !(sm->flag & UNKNOWN_MASK) ) { if (sm->flag & SAT_MASK) status = 1; else status = 0; } #if 1 if (status != gvar->status) { fprintf(stdout,"ERROR: Wrong result\n"); } else { fprintf(stdout, "Right result\n"); } #endif } void smt_print_unknown(void) { fprintf(stdout, "unknown\n"); } char * smt_convert_atom_to_string(smtAvar_t * avar) { smtNvar_t * nvar; double coeff; char * str_a, * str_b, * str_c; int i; str_a = (char *) malloc(sizeof(char) * 100); if ( avar->nvars->size == 1) { coeff = array_fetch(double, avar->coeffs, 0); nvar = (smtNvar_t *) avar->nvars->space[0]; if ( coeff >= 0 ) { if ( avar->constant >= 0 ) sprintf(str_a, "(<= (* %d %s) %d)", (int) coeff, nvar->name, (int) avar->constant); else sprintf(str_a, "(<= (* %d %s) (~ %d))", (int) coeff, nvar->name, (int) -avar->constant); } else { if ( avar->constant >= 0 ) sprintf(str_a, "(<= (* (~ %d) %s) %d)", (int) -coeff, nvar->name, (int) avar->constant); else sprintf(str_a, "(<= (* (~ %d) %s) (~ %d))", (int) -coeff, nvar->name, (int) -avar->constant); } str_b = util_strsav(str_a); free(str_a); return str_b; } str_b = util_strsav("(<= (+ "); for(i = 0; i < avar->nvars->size; i++) { coeff = array_fetch(double, avar->coeffs, i); nvar = (smtNvar_t *) avar->nvars->space[i]; if ( coeff > 0 ) sprintf(str_a, "(* %d %s) ", (int) coeff, nvar->name); /* a, b, c */ else sprintf(str_a, "(* (~ %d) %s) ", (int) -coeff, nvar->name); /* a, b, c */ str_c = str_b; str_b = util_strcat3(str_b, str_a, ""); free(str_c); } if ( avar->constant >= 0 ) sprintf(str_a, "%d)", (int) avar->constant); else sprintf(str_a, "(~ %d))", (int) -avar->constant); str_c = util_strcat3(str_b, ") ", str_a); free(str_a); free(str_b); return str_c; } int smt_check_solution(smtManager_t * sm) { smtAvar_t * avar; smtNvar_t * lnvar, * rnvar; double weight; int id, i; for(i = 0; i < sm->avarArr->size; i++) { avar = (smtAvar_t *) sm->avarArr->space[i]; id = avar->id; assert(sm->avalues[id] != 2); /*if (sm->avalues[id] == 2) continue;*/ if (sm->avalues[id] == 1) { lnvar = (smtNvar_t *) avar->nvars->space[0]; rnvar = (smtNvar_t *) avar->nvars->space[1]; weight = avar->constant; } else { lnvar = (smtNvar_t *) avar->nvars->space[1]; rnvar = (smtNvar_t *) avar->nvars->space[0]; weight = -avar->constant - sm->epsilon; } if (sm->flag & IDL_MASK) { if (sm->ivalues[lnvar->id-1] - sm->ivalues[rnvar->id-1] > weight) { fprintf(stdout, "unknown\n"); exit(0); } } else if (sm->flag & RDL_MASK) { weight = weight + sm->epsilonless; if (sm->rvalues[lnvar->id-1] - sm->rvalues[rnvar->id-1] > weight) { fprintf(stdout, "unknown\n"); exit(0); } } } return 1; } int smt_mp_check_solution(smtManager_t * sm) { smtMp_t * mp = sm->mp; mpq_t * pool = mp->pool; mpq_t * tmp_a = 0, * weight = 0, * diff = 0; smtAvar_t * avar; smtNvar_t * lnvar, * rnvar; int id, i; /* mp vars */ tmp_a = &pool[2]; diff = &pool[3]; weight = &pool[4]; for(i = 0; i < sm->avarArr->size; i++) { avar = (smtAvar_t *) sm->avarArr->space[i]; id = avar->id; assert(sm->avalues[id] != 2); /*if (sm->avalues[id] == 2) continue;*/ if (sm->avalues[id] == 1) { lnvar = (smtNvar_t *) avar->nvars->space[0]; rnvar = (smtNvar_t *) avar->nvars->space[1]; mpq_set(*weight, sm->mp->weights[avar->id]); } else { lnvar = (smtNvar_t *) avar->nvars->space[1]; rnvar = (smtNvar_t *) avar->nvars->space[0]; weight = &sm->mp->weights[avar->id]; mpq_set(*weight, sm->mp->weights[avar->id]); mpq_neg(*weight, *weight); mpq_set_d(*tmp_a, sm->epsilon); mpq_sub(*weight, *weight, *tmp_a); } mpq_sub(*diff, sm->mp->values[lnvar->id-1], sm->mp->values[rnvar->id-1]); if ( mpq_cmp(*diff, *weight) > 0 ) { fprintf(stdout, "unknown\n"); exit(0); } } return 1; } void smt_print_solution(smtManager_t * sm) { satManager_t * cm = sm->cm; smtBvar_t * bvar; smtAvar_t * avar; smtNvar_t * nvar, * lnvar, * rnvar; double weight; long num_bvar; int i; num_bvar = sm->bvarArr->size - sm->stats->num_inter_bvar; for(i = 0; i < num_bvar; i++) { bvar = (smtBvar_t *) sm->bvarArr->space[i]; if (cm->values[SATVar(bvar->id)] == 1) fprintf(stdout, "%s = true\n", bvar->name); else if (cm->values[SATVar(bvar->id)] == 0) fprintf(stdout, "%s = false\n", bvar->name); else fprintf(stdout, "%s = unknown\n", bvar->name); } for(i = 0; i < sm->avarArr->size; i++) { avar = (smtAvar_t *) sm->avarArr->space[i]; if (cm->values[SATVar(avar->id)] == 1) fprintf(stdout, "%s = true\n", avar->name); else if (cm->values[SATVar(avar->id)] == 0) fprintf(stdout, "%s = false\n", avar->name); else { lnvar = (smtNvar_t *) avar->nvars->space[0]; rnvar = (smtNvar_t *) avar->nvars->space[1]; weight = avar->constant; if (sm->flag & IDL_MASK) { if (sm->ivalues[lnvar->id-1] - sm->ivalues[rnvar->id-1] <= weight) fprintf(stdout, "%s = true\n", avar->name); else fprintf(stdout, "%s = false\n", avar->name); } else if (sm->flag & RDL_MASK) { weight = weight + sm->epsilonless; if (sm->rvalues[lnvar->id-1] - sm->rvalues[rnvar->id-1] <= weight) fprintf(stdout, "%s = true\n", avar->name); else fprintf(stdout, "%s = false\n", avar->name); } } } for(i = 0; i < sm->nvarArr->size; i++) { nvar = (smtNvar_t *) sm->nvarArr->space[i]; if (sm->flag & IDL_MASK) fprintf(stdout, "%s = %d\n", nvar->name, sm->ivalues[nvar->id-1]); else if (sm->flag & RDL_MASK) fprintf(stdout, "%s = %g\n", nvar->name, sm->rvalues[nvar->id-1]); } } void smt_mp_print_solution(smtManager_t * sm) { satManager_t * cm = sm->cm; smtBvar_t * bvar; smtAvar_t * avar; smtNvar_t * nvar; long num_bvar; int i; num_bvar = sm->bvarArr->size - sm->stats->num_inter_bvar; for(i = 0; i < num_bvar; i++) { bvar = (smtBvar_t *) sm->bvarArr->space[i]; if (cm->values[SATVar(bvar->id)] == 1) fprintf(stdout, "%s = true\n", bvar->name); else if (cm->values[SATVar(bvar->id)] == 0) fprintf(stdout, "%s = false\n", bvar->name); else fprintf(stdout, "%s = unknown\n", bvar->name); } for(i = 0; i < sm->avarArr->size; i++) { avar = (smtAvar_t *) sm->avarArr->space[i]; if (cm->values[SATVar(avar->id)] == 1) fprintf(stdout, "%s = true\n", avar->name); else if (cm->values[SATVar(avar->id)] == 0) fprintf(stdout, "%s = false\n", avar->name); } for(i = 0; i < sm->nvarArr->size; i++) { nvar = (smtNvar_t *) sm->nvarArr->space[i]; gmp_printf("%s = %#Qd\n", nvar->name, sm->mp->values[nvar->id-1]); } } #endif