cvc5.git
5 years agofix ex_bv.plf (#2905)
Haniel Barbosa [Thu, 28 Mar 2019 23:30:50 +0000 (18:30 -0500)]
fix ex_bv.plf (#2905)

5 years agoUpdate copyright headers.
Aina Niemetz [Tue, 26 Mar 2019 18:33:55 +0000 (11:33 -0700)]
Update copyright headers.

5 years agoupdate-copyright: Update to 2019.
Aina Niemetz [Tue, 26 Mar 2019 18:11:56 +0000 (11:11 -0700)]
update-copyright: Update to 2019.

5 years agoget-authors: Exclude empty lines.
Mathias Preiner [Tue, 26 Mar 2019 18:22:21 +0000 (11:22 -0700)]
get-authors: Exclude empty lines.

5 years agoFix warnings about wrong line numbers (#2899)
Andres Noetzli [Tue, 26 Mar 2019 15:28:09 +0000 (08:28 -0700)]
Fix warnings about wrong line numbers (#2899)

5 years agoFix a few warnings (#2898)
Andrew Reynolds [Tue, 26 Mar 2019 15:03:29 +0000 (10:03 -0500)]
Fix a few warnings (#2898)

5 years agoget-authors: Exclude common source code patterns. (#2900)
Mathias Preiner [Tue, 26 Mar 2019 01:19:45 +0000 (18:19 -0700)]
get-authors: Exclude common source code patterns. (#2900)

Exclude lines that #include header files and define namespaces.
Since we use git blame -C -M to determine the current top contributors,
git tries to match all #include and namespace definitions to an original
author, which is not accurate since these lines are usually not
copied over from other files.

5 years agoupdate-copyright: Fix matching of excluded paths.
Aina Niemetz [Mon, 25 Mar 2019 19:31:59 +0000 (12:31 -0700)]
update-copyright: Fix matching of excluded paths.

5 years agoget-authors: Readd option -C to git blame command.
Aina Niemetz [Mon, 25 Mar 2019 18:39:17 +0000 (11:39 -0700)]
get-authors: Readd option -C to git blame command.

5 years ago Split regular expression solver (#2891)
Andrew Reynolds [Sun, 24 Mar 2019 19:26:25 +0000 (14:26 -0500)]
 Split regular expression solver (#2891)

5 years agoNew C++ API: Fix include. (#2896)
Aina Niemetz [Sun, 24 Mar 2019 18:46:36 +0000 (11:46 -0700)]
New C++ API: Fix include. (#2896)

5 years agoBV: Fix typerules for rotate operators. (#2895)
Aina Niemetz [Sun, 24 Mar 2019 05:58:31 +0000 (22:58 -0700)]
BV: Fix typerules for rotate operators. (#2895)

5 years agoFix memory leak when using subsolvers (#2893)
Andres Noetzli [Sat, 23 Mar 2019 20:30:35 +0000 (13:30 -0700)]
Fix memory leak when using subsolvers (#2893)

ASAN was reporting memory leaks in regression tests that were using
subsolvers. First, I am going to describe the origin of the leaks and
then the solution implemented in this commit.

Recall an `Expr` stores the `NodeManager` that the internal node is
associated with. `Node::toExpr()` converts a `Node` to an `Expr` and
assumes that the active `NodeManager` (returned by
`NodeManager::currentNM()` is the one associated with the node. In
`ExportPrivate::exportInternal()`, when we were exporting a skolem, we
created a skolem in the target `NodeManager` by calling
`NodeManager::mkSkolem()` (`ExprManager`s do not support the creation of
skolems) but then we called `Node::toExpr()` on the resulting skolem
while the origin `NodeManager` was the active `NodeManager`. One of the
issues of having the wrong `NodeManager` in the `Expr` is that when the
`Expr` is destroyed and the internal node's refcount reaches zero in
destructor of `Expr`, then the node value associated with the node is
added to the set of zombie nodes (nodes waiting to be garbage collected
or resurrected) of the wrong `NodeManager`. The problem here is that the
set of zombie nodes uses the node id to hash and compare nodes. Node
ids, however, are only unique within a given `NodeManager`. Thus, if we
have two nodes with the same id from different `NodeManager`s and both
reach refcount zero in the context of the same `NodeManager`, only one
of them will end up in the set of zombies and thus only that one will be
freed.
Using a subsolver realiably triggered this issue.
`ExportPrivate::exportInternal()` stored the `Expr` with the wrong
`NodeManager` in an `ExprManagerMapCollection` which associates
variables in the original `ExprManager` with the variables in the target
`ExprManager`. When we created a subsolver, we created the
`ExprManagerMapCollection` before creating our subsolver, so it was
deleted after the subsolver and so deleting the
`ExprManagerMapCollection` deleted the last reference to `Expr`s holding
skolem nodes associated with the wrong `NodeManager`.

This commit fixes the issue by making sure that the correct
`NodeManager` is in scope when converting the skolem/bound variable
nodes to an `Expr`. It also swaps the creation order of
`ExprManagerMapCollection` and `ExprManager` to make sure that
`ExprManagerMapCollection` is deleted before the `ExprManager` that the
`Expr`s belong to. Additionally, the commit makes it harder to make a
similar mistake by asserting that the `Expr`s in the
`ExprManagerMapCollection` are associated with the expected
`ExprManager`s. Finally, it adds an assertion that tries to identify
such issues by checking whether the list of zombies contains a node with
the same id but located at a different address.

5 years agoStrip non-matching beginning from indexof operator (#2885)
Andres Noetzli [Sat, 23 Mar 2019 00:15:53 +0000 (00:15 +0000)]
Strip non-matching beginning from indexof operator (#2885)

This commit adds a rewrite that strips endpoints from `str.indexof`
operators if they don't overlap with the string that is being searched
for using `stripConstantEndpoints()`. In addition to that, it makes
`stripConstantEndpoints()` slightly more aggressive by allowing it to
drop substring components that have zero overlap with the string that we
are looking at. Finally, the commit fixes the default argument for
`fullRewriter` of `checkEntailContains()` to be true instead of false,
which should allow for more rewriting opportunities.

5 years agoRevisit strings extended function decomposition (#2892)
Andrew Reynolds [Fri, 22 Mar 2019 21:24:05 +0000 (16:24 -0500)]
Revisit strings extended function decomposition  (#2892)

5 years agoFix instantiation stat for fmf (#2889)
Andrew Reynolds [Fri, 22 Mar 2019 20:28:50 +0000 (15:28 -0500)]
Fix instantiation stat for fmf (#2889)

5 years agoMore fixes for PBE with datatypes (#2882)
Andrew Reynolds [Fri, 22 Mar 2019 14:01:13 +0000 (09:01 -0500)]
More fixes for PBE with datatypes (#2882)

5 years agofix help information on TPTP parsing (#2884)
Haniel Barbosa [Fri, 22 Mar 2019 06:11:06 +0000 (01:11 -0500)]
fix help information on TPTP parsing (#2884)

5 years agoFix stripConstantEndpoints in strings rewriter (#2883)
Andres Noetzli [Fri, 22 Mar 2019 03:48:56 +0000 (03:48 +0000)]
Fix stripConstantEndpoints in strings rewriter (#2883)

`TheoryStringsRewriter::stripConstantEndpoints()` returns the stripped
endpoints in the vectors `nb` and `ne`. These endpoints were not
computed correctly if string literal had to be split. For example:

```
stripConstantEndpoints({ "ABC" }, { "C" }, {}, {}, 1)
```

returned `true` and only "A" for `nb` (instead of "AB") because we
mistakenly used the amount of overlap between "ABC" and "C" (which is
one) for the length of the stripped prefix.

This commit fixes the issue and adds several unit tests.

5 years agoUse empty vector instead of false in query with null Expr assumption (#2876)
makaimann [Fri, 22 Mar 2019 01:10:01 +0000 (18:10 -0700)]
Use empty vector instead of false in query with null Expr assumption (#2876)

This solution is less confusing than using a `false` assumption.

5 years ago Fix bad comparison in RE solver's addMembership (#2880)
Andrew Reynolds [Thu, 21 Mar 2019 19:21:39 +0000 (14:21 -0500)]
 Fix bad comparison in RE solver's addMembership (#2880)

5 years agoRewrite selectors correctly applied to constructors (#2875)
Andrew Reynolds [Thu, 21 Mar 2019 18:41:46 +0000 (13:41 -0500)]
Rewrite selectors correctly applied to constructors (#2875)

5 years agoAdd more NEWS (#2859)
Andres Noetzli [Thu, 21 Mar 2019 17:21:02 +0000 (17:21 +0000)]
Add more NEWS (#2859)

5 years agoSygus abduction feature (#2744)
Andrew Reynolds [Wed, 20 Mar 2019 01:54:40 +0000 (20:54 -0500)]
Sygus abduction feature (#2744)

5 years agoMake declare-datatype(s) a standard, non-extended command in the Smt2 parser. (#2874)
Andrew Reynolds [Tue, 19 Mar 2019 19:15:24 +0000 (14:15 -0500)]
Make declare-datatype(s) a standard, non-extended command in the Smt2 parser. (#2874)

5 years agoFix fairness issue with fast sygus enumerator (#2873)
Andrew Reynolds [Tue, 19 Mar 2019 16:51:11 +0000 (11:51 -0500)]
Fix fairness issue with fast sygus enumerator (#2873)

5 years agoNew C++: Remove redundant mkBoundVar function.
Aina Niemetz [Mon, 18 Mar 2019 22:58:43 +0000 (15:58 -0700)]
New C++: Remove redundant mkBoundVar function.

5 years agoNew C++: Remove redundant mkVar function.
Aina Niemetz [Mon, 18 Mar 2019 22:05:00 +0000 (15:05 -0700)]
New C++: Remove redundant mkVar function.

s

5 years agoBitVector: Allow base 10 in constructor. (#2870)
Aina Niemetz [Mon, 18 Mar 2019 23:07:03 +0000 (16:07 -0700)]
BitVector: Allow base 10 in constructor. (#2870)

5 years agoLimit --solve-int-as-bv=X to QF_NIA/QF_LIA/QF_IDL (#2868)
Andres Noetzli [Sat, 16 Mar 2019 06:23:06 +0000 (06:23 +0000)]
Limit --solve-int-as-bv=X to QF_NIA/QF_LIA/QF_IDL (#2868)

Fixes #1715. We do not support the `--solve-int-as-bv=X` preprocessing
pass with logics other than pure QF_NIA/QF_LIA/QF_IDL. This commit adds
a corresponding check and throws an option exception if an incompatible
logic has been set.

5 years agoEnable CryptoMiniSat-backed BV proofs (#2847)
Alex Ozdemir [Sat, 16 Mar 2019 01:51:47 +0000 (18:51 -0700)]
Enable CryptoMiniSat-backed BV proofs (#2847)

* Connect the plumbing so that BV proofs are enabled when using
CryptoMiniSat
* Also fixed a bug in CNF-proof generation
   * Specifically, CNF proofs broke when proving tautological clauses.
     Now they don't.

5 years agoNew beta-reduction for HOL solving (#2869)
Haniel Barbosa [Fri, 15 Mar 2019 23:35:43 +0000 (18:35 -0500)]
New beta-reduction for HOL solving (#2869)

5 years agoAdding capture avoiding substitution (#2867)
Haniel Barbosa [Fri, 15 Mar 2019 22:01:42 +0000 (17:01 -0500)]
Adding capture avoiding substitution (#2867)

5 years agoFix non-variable function head elimination in UF. (#2864)
Andrew Reynolds [Fri, 15 Mar 2019 02:33:07 +0000 (21:33 -0500)]
Fix non-variable function head elimination in UF. (#2864)

5 years agoFix function term set for theory strings compute care graph. (#2862)
Andrew Reynolds [Thu, 14 Mar 2019 22:51:39 +0000 (17:51 -0500)]
Fix function term set for theory strings compute care graph. (#2862)

5 years agoImprove INSTALL instructions. (#2866)
Aina Niemetz [Thu, 14 Mar 2019 22:17:31 +0000 (15:17 -0700)]
Improve INSTALL instructions. (#2866)

5 years agoUse zero slope tangent planes for transcendental functions (#2803)
Andrew Reynolds [Thu, 14 Mar 2019 21:32:25 +0000 (16:32 -0500)]
Use zero slope tangent planes for transcendental functions (#2803)

5 years agoProperly handle lambdas in relevant domain (#2853)
Andrew Reynolds [Thu, 14 Mar 2019 20:47:48 +0000 (15:47 -0500)]
Properly handle lambdas in relevant domain (#2853)

5 years ago Add getFreeVariables method to node algorithm (#2852)
Andrew Reynolds [Thu, 14 Mar 2019 20:13:55 +0000 (15:13 -0500)]
 Add getFreeVariables method to node algorithm (#2852)

5 years agoDisable DCO signing for organization members.
Mathias Preiner [Thu, 14 Mar 2019 19:45:49 +0000 (12:45 -0700)]
Disable DCO signing for organization members.

5 years agoImplement proper semantics for TPTP predicate is_rat. (#2861)
Andrew Reynolds [Thu, 14 Mar 2019 19:06:48 +0000 (14:06 -0500)]
Implement proper semantics for TPTP predicate is_rat. (#2861)

5 years ago Fix substitution step in ho matching (#2825)
Andrew Reynolds [Thu, 14 Mar 2019 18:36:56 +0000 (13:36 -0500)]
 Fix substitution step in ho matching (#2825)

5 years agoGeneralize sygus-rr-verify for fast enumerator (#2829)
Andrew Reynolds [Thu, 14 Mar 2019 12:46:52 +0000 (07:46 -0500)]
Generalize sygus-rr-verify for fast enumerator (#2829)

5 years agocheck for null assumption in query and replace with false (#2858)
makaimann [Thu, 14 Mar 2019 07:08:15 +0000 (00:08 -0700)]
check for null assumption in query and replace with false (#2858)

The default assumption argument in query was a null `Expr`, but the implementation asserted that the assumption is not null:

declaration: https://github.com/CVC4/CVC4/blob/68174dedcb4bf9d91241585ab1cc876d2fa83d62/src/smt/smt_engine.h#L593
implementation: https://github.com/CVC4/CVC4/blob/68174dedcb4bf9d91241585ab1cc876d2fa83d62/src/smt/smt_engine.cpp#L3548

The change is to simply check if the assumption is null and replaces it with the `false` expression if it is.

It should be `false` not `true` because it is negated in checkSatisfiability (when it's a query) as seen here: https://github.com/CVC4/CVC4/blob/68174dedcb4bf9d91241585ab1cc876d2fa83d62/src/smt/smt_engine.cpp#L3607

Note: I couldn't find a clean way to make `false` the default argument of assumption, because the expression manager is non-static.

5 years agoAdd statistics for proof gen./checking time, size (#2850)
Andres Noetzli [Wed, 13 Mar 2019 22:47:04 +0000 (22:47 +0000)]
Add statistics for proof gen./checking time, size (#2850)

This commit adds a statistic that records the total size of all proofs
generated by an instance of `SmtEngine`. The commit also moves
`SmtEngine::checkProof()` into `smt_engine.cpp` because it needs to know
the complete type of `d_stats` (and the separate file for that method
didn't seem that useful). Additionally, it changes
`smt::SmtEngine::checkProofTime` to `smt::SmtEngine::lfscCheckProofTime`
that only measures the time spent in LFSC and adds a statistic
`proof::ProofManager::proofProductionTime` that measures the proof
production time separately (also works with `get-proof`/`--dump-proof`).

5 years agoRemove spurious data member. (#2857)
Andrew Reynolds [Wed, 13 Mar 2019 16:37:03 +0000 (11:37 -0500)]
Remove spurious data member. (#2857)

5 years agoFix public headers for make install. (#2856)
Mathias Preiner [Wed, 13 Mar 2019 03:09:35 +0000 (20:09 -0700)]
Fix public headers for make install. (#2856)

This commit fixes make install, which previously copied all public header files to ${CMAKE_INSTALL_PREFIX}/ instead of ${CMAKE_INSTALL_PREFIX}/cvc4.
Further, the old build system modified all #include directives in the installed public header files to use the installed headers, e.g., #include "cvc4_public.h" was changed to #include <cvc4/cvc4_public.h>. Now, after make install the script src/fix-install-headers.sh is executed to change the #include directives accordingly (this should be obsolete with the new C++ API).

5 years agoAdd option --sygus-rr-synth-rec for considering all grammar types recursively (#2270)
Andrew Reynolds [Tue, 12 Mar 2019 20:18:30 +0000 (15:18 -0500)]
Add option --sygus-rr-synth-rec for considering all grammar types recursively (#2270)

5 years ago Move tuple/record update elimination from ppRewrite to expandDefinition (#2839)
Andrew Reynolds [Tue, 12 Mar 2019 19:43:42 +0000 (14:43 -0500)]
 Move tuple/record update elimination from ppRewrite to expandDefinition (#2839)

5 years agoErProof class with LFSC output (#2812)
Alex Ozdemir [Fri, 1 Mar 2019 05:54:08 +0000 (21:54 -0800)]
ErProof class with LFSC output (#2812)

* ErProof class with LFSC output

* Created a TraceCheckProof class
   * parsable from text
* Created an ErProof class
   * constructible from a TraceCheckProof
   * writable as LFSC
* A bunch of unit tests

* Reponded to Mathias's first set of comments.

Credits to Mathias for many of the fixes!

* Responed to Andres's first set, fixed tests

I accidentally deleted a "!" last time, causing stuff to fail.

* Use Configuration::isAssertionBuild

* Clarified comment

* Responded to Andres's 2nd review

* Gaurding against a memory error.
* Renaming a file.
* Aggressively unlinking temporary files.

5 years agoUse string stream for proofs instead of tmp files (#2841)
Andres Noetzli [Wed, 27 Feb 2019 00:49:59 +0000 (00:49 +0000)]
Use string stream for proofs instead of tmp files (#2841)

This commit changes CVC4 to use a string stream instead of a temporary
files for proof checking. Note: This change requires a version of LFSC
that supports checking streams (see
https://github.com/CVC4/LFSC/pull/14).

Tested: `make check` passed, changing `holds` to `xholds` in the proof
produced by proof_manager.cpp makes the proofs fail.

5 years agoClangFormat: Disable DerivePointerAlignment (#2842)
Andres Noetzli [Tue, 26 Feb 2019 22:46:04 +0000 (22:46 +0000)]
ClangFormat: Disable DerivePointerAlignment (#2842)

The option `DerivePointerAlignment` tries to automatically determine the
pointer alignment used by the input. In our case, we would eventually
like the code base to be consistent throughtout, so this commit disables
that option.

5 years agoNew C++ API: Remove redundant declareFun function. (#2837)
Aina Niemetz [Wed, 13 Feb 2019 20:52:17 +0000 (12:52 -0800)]
New C++ API: Remove redundant declareFun function. (#2837)

5 years agoRewrite simple regexp pattern to str.contains (#2827)
Andres Noetzli [Wed, 13 Feb 2019 20:18:09 +0000 (12:18 -0800)]
Rewrite simple regexp pattern to str.contains (#2827)

5 years agoNew C++ API: Remove redundant mkTerm function. (#2836)
Aina Niemetz [Wed, 13 Feb 2019 04:16:24 +0000 (20:16 -0800)]
New C++ API: Remove redundant mkTerm function. (#2836)

5 years agoDelete temporary proof files when aborting CVC4 (#2834)
Andres Noetzli [Tue, 12 Feb 2019 19:30:59 +0000 (11:30 -0800)]
Delete temporary proof files when aborting CVC4 (#2834)

CVC4 was not deleting temporary proof files when crashing or being
terminated externally. This commit uses an early `unlink()` to remove
the files as soon as CVC4 terminates.

5 years agoNew C++ API: Unit tests for declare* functions. (#2831)
Aina Niemetz [Mon, 11 Feb 2019 17:04:54 +0000 (09:04 -0800)]
New C++ API: Unit tests for declare* functions. (#2831)

5 years agoMake stripConstantEndpoints() less aggressive (#2830)
Andres Noetzli [Tue, 5 Feb 2019 18:09:15 +0000 (10:09 -0800)]
Make stripConstantEndpoints() less aggressive (#2830)

5 years agoAdd rewrite for contains + const strings replace (#2828)
Andres Noetzli [Mon, 4 Feb 2019 00:17:37 +0000 (16:17 -0800)]
Add rewrite for contains + const strings replace (#2828)

5 years agoFix corner case in stripConstantEndpoints (#2824)
Andres Noetzli [Sat, 2 Feb 2019 08:36:42 +0000 (00:36 -0800)]
Fix corner case in stripConstantEndpoints (#2824)

`stripConstantEndpoints()` was returning `true` when the first argument
was a list only containing an empty string, which could lead to rewrite
loops. This commit checks for that case and adds a unit test for it.

5 years agoFix warning due to catching polymorphic exceptions (#2821)
Andres Noetzli [Tue, 29 Jan 2019 22:05:47 +0000 (14:05 -0800)]
Fix warning due to catching polymorphic exceptions (#2821)

5 years agoNew C++ API: Fix checks for mkTerm. (#2820)
Aina Niemetz [Tue, 29 Jan 2019 19:47:04 +0000 (11:47 -0800)]
New C++ API: Fix checks for mkTerm. (#2820)

This required fixing the OpTerm handling for mkTerm functions in the API.

5 years agoStrings: Remove redundant replace rewrite (#2822)
Andres Noetzli [Tue, 29 Jan 2019 18:17:06 +0000 (10:17 -0800)]
Strings: Remove redundant replace rewrite (#2822)

Pulling the first constant string from a replace if there is no overlap
with the search term is subsumed by the rewrite using
`stripConstantEndpoints()`.

5 years agoExtended DRAT signature to operational DRAT (#2815)
Alex Ozdemir [Thu, 24 Jan 2019 19:45:12 +0000 (11:45 -0800)]
Extended DRAT signature to operational DRAT (#2815)

* Extended DRAT signature to operational DRAT

The DRAT signature now supports both operational and specified DRAT.
That is, either kind of proof will be accepted.

The goal of this implementation of operational DRAT was to re-use as
much of the specified DRAT machinery as possible. However, by writing a
separate operational signature, we could make it much more efficient
(after all, operational DRAT came about because of a push for efficient
cheking).

You can run the new AND old DRAT tests by running

```
lfscc sat.plf smt.plf lrat.plf drat.plf drat_test.plf
```

* Apply suggestions from code review (Yoni)

Co-Authored-By: alex-ozdemir <aozdemir@hmc.edu>
5 years agoAvoid using ProofManager in non-proof CMS build (#2814)
Andres Noetzli [Wed, 23 Jan 2019 18:08:11 +0000 (10:08 -0800)]
Avoid using ProofManager in non-proof CMS build (#2814)

PR #2786 changed `CryptoMinisatSolver::addClause()` to register clauses
with the bit-vector proof if proofs are turned on. The new code
requested the `ProofManager` even when proofs were turned off, which
made the `eager-inc-cryptominisat.smt2` regression and our nightlies
fail. This commit guards the access to the `ProofManager`, restoring the
semantics of the original code when proofs are turned off.

5 years agoStrings: Strengthen multiset reasoning (#2817)
Andres Noetzli [Wed, 23 Jan 2019 02:47:08 +0000 (18:47 -0800)]
Strings: Strengthen multiset reasoning (#2817)

This commit introduces three helper methods for performing multiset
reasoning: an entailment check whether a term is always a strict subset
of another term in the multiset domain (`checkEntailMultisetSubset()`),
a check whether a string term is always homogeneous
(`checkEntailHomogeneousString()`), and an overapproximation for the
multiset domain (`getMultisetApproximation()`). It also adds unit tests
related to multiset reasoning.

5 years ago Fix tuple and record CVC printing (#2818)
Andrew Reynolds [Tue, 22 Jan 2019 21:48:48 +0000 (15:48 -0600)]
 Fix tuple and record CVC printing (#2818)

5 years ago Fix parsing of overloaded parametric datatype selectors (#2819)
Andrew Reynolds [Tue, 22 Jan 2019 20:43:17 +0000 (14:43 -0600)]
 Fix parsing of overloaded parametric datatype selectors (#2819)

5 years agoNew README (markdown). (#2797)
Aina Niemetz [Tue, 22 Jan 2019 18:55:13 +0000 (10:55 -0800)]
New README (markdown). (#2797)

5 years agoFix missing-override warning (#2811)
Andres Noetzli [Sat, 19 Jan 2019 11:34:43 +0000 (03:34 -0800)]
Fix missing-override warning (#2811)

`TLazyBitblaster::setProofLog()` was defined even though the method was
not virtual before PR #2808 and `TBitblaster` was implementing the same
method. After that PR, which made the method virtual, GCC complained
about a missing `override` keyword for `setProofLog()`. However, the
method should have been removed (see
[comment](https://github.com/CVC4/CVC4/pull/2786#discussion_r247299617)).
This commit removes the function definition.

5 years agoExtract DIMACS Printing (#2800)
Alex Ozdemir [Fri, 18 Jan 2019 19:10:26 +0000 (11:10 -0800)]
Extract DIMACS Printing (#2800)

Creating LRAT proofs reuqires writing SAT problems in the DIMACS format.
Before this code was in the LRAT class.

However, since creating ER proofs will also require writing DIMACS, I
decided to extract it.

At the same time I realized that my prior representation of used clauses
was unnecessarily poor. I had chosen it to align with
`CnfProof::collectAtomsForClauses`, but the format is really bad (it
requires extra allocations & manual memory management), and I discovered
that the aforementioned method is super simple, so I'm moving to a
better format.

5 years agoStrings: Introduce checkEntailContains() (#2809)
Andres Noetzli [Fri, 18 Jan 2019 13:59:09 +0000 (05:59 -0800)]
Strings: Introduce checkEntailContains() (#2809)

5 years ago Fix ABC build (#2808)
Andres Noetzli [Fri, 18 Jan 2019 08:43:53 +0000 (00:43 -0800)]
 Fix ABC build (#2808)

PR #2786 introduced a pure virtual method `TBitblaster::getSatSolver()`.
`AigBitblaster` was missing the implementation of that method. This
commit adds an implementation that simply returns the underlying SAT
solver. Note: The method is currently only used for proofs and CVC4 does
not support proofs in combination with ABC. To make this explicit, the
commit also adds a check in `SmtEngine::setDefaults()` that makes sure
that we are not trying to produce proofs with `--bitblast-aig` (before
the commit, we just crashed with an assertion failure/null pointer
dereference).

5 years agoAdd option to print BV constants in binary (#2805)
Andres Noetzli [Thu, 17 Jan 2019 00:38:38 +0000 (16:38 -0800)]
Add option to print BV constants in binary (#2805)

This commit adds the option `--bv-print-consts-in-binary` to print
bit-vector constants in binary, e.g. `#b0001`, instead of decimal, e.g.
`(_ bv1 4)`). The option is on by default to match the behavior of Z3
and Boolector.

5 years agoUpdate NEWS file (#2804)
Andres Noetzli [Wed, 16 Jan 2019 20:27:05 +0000 (12:27 -0800)]
Update NEWS file (#2804)

5 years agoBugfix: LFSC clause equality (#2801)
Alex Ozdemir [Wed, 16 Jan 2019 17:52:42 +0000 (09:52 -0800)]
Bugfix: LFSC clause equality (#2801)

* Bugfix: LFSC clause equality

My implementation of clause equality had an undocumented assumption that
the clauses didn't have any duplicate literals. Now that assumption is
gone, and the tests suite has been expanded.

* Added an empty clause test

* Typo fix: Yoni

Co-Authored-By: alex-ozdemir <aozdemir@hmc.edu>
* Address Yoni's comments

* Remove a duplicate clause_eq test.
* Add an ordering clause_eq test.
* Improve the documentation of clause_eq.

5 years agoExtended Resolution Signature (#2788)
Alex Ozdemir [Wed, 16 Jan 2019 07:55:29 +0000 (23:55 -0800)]
Extended Resolution Signature (#2788)

* Extended Resolution Signature

While extended resolution is a fairly general technique, the paper
"Extended Resolution Simulates DRAT" / the drat2er uses exactly one new
type of rule: definitions of the form

    new <=> old v (~l_1 ^ ~l_2 ^ ... ^ ~l_n)

This PR adds axioms supporting this kind of definition, and adds a test
making use of those new axioms. The axioms support the following ideas:

   1. Introducing a **fresh** variable, defined in the form above
   2. Clausifying that definition to produce proofs of $$ n + 2 $$ new
      clauses in the form of two clauses, and a cnf with $$ n $$ clauses
   3. An axiom for unrolling the proof of the cnf into proofs of the
      original clauses.

* Addressing Yoni's comments

1. Added a new (trivial) test
2. Improved a bunch of documentation

* Update proofs/signatures/er.plf

Co-Authored-By: alex-ozdemir <aozdemir@hmc.edu>
* Removed references to RATs from the signature

There are still a few references in the header comment.

* Aside on continuations

* Scrap the elision annotations

5 years agoFix constant contains ITOS rewrite (#2799)
Andrew Reynolds [Wed, 16 Jan 2019 05:15:27 +0000 (23:15 -0600)]
Fix constant contains ITOS rewrite (#2799)

5 years agoCMake: Fix search for static libraries (#2798)
Andres Noetzli [Wed, 16 Jan 2019 03:14:06 +0000 (19:14 -0800)]
CMake: Fix search for static libraries (#2798)

When configuring CVC4 with `--static`, we change
`CMAKE_FIND_LIBRARY_SUFFIXES` to prefer static libraries (`*.a`) over
shared ones. However, instead of prepending `.a` to the list of
`CMAKE_FIND_LIBRARY_SUFFIXES`, we created a single element with `.a` and
the previous list.

Output of `message("${CMAKE_FIND_LIBRARY_SUFFIXES}")` before the change:

```
.a .tbd;.dylib;.so;.a
```

After the change:

```
.a;.tbd;.dylib;.so;.a
```

On macOS, both the static and the shared library of GMP are available
(when installed via homebrew) and before the change, CMake would pick the
shared library when compiling with `--static --no-static-binary`. This
commit fixes that issue.

5 years agoStrings: Add option to change loop process mode (#2794)
Andres Noetzli [Tue, 15 Jan 2019 18:28:47 +0000 (10:28 -0800)]
Strings: Add option to change loop process mode (#2794)

This commit adds an option `--strings-process-loop-mode` that allows
finer-grained control over CVC4 processes looping word equation. In
particular, performing normal loop breaking sometimes leads to worse
performance. The "simple" mode disables that inference.

5 years ago Fix unsound double abs rewrite rule for FP (#2792)
Andrew Reynolds [Tue, 15 Jan 2019 16:54:02 +0000 (10:54 -0600)]
 Fix unsound double abs rewrite rule for FP (#2792)

5 years ago Only check disequal terms with sygus-rr-verify (#2793)
Andrew Reynolds [Tue, 15 Jan 2019 01:12:59 +0000 (19:12 -0600)]
 Only check disequal terms with sygus-rr-verify (#2793)

5 years agoClausalBitvectorProof (#2786)
Alex Ozdemir [Mon, 14 Jan 2019 18:53:31 +0000 (10:53 -0800)]
ClausalBitvectorProof (#2786)

* [DRAT] ClausalBitvectorProof

Created a class, `ClausalBitvectorProof`, which represents a bitvector
proof of UNSAT using an underlying clausal technique (DRAT, LRAT, etc)

It fits into the `BitvectorProof` class hierarchy like this:

```
              BitvectorProof
              /            \
             /              \
ClausalBitvectorProof  ResolutionBitvectorProof
```

This change is a painful one because all of the following BV subsystems
referenced ResolutionBitvectorProof (subsequently RBVP) or
BitvectorProof (subsequently BVP):
   * CnfStream
   * SatSolver (specifically the BvSatSolver)
   * CnfProof
   * TheoryProof
   * TheoryBV
   * Both bitblasters

And in particular, ResolutionBitvectorProof, the CnfStream, and the
SatSolvers were tightly coupled.

This means that references to and interactions with (R)BVP were
pervasive.

Nevertheless, an SMT developer must persist.

The change summary:
  * Create a subclass of BVP, called ClausalBitvectorProof, which has
    most methods stubbed out.
  * Make a some modifications to BVP and ResolutionBitvectorProof as the
    natural division of labor between the different classes becomes
    clear.
  * Go through all the components in the first list and try to figure
    out which kind of BVP they should **actually** be interacting with,
    and how. Make tweaks accordingly.
  * Add a hook from CryptoMinisat which pipes the produced DRAT proof
    into the new ClausalBitvectorProof.
  * Add a debug statement to ClausalBitvectorProof which parses and
    prints that DRAT proof, for testing purposes.

Test:
  * `make check` to verify that we didn't break any old stuff, including
    lazy BB, and eager BB when using bvminisat.
  * `cvc4 --dump-proofs --bv-sat-solver=cryptominisat --bitblast=eager
  -d bv::clausal test/regress/regress0/bv/ackermann2.smt2`, and see that
     1. It crashed with "Unimplemented"
     2. Right before that it prints out the (textual) DRAT proof.

* Remove 2 unneeded methods

* Missed a rename

* Typos

Thanks Andres!

Co-Authored-By: alex-ozdemir <aozdemir@hmc.edu>
* Address Andres comments

* Reorder members of TBitblaster

5 years agoLFSC LRAT Output (#2787)
Alex Ozdemir [Sun, 13 Jan 2019 21:21:24 +0000 (13:21 -0800)]
LFSC LRAT Output (#2787)

* LFSC ouput & unit test

* Renamed lrat unit test file

* s/DRAT/LRAT/

Thanks Andres!

Co-Authored-By: alex-ozdemir <aozdemir@hmc.edu>
* Addressed Andres' comments

1. Extracted a filter whitespace function.
2. Added @param annotations.

* Addressing Yoni's comments

Tweaked the test method name for LRAT output as LFSC
Added assertions for verifying that clause index lists are sorted during
LFSC LRAT output.

5 years agoLratInstruction inheritance (#2784)
Alex Ozdemir [Sat, 12 Jan 2019 00:04:56 +0000 (16:04 -0800)]
LratInstruction inheritance (#2784)

While implementing and testing LRAT proof output as LFSC, I discovered
that my implementation of LratInstruction as a tagged union was subtly
broken for reasons related to move/copy assignment/constructors.

While I could have figured out how to fix it, I decided to stop fighting
the system and use inheritance.

This PR will be followed by one using the inheritance-based
LratInstruction to implement output to LFSC.

5 years agoFixed linking against drat2er, and use drat2er (#2785)
Alex Ozdemir [Fri, 11 Jan 2019 20:48:13 +0000 (12:48 -0800)]
Fixed linking against drat2er, and use drat2er (#2785)

* Fixed linking against drat2er/drat-trim

We have machinery for linking against drat2er. However, this machinery
didn't quite work because libdrat2er.a contains an (undefined) reference
to `run_drat_trim` from libdrat-trim.a.

Thus, when linking against libdrat2er.a, we also need to link against
libdrat-trim.a.

I made this change, and then tested it by actually calling a function
from the drat2er library (CheckAndConvertToLRAT) which relies on
`run_drat_trim`. Since this invocation compiles, we know that the
linking is working properly now.

* Combined the two libs, per Mathias

* drat2er configured gaurds

5 years agoNew C++ API: Add unit tests for setInfo, setLogic, setOption. (#2782)
Aina Niemetz [Fri, 11 Jan 2019 20:06:03 +0000 (12:06 -0800)]
New C++ API: Add unit tests for setInfo, setLogic, setOption. (#2782)

5 years agoNew C++ API: Get rid of mkConst functions (simplify API). (#2783)
Aina Niemetz [Thu, 10 Jan 2019 18:47:53 +0000 (10:47 -0800)]
New C++ API: Get rid of mkConst functions (simplify API). (#2783)

5 years agoDo not rewrite 1-constructor sygus testers to true (#2780)
Andrew Reynolds [Wed, 9 Jan 2019 21:39:07 +0000 (15:39 -0600)]
Do not rewrite 1-constructor sygus testers to true (#2780)

5 years ago[BV Proofs] Option for proof format (#2777)
Alex Ozdemir [Wed, 9 Jan 2019 18:19:22 +0000 (19:19 +0100)]
[BV Proofs] Option for proof format (#2777)

We're building out a system whereby (eager) BV proofs can be emitted in
one of three formats. Let's add an option for specifying which!

My testing mechanism was not very thorough: I verified that I could specify each of the following option values:
* `er`
* `lrat`
* `drat`
* `help`

and that I could not provide random other option values.

5 years agoClause proof printing (#2779)
Alex Ozdemir [Wed, 9 Jan 2019 08:18:29 +0000 (09:18 +0100)]
Clause proof printing (#2779)

* Print LFSC proofs of CNF formulas

* Unit Test for clause printing

* Added SAT input proof printing unit test

* Fixed cnf_holds reference. Proofs of CMap_holds

There were references to clauses_hold, which should have been references
to cnf_holds.

Also added a function for printing a value of type CMap_holds, and a
test for this function.

5 years agoLFSC drat output (#2776)
Alex Ozdemir [Wed, 9 Jan 2019 07:29:12 +0000 (08:29 +0100)]
LFSC drat output (#2776)

* LFSC drat output

* Addressed Mathias' review

Addressing Mathias' review with the following changes:
* Added a few blank lines
* Added a unit test for LRAT output as LFSC

5 years agoNew C++ API: Add missing getType() calls to kick off type checking. (#2773)
Aina Niemetz [Mon, 7 Jan 2019 17:02:02 +0000 (09:02 -0800)]
New C++ API: Add missing getType() calls to kick off type checking. (#2773)

5 years ago[DRAT] DRAT data structure (#2767)
Alex Ozdemir [Sun, 6 Jan 2019 18:32:42 +0000 (19:32 +0100)]
[DRAT] DRAT data structure  (#2767)

* Copied old DRAT data-structure files.

Next step: clean up the code, and adapt them to our current usage plans.

* Polished the DRAT class.

Notably, removed the idea of lazy-parsing, this is now just a DRAT
wrapper class.

More explicit about whether methods handle binary or text.

Better constructor patterns

* Added implementation of textual DRAT output

* reordered the DratInstruction structure.
* removed the public modifier from the above struct
* removed the operator << implementation for DratInstruction

* use emplace_back

* Addressing Yoni's first review

* Extracted "write literal in DIMACS format" idea as a function
* Replaced some spurious Debug streams with `os`. (they were left over
from an earlier refactor)
* Improved some documentation

* Removed aside about std::string

* Addressed Mathias' comments

Specifically
* SCREAMING_SNAKE_CASED enum variants.
* Extracted some common logic from two branches of a conditional.
* Cleaned out some undefined behavior from bit manipulation.

* Unit tests for binary DRAT parsing

* Added text output test

* s/white/black/ derp

5 years agocmake: Disable unit tests for static builds. (#2775)
Mathias Preiner [Sat, 5 Jan 2019 04:21:10 +0000 (20:21 -0800)]
cmake: Disable unit tests for static builds. (#2775)

--static now implies --no-unit-testing.

Fixes #2672.

5 years agoC++ API: Fix OOB read in unit test (#2774)
Andres Noetzli [Fri, 4 Jan 2019 21:26:08 +0000 (13:26 -0800)]
C++ API: Fix OOB read in unit test (#2774)

There were two typos in the unit tests that caused OOB accesses. Instead
of doing `d_solver.mkConst(CONST_BITVECTOR, std::string("101"), 6)`, the
closing parenthesis was in the wrong place resulting in
`std::string("101", 6)`. The second argument to `std::string(const
char*, size_t)` says how many characters to copy and results in
undefined behavior if the number is greater than the length of the
string, thus the OOB access. The commit fixes the typo and removes one
of the tests because it should not actually fail (16 is an accepted
base).

5 years ago[LRAT] A C++ data structure for LRAT. (#2737)
Alex Ozdemir [Fri, 4 Jan 2019 08:57:27 +0000 (09:57 +0100)]
[LRAT] A C++ data structure for LRAT. (#2737)

* [LRAT] A C++ data structure for LRAT.

Added a data structure for storing (abstract) LRAT proofs.

The constructor will take a drat binary proof and convert it to LRAT
using drat-trim. However, this is unimplemented in this PR.

Subsequent PRs will add:
   * LFSC representation of LRAT
   * Bitvector Proofs based on LRAT
   * Enabled tests for those proofs

* Documenting LRAT constructors

* Apply suggestions from code review

Co-Authored-By: alex-ozdemir <aozdemir@hmc.edu>
* Responding to Andres' review

Consisting of
   * Naming nits
   * Closed fds
   * Better implementation of disjoint union for LratInstruction
   * DRAT -> LRAT conversion is no longer an LratProof constructor

* include reorder

* Update src/proof/lrat/lrat_proof.h

Co-Authored-By: alex-ozdemir <aozdemir@hmc.edu>
* Addressed Andres' comments

* ANonymous namespaces and name resolution?

* Remove inlines, fix i negation

Thanks Andres!

* Use `std::abs`

Credit to Andres

Co-Authored-By: alex-ozdemir <aozdemir@hmc.edu>
* Remove uneeded public

5 years agoNew C++ API: Add missing catch blocks for std::invalid_argument. (#2772)
Aina Niemetz [Fri, 4 Jan 2019 03:29:43 +0000 (19:29 -0800)]
New C++ API: Add missing catch blocks for std::invalid_argument. (#2772)

5 years agoAPI/Smt2 parser: refactor termAtomic (#2674)
Andres Noetzli [Thu, 3 Jan 2019 22:48:18 +0000 (14:48 -0800)]
API/Smt2 parser: refactor termAtomic (#2674)

5 years agoC++ API: Reintroduce zero-value mkBitVector method (#2770)
Andres Noetzli [Thu, 3 Jan 2019 16:55:45 +0000 (17:55 +0100)]
C++ API: Reintroduce zero-value mkBitVector method (#2770)

PR #2764 removed `Solver::mkBitVector(uint32_t)` (returns a bit-vector
of a given size with value zero), which made the build fail when SymFPU
was enabled because solver_black used it for SymFPU-enabled builds. This
commit simply adds a zero default argument to `mkBitVector(uint32_t,
uint64_t)` to allow users to create zero-valued bit-vectors without
explicitly specifying the value again. Additionally, the commit replaces
the use of the `CVC4_USE_SYMFPU` macro by a call to
`Configuration::isBuiltWithSymFPU()`, making sure that we can catch
compile-time errors regardless of configuration. Finally,
`Solver::mkConst(Kind, uint32_t, uint32_t, Term)` now checks whether
CVC4 has been compiled with SymFPU when creating a `CONST_FLOATINGPOINT`
and throws an exception otherwise (solver_black has been updated
correspondingly).