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.

Fix spurious assertion failure caused by subtyping in LFSC proof postprocessor (#8608)

Also removes an old case for parametric datatypes in getBaseType, which is incorrect since datatypes not longer use subtyping.

This avoids more assertion failures in debug mode for LFSC due to subtypes.

Fix type issue for LFSC null terminator (#8607)

This fixes an assertion failure when producing LFSC proofs in debug mode.

The issue currently does not impact the correctness of the code, although this will be important if subtypes are eliminated.

Add oracle checker utility (#8603)

This is a utility that allocates oracle callers for oracle functions on demand and can be used to convert a term containing oracle function symbols into its evaluated form.

It will be used for both SMTO (for checking consistency of oracle interfaces) and SyMO (as part of refinement lemma evaluation in CEGIS).

Add oracle caller utility (#8599)

The implementation of this class has a placeholder for calling external binaries, which will be filled in a later PR.

Making some benchmarks SMT-LIB compliant for subtypes (#8600)

This makes some of our regressions compliant for arithmetic subtyping. This is required to make these benchmarks parsable when subtyping is eliminated.

We should discuss whether we should be permissive for such benchmarks. Regardless, the majority of our regressions should be SMT-LIB compliant.

Fix more misuses of arithmetic subtypes (#8601)

[proofs] [dot] Print nodes clusters at dot format (#8574)

Add a printer option that allows the dot printer to identify each node type and group them up in node clusters. These cluster are determined according to "part of the proof" whether a node belongs to:

- input
- sat proof
- cnf proof
- theory lemma proof
- preprocessing

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

More cleaning uses of arithmetic subtyping (#8595)

Towards eliminating arithmetic subtyping.

Add oracle engine to quantifiers engine (#8589)

This class is the subsolver of quantifiers engine for handling oracles in SMTO. The implementation of this class will be added in followup PRs.

It also contains a utility method for constructing oracle interfaces.

Remove spurious case of ppRewrite (#8596)

Constants equal to constants are always rewritten to false.

Add learned literal type and prop learned database (#8582)

In preparation for deep restart feature, and for extending the get-learned-literal interface to multiple types.

Simplify parser (#8592)

This commit simplifies our parser by removing code that is not relevant
anymore since the removal of support for SMT-LIB <=2.6.

Minor refactoring of smt2 printer (#8588)

Do not allow unresolved sorts in smt2 (#8587)

This simplifies the smt2 parser so that we never parse "inlined" unresolved sorts. This infrastructure was used for accomodating the ad-hoc datatype syntax from SMT-LIB <=2.5, and SyGuS 1.0.

We now assume that sorts are fully declared wherever we parse them.

Eliminate more uses of CONST_RATIONAL (#8590)

To eliminate arithmetic subtyping, we require distinguishing CONST_RATIONAL and CONST_INTEGER internally. Code should avoid usage of these kinds and use trusted utilities instead (e.g. mkConstReal, mkConstInst, isConst).

Properly parse numerals as real when integers are disabled (#8591)

SMT-LIB says numerals are real when integers are not included in the logic.

Due to subtyping, we don't complain internally, although if subtyping is eliminated, this fix is necessary.

Generalization for sygus verify utility (#8586)

This is in preparation for synthesis modulo oracles (SyMO), where the verification loop may run multiple times for a given solution. In a follow up PR, the loop introduced in this PR may run multiple times when oracles are present, since oracle invocations in the subsolver may trigger further simplifications to the rewritten form of the specification.

It also makes it so that candidate models are generated for "unknown" results for subsolvers, which is required for SyMO.

Internal representation of oracle interface quantifiers (#8585)

This is the first step towards supporting SMT and synthesis modulo oracles.

It adds the kind required for specifying "oracle interface quantifiers", or, quantified formulas that specify constraints that depend on an external binary.