cvc5.git
3 years ago[AUTHORS] Add CVC4 as part of CVC series (#6907)
Haniel Barbosa [Tue, 20 Jul 2021 17:36:41 +0000 (14:36 -0300)]
[AUTHORS] Add CVC4 as part of CVC series (#6907)

3 years agoANTLR3: Install into `CMAKE_INSTALL_LIBDIR` (#6912)
Andres Noetzli [Tue, 20 Jul 2021 16:11:15 +0000 (09:11 -0700)]
ANTLR3: Install into `CMAKE_INSTALL_LIBDIR` (#6912)

On some platforms, autotools installs ANTLR3's libraries into lib but
CMAKE_INSTALL_LIBDIR is set to lib64 (e.g., Fedora 33). This commit
sets --libdir to force autotools to install the library into the
directory specified by CMAKE_INSTALL_LIBDIR.

3 years ago'CryptoMiniSat_LIBRARIES' should respect lib/lib64 (#6905)
Andrew V. Jones [Mon, 19 Jul 2021 07:06:53 +0000 (08:06 +0100)]
'CryptoMiniSat_LIBRARIES' should respect lib/lib64 (#6905)

On 64-bit openSUSE (and maybe other distributions), the default install directory for static libraries is `lib64` *not* `lib`. This has an impact on cvc5 when it is automatically building CMS (e.g., with `./configure.sh --cryptominisat --auto-download`): CMS adheres to the default value of `CMAKE_INSTALL_LIBDIR` to work out where to install the library files (so `lib64` on openSUSE), which fails when cvc5 tries to find these in `lib`.

Without this change, the build fails as follows:

```
<snip>
src/CMakeFiles/cvc5.dir/theory/type_enumerator.cpp.o  -Wl,-rpath,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::  deps/lib/libcadical.a  deps/lib/libcryptominisat5.a  ../deps/install/lib64/libglpk.a  deps/lib/libpicpolyxx.a  /usr/lib64/libgmp.so  deps/lib/libpicpoly.a  /usr/lib64/libgmp.so && :
/usr/lib64/gcc/x86_64-suse-linux/11/../../../../x86_64-suse-linux/bin/ld: cannot find deps/lib/libcryptominisat5.a: No such file or directory
collect2: error: ld returned 1 exit status
ninja: build stopped: subcommand failed.
```

and where:

```
avj@platypus ~/clones/cvc5/master/build$ find . -iname "libcryptominisat5.a"
./deps/src/CryptoMiniSat-EP-build/lib/libcryptominisat5.a
./deps/lib64/libcryptominisat5.a
```

(notice: `lib64` in the second path!)

This commit fixes this discrepancy to ensure that cvc5 checks for CMS on `CMAKE_INSTALL_LIBDIR` as well.

**Note**: `CMAKE_INSTALL_LIBDIR` comes from `GNUInstallDirs`, and this is `include`'d in cvc5's top-level `CMakeLists.txt`

Signed-off-by: Andrew V. Jones <andrewvaughanj@gmail.com>
3 years ago'ANTLR3_RUNTIME' should respect lib/lib64 (#6906)
Andrew V. Jones [Mon, 19 Jul 2021 06:55:35 +0000 (07:55 +0100)]
'ANTLR3_RUNTIME' should respect lib/lib64 (#6906)

On 64-bit openSUSE (and maybe other distributions), the default install directory for static libraries is `lib64` *not* `lib`. This has an impact on cvc5 when it is automatically building ANTLR3: ANTLR3 follows the system-wide default of `lib64`, which fails when cvc5 tries to find these in `lib`.

Without this change, the build fails as follows:

```
<snip>
src/parser/CMakeFiles/cvc5parser.dir/smt2/Smt2Parser.c.o  -Wl,-rpath,/home/avj/clones/cvc5/lib64_cms/build/src::::::::::::::::::::::::  src/libcvc5.so.1  deps/lib/libantlr3c.a && :
/usr/lib64/gcc/x86_64-suse-linux/11/../../../../x86_64-suse-linux/bin/ld: cannot find deps/lib/libantlr3c.a: No such file or directory
collect2: error: ld returned 1 exit status
ninja: build stopped: subcommand failed.
```

and where:

```
avj@platypus ~/clones/cvc5/lib64_cms/build$ find . -iname "libantlr3c.a"
./deps/src/ANTLR3-EP-runtime/.libs/libantlr3c.a
./deps/lib64/libantlr3c.a
```

(notice: `lib64` in the second path!)

This commit fixes this discrepancy to ensure that cvc5 checks for ANTLR3 on `CMAKE_INSTALL_LIBDIR`, which matches that `autotools` will use.

**Note**: `CMAKE_INSTALL_LIBDIR` comes from `GNUInstallDirs`, and this is `include`'d in cvc5's top-level `CMakeLists.txt`

Signed-off-by: Andrew V. Jones <andrewvaughanj@gmail.com>
3 years agoAdd n-ary term utilities (#6896)
Andrew Reynolds [Sun, 18 Jul 2021 19:29:13 +0000 (14:29 -0500)]
Add n-ary term utilities (#6896)

Initial work towards rewrite rule reconstruction

3 years agoDo not exhaustive instantiation when FMF is disabled (#6899)
Andrew Reynolds [Fri, 16 Jul 2021 17:04:39 +0000 (12:04 -0500)]
Do not exhaustive instantiation when FMF is disabled (#6899)

This makes FMF not handle quantified formulas when FMF options are disabled, apart from those marked internal.

This is required for combinations of sequences + quantified formulas.

3 years ago[Unit Tests] Avoid linking against external libs (#6898)
Andres Noetzli [Fri, 16 Jul 2021 16:28:30 +0000 (09:28 -0700)]
[Unit Tests] Avoid linking against external libs (#6898)

Fixes #6866. The `theory_airth_cad_white` unit test has been failing on
some platforms (e.g., macOS) due to statically linking libpoly in
libcvc5 and then separately linking it in the unit tests. This resulted
in issues with `static` variables. This commit fixes the issue by
avoiding linking libpoly in the unit tests and instead relying solely on
libcvc5.

Co-authored-by: Ouyancheng <1024842937@qq.com>
3 years ago[Unit Tests] Reenable `top_scope_context_obj` (#6892)
Andres Noetzli [Fri, 16 Jul 2021 03:11:24 +0000 (20:11 -0700)]
[Unit Tests] Reenable `top_scope_context_obj` (#6892)

Fixes #6047. The test was disabled because ASan found a use-after-free
due to an object allocated in the top scope being destroyed after the
scope (see #2607 for a detailed explanation). At first, the plan was to
add support for this use case. However, we have decided that we
currently don't need support for this feature and added a guard against
it (#6082). This commit reenables the test but changes it to destroy the
object allocated in the top level scope before the corresponding level
is popped. It additionally adds a test of the guard from #6082.

3 years agoFix context for proofs of instantiations (#6890)
Andrew Reynolds [Thu, 15 Jul 2021 18:45:12 +0000 (13:45 -0500)]
Fix context for proofs of instantiations (#6890)

Caught by a regression on proof-new, where an instantiation was the symmetric equality of an instantiation on a previous call to check-sat. Proofs of instantiation should be user-context dependent.

3 years agoDistinguish quantifiers preprocess as its own proof rule (#6897)
Andrew Reynolds [Thu, 15 Jul 2021 17:56:05 +0000 (12:56 -0500)]
Distinguish quantifiers preprocess as its own proof rule (#6897)

3 years agoConnect the equality solver to theory arith (#6894)
Andrew Reynolds [Thu, 15 Jul 2021 15:53:05 +0000 (10:53 -0500)]
Connect the equality solver to theory arith (#6894)

--arith-eq-solver is a new option to enable the equality solver in arithmetic, disabled by default.

This PR connects the equality solver to TheoryArith when this option is enabled.

This is in preparation for the central equality engine.

3 years agoArithmetic equality solver (#6876)
Andrew Reynolds [Thu, 15 Jul 2021 13:25:28 +0000 (08:25 -0500)]
Arithmetic equality solver (#6876)

This is work towards the central equality engine. This adds a module of arithmetic that uses the equality engine in the default way.

This class will be incorporated into theory_arith.cpp. It will be the replacement for CongruenceManager when we use the central equality engine architecture.

3 years agoMove master equality engine notification to own file (#6877)
Andrew Reynolds [Thu, 15 Jul 2021 05:20:11 +0000 (00:20 -0500)]
Move master equality engine notification to own file (#6877)

Preparation for central equality engine.

3 years agoAdd node converter utility (#6878)
Andrew Reynolds [Thu, 15 Jul 2021 04:25:36 +0000 (23:25 -0500)]
Add node converter utility (#6878)

Adds a utility for converting nodes. This is the first step towards the LFSC proof conversion.

3 years agobv: Disable bv-assert-input if proofs are enabled. (#6886)
Mathias Preiner [Thu, 15 Jul 2021 02:39:00 +0000 (19:39 -0700)]
bv: Disable bv-assert-input if proofs are enabled. (#6886)

3 years agobv: Rename BBSimple to NodeBitblaster. (#6891)
Mathias Preiner [Thu, 15 Jul 2021 02:19:12 +0000 (19:19 -0700)]
bv: Rename BBSimple to NodeBitblaster. (#6891)

3 years agobv: Rename lazy solver to layered solver. (#6889)
Mathias Preiner [Thu, 15 Jul 2021 01:54:33 +0000 (18:54 -0700)]
bv: Rename lazy solver to layered solver. (#6889)

3 years agobv: Rename simple solver to bitblast-internal. (#6888)
Mathias Preiner [Thu, 15 Jul 2021 01:27:33 +0000 (18:27 -0700)]
bv: Rename simple solver to bitblast-internal. (#6888)

3 years ago[proof] Fix open proof issues in SAT proof (#6887)
Haniel Barbosa [Wed, 14 Jul 2021 23:02:30 +0000 (20:02 -0300)]
[proof] Fix open proof issues in SAT proof (#6887)

Commit d1eee40cc (PR #6346), in a foolish attempt to prevent speculated issues, introduced an overwriting policy to addition of resolution chains during SAT solving at the SAT proof manager. First, this is nonsensical because the lazy proof chain is context-dependent and at the same level other ways of proving that clause are simply redundant and therefore should be ignored. Second, and catastrophically, this policy, for reasons beyond me, can lead to open SAT proofs when the same clause is rederived at the same level.

So this commit simply reverts the change and adds an optimization that when the clause would be rederived at the same level we do nothing and leave the method.

3 years agoAdd option that exercises the previously buggy behavior (#6884)
Haniel Barbosa [Wed, 14 Jul 2021 22:29:50 +0000 (19:29 -0300)]
Add option that exercises the previously buggy behavior (#6884)

3 years agoGeneralize congruence handling for HO in eq proofs (#6883)
Haniel Barbosa [Wed, 14 Jul 2021 21:35:21 +0000 (18:35 -0300)]
Generalize congruence handling for HO in eq proofs (#6883)

Previously we were not considering proofs for HO equalities (i.e., between operators) that were transitivity chains. This commit generalizes the elaboration procedure in eq_proof to do so.

3 years agoFix for context on input proof generator (#6873)
Andrew Reynolds [Wed, 14 Jul 2021 21:15:28 +0000 (16:15 -0500)]
Fix for context on input proof generator (#6873)

The preprocess proof generator uses a dummy CDProof to mark input assertions that do not need justification. This CDProof should be user-context dependent to avoid rare cases where an input assertion was the symmetric equality of another, it was previously context independent.

This also refactors the debugging traces in this class.

3 years agoMove synthesis verification check to own file (#6882)
Andrew Reynolds [Wed, 14 Jul 2021 20:42:40 +0000 (15:42 -0500)]
Move synthesis verification check to own file (#6882)

In preparation for more extensions to this aspect of the synthesis solver.

3 years agoRefactor setup of proof equality engine for central EE (#6831)
Andrew Reynolds [Wed, 14 Jul 2021 14:15:25 +0000 (09:15 -0500)]
Refactor setup of proof equality engine for central EE (#6831)

Users of an equality engine should each use the same proof equality engine that wraps it. This ensures that theory inference managers do so, by tracking the official proof equality engine for an equality engine in theory inference manager.

This is in preparation for (proper equality proofs for) central equality engine.

It also adds some debugging code that is highly useful for debugging issues related to when equalities are processed in theory inference manager.

3 years agoFix models for sequences of infinite element type (#6870)
Andrew Reynolds [Wed, 14 Jul 2021 13:43:25 +0000 (08:43 -0500)]
Fix models for sequences of infinite element type (#6870)

This fixes our model construction for sequences of infinite element type.

We were relying on getModelValue in our model construction which is incorrect since it assumes that the element type's theory can provide concrete values during model generation time. This makes the sequence model construction more robust by generalizing how model values are assigned: we use skeletons instead of concrete values when the element type is infinite.

This fixes some open model generation issues with Facebook benchmarks.

3 years agoClean up option usage in command executor (#6844)
Gereon Kremer [Wed, 14 Jul 2021 07:40:30 +0000 (09:40 +0200)]
Clean up option usage in command executor (#6844)

This PR makes the CommandExecutor class use the options object from its SmtEngine instead of the driver one. This makes sure that options that are set via (set-option ...) are in effect for the CommandExecutor. It still stores the driver options, though, as they are used for resets.
The PR also does some minor cleanups along the way (remove unused pOptions, make things const).
Fixes #2376.

3 years agoAdd missing space for check macro error messages. (#6875)
Mathias Preiner [Wed, 14 Jul 2021 06:57:13 +0000 (23:57 -0700)]
Add missing space for check macro error messages. (#6875)

3 years agobv: Add missing BV_EAGER_ATOM proof rule. (#6874)
Mathias Preiner [Wed, 14 Jul 2021 03:09:07 +0000 (20:09 -0700)]
bv: Add missing BV_EAGER_ATOM proof rule. (#6874)

Fixes an issue with --proof-eager-checking and --bitblast=eager.

3 years agobv: Simplify BV_BITBLAST_* proof rules. (#6871)
Mathias Preiner [Tue, 13 Jul 2021 19:02:37 +0000 (12:02 -0700)]
bv: Simplify BV_BITBLAST_* proof rules. (#6871)

Introduces BV_BITBLAST_STEP rule, which replaces BV_BITBLAST_X rules.

3 years ago[rewriter] Add rewrite to order IFF (equality for Booleans) (#6872)
Haniel Barbosa [Tue, 13 Jul 2021 18:38:23 +0000 (15:38 -0300)]
[rewriter] Add rewrite to order IFF (equality for Booleans) (#6872)

Not doing this rewrite for Booleans is probably an artifact of the old IFF kind being removed. This rewrite is important to simplify the generation of proofs for the SAT solver, as clarified in the new comment in the SAT proof manager.

3 years agobv: Do not rewrite below BV leafs in BBProof's TConvProofGenerator. (#6869)
Mathias Preiner [Tue, 13 Jul 2021 16:11:33 +0000 (09:11 -0700)]
bv: Do not rewrite below BV leafs in BBProof's TConvProofGenerator. (#6869)

Introduces a TermContext class that can be used to skip rewrites below theory leafs. Fixes issues related to bit-vector leafs begin incorrectly rewritten.

3 years agoAdd branch and bound lemma if linear arithmetic generates a non-integer assignment...
Andrew Reynolds [Tue, 13 Jul 2021 07:12:46 +0000 (02:12 -0500)]
Add branch and bound lemma if linear arithmetic generates a non-integer assignment (#6868)

This double checks that TheoryArithPrivate generates a model that does not assign real values to integer variables.

This is done outside of TheoryArithPrivate intentionally, so that it can be checked independently.

This code should very rarely be applied but would have caught the incorrect model which led to wrong results in the UFNIA division of smtcomp 2021.

3 years agobv: Expand bitblast proof steps in the proof post processor. (#6867)
Mathias Preiner [Tue, 13 Jul 2021 02:33:08 +0000 (19:33 -0700)]
bv: Expand bitblast proof steps in the proof post processor. (#6867)

This commit changes BV proof logging to record coarse-grained bit-blast steps during solving and expanding these steps on-demand in the proof post processor.

3 years agoAdd branch and bound (#6865)
Andrew Reynolds [Mon, 12 Jul 2021 20:59:25 +0000 (15:59 -0500)]
Add branch and bound (#6865)

This PR moves https://github.com/cvc5/cvc5/blob/master/src/theory/arith/theory_arith_private.cpp#L3451 to its own module.

The next PR will connect this module to theory_arith / theory_arith_private.

Towards ensuring type constraints are met for linear arithmetic models.

3 years agoFix for learned rewrite pass, add regression (#6850)
Andrew Reynolds [Mon, 12 Jul 2021 19:18:17 +0000 (14:18 -0500)]
Fix for learned rewrite pass, add regression (#6850)

Fixes #4791.

3 years agoFix ANTLR build on CMake <3.11 (#6864)
Andres Noetzli [Mon, 12 Jul 2021 19:05:14 +0000 (12:05 -0700)]
Fix ANTLR build on CMake <3.11 (#6864)

With CMake 3.11 and later, `<DOWNLOAD_DIR>` is substituted in
`ExternalProject_Add` but not in older versions [0]. To maintain
compatibility with older versions of CMake, this commit changes
`ExternalProject_Add` to use `<DOWNLOADED_FILE>` instead, which is both
nicer and substituted in older versions of CMake.

[0] https://cmake.org/cmake/help/latest/release/3.11.html#modules

3 years agoAdd arithmetic preprocess rewrite equality module (#6860)
Andrew Reynolds [Mon, 12 Jul 2021 18:55:13 +0000 (13:55 -0500)]
Add arithmetic preprocess rewrite equality module (#6860)

This is the first part of a refactoring which will ensure that the linear arithmetic solver does not violate integer type constraints in its model.

This PR moves the method https://github.com/ajreynol/CVC4/blob/master/src/theory/arith/theory_arith.cpp#L129 to its own module / file.

3 years agoAdd trace for combination splits (#6862)
Andrew Reynolds [Mon, 12 Jul 2021 18:15:48 +0000 (13:15 -0500)]
Add trace for combination splits (#6862)

Followup PRs will unify these with the lemmas / stats infrastructure in theory inference manager.

3 years agoUse default visibility for `cvc5::Exception` (#6856)
Andres Noetzli [Mon, 12 Jul 2021 17:31:58 +0000 (10:31 -0700)]
Use default visibility for `cvc5::Exception` (#6856)

Currently, `cvc5::Exception` does not have default visibility, which can
cause cvc5 to terminate when trying to catch it in `main.cpp`.
Presumably, this is because the necessary typeinfo is missing [0]. Due
to this issue, production builds for M1 on macOS crashed when parser
exceptions were thrown. The commit changes the visibility of the
exception.

[0] https://gcc.gnu.org/wiki/Visibility,
    "Problems with C++ exceptions (please read!)"

3 years agoImprovements to debug check model (#6861)
Andrew Reynolds [Mon, 12 Jul 2021 17:20:57 +0000 (12:20 -0500)]
Improvements to debug check model (#6861)

This makes it so that debug-check-models applies in production mode, not just in debug mode. It also verifies that type constraints are met.

3 years agotest also with default cores (#6858)
Haniel Barbosa [Fri, 9 Jul 2021 19:25:44 +0000 (16:25 -0300)]
test also with default cores (#6858)

Have unsat cores regression tested also with default mode.

3 years agoMake regression test `issue4971-0` more robust (#6857)
Andres Noetzli [Fri, 9 Jul 2021 19:15:51 +0000 (12:15 -0700)]
Make regression test `issue4971-0` more robust (#6857)

When compiling and running cvc5 on macOS with an M1 CPU, the regression
test regress0/cores/issue4971-0.smt2 returned unsat instead of the
expected unknown for the first (check-sat) command. This commit
makes the regression more robust by adding --cegqi-full and expecting
unsat.

3 years agoUse newer config.sub to fix build on Apple M1 (#6854)
Andres Noetzli [Fri, 9 Jul 2021 18:24:05 +0000 (11:24 -0700)]
Use newer config.sub to fix build on Apple M1 (#6854)

When building cvc5 on macOS for M1 natively, ANTLR's version of
`config.sub` does not recognize `aarch64-apple-darwin20.5.0`. This
commit fixes that issue by downloading the latest version of
`config.sub` (similar to what we are already doing for `config.guess`).
The commit also updates the URLs for `config.guess` and `config.sub` to
the URLs recommended in the files themselves. The commit also does some
minor cleanup/simplifications of the commands for building ANTLR.

3 years agoFix sets cardinality inference involving equivalent parents (#6855)
Andrew Reynolds [Fri, 9 Jul 2021 17:24:50 +0000 (12:24 -0500)]
Fix sets cardinality inference involving equivalent parents (#6855)

This fixes an unsoundness issue in the sets + cardinality solver.

One rule of this solver applies in sets when two parents of a child of a cardinality graph are equal, in which case we know that child or one of its siblings must be equal to the opposite parent. For example, this rule tells us that:

if T = (union T S), then (intersect T S) = S.

The explanation of this rule could consider the representative term of one the parents instead of the term itself say (union T S) is representative T, giving the unsound inference: if (union T S) = (union T S), then (intersect T S) = S. This ensures we use the original terms.

This PR also does some minor cleanup.

3 years agoImplement stop-only for new justification heuristic (#6847)
Andrew Reynolds [Fri, 9 Jul 2021 16:50:51 +0000 (11:50 -0500)]
Implement stop-only for new justification heuristic (#6847)

This also refactors decision engine so that we use inheritance instead of a dummy flag + members to determine which implementation to use.

3 years agoDisable ordering heuristic for justification by default (#6848)
Andrew Reynolds [Thu, 8 Jul 2021 21:16:25 +0000 (16:16 -0500)]
Disable ordering heuristic for justification by default (#6848)

3 years agoAdd script to build wheel for pycvc5 (#6839)
makaimann [Thu, 8 Jul 2021 16:24:54 +0000 (12:24 -0400)]
Add script to build wheel for pycvc5 (#6839)

This PR adds a script for building a wheel distribution for pycvc5. It automatically reads the top-level CMakeLists.txt to obtain the current version number, and then runs the standard setup from setuptools with an extension command class that configures and builds cvc5 with Python bindings. This wheel file is sufficient for uploading to Pypi. Although, note that we need to build for different operating systems and different Python versions because of the extension modules.

Note: another option is to use the scikit-build instead of doing the configuring and building manually. However, I ran into some issues when the setup.py file was not at the top-level. Because we prefer to have it hidden in a sub-folder, I took the manual route for now. In the future, we could consider changing this.

3 years ago[proof] [dot] Print let map (of terms in proof) as part of dot proof (#6853)
Haniel Barbosa [Thu, 8 Jul 2021 13:44:05 +0000 (10:44 -0300)]
[proof] [dot] Print let map (of terms in proof) as part of dot proof (#6853)

The let map is printed as JSON-like dictionary via a comment of the dot output.

3 years ago[unsat cores] Adding regressions from #4971 (#6852)
Haniel Barbosa [Wed, 7 Jul 2021 20:53:20 +0000 (17:53 -0300)]
[unsat cores] Adding regressions from #4971 (#6852)

Adds remaining regressions from issue #4791, which we can handle with the different new unsat-core modes. Note that issue4971-1.smt2 requires the sat-proof mode for unsat cores.

3 years agopow2: Update NEWS. (#6851)
Aina Niemetz [Wed, 7 Jul 2021 19:46:59 +0000 (12:46 -0700)]
pow2: Update NEWS. (#6851)

3 years agoRename operator pow2 to int.pow2. (#6849)
Aina Niemetz [Wed, 7 Jul 2021 18:36:15 +0000 (11:36 -0700)]
Rename operator pow2 to int.pow2. (#6849)

This name is the name of the symbol we parse. Internally, we still call
it POW2. This is a fix for the problem that `pow2` may clash (and
already does clash on SMT-LIB benchmarks) with user-defined symbols.

3 years agoFix regressions for competition build (#6846)
Andrew Reynolds [Wed, 7 Jul 2021 16:08:24 +0000 (11:08 -0500)]
Fix regressions for competition build (#6846)

Fixes one of the issues in the nightlies.

3 years agoStandard output for trigger selection (#6841)
Andrew Reynolds [Wed, 7 Jul 2021 15:44:01 +0000 (10:44 -0500)]
Standard output for trigger selection (#6841)

Fixes #6259.

3 years agoIntegrate Lazard into CAD module (#6812)
Gereon Kremer [Tue, 6 Jul 2021 23:01:13 +0000 (01:01 +0200)]
Integrate Lazard into CAD module (#6812)

This PR adds two new command line options that govern how the CAD module does projection and lifting, allowing to use the new Lazard evaluation. By default, we use McCallum with regular lifting which does not require CoCoA.
Additionally, this PR adds a bunch of unit tests for the CAD module.

3 years agoIntegrate learned rewrite preprocessing pass (#6840)
Andrew Reynolds [Tue, 6 Jul 2021 22:44:09 +0000 (17:44 -0500)]
Integrate learned rewrite preprocessing pass (#6840)

This adds the learned rewrite preprocessing pass, which rewrites the input formula based on (typically theory specific) reasoning about learned literals. The main motivation is for preprocessing ints division/modulus based on bounds.

3 years agoAdd implementation of learned rewrite pass (#6843)
Andrew Reynolds [Tue, 6 Jul 2021 20:00:38 +0000 (15:00 -0500)]
Add implementation of learned rewrite pass (#6843)

3 years agoAdd learned rewrite preprocessing pass (#6842)
Andrew Reynolds [Tue, 6 Jul 2021 17:23:45 +0000 (12:23 -0500)]
Add learned rewrite preprocessing pass (#6842)

Adds the basic skeleton of the pass.

3 years agoPorting C++ API examples to SMT-LIB examples (#6789)
Haniel Barbosa [Tue, 6 Jul 2021 16:29:25 +0000 (13:29 -0300)]
Porting C++ API examples to SMT-LIB examples (#6789)

SyGuS examples will come later.

3 years agoAdd some printing functions for OptimizationObjective and OptimizationResult (#6809)
Ouyancheng [Tue, 6 Jul 2021 03:22:14 +0000 (20:22 -0700)]
Add some printing functions for OptimizationObjective and OptimizationResult (#6809)

Implement the operator << with std::ostream for OptimizationObjective and OptimizationResult. Currently only supports SMTLib2 or Sygus as output languages.
Objective: (maximize [node] :signed) or (minimize [node]) or ...
Result: (sat [expr]) or (unsat) or (unknown([explanation]) [expr/null])

3 years agoAdd doc page about transcendentals (#6755)
Gereon Kremer [Tue, 6 Jul 2021 02:13:47 +0000 (04:13 +0200)]
Add doc page about transcendentals (#6755)

This PR adds a theory reference page for the transcendental extension.

3 years ago[Strings] Fix incorrect rewrite (#6837)
Andres Noetzli [Mon, 5 Jul 2021 13:29:09 +0000 (06:29 -0700)]
[Strings] Fix incorrect rewrite (#6837)

Fixes #6834. There were two cases in our extended rewriter for string
equalities that were modifying the node without returning and without
updating information computed from the original node. This mismatch led
to incorrect rewrites. This commit fixes the issue by adding a flag to
returnRewrite() that determines whether node that was an equality
before and after the rewrite should be rewritten again with the extended
rewriter. We generally do not do that (we'd run in danger of rewriting
equality nodes with the extended rewriter even though we shouldn't) but
for the rewrites that were previously continuing to rewrite the node, we
set this flag and return. This ensures that we do not have an issue with
information being out of date. The commit additionally fixes an issue
where we would apply the rewrite STR_EQ_UNIFY even though the node
hadn't changed.

3 years agoMake buffered inference manager more robust to backtracking (#6833)
Andrew Reynolds [Mon, 5 Jul 2021 13:03:33 +0000 (08:03 -0500)]
Make buffered inference manager more robust to backtracking (#6833)

This makes TheoryEngine notify all theories when a theory sends a conflict. This means that buffered inference managers always clear their buffers when any theory sends a conflict.

This is required for making theories robust to conflicts that may arise when using the central equality engine, where a different theory may raise a conflict during another theory's check.

3 years agoFix performance of string regression (#6832)
Andres Noetzli [Sat, 3 Jul 2021 19:11:57 +0000 (12:11 -0700)]
Fix performance of string regression (#6832)

Regression cmu-dis-0707-3.smt2 has been timing out when using an ASan
build after commit a4f38d6. Before that
commit --strings-exp implicitly enabled --fmf-bound. After the
commit, the solver was supposed to apply the same reasoning but only to
interal quantifiers and without enabling --fmf-bound. However, the
commit missed some options checks that now also have to check whether
--strings-exp is enabled. This commit updates those option checks.
With this fix, we get a slightly different value for bug590.smt2 after
replying unknown. This commit updates the regression to be more lenient
with the value returned.

3 years agoAdd output tags -o, --output. (#6826)
Mathias Preiner [Sat, 3 Jul 2021 17:44:30 +0000 (10:44 -0700)]
Add output tags -o, --output. (#6826)

Output tags are similar to debug/trace tags, but are always enabled
(except for muzzled builds) to provide useful information for users.

Available output tags can be queried via -o help/--output help and are
specified in the base options module via enum values.

Co-authored-by: Gereon Kremer <nafur42@gmail.com>
3 years agoFix bv assert input reset assertions (#6820)
Mathias Preiner [Fri, 2 Jul 2021 22:13:17 +0000 (15:13 -0700)]
Fix bv assert input reset assertions (#6820)

If reset-assertions was called it will now reset the SAT solver and the
CNF stream if clauses were permanently added to the SAT solver via
option --bv-assert-input.

3 years agoFix rewriter for negative constant seq.nth (#6827)
Andrew Reynolds [Fri, 2 Jul 2021 13:55:19 +0000 (08:55 -0500)]
Fix rewriter for negative constant seq.nth (#6827)

Fixes #6777.

3 years agoFix CaDiCaL auto-download on macOS (#6828)
Andres Noetzli [Fri, 2 Jul 2021 07:42:13 +0000 (00:42 -0700)]
Fix CaDiCaL auto-download on macOS (#6828)

* Fix CaDiCaL auto-download on macOS

If we are auto-downloading CaDiCaL, we are manually instantiating its makefile.
To do that, we use `CMAKE_CXX_COMPILER` for the compiler and assemble some
flags. However, we are missing the platform dependent flags. Specifically, we
need to set `-isysroot` on macOS to make sure that the header files are found
because they are not at /usr/include on newer versions of Apple's XCode [0].
Unfortunately, I could not find a CMake variable with the platform specific
flags. They are assembled here [1]. To solve this problem, the commit checks if
`CMAKE_OSX_SYSROOT` is set and adds a corresponding compiler flag if it is.

[0] https://developer.apple.com/documentation/xcode-release-notes/xcode-10-release-notes
[1] https://github.com/Kitware/CMake/blob/d60d6c269ae7ad15adbb82028e9ab50290db2a2b/Source/cmLocalGenerator.cxx#L1900-L1923

3 years agoRefactor lexer for SMT-LIB in sphinx (#6805)
Gereon Kremer [Fri, 2 Jul 2021 06:42:28 +0000 (08:42 +0200)]
Refactor lexer for SMT-LIB in sphinx (#6805)

This PR refactors the lexer used by sphinx for highlighting SMT-LIB files. This new lexer properly checks for word boundaries and uses the proper character sets from the SMT-LIB standard.

3 years agoAdd reverse iterators to `Node`/`TNode` (#6825)
Andres Noetzli [Fri, 2 Jul 2021 04:44:47 +0000 (21:44 -0700)]
Add reverse iterators to `Node`/`TNode` (#6825)

This feature is useful for example for succinctly inserting children of
a node in the reverse order. To make this work, the commit fixes the
declaration of `reference` in the `NodeValue::iterator`. The
`std::reverse_iterator` adapter expects the `reference` type to match
the return type of `operator*` in the corresponding iterator (as
mandated by the standard). Despite its name, `reference` does not have
to be a C++ reference. Note that we cannot actually make it a C++
reference because `NodeValue::iterator` wraps the `NodeValue*` in a
`Node`/`TNode` in `operator*`.

3 years agoAdd recursive function definitions to subsolver in sygus (#6824)
Andrew Reynolds [Thu, 1 Jul 2021 22:35:13 +0000 (17:35 -0500)]
Add recursive function definitions to subsolver in sygus (#6824)

This passes recursive function definitions to the verification subsolver in sygus, with a default bounded limit of 3. This required improving the interface for setting up subsolvers by allowing custom options; the sygus solver statically computes an instance of the options that it uses in all calls.

This allows us to solve non-PBE sygus problems with recursive function definitions. The PR adds an example.

3 years agoFix message to show that cadical and symfpu are required (#6823)
Gereon Kremer [Thu, 1 Jul 2021 17:34:56 +0000 (19:34 +0200)]
Fix message to show that cadical and symfpu are required (#6823)

As mentioned in #6822, we are currently printing an incorrect message if CaDiCaL or SymFPU are not found but auto-download is disabled. This PR fixes this issue.

3 years agoAdd option to limit the number of instantiation rounds (#6818)
Andrew Reynolds [Thu, 1 Jul 2021 15:07:39 +0000 (10:07 -0500)]
Add option to limit the number of instantiation rounds (#6818)

This adds an option to limit the number of instantiation rounds used by quantifiers engine.

This option may be generally useful for making quantifiers terminating. It also is necessary to update the new default behavior of SyGuS + recursive functions. A followup PR will make sygus verification calls set the option added on this PR automatically, so that we use incomplete + termination strategies for (non-PBE) sygus in the presence of recursive functions.

This PR also makes minor improvements to the quantifier utility infrastructure.

3 years agoUse SAT context level for --bv-assert-input instead of decision level. (#6758)
Mathias Preiner [Wed, 30 Jun 2021 22:07:47 +0000 (15:07 -0700)]
Use SAT context level for --bv-assert-input instead of decision level. (#6758)

The decision level as previously implemented was not accurate since it
did not consider the user context level. This resulted in facts being
incorrectly recognized as input assertions, which happened for
incremental benchmarks.

3 years agoUse authored date instead of commit date. (#6815)
Gereon Kremer [Wed, 30 Jun 2021 21:34:31 +0000 (23:34 +0200)]
Use authored date instead of commit date. (#6815)

This commit fixes a subtle issue with pruning the old docs from docs-ci. We remove docs that are older than one week. However, we used the commit date instead of the authored date. Since we actually squash the old commits (that are older than four weeks) regularly, the commit date is always newer.

3 years agopow2: new test (#6819)
yoni206 [Wed, 30 Jun 2021 20:22:17 +0000 (13:22 -0700)]
pow2: new test (#6819)

This PR adds a more "real life" unit test for the pow2 solver. Thanks @4tXJ7f for the help with the options.

3 years agoDo not notify during equality engine initialization (#6817)
Andrew Reynolds [Wed, 30 Jun 2021 18:09:45 +0000 (13:09 -0500)]
Do not notify during equality engine initialization (#6817)

This is an alternative fix to https://github.com/cvc5/cvc5/pull/6808.

This ensures that we do not notify the provided class of an equality engine during initialization.

3 years agoDo not apply fmfBound to standard quantifiers when only stringsExp is enabled (#6816)
Andrew Reynolds [Wed, 30 Jun 2021 16:50:33 +0000 (11:50 -0500)]
Do not apply fmfBound to standard quantifiers when only stringsExp is enabled (#6816)

There are compelling use cases that combine strings/sequences and quantifiers. Prior to this PR, strings enabled "bounded integer" quantifier instantiation so that internally generated quantifiers for strings reductions are handled in a complete manner. However, this enabled bounded integer quantifier instantiation globally. This degrades performance for "unsat" on quantified formulas in general.

After this PR, we do not enable bounded integer quantifier globally. Instead, we ensure that bounded integer quantification is applied to at least the internally generated quantified formulas; all other quantified formulas are handled as usual.

Notice this required ensuring that all quantified formulas generated by strings are marked properly. It also required adding --fmf-bound to a few regressions that explicitly require it.

3 years agoFix pre vs. post-rewrite in proofs for theory preprocessor (#6801)
Andrew Reynolds [Wed, 30 Jun 2021 12:52:35 +0000 (07:52 -0500)]
Fix pre vs. post-rewrite in proofs for theory preprocessor (#6801)

This changes an annotation of a step of rewriting from "post" to "pre" in the theory preprocessor.
Fixes #6754.

3 years agoint-to-bv: correct model values (#6811)
yoni206 [Wed, 30 Jun 2021 12:11:56 +0000 (05:11 -0700)]
int-to-bv: correct model values (#6811)

the int-to-bv preprocessing pass produced wrong models.
This PR fixes this in a similar fashion to other preprocessing passes, by adding a substitution to the preprocessing pass context. This requires moving the main translation function to be a class method, rather than a helper method in an empty namespace.

Thanks to @alex-ozdemir for raising this issue and producing a triggering benchmark (added to regressions in this PR).

3 years agoAdd new variants for the CAD projection (#6794)
Gereon Kremer [Tue, 29 Jun 2021 17:43:39 +0000 (19:43 +0200)]
Add new variants for the CAD projection (#6794)

This PR adds variants for the CAD projection operator to use Lazard's projection operator.

3 years agoFix statistics in AigBitblaster. (#6810)
Mathias Preiner [Tue, 29 Jun 2021 17:34:42 +0000 (10:34 -0700)]
Fix statistics in AigBitblaster. (#6810)

Fixes #6788

3 years agoFP: Refactor, rewrite and clean up word blasting. (#6802)
Aina Niemetz [Tue, 29 Jun 2021 16:18:55 +0000 (09:18 -0700)]
FP: Refactor, rewrite and clean up word blasting. (#6802)

This rewrites the word blasting function FpConverter::convert to be
easier to follow and read. It further cleans up several things.

This additionally prepares for allowing to convert incoming facts rather
than terms registered with theory FP. That is, when word blasting more
lazily, in preNotifyFact rather than in registerTerm.

3 years agoRewrite POW to POW2 when the base is 2 (#6806)
yoni206 [Mon, 28 Jun 2021 23:42:13 +0000 (16:42 -0700)]
Rewrite POW to POW2 when the base is 2 (#6806)

This PR introduces a rewrite from (^ 2 t) to (pow2 t) in order to make use of the specialized pow2 solver.
One regression that expects an error when t is not a constant is changed accordingly.

3 years agoRename internal string kinds to match API (#6797)
Andrew Reynolds [Mon, 28 Jun 2021 20:45:51 +0000 (15:45 -0500)]
Rename internal string kinds to match API (#6797)

This commit replaces (old) internal string kind names to match the API / smt2 standard names.

3 years agoFurther fix #6453 (#6804)
Ouyancheng [Mon, 28 Jun 2021 19:10:55 +0000 (12:10 -0700)]
Further fix #6453 (#6804)

There's one spot left in issue #6453, that is the call to `std::allocator<T>::destroy` in `mkMetaKind`. And this commit fixes it.

3 years ago[proof] [dot] Make dot printer stateful (#6799)
Haniel Barbosa [Mon, 28 Jun 2021 13:39:49 +0000 (10:39 -0300)]
[proof] [dot] Make dot printer stateful (#6799)

In preparation for further changes in the printer.

3 years agopow2 -- final changes (#6800)
yoni206 [Sat, 26 Jun 2021 02:42:43 +0000 (19:42 -0700)]
pow2 -- final changes (#6800)

This commit adds the remaining changes for a working and integrated `pow2` solver.

In particular, it adds a rewrite and a lemma that identify `pow2(x)` with `0` whenever `x<0`.
Regressions are added as well, including `pow2-native-0.smt2` that shows the semantics of `pow2` on negative values.

The next steps are new rewrites and and more lemma schemas.

3 years agopow2: Adding monotonicity lemma (#6793)
yoni206 [Fri, 25 Jun 2021 03:09:06 +0000 (20:09 -0700)]
pow2: Adding monotonicity lemma  (#6793)

We add the lemma x<=y --> pow2(x)<=pow2(y) to the pow2 solver.
Additionally, some renaming of variables is introduced for better clarity.

3 years agoapi: getRealValue: Fix printing of integer values. (#6795)
Aina Niemetz [Thu, 24 Jun 2021 21:19:11 +0000 (14:19 -0700)]
api: getRealValue: Fix printing of integer values. (#6795)

3 years agocmake: Add new code coverage targets. (#6796)
Mathias Preiner [Thu, 24 Jun 2021 21:04:13 +0000 (14:04 -0700)]
cmake: Add new code coverage targets. (#6796)

This commit adds the following new code coverage targets:

- coverage-reset: Resets the code coverage counters

- coverage: Generates code coverage report for all cvc5 executions since the
            last coverage-reset

- coverage-test: This was previously the coverage target that runs the
                 tests and generates the coverage report (as used for
                 nightlies).

By using `make coverage-reset` and `make coverage` it is now possible to
generate coverage reports for arbitrary executions of cvc5.

3 years agoFix linear arithmetic for duplicate lemmas in incremental (#6784)
Andrew Reynolds [Thu, 24 Jun 2021 11:37:20 +0000 (06:37 -0500)]
Fix linear arithmetic for duplicate lemmas in incremental (#6784)

The linear arithmetic solver was not robust to cases where a duplicate lemma is emitted. This leads to non-linear arithmetic not being called to check at full effort, leading to potential model soundness issues.

Fixes #6773.

3 years agoAdd CoCoA implementation (#6733)
Gereon Kremer [Thu, 24 Jun 2021 11:27:30 +0000 (13:27 +0200)]
Add CoCoA implementation (#6733)

This PR adds the actual implementation for the Lazard evaluation based on CoCoALib. It is only used if CoCoALib is available and falls back to a default libpoly-based implementation otherwise.

3 years ago[hol] Disable bound fmf when HOL (#6792)
Haniel Barbosa [Wed, 23 Jun 2021 23:23:30 +0000 (20:23 -0300)]
[hol] Disable bound fmf when HOL (#6792)

Fixes #6536

3 years agopow2: more implementations (#6756)
yoni206 [Wed, 23 Jun 2021 22:16:58 +0000 (15:16 -0700)]
pow2: more implementations (#6756)

This PR adds implementations of functions from the pow2 solver, rewriter and type checker.

3 years ago[regressions] Adding regression from #5371 (#6791)
Haniel Barbosa [Wed, 23 Jun 2021 22:07:56 +0000 (19:07 -0300)]
[regressions] Adding regression from #5371 (#6791)

3 years ago[proofs] [dot] Adding a counter for subproofs (#6735)
Haniel Barbosa [Wed, 23 Jun 2021 20:36:23 +0000 (17:36 -0300)]
[proofs] [dot] Adding a counter for subproofs (#6735)

3 years ago[parser] [hol] Fix parser check for allowing functions when HOL is enabled (#6790)
Haniel Barbosa [Wed, 23 Jun 2021 20:01:13 +0000 (17:01 -0300)]
[parser] [hol] Fix parser check for allowing functions when HOL is enabled (#6790)

Fixes #6526

3 years agodocs: Add quickstart guide. (#6782)
Aina Niemetz [Wed, 23 Jun 2021 19:08:21 +0000 (12:08 -0700)]
docs: Add quickstart guide. (#6782)

3 years agoFP: Remove sections guarded with undefined macro SYMFPUPROPISBOOL. (#6786)
Aina Niemetz [Wed, 23 Jun 2021 18:19:13 +0000 (11:19 -0700)]
FP: Remove sections guarded with undefined macro SYMFPUPROPISBOOL. (#6786)

3 years agoRemove `--tear-down-incremental` (#6745)
Andres Noetzli [Wed, 23 Jun 2021 01:12:15 +0000 (18:12 -0700)]
Remove `--tear-down-incremental` (#6745)

Recent experiments have shown that `--tear-down-incremental` is actually
not really helping anymore and it has always been a bit of a workaround.
It is also broken on current master. This commit removes the option.