Allow changing certain options while solving (#6945)

This PR allows changing some select options ever after the smt engine has been fully initialized, following the SMT-LIB standard (section 4.1.7).

Simplify smt2 printer (#6954)

The common case of printing function applications is to print the kind in smt2 format, this makes this the default case and removes spurious cases. It also makes a few minor fixes.

Integrate installation instructions into documentation (#6814)

This PR migrates the current INSTALL.md to an rst file and then includes it in the documentation. It also does some minor improvements to this file, in particular it now mentions --dep-path

quickstart: Add python example to docs. (#6949)

[proofs] Set BV solver to better proof-producing one when proofs on (#6903)

Since the internal bitblaster can be way slower, the regressions that would have slow runs when --check-proofs is passed now have the command line that forces the use of the default bitblaster.

Python quick start example (#6939)

This is a translation of quickstart.cpp to python.

Integrate central equality engine approach into theory engine, add option and regressions (#6943)

This commit makes TheoryEngine take into account whether theories are using the central equality engine.

With this commit, the central equality engine can now be optionally enabled via `--ee-mode=central`.

Minor updates to shared terms database for central equality engine (#6929)

Includes proper set up of the proof equality engine it uses (which may be shared over multiple theories). Also makes its assertEquality method robust to non-equality atoms.

Fixes for building python wheels on manylinux2014 (#6947)

This PR makes several fixes to the wheel building infrastructure for manylinux2014.

don't statically link to Python (see: this section of PEP-513)
use standard 'build' directory. I noticed that the wheel infrastructure uses directory 'build' to prepare the wheel anyway, so it doesn't make a lot of sense for us to use a separate working directory. I tried changing the name of the build directory in setuptools by setting member variables in initialize_options but that didn't seem to work and I decided it wasn't worth the effort. The wheel should be built in a clean environment anyway, i.e., docker.
find the correct include directory and python library paths for building on manylinux2014 using skbuild. manylinux2014 has several versions of python installed in /opt/python. The CMake infrastructure can't find the necessary information (plus the libraries are deleted from the docker image to save space -- the library is just set to a generic libpython<version>.a). Instead, this PR would manually set them via CMake options.
to allow setting the python information, I extended the configure.sh script to allow directly setting CMake options. There are definitely other options here if you'd rather not change configure.sh. My reasoning was that it could be useful in other situations and I just marked it as an advanced feature. Another approach would be to use skbuild directly in the CMake infrastructure. I didn't like that solution because it would make the CMakeLists.txt more complicated and it wouldn't follow the standard CMake/Cython/Python approach which means we won't benefit from future improvements to that CMake infrastructure. Plus, this issue should only come up on systems with non-standard installations of Python, such as manylinux. This approach (setting CMake options) is basically what scikit-build does automatically if we had used that infrastructure directly.

Minor changes to arrays in preparation for central equality engine (#6917)

Makes arrays more robust to the order in which terms can be added to the equality engine vs. when they are preregistered.

We should probably performance test this.

FYI @barrettcw

Only use libedit on tty inputs (#6946)

This PR improves the check when we use libedit: only when the input is an interactive terminal.
This is motivated by a change to the unit test for the interactive mode that now properly redirects standard input (and output).

Print link to docs preview (#6922)

This commit adds a message to the `docs` target with a link to a preview
of the documentation, e.g.:

```
Preview docs in browser: file://localhost/home/noetzli/repos/cvc5_win/build-docs/docs/sphinx/index.html
```

Make extended rewriter methods const (#6948)

bv: Refactor getEqualityStatus and use for both bitblasting solvers. (#6933)

This commit refactors the getEqualityStatus handling for bitblast and bitblast-internal.

proof: Add eqrange expansion rule. (#6936)

Adds proof support for the eqrange operator.

Co-authored-by: Andrew Reynolds <andrew.j.reynolds@gmail.com>

Track instantiation reasons in proofs (#6935)

This adds optional arguments to INSTANTIATE steps in proofs to track fine-grained reasons for relevant instantiations.

Also simplifies an old argument modEq which was unused.

FYI @MikolasJanota

Add basic LFSC utilities (#6879)

Adds basic utilities in preparation for the LFSC proof conversion.

Depends on #6881, review that first.

Move enum value generator to own file (#6941)

Work towards integrating the enumerator callback into the fast enumerator.

Minor fix for term database + central equality engine (#6928)

Previously we provided a bogus (self) explanation in a rare case of setting up the term database for higher order. This is incompatible with cases where central equality engine = master equality engine.

Revert change to regression (#6940)

Although it works on most machines, it times out in the nightly builds.

Make all dependencies in the fast enumerator optional (#6918)

This allows one to use a fast enumerator without having access to sygus term database, statistics, etc.

Add print expression utility (#6880)

This will be used in the LFSC printer. It may be of general use to other proof printers.

Add regression for fixed `str.indexof_re` issue (#6938)

Fixes #6639. The issue cannot be reproduced on current master and git bisect suggests that commit adf497a
fixed the issue.

Minor changes from proof-new (#6937)

Note the change to the unit test makes it so the test is not dependent on Node ID order.

Miscellaneous fixes from proof-new (#6914)

Add proof letify utility (#6881)

Towards support for external proof conversions.

Fix eq proof conversion for constant merged parameterized ops (#6926)

This issue arises when using the central equality engine on several regressions.

Default equality proofs for bags and separation logic (#6932)

This is the last 2 remaining theories not to use the default handling of equality proofs.

In preparation for proofs in central equality engine.

Add sygus enumerator callback (#6923)

This class will make the uses of the fast enumerator customizable.

Move public options functions to separate file (#6671)

This PR moves the remaining special purpose functions out of the Options class. This set of functions is only used to implement API functions in the smt engine (getting and setting options by string), and by the main driver for parsing and printing usage information.

Enable default equality proofs for sets (#6931)

This enables default support for equality proofs in the theory of sets.

This is in preparation for proofs in the central equality engine, which requires that all active theories that use the central equality engine at least support the default interaction with the equality engine.

More updates to arithmetic in preparation for central equality engine (#6927)

Makes arithEqSolver more robust to propagations from multiple sources, changes the default relationship to congruence manager based on preliminary results on SMT-LIB.

Changes to datatypes in preparation for central equality engine (#6901)

This adds changes from the centralEeDev branch for datatypes.

The changes in behavior are that the inference manager clears its pending inferences when the state is in conflict, and preCheck processes pending facts immediately (which may have been enqueued prior to the call to check via ee merges). These are required to make datatypes robust to the order in which check / merge / backtracks can occur.

Refactor equality engine setup for arithmetic congruence manager (#6902)

Allows congruence manager to use its own (non-official) equality engine if both it and the arithmetic equality solver are enabled.

Fix CLN build (#6920)

Currently, the CLN `CONFIGURE_COMMAND` chains multiple commands using
`&&` but this does not seem to work with CMake 3.20.4 and CMake 3.19.7
and is also not the recommended way of doing it. The commit fixes the
issue by using additional `COMMAND`s and also switches to using the
CMake's `chdir` instead of `cd`.

Configuration: Indicate dependencies being built (#6921)

This commit changes the output of our configuration to show which
dependencies are being built as part of the cvc5 build. For example:

```
ABC                       : off
CryptoMiniSat             : off
GLPK                      : off
Kissat                    : off
LibPoly                   : on (local)
CoCoALib                  : off

Build libcvc5 only        : off
MP library                : gmp (system)
Editline                  : off
```

Indicates that `LibPoly` was not found in the system and is thus built
as part of the cvc5 build and GMP was found in the system.

Fix CoCoA build for newer compilers (#6919)

Newer compilers, such as GCC 11, default to C++17. CoCoA does not
compile with C++17 and its check for the C++ version used by the
compiler does not take into account newer C++ versions. As a result,
building CoCoA using `--auto-download` fails with GCC 11. This commit
adds a patch that makes the test in CoCoA take into account compilers
that default to C++17 or newer.

FP: Add option to word-blast more lazily. (#6904)

When enabled, this does not word-blast when registering term but at preNotifyFact (= more lazily) instead.
This is enabled via option --fp-lazy-wb.

Simplify computation of relevant terms in datatypes (#6885)

This makes it so that we do not consider non-singleton equivalence classes of DT for non-datatype terms to be relevant. This impacts how model construction is done for datatypes.

It's not clear why this method considered such terms to be relevant, I believe this was done to mask a previous bug; regressions now pass when this method is simplified.

Doing this is definitely wrong when using central equality engine, hence the motivation for this simplification.

Add the central equality engine manager (#6893)

This class is responsible for setting up the central equality engine. It relies on a new static method Theory::usesCentralEqualityEngine, which will be refined in followup PRs.

This PR does not change the behavior, it only adds the class.

Further PRs will connect this class to CombinationEngine, make it optionally enabled, and make the remaining changes to TheoryEngine to make it compatible.

Miscellaneous changes in preparation for central equality engine (#6900)

Add support for minimal unsat cores (#4605)

This commit adds support for computing minimal unsat cores. The
algorithm implemented in this commit is just a trivial deletion-based
algorithm that tries to remove each assertion in the unsat core
individually.

Preparation for carry the rewrite rule database in the proof checker (#6915)

Add std::vector<Term> Op:: getIndices() and operator[] for Op (#6397)

[AUTHORS] Add CVC4 as part of CVC series (#6907)

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.

'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>

'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>

Add n-ary term utilities (#6896)

Initial work towards rewrite rule reconstruction

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.

[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>

[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.

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.

Distinguish quantifiers preprocess as its own proof rule (#6897)

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.

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.

Move master equality engine notification to own file (#6877)

Preparation for central equality engine.

Add node converter utility (#6878)

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

bv: Disable bv-assert-input if proofs are enabled. (#6886)

bv: Rename BBSimple to NodeBitblaster. (#6891)

bv: Rename lazy solver to layered solver. (#6889)

bv: Rename simple solver to bitblast-internal. (#6888)

[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.

Add option that exercises the previously buggy behavior (#6884)

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.

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.

Move synthesis verification check to own file (#6882)

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

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.

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.

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.

Add missing space for check macro error messages. (#6875)

bv: Add missing BV_EAGER_ATOM proof rule. (#6874)

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

bv: Simplify BV_BITBLAST_* proof rules. (#6871)

Introduces BV_BITBLAST_STEP rule, which replaces BV_BITBLAST_X rules.

[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.

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.

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.

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.

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.

Fix for learned rewrite pass, add regression (#6850)

Fixes #4791.

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

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.

Add trace for combination splits (#6862)

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

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!)"

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.

test also with default cores (#6858)

Have unsat cores regression tested also with default mode.

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.

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.

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.

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.

Disable ordering heuristic for justification by default (#6848)

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.

[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.

[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.

pow2: Update NEWS. (#6851)

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.

Fix regressions for competition build (#6846)

Fixes one of the issues in the nightlies.

Standard output for trigger selection (#6841)

Fixes #6259.

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.

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.

Add implementation of learned rewrite pass (#6843)