Mathias Preiner [Fri, 9 Oct 2020 18:42:25 +0000 (11:42 -0700)]
Remove deprecated add-path commands and use $GITHUB_PATH instead. (#5232)
Alex Ozdemir [Fri, 9 Oct 2020 17:48:16 +0000 (10:48 -0700)]
use right arith explanation fn to fix regressions (#5231)
Use the Node-returning variants of
Constraint::externalExplainByAssertions in TheoryArithPrivate locations
that aren't computing proofs.
The problem is that the TrustNode returning variant requires that arith
has stored an externally valid literal for the constraint, which is not
always the case.
This is what we did on proof-new, I just forgot.
Alex Ozdemir [Fri, 9 Oct 2020 12:55:14 +0000 (05:55 -0700)]
(proof-new) proofs for arith-constraint explanations (#5224)
Threads proofs through arith::Constraint's machinery for explaining
constraints. Changes, by function:
externalExplainByAssertions:
introduce scope to prove the implication
externalExplainForPropagation:
introduce scope to prove the implication
externalExplainConflict:
use other machinery to prove conflicting constraints
use the CONTRA rule
introduce scope to close the conflict proof
Future commits will pick up these proofs in theory_arith_private.cpp.
Future commits will prove the "split" lemmas produced in constraint.cpp
Andres Noetzli [Fri, 9 Oct 2020 05:28:42 +0000 (22:28 -0700)]
reset-assertions: Remove all non-global symbols in the parser (#5229)
Fixes #5163. When `:global-declarations` is disabled (the default), then
`(reset-assertions)` should remove all declared and defined symbols. Before
this commit, we would remove the defined function from `SmtEngine` but the
parser would not remove it from its symbol table because the symbol was defined
at (what it considered) level 0. Level 0, however, is reserved for global
symbols that we never want to remove.
This commit adds an additional global `pushScope()`/`popScope()`, similar to
what we have in `SmtEngine`. As a result, user-defined symbols are now defined
at level 1 and get removed from the `SymbolTable` when `(reset-assertions)` is
called. The commit also makes sure that symbols defined by the logic are
asserted at level 0, so that they are not removed by `(reset-assertions)`. It
adds a flag to `defineType` to ignore duplicate definitions because some
symbols are defined by multiple logics, which leads to a failing assertion when
inserting them both at level 0 in the hashmap of the `SymbolTable`. E.g.
strings and integer arithmetic both define `Int`. The commit also fixes
existing unit tests that fail with these stricter semantics of
`(reset-assertions)`.
Signed-off-by: Andres Noetzli <noetzli@amazon.com>
Andrew Reynolds [Fri, 9 Oct 2020 01:07:41 +0000 (20:07 -0500)]
Simplify approach for collapsed selectors over non-closed enumerable types (#5223)
This simplifies the approach for wrongly-applied selectors whose range type involves e.g. uninterpreted sorts. These cases are particularly tricky since uninterpreted constants should never appear in facts or lemmas.
Previously, the rewriter had special cases for either making a ground term or value, and a purify step was used to eliminate the occurrences of uninterpreted sorts afterwards.
This PR leverages mkGroundTerm in this inference instead, and makes the rewriter uniformly use mkGroundValue.
This also required making the type enumerator for datatypes more uniform. In particular, we require that the first value enumerated by the type enumerator is of the same shape as the term required by mkGroundTerm, or else debug-check-model will fail. This is due to the fact that now the inference for wrongly applied selectors uses terms while the rewriter uses values. The type enumerator is updated so that recursive codatatypes also first take mkGroundValue as the zero term, when they are well-founded. Previously this was skipped since the codatatype enumerator uses a different algorithm for computing its ground terms.
This is in preparation for further work on optimizations and proofs for datatypes.
Andrew Reynolds [Fri, 9 Oct 2020 00:34:12 +0000 (19:34 -0500)]
(proof-new) Add lazy proof set utility (#5221)
This is a common pattern that is required in several places in preprocessing.
Andrew Reynolds [Fri, 9 Oct 2020 00:07:52 +0000 (19:07 -0500)]
(proof-new) Theory engine proof producing (#5195)
This completes proof support in TheoryEngine.
The main addition in this PR is to make its getExplanation method proof producing.
Andrew Reynolds [Thu, 8 Oct 2020 22:10:36 +0000 (17:10 -0500)]
(proof-new) Fixes and improvements for smt proof postprocessor (#5197)
This includes several subtle issues encountered in the past month based on our regressions.
It also improves the expansion forms of MACRO_ rules to use EQ_RESOLVE instead of a TRUE_INTRO/TRUE_ELIM scheme. This is both more compact and avoids cyclic proofs for some corner cases of proofs with Boolean constant equalites.
makaimann [Thu, 8 Oct 2020 16:35:56 +0000 (09:35 -0700)]
Get correct NodeManagerScope for toStrings in API (#5216)
Gets the correct `NodeManagerScope` for getting the `toString` of a term, op, or sort. The following program had strange output:
```
#include "cvc4/api/cvc4cpp.h"
using namespace CVC4::api;
using namespace std;
int main()
{
Solver s;
Term x = s.mkConst(s.getIntegerSort(), "x");
cout << "x = " << x << endl;
Solver s2;
cout << "x = " << x << endl;
return 0;
}
```
It was outputting:
```
x = x
x = var_267
```
Fixing the scope makes the output `x = x` both times, as expected.
yoni206 [Thu, 8 Oct 2020 00:20:52 +0000 (17:20 -0700)]
fix unit failures on debug without symfpu (#5212)
The following tests fail (locally) when compiling with debug and without symfpu:
unit/api/sort_black (Failed)
unit/theory/logic_info_white (Failed)
unit/util/floatingpoint_black (Child aborted)
This PR conditions the relevant parts of these tests to the availability of symfpu.
Co-authored-by: Aina Niemetz <aina.niemetz@gmail.com>
Alex Ozdemir [Wed, 7 Oct 2020 18:48:06 +0000 (11:48 -0700)]
(proof-new) proofs in ee -> arith pipeline (#5215)
Threads proofs through the flow of information from the equality engine
into the theory of arithmetic.
Pretty straightforward. You just have to bundle up information from the EE.
Aina Niemetz [Wed, 7 Oct 2020 17:55:29 +0000 (10:55 -0700)]
New C++ API: Rename Term::isConst() to Term::isValue(). (#5211)
Gereon Kremer [Wed, 7 Oct 2020 14:13:41 +0000 (16:13 +0200)]
Make sure conflicts are not rewritten (in arithmetic) (#5219)
The arithmetic inference manager did rewrite conflicts, which lead to nodes from the conflict not being assumptions (but rewritten assumptions) triggering an assertion. This rewrite is now removed.
Furthermore rewrites triggering the same assertion within the icp subsolver have been refactored to avoid this issue.
Andrew Reynolds [Wed, 7 Oct 2020 12:23:53 +0000 (07:23 -0500)]
(proof-new) Add the strings proof constructor (#4903)
This is the method for converting strings InferInfo into instructions for building ProofNode. Notice that this is done as a standalone module, and thus the theory of strings uses Inferences only, not PfRule.
The next step will be to integrate this utility into InferenceManager.
Malte Mues [Wed, 7 Oct 2020 06:50:45 +0000 (08:50 +0200)]
Improve OSX support by adding os detection and adapting calls for OSX. (#5023)
On OSX there is another libtoolize tool already available.
The gnu libtoolize version installed with MacPorts or brew is called glibtoolize.
This change makes it easier to run the file on OSX.
Signed-off-by: Malte Mues (mail.mues@gmail.com)
Andrew Reynolds [Wed, 7 Oct 2020 03:22:16 +0000 (22:22 -0500)]
Process pending inferences at the beginning of datatypes post check (#5213)
This fixes a potential crash in datatypes where a pending inference is not processed on a call to Theory::check. This ensures the pending set of inferences in datatypes is empty after each check. This also ensures the pending vectors are cleared before each check in datatypes.
yoni206 [Tue, 6 Oct 2020 20:47:58 +0000 (13:47 -0700)]
bv-to-int: change order of passes (#5208)
Closes #5095 and replaces #5110.
There are two tests in #5095 that produce two different assertion failures when using bv-to-int.
The first happens because the substitution map wasn't applied after the pass.
The second happens because div (that is introduced in the pass) is not rewritten using witness.
Both problems are solved by making sure that apply-substs, theory-preprocess and ite-removal are executed after bv-to-int.
The two tests from #5095 are included as regressions.
Alex Ozdemir [Tue, 6 Oct 2020 19:15:46 +0000 (12:15 -0700)]
(proof-new) proofs for ArithCongMan -> ee facts (#5207)
Threads proof production through the ArithCongruenceManager's pipeline
of information to the equality engine.
The idea is to define a method:
ArithCongruenceManager::assertLitToEqualityEngine(literal, reason, pf)
This method asserts a literal to the equality engine with the given
proof and reason. It stores the proof of the literal for the equality
engine's future reference, and is smart about symmetric literals.
This machinery uses proofs that are not closed over the reason, as the
equality engine requires.
Other functions in the pipeline:
assertionToEqualityEngine
equalsCostant
construct proofs and call assertLitToEqualityEngine.
Future commits will address the ee -> ArithCongruenceManager pipeline,
and the relationship between ArithCongruenceManager and the rest of
arithmetic.
Andrew Reynolds [Tue, 6 Oct 2020 15:02:54 +0000 (10:02 -0500)]
(proof-new) Add interface for trusted substitution and update ppAssert (#5193)
The current work on proof-new involves proofs for preprocessing. The biggest issue currently is that our preprocessing passes do not track proofs for substitutions.
This adds a "trusted substitution" class with is a layer on substitution map. The proof aspect of this class is not yet implemented, this PR just adds its interface.
This also updates Theory::ppAssert to take a TrustSubstitutionMap instead of a SubstitutionMap, since eventually we will require proofs to be provided for substitutions that are added to this map.
Andrew Reynolds [Tue, 6 Oct 2020 14:31:16 +0000 (09:31 -0500)]
(proof-new) Allow null proofs from generators in LazyCDProof (#5196)
In some cases, a proof generator provided to a LazyCDProof may provide a null proof, which causes a segfault on proof-new currently. This PR makes LazyCDProof robust to this case; nullptr is interpreted as the fact is an assumption.
mudathirmahgoub [Tue, 6 Oct 2020 13:23:40 +0000 (08:23 -0500)]
Add operators bag.from_set, bag.to_set to the theory of bags (#5186)
Andrew Reynolds [Tue, 6 Oct 2020 12:00:22 +0000 (07:00 -0500)]
Add arithmetic preprocess module (#5188)
This class serves a similar purpose to the strings preprocess module (https://github.com/CVC4/CVC4/blob/master/src/theory/strings/theory_strings_preprocess.h).
It can potentially be used for reducing extended arithmetic operators on demand via lemmas.
This PR does not change the current behavior, but generalizes the use of operator elimination in TheoryArith to make this possible.
Abdalrhman Mohamed [Tue, 6 Oct 2020 01:11:44 +0000 (20:11 -0500)]
Recover from some exceptions. (#5203)
This PR replaces more calls to SmtEngine functions with calls to corresponding Solver functions in command.cpp. The PR also adds CVC4_API_RECOVERABLE_CHECK macro to use for recoverable exceptions.
mudathirmahgoub [Tue, 6 Oct 2020 00:49:32 +0000 (19:49 -0500)]
Remove subtyping for sets (#5205)
Removed subtyping for sets in type_node.h
Fixes #4502, fixes #4631.
Aina Niemetz [Mon, 5 Oct 2020 23:14:10 +0000 (16:14 -0700)]
cmake: Add warning when unit testing is disabled due to assertions being disabled. (#5204)
This further fixes the testing instructions for API tests (formerly known as system tests)
in INSTALL.md.
Co-authored-by: Haniel Barbosa <hanielbbarbosa@gmail.com>
Aina Niemetz [Mon, 5 Oct 2020 22:35:23 +0000 (15:35 -0700)]
SyGuS: Add fp.sub to default FP grammar. (#5206)
Aina Niemetz [Mon, 5 Oct 2020 22:03:18 +0000 (15:03 -0700)]
Integer: GMP: Move implementation of member functions to .cpp file. (#5190)
This moves the GMP implementation of member functions of class Integer from
the header to the .cpp file. This only moves code, and adds documentation for
previously undocumented or poorly documented functions.
I ran a performance check on the cluster on non-incremental QF_BV, QF_BVFP,
QF_FP, QF_LIA, QF_LIRA and QF_LRA (BV and FP logics heavily rely on class
Integer since class BitVector is implemented on top of Integer). This change has
no impact on performance.
Andrew Reynolds [Mon, 5 Oct 2020 19:30:02 +0000 (14:30 -0500)]
Make sygus more robust to unknown responses in solution verification (#5199)
This makes it so that an "unknown" response in a CEGIS verification step causes the sygus solver to exclude the current solution and mark incomplete. Previously, the sygus solver was non-terminating in such cases, trying the same solution continously.
This also removes the option "sygusVerifySubcall", as this option should always be used. It also makes --nl-ext-tplanes enabled by default when sygus is enabled.
mudathirmahgoub [Sun, 4 Oct 2020 20:10:24 +0000 (15:10 -0500)]
Remove subtyping for sets theory (#5179)
This PR removes subtyping for sets theory due to issues like #4502, #4507 and #4631.
Changes:
Add SingletonOp for singletons to specify the type of the single element in the set.
Add mkSingleton to the solver to enable the user to pass the sort of the single element.
Update smt and cvc parsers to use mkSingleton when the kind is SINGLETON
Aina Niemetz [Sat, 3 Oct 2020 20:18:45 +0000 (13:18 -0700)]
sygus-inst: Add more special BV values. (#5191)
Mathias Preiner [Sat, 3 Oct 2020 19:39:37 +0000 (12:39 -0700)]
Fix CI builds and add cancel workflow.
Andrew Reynolds [Sat, 3 Oct 2020 19:07:16 +0000 (14:07 -0500)]
Fix theory white unit test (#5194)
Andrew Reynolds [Sat, 3 Oct 2020 11:11:02 +0000 (06:11 -0500)]
Standardization of Theory (#5181)
This cleans up various interfaces of Theory now that all theories have been updated to the new standard. This includes making check non-virtual, standardizing when trigger terms are added to equality engines, and simplifications for collectModelInfo.
Andrew Reynolds [Fri, 2 Oct 2020 23:17:53 +0000 (18:17 -0500)]
Minor simplifications to substitution map class (#5180)
This class is an important utility in preprocessing, which we are adding proof support for. This simplifies the interface of this class with regards to unused interfaces for clarity.
Andrew Reynolds [Fri, 2 Oct 2020 21:15:16 +0000 (16:15 -0500)]
(proof-new) Fixes for theory preprocessing proofs (#5171)
This fixes several subtle issues with theory preprocessing.
The main fix is to ensure proofs are correct for cases where the theory preprocessor applies either with or without theory preprocessing (calling Theory::ppRewrite on subterms) enabled, see argument doTheoryPreprocess of preprocess. If disabled, it applies term formula removal and rewriting only. This is required for processing lemmas that are marked as "do not preprocess", which is an optimization, but is also necessary since theory combination may e.g. split on equality that was solved during ppRewrite. The solution is to use 2 separate term conversion sequences for these 2 cases.
It also fixes an issue where preprocessing is term-context-sensitive: terms underneath quantifiers are treated differently. This is now handled by a new TermContext callback "InQuantTermContext".
Andrew Reynolds [Fri, 2 Oct 2020 19:55:31 +0000 (14:55 -0500)]
(proof-new) Make shared solver proof producing (#5169)
This makes the shared terms database use a proof equality engine as a layer on top of its equality engine, analogous to how this done in theories.
Gereon Kremer [Fri, 2 Oct 2020 15:25:29 +0000 (17:25 +0200)]
Allow for theory combination of strings with nonlinear real arithmetic. (#5111)
This PR makes sure that enabling strings and nonlinear real arithmetic at the same time works fine.
Right now, the configuration for strings enforces linear arithmetic if no integers are enabled, in particular for NRA.
Fixed #5109.
Andrew Reynolds [Fri, 2 Oct 2020 14:06:02 +0000 (09:06 -0500)]
Decouple modules from TheoryArithPrivate (#5184)
This decouples the arithmetic rewriter, the operator eliminator and the non-linear extension from TheoryArithPrivate and performs some minor cleanup.
This is in preparation for further refactoring of (lazy) arithmetic operator elimination.
Alex Ozdemir [Fri, 2 Oct 2020 13:03:23 +0000 (06:03 -0700)]
(proof-new) New proofs in arith::Constraint::externalExplain (#5176)
This commit threads proofs through the core of arith:
Constraint::externalExplain, which recursively explain arith literals.
One of the base cases here is asking the EE for an explanation, through
the congruence manager. To delay implementing proofs in
ArithCongruenceManager to a separate commit, we stub out proof
production in ArithCongruenceManager::explain for now.
Alex Ozdemir [Fri, 2 Oct 2020 12:26:28 +0000 (05:26 -0700)]
Remove duplicate declarations in th_bv.plf (#5183)
I think this is dead code now, but still good to fix.
Aina Niemetz [Fri, 2 Oct 2020 00:29:17 +0000 (17:29 -0700)]
SyGuS: Add min/max (sub)normal constants to FP default grammar. (#5185)
Andrew Reynolds [Thu, 1 Oct 2020 22:19:08 +0000 (17:19 -0500)]
(proof-new) Make arrays proof producing (#5112)
This includes adding a basic inference manager to arrays that ensures that the correct applications of PfRule are given to the inference manager.
Note that some calls to lemma are yet to be converted. Also note that some minor simplifications were made for unnecessary parts of the code.
Mathias Preiner [Thu, 1 Oct 2020 20:48:37 +0000 (13:48 -0700)]
Add additional ground terms to SyGuS instantiation grammar (#5167)
This PR adds options to add additional ground terms to the SyGuS instantiation grammars.
Andrew Reynolds [Thu, 1 Oct 2020 19:12:08 +0000 (14:12 -0500)]
Update theory of arithmetic to standard check (#5178)
This updates the theory of arithmetic to use the standard check callbacks (preCheck, postCheck, preNotifyFact, notifyFact). It also refactors some use of the non-linear solver which will solely live in TheoryArith.
The longer term goal is to have TheoryArithPrivate be responsible for linear arithmetic solving only, and to be treated as a black box. Eventually, the non-linear solver will be removed from this class.
This PR is required for several things, including refactoring of preprocessing and expand definitions for arithmetic (div/mod will not be eliminated eagerly). It is also required for fixing issues related to div/mod appearing in instantiations.
This is the last class to have a custom check method. Followup PR will make Theory::check non-virtual.
Aina Niemetz [Thu, 1 Oct 2020 18:29:39 +0000 (11:29 -0700)]
FloatingPoint: Add utility functions for largest and smallest normal. (#5174)
Gereon Kremer [Thu, 1 Oct 2020 16:24:55 +0000 (18:24 +0200)]
Allow to use the initial assignment for CAD (#5177)
While the CAD subsolver already provided for a way to use the linear model to seed the model search, it was not actually used yet.
This PR now does use it, though it is disabled by a Boolean flag.
Andrew Reynolds [Thu, 1 Oct 2020 15:36:14 +0000 (10:36 -0500)]
(proof-new) Preprocessing passes use proper interfaces to assertions pipeline (#5164)
This PR eliminates all uses of assertions pipeline that are not proper, which two-fold:
(1) The assertion list should never be modified in a custom way (without going through replace / push_back),
(2) Places where an assertion is "conjoined" to an existing spot in the vector should use conjoin instead of replace.
This is required for proper proof generation.
This fixes CVC4/cvc4-projects#75.
Andrew Reynolds [Thu, 1 Oct 2020 13:40:06 +0000 (08:40 -0500)]
Make SygusSolver use sygus attributes directly (#5172)
Previously, the SmtEngine was using an interface through TheoryEngine to set user attributes to indicate that e.g. a synth-fun is associated with a given grammar. Since SmtEngine and its members are internal now, this can simply be done directly via attributes. This makes it so that SygusSolver does not depend on TheoryEngine nor does it require the TheoryEngine to be initialized at the time a synth-fun is created.
Mathias Preiner [Thu, 1 Oct 2020 01:17:45 +0000 (18:17 -0700)]
Add GH action to cancel previous pending/running CI builds. (#5175)
GH introduced a new workflow event pull_request_target that now makes it
possible to cancel builds on the base repository.
Aina Niemetz [Thu, 1 Oct 2020 00:26:46 +0000 (17:26 -0700)]
BitVector: Extend interface of setBit to set it to a specific value. (#5173)
Previously, BitVector::setBit only allowed to set the bit at the given
index to 1. This changes its behavior to be also able to set it to 0.
Aina Niemetz [Wed, 30 Sep 2020 21:05:29 +0000 (14:05 -0700)]
FloatingPoint: Add utility functions for largest and smallest subnormal. (#5166)
Gereon Kremer [Wed, 30 Sep 2020 17:41:36 +0000 (19:41 +0200)]
Remove too strict assertion to allow for approximate models (#5168)
This PR simply removes an assertion that would trigger whenever the arithmetic theory asserts a model that contains something else than a constant. This can be the case with witness terms.
In offline discussion we concluded that this discussion was overly strict. Note that these examples may still hit an error during model validation (Cannot run check-model on a model with approximate values.).
This PR also fixes a debug output I found during debugging.
Fixes #5113.
Gereon Kremer [Wed, 30 Sep 2020 17:26:21 +0000 (19:26 +0200)]
Add missing includes. (#5170)
The strategy class added in #5160 was missing the proper includes for std::ostream. For some reason it works for most configurations, but triggers compilation errors in certain cases.
Gereon Kremer [Wed, 30 Sep 2020 15:39:58 +0000 (17:39 +0200)]
Add strategy for nonlinear extension (#5160)
This PR adds a flexible strategy for the nonlinear extension that replaces the handwritten code in checkLastCall().
Andrew Reynolds [Wed, 30 Sep 2020 15:06:58 +0000 (10:06 -0500)]
Dynamic allocation of equality engine for shared solver (#5152)
This updates shared solver to have dynamic allocation of equality engine, analogous to theory solvers.
Andrew Reynolds [Wed, 30 Sep 2020 13:20:03 +0000 (08:20 -0500)]
(proof-new) Add the term conversion sequence generator (#5097)
This class will be used in the theory preprocessor and is planned to be used in other preprocessing passes that can be understood as sequences of rewrite systems.
Haniel Barbosa [Tue, 29 Sep 2020 19:15:06 +0000 (16:15 -0300)]
[proof-new] Adds a proof manager for prop engine (#5162)
Also fixes some weird orderings in src/CMakeLists.txt
mudathirmahgoub [Tue, 29 Sep 2020 18:48:16 +0000 (13:48 -0500)]
Fix bags headers (#5165)
Fix bags headers
Alex Ozdemir [Tue, 29 Sep 2020 16:39:11 +0000 (09:39 -0700)]
(proof-new) Add proof managers and eager gens to arith (#5159)
This commit threads ProofNodeManager, EagerProofGenerator, etc
throughout the arith theory into the appropriate locations. These
objects are currently unused, but will be used in future commits.
Crediting Andy, since he set up some of this.
Co-authored-by: Andrew Reynolds andrew.j.reynolds@gmail.com
Andrew Reynolds [Tue, 29 Sep 2020 14:57:35 +0000 (09:57 -0500)]
(proof-new) Fixes for preprocess proof generator and proofs in assertion pipeline (#5136)
This PR makes several fixes to preprocess proof generator, making it user-context dependent and making it avoid cyclic proofs. It additionally makes assertion pipeline a new interface "conjoin" which should always be used when we conjoin a new assertion to an old position in the assertion vector. It also removes an unnecessary interface to assertion pipeline.
Next PRs will clean up the use of assertions pipeline in all preprocessing passes to use the proper interfaces. This includes removing non-constant references to assertions, which has been fixed on proof-new.
Haniel Barbosa [Tue, 29 Sep 2020 13:57:37 +0000 (10:57 -0300)]
[proof-new] Adds a proof post processor for the Prop Engine (#5161)
The post processor connects the two proofs in the prop engine: the refutation proof in the SAT solver and the CNF transformation proof in the CNF stream. The proof generators from theory engine in the latter are also expanded during the connection.
Haniel Barbosa [Tue, 29 Sep 2020 13:20:02 +0000 (10:20 -0300)]
[proof-new] Updates to proof node updater (#5156)
Haniel Barbosa [Tue, 29 Sep 2020 12:35:46 +0000 (09:35 -0300)]
[proof-new] Adds a proof-producing CNF converter (#5137)
A proof generator that wraps the original CNF stream, to be used when the prop engine is proof producing. It tracks in a lazy cdproof both the concrete clausification steps and the proof generators of the formulas being clausified (in particular, theory lemmas).
Gereon Kremer [Tue, 29 Sep 2020 12:05:46 +0000 (14:05 +0200)]
Clean up nonlinear extension (#5149)
This PR performs some cleanups in the nonlinear extension, in particular it removes the old lemma collection scheme. It is no longer needed, as all subsolvers use the inference manager.
Andrew Reynolds [Tue, 29 Sep 2020 03:56:20 +0000 (22:56 -0500)]
Reset assertions on resetAssertions (#5153)
The assertions object is currently not cleared on resetAssertions, only the prop engine is reset. This means that if a user added assertion, did not use them in a check-sat, and then called reset-assertions, they would not be removed from the assertions pipeline (storing the pending assertions before they are sent to the prop engine).
This fixes #5144.
Alex Ozdemir [Tue, 29 Sep 2020 03:14:47 +0000 (20:14 -0700)]
Add utilities for arith/proof_checker and build it (#5157)
The arith proof checker was not being built (not in cmake). Now it is. A
few dependencies were missing.
Haniel Barbosa [Tue, 29 Sep 2020 02:34:34 +0000 (23:34 -0300)]
[proof-new] Removing spurious forward declaration in CnfStream (#5155)
Haniel Barbosa [Tue, 29 Sep 2020 01:22:29 +0000 (22:22 -0300)]
[proof-new] Adds a proof node hash function (#5154)
Andrew Reynolds [Tue, 29 Sep 2020 00:54:25 +0000 (19:54 -0500)]
Disable regression that is timing out (#5142)
Seems to be timing out on 1/5 of our CI runs currently.
Andrew Reynolds [Mon, 28 Sep 2020 23:33:03 +0000 (18:33 -0500)]
Minor fixes to quantifiers proofs (#5151)
Includes minor changes to the proof checker and a fix in the instantiate module.
Haniel Barbosa [Mon, 28 Sep 2020 20:38:59 +0000 (17:38 -0300)]
[proof-new] Adds a proof manager for the SAT solver (#5140)
Tracks the refutation proof built by Minisat. See the header for extensive explanations.
This commit also adds a few dependencies for the SAT proof manager to work (making it a friend of the SAT solver, getting the cnf stream from theory proxy, having lazy cdproof chain give all the links).
mudathirmahgoub [Mon, 28 Sep 2020 13:53:07 +0000 (08:53 -0500)]
Implement bags rewriter (#5132)
This PR implements rewrite rules for bags. This PR focuses on rewrite rules for non constant nodes.
Rewriting nodes with constant children is delegated to bags::NormalForm class (future PR).
Gereon Kremer [Mon, 28 Sep 2020 11:48:26 +0000 (13:48 +0200)]
Add new arithmetic BoundInference class (#5148)
This PR adds a new utility class that extracts bounds on single variables from theory atoms like x > 0 or y <= 17. It does not perform further reasoning (like recognizing x > y with y > 3 as a bound).
Note that the functionality was introduced in arith/nl/icp/variable_bounds.h, but is now available using Node only.
This PR also replaces the VariableBounds by BoundInference in the icp solver which allowed for checking the code.
Andrew Reynolds [Sun, 27 Sep 2020 22:29:02 +0000 (17:29 -0500)]
Fix sygus quantifier elimination preprocess for multiple functions (#5130)
The option --sygus-qe-preproc performs quantifier elimination to coerce certain synthesis conjectures to be single invocation. This technique was broken when multiple synthesis functions were present. This fixes the issue and adds a regression where --sygus-qe-preproc enables a benchmark to be quickly solved.
Gereon Kremer [Sat, 26 Sep 2020 17:11:13 +0000 (19:11 +0200)]
Use inference manager for nl_solver (#5125)
This PR migrates the nl_solver part of the nonlinear extension to use the new inference manager as well.
It adds a new method clearWaitingLemmas to the inference manager and uses ArithLemma (though NlLemma exists) as we don't need the additional functionality of NlLemma.
Andrew Reynolds [Sat, 26 Sep 2020 15:07:42 +0000 (10:07 -0500)]
Connect the shared solver to theory engine (#5103)
This makes SharedSolver the main communication point for TheoryEngine during solving for combination-related solving tasks. This class is a generalization of SharedTermsDatabase, and in the distributed architecture is a wrapper around shared terms database.
It has 5 callbacks in theory engine: for preregistration, preNotifyFact (which calls addSharedTerms on theories), assertSharedEquality, explain, getEqualityStatus.
This PR has no intended behavior changes.
FYI @barrettcw
Andrew Reynolds [Sat, 26 Sep 2020 13:51:57 +0000 (08:51 -0500)]
Use original quantified formula for single invocation reconstruction (#5129)
This fixes an issue with single invocation solution reconstruction where the preprocessed quantified formula contains internal skolems, thus prohibiting reconstruction. The solution is to use the original quantified formula when doing solution reconstruction. This adds a regression demonstrating the issue.
Aina Niemetz [Sat, 26 Sep 2020 01:08:08 +0000 (18:08 -0700)]
Restrict bvxnor to only allow two operands (was n-ary). (#5138)
Bit-vector operator bvxnor was previously mistakenly marked as
left-assoicative in SMT-LIB. This has recently been corrected in
SMT-LIB. We now restrict bvxnor to only allow two operands in order to
avoid confusion about the semantics, since the behavior of n-ary
operands to bvxnor is now undefined in SMT-LIB.
Andrew Reynolds [Fri, 25 Sep 2020 18:45:38 +0000 (13:45 -0500)]
Make sygus refinement step more robust to unevaluatable counterexamples (#5102)
Currently, the CEGIS refinement loop of the sygus solver may terminate with "unknown" when a duplicate counterexample is generated. This is caused by a candidate t for a conjecture exists f. forall x. G[f, x] such that:
(1) G[t, c] evaluates to a non-constant expression,
(2) ~G[t, k] is satisfiable with model k = c.
Notice this exclusively limited to theories with incomplete functions, e.g. (non-linear) division.
In this case, we know that t is an incorrect solution, but the counterexample we found was not new.
Currently, we abort with "unknown" since the counterexample was not new. After this PR, we exclude t and continue, which is uncontroversially the correct behavior.
This PR moves the resposibility for lemma from synth engine to synth conjecture, which simplifies the behavior of the main check conjecture method.
Haniel Barbosa [Fri, 25 Sep 2020 15:24:06 +0000 (12:24 -0300)]
Cleaning and documenting cnf stream (#5134)
Moreover changes assertClause to return a bool, which is gonna be used by the proof cnf stream.
Aina Niemetz [Thu, 24 Sep 2020 22:47:41 +0000 (15:47 -0700)]
SyGuS: Add default grammar for FP. (#5133)
Andrew Reynolds [Thu, 24 Sep 2020 20:02:04 +0000 (15:02 -0500)]
Function definition fmf preprocessing pass (#5064)
This defines the function definition finite model finding as a proper preprocessing pass.
This is required for cleaning/fixing bugs in the preprocessor on proof-new.
There are no intended behavior changes in this PR, although the code for the pass was updated to the new style guidelines.
Andrew Reynolds [Thu, 24 Sep 2020 03:13:35 +0000 (22:13 -0500)]
Modify lemma vs fact policy for datatype equalities (#5115)
This changes the lemma vs fact policy for datatype equalities. Previously, datatype equalities were sent as lemmas unless they were over datatypes that were composed of datatypes only. This is now changed so that equalities that do not involve direct subterms with finite non-datatype types are kept internal.
The primary type of equality that this targets are "Instantiate" equalities, e.g. the conclusion of:
(is-cons x) => x = (cons (head x) (tail x))
These equalities have been observed to generate large amounts of new terms for many benchmarks.
With this PR, the the challenging Facebook benchmark goes from 2 min 45 sec -> 29 sec. If the instantiate rule is disabled altogether, it still correctly solves, and is faster (~14 seconds), which however is not correct in general.
This change triggered two other issues:
(1) A relations benchmark involving transitive closure now times out. This has been a common issue for the relations solver and should be revisited.
(2) A potential issue with doPendingLemmas in InferenceManagerBuffer was uncovered. In rare cases, we can be re-entrant into this method since OutputChannel::lemma may trigger further preregistration of terms, which can trigger a recursive call to doPendingLemmas in the case of datatypes, which causes a segfault due to corrupting an iterator. This PR adds a simple guard for this method.
This PR also fixes some existing issues in computing cardinality for parametric datatypes.
Andrew Reynolds [Wed, 23 Sep 2020 19:56:52 +0000 (14:56 -0500)]
Disable cegqi-bv when using sygus (#5124)
This disables the CAV 2018 techniques for BV quantifier instantiation when solving sygus since they may generate terms with witness in them. This adds a regression where this occurs.
I've opened an cvc4 projects issue to revisit this (CVC4/cvc4-projects#227).
Gereon Kremer [Wed, 23 Sep 2020 18:05:06 +0000 (20:05 +0200)]
Make IAND solver use inference manager. (#5126)
This PR moves the iand solver (within the nonlinear extension) to use the new inference manager to send lemmas.
Aina Niemetz [Wed, 23 Sep 2020 16:15:39 +0000 (09:15 -0700)]
Missing format from #5112.
yoni206 [Wed, 23 Sep 2020 13:00:59 +0000 (06:00 -0700)]
bv2int: new options for bvand translation (#5096)
Currently, (bvand x y) is translated into a sum of ITEs.
This PR introduces two more options for the translation of (bvand x y):
bv: cast the integer translations of x and y back to bit-vectors, do a bvand, and cast the result to integers.
iand: use the builtin iand operator.
These options are added to many of the tests, and some new tests are added.
In addition, some tests are cleaned up (e.g., removing --no-check-unsat-cores for satisfiable benchmarks).
Finally, some tests are moved from regress0 to regress2 because they take several seconds to complete (2 -- 10 seconds).
Andrew Reynolds [Wed, 23 Sep 2020 04:50:43 +0000 (23:50 -0500)]
Allow E-matching by default when strings are enabled (#5117)
This does not disable E-matching when strings are enabled with --strings-exp, due to potential applications where strings are combined with user-provided quantified formulas.
Notice that by default, we do not want E-matching applied to quantified formulas corresponding to reductions for extended string functions. To correct this, all quantified formulas generated by strings are marked with an "internal quantified formula" attribute, which causes E-matching to ignore them. This feature can in theory be generalized later for other internal sources of quantified formulas.
Aina Niemetz [Wed, 23 Sep 2020 04:25:07 +0000 (21:25 -0700)]
New C++ API: Catch and throw recoverable exception. (#5122)
This allows to distinguish recoverable from non-recoverable exceptions,
and recover if possible.
Aina Niemetz [Wed, 23 Sep 2020 03:46:17 +0000 (20:46 -0700)]
FP: Use Assert instead of AlwaysAssert in traits::(pre|post)condition. (#5121)
For the same reason as in #5119.
Abdalrhman Mohamed [Wed, 23 Sep 2020 03:12:17 +0000 (22:12 -0500)]
Refactor Commands to use the Public API. (#5105)
This is work towards eliminating the Expr layer. This PR does the following:
Replace Expr/Type with Term/Sort in the API for commands.
Remove the command export functionality which is not supported.
Since many commands now call the Solver functions instead of the SmtEngine ones, their behavior may be a slightly different. For example, (get-unsat-assumptions) now only works in incremental mode. In some cases, CVC4 will not recover from non-fatal errors.
Andrew Reynolds [Wed, 23 Sep 2020 01:06:42 +0000 (20:06 -0500)]
Fix type issue with term formula removal (#5107)
We currently are using lookups with uint32_t but storing with int32_t. Somehow the compilers don't complain, but I noticed this was mismatched.
Andres Noetzli [Wed, 23 Sep 2020 00:41:09 +0000 (17:41 -0700)]
[Python API] Conversion to/from Unicode strings (#5120)
Fixes #5024. This commit adds a conversion from constant string terms to
native Python Unicode strings in Term.toPythonObj() and improves
Solver.mkString() to accept strings containing characters outside of
the printable range.
Aina Niemetz [Tue, 22 Sep 2020 23:15:54 +0000 (16:15 -0700)]
FP: Use Assert instead of PRECONDITION macro in converter. (#5119)
The FP converter (= word blaster) uses a PRECONDITION macro that is
defined in symFPU (if included) and calls traits::precondition. This is
a problem for two reasons. First, traits::precondition calls
AlwaysAssert, and PRECONDITION is called for every word-blasted node, so
this can be expensive. Second, in case of an assertion failure, we get
very generic failure messages, that don't allow to distinguish between
failures and are absolutely non-descriptive:
Check failure
b
This fixes both issues.
@martin-cs
Mathias Preiner [Tue, 22 Sep 2020 22:40:48 +0000 (15:40 -0700)]
Add simple BV solver (#5065)
This PR adds a simple BV solver that sends bit-blasting lemmas to the internal MiniSat.
mudathirmahgoub [Tue, 22 Sep 2020 21:59:41 +0000 (16:59 -0500)]
Add skeleton for theory of bags (multisets) (#5100)
This PR adds initial headers and mostly empty source files for the theory of bags (multisets).
It acts as a basis for future commits.
It includes straightforward implementation for typing rules an enumerator for bags.
Andres Noetzli [Tue, 22 Sep 2020 19:13:33 +0000 (12:13 -0700)]
Fix compilation without LibPoly (#5118)
Commit
e969318 introduced the ICP-based
solver for nonlinear arithmetic. That code, however, depends on LibPoly.
When configuring CVC4 without LibPoly, the code doesn't compile because
the class ICPSolver is missing. This commit adds a dummy version if
ICPSolver to remedy the issue.
makaimann [Tue, 22 Sep 2020 18:58:03 +0000 (11:58 -0700)]
Add method to get Python object from constant value term in Python API (#5083)
This PR addresses issue https://github.com/CVC4/CVC4/issues/5014. It simply interprets the SMT-LIB string representation and produces a Python object. It currently supports booleans, ints, reals, bit-vectors, and arrays. The method (`toPythonObj`) is only valid to call if `isConst` returns true.
Mathias Preiner [Tue, 22 Sep 2020 16:51:56 +0000 (09:51 -0700)]
Update copyright header script to support CMake and Python files (#5067)
This PR updates the update-copyright.pl script to also update/add copyright headers to CMake specific files. It further fixes a small typo in the header.
Gereon Kremer [Tue, 22 Sep 2020 15:49:46 +0000 (17:49 +0200)]
ICP-based solver for nonlinear arithmetic (#5017)
This PR adds a new icp-based solver to be integrated into the nonlinear extension.
It is not meant to be used as a stand-alone ICP solver. It does not implement splits (only propagations) and implements a rather aggressive budget mechanism that aims to quickly stop propagation to allow other solvers to take over. Additionally, it enforces a maximum bit size to avoid divergence.