New InferenceIds for BV theory (#5909)

This PR introduces new InferenceId for the BV theory and uses them instead of InferenceId::UNKNOWN.

Document UF inferences (#5917)

Document UF entries of InferenceId enum.

Eliminate non-static members in term util (#5919)

This makes it so that TermUtil is now a collection of static methods. Further refactoring will make this a standalone file of utility methods.

This breaks all dependencies on the TermUtil object in QuantifiersEngine. It also starts breaking some of the depenendencies on quantifiers engine in sygus.

Move first order model for full model check to own file (#5918)

This moves the derived model class used in finite model finding to its own file, in the src/theory/quantifiers/fmf directory.

Updates the code to meet guidelines, no behavior changes.

Move methods from term util to quantifiers registry (#5916)

Towards eliminating dependencies on quantifiers engine, and eliminating the TermUtil class.

Note that QuantifiersModule had to be moved to its own file to avoid circular include dependencies.

Compute fact or lemma in datatypes prior to buffering (#5914)

This is necessary for the planned refactoring of TheoryInference::process. This forces datatypes to decide lemma vs. fact prior to buffering inferences.

Use InferenceId in sep theory. (#5912)

This PR uses the new InferenceIds in the separation logic theory.

TheoryIds for UF theory. (#5901)

This PR introduces new InferenceId for the uf theory and uses them instead of InferenceId::UNKNOWN.

Add InferenceIds for theory of arrays (#5910)

This PR introduces new InferenceIds for the theory of arrays and uses them instead of InferenceId::UNKNOWN.

Add InferenceId to buffered inference manager (#5911)

This PR collects the InferenceId in the InferenceManagerBuffered class.

Add new IntegralHistogramStat (#5898)

This PR adds a new statistics class that improves on HistogramStat if we know that the type is integral (also supporting enums).
Instead of using a comparably slow std::map like HistogramStat, IntegralHistogramStat uses a std::vector that is resized appropriately.
The integral values are simply cast to std::int64_t and used as indices into the vector.

Add bit-level propagation support to BV bitblast solver. (#5906)

This commit adds support for bit-level propagation for the BV bitblast solver to quickly detect conflicts on effort levels != FULL. Bit-level propagation for the bitblast solver is by default disabled for now. Further, bit-blasting of facts is now handled more lazily with a bit-blast queue.

google test: parser: Migrate parser_builder_black. (#5896)

Remove now obsolete sendLemmas and inferences stat from arith::nl (#5903)

This PR removes some obsolete code from the nonlinear solver.
The statistics will soon be replaced by a generic statistic in the theory inference manager.

Moving methods from quantifiers engine to quantifiers state (#5881)

Towards eliminating dependencies on quantifiers engine.

Properly set up equality engine for BV bitblast solver. (#5905)

Theory BV now sets up the default equality engine for BV solvers that do not use their own equality engine like e.g. the BV bitblast solver. This commit also adds the missing equality engine pieces to the BV bitblast solver (getEqualityStatus, explain).

Simplify and fix decision engine's handling of skolem definitions (#5888)

This PR changes the front end of prop engine to distinguish input formulas from skolem definitions, which is required by the decision engine. This PR breaks the dependency of PropEngine on the AssertionsPipeline, as now the determining of whether an input formula is a skolem definition is handled externally, in SmtSolver.

With this PR, we should not be required to satisfy skolem definitions that are not relevant based on the techniques already implemented in the decision engine. Currently, we are not distinguishing input formulas from skolem definitions properly, meaning we assert more literals than we need to.

This also simplifies related interfaces within decision engine.

We should test this PR with --decision=justification on SMT-LIB.

(proof-new) Option to not automatically consider symmetry in CDProof (#5895)

There are compelling use cases not to automatically introduce SYMM steps in CDProof, e.g. in CDProofs used within ProofNodeUpdater for external conversions.

google test: parser: Migrate parser_black. (#5886)

Make most methods of TheoryInferenceManager expect an InferenceId. (#5897)

This PR makes most methods of the TheoryInferenceManager expect an InferenceId.
All classes that inherit from TheoryInferenceManager are adapted accordingly and InferenceIds are passed everywhere.
In some cases, there are no appropriate InferenceIds yet. We use InferenceId::UNKNOWN for the time being and introduce proper values in future PRs.
The InferenceIds are not yet used, but will be used for statistics and debug output.

Add InferenceId member to TheoryInference, adapt all derived classes. (#5894)

This PR adds a new InferenceId member to the TheoryInference class.
All classes derived from TheoryInference are adapted accordingly.

[proof-new] Adding a proof-producing ensure literal method (#5889)

The ensureLiteral method in CnfStream may apply CNF conversion to the given literal (for example if it's an IFF), which needs to be recorded in the proof. This commit adds a proof-producing ensureLiteral to ProofCnfStream, which is called by the prop engine if proofs are enabled.

This commit also simplifies the interfaces on ensureLit and convertAtom by removing the preRegistration flag, which was never used.

Merge InferenceIds into one enum (#5892)

This PR is the first step in consolidating the various variants of Inferences, InferenceIds and InferenceManagers of the theories.
It merges all InferencedIds into one global enum and makes all theories use them.

Fix spurious assertion failure in regexp normalization (#5852)

Fixes #5816.

Simplify interface for preprocessor (#5890)

This does a minor simplification to the interface for preprocessor. It has a postProcess call that is called after another unrelated call at the SmtSolver level (notifyPreprocessedAssertions) is made. This makes it so that Preprocessor::postProcess is inlined as the last step of process.

Refactor term registration visitors (#5875)

This refactors the term registration visitors (PreRegisterVisitor and SharedTermsVisitor), which are responsible for calling Theory::preRegisterTerm and Theory::addSharedTerm.

The purpose of this PR is to resolve a subtle bug in the implementation of PreRegisterVisitor (see explanation below), and to improve performance in particular on the Facebook benchmarks (where preregistering terms is currently 25-35% of runtime on certain challenge benchmarks).

This PR makes it so that that SharedTermsVisitor now subsumes PreRegisterVisitor and should be run when sharing is enabled only. Previously, we ran both PreRegisterVisitor and SharedTermsVisitor, and moreover the former misclassified when a literal had multiple theories since the d_theories field of PreRegisterVisitor is never reset. This meant we would consider a literal to have multiple theories as soon as we saw any literal that had multipleTheories. After this PR, we run SharedTermsVisitor only which also handles calling preRegisterTerm, since it has the ability to anyways (it computes the same information as PreRegisterVisitor regarding which theories care about a term).

The refactoring merges the blocks of code that were copy and pasted in term_registration_visitor.cpp and makes them more optimal, by reducing our calls to Theory::theoryOf.

FYI @barrettcw

Fix open proof for factoring lemma (#5885)

We need to add to the current proof, regardless of whether we have used the factor skolem previously.

Fixes bugs found by @HanielB on SMT-LIB runs.

Simplify method for inferring proxy lemmas in strings (#5789)

This PR simplifies our heuristic for inferring when an explanation for a strings lemma can be minimized based on proxy variable definitions. In particular, we do not turn solved equalities for proxy variables into substitutions. This aspect of the heuristic is incompatible with the new eager solver work, and moreover is buggy since substitutions should not be applied within string terms. The latter was leading the incorrect models on the 2 issues fixed by this PR.

Current results on the eager solver on SMT-LIB shows this change has very little performance impact.

Fixes #5692, fixes #5610.

Remove track instantiations infrastructure (#5883)

This was used in the old method for unsat core tracking for instantiation lemmas, which will soon be subsumed.

This is also work towards eliminating the dependencies on quantifiers engine from Instantiate.

Optimize get skolems method (#5876)

This method is used to determine which skolems have definitions according to term formula removal. This optimizes the method using attributes similar to how expr::getFreeVariables works.

It will be used heavily for SAT relevancy. We should also consider updating the justification heuristic to use this method.

Do not traverse quantifiers in term formula removal (#5859)

Our current policy for term formula removal leaves quantifier bodies unchanged. This simplifies the code based on this observation.

cmake: Make Python3 default and improve toml error messages. (#5884)

./configure.sh will now fail if Python3 is not installed on the system. Since Python2 is now deprecated the user has to explicitly enable it via --python2. This commit also removes the --python3 configure flag.

Eliminating dependencies from inst utils (#5882)

Towards eliminating dependence on QuantifierEngine from inst_match_trie.

Make term database optionally SAT-context-dependent (#5877)

This makes the terms registered to the term database (those considered by E-matching) optionally stored in a SAT-context-dependent manner. The motivation is to have a more flexible/fine-grained set of terms considered by E-matching, e.g. if preregistration becomes lazier in the future.

This uncovered 2 issues:

The induction techniques in "conjecture generator" were using private interfaces, this PR removes the friend relaionship and cleans the code
The conflict-based instantiation module was accessing the signature tables for BOUND_VARIABLES when an operator of an APPLY_UF was a BOUND_VARIABLE. This is possible when options::ufHo is enabled. This makes conflict-based instantiation skip such terms.

google test: expr: Migrate node_manager_black. (#5857)

google test: main: Migrate interactive_shell_black. (#5878)

google test: expr: Migrate type_cardinality_black. (#5871)

google test: expr: Migrate node_self_iterator_black. (#5865)

[quantifiers] Fix prenex computation (#5879)

Previously our prenex computation could generate quantifiers of the form forall x y y. F, which would lead to an assertion failure in getFreeVariablesScope, as it assumes that no shadowing occurs. This commit makes the prenex computation take a set rather than a vector, thus avoiding duplications of prenexed variables. It also changes mkForall to take a constant vector, since it does not modify the given vector.

Fixes #5693

google test: expr: Migrate type_node_white. (#5872)

Use quantifiers inference manager for lemma management (#5867)

Towards eliminating dependencies on quantifiers engine.

This replaces the custom implementation of lemma management in quantifiers engine with the standard one.

It makes a few minor changes to the standard inference manager classes to ensure the same behavior for quantifiers.

Note that some minor changes in behavior are introduced in this PR, such as being more consistent about caching/rewriting lemmas. This should not have any major impact.

Fix disequality between seq.unit terms (#5880)

This adds a missing inference for disequality between seq.unit terms, which was not handled previously.

Fixes #5666.

google test: expr: Migrate node_white. (#5869)

Fix dumping of assertions for monolithic preprocessing passes (#5866)

Previously we were unable to dump assertions in ProcessAssertions::apply for the definition-expansion, simplify and repeat-simplify passes.

Remove support for inst closure (#5874)

This was a feature implemented for "Deciding Local Theory Extensions via E-matching" CAV 2015 that is not used anymore, and will be a burden to maintain further with potential changes to term database.

It also simplifies the TermDatabase::addTerm method (which changed indentation).

Use consistent names for fixtures in unit tests. (#5863)

google test: expr: Migrate node_traversal_black. (#5868)

Avoid spurious traversal of terms during preregistration (#5860)

This simplifies a few places in the code which unecessarily traverse terms during preregistration (which already traverses terms).

Do not combine theories if theory engine needs check (#5861)

In rare cases, theory combination would be run when theory engine still needs check. This was limited to cases where the output channel is used but no lemmas were sent (TheoryEngine::needCheck() vs. d_lemmasAdded).

This led to problems in the theory of sets, which does not run a full effort check if theory engine needs check (since it knows it will be called to check again). However, running theory combination in these cases is not safe since theory of sets computes information pertaining to the care graph during its full effort check. Running theory combination otherwise would lead to theory of sets using stale data, leading to crashes due to terms not appearing in the equality engine.

This fixes #4124 (which appears not to trigger on master anyways currently).

This bug has also appeared on my sat relevancy development branch, hence fixing on master.

google test: expr: Migrate symbol_table_black. (#5870)

Minor cleaning of quantifiers engine (#5858)

This member is currently unused.

google test: expr: Migrate node_manager_white. (#5864)

Remove obsolete include from node_black unit test. (#5862)

google test: expr: Migrate node_builder_black. (#5855)

Miscellaneous cleaning in theory engine (#5854)

This statistic is unused, I believe it is leftover from deleted code.

Adding an option to optimize polite combination for datatypes (#5856)

This PR makes the optimization introduced in bbca987 optional.

Introduce quantifiers registry utility (#5829)

This is a simple module for determining which quantifiers module has ownership of quantified formulas.

This is work towards eliminating dependencies of quantifiers modules.

Note that quantifiers attributes module (which no longer has a dependency on QuantifiersEngine after this PR) will be embedded into this module in a later PR.

Clarifying documentation of `--static-binary` (#5844)

The documentation regarding --static-binary is improved.

Eliminate equality query dependence on quantifiers engine (#5831)

This class will be renamed "RepSelector" on a future PR. It no longer needs to depend on quantifiers engine and can be initialized after the modules it depends on.

[proof-new] Catch trivial cycles in SAT proof generation (#5853)

Evaluating the proof infrastructure in SMT-LIB has uncovered a rare
case (i.e., not previously in our regressions!!) in which we generate
a trivial cycle during SAT proof generation, which can lead to
problematic cycles when expanding MACRO_RESOLUTION steps. For example,
we can go from

       l1 v l2   ~l1 v l3   ~l2 v l3
(ok) ------------------------------
                  l3
in which l3 = l1 v l2, to

         l1 v l2   ~l1 v l3   ~l2 v l3
(bad) ------------------------------
               l3 v l3
              ---------
                 l3
This commit now catches the trivial cycle before it's generated.

Add BV solver bitblast. (#5851)

This PR adds a new bit-blasting BV solver, which can be enabled via --bv-solver=bitblast. The new bit-blast solver can be used instead of the lazy BV solver and currently supports CaDiCaL and CryptoMiniSat as SAT back end.

[proof-new] Fix MACRO_RESOLUTION expansion for singleton clause corner case (#5850)

Evaluating the proof infrastructure in SMT-LIB has uncovered a rare case (i.e., not previously in our regressions!!) in which the resulting clause from crowding literal elimination is a singleton. This commit makes the expansion code robust to that and adds an example of a problematic benchmark as a regression.

Also improves a bit tracing and some comments.

(proof-new) Miscellaneous fixes and regressions (#5841)

(proof-new) Refactor theory preprocessing (#5835)

This simplifies our algorithm for theory preprocessing. The motivation is two-fold:
(1) Proofs are currently incorrect in rare cases due to incorrectly tracking pre vs post rewrites.
(2) We can avoid traversing Boolean connectives with term formula removal. Note that this PR relies on the observation that term formula removal leaves Boolean structure unchanged and can apply locally to theory atoms.

Furthermore, notice that our handling of lemmas generated by term formula removal is now more uniform. In the second algorithm, term formula removal is not applied to fixed point anymore. In other words, we do not remove skolems from lemmas generated by term formula removal recursively. Instead, since lemmas are theory-preprocessed recursively, we use the fixed point that runs outside the above algorithm instead of relying on the inner fixed point in term formula removal.

This PR resolves several open issues with proof production on proof-new.

I will performance test this change on SMT-LIB.

Remove quantifiers regression from decision folder (#5830)

This is a duplicate of https://github.com/CVC4/CVC4/blob/master/test/regress/regress1/quantifiers/symmetric_unsat_7.smt2 and moreover is slow on proof-new.

Cleanup some includes (#5847)

In particular, theory_engine.h is included many places spuriously.

A few blocks of code changed indentation, updated to guidelines.

Improvements for NL traces (#5846)

This makes it so that -t nl-ext is a concise summary of what the nl-ext solver is doing, which I use frequently for debugging.

This is a temporary solution, we should consider a deeper refactoring of traces throughout NL at some point.

[proof-new] Fix bug in expansion of MACRO_RESOLUTION (#5845)

Evaluating the proof infrastructure in SMT-LIB has uncovered a rare case (i.e., not previously in our regressions!!) in which a crowding literal occurs in an OR node that represents a single-literal clause subsequent to the last clause that includes the crowding literal. This was leading to the clause that eliminates the crowding literal not being found. The commit fixes this issue by excluding single-literal clauses from those that can introduce crowding literals (which was already marked as necessary but not properly enforced).

Eliminate PREPROCESS lemma property (#5827)

This is now possible since we always preprocess lemmas.

Note that the LemmaProperty on inferences may be redundant throughout the non-linear solver now.

Simplify alpha equivalence module (#5839)

This class uses a discrimination tree which can compute subsumption as well as alpha-equivalence. This class was initially designed to also support subsumption. However, we were only using this class for alpha-equivalence and hence (canonized) Node comparison suffices and the class can be simplified. It also makes minor cosmetic updates to the module.

If we plan to support subsumption checking later, we will write a new module, and use this class https://github.com/CVC4/CVC4/blob/master/src/expr/match_trie.h which is a more mature version of the class deleted by this PR.

Note: I verified that the new and old implementation was equivalent using a temporary AlwaysAssert.

Avoid calling the printers while converting sexpr to string. (#5842)

This PR modifies sexprToString to use Term::getString to get string constants instead of Term::toString, which depends on the output language. The previous behavior caused CVC4 to crash when AST is picked as the output language.

Fix BagsRewriter::rewriteUnionDisjoint (#5840)

This PR fixes the implementation of (union_disjoint (union_max A B) (intersection_min A B)) =(union_disjoint A B).
It also skips processed bags during model building.

Fix unguarded call to get representative (#5838)

Introduced in 3234db4.
Fixes #5837, that benchmark is now unknown.
Adds an SMT-LIB benchmark that also crashes.

[proof-new] Connecting new unsat cores (#5834)

Allows one to generate unsat cores from the new proof infrastructure. For new this is controlled by a new option, --check-unsat-cores-new.

Add bag inferences for operators: intersection, duplicate_removal, and empty bags (#5832)

This PR adds inferences for operators: intersection, duplicate_removal, and empty bags during post check.
It also fixes a bug in SolverState::getElements

(proof-new) Distinguish pre vs post rewrites in term conversion proof generator (#5833)

This is work towards resolving two kinds of failures on proof-new:

(1) Functional issues with proofs from the rewriter, in particular when a term pre-rewrites and post-rewrites to different things,
(2) Conversion issues in theory-preprocessing, where all steps are assumed to be post-rewrites but some are in fact pre-rewrites. This leads to the term conversion proof generator proving something different than what is expected.

A followup PR will simplify and fix proofs for theory-preprocessing.

Reorganize calls to quantifiers engine from SmtEngine layer (#5828)

This reorganizes calls to QuantifiersEngine from SmtEngine. Our policy has changed recently that the SmtEngine layer is allowed to make calls directly to QuantifiersEngine, which eliminates the need for TheoryEngine to have forwarding calls. This PR makes this policy more consistent.

This also makes quantifier-specific calls more safe by throwing modal exceptions in the cases where quantifiers are present.

Marking "major" since we currently segfault when e.g. dumping instantiations in non-quantified logics. This PR makes it so that we throw a modal exception.

Remove regex header from cvc4cpp.cpp (#5826)

This PR replaces the heavy hammer std::regex_match for checking numbers with string operations

Simplify lemma interface (#5819)

This makes it so that TheoryEngine::lemma returns void not LemmaStatus.

Currently, there was only one use of LemmaStatus by theory solvers, which was CEGQI using it as a way of getting the preprocessed form of a lemma. This makes it so that there is an explicit method in Valuation for getting the preprocessed form of a term + its skolems and their definition assertions.

It also simplifies a few things, e.g. Valuation calls are forwarded to PropEngine instead of going through TheoryEngine. It fixes a few issues in TermFormulaRemoval related to getSkolems.

Use standard equality engine information in quantifiers state (#5824)

This refactors quantifiers so that it uses the standard interfaces for setting up an equality engine and using it via TheoryState.

This eliminates the need for several special interfaces including getMasterEqualityEngine, CombinationEngine::getCoreEqualityEngine, and most uses of EqualityQuery.

Always theory-preprocess lemmas (#5817)

This PR makes it so that theory-preprocessing is always called on lemmas. It simplifies the proof production in the theory preprocessor accordingly.

Additionally, it ensures that our theory-preprocessor is run on lemmas that are generated from term formula removal. Previously, this was not the case and in fact certain lemmas (e.g. literals within witness terms that are not in preprocessed form) would escape and be asserted to TheoryEngine. This was uncovered by a unit test failure, the corresponding regression is added in this PR.

It adds a new interface removeItes to PropEngine which is required for the (deprecated) preprocessing pass removeItes.

This PR now makes the lemma propery PREPROCESS obsolete. Further simplification is possible after this PR in non-linear arithmetic and quantifiers, where it is not necessary to distinguish 2 caches for preprocessed vs. non-preprocessed lemmas.

Add option for whether to filter candidate rewrite pairs (#5825)

This option should be disabled for the new sygus reconstruction algorithm on #5779.

Split pattern term selector from trigger (#5811)

This separates the utilities for selecting pattern terms from the Trigger class itself. This includes a PatternTermSelector, which implements the techniques for selecting the pool of pattern terms, and TriggerTermInfo which contains basic information about pattern terms.

It makes minor refactoring to make the PatternTermSelector class more than just static methods, e.g. it is now a configurable object that selects pattern terms. This makes some of the methods take fewer arguments.

More refactoring is possible, to be addressed on future PRs.

(proof-new) Improvements to quantifiers engine and instantiate interfaces (#5814)

This makes printing instantiations done at the SmtEngine level instead of deeply embedded within the Instantiate module. This provides much better flexibility for future uses of instantiations (e.g. how they are minimized in the new proof infrastructure).

Note this PR breaks the functionality that instantiations are minimized based on the old unsat cores infrastructure (see the disabled regression). This will be fixed once proof-new is fully merged.

Thread proofs through arith channels & similar (#5818)

Thread proofs through conflict/lemma storages & channels in TheoryArithPrivate

d_acTmp
d_approxCuts
lemma output channel
conflict output channel

Use term canonizer utility locally in quantifiers (#5823)

Term canonization was used in two places, which are unrelated and don't need to share the instance.
Also removes a few unnecessary methods from QuantifiersEngine.

Use standard conflict mechanism in quantifiers state (#5822)

Work towards eliminating dependencies on quantifiers engine, this updates quantifiers module to use the standard SAT-context dependent flag in quantifiers state instead of the one in QuantifiersEngine. It also eliminates the use of a custom call to theoryEngineNeedsCheck.

Introduce quantifiers inference manager (#5821)

This is the second prerequisite for eliminating dependencies on quantifiers engine. This PR threads a quantifiers inference manager through all modules in quantifiers that add lemmas.

The code for adding lemmas in quantifiers engine will be migrated to this class.

Remove deprecated quantifiers modules (#5820)

Refactor quantifiers engine initialization (#5813)

This is a step towards breaking up the quantifiers engine.

The key change is that QuantifiersEngine will not be passed as a pointer to the modules it contains. This PR makes it so that necessary modules take a QuantifiersState, which will eventually be extended as needed with additional query methods. For now, modules will take both until the dependencies on QuantifersEngine are removed.

This required that QuantifiersEngine now lives in TheoryQuantifiers, instead of in TheoryEngine, since the QuantifiersEngine must be initialized with QuantifiersState, which is a member of TheoryQuantifiers. Now, TheoryEngine retrieves the QuantifiersEngine from TheoryQuantifiers prior to finishing initialization on theories.

Reestablishing support for define-sort (#5810)

Presumable broken since 3ed42d7ab. This extends the API to have a substitute method for Sort that in needed for doing the Sort substitution in the case of define-sort.

This fixes issue #5809.

Add proofs to TheoryArithPrivate::propagate (#5812)

Specifically, add proofs to conflicts between (a) a propagation from the
congruence manager and (b) a constraint from the main solver.

Refactor bags::SolverState (#5783)

Couple of changes:

SolverState now keep tracks of elements per bag instead of per type.
bags::InferInfo now stores multiple conclusions (conjuncts).
BagSolver applies upward/downward closures for bag elements

Ensure uses of ground terms in triggers are preprocessed and registered (#5808)

This ensures ground terms in triggers are preprocessed and registered in the master equality engine. This avoids cases where our E-matching algorithm is incomplete where it should not be.

Positive impact (+222-69) on SMT-LIB, 30 second timeout

Split inst match generator into multiple files (#5805)

No code changes on this PR, only move + format.

Split E-matching strategies to own files (#5807)

Code move + format only

rename InferInfo::d_newSkolem to InferInfo::d_skolems (#5799)

Rename strings::InferInfo::d_newSkolem to InferInfo::d_skolems to match bags::InferInfo:d_skolems

 Initial cleaning of e-matching instantiation strategy (#5796)

In preparation for splitting this into multiple files.

No behavior changes in this PR.

Initial cleaning of triggers (#5795)

In preparation for splitting trigger.h/cpp into multiple files.

This updates the code to conform to guidelines. No major changes, apart from a heuristic related to "pure theory triggers" is deleted and simplified.

Initial cleaning of inst match generator (#5794)

In preparation towards breaking this file up into multiple files.

No code changes, only updates to conform to new guidelines.