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.

Add method to get leaves of a NodeTrie (#8583)

From the oracles branch.

Make sets and bags operators left-associative (#8584)

Makes it so that we parse n-ary applications of e.g. set.union in smt2.
Left associativity seems to be the case for difference operators in databases.
See
https://docs.microsoft.com/en-us/sql/t-sql/language-elements/set-operators-except-and-intersect-transact-sql?view=sql-server-ver15

Eliminate SmtSolver dependency on SolverEngineState (#8581)

This is in preparation for making SmtSolver able to be deep reset (reconstructed) within in a SolverEngine instance.

Minor fix for printing nullary operators in smt2 (#8577)

Fix proof checker for SUBS (#8578)

Could lead to proof checking failures when using `--proof-granularity=rewrite`

Fixes for LFSC printing and signatures (#8579)

Ensures we recognize some internal FP symbols, adds a missing string operator, fixes seq.unit operator printing (required for CONG over seq.unit), fix for 0-ary tuple printing.

Start post-release for 1.0.0

Bump version to 1.0.0

api: Fix doc generation for kinds in java API. (#8576)

Plus some more fixes for docs.

Update copyright headers for release 1.0 (#8539)

Update NEWS for cvc5 1.0. (#8460)

Co-authored-by: Andrew Reynolds <andrew.j.reynolds@gmail.com>
Co-authored-by: Gereon Kremer <nafur42@gmail.com>
Co-authored-by: mudathirmahgoub <mudathirmahgoub@gmail.com>
Co-authored-by: Andres Noetzli <andres.noetzli@gmail.com>

Make inst constant attribute robust to purification variables (#8573)

Fixes #8572.

Certain combinations of cegqi/sygus-inst may be solution unsound when combined with E-matching, due to using skolems that have dependencies on instantiation constants are used in instantiations.

Make rewriter more robust against RAN becoming rational (#8564)

We use real algebraic number to represent multiplicities of sum terms within the arithmetic rewriter. Unfortunately, such real algebraic numbers can realize that they are in fact rational at awkward times. This makes isRational() unsuitable for checking this, instead we should construct the node and check afterwards.

api: More fixes in the java API. (#8571)

Be permissive for subtyping in function definitions (#8568)

This is to accommodate the Real theory in SMT-LIB, which says that numerals specify reals.

Instead of making our parser for numerals dependent on the logic, we are more permissive.

This fixes several spurious parsing issues in smtlib.

api: More fixes in C++ API docs. (#8570)

Write-up for Pythonic API quickstart (#8566)

docs: Fix mkTerm calls in theory documentation. (#8567)

api: Fix OptionInfo docs for java API. (#8569)

api: Fixes in docs for Op. (#8565)

api: Fixes for Grammar docs in java API. (#8563)

api: Fixes in java api docs. (#8562)

api: Fixes in docs for DatatypeConstructor. (#8561)

Docs: remove api from package name in java.rst (#8560)

Fix broken links in https://cvc5.github.io/docs/cvc5-0.0.12/api/java/java.html

api: More fixes in docs. (#8559)

api: First batch of fixes in the api docs. (#8558)

Uses `@return <uppercase> .... <period>` and `@param <param> <uppercase> ... <period>`,
plus various fixes in the docs.

Fix links when converting kinds documentation to python (#8557)

This mainly fixes explicit rst links when we convert the kinds comments to python.