Use purification for set comprehension reduction (#8711)

Currently, the reduction lemma does not purify set comprehension from its reduction predicate. This means that our rewriter (if it were smart enough) should rewrite the reduction predicate to true.

Moreover, a new forthcoming model-based instantiation technique was giving wrong answers when set comprehensions were present since it could prove the reductions were tautological.

Improve finding Python library/includes (#8718)

On macOS, find_package(PythonLibs ...) does not find the Python
include directory or library when they were installed via homebrew.
find_package(Python ...) is more robust, but only available on newer
versions of CMake. If we are compiling cvc5 on macOS and we have a newer
version of CMake available, this tries to use find_package(Python ...)
to find the paths.

fix link to `Testing cvc5` in `INSTALL.md` (#8675)

The current link renders strangely and does not lead to the relevant subsection. This PR fixes that.

Make equality solver the entry point for all equality engine explanations in arithmetic (#8719)

This makes it so that EqSolver is the main entry point for all equality engine explanations in arithmetic; it still defers to the CongruenceManager to compute these explanations.

To do this, when the core linear solver depends on an explanation from the equality engine, it instead provides a placeholder. Since explanations are computed recursively in TheoryEngine, this will trigger another call to TheoryArith::explain, which will then be handled by the EqSolver. Thus, there should be no net effect on the overall explanations in this commit.

This is work towards eliminating the dependency of the linear solver on the equality engine.

Make printStatisticsSafe public (#8721)

Solver::printStatisticsSafe() is private right now. There is no real reason for that, and as we claim that the driver is only using the regular API we should just make it public.

Add declareOracleFun interface to SolverEngine (#8622)

After this PR, declare-oracle-fun will be added to the API and parser.

Refactor oracles using new std::function backend (#8717)

This also updates several places to be generalized to methods that return a vector of Nodes. Previously we had assumed a use case returning a single node.

After this PR, #8622 will be updated to use the new std::function interface.

Remove unecessary calls to equality engine from congruence manager (#8715)

Removes a deprecated explain interface.

Remove obsolete private methods from API (#8716)

This PR removes two private utilities from the API: Sort::sortSetToTypeNodes and one DatatypeDecl constructor.

Fix rewrite for to_real in division by zero (#8714)

Fixes #8712.

Add support for oracle constant nodes (#8707)

This is the beginning of a refactoring to make std::function the basis for oracles internally, not binary names.

Fix LFSC node converter for 0-ary tuples (#8706)

Was missing 0-ary Tuple case for type-as-node.

Also removes a spurious check in the user-defined sorts case.

Fixes some issues in the nightlies.

Update LFSC version (#8713)

This updates the get-lfsc-checker script to get the latest version of
LFSC, which supports older versions of CMake.

Use (non-recursive) unpurified form instead of original form for defining Skolems (#8699)

This modifies our treatment of purification Skolems in the internal proof calculus. In particular, we now use an "unpurified form" instead of "original form" for defining Skolems. SKOLEM_INTRO is modified to prove the equality between a skolem and its unpurified form.

For example:
k1 purifies (ite A B C)
k2 purifies (+ k1 1)

The unpurified form of k2 is (+ k1 1), its original form is (+ (ite A B C) 1).

As a consequence:
(1) Our global skolem sharing is now slightly weaker, for example a k3 could be constructed whose unpurified form is (+ (ite A B C) 1); previously this would guaranteed to be k1.
(2) We do not require recursively computing the original form of terms when constructing purification Skolems,
(3) The witness form proof generator requires a fix point.
(4) The LFSC signature is simplified, and does not require a side condition to recursively compute the original form of a Skolem.

Fixes cvc5/LFSC#81.

docs: Some fixes in options docs. (#8710)

Change option name for mbqi in fmf (#8701)

In preparation for a new basic implementation of MBQI.

Simplify representation of datatypes at the TypeNode level (#8702)

They previously were TYPE_CONSTANTs hashed by the index of their DType in the NodeManager. Now they are variables having an attribute that is their index.

This makes datatypes more analogous to uninterpreted sorts, and eliminates the need for an auxiliary DatatypeIndexConstant class.

Final preparation for CONST_INTEGER (#8700)

With this PR, CI passes when using CONST_INTEGER instead of (all) integral CONST_RATIONAL.

This does not make this change yet, so CONST_RATIONAL is still used throughout.

Migrate basic EqualityEngine management from CongruenceManager to EqSolver (#8684)

This is work towards having the linear arithmetic solver not impose restrictions on equalities.

The linear arithmetic solver using a CongruenceManager which involves many non-standard uses of the equality engine.

The responsibilities of the CongruenceManager should be migrated to the arithmetic EqSolver, which manages the equality engine in the default way.

This PR is the first step. It makes it so that the memory management and notifications of the equality engine are now solely the responsibility of the EqSolver.

All relevant notifications from the EqSolver are directly forwarded to CongruenceManager. Thus there are no significant behavior changes in this PR.

This PR required removing the experimental option arithCongMan, which forces having the CongruenceManager and the EqSolver both use equality engines.

Add strict-cube and decision-trail partitioning strategies (#8651)

Add the strict-cube modification to the revised partitioning algorithm and add the full-trail partitioning strategy.

More robust treatment of flattening in arith rewriter (#8695)

Currently can allow rewritten forms to be rewritable.

Fixes #8692. Fixes #8693. Fixes #8697.

Make arith msum utility agnostic to Int (#8694)

This utility should continue to assume arithmetic subtypes.

Fixes #8691.

Add missing tests for some corners of the API (#8688)

This PR adds a bunch of unit tests for some not yet covered corners of the API.

docs: Do not use explicit line numbers in literalinclude. (#8690)

Further refactoring in preparation for CONST_INTEGER (#8687)

Miscellaneous refactorings from trying to enable CONST_INTEGER.

Fix tuple printing in LFSC (#8696)

We weren't collecting them as user-defined types after the recent refactor to Tuples.

Properly represent Tuples in the TypeNode AST (#8648)

This makes it so that Tuple types are properly represented in the AST. It also removes a spurious restriction that disallowed higher-order tuples (this was leftover from a very old sanity check in the old API).

For example, a tuple type over (Int, Int) is now (TUPLE_TYPE INT INT) instead of a DATATYPE_TYPE constant.

Tuple types behave exactly like datatypes; we can still retrieve their DType as before.

This is in preparation for gradual types and symbolic tuple projections.

Add simple type rule for real-or-int arguments (#8685)

This adds a simple type rule, ARealOrInteger, which checks whether the
argument of an operator is either a Real or and Int. Note that this
is currently equivalent to AReal, but the plan is to make AReal
strict in the future.

Replace mkConst(CONST_RATIONAL) by mkConstReal (#8686)

This PR removes the usages of CONST_RATIONAL in the nonlinear arithmetic solver.

Towards proper usage of TO_REAL (#8680)

This is work towards making the rewriter preserve types, which is work towards eliminating subtyping.

This makes it so that the arithmetic rewriter does not simply drop TO_REAL from all terms, as this may change the type of the Node. Instead, TO_REAL is pulled upwards, and can be removed beneath arithmetic relations. TO_REAL is not eliminated if it occurs as a child of an operator not belonging to arithmetic. For example if x,y : Int:

(= (+ (to_real x) y) 0.0) ---> (= (to_real (+ x y)) 0.0) ---> (= (+ x y) 0.0) ; note this is the same rewritten form as before
(P (+ (to_real x) y)) ---> (P (to_real (+ x y))).

The one exception is that to_real applied to constants is simply dropped (for now), for example:

(to_real 5) ---> 5

where above, a Real term is rewritten to an Int term. (Fixing this will require further PRs that make integer constants of kind CONST_INTEGER and integral CONST_RATIONAL have Real type, thus we can have the above rewrite return 5 that is constant and has type Real).

Several quantifiers utilities are patched to preserve their behavior wrt handling TO_REAL.

Finally, a few fixes for subtypes are made to the regressions that we were not catching as errors before, and adds one regression.

The net effect of this PR is that the rewritten form of terms may have to_real applications that occur as direct children of symbols from other theories. Special care is required for preregistration, shared terms, and getting model values in the linear solver to strip off TO_REAL if necessary before using the (unmodified) interface to the linear solver.

FYI @barrettcw

Document non-standard string operators (#8679)

This adds documentation for `str.indexof_re`, `str.update`, `str.rev`,
`str.to_lower`, and `str.to_upper`. Note that it moves the documentation
of strings to the "non-standard or extended theories".

Ensure mkConstInt is used on integral rationals only (#8683)

This is work towards using CONST_INTEGER for integer constants.

This corrects a few places that incorrectly assumed that integers were necessary.

Refactor interfaces for E-matching (#8665)

InstMatch objects are now fully owned by Triggers. They are passed by reference to InstMatchGenerators.

This also simplifies the interfaces by not passing the quantified formulas.

This is in preparation for making InstMatch objects carry entailment test information.

Make extended rewriter use standard Subs utility (#8682)

This is work towards ensuring all substitutions are strictly typed.

Add an option to enable all testers. (#8676)

Add missing parenthesis for bags documentation (#8673)

Add unit test for code not exposed by java API (#8678)

This PR adds a C++ unit test that explicitly calls into API functions that are not exposed by the java API. This fixes the issue of false positives in our API coverage checks, as some parts of the C++ API are legitimately not used by the java API.
It also corrects a few other minor issues.

Add unit test for code not exposed by python API (#8677)

This PR adds a C++ unit test that explicitly calls into API functions that are not exposed by the python API. This fixes the issue of false positives in our API coverage checks, as some parts of the C++ API are legitimately not used by the python API.

Add some missing API tests (#8669)

This PR adds a couple of simple API tests for parts of the API that are not covered yet.

Move tests around (#8670)

This PR moves two tests that dealt with particular issues out of unit/api/cpp (which should only have generic unit tests). They are now in unit/theory and api/cpp/.

int-blaster: not allowing higher order functions (#8674)

Currently we throw an OptionException if higher order logic is enabled, but we only check this once we reach an APPLY_FUN node.
This PR does the check regardless of APPLY_FUN, thus capturing, e.g. BAG_MAP.
Fixes cvc5/cvc5-projects#415.
The PR also includes a simplified version of the test from that issue.

Move datatype split inference scheme to its own method (#8664)

Clean code for datatypes split (#8667)

Non-moving version of #8664.

Make labelled separation logic asserts preserve labels (#8671)

This is a first step towards fixing #8659.

The issue is that when two labels are equal, we assume they refer to subheaps of the same heap. This is incorrect for magic wand. This ensures we preserve labels, a further PR will ensure that syntactic equality on labels (instead of semantic equality) is used for knowing when two pto constraints must be unified. This means that SEP_LABEL nodes should never be rewritten.

Fix PyUnicode_AsWideCharString signature (#8522)

Add proper exception specification to the `PyUnicode_AsWideCharString` signature.

Add resource limiting to coverings solver (#8672)

Right now, resource limits are not checked while the coverings solver is computing. This PR adds a new resource and spends it within every recursive call of the coverings solver. This fixes cases where cvc5 does not honor the per-call time limit on QF_NRA.

Add option to apply constant propagation for all learned literals (#8668)

Adds `--simplification-bcp`, disabled by default.

Refactoring of initial lemmas in datatypes (#8666)

This is work towards revising how/when the datatypes instantiate rule is applied.

This simplifies the management of when new terms are registered in the theory of datatypes.

We now use the equality engine's eqNotifyNewClass callback to know when a term should be considered. Previously, this was split over two methods (additionally, collectTerms).

Most importantly, this eliminates the need for a manual addition of the "instantiated constructor term" in getInstantiateCons, which complicates the logic for the impact of applying the datatypes instantiate rule.

Minor improvements for entailment test (#8663)

Makes some minor improvements to the existing (non-incremental) entailment tests, based on comparing with a new implementation.

Minor improvements to quantifiers utilities (#8661)

Make IndexTrie take nodes (#8649)

This makes the class easier to use and allows for a usage where the null node is interpreted as specifying all nodes.

This is in preparation for using this class for testing whether an instantiation from any instantiation strategy is currently feasible based on learning in the style of fail masks from Janota et al FMCAD 2021.

Also, this class should be renamed to something more appropriate, since it no longer takes indices.

FYI @MikolasJanota

Move rep set iterator to its own file (#8647)

Refactor InstMatch (#8646)

Also simplifies the (old) version of multi trigger matching, which copied InstMatch objects unnecessarily, and also used EqualityEngine iteration instead of iterating on a trie.

This is in preparation for making InstMatch objects optionally track fast (and generalized) failures based on configurable criteria.

Refactor mkRep option for instantiation (#8657)

This removes mkRep as an option for addInstantiation.

It adds a new interface for making term vectors representative, which is required for FMF instantiation.

Add some missing resultants in the coverings solver (#8662)

This PR fixes a subtle corner case in the generalization within the coverings solver. When generalizing a single interval that spans the whole real line (i.e. from -infty to infty) that is based on multiple polynomials (most likely because the origin constraint factored) we did not include their pairwise resultants.
This detail is arguably missing in the paper, or rather hidden in a very vague notion of "performing standard CAD simplifications".
Fixes #8638.

Simplify internal represenation of uninterpreted sorts (#8660)

Fix GMP cross-compilation when Wine installed (#8645)

When Wine is installed on the system, our current invocation of GMP's
`configure` fails. To fix the issue, we pass `CC_FOR_BUILD` that is used
to compile build-time programs. When compiling GMP with `--enable-cxx`,
it also seems to be necessary to pass `--build` to make `configure`
pass. Passing `--build` for cross-compilation builds is also recommended
by the [GMP documentation](https://gmplib.org/manual/Build-Options).

Simplify internal representation of instantiated sorts (#8620)

Previously, sort constructors were stored as underlying operator of the NodeValue of instantiated sorts. This made it very difficult to access what sort constructor was used to construct the uninterpreted sort. Moreover, this representation made it virtually impossible to have a clean implementation of the LFSC printer for instantiated uninterpreted sorts, which requires renaming sort constructors.

This introduces a new kind INSTANTIATED_SORT_TYPE, which acts as an uninterpreted sort. The sort constructor is stored as the first child in its AST, which is analogous to parametric datatypes. It furthermore restricts SORT_TYPE to 0 children.

This is work towards having correct LFSC proof output when the input contains instantiated uninterpreted sorts.

[Regressions] Use Wine for Windows builds (#8652)

This changes our build system to use Wine when we are testing a
cross-compiled Windows build. It updates the post-processing in the
regression script to remove `\r` characters and updates two regressions
to make them compatible with Windows builds.

Move VTS term cache to term registry (#8656)

This is in preparation for simplifying the interface to Instantiate::addInstantiation, where the VTS cache can be consulted to ask if VTS is necessary.

Option exception for quantified bit-vectors + eager bitblasting + incremental (#8658)

Fixes #8654.

Make BVInstantiatorUtil an EnvObj (#8633)

Eliminates 5 of the remaining 8 static calls to Rewriter::rewrite.

Add custom targets for specific testers. (#8653)

This adds custom targets to run a specific tester (e.g., `regress-lfsc`).

Signed-off-by: Abdalrhman M Mohamed <abdalrhman-mohamed@uiowa.edu>

Minor cleanup of NodeManager (#8650)

Add `deep-restart` option (#8644)

Adds the ability to have the SmtSolver automatically deep restart after a criteria is met (we have learned new top-level literals, and a threshold of time since the last learned literal has passed). This can be used for non-incremental satisfiability queries only.

By default, --deep-restart=input kicks in on 155 of our regressions, this adds 4 delta-debugged regressions that exercise the feature.

Add tester for LFSC printer. (#8606)

This adds an option to check the LFSC proofs generated by `cvc5` for unsat benchmarks. This does not enable the tester in CI as it fails for many benchmarks.

[Seq] Remove `SkolemCache::mkSkolemSeqNth()` (#8643)

This removes the `SkolemCache::mkSkolemSeqNth()` method. Instead of
handling the out-of-bounds case with a UF, we just use `seq.nth` in its
original form for the out-of-bounds case (and rely on the fact that the
equality engine is configured to perform congruence closure on that
kind). This is part of the changes for the paper on sequences.

Add bag.partition evaluation (#8637)

Add utilities in preparation for deep restarts (#8642)

Remove unused `SEQ_NTH_TOTAL` kind (#8048)

Originally, the idea was to expand the definition of `SEQ_NTH` to use
`SEQ_NTH_TOTAL` (i.e., a total version of that operator), but we have
since then decided to just use `SEQ_NTH`.

Improve handling of `(push)` and `(pop)` (#8641)

This extends PushCommand and PopCommand to take a number of levels
to push/pop. We have support for pushing an arbitrary number of levels
at the API level, so this simplifies the parser code and makes dumping
more precise (previously, we were dumping (push 2) as two (push 1)
commands).

Add declare-oracle-fun command (#8621)

In preparation for adding declare-oracle-fun to the API/parser.

Minor simplifications for datatype selector triggers (#8636)

This is leftover simplification from the fact that (s x) is no longer expanded to (ite (is-C x) (s_total x) (uf x)).

int-blaster: direct support for bvcomp (#8640)

This PR adds a translation of bvcomp using an ite.
Fixes cvc5/cvc5-projects#417
and contains the failed formula as a regression.

Remove redundant assertion in int-blaster (#8639)

When translating nodes with no children, the default case does not change the original node, and so we do not need to assume anything about the node. fixes cvc5/cvc5-projects#416 . The example from the issue is added as a unit test.

Updates to zero level learner (#8597)

Now tracks learned literals for all types.  Unifies the output of `-o learned-literals`.

Followup PRs will add the deep restart feature, which configures which kind of learned literals can be used when restarting.

Avoid trivial equalities in explanation of SETS_CARD_CYCLE (#8635)

This was the root cause of cvc5/cvc5-projects#178.

Simplify implementation of subtype methods in TypeNode (#8634)

Also deletes unused data that was used for an inference schema involving subtypes in sets.

Add table.project evaluator (#8632)

This PR

adds evaluator for table.project operator
updates the parser to interpret "Table" as a table with zero columns

Move linear arithmetic solver to theory::arith::linear (#8628)

This moves the current linear arithmetic solver to src/theory/arith/linear, and inside `cvc5::internal::theory::arith::linear`.

Some code uses internal utilities from `arith::linear`, although this should be minimized.

This is preparation for breaking dependencies with the old code.

Generalize concat conflict for sequences in LFSC (#8625)

This ensures LFSC proofs are correct when using CONCAT_CONFLICT for sequences.

In detail, to justify why (seq.++ (seq.unit c1) t1) = (seq.++ (seq.unit c2) t2) is a conflict, where c1 and c2 are constants, we require an explicit step to evalute (seq.unit c1) = (seq.unit c2) to false, since c1 and c2 are theory-specific constants.

Note this is different from (str.++ (char n1) t1) = (str.++ (char n2) t2) where a syntactic check of n1 and n2 suffices.

This fixes proof checking for regress0/seq/seq-types.smt2.

Remove instances of `check-proofs` in regressions. (#8630)

This PR removes usages of check-proofs option according to the following rules:

unsat and no-check-proofs --> DISABLE-TESTER: proof
unsat and check-proofs --> remove option
sat and no-check-proofs --> remove option
sat and check-proofs --> change to produce-proofs
no-produce-proofs --> DISABLE-TESTER: proof

Add some missing FP symbols to LFSC (#8629)

Distinguish name variants for types in LFSC node converter (#8624)

This PR ensures we distinguish names for cases where types and terms are given the same name.

In particular, this generalizes the getNameForUserNameOf to work with node identifiers instead of Node, so that TypeNode can also use this method for assigning unique names.

It also adds preliminary support for uninterpreted sort constructors in the LFSC node converter.

This fixes 4 more LFSC failures on our regressions.

Make more utilities distinguish Int and Real (#8626)

Towards eliminating arithmetic subtyping.

Simplify management of separation logic heap (#8580)

The separation logic heap is conceptually an extension of the logic, which lives in Env. This PR moves the separation logic heap types from TheoryEngine to Env.

It furthermore makes it so that declaring the separation logic heap does not force initialization of the SolverEngine, meaning that further declarations/options may be done after setting the heap.

This is in preparation for making the SmtSolver class easier to deep reset.

Remove support for unused `declare-*` commands (#8623)

This commit removes support for
declare-sorts/declare-funs/declare-preds. These commands seem to
be a leftover of an earlier SMT-LIB draft [0]. We only had a test for
declare-funs and Z3 doesn't support declare-funs either.

[0] http://homepage.cs.uiowa.edu/~astump/papers/smt-cmd-lang.pdf

Fix internal type issue for congruence over quantifiers in LFSC post-processor (#8619)

Avoids debug assertions in LFSC proof conversion when doing congruence over closures.

Implement internal support for (definitional) satisfiability modulo oracles (#8618)

Adds implementation of OracleEngine, which adds lemmas of the form (= (f c) d) on demand for I/O pairs (c,d) from oracle calls.

Make LFSC printer robust to internal types (#8616)

This makes the LFSC node converter track the "user declared" symbols and types that it encounters.

It furthermore makes the "dry run" phase of proof printing happen before types and symbols are declared, so that all declared symbols are found before the preamble of LFSC proofs are printed.

These changes are specifically to fix cases where a internal type is generated that does not appear in the input. For example, some preprocessing passes may construct auxiliary uninterpreted sorts.

This fixes 6 more LFSC failures from our regressions.

Implement internal support for synthesis modulo oracles (#8617)

SyMO is implemented as a preprocessor for SMT queries in the verification subsolver of SyGuS.

Remove static calls to rewrite involving array constants (#8613)

The type enumerators for arrays and functions relied on static calls to the rewriter. This is overkill, as the appropriate calls to the utility method normalizeConstant in the array rewriter class suffices.

The eliminates 2 of the remaining static calls to the rewriter.

Improvements to phase shifting + purification lemmas (#8598)

Makes 3 improvements to phase shifting + purification lemmas:
(1) we use purification skolems when possible, e.g. for exp(t), or sin(c) where -pi <= c <= pi, since it is unnecessary to assert c is in proper phase. This also adds proofs for purification of exp, which is hence trivial.
(2) we make the phase shift variable a real for which is_int holds. This avoids mixed int/real arithmetic, in preparation for eliminating subtyping
(3) the proof checker and sine solver use a common utility for getting the phase shift lemma.

Revised partitioning (#8143)

This adds the "revised" partitioning algorithm to the splitter and adds support for collecting literals from the sat solver. There is only one partitioning strategy in this PR, but the others will be added in subsequent PRs.

[proofs] [dot] New way to traverse the proof when printing a .dot DAG (#8610)

Change the way cvc5 traverse and print the proof when --proof-dot-dag option is used. The main change is related to the way the printer tracks visited proof nodes. The new conditions are:

- If the proof node has already been visited inside the current scope.
- If the proof node is closed (i.e. does not contains a subproof whose rule is ASSUME) and has already been visited (here the condition is global and the scope doesn't matter).

Signed-off-by: Vinícius Braga Freire vinicius.braga.freire@gmail.com

Integrate oracle checker into quantifiers term registry (#8604)

Also incorporates into sygus term database. For SyMO, oracle function symbols act analogously to recursive function definitions; the oracle checker is used to rewrite terms in the same contexts as when recursive function definitions are evaluated.

Fix spurious assertion involving subtypes (#8611)

Fixes #8609.

Update LFSC version (#8614)

Now has a different expected output ("success" for each check).

Add Relation and Table types to SMTLib parser (#8605)

Fix type issue for FP constants in LFSC node converter (#8612)

Fixes type errors in debug builds.