Solver for quantifier-free integer difference logic, named QF_IDL
in the
SMT-LIB Specification. It was built to profile different strategies for
theory solving.
It uses an off-the-shelf SAT solver as a black box, meaning it doesn't implement
all of DPLL(T). Furthermore, while the parser handles let
bindings correctly,
it only parses the "official" syntax for QF_IDL
. That means this program
doesn't accept atoms of the following forms:
(op x (+ y n))
(op x (- y n))
(op x (+ y (- n)))
(op x (- y (- n)))
This program accepts one SMT-LIB file as input. The input is expected to be
QF_IDL
. If it isn't, the program will either fail to parse it or throw an
error.
In addition to the input file, this program accepts a few command-line flags:
stats
: prints statistics at the end of a run instead ofsat
/unsat
.csv
: prints statistics in CSV format instead of the default human-readable format. This flag has no effect ifstats
is not specified.soft-timeout
andhard-timeout
: accept a duration as an argument, and give up solving after that duration. If the program gives up, the returned status isunknown
. Otherwise, the status is eithersat
orunsat
. Also, the timeout doesn't count the time taken to ingest and preprocess the file.soft-timeout
: waits for the current iteration of the solver to complete before terminating.hard-timeout
: kills the process after the duration elapses, possibly leaving the statistics in an inconsistent state.
Command-line flags can also be used to specify the preprocessing and theory
solving strategies. The available preprocessing strategies, specified with the
preprocessor
flag, are:
nil
: no preprocessingt-lin
: apply the T rule to consecutive inequalities, thereby adding a linear number of clauses.t-quad
: apply the T rule to all possible inequalities, thereby adding a quadratic number of clauses.tie-lin
: apply the T, I, and E rules with linear blowup.tie-quad
: apply the T, I, and E rules with quadratic blowup.
The available theory solving strategies, specified with solver
, are:
bf-basic
: Bellman-Fordbf-full
: Bellman-Ford with the early-stopping optimizationspfa-basic
: Shortest Path Faster Algorithmspfa-full
: Shortest Path Faster Algorithm with amortized parent-graph searchtarjan
: Tarjan's Algorithm
The program can be built with the standard go build
command. The only extra
consideration is if the lexer - in internal/file/lexing.go
- is modified. When
it is, it has to be regenerated with the following commands:
$ go generate ./...
$ go fmt ./...
The generate script requires both bash
and participle
be on the PATH
.
To install the latter, clone it from its GitHub, then run:
$ pushd cmd/participle/
$ go install github.com/alecthomas/participle/v2/cmd/participle
$ popd
Unit tests can be run with:
$ go test -short ./...
Long tests try parsing all the benchmarks in the bench/
directory to check
that ingestion works. Follow the instruction in the bench/
folder to set it
up, then run:
$ go test ./...
When running the long tests, you'll probably need to set GOMAXPROCS
so as to
not run out of RAM.
Theory solvers are tested via fuzzing. The fuzz targets are in
internal/theory_test/theory_test.go
, and the functions available are:
FuzzBFBasic
FuzzBFFull
FuzzSPFABasic
FuzzSPFAFull
FuzzTarjan
To start fuzzing, pick a target and run:
$ go test -fuzz ${TARGET} ./internal/theory_test/