1
2 /*
3 * File Inference.hpp.
4 *
5 * This file is part of the source code of the software program
6 * Vampire. It is protected by applicable
7 * copyright laws.
8 *
9 * This source code is distributed under the licence found here
10 * https://vprover.github.io/license.html
11 * and in the source directory
12 *
13 * In summary, you are allowed to use Vampire for non-commercial
14 * purposes but not allowed to distribute, modify, copy, create derivatives,
15 * or use in competitions.
16 * For other uses of Vampire please contact developers for a different
17 * licence, which we will make an effort to provide.
18 */
19 /**
20 * @file Inference.hpp
21 * Defines class Inference for various kinds of inference
22 *
23 * @since 10/05/2007 Manchester
24 */
25
26 #ifndef __Inference__
27 #define __Inference__
28
29 #include <cstdlib>
30
31 #include "Lib/Allocator.hpp"
32 #include "Lib/VString.hpp"
33 #include "Forwards.hpp"
34
35 #include <type_traits>
36
37 using namespace std;
38 using namespace Lib;
39
40 namespace Kernel {
41
42 /** Kind of input. The integers should not be changed, they are used in
43 * Compare. */
44 enum class UnitInputType : unsigned char {
45 /** Axiom or derives from axioms */
46 AXIOM = 0,
47 /** Assumption or derives from axioms and assumptions */
48 ASSUMPTION = 1,
49 /** derives from the goal */
50 CONJECTURE = 2,
51 /** negated conjecture */
52 NEGATED_CONJECTURE = 3,
53 /** Vampire-only, for the consequence-finding mode */
54 CLAIM = 4,
55 /** Used in parsing and preprocessing for extensionality clause tagging, should not appear in proof search */
56 EXTENSIONALITY_AXIOM = 5,
57 /** Used to seperate model definitions in model_check mode, should not appear in proof search */
58 MODEL_DEFINITION = 6
59 };
60
toNumber(UnitInputType t)61 inline std::underlying_type<UnitInputType>::type toNumber(UnitInputType t) { return static_cast<std::underlying_type<UnitInputType>::type>(t); }
62
63 UnitInputType getInputType(UnitList* units);
64 UnitInputType getInputType(UnitInputType t1, UnitInputType t2);
65
66 /**
67 * Tag to denote various kinds of inference rules.
68 */
69 enum class InferenceRule : unsigned char {
70 /** input formula or clause */
71 INPUT,
72
73 /** THIS DEFINES AN INTERVAL IN THIS ENUM WHERE ALL
74 * (preprocessing/normalisation) FORMULA TRANSFORMATION SHOULD BELONG
75 * (see also INTERNAL_FORMULA_TRANSFORMATION_LAST and isFormulaTransformation below). */
76 GENERIC_FORMULA_TRANSFORMATION,
77 /** negated conjecture from the input */
78 NEGATED_CONJECTURE,
79 /** introduction of answer literal into the conjecture,
80 * or the unit negation of answer literal used to obtain refutation */
81 ANSWER_LITERAL,
82 /** claim definition, definition introduced by a claim in the input */
83 CLAIM_DEFINITION,
84 // /** choice_axiom (Ax)((Ey)F(x,y) -> F(x,f(x))) */
85 // CHOICE_AXIOM,
86 // /** (Ax)(F(x)->F'(x)), G[F(t)] / G[F'(t)] */
87 // MONOTONE_REPLACEMENT,
88 // /** G[(Ax)F(x)] => G[F(t)] */
89 // FORALL_ELIMINATION,
90 /** rectify a formula */
91 RECTIFY,
92 // /** ~(F1 & ... & Fn) => ~F1 \/ ... \/ ~Fn */
93 // NOT_AND,
94 // /** ~(F1 \/ ... \/ Fn) => ~F1 & ... & ~Fn */
95 // NOT_OR,
96 // /** ~(F1 -> F2) => F1 & ~F2 */
97 // NOT_IMP,
98 // /** ~(F1 <-> F2) => F1 <~> F2 */
99 // NOT_IFF,
100 // /** ~(F1 <~> F2) => F1 <-> F2 */
101 // NOT_XOR = 1,
102 // /** ~~F => F */
103 // NOT_NOT = 1,
104 // /** ~(Ax)F => (Ex)~F */
105 // NOT_FORALL,
106 // /** ~(Ex)F => (Ax)~F */
107 // NOT_EXISTS,
108 // /** F1 -> F2 => ~F1 \/ F2 */
109 // IMP_TO_OR,
110 // /** F1 <-> F2 => (F1 -> F2) & (F2 -> F1) */
111 // IFF_TO_AND,
112 // /** F1 <~> F2 => (F1 \/ F2) & (~F1 \/ ~F2) */
113 // XOR_TO_AND,
114 /** replace formula F by (A x1...xn)F, where x1 ... xn are all
115 * free variables of F */
116 CLOSURE,
117 /** obtained by flattening (quantifiers, junctions) */
118 FLATTEN,
119 /** obtained by transformation into ENNF */
120 ENNF,
121 /** obtained by transformation into NNF */
122 NNF,
123 /** reduce a formula containing false or true, for example
124 * false & A ---> false */
125 REDUCE_FALSE_TRUE,
126
127 /** any kind of definition folding */
128 DEFINITION_FOLDING,
129 // /** Replace formula (Q x1 ... xk ... x_n)A by
130 // * (Q x1 ... xk-1 xk+1 ... x_n)A, where xk does not occur in A */
131 // DUMMY_QUANTIFIER_REMOVAL,
132 // /** Transformation (A x1 ... xn)(F1 & ... & Fm) ->
133 // * (A x1 ... xn)F1 & ... & (A x1 ... xn)Fm) */
134 // FORALL_AND,
135 // /** Transformation (E x1 ... xn)(F1 \/ ... \/ Fm) ->
136 // * (E x1 ... xn)F1 \/ ... \/ (E x1 ... xn)Fm) */
137 // EXISTS_OR,
138 // /** (Q x)(Q y)F -> (Q y)(Q x)F */
139 // QUANTIFIER_SWAP,
140 // /** Transformation (A x1 x2)(F1 \/ F2) ->
141 // * (A x1)F1 \/ ... \/ (A x2)F2), where x2 does not occur in F1.
142 // * Can be applied to many variables and disjunctions of arbitrary length */
143 // FORALL_OR,
144 // /** Transformation (E x1 x2)(F1 & F2) ->
145 // * (E x1)F1 & ... & (E x2)F2), where x2 does not occur in F1.
146 // * Can be applied to many variables and disjunctions of arbitrary length */
147 // EXISTS_AND,
148 // /** obtained by permutations, e.g. f <=> g replaced by g <=> f */
149 // PERMUT,
150 // /** obtained by reordering equalities */
151 // REORDER_EQ,
152 // /** obtained by rewriting a positive equivalence
153 // * f <=> ginto an implication f => g or g => f
154 // */
155 // HALF_EQUIV,
156 // /** miniscoping */
157 // MINISCOPE,
158 /** normalizing inference */
159 THEORY_NORMALIZATION,
160
161 /** skolemization */
162 SKOLEMIZE,
163 /** obtain clause from a formula */
164 CLAUSIFY,
165 /** the (preprocessing/normalisation) formula transformation marker --
166 inferences between GENERIC_FORMULA_TRANSFORMATION and INTERNAL_FORMULA_TRANSFORMATION_LAST
167 will be automatically understood as formula transformations (see also isFormulaTransformation) */
168 INTERNAL_FORMULA_TRANSFORMATION_LAST,
169
170 /** THIS DEFINES AN INTERVAL IN THIS ENUM WHERE ALL SIMPLIFYING INFERENCES SHOULD BELONG
171 * (see also INTERNAL_SIMPLIFYING_INFERNCE_LAST and isSimplifyingInferenceRule below). */
172 GENERIC_SIMPLIFYING_INFERNCE,
173 /** obtained by reordering literals */
174 REORDER_LITERALS,
175 /** obtain a clause from a clause by removing duplicate literals */
176 REMOVE_DUPLICATE_LITERALS,
177 /** remove from clause one or more inequalities <i>s != s</i> */
178 TRIVIAL_INEQUALITY_REMOVAL,
179 /** equality resolution as a simplification */
180 EQUALITY_RESOLUTION_WITH_DELETION,
181 /** subsumption resolution simplification rule */
182 SUBSUMPTION_RESOLUTION,
183 /** forward demodulation inference */
184 FORWARD_DEMODULATION,
185 /** backward demodulation inference */
186 BACKWARD_DEMODULATION,
187 /** forward subsumption demodulation inference */
188 FORWARD_SUBSUMPTION_DEMODULATION,
189 /** backward subsumption demodulation inference */
190 BACKWARD_SUBSUMPTION_DEMODULATION,
191 /** forward literal rewriting inference */
192 FORWARD_LITERAL_REWRITING,
193 /** inner rewriting */
194 INNER_REWRITING,
195 /** condensation inference */
196 CONDENSATION,
197 /** evaluation inference */
198 EVALUATION,
199 /** interpreted simplification inference */
200 INTERPRETED_SIMPLIFICATION,
201 //** Flatten a clause to separate theory literals */
202 THEORY_FLATTENING,
203 /** inference rule for term algebras (no equality between terms of different constructors)*/
204 TERM_ALGEBRA_DISTINCTNESS,
205 /** inference rule for term algebras (injectivity of constructors)*/
206 TERM_ALGEBRA_INJECTIVITY_SIMPLIFYING,
207 /** hyper-superposition */
208 HYPER_SUPERPOSITION_SIMPLIFYING, // not used at the moment
209 /** global subsumption */
210 GLOBAL_SUBSUMPTION, // CEREFUL: the main premise is not necessarily the first one!
211 /** distinct equality removal */
212 DISTINCT_EQUALITY_REMOVAL,
213 /** simplification eliminating variables by rewriting arithmetic equalities: e.g.: 6 = 3 x \/ L[x] => L[2] */
214 GAUSSIAN_VARIABLE_ELIMINIATION,
215 /** the last simplifying inference marker --
216 inferences between GENERIC_SIMPLIFYING_INFERNCE and INTERNAL_SIMPLIFYING_INFERNCE_LAST will be automatically understood simplifying
217 (see also isSimplifyingInferenceRule) */
218 INTERNAL_SIMPLIFYING_INFERNCE_LAST,
219
220
221 /** THIS DEFINES AN INTERVAL IN THIS ENUM WHERE ALL SIMPLIFYING INFERENCES SHOULD BELONG
222 * (see also INTERNAL_GENERATING_INFERNCE_LAST and isGeneratingInferenceRule below). */
223 GENERIC_GENERATING_INFERNCE,
224 /** resolution inference */
225 RESOLUTION,
226 /** constrained resolution inference */
227 CONSTRAINED_RESOLUTION,
228 /** factoring inference */
229 FACTORING,
230 /** factoring with constraints */
231 CONSTRAINED_FACTORING,
232 /** superposition inference */
233 SUPERPOSITION,
234 /** superposition with constraints */
235 CONSTRAINED_SUPERPOSITION,
236 /** equality factoring inference */
237 EQUALITY_FACTORING,
238 /** equality resolution inference */
239 EQUALITY_RESOLUTION,
240 /** redundant inference with extensionality-like clause */
241 EXTENSIONALITY_RESOLUTION,
242 /** inference rule for term algebras (injectivity of constructors)*/
243 TERM_ALGEBRA_INJECTIVITY_GENERATING,
244 /** inference rule for term algebras (no cyclic terms)*/
245 TERM_ALGEBRA_ACYCLICITY,
246 /** Replaces a literal of the form C[s] with C[true] \/ s = false, where s is a boolean non-variable term */
247 FOOL_PARAMODULATION,
248 /** unit resulting resolution */
249 UNIT_RESULTING_RESOLUTION,
250 /** hyper-superposition */
251 HYPER_SUPERPOSITION_GENERATING,
252 /** generated as instance of its parent */
253 INSTANCE_GENERATION, // used by InstGen. Fun fact: the inference has one parent (logically) but the age is set from two parents (and +1)!
254 /* Instantiation */
255 INSTANTIATION, // used for theory reasoning
256 /** the last generating inference marker --
257 inferences between GENERIC_GENERATING_INFERNCE and INTERNAL_GENERATING_INFERNCE_LAST will be automatically understood generating
258 (see also isGeneratingInferenceRule) */
259 INTERNAL_GENERATING_INFERNCE_LAST,
260
261
262 /** equality proxy replacement */
263 EQUALITY_PROXY_REPLACEMENT,
264 /** definition of the equality proxy predicate in the form E(x,y) <=> x=y */
265 EQUALITY_PROXY_AXIOM1,
266 /** equality proxy axioms such as E(x,x) or ~E(x,y) \/ x=y */
267 EQUALITY_PROXY_AXIOM2,
268 /** unfolding by definitions f(x1,...,xn)=t */
269 DEFINITION_UNFOLDING,
270
271 /** introduction of new name p, p <=> C */
272 PREDICATE_DEFINITION,
273 /** unfolding predicate definitions */
274 PREDICATE_DEFINITION_UNFOLDING,
275 /** merging predicate definitions */
276 PREDICATE_DEFINITION_MERGING,
277
278
279 /** unused predicate definition removal */
280 UNUSED_PREDICATE_DEFINITION_REMOVAL,
281 /** pure predicate removal */
282 PURE_PREDICATE_REMOVAL,
283 /** inequality splitting */
284 INEQUALITY_SPLITTING,
285 /** inequality splitting name introduction */
286 INEQUALITY_SPLITTING_NAME_INTRODUCTION,
287 /** grounding */
288 GROUNDING,
289 /** equality axiom */
290 EQUALITY_AXIOM,
291 /** distinctness axiom for numbers, generated by SimplifyProver */
292 SIMPLIFY_PROVER_DISTINCT_NUMBERS_AXIOM,
293 /** Introduction of formula to convert formulas used as argument positions.
294 * Such formulas have the form F->f(x)=1 or ~F->f(x)=0 */
295 BOOLEAN_TERM_ENCODING,
296 /** Elimination of FOOL expressions that makes a formula not syntactically first-order */
297 FOOL_ELIMINATION,
298 /** Elimination of $ite expressions */
299 FOOL_ITE_ELIMINATION,
300 /** Elimination of $let expressions */
301 FOOL_LET_ELIMINATION,
302 /** result of general splitting */
303 GENERAL_SPLITTING,
304 /** component introduced by general splitting */
305 GENERAL_SPLITTING_COMPONENT,
306 /** replacing colored constants by skolem functions */
307 COLOR_UNBLOCKING,
308
309 /** refutation in the SAT solver for InstGen */
310 SAT_INSTGEN_REFUTATION,
311
312 /** definition introduced by AVATAR */
313 AVATAR_DEFINITION,
314 /** component introduced by AVATAR */
315 AVATAR_COMPONENT,
316 /** refutation of a AVATAR splitting branch */
317 AVATAR_REFUTATION,
318 /** sat clause representing FO clause for AVATAR */
319 AVATAR_SPLIT_CLAUSE,
320 /** sat clause representing FO clause for AVATAR */
321 AVATAR_CONTRADICTION_CLAUSE,
322 /** sat color elimination */
323 SAT_COLOR_ELIMINATION,
324 /** obtain a formula from a clause */
325 FORMULIFY,
326
327 /** inference coming from outside of Vampire */
328 EXTERNAL,
329
330 /** BNFT flattening */
331 BFNT_FLATTENING,
332 /** BNFT axioms m != n */
333 BFNT_DISTINCT,
334 /** BNFT totality axioms R(x,1) \/ ... \/ R(x,n) */
335 BFNT_TOTALITY,
336
337 /* FMB flattening */
338 FMB_FLATTENING,
339 /* Functional definition for FMB */
340 FMB_FUNC_DEF,
341 /* Definition Introduction for FMB */
342 FMB_DEF_INTRO,
343 /* Finite model not found */
344 MODEL_NOT_FOUND,
345
346 /* Adding sort predicate */
347 ADD_SORT_PREDICATES,
348 /* Adding sort functions */
349 ADD_SORT_FUNCTIONS,
350
351 /** a premise to skolemization */
352 CHOICE_AXIOM,
353
354 /* Induction hypothesis*/
355 INDUCTION_AXIOM,
356 /* Generalized nduction hypothesis*/
357 GEN_INDUCTION_AXIOM,
358
359 /* the unit clause against which the Answer is extracted in the last step */
360 ANSWER_LITERAL_RESOLVER,
361
362 /** A (first-order) tautology generated on behalf of a decision procedure,
363 * whose propositional counterpart becomes a conflict clause in a sat solver */
364 THEORY_TAUTOLOGY_SAT_CONFLICT,
365
366 /** a not further specified theory axiom internally added by the class TheoryAxioms. */
367 GENERIC_THEORY_AXIOM, // CAREFUL: adding rules here influences the theory_split_queue heuristic
368 /** Some specific groups of axioms coming from TheoryAxioms.cpp" */
369 THA_COMMUTATIVITY,
370 THA_ASSOCIATIVITY,
371 THA_RIGHT_IDENTINTY,
372 THA_LEFT_IDENTINTY,
373 THA_INVERSE_OP_OP_INVERSES,
374 THA_INVERSE_OP_UNIT,
375 THA_INVERSE_ASSOC,
376 THA_NONREFLEX,
377 THA_TRANSITIVITY,
378 THA_ORDER_TOTALALITY,
379 THA_ORDER_MONOTONICITY,
380 THA_PLUS_ONE_GREATER,
381 THA_ORDER_PLUS_ONE_DICHOTOMY,
382 THA_MINUS_MINUS_X,
383 THA_TIMES_ZERO,
384 THA_DISTRIBUTIVITY,
385 THA_DIVISIBILITY,
386 THA_MODULO_MULTIPLY,
387 THA_MODULO_POSITIVE,
388 THA_MODULO_SMALL,
389 THA_DIVIDES_MULTIPLY,
390 THA_NONDIVIDES_SKOLEM,
391 THA_ABS_EQUALS,
392 THA_ABS_MINUS_EQUALS,
393 THA_QUOTIENT_NON_ZERO,
394 THA_QUOTIENT_MULTIPLY,
395 THA_EXTRA_INTEGER_ORDERING,
396 THA_FLOOR_SMALL,
397 THA_FLOOR_BIG,
398 THA_CEILING_BIG,
399 THA_CEILING_SMALL,
400 THA_TRUNC1,
401 THA_TRUNC2,
402 THA_TRUNC3,
403 THA_TRUNC4,
404 THA_ARRAY_EXTENSIONALITY,
405 THA_BOOLEAN_ARRAY_EXTENSIONALITY, // currently applied to a formula, so won't propagate to clause->isTheoryAxiom()
406 THA_BOOLEAN_ARRAY_WRITE1, // currently applied to a formula, so won't propagate to clause->isTheoryAxiom()
407 THA_BOOLEAN_ARRAY_WRITE2, // currently applied to a formula, so won't propagate to clause->isTheoryAxiom()
408 THA_ARRAY_WRITE1,
409 THA_ARRAY_WRITE2,
410 /** acyclicity axiom for term algebras */
411 TERM_ALGEBRA_ACYCLICITY_AXIOM,
412 TERM_ALGEBRA_DIRECT_SUBTERMS_AXIOM,
413 TERM_ALGEBRA_SUBTERMS_TRANSITIVE_AXIOM,
414 /** discrimination axiom for term algebras */
415 TERM_ALGEBRA_DISCRIMINATION_AXIOM,
416 /** distinctness axiom for term algebras */
417 TERM_ALGEBRA_DISTINCTNESS_AXIOM,
418 /** exhaustiveness axiom (or domain closure axiom) for term algebras */
419 TERM_ALGEBRA_EXHAUSTIVENESS_AXIOM, // currently (sometimes) applied to a formula, so won't propagate to clause->isTheoryAxiom()
420 /** exhaustiveness axiom (or domain closure axiom) for term algebras */
421 TERM_ALGEBRA_INJECTIVITY_AXIOM,
422 /** one of two axioms of FOOL (distinct constants or finite domain) */
423 FOOL_AXIOM_TRUE_NEQ_FALSE,
424 FOOL_AXIOM_ALL_IS_TRUE_OR_FALSE,
425 /** the last internal theory axiom marker --
426 axioms between THEORY_AXIOM and INTERNAL_THEORY_AXIOM_LAST will be automatically making their respective clauses isTheoryAxiom() true */
427 INTERNAL_THEORY_AXIOM_LAST,
428 /** a theory axiom which is not generated internally in Vampire */
429 EXTERNAL_THEORY_AXIOM
430 }; // class InferenceRule
431
toNumber(InferenceRule r)432 inline std::underlying_type<InferenceRule>::type toNumber(InferenceRule r) { return static_cast<std::underlying_type<InferenceRule>::type>(r); }
433
isFormulaTransformation(InferenceRule r)434 inline bool isFormulaTransformation(InferenceRule r) {
435 return (toNumber(r) >= toNumber(InferenceRule::GENERIC_FORMULA_TRANSFORMATION) &&
436 toNumber(r) < toNumber(InferenceRule::INTERNAL_FORMULA_TRANSFORMATION_LAST));
437 }
438
439 /** Currently not enforced but (almost) assumed:
440 * - these are simplifying inferences used during proof search
441 * - therefore they operate on Clauses
442 * - there is always a main premise, which is going to be the first one returned by Iterator
443 * (CAREFUL: this is currently a problem for GLOBAL_SUBSUMPTION)
444 * - the age of the corresponding Clause is the same as that of this main premise
445 **/
isSimplifyingInferenceRule(InferenceRule r)446 inline bool isSimplifyingInferenceRule(InferenceRule r) {
447 return (toNumber(r) >= toNumber(InferenceRule::GENERIC_SIMPLIFYING_INFERNCE) &&
448 toNumber(r) < toNumber(InferenceRule::INTERNAL_SIMPLIFYING_INFERNCE_LAST));
449 }
450
451 /**
452 * Currently not enforced but (almost) assumed:
453 * - these are generating inferences used during proof search
454 * - therefore they operate on Clauses
455 * - the age of the corresponding Clause is computed as the max over parent's ages +1
456 */
isGeneratingInferenceRule(InferenceRule r)457 inline bool isGeneratingInferenceRule(InferenceRule r) {
458 return (toNumber(r) >= toNumber(InferenceRule::GENERIC_GENERATING_INFERNCE) &&
459 toNumber(r) < toNumber(InferenceRule::INTERNAL_GENERATING_INFERNCE_LAST));
460 }
461
462 /** Currently not enforced but assumed:
463 * - theory axioms should not have any premises
464 **/
isTheoryAxiomRule(InferenceRule r)465 inline bool isTheoryAxiomRule(InferenceRule r) {
466 return (toNumber(r) >= toNumber(InferenceRule::GENERIC_THEORY_AXIOM) &&
467 toNumber(r) < toNumber(InferenceRule::INTERNAL_THEORY_AXIOM_LAST));
468 }
469
isExternalTheoryAxiomRule(InferenceRule r)470 inline bool isExternalTheoryAxiomRule(InferenceRule r) {
471 return r == InferenceRule::EXTERNAL_THEORY_AXIOM;
472 }
473
isSatRefutationRule(InferenceRule r)474 inline bool isSatRefutationRule(InferenceRule r) {
475 return (r == InferenceRule::AVATAR_REFUTATION) ||
476 (r == InferenceRule::SAT_INSTGEN_REFUTATION) ||
477 (r == InferenceRule::GLOBAL_SUBSUMPTION);
478 }
479
480 vstring ruleName(InferenceRule rule);
481
482 /*
483 * The following structs are here just that we can have specialized overloads for the Inference constructor (see below)
484 * There should be not computational overhead under modern compilers.
485 */
486
487 struct FromInput {
FromInputKernel::FromInput488 FromInput(UnitInputType it) : inputType(it) {}
489 UnitInputType inputType;
490 };
491
492 struct TheoryAxiom {
TheoryAxiomKernel::TheoryAxiom493 TheoryAxiom(InferenceRule r) : rule(r) {}
494 InferenceRule rule;
495 };
496
497 struct FormulaTransformation {
FormulaTransformationKernel::FormulaTransformation498 FormulaTransformation(InferenceRule r, Unit* p) : rule(r), premise(p) {}
499 InferenceRule rule;
500 Unit* premise;
501 };
502
503 struct FormulaTransformationMany {
FormulaTransformationManyKernel::FormulaTransformationMany504 FormulaTransformationMany(InferenceRule r, UnitList* p) : rule(r), premises(p) {}
505 InferenceRule rule;
506 UnitList* premises;
507 };
508
509 struct SimplifyingInference1 {
SimplifyingInference1Kernel::SimplifyingInference1510 SimplifyingInference1(InferenceRule r, Clause* main_premise) : rule(r), premise(main_premise) {}
511 InferenceRule rule;
512 Clause* premise;
513 };
514
515 struct SimplifyingInference2 {
SimplifyingInference2Kernel::SimplifyingInference2516 SimplifyingInference2(InferenceRule r, Clause* main_premise, Clause* other_premise) :
517 rule(r), premise1(main_premise), premise2(other_premise) {}
518 InferenceRule rule;
519 Clause* premise1;
520 Clause* premise2;
521 };
522
523 struct SimplifyingInferenceMany {
SimplifyingInferenceManyKernel::SimplifyingInferenceMany524 SimplifyingInferenceMany(InferenceRule r, UnitList* prems) : rule(r), premises(prems) {}
525 InferenceRule rule;
526 UnitList* premises;
527 };
528
529 struct GeneratingInference1 {
GeneratingInference1Kernel::GeneratingInference1530 GeneratingInference1(InferenceRule r, Clause* p) : rule(r), premise(p) {}
531 InferenceRule rule;
532 Clause* premise;
533 };
534
535 struct GeneratingInference2 {
GeneratingInference2Kernel::GeneratingInference2536 GeneratingInference2(InferenceRule r, Clause* p1, Clause* p2) : rule(r), premise1(p1), premise2(p2) {}
537 InferenceRule rule;
538 Clause* premise1;
539 Clause* premise2;
540 };
541
542 struct GeneratingInferenceMany {
GeneratingInferenceManyKernel::GeneratingInferenceMany543 GeneratingInferenceMany(InferenceRule r, UnitList* prems) : rule(r), premises(prems) {}
544 InferenceRule rule;
545 UnitList* premises;
546 };
547
548 struct NonspecificInference0 {
NonspecificInference0Kernel::NonspecificInference0549 NonspecificInference0(UnitInputType it, InferenceRule r) : inputType(it), rule(r) {}
550 UnitInputType inputType;
551 InferenceRule rule;
552 };
553
554 struct NonspecificInference1 {
NonspecificInference1Kernel::NonspecificInference1555 NonspecificInference1(InferenceRule r, Unit* p) : rule(r), premise(p) {}
556 InferenceRule rule;
557 Unit* premise;
558 };
559
560 struct NonspecificInference2 {
NonspecificInference2Kernel::NonspecificInference2561 NonspecificInference2(InferenceRule r, Unit* p1, Unit* p2) : rule(r), premise1(p1), premise2(p2) {}
562 InferenceRule rule;
563 Unit* premise1;
564 Unit* premise2;
565 };
566
567 struct NonspecificInferenceMany {
NonspecificInferenceManyKernel::NonspecificInferenceMany568 NonspecificInferenceMany(InferenceRule r, UnitList* prems) : rule(r), premises(prems) {}
569 InferenceRule rule;
570 UnitList* premises;
571 };
572
573 struct FromSatRefutation; // defined in SATInference.hpp
574
575 /**
576 * Class to represent inferences
577 */
578 class Inference
579 {
580 private:
581 // don't construct on the heap
582 CLASS_NAME(Inference);
583 USE_ALLOCATOR(Inference);
584
585 enum class Kind : unsigned char {
586 INFERENCE_012,
587 INFERENCE_MANY,
588 INFERENCE_FROM_SAT_REFUTATION
589 };
590
initDefault(UnitInputType inputType,InferenceRule r)591 void initDefault(UnitInputType inputType, InferenceRule r) {
592 CALL("Inference::initDefault");
593
594 _inputType = inputType;
595 _rule = r;
596 _included = false;
597 _inductionDepth = 0;
598 _sineLevel = std::numeric_limits<decltype(_sineLevel)>::max();
599 _splits = nullptr;
600 _age = 0;
601 }
602
603 void init0(UnitInputType inputType, InferenceRule r);
604 void init1(InferenceRule r, Unit* premise);
605 void init2(InferenceRule r, Unit* premise1, Unit* premise2);
606 void initMany(InferenceRule r, UnitList* premises);
607
608 public:
609 /* FromInput inferences are automatically InferenceRule::INPUT. */
610 Inference(const FromInput& fi);
611
612 /* Theory axioms are automatically of inputType AXIOM.
613 * and the corresponding rule should satisfy isTheoryAxiomRule
614 * CAREFUL: extending what TheoryAxiomRule is influences the theory_split_queue heuristic
615 **/
616 Inference(const TheoryAxiom& ta);
617
618 /* A formula transformation inference automatically propagates the _included flag from the parent to the child
619 (later during clausal proof search, currently, this is not done anymore)*/
620 Inference(const FormulaTransformation& ft);
621 // _included propagated from the first premise here
622 Inference(const FormulaTransformationMany& ft);
623
624 /* A generating inference automatically computes age as 1 + the maximum over the parents' age */
625 Inference(const GeneratingInference1& gi);
626 Inference(const GeneratingInference2& gi);
627 Inference(const GeneratingInferenceMany& gi);
628
629 /* A simplifying inference has a main premise and possibly also side premises.
630 * The age is automatically computed as the age of the main premise */
631 Inference(const SimplifyingInference1& si);
632 Inference(const SimplifyingInference2& si);
633 Inference(const SimplifyingInferenceMany& si);
634
635 /** No special propagation, no extra checks. Use sparingly. */
636 Inference(const NonspecificInference0& gi);
637 Inference(const NonspecificInference1& gi);
638 Inference(const NonspecificInference2& gi);
639 Inference(const NonspecificInferenceMany& gi);
640
641 Inference(const FromSatRefutation& fsr);
642
643 Inference(const Inference&) = default;
644
645 /**
646 * A class that iterates over parents.
647 * @since 04/01/2008 Torrevieja
648 */
649 struct Iterator {
650 /** The content, can be anything (interpretation depends on Kind) */
651 union {
652 void* pointer;
653 int integer;
654 };
655 };
656
657 Iterator iterator() const;
658 bool hasNext(Iterator& it) const;
659 Unit* next(Iterator& it) const;
660
661 /*
662 * The supporting heap allocated objects are deleted
663 * (The unitList of INFERENCE_MANY and, additionally,
664 * the FromSatRefutationInfo of INFERENCE_FROM_SAT_REFUTATION).
665 */
666 void destroyDirectlyOwned();
667 /**
668 * Decrease reference counters in referred units.
669 *
670 * Also does what destroyDirectlyOwned (see above).
671 */
672 void destroy();
673
674 /**
675 * Since we treat Inferences as PODs, this is intentionally left empty.
676 *
677 * Using this can lead to memory leaks unless reference counters in
678 * referred clauses are decreased extra. (Such as in Clause::destroy()
679 * which does not use Inference::destroy() to avoid deep recursion.)
680 */
~Inference()681 ~Inference() {}
682
683 /*
684 * Inference objects are not meant to generally live outside Units
685 * (who take care of calling destroy on Inference as appropriate).
686 * In the rare cases in which an Inference has not been passed to a Unit yet,
687 * a Destroyer can help calling destroy when coming out of scope prematurely
688 * (e.g. on Unit construction abort or exception occurring).
689 */
690 class Destroyer {
691 Inference* _destroyee;
692 public:
Destroyer(Inference & i)693 Destroyer(Inference& i) : _destroyee(&i) {}
~Destroyer()694 ~Destroyer() { if(_destroyee) _destroyee->destroy(); }
disable()695 void disable() { _destroyee = nullptr; }
696 };
697
698 /**
699 * After minimizePremises has been called, some inferences may have fewer parents,
700 * so statistics could change and this function recomputes them.
701 * The function is only responsible for the update between this inference and its parents (if any).
702 * The caller is responsible to ensure that parents are updated before children.
703 **/
704 void updateStatistics();
705
706 vstring toString() const;
707
708 /**
709 * To implement lazy minimization of proofs coming from a SAT solver
710 * without explicit proof recording.
711 *
712 * We want to postpone the potentially expensive
713 * minimizing call to after
714 * a complete refutation has been found.
715 *
716 * This is meant to be a no-op for all inferences except those related to SAT.
717 */
718 void minimizePremises();
719
name() const720 vstring name() const { return ruleName(_rule); }
721
722 /** return the input type of the unit */
inputType() const723 UnitInputType inputType() const { return (UnitInputType)_inputType; }
724 /** set the input type of the unit */
setInputType(UnitInputType it)725 void setInputType(UnitInputType it) { _inputType=it; }
726 /** return true if inputType relates to a goal **/
derivedFromGoal() const727 bool derivedFromGoal() const { return toNumber(_inputType) > toNumber(UnitInputType::ASSUMPTION); }
728
729 /** Return the inference rule */
rule() const730 InferenceRule rule() const { return _rule; }
731
getSineLevel() const732 unsigned char getSineLevel() const { return _sineLevel; }
733 /* should be only used to initialize the "whole chain" by SineUtils */
setSineLevel(unsigned char l)734 void setSineLevel(unsigned char l) { _sineLevel = l; }
735
736 /*
737 * returns true if clause is a theory axiom
738 *
739 * Definition: A unit is a theory axiom iff both
740 * 1) it is added internally in the TheoryAxiom-class or is an externally added theory axiom
741 * 2) it is a clause.
742 * In particular:
743 * - integer/rational/real theory axioms are internal theory axioms
744 * - term algebra axioms are internal theory axioms
745 * - FOOL axioms are internal theory axioms
746 * - equality-proxy-axioms, SimplifyProver’s-distinct-number-axioms, and BFNT-axioms
747 * are not treated as internal theory axioms, since they are not generated in TheoryAxioms
748 * (these axioms should probably be refactored into TheoryAxioms at some point)
749 * - consequences of theory axioms are not theory axioms
750 * - each theory axiom is a theory-tautology, but not every theory-tautology
751 * is a theory axiom (e.g. a consequence of two theory axioms or a conflict
752 * clause generated by a call to Z3)
753 * We are interested in whether a clause is an internal theory axiom, because of several reasons:
754 * - Internal theory axioms are already assumed to be clausal and simplified as much as possible
755 * - Internal theory axioms often blow up the search space
756 * - We don't need to pass internal theory axioms to another prover, if
757 * that prover natively handles the corresponding theory.
758 *
759 * TODO: handle the exhaustiveness axiom, which should be added as clause
760 */
isTheoryAxiom() const761 bool isTheoryAxiom() const {
762 return isExternalTheoryAxiomRule(_rule) || // maybe we don't want these?
763 isTheoryAxiomRule(_rule);
764 }
765
766 /*
767 * returns true if clause is an external theory axiom
768 *
769 * Definition: A unit is an external theory axiom iff it is added by parsing
770 * an external theory axioms (currently only happens in some LTB mode)
771 *
772 * We are interested in whether a clause is an external theory axiom, because of several reasons:
773 * - External theory axioms should already be simplified as much as possible
774 * - External theory axioms often blow up the search space
775 *
776 * TODO: If an unit u with inference EXTERNAL_THEORY_AXIOM is a formula (and therefore not a clause),
777 * the results c_i of clausifying u will not be labeled EXTERNAL_THEORY_AXIOM, and therefore this function
778 * will return false for c_i. In particular, adding the same formula as a clause or as formula could cause
779 * different behavior by Vampire, which is probably a bad thing.
780 */
isExternalTheoryAxiom() const781 bool isExternalTheoryAxiom() const {
782 return isExternalTheoryAxiomRule(_rule);
783 }
784
785 /** Mark the corresponding unit as read from a TPTP included file */
markIncluded()786 void markIncluded() { _included = 1; }
787 /** true if the unit is read from a TPTP included file */
included() const788 bool included() const { return _included; }
789
790 /*
791 * Returns true if the unit belonging to this inference is a pure theory descendant.
792 *
793 * Definition: A pure theory descendant is a unit that
794 * has a derivation where each leaf is a theory axiom.
795 * (This propagates in AVATAR from the clause being split to the corresponding components,
796 * because some people thought it should be that way.)
797 *
798 * Note that a theory axiom itself is also a pure theory descendant.
799 */
isPureTheoryDescendant() const800 bool isPureTheoryDescendant() const { return _isPureTheoryDescendant; }
801 /** This is how AVATAR sets it... */
setPureTheoryDescendant(bool val)802 void setPureTheoryDescendant(bool val) { _isPureTheoryDescendant = val; }
803
inductionDepth() const804 unsigned inductionDepth() const { return _inductionDepth; }
setInductionDepth(unsigned d)805 void setInductionDepth(unsigned d) { _inductionDepth = d; }
806
807 void computeTheoryRunningSums();
808
splits() const809 SplitSet* splits() const { return _splits; }
setSplits(SplitSet * splits)810 void setSplits(SplitSet* splits) {
811 ASS(splits != nullptr);
812 ASS(!_splits);
813 _splits=splits;
814 }
815
816 /** Return the age */
age() const817 unsigned age() const { return _age; }
818 /** Set the age to @b a */
setAge(unsigned a)819 void setAge(unsigned a) { _age = a; }
820
821 private:
822 Kind _kind : 2;
823
824 UnitInputType _inputType : 3;
825
826 /** The rule used */
827 InferenceRule _rule : 8;
828
829 /** true if the unit is read from a TPTP included file */
830 bool _included : 1;
831
832 /** track whether all leafs were theory axioms only */
833 bool _isPureTheoryDescendant : 1;
834
835 /** Induction depth **/
836 unsigned _inductionDepth : 5;
837
838 /** Sine level computed in SineUtils and used in various heuristics.
839 * May stay uninitialized (i.e. always MAX), if not needed
840 **/
841 unsigned char _sineLevel : 8; // updated as the minimum from parents to children
842
843 /** age */
844 unsigned _age;
845
846 SplitSet* _splits;
847
848 /**
849 * General storage for all Kinds of Inference:
850 * INFERENCE_012 - use ptr1 and ptr2 in sequence storing its up to two premises "left to right"
851 * - the unused are set to nullptr
852 * INFERENCE_MANY - uses ptr1 to point to a list of units, its premises
853 * INFERENCE_FROM_SAT_REFUTATION
854 * - uses ptr1 to point to a list of units, its premises;
855 * - uses ptr2 to point to a heap allocated struct for the sat premises and assumption
856 * which waits to be used during minimisation call; ptr2 can be empty (this means minimisation will be a noop)
857 **/
858 void* _ptr1;
859 void* _ptr2;
860
861 public:
862 // counting the leafs (in the tree rather than dag sense)
863 // which are theory axioms and the total across all leafs
864 float th_ancestors, all_ancestors; // we use floats, because this can grow large (because of the tree understanding of the dag);
865 // CAREFUL: could this lead to platform differences?
866 }; // class Inference
867
868 } // namespace Kernel
869
870 #endif
871